]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/cfgrtl.c
Remove bogus blank line
[thirdparty/gcc.git] / gcc / cfgrtl.c
CommitLineData
ca6c03ca
JH
1/* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING. If not, write to the Free
19Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2002111-1307, USA. */
21
22/* This file contains low level functions to manipulate with CFG and analyze it
23 that are aware of RTL intermediate language.
24
25 Available functionality:
26 - CFG aware instruction chain manipulation
27 delete_insn, delete_insn_chain
28 - Basic block manipulation
29 create_basic_block, flow_delete_block, split_block, merge_blocks_nomove
30 - Infrastructure to determine quickly basic block for instruction.
31 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
32 - Edge redirection with updating and optimizing instruction chain
33 block_label, redirect_edge_and_branch,
34 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
35 - Edge splitting and commiting to edges
36 split_edge, insert_insn_on_edge, commit_edge_insertions
eaec9b3d 37 - Dumping and debugging
ca6c03ca
JH
38 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
39 - Consistency checking
40 verify_flow_info
41 - CFG updating after constant propagation
42 purge_dead_edges, purge_all_dead_edges
43 */
44\f
45#include "config.h"
46#include "system.h"
47#include "tree.h"
48#include "rtl.h"
49#include "hard-reg-set.h"
50#include "basic-block.h"
51#include "regs.h"
52#include "flags.h"
53#include "output.h"
54#include "function.h"
55#include "except.h"
56#include "toplev.h"
57#include "tm_p.h"
58#include "obstack.h"
59
60/* Stubs in case we haven't got a return insn. */
61#ifndef HAVE_return
62#define HAVE_return 0
63#define gen_return() NULL_RTX
64#endif
65
66/* The basic block structure for every insn, indexed by uid. */
67
68varray_type basic_block_for_insn;
69
70/* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
71/* ??? Should probably be using LABEL_NUSES instead. It would take a
72 bit of surgery to be able to use or co-opt the routines in jump. */
73
74rtx label_value_list;
75rtx tail_recursion_label_list;
76
77static int can_delete_note_p PARAMS ((rtx));
78static int can_delete_label_p PARAMS ((rtx));
79static void commit_one_edge_insertion PARAMS ((edge));
80static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
81static rtx last_loop_beg_note PARAMS ((rtx));
82static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
83static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
84\f
85/* Return true if NOTE is not one of the ones that must be kept paired,
86 so that we may simply delete them. */
87
88static int
89can_delete_note_p (note)
90 rtx note;
91{
92 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
93 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
94}
95
96/* True if a given label can be deleted. */
97
98static int
99can_delete_label_p (label)
100 rtx label;
101{
102 rtx x;
103
104 if (LABEL_PRESERVE_P (label))
105 return 0;
106
107 for (x = forced_labels; x; x = XEXP (x, 1))
108 if (label == XEXP (x, 0))
109 return 0;
110 for (x = label_value_list; x; x = XEXP (x, 1))
111 if (label == XEXP (x, 0))
112 return 0;
113 for (x = exception_handler_labels; x; x = XEXP (x, 1))
114 if (label == XEXP (x, 0))
115 return 0;
116
117 /* User declared labels must be preserved. */
118 if (LABEL_NAME (label) != 0)
119 return 0;
120
121 return 1;
122}
123
124/* Delete INSN by patching it out. Return the next insn. */
125
126rtx
127delete_insn (insn)
128 rtx insn;
129{
130 rtx next = NEXT_INSN (insn);
131 rtx note;
132 bool really_delete = true;
133
134 if (GET_CODE (insn) == CODE_LABEL)
135 {
136 /* Some labels can't be directly removed from the INSN chain, as they
137 might be references via variables, constant pool etc.
138 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
139 if (! can_delete_label_p (insn))
140 {
141 const char *name = LABEL_NAME (insn);
142
143 really_delete = false;
144 PUT_CODE (insn, NOTE);
145 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
146 NOTE_SOURCE_FILE (insn) = name;
147 }
148 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
149 }
150
151 if (really_delete)
152 {
153 remove_insn (insn);
154 INSN_DELETED_P (insn) = 1;
155 }
156
157 /* If deleting a jump, decrement the use count of the label. Deleting
158 the label itself should happen in the normal course of block merging. */
159 if (GET_CODE (insn) == JUMP_INSN
160 && JUMP_LABEL (insn)
161 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
162 LABEL_NUSES (JUMP_LABEL (insn))--;
163
164 /* Also if deleting an insn that references a label. */
165 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
166 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
167 LABEL_NUSES (XEXP (note, 0))--;
168
169 if (GET_CODE (insn) == JUMP_INSN
170 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
171 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
172 {
173 rtx pat = PATTERN (insn);
174 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
175 int len = XVECLEN (pat, diff_vec_p);
176 int i;
177
178 for (i = 0; i < len; i++)
179 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
180 }
181
182 return next;
183}
184
185/* Unlink a chain of insns between START and FINISH, leaving notes
186 that must be paired. */
187
188void
189delete_insn_chain (start, finish)
190 rtx start, finish;
191{
192 /* Unchain the insns one by one. It would be quicker to delete all
193 of these with a single unchaining, rather than one at a time, but
194 we need to keep the NOTE's. */
195
196 rtx next;
197
198 while (1)
199 {
200 next = NEXT_INSN (start);
201 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
202 ;
203 else
204 next = delete_insn (start);
205
206 if (start == finish)
207 break;
208 start = next;
209 }
210}
211\f
212/* Create a new basic block consisting of the instructions between
213 HEAD and END inclusive. This function is designed to allow fast
214 BB construction - reuses the note and basic block struct
215 in BB_NOTE, if any and do not grow BASIC_BLOCK chain and should
216 be used directly only by CFG construction code.
217 END can be NULL in to create new empty basic block before HEAD.
218 Both END and HEAD can be NULL to create basic block at the end of
219 INSN chain. */
220
221basic_block
222create_basic_block_structure (index, head, end, bb_note)
223 int index;
224 rtx head, end, bb_note;
225{
226 basic_block bb;
227
228 if (bb_note
229 && ! RTX_INTEGRATED_P (bb_note)
230 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
231 && bb->aux == NULL)
232 {
233 /* If we found an existing note, thread it back onto the chain. */
234
235 rtx after;
236
237 if (GET_CODE (head) == CODE_LABEL)
238 after = head;
239 else
240 {
241 after = PREV_INSN (head);
242 head = bb_note;
243 }
244
245 if (after != bb_note && NEXT_INSN (after) != bb_note)
246 reorder_insns (bb_note, bb_note, after);
247 }
248 else
249 {
250 /* Otherwise we must create a note and a basic block structure. */
251
252 bb = alloc_block ();
253
254 if (!head && !end)
255 {
256 head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK,
257 get_last_insn ());
258 }
259 else if (GET_CODE (head) == CODE_LABEL && end)
260 {
261 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
262 if (head == end)
263 end = bb_note;
264 }
265 else
266 {
267 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
268 head = bb_note;
269 if (!end)
270 end = head;
271 }
272 NOTE_BASIC_BLOCK (bb_note) = bb;
273 }
274
275 /* Always include the bb note in the block. */
276 if (NEXT_INSN (end) == bb_note)
277 end = bb_note;
278
279 bb->head = head;
280 bb->end = end;
281 bb->index = index;
282 BASIC_BLOCK (index) = bb;
283 if (basic_block_for_insn)
284 update_bb_for_insn (bb);
285
286 /* Tag the block so that we know it has been used when considering
287 other basic block notes. */
288 bb->aux = bb;
289
290 return bb;
291}
292
293/* Create new basic block consisting of instructions in between HEAD and
eaec9b3d 294 END and place it to the BB chain at position INDEX.
ca6c03ca
JH
295 END can be NULL in to create new empty basic block before HEAD.
296 Both END and HEAD can be NULL to create basic block at the end of
297 INSN chain. */
298
299basic_block
300create_basic_block (index, head, end)
301 int index;
302 rtx head, end;
303{
304 basic_block bb;
305 int i;
306
307 /* Place the new block just after the block being split. */
308 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
309
310 /* Some parts of the compiler expect blocks to be number in
311 sequential order so insert the new block immediately after the
312 block being split.. */
313 for (i = n_basic_blocks - 1; i > index; --i)
314 {
315 basic_block tmp = BASIC_BLOCK (i - 1);
316 BASIC_BLOCK (i) = tmp;
317 tmp->index = i;
318 }
319
320 bb = create_basic_block_structure (index, head, end, NULL);
321 bb->aux = NULL;
322 return bb;
323}
324\f
325/* Delete the insns in a (non-live) block. We physically delete every
326 non-deleted-note insn, and update the flow graph appropriately.
327
328 Return nonzero if we deleted an exception handler. */
329
330/* ??? Preserving all such notes strikes me as wrong. It would be nice
331 to post-process the stream to remove empty blocks, loops, ranges, etc. */
332
333int
334flow_delete_block (b)
335 basic_block b;
336{
337 int deleted_handler = 0;
338 rtx insn, end, tmp;
339
340 /* If the head of this block is a CODE_LABEL, then it might be the
341 label for an exception handler which can't be reached.
342
343 We need to remove the label from the exception_handler_label list
344 and remove the associated NOTE_INSN_EH_REGION_BEG and
345 NOTE_INSN_EH_REGION_END notes. */
346
347 insn = b->head;
348
349 never_reached_warning (insn);
350
351 if (GET_CODE (insn) == CODE_LABEL)
352 maybe_remove_eh_handler (insn);
353
354 /* Include any jump table following the basic block. */
355 end = b->end;
356 if (GET_CODE (end) == JUMP_INSN
357 && (tmp = JUMP_LABEL (end)) != NULL_RTX
358 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
359 && GET_CODE (tmp) == JUMP_INSN
360 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
361 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
362 end = tmp;
363
364 /* Include any barrier that may follow the basic block. */
365 tmp = next_nonnote_insn (end);
366 if (tmp && GET_CODE (tmp) == BARRIER)
367 end = tmp;
368
369 /* Selectively delete the entire chain. */
370 b->head = NULL;
371 delete_insn_chain (insn, end);
372
373 /* Remove the edges into and out of this block. Note that there may
374 indeed be edges in, if we are removing an unreachable loop. */
375 while (b->pred != NULL)
376 remove_edge (b->pred);
377 while (b->succ != NULL)
378 remove_edge (b->succ);
379
380 b->pred = NULL;
381 b->succ = NULL;
382
383 /* Remove the basic block from the array, and compact behind it. */
384 expunge_block (b);
385
386 return deleted_handler;
387}
388\f
389/* Records the basic block struct in BB_FOR_INSN, for every instruction
390 indexed by INSN_UID. MAX is the size of the array. */
391
392void
393compute_bb_for_insn (max)
394 int max;
395{
396 int i;
397
398 if (basic_block_for_insn)
399 VARRAY_FREE (basic_block_for_insn);
400 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
401
402 for (i = 0; i < n_basic_blocks; ++i)
403 {
404 basic_block bb = BASIC_BLOCK (i);
405 rtx insn, end;
406
407 end = bb->end;
408 insn = bb->head;
409 while (1)
410 {
411 int uid = INSN_UID (insn);
412 if (uid < max)
413 VARRAY_BB (basic_block_for_insn, uid) = bb;
414 if (insn == end)
415 break;
416 insn = NEXT_INSN (insn);
417 }
418 }
419}
420
421/* Release the basic_block_for_insn array. */
422
423void
424free_bb_for_insn ()
425{
426 if (basic_block_for_insn)
427 VARRAY_FREE (basic_block_for_insn);
428 basic_block_for_insn = 0;
429}
430
431/* Update insns block within BB. */
432
433void
434update_bb_for_insn (bb)
435 basic_block bb;
436{
437 rtx insn;
438
439 if (! basic_block_for_insn)
440 return;
441
442 for (insn = bb->head; ; insn = NEXT_INSN (insn))
443 {
444 set_block_for_insn (insn, bb);
445
446 if (insn == bb->end)
447 break;
448 }
449}
450
451/* Record INSN's block as BB. */
452
453void
454set_block_for_insn (insn, bb)
455 rtx insn;
456 basic_block bb;
457{
458 size_t uid = INSN_UID (insn);
459 if (uid >= basic_block_for_insn->num_elements)
460 {
461 int new_size;
462
463 /* Add one-eighth the size so we don't keep calling xrealloc. */
464 new_size = uid + (uid + 7) / 8;
465
466 VARRAY_GROW (basic_block_for_insn, new_size);
467 }
468 VARRAY_BB (basic_block_for_insn, uid) = bb;
469}
470\f
471/* Split a block BB after insn INSN creating a new fallthru edge.
472 Return the new edge. Note that to keep other parts of the compiler happy,
473 this function renumbers all the basic blocks so that the new
474 one has a number one greater than the block split. */
475
476edge
477split_block (bb, insn)
478 basic_block bb;
479 rtx insn;
480{
481 basic_block new_bb;
482 edge new_edge;
483 edge e;
484
485 /* There is no point splitting the block after its end. */
486 if (bb->end == insn)
487 return 0;
488
489 /* Create the new basic block. */
490 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
491 new_bb->count = bb->count;
492 new_bb->frequency = bb->frequency;
493 new_bb->loop_depth = bb->loop_depth;
494 bb->end = insn;
495
496 /* Redirect the outgoing edges. */
497 new_bb->succ = bb->succ;
498 bb->succ = NULL;
499 for (e = new_bb->succ; e; e = e->succ_next)
500 e->src = new_bb;
501
502 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
503
504 if (bb->global_live_at_start)
505 {
506 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
507 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
508 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
509
510 /* We now have to calculate which registers are live at the end
511 of the split basic block and at the start of the new basic
512 block. Start with those registers that are known to be live
513 at the end of the original basic block and get
514 propagate_block to determine which registers are live. */
515 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
516 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
517 COPY_REG_SET (bb->global_live_at_end,
518 new_bb->global_live_at_start);
519 }
520
521 return new_edge;
522}
523
524/* Blocks A and B are to be merged into a single block A. The insns
525 are already contiguous, hence `nomove'. */
526
527void
528merge_blocks_nomove (a, b)
529 basic_block a, b;
530{
531 edge e;
532 rtx b_head, b_end, a_end;
533 rtx del_first = NULL_RTX, del_last = NULL_RTX;
534 int b_empty = 0;
535
536 /* If there was a CODE_LABEL beginning B, delete it. */
537 b_head = b->head;
538 b_end = b->end;
539 if (GET_CODE (b_head) == CODE_LABEL)
540 {
541 /* Detect basic blocks with nothing but a label. This can happen
542 in particular at the end of a function. */
543 if (b_head == b_end)
544 b_empty = 1;
545 del_first = del_last = b_head;
546 b_head = NEXT_INSN (b_head);
547 }
548
549 /* Delete the basic block note. */
550 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
551 {
552 if (b_head == b_end)
553 b_empty = 1;
554 if (! del_last)
555 del_first = b_head;
556 del_last = b_head;
557 b_head = NEXT_INSN (b_head);
558 }
559
560 /* If there was a jump out of A, delete it. */
561 a_end = a->end;
562 if (GET_CODE (a_end) == JUMP_INSN)
563 {
564 rtx prev;
565
566 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
567 if (GET_CODE (prev) != NOTE
568 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
569 || prev == a->head)
570 break;
571
572 del_first = a_end;
573
574#ifdef HAVE_cc0
575 /* If this was a conditional jump, we need to also delete
576 the insn that set cc0. */
577 if (only_sets_cc0_p (prev))
578 {
579 rtx tmp = prev;
580 prev = prev_nonnote_insn (prev);
581 if (!prev)
582 prev = a->head;
583 del_first = tmp;
584 }
585#endif
586
587 a_end = PREV_INSN (del_first);
588 }
589 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
590 del_first = NEXT_INSN (a_end);
591
592 /* Normally there should only be one successor of A and that is B, but
593 partway though the merge of blocks for conditional_execution we'll
594 be merging a TEST block with THEN and ELSE successors. Free the
595 whole lot of them and hope the caller knows what they're doing. */
596 while (a->succ)
597 remove_edge (a->succ);
598
599 /* Adjust the edges out of B for the new owner. */
600 for (e = b->succ; e; e = e->succ_next)
601 e->src = a;
602 a->succ = b->succ;
603
604 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
605 b->pred = b->succ = NULL;
7dddfb65 606 a->global_live_at_end = b->global_live_at_end;
ca6c03ca
JH
607
608 expunge_block (b);
609
610 /* Delete everything marked above as well as crap that might be
611 hanging out between the two blocks. */
612 delete_insn_chain (del_first, del_last);
613
614 /* Reassociate the insns of B with A. */
615 if (!b_empty)
616 {
617 rtx x = a_end;
618 if (basic_block_for_insn)
619 {
620 BLOCK_FOR_INSN (x) = a;
621 while (x != b_end)
622 {
623 x = NEXT_INSN (x);
624 BLOCK_FOR_INSN (x) = a;
625 }
626 }
627 a_end = b_end;
628 }
629 a->end = a_end;
630}
631\f
632/* Return label in the head of basic block. Create one if it doesn't exist. */
633
634rtx
635block_label (block)
636 basic_block block;
637{
638 if (block == EXIT_BLOCK_PTR)
639 return NULL_RTX;
640 if (GET_CODE (block->head) != CODE_LABEL)
641 {
642 block->head = emit_label_before (gen_label_rtx (), block->head);
643 if (basic_block_for_insn)
644 set_block_for_insn (block->head, block);
645 }
646 return block->head;
647}
648
649/* Attempt to perform edge redirection by replacing possibly complex jump
650 instruction by unconditional jump or removing jump completely.
651 This can apply only if all edges now point to the same block.
652
653 The parameters and return values are equivalent to redirect_edge_and_branch.
654 */
655
656static bool
657try_redirect_by_replacing_jump (e, target)
658 edge e;
659 basic_block target;
660{
661 basic_block src = e->src;
662 rtx insn = src->end, kill_from;
663 edge tmp;
664 rtx set;
665 int fallthru = 0;
666
667 /* Verify that all targets will be TARGET. */
668 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
669 if (tmp->dest != target && tmp != e)
670 break;
671 if (tmp || !onlyjump_p (insn))
672 return false;
673
674 /* Avoid removing branch with side effects. */
675 set = single_set (insn);
676 if (!set || side_effects_p (set))
677 return false;
678
679 /* In case we zap a conditional jump, we'll need to kill
680 the cc0 setter too. */
681 kill_from = insn;
682#ifdef HAVE_cc0
683 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
684 kill_from = PREV_INSN (insn);
685#endif
686
687 /* See if we can create the fallthru edge. */
688 if (can_fallthru (src, target))
689 {
690 if (rtl_dump_file)
691 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
692 fallthru = 1;
693
eaec9b3d 694 /* Selectively unlink whole insn chain. */
ca6c03ca
JH
695 delete_insn_chain (kill_from, PREV_INSN (target->head));
696 }
697 /* If this already is simplejump, redirect it. */
698 else if (simplejump_p (insn))
699 {
700 if (e->dest == target)
701 return false;
702 if (rtl_dump_file)
703 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
704 INSN_UID (insn), e->dest->index, target->index);
705 redirect_jump (insn, block_label (target), 0);
706 }
707 /* Or replace possibly complicated jump insn by simple jump insn. */
708 else
709 {
710 rtx target_label = block_label (target);
711 rtx barrier;
712
09eb1aab 713 emit_jump_insn_after (gen_jump (target_label), insn);
ca6c03ca
JH
714 JUMP_LABEL (src->end) = target_label;
715 LABEL_NUSES (target_label)++;
716 if (rtl_dump_file)
717 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
718 INSN_UID (insn), INSN_UID (src->end));
719
720 delete_insn_chain (kill_from, insn);
721
722 barrier = next_nonnote_insn (src->end);
723 if (!barrier || GET_CODE (barrier) != BARRIER)
724 emit_barrier_after (src->end);
725 }
726
727 /* Keep only one edge out and set proper flags. */
728 while (src->succ->succ_next)
729 remove_edge (src->succ);
730 e = src->succ;
731 if (fallthru)
732 e->flags = EDGE_FALLTHRU;
733 else
734 e->flags = 0;
735 e->probability = REG_BR_PROB_BASE;
736 e->count = src->count;
737
738 /* We don't want a block to end on a line-number note since that has
739 the potential of changing the code between -g and not -g. */
740 while (GET_CODE (e->src->end) == NOTE
741 && NOTE_LINE_NUMBER (e->src->end) >= 0)
742 delete_insn (e->src->end);
743
744 if (e->dest != target)
745 redirect_edge_succ (e, target);
746 return true;
747}
748
749/* Return last loop_beg note appearing after INSN, before start of next
750 basic block. Return INSN if there are no such notes.
751
eaec9b3d 752 When emitting jump to redirect an fallthru edge, it should always
ca6c03ca 753 appear after the LOOP_BEG notes, as loop optimizer expect loop to
eaec9b3d 754 either start by fallthru edge or jump following the LOOP_BEG note
ca6c03ca
JH
755 jumping to the loop exit test. */
756
757static rtx
758last_loop_beg_note (insn)
759 rtx insn;
760{
761 rtx last = insn;
762 insn = NEXT_INSN (insn);
763 while (insn && GET_CODE (insn) == NOTE
764 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
765 {
766 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
767 last = insn;
768 insn = NEXT_INSN (insn);
769 }
770 return last;
771}
772
773/* Attempt to change code to redirect edge E to TARGET.
774 Don't do that on expense of adding new instructions or reordering
775 basic blocks.
776
eaec9b3d 777 Function can be also called with edge destination equivalent to the
ca6c03ca
JH
778 TARGET. Then it should try the simplifications and do nothing if
779 none is possible.
780
eaec9b3d 781 Return true if transformation succeeded. We still return false in case
ca6c03ca
JH
782 E already destinated TARGET and we didn't managed to simplify instruction
783 stream. */
784
785bool
786redirect_edge_and_branch (e, target)
787 edge e;
788 basic_block target;
789{
790 rtx tmp;
791 rtx old_label = e->dest->head;
792 basic_block src = e->src;
793 rtx insn = src->end;
794
25b44be5 795 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
ca6c03ca
JH
796 return false;
797
798 if (try_redirect_by_replacing_jump (e, target))
799 return true;
800 /* Do this fast path late, as we want above code to simplify for cases
801 where called on single edge leaving basic block containing nontrivial
802 jump insn. */
803 else if (e->dest == target)
804 return false;
805
806 /* We can only redirect non-fallthru edges of jump insn. */
807 if (e->flags & EDGE_FALLTHRU)
808 return false;
809 if (GET_CODE (insn) != JUMP_INSN)
810 return false;
811
812 /* Recognize a tablejump and adjust all matching cases. */
813 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
814 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
815 && GET_CODE (tmp) == JUMP_INSN
816 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
817 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
818 {
819 rtvec vec;
820 int j;
821 rtx new_label = block_label (target);
822
823 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
824 vec = XVEC (PATTERN (tmp), 0);
825 else
826 vec = XVEC (PATTERN (tmp), 1);
827
828 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
829 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
830 {
831 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
832 --LABEL_NUSES (old_label);
833 ++LABEL_NUSES (new_label);
834 }
835
836 /* Handle casesi dispatch insns */
837 if ((tmp = single_set (insn)) != NULL
838 && SET_DEST (tmp) == pc_rtx
839 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
840 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
841 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
842 {
843 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
844 new_label);
845 --LABEL_NUSES (old_label);
846 ++LABEL_NUSES (new_label);
847 }
848 }
849 else
850 {
851 /* ?? We may play the games with moving the named labels from
852 one basic block to the other in case only one computed_jump is
853 available. */
854 if (computed_jump_p (insn))
855 return false;
856
857 /* A return instruction can't be redirected. */
858 if (returnjump_p (insn))
859 return false;
860
861 /* If the insn doesn't go where we think, we're confused. */
862 if (JUMP_LABEL (insn) != old_label)
863 abort ();
a3623c48
RH
864 /* If the substitution doesn't succeed, die. This can happen
865 if the back end emitted unrecognizable instructions. */
866 if (! redirect_jump (insn, block_label (target), 0))
867 abort ();
ca6c03ca
JH
868 }
869
870 if (rtl_dump_file)
871 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
872 e->src->index, e->dest->index, target->index);
873 if (e->dest != target)
874 redirect_edge_succ_nodup (e, target);
875 return true;
876}
877
4fe9b91c 878/* Like force_nonfallthru below, but additionally performs redirection
ca6c03ca
JH
879 Used by redirect_edge_and_branch_force. */
880
881static basic_block
882force_nonfallthru_and_redirect (e, target)
883 edge e;
884 basic_block target;
885{
886 basic_block jump_block, new_bb = NULL;
887 rtx note;
888 edge new_edge;
889
890 if (e->flags & EDGE_ABNORMAL)
891 abort ();
892 if (!(e->flags & EDGE_FALLTHRU))
893 abort ();
894 if (e->src->succ->succ_next)
895 {
896 /* Create the new structures. */
897 note = last_loop_beg_note (e->src->end);
898 jump_block = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
899 jump_block->count = e->count;
900 jump_block->frequency = EDGE_FREQUENCY (e);
901 jump_block->loop_depth = target->loop_depth;
902
903 if (target->global_live_at_start)
904 {
905 jump_block->global_live_at_start =
906 OBSTACK_ALLOC_REG_SET (&flow_obstack);
907 jump_block->global_live_at_end =
908 OBSTACK_ALLOC_REG_SET (&flow_obstack);
909 COPY_REG_SET (jump_block->global_live_at_start,
910 target->global_live_at_start);
911 COPY_REG_SET (jump_block->global_live_at_end,
912 target->global_live_at_start);
913 }
914
915 /* Wire edge in. */
916 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
917 new_edge->probability = e->probability;
918 new_edge->count = e->count;
919
920 /* Redirect old edge. */
921 redirect_edge_pred (e, jump_block);
922 e->probability = REG_BR_PROB_BASE;
923
924 new_bb = jump_block;
925 }
926 else
927 jump_block = e->src;
928 e->flags &= ~EDGE_FALLTHRU;
929 if (target == EXIT_BLOCK_PTR)
930 {
931 if (HAVE_return)
932 emit_jump_insn_after (gen_return (), jump_block->end);
933 else
934 abort ();
935 }
936 else
937 {
938 rtx label = block_label (target);
939 emit_jump_insn_after (gen_jump (label), jump_block->end);
940 JUMP_LABEL (jump_block->end) = label;
941 LABEL_NUSES (label)++;
942 }
943 emit_barrier_after (jump_block->end);
944 redirect_edge_succ_nodup (e, target);
945
946 return new_bb;
947}
948
949/* Edge E is assumed to be fallthru edge. Emit needed jump instruction
950 (and possibly create new basic block) to make edge non-fallthru.
951 Return newly created BB or NULL if none. */
952basic_block
953force_nonfallthru (e)
954 edge e;
955{
956 return force_nonfallthru_and_redirect (e, e->dest);
957}
958
959/* Redirect edge even at the expense of creating new jump insn or
960 basic block. Return new basic block if created, NULL otherwise.
eaec9b3d 961 Abort if conversion is impossible. */
ca6c03ca
JH
962
963basic_block
964redirect_edge_and_branch_force (e, target)
965 edge e;
966 basic_block target;
967{
968 basic_block new_bb;
969
970 if (redirect_edge_and_branch (e, target))
971 return NULL;
972 if (e->dest == target)
973 return NULL;
974
975 /* In case the edge redirection failed, try to force it to be non-fallthru
976 and redirect newly created simplejump. */
977 new_bb = force_nonfallthru_and_redirect (e, target);
978 return new_bb;
979}
980
981/* The given edge should potentially be a fallthru edge. If that is in
982 fact true, delete the jump and barriers that are in the way. */
983
984void
985tidy_fallthru_edge (e, b, c)
986 edge e;
987 basic_block b, c;
988{
989 rtx q;
990
991 /* ??? In a late-running flow pass, other folks may have deleted basic
992 blocks by nopping out blocks, leaving multiple BARRIERs between here
993 and the target label. They ought to be chastized and fixed.
994
995 We can also wind up with a sequence of undeletable labels between
996 one block and the next.
997
998 So search through a sequence of barriers, labels, and notes for
999 the head of block C and assert that we really do fall through. */
1000
1001 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1002 return;
1003
1004 /* Remove what will soon cease being the jump insn from the source block.
1005 If block B consisted only of this single jump, turn it into a deleted
1006 note. */
1007 q = b->end;
1008 if (GET_CODE (q) == JUMP_INSN
1009 && onlyjump_p (q)
1010 && (any_uncondjump_p (q)
1011 || (b->succ == e && e->succ_next == NULL)))
1012 {
1013#ifdef HAVE_cc0
1014 /* If this was a conditional jump, we need to also delete
1015 the insn that set cc0. */
1016 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1017 q = PREV_INSN (q);
1018#endif
1019
1020 q = PREV_INSN (q);
1021
1022 /* We don't want a block to end on a line-number note since that has
1023 the potential of changing the code between -g and not -g. */
1024 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1025 q = PREV_INSN (q);
1026 }
1027
1028 /* Selectively unlink the sequence. */
1029 if (q != PREV_INSN (c->head))
1030 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1031
1032 e->flags |= EDGE_FALLTHRU;
1033}
1034
1035/* Fix up edges that now fall through, or rather should now fall through
1036 but previously required a jump around now deleted blocks. Simplify
1037 the search by only examining blocks numerically adjacent, since this
1038 is how find_basic_blocks created them. */
1039
1040void
1041tidy_fallthru_edges ()
1042{
1043 int i;
1044
1045 for (i = 1; i < n_basic_blocks; ++i)
1046 {
1047 basic_block b = BASIC_BLOCK (i - 1);
1048 basic_block c = BASIC_BLOCK (i);
1049 edge s;
1050
1051 /* We care about simple conditional or unconditional jumps with
1052 a single successor.
1053
1054 If we had a conditional branch to the next instruction when
1055 find_basic_blocks was called, then there will only be one
1056 out edge for the block which ended with the conditional
1057 branch (since we do not create duplicate edges).
1058
1059 Furthermore, the edge will be marked as a fallthru because we
1060 merge the flags for the duplicate edges. So we do not want to
1061 check that the edge is not a FALLTHRU edge. */
1062 if ((s = b->succ) != NULL
1063 && ! (s->flags & EDGE_COMPLEX)
1064 && s->succ_next == NULL
1065 && s->dest == c
1066 /* If the jump insn has side effects, we can't tidy the edge. */
1067 && (GET_CODE (b->end) != JUMP_INSN
1068 || onlyjump_p (b->end)))
1069 tidy_fallthru_edge (s, b, c);
1070 }
1071}
1072\f
1073/* Helper function for split_edge. Return true in case edge BB2 to BB1
1074 is back edge of syntactic loop. */
1075
1076static bool
1077back_edge_of_syntactic_loop_p (bb1, bb2)
1078 basic_block bb1, bb2;
1079{
1080 rtx insn;
1081 int count = 0;
1082
1083 if (bb1->index > bb2->index)
1084 return false;
1085
1086 if (bb1->index == bb2->index)
1087 return true;
1088
1089 for (insn = bb1->end; insn != bb2->head && count >= 0;
1090 insn = NEXT_INSN (insn))
1091 if (GET_CODE (insn) == NOTE)
1092 {
1093 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1094 count++;
1095 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1096 count--;
1097 }
1098
1099 return count >= 0;
1100}
1101
1102/* Split a (typically critical) edge. Return the new block.
1103 Abort on abnormal edges.
1104
1105 ??? The code generally expects to be called on critical edges.
1106 The case of a block ending in an unconditional jump to a
1107 block with multiple predecessors is not handled optimally. */
1108
1109basic_block
1110split_edge (edge_in)
1111 edge edge_in;
1112{
1113 basic_block bb;
1114 edge edge_out;
1115 rtx before;
1116
1117 /* Abnormal edges cannot be split. */
1118 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1119 abort ();
1120
1121 /* We are going to place the new block in front of edge destination.
eaec9b3d 1122 Avoid existence of fallthru predecessors. */
ca6c03ca
JH
1123 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1124 {
1125 edge e;
1126 for (e = edge_in->dest->pred; e; e = e->pred_next)
1127 if (e->flags & EDGE_FALLTHRU)
1128 break;
1129
1130 if (e)
1131 force_nonfallthru (e);
1132 }
1133
1134 /* Create the basic block note.
1135
f63d1bf7 1136 Where we place the note can have a noticeable impact on the generated
ca6c03ca
JH
1137 code. Consider this cfg:
1138
1139 E
1140 |
1141 0
1142 / \
1143 +->1-->2--->E
1144 | |
1145 +--+
1146
1147 If we need to insert an insn on the edge from block 0 to block 1,
1148 we want to ensure the instructions we insert are outside of any
1149 loop notes that physically sit between block 0 and block 1. Otherwise
1150 we confuse the loop optimizer into thinking the loop is a phony. */
1151
1152 if (edge_in->dest != EXIT_BLOCK_PTR
1153 && PREV_INSN (edge_in->dest->head)
1154 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1155 && NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) == NOTE_INSN_LOOP_BEG
1156 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1157 before = PREV_INSN (edge_in->dest->head);
1158 else if (edge_in->dest != EXIT_BLOCK_PTR)
1159 before = edge_in->dest->head;
1160 else
1161 before = NULL_RTX;
1162
1163 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1164 : edge_in->dest->index, before, NULL);
1165 bb->count = edge_in->count;
1166 bb->frequency = EDGE_FREQUENCY (edge_in);
1167
1168 /* ??? This info is likely going to be out of date very soon. */
1169 if (edge_in->dest->global_live_at_start)
1170 {
1171 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1172 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1173 COPY_REG_SET (bb->global_live_at_start, edge_in->dest->global_live_at_start);
1174 COPY_REG_SET (bb->global_live_at_end, edge_in->dest->global_live_at_start);
1175 }
1176
1177 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1178
1179 /* For non-fallthry edges, we must adjust the predecessor's
1180 jump instruction to target our new block. */
1181 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1182 {
1183 if (!redirect_edge_and_branch (edge_in, bb))
1184 abort ();
1185 }
1186 else
1187 redirect_edge_succ (edge_in, bb);
1188
1189 return bb;
1190}
1191
1192/* Queue instructions for insertion on an edge between two basic blocks.
1193 The new instructions and basic blocks (if any) will not appear in the
1194 CFG until commit_edge_insertions is called. */
1195
1196void
1197insert_insn_on_edge (pattern, e)
1198 rtx pattern;
1199 edge e;
1200{
1201 /* We cannot insert instructions on an abnormal critical edge.
1202 It will be easier to find the culprit if we die now. */
1203 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1204 abort ();
1205
1206 if (e->insns == NULL_RTX)
1207 start_sequence ();
1208 else
1209 push_to_sequence (e->insns);
1210
1211 emit_insn (pattern);
1212
1213 e->insns = get_insns ();
1214 end_sequence ();
1215}
1216
1217/* Update the CFG for the instructions queued on edge E. */
1218
1219static void
1220commit_one_edge_insertion (e)
1221 edge e;
1222{
1223 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1224 basic_block bb;
1225
1226 /* Pull the insns off the edge now since the edge might go away. */
1227 insns = e->insns;
1228 e->insns = NULL_RTX;
1229
1230 /* Figure out where to put these things. If the destination has
1231 one predecessor, insert there. Except for the exit block. */
1232 if (e->dest->pred->pred_next == NULL
1233 && e->dest != EXIT_BLOCK_PTR)
1234 {
1235 bb = e->dest;
1236
1237 /* Get the location correct wrt a code label, and "nice" wrt
1238 a basic block note, and before everything else. */
1239 tmp = bb->head;
1240 if (GET_CODE (tmp) == CODE_LABEL)
1241 tmp = NEXT_INSN (tmp);
1242 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1243 tmp = NEXT_INSN (tmp);
1244 if (tmp == bb->head)
1245 before = tmp;
1246 else
1247 after = PREV_INSN (tmp);
1248 }
1249
1250 /* If the source has one successor and the edge is not abnormal,
1251 insert there. Except for the entry block. */
1252 else if ((e->flags & EDGE_ABNORMAL) == 0
1253 && e->src->succ->succ_next == NULL
1254 && e->src != ENTRY_BLOCK_PTR)
1255 {
1256 bb = e->src;
1257 /* It is possible to have a non-simple jump here. Consider a target
1258 where some forms of unconditional jumps clobber a register. This
1259 happens on the fr30 for example.
1260
1261 We know this block has a single successor, so we can just emit
1262 the queued insns before the jump. */
1263 if (GET_CODE (bb->end) == JUMP_INSN)
1264 {
1265 before = bb->end;
1266 while (GET_CODE (PREV_INSN (before)) == NOTE
1267 && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG)
1268 before = PREV_INSN (before);
1269 }
1270 else
1271 {
1272 /* We'd better be fallthru, or we've lost track of what's what. */
1273 if ((e->flags & EDGE_FALLTHRU) == 0)
1274 abort ();
1275
1276 after = bb->end;
1277 }
1278 }
1279
1280 /* Otherwise we must split the edge. */
1281 else
1282 {
1283 bb = split_edge (e);
1284 after = bb->end;
1285 }
1286
1287 /* Now that we've found the spot, do the insertion. */
1288
1289 if (before)
1290 {
1291 emit_insns_before (insns, before);
1292 last = prev_nonnote_insn (before);
1293 }
1294 else
1295 last = emit_insns_after (insns, after);
1296
1297 if (returnjump_p (last))
1298 {
1299 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1300 This is not currently a problem because this only happens
1301 for the (single) epilogue, which already has a fallthru edge
1302 to EXIT. */
1303
1304 e = bb->succ;
1305 if (e->dest != EXIT_BLOCK_PTR
1306 || e->succ_next != NULL
1307 || (e->flags & EDGE_FALLTHRU) == 0)
1308 abort ();
1309 e->flags &= ~EDGE_FALLTHRU;
1310
1311 emit_barrier_after (last);
1312
1313 if (before)
1314 delete_insn (before);
1315 }
1316 else if (GET_CODE (last) == JUMP_INSN)
1317 abort ();
1318 find_sub_basic_blocks (bb);
1319}
1320
1321/* Update the CFG for all queued instructions. */
1322
1323void
1324commit_edge_insertions ()
1325{
1326 int i;
1327 basic_block bb;
1328
1329#ifdef ENABLE_CHECKING
1330 verify_flow_info ();
1331#endif
1332
1333 i = -1;
1334 bb = ENTRY_BLOCK_PTR;
1335 while (1)
1336 {
1337 edge e, next;
1338
1339 for (e = bb->succ; e; e = next)
1340 {
1341 next = e->succ_next;
1342 if (e->insns)
1343 commit_one_edge_insertion (e);
1344 }
1345
1346 if (++i >= n_basic_blocks)
1347 break;
1348 bb = BASIC_BLOCK (i);
1349 }
1350}
1351\f
1352/* Print out one basic block with live information at start and end. */
1353
1354void
1355dump_bb (bb, outf)
1356 basic_block bb;
1357 FILE *outf;
1358{
1359 rtx insn;
1360 rtx last;
1361 edge e;
1362
1363 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1364 bb->index, bb->loop_depth);
1365 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1366 putc ('\n', outf);
1367
1368 fputs (";; Predecessors: ", outf);
1369 for (e = bb->pred; e; e = e->pred_next)
1370 dump_edge_info (outf, e, 0);
1371 putc ('\n', outf);
1372
1373 fputs (";; Registers live at start:", outf);
1374 dump_regset (bb->global_live_at_start, outf);
1375 putc ('\n', outf);
1376
1377 for (insn = bb->head, last = NEXT_INSN (bb->end);
1378 insn != last;
1379 insn = NEXT_INSN (insn))
1380 print_rtl_single (outf, insn);
1381
1382 fputs (";; Registers live at end:", outf);
1383 dump_regset (bb->global_live_at_end, outf);
1384 putc ('\n', outf);
1385
1386 fputs (";; Successors: ", outf);
1387 for (e = bb->succ; e; e = e->succ_next)
1388 dump_edge_info (outf, e, 1);
1389 putc ('\n', outf);
1390}
1391
1392void
1393debug_bb (bb)
1394 basic_block bb;
1395{
1396 dump_bb (bb, stderr);
1397}
1398
1399void
1400debug_bb_n (n)
1401 int n;
1402{
1403 dump_bb (BASIC_BLOCK (n), stderr);
1404}
1405\f
1406/* Like print_rtl, but also print out live information for the start of each
1407 basic block. */
1408
1409void
1410print_rtl_with_bb (outf, rtx_first)
1411 FILE *outf;
1412 rtx rtx_first;
1413{
b3694847 1414 rtx tmp_rtx;
ca6c03ca
JH
1415
1416 if (rtx_first == 0)
1417 fprintf (outf, "(nil)\n");
1418 else
1419 {
1420 int i;
1421 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1422 int max_uid = get_max_uid ();
1423 basic_block *start = (basic_block *)
1424 xcalloc (max_uid, sizeof (basic_block));
1425 basic_block *end = (basic_block *)
1426 xcalloc (max_uid, sizeof (basic_block));
1427 enum bb_state *in_bb_p = (enum bb_state *)
1428 xcalloc (max_uid, sizeof (enum bb_state));
1429
1430 for (i = n_basic_blocks - 1; i >= 0; i--)
1431 {
1432 basic_block bb = BASIC_BLOCK (i);
1433 rtx x;
1434
1435 start[INSN_UID (bb->head)] = bb;
1436 end[INSN_UID (bb->end)] = bb;
1437 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1438 {
1439 enum bb_state state = IN_MULTIPLE_BB;
1440 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1441 state = IN_ONE_BB;
1442 in_bb_p[INSN_UID (x)] = state;
1443
1444 if (x == bb->end)
1445 break;
1446 }
1447 }
1448
1449 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1450 {
1451 int did_output;
1452 basic_block bb;
1453
1454 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1455 {
1456 fprintf (outf, ";; Start of basic block %d, registers live:",
1457 bb->index);
1458 dump_regset (bb->global_live_at_start, outf);
1459 putc ('\n', outf);
1460 }
1461
1462 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1463 && GET_CODE (tmp_rtx) != NOTE
1464 && GET_CODE (tmp_rtx) != BARRIER)
1465 fprintf (outf, ";; Insn is not within a basic block\n");
1466 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1467 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1468
1469 did_output = print_rtl_single (outf, tmp_rtx);
1470
1471 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1472 {
1473 fprintf (outf, ";; End of basic block %d, registers live:\n",
1474 bb->index);
1475 dump_regset (bb->global_live_at_end, outf);
1476 putc ('\n', outf);
1477 }
1478
1479 if (did_output)
1480 putc ('\n', outf);
1481 }
1482
1483 free (start);
1484 free (end);
1485 free (in_bb_p);
1486 }
1487
1488 if (current_function_epilogue_delay_list != 0)
1489 {
1490 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1491 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1492 tmp_rtx = XEXP (tmp_rtx, 1))
1493 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1494 }
1495}
1496\f
1497/* Verify the CFG consistency. This function check some CFG invariants and
1498 aborts when something is wrong. Hope that this function will help to
1499 convert many optimization passes to preserve CFG consistent.
1500
1501 Currently it does following checks:
1502
1503 - test head/end pointers
1504 - overlapping of basic blocks
1505 - edge list correctness
1506 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
f63d1bf7 1507 - tails of basic blocks (ensure that boundary is necessary)
ca6c03ca
JH
1508 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1509 and NOTE_INSN_BASIC_BLOCK
1510 - check that all insns are in the basic blocks
1511 (except the switch handling code, barriers and notes)
1512 - check that all returns are followed by barriers
1513
1514 In future it can be extended check a lot of other stuff as well
1515 (reachability of basic blocks, life information, etc. etc.). */
1516
1517void
1518verify_flow_info ()
1519{
1520 const int max_uid = get_max_uid ();
1521 const rtx rtx_first = get_insns ();
1522 rtx last_head = get_last_insn ();
1523 basic_block *bb_info, *last_visited;
1524 size_t *edge_checksum;
1525 rtx x;
1526 int i, last_bb_num_seen, num_bb_notes, err = 0;
1527
1528 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1529 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
1530 sizeof (basic_block));
1531 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
1532
1533 for (i = n_basic_blocks - 1; i >= 0; i--)
1534 {
1535 basic_block bb = BASIC_BLOCK (i);
1536 rtx head = bb->head;
1537 rtx end = bb->end;
1538
1539 /* Verify the end of the basic block is in the INSN chain. */
1540 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1541 if (x == end)
1542 break;
1543 if (!x)
1544 {
1f978f5f 1545 error ("end insn %d for block %d not found in the insn stream",
ca6c03ca
JH
1546 INSN_UID (end), bb->index);
1547 err = 1;
1548 }
1549
1550 /* Work backwards from the end to the head of the basic block
1551 to verify the head is in the RTL chain. */
1552 for (; x != NULL_RTX; x = PREV_INSN (x))
1553 {
1554 /* While walking over the insn chain, verify insns appear
1555 in only one basic block and initialize the BB_INFO array
1556 used by other passes. */
1557 if (bb_info[INSN_UID (x)] != NULL)
1558 {
1f978f5f 1559 error ("insn %d is in multiple basic blocks (%d and %d)",
ca6c03ca
JH
1560 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1561 err = 1;
1562 }
1563 bb_info[INSN_UID (x)] = bb;
1564
1565 if (x == head)
1566 break;
1567 }
1568 if (!x)
1569 {
1f978f5f 1570 error ("head insn %d for block %d not found in the insn stream",
ca6c03ca
JH
1571 INSN_UID (head), bb->index);
1572 err = 1;
1573 }
1574
1575 last_head = x;
1576 }
1577
1578 /* Now check the basic blocks (boundaries etc.) */
1579 for (i = n_basic_blocks - 1; i >= 0; i--)
1580 {
1581 basic_block bb = BASIC_BLOCK (i);
1582 int has_fallthru = 0;
1583 edge e;
1584
1585 e = bb->succ;
1586 while (e)
1587 {
1588 if (last_visited [e->dest->index + 2] == bb)
1589 {
1590 error ("verify_flow_info: Duplicate edge %i->%i",
1591 e->src->index, e->dest->index);
1592 err = 1;
1593 }
1594 last_visited [e->dest->index + 2] = bb;
1595
1596 if (e->flags & EDGE_FALLTHRU)
1597 has_fallthru = 1;
1598
1599 if ((e->flags & EDGE_FALLTHRU)
1600 && e->src != ENTRY_BLOCK_PTR
1601 && e->dest != EXIT_BLOCK_PTR)
1602 {
1603 rtx insn;
1604 if (e->src->index + 1 != e->dest->index)
1605 {
1606 error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1607 e->src->index, e->dest->index);
1608 err = 1;
1609 }
1610 else
1611 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1612 insn = NEXT_INSN (insn))
32a6f30e
JDA
1613 if (GET_CODE (insn) == BARRIER
1614#ifndef CASE_DROPS_THROUGH
1615 || INSN_P (insn))
1616#else
1617 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn)))
1618#endif
ca6c03ca
JH
1619 {
1620 error ("verify_flow_info: Incorrect fallthru %i->%i",
1621 e->src->index, e->dest->index);
1f978f5f 1622 fatal_insn ("wrong insn in the fallthru edge", insn);
ca6c03ca
JH
1623 err = 1;
1624 }
1625 }
1626 if (e->src != bb)
1627 {
1628 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1629 bb->index);
1630 fprintf (stderr, "Predecessor: ");
1631 dump_edge_info (stderr, e, 0);
1632 fprintf (stderr, "\nSuccessor: ");
1633 dump_edge_info (stderr, e, 1);
1634 fprintf (stderr, "\n");
1635 err = 1;
1636 }
1637 edge_checksum[e->dest->index + 2] += (size_t) e;
1638 e = e->succ_next;
1639 }
1640 if (!has_fallthru)
1641 {
09eb1aab 1642 rtx insn;
ca6c03ca
JH
1643
1644 /* Ensure existence of barrier in BB with no fallthru edges. */
09eb1aab 1645 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
ca6c03ca
JH
1646 insn = NEXT_INSN (insn))
1647 if (!insn
1648 || (GET_CODE (insn) == NOTE
1649 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1650 {
1f978f5f 1651 error ("missing barrier after block %i", bb->index);
ca6c03ca 1652 err = 1;
09eb1aab 1653 break;
ca6c03ca
JH
1654 }
1655 }
1656
1657 e = bb->pred;
1658 while (e)
1659 {
1660 if (e->dest != bb)
1661 {
1f978f5f 1662 error ("basic block %d pred edge is corrupted", bb->index);
ca6c03ca
JH
1663 fputs ("Predecessor: ", stderr);
1664 dump_edge_info (stderr, e, 0);
1665 fputs ("\nSuccessor: ", stderr);
1666 dump_edge_info (stderr, e, 1);
1667 fputc ('\n', stderr);
1668 err = 1;
1669 }
1670 edge_checksum[e->dest->index + 2] -= (size_t) e;
1671 e = e->pred_next;
1672 }
1673 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1674 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1675 {
1676 debug_rtx (x);
1677 if (! BLOCK_FOR_INSN (x))
1f978f5f 1678 error ("insn %d is inside basic block %d but block_for_insn is NULL",
ca6c03ca
JH
1679 INSN_UID (x), bb->index);
1680 else
1f978f5f 1681 error ("insn %d is inside basic block %d but block_for_insn is %i",
ca6c03ca
JH
1682 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1683 err = 1;
1684 }
1685
1686 /* OK pointers are correct. Now check the header of basic
1687 block. It ought to contain optional CODE_LABEL followed
1688 by NOTE_BASIC_BLOCK. */
1689 x = bb->head;
1690 if (GET_CODE (x) == CODE_LABEL)
1691 {
1692 if (bb->end == x)
1693 {
1694 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1695 bb->index);
1696 err = 1;
1697 }
1698 x = NEXT_INSN (x);
1699 }
1700 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
1701 {
1702 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1703 bb->index);
1704 err = 1;
1705 }
1706
1707 if (bb->end == x)
1708 {
1709 /* Do checks for empty blocks here */
1710 }
1711 else
1712 {
1713 x = NEXT_INSN (x);
1714 while (x)
1715 {
1716 if (NOTE_INSN_BASIC_BLOCK_P (x))
1717 {
1718 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
1719 INSN_UID (x), bb->index);
1720 err = 1;
1721 }
1722
1723 if (x == bb->end)
1724 break;
1725
1726 if (GET_CODE (x) == JUMP_INSN
1727 || GET_CODE (x) == CODE_LABEL
1728 || GET_CODE (x) == BARRIER)
1729 {
1f978f5f
NB
1730 error ("in basic block %d:", bb->index);
1731 fatal_insn ("flow control insn inside a basic block", x);
ca6c03ca
JH
1732 }
1733
1734 x = NEXT_INSN (x);
1735 }
1736 }
1737 }
1738
1739 /* Complete edge checksumming for ENTRY and EXIT. */
1740 {
1741 edge e;
1742 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1743 edge_checksum[e->dest->index + 2] += (size_t) e;
1744 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
1745 edge_checksum[e->dest->index + 2] -= (size_t) e;
1746 }
1747
1748 for (i = -2; i < n_basic_blocks; ++i)
1749 if (edge_checksum[i + 2])
1750 {
1f978f5f 1751 error ("basic block %i edge lists are corrupted", i);
ca6c03ca
JH
1752 err = 1;
1753 }
1754
1755 last_bb_num_seen = -1;
1756 num_bb_notes = 0;
1757 x = rtx_first;
1758 while (x)
1759 {
1760 if (NOTE_INSN_BASIC_BLOCK_P (x))
1761 {
1762 basic_block bb = NOTE_BASIC_BLOCK (x);
1763 num_bb_notes++;
1764 if (bb->index != last_bb_num_seen + 1)
c725bd79 1765 internal_error ("basic blocks not numbered consecutively");
ca6c03ca
JH
1766
1767 last_bb_num_seen = bb->index;
1768 }
1769
1770 if (!bb_info[INSN_UID (x)])
1771 {
1772 switch (GET_CODE (x))
1773 {
1774 case BARRIER:
1775 case NOTE:
1776 break;
1777
1778 case CODE_LABEL:
1779 /* An addr_vec is placed outside any block block. */
1780 if (NEXT_INSN (x)
1781 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
1782 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
1783 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
1784 {
1785 x = NEXT_INSN (x);
1786 }
1787
1788 /* But in any case, non-deletable labels can appear anywhere. */
1789 break;
1790
1791 default:
1f978f5f 1792 fatal_insn ("insn outside basic block", x);
ca6c03ca
JH
1793 }
1794 }
1795
1796 if (INSN_P (x)
1797 && GET_CODE (x) == JUMP_INSN
1798 && returnjump_p (x) && ! condjump_p (x)
1799 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
1f978f5f 1800 fatal_insn ("return not followed by barrier", x);
ca6c03ca
JH
1801
1802 x = NEXT_INSN (x);
1803 }
1804
1805 if (num_bb_notes != n_basic_blocks)
1806 internal_error
1807 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1808 num_bb_notes, n_basic_blocks);
1809
1810 if (err)
c725bd79 1811 internal_error ("verify_flow_info failed");
ca6c03ca
JH
1812
1813 /* Clean up. */
1814 free (bb_info);
1815 free (last_visited);
1816 free (edge_checksum);
1817}
1818\f
eaec9b3d 1819/* Assume that the preceding pass has possibly eliminated jump instructions
ca6c03ca
JH
1820 or converted the unconditional jumps. Eliminate the edges from CFG.
1821 Return true if any edges are eliminated. */
1822
1823bool
1824purge_dead_edges (bb)
1825 basic_block bb;
1826{
1827 edge e, next;
89753b3a 1828 rtx insn = bb->end, note;
ca6c03ca
JH
1829 bool purged = false;
1830
1831 if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
1832 return false;
1833 if (GET_CODE (insn) == JUMP_INSN)
1834 {
1835 rtx note;
1836 edge b,f;
1837 /* We do care only about conditional jumps and simplejumps. */
1838 if (!any_condjump_p (insn)
1839 && !returnjump_p (insn)
1840 && !simplejump_p (insn))
1841 return false;
1842 for (e = bb->succ; e; e = next)
1843 {
1844 next = e->succ_next;
1845
7fcd7218
JH
1846 /* Avoid abnormal flags to leak from computed jumps turned
1847 into simplejumps. */
1848
0e1638d4 1849 e->flags &= ~EDGE_ABNORMAL;
7fcd7218 1850
ca6c03ca
JH
1851 /* Check purposes we can have edge. */
1852 if ((e->flags & EDGE_FALLTHRU)
1853 && any_condjump_p (insn))
1854 continue;
1855 if (e->dest != EXIT_BLOCK_PTR
1856 && e->dest->head == JUMP_LABEL (insn))
1857 continue;
1858 if (e->dest == EXIT_BLOCK_PTR
1859 && returnjump_p (insn))
1860 continue;
1861 purged = true;
1862 remove_edge (e);
1863 }
1864 if (!bb->succ || !purged)
1865 return false;
1866 if (rtl_dump_file)
1867 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
1868 if (!optimize)
1869 return purged;
1870
1871 /* Redistribute probabilities. */
1872 if (!bb->succ->succ_next)
1873 {
1874 bb->succ->probability = REG_BR_PROB_BASE;
1875 bb->succ->count = bb->count;
1876 }
1877 else
1878 {
1879 note = find_reg_note (insn, REG_BR_PROB, NULL);
1880 if (!note)
1881 return purged;
1882 b = BRANCH_EDGE (bb);
1883 f = FALLTHRU_EDGE (bb);
1884 b->probability = INTVAL (XEXP (note, 0));
1885 f->probability = REG_BR_PROB_BASE - b->probability;
1886 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
1887 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
1888 }
1889 return purged;
1890 }
1891
89753b3a
JJ
1892 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
1893 if (GET_CODE (insn) == INSN
1894 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
1895 {
1896 rtx eqnote;
1897 if (! may_trap_p (PATTERN (insn))
1898 || ((eqnote = find_reg_equal_equiv_note (insn))
1899 && ! may_trap_p (XEXP (eqnote, 0))))
1900 remove_note (insn, note);
1901 }
1902
ca6c03ca
JH
1903 /* Cleanup abnormal edges caused by throwing insns that have been
1904 eliminated. */
1905 if (! can_throw_internal (bb->end))
1906 for (e = bb->succ; e; e = next)
1907 {
1908 next = e->succ_next;
1909 if (e->flags & EDGE_EH)
1910 {
1911 remove_edge (e);
1912 purged = true;
1913 }
1914 }
1915
1916 /* If we don't see a jump insn, we don't know exactly why the block would
1917 have been broken at this point. Look for a simple, non-fallthru edge,
1918 as these are only created by conditional branches. If we find such an
1919 edge we know that there used to be a jump here and can then safely
1920 remove all non-fallthru edges. */
1921 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
1922 e = e->succ_next);
1923 if (!e)
1924 return purged;
1925 for (e = bb->succ; e; e = next)
1926 {
1927 next = e->succ_next;
1928 if (!(e->flags & EDGE_FALLTHRU))
1929 remove_edge (e), purged = true;
1930 }
1931 if (!bb->succ || bb->succ->succ_next)
1932 abort ();
1933 bb->succ->probability = REG_BR_PROB_BASE;
1934 bb->succ->count = bb->count;
1935
1936 if (rtl_dump_file)
1937 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
1938 bb->index);
1939 return purged;
1940}
1941
eaec9b3d 1942/* Search all basic blocks for potentially dead edges and purge them.
ca6c03ca 1943
f5143c46 1944 Return true iff some edge has been eliminated.
ca6c03ca
JH
1945 */
1946
1947bool
473fb060 1948purge_all_dead_edges (update_life_p)
00baba68 1949 int update_life_p;
ca6c03ca
JH
1950{
1951 int i, purged = false;
710af899 1952 sbitmap blocks = 0;
473fb060
JH
1953
1954 if (update_life_p)
1955 {
1956 blocks = sbitmap_alloc (n_basic_blocks);
1957 sbitmap_zero (blocks);
1958 }
ca6c03ca 1959 for (i = 0; i < n_basic_blocks; i++)
473fb060
JH
1960 {
1961 bool purged_here;
1962 purged_here = purge_dead_edges (BASIC_BLOCK (i));
1963 purged |= purged_here;
1964 if (purged_here && update_life_p)
1965 SET_BIT (blocks, i);
1966 }
1967 if (update_life_p && purged)
1968 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
1969 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
1970 | PROP_KILL_DEAD_CODE);
1971 if (update_life_p)
1972 sbitmap_free (blocks);
ca6c03ca
JH
1973 return purged;
1974}