| blob | 6d0ce0b1ce6d0bb0cda2a34b66fbf7d3076685b7 |
1 /* Data flow analysis for GNU compiler.
2 Copyright (C) 1987, 88, 92-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This file contains the data flow analysis pass of the compiler. It
23 computes data flow information which tells combine_instructions
24 which insns to consider combining and controls register allocation.
26 Additional data flow information that is too bulky to record is
27 generated during the analysis, and is used at that time to create
28 autoincrement and autodecrement addressing.
30 The first step is dividing the function into basic blocks.
31 find_basic_blocks does this. Then life_analysis determines
32 where each register is live and where it is dead.
34 ** find_basic_blocks **
36 find_basic_blocks divides the current function's rtl into basic
37 blocks and constructs the CFG. The blocks are recorded in the
38 basic_block_info array; the CFG exists in the edge structures
39 referenced by the blocks.
41 find_basic_blocks also finds any unreachable loops and deletes them.
43 ** life_analysis **
45 life_analysis is called immediately after find_basic_blocks.
46 It uses the basic block information to determine where each
47 hard or pseudo register is live.
49 ** live-register info **
51 The information about where each register is live is in two parts:
52 the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
54 basic_block->global_live_at_start has an element for each basic
55 block, and the element is a bit-vector with a bit for each hard or
56 pseudo register. The bit is 1 if the register is live at the
57 beginning of the basic block.
59 Two types of elements can be added to an insn's REG_NOTES.
60 A REG_DEAD note is added to an insn's REG_NOTES for any register
61 that meets both of two conditions: The value in the register is not
62 needed in subsequent insns and the insn does not replace the value in
63 the register (in the case of multi-word hard registers, the value in
64 each register must be replaced by the insn to avoid a REG_DEAD note).
66 In the vast majority of cases, an object in a REG_DEAD note will be
67 used somewhere in the insn. The (rare) exception to this is if an
68 insn uses a multi-word hard register and only some of the registers are
69 needed in subsequent insns. In that case, REG_DEAD notes will be
70 provided for those hard registers that are not subsequently needed.
71 Partial REG_DEAD notes of this type do not occur when an insn sets
72 only some of the hard registers used in such a multi-word operand;
73 omitting REG_DEAD notes for objects stored in an insn is optional and
74 the desire to do so does not justify the complexity of the partial
75 REG_DEAD notes.
77 REG_UNUSED notes are added for each register that is set by the insn
78 but is unused subsequently (if every register set by the insn is unused
79 and the insn does not reference memory or have some other side-effect,
80 the insn is deleted instead). If only part of a multi-word hard
81 register is used in a subsequent insn, REG_UNUSED notes are made for
82 the parts that will not be used.
84 To determine which registers are live after any insn, one can
85 start from the beginning of the basic block and scan insns, noting
86 which registers are set by each insn and which die there.
88 ** Other actions of life_analysis **
90 life_analysis sets up the LOG_LINKS fields of insns because the
91 information needed to do so is readily available.
93 life_analysis deletes insns whose only effect is to store a value
94 that is never used.
96 life_analysis notices cases where a reference to a register as
97 a memory address can be combined with a preceding or following
98 incrementation or decrementation of the register. The separate
99 instruction to increment or decrement is deleted and the address
100 is changed to a POST_INC or similar rtx.
102 Each time an incrementing or decrementing address is created,
103 a REG_INC element is added to the insn's REG_NOTES list.
105 life_analysis fills in certain vectors containing information about
106 register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
107 REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
109 life_analysis sets current_function_sp_is_unchanging if the function
110 doesn't modify the stack pointer. */
112 /* TODO:
114 Split out from life_analysis:
115 - local property discovery (bb->local_live, bb->local_set)
116 - global property computation
117 - log links creation
118 - pre/post modify transformation
119 */
120 \f
140 #define obstack_chunk_alloc xmalloc
141 #define obstack_chunk_free free
144 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
145 the stack pointer does not matter. The value is tested only in
146 functions that have frame pointers.
147 No definition is equivalent to always zero. */
148 #ifndef EXIT_IGNORE_STACK
149 #define EXIT_IGNORE_STACK 0
150 #endif
152 #ifndef HAVE_epilogue
153 #define HAVE_epilogue 0
154 #endif
156 #ifndef HAVE_prologue
157 #define HAVE_prologue 0
158 #endif
160 /* The contents of the current function definition are allocated
161 in this obstack, and all are freed at the end of the function.
162 For top-level functions, this is temporary_obstack.
163 Separate obstacks are made for nested functions. */
167 /* Number of basic blocks in the current function. */
171 /* Number of edges in the current function. */
175 /* The basic block array. */
177 varray_type basic_block_info;
179 /* The special entry and exit blocks. */
193 },
194 {
206 }
207 };
209 /* Nonzero if the second flow pass has completed. */
212 /* Maximum register number used in this function, plus one. */
216 /* Indexed by n, giving various register information */
218 varray_type reg_n_info;
220 /* Size of the reg_n_info table. */
224 /* Element N is the next insn that uses (hard or pseudo) register number N
225 within the current basic block; or zero, if there is no such insn.
226 This is valid only during the final backward scan in propagate_block. */
230 /* Size of a regset for the current function,
231 in (1) bytes and (2) elements. */
236 /* Regset of regs live when calls to `setjmp'-like functions happen. */
237 /* ??? Does this exist only for the setjmp-clobbered warning message? */
239 regset regs_live_at_setjmp;
241 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
242 that have to go in the same hard reg.
243 The first two regs in the list are a pair, and the next two
244 are another pair, etc. */
245 rtx regs_may_share;
247 /* Depth within loops of basic block being scanned for lifetime analysis,
248 plus one. This is the weight attached to references to registers. */
252 /* During propagate_block, this is non-zero if the value of CC0 is live. */
256 /* During propagate_block, this contains a list of all the MEMs we are
257 tracking for dead store elimination. */
261 /* Set of registers that may be eliminable. These are handled specially
262 in updating regs_ever_live. */
266 /* The basic block structure for every insn, indexed by uid. */
268 varray_type basic_block_for_insn;
270 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
271 /* ??? Should probably be using LABEL_NUSES instead. It would take a
272 bit of surgery to be able to use or co-opt the routines in jump. */
276 /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
278 #define INSN_VOLATILE(INSN) bitmap_bit_p (uid_volatile, INSN_UID (INSN))
279 #define SET_INSN_VOLATILE(INSN) bitmap_set_bit (uid_volatile, INSN_UID (INSN))
282 /* Forward declarations */
308 basic_block));
310 basic_block));
335 #ifdef AUTO_INC_DEC
339 #endif
364 /* This function is always defined so it can be called from the
365 debugger, and it is declared extern so we don't get warnings about
366 it being unused. */
369 \f
370 /* Find basic blocks of the current function.
371 F is the first insn of the function and NREGS the number of register
372 numbers in use. */
374 void
376 rtx f;
380 {
383 /* Flush out existing data. */
385 {
390 /* Clear bb->aux on all extant basic blocks. We'll use this as a
391 tag for reuse during create_basic_block, just in case some pass
392 copies around basic block notes improperly. */
397 }
401 /* Size the basic block table. The actual structures will be allocated
402 by find_basic_blocks_1, since we want to keep the structure pointers
403 stable across calls to find_basic_blocks. */
404 /* ??? This whole issue would be much simpler if we called find_basic_blocks
405 exactly once, and thereafter we don't have a single long chain of
406 instructions at all until close to the end of compilation when we
407 actually lay them out. */
413 /* Record the block to which an insn belongs. */
414 /* ??? This should be done another way, by which (perhaps) a label is
415 tagged directly with the basic block that it starts. It is used for
416 more than that currently, but IMO that is the only valid use. */
419 #ifdef AUTO_INC_DEC
420 /* Leave space for insns life_analysis makes in some cases for auto-inc.
421 These cases are rare, so we don't need too much space. */
423 #endif
427 /* Discover the edges of our cfg. */
432 /* Delete unreachable blocks, then merge blocks when possible. */
435 {
440 }
442 /* Mark critical edges. */
446 /* Kill the data we won't maintain. */
449 #ifdef ENABLE_CHECKING
451 #endif
452 }
454 /* Count the basic blocks of the function. */
456 static int
458 rtx f;
459 {
469 {
477 {
478 count++;
479 }
481 /* Record whether this call created an edge. */
483 {
489 /* If there is a specified EH region, we have an edge. */
492 else
493 {
494 /* If there is a nonlocal goto label and the specified
495 region number isn't -1, we have an edge. (0 means
496 no throw, but might have a nonlocal goto). */
499 }
500 }
511 }
513 /* The rest of the compiler works a bit smoother when we don't have to
514 check for the edge case of do-nothing functions with no basic blocks. */
516 {
519 }
522 }
524 /* Find all basic blocks of the function whose first insn is F.
526 Collect and return a list of labels whose addresses are taken. This
527 will be used in make_edges for use with computed gotos. */
529 static rtx
531 rtx f;
532 {
542 /* We process the instructions in a slightly different way than we did
543 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
544 closed out the previous block, so that it gets attached at the proper
545 place. Since this form should be equivalent to the previous,
546 count_basic_blocks continues to use the old form as a check. */
549 {
555 {
556 /* Record whether this call created an edge. */
561 /* If there is an EH region, we have an edge. */
564 else
565 {
566 /* If there is a nonlocal goto label and the specified
567 region number isn't -1, we have an edge. (0 means
568 no throw, but might have a nonlocal goto). */
571 }
572 }
575 {
577 {
580 /* Keep a LIFO list of the currently active exception notes. */
584 {
588 }
590 /* Look for basic block notes with which to keep the
591 basic_block_info pointers stable. Unthread the note now;
592 we'll put it back at the right place in create_basic_block.
593 Or not at all if we've already found a note in this block. */
595 {
599 }
602 }
605 /* A basic block starts at a label. If we've closed one off due
606 to a barrier or some such, no need to do it again. */
608 {
609 /* While we now have edge lists with which other portions of
610 the compiler might determine a call ending a basic block
611 does not imply an abnormal edge, it will be a bit before
612 everything can be updated. So continue to emit a noop at
613 the end of such a block. */
615 {
618 }
622 }
627 /* A basic block ends at a jump. */
630 else
631 {
632 /* ??? Make a special check for table jumps. The way this
633 happens is truly and amazingly gross. We are about to
634 create a basic block that contains just a code label and
635 an addr*vec jump insn. Worse, an addr_diff_vec creates
636 its own natural loop.
638 Prevent this bit of brain damage, pasting things together
639 correctly in make_edges.
641 The correct solution involves emitting the table directly
642 on the tablejump instruction as a note, or JUMP_LABEL. */
646 {
648 n_basic_blocks--;
650 }
651 }
656 /* A basic block ends at a barrier. It may be that an unconditional
657 jump already closed the basic block -- no need to do it again. */
661 /* While we now have edge lists with which other portions of the
662 compiler might determine a call ending a basic block does not
663 imply an abnormal edge, it will be a bit before everything can
664 be updated. So continue to emit a noop at the end of such a
665 block. */
667 {
670 }
674 /* A basic block ends at a call that can either throw or
675 do a non-local goto. */
677 {
678 new_bb_inclusive:
683 new_bb_exclusive:
688 }
689 /* FALLTHRU */
693 {
697 }
699 }
702 {
703 rtx note;
705 /* Make a list of all labels referred to other than by jumps
706 (which just don't have the REG_LABEL notes).
708 Make a special exception for labels followed by an ADDR*VEC,
709 as this would be a part of the tablejump setup code.
711 Make a special exception for the eh_return_stub_label, which
712 we know isn't part of any otherwise visible control flow. */
716 {
720 ;
725 ;
726 else
727 label_value_list
729 }
730 }
731 }
740 }
742 /* Create a new basic block consisting of the instructions between
743 HEAD and END inclusive. Reuses the note and basic block struct
744 in BB_NOTE, if any. */
746 static void
750 {
751 basic_block bb;
757 {
758 /* If we found an existing note, thread it back onto the chain. */
762 else
763 {
766 }
767 }
768 else
769 {
770 /* Otherwise we must create a note and a basic block structure.
771 Since we allow basic block structs in rtl, give the struct
772 the same lifetime by allocating it off the function obstack
773 rather than using malloc. */
780 else
781 {
784 }
786 }
788 /* Always include the bb note in the block. */
797 /* Tag the block so that we know it has been used when considering
798 other basic block notes. */
800 }
801 \f
802 /* Records the basic block struct in BB_FOR_INSN, for every instruction
803 indexed by INSN_UID. MAX is the size of the array. */
805 void
808 {
816 {
823 {
830 }
831 }
832 }
834 /* Free the memory associated with the edge structures. */
836 static void
838 {
843 {
847 {
850 }
854 }
857 {
860 }
866 }
868 /* Identify the edges between basic blocks.
870 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
871 that are otherwise unreachable may be reachable with a non-local goto.
873 BB_EH_END is an array indexed by basic block number in which we record
874 the list of exception regions active at the end of the basic block. */
876 static void
878 rtx label_value_list;
879 {
884 /* Assume no computed jump; revise as we create edges. */
887 /* Heavy use of computed goto in machine-generated code can lead to
888 nearly fully-connected CFGs. In that case we spend a significant
889 amount of time searching the edge lists for duplicates. */
891 {
894 }
896 /* By nature of the way these get numbered, block 0 is always the entry. */
900 {
906 /* Examine the last instruction of the block, and discover the
907 ways we can leave the block. */
912 /* A branch. */
914 {
915 rtx tmp;
917 /* ??? Recognize a tablejump and do the right thing. */
923 {
924 rtvec vec;
929 else
936 /* Some targets (eg, ARM) emit a conditional jump that also
937 contains the out-of-range target. Scan for these and
938 add an edge if necessary. */
946 #ifdef CASE_DROPS_THROUGH
947 /* Silly VAXen. The ADDR_VEC is going to be in the way of
948 us naturally detecting fallthru into the next block. */
950 #endif
951 }
953 /* If this is a computed jump, then mark it as reaching
954 everything on the label_value_list and forced_labels list. */
956 {
964 }
966 /* Returns create an exit out. */
970 /* Otherwise, we have a plain conditional or unconditional jump. */
971 else
972 {
976 }
977 }
979 /* If this is a CALL_INSN, then mark it as reaching the active EH
980 handler for this CALL_INSN. If we're handling asynchronous
981 exceptions then any insn can reach any of the active handlers.
983 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
986 {
987 /* If there's an EH region active at the end of a block,
988 add the appropriate edges. */
992 /* If we have asynchronous exceptions, do the same for *all*
993 exception regions active in the block. */
996 {
1005 {
1009 }
1010 }
1013 {
1014 /* ??? This could be made smarter: in some cases it's possible
1015 to tell that certain calls will not do a nonlocal goto.
1017 For example, if the nested functions that do the nonlocal
1018 gotos do not have their addresses taken, then only calls to
1019 those functions or to other nested functions that use them
1020 could possibly do nonlocal gotos. */
1021 /* We do know that a REG_EH_REGION note with a value less
1022 than 0 is guaranteed not to perform a non-local goto. */
1028 }
1029 }
1031 /* We know something about the structure of the function __throw in
1032 libgcc2.c. It is the only function that ever contains eh_stub
1033 labels. It modifies its return address so that the last block
1034 returns to one of the eh_stub labels within it. So we have to
1035 make additional edges in the flow graph. */
1039 /* Find out if we can drop through to the next block. */
1044 {
1050 }
1051 }
1056 }
1058 /* Create an edge between two basic blocks. FLAGS are auxiliary information
1059 about the edge that is accumulated between calls. */
1061 static void
1066 {
1068 edge e;
1070 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1071 many edges to them, and we didn't allocate memory for it. */
1072 use_edge_cache = (edge_cache
1076 /* Make sure we don't add duplicate edges. */
1080 {
1083 }
1086 n_edges++;
1099 }
1101 /* Create an edge from a basic block to a label. */
1103 static void
1106 basic_block src;
1107 rtx label;
1109 {
1113 /* If the label was never emitted, this insn is junk, but avoid a
1114 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
1115 as a result of a syntax error and a diagnostic has already been
1116 printed. */
1122 }
1124 /* Create the edges generated by INSN in REGION. */
1126 static void
1130 basic_block src;
1131 rtx insn;
1133 {
1140 {
1143 }
1144 }
1146 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1147 dangerous if we intend to move basic blocks around. Move such notes
1148 into the following block. */
1150 static void
1152 {
1161 {
1166 {
1171 {
1172 /* Unlink from the insn chain. */
1176 /* Queue it. */
1179 }
1180 }
1185 /* Find where to insert these things. */
1191 {
1195 }
1196 }
1197 }
1199 /* Recompute eh_beg/eh_end for each basic block. */
1201 static void
1203 rtx f;
1204 {
1210 {
1215 {
1220 {
1224 }
1225 }
1228 {
1234 }
1235 }
1236 }
1238 /* Identify critical edges and set the bits appropriately. */
1240 static void
1242 {
1244 basic_block bb;
1246 /* We begin with the entry block. This is not terribly important now,
1247 but could be if a front end (Fortran) implemented alternate entry
1248 points. */
1253 {
1254 edge e;
1256 /* (1) Critical edges must have a source with multiple successors. */
1258 {
1260 {
1261 /* (2) Critical edges must have a destination with multiple
1262 predecessors. Note that we know there is at least one
1263 predecessor -- the edge we followed to get here. */
1266 else
1268 }
1269 }
1270 else
1271 {
1274 }
1279 }
1280 }
1281 \f
1282 /* Split a (typically critical) edge. Return the new block.
1283 Abort on abnormal edges.
1285 ??? The code generally expects to be called on critical edges.
1286 The case of a block ending in an unconditional jump to a
1287 block with multiple predecessors is not handled optimally. */
1289 basic_block
1291 edge edge_in;
1292 {
1294 edge edge_out;
1295 rtx bb_note;
1298 /* Abnormal edges cannot be split. */
1305 /* Remove the existing edge from the destination's pred list. */
1306 {
1312 }
1314 /* Create the new structures. */
1317 n_edges++;
1323 /* ??? This info is likely going to be out of date very soon. */
1325 {
1328 }
1329 else
1330 {
1333 }
1335 /* Wire them up. */
1351 /* Tricky case -- if there existed a fallthru into the successor
1352 (and we're not it) we must add a new unconditional jump around
1353 the new block we're actually interested in.
1355 Further, if that edge is critical, this means a second new basic
1356 block must be created to hold it. In order to simplify correct
1357 insn placement, do this before we touch the existing basic block
1358 ordering for the block we were really wanting. */
1360 {
1361 edge e;
1367 {
1368 basic_block jump_block;
1369 rtx pos;
1372 {
1373 /* Non critical -- we can simply add a jump to the end
1374 of the existing predecessor. */
1376 }
1377 else
1378 {
1379 /* We need a new block to hold the jump. The simplest
1380 way to do the bulk of the work here is to recursively
1381 call ourselves. */
1384 }
1386 /* Now add the jump insn ... */
1392 /* ... let jump know that label is in use, ... */
1396 /* ... and clear fallthru on the outgoing edge. */
1399 /* Continue splitting the interesting edge. */
1400 }
1401 }
1403 /* Place the new block just in front of the successor. */
1407 else
1410 {
1414 }
1418 /* Create the basic block note.
1420 Where we place the note can have a noticable impact on the generated
1421 code. Consider this cfg:
1424 E
1425 |
1426 0
1427 / \
1428 +->1-->2--->E
1429 | |
1430 +--+
1432 If we need to insert an insn on the edge from block 0 to block 1,
1433 we want to ensure the instructions we insert are outside of any
1434 loop notes that physically sit between block 0 and block 1. Otherwise
1435 we confuse the loop optimizer into thinking the loop is a phony. */
1444 else
1449 /* Not quite simple -- for non-fallthru edges, we must adjust the
1450 predecessor's jump instruction to target our new block. */
1452 {
1460 /* ??? Recognize a tablejump and adjust all matching cases. */
1466 {
1467 rtvec vec;
1472 else
1477 {
1481 }
1483 /* Handle casesi dispatch insns */
1489 {
1491 new_label);
1494 }
1495 }
1496 else
1497 {
1498 /* This would have indicated an abnormal edge. */
1502 /* A return instruction can't be redirected. */
1506 /* If the insn doesn't go where we think, we're confused. */
1511 }
1515 }
1518 }
1520 /* Queue instructions for insertion on an edge between two basic blocks.
1521 The new instructions and basic blocks (if any) will not appear in the
1522 CFG until commit_edge_insertions is called. */
1524 void
1526 rtx pattern;
1527 edge e;
1528 {
1529 /* We cannot insert instructions on an abnormal critical edge.
1530 It will be easier to find the culprit if we die now. */
1537 else
1544 }
1546 /* Update the CFG for the instructions queued on edge E. */
1548 static void
1550 edge e;
1551 {
1553 basic_block bb;
1555 /* Figure out where to put these things. If the destination has
1556 one predecessor, insert there. Except for the exit block. */
1559 {
1562 /* Get the location correct wrt a code label, and "nice" wrt
1563 a basic block note, and before everything else. */
1572 else
1574 }
1576 /* If the source has one successor and the edge is not abnormal,
1577 insert there. Except for the entry block. */
1581 {
1584 {
1585 /* ??? Is it possible to wind up with non-simple jumps? Perhaps
1586 a jump with delay slots already filled? */
1591 }
1592 else
1593 {
1594 /* We'd better be fallthru, or we've lost track of what's what. */
1599 }
1600 }
1602 /* Otherwise we must split the edge. */
1603 else
1604 {
1607 }
1609 /* Now that we've found the spot, do the insertion. */
1613 /* Set the new block number for these insns, if structure is allocated. */
1615 {
1616 rtx i;
1619 }
1622 {
1626 }
1627 else
1628 {
1632 }
1633 }
1635 /* Update the CFG for all queued instructions. */
1637 void
1639 {
1641 basic_block bb;
1646 {
1650 {
1654 }
1659 }
1660 }
1661 \f
1662 /* Delete all unreachable basic blocks. */
1664 static void
1666 {
1669 edge e;
1675 /* Use basic_block->aux as a marker. Clear them all. */
1680 /* Add our starting points to the worklist. Almost always there will
1681 be only one. It isn't inconcievable that we might one day directly
1682 support Fortran alternate entry points. */
1685 {
1688 /* Mark the block with a handy non-null value. */
1690 }
1692 /* Iterate: find everything reachable from what we've already seen. */
1695 {
1700 {
1703 }
1704 }
1706 /* Delete all unreachable basic blocks. Count down so that we don't
1707 interfere with the block renumbering that happens in delete_block. */
1712 {
1716 /* This block was found. Tidy up the mark. */
1718 else
1720 }
1722 /* Fix up edges that now fall through, or rather should now fall through
1723 but previously required a jump around now deleted blocks. Simplify
1724 the search by only examining blocks numerically adjacent, since this
1725 is how find_basic_blocks created them. */
1728 {
1731 edge s;
1733 /* We care about simple conditional or unconditional jumps with
1734 a single successor.
1736 If we had a conditional branch to the next instruction when
1737 find_basic_blocks was called, then there will only be one
1738 out edge for the block which ended with the conditional
1739 branch (since we do not create duplicate edges).
1741 Furthermore, the edge will be marked as a fallthru because we
1742 merge the flags for the duplicate edges. So we do not want to
1743 check that the edge is not a FALLTHRU edge. */
1747 /* If the jump insn has side effects, we can't tidy the edge. */
1751 }
1753 /* If we deleted an exception handler, we may have EH region begin/end
1754 blocks to remove as well. */
1759 }
1761 /* Find EH regions for which there is no longer a handler, and delete them. */
1763 static void
1765 {
1766 rtx insn;
1772 {
1775 {
1777 /* A NULL handler indicates a region is no longer needed,
1778 as long as it isn't the target of a rethrow. */
1780 {
1783 }
1784 }
1785 }
1786 }
1788 /* Return true if NOTE is not one of the ones that must be kept paired,
1789 so that we may simply delete them. */
1791 static int
1793 rtx note;
1794 {
1797 }
1799 /* Unlink a chain of insns between START and FINISH, leaving notes
1800 that must be paired. */
1802 void
1805 {
1806 /* Unchain the insns one by one. It would be quicker to delete all
1807 of these with a single unchaining, rather than one at a time, but
1808 we need to keep the NOTE's. */
1810 rtx next;
1813 {
1816 ;
1818 ;
1819 else
1825 }
1826 }
1828 /* Delete the insns in a (non-live) block. We physically delete every
1829 non-deleted-note insn, and update the flow graph appropriately.
1831 Return nonzero if we deleted an exception handler. */
1833 /* ??? Preserving all such notes strikes me as wrong. It would be nice
1834 to post-process the stream to remove empty blocks, loops, ranges, etc. */
1836 static int
1838 basic_block b;
1839 {
1843 /* If the head of this block is a CODE_LABEL, then it might be the
1844 label for an exception handler which can't be reached.
1846 We need to remove the label from the exception_handler_label list
1847 and remove the associated NOTE_INSN_EH_REGION_BEG and
1848 NOTE_INSN_EH_REGION_END notes. */
1855 {
1859 {
1861 {
1862 /* Found a match, splice this label out of the EH label list. */
1867 /* Remove the handler from all regions */
1871 }
1873 }
1875 /* This label may be referenced by code solely for its value, or
1876 referenced by static data, or something. We have determined
1877 that it is not reachable, but cannot delete the label itself.
1878 Save code space and continue to delete the balance of the block,
1879 along with properly updating the cfg. */
1881 {
1882 /* If we've only got one of these, skip the whole deleting
1883 insns thing. */
1887 }
1888 }
1890 /* Selectively unlink the insn chain. Include any BARRIER that may
1891 follow the basic block. */
1897 no_delete_insns:
1899 /* Remove the edges into and out of this block. Note that there may
1900 indeed be edges in, if we are removing an unreachable loop. */
1901 {
1905 {
1910 n_edges--;
1912 }
1914 {
1919 n_edges--;
1921 }
1925 }
1927 /* Remove the basic block from the array, and compact behind it. */
1931 }
1933 /* Remove block B from the basic block array and compact behind it. */
1935 static void
1937 basic_block b;
1938 {
1942 {
1946 }
1949 n_basic_blocks--;
1950 }
1952 /* Delete INSN by patching it out. Return the next insn. */
1954 static rtx
1956 rtx insn;
1957 {
1968 else
1974 /* If deleting a jump, decrement the use count of the label. Deleting
1975 the label itself should happen in the normal course of block merging. */
1980 }
1982 /* True if a given label can be deleted. */
1984 static int
1986 rtx label;
1987 {
1988 rtx x;
2003 /* User declared labels must be preserved. */
2008 }
2010 /* Blocks A and B are to be merged into a single block. A has no incoming
2011 fallthru edge, so it can be moved before B without adding or modifying
2012 any jumps (aside from the jump from A to B). */
2014 static int
2017 {
2024 /* We want to delete the BARRIER after the end of the insns we are
2025 going to move. If we don't find a BARRIER, then do nothing. This
2026 can happen in some cases if we have labels we can not delete.
2028 Similarly, do nothing if we can not delete the label at the start
2029 of the target block. */
2035 else
2038 /* Move block and loop notes out of the chain so that we do not
2039 disturb their order.
2041 ??? A better solution would be to squeeze out all the non-nested notes
2042 and adjust the block trees appropriately. Even better would be to have
2043 a tighter connection between block trees and rtl so that this is not
2044 necessary. */
2047 /* Scramble the insn chain. */
2052 {
2055 }
2057 /* Swap the records for the two blocks around. Although we are deleting B,
2058 A is now where B was and we want to compact the BB array from where
2059 A used to be. */
2066 /* Now blocks A and B are contiguous. Merge them. */
2070 }
2072 /* Blocks A and B are to be merged into a single block. B has no outgoing
2073 fallthru edge, so it can be moved after A without adding or modifying
2074 any jumps (aside from the jump from A to B). */
2076 static int
2079 {
2085 /* We want to delete the BARRIER after the end of the insns we are
2086 going to move. If we don't find a BARRIER, then do nothing. This
2087 can happen in some cases if we have labels we can not delete.
2089 Similarly, do nothing if we can not delete the label at the start
2090 of the target block. */
2096 else
2099 /* Move block and loop notes out of the chain so that we do not
2100 disturb their order.
2102 ??? A better solution would be to squeeze out all the non-nested notes
2103 and adjust the block trees appropriately. Even better would be to have
2104 a tighter connection between block trees and rtl so that this is not
2105 necessary. */
2108 /* Scramble the insn chain. */
2111 /* Now blocks A and B are contiguous. Merge them. */
2115 {
2118 }
2121 }
2123 /* Blocks A and B are to be merged into a single block. The insns
2124 are already contiguous, hence `nomove'. */
2126 static void
2129 {
2130 edge e;
2134 /* If there was a CODE_LABEL beginning B, delete it. */
2138 {
2139 /* Detect basic blocks with nothing but a label. This can happen
2140 in particular at the end of a function. */
2144 }
2146 /* Delete the basic block note. */
2149 {
2153 }
2155 /* If there was a jump out of A, delete it. */
2158 {
2159 rtx prev;
2165 #ifdef HAVE_cc0
2166 /* If this was a conditional jump, we need to also delete
2167 the insn that set cc0. */
2170 {
2176 }
2177 #endif
2179 /* Note that a->head != a->end, since we should have at least a
2180 bb note plus the jump, so prev != insn. */
2183 }
2185 /* By definition, there should only be one successor of A, and that is
2186 B. Free that edge struct. */
2187 n_edges--;
2190 /* Adjust the edges out of B for the new owner. */
2195 /* Reassociate the insns of B with A. */
2197 {
2200 {
2203 }
2205 }
2208 /* Compact the basic block array. */
2210 }
2212 /* Attempt to merge basic blocks that are potentially non-adjacent.
2213 Return true iff the attempt succeeded. */
2215 static int
2217 edge e;
2219 {
2220 /* If B has a fallthru edge to C, no need to move anything. */
2222 {
2223 /* If a label still appears somewhere and we cannot delete the label,
2224 then we cannot merge the blocks. The edge was tidied already. */
2234 {
2237 }
2240 }
2241 else
2242 {
2243 edge tmp_edge;
2244 basic_block d;
2248 /* We must make sure to not munge nesting of exception regions,
2249 lexical blocks, and loop notes.
2251 The first is taken care of by requiring that the active eh
2252 region at the end of one block always matches the active eh
2253 region at the beginning of the next block.
2255 The later two are taken care of by squeezing out all the notes. */
2257 /* ??? A throw/catch edge (or any abnormal edge) should be rarely
2258 executed and we may want to treat blocks which have two out
2259 edges, one normal, one abnormal as only having one edge for
2260 block merging purposes. */
2272 /* If B does not have an incoming fallthru, and the exception regions
2273 match, then it can be moved immediately before C without introducing
2274 or modifying jumps.
2276 C can not be the first block, so we do not have to worry about
2277 accessing a non-existent block. */
2284 /* Otherwise, we're going to try to move C after B. Make sure the
2285 exception regions match.
2287 If B is the last basic block, then we must not try to access the
2288 block structure for block B + 1. Luckily in that case we do not
2289 need to worry about matching exception regions. */
2293 {
2294 /* If C does not have an outgoing fallthru, then it can be moved
2295 immediately after B without introducing or modifying jumps. */
2299 /* Otherwise, we'll need to insert an extra jump, and possibly
2300 a new block to contain it. */
2301 /* ??? Not implemented yet. */
2302 }
2305 }
2306 }
2308 /* Top level driver for merge_blocks. */
2310 static void
2312 {
2315 /* Attempt to merge blocks as made possible by edge removal. If a block
2316 has only one successor, and the successor has only one predecessor,
2317 they may be combined. */
2320 {
2322 edge s;
2324 /* A loop because chains of blocks might be combineable. */
2330 /* If the jump insn has side effects, we can't kill the edge. */
2336 /* Don't get confused by the index shift caused by deleting blocks. */
2338 }
2339 }
2341 /* The given edge should potentially a fallthru edge. If that is in
2342 fact true, delete the unconditional jump and barriers that are in
2343 the way. */
2345 static void
2347 edge e;
2349 {
2350 rtx q;
2352 /* ??? In a late-running flow pass, other folks may have deleted basic
2353 blocks by nopping out blocks, leaving multiple BARRIERs between here
2354 and the target label. They ought to be chastized and fixed.
2356 We can also wind up with a sequence of undeletable labels between
2357 one block and the next.
2359 So search through a sequence of barriers, labels, and notes for
2360 the head of block C and assert that we really do fall through. */
2365 /* Remove what will soon cease being the jump insn from the source block.
2366 If block B consisted only of this single jump, turn it into a deleted
2367 note. */
2370 {
2371 #ifdef HAVE_cc0
2372 /* If this was a conditional jump, we need to also delete
2373 the insn that set cc0. */
2376 #endif
2379 {
2383 }
2384 else
2386 }
2388 /* Selectively unlink the sequence. */
2393 }
2395 /* Discover and record the loop depth at the head of each basic block. */
2397 void
2400 {
2403 /* The loop infrastructure does the real job for us. */
2410 }
2411 \f
2412 /* Perform data flow analysis.
2413 F is the first insn of the function and NREGS the number of register numbers
2414 in use. */
2416 void
2418 rtx f;
2422 {
2423 #ifdef ELIMINABLE_REGS
2426 #endif
2429 /* Record which registers will be eliminated. We use this in
2430 mark_used_regs. */
2434 #ifdef ELIMINABLE_REGS
2437 #else
2439 #endif
2441 /* Allocate a bitmap to be filled in by record_volatile_insns. */
2444 /* We want alias analysis information for local dead store elimination. */
2462 }
2464 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2465 Search for REGNO. If found, abort if it is not wider than word_mode. */
2467 static int
2471 {
2476 {
2480 }
2482 }
2484 /* A subroutine of verify_local_live_at_start. Search through insns
2485 between HEAD and END looking for register REGNO. */
2487 static void
2491 {
2493 {
2500 }
2502 /* We didn't find the register at all. Something's way screwy. */
2504 }
2506 /* A subroutine of update_life_info. Verify that there are no untoward
2507 changes in live_at_start during a local update. */
2509 static void
2511 regset new_live_at_start;
2512 basic_block bb;
2513 {
2515 {
2516 /* After reload, there are no pseudos, nor subregs of multi-word
2517 registers. The regsets should exactly match. */
2520 }
2521 else
2522 {
2525 /* Find the set of changed registers. */
2529 {
2530 /* No registers should die. */
2533 /* Verify that the now-live register is wider than word_mode. */
2535 });
2536 }
2537 }
2539 /* Updates death notes starting with the basic blocks set in BLOCKS.
2541 If LOCAL_ONLY, such as after splitting or peepholeing, we are only
2542 expecting local modifications to basic blocks. If we find extra
2543 registers live at the beginning of a block, then we either killed
2544 useful data, or we have a broken split that wants data not provided.
2545 If we find registers removed from live_at_start, that means we have
2546 a broken peephole that is killing a register it shouldn't.
2548 ??? This is not true in one situation -- when a pre-reload splitter
2549 generates subregs of a multi-word pseudo, current life analysis will
2550 lose the kill. So we _can_ have a pseudo go live. How irritating.
2552 BLOCK_FOR_INSN is assumed to be correct.
2554 ??? PROP_FLAGS should not contain PROP_LOG_LINKS. Need to set up
2555 reg_next_use for that. Including PROP_REG_INFO does not refresh
2556 regs_ever_live unless the caller resets it to zero. */
2558 void
2560 sbitmap blocks;
2563 {
2564 regset tmp;
2569 /* For a global update, we go through the relaxation process again. */
2571 {
2575 /* If asked, remove notes from the blocks we'll update. */
2578 }
2581 {
2586 prop_flags);
2590 });
2593 }
2595 /* Free the variables allocated by find_basic_blocks.
2597 KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed. */
2599 void
2602 {
2604 {
2607 }
2610 {
2619 }
2620 }
2622 /* Return nonzero if the destination of SET equals the source. */
2623 static int
2625 rtx set;
2626 {
2641 }
2643 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2644 value to itself. */
2645 static int
2647 rtx insn;
2648 {
2651 /* Insns carrying these notes are useful later on. */
2659 {
2661 /* If nothing but SETs of registers to themselves,
2662 this insn can also be deleted. */
2664 {
2673 }
2676 }
2678 }
2680 static void
2682 rtx x;
2683 rtx pat ATTRIBUTE_UNUSED;
2685 {
2687 /* The stack pointer is only modified indirectly as the result
2688 of a push until later in flow. See the comments in rtl.texi
2689 regarding Embedded Side-Effects on Addresses. */
2697 }
2699 /* Record which insns refer to any volatile memory
2700 or for any reason can't be deleted just because they are dead stores.
2701 Also, delete any insns that copy a register to itself.
2702 And see if the stack pointer is modified. */
2703 static void
2705 rtx f;
2706 {
2707 rtx insn;
2709 {
2714 {
2719 /* A SET that makes space on the stack cannot be dead.
2720 (Such SETs occur only for allocating variable-size data,
2721 so they will always have a PLUS or MINUS according to the
2722 direction of stack growth.)
2723 Even if this function never uses this stack pointer value,
2724 signal handlers do! */
2727 #ifdef STACK_GROWS_DOWNWARD
2729 #else
2731 #endif
2735 /* Delete (in effect) any obvious no-op moves. */
2737 {
2741 }
2742 }
2744 /* Check if insn modifies the stack pointer. */
2748 notice_stack_pointer_modification,
2749 NULL);
2750 }
2751 }
2753 /* Mark a register in SET. Hard registers in large modes get all
2754 of their component registers set as well. */
2755 static void
2757 regset set;
2758 rtx reg;
2759 {
2764 {
2768 }
2769 }
2771 /* Mark those regs which are needed at the end of the function as live
2772 at the end of the last basic block. */
2773 static void
2775 regset set;
2776 {
2777 tree type;
2780 /* If exiting needs the right stack value, consider the stack pointer
2781 live at the end of the function. */
2783 || ! EXIT_IGNORE_STACK
2784 || (! FRAME_POINTER_REQUIRED
2785 && ! current_function_calls_alloca
2788 {
2790 }
2792 /* Mark the frame pointer if needed at the end of the function. If
2793 we end up eliminating it, it will be removed from the live list
2794 of each basic block by reload. */
2797 {
2799 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2800 /* If they are different, also mark the hard frame pointer as live */
2802 #endif
2803 }
2805 #ifdef PIC_OFFSET_TABLE_REGNUM
2806 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
2807 /* Many architectures have a GP register even without flag_pic.
2808 Assume the pic register is not in use, or will be handled by
2809 other means, if it is not fixed. */
2812 #endif
2813 #endif
2815 /* Mark all global registers, and all registers used by the epilogue
2816 as being live at the end of the function since they may be
2817 referenced by our caller. */
2820 #ifdef EPILOGUE_USES
2822 #endif
2823 )
2826 /* Mark all call-saved registers that we actaully used. */
2828 {
2832 }
2834 /* Mark function return value. */
2835 /* ??? Only do this after reload. Consider a non-void function that
2836 omits a return statement. Across that edge we'll have the return
2837 register live, and no set for it. Thus the return register will
2838 be live back through the CFG to the entry, and thus we die. A
2839 possible solution is to emit a clobber at exits without returns. */
2844 {
2845 rtx outgoing;
2851 #ifdef FUNCTION_OUTGOING_VALUE
2853 #else
2855 #endif
2860 {
2863 /* Check for a NULL entry, used to indicate that the parameter
2864 goes on the stack and in registers. */
2868 {
2872 }
2873 }
2874 else
2876 }
2877 }
2879 /* Determine which registers are live at the start of each
2880 basic block of the function whose first insn is F.
2881 NREGS is the number of registers used in F.
2882 We allocate the vector basic_block_live_at_start
2883 and the regsets that it points to, and fill them with the data.
2884 regset_size and regset_bytes are also set here. */
2886 static void
2888 rtx f;
2891 {
2897 /* Allocate and zero out many data structures
2898 that will record the data from lifetime analysis. */
2905 /* Assume that the stack pointer is unchanging if alloca hasn't been used.
2906 This will be cleared by record_volatile_insns if it encounters an insn
2907 which modifies the stack pointer. */
2911 /* Find the set of registers live on function exit. Do this before
2912 zeroing regs_ever_live, as we use that data post-reload. */
2915 /* The post-reload life analysis have (on a global basis) the same
2916 registers live as was computed by reload itself. elimination
2917 Otherwise offsets and such may be incorrect.
2919 Reload will make some registers as live even though they do not
2920 appear in the rtl. */
2925 /* Compute register life at block boundaries. It'd be nice to
2926 begin with just the exit and noreturn blocks, but that set
2927 is not immediately handy. */
2928 {
2929 sbitmap blocks;
2934 }
2936 /* The only pseudos that are live at the beginning of the function are
2937 those that were not set anywhere in the function. local-alloc doesn't
2938 know how to handle these correctly, so mark them as not local to any
2939 one basic block. */
2945 /* Now the life information is accurate. Make one more pass over each
2946 basic block to delete dead stores, create autoincrement addressing
2947 and record how many times each register is used, is set, or dies. */
2948 {
2949 regset tmp;
2953 {
2958 }
2961 }
2963 /* We have a problem with any pseudoreg that lives across the setjmp.
2964 ANSI says that if a user variable does not change in value between
2965 the setjmp and the longjmp, then the longjmp preserves it. This
2966 includes longjmp from a place where the pseudo appears dead.
2967 (In principle, the value still exists if it is in scope.)
2968 If the pseudo goes in a hard reg, some other value may occupy
2969 that hard reg where this pseudo is dead, thus clobbering the pseudo.
2970 Conclusion: such a pseudo must not go in a hard reg. */
2973 {
2975 {
2978 }
2979 });
2981 /* Restore regs_ever_live that was provided by reload. */
2985 /* Clean up. */
2988 }
2990 /* Propagate global life info around the graph of basic blocks. Begin
2991 considering blocks with their corresponding bit set in BLOCKS_IN.
2992 BLOCKS_OUT is set for every block that was changed. */
2994 static void
2998 {
3006 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
3007 because the `head == tail' style test for an empty queue doesn't
3008 work with a full queue. */
3013 /* Clear out the garbage that might be hanging out in bb->aux. */
3017 /* Queue the blocks set in the initial mask. Do this in reverse block
3018 number order so that we are more likely for the first round to do
3019 useful work. We use AUX non-null to flag that the block is queued. */
3021 {
3025 });
3030 {
3032 basic_block bb;
3033 edge e;
3040 /* Begin by propogating live_at_start from the successor blocks. */
3043 {
3046 }
3049 {
3052 }
3054 /* On our first pass through this block, we'll go ahead and continue.
3055 Recognize first pass by local_set NULL. On subsequent passes, we
3056 get to skip out early if live_at_end wouldn't have changed. */
3059 {
3062 }
3063 else
3064 {
3065 /* If any bits were removed from live_at_end, we'll have to
3066 rescan the block. This wouldn't be necessary if we had
3067 precalculated local_live, however with PROP_SCAN_DEAD_CODE
3068 local_live is really dependant on live_at_end. */
3074 {
3075 /* Find the set of changed bits. Take this opportunity
3076 to notice that this set is empty and early out. */
3083 /* If any of the changed bits overlap with local_set,
3084 we'll have to rescan the block. Detect overlap by
3085 the AND with ~local_set turning off bits. */
3087 BITMAP_AND_COMPL);
3088 }
3089 }
3091 /* Let our caller know that BB changed enough to require its
3092 death notes updated. */
3096 {
3097 /* Add to live_at_start the set of all registers in
3098 new_live_at_end that aren't in the old live_at_end. */
3101 BITMAP_AND_COMPL);
3109 }
3110 else
3111 {
3114 /* Rescan the block insn by insn to turn (a copy of) live_at_end
3115 into live_at_start. */
3119 /* If live_at start didn't change, no need to go farther. */
3124 }
3126 /* Queue all predecessors of BB so that we may re-examine
3127 their live_at_end. */
3129 {
3132 {
3137 }
3138 }
3139 }
3145 {
3148 });
3151 }
3152 \f
3153 /* Subroutines of life analysis. */
3155 /* Allocate the permanent data structures that represent the results
3156 of life analysis. Not static since used also for stupid life analysis. */
3158 void
3160 {
3164 {
3169 }
3171 ENTRY_BLOCK_PTR->global_live_at_end
3173 EXIT_BLOCK_PTR->global_live_at_start
3177 }
3179 void
3181 {
3184 /* Recalculate the register space, in case it has grown. Old style
3185 vector oriented regsets would set regset_{size,bytes} here also. */
3188 /* Reset all the data we'll collect in propagate_block and its
3189 subroutines. */
3191 {
3198 }
3199 }
3201 /* Compute the registers live at the beginning of a basic block
3202 from those live at the end.
3204 When called, OLD contains those live at the end.
3205 On return, it contains those live at the beginning.
3206 FIRST and LAST are the first and last insns of the basic block.
3208 FINAL is nonzero if we are doing the final pass which is not
3209 for computing the life info (since that has already been done)
3210 but for acting on it. On this pass, we delete dead stores,
3211 set up the logical links and dead-variables lists of instructions,
3212 and merge instructions for autoincrement and autodecrement addresses.
3214 SIGNIFICANT is nonzero only the first time for each basic block.
3215 If it is nonzero, it points to a regset in which we store
3216 a 1 for each register that is set within the block.
3218 BNUM is the number of the basic block. */
3220 static void
3223 rtx first;
3224 rtx last;
3225 regset significant;
3228 {
3230 rtx prev;
3231 regset live;
3232 regset dead;
3234 /* Find the loop depth for this block. Ignore loop level changes in the
3235 middle of the basic block -- for register allocation purposes, the
3236 important uses will be in the blocks wholely contained within the loop
3237 not in the loop pre-header or post-trailer. */
3246 {
3249 /* Process the regs live at the end of the block.
3250 Mark them as not local to any one basic block. */
3252 {
3254 });
3255 }
3257 /* Scan the block an insn at a time from end to beginning. */
3260 {
3264 {
3265 /* If this is a call to `setjmp' et al,
3266 warn if any non-volatile datum is live. */
3271 }
3273 /* Update the life-status of regs for this insn.
3274 First DEAD gets which regs are set in this insn
3275 then LIVE gets which regs are used in this insn.
3276 Then the regs live before the insn
3277 are those live after, with DEAD regs turned off,
3278 and then LIVE regs turned on. */
3281 {
3288 {
3290 /* Don't delete something that refers to volatile storage! */
3294 }
3296 /* We almost certainly don't want to delete prologue or epilogue
3297 instructions. Warn about probable compiler losage. */
3299 && insn_is_dead
3300 && reload_completed
3303 {
3307 }
3309 /* If an instruction consists of just dead store(s) on final pass,
3310 "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
3311 We could really delete it with delete_insn, but that
3312 can cause trouble for first or last insn in a basic block. */
3314 {
3315 rtx inote;
3316 /* If the insn referred to a label, note that the label is
3317 now less used. */
3319 {
3321 {
3323 rtx next;
3326 /* If this label was attached to an ADDR_VEC, it's
3327 safe to delete the ADDR_VEC. In fact, it's pretty much
3328 mandatory to delete it, because the ADDR_VEC may
3329 be referencing labels that no longer exist. */
3335 {
3345 }
3346 }
3347 }
3353 /* CC0 is now known to be dead. Either this insn used it,
3354 in which case it doesn't anymore, or clobbered it,
3355 so the next insn can't use it. */
3358 /* If this insn is copying the return value from a library call,
3359 delete the entire library call. */
3361 {
3367 {
3372 }
3373 }
3375 }
3380 /* See if this is an increment or decrement that can be
3381 merged into a following memory address. */
3382 #ifdef AUTO_INC_DEC
3383 {
3386 /* Does this instruction increment or decrement a register? */
3395 /* Ok, look for a following memory ref we can combine with.
3396 If one is found, change the memory ref to a PRE_INC
3397 or PRE_DEC, cancel this insn, and return 1.
3398 Return 0 if nothing has been done. */
3401 }
3404 /* If this is not the final pass, and this insn is copying the
3405 value of a library call and it's dead, don't scan the
3406 insns that perform the library call, so that the call's
3407 arguments are not marked live. */
3409 {
3410 /* Mark the dest reg as `significant'. */
3416 }
3422 /* We have an insn to pop a constant amount off the stack.
3423 (Such insns use PLUS regardless of the direction of the stack,
3424 and any insn to adjust the stack by a constant is always a pop.)
3425 These insns, if not dead stores, have no effect on life. */
3426 ;
3427 else
3428 {
3429 /* Any regs live at the time of a call instruction
3430 must not go in a register clobbered by calls.
3431 Find all regs now live and record this for them. */
3436 {
3438 });
3440 /* LIVE gets the regs used in INSN;
3441 DEAD gets those set by it. Dead insns don't make anything
3442 live. */
3447 /* If an insn doesn't use CC0, it becomes dead since we
3448 assume that every insn clobbers it. So show it dead here;
3449 mark_used_regs will set it live if it is referenced. */
3455 /* Sometimes we may have inserted something before INSN (such as
3456 a move) when we make an auto-inc. So ensure we will scan
3457 those insns. */
3458 #ifdef AUTO_INC_DEC
3460 #endif
3463 {
3466 rtx note;
3469 note;
3475 /* Each call clobbers all call-clobbered regs that are not
3476 global or fixed. Note that the function-value reg is a
3477 call-clobbered reg, and mark_set_regs has already had
3478 a chance to handle it. */
3483 {
3487 }
3489 /* The stack ptr is used (honorarily) by a CALL insn. */
3492 /* Calls may also reference any of the global registers,
3493 so they are made live. */
3500 /* Calls also clobber memory. */
3502 }
3504 /* Update OLD for the registers used or set. */
3508 }
3510 /* On final pass, update counts of how many insns each reg is live
3511 at. */
3515 }
3516 flushed: ;
3519 }
3524 }
3525 \f
3526 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3527 (SET expressions whose destinations are registers dead after the insn).
3528 NEEDED is the regset that says which regs are alive after the insn.
3530 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3532 If X is the entire body of an insn, NOTES contains the reg notes
3533 pertaining to the insn. */
3535 static int
3537 rtx x;
3538 regset needed;
3540 rtx notes ATTRIBUTE_UNUSED;
3541 {
3544 #ifdef AUTO_INC_DEC
3545 /* If flow is invoked after reload, we must take existing AUTO_INC
3546 expresions into account. */
3548 {
3550 {
3552 {
3555 /* Don't delete insns to set global regs. */
3559 }
3560 }
3561 }
3562 #endif
3564 /* If setting something that's a reg or part of one,
3565 see if that register's altered value will be live. */
3568 {
3571 /* A SET that is a subroutine call cannot be dead. */
3575 #ifdef HAVE_cc0
3578 #endif
3581 {
3582 rtx temp;
3583 /* Walk the set of memory locations we are currently tracking
3584 and see if one is an identical match to this memory location.
3585 If so, this memory write is dead (remember, we're walking
3586 backwards from the end of the block to the start. */
3589 {
3593 }
3594 }
3601 {
3604 /* Don't delete insns to set global regs. */
3606 /* Make sure insns to set frame pointer aren't deleted. */
3609 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3612 #endif
3613 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3614 /* Make sure insns to set arg pointer are never deleted
3615 (if the arg pointer isn't fixed, there will be a USE for
3616 it, so we can treat it normally). */
3618 #endif
3622 /* If this is a hard register, verify that subsequent words are
3623 not needed. */
3625 {
3631 }
3634 }
3635 }
3637 /* If performing several activities,
3638 insn is dead if each activity is individually dead.
3639 Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
3640 that's inside a PARALLEL doesn't make the insn worth keeping. */
3642 {
3652 }
3654 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
3655 is not necessarily true for hard registers. */
3661 /* We do not check other CLOBBER or USE here. An insn consisting of just
3662 a CLOBBER or just a USE should not be deleted. */
3664 }
3666 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
3667 return 1 if the entire library call is dead.
3668 This is true if X copies a register (hard or pseudo)
3669 and if the hard return reg of the call insn is dead.
3670 (The caller should have tested the destination of X already for death.)
3672 If this insn doesn't just copy a register, then we don't
3673 have an ordinary libcall. In that case, cse could not have
3674 managed to substitute the source for the dest later on,
3675 so we can assume the libcall is dead.
3677 NEEDED is the bit vector of pseudoregs live before this insn.
3678 NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
3680 static int
3682 rtx x;
3683 regset needed;
3684 rtx note;
3685 rtx insn;
3686 {
3690 {
3693 {
3695 rtx call_pat;
3698 /* Find the call insn. */
3702 /* If there is none, do nothing special,
3703 since ordinary death handling can understand these insns. */
3707 /* See if the hard reg holding the value is dead.
3708 If this is a PARALLEL, find the call within it. */
3711 {
3717 /* This may be a library call that is returning a value
3718 via invisible pointer. Do nothing special, since
3719 ordinary death handling can understand these insns. */
3724 }
3727 }
3728 }
3730 }
3732 /* Return 1 if register REGNO was used before it was set, i.e. if it is
3733 live at function entry. Don't count global register variables, variables
3734 in registers that can be used for function arg passing, or variables in
3735 fixed hard registers. */
3737 int
3740 {
3749 }
3751 /* 1 if register REGNO was alive at a place where `setjmp' was called
3752 and was set more than once or is an argument.
3753 Such regs may be clobbered by `longjmp'. */
3755 int
3758 {
3765 }
3766 \f
3767 /* INSN references memory, possibly using autoincrement addressing modes.
3768 Find any entries on the mem_set_list that need to be invalidated due
3769 to an address change. */
3770 static void
3772 rtx insn;
3773 {
3776 {
3778 {
3781 rtx next;
3784 {
3787 {
3788 /* Splice temp out of list. */
3791 else
3794 }
3795 else
3798 }
3799 }
3800 }
3801 }
3803 /* Process the registers that are set within X. Their bits are set to
3804 1 in the regset DEAD, because they are dead prior to this insn.
3806 If INSN is nonzero, it is the insn being processed.
3808 FLAGS is the set of operations to perform. */
3810 static void
3812 regset needed;
3813 regset dead;
3814 rtx x;
3815 rtx insn;
3816 regset significant;
3818 {
3824 {
3827 {
3832 }
3833 }
3834 }
3836 /* Process a single SET rtx, X. */
3838 static void
3840 regset needed;
3841 regset dead;
3842 rtx x;
3843 rtx insn;
3844 regset significant;
3846 {
3850 /* Some targets place small structures in registers for
3851 return values of functions. We have to detect this
3852 case specially here to get correct flow information. */
3855 {
3862 }
3864 /* Modifying just one hardware register of a multi-reg value
3865 or just a byte field of a register
3866 does not mean the value from before this insn is now dead.
3867 But it does mean liveness of that register at the end of the block
3868 is significant.
3870 Within mark_set_1, however, we treat it as if the register is
3871 indeed modified. mark_used_regs will, however, also treat this
3872 register as being used. Thus, we treat these insns as setting a
3873 new value for the register as a function of its old value. This
3874 cases LOG_LINKS to be made appropriately and this will help combine. */
3881 /* If this set is a MEM, then it kills any aliased writes.
3882 If this set is a REG, then it kills any MEMs which use the reg. */
3884 {
3887 {
3890 rtx next;
3893 {
3899 {
3900 /* Splice this entry out of the list. */
3903 else
3906 }
3907 else
3910 }
3911 }
3913 /* If the memory reference had embedded side effects (autoincrement
3914 address modes. Then we may need to kill some entries on the
3915 memory set list. */
3920 /* We do not know the size of a BLKmode store, so we do not track
3921 them for redundant store elimination. */
3923 /* There are no REG_INC notes for SP, so we can't assume we'll see
3924 everything that invalidates it. To be safe, don't eliminate any
3925 stores though SP; none of them should be redundant anyway. */
3928 }
3934 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3937 #endif
3938 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3940 #endif
3942 /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
3943 {
3947 /* Mark it as a significant register for this basic block. */
3951 /* Mark it as dead before this insn. */
3954 /* A hard reg in a wide mode may really be multiple registers.
3955 If so, mark all of them just like the first. */
3957 {
3960 /* Nothing below is needed for the stack pointer; get out asap.
3961 Eg, log links aren't needed, since combine won't use them. */
3967 {
3976 }
3977 }
3979 /* Additional data to record if this is the final pass. */
3982 {
3990 /* If this is a hard reg, record this function uses the reg. */
3993 {
3999 {
4000 /* The next use is no longer "next", since a store
4001 intervenes. */
4003 }
4007 {
4010 }
4011 }
4012 else
4013 {
4014 /* The next use is no longer "next", since a store
4015 intervenes. */
4019 /* Keep track of which basic blocks each reg appears in. */
4022 {
4028 /* Count (weighted) references, stores, etc. This counts a
4029 register twice if it is modified, but that is correct. */
4033 /* The insns where a reg is live are normally counted
4034 elsewhere, but we want the count to include the insn
4035 where the reg is set, and the normal counting mechanism
4036 would not count it. */
4038 }
4039 }
4042 {
4044 {
4045 /* Make a logical link from the next following insn
4046 that uses this register, back to this insn.
4047 The following insns have already been processed.
4049 We don't build a LOG_LINK for hard registers containing
4050 in ASM_OPERANDs. If these registers get replaced,
4051 we might wind up changing the semantics of the insn,
4052 even if reload can make what appear to be valid
4053 assignments later. */
4058 }
4059 }
4061 {
4066 {
4067 /* Note that dead stores have already been deleted
4068 when possible. If we get here, we have found a
4069 dead store that cannot be eliminated (because the
4070 same insn does something useful). Indicate this
4071 by marking the reg being set as dying here. */
4074 }
4075 }
4076 else
4077 {
4079 {
4080 /* This is a case where we have a multi-word hard register
4081 and some, but not all, of the words of the register are
4082 needed in subsequent insns. Write REG_UNUSED notes
4083 for those parts that were not needed. This case should
4084 be rare. */
4092 = (alloc_EXPR_LIST
4096 }
4097 }
4098 }
4099 }
4101 {
4104 }
4106 /* If this is the last pass and this is a SCRATCH, show it will be dying
4107 here and count it. */
4109 {
4113 }
4114 }
4115 \f
4116 #ifdef AUTO_INC_DEC
4118 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
4119 reference. */
4121 static void
4123 regset needed;
4124 rtx x;
4125 rtx insn;
4126 {
4129 rtx set;
4131 /* Here we detect use of an index register which might be good for
4132 postincrement, postdecrement, preincrement, or predecrement. */
4138 {
4141 rtx use;
4142 rtx incr;
4145 /* Is the next use an increment that might make auto-increment? */
4150 /* Can't add side effects to jumps; if reg is spilled and
4151 reloaded, there's no way to store back the altered value. */
4156 && ((HAVE_POST_INCREMENT
4158 || (HAVE_POST_DECREMENT
4160 || (HAVE_PRE_INCREMENT
4162 || (HAVE_PRE_DECREMENT
4164 /* Make sure this reg appears only once in this insn. */
4167 {
4174 {
4175 /* This is the simple case. Try to make the auto-inc. If
4176 we can't, we are done. Otherwise, we will do any
4177 needed updates below. */
4182 }
4184 /* PREV_INSN used here to check the semi-open interval
4185 [insn,incr). */
4187 /* We must also check for sets of q as q may be
4188 a call clobbered hard register and there may
4189 be a call between PREV_INSN (insn) and incr. */
4191 {
4192 /* We have *p followed sometime later by q = p+size.
4193 Both p and q must be live afterward,
4194 and q is not used between INSN and its assignment.
4195 Change it to q = p, ...*q..., q = q+size.
4196 Then fall into the usual case. */
4198 basic_block bb;
4209 /* If we can't make the auto-inc, or can't make the
4210 replacement into Y, exit. There's no point in making
4211 the change below if we can't do the auto-inc and doing
4212 so is not correct in the pre-inc case. */
4221 /* We now know we'll be doing this change, so emit the
4222 new insn(s) and do the updates. */
4228 /* INCR will become a NOTE and INSN won't contain a
4229 use of ADDR. If a use of ADDR was just placed in
4230 the insn before INSN, make that the next use.
4231 Otherwise, invalidate it. */
4236 else
4242 /* REGNO is now used in INCR which is below INSN, but
4243 it previously wasn't live here. If we don't mark
4244 it as needed, we'll put a REG_DEAD note for it
4245 on this insn, which is incorrect. */
4248 /* If there are any calls between INSN and INCR, show
4249 that REGNO now crosses them. */
4253 }
4254 else
4257 /* If we haven't returned, it means we were able to make the
4258 auto-inc, so update the status. First, record that this insn
4259 has an implicit side effect. */
4264 /* Modify the old increment-insn to simply copy
4265 the already-incremented value of our register. */
4269 /* If that makes it a no-op (copying the register into itself) delete
4270 it so it won't appear to be a "use" and a "set" of this
4271 register. */
4273 {
4277 }
4280 {
4281 /* Count an extra reference to the reg. When a reg is
4282 incremented, spilling it is worse, so we want to make
4283 that less likely. */
4286 /* Count the increment as a setting of the register,
4287 even though it isn't a SET in rtl. */
4289 }
4290 }
4291 }
4292 }
4294 \f
4295 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
4296 This is done assuming the registers needed from X
4297 are those that have 1-bits in NEEDED.
4299 FLAGS is the set of enabled operations.
4301 INSN is the containing instruction. If INSN is dead, this function is not
4302 called. */
4304 static void
4306 regset needed;
4307 regset live;
4308 rtx x;
4310 rtx insn;
4311 {
4316 retry:
4319 {
4330 #ifdef HAVE_cc0
4334 #endif
4337 /* If we are clobbering a MEM, mark any registers inside the address
4338 as being used. */
4344 /* Don't bother watching stores to mems if this is not the
4345 final pass. We'll not be deleting dead stores this round. */
4347 {
4348 /* Invalidate the data for the last MEM stored, but only if MEM is
4349 something that can be stored into. */
4353 else
4354 {
4357 rtx next;
4360 {
4363 {
4364 /* Splice temp out of the list. */
4367 else
4370 }
4371 else
4374 }
4375 }
4377 /* If the memory reference had embedded side effects (autoincrement
4378 address modes. Then we may need to kill some entries on the
4379 memory set list. */
4382 }
4384 #ifdef AUTO_INC_DEC
4387 #endif
4397 /* While we're here, optimize this case. */
4400 /* In case the SUBREG is not of a register, don't optimize */
4402 {
4405 }
4407 /* ... fall through ... */
4410 /* See a register other than being set
4411 => mark it as needed. */
4414 {
4420 /* A hard reg in a wide mode may really be multiple registers.
4421 If so, mark all of them just like the first. */
4423 {
4426 /* For stack ptr or fixed arg pointer,
4427 nothing below can be necessary, so waste no more time. */
4429 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4432 #endif
4433 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4435 #endif
4438 {
4439 /* If this is a register we are going to try to eliminate,
4440 don't mark it live here. If we are successful in
4441 eliminating it, it need not be live unless it is used for
4442 pseudos, in which case it will have been set live when
4443 it was allocated to the pseudos. If the register will not
4444 be eliminated, reload will set it live at that point. */
4449 }
4450 /* No death notes for global register variables;
4451 their values are live after this function exits. */
4453 {
4457 }
4461 {
4468 }
4469 }
4472 {
4473 /* Record where each reg is used, so when the reg
4474 is set we know the next insn that uses it. */
4477 }
4479 {
4481 {
4482 /* If a hard reg is being used,
4483 record that this function does use it. */
4488 do
4491 }
4492 else
4493 {
4494 /* Keep track of which basic block each reg appears in. */
4503 /* Count (weighted) number of uses of each reg. */
4506 }
4507 }
4509 /* Record and count the insns in which a reg dies.
4510 If it is used in this insn and was dead below the insn
4511 then it dies in this insn. If it was set in this insn,
4512 we do not make a REG_DEAD note; likewise if we already
4513 made such a note. */
4516 {
4519 #if 0
4521 #endif
4522 )
4523 {
4524 /* Check for the case where the register dying partially
4525 overlaps the register set by this insn. */
4528 {
4532 }
4534 /* If none of the words in X is needed, make a REG_DEAD
4535 note. Otherwise, we must make partial REG_DEAD notes. */
4537 {
4541 }
4542 else
4543 {
4546 /* Don't make a REG_DEAD note for a part of a register
4547 that is set in the insn. */
4554 = (alloc_EXPR_LIST
4558 }
4559 }
4560 }
4561 }
4565 {
4569 /* If storing into MEM, don't show it as being used. But do
4570 show the address as being used. */
4572 {
4573 #ifdef AUTO_INC_DEC
4576 #endif
4580 }
4582 /* Storing in STRICT_LOW_PART is like storing in a reg
4583 in that this SET might be dead, so ignore it in TESTREG.
4584 but in some other ways it is like using the reg.
4586 Storing in a SUBREG or a bit field is like storing the entire
4587 register in that if the register's value is not used
4588 then this SET is not needed. */
4593 {
4601 /* Modifying a single register in an alternate mode
4602 does not use any of the old value. But these other
4603 ways of storing in a register do use the old value. */
4606 ;
4607 else
4611 }
4613 /* If this is a store into a register,
4614 recursively scan the value being stored. */
4621 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4624 #endif
4625 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4627 #endif
4628 ))
4629 /* We used to exclude global_regs here, but that seems wrong.
4630 Storing in them is like storing in mem. */
4631 {
4636 }
4637 }
4641 /* ??? This info should have been gotten from mark_regs_live_at_end,
4642 as applied to the EXIT block, and propagated along the edge that
4643 connects this block to the EXIT. */
4650 {
4651 /* Traditional and volatile asm instructions must be considered to use
4652 and clobber all hard registers, all pseudo-registers and all of
4653 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
4655 Consider for instance a volatile asm that changes the fpu rounding
4656 mode. An insn should not be moved across this even if it only uses
4657 pseudo-regs because it might give an incorrectly rounded result.
4659 ?!? Unfortunately, marking all hard registers as live causes massive
4660 problems for the register allocator and marking all pseudos as live
4661 creates mountains of uninitialized variable warnings.
4663 So for now, just clear the memory set list and mark any regs
4664 we can find in ASM_OPERANDS as used. */
4668 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
4669 We can not just fall through here since then we would be confused
4670 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
4671 traditional asms unlike their normal usage. */
4673 {
4679 }
4681 }
4686 }
4688 /* Recursively scan the operands of this expression. */
4690 {
4695 {
4697 {
4698 /* Tail recursive case: save a function call level. */
4700 {
4703 }
4705 }
4707 {
4711 }
4712 }
4713 }
4714 }
4715 \f
4716 #ifdef AUTO_INC_DEC
4718 static int
4720 rtx insn;
4721 {
4722 /* Find the next use of this reg. If in same basic block,
4723 make it do pre-increment or pre-decrement if appropriate. */
4731 /* Don't do this if the reg dies, or gets set in y; a standard addressing
4732 mode would be better. */
4735 {
4736 /* We have found a suitable auto-increment
4737 and already changed insn Y to do it.
4738 So flush this increment-instruction. */
4742 /* Count a reference to this reg for the increment
4743 insn we are deleting. When a reg is incremented.
4744 spilling it is worse, so we want to make that
4745 less likely. */
4747 {
4750 }
4752 }
4754 }
4756 /* Try to change INSN so that it does pre-increment or pre-decrement
4757 addressing on register REG in order to add AMOUNT to REG.
4758 AMOUNT is negative for pre-decrement.
4759 Returns 1 if the change could be made.
4760 This checks all about the validity of the result of modifying INSN. */
4762 static int
4765 HOST_WIDE_INT amount;
4766 {
4769 /* Nonzero if we can try to make a pre-increment or pre-decrement.
4770 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
4772 /* Nonzero if we can try to make a post-increment or post-decrement.
4773 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
4774 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
4775 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
4778 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
4781 /* From the sign of increment, see which possibilities are conceivable
4782 on this target machine. */
4796 /* It is not safe to add a side effect to a jump insn
4797 because if the incremented register is spilled and must be reloaded
4798 there would be no way to store the incremented value back in memory. */
4807 {
4810 }
4818 /* See if this combination of instruction and addressing mode exists. */
4826 /* Record that this insn now has an implicit side effect on X. */
4829 }
4832 \f
4833 /* Find the place in the rtx X where REG is used as a memory address.
4834 Return the MEM rtx that so uses it.
4835 If PLUSCONST is nonzero, search instead for a memory address equivalent to
4836 (plus REG (const_int PLUSCONST)).
4838 If such an address does not appear, return 0.
4839 If REG appears more than once, or is used other than in such an address,
4840 return (rtx)1. */
4842 rtx
4845 rtx reg;
4846 HOST_WIDE_INT plusconst;
4847 {
4864 {
4865 /* If REG occurs inside a MEM used in a bit-field reference,
4866 that is unacceptable. */
4869 }
4875 {
4877 {
4883 }
4885 {
4888 {
4894 }
4895 }
4896 }
4899 }
4900 \f
4901 /* Write information about registers and basic blocks into FILE.
4902 This is part of making a debugging dump. */
4904 void
4907 {
4914 {
4936 {
4941 else
4945 }
4949 }
4953 {
4971 {
4975 }
4976 else
4981 {
4985 }
4986 else
4990 }
4993 }
4995 void
4997 {
4999 }
5001 static void
5004 edge e;
5006 {
5013 else
5017 {
5020 };
5028 {
5035 else
5038 }
5040 }
5041 }
5043 \f
5044 /* Like print_rtl, but also print out live information for the start of each
5045 basic block. */
5047 void
5050 rtx rtx_first;
5051 {
5056 else
5057 {
5069 {
5071 rtx x;
5076 {
5084 }
5085 }
5088 {
5090 basic_block bb;
5093 {
5098 {
5103 });
5105 }
5122 }
5127 }
5130 {
5135 }
5136 }
5138 /* Compute dominator relationships using new flow graph structures. */
5139 void
5143 {
5146 edge e;
5149 /* Allocate a worklist array/queue. Entries are only added to the
5150 list if they were not already on the list. So the size is
5151 bounded by the number of basic blocks. */
5159 {
5160 /* The optimistic setting of dominators requires us to put every
5161 block on the work list initially. */
5163 {
5166 }
5168 /* We want a maximal solution, so initially assume everything dominates
5169 everything else. */
5172 /* Mark successors of the entry block so we can identify them below. */
5176 /* Iterate until the worklist is empty. */
5178 {
5179 /* Take the first entry off the worklist. */
5183 /* Compute the intersection of the dominators of all the
5184 predecessor blocks.
5186 If one of the predecessor blocks is the ENTRY block, then the
5187 intersection of the dominators of the predecessor blocks is
5188 defined as the null set. We can identify such blocks by the
5189 special value in the AUX field in the block structure. */
5191 {
5192 /* Do not clear the aux field for blocks which are
5193 successors of the ENTRY block. That way we we never
5194 add them to the worklist again.
5196 The intersect of dominators of the preds of this block is
5197 defined as the null set. */
5199 }
5200 else
5201 {
5202 /* Clear the aux field of this block so it can be added to
5203 the worklist again if necessary. */
5206 }
5208 /* Make sure each block always dominates itself. */
5211 /* If the out state of this block changed, then we need to
5212 add the successors of this block to the worklist if they
5213 are not already on the worklist. */
5215 {
5217 {
5219 {
5222 }
5223 }
5224 }
5225 }
5226 }
5229 {
5230 /* The optimistic setting of dominators requires us to put every
5231 block on the work list initially. */
5233 {
5236 }
5238 /* We want a maximal solution, so initially assume everything post
5239 dominates everything else. */
5242 /* Mark predecessors of the exit block so we can identify them below. */
5246 /* Iterate until the worklist is empty. */
5248 {
5249 /* Take the first entry off the worklist. */
5253 /* Compute the intersection of the post dominators of all the
5254 successor blocks.
5256 If one of the successor blocks is the EXIT block, then the
5257 intersection of the dominators of the successor blocks is
5258 defined as the null set. We can identify such blocks by the
5259 special value in the AUX field in the block structure. */
5261 {
5262 /* Do not clear the aux field for blocks which are
5263 predecessors of the EXIT block. That way we we never
5264 add them to the worklist again.
5266 The intersect of dominators of the succs of this block is
5267 defined as the null set. */
5269 }
5270 else
5271 {
5272 /* Clear the aux field of this block so it can be added to
5273 the worklist again if necessary. */
5277 }
5279 /* Make sure each block always post dominates itself. */
5282 /* If the out state of this block changed, then we need to
5283 add the successors of this block to the worklist if they
5284 are not already on the worklist. */
5288 {
5290 {
5292 {
5295 }
5296 }
5297 }
5298 }
5299 }
5301 }
5303 /* Given DOMINATORS, compute the immediate dominators into IDOM. */
5305 void
5309 {
5315 /* Begin with tmp(n) = dom(n) - { n }. */
5317 {
5320 }
5322 /* Subtract out all of our dominator's dominators. */
5324 {
5331 }
5333 /* Find the one bit set in the bitmap and put it in the output array. */
5335 {
5338 }
5341 }
5343 /* Count for a single SET rtx, X. */
5345 static void
5347 rtx x;
5348 {
5352 /* Find the register that's set/clobbered. */
5360 {
5365 }
5368 {
5371 {
5372 /* Count (weighted) references, stores, etc. This counts a
5373 register twice if it is modified, but that is correct. */
5377 }
5378 }
5379 }
5381 /* Increment REG_N_SETS for each SET or CLOBBER found in X; also increment
5382 REG_N_REFS by the current loop depth for each SET or CLOBBER found. */
5384 static void
5386 rtx x;
5387 {
5393 {
5396 {
5400 }
5401 }
5402 }
5404 /* Increment REG_N_REFS by the current loop depth each register reference
5405 found in X. */
5407 static void
5409 rtx x;
5410 {
5413 retry:
5416 {
5428 #ifdef HAVE_cc0
5431 #endif
5434 /* If we are clobbering a MEM, mark any registers inside the address
5435 as being used. */
5441 /* While we're here, optimize this case. */
5444 /* In case the SUBREG is not of a register, don't optimize */
5446 {
5449 }
5451 /* ... fall through ... */
5459 {
5463 /* If storing into MEM, don't show it as being used. But do
5464 show the address as being used. */
5466 {
5470 }
5472 /* Storing in STRICT_LOW_PART is like storing in a reg
5473 in that this SET might be dead, so ignore it in TESTREG.
5474 but in some other ways it is like using the reg.
5476 Storing in a SUBREG or a bit field is like storing the entire
5477 register in that if the register's value is not used
5478 then this SET is not needed. */
5483 {
5484 /* Modifying a single register in an alternate mode
5485 does not use any of the old value. But these other
5486 ways of storing in a register do use the old value. */
5489 ;
5490 else
5494 }
5496 /* If this is a store into a register,
5497 recursively scan the value being stored. */
5502 {
5507 }
5508 }
5513 }
5515 /* Recursively scan the operands of this expression. */
5517 {
5522 {
5524 {
5525 /* Tail recursive case: save a function call level. */
5527 {
5530 }
5532 }
5534 {
5538 }
5539 }
5540 }
5541 }
5543 /* Recompute register set/reference counts immediately prior to register
5544 allocation.
5546 This avoids problems with set/reference counts changing to/from values
5547 which have special meanings to the register allocators.
5549 Additionally, the reference counts are the primary component used by the
5550 register allocators to prioritize pseudos for allocation to hard regs.
5551 More accurate reference counts generally lead to better register allocation.
5553 F is the first insn to be scanned.
5554 LOOP_STEP denotes how much loop_depth should be incremented per
5555 loop nesting level in order to increase the ref count more for references
5556 in a loop.
5558 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
5559 possibly other information which is used by the register allocators. */
5561 void
5563 rtx f ATTRIBUTE_UNUSED;
5565 {
5566 rtx insn;
5570 /* Clear out the old data. */
5573 {
5576 }
5578 /* Scan each insn in the chain and count how many times each register is
5579 set/used. */
5582 {
5586 {
5588 {
5589 rtx links;
5591 /* This call will increment REG_N_SETS for each SET or CLOBBER
5592 of a register in INSN. It will also increment REG_N_REFS
5593 by the loop depth for each set of a register in INSN. */
5596 /* count_reg_sets does not detect autoincrement address modes, so
5597 detect them here by looking at the notes attached to INSN. */
5599 {
5601 /* Count (weighted) references, stores, etc. This counts a
5602 register twice if it is modified, but that is correct. */
5604 }
5606 /* This call will increment REG_N_REFS by the current loop depth for
5607 each reference to a register in INSN. */
5610 /* count_reg_references will not include counts for arguments to
5611 function calls, so detect them here by examining the
5612 CALL_INSN_FUNCTION_USAGE data. */
5614 {
5615 rtx note;
5618 note;
5622 }
5623 }
5626 }
5627 }
5628 }
5630 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
5631 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
5632 of the number of registers that died. */
5634 int
5636 sbitmap blocks;
5638 {
5642 {
5643 basic_block bb;
5644 rtx insn;
5652 {
5654 {
5659 {
5661 {
5664 {
5670 else
5673 }
5674 /* FALLTHRU */
5678 {
5683 }
5684 /* FALLTHRU */
5690 }
5691 }
5692 }
5696 }
5697 }
5700 }
5702 /* Record INSN's block as BB. */
5704 void
5706 rtx insn;
5707 basic_block bb;
5708 {
5711 {
5714 /* Add one-eighth the size so we don't keep calling xrealloc. */
5718 }
5720 }
5722 /* Record INSN's block number as BB. */
5723 /* ??? This has got to go. */
5725 void
5727 rtx insn;
5729 {
5731 }
5732 \f
5733 /* Verify the CFG consistency. This function check some CFG invariants and
5734 aborts when something is wrong. Hope that this function will help to
5735 convert many optimization passes to preserve CFG consistent.
5737 Currently it does following checks:
5739 - test head/end pointers
5740 - overlapping of basic blocks
5741 - edge list corectness
5742 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
5743 - tails of basic blocks (ensure that boundary is necesary)
5744 - scans body of the basic block for JUMP_INSN, CODE_LABEL
5745 and NOTE_INSN_BASIC_BLOCK
5746 - check that all insns are in the basic blocks
5747 (except the switch handling code, barriers and notes)
5749 In future it can be extended check a lot of other stuff as well
5750 (reachability of basic blocks, life information, etc. etc.). */
5752 void
5754 {
5758 rtx x;
5763 /* First pass check head/end pointers and set bb_info array used by
5764 later passes. */
5766 {
5769 /* Check the head pointer and make sure that it is pointing into
5770 insn list. */
5775 {
5779 }
5781 /* Check the end pointer and make sure that it is pointing into
5782 insn list. */
5784 {
5786 {
5790 }
5795 }
5797 {
5801 }
5802 }
5804 /* Now check the basic blocks (boundaries etc.) */
5806 {
5808 /* Check corectness of edge lists */
5809 edge e;
5813 {
5815 {
5824 }
5826 {
5831 {
5834 }
5835 }
5837 }
5841 {
5843 {
5851 }
5853 {
5858 {
5861 }
5862 }
5864 }
5866 /* OK pointers are correct. Now check the header of basic
5867 block. It ought to contain optional CODE_LABEL followed
5868 by NOTE_BASIC_BLOCK. */
5871 {
5873 {
5877 }
5879 }
5883 {
5887 }
5890 {
5891 /* Do checks for empty blocks here */
5892 }
5893 else
5894 {
5897 {
5900 {
5904 }
5912 {
5915 }
5918 }
5919 }
5920 }
5924 {
5926 {
5928 {
5934 /* An addr_vec is placed outside any block block. */
5939 {
5941 }
5943 /* But in any case, non-deletable labels can appear anywhere. */
5948 }
5949 }
5952 }
5957 /* Clean up. */
5959 }
5960 \f
5961 /* Functions to access an edge list with a vector representation.
5962 Enough data is kept such that given an index number, the
5963 pred and succ that edge reprsents can be determined, or
5964 given a pred and a succ, it's index number can be returned.
5965 This allows algorithms which comsume a lot of memory to
5966 represent the normally full matrix of edge (pred,succ) with a
5967 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
5968 wasted space in the client code due to sparse flow graphs. */
5970 /* This functions initializes the edge list. Basically the entire
5971 flowgraph is processed, and all edges are assigned a number,
5972 and the data structure is filed in. */
5975 {
5977 edge e;
5986 /* Determine the number of edges in the flow graph by counting successor
5987 edges on each basic block. */
5989 {
5993 num_edges++;
5994 }
5995 /* Don't forget successors of the entry block. */
5997 num_edges++;
6006 /* Follow successors of the entry block, and register these edges. */
6008 {
6010 num_edges++;
6011 }
6014 {
6017 /* Follow all successors of blocks, and register these edges. */
6019 {
6021 num_edges++;
6022 }
6023 }
6025 }
6027 /* This function free's memory associated with an edge list. */
6028 void
6031 {
6033 {
6036 }
6037 }
6039 /* This function provides debug output showing an edge list. */
6040 void
6044 {
6050 {
6054 else
6059 else
6061 }
6062 }
6064 /* This function provides an internal consistancy check of an edge list,
6065 verifying that all edges are present, and that there are no
6066 extra edges. */
6067 void
6071 {
6073 edge e;
6076 {
6080 {
6085 {
6088 }
6095 }
6096 }
6098 {
6103 {
6106 }
6113 }
6114 /* We've verified that all the edges are in the list, no lets make sure
6115 there are no spurious edges in the list. */
6119 {
6127 {
6130 }
6133 {
6136 }
6146 }
6148 {
6156 {
6159 }
6162 {
6165 }
6169 succ);
6175 }
6177 {
6185 {
6188 }
6191 {
6194 }
6198 pred);
6203 EXIT_BLOCK_PTR));
6204 }
6205 }
6207 /* This routine will determine what, if any, edge there is between
6208 a specified predecessor and successor. */
6210 int
6214 {
6217 {
6221 }
6223 }
6225 /* This function will remove an edge from the flow graph. */
6226 static void
6228 edge e;
6229 {
6232 edge tmp;
6243 else
6253 else
6256 n_edges--;
6258 }
6260 /* This routine will remove any fake successor edges for a basic block.
6261 When the edge is removed, it is also removed from whatever predecessor
6262 list it is in. */
6263 static void
6265 basic_block bb;
6266 {
6267 edge e;
6269 {
6274 }
6275 }
6277 /* This routine will remove all fake edges from the flow graph. If
6278 we remove all fake successors, it will automatically remove all
6279 fake predecessors. */
6280 void
6282 {
6288 /* We've handled all successors except the entry block's. */
6290 }
6292 /* This functions will add a fake edge between any block which has no
6293 successors, and the exit block. Some data flow equations require these
6294 edges to exist. */
6295 void
6297 {
6303 }
6304 \f
6305 /* Dump the list of basic blocks in the bitmap NODES. */
6306 static void
6311 {
6317 }
6320 /* Dump the list of exiting edges in the array EDGES. */
6321 static void
6327 {
6334 }
6337 /* Dump loop related CFG information. */
6338 static void
6342 {
6349 {
6350 edge succ;
6356 }
6359 /* Dump the DFS node order. */
6361 {
6366 }
6367 }
6370 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
6371 static int
6375 {
6377 }
6380 /* Dump the loop information specified by LOOPS to the stream FILE. */
6381 void
6386 {
6397 {
6400 fprintf (file, ";; loop %d (%d to %d):\n;; header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
6412 {
6416 {
6420 {
6426 /* If the union of LOOP and OLOOP is different than
6427 the larger of LOOP and OLOOP then LOOP and OLOOP
6428 must be disjoint. */
6434 }
6435 }
6436 }
6439 {
6440 /* Print diagnostics to compare our concept of a loop with
6441 what the loop notes say. */
6452 }
6453 }
6457 }
6460 /* Free all the memory allocated for LOOPS. */
6461 void
6464 {
6466 {
6472 /* Free the loop descriptors. */
6474 {
6481 }
6491 }
6492 }
6495 /* Find the exits from the loop using the bitmap of loop nodes NODES
6496 and store in EXITS array. Return the number of exits from the
6497 loop. */
6498 static int
6502 {
6503 edge e;
6509 /* Check all nodes within the loop to see if there are any
6510 successors not in the loop. Note that a node may have multiple
6511 exiting edges. */
6515 {
6519 num_exits++;
6520 }
6521 });
6528 /* Store all exiting edges into an array. */
6532 {
6537 }
6538 });
6541 }
6544 /* Find the nodes contained within the loop with header HEADER and
6545 latch LATCH and store in NODES. Return the number of nodes within
6546 the loop. */
6547 static int
6549 basic_block header;
6550 basic_block latch;
6551 sbitmap nodes;
6552 {
6560 /* Start with only the loop header in the set of loop nodes. */
6563 num_nodes++;
6566 /* Push the loop latch on to the stack. */
6568 {
6571 num_nodes++;
6573 }
6576 {
6577 basic_block node;
6578 edge e;
6582 {
6585 /* If each ancestor not marked as part of loop, add to set of
6586 loop nodes and push on to stack. */
6589 {
6592 num_nodes++;
6594 }
6595 }
6596 }
6599 }
6602 /* Compute the depth first search order and store in the array
6603 DFS_ORDER, marking the nodes visited in VISITED. Returns the
6604 number of nodes visited. */
6605 static int
6608 {
6609 edge e;
6613 sbitmap visited;
6615 /* Allocate stack for back-tracking up CFG. */
6619 /* Allocate bitmap to track nodes that have been visited. */
6622 /* None of the nodes in the CFG have been visited yet. */
6625 /* Start with the first successor edge from the entry block. */
6628 {
6632 /* Mark that we have visited this node. */
6636 /* If this node has not been visited before, push the current
6637 edge on to the stack and proceed with the first successor
6638 edge of this node. */
6641 {
6644 }
6645 else
6646 {
6649 {
6650 /* DEST has no successors (for example, a non-returning
6651 function is called) so do not push the current edge
6652 but carry on with its next successor. */
6655 }
6658 {
6661 /* Pop edge off stack. */
6664 }
6666 }
6667 }
6671 /* The number of nodes visited should not be greater than
6672 n_basic_blocks. */
6676 /* There are some nodes left in the CFG that are unreachable. */
6680 }
6683 /* Return the block for the pre-header of the loop with header
6684 HEADER where DOM specifies the dominator information. Return NULL if
6685 there is no pre-header. */
6686 static basic_block
6688 basic_block header;
6690 {
6691 basic_block pre_header;
6692 edge e;
6694 /* If block p is a predecessor of the header and is the only block
6695 that the header does not dominate, then it is the pre-header. */
6698 {
6703 {
6706 else
6707 {
6708 /* There are multiple edges into the header from outside
6709 the loop so there is no pre-header block. */
6712 }
6713 }
6714 }
6716 }
6719 /* Add LOOP to the loop hierarchy tree so that it is a sibling or a
6720 descendant of ROOT. */
6721 static void
6725 {
6732 {
6734 {
6736 {
6737 /* Add LOOP as a sibling or descendent of OUTER->INNER. */
6739 }
6740 else
6741 {
6742 /* Add LOOP as child of OUTER. */
6746 }
6748 }
6749 }
6750 /* Add LOOP as a sibling of ROOT. */
6754 }
6757 /* Build the loop hierarchy tree for LOOPS. */
6758 static void
6761 {
6769 /* Root the loop hierarchy tree with the first loop found.
6770 Since we used a depth first search this should be the
6771 outermost loop. */
6775 /* Add the remaining loops to the tree. */
6778 }
6781 /* Helper function to compute loop nesting depth and enclosed loop level
6782 for the natural loop specified by LOOP at the loop depth DEPTH.
6783 Returns the loop level. */
6784 static int
6788 {
6795 /* Traverse loop tree assigning depth and computing level as the
6796 maximum level of all the inner loops of this loop. The loop
6797 level is equivalent to the height of the loop in the loop tree
6798 and corresponds to the number of enclosed loop levels. */
6800 {
6807 }
6811 }
6814 /* Compute the loop nesting depth and enclosed loop level for the loop
6815 hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
6816 level. */
6818 static int
6821 {
6823 }
6826 /* Find all the natural loops in the function and save in LOOPS structure
6827 and recalculate loop_depth information in basic block structures.
6828 Return the number of natural loops found. */
6830 int
6833 {
6837 edge e;
6838 sbitmap headers;
6847 /* Taking care of this degenerate case makes the rest of
6848 this code simpler. */
6852 /* Compute the dominators. */
6856 /* Count the number of loop edges (back edges). This should be the
6857 same as the number of natural loops. Also clear the loop_depth
6858 and as we work from inner->outer in a loop nest we call
6859 find_loop_nodes_find which will increment loop_depth for nodes
6860 within the current loop, which happens to enclose inner loops. */
6864 {
6867 {
6870 /* Look for back edges where a predecessor is dominated
6871 by this block. A natural loop has a single entry
6872 node (header) that dominates all the nodes in the
6873 loop. It also has single back edge to the header
6874 from a latch node. Note that multiple natural loops
6875 may share the same header. */
6877 num_loops++;
6878 }
6879 }
6882 {
6883 /* Compute depth first search order of the CFG so that outer
6884 natural loops will be found before inner natural loops. */
6888 /* Allocate loop structures. */
6889 loops->array
6898 /* Find and record information about all the natural loops
6899 in the CFG. */
6902 {
6903 basic_block header;
6905 /* Search the nodes of the CFG in DFS order that we can find
6906 outer loops first. */
6909 /* Look for all the possible latch blocks for this header. */
6911 {
6914 /* Look for back edges where a predecessor is dominated
6915 by this block. A natural loop has a single entry
6916 node (header) that dominates all the nodes in the
6917 loop. It also has single back edge to the header
6918 from a latch node. Note that multiple natural loops
6919 may share the same header. */
6922 {
6930 /* Keep track of blocks that are loop headers so
6931 that we can tell which loops should be merged. */
6936 /* Find nodes contained within the loop. */
6938 loop->num_nodes
6941 /* Find edges which exit the loop. Note that a node
6942 may have several exit edges. */
6943 loop->num_exits
6946 /* Look to see if the loop has a pre-header node. */
6947 loop->pre_header
6950 num_loops++;
6951 }
6952 }
6953 }
6955 /* Natural loops with shared headers may either be disjoint or
6956 nested. Disjoint loops with shared headers cannot be inner
6957 loops and should be merged. For now just mark loops that share
6958 headers. */
6964 }
6968 /* Save CFG derived information to avoid recomputing it. */
6972 /* Build the loop hierarchy tree. */
6975 /* Assign the loop nesting depth and enclosed loop level for each
6976 loop. */
6980 }
6983 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
6984 int
6987 edge e;
6988 {
6993 }