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