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)
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. */
44 #include "hard-reg-set.h"
45 #include "basic-block.h"
46 #include "insn-config.h"
47 #include "insn-flags.h"
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. */
74 struct loop **uid_loop;
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
87 static int max_loop_num;
89 /* Bound on pseudo register number before loop optimization.
90 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
91 unsigned int max_reg_before_loop;
93 /* The value to pass to the next call of reg_scan_update. */
94 static int loop_max_reg;
96 #define obstack_chunk_alloc xmalloc
97 #define obstack_chunk_free free
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. */
105 rtx insn; /* A movable insn */
106 rtx set_src; /* The expression this reg is set from. */
107 rtx set_dest; /* The destination of this SET. */
108 rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
109 of any registers used within the LIBCALL. */
110 int consec; /* Number of consecutive following insns
111 that must be moved with this one. */
112 unsigned int regno; /* The register it sets */
113 short lifetime; /* lifetime of that register;
114 may be adjusted when matching movables
115 that load the same value are found. */
116 short savings; /* Number of insns we can move for this reg,
117 including other movables that force this
118 or match this one. */
119 unsigned int cond : 1; /* 1 if only conditionally movable */
120 unsigned int force : 1; /* 1 means MUST move this insn */
121 unsigned int global : 1; /* 1 means reg is live outside this loop */
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. */
125 unsigned int done : 1; /* 1 inhibits further processing of this */
127 unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
128 In particular, moving it does not make it
130 unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
131 load SRC, rather than copying INSN. */
132 unsigned int move_insn_first:1;/* Same as above, if this is necessary for the
133 first insn of a consecutive sets group. */
134 unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
135 enum machine_mode savemode; /* Nonzero means it is a mode for a low part
136 that we should avoid changing when clearing
137 the rest of the reg. */
138 struct movable *match; /* First entry for same value */
139 struct movable *forces; /* An insn that must be moved if this is */
140 struct movable *next;
144 FILE *loop_dump_stream;
146 /* Forward declarations. */
148 static void find_and_verify_loops PARAMS ((rtx, struct loops *));
149 static void mark_loop_jump PARAMS ((rtx, struct loop *));
150 static void prescan_loop PARAMS ((struct loop *));
151 static int reg_in_basic_block_p PARAMS ((rtx, rtx));
152 static int consec_sets_invariant_p PARAMS ((const struct loop *,
154 static int labels_in_range_p PARAMS ((rtx, int));
155 static void count_one_set PARAMS ((struct loop_regs *, rtx, rtx, rtx *));
156 static void note_addr_stored PARAMS ((rtx, rtx, void *));
157 static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
158 static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
159 static void scan_loop PARAMS ((struct loop*, int));
161 static void replace_call_address PARAMS ((rtx, rtx, rtx));
163 static rtx skip_consec_insns PARAMS ((rtx, int));
164 static int libcall_benefit PARAMS ((rtx));
165 static void ignore_some_movables PARAMS ((struct loop_movables *));
166 static void force_movables PARAMS ((struct loop_movables *));
167 static void combine_movables PARAMS ((struct loop_movables *,
168 struct loop_regs *));
169 static int regs_match_p PARAMS ((rtx, rtx, struct loop_movables *));
170 static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct loop_movables *,
171 struct loop_regs *));
172 static void add_label_notes PARAMS ((rtx, rtx));
173 static void move_movables PARAMS ((struct loop *loop, struct loop_movables *,
175 static void loop_movables_add PARAMS((struct loop_movables *,
177 static void loop_movables_free PARAMS((struct loop_movables *));
178 static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
179 static void loop_bivs_find PARAMS((struct loop *));
180 static void loop_bivs_init_find PARAMS((struct loop *));
181 static void loop_bivs_check PARAMS((struct loop *));
182 static void loop_givs_find PARAMS((struct loop *));
183 static void loop_givs_check PARAMS((struct loop *));
184 static int loop_biv_eliminable_p PARAMS((struct loop *, struct iv_class *,
186 static int loop_giv_reduce_benefit PARAMS((struct loop *, struct iv_class *,
187 struct induction *, rtx));
188 static void loop_givs_dead_check PARAMS((struct loop *, struct iv_class *));
189 static void loop_givs_reduce PARAMS((struct loop *, struct iv_class *));
190 static void loop_givs_rescan PARAMS((struct loop *, struct iv_class *,
192 static void loop_ivs_free PARAMS((struct loop *));
193 static void strength_reduce PARAMS ((struct loop *, int, int));
194 static void find_single_use_in_loop PARAMS ((struct loop_regs *, rtx, rtx));
195 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
196 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
197 static void record_biv PARAMS ((struct loop *, struct induction *,
198 rtx, rtx, rtx, rtx, rtx *,
200 static void check_final_value PARAMS ((const struct loop *,
201 struct induction *));
202 static void loop_biv_dump PARAMS((const struct induction *, FILE *, int));
203 static void loop_giv_dump PARAMS((const struct induction *, FILE *, int));
204 static void record_giv PARAMS ((const struct loop *, struct induction *,
205 rtx, rtx, rtx, rtx, rtx, rtx, int,
206 enum g_types, int, int, rtx *));
207 static void update_giv_derive PARAMS ((const struct loop *, rtx));
208 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
209 struct loop_info *));
210 static int basic_induction_var PARAMS ((const struct loop *, rtx,
211 enum machine_mode, rtx, rtx,
212 rtx *, rtx *, rtx **));
213 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
214 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
215 rtx *, rtx *, rtx *, int, int *,
217 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
218 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
219 static int check_dbra_loop PARAMS ((struct loop *, int));
220 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
221 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
222 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
223 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
224 static int product_cheap_p PARAMS ((rtx, rtx));
225 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
227 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
228 struct iv_class *, int, rtx));
229 static int last_use_this_basic_block PARAMS ((rtx, rtx));
230 static void record_initial PARAMS ((rtx, rtx, void *));
231 static void update_reg_last_use PARAMS ((rtx, rtx));
232 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
233 static void loop_regs_scan PARAMS ((const struct loop*, int, int *));
234 static void load_mems PARAMS ((const struct loop *));
235 static int insert_loop_mem PARAMS ((rtx *, void *));
236 static int replace_loop_mem PARAMS ((rtx *, void *));
237 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
238 static int replace_loop_reg PARAMS ((rtx *, void *));
239 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
240 static void note_reg_stored PARAMS ((rtx, rtx, void *));
241 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
242 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
244 static int replace_label PARAMS ((rtx *, void *));
245 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
246 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
247 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
249 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
250 void debug_biv PARAMS ((const struct induction *));
251 void debug_giv PARAMS ((const struct induction *));
252 void debug_loop PARAMS ((const struct loop *));
253 void debug_loops PARAMS ((const struct loops *));
255 typedef struct rtx_pair
261 typedef struct loop_replace_args
268 /* Nonzero iff INSN is between START and END, inclusive. */
269 #define INSN_IN_RANGE_P(INSN, START, END) \
270 (INSN_UID (INSN) < max_uid_for_loop \
271 && INSN_LUID (INSN) >= INSN_LUID (START) \
272 && INSN_LUID (INSN) <= INSN_LUID (END))
274 /* Indirect_jump_in_function is computed once per function. */
275 static int indirect_jump_in_function;
276 static int indirect_jump_in_function_p PARAMS ((rtx));
278 static int compute_luids PARAMS ((rtx, rtx, int));
280 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
284 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
285 copy the value of the strength reduced giv to its original register. */
286 static int copy_cost;
288 /* Cost of using a register, to normalize the benefits of a giv. */
289 static int reg_address_cost;
294 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
296 reg_address_cost = address_cost (reg, SImode);
298 copy_cost = COSTS_N_INSNS (1);
301 /* Compute the mapping from uids to luids.
302 LUIDs are numbers assigned to insns, like uids,
303 except that luids increase monotonically through the code.
304 Start at insn START and stop just before END. Assign LUIDs
305 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
307 compute_luids (start, end, prev_luid)
314 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
316 if (INSN_UID (insn) >= max_uid_for_loop)
318 /* Don't assign luids to line-number NOTEs, so that the distance in
319 luids between two insns is not affected by -g. */
320 if (GET_CODE (insn) != NOTE
321 || NOTE_LINE_NUMBER (insn) <= 0)
322 uid_luid[INSN_UID (insn)] = ++i;
324 /* Give a line number note the same luid as preceding insn. */
325 uid_luid[INSN_UID (insn)] = i;
330 /* Entry point of this file. Perform loop optimization
331 on the current function. F is the first insn of the function
332 and DUMPFILE is a stream for output of a trace of actions taken
333 (or 0 if none should be output). */
336 loop_optimize (f, dumpfile, flags)
337 /* f is the first instruction of a chain of insns for one function */
344 struct loops loops_data;
345 struct loops *loops = &loops_data;
346 struct loop_info *loops_info;
348 loop_dump_stream = dumpfile;
350 init_recog_no_volatile ();
352 max_reg_before_loop = max_reg_num ();
353 loop_max_reg = max_reg_before_loop;
357 /* Count the number of loops. */
360 for (insn = f; insn; insn = NEXT_INSN (insn))
362 if (GET_CODE (insn) == NOTE
363 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
367 /* Don't waste time if no loops. */
368 if (max_loop_num == 0)
371 loops->num = max_loop_num;
373 /* Get size to use for tables indexed by uids.
374 Leave some space for labels allocated by find_and_verify_loops. */
375 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
377 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
378 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
379 sizeof (struct loop *));
381 /* Allocate storage for array of loops. */
382 loops->array = (struct loop *)
383 xcalloc (loops->num, sizeof (struct loop));
385 /* Find and process each loop.
386 First, find them, and record them in order of their beginnings. */
387 find_and_verify_loops (f, loops);
389 /* Allocate and initialize auxiliary loop information. */
390 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
391 for (i = 0; i < loops->num; i++)
392 loops->array[i].aux = loops_info + i;
394 /* Now find all register lifetimes. This must be done after
395 find_and_verify_loops, because it might reorder the insns in the
397 reg_scan (f, max_reg_before_loop, 1);
399 /* This must occur after reg_scan so that registers created by gcse
400 will have entries in the register tables.
402 We could have added a call to reg_scan after gcse_main in toplev.c,
403 but moving this call to init_alias_analysis is more efficient. */
404 init_alias_analysis ();
406 /* See if we went too far. Note that get_max_uid already returns
407 one more that the maximum uid of all insn. */
408 if (get_max_uid () > max_uid_for_loop)
410 /* Now reset it to the actual size we need. See above. */
411 max_uid_for_loop = get_max_uid ();
413 /* find_and_verify_loops has already called compute_luids, but it
414 might have rearranged code afterwards, so we need to recompute
416 max_luid = compute_luids (f, NULL_RTX, 0);
418 /* Don't leave gaps in uid_luid for insns that have been
419 deleted. It is possible that the first or last insn
420 using some register has been deleted by cross-jumping.
421 Make sure that uid_luid for that former insn's uid
422 points to the general area where that insn used to be. */
423 for (i = 0; i < max_uid_for_loop; i++)
425 uid_luid[0] = uid_luid[i];
426 if (uid_luid[0] != 0)
429 for (i = 0; i < max_uid_for_loop; i++)
430 if (uid_luid[i] == 0)
431 uid_luid[i] = uid_luid[i - 1];
433 /* Determine if the function has indirect jump. On some systems
434 this prevents low overhead loop instructions from being used. */
435 indirect_jump_in_function = indirect_jump_in_function_p (f);
437 /* Now scan the loops, last ones first, since this means inner ones are done
438 before outer ones. */
439 for (i = max_loop_num - 1; i >= 0; i--)
441 struct loop *loop = &loops->array[i];
443 if (! loop->invalid && loop->end)
444 scan_loop (loop, flags);
447 /* If there were lexical blocks inside the loop, they have been
448 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
449 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
450 the BLOCKs as well. */
451 if (write_symbols != NO_DEBUG)
454 end_alias_analysis ();
463 /* Returns the next insn, in execution order, after INSN. START and
464 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
465 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
466 insn-stream; it is used with loops that are entered near the
470 next_insn_in_loop (loop, insn)
471 const struct loop *loop;
474 insn = NEXT_INSN (insn);
476 if (insn == loop->end)
479 /* Go to the top of the loop, and continue there. */
486 if (insn == loop->scan_start)
493 /* Optimize one loop described by LOOP. */
495 /* ??? Could also move memory writes out of loops if the destination address
496 is invariant, the source is invariant, the memory write is not volatile,
497 and if we can prove that no read inside the loop can read this address
498 before the write occurs. If there is a read of this address after the
499 write, then we can also mark the memory read as invariant. */
502 scan_loop (loop, flags)
506 struct loop_info *loop_info = LOOP_INFO (loop);
507 struct loop_regs *regs = LOOP_REGS (loop);
509 rtx loop_start = loop->start;
510 rtx loop_end = loop->end;
512 /* 1 if we are scanning insns that could be executed zero times. */
514 /* 1 if we are scanning insns that might never be executed
515 due to a subroutine call which might exit before they are reached. */
517 /* Jump insn that enters the loop, or 0 if control drops in. */
518 rtx loop_entry_jump = 0;
519 /* Number of insns in the loop. */
522 rtx temp, update_start, update_end;
523 /* The SET from an insn, if it is the only SET in the insn. */
525 /* Chain describing insns movable in current loop. */
526 struct loop_movables *movables = LOOP_MOVABLES (loop);
527 /* Ratio of extra register life span we can justify
528 for saving an instruction. More if loop doesn't call subroutines
529 since in that case saving an insn makes more difference
530 and more registers are available. */
532 /* Nonzero if we are scanning instructions in a sub-loop. */
541 /* Determine whether this loop starts with a jump down to a test at
542 the end. This will occur for a small number of loops with a test
543 that is too complex to duplicate in front of the loop.
545 We search for the first insn or label in the loop, skipping NOTEs.
546 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
547 (because we might have a loop executed only once that contains a
548 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
549 (in case we have a degenerate loop).
551 Note that if we mistakenly think that a loop is entered at the top
552 when, in fact, it is entered at the exit test, the only effect will be
553 slightly poorer optimization. Making the opposite error can generate
554 incorrect code. Since very few loops now start with a jump to the
555 exit test, the code here to detect that case is very conservative. */
557 for (p = NEXT_INSN (loop_start);
559 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
560 && (GET_CODE (p) != NOTE
561 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
562 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
566 loop->scan_start = p;
568 /* Set up variables describing this loop. */
570 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
572 /* If loop has a jump before the first label,
573 the true entry is the target of that jump.
574 Start scan from there.
575 But record in LOOP->TOP the place where the end-test jumps
576 back to so we can scan that after the end of the loop. */
577 if (GET_CODE (p) == JUMP_INSN)
581 /* Loop entry must be unconditional jump (and not a RETURN) */
582 if (any_uncondjump_p (p)
583 && JUMP_LABEL (p) != 0
584 /* Check to see whether the jump actually
585 jumps out of the loop (meaning it's no loop).
586 This case can happen for things like
587 do {..} while (0). If this label was generated previously
588 by loop, we can't tell anything about it and have to reject
590 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
592 loop->top = next_label (loop->scan_start);
593 loop->scan_start = JUMP_LABEL (p);
597 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
598 as required by loop_reg_used_before_p. So skip such loops. (This
599 test may never be true, but it's best to play it safe.)
601 Also, skip loops where we do not start scanning at a label. This
602 test also rejects loops starting with a JUMP_INSN that failed the
605 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
606 || GET_CODE (loop->scan_start) != CODE_LABEL)
608 if (loop_dump_stream)
609 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
610 INSN_UID (loop_start), INSN_UID (loop_end));
614 /* Allocate extra space for REGs that might be created by load_mems.
615 We allocate a little extra slop as well, in the hopes that we
616 won't have to reallocate the regs array. */
617 loop_regs_scan (loop, loop_info->mems_idx + 16, &insn_count);
619 if (loop_dump_stream)
621 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
622 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
624 fprintf (loop_dump_stream, "Continue at insn %d.\n",
625 INSN_UID (loop->cont));
628 /* Scan through the loop finding insns that are safe to move.
629 Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
630 this reg will be considered invariant for subsequent insns.
631 We consider whether subsequent insns use the reg
632 in deciding whether it is worth actually moving.
634 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
635 and therefore it is possible that the insns we are scanning
636 would never be executed. At such times, we must make sure
637 that it is safe to execute the insn once instead of zero times.
638 When MAYBE_NEVER is 0, all insns will be executed at least once
639 so that is not a problem. */
641 for (p = next_insn_in_loop (loop, loop->scan_start);
643 p = next_insn_in_loop (loop, p))
645 if (GET_CODE (p) == INSN
646 && (set = single_set (p))
647 && GET_CODE (SET_DEST (set)) == REG
648 && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
653 rtx src = SET_SRC (set);
654 rtx dependencies = 0;
656 /* Figure out what to use as a source of this insn. If a REG_EQUIV
657 note is given or if a REG_EQUAL note with a constant operand is
658 specified, use it as the source and mark that we should move
659 this insn by calling emit_move_insn rather that duplicating the
662 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
664 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
666 src = XEXP (temp, 0), move_insn = 1;
669 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
670 if (temp && CONSTANT_P (XEXP (temp, 0)))
671 src = XEXP (temp, 0), move_insn = 1;
672 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
674 src = XEXP (temp, 0);
675 /* A libcall block can use regs that don't appear in
676 the equivalent expression. To move the libcall,
677 we must move those regs too. */
678 dependencies = libcall_other_reg (p, src);
682 /* Don't try to optimize a register that was made
683 by loop-optimization for an inner loop.
684 We don't know its life-span, so we can't compute the benefit. */
685 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
687 else if (/* The register is used in basic blocks other
688 than the one where it is set (meaning that
689 something after this point in the loop might
690 depend on its value before the set). */
691 ! reg_in_basic_block_p (p, SET_DEST (set))
692 /* And the set is not guaranteed to be executed one
693 the loop starts, or the value before the set is
694 needed before the set occurs...
696 ??? Note we have quadratic behaviour here, mitigated
697 by the fact that the previous test will often fail for
698 large loops. Rather than re-scanning the entire loop
699 each time for register usage, we should build tables
700 of the register usage and use them here instead. */
702 || loop_reg_used_before_p (loop, set, p)))
703 /* It is unsafe to move the set.
705 This code used to consider it OK to move a set of a variable
706 which was not created by the user and not used in an exit test.
707 That behavior is incorrect and was removed. */
709 else if ((tem = loop_invariant_p (loop, src))
710 && (dependencies == 0
711 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
712 && (regs->array[REGNO (SET_DEST (set))].set_in_loop == 1
714 = consec_sets_invariant_p
715 (loop, SET_DEST (set),
716 regs->array[REGNO (SET_DEST (set))].set_in_loop,
718 /* If the insn can cause a trap (such as divide by zero),
719 can't move it unless it's guaranteed to be executed
720 once loop is entered. Even a function call might
721 prevent the trap insn from being reached
722 (since it might exit!) */
723 && ! ((maybe_never || call_passed)
724 && may_trap_p (src)))
726 register struct movable *m;
727 register int regno = REGNO (SET_DEST (set));
729 /* A potential lossage is where we have a case where two insns
730 can be combined as long as they are both in the loop, but
731 we move one of them outside the loop. For large loops,
732 this can lose. The most common case of this is the address
733 of a function being called.
735 Therefore, if this register is marked as being used exactly
736 once if we are in a loop with calls (a "large loop"), see if
737 we can replace the usage of this register with the source
738 of this SET. If we can, delete this insn.
740 Don't do this if P has a REG_RETVAL note or if we have
741 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
743 if (loop_info->has_call
744 && regs->array[regno].single_usage != 0
745 && regs->array[regno].single_usage != const0_rtx
746 && REGNO_FIRST_UID (regno) == INSN_UID (p)
747 && (REGNO_LAST_UID (regno)
748 == INSN_UID (regs->array[regno].single_usage))
749 && regs->array[regno].set_in_loop == 1
750 && ! side_effects_p (SET_SRC (set))
751 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
752 && (! SMALL_REGISTER_CLASSES
753 || (! (GET_CODE (SET_SRC (set)) == REG
754 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
755 /* This test is not redundant; SET_SRC (set) might be
756 a call-clobbered register and the life of REGNO
757 might span a call. */
758 && ! modified_between_p (SET_SRC (set), p,
759 regs->array[regno].single_usage)
760 && no_labels_between_p (p, regs->array[regno].single_usage)
761 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
762 regs->array[regno].single_usage))
764 /* Replace any usage in a REG_EQUAL note. Must copy the
765 new source, so that we don't get rtx sharing between the
766 SET_SOURCE and REG_NOTES of insn p. */
767 REG_NOTES (regs->array[regno].single_usage)
768 = replace_rtx (REG_NOTES (regs->array[regno].single_usage),
769 SET_DEST (set), copy_rtx (SET_SRC (set)));
772 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
773 NOTE_SOURCE_FILE (p) = 0;
774 regs->array[regno].set_in_loop = 0;
778 m = (struct movable *) xmalloc (sizeof (struct movable));
782 m->dependencies = dependencies;
783 m->set_dest = SET_DEST (set);
785 m->consec = regs->array[REGNO (SET_DEST (set))].set_in_loop - 1;
789 m->move_insn = move_insn;
790 m->move_insn_first = 0;
791 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
792 m->savemode = VOIDmode;
794 /* Set M->cond if either loop_invariant_p
795 or consec_sets_invariant_p returned 2
796 (only conditionally invariant). */
797 m->cond = ((tem | tem1 | tem2) > 1);
798 m->global = LOOP_REG_GLOBAL_P (loop, regno);
800 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
801 m->savings = regs->array[regno].n_times_set;
802 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
803 m->savings += libcall_benefit (p);
804 regs->array[regno].set_in_loop = move_insn ? -2 : -1;
805 /* Add M to the end of the chain MOVABLES. */
806 loop_movables_add (movables, m);
810 /* It is possible for the first instruction to have a
811 REG_EQUAL note but a non-invariant SET_SRC, so we must
812 remember the status of the first instruction in case
813 the last instruction doesn't have a REG_EQUAL note. */
814 m->move_insn_first = m->move_insn;
816 /* Skip this insn, not checking REG_LIBCALL notes. */
817 p = next_nonnote_insn (p);
818 /* Skip the consecutive insns, if there are any. */
819 p = skip_consec_insns (p, m->consec);
820 /* Back up to the last insn of the consecutive group. */
821 p = prev_nonnote_insn (p);
823 /* We must now reset m->move_insn, m->is_equiv, and possibly
824 m->set_src to correspond to the effects of all the
826 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
828 m->set_src = XEXP (temp, 0), m->move_insn = 1;
831 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
832 if (temp && CONSTANT_P (XEXP (temp, 0)))
833 m->set_src = XEXP (temp, 0), m->move_insn = 1;
838 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
841 /* If this register is always set within a STRICT_LOW_PART
842 or set to zero, then its high bytes are constant.
843 So clear them outside the loop and within the loop
844 just load the low bytes.
845 We must check that the machine has an instruction to do so.
846 Also, if the value loaded into the register
847 depends on the same register, this cannot be done. */
848 else if (SET_SRC (set) == const0_rtx
849 && GET_CODE (NEXT_INSN (p)) == INSN
850 && (set1 = single_set (NEXT_INSN (p)))
851 && GET_CODE (set1) == SET
852 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
853 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
854 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
856 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
858 register int regno = REGNO (SET_DEST (set));
859 if (regs->array[regno].set_in_loop == 2)
861 register struct movable *m;
862 m = (struct movable *) xmalloc (sizeof (struct movable));
865 m->set_dest = SET_DEST (set);
872 m->move_insn_first = 0;
874 /* If the insn may not be executed on some cycles,
875 we can't clear the whole reg; clear just high part.
876 Not even if the reg is used only within this loop.
883 Clearing x before the inner loop could clobber a value
884 being saved from the last time around the outer loop.
885 However, if the reg is not used outside this loop
886 and all uses of the register are in the same
887 basic block as the store, there is no problem.
889 If this insn was made by loop, we don't know its
890 INSN_LUID and hence must make a conservative
892 m->global = (INSN_UID (p) >= max_uid_for_loop
893 || LOOP_REG_GLOBAL_P (loop, regno)
894 || (labels_in_range_p
895 (p, REGNO_FIRST_LUID (regno))));
896 if (maybe_never && m->global)
897 m->savemode = GET_MODE (SET_SRC (set1));
899 m->savemode = VOIDmode;
903 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
905 regs->array[regno].set_in_loop = -1;
906 /* Add M to the end of the chain MOVABLES. */
907 loop_movables_add (movables, m);
911 /* Past a call insn, we get to insns which might not be executed
912 because the call might exit. This matters for insns that trap.
913 Constant and pure call insns always return, so they don't count. */
914 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
916 /* Past a label or a jump, we get to insns for which we
917 can't count on whether or how many times they will be
918 executed during each iteration. Therefore, we can
919 only move out sets of trivial variables
920 (those not used after the loop). */
921 /* Similar code appears twice in strength_reduce. */
922 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
923 /* If we enter the loop in the middle, and scan around to the
924 beginning, don't set maybe_never for that. This must be an
925 unconditional jump, otherwise the code at the top of the
926 loop might never be executed. Unconditional jumps are
927 followed a by barrier then loop end. */
928 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
929 && NEXT_INSN (NEXT_INSN (p)) == loop_end
930 && any_uncondjump_p (p)))
932 else if (GET_CODE (p) == NOTE)
934 /* At the virtual top of a converted loop, insns are again known to
935 be executed: logically, the loop begins here even though the exit
936 code has been duplicated. */
937 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
938 maybe_never = call_passed = 0;
939 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
941 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
946 /* If one movable subsumes another, ignore that other. */
948 ignore_some_movables (movables);
950 /* For each movable insn, see if the reg that it loads
951 leads when it dies right into another conditionally movable insn.
952 If so, record that the second insn "forces" the first one,
953 since the second can be moved only if the first is. */
955 force_movables (movables);
957 /* See if there are multiple movable insns that load the same value.
958 If there are, make all but the first point at the first one
959 through the `match' field, and add the priorities of them
960 all together as the priority of the first. */
962 combine_movables (movables, regs);
964 /* Now consider each movable insn to decide whether it is worth moving.
965 Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
967 Generally this increases code size, so do not move moveables when
968 optimizing for code size. */
971 move_movables (loop, movables, threshold, insn_count);
973 /* Now candidates that still are negative are those not moved.
974 Change regs->array[I].set_in_loop to indicate that those are not actually
976 for (i = 0; i < regs->num; i++)
977 if (regs->array[i].set_in_loop < 0)
978 regs->array[i].set_in_loop = regs->array[i].n_times_set;
980 /* Now that we've moved some things out of the loop, we might be able to
981 hoist even more memory references. */
984 /* Recalculate regs->array if load_mems has created new registers. */
985 if (max_reg_num () > regs->num)
986 loop_regs_scan (loop, 0, &insn_count);
988 for (update_start = loop_start;
989 PREV_INSN (update_start)
990 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
991 update_start = PREV_INSN (update_start))
993 update_end = NEXT_INSN (loop_end);
995 reg_scan_update (update_start, update_end, loop_max_reg);
996 loop_max_reg = max_reg_num ();
998 if (flag_strength_reduce)
1000 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1001 /* Ensure our label doesn't go away. */
1002 LABEL_NUSES (update_end)++;
1004 strength_reduce (loop, insn_count, flags);
1006 reg_scan_update (update_start, update_end, loop_max_reg);
1007 loop_max_reg = max_reg_num ();
1009 if (update_end && GET_CODE (update_end) == CODE_LABEL
1010 && --LABEL_NUSES (update_end) == 0)
1011 delete_insn (update_end);
1015 /* The movable information is required for strength reduction. */
1016 loop_movables_free (movables);
1023 /* Add elements to *OUTPUT to record all the pseudo-regs
1024 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1027 record_excess_regs (in_this, not_in_this, output)
1028 rtx in_this, not_in_this;
1035 code = GET_CODE (in_this);
1049 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1050 && ! reg_mentioned_p (in_this, not_in_this))
1051 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1058 fmt = GET_RTX_FORMAT (code);
1059 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1066 for (j = 0; j < XVECLEN (in_this, i); j++)
1067 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1071 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1077 /* Check what regs are referred to in the libcall block ending with INSN,
1078 aside from those mentioned in the equivalent value.
1079 If there are none, return 0.
1080 If there are one or more, return an EXPR_LIST containing all of them. */
1083 libcall_other_reg (insn, equiv)
1086 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1087 rtx p = XEXP (note, 0);
1090 /* First, find all the regs used in the libcall block
1091 that are not mentioned as inputs to the result. */
1095 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1096 || GET_CODE (p) == CALL_INSN)
1097 record_excess_regs (PATTERN (p), equiv, &output);
1104 /* Return 1 if all uses of REG
1105 are between INSN and the end of the basic block. */
1108 reg_in_basic_block_p (insn, reg)
1111 int regno = REGNO (reg);
1114 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1117 /* Search this basic block for the already recorded last use of the reg. */
1118 for (p = insn; p; p = NEXT_INSN (p))
1120 switch (GET_CODE (p))
1127 /* Ordinary insn: if this is the last use, we win. */
1128 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1133 /* Jump insn: if this is the last use, we win. */
1134 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1136 /* Otherwise, it's the end of the basic block, so we lose. */
1141 /* It's the end of the basic block, so we lose. */
1149 /* The "last use" that was recorded can't be found after the first
1150 use. This can happen when the last use was deleted while
1151 processing an inner loop, this inner loop was then completely
1152 unrolled, and the outer loop is always exited after the inner loop,
1153 so that everything after the first use becomes a single basic block. */
1157 /* Compute the benefit of eliminating the insns in the block whose
1158 last insn is LAST. This may be a group of insns used to compute a
1159 value directly or can contain a library call. */
1162 libcall_benefit (last)
1168 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1169 insn != last; insn = NEXT_INSN (insn))
1171 if (GET_CODE (insn) == CALL_INSN)
1172 benefit += 10; /* Assume at least this many insns in a library
1174 else if (GET_CODE (insn) == INSN
1175 && GET_CODE (PATTERN (insn)) != USE
1176 && GET_CODE (PATTERN (insn)) != CLOBBER)
1183 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1186 skip_consec_insns (insn, count)
1190 for (; count > 0; count--)
1194 /* If first insn of libcall sequence, skip to end. */
1195 /* Do this at start of loop, since INSN is guaranteed to
1197 if (GET_CODE (insn) != NOTE
1198 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1199 insn = XEXP (temp, 0);
1202 insn = NEXT_INSN (insn);
1203 while (GET_CODE (insn) == NOTE);
1209 /* Ignore any movable whose insn falls within a libcall
1210 which is part of another movable.
1211 We make use of the fact that the movable for the libcall value
1212 was made later and so appears later on the chain. */
1215 ignore_some_movables (movables)
1216 struct loop_movables *movables;
1218 register struct movable *m, *m1;
1220 for (m = movables->head; m; m = m->next)
1222 /* Is this a movable for the value of a libcall? */
1223 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1227 /* Check for earlier movables inside that range,
1228 and mark them invalid. We cannot use LUIDs here because
1229 insns created by loop.c for prior loops don't have LUIDs.
1230 Rather than reject all such insns from movables, we just
1231 explicitly check each insn in the libcall (since invariant
1232 libcalls aren't that common). */
1233 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1234 for (m1 = movables->head; m1 != m; m1 = m1->next)
1235 if (m1->insn == insn)
1241 /* For each movable insn, see if the reg that it loads
1242 leads when it dies right into another conditionally movable insn.
1243 If so, record that the second insn "forces" the first one,
1244 since the second can be moved only if the first is. */
1247 force_movables (movables)
1248 struct loop_movables *movables;
1250 register struct movable *m, *m1;
1251 for (m1 = movables->head; m1; m1 = m1->next)
1252 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1253 if (!m1->partial && !m1->done)
1255 int regno = m1->regno;
1256 for (m = m1->next; m; m = m->next)
1257 /* ??? Could this be a bug? What if CSE caused the
1258 register of M1 to be used after this insn?
1259 Since CSE does not update regno_last_uid,
1260 this insn M->insn might not be where it dies.
1261 But very likely this doesn't matter; what matters is
1262 that M's reg is computed from M1's reg. */
1263 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1266 if (m != 0 && m->set_src == m1->set_dest
1267 /* If m->consec, m->set_src isn't valid. */
1271 /* Increase the priority of the moving the first insn
1272 since it permits the second to be moved as well. */
1276 m1->lifetime += m->lifetime;
1277 m1->savings += m->savings;
1282 /* Find invariant expressions that are equal and can be combined into
1286 combine_movables (movables, regs)
1287 struct loop_movables *movables;
1288 struct loop_regs *regs;
1290 register struct movable *m;
1291 char *matched_regs = (char *) xmalloc (regs->num);
1292 enum machine_mode mode;
1294 /* Regs that are set more than once are not allowed to match
1295 or be matched. I'm no longer sure why not. */
1296 /* Perhaps testing m->consec_sets would be more appropriate here? */
1298 for (m = movables->head; m; m = m->next)
1299 if (m->match == 0 && regs->array[m->regno].n_times_set == 1
1302 register struct movable *m1;
1303 int regno = m->regno;
1305 memset (matched_regs, 0, regs->num);
1306 matched_regs[regno] = 1;
1308 /* We want later insns to match the first one. Don't make the first
1309 one match any later ones. So start this loop at m->next. */
1310 for (m1 = m->next; m1; m1 = m1->next)
1311 if (m != m1 && m1->match == 0
1312 && regs->array[m1->regno].n_times_set == 1
1313 /* A reg used outside the loop mustn't be eliminated. */
1315 /* A reg used for zero-extending mustn't be eliminated. */
1317 && (matched_regs[m1->regno]
1320 /* Can combine regs with different modes loaded from the
1321 same constant only if the modes are the same or
1322 if both are integer modes with M wider or the same
1323 width as M1. The check for integer is redundant, but
1324 safe, since the only case of differing destination
1325 modes with equal sources is when both sources are
1326 VOIDmode, i.e., CONST_INT. */
1327 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1328 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1329 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1330 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1331 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1332 /* See if the source of M1 says it matches M. */
1333 && ((GET_CODE (m1->set_src) == REG
1334 && matched_regs[REGNO (m1->set_src)])
1335 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1337 && ((m->dependencies == m1->dependencies)
1338 || rtx_equal_p (m->dependencies, m1->dependencies)))
1340 m->lifetime += m1->lifetime;
1341 m->savings += m1->savings;
1344 matched_regs[m1->regno] = 1;
1348 /* Now combine the regs used for zero-extension.
1349 This can be done for those not marked `global'
1350 provided their lives don't overlap. */
1352 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1353 mode = GET_MODE_WIDER_MODE (mode))
1355 register struct movable *m0 = 0;
1357 /* Combine all the registers for extension from mode MODE.
1358 Don't combine any that are used outside this loop. */
1359 for (m = movables->head; m; m = m->next)
1360 if (m->partial && ! m->global
1361 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1363 register struct movable *m1;
1364 int first = REGNO_FIRST_LUID (m->regno);
1365 int last = REGNO_LAST_LUID (m->regno);
1369 /* First one: don't check for overlap, just record it. */
1374 /* Make sure they extend to the same mode.
1375 (Almost always true.) */
1376 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1379 /* We already have one: check for overlap with those
1380 already combined together. */
1381 for (m1 = movables->head; m1 != m; m1 = m1->next)
1382 if (m1 == m0 || (m1->partial && m1->match == m0))
1383 if (! (REGNO_FIRST_LUID (m1->regno) > last
1384 || REGNO_LAST_LUID (m1->regno) < first))
1387 /* No overlap: we can combine this with the others. */
1388 m0->lifetime += m->lifetime;
1389 m0->savings += m->savings;
1399 free (matched_regs);
1402 /* Return 1 if regs X and Y will become the same if moved. */
1405 regs_match_p (x, y, movables)
1407 struct loop_movables *movables;
1409 unsigned int xn = REGNO (x);
1410 unsigned int yn = REGNO (y);
1411 struct movable *mx, *my;
1413 for (mx = movables->head; mx; mx = mx->next)
1414 if (mx->regno == xn)
1417 for (my = movables->head; my; my = my->next)
1418 if (my->regno == yn)
1422 && ((mx->match == my->match && mx->match != 0)
1424 || mx == my->match));
1427 /* Return 1 if X and Y are identical-looking rtx's.
1428 This is the Lisp function EQUAL for rtx arguments.
1430 If two registers are matching movables or a movable register and an
1431 equivalent constant, consider them equal. */
1434 rtx_equal_for_loop_p (x, y, movables, regs)
1436 struct loop_movables *movables;
1437 struct loop_regs *regs;
1441 register struct movable *m;
1442 register enum rtx_code code;
1443 register const char *fmt;
1447 if (x == 0 || y == 0)
1450 code = GET_CODE (x);
1452 /* If we have a register and a constant, they may sometimes be
1454 if (GET_CODE (x) == REG && regs->array[REGNO (x)].set_in_loop == -2
1457 for (m = movables->head; m; m = m->next)
1458 if (m->move_insn && m->regno == REGNO (x)
1459 && rtx_equal_p (m->set_src, y))
1462 else if (GET_CODE (y) == REG && regs->array[REGNO (y)].set_in_loop == -2
1465 for (m = movables->head; m; m = m->next)
1466 if (m->move_insn && m->regno == REGNO (y)
1467 && rtx_equal_p (m->set_src, x))
1471 /* Otherwise, rtx's of different codes cannot be equal. */
1472 if (code != GET_CODE (y))
1475 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1476 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1478 if (GET_MODE (x) != GET_MODE (y))
1481 /* These three types of rtx's can be compared nonrecursively. */
1483 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1485 if (code == LABEL_REF)
1486 return XEXP (x, 0) == XEXP (y, 0);
1487 if (code == SYMBOL_REF)
1488 return XSTR (x, 0) == XSTR (y, 0);
1490 /* Compare the elements. If any pair of corresponding elements
1491 fail to match, return 0 for the whole things. */
1493 fmt = GET_RTX_FORMAT (code);
1494 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1499 if (XWINT (x, i) != XWINT (y, i))
1504 if (XINT (x, i) != XINT (y, i))
1509 /* Two vectors must have the same length. */
1510 if (XVECLEN (x, i) != XVECLEN (y, i))
1513 /* And the corresponding elements must match. */
1514 for (j = 0; j < XVECLEN (x, i); j++)
1515 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1516 movables, regs) == 0)
1521 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1527 if (strcmp (XSTR (x, i), XSTR (y, i)))
1532 /* These are just backpointers, so they don't matter. */
1538 /* It is believed that rtx's at this level will never
1539 contain anything but integers and other rtx's,
1540 except for within LABEL_REFs and SYMBOL_REFs. */
1548 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1549 insns in INSNS which use the reference. LABEL_NUSES for CODE_LABEL
1550 references is incremented once for each added note. */
1553 add_label_notes (x, insns)
1557 enum rtx_code code = GET_CODE (x);
1562 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1564 /* This code used to ignore labels that referred to dispatch tables to
1565 avoid flow generating (slighly) worse code.
1567 We no longer ignore such label references (see LABEL_REF handling in
1568 mark_jump_label for additional information). */
1569 for (insn = insns; insn; insn = NEXT_INSN (insn))
1570 if (reg_mentioned_p (XEXP (x, 0), insn))
1572 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1574 if (LABEL_P (XEXP (x, 0)))
1575 LABEL_NUSES (XEXP (x, 0))++;
1579 fmt = GET_RTX_FORMAT (code);
1580 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1583 add_label_notes (XEXP (x, i), insns);
1584 else if (fmt[i] == 'E')
1585 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1586 add_label_notes (XVECEXP (x, i, j), insns);
1590 /* Scan MOVABLES, and move the insns that deserve to be moved.
1591 If two matching movables are combined, replace one reg with the
1592 other throughout. */
1595 move_movables (loop, movables, threshold, insn_count)
1597 struct loop_movables *movables;
1601 struct loop_regs *regs = LOOP_REGS (loop);
1602 int nregs = regs->num;
1604 register struct movable *m;
1606 rtx loop_start = loop->start;
1607 rtx loop_end = loop->end;
1608 /* Map of pseudo-register replacements to handle combining
1609 when we move several insns that load the same value
1610 into different pseudo-registers. */
1611 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1612 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1616 for (m = movables->head; m; m = m->next)
1618 /* Describe this movable insn. */
1620 if (loop_dump_stream)
1622 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1623 INSN_UID (m->insn), m->regno, m->lifetime);
1625 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1627 fprintf (loop_dump_stream, "cond ");
1629 fprintf (loop_dump_stream, "force ");
1631 fprintf (loop_dump_stream, "global ");
1633 fprintf (loop_dump_stream, "done ");
1635 fprintf (loop_dump_stream, "move-insn ");
1637 fprintf (loop_dump_stream, "matches %d ",
1638 INSN_UID (m->match->insn));
1640 fprintf (loop_dump_stream, "forces %d ",
1641 INSN_UID (m->forces->insn));
1644 /* Count movables. Value used in heuristics in strength_reduce. */
1647 /* Ignore the insn if it's already done (it matched something else).
1648 Otherwise, see if it is now safe to move. */
1652 || (1 == loop_invariant_p (loop, m->set_src)
1653 && (m->dependencies == 0
1654 || 1 == loop_invariant_p (loop, m->dependencies))
1656 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1659 && (! m->forces || m->forces->done))
1663 int savings = m->savings;
1665 /* We have an insn that is safe to move.
1666 Compute its desirability. */
1671 if (loop_dump_stream)
1672 fprintf (loop_dump_stream, "savings %d ", savings);
1674 if (regs->array[regno].moved_once && loop_dump_stream)
1675 fprintf (loop_dump_stream, "halved since already moved ");
1677 /* An insn MUST be moved if we already moved something else
1678 which is safe only if this one is moved too: that is,
1679 if already_moved[REGNO] is nonzero. */
1681 /* An insn is desirable to move if the new lifetime of the
1682 register is no more than THRESHOLD times the old lifetime.
1683 If it's not desirable, it means the loop is so big
1684 that moving won't speed things up much,
1685 and it is liable to make register usage worse. */
1687 /* It is also desirable to move if it can be moved at no
1688 extra cost because something else was already moved. */
1690 if (already_moved[regno]
1691 || flag_move_all_movables
1692 || (threshold * savings * m->lifetime) >=
1693 (regs->array[regno].moved_once ? insn_count * 2 : insn_count)
1694 || (m->forces && m->forces->done
1695 && regs->array[m->forces->regno].n_times_set == 1))
1698 register struct movable *m1;
1699 rtx first = NULL_RTX;
1701 /* Now move the insns that set the reg. */
1703 if (m->partial && m->match)
1707 /* Find the end of this chain of matching regs.
1708 Thus, we load each reg in the chain from that one reg.
1709 And that reg is loaded with 0 directly,
1710 since it has ->match == 0. */
1711 for (m1 = m; m1->match; m1 = m1->match);
1712 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1713 SET_DEST (PATTERN (m1->insn)));
1714 i1 = emit_insn_before (newpat, loop_start);
1716 /* Mark the moved, invariant reg as being allowed to
1717 share a hard reg with the other matching invariant. */
1718 REG_NOTES (i1) = REG_NOTES (m->insn);
1719 r1 = SET_DEST (PATTERN (m->insn));
1720 r2 = SET_DEST (PATTERN (m1->insn));
1722 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1723 gen_rtx_EXPR_LIST (VOIDmode, r2,
1725 delete_insn (m->insn);
1730 if (loop_dump_stream)
1731 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1733 /* If we are to re-generate the item being moved with a
1734 new move insn, first delete what we have and then emit
1735 the move insn before the loop. */
1736 else if (m->move_insn)
1740 for (count = m->consec; count >= 0; count--)
1742 /* If this is the first insn of a library call sequence,
1744 if (GET_CODE (p) != NOTE
1745 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1748 /* If this is the last insn of a libcall sequence, then
1749 delete every insn in the sequence except the last.
1750 The last insn is handled in the normal manner. */
1751 if (GET_CODE (p) != NOTE
1752 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1754 temp = XEXP (temp, 0);
1756 temp = delete_insn (temp);
1760 p = delete_insn (p);
1762 /* simplify_giv_expr expects that it can walk the insns
1763 at m->insn forwards and see this old sequence we are
1764 tossing here. delete_insn does preserve the next
1765 pointers, but when we skip over a NOTE we must fix
1766 it up. Otherwise that code walks into the non-deleted
1768 while (p && GET_CODE (p) == NOTE)
1769 p = NEXT_INSN (temp) = NEXT_INSN (p);
1773 emit_move_insn (m->set_dest, m->set_src);
1774 temp = get_insns ();
1777 add_label_notes (m->set_src, temp);
1779 i1 = emit_insns_before (temp, loop_start);
1780 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1782 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1783 m->set_src, REG_NOTES (i1));
1785 if (loop_dump_stream)
1786 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1788 /* The more regs we move, the less we like moving them. */
1793 for (count = m->consec; count >= 0; count--)
1797 /* If first insn of libcall sequence, skip to end. */
1798 /* Do this at start of loop, since p is guaranteed to
1800 if (GET_CODE (p) != NOTE
1801 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1804 /* If last insn of libcall sequence, move all
1805 insns except the last before the loop. The last
1806 insn is handled in the normal manner. */
1807 if (GET_CODE (p) != NOTE
1808 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1812 rtx fn_address_insn = 0;
1815 for (temp = XEXP (temp, 0); temp != p;
1816 temp = NEXT_INSN (temp))
1822 if (GET_CODE (temp) == NOTE)
1825 body = PATTERN (temp);
1827 /* Find the next insn after TEMP,
1828 not counting USE or NOTE insns. */
1829 for (next = NEXT_INSN (temp); next != p;
1830 next = NEXT_INSN (next))
1831 if (! (GET_CODE (next) == INSN
1832 && GET_CODE (PATTERN (next)) == USE)
1833 && GET_CODE (next) != NOTE)
1836 /* If that is the call, this may be the insn
1837 that loads the function address.
1839 Extract the function address from the insn
1840 that loads it into a register.
1841 If this insn was cse'd, we get incorrect code.
1843 So emit a new move insn that copies the
1844 function address into the register that the
1845 call insn will use. flow.c will delete any
1846 redundant stores that we have created. */
1847 if (GET_CODE (next) == CALL_INSN
1848 && GET_CODE (body) == SET
1849 && GET_CODE (SET_DEST (body)) == REG
1850 && (n = find_reg_note (temp, REG_EQUAL,
1853 fn_reg = SET_SRC (body);
1854 if (GET_CODE (fn_reg) != REG)
1855 fn_reg = SET_DEST (body);
1856 fn_address = XEXP (n, 0);
1857 fn_address_insn = temp;
1859 /* We have the call insn.
1860 If it uses the register we suspect it might,
1861 load it with the correct address directly. */
1862 if (GET_CODE (temp) == CALL_INSN
1864 && reg_referenced_p (fn_reg, body))
1865 emit_insn_after (gen_move_insn (fn_reg,
1869 if (GET_CODE (temp) == CALL_INSN)
1871 i1 = emit_call_insn_before (body, loop_start);
1872 /* Because the USAGE information potentially
1873 contains objects other than hard registers
1874 we need to copy it. */
1875 if (CALL_INSN_FUNCTION_USAGE (temp))
1876 CALL_INSN_FUNCTION_USAGE (i1)
1877 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1880 i1 = emit_insn_before (body, loop_start);
1883 if (temp == fn_address_insn)
1884 fn_address_insn = i1;
1885 REG_NOTES (i1) = REG_NOTES (temp);
1891 if (m->savemode != VOIDmode)
1893 /* P sets REG to zero; but we should clear only
1894 the bits that are not covered by the mode
1896 rtx reg = m->set_dest;
1902 (GET_MODE (reg), and_optab, reg,
1903 GEN_INT ((((HOST_WIDE_INT) 1
1904 << GET_MODE_BITSIZE (m->savemode)))
1906 reg, 1, OPTAB_LIB_WIDEN);
1910 emit_move_insn (reg, tem);
1911 sequence = gen_sequence ();
1913 i1 = emit_insn_before (sequence, loop_start);
1915 else if (GET_CODE (p) == CALL_INSN)
1917 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1918 /* Because the USAGE information potentially
1919 contains objects other than hard registers
1920 we need to copy it. */
1921 if (CALL_INSN_FUNCTION_USAGE (p))
1922 CALL_INSN_FUNCTION_USAGE (i1)
1923 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1925 else if (count == m->consec && m->move_insn_first)
1927 /* The SET_SRC might not be invariant, so we must
1928 use the REG_EQUAL note. */
1930 emit_move_insn (m->set_dest, m->set_src);
1931 temp = get_insns ();
1934 add_label_notes (m->set_src, temp);
1936 i1 = emit_insns_before (temp, loop_start);
1937 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1939 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1941 m->set_src, REG_NOTES (i1));
1944 i1 = emit_insn_before (PATTERN (p), loop_start);
1946 if (REG_NOTES (i1) == 0)
1948 REG_NOTES (i1) = REG_NOTES (p);
1950 /* If there is a REG_EQUAL note present whose value
1951 is not loop invariant, then delete it, since it
1952 may cause problems with later optimization passes.
1953 It is possible for cse to create such notes
1954 like this as a result of record_jump_cond. */
1956 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
1957 && ! loop_invariant_p (loop, XEXP (temp, 0)))
1958 remove_note (i1, temp);
1964 if (loop_dump_stream)
1965 fprintf (loop_dump_stream, " moved to %d",
1968 /* If library call, now fix the REG_NOTES that contain
1969 insn pointers, namely REG_LIBCALL on FIRST
1970 and REG_RETVAL on I1. */
1971 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
1973 XEXP (temp, 0) = first;
1974 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
1975 XEXP (temp, 0) = i1;
1982 /* simplify_giv_expr expects that it can walk the insns
1983 at m->insn forwards and see this old sequence we are
1984 tossing here. delete_insn does preserve the next
1985 pointers, but when we skip over a NOTE we must fix
1986 it up. Otherwise that code walks into the non-deleted
1988 while (p && GET_CODE (p) == NOTE)
1989 p = NEXT_INSN (temp) = NEXT_INSN (p);
1992 /* The more regs we move, the less we like moving them. */
1996 /* Any other movable that loads the same register
1998 already_moved[regno] = 1;
2000 /* This reg has been moved out of one loop. */
2001 regs->array[regno].moved_once = 1;
2003 /* The reg set here is now invariant. */
2005 regs->array[regno].set_in_loop = 0;
2009 /* Change the length-of-life info for the register
2010 to say it lives at least the full length of this loop.
2011 This will help guide optimizations in outer loops. */
2013 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2014 /* This is the old insn before all the moved insns.
2015 We can't use the moved insn because it is out of range
2016 in uid_luid. Only the old insns have luids. */
2017 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2018 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2019 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2021 /* Combine with this moved insn any other matching movables. */
2024 for (m1 = movables->head; m1; m1 = m1->next)
2029 /* Schedule the reg loaded by M1
2030 for replacement so that shares the reg of M.
2031 If the modes differ (only possible in restricted
2032 circumstances, make a SUBREG.
2034 Note this assumes that the target dependent files
2035 treat REG and SUBREG equally, including within
2036 GO_IF_LEGITIMATE_ADDRESS and in all the
2037 predicates since we never verify that replacing the
2038 original register with a SUBREG results in a
2039 recognizable insn. */
2040 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2041 reg_map[m1->regno] = m->set_dest;
2044 = gen_lowpart_common (GET_MODE (m1->set_dest),
2047 /* Get rid of the matching insn
2048 and prevent further processing of it. */
2051 /* if library call, delete all insn except last, which
2053 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2056 for (temp = XEXP (temp, 0); temp != m1->insn;
2057 temp = NEXT_INSN (temp))
2060 delete_insn (m1->insn);
2062 /* Any other movable that loads the same register
2064 already_moved[m1->regno] = 1;
2066 /* The reg merged here is now invariant,
2067 if the reg it matches is invariant. */
2069 regs->array[m1->regno].set_in_loop = 0;
2072 else if (loop_dump_stream)
2073 fprintf (loop_dump_stream, "not desirable");
2075 else if (loop_dump_stream && !m->match)
2076 fprintf (loop_dump_stream, "not safe");
2078 if (loop_dump_stream)
2079 fprintf (loop_dump_stream, "\n");
2083 new_start = loop_start;
2085 /* Go through all the instructions in the loop, making
2086 all the register substitutions scheduled in REG_MAP. */
2087 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2088 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2089 || GET_CODE (p) == CALL_INSN)
2091 replace_regs (PATTERN (p), reg_map, nregs, 0);
2092 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2098 free (already_moved);
2103 loop_movables_add (movables, m)
2104 struct loop_movables *movables;
2107 if (movables->head == 0)
2110 movables->last->next = m;
2116 loop_movables_free (movables)
2117 struct loop_movables *movables;
2120 struct movable *m_next;
2122 for (m = movables->head; m; m = m_next)
2130 /* Scan X and replace the address of any MEM in it with ADDR.
2131 REG is the address that MEM should have before the replacement. */
2134 replace_call_address (x, reg, addr)
2137 register enum rtx_code code;
2139 register const char *fmt;
2143 code = GET_CODE (x);
2157 /* Short cut for very common case. */
2158 replace_call_address (XEXP (x, 1), reg, addr);
2162 /* Short cut for very common case. */
2163 replace_call_address (XEXP (x, 0), reg, addr);
2167 /* If this MEM uses a reg other than the one we expected,
2168 something is wrong. */
2169 if (XEXP (x, 0) != reg)
2178 fmt = GET_RTX_FORMAT (code);
2179 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2182 replace_call_address (XEXP (x, i), reg, addr);
2183 else if (fmt[i] == 'E')
2186 for (j = 0; j < XVECLEN (x, i); j++)
2187 replace_call_address (XVECEXP (x, i, j), reg, addr);
2193 /* Return the number of memory refs to addresses that vary
2197 count_nonfixed_reads (loop, x)
2198 const struct loop *loop;
2201 register enum rtx_code code;
2203 register const char *fmt;
2209 code = GET_CODE (x);
2223 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2224 + count_nonfixed_reads (loop, XEXP (x, 0)));
2231 fmt = GET_RTX_FORMAT (code);
2232 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2235 value += count_nonfixed_reads (loop, XEXP (x, i));
2239 for (j = 0; j < XVECLEN (x, i); j++)
2240 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2246 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2247 `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2248 `unknown_address_altered', `unknown_constant_address_altered', and
2249 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2250 list `store_mems' in LOOP. */
2256 register int level = 1;
2258 struct loop_info *loop_info = LOOP_INFO (loop);
2259 rtx start = loop->start;
2260 rtx end = loop->end;
2261 /* The label after END. Jumping here is just like falling off the
2262 end of the loop. We use next_nonnote_insn instead of next_label
2263 as a hedge against the (pathological) case where some actual insn
2264 might end up between the two. */
2265 rtx exit_target = next_nonnote_insn (end);
2267 loop_info->has_indirect_jump = indirect_jump_in_function;
2268 loop_info->pre_header_has_call = 0;
2269 loop_info->has_call = 0;
2270 loop_info->has_nonconst_call = 0;
2271 loop_info->has_volatile = 0;
2272 loop_info->has_tablejump = 0;
2273 loop_info->has_multiple_exit_targets = 0;
2276 loop_info->unknown_address_altered = 0;
2277 loop_info->unknown_constant_address_altered = 0;
2278 loop_info->store_mems = NULL_RTX;
2279 loop_info->first_loop_store_insn = NULL_RTX;
2280 loop_info->mems_idx = 0;
2281 loop_info->num_mem_sets = 0;
2284 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
2285 insn = PREV_INSN (insn))
2287 if (GET_CODE (insn) == CALL_INSN)
2289 loop_info->pre_header_has_call = 1;
2294 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2295 insn = NEXT_INSN (insn))
2297 if (GET_CODE (insn) == NOTE)
2299 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2302 /* Count number of loops contained in this one. */
2305 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2310 else if (GET_CODE (insn) == CALL_INSN)
2312 if (! CONST_CALL_P (insn))
2314 loop_info->unknown_address_altered = 1;
2315 loop_info->has_nonconst_call = 1;
2317 loop_info->has_call = 1;
2319 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2321 rtx label1 = NULL_RTX;
2322 rtx label2 = NULL_RTX;
2324 if (volatile_refs_p (PATTERN (insn)))
2325 loop_info->has_volatile = 1;
2327 if (GET_CODE (insn) == JUMP_INSN
2328 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2329 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2330 loop_info->has_tablejump = 1;
2332 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2333 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2334 loop_info->first_loop_store_insn = insn;
2336 if (! loop_info->has_multiple_exit_targets
2337 && GET_CODE (insn) == JUMP_INSN
2338 && GET_CODE (PATTERN (insn)) == SET
2339 && SET_DEST (PATTERN (insn)) == pc_rtx)
2341 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2343 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2344 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2348 label1 = SET_SRC (PATTERN (insn));
2353 if (label1 && label1 != pc_rtx)
2355 if (GET_CODE (label1) != LABEL_REF)
2357 /* Something tricky. */
2358 loop_info->has_multiple_exit_targets = 1;
2361 else if (XEXP (label1, 0) != exit_target
2362 && LABEL_OUTSIDE_LOOP_P (label1))
2364 /* A jump outside the current loop. */
2365 loop_info->has_multiple_exit_targets = 1;
2376 else if (GET_CODE (insn) == RETURN)
2377 loop_info->has_multiple_exit_targets = 1;
2380 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2381 if (/* An exception thrown by a called function might land us
2383 ! loop_info->has_nonconst_call
2384 /* We don't want loads for MEMs moved to a location before the
2385 one at which their stack memory becomes allocated. (Note
2386 that this is not a problem for malloc, etc., since those
2387 require actual function calls. */
2388 && ! current_function_calls_alloca
2389 /* There are ways to leave the loop other than falling off the
2391 && ! loop_info->has_multiple_exit_targets)
2392 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2393 insn = NEXT_INSN (insn))
2394 for_each_rtx (&insn, insert_loop_mem, loop_info);
2396 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2397 that loop_invariant_p and load_mems can use true_dependence
2398 to determine what is really clobbered. */
2399 if (loop_info->unknown_address_altered)
2401 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2403 loop_info->store_mems
2404 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2406 if (loop_info->unknown_constant_address_altered)
2408 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2410 RTX_UNCHANGING_P (mem) = 1;
2411 loop_info->store_mems
2412 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2416 /* Scan the function looking for loops. Record the start and end of each loop.
2417 Also mark as invalid loops any loops that contain a setjmp or are branched
2418 to from outside the loop. */
2421 find_and_verify_loops (f, loops)
2423 struct loops *loops;
2428 struct loop *current_loop;
2429 struct loop *next_loop;
2432 num_loops = loops->num;
2434 compute_luids (f, NULL_RTX, 0);
2436 /* If there are jumps to undefined labels,
2437 treat them as jumps out of any/all loops.
2438 This also avoids writing past end of tables when there are no loops. */
2441 /* Find boundaries of loops, mark which loops are contained within
2442 loops, and invalidate loops that have setjmp. */
2445 current_loop = NULL;
2446 for (insn = f; insn; insn = NEXT_INSN (insn))
2448 if (GET_CODE (insn) == NOTE)
2449 switch (NOTE_LINE_NUMBER (insn))
2451 case NOTE_INSN_LOOP_BEG:
2452 next_loop = loops->array + num_loops;
2453 next_loop->num = num_loops;
2455 next_loop->start = insn;
2456 next_loop->outer = current_loop;
2457 current_loop = next_loop;
2460 case NOTE_INSN_SETJMP:
2461 /* In this case, we must invalidate our current loop and any
2463 for (loop = current_loop; loop; loop = loop->outer)
2466 if (loop_dump_stream)
2467 fprintf (loop_dump_stream,
2468 "\nLoop at %d ignored due to setjmp.\n",
2469 INSN_UID (loop->start));
2473 case NOTE_INSN_LOOP_CONT:
2474 current_loop->cont = insn;
2477 case NOTE_INSN_LOOP_VTOP:
2478 current_loop->vtop = insn;
2481 case NOTE_INSN_LOOP_END:
2485 current_loop->end = insn;
2486 current_loop = current_loop->outer;
2493 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2494 enclosing loop, but this doesn't matter. */
2495 uid_loop[INSN_UID (insn)] = current_loop;
2498 /* Any loop containing a label used in an initializer must be invalidated,
2499 because it can be jumped into from anywhere. */
2501 for (label = forced_labels; label; label = XEXP (label, 1))
2503 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2504 loop; loop = loop->outer)
2508 /* Any loop containing a label used for an exception handler must be
2509 invalidated, because it can be jumped into from anywhere. */
2511 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2513 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2514 loop; loop = loop->outer)
2518 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2519 loop that it is not contained within, that loop is marked invalid.
2520 If any INSN or CALL_INSN uses a label's address, then the loop containing
2521 that label is marked invalid, because it could be jumped into from
2524 Also look for blocks of code ending in an unconditional branch that
2525 exits the loop. If such a block is surrounded by a conditional
2526 branch around the block, move the block elsewhere (see below) and
2527 invert the jump to point to the code block. This may eliminate a
2528 label in our loop and will simplify processing by both us and a
2529 possible second cse pass. */
2531 for (insn = f; insn; insn = NEXT_INSN (insn))
2534 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2536 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2538 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2541 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2542 loop; loop = loop->outer)
2547 if (GET_CODE (insn) != JUMP_INSN)
2550 mark_loop_jump (PATTERN (insn), this_loop);
2552 /* See if this is an unconditional branch outside the loop. */
2554 && (GET_CODE (PATTERN (insn)) == RETURN
2555 || (any_uncondjump_p (insn)
2556 && onlyjump_p (insn)
2557 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2559 && get_max_uid () < max_uid_for_loop)
2562 rtx our_next = next_real_insn (insn);
2563 rtx last_insn_to_move = NEXT_INSN (insn);
2564 struct loop *dest_loop;
2565 struct loop *outer_loop = NULL;
2567 /* Go backwards until we reach the start of the loop, a label,
2569 for (p = PREV_INSN (insn);
2570 GET_CODE (p) != CODE_LABEL
2571 && ! (GET_CODE (p) == NOTE
2572 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2573 && GET_CODE (p) != JUMP_INSN;
2577 /* Check for the case where we have a jump to an inner nested
2578 loop, and do not perform the optimization in that case. */
2580 if (JUMP_LABEL (insn))
2582 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2585 for (outer_loop = dest_loop; outer_loop;
2586 outer_loop = outer_loop->outer)
2587 if (outer_loop == this_loop)
2592 /* Make sure that the target of P is within the current loop. */
2594 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2595 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2596 outer_loop = this_loop;
2598 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2599 we have a block of code to try to move.
2601 We look backward and then forward from the target of INSN
2602 to find a BARRIER at the same loop depth as the target.
2603 If we find such a BARRIER, we make a new label for the start
2604 of the block, invert the jump in P and point it to that label,
2605 and move the block of code to the spot we found. */
2608 && GET_CODE (p) == JUMP_INSN
2609 && JUMP_LABEL (p) != 0
2610 /* Just ignore jumps to labels that were never emitted.
2611 These always indicate compilation errors. */
2612 && INSN_UID (JUMP_LABEL (p)) != 0
2613 && any_condjump_p (p) && onlyjump_p (p)
2614 && next_real_insn (JUMP_LABEL (p)) == our_next
2615 /* If it's not safe to move the sequence, then we
2617 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2618 &last_insn_to_move))
2621 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2622 struct loop *target_loop = uid_loop[INSN_UID (target)];
2625 for (loc = target; loc; loc = PREV_INSN (loc))
2626 if (GET_CODE (loc) == BARRIER
2627 /* Don't move things inside a tablejump. */
2628 && ((loc2 = next_nonnote_insn (loc)) == 0
2629 || GET_CODE (loc2) != CODE_LABEL
2630 || (loc2 = next_nonnote_insn (loc2)) == 0
2631 || GET_CODE (loc2) != JUMP_INSN
2632 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2633 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2634 && uid_loop[INSN_UID (loc)] == target_loop)
2638 for (loc = target; loc; loc = NEXT_INSN (loc))
2639 if (GET_CODE (loc) == BARRIER
2640 /* Don't move things inside a tablejump. */
2641 && ((loc2 = next_nonnote_insn (loc)) == 0
2642 || GET_CODE (loc2) != CODE_LABEL
2643 || (loc2 = next_nonnote_insn (loc2)) == 0
2644 || GET_CODE (loc2) != JUMP_INSN
2645 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2646 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2647 && uid_loop[INSN_UID (loc)] == target_loop)
2652 rtx cond_label = JUMP_LABEL (p);
2653 rtx new_label = get_label_after (p);
2655 /* Ensure our label doesn't go away. */
2656 LABEL_NUSES (cond_label)++;
2658 /* Verify that uid_loop is large enough and that
2660 if (invert_jump (p, new_label, 1))
2664 /* If no suitable BARRIER was found, create a suitable
2665 one before TARGET. Since TARGET is a fall through
2666 path, we'll need to insert an jump around our block
2667 and a add a BARRIER before TARGET.
2669 This creates an extra unconditional jump outside
2670 the loop. However, the benefits of removing rarely
2671 executed instructions from inside the loop usually
2672 outweighs the cost of the extra unconditional jump
2673 outside the loop. */
2678 temp = gen_jump (JUMP_LABEL (insn));
2679 temp = emit_jump_insn_before (temp, target);
2680 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2681 LABEL_NUSES (JUMP_LABEL (insn))++;
2682 loc = emit_barrier_before (target);
2685 /* Include the BARRIER after INSN and copy the
2687 new_label = squeeze_notes (new_label,
2689 reorder_insns (new_label, last_insn_to_move, loc);
2691 /* All those insns are now in TARGET_LOOP. */
2693 q != NEXT_INSN (last_insn_to_move);
2695 uid_loop[INSN_UID (q)] = target_loop;
2697 /* The label jumped to by INSN is no longer a loop
2698 exit. Unless INSN does not have a label (e.g.,
2699 it is a RETURN insn), search loop->exit_labels
2700 to find its label_ref, and remove it. Also turn
2701 off LABEL_OUTSIDE_LOOP_P bit. */
2702 if (JUMP_LABEL (insn))
2704 for (q = 0, r = this_loop->exit_labels;
2706 q = r, r = LABEL_NEXTREF (r))
2707 if (XEXP (r, 0) == JUMP_LABEL (insn))
2709 LABEL_OUTSIDE_LOOP_P (r) = 0;
2711 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2713 this_loop->exit_labels = LABEL_NEXTREF (r);
2717 for (loop = this_loop; loop && loop != target_loop;
2721 /* If we didn't find it, then something is
2727 /* P is now a jump outside the loop, so it must be put
2728 in loop->exit_labels, and marked as such.
2729 The easiest way to do this is to just call
2730 mark_loop_jump again for P. */
2731 mark_loop_jump (PATTERN (p), this_loop);
2733 /* If INSN now jumps to the insn after it,
2735 if (JUMP_LABEL (insn) != 0
2736 && (next_real_insn (JUMP_LABEL (insn))
2737 == next_real_insn (insn)))
2741 /* Continue the loop after where the conditional
2742 branch used to jump, since the only branch insn
2743 in the block (if it still remains) is an inter-loop
2744 branch and hence needs no processing. */
2745 insn = NEXT_INSN (cond_label);
2747 if (--LABEL_NUSES (cond_label) == 0)
2748 delete_insn (cond_label);
2750 /* This loop will be continued with NEXT_INSN (insn). */
2751 insn = PREV_INSN (insn);
2758 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2759 loops it is contained in, mark the target loop invalid.
2761 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2764 mark_loop_jump (x, loop)
2768 struct loop *dest_loop;
2769 struct loop *outer_loop;
2772 switch (GET_CODE (x))
2785 /* There could be a label reference in here. */
2786 mark_loop_jump (XEXP (x, 0), loop);
2792 mark_loop_jump (XEXP (x, 0), loop);
2793 mark_loop_jump (XEXP (x, 1), loop);
2797 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2798 mark_loop_jump (XEXP (x, 1), loop);
2803 mark_loop_jump (XEXP (x, 0), loop);
2807 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2809 /* Link together all labels that branch outside the loop. This
2810 is used by final_[bg]iv_value and the loop unrolling code. Also
2811 mark this LABEL_REF so we know that this branch should predict
2814 /* A check to make sure the label is not in an inner nested loop,
2815 since this does not count as a loop exit. */
2818 for (outer_loop = dest_loop; outer_loop;
2819 outer_loop = outer_loop->outer)
2820 if (outer_loop == loop)
2826 if (loop && ! outer_loop)
2828 LABEL_OUTSIDE_LOOP_P (x) = 1;
2829 LABEL_NEXTREF (x) = loop->exit_labels;
2830 loop->exit_labels = x;
2832 for (outer_loop = loop;
2833 outer_loop && outer_loop != dest_loop;
2834 outer_loop = outer_loop->outer)
2835 outer_loop->exit_count++;
2838 /* If this is inside a loop, but not in the current loop or one enclosed
2839 by it, it invalidates at least one loop. */
2844 /* We must invalidate every nested loop containing the target of this
2845 label, except those that also contain the jump insn. */
2847 for (; dest_loop; dest_loop = dest_loop->outer)
2849 /* Stop when we reach a loop that also contains the jump insn. */
2850 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2851 if (dest_loop == outer_loop)
2854 /* If we get here, we know we need to invalidate a loop. */
2855 if (loop_dump_stream && ! dest_loop->invalid)
2856 fprintf (loop_dump_stream,
2857 "\nLoop at %d ignored due to multiple entry points.\n",
2858 INSN_UID (dest_loop->start));
2860 dest_loop->invalid = 1;
2865 /* If this is not setting pc, ignore. */
2866 if (SET_DEST (x) == pc_rtx)
2867 mark_loop_jump (SET_SRC (x), loop);
2871 mark_loop_jump (XEXP (x, 1), loop);
2872 mark_loop_jump (XEXP (x, 2), loop);
2877 for (i = 0; i < XVECLEN (x, 0); i++)
2878 mark_loop_jump (XVECEXP (x, 0, i), loop);
2882 for (i = 0; i < XVECLEN (x, 1); i++)
2883 mark_loop_jump (XVECEXP (x, 1, i), loop);
2887 /* Strictly speaking this is not a jump into the loop, only a possible
2888 jump out of the loop. However, we have no way to link the destination
2889 of this jump onto the list of exit labels. To be safe we mark this
2890 loop and any containing loops as invalid. */
2893 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2895 if (loop_dump_stream && ! outer_loop->invalid)
2896 fprintf (loop_dump_stream,
2897 "\nLoop at %d ignored due to unknown exit jump.\n",
2898 INSN_UID (outer_loop->start));
2899 outer_loop->invalid = 1;
2906 /* Return nonzero if there is a label in the range from
2907 insn INSN to and including the insn whose luid is END
2908 INSN must have an assigned luid (i.e., it must not have
2909 been previously created by loop.c). */
2912 labels_in_range_p (insn, end)
2916 while (insn && INSN_LUID (insn) <= end)
2918 if (GET_CODE (insn) == CODE_LABEL)
2920 insn = NEXT_INSN (insn);
2926 /* Record that a memory reference X is being set. */
2929 note_addr_stored (x, y, data)
2931 rtx y ATTRIBUTE_UNUSED;
2932 void *data ATTRIBUTE_UNUSED;
2934 struct loop_info *loop_info = data;
2936 if (x == 0 || GET_CODE (x) != MEM)
2939 /* Count number of memory writes.
2940 This affects heuristics in strength_reduce. */
2941 loop_info->num_mem_sets++;
2943 /* BLKmode MEM means all memory is clobbered. */
2944 if (GET_MODE (x) == BLKmode)
2946 if (RTX_UNCHANGING_P (x))
2947 loop_info->unknown_constant_address_altered = 1;
2949 loop_info->unknown_address_altered = 1;
2954 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2955 loop_info->store_mems);
2958 /* X is a value modified by an INSN that references a biv inside a loop
2959 exit test (ie, X is somehow related to the value of the biv). If X
2960 is a pseudo that is used more than once, then the biv is (effectively)
2961 used more than once. DATA is a pointer to a loop_regs structure. */
2964 note_set_pseudo_multiple_uses (x, y, data)
2966 rtx y ATTRIBUTE_UNUSED;
2969 struct loop_regs *regs = (struct loop_regs *) data;
2974 while (GET_CODE (x) == STRICT_LOW_PART
2975 || GET_CODE (x) == SIGN_EXTRACT
2976 || GET_CODE (x) == ZERO_EXTRACT
2977 || GET_CODE (x) == SUBREG)
2980 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
2983 /* If we do not have usage information, or if we know the register
2984 is used more than once, note that fact for check_dbra_loop. */
2985 if (REGNO (x) >= max_reg_before_loop
2986 || ! regs->array[REGNO (x)].single_usage
2987 || regs->array[REGNO (x)].single_usage == const0_rtx)
2988 regs->multiple_uses = 1;
2991 /* Return nonzero if the rtx X is invariant over the current loop.
2993 The value is 2 if we refer to something only conditionally invariant.
2995 A memory ref is invariant if it is not volatile and does not conflict
2996 with anything stored in `loop_info->store_mems'. */
2999 loop_invariant_p (loop, x)
3000 const struct loop *loop;
3003 struct loop_info *loop_info = LOOP_INFO (loop);
3004 struct loop_regs *regs = LOOP_REGS (loop);
3006 register enum rtx_code code;
3007 register const char *fmt;
3008 int conditional = 0;
3013 code = GET_CODE (x);
3023 /* A LABEL_REF is normally invariant, however, if we are unrolling
3024 loops, and this label is inside the loop, then it isn't invariant.
3025 This is because each unrolled copy of the loop body will have
3026 a copy of this label. If this was invariant, then an insn loading
3027 the address of this label into a register might get moved outside
3028 the loop, and then each loop body would end up using the same label.
3030 We don't know the loop bounds here though, so just fail for all
3032 if (flag_unroll_loops)
3039 case UNSPEC_VOLATILE:
3043 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3044 since the reg might be set by initialization within the loop. */
3046 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3047 || x == arg_pointer_rtx)
3048 && ! current_function_has_nonlocal_goto)
3051 if (LOOP_INFO (loop)->has_call
3052 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3055 if (regs->array[REGNO (x)].set_in_loop < 0)
3058 return regs->array[REGNO (x)].set_in_loop == 0;
3061 /* Volatile memory references must be rejected. Do this before
3062 checking for read-only items, so that volatile read-only items
3063 will be rejected also. */
3064 if (MEM_VOLATILE_P (x))
3067 /* See if there is any dependence between a store and this load. */
3068 mem_list_entry = loop_info->store_mems;
3069 while (mem_list_entry)
3071 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3075 mem_list_entry = XEXP (mem_list_entry, 1);
3078 /* It's not invalidated by a store in memory
3079 but we must still verify the address is invariant. */
3083 /* Don't mess with insns declared volatile. */
3084 if (MEM_VOLATILE_P (x))
3092 fmt = GET_RTX_FORMAT (code);
3093 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3097 int tem = loop_invariant_p (loop, XEXP (x, i));
3103 else if (fmt[i] == 'E')
3106 for (j = 0; j < XVECLEN (x, i); j++)
3108 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3118 return 1 + conditional;
3121 /* Return nonzero if all the insns in the loop that set REG
3122 are INSN and the immediately following insns,
3123 and if each of those insns sets REG in an invariant way
3124 (not counting uses of REG in them).
3126 The value is 2 if some of these insns are only conditionally invariant.
3128 We assume that INSN itself is the first set of REG
3129 and that its source is invariant. */
3132 consec_sets_invariant_p (loop, reg, n_sets, insn)
3133 const struct loop *loop;
3137 struct loop_regs *regs = LOOP_REGS (loop);
3139 unsigned int regno = REGNO (reg);
3141 /* Number of sets we have to insist on finding after INSN. */
3142 int count = n_sets - 1;
3143 int old = regs->array[regno].set_in_loop;
3147 /* If N_SETS hit the limit, we can't rely on its value. */
3151 regs->array[regno].set_in_loop = 0;
3155 register enum rtx_code code;
3159 code = GET_CODE (p);
3161 /* If library call, skip to end of it. */
3162 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3167 && (set = single_set (p))
3168 && GET_CODE (SET_DEST (set)) == REG
3169 && REGNO (SET_DEST (set)) == regno)
3171 this = loop_invariant_p (loop, SET_SRC (set));
3174 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3176 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3177 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3179 this = (CONSTANT_P (XEXP (temp, 0))
3180 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3181 && loop_invariant_p (loop, XEXP (temp, 0))));
3188 else if (code != NOTE)
3190 regs->array[regno].set_in_loop = old;
3195 regs->array[regno].set_in_loop = old;
3196 /* If loop_invariant_p ever returned 2, we return 2. */
3197 return 1 + (value & 2);
3201 /* I don't think this condition is sufficient to allow INSN
3202 to be moved, so we no longer test it. */
3204 /* Return 1 if all insns in the basic block of INSN and following INSN
3205 that set REG are invariant according to TABLE. */
3208 all_sets_invariant_p (reg, insn, table)
3212 register rtx p = insn;
3213 register int regno = REGNO (reg);
3217 register enum rtx_code code;
3219 code = GET_CODE (p);
3220 if (code == CODE_LABEL || code == JUMP_INSN)
3222 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3223 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3224 && REGNO (SET_DEST (PATTERN (p))) == regno)
3226 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3233 /* Look at all uses (not sets) of registers in X. For each, if it is
3234 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3235 a different insn, set USAGE[REGNO] to const0_rtx. */
3238 find_single_use_in_loop (regs, insn, x)
3239 struct loop_regs *regs;
3243 enum rtx_code code = GET_CODE (x);
3244 const char *fmt = GET_RTX_FORMAT (code);
3248 regs->array[REGNO (x)].single_usage
3249 = (regs->array[REGNO (x)].single_usage != 0
3250 && regs->array[REGNO (x)].single_usage != insn)
3251 ? const0_rtx : insn;
3253 else if (code == SET)
3255 /* Don't count SET_DEST if it is a REG; otherwise count things
3256 in SET_DEST because if a register is partially modified, it won't
3257 show up as a potential movable so we don't care how USAGE is set
3259 if (GET_CODE (SET_DEST (x)) != REG)
3260 find_single_use_in_loop (regs, insn, SET_DEST (x));
3261 find_single_use_in_loop (regs, insn, SET_SRC (x));
3264 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3266 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3267 find_single_use_in_loop (regs, insn, XEXP (x, i));
3268 else if (fmt[i] == 'E')
3269 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3270 find_single_use_in_loop (regs, insn, XVECEXP (x, i, j));
3274 /* Count and record any set in X which is contained in INSN. Update
3275 REGS->array[I].MAY_NOT_OPTIMIZE and LAST_SET for any register I set
3279 count_one_set (regs, insn, x, last_set)
3280 struct loop_regs *regs;
3284 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3285 /* Don't move a reg that has an explicit clobber.
3286 It's not worth the pain to try to do it correctly. */
3287 regs->array[REGNO (XEXP (x, 0))].may_not_optimize = 1;
3289 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3291 rtx dest = SET_DEST (x);
3292 while (GET_CODE (dest) == SUBREG
3293 || GET_CODE (dest) == ZERO_EXTRACT
3294 || GET_CODE (dest) == SIGN_EXTRACT
3295 || GET_CODE (dest) == STRICT_LOW_PART)
3296 dest = XEXP (dest, 0);
3297 if (GET_CODE (dest) == REG)
3299 register int regno = REGNO (dest);
3300 /* If this is the first setting of this reg
3301 in current basic block, and it was set before,
3302 it must be set in two basic blocks, so it cannot
3303 be moved out of the loop. */
3304 if (regs->array[regno].set_in_loop > 0
3306 regs->array[regno].may_not_optimize = 1;
3307 /* If this is not first setting in current basic block,
3308 see if reg was used in between previous one and this.
3309 If so, neither one can be moved. */
3310 if (last_set[regno] != 0
3311 && reg_used_between_p (dest, last_set[regno], insn))
3312 regs->array[regno].may_not_optimize = 1;
3313 if (regs->array[regno].set_in_loop < 127)
3314 ++regs->array[regno].set_in_loop;
3315 last_set[regno] = insn;
3320 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3321 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3322 contained in insn INSN is used by any insn that precedes INSN in
3323 cyclic order starting from the loop entry point.
3325 We don't want to use INSN_LUID here because if we restrict INSN to those
3326 that have a valid INSN_LUID, it means we cannot move an invariant out
3327 from an inner loop past two loops. */
3330 loop_reg_used_before_p (loop, set, insn)
3331 const struct loop *loop;
3334 rtx reg = SET_DEST (set);
3337 /* Scan forward checking for register usage. If we hit INSN, we
3338 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3339 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3341 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3351 /* A "basic induction variable" or biv is a pseudo reg that is set
3352 (within this loop) only by incrementing or decrementing it. */
3353 /* A "general induction variable" or giv is a pseudo reg whose
3354 value is a linear function of a biv. */
3356 /* Bivs are recognized by `basic_induction_var';
3357 Givs by `general_induction_var'. */
3359 /* Communication with routines called via `note_stores'. */
3361 static rtx note_insn;
3363 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3365 static rtx addr_placeholder;
3367 /* ??? Unfinished optimizations, and possible future optimizations,
3368 for the strength reduction code. */
3370 /* ??? The interaction of biv elimination, and recognition of 'constant'
3371 bivs, may cause problems. */
3373 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3374 performance problems.
3376 Perhaps don't eliminate things that can be combined with an addressing
3377 mode. Find all givs that have the same biv, mult_val, and add_val;
3378 then for each giv, check to see if its only use dies in a following
3379 memory address. If so, generate a new memory address and check to see
3380 if it is valid. If it is valid, then store the modified memory address,
3381 otherwise, mark the giv as not done so that it will get its own iv. */
3383 /* ??? Could try to optimize branches when it is known that a biv is always
3386 /* ??? When replace a biv in a compare insn, we should replace with closest
3387 giv so that an optimized branch can still be recognized by the combiner,
3388 e.g. the VAX acb insn. */
3390 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3391 was rerun in loop_optimize whenever a register was added or moved.
3392 Also, some of the optimizations could be a little less conservative. */
3394 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3395 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3398 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3399 loop iteration except for the last one.
3401 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3405 for_each_insn_in_loop (loop, fncall)
3407 loop_insn_callback fncall;
3409 /* This is 1 if current insn is not executed at least once for every loop
3411 int not_every_iteration = 0;
3412 int maybe_multiple = 0;
3413 int past_loop_latch = 0;
3417 /* If loop_scan_start points to the loop exit test, we have to be wary of
3418 subversive use of gotos inside expression statements. */
3419 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3420 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3422 /* Scan through loop to find all possible bivs. */
3424 for (p = next_insn_in_loop (loop, loop->scan_start);
3426 p = next_insn_in_loop (loop, p))
3428 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3430 /* Past CODE_LABEL, we get to insns that may be executed multiple
3431 times. The only way we can be sure that they can't is if every
3432 jump insn between here and the end of the loop either
3433 returns, exits the loop, is a jump to a location that is still
3434 behind the label, or is a jump to the loop start. */
3436 if (GET_CODE (p) == CODE_LABEL)
3444 insn = NEXT_INSN (insn);
3445 if (insn == loop->scan_start)
3447 if (insn == loop->end)
3453 if (insn == loop->scan_start)
3457 if (GET_CODE (insn) == JUMP_INSN
3458 && GET_CODE (PATTERN (insn)) != RETURN
3459 && (!any_condjump_p (insn)
3460 || (JUMP_LABEL (insn) != 0
3461 && JUMP_LABEL (insn) != loop->scan_start
3462 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3470 /* Past a jump, we get to insns for which we can't count
3471 on whether they will be executed during each iteration. */
3472 /* This code appears twice in strength_reduce. There is also similar
3473 code in scan_loop. */
3474 if (GET_CODE (p) == JUMP_INSN
3475 /* If we enter the loop in the middle, and scan around to the
3476 beginning, don't set not_every_iteration for that.
3477 This can be any kind of jump, since we want to know if insns
3478 will be executed if the loop is executed. */
3479 && !(JUMP_LABEL (p) == loop->top
3480 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3481 && any_uncondjump_p (p))
3482 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3486 /* If this is a jump outside the loop, then it also doesn't
3487 matter. Check to see if the target of this branch is on the
3488 loop->exits_labels list. */
3490 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3491 if (XEXP (label, 0) == JUMP_LABEL (p))
3495 not_every_iteration = 1;
3498 else if (GET_CODE (p) == NOTE)
3500 /* At the virtual top of a converted loop, insns are again known to
3501 be executed each iteration: logically, the loop begins here
3502 even though the exit code has been duplicated.
3504 Insns are also again known to be executed each iteration at
3505 the LOOP_CONT note. */
3506 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3507 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3509 not_every_iteration = 0;
3510 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3512 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3516 /* Note if we pass a loop latch. If we do, then we can not clear
3517 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3518 a loop since a jump before the last CODE_LABEL may have started
3519 a new loop iteration.
3521 Note that LOOP_TOP is only set for rotated loops and we need
3522 this check for all loops, so compare against the CODE_LABEL
3523 which immediately follows LOOP_START. */
3524 if (GET_CODE (p) == JUMP_INSN
3525 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3526 past_loop_latch = 1;
3528 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3529 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3530 or not an insn is known to be executed each iteration of the
3531 loop, whether or not any iterations are known to occur.
3533 Therefore, if we have just passed a label and have no more labels
3534 between here and the test insn of the loop, and we have not passed
3535 a jump to the top of the loop, then we know these insns will be
3536 executed each iteration. */
3538 if (not_every_iteration
3540 && GET_CODE (p) == CODE_LABEL
3541 && no_labels_between_p (p, loop->end)
3542 && loop_insn_first_p (p, loop->cont))
3543 not_every_iteration = 0;
3548 loop_bivs_find (loop)
3551 struct loop_regs *regs = LOOP_REGS (loop);
3552 struct loop_ivs *ivs = LOOP_IVS (loop);
3553 /* Temporary list pointers for traversing ivs->list. */
3554 struct iv_class *bl, **backbl;
3558 for_each_insn_in_loop (loop, check_insn_for_bivs);
3560 /* Scan ivs->list to remove all regs that proved not to be bivs.
3561 Make a sanity check against regs->n_times_set. */
3562 for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
3564 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3565 /* Above happens if register modified by subreg, etc. */
3566 /* Make sure it is not recognized as a basic induction var: */
3567 || regs->array[bl->regno].n_times_set != bl->biv_count
3568 /* If never incremented, it is invariant that we decided not to
3569 move. So leave it alone. */
3570 || ! bl->incremented)
3572 if (loop_dump_stream)
3573 fprintf (loop_dump_stream, "Biv %d: discarded, %s\n",
3575 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3576 ? "not induction variable"
3577 : (! bl->incremented ? "never incremented"
3580 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3587 if (loop_dump_stream)
3588 fprintf (loop_dump_stream, "Biv %d: verified\n", bl->regno);
3594 /* Determine how BIVS are initialised by looking through pre-header
3595 extended basic block. */
3597 loop_bivs_init_find (loop)
3600 struct loop_ivs *ivs = LOOP_IVS (loop);
3601 /* Temporary list pointers for traversing ivs->list. */
3602 struct iv_class *bl;
3606 /* Find initial value for each biv by searching backwards from loop_start,
3607 halting at first label. Also record any test condition. */
3610 for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3616 if (GET_CODE (p) == CALL_INSN)
3620 note_stores (PATTERN (p), record_initial, ivs);
3622 /* Record any test of a biv that branches around the loop if no store
3623 between it and the start of loop. We only care about tests with
3624 constants and registers and only certain of those. */
3625 if (GET_CODE (p) == JUMP_INSN
3626 && JUMP_LABEL (p) != 0
3627 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
3628 && (test = get_condition_for_loop (loop, p)) != 0
3629 && GET_CODE (XEXP (test, 0)) == REG
3630 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3631 && (bl = REG_IV_CLASS (ivs, REGNO (XEXP (test, 0)))) != 0
3632 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop->start)
3633 && bl->init_insn == 0)
3635 /* If an NE test, we have an initial value! */
3636 if (GET_CODE (test) == NE)
3639 bl->init_set = gen_rtx_SET (VOIDmode,
3640 XEXP (test, 0), XEXP (test, 1));
3643 bl->initial_test = test;
3649 /* Look at the each biv and see if we can say anything better about its
3650 initial value from any initializing insns set up above. (This is done
3651 in two passes to avoid missing SETs in a PARALLEL.) */
3653 loop_bivs_check (loop)
3656 struct loop_ivs *ivs = LOOP_IVS (loop);
3657 /* Temporary list pointers for traversing ivs->list. */
3658 struct iv_class *bl;
3659 struct iv_class **backbl;
3661 for (backbl = &ivs->list; (bl = *backbl); backbl = &bl->next)
3666 if (! bl->init_insn)
3669 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3670 is a constant, use the value of that. */
3671 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3672 && CONSTANT_P (XEXP (note, 0)))
3673 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3674 && CONSTANT_P (XEXP (note, 0))))
3675 src = XEXP (note, 0);
3677 src = SET_SRC (bl->init_set);
3679 if (loop_dump_stream)
3680 fprintf (loop_dump_stream,
3681 "Biv %d: initialized at insn %d: initial value ",
3682 bl->regno, INSN_UID (bl->init_insn));
3684 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3685 || GET_MODE (src) == VOIDmode)
3686 && valid_initial_value_p (src, bl->init_insn,
3687 LOOP_INFO (loop)->pre_header_has_call,
3690 bl->initial_value = src;
3692 if (loop_dump_stream)
3694 print_simple_rtl (loop_dump_stream, src);
3695 fputc ('\n', loop_dump_stream);
3698 /* If we can't make it a giv,
3699 let biv keep initial value of "itself". */
3700 else if (loop_dump_stream)
3701 fprintf (loop_dump_stream, "is complex\n");
3706 /* Search the loop for general induction variables. */
3709 loop_givs_find (loop)
3712 for_each_insn_in_loop (loop, check_insn_for_givs);
3716 /* For each giv for which we still don't know whether or not it is
3717 replaceable, check to see if it is replaceable because its final value
3718 can be calculated. */
3721 loop_givs_check (loop)
3724 struct loop_ivs *ivs = LOOP_IVS (loop);
3725 struct iv_class *bl;
3727 for (bl = ivs->list; bl; bl = bl->next)
3729 struct induction *v;
3731 for (v = bl->giv; v; v = v->next_iv)
3732 if (! v->replaceable && ! v->not_replaceable)
3733 check_final_value (loop, v);
3738 /* Return non-zero if it is possible to eliminate the biv BL provided
3739 all givs are reduced. This is possible if either the reg is not
3740 used outside the loop, or we can compute what its final value will
3744 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3746 struct iv_class *bl;
3750 /* For architectures with a decrement_and_branch_until_zero insn,
3751 don't do this if we put a REG_NONNEG note on the endtest for this
3754 #ifdef HAVE_decrement_and_branch_until_zero
3757 if (loop_dump_stream)
3758 fprintf (loop_dump_stream,
3759 "Cannot eliminate nonneg biv %d.\n", bl->regno);
3764 /* Check that biv is used outside loop or if it has a final value.
3765 Compare against bl->init_insn rather than loop->start. We aren't
3766 concerned with any uses of the biv between init_insn and
3767 loop->start since these won't be affected by the value of the biv
3768 elsewhere in the function, so long as init_insn doesn't use the
3771 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3773 && INSN_UID (bl->init_insn) < max_uid_for_loop
3774 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3775 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3776 || (bl->final_value = final_biv_value (loop, bl)))
3777 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3779 if (loop_dump_stream)
3781 fprintf (loop_dump_stream,
3782 "Cannot eliminate biv %d.\n",
3784 fprintf (loop_dump_stream,
3785 "First use: insn %d, last use: insn %d.\n",
3786 REGNO_FIRST_UID (bl->regno),
3787 REGNO_LAST_UID (bl->regno));
3793 /* Reduce each giv of BL that we have decided to reduce. */
3796 loop_givs_reduce (loop, bl)
3798 struct iv_class *bl;
3800 struct induction *v;
3802 for (v = bl->giv; v; v = v->next_iv)
3804 struct induction *tv;
3805 if (! v->ignore && v->same == 0)
3807 int auto_inc_opt = 0;
3809 /* If the code for derived givs immediately below has already
3810 allocated a new_reg, we must keep it. */
3812 v->new_reg = gen_reg_rtx (v->mode);
3815 /* If the target has auto-increment addressing modes, and
3816 this is an address giv, then try to put the increment
3817 immediately after its use, so that flow can create an
3818 auto-increment addressing mode. */
3819 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
3820 && bl->biv->always_executed && ! bl->biv->maybe_multiple
3821 /* We don't handle reversed biv's because bl->biv->insn
3822 does not have a valid INSN_LUID. */
3824 && v->always_executed && ! v->maybe_multiple
3825 && INSN_UID (v->insn) < max_uid_for_loop)
3827 /* If other giv's have been combined with this one, then
3828 this will work only if all uses of the other giv's occur
3829 before this giv's insn. This is difficult to check.
3831 We simplify this by looking for the common case where
3832 there is one DEST_REG giv, and this giv's insn is the
3833 last use of the dest_reg of that DEST_REG giv. If the
3834 increment occurs after the address giv, then we can
3835 perform the optimization. (Otherwise, the increment
3836 would have to go before other_giv, and we would not be
3837 able to combine it with the address giv to get an
3838 auto-inc address.) */
3839 if (v->combined_with)
3841 struct induction *other_giv = 0;
3843 for (tv = bl->giv; tv; tv = tv->next_iv)
3851 if (! tv && other_giv
3852 && REGNO (other_giv->dest_reg) < max_reg_before_loop
3853 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
3854 == INSN_UID (v->insn))
3855 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
3858 /* Check for case where increment is before the address
3859 giv. Do this test in "loop order". */
3860 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
3861 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3862 || (INSN_LUID (bl->biv->insn)
3863 > INSN_LUID (loop->scan_start))))
3864 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3865 && (INSN_LUID (loop->scan_start)
3866 < INSN_LUID (bl->biv->insn))))
3875 /* We can't put an insn immediately after one setting
3876 cc0, or immediately before one using cc0. */
3877 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
3878 || (auto_inc_opt == -1
3879 && (prev = prev_nonnote_insn (v->insn)) != 0
3881 && sets_cc0_p (PATTERN (prev))))
3887 v->auto_inc_opt = 1;
3891 /* For each place where the biv is incremented, add an insn
3892 to increment the new, reduced reg for the giv. */
3893 for (tv = bl->biv; tv; tv = tv->next_iv)
3898 insert_before = tv->insn;
3899 else if (auto_inc_opt == 1)
3900 insert_before = NEXT_INSN (v->insn);
3902 insert_before = v->insn;
3904 if (tv->mult_val == const1_rtx)
3905 emit_iv_add_mult (tv->add_val, v->mult_val,
3906 v->new_reg, v->new_reg, insert_before);
3907 else /* tv->mult_val == const0_rtx */
3908 /* A multiply is acceptable here
3909 since this is presumed to be seldom executed. */
3910 emit_iv_add_mult (tv->add_val, v->mult_val,
3911 v->add_val, v->new_reg, insert_before);
3914 /* Add code at loop start to initialize giv's reduced reg. */
3916 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
3917 v->mult_val, v->add_val, v->new_reg,
3924 /* Check for givs whose first use is their definition and whose
3925 last use is the definition of another giv. If so, it is likely
3926 dead and should not be used to derive another giv nor to
3930 loop_givs_dead_check (loop, bl)
3931 struct loop *loop ATTRIBUTE_UNUSED;
3932 struct iv_class *bl;
3934 struct induction *v;
3936 for (v = bl->giv; v; v = v->next_iv)
3939 || (v->same && v->same->ignore))
3942 if (v->giv_type == DEST_REG
3943 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
3945 struct induction *v1;
3947 for (v1 = bl->giv; v1; v1 = v1->next_iv)
3948 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
3956 loop_givs_rescan (loop, bl, reg_map, end_insert_before)
3958 struct iv_class *bl;
3960 rtx end_insert_before;
3962 struct induction *v;
3964 for (v = bl->giv; v; v = v->next_iv)
3966 if (v->same && v->same->ignore)
3972 /* Update expression if this was combined, in case other giv was
3975 v->new_reg = replace_rtx (v->new_reg,
3976 v->same->dest_reg, v->same->new_reg);
3978 /* See if this register is known to be a pointer to something. If
3979 so, see if we can find the alignment. First see if there is a
3980 destination register that is a pointer. If so, this shares the
3981 alignment too. Next see if we can deduce anything from the
3982 computational information. If not, and this is a DEST_ADDR
3983 giv, at least we know that it's a pointer, though we don't know
3985 if (GET_CODE (v->new_reg) == REG
3986 && v->giv_type == DEST_REG
3987 && REG_POINTER (v->dest_reg))
3988 mark_reg_pointer (v->new_reg,
3989 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
3990 else if (GET_CODE (v->new_reg) == REG
3991 && REG_POINTER (v->src_reg))
3993 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
3996 || GET_CODE (v->add_val) != CONST_INT
3997 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4000 mark_reg_pointer (v->new_reg, align);
4002 else if (GET_CODE (v->new_reg) == REG
4003 && GET_CODE (v->add_val) == REG
4004 && REG_POINTER (v->add_val))
4006 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4008 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4009 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4012 mark_reg_pointer (v->new_reg, align);
4014 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4015 mark_reg_pointer (v->new_reg, 0);
4017 if (v->giv_type == DEST_ADDR)
4018 /* Store reduced reg as the address in the memref where we found
4020 validate_change (v->insn, v->location, v->new_reg, 0);
4021 else if (v->replaceable)
4023 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4027 /* Not replaceable; emit an insn to set the original giv reg from
4028 the reduced giv, same as above. */
4029 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4033 /* When a loop is reversed, givs which depend on the reversed
4034 biv, and which are live outside the loop, must be set to their
4035 correct final value. This insn is only needed if the giv is
4036 not replaceable. The correct final value is the same as the
4037 value that the giv starts the reversed loop with. */
4038 if (bl->reversed && ! v->replaceable)
4039 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4040 v->mult_val, v->add_val, v->dest_reg,
4042 else if (v->final_value)
4046 /* If the loop has multiple exits, emit the insn before the
4047 loop to ensure that it will always be executed no matter
4048 how the loop exits. Otherwise, emit the insn after the loop,
4049 since this is slightly more efficient. */
4050 if (loop->exit_count)
4051 insert_before = loop->start;
4053 insert_before = end_insert_before;
4054 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4058 if (loop_dump_stream)
4060 fprintf (loop_dump_stream, "giv at %d reduced to ",
4061 INSN_UID (v->insn));
4062 print_simple_rtl (loop_dump_stream, v->new_reg);
4063 fprintf (loop_dump_stream, "\n");
4070 loop_giv_reduce_benefit (loop, bl, v, test_reg)
4071 struct loop *loop ATTRIBUTE_UNUSED;
4072 struct iv_class *bl;
4073 struct induction *v;
4079 benefit = v->benefit;
4080 PUT_MODE (test_reg, v->mode);
4081 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4082 test_reg, test_reg);
4084 /* Reduce benefit if not replaceable, since we will insert a
4085 move-insn to replace the insn that calculates this giv. Don't do
4086 this unless the giv is a user variable, since it will often be
4087 marked non-replaceable because of the duplication of the exit
4088 code outside the loop. In such a case, the copies we insert are
4089 dead and will be deleted. So they don't have a cost. Similar
4090 situations exist. */
4091 /* ??? The new final_[bg]iv_value code does a much better job of
4092 finding replaceable giv's, and hence this code may no longer be
4094 if (! v->replaceable && ! bl->eliminable
4095 && REG_USERVAR_P (v->dest_reg))
4096 benefit -= copy_cost;
4098 /* Decrease the benefit to count the add-insns that we will insert
4099 to increment the reduced reg for the giv. ??? This can
4100 overestimate the run-time cost of the additional insns, e.g. if
4101 there are multiple basic blocks that increment the biv, but only
4102 one of these blocks is executed during each iteration. There is
4103 no good way to detect cases like this with the current structure
4104 of the loop optimizer. This code is more accurate for
4105 determining code size than run-time benefits. */
4106 benefit -= add_cost * bl->biv_count;
4108 /* Decide whether to strength-reduce this giv or to leave the code
4109 unchanged (recompute it from the biv each time it is used). This
4110 decision can be made independently for each giv. */
4113 /* Attempt to guess whether autoincrement will handle some of the
4114 new add insns; if so, increase BENEFIT (undo the subtraction of
4115 add_cost that was done above). */
4116 if (v->giv_type == DEST_ADDR
4117 /* Increasing the benefit is risky, since this is only a guess.
4118 Avoid increasing register pressure in cases where there would
4119 be no other benefit from reducing this giv. */
4121 && GET_CODE (v->mult_val) == CONST_INT)
4123 if (HAVE_POST_INCREMENT
4124 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4125 benefit += add_cost * bl->biv_count;
4126 else if (HAVE_PRE_INCREMENT
4127 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4128 benefit += add_cost * bl->biv_count;
4129 else if (HAVE_POST_DECREMENT
4130 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4131 benefit += add_cost * bl->biv_count;
4132 else if (HAVE_PRE_DECREMENT
4133 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4134 benefit += add_cost * bl->biv_count;
4142 /* Free IV structures for LOOP. */
4145 loop_ivs_free (loop)
4148 struct loop_ivs *ivs = LOOP_IVS (loop);
4149 struct iv_class *iv = ivs->list;
4155 struct iv_class *next = iv->next;
4156 struct induction *induction;
4157 struct induction *next_induction;
4159 for (induction = iv->biv; induction; induction = next_induction)
4161 next_induction = induction->next_iv;
4164 for (induction = iv->giv; induction; induction = next_induction)
4166 next_induction = induction->next_iv;
4176 /* Perform strength reduction and induction variable elimination.
4178 Pseudo registers created during this function will be beyond the
4179 last valid index in several tables including
4180 REGS->ARRAY[I].N_TIMES_SET and REGNO_LAST_UID. This does not cause a
4181 problem here, because the added registers cannot be givs outside of
4182 their loop, and hence will never be reconsidered. But scan_loop
4183 must check regnos to make sure they are in bounds. */
4186 strength_reduce (loop, insn_count, flags)
4191 struct loop_info *loop_info = LOOP_INFO (loop);
4192 struct loop_regs *regs = LOOP_REGS (loop);
4193 struct loop_ivs *ivs = LOOP_IVS (loop);
4195 /* Temporary list pointer for traversing ivs->list. */
4196 struct iv_class *bl;
4197 /* Ratio of extra register life span we can justify
4198 for saving an instruction. More if loop doesn't call subroutines
4199 since in that case saving an insn makes more difference
4200 and more registers are available. */
4201 /* ??? could set this to last value of threshold in move_movables */
4202 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
4203 /* Map of pseudo-register replacements. */
4204 rtx *reg_map = NULL;
4206 rtx end_insert_before;
4207 int unrolled_insn_copies = 0;
4208 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
4210 addr_placeholder = gen_reg_rtx (Pmode);
4212 /* Save insn immediately after the loop_end. Insns inserted after loop_end
4213 must be put before this insn, so that they will appear in the right
4214 order (i.e. loop order).
4216 If loop_end is the end of the current function, then emit a
4217 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
4219 if (NEXT_INSN (loop->end) != 0)
4220 end_insert_before = NEXT_INSN (loop->end);
4222 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop->end);
4224 ivs->n_regs = max_reg_before_loop;
4225 ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
4227 /* Find all BIVs in loop. */
4228 loop_bivs_find (loop);
4230 /* Exit if there are no bivs. */
4233 /* Can still unroll the loop anyways, but indicate that there is no
4234 strength reduction info available. */
4235 if (flags & LOOP_UNROLL)
4236 unroll_loop (loop, insn_count, end_insert_before, 0);
4238 loop_ivs_free (loop);
4242 /* Determine how BIVS are initialised by looking through pre-header
4243 extended basic block. */
4244 loop_bivs_init_find (loop);
4246 /* Look at the each biv and see if we can say anything better about its
4247 initial value from any initializing insns set up above. */
4248 loop_bivs_check (loop);
4250 /* Search the loop for general induction variables. */
4251 loop_givs_find (loop);
4253 /* Try to calculate and save the number of loop iterations. This is
4254 set to zero if the actual number can not be calculated. This must
4255 be called after all giv's have been identified, since otherwise it may
4256 fail if the iteration variable is a giv. */
4257 loop_iterations (loop);
4259 /* Now for each giv for which we still don't know whether or not it is
4260 replaceable, check to see if it is replaceable because its final value
4261 can be calculated. This must be done after loop_iterations is called,
4262 so that final_giv_value will work correctly. */
4263 loop_givs_check (loop);
4265 /* Try to prove that the loop counter variable (if any) is always
4266 nonnegative; if so, record that fact with a REG_NONNEG note
4267 so that "decrement and branch until zero" insn can be used. */
4268 check_dbra_loop (loop, insn_count);
4270 /* Create reg_map to hold substitutions for replaceable giv regs.
4271 Some givs might have been made from biv increments, so look at
4272 ivs->reg_iv_type for a suitable size. */
4273 reg_map_size = ivs->n_regs;
4274 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
4276 /* Examine each iv class for feasibility of strength reduction/induction
4277 variable elimination. */
4279 for (bl = ivs->list; bl; bl = bl->next)
4281 struct induction *v;
4284 /* Test whether it will be possible to eliminate this biv
4285 provided all givs are reduced. */
4286 bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
4288 /* Check each extension dependent giv in this class to see if its
4289 root biv is safe from wrapping in the interior mode. */
4290 check_ext_dependant_givs (bl, loop_info);
4292 /* Combine all giv's for this iv_class. */
4293 combine_givs (regs, bl);
4295 /* This will be true at the end, if all givs which depend on this
4296 biv have been strength reduced.
4297 We can't (currently) eliminate the biv unless this is so. */
4298 bl->all_reduced = 1;
4300 for (v = bl->giv; v; v = v->next_iv)
4302 struct induction *tv;
4304 if (v->ignore || v->same)
4307 benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
4309 /* If an insn is not to be strength reduced, then set its ignore
4310 flag, and clear bl->all_reduced. */
4312 /* A giv that depends on a reversed biv must be reduced if it is
4313 used after the loop exit, otherwise, it would have the wrong
4314 value after the loop exit. To make it simple, just reduce all
4315 of such giv's whether or not we know they are used after the loop
4318 if (! flag_reduce_all_givs
4319 && v->lifetime * threshold * benefit < insn_count
4322 if (loop_dump_stream)
4323 fprintf (loop_dump_stream,
4324 "giv of insn %d not worth while, %d vs %d.\n",
4326 v->lifetime * threshold * benefit, insn_count);
4328 bl->all_reduced = 0;
4332 /* Check that we can increment the reduced giv without a
4333 multiply insn. If not, reject it. */
4335 for (tv = bl->biv; tv; tv = tv->next_iv)
4336 if (tv->mult_val == const1_rtx
4337 && ! product_cheap_p (tv->add_val, v->mult_val))
4339 if (loop_dump_stream)
4340 fprintf (loop_dump_stream,
4341 "giv of insn %d: would need a multiply.\n",
4342 INSN_UID (v->insn));
4344 bl->all_reduced = 0;
4350 /* Check for givs whose first use is their definition and whose
4351 last use is the definition of another giv. If so, it is likely
4352 dead and should not be used to derive another giv nor to
4354 loop_givs_dead_check (loop, bl);
4356 /* Reduce each giv that we decided to reduce. */
4357 loop_givs_reduce (loop, bl);
4359 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4362 For each giv register that can be reduced now: if replaceable,
4363 substitute reduced reg wherever the old giv occurs;
4364 else add new move insn "giv_reg = reduced_reg". */
4365 loop_givs_rescan (loop, bl, reg_map, end_insert_before);
4367 /* All the givs based on the biv bl have been reduced if they
4370 /* For each giv not marked as maybe dead that has been combined with a
4371 second giv, clear any "maybe dead" mark on that second giv.
4372 v->new_reg will either be or refer to the register of the giv it
4375 Doing this clearing avoids problems in biv elimination where
4376 a giv's new_reg is a complex value that can't be put in the
4377 insn but the giv combined with (with a reg as new_reg) is
4378 marked maybe_dead. Since the register will be used in either
4379 case, we'd prefer it be used from the simpler giv. */
4381 for (v = bl->giv; v; v = v->next_iv)
4382 if (! v->maybe_dead && v->same)
4383 v->same->maybe_dead = 0;
4385 /* Try to eliminate the biv, if it is a candidate.
4386 This won't work if ! bl->all_reduced,
4387 since the givs we planned to use might not have been reduced.
4389 We have to be careful that we didn't initially think we could
4390 eliminate this biv because of a giv that we now think may be
4391 dead and shouldn't be used as a biv replacement.
4393 Also, there is the possibility that we may have a giv that looks
4394 like it can be used to eliminate a biv, but the resulting insn
4395 isn't valid. This can happen, for example, on the 88k, where a
4396 JUMP_INSN can compare a register only with zero. Attempts to
4397 replace it with a compare with a constant will fail.
4399 Note that in cases where this call fails, we may have replaced some
4400 of the occurrences of the biv with a giv, but no harm was done in
4401 doing so in the rare cases where it can occur. */
4403 if (bl->all_reduced == 1 && bl->eliminable
4404 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4406 /* ?? If we created a new test to bypass the loop entirely,
4407 or otherwise drop straight in, based on this test, then
4408 we might want to rewrite it also. This way some later
4409 pass has more hope of removing the initialization of this
4412 /* If final_value != 0, then the biv may be used after loop end
4413 and we must emit an insn to set it just in case.
4415 Reversed bivs already have an insn after the loop setting their
4416 value, so we don't need another one. We can't calculate the
4417 proper final value for such a biv here anyways. */
4418 if (bl->final_value && ! bl->reversed)
4422 /* If the loop has multiple exits, emit the insn before the
4423 loop to ensure that it will always be executed no matter
4424 how the loop exits. Otherwise, emit the insn after the
4425 loop, since this is slightly more efficient. */
4426 if (loop->exit_count)
4427 insert_before = loop->start;
4429 insert_before = end_insert_before;
4431 emit_insn_before (gen_move_insn (bl->biv->dest_reg,
4436 if (loop_dump_stream)
4437 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4442 /* Go through all the instructions in the loop, making all the
4443 register substitutions scheduled in REG_MAP. */
4445 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
4446 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4447 || GET_CODE (p) == CALL_INSN)
4449 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4450 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4454 if (loop_info->n_iterations > 0)
4456 /* When we completely unroll a loop we will likely not need the increment
4457 of the loop BIV and we will not need the conditional branch at the
4459 unrolled_insn_copies = insn_count - 2;
4462 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4463 need the comparison before the conditional branch at the end of the
4465 unrolled_insn_copies -= 1;
4468 /* We'll need one copy for each loop iteration. */
4469 unrolled_insn_copies *= loop_info->n_iterations;
4471 /* A little slop to account for the ability to remove initialization
4472 code, better CSE, and other secondary benefits of completely
4473 unrolling some loops. */
4474 unrolled_insn_copies -= 1;
4476 /* Clamp the value. */
4477 if (unrolled_insn_copies < 0)
4478 unrolled_insn_copies = 0;
4481 /* Unroll loops from within strength reduction so that we can use the
4482 induction variable information that strength_reduce has already
4483 collected. Always unroll loops that would be as small or smaller
4484 unrolled than when rolled. */
4485 if ((flags & LOOP_UNROLL)
4486 || (loop_info->n_iterations > 0
4487 && unrolled_insn_copies <= insn_count))
4488 unroll_loop (loop, insn_count, end_insert_before, 1);
4490 #ifdef HAVE_doloop_end
4491 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4492 doloop_optimize (loop);
4493 #endif /* HAVE_doloop_end */
4495 if (loop_dump_stream)
4496 fprintf (loop_dump_stream, "\n");
4498 loop_ivs_free (loop);
4503 /*Record all basic induction variables calculated in the insn. */
4505 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4508 int not_every_iteration;
4511 struct loop_ivs *ivs = LOOP_IVS (loop);
4518 if (GET_CODE (p) == INSN
4519 && (set = single_set (p))
4520 && GET_CODE (SET_DEST (set)) == REG)
4522 dest_reg = SET_DEST (set);
4523 if (REGNO (dest_reg) < max_reg_before_loop
4524 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4525 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4527 if (basic_induction_var (loop, SET_SRC (set),
4528 GET_MODE (SET_SRC (set)),
4529 dest_reg, p, &inc_val, &mult_val,
4532 /* It is a possible basic induction variable.
4533 Create and initialize an induction structure for it. */
4536 = (struct induction *) xmalloc (sizeof (struct induction));
4538 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4539 not_every_iteration, maybe_multiple);
4540 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4542 else if (REGNO (dest_reg) < ivs->n_regs)
4543 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4549 /* Record all givs calculated in the insn.
4550 A register is a giv if: it is only set once, it is a function of a
4551 biv and a constant (or invariant), and it is not a biv. */
4553 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4556 int not_every_iteration;
4559 struct loop_regs *regs = LOOP_REGS (loop);
4562 /* Look for a general induction variable in a register. */
4563 if (GET_CODE (p) == INSN
4564 && (set = single_set (p))
4565 && GET_CODE (SET_DEST (set)) == REG
4566 && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
4575 rtx last_consec_insn;
4577 dest_reg = SET_DEST (set);
4578 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4581 if (/* SET_SRC is a giv. */
4582 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4583 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4584 /* Equivalent expression is a giv. */
4585 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4586 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4587 &add_val, &mult_val, &ext_val, 0,
4588 &benefit, VOIDmode)))
4589 /* Don't try to handle any regs made by loop optimization.
4590 We have nothing on them in regno_first_uid, etc. */
4591 && REGNO (dest_reg) < max_reg_before_loop
4592 /* Don't recognize a BASIC_INDUCT_VAR here. */
4593 && dest_reg != src_reg
4594 /* This must be the only place where the register is set. */
4595 && (regs->array[REGNO (dest_reg)].n_times_set == 1
4596 /* or all sets must be consecutive and make a giv. */
4597 || (benefit = consec_sets_giv (loop, benefit, p,
4599 &add_val, &mult_val, &ext_val,
4600 &last_consec_insn))))
4603 = (struct induction *) xmalloc (sizeof (struct induction));
4605 /* If this is a library call, increase benefit. */
4606 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4607 benefit += libcall_benefit (p);
4609 /* Skip the consecutive insns, if there are any. */
4610 if (regs->array[REGNO (dest_reg)].n_times_set != 1)
4611 p = last_consec_insn;
4613 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4614 ext_val, benefit, DEST_REG, not_every_iteration,
4615 maybe_multiple, NULL_PTR);
4620 #ifndef DONT_REDUCE_ADDR
4621 /* Look for givs which are memory addresses. */
4622 /* This resulted in worse code on a VAX 8600. I wonder if it
4624 if (GET_CODE (p) == INSN)
4625 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4629 /* Update the status of whether giv can derive other givs. This can
4630 change when we pass a label or an insn that updates a biv. */
4631 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4632 || GET_CODE (p) == CODE_LABEL)
4633 update_giv_derive (loop, p);
4637 /* Return 1 if X is a valid source for an initial value (or as value being
4638 compared against in an initial test).
4640 X must be either a register or constant and must not be clobbered between
4641 the current insn and the start of the loop.
4643 INSN is the insn containing X. */
4646 valid_initial_value_p (x, insn, call_seen, loop_start)
4655 /* Only consider pseudos we know about initialized in insns whose luids
4657 if (GET_CODE (x) != REG
4658 || REGNO (x) >= max_reg_before_loop)
4661 /* Don't use call-clobbered registers across a call which clobbers it. On
4662 some machines, don't use any hard registers at all. */
4663 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4664 && (SMALL_REGISTER_CLASSES
4665 || (call_used_regs[REGNO (x)] && call_seen)))
4668 /* Don't use registers that have been clobbered before the start of the
4670 if (reg_set_between_p (x, insn, loop_start))
4676 /* Scan X for memory refs and check each memory address
4677 as a possible giv. INSN is the insn whose pattern X comes from.
4678 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4679 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4680 more thanonce in each loop iteration. */
4683 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4684 const struct loop *loop;
4687 int not_every_iteration, maybe_multiple;
4690 register enum rtx_code code;
4691 register const char *fmt;
4696 code = GET_CODE (x);
4721 /* This code used to disable creating GIVs with mult_val == 1 and
4722 add_val == 0. However, this leads to lost optimizations when
4723 it comes time to combine a set of related DEST_ADDR GIVs, since
4724 this one would not be seen. */
4726 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4727 &mult_val, &ext_val, 1, &benefit,
4730 /* Found one; record it. */
4732 = (struct induction *) xmalloc (sizeof (struct induction));
4734 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4735 add_val, ext_val, benefit, DEST_ADDR,
4736 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4738 v->mem_mode = GET_MODE (x);
4747 /* Recursively scan the subexpressions for other mem refs. */
4749 fmt = GET_RTX_FORMAT (code);
4750 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4752 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4754 else if (fmt[i] == 'E')
4755 for (j = 0; j < XVECLEN (x, i); j++)
4756 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4760 /* Fill in the data about one biv update.
4761 V is the `struct induction' in which we record the biv. (It is
4762 allocated by the caller, with alloca.)
4763 INSN is the insn that sets it.
4764 DEST_REG is the biv's reg.
4766 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4767 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4768 being set to INC_VAL.
4770 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4771 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4772 can be executed more than once per iteration. If MAYBE_MULTIPLE
4773 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4774 executed exactly once per iteration. */
4777 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4778 not_every_iteration, maybe_multiple)
4780 struct induction *v;
4786 int not_every_iteration;
4789 struct loop_ivs *ivs = LOOP_IVS (loop);
4790 struct iv_class *bl;
4793 v->src_reg = dest_reg;
4794 v->dest_reg = dest_reg;
4795 v->mult_val = mult_val;
4796 v->add_val = inc_val;
4797 v->ext_dependant = NULL_RTX;
4798 v->location = location;
4799 v->mode = GET_MODE (dest_reg);
4800 v->always_computable = ! not_every_iteration;
4801 v->always_executed = ! not_every_iteration;
4802 v->maybe_multiple = maybe_multiple;
4804 /* Add this to the reg's iv_class, creating a class
4805 if this is the first incrementation of the reg. */
4807 bl = REG_IV_CLASS (ivs, REGNO (dest_reg));
4810 /* Create and initialize new iv_class. */
4812 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4814 bl->regno = REGNO (dest_reg);
4820 /* Set initial value to the reg itself. */
4821 bl->initial_value = dest_reg;
4822 bl->final_value = 0;
4823 /* We haven't seen the initializing insn yet */
4826 bl->initial_test = 0;
4827 bl->incremented = 0;
4831 bl->total_benefit = 0;
4833 /* Add this class to ivs->list. */
4834 bl->next = ivs->list;
4837 /* Put it in the array of biv register classes. */
4838 REG_IV_CLASS (ivs, REGNO (dest_reg)) = bl;
4841 /* Update IV_CLASS entry for this biv. */
4842 v->next_iv = bl->biv;
4845 if (mult_val == const1_rtx)
4846 bl->incremented = 1;
4848 if (loop_dump_stream)
4849 loop_biv_dump (v, loop_dump_stream, 0);
4852 /* Fill in the data about one giv.
4853 V is the `struct induction' in which we record the giv. (It is
4854 allocated by the caller, with alloca.)
4855 INSN is the insn that sets it.
4856 BENEFIT estimates the savings from deleting this insn.
4857 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4858 into a register or is used as a memory address.
4860 SRC_REG is the biv reg which the giv is computed from.
4861 DEST_REG is the giv's reg (if the giv is stored in a reg).
4862 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4863 LOCATION points to the place where this giv's value appears in INSN. */
4866 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4867 benefit, type, not_every_iteration, maybe_multiple, location)
4868 const struct loop *loop;
4869 struct induction *v;
4873 rtx mult_val, add_val, ext_val;
4876 int not_every_iteration, maybe_multiple;
4879 struct loop_ivs *ivs = LOOP_IVS (loop);
4880 struct induction *b;
4881 struct iv_class *bl;
4882 rtx set = single_set (insn);
4885 /* Attempt to prove constantness of the values. */
4886 temp = simplify_rtx (add_val);
4891 v->src_reg = src_reg;
4893 v->dest_reg = dest_reg;
4894 v->mult_val = mult_val;
4895 v->add_val = add_val;
4896 v->ext_dependant = ext_val;
4897 v->benefit = benefit;
4898 v->location = location;
4900 v->combined_with = 0;
4901 v->maybe_multiple = maybe_multiple;
4903 v->derive_adjustment = 0;
4909 v->auto_inc_opt = 0;
4913 /* The v->always_computable field is used in update_giv_derive, to
4914 determine whether a giv can be used to derive another giv. For a
4915 DEST_REG giv, INSN computes a new value for the giv, so its value
4916 isn't computable if INSN insn't executed every iteration.
4917 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4918 it does not compute a new value. Hence the value is always computable
4919 regardless of whether INSN is executed each iteration. */
4921 if (type == DEST_ADDR)
4922 v->always_computable = 1;
4924 v->always_computable = ! not_every_iteration;
4926 v->always_executed = ! not_every_iteration;
4928 if (type == DEST_ADDR)
4930 v->mode = GET_MODE (*location);
4933 else /* type == DEST_REG */
4935 v->mode = GET_MODE (SET_DEST (set));
4937 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
4939 /* If the lifetime is zero, it means that this register is
4940 really a dead store. So mark this as a giv that can be
4941 ignored. This will not prevent the biv from being eliminated. */
4942 if (v->lifetime == 0)
4945 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
4946 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
4949 /* Add the giv to the class of givs computed from one biv. */
4951 bl = REG_IV_CLASS (ivs, REGNO (src_reg));
4954 v->next_iv = bl->giv;
4956 /* Don't count DEST_ADDR. This is supposed to count the number of
4957 insns that calculate givs. */
4958 if (type == DEST_REG)
4960 bl->total_benefit += benefit;
4963 /* Fatal error, biv missing for this giv? */
4966 if (type == DEST_ADDR)
4970 /* The giv can be replaced outright by the reduced register only if all
4971 of the following conditions are true:
4972 - the insn that sets the giv is always executed on any iteration
4973 on which the giv is used at all
4974 (there are two ways to deduce this:
4975 either the insn is executed on every iteration,
4976 or all uses follow that insn in the same basic block),
4977 - the giv is not used outside the loop
4978 - no assignments to the biv occur during the giv's lifetime. */
4980 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
4981 /* Previous line always fails if INSN was moved by loop opt. */
4982 && REGNO_LAST_LUID (REGNO (dest_reg))
4983 < INSN_LUID (loop->end)
4984 && (! not_every_iteration
4985 || last_use_this_basic_block (dest_reg, insn)))
4987 /* Now check that there are no assignments to the biv within the
4988 giv's lifetime. This requires two separate checks. */
4990 /* Check each biv update, and fail if any are between the first
4991 and last use of the giv.
4993 If this loop contains an inner loop that was unrolled, then
4994 the insn modifying the biv may have been emitted by the loop
4995 unrolling code, and hence does not have a valid luid. Just
4996 mark the biv as not replaceable in this case. It is not very
4997 useful as a biv, because it is used in two different loops.
4998 It is very unlikely that we would be able to optimize the giv
4999 using this biv anyways. */
5002 for (b = bl->biv; b; b = b->next_iv)
5004 if (INSN_UID (b->insn) >= max_uid_for_loop
5005 || ((INSN_LUID (b->insn)
5006 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5007 && (INSN_LUID (b->insn)
5008 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5011 v->not_replaceable = 1;
5016 /* If there are any backwards branches that go from after the
5017 biv update to before it, then this giv is not replaceable. */
5019 for (b = bl->biv; b; b = b->next_iv)
5020 if (back_branch_in_range_p (loop, b->insn))
5023 v->not_replaceable = 1;
5029 /* May still be replaceable, we don't have enough info here to
5032 v->not_replaceable = 0;
5036 /* Record whether the add_val contains a const_int, for later use by
5041 v->no_const_addval = 1;
5042 if (tem == const0_rtx)
5044 else if (CONSTANT_P (add_val))
5045 v->no_const_addval = 0;
5046 if (GET_CODE (tem) == PLUS)
5050 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5051 tem = XEXP (tem, 0);
5052 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5053 tem = XEXP (tem, 1);
5057 if (CONSTANT_P (XEXP (tem, 1)))
5058 v->no_const_addval = 0;
5062 if (loop_dump_stream)
5063 loop_giv_dump (v, loop_dump_stream, 0);
5066 /* All this does is determine whether a giv can be made replaceable because
5067 its final value can be calculated. This code can not be part of record_giv
5068 above, because final_giv_value requires that the number of loop iterations
5069 be known, and that can not be accurately calculated until after all givs
5070 have been identified. */
5073 check_final_value (loop, v)
5074 const struct loop *loop;
5075 struct induction *v;
5077 struct loop_ivs *ivs = LOOP_IVS (loop);
5078 struct iv_class *bl;
5079 rtx final_value = 0;
5081 bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
5083 /* DEST_ADDR givs will never reach here, because they are always marked
5084 replaceable above in record_giv. */
5086 /* The giv can be replaced outright by the reduced register only if all
5087 of the following conditions are true:
5088 - the insn that sets the giv is always executed on any iteration
5089 on which the giv is used at all
5090 (there are two ways to deduce this:
5091 either the insn is executed on every iteration,
5092 or all uses follow that insn in the same basic block),
5093 - its final value can be calculated (this condition is different
5094 than the one above in record_giv)
5095 - it's not used before the it's set
5096 - no assignments to the biv occur during the giv's lifetime. */
5099 /* This is only called now when replaceable is known to be false. */
5100 /* Clear replaceable, so that it won't confuse final_giv_value. */
5104 if ((final_value = final_giv_value (loop, v))
5105 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5107 int biv_increment_seen = 0, before_giv_insn = 0;
5113 /* When trying to determine whether or not a biv increment occurs
5114 during the lifetime of the giv, we can ignore uses of the variable
5115 outside the loop because final_value is true. Hence we can not
5116 use regno_last_uid and regno_first_uid as above in record_giv. */
5118 /* Search the loop to determine whether any assignments to the
5119 biv occur during the giv's lifetime. Start with the insn
5120 that sets the giv, and search around the loop until we come
5121 back to that insn again.
5123 Also fail if there is a jump within the giv's lifetime that jumps
5124 to somewhere outside the lifetime but still within the loop. This
5125 catches spaghetti code where the execution order is not linear, and
5126 hence the above test fails. Here we assume that the giv lifetime
5127 does not extend from one iteration of the loop to the next, so as
5128 to make the test easier. Since the lifetime isn't known yet,
5129 this requires two loops. See also record_giv above. */
5131 last_giv_use = v->insn;
5138 before_giv_insn = 1;
5139 p = NEXT_INSN (loop->start);
5144 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5145 || GET_CODE (p) == CALL_INSN)
5147 /* It is possible for the BIV increment to use the GIV if we
5148 have a cycle. Thus we must be sure to check each insn for
5149 both BIV and GIV uses, and we must check for BIV uses
5152 if (! biv_increment_seen
5153 && reg_set_p (v->src_reg, PATTERN (p)))
5154 biv_increment_seen = 1;
5156 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5158 if (biv_increment_seen || before_giv_insn)
5161 v->not_replaceable = 1;
5169 /* Now that the lifetime of the giv is known, check for branches
5170 from within the lifetime to outside the lifetime if it is still
5180 p = NEXT_INSN (loop->start);
5181 if (p == last_giv_use)
5184 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5185 && LABEL_NAME (JUMP_LABEL (p))
5186 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5187 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5188 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5189 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5192 v->not_replaceable = 1;
5194 if (loop_dump_stream)
5195 fprintf (loop_dump_stream,
5196 "Found branch outside giv lifetime.\n");
5203 /* If it is replaceable, then save the final value. */
5205 v->final_value = final_value;
5208 if (loop_dump_stream && v->replaceable)
5209 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5210 INSN_UID (v->insn), REGNO (v->dest_reg));
5213 /* Update the status of whether a giv can derive other givs.
5215 We need to do something special if there is or may be an update to the biv
5216 between the time the giv is defined and the time it is used to derive
5219 In addition, a giv that is only conditionally set is not allowed to
5220 derive another giv once a label has been passed.
5222 The cases we look at are when a label or an update to a biv is passed. */
5225 update_giv_derive (loop, p)
5226 const struct loop *loop;
5229 struct loop_ivs *ivs = LOOP_IVS (loop);
5230 struct iv_class *bl;
5231 struct induction *biv, *giv;
5235 /* Search all IV classes, then all bivs, and finally all givs.
5237 There are three cases we are concerned with. First we have the situation
5238 of a giv that is only updated conditionally. In that case, it may not
5239 derive any givs after a label is passed.
5241 The second case is when a biv update occurs, or may occur, after the
5242 definition of a giv. For certain biv updates (see below) that are
5243 known to occur between the giv definition and use, we can adjust the
5244 giv definition. For others, or when the biv update is conditional,
5245 we must prevent the giv from deriving any other givs. There are two
5246 sub-cases within this case.
5248 If this is a label, we are concerned with any biv update that is done
5249 conditionally, since it may be done after the giv is defined followed by
5250 a branch here (actually, we need to pass both a jump and a label, but
5251 this extra tracking doesn't seem worth it).
5253 If this is a jump, we are concerned about any biv update that may be
5254 executed multiple times. We are actually only concerned about
5255 backward jumps, but it is probably not worth performing the test
5256 on the jump again here.
5258 If this is a biv update, we must adjust the giv status to show that a
5259 subsequent biv update was performed. If this adjustment cannot be done,
5260 the giv cannot derive further givs. */
5262 for (bl = ivs->list; bl; bl = bl->next)
5263 for (biv = bl->biv; biv; biv = biv->next_iv)
5264 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5267 for (giv = bl->giv; giv; giv = giv->next_iv)
5269 /* If cant_derive is already true, there is no point in
5270 checking all of these conditions again. */
5271 if (giv->cant_derive)
5274 /* If this giv is conditionally set and we have passed a label,
5275 it cannot derive anything. */
5276 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5277 giv->cant_derive = 1;
5279 /* Skip givs that have mult_val == 0, since
5280 they are really invariants. Also skip those that are
5281 replaceable, since we know their lifetime doesn't contain
5283 else if (giv->mult_val == const0_rtx || giv->replaceable)
5286 /* The only way we can allow this giv to derive another
5287 is if this is a biv increment and we can form the product
5288 of biv->add_val and giv->mult_val. In this case, we will
5289 be able to compute a compensation. */
5290 else if (biv->insn == p)
5295 if (biv->mult_val == const1_rtx)
5296 tem = simplify_giv_expr (loop,
5297 gen_rtx_MULT (giv->mode,
5300 &ext_val_dummy, &dummy);
5302 if (tem && giv->derive_adjustment)
5303 tem = simplify_giv_expr
5305 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5306 &ext_val_dummy, &dummy);
5309 giv->derive_adjustment = tem;
5311 giv->cant_derive = 1;
5313 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5314 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5315 giv->cant_derive = 1;
5320 /* Check whether an insn is an increment legitimate for a basic induction var.
5321 X is the source of insn P, or a part of it.
5322 MODE is the mode in which X should be interpreted.
5324 DEST_REG is the putative biv, also the destination of the insn.
5325 We accept patterns of these forms:
5326 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5327 REG = INVARIANT + REG
5329 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5330 store the additive term into *INC_VAL, and store the place where
5331 we found the additive term into *LOCATION.
5333 If X is an assignment of an invariant into DEST_REG, we set
5334 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5336 We also want to detect a BIV when it corresponds to a variable
5337 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5338 of the variable may be a PLUS that adds a SUBREG of that variable to
5339 an invariant and then sign- or zero-extends the result of the PLUS
5342 Most GIVs in such cases will be in the promoted mode, since that is the
5343 probably the natural computation mode (and almost certainly the mode
5344 used for addresses) on the machine. So we view the pseudo-reg containing
5345 the variable as the BIV, as if it were simply incremented.
5347 Note that treating the entire pseudo as a BIV will result in making
5348 simple increments to any GIVs based on it. However, if the variable
5349 overflows in its declared mode but not its promoted mode, the result will
5350 be incorrect. This is acceptable if the variable is signed, since
5351 overflows in such cases are undefined, but not if it is unsigned, since
5352 those overflows are defined. So we only check for SIGN_EXTEND and
5355 If we cannot find a biv, we return 0. */
5358 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5359 const struct loop *loop;
5361 enum machine_mode mode;
5368 register enum rtx_code code;
5372 code = GET_CODE (x);
5377 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5378 || (GET_CODE (XEXP (x, 0)) == SUBREG
5379 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5380 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5382 argp = &XEXP (x, 1);
5384 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5385 || (GET_CODE (XEXP (x, 1)) == SUBREG
5386 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5387 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5389 argp = &XEXP (x, 0);
5395 if (loop_invariant_p (loop, arg) != 1)
5398 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5399 *mult_val = const1_rtx;
5404 /* If this is a SUBREG for a promoted variable, check the inner
5406 if (SUBREG_PROMOTED_VAR_P (x))
5407 return basic_induction_var (loop, SUBREG_REG (x),
5408 GET_MODE (SUBREG_REG (x)),
5409 dest_reg, p, inc_val, mult_val, location);
5413 /* If this register is assigned in a previous insn, look at its
5414 source, but don't go outside the loop or past a label. */
5416 /* If this sets a register to itself, we would repeat any previous
5417 biv increment if we applied this strategy blindly. */
5418 if (rtx_equal_p (dest_reg, x))
5427 insn = PREV_INSN (insn);
5429 while (insn && GET_CODE (insn) == NOTE
5430 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5434 set = single_set (insn);
5437 dest = SET_DEST (set);
5439 || (GET_CODE (dest) == SUBREG
5440 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5441 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5442 && SUBREG_REG (dest) == x))
5443 return basic_induction_var (loop, SET_SRC (set),
5444 (GET_MODE (SET_SRC (set)) == VOIDmode
5446 : GET_MODE (SET_SRC (set))),
5448 inc_val, mult_val, location);
5450 while (GET_CODE (dest) == SIGN_EXTRACT
5451 || GET_CODE (dest) == ZERO_EXTRACT
5452 || GET_CODE (dest) == SUBREG
5453 || GET_CODE (dest) == STRICT_LOW_PART)
5454 dest = XEXP (dest, 0);
5460 /* Can accept constant setting of biv only when inside inner most loop.
5461 Otherwise, a biv of an inner loop may be incorrectly recognized
5462 as a biv of the outer loop,
5463 causing code to be moved INTO the inner loop. */
5465 if (loop_invariant_p (loop, x) != 1)
5470 /* convert_modes aborts if we try to convert to or from CCmode, so just
5471 exclude that case. It is very unlikely that a condition code value
5472 would be a useful iterator anyways. */
5473 if (loop->level == 1
5474 && GET_MODE_CLASS (mode) != MODE_CC
5475 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5477 /* Possible bug here? Perhaps we don't know the mode of X. */
5478 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5479 *mult_val = const0_rtx;
5486 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5487 dest_reg, p, inc_val, mult_val, location);
5490 /* Similar, since this can be a sign extension. */
5491 for (insn = PREV_INSN (p);
5492 (insn && GET_CODE (insn) == NOTE
5493 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5494 insn = PREV_INSN (insn))
5498 set = single_set (insn);
5500 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5501 && set && SET_DEST (set) == XEXP (x, 0)
5502 && GET_CODE (XEXP (x, 1)) == CONST_INT
5503 && INTVAL (XEXP (x, 1)) >= 0
5504 && GET_CODE (SET_SRC (set)) == ASHIFT
5505 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5506 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5507 GET_MODE (XEXP (x, 0)),
5508 dest_reg, insn, inc_val, mult_val,
5517 /* A general induction variable (giv) is any quantity that is a linear
5518 function of a basic induction variable,
5519 i.e. giv = biv * mult_val + add_val.
5520 The coefficients can be any loop invariant quantity.
5521 A giv need not be computed directly from the biv;
5522 it can be computed by way of other givs. */
5524 /* Determine whether X computes a giv.
5525 If it does, return a nonzero value
5526 which is the benefit from eliminating the computation of X;
5527 set *SRC_REG to the register of the biv that it is computed from;
5528 set *ADD_VAL and *MULT_VAL to the coefficients,
5529 such that the value of X is biv * mult + add; */
5532 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5533 is_addr, pbenefit, addr_mode)
5534 const struct loop *loop;
5542 enum machine_mode addr_mode;
5544 struct loop_ivs *ivs = LOOP_IVS (loop);
5547 /* If this is an invariant, forget it, it isn't a giv. */
5548 if (loop_invariant_p (loop, x) == 1)
5552 *ext_val = NULL_RTX;
5553 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5557 switch (GET_CODE (x))
5561 /* Since this is now an invariant and wasn't before, it must be a giv
5562 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5564 *src_reg = ivs->list->biv->dest_reg;
5565 *mult_val = const0_rtx;
5570 /* This is equivalent to a BIV. */
5572 *mult_val = const1_rtx;
5573 *add_val = const0_rtx;
5577 /* Either (plus (biv) (invar)) or
5578 (plus (mult (biv) (invar_1)) (invar_2)). */
5579 if (GET_CODE (XEXP (x, 0)) == MULT)
5581 *src_reg = XEXP (XEXP (x, 0), 0);
5582 *mult_val = XEXP (XEXP (x, 0), 1);
5586 *src_reg = XEXP (x, 0);
5587 *mult_val = const1_rtx;
5589 *add_val = XEXP (x, 1);
5593 /* ADD_VAL is zero. */
5594 *src_reg = XEXP (x, 0);
5595 *mult_val = XEXP (x, 1);
5596 *add_val = const0_rtx;
5603 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5604 unless they are CONST_INT). */
5605 if (GET_CODE (*add_val) == USE)
5606 *add_val = XEXP (*add_val, 0);
5607 if (GET_CODE (*mult_val) == USE)
5608 *mult_val = XEXP (*mult_val, 0);
5611 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5613 *pbenefit += rtx_cost (orig_x, SET);
5615 /* Always return true if this is a giv so it will be detected as such,
5616 even if the benefit is zero or negative. This allows elimination
5617 of bivs that might otherwise not be eliminated. */
5621 /* Given an expression, X, try to form it as a linear function of a biv.
5622 We will canonicalize it to be of the form
5623 (plus (mult (BIV) (invar_1))
5625 with possible degeneracies.
5627 The invariant expressions must each be of a form that can be used as a
5628 machine operand. We surround then with a USE rtx (a hack, but localized
5629 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5630 routine; it is the caller's responsibility to strip them.
5632 If no such canonicalization is possible (i.e., two biv's are used or an
5633 expression that is neither invariant nor a biv or giv), this routine
5636 For a non-zero return, the result will have a code of CONST_INT, USE,
5637 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5639 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5641 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5642 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5645 simplify_giv_expr (loop, x, ext_val, benefit)
5646 const struct loop *loop;
5651 struct loop_ivs *ivs = LOOP_IVS (loop);
5652 struct loop_regs *regs = LOOP_REGS (loop);
5653 enum machine_mode mode = GET_MODE (x);
5657 /* If this is not an integer mode, or if we cannot do arithmetic in this
5658 mode, this can't be a giv. */
5659 if (mode != VOIDmode
5660 && (GET_MODE_CLASS (mode) != MODE_INT
5661 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5664 switch (GET_CODE (x))
5667 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5668 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5669 if (arg0 == 0 || arg1 == 0)
5672 /* Put constant last, CONST_INT last if both constant. */
5673 if ((GET_CODE (arg0) == USE
5674 || GET_CODE (arg0) == CONST_INT)
5675 && ! ((GET_CODE (arg0) == USE
5676 && GET_CODE (arg1) == USE)
5677 || GET_CODE (arg1) == CONST_INT))
5678 tem = arg0, arg0 = arg1, arg1 = tem;
5680 /* Handle addition of zero, then addition of an invariant. */
5681 if (arg1 == const0_rtx)
5683 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5684 switch (GET_CODE (arg0))
5688 /* Adding two invariants must result in an invariant, so enclose
5689 addition operation inside a USE and return it. */
5690 if (GET_CODE (arg0) == USE)
5691 arg0 = XEXP (arg0, 0);
5692 if (GET_CODE (arg1) == USE)
5693 arg1 = XEXP (arg1, 0);
5695 if (GET_CODE (arg0) == CONST_INT)
5696 tem = arg0, arg0 = arg1, arg1 = tem;
5697 if (GET_CODE (arg1) == CONST_INT)
5698 tem = sge_plus_constant (arg0, arg1);
5700 tem = sge_plus (mode, arg0, arg1);
5702 if (GET_CODE (tem) != CONST_INT)
5703 tem = gen_rtx_USE (mode, tem);
5708 /* biv + invar or mult + invar. Return sum. */
5709 return gen_rtx_PLUS (mode, arg0, arg1);
5712 /* (a + invar_1) + invar_2. Associate. */
5714 simplify_giv_expr (loop,
5726 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5727 MULT to reduce cases. */
5728 if (GET_CODE (arg0) == REG)
5729 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5730 if (GET_CODE (arg1) == REG)
5731 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5733 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5734 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5735 Recurse to associate the second PLUS. */
5736 if (GET_CODE (arg1) == MULT)
5737 tem = arg0, arg0 = arg1, arg1 = tem;
5739 if (GET_CODE (arg1) == PLUS)
5741 simplify_giv_expr (loop,
5743 gen_rtx_PLUS (mode, arg0,
5748 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5749 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5752 if (!rtx_equal_p (arg0, arg1))
5755 return simplify_giv_expr (loop,
5764 /* Handle "a - b" as "a + b * (-1)". */
5765 return simplify_giv_expr (loop,
5774 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5775 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5776 if (arg0 == 0 || arg1 == 0)
5779 /* Put constant last, CONST_INT last if both constant. */
5780 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5781 && GET_CODE (arg1) != CONST_INT)
5782 tem = arg0, arg0 = arg1, arg1 = tem;
5784 /* If second argument is not now constant, not giv. */
5785 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5788 /* Handle multiply by 0 or 1. */
5789 if (arg1 == const0_rtx)
5792 else if (arg1 == const1_rtx)
5795 switch (GET_CODE (arg0))
5798 /* biv * invar. Done. */
5799 return gen_rtx_MULT (mode, arg0, arg1);
5802 /* Product of two constants. */
5803 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5806 /* invar * invar is a giv, but attempt to simplify it somehow. */
5807 if (GET_CODE (arg1) != CONST_INT)
5810 arg0 = XEXP (arg0, 0);
5811 if (GET_CODE (arg0) == MULT)
5813 /* (invar_0 * invar_1) * invar_2. Associate. */
5814 return simplify_giv_expr (loop,
5823 /* Porpagate the MULT expressions to the intermost nodes. */
5824 else if (GET_CODE (arg0) == PLUS)
5826 /* (invar_0 + invar_1) * invar_2. Distribute. */
5827 return simplify_giv_expr (loop,
5839 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
5842 /* (a * invar_1) * invar_2. Associate. */
5843 return simplify_giv_expr (loop,
5852 /* (a + invar_1) * invar_2. Distribute. */
5853 return simplify_giv_expr (loop,
5868 /* Shift by constant is multiply by power of two. */
5869 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5873 simplify_giv_expr (loop,
5876 GEN_INT ((HOST_WIDE_INT) 1
5877 << INTVAL (XEXP (x, 1)))),
5881 /* "-a" is "a * (-1)" */
5882 return simplify_giv_expr (loop,
5883 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
5887 /* "~a" is "-a - 1". Silly, but easy. */
5888 return simplify_giv_expr (loop,
5889 gen_rtx_MINUS (mode,
5890 gen_rtx_NEG (mode, XEXP (x, 0)),
5895 /* Already in proper form for invariant. */
5901 /* Conditionally recognize extensions of simple IVs. After we've
5902 computed loop traversal counts and verified the range of the
5903 source IV, we'll reevaluate this as a GIV. */
5904 if (*ext_val == NULL_RTX)
5906 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5907 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
5909 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
5916 /* If this is a new register, we can't deal with it. */
5917 if (REGNO (x) >= max_reg_before_loop)
5920 /* Check for biv or giv. */
5921 switch (REG_IV_TYPE (ivs, REGNO (x)))
5925 case GENERAL_INDUCT:
5927 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
5929 /* Form expression from giv and add benefit. Ensure this giv
5930 can derive another and subtract any needed adjustment if so. */
5932 /* Increasing the benefit here is risky. The only case in which it
5933 is arguably correct is if this is the only use of V. In other
5934 cases, this will artificially inflate the benefit of the current
5935 giv, and lead to suboptimal code. Thus, it is disabled, since
5936 potentially not reducing an only marginally beneficial giv is
5937 less harmful than reducing many givs that are not really
5940 rtx single_use = regs->array[REGNO (x)].single_usage;
5941 if (single_use && single_use != const0_rtx)
5942 *benefit += v->benefit;
5948 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
5949 v->src_reg, v->mult_val),
5952 if (v->derive_adjustment)
5953 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
5954 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
5957 if (!v->ext_dependant)
5962 *ext_val = v->ext_dependant;
5970 /* If it isn't an induction variable, and it is invariant, we
5971 may be able to simplify things further by looking through
5972 the bits we just moved outside the loop. */
5973 if (loop_invariant_p (loop, x) == 1)
5976 struct loop_movables *movables = LOOP_MOVABLES (loop);
5978 for (m = movables->head; m; m = m->next)
5979 if (rtx_equal_p (x, m->set_dest))
5981 /* Ok, we found a match. Substitute and simplify. */
5983 /* If we match another movable, we must use that, as
5984 this one is going away. */
5986 return simplify_giv_expr (loop, m->match->set_dest,
5989 /* If consec is non-zero, this is a member of a group of
5990 instructions that were moved together. We handle this
5991 case only to the point of seeking to the last insn and
5992 looking for a REG_EQUAL. Fail if we don't find one. */
5999 tem = NEXT_INSN (tem);
6003 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6005 tem = XEXP (tem, 0);
6009 tem = single_set (m->insn);
6011 tem = SET_SRC (tem);
6016 /* What we are most interested in is pointer
6017 arithmetic on invariants -- only take
6018 patterns we may be able to do something with. */
6019 if (GET_CODE (tem) == PLUS
6020 || GET_CODE (tem) == MULT
6021 || GET_CODE (tem) == ASHIFT
6022 || GET_CODE (tem) == CONST_INT
6023 || GET_CODE (tem) == SYMBOL_REF)
6025 tem = simplify_giv_expr (loop, tem, ext_val,
6030 else if (GET_CODE (tem) == CONST
6031 && GET_CODE (XEXP (tem, 0)) == PLUS
6032 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6033 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6035 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6047 /* Fall through to general case. */
6049 /* If invariant, return as USE (unless CONST_INT).
6050 Otherwise, not giv. */
6051 if (GET_CODE (x) == USE)
6054 if (loop_invariant_p (loop, x) == 1)
6056 if (GET_CODE (x) == CONST_INT)
6058 if (GET_CODE (x) == CONST
6059 && GET_CODE (XEXP (x, 0)) == PLUS
6060 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6061 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6063 return gen_rtx_USE (mode, x);
6070 /* This routine folds invariants such that there is only ever one
6071 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6074 sge_plus_constant (x, c)
6077 if (GET_CODE (x) == CONST_INT)
6078 return GEN_INT (INTVAL (x) + INTVAL (c));
6079 else if (GET_CODE (x) != PLUS)
6080 return gen_rtx_PLUS (GET_MODE (x), x, c);
6081 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6083 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6084 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6086 else if (GET_CODE (XEXP (x, 0)) == PLUS
6087 || GET_CODE (XEXP (x, 1)) != PLUS)
6089 return gen_rtx_PLUS (GET_MODE (x),
6090 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6094 return gen_rtx_PLUS (GET_MODE (x),
6095 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6100 sge_plus (mode, x, y)
6101 enum machine_mode mode;
6104 while (GET_CODE (y) == PLUS)
6106 rtx a = XEXP (y, 0);
6107 if (GET_CODE (a) == CONST_INT)
6108 x = sge_plus_constant (x, a);
6110 x = gen_rtx_PLUS (mode, x, a);
6113 if (GET_CODE (y) == CONST_INT)
6114 x = sge_plus_constant (x, y);
6116 x = gen_rtx_PLUS (mode, x, y);
6120 /* Help detect a giv that is calculated by several consecutive insns;
6124 The caller has already identified the first insn P as having a giv as dest;
6125 we check that all other insns that set the same register follow
6126 immediately after P, that they alter nothing else,
6127 and that the result of the last is still a giv.
6129 The value is 0 if the reg set in P is not really a giv.
6130 Otherwise, the value is the amount gained by eliminating
6131 all the consecutive insns that compute the value.
6133 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6134 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6136 The coefficients of the ultimate giv value are stored in
6137 *MULT_VAL and *ADD_VAL. */
6140 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6141 add_val, mult_val, ext_val, last_consec_insn)
6142 const struct loop *loop;
6150 rtx *last_consec_insn;
6152 struct loop_ivs *ivs = LOOP_IVS (loop);
6153 struct loop_regs *regs = LOOP_REGS (loop);
6160 /* Indicate that this is a giv so that we can update the value produced in
6161 each insn of the multi-insn sequence.
6163 This induction structure will be used only by the call to
6164 general_induction_var below, so we can allocate it on our stack.
6165 If this is a giv, our caller will replace the induct var entry with
6166 a new induction structure. */
6167 struct induction *v;
6169 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6172 v = (struct induction *) alloca (sizeof (struct induction));
6173 v->src_reg = src_reg;
6174 v->mult_val = *mult_val;
6175 v->add_val = *add_val;
6176 v->benefit = first_benefit;
6178 v->derive_adjustment = 0;
6179 v->ext_dependant = NULL_RTX;
6181 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6182 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6184 count = regs->array[REGNO (dest_reg)].n_times_set - 1;
6189 code = GET_CODE (p);
6191 /* If libcall, skip to end of call sequence. */
6192 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6196 && (set = single_set (p))
6197 && GET_CODE (SET_DEST (set)) == REG
6198 && SET_DEST (set) == dest_reg
6199 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6200 add_val, mult_val, ext_val, 0,
6202 /* Giv created by equivalent expression. */
6203 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6204 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6205 add_val, mult_val, ext_val, 0,
6206 &benefit, VOIDmode)))
6207 && src_reg == v->src_reg)
6209 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6210 benefit += libcall_benefit (p);
6213 v->mult_val = *mult_val;
6214 v->add_val = *add_val;
6215 v->benefit += benefit;
6217 else if (code != NOTE)
6219 /* Allow insns that set something other than this giv to a
6220 constant. Such insns are needed on machines which cannot
6221 include long constants and should not disqualify a giv. */
6223 && (set = single_set (p))
6224 && SET_DEST (set) != dest_reg
6225 && CONSTANT_P (SET_SRC (set)))
6228 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6233 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6234 *last_consec_insn = p;
6238 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6239 represented by G1. If no such expression can be found, or it is clear that
6240 it cannot possibly be a valid address, 0 is returned.
6242 To perform the computation, we note that
6245 where `v' is the biv.
6247 So G2 = (y/b) * G1 + (b - a*y/x).
6249 Note that MULT = y/x.
6251 Update: A and B are now allowed to be additive expressions such that
6252 B contains all variables in A. That is, computing B-A will not require
6253 subtracting variables. */
6256 express_from_1 (a, b, mult)
6259 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6261 if (mult == const0_rtx)
6264 /* If MULT is not 1, we cannot handle A with non-constants, since we
6265 would then be required to subtract multiples of the registers in A.
6266 This is theoretically possible, and may even apply to some Fortran
6267 constructs, but it is a lot of work and we do not attempt it here. */
6269 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6272 /* In general these structures are sorted top to bottom (down the PLUS
6273 chain), but not left to right across the PLUS. If B is a higher
6274 order giv than A, we can strip one level and recurse. If A is higher
6275 order, we'll eventually bail out, but won't know that until the end.
6276 If they are the same, we'll strip one level around this loop. */
6278 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6280 rtx ra, rb, oa, ob, tmp;
6282 ra = XEXP (a, 0), oa = XEXP (a, 1);
6283 if (GET_CODE (ra) == PLUS)
6284 tmp = ra, ra = oa, oa = tmp;
6286 rb = XEXP (b, 0), ob = XEXP (b, 1);
6287 if (GET_CODE (rb) == PLUS)
6288 tmp = rb, rb = ob, ob = tmp;
6290 if (rtx_equal_p (ra, rb))
6291 /* We matched: remove one reg completely. */
6293 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6294 /* An alternate match. */
6296 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6297 /* An alternate match. */
6301 /* Indicates an extra register in B. Strip one level from B and
6302 recurse, hoping B was the higher order expression. */
6303 ob = express_from_1 (a, ob, mult);
6306 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6310 /* Here we are at the last level of A, go through the cases hoping to
6311 get rid of everything but a constant. */
6313 if (GET_CODE (a) == PLUS)
6317 ra = XEXP (a, 0), oa = XEXP (a, 1);
6318 if (rtx_equal_p (oa, b))
6320 else if (!rtx_equal_p (ra, b))
6323 if (GET_CODE (oa) != CONST_INT)
6326 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6328 else if (GET_CODE (a) == CONST_INT)
6330 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6332 else if (CONSTANT_P (a))
6334 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6336 else if (GET_CODE (b) == PLUS)
6338 if (rtx_equal_p (a, XEXP (b, 0)))
6340 else if (rtx_equal_p (a, XEXP (b, 1)))
6345 else if (rtx_equal_p (a, b))
6352 express_from (g1, g2)
6353 struct induction *g1, *g2;
6357 /* The value that G1 will be multiplied by must be a constant integer. Also,
6358 the only chance we have of getting a valid address is if b*c/a (see above
6359 for notation) is also an integer. */
6360 if (GET_CODE (g1->mult_val) == CONST_INT
6361 && GET_CODE (g2->mult_val) == CONST_INT)
6363 if (g1->mult_val == const0_rtx
6364 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6366 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6368 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6372 /* ??? Find out if the one is a multiple of the other? */
6376 add = express_from_1 (g1->add_val, g2->add_val, mult);
6377 if (add == NULL_RTX)
6379 /* Failed. If we've got a multiplication factor between G1 and G2,
6380 scale G1's addend and try again. */
6381 if (INTVAL (mult) > 1)
6383 rtx g1_add_val = g1->add_val;
6384 if (GET_CODE (g1_add_val) == MULT
6385 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6388 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6389 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6390 XEXP (g1_add_val, 0), GEN_INT (m));
6394 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6398 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6401 if (add == NULL_RTX)
6404 /* Form simplified final result. */
6405 if (mult == const0_rtx)
6407 else if (mult == const1_rtx)
6408 mult = g1->dest_reg;
6410 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6412 if (add == const0_rtx)
6416 if (GET_CODE (add) == PLUS
6417 && CONSTANT_P (XEXP (add, 1)))
6419 rtx tem = XEXP (add, 1);
6420 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6424 return gen_rtx_PLUS (g2->mode, mult, add);
6428 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6429 represented by G1. This indicates that G2 should be combined with G1 and
6430 that G2 can use (either directly or via an address expression) a register
6431 used to represent G1. */
6434 combine_givs_p (g1, g2)
6435 struct induction *g1, *g2;
6439 /* With the introduction of ext dependant givs, we must care for modes.
6440 G2 must not use a wider mode than G1. */
6441 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6444 ret = comb = express_from (g1, g2);
6445 if (comb == NULL_RTX)
6447 if (g1->mode != g2->mode)
6448 ret = gen_lowpart (g2->mode, comb);
6450 /* If these givs are identical, they can be combined. We use the results
6451 of express_from because the addends are not in a canonical form, so
6452 rtx_equal_p is a weaker test. */
6453 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6454 combination to be the other way round. */
6455 if (comb == g1->dest_reg
6456 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6461 /* If G2 can be expressed as a function of G1 and that function is valid
6462 as an address and no more expensive than using a register for G2,
6463 the expression of G2 in terms of G1 can be used. */
6465 && g2->giv_type == DEST_ADDR
6466 && memory_address_p (g2->mem_mode, ret)
6467 /* ??? Looses, especially with -fforce-addr, where *g2->location
6468 will always be a register, and so anything more complicated
6472 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6474 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6485 /* Check each extension dependant giv in this class to see if its
6486 root biv is safe from wrapping in the interior mode, which would
6487 make the giv illegal. */
6490 check_ext_dependant_givs (bl, loop_info)
6491 struct iv_class *bl;
6492 struct loop_info *loop_info;
6494 int ze_ok = 0, se_ok = 0, info_ok = 0;
6495 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6496 HOST_WIDE_INT start_val;
6497 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6499 struct induction *v;
6501 /* Make sure the iteration data is available. We must have
6502 constants in order to be certain of no overflow. */
6503 /* ??? An unknown iteration count with an increment of +-1
6504 combined with friendly exit tests of against an invariant
6505 value is also ameanable to optimization. Not implemented. */
6506 if (loop_info->n_iterations > 0
6507 && bl->initial_value
6508 && GET_CODE (bl->initial_value) == CONST_INT
6509 && (incr = biv_total_increment (bl))
6510 && GET_CODE (incr) == CONST_INT
6511 /* Make sure the host can represent the arithmetic. */
6512 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6514 unsigned HOST_WIDE_INT abs_incr, total_incr;
6515 HOST_WIDE_INT s_end_val;
6519 start_val = INTVAL (bl->initial_value);
6520 u_start_val = start_val;
6522 neg_incr = 0, abs_incr = INTVAL (incr);
6523 if (INTVAL (incr) < 0)
6524 neg_incr = 1, abs_incr = -abs_incr;
6525 total_incr = abs_incr * loop_info->n_iterations;
6527 /* Check for host arithmatic overflow. */
6528 if (total_incr / loop_info->n_iterations == abs_incr)
6530 unsigned HOST_WIDE_INT u_max;
6531 HOST_WIDE_INT s_max;
6533 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6534 s_end_val = u_end_val;
6535 u_max = GET_MODE_MASK (biv_mode);
6538 /* Check zero extension of biv ok. */
6540 /* Check for host arithmatic overflow. */
6542 ? u_end_val < u_start_val
6543 : u_end_val > u_start_val)
6544 /* Check for target arithmetic overflow. */
6546 ? 1 /* taken care of with host overflow */
6547 : u_end_val <= u_max))
6552 /* Check sign extension of biv ok. */
6553 /* ??? While it is true that overflow with signed and pointer
6554 arithmetic is undefined, I fear too many programmers don't
6555 keep this fact in mind -- myself included on occasion.
6556 So leave alone with the signed overflow optimizations. */
6557 if (start_val >= -s_max - 1
6558 /* Check for host arithmatic overflow. */
6560 ? s_end_val < start_val
6561 : s_end_val > start_val)
6562 /* Check for target arithmetic overflow. */
6564 ? s_end_val >= -s_max - 1
6565 : s_end_val <= s_max))
6572 /* Invalidate givs that fail the tests. */
6573 for (v = bl->giv; v; v = v->next_iv)
6574 if (v->ext_dependant)
6576 enum rtx_code code = GET_CODE (v->ext_dependant);
6589 /* We don't know whether this value is being used as either
6590 signed or unsigned, so to safely truncate we must satisfy
6591 both. The initial check here verifies the BIV itself;
6592 once that is successful we may check its range wrt the
6596 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6597 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6599 /* We know from the above that both endpoints are nonnegative,
6600 and that there is no wrapping. Verify that both endpoints
6601 are within the (signed) range of the outer mode. */
6602 if (u_start_val <= max && u_end_val <= max)
6613 if (loop_dump_stream)
6615 fprintf (loop_dump_stream,
6616 "Verified ext dependant giv at %d of reg %d\n",
6617 INSN_UID (v->insn), bl->regno);
6622 if (loop_dump_stream)
6627 why = "biv iteration values overflowed";
6631 incr = biv_total_increment (bl);
6632 if (incr == const1_rtx)
6633 why = "biv iteration info incomplete; incr by 1";
6635 why = "biv iteration info incomplete";
6638 fprintf (loop_dump_stream,
6639 "Failed ext dependant giv at %d, %s\n",
6640 INSN_UID (v->insn), why);
6647 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6650 extend_value_for_giv (v, value)
6651 struct induction *v;
6654 rtx ext_dep = v->ext_dependant;
6659 /* Recall that check_ext_dependant_givs verified that the known bounds
6660 of a biv did not overflow or wrap with respect to the extension for
6661 the giv. Therefore, constants need no additional adjustment. */
6662 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6665 /* Otherwise, we must adjust the value to compensate for the
6666 differing modes of the biv and the giv. */
6667 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6670 struct combine_givs_stats
6677 cmp_combine_givs_stats (xp, yp)
6681 const struct combine_givs_stats * const x =
6682 (const struct combine_givs_stats *) xp;
6683 const struct combine_givs_stats * const y =
6684 (const struct combine_givs_stats *) yp;
6686 d = y->total_benefit - x->total_benefit;
6687 /* Stabilize the sort. */
6689 d = x->giv_number - y->giv_number;
6693 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6694 any other. If so, point SAME to the giv combined with and set NEW_REG to
6695 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6696 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6699 combine_givs (regs, bl)
6700 struct loop_regs *regs;
6701 struct iv_class *bl;
6703 /* Additional benefit to add for being combined multiple times. */
6704 const int extra_benefit = 3;
6706 struct induction *g1, *g2, **giv_array;
6707 int i, j, k, giv_count;
6708 struct combine_givs_stats *stats;
6711 /* Count givs, because bl->giv_count is incorrect here. */
6713 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6718 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6720 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6722 giv_array[i++] = g1;
6724 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6725 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6727 for (i = 0; i < giv_count; i++)
6733 stats[i].giv_number = i;
6735 /* If a DEST_REG GIV is used only once, do not allow it to combine
6736 with anything, for in doing so we will gain nothing that cannot
6737 be had by simply letting the GIV with which we would have combined
6738 to be reduced on its own. The losage shows up in particular with
6739 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6740 be seen elsewhere as well. */
6741 if (g1->giv_type == DEST_REG
6742 && (single_use = regs->array[REGNO (g1->dest_reg)].single_usage)
6743 && single_use != const0_rtx)
6746 this_benefit = g1->benefit;
6747 /* Add an additional weight for zero addends. */
6748 if (g1->no_const_addval)
6751 for (j = 0; j < giv_count; j++)
6757 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6759 can_combine[i * giv_count + j] = this_combine;
6760 this_benefit += g2->benefit + extra_benefit;
6763 stats[i].total_benefit = this_benefit;
6766 /* Iterate, combining until we can't. */
6768 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6770 if (loop_dump_stream)
6772 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6773 for (k = 0; k < giv_count; k++)
6775 g1 = giv_array[stats[k].giv_number];
6776 if (!g1->combined_with && !g1->same)
6777 fprintf (loop_dump_stream, " {%d, %d}",
6778 INSN_UID (giv_array[stats[k].giv_number]->insn),
6779 stats[k].total_benefit);
6781 putc ('\n', loop_dump_stream);
6784 for (k = 0; k < giv_count; k++)
6786 int g1_add_benefit = 0;
6788 i = stats[k].giv_number;
6791 /* If it has already been combined, skip. */
6792 if (g1->combined_with || g1->same)
6795 for (j = 0; j < giv_count; j++)
6798 if (g1 != g2 && can_combine[i * giv_count + j]
6799 /* If it has already been combined, skip. */
6800 && ! g2->same && ! g2->combined_with)
6804 g2->new_reg = can_combine[i * giv_count + j];
6806 g1->combined_with++;
6807 g1->lifetime += g2->lifetime;
6809 g1_add_benefit += g2->benefit;
6811 /* ??? The new final_[bg]iv_value code does a much better job
6812 of finding replaceable giv's, and hence this code may no
6813 longer be necessary. */
6814 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6815 g1_add_benefit -= copy_cost;
6817 /* To help optimize the next set of combinations, remove
6818 this giv from the benefits of other potential mates. */
6819 for (l = 0; l < giv_count; ++l)
6821 int m = stats[l].giv_number;
6822 if (can_combine[m * giv_count + j])
6823 stats[l].total_benefit -= g2->benefit + extra_benefit;
6826 if (loop_dump_stream)
6827 fprintf (loop_dump_stream,
6828 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
6829 INSN_UID (g2->insn), INSN_UID (g1->insn),
6830 g1->benefit, g1_add_benefit, g1->lifetime);
6834 /* To help optimize the next set of combinations, remove
6835 this giv from the benefits of other potential mates. */
6836 if (g1->combined_with)
6838 for (j = 0; j < giv_count; ++j)
6840 int m = stats[j].giv_number;
6841 if (can_combine[m * giv_count + i])
6842 stats[j].total_benefit -= g1->benefit + extra_benefit;
6845 g1->benefit += g1_add_benefit;
6847 /* We've finished with this giv, and everything it touched.
6848 Restart the combination so that proper weights for the
6849 rest of the givs are properly taken into account. */
6850 /* ??? Ideally we would compact the arrays at this point, so
6851 as to not cover old ground. But sanely compacting
6852 can_combine is tricky. */
6862 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
6865 emit_iv_add_mult (b, m, a, reg, insert_before)
6866 rtx b; /* initial value of basic induction variable */
6867 rtx m; /* multiplicative constant */
6868 rtx a; /* additive constant */
6869 rtx reg; /* destination register */
6875 /* Prevent unexpected sharing of these rtx. */
6879 /* Increase the lifetime of any invariants moved further in code. */
6880 update_reg_last_use (a, insert_before);
6881 update_reg_last_use (b, insert_before);
6882 update_reg_last_use (m, insert_before);
6885 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
6887 emit_move_insn (reg, result);
6888 seq = gen_sequence ();
6891 emit_insn_before (seq, insert_before);
6893 /* It is entirely possible that the expansion created lots of new
6894 registers. Iterate over the sequence we just created and
6897 if (GET_CODE (seq) == SEQUENCE)
6900 for (i = 0; i < XVECLEN (seq, 0); ++i)
6902 rtx set = single_set (XVECEXP (seq, 0, i));
6903 if (set && GET_CODE (SET_DEST (set)) == REG)
6904 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6907 else if (GET_CODE (seq) == SET
6908 && GET_CODE (SET_DEST (seq)) == REG)
6909 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
6912 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
6915 iv_add_mult_cost (b, m, a, reg)
6916 rtx b; /* initial value of basic induction variable */
6917 rtx m; /* multiplicative constant */
6918 rtx a; /* additive constant */
6919 rtx reg; /* destination register */
6925 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
6927 emit_move_insn (reg, result);
6928 last = get_last_insn ();
6931 rtx t = single_set (last);
6933 cost += rtx_cost (SET_SRC (t), SET);
6934 last = PREV_INSN (last);
6940 /* Test whether A * B can be computed without
6941 an actual multiply insn. Value is 1 if so. */
6944 product_cheap_p (a, b)
6952 /* If only one is constant, make it B. */
6953 if (GET_CODE (a) == CONST_INT)
6954 tmp = a, a = b, b = tmp;
6956 /* If first constant, both constant, so don't need multiply. */
6957 if (GET_CODE (a) == CONST_INT)
6960 /* If second not constant, neither is constant, so would need multiply. */
6961 if (GET_CODE (b) != CONST_INT)
6964 /* One operand is constant, so might not need multiply insn. Generate the
6965 code for the multiply and see if a call or multiply, or long sequence
6966 of insns is generated. */
6969 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
6970 tmp = gen_sequence ();
6973 if (GET_CODE (tmp) == SEQUENCE)
6975 if (XVEC (tmp, 0) == 0)
6977 else if (XVECLEN (tmp, 0) > 3)
6980 for (i = 0; i < XVECLEN (tmp, 0); i++)
6982 rtx insn = XVECEXP (tmp, 0, i);
6984 if (GET_CODE (insn) != INSN
6985 || (GET_CODE (PATTERN (insn)) == SET
6986 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
6987 || (GET_CODE (PATTERN (insn)) == PARALLEL
6988 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
6989 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
6996 else if (GET_CODE (tmp) == SET
6997 && GET_CODE (SET_SRC (tmp)) == MULT)
6999 else if (GET_CODE (tmp) == PARALLEL
7000 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7001 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7007 /* Check to see if loop can be terminated by a "decrement and branch until
7008 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7009 Also try reversing an increment loop to a decrement loop
7010 to see if the optimization can be performed.
7011 Value is nonzero if optimization was performed. */
7013 /* This is useful even if the architecture doesn't have such an insn,
7014 because it might change a loops which increments from 0 to n to a loop
7015 which decrements from n to 0. A loop that decrements to zero is usually
7016 faster than one that increments from zero. */
7018 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7019 such as approx_final_value, biv_total_increment, loop_iterations, and
7020 final_[bg]iv_value. */
7023 check_dbra_loop (loop, insn_count)
7027 struct loop_info *loop_info = LOOP_INFO (loop);
7028 struct loop_regs *regs = LOOP_REGS (loop);
7029 struct loop_ivs *ivs = LOOP_IVS (loop);
7030 struct iv_class *bl;
7037 rtx before_comparison;
7041 int compare_and_branch;
7042 rtx loop_start = loop->start;
7043 rtx loop_end = loop->end;
7045 /* If last insn is a conditional branch, and the insn before tests a
7046 register value, try to optimize it. Otherwise, we can't do anything. */
7048 jump = PREV_INSN (loop_end);
7049 comparison = get_condition_for_loop (loop, jump);
7050 if (comparison == 0)
7052 if (!onlyjump_p (jump))
7055 /* Try to compute whether the compare/branch at the loop end is one or
7056 two instructions. */
7057 get_condition (jump, &first_compare);
7058 if (first_compare == jump)
7059 compare_and_branch = 1;
7060 else if (first_compare == prev_nonnote_insn (jump))
7061 compare_and_branch = 2;
7066 /* If more than one condition is present to control the loop, then
7067 do not proceed, as this function does not know how to rewrite
7068 loop tests with more than one condition.
7070 Look backwards from the first insn in the last comparison
7071 sequence and see if we've got another comparison sequence. */
7074 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7075 if (GET_CODE (jump1) == JUMP_INSN)
7079 /* Check all of the bivs to see if the compare uses one of them.
7080 Skip biv's set more than once because we can't guarantee that
7081 it will be zero on the last iteration. Also skip if the biv is
7082 used between its update and the test insn. */
7084 for (bl = ivs->list; bl; bl = bl->next)
7086 if (bl->biv_count == 1
7087 && ! bl->biv->maybe_multiple
7088 && bl->biv->dest_reg == XEXP (comparison, 0)
7089 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7097 /* Look for the case where the basic induction variable is always
7098 nonnegative, and equals zero on the last iteration.
7099 In this case, add a reg_note REG_NONNEG, which allows the
7100 m68k DBRA instruction to be used. */
7102 if (((GET_CODE (comparison) == GT
7103 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7104 && INTVAL (XEXP (comparison, 1)) == -1)
7105 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7106 && GET_CODE (bl->biv->add_val) == CONST_INT
7107 && INTVAL (bl->biv->add_val) < 0)
7109 /* Initial value must be greater than 0,
7110 init_val % -dec_value == 0 to ensure that it equals zero on
7111 the last iteration */
7113 if (GET_CODE (bl->initial_value) == CONST_INT
7114 && INTVAL (bl->initial_value) > 0
7115 && (INTVAL (bl->initial_value)
7116 % (-INTVAL (bl->biv->add_val))) == 0)
7118 /* register always nonnegative, add REG_NOTE to branch */
7119 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7121 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7128 /* If the decrement is 1 and the value was tested as >= 0 before
7129 the loop, then we can safely optimize. */
7130 for (p = loop_start; p; p = PREV_INSN (p))
7132 if (GET_CODE (p) == CODE_LABEL)
7134 if (GET_CODE (p) != JUMP_INSN)
7137 before_comparison = get_condition_for_loop (loop, p);
7138 if (before_comparison
7139 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7140 && GET_CODE (before_comparison) == LT
7141 && XEXP (before_comparison, 1) == const0_rtx
7142 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7143 && INTVAL (bl->biv->add_val) == -1)
7145 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7147 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7155 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7156 && INTVAL (bl->biv->add_val) > 0)
7158 /* Try to change inc to dec, so can apply above optimization. */
7160 all registers modified are induction variables or invariant,
7161 all memory references have non-overlapping addresses
7162 (obviously true if only one write)
7163 allow 2 insns for the compare/jump at the end of the loop. */
7164 /* Also, we must avoid any instructions which use both the reversed
7165 biv and another biv. Such instructions will fail if the loop is
7166 reversed. We meet this condition by requiring that either
7167 no_use_except_counting is true, or else that there is only
7169 int num_nonfixed_reads = 0;
7170 /* 1 if the iteration var is used only to count iterations. */
7171 int no_use_except_counting = 0;
7172 /* 1 if the loop has no memory store, or it has a single memory store
7173 which is reversible. */
7174 int reversible_mem_store = 1;
7176 if (bl->giv_count == 0 && ! loop->exit_count)
7178 rtx bivreg = regno_reg_rtx[bl->regno];
7180 /* If there are no givs for this biv, and the only exit is the
7181 fall through at the end of the loop, then
7182 see if perhaps there are no uses except to count. */
7183 no_use_except_counting = 1;
7184 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7187 rtx set = single_set (p);
7189 if (set && GET_CODE (SET_DEST (set)) == REG
7190 && REGNO (SET_DEST (set)) == bl->regno)
7191 /* An insn that sets the biv is okay. */
7193 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7194 || p == prev_nonnote_insn (loop_end))
7195 && reg_mentioned_p (bivreg, PATTERN (p)))
7197 /* If either of these insns uses the biv and sets a pseudo
7198 that has more than one usage, then the biv has uses
7199 other than counting since it's used to derive a value
7200 that is used more than one time. */
7201 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7203 if (regs->multiple_uses)
7205 no_use_except_counting = 0;
7209 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7211 no_use_except_counting = 0;
7217 if (no_use_except_counting)
7218 /* No need to worry about MEMs. */
7220 else if (loop_info->num_mem_sets <= 1)
7222 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7224 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7226 /* If the loop has a single store, and the destination address is
7227 invariant, then we can't reverse the loop, because this address
7228 might then have the wrong value at loop exit.
7229 This would work if the source was invariant also, however, in that
7230 case, the insn should have been moved out of the loop. */
7232 if (loop_info->num_mem_sets == 1)
7234 struct induction *v;
7236 reversible_mem_store
7237 = (! loop_info->unknown_address_altered
7238 && ! loop_info->unknown_constant_address_altered
7239 && ! loop_invariant_p (loop,
7240 XEXP (XEXP (loop_info->store_mems, 0),
7243 /* If the store depends on a register that is set after the
7244 store, it depends on the initial value, and is thus not
7246 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7248 if (v->giv_type == DEST_REG
7249 && reg_mentioned_p (v->dest_reg,
7250 PATTERN (loop_info->first_loop_store_insn))
7251 && loop_insn_first_p (loop_info->first_loop_store_insn,
7253 reversible_mem_store = 0;
7260 /* This code only acts for innermost loops. Also it simplifies
7261 the memory address check by only reversing loops with
7262 zero or one memory access.
7263 Two memory accesses could involve parts of the same array,
7264 and that can't be reversed.
7265 If the biv is used only for counting, than we don't need to worry
7266 about all these things. */
7268 if ((num_nonfixed_reads <= 1
7269 && ! loop_info->has_nonconst_call
7270 && ! loop_info->has_volatile
7271 && reversible_mem_store
7272 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7273 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7274 && (bl == ivs->list && bl->next == 0))
7275 || no_use_except_counting)
7279 /* Loop can be reversed. */
7280 if (loop_dump_stream)
7281 fprintf (loop_dump_stream, "Can reverse loop\n");
7283 /* Now check other conditions:
7285 The increment must be a constant, as must the initial value,
7286 and the comparison code must be LT.
7288 This test can probably be improved since +/- 1 in the constant
7289 can be obtained by changing LT to LE and vice versa; this is
7293 /* for constants, LE gets turned into LT */
7294 && (GET_CODE (comparison) == LT
7295 || (GET_CODE (comparison) == LE
7296 && no_use_except_counting)))
7298 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7299 rtx initial_value, comparison_value;
7301 enum rtx_code cmp_code;
7302 int comparison_const_width;
7303 unsigned HOST_WIDE_INT comparison_sign_mask;
7305 add_val = INTVAL (bl->biv->add_val);
7306 comparison_value = XEXP (comparison, 1);
7307 if (GET_MODE (comparison_value) == VOIDmode)
7308 comparison_const_width
7309 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7311 comparison_const_width
7312 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7313 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7314 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7315 comparison_sign_mask
7316 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7318 /* If the comparison value is not a loop invariant, then we
7319 can not reverse this loop.
7321 ??? If the insns which initialize the comparison value as
7322 a whole compute an invariant result, then we could move
7323 them out of the loop and proceed with loop reversal. */
7324 if (! loop_invariant_p (loop, comparison_value))
7327 if (GET_CODE (comparison_value) == CONST_INT)
7328 comparison_val = INTVAL (comparison_value);
7329 initial_value = bl->initial_value;
7331 /* Normalize the initial value if it is an integer and
7332 has no other use except as a counter. This will allow
7333 a few more loops to be reversed. */
7334 if (no_use_except_counting
7335 && GET_CODE (comparison_value) == CONST_INT
7336 && GET_CODE (initial_value) == CONST_INT)
7338 comparison_val = comparison_val - INTVAL (bl->initial_value);
7339 /* The code below requires comparison_val to be a multiple
7340 of add_val in order to do the loop reversal, so
7341 round up comparison_val to a multiple of add_val.
7342 Since comparison_value is constant, we know that the
7343 current comparison code is LT. */
7344 comparison_val = comparison_val + add_val - 1;
7346 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7347 /* We postpone overflow checks for COMPARISON_VAL here;
7348 even if there is an overflow, we might still be able to
7349 reverse the loop, if converting the loop exit test to
7351 initial_value = const0_rtx;
7354 /* First check if we can do a vanilla loop reversal. */
7355 if (initial_value == const0_rtx
7356 /* If we have a decrement_and_branch_on_count,
7357 prefer the NE test, since this will allow that
7358 instruction to be generated. Note that we must
7359 use a vanilla loop reversal if the biv is used to
7360 calculate a giv or has a non-counting use. */
7361 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7362 && defined (HAVE_decrement_and_branch_on_count)
7363 && (! (add_val == 1 && loop->vtop
7364 && (bl->biv_count == 0
7365 || no_use_except_counting)))
7367 && GET_CODE (comparison_value) == CONST_INT
7368 /* Now do postponed overflow checks on COMPARISON_VAL. */
7369 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7370 & comparison_sign_mask))
7372 /* Register will always be nonnegative, with value
7373 0 on last iteration */
7374 add_adjust = add_val;
7378 else if (add_val == 1 && loop->vtop
7379 && (bl->biv_count == 0
7380 || no_use_except_counting))
7388 if (GET_CODE (comparison) == LE)
7389 add_adjust -= add_val;
7391 /* If the initial value is not zero, or if the comparison
7392 value is not an exact multiple of the increment, then we
7393 can not reverse this loop. */
7394 if (initial_value == const0_rtx
7395 && GET_CODE (comparison_value) == CONST_INT)
7397 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7402 if (! no_use_except_counting || add_val != 1)
7406 final_value = comparison_value;
7408 /* Reset these in case we normalized the initial value
7409 and comparison value above. */
7410 if (GET_CODE (comparison_value) == CONST_INT
7411 && GET_CODE (initial_value) == CONST_INT)
7413 comparison_value = GEN_INT (comparison_val);
7415 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7417 bl->initial_value = initial_value;
7419 /* Save some info needed to produce the new insns. */
7420 reg = bl->biv->dest_reg;
7421 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7422 if (jump_label == pc_rtx)
7423 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7424 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7426 /* Set start_value; if this is not a CONST_INT, we need
7428 Initialize biv to start_value before loop start.
7429 The old initializing insn will be deleted as a
7430 dead store by flow.c. */
7431 if (initial_value == const0_rtx
7432 && GET_CODE (comparison_value) == CONST_INT)
7434 start_value = GEN_INT (comparison_val - add_adjust);
7435 emit_insn_before (gen_move_insn (reg, start_value),
7438 else if (GET_CODE (initial_value) == CONST_INT)
7440 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7441 enum machine_mode mode = GET_MODE (reg);
7442 enum insn_code icode
7443 = add_optab->handlers[(int) mode].insn_code;
7445 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7446 || ! ((*insn_data[icode].operand[1].predicate)
7447 (comparison_value, mode))
7448 || ! ((*insn_data[icode].operand[2].predicate)
7452 = gen_rtx_PLUS (mode, comparison_value, offset);
7453 emit_insn_before ((GEN_FCN (icode)
7454 (reg, comparison_value, offset)),
7456 if (GET_CODE (comparison) == LE)
7457 final_value = gen_rtx_PLUS (mode, comparison_value,
7460 else if (! add_adjust)
7462 enum machine_mode mode = GET_MODE (reg);
7463 enum insn_code icode
7464 = sub_optab->handlers[(int) mode].insn_code;
7465 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7466 || ! ((*insn_data[icode].operand[1].predicate)
7467 (comparison_value, mode))
7468 || ! ((*insn_data[icode].operand[2].predicate)
7469 (initial_value, mode)))
7472 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7473 emit_insn_before ((GEN_FCN (icode)
7474 (reg, comparison_value, initial_value)),
7478 /* We could handle the other cases too, but it'll be
7479 better to have a testcase first. */
7482 /* We may not have a single insn which can increment a reg, so
7483 create a sequence to hold all the insns from expand_inc. */
7485 expand_inc (reg, new_add_val);
7486 tem = gen_sequence ();
7489 p = emit_insn_before (tem, bl->biv->insn);
7490 delete_insn (bl->biv->insn);
7492 /* Update biv info to reflect its new status. */
7494 bl->initial_value = start_value;
7495 bl->biv->add_val = new_add_val;
7497 /* Update loop info. */
7498 loop_info->initial_value = reg;
7499 loop_info->initial_equiv_value = reg;
7500 loop_info->final_value = const0_rtx;
7501 loop_info->final_equiv_value = const0_rtx;
7502 loop_info->comparison_value = const0_rtx;
7503 loop_info->comparison_code = cmp_code;
7504 loop_info->increment = new_add_val;
7506 /* Inc LABEL_NUSES so that delete_insn will
7507 not delete the label. */
7508 LABEL_NUSES (XEXP (jump_label, 0))++;
7510 /* Emit an insn after the end of the loop to set the biv's
7511 proper exit value if it is used anywhere outside the loop. */
7512 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7514 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7515 emit_insn_after (gen_move_insn (reg, final_value),
7518 /* Delete compare/branch at end of loop. */
7519 delete_insn (PREV_INSN (loop_end));
7520 if (compare_and_branch == 2)
7521 delete_insn (first_compare);
7523 /* Add new compare/branch insn at end of loop. */
7525 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7526 GET_MODE (reg), 0, 0,
7527 XEXP (jump_label, 0));
7528 tem = gen_sequence ();
7530 emit_jump_insn_before (tem, loop_end);
7532 for (tem = PREV_INSN (loop_end);
7533 tem && GET_CODE (tem) != JUMP_INSN;
7534 tem = PREV_INSN (tem))
7538 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7544 /* Increment of LABEL_NUSES done above. */
7545 /* Register is now always nonnegative,
7546 so add REG_NONNEG note to the branch. */
7547 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7553 /* No insn may reference both the reversed and another biv or it
7554 will fail (see comment near the top of the loop reversal
7556 Earlier on, we have verified that the biv has no use except
7557 counting, or it is the only biv in this function.
7558 However, the code that computes no_use_except_counting does
7559 not verify reg notes. It's possible to have an insn that
7560 references another biv, and has a REG_EQUAL note with an
7561 expression based on the reversed biv. To avoid this case,
7562 remove all REG_EQUAL notes based on the reversed biv
7564 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7568 rtx set = single_set (p);
7569 /* If this is a set of a GIV based on the reversed biv, any
7570 REG_EQUAL notes should still be correct. */
7572 || GET_CODE (SET_DEST (set)) != REG
7573 || (size_t) REGNO (SET_DEST (set)) >= ivs->n_regs
7574 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7575 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7576 for (pnote = ®_NOTES (p); *pnote;)
7578 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7579 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7581 *pnote = XEXP (*pnote, 1);
7583 pnote = &XEXP (*pnote, 1);
7587 /* Mark that this biv has been reversed. Each giv which depends
7588 on this biv, and which is also live past the end of the loop
7589 will have to be fixed up. */
7593 if (loop_dump_stream)
7595 fprintf (loop_dump_stream, "Reversed loop");
7597 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7599 fprintf (loop_dump_stream, "\n");
7610 /* Verify whether the biv BL appears to be eliminable,
7611 based on the insns in the loop that refer to it.
7613 If ELIMINATE_P is non-zero, actually do the elimination.
7615 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7616 determine whether invariant insns should be placed inside or at the
7617 start of the loop. */
7620 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7621 const struct loop *loop;
7622 struct iv_class *bl;
7624 int threshold, insn_count;
7626 struct loop_ivs *ivs = LOOP_IVS (loop);
7627 rtx reg = bl->biv->dest_reg;
7628 rtx loop_start = loop->start;
7629 rtx loop_end = loop->end;
7632 /* Scan all insns in the loop, stopping if we find one that uses the
7633 biv in a way that we cannot eliminate. */
7635 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7637 enum rtx_code code = GET_CODE (p);
7638 rtx where = threshold >= insn_count ? loop_start : p;
7640 /* If this is a libcall that sets a giv, skip ahead to its end. */
7641 if (GET_RTX_CLASS (code) == 'i')
7643 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7647 rtx last = XEXP (note, 0);
7648 rtx set = single_set (last);
7650 if (set && GET_CODE (SET_DEST (set)) == REG)
7652 unsigned int regno = REGNO (SET_DEST (set));
7654 if (regno < ivs->n_regs
7655 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7656 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7661 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7662 && reg_mentioned_p (reg, PATTERN (p))
7663 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7664 eliminate_p, where))
7666 if (loop_dump_stream)
7667 fprintf (loop_dump_stream,
7668 "Cannot eliminate biv %d: biv used in insn %d.\n",
7669 bl->regno, INSN_UID (p));
7676 if (loop_dump_stream)
7677 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7678 bl->regno, eliminate_p ? "was" : "can be");
7685 /* INSN and REFERENCE are instructions in the same insn chain.
7686 Return non-zero if INSN is first. */
7689 loop_insn_first_p (insn, reference)
7690 rtx insn, reference;
7694 for (p = insn, q = reference;;)
7696 /* Start with test for not first so that INSN == REFERENCE yields not
7698 if (q == insn || ! p)
7700 if (p == reference || ! q)
7703 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7704 previous insn, hence the <= comparison below does not work if
7706 if (INSN_UID (p) < max_uid_for_loop
7707 && INSN_UID (q) < max_uid_for_loop
7708 && GET_CODE (p) != NOTE)
7709 return INSN_LUID (p) <= INSN_LUID (q);
7711 if (INSN_UID (p) >= max_uid_for_loop
7712 || GET_CODE (p) == NOTE)
7714 if (INSN_UID (q) >= max_uid_for_loop)
7719 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7720 the offset that we have to take into account due to auto-increment /
7721 div derivation is zero. */
7723 biv_elimination_giv_has_0_offset (biv, giv, insn)
7724 struct induction *biv, *giv;
7727 /* If the giv V had the auto-inc address optimization applied
7728 to it, and INSN occurs between the giv insn and the biv
7729 insn, then we'd have to adjust the value used here.
7730 This is rare, so we don't bother to make this possible. */
7731 if (giv->auto_inc_opt
7732 && ((loop_insn_first_p (giv->insn, insn)
7733 && loop_insn_first_p (insn, biv->insn))
7734 || (loop_insn_first_p (biv->insn, insn)
7735 && loop_insn_first_p (insn, giv->insn))))
7741 /* If BL appears in X (part of the pattern of INSN), see if we can
7742 eliminate its use. If so, return 1. If not, return 0.
7744 If BIV does not appear in X, return 1.
7746 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7747 where extra insns should be added. Depending on how many items have been
7748 moved out of the loop, it will either be before INSN or at the start of
7752 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7753 const struct loop *loop;
7755 struct iv_class *bl;
7759 enum rtx_code code = GET_CODE (x);
7760 rtx reg = bl->biv->dest_reg;
7761 enum machine_mode mode = GET_MODE (reg);
7762 struct induction *v;
7774 /* If we haven't already been able to do something with this BIV,
7775 we can't eliminate it. */
7781 /* If this sets the BIV, it is not a problem. */
7782 if (SET_DEST (x) == reg)
7785 /* If this is an insn that defines a giv, it is also ok because
7786 it will go away when the giv is reduced. */
7787 for (v = bl->giv; v; v = v->next_iv)
7788 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7792 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7794 /* Can replace with any giv that was reduced and
7795 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7796 Require a constant for MULT_VAL, so we know it's nonzero.
7797 ??? We disable this optimization to avoid potential
7800 for (v = bl->giv; v; v = v->next_iv)
7801 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7802 && v->add_val == const0_rtx
7803 && ! v->ignore && ! v->maybe_dead && v->always_computable
7807 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7813 /* If the giv has the opposite direction of change,
7814 then reverse the comparison. */
7815 if (INTVAL (v->mult_val) < 0)
7816 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7817 const0_rtx, v->new_reg);
7821 /* We can probably test that giv's reduced reg. */
7822 if (validate_change (insn, &SET_SRC (x), new, 0))
7826 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7827 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7828 Require a constant for MULT_VAL, so we know it's nonzero.
7829 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7830 overflow problem. */
7832 for (v = bl->giv; v; v = v->next_iv)
7833 if (GET_CODE (v->mult_val) == CONST_INT
7834 && v->mult_val != const0_rtx
7835 && ! v->ignore && ! v->maybe_dead && v->always_computable
7837 && (GET_CODE (v->add_val) == SYMBOL_REF
7838 || GET_CODE (v->add_val) == LABEL_REF
7839 || GET_CODE (v->add_val) == CONST
7840 || (GET_CODE (v->add_val) == REG
7841 && REG_POINTER (v->add_val))))
7843 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7849 /* If the giv has the opposite direction of change,
7850 then reverse the comparison. */
7851 if (INTVAL (v->mult_val) < 0)
7852 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
7855 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
7856 copy_rtx (v->add_val));
7858 /* Replace biv with the giv's reduced register. */
7859 update_reg_last_use (v->add_val, insn);
7860 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7863 /* Insn doesn't support that constant or invariant. Copy it
7864 into a register (it will be a loop invariant.) */
7865 tem = gen_reg_rtx (GET_MODE (v->new_reg));
7867 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
7870 /* Substitute the new register for its invariant value in
7871 the compare expression. */
7872 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
7873 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7882 case GT: case GE: case GTU: case GEU:
7883 case LT: case LE: case LTU: case LEU:
7884 /* See if either argument is the biv. */
7885 if (XEXP (x, 0) == reg)
7886 arg = XEXP (x, 1), arg_operand = 1;
7887 else if (XEXP (x, 1) == reg)
7888 arg = XEXP (x, 0), arg_operand = 0;
7892 if (CONSTANT_P (arg))
7894 /* First try to replace with any giv that has constant positive
7895 mult_val and constant add_val. We might be able to support
7896 negative mult_val, but it seems complex to do it in general. */
7898 for (v = bl->giv; v; v = v->next_iv)
7899 if (GET_CODE (v->mult_val) == CONST_INT
7900 && INTVAL (v->mult_val) > 0
7901 && (GET_CODE (v->add_val) == SYMBOL_REF
7902 || GET_CODE (v->add_val) == LABEL_REF
7903 || GET_CODE (v->add_val) == CONST
7904 || (GET_CODE (v->add_val) == REG
7905 && REG_POINTER (v->add_val)))
7906 && ! v->ignore && ! v->maybe_dead && v->always_computable
7909 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7915 /* Replace biv with the giv's reduced reg. */
7916 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
7918 /* If all constants are actually constant integers and
7919 the derived constant can be directly placed in the COMPARE,
7921 if (GET_CODE (arg) == CONST_INT
7922 && GET_CODE (v->mult_val) == CONST_INT
7923 && GET_CODE (v->add_val) == CONST_INT)
7925 validate_change (insn, &XEXP (x, arg_operand),
7926 GEN_INT (INTVAL (arg)
7927 * INTVAL (v->mult_val)
7928 + INTVAL (v->add_val)), 1);
7932 /* Otherwise, load it into a register. */
7933 tem = gen_reg_rtx (mode);
7934 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7935 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7937 if (apply_change_group ())
7941 /* Look for giv with positive constant mult_val and nonconst add_val.
7942 Insert insns to calculate new compare value.
7943 ??? Turn this off due to possible overflow. */
7945 for (v = bl->giv; v; v = v->next_iv)
7946 if (GET_CODE (v->mult_val) == CONST_INT
7947 && INTVAL (v->mult_val) > 0
7948 && ! v->ignore && ! v->maybe_dead && v->always_computable
7954 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7960 tem = gen_reg_rtx (mode);
7962 /* Replace biv with giv's reduced register. */
7963 validate_change (insn, &XEXP (x, 1 - arg_operand),
7966 /* Compute value to compare against. */
7967 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7968 /* Use it in this insn. */
7969 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7970 if (apply_change_group ())
7974 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
7976 if (loop_invariant_p (loop, arg) == 1)
7978 /* Look for giv with constant positive mult_val and nonconst
7979 add_val. Insert insns to compute new compare value.
7980 ??? Turn this off due to possible overflow. */
7982 for (v = bl->giv; v; v = v->next_iv)
7983 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
7984 && ! v->ignore && ! v->maybe_dead && v->always_computable
7990 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7996 tem = gen_reg_rtx (mode);
7998 /* Replace biv with giv's reduced register. */
7999 validate_change (insn, &XEXP (x, 1 - arg_operand),
8002 /* Compute value to compare against. */
8003 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8005 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8006 if (apply_change_group ())
8011 /* This code has problems. Basically, you can't know when
8012 seeing if we will eliminate BL, whether a particular giv
8013 of ARG will be reduced. If it isn't going to be reduced,
8014 we can't eliminate BL. We can try forcing it to be reduced,
8015 but that can generate poor code.
8017 The problem is that the benefit of reducing TV, below should
8018 be increased if BL can actually be eliminated, but this means
8019 we might have to do a topological sort of the order in which
8020 we try to process biv. It doesn't seem worthwhile to do
8021 this sort of thing now. */
8024 /* Otherwise the reg compared with had better be a biv. */
8025 if (GET_CODE (arg) != REG
8026 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8029 /* Look for a pair of givs, one for each biv,
8030 with identical coefficients. */
8031 for (v = bl->giv; v; v = v->next_iv)
8033 struct induction *tv;
8035 if (v->ignore || v->maybe_dead || v->mode != mode)
8038 for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
8040 if (! tv->ignore && ! tv->maybe_dead
8041 && rtx_equal_p (tv->mult_val, v->mult_val)
8042 && rtx_equal_p (tv->add_val, v->add_val)
8043 && tv->mode == mode)
8045 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8051 /* Replace biv with its giv's reduced reg. */
8052 XEXP (x, 1 - arg_operand) = v->new_reg;
8053 /* Replace other operand with the other giv's
8055 XEXP (x, arg_operand) = tv->new_reg;
8062 /* If we get here, the biv can't be eliminated. */
8066 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8067 biv is used in it, since it will be replaced. */
8068 for (v = bl->giv; v; v = v->next_iv)
8069 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8077 /* See if any subexpression fails elimination. */
8078 fmt = GET_RTX_FORMAT (code);
8079 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8084 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8085 eliminate_p, where))
8090 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8091 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8092 eliminate_p, where))
8101 /* Return nonzero if the last use of REG
8102 is in an insn following INSN in the same basic block. */
8105 last_use_this_basic_block (reg, insn)
8111 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8114 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8120 /* Called via `note_stores' to record the initial value of a biv. Here we
8121 just record the location of the set and process it later. */
8124 record_initial (dest, set, data)
8127 void *data ATTRIBUTE_UNUSED;
8129 struct loop_ivs *ivs = (struct loop_ivs *) data;
8130 struct iv_class *bl;
8132 if (GET_CODE (dest) != REG
8133 || REGNO (dest) >= ivs->n_regs
8134 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8137 bl = REG_IV_CLASS (ivs, REGNO (dest));
8139 /* If this is the first set found, record it. */
8140 if (bl->init_insn == 0)
8142 bl->init_insn = note_insn;
8147 /* If any of the registers in X are "old" and currently have a last use earlier
8148 than INSN, update them to have a last use of INSN. Their actual last use
8149 will be the previous insn but it will not have a valid uid_luid so we can't
8153 update_reg_last_use (x, insn)
8157 /* Check for the case where INSN does not have a valid luid. In this case,
8158 there is no need to modify the regno_last_uid, as this can only happen
8159 when code is inserted after the loop_end to set a pseudo's final value,
8160 and hence this insn will never be the last use of x. */
8161 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8162 && INSN_UID (insn) < max_uid_for_loop
8163 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8164 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8168 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8169 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8172 update_reg_last_use (XEXP (x, i), insn);
8173 else if (fmt[i] == 'E')
8174 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8175 update_reg_last_use (XVECEXP (x, i, j), insn);
8180 /* Given an insn INSN and condition COND, return the condition in a
8181 canonical form to simplify testing by callers. Specifically:
8183 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8184 (2) Both operands will be machine operands; (cc0) will have been replaced.
8185 (3) If an operand is a constant, it will be the second operand.
8186 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8187 for GE, GEU, and LEU.
8189 If the condition cannot be understood, or is an inequality floating-point
8190 comparison which needs to be reversed, 0 will be returned.
8192 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8194 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8195 insn used in locating the condition was found. If a replacement test
8196 of the condition is desired, it should be placed in front of that
8197 insn and we will be sure that the inputs are still valid.
8199 If WANT_REG is non-zero, we wish the condition to be relative to that
8200 register, if possible. Therefore, do not canonicalize the condition
8204 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8216 int reverse_code = 0;
8217 int did_reverse_condition = 0;
8218 enum machine_mode mode;
8220 code = GET_CODE (cond);
8221 mode = GET_MODE (cond);
8222 op0 = XEXP (cond, 0);
8223 op1 = XEXP (cond, 1);
8227 code = reverse_condition (code);
8228 did_reverse_condition ^= 1;
8234 /* If we are comparing a register with zero, see if the register is set
8235 in the previous insn to a COMPARE or a comparison operation. Perform
8236 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8239 while (GET_RTX_CLASS (code) == '<'
8240 && op1 == CONST0_RTX (GET_MODE (op0))
8243 /* Set non-zero when we find something of interest. */
8247 /* If comparison with cc0, import actual comparison from compare
8251 if ((prev = prev_nonnote_insn (prev)) == 0
8252 || GET_CODE (prev) != INSN
8253 || (set = single_set (prev)) == 0
8254 || SET_DEST (set) != cc0_rtx)
8257 op0 = SET_SRC (set);
8258 op1 = CONST0_RTX (GET_MODE (op0));
8264 /* If this is a COMPARE, pick up the two things being compared. */
8265 if (GET_CODE (op0) == COMPARE)
8267 op1 = XEXP (op0, 1);
8268 op0 = XEXP (op0, 0);
8271 else if (GET_CODE (op0) != REG)
8274 /* Go back to the previous insn. Stop if it is not an INSN. We also
8275 stop if it isn't a single set or if it has a REG_INC note because
8276 we don't want to bother dealing with it. */
8278 if ((prev = prev_nonnote_insn (prev)) == 0
8279 || GET_CODE (prev) != INSN
8280 || FIND_REG_INC_NOTE (prev, 0)
8281 || (set = single_set (prev)) == 0)
8284 /* If this is setting OP0, get what it sets it to if it looks
8286 if (rtx_equal_p (SET_DEST (set), op0))
8288 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8290 /* ??? We may not combine comparisons done in a CCmode with
8291 comparisons not done in a CCmode. This is to aid targets
8292 like Alpha that have an IEEE compliant EQ instruction, and
8293 a non-IEEE compliant BEQ instruction. The use of CCmode is
8294 actually artificial, simply to prevent the combination, but
8295 should not affect other platforms.
8297 However, we must allow VOIDmode comparisons to match either
8298 CCmode or non-CCmode comparison, because some ports have
8299 modeless comparisons inside branch patterns.
8301 ??? This mode check should perhaps look more like the mode check
8302 in simplify_comparison in combine. */
8304 if ((GET_CODE (SET_SRC (set)) == COMPARE
8307 && GET_MODE_CLASS (inner_mode) == MODE_INT
8308 && (GET_MODE_BITSIZE (inner_mode)
8309 <= HOST_BITS_PER_WIDE_INT)
8310 && (STORE_FLAG_VALUE
8311 & ((HOST_WIDE_INT) 1
8312 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8313 #ifdef FLOAT_STORE_FLAG_VALUE
8315 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8316 && (REAL_VALUE_NEGATIVE
8317 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8320 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8321 && (((GET_MODE_CLASS (mode) == MODE_CC)
8322 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8323 || mode == VOIDmode || inner_mode == VOIDmode))
8325 else if (((code == EQ
8327 && (GET_MODE_BITSIZE (inner_mode)
8328 <= HOST_BITS_PER_WIDE_INT)
8329 && GET_MODE_CLASS (inner_mode) == MODE_INT
8330 && (STORE_FLAG_VALUE
8331 & ((HOST_WIDE_INT) 1
8332 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8333 #ifdef FLOAT_STORE_FLAG_VALUE
8335 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8336 && (REAL_VALUE_NEGATIVE
8337 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8340 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8341 && (((GET_MODE_CLASS (mode) == MODE_CC)
8342 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8343 || mode == VOIDmode || inner_mode == VOIDmode))
8346 /* We might have reversed a LT to get a GE here. But this wasn't
8347 actually the comparison of data, so we don't flag that we
8348 have had to reverse the condition. */
8349 did_reverse_condition ^= 1;
8357 else if (reg_set_p (op0, prev))
8358 /* If this sets OP0, but not directly, we have to give up. */
8363 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8364 code = GET_CODE (x);
8367 code = reverse_condition (code);
8368 if (code == UNKNOWN)
8370 did_reverse_condition ^= 1;
8374 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8380 /* If constant is first, put it last. */
8381 if (CONSTANT_P (op0))
8382 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8384 /* If OP0 is the result of a comparison, we weren't able to find what
8385 was really being compared, so fail. */
8386 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8389 /* Canonicalize any ordered comparison with integers involving equality
8390 if we can do computations in the relevant mode and we do not
8393 if (GET_CODE (op1) == CONST_INT
8394 && GET_MODE (op0) != VOIDmode
8395 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8397 HOST_WIDE_INT const_val = INTVAL (op1);
8398 unsigned HOST_WIDE_INT uconst_val = const_val;
8399 unsigned HOST_WIDE_INT max_val
8400 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8405 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8406 code = LT, op1 = GEN_INT (const_val + 1);
8409 /* When cross-compiling, const_val might be sign-extended from
8410 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8412 if ((HOST_WIDE_INT) (const_val & max_val)
8413 != (((HOST_WIDE_INT) 1
8414 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8415 code = GT, op1 = GEN_INT (const_val - 1);
8419 if (uconst_val < max_val)
8420 code = LTU, op1 = GEN_INT (uconst_val + 1);
8424 if (uconst_val != 0)
8425 code = GTU, op1 = GEN_INT (uconst_val - 1);
8433 /* If this was floating-point and we reversed anything other than an
8434 EQ or NE or (UN)ORDERED, return zero. */
8435 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8436 && did_reverse_condition
8437 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8439 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8443 /* Never return CC0; return zero instead. */
8448 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8451 /* Given a jump insn JUMP, return the condition that will cause it to branch
8452 to its JUMP_LABEL. If the condition cannot be understood, or is an
8453 inequality floating-point comparison which needs to be reversed, 0 will
8456 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8457 insn used in locating the condition was found. If a replacement test
8458 of the condition is desired, it should be placed in front of that
8459 insn and we will be sure that the inputs are still valid. */
8462 get_condition (jump, earliest)
8470 /* If this is not a standard conditional jump, we can't parse it. */
8471 if (GET_CODE (jump) != JUMP_INSN
8472 || ! any_condjump_p (jump))
8474 set = pc_set (jump);
8476 cond = XEXP (SET_SRC (set), 0);
8478 /* If this branches to JUMP_LABEL when the condition is false, reverse
8481 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8482 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8484 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8487 /* Similar to above routine, except that we also put an invariant last
8488 unless both operands are invariants. */
8491 get_condition_for_loop (loop, x)
8492 const struct loop *loop;
8495 rtx comparison = get_condition (x, NULL_PTR);
8498 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8499 || loop_invariant_p (loop, XEXP (comparison, 1)))
8502 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8503 XEXP (comparison, 1), XEXP (comparison, 0));
8506 /* Scan the function and determine whether it has indirect (computed) jumps.
8508 This is taken mostly from flow.c; similar code exists elsewhere
8509 in the compiler. It may be useful to put this into rtlanal.c. */
8511 indirect_jump_in_function_p (start)
8516 for (insn = start; insn; insn = NEXT_INSN (insn))
8517 if (computed_jump_p (insn))
8523 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8524 documentation for LOOP_MEMS for the definition of `appropriate'.
8525 This function is called from prescan_loop via for_each_rtx. */
8528 insert_loop_mem (mem, data)
8530 void *data ATTRIBUTE_UNUSED;
8532 struct loop_info *loop_info = data;
8539 switch (GET_CODE (m))
8545 /* We're not interested in MEMs that are only clobbered. */
8549 /* We're not interested in the MEM associated with a
8550 CONST_DOUBLE, so there's no need to traverse into this. */
8554 /* We're not interested in any MEMs that only appear in notes. */
8558 /* This is not a MEM. */
8562 /* See if we've already seen this MEM. */
8563 for (i = 0; i < loop_info->mems_idx; ++i)
8564 if (rtx_equal_p (m, loop_info->mems[i].mem))
8566 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8567 /* The modes of the two memory accesses are different. If
8568 this happens, something tricky is going on, and we just
8569 don't optimize accesses to this MEM. */
8570 loop_info->mems[i].optimize = 0;
8575 /* Resize the array, if necessary. */
8576 if (loop_info->mems_idx == loop_info->mems_allocated)
8578 if (loop_info->mems_allocated != 0)
8579 loop_info->mems_allocated *= 2;
8581 loop_info->mems_allocated = 32;
8583 loop_info->mems = (loop_mem_info *)
8584 xrealloc (loop_info->mems,
8585 loop_info->mems_allocated * sizeof (loop_mem_info));
8588 /* Actually insert the MEM. */
8589 loop_info->mems[loop_info->mems_idx].mem = m;
8590 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8591 because we can't put it in a register. We still store it in the
8592 table, though, so that if we see the same address later, but in a
8593 non-BLK mode, we'll not think we can optimize it at that point. */
8594 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8595 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8596 ++loop_info->mems_idx;
8602 /* Allocate REGS->ARRAY or reallocate it if it is too small.
8604 Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
8605 register that is modified by an insn between FROM and TO. If the
8606 value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
8607 more, stop incrementing it, to avoid overflow.
8609 Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
8610 register I is used, if it is only used once. Otherwise, it is set
8611 to 0 (for no uses) or const0_rtx for more than one use. This
8612 parameter may be zero, in which case this processing is not done.
8614 Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
8615 optimize register I.
8617 Store in *COUNT_PTR the number of actual instructions
8618 in the loop. We use this to decide what is worth moving out. */
8621 loop_regs_scan (loop, extra_size, count_ptr)
8622 const struct loop *loop;
8626 struct loop_regs *regs = LOOP_REGS (loop);
8628 /* last_set[n] is nonzero iff reg n has been set in the current
8629 basic block. In that case, it is the insn that last set reg n. */
8635 old_nregs = regs->num;
8636 regs->num = max_reg_num ();
8638 /* Grow the regs array if not allocated or too small. */
8639 if (regs->num >= regs->size)
8641 regs->size = regs->num + extra_size;
8643 regs->array = (struct loop_reg *)
8644 xrealloc (regs->array, regs->size * sizeof (*regs->array));
8646 /* Zero the new elements. */
8647 memset (regs->array + old_nregs, 0,
8648 (regs->size - old_nregs) * sizeof (*regs->array));
8651 /* Clear previously scanned fields but do not clear n_times_set. */
8652 for (i = 0; i < old_nregs; i++)
8654 regs->array[i].set_in_loop = 0;
8655 regs->array[i].may_not_optimize = 0;
8656 regs->array[i].single_usage = NULL_RTX;
8659 last_set = (rtx *) xcalloc (regs->num, sizeof (rtx));
8661 /* Scan the loop, recording register usage. */
8662 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
8663 insn = NEXT_INSN (insn))
8669 /* Record registers that have exactly one use. */
8670 find_single_use_in_loop (regs, insn, PATTERN (insn));
8672 /* Include uses in REG_EQUAL notes. */
8673 if (REG_NOTES (insn))
8674 find_single_use_in_loop (regs, insn, REG_NOTES (insn));
8676 if (GET_CODE (PATTERN (insn)) == SET
8677 || GET_CODE (PATTERN (insn)) == CLOBBER)
8678 count_one_set (regs, insn, PATTERN (insn), last_set);
8679 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
8682 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
8683 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
8688 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
8689 memset (last_set, 0, regs->num * sizeof (rtx));
8692 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8694 regs->array[i].may_not_optimize = 1;
8695 regs->array[i].set_in_loop = 1;
8698 #ifdef AVOID_CCMODE_COPIES
8699 /* Don't try to move insns which set CC registers if we should not
8700 create CCmode register copies. */
8701 for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8702 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8703 regs->array[i].may_not_optimize = 1;
8706 /* Set regs->array[I].n_times_set for the new registers. */
8707 for (i = old_nregs; i < regs->num; i++)
8708 regs->array[i].n_times_set = regs->array[i].set_in_loop;
8715 /* Move MEMs into registers for the duration of the loop. */
8719 const struct loop *loop;
8721 struct loop_info *loop_info = LOOP_INFO (loop);
8722 struct loop_regs *regs = LOOP_REGS (loop);
8723 int maybe_never = 0;
8726 rtx label = NULL_RTX;
8728 /* Nonzero if the next instruction may never be executed. */
8729 int next_maybe_never = 0;
8730 int last_max_reg = max_reg_num ();
8732 if (loop_info->mems_idx == 0)
8735 /* We cannot use next_label here because it skips over normal insns. */
8736 end_label = next_nonnote_insn (loop->end);
8737 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8738 end_label = NULL_RTX;
8740 /* Check to see if it's possible that some instructions in the loop are
8741 never executed. Also check if there is a goto out of the loop other
8742 than right after the end of the loop. */
8743 for (p = next_insn_in_loop (loop, loop->scan_start);
8744 p != NULL_RTX && ! maybe_never;
8745 p = next_insn_in_loop (loop, p))
8747 if (GET_CODE (p) == CODE_LABEL)
8749 else if (GET_CODE (p) == JUMP_INSN
8750 /* If we enter the loop in the middle, and scan
8751 around to the beginning, don't set maybe_never
8752 for that. This must be an unconditional jump,
8753 otherwise the code at the top of the loop might
8754 never be executed. Unconditional jumps are
8755 followed a by barrier then loop end. */
8756 && ! (GET_CODE (p) == JUMP_INSN
8757 && JUMP_LABEL (p) == loop->top
8758 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8759 && any_uncondjump_p (p)))
8761 /* If this is a jump outside of the loop but not right
8762 after the end of the loop, we would have to emit new fixup
8763 sequences for each such label. */
8764 if (JUMP_LABEL (p) != end_label
8765 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8766 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8767 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8770 if (!any_condjump_p (p))
8771 /* Something complicated. */
8774 /* If there are any more instructions in the loop, they
8775 might not be reached. */
8776 next_maybe_never = 1;
8778 else if (next_maybe_never)
8782 /* Find start of the extended basic block that enters the loop. */
8783 for (p = loop->start;
8784 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8790 /* Build table of mems that get set to constant values before the
8792 for (; p != loop->start; p = NEXT_INSN (p))
8793 cselib_process_insn (p);
8795 /* Actually move the MEMs. */
8796 for (i = 0; i < loop_info->mems_idx; ++i)
8798 regset_head load_copies;
8799 regset_head store_copies;
8802 rtx mem = loop_info->mems[i].mem;
8805 if (MEM_VOLATILE_P (mem)
8806 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8807 /* There's no telling whether or not MEM is modified. */
8808 loop_info->mems[i].optimize = 0;
8810 /* Go through the MEMs written to in the loop to see if this
8811 one is aliased by one of them. */
8812 mem_list_entry = loop_info->store_mems;
8813 while (mem_list_entry)
8815 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8817 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8820 /* MEM is indeed aliased by this store. */
8821 loop_info->mems[i].optimize = 0;
8824 mem_list_entry = XEXP (mem_list_entry, 1);
8827 if (flag_float_store && written
8828 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8829 loop_info->mems[i].optimize = 0;
8831 /* If this MEM is written to, we must be sure that there
8832 are no reads from another MEM that aliases this one. */
8833 if (loop_info->mems[i].optimize && written)
8837 for (j = 0; j < loop_info->mems_idx; ++j)
8841 else if (true_dependence (mem,
8843 loop_info->mems[j].mem,
8846 /* It's not safe to hoist loop_info->mems[i] out of
8847 the loop because writes to it might not be
8848 seen by reads from loop_info->mems[j]. */
8849 loop_info->mems[i].optimize = 0;
8855 if (maybe_never && may_trap_p (mem))
8856 /* We can't access the MEM outside the loop; it might
8857 cause a trap that wouldn't have happened otherwise. */
8858 loop_info->mems[i].optimize = 0;
8860 if (!loop_info->mems[i].optimize)
8861 /* We thought we were going to lift this MEM out of the
8862 loop, but later discovered that we could not. */
8865 INIT_REG_SET (&load_copies);
8866 INIT_REG_SET (&store_copies);
8868 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8869 order to keep scan_loop from moving stores to this MEM
8870 out of the loop just because this REG is neither a
8871 user-variable nor used in the loop test. */
8872 reg = gen_reg_rtx (GET_MODE (mem));
8873 REG_USERVAR_P (reg) = 1;
8874 loop_info->mems[i].reg = reg;
8876 /* Now, replace all references to the MEM with the
8877 corresponding pesudos. */
8879 for (p = next_insn_in_loop (loop, loop->scan_start);
8881 p = next_insn_in_loop (loop, p))
8887 set = single_set (p);
8889 /* See if this copies the mem into a register that isn't
8890 modified afterwards. We'll try to do copy propagation
8891 a little further on. */
8893 /* @@@ This test is _way_ too conservative. */
8895 && GET_CODE (SET_DEST (set)) == REG
8896 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
8897 && REGNO (SET_DEST (set)) < last_max_reg
8898 && regs->array[REGNO (SET_DEST (set))].n_times_set == 1
8899 && rtx_equal_p (SET_SRC (set), mem))
8900 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
8902 /* See if this copies the mem from a register that isn't
8903 modified afterwards. We'll try to remove the
8904 redundant copy later on by doing a little register
8905 renaming and copy propagation. This will help
8906 to untangle things for the BIV detection code. */
8909 && GET_CODE (SET_SRC (set)) == REG
8910 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
8911 && REGNO (SET_SRC (set)) < last_max_reg
8912 && regs->array[REGNO (SET_SRC (set))].n_times_set == 1
8913 && rtx_equal_p (SET_DEST (set), mem))
8914 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
8916 /* Replace the memory reference with the shadow register. */
8917 replace_loop_mems (p, loop_info->mems[i].mem,
8918 loop_info->mems[i].reg);
8921 if (GET_CODE (p) == CODE_LABEL
8922 || GET_CODE (p) == JUMP_INSN)
8926 if (! apply_change_group ())
8927 /* We couldn't replace all occurrences of the MEM. */
8928 loop_info->mems[i].optimize = 0;
8931 /* Load the memory immediately before LOOP->START, which is
8932 the NOTE_LOOP_BEG. */
8933 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
8937 struct elt_loc_list *const_equiv = 0;
8941 struct elt_loc_list *equiv;
8942 struct elt_loc_list *best_equiv = 0;
8943 for (equiv = e->locs; equiv; equiv = equiv->next)
8945 if (CONSTANT_P (equiv->loc))
8946 const_equiv = equiv;
8947 else if (GET_CODE (equiv->loc) == REG
8948 /* Extending hard register lifetimes cuases crash
8949 on SRC targets. Doing so on non-SRC is
8950 probably also not good idea, since we most
8951 probably have pseudoregister equivalence as
8953 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
8956 /* Use the constant equivalence if that is cheap enough. */
8958 best_equiv = const_equiv;
8959 else if (const_equiv
8960 && (rtx_cost (const_equiv->loc, SET)
8961 <= rtx_cost (best_equiv->loc, SET)))
8963 best_equiv = const_equiv;
8967 /* If best_equiv is nonzero, we know that MEM is set to a
8968 constant or register before the loop. We will use this
8969 knowledge to initialize the shadow register with that
8970 constant or reg rather than by loading from MEM. */
8972 best = copy_rtx (best_equiv->loc);
8974 set = gen_move_insn (reg, best);
8975 set = emit_insn_before (set, loop->start);
8977 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
8978 copy_rtx (const_equiv->loc),
8983 if (label == NULL_RTX)
8985 label = gen_label_rtx ();
8986 emit_label_after (label, loop->end);
8989 /* Store the memory immediately after END, which is
8990 the NOTE_LOOP_END. */
8991 set = gen_move_insn (copy_rtx (mem), reg);
8992 emit_insn_after (set, label);
8995 if (loop_dump_stream)
8997 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
8998 REGNO (reg), (written ? "r/w" : "r/o"));
8999 print_rtl (loop_dump_stream, mem);
9000 fputc ('\n', loop_dump_stream);
9003 /* Attempt a bit of copy propagation. This helps untangle the
9004 data flow, and enables {basic,general}_induction_var to find
9006 EXECUTE_IF_SET_IN_REG_SET
9007 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9009 try_copy_prop (loop, reg, j);
9011 CLEAR_REG_SET (&load_copies);
9013 EXECUTE_IF_SET_IN_REG_SET
9014 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9016 try_swap_copy_prop (loop, reg, j);
9018 CLEAR_REG_SET (&store_copies);
9022 if (label != NULL_RTX && end_label != NULL_RTX)
9024 /* Now, we need to replace all references to the previous exit
9025 label with the new one. */
9030 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9032 for_each_rtx (&p, replace_label, &rr);
9034 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9035 field. This is not handled by for_each_rtx because it doesn't
9036 handle unprinted ('0') fields. We need to update JUMP_LABEL
9037 because the immediately following unroll pass will use it.
9038 replace_label would not work anyways, because that only handles
9040 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9041 JUMP_LABEL (p) = label;
9048 /* For communication between note_reg_stored and its caller. */
9049 struct note_reg_stored_arg
9055 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9058 note_reg_stored (x, setter, arg)
9059 rtx x, setter ATTRIBUTE_UNUSED;
9062 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9067 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9068 There must be exactly one insn that sets this pseudo; it will be
9069 deleted if all replacements succeed and we can prove that the register
9070 is not used after the loop. */
9073 try_copy_prop (loop, replacement, regno)
9074 const struct loop *loop;
9078 /* This is the reg that we are copying from. */
9079 rtx reg_rtx = regno_reg_rtx[regno];
9082 /* These help keep track of whether we replaced all uses of the reg. */
9083 int replaced_last = 0;
9084 int store_is_first = 0;
9086 for (insn = next_insn_in_loop (loop, loop->scan_start);
9088 insn = next_insn_in_loop (loop, insn))
9092 /* Only substitute within one extended basic block from the initializing
9094 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9097 if (! INSN_P (insn))
9100 /* Is this the initializing insn? */
9101 set = single_set (insn);
9103 && GET_CODE (SET_DEST (set)) == REG
9104 && REGNO (SET_DEST (set)) == regno)
9110 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9114 /* Only substitute after seeing the initializing insn. */
9115 if (init_insn && insn != init_insn)
9117 struct note_reg_stored_arg arg;
9119 replace_loop_regs (insn, reg_rtx, replacement);
9120 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9123 /* Stop replacing when REPLACEMENT is modified. */
9124 arg.reg = replacement;
9126 note_stores (PATTERN (insn), note_reg_stored, &arg);
9133 if (apply_change_group ())
9135 if (loop_dump_stream)
9136 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9137 if (store_is_first && replaced_last)
9139 PUT_CODE (init_insn, NOTE);
9140 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9141 if (loop_dump_stream)
9142 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9143 INSN_UID (init_insn));
9145 if (loop_dump_stream)
9146 fprintf (loop_dump_stream, ".\n");
9150 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9151 loop LOOP if the order of the sets of these registers can be
9152 swapped. There must be exactly one insn within the loop that sets
9153 this pseudo followed immediately by a move insn that sets
9154 REPLACEMENT with REGNO. */
9156 try_swap_copy_prop (loop, replacement, regno)
9157 const struct loop *loop;
9163 unsigned int new_regno;
9165 new_regno = REGNO (replacement);
9167 for (insn = next_insn_in_loop (loop, loop->scan_start);
9169 insn = next_insn_in_loop (loop, insn))
9171 /* Search for the insn that copies REGNO to NEW_REGNO? */
9172 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9173 && (set = single_set (insn))
9174 && GET_CODE (SET_DEST (set)) == REG
9175 && REGNO (SET_DEST (set)) == new_regno
9176 && GET_CODE (SET_SRC (set)) == REG
9177 && REGNO (SET_SRC (set)) == regno)
9181 if (insn != NULL_RTX)
9186 /* Some DEF-USE info would come in handy here to make this
9187 function more general. For now, just check the previous insn
9188 which is the most likely candidate for setting REGNO. */
9190 prev_insn = PREV_INSN (insn);
9192 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9193 && (prev_set = single_set (prev_insn))
9194 && GET_CODE (SET_DEST (prev_set)) == REG
9195 && REGNO (SET_DEST (prev_set)) == regno)
9198 (set (reg regno) (expr))
9199 (set (reg new_regno) (reg regno))
9201 so try converting this to:
9202 (set (reg new_regno) (expr))
9203 (set (reg regno) (reg new_regno))
9205 The former construct is often generated when a global
9206 variable used for an induction variable is shadowed by a
9207 register (NEW_REGNO). The latter construct improves the
9208 chances of GIV replacement and BIV elimination. */
9210 validate_change (prev_insn, &SET_DEST (prev_set),
9212 validate_change (insn, &SET_DEST (set),
9214 validate_change (insn, &SET_SRC (set),
9217 if (apply_change_group ())
9219 if (loop_dump_stream)
9220 fprintf (loop_dump_stream,
9221 " Swapped set of reg %d at %d with reg %d at %d.\n",
9222 regno, INSN_UID (insn),
9223 new_regno, INSN_UID (prev_insn));
9225 /* Update first use of REGNO. */
9226 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9227 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9229 /* Now perform copy propagation to hopefully
9230 remove all uses of REGNO within the loop. */
9231 try_copy_prop (loop, replacement, regno);
9237 /* Replace MEM with its associated pseudo register. This function is
9238 called from load_mems via for_each_rtx. DATA is actually a pointer
9239 to a structure describing the instruction currently being scanned
9240 and the MEM we are currently replacing. */
9243 replace_loop_mem (mem, data)
9247 loop_replace_args *args = (loop_replace_args *) data;
9253 switch (GET_CODE (m))
9259 /* We're not interested in the MEM associated with a
9260 CONST_DOUBLE, so there's no need to traverse into one. */
9264 /* This is not a MEM. */
9268 if (!rtx_equal_p (args->match, m))
9269 /* This is not the MEM we are currently replacing. */
9272 /* Actually replace the MEM. */
9273 validate_change (args->insn, mem, args->replacement, 1);
9279 replace_loop_mems (insn, mem, reg)
9284 loop_replace_args args;
9288 args.replacement = reg;
9290 for_each_rtx (&insn, replace_loop_mem, &args);
9293 /* Replace one register with another. Called through for_each_rtx; PX points
9294 to the rtx being scanned. DATA is actually a pointer to
9295 a structure of arguments. */
9298 replace_loop_reg (px, data)
9303 loop_replace_args *args = (loop_replace_args *) data;
9308 if (x == args->match)
9309 validate_change (args->insn, px, args->replacement, 1);
9315 replace_loop_regs (insn, reg, replacement)
9320 loop_replace_args args;
9324 args.replacement = replacement;
9326 for_each_rtx (&insn, replace_loop_reg, &args);
9329 /* Replace occurrences of the old exit label for the loop with the new
9330 one. DATA is an rtx_pair containing the old and new labels,
9334 replace_label (x, data)
9339 rtx old_label = ((rtx_pair *) data)->r1;
9340 rtx new_label = ((rtx_pair *) data)->r2;
9345 if (GET_CODE (l) != LABEL_REF)
9348 if (XEXP (l, 0) != old_label)
9351 XEXP (l, 0) = new_label;
9352 ++LABEL_NUSES (new_label);
9353 --LABEL_NUSES (old_label);
9359 loop_biv_dump (v, file, verbose)
9360 const struct induction *v;
9369 REGNO (v->dest_reg), INSN_UID (v->insn));
9370 fprintf (file, " const ");
9371 print_simple_rtl (file, v->add_val);
9373 if (verbose && v->final_value)
9376 fprintf (file, " final ");
9377 print_simple_rtl (file, v->final_value);
9385 loop_giv_dump (v, file, verbose)
9386 const struct induction *v;
9393 if (v->giv_type == DEST_REG)
9394 fprintf (file, "Giv %d: insn %d",
9395 REGNO (v->dest_reg), INSN_UID (v->insn));
9397 fprintf (file, "Dest address: insn %d",
9398 INSN_UID (v->insn));
9400 fprintf (file, " src reg %d benefit %d",
9401 REGNO (v->src_reg), v->benefit);
9402 fprintf (file, " lifetime %d",
9406 fprintf (file, " replaceable");
9408 if (v->no_const_addval)
9409 fprintf (file, " ncav");
9411 if (v->ext_dependant)
9413 switch (GET_CODE (v->ext_dependant))
9416 fprintf (file, " ext se");
9419 fprintf (file, " ext ze");
9422 fprintf (file, " ext tr");
9430 fprintf (file, " mult ");
9431 print_simple_rtl (file, v->mult_val);
9434 fprintf (file, " add ");
9435 print_simple_rtl (file, v->add_val);
9437 if (verbose && v->final_value)
9440 fprintf (file, " final ");
9441 print_simple_rtl (file, v->final_value);
9450 const struct induction *v;
9452 loop_biv_dump (v, stderr, 1);
9458 const struct induction *v;
9460 loop_giv_dump (v, stderr, 1);
9464 #define LOOP_BLOCK_NUM_1(INSN) \
9465 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9467 /* The notes do not have an assigned block, so look at the next insn. */
9468 #define LOOP_BLOCK_NUM(INSN) \
9469 ((INSN) ? (GET_CODE (INSN) == NOTE \
9470 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9471 : LOOP_BLOCK_NUM_1 (INSN)) \
9474 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9477 loop_dump_aux (loop, file, verbose)
9478 const struct loop *loop;
9480 int verbose ATTRIBUTE_UNUSED;
9484 if (! loop || ! file)
9487 /* Print diagnostics to compare our concept of a loop with
9488 what the loop notes say. */
9489 if (! PREV_INSN (loop->first->head)
9490 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9491 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9492 != NOTE_INSN_LOOP_BEG)
9493 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9494 INSN_UID (PREV_INSN (loop->first->head)));
9495 if (! NEXT_INSN (loop->last->end)
9496 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9497 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9498 != NOTE_INSN_LOOP_END)
9499 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9500 INSN_UID (NEXT_INSN (loop->last->end)));
9505 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9506 LOOP_BLOCK_NUM (loop->start),
9507 LOOP_INSN_UID (loop->start),
9508 LOOP_BLOCK_NUM (loop->cont),
9509 LOOP_INSN_UID (loop->cont),
9510 LOOP_BLOCK_NUM (loop->cont),
9511 LOOP_INSN_UID (loop->cont),
9512 LOOP_BLOCK_NUM (loop->vtop),
9513 LOOP_INSN_UID (loop->vtop),
9514 LOOP_BLOCK_NUM (loop->end),
9515 LOOP_INSN_UID (loop->end));
9516 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9517 LOOP_BLOCK_NUM (loop->top),
9518 LOOP_INSN_UID (loop->top),
9519 LOOP_BLOCK_NUM (loop->scan_start),
9520 LOOP_INSN_UID (loop->scan_start));
9521 fprintf (file, ";; exit_count %d", loop->exit_count);
9522 if (loop->exit_count)
9524 fputs (", labels:", file);
9525 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9527 fprintf (file, " %d ",
9528 LOOP_INSN_UID (XEXP (label, 0)));
9533 /* This can happen when a marked loop appears as two nested loops,
9534 say from while (a || b) {}. The inner loop won't match
9535 the loop markers but the outer one will. */
9536 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9537 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9541 /* Call this function from the debugger to dump LOOP. */
9545 const struct loop *loop;
9547 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9550 /* Call this function from the debugger to dump LOOPS. */
9554 const struct loops *loops;
9556 flow_loops_dump (loops, stderr, loop_dump_aux, 1);