Line data Source code
1 : /* Control flow graph manipulation code for GNU compiler.
2 : Copyright (C) 1987-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : /* This file contains low level functions to manipulate the CFG and 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, prepend_insn_to_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 : #include "rtl-iter.h"
65 : #include "profile.h"
66 : #include "sreal.h"
67 :
68 : /* Disable warnings about missing quoting in GCC diagnostics. */
69 : #if __GNUC__ >= 10
70 : # pragma GCC diagnostic push
71 : # pragma GCC diagnostic ignored "-Wformat-diag"
72 : #endif
73 :
74 : /* Holds the interesting leading and trailing notes for the function.
75 : Only applicable if the CFG is in cfglayout mode. */
76 : static GTY(()) rtx_insn *cfg_layout_function_footer;
77 : static GTY(()) rtx_insn *cfg_layout_function_header;
78 :
79 : static rtx_insn *skip_insns_after_block (basic_block);
80 : static void record_effective_endpoints (void);
81 : static void fixup_reorder_chain (void);
82 :
83 : void verify_insn_chain (void);
84 : static void fixup_fallthru_exit_predecessor (void);
85 : static bool can_delete_note_p (const rtx_note *);
86 : static bool can_delete_label_p (const rtx_code_label *);
87 : static basic_block rtl_split_edge (edge);
88 : static bool rtl_move_block_after (basic_block, basic_block);
89 : static bool rtl_verify_flow_info (void);
90 : static basic_block cfg_layout_split_block (basic_block, void *);
91 : static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
92 : static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
93 : static void cfg_layout_delete_block (basic_block);
94 : static void rtl_delete_block (basic_block);
95 : static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
96 : static edge rtl_redirect_edge_and_branch (edge, basic_block);
97 : static basic_block rtl_split_block (basic_block, void *);
98 : static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t);
99 : static bool rtl_verify_flow_info_1 (void);
100 : static void rtl_make_forwarder_block (edge);
101 : static bool rtl_bb_info_initialized_p (basic_block bb);
102 :
103 : /* Return true if NOTE is not one of the ones that must be kept paired,
104 : so that we may simply delete it. */
105 :
106 : static bool
107 10517075 : can_delete_note_p (const rtx_note *note)
108 : {
109 0 : switch (NOTE_KIND (note))
110 : {
111 : case NOTE_INSN_DELETED:
112 : case NOTE_INSN_BASIC_BLOCK:
113 : case NOTE_INSN_EPILOGUE_BEG:
114 : return true;
115 :
116 0 : default:
117 0 : return false;
118 : }
119 : }
120 :
121 : /* True if a given label can be deleted. */
122 :
123 : static bool
124 7631206 : can_delete_label_p (const rtx_code_label *label)
125 : {
126 7631206 : return (!LABEL_PRESERVE_P (label)
127 : /* User declared labels must be preserved. */
128 7622500 : && LABEL_NAME (label) == 0
129 7631206 : && !vec_safe_contains<rtx_insn *> (forced_labels,
130 7576527 : const_cast<rtx_code_label *> (label)));
131 : }
132 :
133 : /* Delete INSN by patching it out. */
134 :
135 : void
136 127808901 : delete_insn (rtx_insn *insn)
137 : {
138 127808901 : rtx note;
139 127808901 : bool really_delete = true;
140 :
141 127808901 : if (LABEL_P (insn))
142 : {
143 : /* Some labels can't be directly removed from the INSN chain, as they
144 : might be references via variables, constant pool etc.
145 : Convert them to the special NOTE_INSN_DELETED_LABEL note. */
146 7631206 : if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
147 : {
148 54679 : const char *name = LABEL_NAME (insn);
149 54679 : basic_block bb = BLOCK_FOR_INSN (insn);
150 54679 : rtx_insn *bb_note = NEXT_INSN (insn);
151 :
152 54679 : really_delete = false;
153 54679 : PUT_CODE (insn, NOTE);
154 54679 : NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
155 54679 : NOTE_DELETED_LABEL_NAME (insn) = name;
156 :
157 : /* If the note following the label starts a basic block, and the
158 : label is a member of the same basic block, interchange the two. */
159 54679 : if (bb_note != NULL_RTX
160 54591 : && NOTE_INSN_BASIC_BLOCK_P (bb_note)
161 13795 : && bb != NULL
162 68474 : && bb == BLOCK_FOR_INSN (bb_note))
163 : {
164 11550 : reorder_insns_nobb (insn, insn, bb_note);
165 11550 : BB_HEAD (bb) = bb_note;
166 11550 : if (BB_END (bb) == bb_note)
167 1588 : BB_END (bb) = insn;
168 : }
169 : }
170 :
171 7631206 : remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
172 : }
173 :
174 7631206 : if (really_delete)
175 : {
176 : /* If this insn has already been deleted, something is very wrong. */
177 127754222 : gcc_assert (!insn->deleted ());
178 127754222 : if (INSN_P (insn))
179 93838796 : df_insn_delete (insn);
180 127754222 : remove_insn (insn);
181 127754222 : insn->set_deleted ();
182 : }
183 :
184 : /* If deleting a jump, decrement the use count of the label. Deleting
185 : the label itself should happen in the normal course of block merging. */
186 127808901 : if (JUMP_P (insn))
187 : {
188 6691414 : if (JUMP_LABEL (insn)
189 6691202 : && LABEL_P (JUMP_LABEL (insn)))
190 6681633 : LABEL_NUSES (JUMP_LABEL (insn))--;
191 :
192 : /* If there are more targets, remove them too. */
193 : while ((note
194 13382828 : = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
195 6691414 : && LABEL_P (XEXP (note, 0)))
196 : {
197 0 : LABEL_NUSES (XEXP (note, 0))--;
198 0 : remove_note (insn, note);
199 : }
200 : }
201 :
202 : /* Also if deleting any insn that references a label as an operand. */
203 255633060 : while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
204 127816530 : && LABEL_P (XEXP (note, 0)))
205 : {
206 7629 : LABEL_NUSES (XEXP (note, 0))--;
207 7629 : remove_note (insn, note);
208 : }
209 :
210 127808901 : if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
211 : {
212 7 : rtvec vec = table->get_labels ();
213 7 : int len = GET_NUM_ELEM (vec);
214 7 : int i;
215 :
216 84 : for (i = 0; i < len; i++)
217 : {
218 77 : rtx label = XEXP (RTVEC_ELT (vec, i), 0);
219 :
220 : /* When deleting code in bulk (e.g. removing many unreachable
221 : blocks) we can delete a label that's a target of the vector
222 : before deleting the vector itself. */
223 77 : if (!NOTE_P (label))
224 77 : LABEL_NUSES (label)--;
225 : }
226 : }
227 127808901 : }
228 :
229 : /* Like delete_insn but also purge dead edges from BB.
230 : Return true if any edges are eliminated. */
231 :
232 : bool
233 12531380 : delete_insn_and_edges (rtx_insn *insn)
234 : {
235 12531380 : bool purge = false;
236 :
237 12531380 : if (NONDEBUG_INSN_P (insn) && BLOCK_FOR_INSN (insn))
238 : {
239 12166699 : basic_block bb = BLOCK_FOR_INSN (insn);
240 12166699 : if (BB_END (bb) == insn)
241 : purge = true;
242 11473308 : else if (DEBUG_INSN_P (BB_END (bb)))
243 1030090 : for (rtx_insn *dinsn = NEXT_INSN (insn);
244 1030090 : DEBUG_INSN_P (dinsn); dinsn = NEXT_INSN (dinsn))
245 696357 : if (BB_END (bb) == dinsn)
246 : {
247 : purge = true;
248 : break;
249 : }
250 : }
251 12531380 : delete_insn (insn);
252 12531380 : if (purge)
253 742223 : return purge_dead_edges (BLOCK_FOR_INSN (insn));
254 : return false;
255 : }
256 :
257 : /* Unlink a chain of insns between START and FINISH, leaving notes
258 : that must be paired. If CLEAR_BB is true, we set bb field for
259 : insns that cannot be removed to NULL. */
260 :
261 : void
262 17278217 : delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb)
263 : {
264 : /* Unchain the insns one by one. It would be quicker to delete all of these
265 : with a single unchaining, rather than one at a time, but we need to keep
266 : the NOTE's. */
267 17278217 : rtx_insn *current = finish;
268 29285702 : while (1)
269 : {
270 29285702 : rtx_insn *prev = PREV_INSN (current);
271 29285702 : if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
272 : ;
273 : else
274 29279845 : delete_insn (current);
275 :
276 29285702 : if (clear_bb && !current->deleted ())
277 47592 : set_block_for_insn (current, NULL);
278 :
279 29285702 : if (current == start)
280 : break;
281 : current = prev;
282 : }
283 17278217 : }
284 :
285 : /* Create a new basic block consisting of the instructions between HEAD and END
286 : inclusive. This function is designed to allow fast BB construction - reuses
287 : the note and basic block struct in BB_NOTE, if any and do not grow
288 : BASIC_BLOCK chain and should be used directly only by CFG construction code.
289 : END can be NULL in to create new empty basic block before HEAD. Both END
290 : and HEAD can be NULL to create basic block at the end of INSN chain.
291 : AFTER is the basic block we should be put after. */
292 :
293 : basic_block
294 13030735 : create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
295 : basic_block after)
296 : {
297 13030735 : basic_block bb;
298 :
299 13030735 : if (bb_note
300 0 : && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
301 13030735 : && bb->aux == NULL)
302 : {
303 : /* If we found an existing note, thread it back onto the chain. */
304 :
305 0 : rtx_insn *after;
306 :
307 0 : if (LABEL_P (head))
308 : after = head;
309 : else
310 : {
311 0 : after = PREV_INSN (head);
312 0 : head = bb_note;
313 : }
314 :
315 0 : if (after != bb_note && NEXT_INSN (after) != bb_note)
316 0 : reorder_insns_nobb (bb_note, bb_note, after);
317 : }
318 : else
319 : {
320 : /* Otherwise we must create a note and a basic block structure. */
321 :
322 13030735 : bb = alloc_block ();
323 :
324 13030735 : init_rtl_bb_info (bb);
325 13030735 : if (!head && !end)
326 475094 : head = end = bb_note
327 475094 : = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
328 12555641 : else if (LABEL_P (head) && end)
329 : {
330 2725320 : bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
331 2725320 : if (head == end)
332 917045 : end = bb_note;
333 : }
334 : else
335 : {
336 9830321 : bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
337 9830321 : head = bb_note;
338 9830321 : if (!end)
339 5455655 : end = head;
340 : }
341 :
342 13030735 : NOTE_BASIC_BLOCK (bb_note) = bb;
343 : }
344 :
345 : /* Always include the bb note in the block. */
346 13030735 : if (NEXT_INSN (end) == bb_note)
347 0 : end = bb_note;
348 :
349 13030735 : BB_HEAD (bb) = head;
350 13030735 : BB_END (bb) = end;
351 13030735 : bb->index = last_basic_block_for_fn (cfun)++;
352 13030735 : bb->flags = BB_NEW | BB_RTL;
353 13030735 : link_block (bb, after);
354 13030735 : SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
355 13030735 : df_bb_refs_record (bb->index, false);
356 13030735 : update_bb_for_insn (bb);
357 13030735 : BB_SET_PARTITION (bb, BB_UNPARTITIONED);
358 :
359 : /* Tag the block so that we know it has been used when considering
360 : other basic block notes. */
361 13030735 : bb->aux = bb;
362 :
363 13030735 : return bb;
364 : }
365 :
366 : /* Create new basic block consisting of instructions in between HEAD and END
367 : and place it to the BB chain after block AFTER. END can be NULL to
368 : create a new empty basic block before HEAD. Both END and HEAD can be
369 : NULL to create basic block at the end of INSN chain. */
370 :
371 : static basic_block
372 13030735 : rtl_create_basic_block (void *headp, void *endp, basic_block after)
373 : {
374 13030735 : rtx_insn *head = (rtx_insn *) headp;
375 13030735 : rtx_insn *end = (rtx_insn *) endp;
376 13030735 : basic_block bb;
377 :
378 : /* Grow the basic block array if needed. */
379 13030735 : if ((size_t) last_basic_block_for_fn (cfun)
380 13030735 : >= basic_block_info_for_fn (cfun)->length ())
381 874163 : vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
382 874163 : last_basic_block_for_fn (cfun) + 1);
383 :
384 13030735 : n_basic_blocks_for_fn (cfun)++;
385 :
386 13030735 : bb = create_basic_block_structure (head, end, NULL, after);
387 13030735 : bb->aux = NULL;
388 13030735 : return bb;
389 : }
390 :
391 : static basic_block
392 4234603 : cfg_layout_create_basic_block (void *head, void *end, basic_block after)
393 : {
394 4234603 : basic_block newbb = rtl_create_basic_block (head, end, after);
395 :
396 4234603 : return newbb;
397 : }
398 :
399 : /* Delete the insns in a (non-live) block. We physically delete every
400 : non-deleted-note insn, and update the flow graph appropriately.
401 :
402 : Return nonzero if we deleted an exception handler. */
403 :
404 : /* ??? Preserving all such notes strikes me as wrong. It would be nice
405 : to post-process the stream to remove empty blocks, loops, ranges, etc. */
406 :
407 : static void
408 6652382 : rtl_delete_block (basic_block b)
409 : {
410 6652382 : rtx_insn *insn, *end;
411 :
412 : /* If the head of this block is a CODE_LABEL, then it might be the
413 : label for an exception handler which can't be reached. We need
414 : to remove the label from the exception_handler_label list. */
415 6652382 : insn = BB_HEAD (b);
416 :
417 6652382 : end = get_last_bb_insn (b);
418 :
419 : /* Selectively delete the entire chain. */
420 6652382 : BB_HEAD (b) = NULL;
421 6652382 : delete_insn_chain (insn, end, true);
422 :
423 :
424 6652382 : if (dump_file)
425 711 : fprintf (dump_file, "deleting block %d\n", b->index);
426 6652382 : df_bb_delete (b->index);
427 6652382 : }
428 :
429 : /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
430 :
431 : void
432 1481542 : compute_bb_for_insn (void)
433 : {
434 1481542 : basic_block bb;
435 :
436 15702914 : FOR_EACH_BB_FN (bb, cfun)
437 : {
438 14221372 : rtx_insn *end = BB_END (bb);
439 14221372 : rtx_insn *insn;
440 :
441 172050850 : for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
442 : {
443 172050850 : BLOCK_FOR_INSN (insn) = bb;
444 172050850 : if (insn == end)
445 : break;
446 : }
447 : }
448 1481542 : }
449 :
450 : /* Release the basic_block_for_insn array. */
451 :
452 : void
453 2963783 : free_bb_for_insn (void)
454 : {
455 2963783 : rtx_insn *insn;
456 207243135 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
457 204279352 : if (!BARRIER_P (insn))
458 199545995 : BLOCK_FOR_INSN (insn) = NULL;
459 2963783 : }
460 :
461 : namespace {
462 :
463 : const pass_data pass_data_free_cfg =
464 : {
465 : RTL_PASS, /* type */
466 : "*free_cfg", /* name */
467 : OPTGROUP_NONE, /* optinfo_flags */
468 : TV_NONE, /* tv_id */
469 : 0, /* properties_required */
470 : 0, /* properties_provided */
471 : PROP_cfg, /* properties_destroyed */
472 : 0, /* todo_flags_start */
473 : 0, /* todo_flags_finish */
474 : };
475 :
476 : class pass_free_cfg : public rtl_opt_pass
477 : {
478 : public:
479 288767 : pass_free_cfg (gcc::context *ctxt)
480 577534 : : rtl_opt_pass (pass_data_free_cfg, ctxt)
481 : {}
482 :
483 : /* opt_pass methods: */
484 : unsigned int execute (function *) final override;
485 :
486 : }; // class pass_free_cfg
487 :
488 : unsigned int
489 1481484 : pass_free_cfg::execute (function *)
490 : {
491 : /* The resource.cc machinery uses DF but the CFG isn't guaranteed to be
492 : valid at that point so it would be too late to call df_analyze. */
493 1481484 : if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch)
494 : {
495 : df_note_add_problem ();
496 : df_analyze ();
497 : }
498 :
499 1481484 : if (crtl->has_bb_partition)
500 64744 : insert_section_boundary_note ();
501 :
502 1481484 : free_bb_for_insn ();
503 1481484 : return 0;
504 : }
505 :
506 : } // anon namespace
507 :
508 : rtl_opt_pass *
509 288767 : make_pass_free_cfg (gcc::context *ctxt)
510 : {
511 288767 : return new pass_free_cfg (ctxt);
512 : }
513 :
514 : /* Return RTX to emit after when we want to emit code on the entry of function. */
515 : rtx_insn *
516 7771 : entry_of_function (void)
517 : {
518 7771 : return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
519 7771 : BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
520 : }
521 :
522 : /* Emit INSN at the entry point of the function, ensuring that it is only
523 : executed once per function. */
524 : void
525 0 : emit_insn_at_entry (rtx insn)
526 : {
527 0 : edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
528 0 : edge e = ei_safe_edge (ei);
529 0 : gcc_assert (e->flags & EDGE_FALLTHRU);
530 :
531 0 : insert_insn_on_edge (insn, e);
532 0 : commit_edge_insertions ();
533 0 : }
534 :
535 : /* Update BLOCK_FOR_INSN of insns between BEGIN and END
536 : (or BARRIER if found) and notify df of the bb change.
537 : The insn chain range is inclusive
538 : (i.e. both BEGIN and END will be updated. */
539 :
540 : void
541 33145135 : update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
542 : {
543 33145135 : rtx_insn *insn;
544 :
545 33145135 : end = NEXT_INSN (end);
546 346271902 : for (insn = begin; insn != end; insn = NEXT_INSN (insn))
547 279981632 : if (!BARRIER_P (insn))
548 277539911 : df_insn_change_bb (insn, bb);
549 33145135 : }
550 :
551 : /* Update BLOCK_FOR_INSN of insns in BB to BB,
552 : and notify df of the change. */
553 :
554 : void
555 16602682 : update_bb_for_insn (basic_block bb)
556 : {
557 16602682 : update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
558 16602682 : }
559 :
560 :
561 : /* Return true if adding or removing instances of INSN might affect the
562 : semantics of the RTL. */
563 :
564 : static bool
565 321539313 : flow_active_insn_p (const rtx_insn *insn)
566 : {
567 321539313 : if (active_insn_p (insn))
568 : return true;
569 :
570 : /* We cannot add new clobbers to a path without first proving that
571 : the clobbered thing is dead.
572 :
573 : For example:
574 :
575 : (code_label L1)
576 : (clobber X)
577 : (set (pc) (label_ref L2))
578 :
579 : is a forwarder block in the sense that a jump to L1 can be replaced
580 : with a jump to L2, although perhaps with some loss of dataflow precision.
581 : However, any attempt to merge a jump to L1 with a jump to L2 would be an
582 : asymmetric operation, in that the merged code must jump to L2 rather than
583 : to L1. Our current definition of "forwarder block" does not allow for
584 : this distinction and so we need to take a conservatively correct
585 : approach. */
586 196491802 : if (GET_CODE (PATTERN (insn)) == CLOBBER)
587 : return true;
588 :
589 : /* Keep a USE of the function return value, otherwise the USE is dropped and
590 : we could fail to thread a jump if USE appears on some paths and not on
591 : others, see PR90257. */
592 196428068 : if (GET_CODE (PATTERN (insn)) == USE
593 571582 : && REG_P (XEXP (PATTERN (insn), 0))
594 196999650 : && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
595 566250 : return true;
596 :
597 : return false;
598 : }
599 :
600 : /* Return true if the block has no effect and only forwards control flow to
601 : its single destination. */
602 :
603 : bool
604 311738144 : contains_no_active_insn_p (const_basic_block bb)
605 : {
606 311738144 : rtx_insn *insn;
607 :
608 311738144 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
609 311738144 : || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
610 438059270 : || !single_succ_p (bb)
611 456044666 : || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0)
612 : return false;
613 :
614 550683830 : for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
615 505035010 : if (INSN_P (insn) && flow_active_insn_p (insn))
616 : return false;
617 :
618 45648820 : return (!INSN_P (insn)
619 35236128 : || (JUMP_P (insn) && simplejump_p (insn))
620 73644472 : || !flow_active_insn_p (insn));
621 : }
622 :
623 : /* Likewise, but protect loop latches, headers and preheaders. */
624 : /* FIXME: Make this a cfg hook. */
625 :
626 : bool
627 311738144 : forwarder_block_p (const_basic_block bb)
628 : {
629 311738144 : if (!contains_no_active_insn_p (bb))
630 : return false;
631 :
632 : /* Protect loop latches, headers and preheaders. */
633 17985396 : if (current_loops)
634 : {
635 8919632 : basic_block dest;
636 8919632 : if (bb->loop_father->header == bb)
637 : return false;
638 8833288 : dest = EDGE_SUCC (bb, 0)->dest;
639 8833288 : if (dest->loop_father->header == dest)
640 1096230 : return false;
641 : }
642 :
643 : return true;
644 : }
645 :
646 : /* Return nonzero if we can reach target from src by falling through. */
647 : /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
648 :
649 : bool
650 43769610 : can_fallthru (basic_block src, basic_block target)
651 : {
652 43769610 : rtx_insn *insn = BB_END (src);
653 43769610 : rtx_insn *insn2;
654 43769610 : edge e;
655 43769610 : edge_iterator ei;
656 :
657 43769610 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
658 : return true;
659 42393374 : if (src->next_bb != target)
660 : return false;
661 :
662 : /* ??? Later we may add code to move jump tables offline. */
663 17312056 : if (tablejump_p (insn, NULL, NULL))
664 : return false;
665 :
666 47033176 : FOR_EACH_EDGE (e, ei, src->succs)
667 29721120 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
668 0 : && e->flags & EDGE_FALLTHRU)
669 : return false;
670 :
671 17312056 : insn2 = BB_HEAD (target);
672 17312056 : if (!active_insn_p (insn2))
673 17312056 : insn2 = next_active_insn (insn2);
674 :
675 17312056 : return next_active_insn (insn) == insn2;
676 : }
677 :
678 : /* Return nonzero if we could reach target from src by falling through,
679 : if the target was made adjacent. If we already have a fall-through
680 : edge to the exit block, we can't do that. */
681 : static bool
682 2262851 : could_fall_through (basic_block src, basic_block target)
683 : {
684 2262851 : edge e;
685 2262851 : edge_iterator ei;
686 :
687 2262851 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
688 : return true;
689 6788553 : FOR_EACH_EDGE (e, ei, src->succs)
690 4525702 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
691 0 : && e->flags & EDGE_FALLTHRU)
692 : return 0;
693 : return true;
694 : }
695 :
696 : /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
697 : rtx_note *
698 63350659 : bb_note (basic_block bb)
699 : {
700 63350659 : rtx_insn *note;
701 :
702 63350659 : note = BB_HEAD (bb);
703 63350659 : if (LABEL_P (note))
704 30411176 : note = NEXT_INSN (note);
705 :
706 63350659 : gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
707 63350659 : return as_a <rtx_note *> (note);
708 : }
709 :
710 : /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
711 : note associated with the BLOCK. */
712 :
713 : static rtx_insn *
714 8466 : first_insn_after_basic_block_note (basic_block block)
715 : {
716 8466 : rtx_insn *insn;
717 :
718 : /* Get the first instruction in the block. */
719 8466 : insn = BB_HEAD (block);
720 :
721 8466 : if (insn == NULL_RTX)
722 : return NULL;
723 8466 : if (LABEL_P (insn))
724 8466 : insn = NEXT_INSN (insn);
725 8466 : gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
726 :
727 8466 : return NEXT_INSN (insn);
728 : }
729 :
730 : /* Creates a new basic block just after basic block BB by splitting
731 : everything after specified instruction INSNP. */
732 :
733 : static basic_block
734 2975721 : rtl_split_block (basic_block bb, void *insnp)
735 : {
736 2975721 : basic_block new_bb;
737 2975721 : rtx_insn *insn = (rtx_insn *) insnp;
738 2975721 : edge e;
739 2975721 : edge_iterator ei;
740 :
741 2975721 : if (!insn)
742 : {
743 8466 : insn = first_insn_after_basic_block_note (bb);
744 :
745 8466 : if (insn)
746 : {
747 8442 : rtx_insn *next = insn;
748 :
749 8442 : insn = PREV_INSN (insn);
750 :
751 : /* If the block contains only debug insns, insn would have
752 : been NULL in a non-debug compilation, and then we'd end
753 : up emitting a DELETED note. For -fcompare-debug
754 : stability, emit the note too. */
755 8442 : if (insn != BB_END (bb)
756 8199 : && DEBUG_INSN_P (next)
757 471 : && DEBUG_INSN_P (BB_END (bb)))
758 : {
759 284 : while (next != BB_END (bb) && DEBUG_INSN_P (next))
760 205 : next = NEXT_INSN (next);
761 :
762 79 : if (next == BB_END (bb))
763 78 : emit_note_after (NOTE_INSN_DELETED, next);
764 : }
765 : }
766 : else
767 24 : insn = get_last_insn ();
768 : }
769 :
770 : /* We probably should check type of the insn so that we do not create
771 : inconsistent cfg. It is checked in verify_flow_info anyway, so do not
772 : bother. */
773 2975721 : if (insn == BB_END (bb))
774 267 : emit_note_after (NOTE_INSN_DELETED, insn);
775 :
776 : /* Create the new basic block. */
777 2975721 : new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
778 2975721 : BB_COPY_PARTITION (new_bb, bb);
779 2975721 : BB_END (bb) = insn;
780 :
781 : /* Redirect the outgoing edges. */
782 2975721 : new_bb->succs = bb->succs;
783 2975721 : bb->succs = NULL;
784 8152648 : FOR_EACH_EDGE (e, ei, new_bb->succs)
785 5176927 : e->src = new_bb;
786 :
787 : /* The new block starts off being dirty. */
788 2975721 : df_set_bb_dirty (bb);
789 2975721 : return new_bb;
790 : }
791 :
792 : /* Return true if LOC1 and LOC2 are equivalent for
793 : unique_locus_on_edge_between_p purposes. */
794 :
795 : static bool
796 1403051 : loc_equal (location_t loc1, location_t loc2)
797 : {
798 1403051 : if (loc1 == loc2)
799 : return true;
800 :
801 659697 : expanded_location loce1 = expand_location (loc1);
802 659697 : expanded_location loce2 = expand_location (loc2);
803 :
804 659697 : if (loce1.line != loce2.line
805 436390 : || loce1.column != loce2.column
806 309474 : || loce1.data != loce2.data)
807 : return false;
808 270560 : if (loce1.file == loce2.file)
809 : return true;
810 0 : return (loce1.file != NULL
811 0 : && loce2.file != NULL
812 0 : && filename_cmp (loce1.file, loce2.file) == 0);
813 : }
814 :
815 : /* Return true if the single edge between blocks A and B is the only place
816 : in RTL which holds some unique locus. */
817 :
818 : static bool
819 1125900 : unique_locus_on_edge_between_p (basic_block a, basic_block b)
820 : {
821 1125900 : const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
822 1125900 : rtx_insn *insn, *end;
823 :
824 1125900 : if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
825 : return false;
826 :
827 : /* First scan block A backward. */
828 509779 : insn = BB_END (a);
829 509779 : end = PREV_INSN (BB_HEAD (a));
830 1193650 : while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
831 174092 : insn = PREV_INSN (insn);
832 :
833 509779 : if (insn != end && loc_equal (INSN_LOCATION (insn), goto_locus))
834 : return false;
835 :
836 : /* Then scan block B forward. */
837 187807 : insn = BB_HEAD (b);
838 187807 : if (insn)
839 : {
840 178373 : end = NEXT_INSN (BB_END (b));
841 358095 : while (insn != end && !NONDEBUG_INSN_P (insn))
842 1349 : insn = NEXT_INSN (insn);
843 :
844 178125 : if (insn != end && INSN_HAS_LOCATION (insn)
845 355626 : && loc_equal (INSN_LOCATION (insn), goto_locus))
846 : return false;
847 : }
848 :
849 : return true;
850 : }
851 :
852 : /* If the single edge between blocks A and B is the only place in RTL which
853 : holds some unique locus, emit a nop with that locus between the blocks. */
854 :
855 : static void
856 1125900 : emit_nop_for_unique_locus_between (basic_block a, basic_block b)
857 : {
858 1125900 : if (!unique_locus_on_edge_between_p (a, b))
859 : return;
860 :
861 21858 : BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
862 21858 : INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
863 : }
864 :
865 : /* Blocks A and B are to be merged into a single block A. The insns
866 : are already contiguous. */
867 :
868 : static void
869 3754736 : rtl_merge_blocks (basic_block a, basic_block b)
870 : {
871 : /* If B is a forwarder block whose outgoing edge has no location, we'll
872 : propagate the locus of the edge between A and B onto it. */
873 3754736 : const bool forward_edge_locus
874 3754736 : = (b->flags & BB_FORWARDER_BLOCK) != 0
875 3754736 : && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
876 3754736 : rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
877 3754736 : rtx_insn *del_first = NULL, *del_last = NULL;
878 3754736 : rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
879 3754736 : bool b_empty = false;
880 :
881 3754736 : if (dump_file)
882 848 : fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
883 : a->index);
884 :
885 4203403 : while (DEBUG_INSN_P (b_end))
886 448667 : b_end = PREV_INSN (b_debug_start = b_end);
887 :
888 : /* If there was a CODE_LABEL beginning B, delete it. */
889 3754736 : if (LABEL_P (b_head))
890 : {
891 : /* Detect basic blocks with nothing but a label. This can happen
892 : in particular at the end of a function. */
893 1748770 : if (b_head == b_end)
894 0 : b_empty = true;
895 :
896 1748770 : del_first = del_last = b_head;
897 1748770 : b_head = NEXT_INSN (b_head);
898 : }
899 :
900 : /* Delete the basic block note and handle blocks containing just that
901 : note. */
902 3754736 : if (NOTE_INSN_BASIC_BLOCK_P (b_head))
903 : {
904 3754736 : if (b_head == b_end)
905 711921 : b_empty = true;
906 3754736 : if (! del_last)
907 2005966 : del_first = b_head;
908 :
909 3754736 : del_last = b_head;
910 3754736 : b_head = NEXT_INSN (b_head);
911 : }
912 :
913 : /* If there was a jump out of A, delete it. */
914 3754736 : if (JUMP_P (a_end))
915 : {
916 51752 : rtx_insn *prev;
917 :
918 52818 : for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
919 52818 : if (!NOTE_P (prev)
920 1092 : || NOTE_INSN_BASIC_BLOCK_P (prev)
921 1066 : || prev == BB_HEAD (a))
922 : break;
923 :
924 : del_first = a_end;
925 :
926 : a_end = PREV_INSN (del_first);
927 : }
928 3702984 : else if (BARRIER_P (NEXT_INSN (a_end)))
929 0 : del_first = NEXT_INSN (a_end);
930 :
931 : /* Delete everything marked above as well as crap that might be
932 : hanging out between the two blocks. */
933 3754736 : BB_END (a) = a_end;
934 3754736 : BB_HEAD (b) = b_empty ? NULL : b_head;
935 3754736 : delete_insn_chain (del_first, del_last, true);
936 :
937 : /* If not optimizing, preserve the locus of the single edge between
938 : blocks A and B if necessary by emitting a nop. */
939 3754736 : if (!optimize
940 1386764 : && !forward_edge_locus
941 4881444 : && !DECL_IGNORED_P (current_function_decl))
942 : {
943 1123704 : emit_nop_for_unique_locus_between (a, b);
944 1123704 : a_end = BB_END (a);
945 : }
946 :
947 : /* Reassociate the insns of B with A. */
948 3754736 : if (!b_empty)
949 : {
950 3042815 : update_bb_for_insn_chain (a_end, b_debug_end, a);
951 :
952 3042815 : BB_END (a) = b_debug_end;
953 3042815 : BB_HEAD (b) = NULL;
954 : }
955 711921 : else if (b_end != b_debug_end)
956 : {
957 : /* Move any deleted labels and other notes between the end of A
958 : and the debug insns that make up B after the debug insns,
959 : bringing the debug insns into A while keeping the notes after
960 : the end of A. */
961 21257 : if (NEXT_INSN (a_end) != b_debug_start)
962 137 : reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
963 : b_debug_end);
964 21257 : update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
965 21257 : BB_END (a) = b_debug_end;
966 : }
967 :
968 3754736 : df_bb_delete (b->index);
969 :
970 3754736 : if (forward_edge_locus)
971 685388 : EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
972 :
973 3754736 : if (dump_file)
974 848 : fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
975 3754736 : }
976 :
977 :
978 : /* Return true when block A and B can be merged. */
979 :
980 : static bool
981 62 : rtl_can_merge_blocks (basic_block a, basic_block b)
982 : {
983 : /* If we are partitioning hot/cold basic blocks, we don't want to
984 : mess up unconditional or indirect jumps that cross between hot
985 : and cold sections.
986 :
987 : Basic block partitioning may result in some jumps that appear to
988 : be optimizable (or blocks that appear to be mergeable), but which really
989 : must be left untouched (they are required to make it safely across
990 : partition boundaries). See the comments at the top of
991 : bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
992 :
993 62 : if (BB_PARTITION (a) != BB_PARTITION (b))
994 : return false;
995 :
996 : /* Protect the loop latches. */
997 62 : if (current_loops && b->loop_father->latch == b)
998 : return false;
999 :
1000 : /* There must be exactly one edge in between the blocks. */
1001 62 : return (single_succ_p (a)
1002 61 : && single_succ (a) == b
1003 51 : && single_pred_p (b)
1004 51 : && a != b
1005 : /* Must be simple edge. */
1006 51 : && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
1007 51 : && a->next_bb == b
1008 51 : && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1009 51 : && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
1010 : /* If the jump insn has side effects,
1011 : we can't kill the edge. */
1012 113 : && (!JUMP_P (BB_END (a))
1013 0 : || (reload_completed
1014 0 : ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
1015 : }
1016 :
1017 : /* Return the label in the head of basic block BLOCK. Create one if it doesn't
1018 : exist. */
1019 :
1020 : rtx_code_label *
1021 15174894 : block_label (basic_block block)
1022 : {
1023 15174894 : if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
1024 : return NULL;
1025 :
1026 15124368 : if (!LABEL_P (BB_HEAD (block)))
1027 : {
1028 5612635 : BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
1029 : }
1030 :
1031 15124368 : return as_a <rtx_code_label *> (BB_HEAD (block));
1032 : }
1033 :
1034 : /* Remove all barriers from BB_FOOTER of a BB. */
1035 :
1036 : static void
1037 3711300 : remove_barriers_from_footer (basic_block bb)
1038 : {
1039 3711300 : rtx_insn *insn = BB_FOOTER (bb);
1040 :
1041 : /* Remove barriers but keep jumptables. */
1042 7164389 : while (insn)
1043 : {
1044 3453089 : if (BARRIER_P (insn))
1045 : {
1046 3453073 : if (PREV_INSN (insn))
1047 16 : SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1048 : else
1049 3453057 : BB_FOOTER (bb) = NEXT_INSN (insn);
1050 3453073 : if (NEXT_INSN (insn))
1051 62427 : SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1052 : }
1053 3453089 : if (LABEL_P (insn))
1054 : return;
1055 3453089 : insn = NEXT_INSN (insn);
1056 : }
1057 : }
1058 :
1059 : /* Attempt to perform edge redirection by replacing possibly complex jump
1060 : instruction by unconditional jump or removing jump completely. This can
1061 : apply only if all edges now point to the same block. The parameters and
1062 : return values are equivalent to redirect_edge_and_branch. */
1063 :
1064 : edge
1065 47343848 : try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1066 : {
1067 47343848 : basic_block src = e->src;
1068 47343848 : rtx_insn *insn = BB_END (src);
1069 47343848 : rtx set;
1070 47343848 : bool fallthru = false;
1071 :
1072 : /* If we are partitioning hot/cold basic blocks, we don't want to
1073 : mess up unconditional or indirect jumps that cross between hot
1074 : and cold sections.
1075 :
1076 : Basic block partitioning may result in some jumps that appear to
1077 : be optimizable (or blocks that appear to be mergeable), but which really
1078 : must be left untouched (they are required to make it safely across
1079 : partition boundaries). See the comments at the top of
1080 : bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1081 :
1082 47343848 : if (BB_PARTITION (src) != BB_PARTITION (target))
1083 : return NULL;
1084 :
1085 : /* We can replace or remove a complex jump only when we have exactly
1086 : two edges. Also, if we have exactly one outgoing edge, we can
1087 : redirect that. */
1088 47287916 : if (EDGE_COUNT (src->succs) >= 3
1089 : /* Verify that all targets will be TARGET. Specifically, the
1090 : edge that is not E must also go to TARGET. */
1091 47287916 : || (EDGE_COUNT (src->succs) == 2
1092 17758759 : && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1093 : return NULL;
1094 :
1095 29670353 : if (!onlyjump_p (insn))
1096 : return NULL;
1097 28151156 : if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1098 : return NULL;
1099 :
1100 : /* Avoid removing branch with side effects. */
1101 28151039 : set = single_set (insn);
1102 28151039 : if (!set || side_effects_p (set))
1103 0 : return NULL;
1104 :
1105 : /* See if we can create the fallthru edge. */
1106 28151039 : if (in_cfglayout || can_fallthru (src, target))
1107 : {
1108 4565906 : if (dump_file)
1109 780 : fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1110 4565906 : fallthru = true;
1111 :
1112 : /* Selectively unlink whole insn chain. */
1113 4565906 : if (in_cfglayout)
1114 : {
1115 3711299 : delete_insn_chain (insn, BB_END (src), false);
1116 3711299 : remove_barriers_from_footer (src);
1117 : }
1118 : else
1119 854607 : delete_insn_chain (insn, PREV_INSN (BB_HEAD (target)), false);
1120 : }
1121 :
1122 : /* If this already is simplejump, redirect it. */
1123 23585133 : else if (simplejump_p (insn))
1124 : {
1125 23583151 : if (e->dest == target)
1126 : return NULL;
1127 420065 : if (dump_file)
1128 36 : fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1129 36 : INSN_UID (insn), e->dest->index, target->index);
1130 420065 : if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1131 420065 : block_label (target), 0))
1132 : {
1133 0 : gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1134 : return NULL;
1135 : }
1136 : }
1137 :
1138 : /* Cannot do anything for target exit block. */
1139 1982 : else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1140 : return NULL;
1141 :
1142 : /* Or replace possibly complicated jump insn by simple jump insn. */
1143 : else
1144 : {
1145 1982 : rtx_code_label *target_label = block_label (target);
1146 1982 : rtx_insn *barrier;
1147 1982 : rtx_insn *label;
1148 1982 : rtx_jump_table_data *table;
1149 :
1150 1982 : emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1151 1982 : JUMP_LABEL (BB_END (src)) = target_label;
1152 1982 : LABEL_NUSES (target_label)++;
1153 1982 : if (dump_file)
1154 0 : fprintf (dump_file, "Replacing insn %i by jump %i\n",
1155 0 : INSN_UID (insn), INSN_UID (BB_END (src)));
1156 :
1157 :
1158 1982 : delete_insn_chain (insn, insn, false);
1159 :
1160 : /* Recognize a tablejump that we are converting to a
1161 : simple jump and remove its associated CODE_LABEL
1162 : and ADDR_VEC or ADDR_DIFF_VEC. */
1163 1982 : if (tablejump_p (insn, &label, &table))
1164 2 : delete_insn_chain (label, table, false);
1165 :
1166 1982 : barrier = next_nonnote_nondebug_insn (BB_END (src));
1167 1982 : if (!barrier || !BARRIER_P (barrier))
1168 1848 : emit_barrier_after (BB_END (src));
1169 : else
1170 : {
1171 134 : if (barrier != NEXT_INSN (BB_END (src)))
1172 : {
1173 : /* Move the jump before barrier so that the notes
1174 : which originally were or were created before jump table are
1175 : inside the basic block. */
1176 0 : rtx_insn *new_insn = BB_END (src);
1177 :
1178 0 : update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1179 : PREV_INSN (barrier), src);
1180 :
1181 0 : SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1182 0 : SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1183 :
1184 0 : SET_NEXT_INSN (new_insn) = barrier;
1185 0 : SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1186 :
1187 0 : SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1188 0 : SET_PREV_INSN (barrier) = new_insn;
1189 : }
1190 : }
1191 : }
1192 :
1193 : /* Keep only one edge out and set proper flags. */
1194 4987953 : if (!single_succ_p (src))
1195 155473 : remove_edge (e);
1196 4987953 : gcc_assert (single_succ_p (src));
1197 :
1198 4987953 : e = single_succ_edge (src);
1199 4987953 : if (fallthru)
1200 4565906 : e->flags = EDGE_FALLTHRU;
1201 : else
1202 422047 : e->flags = 0;
1203 :
1204 4987953 : e->probability = profile_probability::always ();
1205 :
1206 4987953 : if (e->dest != target)
1207 635341 : redirect_edge_succ (e, target);
1208 : return e;
1209 : }
1210 :
1211 : /* Subroutine of redirect_branch_edge that tries to patch the jump
1212 : instruction INSN so that it reaches block NEW. Do this
1213 : only when it originally reached block OLD. Return true if this
1214 : worked or the original target wasn't OLD, return false if redirection
1215 : doesn't work. */
1216 :
1217 : static bool
1218 6744152 : patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1219 : {
1220 6744152 : rtx_jump_table_data *table;
1221 6744152 : rtx tmp;
1222 : /* Recognize a tablejump and adjust all matching cases. */
1223 6744152 : if (tablejump_p (insn, NULL, &table))
1224 : {
1225 10594 : rtvec vec;
1226 10594 : int j;
1227 10594 : rtx_code_label *new_label = block_label (new_bb);
1228 :
1229 10594 : if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1230 : return false;
1231 10594 : vec = table->get_labels ();
1232 :
1233 317599 : for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1234 307005 : if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1235 : {
1236 50901 : RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1237 44019 : --LABEL_NUSES (old_label);
1238 44019 : ++LABEL_NUSES (new_label);
1239 : }
1240 :
1241 : /* Handle casesi dispatch insns. */
1242 10594 : if ((tmp = tablejump_casesi_pattern (insn)) != NULL_RTX
1243 10594 : && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1244 : {
1245 0 : XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1246 : new_label);
1247 0 : --LABEL_NUSES (old_label);
1248 0 : ++LABEL_NUSES (new_label);
1249 : }
1250 : }
1251 6733558 : else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1252 : {
1253 411 : int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1254 411 : rtx note;
1255 :
1256 411 : if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1257 : return false;
1258 411 : rtx_code_label *new_label = block_label (new_bb);
1259 :
1260 1117 : for (i = 0; i < n; ++i)
1261 : {
1262 706 : rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1263 706 : gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1264 706 : if (XEXP (old_ref, 0) == old_label)
1265 : {
1266 818 : ASM_OPERANDS_LABEL (tmp, i)
1267 409 : = gen_rtx_LABEL_REF (Pmode, new_label);
1268 409 : --LABEL_NUSES (old_label);
1269 409 : ++LABEL_NUSES (new_label);
1270 : }
1271 : }
1272 :
1273 411 : if (JUMP_LABEL (insn) == old_label)
1274 : {
1275 305 : JUMP_LABEL (insn) = new_label;
1276 305 : note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1277 305 : if (note)
1278 0 : remove_note (insn, note);
1279 : }
1280 : else
1281 : {
1282 106 : note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1283 106 : if (note)
1284 99 : remove_note (insn, note);
1285 106 : if (JUMP_LABEL (insn) != new_label
1286 106 : && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1287 99 : add_reg_note (insn, REG_LABEL_TARGET, new_label);
1288 : }
1289 822 : while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1290 411 : != NULL_RTX)
1291 0 : XEXP (note, 0) = new_label;
1292 : }
1293 : else
1294 : {
1295 : /* ?? We may play the games with moving the named labels from
1296 : one basic block to the other in case only one computed_jump is
1297 : available. */
1298 6733147 : if (computed_jump_p (insn)
1299 : /* A return instruction can't be redirected. */
1300 6733147 : || returnjump_p (insn))
1301 0 : return false;
1302 :
1303 6733147 : if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1304 : {
1305 : /* If the insn doesn't go where we think, we're confused. */
1306 6705731 : gcc_assert (JUMP_LABEL (insn) == old_label);
1307 :
1308 : /* If the substitution doesn't succeed, die. This can happen
1309 : if the back end emitted unrecognizable instructions or if
1310 : target is exit block on some arches. Or for crossing
1311 : jumps. */
1312 6705731 : if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1313 6705731 : block_label (new_bb), 0))
1314 : {
1315 0 : gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1316 : || CROSSING_JUMP_P (insn));
1317 : return false;
1318 : }
1319 : }
1320 : }
1321 : return true;
1322 : }
1323 :
1324 :
1325 : /* Redirect edge representing branch of (un)conditional jump or tablejump,
1326 : NULL on failure */
1327 : static edge
1328 14475242 : redirect_branch_edge (edge e, basic_block target)
1329 : {
1330 14475242 : rtx_insn *old_label = BB_HEAD (e->dest);
1331 14475242 : basic_block src = e->src;
1332 14475242 : rtx_insn *insn = BB_END (src);
1333 :
1334 : /* We can only redirect non-fallthru edges of jump insn. */
1335 14475242 : if (e->flags & EDGE_FALLTHRU)
1336 : return NULL;
1337 6705452 : else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1338 : return NULL;
1339 :
1340 6705452 : if (!currently_expanding_to_rtl)
1341 : {
1342 6291467 : if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1343 : return NULL;
1344 : }
1345 : else
1346 : /* When expanding this BB might actually contain multiple
1347 : jumps (i.e. not yet split by find_many_sub_basic_blocks).
1348 : Redirect all of those that match our label. */
1349 6722095 : FOR_BB_INSNS (src, insn)
1350 6308110 : if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1351 : old_label, target))
1352 : return NULL;
1353 :
1354 6705452 : if (dump_file)
1355 795 : fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1356 795 : e->src->index, e->dest->index, target->index);
1357 :
1358 6705452 : if (e->dest != target)
1359 6705452 : e = redirect_edge_succ_nodup (e, target);
1360 :
1361 : return e;
1362 : }
1363 :
1364 : /* Called when edge E has been redirected to a new destination,
1365 : in order to update the region crossing flag on the edge and
1366 : jump. */
1367 :
1368 : static void
1369 18063213 : fixup_partition_crossing (edge e)
1370 : {
1371 18063213 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1372 18063213 : == EXIT_BLOCK_PTR_FOR_FN (cfun))
1373 : return;
1374 : /* If we redirected an existing edge, it may already be marked
1375 : crossing, even though the new src is missing a reg crossing note.
1376 : But make sure reg crossing note doesn't already exist before
1377 : inserting. */
1378 18062381 : if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1379 : {
1380 111001 : e->flags |= EDGE_CROSSING;
1381 111001 : if (JUMP_P (BB_END (e->src)))
1382 111001 : CROSSING_JUMP_P (BB_END (e->src)) = 1;
1383 : }
1384 17951380 : else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1385 : {
1386 17951380 : e->flags &= ~EDGE_CROSSING;
1387 : /* Remove the section crossing note from jump at end of
1388 : src if it exists, and if no other successors are
1389 : still crossing. */
1390 17951380 : if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1391 : {
1392 196211 : bool has_crossing_succ = false;
1393 196211 : edge e2;
1394 196211 : edge_iterator ei;
1395 324463 : FOR_EACH_EDGE (e2, ei, e->src->succs)
1396 : {
1397 271988 : has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1398 271988 : if (has_crossing_succ)
1399 : break;
1400 : }
1401 196211 : if (!has_crossing_succ)
1402 52475 : CROSSING_JUMP_P (BB_END (e->src)) = 0;
1403 : }
1404 : }
1405 : }
1406 :
1407 : /* Called when block BB has been reassigned to the cold partition,
1408 : because it is now dominated by another cold block,
1409 : to ensure that the region crossing attributes are updated. */
1410 :
1411 : static void
1412 320 : fixup_new_cold_bb (basic_block bb)
1413 : {
1414 320 : edge e;
1415 320 : edge_iterator ei;
1416 :
1417 : /* This is called when a hot bb is found to now be dominated
1418 : by a cold bb and therefore needs to become cold. Therefore,
1419 : its preds will no longer be region crossing. Any non-dominating
1420 : preds that were previously hot would also have become cold
1421 : in the caller for the same region. Any preds that were previously
1422 : region-crossing will be adjusted in fixup_partition_crossing. */
1423 654 : FOR_EACH_EDGE (e, ei, bb->preds)
1424 : {
1425 334 : fixup_partition_crossing (e);
1426 : }
1427 :
1428 : /* Possibly need to make bb's successor edges region crossing,
1429 : or remove stale region crossing. */
1430 655 : FOR_EACH_EDGE (e, ei, bb->succs)
1431 : {
1432 : /* We can't have fall-through edges across partition boundaries.
1433 : Note that force_nonfallthru will do any necessary partition
1434 : boundary fixup by calling fixup_partition_crossing itself. */
1435 335 : if ((e->flags & EDGE_FALLTHRU)
1436 294 : && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1437 270 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1438 0 : force_nonfallthru (e);
1439 : else
1440 335 : fixup_partition_crossing (e);
1441 : }
1442 320 : }
1443 :
1444 : /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1445 : expense of adding new instructions or reordering basic blocks.
1446 :
1447 : Function can be also called with edge destination equivalent to the TARGET.
1448 : Then it should try the simplifications and do nothing if none is possible.
1449 :
1450 : Return edge representing the branch if transformation succeeded. Return NULL
1451 : on failure.
1452 : We still return NULL in case E already destinated TARGET and we didn't
1453 : managed to simplify instruction stream. */
1454 :
1455 : static edge
1456 9889332 : rtl_redirect_edge_and_branch (edge e, basic_block target)
1457 : {
1458 9889332 : edge ret;
1459 9889332 : basic_block src = e->src;
1460 9889332 : basic_block dest = e->dest;
1461 :
1462 9889332 : if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1463 : return NULL;
1464 :
1465 9889332 : if (dest == target)
1466 : return e;
1467 :
1468 9889327 : if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1469 : {
1470 479407 : df_set_bb_dirty (src);
1471 479407 : fixup_partition_crossing (ret);
1472 479407 : return ret;
1473 : }
1474 :
1475 9409920 : ret = redirect_branch_edge (e, target);
1476 9409920 : if (!ret)
1477 : return NULL;
1478 :
1479 1640130 : df_set_bb_dirty (src);
1480 1640130 : fixup_partition_crossing (ret);
1481 1640130 : return ret;
1482 : }
1483 :
1484 : /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1485 :
1486 : void
1487 5312373 : emit_barrier_after_bb (basic_block bb)
1488 : {
1489 5312373 : rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1490 5312373 : gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1491 : || current_ir_type () == IR_RTL_CFGLAYOUT);
1492 5312373 : if (current_ir_type () == IR_RTL_CFGLAYOUT)
1493 : {
1494 76637 : rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1495 :
1496 76637 : if (BB_FOOTER (bb))
1497 : {
1498 : rtx_insn *footer_tail = BB_FOOTER (bb);
1499 :
1500 2880 : while (NEXT_INSN (footer_tail))
1501 : footer_tail = NEXT_INSN (footer_tail);
1502 2880 : if (!BARRIER_P (footer_tail))
1503 : {
1504 0 : SET_NEXT_INSN (footer_tail) = insn;
1505 0 : SET_PREV_INSN (insn) = footer_tail;
1506 : }
1507 : }
1508 : else
1509 73757 : BB_FOOTER (bb) = insn;
1510 : }
1511 5312373 : }
1512 :
1513 : /* Like force_nonfallthru below, but additionally performs redirection
1514 : Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1515 : when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1516 : simple_return_rtx, indicating which kind of returnjump to create.
1517 : It should be NULL otherwise. */
1518 :
1519 : basic_block
1520 5174466 : force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1521 : {
1522 5174466 : basic_block jump_block, new_bb = NULL, src = e->src;
1523 5174466 : rtx note;
1524 5174466 : edge new_edge;
1525 5174466 : int abnormal_edge_flags = 0;
1526 5174466 : bool asm_goto_edge = false;
1527 :
1528 : /* In the case the last instruction is conditional jump to the next
1529 : instruction, first redirect the jump itself and then continue
1530 : by creating a basic block afterwards to redirect fallthru edge. */
1531 5174466 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1532 5174459 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1533 5174459 : && any_condjump_p (BB_END (e->src))
1534 5968415 : && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1535 : {
1536 0 : rtx note;
1537 0 : edge b = unchecked_make_edge (e->src, target, 0);
1538 0 : bool redirected;
1539 :
1540 0 : redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1541 0 : block_label (target), 0);
1542 0 : gcc_assert (redirected);
1543 :
1544 0 : note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1545 0 : if (note)
1546 : {
1547 0 : int prob = XINT (note, 0);
1548 :
1549 0 : b->probability = profile_probability::from_reg_br_prob_note (prob);
1550 0 : e->probability -= e->probability;
1551 : }
1552 : }
1553 :
1554 5174466 : if (e->flags & EDGE_ABNORMAL)
1555 : {
1556 : /* Irritating special case - fallthru edge to the same block as abnormal
1557 : edge.
1558 : We can't redirect abnormal edge, but we still can split the fallthru
1559 : one and create separate abnormal edge to original destination.
1560 : This allows bb-reorder to make such edge non-fallthru. */
1561 0 : gcc_assert (e->dest == target);
1562 0 : abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1563 0 : e->flags &= EDGE_FALLTHRU;
1564 : }
1565 : else
1566 : {
1567 5174466 : gcc_assert (e->flags & EDGE_FALLTHRU);
1568 5174466 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1569 : {
1570 : /* We can't redirect the entry block. Create an empty block
1571 : at the start of the function which we use to add the new
1572 : jump. */
1573 7 : edge tmp;
1574 7 : edge_iterator ei;
1575 7 : bool found = false;
1576 :
1577 7 : basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1578 : ENTRY_BLOCK_PTR_FOR_FN (cfun));
1579 7 : bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1580 :
1581 : /* Make sure new block ends up in correct hot/cold section. */
1582 7 : BB_COPY_PARTITION (bb, e->dest);
1583 :
1584 : /* Change the existing edge's source to be the new block, and add
1585 : a new edge from the entry block to the new block. */
1586 7 : e->src = bb;
1587 7 : for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1588 7 : (tmp = ei_safe_edge (ei)); )
1589 : {
1590 7 : if (tmp == e)
1591 : {
1592 7 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1593 7 : found = true;
1594 7 : break;
1595 : }
1596 : else
1597 0 : ei_next (&ei);
1598 : }
1599 :
1600 0 : gcc_assert (found);
1601 :
1602 7 : vec_safe_push (bb->succs, e);
1603 7 : make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1604 : EDGE_FALLTHRU);
1605 : }
1606 : }
1607 :
1608 : /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1609 : don't point to the fallthru label. */
1610 5174466 : if (JUMP_P (BB_END (e->src))
1611 794094 : && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1612 793754 : && (e->flags & EDGE_FALLTHRU)
1613 5968220 : && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1614 : {
1615 145 : int n = ASM_OPERANDS_LABEL_LENGTH (note);
1616 :
1617 261 : for (int i = 0; i < n; ++i)
1618 184 : if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1619 : {
1620 : asm_goto_edge = true;
1621 : break;
1622 : }
1623 : }
1624 :
1625 5174466 : if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1626 : {
1627 985930 : rtx_insn *new_head;
1628 985930 : profile_count count = e->count ();
1629 985930 : profile_probability probability = e->probability;
1630 : /* Create the new structures. */
1631 :
1632 : /* If the old block ended with a tablejump, skip its table
1633 : by searching forward from there. Otherwise start searching
1634 : forward from the last instruction of the old block. */
1635 985930 : rtx_jump_table_data *table;
1636 985930 : if (tablejump_p (BB_END (e->src), NULL, &table))
1637 0 : new_head = table;
1638 : else
1639 985930 : new_head = BB_END (e->src);
1640 985930 : new_head = NEXT_INSN (new_head);
1641 :
1642 985930 : jump_block = create_basic_block (new_head, NULL, e->src);
1643 985930 : jump_block->count = count;
1644 :
1645 : /* Make sure new block ends up in correct hot/cold section. */
1646 :
1647 985930 : BB_COPY_PARTITION (jump_block, e->src);
1648 :
1649 : /* Wire edge in. */
1650 985930 : new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1651 985930 : new_edge->probability = probability;
1652 :
1653 : /* Redirect old edge. */
1654 985930 : redirect_edge_pred (e, jump_block);
1655 985930 : e->probability = profile_probability::always ();
1656 :
1657 : /* If e->src was previously region crossing, it no longer is
1658 : and the reg crossing note should be removed. */
1659 985930 : fixup_partition_crossing (new_edge);
1660 :
1661 : /* If asm goto has any label refs to e->dest, change them to point
1662 : to jump_block instead. */
1663 985930 : if (asm_goto_edge)
1664 : {
1665 68 : int n = ASM_OPERANDS_LABEL_LENGTH (note);
1666 :
1667 174 : for (int i = 0; i < n; ++i)
1668 106 : if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1669 : {
1670 69 : LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1671 69 : XEXP (ASM_OPERANDS_LABEL (note, i), 0)
1672 69 : = block_label (jump_block);
1673 69 : LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1674 : }
1675 :
1676 68 : rtx_insn *insn = BB_END (new_edge->src);
1677 68 : rtx note;
1678 68 : rtx_insn *old_label = BB_HEAD (e->dest);
1679 68 : rtx_insn *new_label = BB_HEAD (jump_block);
1680 :
1681 68 : if (JUMP_LABEL (insn) == old_label)
1682 : {
1683 55 : JUMP_LABEL (insn) = new_label;
1684 55 : note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1685 55 : if (note)
1686 0 : remove_note (insn, note);
1687 : }
1688 : else
1689 : {
1690 13 : note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1691 13 : if (note)
1692 13 : remove_note (insn, note);
1693 13 : if (JUMP_LABEL (insn) != new_label
1694 13 : && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1695 13 : add_reg_note (insn, REG_LABEL_TARGET, new_label);
1696 : }
1697 136 : while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1698 68 : != NULL_RTX)
1699 0 : XEXP (note, 0) = new_label;
1700 : }
1701 :
1702 985930 : new_bb = jump_block;
1703 : }
1704 : else
1705 : jump_block = e->src;
1706 :
1707 5174466 : const location_t loc = e->goto_locus;
1708 5174466 : e->flags &= ~EDGE_FALLTHRU;
1709 5174466 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1710 : {
1711 546 : if (jump_label == ret_rtx)
1712 0 : emit_jump_insn_after_setloc (targetm.gen_return (),
1713 0 : BB_END (jump_block), loc);
1714 : else
1715 : {
1716 546 : gcc_assert (jump_label == simple_return_rtx);
1717 546 : emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1718 546 : BB_END (jump_block), loc);
1719 : }
1720 546 : set_return_jump_label (BB_END (jump_block));
1721 : }
1722 : else
1723 : {
1724 5173920 : rtx_code_label *label = block_label (target);
1725 5173920 : emit_jump_insn_after_setloc (targetm.gen_jump (label),
1726 5173920 : BB_END (jump_block), loc);
1727 5173920 : JUMP_LABEL (BB_END (jump_block)) = label;
1728 5173920 : LABEL_NUSES (label)++;
1729 : }
1730 :
1731 : /* We might be in cfg layout mode, and if so, the following routine will
1732 : insert the barrier correctly. */
1733 5174466 : emit_barrier_after_bb (jump_block);
1734 5174466 : redirect_edge_succ_nodup (e, target);
1735 :
1736 5174466 : if (abnormal_edge_flags)
1737 0 : make_edge (src, target, abnormal_edge_flags);
1738 :
1739 5174466 : df_mark_solutions_dirty ();
1740 5174466 : fixup_partition_crossing (e);
1741 5174466 : return new_bb;
1742 : }
1743 :
1744 : /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1745 : (and possibly create new basic block) to make edge non-fallthru.
1746 : Return newly created BB or NULL if none. */
1747 :
1748 : static basic_block
1749 755259 : rtl_force_nonfallthru (edge e)
1750 : {
1751 755259 : return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1752 : }
1753 :
1754 : /* Redirect edge even at the expense of creating new jump insn or
1755 : basic block. Return new basic block if created, NULL otherwise.
1756 : Conversion must be possible. */
1757 :
1758 : static basic_block
1759 474569 : rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1760 : {
1761 474569 : if (redirect_edge_and_branch (e, target)
1762 474569 : || e->dest == target)
1763 : return NULL;
1764 :
1765 : /* In case the edge redirection failed, try to force it to be non-fallthru
1766 : and redirect newly created simplejump. */
1767 383249 : df_set_bb_dirty (e->src);
1768 383249 : return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1769 : }
1770 :
1771 : /* The given edge should potentially be a fallthru edge. If that is in
1772 : fact true, delete the jump and barriers that are in the way. */
1773 :
1774 : static void
1775 771444 : rtl_tidy_fallthru_edge (edge e)
1776 : {
1777 771444 : rtx_insn *q;
1778 771444 : basic_block b = e->src, c = b->next_bb;
1779 :
1780 : /* ??? In a late-running flow pass, other folks may have deleted basic
1781 : blocks by nopping out blocks, leaving multiple BARRIERs between here
1782 : and the target label. They ought to be chastised and fixed.
1783 :
1784 : We can also wind up with a sequence of undeletable labels between
1785 : one block and the next.
1786 :
1787 : So search through a sequence of barriers, labels, and notes for
1788 : the head of block C and assert that we really do fall through. */
1789 :
1790 1567451 : for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1791 24563 : if (NONDEBUG_INSN_P (q))
1792 : return;
1793 :
1794 : /* Remove what will soon cease being the jump insn from the source block.
1795 : If block B consisted only of this single jump, turn it into a deleted
1796 : note. */
1797 771444 : q = BB_END (b);
1798 771444 : if (JUMP_P (q)
1799 31163 : && onlyjump_p (q)
1800 802595 : && (any_uncondjump_p (q)
1801 7338 : || single_succ_p (b)))
1802 : {
1803 24149 : rtx_insn *label;
1804 24149 : rtx_jump_table_data *table;
1805 :
1806 24149 : if (tablejump_p (q, &label, &table))
1807 : {
1808 : /* The label is likely mentioned in some instruction before
1809 : the tablejump and might not be DCEd, so turn it into
1810 : a note instead and move before the tablejump that is going to
1811 : be deleted. */
1812 0 : const char *name = LABEL_NAME (label);
1813 0 : PUT_CODE (label, NOTE);
1814 0 : NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1815 0 : NOTE_DELETED_LABEL_NAME (label) = name;
1816 0 : reorder_insns (label, label, PREV_INSN (q));
1817 0 : delete_insn (table);
1818 : }
1819 :
1820 24149 : q = PREV_INSN (q);
1821 : }
1822 : /* Unconditional jumps with side-effects (i.e. which we can't just delete
1823 : together with the barrier) should never have a fallthru edge. */
1824 747295 : else if (JUMP_P (q) && any_uncondjump_p (q))
1825 : return;
1826 :
1827 : /* Selectively unlink the sequence. */
1828 771444 : if (q != PREV_INSN (BB_HEAD (c)))
1829 24471 : delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1830 :
1831 771444 : e->flags |= EDGE_FALLTHRU;
1832 : }
1833 :
1834 : /* Should move basic block BB after basic block AFTER. NIY. */
1835 :
1836 : static bool
1837 705740 : rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1838 : basic_block after ATTRIBUTE_UNUSED)
1839 : {
1840 705740 : return false;
1841 : }
1842 :
1843 : /* Locate the last bb in the same partition as START_BB. */
1844 :
1845 : static basic_block
1846 34165 : last_bb_in_partition (basic_block start_bb)
1847 : {
1848 34165 : basic_block bb;
1849 22390829 : FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1850 : {
1851 22390829 : if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1852 : return bb;
1853 : }
1854 : /* Return bb before the exit block. */
1855 0 : return bb->prev_bb;
1856 : }
1857 :
1858 : /* Split a (typically critical) edge. Return the new block.
1859 : The edge must not be abnormal.
1860 :
1861 : ??? The code generally expects to be called on critical edges.
1862 : The case of a block ending in an unconditional jump to a
1863 : block with multiple predecessors is not handled optimally. */
1864 :
1865 : static basic_block
1866 1183965 : rtl_split_edge (edge edge_in)
1867 : {
1868 1183965 : basic_block bb, new_bb;
1869 1183965 : rtx_insn *before;
1870 :
1871 : /* Abnormal edges cannot be split. */
1872 1183965 : gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1873 :
1874 : /* We are going to place the new block in front of edge destination.
1875 : Avoid existence of fallthru predecessors. */
1876 1183965 : if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1877 : {
1878 670970 : edge e = find_fallthru_edge (edge_in->dest->preds);
1879 :
1880 670970 : if (e)
1881 509579 : force_nonfallthru (e);
1882 : }
1883 :
1884 : /* Create the basic block note. */
1885 1183965 : if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1886 940932 : before = BB_HEAD (edge_in->dest);
1887 : else
1888 : before = NULL;
1889 :
1890 : /* If this is a fall through edge to the exit block, the blocks might be
1891 : not adjacent, and the right place is after the source. */
1892 1183965 : if ((edge_in->flags & EDGE_FALLTHRU)
1893 512995 : && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1894 : {
1895 243033 : before = NEXT_INSN (BB_END (edge_in->src));
1896 243033 : bb = create_basic_block (before, NULL, edge_in->src);
1897 243033 : BB_COPY_PARTITION (bb, edge_in->src);
1898 243033 : }
1899 : else
1900 : {
1901 940932 : if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1902 : {
1903 77301 : bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1904 77301 : BB_COPY_PARTITION (bb, edge_in->dest);
1905 : }
1906 : else
1907 : {
1908 863631 : basic_block after = edge_in->dest->prev_bb;
1909 : /* If this is post-bb reordering, and the edge crosses a partition
1910 : boundary, the new block needs to be inserted in the bb chain
1911 : at the end of the src partition (since we put the new bb into
1912 : that partition, see below). Otherwise we may end up creating
1913 : an extra partition crossing in the chain, which is illegal.
1914 : It can't go after the src, because src may have a fall-through
1915 : to a different block. */
1916 863631 : if (crtl->bb_reorder_complete
1917 62009 : && (edge_in->flags & EDGE_CROSSING))
1918 : {
1919 34165 : after = last_bb_in_partition (edge_in->src);
1920 34165 : before = get_last_bb_insn (after);
1921 : /* The instruction following the last bb in partition should
1922 : be a barrier, since it cannot end in a fall-through. */
1923 34165 : gcc_checking_assert (BARRIER_P (before));
1924 34165 : before = NEXT_INSN (before);
1925 : }
1926 863631 : bb = create_basic_block (before, NULL, after);
1927 : /* Put the split bb into the src partition, to avoid creating
1928 : a situation where a cold bb dominates a hot bb, in the case
1929 : where src is cold and dest is hot. The src will dominate
1930 : the new bb (whereas it might not have dominated dest). */
1931 863631 : BB_COPY_PARTITION (bb, edge_in->src);
1932 : }
1933 : }
1934 :
1935 1183965 : make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1936 :
1937 : /* Can't allow a region crossing edge to be fallthrough. */
1938 1183965 : if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1939 71772 : && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1940 : {
1941 41179 : new_bb = force_nonfallthru (single_succ_edge (bb));
1942 41179 : gcc_assert (!new_bb);
1943 : }
1944 :
1945 : /* For non-fallthru edges, we must adjust the predecessor's
1946 : jump instruction to target our new block. */
1947 1183965 : if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1948 : {
1949 670970 : edge redirected = redirect_edge_and_branch (edge_in, bb);
1950 670970 : gcc_assert (redirected);
1951 : }
1952 : else
1953 : {
1954 512995 : if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1955 : {
1956 : /* For asm goto even splitting of fallthru edge might
1957 : need insn patching, as other labels might point to the
1958 : old label. */
1959 435694 : rtx_insn *last = BB_END (edge_in->src);
1960 435694 : if (last
1961 435694 : && JUMP_P (last)
1962 207106 : && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1963 182874 : && (extract_asm_operands (PATTERN (last))
1964 182872 : || JUMP_LABEL (last) == before)
1965 435696 : && patch_jump_insn (last, before, bb))
1966 2 : df_set_bb_dirty (edge_in->src);
1967 : }
1968 512995 : redirect_edge_succ (edge_in, bb);
1969 : }
1970 :
1971 1183965 : return bb;
1972 : }
1973 :
1974 : /* Queue instructions for insertion on an edge between two basic blocks.
1975 : The new instructions and basic blocks (if any) will not appear in the
1976 : CFG until commit_edge_insertions is called. If there are already
1977 : queued instructions on the edge, PATTERN is appended to them. */
1978 :
1979 : void
1980 5645821 : insert_insn_on_edge (rtx pattern, edge e)
1981 : {
1982 : /* We cannot insert instructions on an abnormal critical edge.
1983 : It will be easier to find the culprit if we die now. */
1984 5645821 : gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1985 :
1986 5645821 : if (e->insns.r == NULL_RTX)
1987 4777597 : start_sequence ();
1988 : else
1989 868224 : push_to_sequence (e->insns.r);
1990 :
1991 5645821 : emit_insn (pattern);
1992 :
1993 5645821 : e->insns.r = end_sequence ();
1994 5645821 : }
1995 :
1996 : /* Like insert_insn_on_edge, but if there are already queued instructions
1997 : on the edge, PATTERN is prepended to them. */
1998 :
1999 : void
2000 335 : prepend_insn_to_edge (rtx pattern, edge e)
2001 : {
2002 : /* We cannot insert instructions on an abnormal critical edge.
2003 : It will be easier to find the culprit if we die now. */
2004 335 : gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
2005 :
2006 335 : start_sequence ();
2007 :
2008 335 : emit_insn (pattern);
2009 335 : emit_insn (e->insns.r);
2010 :
2011 335 : e->insns.r = end_sequence ();
2012 335 : }
2013 :
2014 : /* Update the CFG for the instructions queued on edge E. */
2015 :
2016 : void
2017 4743252 : commit_one_edge_insertion (edge e)
2018 : {
2019 4743252 : rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
2020 4743252 : basic_block bb;
2021 :
2022 : /* Pull the insns off the edge now since the edge might go away. */
2023 4743252 : insns = e->insns.r;
2024 4743252 : e->insns.r = NULL;
2025 :
2026 : /* Allow the sequence to contain internal jumps, such as a memcpy loop
2027 : or an allocation loop. If such a sequence is emitted during RTL
2028 : expansion, we'll create the appropriate basic blocks later,
2029 : at the end of the pass. But if such a sequence is emitted after
2030 : initial expansion, we'll need to find the subblocks ourselves. */
2031 4743252 : bool contains_jump = false;
2032 4743252 : if (!currently_expanding_to_rtl)
2033 13559558 : for (rtx_insn *insn = insns; insn; insn = NEXT_INSN (insn))
2034 11623920 : if (JUMP_P (insn))
2035 : {
2036 1611693 : rebuild_jump_labels_chain (insns);
2037 1611693 : contains_jump = true;
2038 1611693 : break;
2039 : }
2040 :
2041 : /* Figure out where to put these insns. If the destination has
2042 : one predecessor, insert there. Except for the exit block. */
2043 4743252 : if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2044 : {
2045 1611952 : bb = e->dest;
2046 :
2047 : /* Get the location correct wrt a code label, and "nice" wrt
2048 : a basic block note, and before everything else. */
2049 1611952 : tmp = BB_HEAD (bb);
2050 1611952 : if (LABEL_P (tmp))
2051 77267 : tmp = NEXT_INSN (tmp);
2052 1611952 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2053 1611952 : tmp = NEXT_INSN (tmp);
2054 1611952 : if (tmp == BB_HEAD (bb))
2055 : before = tmp;
2056 1611952 : else if (tmp)
2057 1611952 : after = PREV_INSN (tmp);
2058 : else
2059 0 : after = get_last_insn ();
2060 : }
2061 :
2062 : /* If the source has one successor and the edge is not abnormal,
2063 : insert there. Except for the entry block.
2064 : Don't do this if the predecessor ends in a jump other than
2065 : unconditional simple jump. E.g. for asm goto that points all
2066 : its labels at the fallthru basic block, we can't insert instructions
2067 : before the asm goto, as the asm goto can have various of side effects,
2068 : and can't emit instructions after the asm goto, as it must end
2069 : the basic block. */
2070 3131300 : else if ((e->flags & EDGE_ABNORMAL) == 0
2071 3131300 : && single_succ_p (e->src)
2072 2237542 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2073 5367361 : && (!JUMP_P (BB_END (e->src))
2074 346419 : || simplejump_p (BB_END (e->src))))
2075 : {
2076 2236061 : bb = e->src;
2077 :
2078 : /* It is possible to have a non-simple jump here. Consider a target
2079 : where some forms of unconditional jumps clobber a register. This
2080 : happens on the fr30 for example.
2081 :
2082 : We know this block has a single successor, so we can just emit
2083 : the queued insns before the jump. */
2084 2236061 : if (JUMP_P (BB_END (bb)))
2085 : before = BB_END (bb);
2086 : else
2087 : {
2088 : /* We'd better be fallthru, or we've lost track of what's what. */
2089 1889642 : gcc_assert (e->flags & EDGE_FALLTHRU);
2090 :
2091 : after = BB_END (bb);
2092 : }
2093 : }
2094 :
2095 : /* Otherwise we must split the edge. */
2096 : else
2097 : {
2098 895239 : bb = split_edge (e);
2099 :
2100 : /* If E crossed a partition boundary, we needed to make bb end in
2101 : a region-crossing jump, even though it was originally fallthru. */
2102 895239 : if (JUMP_P (BB_END (bb)))
2103 : before = BB_END (bb);
2104 : else
2105 : after = BB_END (bb);
2106 : }
2107 :
2108 : /* Now that we've found the spot, do the insertion. */
2109 1611952 : if (before)
2110 : {
2111 387598 : emit_insn_before_noloc (insns, before, bb);
2112 387598 : last = prev_nonnote_insn (before);
2113 : }
2114 : else
2115 4355654 : last = emit_insn_after_noloc (insns, after, bb);
2116 :
2117 4743252 : if (returnjump_p (last))
2118 : {
2119 : /* ??? Remove all outgoing edges from BB and add one for EXIT.
2120 : This is not currently a problem because this only happens
2121 : for the (single) epilogue, which already has a fallthru edge
2122 : to EXIT. */
2123 :
2124 1351654 : e = single_succ_edge (bb);
2125 2703308 : gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2126 : && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2127 :
2128 1351654 : e->flags &= ~EDGE_FALLTHRU;
2129 1351654 : emit_barrier_after (last);
2130 :
2131 1351654 : if (before)
2132 0 : delete_insn (before);
2133 : }
2134 : else
2135 : /* Sequences inserted after RTL expansion are expected to be SESE,
2136 : with only internal branches allowed. If the sequence jumps outside
2137 : itself then we do not know how to add the associated edges here. */
2138 3391598 : gcc_assert (!JUMP_P (last) || currently_expanding_to_rtl);
2139 :
2140 4743252 : if (contains_jump)
2141 1611693 : find_sub_basic_blocks (bb);
2142 4743252 : }
2143 :
2144 : /* Update the CFG for all queued instructions. */
2145 :
2146 : void
2147 4561925 : commit_edge_insertions (void)
2148 : {
2149 4561925 : basic_block bb;
2150 :
2151 : /* Optimization passes that invoke this routine can cause hot blocks
2152 : previously reached by both hot and cold blocks to become dominated only
2153 : by cold blocks. This will cause the verification below to fail,
2154 : and lead to now cold code in the hot section. In some cases this
2155 : may only be visible after newly unreachable blocks are deleted,
2156 : which will be done by fixup_partitions. */
2157 4561925 : fixup_partitions ();
2158 :
2159 4561925 : if (!currently_expanding_to_rtl)
2160 3079664 : checking_verify_flow_info ();
2161 :
2162 66806309 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2163 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2164 : {
2165 62244384 : edge e;
2166 62244384 : edge_iterator ei;
2167 :
2168 148709892 : FOR_EACH_EDGE (e, ei, bb->succs)
2169 86465508 : if (e->insns.r)
2170 : {
2171 4702791 : if (currently_expanding_to_rtl)
2172 1195921 : rebuild_jump_labels_chain (e->insns.r);
2173 4702791 : commit_one_edge_insertion (e);
2174 : }
2175 : }
2176 4561925 : }
2177 :
2178 :
2179 : /* Print out RTL-specific basic block information (live information
2180 : at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2181 : documented in dumpfile.h. */
2182 :
2183 : static void
2184 2713 : rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2185 : {
2186 2713 : char *s_indent;
2187 :
2188 2713 : s_indent = (char *) alloca ((size_t) indent + 1);
2189 2713 : memset (s_indent, ' ', (size_t) indent);
2190 2713 : s_indent[indent] = '\0';
2191 :
2192 2713 : if (df && (flags & TDF_DETAILS))
2193 : {
2194 728 : df_dump_top (bb, outf);
2195 728 : putc ('\n', outf);
2196 : }
2197 :
2198 2713 : if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK
2199 2713 : && rtl_bb_info_initialized_p (bb))
2200 : {
2201 2137 : rtx_insn *last = BB_END (bb);
2202 2137 : if (last)
2203 2137 : last = NEXT_INSN (last);
2204 15607 : for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2205 : {
2206 13470 : if (flags & TDF_DETAILS)
2207 4176 : df_dump_insn_top (insn, outf);
2208 13470 : if (! (flags & TDF_SLIM))
2209 13438 : print_rtl_single (outf, insn);
2210 : else
2211 32 : dump_insn_slim (outf, insn);
2212 13470 : if (flags & TDF_DETAILS)
2213 4176 : df_dump_insn_bottom (insn, outf);
2214 : }
2215 : }
2216 :
2217 2713 : if (df && (flags & TDF_DETAILS))
2218 : {
2219 728 : df_dump_bottom (bb, outf);
2220 728 : putc ('\n', outf);
2221 : }
2222 :
2223 2713 : }
2224 :
2225 : /* Like dump_function_to_file, but for RTL. Print out dataflow information
2226 : for the start of each basic block. FLAGS are the TDF_* masks documented
2227 : in dumpfile.h. */
2228 :
2229 : void
2230 4219 : print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2231 : {
2232 4219 : const rtx_insn *tmp_rtx;
2233 4219 : if (rtx_first == 0)
2234 0 : fprintf (outf, "(nil)\n");
2235 : else
2236 : {
2237 4219 : enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2238 4219 : int max_uid = get_max_uid ();
2239 4219 : basic_block *start = XCNEWVEC (basic_block, max_uid);
2240 4219 : basic_block *end = XCNEWVEC (basic_block, max_uid);
2241 4219 : enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2242 4219 : basic_block bb;
2243 :
2244 : /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2245 : insns, but the CFG is not maintained so the basic block info
2246 : is not reliable. Therefore it's omitted from the dumps. */
2247 4219 : if (! (cfun->curr_properties & PROP_cfg))
2248 986 : flags &= ~TDF_BLOCKS;
2249 :
2250 4219 : if (df)
2251 3321 : df_dump_start (outf);
2252 :
2253 4219 : if (cfun->curr_properties & PROP_cfg)
2254 : {
2255 21760 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2256 : {
2257 18527 : rtx_insn *x;
2258 :
2259 18527 : start[INSN_UID (BB_HEAD (bb))] = bb;
2260 18527 : end[INSN_UID (BB_END (bb))] = bb;
2261 18527 : if (flags & TDF_BLOCKS)
2262 : {
2263 5321 : for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2264 : {
2265 5321 : enum bb_state state = IN_MULTIPLE_BB;
2266 :
2267 5321 : if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2268 5321 : state = IN_ONE_BB;
2269 5321 : in_bb_p[INSN_UID (x)] = state;
2270 :
2271 5321 : if (x == BB_END (bb))
2272 : break;
2273 : }
2274 : }
2275 : }
2276 : }
2277 :
2278 163311 : for (tmp_rtx = rtx_first; tmp_rtx != NULL; tmp_rtx = NEXT_INSN (tmp_rtx))
2279 : {
2280 159092 : if (flags & TDF_BLOCKS)
2281 : {
2282 6112 : bb = start[INSN_UID (tmp_rtx)];
2283 6112 : if (bb != NULL)
2284 : {
2285 882 : dump_bb_info (outf, bb, 0, dump_flags, true, false);
2286 882 : if (df && (flags & TDF_DETAILS))
2287 582 : df_dump_top (bb, outf);
2288 : }
2289 :
2290 6112 : if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2291 791 : && !NOTE_P (tmp_rtx)
2292 6324 : && !BARRIER_P (tmp_rtx))
2293 0 : fprintf (outf, ";; Insn is not within a basic block\n");
2294 6112 : else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2295 0 : fprintf (outf, ";; Insn is in multiple basic blocks\n");
2296 : }
2297 :
2298 159092 : if (flags & TDF_DETAILS)
2299 16360 : df_dump_insn_top (tmp_rtx, outf);
2300 159092 : if (! (flags & TDF_SLIM))
2301 158556 : print_rtl_single (outf, tmp_rtx);
2302 : else
2303 536 : dump_insn_slim (outf, tmp_rtx);
2304 159092 : if (flags & TDF_DETAILS)
2305 16360 : df_dump_insn_bottom (tmp_rtx, outf);
2306 :
2307 159092 : bb = end[INSN_UID (tmp_rtx)];
2308 159092 : if (bb != NULL)
2309 : {
2310 18527 : if (flags & TDF_BLOCKS)
2311 : {
2312 882 : dump_bb_info (outf, bb, 0, dump_flags, false, true);
2313 882 : if (df && (flags & TDF_DETAILS))
2314 582 : df_dump_bottom (bb, outf);
2315 882 : putc ('\n', outf);
2316 : }
2317 : /* Emit a hint if the fallthrough target of current basic block
2318 : isn't the one placed right next. */
2319 176681 : else if (EDGE_COUNT (bb->succs) > 0)
2320 : {
2321 17589 : gcc_assert (BB_END (bb) == tmp_rtx);
2322 17589 : const rtx_insn *ninsn = NEXT_INSN (tmp_rtx);
2323 : /* Bypass intervening deleted-insn notes and debug insns. */
2324 17589 : while (ninsn
2325 18873 : && !NONDEBUG_INSN_P (ninsn)
2326 40469 : && !start[INSN_UID (ninsn)])
2327 4007 : ninsn = NEXT_INSN (ninsn);
2328 17589 : edge e = find_fallthru_edge (bb->succs);
2329 17589 : if (e && ninsn)
2330 : {
2331 12851 : basic_block dest = e->dest;
2332 12851 : if (start[INSN_UID (ninsn)] != dest)
2333 2159 : fprintf (outf, "%s ; pc falls through to BB %d\n",
2334 : print_rtx_head, dest->index);
2335 : }
2336 : }
2337 : }
2338 : }
2339 :
2340 4219 : free (start);
2341 4219 : free (end);
2342 4219 : free (in_bb_p);
2343 : }
2344 4219 : }
2345 :
2346 : /* Update the branch probability of BB if a REG_BR_PROB is present. */
2347 :
2348 : void
2349 9625501 : update_br_prob_note (basic_block bb)
2350 : {
2351 9625501 : rtx note;
2352 9625501 : note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2353 9625501 : if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2354 : {
2355 244732 : if (note)
2356 : {
2357 3 : rtx *note_link, this_rtx;
2358 :
2359 3 : note_link = ®_NOTES (BB_END (bb));
2360 6 : for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1))
2361 6 : if (this_rtx == note)
2362 : {
2363 3 : *note_link = XEXP (this_rtx, 1);
2364 3 : break;
2365 : }
2366 : }
2367 244732 : return;
2368 : }
2369 9380769 : if (!note
2370 9380769 : || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2371 : return;
2372 210562 : XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2373 : }
2374 :
2375 : /* Get the last insn associated with block BB (that includes barriers and
2376 : tablejumps after BB). */
2377 : rtx_insn *
2378 6687365 : get_last_bb_insn (basic_block bb)
2379 : {
2380 6687365 : rtx_jump_table_data *table;
2381 6687365 : rtx_insn *tmp;
2382 6687365 : rtx_insn *end = BB_END (bb);
2383 :
2384 : /* Include any jump table following the basic block. */
2385 6687365 : if (tablejump_p (end, NULL, &table))
2386 5 : end = table;
2387 :
2388 : /* Include any barriers that may follow the basic block. */
2389 6687365 : tmp = next_nonnote_nondebug_insn_bb (end);
2390 13942175 : while (tmp && BARRIER_P (tmp))
2391 : {
2392 567445 : end = tmp;
2393 567445 : tmp = next_nonnote_nondebug_insn_bb (end);
2394 : }
2395 :
2396 6687365 : return end;
2397 : }
2398 :
2399 : /* Add all BBs reachable from entry via hot paths into the SET. */
2400 :
2401 : void
2402 565229 : find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2403 : {
2404 565229 : auto_vec<basic_block, 64> worklist;
2405 :
2406 565229 : set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2407 565229 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2408 :
2409 20592686 : while (worklist.length () > 0)
2410 : {
2411 19462228 : basic_block bb = worklist.pop ();
2412 19462228 : edge_iterator ei;
2413 19462228 : edge e;
2414 :
2415 49457913 : FOR_EACH_EDGE (e, ei, bb->succs)
2416 29995685 : if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2417 29995685 : && !set->add (e->dest))
2418 18896999 : worklist.safe_push (e->dest);
2419 : }
2420 565229 : }
2421 :
2422 : /* Sanity check partition hotness to ensure that basic blocks in
2423 : Â the cold partition don't dominate basic blocks in the hot partition.
2424 : If FLAG_ONLY is true, report violations as errors. Otherwise
2425 : re-mark the dominated blocks as cold, since this is run after
2426 : cfg optimizations that may make hot blocks previously reached
2427 : by both hot and cold blocks now only reachable along cold paths. */
2428 :
2429 : static auto_vec<basic_block>
2430 500120 : find_partition_fixes (bool flag_only)
2431 : {
2432 500120 : basic_block bb;
2433 500120 : auto_vec<basic_block> bbs_to_fix;
2434 500120 : hash_set<basic_block> set;
2435 :
2436 : /* Callers check this. */
2437 500120 : gcc_checking_assert (crtl->has_bb_partition);
2438 :
2439 500120 : find_bbs_reachable_by_hot_paths (&set);
2440 :
2441 19365181 : FOR_EACH_BB_FN (bb, cfun)
2442 18865061 : if (!set.contains (bb)
2443 18865061 : && BB_PARTITION (bb) != BB_COLD_PARTITION)
2444 : {
2445 320 : if (flag_only)
2446 0 : error ("non-cold basic block %d reachable only "
2447 : "by paths crossing the cold partition", bb->index);
2448 : else
2449 320 : BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2450 320 : bbs_to_fix.safe_push (bb);
2451 : }
2452 :
2453 500120 : return bbs_to_fix;
2454 500120 : }
2455 :
2456 : /* Perform cleanup on the hot/cold bb partitioning after optimization
2457 : passes that modify the cfg. */
2458 :
2459 : void
2460 12869973 : fixup_partitions (void)
2461 : {
2462 12869973 : if (!crtl->has_bb_partition)
2463 12493816 : return;
2464 :
2465 : /* Delete any blocks that became unreachable and weren't
2466 : already cleaned up, for example during edge forwarding
2467 : and convert_jumps_to_returns. This will expose more
2468 : opportunities for fixing the partition boundaries here.
2469 : Also, the calculation of the dominance graph during verification
2470 : will assert if there are unreachable nodes. */
2471 376157 : delete_unreachable_blocks ();
2472 :
2473 : /* If there are partitions, do a sanity check on them: A basic block in
2474 : Â a cold partition cannot dominate a basic block in a hot partition.
2475 : Fixup any that now violate this requirement, as a result of edge
2476 : forwarding and unreachable block deletion. Â */
2477 376157 : auto_vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2478 :
2479 : /* Do the partition fixup after all necessary blocks have been converted to
2480 : cold, so that we only update the region crossings the minimum number of
2481 : places, which can require forcing edges to be non fallthru. */
2482 376438 : if (! bbs_to_fix.is_empty ())
2483 : {
2484 320 : do
2485 : {
2486 320 : basic_block bb = bbs_to_fix.pop ();
2487 320 : fixup_new_cold_bb (bb);
2488 : }
2489 601 : while (! bbs_to_fix.is_empty ());
2490 :
2491 : /* Fix up hot cold block grouping if needed. */
2492 281 : if (crtl->bb_reorder_complete && current_ir_type () == IR_RTL_CFGRTL)
2493 : {
2494 1 : basic_block bb, first = NULL, second = NULL;
2495 1 : int current_partition = BB_UNPARTITIONED;
2496 :
2497 16 : FOR_EACH_BB_FN (bb, cfun)
2498 : {
2499 15 : if (current_partition != BB_UNPARTITIONED
2500 14 : && BB_PARTITION (bb) != current_partition)
2501 : {
2502 3 : if (first == NULL)
2503 : first = bb;
2504 2 : else if (second == NULL)
2505 : second = bb;
2506 : else
2507 : {
2508 : /* If we switch partitions for the 3rd, 5th etc. time,
2509 : move bbs first (inclusive) .. second (exclusive) right
2510 : before bb. */
2511 1 : basic_block prev_first = first->prev_bb;
2512 1 : basic_block prev_second = second->prev_bb;
2513 1 : basic_block prev_bb = bb->prev_bb;
2514 1 : prev_first->next_bb = second;
2515 1 : second->prev_bb = prev_first;
2516 1 : prev_second->next_bb = bb;
2517 1 : bb->prev_bb = prev_second;
2518 1 : prev_bb->next_bb = first;
2519 1 : first->prev_bb = prev_bb;
2520 1 : rtx_insn *prev_first_insn = PREV_INSN (BB_HEAD (first));
2521 1 : rtx_insn *prev_second_insn
2522 1 : = PREV_INSN (BB_HEAD (second));
2523 1 : rtx_insn *prev_bb_insn = PREV_INSN (BB_HEAD (bb));
2524 1 : SET_NEXT_INSN (prev_first_insn) = BB_HEAD (second);
2525 1 : SET_PREV_INSN (BB_HEAD (second)) = prev_first_insn;
2526 1 : SET_NEXT_INSN (prev_second_insn) = BB_HEAD (bb);
2527 1 : SET_PREV_INSN (BB_HEAD (bb)) = prev_second_insn;
2528 1 : SET_NEXT_INSN (prev_bb_insn) = BB_HEAD (first);
2529 1 : SET_PREV_INSN (BB_HEAD (first)) = prev_bb_insn;
2530 1 : second = NULL;
2531 : }
2532 : }
2533 15 : current_partition = BB_PARTITION (bb);
2534 : }
2535 1 : gcc_assert (!second);
2536 : }
2537 : }
2538 376157 : }
2539 :
2540 : /* Verify, in the basic block chain, that there is at most one switch
2541 : between hot/cold partitions. This condition will not be true until
2542 : after reorder_basic_blocks is called. */
2543 :
2544 : static bool
2545 62948868 : verify_hot_cold_block_grouping (void)
2546 : {
2547 62948868 : basic_block bb;
2548 62948868 : bool err = false;
2549 62948868 : bool switched_sections = false;
2550 62948868 : int current_partition = BB_UNPARTITIONED;
2551 :
2552 : /* Even after bb reordering is complete, we go into cfglayout mode
2553 : again (in compgoto). Ensure we don't call this before going back
2554 : into linearized RTL when any layout fixes would have been committed. */
2555 62948868 : if (!crtl->bb_reorder_complete
2556 62948868 : || current_ir_type () != IR_RTL_CFGRTL)
2557 55631460 : return err;
2558 :
2559 129312014 : FOR_EACH_BB_FN (bb, cfun)
2560 : {
2561 121994606 : if (current_partition != BB_UNPARTITIONED
2562 51588222 : && BB_PARTITION (bb) != current_partition)
2563 : {
2564 734352 : if (switched_sections)
2565 : {
2566 0 : error ("multiple hot/cold transitions found (bb %i)",
2567 : bb->index);
2568 0 : err = true;
2569 : }
2570 : else
2571 : switched_sections = true;
2572 :
2573 734352 : if (!crtl->has_bb_partition)
2574 0 : error ("partition found but function partition flag not set");
2575 : }
2576 121994606 : current_partition = BB_PARTITION (bb);
2577 : }
2578 :
2579 : return err;
2580 : }
2581 :
2582 :
2583 : /* Perform several checks on the edges out of each block, such as
2584 : the consistency of the branch probabilities, the correctness
2585 : of hot/cold partition crossing edges, and the number of expected
2586 : successor edges. Also verify that the dominance relationship
2587 : between hot/cold blocks is sane. */
2588 :
2589 : static bool
2590 99415211 : rtl_verify_edges (void)
2591 : {
2592 99415211 : bool err = false;
2593 99415211 : basic_block bb;
2594 :
2595 1173910299 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2596 : {
2597 1074495088 : int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2598 1074495088 : int n_eh = 0, n_abnormal = 0;
2599 1074495088 : edge e, fallthru = NULL;
2600 1074495088 : edge_iterator ei;
2601 1074495088 : rtx note;
2602 1074495088 : bool has_crossing_edge = false;
2603 :
2604 1074495088 : if (JUMP_P (BB_END (bb))
2605 631646882 : && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2606 435521261 : && EDGE_COUNT (bb->succs) >= 2
2607 1510016349 : && any_condjump_p (BB_END (bb)))
2608 : {
2609 435521261 : if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2610 : {
2611 306381 : if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2612 : {
2613 0 : error ("verify_flow_info: "
2614 : "REG_BR_PROB is set but cfg probability is not");
2615 0 : err = true;
2616 : }
2617 : }
2618 435214880 : else if (XINT (note, 0)
2619 435214880 : != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2620 435214880 : && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2621 : {
2622 0 : error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2623 : XINT (note, 0),
2624 0 : BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2625 0 : err = true;
2626 : }
2627 : }
2628 :
2629 2638864580 : FOR_EACH_EDGE (e, ei, bb->succs)
2630 : {
2631 1564369492 : bool is_crossing;
2632 :
2633 1564369492 : if (e->flags & EDGE_FALLTHRU)
2634 855347950 : n_fallthru++, fallthru = e;
2635 :
2636 3128738984 : is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2637 36502150 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2638 1600871642 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2639 1564369492 : has_crossing_edge |= is_crossing;
2640 1564369492 : if (e->flags & EDGE_CROSSING)
2641 : {
2642 20591705 : if (!is_crossing)
2643 : {
2644 0 : error ("EDGE_CROSSING incorrectly set across same section");
2645 0 : err = true;
2646 : }
2647 20591705 : if (e->flags & EDGE_FALLTHRU)
2648 : {
2649 0 : error ("fallthru edge crosses section boundary in bb %i",
2650 0 : e->src->index);
2651 0 : err = true;
2652 : }
2653 20591705 : if (e->flags & EDGE_EH)
2654 : {
2655 0 : error ("EH edge crosses section boundary in bb %i",
2656 0 : e->src->index);
2657 0 : err = true;
2658 : }
2659 20591705 : if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2660 : {
2661 0 : error ("No region crossing jump at section boundary in bb %i",
2662 : bb->index);
2663 0 : err = true;
2664 : }
2665 : }
2666 1543777787 : else if (is_crossing)
2667 : {
2668 0 : error ("EDGE_CROSSING missing across section boundary");
2669 0 : err = true;
2670 : }
2671 :
2672 1564369492 : if ((e->flags & ~(EDGE_DFS_BACK
2673 : | EDGE_CAN_FALLTHRU
2674 : | EDGE_IRREDUCIBLE_LOOP
2675 : | EDGE_LOOP_EXIT
2676 : | EDGE_CROSSING
2677 : | EDGE_PRESERVE)) == 0)
2678 636572972 : n_branch++;
2679 :
2680 1564369492 : if (e->flags & EDGE_ABNORMAL_CALL)
2681 50460140 : n_abnormal_call++;
2682 :
2683 1564369492 : if (e->flags & EDGE_SIBCALL)
2684 10634363 : n_sibcall++;
2685 :
2686 1564369492 : if (e->flags & EDGE_EH)
2687 59975867 : n_eh++;
2688 :
2689 1564369492 : if (e->flags & EDGE_ABNORMAL)
2690 72049925 : n_abnormal++;
2691 : }
2692 :
2693 1074495088 : if (!has_crossing_edge
2694 1053917371 : && JUMP_P (BB_END (bb))
2695 1685568641 : && CROSSING_JUMP_P (BB_END (bb)))
2696 : {
2697 0 : print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2698 0 : error ("Region crossing jump across same section in bb %i",
2699 : bb->index);
2700 0 : err = true;
2701 : }
2702 :
2703 1074495088 : if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2704 : {
2705 0 : error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2706 0 : err = true;
2707 : }
2708 1074495088 : if (n_eh > 1)
2709 : {
2710 0 : error ("too many exception handling edges in bb %i", bb->index);
2711 0 : err = true;
2712 : }
2713 1074495088 : if (n_branch
2714 1074495088 : && (!JUMP_P (BB_END (bb))
2715 631545814 : || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2716 578999 : || any_condjump_p (BB_END (bb))))))
2717 : {
2718 0 : error ("too many outgoing branch edges from bb %i", bb->index);
2719 0 : err = true;
2720 : }
2721 1074495088 : if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2722 : {
2723 0 : error ("fallthru edge after unconditional jump in bb %i", bb->index);
2724 0 : err = true;
2725 : }
2726 1074495088 : if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2727 : {
2728 0 : error ("wrong number of branch edges after unconditional jump"
2729 : " in bb %i", bb->index);
2730 0 : err = true;
2731 : }
2732 443528273 : if (n_branch != 1 && any_condjump_p (BB_END (bb))
2733 1074496409 : && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2734 : {
2735 0 : error ("wrong amount of branch edges after conditional jump"
2736 : " in bb %i", bb->index);
2737 0 : err = true;
2738 : }
2739 1074495088 : if (n_abnormal_call && !CALL_P (BB_END (bb)))
2740 : {
2741 0 : error ("abnormal call edges for non-call insn in bb %i", bb->index);
2742 0 : err = true;
2743 : }
2744 1074495088 : if (n_sibcall && !CALL_P (BB_END (bb)))
2745 : {
2746 0 : error ("sibcall edges for non-call insn in bb %i", bb->index);
2747 0 : err = true;
2748 : }
2749 1074495088 : if (n_abnormal > n_eh
2750 10839298 : && !(CALL_P (BB_END (bb))
2751 10819056 : && n_abnormal == n_abnormal_call + n_sibcall)
2752 1074515330 : && (!JUMP_P (BB_END (bb))
2753 20242 : || any_condjump_p (BB_END (bb))
2754 20242 : || any_uncondjump_p (BB_END (bb))))
2755 : {
2756 0 : error ("abnormal edges for no purpose in bb %i", bb->index);
2757 0 : err = true;
2758 : }
2759 :
2760 1074495088 : int has_eh = -1;
2761 2632402485 : FOR_EACH_EDGE (e, ei, bb->preds)
2762 : {
2763 1557907397 : if (has_eh == -1)
2764 1074377440 : has_eh = (e->flags & EDGE_EH);
2765 1557907397 : if ((e->flags & EDGE_EH) == has_eh)
2766 1557907397 : continue;
2767 0 : error ("EH incoming edge mixed with non-EH incoming edges "
2768 : "in bb %i", bb->index);
2769 0 : err = true;
2770 0 : break;
2771 : }
2772 : }
2773 :
2774 : /* If there are partitions, do a sanity check on them: A basic block in
2775 : Â a cold partition cannot dominate a basic block in a hot partition. Â */
2776 3001436 : if (crtl->has_bb_partition && !err
2777 102416647 : && current_ir_type () == IR_RTL_CFGLAYOUT)
2778 : {
2779 123963 : auto_vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2780 247926 : err = !bbs_to_fix.is_empty ();
2781 123963 : }
2782 :
2783 : /* Clean up. */
2784 99415211 : return err;
2785 : }
2786 :
2787 : /* Checks on the instructions within blocks. Currently checks that each
2788 : block starts with a basic block note, and that basic block notes and
2789 : control flow jumps are not found in the middle of the block. */
2790 :
2791 : static bool
2792 99415211 : rtl_verify_bb_insns (void)
2793 : {
2794 99415211 : rtx_insn *x;
2795 99415211 : bool err = false;
2796 99415211 : basic_block bb;
2797 :
2798 1173910299 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2799 : {
2800 : /* Now check the header of basic
2801 : block. It ought to contain optional CODE_LABEL followed
2802 : by NOTE_BASIC_BLOCK. */
2803 1074495088 : x = BB_HEAD (bb);
2804 1074495088 : if (LABEL_P (x))
2805 : {
2806 516946100 : if (BB_END (bb) == x)
2807 : {
2808 0 : error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2809 : bb->index);
2810 0 : err = true;
2811 : }
2812 :
2813 516946100 : x = NEXT_INSN (x);
2814 : }
2815 :
2816 1074495088 : if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2817 : {
2818 0 : error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2819 : bb->index);
2820 0 : err = true;
2821 : }
2822 :
2823 1074495088 : if (BB_END (bb) == x)
2824 : /* Do checks for empty blocks here. */
2825 : ;
2826 : else
2827 12159079287 : for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2828 : {
2829 11103073645 : if (NOTE_INSN_BASIC_BLOCK_P (x))
2830 : {
2831 0 : error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2832 0 : INSN_UID (x), bb->index);
2833 0 : err = true;
2834 : }
2835 :
2836 11103073645 : if (x == BB_END (bb))
2837 : break;
2838 :
2839 10047068003 : if (control_flow_insn_p (x))
2840 : {
2841 0 : error ("in basic block %d:", bb->index);
2842 0 : fatal_insn ("flow control insn inside a basic block", x);
2843 : }
2844 : }
2845 : }
2846 :
2847 : /* Clean up. */
2848 99415211 : return err;
2849 : }
2850 :
2851 : /* Verify that block pointers for instructions in basic blocks, headers and
2852 : footers are set appropriately. */
2853 :
2854 : static bool
2855 99415211 : rtl_verify_bb_pointers (void)
2856 : {
2857 99415211 : bool err = false;
2858 99415211 : basic_block bb;
2859 :
2860 : /* Check the general integrity of the basic blocks. */
2861 1173910299 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2862 : {
2863 1074495088 : rtx_insn *insn;
2864 :
2865 1074495088 : if (!(bb->flags & BB_RTL))
2866 : {
2867 0 : error ("BB_RTL flag not set for block %d", bb->index);
2868 0 : err = true;
2869 : }
2870 :
2871 13769009921 : FOR_BB_INSNS (bb, insn)
2872 12694514833 : if (BLOCK_FOR_INSN (insn) != bb)
2873 : {
2874 0 : error ("insn %d basic block pointer is %d, should be %d",
2875 0 : INSN_UID (insn),
2876 0 : BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2877 : bb->index);
2878 0 : err = true;
2879 : }
2880 :
2881 1075079951 : for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2882 584863 : if (!BARRIER_P (insn)
2883 584863 : && BLOCK_FOR_INSN (insn) != NULL)
2884 : {
2885 0 : error ("insn %d in header of bb %d has non-NULL basic block",
2886 0 : INSN_UID (insn), bb->index);
2887 0 : err = true;
2888 : }
2889 1103259401 : for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2890 28764313 : if (!BARRIER_P (insn)
2891 28764313 : && BLOCK_FOR_INSN (insn) != NULL)
2892 : {
2893 0 : error ("insn %d in footer of bb %d has non-NULL basic block",
2894 0 : INSN_UID (insn), bb->index);
2895 0 : err = true;
2896 : }
2897 : }
2898 :
2899 : /* Clean up. */
2900 99415211 : return err;
2901 : }
2902 :
2903 : /* Verify the CFG and RTL consistency common for both underlying RTL and
2904 : cfglayout RTL.
2905 :
2906 : Currently it does following checks:
2907 :
2908 : - overlapping of basic blocks
2909 : - insns with wrong BLOCK_FOR_INSN pointers
2910 : - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2911 : - tails of basic blocks (ensure that boundary is necessary)
2912 : - scans body of the basic block for JUMP_INSN, CODE_LABEL
2913 : and NOTE_INSN_BASIC_BLOCK
2914 : - verify that no fall_thru edge crosses hot/cold partition boundaries
2915 : - verify that there are no pending RTL branch predictions
2916 : - verify that hot blocks are not dominated by cold blocks
2917 :
2918 : In future it can be extended check a lot of other stuff as well
2919 : (reachability of basic blocks, life information, etc. etc.). */
2920 :
2921 : static bool
2922 99415211 : rtl_verify_flow_info_1 (void)
2923 : {
2924 99415211 : bool err = false;
2925 :
2926 99415211 : if (rtl_verify_bb_pointers ())
2927 : err = true;
2928 :
2929 99415211 : if (rtl_verify_bb_insns ())
2930 0 : err = true;
2931 :
2932 99415211 : if (rtl_verify_edges ())
2933 0 : err = true;
2934 :
2935 99415211 : return err;
2936 : }
2937 :
2938 : /* Walk the instruction chain and verify that bb head/end pointers
2939 : are correct, and that instructions are in exactly one bb and have
2940 : correct block pointers. */
2941 :
2942 : static bool
2943 62948868 : rtl_verify_bb_insn_chain (void)
2944 : {
2945 62948868 : basic_block bb;
2946 62948868 : bool err = false;
2947 62948868 : rtx_insn *x;
2948 62948868 : rtx_insn *last_head = get_last_insn ();
2949 62948868 : basic_block *bb_info;
2950 62948868 : const int max_uid = get_max_uid ();
2951 :
2952 62948868 : bb_info = XCNEWVEC (basic_block, max_uid);
2953 :
2954 720949995 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2955 : {
2956 658001127 : rtx_insn *head = BB_HEAD (bb);
2957 658001127 : rtx_insn *end = BB_END (bb);
2958 :
2959 914561308 : for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2960 : {
2961 : /* Verify the end of the basic block is in the INSN chain. */
2962 914561308 : if (x == end)
2963 : break;
2964 :
2965 : /* And that the code outside of basic blocks has NULL bb field. */
2966 256560181 : if (!BARRIER_P (x)
2967 256560181 : && BLOCK_FOR_INSN (x) != NULL)
2968 : {
2969 0 : error ("insn %d outside of basic blocks has non-NULL bb field",
2970 0 : INSN_UID (x));
2971 0 : err = true;
2972 : }
2973 : }
2974 :
2975 658001127 : if (!x)
2976 : {
2977 0 : error ("end insn %d for block %d not found in the insn stream",
2978 0 : INSN_UID (end), bb->index);
2979 0 : err = true;
2980 : }
2981 :
2982 : /* Work backwards from the end to the head of the basic block
2983 : to verify the head is in the RTL chain. */
2984 7738458579 : for (; x != NULL_RTX; x = PREV_INSN (x))
2985 : {
2986 : /* While walking over the insn chain, verify insns appear
2987 : in only one basic block. */
2988 7738458579 : if (bb_info[INSN_UID (x)] != NULL)
2989 : {
2990 0 : error ("insn %d is in multiple basic blocks (%d and %d)",
2991 : INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2992 0 : err = true;
2993 : }
2994 :
2995 7738458579 : bb_info[INSN_UID (x)] = bb;
2996 :
2997 7738458579 : if (x == head)
2998 : break;
2999 : }
3000 658001127 : if (!x)
3001 : {
3002 0 : error ("head insn %d for block %d not found in the insn stream",
3003 0 : INSN_UID (head), bb->index);
3004 0 : err = true;
3005 : }
3006 :
3007 658001127 : last_head = PREV_INSN (x);
3008 : }
3009 :
3010 126920818 : for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
3011 : {
3012 : /* Check that the code before the first basic block has NULL
3013 : bb field. */
3014 63971950 : if (!BARRIER_P (x)
3015 63971950 : && BLOCK_FOR_INSN (x) != NULL)
3016 : {
3017 0 : error ("insn %d outside of basic blocks has non-NULL bb field",
3018 0 : INSN_UID (x));
3019 0 : err = true;
3020 : }
3021 : }
3022 62948868 : free (bb_info);
3023 :
3024 62948868 : return err;
3025 : }
3026 :
3027 : /* Verify that fallthru edges point to adjacent blocks in layout order and
3028 : that barriers exist after non-fallthru blocks. */
3029 :
3030 : static bool
3031 62948868 : rtl_verify_fallthru (void)
3032 : {
3033 62948868 : basic_block bb;
3034 62948868 : bool err = false;
3035 :
3036 720949995 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
3037 : {
3038 658001127 : edge e;
3039 :
3040 658001127 : e = find_fallthru_edge (bb->succs);
3041 658001127 : if (!e)
3042 : {
3043 191088395 : rtx_insn *insn;
3044 :
3045 : /* Ensure existence of barrier in BB with no fallthru edges. */
3046 191671442 : for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
3047 : {
3048 191671442 : if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
3049 : {
3050 0 : error ("missing barrier after block %i", bb->index);
3051 0 : err = true;
3052 0 : break;
3053 : }
3054 191671442 : if (BARRIER_P (insn))
3055 : break;
3056 : }
3057 : }
3058 466912732 : else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
3059 466912732 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3060 : {
3061 436721346 : rtx_insn *insn;
3062 :
3063 436721346 : if (e->src->next_bb != e->dest)
3064 : {
3065 0 : error
3066 0 : ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
3067 : e->src->index, e->dest->index);
3068 0 : err = true;
3069 : }
3070 : else
3071 879955381 : for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
3072 6512689 : insn = NEXT_INSN (insn))
3073 6512689 : if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn))
3074 : {
3075 0 : error ("verify_flow_info: Incorrect fallthru %i->%i",
3076 0 : e->src->index, e->dest->index);
3077 0 : error ("wrong insn in the fallthru edge");
3078 0 : debug_rtx (insn);
3079 0 : err = true;
3080 : }
3081 : }
3082 : }
3083 :
3084 62948868 : return err;
3085 : }
3086 :
3087 : /* Verify that blocks are laid out in consecutive order. While walking the
3088 : instructions, verify that all expected instructions are inside the basic
3089 : blocks, and that all returns are followed by barriers. */
3090 :
3091 : static bool
3092 62948868 : rtl_verify_bb_layout (void)
3093 : {
3094 62948868 : basic_block bb;
3095 62948868 : bool err = false;
3096 62948868 : rtx_insn *x, *y;
3097 62948868 : int num_bb_notes;
3098 62948868 : rtx_insn * const rtx_first = get_insns ();
3099 62948868 : basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
3100 :
3101 62948868 : num_bb_notes = 0;
3102 :
3103 8121611630 : for (x = rtx_first; x; x = NEXT_INSN (x))
3104 : {
3105 8058662762 : if (NOTE_INSN_BASIC_BLOCK_P (x))
3106 : {
3107 658001127 : bb = NOTE_BASIC_BLOCK (x);
3108 :
3109 658001127 : num_bb_notes++;
3110 658001127 : if (bb != last_bb_seen->next_bb)
3111 0 : internal_error ("basic blocks not laid down consecutively");
3112 :
3113 : curr_bb = last_bb_seen = bb;
3114 : }
3115 :
3116 8058662762 : if (!curr_bb)
3117 : {
3118 631073879 : switch (GET_CODE (x))
3119 : {
3120 : case BARRIER:
3121 : case NOTE:
3122 : break;
3123 :
3124 311197644 : case CODE_LABEL:
3125 : /* An ADDR_VEC is placed outside any basic block. */
3126 311197644 : if (NEXT_INSN (x)
3127 311197644 : && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
3128 : x = NEXT_INSN (x);
3129 :
3130 : /* But in any case, non-deletable labels can appear anywhere. */
3131 : break;
3132 :
3133 0 : default:
3134 0 : fatal_insn ("insn outside basic block", x);
3135 : }
3136 : }
3137 :
3138 8058662762 : if (JUMP_P (x)
3139 439659058 : && returnjump_p (x) && ! condjump_p (x)
3140 8090101983 : && ! ((y = next_nonnote_nondebug_insn (x))
3141 31439221 : && BARRIER_P (y)))
3142 0 : fatal_insn ("return not followed by barrier", x);
3143 :
3144 8058662762 : if (curr_bb && x == BB_END (curr_bb))
3145 1289075006 : curr_bb = NULL;
3146 : }
3147 :
3148 62948868 : if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
3149 0 : internal_error
3150 0 : ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3151 : num_bb_notes, n_basic_blocks_for_fn (cfun));
3152 :
3153 62948868 : return err;
3154 : }
3155 :
3156 : /* Verify the CFG and RTL consistency common for both underlying RTL and
3157 : cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3158 :
3159 : Currently it does following checks:
3160 : - all checks of rtl_verify_flow_info_1
3161 : - test head/end pointers
3162 : - check that blocks are laid out in consecutive order
3163 : - check that all insns are in the basic blocks
3164 : (except the switch handling code, barriers and notes)
3165 : - check that all returns are followed by barriers
3166 : - check that all fallthru edge points to the adjacent blocks
3167 : - verify that there is a single hot/cold partition boundary after bbro */
3168 :
3169 : static bool
3170 62948868 : rtl_verify_flow_info (void)
3171 : {
3172 62948868 : bool err = false;
3173 :
3174 62948868 : if (rtl_verify_flow_info_1 ())
3175 : err = true;
3176 :
3177 62948868 : if (rtl_verify_bb_insn_chain ())
3178 0 : err = true;
3179 :
3180 62948868 : if (rtl_verify_fallthru ())
3181 0 : err = true;
3182 :
3183 62948868 : if (rtl_verify_bb_layout ())
3184 : err = true;
3185 :
3186 62948868 : if (verify_hot_cold_block_grouping ())
3187 0 : err = true;
3188 :
3189 62948868 : return err;
3190 : }
3191 :
3192 : /* Assume that the preceding pass has possibly eliminated jump instructions
3193 : or converted the unconditional jumps. Eliminate the edges from CFG.
3194 : Return true if any edges are eliminated. */
3195 :
3196 : bool
3197 74084745 : purge_dead_edges (basic_block bb)
3198 : {
3199 74084745 : edge e;
3200 74084745 : rtx_insn *insn = BB_END (bb);
3201 74084745 : rtx note;
3202 74084745 : bool purged = false;
3203 74084745 : bool found;
3204 74084745 : edge_iterator ei;
3205 :
3206 74084745 : if ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb))
3207 16670032 : do
3208 16670032 : insn = PREV_INSN (insn);
3209 16670032 : while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3210 :
3211 : /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3212 74084745 : if (NONJUMP_INSN_P (insn)
3213 74084745 : && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3214 : {
3215 1360861 : rtx eqnote;
3216 :
3217 1360861 : if (! may_trap_p (PATTERN (insn))
3218 1360861 : || ((eqnote = find_reg_equal_equiv_note (insn))
3219 167 : && ! may_trap_p (XEXP (eqnote, 0))))
3220 43935 : remove_note (insn, note);
3221 : }
3222 : /* A tail call cannot trap either. The tailc/musttail pass could have
3223 : allowed a tail call if it could throw internally, but perform no
3224 : actual statements and then caused the exception to be thrown externally
3225 : in the hope that it is cleaned up later. If it is not, just
3226 : remove REG_EH_REGION note. While the call maybe can throw, the
3227 : current function's frame will not be there anymore when it does. */
3228 74084745 : if (CALL_P (insn)
3229 9228530 : && SIBLING_CALL_P (insn)
3230 74604699 : && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3231 83883 : remove_note (insn, note);
3232 :
3233 : /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3234 177952826 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3235 : {
3236 103868081 : bool remove = false;
3237 :
3238 : /* There are three types of edges we need to handle correctly here: EH
3239 : edges, abnormal call EH edges, and abnormal call non-EH edges. The
3240 : latter can appear when nonlocal gotos are used. */
3241 103868081 : if (e->flags & EDGE_ABNORMAL_CALL)
3242 : {
3243 3369720 : if (!CALL_P (insn))
3244 : remove = true;
3245 3369715 : else if (can_nonlocal_goto (insn))
3246 : ;
3247 3293674 : else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3248 : ;
3249 0 : else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3250 : ;
3251 : else
3252 : remove = true;
3253 : }
3254 100498361 : else if (e->flags & EDGE_EH)
3255 1944217 : remove = !can_throw_internal (insn);
3256 :
3257 1944217 : if (remove)
3258 : {
3259 383480 : remove_edge (e);
3260 383480 : df_set_bb_dirty (bb);
3261 383480 : purged = true;
3262 : }
3263 : else
3264 103484601 : ei_next (&ei);
3265 : }
3266 :
3267 74084745 : if (JUMP_P (insn))
3268 : {
3269 40029724 : rtx note;
3270 40029724 : edge b,f;
3271 40029724 : edge_iterator ei;
3272 :
3273 : /* We do care only about conditional jumps and simplejumps. */
3274 40029724 : if (!any_condjump_p (insn)
3275 12827298 : && !returnjump_p (insn)
3276 49260318 : && !simplejump_p (insn))
3277 : return purged;
3278 :
3279 : /* Branch probability/prediction notes are defined only for
3280 : condjumps. We've possibly turned condjump into simplejump. */
3281 39992415 : if (simplejump_p (insn))
3282 : {
3283 9193285 : note = find_reg_note (insn, REG_BR_PROB, NULL);
3284 9193285 : if (note)
3285 4172 : remove_note (insn, note);
3286 9193285 : while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3287 0 : remove_note (insn, note);
3288 : }
3289 :
3290 107200368 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3291 : {
3292 : /* Avoid abnormal flags to leak from computed jumps turned
3293 : into simplejumps. */
3294 :
3295 67207953 : e->flags &= ~EDGE_ABNORMAL;
3296 :
3297 : /* See if this edge is one we should keep. */
3298 67207953 : if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3299 : /* A conditional jump can fall through into the next
3300 : block, so we should keep the edge. */
3301 : {
3302 27202426 : ei_next (&ei);
3303 27202426 : continue;
3304 : }
3305 40005527 : else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3306 36408823 : && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3307 : /* If the destination block is the target of the jump,
3308 : keep the edge. */
3309 : {
3310 36394690 : ei_next (&ei);
3311 36394690 : continue;
3312 : }
3313 7207541 : else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3314 3610837 : && returnjump_p (insn))
3315 : /* If the destination block is the exit block, and this
3316 : instruction is a return, then keep the edge. */
3317 : {
3318 3596704 : ei_next (&ei);
3319 3596704 : continue;
3320 : }
3321 14133 : else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3322 : /* Keep the edges that correspond to exceptions thrown by
3323 : this instruction and rematerialize the EDGE_ABNORMAL
3324 : flag we just cleared above. */
3325 : {
3326 0 : e->flags |= EDGE_ABNORMAL;
3327 0 : ei_next (&ei);
3328 0 : continue;
3329 : }
3330 :
3331 : /* We do not need this edge. */
3332 14133 : df_set_bb_dirty (bb);
3333 14133 : purged = true;
3334 14133 : remove_edge (e);
3335 : }
3336 :
3337 40175168 : if (EDGE_COUNT (bb->succs) == 0 || !purged)
3338 : return purged;
3339 :
3340 145444 : if (dump_file)
3341 0 : fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3342 :
3343 145444 : if (!optimize)
3344 : return purged;
3345 :
3346 : /* Redistribute probabilities. */
3347 144884 : if (single_succ_p (bb))
3348 : {
3349 144884 : single_succ_edge (bb)->probability = profile_probability::always ();
3350 : }
3351 : else
3352 : {
3353 0 : note = find_reg_note (insn, REG_BR_PROB, NULL);
3354 0 : if (!note)
3355 : return purged;
3356 :
3357 0 : b = BRANCH_EDGE (bb);
3358 0 : f = FALLTHRU_EDGE (bb);
3359 0 : b->probability = profile_probability::from_reg_br_prob_note
3360 0 : (XINT (note, 0));
3361 0 : f->probability = b->probability.invert ();
3362 : }
3363 :
3364 144884 : return purged;
3365 : }
3366 34055021 : else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3367 : {
3368 : /* First, there should not be any EH or ABCALL edges resulting
3369 : from non-local gotos and the like. If there were, we shouldn't
3370 : have created the sibcall in the first place. Second, there
3371 : should of course never have been a fallthru edge. */
3372 519954 : gcc_assert (single_succ_p (bb));
3373 519954 : gcc_assert (single_succ_edge (bb)->flags
3374 : == (EDGE_SIBCALL | EDGE_ABNORMAL));
3375 :
3376 : return false;
3377 : }
3378 :
3379 : /* If we don't see a jump insn, we don't know exactly why the block would
3380 : have been broken at this point. Look for a simple, non-fallthru edge,
3381 : as these are only created by conditional branches. If we find such an
3382 : edge we know that there used to be a jump here and can then safely
3383 : remove all non-fallthru edges. */
3384 33535067 : found = false;
3385 68570857 : FOR_EACH_EDGE (e, ei, bb->succs)
3386 35313681 : if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3387 : {
3388 : found = true;
3389 : break;
3390 : }
3391 :
3392 33535067 : if (!found)
3393 : return purged;
3394 :
3395 : /* Remove all but the fake and fallthru edges. The fake edge may be
3396 : the only successor for this block in the case of noreturn
3397 : calls. */
3398 833805 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3399 : {
3400 555914 : if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3401 : {
3402 278023 : df_set_bb_dirty (bb);
3403 278023 : remove_edge (e);
3404 278023 : purged = true;
3405 : }
3406 : else
3407 277891 : ei_next (&ei);
3408 : }
3409 :
3410 277891 : gcc_assert (single_succ_p (bb));
3411 :
3412 277891 : single_succ_edge (bb)->probability = profile_probability::always ();
3413 :
3414 277891 : if (dump_file)
3415 1 : fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3416 : bb->index);
3417 : return purged;
3418 : }
3419 :
3420 : /* Search all basic blocks for potentially dead edges and purge them. Return
3421 : true if some edge has been eliminated. */
3422 :
3423 : bool
3424 3361348 : purge_all_dead_edges (void)
3425 : {
3426 3361348 : bool purged = false;
3427 3361348 : basic_block bb;
3428 :
3429 49178546 : FOR_EACH_BB_FN (bb, cfun)
3430 45817198 : if (purge_dead_edges (bb))
3431 2640 : purged = true;
3432 :
3433 3361348 : return purged;
3434 : }
3435 :
3436 : /* This is used by a few passes that emit some instructions after abnormal
3437 : calls, moving the basic block's end, while they in fact do want to emit
3438 : them on the fallthru edge. Look for abnormal call edges, find backward
3439 : the call in the block and insert the instructions on the edge instead.
3440 :
3441 : Similarly, handle instructions throwing exceptions internally.
3442 :
3443 : Return true when instructions have been found and inserted on edges. */
3444 :
3445 : bool
3446 1516259 : fixup_abnormal_edges (void)
3447 : {
3448 1516259 : bool inserted = false;
3449 1516259 : basic_block bb;
3450 :
3451 17109130 : FOR_EACH_BB_FN (bb, cfun)
3452 : {
3453 15592871 : edge e;
3454 15592871 : edge_iterator ei;
3455 :
3456 : /* Look for cases we are interested in - calls or instructions causing
3457 : exceptions. */
3458 36731649 : FOR_EACH_EDGE (e, ei, bb->succs)
3459 21821555 : if ((e->flags & EDGE_ABNORMAL_CALL)
3460 21249206 : || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3461 : == (EDGE_ABNORMAL | EDGE_EH)))
3462 : break;
3463 :
3464 15592871 : if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3465 : {
3466 9044 : rtx_insn *insn;
3467 :
3468 : /* Get past the new insns generated. Allow notes, as the insns
3469 : may be already deleted. */
3470 9044 : insn = BB_END (bb);
3471 15351 : while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3472 14554 : && !can_throw_internal (insn)
3473 27134 : && insn != BB_HEAD (bb))
3474 7453 : insn = PREV_INSN (insn);
3475 :
3476 9044 : if (CALL_P (insn) || can_throw_internal (insn))
3477 : {
3478 5851 : rtx_insn *stop, *next;
3479 :
3480 5851 : e = find_fallthru_edge (bb->succs);
3481 :
3482 5851 : stop = NEXT_INSN (BB_END (bb));
3483 5851 : BB_END (bb) = insn;
3484 :
3485 18954 : for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3486 : {
3487 7252 : next = NEXT_INSN (insn);
3488 7252 : if (INSN_P (insn))
3489 : {
3490 6119 : delete_insn (insn);
3491 :
3492 : /* Sometimes there's still the return value USE.
3493 : If it's placed after a trapping call (i.e. that
3494 : call is the last insn anyway), we have no fallthru
3495 : edge. Simply delete this use and don't try to insert
3496 : on the non-existent edge.
3497 : Similarly, sometimes a call that can throw is
3498 : followed in the source with __builtin_unreachable (),
3499 : meaning that there is UB if the call returns rather
3500 : than throws. If there weren't any instructions
3501 : following such calls before, supposedly even the ones
3502 : we've deleted aren't significant and can be
3503 : removed. */
3504 6119 : if (e)
3505 : {
3506 : /* We're not deleting it, we're moving it. */
3507 6118 : insn->set_undeleted ();
3508 6118 : SET_PREV_INSN (insn) = NULL_RTX;
3509 6118 : SET_NEXT_INSN (insn) = NULL_RTX;
3510 :
3511 6118 : insert_insn_on_edge (insn, e);
3512 6118 : inserted = true;
3513 : }
3514 : }
3515 1133 : else if (!BARRIER_P (insn))
3516 1133 : set_block_for_insn (insn, NULL);
3517 : }
3518 : }
3519 :
3520 : /* It may be that we don't find any trapping insn. In this
3521 : case we discovered quite late that the insn that had been
3522 : marked as can_throw_internal in fact couldn't trap at all.
3523 : So we should in fact delete the EH edges out of the block. */
3524 : else
3525 3193 : purge_dead_edges (bb);
3526 : }
3527 : }
3528 :
3529 1516259 : return inserted;
3530 : }
3531 :
3532 : /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3533 : Note that the INSN should be deleted *after* removing dead edges, so
3534 : that the kept edge is the fallthrough edge for a (set (pc) (pc))
3535 : but not for a (set (pc) (label_ref FOO)). */
3536 :
3537 : void
3538 4474 : update_cfg_for_uncondjump (rtx_insn *insn)
3539 : {
3540 4474 : basic_block bb = BLOCK_FOR_INSN (insn);
3541 4474 : gcc_assert (BB_END (bb) == insn);
3542 :
3543 4474 : purge_dead_edges (bb);
3544 :
3545 4474 : if (current_ir_type () != IR_RTL_CFGLAYOUT)
3546 : {
3547 39 : if (!find_fallthru_edge (bb->succs))
3548 : {
3549 39 : auto barrier = next_nonnote_nondebug_insn (insn);
3550 39 : if (!barrier || !BARRIER_P (barrier))
3551 39 : emit_barrier_after (insn);
3552 : }
3553 39 : return;
3554 : }
3555 :
3556 4435 : delete_insn (insn);
3557 4435 : if (EDGE_COUNT (bb->succs) == 1)
3558 : {
3559 2102 : rtx_insn *insn;
3560 :
3561 2102 : single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
3562 :
3563 : /* Remove barriers from the footer if there are any. */
3564 2103 : for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
3565 1 : if (BARRIER_P (insn))
3566 : {
3567 1 : if (PREV_INSN (insn))
3568 0 : SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
3569 : else
3570 1 : BB_FOOTER (bb) = NEXT_INSN (insn);
3571 1 : if (NEXT_INSN (insn))
3572 0 : SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
3573 : }
3574 0 : else if (LABEL_P (insn))
3575 : break;
3576 : }
3577 : }
3578 :
3579 : /* Cut the insns from FIRST to LAST out of the insns stream. */
3580 :
3581 : rtx_insn *
3582 11872550 : unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3583 : {
3584 11872550 : rtx_insn *prevfirst = PREV_INSN (first);
3585 11872550 : rtx_insn *nextlast = NEXT_INSN (last);
3586 :
3587 11872550 : SET_PREV_INSN (first) = NULL;
3588 11872550 : SET_NEXT_INSN (last) = NULL;
3589 11872550 : if (prevfirst)
3590 9344495 : SET_NEXT_INSN (prevfirst) = nextlast;
3591 11872550 : if (nextlast)
3592 10415152 : SET_PREV_INSN (nextlast) = prevfirst;
3593 : else
3594 1457398 : set_last_insn (prevfirst);
3595 11872550 : if (!prevfirst)
3596 2528055 : set_first_insn (nextlast);
3597 11872550 : return first;
3598 : }
3599 :
3600 : /* Skip over inter-block insns occurring after BB which are typically
3601 : associated with BB (e.g., barriers). If there are any such insns,
3602 : we return the last one. Otherwise, we return the end of BB. */
3603 :
3604 : static rtx_insn *
3605 26403526 : skip_insns_after_block (basic_block bb)
3606 : {
3607 26403526 : rtx_insn *insn, *last_insn, *next_head, *prev;
3608 :
3609 26403526 : next_head = NULL;
3610 26403526 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3611 23875456 : next_head = BB_HEAD (bb->next_bb);
3612 :
3613 35138362 : for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3614 : {
3615 32610292 : if (insn == next_head)
3616 : break;
3617 :
3618 8734836 : switch (GET_CODE (insn))
3619 : {
3620 7640659 : case BARRIER:
3621 7640659 : last_insn = insn;
3622 7640659 : continue;
3623 :
3624 1081554 : case NOTE:
3625 1081554 : gcc_assert (NOTE_KIND (insn) != NOTE_INSN_BLOCK_END);
3626 1081554 : continue;
3627 :
3628 12623 : case CODE_LABEL:
3629 12623 : if (NEXT_INSN (insn)
3630 12623 : && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3631 : {
3632 12623 : insn = NEXT_INSN (insn);
3633 12623 : last_insn = insn;
3634 12623 : continue;
3635 : }
3636 : break;
3637 :
3638 : default:
3639 : break;
3640 : }
3641 :
3642 : break;
3643 : }
3644 :
3645 : /* It is possible to hit contradictory sequence. For instance:
3646 :
3647 : jump_insn
3648 : NOTE_INSN_BLOCK_BEG
3649 : barrier
3650 :
3651 : Where barrier belongs to jump_insn, but the note does not. This can be
3652 : created by removing the basic block originally following
3653 : NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3654 :
3655 34069583 : for (insn = last_insn; insn != BB_END (bb); insn = prev)
3656 : {
3657 7666057 : prev = PREV_INSN (insn);
3658 7666057 : if (NOTE_P (insn))
3659 152 : switch (NOTE_KIND (insn))
3660 : {
3661 0 : case NOTE_INSN_BLOCK_END:
3662 0 : gcc_unreachable ();
3663 152 : break;
3664 152 : case NOTE_INSN_DELETED:
3665 152 : case NOTE_INSN_DELETED_LABEL:
3666 152 : case NOTE_INSN_DELETED_DEBUG_LABEL:
3667 152 : continue;
3668 0 : default:
3669 0 : reorder_insns (insn, insn, last_insn);
3670 : }
3671 : }
3672 :
3673 26403526 : return last_insn;
3674 : }
3675 :
3676 : /* Locate or create a label for a given basic block. */
3677 :
3678 : static rtx_insn *
3679 2262851 : label_for_bb (basic_block bb)
3680 : {
3681 2262851 : rtx_insn *label = BB_HEAD (bb);
3682 :
3683 2262851 : if (!LABEL_P (label))
3684 : {
3685 1443701 : if (dump_file)
3686 8 : fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3687 :
3688 1443701 : label = block_label (bb);
3689 : }
3690 :
3691 2262851 : return label;
3692 : }
3693 :
3694 : /* Locate the effective beginning and end of the insn chain for each
3695 : block, as defined by skip_insns_after_block above. */
3696 :
3697 : static void
3698 2528070 : record_effective_endpoints (void)
3699 : {
3700 2528070 : rtx_insn *next_insn;
3701 2528070 : basic_block bb;
3702 2528070 : rtx_insn *insn;
3703 :
3704 2528070 : for (insn = get_insns ();
3705 : insn
3706 5058756 : && NOTE_P (insn)
3707 10116401 : && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3708 2530686 : insn = NEXT_INSN (insn))
3709 2530686 : continue;
3710 : /* No basic blocks at all? */
3711 2528070 : gcc_assert (insn);
3712 :
3713 2528070 : if (PREV_INSN (insn))
3714 2528055 : cfg_layout_function_header =
3715 2528055 : unlink_insn_chain (get_insns (), PREV_INSN (insn));
3716 : else
3717 15 : cfg_layout_function_header = NULL;
3718 :
3719 2528070 : next_insn = get_insns ();
3720 28931596 : FOR_EACH_BB_FN (bb, cfun)
3721 : {
3722 26403526 : rtx_insn *end;
3723 :
3724 26403526 : if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3725 45705 : BB_HEADER (bb) = unlink_insn_chain (next_insn,
3726 45705 : PREV_INSN (BB_HEAD (bb)));
3727 26403526 : end = skip_insns_after_block (bb);
3728 26403526 : if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3729 7564227 : BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3730 26403526 : next_insn = NEXT_INSN (BB_END (bb));
3731 : }
3732 :
3733 2528070 : cfg_layout_function_footer = next_insn;
3734 2528070 : if (cfg_layout_function_footer)
3735 1022939 : cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3736 2530686 : }
3737 :
3738 : namespace {
3739 :
3740 : const pass_data pass_data_into_cfg_layout_mode =
3741 : {
3742 : RTL_PASS, /* type */
3743 : "into_cfglayout", /* name */
3744 : OPTGROUP_NONE, /* optinfo_flags */
3745 : TV_CFG, /* tv_id */
3746 : 0, /* properties_required */
3747 : PROP_cfglayout, /* properties_provided */
3748 : 0, /* properties_destroyed */
3749 : 0, /* todo_flags_start */
3750 : 0, /* todo_flags_finish */
3751 : };
3752 :
3753 : class pass_into_cfg_layout_mode : public rtl_opt_pass
3754 : {
3755 : public:
3756 288767 : pass_into_cfg_layout_mode (gcc::context *ctxt)
3757 577534 : : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3758 : {}
3759 :
3760 : /* opt_pass methods: */
3761 1481480 : unsigned int execute (function *) final override
3762 : {
3763 1481480 : cfg_layout_initialize (0);
3764 1481480 : return 0;
3765 : }
3766 :
3767 : }; // class pass_into_cfg_layout_mode
3768 :
3769 : } // anon namespace
3770 :
3771 : rtl_opt_pass *
3772 288767 : make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3773 : {
3774 288767 : return new pass_into_cfg_layout_mode (ctxt);
3775 : }
3776 :
3777 : namespace {
3778 :
3779 : const pass_data pass_data_outof_cfg_layout_mode =
3780 : {
3781 : RTL_PASS, /* type */
3782 : "outof_cfglayout", /* name */
3783 : OPTGROUP_NONE, /* optinfo_flags */
3784 : TV_CFG, /* tv_id */
3785 : 0, /* properties_required */
3786 : 0, /* properties_provided */
3787 : PROP_cfglayout, /* properties_destroyed */
3788 : 0, /* todo_flags_start */
3789 : 0, /* todo_flags_finish */
3790 : };
3791 :
3792 : class pass_outof_cfg_layout_mode : public rtl_opt_pass
3793 : {
3794 : public:
3795 288767 : pass_outof_cfg_layout_mode (gcc::context *ctxt)
3796 577534 : : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3797 : {}
3798 :
3799 : /* opt_pass methods: */
3800 : unsigned int execute (function *) final override;
3801 :
3802 : }; // class pass_outof_cfg_layout_mode
3803 :
3804 : unsigned int
3805 1481481 : pass_outof_cfg_layout_mode::execute (function *fun)
3806 : {
3807 1481481 : basic_block bb;
3808 :
3809 14999964 : FOR_EACH_BB_FN (bb, fun)
3810 13518483 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3811 12037002 : bb->aux = bb->next_bb;
3812 :
3813 1481481 : cfg_layout_finalize ();
3814 :
3815 1481481 : return 0;
3816 : }
3817 :
3818 : } // anon namespace
3819 :
3820 : rtl_opt_pass *
3821 288767 : make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3822 : {
3823 288767 : return new pass_outof_cfg_layout_mode (ctxt);
3824 : }
3825 :
3826 :
3827 : /* Link the basic blocks in the correct order, compacting the basic
3828 : block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3829 : function also clears the basic block header and footer fields.
3830 :
3831 : This function is usually called after a pass (e.g. tracer) finishes
3832 : some transformations while in cfglayout mode. The required sequence
3833 : of the basic blocks is in a linked list along the bb->aux field.
3834 : This functions re-links the basic block prev_bb and next_bb pointers
3835 : accordingly, and it compacts and renumbers the blocks.
3836 :
3837 : FIXME: This currently works only for RTL, but the only RTL-specific
3838 : bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3839 : to GIMPLE a long time ago, but it doesn't relink the basic block
3840 : chain. It could do that (to give better initial RTL) if this function
3841 : is made IR-agnostic (and moved to cfganal.cc or cfg.cc while at it). */
3842 :
3843 : void
3844 3161677 : relink_block_chain (bool stay_in_cfglayout_mode)
3845 : {
3846 3161677 : basic_block bb, prev_bb;
3847 3161677 : int index;
3848 :
3849 : /* Maybe dump the re-ordered sequence. */
3850 3161677 : if (dump_file)
3851 : {
3852 168 : fprintf (dump_file, "Reordered sequence:\n");
3853 168 : for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3854 : NUM_FIXED_BLOCKS;
3855 1094 : bb;
3856 926 : bb = (basic_block) bb->aux, index++)
3857 : {
3858 926 : fprintf (dump_file, " %i ", index);
3859 926 : if (get_bb_original (bb))
3860 28 : fprintf (dump_file, "duplicate of %i\n",
3861 28 : get_bb_original (bb)->index);
3862 898 : else if (forwarder_block_p (bb)
3863 898 : && !LABEL_P (BB_HEAD (bb)))
3864 16 : fprintf (dump_file, "compensation\n");
3865 : else
3866 882 : fprintf (dump_file, "bb %i\n", bb->index);
3867 : }
3868 : }
3869 :
3870 : /* Now reorder the blocks. */
3871 3161677 : prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3872 3161677 : bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3873 38648928 : for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3874 : {
3875 35487251 : bb->prev_bb = prev_bb;
3876 35487251 : prev_bb->next_bb = bb;
3877 : }
3878 3161677 : prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3879 3161677 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3880 :
3881 : /* Then, clean up the aux fields. */
3882 44972282 : FOR_ALL_BB_FN (bb, cfun)
3883 : {
3884 41810605 : bb->aux = NULL;
3885 41810605 : if (!stay_in_cfglayout_mode)
3886 30002071 : BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3887 : }
3888 :
3889 : /* Maybe reset the original copy tables, they are not valid anymore
3890 : when we renumber the basic blocks in compact_blocks. If we are
3891 : are going out of cfglayout mode, don't re-allocate the tables. */
3892 3161677 : if (original_copy_tables_initialized_p ())
3893 3161676 : free_original_copy_tables ();
3894 3161677 : if (stay_in_cfglayout_mode)
3895 633606 : initialize_original_copy_tables ();
3896 :
3897 : /* Finally, put basic_block_info in the new order. */
3898 3161677 : compact_blocks ();
3899 3161677 : }
3900 :
3901 :
3902 : /* Given a reorder chain, rearrange the code to match. */
3903 :
3904 : static void
3905 2528071 : fixup_reorder_chain (void)
3906 : {
3907 2528071 : basic_block bb;
3908 2528071 : rtx_insn *insn = NULL;
3909 :
3910 2528071 : if (cfg_layout_function_header)
3911 : {
3912 2528055 : set_first_insn (cfg_layout_function_header);
3913 2528055 : insn = cfg_layout_function_header;
3914 2530686 : while (NEXT_INSN (insn))
3915 : insn = NEXT_INSN (insn);
3916 : }
3917 :
3918 : /* First do the bulk reordering -- rechain the blocks without regard to
3919 : the needed changes to jumps and labels. */
3920 :
3921 26718578 : for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3922 : bb->aux)
3923 : {
3924 24190507 : if (BB_HEADER (bb))
3925 : {
3926 44725 : if (insn)
3927 44725 : SET_NEXT_INSN (insn) = BB_HEADER (bb);
3928 : else
3929 0 : set_first_insn (BB_HEADER (bb));
3930 44725 : SET_PREV_INSN (BB_HEADER (bb)) = insn;
3931 44725 : insn = BB_HEADER (bb);
3932 57042 : while (NEXT_INSN (insn))
3933 : insn = NEXT_INSN (insn);
3934 : }
3935 24190507 : if (insn)
3936 24190491 : SET_NEXT_INSN (insn) = BB_HEAD (bb);
3937 : else
3938 16 : set_first_insn (BB_HEAD (bb));
3939 24190507 : SET_PREV_INSN (BB_HEAD (bb)) = insn;
3940 24190507 : insn = BB_END (bb);
3941 24190507 : if (BB_FOOTER (bb))
3942 : {
3943 3013351 : SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3944 3013351 : SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3945 6067440 : while (NEXT_INSN (insn))
3946 : insn = NEXT_INSN (insn);
3947 : }
3948 : }
3949 :
3950 2528071 : SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3951 2528071 : if (cfg_layout_function_footer)
3952 1022946 : SET_PREV_INSN (cfg_layout_function_footer) = insn;
3953 :
3954 3551815 : while (NEXT_INSN (insn))
3955 : insn = NEXT_INSN (insn);
3956 :
3957 2528071 : set_last_insn (insn);
3958 2528071 : if (flag_checking)
3959 2528033 : verify_insn_chain ();
3960 :
3961 : /* Now add jumps and labels as needed to match the blocks new
3962 : outgoing edges. */
3963 :
3964 2528071 : bool remove_unreachable_blocks = false;
3965 26718578 : for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3966 : bb->aux)
3967 : {
3968 24190507 : edge e_fall, e_taken, e;
3969 24190507 : rtx_insn *bb_end_insn;
3970 24190507 : rtx ret_label = NULL_RTX;
3971 24190507 : basic_block nb;
3972 24190507 : edge_iterator ei;
3973 24190507 : bool asm_goto = false;
3974 :
3975 24190507 : if (EDGE_COUNT (bb->succs) == 0)
3976 20154549 : continue;
3977 :
3978 : /* Find the old fallthru edge, and another non-EH edge for
3979 : a taken jump. */
3980 22900999 : e_taken = e_fall = NULL;
3981 :
3982 58397856 : FOR_EACH_EDGE (e, ei, bb->succs)
3983 35496857 : if (e->flags & EDGE_FALLTHRU)
3984 : e_fall = e;
3985 14318585 : else if (! (e->flags & EDGE_EH))
3986 13047832 : e_taken = e;
3987 :
3988 22900999 : bb_end_insn = BB_END (bb);
3989 22900999 : if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3990 : {
3991 12638747 : ret_label = JUMP_LABEL (bb_end_jump);
3992 12638747 : if (any_condjump_p (bb_end_jump))
3993 : {
3994 : /* This might happen if the conditional jump has side
3995 : effects and could therefore not be optimized away.
3996 : Make the basic block to end with a barrier in order
3997 : to prevent rtl_verify_flow_info from complaining. */
3998 11277779 : if (!e_fall)
3999 : {
4000 0 : gcc_assert (!onlyjump_p (bb_end_jump)
4001 : || returnjump_p (bb_end_jump)
4002 : || (e_taken->flags & EDGE_CROSSING));
4003 0 : emit_barrier_after (bb_end_jump);
4004 0 : continue;
4005 : }
4006 :
4007 : /* If the old fallthru is still next, nothing to do. */
4008 11277779 : if (bb->aux == e_fall->dest
4009 2715324 : || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4010 8562467 : continue;
4011 :
4012 : /* The degenerated case of conditional jump jumping to the next
4013 : instruction can happen for jumps with side effects. We need
4014 : to construct a forwarder block and this will be done just
4015 : fine by force_nonfallthru below. */
4016 2715312 : if (!e_taken)
4017 : ;
4018 :
4019 : /* There is another special case: if *neither* block is next,
4020 : such as happens at the very end of a function, then we'll
4021 : need to add a new unconditional jump. Choose the taken
4022 : edge based on known or assumed probability. */
4023 2715312 : else if (bb->aux != e_taken->dest)
4024 : {
4025 576975 : rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
4026 :
4027 576975 : if (note
4028 : && profile_probability::from_reg_br_prob_note
4029 555479 : (XINT (note, 0)) < profile_probability::even ()
4030 772578 : && invert_jump (bb_end_jump,
4031 195603 : (e_fall->dest
4032 195603 : == EXIT_BLOCK_PTR_FOR_FN (cfun)
4033 : ? NULL_RTX
4034 195603 : : label_for_bb (e_fall->dest)), 0))
4035 : {
4036 195603 : e_fall->flags &= ~EDGE_FALLTHRU;
4037 195603 : gcc_checking_assert (could_fall_through
4038 : (e_taken->src, e_taken->dest));
4039 195603 : e_taken->flags |= EDGE_FALLTHRU;
4040 195603 : update_br_prob_note (bb);
4041 195603 : e = e_fall, e_fall = e_taken, e_taken = e;
4042 : }
4043 : }
4044 :
4045 : /* If the "jumping" edge is a crossing edge, and the fall
4046 : through edge is non-crossing, leave things as they are. */
4047 2138337 : else if ((e_taken->flags & EDGE_CROSSING)
4048 71089 : && !(e_fall->flags & EDGE_CROSSING))
4049 71089 : continue;
4050 :
4051 : /* Otherwise we can try to invert the jump. This will
4052 : basically never fail, however, keep up the pretense. */
4053 2067248 : else if (invert_jump (bb_end_jump,
4054 : (e_fall->dest
4055 : == EXIT_BLOCK_PTR_FOR_FN (cfun)
4056 : ? NULL_RTX
4057 2067248 : : label_for_bb (e_fall->dest)), 0))
4058 : {
4059 2067248 : e_fall->flags &= ~EDGE_FALLTHRU;
4060 2067248 : gcc_checking_assert (could_fall_through
4061 : (e_taken->src, e_taken->dest));
4062 2067248 : e_taken->flags |= EDGE_FALLTHRU;
4063 2067248 : update_br_prob_note (bb);
4064 2067248 : if (LABEL_NUSES (ret_label) == 0
4065 2067248 : && single_pred_p (e_taken->dest))
4066 1286180 : delete_insn (as_a<rtx_insn *> (ret_label));
4067 2067248 : continue;
4068 : }
4069 : }
4070 1360968 : else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
4071 : {
4072 : /* If the old fallthru is still next or if
4073 : asm goto doesn't have a fallthru (e.g. when followed by
4074 : __builtin_unreachable ()), nothing to do. */
4075 1081 : if (! e_fall
4076 1015 : || bb->aux == e_fall->dest
4077 101 : || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4078 980 : continue;
4079 :
4080 : /* Otherwise we'll have to use the fallthru fixup below.
4081 : But avoid redirecting asm goto to EXIT. */
4082 : asm_goto = true;
4083 : }
4084 : else
4085 : {
4086 : /* Otherwise we have some return, switch or computed
4087 : jump. In the 99% case, there should not have been a
4088 : fallthru edge. */
4089 1359887 : gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
4090 1359887 : continue;
4091 : }
4092 : }
4093 : else
4094 : {
4095 : /* No fallthru implies a noreturn function with EH edges, or
4096 : something similarly bizarre. In any case, we don't need to
4097 : do anything. */
4098 10262252 : if (! e_fall)
4099 362774 : continue;
4100 :
4101 : /* If the fallthru block is still next, nothing to do. */
4102 9899478 : if (bb->aux == e_fall->dest)
4103 5064372 : continue;
4104 :
4105 : /* A fallthru to exit block. */
4106 4835106 : if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4107 1376224 : continue;
4108 : }
4109 :
4110 : /* If E_FALL->dest is just a return block, then we can emit a
4111 : return rather than a jump to the return block. */
4112 576975 : rtx_insn *ret, *use;
4113 576975 : basic_block dest;
4114 576975 : if (!asm_goto
4115 4035857 : && bb_is_just_return (e_fall->dest, &ret, &use)
4116 546 : && ((PATTERN (ret) == simple_return_rtx && targetm.have_simple_return ())
4117 0 : || (PATTERN (ret) == ret_rtx && targetm.have_return ())))
4118 : {
4119 546 : ret_label = PATTERN (ret);
4120 546 : dest = EXIT_BLOCK_PTR_FOR_FN (cfun);
4121 :
4122 546 : e_fall->flags &= ~EDGE_CROSSING;
4123 : /* E_FALL->dest might become unreachable as a result of
4124 : replacing the jump with a return. So arrange to remove
4125 : unreachable blocks. */
4126 546 : remove_unreachable_blocks = true;
4127 : }
4128 : else
4129 : {
4130 4035412 : dest = e_fall->dest;
4131 : }
4132 :
4133 : /* We got here if we need to add a new jump insn.
4134 : Note force_nonfallthru can delete E_FALL and thus we have to
4135 : save E_FALL->src prior to the call to force_nonfallthru. */
4136 4035958 : nb = force_nonfallthru_and_redirect (e_fall, dest, ret_label);
4137 4035958 : if (nb)
4138 : {
4139 755422 : nb->aux = bb->aux;
4140 755422 : bb->aux = nb;
4141 : /* Don't process this new block. */
4142 755422 : bb = nb;
4143 : }
4144 : }
4145 :
4146 2528071 : relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4147 :
4148 : /* Annoying special case - jump around dead jumptables left in the code. */
4149 27545089 : FOR_EACH_BB_FN (bb, cfun)
4150 : {
4151 25017018 : edge e = find_fallthru_edge (bb->succs);
4152 :
4153 25017018 : if (e && !can_fallthru (e->src, e->dest))
4154 71089 : force_nonfallthru (e);
4155 : }
4156 :
4157 : /* Ensure goto_locus from edges has some instructions with that locus in RTL
4158 : when not optimizing. */
4159 2528071 : if (!optimize && !DECL_IGNORED_P (current_function_decl))
4160 3860569 : FOR_EACH_BB_FN (bb, cfun)
4161 : {
4162 3427273 : edge e;
4163 3427273 : edge_iterator ei;
4164 :
4165 8147330 : FOR_EACH_EDGE (e, ei, bb->succs)
4166 4720057 : if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
4167 4720057 : && !(e->flags & EDGE_ABNORMAL))
4168 : {
4169 736075 : edge e2;
4170 736075 : edge_iterator ei2;
4171 736075 : basic_block dest, nb;
4172 736075 : rtx_insn *end;
4173 :
4174 736075 : insn = BB_END (e->src);
4175 736075 : end = PREV_INSN (BB_HEAD (e->src));
4176 736075 : while (insn != end
4177 889900 : && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
4178 153825 : insn = PREV_INSN (insn);
4179 1247217 : if (insn != end
4180 736075 : && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4181 525993 : continue;
4182 224933 : if (simplejump_p (BB_END (e->src))
4183 224933 : && !INSN_HAS_LOCATION (BB_END (e->src)))
4184 : {
4185 0 : INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
4186 0 : continue;
4187 : }
4188 224933 : dest = e->dest;
4189 224933 : if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4190 : {
4191 : /* Non-fallthru edges to the exit block cannot be split. */
4192 148718 : if (!(e->flags & EDGE_FALLTHRU))
4193 0 : continue;
4194 : }
4195 : else
4196 : {
4197 76215 : insn = BB_HEAD (dest);
4198 76215 : end = NEXT_INSN (BB_END (dest));
4199 300457 : while (insn != end && !NONDEBUG_INSN_P (insn))
4200 148027 : insn = NEXT_INSN (insn);
4201 47707 : if (insn != end && INSN_HAS_LOCATION (insn)
4202 121769 : && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4203 14851 : continue;
4204 : }
4205 210082 : nb = split_edge (e);
4206 210082 : if (!INSN_P (BB_END (nb)))
4207 210082 : BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
4208 : nb);
4209 210082 : INSN_LOCATION (BB_END (nb)) = e->goto_locus;
4210 :
4211 : /* If there are other incoming edges to the destination block
4212 : with the same goto locus, redirect them to the new block as
4213 : well, this can prevent other such blocks from being created
4214 : in subsequent iterations of the loop. */
4215 488523 : for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
4216 278441 : if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
4217 45647 : && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
4218 324088 : && e->goto_locus == e2->goto_locus)
4219 15587 : redirect_edge_and_branch (e2, nb);
4220 : else
4221 262854 : ei_next (&ei2);
4222 : }
4223 : }
4224 :
4225 : /* Replacing a jump with a return may have exposed an unreachable
4226 : block. Conditionally remove them if such transformations were
4227 : made. */
4228 2528071 : if (remove_unreachable_blocks)
4229 534 : delete_unreachable_blocks ();
4230 2528071 : }
4231 :
4232 : /* Perform sanity checks on the insn chain.
4233 : 1. Check that next/prev pointers are consistent in both the forward and
4234 : reverse direction.
4235 : 2. Count insns in chain, going both directions, and check if equal.
4236 : 3. Check that get_last_insn () returns the actual end of chain. */
4237 :
4238 : DEBUG_FUNCTION void
4239 5056066 : verify_insn_chain (void)
4240 : {
4241 5056066 : rtx_insn *x, *prevx, *nextx;
4242 5056066 : int insn_cnt1, insn_cnt2;
4243 :
4244 5056066 : for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
4245 609731261 : x != 0;
4246 604675195 : prevx = x, insn_cnt1++, x = NEXT_INSN (x))
4247 604675195 : gcc_assert (PREV_INSN (x) == prevx);
4248 :
4249 5056066 : gcc_assert (prevx == get_last_insn ());
4250 :
4251 : for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
4252 609731261 : x != 0;
4253 604675195 : nextx = x, insn_cnt2++, x = PREV_INSN (x))
4254 604675195 : gcc_assert (NEXT_INSN (x) == nextx);
4255 :
4256 5056066 : gcc_assert (insn_cnt1 == insn_cnt2);
4257 5056066 : }
4258 :
4259 : /* If we have assembler epilogues, the block falling through to exit must
4260 : be the last one in the reordered chain when we reach final. Ensure
4261 : that this condition is met. */
4262 : static void
4263 0 : fixup_fallthru_exit_predecessor (void)
4264 : {
4265 0 : edge e;
4266 0 : basic_block bb = NULL;
4267 :
4268 : /* This transformation is not valid before reload, because we might
4269 : separate a call from the instruction that copies the return
4270 : value. */
4271 0 : gcc_assert (reload_completed);
4272 :
4273 0 : e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4274 0 : if (e)
4275 0 : bb = e->src;
4276 :
4277 0 : if (bb && bb->aux)
4278 : {
4279 0 : basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4280 :
4281 : /* If the very first block is the one with the fall-through exit
4282 : edge, we have to split that block. */
4283 0 : if (c == bb)
4284 : {
4285 0 : bb = split_block_after_labels (bb)->dest;
4286 0 : bb->aux = c->aux;
4287 0 : c->aux = bb;
4288 0 : BB_FOOTER (bb) = BB_FOOTER (c);
4289 0 : BB_FOOTER (c) = NULL;
4290 : }
4291 :
4292 0 : while (c->aux != bb)
4293 : c = (basic_block) c->aux;
4294 :
4295 0 : c->aux = bb->aux;
4296 0 : while (c->aux)
4297 : c = (basic_block) c->aux;
4298 :
4299 0 : c->aux = bb;
4300 0 : bb->aux = NULL;
4301 : }
4302 0 : }
4303 :
4304 : /* In case there are more than one fallthru predecessors of exit, force that
4305 : there is only one. */
4306 :
4307 : static void
4308 2528071 : force_one_exit_fallthru (void)
4309 : {
4310 2528071 : edge e, predecessor = NULL;
4311 2528071 : bool more = false;
4312 2528071 : edge_iterator ei;
4313 2528071 : basic_block forwarder, bb;
4314 :
4315 5343762 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4316 2815692 : if (e->flags & EDGE_FALLTHRU)
4317 : {
4318 1376237 : if (predecessor == NULL)
4319 : predecessor = e;
4320 : else
4321 : {
4322 : more = true;
4323 : break;
4324 : }
4325 : }
4326 :
4327 2528071 : if (!more)
4328 2528070 : return;
4329 :
4330 : /* Exit has several fallthru predecessors. Create a forwarder block for
4331 : them. */
4332 1 : forwarder = split_edge (predecessor);
4333 1 : for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4334 3 : (e = ei_safe_edge (ei)); )
4335 : {
4336 2 : if (e->src == forwarder
4337 1 : || !(e->flags & EDGE_FALLTHRU))
4338 1 : ei_next (&ei);
4339 : else
4340 1 : redirect_edge_and_branch_force (e, forwarder);
4341 : }
4342 :
4343 : /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4344 : exit block. */
4345 5 : FOR_EACH_BB_FN (bb, cfun)
4346 : {
4347 5 : if (bb->aux == NULL && bb != forwarder)
4348 : {
4349 1 : bb->aux = forwarder;
4350 1 : break;
4351 : }
4352 : }
4353 : }
4354 :
4355 : /* Return true in case it is possible to duplicate the basic block BB. */
4356 :
4357 : static bool
4358 8330026 : cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4359 : {
4360 : /* Do not attempt to duplicate tablejumps, as we need to unshare
4361 : the dispatch table. This is difficult to do, as the instructions
4362 : computing jump destination may be hoisted outside the basic block. */
4363 8330026 : if (tablejump_p (BB_END (bb), NULL, NULL))
4364 : return false;
4365 :
4366 : /* Do not duplicate blocks containing insns that can't be copied. */
4367 8327602 : if (targetm.cannot_copy_insn_p)
4368 : {
4369 0 : rtx_insn *insn = BB_HEAD (bb);
4370 0 : while (1)
4371 : {
4372 0 : if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4373 : return false;
4374 0 : if (insn == BB_END (bb))
4375 : break;
4376 0 : insn = NEXT_INSN (insn);
4377 : }
4378 : }
4379 :
4380 : return true;
4381 : }
4382 :
4383 : rtx_insn *
4384 912342 : duplicate_insn_chain (rtx_insn *from, rtx_insn *to,
4385 : class loop *loop, copy_bb_data *id)
4386 : {
4387 912342 : rtx_insn *insn, *next, *copy;
4388 912342 : rtx_note *last;
4389 :
4390 : /* Avoid updating of boundaries of previous basic block. The
4391 : note will get removed from insn stream in fixup. */
4392 912342 : last = emit_note (NOTE_INSN_DELETED);
4393 :
4394 : /* Create copy at the end of INSN chain. The chain will
4395 : be reordered later. */
4396 6436658 : for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4397 : {
4398 5524316 : switch (GET_CODE (insn))
4399 : {
4400 1470841 : case DEBUG_INSN:
4401 : /* Don't duplicate label debug insns. */
4402 1470841 : if (DEBUG_BIND_INSN_P (insn)
4403 1115401 : && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4404 : break;
4405 : /* FALLTHRU */
4406 3736690 : case INSN:
4407 3736690 : case CALL_INSN:
4408 3736690 : case JUMP_INSN:
4409 3736690 : copy = emit_copy_of_insn_after (insn, get_last_insn ());
4410 3736690 : if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4411 499553 : && ANY_RETURN_P (JUMP_LABEL (insn)))
4412 178404 : JUMP_LABEL (copy) = JUMP_LABEL (insn);
4413 3736690 : maybe_copy_prologue_epilogue_insn (insn, copy);
4414 : /* If requested remap dependence info of cliques brought in
4415 : via inlining. */
4416 3736690 : if (id)
4417 : {
4418 2079700 : subrtx_iterator::array_type array;
4419 12502141 : FOR_EACH_SUBRTX (iter, array, PATTERN (insn), ALL)
4420 10436487 : if (MEM_P (*iter) && MEM_EXPR (*iter))
4421 : {
4422 317700 : tree op = MEM_EXPR (*iter);
4423 317700 : if (TREE_CODE (op) == WITH_SIZE_EXPR)
4424 0 : op = TREE_OPERAND (op, 0);
4425 353320 : while (handled_component_p (op))
4426 35620 : op = TREE_OPERAND (op, 0);
4427 317700 : if ((TREE_CODE (op) == MEM_REF
4428 317700 : || TREE_CODE (op) == TARGET_MEM_REF)
4429 298431 : && MR_DEPENDENCE_CLIQUE (op) > 1
4430 330638 : && (!loop
4431 12938 : || (MR_DEPENDENCE_CLIQUE (op)
4432 12938 : != loop->owned_clique)))
4433 : {
4434 1916 : if (!id->dependence_map)
4435 988 : id->dependence_map = new hash_map<dependence_hash,
4436 : unsigned short>;
4437 1916 : bool existed;
4438 1916 : unsigned short &newc = id->dependence_map->get_or_insert
4439 1916 : (MR_DEPENDENCE_CLIQUE (op), &existed);
4440 1916 : if (!existed)
4441 : {
4442 1000 : gcc_assert
4443 : (MR_DEPENDENCE_CLIQUE (op) <= cfun->last_clique);
4444 2000 : newc = get_new_clique (cfun);
4445 : }
4446 : /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4447 : since MEM_EXPR is shared so make a copy and
4448 : walk to the subtree again. */
4449 1916 : tree new_expr = unshare_expr (MEM_EXPR (*iter));
4450 1916 : tree orig_new_expr = new_expr;
4451 1916 : if (TREE_CODE (new_expr) == WITH_SIZE_EXPR)
4452 0 : new_expr = TREE_OPERAND (new_expr, 0);
4453 2529 : while (handled_component_p (new_expr))
4454 613 : new_expr = TREE_OPERAND (new_expr, 0);
4455 1916 : MR_DEPENDENCE_CLIQUE (new_expr) = newc;
4456 1916 : set_mem_expr (const_cast <rtx> (*iter), orig_new_expr);
4457 : }
4458 : }
4459 2079700 : }
4460 : break;
4461 :
4462 0 : case JUMP_TABLE_DATA:
4463 : /* Avoid copying of dispatch tables. We never duplicate
4464 : tablejumps, so this can hit only in case the table got
4465 : moved far from original jump.
4466 : Avoid copying following barrier as well if any
4467 : (and debug insns in between). */
4468 0 : for (next = NEXT_INSN (insn);
4469 0 : next != NEXT_INSN (to);
4470 0 : next = NEXT_INSN (next))
4471 0 : if (!DEBUG_INSN_P (next))
4472 : break;
4473 0 : if (next != NEXT_INSN (to) && BARRIER_P (next))
4474 5524316 : insn = next;
4475 : break;
4476 :
4477 : case CODE_LABEL:
4478 : break;
4479 :
4480 179697 : case BARRIER:
4481 179697 : emit_barrier ();
4482 179697 : break;
4483 :
4484 945115 : case NOTE:
4485 945115 : switch (NOTE_KIND (insn))
4486 : {
4487 : /* In case prologue is empty and function contain label
4488 : in first BB, we may want to copy the block. */
4489 : case NOTE_INSN_PROLOGUE_END:
4490 :
4491 : case NOTE_INSN_DELETED:
4492 : case NOTE_INSN_DELETED_LABEL:
4493 : case NOTE_INSN_DELETED_DEBUG_LABEL:
4494 : /* No problem to strip these. */
4495 : case NOTE_INSN_FUNCTION_BEG:
4496 : /* There is always just single entry to function. */
4497 : case NOTE_INSN_BASIC_BLOCK:
4498 : /* We should only switch text sections once. */
4499 : case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4500 : break;
4501 :
4502 175876 : case NOTE_INSN_EPILOGUE_BEG:
4503 175876 : case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4504 175876 : emit_note_copy (as_a <rtx_note *> (insn));
4505 175876 : break;
4506 :
4507 0 : default:
4508 : /* All other notes should have already been eliminated. */
4509 0 : gcc_unreachable ();
4510 : }
4511 : break;
4512 0 : default:
4513 0 : gcc_unreachable ();
4514 : }
4515 : }
4516 912342 : insn = NEXT_INSN (last);
4517 912342 : delete_insn (last);
4518 912342 : return insn;
4519 : }
4520 :
4521 : /* Create a duplicate of the basic block BB. */
4522 :
4523 : static basic_block
4524 730035 : cfg_layout_duplicate_bb (basic_block bb, copy_bb_data *id)
4525 : {
4526 730035 : rtx_insn *insn;
4527 730035 : basic_block new_bb;
4528 :
4529 730035 : class loop *loop = (id && current_loops) ? bb->loop_father : NULL;
4530 :
4531 730035 : insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb), loop, id);
4532 730035 : new_bb = create_basic_block (insn,
4533 : insn ? get_last_insn () : NULL,
4534 730035 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4535 :
4536 730035 : BB_COPY_PARTITION (new_bb, bb);
4537 730035 : if (BB_HEADER (bb))
4538 : {
4539 : insn = BB_HEADER (bb);
4540 3363 : while (NEXT_INSN (insn))
4541 : insn = NEXT_INSN (insn);
4542 2431 : insn = duplicate_insn_chain (BB_HEADER (bb), insn, loop, id);
4543 2431 : if (insn)
4544 0 : BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4545 : }
4546 :
4547 730035 : if (BB_FOOTER (bb))
4548 : {
4549 : insn = BB_FOOTER (bb);
4550 179700 : while (NEXT_INSN (insn))
4551 : insn = NEXT_INSN (insn);
4552 179667 : insn = duplicate_insn_chain (BB_FOOTER (bb), insn, loop, id);
4553 179667 : if (insn)
4554 179666 : BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4555 : }
4556 :
4557 730035 : return new_bb;
4558 : }
4559 :
4560 :
4561 : /* Main entry point to this module - initialize the datastructures for
4562 : CFG layout changes. It keeps LOOPS up-to-date if not null.
4563 :
4564 : FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4565 :
4566 : void
4567 2528070 : cfg_layout_initialize (int flags)
4568 : {
4569 2528070 : rtx_insn_list *x;
4570 2528070 : basic_block bb;
4571 :
4572 : /* Once bb partitioning is complete, cfg layout mode should not be
4573 : re-entered. Entering cfg layout mode may require fixups. As an
4574 : example, if edge forwarding performed when optimizing the cfg
4575 : layout required moving a block from the hot to the cold
4576 : section. This would create an illegal partitioning unless some
4577 : manual fixup was performed. */
4578 2528070 : gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4579 :
4580 2528070 : initialize_original_copy_tables ();
4581 :
4582 2528070 : cfg_layout_rtl_register_cfg_hooks ();
4583 :
4584 2528070 : record_effective_endpoints ();
4585 :
4586 : /* Make sure that the targets of non local gotos are marked. */
4587 2530447 : for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4588 : {
4589 2377 : bb = BLOCK_FOR_INSN (x->insn ());
4590 2377 : bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4591 : }
4592 :
4593 2528070 : cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4594 2528070 : }
4595 :
4596 : /* Splits superblocks. */
4597 : void
4598 62437 : break_superblocks (void)
4599 : {
4600 62437 : bool need = false;
4601 62437 : basic_block bb;
4602 :
4603 62437 : auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4604 62437 : bitmap_clear (superblocks);
4605 :
4606 3601179 : FOR_EACH_BB_FN (bb, cfun)
4607 3538742 : if (bb->flags & BB_SUPERBLOCK)
4608 : {
4609 207165 : bb->flags &= ~BB_SUPERBLOCK;
4610 207165 : bitmap_set_bit (superblocks, bb->index);
4611 207165 : need = true;
4612 : }
4613 :
4614 62437 : if (need)
4615 : {
4616 53303 : rebuild_jump_labels (get_insns ());
4617 53303 : find_many_sub_basic_blocks (superblocks);
4618 : }
4619 62437 : }
4620 :
4621 : /* Finalize the changes: reorder insn list according to the sequence specified
4622 : by aux pointers, enter compensation code, rebuild scope forest. */
4623 :
4624 : void
4625 2528071 : cfg_layout_finalize (void)
4626 : {
4627 2528071 : free_dominance_info (CDI_DOMINATORS);
4628 2528071 : force_one_exit_fallthru ();
4629 2528071 : rtl_register_cfg_hooks ();
4630 2528071 : if (reload_completed && !targetm.have_epilogue ())
4631 0 : fixup_fallthru_exit_predecessor ();
4632 2528071 : fixup_reorder_chain ();
4633 :
4634 2528071 : rebuild_jump_labels (get_insns ());
4635 2528071 : delete_dead_jumptables ();
4636 :
4637 2528071 : if (flag_checking)
4638 2528033 : verify_insn_chain ();
4639 2528071 : checking_verify_flow_info ();
4640 2528071 : }
4641 :
4642 :
4643 : /* Same as split_block but update cfg_layout structures. */
4644 :
4645 : static basic_block
4646 18088 : cfg_layout_split_block (basic_block bb, void *insnp)
4647 : {
4648 18088 : rtx insn = (rtx) insnp;
4649 18088 : basic_block new_bb = rtl_split_block (bb, insn);
4650 :
4651 18088 : BB_FOOTER (new_bb) = BB_FOOTER (bb);
4652 18088 : BB_FOOTER (bb) = NULL;
4653 :
4654 18088 : return new_bb;
4655 : }
4656 :
4657 : /* Redirect Edge to DEST. */
4658 : static edge
4659 10094188 : cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4660 : {
4661 10094188 : basic_block src = e->src;
4662 10094188 : edge ret;
4663 :
4664 10094188 : if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4665 : return NULL;
4666 :
4667 10094188 : if (e->dest == dest)
4668 : return e;
4669 :
4670 10094188 : if (e->flags & EDGE_CROSSING
4671 7 : && BB_PARTITION (e->src) == BB_PARTITION (dest)
4672 10094190 : && simplejump_p (BB_END (src)))
4673 : {
4674 1 : if (dump_file)
4675 0 : fprintf (dump_file,
4676 : "Removing crossing jump while redirecting edge form %i to %i\n",
4677 0 : e->src->index, dest->index);
4678 1 : delete_insn (BB_END (src));
4679 1 : remove_barriers_from_footer (src);
4680 1 : e->flags |= EDGE_FALLTHRU;
4681 : }
4682 :
4683 10094188 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4684 10094188 : && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4685 : {
4686 311407 : df_set_bb_dirty (src);
4687 311407 : return ret;
4688 : }
4689 :
4690 9782781 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4691 0 : && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4692 : {
4693 0 : if (dump_file)
4694 0 : fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4695 : e->src->index, dest->index);
4696 :
4697 0 : df_set_bb_dirty (e->src);
4698 0 : redirect_edge_succ (e, dest);
4699 0 : return e;
4700 : }
4701 :
4702 : /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4703 : in the case the basic block appears to be in sequence. Avoid this
4704 : transformation. */
4705 :
4706 9782781 : if (e->flags & EDGE_FALLTHRU)
4707 : {
4708 : /* Redirect any branch edges unified with the fallthru one. */
4709 4717629 : if (JUMP_P (BB_END (src))
4710 4717629 : && label_is_jump_target_p (BB_HEAD (e->dest),
4711 : BB_END (src)))
4712 : {
4713 170 : edge redirected;
4714 :
4715 170 : if (dump_file)
4716 0 : fprintf (dump_file, "Fallthru edge unified with branch "
4717 : "%i->%i redirected to %i\n",
4718 0 : e->src->index, e->dest->index, dest->index);
4719 170 : e->flags &= ~EDGE_FALLTHRU;
4720 170 : redirected = redirect_branch_edge (e, dest);
4721 170 : gcc_assert (redirected);
4722 170 : redirected->flags |= EDGE_FALLTHRU;
4723 170 : df_set_bb_dirty (redirected->src);
4724 170 : return redirected;
4725 : }
4726 : /* In case we are redirecting fallthru edge to the branch edge
4727 : of conditional jump, remove it. */
4728 4717459 : if (EDGE_COUNT (src->succs) == 2)
4729 : {
4730 : /* Find the edge that is different from E. */
4731 3608858 : edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4732 :
4733 3608858 : if (s->dest == dest
4734 2 : && any_condjump_p (BB_END (src))
4735 3608858 : && onlyjump_p (BB_END (src)))
4736 0 : delete_insn (BB_END (src));
4737 : }
4738 4717459 : if (dump_file)
4739 2201 : fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4740 2201 : e->src->index, e->dest->index, dest->index);
4741 4717459 : ret = redirect_edge_succ_nodup (e, dest);
4742 : }
4743 : else
4744 5065152 : ret = redirect_branch_edge (e, dest);
4745 :
4746 9782611 : if (!ret)
4747 : return NULL;
4748 :
4749 9782611 : fixup_partition_crossing (ret);
4750 : /* We don't want simplejumps in the insn stream during cfglayout. */
4751 9782611 : gcc_assert (!simplejump_p (BB_END (src)) || CROSSING_JUMP_P (BB_END (src)));
4752 :
4753 9782611 : df_set_bb_dirty (src);
4754 9782611 : return ret;
4755 : }
4756 :
4757 : /* Simple wrapper as we always can redirect fallthru edges. */
4758 : static basic_block
4759 4836076 : cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4760 : {
4761 4836076 : edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4762 :
4763 4836076 : gcc_assert (redirected);
4764 4836076 : return NULL;
4765 : }
4766 :
4767 : /* Same as delete_basic_block but update cfg_layout structures. */
4768 :
4769 : static void
4770 5509961 : cfg_layout_delete_block (basic_block bb)
4771 : {
4772 5509961 : rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4773 5509961 : rtx_insn **to;
4774 :
4775 5509961 : if (BB_HEADER (bb))
4776 : {
4777 72 : next = BB_HEAD (bb);
4778 72 : if (prev)
4779 72 : SET_NEXT_INSN (prev) = BB_HEADER (bb);
4780 : else
4781 0 : set_first_insn (BB_HEADER (bb));
4782 72 : SET_PREV_INSN (BB_HEADER (bb)) = prev;
4783 72 : insn = BB_HEADER (bb);
4784 73 : while (NEXT_INSN (insn))
4785 : insn = NEXT_INSN (insn);
4786 72 : SET_NEXT_INSN (insn) = next;
4787 72 : SET_PREV_INSN (next) = insn;
4788 : }
4789 5509961 : next = NEXT_INSN (BB_END (bb));
4790 5509961 : if (BB_FOOTER (bb))
4791 : {
4792 : insn = BB_FOOTER (bb);
4793 2829563 : while (insn)
4794 : {
4795 1414785 : if (BARRIER_P (insn))
4796 : {
4797 1414771 : if (PREV_INSN (insn))
4798 3 : SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4799 : else
4800 1414768 : BB_FOOTER (bb) = NEXT_INSN (insn);
4801 1414771 : if (NEXT_INSN (insn))
4802 4 : SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4803 : }
4804 1414785 : if (LABEL_P (insn))
4805 : break;
4806 1414784 : insn = NEXT_INSN (insn);
4807 : }
4808 1414779 : if (BB_FOOTER (bb))
4809 : {
4810 14 : insn = BB_END (bb);
4811 14 : SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4812 14 : SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4813 30 : while (NEXT_INSN (insn))
4814 : insn = NEXT_INSN (insn);
4815 14 : SET_NEXT_INSN (insn) = next;
4816 14 : if (next)
4817 12 : SET_PREV_INSN (next) = insn;
4818 : else
4819 2 : set_last_insn (insn);
4820 : }
4821 : }
4822 5509961 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4823 5475667 : to = &BB_HEADER (bb->next_bb);
4824 : else
4825 : to = &cfg_layout_function_footer;
4826 :
4827 5509961 : rtl_delete_block (bb);
4828 :
4829 5509961 : if (prev)
4830 5509961 : prev = NEXT_INSN (prev);
4831 : else
4832 0 : prev = get_insns ();
4833 5509961 : if (next)
4834 5475664 : next = PREV_INSN (next);
4835 : else
4836 34297 : next = get_last_insn ();
4837 :
4838 11019922 : if (next && NEXT_INSN (next) != prev)
4839 : {
4840 1639 : remaints = unlink_insn_chain (prev, next);
4841 1639 : insn = remaints;
4842 3535 : while (NEXT_INSN (insn))
4843 : insn = NEXT_INSN (insn);
4844 1639 : SET_NEXT_INSN (insn) = *to;
4845 1639 : if (*to)
4846 327 : SET_PREV_INSN (*to) = insn;
4847 1639 : *to = remaints;
4848 : }
4849 5509961 : }
4850 :
4851 : /* Return true when blocks A and B can be safely merged. */
4852 :
4853 : static bool
4854 3156784 : cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4855 : {
4856 : /* If we are partitioning hot/cold basic blocks, we don't want to
4857 : mess up unconditional or indirect jumps that cross between hot
4858 : and cold sections.
4859 :
4860 : Basic block partitioning may result in some jumps that appear to
4861 : be optimizable (or blocks that appear to be mergeable), but which really
4862 : must be left untouched (they are required to make it safely across
4863 : partition boundaries). See the comments at the top of
4864 : bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
4865 :
4866 3156784 : if (BB_PARTITION (a) != BB_PARTITION (b))
4867 : return false;
4868 :
4869 : /* Protect the loop latches. */
4870 2980110 : if (current_loops && b->loop_father->latch == b)
4871 : return false;
4872 :
4873 : /* If we would end up moving B's instructions, make sure it doesn't fall
4874 : through into the exit block, since we cannot recover from a fallthrough
4875 : edge into the exit block occurring in the middle of a function. */
4876 2599043 : if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4877 : {
4878 1615465 : edge e = find_fallthru_edge (b->succs);
4879 1615465 : if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4880 : return false;
4881 : }
4882 :
4883 : /* There must be exactly one edge in between the blocks. */
4884 1901443 : return (single_succ_p (a)
4885 1901443 : && single_succ (a) == b
4886 1901443 : && single_pred_p (b) == 1
4887 1877924 : && a != b
4888 : /* Must be simple edge. */
4889 1877924 : && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4890 1877924 : && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4891 1877924 : && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4892 : /* If the jump insn has side effects, we can't kill the edge.
4893 : When not optimizing, try_redirect_by_replacing_jump will
4894 : not allow us to redirect an edge by replacing a table jump. */
4895 3779367 : && (!JUMP_P (BB_END (a))
4896 63298 : || ((!optimize || reload_completed)
4897 51628 : ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4898 : }
4899 :
4900 : /* Merge block A and B. The blocks must be mergeable. */
4901 :
4902 : static void
4903 937662 : cfg_layout_merge_blocks (basic_block a, basic_block b)
4904 : {
4905 : /* If B is a forwarder block whose outgoing edge has no location, we'll
4906 : propagate the locus of the edge between A and B onto it. */
4907 937662 : const bool forward_edge_locus
4908 937662 : = (b->flags & BB_FORWARDER_BLOCK) != 0
4909 937662 : && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
4910 937662 : rtx_insn *insn;
4911 :
4912 937662 : gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4913 :
4914 937662 : if (dump_file)
4915 74 : fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4916 : a->index);
4917 :
4918 : /* If there was a CODE_LABEL beginning B, delete it. */
4919 937662 : if (LABEL_P (BB_HEAD (b)))
4920 : {
4921 396925 : delete_insn (BB_HEAD (b));
4922 : }
4923 :
4924 : /* We should have fallthru edge in a, or we can do dummy redirection to get
4925 : it cleaned up. */
4926 937662 : if (JUMP_P (BB_END (a)))
4927 24514 : try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4928 937662 : gcc_assert (!JUMP_P (BB_END (a)));
4929 :
4930 : /* If not optimizing, preserve the locus of the single edge between
4931 : blocks A and B if necessary by emitting a nop. */
4932 937662 : if (!optimize
4933 2637 : && !forward_edge_locus
4934 939858 : && !DECL_IGNORED_P (current_function_decl))
4935 2196 : emit_nop_for_unique_locus_between (a, b);
4936 :
4937 : /* Move things from b->footer after a->footer. */
4938 937662 : if (BB_FOOTER (b))
4939 : {
4940 206805 : if (!BB_FOOTER (a))
4941 206804 : BB_FOOTER (a) = BB_FOOTER (b);
4942 : else
4943 : {
4944 : rtx_insn *last = BB_FOOTER (a);
4945 :
4946 1 : while (NEXT_INSN (last))
4947 : last = NEXT_INSN (last);
4948 1 : SET_NEXT_INSN (last) = BB_FOOTER (b);
4949 1 : SET_PREV_INSN (BB_FOOTER (b)) = last;
4950 : }
4951 206805 : BB_FOOTER (b) = NULL;
4952 : }
4953 :
4954 : /* Move things from b->header before a->footer.
4955 : Note that this may include dead tablejump data, but we don't clean
4956 : those up until we go out of cfglayout mode. */
4957 937662 : if (BB_HEADER (b))
4958 : {
4959 2213 : if (! BB_FOOTER (a))
4960 1120 : BB_FOOTER (a) = BB_HEADER (b);
4961 : else
4962 : {
4963 : rtx_insn *last = BB_HEADER (b);
4964 :
4965 1230 : while (NEXT_INSN (last))
4966 : last = NEXT_INSN (last);
4967 1093 : SET_NEXT_INSN (last) = BB_FOOTER (a);
4968 1093 : SET_PREV_INSN (BB_FOOTER (a)) = last;
4969 1093 : BB_FOOTER (a) = BB_HEADER (b);
4970 : }
4971 2213 : BB_HEADER (b) = NULL;
4972 : }
4973 :
4974 : /* In the case basic blocks are not adjacent, move them around. */
4975 937662 : if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4976 : {
4977 453682 : insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4978 :
4979 453682 : emit_insn_after_noloc (insn, BB_END (a), a);
4980 : }
4981 : /* Otherwise just re-associate the instructions. */
4982 : else
4983 : {
4984 483980 : insn = BB_HEAD (b);
4985 483980 : BB_END (a) = BB_END (b);
4986 : }
4987 :
4988 : /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4989 : We need to explicitly call. */
4990 937662 : update_bb_for_insn_chain (insn, BB_END (b), a);
4991 :
4992 : /* Skip possible DELETED_LABEL insn. */
4993 937662 : if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4994 0 : insn = NEXT_INSN (insn);
4995 937662 : gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4996 937662 : BB_HEAD (b) = BB_END (b) = NULL;
4997 937662 : delete_insn (insn);
4998 :
4999 937662 : df_bb_delete (b->index);
5000 :
5001 937662 : if (forward_edge_locus)
5002 193565 : EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
5003 :
5004 937662 : if (dump_file)
5005 74 : fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
5006 937662 : }
5007 :
5008 : /* Split edge E. */
5009 :
5010 : static basic_block
5011 3517258 : cfg_layout_split_edge (edge e)
5012 : {
5013 3517258 : basic_block new_bb =
5014 7034516 : create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
5015 3517258 : ? NEXT_INSN (BB_END (e->src)) : get_insns (),
5016 : NULL_RTX, e->src);
5017 :
5018 3517258 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5019 1 : BB_COPY_PARTITION (new_bb, e->src);
5020 : else
5021 3517257 : BB_COPY_PARTITION (new_bb, e->dest);
5022 3517258 : make_edge (new_bb, e->dest, EDGE_FALLTHRU);
5023 3517258 : redirect_edge_and_branch_force (e, new_bb);
5024 :
5025 3517258 : return new_bb;
5026 : }
5027 :
5028 : /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
5029 :
5030 : static void
5031 1143 : rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
5032 : {
5033 1143 : }
5034 :
5035 : /* Return true if BB contains only labels or non-executable
5036 : instructions. */
5037 :
5038 : static bool
5039 0 : rtl_block_empty_p (basic_block bb)
5040 : {
5041 0 : rtx_insn *insn;
5042 :
5043 0 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
5044 0 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5045 : return true;
5046 :
5047 0 : FOR_BB_INSNS (bb, insn)
5048 0 : if (NONDEBUG_INSN_P (insn)
5049 0 : && (!any_uncondjump_p (insn) || !onlyjump_p (insn)))
5050 0 : return false;
5051 :
5052 : return true;
5053 : }
5054 :
5055 : /* Split a basic block if it ends with a conditional branch and if
5056 : the other part of the block is not empty. */
5057 :
5058 : static basic_block
5059 0 : rtl_split_block_before_cond_jump (basic_block bb)
5060 : {
5061 0 : rtx_insn *insn;
5062 0 : rtx_insn *split_point = NULL;
5063 0 : rtx_insn *last = NULL;
5064 0 : bool found_code = false;
5065 :
5066 0 : FOR_BB_INSNS (bb, insn)
5067 : {
5068 0 : if (any_condjump_p (insn))
5069 : split_point = last;
5070 0 : else if (NONDEBUG_INSN_P (insn))
5071 0 : found_code = true;
5072 0 : last = insn;
5073 : }
5074 :
5075 : /* Did not find everything. */
5076 0 : if (found_code && split_point)
5077 0 : return split_block (bb, split_point)->dest;
5078 : else
5079 : return NULL;
5080 : }
5081 :
5082 : /* Return true if BB ends with a call, possibly followed by some
5083 : instructions that must stay with the call, false otherwise. */
5084 :
5085 : static bool
5086 9742377 : rtl_block_ends_with_call_p (basic_block bb)
5087 : {
5088 9742377 : rtx_insn *insn = BB_END (bb);
5089 :
5090 9742377 : while (!CALL_P (insn)
5091 11078622 : && insn != BB_HEAD (bb)
5092 23430921 : && (keep_with_call_p (insn)
5093 11026922 : || NOTE_P (insn)
5094 10905324 : || DEBUG_INSN_P (insn)))
5095 2661265 : insn = PREV_INSN (insn);
5096 9742377 : return (CALL_P (insn));
5097 : }
5098 :
5099 : /* Return true if BB ends with a conditional branch, false otherwise. */
5100 :
5101 : static bool
5102 0 : rtl_block_ends_with_condjump_p (const_basic_block bb)
5103 : {
5104 0 : return any_condjump_p (BB_END (bb));
5105 : }
5106 :
5107 : /* Return true if we need to add fake edge to exit.
5108 : Helper function for rtl_flow_call_edges_add. */
5109 :
5110 : static bool
5111 0 : need_fake_edge_p (const rtx_insn *insn)
5112 : {
5113 0 : if (!INSN_P (insn))
5114 : return false;
5115 :
5116 0 : if ((CALL_P (insn)
5117 0 : && !SIBLING_CALL_P (insn)
5118 0 : && !find_reg_note (insn, REG_NORETURN, NULL)
5119 0 : && !(RTL_CONST_OR_PURE_CALL_P (insn))))
5120 : return true;
5121 :
5122 0 : return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5123 0 : && MEM_VOLATILE_P (PATTERN (insn)))
5124 0 : || (GET_CODE (PATTERN (insn)) == PARALLEL
5125 0 : && asm_noperands (insn) != -1
5126 0 : && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
5127 0 : || GET_CODE (PATTERN (insn)) == ASM_INPUT);
5128 : }
5129 :
5130 : /* Add fake edges to the function exit for any non constant and non noreturn
5131 : calls, volatile inline assembly in the bitmap of blocks specified by
5132 : BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5133 : that were split.
5134 :
5135 : The goal is to expose cases in which entering a basic block does not imply
5136 : that all subsequent instructions must be executed. */
5137 :
5138 : static int
5139 0 : rtl_flow_call_edges_add (sbitmap blocks)
5140 : {
5141 0 : int i;
5142 0 : int blocks_split = 0;
5143 0 : int last_bb = last_basic_block_for_fn (cfun);
5144 0 : bool check_last_block = false;
5145 :
5146 0 : if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
5147 : return 0;
5148 :
5149 0 : if (! blocks)
5150 : check_last_block = true;
5151 : else
5152 0 : check_last_block = bitmap_bit_p (blocks,
5153 0 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
5154 :
5155 : /* In the last basic block, before epilogue generation, there will be
5156 : a fallthru edge to EXIT. Special care is required if the last insn
5157 : of the last basic block is a call because make_edge folds duplicate
5158 : edges, which would result in the fallthru edge also being marked
5159 : fake, which would result in the fallthru edge being removed by
5160 : remove_fake_edges, which would result in an invalid CFG.
5161 :
5162 : Moreover, we can't elide the outgoing fake edge, since the block
5163 : profiler needs to take this into account in order to solve the minimal
5164 : spanning tree in the case that the call doesn't return.
5165 :
5166 : Handle this by adding a dummy instruction in a new last basic block. */
5167 0 : if (check_last_block)
5168 : {
5169 0 : basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
5170 0 : rtx_insn *insn = BB_END (bb);
5171 :
5172 : /* Back up past insns that must be kept in the same block as a call. */
5173 0 : while (insn != BB_HEAD (bb)
5174 0 : && keep_with_call_p (insn))
5175 0 : insn = PREV_INSN (insn);
5176 :
5177 0 : if (need_fake_edge_p (insn))
5178 : {
5179 0 : edge e;
5180 :
5181 0 : e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5182 0 : if (e)
5183 : {
5184 0 : insert_insn_on_edge (gen_use (const0_rtx), e);
5185 0 : commit_edge_insertions ();
5186 : }
5187 : }
5188 : }
5189 :
5190 : /* Now add fake edges to the function exit for any non constant
5191 : calls since there is no way that we can determine if they will
5192 : return or not... */
5193 :
5194 0 : for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
5195 : {
5196 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
5197 0 : rtx_insn *insn;
5198 0 : rtx_insn *prev_insn;
5199 :
5200 0 : if (!bb)
5201 0 : continue;
5202 :
5203 0 : if (blocks && !bitmap_bit_p (blocks, i))
5204 0 : continue;
5205 :
5206 0 : for (insn = BB_END (bb); ; insn = prev_insn)
5207 : {
5208 0 : prev_insn = PREV_INSN (insn);
5209 0 : if (need_fake_edge_p (insn))
5210 : {
5211 0 : edge e;
5212 0 : rtx_insn *split_at_insn = insn;
5213 :
5214 : /* Don't split the block between a call and an insn that should
5215 : remain in the same block as the call. */
5216 0 : if (CALL_P (insn))
5217 0 : while (split_at_insn != BB_END (bb)
5218 0 : && keep_with_call_p (NEXT_INSN (split_at_insn)))
5219 0 : split_at_insn = NEXT_INSN (split_at_insn);
5220 :
5221 : /* The handling above of the final block before the epilogue
5222 : should be enough to verify that there is no edge to the exit
5223 : block in CFG already. Calling make_edge in such case would
5224 : cause us to mark that edge as fake and remove it later. */
5225 :
5226 0 : if (flag_checking && split_at_insn == BB_END (bb))
5227 : {
5228 0 : e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5229 0 : gcc_assert (e == NULL);
5230 : }
5231 :
5232 : /* Note that the following may create a new basic block
5233 : and renumber the existing basic blocks. */
5234 0 : if (split_at_insn != BB_END (bb))
5235 : {
5236 0 : e = split_block (bb, split_at_insn);
5237 0 : if (e)
5238 0 : blocks_split++;
5239 : }
5240 :
5241 0 : edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
5242 0 : ne->probability = profile_probability::guessed_never ();
5243 : }
5244 :
5245 0 : if (insn == BB_HEAD (bb))
5246 : break;
5247 : }
5248 : }
5249 :
5250 0 : if (blocks_split)
5251 0 : verify_flow_info ();
5252 :
5253 : return blocks_split;
5254 : }
5255 :
5256 : /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5257 : the conditional branch target, SECOND_HEAD should be the fall-thru
5258 : there is no need to handle this here the loop versioning code handles
5259 : this. the reason for SECON_HEAD is that it is needed for condition
5260 : in trees, and this should be of the same type since it is a hook. */
5261 : static void
5262 0 : rtl_lv_add_condition_to_bb (basic_block first_head ,
5263 : basic_block second_head ATTRIBUTE_UNUSED,
5264 : basic_block cond_bb, void *comp_rtx)
5265 : {
5266 0 : rtx_code_label *label;
5267 0 : rtx_insn *seq, *jump;
5268 0 : rtx op0 = XEXP ((rtx)comp_rtx, 0);
5269 0 : rtx op1 = XEXP ((rtx)comp_rtx, 1);
5270 0 : enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
5271 0 : machine_mode mode;
5272 :
5273 :
5274 0 : label = block_label (first_head);
5275 0 : mode = GET_MODE (op0);
5276 0 : if (mode == VOIDmode)
5277 0 : mode = GET_MODE (op1);
5278 :
5279 0 : start_sequence ();
5280 0 : op0 = force_operand (op0, NULL_RTX);
5281 0 : op1 = force_operand (op1, NULL_RTX);
5282 0 : do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label,
5283 : profile_probability::uninitialized ());
5284 0 : jump = get_last_insn ();
5285 0 : JUMP_LABEL (jump) = label;
5286 0 : LABEL_NUSES (label)++;
5287 0 : seq = end_sequence ();
5288 :
5289 : /* Add the new cond, in the new head. */
5290 0 : emit_insn_after (seq, BB_END (cond_bb));
5291 0 : }
5292 :
5293 :
5294 : /* Given a block B with unconditional branch at its end, get the
5295 : store the return the branch edge and the fall-thru edge in
5296 : BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5297 : static void
5298 0 : rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
5299 : edge *fallthru_edge)
5300 : {
5301 0 : edge e = EDGE_SUCC (b, 0);
5302 :
5303 0 : if (e->flags & EDGE_FALLTHRU)
5304 : {
5305 0 : *fallthru_edge = e;
5306 0 : *branch_edge = EDGE_SUCC (b, 1);
5307 : }
5308 : else
5309 : {
5310 0 : *branch_edge = e;
5311 0 : *fallthru_edge = EDGE_SUCC (b, 1);
5312 : }
5313 0 : }
5314 :
5315 : void
5316 28536309 : init_rtl_bb_info (basic_block bb)
5317 : {
5318 28536309 : gcc_assert (!bb->il.x.rtl);
5319 28536309 : bb->il.x.head_ = NULL;
5320 28536309 : bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
5321 28536309 : }
5322 :
5323 : static bool
5324 2137 : rtl_bb_info_initialized_p (basic_block bb)
5325 : {
5326 2137 : return bb->il.x.rtl;
5327 : }
5328 :
5329 : /* Returns true if it is possible to remove edge E by redirecting
5330 : it to the destination of the other edge from E->src. */
5331 :
5332 : static bool
5333 152229 : rtl_can_remove_branch_p (const_edge e)
5334 : {
5335 152229 : const_basic_block src = e->src;
5336 152229 : const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5337 152229 : const rtx_insn *insn = BB_END (src);
5338 152229 : rtx set;
5339 :
5340 : /* The conditions are taken from try_redirect_by_replacing_jump. */
5341 152229 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5342 : return false;
5343 :
5344 152229 : if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5345 : return false;
5346 :
5347 152229 : if (BB_PARTITION (src) != BB_PARTITION (target))
5348 : return false;
5349 :
5350 152229 : if (!onlyjump_p (insn)
5351 152229 : || tablejump_p (insn, NULL, NULL))
5352 0 : return false;
5353 :
5354 152229 : set = single_set (insn);
5355 152229 : if (!set || side_effects_p (set))
5356 0 : return false;
5357 :
5358 : return true;
5359 : }
5360 :
5361 : static basic_block
5362 40921 : rtl_duplicate_bb (basic_block bb, copy_bb_data *id)
5363 : {
5364 40921 : bb = cfg_layout_duplicate_bb (bb, id);
5365 40921 : bb->aux = NULL;
5366 40921 : return bb;
5367 : }
5368 :
5369 : /* Do book-keeping of basic block BB for the profile consistency checker.
5370 : Store the counting in RECORD. */
5371 : static void
5372 0 : rtl_account_profile_record (basic_block bb, struct profile_record *record)
5373 : {
5374 0 : rtx_insn *insn;
5375 0 : FOR_BB_INSNS (bb, insn)
5376 0 : if (INSN_P (insn))
5377 : {
5378 0 : record->size += insn_cost (insn, false);
5379 0 : if (profile_info)
5380 : {
5381 0 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().initialized_p ()
5382 0 : && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
5383 0 : && bb->count.ipa ().initialized_p ())
5384 0 : record->time
5385 0 : += insn_cost (insn, true) * bb->count.ipa ().to_gcov_type ();
5386 : }
5387 0 : else if (bb->count.initialized_p ()
5388 0 : && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
5389 0 : record->time
5390 0 : += insn_cost (insn, true)
5391 0 : * bb->count.to_sreal_scale
5392 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
5393 : else
5394 0 : record->time += insn_cost (insn, true);
5395 : }
5396 0 : }
5397 :
5398 : /* Implementation of CFG manipulation for linearized RTL. */
5399 : const struct cfg_hooks rtl_cfg_hooks = {
5400 : IR_RTL_CFGRTL,
5401 : rtl_verify_flow_info,
5402 : rtl_dump_bb,
5403 : rtl_dump_bb_for_graph,
5404 : rtl_dump_bb_as_sarif_properties,
5405 : rtl_create_basic_block,
5406 : rtl_redirect_edge_and_branch,
5407 : rtl_redirect_edge_and_branch_force,
5408 : rtl_can_remove_branch_p,
5409 : rtl_delete_block,
5410 : rtl_split_block,
5411 : rtl_move_block_after,
5412 : rtl_can_merge_blocks, /* can_merge_blocks_p */
5413 : rtl_merge_blocks,
5414 : rtl_predict_edge,
5415 : rtl_predicted_by_p,
5416 : cfg_layout_can_duplicate_bb_p,
5417 : rtl_duplicate_bb,
5418 : rtl_split_edge,
5419 : rtl_make_forwarder_block,
5420 : rtl_tidy_fallthru_edge,
5421 : rtl_force_nonfallthru,
5422 : rtl_block_ends_with_call_p,
5423 : rtl_block_ends_with_condjump_p,
5424 : rtl_flow_call_edges_add,
5425 : NULL, /* execute_on_growing_pred */
5426 : NULL, /* execute_on_shrinking_pred */
5427 : NULL, /* duplicate loop for trees */
5428 : NULL, /* lv_add_condition_to_bb */
5429 : NULL, /* lv_adjust_loop_header_phi*/
5430 : NULL, /* extract_cond_bb_edges */
5431 : NULL, /* flush_pending_stmts */
5432 : rtl_block_empty_p, /* block_empty_p */
5433 : rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5434 : rtl_account_profile_record,
5435 : };
5436 :
5437 : /* Implementation of CFG manipulation for cfg layout RTL, where
5438 : basic block connected via fallthru edges does not have to be adjacent.
5439 : This representation will hopefully become the default one in future
5440 : version of the compiler. */
5441 :
5442 : const struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5443 : IR_RTL_CFGLAYOUT,
5444 : rtl_verify_flow_info_1,
5445 : rtl_dump_bb,
5446 : rtl_dump_bb_for_graph,
5447 : rtl_dump_bb_as_sarif_properties,
5448 : cfg_layout_create_basic_block,
5449 : cfg_layout_redirect_edge_and_branch,
5450 : cfg_layout_redirect_edge_and_branch_force,
5451 : rtl_can_remove_branch_p,
5452 : cfg_layout_delete_block,
5453 : cfg_layout_split_block,
5454 : rtl_move_block_after,
5455 : cfg_layout_can_merge_blocks_p,
5456 : cfg_layout_merge_blocks,
5457 : rtl_predict_edge,
5458 : rtl_predicted_by_p,
5459 : cfg_layout_can_duplicate_bb_p,
5460 : cfg_layout_duplicate_bb,
5461 : cfg_layout_split_edge,
5462 : rtl_make_forwarder_block,
5463 : NULL, /* tidy_fallthru_edge */
5464 : rtl_force_nonfallthru,
5465 : rtl_block_ends_with_call_p,
5466 : rtl_block_ends_with_condjump_p,
5467 : rtl_flow_call_edges_add,
5468 : NULL, /* execute_on_growing_pred */
5469 : NULL, /* execute_on_shrinking_pred */
5470 : duplicate_loop_body_to_header_edge, /* duplicate loop for rtl */
5471 : rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5472 : NULL, /* lv_adjust_loop_header_phi*/
5473 : rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5474 : NULL, /* flush_pending_stmts */
5475 : rtl_block_empty_p, /* block_empty_p */
5476 : rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5477 : rtl_account_profile_record,
5478 : };
5479 :
5480 : #include "gt-cfgrtl.h"
5481 :
5482 : #if __GNUC__ >= 10
5483 : # pragma GCC diagnostic pop
5484 : #endif
|
