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