| blob | a670ef7afa55f30d70b9f5b78baf032ca3480b8c |
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 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
22 /* This is the loop optimization pass of the compiler.
23 It finds invariant computations within loops and moves them
24 to the beginning of the loop. Then it identifies basic and
25 general induction variables. Strength reduction is applied to the general
26 induction variables, and induction variable elimination is applied to
27 the basic induction variables.
29 It also finds cases where
30 a register is set within the loop by zero-extending a narrower value
31 and changes these to zero the entire register once before the loop
32 and merely copy the low part within the loop.
34 Most of the complexity is in heuristics to decide when it is worth
35 while to do these things. */
57 #define LOOP_REG_LIFETIME(LOOP, REGNO) \
58 ((REGNO_LAST_LUID (REGNO) - REGNO_FIRST_LUID (REGNO)))
60 #define LOOP_REG_GLOBAL_P(LOOP, REGNO) \
61 ((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
62 || REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start)))
65 /* Vector mapping INSN_UIDs to luids.
66 The luids are like uids but increase monotonically always.
67 We use them to see whether a jump comes from outside a given loop. */
71 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
72 number the insn is contained in. */
76 /* 1 + largest uid of any insn. */
80 /* 1 + luid of last insn. */
84 /* Number of loops detected in current function. Used as index to the
85 next few tables. */
89 /* Bound on pseudo register number before loop optimization.
90 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
93 /* The value to pass to the next call of reg_scan_update. */
96 #define obstack_chunk_alloc xmalloc
97 #define obstack_chunk_free free
98 \f
99 /* During the analysis of a loop, a chain of `struct movable's
100 is made to record all the movable insns found.
101 Then the entire chain can be scanned to decide which to move. */
103 struct movable
104 {
109 of any registers used within the LIBCALL. */
111 that must be moved with this one. */
114 may be adjusted when matching movables
115 that load the same value are found. */
117 including other movables that force this
118 or match this one. */
122 /* If PARTIAL is 1, GLOBAL means something different:
123 that the reg is live outside the range from where it is set
124 to the following label. */
128 In particular, moving it does not make it
129 invariant. */
131 load SRC, rather than copying INSN. */
133 first insn of a consecutive sets group. */
136 that we should avoid changing when clearing
137 the rest of the reg. */
141 };
146 /* Forward declarations. */
160 #if 0
162 #endif
191 rtx *));
270 {
271 rtx r1;
272 rtx r2;
276 {
277 rtx match;
278 rtx replacement;
279 rtx insn;
282 /* Nonzero iff INSN is between START and END, inclusive. */
283 #define INSN_IN_RANGE_P(INSN, START, END) \
284 (INSN_UID (INSN) < max_uid_for_loop \
285 && INSN_LUID (INSN) >= INSN_LUID (START) \
286 && INSN_LUID (INSN) <= INSN_LUID (END))
288 /* Indirect_jump_in_function is computed once per function. */
296 rtx));
297 \f
298 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
299 copy the value of the strength reduced giv to its original register. */
302 /* Cost of using a register, to normalize the benefits of a giv. */
305 void
307 {
313 }
314 \f
315 /* Compute the mapping from uids to luids.
316 LUIDs are numbers assigned to insns, like uids,
317 except that luids increase monotonically through the code.
318 Start at insn START and stop just before END. Assign LUIDs
319 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
320 static int
324 {
326 rtx insn;
329 {
332 /* Don't assign luids to line-number NOTEs, so that the distance in
333 luids between two insns is not affected by -g. */
337 else
338 /* Give a line number note the same luid as preceding insn. */
340 }
342 }
343 \f
344 /* Entry point of this file. Perform loop optimization
345 on the current function. F is the first insn of the function
346 and DUMPFILE is a stream for output of a trace of actions taken
347 (or 0 if none should be output). */
349 void
351 /* f is the first instruction of a chain of insns for one function */
352 rtx f;
355 {
371 /* Count the number of loops. */
375 {
378 max_loop_num++;
379 }
381 /* Don't waste time if no loops. */
387 /* Get size to use for tables indexed by uids.
388 Leave some space for labels allocated by find_and_verify_loops. */
395 /* Allocate storage for array of loops. */
399 /* Find and process each loop.
400 First, find them, and record them in order of their beginnings. */
403 /* Allocate and initialize auxiliary loop information. */
408 /* Now find all register lifetimes. This must be done after
409 find_and_verify_loops, because it might reorder the insns in the
410 function. */
413 /* This must occur after reg_scan so that registers created by gcse
414 will have entries in the register tables.
416 We could have added a call to reg_scan after gcse_main in toplev.c,
417 but moving this call to init_alias_analysis is more efficient. */
420 /* See if we went too far. Note that get_max_uid already returns
421 one more that the maximum uid of all insn. */
424 /* Now reset it to the actual size we need. See above. */
427 /* find_and_verify_loops has already called compute_luids, but it
428 might have rearranged code afterwards, so we need to recompute
429 the luids now. */
432 /* Don't leave gaps in uid_luid for insns that have been
433 deleted. It is possible that the first or last insn
434 using some register has been deleted by cross-jumping.
435 Make sure that uid_luid for that former insn's uid
436 points to the general area where that insn used to be. */
438 {
442 }
447 /* Determine if the function has indirect jump. On some systems
448 this prevents low overhead loop instructions from being used. */
451 /* Now scan the loops, last ones first, since this means inner ones are done
452 before outer ones. */
454 {
459 }
461 /* If there were lexical blocks inside the loop, they have been
462 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
463 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
464 the BLOCKs as well. */
470 /* Clean up. */
475 }
476 \f
477 /* Returns the next insn, in execution order, after INSN. START and
478 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
479 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
480 insn-stream; it is used with loops that are entered near the
481 bottom. */
483 static rtx
486 rtx insn;
487 {
491 {
493 /* Go to the top of the loop, and continue there. */
495 else
496 /* We're done. */
498 }
501 /* We're done. */
505 }
507 /* Optimize one loop described by LOOP. */
509 /* ??? Could also move memory writes out of loops if the destination address
510 is invariant, the source is invariant, the memory write is not volatile,
511 and if we can prove that no read inside the loop can read this address
512 before the write occurs. If there is a read of this address after the
513 write, then we can also mark the memory read as invariant. */
515 static void
519 {
525 rtx p;
526 /* 1 if we are scanning insns that could be executed zero times. */
528 /* 1 if we are scanning insns that might never be executed
529 due to a subroutine call which might exit before they are reached. */
531 /* Jump insn that enters the loop, or 0 if control drops in. */
533 /* Number of insns in the loop. */
537 /* The SET from an insn, if it is the only SET in the insn. */
539 /* Chain describing insns movable in current loop. */
541 /* Ratio of extra register life span we can justify
542 for saving an instruction. More if loop doesn't call subroutines
543 since in that case saving an insn makes more difference
544 and more registers are available. */
546 /* Nonzero if we are scanning instructions in a sub-loop. */
555 /* Determine whether this loop starts with a jump down to a test at
556 the end. This will occur for a small number of loops with a test
557 that is too complex to duplicate in front of the loop.
559 We search for the first insn or label in the loop, skipping NOTEs.
560 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
561 (because we might have a loop executed only once that contains a
562 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
563 (in case we have a degenerate loop).
565 Note that if we mistakenly think that a loop is entered at the top
566 when, in fact, it is entered at the exit test, the only effect will be
567 slightly poorer optimization. Making the opposite error can generate
568 incorrect code. Since very few loops now start with a jump to the
569 exit test, the code here to detect that case is very conservative. */
572 p != loop_end
578 ;
582 /* If loop end is the end of the current function, then emit a
583 NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy
584 note insn. This is the position we use when sinking insns out of
585 the loop. */
588 else
591 /* Set up variables describing this loop. */
595 /* If loop has a jump before the first label,
596 the true entry is the target of that jump.
597 Start scan from there.
598 But record in LOOP->TOP the place where the end-test jumps
599 back to so we can scan that after the end of the loop. */
601 {
604 /* Loop entry must be unconditional jump (and not a RETURN) */
607 /* Check to see whether the jump actually
608 jumps out of the loop (meaning it's no loop).
609 This case can happen for things like
610 do {..} while (0). If this label was generated previously
611 by loop, we can't tell anything about it and have to reject
612 the loop. */
614 {
617 }
618 }
620 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
621 as required by loop_reg_used_before_p. So skip such loops. (This
622 test may never be true, but it's best to play it safe.)
624 Also, skip loops where we do not start scanning at a label. This
625 test also rejects loops starting with a JUMP_INSN that failed the
626 test above. */
630 {
635 }
637 /* Allocate extra space for REGs that might be created by load_mems.
638 We allocate a little extra slop as well, in the hopes that we
639 won't have to reallocate the regs array. */
643 {
649 }
651 /* Scan through the loop finding insns that are safe to move.
652 Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
653 this reg will be considered invariant for subsequent insns.
654 We consider whether subsequent insns use the reg
655 in deciding whether it is worth actually moving.
657 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
658 and therefore it is possible that the insns we are scanning
659 would never be executed. At such times, we must make sure
660 that it is safe to execute the insn once instead of zero times.
661 When MAYBE_NEVER is 0, all insns will be executed at least once
662 so that is not a problem. */
667 {
672 {
679 /* Figure out what to use as a source of this insn. If a REG_EQUIV
680 note is given or if a REG_EQUAL note with a constant operand is
681 specified, use it as the source and mark that we should move
682 this insn by calling emit_move_insn rather that duplicating the
683 insn.
685 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
686 is present. */
690 else
691 {
696 {
698 /* A libcall block can use regs that don't appear in
699 the equivalent expression. To move the libcall,
700 we must move those regs too. */
702 }
703 }
705 /* Don't try to optimize a register that was made
706 by loop-optimization for an inner loop.
707 We don't know its life-span, so we can't compute the benefit. */
709 ;
711 than the one where it is set (meaning that
712 something after this point in the loop might
713 depend on its value before the set). */
715 /* And the set is not guaranteed to be executed one
716 the loop starts, or the value before the set is
717 needed before the set occurs...
719 ??? Note we have quadratic behaviour here, mitigated
720 by the fact that the previous test will often fail for
721 large loops. Rather than re-scanning the entire loop
722 each time for register usage, we should build tables
723 of the register usage and use them here instead. */
724 && (maybe_never
726 /* It is unsafe to move the set.
728 This code used to consider it OK to move a set of a variable
729 which was not created by the user and not used in an exit test.
730 That behavior is incorrect and was removed. */
731 ;
736 || (tem1
737 = consec_sets_invariant_p
740 p)))
741 /* If the insn can cause a trap (such as divide by zero),
742 can't move it unless it's guaranteed to be executed
743 once loop is entered. Even a function call might
744 prevent the trap insn from being reached
745 (since it might exit!) */
748 {
752 /* A potential lossage is where we have a case where two insns
753 can be combined as long as they are both in the loop, but
754 we move one of them outside the loop. For large loops,
755 this can lose. The most common case of this is the address
756 of a function being called.
758 Therefore, if this register is marked as being used exactly
759 once if we are in a loop with calls (a "large loop"), see if
760 we can replace the usage of this register with the source
761 of this SET. If we can, delete this insn.
763 Don't do this if P has a REG_RETVAL note or if we have
764 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
775 && (! SMALL_REGISTER_CLASSES
778 /* This test is not redundant; SET_SRC (set) might be
779 a call-clobbered register and the life of REGNO
780 might span a call. */
786 {
787 /* Replace any usage in a REG_EQUAL note. Must copy the
788 new source, so that we don't get rtx sharing between the
789 SET_SOURCE and REG_NOTES of insn p. */
799 }
817 /* Set M->cond if either loop_invariant_p
818 or consec_sets_invariant_p returned 2
819 (only conditionally invariant). */
828 /* Add M to the end of the chain MOVABLES. */
832 {
833 /* It is possible for the first instruction to have a
834 REG_EQUAL note but a non-invariant SET_SRC, so we must
835 remember the status of the first instruction in case
836 the last instruction doesn't have a REG_EQUAL note. */
839 /* Skip this insn, not checking REG_LIBCALL notes. */
841 /* Skip the consecutive insns, if there are any. */
843 /* Back up to the last insn of the consecutive group. */
846 /* We must now reset m->move_insn, m->is_equiv, and possibly
847 m->set_src to correspond to the effects of all the
848 insns. */
852 else
853 {
857 else
860 }
862 }
863 }
864 /* If this register is always set within a STRICT_LOW_PART
865 or set to zero, then its high bytes are constant.
866 So clear them outside the loop and within the loop
867 just load the low bytes.
868 We must check that the machine has an instruction to do so.
869 Also, if the value loaded into the register
870 depends on the same register, this cannot be done. */
880 {
883 {
897 /* If the insn may not be executed on some cycles,
898 we can't clear the whole reg; clear just high part.
899 Not even if the reg is used only within this loop.
900 Consider this:
901 while (1)
902 while (s != t) {
903 if (foo ()) x = *s;
904 use (x);
905 }
906 Clearing x before the inner loop could clobber a value
907 being saved from the last time around the outer loop.
908 However, if the reg is not used outside this loop
909 and all uses of the register are in the same
910 basic block as the store, there is no problem.
912 If this insn was made by loop, we don't know its
913 INSN_LUID and hence must make a conservative
914 assumption. */
917 || (labels_in_range_p
921 else
929 /* Add M to the end of the chain MOVABLES. */
931 }
932 }
933 }
934 /* Past a call insn, we get to insns which might not be executed
935 because the call might exit. This matters for insns that trap.
936 Constant and pure call insns always return, so they don't count. */
939 /* Past a label or a jump, we get to insns for which we
940 can't count on whether or how many times they will be
941 executed during each iteration. Therefore, we can
942 only move out sets of trivial variables
943 (those not used after the loop). */
944 /* Similar code appears twice in strength_reduce. */
946 /* If we enter the loop in the middle, and scan around to the
947 beginning, don't set maybe_never for that. This must be an
948 unconditional jump, otherwise the code at the top of the
949 loop might never be executed. Unconditional jumps are
950 followed a by barrier then loop end. */
956 {
957 /* At the virtual top of a converted loop, insns are again known to
958 be executed: logically, the loop begins here even though the exit
959 code has been duplicated. */
963 loop_depth++;
965 loop_depth--;
966 }
967 }
969 /* If one movable subsumes another, ignore that other. */
973 /* For each movable insn, see if the reg that it loads
974 leads when it dies right into another conditionally movable insn.
975 If so, record that the second insn "forces" the first one,
976 since the second can be moved only if the first is. */
980 /* See if there are multiple movable insns that load the same value.
981 If there are, make all but the first point at the first one
982 through the `match' field, and add the priorities of them
983 all together as the priority of the first. */
987 /* Now consider each movable insn to decide whether it is worth moving.
988 Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
990 Generally this increases code size, so do not move moveables when
991 optimizing for code size. */
996 /* Now candidates that still are negative are those not moved.
997 Change regs->array[I].set_in_loop to indicate that those are not actually
998 invariant. */
1003 /* Now that we've moved some things out of the loop, we might be able to
1004 hoist even more memory references. */
1007 /* Recalculate regs->array if load_mems has created new registers. */
1015 ;
1022 {
1024 /* Ensure our label doesn't go away. */
1035 }
1038 /* The movable information is required for strength reduction. */
1044 }
1045 \f
1046 /* Add elements to *OUTPUT to record all the pseudo-regs
1047 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1049 void
1053 {
1061 {
1079 }
1083 {
1087 {
1096 }
1097 }
1098 }
1099 \f
1100 /* Check what regs are referred to in the libcall block ending with INSN,
1101 aside from those mentioned in the equivalent value.
1102 If there are none, return 0.
1103 If there are one or more, return an EXPR_LIST containing all of them. */
1105 rtx
1108 {
1113 /* First, find all the regs used in the libcall block
1114 that are not mentioned as inputs to the result. */
1117 {
1122 }
1125 }
1126 \f
1127 /* Return 1 if all uses of REG
1128 are between INSN and the end of the basic block. */
1130 static int
1133 {
1135 rtx p;
1140 /* Search this basic block for the already recorded last use of the reg. */
1142 {
1144 {
1150 /* Ordinary insn: if this is the last use, we win. */
1156 /* Jump insn: if this is the last use, we win. */
1159 /* Otherwise, it's the end of the basic block, so we lose. */
1164 /* It's the end of the basic block, so we lose. */
1169 }
1170 }
1172 /* The "last use" that was recorded can't be found after the first
1173 use. This can happen when the last use was deleted while
1174 processing an inner loop, this inner loop was then completely
1175 unrolled, and the outer loop is always exited after the inner loop,
1176 so that everything after the first use becomes a single basic block. */
1178 }
1179 \f
1180 /* Compute the benefit of eliminating the insns in the block whose
1181 last insn is LAST. This may be a group of insns used to compute a
1182 value directly or can contain a library call. */
1184 static int
1186 rtx last;
1187 {
1188 rtx insn;
1193 {
1196 routine. */
1200 benefit++;
1201 }
1204 }
1205 \f
1206 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1208 static rtx
1210 rtx insn;
1212 {
1214 {
1215 rtx temp;
1217 /* If first insn of libcall sequence, skip to end. */
1218 /* Do this at start of loop, since INSN is guaranteed to
1219 be an insn here. */
1224 do
1227 }
1230 }
1232 /* Ignore any movable whose insn falls within a libcall
1233 which is part of another movable.
1234 We make use of the fact that the movable for the libcall value
1235 was made later and so appears later on the chain. */
1237 static void
1240 {
1244 {
1245 /* Is this a movable for the value of a libcall? */
1248 {
1249 rtx insn;
1250 /* Check for earlier movables inside that range,
1251 and mark them invalid. We cannot use LUIDs here because
1252 insns created by loop.c for prior loops don't have LUIDs.
1253 Rather than reject all such insns from movables, we just
1254 explicitly check each insn in the libcall (since invariant
1255 libcalls aren't that common). */
1260 }
1261 }
1262 }
1264 /* For each movable insn, see if the reg that it loads
1265 leads when it dies right into another conditionally movable insn.
1266 If so, record that the second insn "forces" the first one,
1267 since the second can be moved only if the first is. */
1269 static void
1272 {
1275 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1277 {
1280 /* ??? Could this be a bug? What if CSE caused the
1281 register of M1 to be used after this insn?
1282 Since CSE does not update regno_last_uid,
1283 this insn M->insn might not be where it dies.
1284 But very likely this doesn't matter; what matters is
1285 that M's reg is computed from M1's reg. */
1290 /* If m->consec, m->set_src isn't valid. */
1294 /* Increase the priority of the moving the first insn
1295 since it permits the second to be moved as well. */
1297 {
1301 }
1302 }
1303 }
1304 \f
1305 /* Find invariant expressions that are equal and can be combined into
1306 one register. */
1308 static void
1312 {
1317 /* Regs that are set more than once are not allowed to match
1318 or be matched. I'm no longer sure why not. */
1319 /* Perhaps testing m->consec_sets would be more appropriate here? */
1324 {
1331 /* We want later insns to match the first one. Don't make the first
1332 one match any later ones. So start this loop at m->next. */
1336 /* A reg used outside the loop mustn't be eliminated. */
1338 /* A reg used for zero-extending mustn't be eliminated. */
1341 ||
1342 (
1343 /* Can combine regs with different modes loaded from the
1344 same constant only if the modes are the same or
1345 if both are integer modes with M wider or the same
1346 width as M1. The check for integer is redundant, but
1347 safe, since the only case of differing destination
1348 modes with equal sources is when both sources are
1349 VOIDmode, i.e., CONST_INT. */
1355 /* See if the source of M1 says it matches M. */
1362 {
1368 }
1369 }
1371 /* Now combine the regs used for zero-extension.
1372 This can be done for those not marked `global'
1373 provided their lives don't overlap. */
1377 {
1380 /* Combine all the registers for extension from mode MODE.
1381 Don't combine any that are used outside this loop. */
1385 {
1391 {
1392 /* First one: don't check for overlap, just record it. */
1395 }
1397 /* Make sure they extend to the same mode.
1398 (Almost always true.) */
1402 /* We already have one: check for overlap with those
1403 already combined together. */
1410 /* No overlap: we can combine this with the others. */
1416 overlap:
1417 ;
1418 }
1419 }
1421 /* Clean up. */
1423 }
1424 \f
1425 /* Return 1 if regs X and Y will become the same if moved. */
1427 static int
1431 {
1448 }
1450 /* Return 1 if X and Y are identical-looking rtx's.
1451 This is the Lisp function EQUAL for rtx arguments.
1453 If two registers are matching movables or a movable register and an
1454 equivalent constant, consider them equal. */
1456 static int
1461 {
1475 /* If we have a register and a constant, they may sometimes be
1476 equal. */
1479 {
1484 }
1487 {
1492 }
1494 /* Otherwise, rtx's of different codes cannot be equal. */
1498 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1499 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1504 /* These three types of rtx's can be compared nonrecursively. */
1513 /* Compare the elements. If any pair of corresponding elements
1514 fail to match, return 0 for the whole things. */
1518 {
1520 {
1532 /* Two vectors must have the same length. */
1536 /* And the corresponding elements must match. */
1555 /* These are just backpointers, so they don't matter. */
1561 /* It is believed that rtx's at this level will never
1562 contain anything but integers and other rtx's,
1563 except for within LABEL_REFs and SYMBOL_REFs. */
1566 }
1567 }
1569 }
1570 \f
1571 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1572 insns in INSNS which use the reference. LABEL_NUSES for CODE_LABEL
1573 references is incremented once for each added note. */
1575 static void
1577 rtx x;
1578 rtx insns;
1579 {
1583 rtx insn;
1586 {
1587 /* This code used to ignore labels that referred to dispatch tables to
1588 avoid flow generating (slighly) worse code.
1590 We no longer ignore such label references (see LABEL_REF handling in
1591 mark_jump_label for additional information). */
1594 {
1599 }
1600 }
1604 {
1610 }
1611 }
1612 \f
1613 /* Scan MOVABLES, and move the insns that deserve to be moved.
1614 If two matching movables are combined, replace one reg with the
1615 other throughout. */
1617 static void
1623 {
1631 /* Map of pseudo-register replacements to handle combining
1632 when we move several insns that load the same value
1633 into different pseudo-registers. */
1640 {
1641 /* Describe this movable insn. */
1644 {
1665 }
1667 /* Count movables. Value used in heuristics in strength_reduce. */
1670 /* Ignore the insn if it's already done (it matched something else).
1671 Otherwise, see if it is now safe to move. */
1683 {
1688 /* We have an insn that is safe to move.
1689 Compute its desirability. */
1700 /* An insn MUST be moved if we already moved something else
1701 which is safe only if this one is moved too: that is,
1702 if already_moved[REGNO] is nonzero. */
1704 /* An insn is desirable to move if the new lifetime of the
1705 register is no more than THRESHOLD times the old lifetime.
1706 If it's not desirable, it means the loop is so big
1707 that moving won't speed things up much,
1708 and it is liable to make register usage worse. */
1710 /* It is also desirable to move if it can be moved at no
1711 extra cost because something else was already moved. */
1714 || flag_move_all_movables
1719 {
1724 /* Now move the insns that set the reg. */
1727 {
1730 /* Find the end of this chain of matching regs.
1731 Thus, we load each reg in the chain from that one reg.
1732 And that reg is loaded with 0 directly,
1733 since it has ->match == 0. */
1739 /* Mark the moved, invariant reg as being allowed to
1740 share a hard reg with the other matching invariant. */
1744 regs_may_share
1747 regs_may_share));
1755 }
1756 /* If we are to re-generate the item being moved with a
1757 new move insn, first delete what we have and then emit
1758 the move insn before the loop. */
1760 {
1764 {
1765 /* If this is the first insn of a library call sequence,
1766 skip to the end. */
1771 /* If this is the last insn of a libcall sequence, then
1772 delete every insn in the sequence except the last.
1773 The last insn is handled in the normal manner. */
1776 {
1780 }
1785 /* simplify_giv_expr expects that it can walk the insns
1786 at m->insn forwards and see this old sequence we are
1787 tossing here. delete_insn does preserve the next
1788 pointers, but when we skip over a NOTE we must fix
1789 it up. Otherwise that code walks into the non-deleted
1790 insn stream. */
1793 }
1812 /* The more regs we move, the less we like moving them. */
1814 }
1815 else
1816 {
1818 {
1821 /* If first insn of libcall sequence, skip to end. */
1822 /* Do this at start of loop, since p is guaranteed to
1823 be an insn here. */
1828 /* If last insn of libcall sequence, move all
1829 insns except the last before the loop. The last
1830 insn is handled in the normal manner. */
1833 {
1841 {
1842 rtx body;
1843 rtx n;
1844 rtx next;
1851 /* Find the next insn after TEMP,
1852 not counting USE or NOTE insns. */
1860 /* If that is the call, this may be the insn
1861 that loads the function address.
1863 Extract the function address from the insn
1864 that loads it into a register.
1865 If this insn was cse'd, we get incorrect code.
1867 So emit a new move insn that copies the
1868 function address into the register that the
1869 call insn will use. flow.c will delete any
1870 redundant stores that we have created. */
1875 NULL_RTX)))
1876 {
1882 }
1883 /* We have the call insn.
1884 If it uses the register we suspect it might,
1885 load it with the correct address directly. */
1890 gen_move_insn
1894 {
1896 /* Because the USAGE information potentially
1897 contains objects other than hard registers
1898 we need to copy it. */
1902 }
1903 else
1911 }
1914 }
1916 {
1917 /* P sets REG to zero; but we should clear only
1918 the bits that are not covered by the mode
1919 m->savemode. */
1921 rtx sequence;
1922 rtx tem;
1925 tem = expand_binop
1938 }
1940 {
1942 /* Because the USAGE information potentially
1943 contains objects other than hard registers
1944 we need to copy it. */
1948 }
1950 {
1951 rtx seq;
1952 /* The SET_SRC might not be invariant, so we must
1953 use the REG_EQUAL note. */
1968 }
1969 else
1973 {
1976 /* If there is a REG_EQUAL note present whose value
1977 is not loop invariant, then delete it, since it
1978 may cause problems with later optimization passes.
1979 It is possible for cse to create such notes
1980 like this as a result of record_jump_cond. */
1985 }
1994 /* If library call, now fix the REG_NOTES that contain
1995 insn pointers, namely REG_LIBCALL on FIRST
1996 and REG_RETVAL on I1. */
1998 {
2002 }
2008 /* simplify_giv_expr expects that it can walk the insns
2009 at m->insn forwards and see this old sequence we are
2010 tossing here. delete_insn does preserve the next
2011 pointers, but when we skip over a NOTE we must fix
2012 it up. Otherwise that code walks into the non-deleted
2013 insn stream. */
2016 }
2018 /* The more regs we move, the less we like moving them. */
2020 }
2022 /* Any other movable that loads the same register
2023 MUST be moved. */
2026 /* This reg has been moved out of one loop. */
2029 /* The reg set here is now invariant. */
2035 /* Change the length-of-life info for the register
2036 to say it lives at least the full length of this loop.
2037 This will help guide optimizations in outer loops. */
2040 /* This is the old insn before all the moved insns.
2041 We can't use the moved insn because it is out of range
2042 in uid_luid. Only the old insns have luids. */
2047 /* Combine with this moved insn any other matching movables. */
2052 {
2053 rtx temp;
2055 /* Schedule the reg loaded by M1
2056 for replacement so that shares the reg of M.
2057 If the modes differ (only possible in restricted
2058 circumstances, make a SUBREG.
2060 Note this assumes that the target dependent files
2061 treat REG and SUBREG equally, including within
2062 GO_IF_LEGITIMATE_ADDRESS and in all the
2063 predicates since we never verify that replacing the
2064 original register with a SUBREG results in a
2065 recognizable insn. */
2068 else
2073 /* Get rid of the matching insn
2074 and prevent further processing of it. */
2077 /* if library call, delete all insn except last, which
2078 is deleted below */
2080 NULL_RTX)))
2081 {
2085 }
2088 /* Any other movable that loads the same register
2089 MUST be moved. */
2092 /* The reg merged here is now invariant,
2093 if the reg it matches is invariant. */
2096 }
2097 }
2100 }
2106 }
2111 /* Go through all the instructions in the loop, making
2112 all the register substitutions scheduled in REG_MAP. */
2116 {
2120 }
2122 /* Clean up. */
2125 }
2128 static void
2132 {
2135 else
2138 }
2141 static void
2144 {
2149 {
2152 }
2153 }
2154 \f
2155 #if 0
2156 /* Scan X and replace the address of any MEM in it with ADDR.
2157 REG is the address that MEM should have before the replacement. */
2159 static void
2162 {
2171 {
2183 /* Short cut for very common case. */
2188 /* Short cut for very common case. */
2193 /* If this MEM uses a reg other than the one we expected,
2194 something is wrong. */
2202 }
2206 {
2210 {
2214 }
2215 }
2216 }
2217 #endif
2218 \f
2219 /* Return the number of memory refs to addresses that vary
2220 in the rtx X. */
2222 static int
2225 rtx x;
2226 {
2237 {
2254 }
2259 {
2263 {
2267 }
2268 }
2270 }
2271 \f
2272 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2273 `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2274 `unknown_address_altered', `unknown_constant_address_altered', and
2275 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2276 list `store_mems' in LOOP. */
2278 static void
2281 {
2283 rtx insn;
2287 /* The label after END. Jumping here is just like falling off the
2288 end of the loop. We use next_nonnote_insn instead of next_label
2289 as a hedge against the (pathological) case where some actual insn
2290 might end up between the two. */
2312 {
2314 {
2317 }
2318 }
2322 {
2324 {
2326 {
2328 /* Count number of loops contained in this one. */
2330 }
2332 {
2334 }
2335 }
2337 {
2339 {
2342 }
2344 }
2346 {
2366 {
2368 {
2371 }
2372 else
2373 {
2375 }
2377 do
2378 {
2380 {
2382 {
2383 /* Something tricky. */
2386 }
2389 {
2390 /* A jump outside the current loop. */
2393 }
2394 }
2398 }
2400 }
2401 }
2404 }
2406 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2408 anywhere. */
2410 /* We don't want loads for MEMs moved to a location before the
2411 one at which their stack memory becomes allocated. (Note
2412 that this is not a problem for malloc, etc., since those
2413 require actual function calls. */
2414 && ! current_function_calls_alloca
2415 /* There are ways to leave the loop other than falling off the
2416 end. */
2422 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2423 that loop_invariant_p and load_mems can use true_dependence
2424 to determine what is really clobbered. */
2426 {
2429 loop_info->store_mems
2431 }
2433 {
2437 loop_info->store_mems
2439 }
2440 }
2441 \f
2442 /* Scan the function looking for loops. Record the start and end of each loop.
2443 Also mark as invalid loops any loops that contain a setjmp or are branched
2444 to from outside the loop. */
2446 static void
2448 rtx f;
2450 {
2451 rtx insn;
2452 rtx label;
2462 /* If there are jumps to undefined labels,
2463 treat them as jumps out of any/all loops.
2464 This also avoids writing past end of tables when there are no loops. */
2467 /* Find boundaries of loops, mark which loops are contained within
2468 loops, and invalidate loops that have setjmp. */
2473 {
2476 {
2480 num_loops++;
2487 /* In this case, we must invalidate our current loop and any
2488 enclosing loop. */
2490 {
2496 }
2517 }
2519 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2520 enclosing loop, but this doesn't matter. */
2522 }
2524 /* Any loop containing a label used in an initializer must be invalidated,
2525 because it can be jumped into from anywhere. */
2528 {
2532 }
2534 /* Any loop containing a label used for an exception handler must be
2535 invalidated, because it can be jumped into from anywhere. */
2538 {
2542 }
2544 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2545 loop that it is not contained within, that loop is marked invalid.
2546 If any INSN or CALL_INSN uses a label's address, then the loop containing
2547 that label is marked invalid, because it could be jumped into from
2548 anywhere.
2550 Also look for blocks of code ending in an unconditional branch that
2551 exits the loop. If such a block is surrounded by a conditional
2552 branch around the block, move the block elsewhere (see below) and
2553 invert the jump to point to the code block. This may eliminate a
2554 label in our loop and will simplify processing by both us and a
2555 possible second cse pass. */
2559 {
2563 {
2566 {
2570 }
2571 }
2578 /* See if this is an unconditional branch outside the loop. */
2586 {
2587 rtx p;
2593 /* Go backwards until we reach the start of the loop, a label,
2594 or a JUMP_INSN. */
2601 ;
2603 /* Check for the case where we have a jump to an inner nested
2604 loop, and do not perform the optimization in that case. */
2607 {
2610 {
2615 }
2616 }
2618 /* Make sure that the target of P is within the current loop. */
2624 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2625 we have a block of code to try to move.
2627 We look backward and then forward from the target of INSN
2628 to find a BARRIER at the same loop depth as the target.
2629 If we find such a BARRIER, we make a new label for the start
2630 of the block, invert the jump in P and point it to that label,
2631 and move the block of code to the spot we found. */
2636 /* Just ignore jumps to labels that were never emitted.
2637 These always indicate compilation errors. */
2641 /* If it's not safe to move the sequence, then we
2642 mustn't try. */
2645 {
2646 rtx target
2653 /* Don't move things inside a tablejump. */
2666 /* Don't move things inside a tablejump. */
2677 {
2681 /* Ensure our label doesn't go away. */
2684 /* Verify that uid_loop is large enough and that
2685 we can invert P. */
2687 {
2690 /* If no suitable BARRIER was found, create a suitable
2691 one before TARGET. Since TARGET is a fall through
2692 path, we'll need to insert an jump around our block
2693 and a add a BARRIER before TARGET.
2695 This creates an extra unconditional jump outside
2696 the loop. However, the benefits of removing rarely
2697 executed instructions from inside the loop usually
2698 outweighs the cost of the extra unconditional jump
2699 outside the loop. */
2701 {
2702 rtx temp;
2709 }
2711 /* Include the BARRIER after INSN and copy the
2712 block after LOC. */
2714 last_insn_to_move);
2717 /* All those insns are now in TARGET_LOOP. */
2723 /* The label jumped to by INSN is no longer a loop
2724 exit. Unless INSN does not have a label (e.g.,
2725 it is a RETURN insn), search loop->exit_labels
2726 to find its label_ref, and remove it. Also turn
2727 off LABEL_OUTSIDE_LOOP_P bit. */
2729 {
2731 r;
2734 {
2738 else
2741 }
2747 /* If we didn't find it, then something is
2748 wrong. */
2751 }
2753 /* P is now a jump outside the loop, so it must be put
2754 in loop->exit_labels, and marked as such.
2755 The easiest way to do this is to just call
2756 mark_loop_jump again for P. */
2759 /* If INSN now jumps to the insn after it,
2760 delete INSN. */
2765 }
2767 /* Continue the loop after where the conditional
2768 branch used to jump, since the only branch insn
2769 in the block (if it still remains) is an inter-loop
2770 branch and hence needs no processing. */
2776 /* This loop will be continued with NEXT_INSN (insn). */
2778 }
2779 }
2780 }
2781 }
2782 }
2784 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2785 loops it is contained in, mark the target loop invalid.
2787 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2789 static void
2791 rtx x;
2793 {
2799 {
2811 /* There could be a label reference in here. */
2823 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2835 /* Link together all labels that branch outside the loop. This
2836 is used by final_[bg]iv_value and the loop unrolling code. Also
2837 mark this LABEL_REF so we know that this branch should predict
2838 false. */
2840 /* A check to make sure the label is not in an inner nested loop,
2841 since this does not count as a loop exit. */
2843 {
2848 }
2849 else
2853 {
2862 }
2864 /* If this is inside a loop, but not in the current loop or one enclosed
2865 by it, it invalidates at least one loop. */
2870 /* We must invalidate every nested loop containing the target of this
2871 label, except those that also contain the jump insn. */
2874 {
2875 /* Stop when we reach a loop that also contains the jump insn. */
2880 /* If we get here, we know we need to invalidate a loop. */
2887 }
2891 /* If this is not setting pc, ignore. */
2913 /* Strictly speaking this is not a jump into the loop, only a possible
2914 jump out of the loop. However, we have no way to link the destination
2915 of this jump onto the list of exit labels. To be safe we mark this
2916 loop and any containing loops as invalid. */
2918 {
2920 {
2926 }
2927 }
2929 }
2930 }
2931 \f
2932 /* Return nonzero if there is a label in the range from
2933 insn INSN to and including the insn whose luid is END
2934 INSN must have an assigned luid (i.e., it must not have
2935 been previously created by loop.c). */
2937 static int
2939 rtx insn;
2941 {
2943 {
2947 }
2950 }
2952 /* Record that a memory reference X is being set. */
2954 static void
2956 rtx x;
2957 rtx y ATTRIBUTE_UNUSED;
2959 {
2965 /* Count number of memory writes.
2966 This affects heuristics in strength_reduce. */
2969 /* BLKmode MEM means all memory is clobbered. */
2971 {
2974 else
2978 }
2982 }
2984 /* X is a value modified by an INSN that references a biv inside a loop
2985 exit test (ie, X is somehow related to the value of the biv). If X
2986 is a pseudo that is used more than once, then the biv is (effectively)
2987 used more than once. DATA is a pointer to a loop_regs structure. */
2989 static void
2991 rtx x;
2992 rtx y ATTRIBUTE_UNUSED;
2994 {
3009 /* If we do not have usage information, or if we know the register
3010 is used more than once, note that fact for check_dbra_loop. */
3015 }
3016 \f
3017 /* Return nonzero if the rtx X is invariant over the current loop.
3019 The value is 2 if we refer to something only conditionally invariant.
3021 A memory ref is invariant if it is not volatile and does not conflict
3022 with anything stored in `loop_info->store_mems'. */
3024 int
3028 {
3035 rtx mem_list_entry;
3041 {
3049 /* A LABEL_REF is normally invariant, however, if we are unrolling
3050 loops, and this label is inside the loop, then it isn't invariant.
3051 This is because each unrolled copy of the loop body will have
3052 a copy of this label. If this was invariant, then an insn loading
3053 the address of this label into a register might get moved outside
3054 the loop, and then each loop body would end up using the same label.
3056 We don't know the loop bounds here though, so just fail for all
3057 labels. */
3060 else
3069 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3070 since the reg might be set by initialization within the loop. */
3087 /* Volatile memory references must be rejected. Do this before
3088 checking for read-only items, so that volatile read-only items
3089 will be rejected also. */
3093 /* See if there is any dependence between a store and this load. */
3096 {
3102 }
3104 /* It's not invalidated by a store in memory
3105 but we must still verify the address is invariant. */
3109 /* Don't mess with insns declared volatile. */
3116 }
3120 {
3122 {
3128 }
3130 {
3133 {
3139 }
3141 }
3142 }
3145 }
3146 \f
3147 /* Return nonzero if all the insns in the loop that set REG
3148 are INSN and the immediately following insns,
3149 and if each of those insns sets REG in an invariant way
3150 (not counting uses of REG in them).
3152 The value is 2 if some of these insns are only conditionally invariant.
3154 We assume that INSN itself is the first set of REG
3155 and that its source is invariant. */
3157 static int
3162 {
3166 rtx temp;
3167 /* Number of sets we have to insist on finding after INSN. */
3173 /* If N_SETS hit the limit, we can't rely on its value. */
3180 {
3182 rtx set;
3187 /* If library call, skip to end of it. */
3196 {
3201 {
3202 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3203 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3204 notes are OK. */
3210 }
3211 }
3213 count--;
3215 {
3218 }
3219 }
3222 /* If loop_invariant_p ever returned 2, we return 2. */
3224 }
3226 #if 0
3227 /* I don't think this condition is sufficient to allow INSN
3228 to be moved, so we no longer test it. */
3230 /* Return 1 if all insns in the basic block of INSN and following INSN
3231 that set REG are invariant according to TABLE. */
3233 static int
3237 {
3242 {
3251 {
3254 }
3255 }
3256 }
3258 \f
3259 /* Look at all uses (not sets) of registers in X. For each, if it is
3260 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3261 a different insn, set USAGE[REGNO] to const0_rtx. */
3263 static void
3266 rtx insn;
3267 rtx x;
3268 {
3280 {
3281 /* Don't count SET_DEST if it is a REG; otherwise count things
3282 in SET_DEST because if a register is partially modified, it won't
3283 show up as a potential movable so we don't care how USAGE is set
3284 for it. */
3288 }
3289 else
3291 {
3297 }
3298 }
3299 \f
3300 /* Count and record any set in X which is contained in INSN. Update
3301 REGS->array[I].MAY_NOT_OPTIMIZE and LAST_SET for any register I set
3302 in X. */
3304 static void
3309 {
3311 /* Don't move a reg that has an explicit clobber.
3312 It's not worth the pain to try to do it correctly. */
3316 {
3324 {
3326 /* If this is the first setting of this reg
3327 in current basic block, and it was set before,
3328 it must be set in two basic blocks, so it cannot
3329 be moved out of the loop. */
3333 /* If this is not first setting in current basic block,
3334 see if reg was used in between previous one and this.
3335 If so, neither one can be moved. */
3342 }
3343 }
3344 }
3345 \f
3346 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3347 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3348 contained in insn INSN is used by any insn that precedes INSN in
3349 cyclic order starting from the loop entry point.
3351 We don't want to use INSN_LUID here because if we restrict INSN to those
3352 that have a valid INSN_LUID, it means we cannot move an invariant out
3353 from an inner loop past two loops. */
3355 static int
3359 {
3361 rtx p;
3363 /* Scan forward checking for register usage. If we hit INSN, we
3364 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3366 {
3372 }
3375 }
3376 \f
3377 /* A "basic induction variable" or biv is a pseudo reg that is set
3378 (within this loop) only by incrementing or decrementing it. */
3379 /* A "general induction variable" or giv is a pseudo reg whose
3380 value is a linear function of a biv. */
3382 /* Bivs are recognized by `basic_induction_var';
3383 Givs by `general_induction_var'. */
3385 /* Communication with routines called via `note_stores'. */
3389 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3393 /* ??? Unfinished optimizations, and possible future optimizations,
3394 for the strength reduction code. */
3396 /* ??? The interaction of biv elimination, and recognition of 'constant'
3397 bivs, may cause problems. */
3399 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3400 performance problems.
3402 Perhaps don't eliminate things that can be combined with an addressing
3403 mode. Find all givs that have the same biv, mult_val, and add_val;
3404 then for each giv, check to see if its only use dies in a following
3405 memory address. If so, generate a new memory address and check to see
3406 if it is valid. If it is valid, then store the modified memory address,
3407 otherwise, mark the giv as not done so that it will get its own iv. */
3409 /* ??? Could try to optimize branches when it is known that a biv is always
3410 positive. */
3412 /* ??? When replace a biv in a compare insn, we should replace with closest
3413 giv so that an optimized branch can still be recognized by the combiner,
3414 e.g. the VAX acb insn. */
3416 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3417 was rerun in loop_optimize whenever a register was added or moved.
3418 Also, some of the optimizations could be a little less conservative. */
3419 \f
3420 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3421 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3422 callback.
3424 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3425 loop iteration except for the last one.
3427 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3428 loop iteration.
3429 */
3430 void
3433 loop_insn_callback fncall;
3434 {
3435 /* This is 1 if current insn is not executed at least once for every loop
3436 iteration. */
3441 rtx p;
3443 /* If loop_scan_start points to the loop exit test, we have to be wary of
3444 subversive use of gotos inside expression statements. */
3448 /* Scan through loop to find all possible bivs. */
3453 {
3456 /* Past CODE_LABEL, we get to insns that may be executed multiple
3457 times. The only way we can be sure that they can't is if every
3458 jump insn between here and the end of the loop either
3459 returns, exits the loop, is a jump to a location that is still
3460 behind the label, or is a jump to the loop start. */
3463 {
3469 {
3474 {
3477 else
3481 }
3489 {
3492 }
3493 }
3494 }
3496 /* Past a jump, we get to insns for which we can't count
3497 on whether they will be executed during each iteration. */
3498 /* This code appears twice in strength_reduce. There is also similar
3499 code in scan_loop. */
3501 /* If we enter the loop in the middle, and scan around to the
3502 beginning, don't set not_every_iteration for that.
3503 This can be any kind of jump, since we want to know if insns
3504 will be executed if the loop is executed. */
3509 {
3512 /* If this is a jump outside the loop, then it also doesn't
3513 matter. Check to see if the target of this branch is on the
3514 loop->exits_labels list. */
3522 }
3525 {
3526 /* At the virtual top of a converted loop, insns are again known to
3527 be executed each iteration: logically, the loop begins here
3528 even though the exit code has been duplicated.
3530 Insns are also again known to be executed each iteration at
3531 the LOOP_CONT note. */
3537 loop_depth++;
3539 loop_depth--;
3540 }
3542 /* Note if we pass a loop latch. If we do, then we can not clear
3543 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3544 a loop since a jump before the last CODE_LABEL may have started
3545 a new loop iteration.
3547 Note that LOOP_TOP is only set for rotated loops and we need
3548 this check for all loops, so compare against the CODE_LABEL
3549 which immediately follows LOOP_START. */
3554 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3555 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3556 or not an insn is known to be executed each iteration of the
3557 loop, whether or not any iterations are known to occur.
3559 Therefore, if we have just passed a label and have no more labels
3560 between here and the test insn of the loop, and we have not passed
3561 a jump to the top of the loop, then we know these insns will be
3562 executed each iteration. */
3565 && !past_loop_latch
3570 }
3571 }
3572 \f
3573 static void
3576 {
3579 /* Temporary list pointers for traversing ivs->list. */
3586 /* Scan ivs->list to remove all regs that proved not to be bivs.
3587 Make a sanity check against regs->n_times_set. */
3589 {
3591 /* Above happens if register modified by subreg, etc. */
3592 /* Make sure it is not recognized as a basic induction var: */
3594 /* If never incremented, it is invariant that we decided not to
3595 move. So leave it alone. */
3597 {
3608 }
3609 else
3610 {
3615 }
3616 }
3617 }
3620 /* Determine how BIVS are initialised by looking through pre-header
3621 extended basic block. */
3622 static void
3625 {
3627 /* Temporary list pointers for traversing ivs->list. */
3630 rtx p;
3632 /* Find initial value for each biv by searching backwards from loop_start,
3633 halting at first label. Also record any test condition. */
3637 {
3638 rtx test;
3648 /* Record any test of a biv that branches around the loop if no store
3649 between it and the start of loop. We only care about tests with
3650 constants and registers and only certain of those. */
3660 {
3661 /* If an NE test, we have an initial value! */
3663 {
3667 }
3668 else
3670 }
3671 }
3672 }
3675 /* Look at the each biv and see if we can say anything better about its
3676 initial value from any initializing insns set up above. (This is done
3677 in two passes to avoid missing SETs in a PARALLEL.) */
3678 static void
3681 {
3683 /* Temporary list pointers for traversing ivs->list. */
3688 {
3689 rtx src;
3690 rtx note;
3695 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3696 is a constant, use the value of that. */
3702 else
3715 {
3719 {
3722 }
3723 }
3724 /* If we can't make it a giv,
3725 let biv keep initial value of "itself". */
3728 }
3729 }
3732 /* Search the loop for general induction variables. */
3734 static void
3737 {
3739 }
3742 /* For each giv for which we still don't know whether or not it is
3743 replaceable, check to see if it is replaceable because its final value
3744 can be calculated. */
3746 static void
3749 {
3754 {
3760 }
3761 }
3764 /* Return non-zero if it is possible to eliminate the biv BL provided
3765 all givs are reduced. This is possible if either the reg is not
3766 used outside the loop, or we can compute what its final value will
3767 be. */
3769 static int
3775 {
3776 /* For architectures with a decrement_and_branch_until_zero insn,
3777 don't do this if we put a REG_NONNEG note on the endtest for this
3778 biv. */
3780 #ifdef HAVE_decrement_and_branch_until_zero
3782 {
3787 }
3788 #endif
3790 /* Check that biv is used outside loop or if it has a final value.
3791 Compare against bl->init_insn rather than loop->start. We aren't
3792 concerned with any uses of the biv between init_insn and
3793 loop->start since these won't be affected by the value of the biv
3794 elsewhere in the function, so long as init_insn doesn't use the
3795 biv itself. */
3806 {
3814 }
3816 }
3819 /* Reduce each giv of BL that we have decided to reduce. */
3821 static void
3825 {
3829 {
3832 {
3835 /* If the code for derived givs immediately below has already
3836 allocated a new_reg, we must keep it. */
3840 #ifdef AUTO_INC_DEC
3841 /* If the target has auto-increment addressing modes, and
3842 this is an address giv, then try to put the increment
3843 immediately after its use, so that flow can create an
3844 auto-increment addressing mode. */
3847 /* We don't handle reversed biv's because bl->biv->insn
3848 does not have a valid INSN_LUID. */
3852 {
3853 /* If other giv's have been combined with this one, then
3854 this will work only if all uses of the other giv's occur
3855 before this giv's insn. This is difficult to check.
3857 We simplify this by looking for the common case where
3858 there is one DEST_REG giv, and this giv's insn is the
3859 last use of the dest_reg of that DEST_REG giv. If the
3860 increment occurs after the address giv, then we can
3861 perform the optimization. (Otherwise, the increment
3862 would have to go before other_giv, and we would not be
3863 able to combine it with the address giv to get an
3864 auto-inc address.) */
3866 {
3871 {
3874 else
3876 }
3883 }
3884 /* Check for case where increment is before the address
3885 giv. Do this test in "loop order". */
3894 else
3897 #ifdef HAVE_cc0
3898 {
3899 rtx prev;
3901 /* We can't put an insn immediately after one setting
3902 cc0, or immediately before one using cc0. */
3909 }
3910 #endif
3914 }
3915 #endif
3917 /* For each place where the biv is incremented, add an insn
3918 to increment the new, reduced reg for the giv. */
3920 {
3921 rtx insert_before;
3927 else
3935 /* A multiply is acceptable here
3936 since this is presumed to be seldom executed. */
3940 }
3942 /* Add code at loop start to initialize giv's reduced reg. */
3947 }
3948 }
3949 }
3952 /* Check for givs whose first use is their definition and whose
3953 last use is the definition of another giv. If so, it is likely
3954 dead and should not be used to derive another giv nor to
3955 eliminate a biv. */
3957 static void
3961 {
3965 {
3972 {
3978 }
3979 }
3980 }
3983 static void
3988 {
3992 {
3999 /* Update expression if this was combined, in case other giv was
4000 replaced. */
4005 /* See if this register is known to be a pointer to something. If
4006 so, see if we can find the alignment. First see if there is a
4007 destination register that is a pointer. If so, this shares the
4008 alignment too. Next see if we can deduce anything from the
4009 computational information. If not, and this is a DEST_ADDR
4010 giv, at least we know that it's a pointer, though we don't know
4011 the alignment. */
4019 {
4028 }
4032 {
4040 }
4045 /* Store reduced reg as the address in the memref where we found
4046 this giv. */
4049 {
4051 }
4052 else
4053 {
4054 /* Not replaceable; emit an insn to set the original giv reg from
4055 the reduced giv, same as above. */
4058 }
4060 /* When a loop is reversed, givs which depend on the reversed
4061 biv, and which are live outside the loop, must be set to their
4062 correct final value. This insn is only needed if the giv is
4063 not replaceable. The correct final value is the same as the
4064 value that the giv starts the reversed loop with. */
4074 {
4079 }
4080 }
4081 }
4084 static int
4089 rtx test_reg;
4090 {
4099 /* Reduce benefit if not replaceable, since we will insert a
4100 move-insn to replace the insn that calculates this giv. Don't do
4101 this unless the giv is a user variable, since it will often be
4102 marked non-replaceable because of the duplication of the exit
4103 code outside the loop. In such a case, the copies we insert are
4104 dead and will be deleted. So they don't have a cost. Similar
4105 situations exist. */
4106 /* ??? The new final_[bg]iv_value code does a much better job of
4107 finding replaceable giv's, and hence this code may no longer be
4108 necessary. */
4113 /* Decrease the benefit to count the add-insns that we will insert
4114 to increment the reduced reg for the giv. ??? This can
4115 overestimate the run-time cost of the additional insns, e.g. if
4116 there are multiple basic blocks that increment the biv, but only
4117 one of these blocks is executed during each iteration. There is
4118 no good way to detect cases like this with the current structure
4119 of the loop optimizer. This code is more accurate for
4120 determining code size than run-time benefits. */
4123 /* Decide whether to strength-reduce this giv or to leave the code
4124 unchanged (recompute it from the biv each time it is used). This
4125 decision can be made independently for each giv. */
4127 #ifdef AUTO_INC_DEC
4128 /* Attempt to guess whether autoincrement will handle some of the
4129 new add insns; if so, increase BENEFIT (undo the subtraction of
4130 add_cost that was done above). */
4132 /* Increasing the benefit is risky, since this is only a guess.
4133 Avoid increasing register pressure in cases where there would
4134 be no other benefit from reducing this giv. */
4137 {
4152 }
4153 #endif
4156 }
4159 /* Free IV structures for LOOP. */
4161 static void
4164 {
4171 {
4177 {
4180 }
4182 {
4185 }
4189 }
4190 }
4193 /* Perform strength reduction and induction variable elimination.
4195 Pseudo registers created during this function will be beyond the
4196 last valid index in several tables including
4197 REGS->ARRAY[I].N_TIMES_SET and REGNO_LAST_UID. This does not cause a
4198 problem here, because the added registers cannot be givs outside of
4199 their loop, and hence will never be reconsidered. But scan_loop
4200 must check regnos to make sure they are in bounds. */
4202 static void
4207 {
4211 rtx p;
4212 /* Temporary list pointer for traversing ivs->list. */
4214 /* Ratio of extra register life span we can justify
4215 for saving an instruction. More if loop doesn't call subroutines
4216 since in that case saving an insn makes more difference
4217 and more registers are available. */
4218 /* ??? could set this to last value of threshold in move_movables */
4220 /* Map of pseudo-register replacements. */
4231 /* Find all BIVs in loop. */
4234 /* Exit if there are no bivs. */
4236 {
4237 /* Can still unroll the loop anyways, but indicate that there is no
4238 strength reduction info available. */
4244 }
4246 /* Determine how BIVS are initialised by looking through pre-header
4247 extended basic block. */
4250 /* Look at the each biv and see if we can say anything better about its
4251 initial value from any initializing insns set up above. */
4254 /* Search the loop for general induction variables. */
4257 /* Try to calculate and save the number of loop iterations. This is
4258 set to zero if the actual number can not be calculated. This must
4259 be called after all giv's have been identified, since otherwise it may
4260 fail if the iteration variable is a giv. */
4263 /* Now for each giv for which we still don't know whether or not it is
4264 replaceable, check to see if it is replaceable because its final value
4265 can be calculated. This must be done after loop_iterations is called,
4266 so that final_giv_value will work correctly. */
4269 /* Try to prove that the loop counter variable (if any) is always
4270 nonnegative; if so, record that fact with a REG_NONNEG note
4271 so that "decrement and branch until zero" insn can be used. */
4274 /* Create reg_map to hold substitutions for replaceable giv regs.
4275 Some givs might have been made from biv increments, so look at
4276 ivs->reg_iv_type for a suitable size. */
4280 /* Examine each iv class for feasibility of strength reduction/induction
4281 variable elimination. */
4284 {
4288 /* Test whether it will be possible to eliminate this biv
4289 provided all givs are reduced. */
4292 /* Check each extension dependent giv in this class to see if its
4293 root biv is safe from wrapping in the interior mode. */
4296 /* Combine all giv's for this iv_class. */
4299 /* This will be true at the end, if all givs which depend on this
4300 biv have been strength reduced.
4301 We can't (currently) eliminate the biv unless this is so. */
4305 {
4313 /* If an insn is not to be strength reduced, then set its ignore
4314 flag, and clear bl->all_reduced. */
4316 /* A giv that depends on a reversed biv must be reduced if it is
4317 used after the loop exit, otherwise, it would have the wrong
4318 value after the loop exit. To make it simple, just reduce all
4319 of such giv's whether or not we know they are used after the loop
4320 exit. */
4325 {
4333 }
4334 else
4335 {
4336 /* Check that we can increment the reduced giv without a
4337 multiply insn. If not, reject it. */
4342 {
4350 }
4351 }
4352 }
4354 /* Check for givs whose first use is their definition and whose
4355 last use is the definition of another giv. If so, it is likely
4356 dead and should not be used to derive another giv nor to
4357 eliminate a biv. */
4360 /* Reduce each giv that we decided to reduce. */
4363 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4364 as not reduced.
4366 For each giv register that can be reduced now: if replaceable,
4367 substitute reduced reg wherever the old giv occurs;
4368 else add new move insn "giv_reg = reduced_reg". */
4371 /* All the givs based on the biv bl have been reduced if they
4372 merit it. */
4374 /* For each giv not marked as maybe dead that has been combined with a
4375 second giv, clear any "maybe dead" mark on that second giv.
4376 v->new_reg will either be or refer to the register of the giv it
4377 combined with.
4379 Doing this clearing avoids problems in biv elimination where
4380 a giv's new_reg is a complex value that can't be put in the
4381 insn but the giv combined with (with a reg as new_reg) is
4382 marked maybe_dead. Since the register will be used in either
4383 case, we'd prefer it be used from the simpler giv. */
4389 /* Try to eliminate the biv, if it is a candidate.
4390 This won't work if ! bl->all_reduced,
4391 since the givs we planned to use might not have been reduced.
4393 We have to be careful that we didn't initially think we could
4394 eliminate this biv because of a giv that we now think may be
4395 dead and shouldn't be used as a biv replacement.
4397 Also, there is the possibility that we may have a giv that looks
4398 like it can be used to eliminate a biv, but the resulting insn
4399 isn't valid. This can happen, for example, on the 88k, where a
4400 JUMP_INSN can compare a register only with zero. Attempts to
4401 replace it with a compare with a constant will fail.
4403 Note that in cases where this call fails, we may have replaced some
4404 of the occurrences of the biv with a giv, but no harm was done in
4405 doing so in the rare cases where it can occur. */
4409 {
4410 /* ?? If we created a new test to bypass the loop entirely,
4411 or otherwise drop straight in, based on this test, then
4412 we might want to rewrite it also. This way some later
4413 pass has more hope of removing the initialization of this
4414 biv entirely. */
4416 /* If final_value != 0, then the biv may be used after loop end
4417 and we must emit an insn to set it just in case.
4419 Reversed bivs already have an insn after the loop setting their
4420 value, so we don't need another one. We can't calculate the
4421 proper final value for such a biv here anyways. */
4429 }
4430 }
4432 /* Go through all the instructions in the loop, making all the
4433 register substitutions scheduled in REG_MAP. */
4438 {
4442 }
4445 {
4446 /* When we completely unroll a loop we will likely not need the increment
4447 of the loop BIV and we will not need the conditional branch at the
4448 end of the loop. */
4451 #ifdef HAVE_cc0
4452 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4453 need the comparison before the conditional branch at the end of the
4454 loop. */
4456 #endif
4458 /* We'll need one copy for each loop iteration. */
4461 /* A little slop to account for the ability to remove initialization
4462 code, better CSE, and other secondary benefits of completely
4463 unrolling some loops. */
4466 /* Clamp the value. */
4469 }
4471 /* Unroll loops from within strength reduction so that we can use the
4472 induction variable information that strength_reduce has already
4473 collected. Always unroll loops that would be as small or smaller
4474 unrolled than when rolled. */
4480 #ifdef HAVE_doloop_end
4491 }
4492 \f
4493 /*Record all basic induction variables calculated in the insn. */
4494 static rtx
4497 rtx p;
4500 {
4502 rtx set;
4503 rtx dest_reg;
4504 rtx inc_val;
4505 rtx mult_val;
4511 {
4516 {
4521 {
4522 /* It is a possible basic induction variable.
4523 Create and initialize an induction structure for it. */
4531 }
4534 }
4535 }
4537 }
4538 \f
4539 /* Record all givs calculated in the insn.
4540 A register is a giv if: it is only set once, it is a function of a
4541 biv and a constant (or invariant), and it is not a biv. */
4542 static rtx
4545 rtx p;
4548 {
4551 rtx set;
4552 /* Look for a general induction variable in a register. */
4557 {
4558 rtx src_reg;
4559 rtx dest_reg;
4560 rtx add_val;
4561 rtx mult_val;
4562 rtx ext_val;
4565 rtx last_consec_insn;
4574 /* Equivalent expression is a giv. */
4579 /* Don't try to handle any regs made by loop optimization.
4580 We have nothing on them in regno_first_uid, etc. */
4582 /* Don't recognize a BASIC_INDUCT_VAR here. */
4584 /* This must be the only place where the register is set. */
4586 /* or all sets must be consecutive and make a giv. */
4591 {
4595 /* If this is a library call, increase benefit. */
4599 /* Skip the consecutive insns, if there are any. */
4607 }
4608 }
4610 #ifndef DONT_REDUCE_ADDR
4611 /* Look for givs which are memory addresses. */
4612 /* This resulted in worse code on a VAX 8600. I wonder if it
4613 still does. */
4616 maybe_multiple);
4617 #endif
4619 /* Update the status of whether giv can derive other givs. This can
4620 change when we pass a label or an insn that updates a biv. */
4625 }
4626 \f
4627 /* Return 1 if X is a valid source for an initial value (or as value being
4628 compared against in an initial test).
4630 X must be either a register or constant and must not be clobbered between
4631 the current insn and the start of the loop.
4633 INSN is the insn containing X. */
4635 static int
4637 rtx x;
4638 rtx insn;
4640 rtx loop_start;
4641 {
4645 /* Only consider pseudos we know about initialized in insns whose luids
4646 we know. */
4651 /* Don't use call-clobbered registers across a call which clobbers it. On
4652 some machines, don't use any hard registers at all. */
4654 && (SMALL_REGISTER_CLASSES
4658 /* Don't use registers that have been clobbered before the start of the
4659 loop. */
4664 }
4665 \f
4666 /* Scan X for memory refs and check each memory address
4667 as a possible giv. INSN is the insn whose pattern X comes from.
4668 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4669 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4670 more thanonce in each loop iteration. */
4672 static void
4675 rtx x;
4676 rtx insn;
4678 {
4688 {
4704 {
4705 rtx src_reg;
4706 rtx add_val;
4707 rtx mult_val;
4708 rtx ext_val;
4711 /* This code used to disable creating GIVs with mult_val == 1 and
4712 add_val == 0. However, this leads to lost optimizations when
4713 it comes time to combine a set of related DEST_ADDR GIVs, since
4714 this one would not be seen. */
4719 {
4720 /* Found one; record it. */
4729 }
4730 }
4735 }
4737 /* Recursively scan the subexpressions for other mem refs. */
4743 maybe_multiple);
4747 maybe_multiple);
4748 }
4749 \f
4750 /* Fill in the data about one biv update.
4751 V is the `struct induction' in which we record the biv. (It is
4752 allocated by the caller, with alloca.)
4753 INSN is the insn that sets it.
4754 DEST_REG is the biv's reg.
4756 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4757 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4758 being set to INC_VAL.
4760 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4761 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4762 can be executed more than once per iteration. If MAYBE_MULTIPLE
4763 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4764 executed exactly once per iteration. */
4766 static void
4771 rtx insn;
4772 rtx dest_reg;
4773 rtx inc_val;
4774 rtx mult_val;
4778 {
4794 /* Add this to the reg's iv_class, creating a class
4795 if this is the first incrementation of the reg. */
4799 {
4800 /* Create and initialize new iv_class. */
4810 /* Set initial value to the reg itself. */
4813 /* We haven't seen the initializing insn yet */
4823 /* Add this class to ivs->list. */
4827 /* Put it in the array of biv register classes. */
4829 }
4831 /* Update IV_CLASS entry for this biv. */
4840 }
4841 \f
4842 /* Fill in the data about one giv.
4843 V is the `struct induction' in which we record the giv. (It is
4844 allocated by the caller, with alloca.)
4845 INSN is the insn that sets it.
4846 BENEFIT estimates the savings from deleting this insn.
4847 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4848 into a register or is used as a memory address.
4850 SRC_REG is the biv reg which the giv is computed from.
4851 DEST_REG is the giv's reg (if the giv is stored in a reg).
4852 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4853 LOCATION points to the place where this giv's value appears in INSN. */
4855 static void
4860 rtx insn;
4861 rtx src_reg;
4862 rtx dest_reg;
4868 {
4873 rtx temp;
4875 /* Attempt to prove constantness of the values. */
4903 /* The v->always_computable field is used in update_giv_derive, to
4904 determine whether a giv can be used to derive another giv. For a
4905 DEST_REG giv, INSN computes a new value for the giv, so its value
4906 isn't computable if INSN insn't executed every iteration.
4907 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4908 it does not compute a new value. Hence the value is always computable
4909 regardless of whether INSN is executed each iteration. */
4913 else
4919 {
4922 }
4924 {
4929 /* If the lifetime is zero, it means that this register is
4930 really a dead store. So mark this as a giv that can be
4931 ignored. This will not prevent the biv from being eliminated. */
4937 }
4939 /* Add the giv to the class of givs computed from one biv. */
4943 {
4946 /* Don't count DEST_ADDR. This is supposed to count the number of
4947 insns that calculate givs. */
4951 }
4952 else
4953 /* Fatal error, biv missing for this giv? */
4958 else
4959 {
4960 /* The giv can be replaced outright by the reduced register only if all
4961 of the following conditions are true:
4962 - the insn that sets the giv is always executed on any iteration
4963 on which the giv is used at all
4964 (there are two ways to deduce this:
4965 either the insn is executed on every iteration,
4966 or all uses follow that insn in the same basic block),
4967 - the giv is not used outside the loop
4968 - no assignments to the biv occur during the giv's lifetime. */
4971 /* Previous line always fails if INSN was moved by loop opt. */
4974 && (! not_every_iteration
4976 {
4977 /* Now check that there are no assignments to the biv within the
4978 giv's lifetime. This requires two separate checks. */
4980 /* Check each biv update, and fail if any are between the first
4981 and last use of the giv.
4983 If this loop contains an inner loop that was unrolled, then
4984 the insn modifying the biv may have been emitted by the loop
4985 unrolling code, and hence does not have a valid luid. Just
4986 mark the biv as not replaceable in this case. It is not very
4987 useful as a biv, because it is used in two different loops.
4988 It is very unlikely that we would be able to optimize the giv
4989 using this biv anyways. */
4993 {
4999 {
5003 }
5004 }
5006 /* If there are any backwards branches that go from after the
5007 biv update to before it, then this giv is not replaceable. */
5011 {
5015 }
5016 }
5017 else
5018 {
5019 /* May still be replaceable, we don't have enough info here to
5020 decide. */
5023 }
5024 }
5026 /* Record whether the add_val contains a const_int, for later use by
5027 combine_givs. */
5028 {
5033 ;
5037 {
5039 {
5044 else
5046 }
5049 }
5050 }
5054 }
5056 /* All this does is determine whether a giv can be made replaceable because
5057 its final value can be calculated. This code can not be part of record_giv
5058 above, because final_giv_value requires that the number of loop iterations
5059 be known, and that can not be accurately calculated until after all givs
5060 have been identified. */
5062 static void
5066 {
5073 /* DEST_ADDR givs will never reach here, because they are always marked
5074 replaceable above in record_giv. */
5076 /* The giv can be replaced outright by the reduced register only if all
5077 of the following conditions are true:
5078 - the insn that sets the giv is always executed on any iteration
5079 on which the giv is used at all
5080 (there are two ways to deduce this:
5081 either the insn is executed on every iteration,
5082 or all uses follow that insn in the same basic block),
5083 - its final value can be calculated (this condition is different
5084 than the one above in record_giv)
5085 - it's not used before the it's set
5086 - no assignments to the biv occur during the giv's lifetime. */
5088 #if 0
5089 /* This is only called now when replaceable is known to be false. */
5090 /* Clear replaceable, so that it won't confuse final_giv_value. */
5092 #endif
5096 {
5099 rtx last_giv_use;
5103 /* When trying to determine whether or not a biv increment occurs
5104 during the lifetime of the giv, we can ignore uses of the variable
5105 outside the loop because final_value is true. Hence we can not
5106 use regno_last_uid and regno_first_uid as above in record_giv. */
5108 /* Search the loop to determine whether any assignments to the
5109 biv occur during the giv's lifetime. Start with the insn
5110 that sets the giv, and search around the loop until we come
5111 back to that insn again.
5113 Also fail if there is a jump within the giv's lifetime that jumps
5114 to somewhere outside the lifetime but still within the loop. This
5115 catches spaghetti code where the execution order is not linear, and
5116 hence the above test fails. Here we assume that the giv lifetime
5117 does not extend from one iteration of the loop to the next, so as
5118 to make the test easier. Since the lifetime isn't known yet,
5119 this requires two loops. See also record_giv above. */
5124 {
5127 {
5130 }
5136 {
5137 /* It is possible for the BIV increment to use the GIV if we
5138 have a cycle. Thus we must be sure to check each insn for
5139 both BIV and GIV uses, and we must check for BIV uses
5140 first. */
5147 {
5149 {
5153 }
5155 }
5156 }
5157 }
5159 /* Now that the lifetime of the giv is known, check for branches
5160 from within the lifetime to outside the lifetime if it is still
5161 replaceable. */
5164 {
5167 {
5180 {
5189 }
5190 }
5191 }
5193 /* If it is replaceable, then save the final value. */
5196 }
5201 }
5202 \f
5203 /* Update the status of whether a giv can derive other givs.
5205 We need to do something special if there is or may be an update to the biv
5206 between the time the giv is defined and the time it is used to derive
5207 another giv.
5209 In addition, a giv that is only conditionally set is not allowed to
5210 derive another giv once a label has been passed.
5212 The cases we look at are when a label or an update to a biv is passed. */
5214 static void
5217 rtx p;
5218 {
5222 rtx tem;
5225 /* Search all IV classes, then all bivs, and finally all givs.
5227 There are three cases we are concerned with. First we have the situation
5228 of a giv that is only updated conditionally. In that case, it may not
5229 derive any givs after a label is passed.
5231 The second case is when a biv update occurs, or may occur, after the
5232 definition of a giv. For certain biv updates (see below) that are
5233 known to occur between the giv definition and use, we can adjust the
5234 giv definition. For others, or when the biv update is conditional,
5235 we must prevent the giv from deriving any other givs. There are two
5236 sub-cases within this case.
5238 If this is a label, we are concerned with any biv update that is done
5239 conditionally, since it may be done after the giv is defined followed by
5240 a branch here (actually, we need to pass both a jump and a label, but
5241 this extra tracking doesn't seem worth it).
5243 If this is a jump, we are concerned about any biv update that may be
5244 executed multiple times. We are actually only concerned about
5245 backward jumps, but it is probably not worth performing the test
5246 on the jump again here.
5248 If this is a biv update, we must adjust the giv status to show that a
5249 subsequent biv update was performed. If this adjustment cannot be done,
5250 the giv cannot derive further givs. */
5256 {
5258 {
5259 /* If cant_derive is already true, there is no point in
5260 checking all of these conditions again. */
5264 /* If this giv is conditionally set and we have passed a label,
5265 it cannot derive anything. */
5269 /* Skip givs that have mult_val == 0, since
5270 they are really invariants. Also skip those that are
5271 replaceable, since we know their lifetime doesn't contain
5272 any biv update. */
5276 /* The only way we can allow this giv to derive another
5277 is if this is a biv increment and we can form the product
5278 of biv->add_val and giv->mult_val. In this case, we will
5279 be able to compute a compensation. */
5281 {
5282 rtx ext_val_dummy;
5293 tem = simplify_giv_expr
5300 else
5302 }
5306 }
5307 }
5308 }
5309 \f
5310 /* Check whether an insn is an increment legitimate for a basic induction var.
5311 X is the source of insn P, or a part of it.
5312 MODE is the mode in which X should be interpreted.
5314 DEST_REG is the putative biv, also the destination of the insn.
5315 We accept patterns of these forms:
5316 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5317 REG = INVARIANT + REG
5319 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5320 store the additive term into *INC_VAL, and store the place where
5321 we found the additive term into *LOCATION.
5323 If X is an assignment of an invariant into DEST_REG, we set
5324 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5326 We also want to detect a BIV when it corresponds to a variable
5327 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5328 of the variable may be a PLUS that adds a SUBREG of that variable to
5329 an invariant and then sign- or zero-extends the result of the PLUS
5330 into the variable.
5332 Most GIVs in such cases will be in the promoted mode, since that is the
5333 probably the natural computation mode (and almost certainly the mode
5334 used for addresses) on the machine. So we view the pseudo-reg containing
5335 the variable as the BIV, as if it were simply incremented.
5337 Note that treating the entire pseudo as a BIV will result in making
5338 simple increments to any GIVs based on it. However, if the variable
5339 overflows in its declared mode but not its promoted mode, the result will
5340 be incorrect. This is acceptable if the variable is signed, since
5341 overflows in such cases are undefined, but not if it is unsigned, since
5342 those overflows are defined. So we only check for SIGN_EXTEND and
5343 not ZERO_EXTEND.
5345 If we cannot find a biv, we return 0. */
5347 static int
5352 rtx dest_reg;
5353 rtx p;
5357 {
5365 {
5371 {
5373 }
5378 {
5380 }
5381 else
5394 /* If this is a SUBREG for a promoted variable, check the inner
5395 value. */
5403 /* If this register is assigned in a previous insn, look at its
5404 source, but don't go outside the loop or past a label. */
5406 /* If this sets a register to itself, we would repeat any previous
5407 biv increment if we applied this strategy blindly. */
5413 {
5414 rtx dest;
5415 do
5416 {
5418 }
5447 }
5448 /* Fall through. */
5450 /* Can accept constant setting of biv only when inside inner most loop.
5451 Otherwise, a biv of an inner loop may be incorrectly recognized
5452 as a biv of the outer loop,
5453 causing code to be moved INTO the inner loop. */
5460 /* convert_modes aborts if we try to convert to or from CCmode, so just
5461 exclude that case. It is very unlikely that a condition code value
5462 would be a useful iterator anyways. */
5466 {
5467 /* Possible bug here? Perhaps we don't know the mode of X. */
5471 }
5472 else
5480 /* Similar, since this can be a sign extension. */
5485 ;
5499 location);
5504 }
5505 }
5506 \f
5507 /* A general induction variable (giv) is any quantity that is a linear
5508 function of a basic induction variable,
5509 i.e. giv = biv * mult_val + add_val.
5510 The coefficients can be any loop invariant quantity.
5511 A giv need not be computed directly from the biv;
5512 it can be computed by way of other givs. */
5514 /* Determine whether X computes a giv.
5515 If it does, return a nonzero value
5516 which is the benefit from eliminating the computation of X;
5517 set *SRC_REG to the register of the biv that it is computed from;
5518 set *ADD_VAL and *MULT_VAL to the coefficients,
5519 such that the value of X is biv * mult + add; */
5521 static int
5525 rtx x;
5533 {
5537 /* If this is an invariant, forget it, it isn't a giv. */
5548 {
5551 /* Since this is now an invariant and wasn't before, it must be a giv
5552 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5553 with. */
5560 /* This is equivalent to a BIV. */
5567 /* Either (plus (biv) (invar)) or
5568 (plus (mult (biv) (invar_1)) (invar_2)). */
5570 {
5573 }
5574 else
5575 {
5578 }
5583 /* ADD_VAL is zero. */
5591 }
5593 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5594 unless they are CONST_INT). */
5602 else
5605 /* Always return true if this is a giv so it will be detected as such,
5606 even if the benefit is zero or negative. This allows elimination
5607 of bivs that might otherwise not be eliminated. */
5609 }
5610 \f
5611 /* Given an expression, X, try to form it as a linear function of a biv.
5612 We will canonicalize it to be of the form
5613 (plus (mult (BIV) (invar_1))
5614 (invar_2))
5615 with possible degeneracies.
5617 The invariant expressions must each be of a form that can be used as a
5618 machine operand. We surround then with a USE rtx (a hack, but localized
5619 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5620 routine; it is the caller's responsibility to strip them.
5622 If no such canonicalization is possible (i.e., two biv's are used or an
5623 expression that is neither invariant nor a biv or giv), this routine
5624 returns 0.
5626 For a non-zero return, the result will have a code of CONST_INT, USE,
5627 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5629 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5634 static rtx
5637 rtx x;
5640 {
5645 rtx tem;
5647 /* If this is not an integer mode, or if we cannot do arithmetic in this
5648 mode, this can't be a giv. */
5655 {
5662 /* Put constant last, CONST_INT last if both constant. */
5670 /* Handle addition of zero, then addition of an invariant. */
5675 {
5678 /* Adding two invariants must result in an invariant, so enclose
5679 addition operation inside a USE and return it. */
5689 else
5698 /* biv + invar or mult + invar. Return sum. */
5702 /* (a + invar_1) + invar_2. Associate. */
5703 return
5709 arg1)),
5714 }
5716 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5717 MULT to reduce cases. */
5723 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5724 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5725 Recurse to associate the second PLUS. */
5730 return
5738 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5754 /* Handle "a - b" as "a + b * (-1)". */
5760 constm1_rtx)),
5769 /* Put constant last, CONST_INT last if both constant. */
5774 /* If second argument is not now constant, not giv. */
5778 /* Handle multiply by 0 or 1. */
5786 {
5788 /* biv * invar. Done. */
5792 /* Product of two constants. */
5796 /* invar * invar is a giv, but attempt to simplify it somehow. */
5802 {
5803 /* (invar_0 * invar_1) * invar_2. Associate. */
5810 arg1)),
5812 }
5813 /* Porpagate the MULT expressions to the intermost nodes. */
5815 {
5816 /* (invar_0 + invar_1) * invar_2. Distribute. */
5822 arg1),
5826 arg1)),
5828 }
5832 /* (a * invar_1) * invar_2. Associate. */
5838 arg1)),
5842 /* (a + invar_1) * invar_2. Distribute. */
5847 arg1),
5850 arg1)),
5855 }
5858 /* Shift by constant is multiply by power of two. */
5862 return
5871 /* "-a" is "a * (-1)" */
5877 /* "~a" is "-a - 1". Silly, but easy. */
5881 const1_rtx),
5885 /* Already in proper form for invariant. */
5891 /* Conditionally recognize extensions of simple IVs. After we've
5892 computed loop traversal counts and verified the range of the
5893 source IV, we'll reevaluate this as a GIV. */
5895 {
5898 {
5901 }
5902 }
5906 /* If this is a new register, we can't deal with it. */
5910 /* Check for biv or giv. */
5912 {
5916 {
5919 /* Form expression from giv and add benefit. Ensure this giv
5920 can derive another and subtract any needed adjustment if so. */
5922 /* Increasing the benefit here is risky. The only case in which it
5923 is arguably correct is if this is the only use of V. In other
5924 cases, this will artificially inflate the benefit of the current
5925 giv, and lead to suboptimal code. Thus, it is disabled, since
5926 potentially not reducing an only marginally beneficial giv is
5927 less harmful than reducing many givs that are not really
5928 beneficial. */
5929 {
5933 }
5946 {
5949 }
5950 else
5951 {
5954 }
5956 }
5959 do_default:
5960 /* If it isn't an induction variable, and it is invariant, we
5961 may be able to simplify things further by looking through
5962 the bits we just moved outside the loop. */
5964 {
5970 {
5971 /* Ok, we found a match. Substitute and simplify. */
5973 /* If we match another movable, we must use that, as
5974 this one is going away. */
5979 /* If consec is non-zero, this is a member of a group of
5980 instructions that were moved together. We handle this
5981 case only to the point of seeking to the last insn and
5982 looking for a REG_EQUAL. Fail if we don't find one. */
5984 {
5987 do
5988 {
5990 }
5996 }
5997 else
5998 {
6002 }
6005 {
6006 /* What we are most interested in is pointer
6007 arithmetic on invariants -- only take
6008 patterns we may be able to do something with. */
6014 {
6016 benefit);
6019 }
6024 {
6029 }
6030 }
6032 }
6033 }
6035 }
6037 /* Fall through to general case. */
6039 /* If invariant, return as USE (unless CONST_INT).
6040 Otherwise, not giv. */
6045 {
6054 }
6055 else
6057 }
6058 }
6060 /* This routine folds invariants such that there is only ever one
6061 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6063 static rtx
6066 {
6072 {
6075 }
6078 {
6081 }
6082 else
6083 {
6086 }
6087 }
6089 static rtx
6093 {
6095 {
6099 else
6102 }
6105 else
6108 }
6109 \f
6110 /* Help detect a giv that is calculated by several consecutive insns;
6111 for example,
6112 giv = biv * M
6113 giv = giv + A
6114 The caller has already identified the first insn P as having a giv as dest;
6115 we check that all other insns that set the same register follow
6116 immediately after P, that they alter nothing else,
6117 and that the result of the last is still a giv.
6119 The value is 0 if the reg set in P is not really a giv.
6120 Otherwise, the value is the amount gained by eliminating
6121 all the consecutive insns that compute the value.
6123 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6124 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6126 The coefficients of the ultimate giv value are stored in
6127 *MULT_VAL and *ADD_VAL. */
6129 static int
6134 rtx p;
6135 rtx src_reg;
6136 rtx dest_reg;
6141 {
6147 rtx temp;
6148 rtx set;
6150 /* Indicate that this is a giv so that we can update the value produced in
6151 each insn of the multi-insn sequence.
6153 This induction structure will be used only by the call to
6154 general_induction_var below, so we can allocate it on our stack.
6155 If this is a giv, our caller will replace the induct var entry with
6156 a new induction structure. */
6177 {
6181 /* If libcall, skip to end of call sequence. */
6192 /* Giv created by equivalent expression. */
6198 {
6202 count--;
6206 }
6208 {
6209 /* Allow insns that set something other than this giv to a
6210 constant. Such insns are needed on machines which cannot
6211 include long constants and should not disqualify a giv. */
6220 }
6221 }
6226 }
6227 \f
6228 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6229 represented by G1. If no such expression can be found, or it is clear that
6230 it cannot possibly be a valid address, 0 is returned.
6232 To perform the computation, we note that
6233 G1 = x * v + a and
6234 G2 = y * v + b
6235 where `v' is the biv.
6237 So G2 = (y/b) * G1 + (b - a*y/x).
6239 Note that MULT = y/x.
6241 Update: A and B are now allowed to be additive expressions such that
6242 B contains all variables in A. That is, computing B-A will not require
6243 subtracting variables. */
6245 static rtx
6248 {
6249 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6254 /* If MULT is not 1, we cannot handle A with non-constants, since we
6255 would then be required to subtract multiples of the registers in A.
6256 This is theoretically possible, and may even apply to some Fortran
6257 constructs, but it is a lot of work and we do not attempt it here. */
6262 /* In general these structures are sorted top to bottom (down the PLUS
6263 chain), but not left to right across the PLUS. If B is a higher
6264 order giv than A, we can strip one level and recurse. If A is higher
6265 order, we'll eventually bail out, but won't know that until the end.
6266 If they are the same, we'll strip one level around this loop. */
6269 {
6281 /* We matched: remove one reg completely. */
6284 /* An alternate match. */
6287 /* An alternate match. */
6289 else
6290 {
6291 /* Indicates an extra register in B. Strip one level from B and
6292 recurse, hoping B was the higher order expression. */
6297 }
6298 }
6300 /* Here we are at the last level of A, go through the cases hoping to
6301 get rid of everything but a constant. */
6304 {
6317 }
6319 {
6321 }
6323 {
6324 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6325 }
6327 {
6332 else
6334 }
6339 }
6341 rtx
6344 {
6347 /* The value that G1 will be multiplied by must be a constant integer. Also,
6348 the only chance we have of getting a valid address is if b*c/a (see above
6349 for notation) is also an integer. */
6352 {
6357 }
6360 else
6361 {
6362 /* ??? Find out if the one is a multiple of the other? */
6364 }
6368 {
6369 /* Failed. If we've got a multiplication factor between G1 and G2,
6370 scale G1's addend and try again. */
6372 {
6376 {
6377 HOST_WIDE_INT m;
6381 }
6382 else
6383 {
6385 mult);
6386 }
6389 }
6390 }
6394 /* Form simplified final result. */
6399 else
6404 else
6405 {
6408 {
6412 }
6415 }
6416 }
6417 \f
6418 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6419 represented by G1. This indicates that G2 should be combined with G1 and
6420 that G2 can use (either directly or via an address expression) a register
6421 used to represent G1. */
6423 static rtx
6426 {
6429 /* With the introduction of ext dependant givs, we must care for modes.
6430 G2 must not use a wider mode than G1. */
6440 /* If these givs are identical, they can be combined. We use the results
6441 of express_from because the addends are not in a canonical form, so
6442 rtx_equal_p is a weaker test. */
6443 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6444 combination to be the other way round. */
6447 {
6449 }
6451 /* If G2 can be expressed as a function of G1 and that function is valid
6452 as an address and no more expensive than using a register for G2,
6453 the expression of G2 in terms of G1 can be used. */
6457 /* ??? Looses, especially with -fforce-addr, where *g2->location
6458 will always be a register, and so anything more complicated
6459 gets discarded. */
6460 #if 0
6461 #ifdef ADDRESS_COST
6463 #else
6465 #endif
6466 #endif
6467 )
6468 {
6470 }
6473 }
6474 \f
6475 /* Check each extension dependant giv in this class to see if its
6476 root biv is safe from wrapping in the interior mode, which would
6477 make the giv illegal. */
6479 static void
6483 {
6486 HOST_WIDE_INT start_val;
6492 /* Make sure the iteration data is available. We must have
6493 constants in order to be certain of no overflow. */
6494 /* ??? An unknown iteration count with an increment of +-1
6495 combined with friendly exit tests of against an invariant
6496 value is also ameanable to optimization. Not implemented. */
6502 /* Make sure the host can represent the arithmetic. */
6504 {
6506 HOST_WIDE_INT s_end_val;
6518 /* Check for host arithmatic overflow. */
6520 {
6522 HOST_WIDE_INT s_max;
6529 /* Check zero extension of biv ok. */
6531 /* Check for host arithmatic overflow. */
6532 && (neg_incr
6535 /* Check for target arithmetic overflow. */
6536 && (neg_incr
6539 {
6541 }
6543 /* Check sign extension of biv ok. */
6544 /* ??? While it is true that overflow with signed and pointer
6545 arithmetic is undefined, I fear too many programmers don't
6546 keep this fact in mind -- myself included on occasion.
6547 So leave alone with the signed overflow optimizations. */
6549 /* Check for host arithmatic overflow. */
6550 && (neg_incr
6553 /* Check for target arithmetic overflow. */
6554 && (neg_incr
6557 {
6559 }
6560 }
6561 }
6563 /* Invalidate givs that fail the tests. */
6566 {
6571 {
6580 /* We don't know whether this value is being used as either
6581 signed or unsigned, so to safely truncate we must satisfy
6582 both. The initial check here verifies the BIV itself;
6583 once that is successful we may check its range wrt the
6584 derived GIV. */
6586 {
6590 /* We know from the above that both endpoints are nonnegative,
6591 and that there is no wrapping. Verify that both endpoints
6592 are within the (signed) range of the outer mode. */
6595 }
6600 }
6603 {
6605 {
6609 }
6610 }
6611 else
6612 {
6614 {
6619 else
6620 {
6625 else
6627 }
6632 }
6634 }
6635 }
6636 }
6638 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6640 rtx
6643 rtx value;
6644 {
6650 /* Recall that check_ext_dependant_givs verified that the known bounds
6651 of a biv did not overflow or wrap with respect to the extension for
6652 the giv. Therefore, constants need no additional adjustment. */
6656 /* Otherwise, we must adjust the value to compensate for the
6657 differing modes of the biv and the giv. */
6659 }
6660 \f
6661 struct combine_givs_stats
6662 {
6665 };
6667 static int
6671 {
6678 /* Stabilize the sort. */
6682 }
6684 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6685 any other. If so, point SAME to the giv combined with and set NEW_REG to
6686 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6687 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6689 static void
6693 {
6694 /* Additional benefit to add for being combined multiple times. */
6702 /* Count givs, because bl->giv_count is incorrect here. */
6706 giv_count++;
6708 giv_array
6719 {
6721 rtx single_use;
6726 /* If a DEST_REG GIV is used only once, do not allow it to combine
6727 with anything, for in doing so we will gain nothing that cannot
6728 be had by simply letting the GIV with which we would have combined
6729 to be reduced on its own. The losage shows up in particular with
6730 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6731 be seen elsewhere as well. */
6738 /* Add an additional weight for zero addends. */
6743 {
6744 rtx this_combine;
6749 {
6752 }
6753 }
6755 }
6757 /* Iterate, combining until we can't. */
6758 restart:
6762 {
6765 {
6771 }
6773 }
6776 {
6782 /* If it has already been combined, skip. */
6787 {
6790 /* If it has already been combined, skip. */
6792 {
6802 /* ??? The new final_[bg]iv_value code does a much better job
6803 of finding replaceable giv's, and hence this code may no
6804 longer be necessary. */
6808 /* To help optimize the next set of combinations, remove
6809 this giv from the benefits of other potential mates. */
6811 {
6815 }
6822 }
6823 }
6825 /* To help optimize the next set of combinations, remove
6826 this giv from the benefits of other potential mates. */
6828 {
6830 {
6834 }
6838 /* We've finished with this giv, and everything it touched.
6839 Restart the combination so that proper weights for the
6840 rest of the givs are properly taken into account. */
6841 /* ??? Ideally we would compact the arrays at this point, so
6842 as to not cover old ground. But sanely compacting
6843 can_combine is tricky. */
6845 }
6846 }
6848 /* Clean up. */
6851 }
6852 \f
6853 /* Generate sequence for REG = B * M + A. */
6855 static rtx
6861 {
6862 rtx seq;
6863 rtx result;
6866 /* Use unsigned arithmetic. */
6874 }
6877 /* Update registers created in insn sequence SEQ. */
6879 static void
6882 rtx seq;
6883 {
6884 /* Update register info for alias analysis. */
6887 {
6890 {
6894 }
6895 }
6896 else
6897 {
6901 }
6902 }
6905 /* EMIT code before BEFORE_BB/BEFORE_INSN to set REG = B * M + A. */
6907 void
6914 basic_block before_bb;
6915 rtx before_insn;
6916 {
6917 rtx seq;
6920 {
6923 }
6925 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
6928 /* Increase the lifetime of any invariants moved further in code. */
6935 /* It is possible that the expansion created lots of new registers.
6936 Iterate over the sequence we just created and record them all. */
6938 }
6941 /* Emit insns in loop pre-header to set REG = B * M + A. */
6943 void
6950 {
6951 rtx seq;
6953 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
6956 /* Increase the lifetime of any invariants moved further in code.
6957 ???? Is this really necessary? */
6964 /* It is possible that the expansion created lots of new registers.
6965 Iterate over the sequence we just created and record them all. */
6967 }
6970 /* Emit insns after loop to set REG = B * M + A. */
6972 void
6979 {
6980 rtx seq;
6982 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
6987 /* It is possible that the expansion created lots of new registers.
6988 Iterate over the sequence we just created and record them all. */
6990 }
6994 /* Similar to gen_add_mult, but compute cost rather than generating
6995 sequence. */
6997 static int
7003 {
7013 {
7018 }
7021 }
7022 \f
7023 /* Test whether A * B can be computed without
7024 an actual multiply insn. Value is 1 if so. */
7026 static int
7028 rtx a;
7029 rtx b;
7030 {
7032 rtx tmp;
7035 /* If only one is constant, make it B. */
7039 /* If first constant, both constant, so don't need multiply. */
7043 /* If second not constant, neither is constant, so would need multiply. */
7047 /* One operand is constant, so might not need multiply insn. Generate the
7048 code for the multiply and see if a call or multiply, or long sequence
7049 of insns is generated. */
7057 {
7062 else
7064 {
7073 {
7076 }
7077 }
7078 }
7088 }
7089 \f
7090 /* Check to see if loop can be terminated by a "decrement and branch until
7091 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7092 Also try reversing an increment loop to a decrement loop
7093 to see if the optimization can be performed.
7094 Value is nonzero if optimization was performed. */
7096 /* This is useful even if the architecture doesn't have such an insn,
7097 because it might change a loops which increments from 0 to n to a loop
7098 which decrements from n to 0. A loop that decrements to zero is usually
7099 faster than one that increments from zero. */
7101 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7102 such as approx_final_value, biv_total_increment, loop_iterations, and
7103 final_[bg]iv_value. */
7105 static int
7109 {
7114 rtx reg;
7115 rtx jump_label;
7116 rtx final_value;
7117 rtx start_value;
7118 rtx new_add_val;
7119 rtx comparison;
7120 rtx before_comparison;
7121 rtx p;
7122 rtx jump;
7123 rtx first_compare;
7128 /* If last insn is a conditional branch, and the insn before tests a
7129 register value, try to optimize it. Otherwise, we can't do anything. */
7138 /* Try to compute whether the compare/branch at the loop end is one or
7139 two instructions. */
7145 else
7148 {
7149 /* If more than one condition is present to control the loop, then
7150 do not proceed, as this function does not know how to rewrite
7151 loop tests with more than one condition.
7153 Look backwards from the first insn in the last comparison
7154 sequence and see if we've got another comparison sequence. */
7156 rtx jump1;
7160 }
7162 /* Check all of the bivs to see if the compare uses one of them.
7163 Skip biv's set more than once because we can't guarantee that
7164 it will be zero on the last iteration. Also skip if the biv is
7165 used between its update and the test insn. */
7168 {
7173 first_compare))
7175 }
7180 /* Look for the case where the basic induction variable is always
7181 nonnegative, and equals zero on the last iteration.
7182 In this case, add a reg_note REG_NONNEG, which allows the
7183 m68k DBRA instruction to be used. */
7191 {
7192 /* Initial value must be greater than 0,
7193 init_val % -dec_value == 0 to ensure that it equals zero on
7194 the last iteration */
7200 {
7201 /* register always nonnegative, add REG_NOTE to branch */
7209 }
7211 /* If the decrement is 1 and the value was tested as >= 0 before
7212 the loop, then we can safely optimize. */
7214 {
7227 {
7235 }
7236 }
7237 }
7240 {
7241 /* Try to change inc to dec, so can apply above optimization. */
7242 /* Can do this if:
7243 all registers modified are induction variables or invariant,
7244 all memory references have non-overlapping addresses
7245 (obviously true if only one write)
7246 allow 2 insns for the compare/jump at the end of the loop. */
7247 /* Also, we must avoid any instructions which use both the reversed
7248 biv and another biv. Such instructions will fail if the loop is
7249 reversed. We meet this condition by requiring that either
7250 no_use_except_counting is true, or else that there is only
7251 one biv. */
7253 /* 1 if the iteration var is used only to count iterations. */
7255 /* 1 if the loop has no memory store, or it has a single memory store
7256 which is reversible. */
7260 {
7264 /* If there are no givs for this biv, and the only exit is the
7265 fall through at the end of the loop, then
7266 see if perhaps there are no uses except to count. */
7270 {
7275 /* An insn that sets the biv is okay. */
7276 ;
7280 {
7281 /* If either of these insns uses the biv and sets a pseudo
7282 that has more than one usage, then the biv has uses
7283 other than counting since it's used to derive a value
7284 that is used more than one time. */
7286 regs);
7288 {
7291 }
7292 }
7294 {
7297 }
7298 }
7300 /* A biv has uses besides counting if it is used to set another biv. */
7303 {
7306 }
7307 }
7310 /* No need to worry about MEMs. */
7311 ;
7313 {
7318 /* If the loop has a single store, and the destination address is
7319 invariant, then we can't reverse the loop, because this address
7320 might then have the wrong value at loop exit.
7321 This would work if the source was invariant also, however, in that
7322 case, the insn should have been moved out of the loop. */
7325 {
7328 reversible_mem_store
7335 /* If the store depends on a register that is set after the
7336 store, it depends on the initial value, and is thus not
7337 reversible. */
7339 {
7346 }
7347 }
7348 }
7349 else
7352 /* This code only acts for innermost loops. Also it simplifies
7353 the memory address check by only reversing loops with
7354 zero or one memory access.
7355 Two memory accesses could involve parts of the same array,
7356 and that can't be reversed.
7357 If the biv is used only for counting, than we don't need to worry
7358 about all these things. */
7363 && reversible_mem_store
7368 {
7369 rtx tem;
7371 /* Loop can be reversed. */
7375 /* Now check other conditions:
7377 The increment must be a constant, as must the initial value,
7378 and the comparison code must be LT.
7380 This test can probably be improved since +/- 1 in the constant
7381 can be obtained by changing LT to LE and vice versa; this is
7382 confusing. */
7385 /* for constants, LE gets turned into LT */
7389 {
7400 comparison_const_width
7402 else
7403 comparison_const_width
7407 comparison_sign_mask
7410 /* If the comparison value is not a loop invariant, then we
7411 can not reverse this loop.
7413 ??? If the insns which initialize the comparison value as
7414 a whole compute an invariant result, then we could move
7415 them out of the loop and proceed with loop reversal. */
7423 /* Normalize the initial value if it is an integer and
7424 has no other use except as a counter. This will allow
7425 a few more loops to be reversed. */
7429 {
7431 /* The code below requires comparison_val to be a multiple
7432 of add_val in order to do the loop reversal, so
7433 round up comparison_val to a multiple of add_val.
7434 Since comparison_value is constant, we know that the
7435 current comparison code is LT. */
7437 comparison_val
7439 /* We postpone overflow checks for COMPARISON_VAL here;
7440 even if there is an overflow, we might still be able to
7441 reverse the loop, if converting the loop exit test to
7442 NE is possible. */
7444 }
7446 /* First check if we can do a vanilla loop reversal. */
7448 /* If we have a decrement_and_branch_on_count,
7449 prefer the NE test, since this will allow that
7450 instruction to be generated. Note that we must
7451 use a vanilla loop reversal if the biv is used to
7452 calculate a giv or has a non-counting use. */
7453 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7454 && defined (HAVE_decrement_and_branch_on_count)
7458 #endif
7460 /* Now do postponed overflow checks on COMPARISON_VAL. */
7463 {
7464 /* Register will always be nonnegative, with value
7465 0 on last iteration */
7469 }
7473 {
7476 }
7477 else
7483 /* If the initial value is not zero, or if the comparison
7484 value is not an exact multiple of the increment, then we
7485 can not reverse this loop. */
7488 {
7491 }
7492 else
7493 {
7496 }
7500 /* Reset these in case we normalized the initial value
7501 and comparison value above. */
7504 {
7506 final_value
7508 }
7511 /* Save some info needed to produce the new insns. */
7518 /* Set start_value; if this is not a CONST_INT, we need
7519 to generate a SUB.
7520 Initialize biv to start_value before loop start.
7521 The old initializing insn will be deleted as a
7522 dead store by flow.c. */
7525 {
7528 }
7530 {
7533 enum insn_code icode
7542 start_value
7549 }
7551 {
7553 enum insn_code icode
7561 start_value
7565 initial_value)));
7566 }
7567 else
7568 /* We could handle the other cases too, but it'll be
7569 better to have a testcase first. */
7572 /* We may not have a single insn which can increment a reg, so
7573 create a sequence to hold all the insns from expand_inc. */
7582 /* Update biv info to reflect its new status. */
7587 /* Update loop info. */
7596 /* Inc LABEL_NUSES so that delete_insn will
7597 not delete the label. */
7600 /* Emit an insn after the end of the loop to set the biv's
7601 proper exit value if it is used anywhere outside the loop. */
7607 /* Delete compare/branch at end of loop. */
7612 /* Add new compare/branch insn at end of loop. */
7624 ;
7630 {
7632 {
7633 /* Increment of LABEL_NUSES done above. */
7634 /* Register is now always nonnegative,
7635 so add REG_NONNEG note to the branch. */
7638 }
7640 }
7642 /* No insn may reference both the reversed and another biv or it
7643 will fail (see comment near the top of the loop reversal
7644 code).
7645 Earlier on, we have verified that the biv has no use except
7646 counting, or it is the only biv in this function.
7647 However, the code that computes no_use_except_counting does
7648 not verify reg notes. It's possible to have an insn that
7649 references another biv, and has a REG_EQUAL note with an
7650 expression based on the reversed biv. To avoid this case,
7651 remove all REG_EQUAL notes based on the reversed biv
7652 here. */
7655 {
7658 /* If this is a set of a GIV based on the reversed biv, any
7659 REG_EQUAL notes should still be correct. */
7666 {
7671 else
7673 }
7674 }
7676 /* Mark that this biv has been reversed. Each giv which depends
7677 on this biv, and which is also live past the end of the loop
7678 will have to be fixed up. */
7683 {
7687 else
7689 }
7692 }
7693 }
7694 }
7697 }
7698 \f
7699 /* Verify whether the biv BL appears to be eliminable,
7700 based on the insns in the loop that refer to it.
7702 If ELIMINATE_P is non-zero, actually do the elimination.
7704 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7705 determine whether invariant insns should be placed inside or at the
7706 start of the loop. */
7708 static int
7714 {
7717 rtx p;
7719 /* Scan all insns in the loop, stopping if we find one that uses the
7720 biv in a way that we cannot eliminate. */
7723 {
7728 /* If this is a libcall that sets a giv, skip ahead to its end. */
7730 {
7734 {
7739 {
7746 }
7747 }
7748 }
7753 {
7759 }
7760 }
7763 {
7768 }
7771 }
7772 \f
7773 /* INSN and REFERENCE are instructions in the same insn chain.
7774 Return non-zero if INSN is first. */
7776 int
7779 {
7783 {
7784 /* Start with test for not first so that INSN == REFERENCE yields not
7785 first. */
7791 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7792 previous insn, hence the <= comparison below does not work if
7793 P is a note. */
7804 }
7805 }
7807 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7808 the offset that we have to take into account due to auto-increment /
7809 div derivation is zero. */
7810 static int
7813 rtx insn;
7814 {
7815 /* If the giv V had the auto-inc address optimization applied
7816 to it, and INSN occurs between the giv insn and the biv
7817 insn, then we'd have to adjust the value used here.
7818 This is rare, so we don't bother to make this possible. */
7827 }
7829 /* If BL appears in X (part of the pattern of INSN), see if we can
7830 eliminate its use. If so, return 1. If not, return 0.
7832 If BIV does not appear in X, return 1.
7834 If ELIMINATE_P is non-zero, actually do the elimination.
7835 WHERE_INSN/WHERE_BB indicate where extra insns should be added.
7836 Depending on how many items have been moved out of the loop, it
7837 will either be before INSN (when WHERE_INSN is non-zero) or at the
7838 start of the loop (when WHERE_INSN is zero). */
7840 static int
7846 basic_block where_bb;
7847 rtx where_insn;
7848 {
7854 #ifdef HAVE_cc0
7856 #endif
7862 {
7864 /* If we haven't already been able to do something with this BIV,
7865 we can't eliminate it. */
7871 /* If this sets the BIV, it is not a problem. */
7875 /* If this is an insn that defines a giv, it is also ok because
7876 it will go away when the giv is reduced. */
7881 #ifdef HAVE_cc0
7883 {
7884 /* Can replace with any giv that was reduced and
7885 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7886 Require a constant for MULT_VAL, so we know it's nonzero.
7887 ??? We disable this optimization to avoid potential
7888 overflows. */
7896 {
7903 /* If the giv has the opposite direction of change,
7904 then reverse the comparison. */
7908 else
7911 /* We can probably test that giv's reduced reg. */
7914 }
7916 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7917 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7918 Require a constant for MULT_VAL, so we know it's nonzero.
7919 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7920 overflow problem. */
7932 {
7939 /* If the giv has the opposite direction of change,
7940 then reverse the comparison. */
7944 else
7948 /* Replace biv with the giv's reduced register. */
7953 /* Insn doesn't support that constant or invariant. Copy it
7954 into a register (it will be a loop invariant.) */
7961 /* Substitute the new register for its invariant value in
7962 the compare expression. */
7966 }
7967 }
7968 #endif
7975 /* See if either argument is the biv. */
7980 else
7984 {
7985 /* First try to replace with any giv that has constant positive
7986 mult_val and constant add_val. We might be able to support
7987 negative mult_val, but it seems complex to do it in general. */
7999 {
8006 /* Replace biv with the giv's reduced reg. */
8009 /* If all constants are actually constant integers and
8010 the derived constant can be directly placed in the COMPARE,
8011 do so. */
8015 {
8020 }
8021 else
8022 {
8023 /* Otherwise, load it into a register. */
8029 }
8032 }
8034 /* Look for giv with positive constant mult_val and nonconst add_val.
8035 Insert insns to calculate new compare value.
8036 ??? Turn this off due to possible overflow. */
8044 {
8045 rtx tem;
8055 /* Replace biv with giv's reduced register. */
8059 /* Compute value to compare against. */
8063 /* Use it in this insn. */
8067 }
8068 }
8070 {
8072 {
8073 /* Look for giv with constant positive mult_val and nonconst
8074 add_val. Insert insns to compute new compare value.
8075 ??? Turn this off due to possible overflow. */
8082 {
8083 rtx tem;
8093 /* Replace biv with giv's reduced register. */
8097 /* Compute value to compare against. */
8104 }
8105 }
8107 /* This code has problems. Basically, you can't know when
8108 seeing if we will eliminate BL, whether a particular giv
8109 of ARG will be reduced. If it isn't going to be reduced,
8110 we can't eliminate BL. We can try forcing it to be reduced,
8111 but that can generate poor code.
8113 The problem is that the benefit of reducing TV, below should
8114 be increased if BL can actually be eliminated, but this means
8115 we might have to do a topological sort of the order in which
8116 we try to process biv. It doesn't seem worthwhile to do
8117 this sort of thing now. */
8119 #if 0
8120 /* Otherwise the reg compared with had better be a biv. */
8125 /* Look for a pair of givs, one for each biv,
8126 with identical coefficients. */
8128 {
8140 {
8147 /* Replace biv with its giv's reduced reg. */
8149 /* Replace other operand with the other giv's
8150 reduced reg. */
8153 }
8154 }
8155 #endif
8156 }
8158 /* If we get here, the biv can't be eliminated. */
8162 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8163 biv is used in it, since it will be replaced. */
8171 }
8173 /* See if any subexpression fails elimination. */
8176 {
8178 {
8191 }
8192 }
8195 }
8196 \f
8197 /* Return nonzero if the last use of REG
8198 is in an insn following INSN in the same basic block. */
8200 static int
8202 rtx reg;
8203 rtx insn;
8204 {
8205 rtx n;
8209 {
8212 }
8214 }
8215 \f
8216 /* Called via `note_stores' to record the initial value of a biv. Here we
8217 just record the location of the set and process it later. */
8219 static void
8221 rtx dest;
8222 rtx set;
8224 {
8235 /* If this is the first set found, record it. */
8237 {
8240 }
8241 }
8242 \f
8243 /* If any of the registers in X are "old" and currently have a last use earlier
8244 than INSN, update them to have a last use of INSN. Their actual last use
8245 will be the previous insn but it will not have a valid uid_luid so we can't
8246 use it. X must be a source expression only. */
8248 static void
8250 rtx x;
8251 rtx insn;
8252 {
8253 /* Check for the case where INSN does not have a valid luid. In this case,
8254 there is no need to modify the regno_last_uid, as this can only happen
8255 when code is inserted after the loop_end to set a pseudo's final value,
8256 and hence this insn will never be the last use of x.
8257 ???? This comment is not correct. See for example loop_givs_reduce.
8258 This may insert an insn before another new insn. */
8262 {
8264 }
8265 else
8266 {
8270 {
8276 }
8277 }
8278 }
8279 \f
8280 /* Given an insn INSN and condition COND, return the condition in a
8281 canonical form to simplify testing by callers. Specifically:
8283 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8284 (2) Both operands will be machine operands; (cc0) will have been replaced.
8285 (3) If an operand is a constant, it will be the second operand.
8286 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8287 for GE, GEU, and LEU.
8289 If the condition cannot be understood, or is an inequality floating-point
8290 comparison which needs to be reversed, 0 will be returned.
8292 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8294 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8295 insn used in locating the condition was found. If a replacement test
8296 of the condition is desired, it should be placed in front of that
8297 insn and we will be sure that the inputs are still valid.
8299 If WANT_REG is non-zero, we wish the condition to be relative to that
8300 register, if possible. Therefore, do not canonicalize the condition
8301 further. */
8303 rtx
8305 rtx insn;
8306 rtx cond;
8309 rtx want_reg;
8310 {
8313 rtx set;
8314 rtx tem;
8326 {
8329 }
8334 /* If we are comparing a register with zero, see if the register is set
8335 in the previous insn to a COMPARE or a comparison operation. Perform
8336 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8337 in cse.c */
8342 {
8343 /* Set non-zero when we find something of interest. */
8346 #ifdef HAVE_cc0
8347 /* If comparison with cc0, import actual comparison from compare
8348 insn. */
8350 {
8361 }
8362 #endif
8364 /* If this is a COMPARE, pick up the two things being compared. */
8366 {
8370 }
8374 /* Go back to the previous insn. Stop if it is not an INSN. We also
8375 stop if it isn't a single set or if it has a REG_INC note because
8376 we don't want to bother dealing with it. */
8384 /* If this is setting OP0, get what it sets it to if it looks
8385 relevant. */
8387 {
8390 /* ??? We may not combine comparisons done in a CCmode with
8391 comparisons not done in a CCmode. This is to aid targets
8392 like Alpha that have an IEEE compliant EQ instruction, and
8393 a non-IEEE compliant BEQ instruction. The use of CCmode is
8394 actually artificial, simply to prevent the combination, but
8395 should not affect other platforms.
8397 However, we must allow VOIDmode comparisons to match either
8398 CCmode or non-CCmode comparison, because some ports have
8399 modeless comparisons inside branch patterns.
8401 ??? This mode check should perhaps look more like the mode check
8402 in simplify_comparison in combine. */
8410 && (STORE_FLAG_VALUE
8413 #ifdef FLOAT_STORE_FLAG_VALUE
8416 && (REAL_VALUE_NEGATIVE
8418 #endif
8419 ))
8430 && (STORE_FLAG_VALUE
8433 #ifdef FLOAT_STORE_FLAG_VALUE
8436 && (REAL_VALUE_NEGATIVE
8438 #endif
8439 ))
8445 {
8446 /* We might have reversed a LT to get a GE here. But this wasn't
8447 actually the comparison of data, so we don't flag that we
8448 have had to reverse the condition. */
8452 }
8453 else
8455 }
8458 /* If this sets OP0, but not directly, we have to give up. */
8462 {
8466 {
8472 }
8477 }
8478 }
8480 /* If constant is first, put it last. */
8484 /* If OP0 is the result of a comparison, we weren't able to find what
8485 was really being compared, so fail. */
8489 /* Canonicalize any ordered comparison with integers involving equality
8490 if we can do computations in the relevant mode and we do not
8491 overflow. */
8496 {
8499 unsigned HOST_WIDE_INT max_val
8503 {
8509 /* When cross-compiling, const_val might be sign-extended from
8510 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8530 }
8531 }
8533 /* If this was floating-point and we reversed anything other than an
8534 EQ or NE or (UN)ORDERED, return zero. */
8536 && did_reverse_condition
8538 && ! flag_fast_math
8542 #ifdef HAVE_cc0
8543 /* Never return CC0; return zero instead. */
8546 #endif
8549 }
8551 /* Given a jump insn JUMP, return the condition that will cause it to branch
8552 to its JUMP_LABEL. If the condition cannot be understood, or is an
8553 inequality floating-point comparison which needs to be reversed, 0 will
8554 be returned.
8556 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8557 insn used in locating the condition was found. If a replacement test
8558 of the condition is desired, it should be placed in front of that
8559 insn and we will be sure that the inputs are still valid. */
8561 rtx
8563 rtx jump;
8565 {
8566 rtx cond;
8568 rtx set;
8570 /* If this is not a standard conditional jump, we can't parse it. */
8578 /* If this branches to JUMP_LABEL when the condition is false, reverse
8579 the condition. */
8580 reverse
8585 }
8587 /* Similar to above routine, except that we also put an invariant last
8588 unless both operands are invariants. */
8590 rtx
8593 rtx x;
8594 {
8604 }
8606 /* Scan the function and determine whether it has indirect (computed) jumps.
8608 This is taken mostly from flow.c; similar code exists elsewhere
8609 in the compiler. It may be useful to put this into rtlanal.c. */
8610 static int
8612 rtx start;
8613 {
8614 rtx insn;
8621 }
8623 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8624 documentation for LOOP_MEMS for the definition of `appropriate'.
8625 This function is called from prescan_loop via for_each_rtx. */
8627 static int
8631 {
8640 {
8645 /* We're not interested in MEMs that are only clobbered. */
8649 /* We're not interested in the MEM associated with a
8650 CONST_DOUBLE, so there's no need to traverse into this. */
8654 /* We're not interested in any MEMs that only appear in notes. */
8658 /* This is not a MEM. */
8660 }
8662 /* See if we've already seen this MEM. */
8665 {
8667 /* The modes of the two memory accesses are different. If
8668 this happens, something tricky is going on, and we just
8669 don't optimize accesses to this MEM. */
8673 }
8675 /* Resize the array, if necessary. */
8677 {
8680 else
8686 }
8688 /* Actually insert the MEM. */
8690 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8691 because we can't put it in a register. We still store it in the
8692 table, though, so that if we see the same address later, but in a
8693 non-BLK mode, we'll not think we can optimize it at that point. */
8699 }
8702 /* Allocate REGS->ARRAY or reallocate it if it is too small.
8704 Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
8705 register that is modified by an insn between FROM and TO. If the
8706 value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
8707 more, stop incrementing it, to avoid overflow.
8709 Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
8710 register I is used, if it is only used once. Otherwise, it is set
8711 to 0 (for no uses) or const0_rtx for more than one use. This
8712 parameter may be zero, in which case this processing is not done.
8714 Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
8715 optimize register I.
8717 Store in *COUNT_PTR the number of actual instructions
8718 in the loop. We use this to decide what is worth moving out. */
8720 static void
8725 {
8728 /* last_set[n] is nonzero iff reg n has been set in the current
8729 basic block. In that case, it is the insn that last set reg n. */
8731 rtx insn;
8738 /* Grow the regs array if not allocated or too small. */
8740 {
8746 /* Zero the new elements. */
8749 }
8751 /* Clear previously scanned fields but do not clear n_times_set. */
8753 {
8757 }
8761 /* Scan the loop, recording register usage. */
8764 {
8766 {
8769 /* Record registers that have exactly one use. */
8772 /* Include uses in REG_EQUAL notes. */
8780 {
8784 last_set);
8785 }
8786 }
8790 }
8793 {
8796 }
8798 #ifdef AVOID_CCMODE_COPIES
8799 /* Don't try to move insns which set CC registers if we should not
8800 create CCmode register copies. */
8804 #endif
8806 /* Set regs->array[I].n_times_set for the new registers. */
8812 }
8815 /* Move MEMs into registers for the duration of the loop. */
8817 static void
8820 {
8827 rtx end_label;
8828 /* Nonzero if the next instruction may never be executed. */
8835 /* We cannot use next_label here because it skips over normal insns. */
8840 /* Check to see if it's possible that some instructions in the loop are
8841 never executed. Also check if there is a goto out of the loop other
8842 than right after the end of the loop. */
8846 {
8850 /* If we enter the loop in the middle, and scan
8851 around to the beginning, don't set maybe_never
8852 for that. This must be an unconditional jump,
8853 otherwise the code at the top of the loop might
8854 never be executed. Unconditional jumps are
8855 followed a by barrier then loop end. */
8860 {
8861 /* If this is a jump outside of the loop but not right
8862 after the end of the loop, we would have to emit new fixup
8863 sequences for each such label. */
8865 JUMP_INSN is executed, we must be conservative. */
8874 /* Something complicated. */
8876 else
8877 /* If there are any more instructions in the loop, they
8878 might not be reached. */
8880 }
8883 }
8885 /* Find start of the extended basic block that enters the loop. */
8889 ;
8894 /* Build table of mems that get set to constant values before the
8895 loop. */
8899 /* Actually move the MEMs. */
8901 {
8902 regset_head load_copies;
8903 regset_head store_copies;
8905 rtx reg;
8907 rtx mem_list_entry;
8911 /* There's no telling whether or not MEM is modified. */
8914 /* Go through the MEMs written to in the loop to see if this
8915 one is aliased by one of them. */
8918 {
8923 {
8924 /* MEM is indeed aliased by this store. */
8927 }
8929 }
8935 /* If this MEM is written to, we must be sure that there
8936 are no reads from another MEM that aliases this one. */
8938 {
8942 {
8946 VOIDmode,
8948 rtx_varies_p))
8949 {
8950 /* It's not safe to hoist loop_info->mems[i] out of
8951 the loop because writes to it might not be
8952 seen by reads from loop_info->mems[j]. */
8955 }
8956 }
8957 }
8960 /* We can't access the MEM outside the loop; it might
8961 cause a trap that wouldn't have happened otherwise. */
8965 /* We thought we were going to lift this MEM out of the
8966 loop, but later discovered that we could not. */
8972 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8973 order to keep scan_loop from moving stores to this MEM
8974 out of the loop just because this REG is neither a
8975 user-variable nor used in the loop test. */
8980 /* Now, replace all references to the MEM with the
8981 corresponding pseudos. */
8986 {
8988 {
8989 rtx set;
8993 /* See if this copies the mem into a register that isn't
8994 modified afterwards. We'll try to do copy propagation
8995 a little further on. */
8997 /* @@@ This test is _way_ too conservative. */
8998 && ! maybe_never
9006 /* See if this copies the mem from a register that isn't
9007 modified afterwards. We'll try to remove the
9008 redundant copy later on by doing a little register
9009 renaming and copy propagation. This will help
9010 to untangle things for the BIV detection code. */
9012 && ! maybe_never
9020 /* Replace the memory reference with the shadow register. */
9023 }
9028 }
9031 /* We couldn't replace all occurrences of the MEM. */
9033 else
9034 {
9035 /* Load the memory immediately before LOOP->START, which is
9036 the NOTE_LOOP_BEG. */
9038 rtx set;
9044 {
9048 {
9052 /* Extending hard register lifetimes causes crash
9053 on SRC targets. Doing so on non-SRC is
9054 probably also not good idea, since we most
9055 probably have pseudoregister equivalence as
9056 well. */
9059 }
9060 /* Use the constant equivalence if that is cheap enough. */
9066 {
9069 }
9071 /* If best_equiv is nonzero, we know that MEM is set to a
9072 constant or register before the loop. We will use this
9073 knowledge to initialize the shadow register with that
9074 constant or reg rather than by loading from MEM. */
9077 }
9082 {
9085 {
9088 }
9089 }
9097 {
9099 {
9102 }
9104 /* Store the memory immediately after END, which is
9105 the NOTE_LOOP_END. */
9108 }
9111 {
9116 }
9118 /* Attempt a bit of copy propagation. This helps untangle the
9119 data flow, and enables {basic,general}_induction_var to find
9120 more bivs/givs. */
9121 EXECUTE_IF_SET_IN_REG_SET
9123 {
9125 });
9128 EXECUTE_IF_SET_IN_REG_SET
9130 {
9132 });
9134 }
9135 }
9138 {
9139 /* Now, we need to replace all references to the previous exit
9140 label with the new one. */
9141 rtx_pair rr;
9146 {
9149 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9150 field. This is not handled by for_each_rtx because it doesn't
9151 handle unprinted ('0') fields. We need to update JUMP_LABEL
9152 because the immediately following unroll pass will use it.
9153 replace_label would not work anyways, because that only handles
9154 LABEL_REFs. */
9157 }
9158 }
9161 }
9163 /* For communication between note_reg_stored and its caller. */
9164 struct note_reg_stored_arg
9165 {
9167 rtx reg;
9168 };
9170 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9171 is equal to ARG. */
9172 static void
9176 {
9180 }
9182 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9183 There must be exactly one insn that sets this pseudo; it will be
9184 deleted if all replacements succeed and we can prove that the register
9185 is not used after the loop. */
9187 static void
9190 rtx replacement;
9192 {
9193 /* This is the reg that we are copying from. */
9196 rtx insn;
9197 /* These help keep track of whether we replaced all uses of the reg. */
9204 {
9205 rtx set;
9207 /* Only substitute within one extended basic block from the initializing
9208 insn. */
9215 /* Is this the initializing insn? */
9220 {
9227 }
9229 /* Only substitute after seeing the initializing insn. */
9231 {
9238 /* Stop replacing when REPLACEMENT is modified. */
9244 }
9245 }
9249 {
9253 {
9259 }
9262 }
9263 }
9265 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9266 loop LOOP if the order of the sets of these registers can be
9267 swapped. There must be exactly one insn within the loop that sets
9268 this pseudo followed immediately by a move insn that sets
9269 REPLACEMENT with REGNO. */
9270 static void
9273 rtx replacement;
9275 {
9276 rtx insn;
9285 {
9286 /* Search for the insn that copies REGNO to NEW_REGNO? */
9294 }
9297 {
9298 rtx prev_insn;
9299 rtx prev_set;
9301 /* Some DEF-USE info would come in handy here to make this
9302 function more general. For now, just check the previous insn
9303 which is the most likely candidate for setting REGNO. */
9311 {
9312 /* We have:
9313 (set (reg regno) (expr))
9314 (set (reg new_regno) (reg regno))
9316 so try converting this to:
9317 (set (reg new_regno) (expr))
9318 (set (reg regno) (reg new_regno))
9320 The former construct is often generated when a global
9321 variable used for an induction variable is shadowed by a
9322 register (NEW_REGNO). The latter construct improves the
9323 chances of GIV replacement and BIV elimination. */
9333 {
9340 /* Update first use of REGNO. */
9344 /* Now perform copy propagation to hopefully
9345 remove all uses of REGNO within the loop. */
9347 }
9348 }
9349 }
9350 }
9352 /* Replace MEM with its associated pseudo register. This function is
9353 called from load_mems via for_each_rtx. DATA is actually a pointer
9354 to a structure describing the instruction currently being scanned
9355 and the MEM we are currently replacing. */
9357 static int
9361 {
9369 {
9374 /* We're not interested in the MEM associated with a
9375 CONST_DOUBLE, so there's no need to traverse into one. */
9379 /* This is not a MEM. */
9381 }
9384 /* This is not the MEM we are currently replacing. */
9387 /* Actually replace the MEM. */
9391 }
9393 static void
9395 rtx insn;
9396 rtx mem;
9397 rtx reg;
9398 {
9399 loop_replace_args args;
9406 }
9408 /* Replace one register with another. Called through for_each_rtx; PX points
9409 to the rtx being scanned. DATA is actually a pointer to
9410 a structure of arguments. */
9412 static int
9416 {
9427 }
9429 static void
9431 rtx insn;
9432 rtx reg;
9433 rtx replacement;
9434 {
9435 loop_replace_args args;
9442 }
9444 /* Replace occurrences of the old exit label for the loop with the new
9445 one. DATA is an rtx_pair containing the old and new labels,
9446 respectively. */
9448 static int
9452 {
9471 }
9472 \f
9473 /* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB
9474 (ignored in the interim). */
9476 static rtx
9479 basic_block where_bb ATTRIBUTE_UNUSED;
9480 rtx where_insn;
9481 rtx pattern;
9482 {
9484 }
9487 /* If WHERE_INSN is non-zero emit insn for PATTERN before WHERE_INSN
9488 in basic block WHERE_BB (ignored in the interim) within the loop
9489 otherwise hoist PATTERN into the loop pre-header. */
9491 rtx
9494 basic_block where_bb ATTRIBUTE_UNUSED;
9495 rtx where_insn;
9496 rtx pattern;
9497 {
9501 }
9504 /* Emit call insn for PATTERN before WHERE_INSN in basic block
9505 WHERE_BB (ignored in the interim) within the loop. */
9507 static rtx
9510 basic_block where_bb ATTRIBUTE_UNUSED;
9511 rtx where_insn;
9512 rtx pattern;
9513 {
9515 }
9518 /* Hoist insn for PATTERN into the loop pre-header. */
9520 rtx
9523 rtx pattern;
9524 {
9526 }
9529 /* Hoist call insn for PATTERN into the loop pre-header. */
9531 static rtx
9534 rtx pattern;
9535 {
9537 }
9540 /* Sink insn for PATTERN after the loop end. */
9542 rtx
9545 rtx pattern;
9546 {
9548 }
9551 /* If the loop has multiple exits, emit insn for PATTERN before the
9552 loop to ensure that it will always be executed no matter how the
9553 loop exits. Otherwise, emit the insn for PATTERN after the loop,
9554 since this is slightly more efficient. */
9556 static rtx
9559 rtx pattern;
9560 {
9563 else
9565 }
9566 \f
9567 static void
9572 {
9580 iv_num++;
9585 {
9588 }
9589 }
9592 static void
9597 {
9599 rtx incr;
9610 {
9613 }
9615 {
9618 }
9622 {
9626 }
9629 {
9633 }
9635 /* List the increments. */
9637 {
9641 }
9643 /* List the givs. */
9645 {
9650 else
9653 }
9654 }
9657 static void
9662 {
9673 {
9677 }
9680 }
9683 static void
9688 {
9695 else
9711 {
9713 {
9725 }
9726 }
9737 {
9741 }
9744 }
9747 void
9750 {
9752 }
9755 void
9758 {
9760 }
9763 void
9766 {
9768 }
9771 void
9774 {
9776 }
9779 #define LOOP_BLOCK_NUM_1(INSN) \
9780 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9782 /* The notes do not have an assigned block, so look at the next insn. */
9783 #define LOOP_BLOCK_NUM(INSN) \
9784 ((INSN) ? (GET_CODE (INSN) == NOTE \
9785 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9786 : LOOP_BLOCK_NUM_1 (INSN)) \
9787 : -1)
9789 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9791 static void
9796 {
9797 rtx label;
9802 /* Print diagnostics to compare our concept of a loop with
9803 what the loop notes say. */
9818 {
9838 {
9841 {
9844 }
9845 }
9848 /* This can happen when a marked loop appears as two nested loops,
9849 say from while (a || b) {}. The inner loop won't match
9850 the loop markers but the outer one will. */
9853 }
9854 }
9856 /* Call this function from the debugger to dump LOOP. */
9858 void
9861 {
9863 }
9865 /* Call this function from the debugger to dump LOOPS. */
9867 void
9870 {
9872 }