| blob | 8135e020ec313517c8725e659fe55a67704e0f53 |
1 /* Data flow analysis for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* This file contains the data flow analysis pass of the compiler. It
24 computes data flow information which tells combine_instructions
25 which insns to consider combining and controls register allocation.
27 Additional data flow information that is too bulky to record is
28 generated during the analysis, and is used at that time to create
29 autoincrement and autodecrement addressing.
31 The first step is dividing the function into basic blocks.
32 find_basic_blocks does this. Then life_analysis determines
33 where each register is live and where it is dead.
35 ** find_basic_blocks **
37 find_basic_blocks divides the current function's rtl into basic
38 blocks and constructs the CFG. The blocks are recorded in the
39 basic_block_info array; the CFG exists in the edge structures
40 referenced by the blocks.
42 find_basic_blocks also finds any unreachable loops and deletes them.
44 ** life_analysis **
46 life_analysis is called immediately after find_basic_blocks.
47 It uses the basic block information to determine where each
48 hard or pseudo register is live.
50 ** live-register info **
52 The information about where each register is live is in two parts:
53 the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
55 basic_block->global_live_at_start has an element for each basic
56 block, and the element is a bit-vector with a bit for each hard or
57 pseudo register. The bit is 1 if the register is live at the
58 beginning of the basic block.
60 Two types of elements can be added to an insn's REG_NOTES.
61 A REG_DEAD note is added to an insn's REG_NOTES for any register
62 that meets both of two conditions: The value in the register is not
63 needed in subsequent insns and the insn does not replace the value in
64 the register (in the case of multi-word hard registers, the value in
65 each register must be replaced by the insn to avoid a REG_DEAD note).
67 In the vast majority of cases, an object in a REG_DEAD note will be
68 used somewhere in the insn. The (rare) exception to this is if an
69 insn uses a multi-word hard register and only some of the registers are
70 needed in subsequent insns. In that case, REG_DEAD notes will be
71 provided for those hard registers that are not subsequently needed.
72 Partial REG_DEAD notes of this type do not occur when an insn sets
73 only some of the hard registers used in such a multi-word operand;
74 omitting REG_DEAD notes for objects stored in an insn is optional and
75 the desire to do so does not justify the complexity of the partial
76 REG_DEAD notes.
78 REG_UNUSED notes are added for each register that is set by the insn
79 but is unused subsequently (if every register set by the insn is unused
80 and the insn does not reference memory or have some other side-effect,
81 the insn is deleted instead). If only part of a multi-word hard
82 register is used in a subsequent insn, REG_UNUSED notes are made for
83 the parts that will not be used.
85 To determine which registers are live after any insn, one can
86 start from the beginning of the basic block and scan insns, noting
87 which registers are set by each insn and which die there.
89 ** Other actions of life_analysis **
91 life_analysis sets up the LOG_LINKS fields of insns because the
92 information needed to do so is readily available.
94 life_analysis deletes insns whose only effect is to store a value
95 that is never used.
97 life_analysis notices cases where a reference to a register as
98 a memory address can be combined with a preceding or following
99 incrementation or decrementation of the register. The separate
100 instruction to increment or decrement is deleted and the address
101 is changed to a POST_INC or similar rtx.
103 Each time an incrementing or decrementing address is created,
104 a REG_INC element is added to the insn's REG_NOTES list.
106 life_analysis fills in certain vectors containing information about
107 register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
108 REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
110 life_analysis sets current_function_sp_is_unchanging if the function
111 doesn't modify the stack pointer. */
113 /* TODO:
115 Split out from life_analysis:
116 - local property discovery (bb->local_live, bb->local_set)
117 - global property computation
118 - log links creation
119 - pre/post modify transformation
120 */
121 \f
143 #define obstack_chunk_alloc xmalloc
144 #define obstack_chunk_free free
147 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
148 the stack pointer does not matter. The value is tested only in
149 functions that have frame pointers.
150 No definition is equivalent to always zero. */
151 #ifndef EXIT_IGNORE_STACK
152 #define EXIT_IGNORE_STACK 0
153 #endif
155 #ifndef HAVE_epilogue
156 #define HAVE_epilogue 0
157 #endif
158 #ifndef HAVE_prologue
159 #define HAVE_prologue 0
160 #endif
161 #ifndef HAVE_sibcall_epilogue
162 #define HAVE_sibcall_epilogue 0
163 #endif
165 /* The contents of the current function definition are allocated
166 in this obstack, and all are freed at the end of the function.
167 For top-level functions, this is temporary_obstack.
168 Separate obstacks are made for nested functions. */
172 /* Number of basic blocks in the current function. */
176 /* Number of edges in the current function. */
180 /* The basic block array. */
182 varray_type basic_block_info;
184 /* The special entry and exit blocks. */
199 },
200 {
213 }
214 };
216 /* Nonzero if the second flow pass has completed. */
219 /* Maximum register number used in this function, plus one. */
223 /* Indexed by n, giving various register information */
225 varray_type reg_n_info;
227 /* Size of a regset for the current function,
228 in (1) bytes and (2) elements. */
233 /* Regset of regs live when calls to `setjmp'-like functions happen. */
234 /* ??? Does this exist only for the setjmp-clobbered warning message? */
236 regset regs_live_at_setjmp;
238 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
239 that have to go in the same hard reg.
240 The first two regs in the list are a pair, and the next two
241 are another pair, etc. */
242 rtx regs_may_share;
244 /* Set of registers that may be eliminable. These are handled specially
245 in updating regs_ever_live. */
249 /* The basic block structure for every insn, indexed by uid. */
251 varray_type basic_block_for_insn;
253 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
254 /* ??? Should probably be using LABEL_NUSES instead. It would take a
255 bit of surgery to be able to use or co-opt the routines in jump. */
260 /* Holds information for tracking conditional register life information. */
261 struct reg_cond_life_info
262 {
263 /* An EXPR_LIST of conditions under which a register is dead. */
264 rtx condition;
266 /* ??? Could store mask of bytes that are dead, so that we could finally
267 track lifetimes of multi-word registers accessed via subregs. */
268 };
270 /* For use in communicating between propagate_block and its subroutines.
271 Holds all information needed to compute life and def-use information. */
273 struct propagate_block_info
274 {
275 /* The basic block we're considering. */
276 basic_block bb;
278 /* Bit N is set if register N is conditionally or unconditionally live. */
279 regset reg_live;
281 /* Bit N is set if register N is set this insn. */
282 regset new_set;
284 /* Element N is the next insn that uses (hard or pseudo) register N
285 within the current basic block; or zero, if there is no such insn. */
288 /* Contains a list of all the MEMs we are tracking for dead store
289 elimination. */
290 rtx mem_set_list;
292 /* If non-null, record the set of registers set in the basic block. */
293 regset local_set;
295 #ifdef HAVE_conditional_execution
296 /* Indexed by register number, holds a reg_cond_life_info for each
297 register that is not unconditionally live or dead. */
298 splay_tree reg_cond_dead;
300 /* Bit N is set if register N is in an expression in reg_cond_dead. */
301 regset reg_cond_reg;
302 #endif
304 /* Non-zero if the value of CC0 is live. */
307 /* Flags controling the set of information propagate_block collects. */
309 };
311 /* Forward declarations */
334 basic_block));
336 basic_block));
363 #ifdef HAVE_conditional_execution
373 #endif
374 #ifdef AUTO_INC_DEC
378 rtx));
380 #endif
390 rtx));
404 \f
405 /* Find basic blocks of the current function.
406 F is the first insn of the function and NREGS the number of register
407 numbers in use. */
409 void
411 rtx f;
414 {
417 /* Flush out existing data. */
419 {
424 /* Clear bb->aux on all extant basic blocks. We'll use this as a
425 tag for reuse during create_basic_block, just in case some pass
426 copies around basic block notes improperly. */
431 }
435 /* Size the basic block table. The actual structures will be allocated
436 by find_basic_blocks_1, since we want to keep the structure pointers
437 stable across calls to find_basic_blocks. */
438 /* ??? This whole issue would be much simpler if we called find_basic_blocks
439 exactly once, and thereafter we don't have a single long chain of
440 instructions at all until close to the end of compilation when we
441 actually lay them out. */
447 /* Record the block to which an insn belongs. */
448 /* ??? This should be done another way, by which (perhaps) a label is
449 tagged directly with the basic block that it starts. It is used for
450 more than that currently, but IMO that is the only valid use. */
453 #ifdef AUTO_INC_DEC
454 /* Leave space for insns life_analysis makes in some cases for auto-inc.
455 These cases are rare, so we don't need too much space. */
457 #endif
461 /* Discover the edges of our cfg. */
465 /* Do very simple cleanup now, for the benefit of code that runs between
466 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
471 #ifdef ENABLE_CHECKING
473 #endif
474 }
476 /* Count the basic blocks of the function. */
478 static int
480 rtx f;
481 {
490 {
498 count++;
500 /* Record whether this call created an edge. */
502 {
508 /* If there is an EH region or rethrow, we have an edge. */
513 /* If there is a nonlocal goto label and the specified
514 region number isn't -1, we have an edge. (0 means
515 no throw, but might have a nonlocal goto). */
517 }
525 }
527 /* The rest of the compiler works a bit smoother when we don't have to
528 check for the edge case of do-nothing functions with no basic blocks. */
530 {
533 }
536 }
538 /* Scan a list of insns for labels referrred to other than by jumps.
539 This is used to scan the alternatives of a call placeholder. */
541 rtx f;
542 rtx lvl;
543 {
544 rtx insn;
548 {
549 rtx note;
551 /* Make a list of all labels referred to other than by jumps
552 (which just don't have the REG_LABEL notes).
554 Make a special exception for labels followed by an ADDR*VEC,
555 as this would be a part of the tablejump setup code.
557 Make a special exception for the eh_return_stub_label, which
558 we know isn't part of any otherwise visible control flow. */
562 {
566 ;
571 ;
573 ;
574 else
576 }
577 }
580 }
582 /* Find all basic blocks of the function whose first insn is F.
584 Collect and return a list of labels whose addresses are taken. This
585 will be used in make_edges for use with computed gotos. */
587 static void
589 rtx f;
590 {
600 /* We process the instructions in a slightly different way than we did
601 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
602 closed out the previous block, so that it gets attached at the proper
603 place. Since this form should be equivalent to the previous,
604 count_basic_blocks continues to use the old form as a check. */
607 {
613 {
615 {
618 /* Keep a LIFO list of the currently active exception notes. */
622 {
627 }
629 /* Look for basic block notes with which to keep the
630 basic_block_info pointers stable. Unthread the note now;
631 we'll put it back at the right place in create_basic_block.
632 Or not at all if we've already found a note in this block. */
634 {
637 else
639 }
641 }
644 /* A basic block starts at a label. If we've closed one off due
645 to a barrier or some such, no need to do it again. */
647 {
648 /* While we now have edge lists with which other portions of
649 the compiler might determine a call ending a basic block
650 does not imply an abnormal edge, it will be a bit before
651 everything can be updated. So continue to emit a noop at
652 the end of such a block. */
654 {
657 }
661 }
667 /* A basic block ends at a jump. */
670 else
671 {
672 /* ??? Make a special check for table jumps. The way this
673 happens is truly and amazingly gross. We are about to
674 create a basic block that contains just a code label and
675 an addr*vec jump insn. Worse, an addr_diff_vec creates
676 its own natural loop.
678 Prevent this bit of brain damage, pasting things together
679 correctly in make_edges.
681 The correct solution involves emitting the table directly
682 on the tablejump instruction as a note, or JUMP_LABEL. */
686 {
688 n_basic_blocks--;
690 }
691 }
696 /* A basic block ends at a barrier. It may be that an unconditional
697 jump already closed the basic block -- no need to do it again. */
701 /* While we now have edge lists with which other portions of the
702 compiler might determine a call ending a basic block does not
703 imply an abnormal edge, it will be a bit before everything can
704 be updated. So continue to emit a noop at the end of such a
705 block. */
707 {
710 }
714 {
715 /* Record whether this call created an edge. */
721 {
722 /* Scan each of the alternatives for label refs. */
726 /* Record its tail recursion label, if any. */
729 }
731 /* If there is an EH region or rethrow, we have an edge. */
736 /* If there is a nonlocal goto label and the specified
737 region number isn't -1, we have an edge. (0 means
738 no throw, but might have a nonlocal goto). */
741 /* A basic block ends at a call that can either throw or
742 do a non-local goto. */
744 {
745 new_bb_inclusive:
750 new_bb_exclusive:
755 }
756 }
757 /* FALLTHRU */
761 {
765 }
767 }
770 {
771 rtx note;
773 /* Make a list of all labels referred to other than by jumps
774 (which just don't have the REG_LABEL notes).
776 Make a special exception for labels followed by an ADDR*VEC,
777 as this would be a part of the tablejump setup code.
779 Make a special exception for the eh_return_stub_label, which
780 we know isn't part of any otherwise visible control flow. */
784 {
788 ;
793 ;
795 ;
796 else
798 }
799 }
800 }
812 }
814 /* Tidy the CFG by deleting unreachable code and whatnot. */
816 void
818 rtx f;
819 {
826 /* Kill the data we won't maintain. */
829 }
831 /* Create a new basic block consisting of the instructions between
832 HEAD and END inclusive. Reuses the note and basic block struct
833 in BB_NOTE, if any. */
835 void
839 {
840 basic_block bb;
846 {
847 /* If we found an existing note, thread it back onto the chain. */
849 rtx after;
853 else
854 {
857 }
861 }
862 else
863 {
864 /* Otherwise we must create a note and a basic block structure.
865 Since we allow basic block structs in rtl, give the struct
866 the same lifetime by allocating it off the function obstack
867 rather than using malloc. */
874 else
875 {
878 }
880 }
882 /* Always include the bb note in the block. */
891 /* Tag the block so that we know it has been used when considering
892 other basic block notes. */
894 }
895 \f
896 /* Records the basic block struct in BB_FOR_INSN, for every instruction
897 indexed by INSN_UID. MAX is the size of the array. */
899 void
902 {
910 {
917 {
924 }
925 }
926 }
928 /* Free the memory associated with the edge structures. */
930 static void
932 {
937 {
941 {
944 }
948 }
951 {
954 }
960 }
962 /* Identify the edges between basic blocks.
964 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
965 that are otherwise unreachable may be reachable with a non-local goto.
967 BB_EH_END is an array indexed by basic block number in which we record
968 the list of exception regions active at the end of the basic block. */
970 static void
972 rtx label_value_list;
973 {
978 /* Assume no computed jump; revise as we create edges. */
981 /* Heavy use of computed goto in machine-generated code can lead to
982 nearly fully-connected CFGs. In that case we spend a significant
983 amount of time searching the edge lists for duplicates. */
985 {
988 }
990 /* By nature of the way these get numbered, block 0 is always the entry. */
994 {
1000 /* Examine the last instruction of the block, and discover the
1001 ways we can leave the block. */
1006 /* A branch. */
1008 {
1009 rtx tmp;
1011 /* ??? Recognize a tablejump and do the right thing. */
1017 {
1018 rtvec vec;
1023 else
1030 /* Some targets (eg, ARM) emit a conditional jump that also
1031 contains the out-of-range target. Scan for these and
1032 add an edge if necessary. */
1040 #ifdef CASE_DROPS_THROUGH
1041 /* Silly VAXen. The ADDR_VEC is going to be in the way of
1042 us naturally detecting fallthru into the next block. */
1044 #endif
1045 }
1047 /* If this is a computed jump, then mark it as reaching
1048 everything on the label_value_list and forced_labels list. */
1050 {
1058 }
1060 /* Returns create an exit out. */
1064 /* Otherwise, we have a plain conditional or unconditional jump. */
1065 else
1066 {
1070 }
1071 }
1073 /* If this is a sibling call insn, then this is in effect a
1074 combined call and return, and so we need an edge to the
1075 exit block. No need to worry about EH edges, since we
1076 wouldn't have created the sibling call in the first place. */
1081 else
1083 /* If this is a CALL_INSN, then mark it as reaching the active EH
1084 handler for this CALL_INSN. If we're handling asynchronous
1085 exceptions then any insn can reach any of the active handlers.
1087 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
1090 {
1091 /* Add any appropriate EH edges. We do this unconditionally
1092 since there may be a REG_EH_REGION or REG_EH_RETHROW note
1093 on the call, and this needn't be within an EH region. */
1096 /* If we have asynchronous exceptions, do the same for *all*
1097 exception regions active in the block. */
1100 {
1109 {
1113 }
1114 }
1117 {
1118 /* ??? This could be made smarter: in some cases it's possible
1119 to tell that certain calls will not do a nonlocal goto.
1121 For example, if the nested functions that do the nonlocal
1122 gotos do not have their addresses taken, then only calls to
1123 those functions or to other nested functions that use them
1124 could possibly do nonlocal gotos. */
1125 /* We do know that a REG_EH_REGION note with a value less
1126 than 0 is guaranteed not to perform a non-local goto. */
1132 }
1133 }
1135 /* We know something about the structure of the function __throw in
1136 libgcc2.c. It is the only function that ever contains eh_stub
1137 labels. It modifies its return address so that the last block
1138 returns to one of the eh_stub labels within it. So we have to
1139 make additional edges in the flow graph. */
1143 /* Find out if we can drop through to the next block. */
1148 {
1154 }
1155 }
1160 }
1162 /* Create an edge between two basic blocks. FLAGS are auxiliary information
1163 about the edge that is accumulated between calls. */
1165 void
1170 {
1172 edge e;
1174 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1175 many edges to them, and we didn't allocate memory for it. */
1176 use_edge_cache = (edge_cache
1180 /* Make sure we don't add duplicate edges. */
1184 {
1187 }
1190 n_edges++;
1203 }
1205 /* Create an edge from a basic block to a label. */
1207 static void
1210 basic_block src;
1211 rtx label;
1213 {
1217 /* If the label was never emitted, this insn is junk, but avoid a
1218 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
1219 as a result of a syntax error and a diagnostic has already been
1220 printed. */
1226 }
1228 /* Create the edges generated by INSN in REGION. */
1230 static void
1234 basic_block src;
1235 rtx insn;
1237 {
1244 {
1247 }
1248 }
1250 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1251 dangerous if we intend to move basic blocks around. Move such notes
1252 into the following block. */
1254 static void
1256 {
1265 {
1270 {
1275 {
1276 /* Unlink from the insn chain. */
1280 /* Queue it. */
1283 }
1284 }
1289 /* Find where to insert these things. */
1295 {
1299 }
1300 }
1301 }
1303 /* Recompute eh_beg/eh_end for each basic block. */
1305 static void
1307 rtx f;
1308 {
1314 {
1319 {
1324 {
1328 }
1329 }
1332 {
1338 }
1339 }
1340 }
1342 /* Identify critical edges and set the bits appropriately. */
1344 static void
1346 {
1348 basic_block bb;
1350 /* We begin with the entry block. This is not terribly important now,
1351 but could be if a front end (Fortran) implemented alternate entry
1352 points. */
1357 {
1358 edge e;
1360 /* (1) Critical edges must have a source with multiple successors. */
1362 {
1364 {
1365 /* (2) Critical edges must have a destination with multiple
1366 predecessors. Note that we know there is at least one
1367 predecessor -- the edge we followed to get here. */
1370 else
1372 }
1373 }
1374 else
1375 {
1378 }
1383 }
1384 }
1385 \f
1386 /* Split a (typically critical) edge. Return the new block.
1387 Abort on abnormal edges.
1389 ??? The code generally expects to be called on critical edges.
1390 The case of a block ending in an unconditional jump to a
1391 block with multiple predecessors is not handled optimally. */
1393 basic_block
1395 edge edge_in;
1396 {
1398 edge edge_out;
1399 rtx bb_note;
1402 /* Abnormal edges cannot be split. */
1409 /* Remove the existing edge from the destination's pred list. */
1410 {
1416 }
1418 /* Create the new structures. */
1421 n_edges++;
1425 /* ??? This info is likely going to be out of date very soon. */
1427 {
1432 }
1434 /* Wire them up. */
1452 /* Tricky case -- if there existed a fallthru into the successor
1453 (and we're not it) we must add a new unconditional jump around
1454 the new block we're actually interested in.
1456 Further, if that edge is critical, this means a second new basic
1457 block must be created to hold it. In order to simplify correct
1458 insn placement, do this before we touch the existing basic block
1459 ordering for the block we were really wanting. */
1461 {
1462 edge e;
1468 {
1469 basic_block jump_block;
1470 rtx pos;
1474 {
1475 /* Non critical -- we can simply add a jump to the end
1476 of the existing predecessor. */
1478 }
1479 else
1480 {
1481 /* We need a new block to hold the jump. The simplest
1482 way to do the bulk of the work here is to recursively
1483 call ourselves. */
1486 }
1488 /* Now add the jump insn ... */
1496 /* ... let jump know that label is in use, ... */
1500 /* ... and clear fallthru on the outgoing edge. */
1503 /* Continue splitting the interesting edge. */
1504 }
1505 }
1507 /* Place the new block just in front of the successor. */
1511 else
1514 {
1518 }
1522 /* Create the basic block note.
1524 Where we place the note can have a noticable impact on the generated
1525 code. Consider this cfg:
1528 E
1529 |
1530 0
1531 / \
1532 +->1-->2--->E
1533 | |
1534 +--+
1536 If we need to insert an insn on the edge from block 0 to block 1,
1537 we want to ensure the instructions we insert are outside of any
1538 loop notes that physically sit between block 0 and block 1. Otherwise
1539 we confuse the loop optimizer into thinking the loop is a phony. */
1548 else
1553 /* Not quite simple -- for non-fallthru edges, we must adjust the
1554 predecessor's jump instruction to target our new block. */
1556 {
1564 /* ??? Recognize a tablejump and adjust all matching cases. */
1570 {
1571 rtvec vec;
1576 else
1581 {
1585 }
1587 /* Handle casesi dispatch insns */
1593 {
1595 new_label);
1598 }
1599 }
1600 else
1601 {
1602 /* This would have indicated an abnormal edge. */
1606 /* A return instruction can't be redirected. */
1610 /* If the insn doesn't go where we think, we're confused. */
1615 }
1619 }
1622 }
1624 /* Queue instructions for insertion on an edge between two basic blocks.
1625 The new instructions and basic blocks (if any) will not appear in the
1626 CFG until commit_edge_insertions is called. */
1628 void
1630 rtx pattern;
1631 edge e;
1632 {
1633 /* We cannot insert instructions on an abnormal critical edge.
1634 It will be easier to find the culprit if we die now. */
1641 else
1648 }
1650 /* Update the CFG for the instructions queued on edge E. */
1652 static void
1654 edge e;
1655 {
1657 basic_block bb;
1659 /* Pull the insns off the edge now since the edge might go away. */
1663 /* Figure out where to put these things. If the destination has
1664 one predecessor, insert there. Except for the exit block. */
1667 {
1670 /* Get the location correct wrt a code label, and "nice" wrt
1671 a basic block note, and before everything else. */
1680 else
1682 }
1684 /* If the source has one successor and the edge is not abnormal,
1685 insert there. Except for the entry block. */
1689 {
1691 /* It is possible to have a non-simple jump here. Consider a target
1692 where some forms of unconditional jumps clobber a register. This
1693 happens on the fr30 for example.
1695 We know this block has a single successor, so we can just emit
1696 the queued insns before the jump. */
1698 {
1700 }
1701 else
1702 {
1703 /* We'd better be fallthru, or we've lost track of what's what. */
1708 }
1709 }
1711 /* Otherwise we must split the edge. */
1712 else
1713 {
1716 }
1718 /* Now that we've found the spot, do the insertion. */
1720 /* Set the new block number for these insns, if structure is allocated. */
1722 {
1723 rtx i;
1726 }
1729 {
1735 }
1736 else
1737 {
1741 }
1744 {
1745 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1746 This is not currently a problem because this only happens
1747 for the (single) epilogue, which already has a fallthru edge
1748 to EXIT. */
1762 }
1765 }
1767 /* Update the CFG for all queued instructions. */
1769 void
1771 {
1773 basic_block bb;
1775 #ifdef ENABLE_CHECKING
1777 #endif
1782 {
1786 {
1790 }
1795 }
1796 }
1797 \f
1798 /* Delete all unreachable basic blocks. */
1800 static void
1802 {
1805 edge e;
1811 /* Use basic_block->aux as a marker. Clear them all. */
1816 /* Add our starting points to the worklist. Almost always there will
1817 be only one. It isn't inconcievable that we might one day directly
1818 support Fortran alternate entry points. */
1821 {
1824 /* Mark the block with a handy non-null value. */
1826 }
1828 /* Iterate: find everything reachable from what we've already seen. */
1831 {
1836 {
1839 }
1840 }
1842 /* Delete all unreachable basic blocks. Count down so that we don't
1843 interfere with the block renumbering that happens in flow_delete_block. */
1848 {
1852 /* This block was found. Tidy up the mark. */
1854 else
1856 }
1860 /* If we deleted an exception handler, we may have EH region begin/end
1861 blocks to remove as well. */
1866 }
1868 /* Find EH regions for which there is no longer a handler, and delete them. */
1870 static void
1872 {
1873 rtx insn;
1879 {
1882 {
1884 /* A NULL handler indicates a region is no longer needed,
1885 as long as its rethrow label isn't used. */
1887 {
1890 }
1891 }
1892 }
1893 }
1895 /* Return true if NOTE is not one of the ones that must be kept paired,
1896 so that we may simply delete them. */
1898 static int
1900 rtx note;
1901 {
1904 }
1906 /* Unlink a chain of insns between START and FINISH, leaving notes
1907 that must be paired. */
1909 void
1912 {
1913 /* Unchain the insns one by one. It would be quicker to delete all
1914 of these with a single unchaining, rather than one at a time, but
1915 we need to keep the NOTE's. */
1917 rtx next;
1920 {
1923 ;
1926 {
1931 }
1932 else
1938 }
1939 }
1941 /* Delete the insns in a (non-live) block. We physically delete every
1942 non-deleted-note insn, and update the flow graph appropriately.
1944 Return nonzero if we deleted an exception handler. */
1946 /* ??? Preserving all such notes strikes me as wrong. It would be nice
1947 to post-process the stream to remove empty blocks, loops, ranges, etc. */
1949 int
1951 basic_block b;
1952 {
1956 /* If the head of this block is a CODE_LABEL, then it might be the
1957 label for an exception handler which can't be reached.
1959 We need to remove the label from the exception_handler_label list
1960 and remove the associated NOTE_INSN_EH_REGION_BEG and
1961 NOTE_INSN_EH_REGION_END notes. */
1968 {
1972 {
1974 {
1975 /* Found a match, splice this label out of the EH label list. */
1980 /* Remove the handler from all regions */
1984 }
1986 }
1987 }
1989 /* Include any jump table following the basic block. */
1999 /* Include any barrier that may follow the basic block. */
2004 /* Selectively delete the entire chain. */
2007 /* Remove the edges into and out of this block. Note that there may
2008 indeed be edges in, if we are removing an unreachable loop. */
2009 {
2013 {
2018 n_edges--;
2020 }
2022 {
2027 n_edges--;
2029 }
2033 }
2035 /* Remove the basic block from the array, and compact behind it. */
2039 }
2041 /* Remove block B from the basic block array and compact behind it. */
2043 static void
2045 basic_block b;
2046 {
2050 {
2054 }
2057 n_basic_blocks--;
2058 }
2060 /* Delete INSN by patching it out. Return the next insn. */
2062 rtx
2064 rtx insn;
2065 {
2068 rtx note;
2078 else
2084 /* If deleting a jump, decrement the use count of the label. Deleting
2085 the label itself should happen in the normal course of block merging. */
2091 /* Also if deleting an insn that references a label. */
2097 }
2099 /* True if a given label can be deleted. */
2101 static int
2103 rtx label;
2104 {
2105 rtx x;
2120 /* User declared labels must be preserved. */
2125 }
2127 static int
2129 rtx label;
2130 {
2131 rtx x;
2138 }
2140 /* Blocks A and B are to be merged into a single block A. The insns
2141 are already contiguous, hence `nomove'. */
2143 void
2146 {
2147 edge e;
2152 /* If there was a CODE_LABEL beginning B, delete it. */
2156 {
2157 /* Detect basic blocks with nothing but a label. This can happen
2158 in particular at the end of a function. */
2163 }
2165 /* Delete the basic block note. */
2168 {
2175 }
2177 /* If there was a jump out of A, delete it. */
2180 {
2181 rtx prev;
2189 #ifdef HAVE_cc0
2190 /* If this was a conditional jump, we need to also delete
2191 the insn that set cc0. */
2193 {
2199 }
2200 #endif
2203 }
2207 /* Delete everything marked above as well as crap that might be
2208 hanging out between the two blocks. */
2211 /* Normally there should only be one successor of A and that is B, but
2212 partway though the merge of blocks for conditional_execution we'll
2213 be merging a TEST block with THEN and ELSE successors. Free the
2214 whole lot of them and hope the caller knows what they're doing. */
2218 /* Adjust the edges out of B for the new owner. */
2223 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
2226 /* Reassociate the insns of B with A. */
2228 {
2230 {
2233 {
2236 }
2237 }
2239 }
2243 }
2245 /* Blocks A and B are to be merged into a single block. A has no incoming
2246 fallthru edge, so it can be moved before B without adding or modifying
2247 any jumps (aside from the jump from A to B). */
2249 static int
2252 {
2264 /* Move block and loop notes out of the chain so that we do not
2265 disturb their order.
2267 ??? A better solution would be to squeeze out all the non-nested notes
2268 and adjust the block trees appropriately. Even better would be to have
2269 a tighter connection between block trees and rtl so that this is not
2270 necessary. */
2273 /* Scramble the insn chain. */
2278 {
2281 }
2283 /* Swap the records for the two blocks around. Although we are deleting B,
2284 A is now where B was and we want to compact the BB array from where
2285 A used to be. */
2292 /* Now blocks A and B are contiguous. Merge them. */
2296 }
2298 /* Blocks A and B are to be merged into a single block. B has no outgoing
2299 fallthru edge, so it can be moved after A without adding or modifying
2300 any jumps (aside from the jump from A to B). */
2302 static int
2305 {
2312 /* Recognize a jump table following block B. */
2318 {
2321 }
2323 /* There had better have been a barrier there. Delete it. */
2328 /* Move block and loop notes out of the chain so that we do not
2329 disturb their order.
2331 ??? A better solution would be to squeeze out all the non-nested notes
2332 and adjust the block trees appropriately. Even better would be to have
2333 a tighter connection between block trees and rtl so that this is not
2334 necessary. */
2337 /* Scramble the insn chain. */
2340 /* Now blocks A and B are contiguous. Merge them. */
2344 {
2347 }
2350 }
2352 /* Attempt to merge basic blocks that are potentially non-adjacent.
2353 Return true iff the attempt succeeded. */
2355 static int
2357 edge e;
2359 {
2360 /* If C has a tail recursion label, do not merge. There is no
2361 edge recorded from the call_placeholder back to this label, as
2362 that would make optimize_sibling_and_tail_recursive_calls more
2363 complex for no gain. */
2368 /* If B has a fallthru edge to C, no need to move anything. */
2370 {
2374 {
2377 }
2380 }
2381 else
2382 {
2383 edge tmp_edge;
2384 basic_block d;
2388 /* We must make sure to not munge nesting of exception regions,
2389 lexical blocks, and loop notes.
2391 The first is taken care of by requiring that the active eh
2392 region at the end of one block always matches the active eh
2393 region at the beginning of the next block.
2395 The later two are taken care of by squeezing out all the notes. */
2397 /* ??? A throw/catch edge (or any abnormal edge) should be rarely
2398 executed and we may want to treat blocks which have two out
2399 edges, one normal, one abnormal as only having one edge for
2400 block merging purposes. */
2412 /* If B does not have an incoming fallthru, and the exception regions
2413 match, then it can be moved immediately before C without introducing
2414 or modifying jumps.
2416 C can not be the first block, so we do not have to worry about
2417 accessing a non-existent block. */
2424 /* Otherwise, we're going to try to move C after B. Make sure the
2425 exception regions match.
2427 If B is the last basic block, then we must not try to access the
2428 block structure for block B + 1. Luckily in that case we do not
2429 need to worry about matching exception regions. */
2433 {
2434 /* If C does not have an outgoing fallthru, then it can be moved
2435 immediately after B without introducing or modifying jumps. */
2439 /* Otherwise, we'll need to insert an extra jump, and possibly
2440 a new block to contain it. */
2441 /* ??? Not implemented yet. */
2442 }
2445 }
2446 }
2448 /* Top level driver for merge_blocks. */
2450 static void
2452 {
2455 /* Attempt to merge blocks as made possible by edge removal. If a block
2456 has only one successor, and the successor has only one predecessor,
2457 they may be combined. */
2460 {
2462 edge s;
2464 /* A loop because chains of blocks might be combineable. */
2470 /* If the jump insn has side effects, we can't kill the edge. */
2476 /* Don't get confused by the index shift caused by deleting blocks. */
2478 }
2479 }
2481 /* The given edge should potentially be a fallthru edge. If that is in
2482 fact true, delete the jump and barriers that are in the way. */
2484 void
2486 edge e;
2488 {
2489 rtx q;
2491 /* ??? In a late-running flow pass, other folks may have deleted basic
2492 blocks by nopping out blocks, leaving multiple BARRIERs between here
2493 and the target label. They ought to be chastized and fixed.
2495 We can also wind up with a sequence of undeletable labels between
2496 one block and the next.
2498 So search through a sequence of barriers, labels, and notes for
2499 the head of block C and assert that we really do fall through. */
2504 /* Remove what will soon cease being the jump insn from the source block.
2505 If block B consisted only of this single jump, turn it into a deleted
2506 note. */
2512 {
2513 #ifdef HAVE_cc0
2514 /* If this was a conditional jump, we need to also delete
2515 the insn that set cc0. */
2518 #endif
2521 {
2525 }
2526 else
2528 }
2530 /* Selectively unlink the sequence. */
2535 }
2537 /* Fix up edges that now fall through, or rather should now fall through
2538 but previously required a jump around now deleted blocks. Simplify
2539 the search by only examining blocks numerically adjacent, since this
2540 is how find_basic_blocks created them. */
2542 static void
2544 {
2548 {
2551 edge s;
2553 /* We care about simple conditional or unconditional jumps with
2554 a single successor.
2556 If we had a conditional branch to the next instruction when
2557 find_basic_blocks was called, then there will only be one
2558 out edge for the block which ended with the conditional
2559 branch (since we do not create duplicate edges).
2561 Furthermore, the edge will be marked as a fallthru because we
2562 merge the flags for the duplicate edges. So we do not want to
2563 check that the edge is not a FALLTHRU edge. */
2567 /* If the jump insn has side effects, we can't tidy the edge. */
2571 }
2572 }
2573 \f
2574 /* Perform data flow analysis.
2575 F is the first insn of the function; FLAGS is a set of PROP_* flags
2576 to be used in accumulating flow info. */
2578 void
2580 rtx f;
2583 {
2584 #ifdef ELIMINABLE_REGS
2587 #endif
2589 /* Record which registers will be eliminated. We use this in
2590 mark_used_regs. */
2594 #ifdef ELIMINABLE_REGS
2597 #else
2599 #endif
2604 /* The post-reload life analysis have (on a global basis) the same
2605 registers live as was computed by reload itself. elimination
2606 Otherwise offsets and such may be incorrect.
2608 Reload will make some registers as live even though they do not
2609 appear in the rtl.
2611 We don't want to create new auto-incs after reload, since they
2612 are unlikely to be useful and can cause problems with shared
2613 stack slots. */
2617 /* We want alias analysis information for local dead store elimination. */
2621 /* Always remove no-op moves. Do this before other processing so
2622 that we don't have to keep re-scanning them. */
2625 /* Some targets can emit simpler epilogues if they know that sp was
2626 not ever modified during the function. After reload, of course,
2627 we've already emitted the epilogue so there's no sense searching. */
2631 /* Allocate and zero out data structures that will record the
2632 data from lifetime analysis. */
2636 /* Find the set of registers live on function exit. */
2639 /* "Update" life info from zero. It'd be nice to begin the
2640 relaxation with just the exit and noreturn blocks, but that set
2641 is not immediately handy. */
2647 /* Clean up. */
2655 }
2657 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2658 Search for REGNO. If found, abort if it is not wider than word_mode. */
2660 static int
2664 {
2669 {
2673 }
2675 }
2677 /* A subroutine of verify_local_live_at_start. Search through insns
2678 between HEAD and END looking for register REGNO. */
2680 static void
2684 {
2686 {
2693 }
2695 /* We didn't find the register at all. Something's way screwy. */
2697 }
2699 /* A subroutine of update_life_info. Verify that there are no untoward
2700 changes in live_at_start during a local update. */
2702 static void
2704 regset new_live_at_start;
2705 basic_block bb;
2706 {
2708 {
2709 /* After reload, there are no pseudos, nor subregs of multi-word
2710 registers. The regsets should exactly match. */
2713 }
2714 else
2715 {
2718 /* Find the set of changed registers. */
2722 {
2723 /* No registers should die. */
2726 /* Verify that the now-live register is wider than word_mode. */
2728 });
2729 }
2730 }
2732 /* Updates life information starting with the basic blocks set in BLOCKS.
2733 If BLOCKS is null, consider it to be the universal set.
2735 If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
2736 we are only expecting local modifications to basic blocks. If we find
2737 extra registers live at the beginning of a block, then we either killed
2738 useful data, or we have a broken split that wants data not provided.
2739 If we find registers removed from live_at_start, that means we have
2740 a broken peephole that is killing a register it shouldn't.
2742 ??? This is not true in one situation -- when a pre-reload splitter
2743 generates subregs of a multi-word pseudo, current life analysis will
2744 lose the kill. So we _can_ have a pseudo go live. How irritating.
2746 Including PROP_REG_INFO does not properly refresh regs_ever_live
2747 unless the caller resets it to zero. */
2749 void
2751 sbitmap blocks;
2754 {
2755 regset tmp;
2756 regset_head tmp_head;
2761 /* For a global update, we go through the relaxation process again. */
2763 {
2767 /* If asked, remove notes from the blocks we'll update. */
2770 }
2773 {
2775 {
2783 });
2784 }
2785 else
2786 {
2788 {
2796 }
2797 }
2802 {
2803 /* The only pseudos that are live at the beginning of the function
2804 are those that were not set anywhere in the function. local-alloc
2805 doesn't know how to handle these correctly, so mark them as not
2806 local to any one basic block. */
2811 /* We have a problem with any pseudoreg that lives across the setjmp.
2812 ANSI says that if a user variable does not change in value between
2813 the setjmp and the longjmp, then the longjmp preserves it. This
2814 includes longjmp from a place where the pseudo appears dead.
2815 (In principle, the value still exists if it is in scope.)
2816 If the pseudo goes in a hard reg, some other value may occupy
2817 that hard reg where this pseudo is dead, thus clobbering the pseudo.
2818 Conclusion: such a pseudo must not go in a hard reg. */
2821 {
2823 {
2826 }
2827 });
2828 }
2829 }
2831 /* Free the variables allocated by find_basic_blocks.
2833 KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed. */
2835 void
2838 {
2840 {
2843 }
2846 {
2855 }
2856 }
2858 /* Return nonzero if the destination of SET equals the source. */
2859 static int
2861 rtx set;
2862 {
2867 {
2872 }
2876 }
2878 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2879 value to itself. */
2880 static int
2882 rtx insn;
2883 {
2886 /* Insns carrying these notes are useful later on. */
2894 {
2896 /* If nothing but SETs of registers to themselves,
2897 this insn can also be deleted. */
2899 {
2908 }
2911 }
2913 }
2915 /* Delete any insns that copy a register to itself. */
2917 static void
2919 rtx f;
2920 {
2921 rtx insn;
2923 {
2925 {
2929 }
2930 }
2931 }
2933 /* Determine if the stack pointer is constant over the life of the function.
2934 Only useful before prologues have been emitted. */
2936 static void
2938 rtx x;
2939 rtx pat ATTRIBUTE_UNUSED;
2941 {
2943 /* The stack pointer is only modified indirectly as the result
2944 of a push until later in flow. See the comments in rtl.texi
2945 regarding Embedded Side-Effects on Addresses. */
2953 }
2955 static void
2957 rtx f;
2958 {
2959 rtx insn;
2961 /* Assume that the stack pointer is unchanging if alloca hasn't
2962 been used. */
2968 {
2970 {
2971 /* Check if insn modifies the stack pointer. */
2973 NULL);
2976 }
2977 }
2978 }
2980 /* Mark a register in SET. Hard registers in large modes get all
2981 of their component registers set as well. */
2982 static void
2984 rtx reg;
2986 {
2995 {
2999 }
3000 }
3002 /* Mark those regs which are needed at the end of the function as live
3003 at the end of the last basic block. */
3004 static void
3006 regset set;
3007 {
3010 /* If exiting needs the right stack value, consider the stack pointer
3011 live at the end of the function. */
3013 || ! EXIT_IGNORE_STACK
3014 || (! FRAME_POINTER_REQUIRED
3015 && ! current_function_calls_alloca
3018 {
3020 }
3022 /* Mark the frame pointer if needed at the end of the function. If
3023 we end up eliminating it, it will be removed from the live list
3024 of each basic block by reload. */
3027 {
3029 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3030 /* If they are different, also mark the hard frame pointer as live */
3032 #endif
3033 }
3035 #ifdef PIC_OFFSET_TABLE_REGNUM
3036 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3037 /* Many architectures have a GP register even without flag_pic.
3038 Assume the pic register is not in use, or will be handled by
3039 other means, if it is not fixed. */
3042 #endif
3043 #endif
3045 /* Mark all global registers, and all registers used by the epilogue
3046 as being live at the end of the function since they may be
3047 referenced by our caller. */
3050 #ifdef EPILOGUE_USES
3052 #endif
3053 )
3056 /* Mark all call-saved registers that we actaully used. */
3058 {
3062 }
3064 /* Mark function return value. */
3066 }
3068 /* Callback function for for_each_successor_phi. DATA is a regset.
3069 Sets the SRC_REGNO, the regno of the phi alternative for phi node
3070 INSN, in the regset. */
3072 static int
3074 rtx insn ATTRIBUTE_UNUSED;
3078 {
3082 }
3084 /* Propagate global life info around the graph of basic blocks. Begin
3085 considering blocks with their corresponding bit set in BLOCKS_IN.
3086 If BLOCKS_IN is null, consider it the universal set.
3088 BLOCKS_OUT is set for every block that was changed. */
3090 static void
3094 {
3097 regset_head tmp_head;
3098 regset_head new_live_at_end_head;
3104 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
3105 because the `head == tail' style test for an empty queue doesn't
3106 work with a full queue. */
3111 /* Clear out the garbage that might be hanging out in bb->aux. */
3115 /* Queue the blocks set in the initial mask. Do this in reverse block
3116 number order so that we are more likely for the first round to do
3117 useful work. We use AUX non-null to flag that the block is queued. */
3119 {
3121 {
3125 });
3126 }
3127 else
3128 {
3130 {
3134 }
3135 }
3141 {
3143 basic_block bb;
3144 edge e;
3151 /* Begin by propogating live_at_start from the successor blocks. */
3154 {
3157 }
3159 /* Force the stack pointer to be live -- which might not already be
3160 the case for blocks within infinite loops. */
3163 /* Regs used in phi nodes are not included in
3164 global_live_at_start, since they are live only along a
3165 particular edge. Set those regs that are live because of a
3166 phi node alternative corresponding to this particular block. */
3169 new_live_at_end);
3172 {
3175 }
3177 /* On our first pass through this block, we'll go ahead and continue.
3178 Recognize first pass by local_set NULL. On subsequent passes, we
3179 get to skip out early if live_at_end wouldn't have changed. */
3182 {
3185 }
3186 else
3187 {
3188 /* If any bits were removed from live_at_end, we'll have to
3189 rescan the block. This wouldn't be necessary if we had
3190 precalculated local_live, however with PROP_SCAN_DEAD_CODE
3191 local_live is really dependant on live_at_end. */
3197 {
3198 /* Find the set of changed bits. Take this opportunity
3199 to notice that this set is empty and early out. */
3206 /* If any of the changed bits overlap with local_set,
3207 we'll have to rescan the block. Detect overlap by
3208 the AND with ~local_set turning off bits. */
3210 BITMAP_AND_COMPL);
3211 }
3212 }
3214 /* Let our caller know that BB changed enough to require its
3215 death notes updated. */
3220 {
3221 /* Add to live_at_start the set of all registers in
3222 new_live_at_end that aren't in the old live_at_end. */
3225 BITMAP_AND_COMPL);
3233 }
3234 else
3235 {
3238 /* Rescan the block insn by insn to turn (a copy of) live_at_end
3239 into live_at_start. */
3242 /* If live_at start didn't change, no need to go farther. */
3247 }
3249 /* Queue all predecessors of BB so that we may re-examine
3250 their live_at_end. */
3252 {
3255 {
3260 }
3261 }
3262 }
3268 {
3270 {
3273 });
3274 }
3275 else
3276 {
3278 {
3281 }
3282 }
3285 }
3286 \f
3287 /* Subroutines of life analysis. */
3289 /* Allocate the permanent data structures that represent the results
3290 of life analysis. Not static since used also for stupid life analysis. */
3292 void
3294 {
3298 {
3303 }
3305 ENTRY_BLOCK_PTR->global_live_at_end
3307 EXIT_BLOCK_PTR->global_live_at_start
3311 }
3313 void
3315 {
3320 /* Recalculate the register space, in case it has grown. Old style
3321 vector oriented regsets would set regset_{size,bytes} here also. */
3324 /* Reset all the data we'll collect in propagate_block and its
3325 subroutines. */
3327 {
3334 }
3335 }
3337 /* Delete dead instructions for propagate_block. */
3339 static void
3341 basic_block bb;
3342 rtx insn;
3343 {
3346 /* If the insn referred to a label, and that label was attached to
3347 an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's
3348 pretty much mandatory to delete it, because the ADDR_VEC may be
3349 referencing labels that no longer exist. */
3352 {
3354 rtx next;
3361 {
3371 }
3372 }
3377 }
3379 /* Delete dead libcalls for propagate_block. Return the insn
3380 before the libcall. */
3382 static rtx
3384 basic_block bb;
3386 {
3395 }
3397 /* Update the life-status of regs for one insn. Return the previous insn. */
3399 rtx
3402 rtx insn;
3403 {
3408 rtx note;
3416 {
3422 }
3424 /* We almost certainly don't want to delete prologue or epilogue
3425 instructions. Warn about probable compiler losage. */
3427 && reload_completed
3430 || (HAVE_sibcall_epilogue
3432 {
3434 {
3438 }
3440 }
3442 /* If an instruction consists of just dead store(s) on final pass,
3443 delete it. */
3445 {
3446 /* Record sets. Do this even for dead instructions, since they
3447 would have killed the values if they hadn't been deleted. */
3450 /* CC0 is now known to be dead. Either this insn used it,
3451 in which case it doesn't anymore, or clobbered it,
3452 so the next insn can't use it. */
3456 {
3459 }
3460 else
3464 }
3466 /* See if this is an increment or decrement that can be merged into
3467 a following memory address. */
3468 #ifdef AUTO_INC_DEC
3469 {
3472 /* Does this instruction increment or decrement a register? */
3480 /* Ok, look for a following memory ref we can combine with.
3481 If one is found, change the memory ref to a PRE_INC
3482 or PRE_DEC, cancel this insn, and return 1.
3483 Return 0 if nothing has been done. */
3486 }
3491 /* If this is not the final pass, and this insn is copying the value of
3492 a library call and it's dead, don't scan the insns that perform the
3493 library call, so that the call's arguments are not marked live. */
3495 {
3496 /* Record the death of the dest reg. */
3501 }
3507 /* We have an insn to pop a constant amount off the stack.
3508 (Such insns use PLUS regardless of the direction of the stack,
3509 and any insn to adjust the stack by a constant is always a pop.)
3510 These insns, if not dead stores, have no effect on life. */
3511 ;
3512 else
3513 {
3514 /* Any regs live at the time of a call instruction must not go
3515 in a register clobbered by calls. Find all regs now live and
3516 record this for them. */
3522 /* Record sets. Do this even for dead instructions, since they
3523 would have killed the values if they hadn't been deleted. */
3527 {
3535 /* Non-constant calls clobber memory. */
3539 /* There may be extra registers to be clobbered. */
3541 note;
3547 /* Calls change all call-used and global registers. */
3551 {
3552 /* We do not want REG_UNUSED notes for these registers. */
3556 }
3557 }
3559 /* If an insn doesn't use CC0, it becomes dead since we assume
3560 that every insn clobbers it. So show it dead here;
3561 mark_used_regs will set it live if it is referenced. */
3564 /* Record uses. */
3568 /* Sometimes we may have inserted something before INSN (such as a move)
3569 when we make an auto-inc. So ensure we will scan those insns. */
3570 #ifdef AUTO_INC_DEC
3572 #endif
3575 {
3583 /* Calls use their arguments. */
3585 note;
3591 /* The stack ptr is used (honorarily) by a CALL insn. */
3594 /* Calls may also reference any of the global registers,
3595 so they are made live. */
3600 }
3601 }
3603 /* On final pass, update counts of how many insns in which each reg
3604 is live. */
3610 }
3612 /* Initialize a propagate_block_info struct for public consumption.
3613 Note that the structure itself is opaque to this file, but that
3614 the user can use the regsets provided here. */
3618 basic_block bb;
3619 regset live;
3620 regset local_set;
3622 {
3634 else
3639 #ifdef HAVE_conditional_execution
3641 free_reg_cond_life_info);
3644 /* If this block ends in a conditional branch, for each register live
3645 from one side of the branch and not the other, record the register
3646 as conditionally dead. */
3650 {
3651 regset_head diff_head;
3657 /* Identify the successor blocks. */
3660 {
3664 {
3668 }
3671 }
3672 else
3673 {
3674 /* This can happen with a conditional jump to the next insn. */
3678 /* Simplest way to do nothing. */
3680 }
3682 /* Extract the condition from the branch. */
3688 {
3692 }
3694 /* Compute which register lead different lives in the successors. */
3697 {
3702 /* For each such register, mark it conditionally dead. */
3703 EXECUTE_IF_SET_IN_REG_SET
3705 {
3707 rtx cond;
3713 else
3719 });
3720 }
3723 }
3724 #endif
3726 /* If this block has no successors, any stores to the frame that aren't
3727 used later in the block are dead. So make a pass over the block
3728 recording any such that are made and show them dead at the end. We do
3729 a very conservative and simple job here. */
3734 {
3735 rtx insn;
3740 {
3748 }
3749 }
3752 }
3754 /* Release a propagate_block_info struct. */
3756 void
3759 {
3764 #ifdef HAVE_conditional_execution
3767 #endif
3773 }
3775 /* Compute the registers live at the beginning of a basic block BB from
3776 those live at the end.
3778 When called, REG_LIVE contains those live at the end. On return, it
3779 contains those live at the beginning.
3781 LOCAL_SET, if non-null, will be set with all registers killed by
3782 this basic block. */
3784 void
3786 basic_block bb;
3787 regset live;
3788 regset local_set;
3790 {
3797 {
3800 /* Process the regs live at the end of the block.
3801 Mark them as not local to any one basic block. */
3804 }
3806 /* Scan the block an insn at a time from end to beginning. */
3809 {
3810 /* If this is a call to `setjmp' et al, warn if any
3811 non-volatile datum is live. */
3821 }
3824 }
3825 \f
3826 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3827 (SET expressions whose destinations are registers dead after the insn).
3828 NEEDED is the regset that says which regs are alive after the insn.
3830 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3832 If X is the entire body of an insn, NOTES contains the reg notes
3833 pertaining to the insn. */
3835 static int
3838 rtx x;
3840 rtx notes ATTRIBUTE_UNUSED;
3841 {
3844 #ifdef AUTO_INC_DEC
3845 /* If flow is invoked after reload, we must take existing AUTO_INC
3846 expresions into account. */
3848 {
3850 {
3852 {
3855 /* Don't delete insns to set global regs. */
3859 }
3860 }
3861 }
3862 #endif
3864 /* If setting something that's a reg or part of one,
3865 see if that register's altered value will be live. */
3868 {
3871 #ifdef HAVE_cc0
3874 #endif
3876 /* A SET that is a subroutine call cannot be dead. */
3878 {
3881 }
3883 /* Don't eliminate loads from volatile memory or volatile asms. */
3888 {
3889 rtx temp;
3894 /* Walk the set of memory locations we are currently tracking
3895 and see if one is an identical match to this memory location.
3896 If so, this memory write is dead (remember, we're walking
3897 backwards from the end of the block to the start). */
3900 {
3904 }
3905 }
3906 else
3907 {
3914 {
3917 /* Obvious. */
3921 /* If this is a hard register, verify that subsequent
3922 words are not needed. */
3924 {
3930 }
3932 /* Don't delete insns to set global regs. */
3936 /* Make sure insns to set the stack pointer aren't deleted. */
3940 /* Make sure insns to set the frame pointer aren't deleted. */
3944 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3948 #endif
3950 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3951 /* Make sure insns to set arg pointer are never deleted
3952 (if the arg pointer isn't fixed, there will be a USE
3953 for it, so we can treat it normally). */
3956 #endif
3958 #ifdef PIC_OFFSET_TABLE_REGNUM
3959 /* Before reload, do not allow sets of the pic register
3960 to be deleted. Reload can insert references to
3961 constant pool memory anywhere in the function, making
3962 the PIC register live where it wasn't before. */
3966 #endif
3968 /* Otherwise, the set is dead. */
3970 }
3971 }
3972 }
3974 /* If performing several activities, insn is dead if each activity
3975 is individually dead. Also, CLOBBERs and USEs can be ignored; a
3976 CLOBBER or USE that's inside a PARALLEL doesn't make the insn
3977 worth keeping. */
3979 {
3989 }
3991 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
3992 is not necessarily true for hard registers. */
3998 /* We do not check other CLOBBER or USE here. An insn consisting of just
3999 a CLOBBER or just a USE should not be deleted. */
4001 }
4003 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
4004 return 1 if the entire library call is dead.
4005 This is true if X copies a register (hard or pseudo)
4006 and if the hard return reg of the call insn is dead.
4007 (The caller should have tested the destination of X already for death.)
4009 If this insn doesn't just copy a register, then we don't
4010 have an ordinary libcall. In that case, cse could not have
4011 managed to substitute the source for the dest later on,
4012 so we can assume the libcall is dead.
4014 NEEDED is the bit vector of pseudoregs live before this insn.
4015 NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
4017 static int
4020 rtx x;
4021 rtx note;
4022 rtx insn;
4023 {
4027 {
4030 {
4032 rtx call_pat;
4035 /* Find the call insn. */
4039 /* If there is none, do nothing special,
4040 since ordinary death handling can understand these insns. */
4044 /* See if the hard reg holding the value is dead.
4045 If this is a PARALLEL, find the call within it. */
4048 {
4054 /* This may be a library call that is returning a value
4055 via invisible pointer. Do nothing special, since
4056 ordinary death handling can understand these insns. */
4061 }
4064 }
4065 }
4067 }
4069 /* Return 1 if register REGNO was used before it was set, i.e. if it is
4070 live at function entry. Don't count global register variables, variables
4071 in registers that can be used for function arg passing, or variables in
4072 fixed hard registers. */
4074 int
4077 {
4086 }
4088 /* 1 if register REGNO was alive at a place where `setjmp' was called
4089 and was set more than once or is an argument.
4090 Such regs may be clobbered by `longjmp'. */
4092 int
4095 {
4102 }
4103 \f
4104 /* INSN references memory, possibly using autoincrement addressing modes.
4105 Find any entries on the mem_set_list that need to be invalidated due
4106 to an address change. */
4108 static void
4111 rtx insn;
4112 {
4115 {
4117 {
4120 rtx next;
4123 {
4126 {
4127 /* Splice temp out of list. */
4130 else
4133 }
4134 else
4137 }
4138 }
4139 }
4140 }
4142 /* Process the registers that are set within X. Their bits are set to
4143 1 in the regset DEAD, because they are dead prior to this insn.
4145 If INSN is nonzero, it is the insn being processed.
4147 FLAGS is the set of operations to perform. */
4149 static void
4153 {
4155 rtx link;
4160 {
4166 }
4167 retry:
4169 {
4181 {
4184 {
4187 {
4196 /* FALLTHRU */
4205 }
4206 }
4208 }
4212 }
4213 }
4215 /* Process a single SET rtx, X. */
4217 static void
4223 {
4228 /* Some targets place small structures in registers for
4229 return values of functions. We have to detect this
4230 case specially here to get correct flow information. */
4233 {
4237 }
4239 /* Modifying just one hardware register of a multi-reg value or just a
4240 byte field of a register does not mean the value from before this insn
4241 is now dead. Of course, if it was dead after it's unused now. */
4244 {
4248 /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */
4249 do
4258 /* FALLTHRU */
4268 {
4272 /* Identify the range of registers affected. This is moderately
4273 tricky for hard registers. See alter_subreg. */
4277 {
4278 #ifdef ALTER_HARD_SUBREG
4281 #else
4283 #endif
4284 regno_last = (regno_first
4287 /* Since we've just adjusted the register number ranges, make
4288 sure REG matches. Otherwise some_was_live will be clear
4289 when it shouldn't have been, and we'll create incorrect
4290 REG_UNUSED notes. */
4292 }
4293 else
4294 {
4295 /* If the number of words in the subreg is less than the number
4296 of words in the full register, we have a well-defined partial
4297 set. Otherwise the high bits are undefined.
4299 This is only really applicable to pseudos, since we just took
4300 care of multi-word hard registers. */
4308 }
4309 }
4310 else
4316 }
4318 /* If this set is a MEM, then it kills any aliased writes.
4319 If this set is a REG, then it kills any MEMs which use the reg. */
4321 {
4323 {
4326 rtx next;
4329 {
4335 {
4336 /* Splice this entry out of the list. */
4339 else
4342 }
4343 else
4346 }
4347 }
4349 /* If the memory reference had embedded side effects (autoincrement
4350 address modes. Then we may need to kill some entries on the
4351 memory set list. */
4356 /* ??? With more effort we could track conditional memory life. */
4357 && ! cond
4358 /* We do not know the size of a BLKmode store, so we do not track
4359 them for redundant store elimination. */
4361 /* There are no REG_INC notes for SP, so we can't assume we'll see
4362 everything that invalidates it. To be safe, don't eliminate any
4363 stores though SP; none of them should be redundant anyway. */
4366 }
4371 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4374 #endif
4375 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4377 #endif
4378 )
4379 {
4383 {
4392 }
4394 #ifdef HAVE_conditional_execution
4395 /* Consider conditional death in deciding that the register needs
4396 a death note. */
4398 /* The stack pointer is never dead. Well, not strictly true,
4399 but it's very difficult to tell from here. Hopefully
4400 combine_stack_adjustments will fix up the most egregious
4401 errors. */
4403 {
4407 }
4408 #endif
4410 /* Additional data to record if this is the final pass. */
4413 {
4419 {
4422 /* The next use is no longer next, since a store intervenes. */
4425 }
4428 {
4430 {
4431 /* Count (weighted) references, stores, etc. This counts a
4432 register twice if it is modified, but that is correct. */
4437 /* The insns where a reg is live are normally counted
4438 elsewhere, but we want the count to include the insn
4439 where the reg is set, and the normal counting mechanism
4440 would not count it. */
4442 }
4444 /* If this is a hard reg, record this function uses the reg. */
4446 {
4449 }
4450 else
4451 {
4452 /* Keep track of which basic blocks each reg appears in. */
4457 }
4458 }
4461 {
4463 {
4464 /* Make a logical link from the next following insn
4465 that uses this register, back to this insn.
4466 The following insns have already been processed.
4468 We don't build a LOG_LINK for hard registers containing
4469 in ASM_OPERANDs. If these registers get replaced,
4470 we might wind up changing the semantics of the insn,
4471 even if reload can make what appear to be valid
4472 assignments later. */
4477 }
4478 }
4480 ;
4482 {
4487 {
4488 /* Note that dead stores have already been deleted
4489 when possible. If we get here, we have found a
4490 dead store that cannot be eliminated (because the
4491 same insn does something useful). Indicate this
4492 by marking the reg being set as dying here. */
4495 }
4496 }
4497 else
4498 {
4500 {
4501 /* This is a case where we have a multi-word hard register
4502 and some, but not all, of the words of the register are
4503 needed in subsequent insns. Write REG_UNUSED notes
4504 for those parts that were not needed. This case should
4505 be rare. */
4513 }
4514 }
4515 }
4517 /* Mark the register as being dead. */
4519 && ! not_dead
4520 /* The stack pointer is never dead. Well, not strictly true,
4521 but it's very difficult to tell from here. Hopefully
4522 combine_stack_adjustments will fix up the most egregious
4523 errors. */
4525 {
4528 }
4529 }
4531 {
4534 }
4536 /* If this is the last pass and this is a SCRATCH, show it will be dying
4537 here and count it. */
4539 {
4543 }
4544 }
4545 \f
4546 #ifdef HAVE_conditional_execution
4547 /* Mark REGNO conditionally dead. Return true if the register is
4548 now unconditionally dead. */
4550 static int
4554 rtx cond;
4555 {
4556 /* If this is a store to a predicate register, the value of the
4557 predicate is changing, we don't know that the predicate as seen
4558 before is the same as that seen after. Flush all dependant
4559 conditions from reg_cond_dead. This will make all such
4560 conditionally live registers unconditionally live. */
4564 /* If this is an unconditional store, remove any conditional
4565 life that may have existed. */
4568 else
4569 {
4570 splay_tree_node node;
4572 rtx ncond;
4574 /* Otherwise this is a conditional set. Record that fact.
4575 It may have been conditionally used, or there may be a
4576 subsequent set with a complimentary condition. */
4580 {
4581 /* The register was unconditionally live previously.
4582 Record the current condition as the condition under
4583 which it is dead. */
4593 /* Not unconditionaly dead. */
4595 }
4596 else
4597 {
4598 /* The register was conditionally live previously.
4599 Add the new condition to the old. */
4604 /* If the register is now unconditionally dead,
4605 remove the entry in the splay_tree. */
4608 else
4609 {
4615 /* Not unconditionaly dead. */
4617 }
4618 }
4619 }
4622 }
4624 /* Called from splay_tree_delete for pbi->reg_cond_life. */
4626 static void
4628 splay_tree_value value;
4629 {
4633 }
4635 /* Helper function for flush_reg_cond_reg. */
4637 static int
4639 splay_tree_node node;
4641 {
4647 /* Don't need to search if last flushed value was farther on in
4648 the in-order traversal. */
4652 /* Splice out portions of the expression that refer to regno. */
4656 {
4658 {
4662 }
4663 else
4665 }
4667 /* If the entire condition is now NULL, signal the node to be removed. */
4669 {
4672 }
4673 else
4675 }
4677 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
4679 static void
4683 {
4693 }
4695 /* Logical arithmetic on predicate conditions. IOR, NOT and NAND.
4696 We actually use EXPR_LIST to chain the sub-expressions together
4697 instead of IOR because it's easier to manipulate and we have
4698 the lists.c functions to reuse nodes.
4700 Return a new rtl expression as appropriate. */
4702 static rtx
4705 {
4707 rtx x_reg;
4708 rtx c;
4710 /* We expect these conditions to be of the form (eq reg 0). */
4717 /* Search the expression for an existing sub-expression of X_REG. */
4719 {
4722 {
4723 /* If we find X already present in OLD, we need do nothing. */
4727 /* If we find X being a compliment of a condition in OLD,
4728 then the entire condition is true. */
4731 }
4732 }
4734 /* Otherwise just add to the chain. */
4736 }
4738 static rtx
4740 rtx x;
4741 {
4743 rtx x_reg;
4745 /* We expect these conditions to be of the form (eq reg 0). */
4754 NULL_RTX);
4755 }
4757 static rtx
4760 {
4762 rtx x_reg;
4765 /* We expect these conditions to be of the form (eq reg 0). */
4772 /* Search the expression for an existing sub-expression of X_REG. */
4775 {
4778 {
4779 /* If we find X already present in OLD, then we need to
4780 splice it out. */
4782 {
4786 }
4788 /* If we find X being a compliment of a condition in OLD,
4789 then we need do nothing. */
4792 }
4793 }
4795 /* Otherwise, by implication, the register in question is now live for
4796 the inverse of the condition X. */
4799 old);
4800 }
4802 \f
4803 #ifdef AUTO_INC_DEC
4805 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
4806 reference. */
4808 static void
4811 rtx x;
4812 rtx insn;
4813 {
4816 rtx set;
4818 /* Here we detect use of an index register which might be good for
4819 postincrement, postdecrement, preincrement, or predecrement. */
4825 {
4828 rtx use;
4829 rtx incr;
4832 /* Is the next use an increment that might make auto-increment? */
4837 /* Can't add side effects to jumps; if reg is spilled and
4838 reloaded, there's no way to store back the altered value. */
4843 && ((HAVE_POST_INCREMENT
4845 || (HAVE_POST_DECREMENT
4847 || (HAVE_PRE_INCREMENT
4849 || (HAVE_PRE_DECREMENT
4851 /* Make sure this reg appears only once in this insn. */
4854 {
4861 /* Mustn't autoinc an eliminable register. */
4864 {
4865 /* This is the simple case. Try to make the auto-inc. If
4866 we can't, we are done. Otherwise, we will do any
4867 needed updates below. */
4872 }
4874 /* PREV_INSN used here to check the semi-open interval
4875 [insn,incr). */
4877 /* We must also check for sets of q as q may be
4878 a call clobbered hard register and there may
4879 be a call between PREV_INSN (insn) and incr. */
4881 {
4882 /* We have *p followed sometime later by q = p+size.
4883 Both p and q must be live afterward,
4884 and q is not used between INSN and its assignment.
4885 Change it to q = p, ...*q..., q = q+size.
4886 Then fall into the usual case. */
4898 /* If we can't make the auto-inc, or can't make the
4899 replacement into Y, exit. There's no point in making
4900 the change below if we can't do the auto-inc and doing
4901 so is not correct in the pre-inc case. */
4910 /* We now know we'll be doing this change, so emit the
4911 new insn(s) and do the updates. */
4917 /* INCR will become a NOTE and INSN won't contain a
4918 use of ADDR. If a use of ADDR was just placed in
4919 the insn before INSN, make that the next use.
4920 Otherwise, invalidate it. */
4925 else
4931 /* REGNO is now used in INCR which is below INSN, but it
4932 previously wasn't live here. If we don't mark it as
4933 live, we'll put a REG_DEAD note for it on this insn,
4934 which is incorrect. */
4937 /* If there are any calls between INSN and INCR, show
4938 that REGNO now crosses them. */
4942 }
4943 else
4946 /* If we haven't returned, it means we were able to make the
4947 auto-inc, so update the status. First, record that this insn
4948 has an implicit side effect. */
4953 /* Modify the old increment-insn to simply copy
4954 the already-incremented value of our register. */
4958 /* If that makes it a no-op (copying the register into itself) delete
4959 it so it won't appear to be a "use" and a "set" of this
4960 register. */
4962 {
4963 /* If the original source was dead, it's dead now. */
4971 }
4974 {
4975 /* Count an extra reference to the reg. When a reg is
4976 incremented, spilling it is worse, so we want to make
4977 that less likely. */
4981 /* Count the increment as a setting of the register,
4982 even though it isn't a SET in rtl. */
4984 }
4985 }
4986 }
4987 }
4989 \f
4990 static void
4993 rtx reg;
4994 rtx cond ATTRIBUTE_UNUSED;
4995 rtx insn;
4996 {
5003 /* A hard reg in a wide mode may really be multiple registers.
5004 If so, mark all of them just like the first. */
5006 {
5009 {
5013 }
5014 }
5017 {
5018 /* Record where each reg is used, so when the reg is set we know
5019 the next insn that uses it. */
5021 }
5024 {
5026 {
5027 /* If this is a register we are going to try to eliminate,
5028 don't mark it live here. If we are successful in
5029 eliminating it, it need not be live unless it is used for
5030 pseudos, in which case it will have been set live when it
5031 was allocated to the pseudos. If the register will not
5032 be eliminated, reload will set it live at that point.
5034 Otherwise, record that this function uses this register. */
5035 /* ??? The PPC backend tries to "eliminate" on the pic
5036 register to itself. This should be fixed. In the mean
5037 time, hack around it. */
5042 {
5044 do
5047 }
5048 }
5049 else
5050 {
5051 /* Keep track of which basic block each reg appears in. */
5059 /* Count (weighted) number of uses of each reg. */
5062 }
5063 }
5065 /* Find out if any of the register was set this insn. */
5068 {
5072 }
5074 /* Record and count the insns in which a reg dies. If it is used in
5075 this insn and was dead below the insn then it dies in this insn.
5076 If it was set in this insn, we do not make a REG_DEAD note;
5077 likewise if we already made such a note. */
5079 && some_was_dead
5081 {
5082 /* Check for the case where the register dying partially
5083 overlaps the register set by this insn. */
5086 {
5090 }
5092 /* If none of the words in X is needed, make a REG_DEAD note.
5093 Otherwise, we must make partial REG_DEAD notes. */
5095 {
5103 }
5104 else
5105 {
5106 /* Don't make a REG_DEAD note for a part of a register
5107 that is set in the insn. */
5117 }
5118 }
5122 {
5126 }
5128 #ifdef HAVE_conditional_execution
5129 /* If this is a conditional use, record that fact. If it is later
5130 conditionally set, we'll know to kill the register. */
5132 {
5133 splay_tree_node node;
5135 rtx ncond;
5138 {
5141 {
5142 /* The register was unconditionally live previously.
5143 No need to do anything. */
5144 }
5145 else
5146 {
5147 /* The register was conditionally live previously.
5148 Subtract the new life cond from the old death cond. */
5153 /* If the register is now unconditionally live, remove the
5154 entry in the splay_tree. */
5156 {
5159 }
5160 else
5162 }
5163 }
5164 else
5165 {
5166 /* The register was not previously live at all. Record
5167 the condition under which it is still dead. */
5172 }
5173 }
5175 {
5176 splay_tree_node node;
5181 {
5182 /* The register was conditionally live previously, but is now
5183 unconditionally so. Remove it from the conditionally dead
5184 list, so that a conditional set won't cause us to think
5185 it dead. */
5189 }
5190 }
5192 #endif
5193 }
5195 /* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
5196 This is done assuming the registers needed from X are those that
5197 have 1-bits in PBI->REG_LIVE.
5199 INSN is the containing instruction. If INSN is dead, this function
5200 is not called. */
5202 static void
5206 {
5211 retry:
5214 {
5225 #ifdef HAVE_cc0
5229 #endif
5232 /* If we are clobbering a MEM, mark any registers inside the address
5233 as being used. */
5239 /* Don't bother watching stores to mems if this is not the
5240 final pass. We'll not be deleting dead stores this round. */
5242 {
5243 /* Invalidate the data for the last MEM stored, but only if MEM is
5244 something that can be stored into. */
5248 else
5249 {
5252 rtx next;
5255 {
5258 {
5259 /* Splice temp out of the list. */
5262 else
5265 }
5266 else
5269 }
5270 }
5272 /* If the memory reference had embedded side effects (autoincrement
5273 address modes. Then we may need to kill some entries on the
5274 memory set list. */
5277 }
5279 #ifdef AUTO_INC_DEC
5282 #endif
5286 #ifdef CLASS_CANNOT_CHANGE_MODE
5292 #endif
5294 /* While we're here, optimize this case. */
5298 /* FALLTHRU */
5301 /* See a register other than being set => mark it as needed. */
5306 {
5310 /* If storing into MEM, don't show it as being used. But do
5311 show the address as being used. */
5313 {
5314 #ifdef AUTO_INC_DEC
5317 #endif
5321 }
5323 /* Storing in STRICT_LOW_PART is like storing in a reg
5324 in that this SET might be dead, so ignore it in TESTREG.
5325 but in some other ways it is like using the reg.
5327 Storing in a SUBREG or a bit field is like storing the entire
5328 register in that if the register's value is not used
5329 then this SET is not needed. */
5334 {
5335 #ifdef CLASS_CANNOT_CHANGE_MODE
5342 #endif
5344 /* Modifying a single register in an alternate mode
5345 does not use any of the old value. But these other
5346 ways of storing in a register do use the old value. */
5349 ;
5350 else
5354 }
5356 /* If this is a store into a register, recursively scan the
5357 value being stored. */
5365 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
5368 #endif
5369 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
5371 #endif
5372 ))
5373 {
5378 }
5379 }
5386 {
5387 /* Traditional and volatile asm instructions must be considered to use
5388 and clobber all hard registers, all pseudo-registers and all of
5389 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
5391 Consider for instance a volatile asm that changes the fpu rounding
5392 mode. An insn should not be moved across this even if it only uses
5393 pseudo-regs because it might give an incorrectly rounded result.
5395 ?!? Unfortunately, marking all hard registers as live causes massive
5396 problems for the register allocator and marking all pseudos as live
5397 creates mountains of uninitialized variable warnings.
5399 So for now, just clear the memory set list and mark any regs
5400 we can find in ASM_OPERANDS as used. */
5404 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
5405 We can not just fall through here since then we would be confused
5406 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
5407 traditional asms unlike their normal usage. */
5409 {
5414 }
5416 }
5429 /* We _do_not_ want to scan operands of phi nodes. Operands of
5430 a phi function are evaluated only when control reaches this
5431 block along a particular edge. Therefore, regs that appear
5432 as arguments to phi should not be added to the global live at
5433 start. */
5438 }
5440 /* Recursively scan the operands of this expression. */
5442 {
5447 {
5449 {
5450 /* Tail recursive case: save a function call level. */
5452 {
5455 }
5457 }
5459 {
5463 }
5464 }
5465 }
5466 }
5467 \f
5468 #ifdef AUTO_INC_DEC
5470 static int
5473 rtx insn;
5474 {
5475 /* Find the next use of this reg. If in same basic block,
5476 make it do pre-increment or pre-decrement if appropriate. */
5484 /* Don't do this if the reg dies, or gets set in y; a standard addressing
5485 mode would be better. */
5488 {
5489 /* We have found a suitable auto-increment
5490 and already changed insn Y to do it.
5491 So flush this increment-instruction. */
5495 /* Count a reference to this reg for the increment
5496 insn we are deleting. When a reg is incremented.
5497 spilling it is worse, so we want to make that
5498 less likely. */
5500 {
5504 }
5506 }
5508 }
5510 /* Try to change INSN so that it does pre-increment or pre-decrement
5511 addressing on register REG in order to add AMOUNT to REG.
5512 AMOUNT is negative for pre-decrement.
5513 Returns 1 if the change could be made.
5514 This checks all about the validity of the result of modifying INSN. */
5516 static int
5519 HOST_WIDE_INT amount;
5520 {
5523 /* Nonzero if we can try to make a pre-increment or pre-decrement.
5524 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
5526 /* Nonzero if we can try to make a post-increment or post-decrement.
5527 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
5528 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
5529 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
5532 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
5535 /* From the sign of increment, see which possibilities are conceivable
5536 on this target machine. */
5550 /* It is not safe to add a side effect to a jump insn
5551 because if the incremented register is spilled and must be reloaded
5552 there would be no way to store the incremented value back in memory. */
5561 {
5564 }
5572 /* See if this combination of instruction and addressing mode exists. */
5580 /* Record that this insn now has an implicit side effect on X. */
5583 }
5586 \f
5587 /* Find the place in the rtx X where REG is used as a memory address.
5588 Return the MEM rtx that so uses it.
5589 If PLUSCONST is nonzero, search instead for a memory address equivalent to
5590 (plus REG (const_int PLUSCONST)).
5592 If such an address does not appear, return 0.
5593 If REG appears more than once, or is used other than in such an address,
5594 return (rtx)1. */
5596 rtx
5599 rtx reg;
5600 HOST_WIDE_INT plusconst;
5601 {
5618 {
5619 /* If REG occurs inside a MEM used in a bit-field reference,
5620 that is unacceptable. */
5623 }
5629 {
5631 {
5637 }
5639 {
5642 {
5648 }
5649 }
5650 }
5653 }
5654 \f
5655 /* Write information about registers and basic blocks into FILE.
5656 This is part of making a debugging dump. */
5658 void
5660 regset r;
5662 {
5665 {
5668 }
5671 {
5676 });
5677 }
5679 void
5681 regset r;
5682 {
5685 }
5687 void
5690 {
5697 {
5719 {
5724 else
5728 }
5732 }
5736 {
5758 }
5761 }
5763 void
5765 {
5767 }
5769 static void
5772 edge e;
5774 {
5781 else
5788 {
5791 };
5799 {
5806 else
5809 }
5811 }
5812 }
5814 \f
5815 /* Print out one basic block with live information at start and end. */
5816 void
5818 basic_block bb;
5820 {
5821 rtx insn;
5822 rtx last;
5823 edge e;
5853 }
5855 void
5857 basic_block bb;
5858 {
5860 }
5862 void
5865 {
5867 }
5869 /* Like print_rtl, but also print out live information for the start of each
5870 basic block. */
5872 void
5875 rtx rtx_first;
5876 {
5881 else
5882 {
5894 {
5896 rtx x;
5901 {
5909 }
5910 }
5913 {
5915 basic_block bb;
5918 {
5923 }
5935 {
5940 }
5944 }
5949 }
5952 {
5957 }
5958 }
5960 /* Compute dominator relationships using new flow graph structures. */
5961 void
5965 {
5968 edge e;
5972 /* Allocate a worklist array/queue. Entries are only added to the
5973 list if they were not already on the list. So the size is
5974 bounded by the number of basic blocks. */
5982 {
5983 /* The optimistic setting of dominators requires us to put every
5984 block on the work list initially. */
5987 {
5990 }
5994 /* We want a maximal solution, so initially assume everything dominates
5995 everything else. */
5998 /* Mark successors of the entry block so we can identify them below. */
6002 /* Iterate until the worklist is empty. */
6004 {
6005 /* Take the first entry off the worklist. */
6009 qlen--;
6013 /* Compute the intersection of the dominators of all the
6014 predecessor blocks.
6016 If one of the predecessor blocks is the ENTRY block, then the
6017 intersection of the dominators of the predecessor blocks is
6018 defined as the null set. We can identify such blocks by the
6019 special value in the AUX field in the block structure. */
6021 {
6022 /* Do not clear the aux field for blocks which are
6023 successors of the ENTRY block. That way we we never
6024 add them to the worklist again.
6026 The intersect of dominators of the preds of this block is
6027 defined as the null set. */
6029 }
6030 else
6031 {
6032 /* Clear the aux field of this block so it can be added to
6033 the worklist again if necessary. */
6036 }
6038 /* Make sure each block always dominates itself. */
6041 /* If the out state of this block changed, then we need to
6042 add the successors of this block to the worklist if they
6043 are not already on the worklist. */
6045 {
6047 {
6049 {
6053 qlen++;
6056 }
6057 }
6058 }
6059 }
6060 }
6063 {
6064 /* The optimistic setting of dominators requires us to put every
6065 block on the work list initially. */
6068 {
6071 }
6075 /* We want a maximal solution, so initially assume everything post
6076 dominates everything else. */
6079 /* Mark predecessors of the exit block so we can identify them below. */
6083 /* Iterate until the worklist is empty. */
6085 {
6086 /* Take the first entry off the worklist. */
6090 qlen--;
6094 /* Compute the intersection of the post dominators of all the
6095 successor blocks.
6097 If one of the successor blocks is the EXIT block, then the
6098 intersection of the dominators of the successor blocks is
6099 defined as the null set. We can identify such blocks by the
6100 special value in the AUX field in the block structure. */
6102 {
6103 /* Do not clear the aux field for blocks which are
6104 predecessors of the EXIT block. That way we we never
6105 add them to the worklist again.
6107 The intersect of dominators of the succs of this block is
6108 defined as the null set. */
6110 }
6111 else
6112 {
6113 /* Clear the aux field of this block so it can be added to
6114 the worklist again if necessary. */
6118 }
6120 /* Make sure each block always post dominates itself. */
6123 /* If the out state of this block changed, then we need to
6124 add the successors of this block to the worklist if they
6125 are not already on the worklist. */
6129 {
6131 {
6133 {
6137 qlen++;
6140 }
6141 }
6142 }
6143 }
6144 }
6148 }
6150 /* Given DOMINATORS, compute the immediate dominators into IDOM. */
6152 void
6156 {
6162 /* Begin with tmp(n) = dom(n) - { n }. */
6164 {
6167 }
6169 /* Subtract out all of our dominator's dominators. */
6171 {
6178 }
6180 /* Find the one bit set in the bitmap and put it in the output array. */
6182 {
6185 }
6188 }
6190 /* Recompute register set/reference counts immediately prior to register
6191 allocation.
6193 This avoids problems with set/reference counts changing to/from values
6194 which have special meanings to the register allocators.
6196 Additionally, the reference counts are the primary component used by the
6197 register allocators to prioritize pseudos for allocation to hard regs.
6198 More accurate reference counts generally lead to better register allocation.
6200 F is the first insn to be scanned.
6202 LOOP_STEP denotes how much loop_depth should be incremented per
6203 loop nesting level in order to increase the ref count more for
6204 references in a loop.
6206 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
6207 possibly other information which is used by the register allocators. */
6209 void
6211 rtx f ATTRIBUTE_UNUSED;
6213 {
6216 }
6218 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
6219 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
6220 of the number of registers that died. */
6222 int
6224 sbitmap blocks;
6226 {
6230 {
6231 basic_block bb;
6232 rtx insn;
6240 {
6242 {
6247 {
6249 {
6252 {
6258 else
6261 }
6262 /* FALLTHRU */
6266 {
6271 }
6272 /* FALLTHRU */
6278 }
6279 }
6280 }
6284 }
6285 }
6288 }
6290 /* Record INSN's block as BB. */
6292 void
6294 rtx insn;
6295 basic_block bb;
6296 {
6299 {
6302 /* Add one-eighth the size so we don't keep calling xrealloc. */
6306 }
6308 }
6310 /* Record INSN's block number as BB. */
6311 /* ??? This has got to go. */
6313 void
6315 rtx insn;
6317 {
6319 }
6320 \f
6321 /* Verify the CFG consistency. This function check some CFG invariants and
6322 aborts when something is wrong. Hope that this function will help to
6323 convert many optimization passes to preserve CFG consistent.
6325 Currently it does following checks:
6327 - test head/end pointers
6328 - overlapping of basic blocks
6329 - edge list corectness
6330 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
6331 - tails of basic blocks (ensure that boundary is necesary)
6332 - scans body of the basic block for JUMP_INSN, CODE_LABEL
6333 and NOTE_INSN_BASIC_BLOCK
6334 - check that all insns are in the basic blocks
6335 (except the switch handling code, barriers and notes)
6336 - check that all returns are followed by barriers
6338 In future it can be extended check a lot of other stuff as well
6339 (reachability of basic blocks, life information, etc. etc.). */
6341 void
6343 {
6347 rtx x;
6352 /* First pass check head/end pointers and set bb_info array used by
6353 later passes. */
6355 {
6358 /* Check the head pointer and make sure that it is pointing into
6359 insn list. */
6364 {
6368 }
6370 /* Check the end pointer and make sure that it is pointing into
6371 insn list. */
6373 {
6375 {
6379 }
6384 }
6386 {
6390 }
6391 }
6393 /* Now check the basic blocks (boundaries etc.) */
6395 {
6397 /* Check corectness of edge lists */
6398 edge e;
6402 {
6404 {
6413 }
6415 {
6420 {
6423 }
6424 }
6426 }
6430 {
6432 {
6440 }
6442 {
6447 {
6450 }
6451 }
6453 }
6455 /* OK pointers are correct. Now check the header of basic
6456 block. It ought to contain optional CODE_LABEL followed
6457 by NOTE_BASIC_BLOCK. */
6460 {
6462 {
6466 }
6468 }
6472 {
6476 }
6479 {
6480 /* Do checks for empty blocks here */
6481 }
6482 else
6483 {
6486 {
6489 {
6493 }
6501 {
6504 }
6507 }
6508 }
6509 }
6515 {
6518 {
6520 num_bb_notes++;
6524 }
6527 {
6529 {
6535 /* An addr_vec is placed outside any block block. */
6540 {
6542 }
6544 /* But in any case, non-deletable labels can appear anywhere. */
6549 }
6550 }
6559 }
6568 /* Clean up. */
6570 }
6571 \f
6572 /* Functions to access an edge list with a vector representation.
6573 Enough data is kept such that given an index number, the
6574 pred and succ that edge reprsents can be determined, or
6575 given a pred and a succ, it's index number can be returned.
6576 This allows algorithms which comsume a lot of memory to
6577 represent the normally full matrix of edge (pred,succ) with a
6578 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
6579 wasted space in the client code due to sparse flow graphs. */
6581 /* This functions initializes the edge list. Basically the entire
6582 flowgraph is processed, and all edges are assigned a number,
6583 and the data structure is filed in. */
6586 {
6588 edge e;
6597 /* Determine the number of edges in the flow graph by counting successor
6598 edges on each basic block. */
6600 {
6604 num_edges++;
6605 }
6606 /* Don't forget successors of the entry block. */
6608 num_edges++;
6617 /* Follow successors of the entry block, and register these edges. */
6619 {
6621 num_edges++;
6622 }
6625 {
6628 /* Follow all successors of blocks, and register these edges. */
6630 {
6632 num_edges++;
6633 }
6634 }
6636 }
6638 /* This function free's memory associated with an edge list. */
6639 void
6642 {
6644 {
6647 }
6648 }
6650 /* This function provides debug output showing an edge list. */
6651 void
6655 {
6661 {
6665 else
6670 else
6672 }
6673 }
6675 /* This function provides an internal consistancy check of an edge list,
6676 verifying that all edges are present, and that there are no
6677 extra edges. */
6678 void
6682 {
6684 edge e;
6687 {
6691 {
6696 {
6699 }
6706 }
6707 }
6709 {
6714 {
6717 }
6724 }
6725 /* We've verified that all the edges are in the list, no lets make sure
6726 there are no spurious edges in the list. */
6730 {
6738 {
6741 }
6744 {
6747 }
6757 }
6759 {
6767 {
6770 }
6773 {
6776 }
6780 succ);
6786 }
6788 {
6796 {
6799 }
6802 {
6805 }
6809 pred);
6814 EXIT_BLOCK_PTR));
6815 }
6816 }
6818 /* This routine will determine what, if any, edge there is between
6819 a specified predecessor and successor. */
6821 int
6825 {
6828 {
6832 }
6834 }
6836 /* This function will remove an edge from the flow graph. */
6837 void
6839 edge e;
6840 {
6843 edge tmp;
6854 else
6864 else
6867 n_edges--;
6869 }
6871 /* This routine will remove any fake successor edges for a basic block.
6872 When the edge is removed, it is also removed from whatever predecessor
6873 list it is in. */
6874 static void
6876 basic_block bb;
6877 {
6878 edge e;
6880 {
6885 }
6886 }
6888 /* This routine will remove all fake edges from the flow graph. If
6889 we remove all fake successors, it will automatically remove all
6890 fake predecessors. */
6891 void
6893 {
6899 /* We've handled all successors except the entry block's. */
6901 }
6903 /* This functions will add a fake edge between any block which has no
6904 successors, and the exit block. Some data flow equations require these
6905 edges to exist. */
6906 void
6908 {
6914 }
6916 /* Redirect an edge's successor from one block to another. */
6918 void
6920 edge e;
6921 basic_block new_succ;
6922 {
6925 /* Disconnect the edge from the old successor block. */
6930 /* Reconnect the edge to the new successor block. */
6934 }
6936 /* Redirect an edge's predecessor from one block to another. */
6938 void
6940 edge e;
6941 basic_block new_pred;
6942 {
6945 /* Disconnect the edge from the old predecessor block. */
6950 /* Reconnect the edge to the new predecessor block. */
6954 }
6955 \f
6956 /* Dump the list of basic blocks in the bitmap NODES. */
6957 static void
6962 {
6968 }
6971 /* Dump the list of exiting edges in the array EDGES. */
6972 static void
6978 {
6985 }
6988 /* Dump loop related CFG information. */
6989 static void
6993 {
7000 {
7001 edge succ;
7007 }
7010 /* Dump the DFS node order. */
7012 {
7017 }
7018 }
7021 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
7022 static int
7026 {
7028 }
7031 /* Dump the loop information specified by LOOPS to the stream FILE. */
7032 void
7037 {
7049 {
7052 fprintf (file, ";; loop %d (%d to %d):\n;; header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
7064 {
7068 {
7072 {
7078 /* If the union of LOOP and OLOOP is different than
7079 the larger of LOOP and OLOOP then LOOP and OLOOP
7080 must be disjoint. */
7086 }
7087 }
7088 }
7091 {
7092 /* Print diagnostics to compare our concept of a loop with
7093 what the loop notes say. */
7104 }
7105 }
7109 }
7112 /* Free all the memory allocated for LOOPS. */
7113 void
7116 {
7118 {
7124 /* Free the loop descriptors. */
7126 {
7133 }
7143 }
7144 }
7147 /* Find the exits from the loop using the bitmap of loop nodes NODES
7148 and store in EXITS array. Return the number of exits from the
7149 loop. */
7150 static int
7154 {
7155 edge e;
7161 /* Check all nodes within the loop to see if there are any
7162 successors not in the loop. Note that a node may have multiple
7163 exiting edges. */
7167 {
7171 num_exits++;
7172 }
7173 });
7180 /* Store all exiting edges into an array. */
7184 {
7189 }
7190 });
7193 }
7196 /* Find the nodes contained within the loop with header HEADER and
7197 latch LATCH and store in NODES. Return the number of nodes within
7198 the loop. */
7199 static int
7201 basic_block header;
7202 basic_block latch;
7203 sbitmap nodes;
7204 {
7212 /* Start with only the loop header in the set of loop nodes. */
7215 num_nodes++;
7218 /* Push the loop latch on to the stack. */
7220 {
7223 num_nodes++;
7225 }
7228 {
7229 basic_block node;
7230 edge e;
7234 {
7237 /* If each ancestor not marked as part of loop, add to set of
7238 loop nodes and push on to stack. */
7241 {
7244 num_nodes++;
7246 }
7247 }
7248 }
7251 }
7254 /* Compute the depth first search order and store in the array
7255 DFS_ORDER, marking the nodes visited in VISITED. Returns the
7256 number of nodes visited. A depth first search tries to get as far
7257 away from the starting point as quickly as possible. */
7258 static int
7261 {
7265 sbitmap visited;
7267 /* Allocate stack for back-tracking up CFG. */
7271 /* Allocate bitmap to track nodes that have been visited. */
7274 /* None of the nodes in the CFG have been visited yet. */
7277 /* Push the first edge on to the stack. */
7281 {
7282 edge e;
7283 basic_block src;
7284 basic_block dest;
7286 /* Look at the edge on the top of the stack. */
7291 /* Check if the edge destination has been visited yet. */
7293 {
7294 /* Mark that we have visited the destination. */
7298 {
7299 /* Since the DEST node has been visited for the first
7300 time, check its successors. */
7302 }
7303 else
7304 {
7305 /* There are no successors for the DEST node so assign
7306 its DFS number. */
7308 }
7309 }
7310 else
7311 {
7313 {
7314 /* There are no more successors for the SRC node
7315 so assign its DFS number. */
7317 }
7321 else
7322 sp--;
7323 }
7324 }
7329 /* The number of nodes visited should not be greater than
7330 n_basic_blocks. */
7334 /* There are some nodes left in the CFG that are unreachable. */
7338 }
7341 /* Return the block for the pre-header of the loop with header
7342 HEADER where DOM specifies the dominator information. Return NULL if
7343 there is no pre-header. */
7344 static basic_block
7346 basic_block header;
7348 {
7349 basic_block pre_header;
7350 edge e;
7352 /* If block p is a predecessor of the header and is the only block
7353 that the header does not dominate, then it is the pre-header. */
7356 {
7361 {
7364 else
7365 {
7366 /* There are multiple edges into the header from outside
7367 the loop so there is no pre-header block. */
7370 }
7371 }
7372 }
7374 }
7377 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
7378 previously added. The insertion algorithm assumes that the loops
7379 are added in the order found by a depth first search of the CFG. */
7380 static void
7384 {
7387 {
7391 }
7394 {
7396 {
7400 }
7402 }
7406 }
7409 /* Build the loop hierarchy tree for LOOPS. */
7410 static void
7413 {
7421 /* Root the loop hierarchy tree with the first loop found.
7422 Since we used a depth first search this should be the
7423 outermost loop. */
7427 /* Add the remaining loops to the tree. */
7430 }
7433 /* Helper function to compute loop nesting depth and enclosed loop level
7434 for the natural loop specified by LOOP at the loop depth DEPTH.
7435 Returns the loop level. */
7436 static int
7440 {
7447 /* Traverse loop tree assigning depth and computing level as the
7448 maximum level of all the inner loops of this loop. The loop
7449 level is equivalent to the height of the loop in the loop tree
7450 and corresponds to the number of enclosed loop levels (including
7451 itself). */
7453 {
7460 }
7464 }
7467 /* Compute the loop nesting depth and enclosed loop level for the loop
7468 hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
7469 level. */
7471 static int
7474 {
7479 /* Traverse all the outer level loops. */
7481 {
7485 }
7487 }
7490 /* Find all the natural loops in the function and save in LOOPS structure
7491 and recalculate loop_depth information in basic block structures.
7492 Return the number of natural loops found. */
7494 int
7497 {
7501 edge e;
7502 sbitmap headers;
7511 /* Taking care of this degenerate case makes the rest of
7512 this code simpler. */
7516 /* Compute the dominators. */
7520 /* Count the number of loop edges (back edges). This should be the
7521 same as the number of natural loops. Also clear the loop_depth
7522 and as we work from inner->outer in a loop nest we call
7523 find_loop_nodes_find which will increment loop_depth for nodes
7524 within the current loop, which happens to enclose inner loops. */
7528 {
7531 {
7534 /* Look for back edges where a predecessor is dominated
7535 by this block. A natural loop has a single entry
7536 node (header) that dominates all the nodes in the
7537 loop. It also has single back edge to the header
7538 from a latch node. Note that multiple natural loops
7539 may share the same header. */
7541 num_loops++;
7542 }
7543 }
7546 {
7547 /* Compute depth first search order of the CFG so that outer
7548 natural loops will be found before inner natural loops. */
7552 /* Allocate loop structures. */
7553 loops->array
7562 /* Find and record information about all the natural loops
7563 in the CFG. */
7566 {
7567 basic_block header;
7569 /* Search the nodes of the CFG in DFS order that we can find
7570 outer loops first. */
7573 /* Look for all the possible latch blocks for this header. */
7575 {
7578 /* Look for back edges where a predecessor is dominated
7579 by this block. A natural loop has a single entry
7580 node (header) that dominates all the nodes in the
7581 loop. It also has single back edge to the header
7582 from a latch node. Note that multiple natural loops
7583 may share the same header. */
7586 {
7594 /* Keep track of blocks that are loop headers so
7595 that we can tell which loops should be merged. */
7600 /* Find nodes contained within the loop. */
7602 loop->num_nodes
7605 /* Compute first and last blocks within the loop.
7606 These are often the same as the loop header and
7607 loop latch respectively, but this is not always
7608 the case. */
7609 loop->first
7611 loop->last
7614 /* Find edges which exit the loop. Note that a node
7615 may have several exit edges. */
7616 loop->num_exits
7619 /* Look to see if the loop has a pre-header node. */
7620 loop->pre_header
7623 num_loops++;
7624 }
7625 }
7626 }
7628 /* Natural loops with shared headers may either be disjoint or
7629 nested. Disjoint loops with shared headers cannot be inner
7630 loops and should be merged. For now just mark loops that share
7631 headers. */
7637 }
7641 /* Save CFG derived information to avoid recomputing it. */
7645 /* Build the loop hierarchy tree. */
7648 /* Assign the loop nesting depth and enclosed loop level for each
7649 loop. */
7653 }
7656 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
7658 int
7661 edge e;
7662 {
7667 }
7670 /* Clear LOG_LINKS fields of insns in a chain. */
7672 void
7674 rtx insns;
7675 {
7676 rtx i;
7680 }
7682 /* Given a register bitmap, turn on the bits in a HARD_REG_SET that
7683 correspond to the hard registers, if any, set in that map. This
7684 could be done far more efficiently by having all sorts of special-cases
7685 with moving single words, but probably isn't worth the trouble. */
7687 void
7690 bitmap from;
7691 {
7694 EXECUTE_IF_SET_IN_BITMAP
7696 {
7700 });
7701 }