| blob | fa74b8e32301ecf2f4d4251193ea806d9af50715 |
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, 2003, 2004 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.
27 Basic induction variables (BIVs) are a pseudo registers which are set within
28 a loop only by incrementing or decrementing its value. General induction
29 variables (GIVs) are pseudo registers with a value which is a linear function
30 of a basic induction variable. BIVs are recognized by `basic_induction_var';
31 GIVs by `general_induction_var'.
33 Once induction variables are identified, strength reduction is applied to the
34 general induction variables, and induction variable elimination is applied to
35 the basic induction variables.
37 It also finds cases where
38 a register is set within the loop by zero-extending a narrower value
39 and changes these to zero the entire register once before the loop
40 and merely copy the low part within the loop.
42 Most of the complexity is in heuristics to decide when it is worth
43 while to do these things. */
70 /* Not really meaningful values, but at least something. */
71 #ifndef SIMULTANEOUS_PREFETCHES
72 #define SIMULTANEOUS_PREFETCHES 3
73 #endif
74 #ifndef PREFETCH_BLOCK
75 #define PREFETCH_BLOCK 32
76 #endif
77 #ifndef HAVE_prefetch
78 #define HAVE_prefetch 0
79 #define CODE_FOR_prefetch 0
80 #define gen_prefetch(a,b,c) (abort(), NULL_RTX)
81 #endif
83 /* Give up the prefetch optimizations once we exceed a given threshold.
84 It is unlikely that we would be able to optimize something in a loop
85 with so many detected prefetches. */
86 #define MAX_PREFETCHES 100
87 /* The number of prefetch blocks that are beneficial to fetch at once before
88 a loop with a known (and low) iteration count. */
89 #define PREFETCH_BLOCKS_BEFORE_LOOP_MAX 6
90 /* For very tiny loops it is not worthwhile to prefetch even before the loop,
91 since it is likely that the data are already in the cache. */
92 #define PREFETCH_BLOCKS_BEFORE_LOOP_MIN 2
94 /* Parameterize some prefetch heuristics so they can be turned on and off
95 easily for performance testing on new architectures. These can be
96 defined in target-dependent files. */
98 /* Prefetch is worthwhile only when loads/stores are dense. */
99 #ifndef PREFETCH_ONLY_DENSE_MEM
100 #define PREFETCH_ONLY_DENSE_MEM 1
101 #endif
103 /* Define what we mean by "dense" loads and stores; This value divided by 256
104 is the minimum percentage of memory references that worth prefetching. */
105 #ifndef PREFETCH_DENSE_MEM
106 #define PREFETCH_DENSE_MEM 220
107 #endif
109 /* Do not prefetch for a loop whose iteration count is known to be low. */
110 #ifndef PREFETCH_NO_LOW_LOOPCNT
111 #define PREFETCH_NO_LOW_LOOPCNT 1
112 #endif
114 /* Define what we mean by a "low" iteration count. */
115 #ifndef PREFETCH_LOW_LOOPCNT
116 #define PREFETCH_LOW_LOOPCNT 32
117 #endif
119 /* Do not prefetch for a loop that contains a function call; such a loop is
120 probably not an internal loop. */
121 #ifndef PREFETCH_NO_CALL
122 #define PREFETCH_NO_CALL 1
123 #endif
125 /* Do not prefetch accesses with an extreme stride. */
126 #ifndef PREFETCH_NO_EXTREME_STRIDE
127 #define PREFETCH_NO_EXTREME_STRIDE 1
128 #endif
130 /* Define what we mean by an "extreme" stride. */
131 #ifndef PREFETCH_EXTREME_STRIDE
132 #define PREFETCH_EXTREME_STRIDE 4096
133 #endif
135 /* Define a limit to how far apart indices can be and still be merged
136 into a single prefetch. */
137 #ifndef PREFETCH_EXTREME_DIFFERENCE
138 #define PREFETCH_EXTREME_DIFFERENCE 4096
139 #endif
141 /* Issue prefetch instructions before the loop to fetch data to be used
142 in the first few loop iterations. */
143 #ifndef PREFETCH_BEFORE_LOOP
144 #define PREFETCH_BEFORE_LOOP 1
145 #endif
147 /* Do not handle reversed order prefetches (negative stride). */
148 #ifndef PREFETCH_NO_REVERSE_ORDER
149 #define PREFETCH_NO_REVERSE_ORDER 1
150 #endif
152 /* Prefetch even if the GIV is in conditional code. */
153 #ifndef PREFETCH_CONDITIONAL
154 #define PREFETCH_CONDITIONAL 1
155 #endif
157 #define LOOP_REG_LIFETIME(LOOP, REGNO) \
158 ((REGNO_LAST_LUID (REGNO) - REGNO_FIRST_LUID (REGNO)))
160 #define LOOP_REG_GLOBAL_P(LOOP, REGNO) \
161 ((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
162 || REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start)))
164 #define LOOP_REGNO_NREGS(REGNO, SET_DEST) \
165 ((REGNO) < FIRST_PSEUDO_REGISTER \
166 ? (int) HARD_REGNO_NREGS ((REGNO), GET_MODE (SET_DEST)) : 1)
169 /* Vector mapping INSN_UIDs to luids.
170 The luids are like uids but increase monotonically always.
171 We use them to see whether a jump comes from outside a given loop. */
175 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
176 number the insn is contained in. */
180 /* 1 + largest uid of any insn. */
184 /* Number of loops detected in current function. Used as index to the
185 next few tables. */
189 /* Bound on pseudo register number before loop optimization.
190 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
193 /* The value to pass to the next call of reg_scan_update. */
195 \f
196 /* During the analysis of a loop, a chain of `struct movable's
197 is made to record all the movable insns found.
198 Then the entire chain can be scanned to decide which to move. */
200 struct movable
201 {
206 of any registers used within the LIBCALL. */
208 that must be moved with this one. */
211 may be adjusted when matching movables
212 that load the same value are found. */
214 including other movables that force this
215 or match this one. */
217 a low part that we should avoid changing when
218 clearing the rest of the reg. */
222 /* If PARTIAL is 1, GLOBAL means something different:
223 that the reg is live outside the range from where it is set
224 to the following label. */
228 In particular, moving it does not make it
229 invariant. */
231 load SRC, rather than copying INSN. */
233 first insn of a consecutive sets group. */
236 the original insn with a copy from that
237 pseudo, rather than deleting it. */
241 };
246 /* Forward declarations. */
261 #if 0
263 #endif
304 rtx *);
373 {
374 rtx match;
375 rtx replacement;
376 rtx insn;
379 /* Nonzero iff INSN is between START and END, inclusive. */
380 #define INSN_IN_RANGE_P(INSN, START, END) \
381 (INSN_UID (INSN) < max_uid_for_loop \
382 && INSN_LUID (INSN) >= INSN_LUID (START) \
383 && INSN_LUID (INSN) <= INSN_LUID (END))
385 /* Indirect_jump_in_function is computed once per function. */
393 \f
394 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
395 copy the value of the strength reduced giv to its original register. */
398 /* Cost of using a register, to normalize the benefits of a giv. */
401 void
403 {
409 }
410 \f
411 /* Compute the mapping from uids to luids.
412 LUIDs are numbers assigned to insns, like uids,
413 except that luids increase monotonically through the code.
414 Start at insn START and stop just before END. Assign LUIDs
415 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
416 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 {
446 rtx insn;
461 /* Count the number of loops. */
465 {
468 max_loop_num++;
469 }
471 /* Don't waste time if no loops. */
477 /* Get size to use for tables indexed by uids.
478 Leave some space for labels allocated by find_and_verify_loops. */
484 /* Allocate storage for array of loops. */
487 /* Find and process each loop.
488 First, find them, and record them in order of their beginnings. */
491 /* Allocate and initialize auxiliary loop information. */
496 /* Now find all register lifetimes. This must be done after
497 find_and_verify_loops, because it might reorder the insns in the
498 function. */
501 /* This must occur after reg_scan so that registers created by gcse
502 will have entries in the register tables.
504 We could have added a call to reg_scan after gcse_main in toplev.c,
505 but moving this call to init_alias_analysis is more efficient. */
508 /* See if we went too far. Note that get_max_uid already returns
509 one more that the maximum uid of all insn. */
512 /* Now reset it to the actual size we need. See above. */
515 /* find_and_verify_loops has already called compute_luids, but it
516 might have rearranged code afterwards, so we need to recompute
517 the luids now. */
520 /* Don't leave gaps in uid_luid for insns that have been
521 deleted. It is possible that the first or last insn
522 using some register has been deleted by cross-jumping.
523 Make sure that uid_luid for that former insn's uid
524 points to the general area where that insn used to be. */
526 {
530 }
535 /* Determine if the function has indirect jump. On some systems
536 this prevents low overhead loop instructions from being used. */
539 /* Now scan the loops, last ones first, since this means inner ones are done
540 before outer ones. */
542 {
546 {
549 }
550 }
554 /* 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
572 {
576 {
578 /* Go to the top of the loop, and continue there. */
580 else
581 /* We're done. */
583 }
586 /* We're done. */
590 }
592 /* Find any register references hidden inside X and add them to
593 the dependency list DEPS. This is used to look inside CLOBBER (MEM
594 when checking whether a PARALLEL can be pulled out of a loop. */
596 static rtx
598 {
602 else
603 {
607 {
613 }
614 }
616 }
618 /* Optimize one loop described by LOOP. */
620 /* ??? Could also move memory writes out of loops if the destination address
621 is invariant, the source is invariant, the memory write is not volatile,
622 and if we can prove that no read inside the loop can read this address
623 before the write occurs. If there is a read of this address after the
624 write, then we can also mark the memory read as invariant. */
626 static void
628 {
634 rtx p;
635 /* 1 if we are scanning insns that could be executed zero times. */
637 /* 1 if we are scanning insns that might never be executed
638 due to a subroutine call which might exit before they are reached. */
640 /* Number of insns in the loop. */
644 /* The SET from an insn, if it is the only SET in the insn. */
646 /* Chain describing insns movable in current loop. */
648 /* Ratio of extra register life span we can justify
649 for saving an instruction. More if loop doesn't call subroutines
650 since in that case saving an insn makes more difference
651 and more registers are available. */
653 /* Nonzero if we are scanning instructions in a sub-loop. */
662 /* Determine whether this loop starts with a jump down to a test at
663 the end. This will occur for a small number of loops with a test
664 that is too complex to duplicate in front of the loop.
666 We search for the first insn or label in the loop, skipping NOTEs.
667 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
668 (because we might have a loop executed only once that contains a
669 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
670 (in case we have a degenerate loop).
672 Note that if we mistakenly think that a loop is entered at the top
673 when, in fact, it is entered at the exit test, the only effect will be
674 slightly poorer optimization. Making the opposite error can generate
675 incorrect code. Since very few loops now start with a jump to the
676 exit test, the code here to detect that case is very conservative. */
679 p != loop_end
685 ;
689 /* If loop end is the end of the current function, then emit a
690 NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy
691 note insn. This is the position we use when sinking insns out of
692 the loop. */
695 else
698 /* Set up variables describing this loop. */
702 /* If loop has a jump before the first label,
703 the true entry is the target of that jump.
704 Start scan from there.
705 But record in LOOP->TOP the place where the end-test jumps
706 back to so we can scan that after the end of the loop. */
708 /* Loop entry must be unconditional jump (and not a RETURN) */
711 /* Check to see whether the jump actually
712 jumps out of the loop (meaning it's no loop).
713 This case can happen for things like
714 do {..} while (0). If this label was generated previously
715 by loop, we can't tell anything about it and have to reject
716 the loop. */
718 {
721 }
723 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
724 as required by loop_reg_used_before_p. So skip such loops. (This
725 test may never be true, but it's best to play it safe.)
727 Also, skip loops where we do not start scanning at a label. This
728 test also rejects loops starting with a JUMP_INSN that failed the
729 test above. */
733 {
738 }
740 /* Allocate extra space for REGs that might be created by load_mems.
741 We allocate a little extra slop as well, in the hopes that we
742 won't have to reallocate the regs array. */
747 {
753 }
755 /* Scan through the loop finding insns that are safe to move.
756 Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
757 this reg will be considered invariant for subsequent insns.
758 We consider whether subsequent insns use the reg
759 in deciding whether it is worth actually moving.
761 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
762 and therefore it is possible that the insns we are scanning
763 would never be executed. At such times, we must make sure
764 that it is safe to execute the insn once instead of zero times.
765 When MAYBE_NEVER is 0, all insns will be executed at least once
766 so that is not a problem. */
771 {
773 in_libcall--;
775 {
776 /* Do not scan past an optimization barrier. */
781 in_libcall++;
785 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
787 #endif
789 {
797 /* Figure out what to use as a source of this insn. If a
798 REG_EQUIV note is given or if a REG_EQUAL note with a
799 constant operand is specified, use it as the source and
800 mark that we should move this insn by calling
801 emit_move_insn rather that duplicating the insn.
803 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL
804 note is present. */
808 else
809 {
814 {
816 /* A libcall block can use regs that don't appear in
817 the equivalent expression. To move the libcall,
818 we must move those regs too. */
820 }
821 }
823 /* For parallels, add any possible uses to the dependencies, as
824 we can't move the insn without resolving them first.
825 MEMs inside CLOBBERs may also reference registers; these
826 count as implicit uses. */
828 {
830 {
833 dependencies
835 dependencies);
840 }
841 }
844 than the one where it is set (meaning that
845 something after this point in the loop might
846 depend on its value before the set). */
848 /* And the set is not guaranteed to be executed once
849 the loop starts, or the value before the set is
850 needed before the set occurs...
852 ??? Note we have quadratic behavior here, mitigated
853 by the fact that the previous test will often fail for
854 large loops. Rather than re-scanning the entire loop
855 each time for register usage, we should build tables
856 of the register usage and use them here instead. */
857 && (maybe_never
859 /* It is unsafe to move the set. However, it may be OK to
860 move the source into a new pseudo, and substitute a
861 reg-to-reg copy for the original insn.
863 This code used to consider it OK to move a set of a variable
864 which was not created by the user and not used in an exit
865 test.
866 That behavior is incorrect and was removed. */
869 /* Don't try to optimize a MODE_CC set with a constant
870 source. It probably will be combined with a conditional
871 jump. */
874 ;
875 /* Don't try to optimize a register that was made
876 by loop-optimization for an inner loop.
877 We don't know its life-span, so we can't compute
878 the benefit. */
880 ;
881 /* Don't move the source and add a reg-to-reg copy:
882 - with -Os (this certainly increases size),
883 - if the mode doesn't support copy operations (obviously),
884 - if the source is already a reg (the motion will gain nothing),
885 - if the source is a legitimate constant (likewise). */
887 && (optimize_size
892 ;
895 || (tem2
898 || (tem1
899 = consec_sets_invariant_p
902 p)))
903 /* If the insn can cause a trap (such as divide by zero),
904 can't move it unless it's guaranteed to be executed
905 once loop is entered. Even a function call might
906 prevent the trap insn from being reached
907 (since it might exit!) */
910 {
914 /* A potential lossage is where we have a case where two insns
915 can be combined as long as they are both in the loop, but
916 we move one of them outside the loop. For large loops,
917 this can lose. The most common case of this is the address
918 of a function being called.
920 Therefore, if this register is marked as being used
921 exactly once if we are in a loop with calls
922 (a "large loop"), see if we can replace the usage of
923 this register with the source of this SET. If we can,
924 delete this insn.
926 Don't do this if P has a REG_RETVAL note or if we have
927 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
939 && (! SMALL_REGISTER_CLASSES
944 /* This test is not redundant; SET_SRC (set) might be
945 a call-clobbered register and the life of REGNO
946 might span a call. */
953 {
954 /* Replace any usage in a REG_EQUAL note. Must copy
955 the new source, so that we don't get rtx sharing
956 between the SET_SOURCE and REG_NOTES of insn p. */
958 = (replace_rtx
964 i++)
967 }
976 m->consec
987 /* Set M->cond if either loop_invariant_p
988 or consec_sets_invariant_p returned 2
989 (only conditionally invariant). */
999 /* Add M to the end of the chain MOVABLES. */
1003 {
1004 /* It is possible for the first instruction to have a
1005 REG_EQUAL note but a non-invariant SET_SRC, so we must
1006 remember the status of the first instruction in case
1007 the last instruction doesn't have a REG_EQUAL note. */
1010 /* Skip this insn, not checking REG_LIBCALL notes. */
1012 /* Skip the consecutive insns, if there are any. */
1014 /* Back up to the last insn of the consecutive group. */
1017 /* We must now reset m->move_insn, m->is_equiv, and
1018 possibly m->set_src to correspond to the effects of
1019 all the insns. */
1023 else
1024 {
1028 else
1031 }
1032 m->is_equiv
1034 }
1035 }
1036 /* If this register is always set within a STRICT_LOW_PART
1037 or set to zero, then its high bytes are constant.
1038 So clear them outside the loop and within the loop
1039 just load the low bytes.
1040 We must check that the machine has an instruction to do so.
1041 Also, if the value loaded into the register
1042 depends on the same register, this cannot be done. */
1052 {
1055 {
1070 /* If the insn may not be executed on some cycles,
1071 we can't clear the whole reg; clear just high part.
1072 Not even if the reg is used only within this loop.
1073 Consider this:
1074 while (1)
1075 while (s != t) {
1076 if (foo ()) x = *s;
1077 use (x);
1078 }
1079 Clearing x before the inner loop could clobber a value
1080 being saved from the last time around the outer loop.
1081 However, if the reg is not used outside this loop
1082 and all uses of the register are in the same
1083 basic block as the store, there is no problem.
1085 If this insn was made by loop, we don't know its
1086 INSN_LUID and hence must make a conservative
1087 assumption. */
1090 || (labels_in_range_p
1094 else
1103 i++)
1105 /* Add M to the end of the chain MOVABLES. */
1107 }
1108 }
1109 }
1110 }
1111 /* Past a call insn, we get to insns which might not be executed
1112 because the call might exit. This matters for insns that trap.
1113 Constant and pure call insns always return, so they don't count. */
1116 /* Past a label or a jump, we get to insns for which we
1117 can't count on whether or how many times they will be
1118 executed during each iteration. Therefore, we can
1119 only move out sets of trivial variables
1120 (those not used after the loop). */
1121 /* Similar code appears twice in strength_reduce. */
1123 /* If we enter the loop in the middle, and scan around to the
1124 beginning, don't set maybe_never for that. This must be an
1125 unconditional jump, otherwise the code at the top of the
1126 loop might never be executed. Unconditional jumps are
1127 followed by a barrier then the loop_end. */
1133 {
1134 /* At the virtual top of a converted loop, insns are again known to
1135 be executed: logically, the loop begins here even though the exit
1136 code has been duplicated. */
1140 loop_depth++;
1142 loop_depth--;
1143 }
1144 }
1146 /* If one movable subsumes another, ignore that other. */
1150 /* For each movable insn, see if the reg that it loads
1151 leads when it dies right into another conditionally movable insn.
1152 If so, record that the second insn "forces" the first one,
1153 since the second can be moved only if the first is. */
1157 /* See if there are multiple movable insns that load the same value.
1158 If there are, make all but the first point at the first one
1159 through the `match' field, and add the priorities of them
1160 all together as the priority of the first. */
1164 /* Now consider each movable insn to decide whether it is worth moving.
1165 Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
1167 For machines with few registers this increases code size, so do not
1168 move moveables when optimizing for code size on such machines.
1169 (The 18 below is the value for i386.) */
1173 {
1176 /* Recalculate regs->array if move_movables has created new
1177 registers. */
1179 {
1185 ;
1190 }
1191 }
1193 /* Now candidates that still are negative are those not moved.
1194 Change regs->array[I].set_in_loop to indicate that those are not actually
1195 invariant. */
1200 /* Now that we've moved some things out of the loop, we might be able to
1201 hoist even more memory references. */
1204 /* Recalculate regs->array if load_mems has created new registers. */
1212 ;
1219 {
1221 /* Ensure our label doesn't go away. */
1232 }
1235 /* The movable information is required for strength reduction. */
1241 }
1242 \f
1243 /* Add elements to *OUTPUT to record all the pseudo-regs
1244 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1246 void
1248 {
1256 {
1274 }
1278 {
1282 {
1291 }
1292 }
1293 }
1294 \f
1295 /* Check what regs are referred to in the libcall block ending with INSN,
1296 aside from those mentioned in the equivalent value.
1297 If there are none, return 0.
1298 If there are one or more, return an EXPR_LIST containing all of them. */
1300 rtx
1302 {
1307 /* First, find all the regs used in the libcall block
1308 that are not mentioned as inputs to the result. */
1311 {
1316 }
1319 }
1320 \f
1321 /* Return 1 if all uses of REG
1322 are between INSN and the end of the basic block. */
1324 static int
1326 {
1328 rtx p;
1333 /* Search this basic block for the already recorded last use of the reg. */
1335 {
1337 {
1343 /* Ordinary insn: if this is the last use, we win. */
1349 /* Jump insn: if this is the last use, we win. */
1352 /* Otherwise, it's the end of the basic block, so we lose. */
1357 /* It's the end of the basic block, so we lose. */
1362 }
1363 }
1365 /* The "last use" that was recorded can't be found after the first
1366 use. This can happen when the last use was deleted while
1367 processing an inner loop, this inner loop was then completely
1368 unrolled, and the outer loop is always exited after the inner loop,
1369 so that everything after the first use becomes a single basic block. */
1371 }
1372 \f
1373 /* Compute the benefit of eliminating the insns in the block whose
1374 last insn is LAST. This may be a group of insns used to compute a
1375 value directly or can contain a library call. */
1377 static int
1379 {
1380 rtx insn;
1385 {
1388 routine. */
1392 benefit++;
1393 }
1396 }
1397 \f
1398 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1400 static rtx
1402 {
1404 {
1405 rtx temp;
1407 /* If first insn of libcall sequence, skip to end. */
1408 /* Do this at start of loop, since INSN is guaranteed to
1409 be an insn here. */
1414 do
1417 }
1420 }
1422 /* Ignore any movable whose insn falls within a libcall
1423 which is part of another movable.
1424 We make use of the fact that the movable for the libcall value
1425 was made later and so appears later on the chain. */
1427 static void
1429 {
1433 {
1434 /* Is this a movable for the value of a libcall? */
1437 {
1438 rtx insn;
1439 /* Check for earlier movables inside that range,
1440 and mark them invalid. We cannot use LUIDs here because
1441 insns created by loop.c for prior loops don't have LUIDs.
1442 Rather than reject all such insns from movables, we just
1443 explicitly check each insn in the libcall (since invariant
1444 libcalls aren't that common). */
1449 }
1450 }
1451 }
1453 /* For each movable insn, see if the reg that it loads
1454 leads when it dies right into another conditionally movable insn.
1455 If so, record that the second insn "forces" the first one,
1456 since the second can be moved only if the first is. */
1458 static void
1460 {
1464 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1466 {
1469 /* ??? Could this be a bug? What if CSE caused the
1470 register of M1 to be used after this insn?
1471 Since CSE does not update regno_last_uid,
1472 this insn M->insn might not be where it dies.
1473 But very likely this doesn't matter; what matters is
1474 that M's reg is computed from M1's reg. */
1479 /* If m->consec, m->set_src isn't valid. */
1483 /* Increase the priority of the moving the first insn
1484 since it permits the second to be moved as well.
1485 Likewise for insns already forced by the first insn. */
1487 {
1492 {
1495 }
1496 }
1497 }
1498 }
1499 \f
1500 /* Find invariant expressions that are equal and can be combined into
1501 one register. */
1503 static void
1505 {
1510 /* Regs that are set more than once are not allowed to match
1511 or be matched. I'm no longer sure why not. */
1512 /* Only pseudo registers are allowed to match or be matched,
1513 since move_movables does not validate the change. */
1514 /* Perhaps testing m->consec_sets would be more appropriate here? */
1521 {
1528 /* We want later insns to match the first one. Don't make the first
1529 one match any later ones. So start this loop at m->next. */
1535 /* A reg used outside the loop mustn't be eliminated. */
1537 /* A reg used for zero-extending mustn't be eliminated. */
1540 ||
1541 (
1542 /* Can combine regs with different modes loaded from the
1543 same constant only if the modes are the same or
1544 if both are integer modes with M wider or the same
1545 width as M1. The check for integer is redundant, but
1546 safe, since the only case of differing destination
1547 modes with equal sources is when both sources are
1548 VOIDmode, i.e., CONST_INT. */
1554 /* See if the source of M1 says it matches M. */
1561 {
1567 }
1568 }
1570 /* Now combine the regs used for zero-extension.
1571 This can be done for those not marked `global'
1572 provided their lives don't overlap. */
1576 {
1579 /* Combine all the registers for extension from mode MODE.
1580 Don't combine any that are used outside this loop. */
1584 {
1591 {
1592 /* First one: don't check for overlap, just record it. */
1595 }
1597 /* Make sure they extend to the same mode.
1598 (Almost always true.) */
1602 /* We already have one: check for overlap with those
1603 already combined together. */
1610 /* No overlap: we can combine this with the others. */
1616 overlap:
1617 ;
1618 }
1619 }
1621 /* Clean up. */
1623 }
1625 /* Returns the number of movable instructions in LOOP that were not
1626 moved outside the loop. */
1628 static int
1630 {
1639 }
1641 \f
1642 /* Return 1 if regs X and Y will become the same if moved. */
1644 static int
1646 {
1663 }
1665 /* Return 1 if X and Y are identical-looking rtx's.
1666 This is the Lisp function EQUAL for rtx arguments.
1668 If two registers are matching movables or a movable register and an
1669 equivalent constant, consider them equal. */
1671 static int
1674 {
1688 /* If we have a register and a constant, they may sometimes be
1689 equal. */
1692 {
1697 }
1700 {
1705 }
1707 /* Otherwise, rtx's of different codes cannot be equal. */
1711 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1712 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1717 /* These three types of rtx's can be compared nonrecursively. */
1726 /* Compare the elements. If any pair of corresponding elements
1727 fail to match, return 0 for the whole things. */
1731 {
1733 {
1745 /* Two vectors must have the same length. */
1749 /* And the corresponding elements must match. */
1768 /* These are just backpointers, so they don't matter. */
1774 /* It is believed that rtx's at this level will never
1775 contain anything but integers and other rtx's,
1776 except for within LABEL_REFs and SYMBOL_REFs. */
1779 }
1780 }
1782 }
1783 \f
1784 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1785 insns in INSNS which use the reference. LABEL_NUSES for CODE_LABEL
1786 references is incremented once for each added note. */
1788 static void
1790 {
1794 rtx insn;
1797 {
1798 /* This code used to ignore labels that referred to dispatch tables to
1799 avoid flow generating (slightly) worse code.
1801 We no longer ignore such label references (see LABEL_REF handling in
1802 mark_jump_label for additional information). */
1805 {
1810 }
1811 }
1815 {
1821 }
1822 }
1823 \f
1824 /* Scan MOVABLES, and move the insns that deserve to be moved.
1825 If two matching movables are combined, replace one reg with the
1826 other throughout. */
1828 static void
1831 {
1836 rtx p;
1839 /* Map of pseudo-register replacements to handle combining
1840 when we move several insns that load the same value
1841 into different pseudo-registers. */
1846 {
1847 /* Describe this movable insn. */
1850 {
1871 }
1873 /* Ignore the insn if it's already done (it matched something else).
1874 Otherwise, see if it is now safe to move. */
1886 {
1888 rtx p;
1891 /* We have an insn that is safe to move.
1892 Compute its desirability. */
1903 /* An insn MUST be moved if we already moved something else
1904 which is safe only if this one is moved too: that is,
1905 if already_moved[REGNO] is nonzero. */
1907 /* An insn is desirable to move if the new lifetime of the
1908 register is no more than THRESHOLD times the old lifetime.
1909 If it's not desirable, it means the loop is so big
1910 that moving won't speed things up much,
1911 and it is liable to make register usage worse. */
1913 /* It is also desirable to move if it can be moved at no
1914 extra cost because something else was already moved. */
1917 || flag_move_all_movables
1922 {
1931 /* Now move the insns that set the reg. */
1934 {
1937 /* Find the end of this chain of matching regs.
1938 Thus, we load each reg in the chain from that one reg.
1939 And that reg is loaded with 0 directly,
1940 since it has ->match == 0. */
1946 /* Mark the moved, invariant reg as being allowed to
1947 share a hard reg with the other matching invariant. */
1951 regs_may_share
1954 regs_may_share));
1962 }
1963 /* If we are to re-generate the item being moved with a
1964 new move insn, first delete what we have and then emit
1965 the move insn before the loop. */
1967 {
1971 {
1972 /* If this is the first insn of a library call sequence,
1973 something is very wrong. */
1978 /* If this is the last insn of a libcall sequence, then
1979 delete every insn in the sequence except the last.
1980 The last insn is handled in the normal manner. */
1983 {
1987 }
1992 /* simplify_giv_expr expects that it can walk the insns
1993 at m->insn forwards and see this old sequence we are
1994 tossing here. delete_insn does preserve the next
1995 pointers, but when we skip over a NOTE we must fix
1996 it up. Otherwise that code walks into the non-deleted
1997 insn stream. */
2002 {
2003 /* Replace the original insn with a move from
2004 our newly created temp. */
2010 }
2011 }
2030 /* The more regs we move, the less we like moving them. */
2032 }
2033 else
2034 {
2036 {
2039 /* If first insn of libcall sequence, skip to end. */
2040 /* Do this at start of loop, since p is guaranteed to
2041 be an insn here. */
2046 /* If last insn of libcall sequence, move all
2047 insns except the last before the loop. The last
2048 insn is handled in the normal manner. */
2051 {
2059 {
2060 rtx body;
2061 rtx n;
2062 rtx next;
2069 /* Find the next insn after TEMP,
2070 not counting USE or NOTE insns. */
2078 /* If that is the call, this may be the insn
2079 that loads the function address.
2081 Extract the function address from the insn
2082 that loads it into a register.
2083 If this insn was cse'd, we get incorrect code.
2085 So emit a new move insn that copies the
2086 function address into the register that the
2087 call insn will use. flow.c will delete any
2088 redundant stores that we have created. */
2093 NULL_RTX)))
2094 {
2100 }
2101 /* We have the call insn.
2102 If it uses the register we suspect it might,
2103 load it with the correct address directly. */
2108 gen_move_insn
2112 {
2114 /* Because the USAGE information potentially
2115 contains objects other than hard registers
2116 we need to copy it. */
2120 }
2121 else
2130 }
2133 }
2135 {
2136 /* P sets REG to zero; but we should clear only
2137 the bits that are not covered by the mode
2138 m->savemode. */
2140 rtx sequence;
2141 rtx tem;
2144 tem = expand_simple_binop
2157 }
2159 {
2161 /* Because the USAGE information potentially
2162 contains objects other than hard registers
2163 we need to copy it. */
2167 }
2169 {
2170 rtx seq;
2171 /* The SET_SRC might not be invariant, so we must
2172 use the REG_EQUAL note. */
2185 }
2187 {
2195 }
2196 else
2200 {
2204 /* If there is a REG_EQUAL note present whose value
2205 is not loop invariant, then delete it, since it
2206 may cause problems with later optimization passes.
2207 It is possible for cse to create such notes
2208 like this as a result of record_jump_cond. */
2213 }
2222 /* If library call, now fix the REG_NOTES that contain
2223 insn pointers, namely REG_LIBCALL on FIRST
2224 and REG_RETVAL on I1. */
2226 {
2230 }
2236 /* simplify_giv_expr expects that it can walk the insns
2237 at m->insn forwards and see this old sequence we are
2238 tossing here. delete_insn does preserve the next
2239 pointers, but when we skip over a NOTE we must fix
2240 it up. Otherwise that code walks into the non-deleted
2241 insn stream. */
2246 {
2247 rtx seq;
2248 /* Replace the original insn with a move from
2249 our newly created temp. */
2255 }
2256 }
2258 /* The more regs we move, the less we like moving them. */
2260 }
2265 {
2266 /* Any other movable that loads the same register
2267 MUST be moved. */
2270 /* This reg has been moved out of one loop. */
2273 /* The reg set here is now invariant. */
2275 {
2279 }
2281 /* Change the length-of-life info for the register
2282 to say it lives at least the full length of this loop.
2283 This will help guide optimizations in outer loops. */
2286 /* This is the old insn before all the moved insns.
2287 We can't use the moved insn because it is out of range
2288 in uid_luid. Only the old insns have luids. */
2292 }
2294 /* Combine with this moved insn any other matching movables. */
2299 {
2300 rtx temp;
2302 /* Schedule the reg loaded by M1
2303 for replacement so that shares the reg of M.
2304 If the modes differ (only possible in restricted
2305 circumstances, make a SUBREG.
2307 Note this assumes that the target dependent files
2308 treat REG and SUBREG equally, including within
2309 GO_IF_LEGITIMATE_ADDRESS and in all the
2310 predicates since we never verify that replacing the
2311 original register with a SUBREG results in a
2312 recognizable insn. */
2315 else
2320 /* Get rid of the matching insn
2321 and prevent further processing of it. */
2324 /* If library call, delete all insns. */
2326 NULL_RTX)))
2328 else
2331 /* Any other movable that loads the same register
2332 MUST be moved. */
2335 /* The reg merged here is now invariant,
2336 if the reg it matches is invariant. */
2338 {
2342 i++)
2344 }
2345 }
2346 }
2349 }
2355 }
2360 /* Go through all the instructions in the loop, making
2361 all the register substitutions scheduled in REG_MAP. */
2365 {
2369 }
2371 /* Clean up. */
2374 }
2377 static void
2379 {
2382 else
2385 }
2388 static void
2390 {
2395 {
2398 }
2399 }
2400 \f
2401 #if 0
2402 /* Scan X and replace the address of any MEM in it with ADDR.
2403 REG is the address that MEM should have before the replacement. */
2405 static void
2407 {
2416 {
2428 /* Short cut for very common case. */
2433 /* Short cut for very common case. */
2438 /* If this MEM uses a reg other than the one we expected,
2439 something is wrong. */
2447 }
2451 {
2455 {
2459 }
2460 }
2461 }
2462 #endif
2463 \f
2464 /* Return the number of memory refs to addresses that vary
2465 in the rtx X. */
2467 static int
2469 {
2480 {
2497 }
2502 {
2506 {
2510 }
2511 }
2513 }
2514 \f
2515 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2516 `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2517 `unknown_address_altered', `unknown_constant_address_altered', and
2518 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2519 list `store_mems' in LOOP. */
2521 static void
2523 {
2525 rtx insn;
2529 /* The label after END. Jumping here is just like falling off the
2530 end of the loop. We use next_nonnote_insn instead of next_label
2531 as a hedge against the (pathological) case where some actual insn
2532 might end up between the two. */
2551 /* If loop opts run twice, this was set on 1st pass for 2nd. */
2556 {
2558 {
2561 }
2562 }
2566 {
2568 {
2571 {
2573 /* Count number of loops contained in this one. */
2575 }
2582 {
2585 }
2592 /* Calls initializing constant objects have CLOBBER of MEM /u in the
2593 attached FUNCTION_USAGE expression list, not accounted for by the
2594 code above. We should note these to avoid missing dependencies in
2595 later references. */
2596 {
2597 rtx fusage_entry;
2601 {
2607 {
2612 }
2613 }
2614 }
2619 {
2623 {
2628 {
2631 }
2632 else
2633 {
2636 }
2638 do
2639 {
2641 {
2643 {
2644 /* Something tricky. */
2647 }
2650 {
2651 /* A jump outside the current loop. */
2654 }
2655 }
2659 }
2661 }
2662 else
2663 {
2664 /* A return, or something tricky. */
2666 }
2667 }
2668 /* Fall through. */
2689 }
2690 }
2692 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2694 anywhere. */
2696 /* We don't want loads for MEMs moved to a location before the
2697 one at which their stack memory becomes allocated. (Note
2698 that this is not a problem for malloc, etc., since those
2699 require actual function calls. */
2700 && ! current_function_calls_alloca
2701 /* There are ways to leave the loop other than falling off the
2702 end. */
2708 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2709 that loop_invariant_p and load_mems can use true_dependence
2710 to determine what is really clobbered. */
2712 {
2715 loop_info->store_mems
2717 }
2719 {
2723 loop_info->store_mems
2725 }
2726 }
2727 \f
2728 /* Invalidate all loops containing LABEL. */
2730 static void
2732 {
2736 }
2738 /* Scan the function looking for loops. Record the start and end of each loop.
2739 Also mark as invalid loops any loops that contain a setjmp or are branched
2740 to from outside the loop. */
2742 static void
2744 {
2745 rtx insn;
2746 rtx label;
2756 /* If there are jumps to undefined labels,
2757 treat them as jumps out of any/all loops.
2758 This also avoids writing past end of tables when there are no loops. */
2761 /* Find boundaries of loops, mark which loops are contained within
2762 loops, and invalidate loops that have setjmp. */
2767 {
2770 {
2774 num_loops++;
2798 }
2802 {
2803 /* In this case, we must invalidate our current loop and any
2804 enclosing loop. */
2806 {
2812 }
2813 }
2815 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2816 enclosing loop, but this doesn't matter. */
2818 }
2820 /* Any loop containing a label used in an initializer must be invalidated,
2821 because it can be jumped into from anywhere. */
2825 /* Any loop containing a label used for an exception handler must be
2826 invalidated, because it can be jumped into from anywhere. */
2829 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2830 loop that it is not contained within, that loop is marked invalid.
2831 If any INSN or CALL_INSN uses a label's address, then the loop containing
2832 that label is marked invalid, because it could be jumped into from
2833 anywhere.
2835 Also look for blocks of code ending in an unconditional branch that
2836 exits the loop. If such a block is surrounded by a conditional
2837 branch around the block, move the block elsewhere (see below) and
2838 invert the jump to point to the code block. This may eliminate a
2839 label in our loop and will simplify processing by both us and a
2840 possible second cse pass. */
2844 {
2848 {
2852 }
2859 /* See if this is an unconditional branch outside the loop. */
2867 {
2868 rtx p;
2874 /* Go backwards until we reach the start of the loop, a label,
2875 or a JUMP_INSN. */
2882 ;
2884 /* Check for the case where we have a jump to an inner nested
2885 loop, and do not perform the optimization in that case. */
2888 {
2891 {
2896 }
2897 }
2899 /* Make sure that the target of P is within the current loop. */
2905 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2906 we have a block of code to try to move.
2908 We look backward and then forward from the target of INSN
2909 to find a BARRIER at the same loop depth as the target.
2910 If we find such a BARRIER, we make a new label for the start
2911 of the block, invert the jump in P and point it to that label,
2912 and move the block of code to the spot we found. */
2917 /* Just ignore jumps to labels that were never emitted.
2918 These always indicate compilation errors. */
2922 /* If it's not safe to move the sequence, then we
2923 mustn't try. */
2926 {
2927 rtx target
2931 rtx tmp;
2933 /* Search for possible garbage past the conditional jumps
2934 and look for the last barrier. */
2942 /* Don't move things inside a tablejump. */
2955 /* Don't move things inside a tablejump. */
2966 {
2970 /* Ensure our label doesn't go away. */
2973 /* Verify that uid_loop is large enough and that
2974 we can invert P. */
2976 {
2979 /* If no suitable BARRIER was found, create a suitable
2980 one before TARGET. Since TARGET is a fall through
2981 path, we'll need to insert a jump around our block
2982 and add a BARRIER before TARGET.
2984 This creates an extra unconditional jump outside
2985 the loop. However, the benefits of removing rarely
2986 executed instructions from inside the loop usually
2987 outweighs the cost of the extra unconditional jump
2988 outside the loop. */
2990 {
2991 rtx temp;
2998 }
3000 /* Include the BARRIER after INSN and copy the
3001 block after LOC. */
3006 /* All those insns are now in TARGET_LOOP. */
3012 /* The label jumped to by INSN is no longer a loop
3013 exit. Unless INSN does not have a label (e.g.,
3014 it is a RETURN insn), search loop->exit_labels
3015 to find its label_ref, and remove it. Also turn
3016 off LABEL_OUTSIDE_LOOP_P bit. */
3018 {
3020 r;
3023 {
3027 else
3030 }
3036 /* If we didn't find it, then something is
3037 wrong. */
3040 }
3042 /* P is now a jump outside the loop, so it must be put
3043 in loop->exit_labels, and marked as such.
3044 The easiest way to do this is to just call
3045 mark_loop_jump again for P. */
3048 /* If INSN now jumps to the insn after it,
3049 delete INSN. */
3054 }
3056 /* Continue the loop after where the conditional
3057 branch used to jump, since the only branch insn
3058 in the block (if it still remains) is an inter-loop
3059 branch and hence needs no processing. */
3065 /* This loop will be continued with NEXT_INSN (insn). */
3067 }
3068 }
3069 }
3070 }
3071 }
3073 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
3074 loops it is contained in, mark the target loop invalid.
3076 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
3078 static void
3080 {
3086 {
3098 /* There could be a label reference in here. */
3110 /* This may refer to a LABEL_REF or SYMBOL_REF. */
3122 /* Link together all labels that branch outside the loop. This
3123 is used by final_[bg]iv_value and the loop unrolling code. Also
3124 mark this LABEL_REF so we know that this branch should predict
3125 false. */
3127 /* A check to make sure the label is not in an inner nested loop,
3128 since this does not count as a loop exit. */
3130 {
3135 }
3136 else
3140 {
3149 }
3151 /* If this is inside a loop, but not in the current loop or one enclosed
3152 by it, it invalidates at least one loop. */
3157 /* We must invalidate every nested loop containing the target of this
3158 label, except those that also contain the jump insn. */
3161 {
3162 /* Stop when we reach a loop that also contains the jump insn. */
3167 /* If we get here, we know we need to invalidate a loop. */
3174 }
3178 /* If this is not setting pc, ignore. */
3200 /* Strictly speaking this is not a jump into the loop, only a possible
3201 jump out of the loop. However, we have no way to link the destination
3202 of this jump onto the list of exit labels. To be safe we mark this
3203 loop and any containing loops as invalid. */
3205 {
3207 {
3213 }
3214 }
3216 }
3217 }
3218 \f
3219 /* Return nonzero if there is a label in the range from
3220 insn INSN to and including the insn whose luid is END
3221 INSN must have an assigned luid (i.e., it must not have
3222 been previously created by loop.c). */
3224 static int
3226 {
3228 {
3232 }
3235 }
3237 /* Record that a memory reference X is being set. */
3239 static void
3242 {
3248 /* Count number of memory writes.
3249 This affects heuristics in strength_reduce. */
3252 /* BLKmode MEM means all memory is clobbered. */
3254 {
3257 else
3261 }
3265 }
3267 /* X is a value modified by an INSN that references a biv inside a loop
3268 exit test (ie, X is somehow related to the value of the biv). If X
3269 is a pseudo that is used more than once, then the biv is (effectively)
3270 used more than once. DATA is a pointer to a loop_regs structure. */
3272 static void
3274 {
3289 /* If we do not have usage information, or if we know the register
3290 is used more than once, note that fact for check_dbra_loop. */
3295 }
3296 \f
3297 /* Return nonzero if the rtx X is invariant over the current loop.
3299 The value is 2 if we refer to something only conditionally invariant.
3301 A memory ref is invariant if it is not volatile and does not conflict
3302 with anything stored in `loop_info->store_mems'. */
3304 int
3306 {
3313 rtx mem_list_entry;
3319 {
3327 /* A LABEL_REF is normally invariant, however, if we are unrolling
3328 loops, and this label is inside the loop, then it isn't invariant.
3329 This is because each unrolled copy of the loop body will have
3330 a copy of this label. If this was invariant, then an insn loading
3331 the address of this label into a register might get moved outside
3332 the loop, and then each loop body would end up using the same label.
3334 We don't know the loop bounds here though, so just fail for all
3335 labels. */
3338 else
3347 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3348 since the reg might be set by initialization within the loop. */
3359 /* Out-of-range regs can occur when we are called from unrolling.
3360 These registers created by the unroller are set in the loop,
3361 hence are never invariant.
3362 Other out-of-range regs can be generated by load_mems; those that
3363 are written to in the loop are not invariant, while those that are
3364 not written to are invariant. It would be easy for load_mems
3365 to set n_times_set correctly for these registers, however, there
3366 is no easy way to distinguish them from registers created by the
3367 unroller. */
3378 /* Volatile memory references must be rejected. Do this before
3379 checking for read-only items, so that volatile read-only items
3380 will be rejected also. */
3384 /* See if there is any dependence between a store and this load. */
3387 {
3393 }
3395 /* It's not invalidated by a store in memory
3396 but we must still verify the address is invariant. */
3400 /* Don't mess with insns declared volatile. */
3407 }
3411 {
3413 {
3419 }
3421 {
3424 {
3430 }
3432 }
3433 }
3436 }
3437 \f
3438 /* Return nonzero if all the insns in the loop that set REG
3439 are INSN and the immediately following insns,
3440 and if each of those insns sets REG in an invariant way
3441 (not counting uses of REG in them).
3443 The value is 2 if some of these insns are only conditionally invariant.
3445 We assume that INSN itself is the first set of REG
3446 and that its source is invariant. */
3448 static int
3450 rtx insn)
3451 {
3455 rtx temp;
3456 /* Number of sets we have to insist on finding after INSN. */
3462 /* If N_SETS hit the limit, we can't rely on its value. */
3469 {
3471 rtx set;
3476 /* If library call, skip to end of it. */
3485 {
3490 {
3491 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3492 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3493 notes are OK. */
3499 }
3500 }
3502 count--;
3504 {
3507 }
3508 }
3511 /* If loop_invariant_p ever returned 2, we return 2. */
3513 }
3515 #if 0
3516 /* I don't think this condition is sufficient to allow INSN
3517 to be moved, so we no longer test it. */
3519 /* Return 1 if all insns in the basic block of INSN and following INSN
3520 that set REG are invariant according to TABLE. */
3522 static int
3524 {
3529 {
3538 {
3541 }
3542 }
3543 }
3545 \f
3546 /* Look at all uses (not sets) of registers in X. For each, if it is
3547 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3548 a different insn, set USAGE[REGNO] to const0_rtx. */
3550 static void
3552 {
3564 {
3565 /* Don't count SET_DEST if it is a REG; otherwise count things
3566 in SET_DEST because if a register is partially modified, it won't
3567 show up as a potential movable so we don't care how USAGE is set
3568 for it. */
3572 }
3573 else
3575 {
3581 }
3582 }
3583 \f
3584 /* Count and record any set in X which is contained in INSN. Update
3585 REGS->array[I].MAY_NOT_OPTIMIZE and LAST_SET for any register I set
3586 in X. */
3588 static void
3590 {
3592 /* Don't move a reg that has an explicit clobber.
3593 It's not worth the pain to try to do it correctly. */
3597 {
3605 {
3609 {
3610 /* If this is the first setting of this reg
3611 in current basic block, and it was set before,
3612 it must be set in two basic blocks, so it cannot
3613 be moved out of the loop. */
3617 /* If this is not first setting in current basic block,
3618 see if reg was used in between previous one and this.
3619 If so, neither one can be moved. */
3626 }
3627 }
3628 }
3629 }
3630 \f
3631 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3632 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3633 contained in insn INSN is used by any insn that precedes INSN in
3634 cyclic order starting from the loop entry point.
3636 We don't want to use INSN_LUID here because if we restrict INSN to those
3637 that have a valid INSN_LUID, it means we cannot move an invariant out
3638 from an inner loop past two loops. */
3640 static int
3642 {
3644 rtx p;
3646 /* Scan forward checking for register usage. If we hit INSN, we
3647 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3649 {
3655 }
3658 }
3659 \f
3661 /* Information we collect about arrays that we might want to prefetch. */
3662 struct prefetch_info
3663 {
3667 index. */
3668 HOST_WIDE_INT index;
3670 iteration. */
3672 prefetch area in one iteration. */
3674 This is set only for loops with known
3675 iteration counts and is 0xffffffff
3676 otherwise. */
3680 };
3682 /* Data used by check_store function. */
3683 struct check_store_data
3684 {
3685 rtx mem_address;
3687 };
3693 /* Set mem_write when mem_address is found. Used as callback to
3694 note_stores. */
3695 static void
3697 {
3702 }
3703 \f
3704 /* Like rtx_equal_p, but attempts to swap commutative operands. This is
3705 important to get some addresses combined. Later more sophisticated
3706 transformations can be added when necessary.
3708 ??? Same trick with swapping operand is done at several other places.
3709 It can be nice to develop some common way to handle this. */
3711 static int
3713 {
3727 {
3732 }
3733 /* Compare the elements. If any pair of corresponding elements fails to
3734 match, return 0 for the whole thing. */
3738 {
3740 {
3752 /* Two vectors must have the same length. */
3756 /* And the corresponding elements must match. */
3774 /* These are just backpointers, so they don't matter. */
3780 /* It is believed that rtx's at this level will never
3781 contain anything but integers and other rtx's,
3782 except for within LABEL_REFs and SYMBOL_REFs. */
3785 }
3786 }
3788 }
3789 \f
3790 /* Remove constant addition value from the expression X (when present)
3791 and return it. */
3793 static HOST_WIDE_INT
3795 {
3799 /* Avoid clobbering a shared CONST expression. */
3801 {
3805 {
3808 }
3810 }
3813 {
3816 }
3818 /* For plus expression recurse on ourself. */
3820 {
3824 /* In case our parameter was constant, remove extra zero from the
3825 expression. */
3830 }
3833 }
3835 /* Attempt to identify accesses to arrays that are most likely to cause cache
3836 misses, and emit prefetch instructions a few prefetch blocks forward.
3838 To detect the arrays we use the GIV information that was collected by the
3839 strength reduction pass.
3841 The prefetch instructions are generated after the GIV information is done
3842 and before the strength reduction process. The new GIVs are injected into
3843 the strength reduction tables, so the prefetch addresses are optimized as
3844 well.
3846 GIVs are split into base address, stride, and constant addition values.
3847 GIVs with the same address, stride and close addition values are combined
3848 into a single prefetch. Also writes to GIVs are detected, so that prefetch
3849 for write instructions can be used for the block we write to, on machines
3850 that support write prefetches.
3852 Several heuristics are used to determine when to prefetch. They are
3853 controlled by defined symbols that can be overridden for each target. */
3855 static void
3857 {
3873 /* Consider only loops w/o calls. When a call is done, the loop is probably
3874 slow enough to read the memory. */
3876 {
3881 }
3883 /* Don't prefetch in loops known to have few iterations. */
3887 {
3892 }
3894 /* Search all induction variables and pick those interesting for the prefetch
3895 machinery. */
3897 {
3903 /* Expect all BIVs to be executed in each iteration. This makes our
3904 analysis more conservative. */
3906 {
3907 /* Discard non-constant additions that we can't handle well yet, and
3908 BIVs that are executed multiple times; such BIVs ought to be
3909 handled in the nested loop. We accept not_every_iteration BIVs,
3910 since these only result in larger strides and make our
3911 heuristics more conservative. */
3913 {
3915 {
3921 }
3923 }
3926 {
3928 {
3934 }
3936 }
3940 }
3946 {
3947 rtx address;
3948 rtx temp;
3957 /* See whether an induction variable is interesting to us and if
3958 not, report the reason. */
3962 /* We are interested only in constant stride memory references
3963 in order to be able to compute density easily. */
3967 else
3968 {
3971 {
3974 }
3976 /* On some targets, reversed order prefetches are not
3977 worthwhile. */
3981 /* Prefetch of accesses with an extreme stride might not be
3982 worthwhile, either. */
3987 /* Ignore GIVs with varying add values; we can't predict the
3988 value for the next iteration. */
3992 /* Ignore GIVs in the nested loops; they ought to have been
3993 handled already. */
3996 }
3999 {
4005 }
4007 /* Determine the pointer to the basic array we are examining. It is
4008 the sum of the BIV's initial value and the GIV's add_val. */
4018 /* When the GIV is not always executed, we might be better off by
4019 not dirtying the cache pages. */
4022 else
4023 {
4028 }
4030 /* Attempt to find another prefetch to the same array and see if we
4031 can merge this one. */
4035 {
4036 /* In case both access same array (same location
4037 just with small difference in constant indexes), merge
4038 the prefetches. Just do the later and the earlier will
4039 get prefetched from previous iteration.
4040 The artificial threshold should not be too small,
4041 but also not bigger than small portion of memory usually
4042 traversed by single loop. */
4045 {
4054 }
4058 {
4063 }
4064 }
4066 /* Merging failed. */
4068 {
4076 num_prefetches++;
4078 {
4083 }
4084 }
4085 }
4086 }
4089 {
4092 /* Attempt to calculate the total number of bytes fetched by all
4093 iterations of the loop. Avoid overflow. */
4098 else
4103 /* Prefetch might be worthwhile only when the loads/stores are dense. */
4108 {
4113 }
4114 else
4115 {
4121 }
4122 else
4125 /* Find how many prefetch instructions we'll use within the loop. */
4127 {
4133 }
4134 }
4136 /* Determine how many iterations ahead to prefetch within the loop, based
4137 on how many prefetches we currently expect to do within the loop. */
4139 {
4141 {
4147 }
4148 }
4149 /* We'll also use AHEAD to determine how many prefetch instructions to
4150 emit before a loop, so don't leave it zero. */
4155 {
4156 /* Update if we've decided not to prefetch anything within the loop. */
4160 /* Find how many prefetch instructions we'll use before the loop. */
4162 {
4170 }
4173 {
4193 }
4194 }
4197 {
4198 /* Record that this loop uses prefetch instructions. */
4202 {
4207 }
4208 }
4211 {
4215 {
4217 rtx insn;
4221 rtx seq;
4223 /* We can save some effort by offsetting the address on
4224 architectures with offsettable memory references. */
4227 else
4228 {
4234 }
4237 /* Make sure the address operand is valid for prefetch. */
4247 /* Check all insns emitted and record the new GIV
4248 information. */
4251 {
4256 }
4257 }
4260 {
4261 /* Emit insns before the loop to fetch the first cache lines or,
4262 if we're not prefetching within the loop, everything we expect
4263 to need. */
4265 {
4273 /* Functions called by LOOP_IV_ADD_EMIT_BEFORE expect a
4274 non-constant INIT_VAL to have the same mode as REG, which
4275 in this case we know to be Pmode. */
4277 {
4278 rtx seq;
4285 }
4291 loop_start);
4292 }
4293 }
4294 }
4297 }
4298 \f
4299 /* Communication with routines called via `note_stores'. */
4303 /* Dummy register to have nonzero DEST_REG for DEST_ADDR type givs. */
4307 /* ??? Unfinished optimizations, and possible future optimizations,
4308 for the strength reduction code. */
4310 /* ??? The interaction of biv elimination, and recognition of 'constant'
4311 bivs, may cause problems. */
4313 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
4314 performance problems.
4316 Perhaps don't eliminate things that can be combined with an addressing
4317 mode. Find all givs that have the same biv, mult_val, and add_val;
4318 then for each giv, check to see if its only use dies in a following
4319 memory address. If so, generate a new memory address and check to see
4320 if it is valid. If it is valid, then store the modified memory address,
4321 otherwise, mark the giv as not done so that it will get its own iv. */
4323 /* ??? Could try to optimize branches when it is known that a biv is always
4324 positive. */
4326 /* ??? When replace a biv in a compare insn, we should replace with closest
4327 giv so that an optimized branch can still be recognized by the combiner,
4328 e.g. the VAX acb insn. */
4330 /* ??? Many of the checks involving uid_luid could be simplified if regscan
4331 was rerun in loop_optimize whenever a register was added or moved.
4332 Also, some of the optimizations could be a little less conservative. */
4333 \f
4334 /* Scan the loop body and call FNCALL for each insn. In the addition to the
4335 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
4336 callback.
4338 NOT_EVERY_ITERATION is 1 if current insn is not known to be executed at
4339 least once for every loop iteration except for the last one.
4341 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
4342 loop iteration.
4343 */
4344 void
4346 {
4351 rtx p;
4353 /* If loop_scan_start points to the loop exit test, we have to be wary of
4354 subversive use of gotos inside expression statements. */
4358 /* Scan through loop and update NOT_EVERY_ITERATION and MAYBE_MULTIPLE. */
4362 {
4365 /* Past CODE_LABEL, we get to insns that may be executed multiple
4366 times. The only way we can be sure that they can't is if every
4367 jump insn between here and the end of the loop either
4368 returns, exits the loop, is a jump to a location that is still
4369 behind the label, or is a jump to the loop start. */
4372 {
4378 {
4383 {
4386 else
4390 }
4398 {
4401 }
4402 }
4403 }
4405 /* Past a jump, we get to insns for which we can't count
4406 on whether they will be executed during each iteration. */
4407 /* This code appears twice in strength_reduce. There is also similar
4408 code in scan_loop. */
4410 /* If we enter the loop in the middle, and scan around to the
4411 beginning, don't set not_every_iteration for that.
4412 This can be any kind of jump, since we want to know if insns
4413 will be executed if the loop is executed. */
4418 {
4421 /* If this is a jump outside the loop, then it also doesn't
4422 matter. Check to see if the target of this branch is on the
4423 loop->exits_labels list. */
4431 }
4434 {
4435 /* At the virtual top of a converted loop, insns are again known to
4436 be executed each iteration: logically, the loop begins here
4437 even though the exit code has been duplicated.
4439 Insns are also again known to be executed each iteration at
4440 the LOOP_CONT note. */
4446 loop_depth++;
4448 loop_depth--;
4449 }
4451 /* Note if we pass a loop latch. If we do, then we can not clear
4452 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
4453 a loop since a jump before the last CODE_LABEL may have started
4454 a new loop iteration.
4456 Note that LOOP_TOP is only set for rotated loops and we need
4457 this check for all loops, so compare against the CODE_LABEL
4458 which immediately follows LOOP_START. */
4463 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
4464 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
4465 or not an insn is known to be executed each iteration of the
4466 loop, whether or not any iterations are known to occur.
4468 Therefore, if we have just passed a label and have no more labels
4469 between here and the test insn of the loop, and we have not passed
4470 a jump to the top of the loop, then we know these insns will be
4471 executed each iteration. */
4474 && !past_loop_latch
4479 }
4480 }
4481 \f
4482 static void
4484 {
4487 /* Temporary list pointers for traversing ivs->list. */
4494 /* Scan ivs->list to remove all regs that proved not to be bivs.
4495 Make a sanity check against regs->n_times_set. */
4497 {
4499 /* Above happens if register modified by subreg, etc. */
4500 /* Make sure it is not recognized as a basic induction var: */
4502 /* If never incremented, it is invariant that we decided not to
4503 move. So leave it alone. */
4505 {
4516 }
4517 else
4518 {
4523 }
4524 }
4525 }
4528 /* Determine how BIVS are initialized by looking through pre-header
4529 extended basic block. */
4530 static void
4532 {
4534 /* Temporary list pointers for traversing ivs->list. */
4537 rtx p;
4539 /* Find initial value for each biv by searching backwards from loop_start,
4540 halting at first label. Also record any test condition. */
4544 {
4545 rtx test;
4555 /* Record any test of a biv that branches around the loop if no store
4556 between it and the start of loop. We only care about tests with
4557 constants and registers and only certain of those. */
4567 {
4568 /* If an NE test, we have an initial value! */
4570 {
4574 }
4575 else
4577 }
4578 }
4579 }
4582 /* Look at the each biv and see if we can say anything better about its
4583 initial value from any initializing insns set up above. (This is done
4584 in two passes to avoid missing SETs in a PARALLEL.) */
4585 static void
4587 {
4589 /* Temporary list pointers for traversing ivs->list. */
4594 {
4595 rtx src;
4596 rtx note;
4601 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
4602 is a constant, use the value of that. */
4608 else
4621 {
4625 {
4628 }
4629 }
4630 /* If we can't make it a giv,
4631 let biv keep initial value of "itself". */
4634 }
4635 }
4638 /* Search the loop for general induction variables. */
4640 static void
4642 {
4644 }
4647 /* For each giv for which we still don't know whether or not it is
4648 replaceable, check to see if it is replaceable because its final value
4649 can be calculated. */
4651 static void
4653 {
4658 {
4664 }
4665 }
4668 /* Return nonzero if it is possible to eliminate the biv BL provided
4669 all givs are reduced. This is possible if either the reg is not
4670 used outside the loop, or we can compute what its final value will
4671 be. */
4673 static int
4676 {
4677 /* For architectures with a decrement_and_branch_until_zero insn,
4678 don't do this if we put a REG_NONNEG note on the endtest for this
4679 biv. */
4681 #ifdef HAVE_decrement_and_branch_until_zero
4683 {
4688 }
4689 #endif
4691 /* Check that biv is used outside loop or if it has a final value.
4692 Compare against bl->init_insn rather than loop->start. We aren't
4693 concerned with any uses of the biv between init_insn and
4694 loop->start since these won't be affected by the value of the biv
4695 elsewhere in the function, so long as init_insn doesn't use the
4696 biv itself. */
4707 {
4715 }
4717 }
4720 /* Reduce each giv of BL that we have decided to reduce. */
4722 static void
4724 {
4728 {
4731 {
4734 /* If the code for derived givs immediately below has already
4735 allocated a new_reg, we must keep it. */
4739 #ifdef AUTO_INC_DEC
4740 /* If the target has auto-increment addressing modes, and
4741 this is an address giv, then try to put the increment
4742 immediately after its use, so that flow can create an
4743 auto-increment addressing mode. */
4746 /* We don't handle reversed biv's because bl->biv->insn
4747 does not have a valid INSN_LUID. */
4751 {
4752 /* If other giv's have been combined with this one, then
4753 this will work only if all uses of the other giv's occur
4754 before this giv's insn. This is difficult to check.
4756 We simplify this by looking for the common case where
4757 there is one DEST_REG giv, and this giv's insn is the
4758 last use of the dest_reg of that DEST_REG giv. If the
4759 increment occurs after the address giv, then we can
4760 perform the optimization. (Otherwise, the increment
4761 would have to go before other_giv, and we would not be
4762 able to combine it with the address giv to get an
4763 auto-inc address.) */
4765 {
4770 {
4773 else
4775 }
4782 }
4783 /* Check for case where increment is before the address
4784 giv. Do this test in "loop order". */
4793 else
4796 #ifdef HAVE_cc0
4797 {
4798 rtx prev;
4800 /* We can't put an insn immediately after one setting
4801 cc0, or immediately before one using cc0. */
4808 }
4809 #endif
4813 }
4814 #endif
4816 /* For each place where the biv is incremented, add an insn
4817 to increment the new, reduced reg for the giv. */
4819 {
4820 rtx insert_before;
4822 /* Skip if location is the same as a previous one. */
4829 else
4837 /* A multiply is acceptable here
4838 since this is presumed to be seldom executed. */
4842 }
4844 /* Add code at loop start to initialize giv's reduced reg. */
4849 }
4850 }
4851 }
4854 /* Check for givs whose first use is their definition and whose
4855 last use is the definition of another giv. If so, it is likely
4856 dead and should not be used to derive another giv nor to
4857 eliminate a biv. */
4859 static void
4861 {
4865 {
4872 {
4878 }
4879 }
4880 }
4883 static void
4885 {
4889 {
4896 /* Update expression if this was combined, in case other giv was
4897 replaced. */
4902 /* See if this register is known to be a pointer to something. If
4903 so, see if we can find the alignment. First see if there is a
4904 destination register that is a pointer. If so, this shares the
4905 alignment too. Next see if we can deduce anything from the
4906 computational information. If not, and this is a DEST_ADDR
4907 giv, at least we know that it's a pointer, though we don't know
4908 the alignment. */
4916 {
4925 }
4929 {
4937 }
4942 /* Store reduced reg as the address in the memref where we found
4943 this giv. */
4946 {
4948 }
4949 else
4950 {
4952 rtx note;
4954 /* Not replaceable; emit an insn to set the original giv reg from
4955 the reduced giv, same as above. */
4960 /* The original insn may have a REG_EQUAL note. This note is
4961 now incorrect and may result in invalid substitutions later.
4962 The original insn is dead, but may be part of a libcall
4963 sequence, which doesn't seem worth the bother of handling. */
4967 }
4969 /* When a loop is reversed, givs which depend on the reversed
4970 biv, and which are live outside the loop, must be set to their
4971 correct final value. This insn is only needed if the giv is
4972 not replaceable. The correct final value is the same as the
4973 value that the giv starts the reversed loop with. */
4984 {
4989 }
4990 }
4991 }
4994 static int
4997 rtx test_reg)
4998 {
5007 /* Reduce benefit if not replaceable, since we will insert a
5008 move-insn to replace the insn that calculates this giv. Don't do
5009 this unless the giv is a user variable, since it will often be
5010 marked non-replaceable because of the duplication of the exit
5011 code outside the loop. In such a case, the copies we insert are
5012 dead and will be deleted. So they don't have a cost. Similar
5013 situations exist. */
5014 /* ??? The new final_[bg]iv_value code does a much better job of
5015 finding replaceable giv's, and hence this code may no longer be
5016 necessary. */
5021 /* Decrease the benefit to count the add-insns that we will insert
5022 to increment the reduced reg for the giv. ??? This can
5023 overestimate the run-time cost of the additional insns, e.g. if
5024 there are multiple basic blocks that increment the biv, but only
5025 one of these blocks is executed during each iteration. There is
5026 no good way to detect cases like this with the current structure
5027 of the loop optimizer. This code is more accurate for
5028 determining code size than run-time benefits. */
5031 /* Decide whether to strength-reduce this giv or to leave the code
5032 unchanged (recompute it from the biv each time it is used). This
5033 decision can be made independently for each giv. */
5035 #ifdef AUTO_INC_DEC
5036 /* Attempt to guess whether autoincrement will handle some of the
5037 new add insns; if so, increase BENEFIT (undo the subtraction of
5038 add_cost that was done above). */
5040 /* Increasing the benefit is risky, since this is only a guess.
5041 Avoid increasing register pressure in cases where there would
5042 be no other benefit from reducing this giv. */
5045 {
5060 }
5061 #endif
5064 }
5067 /* Free IV structures for LOOP. */
5069 static void
5071 {
5078 {
5084 {
5087 }
5089 {
5092 }
5096 }
5097 }
5100 /* Perform strength reduction and induction variable elimination.
5102 Pseudo registers created during this function will be beyond the
5103 last valid index in several tables including
5104 REGS->ARRAY[I].N_TIMES_SET and REGNO_LAST_UID. This does not cause a
5105 problem here, because the added registers cannot be givs outside of
5106 their loop, and hence will never be reconsidered. But scan_loop
5107 must check regnos to make sure they are in bounds. */
5109 static void
5111 {
5115 rtx p;
5116 /* Temporary list pointer for traversing ivs->list. */
5118 /* Ratio of extra register life span we can justify
5119 for saving an instruction. More if loop doesn't call subroutines
5120 since in that case saving an insn makes more difference
5121 and more registers are available. */
5122 /* ??? could set this to last value of threshold in move_movables */
5124 /* Map of pseudo-register replacements. */
5136 /* Find all BIVs in loop. */
5139 /* Exit if there are no bivs. */
5141 {
5142 /* Can still unroll the loop anyways, but indicate that there is no
5143 strength reduction info available. */
5149 }
5151 /* Determine how BIVS are initialized by looking through pre-header
5152 extended basic block. */
5155 /* Look at the each biv and see if we can say anything better about its
5156 initial value from any initializing insns set up above. */
5159 /* Search the loop for general induction variables. */
5162 /* Try to calculate and save the number of loop iterations. This is
5163 set to zero if the actual number can not be calculated. This must
5164 be called after all giv's have been identified, since otherwise it may
5165 fail if the iteration variable is a giv. */
5168 #ifdef HAVE_prefetch
5171 #endif
5173 /* Now for each giv for which we still don't know whether or not it is
5174 replaceable, check to see if it is replaceable because its final value
5175 can be calculated. This must be done after loop_iterations is called,
5176 so that final_giv_value will work correctly. */
5179 /* Try to prove that the loop counter variable (if any) is always
5180 nonnegative; if so, record that fact with a REG_NONNEG note
5181 so that "decrement and branch until zero" insn can be used. */
5184 /* Create reg_map to hold substitutions for replaceable giv regs.
5185 Some givs might have been made from biv increments, so look at
5186 ivs->reg_iv_type for a suitable size. */
5190 /* Examine each iv class for feasibility of strength reduction/induction
5191 variable elimination. */
5194 {
5198 /* Test whether it will be possible to eliminate this biv
5199 provided all givs are reduced. */
5202 /* This will be true at the end, if all givs which depend on this
5203 biv have been strength reduced.
5204 We can't (currently) eliminate the biv unless this is so. */
5207 /* Check each extension dependent giv in this class to see if its
5208 root biv is safe from wrapping in the interior mode. */
5211 /* Combine all giv's for this iv_class. */
5215 {
5223 /* If an insn is not to be strength reduced, then set its ignore
5224 flag, and clear bl->all_reduced. */
5226 /* A giv that depends on a reversed biv must be reduced if it is
5227 used after the loop exit, otherwise, it would have the wrong
5228 value after the loop exit. To make it simple, just reduce all
5229 of such giv's whether or not we know they are used after the loop
5230 exit. */
5235 {
5243 }
5244 else
5245 {
5246 /* Check that we can increment the reduced giv without a
5247 multiply insn. If not, reject it. */
5252 {
5260 }
5261 }
5262 }
5264 /* Check for givs whose first use is their definition and whose
5265 last use is the definition of another giv. If so, it is likely
5266 dead and should not be used to derive another giv nor to
5267 eliminate a biv. */
5270 /* Reduce each giv that we decided to reduce. */
5273 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
5274 as not reduced.
5276 For each giv register that can be reduced now: if replaceable,
5277 substitute reduced reg wherever the old giv occurs;
5278 else add new move insn "giv_reg = reduced_reg". */
5281 /* All the givs based on the biv bl have been reduced if they
5282 merit it. */
5284 /* For each giv not marked as maybe dead that has been combined with a
5285 second giv, clear any "maybe dead" mark on that second giv.
5286 v->new_reg will either be or refer to the register of the giv it
5287 combined with.
5289 Doing this clearing avoids problems in biv elimination where
5290 a giv's new_reg is a complex value that can't be put in the
5291 insn but the giv combined with (with a reg as new_reg) is
5292 marked maybe_dead. Since the register will be used in either
5293 case, we'd prefer it be used from the simpler giv. */
5299 /* Try to eliminate the biv, if it is a candidate.
5300 This won't work if ! bl->all_reduced,
5301 since the givs we planned to use might not have been reduced.
5303 We have to be careful that we didn't initially think we could
5304 eliminate this biv because of a giv that we now think may be
5305 dead and shouldn't be used as a biv replacement.
5307 Also, there is the possibility that we may have a giv that looks
5308 like it can be used to eliminate a biv, but the resulting insn
5309 isn't valid. This can happen, for example, on the 88k, where a
5310 JUMP_INSN can compare a register only with zero. Attempts to
5311 replace it with a compare with a constant will fail.
5313 Note that in cases where this call fails, we may have replaced some
5314 of the occurrences of the biv with a giv, but no harm was done in
5315 doing so in the rare cases where it can occur. */
5319 {
5320 /* ?? If we created a new test to bypass the loop entirely,
5321 or otherwise drop straight in, based on this test, then
5322 we might want to rewrite it also. This way some later
5323 pass has more hope of removing the initialization of this
5324 biv entirely. */
5326 /* If final_value != 0, then the biv may be used after loop end
5327 and we must emit an insn to set it just in case.
5329 Reversed bivs already have an insn after the loop setting their
5330 value, so we don't need another one. We can't calculate the
5331 proper final value for such a biv here anyways. */
5340 }
5341 /* See above note wrt final_value. But since we couldn't eliminate
5342 the biv, we must set the value after the loop instead of before. */
5346 }
5348 /* Go through all the instructions in the loop, making all the
5349 register substitutions scheduled in REG_MAP. */
5354 {
5358 }
5361 {
5362 /* When we completely unroll a loop we will likely not need the increment
5363 of the loop BIV and we will not need the conditional branch at the
5364 end of the loop. */
5367 #ifdef HAVE_cc0
5368 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
5369 need the comparison before the conditional branch at the end of the
5370 loop. */
5372 #endif
5374 /* We'll need one copy for each loop iteration. */
5377 /* A little slop to account for the ability to remove initialization
5378 code, better CSE, and other secondary benefits of completely
5379 unrolling some loops. */
5382 /* Clamp the value. */
5385 }
5387 /* Unroll loops from within strength reduction so that we can use the
5388 induction variable information that strength_reduce has already
5389 collected. Always unroll loops that would be as small or smaller
5390 unrolled than when rolled. */
5397 #ifdef HAVE_doloop_end
5402 /* In case number of iterations is known, drop branch prediction note
5403 in the branch. Do that only in second loop pass, as loop unrolling
5404 may change the number of iterations performed. */
5406 {
5407 unsigned HOST_WIDE_INT n
5412 }
5420 }
5421 \f
5422 /*Record all basic induction variables calculated in the insn. */
5423 static rtx
5426 {
5428 rtx set;
5429 rtx dest_reg;
5430 rtx inc_val;
5431 rtx mult_val;
5437 {
5442 {
5447 {
5448 /* It is a possible basic induction variable.
5449 Create and initialize an induction structure for it. */
5456 }
5459 }
5460 }
5462 }
5463 \f
5464 /* Record all givs calculated in the insn.
5465 A register is a giv if: it is only set once, it is a function of a
5466 biv and a constant (or invariant), and it is not a biv. */
5467 static rtx
5470 {
5473 rtx set;
5474 /* Look for a general induction variable in a register. */
5479 {
5480 rtx src_reg;
5481 rtx dest_reg;
5482 rtx add_val;
5483 rtx mult_val;
5484 rtx ext_val;
5487 rtx last_consec_insn;
5496 /* Equivalent expression is a giv. */
5501 /* Don't try to handle any regs made by loop optimization.
5502 We have nothing on them in regno_first_uid, etc. */
5504 /* Don't recognize a BASIC_INDUCT_VAR here. */
5506 /* This must be the only place where the register is set. */
5508 /* or all sets must be consecutive and make a giv. */
5513 {
5516 /* If this is a library call, increase benefit. */
5520 /* Skip the consecutive insns, if there are any. */
5528 }
5529 }
5531 /* Look for givs which are memory addresses. */
5534 maybe_multiple);
5536 /* Update the status of whether giv can derive other givs. This can
5537 change when we pass a label or an insn that updates a biv. */
5542 }
5543 \f
5544 /* Return 1 if X is a valid source for an initial value (or as value being
5545 compared against in an initial test).
5547 X must be either a register or constant and must not be clobbered between
5548 the current insn and the start of the loop.
5550 INSN is the insn containing X. */
5552 static int
5554 {
5558 /* Only consider pseudos we know about initialized in insns whose luids
5559 we know. */
5564 /* Don't use call-clobbered registers across a call which clobbers it. On
5565 some machines, don't use any hard registers at all. */
5567 && (SMALL_REGISTER_CLASSES
5571 /* Don't use registers that have been clobbered before the start of the
5572 loop. */
5577 }
5578 \f
5579 /* Scan X for memory refs and check each memory address
5580 as a possible giv. INSN is the insn whose pattern X comes from.
5581 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
5582 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
5583 more than once in each loop iteration. */
5585 static void
5588 {
5598 {
5614 {
5615 rtx src_reg;
5616 rtx add_val;
5617 rtx mult_val;
5618 rtx ext_val;
5621 /* This code used to disable creating GIVs with mult_val == 1 and
5622 add_val == 0. However, this leads to lost optimizations when
5623 it comes time to combine a set of related DEST_ADDR GIVs, since
5624 this one would not be seen. */
5629 {
5630 /* Found one; record it. */
5638 }
5639 }
5644 }
5646 /* Recursively scan the subexpressions for other mem refs. */
5652 maybe_multiple);
5656 maybe_multiple);
5657 }
5658 \f
5659 /* Fill in the data about one biv update.
5660 V is the `struct induction' in which we record the biv. (It is
5661 allocated by the caller, with alloca.)
5662 INSN is the insn that sets it.
5663 DEST_REG is the biv's reg.
5665 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
5666 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
5667 being set to INC_VAL.
5669 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
5670 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
5671 can be executed more than once per iteration. If MAYBE_MULTIPLE
5672 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
5673 executed exactly once per iteration. */
5675 static void
5679 {
5696 /* Add this to the reg's iv_class, creating a class
5697 if this is the first incrementation of the reg. */
5701 {
5702 /* Create and initialize new iv_class. */
5712 /* Set initial value to the reg itself. */
5715 /* We haven't seen the initializing insn yet. */
5725 /* Add this class to ivs->list. */
5729 /* Put it in the array of biv register classes. */
5731 }
5732 else
5733 {
5734 /* Check if location is the same as a previous one. */
5738 {
5741 }
5742 }
5744 /* Update IV_CLASS entry for this biv. */
5753 }
5754 \f
5755 /* Fill in the data about one giv.
5756 V is the `struct induction' in which we record the giv. (It is
5757 allocated by the caller, with alloca.)
5758 INSN is the insn that sets it.
5759 BENEFIT estimates the savings from deleting this insn.
5760 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
5761 into a register or is used as a memory address.
5763 SRC_REG is the biv reg which the giv is computed from.
5764 DEST_REG is the giv's reg (if the giv is stored in a reg).
5765 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
5766 LOCATION points to the place where this giv's value appears in INSN. */
5768 static void
5773 {
5778 rtx temp;
5780 /* Attempt to prove constantness of the values. Don't let simplify_rtx
5781 undo the MULT canonicalization that we performed earlier. */
5811 /* The v->always_computable field is used in update_giv_derive, to
5812 determine whether a giv can be used to derive another giv. For a
5813 DEST_REG giv, INSN computes a new value for the giv, so its value
5814 isn't computable if INSN insn't executed every iteration.
5815 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5816 it does not compute a new value. Hence the value is always computable
5817 regardless of whether INSN is executed each iteration. */
5821 else
5827 {
5830 }
5832 {
5837 /* If the lifetime is zero, it means that this register is
5838 really a dead store. So mark this as a giv that can be
5839 ignored. This will not prevent the biv from being eliminated. */
5845 }
5847 /* Add the giv to the class of givs computed from one biv. */
5851 {
5854 /* Don't count DEST_ADDR. This is supposed to count the number of
5855 insns that calculate givs. */
5859 }
5860 else
5861 /* Fatal error, biv missing for this giv? */
5865 {
5868 }
5869 else
5870 {
5871 /* The giv can be replaced outright by the reduced register only if all
5872 of the following conditions are true:
5873 - the insn that sets the giv is always executed on any iteration
5874 on which the giv is used at all
5875 (there are two ways to deduce this:
5876 either the insn is executed on every iteration,
5877 or all uses follow that insn in the same basic block),
5878 - the giv is not used outside the loop
5879 - no assignments to the biv occur during the giv's lifetime. */
5882 /* Previous line always fails if INSN was moved by loop opt. */
5885 && (! not_every_iteration
5887 {
5888 /* Now check that there are no assignments to the biv within the
5889 giv's lifetime. This requires two separate checks. */
5891 /* Check each biv update, and fail if any are between the first
5892 and last use of the giv.
5894 If this loop contains an inner loop that was unrolled, then
5895 the insn modifying the biv may have been emitted by the loop
5896 unrolling code, and hence does not have a valid luid. Just
5897 mark the biv as not replaceable in this case. It is not very
5898 useful as a biv, because it is used in two different loops.
5899 It is very unlikely that we would be able to optimize the giv
5900 using this biv anyways. */
5905 {
5911 {
5915 }
5916 }
5918 /* If there are any backwards branches that go from after the
5919 biv update to before it, then this giv is not replaceable. */
5923 {
5927 }
5928 }
5929 else
5930 {
5931 /* May still be replaceable, we don't have enough info here to
5932 decide. */
5935 }
5936 }
5938 /* Record whether the add_val contains a const_int, for later use by
5939 combine_givs. */
5940 {
5945 ;
5949 {
5951 {
5956 else
5958 }
5961 }
5962 }
5966 }
5968 /* All this does is determine whether a giv can be made replaceable because
5969 its final value can be calculated. This code can not be part of record_giv
5970 above, because final_giv_value requires that the number of loop iterations
5971 be known, and that can not be accurately calculated until after all givs
5972 have been identified. */
5974 static void
5976 {
5979 /* DEST_ADDR givs will never reach here, because they are always marked
5980 replaceable above in record_giv. */
5982 /* The giv can be replaced outright by the reduced register only if all
5983 of the following conditions are true:
5984 - the insn that sets the giv is always executed on any iteration
5985 on which the giv is used at all
5986 (there are two ways to deduce this:
5987 either the insn is executed on every iteration,
5988 or all uses follow that insn in the same basic block),
5989 - its final value can be calculated (this condition is different
5990 than the one above in record_giv)
5991 - it's not used before the it's set
5992 - no assignments to the biv occur during the giv's lifetime. */
5994 #if 0
5995 /* This is only called now when replaceable is known to be false. */
5996 /* Clear replaceable, so that it won't confuse final_giv_value. */
5998 #endif
6003 {
6006 rtx last_giv_use;
6011 /* When trying to determine whether or not a biv increment occurs
6012 during the lifetime of the giv, we can ignore uses of the variable
6013 outside the loop because final_value is true. Hence we can not
6014 use regno_last_uid and regno_first_uid as above in record_giv. */
6016 /* Search the loop to determine whether any assignments to the
6017 biv occur during the giv's lifetime. Start with the insn
6018 that sets the giv, and search around the loop until we come
6019 back to that insn again.
6021 Also fail if there is a jump within the giv's lifetime that jumps
6022 to somewhere outside the lifetime but still within the loop. This
6023 catches spaghetti code where the execution order is not linear, and
6024 hence the above test fails. Here we assume that the giv lifetime
6025 does not extend from one iteration of the loop to the next, so as
6026 to make the test easier. Since the lifetime isn't known yet,
6027 this requires two loops. See also record_giv above. */
6032 {
6035 {
6038 }
6044 {
6045 /* It is possible for the BIV increment to use the GIV if we
6046 have a cycle. Thus we must be sure to check each insn for
6047 both BIV and GIV uses, and we must check for BIV uses
6048 first. */
6055 {
6057 {
6061 }
6063 }
6064 }
6065 }
6067 /* Now that the lifetime of the giv is known, check for branches
6068 from within the lifetime to outside the lifetime if it is still
6069 replaceable. */
6072 {
6075 {
6088 {
6097 }
6098 }
6099 }
6101 /* If it is replaceable, then save the final value. */
6104 }
6109 }
6110 \f
6111 /* Update the status of whether a giv can derive other givs.
6113 We need to do something special if there is or may be an update to the biv
6114 between the time the giv is defined and the time it is used to derive
6115 another giv.
6117 In addition, a giv that is only conditionally set is not allowed to
6118 derive another giv once a label has been passed.
6120 The cases we look at are when a label or an update to a biv is passed. */
6122 static void
6124 {
6128 rtx tem;
6131 /* Search all IV classes, then all bivs, and finally all givs.
6133 There are three cases we are concerned with. First we have the situation
6134 of a giv that is only updated conditionally. In that case, it may not
6135 derive any givs after a label is passed.
6137 The second case is when a biv update occurs, or may occur, after the
6138 definition of a giv. For certain biv updates (see below) that are
6139 known to occur between the giv definition and use, we can adjust the
6140 giv definition. For others, or when the biv update is conditional,
6141 we must prevent the giv from deriving any other givs. There are two
6142 sub-cases within this case.
6144 If this is a label, we are concerned with any biv update that is done
6145 conditionally, since it may be done after the giv is defined followed by
6146 a branch here (actually, we need to pass both a jump and a label, but
6147 this extra tracking doesn't seem worth it).
6149 If this is a jump, we are concerned about any biv update that may be
6150 executed multiple times. We are actually only concerned about
6151 backward jumps, but it is probably not worth performing the test
6152 on the jump again here.
6154 If this is a biv update, we must adjust the giv status to show that a
6155 subsequent biv update was performed. If this adjustment cannot be done,
6156 the giv cannot derive further givs. */
6162 {
6163 /* Skip if location is the same as a previous one. */
6168 {
6169 /* If cant_derive is already true, there is no point in
6170 checking all of these conditions again. */
6174 /* If this giv is conditionally set and we have passed a label,
6175 it cannot derive anything. */
6179 /* Skip givs that have mult_val == 0, since
6180 they are really invariants. Also skip those that are
6181 replaceable, since we know their lifetime doesn't contain
6182 any biv update. */
6186 /* The only way we can allow this giv to derive another
6187 is if this is a biv increment and we can form the product
6188 of biv->add_val and giv->mult_val. In this case, we will
6189 be able to compute a compensation. */
6191 {
6192 rtx ext_val_dummy;
6203 tem = simplify_giv_expr
6210 else
6212 }
6216 }
6217 }
6218 }
6219 \f
6220 /* Check whether an insn is an increment legitimate for a basic induction var.
6221 X is the source of insn P, or a part of it.
6222 MODE is the mode in which X should be interpreted.
6224 DEST_REG is the putative biv, also the destination of the insn.
6225 We accept patterns of these forms:
6226 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
6227 REG = INVARIANT + REG
6229 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
6230 store the additive term into *INC_VAL, and store the place where
6231 we found the additive term into *LOCATION.
6233 If X is an assignment of an invariant into DEST_REG, we set
6234 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
6236 We also want to detect a BIV when it corresponds to a variable
6237 whose mode was promoted. In that case, an increment
6238 of the variable may be a PLUS that adds a SUBREG of that variable to
6239 an invariant and then sign- or zero-extends the result of the PLUS
6240 into the variable.
6242 Most GIVs in such cases will be in the promoted mode, since that is the
6243 probably the natural computation mode (and almost certainly the mode
6244 used for addresses) on the machine. So we view the pseudo-reg containing
6245 the variable as the BIV, as if it were simply incremented.
6247 Note that treating the entire pseudo as a BIV will result in making
6248 simple increments to any GIVs based on it. However, if the variable
6249 overflows in its declared mode but not its promoted mode, the result will
6250 be incorrect. This is acceptable if the variable is signed, since
6251 overflows in such cases are undefined, but not if it is unsigned, since
6252 those overflows are defined. So we only check for SIGN_EXTEND and
6253 not ZERO_EXTEND.
6255 If we cannot find a biv, we return 0. */
6257 static int
6261 {
6269 {
6275 {
6277 }
6282 {
6284 }
6285 else
6292 /* convert_modes can emit new instructions, e.g. when arg is a loop
6293 invariant MEM and dest_reg has a different mode.
6294 These instructions would be emitted after the end of the function
6295 and then *inc_val would be an uninitialized pseudo.
6296 Detect this and bail in this case.
6297 Other alternatives to solve this can be introducing a convert_modes
6298 variant which is allowed to fail but not allowed to emit new
6299 instructions, emit these instructions before loop start and let
6300 it be garbage collected if *inc_val is never used or saving the
6301 *inc_val initialization sequence generated here and when *inc_val
6302 is going to be actually used, emit it at some suitable place. */
6306 {
6309 }
6317 /* If what's inside the SUBREG is a BIV, then the SUBREG. This will
6318 handle addition of promoted variables.
6319 ??? The comment at the start of this function is wrong: promoted
6320 variable increments don't look like it says they do. */
6326 /* If this register is assigned in a previous insn, look at its
6327 source, but don't go outside the loop or past a label. */
6329 /* If this sets a register to itself, we would repeat any previous
6330 biv increment if we applied this strategy blindly. */
6336 {
6337 rtx dest;
6338 do
6339 {
6341 }
6370 }
6371 /* Fall through. */
6373 /* Can accept constant setting of biv only when inside inner most loop.
6374 Otherwise, a biv of an inner loop may be incorrectly recognized
6375 as a biv of the outer loop,
6376 causing code to be moved INTO the inner loop. */
6383 /* convert_modes aborts if we try to convert to or from CCmode, so just
6384 exclude that case. It is very unlikely that a condition code value
6385 would be a useful iterator anyways. convert_modes aborts if we try to
6386 convert a float mode to non-float or vice versa too. */
6390 {
6391 /* Possible bug here? Perhaps we don't know the mode of X. */
6395 {
6398 }
6403 }
6404 else
6408 /* Ignore this BIV if signed arithmetic overflow is defined. */
6415 /* Similar, since this can be a sign extension. */
6420 ;
6434 location);
6439 }
6440 }
6441 \f
6442 /* A general induction variable (giv) is any quantity that is a linear
6443 function of a basic induction variable,
6444 i.e. giv = biv * mult_val + add_val.
6445 The coefficients can be any loop invariant quantity.
6446 A giv need not be computed directly from the biv;
6447 it can be computed by way of other givs. */
6449 /* Determine whether X computes a giv.
6450 If it does, return a nonzero value
6451 which is the benefit from eliminating the computation of X;
6452 set *SRC_REG to the register of the biv that it is computed from;
6453 set *ADD_VAL and *MULT_VAL to the coefficients,
6454 such that the value of X is biv * mult + add; */
6456 static int
6461 {
6465 /* If this is an invariant, forget it, it isn't a giv. */
6476 {
6479 /* Since this is now an invariant and wasn't before, it must be a giv
6480 with MULT_VAL == 0. It doesn't matter which BIV we associate this
6481 with. */
6488 /* This is equivalent to a BIV. */
6495 /* Either (plus (biv) (invar)) or
6496 (plus (mult (biv) (invar_1)) (invar_2)). */
6498 {
6501 }
6502 else
6503 {
6506 }
6511 /* ADD_VAL is zero. */
6519 }
6521 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
6522 unless they are CONST_INT). */
6530 else
6533 /* Always return true if this is a giv so it will be detected as such,
6534 even if the benefit is zero or negative. This allows elimination
6535 of bivs that might otherwise not be eliminated. */
6537 }
6538 \f
6539 /* Given an expression, X, try to form it as a linear function of a biv.
6540 We will canonicalize it to be of the form
6541 (plus (mult (BIV) (invar_1))
6542 (invar_2))
6543 with possible degeneracies.
6545 The invariant expressions must each be of a form that can be used as a
6546 machine operand. We surround then with a USE rtx (a hack, but localized
6547 and certainly unambiguous!) if not a CONST_INT for simplicity in this
6548 routine; it is the caller's responsibility to strip them.
6550 If no such canonicalization is possible (i.e., two biv's are used or an
6551 expression that is neither invariant nor a biv or giv), this routine
6552 returns 0.
6554 For a nonzero return, the result will have a code of CONST_INT, USE,
6555 REG (for a BIV), PLUS, or MULT. No other codes will occur.
6557 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
6562 static rtx
6564 {
6569 rtx tem;
6571 /* If this is not an integer mode, or if we cannot do arithmetic in this
6572 mode, this can't be a giv. */
6579 {
6586 /* Put constant last, CONST_INT last if both constant. */
6594 /* Handle addition of zero, then addition of an invariant. */
6599 {
6602 /* Adding two invariants must result in an invariant, so enclose
6603 addition operation inside a USE and return it. */
6613 else
6622 /* biv + invar or mult + invar. Return sum. */
6626 /* (a + invar_1) + invar_2. Associate. */
6627 return
6633 arg1)),
6638 }
6640 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
6641 MULT to reduce cases. */
6647 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
6648 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
6649 Recurse to associate the second PLUS. */
6654 return
6662 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
6678 /* Handle "a - b" as "a + b * (-1)". */
6684 constm1_rtx)),
6693 /* Put constant last, CONST_INT last if both constant. */
6698 /* If second argument is not now constant, not giv. */
6702 /* Handle multiply by 0 or 1. */
6710 {
6712 /* biv * invar. Done. */
6716 /* Product of two constants. */
6720 /* invar * invar is a giv, but attempt to simplify it somehow. */
6726 {
6727 /* (invar_0 * invar_1) * invar_2. Associate. */
6734 arg1)),
6736 }
6737 /* Propagate the MULT expressions to the innermost nodes. */
6739 {
6740 /* (invar_0 + invar_1) * invar_2. Distribute. */
6746 arg1),
6750 arg1)),
6752 }
6756 /* (a * invar_1) * invar_2. Associate. */
6762 arg1)),
6766 /* (a + invar_1) * invar_2. Distribute. */
6771 arg1),
6774 arg1)),
6779 }
6782 /* Shift by constant is multiply by power of two. */
6786 return
6795 /* "-a" is "a * (-1)" */
6801 /* "~a" is "-a - 1". Silly, but easy. */
6805 const1_rtx),
6809 /* Already in proper form for invariant. */
6815 /* Conditionally recognize extensions of simple IVs. After we've
6816 computed loop traversal counts and verified the range of the
6817 source IV, we'll reevaluate this as a GIV. */
6819 {
6822 {
6825 }
6826 }
6830 /* If this is a new register, we can't deal with it. */
6834 /* Check for biv or giv. */
6836 {
6840 {
6843 /* Form expression from giv and add benefit. Ensure this giv
6844 can derive another and subtract any needed adjustment if so. */
6846 /* Increasing the benefit here is risky. The only case in which it
6847 is arguably correct is if this is the only use of V. In other
6848 cases, this will artificially inflate the benefit of the current
6849 giv, and lead to suboptimal code. Thus, it is disabled, since
6850 potentially not reducing an only marginally beneficial giv is
6851 less harmful than reducing many givs that are not really
6852 beneficial. */
6853 {
6857 }
6870 {
6873 }
6874 else
6875 {
6878 }
6880 }
6883 do_default:
6884 /* If it isn't an induction variable, and it is invariant, we
6885 may be able to simplify things further by looking through
6886 the bits we just moved outside the loop. */
6888 {
6894 {
6895 /* Ok, we found a match. Substitute and simplify. */
6897 /* If we match another movable, we must use that, as
6898 this one is going away. */
6903 /* If consec is nonzero, this is a member of a group of
6904 instructions that were moved together. We handle this
6905 case only to the point of seeking to the last insn and
6906 looking for a REG_EQUAL. Fail if we don't find one. */
6908 {
6911 do
6912 {
6914 }
6920 }
6921 else
6922 {
6926 }
6929 {
6930 /* What we are most interested in is pointer
6931 arithmetic on invariants -- only take
6932 patterns we may be able to do something with. */
6938 {
6940 benefit);
6943 }
6948 {
6953 }
6954 }
6956 }
6957 }
6959 }
6961 /* Fall through to general case. */
6963 /* If invariant, return as USE (unless CONST_INT).
6964 Otherwise, not giv. */
6969 {
6978 }
6979 else
6981 }
6982 }
6984 /* This routine folds invariants such that there is only ever one
6985 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6987 static rtx
6989 {
6995 {
6998 }
7001 {
7004 }
7005 else
7006 {
7009 }
7010 }
7012 static rtx
7014 {
7016 {
7020 else
7023 }
7026 else
7029 }
7030 \f
7031 /* Help detect a giv that is calculated by several consecutive insns;
7032 for example,
7033 giv = biv * M
7034 giv = giv + A
7035 The caller has already identified the first insn P as having a giv as dest;
7036 we check that all other insns that set the same register follow
7037 immediately after P, that they alter nothing else,
7038 and that the result of the last is still a giv.
7040 The value is 0 if the reg set in P is not really a giv.
7041 Otherwise, the value is the amount gained by eliminating
7042 all the consecutive insns that compute the value.
7044 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
7045 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
7047 The coefficients of the ultimate giv value are stored in
7048 *MULT_VAL and *ADD_VAL. */
7050 static int
7054 {
7060 rtx temp;
7061 rtx set;
7063 /* Indicate that this is a giv so that we can update the value produced in
7064 each insn of the multi-insn sequence.
7066 This induction structure will be used only by the call to
7067 general_induction_var below, so we can allocate it on our stack.
7068 If this is a giv, our caller will replace the induct var entry with
7069 a new induction structure. */
7090 {
7094 /* If libcall, skip to end of call sequence. */
7105 /* Giv created by equivalent expression. */
7111 {
7115 count--;
7119 }
7121 {
7122 /* Allow insns that set something other than this giv to a
7123 constant. Such insns are needed on machines which cannot
7124 include long constants and should not disqualify a giv. */
7133 }
7134 }
7139 }
7140 \f
7141 /* Return an rtx, if any, that expresses giv G2 as a function of the register
7142 represented by G1. If no such expression can be found, or it is clear that
7143 it cannot possibly be a valid address, 0 is returned.
7145 To perform the computation, we note that
7146 G1 = x * v + a and
7147 G2 = y * v + b
7148 where `v' is the biv.
7150 So G2 = (y/b) * G1 + (b - a*y/x).
7152 Note that MULT = y/x.
7154 Update: A and B are now allowed to be additive expressions such that
7155 B contains all variables in A. That is, computing B-A will not require
7156 subtracting variables. */
7158 static rtx
7160 {
7161 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
7166 /* If MULT is not 1, we cannot handle A with non-constants, since we
7167 would then be required to subtract multiples of the registers in A.
7168 This is theoretically possible, and may even apply to some Fortran
7169 constructs, but it is a lot of work and we do not attempt it here. */
7174 /* In general these structures are sorted top to bottom (down the PLUS
7175 chain), but not left to right across the PLUS. If B is a higher
7176 order giv than A, we can strip one level and recurse. If A is higher
7177 order, we'll eventually bail out, but won't know that until the end.
7178 If they are the same, we'll strip one level around this loop. */
7181 {
7193 /* We matched: remove one reg completely. */
7196 /* An alternate match. */
7199 /* An alternate match. */
7201 else
7202 {
7203 /* Indicates an extra register in B. Strip one level from B and
7204 recurse, hoping B was the higher order expression. */
7209 }
7210 }
7212 /* Here we are at the last level of A, go through the cases hoping to
7213 get rid of everything but a constant. */
7216 {
7229 }
7231 {
7233 }
7235 {
7240 }
7242 {
7247 else
7249 }
7254 }
7256 rtx
7258 {
7261 /* The value that G1 will be multiplied by must be a constant integer. Also,
7262 the only chance we have of getting a valid address is if b*c/a (see above
7263 for notation) is also an integer. */
7266 {
7274 }
7277 else
7278 {
7279 /* ??? Find out if the one is a multiple of the other? */
7281 }
7285 {
7286 /* Failed. If we've got a multiplication factor between G1 and G2,
7287 scale G1's addend and try again. */
7289 {
7293 {
7294 HOST_WIDE_INT m;
7298 }
7299 else
7300 {
7302 mult);
7303 }
7306 }
7307 }
7311 /* Form simplified final result. */
7316 else
7321 else
7322 {
7325 {
7329 }
7332 }
7333 }
7334 \f
7335 /* Return an rtx, if any, that expresses giv G2 as a function of the register
7336 represented by G1. This indicates that G2 should be combined with G1 and
7337 that G2 can use (either directly or via an address expression) a register
7338 used to represent G1. */
7340 static rtx
7342 {
7345 /* With the introduction of ext dependent givs, we must care for modes.
7346 G2 must not use a wider mode than G1. */
7356 /* If these givs are identical, they can be combined. We use the results
7357 of express_from because the addends are not in a canonical form, so
7358 rtx_equal_p is a weaker test. */
7359 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
7360 combination to be the other way round. */
7363 {
7365 }
7367 /* If G2 can be expressed as a function of G1 and that function is valid
7368 as an address and no more expensive than using a register for G2,
7369 the expression of G2 in terms of G1 can be used. */
7376 }
7377 \f
7378 /* See if BL is monotonic and has a constant per-iteration increment.
7379 Return the increment if so, otherwise return 0. */
7381 static HOST_WIDE_INT
7383 {
7385 rtx incr;
7387 /* Get the total increment and check that it is constant. */
7393 {
7402 }
7404 }
7407 /* Subroutine of biv_fits_mode_p. Return true if biv BL, when biased by
7408 BIAS, will never exceed the unsigned range of MODE. LOOP is the loop
7409 to which the biv belongs and INCR is its per-iteration increment. */
7411 static bool
7415 {
7418 /* We need to be able to manipulate MODE-size constants. */
7422 /* The number of loop iterations must be constant. */
7426 /* So must the biv's initial value. */
7433 /* Make sure that the initial value is within range. */
7437 /* Set up DELTA and SPAN such that the number of iterations * DELTA
7438 (calculated to arbitrary precision) must be <= SPAN. */
7440 {
7443 }
7444 else
7445 {
7447 /* Handle the special case in which MAXIMUM is the largest
7448 unsigned HOST_WIDE_INT and INITIAL is 0. */
7451 else
7453 }
7455 }
7458 /* Return true if biv BL will never exceed the bounds of MODE. LOOP is
7459 the loop to which BL belongs and INCR is its per-iteration increment.
7460 UNSIGNEDP is true if the biv should be treated as unsigned. */
7462 static bool
7465 {
7469 /* A biv's value will always be limited to its natural mode.
7470 Larger modes will observe the same wrap-around. */
7484 {
7485 /* If the increment is +1, and the exit test is a <, the BIV
7486 cannot overflow. (For <=, we have the problematic case that
7487 the comparison value might be the maximum value of the range.) */
7489 {
7494 }
7496 /* Likewise for increment -1 and exit test >. */
7498 {
7503 }
7504 }
7506 }
7509 /* Given that X is an extension or truncation of BL, return true
7510 if it is unaffected by overflow. LOOP is the loop to which
7511 BL belongs and INCR is its per-iteration increment. */
7513 static bool
7516 {
7521 {
7530 /* We don't know whether this value is being used as signed
7531 or unsigned, so check the conditions for both. */
7538 }
7542 }
7545 /* Check each extension dependent giv in this class to see if its
7546 root biv is safe from wrapping in the interior mode, which would
7547 make the giv illegal. */
7549 static void
7551 {
7553 HOST_WIDE_INT incr;
7557 /* Invalidate givs that fail the tests. */
7560 {
7563 {
7568 }
7569 else
7570 {
7578 }
7579 }
7580 }
7582 /* Generate a version of VALUE in a mode appropriate for initializing V. */
7584 rtx
7586 {
7592 /* Recall that check_ext_dependent_givs verified that the known bounds
7593 of a biv did not overflow or wrap with respect to the extension for
7594 the giv. Therefore, constants need no additional adjustment. */
7598 /* Otherwise, we must adjust the value to compensate for the
7599 differing modes of the biv and the giv. */
7601 }
7602 \f
7603 struct combine_givs_stats
7604 {
7607 };
7609 static int
7611 {
7618 /* Stabilize the sort. */
7622 }
7624 /* Check all pairs of givs for iv_class BL and see if any can be combined with
7625 any other. If so, point SAME to the giv combined with and set NEW_REG to
7626 be an expression (in terms of the other giv's DEST_REG) equivalent to the
7627 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
7629 static void
7631 {
7632 /* Additional benefit to add for being combined multiple times. */
7640 /* Count givs, because bl->giv_count is incorrect here. */
7644 giv_count++;
7656 {
7658 rtx single_use;
7663 /* If a DEST_REG GIV is used only once, do not allow it to combine
7664 with anything, for in doing so we will gain nothing that cannot
7665 be had by simply letting the GIV with which we would have combined
7666 to be reduced on its own. The losage shows up in particular with
7667 DEST_ADDR targets on hosts with reg+reg addressing, though it can
7668 be seen elsewhere as well. */
7675 /* Add an additional weight for zero addends. */
7680 {
7681 rtx this_combine;
7686 {
7689 }
7690 }
7692 }
7694 /* Iterate, combining until we can't. */
7695 restart:
7699 {
7702 {
7708 }
7710 }
7713 {
7719 /* If it has already been combined, skip. */
7724 {
7727 /* If it has already been combined, skip. */
7729 {
7734 /* For destination, we now may replace by mem expression instead
7735 of register. This changes the costs considerably, so add the
7736 compensation. */
7746 /* ??? The new final_[bg]iv_value code does a much better job
7747 of finding replaceable giv's, and hence this code may no
7748 longer be necessary. */
7752 /* To help optimize the next set of combinations, remove
7753 this giv from the benefits of other potential mates. */
7755 {
7759 }
7766 }
7767 }
7769 /* To help optimize the next set of combinations, remove
7770 this giv from the benefits of other potential mates. */
7772 {
7774 {
7778 }
7782 /* We've finished with this giv, and everything it touched.
7783 Restart the combination so that proper weights for the
7784 rest of the givs are properly taken into account. */
7785 /* ??? Ideally we would compact the arrays at this point, so
7786 as to not cover old ground. But sanely compacting
7787 can_combine is tricky. */
7789 }
7790 }
7792 /* Clean up. */
7795 }
7796 \f
7797 /* Generate sequence for REG = B * M + A. B is the initial value of
7798 the basic induction variable, M a multiplicative constant, A an
7799 additive constant and REG the destination register. */
7801 static rtx
7803 {
7804 rtx seq;
7805 rtx result;
7808 /* Use unsigned arithmetic. */
7816 }
7819 /* Update registers created in insn sequence SEQ. */
7821 static void
7823 {
7824 rtx insn;
7826 /* Update register info for alias analysis. */
7830 {
7837 }
7838 }
7841 /* EMIT code before BEFORE_BB/BEFORE_INSN to set REG = B * M + A. B
7842 is the initial value of the basic induction variable, M a
7843 multiplicative constant, A an additive constant and REG the
7844 destination register. */
7846 void
7849 {
7850 rtx seq;
7853 {
7856 }
7858 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
7861 /* Increase the lifetime of any invariants moved further in code. */
7866 /* It is possible that the expansion created lots of new registers.
7867 Iterate over the sequence we just created and record them all. We
7868 must do this before inserting the sequence. */
7872 }
7875 /* Emit insns in loop pre-header to set REG = B * M + A. B is the
7876 initial value of the basic induction variable, M a multiplicative
7877 constant, A an additive constant and REG the destination
7878 register. */
7880 void
7882 {
7883 rtx seq;
7885 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
7888 /* Increase the lifetime of any invariants moved further in code.
7889 ???? Is this really necessary? */
7894 /* It is possible that the expansion created lots of new registers.
7895 Iterate over the sequence we just created and record them all. We
7896 must do this before inserting the sequence. */
7900 }
7903 /* Emit insns after loop to set REG = B * M + A. B is the initial
7904 value of the basic induction variable, M a multiplicative constant,
7905 A an additive constant and REG the destination register. */
7907 void
7909 {
7910 rtx seq;
7912 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
7915 /* It is possible that the expansion created lots of new registers.
7916 Iterate over the sequence we just created and record them all. We
7917 must do this before inserting the sequence. */
7921 }
7925 /* Similar to gen_add_mult, but compute cost rather than generating
7926 sequence. */
7928 static int
7930 {
7940 {
7945 }
7948 }
7949 \f
7950 /* Test whether A * B can be computed without
7951 an actual multiply insn. Value is 1 if so.
7953 ??? This function stinks because it generates a ton of wasted RTL
7954 ??? and as a result fragments GC memory to no end. There are other
7955 ??? places in the compiler which are invoked a lot and do the same
7956 ??? thing, generate wasted RTL just to see if something is possible. */
7958 static int
7960 {
7961 rtx tmp;
7964 /* If only one is constant, make it B. */
7968 /* If first constant, both constant, so don't need multiply. */
7972 /* If second not constant, neither is constant, so would need multiply. */
7976 /* One operand is constant, so might not need multiply insn. Generate the
7977 code for the multiply and see if a call or multiply, or long sequence
7978 of insns is generated. */
7987 {
7990 {
8000 {
8003 }
8006 }
8007 }
8017 }
8018 \f
8019 /* Check to see if loop can be terminated by a "decrement and branch until
8020 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
8021 Also try reversing an increment loop to a decrement loop
8022 to see if the optimization can be performed.
8023 Value is nonzero if optimization was performed. */
8025 /* This is useful even if the architecture doesn't have such an insn,
8026 because it might change a loops which increments from 0 to n to a loop
8027 which decrements from n to 0. A loop that decrements to zero is usually
8028 faster than one that increments from zero. */
8030 /* ??? This could be rewritten to use some of the loop unrolling procedures,
8031 such as approx_final_value, biv_total_increment, loop_iterations, and
8032 final_[bg]iv_value. */
8034 static int
8036 {
8041 rtx reg;
8043 rtx jump_label;
8044 rtx final_value;
8045 rtx start_value;
8046 rtx new_add_val;
8047 rtx comparison;
8048 rtx before_comparison;
8049 rtx p;
8050 rtx jump;
8051 rtx first_compare;
8056 /* If last insn is a conditional branch, and the insn before tests a
8057 register value, try to optimize it. Otherwise, we can't do anything. */
8066 /* Try to compute whether the compare/branch at the loop end is one or
8067 two instructions. */
8073 else
8076 {
8077 /* If more than one condition is present to control the loop, then
8078 do not proceed, as this function does not know how to rewrite
8079 loop tests with more than one condition.
8081 Look backwards from the first insn in the last comparison
8082 sequence and see if we've got another comparison sequence. */
8084 rtx jump1;
8088 }
8090 /* Check all of the bivs to see if the compare uses one of them.
8091 Skip biv's set more than once because we can't guarantee that
8092 it will be zero on the last iteration. Also skip if the biv is
8093 used between its update and the test insn. */
8096 {
8101 first_compare))
8103 }
8105 /* Try swapping the comparison to identify a suitable biv. */
8112 first_compare))
8113 {
8115 VOIDmode,
8119 }
8124 /* Look for the case where the basic induction variable is always
8125 nonnegative, and equals zero on the last iteration.
8126 In this case, add a reg_note REG_NONNEG, which allows the
8127 m68k DBRA instruction to be used. */
8133 {
8134 /* Initial value must be greater than 0,
8135 init_val % -dec_value == 0 to ensure that it equals zero on
8136 the last iteration */
8142 {
8143 /* Register always nonnegative, add REG_NOTE to branch. */
8151 }
8153 /* If the decrement is 1 and the value was tested as >= 0 before
8154 the loop, then we can safely optimize. */
8156 {
8170 {
8178 }
8179 }
8180 }
8183 {
8184 /* Try to change inc to dec, so can apply above optimization. */
8185 /* Can do this if:
8186 all registers modified are induction variables or invariant,
8187 all memory references have non-overlapping addresses
8188 (obviously true if only one write)
8189 allow 2 insns for the compare/jump at the end of the loop. */
8190 /* Also, we must avoid any instructions which use both the reversed
8191 biv and another biv. Such instructions will fail if the loop is
8192 reversed. We meet this condition by requiring that either
8193 no_use_except_counting is true, or else that there is only
8194 one biv. */
8196 /* 1 if the iteration var is used only to count iterations. */
8198 /* 1 if the loop has no memory store, or it has a single memory store
8199 which is reversible. */
8205 {
8209 /* If there are no givs for this biv, and the only exit is the
8210 fall through at the end of the loop, then
8211 see if perhaps there are no uses except to count. */
8215 {
8220 /* An insn that sets the biv is okay. */
8221 ;
8223 /* An insn that doesn't mention the biv is okay. */
8224 ;
8227 {
8228 /* If either of these insns uses the biv and sets a pseudo
8229 that has more than one usage, then the biv has uses
8230 other than counting since it's used to derive a value
8231 that is used more than one time. */
8233 regs);
8235 {
8238 }
8239 }
8240 else
8241 {
8244 }
8245 }
8247 /* A biv has uses besides counting if it is used to set
8248 another biv. */
8252 {
8255 }
8256 }
8259 /* No need to worry about MEMs. */
8260 ;
8262 {
8267 /* If the loop has a single store, and the destination address is
8268 invariant, then we can't reverse the loop, because this address
8269 might then have the wrong value at loop exit.
8270 This would work if the source was invariant also, however, in that
8271 case, the insn should have been moved out of the loop. */
8274 {
8277 /* If we could prove that each of the memory locations
8278 written to was different, then we could reverse the
8279 store -- but we don't presently have any way of
8280 knowing that. */
8283 /* If the store depends on a register that is set after the
8284 store, it depends on the initial value, and is thus not
8285 reversible. */
8287 {
8294 }
8295 }
8296 }
8297 else
8300 /* This code only acts for innermost loops. Also it simplifies
8301 the memory address check by only reversing loops with
8302 zero or one memory access.
8303 Two memory accesses could involve parts of the same array,
8304 and that can't be reversed.
8305 If the biv is used only for counting, than we don't need to worry
8306 about all these things. */
8312 && reversible_mem_store
8317 {
8318 rtx tem;
8320 /* Loop can be reversed. */
8324 /* Now check other conditions:
8326 The increment must be a constant, as must the initial value,
8327 and the comparison code must be LT.
8329 This test can probably be improved since +/- 1 in the constant
8330 can be obtained by changing LT to LE and vice versa; this is
8331 confusing. */
8334 /* for constants, LE gets turned into LT */
8339 {
8351 comparison_const_width
8353 else
8354 comparison_const_width
8358 comparison_sign_mask
8361 /* If the comparison value is not a loop invariant, then we
8362 can not reverse this loop.
8364 ??? If the insns which initialize the comparison value as
8365 a whole compute an invariant result, then we could move
8366 them out of the loop and proceed with loop reversal. */
8374 /* Normalize the initial value if it is an integer and
8375 has no other use except as a counter. This will allow
8376 a few more loops to be reversed. */
8380 {
8382 /* The code below requires comparison_val to be a multiple
8383 of add_val in order to do the loop reversal, so
8384 round up comparison_val to a multiple of add_val.
8385 Since comparison_value is constant, we know that the
8386 current comparison code is LT. */
8388 comparison_val
8390 /* We postpone overflow checks for COMPARISON_VAL here;
8391 even if there is an overflow, we might still be able to
8392 reverse the loop, if converting the loop exit test to
8393 NE is possible. */
8395 }
8397 /* First check if we can do a vanilla loop reversal. */
8400 /* Now do postponed overflow checks on COMPARISON_VAL. */
8403 {
8404 /* Register will always be nonnegative, with value
8405 0 on last iteration */
8409 }
8410 else
8416 /* If the initial value is not zero, or if the comparison
8417 value is not an exact multiple of the increment, then we
8418 can not reverse this loop. */
8421 {
8424 }
8425 else
8426 {
8429 }
8433 /* Reset these in case we normalized the initial value
8434 and comparison value above. */
8437 {
8439 final_value
8441 }
8444 /* Save some info needed to produce the new insns. */
8450 /* Set start_value; if this is not a CONST_INT, we need
8451 to generate a SUB.
8452 Initialize biv to start_value before loop start.
8453 The old initializing insn will be deleted as a
8454 dead store by flow.c. */
8457 {
8458 start_value
8461 }
8463 {
8470 start_value
8476 }
8478 {
8480 initial_value);
8484 start_value
8487 }
8488 else
8489 /* We could handle the other cases too, but it'll be
8490 better to have a testcase first. */
8493 /* We may not have a single insn which can increment a reg, so
8494 create a sequence to hold all the insns from expand_inc. */
8503 /* Update biv info to reflect its new status. */
8508 /* Update loop info. */
8517 /* Inc LABEL_NUSES so that delete_insn will
8518 not delete the label. */
8521 /* If we have a separate comparison insn that does more
8522 than just set cc0, the result of the comparison might
8523 be used outside the loop. */
8525 #ifdef HAVE_CC0
8527 #endif
8528 );
8530 /* Emit an insn after the end of the loop to set the biv's
8531 proper exit value if it is used anywhere outside the loop. */
8541 /* Delete compare/branch at end of loop. */
8546 /* Add new compare/branch insn at end of loop. */
8558 ;
8564 {
8566 {
8567 /* Increment of LABEL_NUSES done above. */
8568 /* Register is now always nonnegative,
8569 so add REG_NONNEG note to the branch. */
8572 }
8574 }
8576 /* No insn may reference both the reversed and another biv or it
8577 will fail (see comment near the top of the loop reversal
8578 code).
8579 Earlier on, we have verified that the biv has no use except
8580 counting, or it is the only biv in this function.
8581 However, the code that computes no_use_except_counting does
8582 not verify reg notes. It's possible to have an insn that
8583 references another biv, and has a REG_EQUAL note with an
8584 expression based on the reversed biv. To avoid this case,
8585 remove all REG_EQUAL notes based on the reversed biv
8586 here. */
8589 {
8592 /* If this is a set of a GIV based on the reversed biv, any
8593 REG_EQUAL notes should still be correct. */
8600 {
8605 else
8607 }
8608 }
8610 /* Mark that this biv has been reversed. Each giv which depends
8611 on this biv, and which is also live past the end of the loop
8612 will have to be fixed up. */
8617 {
8621 else
8623 }
8626 }
8627 }
8628 }
8631 }
8632 \f
8633 /* Verify whether the biv BL appears to be eliminable,
8634 based on the insns in the loop that refer to it.
8636 If ELIMINATE_P is nonzero, actually do the elimination.
8638 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
8639 determine whether invariant insns should be placed inside or at the
8640 start of the loop. */
8642 static int
8645 {
8648 rtx p;
8650 /* Scan all insns in the loop, stopping if we find one that uses the
8651 biv in a way that we cannot eliminate. */
8654 {
8658 rtx note;
8660 /* If this is a libcall that sets a giv, skip ahead to its end. */
8662 {
8666 {
8671 {
8678 }
8679 }
8680 }
8682 /* Closely examine the insn if the biv is mentioned. */
8687 {
8693 }
8695 /* If we are eliminating, kill REG_EQUAL notes mentioning the biv. */
8700 }
8703 {
8708 }
8711 }
8712 \f
8713 /* INSN and REFERENCE are instructions in the same insn chain.
8714 Return nonzero if INSN is first. */
8716 int
8718 {
8722 {
8723 /* Start with test for not first so that INSN == REFERENCE yields not
8724 first. */
8730 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
8731 previous insn, hence the <= comparison below does not work if
8732 P is a note. */
8743 }
8744 }
8746 /* We are trying to eliminate BIV in INSN using GIV. Return nonzero if
8747 the offset that we have to take into account due to auto-increment /
8748 div derivation is zero. */
8749 static int
8752 {
8753 /* If the giv V had the auto-inc address optimization applied
8754 to it, and INSN occurs between the giv insn and the biv
8755 insn, then we'd have to adjust the value used here.
8756 This is rare, so we don't bother to make this possible. */
8765 }
8767 /* If BL appears in X (part of the pattern of INSN), see if we can
8768 eliminate its use. If so, return 1. If not, return 0.
8770 If BIV does not appear in X, return 1.
8772 If ELIMINATE_P is nonzero, actually do the elimination.
8773 WHERE_INSN/WHERE_BB indicate where extra insns should be added.
8774 Depending on how many items have been moved out of the loop, it
8775 will either be before INSN (when WHERE_INSN is nonzero) or at the
8776 start of the loop (when WHERE_INSN is zero). */
8778 static int
8782 {
8788 #ifdef HAVE_cc0
8790 #endif
8796 {
8798 /* If we haven't already been able to do something with this BIV,
8799 we can't eliminate it. */
8805 /* If this sets the BIV, it is not a problem. */
8809 /* If this is an insn that defines a giv, it is also ok because
8810 it will go away when the giv is reduced. */
8815 #ifdef HAVE_cc0
8817 {
8818 /* Can replace with any giv that was reduced and
8819 that has (MULT_VAL != 0) and (ADD_VAL == 0).
8820 Require a constant for MULT_VAL, so we know it's nonzero.
8821 ??? We disable this optimization to avoid potential
8822 overflows. */
8830 {
8837 /* If the giv has the opposite direction of change,
8838 then reverse the comparison. */
8842 else
8845 /* We can probably test that giv's reduced reg. */
8848 }
8850 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
8851 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
8852 Require a constant for MULT_VAL, so we know it's nonzero.
8853 ??? Do this only if ADD_VAL is a pointer to avoid a potential
8854 overflow problem. */
8866 {
8873 /* If the giv has the opposite direction of change,
8874 then reverse the comparison. */
8878 else
8882 /* Replace biv with the giv's reduced register. */
8887 /* Insn doesn't support that constant or invariant. Copy it
8888 into a register (it will be a loop invariant.) */
8895 /* Substitute the new register for its invariant value in
8896 the compare expression. */
8900 }
8901 }
8902 #endif
8909 /* See if either argument is the biv. */
8914 else
8918 {
8919 /* First try to replace with any giv that has constant positive
8920 mult_val and constant add_val. We might be able to support
8921 negative mult_val, but it seems complex to do it in general. */
8933 {
8937 /* Don't eliminate if the linear combination that makes up
8938 the giv overflows when it is applied to ARG. */
8940 {
8941 rtx add_val;
8945 else
8951 }
8956 /* Replace biv with the giv's reduced reg. */
8959 /* If all constants are actually constant integers and
8960 the derived constant can be directly placed in the COMPARE,
8961 do so. */
8964 {
8967 }
8968 else
8969 {
8970 /* Otherwise, load it into a register. */
8975 }
8981 }
8983 /* Look for giv with positive constant mult_val and nonconst add_val.
8984 Insert insns to calculate new compare value.
8985 ??? Turn this off due to possible overflow. */
8993 {
8994 rtx tem;
9004 /* Replace biv with giv's reduced register. */
9008 /* Compute value to compare against. */
9012 /* Use it in this insn. */
9016 }
9017 }
9019 {
9021 {
9022 /* Look for giv with constant positive mult_val and nonconst
9023 add_val. Insert insns to compute new compare value.
9024 ??? Turn this off due to possible overflow. */
9031 {
9032 rtx tem;
9042 /* Replace biv with giv's reduced register. */
9046 /* Compute value to compare against. */
9053 }
9054 }
9056 /* This code has problems. Basically, you can't know when
9057 seeing if we will eliminate BL, whether a particular giv
9058 of ARG will be reduced. If it isn't going to be reduced,
9059 we can't eliminate BL. We can try forcing it to be reduced,
9060 but that can generate poor code.
9062 The problem is that the benefit of reducing TV, below should
9063 be increased if BL can actually be eliminated, but this means
9064 we might have to do a topological sort of the order in which
9065 we try to process biv. It doesn't seem worthwhile to do
9066 this sort of thing now. */
9068 #if 0
9069 /* Otherwise the reg compared with had better be a biv. */
9074 /* Look for a pair of givs, one for each biv,
9075 with identical coefficients. */
9077 {
9089 {
9096 /* Replace biv with its giv's reduced reg. */
9098 /* Replace other operand with the other giv's
9099 reduced reg. */
9102 }
9103 }
9104 #endif
9105 }
9107 /* If we get here, the biv can't be eliminated. */
9111 /* If this address is a DEST_ADDR giv, it doesn't matter if the
9112 biv is used in it, since it will be replaced. */
9120 }
9122 /* See if any subexpression fails elimination. */
9125 {
9127 {
9140 }
9141 }
9144 }
9145 \f
9146 /* Return nonzero if the last use of REG
9147 is in an insn following INSN in the same basic block. */
9149 static int
9151 {
9152 rtx n;
9156 {
9159 }
9161 }
9162 \f
9163 /* Called via `note_stores' to record the initial value of a biv. Here we
9164 just record the location of the set and process it later. */
9166 static void
9168 {
9179 /* If this is the first set found, record it. */
9181 {
9184 }
9185 }
9186 \f
9187 /* If any of the registers in X are "old" and currently have a last use earlier
9188 than INSN, update them to have a last use of INSN. Their actual last use
9189 will be the previous insn but it will not have a valid uid_luid so we can't
9190 use it. X must be a source expression only. */
9192 static void
9194 {
9195 /* Check for the case where INSN does not have a valid luid. In this case,
9196 there is no need to modify the regno_last_uid, as this can only happen
9197 when code is inserted after the loop_end to set a pseudo's final value,
9198 and hence this insn will never be the last use of x.
9199 ???? This comment is not correct. See for example loop_givs_reduce.
9200 This may insert an insn before another new insn. */
9204 {
9206 }
9207 else
9208 {
9212 {
9218 }
9219 }
9220 }
9221 \f
9222 /* Given an insn INSN and condition COND, return the condition in a
9223 canonical form to simplify testing by callers. Specifically:
9225 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
9226 (2) Both operands will be machine operands; (cc0) will have been replaced.
9227 (3) If an operand is a constant, it will be the second operand.
9228 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
9229 for GE, GEU, and LEU.
9231 If the condition cannot be understood, or is an inequality floating-point
9232 comparison which needs to be reversed, 0 will be returned.
9234 If REVERSE is nonzero, then reverse the condition prior to canonizing it.
9236 If EARLIEST is nonzero, it is a pointer to a place where the earliest
9237 insn used in locating the condition was found. If a replacement test
9238 of the condition is desired, it should be placed in front of that
9239 insn and we will be sure that the inputs are still valid.
9241 If WANT_REG is nonzero, we wish the condition to be relative to that
9242 register, if possible. Therefore, do not canonicalize the condition
9243 further. If ALLOW_CC_MODE is nonzero, allow the condition returned
9244 to be a compare to a CC mode register. */
9246 rtx
9249 {
9252 rtx set;
9253 rtx tem;
9271 /* If we are comparing a register with zero, see if the register is set
9272 in the previous insn to a COMPARE or a comparison operation. Perform
9273 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
9274 in cse.c */
9279 {
9280 /* Set nonzero when we find something of interest. */
9283 #ifdef HAVE_cc0
9284 /* If comparison with cc0, import actual comparison from compare
9285 insn. */
9287 {
9298 }
9299 #endif
9301 /* If this is a COMPARE, pick up the two things being compared. */
9303 {
9307 }
9311 /* Go back to the previous insn. Stop if it is not an INSN. We also
9312 stop if it isn't a single set or if it has a REG_INC note because
9313 we don't want to bother dealing with it. */
9327 /* If this is setting OP0, get what it sets it to if it looks
9328 relevant. */
9330 {
9332 #ifdef FLOAT_STORE_FLAG_VALUE
9333 REAL_VALUE_TYPE fsfv;
9334 #endif
9336 /* ??? We may not combine comparisons done in a CCmode with
9337 comparisons not done in a CCmode. This is to aid targets
9338 like Alpha that have an IEEE compliant EQ instruction, and
9339 a non-IEEE compliant BEQ instruction. The use of CCmode is
9340 actually artificial, simply to prevent the combination, but
9341 should not affect other platforms.
9343 However, we must allow VOIDmode comparisons to match either
9344 CCmode or non-CCmode comparison, because some ports have
9345 modeless comparisons inside branch patterns.
9347 ??? This mode check should perhaps look more like the mode check
9348 in simplify_comparison in combine. */
9356 && (STORE_FLAG_VALUE
9359 #ifdef FLOAT_STORE_FLAG_VALUE
9364 #endif
9365 ))
9376 && (STORE_FLAG_VALUE
9379 #ifdef FLOAT_STORE_FLAG_VALUE
9384 #endif
9385 ))
9391 {
9394 }
9395 else
9397 }
9400 /* If this sets OP0, but not directly, we have to give up. */
9404 {
9408 {
9413 }
9418 }
9419 }
9421 /* If constant is first, put it last. */
9425 /* If OP0 is the result of a comparison, we weren't able to find what
9426 was really being compared, so fail. */
9431 /* Canonicalize any ordered comparison with integers involving equality
9432 if we can do computations in the relevant mode and we do not
9433 overflow. */
9439 {
9442 unsigned HOST_WIDE_INT max_val
9446 {
9452 /* When cross-compiling, const_val might be sign-extended from
9453 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
9473 }
9474 }
9476 /* Never return CC0; return zero instead. */
9481 }
9483 /* Given a jump insn JUMP, return the condition that will cause it to branch
9484 to its JUMP_LABEL. If the condition cannot be understood, or is an
9485 inequality floating-point comparison which needs to be reversed, 0 will
9486 be returned.
9488 If EARLIEST is nonzero, it is a pointer to a place where the earliest
9489 insn used in locating the condition was found. If a replacement test
9490 of the condition is desired, it should be placed in front of that
9491 insn and we will be sure that the inputs are still valid.
9493 If ALLOW_CC_MODE is nonzero, allow the condition returned to be a
9494 compare CC mode register. */
9496 rtx
9498 {
9499 rtx cond;
9501 rtx set;
9503 /* If this is not a standard conditional jump, we can't parse it. */
9511 /* If this branches to JUMP_LABEL when the condition is false, reverse
9512 the condition. */
9513 reverse
9518 allow_cc_mode);
9519 }
9521 /* Similar to above routine, except that we also put an invariant last
9522 unless both operands are invariants. */
9524 rtx
9526 {
9536 }
9538 /* Scan the function and determine whether it has indirect (computed) jumps.
9540 This is taken mostly from flow.c; similar code exists elsewhere
9541 in the compiler. It may be useful to put this into rtlanal.c. */
9542 static int
9544 {
9545 rtx insn;
9552 }
9554 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
9555 documentation for LOOP_MEMS for the definition of `appropriate'.
9556 This function is called from prescan_loop via for_each_rtx. */
9558 static int
9560 {
9569 {
9574 /* We're not interested in MEMs that are only clobbered. */
9578 /* We're not interested in the MEM associated with a
9579 CONST_DOUBLE, so there's no need to traverse into this. */
9583 /* We're not interested in any MEMs that only appear in notes. */
9587 /* This is not a MEM. */
9589 }
9591 /* See if we've already seen this MEM. */
9594 {
9598 /* The modes of the two memory accesses are different. If
9599 this happens, something tricky is going on, and we just
9600 don't optimize accesses to this MEM. */
9604 }
9606 /* Resize the array, if necessary. */
9608 {
9611 else
9616 }
9618 /* Actually insert the MEM. */
9620 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
9621 because we can't put it in a register. We still store it in the
9622 table, though, so that if we see the same address later, but in a
9623 non-BLK mode, we'll not think we can optimize it at that point. */
9629 }
9632 /* Allocate REGS->ARRAY or reallocate it if it is too small.
9634 Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
9635 register that is modified by an insn between FROM and TO. If the
9636 value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
9637 more, stop incrementing it, to avoid overflow.
9639 Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
9640 register I is used, if it is only used once. Otherwise, it is set
9641 to 0 (for no uses) or const0_rtx for more than one use. This
9642 parameter may be zero, in which case this processing is not done.
9644 Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
9645 optimize register I. */
9647 static void
9649 {
9652 /* last_set[n] is nonzero iff reg n has been set in the current
9653 basic block. In that case, it is the insn that last set reg n. */
9655 rtx insn;
9661 /* Grow the regs array if not allocated or too small. */
9663 {
9668 /* Zero the new elements. */
9671 }
9673 /* Clear previously scanned fields but do not clear n_times_set. */
9675 {
9679 }
9683 /* Scan the loop, recording register usage. */
9686 {
9688 {
9689 /* Record registers that have exactly one use. */
9692 /* Include uses in REG_EQUAL notes. */
9700 {
9704 last_set);
9705 }
9706 }
9711 /* Invalidate all registers used for function argument passing.
9712 We check rtx_varies_p for the same reason as below, to allow
9713 optimizing PIC calculations. */
9715 {
9716 rtx link;
9718 link;
9720 {
9727 }
9728 }
9729 }
9731 /* Invalidate all hard registers clobbered by calls. With one exception:
9732 a call-clobbered PIC register is still function-invariant for our
9733 purposes, since we can hoist any PIC calculations out of the loop.
9734 Thus the call to rtx_varies_p. */
9739 {
9742 }
9744 #ifdef AVOID_CCMODE_COPIES
9745 /* Don't try to move insns which set CC registers if we should not
9746 create CCmode register copies. */
9750 #endif
9752 /* Set regs->array[I].n_times_set for the new registers. */
9757 }
9759 /* Returns the number of real INSNs in the LOOP. */
9761 static int
9763 {
9765 rtx insn;
9773 }
9775 /* Move MEMs into registers for the duration of the loop. */
9777 static void
9779 {
9786 rtx end_label;
9787 /* Nonzero if the next instruction may never be executed. */
9794 /* We cannot use next_label here because it skips over normal insns. */
9799 /* Check to see if it's possible that some instructions in the loop are
9800 never executed. Also check if there is a goto out of the loop other
9801 than right after the end of the loop. */
9805 {
9809 /* If we enter the loop in the middle, and scan
9810 around to the beginning, don't set maybe_never
9811 for that. This must be an unconditional jump,
9812 otherwise the code at the top of the loop might
9813 never be executed. Unconditional jumps are
9814 followed a by barrier then loop end. */
9819 {
9820 /* If this is a jump outside of the loop but not right
9821 after the end of the loop, we would have to emit new fixup
9822 sequences for each such label. */
9824 JUMP_INSN is executed, we must be conservative. */
9833 /* Something complicated. */
9835 else
9836 /* If there are any more instructions in the loop, they
9837 might not be reached. */
9839 }
9842 }
9844 /* Find start of the extended basic block that enters the loop. */
9848 ;
9853 /* Build table of mems that get set to constant values before the
9854 loop. */
9858 /* Actually move the MEMs. */
9860 {
9861 regset_head load_copies;
9862 regset_head store_copies;
9864 rtx reg;
9866 rtx mem_list_entry;
9870 /* There's no telling whether or not MEM is modified. */
9873 /* Go through the MEMs written to in the loop to see if this
9874 one is aliased by one of them. */
9877 {
9882 {
9883 /* MEM is indeed aliased by this store. */
9886 }
9888 }
9894 /* If this MEM is written to, we must be sure that there
9895 are no reads from another MEM that aliases this one. */
9897 {
9901 {
9905 VOIDmode,
9907 rtx_varies_p))
9908 {
9909 /* It's not safe to hoist loop_info->mems[i] out of
9910 the loop because writes to it might not be
9911 seen by reads from loop_info->mems[j]. */
9914 }
9915 }
9916 }
9919 /* We can't access the MEM outside the loop; it might
9920 cause a trap that wouldn't have happened otherwise. */
9924 /* We thought we were going to lift this MEM out of the
9925 loop, but later discovered that we could not. */
9931 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
9932 order to keep scan_loop from moving stores to this MEM
9933 out of the loop just because this REG is neither a
9934 user-variable nor used in the loop test. */
9939 /* Now, replace all references to the MEM with the
9940 corresponding pseudos. */
9945 {
9947 {
9948 rtx set;
9952 /* See if this copies the mem into a register that isn't
9953 modified afterwards. We'll try to do copy propagation
9954 a little further on. */
9956 /* @@@ This test is _way_ too conservative. */
9957 && ! maybe_never
9965 /* See if this copies the mem from a register that isn't
9966 modified afterwards. We'll try to remove the
9967 redundant copy later on by doing a little register
9968 renaming and copy propagation. This will help
9969 to untangle things for the BIV detection code. */
9971 && ! maybe_never
9979 /* If this is a call which uses / clobbers this memory
9980 location, we must not change the interface here. */
9984 {
9988 }
9989 else
9990 /* Replace the memory reference with the shadow register. */
9993 }
9998 }
10003 /* We couldn't replace all occurrences of the MEM. */
10005 else
10006 {
10007 /* Load the memory immediately before LOOP->START, which is
10008 the NOTE_LOOP_BEG. */
10010 rtx set;
10016 {
10020 {
10024 /* Extending hard register lifetimes causes crash
10025 on SRC targets. Doing so on non-SRC is
10026 probably also not good idea, since we most
10027 probably have pseudoregister equivalence as
10028 well. */
10031 }
10032 /* Use the constant equivalence if that is cheap enough. */
10038 {
10041 }
10043 /* If best_equiv is nonzero, we know that MEM is set to a
10044 constant or register before the loop. We will use this
10045 knowledge to initialize the shadow register with that
10046 constant or reg rather than by loading from MEM. */
10049 }
10054 {
10057 {
10060 }
10061 }
10067 {
10069 {
10072 }
10074 /* Store the memory immediately after END, which is
10075 the NOTE_LOOP_END. */
10078 }
10081 {
10086 }
10088 /* Attempt a bit of copy propagation. This helps untangle the
10089 data flow, and enables {basic,general}_induction_var to find
10090 more bivs/givs. */
10091 EXECUTE_IF_SET_IN_REG_SET
10093 {
10095 });
10098 EXECUTE_IF_SET_IN_REG_SET
10100 {
10102 });
10104 }
10105 }
10107 /* Now, we need to replace all references to the previous exit
10108 label with the new one. */
10115 }
10117 /* For communication between note_reg_stored and its caller. */
10118 struct note_reg_stored_arg
10119 {
10121 rtx reg;
10122 };
10124 /* Called via note_stores, record in SET_SEEN whether X, which is written,
10125 is equal to ARG. */
10126 static void
10128 {
10132 }
10134 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
10135 There must be exactly one insn that sets this pseudo; it will be
10136 deleted if all replacements succeed and we can prove that the register
10137 is not used after the loop. */
10139 static void
10141 {
10142 /* This is the reg that we are copying from. */
10145 rtx insn;
10146 /* These help keep track of whether we replaced all uses of the reg. */
10153 {
10154 rtx set;
10156 /* Only substitute within one extended basic block from the initializing
10157 insn. */
10164 /* Is this the initializing insn? */
10169 {
10176 }
10178 /* Only substitute after seeing the initializing insn. */
10180 {
10187 /* Stop replacing when REPLACEMENT is modified. */
10192 {
10195 /* It is possible that we've turned previously valid REG_EQUAL to
10196 invalid, as we change the REGNO to REPLACEMENT and unlike REGNO,
10197 REPLACEMENT is modified, we get different meaning. */
10201 }
10202 }
10203 }
10207 {
10211 {
10212 rtx first;
10213 rtx retval_note;
10215 /* Assume we're just deleting INIT_INSN. */
10217 /* Look for REG_RETVAL note. If we're deleting the end of
10218 the libcall sequence, the whole sequence can go. */
10220 /* If we found a REG_RETVAL note, find the first instruction
10221 in the sequence. */
10225 /* Delete the instructions. */
10227 }
10230 }
10231 }
10233 /* Replace all the instructions from FIRST up to and including LAST
10234 with NOTE_INSN_DELETED notes. */
10236 static void
10238 {
10240 {
10246 /* If this was the LAST instructions we're supposed to delete,
10247 we're done. */
10252 }
10253 }
10255 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
10256 loop LOOP if the order of the sets of these registers can be
10257 swapped. There must be exactly one insn within the loop that sets
10258 this pseudo followed immediately by a move insn that sets
10259 REPLACEMENT with REGNO. */
10260 static void
10263 {
10264 rtx insn;
10273 {
10274 /* Search for the insn that copies REGNO to NEW_REGNO? */
10282 }
10285 {
10286 rtx prev_insn;
10287 rtx prev_set;
10289 /* Some DEF-USE info would come in handy here to make this
10290 function more general. For now, just check the previous insn
10291 which is the most likely candidate for setting REGNO. */
10299 {
10300 /* We have:
10301 (set (reg regno) (expr))
10302 (set (reg new_regno) (reg regno))
10304 so try converting this to:
10305 (set (reg new_regno) (expr))
10306 (set (reg regno) (reg new_regno))
10308 The former construct is often generated when a global
10309 variable used for an induction variable is shadowed by a
10310 register (NEW_REGNO). The latter construct improves the
10311 chances of GIV replacement and BIV elimination. */
10321 {
10328 /* Update first use of REGNO. */
10332 /* Now perform copy propagation to hopefully
10333 remove all uses of REGNO within the loop. */
10335 }
10336 }
10337 }
10338 }
10340 /* Worker function for find_mem_in_note, called via for_each_rtx. */
10342 static int
10344 {
10346 {
10350 }
10352 }
10354 /* Returns the first MEM found in NOTE by depth-first search. */
10356 static rtx
10358 {
10362 }
10364 /* Replace MEM with its associated pseudo register. This function is
10365 called from load_mems via for_each_rtx. DATA is actually a pointer
10366 to a structure describing the instruction currently being scanned
10367 and the MEM we are currently replacing. */
10369 static int
10371 {
10379 {
10384 /* We're not interested in the MEM associated with a
10385 CONST_DOUBLE, so there's no need to traverse into one. */
10389 /* This is not a MEM. */
10391 }
10394 /* This is not the MEM we are currently replacing. */
10397 /* Actually replace the MEM. */
10401 }
10403 static void
10405 {
10406 loop_replace_args args;
10414 /* If we hoist a mem write out of the loop, then REG_EQUAL
10415 notes referring to the mem are no longer valid. */
10417 {
10422 {
10426 {
10427 /* Remove the note. */
10430 }
10431 }
10432 }
10433 }
10435 /* Replace one register with another. Called through for_each_rtx; PX points
10436 to the rtx being scanned. DATA is actually a pointer to
10437 a structure of arguments. */
10439 static int
10441 {
10452 }
10454 static void
10456 {
10457 loop_replace_args args;
10464 }
10465 \f
10466 /* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB
10467 (ignored in the interim). */
10469 static rtx
10472 rtx pattern)
10473 {
10475 }
10478 /* If WHERE_INSN is nonzero emit insn for PATTERN before WHERE_INSN
10479 in basic block WHERE_BB (ignored in the interim) within the loop
10480 otherwise hoist PATTERN into the loop pre-header. */
10482 rtx
10484 basic_block where_bb ATTRIBUTE_UNUSED,
10486 {
10490 }
10493 /* Emit call insn for PATTERN before WHERE_INSN in basic block
10494 WHERE_BB (ignored in the interim) within the loop. */
10496 static rtx
10498 basic_block where_bb ATTRIBUTE_UNUSED,
10500 {
10502 }
10505 /* Hoist insn for PATTERN into the loop pre-header. */
10507 rtx
10509 {
10511 }
10514 /* Hoist call insn for PATTERN into the loop pre-header. */
10516 static rtx
10518 {
10520 }
10523 /* Sink insn for PATTERN after the loop end. */
10525 rtx
10527 {
10529 }
10531 /* bl->final_value can be either general_operand or PLUS of general_operand
10532 and constant. Emit sequence of instructions to load it into REG. */
10533 static rtx
10535 {
10536 rtx seq;
10544 }
10546 /* If the loop has multiple exits, emit insn for PATTERN before the
10547 loop to ensure that it will always be executed no matter how the
10548 loop exits. Otherwise, emit the insn for PATTERN after the loop,
10549 since this is slightly more efficient. */
10551 static rtx
10553 {
10556 else
10558 }
10559 \f
10560 static void
10562 {
10570 iv_num++;
10575 {
10578 }
10579 }
10582 static void
10585 {
10587 rtx incr;
10598 {
10601 }
10603 {
10606 }
10610 {
10614 }
10617 {
10621 }
10623 /* List the increments. */
10625 {
10629 }
10631 /* List the givs. */
10633 {
10638 else
10641 }
10642 }
10645 static void
10647 {
10658 {
10662 }
10665 }
10668 static void
10670 {
10677 else
10693 {
10695 {
10707 }
10708 }
10719 {
10723 }
10726 }
10729 void
10731 {
10733 }
10736 void
10738 {
10740 }
10743 void
10745 {
10747 }
10750 void
10752 {
10754 }
10757 #define LOOP_BLOCK_NUM_1(INSN) \
10758 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
10760 /* The notes do not have an assigned block, so look at the next insn. */
10761 #define LOOP_BLOCK_NUM(INSN) \
10762 ((INSN) ? (GET_CODE (INSN) == NOTE \
10763 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
10764 : LOOP_BLOCK_NUM_1 (INSN)) \
10765 : -1)
10767 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
10769 static void
10772 {
10773 rtx label;
10778 /* Print diagnostics to compare our concept of a loop with
10779 what the loop notes say. */
10794 {
10814 {
10817 {
10820 }
10821 }
10824 /* This can happen when a marked loop appears as two nested loops,
10825 say from while (a || b) {}. The inner loop won't match
10826 the loop markers but the outer one will. */
10829 }
10830 }
10832 /* Call this function from the debugger to dump LOOP. */
10834 void
10836 {
10838 }
10840 /* Call this function from the debugger to dump LOOPS. */
10842 void
10844 {
10846 }