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. */
22 /* This file contains the data flow analysis pass of the compiler. It
23 computes data flow information which tells combine_instructions
24 which insns to consider combining and controls register allocation.
26 Additional data flow information that is too bulky to record is
27 generated during the analysis, and is used at that time to create
28 autoincrement and autodecrement addressing.
30 The first step is dividing the function into basic blocks.
31 find_basic_blocks does this. Then life_analysis determines
32 where each register is live and where it is dead.
34 ** find_basic_blocks **
36 find_basic_blocks divides the current function's rtl into basic
37 blocks and constructs the CFG. The blocks are recorded in the
38 basic_block_info array; the CFG exists in the edge structures
39 referenced by the blocks.
41 find_basic_blocks also finds any unreachable loops and deletes them.
45 life_analysis is called immediately after find_basic_blocks.
46 It uses the basic block information to determine where each
47 hard or pseudo register is live.
49 ** live-register info **
51 The information about where each register is live is in two parts:
52 the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
54 basic_block->global_live_at_start has an element for each basic
55 block, and the element is a bit-vector with a bit for each hard or
56 pseudo register. The bit is 1 if the register is live at the
57 beginning of the basic block.
59 Two types of elements can be added to an insn's REG_NOTES.
60 A REG_DEAD note is added to an insn's REG_NOTES for any register
61 that meets both of two conditions: The value in the register is not
62 needed in subsequent insns and the insn does not replace the value in
63 the register (in the case of multi-word hard registers, the value in
64 each register must be replaced by the insn to avoid a REG_DEAD note).
66 In the vast majority of cases, an object in a REG_DEAD note will be
67 used somewhere in the insn. The (rare) exception to this is if an
68 insn uses a multi-word hard register and only some of the registers are
69 needed in subsequent insns. In that case, REG_DEAD notes will be
70 provided for those hard registers that are not subsequently needed.
71 Partial REG_DEAD notes of this type do not occur when an insn sets
72 only some of the hard registers used in such a multi-word operand;
73 omitting REG_DEAD notes for objects stored in an insn is optional and
74 the desire to do so does not justify the complexity of the partial
77 REG_UNUSED notes are added for each register that is set by the insn
78 but is unused subsequently (if every register set by the insn is unused
79 and the insn does not reference memory or have some other side-effect,
80 the insn is deleted instead). If only part of a multi-word hard
81 register is used in a subsequent insn, REG_UNUSED notes are made for
82 the parts that will not be used.
84 To determine which registers are live after any insn, one can
85 start from the beginning of the basic block and scan insns, noting
86 which registers are set by each insn and which die there.
88 ** Other actions of life_analysis **
90 life_analysis sets up the LOG_LINKS fields of insns because the
91 information needed to do so is readily available.
93 life_analysis deletes insns whose only effect is to store a value
96 life_analysis notices cases where a reference to a register as
97 a memory address can be combined with a preceding or following
98 incrementation or decrementation of the register. The separate
99 instruction to increment or decrement is deleted and the address
100 is changed to a POST_INC or similar rtx.
102 Each time an incrementing or decrementing address is created,
103 a REG_INC element is added to the insn's REG_NOTES list.
105 life_analysis fills in certain vectors containing information about
106 register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
107 REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
109 life_analysis sets current_function_sp_is_unchanging if the function
110 doesn't modify the stack pointer. */
114 Split out from life_analysis:
115 - local property discovery (bb->local_live, bb->local_set)
116 - global property computation
118 - pre/post modify transformation
126 #include "hard-reg-set.h"
127 #include "basic-block.h"
128 #include "insn-config.h"
132 #include "function.h"
136 #include "insn-flags.h"
141 #include "splay-tree.h"
143 #define obstack_chunk_alloc xmalloc
144 #define obstack_chunk_free free
146 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
147 the stack pointer does not matter. The value is tested only in
148 functions that have frame pointers.
149 No definition is equivalent to always zero. */
150 #ifndef EXIT_IGNORE_STACK
151 #define EXIT_IGNORE_STACK 0
154 #ifndef HAVE_epilogue
155 #define HAVE_epilogue 0
157 #ifndef HAVE_prologue
158 #define HAVE_prologue 0
160 #ifndef HAVE_sibcall_epilogue
161 #define HAVE_sibcall_epilogue 0
165 #define LOCAL_REGNO(REGNO) 0
167 #ifndef EPILOGUE_USES
168 #define EPILOGUE_USES(REGNO) 0
171 /* The contents of the current function definition are allocated
172 in this obstack, and all are freed at the end of the function.
173 For top-level functions, this is temporary_obstack.
174 Separate obstacks are made for nested functions. */
176 extern struct obstack *function_obstack;
178 /* Number of basic blocks in the current function. */
182 /* Number of edges in the current function. */
186 /* The basic block array. */
188 varray_type basic_block_info;
190 /* The special entry and exit blocks. */
192 struct basic_block_def entry_exit_blocks[2]
197 NULL, /* local_set */
198 NULL, /* global_live_at_start */
199 NULL, /* global_live_at_end */
201 ENTRY_BLOCK, /* index */
203 -1, -1, /* eh_beg, eh_end */
211 NULL, /* local_set */
212 NULL, /* global_live_at_start */
213 NULL, /* global_live_at_end */
215 EXIT_BLOCK, /* index */
217 -1, -1, /* eh_beg, eh_end */
222 /* Nonzero if the second flow pass has completed. */
225 /* Maximum register number used in this function, plus one. */
229 /* Indexed by n, giving various register information */
231 varray_type reg_n_info;
233 /* Size of a regset for the current function,
234 in (1) bytes and (2) elements. */
239 /* Regset of regs live when calls to `setjmp'-like functions happen. */
240 /* ??? Does this exist only for the setjmp-clobbered warning message? */
242 regset regs_live_at_setjmp;
244 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
245 that have to go in the same hard reg.
246 The first two regs in the list are a pair, and the next two
247 are another pair, etc. */
250 /* Set of registers that may be eliminable. These are handled specially
251 in updating regs_ever_live. */
253 static HARD_REG_SET elim_reg_set;
255 /* The basic block structure for every insn, indexed by uid. */
257 varray_type basic_block_for_insn;
259 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
260 /* ??? Should probably be using LABEL_NUSES instead. It would take a
261 bit of surgery to be able to use or co-opt the routines in jump. */
263 static rtx label_value_list;
264 static rtx tail_recursion_label_list;
266 /* Holds information for tracking conditional register life information. */
267 struct reg_cond_life_info
269 /* An EXPR_LIST of conditions under which a register is dead. */
272 /* ??? Could store mask of bytes that are dead, so that we could finally
273 track lifetimes of multi-word registers accessed via subregs. */
276 /* For use in communicating between propagate_block and its subroutines.
277 Holds all information needed to compute life and def-use information. */
279 struct propagate_block_info
281 /* The basic block we're considering. */
284 /* Bit N is set if register N is conditionally or unconditionally live. */
287 /* Bit N is set if register N is set this insn. */
290 /* Element N is the next insn that uses (hard or pseudo) register N
291 within the current basic block; or zero, if there is no such insn. */
294 /* Contains a list of all the MEMs we are tracking for dead store
298 /* If non-null, record the set of registers set in the basic block. */
301 #ifdef HAVE_conditional_execution
302 /* Indexed by register number, holds a reg_cond_life_info for each
303 register that is not unconditionally live or dead. */
304 splay_tree reg_cond_dead;
306 /* Bit N is set if register N is in an expression in reg_cond_dead. */
310 /* Non-zero if the value of CC0 is live. */
313 /* Flags controling the set of information propagate_block collects. */
317 /* Store the data structures necessary for depth-first search. */
318 struct depth_first_search_dsS {
319 /* stack for backtracking during the algorithm */
322 /* number of edges in the stack. That is, positions 0, ..., sp-1
326 /* record of basic blocks already seen by depth-first search */
327 sbitmap visited_blocks;
329 typedef struct depth_first_search_dsS *depth_first_search_ds;
331 /* Forward declarations */
332 static int count_basic_blocks PARAMS ((rtx));
333 static void find_basic_blocks_1 PARAMS ((rtx));
334 static rtx find_label_refs PARAMS ((rtx, rtx));
335 static void clear_edges PARAMS ((void));
336 static void make_edges PARAMS ((rtx));
337 static void make_label_edge PARAMS ((sbitmap *, basic_block,
339 static void make_eh_edge PARAMS ((sbitmap *, eh_nesting_info *,
340 basic_block, rtx, int));
341 static void mark_critical_edges PARAMS ((void));
342 static void move_stray_eh_region_notes PARAMS ((void));
343 static void record_active_eh_regions PARAMS ((rtx));
345 static void commit_one_edge_insertion PARAMS ((edge));
347 static void delete_unreachable_blocks PARAMS ((void));
348 static void delete_eh_regions PARAMS ((void));
349 static int can_delete_note_p PARAMS ((rtx));
350 static void expunge_block PARAMS ((basic_block));
351 static int can_delete_label_p PARAMS ((rtx));
352 static int tail_recursion_label_p PARAMS ((rtx));
353 static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
355 static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
357 static int merge_blocks PARAMS ((edge,basic_block,basic_block));
358 static void try_merge_blocks PARAMS ((void));
359 static void tidy_fallthru_edges PARAMS ((void));
360 static int verify_wide_reg_1 PARAMS ((rtx *, void *));
361 static void verify_wide_reg PARAMS ((int, rtx, rtx));
362 static void verify_local_live_at_start PARAMS ((regset, basic_block));
363 static int set_noop_p PARAMS ((rtx));
364 static int noop_move_p PARAMS ((rtx));
365 static void delete_noop_moves PARAMS ((rtx));
366 static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
367 static void notice_stack_pointer_modification PARAMS ((rtx));
368 static void mark_reg PARAMS ((rtx, void *));
369 static void mark_regs_live_at_end PARAMS ((regset));
370 static int set_phi_alternative_reg PARAMS ((rtx, int, int, void *));
371 static void calculate_global_regs_live PARAMS ((sbitmap, sbitmap, int));
372 static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
373 static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
374 static int insn_dead_p PARAMS ((struct propagate_block_info *,
376 static int libcall_dead_p PARAMS ((struct propagate_block_info *,
378 static void mark_set_regs PARAMS ((struct propagate_block_info *,
380 static void mark_set_1 PARAMS ((struct propagate_block_info *,
381 enum rtx_code, rtx, rtx,
383 #ifdef HAVE_conditional_execution
384 static int mark_regno_cond_dead PARAMS ((struct propagate_block_info *,
386 static void free_reg_cond_life_info PARAMS ((splay_tree_value));
387 static int flush_reg_cond_reg_1 PARAMS ((splay_tree_node, void *));
388 static void flush_reg_cond_reg PARAMS ((struct propagate_block_info *,
390 static rtx ior_reg_cond PARAMS ((rtx, rtx));
391 static rtx not_reg_cond PARAMS ((rtx));
392 static rtx nand_reg_cond PARAMS ((rtx, rtx));
395 static void attempt_auto_inc PARAMS ((struct propagate_block_info *,
396 rtx, rtx, rtx, rtx, rtx));
397 static void find_auto_inc PARAMS ((struct propagate_block_info *,
399 static int try_pre_increment_1 PARAMS ((struct propagate_block_info *,
401 static int try_pre_increment PARAMS ((rtx, rtx, HOST_WIDE_INT));
403 static void mark_used_reg PARAMS ((struct propagate_block_info *,
405 static void mark_used_regs PARAMS ((struct propagate_block_info *,
407 void dump_flow_info PARAMS ((FILE *));
408 void debug_flow_info PARAMS ((void));
409 static void dump_edge_info PARAMS ((FILE *, edge, int));
411 static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
413 static void remove_fake_successors PARAMS ((basic_block));
414 static void flow_nodes_print PARAMS ((const char *, const sbitmap,
416 static void flow_edge_list_print PARAMS ((const char *, const edge *,
418 static void flow_loops_cfg_dump PARAMS ((const struct loops *,
420 static int flow_loop_nested_p PARAMS ((struct loop *,
422 static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap,
424 static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **));
425 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
426 static int flow_depth_first_order_compute PARAMS ((int *, int *));
427 static void flow_dfs_compute_reverse_init
428 PARAMS ((depth_first_search_ds));
429 static void flow_dfs_compute_reverse_add_bb
430 PARAMS ((depth_first_search_ds, basic_block));
431 static basic_block flow_dfs_compute_reverse_execute
432 PARAMS ((depth_first_search_ds));
433 static void flow_dfs_compute_reverse_finish
434 PARAMS ((depth_first_search_ds));
435 static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
436 static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
437 static void flow_loops_tree_build PARAMS ((struct loops *));
438 static int flow_loop_level_compute PARAMS ((struct loop *, int));
439 static int flow_loops_level_compute PARAMS ((struct loops *));
441 /* Find basic blocks of the current function.
442 F is the first insn of the function and NREGS the number of register
446 find_basic_blocks (f, nregs, file)
448 int nregs ATTRIBUTE_UNUSED;
449 FILE *file ATTRIBUTE_UNUSED;
453 /* Flush out existing data. */
454 if (basic_block_info != NULL)
460 /* Clear bb->aux on all extant basic blocks. We'll use this as a
461 tag for reuse during create_basic_block, just in case some pass
462 copies around basic block notes improperly. */
463 for (i = 0; i < n_basic_blocks; ++i)
464 BASIC_BLOCK (i)->aux = NULL;
466 VARRAY_FREE (basic_block_info);
469 n_basic_blocks = count_basic_blocks (f);
471 /* Size the basic block table. The actual structures will be allocated
472 by find_basic_blocks_1, since we want to keep the structure pointers
473 stable across calls to find_basic_blocks. */
474 /* ??? This whole issue would be much simpler if we called find_basic_blocks
475 exactly once, and thereafter we don't have a single long chain of
476 instructions at all until close to the end of compilation when we
477 actually lay them out. */
479 VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
481 find_basic_blocks_1 (f);
483 /* Record the block to which an insn belongs. */
484 /* ??? This should be done another way, by which (perhaps) a label is
485 tagged directly with the basic block that it starts. It is used for
486 more than that currently, but IMO that is the only valid use. */
488 max_uid = get_max_uid ();
490 /* Leave space for insns life_analysis makes in some cases for auto-inc.
491 These cases are rare, so we don't need too much space. */
492 max_uid += max_uid / 10;
495 compute_bb_for_insn (max_uid);
497 /* Discover the edges of our cfg. */
498 record_active_eh_regions (f);
499 make_edges (label_value_list);
501 /* Do very simple cleanup now, for the benefit of code that runs between
502 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
503 tidy_fallthru_edges ();
505 mark_critical_edges ();
507 #ifdef ENABLE_CHECKING
512 /* Count the basic blocks of the function. */
515 count_basic_blocks (f)
519 register RTX_CODE prev_code;
520 register int count = 0;
522 int call_had_abnormal_edge = 0;
524 prev_code = JUMP_INSN;
525 for (insn = f; insn; insn = NEXT_INSN (insn))
527 register RTX_CODE code = GET_CODE (insn);
529 if (code == CODE_LABEL
530 || (GET_RTX_CLASS (code) == 'i'
531 && (prev_code == JUMP_INSN
532 || prev_code == BARRIER
533 || (prev_code == CALL_INSN && call_had_abnormal_edge))))
536 /* Record whether this call created an edge. */
537 if (code == CALL_INSN)
539 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
540 int region = (note ? INTVAL (XEXP (note, 0)) : 1);
542 call_had_abnormal_edge = 0;
544 /* If there is an EH region or rethrow, we have an edge. */
545 if ((eh_region && region > 0)
546 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
547 call_had_abnormal_edge = 1;
548 else if (nonlocal_goto_handler_labels && region >= 0)
549 /* If there is a nonlocal goto label and the specified
550 region number isn't -1, we have an edge. (0 means
551 no throw, but might have a nonlocal goto). */
552 call_had_abnormal_edge = 1;
557 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
559 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
563 /* The rest of the compiler works a bit smoother when we don't have to
564 check for the edge case of do-nothing functions with no basic blocks. */
567 emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
574 /* Scan a list of insns for labels referred to other than by jumps.
575 This is used to scan the alternatives of a call placeholder. */
577 find_label_refs (f, lvl)
583 for (insn = f; insn; insn = NEXT_INSN (insn))
588 /* Make a list of all labels referred to other than by jumps
589 (which just don't have the REG_LABEL notes).
591 Make a special exception for labels followed by an ADDR*VEC,
592 as this would be a part of the tablejump setup code.
594 Make a special exception for the eh_return_stub_label, which
595 we know isn't part of any otherwise visible control flow. */
597 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
598 if (REG_NOTE_KIND (note) == REG_LABEL)
600 rtx lab = XEXP (note, 0), next;
602 if (lab == eh_return_stub_label)
604 else if ((next = next_nonnote_insn (lab)) != NULL
605 && GET_CODE (next) == JUMP_INSN
606 && (GET_CODE (PATTERN (next)) == ADDR_VEC
607 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
609 else if (GET_CODE (lab) == NOTE)
612 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
619 /* Find all basic blocks of the function whose first insn is F.
621 Collect and return a list of labels whose addresses are taken. This
622 will be used in make_edges for use with computed gotos. */
625 find_basic_blocks_1 (f)
628 register rtx insn, next;
630 rtx bb_note = NULL_RTX;
631 rtx eh_list = NULL_RTX;
637 /* We process the instructions in a slightly different way than we did
638 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
639 closed out the previous block, so that it gets attached at the proper
640 place. Since this form should be equivalent to the previous,
641 count_basic_blocks continues to use the old form as a check. */
643 for (insn = f; insn; insn = next)
645 enum rtx_code code = GET_CODE (insn);
647 next = NEXT_INSN (insn);
653 int kind = NOTE_LINE_NUMBER (insn);
655 /* Keep a LIFO list of the currently active exception notes. */
656 if (kind == NOTE_INSN_EH_REGION_BEG)
657 eh_list = alloc_INSN_LIST (insn, eh_list);
658 else if (kind == NOTE_INSN_EH_REGION_END)
662 eh_list = XEXP (eh_list, 1);
663 free_INSN_LIST_node (t);
666 /* Look for basic block notes with which to keep the
667 basic_block_info pointers stable. Unthread the note now;
668 we'll put it back at the right place in create_basic_block.
669 Or not at all if we've already found a note in this block. */
670 else if (kind == NOTE_INSN_BASIC_BLOCK)
672 if (bb_note == NULL_RTX)
675 next = flow_delete_insn (insn);
681 /* A basic block starts at a label. If we've closed one off due
682 to a barrier or some such, no need to do it again. */
683 if (head != NULL_RTX)
685 /* While we now have edge lists with which other portions of
686 the compiler might determine a call ending a basic block
687 does not imply an abnormal edge, it will be a bit before
688 everything can be updated. So continue to emit a noop at
689 the end of such a block. */
690 if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
692 rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
693 end = emit_insn_after (nop, end);
696 create_basic_block (i++, head, end, bb_note);
704 /* A basic block ends at a jump. */
705 if (head == NULL_RTX)
709 /* ??? Make a special check for table jumps. The way this
710 happens is truly and amazingly gross. We are about to
711 create a basic block that contains just a code label and
712 an addr*vec jump insn. Worse, an addr_diff_vec creates
713 its own natural loop.
715 Prevent this bit of brain damage, pasting things together
716 correctly in make_edges.
718 The correct solution involves emitting the table directly
719 on the tablejump instruction as a note, or JUMP_LABEL. */
721 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
722 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
730 goto new_bb_inclusive;
733 /* A basic block ends at a barrier. It may be that an unconditional
734 jump already closed the basic block -- no need to do it again. */
735 if (head == NULL_RTX)
738 /* While we now have edge lists with which other portions of the
739 compiler might determine a call ending a basic block does not
740 imply an abnormal edge, it will be a bit before everything can
741 be updated. So continue to emit a noop at the end of such a
743 if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
745 rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
746 end = emit_insn_after (nop, end);
748 goto new_bb_exclusive;
752 /* Record whether this call created an edge. */
753 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
754 int region = (note ? INTVAL (XEXP (note, 0)) : 1);
755 int call_has_abnormal_edge = 0;
757 if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
759 /* Scan each of the alternatives for label refs. */
760 lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
761 lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
762 lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
763 /* Record its tail recursion label, if any. */
764 if (XEXP (PATTERN (insn), 3) != NULL_RTX)
765 trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
768 /* If there is an EH region or rethrow, we have an edge. */
769 if ((eh_list && region > 0)
770 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
771 call_has_abnormal_edge = 1;
772 else if (nonlocal_goto_handler_labels && region >= 0)
773 /* If there is a nonlocal goto label and the specified
774 region number isn't -1, we have an edge. (0 means
775 no throw, but might have a nonlocal goto). */
776 call_has_abnormal_edge = 1;
778 /* A basic block ends at a call that can either throw or
779 do a non-local goto. */
780 if (call_has_abnormal_edge)
783 if (head == NULL_RTX)
788 create_basic_block (i++, head, end, bb_note);
789 head = end = NULL_RTX;
797 if (GET_RTX_CLASS (code) == 'i')
799 if (head == NULL_RTX)
806 if (GET_RTX_CLASS (code) == 'i')
810 /* Make a list of all labels referred to other than by jumps
811 (which just don't have the REG_LABEL notes).
813 Make a special exception for labels followed by an ADDR*VEC,
814 as this would be a part of the tablejump setup code.
816 Make a special exception for the eh_return_stub_label, which
817 we know isn't part of any otherwise visible control flow. */
819 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
820 if (REG_NOTE_KIND (note) == REG_LABEL)
822 rtx lab = XEXP (note, 0), next;
824 if (lab == eh_return_stub_label)
826 else if ((next = next_nonnote_insn (lab)) != NULL
827 && GET_CODE (next) == JUMP_INSN
828 && (GET_CODE (PATTERN (next)) == ADDR_VEC
829 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
831 else if (GET_CODE (lab) == NOTE)
834 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
839 if (head != NULL_RTX)
840 create_basic_block (i++, head, end, bb_note);
842 flow_delete_insn (bb_note);
844 if (i != n_basic_blocks)
847 label_value_list = lvl;
848 tail_recursion_label_list = trll;
851 /* Tidy the CFG by deleting unreachable code and whatnot. */
857 delete_unreachable_blocks ();
858 move_stray_eh_region_notes ();
859 record_active_eh_regions (f);
861 mark_critical_edges ();
863 /* Kill the data we won't maintain. */
864 free_EXPR_LIST_list (&label_value_list);
865 free_EXPR_LIST_list (&tail_recursion_label_list);
868 /* Create a new basic block consisting of the instructions between
869 HEAD and END inclusive. Reuses the note and basic block struct
870 in BB_NOTE, if any. */
873 create_basic_block (index, head, end, bb_note)
875 rtx head, end, bb_note;
880 && ! RTX_INTEGRATED_P (bb_note)
881 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
884 /* If we found an existing note, thread it back onto the chain. */
888 if (GET_CODE (head) == CODE_LABEL)
892 after = PREV_INSN (head);
896 if (after != bb_note && NEXT_INSN (after) != bb_note)
897 reorder_insns (bb_note, bb_note, after);
901 /* Otherwise we must create a note and a basic block structure.
902 Since we allow basic block structs in rtl, give the struct
903 the same lifetime by allocating it off the function obstack
904 rather than using malloc. */
906 bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
907 memset (bb, 0, sizeof (*bb));
909 if (GET_CODE (head) == CODE_LABEL)
910 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
913 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
916 NOTE_BASIC_BLOCK (bb_note) = bb;
919 /* Always include the bb note in the block. */
920 if (NEXT_INSN (end) == bb_note)
926 BASIC_BLOCK (index) = bb;
928 /* Tag the block so that we know it has been used when considering
929 other basic block notes. */
933 /* Records the basic block struct in BB_FOR_INSN, for every instruction
934 indexed by INSN_UID. MAX is the size of the array. */
937 compute_bb_for_insn (max)
942 if (basic_block_for_insn)
943 VARRAY_FREE (basic_block_for_insn);
944 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
946 for (i = 0; i < n_basic_blocks; ++i)
948 basic_block bb = BASIC_BLOCK (i);
955 int uid = INSN_UID (insn);
957 VARRAY_BB (basic_block_for_insn, uid) = bb;
960 insn = NEXT_INSN (insn);
965 /* Free the memory associated with the edge structures. */
973 for (i = 0; i < n_basic_blocks; ++i)
975 basic_block bb = BASIC_BLOCK (i);
977 for (e = bb->succ; e; e = n)
987 for (e = ENTRY_BLOCK_PTR->succ; e; e = n)
993 ENTRY_BLOCK_PTR->succ = 0;
994 EXIT_BLOCK_PTR->pred = 0;
999 /* Identify the edges between basic blocks.
1001 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
1002 that are otherwise unreachable may be reachable with a non-local goto.
1004 BB_EH_END is an array indexed by basic block number in which we record
1005 the list of exception regions active at the end of the basic block. */
1008 make_edges (label_value_list)
1009 rtx label_value_list;
1012 eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
1013 sbitmap *edge_cache = NULL;
1015 /* Assume no computed jump; revise as we create edges. */
1016 current_function_has_computed_jump = 0;
1018 /* Heavy use of computed goto in machine-generated code can lead to
1019 nearly fully-connected CFGs. In that case we spend a significant
1020 amount of time searching the edge lists for duplicates. */
1021 if (forced_labels || label_value_list)
1023 edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
1024 sbitmap_vector_zero (edge_cache, n_basic_blocks);
1027 /* By nature of the way these get numbered, block 0 is always the entry. */
1028 make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
1030 for (i = 0; i < n_basic_blocks; ++i)
1032 basic_block bb = BASIC_BLOCK (i);
1035 int force_fallthru = 0;
1037 /* Examine the last instruction of the block, and discover the
1038 ways we can leave the block. */
1041 code = GET_CODE (insn);
1044 if (code == JUMP_INSN)
1048 /* ??? Recognize a tablejump and do the right thing. */
1049 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1050 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1051 && GET_CODE (tmp) == JUMP_INSN
1052 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1053 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1058 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1059 vec = XVEC (PATTERN (tmp), 0);
1061 vec = XVEC (PATTERN (tmp), 1);
1063 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1064 make_label_edge (edge_cache, bb,
1065 XEXP (RTVEC_ELT (vec, j), 0), 0);
1067 /* Some targets (eg, ARM) emit a conditional jump that also
1068 contains the out-of-range target. Scan for these and
1069 add an edge if necessary. */
1070 if ((tmp = single_set (insn)) != NULL
1071 && SET_DEST (tmp) == pc_rtx
1072 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1073 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
1074 make_label_edge (edge_cache, bb,
1075 XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
1077 #ifdef CASE_DROPS_THROUGH
1078 /* Silly VAXen. The ADDR_VEC is going to be in the way of
1079 us naturally detecting fallthru into the next block. */
1084 /* If this is a computed jump, then mark it as reaching
1085 everything on the label_value_list and forced_labels list. */
1086 else if (computed_jump_p (insn))
1088 current_function_has_computed_jump = 1;
1090 for (x = label_value_list; x; x = XEXP (x, 1))
1091 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1093 for (x = forced_labels; x; x = XEXP (x, 1))
1094 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1097 /* Returns create an exit out. */
1098 else if (returnjump_p (insn))
1099 make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
1101 /* Otherwise, we have a plain conditional or unconditional jump. */
1104 if (! JUMP_LABEL (insn))
1106 make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
1110 /* If this is a sibling call insn, then this is in effect a
1111 combined call and return, and so we need an edge to the
1112 exit block. No need to worry about EH edges, since we
1113 wouldn't have created the sibling call in the first place. */
1115 if (code == CALL_INSN && SIBLING_CALL_P (insn))
1116 make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
1117 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1120 /* If this is a CALL_INSN, then mark it as reaching the active EH
1121 handler for this CALL_INSN. If we're handling asynchronous
1122 exceptions then any insn can reach any of the active handlers.
1124 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
1126 if (code == CALL_INSN || asynchronous_exceptions)
1128 /* Add any appropriate EH edges. We do this unconditionally
1129 since there may be a REG_EH_REGION or REG_EH_RETHROW note
1130 on the call, and this needn't be within an EH region. */
1131 make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
1133 /* If we have asynchronous exceptions, do the same for *all*
1134 exception regions active in the block. */
1135 if (asynchronous_exceptions
1136 && bb->eh_beg != bb->eh_end)
1138 if (bb->eh_beg >= 0)
1139 make_eh_edge (edge_cache, eh_nest_info, bb,
1140 NULL_RTX, bb->eh_beg);
1142 for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
1143 if (GET_CODE (x) == NOTE
1144 && (NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_BEG
1145 || NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
1147 int region = NOTE_EH_HANDLER (x);
1148 make_eh_edge (edge_cache, eh_nest_info, bb,
1153 if (code == CALL_INSN && nonlocal_goto_handler_labels)
1155 /* ??? This could be made smarter: in some cases it's possible
1156 to tell that certain calls will not do a nonlocal goto.
1158 For example, if the nested functions that do the nonlocal
1159 gotos do not have their addresses taken, then only calls to
1160 those functions or to other nested functions that use them
1161 could possibly do nonlocal gotos. */
1162 /* We do know that a REG_EH_REGION note with a value less
1163 than 0 is guaranteed not to perform a non-local goto. */
1164 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1165 if (!note || INTVAL (XEXP (note, 0)) >= 0)
1166 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
1167 make_label_edge (edge_cache, bb, XEXP (x, 0),
1168 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1172 /* We know something about the structure of the function __throw in
1173 libgcc2.c. It is the only function that ever contains eh_stub
1174 labels. It modifies its return address so that the last block
1175 returns to one of the eh_stub labels within it. So we have to
1176 make additional edges in the flow graph. */
1177 if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
1178 make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH);
1180 /* Find out if we can drop through to the next block. */
1181 insn = next_nonnote_insn (insn);
1182 if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
1183 make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1184 else if (i + 1 < n_basic_blocks)
1186 rtx tmp = BLOCK_HEAD (i + 1);
1187 if (GET_CODE (tmp) == NOTE)
1188 tmp = next_nonnote_insn (tmp);
1189 if (force_fallthru || insn == tmp)
1190 make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
1194 free_eh_nesting_info (eh_nest_info);
1196 sbitmap_vector_free (edge_cache);
1199 /* Create an edge between two basic blocks. FLAGS are auxiliary information
1200 about the edge that is accumulated between calls. */
1203 make_edge (edge_cache, src, dst, flags)
1204 sbitmap *edge_cache;
1205 basic_block src, dst;
1211 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1212 many edges to them, and we didn't allocate memory for it. */
1213 use_edge_cache = (edge_cache
1214 && src != ENTRY_BLOCK_PTR
1215 && dst != EXIT_BLOCK_PTR);
1217 /* Make sure we don't add duplicate edges. */
1218 if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
1219 for (e = src->succ; e; e = e->succ_next)
1226 e = (edge) xcalloc (1, sizeof (*e));
1229 e->succ_next = src->succ;
1230 e->pred_next = dst->pred;
1239 SET_BIT (edge_cache[src->index], dst->index);
1242 /* Create an edge from a basic block to a label. */
1245 make_label_edge (edge_cache, src, label, flags)
1246 sbitmap *edge_cache;
1251 if (GET_CODE (label) != CODE_LABEL)
1254 /* If the label was never emitted, this insn is junk, but avoid a
1255 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
1256 as a result of a syntax error and a diagnostic has already been
1259 if (INSN_UID (label) == 0)
1262 make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
1265 /* Create the edges generated by INSN in REGION. */
1268 make_eh_edge (edge_cache, eh_nest_info, src, insn, region)
1269 sbitmap *edge_cache;
1270 eh_nesting_info *eh_nest_info;
1275 handler_info **handler_list;
1278 is_call = (insn && GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
1279 num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
1282 make_label_edge (edge_cache, src, handler_list[num]->handler_label,
1283 EDGE_ABNORMAL | EDGE_EH | is_call);
1287 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1288 dangerous if we intend to move basic blocks around. Move such notes
1289 into the following block. */
1292 move_stray_eh_region_notes ()
1297 if (n_basic_blocks < 2)
1300 b2 = BASIC_BLOCK (n_basic_blocks - 1);
1301 for (i = n_basic_blocks - 2; i >= 0; --i, b2 = b1)
1303 rtx insn, next, list = NULL_RTX;
1305 b1 = BASIC_BLOCK (i);
1306 for (insn = NEXT_INSN (b1->end); insn != b2->head; insn = next)
1308 next = NEXT_INSN (insn);
1309 if (GET_CODE (insn) == NOTE
1310 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1311 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1313 /* Unlink from the insn chain. */
1314 NEXT_INSN (PREV_INSN (insn)) = next;
1315 PREV_INSN (next) = PREV_INSN (insn);
1318 NEXT_INSN (insn) = list;
1323 if (list == NULL_RTX)
1326 /* Find where to insert these things. */
1328 if (GET_CODE (insn) == CODE_LABEL)
1329 insn = NEXT_INSN (insn);
1333 next = NEXT_INSN (list);
1334 add_insn_after (list, insn);
1340 /* Recompute eh_beg/eh_end for each basic block. */
1343 record_active_eh_regions (f)
1346 rtx insn, eh_list = NULL_RTX;
1348 basic_block bb = BASIC_BLOCK (0);
1350 for (insn = f; insn; insn = NEXT_INSN (insn))
1352 if (bb->head == insn)
1353 bb->eh_beg = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1355 if (GET_CODE (insn) == NOTE)
1357 int kind = NOTE_LINE_NUMBER (insn);
1358 if (kind == NOTE_INSN_EH_REGION_BEG)
1359 eh_list = alloc_INSN_LIST (insn, eh_list);
1360 else if (kind == NOTE_INSN_EH_REGION_END)
1362 rtx t = XEXP (eh_list, 1);
1363 free_INSN_LIST_node (eh_list);
1368 if (bb->end == insn)
1370 bb->eh_end = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1372 if (i == n_basic_blocks)
1374 bb = BASIC_BLOCK (i);
1379 /* Identify critical edges and set the bits appropriately. */
1382 mark_critical_edges ()
1384 int i, n = n_basic_blocks;
1387 /* We begin with the entry block. This is not terribly important now,
1388 but could be if a front end (Fortran) implemented alternate entry
1390 bb = ENTRY_BLOCK_PTR;
1397 /* (1) Critical edges must have a source with multiple successors. */
1398 if (bb->succ && bb->succ->succ_next)
1400 for (e = bb->succ; e; e = e->succ_next)
1402 /* (2) Critical edges must have a destination with multiple
1403 predecessors. Note that we know there is at least one
1404 predecessor -- the edge we followed to get here. */
1405 if (e->dest->pred->pred_next)
1406 e->flags |= EDGE_CRITICAL;
1408 e->flags &= ~EDGE_CRITICAL;
1413 for (e = bb->succ; e; e = e->succ_next)
1414 e->flags &= ~EDGE_CRITICAL;
1419 bb = BASIC_BLOCK (i);
1423 /* Split a (typically critical) edge. Return the new block.
1424 Abort on abnormal edges.
1426 ??? The code generally expects to be called on critical edges.
1427 The case of a block ending in an unconditional jump to a
1428 block with multiple predecessors is not handled optimally. */
1431 split_edge (edge_in)
1434 basic_block old_pred, bb, old_succ;
1439 /* Abnormal edges cannot be split. */
1440 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1443 old_pred = edge_in->src;
1444 old_succ = edge_in->dest;
1446 /* Remove the existing edge from the destination's pred list. */
1449 for (pp = &old_succ->pred; *pp != edge_in; pp = &(*pp)->pred_next)
1451 *pp = edge_in->pred_next;
1452 edge_in->pred_next = NULL;
1455 /* Create the new structures. */
1456 bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
1457 edge_out = (edge) xcalloc (1, sizeof (*edge_out));
1460 memset (bb, 0, sizeof (*bb));
1462 /* ??? This info is likely going to be out of date very soon. */
1463 if (old_succ->global_live_at_start)
1465 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
1466 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
1467 COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
1468 COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
1473 bb->succ = edge_out;
1474 bb->count = edge_in->count;
1477 edge_in->flags &= ~EDGE_CRITICAL;
1479 edge_out->pred_next = old_succ->pred;
1480 edge_out->succ_next = NULL;
1482 edge_out->dest = old_succ;
1483 edge_out->flags = EDGE_FALLTHRU;
1484 edge_out->probability = REG_BR_PROB_BASE;
1485 edge_out->count = edge_in->count;
1487 old_succ->pred = edge_out;
1489 /* Tricky case -- if there existed a fallthru into the successor
1490 (and we're not it) we must add a new unconditional jump around
1491 the new block we're actually interested in.
1493 Further, if that edge is critical, this means a second new basic
1494 block must be created to hold it. In order to simplify correct
1495 insn placement, do this before we touch the existing basic block
1496 ordering for the block we were really wanting. */
1497 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1500 for (e = edge_out->pred_next; e; e = e->pred_next)
1501 if (e->flags & EDGE_FALLTHRU)
1506 basic_block jump_block;
1509 if ((e->flags & EDGE_CRITICAL) == 0
1510 && e->src != ENTRY_BLOCK_PTR)
1512 /* Non critical -- we can simply add a jump to the end
1513 of the existing predecessor. */
1514 jump_block = e->src;
1518 /* We need a new block to hold the jump. The simplest
1519 way to do the bulk of the work here is to recursively
1521 jump_block = split_edge (e);
1522 e = jump_block->succ;
1525 /* Now add the jump insn ... */
1526 pos = emit_jump_insn_after (gen_jump (old_succ->head),
1528 jump_block->end = pos;
1529 if (basic_block_for_insn)
1530 set_block_for_insn (pos, jump_block);
1531 emit_barrier_after (pos);
1533 /* ... let jump know that label is in use, ... */
1534 JUMP_LABEL (pos) = old_succ->head;
1535 ++LABEL_NUSES (old_succ->head);
1537 /* ... and clear fallthru on the outgoing edge. */
1538 e->flags &= ~EDGE_FALLTHRU;
1540 /* Continue splitting the interesting edge. */
1544 /* Place the new block just in front of the successor. */
1545 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1546 if (old_succ == EXIT_BLOCK_PTR)
1547 j = n_basic_blocks - 1;
1549 j = old_succ->index;
1550 for (i = n_basic_blocks - 1; i > j; --i)
1552 basic_block tmp = BASIC_BLOCK (i - 1);
1553 BASIC_BLOCK (i) = tmp;
1556 BASIC_BLOCK (i) = bb;
1559 /* Create the basic block note.
1561 Where we place the note can have a noticable impact on the generated
1562 code. Consider this cfg:
1572 If we need to insert an insn on the edge from block 0 to block 1,
1573 we want to ensure the instructions we insert are outside of any
1574 loop notes that physically sit between block 0 and block 1. Otherwise
1575 we confuse the loop optimizer into thinking the loop is a phony. */
1576 if (old_succ != EXIT_BLOCK_PTR
1577 && PREV_INSN (old_succ->head)
1578 && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
1579 && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
1580 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1581 PREV_INSN (old_succ->head));
1582 else if (old_succ != EXIT_BLOCK_PTR)
1583 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
1585 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
1586 NOTE_BASIC_BLOCK (bb_note) = bb;
1587 bb->head = bb->end = bb_note;
1589 /* Not quite simple -- for non-fallthru edges, we must adjust the
1590 predecessor's jump instruction to target our new block. */
1591 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1593 rtx tmp, insn = old_pred->end;
1594 rtx old_label = old_succ->head;
1595 rtx new_label = gen_label_rtx ();
1597 if (GET_CODE (insn) != JUMP_INSN)
1600 /* ??? Recognize a tablejump and adjust all matching cases. */
1601 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1602 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1603 && GET_CODE (tmp) == JUMP_INSN
1604 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1605 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1610 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1611 vec = XVEC (PATTERN (tmp), 0);
1613 vec = XVEC (PATTERN (tmp), 1);
1615 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1616 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1618 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (VOIDmode, new_label);
1619 --LABEL_NUSES (old_label);
1620 ++LABEL_NUSES (new_label);
1623 /* Handle casesi dispatch insns */
1624 if ((tmp = single_set (insn)) != NULL
1625 && SET_DEST (tmp) == pc_rtx
1626 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1627 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1628 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1630 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
1632 --LABEL_NUSES (old_label);
1633 ++LABEL_NUSES (new_label);
1638 /* This would have indicated an abnormal edge. */
1639 if (computed_jump_p (insn))
1642 /* A return instruction can't be redirected. */
1643 if (returnjump_p (insn))
1646 /* If the insn doesn't go where we think, we're confused. */
1647 if (JUMP_LABEL (insn) != old_label)
1650 redirect_jump (insn, new_label, 0);
1653 emit_label_before (new_label, bb_note);
1654 bb->head = new_label;
1660 /* Queue instructions for insertion on an edge between two basic blocks.
1661 The new instructions and basic blocks (if any) will not appear in the
1662 CFG until commit_edge_insertions is called. */
1665 insert_insn_on_edge (pattern, e)
1669 /* We cannot insert instructions on an abnormal critical edge.
1670 It will be easier to find the culprit if we die now. */
1671 if ((e->flags & (EDGE_ABNORMAL|EDGE_CRITICAL))
1672 == (EDGE_ABNORMAL|EDGE_CRITICAL))
1675 if (e->insns == NULL_RTX)
1678 push_to_sequence (e->insns);
1680 emit_insn (pattern);
1682 e->insns = get_insns ();
1686 /* Update the CFG for the instructions queued on edge E. */
1689 commit_one_edge_insertion (e)
1692 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1695 /* Pull the insns off the edge now since the edge might go away. */
1697 e->insns = NULL_RTX;
1699 /* Figure out where to put these things. If the destination has
1700 one predecessor, insert there. Except for the exit block. */
1701 if (e->dest->pred->pred_next == NULL
1702 && e->dest != EXIT_BLOCK_PTR)
1706 /* Get the location correct wrt a code label, and "nice" wrt
1707 a basic block note, and before everything else. */
1709 if (GET_CODE (tmp) == CODE_LABEL)
1710 tmp = NEXT_INSN (tmp);
1711 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1712 tmp = NEXT_INSN (tmp);
1713 if (tmp == bb->head)
1716 after = PREV_INSN (tmp);
1719 /* If the source has one successor and the edge is not abnormal,
1720 insert there. Except for the entry block. */
1721 else if ((e->flags & EDGE_ABNORMAL) == 0
1722 && e->src->succ->succ_next == NULL
1723 && e->src != ENTRY_BLOCK_PTR)
1726 /* It is possible to have a non-simple jump here. Consider a target
1727 where some forms of unconditional jumps clobber a register. This
1728 happens on the fr30 for example.
1730 We know this block has a single successor, so we can just emit
1731 the queued insns before the jump. */
1732 if (GET_CODE (bb->end) == JUMP_INSN)
1738 /* We'd better be fallthru, or we've lost track of what's what. */
1739 if ((e->flags & EDGE_FALLTHRU) == 0)
1746 /* Otherwise we must split the edge. */
1749 bb = split_edge (e);
1753 /* Now that we've found the spot, do the insertion. */
1755 /* Set the new block number for these insns, if structure is allocated. */
1756 if (basic_block_for_insn)
1759 for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
1760 set_block_for_insn (i, bb);
1765 emit_insns_before (insns, before);
1766 if (before == bb->head)
1769 last = prev_nonnote_insn (before);
1773 last = emit_insns_after (insns, after);
1774 if (after == bb->end)
1778 if (returnjump_p (last))
1780 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1781 This is not currently a problem because this only happens
1782 for the (single) epilogue, which already has a fallthru edge
1786 if (e->dest != EXIT_BLOCK_PTR
1787 || e->succ_next != NULL
1788 || (e->flags & EDGE_FALLTHRU) == 0)
1790 e->flags &= ~EDGE_FALLTHRU;
1792 emit_barrier_after (last);
1796 flow_delete_insn (before);
1798 else if (GET_CODE (last) == JUMP_INSN)
1802 /* Update the CFG for all queued instructions. */
1805 commit_edge_insertions ()
1810 #ifdef ENABLE_CHECKING
1811 verify_flow_info ();
1815 bb = ENTRY_BLOCK_PTR;
1820 for (e = bb->succ; e; e = next)
1822 next = e->succ_next;
1824 commit_one_edge_insertion (e);
1827 if (++i >= n_basic_blocks)
1829 bb = BASIC_BLOCK (i);
1833 /* Delete all unreachable basic blocks. */
1836 delete_unreachable_blocks ()
1838 basic_block *worklist, *tos;
1839 int deleted_handler;
1844 tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
1846 /* Use basic_block->aux as a marker. Clear them all. */
1848 for (i = 0; i < n; ++i)
1849 BASIC_BLOCK (i)->aux = NULL;
1851 /* Add our starting points to the worklist. Almost always there will
1852 be only one. It isn't inconcievable that we might one day directly
1853 support Fortran alternate entry points. */
1855 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
1859 /* Mark the block with a handy non-null value. */
1863 /* Iterate: find everything reachable from what we've already seen. */
1865 while (tos != worklist)
1867 basic_block b = *--tos;
1869 for (e = b->succ; e; e = e->succ_next)
1877 /* Delete all unreachable basic blocks. Count down so that we don't
1878 interfere with the block renumbering that happens in flow_delete_block. */
1880 deleted_handler = 0;
1882 for (i = n - 1; i >= 0; --i)
1884 basic_block b = BASIC_BLOCK (i);
1887 /* This block was found. Tidy up the mark. */
1890 deleted_handler |= flow_delete_block (b);
1893 tidy_fallthru_edges ();
1895 /* If we deleted an exception handler, we may have EH region begin/end
1896 blocks to remove as well. */
1897 if (deleted_handler)
1898 delete_eh_regions ();
1903 /* Find EH regions for which there is no longer a handler, and delete them. */
1906 delete_eh_regions ()
1910 update_rethrow_references ();
1912 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1913 if (GET_CODE (insn) == NOTE)
1915 if ((NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
1916 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1918 int num = NOTE_EH_HANDLER (insn);
1919 /* A NULL handler indicates a region is no longer needed,
1920 as long as its rethrow label isn't used. */
1921 if (get_first_handler (num) == NULL && ! rethrow_used (num))
1923 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1924 NOTE_SOURCE_FILE (insn) = 0;
1930 /* Return true if NOTE is not one of the ones that must be kept paired,
1931 so that we may simply delete them. */
1934 can_delete_note_p (note)
1937 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
1938 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
1941 /* Unlink a chain of insns between START and FINISH, leaving notes
1942 that must be paired. */
1945 flow_delete_insn_chain (start, finish)
1948 /* Unchain the insns one by one. It would be quicker to delete all
1949 of these with a single unchaining, rather than one at a time, but
1950 we need to keep the NOTE's. */
1956 next = NEXT_INSN (start);
1957 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
1959 else if (GET_CODE (start) == CODE_LABEL
1960 && ! can_delete_label_p (start))
1962 const char *name = LABEL_NAME (start);
1963 PUT_CODE (start, NOTE);
1964 NOTE_LINE_NUMBER (start) = NOTE_INSN_DELETED_LABEL;
1965 NOTE_SOURCE_FILE (start) = name;
1968 next = flow_delete_insn (start);
1970 if (start == finish)
1976 /* Delete the insns in a (non-live) block. We physically delete every
1977 non-deleted-note insn, and update the flow graph appropriately.
1979 Return nonzero if we deleted an exception handler. */
1981 /* ??? Preserving all such notes strikes me as wrong. It would be nice
1982 to post-process the stream to remove empty blocks, loops, ranges, etc. */
1985 flow_delete_block (b)
1988 int deleted_handler = 0;
1991 /* If the head of this block is a CODE_LABEL, then it might be the
1992 label for an exception handler which can't be reached.
1994 We need to remove the label from the exception_handler_label list
1995 and remove the associated NOTE_INSN_EH_REGION_BEG and
1996 NOTE_INSN_EH_REGION_END notes. */
2000 never_reached_warning (insn);
2002 if (GET_CODE (insn) == CODE_LABEL)
2004 rtx x, *prev = &exception_handler_labels;
2006 for (x = exception_handler_labels; x; x = XEXP (x, 1))
2008 if (XEXP (x, 0) == insn)
2010 /* Found a match, splice this label out of the EH label list. */
2011 *prev = XEXP (x, 1);
2012 XEXP (x, 1) = NULL_RTX;
2013 XEXP (x, 0) = NULL_RTX;
2015 /* Remove the handler from all regions */
2016 remove_handler (insn);
2017 deleted_handler = 1;
2020 prev = &XEXP (x, 1);
2024 /* Include any jump table following the basic block. */
2026 if (GET_CODE (end) == JUMP_INSN
2027 && (tmp = JUMP_LABEL (end)) != NULL_RTX
2028 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
2029 && GET_CODE (tmp) == JUMP_INSN
2030 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
2031 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
2034 /* Include any barrier that may follow the basic block. */
2035 tmp = next_nonnote_insn (end);
2036 if (tmp && GET_CODE (tmp) == BARRIER)
2039 /* Selectively delete the entire chain. */
2040 flow_delete_insn_chain (insn, end);
2042 /* Remove the edges into and out of this block. Note that there may
2043 indeed be edges in, if we are removing an unreachable loop. */
2047 for (e = b->pred; e; e = next)
2049 for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
2052 next = e->pred_next;
2056 for (e = b->succ; e; e = next)
2058 for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
2061 next = e->succ_next;
2070 /* Remove the basic block from the array, and compact behind it. */
2073 return deleted_handler;
2076 /* Remove block B from the basic block array and compact behind it. */
2082 int i, n = n_basic_blocks;
2084 for (i = b->index; i + 1 < n; ++i)
2086 basic_block x = BASIC_BLOCK (i + 1);
2087 BASIC_BLOCK (i) = x;
2091 basic_block_info->num_elements--;
2095 /* Delete INSN by patching it out. Return the next insn. */
2098 flow_delete_insn (insn)
2101 rtx prev = PREV_INSN (insn);
2102 rtx next = NEXT_INSN (insn);
2105 PREV_INSN (insn) = NULL_RTX;
2106 NEXT_INSN (insn) = NULL_RTX;
2107 INSN_DELETED_P (insn) = 1;
2110 NEXT_INSN (prev) = next;
2112 PREV_INSN (next) = prev;
2114 set_last_insn (prev);
2116 if (GET_CODE (insn) == CODE_LABEL)
2117 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2119 /* If deleting a jump, decrement the use count of the label. Deleting
2120 the label itself should happen in the normal course of block merging. */
2121 if (GET_CODE (insn) == JUMP_INSN
2122 && JUMP_LABEL (insn)
2123 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
2124 LABEL_NUSES (JUMP_LABEL (insn))--;
2126 /* Also if deleting an insn that references a label. */
2127 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
2128 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2129 LABEL_NUSES (XEXP (note, 0))--;
2134 /* True if a given label can be deleted. */
2137 can_delete_label_p (label)
2142 if (LABEL_PRESERVE_P (label))
2145 for (x = forced_labels; x; x = XEXP (x, 1))
2146 if (label == XEXP (x, 0))
2148 for (x = label_value_list; x; x = XEXP (x, 1))
2149 if (label == XEXP (x, 0))
2151 for (x = exception_handler_labels; x; x = XEXP (x, 1))
2152 if (label == XEXP (x, 0))
2155 /* User declared labels must be preserved. */
2156 if (LABEL_NAME (label) != 0)
2163 tail_recursion_label_p (label)
2168 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
2169 if (label == XEXP (x, 0))
2175 /* Blocks A and B are to be merged into a single block A. The insns
2176 are already contiguous, hence `nomove'. */
2179 merge_blocks_nomove (a, b)
2183 rtx b_head, b_end, a_end;
2184 rtx del_first = NULL_RTX, del_last = NULL_RTX;
2187 /* If there was a CODE_LABEL beginning B, delete it. */
2190 if (GET_CODE (b_head) == CODE_LABEL)
2192 /* Detect basic blocks with nothing but a label. This can happen
2193 in particular at the end of a function. */
2194 if (b_head == b_end)
2196 del_first = del_last = b_head;
2197 b_head = NEXT_INSN (b_head);
2200 /* Delete the basic block note. */
2201 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
2203 if (b_head == b_end)
2208 b_head = NEXT_INSN (b_head);
2211 /* If there was a jump out of A, delete it. */
2213 if (GET_CODE (a_end) == JUMP_INSN)
2217 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
2218 if (GET_CODE (prev) != NOTE
2219 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
2226 /* If this was a conditional jump, we need to also delete
2227 the insn that set cc0. */
2228 if (prev && sets_cc0_p (prev))
2231 prev = prev_nonnote_insn (prev);
2240 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
2241 del_first = NEXT_INSN (a_end);
2243 /* Delete everything marked above as well as crap that might be
2244 hanging out between the two blocks. */
2245 flow_delete_insn_chain (del_first, del_last);
2247 /* Normally there should only be one successor of A and that is B, but
2248 partway though the merge of blocks for conditional_execution we'll
2249 be merging a TEST block with THEN and ELSE successors. Free the
2250 whole lot of them and hope the caller knows what they're doing. */
2252 remove_edge (a->succ);
2254 /* Adjust the edges out of B for the new owner. */
2255 for (e = b->succ; e; e = e->succ_next)
2259 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
2260 b->pred = b->succ = NULL;
2262 /* Reassociate the insns of B with A. */
2265 if (basic_block_for_insn)
2267 BLOCK_FOR_INSN (b_head) = a;
2268 while (b_head != b_end)
2270 b_head = NEXT_INSN (b_head);
2271 BLOCK_FOR_INSN (b_head) = a;
2281 /* Blocks A and B are to be merged into a single block. A has no incoming
2282 fallthru edge, so it can be moved before B without adding or modifying
2283 any jumps (aside from the jump from A to B). */
2286 merge_blocks_move_predecessor_nojumps (a, b)
2289 rtx start, end, barrier;
2295 barrier = next_nonnote_insn (end);
2296 if (GET_CODE (barrier) != BARRIER)
2298 flow_delete_insn (barrier);
2300 /* Move block and loop notes out of the chain so that we do not
2301 disturb their order.
2303 ??? A better solution would be to squeeze out all the non-nested notes
2304 and adjust the block trees appropriately. Even better would be to have
2305 a tighter connection between block trees and rtl so that this is not
2307 start = squeeze_notes (start, end);
2309 /* Scramble the insn chain. */
2310 if (end != PREV_INSN (b->head))
2311 reorder_insns (start, end, PREV_INSN (b->head));
2315 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
2316 a->index, b->index);
2319 /* Swap the records for the two blocks around. Although we are deleting B,
2320 A is now where B was and we want to compact the BB array from where
2322 BASIC_BLOCK (a->index) = b;
2323 BASIC_BLOCK (b->index) = a;
2325 a->index = b->index;
2328 /* Now blocks A and B are contiguous. Merge them. */
2329 merge_blocks_nomove (a, b);
2334 /* Blocks A and B are to be merged into a single block. B has no outgoing
2335 fallthru edge, so it can be moved after A without adding or modifying
2336 any jumps (aside from the jump from A to B). */
2339 merge_blocks_move_successor_nojumps (a, b)
2342 rtx start, end, barrier;
2346 barrier = NEXT_INSN (end);
2348 /* Recognize a jump table following block B. */
2349 if (GET_CODE (barrier) == CODE_LABEL
2350 && NEXT_INSN (barrier)
2351 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
2352 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
2353 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
2355 end = NEXT_INSN (barrier);
2356 barrier = NEXT_INSN (end);
2359 /* There had better have been a barrier there. Delete it. */
2360 if (GET_CODE (barrier) != BARRIER)
2362 flow_delete_insn (barrier);
2364 /* Move block and loop notes out of the chain so that we do not
2365 disturb their order.
2367 ??? A better solution would be to squeeze out all the non-nested notes
2368 and adjust the block trees appropriately. Even better would be to have
2369 a tighter connection between block trees and rtl so that this is not
2371 start = squeeze_notes (start, end);
2373 /* Scramble the insn chain. */
2374 reorder_insns (start, end, a->end);
2376 /* Now blocks A and B are contiguous. Merge them. */
2377 merge_blocks_nomove (a, b);
2381 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
2382 b->index, a->index);
2388 /* Attempt to merge basic blocks that are potentially non-adjacent.
2389 Return true iff the attempt succeeded. */
2392 merge_blocks (e, b, c)
2396 /* If C has a tail recursion label, do not merge. There is no
2397 edge recorded from the call_placeholder back to this label, as
2398 that would make optimize_sibling_and_tail_recursive_calls more
2399 complex for no gain. */
2400 if (GET_CODE (c->head) == CODE_LABEL
2401 && tail_recursion_label_p (c->head))
2404 /* If B has a fallthru edge to C, no need to move anything. */
2405 if (e->flags & EDGE_FALLTHRU)
2407 merge_blocks_nomove (b, c);
2411 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
2412 b->index, c->index);
2421 int c_has_outgoing_fallthru;
2422 int b_has_incoming_fallthru;
2424 /* We must make sure to not munge nesting of exception regions,
2425 lexical blocks, and loop notes.
2427 The first is taken care of by requiring that the active eh
2428 region at the end of one block always matches the active eh
2429 region at the beginning of the next block.
2431 The later two are taken care of by squeezing out all the notes. */
2433 /* ??? A throw/catch edge (or any abnormal edge) should be rarely
2434 executed and we may want to treat blocks which have two out
2435 edges, one normal, one abnormal as only having one edge for
2436 block merging purposes. */
2438 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
2439 if (tmp_edge->flags & EDGE_FALLTHRU)
2441 c_has_outgoing_fallthru = (tmp_edge != NULL);
2443 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
2444 if (tmp_edge->flags & EDGE_FALLTHRU)
2446 b_has_incoming_fallthru = (tmp_edge != NULL);
2448 /* If B does not have an incoming fallthru, and the exception regions
2449 match, then it can be moved immediately before C without introducing
2452 C can not be the first block, so we do not have to worry about
2453 accessing a non-existent block. */
2454 d = BASIC_BLOCK (c->index - 1);
2455 if (! b_has_incoming_fallthru
2456 && d->eh_end == b->eh_beg
2457 && b->eh_end == c->eh_beg)
2458 return merge_blocks_move_predecessor_nojumps (b, c);
2460 /* Otherwise, we're going to try to move C after B. Make sure the
2461 exception regions match.
2463 If B is the last basic block, then we must not try to access the
2464 block structure for block B + 1. Luckily in that case we do not
2465 need to worry about matching exception regions. */
2466 d = (b->index + 1 < n_basic_blocks ? BASIC_BLOCK (b->index + 1) : NULL);
2467 if (b->eh_end == c->eh_beg
2468 && (d == NULL || c->eh_end == d->eh_beg))
2470 /* If C does not have an outgoing fallthru, then it can be moved
2471 immediately after B without introducing or modifying jumps. */
2472 if (! c_has_outgoing_fallthru)
2473 return merge_blocks_move_successor_nojumps (b, c);
2475 /* Otherwise, we'll need to insert an extra jump, and possibly
2476 a new block to contain it. */
2477 /* ??? Not implemented yet. */
2484 /* Top level driver for merge_blocks. */
2491 /* Attempt to merge blocks as made possible by edge removal. If a block
2492 has only one successor, and the successor has only one predecessor,
2493 they may be combined. */
2495 for (i = 0; i < n_basic_blocks;)
2497 basic_block c, b = BASIC_BLOCK (i);
2500 /* A loop because chains of blocks might be combineable. */
2501 while ((s = b->succ) != NULL
2502 && s->succ_next == NULL
2503 && (s->flags & EDGE_EH) == 0
2504 && (c = s->dest) != EXIT_BLOCK_PTR
2505 && c->pred->pred_next == NULL
2506 /* If the jump insn has side effects, we can't kill the edge. */
2507 && (GET_CODE (b->end) != JUMP_INSN
2508 || onlyjump_p (b->end))
2509 && merge_blocks (s, b, c))
2512 /* Don't get confused by the index shift caused by deleting blocks. */
2517 /* The given edge should potentially be a fallthru edge. If that is in
2518 fact true, delete the jump and barriers that are in the way. */
2521 tidy_fallthru_edge (e, b, c)
2527 /* ??? In a late-running flow pass, other folks may have deleted basic
2528 blocks by nopping out blocks, leaving multiple BARRIERs between here
2529 and the target label. They ought to be chastized and fixed.
2531 We can also wind up with a sequence of undeletable labels between
2532 one block and the next.
2534 So search through a sequence of barriers, labels, and notes for
2535 the head of block C and assert that we really do fall through. */
2537 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
2540 /* Remove what will soon cease being the jump insn from the source block.
2541 If block B consisted only of this single jump, turn it into a deleted
2544 if (GET_CODE (q) == JUMP_INSN
2546 && (any_uncondjump_p (q)
2547 || (b->succ == e && e->succ_next == NULL)))
2550 /* If this was a conditional jump, we need to also delete
2551 the insn that set cc0. */
2552 if (any_condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
2559 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
2560 NOTE_SOURCE_FILE (q) = 0;
2568 /* Selectively unlink the sequence. */
2569 if (q != PREV_INSN (c->head))
2570 flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
2572 e->flags |= EDGE_FALLTHRU;
2575 /* Fix up edges that now fall through, or rather should now fall through
2576 but previously required a jump around now deleted blocks. Simplify
2577 the search by only examining blocks numerically adjacent, since this
2578 is how find_basic_blocks created them. */
2581 tidy_fallthru_edges ()
2585 for (i = 1; i < n_basic_blocks; ++i)
2587 basic_block b = BASIC_BLOCK (i - 1);
2588 basic_block c = BASIC_BLOCK (i);
2591 /* We care about simple conditional or unconditional jumps with
2594 If we had a conditional branch to the next instruction when
2595 find_basic_blocks was called, then there will only be one
2596 out edge for the block which ended with the conditional
2597 branch (since we do not create duplicate edges).
2599 Furthermore, the edge will be marked as a fallthru because we
2600 merge the flags for the duplicate edges. So we do not want to
2601 check that the edge is not a FALLTHRU edge. */
2602 if ((s = b->succ) != NULL
2603 && s->succ_next == NULL
2605 /* If the jump insn has side effects, we can't tidy the edge. */
2606 && (GET_CODE (b->end) != JUMP_INSN
2607 || onlyjump_p (b->end)))
2608 tidy_fallthru_edge (s, b, c);
2612 /* Perform data flow analysis.
2613 F is the first insn of the function; FLAGS is a set of PROP_* flags
2614 to be used in accumulating flow info. */
2617 life_analysis (f, file, flags)
2622 #ifdef ELIMINABLE_REGS
2624 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
2627 /* Record which registers will be eliminated. We use this in
2630 CLEAR_HARD_REG_SET (elim_reg_set);
2632 #ifdef ELIMINABLE_REGS
2633 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2634 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
2636 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
2640 flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC);
2642 /* The post-reload life analysis have (on a global basis) the same
2643 registers live as was computed by reload itself. elimination
2644 Otherwise offsets and such may be incorrect.
2646 Reload will make some registers as live even though they do not
2649 We don't want to create new auto-incs after reload, since they
2650 are unlikely to be useful and can cause problems with shared
2652 if (reload_completed)
2653 flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
2655 /* We want alias analysis information for local dead store elimination. */
2656 if (optimize && (flags & PROP_SCAN_DEAD_CODE))
2657 init_alias_analysis ();
2659 /* Always remove no-op moves. Do this before other processing so
2660 that we don't have to keep re-scanning them. */
2661 delete_noop_moves (f);
2663 /* Some targets can emit simpler epilogues if they know that sp was
2664 not ever modified during the function. After reload, of course,
2665 we've already emitted the epilogue so there's no sense searching. */
2666 if (! reload_completed)
2667 notice_stack_pointer_modification (f);
2669 /* Allocate and zero out data structures that will record the
2670 data from lifetime analysis. */
2671 allocate_reg_life_data ();
2672 allocate_bb_life_data ();
2674 /* Find the set of registers live on function exit. */
2675 mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
2677 /* "Update" life info from zero. It'd be nice to begin the
2678 relaxation with just the exit and noreturn blocks, but that set
2679 is not immediately handy. */
2681 if (flags & PROP_REG_INFO)
2682 memset (regs_ever_live, 0, sizeof (regs_ever_live));
2683 update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
2686 if (optimize && (flags & PROP_SCAN_DEAD_CODE))
2687 end_alias_analysis ();
2690 dump_flow_info (file);
2692 free_basic_block_vars (1);
2695 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2696 Search for REGNO. If found, abort if it is not wider than word_mode. */
2699 verify_wide_reg_1 (px, pregno)
2704 unsigned int regno = *(int *) pregno;
2706 if (GET_CODE (x) == REG && REGNO (x) == regno)
2708 if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
2715 /* A subroutine of verify_local_live_at_start. Search through insns
2716 between HEAD and END looking for register REGNO. */
2719 verify_wide_reg (regno, head, end)
2726 && for_each_rtx (&PATTERN (head), verify_wide_reg_1, ®no))
2730 head = NEXT_INSN (head);
2733 /* We didn't find the register at all. Something's way screwy. */
2737 /* A subroutine of update_life_info. Verify that there are no untoward
2738 changes in live_at_start during a local update. */
2741 verify_local_live_at_start (new_live_at_start, bb)
2742 regset new_live_at_start;
2745 if (reload_completed)
2747 /* After reload, there are no pseudos, nor subregs of multi-word
2748 registers. The regsets should exactly match. */
2749 if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
2756 /* Find the set of changed registers. */
2757 XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
2759 EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i,
2761 /* No registers should die. */
2762 if (REGNO_REG_SET_P (bb->global_live_at_start, i))
2764 /* Verify that the now-live register is wider than word_mode. */
2765 verify_wide_reg (i, bb->head, bb->end);
2770 /* Updates life information starting with the basic blocks set in BLOCKS.
2771 If BLOCKS is null, consider it to be the universal set.
2773 If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
2774 we are only expecting local modifications to basic blocks. If we find
2775 extra registers live at the beginning of a block, then we either killed
2776 useful data, or we have a broken split that wants data not provided.
2777 If we find registers removed from live_at_start, that means we have
2778 a broken peephole that is killing a register it shouldn't.
2780 ??? This is not true in one situation -- when a pre-reload splitter
2781 generates subregs of a multi-word pseudo, current life analysis will
2782 lose the kill. So we _can_ have a pseudo go live. How irritating.
2784 Including PROP_REG_INFO does not properly refresh regs_ever_live
2785 unless the caller resets it to zero. */
2788 update_life_info (blocks, extent, prop_flags)
2790 enum update_life_extent extent;
2794 regset_head tmp_head;
2797 tmp = INITIALIZE_REG_SET (tmp_head);
2799 /* For a global update, we go through the relaxation process again. */
2800 if (extent != UPDATE_LIFE_LOCAL)
2802 calculate_global_regs_live (blocks, blocks,
2803 prop_flags & PROP_SCAN_DEAD_CODE);
2805 /* If asked, remove notes from the blocks we'll update. */
2806 if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
2807 count_or_remove_death_notes (blocks, 1);
2812 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
2814 basic_block bb = BASIC_BLOCK (i);
2816 COPY_REG_SET (tmp, bb->global_live_at_end);
2817 propagate_block (bb, tmp, (regset) NULL, prop_flags);
2819 if (extent == UPDATE_LIFE_LOCAL)
2820 verify_local_live_at_start (tmp, bb);
2825 for (i = n_basic_blocks - 1; i >= 0; --i)
2827 basic_block bb = BASIC_BLOCK (i);
2829 COPY_REG_SET (tmp, bb->global_live_at_end);
2830 propagate_block (bb, tmp, (regset) NULL, prop_flags);
2832 if (extent == UPDATE_LIFE_LOCAL)
2833 verify_local_live_at_start (tmp, bb);
2839 if (prop_flags & PROP_REG_INFO)
2841 /* The only pseudos that are live at the beginning of the function
2842 are those that were not set anywhere in the function. local-alloc
2843 doesn't know how to handle these correctly, so mark them as not
2844 local to any one basic block. */
2845 EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
2846 FIRST_PSEUDO_REGISTER, i,
2847 { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
2849 /* We have a problem with any pseudoreg that lives across the setjmp.
2850 ANSI says that if a user variable does not change in value between
2851 the setjmp and the longjmp, then the longjmp preserves it. This
2852 includes longjmp from a place where the pseudo appears dead.
2853 (In principle, the value still exists if it is in scope.)
2854 If the pseudo goes in a hard reg, some other value may occupy
2855 that hard reg where this pseudo is dead, thus clobbering the pseudo.
2856 Conclusion: such a pseudo must not go in a hard reg. */
2857 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
2858 FIRST_PSEUDO_REGISTER, i,
2860 if (regno_reg_rtx[i] != 0)
2862 REG_LIVE_LENGTH (i) = -1;
2863 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2869 /* Free the variables allocated by find_basic_blocks.
2871 KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed. */
2874 free_basic_block_vars (keep_head_end_p)
2875 int keep_head_end_p;
2877 if (basic_block_for_insn)
2879 VARRAY_FREE (basic_block_for_insn);
2880 basic_block_for_insn = NULL;
2883 if (! keep_head_end_p)
2886 VARRAY_FREE (basic_block_info);
2889 ENTRY_BLOCK_PTR->aux = NULL;
2890 ENTRY_BLOCK_PTR->global_live_at_end = NULL;
2891 EXIT_BLOCK_PTR->aux = NULL;
2892 EXIT_BLOCK_PTR->global_live_at_start = NULL;
2896 /* Return nonzero if the destination of SET equals the source. */
2902 rtx src = SET_SRC (set);
2903 rtx dst = SET_DEST (set);
2905 if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
2907 if (SUBREG_WORD (src) != SUBREG_WORD (dst))
2909 src = SUBREG_REG (src);
2910 dst = SUBREG_REG (dst);
2913 return (GET_CODE (src) == REG && GET_CODE (dst) == REG
2914 && REGNO (src) == REGNO (dst));
2917 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2924 rtx pat = PATTERN (insn);
2926 /* Insns carrying these notes are useful later on. */
2927 if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
2930 if (GET_CODE (pat) == SET && set_noop_p (pat))
2933 if (GET_CODE (pat) == PARALLEL)
2936 /* If nothing but SETs of registers to themselves,
2937 this insn can also be deleted. */
2938 for (i = 0; i < XVECLEN (pat, 0); i++)
2940 rtx tem = XVECEXP (pat, 0, i);
2942 if (GET_CODE (tem) == USE
2943 || GET_CODE (tem) == CLOBBER)
2946 if (GET_CODE (tem) != SET || ! set_noop_p (tem))
2955 /* Delete any insns that copy a register to itself. */
2958 delete_noop_moves (f)
2962 for (insn = f; insn; insn = NEXT_INSN (insn))
2964 if (GET_CODE (insn) == INSN && noop_move_p (insn))
2966 PUT_CODE (insn, NOTE);
2967 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2968 NOTE_SOURCE_FILE (insn) = 0;
2973 /* Determine if the stack pointer is constant over the life of the function.
2974 Only useful before prologues have been emitted. */
2977 notice_stack_pointer_modification_1 (x, pat, data)
2979 rtx pat ATTRIBUTE_UNUSED;
2980 void *data ATTRIBUTE_UNUSED;
2982 if (x == stack_pointer_rtx
2983 /* The stack pointer is only modified indirectly as the result
2984 of a push until later in flow. See the comments in rtl.texi
2985 regarding Embedded Side-Effects on Addresses. */
2986 || (GET_CODE (x) == MEM
2987 && (GET_CODE (XEXP (x, 0)) == PRE_DEC
2988 || GET_CODE (XEXP (x, 0)) == PRE_INC
2989 || GET_CODE (XEXP (x, 0)) == POST_DEC
2990 || GET_CODE (XEXP (x, 0)) == POST_INC)
2991 && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
2992 current_function_sp_is_unchanging = 0;
2996 notice_stack_pointer_modification (f)
3001 /* Assume that the stack pointer is unchanging if alloca hasn't
3003 current_function_sp_is_unchanging = !current_function_calls_alloca;
3004 if (! current_function_sp_is_unchanging)
3007 for (insn = f; insn; insn = NEXT_INSN (insn))
3011 /* Check if insn modifies the stack pointer. */
3012 note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
3014 if (! current_function_sp_is_unchanging)
3020 /* Mark a register in SET. Hard registers in large modes get all
3021 of their component registers set as well. */
3024 mark_reg (reg, xset)
3028 regset set = (regset) xset;
3029 int regno = REGNO (reg);
3031 if (GET_MODE (reg) == BLKmode)
3034 SET_REGNO_REG_SET (set, regno);
3035 if (regno < FIRST_PSEUDO_REGISTER)
3037 int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3039 SET_REGNO_REG_SET (set, regno + n);
3043 /* Mark those regs which are needed at the end of the function as live
3044 at the end of the last basic block. */
3047 mark_regs_live_at_end (set)
3052 /* If exiting needs the right stack value, consider the stack pointer
3053 live at the end of the function. */
3054 if ((HAVE_epilogue && reload_completed)
3055 || ! EXIT_IGNORE_STACK
3056 || (! FRAME_POINTER_REQUIRED
3057 && ! current_function_calls_alloca
3058 && flag_omit_frame_pointer)
3059 || current_function_sp_is_unchanging)
3061 SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
3064 /* Mark the frame pointer if needed at the end of the function. If
3065 we end up eliminating it, it will be removed from the live list
3066 of each basic block by reload. */
3068 if (! reload_completed || frame_pointer_needed)
3070 SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
3071 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3072 /* If they are different, also mark the hard frame pointer as live. */
3073 if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3074 SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
3078 #ifdef PIC_OFFSET_TABLE_REGNUM
3079 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3080 /* Many architectures have a GP register even without flag_pic.
3081 Assume the pic register is not in use, or will be handled by
3082 other means, if it is not fixed. */
3083 if (fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3084 SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
3088 /* Mark all global registers, and all registers used by the epilogue
3089 as being live at the end of the function since they may be
3090 referenced by our caller. */
3091 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3092 if (global_regs[i] || EPILOGUE_USES (i))
3093 SET_REGNO_REG_SET (set, i);
3095 /* Mark all call-saved registers that we actaully used. */
3096 if (HAVE_epilogue && reload_completed)
3098 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3099 if (regs_ever_live[i] && ! call_used_regs[i] && ! LOCAL_REGNO (i))
3100 SET_REGNO_REG_SET (set, i);
3103 /* Mark function return value. */
3104 diddle_return_value (mark_reg, set);
3107 /* Callback function for for_each_successor_phi. DATA is a regset.
3108 Sets the SRC_REGNO, the regno of the phi alternative for phi node
3109 INSN, in the regset. */
3112 set_phi_alternative_reg (insn, dest_regno, src_regno, data)
3113 rtx insn ATTRIBUTE_UNUSED;
3114 int dest_regno ATTRIBUTE_UNUSED;
3118 regset live = (regset) data;
3119 SET_REGNO_REG_SET (live, src_regno);
3123 /* Propagate global life info around the graph of basic blocks. Begin
3124 considering blocks with their corresponding bit set in BLOCKS_IN.
3125 If BLOCKS_IN is null, consider it the universal set.
3127 BLOCKS_OUT is set for every block that was changed. */
3130 calculate_global_regs_live (blocks_in, blocks_out, flags)
3131 sbitmap blocks_in, blocks_out;
3134 basic_block *queue, *qhead, *qtail, *qend;
3135 regset tmp, new_live_at_end;
3136 regset_head tmp_head;
3137 regset_head new_live_at_end_head;
3140 tmp = INITIALIZE_REG_SET (tmp_head);
3141 new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
3143 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
3144 because the `head == tail' style test for an empty queue doesn't
3145 work with a full queue. */
3146 queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
3148 qhead = qend = queue + n_basic_blocks + 2;
3150 /* Clear out the garbage that might be hanging out in bb->aux. */
3151 for (i = n_basic_blocks - 1; i >= 0; --i)
3152 BASIC_BLOCK (i)->aux = NULL;
3154 /* Queue the blocks set in the initial mask. Do this in reverse block
3155 number order so that we are more likely for the first round to do
3156 useful work. We use AUX non-null to flag that the block is queued. */
3159 EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
3161 basic_block bb = BASIC_BLOCK (i);
3168 for (i = 0; i < n_basic_blocks; ++i)
3170 basic_block bb = BASIC_BLOCK (i);
3177 sbitmap_zero (blocks_out);
3179 while (qhead != qtail)
3181 int rescan, changed;
3190 /* Begin by propogating live_at_start from the successor blocks. */
3191 CLEAR_REG_SET (new_live_at_end);
3192 for (e = bb->succ; e; e = e->succ_next)
3194 basic_block sb = e->dest;
3195 IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
3198 /* Force the stack pointer to be live -- which might not already be
3199 the case for blocks within infinite loops. */
3200 SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
3202 /* Similarly for the frame pointer before reload. Any reference
3203 to any pseudo before reload is a potential reference of the
3205 if (! reload_completed)
3206 SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
3208 /* Regs used in phi nodes are not included in
3209 global_live_at_start, since they are live only along a
3210 particular edge. Set those regs that are live because of a
3211 phi node alternative corresponding to this particular block. */
3213 for_each_successor_phi (bb, &set_phi_alternative_reg,
3216 if (bb == ENTRY_BLOCK_PTR)
3218 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3222 /* On our first pass through this block, we'll go ahead and continue.
3223 Recognize first pass by local_set NULL. On subsequent passes, we
3224 get to skip out early if live_at_end wouldn't have changed. */
3226 if (bb->local_set == NULL)
3228 bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
3233 /* If any bits were removed from live_at_end, we'll have to
3234 rescan the block. This wouldn't be necessary if we had
3235 precalculated local_live, however with PROP_SCAN_DEAD_CODE
3236 local_live is really dependent on live_at_end. */
3237 CLEAR_REG_SET (tmp);
3238 rescan = bitmap_operation (tmp, bb->global_live_at_end,
3239 new_live_at_end, BITMAP_AND_COMPL);
3243 /* Find the set of changed bits. Take this opportunity
3244 to notice that this set is empty and early out. */
3245 CLEAR_REG_SET (tmp);
3246 changed = bitmap_operation (tmp, bb->global_live_at_end,
3247 new_live_at_end, BITMAP_XOR);
3251 /* If any of the changed bits overlap with local_set,
3252 we'll have to rescan the block. Detect overlap by
3253 the AND with ~local_set turning off bits. */
3254 rescan = bitmap_operation (tmp, tmp, bb->local_set,
3259 /* Let our caller know that BB changed enough to require its
3260 death notes updated. */
3262 SET_BIT (blocks_out, bb->index);
3266 /* Add to live_at_start the set of all registers in
3267 new_live_at_end that aren't in the old live_at_end. */
3269 bitmap_operation (tmp, new_live_at_end, bb->global_live_at_end,
3271 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3273 changed = bitmap_operation (bb->global_live_at_start,
3274 bb->global_live_at_start,
3281 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3283 /* Rescan the block insn by insn to turn (a copy of) live_at_end
3284 into live_at_start. */
3285 propagate_block (bb, new_live_at_end, bb->local_set, flags);
3287 /* If live_at start didn't change, no need to go farther. */
3288 if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
3291 COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
3294 /* Queue all predecessors of BB so that we may re-examine
3295 their live_at_end. */
3296 for (e = bb->pred; e; e = e->pred_next)
3298 basic_block pb = e->src;
3299 if (pb->aux == NULL)
3310 FREE_REG_SET (new_live_at_end);
3314 EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
3316 basic_block bb = BASIC_BLOCK (i);
3317 FREE_REG_SET (bb->local_set);
3322 for (i = n_basic_blocks - 1; i >= 0; --i)
3324 basic_block bb = BASIC_BLOCK (i);
3325 FREE_REG_SET (bb->local_set);
3332 /* Subroutines of life analysis. */
3334 /* Allocate the permanent data structures that represent the results
3335 of life analysis. Not static since used also for stupid life analysis. */
3338 allocate_bb_life_data ()
3342 for (i = 0; i < n_basic_blocks; i++)
3344 basic_block bb = BASIC_BLOCK (i);
3346 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
3347 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
3350 ENTRY_BLOCK_PTR->global_live_at_end
3351 = OBSTACK_ALLOC_REG_SET (function_obstack);
3352 EXIT_BLOCK_PTR->global_live_at_start
3353 = OBSTACK_ALLOC_REG_SET (function_obstack);
3355 regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
3359 allocate_reg_life_data ()
3363 max_regno = max_reg_num ();
3365 /* Recalculate the register space, in case it has grown. Old style
3366 vector oriented regsets would set regset_{size,bytes} here also. */
3367 allocate_reg_info (max_regno, FALSE, FALSE);
3369 /* Reset all the data we'll collect in propagate_block and its
3371 for (i = 0; i < max_regno; i++)
3375 REG_N_DEATHS (i) = 0;
3376 REG_N_CALLS_CROSSED (i) = 0;
3377 REG_LIVE_LENGTH (i) = 0;
3378 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
3382 /* Delete dead instructions for propagate_block. */
3385 propagate_block_delete_insn (bb, insn)
3389 rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
3391 /* If the insn referred to a label, and that label was attached to
3392 an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's
3393 pretty much mandatory to delete it, because the ADDR_VEC may be
3394 referencing labels that no longer exist. */
3398 rtx label = XEXP (inote, 0);
3401 if (LABEL_NUSES (label) == 1
3402 && (next = next_nonnote_insn (label)) != NULL
3403 && GET_CODE (next) == JUMP_INSN
3404 && (GET_CODE (PATTERN (next)) == ADDR_VEC
3405 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
3407 rtx pat = PATTERN (next);
3408 int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3409 int len = XVECLEN (pat, diff_vec_p);
3412 for (i = 0; i < len; i++)
3413 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
3415 flow_delete_insn (next);
3419 if (bb->end == insn)
3420 bb->end = PREV_INSN (insn);
3421 flow_delete_insn (insn);
3424 /* Delete dead libcalls for propagate_block. Return the insn
3425 before the libcall. */
3428 propagate_block_delete_libcall (bb, insn, note)
3432 rtx first = XEXP (note, 0);
3433 rtx before = PREV_INSN (first);
3435 if (insn == bb->end)
3438 flow_delete_insn_chain (first, insn);
3442 /* Update the life-status of regs for one insn. Return the previous insn. */
3445 propagate_one_insn (pbi, insn)
3446 struct propagate_block_info *pbi;
3449 rtx prev = PREV_INSN (insn);
3450 int flags = pbi->flags;
3451 int insn_is_dead = 0;
3452 int libcall_is_dead = 0;
3456 if (! INSN_P (insn))
3459 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3460 if (flags & PROP_SCAN_DEAD_CODE)
3462 insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
3464 libcall_is_dead = (insn_is_dead && note != 0
3465 && libcall_dead_p (pbi, note, insn));
3468 /* We almost certainly don't want to delete prologue or epilogue
3469 instructions. Warn about probable compiler losage. */
3472 && (((HAVE_epilogue || HAVE_prologue)
3473 && prologue_epilogue_contains (insn))
3474 || (HAVE_sibcall_epilogue
3475 && sibcall_epilogue_contains (insn)))
3476 && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
3478 if (flags & PROP_KILL_DEAD_CODE)
3480 warning ("ICE: would have deleted prologue/epilogue insn");
3481 if (!inhibit_warnings)
3484 libcall_is_dead = insn_is_dead = 0;
3487 /* If an instruction consists of just dead store(s) on final pass,
3489 if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
3491 /* Record sets. Do this even for dead instructions, since they
3492 would have killed the values if they hadn't been deleted. */
3493 mark_set_regs (pbi, PATTERN (insn), insn);
3495 /* CC0 is now known to be dead. Either this insn used it,
3496 in which case it doesn't anymore, or clobbered it,
3497 so the next insn can't use it. */
3500 if (libcall_is_dead)
3502 prev = propagate_block_delete_libcall (pbi->bb, insn, note);
3503 insn = NEXT_INSN (prev);
3506 propagate_block_delete_insn (pbi->bb, insn);
3511 /* See if this is an increment or decrement that can be merged into
3512 a following memory address. */
3515 register rtx x = single_set (insn);
3517 /* Does this instruction increment or decrement a register? */
3518 if ((flags & PROP_AUTOINC)
3520 && GET_CODE (SET_DEST (x)) == REG
3521 && (GET_CODE (SET_SRC (x)) == PLUS
3522 || GET_CODE (SET_SRC (x)) == MINUS)
3523 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
3524 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
3525 /* Ok, look for a following memory ref we can combine with.
3526 If one is found, change the memory ref to a PRE_INC
3527 or PRE_DEC, cancel this insn, and return 1.
3528 Return 0 if nothing has been done. */
3529 && try_pre_increment_1 (pbi, insn))
3532 #endif /* AUTO_INC_DEC */
3534 CLEAR_REG_SET (pbi->new_set);
3536 /* If this is not the final pass, and this insn is copying the value of
3537 a library call and it's dead, don't scan the insns that perform the
3538 library call, so that the call's arguments are not marked live. */
3539 if (libcall_is_dead)
3541 /* Record the death of the dest reg. */
3542 mark_set_regs (pbi, PATTERN (insn), insn);
3544 insn = XEXP (note, 0);
3545 return PREV_INSN (insn);
3547 else if (GET_CODE (PATTERN (insn)) == SET
3548 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
3549 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
3550 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
3551 && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
3552 /* We have an insn to pop a constant amount off the stack.
3553 (Such insns use PLUS regardless of the direction of the stack,
3554 and any insn to adjust the stack by a constant is always a pop.)
3555 These insns, if not dead stores, have no effect on life. */
3559 /* Any regs live at the time of a call instruction must not go
3560 in a register clobbered by calls. Find all regs now live and
3561 record this for them. */
3563 if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
3564 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3565 { REG_N_CALLS_CROSSED (i)++; });
3567 /* Record sets. Do this even for dead instructions, since they
3568 would have killed the values if they hadn't been deleted. */
3569 mark_set_regs (pbi, PATTERN (insn), insn);
3571 if (GET_CODE (insn) == CALL_INSN)
3577 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3578 cond = COND_EXEC_TEST (PATTERN (insn));
3580 /* Non-constant calls clobber memory. */
3581 if (! CONST_CALL_P (insn))
3582 free_EXPR_LIST_list (&pbi->mem_set_list);
3584 /* There may be extra registers to be clobbered. */
3585 for (note = CALL_INSN_FUNCTION_USAGE (insn);
3587 note = XEXP (note, 1))
3588 if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3589 mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
3590 cond, insn, pbi->flags);
3592 /* Calls change all call-used and global registers. */
3593 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3594 if (call_used_regs[i] && ! global_regs[i]
3597 /* We do not want REG_UNUSED notes for these registers. */
3598 mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
3600 pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
3604 /* If an insn doesn't use CC0, it becomes dead since we assume
3605 that every insn clobbers it. So show it dead here;
3606 mark_used_regs will set it live if it is referenced. */
3611 mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
3613 /* Sometimes we may have inserted something before INSN (such as a move)
3614 when we make an auto-inc. So ensure we will scan those insns. */
3616 prev = PREV_INSN (insn);
3619 if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
3625 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3626 cond = COND_EXEC_TEST (PATTERN (insn));
3628 /* Calls use their arguments. */
3629 for (note = CALL_INSN_FUNCTION_USAGE (insn);
3631 note = XEXP (note, 1))
3632 if (GET_CODE (XEXP (note, 0)) == USE)
3633 mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
3636 /* The stack ptr is used (honorarily) by a CALL insn. */
3637 SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
3639 /* Calls may also reference any of the global registers,
3640 so they are made live. */
3641 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3643 mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
3648 /* On final pass, update counts of how many insns in which each reg
3650 if (flags & PROP_REG_INFO)
3651 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3652 { REG_LIVE_LENGTH (i)++; });
3657 /* Initialize a propagate_block_info struct for public consumption.
3658 Note that the structure itself is opaque to this file, but that
3659 the user can use the regsets provided here. */
3661 struct propagate_block_info *
3662 init_propagate_block_info (bb, live, local_set, flags)
3668 struct propagate_block_info *pbi = xmalloc (sizeof (*pbi));
3671 pbi->reg_live = live;
3672 pbi->mem_set_list = NULL_RTX;
3673 pbi->local_set = local_set;
3677 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3678 pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
3680 pbi->reg_next_use = NULL;
3682 pbi->new_set = BITMAP_XMALLOC ();
3684 #ifdef HAVE_conditional_execution
3685 pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
3686 free_reg_cond_life_info);
3687 pbi->reg_cond_reg = BITMAP_XMALLOC ();
3689 /* If this block ends in a conditional branch, for each register live
3690 from one side of the branch and not the other, record the register
3691 as conditionally dead. */
3692 if ((flags & (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE))
3693 && GET_CODE (bb->end) == JUMP_INSN
3694 && any_condjump_p (bb->end))
3696 regset_head diff_head;
3697 regset diff = INITIALIZE_REG_SET (diff_head);
3698 basic_block bb_true, bb_false;
3699 rtx cond_true, cond_false, set_src;
3702 /* Identify the successor blocks. */
3703 bb_true = bb->succ->dest;
3704 if (bb->succ->succ_next != NULL)
3706 bb_false = bb->succ->succ_next->dest;
3708 if (bb->succ->flags & EDGE_FALLTHRU)
3710 basic_block t = bb_false;
3714 else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
3719 /* This can happen with a conditional jump to the next insn. */
3720 if (JUMP_LABEL (bb->end) != bb_true->head)
3723 /* Simplest way to do nothing. */
3727 /* Extract the condition from the branch. */
3728 set_src = SET_SRC (pc_set (bb->end));
3729 cond_true = XEXP (set_src, 0);
3730 cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
3731 GET_MODE (cond_true), XEXP (cond_true, 0),
3732 XEXP (cond_true, 1));
3733 if (GET_CODE (XEXP (set_src, 1)) == PC)
3736 cond_false = cond_true;
3740 /* Compute which register lead different lives in the successors. */
3741 if (bitmap_operation (diff, bb_true->global_live_at_start,
3742 bb_false->global_live_at_start, BITMAP_XOR))
3744 rtx reg = XEXP (cond_true, 0);
3746 if (GET_CODE (reg) == SUBREG)
3747 reg = SUBREG_REG (reg);
3749 if (GET_CODE (reg) != REG)
3752 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg));
3754 /* For each such register, mark it conditionally dead. */
3755 EXECUTE_IF_SET_IN_REG_SET
3758 struct reg_cond_life_info *rcli;
3761 rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
3763 if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
3767 rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
3769 splay_tree_insert (pbi->reg_cond_dead, i,
3770 (splay_tree_value) rcli);
3774 FREE_REG_SET (diff);
3778 /* If this block has no successors, any stores to the frame that aren't
3779 used later in the block are dead. So make a pass over the block
3780 recording any such that are made and show them dead at the end. We do
3781 a very conservative and simple job here. */
3783 && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
3784 && (TYPE_RETURNS_STACK_DEPRESSED
3785 (TREE_TYPE (current_function_decl))))
3786 && (flags & PROP_SCAN_DEAD_CODE)
3787 && (bb->succ == NULL
3788 || (bb->succ->succ_next == NULL
3789 && bb->succ->dest == EXIT_BLOCK_PTR)))
3792 for (insn = bb->end; insn != bb->head; insn = PREV_INSN (insn))
3793 if (GET_CODE (insn) == INSN
3794 && GET_CODE (PATTERN (insn)) == SET
3795 && GET_CODE (SET_DEST (PATTERN (insn))) == MEM)
3797 rtx mem = SET_DEST (PATTERN (insn));
3799 if (XEXP (mem, 0) == frame_pointer_rtx
3800 || (GET_CODE (XEXP (mem, 0)) == PLUS
3801 && XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx
3802 && GET_CODE (XEXP (XEXP (mem, 0), 1)) == CONST_INT))
3803 pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
3810 /* Release a propagate_block_info struct. */
3813 free_propagate_block_info (pbi)
3814 struct propagate_block_info *pbi;
3816 free_EXPR_LIST_list (&pbi->mem_set_list);
3818 BITMAP_XFREE (pbi->new_set);
3820 #ifdef HAVE_conditional_execution
3821 splay_tree_delete (pbi->reg_cond_dead);
3822 BITMAP_XFREE (pbi->reg_cond_reg);
3825 if (pbi->reg_next_use)
3826 free (pbi->reg_next_use);
3831 /* Compute the registers live at the beginning of a basic block BB from
3832 those live at the end.
3834 When called, REG_LIVE contains those live at the end. On return, it
3835 contains those live at the beginning.
3837 LOCAL_SET, if non-null, will be set with all registers killed by
3838 this basic block. */
3841 propagate_block (bb, live, local_set, flags)
3847 struct propagate_block_info *pbi;
3850 pbi = init_propagate_block_info (bb, live, local_set, flags);
3852 if (flags & PROP_REG_INFO)
3856 /* Process the regs live at the end of the block.
3857 Mark them as not local to any one basic block. */
3858 EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
3859 { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
3862 /* Scan the block an insn at a time from end to beginning. */
3864 for (insn = bb->end;; insn = prev)
3866 /* If this is a call to `setjmp' et al, warn if any
3867 non-volatile datum is live. */
3868 if ((flags & PROP_REG_INFO)
3869 && GET_CODE (insn) == NOTE
3870 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3871 IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
3873 prev = propagate_one_insn (pbi, insn);
3875 if (insn == bb->head)
3879 free_propagate_block_info (pbi);
3882 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3883 (SET expressions whose destinations are registers dead after the insn).
3884 NEEDED is the regset that says which regs are alive after the insn.
3886 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3888 If X is the entire body of an insn, NOTES contains the reg notes
3889 pertaining to the insn. */
3892 insn_dead_p (pbi, x, call_ok, notes)
3893 struct propagate_block_info *pbi;
3896 rtx notes ATTRIBUTE_UNUSED;
3898 enum rtx_code code = GET_CODE (x);
3901 /* If flow is invoked after reload, we must take existing AUTO_INC
3902 expresions into account. */
3903 if (reload_completed)
3905 for (; notes; notes = XEXP (notes, 1))
3907 if (REG_NOTE_KIND (notes) == REG_INC)
3909 int regno = REGNO (XEXP (notes, 0));
3911 /* Don't delete insns to set global regs. */
3912 if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3913 || REGNO_REG_SET_P (pbi->reg_live, regno))
3920 /* If setting something that's a reg or part of one,
3921 see if that register's altered value will be live. */
3925 rtx r = SET_DEST (x);
3928 if (GET_CODE (r) == CC0)
3929 return ! pbi->cc0_live;
3932 /* A SET that is a subroutine call cannot be dead. */
3933 if (GET_CODE (SET_SRC (x)) == CALL)
3939 /* Don't eliminate loads from volatile memory or volatile asms. */
3940 else if (volatile_refs_p (SET_SRC (x)))
3943 if (GET_CODE (r) == MEM)
3947 if (MEM_VOLATILE_P (r))
3950 /* Walk the set of memory locations we are currently tracking
3951 and see if one is an identical match to this memory location.
3952 If so, this memory write is dead (remember, we're walking
3953 backwards from the end of the block to the start). */
3954 temp = pbi->mem_set_list;
3957 if (rtx_equal_p (XEXP (temp, 0), r))
3959 temp = XEXP (temp, 1);
3964 while (GET_CODE (r) == SUBREG
3965 || GET_CODE (r) == STRICT_LOW_PART
3966 || GET_CODE (r) == ZERO_EXTRACT)
3969 if (GET_CODE (r) == REG)
3971 int regno = REGNO (r);
3974 if (REGNO_REG_SET_P (pbi->reg_live, regno))
3977 /* If this is a hard register, verify that subsequent
3978 words are not needed. */
3979 if (regno < FIRST_PSEUDO_REGISTER)
3981 int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
3984 if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
3988 /* Don't delete insns to set global regs. */
3989 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3992 /* Make sure insns to set the stack pointer aren't deleted. */
3993 if (regno == STACK_POINTER_REGNUM)
3996 /* Make sure insns to set the frame pointer aren't deleted. */
3997 if (regno == FRAME_POINTER_REGNUM
3998 && (! reload_completed || frame_pointer_needed))
4000 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4001 if (regno == HARD_FRAME_POINTER_REGNUM
4002 && (! reload_completed || frame_pointer_needed))
4006 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4007 /* Make sure insns to set arg pointer are never deleted
4008 (if the arg pointer isn't fixed, there will be a USE
4009 for it, so we can treat it normally). */
4010 if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4014 #ifdef PIC_OFFSET_TABLE_REGNUM
4015 /* Before reload, do not allow sets of the pic register
4016 to be deleted. Reload can insert references to
4017 constant pool memory anywhere in the function, making
4018 the PIC register live where it wasn't before. */
4019 if (regno == PIC_OFFSET_TABLE_REGNUM && fixed_regs[regno]
4020 && ! reload_completed)
4024 /* Otherwise, the set is dead. */
4030 /* If performing several activities, insn is dead if each activity
4031 is individually dead. Also, CLOBBERs and USEs can be ignored; a
4032 CLOBBER or USE that's inside a PARALLEL doesn't make the insn
4034 else if (code == PARALLEL)
4036 int i = XVECLEN (x, 0);
4038 for (i--; i >= 0; i--)
4039 if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
4040 && GET_CODE (XVECEXP (x, 0, i)) != USE
4041 && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
4047 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
4048 is not necessarily true for hard registers. */
4049 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
4050 && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
4051 && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
4054 /* We do not check other CLOBBER or USE here. An insn consisting of just
4055 a CLOBBER or just a USE should not be deleted. */
4059 /* If INSN is the last insn in a libcall, and assuming INSN is dead,
4060 return 1 if the entire library call is dead.
4061 This is true if INSN copies a register (hard or pseudo)
4062 and if the hard return reg of the call insn is dead.
4063 (The caller should have tested the destination of the SET inside
4064 INSN already for death.)
4066 If this insn doesn't just copy a register, then we don't
4067 have an ordinary libcall. In that case, cse could not have
4068 managed to substitute the source for the dest later on,
4069 so we can assume the libcall is dead.
4071 PBI is the block info giving pseudoregs live before this insn.
4072 NOTE is the REG_RETVAL note of the insn. */
4075 libcall_dead_p (pbi, note, insn)
4076 struct propagate_block_info *pbi;
4080 rtx x = single_set (insn);
4084 register rtx r = SET_SRC (x);
4085 if (GET_CODE (r) == REG)
4087 rtx call = XEXP (note, 0);
4091 /* Find the call insn. */
4092 while (call != insn && GET_CODE (call) != CALL_INSN)
4093 call = NEXT_INSN (call);
4095 /* If there is none, do nothing special,
4096 since ordinary death handling can understand these insns. */
4100 /* See if the hard reg holding the value is dead.
4101 If this is a PARALLEL, find the call within it. */
4102 call_pat = PATTERN (call);
4103 if (GET_CODE (call_pat) == PARALLEL)
4105 for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
4106 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
4107 && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
4110 /* This may be a library call that is returning a value
4111 via invisible pointer. Do nothing special, since
4112 ordinary death handling can understand these insns. */
4116 call_pat = XVECEXP (call_pat, 0, i);
4119 return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
4125 /* Return 1 if register REGNO was used before it was set, i.e. if it is
4126 live at function entry. Don't count global register variables, variables
4127 in registers that can be used for function arg passing, or variables in
4128 fixed hard registers. */
4131 regno_uninitialized (regno)
4134 if (n_basic_blocks == 0
4135 || (regno < FIRST_PSEUDO_REGISTER
4136 && (global_regs[regno]
4137 || fixed_regs[regno]
4138 || FUNCTION_ARG_REGNO_P (regno))))
4141 return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno);
4144 /* 1 if register REGNO was alive at a place where `setjmp' was called
4145 and was set more than once or is an argument.
4146 Such regs may be clobbered by `longjmp'. */
4149 regno_clobbered_at_setjmp (regno)
4152 if (n_basic_blocks == 0)
4155 return ((REG_N_SETS (regno) > 1
4156 || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno))
4157 && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
4160 /* INSN references memory, possibly using autoincrement addressing modes.
4161 Find any entries on the mem_set_list that need to be invalidated due
4162 to an address change. */
4165 invalidate_mems_from_autoinc (pbi, insn)
4166 struct propagate_block_info *pbi;
4169 rtx note = REG_NOTES (insn);
4170 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
4172 if (REG_NOTE_KIND (note) == REG_INC)
4174 rtx temp = pbi->mem_set_list;
4175 rtx prev = NULL_RTX;
4180 next = XEXP (temp, 1);
4181 if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
4183 /* Splice temp out of list. */
4185 XEXP (prev, 1) = next;
4187 pbi->mem_set_list = next;
4188 free_EXPR_LIST_node (temp);
4198 /* Process the registers that are set within X. Their bits are set to
4199 1 in the regset DEAD, because they are dead prior to this insn.
4201 If INSN is nonzero, it is the insn being processed.
4203 FLAGS is the set of operations to perform. */
4206 mark_set_regs (pbi, x, insn)
4207 struct propagate_block_info *pbi;
4210 rtx cond = NULL_RTX;
4215 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4217 if (REG_NOTE_KIND (link) == REG_INC)
4218 mark_set_1 (pbi, SET, XEXP (link, 0),
4219 (GET_CODE (x) == COND_EXEC
4220 ? COND_EXEC_TEST (x) : NULL_RTX),
4224 switch (code = GET_CODE (x))
4228 mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
4232 cond = COND_EXEC_TEST (x);
4233 x = COND_EXEC_CODE (x);
4239 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4241 rtx sub = XVECEXP (x, 0, i);
4242 switch (code = GET_CODE (sub))
4245 if (cond != NULL_RTX)
4248 cond = COND_EXEC_TEST (sub);
4249 sub = COND_EXEC_CODE (sub);
4250 if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
4256 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
4271 /* Process a single SET rtx, X. */
4274 mark_set_1 (pbi, code, reg, cond, insn, flags)
4275 struct propagate_block_info *pbi;
4277 rtx reg, cond, insn;
4280 int regno_first = -1, regno_last = -1;
4284 /* Some targets place small structures in registers for
4285 return values of functions. We have to detect this
4286 case specially here to get correct flow information. */
4287 if (GET_CODE (reg) == PARALLEL
4288 && GET_MODE (reg) == BLKmode)
4290 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4291 mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
4295 /* Modifying just one hardware register of a multi-reg value or just a
4296 byte field of a register does not mean the value from before this insn
4297 is now dead. Of course, if it was dead after it's unused now. */
4299 switch (GET_CODE (reg))
4303 case STRICT_LOW_PART:
4304 /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */
4306 reg = XEXP (reg, 0);
4307 while (GET_CODE (reg) == SUBREG
4308 || GET_CODE (reg) == ZERO_EXTRACT
4309 || GET_CODE (reg) == SIGN_EXTRACT
4310 || GET_CODE (reg) == STRICT_LOW_PART);
4311 if (GET_CODE (reg) == MEM)
4313 not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
4317 regno_last = regno_first = REGNO (reg);
4318 if (regno_first < FIRST_PSEUDO_REGISTER)
4319 regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
4323 if (GET_CODE (SUBREG_REG (reg)) == REG)
4325 enum machine_mode outer_mode = GET_MODE (reg);
4326 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
4328 /* Identify the range of registers affected. This is moderately
4329 tricky for hard registers. See alter_subreg. */
4331 regno_last = regno_first = REGNO (SUBREG_REG (reg));
4332 if (regno_first < FIRST_PSEUDO_REGISTER)
4334 #ifdef ALTER_HARD_SUBREG
4335 regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
4336 inner_mode, regno_first);
4338 regno_first += SUBREG_WORD (reg);
4340 regno_last = (regno_first
4341 + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
4343 /* Since we've just adjusted the register number ranges, make
4344 sure REG matches. Otherwise some_was_live will be clear
4345 when it shouldn't have been, and we'll create incorrect
4346 REG_UNUSED notes. */
4347 reg = gen_rtx_REG (outer_mode, regno_first);
4351 /* If the number of words in the subreg is less than the number
4352 of words in the full register, we have a well-defined partial
4353 set. Otherwise the high bits are undefined.
4355 This is only really applicable to pseudos, since we just took
4356 care of multi-word hard registers. */
4357 if (((GET_MODE_SIZE (outer_mode)
4358 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
4359 < ((GET_MODE_SIZE (inner_mode)
4360 + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
4361 not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
4363 reg = SUBREG_REG (reg);
4367 reg = SUBREG_REG (reg);
4374 /* If this set is a MEM, then it kills any aliased writes.
4375 If this set is a REG, then it kills any MEMs which use the reg. */
4376 if (optimize && (flags & PROP_SCAN_DEAD_CODE))
4378 if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
4380 rtx temp = pbi->mem_set_list;
4381 rtx prev = NULL_RTX;
4386 next = XEXP (temp, 1);
4387 if ((GET_CODE (reg) == MEM
4388 && output_dependence (XEXP (temp, 0), reg))
4389 || (GET_CODE (reg) == REG
4390 && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
4392 /* Splice this entry out of the list. */
4394 XEXP (prev, 1) = next;
4396 pbi->mem_set_list = next;
4397 free_EXPR_LIST_node (temp);
4405 /* If the memory reference had embedded side effects (autoincrement
4406 address modes. Then we may need to kill some entries on the
4408 if (insn && GET_CODE (reg) == MEM)
4409 invalidate_mems_from_autoinc (pbi, insn);
4411 if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
4412 /* ??? With more effort we could track conditional memory life. */
4414 /* We do not know the size of a BLKmode store, so we do not track
4415 them for redundant store elimination. */
4416 && GET_MODE (reg) != BLKmode
4417 /* There are no REG_INC notes for SP, so we can't assume we'll see
4418 everything that invalidates it. To be safe, don't eliminate any
4419 stores though SP; none of them should be redundant anyway. */
4420 && ! reg_mentioned_p (stack_pointer_rtx, reg))
4421 pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
4424 if (GET_CODE (reg) == REG
4425 && ! (regno_first == FRAME_POINTER_REGNUM
4426 && (! reload_completed || frame_pointer_needed))
4427 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4428 && ! (regno_first == HARD_FRAME_POINTER_REGNUM
4429 && (! reload_completed || frame_pointer_needed))
4431 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4432 && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
4436 int some_was_live = 0, some_was_dead = 0;
4438 for (i = regno_first; i <= regno_last; ++i)
4440 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
4442 SET_REGNO_REG_SET (pbi->local_set, i);
4443 if (code != CLOBBER)
4444 SET_REGNO_REG_SET (pbi->new_set, i);
4446 some_was_live |= needed_regno;
4447 some_was_dead |= ! needed_regno;
4450 #ifdef HAVE_conditional_execution
4451 /* Consider conditional death in deciding that the register needs
4453 if (some_was_live && ! not_dead
4454 /* The stack pointer is never dead. Well, not strictly true,
4455 but it's very difficult to tell from here. Hopefully
4456 combine_stack_adjustments will fix up the most egregious
4458 && regno_first != STACK_POINTER_REGNUM)
4460 for (i = regno_first; i <= regno_last; ++i)
4461 if (! mark_regno_cond_dead (pbi, i, cond))
4466 /* Additional data to record if this is the final pass. */
4467 if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
4468 | PROP_DEATH_NOTES | PROP_AUTOINC))
4471 register int blocknum = pbi->bb->index;
4474 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4476 y = pbi->reg_next_use[regno_first];
4478 /* The next use is no longer next, since a store intervenes. */
4479 for (i = regno_first; i <= regno_last; ++i)
4480 pbi->reg_next_use[i] = 0;
4483 if (flags & PROP_REG_INFO)
4485 for (i = regno_first; i <= regno_last; ++i)
4487 /* Count (weighted) references, stores, etc. This counts a
4488 register twice if it is modified, but that is correct. */
4489 REG_N_SETS (i) += 1;
4490 REG_N_REFS (i) += (optimize_size ? 1
4491 : pbi->bb->loop_depth + 1);
4493 /* The insns where a reg is live are normally counted
4494 elsewhere, but we want the count to include the insn
4495 where the reg is set, and the normal counting mechanism
4496 would not count it. */
4497 REG_LIVE_LENGTH (i) += 1;
4500 /* If this is a hard reg, record this function uses the reg. */
4501 if (regno_first < FIRST_PSEUDO_REGISTER)
4503 for (i = regno_first; i <= regno_last; i++)
4504 regs_ever_live[i] = 1;
4508 /* Keep track of which basic blocks each reg appears in. */
4509 if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
4510 REG_BASIC_BLOCK (regno_first) = blocknum;
4511 else if (REG_BASIC_BLOCK (regno_first) != blocknum)
4512 REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
4516 if (! some_was_dead)
4518 if (flags & PROP_LOG_LINKS)
4520 /* Make a logical link from the next following insn
4521 that uses this register, back to this insn.
4522 The following insns have already been processed.
4524 We don't build a LOG_LINK for hard registers containing
4525 in ASM_OPERANDs. If these registers get replaced,
4526 we might wind up changing the semantics of the insn,
4527 even if reload can make what appear to be valid
4528 assignments later. */
4529 if (y && (BLOCK_NUM (y) == blocknum)
4530 && (regno_first >= FIRST_PSEUDO_REGISTER
4531 || asm_noperands (PATTERN (y)) < 0))
4532 LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
4537 else if (! some_was_live)
4539 if (flags & PROP_REG_INFO)
4540 REG_N_DEATHS (regno_first) += 1;
4542 if (flags & PROP_DEATH_NOTES)
4544 /* Note that dead stores have already been deleted
4545 when possible. If we get here, we have found a
4546 dead store that cannot be eliminated (because the
4547 same insn does something useful). Indicate this
4548 by marking the reg being set as dying here. */
4550 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4555 if (flags & PROP_DEATH_NOTES)
4557 /* This is a case where we have a multi-word hard register
4558 and some, but not all, of the words of the register are
4559 needed in subsequent insns. Write REG_UNUSED notes
4560 for those parts that were not needed. This case should
4563 for (i = regno_first; i <= regno_last; ++i)
4564 if (! REGNO_REG_SET_P (pbi->reg_live, i))
4566 = alloc_EXPR_LIST (REG_UNUSED,
4567 gen_rtx_REG (reg_raw_mode[i], i),
4573 /* Mark the register as being dead. */
4576 /* The stack pointer is never dead. Well, not strictly true,
4577 but it's very difficult to tell from here. Hopefully
4578 combine_stack_adjustments will fix up the most egregious
4580 && regno_first != STACK_POINTER_REGNUM)
4582 for (i = regno_first; i <= regno_last; ++i)
4583 CLEAR_REGNO_REG_SET (pbi->reg_live, i);
4586 else if (GET_CODE (reg) == REG)
4588 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4589 pbi->reg_next_use[regno_first] = 0;
4592 /* If this is the last pass and this is a SCRATCH, show it will be dying
4593 here and count it. */
4594 else if (GET_CODE (reg) == SCRATCH)
4596 if (flags & PROP_DEATH_NOTES)
4598 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4602 #ifdef HAVE_conditional_execution
4603 /* Mark REGNO conditionally dead.
4604 Return true if the register is now unconditionally dead. */
4607 mark_regno_cond_dead (pbi, regno, cond)
4608 struct propagate_block_info *pbi;
4612 /* If this is a store to a predicate register, the value of the
4613 predicate is changing, we don't know that the predicate as seen
4614 before is the same as that seen after. Flush all dependent
4615 conditions from reg_cond_dead. This will make all such
4616 conditionally live registers unconditionally live. */
4617 if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
4618 flush_reg_cond_reg (pbi, regno);
4620 /* If this is an unconditional store, remove any conditional
4621 life that may have existed. */
4622 if (cond == NULL_RTX)
4623 splay_tree_remove (pbi->reg_cond_dead, regno);
4626 splay_tree_node node;
4627 struct reg_cond_life_info *rcli;
4630 /* Otherwise this is a conditional set. Record that fact.
4631 It may have been conditionally used, or there may be a
4632 subsequent set with a complimentary condition. */
4634 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
4637 /* The register was unconditionally live previously.
4638 Record the current condition as the condition under
4639 which it is dead. */
4640 rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
4641 rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
4642 splay_tree_insert (pbi->reg_cond_dead, regno,
4643 (splay_tree_value) rcli);
4645 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
4647 /* Not unconditionaly dead. */
4652 /* The register was conditionally live previously.
4653 Add the new condition to the old. */
4654 rcli = (struct reg_cond_life_info *) node->value;
4655 ncond = rcli->condition;
4656 ncond = ior_reg_cond (ncond, cond);
4658 /* If the register is now unconditionally dead,
4659 remove the entry in the splay_tree. */
4660 if (ncond == const1_rtx)
4661 splay_tree_remove (pbi->reg_cond_dead, regno);
4664 rcli->condition = ncond;
4666 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
4668 /* Not unconditionaly dead. */
4677 /* Called from splay_tree_delete for pbi->reg_cond_life. */
4680 free_reg_cond_life_info (value)
4681 splay_tree_value value;
4683 struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
4684 free_EXPR_LIST_list (&rcli->condition);
4688 /* Helper function for flush_reg_cond_reg. */
4691 flush_reg_cond_reg_1 (node, data)
4692 splay_tree_node node;
4695 struct reg_cond_life_info *rcli;
4696 int *xdata = (int *) data;
4697 unsigned int regno = xdata[0];
4700 /* Don't need to search if last flushed value was farther on in
4701 the in-order traversal. */
4702 if (xdata[1] >= (int) node->key)
4705 /* Splice out portions of the expression that refer to regno. */
4706 rcli = (struct reg_cond_life_info *) node->value;
4707 c = *(prev = &rcli->condition);
4710 if (regno == REGNO (XEXP (XEXP (c, 0), 0)))
4712 rtx next = XEXP (c, 1);
4713 free_EXPR_LIST_node (c);
4717 c = *(prev = &XEXP (c, 1));
4720 /* If the entire condition is now NULL, signal the node to be removed. */
4721 if (! rcli->condition)
4723 xdata[1] = node->key;
4730 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
4733 flush_reg_cond_reg (pbi, regno)
4734 struct propagate_block_info *pbi;
4741 while (splay_tree_foreach (pbi->reg_cond_dead,
4742 flush_reg_cond_reg_1, pair) == -1)
4743 splay_tree_remove (pbi->reg_cond_dead, pair[1]);
4745 CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
4748 /* Logical arithmetic on predicate conditions. IOR, NOT and NAND.
4749 We actually use EXPR_LIST to chain the sub-expressions together
4750 instead of IOR because it's easier to manipulate and we have
4751 the lists.c functions to reuse nodes.
4753 Return a new rtl expression as appropriate. */
4756 ior_reg_cond (old, x)
4759 enum rtx_code x_code;
4763 /* We expect these conditions to be of the form (eq reg 0). */
4764 x_code = GET_CODE (x);
4765 if (GET_RTX_CLASS (x_code) != '<'
4766 || GET_CODE (x_reg = XEXP (x, 0)) != REG
4767 || XEXP (x, 1) != const0_rtx)
4770 /* Search the expression for an existing sub-expression of X_REG. */
4771 for (c = old; c; c = XEXP (c, 1))
4773 rtx y = XEXP (c, 0);
4774 if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4776 /* If we find X already present in OLD, we need do nothing. */
4777 if (GET_CODE (y) == x_code)
4780 /* If we find X being a compliment of a condition in OLD,
4781 then the entire condition is true. */
4782 if (GET_CODE (y) == reverse_condition (x_code))
4787 /* Otherwise just add to the chain. */
4788 return alloc_EXPR_LIST (0, x, old);
4795 enum rtx_code x_code;
4798 /* We expect these conditions to be of the form (eq reg 0). */
4799 x_code = GET_CODE (x);
4800 if (GET_RTX_CLASS (x_code) != '<'
4801 || GET_CODE (x_reg = XEXP (x, 0)) != REG
4802 || XEXP (x, 1) != const0_rtx)
4805 return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4806 VOIDmode, x_reg, const0_rtx),
4811 nand_reg_cond (old, x)
4814 enum rtx_code x_code;
4818 /* We expect these conditions to be of the form (eq reg 0). */
4819 x_code = GET_CODE (x);
4820 if (GET_RTX_CLASS (x_code) != '<'
4821 || GET_CODE (x_reg = XEXP (x, 0)) != REG
4822 || XEXP (x, 1) != const0_rtx)
4825 /* Search the expression for an existing sub-expression of X_REG. */
4827 for (c = *(prev = &old); c; c = *(prev = &XEXP (c, 1)))
4829 rtx y = XEXP (c, 0);
4830 if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4832 /* If we find X already present in OLD, then we need to
4834 if (GET_CODE (y) == x_code)
4836 *prev = XEXP (c, 1);
4837 free_EXPR_LIST_node (c);
4838 return old ? old : const0_rtx;
4841 /* If we find X being a compliment of a condition in OLD,
4842 then we need do nothing. */
4843 if (GET_CODE (y) == reverse_condition (x_code))
4848 /* Otherwise, by implication, the register in question is now live for
4849 the inverse of the condition X. */
4850 return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4851 VOIDmode, x_reg, const0_rtx),
4854 #endif /* HAVE_conditional_execution */
4858 /* Try to substitute the auto-inc expression INC as the address inside
4859 MEM which occurs in INSN. Currently, the address of MEM is an expression
4860 involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
4861 that has a single set whose source is a PLUS of INCR_REG and something
4865 attempt_auto_inc (pbi, inc, insn, mem, incr, incr_reg)
4866 struct propagate_block_info *pbi;
4867 rtx inc, insn, mem, incr, incr_reg;
4869 int regno = REGNO (incr_reg);
4870 rtx set = single_set (incr);
4871 rtx q = SET_DEST (set);
4872 rtx y = SET_SRC (set);
4873 int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
4875 /* Make sure this reg appears only once in this insn. */
4876 if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
4879 if (dead_or_set_p (incr, incr_reg)
4880 /* Mustn't autoinc an eliminable register. */
4881 && (regno >= FIRST_PSEUDO_REGISTER
4882 || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
4884 /* This is the simple case. Try to make the auto-inc. If
4885 we can't, we are done. Otherwise, we will do any
4886 needed updates below. */
4887 if (! validate_change (insn, &XEXP (mem, 0), inc, 0))
4890 else if (GET_CODE (q) == REG
4891 /* PREV_INSN used here to check the semi-open interval
4893 && ! reg_used_between_p (q, PREV_INSN (insn), incr)
4894 /* We must also check for sets of q as q may be
4895 a call clobbered hard register and there may
4896 be a call between PREV_INSN (insn) and incr. */
4897 && ! reg_set_between_p (q, PREV_INSN (insn), incr))
4899 /* We have *p followed sometime later by q = p+size.
4900 Both p and q must be live afterward,
4901 and q is not used between INSN and its assignment.
4902 Change it to q = p, ...*q..., q = q+size.
4903 Then fall into the usual case. */
4907 emit_move_insn (q, incr_reg);
4908 insns = get_insns ();
4911 if (basic_block_for_insn)
4912 for (temp = insns; temp; temp = NEXT_INSN (temp))
4913 set_block_for_insn (temp, pbi->bb);
4915 /* If we can't make the auto-inc, or can't make the
4916 replacement into Y, exit. There's no point in making
4917 the change below if we can't do the auto-inc and doing
4918 so is not correct in the pre-inc case. */
4921 validate_change (insn, &XEXP (mem, 0), inc, 1);
4922 validate_change (incr, &XEXP (y, opnum), q, 1);
4923 if (! apply_change_group ())
4926 /* We now know we'll be doing this change, so emit the
4927 new insn(s) and do the updates. */
4928 emit_insns_before (insns, insn);
4930 if (pbi->bb->head == insn)
4931 pbi->bb->head = insns;
4933 /* INCR will become a NOTE and INSN won't contain a
4934 use of INCR_REG. If a use of INCR_REG was just placed in
4935 the insn before INSN, make that the next use.
4936 Otherwise, invalidate it. */
4937 if (GET_CODE (PREV_INSN (insn)) == INSN
4938 && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
4939 && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg)
4940 pbi->reg_next_use[regno] = PREV_INSN (insn);
4942 pbi->reg_next_use[regno] = 0;
4947 /* REGNO is now used in INCR which is below INSN, but
4948 it previously wasn't live here. If we don't mark
4949 it as live, we'll put a REG_DEAD note for it
4950 on this insn, which is incorrect. */
4951 SET_REGNO_REG_SET (pbi->reg_live, regno);
4953 /* If there are any calls between INSN and INCR, show
4954 that REGNO now crosses them. */
4955 for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
4956 if (GET_CODE (temp) == CALL_INSN)
4957 REG_N_CALLS_CROSSED (regno)++;
4962 /* If we haven't returned, it means we were able to make the
4963 auto-inc, so update the status. First, record that this insn
4964 has an implicit side effect. */
4966 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn));
4968 /* Modify the old increment-insn to simply copy
4969 the already-incremented value of our register. */
4970 if (! validate_change (incr, &SET_SRC (set), incr_reg, 0))
4973 /* If that makes it a no-op (copying the register into itself) delete
4974 it so it won't appear to be a "use" and a "set" of this
4976 if (REGNO (SET_DEST (set)) == REGNO (incr_reg))
4978 /* If the original source was dead, it's dead now. */
4981 while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX)
4983 remove_note (incr, note);
4984 if (XEXP (note, 0) != incr_reg)
4985 CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
4988 PUT_CODE (incr, NOTE);
4989 NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
4990 NOTE_SOURCE_FILE (incr) = 0;
4993 if (regno >= FIRST_PSEUDO_REGISTER)
4995 /* Count an extra reference to the reg. When a reg is
4996 incremented, spilling it is worse, so we want to make
4997 that less likely. */
4998 REG_N_REFS (regno) += (optimize_size ? 1 : pbi->bb->loop_depth + 1);
5000 /* Count the increment as a setting of the register,
5001 even though it isn't a SET in rtl. */
5002 REG_N_SETS (regno)++;
5006 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
5010 find_auto_inc (pbi, x, insn)
5011 struct propagate_block_info *pbi;
5015 rtx addr = XEXP (x, 0);
5016 HOST_WIDE_INT offset = 0;
5017 rtx set, y, incr, inc_val;
5019 int size = GET_MODE_SIZE (GET_MODE (x));
5021 if (GET_CODE (insn) == JUMP_INSN)
5024 /* Here we detect use of an index register which might be good for
5025 postincrement, postdecrement, preincrement, or predecrement. */
5027 if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
5028 offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
5030 if (GET_CODE (addr) != REG)
5033 regno = REGNO (addr);
5035 /* Is the next use an increment that might make auto-increment? */
5036 incr = pbi->reg_next_use[regno];
5037 if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
5039 set = single_set (incr);
5040 if (set == 0 || GET_CODE (set) != SET)
5044 if (GET_CODE (y) != PLUS)
5047 if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr))
5048 inc_val = XEXP (y, 1);
5049 else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr))
5050 inc_val = XEXP (y, 0);
5054 if (GET_CODE (inc_val) == CONST_INT)
5056 if (HAVE_POST_INCREMENT
5057 && (INTVAL (inc_val) == size && offset == 0))
5058 attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x,
5060 else if (HAVE_POST_DECREMENT
5061 && (INTVAL (inc_val) == -size && offset == 0))
5062 attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x,
5064 else if (HAVE_PRE_INCREMENT
5065 && (INTVAL (inc_val) == size && offset == size))
5066 attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x,
5068 else if (HAVE_PRE_DECREMENT
5069 && (INTVAL (inc_val) == -size && offset == -size))
5070 attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x,
5072 else if (HAVE_POST_MODIFY_DISP && offset == 0)
5073 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
5074 gen_rtx_PLUS (Pmode,
5077 insn, x, incr, addr);
5079 else if (GET_CODE (inc_val) == REG
5080 && ! reg_set_between_p (inc_val, PREV_INSN (insn),
5084 if (HAVE_POST_MODIFY_REG && offset == 0)
5085 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
5086 gen_rtx_PLUS (Pmode,
5089 insn, x, incr, addr);
5093 #endif /* AUTO_INC_DEC */
5096 mark_used_reg (pbi, reg, cond, insn)
5097 struct propagate_block_info *pbi;
5099 rtx cond ATTRIBUTE_UNUSED;
5102 int regno = REGNO (reg);
5103 int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
5104 int some_was_dead = ! some_was_live;
5108 /* A hard reg in a wide mode may really be multiple registers.
5109 If so, mark all of them just like the first. */
5110 if (regno < FIRST_PSEUDO_REGISTER)
5112 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5115 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
5116 some_was_live |= needed_regno;
5117 some_was_dead |= ! needed_regno;
5121 if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
5123 /* Record where each reg is used, so when the reg is set we know
5124 the next insn that uses it. */
5125 pbi->reg_next_use[regno] = insn;
5128 if (pbi->flags & PROP_REG_INFO)
5130 if (regno < FIRST_PSEUDO_REGISTER)
5132 /* If this is a register we are going to try to eliminate,
5133 don't mark it live here. If we are successful in
5134 eliminating it, it need not be live unless it is used for
5135 pseudos, in which case it will have been set live when it
5136 was allocated to the pseudos. If the register will not
5137 be eliminated, reload will set it live at that point.
5139 Otherwise, record that this function uses this register. */
5140 /* ??? The PPC backend tries to "eliminate" on the pic
5141 register to itself. This should be fixed. In the mean
5142 time, hack around it. */
5144 if (! (TEST_HARD_REG_BIT (elim_reg_set, regno)
5145 && (regno == FRAME_POINTER_REGNUM
5146 || regno == ARG_POINTER_REGNUM)))
5148 int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5150 regs_ever_live[regno + --n] = 1;
5156 /* Keep track of which basic block each reg appears in. */
5158 register int blocknum = pbi->bb->index;
5159 if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
5160 REG_BASIC_BLOCK (regno) = blocknum;
5161 else if (REG_BASIC_BLOCK (regno) != blocknum)
5162 REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
5164 /* Count (weighted) number of uses of each reg. */
5165 REG_N_REFS (regno) += (optimize_size ? 1
5166 : pbi->bb->loop_depth + 1);
5170 /* Find out if any of the register was set this insn. */
5171 some_not_set = ! REGNO_REG_SET_P (pbi->new_set, regno);
5172 if (regno < FIRST_PSEUDO_REGISTER)
5174 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5176 some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, regno + n);
5179 /* Record and count the insns in which a reg dies. If it is used in
5180 this insn and was dead below the insn then it dies in this insn.
5181 If it was set in this insn, we do not make a REG_DEAD note;
5182 likewise if we already made such a note. */
5183 if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
5187 /* Check for the case where the register dying partially
5188 overlaps the register set by this insn. */
5189 if (regno < FIRST_PSEUDO_REGISTER
5190 && HARD_REGNO_NREGS (regno, GET_MODE (reg)) > 1)
5192 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5194 some_was_live |= REGNO_REG_SET_P (pbi->new_set, regno + n);
5197 /* If none of the words in X is needed, make a REG_DEAD note.
5198 Otherwise, we must make partial REG_DEAD notes. */
5199 if (! some_was_live)
5201 if ((pbi->flags & PROP_DEATH_NOTES)
5202 && ! find_regno_note (insn, REG_DEAD, regno))
5204 = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
5206 if (pbi->flags & PROP_REG_INFO)
5207 REG_N_DEATHS (regno)++;
5211 /* Don't make a REG_DEAD note for a part of a register
5212 that is set in the insn. */
5214 n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
5215 for (; n >= regno; n--)
5216 if (! REGNO_REG_SET_P (pbi->reg_live, n)
5217 && ! dead_or_set_regno_p (insn, n))
5219 = alloc_EXPR_LIST (REG_DEAD,
5220 gen_rtx_REG (reg_raw_mode[n], n),
5225 SET_REGNO_REG_SET (pbi->reg_live, regno);
5226 if (regno < FIRST_PSEUDO_REGISTER)
5228 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5230 SET_REGNO_REG_SET (pbi->reg_live, regno + n);
5233 #ifdef HAVE_conditional_execution
5234 /* If this is a conditional use, record that fact. If it is later
5235 conditionally set, we'll know to kill the register. */
5236 if (cond != NULL_RTX)
5238 splay_tree_node node;
5239 struct reg_cond_life_info *rcli;
5244 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5247 /* The register was unconditionally live previously.
5248 No need to do anything. */
5252 /* The register was conditionally live previously.
5253 Subtract the new life cond from the old death cond. */
5254 rcli = (struct reg_cond_life_info *) node->value;
5255 ncond = rcli->condition;
5256 ncond = nand_reg_cond (ncond, cond);
5258 /* If the register is now unconditionally live, remove the
5259 entry in the splay_tree. */
5260 if (ncond == const0_rtx)
5262 rcli->condition = NULL_RTX;
5263 splay_tree_remove (pbi->reg_cond_dead, regno);
5267 rcli->condition = ncond;
5268 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
5274 /* The register was not previously live at all. Record
5275 the condition under which it is still dead. */
5276 rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
5277 rcli->condition = not_reg_cond (cond);
5278 splay_tree_insert (pbi->reg_cond_dead, regno,
5279 (splay_tree_value) rcli);
5281 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
5284 else if (some_was_live)
5286 splay_tree_node node;
5287 struct reg_cond_life_info *rcli;
5289 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5292 /* The register was conditionally live previously, but is now
5293 unconditionally so. Remove it from the conditionally dead
5294 list, so that a conditional set won't cause us to think
5296 rcli = (struct reg_cond_life_info *) node->value;
5297 rcli->condition = NULL_RTX;
5298 splay_tree_remove (pbi->reg_cond_dead, regno);
5305 /* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
5306 This is done assuming the registers needed from X are those that
5307 have 1-bits in PBI->REG_LIVE.
5309 INSN is the containing instruction. If INSN is dead, this function
5313 mark_used_regs (pbi, x, cond, insn)
5314 struct propagate_block_info *pbi;
5317 register RTX_CODE code;
5319 int flags = pbi->flags;
5322 code = GET_CODE (x);
5342 /* If we are clobbering a MEM, mark any registers inside the address
5344 if (GET_CODE (XEXP (x, 0)) == MEM)
5345 mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
5349 /* Don't bother watching stores to mems if this is not the
5350 final pass. We'll not be deleting dead stores this round. */
5351 if (optimize && (flags & PROP_SCAN_DEAD_CODE))
5353 /* Invalidate the data for the last MEM stored, but only if MEM is
5354 something that can be stored into. */
5355 if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
5356 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
5357 /* Needn't clear the memory set list. */
5361 rtx temp = pbi->mem_set_list;
5362 rtx prev = NULL_RTX;
5367 next = XEXP (temp, 1);
5368 if (anti_dependence (XEXP (temp, 0), x))
5370 /* Splice temp out of the list. */
5372 XEXP (prev, 1) = next;
5374 pbi->mem_set_list = next;
5375 free_EXPR_LIST_node (temp);
5383 /* If the memory reference had embedded side effects (autoincrement
5384 address modes. Then we may need to kill some entries on the
5387 invalidate_mems_from_autoinc (pbi, insn);
5391 if (flags & PROP_AUTOINC)
5392 find_auto_inc (pbi, x, insn);
5397 #ifdef CLASS_CANNOT_CHANGE_MODE
5398 if (GET_CODE (SUBREG_REG (x)) == REG
5399 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
5400 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (x),
5401 GET_MODE (SUBREG_REG (x))))
5402 REG_CHANGES_MODE (REGNO (SUBREG_REG (x))) = 1;
5405 /* While we're here, optimize this case. */
5407 if (GET_CODE (x) != REG)
5412 /* See a register other than being set => mark it as needed. */
5413 mark_used_reg (pbi, x, cond, insn);
5418 register rtx testreg = SET_DEST (x);
5421 /* If storing into MEM, don't show it as being used. But do
5422 show the address as being used. */
5423 if (GET_CODE (testreg) == MEM)
5426 if (flags & PROP_AUTOINC)
5427 find_auto_inc (pbi, testreg, insn);
5429 mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
5430 mark_used_regs (pbi, SET_SRC (x), cond, insn);
5434 /* Storing in STRICT_LOW_PART is like storing in a reg
5435 in that this SET might be dead, so ignore it in TESTREG.
5436 but in some other ways it is like using the reg.
5438 Storing in a SUBREG or a bit field is like storing the entire
5439 register in that if the register's value is not used
5440 then this SET is not needed. */
5441 while (GET_CODE (testreg) == STRICT_LOW_PART
5442 || GET_CODE (testreg) == ZERO_EXTRACT
5443 || GET_CODE (testreg) == SIGN_EXTRACT
5444 || GET_CODE (testreg) == SUBREG)
5446 #ifdef CLASS_CANNOT_CHANGE_MODE
5447 if (GET_CODE (testreg) == SUBREG
5448 && GET_CODE (SUBREG_REG (testreg)) == REG
5449 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
5450 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (SUBREG_REG (testreg)),
5451 GET_MODE (testreg)))
5452 REG_CHANGES_MODE (REGNO (SUBREG_REG (testreg))) = 1;
5455 /* Modifying a single register in an alternate mode
5456 does not use any of the old value. But these other
5457 ways of storing in a register do use the old value. */
5458 if (GET_CODE (testreg) == SUBREG
5459 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
5464 testreg = XEXP (testreg, 0);
5467 /* If this is a store into a register, recursively scan the
5468 value being stored. */
5470 if ((GET_CODE (testreg) == PARALLEL
5471 && GET_MODE (testreg) == BLKmode)
5472 || (GET_CODE (testreg) == REG
5473 && (regno = REGNO (testreg),
5474 ! (regno == FRAME_POINTER_REGNUM
5475 && (! reload_completed || frame_pointer_needed)))
5476 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
5477 && ! (regno == HARD_FRAME_POINTER_REGNUM
5478 && (! reload_completed || frame_pointer_needed))
5480 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
5481 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
5486 mark_used_regs (pbi, SET_DEST (x), cond, insn);
5487 mark_used_regs (pbi, SET_SRC (x), cond, insn);
5494 case UNSPEC_VOLATILE:
5498 /* Traditional and volatile asm instructions must be considered to use
5499 and clobber all hard registers, all pseudo-registers and all of
5500 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
5502 Consider for instance a volatile asm that changes the fpu rounding
5503 mode. An insn should not be moved across this even if it only uses
5504 pseudo-regs because it might give an incorrectly rounded result.
5506 ?!? Unfortunately, marking all hard registers as live causes massive
5507 problems for the register allocator and marking all pseudos as live
5508 creates mountains of uninitialized variable warnings.
5510 So for now, just clear the memory set list and mark any regs
5511 we can find in ASM_OPERANDS as used. */
5512 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
5513 free_EXPR_LIST_list (&pbi->mem_set_list);
5515 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
5516 We can not just fall through here since then we would be confused
5517 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
5518 traditional asms unlike their normal usage. */
5519 if (code == ASM_OPERANDS)
5523 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
5524 mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
5530 if (cond != NULL_RTX)
5533 mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
5535 cond = COND_EXEC_TEST (x);
5536 x = COND_EXEC_CODE (x);
5540 /* We _do_not_ want to scan operands of phi nodes. Operands of
5541 a phi function are evaluated only when control reaches this
5542 block along a particular edge. Therefore, regs that appear
5543 as arguments to phi should not be added to the global live at
5551 /* Recursively scan the operands of this expression. */
5554 register const char *fmt = GET_RTX_FORMAT (code);
5557 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5561 /* Tail recursive case: save a function call level. */
5567 mark_used_regs (pbi, XEXP (x, i), cond, insn);
5569 else if (fmt[i] == 'E')
5572 for (j = 0; j < XVECLEN (x, i); j++)
5573 mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
5582 try_pre_increment_1 (pbi, insn)
5583 struct propagate_block_info *pbi;
5586 /* Find the next use of this reg. If in same basic block,
5587 make it do pre-increment or pre-decrement if appropriate. */
5588 rtx x = single_set (insn);
5589 HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
5590 * INTVAL (XEXP (SET_SRC (x), 1)));
5591 int regno = REGNO (SET_DEST (x));
5592 rtx y = pbi->reg_next_use[regno];
5594 && BLOCK_NUM (y) == BLOCK_NUM (insn)
5595 /* Don't do this if the reg dies, or gets set in y; a standard addressing
5596 mode would be better. */
5597 && ! dead_or_set_p (y, SET_DEST (x))
5598 && try_pre_increment (y, SET_DEST (x), amount))
5600 /* We have found a suitable auto-increment
5601 and already changed insn Y to do it.
5602 So flush this increment-instruction. */
5603 PUT_CODE (insn, NOTE);
5604 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5605 NOTE_SOURCE_FILE (insn) = 0;
5606 /* Count a reference to this reg for the increment
5607 insn we are deleting. When a reg is incremented.
5608 spilling it is worse, so we want to make that
5610 if (regno >= FIRST_PSEUDO_REGISTER)
5612 REG_N_REFS (regno) += (optimize_size ? 1
5613 : pbi->bb->loop_depth + 1);
5614 REG_N_SETS (regno)++;
5621 /* Try to change INSN so that it does pre-increment or pre-decrement
5622 addressing on register REG in order to add AMOUNT to REG.
5623 AMOUNT is negative for pre-decrement.
5624 Returns 1 if the change could be made.
5625 This checks all about the validity of the result of modifying INSN. */
5628 try_pre_increment (insn, reg, amount)
5630 HOST_WIDE_INT amount;
5634 /* Nonzero if we can try to make a pre-increment or pre-decrement.
5635 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
5637 /* Nonzero if we can try to make a post-increment or post-decrement.
5638 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
5639 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
5640 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
5643 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
5646 /* From the sign of increment, see which possibilities are conceivable
5647 on this target machine. */
5648 if (HAVE_PRE_INCREMENT && amount > 0)
5650 if (HAVE_POST_INCREMENT && amount > 0)
5653 if (HAVE_PRE_DECREMENT && amount < 0)
5655 if (HAVE_POST_DECREMENT && amount < 0)
5658 if (! (pre_ok || post_ok))
5661 /* It is not safe to add a side effect to a jump insn
5662 because if the incremented register is spilled and must be reloaded
5663 there would be no way to store the incremented value back in memory. */
5665 if (GET_CODE (insn) == JUMP_INSN)
5670 use = find_use_as_address (PATTERN (insn), reg, 0);
5671 if (post_ok && (use == 0 || use == (rtx) 1))
5673 use = find_use_as_address (PATTERN (insn), reg, -amount);
5677 if (use == 0 || use == (rtx) 1)
5680 if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
5683 /* See if this combination of instruction and addressing mode exists. */
5684 if (! validate_change (insn, &XEXP (use, 0),
5685 gen_rtx_fmt_e (amount > 0
5686 ? (do_post ? POST_INC : PRE_INC)
5687 : (do_post ? POST_DEC : PRE_DEC),
5691 /* Record that this insn now has an implicit side effect on X. */
5692 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
5696 #endif /* AUTO_INC_DEC */
5698 /* Find the place in the rtx X where REG is used as a memory address.
5699 Return the MEM rtx that so uses it.
5700 If PLUSCONST is nonzero, search instead for a memory address equivalent to
5701 (plus REG (const_int PLUSCONST)).
5703 If such an address does not appear, return 0.
5704 If REG appears more than once, or is used other than in such an address,
5708 find_use_as_address (x, reg, plusconst)
5711 HOST_WIDE_INT plusconst;
5713 enum rtx_code code = GET_CODE (x);
5714 const char *fmt = GET_RTX_FORMAT (code);
5716 register rtx value = 0;
5719 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
5722 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
5723 && XEXP (XEXP (x, 0), 0) == reg
5724 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
5725 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
5728 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
5730 /* If REG occurs inside a MEM used in a bit-field reference,
5731 that is unacceptable. */
5732 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
5733 return (rtx) (HOST_WIDE_INT) 1;
5737 return (rtx) (HOST_WIDE_INT) 1;
5739 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5743 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
5747 return (rtx) (HOST_WIDE_INT) 1;
5749 else if (fmt[i] == 'E')
5752 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5754 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
5758 return (rtx) (HOST_WIDE_INT) 1;
5766 /* Write information about registers and basic blocks into FILE.
5767 This is part of making a debugging dump. */
5770 dump_regset (r, outf)
5777 fputs (" (nil)", outf);
5781 EXECUTE_IF_SET_IN_REG_SET (r, 0, i,
5783 fprintf (outf, " %d", i);
5784 if (i < FIRST_PSEUDO_REGISTER)
5785 fprintf (outf, " [%s]",
5794 dump_regset (r, stderr);
5795 putc ('\n', stderr);
5799 dump_flow_info (file)
5803 static const char * const reg_class_names[] = REG_CLASS_NAMES;
5805 fprintf (file, "%d registers.\n", max_regno);
5806 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
5809 enum reg_class class, altclass;
5810 fprintf (file, "\nRegister %d used %d times across %d insns",
5811 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
5812 if (REG_BASIC_BLOCK (i) >= 0)
5813 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
5815 fprintf (file, "; set %d time%s", REG_N_SETS (i),
5816 (REG_N_SETS (i) == 1) ? "" : "s");
5817 if (REG_USERVAR_P (regno_reg_rtx[i]))
5818 fprintf (file, "; user var");
5819 if (REG_N_DEATHS (i) != 1)
5820 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
5821 if (REG_N_CALLS_CROSSED (i) == 1)
5822 fprintf (file, "; crosses 1 call");
5823 else if (REG_N_CALLS_CROSSED (i))
5824 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
5825 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
5826 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
5827 class = reg_preferred_class (i);
5828 altclass = reg_alternate_class (i);
5829 if (class != GENERAL_REGS || altclass != ALL_REGS)
5831 if (altclass == ALL_REGS || class == ALL_REGS)
5832 fprintf (file, "; pref %s", reg_class_names[(int) class]);
5833 else if (altclass == NO_REGS)
5834 fprintf (file, "; %s or none", reg_class_names[(int) class]);
5836 fprintf (file, "; pref %s, else %s",
5837 reg_class_names[(int) class],
5838 reg_class_names[(int) altclass]);
5840 if (REGNO_POINTER_FLAG (i))
5841 fprintf (file, "; pointer");
5842 fprintf (file, ".\n");
5845 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
5846 for (i = 0; i < n_basic_blocks; i++)
5848 register basic_block bb = BASIC_BLOCK (i);
5851 fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count %d.\n",
5852 i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth, bb->count);
5854 fprintf (file, "Predecessors: ");
5855 for (e = bb->pred; e; e = e->pred_next)
5856 dump_edge_info (file, e, 0);
5858 fprintf (file, "\nSuccessors: ");
5859 for (e = bb->succ; e; e = e->succ_next)
5860 dump_edge_info (file, e, 1);
5862 fprintf (file, "\nRegisters live at start:");
5863 dump_regset (bb->global_live_at_start, file);
5865 fprintf (file, "\nRegisters live at end:");
5866 dump_regset (bb->global_live_at_end, file);
5877 dump_flow_info (stderr);
5881 dump_edge_info (file, e, do_succ)
5886 basic_block side = (do_succ ? e->dest : e->src);
5888 if (side == ENTRY_BLOCK_PTR)
5889 fputs (" ENTRY", file);
5890 else if (side == EXIT_BLOCK_PTR)
5891 fputs (" EXIT", file);
5893 fprintf (file, " %d", side->index);
5896 fprintf (file, " count:%d", e->count);
5900 static const char * const bitnames[] = {
5901 "fallthru", "crit", "ab", "abcall", "eh", "fake"
5904 int i, flags = e->flags;
5908 for (i = 0; flags; i++)
5909 if (flags & (1 << i))
5915 if (i < (int) ARRAY_SIZE (bitnames))
5916 fputs (bitnames[i], file);
5918 fprintf (file, "%d", i);
5925 /* Print out one basic block with live information at start and end. */
5936 fprintf (outf, ";; Basic block %d, loop depth %d, count %d",
5937 bb->index, bb->loop_depth, bb->count);
5938 if (bb->eh_beg != -1 || bb->eh_end != -1)
5939 fprintf (outf, ", eh regions %d/%d", bb->eh_beg, bb->eh_end);
5942 fputs (";; Predecessors: ", outf);
5943 for (e = bb->pred; e; e = e->pred_next)
5944 dump_edge_info (outf, e, 0);
5947 fputs (";; Registers live at start:", outf);
5948 dump_regset (bb->global_live_at_start, outf);
5951 for (insn = bb->head, last = NEXT_INSN (bb->end);
5953 insn = NEXT_INSN (insn))
5954 print_rtl_single (outf, insn);
5956 fputs (";; Registers live at end:", outf);
5957 dump_regset (bb->global_live_at_end, outf);
5960 fputs (";; Successors: ", outf);
5961 for (e = bb->succ; e; e = e->succ_next)
5962 dump_edge_info (outf, e, 1);
5970 dump_bb (bb, stderr);
5977 dump_bb (BASIC_BLOCK (n), stderr);
5980 /* Like print_rtl, but also print out live information for the start of each
5984 print_rtl_with_bb (outf, rtx_first)
5988 register rtx tmp_rtx;
5991 fprintf (outf, "(nil)\n");
5995 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
5996 int max_uid = get_max_uid ();
5997 basic_block *start = (basic_block *)
5998 xcalloc (max_uid, sizeof (basic_block));
5999 basic_block *end = (basic_block *)
6000 xcalloc (max_uid, sizeof (basic_block));
6001 enum bb_state *in_bb_p = (enum bb_state *)
6002 xcalloc (max_uid, sizeof (enum bb_state));
6004 for (i = n_basic_blocks - 1; i >= 0; i--)
6006 basic_block bb = BASIC_BLOCK (i);
6009 start[INSN_UID (bb->head)] = bb;
6010 end[INSN_UID (bb->end)] = bb;
6011 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
6013 enum bb_state state = IN_MULTIPLE_BB;
6014 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
6016 in_bb_p[INSN_UID (x)] = state;
6023 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
6028 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
6030 fprintf (outf, ";; Start of basic block %d, registers live:",
6032 dump_regset (bb->global_live_at_start, outf);
6036 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
6037 && GET_CODE (tmp_rtx) != NOTE
6038 && GET_CODE (tmp_rtx) != BARRIER)
6039 fprintf (outf, ";; Insn is not within a basic block\n");
6040 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
6041 fprintf (outf, ";; Insn is in multiple basic blocks\n");
6043 did_output = print_rtl_single (outf, tmp_rtx);
6045 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
6047 fprintf (outf, ";; End of basic block %d, registers live:\n",
6049 dump_regset (bb->global_live_at_end, outf);
6062 if (current_function_epilogue_delay_list != 0)
6064 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
6065 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
6066 tmp_rtx = XEXP (tmp_rtx, 1))
6067 print_rtl_single (outf, XEXP (tmp_rtx, 0));
6071 /* Compute dominator relationships using new flow graph structures. */
6074 compute_flow_dominators (dominators, post_dominators)
6075 sbitmap *dominators;
6076 sbitmap *post_dominators;
6079 sbitmap *temp_bitmap;
6081 basic_block *worklist, *workend, *qin, *qout;
6084 /* Allocate a worklist array/queue. Entries are only added to the
6085 list if they were not already on the list. So the size is
6086 bounded by the number of basic blocks. */
6087 worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
6088 workend = &worklist[n_basic_blocks];
6090 temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6091 sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
6095 /* The optimistic setting of dominators requires us to put every
6096 block on the work list initially. */
6097 qin = qout = worklist;
6098 for (bb = 0; bb < n_basic_blocks; bb++)
6100 *qin++ = BASIC_BLOCK (bb);
6101 BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6103 qlen = n_basic_blocks;
6106 /* We want a maximal solution, so initially assume everything dominates
6108 sbitmap_vector_ones (dominators, n_basic_blocks);
6110 /* Mark successors of the entry block so we can identify them below. */
6111 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6112 e->dest->aux = ENTRY_BLOCK_PTR;
6114 /* Iterate until the worklist is empty. */
6117 /* Take the first entry off the worklist. */
6118 basic_block b = *qout++;
6119 if (qout >= workend)
6125 /* Compute the intersection of the dominators of all the
6128 If one of the predecessor blocks is the ENTRY block, then the
6129 intersection of the dominators of the predecessor blocks is
6130 defined as the null set. We can identify such blocks by the
6131 special value in the AUX field in the block structure. */
6132 if (b->aux == ENTRY_BLOCK_PTR)
6134 /* Do not clear the aux field for blocks which are
6135 successors of the ENTRY block. That way we never add
6136 them to the worklist again.
6138 The intersect of dominators of the preds of this block is
6139 defined as the null set. */
6140 sbitmap_zero (temp_bitmap[bb]);
6144 /* Clear the aux field of this block so it can be added to
6145 the worklist again if necessary. */
6147 sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
6150 /* Make sure each block always dominates itself. */
6151 SET_BIT (temp_bitmap[bb], bb);
6153 /* If the out state of this block changed, then we need to
6154 add the successors of this block to the worklist if they
6155 are not already on the worklist. */
6156 if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
6158 for (e = b->succ; e; e = e->succ_next)
6160 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
6174 if (post_dominators)
6176 /* The optimistic setting of dominators requires us to put every
6177 block on the work list initially. */
6178 qin = qout = worklist;
6179 for (bb = 0; bb < n_basic_blocks; bb++)
6181 *qin++ = BASIC_BLOCK (bb);
6182 BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6184 qlen = n_basic_blocks;
6187 /* We want a maximal solution, so initially assume everything post
6188 dominates everything else. */
6189 sbitmap_vector_ones (post_dominators, n_basic_blocks);
6191 /* Mark predecessors of the exit block so we can identify them below. */
6192 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
6193 e->src->aux = EXIT_BLOCK_PTR;
6195 /* Iterate until the worklist is empty. */
6198 /* Take the first entry off the worklist. */
6199 basic_block b = *qout++;
6200 if (qout >= workend)
6206 /* Compute the intersection of the post dominators of all the
6209 If one of the successor blocks is the EXIT block, then the
6210 intersection of the dominators of the successor blocks is
6211 defined as the null set. We can identify such blocks by the
6212 special value in the AUX field in the block structure. */
6213 if (b->aux == EXIT_BLOCK_PTR)
6215 /* Do not clear the aux field for blocks which are
6216 predecessors of the EXIT block. That way we we never
6217 add them to the worklist again.
6219 The intersect of dominators of the succs of this block is
6220 defined as the null set. */
6221 sbitmap_zero (temp_bitmap[bb]);
6225 /* Clear the aux field of this block so it can be added to
6226 the worklist again if necessary. */
6228 sbitmap_intersection_of_succs (temp_bitmap[bb],
6229 post_dominators, bb);
6232 /* Make sure each block always post dominates itself. */
6233 SET_BIT (temp_bitmap[bb], bb);
6235 /* If the out state of this block changed, then we need to
6236 add the successors of this block to the worklist if they
6237 are not already on the worklist. */
6238 if (sbitmap_a_and_b (post_dominators[bb],
6239 post_dominators[bb],
6242 for (e = b->pred; e; e = e->pred_next)
6244 if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
6262 /* Given DOMINATORS, compute the immediate dominators into IDOM. If a
6263 block dominates only itself, its entry remains as INVALID_BLOCK. */
6266 compute_immediate_dominators (idom, dominators)
6268 sbitmap *dominators;
6273 tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6275 /* Begin with tmp(n) = dom(n) - { n }. */
6276 for (b = n_basic_blocks; --b >= 0;)
6278 sbitmap_copy (tmp[b], dominators[b]);
6279 RESET_BIT (tmp[b], b);
6282 /* Subtract out all of our dominator's dominators. */
6283 for (b = n_basic_blocks; --b >= 0;)
6285 sbitmap tmp_b = tmp[b];
6288 for (s = n_basic_blocks; --s >= 0;)
6289 if (TEST_BIT (tmp_b, s))
6290 sbitmap_difference (tmp_b, tmp_b, tmp[s]);
6293 /* Find the one bit set in the bitmap and put it in the output array. */
6294 for (b = n_basic_blocks; --b >= 0;)
6297 EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
6300 sbitmap_vector_free (tmp);
6303 /* Given POSTDOMINATORS, compute the immediate postdominators into
6304 IDOM. If a block is only dominated by itself, its entry remains as
6308 compute_immediate_postdominators (idom, postdominators)
6310 sbitmap *postdominators;
6312 compute_immediate_dominators (idom, postdominators);
6315 /* Recompute register set/reference counts immediately prior to register
6318 This avoids problems with set/reference counts changing to/from values
6319 which have special meanings to the register allocators.
6321 Additionally, the reference counts are the primary component used by the
6322 register allocators to prioritize pseudos for allocation to hard regs.
6323 More accurate reference counts generally lead to better register allocation.
6325 F is the first insn to be scanned.
6327 LOOP_STEP denotes how much loop_depth should be incremented per
6328 loop nesting level in order to increase the ref count more for
6329 references in a loop.
6331 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
6332 possibly other information which is used by the register allocators. */
6335 recompute_reg_usage (f, loop_step)
6336 rtx f ATTRIBUTE_UNUSED;
6337 int loop_step ATTRIBUTE_UNUSED;
6339 allocate_reg_life_data ();
6340 update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO);
6343 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
6344 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
6345 of the number of registers that died. */
6348 count_or_remove_death_notes (blocks, kill)
6354 for (i = n_basic_blocks - 1; i >= 0; --i)
6359 if (blocks && ! TEST_BIT (blocks, i))
6362 bb = BASIC_BLOCK (i);
6364 for (insn = bb->head;; insn = NEXT_INSN (insn))
6368 rtx *pprev = ®_NOTES (insn);
6373 switch (REG_NOTE_KIND (link))
6376 if (GET_CODE (XEXP (link, 0)) == REG)
6378 rtx reg = XEXP (link, 0);
6381 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
6384 n = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
6392 rtx next = XEXP (link, 1);
6393 free_EXPR_LIST_node (link);
6394 *pprev = link = next;
6400 pprev = &XEXP (link, 1);
6407 if (insn == bb->end)
6415 /* Record INSN's block as BB. */
6418 set_block_for_insn (insn, bb)
6422 size_t uid = INSN_UID (insn);
6423 if (uid >= basic_block_for_insn->num_elements)
6427 /* Add one-eighth the size so we don't keep calling xrealloc. */
6428 new_size = uid + (uid + 7) / 8;
6430 VARRAY_GROW (basic_block_for_insn, new_size);
6432 VARRAY_BB (basic_block_for_insn, uid) = bb;
6435 /* Record INSN's block number as BB. */
6436 /* ??? This has got to go. */
6439 set_block_num (insn, bb)
6443 set_block_for_insn (insn, BASIC_BLOCK (bb));
6446 /* Verify the CFG consistency. This function check some CFG invariants and
6447 aborts when something is wrong. Hope that this function will help to
6448 convert many optimization passes to preserve CFG consistent.
6450 Currently it does following checks:
6452 - test head/end pointers
6453 - overlapping of basic blocks
6454 - edge list corectness
6455 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
6456 - tails of basic blocks (ensure that boundary is necesary)
6457 - scans body of the basic block for JUMP_INSN, CODE_LABEL
6458 and NOTE_INSN_BASIC_BLOCK
6459 - check that all insns are in the basic blocks
6460 (except the switch handling code, barriers and notes)
6461 - check that all returns are followed by barriers
6463 In future it can be extended check a lot of other stuff as well
6464 (reachability of basic blocks, life information, etc. etc.). */
6469 const int max_uid = get_max_uid ();
6470 const rtx rtx_first = get_insns ();
6471 rtx last_head = get_last_insn ();
6472 basic_block *bb_info;
6474 int i, last_bb_num_seen, num_bb_notes, err = 0;
6476 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
6478 for (i = n_basic_blocks - 1; i >= 0; i--)
6480 basic_block bb = BASIC_BLOCK (i);
6481 rtx head = bb->head;
6484 /* Verify the end of the basic block is in the INSN chain. */
6485 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
6490 error ("End insn %d for block %d not found in the insn stream.",
6491 INSN_UID (end), bb->index);
6495 /* Work backwards from the end to the head of the basic block
6496 to verify the head is in the RTL chain. */
6497 for (; x != NULL_RTX; x = PREV_INSN (x))
6499 /* While walking over the insn chain, verify insns appear
6500 in only one basic block and initialize the BB_INFO array
6501 used by other passes. */
6502 if (bb_info[INSN_UID (x)] != NULL)
6504 error ("Insn %d is in multiple basic blocks (%d and %d)",
6505 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
6508 bb_info[INSN_UID (x)] = bb;
6515 error ("Head insn %d for block %d not found in the insn stream.",
6516 INSN_UID (head), bb->index);
6523 /* Now check the basic blocks (boundaries etc.) */
6524 for (i = n_basic_blocks - 1; i >= 0; i--)
6526 basic_block bb = BASIC_BLOCK (i);
6527 /* Check corectness of edge lists */
6536 "verify_flow_info: Basic block %d succ edge is corrupted\n",
6538 fprintf (stderr, "Predecessor: ");
6539 dump_edge_info (stderr, e, 0);
6540 fprintf (stderr, "\nSuccessor: ");
6541 dump_edge_info (stderr, e, 1);
6545 if (e->dest != EXIT_BLOCK_PTR)
6547 edge e2 = e->dest->pred;
6548 while (e2 && e2 != e)
6552 error ("Basic block %i edge lists are corrupted", bb->index);
6564 error ("Basic block %d pred edge is corrupted", bb->index);
6565 fputs ("Predecessor: ", stderr);
6566 dump_edge_info (stderr, e, 0);
6567 fputs ("\nSuccessor: ", stderr);
6568 dump_edge_info (stderr, e, 1);
6569 fputc ('\n', stderr);
6572 if (e->src != ENTRY_BLOCK_PTR)
6574 edge e2 = e->src->succ;
6575 while (e2 && e2 != e)
6579 error ("Basic block %i edge lists are corrupted", bb->index);
6586 /* OK pointers are correct. Now check the header of basic
6587 block. It ought to contain optional CODE_LABEL followed
6588 by NOTE_BASIC_BLOCK. */
6590 if (GET_CODE (x) == CODE_LABEL)
6594 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
6600 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
6602 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
6609 /* Do checks for empty blocks here */
6616 if (NOTE_INSN_BASIC_BLOCK_P (x))
6618 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
6619 INSN_UID (x), bb->index);
6626 if (GET_CODE (x) == JUMP_INSN
6627 || GET_CODE (x) == CODE_LABEL
6628 || GET_CODE (x) == BARRIER)
6630 error ("In basic block %d:", bb->index);
6631 fatal_insn ("Flow control insn inside a basic block", x);
6639 last_bb_num_seen = -1;
6644 if (NOTE_INSN_BASIC_BLOCK_P (x))
6646 basic_block bb = NOTE_BASIC_BLOCK (x);
6648 if (bb->index != last_bb_num_seen + 1)
6649 fatal ("Basic blocks not numbered consecutively");
6650 last_bb_num_seen = bb->index;
6653 if (!bb_info[INSN_UID (x)])
6655 switch (GET_CODE (x))
6662 /* An addr_vec is placed outside any block block. */
6664 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
6665 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
6666 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
6671 /* But in any case, non-deletable labels can appear anywhere. */
6675 fatal_insn ("Insn outside basic block", x);
6680 && GET_CODE (x) == JUMP_INSN
6681 && returnjump_p (x) && ! condjump_p (x)
6682 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
6683 fatal_insn ("Return not followed by barrier", x);
6688 if (num_bb_notes != n_basic_blocks)
6689 fatal ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
6690 num_bb_notes, n_basic_blocks);
6699 /* Functions to access an edge list with a vector representation.
6700 Enough data is kept such that given an index number, the
6701 pred and succ that edge represents can be determined, or
6702 given a pred and a succ, its index number can be returned.
6703 This allows algorithms which consume a lot of memory to
6704 represent the normally full matrix of edge (pred,succ) with a
6705 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
6706 wasted space in the client code due to sparse flow graphs. */
6708 /* This functions initializes the edge list. Basically the entire
6709 flowgraph is processed, and all edges are assigned a number,
6710 and the data structure is filled in. */
6715 struct edge_list *elist;
6721 block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
6725 /* Determine the number of edges in the flow graph by counting successor
6726 edges on each basic block. */
6727 for (x = 0; x < n_basic_blocks; x++)
6729 basic_block bb = BASIC_BLOCK (x);
6731 for (e = bb->succ; e; e = e->succ_next)
6734 /* Don't forget successors of the entry block. */
6735 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6738 elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
6739 elist->num_blocks = block_count;
6740 elist->num_edges = num_edges;
6741 elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
6745 /* Follow successors of the entry block, and register these edges. */
6746 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6748 elist->index_to_edge[num_edges] = e;
6752 for (x = 0; x < n_basic_blocks; x++)
6754 basic_block bb = BASIC_BLOCK (x);
6756 /* Follow all successors of blocks, and register these edges. */
6757 for (e = bb->succ; e; e = e->succ_next)
6759 elist->index_to_edge[num_edges] = e;
6766 /* This function free's memory associated with an edge list. */
6769 free_edge_list (elist)
6770 struct edge_list *elist;
6774 free (elist->index_to_edge);
6779 /* This function provides debug output showing an edge list. */
6782 print_edge_list (f, elist)
6784 struct edge_list *elist;
6787 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
6788 elist->num_blocks - 2, elist->num_edges);
6790 for (x = 0; x < elist->num_edges; x++)
6792 fprintf (f, " %-4d - edge(", x);
6793 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
6794 fprintf (f, "entry,");
6796 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
6798 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
6799 fprintf (f, "exit)\n");
6801 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
6805 /* This function provides an internal consistency check of an edge list,
6806 verifying that all edges are present, and that there are no
6810 verify_edge_list (f, elist)
6812 struct edge_list *elist;
6814 int x, pred, succ, index;
6817 for (x = 0; x < n_basic_blocks; x++)
6819 basic_block bb = BASIC_BLOCK (x);
6821 for (e = bb->succ; e; e = e->succ_next)
6823 pred = e->src->index;
6824 succ = e->dest->index;
6825 index = EDGE_INDEX (elist, e->src, e->dest);
6826 if (index == EDGE_INDEX_NO_EDGE)
6828 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
6831 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6832 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6833 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6834 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6835 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6836 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6839 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6841 pred = e->src->index;
6842 succ = e->dest->index;
6843 index = EDGE_INDEX (elist, e->src, e->dest);
6844 if (index == EDGE_INDEX_NO_EDGE)
6846 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
6849 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6850 fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6851 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6852 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6853 fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6854 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6856 /* We've verified that all the edges are in the list, no lets make sure
6857 there are no spurious edges in the list. */
6859 for (pred = 0; pred < n_basic_blocks; pred++)
6860 for (succ = 0; succ < n_basic_blocks; succ++)
6862 basic_block p = BASIC_BLOCK (pred);
6863 basic_block s = BASIC_BLOCK (succ);
6867 for (e = p->succ; e; e = e->succ_next)
6873 for (e = s->pred; e; e = e->pred_next)
6879 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6880 == EDGE_INDEX_NO_EDGE && found_edge != 0)
6881 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
6883 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
6884 != EDGE_INDEX_NO_EDGE && found_edge == 0)
6885 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
6886 pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6887 BASIC_BLOCK (succ)));
6889 for (succ = 0; succ < n_basic_blocks; succ++)
6891 basic_block p = ENTRY_BLOCK_PTR;
6892 basic_block s = BASIC_BLOCK (succ);
6896 for (e = p->succ; e; e = e->succ_next)
6902 for (e = s->pred; e; e = e->pred_next)
6908 if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6909 == EDGE_INDEX_NO_EDGE && found_edge != 0)
6910 fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
6912 if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
6913 != EDGE_INDEX_NO_EDGE && found_edge == 0)
6914 fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
6915 succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
6916 BASIC_BLOCK (succ)));
6918 for (pred = 0; pred < n_basic_blocks; pred++)
6920 basic_block p = BASIC_BLOCK (pred);
6921 basic_block s = EXIT_BLOCK_PTR;
6925 for (e = p->succ; e; e = e->succ_next)
6931 for (e = s->pred; e; e = e->pred_next)
6937 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6938 == EDGE_INDEX_NO_EDGE && found_edge != 0)
6939 fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
6941 if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
6942 != EDGE_INDEX_NO_EDGE && found_edge == 0)
6943 fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
6944 pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
6949 /* This routine will determine what, if any, edge there is between
6950 a specified predecessor and successor. */
6953 find_edge_index (edge_list, pred, succ)
6954 struct edge_list *edge_list;
6955 basic_block pred, succ;
6958 for (x = 0; x < NUM_EDGES (edge_list); x++)
6960 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
6961 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
6964 return (EDGE_INDEX_NO_EDGE);
6967 /* This function will remove an edge from the flow graph. */
6973 edge last_pred = NULL;
6974 edge last_succ = NULL;
6976 basic_block src, dest;
6979 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
6985 last_succ->succ_next = e->succ_next;
6987 src->succ = e->succ_next;
6989 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
6995 last_pred->pred_next = e->pred_next;
6997 dest->pred = e->pred_next;
7003 /* This routine will remove any fake successor edges for a basic block.
7004 When the edge is removed, it is also removed from whatever predecessor
7008 remove_fake_successors (bb)
7012 for (e = bb->succ; e;)
7016 if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
7021 /* This routine will remove all fake edges from the flow graph. If
7022 we remove all fake successors, it will automatically remove all
7023 fake predecessors. */
7026 remove_fake_edges ()
7030 for (x = 0; x < n_basic_blocks; x++)
7031 remove_fake_successors (BASIC_BLOCK (x));
7033 /* We've handled all successors except the entry block's. */
7034 remove_fake_successors (ENTRY_BLOCK_PTR);
7037 /* This function will add a fake edge between any block which has no
7038 successors, and the exit block. Some data flow equations require these
7042 add_noreturn_fake_exit_edges ()
7046 for (x = 0; x < n_basic_blocks; x++)
7047 if (BASIC_BLOCK (x)->succ == NULL)
7048 make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
7051 /* This function adds a fake edge between any infinite loops to the
7052 exit block. Some optimizations require a path from each node to
7055 See also Morgan, Figure 3.10, pp. 82-83.
7057 The current implementation is ugly, not attempting to minimize the
7058 number of inserted fake edges. To reduce the number of fake edges
7059 to insert, add fake edges from _innermost_ loops containing only
7060 nodes not reachable from the exit block. */
7063 connect_infinite_loops_to_exit ()
7065 basic_block unvisited_block;
7067 /* Perform depth-first search in the reverse graph to find nodes
7068 reachable from the exit block. */
7069 struct depth_first_search_dsS dfs_ds;
7071 flow_dfs_compute_reverse_init (&dfs_ds);
7072 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
7074 /* Repeatedly add fake edges, updating the unreachable nodes. */
7077 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
7078 if (!unvisited_block)
7080 make_edge (NULL, unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
7081 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
7084 flow_dfs_compute_reverse_finish (&dfs_ds);
7089 /* Redirect an edge's successor from one block to another. */
7092 redirect_edge_succ (e, new_succ)
7094 basic_block new_succ;
7098 /* Disconnect the edge from the old successor block. */
7099 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
7101 *pe = (*pe)->pred_next;
7103 /* Reconnect the edge to the new successor block. */
7104 e->pred_next = new_succ->pred;
7109 /* Redirect an edge's predecessor from one block to another. */
7112 redirect_edge_pred (e, new_pred)
7114 basic_block new_pred;
7118 /* Disconnect the edge from the old predecessor block. */
7119 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
7121 *pe = (*pe)->succ_next;
7123 /* Reconnect the edge to the new predecessor block. */
7124 e->succ_next = new_pred->succ;
7129 /* Dump the list of basic blocks in the bitmap NODES. */
7132 flow_nodes_print (str, nodes, file)
7134 const sbitmap nodes;
7142 fprintf (file, "%s { ", str);
7143 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
7144 fputs ("}\n", file);
7148 /* Dump the list of edges in the array EDGE_LIST. */
7151 flow_edge_list_print (str, edge_list, num_edges, file)
7153 const edge *edge_list;
7162 fprintf (file, "%s { ", str);
7163 for (i = 0; i < num_edges; i++)
7164 fprintf (file, "%d->%d ", edge_list[i]->src->index,
7165 edge_list[i]->dest->index);
7166 fputs ("}\n", file);
7170 /* Dump loop related CFG information. */
7173 flow_loops_cfg_dump (loops, file)
7174 const struct loops *loops;
7179 if (! loops->num || ! file || ! loops->cfg.dom)
7182 for (i = 0; i < n_basic_blocks; i++)
7186 fprintf (file, ";; %d succs { ", i);
7187 for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
7188 fprintf (file, "%d ", succ->dest->index);
7189 flow_nodes_print ("} dom", loops->cfg.dom[i], file);
7192 /* Dump the DFS node order. */
7193 if (loops->cfg.dfs_order)
7195 fputs (";; DFS order: ", file);
7196 for (i = 0; i < n_basic_blocks; i++)
7197 fprintf (file, "%d ", loops->cfg.dfs_order[i]);
7200 /* Dump the reverse completion node order. */
7201 if (loops->cfg.rc_order)
7203 fputs (";; RC order: ", file);
7204 for (i = 0; i < n_basic_blocks; i++)
7205 fprintf (file, "%d ", loops->cfg.rc_order[i]);
7210 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
7213 flow_loop_nested_p (outer, loop)
7217 return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
7221 /* Dump the loop information specified by LOOP to the stream FILE
7222 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
7224 flow_loop_dump (loop, file, loop_dump_aux, verbose)
7225 const struct loop *loop;
7227 void (*loop_dump_aux)(const struct loop *, FILE *, int);
7230 if (! loop || ! loop->header)
7233 fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
7234 loop->num, INSN_UID (loop->first->head),
7235 INSN_UID (loop->last->end),
7236 loop->shared ? " shared" : "",
7237 loop->invalid ? " invalid" : "");
7238 fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
7239 loop->header->index, loop->latch->index,
7240 loop->pre_header ? loop->pre_header->index : -1,
7241 loop->first->index, loop->last->index);
7242 fprintf (file, ";; depth %d, level %d, outer %ld\n",
7243 loop->depth, loop->level,
7244 (long) (loop->outer ? loop->outer->num : -1));
7246 flow_edge_list_print (";; entry edges", loop->entry_edges,
7247 loop->num_entries, file);
7248 fprintf (file, ";; %d", loop->num_nodes);
7249 flow_nodes_print (" nodes", loop->nodes, file);
7250 flow_edge_list_print (";; exit edges", loop->exit_edges,
7251 loop->num_exits, file);
7254 loop_dump_aux (loop, file, verbose);
7258 /* Dump the loop information specified by LOOPS to the stream FILE,
7259 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
7261 flow_loops_dump (loops, file, loop_dump_aux, verbose)
7262 const struct loops *loops;
7264 void (*loop_dump_aux)(const struct loop *, FILE *, int);
7270 num_loops = loops->num;
7271 if (! num_loops || ! file)
7274 fprintf (file, ";; %d loops found, %d levels\n",
7275 num_loops, loops->levels);
7277 for (i = 0; i < num_loops; i++)
7279 struct loop *loop = &loops->array[i];
7281 flow_loop_dump (loop, file, loop_dump_aux, verbose);
7287 for (j = 0; j < i; j++)
7289 struct loop *oloop = &loops->array[j];
7291 if (loop->header == oloop->header)
7296 smaller = loop->num_nodes < oloop->num_nodes;
7298 /* If the union of LOOP and OLOOP is different than
7299 the larger of LOOP and OLOOP then LOOP and OLOOP
7300 must be disjoint. */
7301 disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
7302 smaller ? oloop : loop);
7304 ";; loop header %d shared by loops %d, %d %s\n",
7305 loop->header->index, i, j,
7306 disjoint ? "disjoint" : "nested");
7313 flow_loops_cfg_dump (loops, file);
7317 /* Free all the memory allocated for LOOPS. */
7320 flow_loops_free (loops)
7321 struct loops *loops;
7330 /* Free the loop descriptors. */
7331 for (i = 0; i < loops->num; i++)
7333 struct loop *loop = &loops->array[i];
7336 sbitmap_free (loop->nodes);
7337 if (loop->entry_edges)
7338 free (loop->entry_edges);
7339 if (loop->exit_edges)
7340 free (loop->exit_edges);
7342 free (loops->array);
7343 loops->array = NULL;
7346 sbitmap_vector_free (loops->cfg.dom);
7347 if (loops->cfg.dfs_order)
7348 free (loops->cfg.dfs_order);
7350 sbitmap_free (loops->shared_headers);
7355 /* Find the entry edges into the loop with header HEADER and nodes
7356 NODES and store in ENTRY_EDGES array. Return the number of entry
7357 edges from the loop. */
7360 flow_loop_entry_edges_find (header, nodes, entry_edges)
7362 const sbitmap nodes;
7368 *entry_edges = NULL;
7371 for (e = header->pred; e; e = e->pred_next)
7373 basic_block src = e->src;
7375 if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
7382 *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
7385 for (e = header->pred; e; e = e->pred_next)
7387 basic_block src = e->src;
7389 if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
7390 (*entry_edges)[num_entries++] = e;
7397 /* Find the exit edges from the loop using the bitmap of loop nodes
7398 NODES and store in EXIT_EDGES array. Return the number of
7399 exit edges from the loop. */
7402 flow_loop_exit_edges_find (nodes, exit_edges)
7403 const sbitmap nodes;
7412 /* Check all nodes within the loop to see if there are any
7413 successors not in the loop. Note that a node may have multiple
7414 exiting edges ????? A node can have one jumping edge and one fallthru
7415 edge so only one of these can exit the loop. */
7417 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7418 for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7420 basic_block dest = e->dest;
7422 if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7430 *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *));
7432 /* Store all exiting edges into an array. */
7434 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7435 for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7437 basic_block dest = e->dest;
7439 if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7440 (*exit_edges)[num_exits++] = e;
7448 /* Find the nodes contained within the loop with header HEADER and
7449 latch LATCH and store in NODES. Return the number of nodes within
7453 flow_loop_nodes_find (header, latch, nodes)
7462 stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
7465 /* Start with only the loop header in the set of loop nodes. */
7466 sbitmap_zero (nodes);
7467 SET_BIT (nodes, header->index);
7469 header->loop_depth++;
7471 /* Push the loop latch on to the stack. */
7472 if (! TEST_BIT (nodes, latch->index))
7474 SET_BIT (nodes, latch->index);
7475 latch->loop_depth++;
7477 stack[sp++] = latch;
7486 for (e = node->pred; e; e = e->pred_next)
7488 basic_block ancestor = e->src;
7490 /* If each ancestor not marked as part of loop, add to set of
7491 loop nodes and push on to stack. */
7492 if (ancestor != ENTRY_BLOCK_PTR
7493 && ! TEST_BIT (nodes, ancestor->index))
7495 SET_BIT (nodes, ancestor->index);
7496 ancestor->loop_depth++;
7498 stack[sp++] = ancestor;
7506 /* Compute the depth first search order and store in the array
7507 DFS_ORDER if non-zero, marking the nodes visited in VISITED. If
7508 RC_ORDER is non-zero, return the reverse completion number for each
7509 node. Returns the number of nodes visited. A depth first search
7510 tries to get as far away from the starting point as quickly as
7514 flow_depth_first_order_compute (dfs_order, rc_order)
7521 int rcnum = n_basic_blocks - 1;
7524 /* Allocate stack for back-tracking up CFG. */
7525 stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
7528 /* Allocate bitmap to track nodes that have been visited. */
7529 visited = sbitmap_alloc (n_basic_blocks);
7531 /* None of the nodes in the CFG have been visited yet. */
7532 sbitmap_zero (visited);
7534 /* Push the first edge on to the stack. */
7535 stack[sp++] = ENTRY_BLOCK_PTR->succ;
7543 /* Look at the edge on the top of the stack. */
7548 /* Check if the edge destination has been visited yet. */
7549 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
7551 /* Mark that we have visited the destination. */
7552 SET_BIT (visited, dest->index);
7555 dfs_order[dfsnum++] = dest->index;
7559 /* Since the DEST node has been visited for the first
7560 time, check its successors. */
7561 stack[sp++] = dest->succ;
7565 /* There are no successors for the DEST node so assign
7566 its reverse completion number. */
7568 rc_order[rcnum--] = dest->index;
7573 if (! e->succ_next && src != ENTRY_BLOCK_PTR)
7575 /* There are no more successors for the SRC node
7576 so assign its reverse completion number. */
7578 rc_order[rcnum--] = src->index;
7582 stack[sp - 1] = e->succ_next;
7589 sbitmap_free (visited);
7591 /* The number of nodes visited should not be greater than
7593 if (dfsnum > n_basic_blocks)
7596 /* There are some nodes left in the CFG that are unreachable. */
7597 if (dfsnum < n_basic_blocks)
7602 /* Compute the depth first search order on the _reverse_ graph and
7603 store in the array DFS_ORDER, marking the nodes visited in VISITED.
7604 Returns the number of nodes visited.
7606 The computation is split into three pieces:
7608 flow_dfs_compute_reverse_init () creates the necessary data
7611 flow_dfs_compute_reverse_add_bb () adds a basic block to the data
7612 structures. The block will start the search.
7614 flow_dfs_compute_reverse_execute () continues (or starts) the
7615 search using the block on the top of the stack, stopping when the
7618 flow_dfs_compute_reverse_finish () destroys the necessary data
7621 Thus, the user will probably call ..._init(), call ..._add_bb() to
7622 add a beginning basic block to the stack, call ..._execute(),
7623 possibly add another bb to the stack and again call ..._execute(),
7624 ..., and finally call _finish(). */
7626 /* Initialize the data structures used for depth-first search on the
7627 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
7628 added to the basic block stack. DATA is the current depth-first
7629 search context. If INITIALIZE_STACK is non-zero, there is an
7630 element on the stack. */
7633 flow_dfs_compute_reverse_init (data)
7634 depth_first_search_ds data;
7636 /* Allocate stack for back-tracking up CFG. */
7638 (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
7639 * sizeof (basic_block));
7642 /* Allocate bitmap to track nodes that have been visited. */
7643 data->visited_blocks = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1));
7645 /* None of the nodes in the CFG have been visited yet. */
7646 sbitmap_zero (data->visited_blocks);
7651 /* Add the specified basic block to the top of the dfs data
7652 structures. When the search continues, it will start at the
7656 flow_dfs_compute_reverse_add_bb (data, bb)
7657 depth_first_search_ds data;
7660 data->stack[data->sp++] = bb;
7664 /* Continue the depth-first search through the reverse graph starting
7665 with the block at the stack's top and ending when the stack is
7666 empty. Visited nodes are marked. Returns an unvisited basic
7667 block, or NULL if there is none available. */
7670 flow_dfs_compute_reverse_execute (data)
7671 depth_first_search_ds data;
7677 while (data->sp > 0)
7679 bb = data->stack[--data->sp];
7681 /* Mark that we have visited this node. */
7682 if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
7684 SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
7686 /* Perform depth-first search on adjacent vertices. */
7687 for (e = bb->pred; e; e = e->pred_next)
7688 flow_dfs_compute_reverse_add_bb (data, e->src);
7692 /* Determine if there are unvisited basic blocks. */
7693 for (i = n_basic_blocks - (INVALID_BLOCK + 1); --i >= 0;)
7694 if (!TEST_BIT (data->visited_blocks, i))
7695 return BASIC_BLOCK (i + (INVALID_BLOCK + 1));
7699 /* Destroy the data structures needed for depth-first search on the
7703 flow_dfs_compute_reverse_finish (data)
7704 depth_first_search_ds data;
7707 sbitmap_free (data->visited_blocks);
7711 /* Return the block for the pre-header of the loop with header
7712 HEADER where DOM specifies the dominator information. Return NULL if
7713 there is no pre-header. */
7716 flow_loop_pre_header_find (header, dom)
7720 basic_block pre_header;
7723 /* If block p is a predecessor of the header and is the only block
7724 that the header does not dominate, then it is the pre-header. */
7726 for (e = header->pred; e; e = e->pred_next)
7728 basic_block node = e->src;
7730 if (node != ENTRY_BLOCK_PTR
7731 && ! TEST_BIT (dom[node->index], header->index))
7733 if (pre_header == NULL)
7737 /* There are multiple edges into the header from outside
7738 the loop so there is no pre-header block. */
7747 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
7748 previously added. The insertion algorithm assumes that the loops
7749 are added in the order found by a depth first search of the CFG. */
7752 flow_loop_tree_node_add (prevloop, loop)
7753 struct loop *prevloop;
7757 if (flow_loop_nested_p (prevloop, loop))
7759 prevloop->inner = loop;
7760 loop->outer = prevloop;
7764 while (prevloop->outer)
7766 if (flow_loop_nested_p (prevloop->outer, loop))
7768 prevloop->next = loop;
7769 loop->outer = prevloop->outer;
7772 prevloop = prevloop->outer;
7775 prevloop->next = loop;
7779 /* Build the loop hierarchy tree for LOOPS. */
7782 flow_loops_tree_build (loops)
7783 struct loops *loops;
7788 num_loops = loops->num;
7792 /* Root the loop hierarchy tree with the first loop found.
7793 Since we used a depth first search this should be the
7795 loops->tree = &loops->array[0];
7796 loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
7798 /* Add the remaining loops to the tree. */
7799 for (i = 1; i < num_loops; i++)
7800 flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
7803 /* Helper function to compute loop nesting depth and enclosed loop level
7804 for the natural loop specified by LOOP at the loop depth DEPTH.
7805 Returns the loop level. */
7808 flow_loop_level_compute (loop, depth)
7818 /* Traverse loop tree assigning depth and computing level as the
7819 maximum level of all the inner loops of this loop. The loop
7820 level is equivalent to the height of the loop in the loop tree
7821 and corresponds to the number of enclosed loop levels (including
7823 for (inner = loop->inner; inner; inner = inner->next)
7827 ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
7832 loop->level = level;
7833 loop->depth = depth;
7837 /* Compute the loop nesting depth and enclosed loop level for the loop
7838 hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
7842 flow_loops_level_compute (loops)
7843 struct loops *loops;
7849 /* Traverse all the outer level loops. */
7850 for (loop = loops->tree; loop; loop = loop->next)
7852 level = flow_loop_level_compute (loop, 1);
7859 /* Find all the natural loops in the function and save in LOOPS structure
7860 and recalculate loop_depth information in basic block structures.
7861 Return the number of natural loops found. */
7864 flow_loops_find (loops)
7865 struct loops *loops;
7877 loops->array = NULL;
7882 /* Taking care of this degenerate case makes the rest of
7883 this code simpler. */
7884 if (n_basic_blocks == 0)
7887 /* Compute the dominators. */
7888 dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7889 compute_flow_dominators (dom, NULL);
7891 /* Count the number of loop edges (back edges). This should be the
7892 same as the number of natural loops. Also clear the loop_depth
7893 and as we work from inner->outer in a loop nest we call
7894 find_loop_nodes_find which will increment loop_depth for nodes
7895 within the current loop, which happens to enclose inner loops. */
7898 for (b = 0; b < n_basic_blocks; b++)
7900 BASIC_BLOCK (b)->loop_depth = 0;
7901 for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
7903 basic_block latch = e->src;
7905 /* Look for back edges where a predecessor is dominated
7906 by this block. A natural loop has a single entry
7907 node (header) that dominates all the nodes in the
7908 loop. It also has single back edge to the header
7909 from a latch node. Note that multiple natural loops
7910 may share the same header. */
7911 if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
7918 /* Compute depth first search order of the CFG so that outer
7919 natural loops will be found before inner natural loops. */
7920 dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7921 rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7922 flow_depth_first_order_compute (dfs_order, rc_order);
7924 /* Allocate loop structures. */
7926 = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
7928 headers = sbitmap_alloc (n_basic_blocks);
7929 sbitmap_zero (headers);
7931 loops->shared_headers = sbitmap_alloc (n_basic_blocks);
7932 sbitmap_zero (loops->shared_headers);
7934 /* Find and record information about all the natural loops
7937 for (b = 0; b < n_basic_blocks; b++)
7941 /* Search the nodes of the CFG in DFS order that we can find
7942 outer loops first. */
7943 header = BASIC_BLOCK (rc_order[b]);
7945 /* Look for all the possible latch blocks for this header. */
7946 for (e = header->pred; e; e = e->pred_next)
7948 basic_block latch = e->src;
7950 /* Look for back edges where a predecessor is dominated
7951 by this block. A natural loop has a single entry
7952 node (header) that dominates all the nodes in the
7953 loop. It also has single back edge to the header
7954 from a latch node. Note that multiple natural loops
7955 may share the same header. */
7956 if (latch != ENTRY_BLOCK_PTR
7957 && TEST_BIT (dom[latch->index], header->index))
7961 loop = loops->array + num_loops;
7963 loop->header = header;
7964 loop->latch = latch;
7965 loop->num = num_loops;
7967 /* Keep track of blocks that are loop headers so
7968 that we can tell which loops should be merged. */
7969 if (TEST_BIT (headers, header->index))
7970 SET_BIT (loops->shared_headers, header->index);
7971 SET_BIT (headers, header->index);
7973 /* Find nodes contained within the loop. */
7974 loop->nodes = sbitmap_alloc (n_basic_blocks);
7976 = flow_loop_nodes_find (header, latch, loop->nodes);
7978 /* Compute first and last blocks within the loop.
7979 These are often the same as the loop header and
7980 loop latch respectively, but this is not always
7983 = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
7985 = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
7987 /* Find edges which enter the loop header.
7988 Note that the entry edges should only
7989 enter the header of a natural loop. */
7991 = flow_loop_entry_edges_find (loop->header, loop->nodes,
7992 &loop->entry_edges);
7994 /* Find edges which exit the loop. */
7996 = flow_loop_exit_edges_find (loop->nodes,
7999 /* Look to see if the loop has a pre-header node. */
8000 loop->pre_header = flow_loop_pre_header_find (header, dom);
8007 /* Natural loops with shared headers may either be disjoint or
8008 nested. Disjoint loops with shared headers cannot be inner
8009 loops and should be merged. For now just mark loops that share
8011 for (i = 0; i < num_loops; i++)
8012 if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
8013 loops->array[i].shared = 1;
8015 sbitmap_free (headers);
8018 loops->num = num_loops;
8020 /* Save CFG derived information to avoid recomputing it. */
8021 loops->cfg.dom = dom;
8022 loops->cfg.dfs_order = dfs_order;
8023 loops->cfg.rc_order = rc_order;
8025 /* Build the loop hierarchy tree. */
8026 flow_loops_tree_build (loops);
8028 /* Assign the loop nesting depth and enclosed loop level for each
8030 loops->levels = flow_loops_level_compute (loops);
8035 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
8038 flow_loop_outside_edge_p (loop, e)
8039 const struct loop *loop;
8042 if (e->dest != loop->header)
8044 return (e->src == ENTRY_BLOCK_PTR)
8045 || ! TEST_BIT (loop->nodes, e->src->index);
8048 /* Clear LOG_LINKS fields of insns in a chain.
8049 Also clear the global_live_at_{start,end} fields of the basic block
8053 clear_log_links (insns)
8059 for (i = insns; i; i = NEXT_INSN (i))
8063 for (b = 0; b < n_basic_blocks; b++)
8065 basic_block bb = BASIC_BLOCK (b);
8067 bb->global_live_at_start = NULL;
8068 bb->global_live_at_end = NULL;
8071 ENTRY_BLOCK_PTR->global_live_at_end = NULL;
8072 EXIT_BLOCK_PTR->global_live_at_start = NULL;
8075 /* Given a register bitmap, turn on the bits in a HARD_REG_SET that
8076 correspond to the hard registers, if any, set in that map. This
8077 could be done far more efficiently by having all sorts of special-cases
8078 with moving single words, but probably isn't worth the trouble. */
8081 reg_set_to_hard_reg_set (to, from)
8087 EXECUTE_IF_SET_IN_BITMAP
8090 if (i >= FIRST_PSEUDO_REGISTER)
8092 SET_HARD_REG_BIT (*to, i);