1 /* Data flow analysis for GNU compiler.
2 Copyright (C) 1987, 88, 92-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 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_crosses 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 "basic-block.h"
127 #include "insn-config.h"
129 #include "hard-reg-set.h"
132 #include "function.h"
136 #include "insn-flags.h"
140 #define obstack_chunk_alloc xmalloc
141 #define obstack_chunk_free free
144 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
145 the stack pointer does not matter. The value is tested only in
146 functions that have frame pointers.
147 No definition is equivalent to always zero. */
148 #ifndef EXIT_IGNORE_STACK
149 #define EXIT_IGNORE_STACK 0
152 #ifndef HAVE_epilogue
153 #define HAVE_epilogue 0
156 #ifndef HAVE_prologue
157 #define HAVE_prologue 0
160 /* The contents of the current function definition are allocated
161 in this obstack, and all are freed at the end of the function.
162 For top-level functions, this is temporary_obstack.
163 Separate obstacks are made for nested functions. */
165 extern struct obstack
*function_obstack
;
167 /* Number of basic blocks in the current function. */
171 /* Number of edges in the current function. */
175 /* The basic block array. */
177 varray_type basic_block_info
;
179 /* The special entry and exit blocks. */
181 struct basic_block_def entry_exit_blocks
[2] =
188 NULL
, /* local_set */
189 NULL
, /* global_live_at_start */
190 NULL
, /* global_live_at_end */
192 ENTRY_BLOCK
, /* index */
194 -1, -1 /* eh_beg, eh_end */
201 NULL
, /* local_set */
202 NULL
, /* global_live_at_start */
203 NULL
, /* global_live_at_end */
205 EXIT_BLOCK
, /* index */
207 -1, -1 /* eh_beg, eh_end */
211 /* Nonzero if the second flow pass has completed. */
214 /* Maximum register number used in this function, plus one. */
218 /* Indexed by n, giving various register information */
220 varray_type reg_n_info
;
222 /* Size of the reg_n_info table. */
224 unsigned int reg_n_max
;
226 /* Element N is the next insn that uses (hard or pseudo) register number N
227 within the current basic block; or zero, if there is no such insn.
228 This is valid only during the final backward scan in propagate_block. */
230 static rtx
*reg_next_use
;
232 /* Size of a regset for the current function,
233 in (1) bytes and (2) elements. */
238 /* Regset of regs live when calls to `setjmp'-like functions happen. */
239 /* ??? Does this exist only for the setjmp-clobbered warning message? */
241 regset regs_live_at_setjmp
;
243 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
244 that have to go in the same hard reg.
245 The first two regs in the list are a pair, and the next two
246 are another pair, etc. */
249 /* Depth within loops of basic block being scanned for lifetime analysis,
250 plus one. This is the weight attached to references to registers. */
252 static int loop_depth
;
254 /* During propagate_block, this is non-zero if the value of CC0 is live. */
258 /* During propagate_block, this contains a list of all the MEMs we are
259 tracking for dead store elimination. */
261 static rtx mem_set_list
;
263 /* Set of registers that may be eliminable. These are handled specially
264 in updating regs_ever_live. */
266 static HARD_REG_SET elim_reg_set
;
268 /* The basic block structure for every insn, indexed by uid. */
270 varray_type basic_block_for_insn
;
272 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
273 /* ??? Should probably be using LABEL_NUSES instead. It would take a
274 bit of surgery to be able to use or co-opt the routines in jump. */
276 static rtx label_value_list
;
278 /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
280 #define INSN_VOLATILE(INSN) bitmap_bit_p (uid_volatile, INSN_UID (INSN))
281 #define SET_INSN_VOLATILE(INSN) bitmap_set_bit (uid_volatile, INSN_UID (INSN))
282 static bitmap uid_volatile
;
284 /* Forward declarations */
285 static int count_basic_blocks
PROTO((rtx
));
286 static rtx find_basic_blocks_1
PROTO((rtx
));
287 static void create_basic_block
PROTO((int, rtx
, rtx
, rtx
));
288 static void clear_edges
PROTO((void));
289 static void make_edges
PROTO((rtx
));
290 static void make_edge
PROTO((sbitmap
*, basic_block
,
292 static void make_label_edge
PROTO((sbitmap
*, basic_block
,
294 static void make_eh_edge
PROTO((sbitmap
*, eh_nesting_info
*,
295 basic_block
, rtx
, int));
296 static void mark_critical_edges
PROTO((void));
297 static void move_stray_eh_region_notes
PROTO((void));
298 static void record_active_eh_regions
PROTO((rtx
));
300 static void commit_one_edge_insertion
PROTO((edge
));
302 static void delete_unreachable_blocks
PROTO((void));
303 static void delete_eh_regions
PROTO((void));
304 static int can_delete_note_p
PROTO((rtx
));
305 static int delete_block
PROTO((basic_block
));
306 static void expunge_block
PROTO((basic_block
));
307 static rtx flow_delete_insn
PROTO((rtx
));
308 static int can_delete_label_p
PROTO((rtx
));
309 static int merge_blocks_move_predecessor_nojumps
PROTO((basic_block
,
311 static int merge_blocks_move_successor_nojumps
PROTO((basic_block
,
313 static void merge_blocks_nomove
PROTO((basic_block
, basic_block
));
314 static int merge_blocks
PROTO((edge
,basic_block
,basic_block
));
315 static void try_merge_blocks
PROTO((void));
316 static void tidy_fallthru_edge
PROTO((edge
,basic_block
,basic_block
));
317 static void calculate_loop_depth
PROTO((rtx
));
319 static int verify_wide_reg_1
PROTO((rtx
*, void *));
320 static void verify_wide_reg
PROTO((int, rtx
, rtx
));
321 static void verify_local_live_at_start
PROTO((regset
, basic_block
));
322 static int set_noop_p
PROTO((rtx
));
323 static int noop_move_p
PROTO((rtx
));
324 static void notice_stack_pointer_modification
PROTO ((rtx
, rtx
, void *));
325 static void record_volatile_insns
PROTO((rtx
));
326 static void mark_reg
PROTO((regset
, rtx
));
327 static void mark_regs_live_at_end
PROTO((regset
));
328 static void life_analysis_1
PROTO((rtx
, int, int));
329 static void calculate_global_regs_live
PROTO((sbitmap
, sbitmap
, int));
330 static void propagate_block
PROTO((regset
, rtx
, rtx
,
332 static int insn_dead_p
PROTO((rtx
, regset
, int, rtx
));
333 static int libcall_dead_p
PROTO((rtx
, regset
, rtx
, rtx
));
334 static void mark_set_regs
PROTO((regset
, regset
, rtx
,
336 static void mark_set_1
PROTO((regset
, regset
, rtx
,
339 static void find_auto_inc
PROTO((regset
, rtx
, rtx
));
340 static int try_pre_increment_1
PROTO((rtx
));
341 static int try_pre_increment
PROTO((rtx
, rtx
, HOST_WIDE_INT
));
343 static void mark_used_regs
PROTO((regset
, regset
, rtx
, int, rtx
));
344 void dump_flow_info
PROTO((FILE *));
345 void debug_flow_info
PROTO((void));
346 static void dump_edge_info
PROTO((FILE *, edge
, int));
348 static void count_reg_sets_1
PROTO ((rtx
));
349 static void count_reg_sets
PROTO ((rtx
));
350 static void count_reg_references
PROTO ((rtx
));
351 static void invalidate_mems_from_autoinc
PROTO ((rtx
));
352 static void remove_edge
PROTO ((edge
));
353 static void remove_fake_successors
PROTO ((basic_block
));
355 /* This function is always defined so it can be called from the
356 debugger, and it is declared extern so we don't get warnings about
358 void verify_flow_info
PROTO ((void));
361 /* Find basic blocks of the current function.
362 F is the first insn of the function and NREGS the number of register
366 find_basic_blocks (f
, nregs
, file
, do_cleanup
)
368 int nregs ATTRIBUTE_UNUSED
;
369 FILE *file ATTRIBUTE_UNUSED
;
374 /* Flush out existing data. */
375 if (basic_block_info
!= NULL
)
381 /* Clear bb->aux on all extant basic blocks. We'll use this as a
382 tag for reuse during create_basic_block, just in case some pass
383 copies around basic block notes improperly. */
384 for (i
= 0; i
< n_basic_blocks
; ++i
)
385 BASIC_BLOCK (i
)->aux
= NULL
;
387 VARRAY_FREE (basic_block_info
);
390 n_basic_blocks
= count_basic_blocks (f
);
392 /* Size the basic block table. The actual structures will be allocated
393 by find_basic_blocks_1, since we want to keep the structure pointers
394 stable across calls to find_basic_blocks. */
395 /* ??? This whole issue would be much simpler if we called find_basic_blocks
396 exactly once, and thereafter we don't have a single long chain of
397 instructions at all until close to the end of compilation when we
398 actually lay them out. */
400 VARRAY_BB_INIT (basic_block_info
, n_basic_blocks
, "basic_block_info");
402 label_value_list
= find_basic_blocks_1 (f
);
404 /* Record the block to which an insn belongs. */
405 /* ??? This should be done another way, by which (perhaps) a label is
406 tagged directly with the basic block that it starts. It is used for
407 more than that currently, but IMO that is the only valid use. */
409 max_uid
= get_max_uid ();
411 /* Leave space for insns life_analysis makes in some cases for auto-inc.
412 These cases are rare, so we don't need too much space. */
413 max_uid
+= max_uid
/ 10;
416 compute_bb_for_insn (max_uid
);
418 /* Discover the edges of our cfg. */
420 record_active_eh_regions (f
);
421 make_edges (label_value_list
);
423 /* Delete unreachable blocks, then merge blocks when possible. */
427 delete_unreachable_blocks ();
428 move_stray_eh_region_notes ();
429 record_active_eh_regions (f
);
433 /* Mark critical edges. */
435 mark_critical_edges ();
437 /* Discover the loop depth at the start of each basic block to aid
438 register allocation. */
439 calculate_loop_depth (f
);
441 /* Kill the data we won't maintain. */
442 label_value_list
= NULL_RTX
;
444 #ifdef ENABLE_CHECKING
449 /* Count the basic blocks of the function. */
452 count_basic_blocks (f
)
456 register RTX_CODE prev_code
;
457 register int count
= 0;
459 int call_had_abnormal_edge
= 0;
460 rtx prev_call
= NULL_RTX
;
462 prev_code
= JUMP_INSN
;
463 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
465 register RTX_CODE code
= GET_CODE (insn
);
467 if (code
== CODE_LABEL
468 || (GET_RTX_CLASS (code
) == 'i'
469 && (prev_code
== JUMP_INSN
470 || prev_code
== BARRIER
471 || (prev_code
== CALL_INSN
&& call_had_abnormal_edge
))))
475 /* If the previous insn was a call that did not create an
476 abnormal edge, we want to add a nop so that the CALL_INSN
477 itself is not at basic_block_end. This allows us to
478 easily distinguish between normal calls and those which
479 create abnormal edges in the flow graph. */
481 if (count
> 0 && prev_call
!= 0 && !call_had_abnormal_edge
)
483 rtx nop
= gen_rtx_USE (VOIDmode
, const0_rtx
);
484 emit_insn_after (nop
, prev_call
);
488 /* Record whether this call created an edge. */
489 if (code
== CALL_INSN
)
491 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
492 int region
= (note
? XWINT (XEXP (note
, 0), 0) : 1);
494 call_had_abnormal_edge
= 0;
496 /* If there is a specified EH region, we have an edge. */
497 if (eh_region
&& region
> 0)
498 call_had_abnormal_edge
= 1;
501 /* If there is a nonlocal goto label and the specified
502 region number isn't -1, we have an edge. (0 means
503 no throw, but might have a nonlocal goto). */
504 if (nonlocal_goto_handler_labels
&& region
>= 0)
505 call_had_abnormal_edge
= 1;
508 else if (code
!= NOTE
)
509 prev_call
= NULL_RTX
;
513 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
)
515 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
520 /* The rest of the compiler works a bit smoother when we don't have to
521 check for the edge case of do-nothing functions with no basic blocks. */
524 emit_insn (gen_rtx_USE (VOIDmode
, const0_rtx
));
531 /* Find all basic blocks of the function whose first insn is F.
533 Collect and return a list of labels whose addresses are taken. This
534 will be used in make_edges for use with computed gotos. */
537 find_basic_blocks_1 (f
)
540 register rtx insn
, next
;
541 int call_has_abnormal_edge
= 0;
543 rtx bb_note
= NULL_RTX
;
544 rtx eh_list
= NULL_RTX
;
545 rtx label_value_list
= NULL_RTX
;
549 /* We process the instructions in a slightly different way than we did
550 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
551 closed out the previous block, so that it gets attached at the proper
552 place. Since this form should be equivalent to the previous,
553 count_basic_blocks continues to use the old form as a check. */
555 for (insn
= f
; insn
; insn
= next
)
557 enum rtx_code code
= GET_CODE (insn
);
559 next
= NEXT_INSN (insn
);
561 if (code
== CALL_INSN
)
563 /* Record whether this call created an edge. */
564 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
565 int region
= (note
? XWINT (XEXP (note
, 0), 0) : 1);
566 call_has_abnormal_edge
= 0;
568 /* If there is an EH region, we have an edge. */
569 if (eh_list
&& region
> 0)
570 call_has_abnormal_edge
= 1;
573 /* If there is a nonlocal goto label and the specified
574 region number isn't -1, we have an edge. (0 means
575 no throw, but might have a nonlocal goto). */
576 if (nonlocal_goto_handler_labels
&& region
>= 0)
577 call_has_abnormal_edge
= 1;
585 int kind
= NOTE_LINE_NUMBER (insn
);
587 /* Keep a LIFO list of the currently active exception notes. */
588 if (kind
== NOTE_INSN_EH_REGION_BEG
)
589 eh_list
= alloc_INSN_LIST (insn
, eh_list
);
590 else if (kind
== NOTE_INSN_EH_REGION_END
)
593 eh_list
= XEXP (eh_list
, 1);
594 free_INSN_LIST_node (t
);
597 /* Look for basic block notes with which to keep the
598 basic_block_info pointers stable. Unthread the note now;
599 we'll put it back at the right place in create_basic_block.
600 Or not at all if we've already found a note in this block. */
601 else if (kind
== NOTE_INSN_BASIC_BLOCK
)
603 if (bb_note
== NULL_RTX
)
605 next
= flow_delete_insn (insn
);
612 /* A basic block starts at a label. If we've closed one off due
613 to a barrier or some such, no need to do it again. */
614 if (head
!= NULL_RTX
)
616 /* While we now have edge lists with which other portions of
617 the compiler might determine a call ending a basic block
618 does not imply an abnormal edge, it will be a bit before
619 everything can be updated. So continue to emit a noop at
620 the end of such a block. */
621 if (GET_CODE (end
) == CALL_INSN
)
623 rtx nop
= gen_rtx_USE (VOIDmode
, const0_rtx
);
624 end
= emit_insn_after (nop
, end
);
627 create_basic_block (i
++, head
, end
, bb_note
);
634 /* A basic block ends at a jump. */
635 if (head
== NULL_RTX
)
639 /* ??? Make a special check for table jumps. The way this
640 happens is truly and amazingly gross. We are about to
641 create a basic block that contains just a code label and
642 an addr*vec jump insn. Worse, an addr_diff_vec creates
643 its own natural loop.
645 Prevent this bit of brain damage, pasting things together
646 correctly in make_edges.
648 The correct solution involves emitting the table directly
649 on the tablejump instruction as a note, or JUMP_LABEL. */
651 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
652 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
660 goto new_bb_inclusive
;
663 /* A basic block ends at a barrier. It may be that an unconditional
664 jump already closed the basic block -- no need to do it again. */
665 if (head
== NULL_RTX
)
668 /* While we now have edge lists with which other portions of the
669 compiler might determine a call ending a basic block does not
670 imply an abnormal edge, it will be a bit before everything can
671 be updated. So continue to emit a noop at the end of such a
673 if (GET_CODE (end
) == CALL_INSN
)
675 rtx nop
= gen_rtx_USE (VOIDmode
, const0_rtx
);
676 end
= emit_insn_after (nop
, end
);
678 goto new_bb_exclusive
;
681 /* A basic block ends at a call that can either throw or
682 do a non-local goto. */
683 if (call_has_abnormal_edge
)
686 if (head
== NULL_RTX
)
691 create_basic_block (i
++, head
, end
, bb_note
);
692 head
= end
= NULL_RTX
;
699 if (GET_RTX_CLASS (code
) == 'i')
701 if (head
== NULL_RTX
)
708 if (GET_RTX_CLASS (code
) == 'i')
712 /* Make a list of all labels referred to other than by jumps
713 (which just don't have the REG_LABEL notes).
715 Make a special exception for labels followed by an ADDR*VEC,
716 as this would be a part of the tablejump setup code.
718 Make a special exception for the eh_return_stub_label, which
719 we know isn't part of any otherwise visible control flow. */
721 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
722 if (REG_NOTE_KIND (note
) == REG_LABEL
)
724 rtx lab
= XEXP (note
, 0), next
;
726 if (lab
== eh_return_stub_label
)
728 else if ((next
= next_nonnote_insn (lab
)) != NULL
729 && GET_CODE (next
) == JUMP_INSN
730 && (GET_CODE (PATTERN (next
)) == ADDR_VEC
731 || GET_CODE (PATTERN (next
)) == ADDR_DIFF_VEC
))
735 = alloc_EXPR_LIST (0, XEXP (note
, 0), label_value_list
);
740 if (head
!= NULL_RTX
)
741 create_basic_block (i
++, head
, end
, bb_note
);
743 if (i
!= n_basic_blocks
)
746 return label_value_list
;
749 /* Create a new basic block consisting of the instructions between
750 HEAD and END inclusive. Reuses the note and basic block struct
751 in BB_NOTE, if any. */
754 create_basic_block (index
, head
, end
, bb_note
)
756 rtx head
, end
, bb_note
;
761 && ! RTX_INTEGRATED_P (bb_note
)
762 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
765 /* If we found an existing note, thread it back onto the chain. */
767 if (GET_CODE (head
) == CODE_LABEL
)
768 add_insn_after (bb_note
, head
);
771 add_insn_before (bb_note
, head
);
777 /* Otherwise we must create a note and a basic block structure.
778 Since we allow basic block structs in rtl, give the struct
779 the same lifetime by allocating it off the function obstack
780 rather than using malloc. */
782 bb
= (basic_block
) obstack_alloc (function_obstack
, sizeof (*bb
));
783 memset (bb
, 0, sizeof (*bb
));
785 if (GET_CODE (head
) == CODE_LABEL
)
786 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
789 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
792 NOTE_BASIC_BLOCK (bb_note
) = bb
;
795 /* Always include the bb note in the block. */
796 if (NEXT_INSN (end
) == bb_note
)
802 BASIC_BLOCK (index
) = bb
;
804 /* Tag the block so that we know it has been used when considering
805 other basic block notes. */
809 /* Records the basic block struct in BB_FOR_INSN, for every instruction
810 indexed by INSN_UID. MAX is the size of the array. */
813 compute_bb_for_insn (max
)
818 if (basic_block_for_insn
)
819 VARRAY_FREE (basic_block_for_insn
);
820 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
822 for (i
= 0; i
< n_basic_blocks
; ++i
)
824 basic_block bb
= BASIC_BLOCK (i
);
831 int uid
= INSN_UID (insn
);
833 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
836 insn
= NEXT_INSN (insn
);
841 /* Free the memory associated with the edge structures. */
849 for (i
= 0; i
< n_basic_blocks
; ++i
)
851 basic_block bb
= BASIC_BLOCK (i
);
853 for (e
= bb
->succ
; e
; e
= n
)
863 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= n
)
869 ENTRY_BLOCK_PTR
->succ
= 0;
870 EXIT_BLOCK_PTR
->pred
= 0;
875 /* Identify the edges between basic blocks.
877 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
878 that are otherwise unreachable may be reachable with a non-local goto.
880 BB_EH_END is an array indexed by basic block number in which we record
881 the list of exception regions active at the end of the basic block. */
884 make_edges (label_value_list
)
885 rtx label_value_list
;
888 eh_nesting_info
*eh_nest_info
= init_eh_nesting_info ();
889 sbitmap
*edge_cache
= NULL
;
891 /* Assume no computed jump; revise as we create edges. */
892 current_function_has_computed_jump
= 0;
894 /* Heavy use of computed goto in machine-generated code can lead to
895 nearly fully-connected CFGs. In that case we spend a significant
896 amount of time searching the edge lists for duplicates. */
897 if (forced_labels
|| label_value_list
)
899 edge_cache
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
900 sbitmap_vector_zero (edge_cache
, n_basic_blocks
);
903 /* By nature of the way these get numbered, block 0 is always the entry. */
904 make_edge (edge_cache
, ENTRY_BLOCK_PTR
, BASIC_BLOCK (0), EDGE_FALLTHRU
);
906 for (i
= 0; i
< n_basic_blocks
; ++i
)
908 basic_block bb
= BASIC_BLOCK (i
);
911 int force_fallthru
= 0;
913 /* Examine the last instruction of the block, and discover the
914 ways we can leave the block. */
917 code
= GET_CODE (insn
);
920 if (code
== JUMP_INSN
)
924 /* ??? Recognize a tablejump and do the right thing. */
925 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
926 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
927 && GET_CODE (tmp
) == JUMP_INSN
928 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
929 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
934 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
935 vec
= XVEC (PATTERN (tmp
), 0);
937 vec
= XVEC (PATTERN (tmp
), 1);
939 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
940 make_label_edge (edge_cache
, bb
,
941 XEXP (RTVEC_ELT (vec
, j
), 0), 0);
943 /* Some targets (eg, ARM) emit a conditional jump that also
944 contains the out-of-range target. Scan for these and
945 add an edge if necessary. */
946 if ((tmp
= single_set (insn
)) != NULL
947 && SET_DEST (tmp
) == pc_rtx
948 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
949 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
)
950 make_label_edge (edge_cache
, bb
,
951 XEXP (XEXP (SET_SRC (tmp
), 2), 0), 0);
953 #ifdef CASE_DROPS_THROUGH
954 /* Silly VAXen. The ADDR_VEC is going to be in the way of
955 us naturally detecting fallthru into the next block. */
960 /* If this is a computed jump, then mark it as reaching
961 everything on the label_value_list and forced_labels list. */
962 else if (computed_jump_p (insn
))
964 current_function_has_computed_jump
= 1;
966 for (x
= label_value_list
; x
; x
= XEXP (x
, 1))
967 make_label_edge (edge_cache
, bb
, XEXP (x
, 0), EDGE_ABNORMAL
);
969 for (x
= forced_labels
; x
; x
= XEXP (x
, 1))
970 make_label_edge (edge_cache
, bb
, XEXP (x
, 0), EDGE_ABNORMAL
);
973 /* Returns create an exit out. */
974 else if (returnjump_p (insn
))
975 make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, 0);
977 /* Otherwise, we have a plain conditional or unconditional jump. */
980 if (! JUMP_LABEL (insn
))
982 make_label_edge (edge_cache
, bb
, JUMP_LABEL (insn
), 0);
986 /* If this is a CALL_INSN, then mark it as reaching the active EH
987 handler for this CALL_INSN. If we're handling asynchronous
988 exceptions then any insn can reach any of the active handlers.
990 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
992 if (code
== CALL_INSN
|| asynchronous_exceptions
)
994 /* If there's an EH region active at the end of a block,
995 add the appropriate edges. */
997 make_eh_edge (edge_cache
, eh_nest_info
, bb
, insn
, bb
->eh_end
);
999 /* If we have asynchronous exceptions, do the same for *all*
1000 exception regions active in the block. */
1001 if (asynchronous_exceptions
1002 && bb
->eh_beg
!= bb
->eh_end
)
1004 if (bb
->eh_beg
>= 0)
1005 make_eh_edge (edge_cache
, eh_nest_info
, bb
,
1006 NULL_RTX
, bb
->eh_beg
);
1008 for (x
= bb
->head
; x
!= bb
->end
; x
= NEXT_INSN (x
))
1009 if (GET_CODE (x
) == NOTE
1010 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_EH_REGION_BEG
1011 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_EH_REGION_END
))
1013 int region
= NOTE_EH_HANDLER (x
);
1014 make_eh_edge (edge_cache
, eh_nest_info
, bb
,
1019 if (code
== CALL_INSN
&& nonlocal_goto_handler_labels
)
1021 /* ??? This could be made smarter: in some cases it's possible
1022 to tell that certain calls will not do a nonlocal goto.
1024 For example, if the nested functions that do the nonlocal
1025 gotos do not have their addresses taken, then only calls to
1026 those functions or to other nested functions that use them
1027 could possibly do nonlocal gotos. */
1028 /* We do know that a REG_EH_REGION note with a value less
1029 than 0 is guaranteed not to perform a non-local goto. */
1030 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1031 if (!note
|| XINT (XEXP (note
, 0), 0) >= 0)
1032 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
1033 make_label_edge (edge_cache
, bb
, XEXP (x
, 0),
1034 EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
);
1038 /* We know something about the structure of the function __throw in
1039 libgcc2.c. It is the only function that ever contains eh_stub
1040 labels. It modifies its return address so that the last block
1041 returns to one of the eh_stub labels within it. So we have to
1042 make additional edges in the flow graph. */
1043 if (i
+ 1 == n_basic_blocks
&& eh_return_stub_label
!= 0)
1044 make_label_edge (edge_cache
, bb
, eh_return_stub_label
, EDGE_EH
);
1046 /* Find out if we can drop through to the next block. */
1047 insn
= next_nonnote_insn (insn
);
1048 if (!insn
|| (i
+ 1 == n_basic_blocks
&& force_fallthru
))
1049 make_edge (edge_cache
, bb
, EXIT_BLOCK_PTR
, EDGE_FALLTHRU
);
1050 else if (i
+ 1 < n_basic_blocks
)
1052 rtx tmp
= BLOCK_HEAD (i
+ 1);
1053 if (GET_CODE (tmp
) == NOTE
)
1054 tmp
= next_nonnote_insn (tmp
);
1055 if (force_fallthru
|| insn
== tmp
)
1056 make_edge (edge_cache
, bb
, BASIC_BLOCK (i
+ 1), EDGE_FALLTHRU
);
1060 free_eh_nesting_info (eh_nest_info
);
1062 sbitmap_vector_free (edge_cache
);
1065 /* Create an edge between two basic blocks. FLAGS are auxiliary information
1066 about the edge that is accumulated between calls. */
1069 make_edge (edge_cache
, src
, dst
, flags
)
1070 sbitmap
*edge_cache
;
1071 basic_block src
, dst
;
1077 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1078 many edges to them, and we didn't allocate memory for it. */
1079 use_edge_cache
= (edge_cache
1080 && src
!= ENTRY_BLOCK_PTR
1081 && dst
!= EXIT_BLOCK_PTR
);
1083 /* Make sure we don't add duplicate edges. */
1084 if (! use_edge_cache
|| TEST_BIT (edge_cache
[src
->index
], dst
->index
))
1085 for (e
= src
->succ
; e
; e
= e
->succ_next
)
1092 e
= (edge
) xcalloc (1, sizeof (*e
));
1095 e
->succ_next
= src
->succ
;
1096 e
->pred_next
= dst
->pred
;
1105 SET_BIT (edge_cache
[src
->index
], dst
->index
);
1108 /* Create an edge from a basic block to a label. */
1111 make_label_edge (edge_cache
, src
, label
, flags
)
1112 sbitmap
*edge_cache
;
1117 if (GET_CODE (label
) != CODE_LABEL
)
1120 /* If the label was never emitted, this insn is junk, but avoid a
1121 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
1122 as a result of a syntax error and a diagnostic has already been
1125 if (INSN_UID (label
) == 0)
1128 make_edge (edge_cache
, src
, BLOCK_FOR_INSN (label
), flags
);
1131 /* Create the edges generated by INSN in REGION. */
1134 make_eh_edge (edge_cache
, eh_nest_info
, src
, insn
, region
)
1135 sbitmap
*edge_cache
;
1136 eh_nesting_info
*eh_nest_info
;
1141 handler_info
**handler_list
;
1144 is_call
= (insn
&& GET_CODE (insn
) == CALL_INSN
? EDGE_ABNORMAL_CALL
: 0);
1145 num
= reachable_handlers (region
, eh_nest_info
, insn
, &handler_list
);
1148 make_label_edge (edge_cache
, src
, handler_list
[num
]->handler_label
,
1149 EDGE_ABNORMAL
| EDGE_EH
| is_call
);
1153 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1154 dangerous if we intend to move basic blocks around. Move such notes
1155 into the following block. */
1158 move_stray_eh_region_notes ()
1163 if (n_basic_blocks
< 2)
1166 b2
= BASIC_BLOCK (n_basic_blocks
- 1);
1167 for (i
= n_basic_blocks
- 2; i
>= 0; --i
, b2
= b1
)
1169 rtx insn
, next
, list
= NULL_RTX
;
1171 b1
= BASIC_BLOCK (i
);
1172 for (insn
= NEXT_INSN (b1
->end
); insn
!= b2
->head
; insn
= next
)
1174 next
= NEXT_INSN (insn
);
1175 if (GET_CODE (insn
) == NOTE
1176 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1177 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
))
1179 /* Unlink from the insn chain. */
1180 NEXT_INSN (PREV_INSN (insn
)) = next
;
1181 PREV_INSN (next
) = PREV_INSN (insn
);
1184 NEXT_INSN (insn
) = list
;
1189 if (list
== NULL_RTX
)
1192 /* Find where to insert these things. */
1194 if (GET_CODE (insn
) == CODE_LABEL
)
1195 insn
= NEXT_INSN (insn
);
1199 next
= NEXT_INSN (list
);
1200 add_insn_after (list
, insn
);
1206 /* Recompute eh_beg/eh_end for each basic block. */
1209 record_active_eh_regions (f
)
1212 rtx insn
, eh_list
= NULL_RTX
;
1214 basic_block bb
= BASIC_BLOCK (0);
1216 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
1218 if (bb
->head
== insn
)
1219 bb
->eh_beg
= (eh_list
? NOTE_EH_HANDLER (XEXP (eh_list
, 0)) : -1);
1221 if (GET_CODE (insn
) == NOTE
)
1223 int kind
= NOTE_LINE_NUMBER (insn
);
1224 if (kind
== NOTE_INSN_EH_REGION_BEG
)
1225 eh_list
= alloc_INSN_LIST (insn
, eh_list
);
1226 else if (kind
== NOTE_INSN_EH_REGION_END
)
1228 rtx t
= XEXP (eh_list
, 1);
1229 free_INSN_LIST_node (eh_list
);
1234 if (bb
->end
== insn
)
1236 bb
->eh_end
= (eh_list
? NOTE_EH_HANDLER (XEXP (eh_list
, 0)) : -1);
1238 if (i
== n_basic_blocks
)
1240 bb
= BASIC_BLOCK (i
);
1245 /* Identify critical edges and set the bits appropriately. */
1248 mark_critical_edges ()
1250 int i
, n
= n_basic_blocks
;
1253 /* We begin with the entry block. This is not terribly important now,
1254 but could be if a front end (Fortran) implemented alternate entry
1256 bb
= ENTRY_BLOCK_PTR
;
1263 /* (1) Critical edges must have a source with multiple successors. */
1264 if (bb
->succ
&& bb
->succ
->succ_next
)
1266 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1268 /* (2) Critical edges must have a destination with multiple
1269 predecessors. Note that we know there is at least one
1270 predecessor -- the edge we followed to get here. */
1271 if (e
->dest
->pred
->pred_next
)
1272 e
->flags
|= EDGE_CRITICAL
;
1274 e
->flags
&= ~EDGE_CRITICAL
;
1279 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1280 e
->flags
&= ~EDGE_CRITICAL
;
1285 bb
= BASIC_BLOCK (i
);
1289 /* Split a (typically critical) edge. Return the new block.
1290 Abort on abnormal edges.
1292 ??? The code generally expects to be called on critical edges.
1293 The case of a block ending in an unconditional jump to a
1294 block with multiple predecessors is not handled optimally. */
1297 split_edge (edge_in
)
1300 basic_block old_pred
, bb
, old_succ
;
1305 /* Abnormal edges cannot be split. */
1306 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1309 old_pred
= edge_in
->src
;
1310 old_succ
= edge_in
->dest
;
1312 /* Remove the existing edge from the destination's pred list. */
1315 for (pp
= &old_succ
->pred
; *pp
!= edge_in
; pp
= &(*pp
)->pred_next
)
1317 *pp
= edge_in
->pred_next
;
1318 edge_in
->pred_next
= NULL
;
1321 /* Create the new structures. */
1322 bb
= (basic_block
) obstack_alloc (function_obstack
, sizeof (*bb
));
1323 edge_out
= (edge
) xcalloc (1, sizeof (*edge_out
));
1326 memset (bb
, 0, sizeof (*bb
));
1327 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (function_obstack
);
1328 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (function_obstack
);
1330 /* ??? This info is likely going to be out of date very soon. */
1331 if (old_succ
->global_live_at_start
)
1333 COPY_REG_SET (bb
->global_live_at_start
, old_succ
->global_live_at_start
);
1334 COPY_REG_SET (bb
->global_live_at_end
, old_succ
->global_live_at_start
);
1338 CLEAR_REG_SET (bb
->global_live_at_start
);
1339 CLEAR_REG_SET (bb
->global_live_at_end
);
1344 bb
->succ
= edge_out
;
1347 edge_in
->flags
&= ~EDGE_CRITICAL
;
1349 edge_out
->pred_next
= old_succ
->pred
;
1350 edge_out
->succ_next
= NULL
;
1352 edge_out
->dest
= old_succ
;
1353 edge_out
->flags
= EDGE_FALLTHRU
;
1354 edge_out
->probability
= REG_BR_PROB_BASE
;
1356 old_succ
->pred
= edge_out
;
1358 /* Tricky case -- if there existed a fallthru into the successor
1359 (and we're not it) we must add a new unconditional jump around
1360 the new block we're actually interested in.
1362 Further, if that edge is critical, this means a second new basic
1363 block must be created to hold it. In order to simplify correct
1364 insn placement, do this before we touch the existing basic block
1365 ordering for the block we were really wanting. */
1366 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1369 for (e
= edge_out
->pred_next
; e
; e
= e
->pred_next
)
1370 if (e
->flags
& EDGE_FALLTHRU
)
1375 basic_block jump_block
;
1378 if ((e
->flags
& EDGE_CRITICAL
) == 0)
1380 /* Non critical -- we can simply add a jump to the end
1381 of the existing predecessor. */
1382 jump_block
= e
->src
;
1386 /* We need a new block to hold the jump. The simplest
1387 way to do the bulk of the work here is to recursively
1389 jump_block
= split_edge (e
);
1390 e
= jump_block
->succ
;
1393 /* Now add the jump insn ... */
1394 pos
= emit_jump_insn_after (gen_jump (old_succ
->head
),
1396 jump_block
->end
= pos
;
1397 emit_barrier_after (pos
);
1399 /* ... let jump know that label is in use, ... */
1400 JUMP_LABEL (pos
) = old_succ
->head
;
1401 ++LABEL_NUSES (old_succ
->head
);
1403 /* ... and clear fallthru on the outgoing edge. */
1404 e
->flags
&= ~EDGE_FALLTHRU
;
1406 /* Continue splitting the interesting edge. */
1410 /* Place the new block just in front of the successor. */
1411 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
1412 if (old_succ
== EXIT_BLOCK_PTR
)
1413 j
= n_basic_blocks
- 1;
1415 j
= old_succ
->index
;
1416 for (i
= n_basic_blocks
- 1; i
> j
; --i
)
1418 basic_block tmp
= BASIC_BLOCK (i
- 1);
1419 BASIC_BLOCK (i
) = tmp
;
1422 BASIC_BLOCK (i
) = bb
;
1425 /* Create the basic block note.
1427 Where we place the note can have a noticable impact on the generated
1428 code. Consider this cfg:
1439 If we need to insert an insn on the edge from block 0 to block 1,
1440 we want to ensure the instructions we insert are outside of any
1441 loop notes that physically sit between block 0 and block 1. Otherwise
1442 we confuse the loop optimizer into thinking the loop is a phony. */
1443 if (old_succ
!= EXIT_BLOCK_PTR
1444 && PREV_INSN (old_succ
->head
)
1445 && GET_CODE (PREV_INSN (old_succ
->head
)) == NOTE
1446 && NOTE_LINE_NUMBER (PREV_INSN (old_succ
->head
)) == NOTE_INSN_LOOP_BEG
)
1447 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
,
1448 PREV_INSN (old_succ
->head
));
1449 else if (old_succ
!= EXIT_BLOCK_PTR
)
1450 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, old_succ
->head
);
1452 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
1453 NOTE_BASIC_BLOCK (bb_note
) = bb
;
1454 bb
->head
= bb
->end
= bb_note
;
1456 /* Not quite simple -- for non-fallthru edges, we must adjust the
1457 predecessor's jump instruction to target our new block. */
1458 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1460 rtx tmp
, insn
= old_pred
->end
;
1461 rtx old_label
= old_succ
->head
;
1462 rtx new_label
= gen_label_rtx ();
1464 if (GET_CODE (insn
) != JUMP_INSN
)
1467 /* ??? Recognize a tablejump and adjust all matching cases. */
1468 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
1469 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
1470 && GET_CODE (tmp
) == JUMP_INSN
1471 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
1472 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
1477 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
1478 vec
= XVEC (PATTERN (tmp
), 0);
1480 vec
= XVEC (PATTERN (tmp
), 1);
1482 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1483 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1485 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (VOIDmode
, new_label
);
1486 --LABEL_NUSES (old_label
);
1487 ++LABEL_NUSES (new_label
);
1490 /* Handle casesi dispatch insns */
1491 if ((tmp
= single_set (insn
)) != NULL
1492 && SET_DEST (tmp
) == pc_rtx
1493 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1494 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1495 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1497 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
1499 --LABEL_NUSES (old_label
);
1500 ++LABEL_NUSES (new_label
);
1505 /* This would have indicated an abnormal edge. */
1506 if (computed_jump_p (insn
))
1509 /* A return instruction can't be redirected. */
1510 if (returnjump_p (insn
))
1513 /* If the insn doesn't go where we think, we're confused. */
1514 if (JUMP_LABEL (insn
) != old_label
)
1517 redirect_jump (insn
, new_label
);
1520 emit_label_before (new_label
, bb_note
);
1521 bb
->head
= new_label
;
1527 /* Queue instructions for insertion on an edge between two basic blocks.
1528 The new instructions and basic blocks (if any) will not appear in the
1529 CFG until commit_edge_insertions is called. */
1532 insert_insn_on_edge (pattern
, e
)
1536 /* We cannot insert instructions on an abnormal critical edge.
1537 It will be easier to find the culprit if we die now. */
1538 if ((e
->flags
& (EDGE_ABNORMAL
|EDGE_CRITICAL
))
1539 == (EDGE_ABNORMAL
|EDGE_CRITICAL
))
1542 if (e
->insns
== NULL_RTX
)
1545 push_to_sequence (e
->insns
);
1547 emit_insn (pattern
);
1549 e
->insns
= get_insns ();
1553 /* Update the CFG for the instructions queued on edge E. */
1556 commit_one_edge_insertion (e
)
1559 rtx before
= NULL_RTX
, after
= NULL_RTX
, tmp
;
1562 /* Figure out where to put these things. If the destination has
1563 one predecessor, insert there. Except for the exit block. */
1564 if (e
->dest
->pred
->pred_next
== NULL
1565 && e
->dest
!= EXIT_BLOCK_PTR
)
1569 /* Get the location correct wrt a code label, and "nice" wrt
1570 a basic block note, and before everything else. */
1572 if (GET_CODE (tmp
) == CODE_LABEL
)
1573 tmp
= NEXT_INSN (tmp
);
1574 if (GET_CODE (tmp
) == NOTE
1575 && NOTE_LINE_NUMBER (tmp
) == NOTE_INSN_BASIC_BLOCK
)
1576 tmp
= NEXT_INSN (tmp
);
1577 if (tmp
== bb
->head
)
1580 after
= PREV_INSN (tmp
);
1583 /* If the source has one successor and the edge is not abnormal,
1584 insert there. Except for the entry block. */
1585 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1586 && e
->src
->succ
->succ_next
== NULL
1587 && e
->src
!= ENTRY_BLOCK_PTR
)
1590 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1592 /* ??? Is it possible to wind up with non-simple jumps? Perhaps
1593 a jump with delay slots already filled? */
1594 if (! simplejump_p (bb
->end
))
1601 /* We'd better be fallthru, or we've lost track of what's what. */
1602 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1609 /* Otherwise we must split the edge. */
1612 bb
= split_edge (e
);
1616 /* Now that we've found the spot, do the insertion. */
1618 e
->insns
= NULL_RTX
;
1620 /* Set the new block number for these insns, if structure is allocated. */
1621 if (basic_block_for_insn
)
1624 for (i
= tmp
; i
!= NULL_RTX
; i
= NEXT_INSN (i
))
1625 set_block_for_insn (i
, bb
);
1630 emit_insns_before (tmp
, before
);
1631 if (before
== bb
->head
)
1636 tmp
= emit_insns_after (tmp
, after
);
1637 if (after
== bb
->end
)
1642 /* Update the CFG for all queued instructions. */
1645 commit_edge_insertions ()
1651 bb
= ENTRY_BLOCK_PTR
;
1656 for (e
= bb
->succ
; e
; e
= next
)
1658 next
= e
->succ_next
;
1660 commit_one_edge_insertion (e
);
1663 if (++i
>= n_basic_blocks
)
1665 bb
= BASIC_BLOCK (i
);
1669 /* Delete all unreachable basic blocks. */
1672 delete_unreachable_blocks ()
1674 basic_block
*worklist
, *tos
;
1675 int deleted_handler
;
1680 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
) * n
);
1682 /* Use basic_block->aux as a marker. Clear them all. */
1684 for (i
= 0; i
< n
; ++i
)
1685 BASIC_BLOCK (i
)->aux
= NULL
;
1687 /* Add our starting points to the worklist. Almost always there will
1688 be only one. It isn't inconcievable that we might one day directly
1689 support Fortran alternate entry points. */
1691 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
1695 /* Mark the block with a handy non-null value. */
1699 /* Iterate: find everything reachable from what we've already seen. */
1701 while (tos
!= worklist
)
1703 basic_block b
= *--tos
;
1705 for (e
= b
->succ
; e
; e
= e
->succ_next
)
1713 /* Delete all unreachable basic blocks. Count down so that we don't
1714 interfere with the block renumbering that happens in delete_block. */
1716 deleted_handler
= 0;
1718 for (i
= n
- 1; i
>= 0; --i
)
1720 basic_block b
= BASIC_BLOCK (i
);
1723 /* This block was found. Tidy up the mark. */
1726 deleted_handler
|= delete_block (b
);
1729 /* Fix up edges that now fall through, or rather should now fall through
1730 but previously required a jump around now deleted blocks. Simplify
1731 the search by only examining blocks numerically adjacent, since this
1732 is how find_basic_blocks created them. */
1734 for (i
= 1; i
< n_basic_blocks
; ++i
)
1736 basic_block b
= BASIC_BLOCK (i
- 1);
1737 basic_block c
= BASIC_BLOCK (i
);
1740 /* We care about simple conditional or unconditional jumps with
1743 If we had a conditional branch to the next instruction when
1744 find_basic_blocks was called, then there will only be one
1745 out edge for the block which ended with the conditional
1746 branch (since we do not create duplicate edges).
1748 Furthermore, the edge will be marked as a fallthru because we
1749 merge the flags for the duplicate edges. So we do not want to
1750 check that the edge is not a FALLTHRU edge. */
1751 if ((s
= b
->succ
) != NULL
1752 && s
->succ_next
== NULL
1754 /* If the jump insn has side effects, we can't tidy the edge. */
1755 && (GET_CODE (b
->end
) != JUMP_INSN
1756 || onlyjump_p (b
->end
)))
1757 tidy_fallthru_edge (s
, b
, c
);
1760 /* If we deleted an exception handler, we may have EH region begin/end
1761 blocks to remove as well. */
1762 if (deleted_handler
)
1763 delete_eh_regions ();
1768 /* Find EH regions for which there is no longer a handler, and delete them. */
1771 delete_eh_regions ()
1775 update_rethrow_references ();
1777 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1778 if (GET_CODE (insn
) == NOTE
)
1780 if ((NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
) ||
1781 (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
))
1783 int num
= NOTE_EH_HANDLER (insn
);
1784 /* A NULL handler indicates a region is no longer needed,
1785 as long as it isn't the target of a rethrow. */
1786 if (get_first_handler (num
) == NULL
&& ! rethrow_used (num
))
1788 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
1789 NOTE_SOURCE_FILE (insn
) = 0;
1795 /* Return true if NOTE is not one of the ones that must be kept paired,
1796 so that we may simply delete them. */
1799 can_delete_note_p (note
)
1802 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
1803 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
);
1806 /* Unlink a chain of insns between START and FINISH, leaving notes
1807 that must be paired. */
1810 flow_delete_insn_chain (start
, finish
)
1813 /* Unchain the insns one by one. It would be quicker to delete all
1814 of these with a single unchaining, rather than one at a time, but
1815 we need to keep the NOTE's. */
1821 next
= NEXT_INSN (start
);
1822 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
1824 else if (GET_CODE (start
) == CODE_LABEL
&& !can_delete_label_p (start
))
1827 next
= flow_delete_insn (start
);
1829 if (start
== finish
)
1835 /* Delete the insns in a (non-live) block. We physically delete every
1836 non-deleted-note insn, and update the flow graph appropriately.
1838 Return nonzero if we deleted an exception handler. */
1840 /* ??? Preserving all such notes strikes me as wrong. It would be nice
1841 to post-process the stream to remove empty blocks, loops, ranges, etc. */
1847 int deleted_handler
= 0;
1850 /* If the head of this block is a CODE_LABEL, then it might be the
1851 label for an exception handler which can't be reached.
1853 We need to remove the label from the exception_handler_label list
1854 and remove the associated NOTE_INSN_EH_REGION_BEG and
1855 NOTE_INSN_EH_REGION_END notes. */
1859 never_reached_warning (insn
);
1861 if (GET_CODE (insn
) == CODE_LABEL
)
1863 rtx x
, *prev
= &exception_handler_labels
;
1865 for (x
= exception_handler_labels
; x
; x
= XEXP (x
, 1))
1867 if (XEXP (x
, 0) == insn
)
1869 /* Found a match, splice this label out of the EH label list. */
1870 *prev
= XEXP (x
, 1);
1871 XEXP (x
, 1) = NULL_RTX
;
1872 XEXP (x
, 0) = NULL_RTX
;
1874 /* Remove the handler from all regions */
1875 remove_handler (insn
);
1876 deleted_handler
= 1;
1879 prev
= &XEXP (x
, 1);
1882 /* This label may be referenced by code solely for its value, or
1883 referenced by static data, or something. We have determined
1884 that it is not reachable, but cannot delete the label itself.
1885 Save code space and continue to delete the balance of the block,
1886 along with properly updating the cfg. */
1887 if (!can_delete_label_p (insn
))
1889 /* If we've only got one of these, skip the whole deleting
1892 goto no_delete_insns
;
1893 insn
= NEXT_INSN (insn
);
1897 /* Selectively unlink the insn chain. Include any BARRIER that may
1898 follow the basic block. */
1899 end
= next_nonnote_insn (b
->end
);
1900 if (!end
|| GET_CODE (end
) != BARRIER
)
1902 flow_delete_insn_chain (insn
, end
);
1906 /* Remove the edges into and out of this block. Note that there may
1907 indeed be edges in, if we are removing an unreachable loop. */
1911 for (e
= b
->pred
; e
; e
= next
)
1913 for (q
= &e
->src
->succ
; *q
!= e
; q
= &(*q
)->succ_next
)
1916 next
= e
->pred_next
;
1920 for (e
= b
->succ
; e
; e
= next
)
1922 for (q
= &e
->dest
->pred
; *q
!= e
; q
= &(*q
)->pred_next
)
1925 next
= e
->succ_next
;
1934 /* Remove the basic block from the array, and compact behind it. */
1937 return deleted_handler
;
1940 /* Remove block B from the basic block array and compact behind it. */
1946 int i
, n
= n_basic_blocks
;
1948 for (i
= b
->index
; i
+ 1 < n
; ++i
)
1950 basic_block x
= BASIC_BLOCK (i
+ 1);
1951 BASIC_BLOCK (i
) = x
;
1955 basic_block_info
->num_elements
--;
1959 /* Delete INSN by patching it out. Return the next insn. */
1962 flow_delete_insn (insn
)
1965 rtx prev
= PREV_INSN (insn
);
1966 rtx next
= NEXT_INSN (insn
);
1968 PREV_INSN (insn
) = NULL_RTX
;
1969 NEXT_INSN (insn
) = NULL_RTX
;
1972 NEXT_INSN (prev
) = next
;
1974 PREV_INSN (next
) = prev
;
1976 set_last_insn (prev
);
1978 if (GET_CODE (insn
) == CODE_LABEL
)
1979 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
1981 /* If deleting a jump, decrement the use count of the label. Deleting
1982 the label itself should happen in the normal course of block merging. */
1983 if (GET_CODE (insn
) == JUMP_INSN
&& JUMP_LABEL (insn
))
1984 LABEL_NUSES (JUMP_LABEL (insn
))--;
1989 /* True if a given label can be deleted. */
1992 can_delete_label_p (label
)
1997 if (LABEL_PRESERVE_P (label
))
2000 for (x
= forced_labels
; x
; x
= XEXP (x
, 1))
2001 if (label
== XEXP (x
, 0))
2003 for (x
= label_value_list
; x
; x
= XEXP (x
, 1))
2004 if (label
== XEXP (x
, 0))
2006 for (x
= exception_handler_labels
; x
; x
= XEXP (x
, 1))
2007 if (label
== XEXP (x
, 0))
2010 /* User declared labels must be preserved. */
2011 if (LABEL_NAME (label
) != 0)
2017 /* Blocks A and B are to be merged into a single block. A has no incoming
2018 fallthru edge, so it can be moved before B without adding or modifying
2019 any jumps (aside from the jump from A to B). */
2022 merge_blocks_move_predecessor_nojumps (a
, b
)
2025 rtx start
, end
, barrier
;
2031 /* We want to delete the BARRIER after the end of the insns we are
2032 going to move. If we don't find a BARRIER, then do nothing. This
2033 can happen in some cases if we have labels we can not delete.
2035 Similarly, do nothing if we can not delete the label at the start
2036 of the target block. */
2037 barrier
= next_nonnote_insn (end
);
2038 if (GET_CODE (barrier
) != BARRIER
2039 || (GET_CODE (b
->head
) == CODE_LABEL
2040 && ! can_delete_label_p (b
->head
)))
2043 flow_delete_insn (barrier
);
2045 /* Move block and loop notes out of the chain so that we do not
2046 disturb their order.
2048 ??? A better solution would be to squeeze out all the non-nested notes
2049 and adjust the block trees appropriately. Even better would be to have
2050 a tighter connection between block trees and rtl so that this is not
2052 start
= squeeze_notes (start
, end
);
2054 /* Scramble the insn chain. */
2055 if (end
!= PREV_INSN (b
->head
))
2056 reorder_insns (start
, end
, PREV_INSN (b
->head
));
2060 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
2061 a
->index
, b
->index
);
2064 /* Swap the records for the two blocks around. Although we are deleting B,
2065 A is now where B was and we want to compact the BB array from where
2067 BASIC_BLOCK(a
->index
) = b
;
2068 BASIC_BLOCK(b
->index
) = a
;
2070 a
->index
= b
->index
;
2073 /* Now blocks A and B are contiguous. Merge them. */
2074 merge_blocks_nomove (a
, b
);
2079 /* Blocks A and B are to be merged into a single block. B has no outgoing
2080 fallthru edge, so it can be moved after A without adding or modifying
2081 any jumps (aside from the jump from A to B). */
2084 merge_blocks_move_successor_nojumps (a
, b
)
2087 rtx start
, end
, barrier
;
2092 /* We want to delete the BARRIER after the end of the insns we are
2093 going to move. If we don't find a BARRIER, then do nothing. This
2094 can happen in some cases if we have labels we can not delete.
2096 Similarly, do nothing if we can not delete the label at the start
2097 of the target block. */
2098 barrier
= next_nonnote_insn (end
);
2099 if (GET_CODE (barrier
) != BARRIER
2100 || (GET_CODE (b
->head
) == CODE_LABEL
2101 && ! can_delete_label_p (b
->head
)))
2104 flow_delete_insn (barrier
);
2106 /* Move block and loop notes out of the chain so that we do not
2107 disturb their order.
2109 ??? A better solution would be to squeeze out all the non-nested notes
2110 and adjust the block trees appropriately. Even better would be to have
2111 a tighter connection between block trees and rtl so that this is not
2113 start
= squeeze_notes (start
, end
);
2115 /* Scramble the insn chain. */
2116 reorder_insns (start
, end
, a
->end
);
2118 /* Now blocks A and B are contiguous. Merge them. */
2119 merge_blocks_nomove (a
, b
);
2123 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
2124 b
->index
, a
->index
);
2130 /* Blocks A and B are to be merged into a single block. The insns
2131 are already contiguous, hence `nomove'. */
2134 merge_blocks_nomove (a
, b
)
2138 rtx b_head
, b_end
, a_end
;
2141 /* If there was a CODE_LABEL beginning B, delete it. */
2144 if (GET_CODE (b_head
) == CODE_LABEL
)
2146 /* Detect basic blocks with nothing but a label. This can happen
2147 in particular at the end of a function. */
2148 if (b_head
== b_end
)
2150 b_head
= flow_delete_insn (b_head
);
2153 /* Delete the basic block note. */
2154 if (GET_CODE (b_head
) == NOTE
2155 && NOTE_LINE_NUMBER (b_head
) == NOTE_INSN_BASIC_BLOCK
)
2157 if (b_head
== b_end
)
2159 b_head
= flow_delete_insn (b_head
);
2162 /* If there was a jump out of A, delete it. */
2164 if (GET_CODE (a_end
) == JUMP_INSN
)
2168 prev
= prev_nonnote_insn (a_end
);
2173 /* If this was a conditional jump, we need to also delete
2174 the insn that set cc0. */
2176 if (prev
&& sets_cc0_p (prev
))
2179 prev
= prev_nonnote_insn (prev
);
2182 flow_delete_insn (tmp
);
2186 /* Note that a->head != a->end, since we should have at least a
2187 bb note plus the jump, so prev != insn. */
2188 flow_delete_insn (a_end
);
2192 /* By definition, there should only be one successor of A, and that is
2193 B. Free that edge struct. */
2197 /* Adjust the edges out of B for the new owner. */
2198 for (e
= b
->succ
; e
; e
= e
->succ_next
)
2202 /* Reassociate the insns of B with A. */
2205 BLOCK_FOR_INSN (b_head
) = a
;
2206 while (b_head
!= b_end
)
2208 b_head
= NEXT_INSN (b_head
);
2209 BLOCK_FOR_INSN (b_head
) = a
;
2215 /* Compact the basic block array. */
2219 /* Attempt to merge basic blocks that are potentially non-adjacent.
2220 Return true iff the attempt succeeded. */
2223 merge_blocks (e
, b
, c
)
2227 /* If B has a fallthru edge to C, no need to move anything. */
2228 if (e
->flags
& EDGE_FALLTHRU
)
2230 /* If a label still appears somewhere and we cannot delete the label,
2231 then we cannot merge the blocks. The edge was tidied already. */
2233 rtx insn
, stop
= NEXT_INSN (c
->head
);
2234 for (insn
= NEXT_INSN (b
->end
); insn
!= stop
; insn
= NEXT_INSN (insn
))
2235 if (GET_CODE (insn
) == CODE_LABEL
&& !can_delete_label_p (insn
))
2238 merge_blocks_nomove (b
, c
);
2242 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
2243 b
->index
, c
->index
);
2252 int c_has_outgoing_fallthru
;
2253 int b_has_incoming_fallthru
;
2255 /* We must make sure to not munge nesting of exception regions,
2256 lexical blocks, and loop notes.
2258 The first is taken care of by requiring that the active eh
2259 region at the end of one block always matches the active eh
2260 region at the beginning of the next block.
2262 The later two are taken care of by squeezing out all the notes. */
2264 /* ??? A throw/catch edge (or any abnormal edge) should be rarely
2265 executed and we may want to treat blocks which have two out
2266 edges, one normal, one abnormal as only having one edge for
2267 block merging purposes. */
2269 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
2270 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
2272 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
2274 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
2275 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
2277 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
2279 /* If B does not have an incoming fallthru, and the exception regions
2280 match, then it can be moved immediately before C without introducing
2283 C can not be the first block, so we do not have to worry about
2284 accessing a non-existent block. */
2285 d
= BASIC_BLOCK (c
->index
- 1);
2286 if (! b_has_incoming_fallthru
2287 && d
->eh_end
== b
->eh_beg
2288 && b
->eh_end
== c
->eh_beg
)
2289 return merge_blocks_move_predecessor_nojumps (b
, c
);
2291 /* Otherwise, we're going to try to move C after B. Make sure the
2292 exception regions match.
2294 If B is the last basic block, then we must not try to access the
2295 block structure for block B + 1. Luckily in that case we do not
2296 need to worry about matching exception regions. */
2297 d
= (b
->index
+ 1 < n_basic_blocks
? BASIC_BLOCK (b
->index
+ 1) : NULL
);
2298 if (b
->eh_end
== c
->eh_beg
2299 && (d
== NULL
|| c
->eh_end
== d
->eh_beg
))
2301 /* If C does not have an outgoing fallthru, then it can be moved
2302 immediately after B without introducing or modifying jumps. */
2303 if (! c_has_outgoing_fallthru
)
2304 return merge_blocks_move_successor_nojumps (b
, c
);
2306 /* Otherwise, we'll need to insert an extra jump, and possibly
2307 a new block to contain it. */
2308 /* ??? Not implemented yet. */
2315 /* Top level driver for merge_blocks. */
2322 /* Attempt to merge blocks as made possible by edge removal. If a block
2323 has only one successor, and the successor has only one predecessor,
2324 they may be combined. */
2326 for (i
= 0; i
< n_basic_blocks
; )
2328 basic_block c
, b
= BASIC_BLOCK (i
);
2331 /* A loop because chains of blocks might be combineable. */
2332 while ((s
= b
->succ
) != NULL
2333 && s
->succ_next
== NULL
2334 && (s
->flags
& EDGE_EH
) == 0
2335 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2336 && c
->pred
->pred_next
== NULL
2337 /* If the jump insn has side effects, we can't kill the edge. */
2338 && (GET_CODE (b
->end
) != JUMP_INSN
2339 || onlyjump_p (b
->end
))
2340 && merge_blocks (s
, b
, c
))
2343 /* Don't get confused by the index shift caused by deleting blocks. */
2348 /* The given edge should potentially a fallthru edge. If that is in
2349 fact true, delete the unconditional jump and barriers that are in
2353 tidy_fallthru_edge (e
, b
, c
)
2359 /* ??? In a late-running flow pass, other folks may have deleted basic
2360 blocks by nopping out blocks, leaving multiple BARRIERs between here
2361 and the target label. They ought to be chastized and fixed.
2363 We can also wind up with a sequence of undeletable labels between
2364 one block and the next.
2366 So search through a sequence of barriers, labels, and notes for
2367 the head of block C and assert that we really do fall through. */
2369 if (next_real_insn (b
->end
) != next_real_insn (PREV_INSN (c
->head
)))
2372 /* Remove what will soon cease being the jump insn from the source block.
2373 If block B consisted only of this single jump, turn it into a deleted
2376 if (GET_CODE (q
) == JUMP_INSN
)
2379 /* If this was a conditional jump, we need to also delete
2380 the insn that set cc0. */
2381 if (! simplejump_p (q
) && condjump_p (q
) && sets_cc0_p (PREV_INSN (q
)))
2388 NOTE_LINE_NUMBER (q
) = NOTE_INSN_DELETED
;
2389 NOTE_SOURCE_FILE (q
) = 0;
2392 b
->end
= q
= PREV_INSN (q
);
2395 /* Selectively unlink the sequence. */
2396 if (q
!= PREV_INSN (c
->head
))
2397 flow_delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
2399 e
->flags
|= EDGE_FALLTHRU
;
2402 /* Discover and record the loop depth at the head of each basic block. */
2405 calculate_loop_depth (insns
)
2410 int i
= 0, depth
= 1;
2412 bb
= BASIC_BLOCK (i
);
2413 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
2415 if (insn
== bb
->head
)
2417 bb
->loop_depth
= depth
;
2418 if (++i
>= n_basic_blocks
)
2420 bb
= BASIC_BLOCK (i
);
2423 if (GET_CODE (insn
) == NOTE
)
2425 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
2427 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
2430 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error. */
2437 /* Perform data flow analysis.
2438 F is the first insn of the function and NREGS the number of register numbers
2442 life_analysis (f
, nregs
, file
, remove_dead_code
)
2446 int remove_dead_code
;
2448 #ifdef ELIMINABLE_REGS
2450 static struct {int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
2454 /* Record which registers will be eliminated. We use this in
2457 CLEAR_HARD_REG_SET (elim_reg_set
);
2459 #ifdef ELIMINABLE_REGS
2460 for (i
= 0; i
< sizeof eliminables
/ sizeof eliminables
[0]; i
++)
2461 SET_HARD_REG_BIT (elim_reg_set
, eliminables
[i
].from
);
2463 SET_HARD_REG_BIT (elim_reg_set
, FRAME_POINTER_REGNUM
);
2466 /* Allocate a bitmap to be filled in by record_volatile_insns. */
2467 uid_volatile
= BITMAP_XMALLOC ();
2469 /* We want alias analysis information for local dead store elimination. */
2470 init_alias_analysis ();
2473 if (! remove_dead_code
)
2474 flags
&= ~(PROP_SCAN_DEAD_CODE
| PROP_KILL_DEAD_CODE
);
2475 life_analysis_1 (f
, nregs
, flags
);
2477 if (! reload_completed
)
2478 mark_constant_function ();
2480 end_alias_analysis ();
2483 dump_flow_info (file
);
2485 BITMAP_XFREE (uid_volatile
);
2486 free_basic_block_vars (1);
2489 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2490 Search for REGNO. If found, abort if it is not wider than word_mode. */
2493 verify_wide_reg_1 (px
, pregno
)
2498 int regno
= *(int *) pregno
;
2500 if (GET_CODE (x
) == REG
&& REGNO (x
) == regno
)
2502 if (GET_MODE_BITSIZE (GET_MODE (x
)) <= BITS_PER_WORD
)
2509 /* A subroutine of verify_local_live_at_start. Search through insns
2510 between HEAD and END looking for register REGNO. */
2513 verify_wide_reg (regno
, head
, end
)
2519 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i'
2520 && for_each_rtx (&PATTERN (head
), verify_wide_reg_1
, ®no
))
2524 head
= NEXT_INSN (head
);
2527 /* We didn't find the register at all. Something's way screwy. */
2531 /* A subroutine of update_life_info. Verify that there are no untoward
2532 changes in live_at_start during a local update. */
2535 verify_local_live_at_start (new_live_at_start
, bb
)
2536 regset new_live_at_start
;
2539 if (reload_completed
)
2541 /* After reload, there are no pseudos, nor subregs of multi-word
2542 registers. The regsets should exactly match. */
2543 if (! REG_SET_EQUAL_P (new_live_at_start
, bb
->global_live_at_start
))
2550 /* Find the set of changed registers. */
2551 XOR_REG_SET (new_live_at_start
, bb
->global_live_at_start
);
2553 EXECUTE_IF_SET_IN_REG_SET (new_live_at_start
, 0, i
,
2555 /* No registers should die. */
2556 if (REGNO_REG_SET_P (bb
->global_live_at_start
, i
))
2558 /* Verify that the now-live register is wider than word_mode. */
2559 verify_wide_reg (i
, bb
->head
, bb
->end
);
2564 /* Updates death notes starting with the basic blocks set in BLOCKS.
2566 If LOCAL_ONLY, such as after splitting or peepholeing, we are only
2567 expecting local modifications to basic blocks. If we find extra
2568 registers live at the beginning of a block, then we either killed
2569 useful data, or we have a broken split that wants data not provided.
2570 If we find registers removed from live_at_start, that means we have
2571 a broken peephole that is killing a register it shouldn't.
2573 ??? This is not true in one situation -- when a pre-reload splitter
2574 generates subregs of a multi-word pseudo, current life analysis will
2575 lose the kill. So we _can_ have a pseudo go live. How irritating.
2577 BLOCK_FOR_INSN is assumed to be correct.
2579 ??? PROP_FLAGS should not contain PROP_LOG_LINKS. Need to set up
2580 reg_next_use for that. Including PROP_REG_INFO does not refresh
2581 regs_ever_live unless the caller resets it to zero. */
2584 update_life_info (blocks
, extent
, prop_flags
)
2586 enum update_life_extent extent
;
2592 tmp
= ALLOCA_REG_SET ();
2594 /* For a global update, we go through the relaxation process again. */
2595 if (extent
!= UPDATE_LIFE_LOCAL
)
2597 calculate_global_regs_live (blocks
, blocks
,
2598 prop_flags
& PROP_SCAN_DEAD_CODE
);
2600 /* If asked, remove notes from the blocks we'll update. */
2601 if (extent
== UPDATE_LIFE_GLOBAL_RM_NOTES
)
2602 count_or_remove_death_notes (blocks
, 1);
2605 EXECUTE_IF_SET_IN_SBITMAP (blocks
, 0, i
,
2607 basic_block bb
= BASIC_BLOCK (i
);
2609 COPY_REG_SET (tmp
, bb
->global_live_at_end
);
2610 propagate_block (tmp
, bb
->head
, bb
->end
, (regset
) NULL
, i
,
2613 if (extent
== UPDATE_LIFE_LOCAL
)
2614 verify_local_live_at_start (tmp
, bb
);
2620 /* Free the variables allocated by find_basic_blocks.
2622 KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed. */
2625 free_basic_block_vars (keep_head_end_p
)
2626 int keep_head_end_p
;
2628 if (basic_block_for_insn
)
2630 VARRAY_FREE (basic_block_for_insn
);
2631 basic_block_for_insn
= NULL
;
2634 if (! keep_head_end_p
)
2637 VARRAY_FREE (basic_block_info
);
2640 ENTRY_BLOCK_PTR
->aux
= NULL
;
2641 ENTRY_BLOCK_PTR
->global_live_at_end
= NULL
;
2642 EXIT_BLOCK_PTR
->aux
= NULL
;
2643 EXIT_BLOCK_PTR
->global_live_at_start
= NULL
;
2647 /* Return nonzero if the destination of SET equals the source. */
2652 rtx src
= SET_SRC (set
);
2653 rtx dst
= SET_DEST (set
);
2654 if (GET_CODE (src
) == REG
&& GET_CODE (dst
) == REG
2655 && REGNO (src
) == REGNO (dst
))
2657 if (GET_CODE (src
) != SUBREG
|| GET_CODE (dst
) != SUBREG
2658 || SUBREG_WORD (src
) != SUBREG_WORD (dst
))
2660 src
= SUBREG_REG (src
);
2661 dst
= SUBREG_REG (dst
);
2662 if (GET_CODE (src
) == REG
&& GET_CODE (dst
) == REG
2663 && REGNO (src
) == REGNO (dst
))
2668 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2674 rtx pat
= PATTERN (insn
);
2676 /* Insns carrying these notes are useful later on. */
2677 if (find_reg_note (insn
, REG_EQUAL
, NULL_RTX
))
2680 if (GET_CODE (pat
) == SET
&& set_noop_p (pat
))
2683 if (GET_CODE (pat
) == PARALLEL
)
2686 /* If nothing but SETs of registers to themselves,
2687 this insn can also be deleted. */
2688 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
2690 rtx tem
= XVECEXP (pat
, 0, i
);
2692 if (GET_CODE (tem
) == USE
2693 || GET_CODE (tem
) == CLOBBER
)
2696 if (GET_CODE (tem
) != SET
|| ! set_noop_p (tem
))
2706 notice_stack_pointer_modification (x
, pat
, data
)
2708 rtx pat ATTRIBUTE_UNUSED
;
2709 void *data ATTRIBUTE_UNUSED
;
2711 if (x
== stack_pointer_rtx
2712 /* The stack pointer is only modified indirectly as the result
2713 of a push until later in flow. See the comments in rtl.texi
2714 regarding Embedded Side-Effects on Addresses. */
2715 || (GET_CODE (x
) == MEM
2716 && (GET_CODE (XEXP (x
, 0)) == PRE_DEC
2717 || GET_CODE (XEXP (x
, 0)) == PRE_INC
2718 || GET_CODE (XEXP (x
, 0)) == POST_DEC
2719 || GET_CODE (XEXP (x
, 0)) == POST_INC
)
2720 && XEXP (XEXP (x
, 0), 0) == stack_pointer_rtx
))
2721 current_function_sp_is_unchanging
= 0;
2724 /* Record which insns refer to any volatile memory
2725 or for any reason can't be deleted just because they are dead stores.
2726 Also, delete any insns that copy a register to itself.
2727 And see if the stack pointer is modified. */
2729 record_volatile_insns (f
)
2733 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
2735 enum rtx_code code1
= GET_CODE (insn
);
2736 if (code1
== CALL_INSN
)
2737 SET_INSN_VOLATILE (insn
);
2738 else if (code1
== INSN
|| code1
== JUMP_INSN
)
2740 if (GET_CODE (PATTERN (insn
)) != USE
2741 && volatile_refs_p (PATTERN (insn
)))
2742 SET_INSN_VOLATILE (insn
);
2744 /* A SET that makes space on the stack cannot be dead.
2745 (Such SETs occur only for allocating variable-size data,
2746 so they will always have a PLUS or MINUS according to the
2747 direction of stack growth.)
2748 Even if this function never uses this stack pointer value,
2749 signal handlers do! */
2750 else if (code1
== INSN
&& GET_CODE (PATTERN (insn
)) == SET
2751 && SET_DEST (PATTERN (insn
)) == stack_pointer_rtx
2752 #ifdef STACK_GROWS_DOWNWARD
2753 && GET_CODE (SET_SRC (PATTERN (insn
))) == MINUS
2755 && GET_CODE (SET_SRC (PATTERN (insn
))) == PLUS
2757 && XEXP (SET_SRC (PATTERN (insn
)), 0) == stack_pointer_rtx
)
2758 SET_INSN_VOLATILE (insn
);
2760 /* Delete (in effect) any obvious no-op moves. */
2761 else if (noop_move_p (insn
))
2763 PUT_CODE (insn
, NOTE
);
2764 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
2765 NOTE_SOURCE_FILE (insn
) = 0;
2769 /* Check if insn modifies the stack pointer. */
2770 if ( current_function_sp_is_unchanging
2771 && GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
2772 note_stores (PATTERN (insn
),
2773 notice_stack_pointer_modification
,
2778 /* Mark a register in SET. Hard registers in large modes get all
2779 of their component registers set as well. */
2785 int regno
= REGNO (reg
);
2787 SET_REGNO_REG_SET (set
, regno
);
2788 if (regno
< FIRST_PSEUDO_REGISTER
)
2790 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2792 SET_REGNO_REG_SET (set
, regno
+ n
);
2796 /* Mark those regs which are needed at the end of the function as live
2797 at the end of the last basic block. */
2799 mark_regs_live_at_end (set
)
2805 /* If exiting needs the right stack value, consider the stack pointer
2806 live at the end of the function. */
2807 if ((HAVE_epilogue
&& reload_completed
)
2808 || ! EXIT_IGNORE_STACK
2809 || (! FRAME_POINTER_REQUIRED
2810 && ! current_function_calls_alloca
2811 && flag_omit_frame_pointer
)
2812 || current_function_sp_is_unchanging
)
2814 SET_REGNO_REG_SET (set
, STACK_POINTER_REGNUM
);
2817 /* Mark the frame pointer if needed at the end of the function. If
2818 we end up eliminating it, it will be removed from the live list
2819 of each basic block by reload. */
2821 if (! reload_completed
|| frame_pointer_needed
)
2823 SET_REGNO_REG_SET (set
, FRAME_POINTER_REGNUM
);
2824 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2825 /* If they are different, also mark the hard frame pointer as live */
2826 SET_REGNO_REG_SET (set
, HARD_FRAME_POINTER_REGNUM
);
2830 #ifdef PIC_OFFSET_TABLE_REGNUM
2831 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
2832 /* Many architectures have a GP register even without flag_pic.
2833 Assume the pic register is not in use, or will be handled by
2834 other means, if it is not fixed. */
2835 if (fixed_regs
[PIC_OFFSET_TABLE_REGNUM
])
2836 SET_REGNO_REG_SET (set
, PIC_OFFSET_TABLE_REGNUM
);
2840 /* Mark all global registers, and all registers used by the epilogue
2841 as being live at the end of the function since they may be
2842 referenced by our caller. */
2843 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2845 #ifdef EPILOGUE_USES
2846 || EPILOGUE_USES (i
)
2849 SET_REGNO_REG_SET (set
, i
);
2851 /* Mark all call-saved registers that we actaully used. */
2852 if (HAVE_epilogue
&& reload_completed
)
2854 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2855 if (! call_used_regs
[i
] && regs_ever_live
[i
])
2856 SET_REGNO_REG_SET (set
, i
);
2859 /* Mark function return value. */
2860 /* ??? Only do this after reload. Consider a non-void function that
2861 omits a return statement. Across that edge we'll have the return
2862 register live, and no set for it. Thus the return register will
2863 be live back through the CFG to the entry, and thus we die. A
2864 possible solution is to emit a clobber at exits without returns. */
2866 type
= TREE_TYPE (DECL_RESULT (current_function_decl
));
2867 if (reload_completed
2868 && type
!= void_type_node
)
2872 if (current_function_returns_struct
2873 || current_function_returns_pcc_struct
)
2874 type
= build_pointer_type (type
);
2876 #ifdef FUNCTION_OUTGOING_VALUE
2877 outgoing
= FUNCTION_OUTGOING_VALUE (type
, current_function_decl
);
2879 outgoing
= FUNCTION_VALUE (type
, current_function_decl
);
2882 if (GET_CODE (outgoing
) == REG
)
2883 mark_reg (set
, outgoing
);
2884 else if (GET_CODE (outgoing
) == PARALLEL
)
2886 int len
= XVECLEN (outgoing
, 0);
2888 /* Check for a NULL entry, used to indicate that the parameter
2889 goes on the stack and in registers. */
2890 i
= (XEXP (XVECEXP (outgoing
, 0, 0), 0) ? 0 : 1);
2892 for ( ; i
< len
; ++i
)
2894 rtx r
= XVECEXP (outgoing
, 0, i
);
2895 if (GET_CODE (r
) == REG
)
2904 /* Determine which registers are live at the start of each
2905 basic block of the function whose first insn is F.
2906 NREGS is the number of registers used in F.
2907 We allocate the vector basic_block_live_at_start
2908 and the regsets that it points to, and fill them with the data.
2909 regset_size and regset_bytes are also set here. */
2912 life_analysis_1 (f
, nregs
, flags
)
2917 char save_regs_ever_live
[FIRST_PSEUDO_REGISTER
];
2922 /* Allocate and zero out many data structures
2923 that will record the data from lifetime analysis. */
2925 allocate_reg_life_data ();
2926 allocate_bb_life_data ();
2928 reg_next_use
= (rtx
*) xcalloc (nregs
, sizeof (rtx
));
2930 /* Assume that the stack pointer is unchanging if alloca hasn't been used.
2931 This will be cleared by record_volatile_insns if it encounters an insn
2932 which modifies the stack pointer. */
2933 current_function_sp_is_unchanging
= !current_function_calls_alloca
;
2934 record_volatile_insns (f
);
2936 /* Find the set of registers live on function exit. Do this before
2937 zeroing regs_ever_live, as we use that data post-reload. */
2938 mark_regs_live_at_end (EXIT_BLOCK_PTR
->global_live_at_start
);
2940 /* The post-reload life analysis have (on a global basis) the same
2941 registers live as was computed by reload itself. elimination
2942 Otherwise offsets and such may be incorrect.
2944 Reload will make some registers as live even though they do not
2945 appear in the rtl. */
2946 if (reload_completed
)
2947 memcpy (save_regs_ever_live
, regs_ever_live
, sizeof (regs_ever_live
));
2948 memset (regs_ever_live
, 0, sizeof regs_ever_live
);
2950 /* Compute register life at block boundaries. It'd be nice to
2951 begin with just the exit and noreturn blocks, but that set
2952 is not immediately handy. */
2955 blocks
= sbitmap_alloc (n_basic_blocks
);
2956 sbitmap_ones (blocks
);
2957 calculate_global_regs_live (blocks
, blocks
, flags
& PROP_SCAN_DEAD_CODE
);
2958 sbitmap_free (blocks
);
2961 /* The only pseudos that are live at the beginning of the function are
2962 those that were not set anywhere in the function. local-alloc doesn't
2963 know how to handle these correctly, so mark them as not local to any
2966 EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR
->global_live_at_end
,
2967 FIRST_PSEUDO_REGISTER
, i
,
2968 { REG_BASIC_BLOCK (i
) = REG_BLOCK_GLOBAL
; });
2970 /* Now the life information is accurate. Make one more pass over each
2971 basic block to delete dead stores, create autoincrement addressing
2972 and record how many times each register is used, is set, or dies. */
2975 tmp
= ALLOCA_REG_SET ();
2977 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
2979 basic_block bb
= BASIC_BLOCK (i
);
2981 COPY_REG_SET (tmp
, bb
->global_live_at_end
);
2982 propagate_block (tmp
, bb
->head
, bb
->end
, (regset
) NULL
, i
, flags
);
2988 /* We have a problem with any pseudoreg that lives across the setjmp.
2989 ANSI says that if a user variable does not change in value between
2990 the setjmp and the longjmp, then the longjmp preserves it. This
2991 includes longjmp from a place where the pseudo appears dead.
2992 (In principle, the value still exists if it is in scope.)
2993 If the pseudo goes in a hard reg, some other value may occupy
2994 that hard reg where this pseudo is dead, thus clobbering the pseudo.
2995 Conclusion: such a pseudo must not go in a hard reg. */
2996 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp
,
2997 FIRST_PSEUDO_REGISTER
, i
,
2999 if (regno_reg_rtx
[i
] != 0)
3001 REG_LIVE_LENGTH (i
) = -1;
3002 REG_BASIC_BLOCK (i
) = REG_BLOCK_UNKNOWN
;
3006 /* Restore regs_ever_live that was provided by reload. */
3007 if (reload_completed
)
3008 memcpy (regs_ever_live
, save_regs_ever_live
, sizeof (regs_ever_live
));
3011 free (reg_next_use
);
3012 reg_next_use
= NULL
;
3015 /* Propagate global life info around the graph of basic blocks. Begin
3016 considering blocks with their corresponding bit set in BLOCKS_IN.
3017 BLOCKS_OUT is set for every block that was changed. */
3020 calculate_global_regs_live (blocks_in
, blocks_out
, flags
)
3021 sbitmap blocks_in
, blocks_out
;
3024 basic_block
*queue
, *qhead
, *qtail
, *qend
;
3025 regset tmp
, new_live_at_end
;
3028 tmp
= ALLOCA_REG_SET ();
3029 new_live_at_end
= ALLOCA_REG_SET ();
3031 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
3032 because the `head == tail' style test for an empty queue doesn't
3033 work with a full queue. */
3034 queue
= (basic_block
*) xmalloc ((n_basic_blocks
+ 2) * sizeof (*queue
));
3036 qhead
= qend
= queue
+ n_basic_blocks
+ 2;
3038 /* Clear out the garbage that might be hanging out in bb->aux. */
3039 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
3040 BASIC_BLOCK (i
)->aux
= NULL
;
3042 /* Queue the blocks set in the initial mask. Do this in reverse block
3043 number order so that we are more likely for the first round to do
3044 useful work. We use AUX non-null to flag that the block is queued. */
3045 EXECUTE_IF_SET_IN_SBITMAP (blocks_in
, 0, i
,
3047 basic_block bb
= BASIC_BLOCK (i
);
3052 sbitmap_zero (blocks_out
);
3054 while (qhead
!= qtail
)
3056 int rescan
, changed
;
3065 /* Begin by propogating live_at_start from the successor blocks. */
3066 CLEAR_REG_SET (new_live_at_end
);
3067 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3069 basic_block sb
= e
->dest
;
3070 IOR_REG_SET (new_live_at_end
, sb
->global_live_at_start
);
3073 if (bb
== ENTRY_BLOCK_PTR
)
3075 COPY_REG_SET (bb
->global_live_at_end
, new_live_at_end
);
3079 /* On our first pass through this block, we'll go ahead and continue.
3080 Recognize first pass by local_set NULL. On subsequent passes, we
3081 get to skip out early if live_at_end wouldn't have changed. */
3083 if (bb
->local_set
== NULL
)
3085 bb
->local_set
= OBSTACK_ALLOC_REG_SET (function_obstack
);
3090 /* If any bits were removed from live_at_end, we'll have to
3091 rescan the block. This wouldn't be necessary if we had
3092 precalculated local_live, however with PROP_SCAN_DEAD_CODE
3093 local_live is really dependant on live_at_end. */
3094 CLEAR_REG_SET (tmp
);
3095 rescan
= bitmap_operation (tmp
, bb
->global_live_at_end
,
3096 new_live_at_end
, BITMAP_AND_COMPL
);
3100 /* Find the set of changed bits. Take this opportunity
3101 to notice that this set is empty and early out. */
3102 CLEAR_REG_SET (tmp
);
3103 changed
= bitmap_operation (tmp
, bb
->global_live_at_end
,
3104 new_live_at_end
, BITMAP_XOR
);
3108 /* If any of the changed bits overlap with local_set,
3109 we'll have to rescan the block. Detect overlap by
3110 the AND with ~local_set turning off bits. */
3111 rescan
= bitmap_operation (tmp
, tmp
, bb
->local_set
,
3116 /* Let our caller know that BB changed enough to require its
3117 death notes updated. */
3118 SET_BIT (blocks_out
, bb
->index
);
3122 /* Add to live_at_start the set of all registers in
3123 new_live_at_end that aren't in the old live_at_end. */
3125 bitmap_operation (tmp
, new_live_at_end
, bb
->global_live_at_end
,
3127 COPY_REG_SET (bb
->global_live_at_end
, new_live_at_end
);
3129 changed
= bitmap_operation (bb
->global_live_at_start
,
3130 bb
->global_live_at_start
,
3137 COPY_REG_SET (bb
->global_live_at_end
, new_live_at_end
);
3139 /* Rescan the block insn by insn to turn (a copy of) live_at_end
3140 into live_at_start. */
3141 propagate_block (new_live_at_end
, bb
->head
, bb
->end
,
3142 bb
->local_set
, bb
->index
, flags
);
3144 /* If live_at start didn't change, no need to go farther. */
3145 if (REG_SET_EQUAL_P (bb
->global_live_at_start
, new_live_at_end
))
3148 COPY_REG_SET (bb
->global_live_at_start
, new_live_at_end
);
3151 /* Queue all predecessors of BB so that we may re-examine
3152 their live_at_end. */
3153 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
3155 basic_block pb
= e
->src
;
3156 if (pb
->aux
== NULL
)
3167 FREE_REG_SET (new_live_at_end
);
3169 EXECUTE_IF_SET_IN_SBITMAP (blocks_out
, 0, i
,
3171 basic_block bb
= BASIC_BLOCK (i
);
3172 FREE_REG_SET (bb
->local_set
);
3178 /* Subroutines of life analysis. */
3180 /* Allocate the permanent data structures that represent the results
3181 of life analysis. Not static since used also for stupid life analysis. */
3184 allocate_bb_life_data ()
3188 for (i
= 0; i
< n_basic_blocks
; i
++)
3190 basic_block bb
= BASIC_BLOCK (i
);
3192 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (function_obstack
);
3193 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (function_obstack
);
3196 ENTRY_BLOCK_PTR
->global_live_at_end
3197 = OBSTACK_ALLOC_REG_SET (function_obstack
);
3198 EXIT_BLOCK_PTR
->global_live_at_start
3199 = OBSTACK_ALLOC_REG_SET (function_obstack
);
3201 regs_live_at_setjmp
= OBSTACK_ALLOC_REG_SET (function_obstack
);
3205 allocate_reg_life_data ()
3209 /* Recalculate the register space, in case it has grown. Old style
3210 vector oriented regsets would set regset_{size,bytes} here also. */
3211 allocate_reg_info (max_regno
, FALSE
, FALSE
);
3213 /* Reset all the data we'll collect in propagate_block and its
3215 for (i
= 0; i
< max_regno
; i
++)
3219 REG_N_DEATHS (i
) = 0;
3220 REG_N_CALLS_CROSSED (i
) = 0;
3221 REG_LIVE_LENGTH (i
) = 0;
3222 REG_BASIC_BLOCK (i
) = REG_BLOCK_UNKNOWN
;
3226 /* Compute the registers live at the beginning of a basic block
3227 from those live at the end.
3229 When called, OLD contains those live at the end.
3230 On return, it contains those live at the beginning.
3231 FIRST and LAST are the first and last insns of the basic block.
3233 FINAL is nonzero if we are doing the final pass which is not
3234 for computing the life info (since that has already been done)
3235 but for acting on it. On this pass, we delete dead stores,
3236 set up the logical links and dead-variables lists of instructions,
3237 and merge instructions for autoincrement and autodecrement addresses.
3239 SIGNIFICANT is nonzero only the first time for each basic block.
3240 If it is nonzero, it points to a regset in which we store
3241 a 1 for each register that is set within the block.
3243 BNUM is the number of the basic block. */
3246 propagate_block (old
, first
, last
, significant
, bnum
, flags
)
3247 register regset old
;
3259 /* Find the loop depth for this block. Ignore loop level changes in the
3260 middle of the basic block -- for register allocation purposes, the
3261 important uses will be in the blocks wholely contained within the loop
3262 not in the loop pre-header or post-trailer. */
3263 loop_depth
= BASIC_BLOCK (bnum
)->loop_depth
;
3265 dead
= ALLOCA_REG_SET ();
3266 live
= ALLOCA_REG_SET ();
3270 if (flags
& PROP_REG_INFO
)
3274 /* Process the regs live at the end of the block.
3275 Mark them as not local to any one basic block. */
3276 EXECUTE_IF_SET_IN_REG_SET (old
, 0, i
,
3278 REG_BASIC_BLOCK (i
) = REG_BLOCK_GLOBAL
;
3282 /* Scan the block an insn at a time from end to beginning. */
3284 for (insn
= last
; ; insn
= prev
)
3286 prev
= PREV_INSN (insn
);
3288 if (GET_CODE (insn
) == NOTE
)
3290 /* If this is a call to `setjmp' et al,
3291 warn if any non-volatile datum is live. */
3293 if ((flags
& PROP_REG_INFO
)
3294 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
)
3295 IOR_REG_SET (regs_live_at_setjmp
, old
);
3298 /* Update the life-status of regs for this insn.
3299 First DEAD gets which regs are set in this insn
3300 then LIVE gets which regs are used in this insn.
3301 Then the regs live before the insn
3302 are those live after, with DEAD regs turned off,
3303 and then LIVE regs turned on. */
3305 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
3308 rtx note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
3309 int insn_is_dead
= 0;
3310 int libcall_is_dead
= 0;
3312 if (flags
& PROP_SCAN_DEAD_CODE
)
3314 insn_is_dead
= (insn_dead_p (PATTERN (insn
), old
, 0, REG_NOTES (insn
))
3315 /* Don't delete something that refers to volatile storage! */
3316 && ! INSN_VOLATILE (insn
));
3317 libcall_is_dead
= (insn_is_dead
&& note
!= 0
3318 && libcall_dead_p (PATTERN (insn
), old
, note
, insn
));
3321 /* We almost certainly don't want to delete prologue or epilogue
3322 instructions. Warn about probable compiler losage. */
3323 if ((flags
& PROP_KILL_DEAD_CODE
)
3326 && (HAVE_epilogue
|| HAVE_prologue
)
3327 && prologue_epilogue_contains (insn
))
3329 warning ("ICE: would have deleted prologue/epilogue insn");
3331 libcall_is_dead
= insn_is_dead
= 0;
3334 /* If an instruction consists of just dead store(s) on final pass,
3335 "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
3336 We could really delete it with delete_insn, but that
3337 can cause trouble for first or last insn in a basic block. */
3338 if ((flags
& PROP_KILL_DEAD_CODE
) && insn_is_dead
)
3341 /* If the insn referred to a label, note that the label is
3343 for (inote
= REG_NOTES (insn
); inote
; inote
= XEXP (inote
, 1))
3345 if (REG_NOTE_KIND (inote
) == REG_LABEL
)
3347 rtx label
= XEXP (inote
, 0);
3349 LABEL_NUSES (label
)--;
3351 /* If this label was attached to an ADDR_VEC, it's
3352 safe to delete the ADDR_VEC. In fact, it's pretty much
3353 mandatory to delete it, because the ADDR_VEC may
3354 be referencing labels that no longer exist. */
3355 if (LABEL_NUSES (label
) == 0
3356 && (next
= next_nonnote_insn (label
)) != NULL
3357 && GET_CODE (next
) == JUMP_INSN
3358 && (GET_CODE (PATTERN (next
)) == ADDR_VEC
3359 || GET_CODE (PATTERN (next
)) == ADDR_DIFF_VEC
))
3361 rtx pat
= PATTERN (next
);
3362 int diff_vec_p
= GET_CODE (pat
) == ADDR_DIFF_VEC
;
3363 int len
= XVECLEN (pat
, diff_vec_p
);
3365 for (i
= 0; i
< len
; i
++)
3366 LABEL_NUSES (XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0))--;
3367 PUT_CODE (next
, NOTE
);
3368 NOTE_LINE_NUMBER (next
) = NOTE_INSN_DELETED
;
3369 NOTE_SOURCE_FILE (next
) = 0;
3374 PUT_CODE (insn
, NOTE
);
3375 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
3376 NOTE_SOURCE_FILE (insn
) = 0;
3378 /* CC0 is now known to be dead. Either this insn used it,
3379 in which case it doesn't anymore, or clobbered it,
3380 so the next insn can't use it. */
3383 /* If this insn is copying the return value from a library call,
3384 delete the entire library call. */
3385 if (libcall_is_dead
)
3387 rtx first
= XEXP (note
, 0);
3389 while (INSN_DELETED_P (first
))
3390 first
= NEXT_INSN (first
);
3395 NOTE_LINE_NUMBER (p
) = NOTE_INSN_DELETED
;
3396 NOTE_SOURCE_FILE (p
) = 0;
3402 CLEAR_REG_SET (dead
);
3403 CLEAR_REG_SET (live
);
3405 /* See if this is an increment or decrement that can be
3406 merged into a following memory address. */
3409 register rtx x
= single_set (insn
);
3411 /* Does this instruction increment or decrement a register? */
3412 if (!reload_completed
3413 && (flags
& PROP_AUTOINC
)
3415 && GET_CODE (SET_DEST (x
)) == REG
3416 && (GET_CODE (SET_SRC (x
)) == PLUS
3417 || GET_CODE (SET_SRC (x
)) == MINUS
)
3418 && XEXP (SET_SRC (x
), 0) == SET_DEST (x
)
3419 && GET_CODE (XEXP (SET_SRC (x
), 1)) == CONST_INT
3420 /* Ok, look for a following memory ref we can combine with.
3421 If one is found, change the memory ref to a PRE_INC
3422 or PRE_DEC, cancel this insn, and return 1.
3423 Return 0 if nothing has been done. */
3424 && try_pre_increment_1 (insn
))
3427 #endif /* AUTO_INC_DEC */
3429 /* If this is not the final pass, and this insn is copying the
3430 value of a library call and it's dead, don't scan the
3431 insns that perform the library call, so that the call's
3432 arguments are not marked live. */
3433 if (libcall_is_dead
)
3435 /* Mark the dest reg as `significant'. */
3436 mark_set_regs (old
, dead
, PATTERN (insn
), NULL_RTX
,
3437 significant
, flags
);
3439 insn
= XEXP (note
, 0);
3440 prev
= PREV_INSN (insn
);
3442 else if (GET_CODE (PATTERN (insn
)) == SET
3443 && SET_DEST (PATTERN (insn
)) == stack_pointer_rtx
3444 && GET_CODE (SET_SRC (PATTERN (insn
))) == PLUS
3445 && XEXP (SET_SRC (PATTERN (insn
)), 0) == stack_pointer_rtx
3446 && GET_CODE (XEXP (SET_SRC (PATTERN (insn
)), 1)) == CONST_INT
)
3447 /* We have an insn to pop a constant amount off the stack.
3448 (Such insns use PLUS regardless of the direction of the stack,
3449 and any insn to adjust the stack by a constant is always a pop.)
3450 These insns, if not dead stores, have no effect on life. */
3454 /* Any regs live at the time of a call instruction
3455 must not go in a register clobbered by calls.
3456 Find all regs now live and record this for them. */
3458 if (GET_CODE (insn
) == CALL_INSN
3459 && (flags
& PROP_REG_INFO
))
3460 EXECUTE_IF_SET_IN_REG_SET (old
, 0, i
,
3462 REG_N_CALLS_CROSSED (i
)++;
3465 /* LIVE gets the regs used in INSN;
3466 DEAD gets those set by it. Dead insns don't make anything
3469 mark_set_regs (old
, dead
, PATTERN (insn
),
3470 insn
, significant
, flags
);
3472 /* If an insn doesn't use CC0, it becomes dead since we
3473 assume that every insn clobbers it. So show it dead here;
3474 mark_used_regs will set it live if it is referenced. */
3478 mark_used_regs (old
, live
, PATTERN (insn
), flags
, insn
);
3480 /* Sometimes we may have inserted something before INSN (such as
3481 a move) when we make an auto-inc. So ensure we will scan
3484 prev
= PREV_INSN (insn
);
3487 if (! insn_is_dead
&& GET_CODE (insn
) == CALL_INSN
)
3493 for (note
= CALL_INSN_FUNCTION_USAGE (insn
);
3495 note
= XEXP (note
, 1))
3496 if (GET_CODE (XEXP (note
, 0)) == USE
)
3497 mark_used_regs (old
, live
, XEXP (XEXP (note
, 0), 0),
3500 /* Each call clobbers all call-clobbered regs that are not
3501 global or fixed. Note that the function-value reg is a
3502 call-clobbered reg, and mark_set_regs has already had
3503 a chance to handle it. */
3505 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3506 if (call_used_regs
[i
] && ! global_regs
[i
]
3509 SET_REGNO_REG_SET (dead
, i
);
3511 SET_REGNO_REG_SET (significant
, i
);
3514 /* The stack ptr is used (honorarily) by a CALL insn. */
3515 SET_REGNO_REG_SET (live
, STACK_POINTER_REGNUM
);
3517 /* Calls may also reference any of the global registers,
3518 so they are made live. */
3519 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3521 mark_used_regs (old
, live
,
3522 gen_rtx_REG (reg_raw_mode
[i
], i
),
3525 /* Calls also clobber memory. */
3526 free_EXPR_LIST_list (&mem_set_list
);
3529 /* Update OLD for the registers used or set. */
3530 AND_COMPL_REG_SET (old
, dead
);
3531 IOR_REG_SET (old
, live
);
3535 /* On final pass, update counts of how many insns each reg is live
3537 if (flags
& PROP_REG_INFO
)
3538 EXECUTE_IF_SET_IN_REG_SET (old
, 0, i
,
3539 { REG_LIVE_LENGTH (i
)++; });
3546 FREE_REG_SET (dead
);
3547 FREE_REG_SET (live
);
3548 free_EXPR_LIST_list (&mem_set_list
);
3551 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3552 (SET expressions whose destinations are registers dead after the insn).
3553 NEEDED is the regset that says which regs are alive after the insn.
3555 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3557 If X is the entire body of an insn, NOTES contains the reg notes
3558 pertaining to the insn. */
3561 insn_dead_p (x
, needed
, call_ok
, notes
)
3565 rtx notes ATTRIBUTE_UNUSED
;
3567 enum rtx_code code
= GET_CODE (x
);
3570 /* If flow is invoked after reload, we must take existing AUTO_INC
3571 expresions into account. */
3572 if (reload_completed
)
3574 for ( ; notes
; notes
= XEXP (notes
, 1))
3576 if (REG_NOTE_KIND (notes
) == REG_INC
)
3578 int regno
= REGNO (XEXP (notes
, 0));
3580 /* Don't delete insns to set global regs. */
3581 if ((regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
3582 || REGNO_REG_SET_P (needed
, regno
))
3589 /* If setting something that's a reg or part of one,
3590 see if that register's altered value will be live. */
3594 rtx r
= SET_DEST (x
);
3596 /* A SET that is a subroutine call cannot be dead. */
3597 if (! call_ok
&& GET_CODE (SET_SRC (x
)) == CALL
)
3601 if (GET_CODE (r
) == CC0
)
3605 if (GET_CODE (r
) == MEM
&& ! MEM_VOLATILE_P (r
))
3608 /* Walk the set of memory locations we are currently tracking
3609 and see if one is an identical match to this memory location.
3610 If so, this memory write is dead (remember, we're walking
3611 backwards from the end of the block to the start. */
3612 temp
= mem_set_list
;
3615 if (rtx_equal_p (XEXP (temp
, 0), r
))
3617 temp
= XEXP (temp
, 1);
3621 while (GET_CODE (r
) == SUBREG
|| GET_CODE (r
) == STRICT_LOW_PART
3622 || GET_CODE (r
) == ZERO_EXTRACT
)
3625 if (GET_CODE (r
) == REG
)
3627 int regno
= REGNO (r
);
3629 /* Don't delete insns to set global regs. */
3630 if ((regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
3631 /* Make sure insns to set frame pointer aren't deleted. */
3632 || (regno
== FRAME_POINTER_REGNUM
3633 && (! reload_completed
|| frame_pointer_needed
))
3634 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3635 || (regno
== HARD_FRAME_POINTER_REGNUM
3636 && (! reload_completed
|| frame_pointer_needed
))
3638 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3639 /* Make sure insns to set arg pointer are never deleted
3640 (if the arg pointer isn't fixed, there will be a USE for
3641 it, so we can treat it normally). */
3642 || (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
3644 || REGNO_REG_SET_P (needed
, regno
))
3647 /* If this is a hard register, verify that subsequent words are
3649 if (regno
< FIRST_PSEUDO_REGISTER
)
3651 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (r
));
3654 if (REGNO_REG_SET_P (needed
, regno
+n
))
3662 /* If performing several activities,
3663 insn is dead if each activity is individually dead.
3664 Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
3665 that's inside a PARALLEL doesn't make the insn worth keeping. */
3666 else if (code
== PARALLEL
)
3668 int i
= XVECLEN (x
, 0);
3670 for (i
--; i
>= 0; i
--)
3671 if (GET_CODE (XVECEXP (x
, 0, i
)) != CLOBBER
3672 && GET_CODE (XVECEXP (x
, 0, i
)) != USE
3673 && ! insn_dead_p (XVECEXP (x
, 0, i
), needed
, call_ok
, NULL_RTX
))
3679 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
3680 is not necessarily true for hard registers. */
3681 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == REG
3682 && REGNO (XEXP (x
, 0)) >= FIRST_PSEUDO_REGISTER
3683 && ! REGNO_REG_SET_P (needed
, REGNO (XEXP (x
, 0))))
3686 /* We do not check other CLOBBER or USE here. An insn consisting of just
3687 a CLOBBER or just a USE should not be deleted. */
3691 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
3692 return 1 if the entire library call is dead.
3693 This is true if X copies a register (hard or pseudo)
3694 and if the hard return reg of the call insn is dead.
3695 (The caller should have tested the destination of X already for death.)
3697 If this insn doesn't just copy a register, then we don't
3698 have an ordinary libcall. In that case, cse could not have
3699 managed to substitute the source for the dest later on,
3700 so we can assume the libcall is dead.
3702 NEEDED is the bit vector of pseudoregs live before this insn.
3703 NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
3706 libcall_dead_p (x
, needed
, note
, insn
)
3712 register RTX_CODE code
= GET_CODE (x
);
3716 register rtx r
= SET_SRC (x
);
3717 if (GET_CODE (r
) == REG
)
3719 rtx call
= XEXP (note
, 0);
3723 /* Find the call insn. */
3724 while (call
!= insn
&& GET_CODE (call
) != CALL_INSN
)
3725 call
= NEXT_INSN (call
);
3727 /* If there is none, do nothing special,
3728 since ordinary death handling can understand these insns. */
3732 /* See if the hard reg holding the value is dead.
3733 If this is a PARALLEL, find the call within it. */
3734 call_pat
= PATTERN (call
);
3735 if (GET_CODE (call_pat
) == PARALLEL
)
3737 for (i
= XVECLEN (call_pat
, 0) - 1; i
>= 0; i
--)
3738 if (GET_CODE (XVECEXP (call_pat
, 0, i
)) == SET
3739 && GET_CODE (SET_SRC (XVECEXP (call_pat
, 0, i
))) == CALL
)
3742 /* This may be a library call that is returning a value
3743 via invisible pointer. Do nothing special, since
3744 ordinary death handling can understand these insns. */
3748 call_pat
= XVECEXP (call_pat
, 0, i
);
3751 return insn_dead_p (call_pat
, needed
, 1, REG_NOTES (call
));
3757 /* Return 1 if register REGNO was used before it was set, i.e. if it is
3758 live at function entry. Don't count global register variables, variables
3759 in registers that can be used for function arg passing, or variables in
3760 fixed hard registers. */
3763 regno_uninitialized (regno
)
3766 if (n_basic_blocks
== 0
3767 || (regno
< FIRST_PSEUDO_REGISTER
3768 && (global_regs
[regno
]
3769 || fixed_regs
[regno
]
3770 || FUNCTION_ARG_REGNO_P (regno
))))
3773 return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start
, regno
);
3776 /* 1 if register REGNO was alive at a place where `setjmp' was called
3777 and was set more than once or is an argument.
3778 Such regs may be clobbered by `longjmp'. */
3781 regno_clobbered_at_setjmp (regno
)
3784 if (n_basic_blocks
== 0)
3787 return ((REG_N_SETS (regno
) > 1
3788 || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start
, regno
))
3789 && REGNO_REG_SET_P (regs_live_at_setjmp
, regno
));
3792 /* INSN references memory, possibly using autoincrement addressing modes.
3793 Find any entries on the mem_set_list that need to be invalidated due
3794 to an address change. */
3796 invalidate_mems_from_autoinc (insn
)
3799 rtx note
= REG_NOTES (insn
);
3800 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3802 if (REG_NOTE_KIND (note
) == REG_INC
)
3804 rtx temp
= mem_set_list
;
3805 rtx prev
= NULL_RTX
;
3810 next
= XEXP (temp
, 1);
3811 if (reg_overlap_mentioned_p (XEXP (note
, 0), XEXP (temp
, 0)))
3813 /* Splice temp out of list. */
3815 XEXP (prev
, 1) = next
;
3817 mem_set_list
= next
;
3818 free_EXPR_LIST_node (temp
);
3828 /* Process the registers that are set within X. Their bits are set to
3829 1 in the regset DEAD, because they are dead prior to this insn.
3831 If INSN is nonzero, it is the insn being processed.
3833 FLAGS is the set of operations to perform. */
3836 mark_set_regs (needed
, dead
, x
, insn
, significant
, flags
)
3844 register RTX_CODE code
= GET_CODE (x
);
3846 if (code
== SET
|| code
== CLOBBER
)
3847 mark_set_1 (needed
, dead
, x
, insn
, significant
, flags
);
3848 else if (code
== PARALLEL
)
3851 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3853 code
= GET_CODE (XVECEXP (x
, 0, i
));
3854 if (code
== SET
|| code
== CLOBBER
)
3855 mark_set_1 (needed
, dead
, XVECEXP (x
, 0, i
), insn
,
3856 significant
, flags
);
3861 /* Process a single SET rtx, X. */
3864 mark_set_1 (needed
, dead
, x
, insn
, significant
, flags
)
3872 register int regno
= -1;
3873 register rtx reg
= SET_DEST (x
);
3875 /* Some targets place small structures in registers for
3876 return values of functions. We have to detect this
3877 case specially here to get correct flow information. */
3878 if (GET_CODE (reg
) == PARALLEL
3879 && GET_MODE (reg
) == BLKmode
)
3883 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
3884 mark_set_1 (needed
, dead
, XVECEXP (reg
, 0, i
), insn
,
3885 significant
, flags
);
3889 /* Modifying just one hardware register of a multi-reg value
3890 or just a byte field of a register
3891 does not mean the value from before this insn is now dead.
3892 But it does mean liveness of that register at the end of the block
3895 Within mark_set_1, however, we treat it as if the register is
3896 indeed modified. mark_used_regs will, however, also treat this
3897 register as being used. Thus, we treat these insns as setting a
3898 new value for the register as a function of its old value. This
3899 cases LOG_LINKS to be made appropriately and this will help combine. */
3901 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
3902 || GET_CODE (reg
) == SIGN_EXTRACT
3903 || GET_CODE (reg
) == STRICT_LOW_PART
)
3904 reg
= XEXP (reg
, 0);
3906 /* If this set is a MEM, then it kills any aliased writes.
3907 If this set is a REG, then it kills any MEMs which use the reg. */
3908 if (flags
& PROP_SCAN_DEAD_CODE
)
3910 if (GET_CODE (reg
) == MEM
3911 || GET_CODE (reg
) == REG
)
3913 rtx temp
= mem_set_list
;
3914 rtx prev
= NULL_RTX
;
3919 next
= XEXP (temp
, 1);
3920 if ((GET_CODE (reg
) == MEM
3921 && output_dependence (XEXP (temp
, 0), reg
))
3922 || (GET_CODE (reg
) == REG
3923 && reg_overlap_mentioned_p (reg
, XEXP (temp
, 0))))
3925 /* Splice this entry out of the list. */
3927 XEXP (prev
, 1) = next
;
3929 mem_set_list
= next
;
3930 free_EXPR_LIST_node (temp
);
3938 /* If the memory reference had embedded side effects (autoincrement
3939 address modes. Then we may need to kill some entries on the
3941 if (insn
&& GET_CODE (reg
) == MEM
)
3942 invalidate_mems_from_autoinc (insn
);
3944 if (GET_CODE (reg
) == MEM
&& ! side_effects_p (reg
)
3945 /* We do not know the size of a BLKmode store, so we do not track
3946 them for redundant store elimination. */
3947 && GET_MODE (reg
) != BLKmode
3948 /* There are no REG_INC notes for SP, so we can't assume we'll see
3949 everything that invalidates it. To be safe, don't eliminate any
3950 stores though SP; none of them should be redundant anyway. */
3951 && ! reg_mentioned_p (stack_pointer_rtx
, reg
))
3952 mem_set_list
= alloc_EXPR_LIST (0, reg
, mem_set_list
);
3955 if (GET_CODE (reg
) == REG
3956 && (regno
= REGNO (reg
),
3957 ! (regno
== FRAME_POINTER_REGNUM
3958 && (! reload_completed
|| frame_pointer_needed
)))
3959 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3960 && ! (regno
== HARD_FRAME_POINTER_REGNUM
3961 && (! reload_completed
|| frame_pointer_needed
))
3963 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3964 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
3966 && ! (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
]))
3967 /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
3969 int some_needed
= REGNO_REG_SET_P (needed
, regno
);
3970 int some_not_needed
= ! some_needed
;
3972 /* Mark it as a significant register for this basic block. */
3974 SET_REGNO_REG_SET (significant
, regno
);
3976 /* Mark it as dead before this insn. */
3977 SET_REGNO_REG_SET (dead
, regno
);
3979 /* A hard reg in a wide mode may really be multiple registers.
3980 If so, mark all of them just like the first. */
3981 if (regno
< FIRST_PSEUDO_REGISTER
)
3985 /* Nothing below is needed for the stack pointer; get out asap.
3986 Eg, log links aren't needed, since combine won't use them. */
3987 if (regno
== STACK_POINTER_REGNUM
)
3990 n
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
3993 int regno_n
= regno
+ n
;
3994 int needed_regno
= REGNO_REG_SET_P (needed
, regno_n
);
3996 SET_REGNO_REG_SET (significant
, regno_n
);
3998 SET_REGNO_REG_SET (dead
, regno_n
);
3999 some_needed
|= needed_regno
;
4000 some_not_needed
|= ! needed_regno
;
4004 /* Additional data to record if this is the final pass. */
4005 if (flags
& (PROP_LOG_LINKS
| PROP_REG_INFO
4006 | PROP_DEATH_NOTES
| PROP_AUTOINC
))
4009 register int blocknum
= BLOCK_NUM (insn
);
4012 if (flags
& (PROP_LOG_LINKS
| PROP_AUTOINC
))
4013 y
= reg_next_use
[regno
];
4015 /* If this is a hard reg, record this function uses the reg. */
4017 if (regno
< FIRST_PSEUDO_REGISTER
)
4020 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4022 if (flags
& (PROP_LOG_LINKS
| PROP_AUTOINC
))
4023 for (i
= regno
; i
< endregno
; i
++)
4025 /* The next use is no longer "next", since a store
4027 reg_next_use
[i
] = 0;
4030 if (flags
& PROP_REG_INFO
)
4031 for (i
= regno
; i
< endregno
; i
++)
4033 regs_ever_live
[i
] = 1;
4039 /* The next use is no longer "next", since a store
4041 if (flags
& (PROP_LOG_LINKS
| PROP_AUTOINC
))
4042 reg_next_use
[regno
] = 0;
4044 /* Keep track of which basic blocks each reg appears in. */
4046 if (flags
& PROP_REG_INFO
)
4048 if (REG_BASIC_BLOCK (regno
) == REG_BLOCK_UNKNOWN
)
4049 REG_BASIC_BLOCK (regno
) = blocknum
;
4050 else if (REG_BASIC_BLOCK (regno
) != blocknum
)
4051 REG_BASIC_BLOCK (regno
) = REG_BLOCK_GLOBAL
;
4053 /* Count (weighted) references, stores, etc. This counts a
4054 register twice if it is modified, but that is correct. */
4055 REG_N_SETS (regno
)++;
4056 REG_N_REFS (regno
) += loop_depth
;
4058 /* The insns where a reg is live are normally counted
4059 elsewhere, but we want the count to include the insn
4060 where the reg is set, and the normal counting mechanism
4061 would not count it. */
4062 REG_LIVE_LENGTH (regno
)++;
4066 if (! some_not_needed
)
4068 if (flags
& PROP_LOG_LINKS
)
4070 /* Make a logical link from the next following insn
4071 that uses this register, back to this insn.
4072 The following insns have already been processed.
4074 We don't build a LOG_LINK for hard registers containing
4075 in ASM_OPERANDs. If these registers get replaced,
4076 we might wind up changing the semantics of the insn,
4077 even if reload can make what appear to be valid
4078 assignments later. */
4079 if (y
&& (BLOCK_NUM (y
) == blocknum
)
4080 && (regno
>= FIRST_PSEUDO_REGISTER
4081 || asm_noperands (PATTERN (y
)) < 0))
4082 LOG_LINKS (y
) = alloc_INSN_LIST (insn
, LOG_LINKS (y
));
4085 else if (! some_needed
)
4087 if (flags
& PROP_REG_INFO
)
4088 REG_N_DEATHS (REGNO (reg
))++;
4090 if (flags
& PROP_DEATH_NOTES
)
4092 /* Note that dead stores have already been deleted
4093 when possible. If we get here, we have found a
4094 dead store that cannot be eliminated (because the
4095 same insn does something useful). Indicate this
4096 by marking the reg being set as dying here. */
4098 = alloc_EXPR_LIST (REG_UNUSED
, reg
, REG_NOTES (insn
));
4103 if (flags
& PROP_DEATH_NOTES
)
4105 /* This is a case where we have a multi-word hard register
4106 and some, but not all, of the words of the register are
4107 needed in subsequent insns. Write REG_UNUSED notes
4108 for those parts that were not needed. This case should
4113 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
)) - 1;
4115 if (!REGNO_REG_SET_P (needed
, regno
+ i
))
4119 gen_rtx_REG (reg_raw_mode
[regno
+ i
], regno
+ i
),
4125 else if (GET_CODE (reg
) == REG
)
4127 if (flags
& (PROP_LOG_LINKS
| PROP_AUTOINC
))
4128 reg_next_use
[regno
] = 0;
4131 /* If this is the last pass and this is a SCRATCH, show it will be dying
4132 here and count it. */
4133 else if (GET_CODE (reg
) == SCRATCH
)
4135 if (flags
& PROP_DEATH_NOTES
)
4137 = alloc_EXPR_LIST (REG_UNUSED
, reg
, REG_NOTES (insn
));
4143 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
4147 find_auto_inc (needed
, x
, insn
)
4152 rtx addr
= XEXP (x
, 0);
4153 HOST_WIDE_INT offset
= 0;
4156 /* Here we detect use of an index register which might be good for
4157 postincrement, postdecrement, preincrement, or predecrement. */
4159 if (GET_CODE (addr
) == PLUS
&& GET_CODE (XEXP (addr
, 1)) == CONST_INT
)
4160 offset
= INTVAL (XEXP (addr
, 1)), addr
= XEXP (addr
, 0);
4162 if (GET_CODE (addr
) == REG
)
4165 register int size
= GET_MODE_SIZE (GET_MODE (x
));
4168 int regno
= REGNO (addr
);
4170 /* Is the next use an increment that might make auto-increment? */
4171 if ((incr
= reg_next_use
[regno
]) != 0
4172 && (set
= single_set (incr
)) != 0
4173 && GET_CODE (set
) == SET
4174 && BLOCK_NUM (incr
) == BLOCK_NUM (insn
)
4175 /* Can't add side effects to jumps; if reg is spilled and
4176 reloaded, there's no way to store back the altered value. */
4177 && GET_CODE (insn
) != JUMP_INSN
4178 && (y
= SET_SRC (set
), GET_CODE (y
) == PLUS
)
4179 && XEXP (y
, 0) == addr
4180 && GET_CODE (XEXP (y
, 1)) == CONST_INT
4181 && ((HAVE_POST_INCREMENT
4182 && (INTVAL (XEXP (y
, 1)) == size
&& offset
== 0))
4183 || (HAVE_POST_DECREMENT
4184 && (INTVAL (XEXP (y
, 1)) == - size
&& offset
== 0))
4185 || (HAVE_PRE_INCREMENT
4186 && (INTVAL (XEXP (y
, 1)) == size
&& offset
== size
))
4187 || (HAVE_PRE_DECREMENT
4188 && (INTVAL (XEXP (y
, 1)) == - size
&& offset
== - size
)))
4189 /* Make sure this reg appears only once in this insn. */
4190 && (use
= find_use_as_address (PATTERN (insn
), addr
, offset
),
4191 use
!= 0 && use
!= (rtx
) 1))
4193 rtx q
= SET_DEST (set
);
4194 enum rtx_code inc_code
= (INTVAL (XEXP (y
, 1)) == size
4195 ? (offset
? PRE_INC
: POST_INC
)
4196 : (offset
? PRE_DEC
: POST_DEC
));
4198 if (dead_or_set_p (incr
, addr
))
4200 /* This is the simple case. Try to make the auto-inc. If
4201 we can't, we are done. Otherwise, we will do any
4202 needed updates below. */
4203 if (! validate_change (insn
, &XEXP (x
, 0),
4204 gen_rtx_fmt_e (inc_code
, Pmode
, addr
),
4208 else if (GET_CODE (q
) == REG
4209 /* PREV_INSN used here to check the semi-open interval
4211 && ! reg_used_between_p (q
, PREV_INSN (insn
), incr
)
4212 /* We must also check for sets of q as q may be
4213 a call clobbered hard register and there may
4214 be a call between PREV_INSN (insn) and incr. */
4215 && ! reg_set_between_p (q
, PREV_INSN (insn
), incr
))
4217 /* We have *p followed sometime later by q = p+size.
4218 Both p and q must be live afterward,
4219 and q is not used between INSN and its assignment.
4220 Change it to q = p, ...*q..., q = q+size.
4221 Then fall into the usual case. */
4226 emit_move_insn (q
, addr
);
4227 insns
= get_insns ();
4230 bb
= BLOCK_FOR_INSN (insn
);
4231 for (temp
= insns
; temp
; temp
= NEXT_INSN (temp
))
4232 set_block_for_insn (temp
, bb
);
4234 /* If we can't make the auto-inc, or can't make the
4235 replacement into Y, exit. There's no point in making
4236 the change below if we can't do the auto-inc and doing
4237 so is not correct in the pre-inc case. */
4239 validate_change (insn
, &XEXP (x
, 0),
4240 gen_rtx_fmt_e (inc_code
, Pmode
, q
),
4242 validate_change (incr
, &XEXP (y
, 0), q
, 1);
4243 if (! apply_change_group ())
4246 /* We now know we'll be doing this change, so emit the
4247 new insn(s) and do the updates. */
4248 emit_insns_before (insns
, insn
);
4250 if (BLOCK_FOR_INSN (insn
)->head
== insn
)
4251 BLOCK_FOR_INSN (insn
)->head
= insns
;
4253 /* INCR will become a NOTE and INSN won't contain a
4254 use of ADDR. If a use of ADDR was just placed in
4255 the insn before INSN, make that the next use.
4256 Otherwise, invalidate it. */
4257 if (GET_CODE (PREV_INSN (insn
)) == INSN
4258 && GET_CODE (PATTERN (PREV_INSN (insn
))) == SET
4259 && SET_SRC (PATTERN (PREV_INSN (insn
))) == addr
)
4260 reg_next_use
[regno
] = PREV_INSN (insn
);
4262 reg_next_use
[regno
] = 0;
4267 /* REGNO is now used in INCR which is below INSN, but
4268 it previously wasn't live here. If we don't mark
4269 it as needed, we'll put a REG_DEAD note for it
4270 on this insn, which is incorrect. */
4271 SET_REGNO_REG_SET (needed
, regno
);
4273 /* If there are any calls between INSN and INCR, show
4274 that REGNO now crosses them. */
4275 for (temp
= insn
; temp
!= incr
; temp
= NEXT_INSN (temp
))
4276 if (GET_CODE (temp
) == CALL_INSN
)
4277 REG_N_CALLS_CROSSED (regno
)++;
4282 /* If we haven't returned, it means we were able to make the
4283 auto-inc, so update the status. First, record that this insn
4284 has an implicit side effect. */
4287 = alloc_EXPR_LIST (REG_INC
, addr
, REG_NOTES (insn
));
4289 /* Modify the old increment-insn to simply copy
4290 the already-incremented value of our register. */
4291 if (! validate_change (incr
, &SET_SRC (set
), addr
, 0))
4294 /* If that makes it a no-op (copying the register into itself) delete
4295 it so it won't appear to be a "use" and a "set" of this
4297 if (SET_DEST (set
) == addr
)
4299 PUT_CODE (incr
, NOTE
);
4300 NOTE_LINE_NUMBER (incr
) = NOTE_INSN_DELETED
;
4301 NOTE_SOURCE_FILE (incr
) = 0;
4304 if (regno
>= FIRST_PSEUDO_REGISTER
)
4306 /* Count an extra reference to the reg. When a reg is
4307 incremented, spilling it is worse, so we want to make
4308 that less likely. */
4309 REG_N_REFS (regno
) += loop_depth
;
4311 /* Count the increment as a setting of the register,
4312 even though it isn't a SET in rtl. */
4313 REG_N_SETS (regno
)++;
4318 #endif /* AUTO_INC_DEC */
4320 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
4321 This is done assuming the registers needed from X
4322 are those that have 1-bits in NEEDED.
4324 FLAGS is the set of enabled operations.
4326 INSN is the containing instruction. If INSN is dead, this function is not
4330 mark_used_regs (needed
, live
, x
, flags
, insn
)
4337 register RTX_CODE code
;
4342 code
= GET_CODE (x
);
4362 /* If we are clobbering a MEM, mark any registers inside the address
4364 if (GET_CODE (XEXP (x
, 0)) == MEM
)
4365 mark_used_regs (needed
, live
, XEXP (XEXP (x
, 0), 0), flags
, insn
);
4369 /* Don't bother watching stores to mems if this is not the
4370 final pass. We'll not be deleting dead stores this round. */
4371 if (flags
& PROP_SCAN_DEAD_CODE
)
4373 /* Invalidate the data for the last MEM stored, but only if MEM is
4374 something that can be stored into. */
4375 if (GET_CODE (XEXP (x
, 0)) == SYMBOL_REF
4376 && CONSTANT_POOL_ADDRESS_P (XEXP (x
, 0)))
4377 ; /* needn't clear the memory set list */
4380 rtx temp
= mem_set_list
;
4381 rtx prev
= NULL_RTX
;
4386 next
= XEXP (temp
, 1);
4387 if (anti_dependence (XEXP (temp
, 0), x
))
4389 /* Splice temp out of the list. */
4391 XEXP (prev
, 1) = next
;
4393 mem_set_list
= next
;
4394 free_EXPR_LIST_node (temp
);
4402 /* If the memory reference had embedded side effects (autoincrement
4403 address modes. Then we may need to kill some entries on the
4406 invalidate_mems_from_autoinc (insn
);
4410 if (flags
& PROP_AUTOINC
)
4411 find_auto_inc (needed
, x
, insn
);
4416 if (GET_CODE (SUBREG_REG (x
)) == REG
4417 && REGNO (SUBREG_REG (x
)) >= FIRST_PSEUDO_REGISTER
4418 && (GET_MODE_SIZE (GET_MODE (x
))
4419 != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))))
4420 REG_CHANGES_SIZE (REGNO (SUBREG_REG (x
))) = 1;
4422 /* While we're here, optimize this case. */
4425 /* In case the SUBREG is not of a register, don't optimize */
4426 if (GET_CODE (x
) != REG
)
4428 mark_used_regs (needed
, live
, x
, flags
, insn
);
4432 /* ... fall through ... */
4435 /* See a register other than being set
4436 => mark it as needed. */
4440 int some_needed
= REGNO_REG_SET_P (needed
, regno
);
4441 int some_not_needed
= ! some_needed
;
4443 SET_REGNO_REG_SET (live
, regno
);
4445 /* A hard reg in a wide mode may really be multiple registers.
4446 If so, mark all of them just like the first. */
4447 if (regno
< FIRST_PSEUDO_REGISTER
)
4451 /* For stack ptr or fixed arg pointer,
4452 nothing below can be necessary, so waste no more time. */
4453 if (regno
== STACK_POINTER_REGNUM
4454 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4455 || (regno
== HARD_FRAME_POINTER_REGNUM
4456 && (! reload_completed
|| frame_pointer_needed
))
4458 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4459 || (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4461 || (regno
== FRAME_POINTER_REGNUM
4462 && (! reload_completed
|| frame_pointer_needed
)))
4464 /* If this is a register we are going to try to eliminate,
4465 don't mark it live here. If we are successful in
4466 eliminating it, it need not be live unless it is used for
4467 pseudos, in which case it will have been set live when
4468 it was allocated to the pseudos. If the register will not
4469 be eliminated, reload will set it live at that point. */
4471 if (! TEST_HARD_REG_BIT (elim_reg_set
, regno
))
4472 regs_ever_live
[regno
] = 1;
4475 /* No death notes for global register variables;
4476 their values are live after this function exits. */
4477 if (global_regs
[regno
])
4479 if (flags
& (PROP_LOG_LINKS
| PROP_AUTOINC
))
4480 reg_next_use
[regno
] = insn
;
4484 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4487 int regno_n
= regno
+ n
;
4488 int needed_regno
= REGNO_REG_SET_P (needed
, regno_n
);
4490 SET_REGNO_REG_SET (live
, regno_n
);
4491 some_needed
|= needed_regno
;
4492 some_not_needed
|= ! needed_regno
;
4496 if (flags
& (PROP_LOG_LINKS
| PROP_AUTOINC
))
4498 /* Record where each reg is used, so when the reg
4499 is set we know the next insn that uses it. */
4501 reg_next_use
[regno
] = insn
;
4503 if (flags
& PROP_REG_INFO
)
4505 if (regno
< FIRST_PSEUDO_REGISTER
)
4507 /* If a hard reg is being used,
4508 record that this function does use it. */
4510 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4514 regs_ever_live
[regno
+ --i
] = 1;
4519 /* Keep track of which basic block each reg appears in. */
4521 register int blocknum
= BLOCK_NUM (insn
);
4523 if (REG_BASIC_BLOCK (regno
) == REG_BLOCK_UNKNOWN
)
4524 REG_BASIC_BLOCK (regno
) = blocknum
;
4525 else if (REG_BASIC_BLOCK (regno
) != blocknum
)
4526 REG_BASIC_BLOCK (regno
) = REG_BLOCK_GLOBAL
;
4528 /* Count (weighted) number of uses of each reg. */
4530 REG_N_REFS (regno
) += loop_depth
;
4534 /* Record and count the insns in which a reg dies.
4535 If it is used in this insn and was dead below the insn
4536 then it dies in this insn. If it was set in this insn,
4537 we do not make a REG_DEAD note; likewise if we already
4538 made such a note. */
4540 if (flags
& PROP_DEATH_NOTES
)
4543 && ! dead_or_set_p (insn
, x
)
4545 && (regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
4549 /* Check for the case where the register dying partially
4550 overlaps the register set by this insn. */
4551 if (regno
< FIRST_PSEUDO_REGISTER
4552 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4554 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4556 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4559 /* If none of the words in X is needed, make a REG_DEAD
4560 note. Otherwise, we must make partial REG_DEAD notes. */
4564 = alloc_EXPR_LIST (REG_DEAD
, x
, REG_NOTES (insn
));
4565 REG_N_DEATHS (regno
)++;
4571 /* Don't make a REG_DEAD note for a part of a register
4572 that is set in the insn. */
4574 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4576 if (!REGNO_REG_SET_P (needed
, regno
+ i
)
4577 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4580 (REG_DEAD
, gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4591 register rtx testreg
= SET_DEST (x
);
4594 /* If storing into MEM, don't show it as being used. But do
4595 show the address as being used. */
4596 if (GET_CODE (testreg
) == MEM
)
4599 if (flags
& PROP_AUTOINC
)
4600 find_auto_inc (needed
, testreg
, insn
);
4602 mark_used_regs (needed
, live
, XEXP (testreg
, 0), flags
, insn
);
4603 mark_used_regs (needed
, live
, SET_SRC (x
), flags
, insn
);
4607 /* Storing in STRICT_LOW_PART is like storing in a reg
4608 in that this SET might be dead, so ignore it in TESTREG.
4609 but in some other ways it is like using the reg.
4611 Storing in a SUBREG or a bit field is like storing the entire
4612 register in that if the register's value is not used
4613 then this SET is not needed. */
4614 while (GET_CODE (testreg
) == STRICT_LOW_PART
4615 || GET_CODE (testreg
) == ZERO_EXTRACT
4616 || GET_CODE (testreg
) == SIGN_EXTRACT
4617 || GET_CODE (testreg
) == SUBREG
)
4619 if (GET_CODE (testreg
) == SUBREG
4620 && GET_CODE (SUBREG_REG (testreg
)) == REG
4621 && REGNO (SUBREG_REG (testreg
)) >= FIRST_PSEUDO_REGISTER
4622 && (GET_MODE_SIZE (GET_MODE (testreg
))
4623 != GET_MODE_SIZE (GET_MODE (SUBREG_REG (testreg
)))))
4624 REG_CHANGES_SIZE (REGNO (SUBREG_REG (testreg
))) = 1;
4626 /* Modifying a single register in an alternate mode
4627 does not use any of the old value. But these other
4628 ways of storing in a register do use the old value. */
4629 if (GET_CODE (testreg
) == SUBREG
4630 && !(REG_SIZE (SUBREG_REG (testreg
)) > REG_SIZE (testreg
)))
4635 testreg
= XEXP (testreg
, 0);
4638 /* If this is a store into a register,
4639 recursively scan the value being stored. */
4641 if ((GET_CODE (testreg
) == PARALLEL
4642 && GET_MODE (testreg
) == BLKmode
)
4643 || (GET_CODE (testreg
) == REG
4644 && (regno
= REGNO (testreg
), ! (regno
== FRAME_POINTER_REGNUM
4645 && (! reload_completed
|| frame_pointer_needed
)))
4646 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4647 && ! (regno
== HARD_FRAME_POINTER_REGNUM
4648 && (! reload_completed
|| frame_pointer_needed
))
4650 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4651 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4654 /* We used to exclude global_regs here, but that seems wrong.
4655 Storing in them is like storing in mem. */
4657 mark_used_regs (needed
, live
, SET_SRC (x
), flags
, insn
);
4659 mark_used_regs (needed
, live
, SET_DEST (x
), flags
, insn
);
4666 /* ??? This info should have been gotten from mark_regs_live_at_end,
4667 as applied to the EXIT block, and propagated along the edge that
4668 connects this block to the EXIT. */
4672 case UNSPEC_VOLATILE
:
4676 /* Traditional and volatile asm instructions must be considered to use
4677 and clobber all hard registers, all pseudo-registers and all of
4678 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
4680 Consider for instance a volatile asm that changes the fpu rounding
4681 mode. An insn should not be moved across this even if it only uses
4682 pseudo-regs because it might give an incorrectly rounded result.
4684 ?!? Unfortunately, marking all hard registers as live causes massive
4685 problems for the register allocator and marking all pseudos as live
4686 creates mountains of uninitialized variable warnings.
4688 So for now, just clear the memory set list and mark any regs
4689 we can find in ASM_OPERANDS as used. */
4690 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
4691 free_EXPR_LIST_list (&mem_set_list
);
4693 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
4694 We can not just fall through here since then we would be confused
4695 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
4696 traditional asms unlike their normal usage. */
4697 if (code
== ASM_OPERANDS
)
4701 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
4702 mark_used_regs (needed
, live
, ASM_OPERANDS_INPUT (x
, j
),
4713 /* Recursively scan the operands of this expression. */
4716 register const char *fmt
= GET_RTX_FORMAT (code
);
4719 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4723 /* Tail recursive case: save a function call level. */
4729 mark_used_regs (needed
, live
, XEXP (x
, i
), flags
, insn
);
4731 else if (fmt
[i
] == 'E')
4734 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4735 mark_used_regs (needed
, live
, XVECEXP (x
, i
, j
), flags
, insn
);
4744 try_pre_increment_1 (insn
)
4747 /* Find the next use of this reg. If in same basic block,
4748 make it do pre-increment or pre-decrement if appropriate. */
4749 rtx x
= single_set (insn
);
4750 HOST_WIDE_INT amount
= ((GET_CODE (SET_SRC (x
)) == PLUS
? 1 : -1)
4751 * INTVAL (XEXP (SET_SRC (x
), 1)));
4752 int regno
= REGNO (SET_DEST (x
));
4753 rtx y
= reg_next_use
[regno
];
4755 && BLOCK_NUM (y
) == BLOCK_NUM (insn
)
4756 /* Don't do this if the reg dies, or gets set in y; a standard addressing
4757 mode would be better. */
4758 && ! dead_or_set_p (y
, SET_DEST (x
))
4759 && try_pre_increment (y
, SET_DEST (x
), amount
))
4761 /* We have found a suitable auto-increment
4762 and already changed insn Y to do it.
4763 So flush this increment-instruction. */
4764 PUT_CODE (insn
, NOTE
);
4765 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
4766 NOTE_SOURCE_FILE (insn
) = 0;
4767 /* Count a reference to this reg for the increment
4768 insn we are deleting. When a reg is incremented.
4769 spilling it is worse, so we want to make that
4771 if (regno
>= FIRST_PSEUDO_REGISTER
)
4773 REG_N_REFS (regno
) += loop_depth
;
4774 REG_N_SETS (regno
)++;
4781 /* Try to change INSN so that it does pre-increment or pre-decrement
4782 addressing on register REG in order to add AMOUNT to REG.
4783 AMOUNT is negative for pre-decrement.
4784 Returns 1 if the change could be made.
4785 This checks all about the validity of the result of modifying INSN. */
4788 try_pre_increment (insn
, reg
, amount
)
4790 HOST_WIDE_INT amount
;
4794 /* Nonzero if we can try to make a pre-increment or pre-decrement.
4795 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
4797 /* Nonzero if we can try to make a post-increment or post-decrement.
4798 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
4799 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
4800 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
4803 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
4806 /* From the sign of increment, see which possibilities are conceivable
4807 on this target machine. */
4808 if (HAVE_PRE_INCREMENT
&& amount
> 0)
4810 if (HAVE_POST_INCREMENT
&& amount
> 0)
4813 if (HAVE_PRE_DECREMENT
&& amount
< 0)
4815 if (HAVE_POST_DECREMENT
&& amount
< 0)
4818 if (! (pre_ok
|| post_ok
))
4821 /* It is not safe to add a side effect to a jump insn
4822 because if the incremented register is spilled and must be reloaded
4823 there would be no way to store the incremented value back in memory. */
4825 if (GET_CODE (insn
) == JUMP_INSN
)
4830 use
= find_use_as_address (PATTERN (insn
), reg
, 0);
4831 if (post_ok
&& (use
== 0 || use
== (rtx
) 1))
4833 use
= find_use_as_address (PATTERN (insn
), reg
, -amount
);
4837 if (use
== 0 || use
== (rtx
) 1)
4840 if (GET_MODE_SIZE (GET_MODE (use
)) != (amount
> 0 ? amount
: - amount
))
4843 /* See if this combination of instruction and addressing mode exists. */
4844 if (! validate_change (insn
, &XEXP (use
, 0),
4845 gen_rtx_fmt_e (amount
> 0
4846 ? (do_post
? POST_INC
: PRE_INC
)
4847 : (do_post
? POST_DEC
: PRE_DEC
),
4851 /* Record that this insn now has an implicit side effect on X. */
4852 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_INC
, reg
, REG_NOTES (insn
));
4856 #endif /* AUTO_INC_DEC */
4858 /* Find the place in the rtx X where REG is used as a memory address.
4859 Return the MEM rtx that so uses it.
4860 If PLUSCONST is nonzero, search instead for a memory address equivalent to
4861 (plus REG (const_int PLUSCONST)).
4863 If such an address does not appear, return 0.
4864 If REG appears more than once, or is used other than in such an address,
4868 find_use_as_address (x
, reg
, plusconst
)
4871 HOST_WIDE_INT plusconst
;
4873 enum rtx_code code
= GET_CODE (x
);
4874 const char *fmt
= GET_RTX_FORMAT (code
);
4876 register rtx value
= 0;
4879 if (code
== MEM
&& XEXP (x
, 0) == reg
&& plusconst
== 0)
4882 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
4883 && XEXP (XEXP (x
, 0), 0) == reg
4884 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
4885 && INTVAL (XEXP (XEXP (x
, 0), 1)) == plusconst
)
4888 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4890 /* If REG occurs inside a MEM used in a bit-field reference,
4891 that is unacceptable. */
4892 if (find_use_as_address (XEXP (x
, 0), reg
, 0) != 0)
4893 return (rtx
) (HOST_WIDE_INT
) 1;
4897 return (rtx
) (HOST_WIDE_INT
) 1;
4899 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4903 tem
= find_use_as_address (XEXP (x
, i
), reg
, plusconst
);
4907 return (rtx
) (HOST_WIDE_INT
) 1;
4912 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4914 tem
= find_use_as_address (XVECEXP (x
, i
, j
), reg
, plusconst
);
4918 return (rtx
) (HOST_WIDE_INT
) 1;
4926 /* Write information about registers and basic blocks into FILE.
4927 This is part of making a debugging dump. */
4930 dump_flow_info (file
)
4934 static const char * const reg_class_names
[] = REG_CLASS_NAMES
;
4936 fprintf (file
, "%d registers.\n", max_regno
);
4937 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
4940 enum reg_class
class, altclass
;
4941 fprintf (file
, "\nRegister %d used %d times across %d insns",
4942 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
4943 if (REG_BASIC_BLOCK (i
) >= 0)
4944 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
4946 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
4947 (REG_N_SETS (i
) == 1) ? "" : "s");
4948 if (REG_USERVAR_P (regno_reg_rtx
[i
]))
4949 fprintf (file
, "; user var");
4950 if (REG_N_DEATHS (i
) != 1)
4951 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
4952 if (REG_N_CALLS_CROSSED (i
) == 1)
4953 fprintf (file
, "; crosses 1 call");
4954 else if (REG_N_CALLS_CROSSED (i
))
4955 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
4956 if (PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
4957 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
4958 class = reg_preferred_class (i
);
4959 altclass
= reg_alternate_class (i
);
4960 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
4962 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
4963 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
4964 else if (altclass
== NO_REGS
)
4965 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
4967 fprintf (file
, "; pref %s, else %s",
4968 reg_class_names
[(int) class],
4969 reg_class_names
[(int) altclass
]);
4971 if (REGNO_POINTER_FLAG (i
))
4972 fprintf (file
, "; pointer");
4973 fprintf (file
, ".\n");
4976 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
4977 for (i
= 0; i
< n_basic_blocks
; i
++)
4979 register basic_block bb
= BASIC_BLOCK (i
);
4983 fprintf (file
, "\nBasic block %d: first insn %d, last %d.\n",
4984 i
, INSN_UID (bb
->head
), INSN_UID (bb
->end
));
4986 fprintf (file
, "Predecessors: ");
4987 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
4988 dump_edge_info (file
, e
, 0);
4990 fprintf (file
, "\nSuccessors: ");
4991 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4992 dump_edge_info (file
, e
, 1);
4994 fprintf (file
, "\nRegisters live at start:");
4995 if (bb
->global_live_at_start
)
4997 for (regno
= 0; regno
< max_regno
; regno
++)
4998 if (REGNO_REG_SET_P (bb
->global_live_at_start
, regno
))
4999 fprintf (file
, " %d", regno
);
5002 fprintf (file
, " n/a");
5004 fprintf (file
, "\nRegisters live at end:");
5005 if (bb
->global_live_at_end
)
5007 for (regno
= 0; regno
< max_regno
; regno
++)
5008 if (REGNO_REG_SET_P (bb
->global_live_at_end
, regno
))
5009 fprintf (file
, " %d", regno
);
5012 fprintf (file
, " n/a");
5023 dump_flow_info (stderr
);
5027 dump_edge_info (file
, e
, do_succ
)
5032 basic_block side
= (do_succ
? e
->dest
: e
->src
);
5034 if (side
== ENTRY_BLOCK_PTR
)
5035 fputs (" ENTRY", file
);
5036 else if (side
== EXIT_BLOCK_PTR
)
5037 fputs (" EXIT", file
);
5039 fprintf (file
, " %d", side
->index
);
5043 static const char * const bitnames
[] = {
5044 "fallthru", "crit", "ab", "abcall", "eh", "fake"
5047 int i
, flags
= e
->flags
;
5051 for (i
= 0; flags
; i
++)
5052 if (flags
& (1 << i
))
5058 if (i
< (int)(sizeof (bitnames
) / sizeof (*bitnames
)))
5059 fputs (bitnames
[i
], file
);
5061 fprintf (file
, "%d", i
);
5069 /* Like print_rtl, but also print out live information for the start of each
5073 print_rtl_with_bb (outf
, rtx_first
)
5077 register rtx tmp_rtx
;
5080 fprintf (outf
, "(nil)\n");
5084 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
5085 int max_uid
= get_max_uid ();
5086 basic_block
*start
= (basic_block
*)
5087 xcalloc (max_uid
, sizeof (basic_block
));
5088 basic_block
*end
= (basic_block
*)
5089 xcalloc (max_uid
, sizeof (basic_block
));
5090 enum bb_state
*in_bb_p
= (enum bb_state
*)
5091 xcalloc (max_uid
, sizeof (enum bb_state
));
5093 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
5095 basic_block bb
= BASIC_BLOCK (i
);
5098 start
[INSN_UID (bb
->head
)] = bb
;
5099 end
[INSN_UID (bb
->end
)] = bb
;
5100 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
5102 enum bb_state state
= IN_MULTIPLE_BB
;
5103 if (in_bb_p
[INSN_UID(x
)] == NOT_IN_BB
)
5105 in_bb_p
[INSN_UID(x
)] = state
;
5112 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
5117 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
5119 fprintf (outf
, ";; Start of basic block %d, registers live:",
5122 EXECUTE_IF_SET_IN_REG_SET (bb
->global_live_at_start
, 0, i
,
5124 fprintf (outf
, " %d", i
);
5125 if (i
< FIRST_PSEUDO_REGISTER
)
5126 fprintf (outf
, " [%s]",
5132 if (in_bb_p
[INSN_UID(tmp_rtx
)] == NOT_IN_BB
5133 && GET_CODE (tmp_rtx
) != NOTE
5134 && GET_CODE (tmp_rtx
) != BARRIER
5136 fprintf (outf
, ";; Insn is not within a basic block\n");
5137 else if (in_bb_p
[INSN_UID(tmp_rtx
)] == IN_MULTIPLE_BB
)
5138 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
5140 did_output
= print_rtl_single (outf
, tmp_rtx
);
5142 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
5143 fprintf (outf
, ";; End of basic block %d\n", bb
->index
);
5154 if (current_function_epilogue_delay_list
!= 0)
5156 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
5157 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
5158 tmp_rtx
= XEXP (tmp_rtx
, 1))
5159 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
5163 /* Compute dominator relationships using new flow graph structures. */
5165 compute_flow_dominators (dominators
, post_dominators
)
5166 sbitmap
*dominators
;
5167 sbitmap
*post_dominators
;
5170 sbitmap
*temp_bitmap
;
5172 basic_block
*worklist
, *tos
;
5174 /* Allocate a worklist array/queue. Entries are only added to the
5175 list if they were not already on the list. So the size is
5176 bounded by the number of basic blocks. */
5177 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
5180 temp_bitmap
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
5181 sbitmap_vector_zero (temp_bitmap
, n_basic_blocks
);
5185 /* The optimistic setting of dominators requires us to put every
5186 block on the work list initially. */
5187 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
5189 *tos
++ = BASIC_BLOCK (bb
);
5190 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
5193 /* We want a maximal solution, so initially assume everything dominates
5195 sbitmap_vector_ones (dominators
, n_basic_blocks
);
5197 /* Mark successors of the entry block so we can identify them below. */
5198 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
5199 e
->dest
->aux
= ENTRY_BLOCK_PTR
;
5201 /* Iterate until the worklist is empty. */
5202 while (tos
!= worklist
)
5204 /* Take the first entry off the worklist. */
5205 basic_block b
= *--tos
;
5208 /* Compute the intersection of the dominators of all the
5211 If one of the predecessor blocks is the ENTRY block, then the
5212 intersection of the dominators of the predecessor blocks is
5213 defined as the null set. We can identify such blocks by the
5214 special value in the AUX field in the block structure. */
5215 if (b
->aux
== ENTRY_BLOCK_PTR
)
5217 /* Do not clear the aux field for blocks which are
5218 successors of the ENTRY block. That way we we never
5219 add them to the worklist again.
5221 The intersect of dominators of the preds of this block is
5222 defined as the null set. */
5223 sbitmap_zero (temp_bitmap
[bb
]);
5227 /* Clear the aux field of this block so it can be added to
5228 the worklist again if necessary. */
5230 sbitmap_intersection_of_preds (temp_bitmap
[bb
], dominators
, bb
);
5233 /* Make sure each block always dominates itself. */
5234 SET_BIT (temp_bitmap
[bb
], bb
);
5236 /* If the out state of this block changed, then we need to
5237 add the successors of this block to the worklist if they
5238 are not already on the worklist. */
5239 if (sbitmap_a_and_b (dominators
[bb
], dominators
[bb
], temp_bitmap
[bb
]))
5241 for (e
= b
->succ
; e
; e
= e
->succ_next
)
5243 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR
)
5253 if (post_dominators
)
5255 /* The optimistic setting of dominators requires us to put every
5256 block on the work list initially. */
5257 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
5259 *tos
++ = BASIC_BLOCK (bb
);
5260 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
5263 /* We want a maximal solution, so initially assume everything post
5264 dominates everything else. */
5265 sbitmap_vector_ones (post_dominators
, n_basic_blocks
);
5267 /* Mark predecessors of the exit block so we can identify them below. */
5268 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
5269 e
->src
->aux
= EXIT_BLOCK_PTR
;
5271 /* Iterate until the worklist is empty. */
5272 while (tos
!= worklist
)
5274 /* Take the first entry off the worklist. */
5275 basic_block b
= *--tos
;
5278 /* Compute the intersection of the post dominators of all the
5281 If one of the successor blocks is the EXIT block, then the
5282 intersection of the dominators of the successor blocks is
5283 defined as the null set. We can identify such blocks by the
5284 special value in the AUX field in the block structure. */
5285 if (b
->aux
== EXIT_BLOCK_PTR
)
5287 /* Do not clear the aux field for blocks which are
5288 predecessors of the EXIT block. That way we we never
5289 add them to the worklist again.
5291 The intersect of dominators of the succs of this block is
5292 defined as the null set. */
5293 sbitmap_zero (temp_bitmap
[bb
]);
5297 /* Clear the aux field of this block so it can be added to
5298 the worklist again if necessary. */
5300 sbitmap_intersection_of_succs (temp_bitmap
[bb
],
5301 post_dominators
, bb
);
5304 /* Make sure each block always post dominates itself. */
5305 SET_BIT (temp_bitmap
[bb
], bb
);
5307 /* If the out state of this block changed, then we need to
5308 add the successors of this block to the worklist if they
5309 are not already on the worklist. */
5310 if (sbitmap_a_and_b (post_dominators
[bb
],
5311 post_dominators
[bb
],
5314 for (e
= b
->pred
; e
; e
= e
->pred_next
)
5316 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR
)
5328 /* Given DOMINATORS, compute the immediate dominators into IDOM. */
5331 compute_immediate_dominators (idom
, dominators
)
5333 sbitmap
*dominators
;
5338 tmp
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
5340 /* Begin with tmp(n) = dom(n) - { n }. */
5341 for (b
= n_basic_blocks
; --b
>= 0; )
5343 sbitmap_copy (tmp
[b
], dominators
[b
]);
5344 RESET_BIT (tmp
[b
], b
);
5347 /* Subtract out all of our dominator's dominators. */
5348 for (b
= n_basic_blocks
; --b
>= 0; )
5350 sbitmap tmp_b
= tmp
[b
];
5353 for (s
= n_basic_blocks
; --s
>= 0; )
5354 if (TEST_BIT (tmp_b
, s
))
5355 sbitmap_difference (tmp_b
, tmp_b
, tmp
[s
]);
5358 /* Find the one bit set in the bitmap and put it in the output array. */
5359 for (b
= n_basic_blocks
; --b
>= 0; )
5362 EXECUTE_IF_SET_IN_SBITMAP (tmp
[b
], 0, t
, { idom
[b
] = t
; });
5365 sbitmap_vector_free (tmp
);
5368 /* Count for a single SET rtx, X. */
5371 count_reg_sets_1 (x
)
5375 register rtx reg
= SET_DEST (x
);
5377 /* Find the register that's set/clobbered. */
5378 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
5379 || GET_CODE (reg
) == SIGN_EXTRACT
5380 || GET_CODE (reg
) == STRICT_LOW_PART
)
5381 reg
= XEXP (reg
, 0);
5383 if (GET_CODE (reg
) == PARALLEL
5384 && GET_MODE (reg
) == BLKmode
)
5387 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
5388 count_reg_sets_1 (XVECEXP (reg
, 0, i
));
5392 if (GET_CODE (reg
) == REG
)
5394 regno
= REGNO (reg
);
5395 if (regno
>= FIRST_PSEUDO_REGISTER
)
5397 /* Count (weighted) references, stores, etc. This counts a
5398 register twice if it is modified, but that is correct. */
5399 REG_N_SETS (regno
)++;
5401 REG_N_REFS (regno
) += loop_depth
;
5406 /* Increment REG_N_SETS for each SET or CLOBBER found in X; also increment
5407 REG_N_REFS by the current loop depth for each SET or CLOBBER found. */
5413 register RTX_CODE code
= GET_CODE (x
);
5415 if (code
== SET
|| code
== CLOBBER
)
5416 count_reg_sets_1 (x
);
5417 else if (code
== PARALLEL
)
5420 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
5422 code
= GET_CODE (XVECEXP (x
, 0, i
));
5423 if (code
== SET
|| code
== CLOBBER
)
5424 count_reg_sets_1 (XVECEXP (x
, 0, i
));
5429 /* Increment REG_N_REFS by the current loop depth each register reference
5433 count_reg_references (x
)
5436 register RTX_CODE code
;
5439 code
= GET_CODE (x
);
5459 /* If we are clobbering a MEM, mark any registers inside the address
5461 if (GET_CODE (XEXP (x
, 0)) == MEM
)
5462 count_reg_references (XEXP (XEXP (x
, 0), 0));
5466 /* While we're here, optimize this case. */
5469 /* In case the SUBREG is not of a register, don't optimize */
5470 if (GET_CODE (x
) != REG
)
5472 count_reg_references (x
);
5476 /* ... fall through ... */
5479 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
5480 REG_N_REFS (REGNO (x
)) += loop_depth
;
5485 register rtx testreg
= SET_DEST (x
);
5488 /* If storing into MEM, don't show it as being used. But do
5489 show the address as being used. */
5490 if (GET_CODE (testreg
) == MEM
)
5492 count_reg_references (XEXP (testreg
, 0));
5493 count_reg_references (SET_SRC (x
));
5497 /* Storing in STRICT_LOW_PART is like storing in a reg
5498 in that this SET might be dead, so ignore it in TESTREG.
5499 but in some other ways it is like using the reg.
5501 Storing in a SUBREG or a bit field is like storing the entire
5502 register in that if the register's value is not used
5503 then this SET is not needed. */
5504 while (GET_CODE (testreg
) == STRICT_LOW_PART
5505 || GET_CODE (testreg
) == ZERO_EXTRACT
5506 || GET_CODE (testreg
) == SIGN_EXTRACT
5507 || GET_CODE (testreg
) == SUBREG
)
5509 /* Modifying a single register in an alternate mode
5510 does not use any of the old value. But these other
5511 ways of storing in a register do use the old value. */
5512 if (GET_CODE (testreg
) == SUBREG
5513 && !(REG_SIZE (SUBREG_REG (testreg
)) > REG_SIZE (testreg
)))
5518 testreg
= XEXP (testreg
, 0);
5521 /* If this is a store into a register,
5522 recursively scan the value being stored. */
5524 if ((GET_CODE (testreg
) == PARALLEL
5525 && GET_MODE (testreg
) == BLKmode
)
5526 || GET_CODE (testreg
) == REG
)
5528 count_reg_references (SET_SRC (x
));
5530 count_reg_references (SET_DEST (x
));
5540 /* Recursively scan the operands of this expression. */
5543 register const char *fmt
= GET_RTX_FORMAT (code
);
5546 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
5550 /* Tail recursive case: save a function call level. */
5556 count_reg_references (XEXP (x
, i
));
5558 else if (fmt
[i
] == 'E')
5561 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
5562 count_reg_references (XVECEXP (x
, i
, j
));
5568 /* Recompute register set/reference counts immediately prior to register
5571 This avoids problems with set/reference counts changing to/from values
5572 which have special meanings to the register allocators.
5574 Additionally, the reference counts are the primary component used by the
5575 register allocators to prioritize pseudos for allocation to hard regs.
5576 More accurate reference counts generally lead to better register allocation.
5578 F is the first insn to be scanned.
5579 LOOP_STEP denotes how much loop_depth should be incremented per
5580 loop nesting level in order to increase the ref count more for references
5583 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
5584 possibly other information which is used by the register allocators. */
5587 recompute_reg_usage (f
, loop_step
)
5594 /* Clear out the old data. */
5595 max_reg
= max_reg_num ();
5596 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_reg
; i
++)
5602 /* Scan each insn in the chain and count how many times each register is
5605 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
5607 /* Keep track of loop depth. */
5608 if (GET_CODE (insn
) == NOTE
)
5610 /* Look for loop boundaries. */
5611 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
5612 loop_depth
-= loop_step
;
5613 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
5614 loop_depth
+= loop_step
;
5616 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
5617 Abort now rather than setting register status incorrectly. */
5618 if (loop_depth
== 0)
5621 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5625 /* This call will increment REG_N_SETS for each SET or CLOBBER
5626 of a register in INSN. It will also increment REG_N_REFS
5627 by the loop depth for each set of a register in INSN. */
5628 count_reg_sets (PATTERN (insn
));
5630 /* count_reg_sets does not detect autoincrement address modes, so
5631 detect them here by looking at the notes attached to INSN. */
5632 for (links
= REG_NOTES (insn
); links
; links
= XEXP (links
, 1))
5634 if (REG_NOTE_KIND (links
) == REG_INC
)
5635 /* Count (weighted) references, stores, etc. This counts a
5636 register twice if it is modified, but that is correct. */
5637 REG_N_SETS (REGNO (XEXP (links
, 0)))++;
5640 /* This call will increment REG_N_REFS by the current loop depth for
5641 each reference to a register in INSN. */
5642 count_reg_references (PATTERN (insn
));
5644 /* count_reg_references will not include counts for arguments to
5645 function calls, so detect them here by examining the
5646 CALL_INSN_FUNCTION_USAGE data. */
5647 if (GET_CODE (insn
) == CALL_INSN
)
5651 for (note
= CALL_INSN_FUNCTION_USAGE (insn
);
5653 note
= XEXP (note
, 1))
5654 if (GET_CODE (XEXP (note
, 0)) == USE
)
5655 count_reg_references (XEXP (XEXP (note
, 0), 0));
5661 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
5662 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
5663 of the number of registers that died. */
5666 count_or_remove_death_notes (blocks
, kill
)
5672 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
5677 if (blocks
&& ! TEST_BIT (blocks
, i
))
5680 bb
= BASIC_BLOCK (i
);
5682 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
5684 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5686 rtx
*pprev
= ®_NOTES (insn
);
5691 switch (REG_NOTE_KIND (link
))
5694 if (GET_CODE (XEXP (link
, 0)) == REG
)
5696 rtx reg
= XEXP (link
, 0);
5699 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
5702 n
= HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
));
5710 rtx next
= XEXP (link
, 1);
5711 free_EXPR_LIST_node (link
);
5712 *pprev
= link
= next
;
5718 pprev
= &XEXP (link
, 1);
5725 if (insn
== bb
->end
)
5733 /* Record INSN's block as BB. */
5736 set_block_for_insn (insn
, bb
)
5740 size_t uid
= INSN_UID (insn
);
5741 if (uid
>= basic_block_for_insn
->num_elements
)
5745 /* Add one-eighth the size so we don't keep calling xrealloc. */
5746 new_size
= uid
+ (uid
+ 7) / 8;
5748 VARRAY_GROW (basic_block_for_insn
, new_size
);
5750 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
5753 /* Record INSN's block number as BB. */
5754 /* ??? This has got to go. */
5757 set_block_num (insn
, bb
)
5761 set_block_for_insn (insn
, BASIC_BLOCK (bb
));
5764 /* Verify the CFG consistency. This function check some CFG invariants and
5765 aborts when something is wrong. Hope that this function will help to
5766 convert many optimization passes to preserve CFG consistent.
5768 Currently it does following checks:
5770 - test head/end pointers
5771 - overlapping of basic blocks
5772 - edge list corectness
5773 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
5774 - tails of basic blocks (ensure that boundary is necesary)
5775 - scans body of the basic block for JUMP_INSN, CODE_LABEL
5776 and NOTE_INSN_BASIC_BLOCK
5777 - check that all insns are in the basic blocks
5778 (except the switch handling code, barriers and notes)
5780 In future it can be extended check a lot of other stuff as well
5781 (reachability of basic blocks, life information, etc. etc.). */
5786 const int max_uid
= get_max_uid ();
5787 const rtx rtx_first
= get_insns ();
5788 basic_block
*bb_info
;
5792 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
5794 /* First pass check head/end pointers and set bb_info array used by
5796 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
5798 basic_block bb
= BASIC_BLOCK (i
);
5800 /* Check the head pointer and make sure that it is pointing into
5802 for (x
= rtx_first
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
5807 error ("Head insn %d for block %d not found in the insn stream.",
5808 INSN_UID (bb
->head
), bb
->index
);
5812 /* Check the end pointer and make sure that it is pointing into
5814 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
5816 if (bb_info
[INSN_UID (x
)] != NULL
)
5818 error ("Insn %d is in multiple basic blocks (%d and %d)",
5819 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
5822 bb_info
[INSN_UID (x
)] = bb
;
5829 error ("End insn %d for block %d not found in the insn stream.",
5830 INSN_UID (bb
->end
), bb
->index
);
5835 /* Now check the basic blocks (boundaries etc.) */
5836 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
5838 basic_block bb
= BASIC_BLOCK (i
);
5839 /* Check corectness of edge lists */
5847 fprintf (stderr
, "verify_flow_info: Basic block %d succ edge is corrupted\n",
5849 fprintf (stderr
, "Predecessor: ");
5850 dump_edge_info (stderr
, e
, 0);
5851 fprintf (stderr
, "\nSuccessor: ");
5852 dump_edge_info (stderr
, e
, 1);
5856 if (e
->dest
!= EXIT_BLOCK_PTR
)
5858 edge e2
= e
->dest
->pred
;
5859 while (e2
&& e2
!= e
)
5863 error ("Basic block %i edge lists are corrupted", bb
->index
);
5875 error ("Basic block %d pred edge is corrupted", bb
->index
);
5876 fputs ("Predecessor: ", stderr
);
5877 dump_edge_info (stderr
, e
, 0);
5878 fputs ("\nSuccessor: ", stderr
);
5879 dump_edge_info (stderr
, e
, 1);
5880 fputc ('\n', stderr
);
5883 if (e
->src
!= ENTRY_BLOCK_PTR
)
5885 edge e2
= e
->src
->succ
;
5886 while (e2
&& e2
!= e
)
5890 error ("Basic block %i edge lists are corrupted", bb
->index
);
5897 /* OK pointers are correct. Now check the header of basic
5898 block. It ought to contain optional CODE_LABEL followed
5899 by NOTE_BASIC_BLOCK. */
5901 if (GET_CODE (x
) == CODE_LABEL
)
5905 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
5911 if (GET_CODE (x
) != NOTE
5912 || NOTE_LINE_NUMBER (x
) != NOTE_INSN_BASIC_BLOCK
5913 || NOTE_BASIC_BLOCK (x
) != bb
)
5915 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
5922 /* Do checks for empty blocks here */
5929 if (GET_CODE (x
) == NOTE
5930 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
5932 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
5933 INSN_UID (x
), bb
->index
);
5940 if (GET_CODE (x
) == JUMP_INSN
5941 || GET_CODE (x
) == CODE_LABEL
5942 || GET_CODE (x
) == BARRIER
)
5944 error ("In basic block %d:", bb
->index
);
5945 fatal_insn ("Flow control insn inside a basic block", x
);
5956 if (!bb_info
[INSN_UID (x
)])
5958 switch (GET_CODE (x
))
5965 /* An addr_vec is placed outside any block block. */
5967 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
5968 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
5969 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
5974 /* But in any case, non-deletable labels can appear anywhere. */
5978 fatal_insn ("Insn outside basic block", x
);
5992 /* Functions to access an edge list with a vector representation.
5993 Enough data is kept such that given an index number, the
5994 pred and succ that edge reprsents can be determined, or
5995 given a pred and a succ, it's index number can be returned.
5996 This allows algorithms which comsume a lot of memory to
5997 represent the normally full matrix of edge (pred,succ) with a
5998 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
5999 wasted space in the client code due to sparse flow graphs. */
6001 /* This functions initializes the edge list. Basically the entire
6002 flowgraph is processed, and all edges are assigned a number,
6003 and the data structure is filed in. */
6007 struct edge_list
*elist
;
6013 block_count
= n_basic_blocks
+ 2; /* Include the entry and exit blocks. */
6017 /* Determine the number of edges in the flow graph by counting successor
6018 edges on each basic block. */
6019 for (x
= 0; x
< n_basic_blocks
; x
++)
6021 basic_block bb
= BASIC_BLOCK (x
);
6023 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
6026 /* Don't forget successors of the entry block. */
6027 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
6030 elist
= xmalloc (sizeof (struct edge_list
));
6031 elist
->num_blocks
= block_count
;
6032 elist
->num_edges
= num_edges
;
6033 elist
->index_to_edge
= xmalloc (sizeof (edge
) * num_edges
);
6037 /* Follow successors of the entry block, and register these edges. */
6038 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
6040 elist
->index_to_edge
[num_edges
] = e
;
6044 for (x
= 0; x
< n_basic_blocks
; x
++)
6046 basic_block bb
= BASIC_BLOCK (x
);
6048 /* Follow all successors of blocks, and register these edges. */
6049 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
6051 elist
->index_to_edge
[num_edges
] = e
;
6058 /* This function free's memory associated with an edge list. */
6060 free_edge_list (elist
)
6061 struct edge_list
*elist
;
6065 free (elist
->index_to_edge
);
6070 /* This function provides debug output showing an edge list. */
6072 print_edge_list (f
, elist
)
6074 struct edge_list
*elist
;
6077 fprintf(f
, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
6078 elist
->num_blocks
- 2, elist
->num_edges
);
6080 for (x
= 0; x
< elist
->num_edges
; x
++)
6082 fprintf (f
, " %-4d - edge(", x
);
6083 if (INDEX_EDGE_PRED_BB (elist
, x
) == ENTRY_BLOCK_PTR
)
6084 fprintf (f
,"entry,");
6086 fprintf (f
,"%d,", INDEX_EDGE_PRED_BB (elist
, x
)->index
);
6088 if (INDEX_EDGE_SUCC_BB (elist
, x
) == EXIT_BLOCK_PTR
)
6089 fprintf (f
,"exit)\n");
6091 fprintf (f
,"%d)\n", INDEX_EDGE_SUCC_BB (elist
, x
)->index
);
6095 /* This function provides an internal consistancy check of an edge list,
6096 verifying that all edges are present, and that there are no
6099 verify_edge_list (f
, elist
)
6101 struct edge_list
*elist
;
6103 int x
, pred
, succ
, index
;
6106 for (x
= 0; x
< n_basic_blocks
; x
++)
6108 basic_block bb
= BASIC_BLOCK (x
);
6110 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
6112 pred
= e
->src
->index
;
6113 succ
= e
->dest
->index
;
6114 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
6115 if (index
== EDGE_INDEX_NO_EDGE
)
6117 fprintf (f
, "*p* No index for edge from %d to %d\n",pred
, succ
);
6120 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
6121 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
6122 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
6123 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
6124 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
6125 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
6128 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
6130 pred
= e
->src
->index
;
6131 succ
= e
->dest
->index
;
6132 index
= EDGE_INDEX (elist
, e
->src
, e
->dest
);
6133 if (index
== EDGE_INDEX_NO_EDGE
)
6135 fprintf (f
, "*p* No index for edge from %d to %d\n",pred
, succ
);
6138 if (INDEX_EDGE_PRED_BB (elist
, index
)->index
!= pred
)
6139 fprintf (f
, "*p* Pred for index %d should be %d not %d\n",
6140 index
, pred
, INDEX_EDGE_PRED_BB (elist
, index
)->index
);
6141 if (INDEX_EDGE_SUCC_BB (elist
, index
)->index
!= succ
)
6142 fprintf (f
, "*p* Succ for index %d should be %d not %d\n",
6143 index
, succ
, INDEX_EDGE_SUCC_BB (elist
, index
)->index
);
6145 /* We've verified that all the edges are in the list, no lets make sure
6146 there are no spurious edges in the list. */
6148 for (pred
= 0 ; pred
< n_basic_blocks
; pred
++)
6149 for (succ
= 0 ; succ
< n_basic_blocks
; succ
++)
6151 basic_block p
= BASIC_BLOCK (pred
);
6152 basic_block s
= BASIC_BLOCK (succ
);
6156 for (e
= p
->succ
; e
; e
= e
->succ_next
)
6162 for (e
= s
->pred
; e
; e
= e
->pred_next
)
6168 if (EDGE_INDEX (elist
, BASIC_BLOCK (pred
), BASIC_BLOCK (succ
))
6169 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
6170 fprintf (f
, "*** Edge (%d, %d) appears to not have an index\n",
6172 if (EDGE_INDEX (elist
, BASIC_BLOCK (pred
), BASIC_BLOCK (succ
))
6173 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
6174 fprintf (f
, "*** Edge (%d, %d) has index %d, but there is no edge\n",
6175 pred
, succ
, EDGE_INDEX (elist
, BASIC_BLOCK (pred
),
6176 BASIC_BLOCK (succ
)));
6178 for (succ
= 0 ; succ
< n_basic_blocks
; succ
++)
6180 basic_block p
= ENTRY_BLOCK_PTR
;
6181 basic_block s
= BASIC_BLOCK (succ
);
6185 for (e
= p
->succ
; e
; e
= e
->succ_next
)
6191 for (e
= s
->pred
; e
; e
= e
->pred_next
)
6197 if (EDGE_INDEX (elist
, ENTRY_BLOCK_PTR
, BASIC_BLOCK (succ
))
6198 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
6199 fprintf (f
, "*** Edge (entry, %d) appears to not have an index\n",
6201 if (EDGE_INDEX (elist
, ENTRY_BLOCK_PTR
, BASIC_BLOCK (succ
))
6202 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
6203 fprintf (f
, "*** Edge (entry, %d) has index %d, but no edge exists\n",
6204 succ
, EDGE_INDEX (elist
, ENTRY_BLOCK_PTR
,
6205 BASIC_BLOCK (succ
)));
6207 for (pred
= 0 ; pred
< n_basic_blocks
; pred
++)
6209 basic_block p
= BASIC_BLOCK (pred
);
6210 basic_block s
= EXIT_BLOCK_PTR
;
6214 for (e
= p
->succ
; e
; e
= e
->succ_next
)
6220 for (e
= s
->pred
; e
; e
= e
->pred_next
)
6226 if (EDGE_INDEX (elist
, BASIC_BLOCK (pred
), EXIT_BLOCK_PTR
)
6227 == EDGE_INDEX_NO_EDGE
&& found_edge
!= 0)
6228 fprintf (f
, "*** Edge (%d, exit) appears to not have an index\n",
6230 if (EDGE_INDEX (elist
, BASIC_BLOCK (pred
), EXIT_BLOCK_PTR
)
6231 != EDGE_INDEX_NO_EDGE
&& found_edge
== 0)
6232 fprintf (f
, "*** Edge (%d, exit) has index %d, but no edge exists\n",
6233 pred
, EDGE_INDEX (elist
, BASIC_BLOCK (pred
),
6238 /* This routine will determine what, if any, edge there is between
6239 a specified predecessor and successor. */
6242 find_edge_index (edge_list
, pred
, succ
)
6243 struct edge_list
*edge_list
;
6244 basic_block pred
, succ
;
6247 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
6249 if (INDEX_EDGE_PRED_BB (edge_list
, x
) == pred
6250 && INDEX_EDGE_SUCC_BB (edge_list
, x
) == succ
)
6253 return (EDGE_INDEX_NO_EDGE
);
6256 /* This function will remove an edge from the flow graph. */
6261 edge last_pred
= NULL
;
6262 edge last_succ
= NULL
;
6264 basic_block src
, dest
;
6267 for (tmp
= src
->succ
; tmp
&& tmp
!= e
; tmp
= tmp
->succ_next
)
6273 last_succ
->succ_next
= e
->succ_next
;
6275 src
->succ
= e
->succ_next
;
6277 for (tmp
= dest
->pred
; tmp
&& tmp
!= e
; tmp
= tmp
->pred_next
)
6283 last_pred
->pred_next
= e
->pred_next
;
6285 dest
->pred
= e
->pred_next
;
6291 /* This routine will remove any fake successor edges for a basic block.
6292 When the edge is removed, it is also removed from whatever predecessor
6295 remove_fake_successors (bb
)
6299 for (e
= bb
->succ
; e
; )
6303 if ((tmp
->flags
& EDGE_FAKE
) == EDGE_FAKE
)
6308 /* This routine will remove all fake edges from the flow graph. If
6309 we remove all fake successors, it will automatically remove all
6310 fake predecessors. */
6312 remove_fake_edges ()
6316 for (x
= 0; x
< n_basic_blocks
; x
++)
6317 remove_fake_successors (BASIC_BLOCK (x
));
6319 /* We've handled all successors except the entry block's. */
6320 remove_fake_successors (ENTRY_BLOCK_PTR
);
6323 /* This functions will add a fake edge between any block which has no
6324 successors, and the exit block. Some data flow equations require these
6327 add_noreturn_fake_exit_edges ()
6331 for (x
= 0; x
< n_basic_blocks
; x
++)
6332 if (BASIC_BLOCK (x
)->succ
== NULL
)
6333 make_edge (NULL
, BASIC_BLOCK (x
), EXIT_BLOCK_PTR
, EDGE_FAKE
);
6336 /* Dump the list of basic blocks in the bitmap NODES. */
6338 flow_nodes_print (str
, nodes
, file
)
6340 const sbitmap nodes
;
6345 fprintf (file
, "%s { ", str
);
6346 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {fprintf (file
, "%d ", node
);});
6347 fputs ("}\n", file
);
6351 /* Dump the list of exiting edges in the array EDGES. */
6353 flow_exits_print (str
, edges
, num_edges
, file
)
6361 fprintf (file
, "%s { ", str
);
6362 for (i
= 0; i
< num_edges
; i
++)
6363 fprintf (file
, "%d->%d ", edges
[i
]->src
->index
, edges
[i
]->dest
->index
);
6364 fputs ("}\n", file
);
6368 /* Dump loop related CFG information. */
6370 flow_loops_cfg_dump (loops
, file
)
6371 const struct loops
*loops
;
6376 if (! loops
->num
|| ! file
|| ! loops
->cfg
.dom
)
6379 for (i
= 0; i
< n_basic_blocks
; i
++)
6383 fprintf (file
, ";; %d succs { ", i
);
6384 for (succ
= BASIC_BLOCK (i
)->succ
; succ
; succ
= succ
->succ_next
)
6385 fprintf (file
, "%d ", succ
->dest
->index
);
6386 flow_nodes_print ("} dom", loops
->cfg
.dom
[i
], file
);
6390 /* Dump the DFS node order. */
6391 if (loops
->cfg
.dfs_order
)
6393 fputs (";; DFS order: ", file
);
6394 for (i
= 0; i
< n_basic_blocks
; i
++)
6395 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
6401 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
6403 flow_loop_nested_p (outer
, loop
)
6407 return sbitmap_a_subset_b_p (loop
->nodes
, outer
->nodes
);
6411 /* Dump the loop information specified by LOOPS to the stream FILE. */
6413 flow_loops_dump (loops
, file
, verbose
)
6414 const struct loops
*loops
;
6421 num_loops
= loops
->num
;
6422 if (! num_loops
|| ! file
)
6425 fprintf (file
, ";; %d loops found\n", num_loops
);
6427 for (i
= 0; i
< num_loops
; i
++)
6429 struct loop
*loop
= &loops
->array
[i
];
6431 fprintf (file
, ";; loop %d (%d to %d):\n"
6432 ";; header %d, latch %d, pre-header %d,"
6433 " depth %d, level %d, outer %d\n",
6434 i
, INSN_UID (loop
->header
->head
), INSN_UID (loop
->latch
->end
),
6435 loop
->header
->index
, loop
->latch
->index
,
6436 loop
->pre_header
? loop
->pre_header
->index
: -1,
6437 loop
->depth
, loop
->level
,
6438 loop
->outer
? (loop
->outer
- loops
->array
) : -1);
6439 fprintf (file
, ";; %d", loop
->num_nodes
);
6440 flow_nodes_print (" nodes", loop
->nodes
, file
);
6441 fprintf (file
, ";; %d", loop
->num_exits
);
6442 flow_exits_print (" exits", loop
->exits
, loop
->num_exits
, file
);
6448 for (j
= 0; j
< i
; j
++)
6450 struct loop
*oloop
= &loops
->array
[j
];
6452 if (loop
->header
== oloop
->header
)
6457 smaller
= loop
->num_nodes
< oloop
->num_nodes
;
6459 /* If the union of LOOP and OLOOP is different than
6460 the larger of LOOP and OLOOP then LOOP and OLOOP
6461 must be disjoint. */
6462 disjoint
= ! flow_loop_nested_p (smaller
? loop
: oloop
,
6463 smaller
? oloop
: loop
);
6464 fprintf (file
, ";; loop header %d shared by loops %d, %d"
6466 loop
->header
->index
, i
, j
,
6467 disjoint
? "disjoint" : "nested");
6474 /* Print diagnostics to compare our concept of a loop with
6475 what the loop notes say. */
6476 if (GET_CODE (PREV_INSN (loop
->header
->head
)) != NOTE
6477 || NOTE_LINE_NUMBER (PREV_INSN (loop
->header
->head
))
6478 != NOTE_INSN_LOOP_BEG
)
6479 fprintf (file
, ";; No NOTE_INSN_LOOP_BEG at %d\n",
6480 INSN_UID (PREV_INSN (loop
->header
->head
)));
6481 if (GET_CODE (NEXT_INSN (loop
->latch
->end
)) != NOTE
6482 || NOTE_LINE_NUMBER (NEXT_INSN (loop
->latch
->end
))
6483 != NOTE_INSN_LOOP_END
)
6484 fprintf (file
, ";; No NOTE_INSN_LOOP_END at %d\n",
6485 INSN_UID (NEXT_INSN (loop
->latch
->end
)));
6490 flow_loops_cfg_dump (loops
, file
);
6494 /* Free all the memory allocated for LOOPS. */
6496 flow_loops_free (loops
)
6497 struct loops
*loops
;
6506 /* Free the loop descriptors. */
6507 for (i
= 0; i
< loops
->num
; i
++)
6509 struct loop
*loop
= &loops
->array
[i
];
6512 sbitmap_free (loop
->nodes
);
6516 free (loops
->array
);
6517 loops
->array
= NULL
;
6520 sbitmap_vector_free (loops
->cfg
.dom
);
6521 if (loops
->cfg
.dfs_order
)
6522 free (loops
->cfg
.dfs_order
);
6524 sbitmap_free (loops
->shared_headers
);
6529 /* Find the exits from the loop using the bitmap of loop nodes NODES
6530 and store in EXITS array. Return the number of exits from the
6533 flow_loop_exits_find (nodes
, exits
)
6534 const sbitmap nodes
;
6543 /* Check all nodes within the loop to see if there are any
6544 successors not in the loop. Note that a node may have multiple
6547 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {
6548 for (e
= BASIC_BLOCK (node
)->succ
; e
; e
= e
->succ_next
)
6550 basic_block dest
= e
->dest
;
6552 if (dest
== EXIT_BLOCK_PTR
|| ! TEST_BIT (nodes
, dest
->index
))
6560 *exits
= (edge
*) xmalloc (num_exits
* sizeof (edge
*));
6562 /* Store all exiting edges into an array. */
6564 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {
6565 for (e
= BASIC_BLOCK (node
)->succ
; e
; e
= e
->succ_next
)
6567 basic_block dest
= e
->dest
;
6569 if (dest
== EXIT_BLOCK_PTR
|| ! TEST_BIT (nodes
, dest
->index
))
6570 (*exits
)[num_exits
++] = e
;
6578 /* Find the nodes contained within the loop with header HEADER and
6579 latch LATCH and store in NODES. Return the number of nodes within
6582 flow_loop_nodes_find (header
, latch
, nodes
)
6591 stack
= (basic_block
*) xmalloc (n_basic_blocks
* sizeof (basic_block
));
6594 /* Start with only the loop header in the set of loop nodes. */
6595 sbitmap_zero (nodes
);
6596 SET_BIT (nodes
, header
->index
);
6599 /* Push the loop latch on to the stack. */
6600 if (! TEST_BIT (nodes
, latch
->index
))
6602 SET_BIT (nodes
, latch
->index
);
6604 stack
[sp
++] = latch
;
6613 for (e
= node
->pred
; e
; e
= e
->pred_next
)
6615 basic_block ancestor
= e
->src
;
6617 /* If each ancestor not marked as part of loop, add to set of
6618 loop nodes and push on to stack. */
6619 if (ancestor
!= ENTRY_BLOCK_PTR
6620 && ! TEST_BIT (nodes
, ancestor
->index
))
6622 SET_BIT (nodes
, ancestor
->index
);
6624 stack
[sp
++] = ancestor
;
6633 /* Compute the depth first search order and store in the array
6634 DFS_ORDER, marking the nodes visited in VISITED. Returns the
6635 number of nodes visited. */
6637 flow_depth_first_order_compute (dfs_order
)
6646 /* Allocate stack for back-tracking up CFG. */
6647 stack
= (edge
*) xmalloc (n_basic_blocks
* sizeof (edge
));
6650 /* Allocate bitmap to track nodes that have been visited. */
6651 visited
= sbitmap_alloc (n_basic_blocks
);
6653 /* None of the nodes in the CFG have been visited yet. */
6654 sbitmap_zero (visited
);
6656 /* Start with the first successor edge from the entry block. */
6657 e
= ENTRY_BLOCK_PTR
->succ
;
6660 basic_block src
= e
->src
;
6661 basic_block dest
= e
->dest
;
6663 /* Mark that we have visited this node. */
6664 if (src
!= ENTRY_BLOCK_PTR
)
6665 SET_BIT (visited
, src
->index
);
6667 /* If this node has not been visited before, push the current
6668 edge on to the stack and proceed with the first successor
6669 edge of this node. */
6670 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
)
6678 if (dest
!= EXIT_BLOCK_PTR
&& ! TEST_BIT (visited
, dest
->index
)
6681 /* DEST has no successors (for example, a non-returning
6682 function is called) so do not push the current edge
6683 but carry on with its next successor. */
6684 dfs_order
[dest
->index
] = n_basic_blocks
- ++dfsnum
;
6685 SET_BIT (visited
, dest
->index
);
6688 while (! e
->succ_next
&& src
!= ENTRY_BLOCK_PTR
)
6690 dfs_order
[src
->index
] = n_basic_blocks
- ++dfsnum
;
6692 /* Pop edge off stack. */
6700 sbitmap_free (visited
);
6702 /* The number of nodes visited should not be greater than
6704 if (dfsnum
> n_basic_blocks
)
6707 /* There are some nodes left in the CFG that are unreachable. */
6708 if (dfsnum
< n_basic_blocks
)
6714 /* Return the block for the pre-header of the loop with header
6715 HEADER where DOM specifies the dominator information. Return NULL if
6716 there is no pre-header. */
6718 flow_loop_pre_header_find (header
, dom
)
6722 basic_block pre_header
;
6725 /* If block p is a predecessor of the header and is the only block
6726 that the header does not dominate, then it is the pre-header. */
6728 for (e
= header
->pred
; e
; e
= e
->pred_next
)
6730 basic_block node
= e
->src
;
6732 if (node
!= ENTRY_BLOCK_PTR
6733 && ! TEST_BIT (dom
[node
->index
], header
->index
))
6735 if (pre_header
== NULL
)
6739 /* There are multiple edges into the header from outside
6740 the loop so there is no pre-header block. */
6750 /* Add LOOP to the loop hierarchy tree so that it is a sibling or a
6751 descendant of ROOT. */
6753 flow_loop_tree_node_add (root
, loop
)
6762 for (outer
= root
; outer
; outer
= outer
->next
)
6764 if (flow_loop_nested_p (outer
, loop
))
6768 /* Add LOOP as a sibling or descendent of OUTER->INNER. */
6769 flow_loop_tree_node_add (outer
->inner
, loop
);
6773 /* Add LOOP as child of OUTER. */
6774 outer
->inner
= loop
;
6775 loop
->outer
= outer
;
6781 /* Add LOOP as a sibling of ROOT. */
6782 loop
->next
= root
->next
;
6784 loop
->outer
= root
->outer
;
6788 /* Build the loop hierarchy tree for LOOPS. */
6790 flow_loops_tree_build (loops
)
6791 struct loops
*loops
;
6796 num_loops
= loops
->num
;
6800 /* Root the loop hierarchy tree with the first loop found.
6801 Since we used a depth first search this should be the
6803 loops
->tree
= &loops
->array
[0];
6804 loops
->tree
->outer
= loops
->tree
->inner
= loops
->tree
->next
= NULL
;
6806 /* Add the remaining loops to the tree. */
6807 for (i
= 1; i
< num_loops
; i
++)
6808 flow_loop_tree_node_add (loops
->tree
, &loops
->array
[i
]);
6812 /* Helper function to compute loop nesting depth and enclosed loop level
6813 for the natural loop specified by LOOP at the loop depth DEPTH.
6814 Returns the loop level. */
6816 flow_loop_level_compute (loop
, depth
)
6826 /* Traverse loop tree assigning depth and computing level as the
6827 maximum level of all the inner loops of this loop. The loop
6828 level is equivalent to the height of the loop in the loop tree
6829 and corresponds to the number of enclosed loop levels. */
6830 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
6834 ilevel
= flow_loop_level_compute (inner
, depth
+ 1) + 1;
6839 loop
->level
= level
;
6840 loop
->depth
= depth
;
6845 /* Compute the loop nesting depth and enclosed loop level for the loop
6846 hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
6849 flow_loops_level_compute (loops
)
6850 struct loops
*loops
;
6852 return flow_loop_level_compute (loops
->tree
, 0);
6856 /* Find all the natural loops in the function and save in LOOPS structure.
6857 Return the number of natural loops found. */
6859 flow_loops_find (loops
)
6860 struct loops
*loops
;
6871 loops
->array
= NULL
;
6875 /* Taking care of this degenerate case makes the rest of
6876 this code simpler. */
6877 if (n_basic_blocks
== 0)
6880 /* Compute the dominators. */
6881 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
6882 compute_flow_dominators (dom
, NULL
);
6884 /* Count the number of loop edges (back edges). This should be the
6885 same as the number of natural loops. */
6887 for (b
= 0; b
< n_basic_blocks
; b
++)
6889 for (e
= BASIC_BLOCK (b
)->pred
; e
; e
= e
->pred_next
)
6891 basic_block latch
= e
->src
;
6893 /* Look for back edges where a predecessor is dominated
6894 by this block. A natural loop has a single entry
6895 node (header) that dominates all the nodes in the
6896 loop. It also has single back edge to the header
6897 from a latch node. Note that multiple natural loops
6898 may share the same header. */
6899 if (latch
!= ENTRY_BLOCK_PTR
&& TEST_BIT (dom
[latch
->index
], b
))
6906 /* Compute depth first search order of the CFG so that outer
6907 natural loops will be found before inner natural loops. */
6908 dfs_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
6909 flow_depth_first_order_compute (dfs_order
);
6911 /* Allocate loop structures. */
6912 loops
->array
= (struct loop
*)
6913 xcalloc (num_loops
, sizeof (struct loop
));
6915 headers
= sbitmap_alloc (n_basic_blocks
);
6916 sbitmap_zero (headers
);
6918 loops
->shared_headers
= sbitmap_alloc (n_basic_blocks
);
6919 sbitmap_zero (loops
->shared_headers
);
6921 /* Find and record information about all the natural loops
6924 for (b
= 0; b
< n_basic_blocks
; b
++)
6928 /* Search the nodes of the CFG in DFS order that we can find
6929 outer loops first. */
6930 header
= BASIC_BLOCK (dfs_order
[b
]);
6932 /* Look for all the possible latch blocks for this header. */
6933 for (e
= header
->pred
; e
; e
= e
->pred_next
)
6935 basic_block latch
= e
->src
;
6937 /* Look for back edges where a predecessor is dominated
6938 by this block. A natural loop has a single entry
6939 node (header) that dominates all the nodes in the
6940 loop. It also has single back edge to the header
6941 from a latch node. Note that multiple natural loops
6942 may share the same header. */
6943 if (latch
!= ENTRY_BLOCK_PTR
6944 && TEST_BIT (dom
[latch
->index
], header
->index
))
6948 loop
= loops
->array
+ num_loops
;
6950 loop
->header
= header
;
6951 loop
->latch
= latch
;
6953 /* Keep track of blocks that are loop headers so
6954 that we can tell which loops should be merged. */
6955 if (TEST_BIT (headers
, header
->index
))
6956 SET_BIT (loops
->shared_headers
, header
->index
);
6957 SET_BIT (headers
, header
->index
);
6959 /* Find nodes contained within the loop. */
6960 loop
->nodes
= sbitmap_alloc (n_basic_blocks
);
6962 flow_loop_nodes_find (header
, latch
, loop
->nodes
);
6964 /* Find edges which exit the loop. Note that a node
6965 may have several exit edges. */
6967 = flow_loop_exits_find (loop
->nodes
, &loop
->exits
);
6969 /* Look to see if the loop has a pre-header node. */
6971 = flow_loop_pre_header_find (header
, dom
);
6978 /* Natural loops with shared headers may either be disjoint or
6979 nested. Disjoint loops with shared headers cannot be inner
6980 loops and should be merged. For now just mark loops that share
6982 for (i
= 0; i
< num_loops
; i
++)
6983 if (TEST_BIT (loops
->shared_headers
, loops
->array
[i
].header
->index
))
6984 loops
->array
[i
].shared
= 1;
6986 sbitmap_free (headers
);
6989 loops
->num
= num_loops
;
6991 /* Save CFG derived information to avoid recomputing it. */
6992 loops
->cfg
.dom
= dom
;
6993 loops
->cfg
.dfs_order
= dfs_order
;
6995 /* Build the loop hierarchy tree. */
6996 flow_loops_tree_build (loops
);
6998 /* Assign the loop nesting depth and enclosed loop level for each
7000 flow_loops_level_compute (loops
);
7006 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
7008 flow_loop_outside_edge_p (loop
, e
)
7009 const struct loop
*loop
;
7012 if (e
->dest
!= loop
->header
)
7014 return (e
->src
== ENTRY_BLOCK_PTR
)
7015 || ! TEST_BIT (loop
->nodes
, e
->src
->index
);