| blob | ea1a3d57b01d0084a792f39bd25314cda9a3250a |
1 /* Perform various loop optimizations, including strength reduction.
2 Copyright (C) 1987, 88, 89, 91-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 is the loop optimization pass of the compiler.
23 It finds invariant computations within loops and moves them
24 to the beginning of the loop. Then it identifies basic and
25 general induction variables. Strength reduction is applied to the general
26 induction variables, and induction variable elimination is applied to
27 the basic induction variables.
29 It also finds cases where
30 a register is set within the loop by zero-extending a narrower value
31 and changes these to zero the entire register once before the loop
32 and merely copy the low part within the loop.
34 Most of the complexity is in heuristics to decide when it is worth
35 while to do these things. */
54 /* Information about the loop being processed used to compute
55 the number of loop iterations for loop unrolling and doloop
56 optimization. */
59 /* Vector mapping INSN_UIDs to luids.
60 The luids are like uids but increase monotonically always.
61 We use them to see whether a jump comes from outside a given loop. */
65 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
66 number the insn is contained in. */
70 /* 1 + largest uid of any insn. */
74 /* 1 + luid of last insn. */
78 /* Number of loops detected in current function. Used as index to the
79 next few tables. */
83 /* Indexed by loop number, contains the first and last insn of each loop. */
87 /* Likewise for the continue insn */
90 /* The first code_label that is reached in every loop iteration.
91 0 when not computed yet, initially const0_rtx if a jump couldn't be
92 followed.
93 Also set to 0 when there is no such label before the NOTE_INSN_LOOP_CONT
94 of this loop, or in verify_dominator, if a jump couldn't be followed. */
97 /* For each loop, gives the containing loop number, -1 if none. */
101 #ifdef HAVE_decrement_and_branch_on_count
102 /* Records whether resource in use by inner loop. */
107 /* Indexed by loop number, contains a nonzero value if the "loop" isn't
108 really a loop (an insn outside the loop branches into it). */
112 /* Indexed by loop number, links together all LABEL_REFs which refer to
113 code labels outside the loop. Used by routines that need to know all
114 loop exits, such as final_biv_value and final_giv_value.
116 This does not include loop exits due to return instructions. This is
117 because all bivs and givs are pseudos, and hence must be dead after a
118 return, so the presense of a return does not affect any of the
119 optimizations that use this info. It is simpler to just not include return
120 instructions on this list. */
124 /* Indexed by loop number, counts the number of LABEL_REFs on
125 loop_number_exit_labels for this loop and all loops nested inside it. */
129 /* Indexed by register number, contains the number of times the reg
130 is set during the loop being scanned.
131 During code motion, a negative value indicates a reg that has been
132 made a candidate; in particular -2 means that it is an candidate that
133 we know is equal to a constant and -1 means that it is an candidate
134 not known equal to a constant.
135 After code motion, regs moved have 0 (which is accurate now)
136 while the failed candidates have the original number of times set.
138 Therefore, at all times, == 0 indicates an invariant register;
139 < 0 a conditionally invariant one. */
143 /* Original value of set_in_loop; same except that this value
144 is not set negative for a reg whose sets have been made candidates
145 and not set to 0 for a reg that is moved. */
149 /* Index by register number, 1 indicates that the register
150 cannot be moved or strength reduced. */
154 /* Contains the insn in which a register was used if it was used
155 exactly once; contains const0_rtx if it was used more than once. */
159 /* Nonzero means reg N has already been moved out of one loop.
160 This reduces the desire to move it out of another. */
164 /* List of MEMs that are stored in this loop. */
168 /* The insn where the first of these was found. */
177 /* Array of MEMs that are used (read or written) in this loop, but
178 cannot be aliased by anything in this loop, except perhaps
179 themselves. In other words, if loop_mems[i] is altered during the
180 loop, it is altered by an expression that is rtx_equal_p to it. */
184 /* The index of the next available slot in LOOP_MEMS. */
188 /* The number of elements allocated in LOOP_MEMs. */
192 /* Nonzero if we don't know what MEMs were changed in the current
193 loop. This happens if the loop contains a call (in which case
194 `loop_info->has_call' will also be set) or if we store into more
195 than NUM_STORES MEMs. */
199 /* Count of movable (i.e. invariant) instructions discovered in the loop. */
202 /* Count of memory write instructions discovered in the loop. */
205 /* Bound on pseudo register number before loop optimization.
206 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
209 /* This obstack is used in product_cheap_p to allocate its rtl. It
210 may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
211 If we used the same obstack that it did, we would be deallocating
212 that array. */
216 /* This is where the pointer to the obstack being used for RTL is stored. */
220 #define obstack_chunk_alloc xmalloc
221 #define obstack_chunk_free free
222 \f
223 /* During the analysis of a loop, a chain of `struct movable's
224 is made to record all the movable insns found.
225 Then the entire chain can be scanned to decide which to move. */
227 struct movable
228 {
233 of any registers used within the LIBCALL. */
235 that must be moved with this one. */
238 may be adjusted when matching movables
239 that load the same value are found. */
241 including other movables that force this
242 or match this one. */
246 /* If PARTIAL is 1, GLOBAL means something different:
247 that the reg is live outside the range from where it is set
248 to the following label. */
252 In particular, moving it does not make it
253 invariant. */
255 load SRC, rather than copying INSN. */
257 first insn of a consecutive sets group. */
260 that we should avoid changing when clearing
261 the rest of the reg. */
265 };
271 /* Forward declarations. */
287 #if 0
289 #endif
308 static void record_giv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx, int, enum g_types, int, int, rtx *, rtx, rtx));
336 rtx r;
341 rtx r1;
342 rtx r2;
345 /* Nonzero iff INSN is between START and END, inclusive. */
346 #define INSN_IN_RANGE_P(INSN, START, END) \
347 (INSN_UID (INSN) < max_uid_for_loop \
348 && INSN_LUID (INSN) >= INSN_LUID (START) \
349 && INSN_LUID (INSN) <= INSN_LUID (END))
351 #ifdef HAVE_decrement_and_branch_on_count
352 /* Test whether BCT applicable and safe. */
355 /* Auxiliary function that inserts the BCT pattern into the loop. */
359 /* Indirect_jump_in_function is computed once per function. */
367 \f
368 /* Relative gain of eliminating various kinds of operations. */
370 #if 0
373 #endif
375 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
376 copy the value of the strength reduced giv to its original register. */
379 /* Cost of using a register, to normalize the benefits of a giv. */
383 void
385 {
391 #ifdef ADDRESS_COST
393 #else
395 #endif
397 /* We multiply by 2 to reconcile the difference in scale between
398 these two ways of computing costs. Otherwise the cost of a copy
399 will be far less than the cost of an add. */
403 /* Free the objects we just allocated. */
406 /* Initialize the obstack used for rtl in product_cheap_p. */
408 }
409 \f
410 /* Compute the mapping from uids to luids.
411 LUIDs are numbers assigned to insns, like uids,
412 except that luids increase monotonically through the code.
413 Start at insn START and stop just before END. Assign LUIDs
414 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
415 static int
419 {
421 rtx insn;
424 {
427 /* Don't assign luids to line-number NOTEs, so that the distance in
428 luids between two insns is not affected by -g. */
432 else
433 /* Give a line number note the same luid as preceding insn. */
435 }
437 }
438 \f
439 /* Entry point of this file. Perform loop optimization
440 on the current function. F is the first insn of the function
441 and DUMPFILE is a stream for output of a trace of actions taken
442 (or 0 if none should be output). */
444 void
446 /* f is the first instruction of a chain of insns for one function */
447 rtx f;
450 {
465 /* Count the number of loops. */
469 {
472 max_loop_num++;
473 }
475 /* Don't waste time if no loops. */
479 /* Get size to use for tables indexed by uids.
480 Leave some space for labels allocated by find_and_verify_loops. */
489 /* Allocate tables for recording each loop. We set each entry, so they need
490 not be zeroed. */
500 #ifdef HAVE_decrement_and_branch_on_count
501 /* Allocate for BCT optimization */
506 /* Find and process each loop.
507 First, find them, and record them in order of their beginnings. */
510 /* Now find all register lifetimes. This must be done after
511 find_and_verify_loops, because it might reorder the insns in the
512 function. */
515 /* This must occur after reg_scan so that registers created by gcse
516 will have entries in the register tables.
518 We could have added a call to reg_scan after gcse_main in toplev.c,
519 but moving this call to init_alias_analysis is more efficient. */
522 /* See if we went too far. Note that get_max_uid already returns
523 one more that the maximum uid of all insn. */
526 /* Now reset it to the actual size we need. See above. */
529 /* find_and_verify_loops has already called compute_luids, but it might
530 have rearranged code afterwards, so we need to recompute the luids now. */
533 /* Don't leave gaps in uid_luid for insns that have been
534 deleted. It is possible that the first or last insn
535 using some register has been deleted by cross-jumping.
536 Make sure that uid_luid for that former insn's uid
537 points to the general area where that insn used to be. */
539 {
543 }
548 /* Create a mapping from loops to BLOCK tree nodes. */
552 /* Determine if the function has indirect jump. On some systems
553 this prevents low overhead loop instructions from being used. */
556 /* Now scan the loops, last ones first, since this means inner ones are done
557 before outer ones. */
563 /* If debugging and unrolling loops, we must replicate the tree nodes
564 corresponding to the blocks inside the loop, so that the original one
565 to one mapping will remain. */
570 }
571 \f
572 /* Returns the next insn, in execution order, after INSN. START and
573 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
574 respectively. LOOP_TOP, if non-NULL, is the top of the loop in the
575 insn-stream; it is used with loops that are entered near the
576 bottom. */
578 static rtx
580 rtx insn;
581 rtx start;
582 rtx end;
583 rtx loop_top;
584 {
588 {
590 /* Go to the top of the loop, and continue there. */
592 else
593 /* We're done. */
595 }
598 /* We're done. */
602 }
604 /* Optimize one loop whose start is LOOP_START and end is END.
605 LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
606 NOTE_INSN_LOOP_END.
607 LOOP_CONT is the NOTE_INSN_LOOP_CONT. */
609 /* ??? Could also move memory writes out of loops if the destination address
610 is invariant, the source is invariant, the memory write is not volatile,
611 and if we can prove that no read inside the loop can read this address
612 before the write occurs. If there is a read of this address after the
613 write, then we can also mark the memory read as invariant. */
615 static void
619 {
621 rtx p;
622 /* 1 if we are scanning insns that could be executed zero times. */
624 /* 1 if we are scanning insns that might never be executed
625 due to a subroutine call which might exit before they are reached. */
627 /* For a rotated loop that is entered near the bottom,
628 this is the label at the top. Otherwise it is zero. */
630 /* Jump insn that enters the loop, or 0 if control drops in. */
632 /* Place in the loop where control enters. */
633 rtx scan_start;
634 /* Number of insns in the loop. */
638 rtx temp;
639 /* The SET from an insn, if it is the only SET in the insn. */
641 /* Chain describing insns movable in current loop. */
643 /* Last element in `movables' -- so we can add elements at the end. */
645 /* Ratio of extra register life span we can justify
646 for saving an instruction. More if loop doesn't call subroutines
647 since in that case saving an insn makes more difference
648 and more registers are available. */
650 /* Nonzero if we are scanning instructions in a sub-loop. */
655 /* Determine whether this loop starts with a jump down to a test at
656 the end. This will occur for a small number of loops with a test
657 that is too complex to duplicate in front of the loop.
659 We search for the first insn or label in the loop, skipping NOTEs.
660 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
661 (because we might have a loop executed only once that contains a
662 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
663 (in case we have a degenerate loop).
665 Note that if we mistakenly think that a loop is entered at the top
666 when, in fact, it is entered at the exit test, the only effect will be
667 slightly poorer optimization. Making the opposite error can generate
668 incorrect code. Since very few loops now start with a jump to the
669 exit test, the code here to detect that case is very conservative. */
672 p != end
678 ;
682 /* Set up variables describing this loop. */
686 /* If loop has a jump before the first label,
687 the true entry is the target of that jump.
688 Start scan from there.
689 But record in LOOP_TOP the place where the end-test jumps
690 back to so we can scan that after the end of the loop. */
692 {
695 /* Loop entry must be unconditional jump (and not a RETURN) */
698 /* Check to see whether the jump actually
699 jumps out of the loop (meaning it's no loop).
700 This case can happen for things like
701 do {..} while (0). If this label was generated previously
702 by loop, we can't tell anything about it and have to reject
703 the loop. */
705 {
708 }
709 }
711 /* If SCAN_START was an insn created by loop, we don't know its luid
712 as required by loop_reg_used_before_p. So skip such loops. (This
713 test may never be true, but it's best to play it safe.)
715 Also, skip loops where we do not start scanning at a label. This
716 test also rejects loops starting with a JUMP_INSN that failed the
717 test above. */
721 {
726 }
728 /* Count number of times each reg is set during this loop.
729 Set VARRAY_CHAR (may_not_optimize, I) if it is not safe to move out
730 the setting of register I. Set VARRAY_RTX (reg_single_usage, I). */
732 /* Allocate extra space for REGS that might be created by
733 load_mems. We allocate a little extra slop as well, in the hopes
734 that even after the moving of movables creates some new registers
735 we won't have to reallocate these arrays. However, we do grow
736 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
747 {
750 }
752 #ifdef AVOID_CCMODE_COPIES
753 /* Don't try to move insns which set CC registers if we should not
754 create CCmode register copies. */
758 #endif
764 {
770 }
772 /* Scan through the loop finding insns that are safe to move.
773 Set set_in_loop negative for the reg being set, so that
774 this reg will be considered invariant for subsequent insns.
775 We consider whether subsequent insns use the reg
776 in deciding whether it is worth actually moving.
778 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
779 and therefore it is possible that the insns we are scanning
780 would never be executed. At such times, we must make sure
781 that it is safe to execute the insn once instead of zero times.
782 When MAYBE_NEVER is 0, all insns will be executed at least once
783 so that is not a problem. */
788 {
800 {
807 /* Figure out what to use as a source of this insn. If a REG_EQUIV
808 note is given or if a REG_EQUAL note with a constant operand is
809 specified, use it as the source and mark that we should move
810 this insn by calling emit_move_insn rather that duplicating the
811 insn.
813 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
814 is present. */
818 else
819 {
824 {
826 /* A libcall block can use regs that don't appear in
827 the equivalent expression. To move the libcall,
828 we must move those regs too. */
830 }
831 }
833 /* Don't try to optimize a register that was made
834 by loop-optimization for an inner loop.
835 We don't know its life-span, so we can't compute the benefit. */
837 ;
839 than the one where it is set (meaning that
840 something after this point in the loop might
841 depend on its value before the set). */
843 /* And the set is not guaranteed to be executed one
844 the loop starts, or the value before the set is
845 needed before the set occurs...
847 ??? Note we have quadratic behaviour here, mitigated
848 by the fact that the previous test will often fail for
849 large loops. Rather than re-scanning the entire loop
850 each time for register usage, we should build tables
851 of the register usage and use them here instead. */
852 && (maybe_never
855 /* It is unsafe to move the set.
857 This code used to consider it OK to move a set of a variable
858 which was not created by the user and not used in an exit test.
859 That behavior is incorrect and was removed. */
860 ;
866 || (tem1
867 = consec_sets_invariant_p
870 p)))
871 /* If the insn can cause a trap (such as divide by zero),
872 can't move it unless it's guaranteed to be executed
873 once loop is entered. Even a function call might
874 prevent the trap insn from being reached
875 (since it might exit!) */
878 {
882 /* A potential lossage is where we have a case where two insns
883 can be combined as long as they are both in the loop, but
884 we move one of them outside the loop. For large loops,
885 this can lose. The most common case of this is the address
886 of a function being called.
888 Therefore, if this register is marked as being used exactly
889 once if we are in a loop with calls (a "large loop"), see if
890 we can replace the usage of this register with the source
891 of this SET. If we can, delete this insn.
893 Don't do this if P has a REG_RETVAL note or if we have
894 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
905 && (! SMALL_REGISTER_CLASSES
908 /* This test is not redundant; SET_SRC (set) might be
909 a call-clobbered register and the life of REGNO
910 might span a call. */
912 VARRAY_RTX
916 VARRAY_RTX
918 {
919 /* Replace any usage in a REG_EQUAL note. Must copy the
920 new source, so that we don't get rtx sharing between the
921 SET_SOURCE and REG_NOTES of insn p. */
932 }
951 /* Set M->cond if either invariant_p or consec_sets_invariant_p
952 returned 2 (only conditionally invariant). */
963 /* Add M to the end of the chain MOVABLES. */
966 else
971 {
972 /* It is possible for the first instruction to have a
973 REG_EQUAL note but a non-invariant SET_SRC, so we must
974 remember the status of the first instruction in case
975 the last instruction doesn't have a REG_EQUAL note. */
978 /* Skip this insn, not checking REG_LIBCALL notes. */
980 /* Skip the consecutive insns, if there are any. */
982 /* Back up to the last insn of the consecutive group. */
985 /* We must now reset m->move_insn, m->is_equiv, and possibly
986 m->set_src to correspond to the effects of all the
987 insns. */
991 else
992 {
996 else
999 }
1001 }
1002 }
1003 /* If this register is always set within a STRICT_LOW_PART
1004 or set to zero, then its high bytes are constant.
1005 So clear them outside the loop and within the loop
1006 just load the low bytes.
1007 We must check that the machine has an instruction to do so.
1008 Also, if the value loaded into the register
1009 depends on the same register, this cannot be done. */
1019 {
1022 {
1036 /* If the insn may not be executed on some cycles,
1037 we can't clear the whole reg; clear just high part.
1038 Not even if the reg is used only within this loop.
1039 Consider this:
1040 while (1)
1041 while (s != t) {
1042 if (foo ()) x = *s;
1043 use (x);
1044 }
1045 Clearing x before the inner loop could clobber a value
1046 being saved from the last time around the outer loop.
1047 However, if the reg is not used outside this loop
1048 and all uses of the register are in the same
1049 basic block as the store, there is no problem.
1051 If this insn was made by loop, we don't know its
1052 INSN_LUID and hence must make a conservative
1053 assumption. */
1059 || (labels_in_range_p
1063 else
1072 /* Add M to the end of the chain MOVABLES. */
1075 else
1078 }
1079 }
1080 }
1081 /* Past a call insn, we get to insns which might not be executed
1082 because the call might exit. This matters for insns that trap.
1083 Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
1084 so they don't count. */
1087 /* Past a label or a jump, we get to insns for which we
1088 can't count on whether or how many times they will be
1089 executed during each iteration. Therefore, we can
1090 only move out sets of trivial variables
1091 (those not used after the loop). */
1092 /* Similar code appears twice in strength_reduce. */
1094 /* If we enter the loop in the middle, and scan around to the
1095 beginning, don't set maybe_never for that. This must be an
1096 unconditional jump, otherwise the code at the top of the
1097 loop might never be executed. Unconditional jumps are
1098 followed a by barrier then loop end. */
1104 {
1105 /* At the virtual top of a converted loop, insns are again known to
1106 be executed: logically, the loop begins here even though the exit
1107 code has been duplicated. */
1111 loop_depth++;
1113 loop_depth--;
1114 }
1115 }
1117 /* If one movable subsumes another, ignore that other. */
1121 /* For each movable insn, see if the reg that it loads
1122 leads when it dies right into another conditionally movable insn.
1123 If so, record that the second insn "forces" the first one,
1124 since the second can be moved only if the first is. */
1128 /* See if there are multiple movable insns that load the same value.
1129 If there are, make all but the first point at the first one
1130 through the `match' field, and add the priorities of them
1131 all together as the priority of the first. */
1135 /* Now consider each movable insn to decide whether it is worth moving.
1136 Store 0 in set_in_loop for each reg that is moved.
1138 Generally this increases code size, so do not move moveables when
1139 optimizing for code size. */
1145 /* Now candidates that still are negative are those not moved.
1146 Change set_in_loop to indicate that those are not actually invariant. */
1151 /* Now that we've moved some things out of the loop, we might be able to
1152 hoist even more memory references. */
1157 {
1162 }
1168 }
1169 \f
1170 /* Add elements to *OUTPUT to record all the pseudo-regs
1171 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1173 void
1177 {
1185 {
1203 }
1207 {
1211 {
1220 }
1221 }
1222 }
1223 \f
1224 /* Check what regs are referred to in the libcall block ending with INSN,
1225 aside from those mentioned in the equivalent value.
1226 If there are none, return 0.
1227 If there are one or more, return an EXPR_LIST containing all of them. */
1229 rtx
1232 {
1237 /* First, find all the regs used in the libcall block
1238 that are not mentioned as inputs to the result. */
1241 {
1246 }
1249 }
1250 \f
1251 /* Return 1 if all uses of REG
1252 are between INSN and the end of the basic block. */
1254 static int
1257 {
1259 rtx p;
1264 /* Search this basic block for the already recorded last use of the reg. */
1266 {
1268 {
1274 /* Ordinary insn: if this is the last use, we win. */
1280 /* Jump insn: if this is the last use, we win. */
1283 /* Otherwise, it's the end of the basic block, so we lose. */
1288 /* It's the end of the basic block, so we lose. */
1293 }
1294 }
1296 /* The "last use" doesn't follow the "first use"?? */
1298 }
1299 \f
1300 /* Compute the benefit of eliminating the insns in the block whose
1301 last insn is LAST. This may be a group of insns used to compute a
1302 value directly or can contain a library call. */
1304 static int
1306 rtx last;
1307 {
1308 rtx insn;
1313 {
1316 routine. */
1320 benefit++;
1321 }
1324 }
1325 \f
1326 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1328 static rtx
1330 rtx insn;
1332 {
1334 {
1335 rtx temp;
1337 /* If first insn of libcall sequence, skip to end. */
1338 /* Do this at start of loop, since INSN is guaranteed to
1339 be an insn here. */
1346 }
1349 }
1351 /* Ignore any movable whose insn falls within a libcall
1352 which is part of another movable.
1353 We make use of the fact that the movable for the libcall value
1354 was made later and so appears later on the chain. */
1356 static void
1359 {
1363 {
1364 /* Is this a movable for the value of a libcall? */
1367 {
1368 rtx insn;
1369 /* Check for earlier movables inside that range,
1370 and mark them invalid. We cannot use LUIDs here because
1371 insns created by loop.c for prior loops don't have LUIDs.
1372 Rather than reject all such insns from movables, we just
1373 explicitly check each insn in the libcall (since invariant
1374 libcalls aren't that common). */
1379 }
1380 }
1381 }
1383 /* For each movable insn, see if the reg that it loads
1384 leads when it dies right into another conditionally movable insn.
1385 If so, record that the second insn "forces" the first one,
1386 since the second can be moved only if the first is. */
1388 static void
1391 {
1394 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1396 {
1399 /* ??? Could this be a bug? What if CSE caused the
1400 register of M1 to be used after this insn?
1401 Since CSE does not update regno_last_uid,
1402 this insn M->insn might not be where it dies.
1403 But very likely this doesn't matter; what matters is
1404 that M's reg is computed from M1's reg. */
1409 /* If m->consec, m->set_src isn't valid. */
1413 /* Increase the priority of the moving the first insn
1414 since it permits the second to be moved as well. */
1416 {
1420 }
1421 }
1422 }
1423 \f
1424 /* Find invariant expressions that are equal and can be combined into
1425 one register. */
1427 static void
1431 {
1436 /* Regs that are set more than once are not allowed to match
1437 or be matched. I'm no longer sure why not. */
1438 /* Perhaps testing m->consec_sets would be more appropriate here? */
1442 {
1449 /* We want later insns to match the first one. Don't make the first
1450 one match any later ones. So start this loop at m->next. */
1453 /* A reg used outside the loop mustn't be eliminated. */
1455 /* A reg used for zero-extending mustn't be eliminated. */
1458 ||
1459 (
1460 /* Can combine regs with different modes loaded from the
1461 same constant only if the modes are the same or
1462 if both are integer modes with M wider or the same
1463 width as M1. The check for integer is redundant, but
1464 safe, since the only case of differing destination
1465 modes with equal sources is when both sources are
1466 VOIDmode, i.e., CONST_INT. */
1472 /* See if the source of M1 says it matches M. */
1476 movables))))
1479 {
1485 }
1486 }
1488 /* Now combine the regs used for zero-extension.
1489 This can be done for those not marked `global'
1490 provided their lives don't overlap. */
1494 {
1497 /* Combine all the registers for extension from mode MODE.
1498 Don't combine any that are used outside this loop. */
1502 {
1508 {
1509 /* First one: don't check for overlap, just record it. */
1512 }
1514 /* Make sure they extend to the same mode.
1515 (Almost always true.) */
1519 /* We already have one: check for overlap with those
1520 already combined together. */
1527 /* No overlap: we can combine this with the others. */
1533 overlap: ;
1534 }
1535 }
1536 }
1537 \f
1538 /* Return 1 if regs X and Y will become the same if moved. */
1540 static int
1544 {
1561 }
1563 /* Return 1 if X and Y are identical-looking rtx's.
1564 This is the Lisp function EQUAL for rtx arguments.
1566 If two registers are matching movables or a movable register and an
1567 equivalent constant, consider them equal. */
1569 static int
1573 {
1587 /* If we have a register and a constant, they may sometimes be
1588 equal. */
1591 {
1596 }
1599 {
1604 }
1606 /* Otherwise, rtx's of different codes cannot be equal. */
1610 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1611 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1616 /* These three types of rtx's can be compared nonrecursively. */
1625 /* Compare the elements. If any pair of corresponding elements
1626 fail to match, return 0 for the whole things. */
1630 {
1632 {
1644 /* Two vectors must have the same length. */
1648 /* And the corresponding elements must match. */
1665 /* These are just backpointers, so they don't matter. */
1671 /* It is believed that rtx's at this level will never
1672 contain anything but integers and other rtx's,
1673 except for within LABEL_REFs and SYMBOL_REFs. */
1676 }
1677 }
1679 }
1680 \f
1681 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1682 insns in INSNS which use the reference. */
1684 static void
1686 rtx x;
1687 rtx insns;
1688 {
1692 rtx insn;
1695 {
1696 /* This code used to ignore labels that referred to dispatch tables to
1697 avoid flow generating (slighly) worse code.
1699 We no longer ignore such label references (see LABEL_REF handling in
1700 mark_jump_label for additional information). */
1705 }
1709 {
1715 }
1716 }
1717 \f
1718 /* Scan MOVABLES, and move the insns that deserve to be moved.
1719 If two matching movables are combined, replace one reg with the
1720 other throughout. */
1722 static void
1727 rtx loop_start;
1728 rtx end;
1730 {
1734 /* Map of pseudo-register replacements to handle combining
1735 when we move several insns that load the same value
1736 into different pseudo-registers. */
1746 {
1747 /* Describe this movable insn. */
1750 {
1771 }
1773 /* Count movables. Value used in heuristics in strength_reduce. */
1774 num_movables++;
1776 /* Ignore the insn if it's already done (it matched something else).
1777 Otherwise, see if it is now safe to move. */
1789 {
1794 /* We have an insn that is safe to move.
1795 Compute its desirability. */
1806 /* An insn MUST be moved if we already moved something else
1807 which is safe only if this one is moved too: that is,
1808 if already_moved[REGNO] is nonzero. */
1810 /* An insn is desirable to move if the new lifetime of the
1811 register is no more than THRESHOLD times the old lifetime.
1812 If it's not desirable, it means the loop is so big
1813 that moving won't speed things up much,
1814 and it is liable to make register usage worse. */
1816 /* It is also desirable to move if it can be moved at no
1817 extra cost because something else was already moved. */
1820 || flag_move_all_movables
1825 {
1830 /* Now move the insns that set the reg. */
1833 {
1836 /* Find the end of this chain of matching regs.
1837 Thus, we load each reg in the chain from that one reg.
1838 And that reg is loaded with 0 directly,
1839 since it has ->match == 0. */
1845 /* Mark the moved, invariant reg as being allowed to
1846 share a hard reg with the other matching invariant. */
1850 regs_may_share
1853 regs_may_share));
1861 }
1862 /* If we are to re-generate the item being moved with a
1863 new move insn, first delete what we have and then emit
1864 the move insn before the loop. */
1866 {
1870 {
1871 /* If this is the first insn of a library call sequence,
1872 skip to the end. */
1877 /* If this is the last insn of a libcall sequence, then
1878 delete every insn in the sequence except the last.
1879 The last insn is handled in the normal manner. */
1882 {
1886 }
1891 /* simplify_giv_expr expects that it can walk the insns
1892 at m->insn forwards and see this old sequence we are
1893 tossing here. delete_insn does preserve the next
1894 pointers, but when we skip over a NOTE we must fix
1895 it up. Otherwise that code walks into the non-deleted
1896 insn stream. */
1899 }
1917 /* The more regs we move, the less we like moving them. */
1919 }
1920 else
1921 {
1923 {
1926 /* If first insn of libcall sequence, skip to end. */
1927 /* Do this at start of loop, since p is guaranteed to
1928 be an insn here. */
1933 /* If last insn of libcall sequence, move all
1934 insns except the last before the loop. The last
1935 insn is handled in the normal manner. */
1938 {
1946 {
1947 rtx body;
1948 rtx n;
1949 rtx next;
1956 /* Find the next insn after TEMP,
1957 not counting USE or NOTE insns. */
1965 /* If that is the call, this may be the insn
1966 that loads the function address.
1968 Extract the function address from the insn
1969 that loads it into a register.
1970 If this insn was cse'd, we get incorrect code.
1972 So emit a new move insn that copies the
1973 function address into the register that the
1974 call insn will use. flow.c will delete any
1975 redundant stores that we have created. */
1980 NULL_RTX)))
1981 {
1987 }
1988 /* We have the call insn.
1989 If it uses the register we suspect it might,
1990 load it with the correct address directly. */
1995 fn_address),
1996 fn_address_insn);
1999 {
2001 /* Because the USAGE information potentially
2002 contains objects other than hard registers
2003 we need to copy it. */
2007 }
2008 else
2016 }
2019 }
2021 {
2022 /* P sets REG to zero; but we should clear only
2023 the bits that are not covered by the mode
2024 m->savemode. */
2026 rtx sequence;
2027 rtx tem;
2030 tem = expand_binop
2043 }
2045 {
2047 /* Because the USAGE information potentially
2048 contains objects other than hard registers
2049 we need to copy it. */
2053 }
2055 {
2056 /* The SET_SRC might not be invariant, so we must
2057 use the REG_EQUAL note. */
2071 }
2072 else
2076 {
2079 /* If there is a REG_EQUAL note present whose value
2080 is not loop invariant, then delete it, since it
2081 may cause problems with later optimization passes.
2082 It is possible for cse to create such notes
2083 like this as a result of record_jump_cond. */
2088 }
2097 /* If library call, now fix the REG_NOTES that contain
2098 insn pointers, namely REG_LIBCALL on FIRST
2099 and REG_RETVAL on I1. */
2101 {
2105 }
2111 /* simplify_giv_expr expects that it can walk the insns
2112 at m->insn forwards and see this old sequence we are
2113 tossing here. delete_insn does preserve the next
2114 pointers, but when we skip over a NOTE we must fix
2115 it up. Otherwise that code walks into the non-deleted
2116 insn stream. */
2119 }
2121 /* The more regs we move, the less we like moving them. */
2123 }
2125 /* Any other movable that loads the same register
2126 MUST be moved. */
2129 /* This reg has been moved out of one loop. */
2132 /* The reg set here is now invariant. */
2138 /* Change the length-of-life info for the register
2139 to say it lives at least the full length of this loop.
2140 This will help guide optimizations in outer loops. */
2143 /* This is the old insn before all the moved insns.
2144 We can't use the moved insn because it is out of range
2145 in uid_luid. Only the old insns have luids. */
2150 /* Combine with this moved insn any other matching movables. */
2155 {
2156 rtx temp;
2158 /* Schedule the reg loaded by M1
2159 for replacement so that shares the reg of M.
2160 If the modes differ (only possible in restricted
2161 circumstances, make a SUBREG.
2163 Note this assumes that the target dependent files
2164 treat REG and SUBREG equally, including within
2165 GO_IF_LEGITIMATE_ADDRESS and in all the
2166 predicates since we never verify that replacing the
2167 original register with a SUBREG results in a
2168 recognizable insn. */
2171 else
2176 /* Get rid of the matching insn
2177 and prevent further processing of it. */
2180 /* if library call, delete all insn except last, which
2181 is deleted below */
2183 NULL_RTX)))
2184 {
2188 }
2191 /* Any other movable that loads the same register
2192 MUST be moved. */
2195 /* The reg merged here is now invariant,
2196 if the reg it matches is invariant. */
2199 }
2200 }
2203 }
2209 }
2214 /* Go through all the instructions in the loop, making
2215 all the register substitutions scheduled in REG_MAP. */
2219 {
2223 }
2224 }
2225 \f
2226 #if 0
2227 /* Scan X and replace the address of any MEM in it with ADDR.
2228 REG is the address that MEM should have before the replacement. */
2230 static void
2233 {
2242 {
2254 /* Short cut for very common case. */
2259 /* Short cut for very common case. */
2264 /* If this MEM uses a reg other than the one we expected,
2265 something is wrong. */
2273 }
2277 {
2281 {
2285 }
2286 }
2287 }
2288 #endif
2289 \f
2290 /* Return the number of memory refs to addresses that vary
2291 in the rtx X. */
2293 static int
2295 rtx x;
2296 {
2307 {
2324 }
2329 {
2333 {
2337 }
2338 }
2340 }
2342 \f
2343 #if 0
2344 /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
2345 Replace it with an instruction to load just the low bytes
2346 if the machine supports such an instruction,
2347 and insert above LOOP_START an instruction to clear the register. */
2349 static void
2352 {
2356 /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
2357 to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
2359 new
2360 = gen_rtx_SET
2362 gen_rtx_STRICT_LOW_PART
2371 {
2374 /* Clear destination register before the loop. */
2377 loop_start);
2379 /* Inside the loop, just load the low part. */
2381 }
2382 }
2383 #endif
2384 \f
2385 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2386 `has_call', `has_volatile', and `has_tablejump' within LOOP_INFO.
2387 Set the global variables `unknown_address_altered' and
2388 `num_mem_sets'. Also, fill in the array `loop_mems' and the list
2389 `loop_store_mems'. */
2391 static void
2395 {
2397 rtx insn;
2398 /* The label after END. Jumping here is just like falling off the
2399 end of the loop. We use next_nonnote_insn instead of next_label
2400 as a hedge against the (pathological) case where some actual insn
2401 might end up between the two. */
2422 {
2424 {
2426 {
2428 /* Count number of loops contained in this one. */
2430 }
2432 {
2435 {
2438 }
2439 }
2441 {
2444 }
2446 {
2447 /* If there is a NOTE_INSN_LOOP_VTOP, then this is a for
2448 or while style loop, with a loop exit test at the
2449 start. Thus, we can assume that the loop condition
2450 was true when the loop was entered. */
2453 }
2454 }
2456 {
2460 }
2462 {
2482 {
2484 {
2487 }
2488 else
2489 {
2491 }
2495 {
2497 {
2498 /* Something tricky. */
2501 }
2504 {
2505 /* A jump outside the current loop. */
2508 }
2509 }
2514 }
2515 }
2518 }
2520 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2522 !unknown_address_altered
2523 /* An exception thrown by a called function might land us
2524 anywhere. */
2526 /* We don't want loads for MEMs moved to a location before the
2527 one at which their stack memory becomes allocated. (Note
2528 that this is not a problem for malloc, etc., since those
2529 require actual function calls. */
2530 && !current_function_calls_alloca
2531 /* There are ways to leave the loop other than falling off the
2532 end. */
2537 }
2538 \f
2539 /* LOOP_NUMBER_CONT_DOMINATOR is now the last label between the loop start
2540 and the continue note that is a the destination of a (cond)jump after
2541 the continue note. If there is any (cond)jump between the loop start
2542 and what we have so far as LOOP_NUMBER_CONT_DOMINATOR that has a
2543 target between LOOP_DOMINATOR and the continue note, move
2544 LOOP_NUMBER_CONT_DOMINATOR forward to that label; if a jump's
2545 destination cannot be determined, clear LOOP_NUMBER_CONT_DOMINATOR. */
2547 static void
2550 {
2551 rtx insn;
2554 /* This can happen for an empty loop, e.g. in
2555 gcc.c-torture/compile/920410-2.c */
2558 {
2561 }
2565 {
2568 {
2572 /* If it is not a jump we can easily understand or for
2573 which we do not have jump target information in the JUMP_LABEL
2574 field (consider ADDR_VEC and ADDR_DIFF_VEC insns), then clear
2575 LOOP_NUMBER_CONT_DOMINATOR. */
2579 {
2582 }
2586 && (label_luid
2589 }
2590 }
2591 }
2593 /* Scan the function looking for loops. Record the start and end of each loop.
2594 Also mark as invalid loops any loops that contain a setjmp or are branched
2595 to from outside the loop. */
2597 static void
2599 rtx f;
2600 {
2608 /* If there are jumps to undefined labels,
2609 treat them as jumps out of any/all loops.
2610 This also avoids writing past end of tables when there are no loops. */
2613 /* Find boundaries of loops, mark which loops are contained within
2614 loops, and invalidate loops that have setjmp. */
2617 {
2620 {
2634 /* In this case, we must invalidate our current loop and any
2635 enclosing loop. */
2637 {
2643 }
2660 }
2661 /* If for any loop, this is a jump insn between the NOTE_INSN_LOOP_CONT
2662 and NOTE_INSN_LOOP_END notes, update loop_number_loop_dominator. */
2666 {
2674 do
2675 {
2676 /* First see if we care about this loop. */
2679 {
2680 /* If the jump destination is not known, invalidate
2681 loop_number_const_dominator. */
2684 else
2685 /* Check if the destination is between loop start and
2686 cont. */
2691 /* And if there is no later destination already
2692 recorded. */
2698 }
2700 }
2702 }
2704 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2705 enclosing loop, but this doesn't matter. */
2707 }
2709 /* Any loop containing a label used in an initializer must be invalidated,
2710 because it can be jumped into from anywhere. */
2713 {
2720 }
2722 /* Any loop containing a label used for an exception handler must be
2723 invalidated, because it can be jumped into from anywhere. */
2726 {
2733 }
2735 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2736 loop that it is not contained within, that loop is marked invalid.
2737 If any INSN or CALL_INSN uses a label's address, then the loop containing
2738 that label is marked invalid, because it could be jumped into from
2739 anywhere.
2741 Also look for blocks of code ending in an unconditional branch that
2742 exits the loop. If such a block is surrounded by a conditional
2743 branch around the block, move the block elsewhere (see below) and
2744 invert the jump to point to the code block. This may eliminate a
2745 label in our loop and will simplify processing by both us and a
2746 possible second cse pass. */
2750 {
2754 {
2757 {
2764 }
2765 }
2772 /* See if this is an unconditional branch outside the loop. */
2779 {
2780 rtx p;
2785 /* Go backwards until we reach the start of the loop, a label,
2786 or a JUMP_INSN. */
2793 ;
2795 /* Check for the case where we have a jump to an inner nested
2796 loop, and do not perform the optimization in that case. */
2799 {
2802 {
2807 }
2808 }
2810 /* Make sure that the target of P is within the current loop. */
2816 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2817 we have a block of code to try to move.
2819 We look backward and then forward from the target of INSN
2820 to find a BARRIER at the same loop depth as the target.
2821 If we find such a BARRIER, we make a new label for the start
2822 of the block, invert the jump in P and point it to that label,
2823 and move the block of code to the spot we found. */
2828 /* Just ignore jumps to labels that were never emitted.
2829 These always indicate compilation errors. */
2834 {
2835 rtx target
2838 rtx loc;
2852 {
2856 /* Ensure our label doesn't go away. */
2859 /* Verify that uid_loop_num is large enough and that
2860 we can invert P. */
2862 {
2865 /* If no suitable BARRIER was found, create a suitable
2866 one before TARGET. Since TARGET is a fall through
2867 path, we'll need to insert an jump around our block
2868 and a add a BARRIER before TARGET.
2870 This creates an extra unconditional jump outside
2871 the loop. However, the benefits of removing rarely
2872 executed instructions from inside the loop usually
2873 outweighs the cost of the extra unconditional jump
2874 outside the loop. */
2876 {
2877 rtx temp;
2884 }
2886 /* Include the BARRIER after INSN and copy the
2887 block after LOC. */
2891 /* All those insns are now in TARGET_LOOP_NUM. */
2896 /* The label jumped to by INSN is no longer a loop exit.
2897 Unless INSN does not have a label (e.g., it is a
2898 RETURN insn), search loop_number_exit_labels to find
2899 its label_ref, and remove it. Also turn off
2900 LABEL_OUTSIDE_LOOP_P bit. */
2902 {
2909 {
2913 else
2917 }
2924 /* If we didn't find it, then something is wrong. */
2927 }
2929 /* P is now a jump outside the loop, so it must be put
2930 in loop_number_exit_labels, and marked as such.
2931 The easiest way to do this is to just call
2932 mark_loop_jump again for P. */
2935 /* If INSN now jumps to the insn after it,
2936 delete INSN. */
2941 }
2943 /* Continue the loop after where the conditional
2944 branch used to jump, since the only branch insn
2945 in the block (if it still remains) is an inter-loop
2946 branch and hence needs no processing. */
2952 /* This loop will be continued with NEXT_INSN (insn). */
2954 }
2955 }
2956 }
2957 }
2958 }
2960 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2961 loops it is contained in, mark the target loop invalid.
2963 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2965 static void
2967 rtx x;
2969 {
2975 {
2987 /* There could be a label reference in here. */
2999 /* This may refer to a LABEL_REF or SYMBOL_REF. */
3011 /* Link together all labels that branch outside the loop. This
3012 is used by final_[bg]iv_value and the loop unrolling code. Also
3013 mark this LABEL_REF so we know that this branch should predict
3014 false. */
3016 /* A check to make sure the label is not in an inner nested loop,
3017 since this does not count as a loop exit. */
3019 {
3024 }
3025 else
3029 {
3038 }
3040 /* If this is inside a loop, but not in the current loop or one enclosed
3041 by it, it invalidates at least one loop. */
3046 /* We must invalidate every nested loop containing the target of this
3047 label, except those that also contain the jump insn. */
3050 {
3051 /* Stop when we reach a loop that also contains the jump insn. */
3057 /* If we get here, we know we need to invalidate a loop. */
3064 }
3068 /* If this is not setting pc, ignore. */
3090 /* Strictly speaking this is not a jump into the loop, only a possible
3091 jump out of the loop. However, we have no way to link the destination
3092 of this jump onto the list of exit labels. To be safe we mark this
3093 loop and any containing loops as invalid. */
3095 {
3098 {
3104 }
3105 }
3107 }
3108 }
3109 \f
3110 /* Return nonzero if there is a label in the range from
3111 insn INSN to and including the insn whose luid is END
3112 INSN must have an assigned luid (i.e., it must not have
3113 been previously created by loop.c). */
3115 static int
3117 rtx insn;
3119 {
3121 {
3125 }
3128 }
3130 /* Record that a memory reference X is being set. */
3132 static void
3134 rtx x;
3135 rtx y ATTRIBUTE_UNUSED;
3136 {
3140 /* Count number of memory writes.
3141 This affects heuristics in strength_reduce. */
3142 num_mem_sets++;
3144 /* BLKmode MEM means all memory is clobbered. */
3152 }
3153 \f
3154 /* Return nonzero if the rtx X is invariant over the current loop.
3156 The value is 2 if we refer to something only conditionally invariant.
3158 If `unknown_address_altered' is nonzero, no memory ref is invariant.
3159 Otherwise, a memory ref is invariant if it does not conflict with
3160 anything stored in `loop_store_mems'. */
3162 int
3165 {
3170 rtx mem_list_entry;
3176 {
3184 /* A LABEL_REF is normally invariant, however, if we are unrolling
3185 loops, and this label is inside the loop, then it isn't invariant.
3186 This is because each unrolled copy of the loop body will have
3187 a copy of this label. If this was invariant, then an insn loading
3188 the address of this label into a register might get moved outside
3189 the loop, and then each loop body would end up using the same label.
3191 We don't know the loop bounds here though, so just fail for all
3192 labels. */
3195 else
3204 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3205 since the reg might be set by initialization within the loop. */
3222 /* Volatile memory references must be rejected. Do this before
3223 checking for read-only items, so that volatile read-only items
3224 will be rejected also. */
3228 /* Read-only items (such as constants in a constant pool) are
3229 invariant if their address is. */
3233 /* If we had a subroutine call, any location in memory could have been
3234 clobbered. */
3238 /* See if there is any dependence between a store and this load. */
3241 {
3246 }
3248 /* It's not invalidated by a store in memory
3249 but we must still verify the address is invariant. */
3253 /* Don't mess with insns declared volatile. */
3260 }
3264 {
3266 {
3272 }
3274 {
3277 {
3283 }
3285 }
3286 }
3289 }
3291 \f
3292 /* Return nonzero if all the insns in the loop that set REG
3293 are INSN and the immediately following insns,
3294 and if each of those insns sets REG in an invariant way
3295 (not counting uses of REG in them).
3297 The value is 2 if some of these insns are only conditionally invariant.
3299 We assume that INSN itself is the first set of REG
3300 and that its source is invariant. */
3302 static int
3306 {
3309 rtx temp;
3310 /* Number of sets we have to insist on finding after INSN. */
3316 /* If N_SETS hit the limit, we can't rely on its value. */
3323 {
3325 rtx set;
3330 /* If library call, skip to end of it. */
3339 {
3344 {
3345 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3346 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3347 notes are OK. */
3353 }
3354 }
3356 count--;
3358 {
3361 }
3362 }
3365 /* If invariant_p ever returned 2, we return 2. */
3367 }
3369 #if 0
3370 /* I don't think this condition is sufficient to allow INSN
3371 to be moved, so we no longer test it. */
3373 /* Return 1 if all insns in the basic block of INSN and following INSN
3374 that set REG are invariant according to TABLE. */
3376 static int
3380 {
3385 {
3394 {
3397 }
3398 }
3399 }
3401 \f
3402 /* Look at all uses (not sets) of registers in X. For each, if it is
3403 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3404 a different insn, set USAGE[REGNO] to const0_rtx. */
3406 static void
3408 rtx insn;
3409 rtx x;
3410 varray_type usage;
3411 {
3423 {
3424 /* Don't count SET_DEST if it is a REG; otherwise count things
3425 in SET_DEST because if a register is partially modified, it won't
3426 show up as a potential movable so we don't care how USAGE is set
3427 for it. */
3431 }
3432 else
3434 {
3440 }
3441 }
3442 \f
3443 /* Count and record any set in X which is contained in INSN. Update
3444 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3446 static void
3449 varray_type may_not_move;
3451 {
3453 /* Don't move a reg that has an explicit clobber.
3454 It's not worth the pain to try to do it correctly. */
3458 {
3466 {
3468 /* If this is the first setting of this reg
3469 in current basic block, and it was set before,
3470 it must be set in two basic blocks, so it cannot
3471 be moved out of the loop. */
3475 /* If this is not first setting in current basic block,
3476 see if reg was used in between previous one and this.
3477 If so, neither one can be moved. */
3484 }
3485 }
3486 }
3488 /* Increment SET_IN_LOOP at the index of each register
3489 that is modified by an insn between FROM and TO.
3490 If the value of an element of SET_IN_LOOP becomes 127 or more,
3491 stop incrementing it, to avoid overflow.
3493 Store in SINGLE_USAGE[I] the single insn in which register I is
3494 used, if it is only used once. Otherwise, it is set to 0 (for no
3495 uses) or const0_rtx for more than one use. This parameter may be zero,
3496 in which case this processing is not done.
3498 Store in *COUNT_PTR the number of actual instruction
3499 in the loop. We use this to decide what is worth moving out. */
3501 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3502 In that case, it is the insn that last set reg n. */
3504 static void
3507 varray_type may_not_move;
3508 varray_type single_usage;
3511 {
3518 {
3520 {
3523 /* Record registers that have exactly one use. */
3526 /* Include uses in REG_EQUAL notes. */
3534 {
3539 }
3540 }
3544 }
3546 }
3547 \f
3548 /* Given a loop that is bounded by LOOP_START and LOOP_END
3549 and that is entered at SCAN_START,
3550 return 1 if the register set in SET contained in insn INSN is used by
3551 any insn that precedes INSN in cyclic order starting
3552 from the loop entry point.
3554 We don't want to use INSN_LUID here because if we restrict INSN to those
3555 that have a valid INSN_LUID, it means we cannot move an invariant out
3556 from an inner loop past two loops. */
3558 static int
3561 {
3563 rtx p;
3565 /* Scan forward checking for register usage. If we hit INSN, we
3566 are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
3568 {
3575 }
3578 }
3579 \f
3580 /* A "basic induction variable" or biv is a pseudo reg that is set
3581 (within this loop) only by incrementing or decrementing it. */
3582 /* A "general induction variable" or giv is a pseudo reg whose
3583 value is a linear function of a biv. */
3585 /* Bivs are recognized by `basic_induction_var';
3586 Givs by `general_induction_var'. */
3588 /* Indexed by register number, indicates whether or not register is an
3589 induction variable, and if so what type. */
3591 varray_type reg_iv_type;
3593 /* Indexed by register number, contains pointer to `struct induction'
3594 if register is an induction variable. This holds general info for
3595 all induction variables. */
3597 varray_type reg_iv_info;
3599 /* Indexed by register number, contains pointer to `struct iv_class'
3600 if register is a basic induction variable. This holds info describing
3601 the class (a related group) of induction variables that the biv belongs
3602 to. */
3606 /* The head of a list which links together (via the next field)
3607 every iv class for the current loop. */
3611 /* Givs made from biv increments are always splittable for loop unrolling.
3612 Since there is no regscan info for them, we have to keep track of them
3613 separately. */
3616 /* Communication with routines called via `note_stores'. */
3620 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3624 /* ??? Unfinished optimizations, and possible future optimizations,
3625 for the strength reduction code. */
3627 /* ??? The interaction of biv elimination, and recognition of 'constant'
3628 bivs, may cause problems. */
3630 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3631 performance problems.
3633 Perhaps don't eliminate things that can be combined with an addressing
3634 mode. Find all givs that have the same biv, mult_val, and add_val;
3635 then for each giv, check to see if its only use dies in a following
3636 memory address. If so, generate a new memory address and check to see
3637 if it is valid. If it is valid, then store the modified memory address,
3638 otherwise, mark the giv as not done so that it will get its own iv. */
3640 /* ??? Could try to optimize branches when it is known that a biv is always
3641 positive. */
3643 /* ??? When replace a biv in a compare insn, we should replace with closest
3644 giv so that an optimized branch can still be recognized by the combiner,
3645 e.g. the VAX acb insn. */
3647 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3648 was rerun in loop_optimize whenever a register was added or moved.
3649 Also, some of the optimizations could be a little less conservative. */
3650 \f
3651 /* Perform strength reduction and induction variable elimination.
3653 Pseudo registers created during this function will be beyond the last
3654 valid index in several tables including n_times_set and regno_last_uid.
3655 This does not cause a problem here, because the added registers cannot be
3656 givs outside of their loop, and hence will never be reconsidered.
3657 But scan_loop must check regnos to make sure they are in bounds.
3659 SCAN_START is the first instruction in the loop, as the loop would
3660 actually be executed. END is the NOTE_INSN_LOOP_END. LOOP_TOP is
3661 the first instruction in the loop, as it is layed out in the
3662 instruction stream. LOOP_START is the NOTE_INSN_LOOP_BEG.
3663 LOOP_CONT is the NOTE_INSN_LOOP_CONT. */
3665 static void
3668 rtx scan_start;
3669 rtx end;
3670 rtx loop_top;
3672 rtx loop_start;
3673 rtx loop_end;
3675 rtx loop_cont;
3677 {
3678 rtx p;
3679 rtx set;
3680 rtx inc_val;
3681 rtx mult_val;
3682 rtx dest_reg;
3684 /* This is 1 if current insn is not executed at least once for every loop
3685 iteration. */
3687 /* This is 1 if current insn may be executed more than once for every
3688 loop iteration. */
3690 /* This is 1 if we have past a branch back to the top of the loop
3691 (aka a loop latch). */
3693 /* Temporary list pointers for traversing loop_iv_list. */
3695 /* Ratio of extra register life span we can justify
3696 for saving an instruction. More if loop doesn't call subroutines
3697 since in that case saving an insn makes more difference
3698 and more registers are available. */
3699 /* ??? could set this to last value of threshold in move_movables */
3701 /* Map of pseudo-register replacements. */
3705 rtx test;
3706 rtx end_insert_before;
3711 /* If scan_start points to the loop exit test, we have to be wary of
3712 subversive use of gotos inside expression statements. */
3726 /* Save insn immediately after the loop_end. Insns inserted after loop_end
3727 must be put before this insn, so that they will appear in the right
3728 order (i.e. loop order).
3730 If loop_end is the end of the current function, then emit a
3731 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
3732 dummy note insn. */
3735 else
3738 /* Scan through loop to find all possible bivs. */
3743 {
3747 {
3752 {
3756 {
3757 /* It is a possible basic induction variable.
3758 Create and initialize an induction structure for it. */
3766 }
3769 }
3770 }
3772 /* Past CODE_LABEL, we get to insns that may be executed multiple
3773 times. The only way we can be sure that they can't is if every
3774 jump insn between here and the end of the loop either
3775 returns, exits the loop, is a jump to a location that is still
3776 behind the label, or is a jump to the loop start. */
3779 {
3785 {
3790 {
3793 else
3797 }
3805 {
3808 }
3809 }
3810 }
3812 /* Past a jump, we get to insns for which we can't count
3813 on whether they will be executed during each iteration. */
3814 /* This code appears twice in strength_reduce. There is also similar
3815 code in scan_loop. */
3817 /* If we enter the loop in the middle, and scan around to the
3818 beginning, don't set not_every_iteration for that.
3819 This can be any kind of jump, since we want to know if insns
3820 will be executed if the loop is executed. */
3824 {
3827 /* If this is a jump outside the loop, then it also doesn't
3828 matter. Check to see if the target of this branch is on the
3829 loop_number_exits_labels list. */
3832 label;
3839 }
3842 {
3843 /* At the virtual top of a converted loop, insns are again known to
3844 be executed each iteration: logically, the loop begins here
3845 even though the exit code has been duplicated.
3847 Insns are also again known to be executed each iteration at
3848 the LOOP_CONT note. */
3854 loop_depth++;
3856 loop_depth--;
3857 }
3859 /* Note if we pass a loop latch. If we do, then we can not clear
3860 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3861 a loop since a jump before the last CODE_LABEL may have started
3862 a new loop iteration.
3864 Note that LOOP_TOP is only set for rotated loops and we need
3865 this check for all loops, so compare against the CODE_LABEL
3866 which immediately follows LOOP_START. */
3870 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3871 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3872 or not an insn is known to be executed each iteration of the
3873 loop, whether or not any iterations are known to occur.
3875 Therefore, if we have just passed a label and have no more labels
3876 between here and the test insn of the loop, and we have not passed
3877 a jump to the top of the loop, then we know these insns will be
3878 executed each iteration. */
3881 && ! past_loop_latch
3886 }
3888 /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3889 Make a sanity check against n_times_set. */
3891 {
3893 /* Above happens if register modified by subreg, etc. */
3894 /* Make sure it is not recognized as a basic induction var: */
3896 /* If never incremented, it is invariant that we decided not to
3897 move. So leave it alone. */
3899 {
3910 }
3911 else
3912 {
3917 }
3918 }
3920 /* Exit if there are no bivs. */
3922 {
3923 /* Can still unroll the loop anyways, but indicate that there is no
3924 strength reduction info available. */
3930 }
3932 /* Find initial value for each biv by searching backwards from loop_start,
3933 halting at first label. Also record any test condition. */
3937 {
3947 /* Record any test of a biv that branches around the loop if no store
3948 between it and the start of loop. We only care about tests with
3949 constants and registers and only certain of those. */
3959 {
3960 /* If an NE test, we have an initial value! */
3962 {
3966 }
3967 else
3969 }
3970 }
3972 /* Look at the each biv and see if we can say anything better about its
3973 initial value from any initializing insns set up above. (This is done
3974 in two passes to avoid missing SETs in a PARALLEL.) */
3976 {
3977 rtx src;
3978 rtx note;
3983 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3984 is a constant, use the value of that. */
3990 else
4001 {
4005 {
4007 {
4010 }
4011 else
4012 {
4015 }
4016 }
4017 }
4018 else
4019 {
4023 /* Biv initial value is not a simple move. If it is the sum of
4024 another biv and a constant, check if both bivs are incremented
4025 in lockstep. Then we are actually looking at a giv.
4026 For simplicity, we only handle the case where there is but a
4027 single increment, and the register is not used elsewhere. */
4036 {
4042 }
4044 /* Now, can we transform this biv into a giv? */
4049 /* init_insn is only set to insns that are before loop_start
4050 without any intervening labels. */
4053 /* The register from BL2 must be set before the register from
4054 BL is set, or we must be able to move the latter set after
4055 the former set. Currently there can't be any labels
4056 in-between when biv_toal_increment returns nonzero both times
4057 but we test it here in case some day some real cfg analysis
4058 gets used to set always_computable. */
4067 {
4076 /* Let this giv be discovered by the generic code. */
4079 /* We can get better optimization if we can move the giv setting
4080 before the first giv use. */
4084 dominator)
4087 {
4088 rtx p;
4089 rtx next;
4092 {
4098 #ifdef HAVE_cc0
4101 #endif
4103 }
4107 /* Avoid problems with luids by actually moving the insn
4108 and adjusting all luids in the range. */
4113 /* If the only purpose of the init insn is to initialize
4114 this giv, delete it. */
4118 }
4120 {
4127 }
4128 /* Remove this biv from the chain. */
4130 {
4131 /* We move the following giv from *bl->next into *bl.
4132 We have to update reg_biv_class for that moved biv
4133 to point to its new address. */
4136 }
4137 else
4138 {
4141 }
4142 }
4144 /* If we can't make it a giv,
4145 let biv keep initial value of "itself". */
4148 }
4149 }
4151 /* If a biv is unconditionally incremented several times in a row, convert
4152 all but the last increment into a giv. */
4154 /* Get an upper bound for the number of registers
4155 we might have after all bivs have been processed. */
4160 /* If the loop contains volatile memory references do not allow any
4161 replacements to take place, since this could loose the volatile markers. */
4163 {
4166 /* Reallocate reg_iv_type and reg_iv_info. */
4171 {
4175 /* The biv increments lists are in reverse order. Fix this first. */
4177 {
4181 }
4183 /* We must guard against the case that an early exit between v->insn
4184 and next->insn leaves the biv live after the loop, since that
4185 would mean that we'd be missing an increment for the final
4186 value. The following test to set biv_dead_after_loop is like
4187 the first part of the test to set bl->eliminable.
4188 We don't check here if we can calculate the final value, since
4189 this can't succeed if we already know that there is a jump
4190 between v->insn and next->insn, yet next->always_executed is
4191 set and next->maybe_multiple is cleared. Such a combination
4192 implies that the jump destination is outside the loop.
4193 If we want to make this check more sophisticated, we should
4194 check each branch between v->insn and next->insn individually
4195 to see if the biv is dead at its destination. */
4202 #ifdef HAVE_decrement_and_branch_until_zero
4204 #endif
4209 {
4210 HOST_WIDE_INT offset;
4222 || ! (biv_dead_after_loop
4224 {
4227 }
4234 /* Unlike reg_iv_type / reg_iv_info, the other three arrays
4235 have been allocated with some slop space, so we may not
4236 actually need to reallocate them. If we do, the following
4237 if statement will be executed just once in this loop. */
4239 {
4240 /* Grow all the remaining arrays. */
4245 }
4248 {
4251 }
4253 /* Here we can try to eliminate the increment by combining
4254 it into the uses. */
4256 /* Set last_use_insn so that we can check against it. */
4261 {
4265 {
4267 }
4268 }
4270 /* If we can't get the LUIDs for the insns, we can't
4271 calculate the lifetime. This is likely from unrolling
4272 of an inner loop, so there is little point in making this
4273 a DEST_REG giv anyways. */
4277 {
4278 /* Change the increment at NEXT back to what it was. */
4284 }
4318 /* If next_insn has a REG_EQUAL note that mentiones OLD_REG,
4319 it must be replaced. */
4324 /* Remove the increment from the list of biv increments,
4325 and record it as a giv. */
4334 /* Now replace the biv with DEST_REG in all insns between
4335 the replaced increment and the next increment, and
4336 remember the last insn that needed a replacement. */
4340 {
4341 rtx note;
4346 {
4350 }
4352 {
4356 }
4357 }
4361 /* If the lifetime is zero, it means that this register is really
4362 a dead store. So mark this as a giv that can be ignored.
4363 This will not prevent the biv from being eliminated. */
4371 }
4372 }
4373 }
4376 /* Search the loop for general induction variables. */
4378 /* A register is a giv if: it is only set once, it is a function of a
4379 biv and a constant (or invariant), and it is not a biv. */
4386 {
4388 /* At end of a straight-in loop, we are done.
4389 At end of a loop entered at the bottom, scan the top. */
4393 {
4396 else
4400 }
4402 /* Look for a general induction variable in a register. */
4407 {
4408 rtx src_reg;
4409 rtx add_val;
4410 rtx mult_val;
4413 rtx last_consec_insn;
4422 /* Equivalent expression is a giv. */
4427 /* Don't try to handle any regs made by loop optimization.
4428 We have nothing on them in regno_first_uid, etc. */
4430 /* Don't recognize a BASIC_INDUCT_VAR here. */
4432 /* This must be the only place where the register is set. */
4434 /* or all sets must be consecutive and make a giv. */
4439 {
4443 /* If this is a library call, increase benefit. */
4447 /* Skip the consecutive insns, if there are any. */
4455 }
4456 }
4458 #ifndef DONT_REDUCE_ADDR
4459 /* Look for givs which are memory addresses. */
4460 /* This resulted in worse code on a VAX 8600. I wonder if it
4461 still does. */
4465 #endif
4467 /* Update the status of whether giv can derive other givs. This can
4468 change when we pass a label or an insn that updates a biv. */
4473 /* Past CODE_LABEL, we get to insns that may be executed multiple
4474 times. The only way we can be sure that they can't is if every
4475 every jump insn between here and the end of the loop either
4476 returns, exits the loop, is a forward jump, or is a jump
4477 to the loop start. */
4480 {
4486 {
4491 {
4494 else
4498 }
4509 {
4512 }
4513 }
4514 }
4516 /* Past a jump, we get to insns for which we can't count
4517 on whether they will be executed during each iteration. */
4518 /* This code appears twice in strength_reduce. There is also similar
4519 code in scan_loop. */
4521 /* If we enter the loop in the middle, and scan around to the
4522 beginning, don't set not_every_iteration for that.
4523 This can be any kind of jump, since we want to know if insns
4524 will be executed if the loop is executed. */
4528 {
4531 /* If this is a jump outside the loop, then it also doesn't
4532 matter. Check to see if the target of this branch is on the
4533 loop_number_exits_labels list. */
4536 label;
4543 }
4546 {
4547 /* At the virtual top of a converted loop, insns are again known to
4548 be executed each iteration: logically, the loop begins here
4549 even though the exit code has been duplicated.
4551 Insns are also again known to be executed each iteration at
4552 the LOOP_CONT note. */
4558 loop_depth++;
4560 loop_depth--;
4561 }
4563 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
4564 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
4565 or not an insn is known to be executed each iteration of the
4566 loop, whether or not any iterations are known to occur.
4568 Therefore, if we have just passed a label and have no more labels
4569 between here and the test insn of the loop, we know these insns
4570 will be executed each iteration. */
4576 }
4578 /* Try to calculate and save the number of loop iterations. This is
4579 set to zero if the actual number can not be calculated. This must
4580 be called after all giv's have been identified, since otherwise it may
4581 fail if the iteration variable is a giv. */
4585 /* Now for each giv for which we still don't know whether or not it is
4586 replaceable, check to see if it is replaceable because its final value
4587 can be calculated. This must be done after loop_iterations is called,
4588 so that final_giv_value will work correctly. */
4591 {
4597 }
4599 /* Try to prove that the loop counter variable (if any) is always
4600 nonnegative; if so, record that fact with a REG_NONNEG note
4601 so that "decrement and branch until zero" insn can be used. */
4604 /* Create reg_map to hold substitutions for replaceable giv regs.
4605 Some givs might have been made from biv increments, so look at
4606 reg_iv_type for a suitable size. */
4611 /* Examine each iv class for feasibility of strength reduction/induction
4612 variable elimination. */
4615 {
4622 /* Test whether it will be possible to eliminate this biv
4623 provided all givs are reduced. This is possible if either
4624 the reg is not used outside the loop, or we can compute
4625 what its final value will be.
4627 For architectures with a decrement_and_branch_until_zero insn,
4628 don't do this if we put a REG_NONNEG note on the endtest for
4629 this biv. */
4631 /* Compare against bl->init_insn rather than loop_start.
4632 We aren't concerned with any uses of the biv between
4633 init_insn and loop_start since these won't be affected
4634 by the value of the biv elsewhere in the function, so
4635 long as init_insn doesn't use the biv itself.
4636 March 14, 1989 -- self@bayes.arc.nasa.gov */
4642 #ifdef HAVE_decrement_and_branch_until_zero
4644 #endif
4648 #ifdef HAVE_decrement_and_branch_until_zero
4650 #endif
4651 ))
4654 else
4655 {
4657 {
4665 }
4666 }
4668 /* Combine all giv's for this iv_class. */
4671 /* This will be true at the end, if all givs which depend on this
4672 biv have been strength reduced.
4673 We can't (currently) eliminate the biv unless this is so. */
4676 /* Check each giv in this class to see if we will benefit by reducing
4677 it. Skip giv's combined with others. */
4679 {
4687 /* Reduce benefit if not replaceable, since we will insert
4688 a move-insn to replace the insn that calculates this giv.
4689 Don't do this unless the giv is a user variable, since it
4690 will often be marked non-replaceable because of the duplication
4691 of the exit code outside the loop. In such a case, the copies
4692 we insert are dead and will be deleted. So they don't have
4693 a cost. Similar situations exist. */
4694 /* ??? The new final_[bg]iv_value code does a much better job
4695 of finding replaceable giv's, and hence this code may no longer
4696 be necessary. */
4701 /* Decrease the benefit to count the add-insns that we will
4702 insert to increment the reduced reg for the giv. */
4705 /* Decide whether to strength-reduce this giv or to leave the code
4706 unchanged (recompute it from the biv each time it is used).
4707 This decision can be made independently for each giv. */
4709 #ifdef AUTO_INC_DEC
4710 /* Attempt to guess whether autoincrement will handle some of the
4711 new add insns; if so, increase BENEFIT (undo the subtraction of
4712 add_cost that was done above). */
4715 {
4728 }
4729 #endif
4731 /* If an insn is not to be strength reduced, then set its ignore
4732 flag, and clear all_reduced. */
4734 /* A giv that depends on a reversed biv must be reduced if it is
4735 used after the loop exit, otherwise, it would have the wrong
4736 value after the loop exit. To make it simple, just reduce all
4737 of such giv's whether or not we know they are used after the loop
4738 exit. */
4742 {
4750 }
4751 else
4752 {
4753 /* Check that we can increment the reduced giv without a
4754 multiply insn. If not, reject it. */
4759 {
4767 }
4768 }
4769 }
4771 /* Check for givs whose first use is their definition and whose
4772 last use is the definition of another giv. If so, it is likely
4773 dead and should not be used to derive another giv nor to
4774 eliminate a biv. */
4776 {
4782 {
4788 }
4791 {
4797 }
4798 }
4800 /* Now that we know which givs will be reduced, try to rearrange the
4801 combinations to reduce register pressure.
4802 recombine_givs calls find_life_end, which needs reg_iv_type and
4803 reg_iv_info to be valid for all pseudos. We do the necessary
4804 reallocation here since it allows to check if there are still
4805 more bivs to process. */
4808 {
4809 /* If there are still more bivs to process, allocate some slack
4810 space so that we're not constantly reallocating these arrays. */
4813 /* Reallocate reg_iv_type and reg_iv_info. */
4816 }
4819 /* Reduce each giv that we decided to reduce. */
4822 {
4825 {
4828 /* If the code for derived givs immediately below has already
4829 allocated a new_reg, we must keep it. */
4834 {
4837 /* In case d->dest_reg is not replaceable, we have
4838 to replace it in v->insn now. */
4845 /* For each place where the biv is incremented, add an
4846 insn to set the new, reduced reg for the giv.
4847 We used to do this only for biv_count != 1, but
4848 this fails when there is a giv after a single biv
4849 increment, e.g. when the last giv was expressed as
4850 pre-decrement. */
4852 {
4853 /* We always emit reduced giv increments before the
4854 biv increment when bl->biv_count != 1. So by
4855 emitting the add insns for derived givs after the
4856 biv increment, they pick up the updated value of
4857 the reduced giv.
4858 If the reduced giv is processed with
4859 auto_inc_opt == 1, then it is incremented earlier
4860 than the biv, hence we'll still pick up the right
4861 value.
4862 If it's processed with auto_inc_opt == -1,
4863 that implies that the biv increment is before the
4864 first reduced giv's use. The derived giv's lifetime
4865 is after the reduced giv's lifetime, hence in this
4866 case, the biv increment doesn't matter. */
4868 }
4870 }
4872 #ifdef AUTO_INC_DEC
4873 /* If the target has auto-increment addressing modes, and
4874 this is an address giv, then try to put the increment
4875 immediately after its use, so that flow can create an
4876 auto-increment addressing mode. */
4879 /* We don't handle reversed biv's because bl->biv->insn
4880 does not have a valid INSN_LUID. */
4884 {
4885 /* If other giv's have been combined with this one, then
4886 this will work only if all uses of the other giv's occur
4887 before this giv's insn. This is difficult to check.
4889 We simplify this by looking for the common case where
4890 there is one DEST_REG giv, and this giv's insn is the
4891 last use of the dest_reg of that DEST_REG giv. If the
4892 increment occurs after the address giv, then we can
4893 perform the optimization. (Otherwise, the increment
4894 would have to go before other_giv, and we would not be
4895 able to combine it with the address giv to get an
4896 auto-inc address.) */
4898 {
4903 {
4906 else
4908 }
4915 }
4916 /* Check for case where increment is before the address
4917 giv. Do this test in "loop order". */
4926 else
4929 #ifdef HAVE_cc0
4930 {
4931 rtx prev;
4933 /* We can't put an insn immediately after one setting
4934 cc0, or immediately before one using cc0. */
4941 }
4942 #endif
4946 }
4947 #endif
4949 /* For each place where the biv is incremented, add an insn
4950 to increment the new, reduced reg for the giv. */
4952 {
4953 rtx insert_before;
4959 else
4966 /* A multiply is acceptable here
4967 since this is presumed to be seldom executed. */
4970 }
4972 /* Add code at loop start to initialize giv's reduced reg. */
4976 }
4977 }
4979 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4980 as not reduced.
4982 For each giv register that can be reduced now: if replaceable,
4983 substitute reduced reg wherever the old giv occurs;
4984 else add new move insn "giv_reg = reduced_reg". */
4987 {
4994 /* Update expression if this was combined, in case other giv was
4995 replaced. */
5001 /* Store reduced reg as the address in the memref where we found
5002 this giv. */
5005 {
5008 #if 0
5009 /* I can no longer duplicate the original problem. Perhaps
5010 this is unnecessary now? */
5012 /* Replaceable; it isn't strictly necessary to delete the old
5013 insn and emit a new one, because v->dest_reg is now dead.
5015 However, especially when unrolling loops, the special
5016 handling for (set REG0 REG1) in the second cse pass may
5017 make v->dest_reg live again. To avoid this problem, emit
5018 an insn to set the original giv reg from the reduced giv.
5019 We can not delete the original insn, since it may be part
5020 of a LIBCALL, and the code in flow that eliminates dead
5021 libcalls will fail if it is deleted. */
5024 #endif
5025 }
5026 else
5027 {
5028 /* Not replaceable; emit an insn to set the original giv reg from
5029 the reduced giv, same as above. */
5032 }
5034 /* When a loop is reversed, givs which depend on the reversed
5035 biv, and which are live outside the loop, must be set to their
5036 correct final value. This insn is only needed if the giv is
5037 not replaceable. The correct final value is the same as the
5038 value that the giv starts the reversed loop with. */
5043 {
5044 rtx insert_before;
5046 /* If the loop has multiple exits, emit the insn before the
5047 loop to ensure that it will always be executed no matter
5048 how the loop exits. Otherwise, emit the insn after the loop,
5049 since this is slightly more efficient. */
5052 else
5055 insert_before);
5057 #if 0
5058 /* If the insn to set the final value of the giv was emitted
5059 before the loop, then we must delete the insn inside the loop
5060 that sets it. If this is a LIBCALL, then we must delete
5061 every insn in the libcall. Note, however, that
5062 final_giv_value will only succeed when there are multiple
5063 exits if the giv is dead at each exit, hence it does not
5064 matter that the original insn remains because it is dead
5065 anyways. */
5066 /* Delete the insn inside the loop that sets the giv since
5067 the giv is now set before (or after) the loop. */
5069 #endif
5070 }
5073 {
5078 }
5079 }
5081 /* All the givs based on the biv bl have been reduced if they
5082 merit it. */
5084 /* For each giv not marked as maybe dead that has been combined with a
5085 second giv, clear any "maybe dead" mark on that second giv.
5086 v->new_reg will either be or refer to the register of the giv it
5087 combined with.
5089 Doing this clearing avoids problems in biv elimination where a
5090 giv's new_reg is a complex value that can't be put in the insn but
5091 the giv combined with (with a reg as new_reg) is marked maybe_dead.
5092 Since the register will be used in either case, we'd prefer it be
5093 used from the simpler giv. */
5099 /* Try to eliminate the biv, if it is a candidate.
5100 This won't work if ! all_reduced,
5101 since the givs we planned to use might not have been reduced.
5103 We have to be careful that we didn't initially think we could eliminate
5104 this biv because of a giv that we now think may be dead and shouldn't
5105 be used as a biv replacement.
5107 Also, there is the possibility that we may have a giv that looks
5108 like it can be used to eliminate a biv, but the resulting insn
5109 isn't valid. This can happen, for example, on the 88k, where a
5110 JUMP_INSN can compare a register only with zero. Attempts to
5111 replace it with a compare with a constant will fail.
5113 Note that in cases where this call fails, we may have replaced some
5114 of the occurrences of the biv with a giv, but no harm was done in
5115 doing so in the rare cases where it can occur. */
5121 {
5122 /* ?? If we created a new test to bypass the loop entirely,
5123 or otherwise drop straight in, based on this test, then
5124 we might want to rewrite it also. This way some later
5125 pass has more hope of removing the initialization of this
5126 biv entirely. */
5128 /* If final_value != 0, then the biv may be used after loop end
5129 and we must emit an insn to set it just in case.
5131 Reversed bivs already have an insn after the loop setting their
5132 value, so we don't need another one. We can't calculate the
5133 proper final value for such a biv here anyways. */
5135 {
5136 rtx insert_before;
5138 /* If the loop has multiple exits, emit the insn before the
5139 loop to ensure that it will always be executed no matter
5140 how the loop exits. Otherwise, emit the insn after the
5141 loop, since this is slightly more efficient. */
5144 else
5148 end_insert_before);
5149 }
5151 #if 0
5152 /* Delete all of the instructions inside the loop which set
5153 the biv, as they are all dead. If is safe to delete them,
5154 because an insn setting a biv will never be part of a libcall. */
5155 /* However, deleting them will invalidate the regno_last_uid info,
5156 so keeping them around is more convenient. Final_biv_value
5157 will only succeed when there are multiple exits if the biv
5158 is dead at each exit, hence it does not matter that the original
5159 insn remains, because it is dead anyways. */
5162 #endif
5167 }
5168 }
5170 /* Go through all the instructions in the loop, making all the
5171 register substitutions scheduled in REG_MAP. */
5176 {
5180 }
5183 {
5184 /* When we completely unroll a loop we will likely not need the increment
5185 of the loop BIV and we will not need the conditional branch at the
5186 end of the loop. */
5189 #ifdef HAVE_cc0
5190 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
5191 need the comparison before the conditional branch at the end of the
5192 loop. */
5194 #endif
5196 /* We'll need one copy for each loop iteration. */
5199 /* A little slop to account for the ability to remove initialization
5200 code, better CSE, and other secondary benefits of completely
5201 unrolling some loops. */
5204 /* Clamp the value. */
5207 }
5209 /* Unroll loops from within strength reduction so that we can use the
5210 induction variable information that strength_reduce has already
5211 collected. Always unroll loops that would be as small or smaller
5212 unrolled than when rolled. */
5219 #ifdef HAVE_decrement_and_branch_on_count
5220 /* Instrument the loop with BCT insn. */
5229 egress:
5232 }
5233 \f
5234 /* Return 1 if X is a valid source for an initial value (or as value being
5235 compared against in an initial test).
5237 X must be either a register or constant and must not be clobbered between
5238 the current insn and the start of the loop.
5240 INSN is the insn containing X. */
5242 static int
5244 rtx x;
5245 rtx insn;
5247 rtx loop_start;
5248 {
5252 /* Only consider pseudos we know about initialized in insns whose luids
5253 we know. */
5258 /* Don't use call-clobbered registers across a call which clobbers it. On
5259 some machines, don't use any hard registers at all. */
5261 && (SMALL_REGISTER_CLASSES
5265 /* Don't use registers that have been clobbered before the start of the
5266 loop. */
5271 }
5272 \f
5273 /* Scan X for memory refs and check each memory address
5274 as a possible giv. INSN is the insn whose pattern X comes from.
5275 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
5276 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
5277 more thanonce in each loop iteration. */
5279 static void
5281 loop_end)
5282 rtx x;
5283 rtx insn;
5286 {
5296 {
5312 {
5313 rtx src_reg;
5314 rtx add_val;
5315 rtx mult_val;
5318 /* This code used to disable creating GIVs with mult_val == 1 and
5319 add_val == 0. However, this leads to lost optimizations when
5320 it comes time to combine a set of related DEST_ADDR GIVs, since
5321 this one would not be seen. */
5325 {
5326 /* Found one; record it. */
5335 }
5336 }
5341 }
5343 /* Recursively scan the subexpressions for other mem refs. */
5354 }
5355 \f
5356 /* Fill in the data about one biv update.
5357 V is the `struct induction' in which we record the biv. (It is
5358 allocated by the caller, with alloca.)
5359 INSN is the insn that sets it.
5360 DEST_REG is the biv's reg.
5362 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
5363 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
5364 being set to INC_VAL.
5366 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
5367 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
5368 can be executed more than once per iteration. If MAYBE_MULTIPLE
5369 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
5370 executed exactly once per iteration. */
5372 static void
5376 rtx insn;
5377 rtx dest_reg;
5378 rtx inc_val;
5379 rtx mult_val;
5383 {
5397 /* Add this to the reg's iv_class, creating a class
5398 if this is the first incrementation of the reg. */
5402 {
5403 /* Create and initialize new iv_class. */
5413 /* Set initial value to the reg itself. */
5415 /* We haven't seen the initializing insn yet */
5425 /* Add this class to loop_iv_list. */
5429 /* Put it in the array of biv register classes. */
5431 }
5433 /* Update IV_CLASS entry for this biv. */
5441 {
5446 {
5450 }
5451 else
5452 {
5456 }
5457 }
5458 }
5459 \f
5460 /* Fill in the data about one giv.
5461 V is the `struct induction' in which we record the giv. (It is
5462 allocated by the caller, with alloca.)
5463 INSN is the insn that sets it.
5464 BENEFIT estimates the savings from deleting this insn.
5465 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
5466 into a register or is used as a memory address.
5468 SRC_REG is the biv reg which the giv is computed from.
5469 DEST_REG is the giv's reg (if the giv is stored in a reg).
5470 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
5471 LOCATION points to the place where this giv's value appears in INSN. */
5473 static void
5476 loop_end)
5478 rtx insn;
5479 rtx src_reg;
5480 rtx dest_reg;
5487 {
5516 /* The v->always_computable field is used in update_giv_derive, to
5517 determine whether a giv can be used to derive another giv. For a
5518 DEST_REG giv, INSN computes a new value for the giv, so its value
5519 isn't computable if INSN insn't executed every iteration.
5520 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5521 it does not compute a new value. Hence the value is always computable
5522 regardless of whether INSN is executed each iteration. */
5526 else
5532 {
5535 }
5537 {
5543 /* If the lifetime is zero, it means that this register is
5544 really a dead store. So mark this as a giv that can be
5545 ignored. This will not prevent the biv from being eliminated. */
5551 }
5553 /* Add the giv to the class of givs computed from one biv. */
5557 {
5560 /* Don't count DEST_ADDR. This is supposed to count the number of
5561 insns that calculate givs. */
5565 }
5566 else
5567 /* Fatal error, biv missing for this giv? */
5572 else
5573 {
5574 /* The giv can be replaced outright by the reduced register only if all
5575 of the following conditions are true:
5576 - the insn that sets the giv is always executed on any iteration
5577 on which the giv is used at all
5578 (there are two ways to deduce this:
5579 either the insn is executed on every iteration,
5580 or all uses follow that insn in the same basic block),
5581 - the giv is not used outside the loop
5582 - no assignments to the biv occur during the giv's lifetime. */
5585 /* Previous line always fails if INSN was moved by loop opt. */
5587 && (! not_every_iteration
5589 {
5590 /* Now check that there are no assignments to the biv within the
5591 giv's lifetime. This requires two separate checks. */
5593 /* Check each biv update, and fail if any are between the first
5594 and last use of the giv.
5596 If this loop contains an inner loop that was unrolled, then
5597 the insn modifying the biv may have been emitted by the loop
5598 unrolling code, and hence does not have a valid luid. Just
5599 mark the biv as not replaceable in this case. It is not very
5600 useful as a biv, because it is used in two different loops.
5601 It is very unlikely that we would be able to optimize the giv
5602 using this biv anyways. */
5606 {
5612 {
5616 }
5617 }
5619 /* If there are any backwards branches that go from after the
5620 biv update to before it, then this giv is not replaceable. */
5624 {
5628 }
5629 }
5630 else
5631 {
5632 /* May still be replaceable, we don't have enough info here to
5633 decide. */
5636 }
5637 }
5639 /* Record whether the add_val contains a const_int, for later use by
5640 combine_givs. */
5641 {
5646 ;
5650 {
5652 {
5657 else
5659 }
5662 }
5663 }
5666 {
5670 else
5686 {
5689 }
5690 else
5691 {
5694 }
5697 {
5700 }
5701 else
5702 {
5705 }
5706 }
5711 }
5714 /* All this does is determine whether a giv can be made replaceable because
5715 its final value can be calculated. This code can not be part of record_giv
5716 above, because final_giv_value requires that the number of loop iterations
5717 be known, and that can not be accurately calculated until after all givs
5718 have been identified. */
5720 static void
5725 {
5731 /* DEST_ADDR givs will never reach here, because they are always marked
5732 replaceable above in record_giv. */
5734 /* The giv can be replaced outright by the reduced register only if all
5735 of the following conditions are true:
5736 - the insn that sets the giv is always executed on any iteration
5737 on which the giv is used at all
5738 (there are two ways to deduce this:
5739 either the insn is executed on every iteration,
5740 or all uses follow that insn in the same basic block),
5741 - its final value can be calculated (this condition is different
5742 than the one above in record_giv)
5743 - no assignments to the biv occur during the giv's lifetime. */
5745 #if 0
5746 /* This is only called now when replaceable is known to be false. */
5747 /* Clear replaceable, so that it won't confuse final_giv_value. */
5749 #endif
5753 {
5756 rtx last_giv_use;
5760 /* When trying to determine whether or not a biv increment occurs
5761 during the lifetime of the giv, we can ignore uses of the variable
5762 outside the loop because final_value is true. Hence we can not
5763 use regno_last_uid and regno_first_uid as above in record_giv. */
5765 /* Search the loop to determine whether any assignments to the
5766 biv occur during the giv's lifetime. Start with the insn
5767 that sets the giv, and search around the loop until we come
5768 back to that insn again.
5770 Also fail if there is a jump within the giv's lifetime that jumps
5771 to somewhere outside the lifetime but still within the loop. This
5772 catches spaghetti code where the execution order is not linear, and
5773 hence the above test fails. Here we assume that the giv lifetime
5774 does not extend from one iteration of the loop to the next, so as
5775 to make the test easier. Since the lifetime isn't known yet,
5776 this requires two loops. See also record_giv above. */
5781 {
5790 {
5792 {
5794 {
5798 }
5799 }
5804 }
5805 }
5807 /* Now that the lifetime of the giv is known, check for branches
5808 from within the lifetime to outside the lifetime if it is still
5809 replaceable. */
5812 {
5815 {
5828 {
5837 }
5838 }
5839 }
5841 /* If it is replaceable, then save the final value. */
5844 }
5849 }
5850 \f
5851 /* Update the status of whether a giv can derive other givs.
5853 We need to do something special if there is or may be an update to the biv
5854 between the time the giv is defined and the time it is used to derive
5855 another giv.
5857 In addition, a giv that is only conditionally set is not allowed to
5858 derive another giv once a label has been passed.
5860 The cases we look at are when a label or an update to a biv is passed. */
5862 static void
5864 rtx p;
5865 {
5868 rtx tem;
5871 /* Search all IV classes, then all bivs, and finally all givs.
5873 There are three cases we are concerned with. First we have the situation
5874 of a giv that is only updated conditionally. In that case, it may not
5875 derive any givs after a label is passed.
5877 The second case is when a biv update occurs, or may occur, after the
5878 definition of a giv. For certain biv updates (see below) that are
5879 known to occur between the giv definition and use, we can adjust the
5880 giv definition. For others, or when the biv update is conditional,
5881 we must prevent the giv from deriving any other givs. There are two
5882 sub-cases within this case.
5884 If this is a label, we are concerned with any biv update that is done
5885 conditionally, since it may be done after the giv is defined followed by
5886 a branch here (actually, we need to pass both a jump and a label, but
5887 this extra tracking doesn't seem worth it).
5889 If this is a jump, we are concerned about any biv update that may be
5890 executed multiple times. We are actually only concerned about
5891 backward jumps, but it is probably not worth performing the test
5892 on the jump again here.
5894 If this is a biv update, we must adjust the giv status to show that a
5895 subsequent biv update was performed. If this adjustment cannot be done,
5896 the giv cannot derive further givs. */
5902 {
5904 {
5905 /* If cant_derive is already true, there is no point in
5906 checking all of these conditions again. */
5910 /* If this giv is conditionally set and we have passed a label,
5911 it cannot derive anything. */
5915 /* Skip givs that have mult_val == 0, since
5916 they are really invariants. Also skip those that are
5917 replaceable, since we know their lifetime doesn't contain
5918 any biv update. */
5922 /* The only way we can allow this giv to derive another
5923 is if this is a biv increment and we can form the product
5924 of biv->add_val and giv->mult_val. In this case, we will
5925 be able to compute a compensation. */
5927 {
5937 tem = simplify_giv_expr
5943 else
5945 }
5949 }
5950 }
5951 }
5952 \f
5953 /* Check whether an insn is an increment legitimate for a basic induction var.
5954 X is the source of insn P, or a part of it.
5955 MODE is the mode in which X should be interpreted.
5957 DEST_REG is the putative biv, also the destination of the insn.
5958 We accept patterns of these forms:
5959 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5960 REG = INVARIANT + REG
5962 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5963 store the additive term into *INC_VAL, and store the place where
5964 we found the additive term into *LOCATION.
5966 If X is an assignment of an invariant into DEST_REG, we set
5967 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5969 We also want to detect a BIV when it corresponds to a variable
5970 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5971 of the variable may be a PLUS that adds a SUBREG of that variable to
5972 an invariant and then sign- or zero-extends the result of the PLUS
5973 into the variable.
5975 Most GIVs in such cases will be in the promoted mode, since that is the
5976 probably the natural computation mode (and almost certainly the mode
5977 used for addresses) on the machine. So we view the pseudo-reg containing
5978 the variable as the BIV, as if it were simply incremented.
5980 Note that treating the entire pseudo as a BIV will result in making
5981 simple increments to any GIVs based on it. However, if the variable
5982 overflows in its declared mode but not its promoted mode, the result will
5983 be incorrect. This is acceptable if the variable is signed, since
5984 overflows in such cases are undefined, but not if it is unsigned, since
5985 those overflows are defined. So we only check for SIGN_EXTEND and
5986 not ZERO_EXTEND.
5988 If we cannot find a biv, we return 0. */
5990 static int
5994 rtx p;
5995 rtx dest_reg;
5999 {
6007 {
6013 {
6015 }
6020 {
6022 }
6023 else
6036 /* If this is a SUBREG for a promoted variable, check the inner
6037 value. */
6044 /* If this register is assigned in a previous insn, look at its
6045 source, but don't go outside the loop or past a label. */
6049 {
6073 }
6074 /* ... fall through ... */
6076 /* Can accept constant setting of biv only when inside inner most loop.
6077 Otherwise, a biv of an inner loop may be incorrectly recognized
6078 as a biv of the outer loop,
6079 causing code to be moved INTO the inner loop. */
6086 /* convert_modes aborts if we try to convert to or from CCmode, so just
6087 exclude that case. It is very unlikely that a condition code value
6088 would be a useful iterator anyways. */
6092 {
6093 /* Possible bug here? Perhaps we don't know the mode of X. */
6097 }
6098 else
6106 /* Similar, since this can be a sign extension. */
6111 ;
6124 location);
6129 }
6130 }
6131 \f
6132 /* A general induction variable (giv) is any quantity that is a linear
6133 function of a basic induction variable,
6134 i.e. giv = biv * mult_val + add_val.
6135 The coefficients can be any loop invariant quantity.
6136 A giv need not be computed directly from the biv;
6137 it can be computed by way of other givs. */
6139 /* Determine whether X computes a giv.
6140 If it does, return a nonzero value
6141 which is the benefit from eliminating the computation of X;
6142 set *SRC_REG to the register of the biv that it is computed from;
6143 set *ADD_VAL and *MULT_VAL to the coefficients,
6144 such that the value of X is biv * mult + add; */
6146 static int
6148 rtx x;
6154 {
6158 /* If this is an invariant, forget it, it isn't a giv. */
6162 /* See if the expression could be a giv and get its form.
6163 Mark our place on the obstack in case we don't find a giv. */
6168 {
6171 }
6174 {
6177 /* Since this is now an invariant and wasn't before, it must be a giv
6178 with MULT_VAL == 0. It doesn't matter which BIV we associate this
6179 with. */
6186 /* This is equivalent to a BIV. */
6193 /* Either (plus (biv) (invar)) or
6194 (plus (mult (biv) (invar_1)) (invar_2)). */
6196 {
6199 }
6200 else
6201 {
6204 }
6209 /* ADD_VAL is zero. */
6217 }
6219 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
6220 unless they are CONST_INT). */
6227 {
6228 #ifdef ADDRESS_COST
6230 #else
6232 #endif
6233 }
6234 else
6237 /* Always return true if this is a giv so it will be detected as such,
6238 even if the benefit is zero or negative. This allows elimination
6239 of bivs that might otherwise not be eliminated. */
6241 }
6242 \f
6243 /* Given an expression, X, try to form it as a linear function of a biv.
6244 We will canonicalize it to be of the form
6245 (plus (mult (BIV) (invar_1))
6246 (invar_2))
6247 with possible degeneracies.
6249 The invariant expressions must each be of a form that can be used as a
6250 machine operand. We surround then with a USE rtx (a hack, but localized
6251 and certainly unambiguous!) if not a CONST_INT for simplicity in this
6252 routine; it is the caller's responsibility to strip them.
6254 If no such canonicalization is possible (i.e., two biv's are used or an
6255 expression that is neither invariant nor a biv or giv), this routine
6256 returns 0.
6258 For a non-zero return, the result will have a code of CONST_INT, USE,
6259 REG (for a BIV), PLUS, or MULT. No other codes will occur.
6261 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
6266 static rtx
6268 rtx x;
6270 {
6273 rtx tem;
6275 /* If this is not an integer mode, or if we cannot do arithmetic in this
6276 mode, this can't be a giv. */
6283 {
6290 /* Put constant last, CONST_INT last if both constant. */
6298 /* Handle addition of zero, then addition of an invariant. */
6303 {
6306 /* Adding two invariants must result in an invariant, so enclose
6307 addition operation inside a USE and return it. */
6317 else
6326 /* biv + invar or mult + invar. Return sum. */
6330 /* (a + invar_1) + invar_2. Associate. */
6331 return
6336 arg1)),
6337 benefit);
6341 }
6343 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
6344 MULT to reduce cases. */
6350 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
6351 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
6352 Recurse to associate the second PLUS. */
6357 return
6362 benefit);
6364 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
6376 benefit);
6379 /* Handle "a - b" as "a + b * (-1)". */
6384 constm1_rtx)),
6385 benefit);
6393 /* Put constant last, CONST_INT last if both constant. */
6398 /* If second argument is not now constant, not giv. */
6402 /* Handle multiply by 0 or 1. */
6410 {
6412 /* biv * invar. Done. */
6416 /* Product of two constants. */
6420 /* invar * invar. It is a giv, but very few of these will
6421 actually pay off, so limit to simple registers. */
6431 {
6435 }
6436 else
6441 /* (a * invar_1) * invar_2. Associate. */
6446 arg1)),
6447 benefit);
6450 /* (a + invar_1) * invar_2. Distribute. */
6454 arg1),
6457 arg1)),
6458 benefit);
6462 }
6465 /* Shift by constant is multiply by power of two. */
6469 return
6474 benefit);
6477 /* "-a" is "a * (-1)" */
6479 benefit);
6482 /* "~a" is "-a - 1". Silly, but easy. */
6485 const1_rtx),
6486 benefit);
6489 /* Already in proper form for invariant. */
6493 /* If this is a new register, we can't deal with it. */
6497 /* Check for biv or giv. */
6499 {
6503 {
6506 /* Form expression from giv and add benefit. Ensure this giv
6507 can derive another and subtract any needed adjustment if so. */
6519 }
6522 /* If it isn't an induction variable, and it is invariant, we
6523 may be able to simplify things further by looking through
6524 the bits we just moved outside the loop. */
6526 {
6531 {
6532 /* Ok, we found a match. Substitute and simplify. */
6534 /* If we match another movable, we must use that, as
6535 this one is going away. */
6539 /* If consec is non-zero, this is a member of a group of
6540 instructions that were moved together. We handle this
6541 case only to the point of seeking to the last insn and
6542 looking for a REG_EQUAL. Fail if we don't find one. */
6544 {
6552 }
6553 else
6554 {
6558 }
6561 {
6562 /* What we are most interested in is pointer
6563 arithmetic on invariants -- only take
6564 patterns we may be able to do something with. */
6570 {
6574 }
6579 {
6583 }
6584 }
6586 }
6587 }
6589 }
6591 /* Fall through to general case. */
6593 /* If invariant, return as USE (unless CONST_INT).
6594 Otherwise, not giv. */
6599 {
6608 }
6609 else
6611 }
6612 }
6614 /* This routine folds invariants such that there is only ever one
6615 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6617 static rtx
6620 {
6626 {
6629 }
6632 {
6635 }
6636 else
6637 {
6640 }
6641 }
6643 static rtx
6647 {
6649 {
6653 else
6656 }
6659 else
6662 }
6663 \f
6664 /* Help detect a giv that is calculated by several consecutive insns;
6665 for example,
6666 giv = biv * M
6667 giv = giv + A
6668 The caller has already identified the first insn P as having a giv as dest;
6669 we check that all other insns that set the same register follow
6670 immediately after P, that they alter nothing else,
6671 and that the result of the last is still a giv.
6673 The value is 0 if the reg set in P is not really a giv.
6674 Otherwise, the value is the amount gained by eliminating
6675 all the consecutive insns that compute the value.
6677 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6678 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6680 The coefficients of the ultimate giv value are stored in
6681 *MULT_VAL and *ADD_VAL. */
6683 static int
6687 rtx p;
6688 rtx src_reg;
6689 rtx dest_reg;
6693 {
6697 rtx temp;
6698 rtx set;
6700 /* Indicate that this is a giv so that we can update the value produced in
6701 each insn of the multi-insn sequence.
6703 This induction structure will be used only by the call to
6704 general_induction_var below, so we can allocate it on our stack.
6705 If this is a giv, our caller will replace the induct var entry with
6706 a new induction structure. */
6722 {
6726 /* If libcall, skip to end of call sequence. */
6736 /* Giv created by equivalent expression. */
6741 {
6745 count--;
6749 }
6751 {
6752 /* Allow insns that set something other than this giv to a
6753 constant. Such insns are needed on machines which cannot
6754 include long constants and should not disqualify a giv. */
6763 }
6764 }
6768 }
6769 \f
6770 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6771 represented by G1. If no such expression can be found, or it is clear that
6772 it cannot possibly be a valid address, 0 is returned.
6774 To perform the computation, we note that
6775 G1 = x * v + a and
6776 G2 = y * v + b
6777 where `v' is the biv.
6779 So G2 = (y/b) * G1 + (b - a*y/x).
6781 Note that MULT = y/x.
6783 Update: A and B are now allowed to be additive expressions such that
6784 B contains all variables in A. That is, computing B-A will not require
6785 subtracting variables. */
6787 static rtx
6790 {
6791 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6796 /* If MULT is not 1, we cannot handle A with non-constants, since we
6797 would then be required to subtract multiples of the registers in A.
6798 This is theoretically possible, and may even apply to some Fortran
6799 constructs, but it is a lot of work and we do not attempt it here. */
6804 /* In general these structures are sorted top to bottom (down the PLUS
6805 chain), but not left to right across the PLUS. If B is a higher
6806 order giv than A, we can strip one level and recurse. If A is higher
6807 order, we'll eventually bail out, but won't know that until the end.
6808 If they are the same, we'll strip one level around this loop. */
6811 {
6823 /* We matched: remove one reg completely. */
6826 /* An alternate match. */
6829 /* An alternate match. */
6831 else
6832 {
6833 /* Indicates an extra register in B. Strip one level from B and
6834 recurse, hoping B was the higher order expression. */
6839 }
6840 }
6842 /* Here we are at the last level of A, go through the cases hoping to
6843 get rid of everything but a constant. */
6846 {
6859 }
6861 {
6863 }
6865 {
6870 else
6872 }
6877 }
6879 rtx
6882 {
6885 /* The value that G1 will be multiplied by must be a constant integer. Also,
6886 the only chance we have of getting a valid address is if b*c/a (see above
6887 for notation) is also an integer. */
6890 {
6895 }
6898 else
6899 {
6900 /* ??? Find out if the one is a multiple of the other? */
6902 }
6906 {
6907 /* Failed. If we've got a multiplication factor between G1 and G2,
6908 scale G1's addend and try again. */
6910 {
6914 {
6915 HOST_WIDE_INT m;
6919 }
6920 else
6921 {
6923 mult);
6924 }
6927 }
6928 }
6932 /* Form simplified final result. */
6937 else
6942 else
6943 {
6946 {
6950 }
6953 }
6955 }
6956 \f
6957 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6958 represented by G1. This indicates that G2 should be combined with G1 and
6959 that G2 can use (either directly or via an address expression) a register
6960 used to represent G1. */
6962 static rtx
6965 {
6968 /* If these givs are identical, they can be combined. We use the results
6969 of express_from because the addends are not in a canonical form, so
6970 rtx_equal_p is a weaker test. */
6971 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6972 combination to be the other way round. */
6975 {
6977 }
6979 /* If G2 can be expressed as a function of G1 and that function is valid
6980 as an address and no more expensive than using a register for G2,
6981 the expression of G2 in terms of G1 can be used. */
6985 /* ??? Looses, especially with -fforce-addr, where *g2->location
6986 will always be a register, and so anything more complicated
6987 gets discarded. */
6988 #if 0
6989 #ifdef ADDRESS_COST
6991 #else
6993 #endif
6994 #endif
6995 )
6996 {
6998 }
7001 }
7002 \f
7003 struct combine_givs_stats
7004 {
7007 };
7009 static int
7012 {
7015 /* Stabilize the sort. */
7019 }
7021 /* Check all pairs of givs for iv_class BL and see if any can be combined with
7022 any other. If so, point SAME to the giv combined with and set NEW_REG to
7023 be an expression (in terms of the other giv's DEST_REG) equivalent to the
7024 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
7026 static void
7029 {
7030 /* Additional benefit to add for being combined multiple times. */
7038 /* Count givs, because bl->giv_count is incorrect here. */
7042 giv_count++;
7044 giv_array
7058 {
7060 rtx single_use;
7065 /* If a DEST_REG GIV is used only once, do not allow it to combine
7066 with anything, for in doing so we will gain nothing that cannot
7067 be had by simply letting the GIV with which we would have combined
7068 to be reduced on its own. The losage shows up in particular with
7069 DEST_ADDR targets on hosts with reg+reg addressing, though it can
7070 be seen elsewhere as well. */
7077 /* Add an additional weight for zero addends. */
7082 {
7083 rtx this_combine;
7088 {
7091 }
7092 }
7094 }
7096 /* Iterate, combining until we can't. */
7097 restart:
7101 {
7104 {
7110 }
7112 }
7115 {
7121 /* If it has already been combined, skip. */
7126 {
7129 /* If it has already been combined, skip. */
7131 {
7141 /* ??? The new final_[bg]iv_value code does a much better job
7142 of finding replaceable giv's, and hence this code may no
7143 longer be necessary. */
7147 /* To help optimize the next set of combinations, remove
7148 this giv from the benefits of other potential mates. */
7150 {
7154 }
7160 }
7161 }
7163 /* To help optimize the next set of combinations, remove
7164 this giv from the benefits of other potential mates. */
7166 {
7168 {
7172 }
7176 /* We've finished with this giv, and everything it touched.
7177 Restart the combination so that proper weights for the
7178 rest of the givs are properly taken into account. */
7179 /* ??? Ideally we would compact the arrays at this point, so
7180 as to not cover old ground. But sanely compacting
7181 can_combine is tricky. */
7183 }
7184 }
7185 }
7186 \f
7187 struct recombine_givs_stats
7188 {
7191 };
7193 /* Used below as comparison function for qsort. We want a ascending luid
7194 when scanning the array starting at the end, thus the arguments are
7195 used in reverse. */
7196 static int
7199 {
7202 /* Stabilize the sort. */
7206 }
7208 /* Scan X, which is a part of INSN, for the end of life of a giv. Also
7209 look for the start of life of a giv where the start has not been seen
7210 yet to unlock the search for the end of its life.
7211 Only consider givs that belong to BIV.
7212 Return the total number of lifetime ends that have been found. */
7213 static int
7217 {
7225 {
7227 {
7230 {
7238 {
7239 /* If we see a 0 here for end_luid, it means that we have
7240 scanned the entire loop without finding any use at all.
7241 We must not predicate this code on a start_luid match
7242 since that would make the test fail for givs that have
7243 been hoisted out of inner loops. */
7245 {
7248 }
7251 }
7253 }
7255 }
7257 {
7265 {
7270 }
7272 }
7280 }
7284 {
7291 }
7293 }
7295 /* For each giv that has been combined with another, look if
7296 we can combine it with the most recently used one instead.
7297 This tends to shorten giv lifetimes, and helps the next step:
7298 try to derive givs from other givs. */
7299 static void
7304 {
7312 {
7314 giv_count++;
7315 }
7316 giv_array
7320 /* Initialize stats and set up the ix field for each giv in stats to name
7321 the corresponding index into stats. */
7323 {
7324 rtx p;
7330 /* If this giv has been hoisted out of an inner loop, use the luid of
7331 the previous insn. */
7335 i++;
7336 }
7340 /* Set up the ix field for each giv in stats to name
7341 the corresponding index into stats, and
7342 do the actual most-recently-used recombination. */
7344 {
7348 {
7350 rtx new_combine;
7352 /* combine_givs_p actually says if we can make this transformation.
7353 The other tests are here only to avoid keeping a giv alive
7354 that could otherwise be eliminated. */
7360 {
7365 /* No need to update lifetimes / benefits here since we have
7366 already decided what to reduce. */
7369 {
7375 }
7377 }
7379 }
7387 }
7390 /* For each DEST_REG giv, compute lifetime starts, and try to compute
7391 lifetime ends from regscan info. */
7393 {
7398 {
7399 /* Loop unrolling of an inner loop can even create new DEST_REG
7400 givs. */
7401 rtx p;
7407 }
7409 {
7411 {
7414 }
7416 {
7417 rtx p;
7418 /* This insn has been created by loop optimization on an inner
7419 loop. We don't have a proper start_luid that will match
7420 when we see the first set. But we do know that there will
7421 be no use before the set, so we can set end_luid to 0 so that
7422 we'll start looking for the last use right away. */
7427 ends_need_computing++;
7428 }
7429 else
7430 {
7435 /* Find the first insn that sets the giv, so that we can verify
7436 if this giv's lifetime wraps around the loop. We also need
7437 the luid of the first setting insn in order to detect the
7438 last use properly. */
7440 {
7443 count--;
7444 }
7448 {
7450 ends_need_computing++;
7451 }
7452 else
7453 {
7456 {
7458 ends_need_computing++;
7459 }
7460 }
7461 }
7462 }
7463 }
7465 /* If the regscan information was unconclusive for one or more DEST_REG
7466 givs, scan the all insn in the loop to find out lifetime ends. */
7468 {
7472 do
7473 {
7480 }
7482 }
7484 /* Set start_luid back to the last insn that sets the giv. This allows
7485 more combinations. */
7487 {
7493 }
7495 /* Now adjust lifetime ends by taking combined givs into account. */
7497 {
7505 {
7508 /* Use unsigned arithmetic to model loop wrap-around. */
7512 }
7513 }
7517 /* Try to derive DEST_REG givs from previous DEST_REG givs with the
7518 same mult_val and non-overlapping lifetime. This reduces register
7519 pressure.
7520 Once we find a DEST_REG giv that is suitable to derive others from,
7521 we set last_giv to this giv, and try to derive as many other DEST_REG
7522 givs from it without joining overlapping lifetimes. If we then
7523 encounter a DEST_REG giv that we can't derive, we set rescan to the
7524 index for this giv (unless rescan is already set).
7525 When we are finished with the current LAST_GIV (i.e. the inner loop
7526 terminates), we start again with rescan, which then becomes the new
7527 LAST_GIV. */
7529 {
7533 {
7534 rtx sum;
7540 {
7541 /* Don't use a giv that's likely to be dead to derive
7542 others - that would be likely to keep that giv alive. */
7544 {
7548 }
7550 }
7551 /* Use unsigned arithmetic to model loop wrap around. */
7556 /* Check that the giv insn we're about to use for deriving
7557 precedes all uses of that giv. Note that initializing the
7558 derived giv would defeat the purpose of reducing register
7559 pressure.
7560 ??? We could arrange to move the insn. */
7564 /* ??? Could handle libcalls, but would need more logic. */
7566 /* We would really like to know if for any giv that v
7567 is combined with, v->insn or any intervening biv increment
7568 dominates that combined giv. However, we
7569 don't have this detailed control flow information.
7570 N.B. since last_giv will be reduced, it is valid
7571 anywhere in the loop, so we don't need to check the
7572 validity of last_giv.
7573 We rely here on the fact that v->always_executed implies that
7574 there is no jump to someplace else in the loop before the
7575 giv insn, and hence any insn that is executed before the
7576 giv insn in the loop will have a lower luid. */
7579 /* Make sure we don't make the add more expensive. ADD_COST
7580 doesn't take different costs of registers and constants into
7581 account, so compare the cost of the actual SET_SRCs. */
7584 /* ??? unroll can't understand anything but reg + const_int
7585 sums. It would be cleaner to fix unroll. */
7592 {
7597 {
7603 }
7604 }
7607 }
7608 }
7609 }
7610 \f
7611 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
7613 void
7619 rtx insert_before;
7620 {
7621 rtx seq;
7622 rtx result;
7624 /* Prevent unexpected sharing of these rtx. */
7628 /* Increase the lifetime of any invariants moved further in code. */
7642 /* It is entirely possible that the expansion created lots of new
7643 registers. Iterate over the sequence we just created and
7644 record them all. */
7647 {
7650 {
7654 }
7655 }
7659 }
7660 \f
7661 /* Test whether A * B can be computed without
7662 an actual multiply insn. Value is 1 if so. */
7664 static int
7666 rtx a;
7667 rtx b;
7668 {
7670 rtx tmp;
7675 /* If only one is constant, make it B. */
7679 /* If first constant, both constant, so don't need multiply. */
7683 /* If second not constant, neither is constant, so would need multiply. */
7687 /* One operand is constant, so might not need multiply insn. Generate the
7688 code for the multiply and see if a call or multiply, or long sequence
7689 of insns is generated. */
7698 {
7703 else
7705 {
7714 {
7717 }
7718 }
7719 }
7728 /* Free any storage we obtained in generating this multiply and restore rtl
7729 allocation to its normal obstack. */
7734 }
7735 \f
7736 /* Check to see if loop can be terminated by a "decrement and branch until
7737 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7738 Also try reversing an increment loop to a decrement loop
7739 to see if the optimization can be performed.
7740 Value is nonzero if optimization was performed. */
7742 /* This is useful even if the architecture doesn't have such an insn,
7743 because it might change a loops which increments from 0 to n to a loop
7744 which decrements from n to 0. A loop that decrements to zero is usually
7745 faster than one that increments from zero. */
7747 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7748 such as approx_final_value, biv_total_increment, loop_iterations, and
7749 final_[bg]iv_value. */
7751 static int
7753 rtx loop_end;
7755 rtx loop_start;
7757 {
7759 rtx reg;
7760 rtx jump_label;
7761 rtx final_value;
7762 rtx start_value;
7763 rtx new_add_val;
7764 rtx comparison;
7765 rtx before_comparison;
7766 rtx p;
7767 rtx jump;
7768 rtx first_compare;
7771 /* If last insn is a conditional branch, and the insn before tests a
7772 register value, try to optimize it. Otherwise, we can't do anything. */
7779 /* Try to compute whether the compare/branch at the loop end is one or
7780 two instructions. */
7786 else
7789 /* Check all of the bivs to see if the compare uses one of them.
7790 Skip biv's set more than once because we can't guarantee that
7791 it will be zero on the last iteration. Also skip if the biv is
7792 used between its update and the test insn. */
7795 {
7799 first_compare))
7801 }
7806 /* Look for the case where the basic induction variable is always
7807 nonnegative, and equals zero on the last iteration.
7808 In this case, add a reg_note REG_NONNEG, which allows the
7809 m68k DBRA instruction to be used. */
7817 {
7818 /* Initial value must be greater than 0,
7819 init_val % -dec_value == 0 to ensure that it equals zero on
7820 the last iteration */
7826 {
7827 /* register always nonnegative, add REG_NOTE to branch */
7834 }
7836 /* If the decrement is 1 and the value was tested as >= 0 before
7837 the loop, then we can safely optimize. */
7839 {
7852 {
7859 }
7860 }
7861 }
7864 {
7865 /* Try to change inc to dec, so can apply above optimization. */
7866 /* Can do this if:
7867 all registers modified are induction variables or invariant,
7868 all memory references have non-overlapping addresses
7869 (obviously true if only one write)
7870 allow 2 insns for the compare/jump at the end of the loop. */
7871 /* Also, we must avoid any instructions which use both the reversed
7872 biv and another biv. Such instructions will fail if the loop is
7873 reversed. We meet this condition by requiring that either
7874 no_use_except_counting is true, or else that there is only
7875 one biv. */
7877 /* 1 if the iteration var is used only to count iterations. */
7879 /* 1 if the loop has no memory store, or it has a single memory store
7880 which is reversible. */
7885 {
7888 /* If there are no givs for this biv, and the only exit is the
7889 fall through at the end of the loop, then
7890 see if perhaps there are no uses except to count. */
7894 {
7899 /* An insn that sets the biv is okay. */
7900 ;
7903 /* Don't bother about the end test. */
7904 ;
7906 {
7909 }
7910 }
7911 }
7916 {
7921 /* If the loop has a single store, and the destination address is
7922 invariant, then we can't reverse the loop, because this address
7923 might then have the wrong value at loop exit.
7924 This would work if the source was invariant also, however, in that
7925 case, the insn should have been moved out of the loop. */
7928 {
7931 reversible_mem_store
7932 = (! unknown_address_altered
7935 /* If the store depends on a register that is set after the
7936 store, it depends on the initial value, and is thus not
7937 reversible. */
7939 {
7945 }
7946 }
7947 }
7948 else
7951 /* This code only acts for innermost loops. Also it simplifies
7952 the memory address check by only reversing loops with
7953 zero or one memory access.
7954 Two memory accesses could involve parts of the same array,
7955 and that can't be reversed.
7956 If the biv is used only for counting, than we don't need to worry
7957 about all these things. */
7962 && reversible_mem_store
7967 {
7968 rtx tem;
7970 /* Loop can be reversed. */
7974 /* Now check other conditions:
7976 The increment must be a constant, as must the initial value,
7977 and the comparison code must be LT.
7979 This test can probably be improved since +/- 1 in the constant
7980 can be obtained by changing LT to LE and vice versa; this is
7981 confusing. */
7984 /* for constants, LE gets turned into LT */
7988 {
7999 comparison_const_width
8001 else
8002 comparison_const_width
8006 comparison_sign_mask
8009 /* If the comparison value is not a loop invariant, then we
8010 can not reverse this loop.
8012 ??? If the insns which initialize the comparison value as
8013 a whole compute an invariant result, then we could move
8014 them out of the loop and proceed with loop reversal. */
8022 /* Normalize the initial value if it is an integer and
8023 has no other use except as a counter. This will allow
8024 a few more loops to be reversed. */
8028 {
8030 /* The code below requires comparison_val to be a multiple
8031 of add_val in order to do the loop reversal, so
8032 round up comparison_val to a multiple of add_val.
8033 Since comparison_value is constant, we know that the
8034 current comparison code is LT. */
8036 comparison_val
8038 /* We postpone overflow checks for COMPARISON_VAL here;
8039 even if there is an overflow, we might still be able to
8040 reverse the loop, if converting the loop exit test to
8041 NE is possible. */
8043 }
8045 /* First check if we can do a vanilla loop reversal. */
8047 /* If we have a decrement_and_branch_on_count,
8048 prefer the NE test, since this will allow that
8049 instruction to be generated. Note that we must
8050 use a vanilla loop reversal if the biv is used to
8051 calculate a giv or has a non-counting use. */
8052 #if ! defined (HAVE_decrement_and_branch_until_zero) \
8053 && defined (HAVE_decrement_and_branch_on_count)
8057 #endif
8059 /* Now do postponed overflow checks on COMPARISON_VAL. */
8062 {
8063 /* Register will always be nonnegative, with value
8064 0 on last iteration */
8068 }
8072 {
8075 }
8076 else
8082 /* If the initial value is not zero, or if the comparison
8083 value is not an exact multiple of the increment, then we
8084 can not reverse this loop. */
8087 {
8090 }
8091 else
8092 {
8095 }
8099 /* Reset these in case we normalized the initial value
8100 and comparison value above. */
8103 {
8105 final_value
8107 }
8110 /* Save some info needed to produce the new insns. */
8117 /* Set start_value; if this is not a CONST_INT, we need
8118 to generate a SUB.
8119 Initialize biv to start_value before loop start.
8120 The old initializing insn will be deleted as a
8121 dead store by flow.c. */
8124 {
8127 loop_start);
8128 }
8130 {
8133 enum insn_code icode
8142 start_value
8146 loop_start);
8150 }
8152 {
8154 enum insn_code icode
8162 start_value
8166 loop_start);
8167 }
8168 else
8169 /* We could handle the other cases too, but it'll be
8170 better to have a testcase first. */
8173 /* We may not have a single insn which can increment a reg, so
8174 create a sequence to hold all the insns from expand_inc. */
8183 /* Update biv info to reflect its new status. */
8188 /* Update loop info. */
8197 /* Inc LABEL_NUSES so that delete_insn will
8198 not delete the label. */
8201 /* Emit an insn after the end of the loop to set the biv's
8202 proper exit value if it is used anywhere outside the loop. */
8207 loop_end);
8209 /* Delete compare/branch at end of loop. */
8214 /* Add new compare/branch insn at end of loop. */
8226 ;
8232 {
8234 {
8235 /* Increment of LABEL_NUSES done above. */
8236 /* Register is now always nonnegative,
8237 so add REG_NONNEG note to the branch. */
8240 }
8242 }
8244 /* No insn may reference both the reversed and another biv or it
8245 will fail (see comment near the top of the loop reversal
8246 code).
8247 Earlier on, we have verified that the biv has no use except
8248 counting, or it is the only biv in this function.
8249 However, the code that computes no_use_except_counting does
8250 not verify reg notes. It's possible to have an insn that
8251 references another biv, and has a REG_EQUAL note with an
8252 expression based on the reversed biv. To avoid this case,
8253 remove all REG_EQUAL notes based on the reversed biv
8254 here. */
8257 {
8260 /* If this is a set of a GIV based on the reversed biv, any
8261 REG_EQUAL notes should still be correct. */
8268 {
8273 else
8275 }
8276 }
8278 /* Mark that this biv has been reversed. Each giv which depends
8279 on this biv, and which is also live past the end of the loop
8280 will have to be fixed up. */
8285 {
8289 else
8291 }
8294 }
8295 }
8296 }
8299 }
8300 \f
8301 /* Verify whether the biv BL appears to be eliminable,
8302 based on the insns in the loop that refer to it.
8303 LOOP_START is the first insn of the loop, and END is the end insn.
8305 If ELIMINATE_P is non-zero, actually do the elimination.
8307 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
8308 determine whether invariant insns should be placed inside or at the
8309 start of the loop. */
8311 static int
8314 rtx loop_start;
8315 rtx end;
8318 {
8320 rtx p;
8322 /* Scan all insns in the loop, stopping if we find one that uses the
8323 biv in a way that we cannot eliminate. */
8326 {
8330 /* If this is a libcall that sets a giv, skip ahead to its end. */
8332 {
8336 {
8341 {
8348 }
8349 }
8350 }
8354 {
8360 }
8361 }
8364 {
8369 }
8372 }
8373 \f
8374 /* INSN and REFERENCE are instructions in the same insn chain.
8375 Return non-zero if INSN is first. */
8377 int
8380 {
8384 {
8385 /* Start with test for not first so that INSN == REFERENCE yields not
8386 first. */
8392 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
8393 previous insn, hence the <= comparison below does not work if
8394 P is a note. */
8405 }
8406 }
8408 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
8409 the offset that we have to take into account due to auto-increment /
8410 div derivation is zero. */
8411 static int
8414 rtx insn;
8415 {
8416 /* If the giv V had the auto-inc address optimization applied
8417 to it, and INSN occurs between the giv insn and the biv
8418 insn, then we'd have to adjust the value used here.
8419 This is rare, so we don't bother to make this possible. */
8427 /* If the giv V was derived from another giv, and INSN does
8428 not occur between the giv insn and the biv insn, then we'd
8429 have to adjust the value used here. This is rare, so we don't
8430 bother to make this possible. */
8444 }
8446 /* If BL appears in X (part of the pattern of INSN), see if we can
8447 eliminate its use. If so, return 1. If not, return 0.
8449 If BIV does not appear in X, return 1.
8451 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
8452 where extra insns should be added. Depending on how many items have been
8453 moved out of the loop, it will either be before INSN or at the start of
8454 the loop. */
8456 static int
8461 rtx where;
8462 {
8468 #ifdef HAVE_cc0
8470 #endif
8476 {
8478 /* If we haven't already been able to do something with this BIV,
8479 we can't eliminate it. */
8485 /* If this sets the BIV, it is not a problem. */
8489 /* If this is an insn that defines a giv, it is also ok because
8490 it will go away when the giv is reduced. */
8495 #ifdef HAVE_cc0
8497 {
8498 /* Can replace with any giv that was reduced and
8499 that has (MULT_VAL != 0) and (ADD_VAL == 0).
8500 Require a constant for MULT_VAL, so we know it's nonzero.
8501 ??? We disable this optimization to avoid potential
8502 overflows. */
8510 {
8517 /* If the giv has the opposite direction of change,
8518 then reverse the comparison. */
8522 else
8525 /* We can probably test that giv's reduced reg. */
8528 }
8530 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
8531 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
8532 Require a constant for MULT_VAL, so we know it's nonzero.
8533 ??? Do this only if ADD_VAL is a pointer to avoid a potential
8534 overflow problem. */
8545 {
8552 /* If the giv has the opposite direction of change,
8553 then reverse the comparison. */
8557 else
8561 /* Replace biv with the giv's reduced register. */
8566 /* Insn doesn't support that constant or invariant. Copy it
8567 into a register (it will be a loop invariant.) */
8571 where);
8573 /* Substitute the new register for its invariant value in
8574 the compare expression. */
8578 }
8579 }
8580 #endif
8587 /* See if either argument is the biv. */
8592 else
8596 {
8597 /* First try to replace with any giv that has constant positive
8598 mult_val and constant add_val. We might be able to support
8599 negative mult_val, but it seems complex to do it in general. */
8610 {
8617 /* Replace biv with the giv's reduced reg. */
8620 /* If all constants are actually constant integers and
8621 the derived constant can be directly placed in the COMPARE,
8622 do so. */
8632 /* Otherwise, load it into a register. */
8638 /* If that failed, put back the change we made above. */
8640 }
8642 /* Look for giv with positive constant mult_val and nonconst add_val.
8643 Insert insns to calculate new compare value.
8644 ??? Turn this off due to possible overflow. */
8651 {
8652 rtx tem;
8662 /* Replace biv with giv's reduced register. */
8666 /* Compute value to compare against. */
8668 /* Use it in this insn. */
8672 }
8673 }
8675 {
8677 {
8678 /* Look for giv with constant positive mult_val and nonconst
8679 add_val. Insert insns to compute new compare value.
8680 ??? Turn this off due to possible overflow. */
8687 {
8688 rtx tem;
8698 /* Replace biv with giv's reduced register. */
8702 /* Compute value to compare against. */
8708 }
8709 }
8711 /* This code has problems. Basically, you can't know when
8712 seeing if we will eliminate BL, whether a particular giv
8713 of ARG will be reduced. If it isn't going to be reduced,
8714 we can't eliminate BL. We can try forcing it to be reduced,
8715 but that can generate poor code.
8717 The problem is that the benefit of reducing TV, below should
8718 be increased if BL can actually be eliminated, but this means
8719 we might have to do a topological sort of the order in which
8720 we try to process biv. It doesn't seem worthwhile to do
8721 this sort of thing now. */
8723 #if 0
8724 /* Otherwise the reg compared with had better be a biv. */
8729 /* Look for a pair of givs, one for each biv,
8730 with identical coefficients. */
8732 {
8743 {
8750 /* Replace biv with its giv's reduced reg. */
8752 /* Replace other operand with the other giv's
8753 reduced reg. */
8756 }
8757 }
8758 #endif
8759 }
8761 /* If we get here, the biv can't be eliminated. */
8765 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8766 biv is used in it, since it will be replaced. */
8774 }
8776 /* See if any subexpression fails elimination. */
8779 {
8781 {
8794 }
8795 }
8798 }
8799 \f
8800 /* Return nonzero if the last use of REG
8801 is in an insn following INSN in the same basic block. */
8803 static int
8805 rtx reg;
8806 rtx insn;
8807 {
8808 rtx n;
8812 {
8815 }
8817 }
8818 \f
8819 /* Called via `note_stores' to record the initial value of a biv. Here we
8820 just record the location of the set and process it later. */
8822 static void
8824 rtx dest;
8825 rtx set;
8826 {
8836 /* If this is the first set found, record it. */
8838 {
8841 }
8842 }
8843 \f
8844 /* If any of the registers in X are "old" and currently have a last use earlier
8845 than INSN, update them to have a last use of INSN. Their actual last use
8846 will be the previous insn but it will not have a valid uid_luid so we can't
8847 use it. */
8849 static void
8851 rtx x;
8852 rtx insn;
8853 {
8854 /* Check for the case where INSN does not have a valid luid. In this case,
8855 there is no need to modify the regno_last_uid, as this can only happen
8856 when code is inserted after the loop_end to set a pseudo's final value,
8857 and hence this insn will never be the last use of x. */
8862 else
8863 {
8867 {
8873 }
8874 }
8875 }
8876 \f
8877 /* Given a jump insn JUMP, return the condition that will cause it to branch
8878 to its JUMP_LABEL. If the condition cannot be understood, or is an
8879 inequality floating-point comparison which needs to be reversed, 0 will
8880 be returned.
8882 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8883 insn used in locating the condition was found. If a replacement test
8884 of the condition is desired, it should be placed in front of that
8885 insn and we will be sure that the inputs are still valid.
8887 The condition will be returned in a canonical form to simplify testing by
8888 callers. Specifically:
8890 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8891 (2) Both operands will be machine operands; (cc0) will have been replaced.
8892 (3) If an operand is a constant, it will be the second operand.
8893 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8894 for GE, GEU, and LEU. */
8896 rtx
8898 rtx jump;
8900 {
8903 rtx set;
8904 rtx tem;
8910 /* If this is not a standard conditional jump, we can't parse it. */
8923 /* If this branches to JUMP_LABEL when the condition is false, reverse
8924 the condition. */
8929 /* If we are comparing a register with zero, see if the register is set
8930 in the previous insn to a COMPARE or a comparison operation. Perform
8931 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8932 in cse.c */
8935 {
8936 /* Set non-zero when we find something of interest. */
8939 #ifdef HAVE_cc0
8940 /* If comparison with cc0, import actual comparison from compare
8941 insn. */
8943 {
8954 }
8955 #endif
8957 /* If this is a COMPARE, pick up the two things being compared. */
8959 {
8963 }
8967 /* Go back to the previous insn. Stop if it is not an INSN. We also
8968 stop if it isn't a single set or if it has a REG_INC note because
8969 we don't want to bother dealing with it. */
8977 /* If this is setting OP0, get what it sets it to if it looks
8978 relevant. */
8980 {
8983 /* ??? We may not combine comparisons done in a CCmode with
8984 comparisons not done in a CCmode. This is to aid targets
8985 like Alpha that have an IEEE compliant EQ instruction, and
8986 a non-IEEE compliant BEQ instruction. The use of CCmode is
8987 actually artificial, simply to prevent the combination, but
8988 should not affect other platforms.
8990 However, we must allow VOIDmode comparisons to match either
8991 CCmode or non-CCmode comparison, because some ports have
8992 modeless comparisons inside branch patterns.
8994 ??? This mode check should perhaps look more like the mode check
8995 in simplify_comparison in combine. */
9003 && (STORE_FLAG_VALUE
9006 #ifdef FLOAT_STORE_FLAG_VALUE
9010 #endif
9011 ))
9022 && (STORE_FLAG_VALUE
9025 #ifdef FLOAT_STORE_FLAG_VALUE
9029 #endif
9030 ))
9036 {
9037 /* We might have reversed a LT to get a GE here. But this wasn't
9038 actually the comparison of data, so we don't flag that we
9039 have had to reverse the condition. */
9043 }
9044 else
9046 }
9049 /* If this sets OP0, but not directly, we have to give up. */
9053 {
9057 {
9061 }
9066 }
9067 }
9069 /* If constant is first, put it last. */
9073 /* If OP0 is the result of a comparison, we weren't able to find what
9074 was really being compared, so fail. */
9078 /* Canonicalize any ordered comparison with integers involving equality
9079 if we can do computations in the relevant mode and we do not
9080 overflow. */
9085 {
9088 unsigned HOST_WIDE_INT max_val
9092 {
9098 /* When cross-compiling, const_val might be sign-extended from
9099 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
9119 }
9120 }
9122 /* If this was floating-point and we reversed anything other than an
9123 EQ or NE, return zero. */
9126 && ! flag_fast_math
9130 #ifdef HAVE_cc0
9131 /* Never return CC0; return zero instead. */
9134 #endif
9137 }
9139 /* Similar to above routine, except that we also put an invariant last
9140 unless both operands are invariants. */
9142 rtx
9144 rtx x;
9145 {
9155 }
9157 #ifdef HAVE_decrement_and_branch_on_count
9158 /* Instrument loop for insertion of bct instruction. We distinguish between
9159 loops with compile-time bounds and those with run-time bounds.
9160 Information from loop_iterations() is used to compute compile-time bounds.
9161 Run-time bounds should use loop preconditioning, but currently ignored.
9162 */
9164 static void
9168 {
9174 /* If the loop condition is <= or >=, the number of iteration
9175 is 1 more than the range of the bounds of the loop. */
9182 /* It's impossible to instrument a competely unrolled loop. */
9186 /* Make sure that the count register is not in use. */
9188 {
9192 loop_num);
9194 }
9196 /* Make sure that the function has no indirect jumps. */
9198 {
9202 loop_num);
9204 }
9206 /* Make sure that the last loop insn is a conditional jump. */
9210 {
9214 loop_num);
9216 }
9218 /* Make sure that the loop does not contain a function call
9219 (the count register might be altered by the called function). */
9221 {
9225 loop_num);
9227 }
9229 /* Make sure that the loop does not jump via a table.
9230 (the count register might be used to perform the branch on table). */
9232 {
9236 loop_num);
9238 }
9240 /* Account for loop unrolling in instrumented iteration count. */
9243 else
9247 {
9248 /* Allow an enclosing outer loop to benefit if possible. */
9252 loop_num);
9254 }
9256 /* Try to instrument the loop. */
9258 /* Handle the simpler case, where the bounds are known at compile time. */
9260 {
9261 /* Mark all enclosing loops that they cannot use count register. */
9266 }
9268 /* Handle the more complex case, that the bounds are NOT known
9269 at compile time. In this case we generate run_time calculation
9270 of the number of iterations. */
9273 {
9277 loop_num);
9279 }
9283 {
9287 loop_num);
9289 }
9291 /* With runtime bounds, if the compare is of the form '!=' we give up */
9293 {
9297 loop_num);
9299 }
9300 /* Use common loop preconditioning code instead. */
9301 #if 0
9302 else
9303 {
9304 /* We rely on the existence of run-time guard to ensure that the
9305 loop executes at least once. */
9306 rtx sequence;
9307 rtx iterations_num_reg;
9309 unsigned HOST_WIDE_INT increment_value_abs
9312 /* make sure that the increment is a power of two, otherwise (an
9313 expensive) divide is needed. */
9315 {
9320 }
9322 /* compute the number of iterations */
9324 {
9325 rtx temp_reg;
9327 /* Again, the number of iterations is calculated by:
9328 ;
9329 ; compare-val - initial-val + (increment -1) + additional-iteration
9330 ; num_iterations = -----------------------------------------------------------------
9331 ; increment
9332 */
9333 /* ??? Do we have to call copy_rtx here before passing rtx to
9334 expand_binop? */
9336 {
9337 /* <, <= :the loop variable is increasing */
9341 }
9342 else
9343 {
9347 }
9357 temp_reg,
9360 else
9362 }
9367 }
9371 }
9373 /* Instrument loop by inserting a bct in it as follows:
9374 1. A new counter register is created.
9375 2. In the head of the loop the new variable is initialized to the value
9376 passed in the loop_num_iterations parameter.
9377 3. At the end of the loop, comparison of the register with 0 is generated.
9378 The created comparison follows the pattern defined for the
9379 decrement_and_branch_on_count insn, so this insn will be generated.
9380 4. The branch on the old variable are deleted. The compare must remain
9381 because it might be used elsewhere. If the loop-variable or condition
9382 register are used elsewhere, they will be eliminated by flow. */
9384 static void
9387 rtx loop_num_iterations;
9388 {
9389 rtx counter_reg;
9390 rtx start_label;
9391 rtx sequence;
9394 {
9396 {
9401 else
9404 }
9406 /* Discard original jump to continue loop. Original compare result
9407 may still be live, so it cannot be discarded explicitly. */
9410 /* Insert the label which will delimit the start of the loop. */
9414 /* Insert initialization of the count register into the loop header. */
9422 /* Insert new comparison on the count register instead of the
9423 old one, generating the needed BCT pattern (that will be
9424 later recognized by assembly generation phase). */
9426 start_label),
9427 loop_end);
9429 }
9431 }
9434 /* Scan the function and determine whether it has indirect (computed) jumps.
9436 This is taken mostly from flow.c; similar code exists elsewhere
9437 in the compiler. It may be useful to put this into rtlanal.c. */
9438 static int
9440 rtx start;
9441 {
9442 rtx insn;
9449 }
9451 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
9452 documentation for LOOP_MEMS for the definition of `appropriate'.
9453 This function is called from prescan_loop via for_each_rtx. */
9455 static int
9459 {
9467 {
9472 /* We're not interested in the MEM associated with a
9473 CONST_DOUBLE, so there's no need to traverse into this. */
9477 /* This is not a MEM. */
9479 }
9481 /* See if we've already seen this MEM. */
9484 {
9486 /* The modes of the two memory accesses are different. If
9487 this happens, something tricky is going on, and we just
9488 don't optimize accesses to this MEM. */
9492 }
9494 /* Resize the array, if necessary. */
9496 {
9499 else
9505 }
9507 /* Actually insert the MEM. */
9509 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
9510 because we can't put it in a register. We still store it in the
9511 table, though, so that if we see the same address later, but in a
9512 non-BLK mode, we'll not think we can optimize it at that point. */
9518 }
9520 /* Like load_mems, but also ensures that SET_IN_LOOP,
9521 MAY_NOT_OPTIMIZE, REG_SINGLE_USAGE, and INSN_COUNT have the correct
9522 values after load_mems. */
9524 static void
9526 insn_count)
9527 rtx scan_start;
9528 rtx end;
9529 rtx loop_top;
9530 rtx start;
9532 {
9537 /* Recalculate set_in_loop and friends since load_mems may have
9538 created new registers. */
9540 {
9548 {
9549 /* Grow all the arrays. */
9554 }
9555 /* Clear the arrays */
9565 {
9568 }
9570 #ifdef AVOID_CCMODE_COPIES
9571 /* Don't try to move insns which set CC registers if we should not
9572 create CCmode register copies. */
9576 #endif
9578 /* Set n_times_set for the new registers. */
9582 }
9583 }
9585 /* Move MEMs into registers for the duration of the loop. SCAN_START
9586 is the first instruction in the loop (as it is executed). The
9587 other parameters are as for next_insn_in_loop. */
9589 static void
9591 rtx scan_start;
9592 rtx end;
9593 rtx loop_top;
9594 rtx start;
9595 {
9598 rtx p;
9603 {
9604 /* Nonzero if the next instruction may never be executed. */
9607 /* Check to see if it's possible that some instructions in the
9608 loop are never executed. */
9612 {
9616 /* If we enter the loop in the middle, and scan
9617 around to the beginning, don't set maybe_never
9618 for that. This must be an unconditional jump,
9619 otherwise the code at the top of the loop might
9620 never be executed. Unconditional jumps are
9621 followed a by barrier then loop end. */
9626 {
9628 /* Something complicated. */
9630 else
9631 /* If there are any more instructions in the loop, they
9632 might not be reached. */
9634 }
9637 }
9639 /* Actually move the MEMs. */
9641 {
9643 rtx reg;
9645 rtx mem_list_entry;
9649 /* There's no telling whether or not MEM is modified. */
9652 /* Go through the MEMs written to in the loop to see if this
9653 one is aliased by one of them. */
9656 {
9661 {
9662 /* MEM is indeed aliased by this store. */
9665 }
9667 }
9669 /* If this MEM is written to, we must be sure that there
9670 are no reads from another MEM that aliases this one. */
9672 {
9676 {
9680 VOIDmode,
9682 rtx_varies_p))
9683 {
9684 /* It's not safe to hoist loop_mems[i] out of
9685 the loop because writes to it might not be
9686 seen by reads from loop_mems[j]. */
9689 }
9690 }
9691 }
9694 /* We can't access the MEM outside the loop; it might
9695 cause a trap that wouldn't have happened otherwise. */
9699 /* We thought we were going to lift this MEM out of the
9700 loop, but later discovered that we could not. */
9703 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
9704 order to keep scan_loop from moving stores to this MEM
9705 out of the loop just because this REG is neither a
9706 user-variable nor used in the loop test. */
9711 /* Now, replace all references to the MEM with the
9712 corresponding pesudos. */
9716 {
9717 rtx_and_int ri;
9721 }
9724 /* We couldn't replace all occurrences of the MEM. */
9726 else
9727 {
9728 rtx set;
9730 /* Load the memory immediately before START, which is
9731 the NOTE_LOOP_BEG. */
9736 {
9738 {
9739 /* We must compute the former
9740 right-after-the-end label before we insert
9741 the new one. */
9745 }
9747 /* Store the memory immediately after END, which is
9748 the NOTE_LOOP_END. */
9751 }
9754 {
9759 }
9760 }
9761 }
9762 }
9765 {
9766 /* Now, we need to replace all references to the previous exit
9767 label with the new one. */
9768 rtx_pair rr;
9773 {
9776 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9777 field. This is not handled by for_each_rtx because it doesn't
9778 handle unprinted ('0') fields. We need to update JUMP_LABEL
9779 because the immediately following unroll pass will use it.
9780 replace_label would not work anyways, because that only handles
9781 LABEL_REFs. */
9784 }
9785 }
9786 }
9788 /* Replace MEM with its associated pseudo register. This function is
9789 called from load_mems via for_each_rtx. DATA is actually an
9790 rtx_and_int * describing the instruction currently being scanned
9791 and the MEM we are currently replacing. */
9793 static int
9797 {
9799 rtx insn;
9807 {
9812 /* We're not interested in the MEM associated with a
9813 CONST_DOUBLE, so there's no need to traverse into one. */
9817 /* This is not a MEM. */
9819 }
9825 /* This is not the MEM we are currently replacing. */
9830 /* Actually replace the MEM. */
9834 }
9836 /* Replace occurrences of the old exit label for the loop with the new
9837 one. DATA is an rtx_pair containing the old and new labels,
9838 respectively. */
9840 static int
9844 {
9863 }