1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987-2018 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 optimizer of the control flow. The main entry point is
21 cleanup_cfg. Following optimizations are performed:
22
23 - Unreachable blocks removal
24 - Edge forwarding (edge to the forwarder block is forwarded to its
25 successor. Simplification of the branch instruction is performed by
26 underlying infrastructure so branch can be converted to simplejump or
27 eliminated).
28 - Cross jumping (tail merging)
29 - Conditional jump-around-simplejump simplification
30 - Basic block merging. */
31
32 #include "config.h"
33 #include "system.h"
34 #include "coretypes.h"
35 #include "backend.h"
36 #include "target.h"
37 #include "rtl.h"
38 #include "tree.h"
39 #include "cfghooks.h"
40 #include "df.h"
41 #include "memmodel.h"
42 #include "tm_p.h"
43 #include "insn-config.h"
44 #include "emit-rtl.h"
45 #include "cselib.h"
46 #include "params.h"
47 #include "tree-pass.h"
48 #include "cfgloop.h"
49 #include "cfgrtl.h"
50 #include "cfganal.h"
51 #include "cfgbuild.h"
52 #include "cfgcleanup.h"
53 #include "dce.h"
54 #include "dbgcnt.h"
55 #include "rtl-iter.h"
56
57 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
58
59 /* Set to true when we are running first pass of try_optimize_cfg loop. */
60 static bool first_pass;
61
62 /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg. */
63 static bool crossjumps_occurred;
64
65 /* Set to true if we couldn't run an optimization due to stale liveness
66 information; we should run df_analyze to enable more opportunities. */
67 static bool block_was_dirty;
68
69 static bool try_crossjump_to_edge (int, edge, edge, enum replace_direction);
70 static bool try_crossjump_bb (int, basic_block);
71 static bool outgoing_edges_match (int, basic_block, basic_block);
72 static enum replace_direction old_insns_match_p (int, rtx_insn *, rtx_insn *);
73
74 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
75 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
76 static bool try_optimize_cfg (int);
77 static bool try_simplify_condjump (basic_block);
78 static bool try_forward_edges (int, basic_block);
79 static edge thread_jump (edge, basic_block);
80 static bool mark_effect (rtx, bitmap);
81 static void notice_new_block (basic_block);
82 static void update_forwarder_flag (basic_block);
83 static void merge_memattrs (rtx, rtx);
84
85 /* Set flags for newly created block. */
86
87 static void
notice_new_block(basic_block bb)88 notice_new_block (basic_block bb)
89 {
90 if (!bb)
91 return;
92
93 if (forwarder_block_p (bb))
94 bb->flags |= BB_FORWARDER_BLOCK;
95 }
96
97 /* Recompute forwarder flag after block has been modified. */
98
99 static void
update_forwarder_flag(basic_block bb)100 update_forwarder_flag (basic_block bb)
101 {
102 if (forwarder_block_p (bb))
103 bb->flags |= BB_FORWARDER_BLOCK;
104 else
105 bb->flags &= ~BB_FORWARDER_BLOCK;
106 }
107
108 /* Simplify a conditional jump around an unconditional jump.
109 Return true if something changed. */
110
111 static bool
try_simplify_condjump(basic_block cbranch_block)112 try_simplify_condjump (basic_block cbranch_block)
113 {
114 basic_block jump_block, jump_dest_block, cbranch_dest_block;
115 edge cbranch_jump_edge, cbranch_fallthru_edge;
116 rtx_insn *cbranch_insn;
117
118 /* Verify that there are exactly two successors. */
119 if (EDGE_COUNT (cbranch_block->succs) != 2)
120 return false;
121
122 /* Verify that we've got a normal conditional branch at the end
123 of the block. */
124 cbranch_insn = BB_END (cbranch_block);
125 if (!any_condjump_p (cbranch_insn))
126 return false;
127
128 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
129 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
130
131 /* The next block must not have multiple predecessors, must not
132 be the last block in the function, and must contain just the
133 unconditional jump. */
134 jump_block = cbranch_fallthru_edge->dest;
135 if (!single_pred_p (jump_block)
136 || jump_block->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
137 || !FORWARDER_BLOCK_P (jump_block))
138 return false;
139 jump_dest_block = single_succ (jump_block);
140
141 /* If we are partitioning hot/cold basic blocks, we don't want to
142 mess up unconditional or indirect jumps that cross between hot
143 and cold sections.
144
145 Basic block partitioning may result in some jumps that appear to
146 be optimizable (or blocks that appear to be mergeable), but which really
147 must be left untouched (they are required to make it safely across
148 partition boundaries). See the comments at the top of
149 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
150
151 if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
152 || (cbranch_jump_edge->flags & EDGE_CROSSING))
153 return false;
154
155 /* The conditional branch must target the block after the
156 unconditional branch. */
157 cbranch_dest_block = cbranch_jump_edge->dest;
158
159 if (cbranch_dest_block == EXIT_BLOCK_PTR_FOR_FN (cfun)
160 || jump_dest_block == EXIT_BLOCK_PTR_FOR_FN (cfun)
161 || !can_fallthru (jump_block, cbranch_dest_block))
162 return false;
163
164 /* Invert the conditional branch. */
165 if (!invert_jump (as_a <rtx_jump_insn *> (cbranch_insn),
166 block_label (jump_dest_block), 0))
167 return false;
168
169 if (dump_file)
170 fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
171 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
172
173 /* Success. Update the CFG to match. Note that after this point
174 the edge variable names appear backwards; the redirection is done
175 this way to preserve edge profile data. */
176 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
177 cbranch_dest_block);
178 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
179 jump_dest_block);
180 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
181 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
182 update_br_prob_note (cbranch_block);
183
184 /* Delete the block with the unconditional jump, and clean up the mess. */
185 delete_basic_block (jump_block);
186 tidy_fallthru_edge (cbranch_jump_edge);
187 update_forwarder_flag (cbranch_block);
188
189 return true;
190 }
191
192 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
193 on register. Used by jump threading. */
194
195 static bool
mark_effect(rtx exp,regset nonequal)196 mark_effect (rtx exp, regset nonequal)
197 {
198 rtx dest;
199 switch (GET_CODE (exp))
200 {
201 /* In case we do clobber the register, mark it as equal, as we know the
202 value is dead so it don't have to match. */
203 case CLOBBER:
204 dest = XEXP (exp, 0);
205 if (REG_P (dest))
206 bitmap_clear_range (nonequal, REGNO (dest), REG_NREGS (dest));
207 return false;
208
209 case SET:
210 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
211 return false;
212 dest = SET_DEST (exp);
213 if (dest == pc_rtx)
214 return false;
215 if (!REG_P (dest))
216 return true;
217 bitmap_set_range (nonequal, REGNO (dest), REG_NREGS (dest));
218 return false;
219
220 default:
221 return false;
222 }
223 }
224
225 /* Return true if X contains a register in NONEQUAL. */
226 static bool
mentions_nonequal_regs(const_rtx x,regset nonequal)227 mentions_nonequal_regs (const_rtx x, regset nonequal)
228 {
229 subrtx_iterator::array_type array;
230 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
231 {
232 const_rtx x = *iter;
233 if (REG_P (x))
234 {
235 unsigned int end_regno = END_REGNO (x);
236 for (unsigned int regno = REGNO (x); regno < end_regno; ++regno)
237 if (REGNO_REG_SET_P (nonequal, regno))
238 return true;
239 }
240 }
241 return false;
242 }
243
244 /* Attempt to prove that the basic block B will have no side effects and
245 always continues in the same edge if reached via E. Return the edge
246 if exist, NULL otherwise. */
247
248 static edge
thread_jump(edge e,basic_block b)249 thread_jump (edge e, basic_block b)
250 {
251 rtx set1, set2, cond1, cond2;
252 rtx_insn *insn;
253 enum rtx_code code1, code2, reversed_code2;
254 bool reverse1 = false;
255 unsigned i;
256 regset nonequal;
257 bool failed = false;
258 reg_set_iterator rsi;
259
260 if (b->flags & BB_NONTHREADABLE_BLOCK)
261 return NULL;
262
263 /* At the moment, we do handle only conditional jumps, but later we may
264 want to extend this code to tablejumps and others. */
265 if (EDGE_COUNT (e->src->succs) != 2)
266 return NULL;
267 if (EDGE_COUNT (b->succs) != 2)
268 {
269 b->flags |= BB_NONTHREADABLE_BLOCK;
270 return NULL;
271 }
272
273 /* Second branch must end with onlyjump, as we will eliminate the jump. */
274 if (!any_condjump_p (BB_END (e->src)))
275 return NULL;
276
277 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
278 {
279 b->flags |= BB_NONTHREADABLE_BLOCK;
280 return NULL;
281 }
282
283 set1 = pc_set (BB_END (e->src));
284 set2 = pc_set (BB_END (b));
285 if (((e->flags & EDGE_FALLTHRU) != 0)
286 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
287 reverse1 = true;
288
289 cond1 = XEXP (SET_SRC (set1), 0);
290 cond2 = XEXP (SET_SRC (set2), 0);
291 if (reverse1)
292 code1 = reversed_comparison_code (cond1, BB_END (e->src));
293 else
294 code1 = GET_CODE (cond1);
295
296 code2 = GET_CODE (cond2);
297 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
298
299 if (!comparison_dominates_p (code1, code2)
300 && !comparison_dominates_p (code1, reversed_code2))
301 return NULL;
302
303 /* Ensure that the comparison operators are equivalent.
304 ??? This is far too pessimistic. We should allow swapped operands,
305 different CCmodes, or for example comparisons for interval, that
306 dominate even when operands are not equivalent. */
307 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
308 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
309 return NULL;
310
311 /* Short circuit cases where block B contains some side effects, as we can't
312 safely bypass it. */
313 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
314 insn = NEXT_INSN (insn))
315 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
316 {
317 b->flags |= BB_NONTHREADABLE_BLOCK;
318 return NULL;
319 }
320
321 cselib_init (0);
322
323 /* First process all values computed in the source basic block. */
324 for (insn = NEXT_INSN (BB_HEAD (e->src));
325 insn != NEXT_INSN (BB_END (e->src));
326 insn = NEXT_INSN (insn))
327 if (INSN_P (insn))
328 cselib_process_insn (insn);
329
330 nonequal = BITMAP_ALLOC (NULL);
331 CLEAR_REG_SET (nonequal);
332
333 /* Now assume that we've continued by the edge E to B and continue
334 processing as if it were same basic block.
335 Our goal is to prove that whole block is an NOOP. */
336
337 for (insn = NEXT_INSN (BB_HEAD (b));
338 insn != NEXT_INSN (BB_END (b)) && !failed;
339 insn = NEXT_INSN (insn))
340 {
341 if (INSN_P (insn))
342 {
343 rtx pat = PATTERN (insn);
344
345 if (GET_CODE (pat) == PARALLEL)
346 {
347 for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
348 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
349 }
350 else
351 failed |= mark_effect (pat, nonequal);
352 }
353
354 cselib_process_insn (insn);
355 }
356
357 /* Later we should clear nonequal of dead registers. So far we don't
358 have life information in cfg_cleanup. */
359 if (failed)
360 {
361 b->flags |= BB_NONTHREADABLE_BLOCK;
362 goto failed_exit;
363 }
364
365 /* cond2 must not mention any register that is not equal to the
366 former block. */
367 if (mentions_nonequal_regs (cond2, nonequal))
368 goto failed_exit;
369
370 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, rsi)
371 goto failed_exit;
372
373 BITMAP_FREE (nonequal);
374 cselib_finish ();
375 if ((comparison_dominates_p (code1, code2) != 0)
376 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
377 return BRANCH_EDGE (b);
378 else
379 return FALLTHRU_EDGE (b);
380
381 failed_exit:
382 BITMAP_FREE (nonequal);
383 cselib_finish ();
384 return NULL;
385 }
386
387 /* Attempt to forward edges leaving basic block B.
388 Return true if successful. */
389
390 static bool
try_forward_edges(int mode,basic_block b)391 try_forward_edges (int mode, basic_block b)
392 {
393 bool changed = false;
394 edge_iterator ei;
395 edge e, *threaded_edges = NULL;
396
397 for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
398 {
399 basic_block target, first;
400 location_t goto_locus;
401 int counter;
402 bool threaded = false;
403 int nthreaded_edges = 0;
404 bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0;
405 bool new_target_threaded = false;
406
407 /* Skip complex edges because we don't know how to update them.
408
409 Still handle fallthru edges, as we can succeed to forward fallthru
410 edge to the same place as the branch edge of conditional branch
411 and turn conditional branch to an unconditional branch. */
412 if (e->flags & EDGE_COMPLEX)
413 {
414 ei_next (&ei);
415 continue;
416 }
417
418 target = first = e->dest;
419 counter = NUM_FIXED_BLOCKS;
420 goto_locus = e->goto_locus;
421
422 while (counter < n_basic_blocks_for_fn (cfun))
423 {
424 basic_block new_target = NULL;
425 may_thread |= (target->flags & BB_MODIFIED) != 0;
426
427 if (FORWARDER_BLOCK_P (target)
428 && single_succ (target) != EXIT_BLOCK_PTR_FOR_FN (cfun))
429 {
430 /* Bypass trivial infinite loops. */
431 new_target = single_succ (target);
432 if (target == new_target)
433 counter = n_basic_blocks_for_fn (cfun);
434 else if (!optimize)
435 {
436 /* When not optimizing, ensure that edges or forwarder
437 blocks with different locus are not optimized out. */
438 location_t new_locus = single_succ_edge (target)->goto_locus;
439 location_t locus = goto_locus;
440
441 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION
442 && LOCATION_LOCUS (locus) != UNKNOWN_LOCATION
443 && new_locus != locus)
444 new_target = NULL;
445 else
446 {
447 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION)
448 locus = new_locus;
449
450 rtx_insn *last = BB_END (target);
451 if (DEBUG_INSN_P (last))
452 last = prev_nondebug_insn (last);
453 if (last && INSN_P (last))
454 new_locus = INSN_LOCATION (last);
455 else
456 new_locus = UNKNOWN_LOCATION;
457
458 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION
459 && LOCATION_LOCUS (locus) != UNKNOWN_LOCATION
460 && new_locus != locus)
461 new_target = NULL;
462 else
463 {
464 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION)
465 locus = new_locus;
466
467 goto_locus = locus;
468 }
469 }
470 }
471 }
472
473 /* Allow to thread only over one edge at time to simplify updating
474 of probabilities. */
475 else if ((mode & CLEANUP_THREADING) && may_thread)
476 {
477 edge t = thread_jump (e, target);
478 if (t)
479 {
480 if (!threaded_edges)
481 threaded_edges = XNEWVEC (edge,
482 n_basic_blocks_for_fn (cfun));
483 else
484 {
485 int i;
486
487 /* Detect an infinite loop across blocks not
488 including the start block. */
489 for (i = 0; i < nthreaded_edges; ++i)
490 if (threaded_edges[i] == t)
491 break;
492 if (i < nthreaded_edges)
493 {
494 counter = n_basic_blocks_for_fn (cfun);
495 break;
496 }
497 }
498
499 /* Detect an infinite loop across the start block. */
500 if (t->dest == b)
501 break;
502
503 gcc_assert (nthreaded_edges
504 < (n_basic_blocks_for_fn (cfun)
505 - NUM_FIXED_BLOCKS));
506 threaded_edges[nthreaded_edges++] = t;
507
508 new_target = t->dest;
509 new_target_threaded = true;
510 }
511 }
512
513 if (!new_target)
514 break;
515
516 counter++;
517 /* Do not turn non-crossing jump to crossing. Depending on target
518 it may require different instruction pattern. */
519 if ((e->flags & EDGE_CROSSING)
520 || BB_PARTITION (first) == BB_PARTITION (new_target))
521 {
522 target = new_target;
523 threaded |= new_target_threaded;
524 }
525 }
526
527 if (counter >= n_basic_blocks_for_fn (cfun))
528 {
529 if (dump_file)
530 fprintf (dump_file, "Infinite loop in BB %i.\n",
531 target->index);
532 }
533 else if (target == first)
534 ; /* We didn't do anything. */
535 else
536 {
537 /* Save the values now, as the edge may get removed. */
538 profile_count edge_count = e->count ();
539 int n = 0;
540
541 e->goto_locus = goto_locus;
542
543 /* Don't force if target is exit block. */
544 if (threaded && target != EXIT_BLOCK_PTR_FOR_FN (cfun))
545 {
546 notice_new_block (redirect_edge_and_branch_force (e, target));
547 if (dump_file)
548 fprintf (dump_file, "Conditionals threaded.\n");
549 }
550 else if (!redirect_edge_and_branch (e, target))
551 {
552 if (dump_file)
553 fprintf (dump_file,
554 "Forwarding edge %i->%i to %i failed.\n",
555 b->index, e->dest->index, target->index);
556 ei_next (&ei);
557 continue;
558 }
559
560 /* We successfully forwarded the edge. Now update profile
561 data: for each edge we traversed in the chain, remove
562 the original edge's execution count. */
563 do
564 {
565 edge t;
566
567 if (!single_succ_p (first))
568 {
569 gcc_assert (n < nthreaded_edges);
570 t = threaded_edges [n++];
571 gcc_assert (t->src == first);
572 update_bb_profile_for_threading (first, edge_count, t);
573 update_br_prob_note (first);
574 }
575 else
576 {
577 first->count -= edge_count;
578 /* It is possible that as the result of
579 threading we've removed edge as it is
580 threaded to the fallthru edge. Avoid
581 getting out of sync. */
582 if (n < nthreaded_edges
583 && first == threaded_edges [n]->src)
584 n++;
585 t = single_succ_edge (first);
586 }
587
588 first = t->dest;
589 }
590 while (first != target);
591
592 changed = true;
593 continue;
594 }
595 ei_next (&ei);
596 }
597
598 free (threaded_edges);
599 return changed;
600 }
601
602
603 /* Blocks A and B are to be merged into a single block. A has no incoming
604 fallthru edge, so it can be moved before B without adding or modifying
605 any jumps (aside from the jump from A to B). */
606
607 static void
merge_blocks_move_predecessor_nojumps(basic_block a,basic_block b)608 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
609 {
610 rtx_insn *barrier;
611
612 /* If we are partitioning hot/cold basic blocks, we don't want to
613 mess up unconditional or indirect jumps that cross between hot
614 and cold sections.
615
616 Basic block partitioning may result in some jumps that appear to
617 be optimizable (or blocks that appear to be mergeable), but which really
618 must be left untouched (they are required to make it safely across
619 partition boundaries). See the comments at the top of
620 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
621
622 if (BB_PARTITION (a) != BB_PARTITION (b))
623 return;
624
625 barrier = next_nonnote_insn (BB_END (a));
626 gcc_assert (BARRIER_P (barrier));
627 delete_insn (barrier);
628
629 /* Scramble the insn chain. */
630 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
631 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
632 df_set_bb_dirty (a);
633
634 if (dump_file)
635 fprintf (dump_file, "Moved block %d before %d and merged.\n",
636 a->index, b->index);
637
638 /* Swap the records for the two blocks around. */
639
640 unlink_block (a);
641 link_block (a, b->prev_bb);
642
643 /* Now blocks A and B are contiguous. Merge them. */
644 merge_blocks (a, b);
645 }
646
647 /* Blocks A and B are to be merged into a single block. B has no outgoing
648 fallthru edge, so it can be moved after A without adding or modifying
649 any jumps (aside from the jump from A to B). */
650
651 static void
merge_blocks_move_successor_nojumps(basic_block a,basic_block b)652 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
653 {
654 rtx_insn *barrier, *real_b_end;
655 rtx_insn *label;
656 rtx_jump_table_data *table;
657
658 /* If we are partitioning hot/cold basic blocks, we don't want to
659 mess up unconditional or indirect jumps that cross between hot
660 and cold sections.
661
662 Basic block partitioning may result in some jumps that appear to
663 be optimizable (or blocks that appear to be mergeable), but which really
664 must be left untouched (they are required to make it safely across
665 partition boundaries). See the comments at the top of
666 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
667
668 if (BB_PARTITION (a) != BB_PARTITION (b))
669 return;
670
671 real_b_end = BB_END (b);
672
673 /* If there is a jump table following block B temporarily add the jump table
674 to block B so that it will also be moved to the correct location. */
675 if (tablejump_p (BB_END (b), &label, &table)
676 && prev_active_insn (label) == BB_END (b))
677 {
678 BB_END (b) = table;
679 }
680
681 /* There had better have been a barrier there. Delete it. */
682 barrier = NEXT_INSN (BB_END (b));
683 if (barrier && BARRIER_P (barrier))
684 delete_insn (barrier);
685
686
687 /* Scramble the insn chain. */
688 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
689
690 /* Restore the real end of b. */
691 BB_END (b) = real_b_end;
692
693 if (dump_file)
694 fprintf (dump_file, "Moved block %d after %d and merged.\n",
695 b->index, a->index);
696
697 /* Now blocks A and B are contiguous. Merge them. */
698 merge_blocks (a, b);
699 }
700
701 /* Attempt to merge basic blocks that are potentially non-adjacent.
702 Return NULL iff the attempt failed, otherwise return basic block
703 where cleanup_cfg should continue. Because the merging commonly
704 moves basic block away or introduces another optimization
705 possibility, return basic block just before B so cleanup_cfg don't
706 need to iterate.
707
708 It may be good idea to return basic block before C in the case
709 C has been moved after B and originally appeared earlier in the
710 insn sequence, but we have no information available about the
711 relative ordering of these two. Hopefully it is not too common. */
712
713 static basic_block
merge_blocks_move(edge e,basic_block b,basic_block c,int mode)714 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
715 {
716 basic_block next;
717
718 /* If we are partitioning hot/cold basic blocks, we don't want to
719 mess up unconditional or indirect jumps that cross between hot
720 and cold sections.
721
722 Basic block partitioning may result in some jumps that appear to
723 be optimizable (or blocks that appear to be mergeable), but which really
724 must be left untouched (they are required to make it safely across
725 partition boundaries). See the comments at the top of
726 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
727
728 if (BB_PARTITION (b) != BB_PARTITION (c))
729 return NULL;
730
731 /* If B has a fallthru edge to C, no need to move anything. */
732 if (e->flags & EDGE_FALLTHRU)
733 {
734 int b_index = b->index, c_index = c->index;
735
736 /* Protect the loop latches. */
737 if (current_loops && c->loop_father->latch == c)
738 return NULL;
739
740 merge_blocks (b, c);
741 update_forwarder_flag (b);
742
743 if (dump_file)
744 fprintf (dump_file, "Merged %d and %d without moving.\n",
745 b_index, c_index);
746
747 return b->prev_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? b : b->prev_bb;
748 }
749
750 /* Otherwise we will need to move code around. Do that only if expensive
751 transformations are allowed. */
752 else if (mode & CLEANUP_EXPENSIVE)
753 {
754 edge tmp_edge, b_fallthru_edge;
755 bool c_has_outgoing_fallthru;
756 bool b_has_incoming_fallthru;
757
758 /* Avoid overactive code motion, as the forwarder blocks should be
759 eliminated by edge redirection instead. One exception might have
760 been if B is a forwarder block and C has no fallthru edge, but
761 that should be cleaned up by bb-reorder instead. */
762 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
763 return NULL;
764
765 /* We must make sure to not munge nesting of lexical blocks,
766 and loop notes. This is done by squeezing out all the notes
767 and leaving them there to lie. Not ideal, but functional. */
768
769 tmp_edge = find_fallthru_edge (c->succs);
770 c_has_outgoing_fallthru = (tmp_edge != NULL);
771
772 tmp_edge = find_fallthru_edge (b->preds);
773 b_has_incoming_fallthru = (tmp_edge != NULL);
774 b_fallthru_edge = tmp_edge;
775 next = b->prev_bb;
776 if (next == c)
777 next = next->prev_bb;
778
779 /* Otherwise, we're going to try to move C after B. If C does
780 not have an outgoing fallthru, then it can be moved
781 immediately after B without introducing or modifying jumps. */
782 if (! c_has_outgoing_fallthru)
783 {
784 merge_blocks_move_successor_nojumps (b, c);
785 return next == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? next->next_bb : next;
786 }
787
788 /* If B does not have an incoming fallthru, then it can be moved
789 immediately before C without introducing or modifying jumps.
790 C cannot be the first block, so we do not have to worry about
791 accessing a non-existent block. */
792
793 if (b_has_incoming_fallthru)
794 {
795 basic_block bb;
796
797 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
798 return NULL;
799 bb = force_nonfallthru (b_fallthru_edge);
800 if (bb)
801 notice_new_block (bb);
802 }
803
804 merge_blocks_move_predecessor_nojumps (b, c);
805 return next == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? next->next_bb : next;
806 }
807
808 return NULL;
809 }
810
811
812 /* Removes the memory attributes of MEM expression
813 if they are not equal. */
814
815 static void
merge_memattrs(rtx x,rtx y)816 merge_memattrs (rtx x, rtx y)
817 {
818 int i;
819 int j;
820 enum rtx_code code;
821 const char *fmt;
822
823 if (x == y)
824 return;
825 if (x == 0 || y == 0)
826 return;
827
828 code = GET_CODE (x);
829
830 if (code != GET_CODE (y))
831 return;
832
833 if (GET_MODE (x) != GET_MODE (y))
834 return;
835
836 if (code == MEM && !mem_attrs_eq_p (MEM_ATTRS (x), MEM_ATTRS (y)))
837 {
838 if (! MEM_ATTRS (x))
839 MEM_ATTRS (y) = 0;
840 else if (! MEM_ATTRS (y))
841 MEM_ATTRS (x) = 0;
842 else
843 {
844 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
845 {
846 set_mem_alias_set (x, 0);
847 set_mem_alias_set (y, 0);
848 }
849
850 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
851 {
852 set_mem_expr (x, 0);
853 set_mem_expr (y, 0);
854 clear_mem_offset (x);
855 clear_mem_offset (y);
856 }
857 else if (MEM_OFFSET_KNOWN_P (x) != MEM_OFFSET_KNOWN_P (y)
858 || (MEM_OFFSET_KNOWN_P (x)
859 && maybe_ne (MEM_OFFSET (x), MEM_OFFSET (y))))
860 {
861 clear_mem_offset (x);
862 clear_mem_offset (y);
863 }
864
865 if (!MEM_SIZE_KNOWN_P (x))
866 clear_mem_size (y);
867 else if (!MEM_SIZE_KNOWN_P (y))
868 clear_mem_size (x);
869 else if (known_le (MEM_SIZE (x), MEM_SIZE (y)))
870 set_mem_size (x, MEM_SIZE (y));
871 else if (known_le (MEM_SIZE (y), MEM_SIZE (x)))
872 set_mem_size (y, MEM_SIZE (x));
873 else
874 {
875 /* The sizes aren't ordered, so we can't merge them. */
876 clear_mem_size (x);
877 clear_mem_size (y);
878 }
879
880 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
881 set_mem_align (y, MEM_ALIGN (x));
882 }
883 }
884 if (code == MEM)
885 {
886 if (MEM_READONLY_P (x) != MEM_READONLY_P (y))
887 {
888 MEM_READONLY_P (x) = 0;
889 MEM_READONLY_P (y) = 0;
890 }
891 if (MEM_NOTRAP_P (x) != MEM_NOTRAP_P (y))
892 {
893 MEM_NOTRAP_P (x) = 0;
894 MEM_NOTRAP_P (y) = 0;
895 }
896 if (MEM_VOLATILE_P (x) != MEM_VOLATILE_P (y))
897 {
898 MEM_VOLATILE_P (x) = 1;
899 MEM_VOLATILE_P (y) = 1;
900 }
901 }
902
903 fmt = GET_RTX_FORMAT (code);
904 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
905 {
906 switch (fmt[i])
907 {
908 case 'E':
909 /* Two vectors must have the same length. */
910 if (XVECLEN (x, i) != XVECLEN (y, i))
911 return;
912
913 for (j = 0; j < XVECLEN (x, i); j++)
914 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
915
916 break;
917
918 case 'e':
919 merge_memattrs (XEXP (x, i), XEXP (y, i));
920 }
921 }
922 return;
923 }
924
925
926 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
927 different single sets S1 and S2. */
928
929 static bool
equal_different_set_p(rtx p1,rtx s1,rtx p2,rtx s2)930 equal_different_set_p (rtx p1, rtx s1, rtx p2, rtx s2)
931 {
932 int i;
933 rtx e1, e2;
934
935 if (p1 == s1 && p2 == s2)
936 return true;
937
938 if (GET_CODE (p1) != PARALLEL || GET_CODE (p2) != PARALLEL)
939 return false;
940
941 if (XVECLEN (p1, 0) != XVECLEN (p2, 0))
942 return false;
943
944 for (i = 0; i < XVECLEN (p1, 0); i++)
945 {
946 e1 = XVECEXP (p1, 0, i);
947 e2 = XVECEXP (p2, 0, i);
948 if (e1 == s1 && e2 == s2)
949 continue;
950 if (reload_completed
951 ? rtx_renumbered_equal_p (e1, e2) : rtx_equal_p (e1, e2))
952 continue;
953
954 return false;
955 }
956
957 return true;
958 }
959
960
961 /* NOTE1 is the REG_EQUAL note, if any, attached to an insn
962 that is a single_set with a SET_SRC of SRC1. Similarly
963 for NOTE2/SRC2.
964
965 So effectively NOTE1/NOTE2 are an alternate form of
966 SRC1/SRC2 respectively.
967
968 Return nonzero if SRC1 or NOTE1 has the same constant
969 integer value as SRC2 or NOTE2. Else return zero. */
970 static int
values_equal_p(rtx note1,rtx note2,rtx src1,rtx src2)971 values_equal_p (rtx note1, rtx note2, rtx src1, rtx src2)
972 {
973 if (note1
974 && note2
975 && CONST_INT_P (XEXP (note1, 0))
976 && rtx_equal_p (XEXP (note1, 0), XEXP (note2, 0)))
977 return 1;
978
979 if (!note1
980 && !note2
981 && CONST_INT_P (src1)
982 && CONST_INT_P (src2)
983 && rtx_equal_p (src1, src2))
984 return 1;
985
986 if (note1
987 && CONST_INT_P (src2)
988 && rtx_equal_p (XEXP (note1, 0), src2))
989 return 1;
990
991 if (note2
992 && CONST_INT_P (src1)
993 && rtx_equal_p (XEXP (note2, 0), src1))
994 return 1;
995
996 return 0;
997 }
998
999 /* Examine register notes on I1 and I2 and return:
1000 - dir_forward if I1 can be replaced by I2, or
1001 - dir_backward if I2 can be replaced by I1, or
1002 - dir_both if both are the case. */
1003
1004 static enum replace_direction
can_replace_by(rtx_insn * i1,rtx_insn * i2)1005 can_replace_by (rtx_insn *i1, rtx_insn *i2)
1006 {
1007 rtx s1, s2, d1, d2, src1, src2, note1, note2;
1008 bool c1, c2;
1009
1010 /* Check for 2 sets. */
1011 s1 = single_set (i1);
1012 s2 = single_set (i2);
1013 if (s1 == NULL_RTX || s2 == NULL_RTX)
1014 return dir_none;
1015
1016 /* Check that the 2 sets set the same dest. */
1017 d1 = SET_DEST (s1);
1018 d2 = SET_DEST (s2);
1019 if (!(reload_completed
1020 ? rtx_renumbered_equal_p (d1, d2) : rtx_equal_p (d1, d2)))
1021 return dir_none;
1022
1023 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1024 set dest to the same value. */
1025 note1 = find_reg_equal_equiv_note (i1);
1026 note2 = find_reg_equal_equiv_note (i2);
1027
1028 src1 = SET_SRC (s1);
1029 src2 = SET_SRC (s2);
1030
1031 if (!values_equal_p (note1, note2, src1, src2))
1032 return dir_none;
1033
1034 if (!equal_different_set_p (PATTERN (i1), s1, PATTERN (i2), s2))
1035 return dir_none;
1036
1037 /* Although the 2 sets set dest to the same value, we cannot replace
1038 (set (dest) (const_int))
1039 by
1040 (set (dest) (reg))
1041 because we don't know if the reg is live and has the same value at the
1042 location of replacement. */
1043 c1 = CONST_INT_P (src1);
1044 c2 = CONST_INT_P (src2);
1045 if (c1 && c2)
1046 return dir_both;
1047 else if (c2)
1048 return dir_forward;
1049 else if (c1)
1050 return dir_backward;
1051
1052 return dir_none;
1053 }
1054
1055 /* Merges directions A and B. */
1056
1057 static enum replace_direction
merge_dir(enum replace_direction a,enum replace_direction b)1058 merge_dir (enum replace_direction a, enum replace_direction b)
1059 {
1060 /* Implements the following table:
1061 |bo fw bw no
1062 ---+-----------
1063 bo |bo fw bw no
1064 fw |-- fw no no
1065 bw |-- -- bw no
1066 no |-- -- -- no. */
1067
1068 if (a == b)
1069 return a;
1070
1071 if (a == dir_both)
1072 return b;
1073 if (b == dir_both)
1074 return a;
1075
1076 return dir_none;
1077 }
1078
1079 /* Array of flags indexed by reg note kind, true if the given
1080 reg note is CFA related. */
1081 static const bool reg_note_cfa_p[] = {
1082 #undef REG_CFA_NOTE
1083 #define DEF_REG_NOTE(NAME) false,
1084 #define REG_CFA_NOTE(NAME) true,
1085 #include "reg-notes.def"
1086 #undef REG_CFA_NOTE
1087 #undef DEF_REG_NOTE
1088 false
1089 };
1090
1091 /* Return true if I1 and I2 have identical CFA notes (the same order
1092 and equivalent content). */
1093
1094 static bool
insns_have_identical_cfa_notes(rtx_insn * i1,rtx_insn * i2)1095 insns_have_identical_cfa_notes (rtx_insn *i1, rtx_insn *i2)
1096 {
1097 rtx n1, n2;
1098 for (n1 = REG_NOTES (i1), n2 = REG_NOTES (i2); ;
1099 n1 = XEXP (n1, 1), n2 = XEXP (n2, 1))
1100 {
1101 /* Skip over reg notes not related to CFI information. */
1102 while (n1 && !reg_note_cfa_p[REG_NOTE_KIND (n1)])
1103 n1 = XEXP (n1, 1);
1104 while (n2 && !reg_note_cfa_p[REG_NOTE_KIND (n2)])
1105 n2 = XEXP (n2, 1);
1106 if (n1 == NULL_RTX && n2 == NULL_RTX)
1107 return true;
1108 if (n1 == NULL_RTX || n2 == NULL_RTX)
1109 return false;
1110 if (XEXP (n1, 0) == XEXP (n2, 0))
1111 ;
1112 else if (XEXP (n1, 0) == NULL_RTX || XEXP (n2, 0) == NULL_RTX)
1113 return false;
1114 else if (!(reload_completed
1115 ? rtx_renumbered_equal_p (XEXP (n1, 0), XEXP (n2, 0))
1116 : rtx_equal_p (XEXP (n1, 0), XEXP (n2, 0))))
1117 return false;
1118 }
1119 }
1120
1121 /* Examine I1 and I2 and return:
1122 - dir_forward if I1 can be replaced by I2, or
1123 - dir_backward if I2 can be replaced by I1, or
1124 - dir_both if both are the case. */
1125
1126 static enum replace_direction
old_insns_match_p(int mode ATTRIBUTE_UNUSED,rtx_insn * i1,rtx_insn * i2)1127 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx_insn *i1, rtx_insn *i2)
1128 {
1129 rtx p1, p2;
1130
1131 /* Verify that I1 and I2 are equivalent. */
1132 if (GET_CODE (i1) != GET_CODE (i2))
1133 return dir_none;
1134
1135 /* __builtin_unreachable() may lead to empty blocks (ending with
1136 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1137 if (NOTE_INSN_BASIC_BLOCK_P (i1) && NOTE_INSN_BASIC_BLOCK_P (i2))
1138 return dir_both;
1139
1140 /* ??? Do not allow cross-jumping between different stack levels. */
1141 p1 = find_reg_note (i1, REG_ARGS_SIZE, NULL);
1142 p2 = find_reg_note (i2, REG_ARGS_SIZE, NULL);
1143 if (p1 && p2)
1144 {
1145 p1 = XEXP (p1, 0);
1146 p2 = XEXP (p2, 0);
1147 if (!rtx_equal_p (p1, p2))
1148 return dir_none;
1149
1150 /* ??? Worse, this adjustment had better be constant lest we
1151 have differing incoming stack levels. */
1152 if (!frame_pointer_needed
1153 && known_eq (find_args_size_adjust (i1), HOST_WIDE_INT_MIN))
1154 return dir_none;
1155 }
1156 else if (p1 || p2)
1157 return dir_none;
1158
1159 /* Do not allow cross-jumping between frame related insns and other
1160 insns. */
1161 if (RTX_FRAME_RELATED_P (i1) != RTX_FRAME_RELATED_P (i2))
1162 return dir_none;
1163
1164 p1 = PATTERN (i1);
1165 p2 = PATTERN (i2);
1166
1167 if (GET_CODE (p1) != GET_CODE (p2))
1168 return dir_none;
1169
1170 /* If this is a CALL_INSN, compare register usage information.
1171 If we don't check this on stack register machines, the two
1172 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1173 numbers of stack registers in the same basic block.
1174 If we don't check this on machines with delay slots, a delay slot may
1175 be filled that clobbers a parameter expected by the subroutine.
1176
1177 ??? We take the simple route for now and assume that if they're
1178 equal, they were constructed identically.
1179
1180 Also check for identical exception regions. */
1181
1182 if (CALL_P (i1))
1183 {
1184 /* Ensure the same EH region. */
1185 rtx n1 = find_reg_note (i1, REG_EH_REGION, 0);
1186 rtx n2 = find_reg_note (i2, REG_EH_REGION, 0);
1187
1188 if (!n1 && n2)
1189 return dir_none;
1190
1191 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1192 return dir_none;
1193
1194 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
1195 CALL_INSN_FUNCTION_USAGE (i2))
1196 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2))
1197 return dir_none;
1198
1199 /* For address sanitizer, never crossjump __asan_report_* builtins,
1200 otherwise errors might be reported on incorrect lines. */
1201 if (flag_sanitize & SANITIZE_ADDRESS)
1202 {
1203 rtx call = get_call_rtx_from (i1);
1204 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
1205 {
1206 rtx symbol = XEXP (XEXP (call, 0), 0);
1207 if (SYMBOL_REF_DECL (symbol)
1208 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
1209 {
1210 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
1211 == BUILT_IN_NORMAL)
1212 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
1213 >= BUILT_IN_ASAN_REPORT_LOAD1
1214 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
1215 <= BUILT_IN_ASAN_STOREN)
1216 return dir_none;
1217 }
1218 }
1219 }
1220 }
1221
1222 /* If both i1 and i2 are frame related, verify all the CFA notes
1223 in the same order and with the same content. */
1224 if (RTX_FRAME_RELATED_P (i1) && !insns_have_identical_cfa_notes (i1, i2))
1225 return dir_none;
1226
1227 #ifdef STACK_REGS
1228 /* If cross_jump_death_matters is not 0, the insn's mode
1229 indicates whether or not the insn contains any stack-like
1230 regs. */
1231
1232 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
1233 {
1234 /* If register stack conversion has already been done, then
1235 death notes must also be compared before it is certain that
1236 the two instruction streams match. */
1237
1238 rtx note;
1239 HARD_REG_SET i1_regset, i2_regset;
1240
1241 CLEAR_HARD_REG_SET (i1_regset);
1242 CLEAR_HARD_REG_SET (i2_regset);
1243
1244 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
1245 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1246 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
1247
1248 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1249 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1250 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1251
1252 if (!hard_reg_set_equal_p (i1_regset, i2_regset))
1253 return dir_none;
1254 }
1255 #endif
1256
1257 if (reload_completed
1258 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1259 return dir_both;
1260
1261 return can_replace_by (i1, i2);
1262 }
1263
1264 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1265 flow_find_head_matching_sequence, ensure the notes match. */
1266
1267 static void
merge_notes(rtx_insn * i1,rtx_insn * i2)1268 merge_notes (rtx_insn *i1, rtx_insn *i2)
1269 {
1270 /* If the merged insns have different REG_EQUAL notes, then
1271 remove them. */
1272 rtx equiv1 = find_reg_equal_equiv_note (i1);
1273 rtx equiv2 = find_reg_equal_equiv_note (i2);
1274
1275 if (equiv1 && !equiv2)
1276 remove_note (i1, equiv1);
1277 else if (!equiv1 && equiv2)
1278 remove_note (i2, equiv2);
1279 else if (equiv1 && equiv2
1280 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1281 {
1282 remove_note (i1, equiv1);
1283 remove_note (i2, equiv2);
1284 }
1285 }
1286
1287 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1288 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1289 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1290 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1291 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1292
1293 static void
walk_to_nondebug_insn(rtx_insn ** i1,basic_block * bb1,bool follow_fallthru,bool * did_fallthru)1294 walk_to_nondebug_insn (rtx_insn **i1, basic_block *bb1, bool follow_fallthru,
1295 bool *did_fallthru)
1296 {
1297 edge fallthru;
1298
1299 *did_fallthru = false;
1300
1301 /* Ignore notes. */
1302 while (!NONDEBUG_INSN_P (*i1))
1303 {
1304 if (*i1 != BB_HEAD (*bb1))
1305 {
1306 *i1 = PREV_INSN (*i1);
1307 continue;
1308 }
1309
1310 if (!follow_fallthru)
1311 return;
1312
1313 fallthru = find_fallthru_edge ((*bb1)->preds);
1314 if (!fallthru || fallthru->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1315 || !single_succ_p (fallthru->src))
1316 return;
1317
1318 *bb1 = fallthru->src;
1319 *i1 = BB_END (*bb1);
1320 *did_fallthru = true;
1321 }
1322 }
1323
1324 /* Look through the insns at the end of BB1 and BB2 and find the longest
1325 sequence that are either equivalent, or allow forward or backward
1326 replacement. Store the first insns for that sequence in *F1 and *F2 and
1327 return the sequence length.
1328
1329 DIR_P indicates the allowed replacement direction on function entry, and
1330 the actual replacement direction on function exit. If NULL, only equivalent
1331 sequences are allowed.
1332
1333 To simplify callers of this function, if the blocks match exactly,
1334 store the head of the blocks in *F1 and *F2. */
1335
1336 int
flow_find_cross_jump(basic_block bb1,basic_block bb2,rtx_insn ** f1,rtx_insn ** f2,enum replace_direction * dir_p)1337 flow_find_cross_jump (basic_block bb1, basic_block bb2, rtx_insn **f1,
1338 rtx_insn **f2, enum replace_direction *dir_p)
1339 {
1340 rtx_insn *i1, *i2, *last1, *last2, *afterlast1, *afterlast2;
1341 int ninsns = 0;
1342 enum replace_direction dir, last_dir, afterlast_dir;
1343 bool follow_fallthru, did_fallthru;
1344
1345 if (dir_p)
1346 dir = *dir_p;
1347 else
1348 dir = dir_both;
1349 afterlast_dir = dir;
1350 last_dir = afterlast_dir;
1351
1352 /* Skip simple jumps at the end of the blocks. Complex jumps still
1353 need to be compared for equivalence, which we'll do below. */
1354
1355 i1 = BB_END (bb1);
1356 last1 = afterlast1 = last2 = afterlast2 = NULL;
1357 if (onlyjump_p (i1)
1358 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1359 {
1360 last1 = i1;
1361 i1 = PREV_INSN (i1);
1362 }
1363
1364 i2 = BB_END (bb2);
1365 if (onlyjump_p (i2)
1366 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1367 {
1368 last2 = i2;
1369 /* Count everything except for unconditional jump as insn.
1370 Don't count any jumps if dir_p is NULL. */
1371 if (!simplejump_p (i2) && !returnjump_p (i2) && last1 && dir_p)
1372 ninsns++;
1373 i2 = PREV_INSN (i2);
1374 }
1375
1376 while (true)
1377 {
1378 /* In the following example, we can replace all jumps to C by jumps to A.
1379
1380 This removes 4 duplicate insns.
1381 [bb A] insn1 [bb C] insn1
1382 insn2 insn2
1383 [bb B] insn3 insn3
1384 insn4 insn4
1385 jump_insn jump_insn
1386
1387 We could also replace all jumps to A by jumps to C, but that leaves B
1388 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1389 step, all jumps to B would be replaced with jumps to the middle of C,
1390 achieving the same result with more effort.
1391 So we allow only the first possibility, which means that we don't allow
1392 fallthru in the block that's being replaced. */
1393
1394 follow_fallthru = dir_p && dir != dir_forward;
1395 walk_to_nondebug_insn (&i1, &bb1, follow_fallthru, &did_fallthru);
1396 if (did_fallthru)
1397 dir = dir_backward;
1398
1399 follow_fallthru = dir_p && dir != dir_backward;
1400 walk_to_nondebug_insn (&i2, &bb2, follow_fallthru, &did_fallthru);
1401 if (did_fallthru)
1402 dir = dir_forward;
1403
1404 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1405 break;
1406
1407 /* Do not turn corssing edge to non-crossing or vice versa after
1408 reload. */
1409 if (BB_PARTITION (BLOCK_FOR_INSN (i1))
1410 != BB_PARTITION (BLOCK_FOR_INSN (i2))
1411 && reload_completed)
1412 break;
1413
1414 dir = merge_dir (dir, old_insns_match_p (0, i1, i2));
1415 if (dir == dir_none || (!dir_p && dir != dir_both))
1416 break;
1417
1418 merge_memattrs (i1, i2);
1419
1420 /* Don't begin a cross-jump with a NOTE insn. */
1421 if (INSN_P (i1))
1422 {
1423 merge_notes (i1, i2);
1424
1425 afterlast1 = last1, afterlast2 = last2;
1426 last1 = i1, last2 = i2;
1427 afterlast_dir = last_dir;
1428 last_dir = dir;
1429 if (active_insn_p (i1))
1430 ninsns++;
1431 }
1432
1433 i1 = PREV_INSN (i1);
1434 i2 = PREV_INSN (i2);
1435 }
1436
1437 /* Don't allow the insn after a compare to be shared by
1438 cross-jumping unless the compare is also shared. */
1439 if (HAVE_cc0 && ninsns && reg_mentioned_p (cc0_rtx, last1)
1440 && ! sets_cc0_p (last1))
1441 last1 = afterlast1, last2 = afterlast2, last_dir = afterlast_dir, ninsns--;
1442
1443 /* Include preceding notes and labels in the cross-jump. One,
1444 this may bring us to the head of the blocks as requested above.
1445 Two, it keeps line number notes as matched as may be. */
1446 if (ninsns)
1447 {
1448 bb1 = BLOCK_FOR_INSN (last1);
1449 while (last1 != BB_HEAD (bb1) && !NONDEBUG_INSN_P (PREV_INSN (last1)))
1450 last1 = PREV_INSN (last1);
1451
1452 if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1453 last1 = PREV_INSN (last1);
1454
1455 bb2 = BLOCK_FOR_INSN (last2);
1456 while (last2 != BB_HEAD (bb2) && !NONDEBUG_INSN_P (PREV_INSN (last2)))
1457 last2 = PREV_INSN (last2);
1458
1459 if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1460 last2 = PREV_INSN (last2);
1461
1462 *f1 = last1;
1463 *f2 = last2;
1464 }
1465
1466 if (dir_p)
1467 *dir_p = last_dir;
1468 return ninsns;
1469 }
1470
1471 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1472 the head of the two blocks. Do not include jumps at the end.
1473 If STOP_AFTER is nonzero, stop after finding that many matching
1474 instructions. If STOP_AFTER is zero, count all INSN_P insns, if it is
1475 non-zero, only count active insns. */
1476
1477 int
flow_find_head_matching_sequence(basic_block bb1,basic_block bb2,rtx_insn ** f1,rtx_insn ** f2,int stop_after)1478 flow_find_head_matching_sequence (basic_block bb1, basic_block bb2, rtx_insn **f1,
1479 rtx_insn **f2, int stop_after)
1480 {
1481 rtx_insn *i1, *i2, *last1, *last2, *beforelast1, *beforelast2;
1482 int ninsns = 0;
1483 edge e;
1484 edge_iterator ei;
1485 int nehedges1 = 0, nehedges2 = 0;
1486
1487 FOR_EACH_EDGE (e, ei, bb1->succs)
1488 if (e->flags & EDGE_EH)
1489 nehedges1++;
1490 FOR_EACH_EDGE (e, ei, bb2->succs)
1491 if (e->flags & EDGE_EH)
1492 nehedges2++;
1493
1494 i1 = BB_HEAD (bb1);
1495 i2 = BB_HEAD (bb2);
1496 last1 = beforelast1 = last2 = beforelast2 = NULL;
1497
1498 while (true)
1499 {
1500 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1501 while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
1502 {
1503 if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG)
1504 break;
1505 i1 = NEXT_INSN (i1);
1506 }
1507
1508 while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
1509 {
1510 if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG)
1511 break;
1512 i2 = NEXT_INSN (i2);
1513 }
1514
1515 if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
1516 || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
1517 break;
1518
1519 if (NOTE_P (i1) || NOTE_P (i2)
1520 || JUMP_P (i1) || JUMP_P (i2))
1521 break;
1522
1523 /* A sanity check to make sure we're not merging insns with different
1524 effects on EH. If only one of them ends a basic block, it shouldn't
1525 have an EH edge; if both end a basic block, there should be the same
1526 number of EH edges. */
1527 if ((i1 == BB_END (bb1) && i2 != BB_END (bb2)
1528 && nehedges1 > 0)
1529 || (i2 == BB_END (bb2) && i1 != BB_END (bb1)
1530 && nehedges2 > 0)
1531 || (i1 == BB_END (bb1) && i2 == BB_END (bb2)
1532 && nehedges1 != nehedges2))
1533 break;
1534
1535 if (old_insns_match_p (0, i1, i2) != dir_both)
1536 break;
1537
1538 merge_memattrs (i1, i2);
1539
1540 /* Don't begin a cross-jump with a NOTE insn. */
1541 if (INSN_P (i1))
1542 {
1543 merge_notes (i1, i2);
1544
1545 beforelast1 = last1, beforelast2 = last2;
1546 last1 = i1, last2 = i2;
1547 if (!stop_after || active_insn_p (i1))
1548 ninsns++;
1549 }
1550
1551 if (i1 == BB_END (bb1) || i2 == BB_END (bb2)
1552 || (stop_after > 0 && ninsns == stop_after))
1553 break;
1554
1555 i1 = NEXT_INSN (i1);
1556 i2 = NEXT_INSN (i2);
1557 }
1558
1559 /* Don't allow a compare to be shared by cross-jumping unless the insn
1560 after the compare is also shared. */
1561 if (HAVE_cc0 && ninsns && reg_mentioned_p (cc0_rtx, last1)
1562 && sets_cc0_p (last1))
1563 last1 = beforelast1, last2 = beforelast2, ninsns--;
1564
1565 if (ninsns)
1566 {
1567 *f1 = last1;
1568 *f2 = last2;
1569 }
1570
1571 return ninsns;
1572 }
1573
1574 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1575 the branch instruction. This means that if we commonize the control
1576 flow before end of the basic block, the semantic remains unchanged.
1577
1578 We may assume that there exists one edge with a common destination. */
1579
1580 static bool
outgoing_edges_match(int mode,basic_block bb1,basic_block bb2)1581 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1582 {
1583 int nehedges1 = 0, nehedges2 = 0;
1584 edge fallthru1 = 0, fallthru2 = 0;
1585 edge e1, e2;
1586 edge_iterator ei;
1587
1588 /* If we performed shrink-wrapping, edges to the exit block can
1589 only be distinguished for JUMP_INSNs. The two paths may differ in
1590 whether they went through the prologue. Sibcalls are fine, we know
1591 that we either didn't need or inserted an epilogue before them. */
1592 if (crtl->shrink_wrapped
1593 && single_succ_p (bb1)
1594 && single_succ (bb1) == EXIT_BLOCK_PTR_FOR_FN (cfun)
1595 && (!JUMP_P (BB_END (bb1))
1596 /* Punt if the only successor is a fake edge to exit, the jump
1597 must be some weird one. */
1598 || (single_succ_edge (bb1)->flags & EDGE_FAKE) != 0)
1599 && !(CALL_P (BB_END (bb1)) && SIBLING_CALL_P (BB_END (bb1))))
1600 return false;
1601
1602 /* If BB1 has only one successor, we may be looking at either an
1603 unconditional jump, or a fake edge to exit. */
1604 if (single_succ_p (bb1)
1605 && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1606 && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1607 return (single_succ_p (bb2)
1608 && (single_succ_edge (bb2)->flags
1609 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1610 && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1611
1612 /* Match conditional jumps - this may get tricky when fallthru and branch
1613 edges are crossed. */
1614 if (EDGE_COUNT (bb1->succs) == 2
1615 && any_condjump_p (BB_END (bb1))
1616 && onlyjump_p (BB_END (bb1)))
1617 {
1618 edge b1, f1, b2, f2;
1619 bool reverse, match;
1620 rtx set1, set2, cond1, cond2;
1621 enum rtx_code code1, code2;
1622
1623 if (EDGE_COUNT (bb2->succs) != 2
1624 || !any_condjump_p (BB_END (bb2))
1625 || !onlyjump_p (BB_END (bb2)))
1626 return false;
1627
1628 b1 = BRANCH_EDGE (bb1);
1629 b2 = BRANCH_EDGE (bb2);
1630 f1 = FALLTHRU_EDGE (bb1);
1631 f2 = FALLTHRU_EDGE (bb2);
1632
1633 /* Get around possible forwarders on fallthru edges. Other cases
1634 should be optimized out already. */
1635 if (FORWARDER_BLOCK_P (f1->dest))
1636 f1 = single_succ_edge (f1->dest);
1637
1638 if (FORWARDER_BLOCK_P (f2->dest))
1639 f2 = single_succ_edge (f2->dest);
1640
1641 /* To simplify use of this function, return false if there are
1642 unneeded forwarder blocks. These will get eliminated later
1643 during cleanup_cfg. */
1644 if (FORWARDER_BLOCK_P (f1->dest)
1645 || FORWARDER_BLOCK_P (f2->dest)
1646 || FORWARDER_BLOCK_P (b1->dest)
1647 || FORWARDER_BLOCK_P (b2->dest))
1648 return false;
1649
1650 if (f1->dest == f2->dest && b1->dest == b2->dest)
1651 reverse = false;
1652 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1653 reverse = true;
1654 else
1655 return false;
1656
1657 set1 = pc_set (BB_END (bb1));
1658 set2 = pc_set (BB_END (bb2));
1659 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1660 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1661 reverse = !reverse;
1662
1663 cond1 = XEXP (SET_SRC (set1), 0);
1664 cond2 = XEXP (SET_SRC (set2), 0);
1665 code1 = GET_CODE (cond1);
1666 if (reverse)
1667 code2 = reversed_comparison_code (cond2, BB_END (bb2));
1668 else
1669 code2 = GET_CODE (cond2);
1670
1671 if (code2 == UNKNOWN)
1672 return false;
1673
1674 /* Verify codes and operands match. */
1675 match = ((code1 == code2
1676 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1677 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1678 || (code1 == swap_condition (code2)
1679 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1680 XEXP (cond2, 0))
1681 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1682 XEXP (cond2, 1))));
1683
1684 /* If we return true, we will join the blocks. Which means that
1685 we will only have one branch prediction bit to work with. Thus
1686 we require the existing branches to have probabilities that are
1687 roughly similar. */
1688 if (match
1689 && optimize_bb_for_speed_p (bb1)
1690 && optimize_bb_for_speed_p (bb2))
1691 {
1692 profile_probability prob2;
1693
1694 if (b1->dest == b2->dest)
1695 prob2 = b2->probability;
1696 else
1697 /* Do not use f2 probability as f2 may be forwarded. */
1698 prob2 = b2->probability.invert ();
1699
1700 /* Fail if the difference in probabilities is greater than 50%.
1701 This rules out two well-predicted branches with opposite
1702 outcomes. */
1703 if (b1->probability.differs_lot_from_p (prob2))
1704 {
1705 if (dump_file)
1706 {
1707 fprintf (dump_file,
1708 "Outcomes of branch in bb %i and %i differ too"
1709 " much (", bb1->index, bb2->index);
1710 b1->probability.dump (dump_file);
1711 prob2.dump (dump_file);
1712 fprintf (dump_file, ")\n");
1713 }
1714 return false;
1715 }
1716 }
1717
1718 if (dump_file && match)
1719 fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1720 bb1->index, bb2->index);
1721
1722 return match;
1723 }
1724
1725 /* Generic case - we are seeing a computed jump, table jump or trapping
1726 instruction. */
1727
1728 /* Check whether there are tablejumps in the end of BB1 and BB2.
1729 Return true if they are identical. */
1730 {
1731 rtx_insn *label1, *label2;
1732 rtx_jump_table_data *table1, *table2;
1733
1734 if (tablejump_p (BB_END (bb1), &label1, &table1)
1735 && tablejump_p (BB_END (bb2), &label2, &table2)
1736 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1737 {
1738 /* The labels should never be the same rtx. If they really are same
1739 the jump tables are same too. So disable crossjumping of blocks BB1
1740 and BB2 because when deleting the common insns in the end of BB1
1741 by delete_basic_block () the jump table would be deleted too. */
1742 /* If LABEL2 is referenced in BB1->END do not do anything
1743 because we would loose information when replacing
1744 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1745 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1746 {
1747 /* Set IDENTICAL to true when the tables are identical. */
1748 bool identical = false;
1749 rtx p1, p2;
1750
1751 p1 = PATTERN (table1);
1752 p2 = PATTERN (table2);
1753 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1754 {
1755 identical = true;
1756 }
1757 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1758 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1759 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1760 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1761 {
1762 int i;
1763
1764 identical = true;
1765 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1766 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1767 identical = false;
1768 }
1769
1770 if (identical)
1771 {
1772 bool match;
1773
1774 /* Temporarily replace references to LABEL1 with LABEL2
1775 in BB1->END so that we could compare the instructions. */
1776 replace_label_in_insn (BB_END (bb1), label1, label2, false);
1777
1778 match = (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2))
1779 == dir_both);
1780 if (dump_file && match)
1781 fprintf (dump_file,
1782 "Tablejumps in bb %i and %i match.\n",
1783 bb1->index, bb2->index);
1784
1785 /* Set the original label in BB1->END because when deleting
1786 a block whose end is a tablejump, the tablejump referenced
1787 from the instruction is deleted too. */
1788 replace_label_in_insn (BB_END (bb1), label2, label1, false);
1789
1790 return match;
1791 }
1792 }
1793 return false;
1794 }
1795 }
1796
1797 /* Find the last non-debug non-note instruction in each bb, except
1798 stop when we see the NOTE_INSN_BASIC_BLOCK, as old_insns_match_p
1799 handles that case specially. old_insns_match_p does not handle
1800 other types of instruction notes. */
1801 rtx_insn *last1 = BB_END (bb1);
1802 rtx_insn *last2 = BB_END (bb2);
1803 while (!NOTE_INSN_BASIC_BLOCK_P (last1) &&
1804 (DEBUG_INSN_P (last1) || NOTE_P (last1)))
1805 last1 = PREV_INSN (last1);
1806 while (!NOTE_INSN_BASIC_BLOCK_P (last2) &&
1807 (DEBUG_INSN_P (last2) || NOTE_P (last2)))
1808 last2 = PREV_INSN (last2);
1809 gcc_assert (last1 && last2);
1810
1811 /* First ensure that the instructions match. There may be many outgoing
1812 edges so this test is generally cheaper. */
1813 if (old_insns_match_p (mode, last1, last2) != dir_both)
1814 return false;
1815
1816 /* Search the outgoing edges, ensure that the counts do match, find possible
1817 fallthru and exception handling edges since these needs more
1818 validation. */
1819 if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
1820 return false;
1821
1822 bool nonfakeedges = false;
1823 FOR_EACH_EDGE (e1, ei, bb1->succs)
1824 {
1825 e2 = EDGE_SUCC (bb2, ei.index);
1826
1827 if ((e1->flags & EDGE_FAKE) == 0)
1828 nonfakeedges = true;
1829
1830 if (e1->flags & EDGE_EH)
1831 nehedges1++;
1832
1833 if (e2->flags & EDGE_EH)
1834 nehedges2++;
1835
1836 if (e1->flags & EDGE_FALLTHRU)
1837 fallthru1 = e1;
1838 if (e2->flags & EDGE_FALLTHRU)
1839 fallthru2 = e2;
1840 }
1841
1842 /* If number of edges of various types does not match, fail. */
1843 if (nehedges1 != nehedges2
1844 || (fallthru1 != 0) != (fallthru2 != 0))
1845 return false;
1846
1847 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1848 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1849 attempt to optimize, as the two basic blocks might have different
1850 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1851 traps there should be REG_ARG_SIZE notes, they could be missing
1852 for __builtin_unreachable () uses though. */
1853 if (!nonfakeedges
1854 && !ACCUMULATE_OUTGOING_ARGS
1855 && (!INSN_P (last1)
1856 || !find_reg_note (last1, REG_ARGS_SIZE, NULL)))
1857 return false;
1858
1859 /* fallthru edges must be forwarded to the same destination. */
1860 if (fallthru1)
1861 {
1862 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1863 ? single_succ (fallthru1->dest): fallthru1->dest);
1864 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1865 ? single_succ (fallthru2->dest): fallthru2->dest);
1866
1867 if (d1 != d2)
1868 return false;
1869 }
1870
1871 /* Ensure the same EH region. */
1872 {
1873 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1874 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1875
1876 if (!n1 && n2)
1877 return false;
1878
1879 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1880 return false;
1881 }
1882
1883 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1884 version of sequence abstraction. */
1885 FOR_EACH_EDGE (e1, ei, bb2->succs)
1886 {
1887 edge e2;
1888 edge_iterator ei;
1889 basic_block d1 = e1->dest;
1890
1891 if (FORWARDER_BLOCK_P (d1))
1892 d1 = EDGE_SUCC (d1, 0)->dest;
1893
1894 FOR_EACH_EDGE (e2, ei, bb1->succs)
1895 {
1896 basic_block d2 = e2->dest;
1897 if (FORWARDER_BLOCK_P (d2))
1898 d2 = EDGE_SUCC (d2, 0)->dest;
1899 if (d1 == d2)
1900 break;
1901 }
1902
1903 if (!e2)
1904 return false;
1905 }
1906
1907 return true;
1908 }
1909
1910 /* Returns true if BB basic block has a preserve label. */
1911
1912 static bool
block_has_preserve_label(basic_block bb)1913 block_has_preserve_label (basic_block bb)
1914 {
1915 return (bb
1916 && block_label (bb)
1917 && LABEL_PRESERVE_P (block_label (bb)));
1918 }
1919
1920 /* E1 and E2 are edges with the same destination block. Search their
1921 predecessors for common code. If found, redirect control flow from
1922 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1923 or the other way around (dir_backward). DIR specifies the allowed
1924 replacement direction. */
1925
1926 static bool
try_crossjump_to_edge(int mode,edge e1,edge e2,enum replace_direction dir)1927 try_crossjump_to_edge (int mode, edge e1, edge e2,
1928 enum replace_direction dir)
1929 {
1930 int nmatch;
1931 basic_block src1 = e1->src, src2 = e2->src;
1932 basic_block redirect_to, redirect_from, to_remove;
1933 basic_block osrc1, osrc2, redirect_edges_to, tmp;
1934 rtx_insn *newpos1, *newpos2;
1935 edge s;
1936 edge_iterator ei;
1937
1938 newpos1 = newpos2 = NULL;
1939
1940 /* Search backward through forwarder blocks. We don't need to worry
1941 about multiple entry or chained forwarders, as they will be optimized
1942 away. We do this to look past the unconditional jump following a
1943 conditional jump that is required due to the current CFG shape. */
1944 if (single_pred_p (src1)
1945 && FORWARDER_BLOCK_P (src1))
1946 e1 = single_pred_edge (src1), src1 = e1->src;
1947
1948 if (single_pred_p (src2)
1949 && FORWARDER_BLOCK_P (src2))
1950 e2 = single_pred_edge (src2), src2 = e2->src;
1951
1952 /* Nothing to do if we reach ENTRY, or a common source block. */
1953 if (src1 == ENTRY_BLOCK_PTR_FOR_FN (cfun) || src2
1954 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1955 return false;
1956 if (src1 == src2)
1957 return false;
1958
1959 /* Seeing more than 1 forwarder blocks would confuse us later... */
1960 if (FORWARDER_BLOCK_P (e1->dest)
1961 && FORWARDER_BLOCK_P (single_succ (e1->dest)))
1962 return false;
1963
1964 if (FORWARDER_BLOCK_P (e2->dest)
1965 && FORWARDER_BLOCK_P (single_succ (e2->dest)))
1966 return false;
1967
1968 /* Likewise with dead code (possibly newly created by the other optimizations
1969 of cfg_cleanup). */
1970 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1971 return false;
1972
1973 /* Do not turn corssing edge to non-crossing or vice versa after reload. */
1974 if (BB_PARTITION (src1) != BB_PARTITION (src2)
1975 && reload_completed)
1976 return false;
1977
1978 /* Look for the common insn sequence, part the first ... */
1979 if (!outgoing_edges_match (mode, src1, src2))
1980 return false;
1981
1982 /* ... and part the second. */
1983 nmatch = flow_find_cross_jump (src1, src2, &newpos1, &newpos2, &dir);
1984
1985 osrc1 = src1;
1986 osrc2 = src2;
1987 if (newpos1 != NULL_RTX)
1988 src1 = BLOCK_FOR_INSN (newpos1);
1989 if (newpos2 != NULL_RTX)
1990 src2 = BLOCK_FOR_INSN (newpos2);
1991
1992 /* Check that SRC1 and SRC2 have preds again. They may have changed
1993 above due to the call to flow_find_cross_jump. */
1994 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1995 return false;
1996
1997 if (dir == dir_backward)
1998 {
1999 std::swap (osrc1, osrc2);
2000 std::swap (src1, src2);
2001 std::swap (e1, e2);
2002 std::swap (newpos1, newpos2);
2003 }
2004
2005 /* Don't proceed with the crossjump unless we found a sufficient number
2006 of matching instructions or the 'from' block was totally matched
2007 (such that its predecessors will hopefully be redirected and the
2008 block removed). */
2009 if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
2010 && (newpos1 != BB_HEAD (src1)))
2011 return false;
2012
2013 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
2014 if (block_has_preserve_label (e1->dest)
2015 && (e1->flags & EDGE_ABNORMAL))
2016 return false;
2017
2018 /* Here we know that the insns in the end of SRC1 which are common with SRC2
2019 will be deleted.
2020 If we have tablejumps in the end of SRC1 and SRC2
2021 they have been already compared for equivalence in outgoing_edges_match ()
2022 so replace the references to TABLE1 by references to TABLE2. */
2023 {
2024 rtx_insn *label1, *label2;
2025 rtx_jump_table_data *table1, *table2;
2026
2027 if (tablejump_p (BB_END (osrc1), &label1, &table1)
2028 && tablejump_p (BB_END (osrc2), &label2, &table2)
2029 && label1 != label2)
2030 {
2031 rtx_insn *insn;
2032
2033 /* Replace references to LABEL1 with LABEL2. */
2034 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2035 {
2036 /* Do not replace the label in SRC1->END because when deleting
2037 a block whose end is a tablejump, the tablejump referenced
2038 from the instruction is deleted too. */
2039 if (insn != BB_END (osrc1))
2040 replace_label_in_insn (insn, label1, label2, true);
2041 }
2042 }
2043 }
2044
2045 /* Avoid splitting if possible. We must always split when SRC2 has
2046 EH predecessor edges, or we may end up with basic blocks with both
2047 normal and EH predecessor edges. */
2048 if (newpos2 == BB_HEAD (src2)
2049 && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
2050 redirect_to = src2;
2051 else
2052 {
2053 if (newpos2 == BB_HEAD (src2))
2054 {
2055 /* Skip possible basic block header. */
2056 if (LABEL_P (newpos2))
2057 newpos2 = NEXT_INSN (newpos2);
2058 while (DEBUG_INSN_P (newpos2))
2059 newpos2 = NEXT_INSN (newpos2);
2060 if (NOTE_P (newpos2))
2061 newpos2 = NEXT_INSN (newpos2);
2062 while (DEBUG_INSN_P (newpos2))
2063 newpos2 = NEXT_INSN (newpos2);
2064 }
2065
2066 if (dump_file)
2067 fprintf (dump_file, "Splitting bb %i before %i insns\n",
2068 src2->index, nmatch);
2069 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
2070 }
2071
2072 if (dump_file)
2073 fprintf (dump_file,
2074 "Cross jumping from bb %i to bb %i; %i common insns\n",
2075 src1->index, src2->index, nmatch);
2076
2077 /* We may have some registers visible through the block. */
2078 df_set_bb_dirty (redirect_to);
2079
2080 if (osrc2 == src2)
2081 redirect_edges_to = redirect_to;
2082 else
2083 redirect_edges_to = osrc2;
2084
2085 /* Recompute the counts of destinations of outgoing edges. */
2086 FOR_EACH_EDGE (s, ei, redirect_edges_to->succs)
2087 {
2088 edge s2;
2089 edge_iterator ei;
2090 basic_block d = s->dest;
2091
2092 if (FORWARDER_BLOCK_P (d))
2093 d = single_succ (d);
2094
2095 FOR_EACH_EDGE (s2, ei, src1->succs)
2096 {
2097 basic_block d2 = s2->dest;
2098 if (FORWARDER_BLOCK_P (d2))
2099 d2 = single_succ (d2);
2100 if (d == d2)
2101 break;
2102 }
2103
2104 /* Take care to update possible forwarder blocks. We verified
2105 that there is no more than one in the chain, so we can't run
2106 into infinite loop. */
2107 if (FORWARDER_BLOCK_P (s->dest))
2108 s->dest->count += s->count ();
2109
2110 if (FORWARDER_BLOCK_P (s2->dest))
2111 s2->dest->count -= s->count ();
2112
2113 s->probability = s->probability.combine_with_count
2114 (redirect_edges_to->count,
2115 s2->probability, src1->count);
2116 }
2117
2118 /* Adjust count for the block. An earlier jump
2119 threading pass may have left the profile in an inconsistent
2120 state (see update_bb_profile_for_threading) so we must be
2121 prepared for overflows. */
2122 tmp = redirect_to;
2123 do
2124 {
2125 tmp->count += src1->count;
2126 if (tmp == redirect_edges_to)
2127 break;
2128 tmp = find_fallthru_edge (tmp->succs)->dest;
2129 }
2130 while (true);
2131 update_br_prob_note (redirect_edges_to);
2132
2133 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2134
2135 /* Skip possible basic block header. */
2136 if (LABEL_P (newpos1))
2137 newpos1 = NEXT_INSN (newpos1);
2138
2139 while (DEBUG_INSN_P (newpos1))
2140 newpos1 = NEXT_INSN (newpos1);
2141
2142 if (NOTE_INSN_BASIC_BLOCK_P (newpos1))
2143 newpos1 = NEXT_INSN (newpos1);
2144
2145 while (DEBUG_INSN_P (newpos1))
2146 newpos1 = NEXT_INSN (newpos1);
2147
2148 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
2149 to_remove = single_succ (redirect_from);
2150
2151 redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
2152 delete_basic_block (to_remove);
2153
2154 update_forwarder_flag (redirect_from);
2155 if (redirect_to != src2)
2156 update_forwarder_flag (src2);
2157
2158 return true;
2159 }
2160
2161 /* Search the predecessors of BB for common insn sequences. When found,
2162 share code between them by redirecting control flow. Return true if
2163 any changes made. */
2164
2165 static bool
try_crossjump_bb(int mode,basic_block bb)2166 try_crossjump_bb (int mode, basic_block bb)
2167 {
2168 edge e, e2, fallthru;
2169 bool changed;
2170 unsigned max, ix, ix2;
2171
2172 /* Nothing to do if there is not at least two incoming edges. */
2173 if (EDGE_COUNT (bb->preds) < 2)
2174 return false;
2175
2176 /* Don't crossjump if this block ends in a computed jump,
2177 unless we are optimizing for size. */
2178 if (optimize_bb_for_size_p (bb)
2179 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
2180 && computed_jump_p (BB_END (bb)))
2181 return false;
2182
2183 /* If we are partitioning hot/cold basic blocks, we don't want to
2184 mess up unconditional or indirect jumps that cross between hot
2185 and cold sections.
2186
2187 Basic block partitioning may result in some jumps that appear to
2188 be optimizable (or blocks that appear to be mergeable), but which really
2189 must be left untouched (they are required to make it safely across
2190 partition boundaries). See the comments at the top of
2191 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2192
2193 if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
2194 BB_PARTITION (EDGE_PRED (bb, 1)->src)
2195 || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
2196 return false;
2197
2198 /* It is always cheapest to redirect a block that ends in a branch to
2199 a block that falls through into BB, as that adds no branches to the
2200 program. We'll try that combination first. */
2201 fallthru = NULL;
2202 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
2203
2204 if (EDGE_COUNT (bb->preds) > max)
2205 return false;
2206
2207 fallthru = find_fallthru_edge (bb->preds);
2208
2209 changed = false;
2210 for (ix = 0; ix < EDGE_COUNT (bb->preds);)
2211 {
2212 e = EDGE_PRED (bb, ix);
2213 ix++;
2214
2215 /* As noted above, first try with the fallthru predecessor (or, a
2216 fallthru predecessor if we are in cfglayout mode). */
2217 if (fallthru)
2218 {
2219 /* Don't combine the fallthru edge into anything else.
2220 If there is a match, we'll do it the other way around. */
2221 if (e == fallthru)
2222 continue;
2223 /* If nothing changed since the last attempt, there is nothing
2224 we can do. */
2225 if (!first_pass
2226 && !((e->src->flags & BB_MODIFIED)
2227 || (fallthru->src->flags & BB_MODIFIED)))
2228 continue;
2229
2230 if (try_crossjump_to_edge (mode, e, fallthru, dir_forward))
2231 {
2232 changed = true;
2233 ix = 0;
2234 continue;
2235 }
2236 }
2237
2238 /* Non-obvious work limiting check: Recognize that we're going
2239 to call try_crossjump_bb on every basic block. So if we have
2240 two blocks with lots of outgoing edges (a switch) and they
2241 share lots of common destinations, then we would do the
2242 cross-jump check once for each common destination.
2243
2244 Now, if the blocks actually are cross-jump candidates, then
2245 all of their destinations will be shared. Which means that
2246 we only need check them for cross-jump candidacy once. We
2247 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2248 choosing to do the check from the block for which the edge
2249 in question is the first successor of A. */
2250 if (EDGE_SUCC (e->src, 0) != e)
2251 continue;
2252
2253 for (ix2 = 0; ix2 < EDGE_COUNT (bb->preds); ix2++)
2254 {
2255 e2 = EDGE_PRED (bb, ix2);
2256
2257 if (e2 == e)
2258 continue;
2259
2260 /* We've already checked the fallthru edge above. */
2261 if (e2 == fallthru)
2262 continue;
2263
2264 /* The "first successor" check above only prevents multiple
2265 checks of crossjump(A,B). In order to prevent redundant
2266 checks of crossjump(B,A), require that A be the block
2267 with the lowest index. */
2268 if (e->src->index > e2->src->index)
2269 continue;
2270
2271 /* If nothing changed since the last attempt, there is nothing
2272 we can do. */
2273 if (!first_pass
2274 && !((e->src->flags & BB_MODIFIED)
2275 || (e2->src->flags & BB_MODIFIED)))
2276 continue;
2277
2278 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2279 direction. */
2280 if (try_crossjump_to_edge (mode, e, e2, dir_both))
2281 {
2282 changed = true;
2283 ix = 0;
2284 break;
2285 }
2286 }
2287 }
2288
2289 if (changed)
2290 crossjumps_occurred = true;
2291
2292 return changed;
2293 }
2294
2295 /* Search the successors of BB for common insn sequences. When found,
2296 share code between them by moving it across the basic block
2297 boundary. Return true if any changes made. */
2298
2299 static bool
try_head_merge_bb(basic_block bb)2300 try_head_merge_bb (basic_block bb)
2301 {
2302 basic_block final_dest_bb = NULL;
2303 int max_match = INT_MAX;
2304 edge e0;
2305 rtx_insn **headptr, **currptr, **nextptr;
2306 bool changed, moveall;
2307 unsigned ix;
2308 rtx_insn *e0_last_head;
2309 rtx cond;
2310 rtx_insn *move_before;
2311 unsigned nedges = EDGE_COUNT (bb->succs);
2312 rtx_insn *jump = BB_END (bb);
2313 regset live, live_union;
2314
2315 /* Nothing to do if there is not at least two outgoing edges. */
2316 if (nedges < 2)
2317 return false;
2318
2319 /* Don't crossjump if this block ends in a computed jump,
2320 unless we are optimizing for size. */
2321 if (optimize_bb_for_size_p (bb)
2322 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
2323 && computed_jump_p (BB_END (bb)))
2324 return false;
2325
2326 cond = get_condition (jump, &move_before, true, false);
2327 if (cond == NULL_RTX)
2328 {
2329 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, jump))
2330 move_before = prev_nonnote_nondebug_insn (jump);
2331 else
2332 move_before = jump;
2333 }
2334
2335 for (ix = 0; ix < nedges; ix++)
2336 if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
2337 return false;
2338
2339 for (ix = 0; ix < nedges; ix++)
2340 {
2341 edge e = EDGE_SUCC (bb, ix);
2342 basic_block other_bb = e->dest;
2343
2344 if (df_get_bb_dirty (other_bb))
2345 {
2346 block_was_dirty = true;
2347 return false;
2348 }
2349
2350 if (e->flags & EDGE_ABNORMAL)
2351 return false;
2352
2353 /* Normally, all destination blocks must only be reachable from this
2354 block, i.e. they must have one incoming edge.
2355
2356 There is one special case we can handle, that of multiple consecutive
2357 jumps where the first jumps to one of the targets of the second jump.
2358 This happens frequently in switch statements for default labels.
2359 The structure is as follows:
2360 FINAL_DEST_BB
2361 ....
2362 if (cond) jump A;
2363 fall through
2364 BB
2365 jump with targets A, B, C, D...
2366 A
2367 has two incoming edges, from FINAL_DEST_BB and BB
2368
2369 In this case, we can try to move the insns through BB and into
2370 FINAL_DEST_BB. */
2371 if (EDGE_COUNT (other_bb->preds) != 1)
2372 {
2373 edge incoming_edge, incoming_bb_other_edge;
2374 edge_iterator ei;
2375
2376 if (final_dest_bb != NULL
2377 || EDGE_COUNT (other_bb->preds) != 2)
2378 return false;
2379
2380 /* We must be able to move the insns across the whole block. */
2381 move_before = BB_HEAD (bb);
2382 while (!NONDEBUG_INSN_P (move_before))
2383 move_before = NEXT_INSN (move_before);
2384
2385 if (EDGE_COUNT (bb->preds) != 1)
2386 return false;
2387 incoming_edge = EDGE_PRED (bb, 0);
2388 final_dest_bb = incoming_edge->src;
2389 if (EDGE_COUNT (final_dest_bb->succs) != 2)
2390 return false;
2391 FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
2392 if (incoming_bb_other_edge != incoming_edge)
2393 break;
2394 if (incoming_bb_other_edge->dest != other_bb)
2395 return false;
2396 }
2397 }
2398
2399 e0 = EDGE_SUCC (bb, 0);
2400 e0_last_head = NULL;
2401 changed = false;
2402
2403 for (ix = 1; ix < nedges; ix++)
2404 {
2405 edge e = EDGE_SUCC (bb, ix);
2406 rtx_insn *e0_last, *e_last;
2407 int nmatch;
2408
2409 nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
2410 &e0_last, &e_last, 0);
2411 if (nmatch == 0)
2412 return false;
2413
2414 if (nmatch < max_match)
2415 {
2416 max_match = nmatch;
2417 e0_last_head = e0_last;
2418 }
2419 }
2420
2421 /* If we matched an entire block, we probably have to avoid moving the
2422 last insn. */
2423 if (max_match > 0
2424 && e0_last_head == BB_END (e0->dest)
2425 && (find_reg_note (e0_last_head, REG_EH_REGION, 0)
2426 || control_flow_insn_p (e0_last_head)))
2427 {
2428 max_match--;
2429 if (max_match == 0)
2430 return false;
2431 e0_last_head = prev_real_nondebug_insn (e0_last_head);
2432 }
2433
2434 if (max_match == 0)
2435 return false;
2436
2437 /* We must find a union of the live registers at each of the end points. */
2438 live = BITMAP_ALLOC (NULL);
2439 live_union = BITMAP_ALLOC (NULL);
2440
2441 currptr = XNEWVEC (rtx_insn *, nedges);
2442 headptr = XNEWVEC (rtx_insn *, nedges);
2443 nextptr = XNEWVEC (rtx_insn *, nedges);
2444
2445 for (ix = 0; ix < nedges; ix++)
2446 {
2447 int j;
2448 basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
2449 rtx_insn *head = BB_HEAD (merge_bb);
2450
2451 while (!NONDEBUG_INSN_P (head))
2452 head = NEXT_INSN (head);
2453 headptr[ix] = head;
2454 currptr[ix] = head;
2455
2456 /* Compute the end point and live information */
2457 for (j = 1; j < max_match; j++)
2458 do
2459 head = NEXT_INSN (head);
2460 while (!NONDEBUG_INSN_P (head));
2461 simulate_backwards_to_point (merge_bb, live, head);
2462 IOR_REG_SET (live_union, live);
2463 }
2464
2465 /* If we're moving across two blocks, verify the validity of the
2466 first move, then adjust the target and let the loop below deal
2467 with the final move. */
2468 if (final_dest_bb != NULL)
2469 {
2470 rtx_insn *move_upto;
2471
2472 moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
2473 jump, e0->dest, live_union,
2474 NULL, &move_upto);
2475 if (!moveall)
2476 {
2477 if (move_upto == NULL_RTX)
2478 goto out;
2479
2480 while (e0_last_head != move_upto)
2481 {
2482 df_simulate_one_insn_backwards (e0->dest, e0_last_head,
2483 live_union);
2484 e0_last_head = PREV_INSN (e0_last_head);
2485 }
2486 }
2487 if (e0_last_head == NULL_RTX)
2488 goto out;
2489
2490 jump = BB_END (final_dest_bb);
2491 cond = get_condition (jump, &move_before, true, false);
2492 if (cond == NULL_RTX)
2493 {
2494 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, jump))
2495 move_before = prev_nonnote_nondebug_insn (jump);
2496 else
2497 move_before = jump;
2498 }
2499 }
2500
2501 do
2502 {
2503 rtx_insn *move_upto;
2504 moveall = can_move_insns_across (currptr[0], e0_last_head,
2505 move_before, jump, e0->dest, live_union,
2506 NULL, &move_upto);
2507 if (!moveall && move_upto == NULL_RTX)
2508 {
2509 if (jump == move_before)
2510 break;
2511
2512 /* Try again, using a different insertion point. */
2513 move_before = jump;
2514
2515 /* Don't try moving before a cc0 user, as that may invalidate
2516 the cc0. */
2517 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, jump))
2518 break;
2519
2520 continue;
2521 }
2522
2523 if (final_dest_bb && !moveall)
2524 /* We haven't checked whether a partial move would be OK for the first
2525 move, so we have to fail this case. */
2526 break;
2527
2528 changed = true;
2529 for (;;)
2530 {
2531 if (currptr[0] == move_upto)
2532 break;
2533 for (ix = 0; ix < nedges; ix++)
2534 {
2535 rtx_insn *curr = currptr[ix];
2536 do
2537 curr = NEXT_INSN (curr);
2538 while (!NONDEBUG_INSN_P (curr));
2539 currptr[ix] = curr;
2540 }
2541 }
2542
2543 /* If we can't currently move all of the identical insns, remember
2544 each insn after the range that we'll merge. */
2545 if (!moveall)
2546 for (ix = 0; ix < nedges; ix++)
2547 {
2548 rtx_insn *curr = currptr[ix];
2549 do
2550 curr = NEXT_INSN (curr);
2551 while (!NONDEBUG_INSN_P (curr));
2552 nextptr[ix] = curr;
2553 }
2554
2555 reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
2556 df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
2557 if (final_dest_bb != NULL)
2558 df_set_bb_dirty (final_dest_bb);
2559 df_set_bb_dirty (bb);
2560 for (ix = 1; ix < nedges; ix++)
2561 {
2562 df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
2563 delete_insn_chain (headptr[ix], currptr[ix], false);
2564 }
2565 if (!moveall)
2566 {
2567 if (jump == move_before)
2568 break;
2569
2570 /* For the unmerged insns, try a different insertion point. */
2571 move_before = jump;
2572
2573 /* Don't try moving before a cc0 user, as that may invalidate
2574 the cc0. */
2575 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, jump))
2576 break;
2577
2578 for (ix = 0; ix < nedges; ix++)
2579 currptr[ix] = headptr[ix] = nextptr[ix];
2580 }
2581 }
2582 while (!moveall);
2583
2584 out:
2585 free (currptr);
2586 free (headptr);
2587 free (nextptr);
2588
2589 crossjumps_occurred |= changed;
2590
2591 return changed;
2592 }
2593
2594 /* Return true if BB contains just bb note, or bb note followed
2595 by only DEBUG_INSNs. */
2596
2597 static bool
trivially_empty_bb_p(basic_block bb)2598 trivially_empty_bb_p (basic_block bb)
2599 {
2600 rtx_insn *insn = BB_END (bb);
2601
2602 while (1)
2603 {
2604 if (insn == BB_HEAD (bb))
2605 return true;
2606 if (!DEBUG_INSN_P (insn))
2607 return false;
2608 insn = PREV_INSN (insn);
2609 }
2610 }
2611
2612 /* Return true if BB contains just a return and possibly a USE of the
2613 return value. Fill in *RET and *USE with the return and use insns
2614 if any found, otherwise NULL. All CLOBBERs are ignored. */
2615
2616 static bool
bb_is_just_return(basic_block bb,rtx_insn ** ret,rtx_insn ** use)2617 bb_is_just_return (basic_block bb, rtx_insn **ret, rtx_insn **use)
2618 {
2619 *ret = *use = NULL;
2620 rtx_insn *insn;
2621
2622 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2623 return false;
2624
2625 FOR_BB_INSNS (bb, insn)
2626 if (NONDEBUG_INSN_P (insn))
2627 {
2628 rtx pat = PATTERN (insn);
2629
2630 if (!*ret && ANY_RETURN_P (pat))
2631 *ret = insn;
2632 else if (!*ret && !*use && GET_CODE (pat) == USE
2633 && REG_P (XEXP (pat, 0))
2634 && REG_FUNCTION_VALUE_P (XEXP (pat, 0)))
2635 *use = insn;
2636 else if (GET_CODE (pat) != CLOBBER)
2637 return false;
2638 }
2639
2640 return !!*ret;
2641 }
2642
2643 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2644 instructions etc. Return nonzero if changes were made. */
2645
2646 static bool
try_optimize_cfg(int mode)2647 try_optimize_cfg (int mode)
2648 {
2649 bool changed_overall = false;
2650 bool changed;
2651 int iterations = 0;
2652 basic_block bb, b, next;
2653
2654 if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
2655 clear_bb_flags ();
2656
2657 crossjumps_occurred = false;
2658
2659 FOR_EACH_BB_FN (bb, cfun)
2660 update_forwarder_flag (bb);
2661
2662 if (! targetm.cannot_modify_jumps_p ())
2663 {
2664 first_pass = true;
2665 /* Attempt to merge blocks as made possible by edge removal. If
2666 a block has only one successor, and the successor has only
2667 one predecessor, they may be combined. */
2668 do
2669 {
2670 block_was_dirty = false;
2671 changed = false;
2672 iterations++;
2673
2674 if (dump_file)
2675 fprintf (dump_file,
2676 "\n\ntry_optimize_cfg iteration %i\n\n",
2677 iterations);
2678
2679 for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
2680 != EXIT_BLOCK_PTR_FOR_FN (cfun);)
2681 {
2682 basic_block c;
2683 edge s;
2684 bool changed_here = false;
2685
2686 /* Delete trivially dead basic blocks. This is either
2687 blocks with no predecessors, or empty blocks with no
2688 successors. However if the empty block with no
2689 successors is the successor of the ENTRY_BLOCK, it is
2690 kept. This ensures that the ENTRY_BLOCK will have a
2691 successor which is a precondition for many RTL
2692 passes. Empty blocks may result from expanding
2693 __builtin_unreachable (). */
2694 if (EDGE_COUNT (b->preds) == 0
2695 || (EDGE_COUNT (b->succs) == 0
2696 && trivially_empty_bb_p (b)
2697 && single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest
2698 != b))
2699 {
2700 c = b->prev_bb;
2701 if (EDGE_COUNT (b->preds) > 0)
2702 {
2703 edge e;
2704 edge_iterator ei;
2705
2706 if (current_ir_type () == IR_RTL_CFGLAYOUT)
2707 {
2708 if (BB_FOOTER (b)
2709 && BARRIER_P (BB_FOOTER (b)))
2710 FOR_EACH_EDGE (e, ei, b->preds)
2711 if ((e->flags & EDGE_FALLTHRU)
2712 && BB_FOOTER (e->src) == NULL)
2713 {
2714 if (BB_FOOTER (b))
2715 {
2716 BB_FOOTER (e->src) = BB_FOOTER (b);
2717 BB_FOOTER (b) = NULL;
2718 }
2719 else
2720 {
2721 start_sequence ();
2722 BB_FOOTER (e->src) = emit_barrier ();
2723 end_sequence ();
2724 }
2725 }
2726 }
2727 else
2728 {
2729 rtx_insn *last = get_last_bb_insn (b);
2730 if (last && BARRIER_P (last))
2731 FOR_EACH_EDGE (e, ei, b->preds)
2732 if ((e->flags & EDGE_FALLTHRU))
2733 emit_barrier_after (BB_END (e->src));
2734 }
2735 }
2736 delete_basic_block (b);
2737 changed = true;
2738 /* Avoid trying to remove the exit block. */
2739 b = (c == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? c->next_bb : c);
2740 continue;
2741 }
2742
2743 /* Remove code labels no longer used. */
2744 if (single_pred_p (b)
2745 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2746 && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
2747 && LABEL_P (BB_HEAD (b))
2748 && !LABEL_PRESERVE_P (BB_HEAD (b))
2749 /* If the previous block ends with a branch to this
2750 block, we can't delete the label. Normally this
2751 is a condjump that is yet to be simplified, but
2752 if CASE_DROPS_THRU, this can be a tablejump with
2753 some element going to the same place as the
2754 default (fallthru). */
2755 && (single_pred (b) == ENTRY_BLOCK_PTR_FOR_FN (cfun)
2756 || !JUMP_P (BB_END (single_pred (b)))
2757 || ! label_is_jump_target_p (BB_HEAD (b),
2758 BB_END (single_pred (b)))))
2759 {
2760 delete_insn (BB_HEAD (b));
2761 if (dump_file)
2762 fprintf (dump_file, "Deleted label in block %i.\n",
2763 b->index);
2764 }
2765
2766 /* If we fall through an empty block, we can remove it. */
2767 if (!(mode & (CLEANUP_CFGLAYOUT | CLEANUP_NO_INSN_DEL))
2768 && single_pred_p (b)
2769 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2770 && !LABEL_P (BB_HEAD (b))
2771 && FORWARDER_BLOCK_P (b)
2772 /* Note that forwarder_block_p true ensures that
2773 there is a successor for this block. */
2774 && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
2775 && n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS + 1)
2776 {
2777 if (dump_file)
2778 fprintf (dump_file,
2779 "Deleting fallthru block %i.\n",
2780 b->index);
2781
2782 c = ((b->prev_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2783 ? b->next_bb : b->prev_bb);
2784 redirect_edge_succ_nodup (single_pred_edge (b),
2785 single_succ (b));
2786 delete_basic_block (b);
2787 changed = true;
2788 b = c;
2789 continue;
2790 }
2791
2792 /* Merge B with its single successor, if any. */
2793 if (single_succ_p (b)
2794 && (s = single_succ_edge (b))
2795 && !(s->flags & EDGE_COMPLEX)
2796 && (c = s->dest) != EXIT_BLOCK_PTR_FOR_FN (cfun)
2797 && single_pred_p (c)
2798 && b != c)
2799 {
2800 /* When not in cfg_layout mode use code aware of reordering
2801 INSN. This code possibly creates new basic blocks so it
2802 does not fit merge_blocks interface and is kept here in
2803 hope that it will become useless once more of compiler
2804 is transformed to use cfg_layout mode. */
2805
2806 if ((mode & CLEANUP_CFGLAYOUT)
2807 && can_merge_blocks_p (b, c))
2808 {
2809 merge_blocks (b, c);
2810 update_forwarder_flag (b);
2811 changed_here = true;
2812 }
2813 else if (!(mode & CLEANUP_CFGLAYOUT)
2814 /* If the jump insn has side effects,
2815 we can't kill the edge. */
2816 && (!JUMP_P (BB_END (b))
2817 || (reload_completed
2818 ? simplejump_p (BB_END (b))
2819 : (onlyjump_p (BB_END (b))
2820 && !tablejump_p (BB_END (b),
2821 NULL, NULL))))
2822 && (next = merge_blocks_move (s, b, c, mode)))
2823 {
2824 b = next;
2825 changed_here = true;
2826 }
2827 }
2828
2829 /* Try to change a branch to a return to just that return. */
2830 rtx_insn *ret, *use;
2831 if (single_succ_p (b)
2832 && onlyjump_p (BB_END (b))
2833 && bb_is_just_return (single_succ (b), &ret, &use))
2834 {
2835 if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2836 PATTERN (ret), 0))
2837 {
2838 if (use)
2839 emit_insn_before (copy_insn (PATTERN (use)),
2840 BB_END (b));
2841 if (dump_file)
2842 fprintf (dump_file, "Changed jump %d->%d to return.\n",
2843 b->index, single_succ (b)->index);
2844 redirect_edge_succ (single_succ_edge (b),
2845 EXIT_BLOCK_PTR_FOR_FN (cfun));
2846 single_succ_edge (b)->flags &= ~EDGE_CROSSING;
2847 changed_here = true;
2848 }
2849 }
2850
2851 /* Try to change a conditional branch to a return to the
2852 respective conditional return. */
2853 if (EDGE_COUNT (b->succs) == 2
2854 && any_condjump_p (BB_END (b))
2855 && bb_is_just_return (BRANCH_EDGE (b)->dest, &ret, &use))
2856 {
2857 if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2858 PATTERN (ret), 0))
2859 {
2860 if (use)
2861 emit_insn_before (copy_insn (PATTERN (use)),
2862 BB_END (b));
2863 if (dump_file)
2864 fprintf (dump_file, "Changed conditional jump %d->%d "
2865 "to conditional return.\n",
2866 b->index, BRANCH_EDGE (b)->dest->index);
2867 redirect_edge_succ (BRANCH_EDGE (b),
2868 EXIT_BLOCK_PTR_FOR_FN (cfun));
2869 BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
2870 changed_here = true;
2871 }
2872 }
2873
2874 /* Try to flip a conditional branch that falls through to
2875 a return so that it becomes a conditional return and a
2876 new jump to the original branch target. */
2877 if (EDGE_COUNT (b->succs) == 2
2878 && BRANCH_EDGE (b)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2879 && any_condjump_p (BB_END (b))
2880 && bb_is_just_return (FALLTHRU_EDGE (b)->dest, &ret, &use))
2881 {
2882 if (invert_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2883 JUMP_LABEL (BB_END (b)), 0))
2884 {
2885 basic_block new_ft = BRANCH_EDGE (b)->dest;
2886 if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2887 PATTERN (ret), 0))
2888 {
2889 if (use)
2890 emit_insn_before (copy_insn (PATTERN (use)),
2891 BB_END (b));
2892 if (dump_file)
2893 fprintf (dump_file, "Changed conditional jump "
2894 "%d->%d to conditional return, adding "
2895 "fall-through jump.\n",
2896 b->index, BRANCH_EDGE (b)->dest->index);
2897 redirect_edge_succ (BRANCH_EDGE (b),
2898 EXIT_BLOCK_PTR_FOR_FN (cfun));
2899 BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
2900 std::swap (BRANCH_EDGE (b)->probability,
2901 FALLTHRU_EDGE (b)->probability);
2902 update_br_prob_note (b);
2903 basic_block jb = force_nonfallthru (FALLTHRU_EDGE (b));
2904 notice_new_block (jb);
2905 if (!redirect_jump (as_a <rtx_jump_insn *> (BB_END (jb)),
2906 block_label (new_ft), 0))
2907 gcc_unreachable ();
2908 redirect_edge_succ (single_succ_edge (jb), new_ft);
2909 changed_here = true;
2910 }
2911 else
2912 {
2913 /* Invert the jump back to what it was. This should
2914 never fail. */
2915 if (!invert_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2916 JUMP_LABEL (BB_END (b)), 0))
2917 gcc_unreachable ();
2918 }
2919 }
2920 }
2921
2922 /* Simplify branch over branch. */
2923 if ((mode & CLEANUP_EXPENSIVE)
2924 && !(mode & CLEANUP_CFGLAYOUT)
2925 && try_simplify_condjump (b))
2926 changed_here = true;
2927
2928 /* If B has a single outgoing edge, but uses a
2929 non-trivial jump instruction without side-effects, we
2930 can either delete the jump entirely, or replace it
2931 with a simple unconditional jump. */
2932 if (single_succ_p (b)
2933 && single_succ (b) != EXIT_BLOCK_PTR_FOR_FN (cfun)
2934 && onlyjump_p (BB_END (b))
2935 && !CROSSING_JUMP_P (BB_END (b))
2936 && try_redirect_by_replacing_jump (single_succ_edge (b),
2937 single_succ (b),
2938 (mode & CLEANUP_CFGLAYOUT) != 0))
2939 {
2940 update_forwarder_flag (b);
2941 changed_here = true;
2942 }
2943
2944 /* Simplify branch to branch. */
2945 if (try_forward_edges (mode, b))
2946 {
2947 update_forwarder_flag (b);
2948 changed_here = true;
2949 }
2950
2951 /* Look for shared code between blocks. */
2952 if ((mode & CLEANUP_CROSSJUMP)
2953 && try_crossjump_bb (mode, b))
2954 changed_here = true;
2955
2956 if ((mode & CLEANUP_CROSSJUMP)
2957 /* This can lengthen register lifetimes. Do it only after
2958 reload. */
2959 && reload_completed
2960 && try_head_merge_bb (b))
2961 changed_here = true;
2962
2963 /* Don't get confused by the index shift caused by
2964 deleting blocks. */
2965 if (!changed_here)
2966 b = b->next_bb;
2967 else
2968 changed = true;
2969 }
2970
2971 if ((mode & CLEANUP_CROSSJUMP)
2972 && try_crossjump_bb (mode, EXIT_BLOCK_PTR_FOR_FN (cfun)))
2973 changed = true;
2974
2975 if (block_was_dirty)
2976 {
2977 /* This should only be set by head-merging. */
2978 gcc_assert (mode & CLEANUP_CROSSJUMP);
2979 df_analyze ();
2980 }
2981
2982 if (changed)
2983 {
2984 /* Edge forwarding in particular can cause hot blocks previously
2985 reached by both hot and cold blocks to become dominated only
2986 by cold blocks. This will cause the verification below to fail,
2987 and lead to now cold code in the hot section. This is not easy
2988 to detect and fix during edge forwarding, and in some cases
2989 is only visible after newly unreachable blocks are deleted,
2990 which will be done in fixup_partitions. */
2991 if ((mode & CLEANUP_NO_PARTITIONING) == 0)
2992 {
2993 fixup_partitions ();
2994 checking_verify_flow_info ();
2995 }
2996 }
2997
2998 changed_overall |= changed;
2999 first_pass = false;
3000 }
3001 while (changed);
3002 }
3003
3004 FOR_ALL_BB_FN (b, cfun)
3005 b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
3006
3007 return changed_overall;
3008 }
3009
3010 /* Delete all unreachable basic blocks. */
3011
3012 bool
delete_unreachable_blocks(void)3013 delete_unreachable_blocks (void)
3014 {
3015 bool changed = false;
3016 basic_block b, prev_bb;
3017
3018 find_unreachable_blocks ();
3019
3020 /* When we're in GIMPLE mode and there may be debug bind insns, we
3021 should delete blocks in reverse dominator order, so as to get a
3022 chance to substitute all released DEFs into debug bind stmts. If
3023 we don't have dominators information, walking blocks backward
3024 gets us a better chance of retaining most debug information than
3025 otherwise. */
3026 if (MAY_HAVE_DEBUG_BIND_INSNS && current_ir_type () == IR_GIMPLE
3027 && dom_info_available_p (CDI_DOMINATORS))
3028 {
3029 for (b = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
3030 b != ENTRY_BLOCK_PTR_FOR_FN (cfun); b = prev_bb)
3031 {
3032 prev_bb = b->prev_bb;
3033
3034 if (!(b->flags & BB_REACHABLE))
3035 {
3036 /* Speed up the removal of blocks that don't dominate
3037 others. Walking backwards, this should be the common
3038 case. */
3039 if (!first_dom_son (CDI_DOMINATORS, b))
3040 delete_basic_block (b);
3041 else
3042 {
3043 vec<basic_block> h
3044 = get_all_dominated_blocks (CDI_DOMINATORS, b);
3045
3046 while (h.length ())
3047 {
3048 b = h.pop ();
3049
3050 prev_bb = b->prev_bb;
3051
3052 gcc_assert (!(b->flags & BB_REACHABLE));
3053
3054 delete_basic_block (b);
3055 }
3056
3057 h.release ();
3058 }
3059
3060 changed = true;
3061 }
3062 }
3063 }
3064 else
3065 {
3066 for (b = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
3067 b != ENTRY_BLOCK_PTR_FOR_FN (cfun); b = prev_bb)
3068 {
3069 prev_bb = b->prev_bb;
3070
3071 if (!(b->flags & BB_REACHABLE))
3072 {
3073 delete_basic_block (b);
3074 changed = true;
3075 }
3076 }
3077 }
3078
3079 if (changed)
3080 tidy_fallthru_edges ();
3081 return changed;
3082 }
3083
3084 /* Delete any jump tables never referenced. We can't delete them at the
3085 time of removing tablejump insn as they are referenced by the preceding
3086 insns computing the destination, so we delay deleting and garbagecollect
3087 them once life information is computed. */
3088 void
delete_dead_jumptables(void)3089 delete_dead_jumptables (void)
3090 {
3091 basic_block bb;
3092
3093 /* A dead jump table does not belong to any basic block. Scan insns
3094 between two adjacent basic blocks. */
3095 FOR_EACH_BB_FN (bb, cfun)
3096 {
3097 rtx_insn *insn, *next;
3098
3099 for (insn = NEXT_INSN (BB_END (bb));
3100 insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
3101 insn = next)
3102 {
3103 next = NEXT_INSN (insn);
3104 if (LABEL_P (insn)
3105 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
3106 && JUMP_TABLE_DATA_P (next))
3107 {
3108 rtx_insn *label = insn, *jump = next;
3109
3110 if (dump_file)
3111 fprintf (dump_file, "Dead jumptable %i removed\n",
3112 INSN_UID (insn));
3113
3114 next = NEXT_INSN (next);
3115 delete_insn (jump);
3116 delete_insn (label);
3117 }
3118 }
3119 }
3120 }
3121
3122
3123 /* Tidy the CFG by deleting unreachable code and whatnot. */
3124
3125 bool
cleanup_cfg(int mode)3126 cleanup_cfg (int mode)
3127 {
3128 bool changed = false;
3129
3130 /* Set the cfglayout mode flag here. We could update all the callers
3131 but that is just inconvenient, especially given that we eventually
3132 want to have cfglayout mode as the default. */
3133 if (current_ir_type () == IR_RTL_CFGLAYOUT)
3134 mode |= CLEANUP_CFGLAYOUT;
3135
3136 timevar_push (TV_CLEANUP_CFG);
3137 if (delete_unreachable_blocks ())
3138 {
3139 changed = true;
3140 /* We've possibly created trivially dead code. Cleanup it right
3141 now to introduce more opportunities for try_optimize_cfg. */
3142 if (!(mode & (CLEANUP_NO_INSN_DEL))
3143 && !reload_completed)
3144 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3145 }
3146
3147 compact_blocks ();
3148
3149 /* To tail-merge blocks ending in the same noreturn function (e.g.
3150 a call to abort) we have to insert fake edges to exit. Do this
3151 here once. The fake edges do not interfere with any other CFG
3152 cleanups. */
3153 if (mode & CLEANUP_CROSSJUMP)
3154 add_noreturn_fake_exit_edges ();
3155
3156 if (!dbg_cnt (cfg_cleanup))
3157 return changed;
3158
3159 while (try_optimize_cfg (mode))
3160 {
3161 delete_unreachable_blocks (), changed = true;
3162 if (!(mode & CLEANUP_NO_INSN_DEL))
3163 {
3164 /* Try to remove some trivially dead insns when doing an expensive
3165 cleanup. But delete_trivially_dead_insns doesn't work after
3166 reload (it only handles pseudos) and run_fast_dce is too costly
3167 to run in every iteration.
3168
3169 For effective cross jumping, we really want to run a fast DCE to
3170 clean up any dead conditions, or they get in the way of performing
3171 useful tail merges.
3172
3173 Other transformations in cleanup_cfg are not so sensitive to dead
3174 code, so delete_trivially_dead_insns or even doing nothing at all
3175 is good enough. */
3176 if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
3177 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3178 break;
3179 if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occurred)
3180 run_fast_dce ();
3181 }
3182 else
3183 break;
3184 }
3185
3186 if (mode & CLEANUP_CROSSJUMP)
3187 remove_fake_exit_edges ();
3188
3189 /* Don't call delete_dead_jumptables in cfglayout mode, because
3190 that function assumes that jump tables are in the insns stream.
3191 But we also don't _have_ to delete dead jumptables in cfglayout
3192 mode because we shouldn't even be looking at things that are
3193 not in a basic block. Dead jumptables are cleaned up when
3194 going out of cfglayout mode. */
3195 if (!(mode & CLEANUP_CFGLAYOUT))
3196 delete_dead_jumptables ();
3197
3198 /* ??? We probably do this way too often. */
3199 if (current_loops
3200 && (changed
3201 || (mode & CLEANUP_CFG_CHANGED)))
3202 {
3203 timevar_push (TV_REPAIR_LOOPS);
3204 /* The above doesn't preserve dominance info if available. */
3205 gcc_assert (!dom_info_available_p (CDI_DOMINATORS));
3206 calculate_dominance_info (CDI_DOMINATORS);
3207 fix_loop_structure (NULL);
3208 free_dominance_info (CDI_DOMINATORS);
3209 timevar_pop (TV_REPAIR_LOOPS);
3210 }
3211
3212 timevar_pop (TV_CLEANUP_CFG);
3213
3214 return changed;
3215 }
3216
3217 namespace {
3218
3219 const pass_data pass_data_jump =
3220 {
3221 RTL_PASS, /* type */
3222 "jump", /* name */
3223 OPTGROUP_NONE, /* optinfo_flags */
3224 TV_JUMP, /* tv_id */
3225 0, /* properties_required */
3226 0, /* properties_provided */
3227 0, /* properties_destroyed */
3228 0, /* todo_flags_start */
3229 0, /* todo_flags_finish */
3230 };
3231
3232 class pass_jump : public rtl_opt_pass
3233 {
3234 public:
pass_jump(gcc::context * ctxt)3235 pass_jump (gcc::context *ctxt)
3236 : rtl_opt_pass (pass_data_jump, ctxt)
3237 {}
3238
3239 /* opt_pass methods: */
3240 virtual unsigned int execute (function *);
3241
3242 }; // class pass_jump
3243
3244 unsigned int
execute(function *)3245 pass_jump::execute (function *)
3246 {
3247 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3248 if (dump_file)
3249 dump_flow_info (dump_file, dump_flags);
3250 cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
3251 | (flag_thread_jumps ? CLEANUP_THREADING : 0));
3252 return 0;
3253 }
3254
3255 } // anon namespace
3256
3257 rtl_opt_pass *
make_pass_jump(gcc::context * ctxt)3258 make_pass_jump (gcc::context *ctxt)
3259 {
3260 return new pass_jump (ctxt);
3261 }
3262
3263 namespace {
3264
3265 const pass_data pass_data_jump2 =
3266 {
3267 RTL_PASS, /* type */
3268 "jump2", /* name */
3269 OPTGROUP_NONE, /* optinfo_flags */
3270 TV_JUMP, /* tv_id */
3271 0, /* properties_required */
3272 0, /* properties_provided */
3273 0, /* properties_destroyed */
3274 0, /* todo_flags_start */
3275 0, /* todo_flags_finish */
3276 };
3277
3278 class pass_jump2 : public rtl_opt_pass
3279 {
3280 public:
pass_jump2(gcc::context * ctxt)3281 pass_jump2 (gcc::context *ctxt)
3282 : rtl_opt_pass (pass_data_jump2, ctxt)
3283 {}
3284
3285 /* opt_pass methods: */
execute(function *)3286 virtual unsigned int execute (function *)
3287 {
3288 cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
3289 return 0;
3290 }
3291
3292 }; // class pass_jump2
3293
3294 } // anon namespace
3295
3296 rtl_opt_pass *
make_pass_jump2(gcc::context * ctxt)3297 make_pass_jump2 (gcc::context *ctxt)
3298 {
3299 return new pass_jump2 (ctxt);
3300 }
3301