1 /* Data flow analysis for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* This file contains the data flow analysis pass of the compiler. It
24 computes data flow information which tells combine_instructions
25 which insns to consider combining and controls register allocation.
27 Additional data flow information that is too bulky to record is
28 generated during the analysis, and is used at that time to create
29 autoincrement and autodecrement addressing.
31 The first step is dividing the function into basic blocks.
32 find_basic_blocks does this. Then life_analysis determines
33 where each register is live and where it is dead.
35 ** find_basic_blocks **
37 find_basic_blocks divides the current function's rtl into basic
38 blocks and constructs the CFG. The blocks are recorded in the
39 basic_block_info array; the CFG exists in the edge structures
40 referenced by the blocks.
42 find_basic_blocks also finds any unreachable loops and deletes them.
46 life_analysis is called immediately after find_basic_blocks.
47 It uses the basic block information to determine where each
48 hard or pseudo register is live.
50 ** live-register info **
52 The information about where each register is live is in two parts:
53 the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
55 basic_block->global_live_at_start has an element for each basic
56 block, and the element is a bit-vector with a bit for each hard or
57 pseudo register. The bit is 1 if the register is live at the
58 beginning of the basic block.
60 Two types of elements can be added to an insn's REG_NOTES.
61 A REG_DEAD note is added to an insn's REG_NOTES for any register
62 that meets both of two conditions: The value in the register is not
63 needed in subsequent insns and the insn does not replace the value in
64 the register (in the case of multi-word hard registers, the value in
65 each register must be replaced by the insn to avoid a REG_DEAD note).
67 In the vast majority of cases, an object in a REG_DEAD note will be
68 used somewhere in the insn. The (rare) exception to this is if an
69 insn uses a multi-word hard register and only some of the registers are
70 needed in subsequent insns. In that case, REG_DEAD notes will be
71 provided for those hard registers that are not subsequently needed.
72 Partial REG_DEAD notes of this type do not occur when an insn sets
73 only some of the hard registers used in such a multi-word operand;
74 omitting REG_DEAD notes for objects stored in an insn is optional and
75 the desire to do so does not justify the complexity of the partial
78 REG_UNUSED notes are added for each register that is set by the insn
79 but is unused subsequently (if every register set by the insn is unused
80 and the insn does not reference memory or have some other side-effect,
81 the insn is deleted instead). If only part of a multi-word hard
82 register is used in a subsequent insn, REG_UNUSED notes are made for
83 the parts that will not be used.
85 To determine which registers are live after any insn, one can
86 start from the beginning of the basic block and scan insns, noting
87 which registers are set by each insn and which die there.
89 ** Other actions of life_analysis **
91 life_analysis sets up the LOG_LINKS fields of insns because the
92 information needed to do so is readily available.
94 life_analysis deletes insns whose only effect is to store a value
97 life_analysis notices cases where a reference to a register as
98 a memory address can be combined with a preceding or following
99 incrementation or decrementation of the register. The separate
100 instruction to increment or decrement is deleted and the address
101 is changed to a POST_INC or similar rtx.
103 Each time an incrementing or decrementing address is created,
104 a REG_INC element is added to the insn's REG_NOTES list.
106 life_analysis fills in certain vectors containing information about
107 register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
108 REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
110 life_analysis sets current_function_sp_is_unchanging if the function
111 doesn't modify the stack pointer. */
115 Split out from life_analysis:
116 - local property discovery (bb->local_live, bb->local_set)
117 - global property computation
119 - pre/post modify transformation
127 #include "hard-reg-set.h"
128 #include "basic-block.h"
129 #include "insn-config.h"
133 #include "function.h"
137 #include "insn-flags.h"
141 #include "splay-tree.h"
143 #define obstack_chunk_alloc xmalloc
144 #define obstack_chunk_free free
147 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
148 the stack pointer does not matter. The value is tested only in
149 functions that have frame pointers.
150 No definition is equivalent to always zero. */
151 #ifndef EXIT_IGNORE_STACK
152 #define EXIT_IGNORE_STACK 0
155 #ifndef HAVE_epilogue
156 #define HAVE_epilogue 0
158 #ifndef HAVE_prologue
159 #define HAVE_prologue 0
161 #ifndef HAVE_sibcall_epilogue
162 #define HAVE_sibcall_epilogue 0
165 /* The contents of the current function definition are allocated
166 in this obstack, and all are freed at the end of the function.
167 For top-level functions, this is temporary_obstack.
168 Separate obstacks are made for nested functions. */
170 extern struct obstack *function_obstack;
172 /* Number of basic blocks in the current function. */
176 /* Number of edges in the current function. */
180 /* The basic block array. */
182 varray_type basic_block_info;
184 /* The special entry and exit blocks. */
186 struct basic_block_def entry_exit_blocks[2]
191 NULL, /* local_set */
192 NULL, /* global_live_at_start */
193 NULL, /* global_live_at_end */
195 ENTRY_BLOCK, /* index */
197 -1, -1, /* eh_beg, eh_end */
205 NULL, /* local_set */
206 NULL, /* global_live_at_start */
207 NULL, /* global_live_at_end */
209 EXIT_BLOCK, /* index */
211 -1, -1, /* eh_beg, eh_end */
216 /* Nonzero if the second flow pass has completed. */
219 /* Maximum register number used in this function, plus one. */
223 /* Indexed by n, giving various register information */
225 varray_type reg_n_info;
227 /* Size of a regset for the current function,
228 in (1) bytes and (2) elements. */
233 /* Regset of regs live when calls to `setjmp'-like functions happen. */
234 /* ??? Does this exist only for the setjmp-clobbered warning message? */
236 regset regs_live_at_setjmp;
238 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
239 that have to go in the same hard reg.
240 The first two regs in the list are a pair, and the next two
241 are another pair, etc. */
244 /* Set of registers that may be eliminable. These are handled specially
245 in updating regs_ever_live. */
247 static HARD_REG_SET elim_reg_set;
249 /* The basic block structure for every insn, indexed by uid. */
251 varray_type basic_block_for_insn;
253 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
254 /* ??? Should probably be using LABEL_NUSES instead. It would take a
255 bit of surgery to be able to use or co-opt the routines in jump. */
257 static rtx label_value_list;
258 static rtx tail_recursion_label_list;
260 /* Holds information for tracking conditional register life information. */
261 struct reg_cond_life_info
263 /* An EXPR_LIST of conditions under which a register is dead. */
266 /* ??? Could store mask of bytes that are dead, so that we could finally
267 track lifetimes of multi-word registers accessed via subregs. */
270 /* For use in communicating between propagate_block and its subroutines.
271 Holds all information needed to compute life and def-use information. */
273 struct propagate_block_info
275 /* The basic block we're considering. */
278 /* Bit N is set if register N is conditionally or unconditionally live. */
281 /* Bit N is set if register N is set this insn. */
284 /* Element N is the next insn that uses (hard or pseudo) register N
285 within the current basic block; or zero, if there is no such insn. */
288 /* Contains a list of all the MEMs we are tracking for dead store
292 /* If non-null, record the set of registers set in the basic block. */
295 #ifdef HAVE_conditional_execution
296 /* Indexed by register number, holds a reg_cond_life_info for each
297 register that is not unconditionally live or dead. */
298 splay_tree reg_cond_dead;
300 /* Bit N is set if register N is in an expression in reg_cond_dead. */
304 /* Non-zero if the value of CC0 is live. */
307 /* Flags controling the set of information propagate_block collects. */
311 /* Forward declarations */
312 static int count_basic_blocks PARAMS ((rtx));
313 static void find_basic_blocks_1 PARAMS ((rtx));
314 static rtx find_label_refs PARAMS ((rtx, rtx));
315 static void clear_edges PARAMS ((void));
316 static void make_edges PARAMS ((rtx));
317 static void make_label_edge PARAMS ((sbitmap *, basic_block,
319 static void make_eh_edge PARAMS ((sbitmap *, eh_nesting_info *,
320 basic_block, rtx, int));
321 static void mark_critical_edges PARAMS ((void));
322 static void move_stray_eh_region_notes PARAMS ((void));
323 static void record_active_eh_regions PARAMS ((rtx));
325 static void commit_one_edge_insertion PARAMS ((edge));
327 static void delete_unreachable_blocks PARAMS ((void));
328 static void delete_eh_regions PARAMS ((void));
329 static int can_delete_note_p PARAMS ((rtx));
330 static void expunge_block PARAMS ((basic_block));
331 static int can_delete_label_p PARAMS ((rtx));
332 static int tail_recursion_label_p PARAMS ((rtx));
333 static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
335 static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
337 static int merge_blocks PARAMS ((edge,basic_block,basic_block));
338 static void try_merge_blocks PARAMS ((void));
339 static void tidy_fallthru_edges PARAMS ((void));
340 static int verify_wide_reg_1 PARAMS ((rtx *, void *));
341 static void verify_wide_reg PARAMS ((int, rtx, rtx));
342 static void verify_local_live_at_start PARAMS ((regset, basic_block));
343 static int set_noop_p PARAMS ((rtx));
344 static int noop_move_p PARAMS ((rtx));
345 static void delete_noop_moves PARAMS ((rtx));
346 static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
347 static void notice_stack_pointer_modification PARAMS ((rtx));
348 static void mark_reg PARAMS ((rtx, void *));
349 static void mark_regs_live_at_end PARAMS ((regset));
350 static int set_phi_alternative_reg PARAMS ((rtx, int, int, void *));
351 static void calculate_global_regs_live PARAMS ((sbitmap, sbitmap, int));
352 static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
353 static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
354 static int insn_dead_p PARAMS ((struct propagate_block_info *,
356 static int libcall_dead_p PARAMS ((struct propagate_block_info *,
358 static void mark_set_regs PARAMS ((struct propagate_block_info *,
360 static void mark_set_1 PARAMS ((struct propagate_block_info *,
361 enum rtx_code, rtx, rtx,
363 #ifdef HAVE_conditional_execution
364 static int mark_regno_cond_dead PARAMS ((struct propagate_block_info *,
366 static void free_reg_cond_life_info PARAMS ((splay_tree_value));
367 static int flush_reg_cond_reg_1 PARAMS ((splay_tree_node, void *));
368 static void flush_reg_cond_reg PARAMS ((struct propagate_block_info *,
370 static rtx ior_reg_cond PARAMS ((rtx, rtx));
371 static rtx not_reg_cond PARAMS ((rtx));
372 static rtx nand_reg_cond PARAMS ((rtx, rtx));
375 static void attempt_auto_inc PARAMS ((struct propagate_block_info *,
376 rtx, rtx, rtx, rtx, rtx));
377 static void find_auto_inc PARAMS ((struct propagate_block_info *,
379 static int try_pre_increment_1 PARAMS ((struct propagate_block_info *,
381 static int try_pre_increment PARAMS ((rtx, rtx, HOST_WIDE_INT));
383 static void mark_used_reg PARAMS ((struct propagate_block_info *,
385 static void mark_used_regs PARAMS ((struct propagate_block_info *,
387 void dump_flow_info PARAMS ((FILE *));
388 void debug_flow_info PARAMS ((void));
389 static void dump_edge_info PARAMS ((FILE *, edge, int));
391 static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
393 static void remove_fake_successors PARAMS ((basic_block));
394 static void flow_nodes_print PARAMS ((const char *, const sbitmap, FILE *));
395 static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
396 static void flow_loops_cfg_dump PARAMS ((const struct loops *, FILE *));
397 static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *));
398 static int flow_loop_exits_find PARAMS ((const sbitmap, edge **));
399 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
400 static int flow_depth_first_order_compute PARAMS ((int *, int *));
401 static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
402 static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
403 static void flow_loops_tree_build PARAMS ((struct loops *));
404 static int flow_loop_level_compute PARAMS ((struct loop *, int));
405 static int flow_loops_level_compute PARAMS ((struct loops *));
407 /* Find basic blocks of the current function.
408 F is the first insn of the function and NREGS the number of register
412 find_basic_blocks (f, nregs, file)
414 int nregs ATTRIBUTE_UNUSED;
415 FILE *file ATTRIBUTE_UNUSED;
419 /* Flush out existing data. */
420 if (basic_block_info != NULL)
426 /* Clear bb->aux on all extant basic blocks. We'll use this as a
427 tag for reuse during create_basic_block, just in case some pass
428 copies around basic block notes improperly. */
429 for (i = 0; i < n_basic_blocks; ++i)
430 BASIC_BLOCK (i)->aux = NULL;
432 VARRAY_FREE (basic_block_info);
435 n_basic_blocks = count_basic_blocks (f);
437 /* Size the basic block table. The actual structures will be allocated
438 by find_basic_blocks_1, since we want to keep the structure pointers
439 stable across calls to find_basic_blocks. */
440 /* ??? This whole issue would be much simpler if we called find_basic_blocks
441 exactly once, and thereafter we don't have a single long chain of
442 instructions at all until close to the end of compilation when we
443 actually lay them out. */
445 VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
447 find_basic_blocks_1 (f);
449 /* Record the block to which an insn belongs. */
450 /* ??? This should be done another way, by which (perhaps) a label is
451 tagged directly with the basic block that it starts. It is used for
452 more than that currently, but IMO that is the only valid use. */
454 max_uid = get_max_uid ();
456 /* Leave space for insns life_analysis makes in some cases for auto-inc.
457 These cases are rare, so we don't need too much space. */
458 max_uid += max_uid / 10;
461 compute_bb_for_insn (max_uid);
463 /* Discover the edges of our cfg. */
464 record_active_eh_regions (f);
465 make_edges (label_value_list);
467 /* Do very simple cleanup now, for the benefit of code that runs between
468 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
469 tidy_fallthru_edges ();
471 mark_critical_edges ();
473 #ifdef ENABLE_CHECKING
478 /* Count the basic blocks of the function. */
481 count_basic_blocks (f)
485 register RTX_CODE prev_code;
486 register int count = 0;
488 int call_had_abnormal_edge = 0;
490 prev_code = JUMP_INSN;
491 for (insn = f; insn; insn = NEXT_INSN (insn))
493 register RTX_CODE code = GET_CODE (insn);
495 if (code == CODE_LABEL
496 || (GET_RTX_CLASS (code) == 'i'
497 && (prev_code == JUMP_INSN
498 || prev_code == BARRIER
499 || (prev_code == CALL_INSN && call_had_abnormal_edge))))
502 /* Record whether this call created an edge. */
503 if (code == CALL_INSN)
505 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
506 int region = (note ? INTVAL (XEXP (note, 0)) : 1);
508 call_had_abnormal_edge = 0;
510 /* If there is an EH region or rethrow, we have an edge. */
511 if ((eh_region && region > 0)
512 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
513 call_had_abnormal_edge = 1;
514 else if (nonlocal_goto_handler_labels && region >= 0)
515 /* If there is a nonlocal goto label and the specified
516 region number isn't -1, we have an edge. (0 means
517 no throw, but might have a nonlocal goto). */
518 call_had_abnormal_edge = 1;
523 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
525 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
529 /* The rest of the compiler works a bit smoother when we don't have to
530 check for the edge case of do-nothing functions with no basic blocks. */
533 emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
540 /* Scan a list of insns for labels referred to other than by jumps.
541 This is used to scan the alternatives of a call placeholder. */
543 find_label_refs (f, lvl)
549 for (insn = f; insn; insn = NEXT_INSN (insn))
550 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
554 /* Make a list of all labels referred to other than by jumps
555 (which just don't have the REG_LABEL notes).
557 Make a special exception for labels followed by an ADDR*VEC,
558 as this would be a part of the tablejump setup code.
560 Make a special exception for the eh_return_stub_label, which
561 we know isn't part of any otherwise visible control flow. */
563 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
564 if (REG_NOTE_KIND (note) == REG_LABEL)
566 rtx lab = XEXP (note, 0), next;
568 if (lab == eh_return_stub_label)
570 else if ((next = next_nonnote_insn (lab)) != NULL
571 && GET_CODE (next) == JUMP_INSN
572 && (GET_CODE (PATTERN (next)) == ADDR_VEC
573 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
575 else if (GET_CODE (lab) == NOTE)
578 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
585 /* Find all basic blocks of the function whose first insn is F.
587 Collect and return a list of labels whose addresses are taken. This
588 will be used in make_edges for use with computed gotos. */
591 find_basic_blocks_1 (f)
594 register rtx insn, next;
596 rtx bb_note = NULL_RTX;
597 rtx eh_list = NULL_RTX;
603 /* We process the instructions in a slightly different way than we did
604 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
605 closed out the previous block, so that it gets attached at the proper
606 place. Since this form should be equivalent to the previous,
607 count_basic_blocks continues to use the old form as a check. */
609 for (insn = f; insn; insn = next)
611 enum rtx_code code = GET_CODE (insn);
613 next = NEXT_INSN (insn);
619 int kind = NOTE_LINE_NUMBER (insn);
621 /* Keep a LIFO list of the currently active exception notes. */
622 if (kind == NOTE_INSN_EH_REGION_BEG)
623 eh_list = alloc_INSN_LIST (insn, eh_list);
624 else if (kind == NOTE_INSN_EH_REGION_END)
628 eh_list = XEXP (eh_list, 1);
629 free_INSN_LIST_node (t);
632 /* Look for basic block notes with which to keep the
633 basic_block_info pointers stable. Unthread the note now;
634 we'll put it back at the right place in create_basic_block.
635 Or not at all if we've already found a note in this block. */
636 else if (kind == NOTE_INSN_BASIC_BLOCK)
638 if (bb_note == NULL_RTX)
641 next = flow_delete_insn (insn);
647 /* A basic block starts at a label. If we've closed one off due
648 to a barrier or some such, no need to do it again. */
649 if (head != NULL_RTX)
651 /* While we now have edge lists with which other portions of
652 the compiler might determine a call ending a basic block
653 does not imply an abnormal edge, it will be a bit before
654 everything can be updated. So continue to emit a noop at
655 the end of such a block. */
656 if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
658 rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
659 end = emit_insn_after (nop, end);
662 create_basic_block (i++, head, end, bb_note);
670 /* A basic block ends at a jump. */
671 if (head == NULL_RTX)
675 /* ??? Make a special check for table jumps. The way this
676 happens is truly and amazingly gross. We are about to
677 create a basic block that contains just a code label and
678 an addr*vec jump insn. Worse, an addr_diff_vec creates
679 its own natural loop.
681 Prevent this bit of brain damage, pasting things together
682 correctly in make_edges.
684 The correct solution involves emitting the table directly
685 on the tablejump instruction as a note, or JUMP_LABEL. */
687 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
688 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
696 goto new_bb_inclusive;
699 /* A basic block ends at a barrier. It may be that an unconditional
700 jump already closed the basic block -- no need to do it again. */
701 if (head == NULL_RTX)
704 /* While we now have edge lists with which other portions of the
705 compiler might determine a call ending a basic block does not
706 imply an abnormal edge, it will be a bit before everything can
707 be updated. So continue to emit a noop at the end of such a
709 if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
711 rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
712 end = emit_insn_after (nop, end);
714 goto new_bb_exclusive;
718 /* Record whether this call created an edge. */
719 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
720 int region = (note ? INTVAL (XEXP (note, 0)) : 1);
721 int call_has_abnormal_edge = 0;
723 if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
725 /* Scan each of the alternatives for label refs. */
726 lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
727 lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
728 lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
729 /* Record its tail recursion label, if any. */
730 if (XEXP (PATTERN (insn), 3) != NULL_RTX)
731 trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
734 /* If there is an EH region or rethrow, we have an edge. */
735 if ((eh_list && region > 0)
736 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
737 call_has_abnormal_edge = 1;
738 else if (nonlocal_goto_handler_labels && region >= 0)
739 /* If there is a nonlocal goto label and the specified
740 region number isn't -1, we have an edge. (0 means
741 no throw, but might have a nonlocal goto). */
742 call_has_abnormal_edge = 1;
744 /* A basic block ends at a call that can either throw or
745 do a non-local goto. */
746 if (call_has_abnormal_edge)
749 if (head == NULL_RTX)
754 create_basic_block (i++, head, end, bb_note);
755 head = end = NULL_RTX;
763 if (GET_RTX_CLASS (code) == 'i')
765 if (head == NULL_RTX)
772 if (GET_RTX_CLASS (code) == 'i')
776 /* Make a list of all labels referred to other than by jumps
777 (which just don't have the REG_LABEL notes).
779 Make a special exception for labels followed by an ADDR*VEC,
780 as this would be a part of the tablejump setup code.
782 Make a special exception for the eh_return_stub_label, which
783 we know isn't part of any otherwise visible control flow. */
785 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
786 if (REG_NOTE_KIND (note) == REG_LABEL)
788 rtx lab = XEXP (note, 0), next;
790 if (lab == eh_return_stub_label)
792 else if ((next = next_nonnote_insn (lab)) != NULL
793 && GET_CODE (next) == JUMP_INSN
794 && (GET_CODE (PATTERN (next)) == ADDR_VEC
795 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
797 else if (GET_CODE (lab) == NOTE)
800 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
805 if (head != NULL_RTX)
806 create_basic_block (i++, head, end, bb_note);
808 flow_delete_insn (bb_note);
810 if (i != n_basic_blocks)
813 label_value_list = lvl;
814 tail_recursion_label_list = trll;
817 /* Tidy the CFG by deleting unreachable code and whatnot. */
823 delete_unreachable_blocks ();
824 move_stray_eh_region_notes ();
825 record_active_eh_regions (f);
827 mark_critical_edges ();
829 /* Kill the data we won't maintain. */
830 free_EXPR_LIST_list (&label_value_list);
831 free_EXPR_LIST_list (&tail_recursion_label_list);
834 /* Create a new basic block consisting of the instructions between
835 HEAD and END inclusive. Reuses the note and basic block struct
836 in BB_NOTE, if any. */
839 create_basic_block (index, head, end, bb_note)
841 rtx head, end, bb_note;
846 && ! RTX_INTEGRATED_P (bb_note)
847 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
850 /* If we found an existing note, thread it back onto the chain. */
854 if (GET_CODE (head) == CODE_LABEL)
858 after = PREV_INSN (head);
862 if (after != bb_note && NEXT_INSN (after) != bb_note)
863 reorder_insns (bb_note, bb_note, after);
867 /* Otherwise we must create a note and a basic block structure.
868 Since we allow basic block structs in rtl, give the struct
869 the same lifetime by allocating it off the function obstack
870 rather than using malloc. */
872 bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
873 memset (bb, 0, sizeof (*bb));
875 if (GET_CODE (head) == CODE_LABEL)
876 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
879 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
882 NOTE_BASIC_BLOCK (bb_note) = bb;
885 /* Always include the bb note in the block. */
886 if (NEXT_INSN (end) == bb_note)
892 BASIC_BLOCK (index) = bb;
894 /* Tag the block so that we know it has been used when considering
895 other basic block notes. */
899 /* Records the basic block struct in BB_FOR_INSN, for every instruction
900 indexed by INSN_UID. MAX is the size of the array. */
903 compute_bb_for_insn (max)
908 if (basic_block_for_insn)
909 VARRAY_FREE (basic_block_for_insn);
910 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
912 for (i = 0; i < n_basic_blocks; ++i)
914 basic_block bb = BASIC_BLOCK (i);
921 int uid = INSN_UID (insn);
923 VARRAY_BB (basic_block_for_insn, uid) = bb;
926 insn = NEXT_INSN (insn);
931 /* Free the memory associated with the edge structures. */
939 for (i = 0; i < n_basic_blocks; ++i)
941 basic_block bb = BASIC_BLOCK (i);
943 for (e = bb->succ; e ; e = n)
953 for (e = ENTRY_BLOCK_PTR->succ; e ; e = n)
959 ENTRY_BLOCK_PTR->succ = 0;
960 EXIT_BLOCK_PTR->pred = 0;
965 /* Identify the edges between basic blocks.
967 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
968 that are otherwise unreachable may be reachable with a non-local goto.
970 BB_EH_END is an array indexed by basic block number in which we record
971 the list of exception regions active at the end of the basic block. */
974 make_edges (label_value_list)
975 rtx label_value_list;
978 eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
979 sbitmap *edge_cache = NULL;
981 /* Assume no computed jump; revise as we create edges. */
982 current_function_has_computed_jump = 0;
984 /* Heavy use of computed goto in machine-generated code can lead to
985 nearly fully-connected CFGs. In that case we spend a significant
986 amount of time searching the edge lists for duplicates. */
987 if (forced_labels || label_value_list)
989 edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
990 sbitmap_vector_zero (edge_cache, n_basic_blocks);
993 /* By nature of the way these get numbered, block 0 is always the entry. */
994 make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
996 for (i = 0; i < n_basic_blocks; ++i)
998 basic_block bb = BASIC_BLOCK (i);
1001 int force_fallthru = 0;
1003 /* Examine the last instruction of the block, and discover the
1004 ways we can leave the block. */
1007 code = GET_CODE (insn);
1010 if (code == JUMP_INSN)
1014 /* ??? Recognize a tablejump and do the right thing. */
1015 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1016 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1017 && GET_CODE (tmp) == JUMP_INSN
1018 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1019 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1024 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1025 vec = XVEC (PATTERN (tmp), 0);
1027 vec = XVEC (PATTERN (tmp), 1);
1029 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1030 make_label_edge (edge_cache, bb,
1031 XEXP (RTVEC_ELT (vec, j), 0), 0);
1033 /* Some targets (eg, ARM) emit a conditional jump that also
1034 contains the out-of-range target. Scan for these and
1035 add an edge if necessary. */
1036 if ((tmp = single_set (insn)) != NULL
1037 && SET_DEST (tmp) == pc_rtx
1038 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1039 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
1040 make_label_edge (edge_cache, bb,
1041 XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
1043 #ifdef CASE_DROPS_THROUGH
1044 /* Silly VAXen. The ADDR_VEC is going to be in the way of
1045 us naturally detecting fallthru into the next block. */
1050 /* If this is a computed jump, then mark it as reaching
1051 everything on the label_value_list and forced_labels list. */
1052 else if (computed_jump_p (insn))
1054 current_function_has_computed_jump = 1;
1056 for (x = label_value_list; x; x = XEXP (x, 1))
1057 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1059 for (x = forced_labels; x; x = XEXP (x, 1))
1060 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1063 /* Returns create an exit out. */
1064 else if (returnjump_p (insn))
1065 make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
1067 /* Otherwise, we have a plain conditional or unconditional jump. */
1070 if (! JUMP_LABEL (insn))
1072 make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
1076 /* If this is a sibling call insn, then this is in effect a
1077 combined call and return, and so we need an edge to the
1078 exit block. No need to worry about EH edges, since we
1079 wouldn't have created the sibling call in the first place. */
1081 if (code == CALL_INSN && SIBLING_CALL_P (insn))
1082 make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
1083 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1086 /* If this is a CALL_INSN, then mark it as reaching the active EH
1087 handler for this CALL_INSN. If we're handling asynchronous
1088 exceptions then any insn can reach any of the active handlers.
1090 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
1092 if (code == CALL_INSN || asynchronous_exceptions)
1094 /* Add any appropriate EH edges. We do this unconditionally
1095 since there may be a REG_EH_REGION or REG_EH_RETHROW note
1096 on the call, and this needn't be within an EH region. */
1097 make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
1099 /* If we have asynchronous exceptions, do the same for *all*
1100 exception regions active in the block. */
1101 if (asynchronous_exceptions
1102 && bb->eh_beg != bb->eh_end)
1104 if (bb->eh_beg >= 0)
1105 make_eh_edge (edge_cache, eh_nest_info, bb,
1106 NULL_RTX, bb->eh_beg);
1108 for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
1109 if (GET_CODE (x) == NOTE
1110 && (NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_BEG
1111 || NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
1113 int region = NOTE_EH_HANDLER (x);
1114 make_eh_edge (edge_cache, eh_nest_info, bb,
1119 if (code == CALL_INSN && nonlocal_goto_handler_labels)
1121 /* ??? This could be made smarter: in some cases it's possible
1122 to tell that certain calls will not do a nonlocal goto.
1124 For example, if the nested functions that do the nonlocal
1125 gotos do not have their addresses taken, then only calls to
1126 those functions or to other nested functions that use them
1127 could possibly do nonlocal gotos. */
1128 /* We do know that a REG_EH_REGION note with a value less
1129 than 0 is guaranteed not to perform a non-local goto. */
1130 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1131 if (!note || INTVAL (XEXP (note, 0)) >= 0)
1132 for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
1133 make_label_edge (edge_cache, bb, XEXP (x, 0),
1134 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1138 /* We know something about the structure of the function __throw in
1139 libgcc2.c. It is the only function that ever contains eh_stub
1140 labels. It modifies its return address so that the last block
1141 returns to one of the eh_stub labels within it. So we have to
1142 make additional edges in the flow graph. */
1143 if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
1144 make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH);
1146 /* Find out if we can drop through to the next block. */
1147 insn = next_nonnote_insn (insn);
1148 if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
1149 make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1150 else if (i + 1 < n_basic_blocks)
1152 rtx tmp = BLOCK_HEAD (i + 1);
1153 if (GET_CODE (tmp) == NOTE)
1154 tmp = next_nonnote_insn (tmp);
1155 if (force_fallthru || insn == tmp)
1156 make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
1160 free_eh_nesting_info (eh_nest_info);
1162 sbitmap_vector_free (edge_cache);
1165 /* Create an edge between two basic blocks. FLAGS are auxiliary information
1166 about the edge that is accumulated between calls. */
1169 make_edge (edge_cache, src, dst, flags)
1170 sbitmap *edge_cache;
1171 basic_block src, dst;
1177 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1178 many edges to them, and we didn't allocate memory for it. */
1179 use_edge_cache = (edge_cache
1180 && src != ENTRY_BLOCK_PTR
1181 && dst != EXIT_BLOCK_PTR);
1183 /* Make sure we don't add duplicate edges. */
1184 if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
1185 for (e = src->succ; e ; e = e->succ_next)
1192 e = (edge) xcalloc (1, sizeof (*e));
1195 e->succ_next = src->succ;
1196 e->pred_next = dst->pred;
1205 SET_BIT (edge_cache[src->index], dst->index);
1208 /* Create an edge from a basic block to a label. */
1211 make_label_edge (edge_cache, src, label, flags)
1212 sbitmap *edge_cache;
1217 if (GET_CODE (label) != CODE_LABEL)
1220 /* If the label was never emitted, this insn is junk, but avoid a
1221 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
1222 as a result of a syntax error and a diagnostic has already been
1225 if (INSN_UID (label) == 0)
1228 make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
1231 /* Create the edges generated by INSN in REGION. */
1234 make_eh_edge (edge_cache, eh_nest_info, src, insn, region)
1235 sbitmap *edge_cache;
1236 eh_nesting_info *eh_nest_info;
1241 handler_info **handler_list;
1244 is_call = (insn && GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
1245 num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
1248 make_label_edge (edge_cache, src, handler_list[num]->handler_label,
1249 EDGE_ABNORMAL | EDGE_EH | is_call);
1253 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1254 dangerous if we intend to move basic blocks around. Move such notes
1255 into the following block. */
1258 move_stray_eh_region_notes ()
1263 if (n_basic_blocks < 2)
1266 b2 = BASIC_BLOCK (n_basic_blocks - 1);
1267 for (i = n_basic_blocks - 2; i >= 0; --i, b2 = b1)
1269 rtx insn, next, list = NULL_RTX;
1271 b1 = BASIC_BLOCK (i);
1272 for (insn = NEXT_INSN (b1->end); insn != b2->head; insn = next)
1274 next = NEXT_INSN (insn);
1275 if (GET_CODE (insn) == NOTE
1276 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1277 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1279 /* Unlink from the insn chain. */
1280 NEXT_INSN (PREV_INSN (insn)) = next;
1281 PREV_INSN (next) = PREV_INSN (insn);
1284 NEXT_INSN (insn) = list;
1289 if (list == NULL_RTX)
1292 /* Find where to insert these things. */
1294 if (GET_CODE (insn) == CODE_LABEL)
1295 insn = NEXT_INSN (insn);
1299 next = NEXT_INSN (list);
1300 add_insn_after (list, insn);
1306 /* Recompute eh_beg/eh_end for each basic block. */
1309 record_active_eh_regions (f)
1312 rtx insn, eh_list = NULL_RTX;
1314 basic_block bb = BASIC_BLOCK (0);
1316 for (insn = f; insn ; insn = NEXT_INSN (insn))
1318 if (bb->head == insn)
1319 bb->eh_beg = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1321 if (GET_CODE (insn) == NOTE)
1323 int kind = NOTE_LINE_NUMBER (insn);
1324 if (kind == NOTE_INSN_EH_REGION_BEG)
1325 eh_list = alloc_INSN_LIST (insn, eh_list);
1326 else if (kind == NOTE_INSN_EH_REGION_END)
1328 rtx t = XEXP (eh_list, 1);
1329 free_INSN_LIST_node (eh_list);
1334 if (bb->end == insn)
1336 bb->eh_end = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1338 if (i == n_basic_blocks)
1340 bb = BASIC_BLOCK (i);
1345 /* Identify critical edges and set the bits appropriately. */
1348 mark_critical_edges ()
1350 int i, n = n_basic_blocks;
1353 /* We begin with the entry block. This is not terribly important now,
1354 but could be if a front end (Fortran) implemented alternate entry
1356 bb = ENTRY_BLOCK_PTR;
1363 /* (1) Critical edges must have a source with multiple successors. */
1364 if (bb->succ && bb->succ->succ_next)
1366 for (e = bb->succ; e ; e = e->succ_next)
1368 /* (2) Critical edges must have a destination with multiple
1369 predecessors. Note that we know there is at least one
1370 predecessor -- the edge we followed to get here. */
1371 if (e->dest->pred->pred_next)
1372 e->flags |= EDGE_CRITICAL;
1374 e->flags &= ~EDGE_CRITICAL;
1379 for (e = bb->succ; e ; e = e->succ_next)
1380 e->flags &= ~EDGE_CRITICAL;
1385 bb = BASIC_BLOCK (i);
1389 /* Split a (typically critical) edge. Return the new block.
1390 Abort on abnormal edges.
1392 ??? The code generally expects to be called on critical edges.
1393 The case of a block ending in an unconditional jump to a
1394 block with multiple predecessors is not handled optimally. */
1397 split_edge (edge_in)
1400 basic_block old_pred, bb, old_succ;
1405 /* Abnormal edges cannot be split. */
1406 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1409 old_pred = edge_in->src;
1410 old_succ = edge_in->dest;
1412 /* Remove the existing edge from the destination's pred list. */
1415 for (pp = &old_succ->pred; *pp != edge_in; pp = &(*pp)->pred_next)
1417 *pp = edge_in->pred_next;
1418 edge_in->pred_next = NULL;
1421 /* Create the new structures. */
1422 bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
1423 edge_out = (edge) xcalloc (1, sizeof (*edge_out));
1426 memset (bb, 0, sizeof (*bb));
1428 /* ??? This info is likely going to be out of date very soon. */
1429 if (old_succ->global_live_at_start)
1431 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
1432 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
1433 COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
1434 COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
1439 bb->succ = edge_out;
1440 bb->count = edge_in->count;
1443 edge_in->flags &= ~EDGE_CRITICAL;
1445 edge_out->pred_next = old_succ->pred;
1446 edge_out->succ_next = NULL;
1448 edge_out->dest = old_succ;
1449 edge_out->flags = EDGE_FALLTHRU;
1450 edge_out->probability = REG_BR_PROB_BASE;
1451 edge_out->count = edge_in->count;
1453 old_succ->pred = edge_out;
1455 /* Tricky case -- if there existed a fallthru into the successor
1456 (and we're not it) we must add a new unconditional jump around
1457 the new block we're actually interested in.
1459 Further, if that edge is critical, this means a second new basic
1460 block must be created to hold it. In order to simplify correct
1461 insn placement, do this before we touch the existing basic block
1462 ordering for the block we were really wanting. */
1463 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1466 for (e = edge_out->pred_next; e ; e = e->pred_next)
1467 if (e->flags & EDGE_FALLTHRU)
1472 basic_block jump_block;
1475 if ((e->flags & EDGE_CRITICAL) == 0
1476 && e->src != ENTRY_BLOCK_PTR)
1478 /* Non critical -- we can simply add a jump to the end
1479 of the existing predecessor. */
1480 jump_block = e->src;
1484 /* We need a new block to hold the jump. The simplest
1485 way to do the bulk of the work here is to recursively
1487 jump_block = split_edge (e);
1488 e = jump_block->succ;
1491 /* Now add the jump insn ... */
1492 pos = emit_jump_insn_after (gen_jump (old_succ->head),
1494 jump_block->end = pos;
1495 if (basic_block_for_insn)
1496 set_block_for_insn (pos, jump_block);
1497 emit_barrier_after (pos);
1499 /* ... let jump know that label is in use, ... */
1500 JUMP_LABEL (pos) = old_succ->head;
1501 ++LABEL_NUSES (old_succ->head);
1503 /* ... and clear fallthru on the outgoing edge. */
1504 e->flags &= ~EDGE_FALLTHRU;
1506 /* Continue splitting the interesting edge. */
1510 /* Place the new block just in front of the successor. */
1511 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1512 if (old_succ == EXIT_BLOCK_PTR)
1513 j = n_basic_blocks - 1;
1515 j = old_succ->index;
1516 for (i = n_basic_blocks - 1; i > j; --i)
1518 basic_block tmp = BASIC_BLOCK (i - 1);
1519 BASIC_BLOCK (i) = tmp;
1522 BASIC_BLOCK (i) = bb;
1525 /* Create the basic block note.
1527 Where we place the note can have a noticable impact on the generated
1528 code. Consider this cfg:
1539 If we need to insert an insn on the edge from block 0 to block 1,
1540 we want to ensure the instructions we insert are outside of any
1541 loop notes that physically sit between block 0 and block 1. Otherwise
1542 we confuse the loop optimizer into thinking the loop is a phony. */
1543 if (old_succ != EXIT_BLOCK_PTR
1544 && PREV_INSN (old_succ->head)
1545 && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
1546 && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
1547 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1548 PREV_INSN (old_succ->head));
1549 else if (old_succ != EXIT_BLOCK_PTR)
1550 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
1552 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
1553 NOTE_BASIC_BLOCK (bb_note) = bb;
1554 bb->head = bb->end = bb_note;
1556 /* Not quite simple -- for non-fallthru edges, we must adjust the
1557 predecessor's jump instruction to target our new block. */
1558 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1560 rtx tmp, insn = old_pred->end;
1561 rtx old_label = old_succ->head;
1562 rtx new_label = gen_label_rtx ();
1564 if (GET_CODE (insn) != JUMP_INSN)
1567 /* ??? Recognize a tablejump and adjust all matching cases. */
1568 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1569 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1570 && GET_CODE (tmp) == JUMP_INSN
1571 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1572 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1577 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1578 vec = XVEC (PATTERN (tmp), 0);
1580 vec = XVEC (PATTERN (tmp), 1);
1582 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1583 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1585 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (VOIDmode, new_label);
1586 --LABEL_NUSES (old_label);
1587 ++LABEL_NUSES (new_label);
1590 /* Handle casesi dispatch insns */
1591 if ((tmp = single_set (insn)) != NULL
1592 && SET_DEST (tmp) == pc_rtx
1593 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1594 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1595 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1597 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
1599 --LABEL_NUSES (old_label);
1600 ++LABEL_NUSES (new_label);
1605 /* This would have indicated an abnormal edge. */
1606 if (computed_jump_p (insn))
1609 /* A return instruction can't be redirected. */
1610 if (returnjump_p (insn))
1613 /* If the insn doesn't go where we think, we're confused. */
1614 if (JUMP_LABEL (insn) != old_label)
1617 redirect_jump (insn, new_label, 0);
1620 emit_label_before (new_label, bb_note);
1621 bb->head = new_label;
1627 /* Queue instructions for insertion on an edge between two basic blocks.
1628 The new instructions and basic blocks (if any) will not appear in the
1629 CFG until commit_edge_insertions is called. */
1632 insert_insn_on_edge (pattern, e)
1636 /* We cannot insert instructions on an abnormal critical edge.
1637 It will be easier to find the culprit if we die now. */
1638 if ((e->flags & (EDGE_ABNORMAL|EDGE_CRITICAL))
1639 == (EDGE_ABNORMAL|EDGE_CRITICAL))
1642 if (e->insns == NULL_RTX)
1645 push_to_sequence (e->insns);
1647 emit_insn (pattern);
1649 e->insns = get_insns ();
1653 /* Update the CFG for the instructions queued on edge E. */
1656 commit_one_edge_insertion (e)
1659 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1662 /* Pull the insns off the edge now since the edge might go away. */
1664 e->insns = NULL_RTX;
1666 /* Figure out where to put these things. If the destination has
1667 one predecessor, insert there. Except for the exit block. */
1668 if (e->dest->pred->pred_next == NULL
1669 && e->dest != EXIT_BLOCK_PTR)
1673 /* Get the location correct wrt a code label, and "nice" wrt
1674 a basic block note, and before everything else. */
1676 if (GET_CODE (tmp) == CODE_LABEL)
1677 tmp = NEXT_INSN (tmp);
1678 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1679 tmp = NEXT_INSN (tmp);
1680 if (tmp == bb->head)
1683 after = PREV_INSN (tmp);
1686 /* If the source has one successor and the edge is not abnormal,
1687 insert there. Except for the entry block. */
1688 else if ((e->flags & EDGE_ABNORMAL) == 0
1689 && e->src->succ->succ_next == NULL
1690 && e->src != ENTRY_BLOCK_PTR)
1693 /* It is possible to have a non-simple jump here. Consider a target
1694 where some forms of unconditional jumps clobber a register. This
1695 happens on the fr30 for example.
1697 We know this block has a single successor, so we can just emit
1698 the queued insns before the jump. */
1699 if (GET_CODE (bb->end) == JUMP_INSN)
1705 /* We'd better be fallthru, or we've lost track of what's what. */
1706 if ((e->flags & EDGE_FALLTHRU) == 0)
1713 /* Otherwise we must split the edge. */
1716 bb = split_edge (e);
1720 /* Now that we've found the spot, do the insertion. */
1722 /* Set the new block number for these insns, if structure is allocated. */
1723 if (basic_block_for_insn)
1726 for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
1727 set_block_for_insn (i, bb);
1732 emit_insns_before (insns, before);
1733 if (before == bb->head)
1736 last = prev_nonnote_insn (before);
1740 last = emit_insns_after (insns, after);
1741 if (after == bb->end)
1745 if (returnjump_p (last))
1747 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1748 This is not currently a problem because this only happens
1749 for the (single) epilogue, which already has a fallthru edge
1753 if (e->dest != EXIT_BLOCK_PTR
1754 || e->succ_next != NULL
1755 || (e->flags & EDGE_FALLTHRU) == 0)
1757 e->flags &= ~EDGE_FALLTHRU;
1759 emit_barrier_after (last);
1763 flow_delete_insn (before);
1765 else if (GET_CODE (last) == JUMP_INSN)
1769 /* Update the CFG for all queued instructions. */
1772 commit_edge_insertions ()
1777 #ifdef ENABLE_CHECKING
1778 verify_flow_info ();
1782 bb = ENTRY_BLOCK_PTR;
1787 for (e = bb->succ; e ; e = next)
1789 next = e->succ_next;
1791 commit_one_edge_insertion (e);
1794 if (++i >= n_basic_blocks)
1796 bb = BASIC_BLOCK (i);
1800 /* Delete all unreachable basic blocks. */
1803 delete_unreachable_blocks ()
1805 basic_block *worklist, *tos;
1806 int deleted_handler;
1811 tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
1813 /* Use basic_block->aux as a marker. Clear them all. */
1815 for (i = 0; i < n; ++i)
1816 BASIC_BLOCK (i)->aux = NULL;
1818 /* Add our starting points to the worklist. Almost always there will
1819 be only one. It isn't inconcievable that we might one day directly
1820 support Fortran alternate entry points. */
1822 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1826 /* Mark the block with a handy non-null value. */
1830 /* Iterate: find everything reachable from what we've already seen. */
1832 while (tos != worklist)
1834 basic_block b = *--tos;
1836 for (e = b->succ; e ; e = e->succ_next)
1844 /* Delete all unreachable basic blocks. Count down so that we don't
1845 interfere with the block renumbering that happens in flow_delete_block. */
1847 deleted_handler = 0;
1849 for (i = n - 1; i >= 0; --i)
1851 basic_block b = BASIC_BLOCK (i);
1854 /* This block was found. Tidy up the mark. */
1857 deleted_handler |= flow_delete_block (b);
1860 tidy_fallthru_edges ();
1862 /* If we deleted an exception handler, we may have EH region begin/end
1863 blocks to remove as well. */
1864 if (deleted_handler)
1865 delete_eh_regions ();
1870 /* Find EH regions for which there is no longer a handler, and delete them. */
1873 delete_eh_regions ()
1877 update_rethrow_references ();
1879 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1880 if (GET_CODE (insn) == NOTE)
1882 if ((NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG) ||
1883 (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1885 int num = NOTE_EH_HANDLER (insn);
1886 /* A NULL handler indicates a region is no longer needed,
1887 as long as its rethrow label isn't used. */
1888 if (get_first_handler (num) == NULL && ! rethrow_used (num))
1890 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1891 NOTE_SOURCE_FILE (insn) = 0;
1897 /* Return true if NOTE is not one of the ones that must be kept paired,
1898 so that we may simply delete them. */
1901 can_delete_note_p (note)
1904 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
1905 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
1908 /* Unlink a chain of insns between START and FINISH, leaving notes
1909 that must be paired. */
1912 flow_delete_insn_chain (start, finish)
1915 /* Unchain the insns one by one. It would be quicker to delete all
1916 of these with a single unchaining, rather than one at a time, but
1917 we need to keep the NOTE's. */
1923 next = NEXT_INSN (start);
1924 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
1926 else if (GET_CODE (start) == CODE_LABEL
1927 && ! can_delete_label_p (start))
1929 const char *name = LABEL_NAME (start);
1930 PUT_CODE (start, NOTE);
1931 NOTE_LINE_NUMBER (start) = NOTE_INSN_DELETED_LABEL;
1932 NOTE_SOURCE_FILE (start) = name;
1935 next = flow_delete_insn (start);
1937 if (start == finish)
1943 /* Delete the insns in a (non-live) block. We physically delete every
1944 non-deleted-note insn, and update the flow graph appropriately.
1946 Return nonzero if we deleted an exception handler. */
1948 /* ??? Preserving all such notes strikes me as wrong. It would be nice
1949 to post-process the stream to remove empty blocks, loops, ranges, etc. */
1952 flow_delete_block (b)
1955 int deleted_handler = 0;
1958 /* If the head of this block is a CODE_LABEL, then it might be the
1959 label for an exception handler which can't be reached.
1961 We need to remove the label from the exception_handler_label list
1962 and remove the associated NOTE_INSN_EH_REGION_BEG and
1963 NOTE_INSN_EH_REGION_END notes. */
1967 never_reached_warning (insn);
1969 if (GET_CODE (insn) == CODE_LABEL)
1971 rtx x, *prev = &exception_handler_labels;
1973 for (x = exception_handler_labels; x; x = XEXP (x, 1))
1975 if (XEXP (x, 0) == insn)
1977 /* Found a match, splice this label out of the EH label list. */
1978 *prev = XEXP (x, 1);
1979 XEXP (x, 1) = NULL_RTX;
1980 XEXP (x, 0) = NULL_RTX;
1982 /* Remove the handler from all regions */
1983 remove_handler (insn);
1984 deleted_handler = 1;
1987 prev = &XEXP (x, 1);
1991 /* Include any jump table following the basic block. */
1993 if (GET_CODE (end) == JUMP_INSN
1994 && (tmp = JUMP_LABEL (end)) != NULL_RTX
1995 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1996 && GET_CODE (tmp) == JUMP_INSN
1997 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1998 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
2001 /* Include any barrier that may follow the basic block. */
2002 tmp = next_nonnote_insn (end);
2003 if (tmp && GET_CODE (tmp) == BARRIER)
2006 /* Selectively delete the entire chain. */
2007 flow_delete_insn_chain (insn, end);
2009 /* Remove the edges into and out of this block. Note that there may
2010 indeed be edges in, if we are removing an unreachable loop. */
2014 for (e = b->pred; e ; e = next)
2016 for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
2019 next = e->pred_next;
2023 for (e = b->succ; e ; e = next)
2025 for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
2028 next = e->succ_next;
2037 /* Remove the basic block from the array, and compact behind it. */
2040 return deleted_handler;
2043 /* Remove block B from the basic block array and compact behind it. */
2049 int i, n = n_basic_blocks;
2051 for (i = b->index; i + 1 < n; ++i)
2053 basic_block x = BASIC_BLOCK (i + 1);
2054 BASIC_BLOCK (i) = x;
2058 basic_block_info->num_elements--;
2062 /* Delete INSN by patching it out. Return the next insn. */
2065 flow_delete_insn (insn)
2068 rtx prev = PREV_INSN (insn);
2069 rtx next = NEXT_INSN (insn);
2072 PREV_INSN (insn) = NULL_RTX;
2073 NEXT_INSN (insn) = NULL_RTX;
2074 INSN_DELETED_P (insn) = 1;
2077 NEXT_INSN (prev) = next;
2079 PREV_INSN (next) = prev;
2081 set_last_insn (prev);
2083 if (GET_CODE (insn) == CODE_LABEL)
2084 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2086 /* If deleting a jump, decrement the use count of the label. Deleting
2087 the label itself should happen in the normal course of block merging. */
2088 if (GET_CODE (insn) == JUMP_INSN
2089 && JUMP_LABEL (insn)
2090 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
2091 LABEL_NUSES (JUMP_LABEL (insn))--;
2093 /* Also if deleting an insn that references a label. */
2094 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
2095 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2096 LABEL_NUSES (XEXP (note, 0))--;
2101 /* True if a given label can be deleted. */
2104 can_delete_label_p (label)
2109 if (LABEL_PRESERVE_P (label))
2112 for (x = forced_labels; x ; x = XEXP (x, 1))
2113 if (label == XEXP (x, 0))
2115 for (x = label_value_list; x ; x = XEXP (x, 1))
2116 if (label == XEXP (x, 0))
2118 for (x = exception_handler_labels; x ; x = XEXP (x, 1))
2119 if (label == XEXP (x, 0))
2122 /* User declared labels must be preserved. */
2123 if (LABEL_NAME (label) != 0)
2130 tail_recursion_label_p (label)
2135 for (x = tail_recursion_label_list; x ; x = XEXP (x, 1))
2136 if (label == XEXP (x, 0))
2142 /* Blocks A and B are to be merged into a single block A. The insns
2143 are already contiguous, hence `nomove'. */
2146 merge_blocks_nomove (a, b)
2150 rtx b_head, b_end, a_end;
2151 rtx del_first = NULL_RTX, del_last = NULL_RTX;
2154 /* If there was a CODE_LABEL beginning B, delete it. */
2157 if (GET_CODE (b_head) == CODE_LABEL)
2159 /* Detect basic blocks with nothing but a label. This can happen
2160 in particular at the end of a function. */
2161 if (b_head == b_end)
2163 del_first = del_last = b_head;
2164 b_head = NEXT_INSN (b_head);
2167 /* Delete the basic block note. */
2168 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
2170 if (b_head == b_end)
2175 b_head = NEXT_INSN (b_head);
2178 /* If there was a jump out of A, delete it. */
2180 if (GET_CODE (a_end) == JUMP_INSN)
2184 prev = prev_nonnote_insn (a_end);
2191 /* If this was a conditional jump, we need to also delete
2192 the insn that set cc0. */
2193 if (prev && sets_cc0_p (prev))
2196 prev = prev_nonnote_insn (prev);
2205 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
2206 del_first = NEXT_INSN (a_end);
2208 /* Delete everything marked above as well as crap that might be
2209 hanging out between the two blocks. */
2210 flow_delete_insn_chain (del_first, del_last);
2212 /* Normally there should only be one successor of A and that is B, but
2213 partway though the merge of blocks for conditional_execution we'll
2214 be merging a TEST block with THEN and ELSE successors. Free the
2215 whole lot of them and hope the caller knows what they're doing. */
2217 remove_edge (a->succ);
2219 /* Adjust the edges out of B for the new owner. */
2220 for (e = b->succ; e ; e = e->succ_next)
2224 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
2225 b->pred = b->succ = NULL;
2227 /* Reassociate the insns of B with A. */
2230 if (basic_block_for_insn)
2232 BLOCK_FOR_INSN (b_head) = a;
2233 while (b_head != b_end)
2235 b_head = NEXT_INSN (b_head);
2236 BLOCK_FOR_INSN (b_head) = a;
2246 /* Blocks A and B are to be merged into a single block. A has no incoming
2247 fallthru edge, so it can be moved before B without adding or modifying
2248 any jumps (aside from the jump from A to B). */
2251 merge_blocks_move_predecessor_nojumps (a, b)
2254 rtx start, end, barrier;
2260 barrier = next_nonnote_insn (end);
2261 if (GET_CODE (barrier) != BARRIER)
2263 flow_delete_insn (barrier);
2265 /* Move block and loop notes out of the chain so that we do not
2266 disturb their order.
2268 ??? A better solution would be to squeeze out all the non-nested notes
2269 and adjust the block trees appropriately. Even better would be to have
2270 a tighter connection between block trees and rtl so that this is not
2272 start = squeeze_notes (start, end);
2274 /* Scramble the insn chain. */
2275 if (end != PREV_INSN (b->head))
2276 reorder_insns (start, end, PREV_INSN (b->head));
2280 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
2281 a->index, b->index);
2284 /* Swap the records for the two blocks around. Although we are deleting B,
2285 A is now where B was and we want to compact the BB array from where
2287 BASIC_BLOCK(a->index) = b;
2288 BASIC_BLOCK(b->index) = a;
2290 a->index = b->index;
2293 /* Now blocks A and B are contiguous. Merge them. */
2294 merge_blocks_nomove (a, b);
2299 /* Blocks A and B are to be merged into a single block. B has no outgoing
2300 fallthru edge, so it can be moved after A without adding or modifying
2301 any jumps (aside from the jump from A to B). */
2304 merge_blocks_move_successor_nojumps (a, b)
2307 rtx start, end, barrier;
2311 barrier = NEXT_INSN (end);
2313 /* Recognize a jump table following block B. */
2314 if (GET_CODE (barrier) == CODE_LABEL
2315 && NEXT_INSN (barrier)
2316 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
2317 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
2318 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
2320 end = NEXT_INSN (barrier);
2321 barrier = NEXT_INSN (end);
2324 /* There had better have been a barrier there. Delete it. */
2325 if (GET_CODE (barrier) != BARRIER)
2327 flow_delete_insn (barrier);
2329 /* Move block and loop notes out of the chain so that we do not
2330 disturb their order.
2332 ??? A better solution would be to squeeze out all the non-nested notes
2333 and adjust the block trees appropriately. Even better would be to have
2334 a tighter connection between block trees and rtl so that this is not
2336 start = squeeze_notes (start, end);
2338 /* Scramble the insn chain. */
2339 reorder_insns (start, end, a->end);
2341 /* Now blocks A and B are contiguous. Merge them. */
2342 merge_blocks_nomove (a, b);
2346 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
2347 b->index, a->index);
2353 /* Attempt to merge basic blocks that are potentially non-adjacent.
2354 Return true iff the attempt succeeded. */
2357 merge_blocks (e, b, c)
2361 /* If C has a tail recursion label, do not merge. There is no
2362 edge recorded from the call_placeholder back to this label, as
2363 that would make optimize_sibling_and_tail_recursive_calls more
2364 complex for no gain. */
2365 if (GET_CODE (c->head) == CODE_LABEL
2366 && tail_recursion_label_p (c->head))
2369 /* If B has a fallthru edge to C, no need to move anything. */
2370 if (e->flags & EDGE_FALLTHRU)
2372 merge_blocks_nomove (b, c);
2376 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
2377 b->index, c->index);
2386 int c_has_outgoing_fallthru;
2387 int b_has_incoming_fallthru;
2389 /* We must make sure to not munge nesting of exception regions,
2390 lexical blocks, and loop notes.
2392 The first is taken care of by requiring that the active eh
2393 region at the end of one block always matches the active eh
2394 region at the beginning of the next block.
2396 The later two are taken care of by squeezing out all the notes. */
2398 /* ??? A throw/catch edge (or any abnormal edge) should be rarely
2399 executed and we may want to treat blocks which have two out
2400 edges, one normal, one abnormal as only having one edge for
2401 block merging purposes. */
2403 for (tmp_edge = c->succ; tmp_edge ; tmp_edge = tmp_edge->succ_next)
2404 if (tmp_edge->flags & EDGE_FALLTHRU)
2406 c_has_outgoing_fallthru = (tmp_edge != NULL);
2408 for (tmp_edge = b->pred; tmp_edge ; tmp_edge = tmp_edge->pred_next)
2409 if (tmp_edge->flags & EDGE_FALLTHRU)
2411 b_has_incoming_fallthru = (tmp_edge != NULL);
2413 /* If B does not have an incoming fallthru, and the exception regions
2414 match, then it can be moved immediately before C without introducing
2417 C can not be the first block, so we do not have to worry about
2418 accessing a non-existent block. */
2419 d = BASIC_BLOCK (c->index - 1);
2420 if (! b_has_incoming_fallthru
2421 && d->eh_end == b->eh_beg
2422 && b->eh_end == c->eh_beg)
2423 return merge_blocks_move_predecessor_nojumps (b, c);
2425 /* Otherwise, we're going to try to move C after B. Make sure the
2426 exception regions match.
2428 If B is the last basic block, then we must not try to access the
2429 block structure for block B + 1. Luckily in that case we do not
2430 need to worry about matching exception regions. */
2431 d = (b->index + 1 < n_basic_blocks ? BASIC_BLOCK (b->index + 1) : NULL);
2432 if (b->eh_end == c->eh_beg
2433 && (d == NULL || c->eh_end == d->eh_beg))
2435 /* If C does not have an outgoing fallthru, then it can be moved
2436 immediately after B without introducing or modifying jumps. */
2437 if (! c_has_outgoing_fallthru)
2438 return merge_blocks_move_successor_nojumps (b, c);
2440 /* Otherwise, we'll need to insert an extra jump, and possibly
2441 a new block to contain it. */
2442 /* ??? Not implemented yet. */
2449 /* Top level driver for merge_blocks. */
2456 /* Attempt to merge blocks as made possible by edge removal. If a block
2457 has only one successor, and the successor has only one predecessor,
2458 they may be combined. */
2460 for (i = 0; i < n_basic_blocks; )
2462 basic_block c, b = BASIC_BLOCK (i);
2465 /* A loop because chains of blocks might be combineable. */
2466 while ((s = b->succ) != NULL
2467 && s->succ_next == NULL
2468 && (s->flags & EDGE_EH) == 0
2469 && (c = s->dest) != EXIT_BLOCK_PTR
2470 && c->pred->pred_next == NULL
2471 /* If the jump insn has side effects, we can't kill the edge. */
2472 && (GET_CODE (b->end) != JUMP_INSN
2473 || onlyjump_p (b->end))
2474 && merge_blocks (s, b, c))
2477 /* Don't get confused by the index shift caused by deleting blocks. */
2482 /* The given edge should potentially be a fallthru edge. If that is in
2483 fact true, delete the jump and barriers that are in the way. */
2486 tidy_fallthru_edge (e, b, c)
2492 /* ??? In a late-running flow pass, other folks may have deleted basic
2493 blocks by nopping out blocks, leaving multiple BARRIERs between here
2494 and the target label. They ought to be chastized and fixed.
2496 We can also wind up with a sequence of undeletable labels between
2497 one block and the next.
2499 So search through a sequence of barriers, labels, and notes for
2500 the head of block C and assert that we really do fall through. */
2502 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
2505 /* Remove what will soon cease being the jump insn from the source block.
2506 If block B consisted only of this single jump, turn it into a deleted
2509 if (GET_CODE (q) == JUMP_INSN
2511 && (any_uncondjump_p (q)
2512 || (b->succ == e && e->succ_next == NULL)))
2515 /* If this was a conditional jump, we need to also delete
2516 the insn that set cc0. */
2517 if (any_condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
2524 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
2525 NOTE_SOURCE_FILE (q) = 0;
2528 b->end = q = PREV_INSN (q);
2531 /* Selectively unlink the sequence. */
2532 if (q != PREV_INSN (c->head))
2533 flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
2535 e->flags |= EDGE_FALLTHRU;
2538 /* Fix up edges that now fall through, or rather should now fall through
2539 but previously required a jump around now deleted blocks. Simplify
2540 the search by only examining blocks numerically adjacent, since this
2541 is how find_basic_blocks created them. */
2544 tidy_fallthru_edges ()
2548 for (i = 1; i < n_basic_blocks; ++i)
2550 basic_block b = BASIC_BLOCK (i - 1);
2551 basic_block c = BASIC_BLOCK (i);
2554 /* We care about simple conditional or unconditional jumps with
2557 If we had a conditional branch to the next instruction when
2558 find_basic_blocks was called, then there will only be one
2559 out edge for the block which ended with the conditional
2560 branch (since we do not create duplicate edges).
2562 Furthermore, the edge will be marked as a fallthru because we
2563 merge the flags for the duplicate edges. So we do not want to
2564 check that the edge is not a FALLTHRU edge. */
2565 if ((s = b->succ) != NULL
2566 && s->succ_next == NULL
2568 /* If the jump insn has side effects, we can't tidy the edge. */
2569 && (GET_CODE (b->end) != JUMP_INSN
2570 || onlyjump_p (b->end)))
2571 tidy_fallthru_edge (s, b, c);
2575 /* Perform data flow analysis.
2576 F is the first insn of the function; FLAGS is a set of PROP_* flags
2577 to be used in accumulating flow info. */
2580 life_analysis (f, file, flags)
2585 #ifdef ELIMINABLE_REGS
2587 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
2590 /* Record which registers will be eliminated. We use this in
2593 CLEAR_HARD_REG_SET (elim_reg_set);
2595 #ifdef ELIMINABLE_REGS
2596 for (i = 0; i < (int) (sizeof eliminables / sizeof eliminables[0]); i++)
2597 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
2599 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
2603 flags &= PROP_DEATH_NOTES | PROP_REG_INFO;
2605 /* The post-reload life analysis have (on a global basis) the same
2606 registers live as was computed by reload itself. elimination
2607 Otherwise offsets and such may be incorrect.
2609 Reload will make some registers as live even though they do not
2612 We don't want to create new auto-incs after reload, since they
2613 are unlikely to be useful and can cause problems with shared
2615 if (reload_completed)
2616 flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
2618 /* We want alias analysis information for local dead store elimination. */
2619 if (flags & PROP_SCAN_DEAD_CODE)
2620 init_alias_analysis ();
2622 /* Always remove no-op moves. Do this before other processing so
2623 that we don't have to keep re-scanning them. */
2624 delete_noop_moves (f);
2626 /* Some targets can emit simpler epilogues if they know that sp was
2627 not ever modified during the function. After reload, of course,
2628 we've already emitted the epilogue so there's no sense searching. */
2629 if (! reload_completed)
2630 notice_stack_pointer_modification (f);
2632 /* Allocate and zero out data structures that will record the
2633 data from lifetime analysis. */
2634 allocate_reg_life_data ();
2635 allocate_bb_life_data ();
2637 /* Find the set of registers live on function exit. */
2638 mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
2640 /* "Update" life info from zero. It'd be nice to begin the
2641 relaxation with just the exit and noreturn blocks, but that set
2642 is not immediately handy. */
2644 if (flags & PROP_REG_INFO)
2645 memset (regs_ever_live, 0, sizeof(regs_ever_live));
2646 update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
2649 if (flags & PROP_SCAN_DEAD_CODE)
2650 end_alias_analysis ();
2653 dump_flow_info (file);
2655 free_basic_block_vars (1);
2658 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2659 Search for REGNO. If found, abort if it is not wider than word_mode. */
2662 verify_wide_reg_1 (px, pregno)
2667 unsigned int regno = *(int *) pregno;
2669 if (GET_CODE (x) == REG && REGNO (x) == regno)
2671 if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
2678 /* A subroutine of verify_local_live_at_start. Search through insns
2679 between HEAD and END looking for register REGNO. */
2682 verify_wide_reg (regno, head, end)
2688 if (GET_RTX_CLASS (GET_CODE (head)) == 'i'
2689 && for_each_rtx (&PATTERN (head), verify_wide_reg_1, ®no))
2693 head = NEXT_INSN (head);
2696 /* We didn't find the register at all. Something's way screwy. */
2700 /* A subroutine of update_life_info. Verify that there are no untoward
2701 changes in live_at_start during a local update. */
2704 verify_local_live_at_start (new_live_at_start, bb)
2705 regset new_live_at_start;
2708 if (reload_completed)
2710 /* After reload, there are no pseudos, nor subregs of multi-word
2711 registers. The regsets should exactly match. */
2712 if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
2719 /* Find the set of changed registers. */
2720 XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
2722 EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i,
2724 /* No registers should die. */
2725 if (REGNO_REG_SET_P (bb->global_live_at_start, i))
2727 /* Verify that the now-live register is wider than word_mode. */
2728 verify_wide_reg (i, bb->head, bb->end);
2733 /* Updates life information starting with the basic blocks set in BLOCKS.
2734 If BLOCKS is null, consider it to be the universal set.
2736 If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
2737 we are only expecting local modifications to basic blocks. If we find
2738 extra registers live at the beginning of a block, then we either killed
2739 useful data, or we have a broken split that wants data not provided.
2740 If we find registers removed from live_at_start, that means we have
2741 a broken peephole that is killing a register it shouldn't.
2743 ??? This is not true in one situation -- when a pre-reload splitter
2744 generates subregs of a multi-word pseudo, current life analysis will
2745 lose the kill. So we _can_ have a pseudo go live. How irritating.
2747 Including PROP_REG_INFO does not properly refresh regs_ever_live
2748 unless the caller resets it to zero. */
2751 update_life_info (blocks, extent, prop_flags)
2753 enum update_life_extent extent;
2757 regset_head tmp_head;
2760 tmp = INITIALIZE_REG_SET (tmp_head);
2762 /* For a global update, we go through the relaxation process again. */
2763 if (extent != UPDATE_LIFE_LOCAL)
2765 calculate_global_regs_live (blocks, blocks,
2766 prop_flags & PROP_SCAN_DEAD_CODE);
2768 /* If asked, remove notes from the blocks we'll update. */
2769 if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
2770 count_or_remove_death_notes (blocks, 1);
2775 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
2777 basic_block bb = BASIC_BLOCK (i);
2779 COPY_REG_SET (tmp, bb->global_live_at_end);
2780 propagate_block (bb, tmp, (regset) NULL, prop_flags);
2782 if (extent == UPDATE_LIFE_LOCAL)
2783 verify_local_live_at_start (tmp, bb);
2788 for (i = n_basic_blocks - 1; i >= 0; --i)
2790 basic_block bb = BASIC_BLOCK (i);
2792 COPY_REG_SET (tmp, bb->global_live_at_end);
2793 propagate_block (bb, tmp, (regset) NULL, prop_flags);
2795 if (extent == UPDATE_LIFE_LOCAL)
2796 verify_local_live_at_start (tmp, bb);
2802 if (prop_flags & PROP_REG_INFO)
2804 /* The only pseudos that are live at the beginning of the function
2805 are those that were not set anywhere in the function. local-alloc
2806 doesn't know how to handle these correctly, so mark them as not
2807 local to any one basic block. */
2808 EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
2809 FIRST_PSEUDO_REGISTER, i,
2810 { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
2812 /* We have a problem with any pseudoreg that lives across the setjmp.
2813 ANSI says that if a user variable does not change in value between
2814 the setjmp and the longjmp, then the longjmp preserves it. This
2815 includes longjmp from a place where the pseudo appears dead.
2816 (In principle, the value still exists if it is in scope.)
2817 If the pseudo goes in a hard reg, some other value may occupy
2818 that hard reg where this pseudo is dead, thus clobbering the pseudo.
2819 Conclusion: such a pseudo must not go in a hard reg. */
2820 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
2821 FIRST_PSEUDO_REGISTER, i,
2823 if (regno_reg_rtx[i] != 0)
2825 REG_LIVE_LENGTH (i) = -1;
2826 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2832 /* Free the variables allocated by find_basic_blocks.
2834 KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed. */
2837 free_basic_block_vars (keep_head_end_p)
2838 int keep_head_end_p;
2840 if (basic_block_for_insn)
2842 VARRAY_FREE (basic_block_for_insn);
2843 basic_block_for_insn = NULL;
2846 if (! keep_head_end_p)
2849 VARRAY_FREE (basic_block_info);
2852 ENTRY_BLOCK_PTR->aux = NULL;
2853 ENTRY_BLOCK_PTR->global_live_at_end = NULL;
2854 EXIT_BLOCK_PTR->aux = NULL;
2855 EXIT_BLOCK_PTR->global_live_at_start = NULL;
2859 /* Return nonzero if the destination of SET equals the source. */
2864 rtx src = SET_SRC (set);
2865 rtx dst = SET_DEST (set);
2867 if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
2869 if (SUBREG_WORD (src) != SUBREG_WORD (dst))
2871 src = SUBREG_REG (src);
2872 dst = SUBREG_REG (dst);
2875 return (GET_CODE (src) == REG && GET_CODE (dst) == REG
2876 && REGNO (src) == REGNO (dst));
2879 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2885 rtx pat = PATTERN (insn);
2887 /* Insns carrying these notes are useful later on. */
2888 if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
2891 if (GET_CODE (pat) == SET && set_noop_p (pat))
2894 if (GET_CODE (pat) == PARALLEL)
2897 /* If nothing but SETs of registers to themselves,
2898 this insn can also be deleted. */
2899 for (i = 0; i < XVECLEN (pat, 0); i++)
2901 rtx tem = XVECEXP (pat, 0, i);
2903 if (GET_CODE (tem) == USE
2904 || GET_CODE (tem) == CLOBBER)
2907 if (GET_CODE (tem) != SET || ! set_noop_p (tem))
2916 /* Delete any insns that copy a register to itself. */
2919 delete_noop_moves (f)
2923 for (insn = f; insn; insn = NEXT_INSN (insn))
2925 if (GET_CODE (insn) == INSN && noop_move_p (insn))
2927 PUT_CODE (insn, NOTE);
2928 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2929 NOTE_SOURCE_FILE (insn) = 0;
2934 /* Determine if the stack pointer is constant over the life of the function.
2935 Only useful before prologues have been emitted. */
2938 notice_stack_pointer_modification_1 (x, pat, data)
2940 rtx pat ATTRIBUTE_UNUSED;
2941 void *data ATTRIBUTE_UNUSED;
2943 if (x == stack_pointer_rtx
2944 /* The stack pointer is only modified indirectly as the result
2945 of a push until later in flow. See the comments in rtl.texi
2946 regarding Embedded Side-Effects on Addresses. */
2947 || (GET_CODE (x) == MEM
2948 && (GET_CODE (XEXP (x, 0)) == PRE_DEC
2949 || GET_CODE (XEXP (x, 0)) == PRE_INC
2950 || GET_CODE (XEXP (x, 0)) == POST_DEC
2951 || GET_CODE (XEXP (x, 0)) == POST_INC)
2952 && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
2953 current_function_sp_is_unchanging = 0;
2957 notice_stack_pointer_modification (f)
2962 /* Assume that the stack pointer is unchanging if alloca hasn't
2964 current_function_sp_is_unchanging = !current_function_calls_alloca;
2965 if (! current_function_sp_is_unchanging)
2968 for (insn = f; insn; insn = NEXT_INSN (insn))
2970 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2972 /* Check if insn modifies the stack pointer. */
2973 note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
2975 if (! current_function_sp_is_unchanging)
2981 /* Mark a register in SET. Hard registers in large modes get all
2982 of their component registers set as well. */
2984 mark_reg (reg, xset)
2988 regset set = (regset) xset;
2989 int regno = REGNO (reg);
2991 if (GET_MODE (reg) == BLKmode)
2994 SET_REGNO_REG_SET (set, regno);
2995 if (regno < FIRST_PSEUDO_REGISTER)
2997 int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2999 SET_REGNO_REG_SET (set, regno + n);
3003 /* Mark those regs which are needed at the end of the function as live
3004 at the end of the last basic block. */
3006 mark_regs_live_at_end (set)
3011 /* If exiting needs the right stack value, consider the stack pointer
3012 live at the end of the function. */
3013 if ((HAVE_epilogue && reload_completed)
3014 || ! EXIT_IGNORE_STACK
3015 || (! FRAME_POINTER_REQUIRED
3016 && ! current_function_calls_alloca
3017 && flag_omit_frame_pointer)
3018 || current_function_sp_is_unchanging)
3020 SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
3023 /* Mark the frame pointer if needed at the end of the function. If
3024 we end up eliminating it, it will be removed from the live list
3025 of each basic block by reload. */
3027 if (! reload_completed || frame_pointer_needed)
3029 SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
3030 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3031 /* If they are different, also mark the hard frame pointer as live */
3032 SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
3036 #ifdef PIC_OFFSET_TABLE_REGNUM
3037 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3038 /* Many architectures have a GP register even without flag_pic.
3039 Assume the pic register is not in use, or will be handled by
3040 other means, if it is not fixed. */
3041 if (fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3042 SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
3046 /* Mark all global registers, and all registers used by the epilogue
3047 as being live at the end of the function since they may be
3048 referenced by our caller. */
3049 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3051 #ifdef EPILOGUE_USES
3052 || EPILOGUE_USES (i)
3055 SET_REGNO_REG_SET (set, i);
3057 /* Mark all call-saved registers that we actaully used. */
3058 if (HAVE_epilogue && reload_completed)
3060 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3061 if (! call_used_regs[i] && regs_ever_live[i])
3062 SET_REGNO_REG_SET (set, i);
3065 /* Mark function return value. */
3066 diddle_return_value (mark_reg, set);
3069 /* Callback function for for_each_successor_phi. DATA is a regset.
3070 Sets the SRC_REGNO, the regno of the phi alternative for phi node
3071 INSN, in the regset. */
3074 set_phi_alternative_reg (insn, dest_regno, src_regno, data)
3075 rtx insn ATTRIBUTE_UNUSED;
3076 int dest_regno ATTRIBUTE_UNUSED;
3080 regset live = (regset) data;
3081 SET_REGNO_REG_SET (live, src_regno);
3085 /* Propagate global life info around the graph of basic blocks. Begin
3086 considering blocks with their corresponding bit set in BLOCKS_IN.
3087 If BLOCKS_IN is null, consider it the universal set.
3089 BLOCKS_OUT is set for every block that was changed. */
3092 calculate_global_regs_live (blocks_in, blocks_out, flags)
3093 sbitmap blocks_in, blocks_out;
3096 basic_block *queue, *qhead, *qtail, *qend;
3097 regset tmp, new_live_at_end;
3098 regset_head tmp_head;
3099 regset_head new_live_at_end_head;
3102 tmp = INITIALIZE_REG_SET (tmp_head);
3103 new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
3105 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
3106 because the `head == tail' style test for an empty queue doesn't
3107 work with a full queue. */
3108 queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
3110 qhead = qend = queue + n_basic_blocks + 2;
3112 /* Clear out the garbage that might be hanging out in bb->aux. */
3113 for (i = n_basic_blocks - 1; i >= 0; --i)
3114 BASIC_BLOCK (i)->aux = NULL;
3116 /* Queue the blocks set in the initial mask. Do this in reverse block
3117 number order so that we are more likely for the first round to do
3118 useful work. We use AUX non-null to flag that the block is queued. */
3121 EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
3123 basic_block bb = BASIC_BLOCK (i);
3130 for (i = 0; i < n_basic_blocks; ++i)
3132 basic_block bb = BASIC_BLOCK (i);
3139 sbitmap_zero (blocks_out);
3141 while (qhead != qtail)
3143 int rescan, changed;
3152 /* Begin by propogating live_at_start from the successor blocks. */
3153 CLEAR_REG_SET (new_live_at_end);
3154 for (e = bb->succ; e ; e = e->succ_next)
3156 basic_block sb = e->dest;
3157 IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
3160 /* Force the stack pointer to be live -- which might not already be
3161 the case for blocks within infinite loops. */
3162 SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
3164 /* Regs used in phi nodes are not included in
3165 global_live_at_start, since they are live only along a
3166 particular edge. Set those regs that are live because of a
3167 phi node alternative corresponding to this particular block. */
3169 for_each_successor_phi (bb, &set_phi_alternative_reg,
3172 if (bb == ENTRY_BLOCK_PTR)
3174 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3178 /* On our first pass through this block, we'll go ahead and continue.
3179 Recognize first pass by local_set NULL. On subsequent passes, we
3180 get to skip out early if live_at_end wouldn't have changed. */
3182 if (bb->local_set == NULL)
3184 bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
3189 /* If any bits were removed from live_at_end, we'll have to
3190 rescan the block. This wouldn't be necessary if we had
3191 precalculated local_live, however with PROP_SCAN_DEAD_CODE
3192 local_live is really dependent on live_at_end. */
3193 CLEAR_REG_SET (tmp);
3194 rescan = bitmap_operation (tmp, bb->global_live_at_end,
3195 new_live_at_end, BITMAP_AND_COMPL);
3199 /* Find the set of changed bits. Take this opportunity
3200 to notice that this set is empty and early out. */
3201 CLEAR_REG_SET (tmp);
3202 changed = bitmap_operation (tmp, bb->global_live_at_end,
3203 new_live_at_end, BITMAP_XOR);
3207 /* If any of the changed bits overlap with local_set,
3208 we'll have to rescan the block. Detect overlap by
3209 the AND with ~local_set turning off bits. */
3210 rescan = bitmap_operation (tmp, tmp, bb->local_set,
3215 /* Let our caller know that BB changed enough to require its
3216 death notes updated. */
3218 SET_BIT (blocks_out, bb->index);
3222 /* Add to live_at_start the set of all registers in
3223 new_live_at_end that aren't in the old live_at_end. */
3225 bitmap_operation (tmp, new_live_at_end, bb->global_live_at_end,
3227 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3229 changed = bitmap_operation (bb->global_live_at_start,
3230 bb->global_live_at_start,
3237 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3239 /* Rescan the block insn by insn to turn (a copy of) live_at_end
3240 into live_at_start. */
3241 propagate_block (bb, new_live_at_end, bb->local_set, flags);
3243 /* If live_at start didn't change, no need to go farther. */
3244 if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
3247 COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
3250 /* Queue all predecessors of BB so that we may re-examine
3251 their live_at_end. */
3252 for (e = bb->pred; e ; e = e->pred_next)
3254 basic_block pb = e->src;
3255 if (pb->aux == NULL)
3266 FREE_REG_SET (new_live_at_end);
3270 EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
3272 basic_block bb = BASIC_BLOCK (i);
3273 FREE_REG_SET (bb->local_set);
3278 for (i = n_basic_blocks - 1; i >= 0; --i)
3280 basic_block bb = BASIC_BLOCK (i);
3281 FREE_REG_SET (bb->local_set);
3288 /* Subroutines of life analysis. */
3290 /* Allocate the permanent data structures that represent the results
3291 of life analysis. Not static since used also for stupid life analysis. */
3294 allocate_bb_life_data ()
3298 for (i = 0; i < n_basic_blocks; i++)
3300 basic_block bb = BASIC_BLOCK (i);
3302 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
3303 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
3306 ENTRY_BLOCK_PTR->global_live_at_end
3307 = OBSTACK_ALLOC_REG_SET (function_obstack);
3308 EXIT_BLOCK_PTR->global_live_at_start
3309 = OBSTACK_ALLOC_REG_SET (function_obstack);
3311 regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
3315 allocate_reg_life_data ()
3319 max_regno = max_reg_num ();
3321 /* Recalculate the register space, in case it has grown. Old style
3322 vector oriented regsets would set regset_{size,bytes} here also. */
3323 allocate_reg_info (max_regno, FALSE, FALSE);
3325 /* Reset all the data we'll collect in propagate_block and its
3327 for (i = 0; i < max_regno; i++)
3331 REG_N_DEATHS (i) = 0;
3332 REG_N_CALLS_CROSSED (i) = 0;
3333 REG_LIVE_LENGTH (i) = 0;
3334 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
3338 /* Delete dead instructions for propagate_block. */
3341 propagate_block_delete_insn (bb, insn)
3345 rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
3347 /* If the insn referred to a label, and that label was attached to
3348 an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's
3349 pretty much mandatory to delete it, because the ADDR_VEC may be
3350 referencing labels that no longer exist. */
3354 rtx label = XEXP (inote, 0);
3357 if (LABEL_NUSES (label) == 1
3358 && (next = next_nonnote_insn (label)) != NULL
3359 && GET_CODE (next) == JUMP_INSN
3360 && (GET_CODE (PATTERN (next)) == ADDR_VEC
3361 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
3363 rtx pat = PATTERN (next);
3364 int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3365 int len = XVECLEN (pat, diff_vec_p);
3368 for (i = 0; i < len; i++)
3369 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
3371 flow_delete_insn (next);
3375 if (bb->end == insn)
3376 bb->end = PREV_INSN (insn);
3377 flow_delete_insn (insn);
3380 /* Delete dead libcalls for propagate_block. Return the insn
3381 before the libcall. */
3384 propagate_block_delete_libcall (bb, insn, note)
3388 rtx first = XEXP (note, 0);
3389 rtx before = PREV_INSN (first);
3391 if (insn == bb->end)
3394 flow_delete_insn_chain (first, insn);
3398 /* Update the life-status of regs for one insn. Return the previous insn. */
3401 propagate_one_insn (pbi, insn)
3402 struct propagate_block_info *pbi;
3405 rtx prev = PREV_INSN (insn);
3406 int flags = pbi->flags;
3407 int insn_is_dead = 0;
3408 int libcall_is_dead = 0;
3412 if (! INSN_P (insn))
3415 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3416 if (flags & PROP_SCAN_DEAD_CODE)
3418 insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
3420 libcall_is_dead = (insn_is_dead && note != 0
3421 && libcall_dead_p (pbi, note, insn));
3424 /* We almost certainly don't want to delete prologue or epilogue
3425 instructions. Warn about probable compiler losage. */
3428 && (((HAVE_epilogue || HAVE_prologue)
3429 && prologue_epilogue_contains (insn))
3430 || (HAVE_sibcall_epilogue
3431 && sibcall_epilogue_contains (insn)))
3432 && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
3434 if (flags & PROP_KILL_DEAD_CODE)
3436 warning ("ICE: would have deleted prologue/epilogue insn");
3437 if (!inhibit_warnings)
3440 libcall_is_dead = insn_is_dead = 0;
3443 /* If an instruction consists of just dead store(s) on final pass,
3445 if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
3447 /* Record sets. Do this even for dead instructions, since they
3448 would have killed the values if they hadn't been deleted. */
3449 mark_set_regs (pbi, PATTERN (insn), insn);
3451 /* CC0 is now known to be dead. Either this insn used it,
3452 in which case it doesn't anymore, or clobbered it,
3453 so the next insn can't use it. */
3456 if (libcall_is_dead)
3458 prev = propagate_block_delete_libcall (pbi->bb, insn, note);
3459 insn = NEXT_INSN (prev);
3462 propagate_block_delete_insn (pbi->bb, insn);
3467 /* See if this is an increment or decrement that can be merged into
3468 a following memory address. */
3471 register rtx x = single_set (insn);
3473 /* Does this instruction increment or decrement a register? */
3474 if ((flags & PROP_AUTOINC)
3476 && GET_CODE (SET_DEST (x)) == REG
3477 && (GET_CODE (SET_SRC (x)) == PLUS
3478 || GET_CODE (SET_SRC (x)) == MINUS)
3479 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
3480 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
3481 /* Ok, look for a following memory ref we can combine with.
3482 If one is found, change the memory ref to a PRE_INC
3483 or PRE_DEC, cancel this insn, and return 1.
3484 Return 0 if nothing has been done. */
3485 && try_pre_increment_1 (pbi, insn))
3488 #endif /* AUTO_INC_DEC */
3490 CLEAR_REG_SET (pbi->new_set);
3492 /* If this is not the final pass, and this insn is copying the value of
3493 a library call and it's dead, don't scan the insns that perform the
3494 library call, so that the call's arguments are not marked live. */
3495 if (libcall_is_dead)
3497 /* Record the death of the dest reg. */
3498 mark_set_regs (pbi, PATTERN (insn), insn);
3500 insn = XEXP (note, 0);
3501 return PREV_INSN (insn);
3503 else if (GET_CODE (PATTERN (insn)) == SET
3504 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
3505 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
3506 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
3507 && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
3508 /* We have an insn to pop a constant amount off the stack.
3509 (Such insns use PLUS regardless of the direction of the stack,
3510 and any insn to adjust the stack by a constant is always a pop.)
3511 These insns, if not dead stores, have no effect on life. */
3515 /* Any regs live at the time of a call instruction must not go
3516 in a register clobbered by calls. Find all regs now live and
3517 record this for them. */
3519 if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
3520 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3521 { REG_N_CALLS_CROSSED (i)++; });
3523 /* Record sets. Do this even for dead instructions, since they
3524 would have killed the values if they hadn't been deleted. */
3525 mark_set_regs (pbi, PATTERN (insn), insn);
3527 if (GET_CODE (insn) == CALL_INSN)
3533 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3534 cond = COND_EXEC_TEST (PATTERN (insn));
3536 /* Non-constant calls clobber memory. */
3537 if (! CONST_CALL_P (insn))
3538 free_EXPR_LIST_list (&pbi->mem_set_list);
3540 /* There may be extra registers to be clobbered. */
3541 for (note = CALL_INSN_FUNCTION_USAGE (insn);
3543 note = XEXP (note, 1))
3544 if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3545 mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
3546 cond, insn, pbi->flags);
3548 /* Calls change all call-used and global registers. */
3549 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3550 if (call_used_regs[i] && ! global_regs[i]
3553 /* We do not want REG_UNUSED notes for these registers. */
3554 mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
3556 pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
3560 /* If an insn doesn't use CC0, it becomes dead since we assume
3561 that every insn clobbers it. So show it dead here;
3562 mark_used_regs will set it live if it is referenced. */
3567 mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
3569 /* Sometimes we may have inserted something before INSN (such as a move)
3570 when we make an auto-inc. So ensure we will scan those insns. */
3572 prev = PREV_INSN (insn);
3575 if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
3581 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3582 cond = COND_EXEC_TEST (PATTERN (insn));
3584 /* Calls use their arguments. */
3585 for (note = CALL_INSN_FUNCTION_USAGE (insn);
3587 note = XEXP (note, 1))
3588 if (GET_CODE (XEXP (note, 0)) == USE)
3589 mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
3592 /* The stack ptr is used (honorarily) by a CALL insn. */
3593 SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
3595 /* Calls may also reference any of the global registers,
3596 so they are made live. */
3597 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3599 mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
3604 /* On final pass, update counts of how many insns in which each reg
3606 if (flags & PROP_REG_INFO)
3607 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3608 { REG_LIVE_LENGTH (i)++; });
3613 /* Initialize a propagate_block_info struct for public consumption.
3614 Note that the structure itself is opaque to this file, but that
3615 the user can use the regsets provided here. */
3617 struct propagate_block_info *
3618 init_propagate_block_info (bb, live, local_set, flags)
3624 struct propagate_block_info *pbi = xmalloc (sizeof(*pbi));
3627 pbi->reg_live = live;
3628 pbi->mem_set_list = NULL_RTX;
3629 pbi->local_set = local_set;
3633 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3634 pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
3636 pbi->reg_next_use = NULL;
3638 pbi->new_set = BITMAP_XMALLOC ();
3640 #ifdef HAVE_conditional_execution
3641 pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
3642 free_reg_cond_life_info);
3643 pbi->reg_cond_reg = BITMAP_XMALLOC ();
3645 /* If this block ends in a conditional branch, for each register live
3646 from one side of the branch and not the other, record the register
3647 as conditionally dead. */
3648 if ((flags & (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE))
3649 && GET_CODE (bb->end) == JUMP_INSN
3650 && any_condjump_p (bb->end))
3652 regset_head diff_head;
3653 regset diff = INITIALIZE_REG_SET (diff_head);
3654 basic_block bb_true, bb_false;
3655 rtx cond_true, cond_false, set_src;
3658 /* Identify the successor blocks. */
3659 bb_true = bb->succ->dest;
3660 if (bb->succ->succ_next != NULL)
3662 bb_false = bb->succ->succ_next->dest;
3664 if (bb->succ->flags & EDGE_FALLTHRU)
3666 basic_block t = bb_false;
3670 else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
3675 /* This can happen with a conditional jump to the next insn. */
3676 if (JUMP_LABEL (bb->end) != bb_true->head)
3679 /* Simplest way to do nothing. */
3683 /* Extract the condition from the branch. */
3684 set_src = SET_SRC (pc_set (bb->end));
3685 cond_true = XEXP (set_src, 0);
3686 cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
3687 GET_MODE (cond_true), XEXP (cond_true, 0),
3688 XEXP (cond_true, 1));
3689 if (GET_CODE (XEXP (set_src, 1)) == PC)
3692 cond_false = cond_true;
3696 /* Compute which register lead different lives in the successors. */
3697 if (bitmap_operation (diff, bb_true->global_live_at_start,
3698 bb_false->global_live_at_start, BITMAP_XOR))
3700 if (GET_CODE (XEXP (cond_true, 0)) != REG)
3702 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond_true, 0)));
3704 /* For each such register, mark it conditionally dead. */
3705 EXECUTE_IF_SET_IN_REG_SET
3708 struct reg_cond_life_info *rcli;
3711 rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
3713 if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
3717 rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
3719 splay_tree_insert (pbi->reg_cond_dead, i,
3720 (splay_tree_value) rcli);
3724 FREE_REG_SET (diff);
3728 /* If this block has no successors, any stores to the frame that aren't
3729 used later in the block are dead. So make a pass over the block
3730 recording any such that are made and show them dead at the end. We do
3731 a very conservative and simple job here. */
3732 if ((flags & PROP_SCAN_DEAD_CODE)
3733 && (bb->succ == NULL
3734 || (bb->succ->succ_next == NULL
3735 && bb->succ->dest == EXIT_BLOCK_PTR)))
3738 for (insn = bb->end; insn != bb->head; insn = PREV_INSN (insn))
3739 if (GET_CODE (insn) == INSN
3740 && GET_CODE (PATTERN (insn)) == SET
3741 && GET_CODE (SET_DEST (PATTERN (insn))) == MEM)
3743 rtx mem = SET_DEST (PATTERN (insn));
3745 if (XEXP (mem, 0) == frame_pointer_rtx
3746 || (GET_CODE (XEXP (mem, 0)) == PLUS
3747 && XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx
3748 && GET_CODE (XEXP (XEXP (mem, 0), 1)) == CONST_INT))
3749 pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
3756 /* Release a propagate_block_info struct. */
3759 free_propagate_block_info (pbi)
3760 struct propagate_block_info *pbi;
3762 free_EXPR_LIST_list (&pbi->mem_set_list);
3764 BITMAP_XFREE (pbi->new_set);
3766 #ifdef HAVE_conditional_execution
3767 splay_tree_delete (pbi->reg_cond_dead);
3768 BITMAP_XFREE (pbi->reg_cond_reg);
3771 if (pbi->reg_next_use)
3772 free (pbi->reg_next_use);
3777 /* Compute the registers live at the beginning of a basic block BB from
3778 those live at the end.
3780 When called, REG_LIVE contains those live at the end. On return, it
3781 contains those live at the beginning.
3783 LOCAL_SET, if non-null, will be set with all registers killed by
3784 this basic block. */
3787 propagate_block (bb, live, local_set, flags)
3793 struct propagate_block_info *pbi;
3796 pbi = init_propagate_block_info (bb, live, local_set, flags);
3798 if (flags & PROP_REG_INFO)
3802 /* Process the regs live at the end of the block.
3803 Mark them as not local to any one basic block. */
3804 EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
3805 { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
3808 /* Scan the block an insn at a time from end to beginning. */
3810 for (insn = bb->end; ; insn = prev)
3812 /* If this is a call to `setjmp' et al, warn if any
3813 non-volatile datum is live. */
3814 if ((flags & PROP_REG_INFO)
3815 && GET_CODE (insn) == NOTE
3816 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3817 IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
3819 prev = propagate_one_insn (pbi, insn);
3821 if (insn == bb->head)
3825 free_propagate_block_info (pbi);
3828 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3829 (SET expressions whose destinations are registers dead after the insn).
3830 NEEDED is the regset that says which regs are alive after the insn.
3832 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3834 If X is the entire body of an insn, NOTES contains the reg notes
3835 pertaining to the insn. */
3838 insn_dead_p (pbi, x, call_ok, notes)
3839 struct propagate_block_info *pbi;
3842 rtx notes ATTRIBUTE_UNUSED;
3844 enum rtx_code code = GET_CODE (x);
3847 /* If flow is invoked after reload, we must take existing AUTO_INC
3848 expresions into account. */
3849 if (reload_completed)
3851 for ( ; notes; notes = XEXP (notes, 1))
3853 if (REG_NOTE_KIND (notes) == REG_INC)
3855 int regno = REGNO (XEXP (notes, 0));
3857 /* Don't delete insns to set global regs. */
3858 if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3859 || REGNO_REG_SET_P (pbi->reg_live, regno))
3866 /* If setting something that's a reg or part of one,
3867 see if that register's altered value will be live. */
3871 rtx r = SET_DEST (x);
3874 if (GET_CODE (r) == CC0)
3875 return ! pbi->cc0_live;
3878 /* A SET that is a subroutine call cannot be dead. */
3879 if (GET_CODE (SET_SRC (x)) == CALL)
3885 /* Don't eliminate loads from volatile memory or volatile asms. */
3886 else if (volatile_refs_p (SET_SRC (x)))
3889 if (GET_CODE (r) == MEM)
3893 if (MEM_VOLATILE_P (r))
3896 /* Walk the set of memory locations we are currently tracking
3897 and see if one is an identical match to this memory location.
3898 If so, this memory write is dead (remember, we're walking
3899 backwards from the end of the block to the start). */
3900 temp = pbi->mem_set_list;
3903 if (rtx_equal_p (XEXP (temp, 0), r))
3905 temp = XEXP (temp, 1);
3910 while (GET_CODE (r) == SUBREG
3911 || GET_CODE (r) == STRICT_LOW_PART
3912 || GET_CODE (r) == ZERO_EXTRACT)
3915 if (GET_CODE (r) == REG)
3917 int regno = REGNO (r);
3920 if (REGNO_REG_SET_P (pbi->reg_live, regno))
3923 /* If this is a hard register, verify that subsequent
3924 words are not needed. */
3925 if (regno < FIRST_PSEUDO_REGISTER)
3927 int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
3930 if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
3934 /* Don't delete insns to set global regs. */
3935 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3938 /* Make sure insns to set the stack pointer aren't deleted. */
3939 if (regno == STACK_POINTER_REGNUM)
3942 /* Make sure insns to set the frame pointer aren't deleted. */
3943 if (regno == FRAME_POINTER_REGNUM
3944 && (! reload_completed || frame_pointer_needed))
3946 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3947 if (regno == HARD_FRAME_POINTER_REGNUM
3948 && (! reload_completed || frame_pointer_needed))
3952 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3953 /* Make sure insns to set arg pointer are never deleted
3954 (if the arg pointer isn't fixed, there will be a USE
3955 for it, so we can treat it normally). */
3956 if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
3960 #ifdef PIC_OFFSET_TABLE_REGNUM
3961 /* Before reload, do not allow sets of the pic register
3962 to be deleted. Reload can insert references to
3963 constant pool memory anywhere in the function, making
3964 the PIC register live where it wasn't before. */
3965 if (regno == PIC_OFFSET_TABLE_REGNUM && fixed_regs[regno]
3966 && ! reload_completed)
3970 /* Otherwise, the set is dead. */
3976 /* If performing several activities, insn is dead if each activity
3977 is individually dead. Also, CLOBBERs and USEs can be ignored; a
3978 CLOBBER or USE that's inside a PARALLEL doesn't make the insn
3980 else if (code == PARALLEL)
3982 int i = XVECLEN (x, 0);
3984 for (i--; i >= 0; i--)
3985 if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
3986 && GET_CODE (XVECEXP (x, 0, i)) != USE
3987 && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
3993 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
3994 is not necessarily true for hard registers. */
3995 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
3996 && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
3997 && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
4000 /* We do not check other CLOBBER or USE here. An insn consisting of just
4001 a CLOBBER or just a USE should not be deleted. */
4005 /* If INSN is the last insn in a libcall, and assuming INSN is dead,
4006 return 1 if the entire library call is dead.
4007 This is true if INSN copies a register (hard or pseudo)
4008 and if the hard return reg of the call insn is dead.
4009 (The caller should have tested the destination of the SET inside
4010 INSN already for death.)
4012 If this insn doesn't just copy a register, then we don't
4013 have an ordinary libcall. In that case, cse could not have
4014 managed to substitute the source for the dest later on,
4015 so we can assume the libcall is dead.
4017 PBI is the block info giving pseudoregs live before this insn.
4018 NOTE is the REG_RETVAL note of the insn. */
4021 libcall_dead_p (pbi, note, insn)
4022 struct propagate_block_info *pbi;
4026 rtx x = single_set (insn);
4030 register rtx r = SET_SRC (x);
4031 if (GET_CODE (r) == REG)
4033 rtx call = XEXP (note, 0);
4037 /* Find the call insn. */
4038 while (call != insn && GET_CODE (call) != CALL_INSN)
4039 call = NEXT_INSN (call);
4041 /* If there is none, do nothing special,
4042 since ordinary death handling can understand these insns. */
4046 /* See if the hard reg holding the value is dead.
4047 If this is a PARALLEL, find the call within it. */
4048 call_pat = PATTERN (call);
4049 if (GET_CODE (call_pat) == PARALLEL)
4051 for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
4052 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
4053 && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
4056 /* This may be a library call that is returning a value
4057 via invisible pointer. Do nothing special, since
4058 ordinary death handling can understand these insns. */
4062 call_pat = XVECEXP (call_pat, 0, i);
4065 return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
4071 /* Return 1 if register REGNO was used before it was set, i.e. if it is
4072 live at function entry. Don't count global register variables, variables
4073 in registers that can be used for function arg passing, or variables in
4074 fixed hard registers. */
4077 regno_uninitialized (regno)
4080 if (n_basic_blocks == 0
4081 || (regno < FIRST_PSEUDO_REGISTER
4082 && (global_regs[regno]
4083 || fixed_regs[regno]
4084 || FUNCTION_ARG_REGNO_P (regno))))
4087 return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno);
4090 /* 1 if register REGNO was alive at a place where `setjmp' was called
4091 and was set more than once or is an argument.
4092 Such regs may be clobbered by `longjmp'. */
4095 regno_clobbered_at_setjmp (regno)
4098 if (n_basic_blocks == 0)
4101 return ((REG_N_SETS (regno) > 1
4102 || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno))
4103 && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
4106 /* INSN references memory, possibly using autoincrement addressing modes.
4107 Find any entries on the mem_set_list that need to be invalidated due
4108 to an address change. */
4111 invalidate_mems_from_autoinc (pbi, insn)
4112 struct propagate_block_info *pbi;
4115 rtx note = REG_NOTES (insn);
4116 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
4118 if (REG_NOTE_KIND (note) == REG_INC)
4120 rtx temp = pbi->mem_set_list;
4121 rtx prev = NULL_RTX;
4126 next = XEXP (temp, 1);
4127 if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
4129 /* Splice temp out of list. */
4131 XEXP (prev, 1) = next;
4133 pbi->mem_set_list = next;
4134 free_EXPR_LIST_node (temp);
4144 /* Process the registers that are set within X. Their bits are set to
4145 1 in the regset DEAD, because they are dead prior to this insn.
4147 If INSN is nonzero, it is the insn being processed.
4149 FLAGS is the set of operations to perform. */
4152 mark_set_regs (pbi, x, insn)
4153 struct propagate_block_info *pbi;
4156 rtx cond = NULL_RTX;
4161 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4163 if (REG_NOTE_KIND (link) == REG_INC)
4164 mark_set_1 (pbi, SET, XEXP (link, 0),
4165 (GET_CODE (x) == COND_EXEC
4166 ? COND_EXEC_TEST (x) : NULL_RTX),
4170 switch (code = GET_CODE (x))
4174 mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
4178 cond = COND_EXEC_TEST (x);
4179 x = COND_EXEC_CODE (x);
4185 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4187 rtx sub = XVECEXP (x, 0, i);
4188 switch (code = GET_CODE (sub))
4191 if (cond != NULL_RTX)
4194 cond = COND_EXEC_TEST (sub);
4195 sub = COND_EXEC_CODE (sub);
4196 if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
4202 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
4217 /* Process a single SET rtx, X. */
4220 mark_set_1 (pbi, code, reg, cond, insn, flags)
4221 struct propagate_block_info *pbi;
4223 rtx reg, cond, insn;
4226 int regno_first = -1, regno_last = -1;
4230 /* Some targets place small structures in registers for
4231 return values of functions. We have to detect this
4232 case specially here to get correct flow information. */
4233 if (GET_CODE (reg) == PARALLEL
4234 && GET_MODE (reg) == BLKmode)
4236 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4237 mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
4241 /* Modifying just one hardware register of a multi-reg value or just a
4242 byte field of a register does not mean the value from before this insn
4243 is now dead. Of course, if it was dead after it's unused now. */
4245 switch (GET_CODE (reg))
4249 case STRICT_LOW_PART:
4250 /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */
4252 reg = XEXP (reg, 0);
4253 while (GET_CODE (reg) == SUBREG
4254 || GET_CODE (reg) == ZERO_EXTRACT
4255 || GET_CODE (reg) == SIGN_EXTRACT
4256 || GET_CODE (reg) == STRICT_LOW_PART);
4257 if (GET_CODE (reg) == MEM)
4259 not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
4263 regno_last = regno_first = REGNO (reg);
4264 if (regno_first < FIRST_PSEUDO_REGISTER)
4265 regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
4269 if (GET_CODE (SUBREG_REG (reg)) == REG)
4271 enum machine_mode outer_mode = GET_MODE (reg);
4272 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
4274 /* Identify the range of registers affected. This is moderately
4275 tricky for hard registers. See alter_subreg. */
4277 regno_last = regno_first = REGNO (SUBREG_REG (reg));
4278 if (regno_first < FIRST_PSEUDO_REGISTER)
4280 #ifdef ALTER_HARD_SUBREG
4281 regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
4282 inner_mode, regno_first);
4284 regno_first += SUBREG_WORD (reg);
4286 regno_last = (regno_first
4287 + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
4289 /* Since we've just adjusted the register number ranges, make
4290 sure REG matches. Otherwise some_was_live will be clear
4291 when it shouldn't have been, and we'll create incorrect
4292 REG_UNUSED notes. */
4293 reg = gen_rtx_REG (outer_mode, regno_first);
4297 /* If the number of words in the subreg is less than the number
4298 of words in the full register, we have a well-defined partial
4299 set. Otherwise the high bits are undefined.
4301 This is only really applicable to pseudos, since we just took
4302 care of multi-word hard registers. */
4303 if (((GET_MODE_SIZE (outer_mode)
4304 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
4305 < ((GET_MODE_SIZE (inner_mode)
4306 + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
4307 not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
4309 reg = SUBREG_REG (reg);
4313 reg = SUBREG_REG (reg);
4320 /* If this set is a MEM, then it kills any aliased writes.
4321 If this set is a REG, then it kills any MEMs which use the reg. */
4322 if (flags & PROP_SCAN_DEAD_CODE)
4324 if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
4326 rtx temp = pbi->mem_set_list;
4327 rtx prev = NULL_RTX;
4332 next = XEXP (temp, 1);
4333 if ((GET_CODE (reg) == MEM
4334 && output_dependence (XEXP (temp, 0), reg))
4335 || (GET_CODE (reg) == REG
4336 && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
4338 /* Splice this entry out of the list. */
4340 XEXP (prev, 1) = next;
4342 pbi->mem_set_list = next;
4343 free_EXPR_LIST_node (temp);
4351 /* If the memory reference had embedded side effects (autoincrement
4352 address modes. Then we may need to kill some entries on the
4354 if (insn && GET_CODE (reg) == MEM)
4355 invalidate_mems_from_autoinc (pbi, insn);
4357 if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
4358 /* ??? With more effort we could track conditional memory life. */
4360 /* We do not know the size of a BLKmode store, so we do not track
4361 them for redundant store elimination. */
4362 && GET_MODE (reg) != BLKmode
4363 /* There are no REG_INC notes for SP, so we can't assume we'll see
4364 everything that invalidates it. To be safe, don't eliminate any
4365 stores though SP; none of them should be redundant anyway. */
4366 && ! reg_mentioned_p (stack_pointer_rtx, reg))
4367 pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
4370 if (GET_CODE (reg) == REG
4371 && ! (regno_first == FRAME_POINTER_REGNUM
4372 && (! reload_completed || frame_pointer_needed))
4373 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4374 && ! (regno_first == HARD_FRAME_POINTER_REGNUM
4375 && (! reload_completed || frame_pointer_needed))
4377 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4378 && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
4382 int some_was_live = 0, some_was_dead = 0;
4384 for (i = regno_first; i <= regno_last; ++i)
4386 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
4388 SET_REGNO_REG_SET (pbi->local_set, i);
4389 if (code != CLOBBER)
4390 SET_REGNO_REG_SET (pbi->new_set, i);
4392 some_was_live |= needed_regno;
4393 some_was_dead |= ! needed_regno;
4396 #ifdef HAVE_conditional_execution
4397 /* Consider conditional death in deciding that the register needs
4399 if (some_was_live && ! not_dead
4400 /* The stack pointer is never dead. Well, not strictly true,
4401 but it's very difficult to tell from here. Hopefully
4402 combine_stack_adjustments will fix up the most egregious
4404 && regno_first != STACK_POINTER_REGNUM)
4406 for (i = regno_first; i <= regno_last; ++i)
4407 if (! mark_regno_cond_dead (pbi, i, cond))
4412 /* Additional data to record if this is the final pass. */
4413 if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
4414 | PROP_DEATH_NOTES | PROP_AUTOINC))
4417 register int blocknum = pbi->bb->index;
4420 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4422 y = pbi->reg_next_use[regno_first];
4424 /* The next use is no longer next, since a store intervenes. */
4425 for (i = regno_first; i <= regno_last; ++i)
4426 pbi->reg_next_use[i] = 0;
4429 if (flags & PROP_REG_INFO)
4431 for (i = regno_first; i <= regno_last; ++i)
4433 /* Count (weighted) references, stores, etc. This counts a
4434 register twice if it is modified, but that is correct. */
4435 REG_N_SETS (i) += 1;
4436 REG_N_REFS (i) += (optimize_size ? 1
4437 : pbi->bb->loop_depth + 1);
4439 /* The insns where a reg is live are normally counted
4440 elsewhere, but we want the count to include the insn
4441 where the reg is set, and the normal counting mechanism
4442 would not count it. */
4443 REG_LIVE_LENGTH (i) += 1;
4446 /* If this is a hard reg, record this function uses the reg. */
4447 if (regno_first < FIRST_PSEUDO_REGISTER)
4449 for (i = regno_first; i <= regno_last; i++)
4450 regs_ever_live[i] = 1;
4454 /* Keep track of which basic blocks each reg appears in. */
4455 if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
4456 REG_BASIC_BLOCK (regno_first) = blocknum;
4457 else if (REG_BASIC_BLOCK (regno_first) != blocknum)
4458 REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
4462 if (! some_was_dead)
4464 if (flags & PROP_LOG_LINKS)
4466 /* Make a logical link from the next following insn
4467 that uses this register, back to this insn.
4468 The following insns have already been processed.
4470 We don't build a LOG_LINK for hard registers containing
4471 in ASM_OPERANDs. If these registers get replaced,
4472 we might wind up changing the semantics of the insn,
4473 even if reload can make what appear to be valid
4474 assignments later. */
4475 if (y && (BLOCK_NUM (y) == blocknum)
4476 && (regno_first >= FIRST_PSEUDO_REGISTER
4477 || asm_noperands (PATTERN (y)) < 0))
4478 LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
4483 else if (! some_was_live)
4485 if (flags & PROP_REG_INFO)
4486 REG_N_DEATHS (regno_first) += 1;
4488 if (flags & PROP_DEATH_NOTES)
4490 /* Note that dead stores have already been deleted
4491 when possible. If we get here, we have found a
4492 dead store that cannot be eliminated (because the
4493 same insn does something useful). Indicate this
4494 by marking the reg being set as dying here. */
4496 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4501 if (flags & PROP_DEATH_NOTES)
4503 /* This is a case where we have a multi-word hard register
4504 and some, but not all, of the words of the register are
4505 needed in subsequent insns. Write REG_UNUSED notes
4506 for those parts that were not needed. This case should
4509 for (i = regno_first; i <= regno_last; ++i)
4510 if (! REGNO_REG_SET_P (pbi->reg_live, i))
4512 = alloc_EXPR_LIST (REG_UNUSED,
4513 gen_rtx_REG (reg_raw_mode[i], i),
4519 /* Mark the register as being dead. */
4522 /* The stack pointer is never dead. Well, not strictly true,
4523 but it's very difficult to tell from here. Hopefully
4524 combine_stack_adjustments will fix up the most egregious
4526 && regno_first != STACK_POINTER_REGNUM)
4528 for (i = regno_first; i <= regno_last; ++i)
4529 CLEAR_REGNO_REG_SET (pbi->reg_live, i);
4532 else if (GET_CODE (reg) == REG)
4534 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4535 pbi->reg_next_use[regno_first] = 0;
4538 /* If this is the last pass and this is a SCRATCH, show it will be dying
4539 here and count it. */
4540 else if (GET_CODE (reg) == SCRATCH)
4542 if (flags & PROP_DEATH_NOTES)
4544 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4548 #ifdef HAVE_conditional_execution
4549 /* Mark REGNO conditionally dead. Return true if the register is
4550 now unconditionally dead. */
4553 mark_regno_cond_dead (pbi, regno, cond)
4554 struct propagate_block_info *pbi;
4558 /* If this is a store to a predicate register, the value of the
4559 predicate is changing, we don't know that the predicate as seen
4560 before is the same as that seen after. Flush all dependent
4561 conditions from reg_cond_dead. This will make all such
4562 conditionally live registers unconditionally live. */
4563 if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
4564 flush_reg_cond_reg (pbi, regno);
4566 /* If this is an unconditional store, remove any conditional
4567 life that may have existed. */
4568 if (cond == NULL_RTX)
4569 splay_tree_remove (pbi->reg_cond_dead, regno);
4572 splay_tree_node node;
4573 struct reg_cond_life_info *rcli;
4576 /* Otherwise this is a conditional set. Record that fact.
4577 It may have been conditionally used, or there may be a
4578 subsequent set with a complimentary condition. */
4580 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
4583 /* The register was unconditionally live previously.
4584 Record the current condition as the condition under
4585 which it is dead. */
4586 rcli = (struct reg_cond_life_info *)
4587 xmalloc (sizeof (*rcli));
4588 rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
4589 splay_tree_insert (pbi->reg_cond_dead, regno,
4590 (splay_tree_value) rcli);
4592 SET_REGNO_REG_SET (pbi->reg_cond_reg,
4593 REGNO (XEXP (cond, 0)));
4595 /* Not unconditionaly dead. */
4600 /* The register was conditionally live previously.
4601 Add the new condition to the old. */
4602 rcli = (struct reg_cond_life_info *) node->value;
4603 ncond = rcli->condition;
4604 ncond = ior_reg_cond (ncond, cond);
4606 /* If the register is now unconditionally dead,
4607 remove the entry in the splay_tree. */
4608 if (ncond == const1_rtx)
4609 splay_tree_remove (pbi->reg_cond_dead, regno);
4612 rcli->condition = ncond;
4614 SET_REGNO_REG_SET (pbi->reg_cond_reg,
4615 REGNO (XEXP (cond, 0)));
4617 /* Not unconditionaly dead. */
4626 /* Called from splay_tree_delete for pbi->reg_cond_life. */
4629 free_reg_cond_life_info (value)
4630 splay_tree_value value;
4632 struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
4633 free_EXPR_LIST_list (&rcli->condition);
4637 /* Helper function for flush_reg_cond_reg. */
4640 flush_reg_cond_reg_1 (node, data)
4641 splay_tree_node node;
4644 struct reg_cond_life_info *rcli;
4645 int *xdata = (int *) data;
4646 unsigned int regno = xdata[0];
4649 /* Don't need to search if last flushed value was farther on in
4650 the in-order traversal. */
4651 if (xdata[1] >= (int) node->key)
4654 /* Splice out portions of the expression that refer to regno. */
4655 rcli = (struct reg_cond_life_info *) node->value;
4656 c = *(prev = &rcli->condition);
4659 if (regno == REGNO (XEXP (XEXP (c, 0), 0)))
4661 rtx next = XEXP (c, 1);
4662 free_EXPR_LIST_node (c);
4666 c = *(prev = &XEXP (c, 1));
4669 /* If the entire condition is now NULL, signal the node to be removed. */
4670 if (! rcli->condition)
4672 xdata[1] = node->key;
4679 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
4682 flush_reg_cond_reg (pbi, regno)
4683 struct propagate_block_info *pbi;
4690 while (splay_tree_foreach (pbi->reg_cond_dead,
4691 flush_reg_cond_reg_1, pair) == -1)
4692 splay_tree_remove (pbi->reg_cond_dead, pair[1]);
4694 CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
4697 /* Logical arithmetic on predicate conditions. IOR, NOT and NAND.
4698 We actually use EXPR_LIST to chain the sub-expressions together
4699 instead of IOR because it's easier to manipulate and we have
4700 the lists.c functions to reuse nodes.
4702 Return a new rtl expression as appropriate. */
4705 ior_reg_cond (old, x)
4708 enum rtx_code x_code;
4712 /* We expect these conditions to be of the form (eq reg 0). */
4713 x_code = GET_CODE (x);
4714 if (GET_RTX_CLASS (x_code) != '<'
4715 || GET_CODE (x_reg = XEXP (x, 0)) != REG
4716 || XEXP (x, 1) != const0_rtx)
4719 /* Search the expression for an existing sub-expression of X_REG. */
4720 for (c = old; c ; c = XEXP (c, 1))
4722 rtx y = XEXP (c, 0);
4723 if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4725 /* If we find X already present in OLD, we need do nothing. */
4726 if (GET_CODE (y) == x_code)
4729 /* If we find X being a compliment of a condition in OLD,
4730 then the entire condition is true. */
4731 if (GET_CODE (y) == reverse_condition (x_code))
4736 /* Otherwise just add to the chain. */
4737 return alloc_EXPR_LIST (0, x, old);
4744 enum rtx_code x_code;
4747 /* We expect these conditions to be of the form (eq reg 0). */
4748 x_code = GET_CODE (x);
4749 if (GET_RTX_CLASS (x_code) != '<'
4750 || GET_CODE (x_reg = XEXP (x, 0)) != REG
4751 || XEXP (x, 1) != const0_rtx)
4754 return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4755 VOIDmode, x_reg, const0_rtx),
4760 nand_reg_cond (old, x)
4763 enum rtx_code x_code;
4767 /* We expect these conditions to be of the form (eq reg 0). */
4768 x_code = GET_CODE (x);
4769 if (GET_RTX_CLASS (x_code) != '<'
4770 || GET_CODE (x_reg = XEXP (x, 0)) != REG
4771 || XEXP (x, 1) != const0_rtx)
4774 /* Search the expression for an existing sub-expression of X_REG. */
4776 for (c = *(prev = &old); c ; c = *(prev = &XEXP (c, 1)))
4778 rtx y = XEXP (c, 0);
4779 if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4781 /* If we find X already present in OLD, then we need to
4783 if (GET_CODE (y) == x_code)
4785 *prev = XEXP (c, 1);
4786 free_EXPR_LIST_node (c);
4787 return old ? old : const0_rtx;
4790 /* If we find X being a compliment of a condition in OLD,
4791 then we need do nothing. */
4792 if (GET_CODE (y) == reverse_condition (x_code))
4797 /* Otherwise, by implication, the register in question is now live for
4798 the inverse of the condition X. */
4799 return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4800 VOIDmode, x_reg, const0_rtx),
4803 #endif /* HAVE_conditional_execution */
4807 /* Try to substitute the auto-inc expression INC as the address inside
4808 MEM which occurs in INSN. Currently, the address of MEM is an expression
4809 involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
4810 that has a single set whose source is a PLUS of INCR_REG and something
4814 attempt_auto_inc (pbi, inc, insn, mem, incr, incr_reg)
4815 struct propagate_block_info *pbi;
4816 rtx inc, insn, mem, incr, incr_reg;
4818 int regno = REGNO (incr_reg);
4819 rtx set = single_set (incr);
4820 rtx q = SET_DEST (set);
4821 rtx y = SET_SRC (set);
4822 int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
4824 /* Make sure this reg appears only once in this insn. */
4825 if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
4828 if (dead_or_set_p (incr, incr_reg)
4829 /* Mustn't autoinc an eliminable register. */
4830 && (regno >= FIRST_PSEUDO_REGISTER
4831 || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
4833 /* This is the simple case. Try to make the auto-inc. If
4834 we can't, we are done. Otherwise, we will do any
4835 needed updates below. */
4836 if (! validate_change (insn, &XEXP (mem, 0), inc, 0))
4839 else if (GET_CODE (q) == REG
4840 /* PREV_INSN used here to check the semi-open interval
4842 && ! reg_used_between_p (q, PREV_INSN (insn), incr)
4843 /* We must also check for sets of q as q may be
4844 a call clobbered hard register and there may
4845 be a call between PREV_INSN (insn) and incr. */
4846 && ! reg_set_between_p (q, PREV_INSN (insn), incr))
4848 /* We have *p followed sometime later by q = p+size.
4849 Both p and q must be live afterward,
4850 and q is not used between INSN and its assignment.
4851 Change it to q = p, ...*q..., q = q+size.
4852 Then fall into the usual case. */
4857 emit_move_insn (q, incr_reg);
4858 insns = get_insns ();
4861 if (basic_block_for_insn)
4862 for (temp = insns; temp; temp = NEXT_INSN (temp))
4863 set_block_for_insn (temp, pbi->bb);
4865 /* If we can't make the auto-inc, or can't make the
4866 replacement into Y, exit. There's no point in making
4867 the change below if we can't do the auto-inc and doing
4868 so is not correct in the pre-inc case. */
4871 validate_change (insn, &XEXP (mem, 0), inc, 1);
4872 validate_change (incr, &XEXP (y, opnum), q, 1);
4873 if (! apply_change_group ())
4876 /* We now know we'll be doing this change, so emit the
4877 new insn(s) and do the updates. */
4878 emit_insns_before (insns, insn);
4880 if (pbi->bb->head == insn)
4881 pbi->bb->head = insns;
4883 /* INCR will become a NOTE and INSN won't contain a
4884 use of INCR_REG. If a use of INCR_REG was just placed in
4885 the insn before INSN, make that the next use.
4886 Otherwise, invalidate it. */
4887 if (GET_CODE (PREV_INSN (insn)) == INSN
4888 && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
4889 && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg)
4890 pbi->reg_next_use[regno] = PREV_INSN (insn);
4892 pbi->reg_next_use[regno] = 0;
4897 /* REGNO is now used in INCR which is below INSN, but
4898 it previously wasn't live here. If we don't mark
4899 it as live, we'll put a REG_DEAD note for it
4900 on this insn, which is incorrect. */
4901 SET_REGNO_REG_SET (pbi->reg_live, regno);
4903 /* If there are any calls between INSN and INCR, show
4904 that REGNO now crosses them. */
4905 for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
4906 if (GET_CODE (temp) == CALL_INSN)
4907 REG_N_CALLS_CROSSED (regno)++;
4912 /* If we haven't returned, it means we were able to make the
4913 auto-inc, so update the status. First, record that this insn
4914 has an implicit side effect. */
4917 = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn));
4919 /* Modify the old increment-insn to simply copy
4920 the already-incremented value of our register. */
4921 if (! validate_change (incr, &SET_SRC (set), incr_reg, 0))
4924 /* If that makes it a no-op (copying the register into itself) delete
4925 it so it won't appear to be a "use" and a "set" of this
4927 if (REGNO (SET_DEST (set)) == REGNO (incr_reg))
4929 /* If the original source was dead, it's dead now. */
4932 while (note = find_reg_note (incr, REG_DEAD, NULL_RTX))
4934 remove_note (incr, note);
4935 if (XEXP (note, 0) != incr_reg)
4936 CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
4939 PUT_CODE (incr, NOTE);
4940 NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
4941 NOTE_SOURCE_FILE (incr) = 0;
4944 if (regno >= FIRST_PSEUDO_REGISTER)
4946 /* Count an extra reference to the reg. When a reg is
4947 incremented, spilling it is worse, so we want to make
4948 that less likely. */
4949 REG_N_REFS (regno) += (optimize_size ? 1 : pbi->bb->loop_depth + 1);
4951 /* Count the increment as a setting of the register,
4952 even though it isn't a SET in rtl. */
4953 REG_N_SETS (regno)++;
4957 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
4961 find_auto_inc (pbi, x, insn)
4962 struct propagate_block_info *pbi;
4966 rtx addr = XEXP (x, 0);
4967 HOST_WIDE_INT offset = 0;
4968 rtx set, y, incr, inc_val;
4970 int size = GET_MODE_SIZE (GET_MODE (x));
4972 if (GET_CODE (insn) == JUMP_INSN)
4975 /* Here we detect use of an index register which might be good for
4976 postincrement, postdecrement, preincrement, or predecrement. */
4978 if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
4979 offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
4981 if (GET_CODE (addr) != REG)
4984 regno = REGNO (addr);
4986 /* Is the next use an increment that might make auto-increment? */
4987 incr = pbi->reg_next_use[regno];
4988 if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
4990 set = single_set (incr);
4991 if (set == 0 || GET_CODE (set) != SET)
4995 if (GET_CODE (y) != PLUS)
4998 if (REGNO (XEXP (y, 0)) == REGNO (addr))
4999 inc_val = XEXP (y, 1);
5000 else if (REGNO (XEXP (y, 1)) == REGNO (addr))
5001 inc_val = XEXP (y, 0);
5005 if (GET_CODE (inc_val) == CONST_INT)
5007 if (HAVE_POST_INCREMENT
5008 && (INTVAL (inc_val) == size && offset == 0))
5009 attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x,
5011 else if (HAVE_POST_DECREMENT
5012 && (INTVAL (inc_val) == - size && offset == 0))
5013 attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x,
5015 else if (HAVE_PRE_INCREMENT
5016 && (INTVAL (inc_val) == size && offset == size))
5017 attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x,
5019 else if (HAVE_PRE_DECREMENT
5020 && (INTVAL (inc_val) == - size && offset == - size))
5021 attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x,
5023 else if (HAVE_POST_MODIFY_DISP && offset == 0)
5024 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
5025 gen_rtx_PLUS (Pmode,
5028 insn, x, incr, addr);
5030 else if (GET_CODE (inc_val) == REG
5031 && ! reg_set_between_p (inc_val, PREV_INSN (insn),
5035 if (HAVE_POST_MODIFY_REG && offset == 0)
5036 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
5037 gen_rtx_PLUS (Pmode,
5040 insn, x, incr, addr);
5044 #endif /* AUTO_INC_DEC */
5047 mark_used_reg (pbi, reg, cond, insn)
5048 struct propagate_block_info *pbi;
5050 rtx cond ATTRIBUTE_UNUSED;
5053 int regno = REGNO (reg);
5054 int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
5055 int some_was_dead = ! some_was_live;
5059 /* A hard reg in a wide mode may really be multiple registers.
5060 If so, mark all of them just like the first. */
5061 if (regno < FIRST_PSEUDO_REGISTER)
5063 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5066 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
5067 some_was_live |= needed_regno;
5068 some_was_dead |= ! needed_regno;
5072 if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
5074 /* Record where each reg is used, so when the reg is set we know
5075 the next insn that uses it. */
5076 pbi->reg_next_use[regno] = insn;
5079 if (pbi->flags & PROP_REG_INFO)
5081 if (regno < FIRST_PSEUDO_REGISTER)
5083 /* If this is a register we are going to try to eliminate,
5084 don't mark it live here. If we are successful in
5085 eliminating it, it need not be live unless it is used for
5086 pseudos, in which case it will have been set live when it
5087 was allocated to the pseudos. If the register will not
5088 be eliminated, reload will set it live at that point.
5090 Otherwise, record that this function uses this register. */
5091 /* ??? The PPC backend tries to "eliminate" on the pic
5092 register to itself. This should be fixed. In the mean
5093 time, hack around it. */
5095 if (! (TEST_HARD_REG_BIT (elim_reg_set, regno)
5096 && (regno == FRAME_POINTER_REGNUM
5097 || regno == ARG_POINTER_REGNUM)))
5099 int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5101 regs_ever_live[regno + --n] = 1;
5107 /* Keep track of which basic block each reg appears in. */
5109 register int blocknum = pbi->bb->index;
5110 if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
5111 REG_BASIC_BLOCK (regno) = blocknum;
5112 else if (REG_BASIC_BLOCK (regno) != blocknum)
5113 REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
5115 /* Count (weighted) number of uses of each reg. */
5116 REG_N_REFS (regno) += (optimize_size ? 1
5117 : pbi->bb->loop_depth + 1);
5121 /* Find out if any of the register was set this insn. */
5122 some_not_set = ! REGNO_REG_SET_P (pbi->new_set, regno);
5123 if (regno < FIRST_PSEUDO_REGISTER)
5125 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5127 some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, regno + n);
5130 /* Record and count the insns in which a reg dies. If it is used in
5131 this insn and was dead below the insn then it dies in this insn.
5132 If it was set in this insn, we do not make a REG_DEAD note;
5133 likewise if we already made such a note. */
5134 if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
5138 /* Check for the case where the register dying partially
5139 overlaps the register set by this insn. */
5140 if (regno < FIRST_PSEUDO_REGISTER
5141 && HARD_REGNO_NREGS (regno, GET_MODE (reg)) > 1)
5143 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5145 some_was_live |= REGNO_REG_SET_P (pbi->new_set, regno + n);
5148 /* If none of the words in X is needed, make a REG_DEAD note.
5149 Otherwise, we must make partial REG_DEAD notes. */
5150 if (! some_was_live)
5152 if ((pbi->flags & PROP_DEATH_NOTES)
5153 && ! find_regno_note (insn, REG_DEAD, regno))
5155 = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
5157 if (pbi->flags & PROP_REG_INFO)
5158 REG_N_DEATHS (regno)++;
5162 /* Don't make a REG_DEAD note for a part of a register
5163 that is set in the insn. */
5165 n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
5166 for (; n >= regno; n--)
5167 if (! REGNO_REG_SET_P (pbi->reg_live, n)
5168 && ! dead_or_set_regno_p (insn, n))
5170 = alloc_EXPR_LIST (REG_DEAD,
5171 gen_rtx_REG (reg_raw_mode[n], n),
5176 SET_REGNO_REG_SET (pbi->reg_live, regno);
5177 if (regno < FIRST_PSEUDO_REGISTER)
5179 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5181 SET_REGNO_REG_SET (pbi->reg_live, regno + n);
5184 #ifdef HAVE_conditional_execution
5185 /* If this is a conditional use, record that fact. If it is later
5186 conditionally set, we'll know to kill the register. */
5187 if (cond != NULL_RTX)
5189 splay_tree_node node;
5190 struct reg_cond_life_info *rcli;
5195 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5198 /* The register was unconditionally live previously.
5199 No need to do anything. */
5203 /* The register was conditionally live previously.
5204 Subtract the new life cond from the old death cond. */
5205 rcli = (struct reg_cond_life_info *) node->value;
5206 ncond = rcli->condition;
5207 ncond = nand_reg_cond (ncond, cond);
5209 /* If the register is now unconditionally live, remove the
5210 entry in the splay_tree. */
5211 if (ncond == const0_rtx)
5213 rcli->condition = NULL_RTX;
5214 splay_tree_remove (pbi->reg_cond_dead, regno);
5217 rcli->condition = ncond;
5222 /* The register was not previously live at all. Record
5223 the condition under which it is still dead. */
5224 rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
5225 rcli->condition = not_reg_cond (cond);
5226 splay_tree_insert (pbi->reg_cond_dead, regno,
5227 (splay_tree_value) rcli);
5230 else if (some_was_live)
5232 splay_tree_node node;
5233 struct reg_cond_life_info *rcli;
5235 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5238 /* The register was conditionally live previously, but is now
5239 unconditionally so. Remove it from the conditionally dead
5240 list, so that a conditional set won't cause us to think
5242 rcli = (struct reg_cond_life_info *) node->value;
5243 rcli->condition = NULL_RTX;
5244 splay_tree_remove (pbi->reg_cond_dead, regno);
5251 /* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
5252 This is done assuming the registers needed from X are those that
5253 have 1-bits in PBI->REG_LIVE.
5255 INSN is the containing instruction. If INSN is dead, this function
5259 mark_used_regs (pbi, x, cond, insn)
5260 struct propagate_block_info *pbi;
5263 register RTX_CODE code;
5265 int flags = pbi->flags;
5268 code = GET_CODE (x);
5288 /* If we are clobbering a MEM, mark any registers inside the address
5290 if (GET_CODE (XEXP (x, 0)) == MEM)
5291 mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
5295 /* Don't bother watching stores to mems if this is not the
5296 final pass. We'll not be deleting dead stores this round. */
5297 if (flags & PROP_SCAN_DEAD_CODE)
5299 /* Invalidate the data for the last MEM stored, but only if MEM is
5300 something that can be stored into. */
5301 if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
5302 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
5303 ; /* needn't clear the memory set list */
5306 rtx temp = pbi->mem_set_list;
5307 rtx prev = NULL_RTX;
5312 next = XEXP (temp, 1);
5313 if (anti_dependence (XEXP (temp, 0), x))
5315 /* Splice temp out of the list. */
5317 XEXP (prev, 1) = next;
5319 pbi->mem_set_list = next;
5320 free_EXPR_LIST_node (temp);
5328 /* If the memory reference had embedded side effects (autoincrement
5329 address modes. Then we may need to kill some entries on the
5332 invalidate_mems_from_autoinc (pbi, insn);
5336 if (flags & PROP_AUTOINC)
5337 find_auto_inc (pbi, x, insn);
5342 #ifdef CLASS_CANNOT_CHANGE_MODE
5343 if (GET_CODE (SUBREG_REG (x)) == REG
5344 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
5345 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (x),
5346 GET_MODE (SUBREG_REG (x))))
5347 REG_CHANGES_MODE (REGNO (SUBREG_REG (x))) = 1;
5350 /* While we're here, optimize this case. */
5352 if (GET_CODE (x) != REG)
5357 /* See a register other than being set => mark it as needed. */
5358 mark_used_reg (pbi, x, cond, insn);
5363 register rtx testreg = SET_DEST (x);
5366 /* If storing into MEM, don't show it as being used. But do
5367 show the address as being used. */
5368 if (GET_CODE (testreg) == MEM)
5371 if (flags & PROP_AUTOINC)
5372 find_auto_inc (pbi, testreg, insn);
5374 mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
5375 mark_used_regs (pbi, SET_SRC (x), cond, insn);
5379 /* Storing in STRICT_LOW_PART is like storing in a reg
5380 in that this SET might be dead, so ignore it in TESTREG.
5381 but in some other ways it is like using the reg.
5383 Storing in a SUBREG or a bit field is like storing the entire
5384 register in that if the register's value is not used
5385 then this SET is not needed. */
5386 while (GET_CODE (testreg) == STRICT_LOW_PART
5387 || GET_CODE (testreg) == ZERO_EXTRACT
5388 || GET_CODE (testreg) == SIGN_EXTRACT
5389 || GET_CODE (testreg) == SUBREG)
5391 #ifdef CLASS_CANNOT_CHANGE_MODE
5392 if (GET_CODE (testreg) == SUBREG
5393 && GET_CODE (SUBREG_REG (testreg)) == REG
5394 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
5395 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (SUBREG_REG (testreg)),
5396 GET_MODE (testreg)))
5397 REG_CHANGES_MODE (REGNO (SUBREG_REG (testreg))) = 1;
5400 /* Modifying a single register in an alternate mode
5401 does not use any of the old value. But these other
5402 ways of storing in a register do use the old value. */
5403 if (GET_CODE (testreg) == SUBREG
5404 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
5409 testreg = XEXP (testreg, 0);
5412 /* If this is a store into a register, recursively scan the
5413 value being stored. */
5415 if ((GET_CODE (testreg) == PARALLEL
5416 && GET_MODE (testreg) == BLKmode)
5417 || (GET_CODE (testreg) == REG
5418 && (regno = REGNO (testreg),
5419 ! (regno == FRAME_POINTER_REGNUM
5420 && (! reload_completed || frame_pointer_needed)))
5421 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
5422 && ! (regno == HARD_FRAME_POINTER_REGNUM
5423 && (! reload_completed || frame_pointer_needed))
5425 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
5426 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
5431 mark_used_regs (pbi, SET_DEST (x), cond, insn);
5432 mark_used_regs (pbi, SET_SRC (x), cond, insn);
5439 case UNSPEC_VOLATILE:
5443 /* Traditional and volatile asm instructions must be considered to use
5444 and clobber all hard registers, all pseudo-registers and all of
5445 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
5447 Consider for instance a volatile asm that changes the fpu rounding
5448 mode. An insn should not be moved across this even if it only uses
5449 pseudo-regs because it might give an incorrectly rounded result.
5451 ?!? Unfortunately, marking all hard registers as live causes massive
5452 problems for the register allocator and marking all pseudos as live
5453 creates mountains of uninitialized variable warnings.
5455 So for now, just clear the memory set list and mark any regs
5456 we can find in ASM_OPERANDS as used. */
5457 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
5458 free_EXPR_LIST_list (&pbi->mem_set_list);
5460 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
5461 We can not just fall through here since then we would be confused
5462 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
5463 traditional asms unlike their normal usage. */
5464 if (code == ASM_OPERANDS)
5468 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
5469 mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
5475 if (cond != NULL_RTX)
5478 mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
5480 cond = COND_EXEC_TEST (x);
5481 x = COND_EXEC_CODE (x);
5485 /* We _do_not_ want to scan operands of phi nodes. Operands of
5486 a phi function are evaluated only when control reaches this
5487 block along a particular edge. Therefore, regs that appear
5488 as arguments to phi should not be added to the global live at
5496 /* Recursively scan the operands of this expression. */
5499 register const char *fmt = GET_RTX_FORMAT (code);
5502 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5506 /* Tail recursive case: save a function call level. */
5512 mark_used_regs (pbi, XEXP (x, i), cond, insn);
5514 else if (fmt[i] == 'E')
5517 for (j = 0; j < XVECLEN (x, i); j++)
5518 mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
5527 try_pre_increment_1 (pbi, insn)
5528 struct propagate_block_info *pbi;
5531 /* Find the next use of this reg. If in same basic block,
5532 make it do pre-increment or pre-decrement if appropriate. */
5533 rtx x = single_set (insn);
5534 HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
5535 * INTVAL (XEXP (SET_SRC (x), 1)));
5536 int regno = REGNO (SET_DEST (x));
5537 rtx y = pbi->reg_next_use[regno];
5539 && BLOCK_NUM (y) == BLOCK_NUM (insn)
5540 /* Don't do this if the reg dies, or gets set in y; a standard addressing
5541 mode would be better. */
5542 && ! dead_or_set_p (y, SET_DEST (x))
5543 && try_pre_increment (y, SET_DEST (x), amount))
5545 /* We have found a suitable auto-increment
5546 and already changed insn Y to do it.
5547 So flush this increment-instruction. */
5548 PUT_CODE (insn, NOTE);
5549 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5550 NOTE_SOURCE_FILE (insn) = 0;
5551 /* Count a reference to this reg for the increment
5552 insn we are deleting. When a reg is incremented.
5553 spilling it is worse, so we want to make that
5555 if (regno >= FIRST_PSEUDO_REGISTER)
5557 REG_N_REFS (regno) += (optimize_size ? 1
5558 : pbi->bb->loop_depth + 1);
5559 REG_N_SETS (regno)++;
5566 /* Try to change INSN so that it does pre-increment or pre-decrement
5567 addressing on register REG in order to add AMOUNT to REG.
5568 AMOUNT is negative for pre-decrement.
5569 Returns 1 if the change could be made.
5570 This checks all about the validity of the result of modifying INSN. */
5573 try_pre_increment (insn, reg, amount)
5575 HOST_WIDE_INT amount;
5579 /* Nonzero if we can try to make a pre-increment or pre-decrement.
5580 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
5582 /* Nonzero if we can try to make a post-increment or post-decrement.
5583 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
5584 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
5585 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
5588 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
5591 /* From the sign of increment, see which possibilities are conceivable
5592 on this target machine. */
5593 if (HAVE_PRE_INCREMENT && amount > 0)
5595 if (HAVE_POST_INCREMENT && amount > 0)
5598 if (HAVE_PRE_DECREMENT && amount < 0)
5600 if (HAVE_POST_DECREMENT && amount < 0)
5603 if (! (pre_ok || post_ok))
5606 /* It is not safe to add a side effect to a jump insn
5607 because if the incremented register is spilled and must be reloaded
5608 there would be no way to store the incremented value back in memory. */
5610 if (GET_CODE (insn) == JUMP_INSN)
5615 use = find_use_as_address (PATTERN (insn), reg, 0);
5616 if (post_ok && (use == 0 || use == (rtx) 1))
5618 use = find_use_as_address (PATTERN (insn), reg, -amount);
5622 if (use == 0 || use == (rtx) 1)
5625 if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
5628 /* See if this combination of instruction and addressing mode exists. */
5629 if (! validate_change (insn, &XEXP (use, 0),
5630 gen_rtx_fmt_e (amount > 0
5631 ? (do_post ? POST_INC : PRE_INC)
5632 : (do_post ? POST_DEC : PRE_DEC),
5636 /* Record that this insn now has an implicit side effect on X. */
5637 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
5641 #endif /* AUTO_INC_DEC */
5643 /* Find the place in the rtx X where REG is used as a memory address.
5644 Return the MEM rtx that so uses it.
5645 If PLUSCONST is nonzero, search instead for a memory address equivalent to
5646 (plus REG (const_int PLUSCONST)).
5648 If such an address does not appear, return 0.
5649 If REG appears more than once, or is used other than in such an address,
5653 find_use_as_address (x, reg, plusconst)
5656 HOST_WIDE_INT plusconst;
5658 enum rtx_code code = GET_CODE (x);
5659 const char *fmt = GET_RTX_FORMAT (code);
5661 register rtx value = 0;
5664 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
5667 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
5668 && XEXP (XEXP (x, 0), 0) == reg
5669 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
5670 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
5673 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
5675 /* If REG occurs inside a MEM used in a bit-field reference,
5676 that is unacceptable. */
5677 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
5678 return (rtx) (HOST_WIDE_INT) 1;
5682 return (rtx) (HOST_WIDE_INT) 1;
5684 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5688 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
5692 return (rtx) (HOST_WIDE_INT) 1;
5694 else if (fmt[i] == 'E')
5697 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5699 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
5703 return (rtx) (HOST_WIDE_INT) 1;
5711 /* Write information about registers and basic blocks into FILE.
5712 This is part of making a debugging dump. */
5715 dump_regset (r, outf)
5722 fputs (" (nil)", outf);
5726 EXECUTE_IF_SET_IN_REG_SET (r, 0, i,
5728 fprintf (outf, " %d", i);
5729 if (i < FIRST_PSEUDO_REGISTER)
5730 fprintf (outf, " [%s]",
5739 dump_regset (r, stderr);
5740 putc ('\n', stderr);
5744 dump_flow_info (file)
5748 static const char * const reg_class_names[] = REG_CLASS_NAMES;
5750 fprintf (file, "%d registers.\n", max_regno);
5751 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
5754 enum reg_class class, altclass;
5755 fprintf (file, "\nRegister %d used %d times across %d insns",
5756 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
5757 if (REG_BASIC_BLOCK (i) >= 0)
5758 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
5760 fprintf (file, "; set %d time%s", REG_N_SETS (i),
5761 (REG_N_SETS (i) == 1) ? "" : "s");
5762 if (REG_USERVAR_P (regno_reg_rtx[i]))
5763 fprintf (file, "; user var");
5764 if (REG_N_DEATHS (i) != 1)
5765 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
5766 if (REG_N_CALLS_CROSSED (i) == 1)
5767 fprintf (file, "; crosses 1 call");
5768 else if (REG_N_CALLS_CROSSED (i))
5769 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
5770 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
5771 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
5772 class = reg_preferred_class (i);
5773 altclass = reg_alternate_class (i);
5774 if (class != GENERAL_REGS || altclass != ALL_REGS)
5776 if (altclass == ALL_REGS || class == ALL_REGS)
5777 fprintf (file, "; pref %s", reg_class_names[(int) class]);
5778 else if (altclass == NO_REGS)
5779 fprintf (file, "; %s or none", reg_class_names[(int) class]);
5781 fprintf (file, "; pref %s, else %s",
5782 reg_class_names[(int) class],
5783 reg_class_names[(int) altclass]);
5785 if (REGNO_POINTER_FLAG (i))
5786 fprintf (file, "; pointer");
5787 fprintf (file, ".\n");
5790 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
5791 for (i = 0; i < n_basic_blocks; i++)
5793 register basic_block bb = BASIC_BLOCK (i);
5796 fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count %d.\n",
5797 i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth, bb->count);
5799 fprintf (file, "Predecessors: ");
5800 for (e = bb->pred; e ; e = e->pred_next)
5801 dump_edge_info (file, e, 0);
5803 fprintf (file, "\nSuccessors: ");
5804 for (e = bb->succ; e ; e = e->succ_next)
5805 dump_edge_info (file, e, 1);
5807 fprintf (file, "\nRegisters live at start:");
5808 dump_regset (bb->global_live_at_start, file);
5810 fprintf (file, "\nRegisters live at end:");
5811 dump_regset (bb->global_live_at_end, file);
5822 dump_flow_info (stderr);
5826 dump_edge_info (file, e, do_succ)
5831 basic_block side = (do_succ ? e->dest : e->src);
5833 if (side == ENTRY_BLOCK_PTR)
5834 fputs (" ENTRY", file);
5835 else if (side == EXIT_BLOCK_PTR)
5836 fputs (" EXIT", file);
5838 fprintf (file, " %d", side->index);
5841 fprintf (file, " count:%d", e->count);
5845 static const char * const bitnames[] = {
5846 "fallthru", "crit", "ab", "abcall", "eh", "fake"
5849 int i, flags = e->flags;
5853 for (i = 0; flags; i++)
5854 if (flags & (1 << i))
5860 if (i < (int)(sizeof (bitnames) / sizeof (*bitnames)))
5861 fputs (bitnames[i], file);
5863 fprintf (file, "%d", i);
5871 /* Print out one basic block with live information at start and end. */
5881 fprintf (outf, ";; Basic block %d, loop depth %d, count %d",
5882 bb->index, bb->loop_depth, bb->count);
5883 if (bb->eh_beg != -1 || bb->eh_end != -1)
5884 fprintf (outf, ", eh regions %d/%d", bb->eh_beg, bb->eh_end);
5887 fputs (";; Predecessors: ", outf);
5888 for (e = bb->pred; e ; e = e->pred_next)
5889 dump_edge_info (outf, e, 0);
5892 fputs (";; Registers live at start:", outf);
5893 dump_regset (bb->global_live_at_start, outf);
5896 for (insn = bb->head, last = NEXT_INSN (bb->end);
5898 insn = NEXT_INSN (insn))
5899 print_rtl_single (outf, insn);
5901 fputs (";; Registers live at end:", outf);
5902 dump_regset (bb->global_live_at_end, outf);
5905 fputs (";; Successors: ", outf);
5906 for (e = bb->succ; e; e = e->succ_next)
5907 dump_edge_info (outf, e, 1);
5915 dump_bb (bb, stderr);
5922 dump_bb (BASIC_BLOCK(n), stderr);
5925 /* Like print_rtl, but also print out live information for the start of each
5929 print_rtl_with_bb (outf, rtx_first)
5933 register rtx tmp_rtx;
5936 fprintf (outf, "(nil)\n");
5940 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
5941 int max_uid = get_max_uid ();
5942 basic_block *start = (basic_block *)
5943 xcalloc (max_uid, sizeof (basic_block));
5944 basic_block *end = (basic_block *)
5945 xcalloc (max_uid, sizeof (basic_block));
5946 enum bb_state *in_bb_p = (enum bb_state *)
5947 xcalloc (max_uid, sizeof (enum bb_state));
5949 for (i = n_basic_blocks - 1; i >= 0; i--)
5951 basic_block bb = BASIC_BLOCK (i);
5954 start[INSN_UID (bb->head)] = bb;
5955 end[INSN_UID (bb->end)] = bb;
5956 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
5958 enum bb_state state = IN_MULTIPLE_BB;
5959 if (in_bb_p[INSN_UID(x)] == NOT_IN_BB)
5961 in_bb_p[INSN_UID(x)] = state;
5968 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
5973 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
5975 fprintf (outf, ";; Start of basic block %d, registers live:",
5977 dump_regset (bb->global_live_at_start, outf);
5981 if (in_bb_p[INSN_UID(tmp_rtx)] == NOT_IN_BB
5982 && GET_CODE (tmp_rtx) != NOTE
5983 && GET_CODE (tmp_rtx) != BARRIER)
5984 fprintf (outf, ";; Insn is not within a basic block\n");
5985 else if (in_bb_p[INSN_UID(tmp_rtx)] == IN_MULTIPLE_BB)
5986 fprintf (outf, ";; Insn is in multiple basic blocks\n");
5988 did_output = print_rtl_single (outf, tmp_rtx);
5990 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
5992 fprintf (outf, ";; End of basic block %d, registers live:\n",
5994 dump_regset (bb->global_live_at_end, outf);
6007 if (current_function_epilogue_delay_list != 0)
6009 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
6010 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
6011 tmp_rtx = XEXP (tmp_rtx, 1))
6012 print_rtl_single (outf, XEXP (tmp_rtx, 0));
6016 /* Compute dominator relationships using new flow graph structures. */
6018 compute_flow_dominators (dominators, post_dominators)
6019 sbitmap *dominators;
6020 sbitmap *post_dominators;
6023 sbitmap *temp_bitmap;
6025 basic_block *worklist, *workend, *qin, *qout;
6028 /* Allocate a worklist array/queue. Entries are only added to the
6029 list if they were not already on the list. So the size is
6030 bounded by the number of basic blocks. */
6031 worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
6032 workend = &worklist[n_basic_blocks];
6034 temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6035 sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
6039 /* The optimistic setting of dominators requires us to put every
6040 block on the work list initially. */
6041 qin = qout = worklist;
6042 for (bb = 0; bb < n_basic_blocks; bb++)
6044 *qin++ = BASIC_BLOCK (bb);
6045 BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6047 qlen = n_basic_blocks;
6050 /* We want a maximal solution, so initially assume everything dominates
6052 sbitmap_vector_ones (dominators, n_basic_blocks);
6054 /* Mark successors of the entry block so we can identify them below. */
6055 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6056 e->dest->aux = ENTRY_BLOCK_PTR;
6058 /* Iterate until the worklist is empty. */
6061 /* Take the first entry off the worklist. */
6062 basic_block b = *qout++;
6063 if (qout >= workend)
6069 /* Compute the intersection of the dominators of all the
6072 If one of the predecessor blocks is the ENTRY block, then the
6073 intersection of the dominators of the predecessor blocks is
6074 defined as the null set. We can identify such blocks by the
6075 special value in the AUX field in the block structure. */
6076 if (b->aux == ENTRY_BLOCK_PTR)
6078 /* Do not clear the aux field for blocks which are
6079 successors of the ENTRY block. That way we we never
6080 add them to the worklist again.
6082 The intersect of dominators of the preds of this block is
6083 defined as the null set. */
6084 sbitmap_zero (temp_bitmap[bb]);
6088 /* Clear the aux field of this block so it can be added to
6089 the worklist again if necessary. */
6091 sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
6094 /* Make sure each block always dominates itself. */
6095 SET_BIT (temp_bitmap[bb], bb);
6097 /* If the out state of this block changed, then we need to
6098 add the successors of this block to the worklist if they
6099 are not already on the worklist. */
6100 if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
6102 for (e = b->succ; e; e = e->succ_next)
6104 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
6118 if (post_dominators)
6120 /* The optimistic setting of dominators requires us to put every
6121 block on the work list initially. */
6122 qin = qout = worklist;
6123 for (bb = 0; bb < n_basic_blocks; bb++)
6125 *qin++ = BASIC_BLOCK (bb);
6126 BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6128 qlen = n_basic_blocks;
6131 /* We want a maximal solution, so initially assume everything post
6132 dominates everything else. */
6133 sbitmap_vector_ones (post_dominators, n_basic_blocks);
6135 /* Mark predecessors of the exit block so we can identify them below. */
6136 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
6137 e->src->aux = EXIT_BLOCK_PTR;
6139 /* Iterate until the worklist is empty. */
6142 /* Take the first entry off the worklist. */
6143 basic_block b = *qout++;
6144 if (qout >= workend)
6150 /* Compute the intersection of the post dominators of all the
6153 If one of the successor blocks is the EXIT block, then the
6154 intersection of the dominators of the successor blocks is
6155 defined as the null set. We can identify such blocks by the
6156 special value in the AUX field in the block structure. */
6157 if (b->aux == EXIT_BLOCK_PTR)
6159 /* Do not clear the aux field for blocks which are
6160 predecessors of the EXIT block. That way we we never
6161 add them to the worklist again.
6163 The intersect of dominators of the succs of this block is
6164 defined as the null set. */
6165 sbitmap_zero (temp_bitmap[bb]);
6169 /* Clear the aux field of this block so it can be added to
6170 the worklist again if necessary. */
6172 sbitmap_intersection_of_succs (temp_bitmap[bb],
6173 post_dominators, bb);
6176 /* Make sure each block always post dominates itself. */
6177 SET_BIT (temp_bitmap[bb], bb);
6179 /* If the out state of this block changed, then we need to
6180 add the successors of this block to the worklist if they
6181 are not already on the worklist. */
6182 if (sbitmap_a_and_b (post_dominators[bb],
6183 post_dominators[bb],
6186 for (e = b->pred; e; e = e->pred_next)
6188 if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
6206 /* Given DOMINATORS, compute the immediate dominators into IDOM. If a
6207 block dominates only itself, its entry remains as INVALID_BLOCK. */
6210 compute_immediate_dominators (idom, dominators)
6212 sbitmap *dominators;
6217 tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6219 /* Begin with tmp(n) = dom(n) - { n }. */
6220 for (b = n_basic_blocks; --b >= 0; )
6222 sbitmap_copy (tmp[b], dominators[b]);
6223 RESET_BIT (tmp[b], b);
6226 /* Subtract out all of our dominator's dominators. */
6227 for (b = n_basic_blocks; --b >= 0; )
6229 sbitmap tmp_b = tmp[b];
6232 for (s = n_basic_blocks; --s >= 0; )
6233 if (TEST_BIT (tmp_b, s))
6234 sbitmap_difference (tmp_b, tmp_b, tmp[s]);
6237 /* Find the one bit set in the bitmap and put it in the output array. */
6238 for (b = n_basic_blocks; --b >= 0; )
6241 EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
6244 sbitmap_vector_free (tmp);
6247 /* Given POSTDOMINATORS, compute the immediate postdominators into
6248 IDOM. If a block is only dominated by itself, its entry remains as
6252 compute_immediate_postdominators (idom, postdominators)
6254 sbitmap *postdominators;
6256 compute_immediate_dominators (idom, postdominators);
6260 /* Recompute register set/reference counts immediately prior to register
6263 This avoids problems with set/reference counts changing to/from values
6264 which have special meanings to the register allocators.
6266 Additionally, the reference counts are the primary component used by the
6267 register allocators to prioritize pseudos for allocation to hard regs.
6268 More accurate reference counts generally lead to better register allocation.
6270 F is the first insn to be scanned.
6272 LOOP_STEP denotes how much loop_depth should be incremented per
6273 loop nesting level in order to increase the ref count more for
6274 references in a loop.
6276 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
6277 possibly other information which is used by the register allocators. */
6280 recompute_reg_usage (f, loop_step)
6281 rtx f ATTRIBUTE_UNUSED;
6282 int loop_step ATTRIBUTE_UNUSED;
6284 allocate_reg_life_data ();
6285 update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO);
6288 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
6289 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
6290 of the number of registers that died. */
6293 count_or_remove_death_notes (blocks, kill)
6299 for (i = n_basic_blocks - 1; i >= 0; --i)
6304 if (blocks && ! TEST_BIT (blocks, i))
6307 bb = BASIC_BLOCK (i);
6309 for (insn = bb->head; ; insn = NEXT_INSN (insn))
6311 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
6313 rtx *pprev = ®_NOTES (insn);
6318 switch (REG_NOTE_KIND (link))
6321 if (GET_CODE (XEXP (link, 0)) == REG)
6323 rtx reg = XEXP (link, 0);
6326 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
6329 n = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
6337 rtx next = XEXP (link, 1);
6338 free_EXPR_LIST_node (link);
6339 *pprev = link = next;
6345 pprev = &XEXP (link, 1);
6352 if (insn == bb->end)
6360 /* Record INSN's block as BB. */
6363 set_block_for_insn (insn, bb)
6367 size_t uid = INSN_UID (insn);
6368 if (uid >= basic_block_for_insn->num_elements)
6372 /* Add one-eighth the size so we don't keep calling xrealloc. */
6373 new_size = uid + (uid + 7) / 8;
6375 VARRAY_GROW (basic_block_for_insn, new_size);
6377 VARRAY_BB (basic_block_for_insn, uid) = bb;
6380 /* Record INSN's block number as BB. */
6381 /* ??? This has got to go. */
6384 set_block_num (insn, bb)
6388 set_block_for_insn (insn, BASIC_BLOCK (bb));
6391 /* Verify the CFG consistency. This function check some CFG invariants and
6392 aborts when something is wrong. Hope that this function will help to
6393 convert many optimization passes to preserve CFG consistent.
6395 Currently it does following checks:
6397 - test head/end pointers
6398 - overlapping of basic blocks
6399 - edge list corectness
6400 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
6401 - tails of basic blocks (ensure that boundary is necesary)
6402 - scans body of the basic block for JUMP_INSN, CODE_LABEL
6403 and NOTE_INSN_BASIC_BLOCK
6404 - check that all insns are in the basic blocks
6405 (except the switch handling code, barriers and notes)
6406 - check that all returns are followed by barriers
6408 In future it can be extended check a lot of other stuff as well
6409 (reachability of basic blocks, life information, etc. etc.). */
6414 const int max_uid = get_max_uid ();
6415 const rtx rtx_first = get_insns ();
6416 rtx last_head = get_last_insn ();
6417 basic_block *bb_info;
6419 int i, last_bb_num_seen, num_bb_notes, err = 0;
6421 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
6423 for (i = n_basic_blocks - 1; i >= 0; i--)
6425 basic_block bb = BASIC_BLOCK (i);
6426 rtx head = bb->head;
6429 /* Verify the end of the basic block is in the INSN chain. */
6430 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
6435 error ("End insn %d for block %d not found in the insn stream.",
6436 INSN_UID (end), bb->index);
6440 /* Work backwards from the end to the head of the basic block
6441 to verify the head is in the RTL chain. */
6442 for ( ; x != NULL_RTX; x = PREV_INSN (x))
6444 /* While walking over the insn chain, verify insns appear
6445 in only one basic block and initialize the BB_INFO array
6446 used by other passes. */
6447 if (bb_info[INSN_UID (x)] != NULL)
6449 error ("Insn %d is in multiple basic blocks (%d and %d)",
6450 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
6453 bb_info[INSN_UID (x)] = bb;
6460 error ("Head insn %d for block %d not found in the insn stream.",
6461 INSN_UID (head), bb->index);
6468 /* Now check the basic blocks (boundaries etc.) */
6469 for (i = n_basic_blocks - 1; i >= 0; i--)
6471 basic_block bb = BASIC_BLOCK (i);
6472 /* Check corectness of edge lists */
6480 fprintf (stderr, "verify_flow_info: Basic block %d succ edge is corrupted\n",
6482 fprintf (stderr, "Predecessor: ");
6483 dump_edge_info (stderr, e, 0);
6484 fprintf (stderr, "\nSuccessor: ");
6485 dump_edge_info (stderr, e, 1);
6489 if (e->dest != EXIT_BLOCK_PTR)
6491 edge e2 = e->dest->pred;
6492 while (e2 && e2 != e)
6496 error ("Basic block %i edge lists are corrupted", bb->index);
6508 error ("Basic block %d pred edge is corrupted", bb->index);
6509 fputs ("Predecessor: ", stderr);
6510 dump_edge_info (stderr, e, 0);
6511 fputs ("\nSuccessor: ", stderr);
6512 dump_edge_info (stderr, e, 1);
6513 fputc ('\n', stderr);
6516 if (e->src != ENTRY_BLOCK_PTR)
6518 edge e2 = e->src->succ;
6519 while (e2 && e2 != e)
6523 error ("Basic block %i edge lists are corrupted", bb->index);
6530 /* OK pointers are correct. Now check the header of basic
6531 block. It ought to contain optional CODE_LABEL followed
6532 by NOTE_BASIC_BLOCK. */
6534 if (GET_CODE (x) == CODE_LABEL)
6538 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
6544 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
6546 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
6553 /* Do checks for empty blocks here */
6560 if (NOTE_INSN_BASIC_BLOCK_P (x))
6562 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
6563 INSN_UID (x), bb->index);
6570 if (GET_CODE (x) == JUMP_INSN
6571 || GET_CODE (x) == CODE_LABEL
6572 || GET_CODE (x) == BARRIER)
6574 error ("In basic block %d:", bb->index);
6575 fatal_insn ("Flow control insn inside a basic block", x);
6583 last_bb_num_seen = -1;
6588 if (NOTE_INSN_BASIC_BLOCK_P (x))
6590 basic_block bb = NOTE_BASIC_BLOCK (x);
6592 if (bb->index != last_bb_num_seen + 1)
6593 fatal ("Basic blocks not numbered consecutively");
6594 last_bb_num_seen = bb->index;
6597 if (!bb_info[INSN_UID (x)])
6599 switch (GET_CODE (x))
6606 /* An addr_vec is placed outside any block block. */
6608 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
6609 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
6610 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
6615 /* But in any case, non-deletable labels can appear anywhere. */
6619 fatal_insn ("Insn outside basic block", x);
6623 if (GET_RTX_CLASS (GET_CODE (x)) == 'i'
6624 && GET_CODE (x) == JUMP_INSN
6625 && returnjump_p (x) && ! condjump_p (x)
6626 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
6627 fatal_insn ("Return not followed by barrier", x);
6632 if (num_bb_notes != n_basic_blocks)
6633 fatal ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
6634 num_bb_notes, n_basic_blocks);
6643 /* Functions to access an edge list with a vector representation.
6644 Enough data is kept such that given an index number, the
6645 pred and succ that edge represents can be determined, or
6646 given a pred and a succ, its index number can be returned.
6647 This allows algorithms which consume a lot of memory to
6648 represent the normally full matrix of edge (pred,succ) with a
6649 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
6650 wasted space in the client code due to sparse flow graphs. */
6652 /* This functions initializes the edge list. Basically the entire
6653 flowgraph is processed, and all edges are assigned a number,
6654 and the data structure is filled in. */
6658 struct edge_list *elist;
6664 block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
6668 /* Determine the number of edges in the flow graph by counting successor
6669 edges on each basic block. */
6670 for (x = 0; x < n_basic_blocks; x++)
6672 basic_block bb = BASIC_BLOCK (x);
6674 for (e = bb->succ; e; e = e->succ_next)
6677 /* Don't forget successors of the entry block. */
6678 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6681 elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
6682 elist->num_blocks = block_count;
6683 elist->num_edges = num_edges;
6684 elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
6688 /* Follow successors of the entry block, and register these edges. */
6689 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6691 elist->index_to_edge[num_edges] = e;
6695 for (x = 0; x < n_basic_blocks; x++)
6697 basic_block bb = BASIC_BLOCK (x);
6699 /* Follow all successors of blocks, and register these edges. */
6700 for (e = bb->succ; e; e = e->succ_next)
6702 elist->index_to_edge[num_edges] = e;
6709 /* This function free's memory associated with an edge list. */
6711 free_edge_list (elist)
6712 struct edge_list *elist;
6716 free (elist->index_to_edge);
6721 /* This function provides debug output showing an edge list. */
6723 print_edge_list (f, elist)
6725 struct edge_list *elist;
6728 fprintf(f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
6729 elist->num_blocks - 2, elist->num_edges);
6731 for (x = 0; x < elist->num_edges; x++)
6733 fprintf (f, " %-4d - edge(", x);
6734 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
6735 fprintf (f,"entry,");
6737 fprintf (f,"%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
6739 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
6740 fprintf (f,"exit)\n");
6742 fprintf (f,"%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
6746 /* This function provides an internal consistency check of an edge list,
6747 verifying that all edges are present, and that there are no
6750 verify_edge_list (f, elist)
6752 struct edge_list *elist;
6754 int x, pred, succ, index;
6757 for (x = 0; x < n_basic_blocks; x++)
6759 basic_block bb = BASIC_BLOCK (x);
6761 for (e = bb->succ; e; e = e->succ_next)
6763 pred = e->src->index;
6764 succ = e->dest->index;
6765 index = EDGE_INDEX (elist, e->src, e->dest);
6766 if (index == EDGE_INDEX_NO_EDGE)
6768 fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6771 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6772 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6773 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6774 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6775 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6776 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6779 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6781 pred = e->src->index;
6782 succ = e->dest->index;
6783 index = EDGE_INDEX (elist, e->src, e->dest);
6784 if (index == EDGE_INDEX_NO_EDGE)
6786 fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6789 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6790 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6791 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6792 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6793 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6794 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6796 /* We've verified that all the edges are in the list, no lets make sure
6797 there are no spurious edges in the list. */
6799 for (pred = 0 ; pred < n_basic_blocks; pred++)
6800 for (succ = 0 ; succ < n_basic_blocks; succ++)
6802 basic_block p = BASIC_BLOCK (pred);
6803 basic_block s = BASIC_BLOCK (succ);
6807 for (e = p->succ; e; e = e->succ_next)
6813 for (e = s->pred; e; e = e->pred_next)
6819 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6820 == EDGE_INDEX_NO_EDGE && found_edge != 0)
6821 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
6823 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6824 != EDGE_INDEX_NO_EDGE && found_edge == 0)
6825 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
6826 pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6827 BASIC_BLOCK (succ)));
6829 for (succ = 0 ; succ < n_basic_blocks; succ++)
6831 basic_block p = ENTRY_BLOCK_PTR;
6832 basic_block s = BASIC_BLOCK (succ);
6836 for (e = p->succ; e; e = e->succ_next)
6842 for (e = s->pred; e; e = e->pred_next)
6848 if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6849 == EDGE_INDEX_NO_EDGE && found_edge != 0)
6850 fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
6852 if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6853 != EDGE_INDEX_NO_EDGE && found_edge == 0)
6854 fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
6855 succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
6856 BASIC_BLOCK (succ)));
6858 for (pred = 0 ; pred < n_basic_blocks; pred++)
6860 basic_block p = BASIC_BLOCK (pred);
6861 basic_block s = EXIT_BLOCK_PTR;
6865 for (e = p->succ; e; e = e->succ_next)
6871 for (e = s->pred; e; e = e->pred_next)
6877 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6878 == EDGE_INDEX_NO_EDGE && found_edge != 0)
6879 fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
6881 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6882 != EDGE_INDEX_NO_EDGE && found_edge == 0)
6883 fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
6884 pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6889 /* This routine will determine what, if any, edge there is between
6890 a specified predecessor and successor. */
6893 find_edge_index (edge_list, pred, succ)
6894 struct edge_list *edge_list;
6895 basic_block pred, succ;
6898 for (x = 0; x < NUM_EDGES (edge_list); x++)
6900 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
6901 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
6904 return (EDGE_INDEX_NO_EDGE);
6907 /* This function will remove an edge from the flow graph. */
6912 edge last_pred = NULL;
6913 edge last_succ = NULL;
6915 basic_block src, dest;
6918 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
6924 last_succ->succ_next = e->succ_next;
6926 src->succ = e->succ_next;
6928 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
6934 last_pred->pred_next = e->pred_next;
6936 dest->pred = e->pred_next;
6942 /* This routine will remove any fake successor edges for a basic block.
6943 When the edge is removed, it is also removed from whatever predecessor
6946 remove_fake_successors (bb)
6950 for (e = bb->succ; e ; )
6954 if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
6959 /* This routine will remove all fake edges from the flow graph. If
6960 we remove all fake successors, it will automatically remove all
6961 fake predecessors. */
6963 remove_fake_edges ()
6967 for (x = 0; x < n_basic_blocks; x++)
6968 remove_fake_successors (BASIC_BLOCK (x));
6970 /* We've handled all successors except the entry block's. */
6971 remove_fake_successors (ENTRY_BLOCK_PTR);
6974 /* This function will add a fake edge between any block which has no
6975 successors, and the exit block. Some data flow equations require these
6978 add_noreturn_fake_exit_edges ()
6982 for (x = 0; x < n_basic_blocks; x++)
6983 if (BASIC_BLOCK (x)->succ == NULL)
6984 make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
6987 /* Redirect an edge's successor from one block to another. */
6990 redirect_edge_succ (e, new_succ)
6992 basic_block new_succ;
6996 /* Disconnect the edge from the old successor block. */
6997 for (pe = &e->dest->pred; *pe != e ; pe = &(*pe)->pred_next)
6999 *pe = (*pe)->pred_next;
7001 /* Reconnect the edge to the new successor block. */
7002 e->pred_next = new_succ->pred;
7007 /* Redirect an edge's predecessor from one block to another. */
7010 redirect_edge_pred (e, new_pred)
7012 basic_block new_pred;
7016 /* Disconnect the edge from the old predecessor block. */
7017 for (pe = &e->src->succ; *pe != e ; pe = &(*pe)->succ_next)
7019 *pe = (*pe)->succ_next;
7021 /* Reconnect the edge to the new predecessor block. */
7022 e->succ_next = new_pred->succ;
7027 /* Dump the list of basic blocks in the bitmap NODES. */
7029 flow_nodes_print (str, nodes, file)
7031 const sbitmap nodes;
7036 fprintf (file, "%s { ", str);
7037 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
7038 fputs ("}\n", file);
7042 /* Dump the list of exiting edges in the array EDGES. */
7044 flow_exits_print (str, edges, num_edges, file)
7052 fprintf (file, "%s { ", str);
7053 for (i = 0; i < num_edges; i++)
7054 fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
7055 fputs ("}\n", file);
7059 /* Dump loop related CFG information. */
7061 flow_loops_cfg_dump (loops, file)
7062 const struct loops *loops;
7067 if (! loops->num || ! file || ! loops->cfg.dom)
7070 for (i = 0; i < n_basic_blocks; i++)
7074 fprintf (file, ";; %d succs { ", i);
7075 for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
7076 fprintf (file, "%d ", succ->dest->index);
7077 flow_nodes_print ("} dom", loops->cfg.dom[i], file);
7081 /* Dump the DFS node order. */
7082 if (loops->cfg.dfs_order)
7084 fputs (";; DFS order: ", file);
7085 for (i = 0; i < n_basic_blocks; i++)
7086 fprintf (file, "%d ", loops->cfg.dfs_order[i]);
7089 /* Dump the reverse completion node order. */
7090 if (loops->cfg.rc_order)
7092 fputs (";; RC order: ", file);
7093 for (i = 0; i < n_basic_blocks; i++)
7094 fprintf (file, "%d ", loops->cfg.rc_order[i]);
7100 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
7102 flow_loop_nested_p (outer, loop)
7106 return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
7110 /* Dump the loop information specified by LOOPS to the stream FILE. */
7112 flow_loops_dump (loops, file, verbose)
7113 const struct loops *loops;
7120 num_loops = loops->num;
7121 if (! num_loops || ! file)
7124 fprintf (file, ";; %d loops found, %d levels\n",
7125 num_loops, loops->levels);
7127 for (i = 0; i < num_loops; i++)
7129 struct loop *loop = &loops->array[i];
7131 fprintf (file, ";; loop %d (%d to %d):\n;; header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
7132 i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
7133 loop->header->index, loop->latch->index,
7134 loop->pre_header ? loop->pre_header->index : -1,
7135 loop->depth, loop->level,
7136 (long) (loop->outer ? (loop->outer - loops->array) : -1));
7137 fprintf (file, ";; %d", loop->num_nodes);
7138 flow_nodes_print (" nodes", loop->nodes, file);
7139 fprintf (file, ";; %d", loop->num_exits);
7140 flow_exits_print (" exits", loop->exits, loop->num_exits, file);
7146 for (j = 0; j < i; j++)
7148 struct loop *oloop = &loops->array[j];
7150 if (loop->header == oloop->header)
7155 smaller = loop->num_nodes < oloop->num_nodes;
7157 /* If the union of LOOP and OLOOP is different than
7158 the larger of LOOP and OLOOP then LOOP and OLOOP
7159 must be disjoint. */
7160 disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
7161 smaller ? oloop : loop);
7163 ";; loop header %d shared by loops %d, %d %s\n",
7164 loop->header->index, i, j,
7165 disjoint ? "disjoint" : "nested");
7172 /* Print diagnostics to compare our concept of a loop with
7173 what the loop notes say. */
7174 if (GET_CODE (PREV_INSN (loop->first->head)) != NOTE
7175 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
7176 != NOTE_INSN_LOOP_BEG)
7177 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
7178 INSN_UID (PREV_INSN (loop->first->head)));
7179 if (GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
7180 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
7181 != NOTE_INSN_LOOP_END)
7182 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
7183 INSN_UID (NEXT_INSN (loop->last->end)));
7188 flow_loops_cfg_dump (loops, file);
7192 /* Free all the memory allocated for LOOPS. */
7194 flow_loops_free (loops)
7195 struct loops *loops;
7204 /* Free the loop descriptors. */
7205 for (i = 0; i < loops->num; i++)
7207 struct loop *loop = &loops->array[i];
7210 sbitmap_free (loop->nodes);
7214 free (loops->array);
7215 loops->array = NULL;
7218 sbitmap_vector_free (loops->cfg.dom);
7219 if (loops->cfg.dfs_order)
7220 free (loops->cfg.dfs_order);
7222 sbitmap_free (loops->shared_headers);
7227 /* Find the exits from the loop using the bitmap of loop nodes NODES
7228 and store in EXITS array. Return the number of exits from the
7231 flow_loop_exits_find (nodes, exits)
7232 const sbitmap nodes;
7241 /* Check all nodes within the loop to see if there are any
7242 successors not in the loop. Note that a node may have multiple
7245 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7246 for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7248 basic_block dest = e->dest;
7250 if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7258 *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
7260 /* Store all exiting edges into an array. */
7262 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7263 for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7265 basic_block dest = e->dest;
7267 if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7268 (*exits)[num_exits++] = e;
7276 /* Find the nodes contained within the loop with header HEADER and
7277 latch LATCH and store in NODES. Return the number of nodes within
7280 flow_loop_nodes_find (header, latch, nodes)
7289 stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
7292 /* Start with only the loop header in the set of loop nodes. */
7293 sbitmap_zero (nodes);
7294 SET_BIT (nodes, header->index);
7296 header->loop_depth++;
7298 /* Push the loop latch on to the stack. */
7299 if (! TEST_BIT (nodes, latch->index))
7301 SET_BIT (nodes, latch->index);
7302 latch->loop_depth++;
7304 stack[sp++] = latch;
7313 for (e = node->pred; e; e = e->pred_next)
7315 basic_block ancestor = e->src;
7317 /* If each ancestor not marked as part of loop, add to set of
7318 loop nodes and push on to stack. */
7319 if (ancestor != ENTRY_BLOCK_PTR
7320 && ! TEST_BIT (nodes, ancestor->index))
7322 SET_BIT (nodes, ancestor->index);
7323 ancestor->loop_depth++;
7325 stack[sp++] = ancestor;
7334 /* Compute the depth first search order and store in the array
7335 DFS_ORDER if non-zero, marking the nodes visited in VISITED. If
7336 RC_ORDER is non-zero, return the reverse completion number for each
7337 node. Returns the number of nodes visited. A depth first search
7338 tries to get as far away from the starting point as quickly as
7341 flow_depth_first_order_compute (dfs_order, rc_order)
7348 int rcnum = n_basic_blocks - 1;
7351 /* Allocate stack for back-tracking up CFG. */
7352 stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
7355 /* Allocate bitmap to track nodes that have been visited. */
7356 visited = sbitmap_alloc (n_basic_blocks);
7358 /* None of the nodes in the CFG have been visited yet. */
7359 sbitmap_zero (visited);
7361 /* Push the first edge on to the stack. */
7362 stack[sp++] = ENTRY_BLOCK_PTR->succ;
7370 /* Look at the edge on the top of the stack. */
7375 /* Check if the edge destination has been visited yet. */
7376 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
7378 /* Mark that we have visited the destination. */
7379 SET_BIT (visited, dest->index);
7382 dfs_order[dfsnum++] = dest->index;
7386 /* Since the DEST node has been visited for the first
7387 time, check its successors. */
7388 stack[sp++] = dest->succ;
7392 /* There are no successors for the DEST node so assign
7393 its reverse completion number. */
7395 rc_order[rcnum--] = dest->index;
7400 if (! e->succ_next && src != ENTRY_BLOCK_PTR)
7402 /* There are no more successors for the SRC node
7403 so assign its reverse completion number. */
7405 rc_order[rcnum--] = src->index;
7409 stack[sp - 1] = e->succ_next;
7416 sbitmap_free (visited);
7418 /* The number of nodes visited should not be greater than
7420 if (dfsnum > n_basic_blocks)
7423 /* There are some nodes left in the CFG that are unreachable. */
7424 if (dfsnum < n_basic_blocks)
7430 /* Return the block for the pre-header of the loop with header
7431 HEADER where DOM specifies the dominator information. Return NULL if
7432 there is no pre-header. */
7434 flow_loop_pre_header_find (header, dom)
7438 basic_block pre_header;
7441 /* If block p is a predecessor of the header and is the only block
7442 that the header does not dominate, then it is the pre-header. */
7444 for (e = header->pred; e; e = e->pred_next)
7446 basic_block node = e->src;
7448 if (node != ENTRY_BLOCK_PTR
7449 && ! TEST_BIT (dom[node->index], header->index))
7451 if (pre_header == NULL)
7455 /* There are multiple edges into the header from outside
7456 the loop so there is no pre-header block. */
7466 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
7467 previously added. The insertion algorithm assumes that the loops
7468 are added in the order found by a depth first search of the CFG. */
7470 flow_loop_tree_node_add (prevloop, loop)
7471 struct loop *prevloop;
7475 if (flow_loop_nested_p (prevloop, loop))
7477 prevloop->inner = loop;
7478 loop->outer = prevloop;
7482 while (prevloop->outer)
7484 if (flow_loop_nested_p (prevloop->outer, loop))
7486 prevloop->next = loop;
7487 loop->outer = prevloop->outer;
7490 prevloop = prevloop->outer;
7493 prevloop->next = loop;
7498 /* Build the loop hierarchy tree for LOOPS. */
7500 flow_loops_tree_build (loops)
7501 struct loops *loops;
7506 num_loops = loops->num;
7510 /* Root the loop hierarchy tree with the first loop found.
7511 Since we used a depth first search this should be the
7513 loops->tree = &loops->array[0];
7514 loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
7516 /* Add the remaining loops to the tree. */
7517 for (i = 1; i < num_loops; i++)
7518 flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
7522 /* Helper function to compute loop nesting depth and enclosed loop level
7523 for the natural loop specified by LOOP at the loop depth DEPTH.
7524 Returns the loop level. */
7526 flow_loop_level_compute (loop, depth)
7536 /* Traverse loop tree assigning depth and computing level as the
7537 maximum level of all the inner loops of this loop. The loop
7538 level is equivalent to the height of the loop in the loop tree
7539 and corresponds to the number of enclosed loop levels (including
7541 for (inner = loop->inner; inner; inner = inner->next)
7545 ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
7550 loop->level = level;
7551 loop->depth = depth;
7556 /* Compute the loop nesting depth and enclosed loop level for the loop
7557 hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
7561 flow_loops_level_compute (loops)
7562 struct loops *loops;
7568 /* Traverse all the outer level loops. */
7569 for (loop = loops->tree; loop; loop = loop->next)
7571 level = flow_loop_level_compute (loop, 1);
7579 /* Find all the natural loops in the function and save in LOOPS structure
7580 and recalculate loop_depth information in basic block structures.
7581 Return the number of natural loops found. */
7584 flow_loops_find (loops)
7585 struct loops *loops;
7597 loops->array = NULL;
7602 /* Taking care of this degenerate case makes the rest of
7603 this code simpler. */
7604 if (n_basic_blocks == 0)
7607 /* Compute the dominators. */
7608 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7609 compute_flow_dominators (dom, NULL);
7611 /* Count the number of loop edges (back edges). This should be the
7612 same as the number of natural loops. Also clear the loop_depth
7613 and as we work from inner->outer in a loop nest we call
7614 find_loop_nodes_find which will increment loop_depth for nodes
7615 within the current loop, which happens to enclose inner loops. */
7618 for (b = 0; b < n_basic_blocks; b++)
7620 BASIC_BLOCK (b)->loop_depth = 0;
7621 for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
7623 basic_block latch = e->src;
7625 /* Look for back edges where a predecessor is dominated
7626 by this block. A natural loop has a single entry
7627 node (header) that dominates all the nodes in the
7628 loop. It also has single back edge to the header
7629 from a latch node. Note that multiple natural loops
7630 may share the same header. */
7631 if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
7638 /* Compute depth first search order of the CFG so that outer
7639 natural loops will be found before inner natural loops. */
7640 dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7641 rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7642 flow_depth_first_order_compute (dfs_order, rc_order);
7644 /* Allocate loop structures. */
7646 = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
7648 headers = sbitmap_alloc (n_basic_blocks);
7649 sbitmap_zero (headers);
7651 loops->shared_headers = sbitmap_alloc (n_basic_blocks);
7652 sbitmap_zero (loops->shared_headers);
7654 /* Find and record information about all the natural loops
7657 for (b = 0; b < n_basic_blocks; b++)
7661 /* Search the nodes of the CFG in DFS order that we can find
7662 outer loops first. */
7663 header = BASIC_BLOCK (rc_order[b]);
7665 /* Look for all the possible latch blocks for this header. */
7666 for (e = header->pred; e; e = e->pred_next)
7668 basic_block latch = e->src;
7670 /* Look for back edges where a predecessor is dominated
7671 by this block. A natural loop has a single entry
7672 node (header) that dominates all the nodes in the
7673 loop. It also has single back edge to the header
7674 from a latch node. Note that multiple natural loops
7675 may share the same header. */
7676 if (latch != ENTRY_BLOCK_PTR
7677 && TEST_BIT (dom[latch->index], header->index))
7681 loop = loops->array + num_loops;
7683 loop->header = header;
7684 loop->latch = latch;
7685 loop->num = num_loops;
7687 /* Keep track of blocks that are loop headers so
7688 that we can tell which loops should be merged. */
7689 if (TEST_BIT (headers, header->index))
7690 SET_BIT (loops->shared_headers, header->index);
7691 SET_BIT (headers, header->index);
7693 /* Find nodes contained within the loop. */
7694 loop->nodes = sbitmap_alloc (n_basic_blocks);
7696 = flow_loop_nodes_find (header, latch, loop->nodes);
7698 /* Compute first and last blocks within the loop.
7699 These are often the same as the loop header and
7700 loop latch respectively, but this is not always
7703 = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
7705 = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
7707 /* Find edges which exit the loop. Note that a node
7708 may have several exit edges. */
7710 = flow_loop_exits_find (loop->nodes, &loop->exits);
7712 /* Look to see if the loop has a pre-header node. */
7714 = flow_loop_pre_header_find (header, dom);
7721 /* Natural loops with shared headers may either be disjoint or
7722 nested. Disjoint loops with shared headers cannot be inner
7723 loops and should be merged. For now just mark loops that share
7725 for (i = 0; i < num_loops; i++)
7726 if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
7727 loops->array[i].shared = 1;
7729 sbitmap_free (headers);
7732 loops->num = num_loops;
7734 /* Save CFG derived information to avoid recomputing it. */
7735 loops->cfg.dom = dom;
7736 loops->cfg.dfs_order = dfs_order;
7737 loops->cfg.rc_order = rc_order;
7739 /* Build the loop hierarchy tree. */
7740 flow_loops_tree_build (loops);
7742 /* Assign the loop nesting depth and enclosed loop level for each
7744 loops->levels = flow_loops_level_compute (loops);
7750 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
7753 flow_loop_outside_edge_p (loop, e)
7754 const struct loop *loop;
7757 if (e->dest != loop->header)
7759 return (e->src == ENTRY_BLOCK_PTR)
7760 || ! TEST_BIT (loop->nodes, e->src->index);
7764 /* Clear LOG_LINKS fields of insns in a chain.
7765 Also clear the global_live_at_{start,end} fields of the basic block
7769 clear_log_links (insns)
7775 for (i = insns; i; i = NEXT_INSN (i))
7776 if (GET_RTX_CLASS (GET_CODE (i)) == 'i')
7779 for (b = 0; b < n_basic_blocks; b++)
7781 basic_block bb = BASIC_BLOCK (b);
7783 bb->global_live_at_start = NULL;
7784 bb->global_live_at_end = NULL;
7787 ENTRY_BLOCK_PTR->global_live_at_end = NULL;
7788 EXIT_BLOCK_PTR->global_live_at_start = NULL;
7791 /* Given a register bitmap, turn on the bits in a HARD_REG_SET that
7792 correspond to the hard registers, if any, set in that map. This
7793 could be done far more efficiently by having all sorts of special-cases
7794 with moving single words, but probably isn't worth the trouble. */
7797 reg_set_to_hard_reg_set (to, from)
7803 EXECUTE_IF_SET_IN_BITMAP
7806 if (i >= FIRST_PSEUDO_REGISTER)
7808 SET_HARD_REG_BIT (*to, i);