1/* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20/* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
22
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
33
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 */
39
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"
64
65/* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67static GTY(()) rtx_insn *cfg_layout_function_footer;
68static GTY(()) rtx_insn *cfg_layout_function_header;
69
70static rtx_insn *skip_insns_after_block (basic_block);
71static void record_effective_endpoints (void);
72static void fixup_reorder_chain (void);
73
74void verify_insn_chain (void);
75static void fixup_fallthru_exit_predecessor (void);
76static int can_delete_note_p (const rtx_note *);
77static int can_delete_label_p (const rtx_code_label *);
78static basic_block rtl_split_edge (edge);
79static bool rtl_move_block_after (basic_block, basic_block);
80static int rtl_verify_flow_info (void);
81static basic_block cfg_layout_split_block (basic_block, void *);
82static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
83static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
84static void cfg_layout_delete_block (basic_block);
85static void rtl_delete_block (basic_block);
86static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
87static edge rtl_redirect_edge_and_branch (edge, basic_block);
88static basic_block rtl_split_block (basic_block, void *);
89static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t);
90static int rtl_verify_flow_info_1 (void);
91static void rtl_make_forwarder_block (edge);
92
93/* Return true if NOTE is not one of the ones that must be kept paired,
94 so that we may simply delete it. */
95
96static int
97can_delete_note_p (const rtx_note *note)
98{
99 switch (NOTE_KIND (note))
100 {
101 case NOTE_INSN_DELETED:
102 case NOTE_INSN_BASIC_BLOCK:
103 case NOTE_INSN_EPILOGUE_BEG:
104 return true;
105
106 default:
107 return false;
108 }
109}
110
111/* True if a given label can be deleted. */
112
113static int
114can_delete_label_p (const rtx_code_label *label)
115{
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)));
121}
122
123/* Delete INSN by patching it out. */
124
125void
126delete_insn (rtx_insn *insn)
127{
128 rtx note;
129 bool really_delete = true;
130
131 if (LABEL_P (insn))
132 {
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)))
137 {
138 const char *name = LABEL_NAME (insn);
139 basic_block bb = BLOCK_FOR_INSN (insn);
140 rtx_insn *bb_note = NEXT_INSN (insn);
141
142 really_delete = false;
143 PUT_CODE (insn, NOTE);
144 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
145 NOTE_DELETED_LABEL_NAME (insn) = name;
146
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))
153 {
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;
158 }
159 }
160
161 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
162 }
163
164 if (really_delete)
165 {
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 ();
172 }
173
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))
177 {
178 if (JUMP_LABEL (insn)
179 && LABEL_P (JUMP_LABEL (insn)))
180 LABEL_NUSES (JUMP_LABEL (insn))--;
181
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)))
186 {
187 LABEL_NUSES (XEXP (note, 0))--;
188 remove_note (insn, note);
189 }
190 }
191
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)))
195 {
196 LABEL_NUSES (XEXP (note, 0))--;
197 remove_note (insn, note);
198 }
199
200 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
201 {
202 rtvec vec = table->get_labels ();
203 int len = GET_NUM_ELEM (vec);
204 int i;
205
206 for (i = 0; i < len; i++)
207 {
208 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
209
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)--;
215 }
216 }
217}
218
219/* Like delete_insn but also purge dead edges from BB.
220 Return true if any edges are eliminated. */
221
222bool
223delete_insn_and_edges (rtx_insn *insn)
224{
225 bool purge = false;
226
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;
235}
236
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. */
240
241void
242delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb)
243{
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)
249 {
250 rtx_insn *prev = PREV_INSN (current);
251 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
252 ;
253 else
254 delete_insn (current);
255
256 if (clear_bb && !current->deleted ())
257 set_block_for_insn (current, NULL);
258
259 if (current == start)
260 break;
261 current = prev;
262 }
263}
264
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. */
272
273basic_block
274create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
275 basic_block after)
276{
277 basic_block bb;
278
279 if (bb_note
280 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
281 && bb->aux == NULL)
282 {
283 /* If we found an existing note, thread it back onto the chain. */
284
285 rtx_insn *after;
286
287 if (LABEL_P (head))
288 after = head;
289 else
290 {
291 after = PREV_INSN (head);
292 head = bb_note;
293 }
294
295 if (after != bb_note && NEXT_INSN (after) != bb_note)
296 reorder_insns_nobb (bb_note, bb_note, after);
297 }
298 else
299 {
300 /* Otherwise we must create a note and a basic block structure. */
301
302 bb = alloc_block ();
303
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)
309 {
310 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
311 if (head == end)
312 end = bb_note;
313 }
314 else
315 {
316 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
317 head = bb_note;
318 if (!end)
319 end = head;
320 }
321
322 NOTE_BASIC_BLOCK (bb_note) = bb;
323 }
324
325 /* Always include the bb note in the block. */
326 if (NEXT_INSN (end) == bb_note)
327 end = bb_note;
328
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);
338
339 /* Tag the block so that we know it has been used when considering
340 other basic block notes. */
341 bb->aux = bb;
342
343 return bb;
344}
345
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. */
350
351static basic_block
352rtl_create_basic_block (void *headp, void *endp, basic_block after)
353{
354 rtx_insn *head = (rtx_insn *) headp;
355 rtx_insn *end = (rtx_insn *) endp;
356 basic_block bb;
357
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 ())
361 {
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);
366 }
367
368 n_basic_blocks_for_fn (cfun)++;
369
370 bb = create_basic_block_structure (head, end, NULL, after);
371 bb->aux = NULL;
372 return bb;
373}
374
375static basic_block
376cfg_layout_create_basic_block (void *head, void *end, basic_block after)
377{
378 basic_block newbb = rtl_create_basic_block (head, end, after);
379
380 return newbb;
381}
382
383/* Delete the insns in a (non-live) block. We physically delete every
384 non-deleted-note insn, and update the flow graph appropriately.
385
386 Return nonzero if we deleted an exception handler. */
387
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. */
390
391static void
392rtl_delete_block (basic_block b)
393{
394 rtx_insn *insn, *end;
395
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);
400
401 end = get_last_bb_insn (b);
402
403 /* Selectively delete the entire chain. */
404 BB_HEAD (b) = NULL;
405 delete_insn_chain (insn, end, true);
406
407
408 if (dump_file)
409 fprintf (dump_file, "deleting block %d\n", b->index);
410 df_bb_delete (b->index);
411}
412
413/* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
414
415void
416compute_bb_for_insn (void)
417{
418 basic_block bb;
419
420 FOR_EACH_BB_FN (bb, cfun)
421 {
422 rtx_insn *end = BB_END (bb);
423 rtx_insn *insn;
424
425 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
426 {
427 BLOCK_FOR_INSN (insn) = bb;
428 if (insn == end)
429 break;
430 }
431 }
432}
433
434/* Release the basic_block_for_insn array. */
435
436unsigned int
437free_bb_for_insn (void)
438{
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;
444}
445
446namespace {
447
448const pass_data pass_data_free_cfg =
449{
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 */
459};
460
461class pass_free_cfg : public rtl_opt_pass
462{
463public:
464 pass_free_cfg (gcc::context *ctxt)
465 : rtl_opt_pass (pass_data_free_cfg, ctxt)
466 {}
467
468 /* opt_pass methods: */
469 virtual unsigned int execute (function *);
470
471}; // class pass_free_cfg
472
473unsigned int
474pass_free_cfg::execute (function *)
475{
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)
479 {
480 df_note_add_problem ();
481 df_analyze ();
482 }
483
484 if (crtl->has_bb_partition)
485 insert_section_boundary_note ();
486
487 free_bb_for_insn ();
488 return 0;
489}
490
491} // anon namespace
492
493rtl_opt_pass *
494make_pass_free_cfg (gcc::context *ctxt)
495{
496 return new pass_free_cfg (ctxt);
497}
498
499/* Return RTX to emit after when we want to emit code on the entry of function. */
500rtx_insn *
501entry_of_function (void)
502{
503 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
504 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
505}
506
507/* Emit INSN at the entry point of the function, ensuring that it is only
508 executed once per function. */
509void
510emit_insn_at_entry (rtx insn)
511{
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);
515
516 insert_insn_on_edge (insn, e);
517 commit_edge_insertions ();
518}
519
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. */
524
525static void
526update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
527{
528 rtx_insn *insn;
529
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);
534}
535
536/* Update BLOCK_FOR_INSN of insns in BB to BB,
537 and notify df of the change. */
538
539void
540update_bb_for_insn (basic_block bb)
541{
542 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
543}
544
545
546/* Like active_insn_p, except keep the return value clobber around
547 even after reload. */
548
549static bool
550flow_active_insn_p (const rtx_insn *insn)
551{
552 if (active_insn_p (insn))
553 return true;
554
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;
564
565 return false;
566}
567
568/* Return true if the block has no effect and only forwards control flow to
569 its single destination. */
570
571bool
572contains_no_active_insn_p (const_basic_block bb)
573{
574 rtx_insn *insn;
575
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;
581
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;
585
586 return (!INSN_P (insn)
587 || (JUMP_P (insn) && simplejump_p (insn))
588 || !flow_active_insn_p (insn));
589}
590
591/* Likewise, but protect loop latches, headers and preheaders. */
592/* FIXME: Make this a cfg hook. */
593
594bool
595forwarder_block_p (const_basic_block bb)
596{
597 if (!contains_no_active_insn_p (bb))
598 return false;
599
600 /* Protect loop latches, headers and preheaders. */
601 if (current_loops)
602 {
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;
609 }
610
611 return true;
612}
613
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. */
616
617bool
618can_fallthru (basic_block src, basic_block target)
619{
620 rtx_insn *insn = BB_END (src);
621 rtx_insn *insn2;
622 edge e;
623 edge_iterator ei;
624
625 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
626 return true;
627 if (src->next_bb != target)
628 return false;
629
630 /* ??? Later we may add code to move jump tables offline. */
631 if (tablejump_p (insn, NULL, NULL))
632 return false;
633
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;
638
639 insn2 = BB_HEAD (target);
640 if (!active_insn_p (insn2))
641 insn2 = next_active_insn (insn2);
642
643 return next_active_insn (insn) == insn2;
644}
645
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. */
649static bool
650could_fall_through (basic_block src, basic_block target)
651{
652 edge e;
653 edge_iterator ei;
654
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;
662}
663
664/* Return the NOTE_INSN_BASIC_BLOCK of BB. */
665rtx_note *
666bb_note (basic_block bb)
667{
668 rtx_insn *note;
669
670 note = BB_HEAD (bb);
671 if (LABEL_P (note))
672 note = NEXT_INSN (note);
673
674 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
675 return as_a <rtx_note *> (note);
676}
677
678/* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
679 note associated with the BLOCK. */
680
681static rtx_insn *
682first_insn_after_basic_block_note (basic_block block)
683{
684 rtx_insn *insn;
685
686 /* Get the first instruction in the block. */
687 insn = BB_HEAD (block);
688
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));
694
695 return NEXT_INSN (insn);
696}
697
698/* Creates a new basic block just after basic block BB by splitting
699 everything after specified instruction INSNP. */
700
701static basic_block
702rtl_split_block (basic_block bb, void *insnp)
703{
704 basic_block new_bb;
705 rtx_insn *insn = (rtx_insn *) insnp;
706 edge e;
707 edge_iterator ei;
708
709 if (!insn)
710 {
711 insn = first_insn_after_basic_block_note (bb);
712
713 if (insn)
714 {
715 rtx_insn *next = insn;
716
717 insn = PREV_INSN (insn);
718
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)))
726 {
727 while (next != BB_END (bb) && DEBUG_INSN_P (next))
728 next = NEXT_INSN (next);
729
730 if (next == BB_END (bb))
731 emit_note_after (NOTE_INSN_DELETED, next);
732 }
733 }
734 else
735 insn = get_last_insn ();
736 }
737
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);
743
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;
748
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;
754
755 /* The new block starts off being dirty. */
756 df_set_bb_dirty (bb);
757 return new_bb;
758}
759
760/* Return true if the single edge between blocks A and B is the only place
761 in RTL which holds some unique locus. */
762
763static bool
764unique_locus_on_edge_between_p (basic_block a, basic_block b)
765{
766 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
767 rtx_insn *insn, *end;
768
769 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
770 return false;
771
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);
777
778 if (insn != end && INSN_LOCATION (insn) == goto_locus)
779 return false;
780
781 /* Then scan block B forward. */
782 insn = BB_HEAD (b);
783 if (insn)
784 {
785 end = NEXT_INSN (BB_END (b));
786 while (insn != end && !NONDEBUG_INSN_P (insn))
787 insn = NEXT_INSN (insn);
788
789 if (insn != end && INSN_HAS_LOCATION (insn)
790 && INSN_LOCATION (insn) == goto_locus)
791 return false;
792 }
793
794 return true;
795}
796
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. */
799
800static void
801emit_nop_for_unique_locus_between (basic_block a, basic_block b)
802{
803 if (!unique_locus_on_edge_between_p (a, b))
804 return;
805
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;
808}
809
810/* Blocks A and B are to be merged into a single block A. The insns
811 are already contiguous. */
812
813static void
814rtl_merge_blocks (basic_block a, basic_block b)
815{
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;
821
822 if (dump_file)
823 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
824 a->index);
825
826 while (DEBUG_INSN_P (b_end))
827 b_end = PREV_INSN (b_debug_start = b_end);
828
829 /* If there was a CODE_LABEL beginning B, delete it. */
830 if (LABEL_P (b_head))
831 {
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;
836
837 del_first = del_last = b_head;
838 b_head = NEXT_INSN (b_head);
839 }
840
841 /* Delete the basic block note and handle blocks containing just that
842 note. */
843 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
844 {
845 if (b_head == b_end)
846 b_empty = 1;
847 if (! del_last)
848 del_first = b_head;
849
850 del_last = b_head;
851 b_head = NEXT_INSN (b_head);
852 }
853
854 /* If there was a jump out of A, delete it. */
855 if (JUMP_P (a_end))
856 {
857 rtx_insn *prev;
858
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;
864
865 del_first = a_end;
866
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))
870 {
871 rtx_insn *tmp = prev;
872
873 prev = prev_nonnote_insn (prev);
874 if (!prev)
875 prev = BB_HEAD (a);
876 del_first = tmp;
877 }
878
879 a_end = PREV_INSN (del_first);
880 }
881 else if (BARRIER_P (NEXT_INSN (a_end)))
882 del_first = NEXT_INSN (a_end);
883
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);
889
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)
893 {
894 emit_nop_for_unique_locus_between (a, b);
895 a_end = BB_END (a);
896 }
897
898 /* Reassociate the insns of B with A. */
899 if (!b_empty)
900 {
901 update_bb_for_insn_chain (a_end, b_debug_end, a);
902
903 BB_END (a) = b_debug_end;
904 BB_HEAD (b) = NULL;
905 }
906 else if (b_end != b_debug_end)
907 {
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;
917 }
918
919 df_bb_delete (b->index);
920
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;
925
926 if (dump_file)
927 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
928}
929
930
931/* Return true when block A and B can be merged. */
932
933static bool
934rtl_can_merge_blocks (basic_block a, basic_block b)
935{
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.
939
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. */
945
946 if (BB_PARTITION (a) != BB_PARTITION (b))
947 return false;
948
949 /* Protect the loop latches. */
950 if (current_loops && b->loop_father->latch == b)
951 return false;
952
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)))));
968}
969
970/* Return the label in the head of basic block BLOCK. Create one if it doesn't
971 exist. */
972
973rtx_code_label *
974block_label (basic_block block)
975{
976 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
977 return NULL;
978
979 if (!LABEL_P (BB_HEAD (block)))
980 {
981 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
982 }
983
984 return as_a <rtx_code_label *> (BB_HEAD (block));
985}
986
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. */
991
992edge
993try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
994{
995 basic_block src = e->src;
996 rtx_insn *insn = BB_END (src), *kill_from;
997 rtx set;
998 int fallthru = 0;
999
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.
1003
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. */
1009
1010 if (BB_PARTITION (src) != BB_PARTITION (target))
1011 return NULL;
1012
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;
1022
1023 if (!onlyjump_p (insn))
1024 return NULL;
1025 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1026 return NULL;
1027
1028 /* Avoid removing branch with side effects. */
1029 set = single_set (insn);
1030 if (!set || side_effects_p (set))
1031 return NULL;
1032
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);
1039
1040 /* See if we can create the fallthru edge. */
1041 if (in_cfglayout || can_fallthru (src, target))
1042 {
1043 if (dump_file)
1044 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1045 fallthru = 1;
1046
1047 /* Selectively unlink whole insn chain. */
1048 if (in_cfglayout)
1049 {
1050 rtx_insn *insn = BB_FOOTER (src);
1051
1052 delete_insn_chain (kill_from, BB_END (src), false);
1053
1054 /* Remove barriers but keep jumptables. */
1055 while (insn)
1056 {
1057 if (BARRIER_P (insn))
1058 {
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);
1065 }
1066 if (LABEL_P (insn))
1067 break;
1068 insn = NEXT_INSN (insn);
1069 }
1070 }
1071 else
1072 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1073 false);
1074 }
1075
1076 /* If this already is simplejump, redirect it. */
1077 else if (simplejump_p (insn))
1078 {
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))
1086 {
1087 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1088 return NULL;
1089 }
1090 }
1091
1092 /* Cannot do anything for target exit block. */
1093 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1094 return NULL;
1095
1096 /* Or replace possibly complicated jump insn by simple jump insn. */
1097 else
1098 {
1099 rtx_code_label *target_label = block_label (target);
1100 rtx_insn *barrier;
1101 rtx_insn *label;
1102 rtx_jump_table_data *table;
1103
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)));
1110
1111
1112 delete_insn_chain (kill_from, insn, false);
1113
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);
1119
1120 barrier = next_nonnote_nondebug_insn (BB_END (src));
1121 if (!barrier || !BARRIER_P (barrier))
1122 emit_barrier_after (BB_END (src));
1123 else
1124 {
1125 if (barrier != NEXT_INSN (BB_END (src)))
1126 {
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);
1131
1132 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1133 PREV_INSN (barrier), src);
1134
1135 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1136 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1137
1138 SET_NEXT_INSN (new_insn) = barrier;
1139 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1140
1141 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1142 SET_PREV_INSN (barrier) = new_insn;
1143 }
1144 }
1145 }
1146
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));
1151
1152 e = single_succ_edge (src);
1153 if (fallthru)
1154 e->flags = EDGE_FALLTHRU;
1155 else
1156 e->flags = 0;
1157
1158 e->probability = profile_probability::always ();
1159
1160 if (e->dest != target)
1161 redirect_edge_succ (e, target);
1162 return e;
1163}
1164
1165/* Subroutine of redirect_branch_edge that tries to patch the jump
1166 instruction INSN so that it reaches block NEW. Do this
1167 only when it originally reached block OLD. Return true if this
1168 worked or the original target wasn't OLD, return false if redirection
1169 doesn't work. */
1170
1171static bool
1172patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1173{
1174 rtx_jump_table_data *table;
1175 rtx tmp;
1176 /* Recognize a tablejump and adjust all matching cases. */
1177 if (tablejump_p (insn, NULL, &table))
1178 {
1179 rtvec vec;
1180 int j;
1181 rtx_code_label *new_label = block_label (new_bb);
1182
1183 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1184 return false;
1185 vec = table->get_labels ();
1186
1187 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1188 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1189 {
1190 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1191 --LABEL_NUSES (old_label);
1192 ++LABEL_NUSES (new_label);
1193 }
1194
1195 /* Handle casesi dispatch insns. */
1196 if ((tmp = single_set (insn)) != NULL
1197 && SET_DEST (tmp) == pc_rtx
1198 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1199 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1200 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1201 {
1202 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1203 new_label);
1204 --LABEL_NUSES (old_label);
1205 ++LABEL_NUSES (new_label);
1206 }
1207 }
1208 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1209 {
1210 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1211 rtx note;
1212
1213 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1214 return false;
1215 rtx_code_label *new_label = block_label (new_bb);
1216
1217 for (i = 0; i < n; ++i)
1218 {
1219 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1220 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1221 if (XEXP (old_ref, 0) == old_label)
1222 {
1223 ASM_OPERANDS_LABEL (tmp, i)
1224 = gen_rtx_LABEL_REF (Pmode, new_label);
1225 --LABEL_NUSES (old_label);
1226 ++LABEL_NUSES (new_label);
1227 }
1228 }
1229
1230 if (JUMP_LABEL (insn) == old_label)
1231 {
1232 JUMP_LABEL (insn) = new_label;
1233 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1234 if (note)
1235 remove_note (insn, note);
1236 }
1237 else
1238 {
1239 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1240 if (note)
1241 remove_note (insn, note);
1242 if (JUMP_LABEL (insn) != new_label
1243 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1244 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1245 }
1246 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1247 != NULL_RTX)
1248 XEXP (note, 0) = new_label;
1249 }
1250 else
1251 {
1252 /* ?? We may play the games with moving the named labels from
1253 one basic block to the other in case only one computed_jump is
1254 available. */
1255 if (computed_jump_p (insn)
1256 /* A return instruction can't be redirected. */
1257 || returnjump_p (insn))
1258 return false;
1259
1260 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1261 {
1262 /* If the insn doesn't go where we think, we're confused. */
1263 gcc_assert (JUMP_LABEL (insn) == old_label);
1264
1265 /* If the substitution doesn't succeed, die. This can happen
1266 if the back end emitted unrecognizable instructions or if
1267 target is exit block on some arches. */
1268 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1269 block_label (new_bb), 0))
1270 {
1271 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1272 return false;
1273 }
1274 }
1275 }
1276 return true;
1277}
1278
1279
1280/* Redirect edge representing branch of (un)conditional jump or tablejump,
1281 NULL on failure */
1282static edge
1283redirect_branch_edge (edge e, basic_block target)
1284{
1285 rtx_insn *old_label = BB_HEAD (e->dest);
1286 basic_block src = e->src;
1287 rtx_insn *insn = BB_END (src);
1288
1289 /* We can only redirect non-fallthru edges of jump insn. */
1290 if (e->flags & EDGE_FALLTHRU)
1291 return NULL;
1292 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1293 return NULL;
1294
1295 if (!currently_expanding_to_rtl)
1296 {
1297 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1298 return NULL;
1299 }
1300 else
1301 /* When expanding this BB might actually contain multiple
1302 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1303 Redirect all of those that match our label. */
1304 FOR_BB_INSNS (src, insn)
1305 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1306 old_label, target))
1307 return NULL;
1308
1309 if (dump_file)
1310 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1311 e->src->index, e->dest->index, target->index);
1312
1313 if (e->dest != target)
1314 e = redirect_edge_succ_nodup (e, target);
1315
1316 return e;
1317}
1318
1319/* Called when edge E has been redirected to a new destination,
1320 in order to update the region crossing flag on the edge and
1321 jump. */
1322
1323static void
1324fixup_partition_crossing (edge e)
1325{
1326 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1327 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1328 return;
1329 /* If we redirected an existing edge, it may already be marked
1330 crossing, even though the new src is missing a reg crossing note.
1331 But make sure reg crossing note doesn't already exist before
1332 inserting. */
1333 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1334 {
1335 e->flags |= EDGE_CROSSING;
1336 if (JUMP_P (BB_END (e->src)))
1337 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1338 }
1339 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1340 {
1341 e->flags &= ~EDGE_CROSSING;
1342 /* Remove the section crossing note from jump at end of
1343 src if it exists, and if no other successors are
1344 still crossing. */
1345 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1346 {
1347 bool has_crossing_succ = false;
1348 edge e2;
1349 edge_iterator ei;
1350 FOR_EACH_EDGE (e2, ei, e->src->succs)
1351 {
1352 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1353 if (has_crossing_succ)
1354 break;
1355 }
1356 if (!has_crossing_succ)
1357 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1358 }
1359 }
1360}
1361
1362/* Called when block BB has been reassigned to the cold partition,
1363 because it is now dominated by another cold block,
1364 to ensure that the region crossing attributes are updated. */
1365
1366static void
1367fixup_new_cold_bb (basic_block bb)
1368{
1369 edge e;
1370 edge_iterator ei;
1371
1372 /* This is called when a hot bb is found to now be dominated
1373 by a cold bb and therefore needs to become cold. Therefore,
1374 its preds will no longer be region crossing. Any non-dominating
1375 preds that were previously hot would also have become cold
1376 in the caller for the same region. Any preds that were previously
1377 region-crossing will be adjusted in fixup_partition_crossing. */
1378 FOR_EACH_EDGE (e, ei, bb->preds)
1379 {
1380 fixup_partition_crossing (e);
1381 }
1382
1383 /* Possibly need to make bb's successor edges region crossing,
1384 or remove stale region crossing. */
1385 FOR_EACH_EDGE (e, ei, bb->succs)
1386 {
1387 /* We can't have fall-through edges across partition boundaries.
1388 Note that force_nonfallthru will do any necessary partition
1389 boundary fixup by calling fixup_partition_crossing itself. */
1390 if ((e->flags & EDGE_FALLTHRU)
1391 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1392 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1393 force_nonfallthru (e);
1394 else
1395 fixup_partition_crossing (e);
1396 }
1397}
1398
1399/* Attempt to change code to redirect edge E to TARGET. Don't do that on
1400 expense of adding new instructions or reordering basic blocks.
1401
1402 Function can be also called with edge destination equivalent to the TARGET.
1403 Then it should try the simplifications and do nothing if none is possible.
1404
1405 Return edge representing the branch if transformation succeeded. Return NULL
1406 on failure.
1407 We still return NULL in case E already destinated TARGET and we didn't
1408 managed to simplify instruction stream. */
1409
1410static edge
1411rtl_redirect_edge_and_branch (edge e, basic_block target)
1412{
1413 edge ret;
1414 basic_block src = e->src;
1415 basic_block dest = e->dest;
1416
1417 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1418 return NULL;
1419
1420 if (dest == target)
1421 return e;
1422
1423 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1424 {
1425 df_set_bb_dirty (src);
1426 fixup_partition_crossing (ret);
1427 return ret;
1428 }
1429
1430 ret = redirect_branch_edge (e, target);
1431 if (!ret)
1432 return NULL;
1433
1434 df_set_bb_dirty (src);
1435 fixup_partition_crossing (ret);
1436 return ret;
1437}
1438
1439/* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1440
1441void
1442emit_barrier_after_bb (basic_block bb)
1443{
1444 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1445 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1446 || current_ir_type () == IR_RTL_CFGLAYOUT);
1447 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1448 {
1449 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1450
1451 if (BB_FOOTER (bb))
1452 {
1453 rtx_insn *footer_tail = BB_FOOTER (bb);
1454
1455 while (NEXT_INSN (footer_tail))
1456 footer_tail = NEXT_INSN (footer_tail);
1457 if (!BARRIER_P (footer_tail))
1458 {
1459 SET_NEXT_INSN (footer_tail) = insn;
1460 SET_PREV_INSN (insn) = footer_tail;
1461 }
1462 }
1463 else
1464 BB_FOOTER (bb) = insn;
1465 }
1466}
1467
1468/* Like force_nonfallthru below, but additionally performs redirection
1469 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1470 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1471 simple_return_rtx, indicating which kind of returnjump to create.
1472 It should be NULL otherwise. */
1473
1474basic_block
1475force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1476{
1477 basic_block jump_block, new_bb = NULL, src = e->src;
1478 rtx note;
1479 edge new_edge;
1480 int abnormal_edge_flags = 0;
1481 bool asm_goto_edge = false;
1482 int loc;
1483
1484 /* In the case the last instruction is conditional jump to the next
1485 instruction, first redirect the jump itself and then continue
1486 by creating a basic block afterwards to redirect fallthru edge. */
1487 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1488 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1489 && any_condjump_p (BB_END (e->src))
1490 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1491 {
1492 rtx note;
1493 edge b = unchecked_make_edge (e->src, target, 0);
1494 bool redirected;
1495
1496 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1497 block_label (target), 0);
1498 gcc_assert (redirected);
1499
1500 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1501 if (note)
1502 {
1503 int prob = XINT (note, 0);
1504
1505 b->probability = profile_probability::from_reg_br_prob_note (prob);
1506 e->probability -= e->probability;
1507 }
1508 }
1509
1510 if (e->flags & EDGE_ABNORMAL)
1511 {
1512 /* Irritating special case - fallthru edge to the same block as abnormal
1513 edge.
1514 We can't redirect abnormal edge, but we still can split the fallthru
1515 one and create separate abnormal edge to original destination.
1516 This allows bb-reorder to make such edge non-fallthru. */
1517 gcc_assert (e->dest == target);
1518 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1519 e->flags &= EDGE_FALLTHRU;
1520 }
1521 else
1522 {
1523 gcc_assert (e->flags & EDGE_FALLTHRU);
1524 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1525 {
1526 /* We can't redirect the entry block. Create an empty block
1527 at the start of the function which we use to add the new
1528 jump. */
1529 edge tmp;
1530 edge_iterator ei;
1531 bool found = false;
1532
1533 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1534 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1535 bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1536
1537 /* Change the existing edge's source to be the new block, and add
1538 a new edge from the entry block to the new block. */
1539 e->src = bb;
1540 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1541 (tmp = ei_safe_edge (ei)); )
1542 {
1543 if (tmp == e)
1544 {
1545 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1546 found = true;
1547 break;
1548 }
1549 else
1550 ei_next (&ei);
1551 }
1552
1553 gcc_assert (found);
1554
1555 vec_safe_push (bb->succs, e);
1556 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1557 EDGE_FALLTHRU);
1558 }
1559 }
1560
1561 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1562 don't point to the target or fallthru label. */
1563 if (JUMP_P (BB_END (e->src))
1564 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1565 && (e->flags & EDGE_FALLTHRU)
1566 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1567 {
1568 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1569 bool adjust_jump_target = false;
1570
1571 for (i = 0; i < n; ++i)
1572 {
1573 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1574 {
1575 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1576 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1577 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1578 adjust_jump_target = true;
1579 }
1580 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1581 asm_goto_edge = true;
1582 }
1583 if (adjust_jump_target)
1584 {
1585 rtx_insn *insn = BB_END (e->src);
1586 rtx note;
1587 rtx_insn *old_label = BB_HEAD (e->dest);
1588 rtx_insn *new_label = BB_HEAD (target);
1589
1590 if (JUMP_LABEL (insn) == old_label)
1591 {
1592 JUMP_LABEL (insn) = new_label;
1593 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1594 if (note)
1595 remove_note (insn, note);
1596 }
1597 else
1598 {
1599 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1600 if (note)
1601 remove_note (insn, note);
1602 if (JUMP_LABEL (insn) != new_label
1603 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1604 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1605 }
1606 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1607 != NULL_RTX)
1608 XEXP (note, 0) = new_label;
1609 }
1610 }
1611
1612 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1613 {
1614 rtx_insn *new_head;
1615 profile_count count = e->count ();
1616 profile_probability probability = e->probability;
1617 /* Create the new structures. */
1618
1619 /* If the old block ended with a tablejump, skip its table
1620 by searching forward from there. Otherwise start searching
1621 forward from the last instruction of the old block. */
1622 rtx_jump_table_data *table;
1623 if (tablejump_p (BB_END (e->src), NULL, &table))
1624 new_head = table;
1625 else
1626 new_head = BB_END (e->src);
1627 new_head = NEXT_INSN (new_head);
1628 /* Make sure we don't split a call and its corresponding
1629 CALL_ARG_LOCATION note. */
1630 if (new_head && NOTE_P (new_head)
1631 && NOTE_KIND (new_head) == NOTE_INSN_CALL_ARG_LOCATION)
1632 new_head = NEXT_INSN (new_head);
1633
1634 jump_block = create_basic_block (new_head, NULL, e->src);
1635 jump_block->count = count;
1636
1637 /* Make sure new block ends up in correct hot/cold section. */
1638
1639 BB_COPY_PARTITION (jump_block, e->src);
1640
1641 /* Wire edge in. */
1642 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1643 new_edge->probability = probability;
1644
1645 /* Redirect old edge. */
1646 redirect_edge_pred (e, jump_block);
1647 e->probability = profile_probability::always ();
1648
1649 /* If e->src was previously region crossing, it no longer is
1650 and the reg crossing note should be removed. */
1651 fixup_partition_crossing (new_edge);
1652
1653 /* If asm goto has any label refs to target's label,
1654 add also edge from asm goto bb to target. */
1655 if (asm_goto_edge)
1656 {
1657 new_edge->probability = new_edge->probability.apply_scale (1, 2);
1658 jump_block->count = jump_block->count.apply_scale (1, 2);
1659 edge new_edge2 = make_edge (new_edge->src, target,
1660 e->flags & ~EDGE_FALLTHRU);
1661 new_edge2->probability = probability - new_edge->probability;
1662 }
1663
1664 new_bb = jump_block;
1665 }
1666 else
1667 jump_block = e->src;
1668
1669 loc = e->goto_locus;
1670 e->flags &= ~EDGE_FALLTHRU;
1671 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1672 {
1673 if (jump_label == ret_rtx)
1674 emit_jump_insn_after_setloc (targetm.gen_return (),
1675 BB_END (jump_block), loc);
1676 else
1677 {
1678 gcc_assert (jump_label == simple_return_rtx);
1679 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1680 BB_END (jump_block), loc);
1681 }
1682 set_return_jump_label (BB_END (jump_block));
1683 }
1684 else
1685 {
1686 rtx_code_label *label = block_label (target);
1687 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1688 BB_END (jump_block), loc);
1689 JUMP_LABEL (BB_END (jump_block)) = label;
1690 LABEL_NUSES (label)++;
1691 }
1692
1693 /* We might be in cfg layout mode, and if so, the following routine will
1694 insert the barrier correctly. */
1695 emit_barrier_after_bb (jump_block);
1696 redirect_edge_succ_nodup (e, target);
1697
1698 if (abnormal_edge_flags)
1699 make_edge (src, target, abnormal_edge_flags);
1700
1701 df_mark_solutions_dirty ();
1702 fixup_partition_crossing (e);
1703 return new_bb;
1704}
1705
1706/* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1707 (and possibly create new basic block) to make edge non-fallthru.
1708 Return newly created BB or NULL if none. */
1709
1710static basic_block
1711rtl_force_nonfallthru (edge e)
1712{
1713 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1714}
1715
1716/* Redirect edge even at the expense of creating new jump insn or
1717 basic block. Return new basic block if created, NULL otherwise.
1718 Conversion must be possible. */
1719
1720static basic_block
1721rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1722{
1723 if (redirect_edge_and_branch (e, target)
1724 || e->dest == target)
1725 return NULL;
1726
1727 /* In case the edge redirection failed, try to force it to be non-fallthru
1728 and redirect newly created simplejump. */
1729 df_set_bb_dirty (e->src);
1730 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1731}
1732
1733/* The given edge should potentially be a fallthru edge. If that is in
1734 fact true, delete the jump and barriers that are in the way. */
1735
1736static void
1737rtl_tidy_fallthru_edge (edge e)
1738{
1739 rtx_insn *q;
1740 basic_block b = e->src, c = b->next_bb;
1741
1742 /* ??? In a late-running flow pass, other folks may have deleted basic
1743 blocks by nopping out blocks, leaving multiple BARRIERs between here
1744 and the target label. They ought to be chastised and fixed.
1745
1746 We can also wind up with a sequence of undeletable labels between
1747 one block and the next.
1748
1749 So search through a sequence of barriers, labels, and notes for
1750 the head of block C and assert that we really do fall through. */
1751
1752 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1753 if (NONDEBUG_INSN_P (q))
1754 return;
1755
1756 /* Remove what will soon cease being the jump insn from the source block.
1757 If block B consisted only of this single jump, turn it into a deleted
1758 note. */
1759 q = BB_END (b);
1760 if (JUMP_P (q)
1761 && onlyjump_p (q)
1762 && (any_uncondjump_p (q)
1763 || single_succ_p (b)))
1764 {
1765 rtx_insn *label;
1766 rtx_jump_table_data *table;
1767
1768 if (tablejump_p (q, &label, &table))
1769 {
1770 /* The label is likely mentioned in some instruction before
1771 the tablejump and might not be DCEd, so turn it into
1772 a note instead and move before the tablejump that is going to
1773 be deleted. */
1774 const char *name = LABEL_NAME (label);
1775 PUT_CODE (label, NOTE);
1776 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1777 NOTE_DELETED_LABEL_NAME (label) = name;
1778 reorder_insns (label, label, PREV_INSN (q));
1779 delete_insn (table);
1780 }
1781
1782 /* If this was a conditional jump, we need to also delete
1783 the insn that set cc0. */
1784 if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1785 q = PREV_INSN (q);
1786
1787 q = PREV_INSN (q);
1788 }
1789 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1790 together with the barrier) should never have a fallthru edge. */
1791 else if (JUMP_P (q) && any_uncondjump_p (q))
1792 return;
1793
1794 /* Selectively unlink the sequence. */
1795 if (q != PREV_INSN (BB_HEAD (c)))
1796 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1797
1798 e->flags |= EDGE_FALLTHRU;
1799}
1800
1801/* Should move basic block BB after basic block AFTER. NIY. */
1802
1803static bool
1804rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1805 basic_block after ATTRIBUTE_UNUSED)
1806{
1807 return false;
1808}
1809
1810/* Locate the last bb in the same partition as START_BB. */
1811
1812static basic_block
1813last_bb_in_partition (basic_block start_bb)
1814{
1815 basic_block bb;
1816 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1817 {
1818 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1819 return bb;
1820 }
1821 /* Return bb before the exit block. */
1822 return bb->prev_bb;
1823}
1824
1825/* Split a (typically critical) edge. Return the new block.
1826 The edge must not be abnormal.
1827
1828 ??? The code generally expects to be called on critical edges.
1829 The case of a block ending in an unconditional jump to a
1830 block with multiple predecessors is not handled optimally. */
1831
1832static basic_block
1833rtl_split_edge (edge edge_in)
1834{
1835 basic_block bb, new_bb;
1836 rtx_insn *before;
1837
1838 /* Abnormal edges cannot be split. */
1839 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1840
1841 /* We are going to place the new block in front of edge destination.
1842 Avoid existence of fallthru predecessors. */
1843 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1844 {
1845 edge e = find_fallthru_edge (edge_in->dest->preds);
1846
1847 if (e)
1848 force_nonfallthru (e);
1849 }
1850
1851 /* Create the basic block note. */
1852 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1853 before = BB_HEAD (edge_in->dest);
1854 else
1855 before = NULL;
1856
1857 /* If this is a fall through edge to the exit block, the blocks might be
1858 not adjacent, and the right place is after the source. */
1859 if ((edge_in->flags & EDGE_FALLTHRU)
1860 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1861 {
1862 before = NEXT_INSN (BB_END (edge_in->src));
1863 bb = create_basic_block (before, NULL, edge_in->src);
1864 BB_COPY_PARTITION (bb, edge_in->src);
1865 }
1866 else
1867 {
1868 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1869 {
1870 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1871 BB_COPY_PARTITION (bb, edge_in->dest);
1872 }
1873 else
1874 {
1875 basic_block after = edge_in->dest->prev_bb;
1876 /* If this is post-bb reordering, and the edge crosses a partition
1877 boundary, the new block needs to be inserted in the bb chain
1878 at the end of the src partition (since we put the new bb into
1879 that partition, see below). Otherwise we may end up creating
1880 an extra partition crossing in the chain, which is illegal.
1881 It can't go after the src, because src may have a fall-through
1882 to a different block. */
1883 if (crtl->bb_reorder_complete
1884 && (edge_in->flags & EDGE_CROSSING))
1885 {
1886 after = last_bb_in_partition (edge_in->src);
1887 before = get_last_bb_insn (after);
1888 /* The instruction following the last bb in partition should
1889 be a barrier, since it cannot end in a fall-through. */
1890 gcc_checking_assert (BARRIER_P (before));
1891 before = NEXT_INSN (before);
1892 }
1893 bb = create_basic_block (before, NULL, after);
1894 /* Put the split bb into the src partition, to avoid creating
1895 a situation where a cold bb dominates a hot bb, in the case
1896 where src is cold and dest is hot. The src will dominate
1897 the new bb (whereas it might not have dominated dest). */
1898 BB_COPY_PARTITION (bb, edge_in->src);
1899 }
1900 }
1901
1902 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1903
1904 /* Can't allow a region crossing edge to be fallthrough. */
1905 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1906 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1907 {
1908 new_bb = force_nonfallthru (single_succ_edge (bb));
1909 gcc_assert (!new_bb);
1910 }
1911
1912 /* For non-fallthru edges, we must adjust the predecessor's
1913 jump instruction to target our new block. */
1914 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1915 {
1916 edge redirected = redirect_edge_and_branch (edge_in, bb);
1917 gcc_assert (redirected);
1918 }
1919 else
1920 {
1921 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1922 {
1923 /* For asm goto even splitting of fallthru edge might
1924 need insn patching, as other labels might point to the
1925 old label. */
1926 rtx_insn *last = BB_END (edge_in->src);
1927 if (last
1928 && JUMP_P (last)
1929 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1930 && (extract_asm_operands (PATTERN (last))
1931 || JUMP_LABEL (last) == before)
1932 && patch_jump_insn (last, before, bb))
1933 df_set_bb_dirty (edge_in->src);
1934 }
1935 redirect_edge_succ (edge_in, bb);
1936 }
1937
1938 return bb;
1939}
1940
1941/* Queue instructions for insertion on an edge between two basic blocks.
1942 The new instructions and basic blocks (if any) will not appear in the
1943 CFG until commit_edge_insertions is called. */
1944
1945void
1946insert_insn_on_edge (rtx pattern, edge e)
1947{
1948 /* We cannot insert instructions on an abnormal critical edge.
1949 It will be easier to find the culprit if we die now. */
1950 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1951
1952 if (e->insns.r == NULL_RTX)
1953 start_sequence ();
1954 else
1955 push_to_sequence (e->insns.r);
1956
1957 emit_insn (pattern);
1958
1959 e->insns.r = get_insns ();
1960 end_sequence ();
1961}
1962
1963/* Update the CFG for the instructions queued on edge E. */
1964
1965void
1966commit_one_edge_insertion (edge e)
1967{
1968 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1969 basic_block bb;
1970
1971 /* Pull the insns off the edge now since the edge might go away. */
1972 insns = e->insns.r;
1973 e->insns.r = NULL;
1974
1975 /* Figure out where to put these insns. If the destination has
1976 one predecessor, insert there. Except for the exit block. */
1977 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1978 {
1979 bb = e->dest;
1980
1981 /* Get the location correct wrt a code label, and "nice" wrt
1982 a basic block note, and before everything else. */
1983 tmp = BB_HEAD (bb);
1984 if (LABEL_P (tmp))
1985 tmp = NEXT_INSN (tmp);
1986 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1987 tmp = NEXT_INSN (tmp);
1988 if (tmp == BB_HEAD (bb))
1989 before = tmp;
1990 else if (tmp)
1991 after = PREV_INSN (tmp);
1992 else
1993 after = get_last_insn ();
1994 }
1995
1996 /* If the source has one successor and the edge is not abnormal,
1997 insert there. Except for the entry block.
1998 Don't do this if the predecessor ends in a jump other than
1999 unconditional simple jump. E.g. for asm goto that points all
2000 its labels at the fallthru basic block, we can't insert instructions
2001 before the asm goto, as the asm goto can have various of side effects,
2002 and can't emit instructions after the asm goto, as it must end
2003 the basic block. */
2004 else if ((e->flags & EDGE_ABNORMAL) == 0
2005 && single_succ_p (e->src)
2006 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2007 && (!JUMP_P (BB_END (e->src))
2008 || simplejump_p (BB_END (e->src))))
2009 {
2010 bb = e->src;
2011
2012 /* It is possible to have a non-simple jump here. Consider a target
2013 where some forms of unconditional jumps clobber a register. This
2014 happens on the fr30 for example.
2015
2016 We know this block has a single successor, so we can just emit
2017 the queued insns before the jump. */
2018 if (JUMP_P (BB_END (bb)))
2019 before = BB_END (bb);
2020 else
2021 {
2022 /* We'd better be fallthru, or we've lost track of what's what. */
2023 gcc_assert (e->flags & EDGE_FALLTHRU);
2024
2025 after = BB_END (bb);
2026 }
2027 }
2028
2029 /* Otherwise we must split the edge. */
2030 else
2031 {
2032 bb = split_edge (e);
2033
2034 /* If E crossed a partition boundary, we needed to make bb end in
2035 a region-crossing jump, even though it was originally fallthru. */
2036 if (JUMP_P (BB_END (bb)))
2037 before = BB_END (bb);
2038 else
2039 after = BB_END (bb);
2040 }
2041
2042 /* Now that we've found the spot, do the insertion. */
2043 if (before)
2044 {
2045 emit_insn_before_noloc (insns, before, bb);
2046 last = prev_nonnote_insn (before);
2047 }
2048 else
2049 last = emit_insn_after_noloc (insns, after, bb);
2050
2051 if (returnjump_p (last))
2052 {
2053 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2054 This is not currently a problem because this only happens
2055 for the (single) epilogue, which already has a fallthru edge
2056 to EXIT. */
2057
2058 e = single_succ_edge (bb);
2059 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2060 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2061
2062 e->flags &= ~EDGE_FALLTHRU;
2063 emit_barrier_after (last);
2064
2065 if (before)
2066 delete_insn (before);
2067 }
2068 else
2069 gcc_assert (!JUMP_P (last));
2070}
2071
2072/* Update the CFG for all queued instructions. */
2073
2074void
2075commit_edge_insertions (void)
2076{
2077 basic_block bb;
2078
2079 /* Optimization passes that invoke this routine can cause hot blocks
2080 previously reached by both hot and cold blocks to become dominated only
2081 by cold blocks. This will cause the verification below to fail,
2082 and lead to now cold code in the hot section. In some cases this
2083 may only be visible after newly unreachable blocks are deleted,
2084 which will be done by fixup_partitions. */
2085 fixup_partitions ();
2086
2087 checking_verify_flow_info ();
2088
2089 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2090 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2091 {
2092 edge e;
2093 edge_iterator ei;
2094
2095 FOR_EACH_EDGE (e, ei, bb->succs)
2096 if (e->insns.r)
2097 commit_one_edge_insertion (e);
2098 }
2099}
2100
2101
2102/* Print out RTL-specific basic block information (live information
2103 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2104 documented in dumpfile.h. */
2105
2106static void
2107rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2108{
2109 char *s_indent;
2110
2111 s_indent = (char *) alloca ((size_t) indent + 1);
2112 memset (s_indent, ' ', (size_t) indent);
2113 s_indent[indent] = '\0';
2114
2115 if (df && (flags & TDF_DETAILS))
2116 {
2117 df_dump_top (bb, outf);
2118 putc ('\n', outf);
2119 }
2120
2121 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2122 {
2123 rtx_insn *last = BB_END (bb);
2124 if (last)
2125 last = NEXT_INSN (last);
2126 for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2127 {
2128 if (flags & TDF_DETAILS)
2129 df_dump_insn_top (insn, outf);
2130 if (! (flags & TDF_SLIM))
2131 print_rtl_single (outf, insn);
2132 else
2133 dump_insn_slim (outf, insn);
2134 if (flags & TDF_DETAILS)
2135 df_dump_insn_bottom (insn, outf);
2136 }
2137 }
2138
2139 if (df && (flags & TDF_DETAILS))
2140 {
2141 df_dump_bottom (bb, outf);
2142 putc ('\n', outf);
2143 }
2144
2145}
2146
2147/* Like dump_function_to_file, but for RTL. Print out dataflow information
2148 for the start of each basic block. FLAGS are the TDF_* masks documented
2149 in dumpfile.h. */
2150
2151void
2152print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2153{
2154 const rtx_insn *tmp_rtx;
2155 if (rtx_first == 0)
2156 fprintf (outf, "(nil)\n");
2157 else
2158 {
2159 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2160 int max_uid = get_max_uid ();
2161 basic_block *start = XCNEWVEC (basic_block, max_uid);
2162 basic_block *end = XCNEWVEC (basic_block, max_uid);
2163 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2164 basic_block bb;
2165
2166 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2167 insns, but the CFG is not maintained so the basic block info
2168 is not reliable. Therefore it's omitted from the dumps. */
2169 if (! (cfun->curr_properties & PROP_cfg))
2170 flags &= ~TDF_BLOCKS;
2171
2172 if (df)
2173 df_dump_start (outf);
2174
2175 if (flags & TDF_BLOCKS)
2176 {
2177 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2178 {
2179 rtx_insn *x;
2180
2181 start[INSN_UID (BB_HEAD (bb))] = bb;
2182 end[INSN_UID (BB_END (bb))] = bb;
2183 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2184 {
2185 enum bb_state state = IN_MULTIPLE_BB;
2186
2187 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2188 state = IN_ONE_BB;
2189 in_bb_p[INSN_UID (x)] = state;
2190
2191 if (x == BB_END (bb))
2192 break;
2193 }
2194 }
2195 }
2196
2197 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2198 {
2199 if (flags & TDF_BLOCKS)
2200 {
2201 bb = start[INSN_UID (tmp_rtx)];
2202 if (bb != NULL)
2203 {
2204 dump_bb_info (outf, bb, 0, dump_flags, true, false);
2205 if (df && (flags & TDF_DETAILS))
2206 df_dump_top (bb, outf);
2207 }
2208
2209 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2210 && !NOTE_P (tmp_rtx)
2211 && !BARRIER_P (tmp_rtx))
2212 fprintf (outf, ";; Insn is not within a basic block\n");
2213 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2214 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2215 }
2216
2217 if (flags & TDF_DETAILS)
2218 df_dump_insn_top (tmp_rtx, outf);
2219 if (! (flags & TDF_SLIM))
2220 print_rtl_single (outf, tmp_rtx);
2221 else
2222 dump_insn_slim (outf, tmp_rtx);
2223 if (flags & TDF_DETAILS)
2224 df_dump_insn_bottom (tmp_rtx, outf);
2225
2226 if (flags & TDF_BLOCKS)
2227 {
2228 bb = end[INSN_UID (tmp_rtx)];
2229 if (bb != NULL)
2230 {
2231 dump_bb_info (outf, bb, 0, dump_flags, false, true);
2232 if (df && (flags & TDF_DETAILS))
2233 df_dump_bottom (bb, outf);
2234 putc ('\n', outf);
2235 }
2236 }
2237 }
2238
2239 free (start);
2240 free (end);
2241 free (in_bb_p);
2242 }
2243}
2244
2245/* Update the branch probability of BB if a REG_BR_PROB is present. */
2246
2247void
2248update_br_prob_note (basic_block bb)
2249{
2250 rtx note;
2251 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2252 if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2253 {
2254 if (note)
2255 {
2256 rtx *note_link, this_rtx;
2257
2258 note_link = &REG_NOTES (BB_END (bb));
2259 for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1))
2260 if (this_rtx == note)
2261 {
2262 *note_link = XEXP (this_rtx, 1);
2263 break;
2264 }
2265 }
2266 return;
2267 }
2268 if (!note
2269 || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2270 return;
2271 XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2272}
2273
2274/* Get the last insn associated with block BB (that includes barriers and
2275 tablejumps after BB). */
2276rtx_insn *
2277get_last_bb_insn (basic_block bb)
2278{
2279 rtx_jump_table_data *table;
2280 rtx_insn *tmp;
2281 rtx_insn *end = BB_END (bb);
2282
2283 /* Include any jump table following the basic block. */
2284 if (tablejump_p (end, NULL, &table))
2285 end = table;
2286
2287 /* Include any barriers that may follow the basic block. */
2288 tmp = next_nonnote_nondebug_insn_bb (end);
2289 while (tmp && BARRIER_P (tmp))
2290 {
2291 end = tmp;
2292 tmp = next_nonnote_nondebug_insn_bb (end);
2293 }
2294
2295 return end;
2296}
2297
2298/* Add all BBs reachable from entry via hot paths into the SET. */
2299
2300void
2301find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2302{
2303 auto_vec<basic_block, 64> worklist;
2304
2305 set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2306 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2307
2308 while (worklist.length () > 0)
2309 {
2310 basic_block bb = worklist.pop ();
2311 edge_iterator ei;
2312 edge e;
2313
2314 FOR_EACH_EDGE (e, ei, bb->succs)
2315 if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2316 && !set->add (e->dest))
2317 worklist.safe_push (e->dest);
2318 }
2319}
2320
2321/* Sanity check partition hotness to ensure that basic blocks in
2322   the cold partition don't dominate basic blocks in the hot partition.
2323 If FLAG_ONLY is true, report violations as errors. Otherwise
2324 re-mark the dominated blocks as cold, since this is run after
2325 cfg optimizations that may make hot blocks previously reached
2326 by both hot and cold blocks now only reachable along cold paths. */
2327
2328static vec<basic_block>
2329find_partition_fixes (bool flag_only)
2330{
2331 basic_block bb;
2332 vec<basic_block> bbs_in_cold_partition = vNULL;
2333 vec<basic_block> bbs_to_fix = vNULL;
2334 hash_set<basic_block> set;
2335
2336 /* Callers check this. */
2337 gcc_checking_assert (crtl->has_bb_partition);
2338
2339 find_bbs_reachable_by_hot_paths (&set);
2340
2341 FOR_EACH_BB_FN (bb, cfun)
2342 if (!set.contains (bb)
2343 && BB_PARTITION (bb) != BB_COLD_PARTITION)
2344 {
2345 if (flag_only)
2346 error ("non-cold basic block %d reachable only "
2347 "by paths crossing the cold partition", bb->index);
2348 else
2349 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2350 bbs_to_fix.safe_push (bb);
2351 bbs_in_cold_partition.safe_push (bb);
2352 }
2353
2354 return bbs_to_fix;
2355}
2356
2357/* Perform cleanup on the hot/cold bb partitioning after optimization
2358 passes that modify the cfg. */
2359
2360void
2361fixup_partitions (void)
2362{
2363 basic_block bb;
2364
2365 if (!crtl->has_bb_partition)
2366 return;
2367
2368 /* Delete any blocks that became unreachable and weren't
2369 already cleaned up, for example during edge forwarding
2370 and convert_jumps_to_returns. This will expose more
2371 opportunities for fixing the partition boundaries here.
2372 Also, the calculation of the dominance graph during verification
2373 will assert if there are unreachable nodes. */
2374 delete_unreachable_blocks ();
2375
2376 /* If there are partitions, do a sanity check on them: A basic block in
2377   a cold partition cannot dominate a basic block in a hot partition.
2378 Fixup any that now violate this requirement, as a result of edge
2379 forwarding and unreachable block deletion.  */
2380 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2381
2382 /* Do the partition fixup after all necessary blocks have been converted to
2383 cold, so that we only update the region crossings the minimum number of
2384 places, which can require forcing edges to be non fallthru. */
2385 while (! bbs_to_fix.is_empty ())
2386 {
2387 bb = bbs_to_fix.pop ();
2388 fixup_new_cold_bb (bb);
2389 }
2390}
2391
2392/* Verify, in the basic block chain, that there is at most one switch
2393 between hot/cold partitions. This condition will not be true until
2394 after reorder_basic_blocks is called. */
2395
2396static int
2397verify_hot_cold_block_grouping (void)
2398{
2399 basic_block bb;
2400 int err = 0;
2401 bool switched_sections = false;
2402 int current_partition = BB_UNPARTITIONED;
2403
2404 /* Even after bb reordering is complete, we go into cfglayout mode
2405 again (in compgoto). Ensure we don't call this before going back
2406 into linearized RTL when any layout fixes would have been committed. */
2407 if (!crtl->bb_reorder_complete
2408 || current_ir_type () != IR_RTL_CFGRTL)
2409 return err;
2410
2411 FOR_EACH_BB_FN (bb, cfun)
2412 {
2413 if (current_partition != BB_UNPARTITIONED
2414 && BB_PARTITION (bb) != current_partition)
2415 {
2416 if (switched_sections)
2417 {
2418 error ("multiple hot/cold transitions found (bb %i)",
2419 bb->index);
2420 err = 1;
2421 }
2422 else
2423 switched_sections = true;
2424
2425 if (!crtl->has_bb_partition)
2426 error ("partition found but function partition flag not set");
2427 }
2428 current_partition = BB_PARTITION (bb);
2429 }
2430
2431 return err;
2432}
2433
2434
2435/* Perform several checks on the edges out of each block, such as
2436 the consistency of the branch probabilities, the correctness
2437 of hot/cold partition crossing edges, and the number of expected
2438 successor edges. Also verify that the dominance relationship
2439 between hot/cold blocks is sane. */
2440
2441static int
2442rtl_verify_edges (void)
2443{
2444 int err = 0;
2445 basic_block bb;
2446
2447 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2448 {
2449 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2450 int n_eh = 0, n_abnormal = 0;
2451 edge e, fallthru = NULL;
2452 edge_iterator ei;
2453 rtx note;
2454 bool has_crossing_edge = false;
2455
2456 if (JUMP_P (BB_END (bb))
2457 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2458 && EDGE_COUNT (bb->succs) >= 2
2459 && any_condjump_p (BB_END (bb)))
2460 {
2461 if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2462 {
2463 if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2464 {
2465 error ("verify_flow_info: "
2466 "REG_BR_PROB is set but cfg probability is not");
2467 err = 1;
2468 }
2469 }
2470 else if (XINT (note, 0)
2471 != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2472 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2473 {
2474 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2475 XINT (note, 0),
2476 BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2477 err = 1;
2478 }
2479 }
2480
2481 FOR_EACH_EDGE (e, ei, bb->succs)
2482 {
2483 bool is_crossing;
2484
2485 if (e->flags & EDGE_FALLTHRU)
2486 n_fallthru++, fallthru = e;
2487
2488 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2489 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2490 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2491 has_crossing_edge |= is_crossing;
2492 if (e->flags & EDGE_CROSSING)
2493 {
2494 if (!is_crossing)
2495 {
2496 error ("EDGE_CROSSING incorrectly set across same section");
2497 err = 1;
2498 }
2499 if (e->flags & EDGE_FALLTHRU)
2500 {
2501 error ("fallthru edge crosses section boundary in bb %i",
2502 e->src->index);
2503 err = 1;
2504 }
2505 if (e->flags & EDGE_EH)
2506 {
2507 error ("EH edge crosses section boundary in bb %i",
2508 e->src->index);
2509 err = 1;
2510 }
2511 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2512 {
2513 error ("No region crossing jump at section boundary in bb %i",
2514 bb->index);
2515 err = 1;
2516 }
2517 }
2518 else if (is_crossing)
2519 {
2520 error ("EDGE_CROSSING missing across section boundary");
2521 err = 1;
2522 }
2523
2524 if ((e->flags & ~(EDGE_DFS_BACK
2525 | EDGE_CAN_FALLTHRU
2526 | EDGE_IRREDUCIBLE_LOOP
2527 | EDGE_LOOP_EXIT
2528 | EDGE_CROSSING
2529 | EDGE_PRESERVE)) == 0)
2530 n_branch++;
2531
2532 if (e->flags & EDGE_ABNORMAL_CALL)
2533 n_abnormal_call++;
2534
2535 if (e->flags & EDGE_SIBCALL)
2536 n_sibcall++;
2537
2538 if (e->flags & EDGE_EH)
2539 n_eh++;
2540
2541 if (e->flags & EDGE_ABNORMAL)
2542 n_abnormal++;
2543 }
2544
2545 if (!has_crossing_edge
2546 && JUMP_P (BB_END (bb))
2547 && CROSSING_JUMP_P (BB_END (bb)))
2548 {
2549 print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2550 error ("Region crossing jump across same section in bb %i",
2551 bb->index);
2552 err = 1;
2553 }
2554
2555 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2556 {
2557 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2558 err = 1;
2559 }
2560 if (n_eh > 1)
2561 {
2562 error ("too many exception handling edges in bb %i", bb->index);
2563 err = 1;
2564 }
2565 if (n_branch
2566 && (!JUMP_P (BB_END (bb))
2567 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2568 || any_condjump_p (BB_END (bb))))))
2569 {
2570 error ("too many outgoing branch edges from bb %i", bb->index);
2571 err = 1;
2572 }
2573 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2574 {
2575 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2576 err = 1;
2577 }
2578 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2579 {
2580 error ("wrong number of branch edges after unconditional jump"
2581 " in bb %i", bb->index);
2582 err = 1;
2583 }
2584 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2585 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2586 {
2587 error ("wrong amount of branch edges after conditional jump"
2588 " in bb %i", bb->index);
2589 err = 1;
2590 }
2591 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2592 {
2593 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2594 err = 1;
2595 }
2596 if (n_sibcall && !CALL_P (BB_END (bb)))
2597 {
2598 error ("sibcall edges for non-call insn in bb %i", bb->index);
2599 err = 1;
2600 }
2601 if (n_abnormal > n_eh
2602 && !(CALL_P (BB_END (bb))
2603 && n_abnormal == n_abnormal_call + n_sibcall)
2604 && (!JUMP_P (BB_END (bb))
2605 || any_condjump_p (BB_END (bb))
2606 || any_uncondjump_p (BB_END (bb))))
2607 {
2608 error ("abnormal edges for no purpose in bb %i", bb->index);
2609 err = 1;
2610 }
2611 }
2612
2613 /* If there are partitions, do a sanity check on them: A basic block in
2614   a cold partition cannot dominate a basic block in a hot partition.  */
2615 if (crtl->has_bb_partition && !err)
2616 {
2617 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2618 err = !bbs_to_fix.is_empty ();
2619 }
2620
2621 /* Clean up. */
2622 return err;
2623}
2624
2625/* Checks on the instructions within blocks. Currently checks that each
2626 block starts with a basic block note, and that basic block notes and
2627 control flow jumps are not found in the middle of the block. */
2628
2629static int
2630rtl_verify_bb_insns (void)
2631{
2632 rtx_insn *x;
2633 int err = 0;
2634 basic_block bb;
2635
2636 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2637 {
2638 /* Now check the header of basic
2639 block. It ought to contain optional CODE_LABEL followed
2640 by NOTE_BASIC_BLOCK. */
2641 x = BB_HEAD (bb);
2642 if (LABEL_P (x))
2643 {
2644 if (BB_END (bb) == x)
2645 {
2646 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2647 bb->index);
2648 err = 1;
2649 }
2650
2651 x = NEXT_INSN (x);
2652 }
2653
2654 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2655 {
2656 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2657 bb->index);
2658 err = 1;
2659 }
2660
2661 if (BB_END (bb) == x)
2662 /* Do checks for empty blocks here. */
2663 ;
2664 else
2665 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2666 {
2667 if (NOTE_INSN_BASIC_BLOCK_P (x))
2668 {
2669 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2670 INSN_UID (x), bb->index);
2671 err = 1;
2672 }
2673
2674 if (x == BB_END (bb))
2675 break;
2676
2677 if (control_flow_insn_p (x))
2678 {
2679 error ("in basic block %d:", bb->index);
2680 fatal_insn ("flow control insn inside a basic block", x);
2681 }
2682 }
2683 }
2684
2685 /* Clean up. */
2686 return err;
2687}
2688
2689/* Verify that block pointers for instructions in basic blocks, headers and
2690 footers are set appropriately. */
2691
2692static int
2693rtl_verify_bb_pointers (void)
2694{
2695 int err = 0;
2696 basic_block bb;
2697
2698 /* Check the general integrity of the basic blocks. */
2699 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2700 {
2701 rtx_insn *insn;
2702
2703 if (!(bb->flags & BB_RTL))
2704 {
2705 error ("BB_RTL flag not set for block %d", bb->index);
2706 err = 1;
2707 }
2708
2709 FOR_BB_INSNS (bb, insn)
2710 if (BLOCK_FOR_INSN (insn) != bb)
2711 {
2712 error ("insn %d basic block pointer is %d, should be %d",
2713 INSN_UID (insn),
2714 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2715 bb->index);
2716 err = 1;
2717 }
2718
2719 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2720 if (!BARRIER_P (insn)
2721 && BLOCK_FOR_INSN (insn) != NULL)
2722 {
2723 error ("insn %d in header of bb %d has non-NULL basic block",
2724 INSN_UID (insn), bb->index);
2725 err = 1;
2726 }
2727 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2728 if (!BARRIER_P (insn)
2729 && BLOCK_FOR_INSN (insn) != NULL)
2730 {
2731 error ("insn %d in footer of bb %d has non-NULL basic block",
2732 INSN_UID (insn), bb->index);
2733 err = 1;
2734 }
2735 }
2736
2737 /* Clean up. */
2738 return err;
2739}
2740
2741/* Verify the CFG and RTL consistency common for both underlying RTL and
2742 cfglayout RTL.
2743
2744 Currently it does following checks:
2745
2746 - overlapping of basic blocks
2747 - insns with wrong BLOCK_FOR_INSN pointers
2748 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2749 - tails of basic blocks (ensure that boundary is necessary)
2750 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2751 and NOTE_INSN_BASIC_BLOCK
2752 - verify that no fall_thru edge crosses hot/cold partition boundaries
2753 - verify that there are no pending RTL branch predictions
2754 - verify that hot blocks are not dominated by cold blocks
2755
2756 In future it can be extended check a lot of other stuff as well
2757 (reachability of basic blocks, life information, etc. etc.). */
2758
2759static int
2760rtl_verify_flow_info_1 (void)
2761{
2762 int err = 0;
2763
2764 err |= rtl_verify_bb_pointers ();
2765
2766 err |= rtl_verify_bb_insns ();
2767
2768 err |= rtl_verify_edges ();
2769
2770 return err;
2771}
2772
2773/* Walk the instruction chain and verify that bb head/end pointers
2774 are correct, and that instructions are in exactly one bb and have
2775 correct block pointers. */
2776
2777static int
2778rtl_verify_bb_insn_chain (void)
2779{
2780 basic_block bb;
2781 int err = 0;
2782 rtx_insn *x;
2783 rtx_insn *last_head = get_last_insn ();
2784 basic_block *bb_info;
2785 const int max_uid = get_max_uid ();
2786
2787 bb_info = XCNEWVEC (basic_block, max_uid);
2788
2789 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2790 {
2791 rtx_insn *head = BB_HEAD (bb);
2792 rtx_insn *end = BB_END (bb);
2793
2794 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2795 {
2796 /* Verify the end of the basic block is in the INSN chain. */
2797 if (x == end)
2798 break;
2799
2800 /* And that the code outside of basic blocks has NULL bb field. */
2801 if (!BARRIER_P (x)
2802 && BLOCK_FOR_INSN (x) != NULL)
2803 {
2804 error ("insn %d outside of basic blocks has non-NULL bb field",
2805 INSN_UID (x));
2806 err = 1;
2807 }
2808 }
2809
2810 if (!x)
2811 {
2812 error ("end insn %d for block %d not found in the insn stream",
2813 INSN_UID (end), bb->index);
2814 err = 1;
2815 }
2816
2817 /* Work backwards from the end to the head of the basic block
2818 to verify the head is in the RTL chain. */
2819 for (; x != NULL_RTX; x = PREV_INSN (x))
2820 {
2821 /* While walking over the insn chain, verify insns appear
2822 in only one basic block. */
2823 if (bb_info[INSN_UID (x)] != NULL)
2824 {
2825 error ("insn %d is in multiple basic blocks (%d and %d)",
2826 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2827 err = 1;
2828 }
2829
2830 bb_info[INSN_UID (x)] = bb;
2831
2832 if (x == head)
2833 break;
2834 }
2835 if (!x)
2836 {
2837 error ("head insn %d for block %d not found in the insn stream",
2838 INSN_UID (head), bb->index);
2839 err = 1;
2840 }
2841
2842 last_head = PREV_INSN (x);
2843 }
2844
2845 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2846 {
2847 /* Check that the code before the first basic block has NULL
2848 bb field. */
2849 if (!BARRIER_P (x)
2850 && BLOCK_FOR_INSN (x) != NULL)
2851 {
2852 error ("insn %d outside of basic blocks has non-NULL bb field",
2853 INSN_UID (x));
2854 err = 1;
2855 }
2856 }
2857 free (bb_info);
2858
2859 return err;
2860}
2861
2862/* Verify that fallthru edges point to adjacent blocks in layout order and
2863 that barriers exist after non-fallthru blocks. */
2864
2865static int
2866rtl_verify_fallthru (void)
2867{
2868 basic_block bb;
2869 int err = 0;
2870
2871 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2872 {
2873 edge e;
2874
2875 e = find_fallthru_edge (bb->succs);
2876 if (!e)
2877 {
2878 rtx_insn *insn;
2879
2880 /* Ensure existence of barrier in BB with no fallthru edges. */
2881 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2882 {
2883 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2884 {
2885 error ("missing barrier after block %i", bb->index);
2886 err = 1;
2887 break;
2888 }
2889 if (BARRIER_P (insn))
2890 break;
2891 }
2892 }
2893 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2894 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2895 {
2896 rtx_insn *insn;
2897
2898 if (e->src->next_bb != e->dest)
2899 {
2900 error
2901 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2902 e->src->index, e->dest->index);
2903 err = 1;
2904 }
2905 else
2906 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2907 insn = NEXT_INSN (insn))
2908 if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn))
2909 {
2910 error ("verify_flow_info: Incorrect fallthru %i->%i",
2911 e->src->index, e->dest->index);
2912 fatal_insn ("wrong insn in the fallthru edge", insn);
2913 err = 1;
2914 }
2915 }
2916 }
2917
2918 return err;
2919}
2920
2921/* Verify that blocks are laid out in consecutive order. While walking the
2922 instructions, verify that all expected instructions are inside the basic
2923 blocks, and that all returns are followed by barriers. */
2924
2925static int
2926rtl_verify_bb_layout (void)
2927{
2928 basic_block bb;
2929 int err = 0;
2930 rtx_insn *x, *y;
2931 int num_bb_notes;
2932 rtx_insn * const rtx_first = get_insns ();
2933 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2934
2935 num_bb_notes = 0;
2936 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2937
2938 for (x = rtx_first; x; x = NEXT_INSN (x))
2939 {
2940 if (NOTE_INSN_BASIC_BLOCK_P (x))
2941 {
2942 bb = NOTE_BASIC_BLOCK (x);
2943
2944 num_bb_notes++;
2945 if (bb != last_bb_seen->next_bb)
2946 internal_error ("basic blocks not laid down consecutively");
2947
2948 curr_bb = last_bb_seen = bb;
2949 }
2950
2951 if (!curr_bb)
2952 {
2953 switch (GET_CODE (x))
2954 {
2955 case BARRIER:
2956 case NOTE:
2957 case DEBUG_INSN:
2958 break;
2959
2960 case CODE_LABEL:
2961 /* An ADDR_VEC is placed outside any basic block. */
2962 if (NEXT_INSN (x)
2963 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2964 x = NEXT_INSN (x);
2965
2966 /* But in any case, non-deletable labels can appear anywhere. */
2967 break;
2968
2969 default:
2970 fatal_insn ("insn outside basic block", x);
2971 }
2972 }
2973
2974 if (JUMP_P (x)
2975 && returnjump_p (x) && ! condjump_p (x)
2976 && ! ((y = next_nonnote_nondebug_insn (x))
2977 && BARRIER_P (y)))
2978 fatal_insn ("return not followed by barrier", x);
2979
2980 if (curr_bb && x == BB_END (curr_bb))
2981 curr_bb = NULL;
2982 }
2983
2984 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2985 internal_error
2986 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2987 num_bb_notes, n_basic_blocks_for_fn (cfun));
2988
2989 return err;
2990}
2991
2992/* Verify the CFG and RTL consistency common for both underlying RTL and
2993 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2994
2995 Currently it does following checks:
2996 - all checks of rtl_verify_flow_info_1
2997 - test head/end pointers
2998 - check that blocks are laid out in consecutive order
2999 - check that all insns are in the basic blocks
3000 (except the switch handling code, barriers and notes)
3001 - check that all returns are followed by barriers
3002 - check that all fallthru edge points to the adjacent blocks
3003 - verify that there is a single hot/cold partition boundary after bbro */
3004
3005static int
3006rtl_verify_flow_info (void)
3007{
3008 int err = 0;
3009
3010 err |= rtl_verify_flow_info_1 ();
3011
3012 err |= rtl_verify_bb_insn_chain ();
3013
3014 err |= rtl_verify_fallthru ();
3015
3016 err |= rtl_verify_bb_layout ();
3017
3018 err |= verify_hot_cold_block_grouping ();
3019
3020 return err;
3021}
3022
3023/* Assume that the preceding pass has possibly eliminated jump instructions
3024 or converted the unconditional jumps. Eliminate the edges from CFG.
3025 Return true if any edges are eliminated. */
3026
3027bool
3028purge_dead_edges (basic_block bb)
3029{
3030 edge e;
3031 rtx_insn *insn = BB_END (bb);
3032 rtx note;
3033 bool purged = false;
3034 bool found;
3035 edge_iterator ei;
3036
3037 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
3038 do
3039 insn = PREV_INSN (insn);
3040 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3041
3042 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3043 if (NONJUMP_INSN_P (insn)
3044 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3045 {
3046 rtx eqnote;
3047
3048 if (! may_trap_p (PATTERN (insn))
3049 || ((eqnote = find_reg_equal_equiv_note (insn))
3050 && ! may_trap_p (XEXP (eqnote, 0))))
3051 remove_note (insn, note);
3052 }
3053
3054 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3055 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3056 {
3057 bool remove = false;
3058
3059 /* There are three types of edges we need to handle correctly here: EH
3060 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3061 latter can appear when nonlocal gotos are used. */
3062 if (e->flags & EDGE_ABNORMAL_CALL)
3063 {
3064 if (!CALL_P (insn))
3065 remove = true;
3066 else if (can_nonlocal_goto (insn))
3067 ;
3068 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3069 ;
3070 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3071 ;
3072 else
3073 remove = true;
3074 }
3075 else if (e->flags & EDGE_EH)
3076 remove = !can_throw_internal (insn);
3077
3078 if (remove)
3079 {
3080 remove_edge (e);
3081 df_set_bb_dirty (bb);
3082 purged = true;
3083 }
3084 else
3085 ei_next (&ei);
3086 }
3087
3088 if (JUMP_P (insn))
3089 {
3090 rtx note;
3091 edge b,f;
3092 edge_iterator ei;
3093
3094 /* We do care only about conditional jumps and simplejumps. */
3095 if (!any_condjump_p (insn)
3096 && !returnjump_p (insn)
3097 && !simplejump_p (insn))
3098 return purged;
3099
3100 /* Branch probability/prediction notes are defined only for
3101 condjumps. We've possibly turned condjump into simplejump. */
3102 if (simplejump_p (insn))
3103 {
3104 note = find_reg_note (insn, REG_BR_PROB, NULL);
3105 if (note)
3106 remove_note (insn, note);
3107 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3108 remove_note (insn, note);
3109 }
3110
3111 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3112 {
3113 /* Avoid abnormal flags to leak from computed jumps turned
3114 into simplejumps. */
3115
3116 e->flags &= ~EDGE_ABNORMAL;
3117
3118 /* See if this edge is one we should keep. */
3119 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3120 /* A conditional jump can fall through into the next
3121 block, so we should keep the edge. */
3122 {
3123 ei_next (&ei);
3124 continue;
3125 }
3126 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3127 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3128 /* If the destination block is the target of the jump,
3129 keep the edge. */
3130 {
3131 ei_next (&ei);
3132 continue;
3133 }
3134 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3135 && returnjump_p (insn))
3136 /* If the destination block is the exit block, and this
3137 instruction is a return, then keep the edge. */
3138 {
3139 ei_next (&ei);
3140 continue;
3141 }
3142 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3143 /* Keep the edges that correspond to exceptions thrown by
3144 this instruction and rematerialize the EDGE_ABNORMAL
3145 flag we just cleared above. */
3146 {
3147 e->flags |= EDGE_ABNORMAL;
3148 ei_next (&ei);
3149 continue;
3150 }
3151
3152 /* We do not need this edge. */
3153 df_set_bb_dirty (bb);
3154 purged = true;
3155 remove_edge (e);
3156 }
3157
3158 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3159 return purged;
3160
3161 if (dump_file)
3162 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3163
3164 if (!optimize)
3165 return purged;
3166
3167 /* Redistribute probabilities. */
3168 if (single_succ_p (bb))
3169 {
3170 single_succ_edge (bb)->probability = profile_probability::always ();
3171 }
3172 else
3173 {
3174 note = find_reg_note (insn, REG_BR_PROB, NULL);
3175 if (!note)
3176 return purged;
3177
3178 b = BRANCH_EDGE (bb);
3179 f = FALLTHRU_EDGE (bb);
3180 b->probability = profile_probability::from_reg_br_prob_note
3181 (XINT (note, 0));
3182 f->probability = b->probability.invert ();
3183 }
3184
3185 return purged;
3186 }
3187 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3188 {
3189 /* First, there should not be any EH or ABCALL edges resulting
3190 from non-local gotos and the like. If there were, we shouldn't
3191 have created the sibcall in the first place. Second, there
3192 should of course never have been a fallthru edge. */
3193 gcc_assert (single_succ_p (bb));
3194 gcc_assert (single_succ_edge (bb)->flags
3195 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3196
3197 return 0;
3198 }
3199
3200 /* If we don't see a jump insn, we don't know exactly why the block would
3201 have been broken at this point. Look for a simple, non-fallthru edge,
3202 as these are only created by conditional branches. If we find such an
3203 edge we know that there used to be a jump here and can then safely
3204 remove all non-fallthru edges. */
3205 found = false;
3206 FOR_EACH_EDGE (e, ei, bb->succs)
3207 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3208 {
3209 found = true;
3210 break;
3211 }
3212
3213 if (!found)
3214 return purged;
3215
3216 /* Remove all but the fake and fallthru edges. The fake edge may be
3217 the only successor for this block in the case of noreturn
3218 calls. */
3219 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3220 {
3221 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3222 {
3223 df_set_bb_dirty (bb);
3224 remove_edge (e);
3225 purged = true;
3226 }
3227 else
3228 ei_next (&ei);
3229 }
3230
3231 gcc_assert (single_succ_p (bb));
3232
3233 single_succ_edge (bb)->probability = profile_probability::always ();
3234
3235 if (dump_file)
3236 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3237 bb->index);
3238 return purged;
3239}
3240
3241/* Search all basic blocks for potentially dead edges and purge them. Return
3242 true if some edge has been eliminated. */
3243
3244bool
3245purge_all_dead_edges (void)
3246{
3247 int purged = false;
3248 basic_block bb;
3249
3250 FOR_EACH_BB_FN (bb, cfun)
3251 {
3252 bool purged_here = purge_dead_edges (bb);
3253
3254 purged |= purged_here;
3255 }
3256
3257 return purged;
3258}
3259
3260/* This is used by a few passes that emit some instructions after abnormal
3261 calls, moving the basic block's end, while they in fact do want to emit
3262 them on the fallthru edge. Look for abnormal call edges, find backward
3263 the call in the block and insert the instructions on the edge instead.
3264
3265 Similarly, handle instructions throwing exceptions internally.
3266
3267 Return true when instructions have been found and inserted on edges. */
3268
3269bool
3270fixup_abnormal_edges (void)
3271{
3272 bool inserted = false;
3273 basic_block bb;
3274
3275 FOR_EACH_BB_FN (bb, cfun)
3276 {
3277 edge e;
3278 edge_iterator ei;
3279
3280 /* Look for cases we are interested in - calls or instructions causing
3281 exceptions. */
3282 FOR_EACH_EDGE (e, ei, bb->succs)
3283 if ((e->flags & EDGE_ABNORMAL_CALL)
3284 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3285 == (EDGE_ABNORMAL | EDGE_EH)))
3286 break;
3287
3288 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3289 {
3290 rtx_insn *insn;
3291
3292 /* Get past the new insns generated. Allow notes, as the insns
3293 may be already deleted. */
3294 insn = BB_END (bb);
3295 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3296 && !can_throw_internal (insn)
3297 && insn != BB_HEAD (bb))
3298 insn = PREV_INSN (insn);
3299
3300 if (CALL_P (insn) || can_throw_internal (insn))
3301 {
3302 rtx_insn *stop, *next;
3303
3304 e = find_fallthru_edge (bb->succs);
3305
3306 stop = NEXT_INSN (BB_END (bb));
3307 BB_END (bb) = insn;
3308
3309 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3310 {
3311 next = NEXT_INSN (insn);
3312 if (INSN_P (insn))
3313 {
3314 delete_insn (insn);
3315
3316 /* Sometimes there's still the return value USE.
3317 If it's placed after a trapping call (i.e. that
3318 call is the last insn anyway), we have no fallthru
3319 edge. Simply delete this use and don't try to insert
3320 on the non-existent edge. */
3321 if (GET_CODE (PATTERN (insn)) != USE)
3322 {
3323 /* We're not deleting it, we're moving it. */
3324 insn->set_undeleted ();
3325 SET_PREV_INSN (insn) = NULL_RTX;
3326 SET_NEXT_INSN (insn) = NULL_RTX;
3327
3328 insert_insn_on_edge (insn, e);
3329 inserted = true;
3330 }
3331 }
3332 else if (!BARRIER_P (insn))
3333 set_block_for_insn (insn, NULL);
3334 }
3335 }
3336
3337 /* It may be that we don't find any trapping insn. In this
3338 case we discovered quite late that the insn that had been
3339 marked as can_throw_internal in fact couldn't trap at all.
3340 So we should in fact delete the EH edges out of the block. */
3341 else
3342 purge_dead_edges (bb);
3343 }
3344 }
3345
3346 return inserted;
3347}
3348
3349/* Cut the insns from FIRST to LAST out of the insns stream. */
3350
3351rtx_insn *
3352unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3353{
3354 rtx_insn *prevfirst = PREV_INSN (first);
3355 rtx_insn *nextlast = NEXT_INSN (last);
3356
3357 SET_PREV_INSN (first) = NULL;
3358 SET_NEXT_INSN (last) = NULL;
3359 if (prevfirst)
3360 SET_NEXT_INSN (prevfirst) = nextlast;
3361 if (nextlast)
3362 SET_PREV_INSN (nextlast) = prevfirst;
3363 else
3364 set_last_insn (prevfirst);
3365 if (!prevfirst)
3366 set_first_insn (nextlast);
3367 return first;
3368}
3369
3370/* Skip over inter-block insns occurring after BB which are typically
3371 associated with BB (e.g., barriers). If there are any such insns,
3372 we return the last one. Otherwise, we return the end of BB. */
3373
3374static rtx_insn *
3375skip_insns_after_block (basic_block bb)
3376{
3377 rtx_insn *insn, *last_insn, *next_head, *prev;
3378
3379 next_head = NULL;
3380 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3381 next_head = BB_HEAD (bb->next_bb);
3382
3383 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3384 {
3385 if (insn == next_head)
3386 break;
3387
3388 switch (GET_CODE (insn))
3389 {
3390 case BARRIER:
3391 last_insn = insn;
3392 continue;
3393
3394 case DEBUG_INSN:
3395 continue;
3396
3397 case NOTE:
3398 switch (NOTE_KIND (insn))
3399 {
3400 case NOTE_INSN_BLOCK_END:
3401 gcc_unreachable ();
3402 continue;
3403 default:
3404 continue;
3405 break;
3406 }
3407 break;
3408
3409 case CODE_LABEL:
3410 if (NEXT_INSN (insn)
3411 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3412 {
3413 insn = NEXT_INSN (insn);
3414 last_insn = insn;
3415 continue;
3416 }
3417 break;
3418
3419 default:
3420 break;
3421 }
3422
3423 break;
3424 }
3425
3426 /* It is possible to hit contradictory sequence. For instance:
3427
3428 jump_insn
3429 NOTE_INSN_BLOCK_BEG
3430 barrier
3431
3432 Where barrier belongs to jump_insn, but the note does not. This can be
3433 created by removing the basic block originally following
3434 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3435
3436 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3437 {
3438 prev = PREV_INSN (insn);
3439 if (NOTE_P (insn))
3440 switch (NOTE_KIND (insn))
3441 {
3442 case NOTE_INSN_BLOCK_END:
3443 gcc_unreachable ();
3444 break;
3445 case NOTE_INSN_DELETED:
3446 case NOTE_INSN_DELETED_LABEL:
3447 case NOTE_INSN_DELETED_DEBUG_LABEL:
3448 continue;
3449 default:
3450 reorder_insns (insn, insn, last_insn);
3451 }
3452 }
3453
3454 return last_insn;
3455}
3456
3457/* Locate or create a label for a given basic block. */
3458
3459static rtx_insn *
3460label_for_bb (basic_block bb)
3461{
3462 rtx_insn *label = BB_HEAD (bb);
3463
3464 if (!LABEL_P (label))
3465 {
3466 if (dump_file)
3467 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3468
3469 label = block_label (bb);
3470 }
3471
3472 return label;
3473}
3474
3475/* Locate the effective beginning and end of the insn chain for each
3476 block, as defined by skip_insns_after_block above. */
3477
3478static void
3479record_effective_endpoints (void)
3480{
3481 rtx_insn *next_insn;
3482 basic_block bb;
3483 rtx_insn *insn;
3484
3485 for (insn = get_insns ();
3486 insn
3487 && NOTE_P (insn)
3488 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3489 insn = NEXT_INSN (insn))
3490 continue;
3491 /* No basic blocks at all? */
3492 gcc_assert (insn);
3493
3494 if (PREV_INSN (insn))
3495 cfg_layout_function_header =
3496 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3497 else
3498 cfg_layout_function_header = NULL;
3499
3500 next_insn = get_insns ();
3501 FOR_EACH_BB_FN (bb, cfun)
3502 {
3503 rtx_insn *end;
3504
3505 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3506 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3507 PREV_INSN (BB_HEAD (bb)));
3508 end = skip_insns_after_block (bb);
3509 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3510 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3511 next_insn = NEXT_INSN (BB_END (bb));
3512 }
3513
3514 cfg_layout_function_footer = next_insn;
3515 if (cfg_layout_function_footer)
3516 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3517}
3518
3519namespace {
3520
3521const pass_data pass_data_into_cfg_layout_mode =
3522{
3523 RTL_PASS, /* type */
3524 "into_cfglayout", /* name */
3525 OPTGROUP_NONE, /* optinfo_flags */
3526 TV_CFG, /* tv_id */
3527 0, /* properties_required */
3528 PROP_cfglayout, /* properties_provided */
3529 0, /* properties_destroyed */
3530 0, /* todo_flags_start */
3531 0, /* todo_flags_finish */
3532};
3533
3534class pass_into_cfg_layout_mode : public rtl_opt_pass
3535{
3536public:
3537 pass_into_cfg_layout_mode (gcc::context *ctxt)
3538 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3539 {}
3540
3541 /* opt_pass methods: */
3542 virtual unsigned int execute (function *)
3543 {
3544 cfg_layout_initialize (0);
3545 return 0;
3546 }
3547
3548}; // class pass_into_cfg_layout_mode
3549
3550} // anon namespace
3551
3552rtl_opt_pass *
3553make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3554{
3555 return new pass_into_cfg_layout_mode (ctxt);
3556}
3557
3558namespace {
3559
3560const pass_data pass_data_outof_cfg_layout_mode =
3561{
3562 RTL_PASS, /* type */
3563 "outof_cfglayout", /* name */
3564 OPTGROUP_NONE, /* optinfo_flags */
3565 TV_CFG, /* tv_id */
3566 0, /* properties_required */
3567 0, /* properties_provided */
3568 PROP_cfglayout, /* properties_destroyed */
3569 0, /* todo_flags_start */
3570 0, /* todo_flags_finish */
3571};
3572
3573class pass_outof_cfg_layout_mode : public rtl_opt_pass
3574{
3575public:
3576 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3577 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3578 {}
3579
3580 /* opt_pass methods: */
3581 virtual unsigned int execute (function *);
3582
3583}; // class pass_outof_cfg_layout_mode
3584
3585unsigned int
3586pass_outof_cfg_layout_mode::execute (function *fun)
3587{
3588 basic_block bb;
3589
3590 FOR_EACH_BB_FN (bb, fun)
3591 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3592 bb->aux = bb->next_bb;
3593
3594 cfg_layout_finalize ();
3595
3596 return 0;
3597}
3598
3599} // anon namespace
3600
3601rtl_opt_pass *
3602make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3603{
3604 return new pass_outof_cfg_layout_mode (ctxt);
3605}
3606
3607
3608/* Link the basic blocks in the correct order, compacting the basic
3609 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3610 function also clears the basic block header and footer fields.
3611
3612 This function is usually called after a pass (e.g. tracer) finishes
3613 some transformations while in cfglayout mode. The required sequence
3614 of the basic blocks is in a linked list along the bb->aux field.
3615 This functions re-links the basic block prev_bb and next_bb pointers
3616 accordingly, and it compacts and renumbers the blocks.
3617
3618 FIXME: This currently works only for RTL, but the only RTL-specific
3619 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3620 to GIMPLE a long time ago, but it doesn't relink the basic block
3621 chain. It could do that (to give better initial RTL) if this function
3622 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3623
3624void
3625relink_block_chain (bool stay_in_cfglayout_mode)
3626{
3627 basic_block bb, prev_bb;
3628 int index;
3629
3630 /* Maybe dump the re-ordered sequence. */
3631 if (dump_file)
3632 {
3633 fprintf (dump_file, "Reordered sequence:\n");
3634 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3635 NUM_FIXED_BLOCKS;
3636 bb;
3637 bb = (basic_block) bb->aux, index++)
3638 {
3639 fprintf (dump_file, " %i ", index);
3640 if (get_bb_original (bb))
3641 fprintf (dump_file, "duplicate of %i ",
3642 get_bb_original (bb)->index);
3643 else if (forwarder_block_p (bb)
3644 && !LABEL_P (BB_HEAD (bb)))
3645 fprintf (dump_file, "compensation ");
3646 else
3647 fprintf (dump_file, "bb %i ", bb->index);
3648 }
3649 }
3650
3651 /* Now reorder the blocks. */
3652 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3653 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3654 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3655 {
3656 bb->prev_bb = prev_bb;
3657 prev_bb->next_bb = bb;
3658 }
3659 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3660 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3661
3662 /* Then, clean up the aux fields. */
3663 FOR_ALL_BB_FN (bb, cfun)
3664 {
3665 bb->aux = NULL;
3666 if (!stay_in_cfglayout_mode)
3667 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3668 }
3669
3670 /* Maybe reset the original copy tables, they are not valid anymore
3671 when we renumber the basic blocks in compact_blocks. If we are
3672 are going out of cfglayout mode, don't re-allocate the tables. */
3673 if (original_copy_tables_initialized_p ())
3674 free_original_copy_tables ();
3675 if (stay_in_cfglayout_mode)
3676 initialize_original_copy_tables ();
3677
3678 /* Finally, put basic_block_info in the new order. */
3679 compact_blocks ();
3680}
3681
3682
3683/* Given a reorder chain, rearrange the code to match. */
3684
3685static void
3686fixup_reorder_chain (void)
3687{
3688 basic_block bb;
3689 rtx_insn *insn = NULL;
3690
3691 if (cfg_layout_function_header)
3692 {
3693 set_first_insn (cfg_layout_function_header);
3694 insn = cfg_layout_function_header;
3695 while (NEXT_INSN (insn))
3696 insn = NEXT_INSN (insn);
3697 }
3698
3699 /* First do the bulk reordering -- rechain the blocks without regard to
3700 the needed changes to jumps and labels. */
3701
3702 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3703 bb->aux)
3704 {
3705 if (BB_HEADER (bb))
3706 {
3707 if (insn)
3708 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3709 else
3710 set_first_insn (BB_HEADER (bb));
3711 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3712 insn = BB_HEADER (bb);
3713 while (NEXT_INSN (insn))
3714 insn = NEXT_INSN (insn);
3715 }
3716 if (insn)
3717 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3718 else
3719 set_first_insn (BB_HEAD (bb));
3720 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3721 insn = BB_END (bb);
3722 if (BB_FOOTER (bb))
3723 {
3724 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3725 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3726 while (NEXT_INSN (insn))
3727 insn = NEXT_INSN (insn);
3728 }
3729 }
3730
3731 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3732 if (cfg_layout_function_footer)
3733 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3734
3735 while (NEXT_INSN (insn))
3736 insn = NEXT_INSN (insn);
3737
3738 set_last_insn (insn);
3739 if (flag_checking)
3740 verify_insn_chain ();
3741
3742 /* Now add jumps and labels as needed to match the blocks new
3743 outgoing edges. */
3744
3745 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3746 bb->aux)
3747 {
3748 edge e_fall, e_taken, e;
3749 rtx_insn *bb_end_insn;
3750 rtx ret_label = NULL_RTX;
3751 basic_block nb;
3752 edge_iterator ei;
3753
3754 if (EDGE_COUNT (bb->succs) == 0)
3755 continue;
3756
3757 /* Find the old fallthru edge, and another non-EH edge for
3758 a taken jump. */
3759 e_taken = e_fall = NULL;
3760
3761 FOR_EACH_EDGE (e, ei, bb->succs)
3762 if (e->flags & EDGE_FALLTHRU)
3763 e_fall = e;
3764 else if (! (e->flags & EDGE_EH))
3765 e_taken = e;
3766
3767 bb_end_insn = BB_END (bb);
3768 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3769 {
3770 ret_label = JUMP_LABEL (bb_end_jump);
3771 if (any_condjump_p (bb_end_jump))
3772 {
3773 /* This might happen if the conditional jump has side
3774 effects and could therefore not be optimized away.
3775 Make the basic block to end with a barrier in order
3776 to prevent rtl_verify_flow_info from complaining. */
3777 if (!e_fall)
3778 {
3779 gcc_assert (!onlyjump_p (bb_end_jump)
3780 || returnjump_p (bb_end_jump)
3781 || (e_taken->flags & EDGE_CROSSING));
3782 emit_barrier_after (bb_end_jump);
3783 continue;
3784 }
3785
3786 /* If the old fallthru is still next, nothing to do. */
3787 if (bb->aux == e_fall->dest
3788 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3789 continue;
3790
3791 /* The degenerated case of conditional jump jumping to the next
3792 instruction can happen for jumps with side effects. We need
3793 to construct a forwarder block and this will be done just
3794 fine by force_nonfallthru below. */
3795 if (!e_taken)
3796 ;
3797
3798 /* There is another special case: if *neither* block is next,
3799 such as happens at the very end of a function, then we'll
3800 need to add a new unconditional jump. Choose the taken
3801 edge based on known or assumed probability. */
3802 else if (bb->aux != e_taken->dest)
3803 {
3804 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3805
3806 if (note
3807 && profile_probability::from_reg_br_prob_note
3808 (XINT (note, 0)) < profile_probability::even ()
3809 && invert_jump (bb_end_jump,
3810 (e_fall->dest
3811 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3812 ? NULL_RTX
3813 : label_for_bb (e_fall->dest)), 0))
3814 {
3815 e_fall->flags &= ~EDGE_FALLTHRU;
3816 gcc_checking_assert (could_fall_through
3817 (e_taken->src, e_taken->dest));
3818 e_taken->flags |= EDGE_FALLTHRU;
3819 update_br_prob_note (bb);
3820 e = e_fall, e_fall = e_taken, e_taken = e;
3821 }
3822 }
3823
3824 /* If the "jumping" edge is a crossing edge, and the fall
3825 through edge is non-crossing, leave things as they are. */
3826 else if ((e_taken->flags & EDGE_CROSSING)
3827 && !(e_fall->flags & EDGE_CROSSING))
3828 continue;
3829
3830 /* Otherwise we can try to invert the jump. This will
3831 basically never fail, however, keep up the pretense. */
3832 else if (invert_jump (bb_end_jump,
3833 (e_fall->dest
3834 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3835 ? NULL_RTX
3836 : label_for_bb (e_fall->dest)), 0))
3837 {
3838 e_fall->flags &= ~EDGE_FALLTHRU;
3839 gcc_checking_assert (could_fall_through
3840 (e_taken->src, e_taken->dest));
3841 e_taken->flags |= EDGE_FALLTHRU;
3842 update_br_prob_note (bb);
3843 if (LABEL_NUSES (ret_label) == 0
3844 && single_pred_p (e_taken->dest))
3845 delete_insn (as_a<rtx_insn *> (ret_label));
3846 continue;
3847 }
3848 }
3849 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3850 {
3851 /* If the old fallthru is still next or if
3852 asm goto doesn't have a fallthru (e.g. when followed by
3853 __builtin_unreachable ()), nothing to do. */
3854 if (! e_fall
3855 || bb->aux == e_fall->dest
3856 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3857 continue;
3858
3859 /* Otherwise we'll have to use the fallthru fixup below. */
3860 }
3861 else
3862 {
3863 /* Otherwise we have some return, switch or computed
3864 jump. In the 99% case, there should not have been a
3865 fallthru edge. */
3866 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3867 continue;
3868 }
3869 }
3870 else
3871 {
3872 /* No fallthru implies a noreturn function with EH edges, or
3873 something similarly bizarre. In any case, we don't need to
3874 do anything. */
3875 if (! e_fall)
3876 continue;
3877
3878 /* If the fallthru block is still next, nothing to do. */
3879 if (bb->aux == e_fall->dest)
3880 continue;
3881
3882 /* A fallthru to exit block. */
3883 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3884 continue;
3885 }
3886
3887 /* We got here if we need to add a new jump insn.
3888 Note force_nonfallthru can delete E_FALL and thus we have to
3889 save E_FALL->src prior to the call to force_nonfallthru. */
3890 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3891 if (nb)
3892 {
3893 nb->aux = bb->aux;
3894 bb->aux = nb;
3895 /* Don't process this new block. */
3896 bb = nb;
3897 }
3898 }
3899
3900 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3901
3902 /* Annoying special case - jump around dead jumptables left in the code. */
3903 FOR_EACH_BB_FN (bb, cfun)
3904 {
3905 edge e = find_fallthru_edge (bb->succs);
3906
3907 if (e && !can_fallthru (e->src, e->dest))
3908 force_nonfallthru (e);
3909 }
3910
3911 /* Ensure goto_locus from edges has some instructions with that locus
3912 in RTL. */
3913 if (!optimize)
3914 FOR_EACH_BB_FN (bb, cfun)
3915 {
3916 edge e;
3917 edge_iterator ei;
3918
3919 FOR_EACH_EDGE (e, ei, bb->succs)
3920 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3921 && !(e->flags & EDGE_ABNORMAL))
3922 {
3923 edge e2;
3924 edge_iterator ei2;
3925 basic_block dest, nb;
3926 rtx_insn *end;
3927
3928 insn = BB_END (e->src);
3929 end = PREV_INSN (BB_HEAD (e->src));
3930 while (insn != end
3931 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3932 insn = PREV_INSN (insn);
3933 if (insn != end
3934 && INSN_LOCATION (insn) == e->goto_locus)
3935 continue;
3936 if (simplejump_p (BB_END (e->src))
3937 && !INSN_HAS_LOCATION (BB_END (e->src)))
3938 {
3939 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3940 continue;
3941 }
3942 dest = e->dest;
3943 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3944 {
3945 /* Non-fallthru edges to the exit block cannot be split. */
3946 if (!(e->flags & EDGE_FALLTHRU))
3947 continue;
3948 }
3949 else
3950 {
3951 insn = BB_HEAD (dest);
3952 end = NEXT_INSN (BB_END (dest));
3953 while (insn != end && !NONDEBUG_INSN_P (insn))
3954 insn = NEXT_INSN (insn);
3955 if (insn != end && INSN_HAS_LOCATION (insn)
3956 && INSN_LOCATION (insn) == e->goto_locus)
3957 continue;
3958 }
3959 nb = split_edge (e);
3960 if (!INSN_P (BB_END (nb)))
3961 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3962 nb);
3963 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3964
3965 /* If there are other incoming edges to the destination block
3966 with the same goto locus, redirect them to the new block as
3967 well, this can prevent other such blocks from being created
3968 in subsequent iterations of the loop. */
3969 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3970 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3971 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3972 && e->goto_locus == e2->goto_locus)
3973 redirect_edge_and_branch (e2, nb);
3974 else
3975 ei_next (&ei2);
3976 }
3977 }
3978}
3979
3980/* Perform sanity checks on the insn chain.
3981 1. Check that next/prev pointers are consistent in both the forward and
3982 reverse direction.
3983 2. Count insns in chain, going both directions, and check if equal.
3984 3. Check that get_last_insn () returns the actual end of chain. */
3985
3986DEBUG_FUNCTION void
3987verify_insn_chain (void)
3988{
3989 rtx_insn *x, *prevx, *nextx;
3990 int insn_cnt1, insn_cnt2;
3991
3992 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3993 x != 0;
3994 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3995 gcc_assert (PREV_INSN (x) == prevx);
3996
3997 gcc_assert (prevx == get_last_insn ());
3998
3999 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
4000 x != 0;
4001 nextx = x, insn_cnt2++, x = PREV_INSN (x))
4002 gcc_assert (NEXT_INSN (x) == nextx);
4003
4004 gcc_assert (insn_cnt1 == insn_cnt2);
4005}
4006
4007/* If we have assembler epilogues, the block falling through to exit must
4008 be the last one in the reordered chain when we reach final. Ensure
4009 that this condition is met. */
4010static void
4011fixup_fallthru_exit_predecessor (void)
4012{
4013 edge e;
4014 basic_block bb = NULL;
4015
4016 /* This transformation is not valid before reload, because we might
4017 separate a call from the instruction that copies the return
4018 value. */
4019 gcc_assert (reload_completed);
4020
4021 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4022 if (e)
4023 bb = e->src;
4024
4025 if (bb && bb->aux)
4026 {
4027 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4028
4029 /* If the very first block is the one with the fall-through exit
4030 edge, we have to split that block. */
4031 if (c == bb)
4032 {
4033 bb = split_block_after_labels (bb)->dest;
4034 bb->aux = c->aux;
4035 c->aux = bb;
4036 BB_FOOTER (bb) = BB_FOOTER (c);
4037 BB_FOOTER (c) = NULL;
4038 }
4039
4040 while (c->aux != bb)
4041 c = (basic_block) c->aux;
4042
4043 c->aux = bb->aux;
4044 while (c->aux)
4045 c = (basic_block) c->aux;
4046
4047 c->aux = bb;
4048 bb->aux = NULL;
4049 }
4050}
4051
4052/* In case there are more than one fallthru predecessors of exit, force that
4053 there is only one. */
4054
4055static void
4056force_one_exit_fallthru (void)
4057{
4058 edge e, predecessor = NULL;
4059 bool more = false;
4060 edge_iterator ei;
4061 basic_block forwarder, bb;
4062
4063 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4064 if (e->flags & EDGE_FALLTHRU)
4065 {
4066 if (predecessor == NULL)
4067 predecessor = e;
4068 else
4069 {
4070 more = true;
4071 break;
4072 }
4073 }
4074
4075 if (!more)
4076 return;
4077
4078 /* Exit has several fallthru predecessors. Create a forwarder block for
4079 them. */
4080 forwarder = split_edge (predecessor);
4081 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4082 (e = ei_safe_edge (ei)); )
4083 {
4084 if (e->src == forwarder
4085 || !(e->flags & EDGE_FALLTHRU))
4086 ei_next (&ei);
4087 else
4088 redirect_edge_and_branch_force (e, forwarder);
4089 }
4090
4091 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4092 exit block. */
4093 FOR_EACH_BB_FN (bb, cfun)
4094 {
4095 if (bb->aux == NULL && bb != forwarder)
4096 {
4097 bb->aux = forwarder;
4098 break;
4099 }
4100 }
4101}
4102
4103/* Return true in case it is possible to duplicate the basic block BB. */
4104
4105static bool
4106cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4107{
4108 /* Do not attempt to duplicate tablejumps, as we need to unshare
4109 the dispatch table. This is difficult to do, as the instructions
4110 computing jump destination may be hoisted outside the basic block. */
4111 if (tablejump_p (BB_END (bb), NULL, NULL))
4112 return false;
4113
4114 /* Do not duplicate blocks containing insns that can't be copied. */
4115 if (targetm.cannot_copy_insn_p)
4116 {
4117 rtx_insn *insn = BB_HEAD (bb);
4118 while (1)
4119 {
4120 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4121 return false;
4122 if (insn == BB_END (bb))
4123 break;
4124 insn = NEXT_INSN (insn);
4125 }
4126 }
4127
4128 return true;
4129}
4130
4131rtx_insn *
4132duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4133{
4134 rtx_insn *insn, *next, *copy;
4135 rtx_note *last;
4136
4137 /* Avoid updating of boundaries of previous basic block. The
4138 note will get removed from insn stream in fixup. */
4139 last = emit_note (NOTE_INSN_DELETED);
4140
4141 /* Create copy at the end of INSN chain. The chain will
4142 be reordered later. */
4143 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4144 {
4145 switch (GET_CODE (insn))
4146 {
4147 case DEBUG_INSN:
4148 /* Don't duplicate label debug insns. */
4149 if (DEBUG_BIND_INSN_P (insn)
4150 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4151 break;
4152 /* FALLTHRU */
4153 case INSN:
4154 case CALL_INSN:
4155 case JUMP_INSN:
4156 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4157 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4158 && ANY_RETURN_P (JUMP_LABEL (insn)))
4159 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4160 maybe_copy_prologue_epilogue_insn (insn, copy);
4161 break;
4162
4163 case JUMP_TABLE_DATA:
4164 /* Avoid copying of dispatch tables. We never duplicate
4165 tablejumps, so this can hit only in case the table got
4166 moved far from original jump.
4167 Avoid copying following barrier as well if any
4168 (and debug insns in between). */
4169 for (next = NEXT_INSN (insn);
4170 next != NEXT_INSN (to);
4171 next = NEXT_INSN (next))
4172 if (!DEBUG_INSN_P (next))
4173 break;
4174 if (next != NEXT_INSN (to) && BARRIER_P (next))
4175 insn = next;
4176 break;
4177
4178 case CODE_LABEL:
4179 break;
4180
4181 case BARRIER:
4182 emit_barrier ();
4183 break;
4184
4185 case NOTE:
4186 switch (NOTE_KIND (insn))
4187 {
4188 /* In case prologue is empty and function contain label
4189 in first BB, we may want to copy the block. */
4190 case NOTE_INSN_PROLOGUE_END:
4191
4192 case NOTE_INSN_DELETED:
4193 case NOTE_INSN_DELETED_LABEL:
4194 case NOTE_INSN_DELETED_DEBUG_LABEL:
4195 /* No problem to strip these. */
4196 case NOTE_INSN_FUNCTION_BEG:
4197 /* There is always just single entry to function. */
4198 case NOTE_INSN_BASIC_BLOCK:
4199 /* We should only switch text sections once. */
4200 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4201 break;
4202
4203 case NOTE_INSN_EPILOGUE_BEG:
4204 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4205 emit_note_copy (as_a <rtx_note *> (insn));
4206 break;
4207
4208 default:
4209 /* All other notes should have already been eliminated. */
4210 gcc_unreachable ();
4211 }
4212 break;
4213 default:
4214 gcc_unreachable ();
4215 }
4216 }
4217 insn = NEXT_INSN (last);
4218 delete_insn (last);
4219 return insn;
4220}
4221
4222/* Create a duplicate of the basic block BB. */
4223
4224static basic_block
4225cfg_layout_duplicate_bb (basic_block bb)
4226{
4227 rtx_insn *insn;
4228 basic_block new_bb;
4229
4230 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4231 new_bb = create_basic_block (insn,
4232 insn ? get_last_insn () : NULL,
4233 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4234
4235 BB_COPY_PARTITION (new_bb, bb);
4236 if (BB_HEADER (bb))
4237 {
4238 insn = BB_HEADER (bb);
4239 while (NEXT_INSN (insn))
4240 insn = NEXT_INSN (insn);
4241 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4242 if (insn)
4243 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4244 }
4245
4246 if (BB_FOOTER (bb))
4247 {
4248 insn = BB_FOOTER (bb);
4249 while (NEXT_INSN (insn))
4250 insn = NEXT_INSN (insn);
4251 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4252 if (insn)
4253 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4254 }
4255
4256 return new_bb;
4257}
4258
4259
4260/* Main entry point to this module - initialize the datastructures for
4261 CFG layout changes. It keeps LOOPS up-to-date if not null.
4262
4263 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4264
4265void
4266cfg_layout_initialize (int flags)
4267{
4268 rtx_insn_list *x;
4269 basic_block bb;
4270
4271 /* Once bb partitioning is complete, cfg layout mode should not be
4272 re-entered. Entering cfg layout mode may require fixups. As an
4273 example, if edge forwarding performed when optimizing the cfg
4274 layout required moving a block from the hot to the cold
4275 section. This would create an illegal partitioning unless some
4276 manual fixup was performed. */
4277 gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4278
4279 initialize_original_copy_tables ();
4280
4281 cfg_layout_rtl_register_cfg_hooks ();
4282
4283 record_effective_endpoints ();
4284
4285 /* Make sure that the targets of non local gotos are marked. */
4286 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4287 {
4288 bb = BLOCK_FOR_INSN (x->insn ());
4289 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4290 }
4291
4292 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4293}
4294
4295/* Splits superblocks. */
4296void
4297break_superblocks (void)
4298{
4299 bool need = false;
4300 basic_block bb;
4301
4302 auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4303 bitmap_clear (superblocks);
4304
4305 FOR_EACH_BB_FN (bb, cfun)
4306 if (bb->flags & BB_SUPERBLOCK)
4307 {
4308 bb->flags &= ~BB_SUPERBLOCK;
4309 bitmap_set_bit (superblocks, bb->index);
4310 need = true;
4311 }
4312
4313 if (need)
4314 {
4315 rebuild_jump_labels (get_insns ());
4316 find_many_sub_basic_blocks (superblocks);
4317 }
4318}
4319
4320/* Finalize the changes: reorder insn list according to the sequence specified
4321 by aux pointers, enter compensation code, rebuild scope forest. */
4322
4323void
4324cfg_layout_finalize (void)
4325{
4326 checking_verify_flow_info ();
4327 free_dominance_info (CDI_DOMINATORS);
4328 force_one_exit_fallthru ();
4329 rtl_register_cfg_hooks ();
4330 if (reload_completed && !targetm.have_epilogue ())
4331 fixup_fallthru_exit_predecessor ();
4332 fixup_reorder_chain ();
4333
4334 rebuild_jump_labels (get_insns ());
4335 delete_dead_jumptables ();
4336
4337 if (flag_checking)
4338 verify_insn_chain ();
4339 checking_verify_flow_info ();
4340}
4341
4342
4343/* Same as split_block but update cfg_layout structures. */
4344
4345static basic_block
4346cfg_layout_split_block (basic_block bb, void *insnp)
4347{
4348 rtx insn = (rtx) insnp;
4349 basic_block new_bb = rtl_split_block (bb, insn);
4350
4351 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4352 BB_FOOTER (bb) = NULL;
4353
4354 return new_bb;
4355}
4356
4357/* Redirect Edge to DEST. */
4358static edge
4359cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4360{
4361 basic_block src = e->src;
4362 edge ret;
4363
4364 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4365 return NULL;
4366
4367 if (e->dest == dest)
4368 return e;
4369
4370 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4371 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4372 {
4373 df_set_bb_dirty (src);
4374 return ret;
4375 }
4376
4377 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4378 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4379 {
4380 if (dump_file)
4381 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4382 e->src->index, dest->index);
4383
4384 df_set_bb_dirty (e->src);
4385 redirect_edge_succ (e, dest);
4386 return e;
4387 }
4388
4389 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4390 in the case the basic block appears to be in sequence. Avoid this
4391 transformation. */
4392
4393 if (e->flags & EDGE_FALLTHRU)
4394 {
4395 /* Redirect any branch edges unified with the fallthru one. */
4396 if (JUMP_P (BB_END (src))
4397 && label_is_jump_target_p (BB_HEAD (e->dest),
4398 BB_END (src)))
4399 {
4400 edge redirected;
4401
4402 if (dump_file)
4403 fprintf (dump_file, "Fallthru edge unified with branch "
4404 "%i->%i redirected to %i\n",
4405 e->src->index, e->dest->index, dest->index);
4406 e->flags &= ~EDGE_FALLTHRU;
4407 redirected = redirect_branch_edge (e, dest);
4408 gcc_assert (redirected);
4409 redirected->flags |= EDGE_FALLTHRU;
4410 df_set_bb_dirty (redirected->src);
4411 return redirected;
4412 }
4413 /* In case we are redirecting fallthru edge to the branch edge
4414 of conditional jump, remove it. */
4415 if (EDGE_COUNT (src->succs) == 2)
4416 {
4417 /* Find the edge that is different from E. */
4418 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4419
4420 if (s->dest == dest
4421 && any_condjump_p (BB_END (src))
4422 && onlyjump_p (BB_END (src)))
4423 delete_insn (BB_END (src));
4424 }
4425 if (dump_file)
4426 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4427 e->src->index, e->dest->index, dest->index);
4428 ret = redirect_edge_succ_nodup (e, dest);
4429 }
4430 else
4431 ret = redirect_branch_edge (e, dest);
4432
4433 /* We don't want simplejumps in the insn stream during cfglayout. */
4434 gcc_assert (!simplejump_p (BB_END (src)));
4435
4436 df_set_bb_dirty (src);
4437 return ret;
4438}
4439
4440/* Simple wrapper as we always can redirect fallthru edges. */
4441static basic_block
4442cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4443{
4444 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4445
4446 gcc_assert (redirected);
4447 return NULL;
4448}
4449
4450/* Same as delete_basic_block but update cfg_layout structures. */
4451
4452static void
4453cfg_layout_delete_block (basic_block bb)
4454{
4455 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4456 rtx_insn **to;
4457
4458 if (BB_HEADER (bb))
4459 {
4460 next = BB_HEAD (bb);
4461 if (prev)
4462 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4463 else
4464 set_first_insn (BB_HEADER (bb));
4465 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4466 insn = BB_HEADER (bb);
4467 while (NEXT_INSN (insn))
4468 insn = NEXT_INSN (insn);
4469 SET_NEXT_INSN (insn) = next;
4470 SET_PREV_INSN (next) = insn;
4471 }
4472 next = NEXT_INSN (BB_END (bb));
4473 if (BB_FOOTER (bb))
4474 {
4475 insn = BB_FOOTER (bb);
4476 while (insn)
4477 {
4478 if (BARRIER_P (insn))
4479 {
4480 if (PREV_INSN (insn))
4481 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4482 else
4483 BB_FOOTER (bb) = NEXT_INSN (insn);
4484 if (NEXT_INSN (insn))
4485 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4486 }
4487 if (LABEL_P (insn))
4488 break;
4489 insn = NEXT_INSN (insn);
4490 }
4491 if (BB_FOOTER (bb))
4492 {
4493 insn = BB_END (bb);
4494 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4495 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4496 while (NEXT_INSN (insn))
4497 insn = NEXT_INSN (insn);
4498 SET_NEXT_INSN (insn) = next;
4499 if (next)
4500 SET_PREV_INSN (next) = insn;
4501 else
4502 set_last_insn (insn);
4503 }
4504 }
4505 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4506 to = &BB_HEADER (bb->next_bb);
4507 else
4508 to = &cfg_layout_function_footer;
4509
4510 rtl_delete_block (bb);
4511
4512 if (prev)
4513 prev = NEXT_INSN (prev);
4514 else
4515 prev = get_insns ();
4516 if (next)
4517 next = PREV_INSN (next);
4518 else
4519 next = get_last_insn ();
4520
4521 if (next && NEXT_INSN (next) != prev)
4522 {
4523 remaints = unlink_insn_chain (prev, next);
4524 insn = remaints;
4525 while (NEXT_INSN (insn))
4526 insn = NEXT_INSN (insn);
4527 SET_NEXT_INSN (insn) = *to;
4528 if (*to)
4529 SET_PREV_INSN (*to) = insn;
4530 *to = remaints;
4531 }
4532}
4533
4534/* Return true when blocks A and B can be safely merged. */
4535
4536static bool
4537cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4538{
4539 /* If we are partitioning hot/cold basic blocks, we don't want to
4540 mess up unconditional or indirect jumps that cross between hot
4541 and cold sections.
4542
4543 Basic block partitioning may result in some jumps that appear to
4544 be optimizable (or blocks that appear to be mergeable), but which really
4545 must be left untouched (they are required to make it safely across
4546 partition boundaries). See the comments at the top of
4547 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4548
4549 if (BB_PARTITION (a) != BB_PARTITION (b))
4550 return false;
4551
4552 /* Protect the loop latches. */
4553 if (current_loops && b->loop_father->latch == b)
4554 return false;
4555
4556 /* If we would end up moving B's instructions, make sure it doesn't fall
4557 through into the exit block, since we cannot recover from a fallthrough
4558 edge into the exit block occurring in the middle of a function. */
4559 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4560 {
4561 edge e = find_fallthru_edge (b->succs);
4562 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4563 return false;
4564 }
4565
4566 /* There must be exactly one edge in between the blocks. */
4567 return (single_succ_p (a)
4568 && single_succ (a) == b
4569 && single_pred_p (b) == 1
4570 && a != b
4571 /* Must be simple edge. */
4572 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4573 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4574 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4575 /* If the jump insn has side effects, we can't kill the edge.
4576 When not optimizing, try_redirect_by_replacing_jump will
4577 not allow us to redirect an edge by replacing a table jump. */
4578 && (!JUMP_P (BB_END (a))
4579 || ((!optimize || reload_completed)
4580 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4581}
4582
4583/* Merge block A and B. The blocks must be mergeable. */
4584
4585static void
4586cfg_layout_merge_blocks (basic_block a, basic_block b)
4587{
4588 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4589 rtx_insn *insn;
4590
4591 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4592
4593 if (dump_file)
4594 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4595 a->index);
4596
4597 /* If there was a CODE_LABEL beginning B, delete it. */
4598 if (LABEL_P (BB_HEAD (b)))
4599 {
4600 delete_insn (BB_HEAD (b));
4601 }
4602
4603 /* We should have fallthru edge in a, or we can do dummy redirection to get
4604 it cleaned up. */
4605 if (JUMP_P (BB_END (a)))
4606 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4607 gcc_assert (!JUMP_P (BB_END (a)));
4608
4609 /* When not optimizing and the edge is the only place in RTL which holds
4610 some unique locus, emit a nop with that locus in between. */
4611 if (!optimize)
4612 emit_nop_for_unique_locus_between (a, b);
4613
4614 /* Move things from b->footer after a->footer. */
4615 if (BB_FOOTER (b))
4616 {
4617 if (!BB_FOOTER (a))
4618 BB_FOOTER (a) = BB_FOOTER (b);
4619 else
4620 {
4621 rtx_insn *last = BB_FOOTER (a);
4622
4623 while (NEXT_INSN (last))
4624 last = NEXT_INSN (last);
4625 SET_NEXT_INSN (last) = BB_FOOTER (b);
4626 SET_PREV_INSN (BB_FOOTER (b)) = last;
4627 }
4628 BB_FOOTER (b) = NULL;
4629 }
4630
4631 /* Move things from b->header before a->footer.
4632 Note that this may include dead tablejump data, but we don't clean
4633 those up until we go out of cfglayout mode. */
4634 if (BB_HEADER (b))
4635 {
4636 if (! BB_FOOTER (a))
4637 BB_FOOTER (a) = BB_HEADER (b);
4638 else
4639 {
4640 rtx_insn *last = BB_HEADER (b);
4641
4642 while (NEXT_INSN (last))
4643 last = NEXT_INSN (last);
4644 SET_NEXT_INSN (last) = BB_FOOTER (a);
4645 SET_PREV_INSN (BB_FOOTER (a)) = last;
4646 BB_FOOTER (a) = BB_HEADER (b);
4647 }
4648 BB_HEADER (b) = NULL;
4649 }
4650
4651 /* In the case basic blocks are not adjacent, move them around. */
4652 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4653 {
4654 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4655
4656 emit_insn_after_noloc (insn, BB_END (a), a);
4657 }
4658 /* Otherwise just re-associate the instructions. */
4659 else
4660 {
4661 insn = BB_HEAD (b);
4662 BB_END (a) = BB_END (b);
4663 }
4664
4665 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4666 We need to explicitly call. */
4667 update_bb_for_insn_chain (insn, BB_END (b), a);
4668
4669 /* Skip possible DELETED_LABEL insn. */
4670 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4671 insn = NEXT_INSN (insn);
4672 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4673 BB_HEAD (b) = BB_END (b) = NULL;
4674 delete_insn (insn);
4675
4676 df_bb_delete (b->index);
4677
4678 /* If B was a forwarder block, propagate the locus on the edge. */
4679 if (forwarder_p
4680 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4681 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4682
4683 if (dump_file)
4684 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4685}
4686
4687/* Split edge E. */
4688
4689static basic_block
4690cfg_layout_split_edge (edge e)
4691{
4692 basic_block new_bb =
4693 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4694 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4695 NULL_RTX, e->src);
4696
4697 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4698 BB_COPY_PARTITION (new_bb, e->src);
4699 else
4700 BB_COPY_PARTITION (new_bb, e->dest);
4701 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4702 redirect_edge_and_branch_force (e, new_bb);
4703
4704 return new_bb;
4705}
4706
4707/* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4708
4709static void
4710rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4711{
4712}
4713
4714/* Return true if BB contains only labels or non-executable
4715 instructions. */
4716
4717static bool
4718rtl_block_empty_p (basic_block bb)
4719{
4720 rtx_insn *insn;
4721
4722 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4723 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4724 return true;
4725
4726 FOR_BB_INSNS (bb, insn)
4727 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4728 return false;
4729
4730 return true;
4731}
4732
4733/* Split a basic block if it ends with a conditional branch and if
4734 the other part of the block is not empty. */
4735
4736static basic_block
4737rtl_split_block_before_cond_jump (basic_block bb)
4738{
4739 rtx_insn *insn;
4740 rtx_insn *split_point = NULL;
4741 rtx_insn *last =