| blob | c7165e54ed70bc205ef8d6b9e18b4be6ebb0bb87 |
1 /* Perform various loop optimizations, including strength reduction.
2 Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 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. */
61 /* Not really meaningful values, but at least something. */
62 #ifndef SIMULTANEOUS_PREFETCHES
63 #define SIMULTANEOUS_PREFETCHES 3
64 #endif
65 #ifndef PREFETCH_BLOCK
66 #define PREFETCH_BLOCK 32
67 #endif
68 #ifndef HAVE_prefetch
69 #define HAVE_prefetch 0
70 #define CODE_FOR_prefetch 0
71 #define gen_prefetch(a,b,c) (abort(), NULL_RTX)
72 #endif
74 /* Give up the prefetch optimizations once we exceed a given threshhold.
75 It is unlikely that we would be able to optimize something in a loop
76 with so many detected prefetches. */
77 #define MAX_PREFETCHES 100
78 /* The number of prefetch blocks that are beneficial to fetch at once before
79 a loop with a known (and low) iteration count. */
80 #define PREFETCH_BLOCKS_BEFORE_LOOP_MAX 6
81 /* For very tiny loops it is not worthwhile to prefetch even before the loop,
82 since it is likely that the data are already in the cache. */
83 #define PREFETCH_BLOCKS_BEFORE_LOOP_MIN 2
85 /* Parameterize some prefetch heuristics so they can be turned on and off
86 easily for performance testing on new architectures. These can be
87 defined in target-dependent files. */
89 /* Prefetch is worthwhile only when loads/stores are dense. */
90 #ifndef PREFETCH_ONLY_DENSE_MEM
91 #define PREFETCH_ONLY_DENSE_MEM 1
92 #endif
94 /* Define what we mean by "dense" loads and stores; This value divided by 256
95 is the minimum percentage of memory references that worth prefetching. */
96 #ifndef PREFETCH_DENSE_MEM
97 #define PREFETCH_DENSE_MEM 220
98 #endif
100 /* Do not prefetch for a loop whose iteration count is known to be low. */
101 #ifndef PREFETCH_NO_LOW_LOOPCNT
102 #define PREFETCH_NO_LOW_LOOPCNT 1
103 #endif
105 /* Define what we mean by a "low" iteration count. */
106 #ifndef PREFETCH_LOW_LOOPCNT
107 #define PREFETCH_LOW_LOOPCNT 32
108 #endif
110 /* Do not prefetch for a loop that contains a function call; such a loop is
111 probably not an internal loop. */
112 #ifndef PREFETCH_NO_CALL
113 #define PREFETCH_NO_CALL 1
114 #endif
116 /* Do not prefetch accesses with an extreme stride. */
117 #ifndef PREFETCH_NO_EXTREME_STRIDE
118 #define PREFETCH_NO_EXTREME_STRIDE 1
119 #endif
121 /* Define what we mean by an "extreme" stride. */
122 #ifndef PREFETCH_EXTREME_STRIDE
123 #define PREFETCH_EXTREME_STRIDE 4096
124 #endif
126 /* Define a limit to how far apart indices can be and still be merged
127 into a single prefetch. */
128 #ifndef PREFETCH_EXTREME_DIFFERENCE
129 #define PREFETCH_EXTREME_DIFFERENCE 4096
130 #endif
132 /* Issue prefetch instructions before the loop to fetch data to be used
133 in the first few loop iterations. */
134 #ifndef PREFETCH_BEFORE_LOOP
135 #define PREFETCH_BEFORE_LOOP 1
136 #endif
138 /* Do not handle reversed order prefetches (negative stride). */
139 #ifndef PREFETCH_NO_REVERSE_ORDER
140 #define PREFETCH_NO_REVERSE_ORDER 1
141 #endif
143 /* Prefetch even if the GIV is in conditional code. */
144 #ifndef PREFETCH_CONDITIONAL
145 #define PREFETCH_CONDITIONAL 1
146 #endif
148 #define LOOP_REG_LIFETIME(LOOP, REGNO) \
149 ((REGNO_LAST_LUID (REGNO) - REGNO_FIRST_LUID (REGNO)))
151 #define LOOP_REG_GLOBAL_P(LOOP, REGNO) \
152 ((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
153 || REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start)))
155 #define LOOP_REGNO_NREGS(REGNO, SET_DEST) \
156 ((REGNO) < FIRST_PSEUDO_REGISTER \
157 ? (int) HARD_REGNO_NREGS ((REGNO), GET_MODE (SET_DEST)) : 1)
160 /* Vector mapping INSN_UIDs to luids.
161 The luids are like uids but increase monotonically always.
162 We use them to see whether a jump comes from outside a given loop. */
166 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
167 number the insn is contained in. */
171 /* 1 + largest uid of any insn. */
175 /* Number of loops detected in current function. Used as index to the
176 next few tables. */
180 /* Bound on pseudo register number before loop optimization.
181 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
184 /* The value to pass to the next call of reg_scan_update. */
186 \f
187 /* During the analysis of a loop, a chain of `struct movable's
188 is made to record all the movable insns found.
189 Then the entire chain can be scanned to decide which to move. */
191 struct movable
192 {
197 of any registers used within the LIBCALL. */
199 that must be moved with this one. */
202 may be adjusted when matching movables
203 that load the same value are found. */
205 including other movables that force this
206 or match this one. */
210 /* If PARTIAL is 1, GLOBAL means something different:
211 that the reg is live outside the range from where it is set
212 to the following label. */
216 In particular, moving it does not make it
217 invariant. */
219 load SRC, rather than copying INSN. */
221 first insn of a consecutive sets group. */
224 that we should avoid changing when clearing
225 the rest of the reg. */
229 };
234 /* Forward declarations. */
249 #if 0
251 #endif
281 rtx *));
364 {
365 rtx r1;
366 rtx r2;
370 {
371 rtx match;
372 rtx replacement;
373 rtx insn;
376 /* Nonzero iff INSN is between START and END, inclusive. */
377 #define INSN_IN_RANGE_P(INSN, START, END) \
378 (INSN_UID (INSN) < max_uid_for_loop \
379 && INSN_LUID (INSN) >= INSN_LUID (START) \
380 && INSN_LUID (INSN) <= INSN_LUID (END))
382 /* Indirect_jump_in_function is computed once per function. */
390 rtx));
391 \f
392 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
393 copy the value of the strength reduced giv to its original register. */
396 /* Cost of using a register, to normalize the benefits of a giv. */
399 void
401 {
407 }
408 \f
409 /* Compute the mapping from uids to luids.
410 LUIDs are numbers assigned to insns, like uids,
411 except that luids increase monotonically through the code.
412 Start at insn START and stop just before END. Assign LUIDs
413 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
414 static int
418 {
420 rtx insn;
423 {
426 /* Don't assign luids to line-number NOTEs, so that the distance in
427 luids between two insns is not affected by -g. */
431 else
432 /* Give a line number note the same luid as preceding insn. */
434 }
436 }
437 \f
438 /* Entry point of this file. Perform loop optimization
439 on the current function. F is the first insn of the function
440 and DUMPFILE is a stream for output of a trace of actions taken
441 (or 0 if none should be output). */
443 void
445 /* f is the first instruction of a chain of insns for one function */
446 rtx f;
449 {
450 rtx insn;
465 /* Count the number of loops. */
469 {
472 max_loop_num++;
473 }
475 /* Don't waste time if no loops. */
481 /* Get size to use for tables indexed by uids.
482 Leave some space for labels allocated by find_and_verify_loops. */
489 /* Allocate storage for array of loops. */
493 /* Find and process each loop.
494 First, find them, and record them in order of their beginnings. */
497 /* Allocate and initialize auxiliary loop information. */
502 /* Now find all register lifetimes. This must be done after
503 find_and_verify_loops, because it might reorder the insns in the
504 function. */
507 /* This must occur after reg_scan so that registers created by gcse
508 will have entries in the register tables.
510 We could have added a call to reg_scan after gcse_main in toplev.c,
511 but moving this call to init_alias_analysis is more efficient. */
514 /* See if we went too far. Note that get_max_uid already returns
515 one more that the maximum uid of all insn. */
518 /* Now reset it to the actual size we need. See above. */
521 /* find_and_verify_loops has already called compute_luids, but it
522 might have rearranged code afterwards, so we need to recompute
523 the luids now. */
526 /* Don't leave gaps in uid_luid for insns that have been
527 deleted. It is possible that the first or last insn
528 using some register has been deleted by cross-jumping.
529 Make sure that uid_luid for that former insn's uid
530 points to the general area where that insn used to be. */
532 {
536 }
541 /* Determine if the function has indirect jump. On some systems
542 this prevents low overhead loop instructions from being used. */
545 /* Now scan the loops, last ones first, since this means inner ones are done
546 before outer ones. */
548 {
553 }
557 /* Clean up. */
562 }
563 \f
564 /* Returns the next insn, in execution order, after INSN. START and
565 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
566 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
567 insn-stream; it is used with loops that are entered near the
568 bottom. */
570 static rtx
573 rtx insn;
574 {
578 {
580 /* Go to the top of the loop, and continue there. */
582 else
583 /* We're done. */
585 }
588 /* We're done. */
592 }
594 /* Optimize one loop described by LOOP. */
596 /* ??? Could also move memory writes out of loops if the destination address
597 is invariant, the source is invariant, the memory write is not volatile,
598 and if we can prove that no read inside the loop can read this address
599 before the write occurs. If there is a read of this address after the
600 write, then we can also mark the memory read as invariant. */
602 static void
606 {
612 rtx p;
613 /* 1 if we are scanning insns that could be executed zero times. */
615 /* 1 if we are scanning insns that might never be executed
616 due to a subroutine call which might exit before they are reached. */
618 /* Number of insns in the loop. */
622 /* The SET from an insn, if it is the only SET in the insn. */
624 /* Chain describing insns movable in current loop. */
626 /* Ratio of extra register life span we can justify
627 for saving an instruction. More if loop doesn't call subroutines
628 since in that case saving an insn makes more difference
629 and more registers are available. */
631 /* Nonzero if we are scanning instructions in a sub-loop. */
640 /* Determine whether this loop starts with a jump down to a test at
641 the end. This will occur for a small number of loops with a test
642 that is too complex to duplicate in front of the loop.
644 We search for the first insn or label in the loop, skipping NOTEs.
645 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
646 (because we might have a loop executed only once that contains a
647 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
648 (in case we have a degenerate loop).
650 Note that if we mistakenly think that a loop is entered at the top
651 when, in fact, it is entered at the exit test, the only effect will be
652 slightly poorer optimization. Making the opposite error can generate
653 incorrect code. Since very few loops now start with a jump to the
654 exit test, the code here to detect that case is very conservative. */
657 p != loop_end
663 ;
667 /* If loop end is the end of the current function, then emit a
668 NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy
669 note insn. This is the position we use when sinking insns out of
670 the loop. */
673 else
676 /* Set up variables describing this loop. */
680 /* If loop has a jump before the first label,
681 the true entry is the target of that jump.
682 Start scan from there.
683 But record in LOOP->TOP the place where the end-test jumps
684 back to so we can scan that after the end of the loop. */
686 /* Loop entry must be unconditional jump (and not a RETURN) */
689 /* Check to see whether the jump actually
690 jumps out of the loop (meaning it's no loop).
691 This case can happen for things like
692 do {..} while (0). If this label was generated previously
693 by loop, we can't tell anything about it and have to reject
694 the loop. */
696 {
699 }
701 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
702 as required by loop_reg_used_before_p. So skip such loops. (This
703 test may never be true, but it's best to play it safe.)
705 Also, skip loops where we do not start scanning at a label. This
706 test also rejects loops starting with a JUMP_INSN that failed the
707 test above. */
711 {
716 }
718 /* Allocate extra space for REGs that might be created by load_mems.
719 We allocate a little extra slop as well, in the hopes that we
720 won't have to reallocate the regs array. */
725 {
731 }
733 /* Scan through the loop finding insns that are safe to move.
734 Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
735 this reg will be considered invariant for subsequent insns.
736 We consider whether subsequent insns use the reg
737 in deciding whether it is worth actually moving.
739 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
740 and therefore it is possible that the insns we are scanning
741 would never be executed. At such times, we must make sure
742 that it is safe to execute the insn once instead of zero times.
743 When MAYBE_NEVER is 0, all insns will be executed at least once
744 so that is not a problem. */
749 {
751 in_libcall--;
753 {
756 in_libcall++;
760 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
762 #endif
764 {
771 /* Figure out what to use as a source of this insn. If a
772 REG_EQUIV note is given or if a REG_EQUAL note with a
773 constant operand is specified, use it as the source and
774 mark that we should move this insn by calling
775 emit_move_insn rather that duplicating the insn.
777 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL
778 note is present. */
782 else
783 {
788 {
790 /* A libcall block can use regs that don't appear in
791 the equivalent expression. To move the libcall,
792 we must move those regs too. */
794 }
795 }
797 /* For parallels, add any possible uses to the dependencies, as
798 we can't move the insn without resolving them first. */
800 {
802 {
805 dependencies
807 dependencies);
808 }
809 }
811 /* Don't try to optimize a register that was made
812 by loop-optimization for an inner loop.
813 We don't know its life-span, so we can't compute
814 the benefit. */
816 ;
818 than the one where it is set (meaning that
819 something after this point in the loop might
820 depend on its value before the set). */
822 /* And the set is not guaranteed to be executed once
823 the loop starts, or the value before the set is
824 needed before the set occurs...
826 ??? Note we have quadratic behavior here, mitigated
827 by the fact that the previous test will often fail for
828 large loops. Rather than re-scanning the entire loop
829 each time for register usage, we should build tables
830 of the register usage and use them here instead. */
831 && (maybe_never
833 /* It is unsafe to move the set.
835 This code used to consider it OK to move a set of a variable
836 which was not created by the user and not used in an exit
837 test.
838 That behavior is incorrect and was removed. */
839 ;
842 || (tem2
845 || (tem1
846 = consec_sets_invariant_p
849 p)))
850 /* If the insn can cause a trap (such as divide by zero),
851 can't move it unless it's guaranteed to be executed
852 once loop is entered. Even a function call might
853 prevent the trap insn from being reached
854 (since it might exit!) */
857 {
861 /* A potential lossage is where we have a case where two insns
862 can be combined as long as they are both in the loop, but
863 we move one of them outside the loop. For large loops,
864 this can lose. The most common case of this is the address
865 of a function being called.
867 Therefore, if this register is marked as being used
868 exactly once if we are in a loop with calls
869 (a "large loop"), see if we can replace the usage of
870 this register with the source of this SET. If we can,
871 delete this insn.
873 Don't do this if P has a REG_RETVAL note or if we have
874 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
886 && (! SMALL_REGISTER_CLASSES
890 /* This test is not redundant; SET_SRC (set) might be
891 a call-clobbered register and the life of REGNO
892 might span a call. */
899 {
900 /* Replace any usage in a REG_EQUAL note. Must copy
901 the new source, so that we don't get rtx sharing
902 between the SET_SOURCE and REG_NOTES of insn p. */
904 = (replace_rtx
910 i++)
913 }
922 m->consec
932 /* Set M->cond if either loop_invariant_p
933 or consec_sets_invariant_p returned 2
934 (only conditionally invariant). */
944 /* Add M to the end of the chain MOVABLES. */
948 {
949 /* It is possible for the first instruction to have a
950 REG_EQUAL note but a non-invariant SET_SRC, so we must
951 remember the status of the first instruction in case
952 the last instruction doesn't have a REG_EQUAL note. */
955 /* Skip this insn, not checking REG_LIBCALL notes. */
957 /* Skip the consecutive insns, if there are any. */
959 /* Back up to the last insn of the consecutive group. */
962 /* We must now reset m->move_insn, m->is_equiv, and
963 possibly m->set_src to correspond to the effects of
964 all the insns. */
968 else
969 {
973 else
976 }
977 m->is_equiv
979 }
980 }
981 /* If this register is always set within a STRICT_LOW_PART
982 or set to zero, then its high bytes are constant.
983 So clear them outside the loop and within the loop
984 just load the low bytes.
985 We must check that the machine has an instruction to do so.
986 Also, if the value loaded into the register
987 depends on the same register, this cannot be done. */
997 {
1000 {
1014 /* If the insn may not be executed on some cycles,
1015 we can't clear the whole reg; clear just high part.
1016 Not even if the reg is used only within this loop.
1017 Consider this:
1018 while (1)
1019 while (s != t) {
1020 if (foo ()) x = *s;
1021 use (x);
1022 }
1023 Clearing x before the inner loop could clobber a value
1024 being saved from the last time around the outer loop.
1025 However, if the reg is not used outside this loop
1026 and all uses of the register are in the same
1027 basic block as the store, there is no problem.
1029 If this insn was made by loop, we don't know its
1030 INSN_LUID and hence must make a conservative
1031 assumption. */
1034 || (labels_in_range_p
1038 else
1047 i++)
1049 /* Add M to the end of the chain MOVABLES. */
1051 }
1052 }
1053 }
1054 }
1055 /* Past a call insn, we get to insns which might not be executed
1056 because the call might exit. This matters for insns that trap.
1057 Constant and pure call insns always return, so they don't count. */
1060 /* Past a label or a jump, we get to insns for which we
1061 can't count on whether or how many times they will be
1062 executed during each iteration. Therefore, we can
1063 only move out sets of trivial variables
1064 (those not used after the loop). */
1065 /* Similar code appears twice in strength_reduce. */
1067 /* If we enter the loop in the middle, and scan around to the
1068 beginning, don't set maybe_never for that. This must be an
1069 unconditional jump, otherwise the code at the top of the
1070 loop might never be executed. Unconditional jumps are
1071 followed by a barrier then the loop_end. */
1077 {
1078 /* At the virtual top of a converted loop, insns are again known to
1079 be executed: logically, the loop begins here even though the exit
1080 code has been duplicated. */
1084 loop_depth++;
1086 loop_depth--;
1087 }
1088 }
1090 /* If one movable subsumes another, ignore that other. */
1094 /* For each movable insn, see if the reg that it loads
1095 leads when it dies right into another conditionally movable insn.
1096 If so, record that the second insn "forces" the first one,
1097 since the second can be moved only if the first is. */
1101 /* See if there are multiple movable insns that load the same value.
1102 If there are, make all but the first point at the first one
1103 through the `match' field, and add the priorities of them
1104 all together as the priority of the first. */
1108 /* Now consider each movable insn to decide whether it is worth moving.
1109 Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
1111 Generally this increases code size, so do not move moveables when
1112 optimizing for code size. */
1115 {
1118 /* Recalculate regs->array if move_movables has created new
1119 registers. */
1121 {
1127 ;
1132 }
1133 }
1135 /* Now candidates that still are negative are those not moved.
1136 Change regs->array[I].set_in_loop to indicate that those are not actually
1137 invariant. */
1142 /* Now that we've moved some things out of the loop, we might be able to
1143 hoist even more memory references. */
1146 /* Recalculate regs->array if load_mems has created new registers. */
1154 ;
1161 {
1163 /* Ensure our label doesn't go away. */
1174 }
1177 /* The movable information is required for strength reduction. */
1183 }
1184 \f
1185 /* Add elements to *OUTPUT to record all the pseudo-regs
1186 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1188 void
1192 {
1200 {
1218 }
1222 {
1226 {
1235 }
1236 }
1237 }
1238 \f
1239 /* Check what regs are referred to in the libcall block ending with INSN,
1240 aside from those mentioned in the equivalent value.
1241 If there are none, return 0.
1242 If there are one or more, return an EXPR_LIST containing all of them. */
1244 rtx
1247 {
1252 /* First, find all the regs used in the libcall block
1253 that are not mentioned as inputs to the result. */
1256 {
1261 }
1264 }
1265 \f
1266 /* Return 1 if all uses of REG
1267 are between INSN and the end of the basic block. */
1269 static int
1272 {
1274 rtx p;
1279 /* Search this basic block for the already recorded last use of the reg. */
1281 {
1283 {
1289 /* Ordinary insn: if this is the last use, we win. */
1295 /* Jump insn: if this is the last use, we win. */
1298 /* Otherwise, it's the end of the basic block, so we lose. */
1303 /* It's the end of the basic block, so we lose. */
1308 }
1309 }
1311 /* The "last use" that was recorded can't be found after the first
1312 use. This can happen when the last use was deleted while
1313 processing an inner loop, this inner loop was then completely
1314 unrolled, and the outer loop is always exited after the inner loop,
1315 so that everything after the first use becomes a single basic block. */
1317 }
1318 \f
1319 /* Compute the benefit of eliminating the insns in the block whose
1320 last insn is LAST. This may be a group of insns used to compute a
1321 value directly or can contain a library call. */
1323 static int
1325 rtx last;
1326 {
1327 rtx insn;
1332 {
1335 routine. */
1339 benefit++;
1340 }
1343 }
1344 \f
1345 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1347 static rtx
1349 rtx insn;
1351 {
1353 {
1354 rtx temp;
1356 /* If first insn of libcall sequence, skip to end. */
1357 /* Do this at start of loop, since INSN is guaranteed to
1358 be an insn here. */
1363 do
1366 }
1369 }
1371 /* Ignore any movable whose insn falls within a libcall
1372 which is part of another movable.
1373 We make use of the fact that the movable for the libcall value
1374 was made later and so appears later on the chain. */
1376 static void
1379 {
1383 {
1384 /* Is this a movable for the value of a libcall? */
1387 {
1388 rtx insn;
1389 /* Check for earlier movables inside that range,
1390 and mark them invalid. We cannot use LUIDs here because
1391 insns created by loop.c for prior loops don't have LUIDs.
1392 Rather than reject all such insns from movables, we just
1393 explicitly check each insn in the libcall (since invariant
1394 libcalls aren't that common). */
1399 }
1400 }
1401 }
1403 /* For each movable insn, see if the reg that it loads
1404 leads when it dies right into another conditionally movable insn.
1405 If so, record that the second insn "forces" the first one,
1406 since the second can be moved only if the first is. */
1408 static void
1411 {
1415 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1417 {
1420 /* ??? Could this be a bug? What if CSE caused the
1421 register of M1 to be used after this insn?
1422 Since CSE does not update regno_last_uid,
1423 this insn M->insn might not be where it dies.
1424 But very likely this doesn't matter; what matters is
1425 that M's reg is computed from M1's reg. */
1430 /* If m->consec, m->set_src isn't valid. */
1434 /* Increase the priority of the moving the first insn
1435 since it permits the second to be moved as well. */
1437 {
1441 }
1442 }
1443 }
1444 \f
1445 /* Find invariant expressions that are equal and can be combined into
1446 one register. */
1448 static void
1452 {
1457 /* Regs that are set more than once are not allowed to match
1458 or be matched. I'm no longer sure why not. */
1459 /* Only pseudo registers are allowed to match or be matched,
1460 since move_movables does not validate the change. */
1461 /* Perhaps testing m->consec_sets would be more appropriate here? */
1467 {
1474 /* We want later insns to match the first one. Don't make the first
1475 one match any later ones. So start this loop at m->next. */
1480 /* A reg used outside the loop mustn't be eliminated. */
1482 /* A reg used for zero-extending mustn't be eliminated. */
1485 ||
1486 (
1487 /* Can combine regs with different modes loaded from the
1488 same constant only if the modes are the same or
1489 if both are integer modes with M wider or the same
1490 width as M1. The check for integer is redundant, but
1491 safe, since the only case of differing destination
1492 modes with equal sources is when both sources are
1493 VOIDmode, i.e., CONST_INT. */
1499 /* See if the source of M1 says it matches M. */
1506 {
1512 }
1513 }
1515 /* Now combine the regs used for zero-extension.
1516 This can be done for those not marked `global'
1517 provided their lives don't overlap. */
1521 {
1524 /* Combine all the registers for extension from mode MODE.
1525 Don't combine any that are used outside this loop. */
1529 {
1536 {
1537 /* First one: don't check for overlap, just record it. */
1540 }
1542 /* Make sure they extend to the same mode.
1543 (Almost always true.) */
1547 /* We already have one: check for overlap with those
1548 already combined together. */
1555 /* No overlap: we can combine this with the others. */
1561 overlap:
1562 ;
1563 }
1564 }
1566 /* Clean up. */
1568 }
1570 /* Returns the number of movable instructions in LOOP that were not
1571 moved outside the loop. */
1573 static int
1576 {
1585 }
1587 \f
1588 /* Return 1 if regs X and Y will become the same if moved. */
1590 static int
1594 {
1611 }
1613 /* Return 1 if X and Y are identical-looking rtx's.
1614 This is the Lisp function EQUAL for rtx arguments.
1616 If two registers are matching movables or a movable register and an
1617 equivalent constant, consider them equal. */
1619 static int
1624 {
1638 /* If we have a register and a constant, they may sometimes be
1639 equal. */
1642 {
1647 }
1650 {
1655 }
1657 /* Otherwise, rtx's of different codes cannot be equal. */
1661 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1662 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1667 /* These three types of rtx's can be compared nonrecursively. */
1676 /* Compare the elements. If any pair of corresponding elements
1677 fail to match, return 0 for the whole things. */
1681 {
1683 {
1695 /* Two vectors must have the same length. */
1699 /* And the corresponding elements must match. */
1718 /* These are just backpointers, so they don't matter. */
1724 /* It is believed that rtx's at this level will never
1725 contain anything but integers and other rtx's,
1726 except for within LABEL_REFs and SYMBOL_REFs. */
1729 }
1730 }
1732 }
1733 \f
1734 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1735 insns in INSNS which use the reference. LABEL_NUSES for CODE_LABEL
1736 references is incremented once for each added note. */
1738 static void
1740 rtx x;
1741 rtx insns;
1742 {
1746 rtx insn;
1749 {
1750 /* This code used to ignore labels that referred to dispatch tables to
1751 avoid flow generating (slighly) worse code.
1753 We no longer ignore such label references (see LABEL_REF handling in
1754 mark_jump_label for additional information). */
1757 {
1762 }
1763 }
1767 {
1773 }
1774 }
1775 \f
1776 /* Scan MOVABLES, and move the insns that deserve to be moved.
1777 If two matching movables are combined, replace one reg with the
1778 other throughout. */
1780 static void
1786 {
1791 rtx p;
1794 /* Map of pseudo-register replacements to handle combining
1795 when we move several insns that load the same value
1796 into different pseudo-registers. */
1801 {
1802 /* Describe this movable insn. */
1805 {
1826 }
1828 /* Ignore the insn if it's already done (it matched something else).
1829 Otherwise, see if it is now safe to move. */
1841 {
1843 rtx p;
1846 /* We have an insn that is safe to move.
1847 Compute its desirability. */
1858 /* An insn MUST be moved if we already moved something else
1859 which is safe only if this one is moved too: that is,
1860 if already_moved[REGNO] is nonzero. */
1862 /* An insn is desirable to move if the new lifetime of the
1863 register is no more than THRESHOLD times the old lifetime.
1864 If it's not desirable, it means the loop is so big
1865 that moving won't speed things up much,
1866 and it is liable to make register usage worse. */
1868 /* It is also desirable to move if it can be moved at no
1869 extra cost because something else was already moved. */
1872 || flag_move_all_movables
1877 {
1882 /* Now move the insns that set the reg. */
1885 {
1888 /* Find the end of this chain of matching regs.
1889 Thus, we load each reg in the chain from that one reg.
1890 And that reg is loaded with 0 directly,
1891 since it has ->match == 0. */
1897 /* Mark the moved, invariant reg as being allowed to
1898 share a hard reg with the other matching invariant. */
1902 regs_may_share
1905 regs_may_share));
1913 }
1914 /* If we are to re-generate the item being moved with a
1915 new move insn, first delete what we have and then emit
1916 the move insn before the loop. */
1918 {
1922 {
1923 /* If this is the first insn of a library call sequence,
1924 something is very wrong. */
1929 /* If this is the last insn of a libcall sequence, then
1930 delete every insn in the sequence except the last.
1931 The last insn is handled in the normal manner. */
1934 {
1938 }
1943 /* simplify_giv_expr expects that it can walk the insns
1944 at m->insn forwards and see this old sequence we are
1945 tossing here. delete_insn does preserve the next
1946 pointers, but when we skip over a NOTE we must fix
1947 it up. Otherwise that code walks into the non-deleted
1948 insn stream. */
1951 }
1969 /* The more regs we move, the less we like moving them. */
1971 }
1972 else
1973 {
1975 {
1978 /* If first insn of libcall sequence, skip to end. */
1979 /* Do this at start of loop, since p is guaranteed to
1980 be an insn here. */
1985 /* If last insn of libcall sequence, move all
1986 insns except the last before the loop. The last
1987 insn is handled in the normal manner. */
1990 {
1998 {
1999 rtx body;
2000 rtx n;
2001 rtx next;
2008 /* Find the next insn after TEMP,
2009 not counting USE or NOTE insns. */
2017 /* If that is the call, this may be the insn
2018 that loads the function address.
2020 Extract the function address from the insn
2021 that loads it into a register.
2022 If this insn was cse'd, we get incorrect code.
2024 So emit a new move insn that copies the
2025 function address into the register that the
2026 call insn will use. flow.c will delete any
2027 redundant stores that we have created. */
2032 NULL_RTX)))
2033 {
2039 }
2040 /* We have the call insn.
2041 If it uses the register we suspect it might,
2042 load it with the correct address directly. */
2047 gen_move_insn
2051 {
2053 /* Because the USAGE information potentially
2054 contains objects other than hard registers
2055 we need to copy it. */
2059 }
2060 else
2069 }
2072 }
2074 {
2075 /* P sets REG to zero; but we should clear only
2076 the bits that are not covered by the mode
2077 m->savemode. */
2079 rtx sequence;
2080 rtx tem;
2083 tem = expand_simple_binop
2096 }
2098 {
2100 /* Because the USAGE information potentially
2101 contains objects other than hard registers
2102 we need to copy it. */
2106 }
2108 {
2109 rtx seq;
2110 /* The SET_SRC might not be invariant, so we must
2111 use the REG_EQUAL note. */
2123 }
2124 else
2128 {
2132 /* If there is a REG_EQUAL note present whose value
2133 is not loop invariant, then delete it, since it
2134 may cause problems with later optimization passes.
2135 It is possible for cse to create such notes
2136 like this as a result of record_jump_cond. */
2141 }
2150 /* If library call, now fix the REG_NOTES that contain
2151 insn pointers, namely REG_LIBCALL on FIRST
2152 and REG_RETVAL on I1. */
2154 {
2158 }
2164 /* simplify_giv_expr expects that it can walk the insns
2165 at m->insn forwards and see this old sequence we are
2166 tossing here. delete_insn does preserve the next
2167 pointers, but when we skip over a NOTE we must fix
2168 it up. Otherwise that code walks into the non-deleted
2169 insn stream. */
2172 }
2174 /* The more regs we move, the less we like moving them. */
2176 }
2178 /* Any other movable that loads the same register
2179 MUST be moved. */
2182 /* This reg has been moved out of one loop. */
2185 /* The reg set here is now invariant. */
2187 {
2191 }
2195 /* Change the length-of-life info for the register
2196 to say it lives at least the full length of this loop.
2197 This will help guide optimizations in outer loops. */
2200 /* This is the old insn before all the moved insns.
2201 We can't use the moved insn because it is out of range
2202 in uid_luid. Only the old insns have luids. */
2207 /* Combine with this moved insn any other matching movables. */
2212 {
2213 rtx temp;
2215 /* Schedule the reg loaded by M1
2216 for replacement so that shares the reg of M.
2217 If the modes differ (only possible in restricted
2218 circumstances, make a SUBREG.
2220 Note this assumes that the target dependent files
2221 treat REG and SUBREG equally, including within
2222 GO_IF_LEGITIMATE_ADDRESS and in all the
2223 predicates since we never verify that replacing the
2224 original register with a SUBREG results in a
2225 recognizable insn. */
2228 else
2233 /* Get rid of the matching insn
2234 and prevent further processing of it. */
2237 /* if library call, delete all insns. */
2239 NULL_RTX)))
2241 else
2244 /* Any other movable that loads the same register
2245 MUST be moved. */
2248 /* The reg merged here is now invariant,
2249 if the reg it matches is invariant. */
2251 {
2255 i++)
2257 }
2258 }
2259 }
2262 }
2268 }
2273 /* Go through all the instructions in the loop, making
2274 all the register substitutions scheduled in REG_MAP. */
2278 {
2282 }
2284 /* Clean up. */
2287 }
2290 static void
2294 {
2297 else
2300 }
2303 static void
2306 {
2311 {
2314 }
2315 }
2316 \f
2317 #if 0
2318 /* Scan X and replace the address of any MEM in it with ADDR.
2319 REG is the address that MEM should have before the replacement. */
2321 static void
2324 {
2333 {
2345 /* Short cut for very common case. */
2350 /* Short cut for very common case. */
2355 /* If this MEM uses a reg other than the one we expected,
2356 something is wrong. */
2364 }
2368 {
2372 {
2376 }
2377 }
2378 }
2379 #endif
2380 \f
2381 /* Return the number of memory refs to addresses that vary
2382 in the rtx X. */
2384 static int
2387 rtx x;
2388 {
2399 {
2416 }
2421 {
2425 {
2429 }
2430 }
2432 }
2433 \f
2434 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2435 `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2436 `unknown_address_altered', `unknown_constant_address_altered', and
2437 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2438 list `store_mems' in LOOP. */
2440 static void
2443 {
2445 rtx insn;
2449 /* The label after END. Jumping here is just like falling off the
2450 end of the loop. We use next_nonnote_insn instead of next_label
2451 as a hedge against the (pathological) case where some actual insn
2452 might end up between the two. */
2471 /* If loop opts run twice, this was set on 1st pass for 2nd. */
2476 {
2478 {
2481 }
2482 }
2486 {
2488 {
2491 {
2493 /* Count number of loops contained in this one. */
2495 }
2502 {
2505 }
2515 {
2519 {
2524 {
2527 }
2528 else
2529 {
2532 }
2534 do
2535 {
2537 {
2539 {
2540 /* Something tricky. */
2543 }
2546 {
2547 /* A jump outside the current loop. */
2550 }
2551 }
2555 }
2557 }
2558 else
2559 {
2560 /* A return, or something tricky. */
2562 }
2563 }
2564 /* FALLTHRU */
2585 }
2586 }
2588 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2590 anywhere. */
2592 /* We don't want loads for MEMs moved to a location before the
2593 one at which their stack memory becomes allocated. (Note
2594 that this is not a problem for malloc, etc., since those
2595 require actual function calls. */
2596 && ! current_function_calls_alloca
2597 /* There are ways to leave the loop other than falling off the
2598 end. */
2604 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2605 that loop_invariant_p and load_mems can use true_dependence
2606 to determine what is really clobbered. */
2608 {
2611 loop_info->store_mems
2613 }
2615 {
2619 loop_info->store_mems
2621 }
2622 }
2623 \f
2624 /* Invalidate all loops containing LABEL. */
2626 static void
2628 rtx label;
2629 {
2633 }
2635 /* Scan the function looking for loops. Record the start and end of each loop.
2636 Also mark as invalid loops any loops that contain a setjmp or are branched
2637 to from outside the loop. */
2639 static void
2641 rtx f;
2643 {
2644 rtx insn;
2645 rtx label;
2655 /* If there are jumps to undefined labels,
2656 treat them as jumps out of any/all loops.
2657 This also avoids writing past end of tables when there are no loops. */
2660 /* Find boundaries of loops, mark which loops are contained within
2661 loops, and invalidate loops that have setjmp. */
2666 {
2669 {
2673 num_loops++;
2697 }
2701 {
2702 /* In this case, we must invalidate our current loop and any
2703 enclosing loop. */
2705 {
2711 }
2712 }
2714 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2715 enclosing loop, but this doesn't matter. */
2717 }
2719 /* Any loop containing a label used in an initializer must be invalidated,
2720 because it can be jumped into from anywhere. */
2724 /* Any loop containing a label used for an exception handler must be
2725 invalidated, because it can be jumped into from anywhere. */
2728 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2729 loop that it is not contained within, that loop is marked invalid.
2730 If any INSN or CALL_INSN uses a label's address, then the loop containing
2731 that label is marked invalid, because it could be jumped into from
2732 anywhere.
2734 Also look for blocks of code ending in an unconditional branch that
2735 exits the loop. If such a block is surrounded by a conditional
2736 branch around the block, move the block elsewhere (see below) and
2737 invert the jump to point to the code block. This may eliminate a
2738 label in our loop and will simplify processing by both us and a
2739 possible second cse pass. */
2743 {
2747 {
2751 }
2758 /* See if this is an unconditional branch outside the loop. */
2766 {
2767 rtx p;
2773 /* Go backwards until we reach the start of the loop, a label,
2774 or a JUMP_INSN. */
2781 ;
2783 /* Check for the case where we have a jump to an inner nested
2784 loop, and do not perform the optimization in that case. */
2787 {
2790 {
2795 }
2796 }
2798 /* Make sure that the target of P is within the current loop. */
2804 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2805 we have a block of code to try to move.
2807 We look backward and then forward from the target of INSN
2808 to find a BARRIER at the same loop depth as the target.
2809 If we find such a BARRIER, we make a new label for the start
2810 of the block, invert the jump in P and point it to that label,
2811 and move the block of code to the spot we found. */
2816 /* Just ignore jumps to labels that were never emitted.
2817 These always indicate compilation errors. */
2821 /* If it's not safe to move the sequence, then we
2822 mustn't try. */
2825 {
2826 rtx target
2830 rtx tmp;
2832 /* Search for possible garbage past the conditional jumps
2833 and look for the last barrier. */
2841 /* Don't move things inside a tablejump. */
2854 /* Don't move things inside a tablejump. */
2865 {
2869 /* Ensure our label doesn't go away. */
2872 /* Verify that uid_loop is large enough and that
2873 we can invert P. */
2875 {
2878 /* If no suitable BARRIER was found, create a suitable
2879 one before TARGET. Since TARGET is a fall through
2880 path, we'll need to insert a jump around our block
2881 and add a BARRIER before TARGET.
2883 This creates an extra unconditional jump outside
2884 the loop. However, the benefits of removing rarely
2885 executed instructions from inside the loop usually
2886 outweighs the cost of the extra unconditional jump
2887 outside the loop. */
2889 {
2890 rtx temp;
2897 }
2899 /* Include the BARRIER after INSN and copy the
2900 block after LOC. */
2905 /* All those insns are now in TARGET_LOOP. */
2911 /* The label jumped to by INSN is no longer a loop
2912 exit. Unless INSN does not have a label (e.g.,
2913 it is a RETURN insn), search loop->exit_labels
2914 to find its label_ref, and remove it. Also turn
2915 off LABEL_OUTSIDE_LOOP_P bit. */
2917 {
2919 r;
2922 {
2926 else
2929 }
2935 /* If we didn't find it, then something is
2936 wrong. */
2939 }
2941 /* P is now a jump outside the loop, so it must be put
2942 in loop->exit_labels, and marked as such.
2943 The easiest way to do this is to just call
2944 mark_loop_jump again for P. */
2947 /* If INSN now jumps to the insn after it,
2948 delete INSN. */
2953 }
2955 /* Continue the loop after where the conditional
2956 branch used to jump, since the only branch insn
2957 in the block (if it still remains) is an inter-loop
2958 branch and hence needs no processing. */
2964 /* This loop will be continued with NEXT_INSN (insn). */
2966 }
2967 }
2968 }
2969 }
2970 }
2972 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2973 loops it is contained in, mark the target loop invalid.
2975 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2977 static void
2979 rtx x;
2981 {
2987 {
2999 /* There could be a label reference in here. */
3011 /* This may refer to a LABEL_REF or SYMBOL_REF. */
3023 /* Link together all labels that branch outside the loop. This
3024 is used by final_[bg]iv_value and the loop unrolling code. Also
3025 mark this LABEL_REF so we know that this branch should predict
3026 false. */
3028 /* A check to make sure the label is not in an inner nested loop,
3029 since this does not count as a loop exit. */
3031 {
3036 }
3037 else
3041 {
3050 }
3052 /* If this is inside a loop, but not in the current loop or one enclosed
3053 by it, it invalidates at least one loop. */
3058 /* We must invalidate every nested loop containing the target of this
3059 label, except those that also contain the jump insn. */
3062 {
3063 /* Stop when we reach a loop that also contains the jump insn. */
3068 /* If we get here, we know we need to invalidate a loop. */
3075 }
3079 /* If this is not setting pc, ignore. */
3101 /* Strictly speaking this is not a jump into the loop, only a possible
3102 jump out of the loop. However, we have no way to link the destination
3103 of this jump onto the list of exit labels. To be safe we mark this
3104 loop and any containing loops as invalid. */
3106 {
3108 {
3114 }
3115 }
3117 }
3118 }
3119 \f
3120 /* Return nonzero if there is a label in the range from
3121 insn INSN to and including the insn whose luid is END
3122 INSN must have an assigned luid (i.e., it must not have
3123 been previously created by loop.c). */
3125 static int
3127 rtx insn;
3129 {
3131 {
3135 }
3138 }
3140 /* Record that a memory reference X is being set. */
3142 static void
3144 rtx x;
3145 rtx y ATTRIBUTE_UNUSED;
3147 {
3153 /* Count number of memory writes.
3154 This affects heuristics in strength_reduce. */
3157 /* BLKmode MEM means all memory is clobbered. */
3159 {
3162 else
3166 }
3170 }
3172 /* X is a value modified by an INSN that references a biv inside a loop
3173 exit test (ie, X is somehow related to the value of the biv). If X
3174 is a pseudo that is used more than once, then the biv is (effectively)
3175 used more than once. DATA is a pointer to a loop_regs structure. */
3177 static void
3179 rtx x;
3180 rtx y ATTRIBUTE_UNUSED;
3182 {
3197 /* If we do not have usage information, or if we know the register
3198 is used more than once, note that fact for check_dbra_loop. */
3203 }
3204 \f
3205 /* Return nonzero if the rtx X is invariant over the current loop.
3207 The value is 2 if we refer to something only conditionally invariant.
3209 A memory ref is invariant if it is not volatile and does not conflict
3210 with anything stored in `loop_info->store_mems'. */
3212 int
3215 rtx x;
3216 {
3223 rtx mem_list_entry;
3229 {
3237 /* A LABEL_REF is normally invariant, however, if we are unrolling
3238 loops, and this label is inside the loop, then it isn't invariant.
3239 This is because each unrolled copy of the loop body will have
3240 a copy of this label. If this was invariant, then an insn loading
3241 the address of this label into a register might get moved outside
3242 the loop, and then each loop body would end up using the same label.
3244 We don't know the loop bounds here though, so just fail for all
3245 labels. */
3248 else
3257 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3258 since the reg might be set by initialization within the loop. */
3269 /* Out-of-range regs can occur when we are called from unrolling.
3270 These have always been created by the unroller and are set in
3271 the loop, hence are never invariant. */
3282 /* Volatile memory references must be rejected. Do this before
3283 checking for read-only items, so that volatile read-only items
3284 will be rejected also. */
3288 /* See if there is any dependence between a store and this load. */
3291 {
3297 }
3299 /* It's not invalidated by a store in memory
3300 but we must still verify the address is invariant. */
3304 /* Don't mess with insns declared volatile. */
3311 }
3315 {
3317 {
3323 }
3325 {
3328 {
3334 }
3336 }
3337 }
3340 }
3341 \f
3342 /* Return nonzero if all the insns in the loop that set REG
3343 are INSN and the immediately following insns,
3344 and if each of those insns sets REG in an invariant way
3345 (not counting uses of REG in them).
3347 The value is 2 if some of these insns are only conditionally invariant.
3349 We assume that INSN itself is the first set of REG
3350 and that its source is invariant. */
3352 static int
3357 {
3361 rtx temp;
3362 /* Number of sets we have to insist on finding after INSN. */
3368 /* If N_SETS hit the limit, we can't rely on its value. */
3375 {
3377 rtx set;
3382 /* If library call, skip to end of it. */
3391 {
3396 {
3397 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3398 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3399 notes are OK. */
3405 }
3406 }
3408 count--;
3410 {
3413 }
3414 }
3417 /* If loop_invariant_p ever returned 2, we return 2. */
3419 }
3421 #if 0
3422 /* I don't think this condition is sufficient to allow INSN
3423 to be moved, so we no longer test it. */
3425 /* Return 1 if all insns in the basic block of INSN and following INSN
3426 that set REG are invariant according to TABLE. */
3428 static int
3432 {
3437 {
3446 {
3449 }
3450 }
3451 }
3453 \f
3454 /* Look at all uses (not sets) of registers in X. For each, if it is
3455 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3456 a different insn, set USAGE[REGNO] to const0_rtx. */
3458 static void
3461 rtx insn;
3462 rtx x;
3463 {
3475 {
3476 /* Don't count SET_DEST if it is a REG; otherwise count things
3477 in SET_DEST because if a register is partially modified, it won't
3478 show up as a potential movable so we don't care how USAGE is set
3479 for it. */
3483 }
3484 else
3486 {
3492 }
3493 }
3494 \f
3495 /* Count and record any set in X which is contained in INSN. Update
3496 REGS->array[I].MAY_NOT_OPTIMIZE and LAST_SET for any register I set
3497 in X. */
3499 static void
3504 {
3506 /* Don't move a reg that has an explicit clobber.
3507 It's not worth the pain to try to do it correctly. */
3511 {
3519 {
3523 {
3524 /* If this is the first setting of this reg
3525 in current basic block, and it was set before,
3526 it must be set in two basic blocks, so it cannot
3527 be moved out of the loop. */
3531 /* If this is not first setting in current basic block,
3532 see if reg was used in between previous one and this.
3533 If so, neither one can be moved. */
3540 }
3541 }
3542 }
3543 }
3544 \f
3545 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3546 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3547 contained in insn INSN is used by any insn that precedes INSN in
3548 cyclic order starting from the loop entry point.
3550 We don't want to use INSN_LUID here because if we restrict INSN to those
3551 that have a valid INSN_LUID, it means we cannot move an invariant out
3552 from an inner loop past two loops. */
3554 static int
3558 {
3560 rtx p;
3562 /* Scan forward checking for register usage. If we hit INSN, we
3563 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3565 {
3571 }
3574 }
3575 \f
3577 /* Information we collect about arrays that we might want to prefetch. */
3578 struct prefetch_info
3579 {
3583 index. */
3584 HOST_WIDE_INT index;
3586 iteration. */
3588 prefetch area in one iteration. */
3590 This is set only for loops with known
3591 iteration counts and is 0xffffffff
3592 otherwise. */
3596 };
3598 /* Data used by check_store function. */
3599 struct check_store_data
3600 {
3601 rtx mem_address;
3603 };
3609 /* Set mem_write when mem_address is found. Used as callback to
3610 note_stores. */
3611 static void
3615 {
3620 }
3621 \f
3622 /* Like rtx_equal_p, but attempts to swap commutative operands. This is
3623 important to get some addresses combined. Later more sophisticated
3624 transformations can be added when necessary.
3626 ??? Same trick with swapping operand is done at several other places.
3627 It can be nice to develop some common way to handle this. */
3629 static int
3632 {
3646 {
3651 }
3652 /* Compare the elements. If any pair of corresponding elements fails to
3653 match, return 0 for the whole thing. */
3657 {
3659 {
3671 /* Two vectors must have the same length. */
3675 /* And the corresponding elements must match. */
3693 /* These are just backpointers, so they don't matter. */
3699 /* It is believed that rtx's at this level will never
3700 contain anything but integers and other rtx's,
3701 except for within LABEL_REFs and SYMBOL_REFs. */
3704 }
3705 }
3707 }
3708 \f
3709 /* Remove constant addition value from the expression X (when present)
3710 and return it. */
3712 static HOST_WIDE_INT
3715 {
3719 /* Avoid clobbering a shared CONST expression. */
3721 {
3725 {
3728 }
3730 }
3733 {
3736 }
3738 /* For plus expression recurse on ourself. */
3740 {
3744 /* In case our parameter was constant, remove extra zero from the
3745 expression. */
3750 }
3753 }
3755 /* Attempt to identify accesses to arrays that are most likely to cause cache
3756 misses, and emit prefetch instructions a few prefetch blocks forward.
3758 To detect the arrays we use the GIV information that was collected by the
3759 strength reduction pass.
3761 The prefetch instructions are generated after the GIV information is done
3762 and before the strength reduction process. The new GIVs are injected into
3763 the strength reduction tables, so the prefetch addresses are optimized as
3764 well.
3766 GIVs are split into base address, stride, and constant addition values.
3767 GIVs with the same address, stride and close addition values are combined
3768 into a single prefetch. Also writes to GIVs are detected, so that prefetch
3769 for write instructions can be used for the block we write to, on machines
3770 that support write prefetches.
3772 Several heuristics are used to determine when to prefetch. They are
3773 controlled by defined symbols that can be overridden for each target. */
3775 static void
3778 {
3794 /* Consider only loops w/o calls. When a call is done, the loop is probably
3795 slow enough to read the memory. */
3797 {
3802 }
3804 /* Don't prefetch in loops known to have few iterations. */
3808 {
3813 }
3815 /* Search all induction variables and pick those interesting for the prefetch
3816 machinery. */
3818 {
3824 /* Expect all BIVs to be executed in each iteration. This makes our
3825 analysis more conservative. */
3827 {
3828 /* Discard non-constant additions that we can't handle well yet, and
3829 BIVs that are executed multiple times; such BIVs ought to be
3830 handled in the nested loop. We accept not_every_iteration BIVs,
3831 since these only result in larger strides and make our
3832 heuristics more conservative. */
3834 {
3836 {
3842 }
3844 }
3847 {
3849 {
3855 }
3857 }
3861 }
3867 {
3868 rtx address;
3869 rtx temp;
3878 /* See whether an induction variable is interesting to us and if
3879 not, report the reason. */
3883 /* We are interested only in constant stride memory references
3884 in order to be able to compute density easily. */
3888 else
3889 {
3892 {
3895 }
3897 /* On some targets, reversed order prefetches are not
3898 worthwhile. */
3902 /* Prefetch of accesses with an extreme stride might not be
3903 worthwhile, either. */
3908 /* Ignore GIVs with varying add values; we can't predict the
3909 value for the next iteration. */
3913 /* Ignore GIVs in the nested loops; they ought to have been
3914 handled already. */
3917 }
3920 {
3926 }
3928 /* Determine the pointer to the basic array we are examining. It is
3929 the sum of the BIV's initial value and the GIV's add_val. */
3939 /* When the GIV is not always executed, we might be better off by
3940 not dirtying the cache pages. */
3943 else
3944 {
3949 }
3951 /* Attempt to find another prefetch to the same array and see if we
3952 can merge this one. */
3956 {
3957 /* In case both access same array (same location
3958 just with small difference in constant indexes), merge
3959 the prefetches. Just do the later and the earlier will
3960 get prefetched from previous iteration.
3961 The artificial threshold should not be too small,
3962 but also not bigger than small portion of memory usually
3963 traversed by single loop. */
3966 {
3975 }
3979 {
3984 }
3985 }
3987 /* Merging failed. */
3989 {
3997 num_prefetches++;
3999 {
4004 }
4005 }
4006 }
4007 }
4010 {
4013 /* Attempt to calculate the total number of bytes fetched by all
4014 iterations of the loop. Avoid overflow. */
4019 else
4024 /* Prefetch might be worthwhile only when the loads/stores are dense. */
4029 {
4034 }
4035 else
4036 {
4042 }
4043 else
4046 /* Find how many prefetch instructions we'll use within the loop. */
4048 {
4054 }
4055 }
4057 /* Determine how many iterations ahead to prefetch within the loop, based
4058 on how many prefetches we currently expect to do within the loop. */
4060 {
4062 {
4068 }
4069 }
4070 /* We'll also use AHEAD to determine how many prefetch instructions to
4071 emit before a loop, so don't leave it zero. */
4076 {
4077 /* Update if we've decided not to prefetch anything within the loop. */
4081 /* Find how many prefetch instructions we'll use before the loop. */
4083 {
4091 }
4094 {
4116 }
4117 }
4120 {
4121 /* Record that this loop uses prefetch instructions. */
4125 {
4130 }
4131 }
4134 {
4138 {
4140 rtx insn;
4144 rtx seq;
4146 /* We can save some effort by offsetting the address on
4147 architectures with offsettable memory references. */
4150 else
4151 {
4157 }
4160 /* Make sure the address operand is valid for prefetch. */
4170 /* Check all insns emitted and record the new GIV
4171 information. */
4174 {
4179 }
4180 }
4183 {
4184 /* Emit insns before the loop to fetch the first cache lines or,
4185 if we're not prefetching within the loop, everything we expect
4186 to need. */
4188 {
4196 /* Functions called by LOOP_IV_ADD_EMIT_BEFORE expect a
4197 non-constant INIT_VAL to have the same mode as REG, which
4198 in this case we know to be Pmode. */
4206 loop_start);
4207 }
4208 }
4209 }
4212 }
4213 \f
4214 /* A "basic induction variable" or biv is a pseudo reg that is set
4215 (within this loop) only by incrementing or decrementing it. */
4216 /* A "general induction variable" or giv is a pseudo reg whose
4217 value is a linear function of a biv. */
4219 /* Bivs are recognized by `basic_induction_var';
4220 Givs by `general_induction_var'. */
4222 /* Communication with routines called via `note_stores'. */
4226 /* Dummy register to have nonzero DEST_REG for DEST_ADDR type givs. */
4230 /* ??? Unfinished optimizations, and possible future optimizations,
4231 for the strength reduction code. */
4233 /* ??? The interaction of biv elimination, and recognition of 'constant'
4234 bivs, may cause problems. */
4236 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
4237 performance problems.
4239 Perhaps don't eliminate things that can be combined with an addressing
4240 mode. Find all givs that have the same biv, mult_val, and add_val;
4241 then for each giv, check to see if its only use dies in a following
4242 memory address. If so, generate a new memory address and check to see
4243 if it is valid. If it is valid, then store the modified memory address,
4244 otherwise, mark the giv as not done so that it will get its own iv. */
4246 /* ??? Could try to optimize branches when it is known that a biv is always
4247 positive. */
4249 /* ??? When replace a biv in a compare insn, we should replace with closest
4250 giv so that an optimized branch can still be recognized by the combiner,
4251 e.g. the VAX acb insn. */
4253 /* ??? Many of the checks involving uid_luid could be simplified if regscan
4254 was rerun in loop_optimize whenever a register was added or moved.
4255 Also, some of the optimizations could be a little less conservative. */
4256 \f
4257 /* Scan the loop body and call FNCALL for each insn. In the addition to the
4258 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
4259 callback.
4261 NOT_EVERY_ITERATION is 1 if current insn is not known to be executed at
4262 least once for every loop iteration except for the last one.
4264 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
4265 loop iteration.
4266 */
4267 void
4270 loop_insn_callback fncall;
4271 {
4276 rtx p;
4278 /* If loop_scan_start points to the loop exit test, we have to be wary of
4279 subversive use of gotos inside expression statements. */
4283 /* Scan through loop and update NOT_EVERY_ITERATION and MAYBE_MULTIPLE. */
4287 {
4290 /* Past CODE_LABEL, we get to insns that may be executed multiple
4291 times. The only way we can be sure that they can't is if every
4292 jump insn between here and the end of the loop either
4293 returns, exits the loop, is a jump to a location that is still
4294 behind the label, or is a jump to the loop start. */
4297 {
4303 {
4308 {
4311 else
4315 }
4323 {
4326 }
4327 }
4328 }
4330 /* Past a jump, we get to insns for which we can't count
4331 on whether they will be executed during each iteration. */
4332 /* This code appears twice in strength_reduce. There is also similar
4333 code in scan_loop. */
4335 /* If we enter the loop in the middle, and scan around to the
4336 beginning, don't set not_every_iteration for that.
4337 This can be any kind of jump, since we want to know if insns
4338 will be executed if the loop is executed. */
4343 {
4346 /* If this is a jump outside the loop, then it also doesn't
4347 matter. Check to see if the target of this branch is on the
4348 loop->exits_labels list. */
4356 }
4359 {
4360 /* At the virtual top of a converted loop, insns are again known to
4361 be executed each iteration: logically, the loop begins here
4362 even though the exit code has been duplicated.
4364 Insns are also again known to be executed each iteration at
4365 the LOOP_CONT note. */
4371 loop_depth++;
4373 loop_depth--;
4374 }
4376 /* Note if we pass a loop latch. If we do, then we can not clear
4377 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
4378 a loop since a jump before the last CODE_LABEL may have started
4379 a new loop iteration.
4381 Note that LOOP_TOP is only set for rotated loops and we need
4382 this check for all loops, so compare against the CODE_LABEL
4383 which immediately follows LOOP_START. */
4388 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
4389 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
4390 or not an insn is known to be executed each iteration of the
4391 loop, whether or not any iterations are known to occur.
4393 Therefore, if we have just passed a label and have no more labels
4394 between here and the test insn of the loop, and we have not passed
4395 a jump to the top of the loop, then we know these insns will be
4396 executed each iteration. */
4399 && !past_loop_latch
4404 }
4405 }
4406 \f
4407 static void
4410 {
4413 /* Temporary list pointers for traversing ivs->list. */
4420 /* Scan ivs->list to remove all regs that proved not to be bivs.
4421 Make a sanity check against regs->n_times_set. */
4423 {
4425 /* Above happens if register modified by subreg, etc. */
4426 /* Make sure it is not recognized as a basic induction var: */
4428 /* If never incremented, it is invariant that we decided not to
4429 move. So leave it alone. */
4431 {
4442 }
4443 else
4444 {
4449 }
4450 }
4451 }
4454 /* Determine how BIVS are initialized by looking through pre-header
4455 extended basic block. */
4456 static void
4459 {
4461 /* Temporary list pointers for traversing ivs->list. */
4464 rtx p;
4466 /* Find initial value for each biv by searching backwards from loop_start,
4467 halting at first label. Also record any test condition. */
4471 {
4472 rtx test;
4482 /* Record any test of a biv that branches around the loop if no store
4483 between it and the start of loop. We only care about tests with
4484 constants and registers and only certain of those. */
4494 {
4495 /* If an NE test, we have an initial value! */
4497 {
4501 }
4502 else
4504 }
4505 }
4506 }
4509 /* Look at the each biv and see if we can say anything better about its
4510 initial value from any initializing insns set up above. (This is done
4511 in two passes to avoid missing SETs in a PARALLEL.) */
4512 static void
4515 {
4517 /* Temporary list pointers for traversing ivs->list. */
4522 {
4523 rtx src;
4524 rtx note;
4529 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
4530 is a constant, use the value of that. */
4536 else
4549 {
4553 {
4556 }
4557 }
4558 /* If we can't make it a giv,
4559 let biv keep initial value of "itself". */
4562 }
4563 }
4566 /* Search the loop for general induction variables. */
4568 static void
4571 {
4573 }
4576 /* For each giv for which we still don't know whether or not it is
4577 replaceable, check to see if it is replaceable because its final value
4578 can be calculated. */
4580 static void
4583 {
4588 {
4594 }
4595 }
4598 /* Return nonzero if it is possible to eliminate the biv BL provided
4599 all givs are reduced. This is possible if either the reg is not
4600 used outside the loop, or we can compute what its final value will
4601 be. */
4603 static int
4609 {
4610 /* For architectures with a decrement_and_branch_until_zero insn,
4611 don't do this if we put a REG_NONNEG note on the endtest for this
4612 biv. */
4614 #ifdef HAVE_decrement_and_branch_until_zero
4616 {
4621 }
4622 #endif
4624 /* Check that biv is used outside loop or if it has a final value.
4625 Compare against bl->init_insn rather than loop->start. We aren't
4626 concerned with any uses of the biv between init_insn and
4627 loop->start since these won't be affected by the value of the biv
4628 elsewhere in the function, so long as init_insn doesn't use the
4629 biv itself. */
4640 {
4648 }
4650 }
4653 /* Reduce each giv of BL that we have decided to reduce. */
4655 static void
4659 {
4663 {
4666 {
4669 /* If the code for derived givs immediately below has already
4670 allocated a new_reg, we must keep it. */
4674 #ifdef AUTO_INC_DEC
4675 /* If the target has auto-increment addressing modes, and
4676 this is an address giv, then try to put the increment
4677 immediately after its use, so that flow can create an
4678 auto-increment addressing mode. */
4681 /* We don't handle reversed biv's because bl->biv->insn
4682 does not have a valid INSN_LUID. */
4686 {
4687 /* If other giv's have been combined with this one, then
4688 this will work only if all uses of the other giv's occur
4689 before this giv's insn. This is difficult to check.
4691 We simplify this by looking for the common case where
4692 there is one DEST_REG giv, and this giv's insn is the
4693 last use of the dest_reg of that DEST_REG giv. If the
4694 increment occurs after the address giv, then we can
4695 perform the optimization. (Otherwise, the increment
4696 would have to go before other_giv, and we would not be
4697 able to combine it with the address giv to get an
4698 auto-inc address.) */
4700 {
4705 {
4708 else
4710 }
4717 }
4718 /* Check for case where increment is before the address
4719 giv. Do this test in "loop order". */
4728 else
4731 #ifdef HAVE_cc0
4732 {
4733 rtx prev;
4735 /* We can't put an insn immediately after one setting
4736 cc0, or immediately before one using cc0. */
4743 }
4744 #endif
4748 }
4749 #endif
4751 /* For each place where the biv is incremented, add an insn
4752 to increment the new, reduced reg for the giv. */
4754 {
4755 rtx insert_before;
4761 else
4769 /* A multiply is acceptable here
4770 since this is presumed to be seldom executed. */
4774 }
4776 /* Add code at loop start to initialize giv's reduced reg. */
4781 }
4782 }
4783 }
4786 /* Check for givs whose first use is their definition and whose
4787 last use is the definition of another giv. If so, it is likely
4788 dead and should not be used to derive another giv nor to
4789 eliminate a biv. */
4791 static void
4795 {
4799 {
4806 {
4812 }
4813 }
4814 }
4817 static void
4822 {
4826 {
4833 /* Update expression if this was combined, in case other giv was
4834 replaced. */
4839 /* See if this register is known to be a pointer to something. If
4840 so, see if we can find the alignment. First see if there is a
4841 destination register that is a pointer. If so, this shares the
4842 alignment too. Next see if we can deduce anything from the
4843 computational information. If not, and this is a DEST_ADDR
4844 giv, at least we know that it's a pointer, though we don't know
4845 the alignment. */
4853 {
4862 }
4866 {
4874 }
4879 /* Store reduced reg as the address in the memref where we found
4880 this giv. */
4883 {
4885 }
4886 else
4887 {
4889 rtx note;
4891 /* Not replaceable; emit an insn to set the original giv reg from
4892 the reduced giv, same as above. */
4897 /* The original insn may have a REG_EQUAL note. This note is
4898 now incorrect and may result in invalid substitutions later.
4899 The original insn is dead, but may be part of a libcall
4900 sequence, which doesn't seem worth the bother of handling. */
4904 }
4906 /* When a loop is reversed, givs which depend on the reversed
4907 biv, and which are live outside the loop, must be set to their
4908 correct final value. This insn is only needed if the giv is
4909 not replaceable. The correct final value is the same as the
4910 value that the giv starts the reversed loop with. */
4921 {
4926 }
4927 }
4928 }
4931 static int
4936 rtx test_reg;
4937 {
4946 /* Reduce benefit if not replaceable, since we will insert a
4947 move-insn to replace the insn that calculates this giv. Don't do
4948 this unless the giv is a user variable, since it will often be
4949 marked non-replaceable because of the duplication of the exit
4950 code outside the loop. In such a case, the copies we insert are
4951 dead and will be deleted. So they don't have a cost. Similar
4952 situations exist. */
4953 /* ??? The new final_[bg]iv_value code does a much better job of
4954 finding replaceable giv's, and hence this code may no longer be
4955 necessary. */
4960 /* Decrease the benefit to count the add-insns that we will insert
4961 to increment the reduced reg for the giv. ??? This can
4962 overestimate the run-time cost of the additional insns, e.g. if
4963 there are multiple basic blocks that increment the biv, but only
4964 one of these blocks is executed during each iteration. There is
4965 no good way to detect cases like this with the current structure
4966 of the loop optimizer. This code is more accurate for
4967 determining code size than run-time benefits. */
4970 /* Decide whether to strength-reduce this giv or to leave the code
4971 unchanged (recompute it from the biv each time it is used). This
4972 decision can be made independently for each giv. */
4974 #ifdef AUTO_INC_DEC
4975 /* Attempt to guess whether autoincrement will handle some of the
4976 new add insns; if so, increase BENEFIT (undo the subtraction of
4977 add_cost that was done above). */
4979 /* Increasing the benefit is risky, since this is only a guess.
4980 Avoid increasing register pressure in cases where there would
4981 be no other benefit from reducing this giv. */
4984 {
4999 }
5000 #endif
5003 }
5006 /* Free IV structures for LOOP. */
5008 static void
5011 {
5018 {
5024 {
5027 }
5029 {
5032 }
5036 }
5037 }
5040 /* Perform strength reduction and induction variable elimination.
5042 Pseudo registers created during this function will be beyond the
5043 last valid index in several tables including
5044 REGS->ARRAY[I].N_TIMES_SET and REGNO_LAST_UID. This does not cause a
5045 problem here, because the added registers cannot be givs outside of
5046 their loop, and hence will never be reconsidered. But scan_loop
5047 must check regnos to make sure they are in bounds. */
5049 static void
5053 {
5057 rtx p;
5058 /* Temporary list pointer for traversing ivs->list. */
5060 /* Ratio of extra register life span we can justify
5061 for saving an instruction. More if loop doesn't call subroutines
5062 since in that case saving an insn makes more difference
5063 and more registers are available. */
5064 /* ??? could set this to last value of threshold in move_movables */
5066 /* Map of pseudo-register replacements. */
5078 /* Find all BIVs in loop. */
5081 /* Exit if there are no bivs. */
5083 {
5084 /* Can still unroll the loop anyways, but indicate that there is no
5085 strength reduction info available. */
5091 }
5093 /* Determine how BIVS are initialized by looking through pre-header
5094 extended basic block. */
5097 /* Look at the each biv and see if we can say anything better about its
5098 initial value from any initializing insns set up above. */
5101 /* Search the loop for general induction variables. */
5104 /* Try to calculate and save the number of loop iterations. This is
5105 set to zero if the actual number can not be calculated. This must
5106 be called after all giv's have been identified, since otherwise it may
5107 fail if the iteration variable is a giv. */
5110 #ifdef HAVE_prefetch
5113 #endif
5115 /* Now for each giv for which we still don't know whether or not it is
5116 replaceable, check to see if it is replaceable because its final value
5117 can be calculated. This must be done after loop_iterations is called,
5118 so that final_giv_value will work correctly. */
5121 /* Try to prove that the loop counter variable (if any) is always
5122 nonnegative; if so, record that fact with a REG_NONNEG note
5123 so that "decrement and branch until zero" insn can be used. */
5126 /* Create reg_map to hold substitutions for replaceable giv regs.
5127 Some givs might have been made from biv increments, so look at
5128 ivs->reg_iv_type for a suitable size. */
5132 /* Examine each iv class for feasibility of strength reduction/induction
5133 variable elimination. */
5136 {
5140 /* Test whether it will be possible to eliminate this biv
5141 provided all givs are reduced. */
5144 /* This will be true at the end, if all givs which depend on this
5145 biv have been strength reduced.
5146 We can't (currently) eliminate the biv unless this is so. */
5149 /* Check each extension dependent giv in this class to see if its
5150 root biv is safe from wrapping in the interior mode. */
5153 /* Combine all giv's for this iv_class. */
5157 {
5165 /* If an insn is not to be strength reduced, then set its ignore
5166 flag, and clear bl->all_reduced. */
5168 /* A giv that depends on a reversed biv must be reduced if it is
5169 used after the loop exit, otherwise, it would have the wrong
5170 value after the loop exit. To make it simple, just reduce all
5171 of such giv's whether or not we know they are used after the loop
5172 exit. */
5177 {
5185 }
5186 else
5187 {
5188 /* Check that we can increment the reduced giv without a
5189 multiply insn. If not, reject it. */
5194 {
5202 }
5203 }
5204 }
5206 /* Check for givs whose first use is their definition and whose
5207 last use is the definition of another giv. If so, it is likely
5208 dead and should not be used to derive another giv nor to
5209 eliminate a biv. */
5212 /* Reduce each giv that we decided to reduce. */
5215 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
5216 as not reduced.
5218 For each giv register that can be reduced now: if replaceable,
5219 substitute reduced reg wherever the old giv occurs;
5220 else add new move insn "giv_reg = reduced_reg". */
5223 /* All the givs based on the biv bl have been reduced if they
5224 merit it. */
5226 /* For each giv not marked as maybe dead that has been combined with a
5227 second giv, clear any "maybe dead" mark on that second giv.
5228 v->new_reg will either be or refer to the register of the giv it
5229 combined with.
5231 Doing this clearing avoids problems in biv elimination where
5232 a giv's new_reg is a complex value that can't be put in the
5233 insn but the giv combined with (with a reg as new_reg) is
5234 marked maybe_dead. Since the register will be used in either
5235 case, we'd prefer it be used from the simpler giv. */
5241 /* Try to eliminate the biv, if it is a candidate.
5242 This won't work if ! bl->all_reduced,
5243 since the givs we planned to use might not have been reduced.
5245 We have to be careful that we didn't initially think we could
5246 eliminate this biv because of a giv that we now think may be
5247 dead and shouldn't be used as a biv replacement.
5249 Also, there is the possibility that we may have a giv that looks
5250 like it can be used to eliminate a biv, but the resulting insn
5251 isn't valid. This can happen, for example, on the 88k, where a
5252 JUMP_INSN can compare a register only with zero. Attempts to
5253 replace it with a compare with a constant will fail.
5255 Note that in cases where this call fails, we may have replaced some
5256 of the occurrences of the biv with a giv, but no harm was done in
5257 doing so in the rare cases where it can occur. */
5261 {
5262 /* ?? If we created a new test to bypass the loop entirely,
5263 or otherwise drop straight in, based on this test, then
5264 we might want to rewrite it also. This way some later
5265 pass has more hope of removing the initialization of this
5266 biv entirely. */
5268 /* If final_value != 0, then the biv may be used after loop end
5269 and we must emit an insn to set it just in case.
5271 Reversed bivs already have an insn after the loop setting their
5272 value, so we don't need another one. We can't calculate the
5273 proper final value for such a biv here anyways. */
5282 }
5283 /* See above note wrt final_value. But since we couldn't eliminate
5284 the biv, we must set the value after the loop instead of before. */
5288 }
5290 /* Go through all the instructions in the loop, making all the
5291 register substitutions scheduled in REG_MAP. */
5296 {
5300 }
5303 {
5304 /* When we completely unroll a loop we will likely not need the increment
5305 of the loop BIV and we will not need the conditional branch at the
5306 end of the loop. */
5309 #ifdef HAVE_cc0
5310 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
5311 need the comparison before the conditional branch at the end of the
5312 loop. */
5314 #endif
5316 /* We'll need one copy for each loop iteration. */
5319 /* A little slop to account for the ability to remove initialization
5320 code, better CSE, and other secondary benefits of completely
5321 unrolling some loops. */
5324 /* Clamp the value. */
5327 }
5329 /* Unroll loops from within strength reduction so that we can use the
5330 induction variable information that strength_reduce has already
5331 collected. Always unroll loops that would be as small or smaller
5332 unrolled than when rolled. */
5339 #ifdef HAVE_doloop_end
5344 /* In case number of iterations is known, drop branch prediction note
5345 in the branch. Do that only in second loop pass, as loop unrolling
5346 may change the number of iterations performed. */
5348 {
5349 unsigned HOST_WIDE_INT n
5354 }
5362 }
5363 \f
5364 /*Record all basic induction variables calculated in the insn. */
5365 static rtx
5368 rtx p;
5371 {
5373 rtx set;
5374 rtx dest_reg;
5375 rtx inc_val;
5376 rtx mult_val;
5382 {
5387 {
5392 {
5393 /* It is a possible basic induction variable.
5394 Create and initialize an induction structure for it. */
5402 }
5405 }
5406 }
5408 }
5409 \f
5410 /* Record all givs calculated in the insn.
5411 A register is a giv if: it is only set once, it is a function of a
5412 biv and a constant (or invariant), and it is not a biv. */
5413 static rtx
5416 rtx p;
5419 {
5422 rtx set;
5423 /* Look for a general induction variable in a register. */
5428 {
5429 rtx src_reg;
5430 rtx dest_reg;
5431 rtx add_val;
5432 rtx mult_val;
5433 rtx ext_val;
5436 rtx last_consec_insn;
5445 /* Equivalent expression is a giv. */
5450 /* Don't try to handle any regs made by loop optimization.
5451 We have nothing on them in regno_first_uid, etc. */
5453 /* Don't recognize a BASIC_INDUCT_VAR here. */
5455 /* This must be the only place where the register is set. */
5457 /* or all sets must be consecutive and make a giv. */
5462 {
5466 /* If this is a library call, increase benefit. */
5470 /* Skip the consecutive insns, if there are any. */
5478 }
5479 }
5481 #ifndef DONT_REDUCE_ADDR
5482 /* Look for givs which are memory addresses. */
5483 /* This resulted in worse code on a VAX 8600. I wonder if it
5484 still does. */
5487 maybe_multiple);
5488 #endif
5490 /* Update the status of whether giv can derive other givs. This can
5491 change when we pass a label or an insn that updates a biv. */
5496 }
5497 \f
5498 /* Return 1 if X is a valid source for an initial value (or as value being
5499 compared against in an initial test).
5501 X must be either a register or constant and must not be clobbered between
5502 the current insn and the start of the loop.
5504 INSN is the insn containing X. */
5506 static int
5508 rtx x;
5509 rtx insn;
5511 rtx loop_start;
5512 {
5516 /* Only consider pseudos we know about initialized in insns whose luids
5517 we know. */
5522 /* Don't use call-clobbered registers across a call which clobbers it. On
5523 some machines, don't use any hard registers at all. */
5525 && (SMALL_REGISTER_CLASSES
5529 /* Don't use registers that have been clobbered before the start of the
5530 loop. */
5535 }
5536 \f
5537 /* Scan X for memory refs and check each memory address
5538 as a possible giv. INSN is the insn whose pattern X comes from.
5539 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
5540 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
5541 more than once in each loop iteration. */
5543 static void
5546 rtx x;
5547 rtx insn;
5549 {
5559 {
5575 {
5576 rtx src_reg;
5577 rtx add_val;
5578 rtx mult_val;
5579 rtx ext_val;
5582 /* This code used to disable creating GIVs with mult_val == 1 and
5583 add_val == 0. However, this leads to lost optimizations when
5584 it comes time to combine a set of related DEST_ADDR GIVs, since
5585 this one would not be seen. */
5590 {
5591 /* Found one; record it. */
5600 }
5601 }
5606 }
5608 /* Recursively scan the subexpressions for other mem refs. */
5614 maybe_multiple);
5618 maybe_multiple);
5619 }
5620 \f
5621 /* Fill in the data about one biv update.
5622 V is the `struct induction' in which we record the biv. (It is
5623 allocated by the caller, with alloca.)
5624 INSN is the insn that sets it.
5625 DEST_REG is the biv's reg.
5627 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
5628 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
5629 being set to INC_VAL.
5631 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
5632 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
5633 can be executed more than once per iteration. If MAYBE_MULTIPLE
5634 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
5635 executed exactly once per iteration. */
5637 static void
5642 rtx insn;
5643 rtx dest_reg;
5644 rtx inc_val;
5645 rtx mult_val;
5649 {
5665 /* Add this to the reg's iv_class, creating a class
5666 if this is the first incrementation of the reg. */
5670 {
5671 /* Create and initialize new iv_class. */
5681 /* Set initial value to the reg itself. */
5684 /* We haven't seen the initializing insn yet */
5694 /* Add this class to ivs->list. */
5698 /* Put it in the array of biv register classes. */
5700 }
5702 /* Update IV_CLASS entry for this biv. */
5711 }
5712 \f
5713 /* Fill in the data about one giv.
5714 V is the `struct induction' in which we record the giv. (It is
5715 allocated by the caller, with alloca.)
5716 INSN is the insn that sets it.
5717 BENEFIT estimates the savings from deleting this insn.
5718 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
5719 into a register or is used as a memory address.
5721 SRC_REG is the biv reg which the giv is computed from.
5722 DEST_REG is the giv's reg (if the giv is stored in a reg).
5723 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
5724 LOCATION points to the place where this giv's value appears in INSN. */
5726 static void
5731 rtx insn;
5732 rtx src_reg;
5733 rtx dest_reg;
5739 {
5744 rtx temp;
5746 /* Attempt to prove constantness of the values. Don't let simplify_rtx
5747 undo the MULT canonicalization that we performed earlier. */
5777 /* The v->always_computable field is used in update_giv_derive, to
5778 determine whether a giv can be used to derive another giv. For a
5779 DEST_REG giv, INSN computes a new value for the giv, so its value
5780 isn't computable if INSN insn't executed every iteration.
5781 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5782 it does not compute a new value. Hence the value is always computable
5783 regardless of whether INSN is executed each iteration. */
5787 else
5793 {
5796 }
5798 {
5803 /* If the lifetime is zero, it means that this register is
5804 really a dead store. So mark this as a giv that can be
5805 ignored. This will not prevent the biv from being eliminated. */
5811 }
5813 /* Add the giv to the class of givs computed from one biv. */
5817 {
5820 /* Don't count DEST_ADDR. This is supposed to count the number of
5821 insns that calculate givs. */
5825 }
5826 else
5827 /* Fatal error, biv missing for this giv? */
5831 {
5834 }
5835 else
5836 {
5837 /* The giv can be replaced outright by the reduced register only if all
5838 of the following conditions are true:
5839 - the insn that sets the giv is always executed on any iteration
5840 on which the giv is used at all
5841 (there are two ways to deduce this:
5842 either the insn is executed on every iteration,
5843 or all uses follow that insn in the same basic block),
5844 - the giv is not used outside the loop
5845 - no assignments to the biv occur during the giv's lifetime. */
5848 /* Previous line always fails if INSN was moved by loop opt. */
5851 && (! not_every_iteration
5853 {
5854 /* Now check that there are no assignments to the biv within the
5855 giv's lifetime. This requires two separate checks. */
5857 /* Check each biv update, and fail if any are between the first
5858 and last use of the giv.
5860 If this loop contains an inner loop that was unrolled, then
5861 the insn modifying the biv may have been emitted by the loop
5862 unrolling code, and hence does not have a valid luid. Just
5863 mark the biv as not replaceable in this case. It is not very
5864 useful as a biv, because it is used in two different loops.
5865 It is very unlikely that we would be able to optimize the giv
5866 using this biv anyways. */
5871 {
5877 {
5881 }
5882 }
5884 /* If there are any backwards branches that go from after the
5885 biv update to before it, then this giv is not replaceable. */
5889 {
5893 }
5894 }
5895 else
5896 {
5897 /* May still be replaceable, we don't have enough info here to
5898 decide. */
5901 }
5902 }
5904 /* Record whether the add_val contains a const_int, for later use by
5905 combine_givs. */
5906 {
5911 ;
5915 {
5917 {
5922 else
5924 }
5927 }
5928 }
5932 }
5934 /* All this does is determine whether a giv can be made replaceable because
5935 its final value can be calculated. This code can not be part of record_giv
5936 above, because final_giv_value requires that the number of loop iterations
5937 be known, and that can not be accurately calculated until after all givs
5938 have been identified. */
5940 static void
5944 {
5947 /* DEST_ADDR givs will never reach here, because they are always marked
5948 replaceable above in record_giv. */
5950 /* The giv can be replaced outright by the reduced register only if all
5951 of the following conditions are true:
5952 - the insn that sets the giv is always executed on any iteration
5953 on which the giv is used at all
5954 (there are two ways to deduce this:
5955 either the insn is executed on every iteration,
5956 or all uses follow that insn in the same basic block),
5957 - its final value can be calculated (this condition is different
5958 than the one above in record_giv)
5959 - it's not used before the it's set
5960 - no assignments to the biv occur during the giv's lifetime. */
5962 #if 0
5963 /* This is only called now when replaceable is known to be false. */
5964 /* Clear replaceable, so that it won't confuse final_giv_value. */
5966 #endif
5971 {
5974 rtx last_giv_use;
5979 /* When trying to determine whether or not a biv increment occurs
5980 during the lifetime of the giv, we can ignore uses of the variable
5981 outside the loop because final_value is true. Hence we can not
5982 use regno_last_uid and regno_first_uid as above in record_giv. */
5984 /* Search the loop to determine whether any assignments to the
5985 biv occur during the giv's lifetime. Start with the insn
5986 that sets the giv, and search around the loop until we come
5987 back to that insn again.
5989 Also fail if there is a jump within the giv's lifetime that jumps
5990 to somewhere outside the lifetime but still within the loop. This
5991 catches spaghetti code where the execution order is not linear, and
5992 hence the above test fails. Here we assume that the giv lifetime
5993 does not extend from one iteration of the loop to the next, so as
5994 to make the test easier. Since the lifetime isn't known yet,
5995 this requires two loops. See also record_giv above. */
6000 {
6003 {
6006 }
6012 {
6013 /* It is possible for the BIV increment to use the GIV if we
6014 have a cycle. Thus we must be sure to check each insn for
6015 both BIV and GIV uses, and we must check for BIV uses
6016 first. */
6023 {
6025 {
6029 }
6031 }
6032 }
6033 }
6035 /* Now that the lifetime of the giv is known, check for branches
6036 from within the lifetime to outside the lifetime if it is still
6037 replaceable. */
6040 {
6043 {
6056 {
6065 }
6066 }
6067 }
6069 /* If it is replaceable, then save the final value. */
6072 }
6077 }
6078 \f
6079 /* Update the status of whether a giv can derive other givs.
6081 We need to do something special if there is or may be an update to the biv
6082 between the time the giv is defined and the time it is used to derive
6083 another giv.
6085 In addition, a giv that is only conditionally set is not allowed to
6086 derive another giv once a label has been passed.
6088 The cases we look at are when a label or an update to a biv is passed. */
6090 static void
6093 rtx p;
6094 {
6098 rtx tem;
6101 /* Search all IV classes, then all bivs, and finally all givs.
6103 There are three cases we are concerned with. First we have the situation
6104 of a giv that is only updated conditionally. In that case, it may not
6105 derive any givs after a label is passed.
6107 The second case is when a biv update occurs, or may occur, after the
6108 definition of a giv. For certain biv updates (see below) that are
6109 known to occur between the giv definition and use, we can adjust the
6110 giv definition. For others, or when the biv update is conditional,
6111 we must prevent the giv from deriving any other givs. There are two
6112 sub-cases within this case.
6114 If this is a label, we are concerned with any biv update that is done
6115 conditionally, since it may be done after the giv is defined followed by
6116 a branch here (actually, we need to pass both a jump and a label, but
6117 this extra tracking doesn't seem worth it).
6119 If this is a jump, we are concerned about any biv update that may be
6120 executed multiple times. We are actually only concerned about
6121 backward jumps, but it is probably not worth performing the test
6122 on the jump again here.
6124 If this is a biv update, we must adjust the giv status to show that a
6125 subsequent biv update was performed. If this adjustment cannot be done,
6126 the giv cannot derive further givs. */
6132 {
6134 {
6135 /* If cant_derive is already true, there is no point in
6136 checking all of these conditions again. */
6140 /* If this giv is conditionally set and we have passed a label,
6141 it cannot derive anything. */
6145 /* Skip givs that have mult_val == 0, since
6146 they are really invariants. Also skip those that are
6147 replaceable, since we know their lifetime doesn't contain
6148 any biv update. */
6152 /* The only way we can allow this giv to derive another
6153 is if this is a biv increment and we can form the product
6154 of biv->add_val and giv->mult_val. In this case, we will
6155 be able to compute a compensation. */
6157 {
6158 rtx ext_val_dummy;
6169 tem = simplify_giv_expr
6176 else
6178 }
6182 }
6183 }
6184 }
6185 \f
6186 /* Check whether an insn is an increment legitimate for a basic induction var.
6187 X is the source of insn P, or a part of it.
6188 MODE is the mode in which X should be interpreted.
6190 DEST_REG is the putative biv, also the destination of the insn.
6191 We accept patterns of these forms:
6192 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
6193 REG = INVARIANT + REG
6195 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
6196 store the additive term into *INC_VAL, and store the place where
6197 we found the additive term into *LOCATION.
6199 If X is an assignment of an invariant into DEST_REG, we set
6200 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
6202 We also want to detect a BIV when it corresponds to a variable
6203 whose mode was promoted via PROMOTED_MODE. In that case, an increment
6204 of the variable may be a PLUS that adds a SUBREG of that variable to
6205 an invariant and then sign- or zero-extends the result of the PLUS
6206 into the variable.
6208 Most GIVs in such cases will be in the promoted mode, since that is the
6209 probably the natural computation mode (and almost certainly the mode
6210 used for addresses) on the machine. So we view the pseudo-reg containing
6211 the variable as the BIV, as if it were simply incremented.
6213 Note that treating the entire pseudo as a BIV will result in making
6214 simple increments to any GIVs based on it. However, if the variable
6215 overflows in its declared mode but not its promoted mode, the result will
6216 be incorrect. This is acceptable if the variable is signed, since
6217 overflows in such cases are undefined, but not if it is unsigned, since
6218 those overflows are defined. So we only check for SIGN_EXTEND and
6219 not ZERO_EXTEND.
6221 If we cannot find a biv, we return 0. */
6223 static int
6226 rtx x;
6228 rtx dest_reg;
6229 rtx p;
6233 {
6241 {
6247 {
6249 }
6254 {
6256 }
6257 else
6270 /* If what's inside the SUBREG is a BIV, then the SUBREG. This will
6271 handle addition of promoted variables.
6272 ??? The comment at the start of this function is wrong: promoted
6273 variable increments don't look like it says they do. */
6279 /* If this register is assigned in a previous insn, look at its
6280 source, but don't go outside the loop or past a label. */
6282 /* If this sets a register to itself, we would repeat any previous
6283 biv increment if we applied this strategy blindly. */
6289 {
6290 rtx dest;
6291 do
6292 {
6294 }
6323 }
6324 /* Fall through. */
6326 /* Can accept constant setting of biv only when inside inner most loop.
6327 Otherwise, a biv of an inner loop may be incorrectly recognized
6328 as a biv of the outer loop,
6329 causing code to be moved INTO the inner loop. */
6336 /* convert_modes aborts if we try to convert to or from CCmode, so just
6337 exclude that case. It is very unlikely that a condition code value
6338 would be a useful iterator anyways. convert_modes aborts if we try to
6339 convert a float mode to non-float or vice versa too. */
6343 {
6344 /* Possible bug here? Perhaps we don't know the mode of X. */
6348 }
6349 else
6357 /* Similar, since this can be a sign extension. */
6362 ;
6376 location);
6381 }
6382 }
6383 \f
6384 /* A general induction variable (giv) is any quantity that is a linear
6385 function of a basic induction variable,
6386 i.e. giv = biv * mult_val + add_val.
6387 The coefficients can be any loop invariant quantity.
6388 A giv need not be computed directly from the biv;
6389 it can be computed by way of other givs. */
6391 /* Determine whether X computes a giv.
6392 If it does, return a nonzero value
6393 which is the benefit from eliminating the computation of X;
6394 set *SRC_REG to the register of the biv that it is computed from;
6395 set *ADD_VAL and *MULT_VAL to the coefficients,
6396 such that the value of X is biv * mult + add; */
6398 static int
6402 rtx x;
6410 {
6414 /* If this is an invariant, forget it, it isn't a giv. */
6425 {
6428 /* Since this is now an invariant and wasn't before, it must be a giv
6429 with MULT_VAL == 0. It doesn't matter which BIV we associate this
6430 with. */
6437 /* This is equivalent to a BIV. */
6444 /* Either (plus (biv) (invar)) or
6445 (plus (mult (biv) (invar_1)) (invar_2)). */
6447 {
6450 }
6451 else
6452 {
6455 }
6460 /* ADD_VAL is zero. */
6468 }
6470 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
6471 unless they are CONST_INT). */
6479 else
6482 /* Always return true if this is a giv so it will be detected as such,
6483 even if the benefit is zero or negative. This allows elimination
6484 of bivs that might otherwise not be eliminated. */
6486 }
6487 \f
6488 /* Given an expression, X, try to form it as a linear function of a biv.
6489 We will canonicalize it to be of the form
6490 (plus (mult (BIV) (invar_1))
6491 (invar_2))
6492 with possible degeneracies.
6494 The invariant expressions must each be of a form that can be used as a
6495 machine operand. We surround then with a USE rtx (a hack, but localized
6496 and certainly unambiguous!) if not a CONST_INT for simplicity in this
6497 routine; it is the caller's responsibility to strip them.
6499 If no such canonicalization is possible (i.e., two biv's are used or an
6500 expression that is neither invariant nor a biv or giv), this routine
6501 returns 0.
6503 For a nonzero return, the result will have a code of CONST_INT, USE,
6504 REG (for a BIV), PLUS, or MULT. No other codes will occur.
6506 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
6511 static rtx
6514 rtx x;
6517 {
6522 rtx tem;
6524 /* If this is not an integer mode, or if we cannot do arithmetic in this
6525 mode, this can't be a giv. */
6532 {
6539 /* Put constant last, CONST_INT last if both constant. */
6547 /* Handle addition of zero, then addition of an invariant. */
6552 {
6555 /* Adding two invariants must result in an invariant, so enclose
6556 addition operation inside a USE and return it. */
6566 else
6575 /* biv + invar or mult + invar. Return sum. */
6579 /* (a + invar_1) + invar_2. Associate. */
6580 return
6586 arg1)),
6591 }
6593 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
6594 MULT to reduce cases. */
6600 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
6601 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
6602 Recurse to associate the second PLUS. */
6607 return
6615 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
6631 /* Handle "a - b" as "a + b * (-1)". */
6637 constm1_rtx)),
6646 /* Put constant last, CONST_INT last if both constant. */
6651 /* If second argument is not now constant, not giv. */
6655 /* Handle multiply by 0 or 1. */
6663 {
6665 /* biv * invar. Done. */
6669 /* Product of two constants. */
6673 /* invar * invar is a giv, but attempt to simplify it somehow. */
6679 {
6680 /* (invar_0 * invar_1) * invar_2. Associate. */
6687 arg1)),
6689 }
6690 /* Propagate the MULT expressions to the intermost nodes. */
6692 {
6693 /* (invar_0 + invar_1) * invar_2. Distribute. */
6699 arg1),
6703 arg1)),
6705 }
6709 /* (a * invar_1) * invar_2. Associate. */
6715 arg1)),
6719 /* (a + invar_1) * invar_2. Distribute. */
6724 arg1),
6727 arg1)),
6732 }
6735 /* Shift by constant is multiply by power of two. */
6739 return
6748 /* "-a" is "a * (-1)" */
6754 /* "~a" is "-a - 1". Silly, but easy. */
6758 const1_rtx),
6762 /* Already in proper form for invariant. */
6768 /* Conditionally recognize extensions of simple IVs. After we've
6769 computed loop traversal counts and verified the range of the
6770 source IV, we'll reevaluate this as a GIV. */
6772 {
6775 {
6778 }
6779 }
6783 /* If this is a new register, we can't deal with it. */
6787 /* Check for biv or giv. */
6789 {
6793 {
6796 /* Form expression from giv and add benefit. Ensure this giv
6797 can derive another and subtract any needed adjustment if so. */
6799 /* Increasing the benefit here is risky. The only case in which it
6800 is arguably correct is if this is the only use of V. In other
6801 cases, this will artificially inflate the benefit of the current
6802 giv, and lead to suboptimal code. Thus, it is disabled, since
6803 potentially not reducing an only marginally beneficial giv is
6804 less harmful than reducing many givs that are not really
6805 beneficial. */
6806 {
6810 }
6823 {
6826 }
6827 else
6828 {
6831 }
6833 }
6836 do_default:
6837 /* If it isn't an induction variable, and it is invariant, we
6838 may be able to simplify things further by looking through
6839 the bits we just moved outside the loop. */
6841 {
6847 {
6848 /* Ok, we found a match. Substitute and simplify. */
6850 /* If we match another movable, we must use that, as
6851 this one is going away. */
6856 /* If consec is nonzero, this is a member of a group of
6857 instructions that were moved together. We handle this
6858 case only to the point of seeking to the last insn and
6859 looking for a REG_EQUAL. Fail if we don't find one. */
6861 {
6864 do
6865 {
6867 }
6873 }
6874 else
6875 {
6879 }
6882 {
6883 /* What we are most interested in is pointer
6884 arithmetic on invariants -- only take
6885 patterns we may be able to do something with. */
6891 {
6893 benefit);
6896 }
6901 {
6906 }
6907 }
6909 }
6910 }
6912 }
6914 /* Fall through to general case. */
6916 /* If invariant, return as USE (unless CONST_INT).
6917 Otherwise, not giv. */
6922 {
6931 }
6932 else
6934 }
6935 }
6937 /* This routine folds invariants such that there is only ever one
6938 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6940 static rtx
6943 {
6949 {
6952 }
6955 {
6958 }
6959 else
6960 {
6963 }
6964 }
6966 static rtx
6970 {
6972 {
6976 else
6979 }
6982 else
6985 }
6986 \f
6987 /* Help detect a giv that is calculated by several consecutive insns;
6988 for example,
6989 giv = biv * M
6990 giv = giv + A
6991 The caller has already identified the first insn P as having a giv as dest;
6992 we check that all other insns that set the same register follow
6993 immediately after P, that they alter nothing else,
6994 and that the result of the last is still a giv.
6996 The value is 0 if the reg set in P is not really a giv.
6997 Otherwise, the value is the amount gained by eliminating
6998 all the consecutive insns that compute the value.
7000 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
7001 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
7003 The coefficients of the ultimate giv value are stored in
7004 *MULT_VAL and *ADD_VAL. */
7006 static int
7011 rtx p;
7012 rtx src_reg;
7013 rtx dest_reg;
7018 {
7024 rtx temp;
7025 rtx set;
7027 /* Indicate that this is a giv so that we can update the value produced in
7028 each insn of the multi-insn sequence.
7030 This induction structure will be used only by the call to
7031 general_induction_var below, so we can allocate it on our stack.
7032 If this is a giv, our caller will replace the induct var entry with
7033 a new induction structure. */
7054 {
7058 /* If libcall, skip to end of call sequence. */
7069 /* Giv created by equivalent expression. */
7075 {
7079 count--;
7083 }
7085 {
7086 /* Allow insns that set something other than this giv to a
7087 constant. Such insns are needed on machines which cannot
7088 include long constants and should not disqualify a giv. */
7097 }
7098 }
7103 }
7104 \f
7105 /* Return an rtx, if any, that expresses giv G2 as a function of the register
7106 represented by G1. If no such expression can be found, or it is clear that
7107 it cannot possibly be a valid address, 0 is returned.
7109 To perform the computation, we note that
7110 G1 = x * v + a and
7111 G2 = y * v + b
7112 where `v' is the biv.
7114 So G2 = (y/b) * G1 + (b - a*y/x).
7116 Note that MULT = y/x.
7118 Update: A and B are now allowed to be additive expressions such that
7119 B contains all variables in A. That is, computing B-A will not require
7120 subtracting variables. */
7122 static rtx
7125 {
7126 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
7131 /* If MULT is not 1, we cannot handle A with non-constants, since we
7132 would then be required to subtract multiples of the registers in A.
7133 This is theoretically possible, and may even apply to some Fortran
7134 constructs, but it is a lot of work and we do not attempt it here. */
7139 /* In general these structures are sorted top to bottom (down the PLUS
7140 chain), but not left to right across the PLUS. If B is a higher
7141 order giv than A, we can strip one level and recurse. If A is higher
7142 order, we'll eventually bail out, but won't know that until the end.
7143 If they are the same, we'll strip one level around this loop. */
7146 {
7158 /* We matched: remove one reg completely. */
7161 /* An alternate match. */
7164 /* An alternate match. */
7166 else
7167 {
7168 /* Indicates an extra register in B. Strip one level from B and
7169 recurse, hoping B was the higher order expression. */
7174 }
7175 }
7177 /* Here we are at the last level of A, go through the cases hoping to
7178 get rid of everything but a constant. */
7181 {
7194 }
7196 {
7198 }
7200 {
7205 }
7207 {
7212 else
7214 }
7219 }
7221 rtx
7224 {
7227 /* The value that G1 will be multiplied by must be a constant integer. Also,
7228 the only chance we have of getting a valid address is if b*c/a (see above
7229 for notation) is also an integer. */
7232 {
7237 }
7240 else
7241 {
7242 /* ??? Find out if the one is a multiple of the other? */
7244 }
7248 {
7249 /* Failed. If we've got a multiplication factor between G1 and G2,
7250 scale G1's addend and try again. */
7252 {
7256 {
7257 HOST_WIDE_INT m;
7261 }
7262 else
7263 {
7265 mult);
7266 }
7269 }
7270 }
7274 /* Form simplified final result. */
7279 else
7284 else
7285 {
7288 {
7292 }
7295 }
7296 }
7297 \f
7298 /* Return an rtx, if any, that expresses giv G2 as a function of the register
7299 represented by G1. This indicates that G2 should be combined with G1 and
7300 that G2 can use (either directly or via an address expression) a register
7301 used to represent G1. */
7303 static rtx
7306 {
7309 /* With the introduction of ext dependent givs, we must care for modes.
7310 G2 must not use a wider mode than G1. */
7320 /* If these givs are identical, they can be combined. We use the results
7321 of express_from because the addends are not in a canonical form, so
7322 rtx_equal_p is a weaker test. */
7323 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
7324 combination to be the other way round. */
7327 {
7329 }
7331 /* If G2 can be expressed as a function of G1 and that function is valid
7332 as an address and no more expensive than using a register for G2,
7333 the expression of G2 in terms of G1 can be used. */
7337 /* ??? Looses, especially with -fforce-addr, where *g2->location
7338 will always be a register, and so anything more complicated
7339 gets discarded. */
7340 #if 0
7341 #ifdef ADDRESS_COST
7343 #else
7345 #endif
7346 #endif
7347 )
7348 {
7350 }
7353 }
7354 \f
7355 /* Check each extension dependent giv in this class to see if its
7356 root biv is safe from wrapping in the interior mode, which would
7357 make the giv illegal. */
7359 static void
7363 {
7366 HOST_WIDE_INT start_val;
7372 /* Make sure the iteration data is available. We must have
7373 constants in order to be certain of no overflow. */
7374 /* ??? An unknown iteration count with an increment of +-1
7375 combined with friendly exit tests of against an invariant
7376 value is also amenable to optimization. Not implemented. */
7382 /* Make sure the host can represent the arithmetic. */
7384 {
7386 HOST_WIDE_INT s_end_val;
7398 /* Check for host arithmetic overflow. */
7400 {
7402 HOST_WIDE_INT s_max;
7409 /* Check zero extension of biv ok. */
7411 /* Check for host arithmetic overflow. */
7412 && (neg_incr
7415 /* Check for target arithmetic overflow. */
7416 && (neg_incr
7419 {
7421 }
7423 /* Check sign extension of biv ok. */
7424 /* ??? While it is true that overflow with signed and pointer
7425 arithmetic is undefined, I fear too many programmers don't
7426 keep this fact in mind -- myself included on occasion.
7427 So leave alone with the signed overflow optimizations. */
7429 /* Check for host arithmetic overflow. */
7430 && (neg_incr
7433 /* Check for target arithmetic overflow. */
7434 && (neg_incr
7437 {
7439 }
7440 }
7441 }
7443 /* Invalidate givs that fail the tests. */
7446 {
7451 {
7460 /* We don't know whether this value is being used as either
7461 signed or unsigned, so to safely truncate we must satisfy
7462 both. The initial check here verifies the BIV itself;
7463 once that is successful we may check its range wrt the
7464 derived GIV. */
7466 {
7470 /* We know from the above that both endpoints are nonnegative,
7471 and that there is no wrapping. Verify that both endpoints
7472 are within the (signed) range of the outer mode. */
7475 }
7480 }
7483 {
7485 {
7489 }
7490 }
7491 else
7492 {
7494 {
7499 else
7500 {
7505 else
7507 }
7512 }
7515 }
7516 }
7517 }
7519 /* Generate a version of VALUE in a mode appropriate for initializing V. */
7521 rtx
7524 rtx value;
7525 {
7531 /* Recall that check_ext_dependent_givs verified that the known bounds
7532 of a biv did not overflow or wrap with respect to the extension for
7533 the giv. Therefore, constants need no additional adjustment. */
7537 /* Otherwise, we must adjust the value to compensate for the
7538 differing modes of the biv and the giv. */
7540 }
7541 \f
7542 struct combine_givs_stats
7543 {
7546 };
7548 static int
7552 {
7559 /* Stabilize the sort. */
7563 }
7565 /* Check all pairs of givs for iv_class BL and see if any can be combined with
7566 any other. If so, point SAME to the giv combined with and set NEW_REG to
7567 be an expression (in terms of the other giv's DEST_REG) equivalent to the
7568 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
7570 static void
7574 {
7575 /* Additional benefit to add for being combined multiple times. */
7583 /* Count givs, because bl->giv_count is incorrect here. */
7587 giv_count++;
7589 giv_array
7600 {
7602 rtx single_use;
7607 /* If a DEST_REG GIV is used only once, do not allow it to combine
7608 with anything, for in doing so we will gain nothing that cannot
7609 be had by simply letting the GIV with which we would have combined
7610 to be reduced on its own. The losage shows up in particular with
7611 DEST_ADDR targets on hosts with reg+reg addressing, though it can
7612 be seen elsewhere as well. */
7619 /* Add an additional weight for zero addends. */
7624 {
7625 rtx this_combine;
7630 {
7633 }
7634 }
7636 }
7638 /* Iterate, combining until we can't. */
7639 restart:
7643 {
7646 {
7652 }
7654 }
7657 {
7663 /* If it has already been combined, skip. */
7668 {
7671 /* If it has already been combined, skip. */
7673 {
7678 /* For destination, we now may replace by mem expression instead
7679 of register. This changes the costs considerably, so add the
7680 compensation. */
7690 /* ??? The new final_[bg]iv_value code does a much better job
7691 of finding replaceable giv's, and hence this code may no
7692 longer be necessary. */
7696 /* To help optimize the next set of combinations, remove
7697 this giv from the benefits of other potential mates. */
7699 {
7703 }
7710 }
7711 }
7713 /* To help optimize the next set of combinations, remove
7714 this giv from the benefits of other potential mates. */
7716 {
7718 {
7722 }
7726 /* We've finished with this giv, and everything it touched.
7727 Restart the combination so that proper weights for the
7728 rest of the givs are properly taken into account. */
7729 /* ??? Ideally we would compact the arrays at this point, so
7730 as to not cover old ground. But sanely compacting
7731 can_combine is tricky. */
7733 }
7734 }
7736 /* Clean up. */
7739 }
7740 \f
7741 /* Generate sequence for REG = B * M + A. */
7743 static rtx
7749 {
7750 rtx seq;
7751 rtx result;
7754 /* Use unsigned arithmetic. */
7762 }
7765 /* Update registers created in insn sequence SEQ. */
7767 static void
7770 rtx seq;
7771 {
7772 rtx insn;
7774 /* Update register info for alias analysis. */
7780 {
7783 {
7790 }
7791 }
7795 }
7798 /* EMIT code before BEFORE_BB/BEFORE_INSN to set REG = B * M + A. */
7800 void
7807 basic_block before_bb;
7808 rtx before_insn;
7809 {
7810 rtx seq;
7813 {
7816 }
7818 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
7821 /* Increase the lifetime of any invariants moved further in code. */
7828 /* It is possible that the expansion created lots of new registers.
7829 Iterate over the sequence we just created and record them all. */
7831 }
7834 /* Emit insns in loop pre-header to set REG = B * M + A. */
7836 void
7843 {
7844 rtx seq;
7846 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
7849 /* Increase the lifetime of any invariants moved further in code.
7850 ???? Is this really necessary? */
7857 /* It is possible that the expansion created lots of new registers.
7858 Iterate over the sequence we just created and record them all. */
7860 }
7863 /* Emit insns after loop to set REG = B * M + A. */
7865 void
7872 {
7873 rtx seq;
7875 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
7880 /* It is possible that the expansion created lots of new registers.
7881 Iterate over the sequence we just created and record them all. */
7883 }
7887 /* Similar to gen_add_mult, but compute cost rather than generating
7888 sequence. */
7890 static int
7896 {
7906 {
7911 }
7914 }
7915 \f
7916 /* Test whether A * B can be computed without
7917 an actual multiply insn. Value is 1 if so.
7919 ??? This function stinks because it generates a ton of wasted RTL
7920 ??? and as a result fragments GC memory to no end. There are other
7921 ??? places in the compiler which are invoked a lot and do the same
7922 ??? thing, generate wasted RTL just to see if something is possible. */
7924 static int
7926 rtx a;
7927 rtx b;
7928 {
7929 rtx tmp;
7932 /* If only one is constant, make it B. */
7936 /* If first constant, both constant, so don't need multiply. */
7940 /* If second not constant, neither is constant, so would need multiply. */
7944 /* One operand is constant, so might not need multiply insn. Generate the
7945 code for the multiply and see if a call or multiply, or long sequence
7946 of insns is generated. */
7955 {
7958 {
7968 {
7971 }
7974 }
7975 }
7985 }
7986 \f
7987 /* Check to see if loop can be terminated by a "decrement and branch until
7988 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7989 Also try reversing an increment loop to a decrement loop
7990 to see if the optimization can be performed.
7991 Value is nonzero if optimization was performed. */
7993 /* This is useful even if the architecture doesn't have such an insn,
7994 because it might change a loops which increments from 0 to n to a loop
7995 which decrements from n to 0. A loop that decrements to zero is usually
7996 faster than one that increments from zero. */
7998 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7999 such as approx_final_value, biv_total_increment, loop_iterations, and
8000 final_[bg]iv_value. */
8002 static int
8006 {
8011 rtx reg;
8012 rtx jump_label;
8013 rtx final_value;
8014 rtx start_value;
8015 rtx new_add_val;
8016 rtx comparison;
8017 rtx before_comparison;
8018 rtx p;
8019 rtx jump;
8020 rtx first_compare;
8025 /* If last insn is a conditional branch, and the insn before tests a
8026 register value, try to optimize it. Otherwise, we can't do anything. */
8035 /* Try to compute whether the compare/branch at the loop end is one or
8036 two instructions. */
8042 else
8045 {
8046 /* If more than one condition is present to control the loop, then
8047 do not proceed, as this function does not know how to rewrite
8048 loop tests with more than one condition.
8050 Look backwards from the first insn in the last comparison
8051 sequence and see if we've got another comparison sequence. */
8053 rtx jump1;
8057 }
8059 /* Check all of the bivs to see if the compare uses one of them.
8060 Skip biv's set more than once because we can't guarantee that
8061 it will be zero on the last iteration. Also skip if the biv is
8062 used between its update and the test insn. */
8065 {
8070 first_compare))
8072 }
8077 /* Look for the case where the basic induction variable is always
8078 nonnegative, and equals zero on the last iteration.
8079 In this case, add a reg_note REG_NONNEG, which allows the
8080 m68k DBRA instruction to be used. */
8088 {
8089 /* Initial value must be greater than 0,
8090 init_val % -dec_value == 0 to ensure that it equals zero on
8091 the last iteration */
8097 {
8098 /* register always nonnegative, add REG_NOTE to branch */
8106 }
8108 /* If the decrement is 1 and the value was tested as >= 0 before
8109 the loop, then we can safely optimize. */
8111 {
8124 {
8132 }
8133 }
8134 }
8137 {
8138 /* Try to change inc to dec, so can apply above optimization. */
8139 /* Can do this if:
8140 all registers modified are induction variables or invariant,
8141 all memory references have non-overlapping addresses
8142 (obviously true if only one write)
8143 allow 2 insns for the compare/jump at the end of the loop. */
8144 /* Also, we must avoid any instructions which use both the reversed
8145 biv and another biv. Such instructions will fail if the loop is
8146 reversed. We meet this condition by requiring that either
8147 no_use_except_counting is true, or else that there is only
8148 one biv. */
8150 /* 1 if the iteration var is used only to count iterations. */
8152 /* 1 if the loop has no memory store, or it has a single memory store
8153 which is reversible. */
8159 {
8163 /* If there are no givs for this biv, and the only exit is the
8164 fall through at the end of the loop, then
8165 see if perhaps there are no uses except to count. */
8169 {
8174 /* An insn that sets the biv is okay. */
8175 ;
8179 {
8180 /* If either of these insns uses the biv and sets a pseudo
8181 that has more than one usage, then the biv has uses
8182 other than counting since it's used to derive a value
8183 that is used more than one time. */
8185 regs);
8187 {
8190 }
8191 }
8193 {
8196 }
8197 }
8199 /* A biv has uses besides counting if it is used to set
8200 another biv. */
8204 {
8207 }
8208 }
8211 /* No need to worry about MEMs. */
8212 ;
8214 {
8219 /* If the loop has a single store, and the destination address is
8220 invariant, then we can't reverse the loop, because this address
8221 might then have the wrong value at loop exit.
8222 This would work if the source was invariant also, however, in that
8223 case, the insn should have been moved out of the loop. */
8226 {
8229 /* If we could prove that each of the memory locations
8230 written to was different, then we could reverse the
8231 store -- but we don't presently have any way of
8232 knowing that. */
8235 /* If the store depends on a register that is set after the
8236 store, it depends on the initial value, and is thus not
8237 reversible. */
8239 {
8246 }
8247 }
8248 }
8249 else
8252 /* This code only acts for innermost loops. Also it simplifies
8253 the memory address check by only reversing loops with
8254 zero or one memory access.
8255 Two memory accesses could involve parts of the same array,
8256 and that can't be reversed.
8257 If the biv is used only for counting, than we don't need to worry
8258 about all these things. */
8264 && reversible_mem_store
8269 {
8270 rtx tem;
8272 /* Loop can be reversed. */
8276 /* Now check other conditions:
8278 The increment must be a constant, as must the initial value,
8279 and the comparison code must be LT.
8281 This test can probably be improved since +/- 1 in the constant
8282 can be obtained by changing LT to LE and vice versa; this is
8283 confusing. */
8286 /* for constants, LE gets turned into LT */
8290 {
8301 comparison_const_width
8303 else
8304 comparison_const_width
8308 comparison_sign_mask
8311 /* If the comparison value is not a loop invariant, then we
8312 can not reverse this loop.
8314 ??? If the insns which initialize the comparison value as
8315 a whole compute an invariant result, then we could move
8316 them out of the loop and proceed with loop reversal. */
8324 /* Normalize the initial value if it is an integer and
8325 has no other use except as a counter. This will allow
8326 a few more loops to be reversed. */
8330 {
8332 /* The code below requires comparison_val to be a multiple
8333 of add_val in order to do the loop reversal, so
8334 round up comparison_val to a multiple of add_val.
8335 Since comparison_value is constant, we know that the
8336 current comparison code is LT. */
8338 comparison_val
8340 /* We postpone overflow checks for COMPARISON_VAL here;
8341 even if there is an overflow, we might still be able to
8342 reverse the loop, if converting the loop exit test to
8343 NE is possible. */
8345 }
8347 /* First check if we can do a vanilla loop reversal. */
8349 /* If we have a decrement_and_branch_on_count,
8350 prefer the NE test, since this will allow that
8351 instruction to be generated. Note that we must
8352 use a vanilla loop reversal if the biv is used to
8353 calculate a giv or has a non-counting use. */
8354 #if ! defined (HAVE_decrement_and_branch_until_zero) \
8355 && defined (HAVE_decrement_and_branch_on_count)
8359 #endif
8361 /* Now do postponed overflow checks on COMPARISON_VAL. */
8364 {
8365 /* Register will always be nonnegative, with value
8366 0 on last iteration */
8370 }
8374 {
8377 }
8378 else
8384 /* If the initial value is not zero, or if the comparison
8385 value is not an exact multiple of the increment, then we
8386 can not reverse this loop. */
8389 {
8392 }
8393 else
8394 {
8397 }
8401 /* Reset these in case we normalized the initial value
8402 and comparison value above. */
8405 {
8407 final_value
8409 }
8412 /* Save some info needed to produce the new insns. */
8417 /* Set start_value; if this is not a CONST_INT, we need
8418 to generate a SUB.
8419 Initialize biv to start_value before loop start.
8420 The old initializing insn will be deleted as a
8421 dead store by flow.c. */
8424 {
8427 }
8429 {
8437 start_value
8443 }
8445 {
8448 initial_value);
8452 start_value
8455 }
8456 else
8457 /* We could handle the other cases too, but it'll be
8458 better to have a testcase first. */
8461 /* We may not have a single insn which can increment a reg, so
8462 create a sequence to hold all the insns from expand_inc. */
8471 /* Update biv info to reflect its new status. */
8476 /* Update loop info. */
8485 /* Inc LABEL_NUSES so that delete_insn will
8486 not delete the label. */
8489 /* Emit an insn after the end of the loop to set the biv's
8490 proper exit value if it is used anywhere outside the loop. */
8496 /* Delete compare/branch at end of loop. */
8501 /* Add new compare/branch insn at end of loop. */
8513 ;
8519 {
8521 {
8522 /* Increment of LABEL_NUSES done above. */
8523 /* Register is now always nonnegative,
8524 so add REG_NONNEG note to the branch. */
8527 }
8529 }
8531 /* No insn may reference both the reversed and another biv or it
8532 will fail (see comment near the top of the loop reversal
8533 code).
8534 Earlier on, we have verified that the biv has no use except
8535 counting, or it is the only biv in this function.
8536 However, the code that computes no_use_except_counting does
8537 not verify reg notes. It's possible to have an insn that
8538 references another biv, and has a REG_EQUAL note with an
8539 expression based on the reversed biv. To avoid this case,
8540 remove all REG_EQUAL notes based on the reversed biv
8541 here. */
8544 {
8547 /* If this is a set of a GIV based on the reversed biv, any
8548 REG_EQUAL notes should still be correct. */
8555 {
8560 else
8562 }
8563 }
8565 /* Mark that this biv has been reversed. Each giv which depends
8566 on this biv, and which is also live past the end of the loop
8567 will have to be fixed up. */
8572 {
8576 else
8578 }
8581 }
8582 }
8583 }
8586 }
8587 \f
8588 /* Verify whether the biv BL appears to be eliminable,
8589 based on the insns in the loop that refer to it.
8591 If ELIMINATE_P is nonzero, actually do the elimination.
8593 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
8594 determine whether invariant insns should be placed inside or at the
8595 start of the loop. */
8597 static int
8603 {
8606 rtx p;
8608 /* Scan all insns in the loop, stopping if we find one that uses the
8609 biv in a way that we cannot eliminate. */
8612 {
8616 rtx note;
8618 /* If this is a libcall that sets a giv, skip ahead to its end. */
8620 {
8624 {
8629 {
8636 }
8637 }
8638 }
8640 /* Closely examine the insn if the biv is mentioned. */
8645 {
8651 }
8653 /* If we are eliminating, kill REG_EQUAL notes mentioning the biv. */
8658 }
8661 {
8666 }
8669 }
8670 \f
8671 /* INSN and REFERENCE are instructions in the same insn chain.
8672 Return nonzero if INSN is first. */
8674 int
8677 {
8681 {
8682 /* Start with test for not first so that INSN == REFERENCE yields not
8683 first. */
8689 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
8690 previous insn, hence the <= comparison below does not work if
8691 P is a note. */
8702 }
8703 }
8705 /* We are trying to eliminate BIV in INSN using GIV. Return nonzero if
8706 the offset that we have to take into account due to auto-increment /
8707 div derivation is zero. */
8708 static int
8711 rtx insn;
8712 {
8713 /* If the giv V had the auto-inc address optimization applied
8714 to it, and INSN occurs between the giv insn and the biv
8715 insn, then we'd have to adjust the value used here.
8716 This is rare, so we don't bother to make this possible. */
8725 }
8727 /* If BL appears in X (part of the pattern of INSN), see if we can
8728 eliminate its use. If so, return 1. If not, return 0.
8730 If BIV does not appear in X, return 1.
8732 If ELIMINATE_P is nonzero, actually do the elimination.
8733 WHERE_INSN/WHERE_BB indicate where extra insns should be added.
8734 Depending on how many items have been moved out of the loop, it
8735 will either be before INSN (when WHERE_INSN is nonzero) or at the
8736 start of the loop (when WHERE_INSN is zero). */
8738 static int
8744 basic_block where_bb;
8745 rtx where_insn;
8746 {
8752 #ifdef HAVE_cc0
8754 #endif
8760 {
8762 /* If we haven't already been able to do something with this BIV,
8763 we can't eliminate it. */
8769 /* If this sets the BIV, it is not a problem. */
8773 /* If this is an insn that defines a giv, it is also ok because
8774 it will go away when the giv is reduced. */
8779 #ifdef HAVE_cc0
8781 {
8782 /* Can replace with any giv that was reduced and
8783 that has (MULT_VAL != 0) and (ADD_VAL == 0).
8784 Require a constant for MULT_VAL, so we know it's nonzero.
8785 ??? We disable this optimization to avoid potential
8786 overflows. */
8794 {
8801 /* If the giv has the opposite direction of change,
8802 then reverse the comparison. */
8806 else
8809 /* We can probably test that giv's reduced reg. */
8812 }
8814 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
8815 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
8816 Require a constant for MULT_VAL, so we know it's nonzero.
8817 ??? Do this only if ADD_VAL is a pointer to avoid a potential
8818 overflow problem. */
8830 {
8837 /* If the giv has the opposite direction of change,
8838 then reverse the comparison. */
8842 else
8846 /* Replace biv with the giv's reduced register. */
8851 /* Insn doesn't support that constant or invariant. Copy it
8852 into a register (it will be a loop invariant.) */
8859 /* Substitute the new register for its invariant value in
8860 the compare expression. */
8864 }
8865 }
8866 #endif
8873 /* See if either argument is the biv. */
8878 else
8882 {
8883 /* First try to replace with any giv that has constant positive
8884 mult_val and constant add_val. We might be able to support
8885 negative mult_val, but it seems complex to do it in general. */
8897 {
8901 /* Don't eliminate if the linear combination that makes up
8902 the giv overflows when it is applied to ARG. */
8904 {
8905 rtx add_val;
8909 else
8915 }
8920 /* Replace biv with the giv's reduced reg. */
8923 /* If all constants are actually constant integers and
8924 the derived constant can be directly placed in the COMPARE,
8925 do so. */
8928 {
8931 }
8932 else
8933 {
8934 /* Otherwise, load it into a register. */
8939 }
8945 }
8947 /* Look for giv with positive constant mult_val and nonconst add_val.
8948 Insert insns to calculate new compare value.
8949 ??? Turn this off due to possible overflow. */
8957 {
8958 rtx tem;
8968 /* Replace biv with giv's reduced register. */
8972 /* Compute value to compare against. */
8976 /* Use it in this insn. */
8980 }
8981 }
8983 {
8985 {
8986 /* Look for giv with constant positive mult_val and nonconst
8987 add_val. Insert insns to compute new compare value.
8988 ??? Turn this off due to possible overflow. */
8995 {
8996 rtx tem;
9006 /* Replace biv with giv's reduced register. */
9010 /* Compute value to compare against. */
9017 }
9018 }
9020 /* This code has problems. Basically, you can't know when
9021 seeing if we will eliminate BL, whether a particular giv
9022 of ARG will be reduced. If it isn't going to be reduced,
9023 we can't eliminate BL. We can try forcing it to be reduced,
9024 but that can generate poor code.
9026 The problem is that the benefit of reducing TV, below should
9027 be increased if BL can actually be eliminated, but this means
9028 we might have to do a topological sort of the order in which
9029 we try to process biv. It doesn't seem worthwhile to do
9030 this sort of thing now. */
9032 #if 0
9033 /* Otherwise the reg compared with had better be a biv. */
9038 /* Look for a pair of givs, one for each biv,
9039 with identical coefficients. */
9041 {
9053 {
9060 /* Replace biv with its giv's reduced reg. */
9062 /* Replace other operand with the other giv's
9063 reduced reg. */
9066 }
9067 }
9068 #endif
9069 }
9071 /* If we get here, the biv can't be eliminated. */
9075 /* If this address is a DEST_ADDR giv, it doesn't matter if the
9076 biv is used in it, since it will be replaced. */
9084 }
9086 /* See if any subexpression fails elimination. */
9089 {
9091 {
9104 }
9105 }
9108 }
9109 \f
9110 /* Return nonzero if the last use of REG
9111 is in an insn following INSN in the same basic block. */
9113 static int
9115 rtx reg;
9116 rtx insn;
9117 {
9118 rtx n;
9122 {
9125 }
9127 }
9128 \f
9129 /* Called via `note_stores' to record the initial value of a biv. Here we
9130 just record the location of the set and process it later. */
9132 static void
9134 rtx dest;
9135 rtx set;
9137 {
9148 /* If this is the first set found, record it. */
9150 {
9153 }
9154 }
9155 \f
9156 /* If any of the registers in X are "old" and currently have a last use earlier
9157 than INSN, update them to have a last use of INSN. Their actual last use
9158 will be the previous insn but it will not have a valid uid_luid so we can't
9159 use it. X must be a source expression only. */
9161 static void
9163 rtx x;
9164 rtx insn;
9165 {
9166 /* Check for the case where INSN does not have a valid luid. In this case,
9167 there is no need to modify the regno_last_uid, as this can only happen
9168 when code is inserted after the loop_end to set a pseudo's final value,
9169 and hence this insn will never be the last use of x.
9170 ???? This comment is not correct. See for example loop_givs_reduce.
9171 This may insert an insn before another new insn. */
9175 {
9177 }
9178 else
9179 {
9183 {
9189 }
9190 }
9191 }
9192 \f
9193 /* Given an insn INSN and condition COND, return the condition in a
9194 canonical form to simplify testing by callers. Specifically:
9196 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
9197 (2) Both operands will be machine operands; (cc0) will have been replaced.
9198 (3) If an operand is a constant, it will be the second operand.
9199 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
9200 for GE, GEU, and LEU.
9202 If the condition cannot be understood, or is an inequality floating-point
9203 comparison which needs to be reversed, 0 will be returned.
9205 If REVERSE is nonzero, then reverse the condition prior to canonizing it.
9207 If EARLIEST is nonzero, it is a pointer to a place where the earliest
9208 insn used in locating the condition was found. If a replacement test
9209 of the condition is desired, it should be placed in front of that
9210 insn and we will be sure that the inputs are still valid.
9212 If WANT_REG is nonzero, we wish the condition to be relative to that
9213 register, if possible. Therefore, do not canonicalize the condition
9214 further. */
9216 rtx
9218 rtx insn;
9219 rtx cond;
9222 rtx want_reg;
9223 {
9226 rtx set;
9227 rtx tem;
9245 /* If we are comparing a register with zero, see if the register is set
9246 in the previous insn to a COMPARE or a comparison operation. Perform
9247 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
9248 in cse.c */
9253 {
9254 /* Set nonzero when we find something of interest. */
9257 #ifdef HAVE_cc0
9258 /* If comparison with cc0, import actual comparison from compare
9259 insn. */
9261 {
9272 }
9273 #endif
9275 /* If this is a COMPARE, pick up the two things being compared. */
9277 {
9281 }
9285 /* Go back to the previous insn. Stop if it is not an INSN. We also
9286 stop if it isn't a single set or if it has a REG_INC note because
9287 we don't want to bother dealing with it. */
9301 /* If this is setting OP0, get what it sets it to if it looks
9302 relevant. */
9304 {
9306 #ifdef FLOAT_STORE_FLAG_VALUE
9307 REAL_VALUE_TYPE fsfv;
9308 #endif
9310 /* ??? We may not combine comparisons done in a CCmode with
9311 comparisons not done in a CCmode. This is to aid targets
9312 like Alpha that have an IEEE compliant EQ instruction, and
9313 a non-IEEE compliant BEQ instruction. The use of CCmode is
9314 actually artificial, simply to prevent the combination, but
9315 should not affect other platforms.
9317 However, we must allow VOIDmode comparisons to match either
9318 CCmode or non-CCmode comparison, because some ports have
9319 modeless comparisons inside branch patterns.
9321 ??? This mode check should perhaps look more like the mode check
9322 in simplify_comparison in combine. */
9330 && (STORE_FLAG_VALUE
9333 #ifdef FLOAT_STORE_FLAG_VALUE
9338 #endif
9339 ))
9350 && (STORE_FLAG_VALUE
9353 #ifdef FLOAT_STORE_FLAG_VALUE
9358 #endif
9359 ))
9365 {
9368 }
9369 else
9371 }
9374 /* If this sets OP0, but not directly, we have to give up. */
9378 {
9382 {
9387 }
9392 }
9393 }
9395 /* If constant is first, put it last. */
9399 /* If OP0 is the result of a comparison, we weren't able to find what
9400 was really being compared, so fail. */
9404 /* Canonicalize any ordered comparison with integers involving equality
9405 if we can do computations in the relevant mode and we do not
9406 overflow. */
9411 {
9414 unsigned HOST_WIDE_INT max_val
9418 {
9424 /* When cross-compiling, const_val might be sign-extended from
9425 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
9445 }
9446 }
9448 #ifdef HAVE_cc0
9449 /* Never return CC0; return zero instead. */
9452 #endif
9455 }
9457 /* Given a jump insn JUMP, return the condition that will cause it to branch
9458 to its JUMP_LABEL. If the condition cannot be understood, or is an
9459 inequality floating-point comparison which needs to be reversed, 0 will
9460 be returned.
9462 If EARLIEST is nonzero, it is a pointer to a place where the earliest
9463 insn used in locating the condition was found. If a replacement test
9464 of the condition is desired, it should be placed in front of that
9465 insn and we will be sure that the inputs are still valid. */
9467 rtx
9469 rtx jump;
9471 {
9472 rtx cond;
9474 rtx set;
9476 /* If this is not a standard conditional jump, we can't parse it. */
9484 /* If this branches to JUMP_LABEL when the condition is false, reverse
9485 the condition. */
9486 reverse
9491 }
9493 /* Similar to above routine, except that we also put an invariant last
9494 unless both operands are invariants. */
9496 rtx
9499 rtx x;
9500 {
9510 }
9512 /* Scan the function and determine whether it has indirect (computed) jumps.
9514 This is taken mostly from flow.c; similar code exists elsewhere
9515 in the compiler. It may be useful to put this into rtlanal.c. */
9516 static int
9518 rtx start;
9519 {
9520 rtx insn;
9527 }
9529 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
9530 documentation for LOOP_MEMS for the definition of `appropriate'.
9531 This function is called from prescan_loop via for_each_rtx. */
9533 static int
9537 {
9546 {
9551 /* We're not interested in MEMs that are only clobbered. */
9555 /* We're not interested in the MEM associated with a
9556 CONST_DOUBLE, so there's no need to traverse into this. */
9560 /* We're not interested in any MEMs that only appear in notes. */
9564 /* This is not a MEM. */
9566 }
9568 /* See if we've already seen this MEM. */
9571 {
9573 /* The modes of the two memory accesses are different. If
9574 this happens, something tricky is going on, and we just
9575 don't optimize accesses to this MEM. */
9579 }
9581 /* Resize the array, if necessary. */
9583 {
9586 else
9592 }
9594 /* Actually insert the MEM. */
9596 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
9597 because we can't put it in a register. We still store it in the
9598 table, though, so that if we see the same address later, but in a
9599 non-BLK mode, we'll not think we can optimize it at that point. */
9605 }
9608 /* Allocate REGS->ARRAY or reallocate it if it is too small.
9610 Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
9611 register that is modified by an insn between FROM and TO. If the
9612 value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
9613 more, stop incrementing it, to avoid overflow.
9615 Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
9616 register I is used, if it is only used once. Otherwise, it is set
9617 to 0 (for no uses) or const0_rtx for more than one use. This
9618 parameter may be zero, in which case this processing is not done.
9620 Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
9621 optimize register I. */
9623 static void
9627 {
9630 /* last_set[n] is nonzero iff reg n has been set in the current
9631 basic block. In that case, it is the insn that last set reg n. */
9633 rtx insn;
9639 /* Grow the regs array if not allocated or too small. */
9641 {
9647 /* Zero the new elements. */
9650 }
9652 /* Clear previously scanned fields but do not clear n_times_set. */
9654 {
9658 }
9662 /* Scan the loop, recording register usage. */
9665 {
9667 {
9668 /* Record registers that have exactly one use. */
9671 /* Include uses in REG_EQUAL notes. */
9679 {
9683 last_set);
9684 }
9685 }
9690 /* Invalidate all registers used for function argument passing.
9691 We check rtx_varies_p for the same reason as below, to allow
9692 optimizing PIC calculations. */
9694 {
9695 rtx link;
9697 link;
9699 {
9706 }
9707 }
9708 }
9710 /* Invalidate all hard registers clobbered by calls. With one exception:
9711 a call-clobbered PIC register is still function-invariant for our
9712 purposes, since we can hoist any PIC calculations out of the loop.
9713 Thus the call to rtx_varies_p. */
9718 {
9721 }
9723 #ifdef AVOID_CCMODE_COPIES
9724 /* Don't try to move insns which set CC registers if we should not
9725 create CCmode register copies. */
9729 #endif
9731 /* Set regs->array[I].n_times_set for the new registers. */
9736 }
9738 /* Returns the number of real INSNs in the LOOP. */
9740 static int
9743 {
9745 rtx insn;
9753 }
9755 /* Move MEMs into registers for the duration of the loop. */
9757 static void
9760 {
9767 rtx end_label;
9768 /* Nonzero if the next instruction may never be executed. */
9775 /* We cannot use next_label here because it skips over normal insns. */
9780 /* Check to see if it's possible that some instructions in the loop are
9781 never executed. Also check if there is a goto out of the loop other
9782 than right after the end of the loop. */
9786 {
9790 /* If we enter the loop in the middle, and scan
9791 around to the beginning, don't set maybe_never
9792 for that. This must be an unconditional jump,
9793 otherwise the code at the top of the loop might
9794 never be executed. Unconditional jumps are
9795 followed a by barrier then loop end. */
9800 {
9801 /* If this is a jump outside of the loop but not right
9802 after the end of the loop, we would have to emit new fixup
9803 sequences for each such label. */
9805 JUMP_INSN is executed, we must be conservative. */
9814 /* Something complicated. */
9816 else
9817 /* If there are any more instructions in the loop, they
9818 might not be reached. */
9820 }
9823 }
9825 /* Find start of the extended basic block that enters the loop. */
9829 ;
9834 /* Build table of mems that get set to constant values before the
9835 loop. */
9839 /* Actually move the MEMs. */
9841 {
9842 regset_head load_copies;
9843 regset_head store_copies;
9845 rtx reg;
9847 rtx mem_list_entry;
9851 /* There's no telling whether or not MEM is modified. */
9854 /* Go through the MEMs written to in the loop to see if this
9855 one is aliased by one of them. */
9858 {
9863 {
9864 /* MEM is indeed aliased by this store. */
9867 }
9869 }
9875 /* If this MEM is written to, we must be sure that there
9876 are no reads from another MEM that aliases this one. */
9878 {
9882 {
9886 VOIDmode,
9888 rtx_varies_p))
9889 {
9890 /* It's not safe to hoist loop_info->mems[i] out of
9891 the loop because writes to it might not be
9892 seen by reads from loop_info->mems[j]. */
9895 }
9896 }
9897 }
9900 /* We can't access the MEM outside the loop; it might
9901 cause a trap that wouldn't have happened otherwise. */
9905 /* We thought we were going to lift this MEM out of the
9906 loop, but later discovered that we could not. */
9912 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
9913 order to keep scan_loop from moving stores to this MEM
9914 out of the loop just because this REG is neither a
9915 user-variable nor used in the loop test. */
9920 /* Now, replace all references to the MEM with the
9921 corresponding pseudos. */
9926 {
9928 {
9929 rtx set;
9933 /* See if this copies the mem into a register that isn't
9934 modified afterwards. We'll try to do copy propagation
9935 a little further on. */
9937 /* @@@ This test is _way_ too conservative. */
9938 && ! maybe_never
9946 /* See if this copies the mem from a register that isn't
9947 modified afterwards. We'll try to remove the
9948 redundant copy later on by doing a little register
9949 renaming and copy propagation. This will help
9950 to untangle things for the BIV detection code. */
9952 && ! maybe_never
9960 /* If this is a call which uses / clobbers this memory
9961 location, we must not change the interface here. */
9965 {
9969 }
9970 else
9971 /* Replace the memory reference with the shadow register. */
9974 }
9979 }
9984 /* We couldn't replace all occurrences of the MEM. */
9986 else
9987 {
9988 /* Load the memory immediately before LOOP->START, which is
9989 the NOTE_LOOP_BEG. */
9991 rtx set;
9997 {
10001 {
10005 /* Extending hard register lifetimes causes crash
10006 on SRC targets. Doing so on non-SRC is
10007 probably also not good idea, since we most
10008 probably have pseudoregister equivalence as
10009 well. */
10012 }
10013 /* Use the constant equivalence if that is cheap enough. */
10019 {
10022 }
10024 /* If best_equiv is nonzero, we know that MEM is set to a
10025 constant or register before the loop. We will use this
10026 knowledge to initialize the shadow register with that
10027 constant or reg rather than by loading from MEM. */
10030 }
10035 {
10038 {
10041 }
10042 }
10048 {
10050 {
10053 }
10055 /* Store the memory immediately after END, which is
10056 the NOTE_LOOP_END. */
10059 }
10062 {
10067 }
10069 /* Attempt a bit of copy propagation. This helps untangle the
10070 data flow, and enables {basic,general}_induction_var to find
10071 more bivs/givs. */
10072 EXECUTE_IF_SET_IN_REG_SET
10074 {
10076 });
10079 EXECUTE_IF_SET_IN_REG_SET
10081 {
10083 });
10085 }
10086 }
10089 {
10090 /* Now, we need to replace all references to the previous exit
10091 label with the new one. */
10092 rtx_pair rr;
10097 {
10100 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
10101 field. This is not handled by for_each_rtx because it doesn't
10102 handle unprinted ('0') fields. We need to update JUMP_LABEL
10103 because the immediately following unroll pass will use it.
10104 replace_label would not work anyways, because that only handles
10105 LABEL_REFs. */
10108 }
10109 }
10112 }
10114 /* For communication between note_reg_stored and its caller. */
10115 struct note_reg_stored_arg
10116 {
10118 rtx reg;
10119 };
10121 /* Called via note_stores, record in SET_SEEN whether X, which is written,
10122 is equal to ARG. */
10123 static void
10127 {
10131 }
10133 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
10134 There must be exactly one insn that sets this pseudo; it will be
10135 deleted if all replacements succeed and we can prove that the register
10136 is not used after the loop. */
10138 static void
10141 rtx replacement;
10143 {
10144 /* This is the reg that we are copying from. */
10147 rtx insn;
10148 /* These help keep track of whether we replaced all uses of the reg. */
10155 {
10156 rtx set;
10158 /* Only substitute within one extended basic block from the initializing
10159 insn. */
10166 /* Is this the initializing insn? */
10171 {
10178 }
10180 /* Only substitute after seeing the initializing insn. */
10182 {
10189 /* Stop replacing when REPLACEMENT is modified. */
10194 {
10197 /* It is possible that we've turned previously valid REG_EQUAL to
10198 invalid, as we change the REGNO to REPLACEMENT and unlike REGNO,
10199 REPLACEMENT is modified, we get different meaning. */
10203 }
10204 }
10205 }
10209 {
10213 {
10214 rtx first;
10215 rtx retval_note;
10217 /* Assume we're just deleting INIT_INSN. */
10219 /* Look for REG_RETVAL note. If we're deleting the end of
10220 the libcall sequence, the whole sequence can go. */
10222 /* If we found a REG_RETVAL note, find the first instruction
10223 in the sequence. */
10227 /* Delete the instructions. */
10229 }
10232 }
10233 }
10235 /* Replace all the instructions from FIRST up to and including LAST
10236 with NOTE_INSN_DELETED notes. */
10238 static void
10240 rtx first;
10241 rtx last;
10242 {
10244 {
10250 /* If this was the LAST instructions we're supposed to delete,
10251 we're done. */
10256 }
10257 }
10259 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
10260 loop LOOP if the order of the sets of these registers can be
10261 swapped. There must be exactly one insn within the loop that sets
10262 this pseudo followed immediately by a move insn that sets
10263 REPLACEMENT with REGNO. */
10264 static void
10267 rtx replacement;
10269 {
10270 rtx insn;
10279 {
10280 /* Search for the insn that copies REGNO to NEW_REGNO? */
10288 }
10291 {
10292 rtx prev_insn;
10293 rtx prev_set;
10295 /* Some DEF-USE info would come in handy here to make this
10296 function more general. For now, just check the previous insn
10297 which is the most likely candidate for setting REGNO. */
10305 {
10306 /* We have:
10307 (set (reg regno) (expr))
10308 (set (reg new_regno) (reg regno))
10310 so try converting this to:
10311 (set (reg new_regno) (expr))
10312 (set (reg regno) (reg new_regno))
10314 The former construct is often generated when a global
10315 variable used for an induction variable is shadowed by a
10316 register (NEW_REGNO). The latter construct improves the
10317 chances of GIV replacement and BIV elimination. */
10327 {
10334 /* Update first use of REGNO. */
10338 /* Now perform copy propagation to hopefully
10339 remove all uses of REGNO within the loop. */
10341 }
10342 }
10343 }
10344 }
10346 /* Replace MEM with its associated pseudo register. This function is
10347 called from load_mems via for_each_rtx. DATA is actually a pointer
10348 to a structure describing the instruction currently being scanned
10349 and the MEM we are currently replacing. */
10351 static int
10355 {
10363 {
10368 /* We're not interested in the MEM associated with a
10369 CONST_DOUBLE, so there's no need to traverse into one. */
10373 /* This is not a MEM. */
10375 }
10378 /* This is not the MEM we are currently replacing. */
10381 /* Actually replace the MEM. */
10385 }
10387 static void
10389 rtx insn;
10390 rtx mem;
10391 rtx reg;
10392 {
10393 loop_replace_args args;
10400 }
10402 /* Replace one register with another. Called through for_each_rtx; PX points
10403 to the rtx being scanned. DATA is actually a pointer to
10404 a structure of arguments. */
10406 static int
10410 {
10421 }
10423 static void
10425 rtx insn;
10426 rtx reg;
10427 rtx replacement;
10428 {
10429 loop_replace_args args;
10436 }
10438 /* Replace occurrences of the old exit label for the loop with the new
10439 one. DATA is an rtx_pair containing the old and new labels,
10440 respectively. */
10442 static int
10446 {
10465 }
10466 \f
10467 /* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB
10468 (ignored in the interim). */
10470 static rtx
10473 basic_block where_bb ATTRIBUTE_UNUSED;
10474 rtx where_insn;
10475 rtx pattern;
10476 {
10478 }
10481 /* If WHERE_INSN is nonzero emit insn for PATTERN before WHERE_INSN
10482 in basic block WHERE_BB (ignored in the interim) within the loop
10483 otherwise hoist PATTERN into the loop pre-header. */
10485 rtx
10488 basic_block where_bb ATTRIBUTE_UNUSED;
10489 rtx where_insn;
10490 rtx pattern;
10491 {
10495 }
10498 /* Emit call insn for PATTERN before WHERE_INSN in basic block
10499 WHERE_BB (ignored in the interim) within the loop. */
10501 static rtx
10504 basic_block where_bb ATTRIBUTE_UNUSED;
10505 rtx where_insn;
10506 rtx pattern;
10507 {
10509 }
10512 /* Hoist insn for PATTERN into the loop pre-header. */
10514 rtx
10517 rtx pattern;
10518 {
10520 }
10523 /* Hoist call insn for PATTERN into the loop pre-header. */
10525 static rtx
10528 rtx pattern;
10529 {
10531 }
10534 /* Sink insn for PATTERN after the loop end. */
10536 rtx
10539 rtx pattern;
10540 {
10542 }
10544 /* bl->final_value can be eighter general_operand or PLUS of general_operand
10545 and constant. Emit sequence of instructions to load it into REG. */
10546 static rtx
10549 {
10550 rtx seq;
10558 }
10560 /* If the loop has multiple exits, emit insn for PATTERN before the
10561 loop to ensure that it will always be executed no matter how the
10562 loop exits. Otherwise, emit the insn for PATTERN after the loop,
10563 since this is slightly more efficient. */
10565 static rtx
10568 rtx pattern;
10569 {
10572 else
10574 }
10575 \f
10576 static void
10581 {
10589 iv_num++;
10594 {
10597 }
10598 }
10601 static void
10606 {
10608 rtx incr;
10619 {
10622 }
10624 {
10627 }
10631 {
10635 }
10638 {
10642 }
10644 /* List the increments. */
10646 {
10650 }
10652 /* List the givs. */
10654 {
10659 else
10662 }
10663 }
10666 static void
10671 {
10682 {
10686 }
10689 }
10692 static void
10697 {
10704 else
10720 {
10722 {
10734 }
10735 }
10746 {
10750 }
10753 }
10756 void
10759 {
10761 }
10764 void
10767 {
10769 }
10772 void
10775 {
10777 }
10780 void
10783 {
10785 }
10788 #define LOOP_BLOCK_NUM_1(INSN) \
10789 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
10791 /* The notes do not have an assigned block, so look at the next insn. */
10792 #define LOOP_BLOCK_NUM(INSN) \
10793 ((INSN) ? (GET_CODE (INSN) == NOTE \
10794 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
10795 : LOOP_BLOCK_NUM_1 (INSN)) \
10796 : -1)
10798 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
10800 static void
10805 {
10806 rtx label;
10811 /* Print diagnostics to compare our concept of a loop with
10812 what the loop notes say. */
10827 {
10847 {
10850 {
10853 }
10854 }
10857 /* This can happen when a marked loop appears as two nested loops,
10858 say from while (a || b) {}. The inner loop won't match
10859 the loop markers but the outer one will. */
10862 }
10863 }
10865 /* Call this function from the debugger to dump LOOP. */
10867 void
10870 {
10872 }
10874 /* Call this function from the debugger to dump LOOPS. */
10876 void
10879 {
10881 }