| blob | 9ed2b35646a8eca4633a2c961c6761122328c072 |
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_crosses 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. */
182 {
183 {
195 },
196 {
208 }
209 };
211 /* Nonzero if the second flow pass has completed. */
214 /* Maximum register number used in this function, plus one. */
218 /* Indexed by n, giving various register information */
220 varray_type reg_n_info;
222 /* Size of the reg_n_info table. */
226 /* Element N is the next insn that uses (hard or pseudo) register number N
227 within the current basic block; or zero, if there is no such insn.
228 This is valid only during the final backward scan in propagate_block. */
232 /* Size of a regset for the current function,
233 in (1) bytes and (2) elements. */
238 /* Regset of regs live when calls to `setjmp'-like functions happen. */
239 /* ??? Does this exist only for the setjmp-clobbered warning message? */
241 regset regs_live_at_setjmp;
243 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
244 that have to go in the same hard reg.
245 The first two regs in the list are a pair, and the next two
246 are another pair, etc. */
247 rtx regs_may_share;
249 /* Depth within loops of basic block being scanned for lifetime analysis,
250 plus one. This is the weight attached to references to registers. */
254 /* During propagate_block, this is non-zero if the value of CC0 is live. */
258 /* During propagate_block, this contains a list of all the MEMs we are
259 tracking for dead store elimination. */
263 /* Set of registers that may be eliminable. These are handled specially
264 in updating regs_ever_live. */
268 /* The basic block structure for every insn, indexed by uid. */
270 varray_type basic_block_for_insn;
272 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
273 /* ??? Should probably be using LABEL_NUSES instead. It would take a
274 bit of surgery to be able to use or co-opt the routines in jump. */
278 /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
280 #define INSN_VOLATILE(INSN) bitmap_bit_p (uid_volatile, INSN_UID (INSN))
281 #define SET_INSN_VOLATILE(INSN) bitmap_set_bit (uid_volatile, INSN_UID (INSN))
284 /* Forward declarations */
310 basic_block));
312 basic_block));
338 #ifdef AUTO_INC_DEC
342 #endif
362 /* This function is always defined so it can be called from the
363 debugger, and it is declared extern so we don't get warnings about
364 it being unused. */
367 \f
368 /* Find basic blocks of the current function.
369 F is the first insn of the function and NREGS the number of register
370 numbers in use. */
372 void
374 rtx f;
378 {
381 /* Flush out existing data. */
383 {
388 /* Clear bb->aux on all extant basic blocks. We'll use this as a
389 tag for reuse during create_basic_block, just in case some pass
390 copies around basic block notes improperly. */
395 }
399 /* Size the basic block table. The actual structures will be allocated
400 by find_basic_blocks_1, since we want to keep the structure pointers
401 stable across calls to find_basic_blocks. */
402 /* ??? This whole issue would be much simpler if we called find_basic_blocks
403 exactly once, and thereafter we don't have a single long chain of
404 instructions at all until close to the end of compilation when we
405 actually lay them out. */
411 /* Record the block to which an insn belongs. */
412 /* ??? This should be done another way, by which (perhaps) a label is
413 tagged directly with the basic block that it starts. It is used for
414 more than that currently, but IMO that is the only valid use. */
417 #ifdef AUTO_INC_DEC
418 /* Leave space for insns life_analysis makes in some cases for auto-inc.
419 These cases are rare, so we don't need too much space. */
421 #endif
425 /* Discover the edges of our cfg. */
430 /* Delete unreachable blocks, then merge blocks when possible. */
433 {
438 }
440 /* Mark critical edges. */
444 /* Discover the loop depth at the start of each basic block to aid
445 register allocation. */
448 /* Kill the data we won't maintain. */
451 #ifdef ENABLE_CHECKING
453 #endif
454 }
456 /* Count the basic blocks of the function. */
458 static int
460 rtx f;
461 {
471 {
479 {
480 count++;
482 /* If the previous insn was a call that did not create an
483 abnormal edge, we want to add a nop so that the CALL_INSN
484 itself is not at basic_block_end. This allows us to
485 easily distinguish between normal calls and those which
486 create abnormal edges in the flow graph. */
489 {
492 }
493 }
495 /* Record whether this call created an edge. */
497 {
503 /* If there is a specified EH region, we have an edge. */
506 else
507 {
508 /* If there is a nonlocal goto label and the specified
509 region number isn't -1, we have an edge. (0 means
510 no throw, but might have a nonlocal goto). */
513 }
514 }
525 }
527 /* The rest of the compiler works a bit smoother when we don't have to
528 check for the edge case of do-nothing functions with no basic blocks. */
530 {
533 }
536 }
538 /* Find all basic blocks of the function whose first insn is F.
540 Collect and return a list of labels whose addresses are taken. This
541 will be used in make_edges for use with computed gotos. */
543 static rtx
545 rtx f;
546 {
556 /* We process the instructions in a slightly different way than we did
557 previously. This is so that we see a NOTE_BASIC_BLOCK after we have
558 closed out the previous block, so that it gets attached at the proper
559 place. Since this form should be equivalent to the previous,
560 count_basic_blocks continues to use the old form as a check. */
563 {
569 {
570 /* Record whether this call created an edge. */
575 /* If there is an EH region, we have an edge. */
578 else
579 {
580 /* If there is a nonlocal goto label and the specified
581 region number isn't -1, we have an edge. (0 means
582 no throw, but might have a nonlocal goto). */
585 }
586 }
589 {
591 {
594 /* Keep a LIFO list of the currently active exception notes. */
598 {
602 }
604 /* Look for basic block notes with which to keep the
605 basic_block_info pointers stable. Unthread the note now;
606 we'll put it back at the right place in create_basic_block.
607 Or not at all if we've already found a note in this block. */
609 {
613 }
616 }
619 /* A basic block starts at a label. If we've closed one off due
620 to a barrier or some such, no need to do it again. */
622 {
623 /* While we now have edge lists with which other portions of
624 the compiler might determine a call ending a basic block
625 does not imply an abnormal edge, it will be a bit before
626 everything can be updated. So continue to emit a noop at
627 the end of such a block. */
629 {
632 }
636 }
641 /* A basic block ends at a jump. */
644 else
645 {
646 /* ??? Make a special check for table jumps. The way this
647 happens is truly and amazingly gross. We are about to
648 create a basic block that contains just a code label and
649 an addr*vec jump insn. Worse, an addr_diff_vec creates
650 its own natural loop.
652 Prevent this bit of brain damage, pasting things together
653 correctly in make_edges.
655 The correct solution involves emitting the table directly
656 on the tablejump instruction as a note, or JUMP_LABEL. */
660 {
662 n_basic_blocks--;
664 }
665 }
670 /* A basic block ends at a barrier. It may be that an unconditional
671 jump already closed the basic block -- no need to do it again. */
675 /* While we now have edge lists with which other portions of the
676 compiler might determine a call ending a basic block does not
677 imply an abnormal edge, it will be a bit before everything can
678 be updated. So continue to emit a noop at the end of such a
679 block. */
681 {
684 }
688 /* A basic block ends at a call that can either throw or
689 do a non-local goto. */
691 {
692 new_bb_inclusive:
697 new_bb_exclusive:
702 }
703 /* FALLTHRU */
707 {
711 }
713 }
716 {
717 rtx note;
719 /* Make a list of all labels referred to other than by jumps
720 (which just don't have the REG_LABEL notes).
722 Make a special exception for labels followed by an ADDR*VEC,
723 as this would be a part of the tablejump setup code.
725 Make a special exception for the eh_return_stub_label, which
726 we know isn't part of any otherwise visible control flow. */
730 {
734 ;
739 ;
740 else
741 label_value_list
743 }
744 }
745 }
754 }
756 /* Create a new basic block consisting of the instructions between
757 HEAD and END inclusive. Reuses the note and basic block struct
758 in BB_NOTE, if any. */
760 static void
764 {
765 basic_block bb;
771 {
772 /* If we found an existing note, thread it back onto the chain. */
776 else
777 {
780 }
781 }
782 else
783 {
784 /* Otherwise we must create a note and a basic block structure.
785 Since we allow basic block structs in rtl, give the struct
786 the same lifetime by allocating it off the function obstack
787 rather than using malloc. */
794 else
795 {
798 }
800 }
802 /* Always include the bb note in the block. */
811 /* Tag the block so that we know it has been used when considering
812 other basic block notes. */
814 }
815 \f
816 /* Records the basic block struct in BB_FOR_INSN, for every instruction
817 indexed by INSN_UID. MAX is the size of the array. */
819 void
822 {
830 {
837 {
844 }
845 }
846 }
848 /* Free the memory associated with the edge structures. */
850 static void
852 {
857 {
861 {
864 }
868 }
871 {
874 }
880 }
882 /* Identify the edges between basic blocks.
884 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks
885 that are otherwise unreachable may be reachable with a non-local goto.
887 BB_EH_END is an array indexed by basic block number in which we record
888 the list of exception regions active at the end of the basic block. */
890 static void
892 rtx label_value_list;
893 {
898 /* Assume no computed jump; revise as we create edges. */
901 /* Heavy use of computed goto in machine-generated code can lead to
902 nearly fully-connected CFGs. In that case we spend a significant
903 amount of time searching the edge lists for duplicates. */
905 {
908 }
910 /* By nature of the way these get numbered, block 0 is always the entry. */
914 {
920 /* Examine the last instruction of the block, and discover the
921 ways we can leave the block. */
926 /* A branch. */
928 {
929 rtx tmp;
931 /* ??? Recognize a tablejump and do the right thing. */
937 {
938 rtvec vec;
943 else
950 /* Some targets (eg, ARM) emit a conditional jump that also
951 contains the out-of-range target. Scan for these and
952 add an edge if necessary. */
960 #ifdef CASE_DROPS_THROUGH
961 /* Silly VAXen. The ADDR_VEC is going to be in the way of
962 us naturally detecting fallthru into the next block. */
964 #endif
965 }
967 /* If this is a computed jump, then mark it as reaching
968 everything on the label_value_list and forced_labels list. */
970 {
978 }
980 /* Returns create an exit out. */
984 /* Otherwise, we have a plain conditional or unconditional jump. */
985 else
986 {
990 }
991 }
993 /* If this is a CALL_INSN, then mark it as reaching the active EH
994 handler for this CALL_INSN. If we're handling asynchronous
995 exceptions then any insn can reach any of the active handlers.
997 Also mark the CALL_INSN as reaching any nonlocal goto handler. */
1000 {
1001 /* If there's an EH region active at the end of a block,
1002 add the appropriate edges. */
1006 /* If we have asynchronous exceptions, do the same for *all*
1007 exception regions active in the block. */
1010 {
1019 {
1023 }
1024 }
1027 {
1028 /* ??? This could be made smarter: in some cases it's possible
1029 to tell that certain calls will not do a nonlocal goto.
1031 For example, if the nested functions that do the nonlocal
1032 gotos do not have their addresses taken, then only calls to
1033 those functions or to other nested functions that use them
1034 could possibly do nonlocal gotos. */
1035 /* We do know that a REG_EH_REGION note with a value less
1036 than 0 is guaranteed not to perform a non-local goto. */
1042 }
1043 }
1045 /* We know something about the structure of the function __throw in
1046 libgcc2.c. It is the only function that ever contains eh_stub
1047 labels. It modifies its return address so that the last block
1048 returns to one of the eh_stub labels within it. So we have to
1049 make additional edges in the flow graph. */
1053 /* Find out if we can drop through to the next block. */
1058 {
1064 }
1065 }
1070 }
1072 /* Create an edge between two basic blocks. FLAGS are auxiliary information
1073 about the edge that is accumulated between calls. */
1075 static void
1080 {
1082 edge e;
1084 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1085 many edges to them, and we didn't allocate memory for it. */
1086 use_edge_cache = (edge_cache
1090 /* Make sure we don't add duplicate edges. */
1094 {
1097 }
1100 n_edges++;
1113 }
1115 /* Create an edge from a basic block to a label. */
1117 static void
1120 basic_block src;
1121 rtx label;
1123 {
1127 /* If the label was never emitted, this insn is junk, but avoid a
1128 crash trying to refer to BLOCK_FOR_INSN (label). This can happen
1129 as a result of a syntax error and a diagnostic has already been
1130 printed. */
1136 }
1138 /* Create the edges generated by INSN in REGION. */
1140 static void
1144 basic_block src;
1145 rtx insn;
1147 {
1154 {
1157 }
1158 }
1160 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1161 dangerous if we intend to move basic blocks around. Move such notes
1162 into the following block. */
1164 static void
1166 {
1175 {
1180 {
1185 {
1186 /* Unlink from the insn chain. */
1190 /* Queue it. */
1193 }
1194 }
1199 /* Find where to insert these things. */
1205 {
1209 }
1210 }
1211 }
1213 /* Recompute eh_beg/eh_end for each basic block. */
1215 static void
1217 rtx f;
1218 {
1224 {
1229 {
1234 {
1238 }
1239 }
1242 {
1248 }
1249 }
1250 }
1252 /* Identify critical edges and set the bits appropriately. */
1254 static void
1256 {
1258 basic_block bb;
1260 /* We begin with the entry block. This is not terribly important now,
1261 but could be if a front end (Fortran) implemented alternate entry
1262 points. */
1267 {
1268 edge e;
1270 /* (1) Critical edges must have a source with multiple successors. */
1272 {
1274 {
1275 /* (2) Critical edges must have a destination with multiple
1276 predecessors. Note that we know there is at least one
1277 predecessor -- the edge we followed to get here. */
1280 else
1282 }
1283 }
1284 else
1285 {
1288 }
1293 }
1294 }
1295 \f
1296 /* Split a (typically critical) edge. Return the new block.
1297 Abort on abnormal edges.
1299 ??? The code generally expects to be called on critical edges.
1300 The case of a block ending in an unconditional jump to a
1301 block with multiple predecessors is not handled optimally. */
1303 basic_block
1305 edge edge_in;
1306 {
1308 edge edge_out;
1309 rtx bb_note;
1312 /* Abnormal edges cannot be split. */
1319 /* Remove the existing edge from the destination's pred list. */
1320 {
1326 }
1328 /* Create the new structures. */
1331 n_edges++;
1337 /* ??? This info is likely going to be out of date very soon. */
1339 {
1342 }
1343 else
1344 {
1347 }
1349 /* Wire them up. */
1365 /* Tricky case -- if there existed a fallthru into the successor
1366 (and we're not it) we must add a new unconditional jump around
1367 the new block we're actually interested in.
1369 Further, if that edge is critical, this means a second new basic
1370 block must be created to hold it. In order to simplify correct
1371 insn placement, do this before we touch the existing basic block
1372 ordering for the block we were really wanting. */
1374 {
1375 edge e;
1381 {
1382 basic_block jump_block;
1383 rtx pos;
1386 {
1387 /* Non critical -- we can simply add a jump to the end
1388 of the existing predecessor. */
1390 }
1391 else
1392 {
1393 /* We need a new block to hold the jump. The simplest
1394 way to do the bulk of the work here is to recursively
1395 call ourselves. */
1398 }
1400 /* Now add the jump insn ... */
1406 /* ... let jump know that label is in use, ... */
1410 /* ... and clear fallthru on the outgoing edge. */
1413 /* Continue splitting the interesting edge. */
1414 }
1415 }
1417 /* Place the new block just in front of the successor. */
1421 else
1424 {
1428 }
1432 /* Create the basic block note. */
1435 else
1440 /* Not quite simple -- for non-fallthru edges, we must adjust the
1441 predecessor's jump instruction to target our new block. */
1443 {
1451 /* ??? Recognize a tablejump and adjust all matching cases. */
1457 {
1458 rtvec vec;
1463 else
1468 {
1472 }
1474 /* Handle casesi dispatch insns */
1480 {
1482 new_label);
1485 }
1486 }
1487 else
1488 {
1489 /* This would have indicated an abnormal edge. */
1493 /* A return instruction can't be redirected. */
1497 /* If the insn doesn't go where we think, we're confused. */
1502 }
1506 }
1509 }
1511 /* Queue instructions for insertion on an edge between two basic blocks.
1512 The new instructions and basic blocks (if any) will not appear in the
1513 CFG until commit_edge_insertions is called. */
1515 void
1517 rtx pattern;
1518 edge e;
1519 {
1520 /* We cannot insert instructions on an abnormal critical edge.
1521 It will be easier to find the culprit if we die now. */
1528 else
1535 }
1537 /* Update the CFG for the instructions queued on edge E. */
1539 static void
1541 edge e;
1542 {
1544 basic_block bb;
1546 /* Figure out where to put these things. If the destination has
1547 one predecessor, insert there. Except for the exit block. */
1550 {
1553 /* Get the location correct wrt a code label, and "nice" wrt
1554 a basic block note, and before everything else. */
1563 else
1565 }
1567 /* If the source has one successor and the edge is not abnormal,
1568 insert there. Except for the entry block. */
1572 {
1575 {
1576 /* ??? Is it possible to wind up with non-simple jumps? Perhaps
1577 a jump with delay slots already filled? */
1582 }
1583 else
1584 {
1585 /* We'd better be fallthru, or we've lost track of what's what. */
1590 }
1591 }
1593 /* Otherwise we must split the edge. */
1594 else
1595 {
1598 }
1600 /* Now that we've found the spot, do the insertion. */
1604 /* Set the new block number for these insns, if structure is allocated. */
1606 {
1607 rtx i;
1610 }
1613 {
1617 }
1618 else
1619 {
1623 }
1624 }
1626 /* Update the CFG for all queued instructions. */
1628 void
1630 {
1632 basic_block bb;
1637 {
1641 {
1645 }
1650 }
1651 }
1652 \f
1653 /* Delete all unreachable basic blocks. */
1655 static void
1657 {
1660 edge e;
1666 /* Use basic_block->aux as a marker. Clear them all. */
1671 /* Add our starting points to the worklist. Almost always there will
1672 be only one. It isn't inconcievable that we might one day directly
1673 support Fortran alternate entry points. */
1676 {
1679 /* Mark the block with a handy non-null value. */
1681 }
1683 /* Iterate: find everything reachable from what we've already seen. */
1686 {
1691 {
1694 }
1695 }
1697 /* Delete all unreachable basic blocks. Count down so that we don't
1698 interfere with the block renumbering that happens in delete_block. */
1703 {
1707 /* This block was found. Tidy up the mark. */
1709 else
1711 }
1713 /* Fix up edges that now fall through, or rather should now fall through
1714 but previously required a jump around now deleted blocks. Simplify
1715 the search by only examining blocks numerically adjacent, since this
1716 is how find_basic_blocks created them. */
1719 {
1722 edge s;
1724 /* We care about simple conditional or unconditional jumps with
1725 a single successor.
1727 If we had a conditional branch to the next instruction when
1728 find_basic_blocks was called, then there will only be one
1729 out edge for the block which ended with the conditional
1730 branch (since we do not create duplicate edges).
1732 Furthermore, the edge will be marked as a fallthru because we
1733 merge the flags for the duplicate edges. So we do not want to
1734 check that the edge is not a FALLTHRU edge. */
1738 /* If the jump insn has side effects, we can't tidy the edge. */
1742 }
1744 /* If we deleted an exception handler, we may have EH region begin/end
1745 blocks to remove as well. */
1750 }
1752 /* Find EH regions for which there is no longer a handler, and delete them. */
1754 static void
1756 {
1757 rtx insn;
1763 {
1766 {
1768 /* A NULL handler indicates a region is no longer needed,
1769 as long as it isn't the target of a rethrow. */
1771 {
1774 }
1775 }
1776 }
1777 }
1779 /* Return true if NOTE is not one of the ones that must be kept paired,
1780 so that we may simply delete them. */
1782 static int
1784 rtx note;
1785 {
1788 }
1790 /* Unlink a chain of insns between START and FINISH, leaving notes
1791 that must be paired. */
1793 void
1796 {
1797 /* Unchain the insns one by one. It would be quicker to delete all
1798 of these with a single unchaining, rather than one at a time, but
1799 we need to keep the NOTE's. */
1801 rtx next;
1804 {
1807 ;
1809 ;
1810 else
1816 }
1817 }
1819 /* Delete the insns in a (non-live) block. We physically delete every
1820 non-deleted-note insn, and update the flow graph appropriately.
1822 Return nonzero if we deleted an exception handler. */
1824 /* ??? Preserving all such notes strikes me as wrong. It would be nice
1825 to post-process the stream to remove empty blocks, loops, ranges, etc. */
1827 static int
1829 basic_block b;
1830 {
1834 /* If the head of this block is a CODE_LABEL, then it might be the
1835 label for an exception handler which can't be reached.
1837 We need to remove the label from the exception_handler_label list
1838 and remove the associated NOTE_INSN_EH_REGION_BEG and
1839 NOTE_INSN_EH_REGION_END notes. */
1846 {
1850 {
1852 {
1853 /* Found a match, splice this label out of the EH label list. */
1858 /* Remove the handler from all regions */
1862 }
1864 }
1866 /* This label may be referenced by code solely for its value, or
1867 referenced by static data, or something. We have determined
1868 that it is not reachable, but cannot delete the label itself.
1869 Save code space and continue to delete the balance of the block,
1870 along with properly updating the cfg. */
1872 {
1873 /* If we've only got one of these, skip the whole deleting
1874 insns thing. */
1878 }
1879 }
1881 /* Selectively unlink the insn chain. Include any BARRIER that may
1882 follow the basic block. */
1888 no_delete_insns:
1890 /* Remove the edges into and out of this block. Note that there may
1891 indeed be edges in, if we are removing an unreachable loop. */
1892 {
1896 {
1901 n_edges--;
1903 }
1905 {
1910 n_edges--;
1912 }
1916 }
1918 /* Remove the basic block from the array, and compact behind it. */
1922 }
1924 /* Remove block B from the basic block array and compact behind it. */
1926 static void
1928 basic_block b;
1929 {
1933 {
1937 }
1940 n_basic_blocks--;
1941 }
1943 /* Delete INSN by patching it out. Return the next insn. */
1945 static rtx
1947 rtx insn;
1948 {
1959 else
1965 /* If deleting a jump, decrement the use count of the label. Deleting
1966 the label itself should happen in the normal course of block merging. */
1971 }
1973 /* True if a given label can be deleted. */
1975 static int
1977 rtx label;
1978 {
1979 rtx x;
1994 /* User declared labels must be preserved. */
1999 }
2001 /* Blocks A and B are to be merged into a single block. A has no incoming
2002 fallthru edge, so it can be moved before B without adding or modifying
2003 any jumps (aside from the jump from A to B). */
2005 static int
2008 {
2015 /* We want to delete the BARRIER after the end of the insns we are
2016 going to move. If we don't find a BARRIER, then do nothing. This
2017 can happen in some cases if we have labels we can not delete.
2019 Similarly, do nothing if we can not delete the label at the start
2020 of the target block. */
2026 else
2029 /* Move block and loop notes out of the chain so that we do not
2030 disturb their order.
2032 ??? A better solution would be to squeeze out all the non-nested notes
2033 and adjust the block trees appropriately. Even better would be to have
2034 a tighter connection between block trees and rtl so that this is not
2035 necessary. */
2038 /* Scramble the insn chain. */
2043 {
2046 }
2048 /* Swap the records for the two blocks around. Although we are deleting B,
2049 A is now where B was and we want to compact the BB array from where
2050 A used to be. */
2057 /* Now blocks A and B are contiguous. Merge them. */
2061 }
2063 /* Blocks A and B are to be merged into a single block. B has no outgoing
2064 fallthru edge, so it can be moved after A without adding or modifying
2065 any jumps (aside from the jump from A to B). */
2067 static int
2070 {
2076 /* We want to delete the BARRIER after the end of the insns we are
2077 going to move. If we don't find a BARRIER, then do nothing. This
2078 can happen in some cases if we have labels we can not delete.
2080 Similarly, do nothing if we can not delete the label at the start
2081 of the target block. */
2087 else
2090 /* Move block and loop notes out of the chain so that we do not
2091 disturb their order.
2093 ??? A better solution would be to squeeze out all the non-nested notes
2094 and adjust the block trees appropriately. Even better would be to have
2095 a tighter connection between block trees and rtl so that this is not
2096 necessary. */
2099 /* Scramble the insn chain. */
2102 /* Now blocks A and B are contiguous. Merge them. */
2106 {
2109 }
2112 }
2114 /* Blocks A and B are to be merged into a single block. The insns
2115 are already contiguous, hence `nomove'. */
2117 static void
2120 {
2121 edge e;
2125 /* If there was a CODE_LABEL beginning B, delete it. */
2129 {
2130 /* Detect basic blocks with nothing but a label. This can happen
2131 in particular at the end of a function. */
2135 }
2137 /* Delete the basic block note. */
2140 {
2144 }
2146 /* If there was a jump out of A, delete it. */
2149 {
2150 rtx prev;
2156 #ifdef HAVE_cc0
2157 /* If this was a conditional jump, we need to also delete
2158 the insn that set cc0. */
2161 {
2167 }
2168 #endif
2170 /* Note that a->head != a->end, since we should have at least a
2171 bb note plus the jump, so prev != insn. */
2174 }
2176 /* By definition, there should only be one successor of A, and that is
2177 B. Free that edge struct. */
2178 n_edges--;
2181 /* Adjust the edges out of B for the new owner. */
2186 /* Reassociate the insns of B with A. */
2188 {
2191 {
2194 }
2196 }
2199 /* Compact the basic block array. */
2201 }
2203 /* Attempt to merge basic blocks that are potentially non-adjacent.
2204 Return true iff the attempt succeeded. */
2206 static int
2208 edge e;
2210 {
2211 /* If B has a fallthru edge to C, no need to move anything. */
2213 {
2214 /* If a label still appears somewhere and we cannot delete the label,
2215 then we cannot merge the blocks. The edge was tidied already. */
2225 {
2228 }
2231 }
2232 else
2233 {
2234 edge tmp_edge;
2235 basic_block d;
2239 /* We must make sure to not munge nesting of exception regions,
2240 lexical blocks, and loop notes.
2242 The first is taken care of by requiring that the active eh
2243 region at the end of one block always matches the active eh
2244 region at the beginning of the next block.
2246 The later two are taken care of by squeezing out all the notes. */
2248 /* ??? A throw/catch edge (or any abnormal edge) should be rarely
2249 executed and we may want to treat blocks which have two out
2250 edges, one normal, one abnormal as only having one edge for
2251 block merging purposes. */
2263 /* If B does not have an incoming fallthru, and the exception regions
2264 match, then it can be moved immediately before C without introducing
2265 or modifying jumps.
2267 C can not be the first block, so we do not have to worry about
2268 accessing a non-existent block. */
2275 /* Otherwise, we're going to try to move C after B. Make sure the
2276 exception regions match.
2278 If B is the last basic block, then we must not try to access the
2279 block structure for block B + 1. Luckily in that case we do not
2280 need to worry about matching exception regions. */
2284 {
2285 /* If C does not have an outgoing fallthru, then it can be moved
2286 immediately after B without introducing or modifying jumps. */
2290 /* Otherwise, we'll need to insert an extra jump, and possibly
2291 a new block to contain it. */
2292 /* ??? Not implemented yet. */
2293 }
2296 }
2297 }
2299 /* Top level driver for merge_blocks. */
2301 static void
2303 {
2306 /* Attempt to merge blocks as made possible by edge removal. If a block
2307 has only one successor, and the successor has only one predecessor,
2308 they may be combined. */
2311 {
2313 edge s;
2315 /* A loop because chains of blocks might be combineable. */
2321 /* If the jump insn has side effects, we can't kill the edge. */
2327 /* Don't get confused by the index shift caused by deleting blocks. */
2329 }
2330 }
2332 /* The given edge should potentially a fallthru edge. If that is in
2333 fact true, delete the unconditional jump and barriers that are in
2334 the way. */
2336 static void
2338 edge e;
2340 {
2341 rtx q;
2343 /* ??? In a late-running flow pass, other folks may have deleted basic
2344 blocks by nopping out blocks, leaving multiple BARRIERs between here
2345 and the target label. They ought to be chastized and fixed.
2347 We can also wind up with a sequence of undeletable labels between
2348 one block and the next.
2350 So search through a sequence of barriers, labels, and notes for
2351 the head of block C and assert that we really do fall through. */
2356 /* Remove what will soon cease being the jump insn from the source block.
2357 If block B consisted only of this single jump, turn it into a deleted
2358 note. */
2361 {
2362 #ifdef HAVE_cc0
2363 /* If this was a conditional jump, we need to also delete
2364 the insn that set cc0. */
2367 #endif
2370 {
2374 }
2375 else
2377 }
2379 /* Selectively unlink the sequence. */
2384 }
2386 /* Discover and record the loop depth at the head of each basic block. */
2388 static void
2390 rtx insns;
2391 {
2392 basic_block bb;
2393 rtx insn;
2398 {
2400 {
2405 }
2408 {
2410 depth++;
2412 depth--;
2414 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error. */
2417 }
2418 }
2419 }
2420 \f
2421 /* Perform data flow analysis.
2422 F is the first insn of the function and NREGS the number of register numbers
2423 in use. */
2425 void
2427 rtx f;
2431 {
2432 #ifdef ELIMINABLE_REGS
2435 #endif
2438 /* Record which registers will be eliminated. We use this in
2439 mark_used_regs. */
2443 #ifdef ELIMINABLE_REGS
2446 #else
2448 #endif
2450 /* Allocate a bitmap to be filled in by record_volatile_insns. */
2453 /* We want alias analysis information for local dead store elimination. */
2471 }
2473 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2474 Search for REGNO. If found, abort if it is not wider than word_mode. */
2476 static int
2480 {
2485 {
2489 }
2491 }
2493 /* A subroutine of verify_local_live_at_start. Search through insns
2494 between HEAD and END looking for register REGNO. */
2496 static void
2500 {
2502 {
2509 }
2511 /* We didn't find the register at all. Something's way screwy. */
2513 }
2515 /* A subroutine of update_life_info. Verify that there are no untoward
2516 changes in live_at_start during a local update. */
2518 static void
2520 regset new_live_at_start;
2521 basic_block bb;
2522 {
2524 {
2525 /* After reload, there are no pseudos, nor subregs of multi-word
2526 registers. The regsets should exactly match. */
2529 }
2530 else
2531 {
2534 /* Find the set of changed registers. */
2538 {
2539 /* No registers should die. */
2542 /* Verify that the now-live register is wider than word_mode. */
2544 });
2545 }
2546 }
2548 /* Updates death notes starting with the basic blocks set in BLOCKS.
2550 If LOCAL_ONLY, such as after splitting or peepholeing, we are only
2551 expecting local modifications to basic blocks. If we find extra
2552 registers live at the beginning of a block, then we either killed
2553 useful data, or we have a broken split that wants data not provided.
2554 If we find registers removed from live_at_start, that means we have
2555 a broken peephole that is killing a register it shouldn't.
2557 ??? This is not true in one situation -- when a pre-reload splitter
2558 generates subregs of a multi-word pseudo, current life analysis will
2559 lose the kill. So we _can_ have a pseudo go live. How irritating.
2561 BLOCK_FOR_INSN is assumed to be correct.
2563 ??? PROP_FLAGS should not contain PROP_LOG_LINKS. Need to set up
2564 reg_next_use for that. Including PROP_REG_INFO does not refresh
2565 regs_ever_live unless the caller resets it to zero. */
2567 void
2569 sbitmap blocks;
2572 {
2573 regset tmp;
2578 /* For a global update, we go through the relaxation process again. */
2580 {
2584 /* If asked, remove notes from the blocks we'll update. */
2587 }
2590 {
2595 prop_flags);
2599 });
2602 }
2604 /* Free the variables allocated by find_basic_blocks.
2606 KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed. */
2608 void
2611 {
2613 {
2616 }
2619 {
2628 }
2629 }
2631 /* Return nonzero if the destination of SET equals the source. */
2632 static int
2634 rtx set;
2635 {
2650 }
2652 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2653 value to itself. */
2654 static int
2656 rtx insn;
2657 {
2660 /* Insns carrying these notes are useful later on. */
2668 {
2670 /* If nothing but SETs of registers to themselves,
2671 this insn can also be deleted. */
2673 {
2682 }
2685 }
2687 }
2689 static void
2691 rtx x;
2692 rtx pat ATTRIBUTE_UNUSED;
2694 {
2696 /* The stack pointer is only modified indirectly as the result
2697 of a push until later in flow. See the comments in rtl.texi
2698 regarding Embedded Side-Effects on Addresses. */
2706 }
2708 /* Record which insns refer to any volatile memory
2709 or for any reason can't be deleted just because they are dead stores.
2710 Also, delete any insns that copy a register to itself.
2711 And see if the stack pointer is modified. */
2712 static void
2714 rtx f;
2715 {
2716 rtx insn;
2718 {
2723 {
2728 /* A SET that makes space on the stack cannot be dead.
2729 (Such SETs occur only for allocating variable-size data,
2730 so they will always have a PLUS or MINUS according to the
2731 direction of stack growth.)
2732 Even if this function never uses this stack pointer value,
2733 signal handlers do! */
2736 #ifdef STACK_GROWS_DOWNWARD
2738 #else
2740 #endif
2744 /* Delete (in effect) any obvious no-op moves. */
2746 {
2750 }
2751 }
2753 /* Check if insn modifies the stack pointer. */
2757 notice_stack_pointer_modification,
2758 NULL);
2759 }
2760 }
2762 /* Mark a register in SET. Hard registers in large modes get all
2763 of their component registers set as well. */
2764 static void
2766 regset set;
2767 rtx reg;
2768 {
2773 {
2777 }
2778 }
2780 /* Mark those regs which are needed at the end of the function as live
2781 at the end of the last basic block. */
2782 static void
2784 regset set;
2785 {
2786 tree type;
2789 /* If exiting needs the right stack value, consider the stack pointer
2790 live at the end of the function. */
2792 || ! EXIT_IGNORE_STACK
2793 || (! FRAME_POINTER_REQUIRED
2794 && ! current_function_calls_alloca
2797 {
2799 }
2801 /* Mark the frame pointer if needed at the end of the function. If
2802 we end up eliminating it, it will be removed from the live list
2803 of each basic block by reload. */
2806 {
2808 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2809 /* If they are different, also mark the hard frame pointer as live */
2811 #endif
2812 }
2814 #ifdef PIC_OFFSET_TABLE_REGNUM
2815 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
2816 /* Many architectures have a GP register even without flag_pic.
2817 Assume the pic register is not in use, or will be handled by
2818 other means, if it is not fixed. */
2821 #endif
2822 #endif
2824 /* Mark all global registers, and all registers used by the epilogue
2825 as being live at the end of the function since they may be
2826 referenced by our caller. */
2829 #ifdef EPILOGUE_USES
2831 #endif
2832 )
2835 /* Mark all call-saved registers that we actaully used. */
2837 {
2841 }
2843 /* Mark function return value. */
2844 /* ??? Only do this after reload. Consider a non-void function that
2845 omits a return statement. Across that edge we'll have the return
2846 register live, and no set for it. Thus the return register will
2847 be live back through the CFG to the entry, and thus we die. A
2848 possible solution is to emit a clobber at exits without returns. */
2853 {
2854 rtx outgoing;
2860 #ifdef FUNCTION_OUTGOING_VALUE
2862 #else
2864 #endif
2869 {
2872 /* Check for a NULL entry, used to indicate that the parameter
2873 goes on the stack and in registers. */
2877 {
2881 }
2882 }
2883 else
2885 }
2886 }
2888 /* Determine which registers are live at the start of each
2889 basic block of the function whose first insn is F.
2890 NREGS is the number of registers used in F.
2891 We allocate the vector basic_block_live_at_start
2892 and the regsets that it points to, and fill them with the data.
2893 regset_size and regset_bytes are also set here. */
2895 static void
2897 rtx f;
2900 {
2906 /* Allocate and zero out many data structures
2907 that will record the data from lifetime analysis. */
2914 /* Assume that the stack pointer is unchanging if alloca hasn't been used.
2915 This will be cleared by record_volatile_insns if it encounters an insn
2916 which modifies the stack pointer. */
2920 /* Find the set of registers live on function exit. Do this before
2921 zeroing regs_ever_live, as we use that data post-reload. */
2924 /* The post-reload life analysis have (on a global basis) the same
2925 registers live as was computed by reload itself. elimination
2926 Otherwise offsets and such may be incorrect.
2928 Reload will make some registers as live even though they do not
2929 appear in the rtl. */
2934 /* Compute register life at block boundaries. It'd be nice to
2935 begin with just the exit and noreturn blocks, but that set
2936 is not immediately handy. */
2937 {
2938 sbitmap blocks;
2943 }
2945 /* The only pseudos that are live at the beginning of the function are
2946 those that were not set anywhere in the function. local-alloc doesn't
2947 know how to handle these correctly, so mark them as not local to any
2948 one basic block. */
2954 /* Now the life information is accurate. Make one more pass over each
2955 basic block to delete dead stores, create autoincrement addressing
2956 and record how many times each register is used, is set, or dies. */
2957 {
2958 regset tmp;
2962 {
2967 }
2970 }
2972 /* We have a problem with any pseudoreg that lives across the setjmp.
2973 ANSI says that if a user variable does not change in value between
2974 the setjmp and the longjmp, then the longjmp preserves it. This
2975 includes longjmp from a place where the pseudo appears dead.
2976 (In principle, the value still exists if it is in scope.)
2977 If the pseudo goes in a hard reg, some other value may occupy
2978 that hard reg where this pseudo is dead, thus clobbering the pseudo.
2979 Conclusion: such a pseudo must not go in a hard reg. */
2982 {
2984 {
2987 }
2988 });
2990 /* Restore regs_ever_live that was provided by reload. */
2994 /* Clean up. */
2997 }
2999 /* Propagate global life info around the graph of basic blocks. Begin
3000 considering blocks with their corresponding bit set in BLOCKS_IN.
3001 BLOCKS_OUT is set for every block that was changed. */
3003 static void
3007 {
3015 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
3016 because the `head == tail' style test for an empty queue doesn't
3017 work with a full queue. */
3022 /* Queue the blocks set in the initial mask. Do this in reverse block
3023 number order so that we are more likely for the first round to do
3024 useful work. We use AUX non-null to flag that the block is queued. */
3026 {
3030 });
3035 {
3037 basic_block bb;
3038 edge e;
3045 /* Begin by propogating live_at_start from the successor blocks. */
3048 {
3051 }
3054 {
3057 }
3059 /* On our first pass through this block, we'll go ahead and continue.
3060 Recognize first pass by local_set NULL. On subsequent passes, we
3061 get to skip out early if live_at_end wouldn't have changed. */
3064 {
3067 }
3068 else
3069 {
3070 /* If any bits were removed from live_at_end, we'll have to
3071 rescan the block. This wouldn't be necessary if we had
3072 precalculated local_live, however with PROP_SCAN_DEAD_CODE
3073 local_live is really dependant on live_at_end. */
3079 {
3080 /* Find the set of changed bits. Take this opportunity
3081 to notice that this set is empty and early out. */
3088 /* If any of the changed bits overlap with local_set,
3089 we'll have to rescan the block. Detect overlap by
3090 the AND with ~local_set turning off bits. */
3092 BITMAP_AND_COMPL);
3093 }
3094 }
3096 /* Let our caller know that BB changed enough to require its
3097 death notes updated. */
3101 {
3102 /* Add to live_at_start the set of all registers in
3103 new_live_at_end that aren't in the old live_at_end. */
3106 BITMAP_AND_COMPL);
3114 }
3115 else
3116 {
3119 /* Rescan the block insn by insn to turn (a copy of) live_at_end
3120 into live_at_start. */
3124 /* If live_at start didn't change, no need to go farther. */
3129 }
3131 /* Queue all predecessors of BB so that we may re-examine
3132 their live_at_end. */
3134 {
3137 {
3142 }
3143 }
3144 }
3150 {
3153 });
3156 }
3157 \f
3158 /* Subroutines of life analysis. */
3160 /* Allocate the permanent data structures that represent the results
3161 of life analysis. Not static since used also for stupid life analysis. */
3163 void
3165 {
3169 {
3174 }
3176 ENTRY_BLOCK_PTR->global_live_at_end
3178 EXIT_BLOCK_PTR->global_live_at_start
3182 }
3184 void
3186 {
3189 /* Recalculate the register space, in case it has grown. Old style
3190 vector oriented regsets would set regset_{size,bytes} here also. */
3193 /* Reset all the data we'll collect in propagate_block and its
3194 subroutines. */
3196 {
3203 }
3204 }
3206 /* Compute the registers live at the beginning of a basic block
3207 from those live at the end.
3209 When called, OLD contains those live at the end.
3210 On return, it contains those live at the beginning.
3211 FIRST and LAST are the first and last insns of the basic block.
3213 FINAL is nonzero if we are doing the final pass which is not
3214 for computing the life info (since that has already been done)
3215 but for acting on it. On this pass, we delete dead stores,
3216 set up the logical links and dead-variables lists of instructions,
3217 and merge instructions for autoincrement and autodecrement addresses.
3219 SIGNIFICANT is nonzero only the first time for each basic block.
3220 If it is nonzero, it points to a regset in which we store
3221 a 1 for each register that is set within the block.
3223 BNUM is the number of the basic block. */
3225 static void
3228 rtx first;
3229 rtx last;
3230 regset significant;
3233 {
3235 rtx prev;
3236 regset live;
3237 regset dead;
3239 /* Find the loop depth for this block. Ignore loop level changes in the
3240 middle of the basic block -- for register allocation purposes, the
3241 important uses will be in the blocks wholely contained within the loop
3242 not in the loop pre-header or post-trailer. */
3251 {
3254 /* Process the regs live at the end of the block.
3255 Mark them as not local to any one basic block. */
3257 {
3259 });
3260 }
3262 /* Scan the block an insn at a time from end to beginning. */
3265 {
3269 {
3270 /* If this is a call to `setjmp' et al,
3271 warn if any non-volatile datum is live. */
3276 }
3278 /* Update the life-status of regs for this insn.
3279 First DEAD gets which regs are set in this insn
3280 then LIVE gets which regs are used in this insn.
3281 Then the regs live before the insn
3282 are those live after, with DEAD regs turned off,
3283 and then LIVE regs turned on. */
3286 {
3293 {
3295 /* Don't delete something that refers to volatile storage! */
3299 }
3301 /* We almost certainly don't want to delete prologue or epilogue
3302 instructions. Warn about probable compiler losage. */
3304 && insn_is_dead
3305 && reload_completed
3308 {
3312 }
3314 /* If an instruction consists of just dead store(s) on final pass,
3315 "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
3316 We could really delete it with delete_insn, but that
3317 can cause trouble for first or last insn in a basic block. */
3319 {
3320 rtx inote;
3321 /* If the insn referred to a label, note that the label is
3322 now less used. */
3324 {
3326 {
3328 rtx next;
3331 /* If this label was attached to an ADDR_VEC, it's
3332 safe to delete the ADDR_VEC. In fact, it's pretty much
3333 mandatory to delete it, because the ADDR_VEC may
3334 be referencing labels that no longer exist. */
3340 {
3350 }
3351 }
3352 }
3358 /* CC0 is now known to be dead. Either this insn used it,
3359 in which case it doesn't anymore, or clobbered it,
3360 so the next insn can't use it. */
3363 /* If this insn is copying the return value from a library call,
3364 delete the entire library call. */
3366 {
3372 {
3377 }
3378 }
3380 }
3385 /* See if this is an increment or decrement that can be
3386 merged into a following memory address. */
3387 #ifdef AUTO_INC_DEC
3388 {
3391 /* Does this instruction increment or decrement a register? */
3400 /* Ok, look for a following memory ref we can combine with.
3401 If one is found, change the memory ref to a PRE_INC
3402 or PRE_DEC, cancel this insn, and return 1.
3403 Return 0 if nothing has been done. */
3406 }
3409 /* If this is not the final pass, and this insn is copying the
3410 value of a library call and it's dead, don't scan the
3411 insns that perform the library call, so that the call's
3412 arguments are not marked live. */
3414 {
3415 /* Mark the dest reg as `significant'. */
3421 }
3427 /* We have an insn to pop a constant amount off the stack.
3428 (Such insns use PLUS regardless of the direction of the stack,
3429 and any insn to adjust the stack by a constant is always a pop.)
3430 These insns, if not dead stores, have no effect on life. */
3431 ;
3432 else
3433 {
3434 /* Any regs live at the time of a call instruction
3435 must not go in a register clobbered by calls.
3436 Find all regs now live and record this for them. */
3441 {
3443 });
3445 /* LIVE gets the regs used in INSN;
3446 DEAD gets those set by it. Dead insns don't make anything
3447 live. */
3452 /* If an insn doesn't use CC0, it becomes dead since we
3453 assume that every insn clobbers it. So show it dead here;
3454 mark_used_regs will set it live if it is referenced. */
3460 /* Sometimes we may have inserted something before INSN (such as
3461 a move) when we make an auto-inc. So ensure we will scan
3462 those insns. */
3463 #ifdef AUTO_INC_DEC
3465 #endif
3468 {
3471 rtx note;
3474 note;
3480 /* Each call clobbers all call-clobbered regs that are not
3481 global or fixed. Note that the function-value reg is a
3482 call-clobbered reg, and mark_set_regs has already had
3483 a chance to handle it. */
3488 {
3492 }
3494 /* The stack ptr is used (honorarily) by a CALL insn. */
3497 /* Calls may also reference any of the global registers,
3498 so they are made live. */
3505 /* Calls also clobber memory. */
3507 }
3509 /* Update OLD for the registers used or set. */
3513 }
3515 /* On final pass, update counts of how many insns each reg is live
3516 at. */
3520 }
3521 flushed: ;
3524 }
3529 }
3530 \f
3531 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3532 (SET expressions whose destinations are registers dead after the insn).
3533 NEEDED is the regset that says which regs are alive after the insn.
3535 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3537 If X is the entire body of an insn, NOTES contains the reg notes
3538 pertaining to the insn. */
3540 static int
3542 rtx x;
3543 regset needed;
3545 rtx notes ATTRIBUTE_UNUSED;
3546 {
3549 #ifdef AUTO_INC_DEC
3550 /* If flow is invoked after reload, we must take existing AUTO_INC
3551 expresions into account. */
3553 {
3555 {
3557 {
3560 /* Don't delete insns to set global regs. */
3564 }
3565 }
3566 }
3567 #endif
3569 /* If setting something that's a reg or part of one,
3570 see if that register's altered value will be live. */
3573 {
3576 /* A SET that is a subroutine call cannot be dead. */
3580 #ifdef HAVE_cc0
3583 #endif
3586 {
3587 rtx temp;
3588 /* Walk the set of memory locations we are currently tracking
3589 and see if one is an identical match to this memory location.
3590 If so, this memory write is dead (remember, we're walking
3591 backwards from the end of the block to the start. */
3594 {
3598 }
3599 }
3606 {
3609 /* Don't delete insns to set global regs. */
3611 /* Make sure insns to set frame pointer aren't deleted. */
3614 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3617 #endif
3618 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3619 /* Make sure insns to set arg pointer are never deleted
3620 (if the arg pointer isn't fixed, there will be a USE for
3621 it, so we can treat it normally). */
3623 #endif
3627 /* If this is a hard register, verify that subsequent words are
3628 not needed. */
3630 {
3636 }
3639 }
3640 }
3642 /* If performing several activities,
3643 insn is dead if each activity is individually dead.
3644 Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
3645 that's inside a PARALLEL doesn't make the insn worth keeping. */
3647 {
3657 }
3659 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
3660 is not necessarily true for hard registers. */
3666 /* We do not check other CLOBBER or USE here. An insn consisting of just
3667 a CLOBBER or just a USE should not be deleted. */
3669 }
3671 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
3672 return 1 if the entire library call is dead.
3673 This is true if X copies a register (hard or pseudo)
3674 and if the hard return reg of the call insn is dead.
3675 (The caller should have tested the destination of X already for death.)
3677 If this insn doesn't just copy a register, then we don't
3678 have an ordinary libcall. In that case, cse could not have
3679 managed to substitute the source for the dest later on,
3680 so we can assume the libcall is dead.
3682 NEEDED is the bit vector of pseudoregs live before this insn.
3683 NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
3685 static int
3687 rtx x;
3688 regset needed;
3689 rtx note;
3690 rtx insn;
3691 {
3695 {
3698 {
3700 rtx call_pat;
3703 /* Find the call insn. */
3707 /* If there is none, do nothing special,
3708 since ordinary death handling can understand these insns. */
3712 /* See if the hard reg holding the value is dead.
3713 If this is a PARALLEL, find the call within it. */
3716 {
3722 /* This may be a library call that is returning a value
3723 via invisible pointer. Do nothing special, since
3724 ordinary death handling can understand these insns. */
3729 }
3732 }
3733 }
3735 }
3737 /* Return 1 if register REGNO was used before it was set, i.e. if it is
3738 live at function entry. Don't count global register variables, variables
3739 in registers that can be used for function arg passing, or variables in
3740 fixed hard registers. */
3742 int
3745 {
3754 }
3756 /* 1 if register REGNO was alive at a place where `setjmp' was called
3757 and was set more than once or is an argument.
3758 Such regs may be clobbered by `longjmp'. */
3760 int
3763 {
3770 }
3771 \f
3772 /* INSN references memory, possibly using autoincrement addressing modes.
3773 Find any entries on the mem_set_list that need to be invalidated due
3774 to an address change. */
3775 static void
3777 rtx insn;
3778 {
3781 {
3783 {
3786 rtx next;
3789 {
3792 {
3793 /* Splice temp out of list. */
3796 else
3799 }
3800 else
3803 }
3804 }
3805 }
3806 }
3808 /* Process the registers that are set within X. Their bits are set to
3809 1 in the regset DEAD, because they are dead prior to this insn.
3811 If INSN is nonzero, it is the insn being processed.
3813 FLAGS is the set of operations to perform. */
3815 static void
3817 regset needed;
3818 regset dead;
3819 rtx x;
3820 rtx insn;
3821 regset significant;
3823 {
3829 {
3832 {
3837 }
3838 }
3839 }
3841 /* Process a single SET rtx, X. */
3843 static void
3845 regset needed;
3846 regset dead;
3847 rtx x;
3848 rtx insn;
3849 regset significant;
3851 {
3855 /* Some targets place small structures in registers for
3856 return values of functions. We have to detect this
3857 case specially here to get correct flow information. */
3860 {
3867 }
3869 /* Modifying just one hardware register of a multi-reg value
3870 or just a byte field of a register
3871 does not mean the value from before this insn is now dead.
3872 But it does mean liveness of that register at the end of the block
3873 is significant.
3875 Within mark_set_1, however, we treat it as if the register is
3876 indeed modified. mark_used_regs will, however, also treat this
3877 register as being used. Thus, we treat these insns as setting a
3878 new value for the register as a function of its old value. This
3879 cases LOG_LINKS to be made appropriately and this will help combine. */
3886 /* If this set is a MEM, then it kills any aliased writes.
3887 If this set is a REG, then it kills any MEMs which use the reg. */
3889 {
3892 {
3895 rtx next;
3898 {
3904 {
3905 /* Splice this entry out of the list. */
3908 else
3911 }
3912 else
3915 }
3916 }
3918 /* If the memory reference had embedded side effects (autoincrement
3919 address modes. Then we may need to kill some entries on the
3920 memory set list. */
3925 /* We do not know the size of a BLKmode store, so we do not track
3926 them for redundant store elimination. */
3928 /* There are no REG_INC notes for SP, so we can't assume we'll see
3929 everything that invalidates it. To be safe, don't eliminate any
3930 stores though SP; none of them should be redundant anyway. */
3933 }
3939 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3942 #endif
3943 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3945 #endif
3947 /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
3948 {
3952 /* Mark it as a significant register for this basic block. */
3956 /* Mark it as dead before this insn. */
3959 /* A hard reg in a wide mode may really be multiple registers.
3960 If so, mark all of them just like the first. */
3962 {
3965 /* Nothing below is needed for the stack pointer; get out asap.
3966 Eg, log links aren't needed, since combine won't use them. */
3972 {
3981 }
3982 }
3984 /* Additional data to record if this is the final pass. */
3987 {
3995 /* If this is a hard reg, record this function uses the reg. */
3998 {
4004 {
4005 /* The next use is no longer "next", since a store
4006 intervenes. */
4008 }
4012 {
4015 }
4016 }
4017 else
4018 {
4019 /* The next use is no longer "next", since a store
4020 intervenes. */
4024 /* Keep track of which basic blocks each reg appears in. */
4027 {
4033 /* Count (weighted) references, stores, etc. This counts a
4034 register twice if it is modified, but that is correct. */
4038 /* The insns where a reg is live are normally counted
4039 elsewhere, but we want the count to include the insn
4040 where the reg is set, and the normal counting mechanism
4041 would not count it. */
4043 }
4044 }
4047 {
4049 {
4050 /* Make a logical link from the next following insn
4051 that uses this register, back to this insn.
4052 The following insns have already been processed.
4054 We don't build a LOG_LINK for hard registers containing
4055 in ASM_OPERANDs. If these registers get replaced,
4056 we might wind up changing the semantics of the insn,
4057 even if reload can make what appear to be valid
4058 assignments later. */
4063 }
4064 }
4066 {
4071 {
4072 /* Note that dead stores have already been deleted
4073 when possible. If we get here, we have found a
4074 dead store that cannot be eliminated (because the
4075 same insn does something useful). Indicate this
4076 by marking the reg being set as dying here. */
4079 }
4080 }
4081 else
4082 {
4084 {
4085 /* This is a case where we have a multi-word hard register
4086 and some, but not all, of the words of the register are
4087 needed in subsequent insns. Write REG_UNUSED notes
4088 for those parts that were not needed. This case should
4089 be rare. */
4097 = (alloc_EXPR_LIST
4101 }
4102 }
4103 }
4104 }
4106 {
4109 }
4111 /* If this is the last pass and this is a SCRATCH, show it will be dying
4112 here and count it. */
4114 {
4118 }
4119 }
4120 \f
4121 #ifdef AUTO_INC_DEC
4123 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
4124 reference. */
4126 static void
4128 regset needed;
4129 rtx x;
4130 rtx insn;
4131 {
4134 rtx set;
4136 /* Here we detect use of an index register which might be good for
4137 postincrement, postdecrement, preincrement, or predecrement. */
4143 {
4146 rtx use;
4147 rtx incr;
4150 /* Is the next use an increment that might make auto-increment? */
4155 /* Can't add side effects to jumps; if reg is spilled and
4156 reloaded, there's no way to store back the altered value. */
4161 && ((HAVE_POST_INCREMENT
4163 || (HAVE_POST_DECREMENT
4165 || (HAVE_PRE_INCREMENT
4167 || (HAVE_PRE_DECREMENT
4169 /* Make sure this reg appears only once in this insn. */
4172 {
4179 {
4180 /* This is the simple case. Try to make the auto-inc. If
4181 we can't, we are done. Otherwise, we will do any
4182 needed updates below. */
4187 }
4189 /* PREV_INSN used here to check the semi-open interval
4190 [insn,incr). */
4192 /* We must also check for sets of q as q may be
4193 a call clobbered hard register and there may
4194 be a call between PREV_INSN (insn) and incr. */
4196 {
4197 /* We have *p followed sometime later by q = p+size.
4198 Both p and q must be live afterward,
4199 and q is not used between INSN and its assignment.
4200 Change it to q = p, ...*q..., q = q+size.
4201 Then fall into the usual case. */
4203 basic_block bb;
4214 /* If we can't make the auto-inc, or can't make the
4215 replacement into Y, exit. There's no point in making
4216 the change below if we can't do the auto-inc and doing
4217 so is not correct in the pre-inc case. */
4226 /* We now know we'll be doing this change, so emit the
4227 new insn(s) and do the updates. */
4233 /* INCR will become a NOTE and INSN won't contain a
4234 use of ADDR. If a use of ADDR was just placed in
4235 the insn before INSN, make that the next use.
4236 Otherwise, invalidate it. */
4241 else
4247 /* REGNO is now used in INCR which is below INSN, but
4248 it previously wasn't live here. If we don't mark
4249 it as needed, we'll put a REG_DEAD note for it
4250 on this insn, which is incorrect. */
4253 /* If there are any calls between INSN and INCR, show
4254 that REGNO now crosses them. */
4258 }
4259 else
4262 /* If we haven't returned, it means we were able to make the
4263 auto-inc, so update the status. First, record that this insn
4264 has an implicit side effect. */
4269 /* Modify the old increment-insn to simply copy
4270 the already-incremented value of our register. */
4274 /* If that makes it a no-op (copying the register into itself) delete
4275 it so it won't appear to be a "use" and a "set" of this
4276 register. */
4278 {
4282 }
4285 {
4286 /* Count an extra reference to the reg. When a reg is
4287 incremented, spilling it is worse, so we want to make
4288 that less likely. */
4291 /* Count the increment as a setting of the register,
4292 even though it isn't a SET in rtl. */
4294 }
4295 }
4296 }
4297 }
4299 \f
4300 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
4301 This is done assuming the registers needed from X
4302 are those that have 1-bits in NEEDED.
4304 FLAGS is the set of enabled operations.
4306 INSN is the containing instruction. If INSN is dead, this function is not
4307 called. */
4309 static void
4311 regset needed;
4312 regset live;
4313 rtx x;
4315 rtx insn;
4316 {
4321 retry:
4324 {
4335 #ifdef HAVE_cc0
4339 #endif
4342 /* If we are clobbering a MEM, mark any registers inside the address
4343 as being used. */
4349 /* Don't bother watching stores to mems if this is not the
4350 final pass. We'll not be deleting dead stores this round. */
4352 {
4353 /* Invalidate the data for the last MEM stored, but only if MEM is
4354 something that can be stored into. */
4358 else
4359 {
4362 rtx next;
4365 {
4368 {
4369 /* Splice temp out of the list. */
4372 else
4375 }
4376 else
4379 }
4380 }
4382 /* If the memory reference had embedded side effects (autoincrement
4383 address modes. Then we may need to kill some entries on the
4384 memory set list. */
4387 }
4389 #ifdef AUTO_INC_DEC
4392 #endif
4402 /* While we're here, optimize this case. */
4405 /* In case the SUBREG is not of a register, don't optimize */
4407 {
4410 }
4412 /* ... fall through ... */
4415 /* See a register other than being set
4416 => mark it as needed. */
4419 {
4425 /* A hard reg in a wide mode may really be multiple registers.
4426 If so, mark all of them just like the first. */
4428 {
4431 /* For stack ptr or fixed arg pointer,
4432 nothing below can be necessary, so waste no more time. */
4434 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4437 #endif
4438 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4440 #endif
4443 {
4444 /* If this is a register we are going to try to eliminate,
4445 don't mark it live here. If we are successful in
4446 eliminating it, it need not be live unless it is used for
4447 pseudos, in which case it will have been set live when
4448 it was allocated to the pseudos. If the register will not
4449 be eliminated, reload will set it live at that point. */
4454 }
4455 /* No death notes for global register variables;
4456 their values are live after this function exits. */
4458 {
4462 }
4466 {
4473 }
4474 }
4477 {
4478 /* Record where each reg is used, so when the reg
4479 is set we know the next insn that uses it. */
4482 }
4484 {
4486 {
4487 /* If a hard reg is being used,
4488 record that this function does use it. */
4493 do
4496 }
4497 else
4498 {
4499 /* Keep track of which basic block each reg appears in. */
4508 /* Count (weighted) number of uses of each reg. */
4511 }
4512 }
4514 /* Record and count the insns in which a reg dies.
4515 If it is used in this insn and was dead below the insn
4516 then it dies in this insn. If it was set in this insn,
4517 we do not make a REG_DEAD note; likewise if we already
4518 made such a note. */
4521 {
4524 #if 0
4526 #endif
4527 )
4528 {
4529 /* Check for the case where the register dying partially
4530 overlaps the register set by this insn. */
4533 {
4537 }
4539 /* If none of the words in X is needed, make a REG_DEAD
4540 note. Otherwise, we must make partial REG_DEAD notes. */
4542 {
4546 }
4547 else
4548 {
4551 /* Don't make a REG_DEAD note for a part of a register
4552 that is set in the insn. */
4559 = (alloc_EXPR_LIST
4563 }
4564 }
4565 }
4566 }
4570 {
4574 /* If storing into MEM, don't show it as being used. But do
4575 show the address as being used. */
4577 {
4578 #ifdef AUTO_INC_DEC
4581 #endif
4585 }
4587 /* Storing in STRICT_LOW_PART is like storing in a reg
4588 in that this SET might be dead, so ignore it in TESTREG.
4589 but in some other ways it is like using the reg.
4591 Storing in a SUBREG or a bit field is like storing the entire
4592 register in that if the register's value is not used
4593 then this SET is not needed. */
4598 {
4606 /* Modifying a single register in an alternate mode
4607 does not use any of the old value. But these other
4608 ways of storing in a register do use the old value. */
4611 ;
4612 else
4616 }
4618 /* If this is a store into a register,
4619 recursively scan the value being stored. */
4626 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4629 #endif
4630 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4632 #endif
4633 ))
4634 /* We used to exclude global_regs here, but that seems wrong.
4635 Storing in them is like storing in mem. */
4636 {
4641 }
4642 }
4646 /* ??? This info should have been gotten from mark_regs_live_at_end,
4647 as applied to the EXIT block, and propagated along the edge that
4648 connects this block to the EXIT. */
4655 {
4656 /* Traditional and volatile asm instructions must be considered to use
4657 and clobber all hard registers, all pseudo-registers and all of
4658 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
4660 Consider for instance a volatile asm that changes the fpu rounding
4661 mode. An insn should not be moved across this even if it only uses
4662 pseudo-regs because it might give an incorrectly rounded result.
4664 ?!? Unfortunately, marking all hard registers as live causes massive
4665 problems for the register allocator and marking all pseudos as live
4666 creates mountains of uninitialized variable warnings.
4668 So for now, just clear the memory set list and mark any regs
4669 we can find in ASM_OPERANDS as used. */
4673 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
4674 We can not just fall through here since then we would be confused
4675 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
4676 traditional asms unlike their normal usage. */
4678 {
4684 }
4686 }
4691 }
4693 /* Recursively scan the operands of this expression. */
4695 {
4700 {
4702 {
4703 /* Tail recursive case: save a function call level. */
4705 {
4708 }
4710 }
4712 {
4716 }
4717 }
4718 }
4719 }
4720 \f
4721 #ifdef AUTO_INC_DEC
4723 static int
4725 rtx insn;
4726 {
4727 /* Find the next use of this reg. If in same basic block,
4728 make it do pre-increment or pre-decrement if appropriate. */
4736 /* Don't do this if the reg dies, or gets set in y; a standard addressing
4737 mode would be better. */
4740 {
4741 /* We have found a suitable auto-increment
4742 and already changed insn Y to do it.
4743 So flush this increment-instruction. */
4747 /* Count a reference to this reg for the increment
4748 insn we are deleting. When a reg is incremented.
4749 spilling it is worse, so we want to make that
4750 less likely. */
4752 {
4755 }
4757 }
4759 }
4761 /* Try to change INSN so that it does pre-increment or pre-decrement
4762 addressing on register REG in order to add AMOUNT to REG.
4763 AMOUNT is negative for pre-decrement.
4764 Returns 1 if the change could be made.
4765 This checks all about the validity of the result of modifying INSN. */
4767 static int
4770 HOST_WIDE_INT amount;
4771 {
4774 /* Nonzero if we can try to make a pre-increment or pre-decrement.
4775 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
4777 /* Nonzero if we can try to make a post-increment or post-decrement.
4778 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
4779 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
4780 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
4783 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
4786 /* From the sign of increment, see which possibilities are conceivable
4787 on this target machine. */
4801 /* It is not safe to add a side effect to a jump insn
4802 because if the incremented register is spilled and must be reloaded
4803 there would be no way to store the incremented value back in memory. */
4812 {
4815 }
4823 /* See if this combination of instruction and addressing mode exists. */
4831 /* Record that this insn now has an implicit side effect on X. */
4834 }
4837 \f
4838 /* Find the place in the rtx X where REG is used as a memory address.
4839 Return the MEM rtx that so uses it.
4840 If PLUSCONST is nonzero, search instead for a memory address equivalent to
4841 (plus REG (const_int PLUSCONST)).
4843 If such an address does not appear, return 0.
4844 If REG appears more than once, or is used other than in such an address,
4845 return (rtx)1. */
4847 rtx
4850 rtx reg;
4851 HOST_WIDE_INT plusconst;
4852 {
4869 {
4870 /* If REG occurs inside a MEM used in a bit-field reference,
4871 that is unacceptable. */
4874 }
4880 {
4882 {
4888 }
4890 {
4893 {
4899 }
4900 }
4901 }
4904 }
4905 \f
4906 /* Write information about registers and basic blocks into FILE.
4907 This is part of making a debugging dump. */
4909 void
4912 {
4919 {
4941 {
4946 else
4950 }
4954 }
4958 {
4976 {
4980 }
4981 else
4986 {
4990 }
4991 else
4995 }
4998 }
5000 void
5002 {
5004 }
5006 static void
5009 edge e;
5011 {
5018 else
5022 {
5025 };
5033 {
5040 else
5043 }
5045 }
5046 }
5048 \f
5049 /* Like print_rtl, but also print out live information for the start of each
5050 basic block. */
5052 void
5055 rtx rtx_first;
5056 {
5061 else
5062 {
5074 {
5076 rtx x;
5081 {
5089 }
5090 }
5093 {
5095 basic_block bb;
5098 {
5103 {
5108 });
5110 }
5127 }
5132 }
5135 {
5140 }
5141 }
5143 \f
5144 /* Integer list support. */
5146 /* Allocate a node from list *HEAD_PTR. */
5148 static int_list_ptr
5151 {
5155 {
5160 }
5164 }
5166 /* Pointer to head of predecessor/successor block list. */
5169 /* Add a new node to integer list LIST with value VAL.
5170 LIST is a pointer to a list object to allow for different implementations.
5171 If *LIST is initially NULL, the list is empty.
5172 The caller must not care whether the element is added to the front or
5173 to the end of the list (to allow for different implementations). */
5175 static int_list_ptr
5180 {
5187 }
5189 /* Free the blocks of lists at BLK_LIST. */
5191 void
5194 {
5198 {
5201 }
5203 /* Mark list as empty for the next function we compile. */
5205 }
5206 \f
5207 /* Predecessor/successor computation. */
5209 /* Mark PRED_BB a precessor of SUCC_BB,
5210 and conversely SUCC_BB a successor of PRED_BB. */
5212 static void
5220 {
5222 {
5225 }
5227 {
5230 }
5231 }
5233 /* Convert edge lists into pred/succ lists for backward compatibility. */
5235 void
5241 {
5243 edge e;
5251 {
5257 }
5262 }
5264 void
5270 {
5272 int_list_ptr p;
5276 {
5281 {
5285 else
5287 }
5291 {
5295 else
5297 }
5299 {
5306 }
5308 }
5310 }
5312 /* Free basic block data storage. */
5314 void
5316 {
5318 }
5320 /* Compute dominator relationships using new flow graph structures. */
5321 void
5325 {
5328 edge e;
5331 /* Allocate a worklist array/queue. Entries are only added to the
5332 list if they were not already on the list. So the size is
5333 bounded by the number of basic blocks. */
5341 {
5342 /* The optimistic setting of dominators requires us to put every
5343 block on the work list initially. */
5345 {
5348 }
5350 /* We want a maximal solution, so initially assume everything dominates
5351 everything else. */
5354 /* Mark successors of the entry block so we can identify them below. */
5358 /* Iterate until the worklist is empty. */
5360 {
5361 /* Take the first entry off the worklist. */
5365 /* Compute the intersection of the dominators of all the
5366 predecessor blocks.
5368 If one of the predecessor blocks is the ENTRY block, then the
5369 intersection of the dominators of the predecessor blocks is
5370 defined as the null set. We can identify such blocks by the
5371 special value in the AUX field in the block structure. */
5373 {
5374 /* Do not clear the aux field for blocks which are
5375 successors of the ENTRY block. That way we we never
5376 add them to the worklist again.
5378 The intersect of dominators of the preds of this block is
5379 defined as the null set. */
5381 }
5382 else
5383 {
5384 /* Clear the aux field of this block so it can be added to
5385 the worklist again if necessary. */
5388 }
5390 /* Make sure each block always dominates itself. */
5393 /* If the out state of this block changed, then we need to
5394 add the successors of this block to the worklist if they
5395 are not already on the worklist. */
5397 {
5399 {
5401 {
5404 }
5405 }
5406 }
5407 }
5408 }
5411 {
5412 /* The optimistic setting of dominators requires us to put every
5413 block on the work list initially. */
5415 {
5418 }
5420 /* We want a maximal solution, so initially assume everything post
5421 dominates everything else. */
5424 /* Mark predecessors of the exit block so we can identify them below. */
5428 /* Iterate until the worklist is empty. */
5430 {
5431 /* Take the first entry off the worklist. */
5435 /* Compute the intersection of the post dominators of all the
5436 successor blocks.
5438 If one of the successor blocks is the EXIT block, then the
5439 intersection of the dominators of the successor blocks is
5440 defined as the null set. We can identify such blocks by the
5441 special value in the AUX field in the block structure. */
5443 {
5444 /* Do not clear the aux field for blocks which are
5445 predecessors of the EXIT block. That way we we never
5446 add them to the worklist again.
5448 The intersect of dominators of the succs of this block is
5449 defined as the null set. */
5451 }
5452 else
5453 {
5454 /* Clear the aux field of this block so it can be added to
5455 the worklist again if necessary. */
5459 }
5461 /* Make sure each block always post dominates itself. */
5464 /* If the out state of this block changed, then we need to
5465 add the successors of this block to the worklist if they
5466 are not already on the worklist. */
5470 {
5472 {
5474 {
5477 }
5478 }
5479 }
5480 }
5481 }
5483 }
5485 /* Given DOMINATORS, compute the immediate dominators into IDOM. */
5487 void
5491 {
5497 /* Begin with tmp(n) = dom(n) - { n }. */
5499 {
5502 }
5504 /* Subtract out all of our dominator's dominators. */
5506 {
5513 }
5515 /* Find the one bit set in the bitmap and put it in the output array. */
5517 {
5520 }
5523 }
5525 /* Count for a single SET rtx, X. */
5527 static void
5529 rtx x;
5530 {
5534 /* Find the register that's set/clobbered. */
5542 {
5547 }
5550 {
5553 {
5554 /* Count (weighted) references, stores, etc. This counts a
5555 register twice if it is modified, but that is correct. */
5559 }
5560 }
5561 }
5563 /* Increment REG_N_SETS for each SET or CLOBBER found in X; also increment
5564 REG_N_REFS by the current loop depth for each SET or CLOBBER found. */
5566 static void
5568 rtx x;
5569 {
5575 {
5578 {
5582 }
5583 }
5584 }
5586 /* Increment REG_N_REFS by the current loop depth each register reference
5587 found in X. */
5589 static void
5591 rtx x;
5592 {
5595 retry:
5598 {
5610 #ifdef HAVE_cc0
5613 #endif
5616 /* If we are clobbering a MEM, mark any registers inside the address
5617 as being used. */
5623 /* While we're here, optimize this case. */
5626 /* In case the SUBREG is not of a register, don't optimize */
5628 {
5631 }
5633 /* ... fall through ... */
5641 {
5645 /* If storing into MEM, don't show it as being used. But do
5646 show the address as being used. */
5648 {
5652 }
5654 /* Storing in STRICT_LOW_PART is like storing in a reg
5655 in that this SET might be dead, so ignore it in TESTREG.
5656 but in some other ways it is like using the reg.
5658 Storing in a SUBREG or a bit field is like storing the entire
5659 register in that if the register's value is not used
5660 then this SET is not needed. */
5665 {
5666 /* Modifying a single register in an alternate mode
5667 does not use any of the old value. But these other
5668 ways of storing in a register do use the old value. */
5671 ;
5672 else
5676 }
5678 /* If this is a store into a register,
5679 recursively scan the value being stored. */
5684 {
5689 }
5690 }
5695 }
5697 /* Recursively scan the operands of this expression. */
5699 {
5704 {
5706 {
5707 /* Tail recursive case: save a function call level. */
5709 {
5712 }
5714 }
5716 {
5720 }
5721 }
5722 }
5723 }
5725 /* Recompute register set/reference counts immediately prior to register
5726 allocation.
5728 This avoids problems with set/reference counts changing to/from values
5729 which have special meanings to the register allocators.
5731 Additionally, the reference counts are the primary component used by the
5732 register allocators to prioritize pseudos for allocation to hard regs.
5733 More accurate reference counts generally lead to better register allocation.
5735 F is the first insn to be scanned.
5736 LOOP_STEP denotes how much loop_depth should be incremented per
5737 loop nesting level in order to increase the ref count more for references
5738 in a loop.
5740 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
5741 possibly other information which is used by the register allocators. */
5743 void
5745 rtx f;
5747 {
5748 rtx insn;
5751 /* Clear out the old data. */
5754 {
5757 }
5759 /* Scan each insn in the chain and count how many times each register is
5760 set/used. */
5763 {
5764 /* Keep track of loop depth. */
5766 {
5767 /* Look for loop boundaries. */
5773 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
5774 Abort now rather than setting register status incorrectly. */
5777 }
5779 {
5780 rtx links;
5782 /* This call will increment REG_N_SETS for each SET or CLOBBER
5783 of a register in INSN. It will also increment REG_N_REFS
5784 by the loop depth for each set of a register in INSN. */
5787 /* count_reg_sets does not detect autoincrement address modes, so
5788 detect them here by looking at the notes attached to INSN. */
5790 {
5792 /* Count (weighted) references, stores, etc. This counts a
5793 register twice if it is modified, but that is correct. */
5795 }
5797 /* This call will increment REG_N_REFS by the current loop depth for
5798 each reference to a register in INSN. */
5801 /* count_reg_references will not include counts for arguments to
5802 function calls, so detect them here by examining the
5803 CALL_INSN_FUNCTION_USAGE data. */
5805 {
5806 rtx note;
5809 note;
5813 }
5814 }
5815 }
5816 }
5818 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
5819 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
5820 of the number of registers that died. */
5822 int
5824 sbitmap blocks;
5826 {
5830 {
5831 basic_block bb;
5832 rtx insn;
5840 {
5842 {
5847 {
5849 {
5852 {
5858 else
5861 }
5862 /* FALLTHRU */
5866 {
5871 }
5872 /* FALLTHRU */
5878 }
5879 }
5880 }
5884 }
5885 }
5888 }
5890 /* Record INSN's block as BB. */
5892 void
5894 rtx insn;
5895 basic_block bb;
5896 {
5899 {
5902 /* Add one-eighth the size so we don't keep calling xrealloc. */
5906 }
5908 }
5910 /* Record INSN's block number as BB. */
5911 /* ??? This has got to go. */
5913 void
5915 rtx insn;
5917 {
5919 }
5920 \f
5921 /* Verify the CFG consistency. This function check some CFG invariants and
5922 aborts when something is wrong. Hope that this function will help to
5923 convert many optimization passes to preserve CFG consistent.
5925 Currently it does following checks:
5927 - test head/end pointers
5928 - overlapping of basic blocks
5929 - edge list corectness
5930 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
5931 - tails of basic blocks (ensure that boundary is necesary)
5932 - scans body of the basic block for JUMP_INSN, CODE_LABEL
5933 and NOTE_INSN_BASIC_BLOCK
5934 - check that all insns are in the basic blocks
5935 (except the switch handling code, barriers and notes)
5937 In future it can be extended check a lot of other stuff as well
5938 (reachability of basic blocks, life information, etc. etc.). */
5940 void
5942 {
5946 rtx x;
5951 /* First pass check head/end pointers and set bb_info array used by
5952 later passes. */
5954 {
5957 /* Check the head pointer and make sure that it is pointing into
5958 insn list. */
5963 {
5967 }
5969 /* Check the end pointer and make sure that it is pointing into
5970 insn list. */
5972 {
5974 {
5978 }
5983 }
5985 {
5989 }
5990 }
5992 /* Now check the basic blocks (boundaries etc.) */
5994 {
5996 /* Check corectness of edge lists */
5997 edge e;
6001 {
6003 {
6012 }
6014 {
6019 {
6022 }
6023 }
6025 }
6029 {
6031 {
6039 }
6041 {
6046 {
6049 }
6050 }
6052 }
6054 /* OK pointers are correct. Now check the header of basic
6055 block. It ought to contain optional CODE_LABEL followed
6056 by NOTE_BASIC_BLOCK. */
6059 {
6061 {
6065 }
6067 }
6071 {
6075 }
6078 {
6079 /* Do checks for empty blocks here */
6080 }
6081 else
6082 {
6085 {
6088 {
6092 }
6100 {
6103 }
6106 }
6107 }
6108 }
6112 {
6114 {
6116 {
6122 /* An addr_vec is placed outside any block block. */
6127 {
6129 }
6131 /* But in any case, non-deletable labels can appear anywhere. */
6136 }
6137 }
6140 }
6145 /* Clean up. */
6147 }
6148 \f
6149 /* Functions to access an edge list with a vector representation.
6150 Enough data is kept such that given an index number, the
6151 pred and succ that edge reprsents can be determined, or
6152 given a pred and a succ, it's index number can be returned.
6153 This allows algorithms which comsume a lot of memory to
6154 represent the normally full matrix of edge (pred,succ) with a
6155 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
6156 wasted space in the client code due to sparse flow graphs. */
6158 /* This functions initializes the edge list. Basically the entire
6159 flowgraph is processed, and all edges are assigned a number,
6160 and the data structure is filed in. */
6163 {
6165 edge e;
6174 /* Determine the number of edges in the flow graph by counting successor
6175 edges on each basic block. */
6177 {
6181 num_edges++;
6182 }
6183 /* Don't forget successors of the entry block. */
6185 num_edges++;
6194 /* Follow successors of the entry block, and register these edges. */
6196 {
6198 num_edges++;
6199 }
6202 {
6205 /* Follow all successors of blocks, and register these edges. */
6207 {
6209 num_edges++;
6210 }
6211 }
6213 }
6215 /* This function free's memory associated with an edge list. */
6216 void
6219 {
6221 {
6224 }
6225 }
6227 /* This function provides debug output showing an edge list. */
6228 void
6232 {
6238 {
6242 else
6247 else
6249 }
6250 }
6252 /* This function provides an internal consistancy check of an edge list,
6253 verifying that all edges are present, and that there are no
6254 extra edges. */
6255 void
6259 {
6261 edge e;
6264 {
6268 {
6273 {
6276 }
6283 }
6284 }
6286 {
6291 {
6294 }
6301 }
6302 /* We've verified that all the edges are in the list, no lets make sure
6303 there are no spurious edges in the list. */
6307 {
6315 {
6318 }
6321 {
6324 }
6334 }
6336 {
6344 {
6347 }
6350 {
6353 }
6357 succ);
6363 }
6365 {
6373 {
6376 }
6379 {
6382 }
6386 pred);
6391 EXIT_BLOCK_PTR));
6392 }
6393 }
6395 /* This routine will determine what, if any, edge there is between
6396 a specified predecessor and successor. */
6398 int
6402 {
6405 {
6409 }
6411 }
6413 /* This function will remove an edge from the flow graph. */
6414 static void
6416 edge e;
6417 {
6420 edge tmp;
6431 else
6441 else
6444 n_edges--;
6446 }
6448 /* This routine will remove any fake successor edges for a basic block.
6449 When the edge is removed, it is also removed from whatever predecessor
6450 list it is in. */
6451 static void
6453 basic_block bb;
6454 {
6455 edge e;
6457 {
6462 }
6463 }
6465 /* This routine will remove all fake edges from the flow graph. If
6466 we remove all fake successors, it will automatically remove all
6467 fake predecessors. */
6468 void
6470 {
6476 /* We've handled all successors except the entry block's. */
6478 }
6480 /* This functions will add a fake edge between any block which has no
6481 successors, and the exit block. Some data flow equations require these
6482 edges to exist. */
6483 void
6485 {
6491 }