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 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,
156 varray_type, rtx *));
158 static void count_loop_regs_set PARAMS ((const struct loop*,
159 varray_type, varray_type,
161 static void note_addr_stored PARAMS ((rtx, rtx, void *));
162 static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
163 static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
164 static void scan_loop PARAMS ((struct loop*, int));
166 static void replace_call_address PARAMS ((rtx, rtx, rtx));
168 static rtx skip_consec_insns PARAMS ((rtx, int));
169 static int libcall_benefit PARAMS ((rtx));
170 static void ignore_some_movables PARAMS ((struct loop_movables *));
171 static void force_movables PARAMS ((struct loop_movables *));
172 static void combine_movables PARAMS ((struct loop_movables *,
173 struct loop_regs *));
174 static int regs_match_p PARAMS ((rtx, rtx, struct loop_movables *));
175 static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct loop_movables *,
176 struct loop_regs *));
177 static void add_label_notes PARAMS ((rtx, rtx));
178 static void move_movables PARAMS ((struct loop *loop, struct loop_movables *,
180 static void loop_movables_add PARAMS((struct loop_movables *,
182 static void loop_movables_free PARAMS((struct loop_movables *));
183 static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
184 static void loop_bivs_find PARAMS((struct loop *));
185 static void loop_bivs_init_find PARAMS((struct loop *));
186 static void loop_bivs_check PARAMS((struct loop *));
187 static void loop_givs_find PARAMS((struct loop *));
188 static void loop_givs_check PARAMS((struct loop *));
189 static void loop_biv_eliminable_p PARAMS((struct loop *, struct iv_class *,
191 static void strength_reduce PARAMS ((struct loop *, int, int));
192 static void find_single_use_in_loop PARAMS ((rtx, rtx, varray_type));
193 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
194 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
195 static void record_biv PARAMS ((struct loop *, struct induction *,
196 rtx, rtx, rtx, rtx, rtx *,
198 static void check_final_value PARAMS ((const struct loop *,
199 struct induction *));
200 static void record_giv PARAMS ((const struct loop *, struct induction *,
201 rtx, rtx, rtx, rtx, rtx, rtx, int,
202 enum g_types, int, int, rtx *));
203 static void update_giv_derive PARAMS ((const struct loop *, rtx));
204 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
205 struct loop_info *));
206 static int basic_induction_var PARAMS ((const struct loop *, rtx,
207 enum machine_mode, rtx, rtx,
208 rtx *, rtx *, rtx **));
209 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
210 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
211 rtx *, rtx *, rtx *, int, int *,
213 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
214 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
215 static int check_dbra_loop PARAMS ((struct loop *, int));
216 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
217 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
218 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
219 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
220 static int product_cheap_p PARAMS ((rtx, rtx));
221 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
223 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
224 struct iv_class *, int, rtx));
225 static int last_use_this_basic_block PARAMS ((rtx, rtx));
226 static void record_initial PARAMS ((rtx, rtx, void *));
227 static void update_reg_last_use PARAMS ((rtx, rtx));
228 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
229 static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
231 static void load_mems PARAMS ((const struct loop *));
232 static int insert_loop_mem PARAMS ((rtx *, void *));
233 static int replace_loop_mem PARAMS ((rtx *, void *));
234 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
235 static int replace_loop_reg PARAMS ((rtx *, void *));
236 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
237 static void note_reg_stored PARAMS ((rtx, rtx, void *));
238 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
239 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
241 static int replace_label PARAMS ((rtx *, void *));
242 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
243 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
244 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
246 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
247 void debug_loop PARAMS ((const struct loop *));
248 void debug_loops PARAMS ((const struct loops *));
250 typedef struct rtx_pair
256 typedef struct loop_replace_args
263 /* Nonzero iff INSN is between START and END, inclusive. */
264 #define INSN_IN_RANGE_P(INSN, START, END) \
265 (INSN_UID (INSN) < max_uid_for_loop \
266 && INSN_LUID (INSN) >= INSN_LUID (START) \
267 && INSN_LUID (INSN) <= INSN_LUID (END))
269 /* Indirect_jump_in_function is computed once per function. */
270 static int indirect_jump_in_function;
271 static int indirect_jump_in_function_p PARAMS ((rtx));
273 static int compute_luids PARAMS ((rtx, rtx, int));
275 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
279 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
280 copy the value of the strength reduced giv to its original register. */
281 static int copy_cost;
283 /* Cost of using a register, to normalize the benefits of a giv. */
284 static int reg_address_cost;
289 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
291 reg_address_cost = address_cost (reg, SImode);
293 copy_cost = COSTS_N_INSNS (1);
296 /* Compute the mapping from uids to luids.
297 LUIDs are numbers assigned to insns, like uids,
298 except that luids increase monotonically through the code.
299 Start at insn START and stop just before END. Assign LUIDs
300 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
302 compute_luids (start, end, prev_luid)
309 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
311 if (INSN_UID (insn) >= max_uid_for_loop)
313 /* Don't assign luids to line-number NOTEs, so that the distance in
314 luids between two insns is not affected by -g. */
315 if (GET_CODE (insn) != NOTE
316 || NOTE_LINE_NUMBER (insn) <= 0)
317 uid_luid[INSN_UID (insn)] = ++i;
319 /* Give a line number note the same luid as preceding insn. */
320 uid_luid[INSN_UID (insn)] = i;
325 /* Entry point of this file. Perform loop optimization
326 on the current function. F is the first insn of the function
327 and DUMPFILE is a stream for output of a trace of actions taken
328 (or 0 if none should be output). */
331 loop_optimize (f, dumpfile, flags)
332 /* f is the first instruction of a chain of insns for one function */
339 struct loops loops_data;
340 struct loops *loops = &loops_data;
341 struct loop_info *loops_info;
342 static char *moved_once;
344 loop_dump_stream = dumpfile;
346 init_recog_no_volatile ();
348 max_reg_before_loop = max_reg_num ();
349 loop_max_reg = max_reg_before_loop;
353 /* Count the number of loops. */
356 for (insn = f; insn; insn = NEXT_INSN (insn))
358 if (GET_CODE (insn) == NOTE
359 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
363 /* Don't waste time if no loops. */
364 if (max_loop_num == 0)
367 loops->num = max_loop_num;
369 moved_once = (char *) xcalloc (max_reg_before_loop, sizeof (char));
371 /* Get size to use for tables indexed by uids.
372 Leave some space for labels allocated by find_and_verify_loops. */
373 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
375 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
376 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
377 sizeof (struct loop *));
379 /* Allocate storage for array of loops. */
380 loops->array = (struct loop *)
381 xcalloc (loops->num, sizeof (struct loop));
383 /* Find and process each loop.
384 First, find them, and record them in order of their beginnings. */
385 find_and_verify_loops (f, loops);
387 /* Allocate and initialize auxiliary loop information. */
388 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
389 for (i = 0; i < loops->num; i++)
390 loops->array[i].aux = loops_info + i;
392 /* Now find all register lifetimes. This must be done after
393 find_and_verify_loops, because it might reorder the insns in the
395 reg_scan (f, max_reg_before_loop, 1);
397 /* This must occur after reg_scan so that registers created by gcse
398 will have entries in the register tables.
400 We could have added a call to reg_scan after gcse_main in toplev.c,
401 but moving this call to init_alias_analysis is more efficient. */
402 init_alias_analysis ();
404 /* See if we went too far. Note that get_max_uid already returns
405 one more that the maximum uid of all insn. */
406 if (get_max_uid () > max_uid_for_loop)
408 /* Now reset it to the actual size we need. See above. */
409 max_uid_for_loop = get_max_uid ();
411 /* find_and_verify_loops has already called compute_luids, but it
412 might have rearranged code afterwards, so we need to recompute
414 max_luid = compute_luids (f, NULL_RTX, 0);
416 /* Don't leave gaps in uid_luid for insns that have been
417 deleted. It is possible that the first or last insn
418 using some register has been deleted by cross-jumping.
419 Make sure that uid_luid for that former insn's uid
420 points to the general area where that insn used to be. */
421 for (i = 0; i < max_uid_for_loop; i++)
423 uid_luid[0] = uid_luid[i];
424 if (uid_luid[0] != 0)
427 for (i = 0; i < max_uid_for_loop; i++)
428 if (uid_luid[i] == 0)
429 uid_luid[i] = uid_luid[i - 1];
431 /* Determine if the function has indirect jump. On some systems
432 this prevents low overhead loop instructions from being used. */
433 indirect_jump_in_function = indirect_jump_in_function_p (f);
435 /* Now scan the loops, last ones first, since this means inner ones are done
436 before outer ones. */
437 for (i = max_loop_num - 1; i >= 0; i--)
439 struct loop *loop = &loops->array[i];
440 struct loop_regs *regs = LOOP_REGS (loop);
442 regs->moved_once = moved_once;
444 if (! loop->invalid && loop->end)
445 scan_loop (loop, flags);
448 /* If there were lexical blocks inside the loop, they have been
449 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
450 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
451 the BLOCKs as well. */
452 if (write_symbols != NO_DEBUG)
455 end_alias_analysis ();
465 /* Returns the next insn, in execution order, after INSN. START and
466 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
467 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
468 insn-stream; it is used with loops that are entered near the
472 next_insn_in_loop (loop, insn)
473 const struct loop *loop;
476 insn = NEXT_INSN (insn);
478 if (insn == loop->end)
481 /* Go to the top of the loop, and continue there. */
488 if (insn == loop->scan_start)
495 /* Optimize one loop described by LOOP. */
497 /* ??? Could also move memory writes out of loops if the destination address
498 is invariant, the source is invariant, the memory write is not volatile,
499 and if we can prove that no read inside the loop can read this address
500 before the write occurs. If there is a read of this address after the
501 write, then we can also mark the memory read as invariant. */
504 scan_loop (loop, flags)
508 struct loop_info *loop_info = LOOP_INFO (loop);
509 struct loop_regs *regs = LOOP_REGS (loop);
511 rtx loop_start = loop->start;
512 rtx loop_end = loop->end;
514 /* 1 if we are scanning insns that could be executed zero times. */
516 /* 1 if we are scanning insns that might never be executed
517 due to a subroutine call which might exit before they are reached. */
519 /* Jump insn that enters the loop, or 0 if control drops in. */
520 rtx loop_entry_jump = 0;
521 /* Number of insns in the loop. */
524 rtx temp, update_start, update_end;
525 /* The SET from an insn, if it is the only SET in the insn. */
527 /* Chain describing insns movable in current loop. */
528 struct loop_movables *movables = LOOP_MOVABLES (loop);
529 /* Ratio of extra register life span we can justify
530 for saving an instruction. More if loop doesn't call subroutines
531 since in that case saving an insn makes more difference
532 and more registers are available. */
534 /* Nonzero if we are scanning instructions in a sub-loop. */
544 /* Determine whether this loop starts with a jump down to a test at
545 the end. This will occur for a small number of loops with a test
546 that is too complex to duplicate in front of the loop.
548 We search for the first insn or label in the loop, skipping NOTEs.
549 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
550 (because we might have a loop executed only once that contains a
551 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
552 (in case we have a degenerate loop).
554 Note that if we mistakenly think that a loop is entered at the top
555 when, in fact, it is entered at the exit test, the only effect will be
556 slightly poorer optimization. Making the opposite error can generate
557 incorrect code. Since very few loops now start with a jump to the
558 exit test, the code here to detect that case is very conservative. */
560 for (p = NEXT_INSN (loop_start);
562 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
563 && (GET_CODE (p) != NOTE
564 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
565 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
569 loop->scan_start = p;
571 /* Set up variables describing this loop. */
573 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
575 /* If loop has a jump before the first label,
576 the true entry is the target of that jump.
577 Start scan from there.
578 But record in LOOP->TOP the place where the end-test jumps
579 back to so we can scan that after the end of the loop. */
580 if (GET_CODE (p) == JUMP_INSN)
584 /* Loop entry must be unconditional jump (and not a RETURN) */
585 if (any_uncondjump_p (p)
586 && JUMP_LABEL (p) != 0
587 /* Check to see whether the jump actually
588 jumps out of the loop (meaning it's no loop).
589 This case can happen for things like
590 do {..} while (0). If this label was generated previously
591 by loop, we can't tell anything about it and have to reject
593 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
595 loop->top = next_label (loop->scan_start);
596 loop->scan_start = JUMP_LABEL (p);
600 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
601 as required by loop_reg_used_before_p. So skip such loops. (This
602 test may never be true, but it's best to play it safe.)
604 Also, skip loops where we do not start scanning at a label. This
605 test also rejects loops starting with a JUMP_INSN that failed the
608 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
609 || GET_CODE (loop->scan_start) != CODE_LABEL)
611 if (loop_dump_stream)
612 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
613 INSN_UID (loop_start), INSN_UID (loop_end));
617 /* Count number of times each reg is set during this loop. Set
618 VARRAY_CHAR (regs->may_not_optimize, I) if it is not safe to move
619 out the setting of register I. Set VARRAY_RTX
620 (regs->single_usage, I). */
622 /* Allocate extra space for REGS that might be created by
623 load_mems. We allocate a little extra slop as well, in the hopes
624 that even after the moving of movables creates some new registers
625 we won't have to reallocate these arrays. However, we do grow
626 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
627 nregs = max_reg_num () + loop_info->mems_idx + 16;
628 VARRAY_INT_INIT (regs->set_in_loop, nregs, "set_in_loop");
629 VARRAY_INT_INIT (regs->n_times_set, nregs, "n_times_set");
630 VARRAY_CHAR_INIT (regs->may_not_optimize, nregs, "may_not_optimize");
631 VARRAY_RTX_INIT (regs->single_usage, nregs, "single_usage");
635 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
638 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
640 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
641 VARRAY_INT (regs->set_in_loop, i) = 1;
644 #ifdef AVOID_CCMODE_COPIES
645 /* Don't try to move insns which set CC registers if we should not
646 create CCmode register copies. */
647 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
648 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
649 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
652 bcopy ((char *) ®s->set_in_loop->data,
653 (char *) ®s->n_times_set->data, nregs * sizeof (int));
655 if (loop_dump_stream)
657 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
658 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
660 fprintf (loop_dump_stream, "Continue at insn %d.\n",
661 INSN_UID (loop->cont));
664 /* Scan through the loop finding insns that are safe to move.
665 Set regs->set_in_loop negative for the reg being set, so that
666 this reg will be considered invariant for subsequent insns.
667 We consider whether subsequent insns use the reg
668 in deciding whether it is worth actually moving.
670 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
671 and therefore it is possible that the insns we are scanning
672 would never be executed. At such times, we must make sure
673 that it is safe to execute the insn once instead of zero times.
674 When MAYBE_NEVER is 0, all insns will be executed at least once
675 so that is not a problem. */
677 for (p = next_insn_in_loop (loop, loop->scan_start);
679 p = next_insn_in_loop (loop, p))
681 if (GET_CODE (p) == INSN
682 && (set = single_set (p))
683 && GET_CODE (SET_DEST (set)) == REG
684 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
689 rtx src = SET_SRC (set);
690 rtx dependencies = 0;
692 /* Figure out what to use as a source of this insn. If a REG_EQUIV
693 note is given or if a REG_EQUAL note with a constant operand is
694 specified, use it as the source and mark that we should move
695 this insn by calling emit_move_insn rather that duplicating the
698 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
700 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
702 src = XEXP (temp, 0), move_insn = 1;
705 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
706 if (temp && CONSTANT_P (XEXP (temp, 0)))
707 src = XEXP (temp, 0), move_insn = 1;
708 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
710 src = XEXP (temp, 0);
711 /* A libcall block can use regs that don't appear in
712 the equivalent expression. To move the libcall,
713 we must move those regs too. */
714 dependencies = libcall_other_reg (p, src);
718 /* Don't try to optimize a register that was made
719 by loop-optimization for an inner loop.
720 We don't know its life-span, so we can't compute the benefit. */
721 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
723 else if (/* The register is used in basic blocks other
724 than the one where it is set (meaning that
725 something after this point in the loop might
726 depend on its value before the set). */
727 ! reg_in_basic_block_p (p, SET_DEST (set))
728 /* And the set is not guaranteed to be executed one
729 the loop starts, or the value before the set is
730 needed before the set occurs...
732 ??? Note we have quadratic behaviour here, mitigated
733 by the fact that the previous test will often fail for
734 large loops. Rather than re-scanning the entire loop
735 each time for register usage, we should build tables
736 of the register usage and use them here instead. */
738 || loop_reg_used_before_p (loop, set, p)))
739 /* It is unsafe to move the set.
741 This code used to consider it OK to move a set of a variable
742 which was not created by the user and not used in an exit test.
743 That behavior is incorrect and was removed. */
745 else if ((tem = loop_invariant_p (loop, src))
746 && (dependencies == 0
747 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
748 && (VARRAY_INT (regs->set_in_loop,
749 REGNO (SET_DEST (set))) == 1
751 = consec_sets_invariant_p
752 (loop, SET_DEST (set),
753 VARRAY_INT (regs->set_in_loop,
754 REGNO (SET_DEST (set))),
756 /* If the insn can cause a trap (such as divide by zero),
757 can't move it unless it's guaranteed to be executed
758 once loop is entered. Even a function call might
759 prevent the trap insn from being reached
760 (since it might exit!) */
761 && ! ((maybe_never || call_passed)
762 && may_trap_p (src)))
764 register struct movable *m;
765 register int regno = REGNO (SET_DEST (set));
767 /* A potential lossage is where we have a case where two insns
768 can be combined as long as they are both in the loop, but
769 we move one of them outside the loop. For large loops,
770 this can lose. The most common case of this is the address
771 of a function being called.
773 Therefore, if this register is marked as being used exactly
774 once if we are in a loop with calls (a "large loop"), see if
775 we can replace the usage of this register with the source
776 of this SET. If we can, delete this insn.
778 Don't do this if P has a REG_RETVAL note or if we have
779 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
781 if (loop_info->has_call
782 && VARRAY_RTX (regs->single_usage, regno) != 0
783 && VARRAY_RTX (regs->single_usage, regno) != const0_rtx
784 && REGNO_FIRST_UID (regno) == INSN_UID (p)
785 && (REGNO_LAST_UID (regno)
786 == INSN_UID (VARRAY_RTX (regs->single_usage, regno)))
787 && VARRAY_INT (regs->set_in_loop, regno) == 1
788 && ! side_effects_p (SET_SRC (set))
789 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
790 && (! SMALL_REGISTER_CLASSES
791 || (! (GET_CODE (SET_SRC (set)) == REG
792 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
793 /* This test is not redundant; SET_SRC (set) might be
794 a call-clobbered register and the life of REGNO
795 might span a call. */
796 && ! modified_between_p (SET_SRC (set), p,
798 (regs->single_usage, regno))
799 && no_labels_between_p (p, VARRAY_RTX (regs->single_usage,
801 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
803 (regs->single_usage, regno)))
805 /* Replace any usage in a REG_EQUAL note. Must copy the
806 new source, so that we don't get rtx sharing between the
807 SET_SOURCE and REG_NOTES of insn p. */
808 REG_NOTES (VARRAY_RTX (regs->single_usage, regno))
809 = replace_rtx (REG_NOTES (VARRAY_RTX
810 (regs->single_usage, regno)),
811 SET_DEST (set), copy_rtx (SET_SRC (set)));
814 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
815 NOTE_SOURCE_FILE (p) = 0;
816 VARRAY_INT (regs->set_in_loop, regno) = 0;
820 m = (struct movable *) xmalloc (sizeof (struct movable));
824 m->dependencies = dependencies;
825 m->set_dest = SET_DEST (set);
827 m->consec = VARRAY_INT (regs->set_in_loop,
828 REGNO (SET_DEST (set))) - 1;
832 m->move_insn = move_insn;
833 m->move_insn_first = 0;
834 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
835 m->savemode = VOIDmode;
837 /* Set M->cond if either loop_invariant_p
838 or consec_sets_invariant_p returned 2
839 (only conditionally invariant). */
840 m->cond = ((tem | tem1 | tem2) > 1);
841 m->global = LOOP_REG_GLOBAL_P (loop, regno);
843 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
844 m->savings = VARRAY_INT (regs->n_times_set, regno);
845 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
846 m->savings += libcall_benefit (p);
847 VARRAY_INT (regs->set_in_loop, regno) = move_insn ? -2 : -1;
848 /* Add M to the end of the chain MOVABLES. */
849 loop_movables_add (movables, m);
853 /* It is possible for the first instruction to have a
854 REG_EQUAL note but a non-invariant SET_SRC, so we must
855 remember the status of the first instruction in case
856 the last instruction doesn't have a REG_EQUAL note. */
857 m->move_insn_first = m->move_insn;
859 /* Skip this insn, not checking REG_LIBCALL notes. */
860 p = next_nonnote_insn (p);
861 /* Skip the consecutive insns, if there are any. */
862 p = skip_consec_insns (p, m->consec);
863 /* Back up to the last insn of the consecutive group. */
864 p = prev_nonnote_insn (p);
866 /* We must now reset m->move_insn, m->is_equiv, and possibly
867 m->set_src to correspond to the effects of all the
869 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
871 m->set_src = XEXP (temp, 0), m->move_insn = 1;
874 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
875 if (temp && CONSTANT_P (XEXP (temp, 0)))
876 m->set_src = XEXP (temp, 0), m->move_insn = 1;
881 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
884 /* If this register is always set within a STRICT_LOW_PART
885 or set to zero, then its high bytes are constant.
886 So clear them outside the loop and within the loop
887 just load the low bytes.
888 We must check that the machine has an instruction to do so.
889 Also, if the value loaded into the register
890 depends on the same register, this cannot be done. */
891 else if (SET_SRC (set) == const0_rtx
892 && GET_CODE (NEXT_INSN (p)) == INSN
893 && (set1 = single_set (NEXT_INSN (p)))
894 && GET_CODE (set1) == SET
895 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
896 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
897 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
899 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
901 register int regno = REGNO (SET_DEST (set));
902 if (VARRAY_INT (regs->set_in_loop, regno) == 2)
904 register struct movable *m;
905 m = (struct movable *) alloca (sizeof (struct movable));
908 m->set_dest = SET_DEST (set);
915 m->move_insn_first = 0;
917 /* If the insn may not be executed on some cycles,
918 we can't clear the whole reg; clear just high part.
919 Not even if the reg is used only within this loop.
926 Clearing x before the inner loop could clobber a value
927 being saved from the last time around the outer loop.
928 However, if the reg is not used outside this loop
929 and all uses of the register are in the same
930 basic block as the store, there is no problem.
932 If this insn was made by loop, we don't know its
933 INSN_LUID and hence must make a conservative
935 m->global = (INSN_UID (p) >= max_uid_for_loop
936 || LOOP_REG_GLOBAL_P (loop, regno)
937 || (labels_in_range_p
938 (p, REGNO_FIRST_LUID (regno))));
939 if (maybe_never && m->global)
940 m->savemode = GET_MODE (SET_SRC (set1));
942 m->savemode = VOIDmode;
946 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
948 VARRAY_INT (regs->set_in_loop, regno) = -1;
949 /* Add M to the end of the chain MOVABLES. */
950 loop_movables_add (movables, m);
954 /* Past a call insn, we get to insns which might not be executed
955 because the call might exit. This matters for insns that trap.
956 Constant and pure call insns always return, so they don't count. */
957 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
959 /* Past a label or a jump, we get to insns for which we
960 can't count on whether or how many times they will be
961 executed during each iteration. Therefore, we can
962 only move out sets of trivial variables
963 (those not used after the loop). */
964 /* Similar code appears twice in strength_reduce. */
965 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
966 /* If we enter the loop in the middle, and scan around to the
967 beginning, don't set maybe_never for that. This must be an
968 unconditional jump, otherwise the code at the top of the
969 loop might never be executed. Unconditional jumps are
970 followed a by barrier then loop end. */
971 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
972 && NEXT_INSN (NEXT_INSN (p)) == loop_end
973 && any_uncondjump_p (p)))
975 else if (GET_CODE (p) == NOTE)
977 /* At the virtual top of a converted loop, insns are again known to
978 be executed: logically, the loop begins here even though the exit
979 code has been duplicated. */
980 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
981 maybe_never = call_passed = 0;
982 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
984 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
989 /* If one movable subsumes another, ignore that other. */
991 ignore_some_movables (movables);
993 /* For each movable insn, see if the reg that it loads
994 leads when it dies right into another conditionally movable insn.
995 If so, record that the second insn "forces" the first one,
996 since the second can be moved only if the first is. */
998 force_movables (movables);
1000 /* See if there are multiple movable insns that load the same value.
1001 If there are, make all but the first point at the first one
1002 through the `match' field, and add the priorities of them
1003 all together as the priority of the first. */
1005 combine_movables (movables, regs);
1007 /* Now consider each movable insn to decide whether it is worth moving.
1008 Store 0 in regs->set_in_loop for each reg that is moved.
1010 Generally this increases code size, so do not move moveables when
1011 optimizing for code size. */
1013 if (! optimize_size)
1014 move_movables (loop, movables, threshold, insn_count);
1016 /* Now candidates that still are negative are those not moved.
1017 Change regs->set_in_loop to indicate that those are not actually
1019 for (i = 0; i < nregs; i++)
1020 if (VARRAY_INT (regs->set_in_loop, i) < 0)
1021 VARRAY_INT (regs->set_in_loop, i) = VARRAY_INT (regs->n_times_set, i);
1023 /* Now that we've moved some things out of the loop, we might be able to
1024 hoist even more memory references. */
1025 load_mems_and_recount_loop_regs_set (loop, &insn_count);
1027 for (update_start = loop_start;
1028 PREV_INSN (update_start)
1029 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
1030 update_start = PREV_INSN (update_start))
1032 update_end = NEXT_INSN (loop_end);
1034 reg_scan_update (update_start, update_end, loop_max_reg);
1035 loop_max_reg = max_reg_num ();
1037 if (flag_strength_reduce)
1039 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1040 /* Ensure our label doesn't go away. */
1041 LABEL_NUSES (update_end)++;
1043 strength_reduce (loop, insn_count, flags);
1045 reg_scan_update (update_start, update_end, loop_max_reg);
1046 loop_max_reg = max_reg_num ();
1048 if (update_end && GET_CODE (update_end) == CODE_LABEL
1049 && --LABEL_NUSES (update_end) == 0)
1050 delete_insn (update_end);
1054 /* The movable information is required for strength reduction. */
1055 loop_movables_free (movables);
1057 VARRAY_FREE (regs->single_usage);
1058 VARRAY_FREE (regs->set_in_loop);
1059 VARRAY_FREE (regs->n_times_set);
1060 VARRAY_FREE (regs->may_not_optimize);
1063 /* Add elements to *OUTPUT to record all the pseudo-regs
1064 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1067 record_excess_regs (in_this, not_in_this, output)
1068 rtx in_this, not_in_this;
1075 code = GET_CODE (in_this);
1089 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1090 && ! reg_mentioned_p (in_this, not_in_this))
1091 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1098 fmt = GET_RTX_FORMAT (code);
1099 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1106 for (j = 0; j < XVECLEN (in_this, i); j++)
1107 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1111 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1117 /* Check what regs are referred to in the libcall block ending with INSN,
1118 aside from those mentioned in the equivalent value.
1119 If there are none, return 0.
1120 If there are one or more, return an EXPR_LIST containing all of them. */
1123 libcall_other_reg (insn, equiv)
1126 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1127 rtx p = XEXP (note, 0);
1130 /* First, find all the regs used in the libcall block
1131 that are not mentioned as inputs to the result. */
1135 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1136 || GET_CODE (p) == CALL_INSN)
1137 record_excess_regs (PATTERN (p), equiv, &output);
1144 /* Return 1 if all uses of REG
1145 are between INSN and the end of the basic block. */
1148 reg_in_basic_block_p (insn, reg)
1151 int regno = REGNO (reg);
1154 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1157 /* Search this basic block for the already recorded last use of the reg. */
1158 for (p = insn; p; p = NEXT_INSN (p))
1160 switch (GET_CODE (p))
1167 /* Ordinary insn: if this is the last use, we win. */
1168 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1173 /* Jump insn: if this is the last use, we win. */
1174 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1176 /* Otherwise, it's the end of the basic block, so we lose. */
1181 /* It's the end of the basic block, so we lose. */
1189 /* The "last use" that was recorded can't be found after the first
1190 use. This can happen when the last use was deleted while
1191 processing an inner loop, this inner loop was then completely
1192 unrolled, and the outer loop is always exited after the inner loop,
1193 so that everything after the first use becomes a single basic block. */
1197 /* Compute the benefit of eliminating the insns in the block whose
1198 last insn is LAST. This may be a group of insns used to compute a
1199 value directly or can contain a library call. */
1202 libcall_benefit (last)
1208 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1209 insn != last; insn = NEXT_INSN (insn))
1211 if (GET_CODE (insn) == CALL_INSN)
1212 benefit += 10; /* Assume at least this many insns in a library
1214 else if (GET_CODE (insn) == INSN
1215 && GET_CODE (PATTERN (insn)) != USE
1216 && GET_CODE (PATTERN (insn)) != CLOBBER)
1223 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1226 skip_consec_insns (insn, count)
1230 for (; count > 0; count--)
1234 /* If first insn of libcall sequence, skip to end. */
1235 /* Do this at start of loop, since INSN is guaranteed to
1237 if (GET_CODE (insn) != NOTE
1238 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1239 insn = XEXP (temp, 0);
1242 insn = NEXT_INSN (insn);
1243 while (GET_CODE (insn) == NOTE);
1249 /* Ignore any movable whose insn falls within a libcall
1250 which is part of another movable.
1251 We make use of the fact that the movable for the libcall value
1252 was made later and so appears later on the chain. */
1255 ignore_some_movables (movables)
1256 struct loop_movables *movables;
1258 register struct movable *m, *m1;
1260 for (m = movables->head; m; m = m->next)
1262 /* Is this a movable for the value of a libcall? */
1263 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1267 /* Check for earlier movables inside that range,
1268 and mark them invalid. We cannot use LUIDs here because
1269 insns created by loop.c for prior loops don't have LUIDs.
1270 Rather than reject all such insns from movables, we just
1271 explicitly check each insn in the libcall (since invariant
1272 libcalls aren't that common). */
1273 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1274 for (m1 = movables->head; m1 != m; m1 = m1->next)
1275 if (m1->insn == insn)
1281 /* For each movable insn, see if the reg that it loads
1282 leads when it dies right into another conditionally movable insn.
1283 If so, record that the second insn "forces" the first one,
1284 since the second can be moved only if the first is. */
1287 force_movables (movables)
1288 struct loop_movables *movables;
1290 register struct movable *m, *m1;
1291 for (m1 = movables->head; m1; m1 = m1->next)
1292 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1293 if (!m1->partial && !m1->done)
1295 int regno = m1->regno;
1296 for (m = m1->next; m; m = m->next)
1297 /* ??? Could this be a bug? What if CSE caused the
1298 register of M1 to be used after this insn?
1299 Since CSE does not update regno_last_uid,
1300 this insn M->insn might not be where it dies.
1301 But very likely this doesn't matter; what matters is
1302 that M's reg is computed from M1's reg. */
1303 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1306 if (m != 0 && m->set_src == m1->set_dest
1307 /* If m->consec, m->set_src isn't valid. */
1311 /* Increase the priority of the moving the first insn
1312 since it permits the second to be moved as well. */
1316 m1->lifetime += m->lifetime;
1317 m1->savings += m->savings;
1322 /* Find invariant expressions that are equal and can be combined into
1326 combine_movables (movables, regs)
1327 struct loop_movables *movables;
1328 struct loop_regs *regs;
1330 register struct movable *m;
1331 char *matched_regs = (char *) xmalloc (regs->num);
1332 enum machine_mode mode;
1334 /* Regs that are set more than once are not allowed to match
1335 or be matched. I'm no longer sure why not. */
1336 /* Perhaps testing m->consec_sets would be more appropriate here? */
1338 for (m = movables->head; m; m = m->next)
1339 if (m->match == 0 && VARRAY_INT (regs->n_times_set, m->regno) == 1
1342 register struct movable *m1;
1343 int regno = m->regno;
1345 memset (matched_regs, 0, regs->num);
1346 matched_regs[regno] = 1;
1348 /* We want later insns to match the first one. Don't make the first
1349 one match any later ones. So start this loop at m->next. */
1350 for (m1 = m->next; m1; m1 = m1->next)
1351 if (m != m1 && m1->match == 0 && VARRAY_INT (regs->n_times_set,
1353 /* A reg used outside the loop mustn't be eliminated. */
1355 /* A reg used for zero-extending mustn't be eliminated. */
1357 && (matched_regs[m1->regno]
1360 /* Can combine regs with different modes loaded from the
1361 same constant only if the modes are the same or
1362 if both are integer modes with M wider or the same
1363 width as M1. The check for integer is redundant, but
1364 safe, since the only case of differing destination
1365 modes with equal sources is when both sources are
1366 VOIDmode, i.e., CONST_INT. */
1367 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1368 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1369 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1370 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1371 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1372 /* See if the source of M1 says it matches M. */
1373 && ((GET_CODE (m1->set_src) == REG
1374 && matched_regs[REGNO (m1->set_src)])
1375 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1377 && ((m->dependencies == m1->dependencies)
1378 || rtx_equal_p (m->dependencies, m1->dependencies)))
1380 m->lifetime += m1->lifetime;
1381 m->savings += m1->savings;
1384 matched_regs[m1->regno] = 1;
1388 /* Now combine the regs used for zero-extension.
1389 This can be done for those not marked `global'
1390 provided their lives don't overlap. */
1392 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1393 mode = GET_MODE_WIDER_MODE (mode))
1395 register struct movable *m0 = 0;
1397 /* Combine all the registers for extension from mode MODE.
1398 Don't combine any that are used outside this loop. */
1399 for (m = movables->head; m; m = m->next)
1400 if (m->partial && ! m->global
1401 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1403 register struct movable *m1;
1404 int first = REGNO_FIRST_LUID (m->regno);
1405 int last = REGNO_LAST_LUID (m->regno);
1409 /* First one: don't check for overlap, just record it. */
1414 /* Make sure they extend to the same mode.
1415 (Almost always true.) */
1416 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1419 /* We already have one: check for overlap with those
1420 already combined together. */
1421 for (m1 = movables->head; m1 != m; m1 = m1->next)
1422 if (m1 == m0 || (m1->partial && m1->match == m0))
1423 if (! (REGNO_FIRST_LUID (m1->regno) > last
1424 || REGNO_LAST_LUID (m1->regno) < first))
1427 /* No overlap: we can combine this with the others. */
1428 m0->lifetime += m->lifetime;
1429 m0->savings += m->savings;
1439 free (matched_regs);
1442 /* Return 1 if regs X and Y will become the same if moved. */
1445 regs_match_p (x, y, movables)
1447 struct loop_movables *movables;
1449 unsigned int xn = REGNO (x);
1450 unsigned int yn = REGNO (y);
1451 struct movable *mx, *my;
1453 for (mx = movables->head; mx; mx = mx->next)
1454 if (mx->regno == xn)
1457 for (my = movables->head; my; my = my->next)
1458 if (my->regno == yn)
1462 && ((mx->match == my->match && mx->match != 0)
1464 || mx == my->match));
1467 /* Return 1 if X and Y are identical-looking rtx's.
1468 This is the Lisp function EQUAL for rtx arguments.
1470 If two registers are matching movables or a movable register and an
1471 equivalent constant, consider them equal. */
1474 rtx_equal_for_loop_p (x, y, movables, regs)
1476 struct loop_movables *movables;
1477 struct loop_regs *regs;
1481 register struct movable *m;
1482 register enum rtx_code code;
1483 register const char *fmt;
1487 if (x == 0 || y == 0)
1490 code = GET_CODE (x);
1492 /* If we have a register and a constant, they may sometimes be
1494 if (GET_CODE (x) == REG && VARRAY_INT (regs->set_in_loop, REGNO (x)) == -2
1497 for (m = movables->head; m; m = m->next)
1498 if (m->move_insn && m->regno == REGNO (x)
1499 && rtx_equal_p (m->set_src, y))
1502 else if (GET_CODE (y) == REG && VARRAY_INT (regs->set_in_loop,
1506 for (m = movables->head; m; m = m->next)
1507 if (m->move_insn && m->regno == REGNO (y)
1508 && rtx_equal_p (m->set_src, x))
1512 /* Otherwise, rtx's of different codes cannot be equal. */
1513 if (code != GET_CODE (y))
1516 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1517 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1519 if (GET_MODE (x) != GET_MODE (y))
1522 /* These three types of rtx's can be compared nonrecursively. */
1524 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1526 if (code == LABEL_REF)
1527 return XEXP (x, 0) == XEXP (y, 0);
1528 if (code == SYMBOL_REF)
1529 return XSTR (x, 0) == XSTR (y, 0);
1531 /* Compare the elements. If any pair of corresponding elements
1532 fail to match, return 0 for the whole things. */
1534 fmt = GET_RTX_FORMAT (code);
1535 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1540 if (XWINT (x, i) != XWINT (y, i))
1545 if (XINT (x, i) != XINT (y, i))
1550 /* Two vectors must have the same length. */
1551 if (XVECLEN (x, i) != XVECLEN (y, i))
1554 /* And the corresponding elements must match. */
1555 for (j = 0; j < XVECLEN (x, i); j++)
1556 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1557 movables, regs) == 0)
1562 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1568 if (strcmp (XSTR (x, i), XSTR (y, i)))
1573 /* These are just backpointers, so they don't matter. */
1579 /* It is believed that rtx's at this level will never
1580 contain anything but integers and other rtx's,
1581 except for within LABEL_REFs and SYMBOL_REFs. */
1589 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1590 insns in INSNS which use the reference. */
1593 add_label_notes (x, insns)
1597 enum rtx_code code = GET_CODE (x);
1602 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1604 /* This code used to ignore labels that referred to dispatch tables to
1605 avoid flow generating (slighly) worse code.
1607 We no longer ignore such label references (see LABEL_REF handling in
1608 mark_jump_label for additional information). */
1609 for (insn = insns; insn; insn = NEXT_INSN (insn))
1610 if (reg_mentioned_p (XEXP (x, 0), insn))
1611 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1615 fmt = GET_RTX_FORMAT (code);
1616 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1619 add_label_notes (XEXP (x, i), insns);
1620 else if (fmt[i] == 'E')
1621 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1622 add_label_notes (XVECEXP (x, i, j), insns);
1626 /* Scan MOVABLES, and move the insns that deserve to be moved.
1627 If two matching movables are combined, replace one reg with the
1628 other throughout. */
1631 move_movables (loop, movables, threshold, insn_count)
1633 struct loop_movables *movables;
1637 struct loop_regs *regs = LOOP_REGS (loop);
1638 int nregs = regs->num;
1640 register struct movable *m;
1642 rtx loop_start = loop->start;
1643 rtx loop_end = loop->end;
1644 /* Map of pseudo-register replacements to handle combining
1645 when we move several insns that load the same value
1646 into different pseudo-registers. */
1647 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1648 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1652 for (m = movables->head; m; m = m->next)
1654 /* Describe this movable insn. */
1656 if (loop_dump_stream)
1658 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1659 INSN_UID (m->insn), m->regno, m->lifetime);
1661 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1663 fprintf (loop_dump_stream, "cond ");
1665 fprintf (loop_dump_stream, "force ");
1667 fprintf (loop_dump_stream, "global ");
1669 fprintf (loop_dump_stream, "done ");
1671 fprintf (loop_dump_stream, "move-insn ");
1673 fprintf (loop_dump_stream, "matches %d ",
1674 INSN_UID (m->match->insn));
1676 fprintf (loop_dump_stream, "forces %d ",
1677 INSN_UID (m->forces->insn));
1680 /* Count movables. Value used in heuristics in strength_reduce. */
1683 /* Ignore the insn if it's already done (it matched something else).
1684 Otherwise, see if it is now safe to move. */
1688 || (1 == loop_invariant_p (loop, m->set_src)
1689 && (m->dependencies == 0
1690 || 1 == loop_invariant_p (loop, m->dependencies))
1692 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1695 && (! m->forces || m->forces->done))
1699 int savings = m->savings;
1701 /* We have an insn that is safe to move.
1702 Compute its desirability. */
1707 if (loop_dump_stream)
1708 fprintf (loop_dump_stream, "savings %d ", savings);
1710 if (regs->moved_once[regno] && loop_dump_stream)
1711 fprintf (loop_dump_stream, "halved since already moved ");
1713 /* An insn MUST be moved if we already moved something else
1714 which is safe only if this one is moved too: that is,
1715 if already_moved[REGNO] is nonzero. */
1717 /* An insn is desirable to move if the new lifetime of the
1718 register is no more than THRESHOLD times the old lifetime.
1719 If it's not desirable, it means the loop is so big
1720 that moving won't speed things up much,
1721 and it is liable to make register usage worse. */
1723 /* It is also desirable to move if it can be moved at no
1724 extra cost because something else was already moved. */
1726 if (already_moved[regno]
1727 || flag_move_all_movables
1728 || (threshold * savings * m->lifetime) >=
1729 (regs->moved_once[regno] ? insn_count * 2 : insn_count)
1730 || (m->forces && m->forces->done
1731 && VARRAY_INT (regs->n_times_set, m->forces->regno) == 1))
1734 register struct movable *m1;
1735 rtx first = NULL_RTX;
1737 /* Now move the insns that set the reg. */
1739 if (m->partial && m->match)
1743 /* Find the end of this chain of matching regs.
1744 Thus, we load each reg in the chain from that one reg.
1745 And that reg is loaded with 0 directly,
1746 since it has ->match == 0. */
1747 for (m1 = m; m1->match; m1 = m1->match);
1748 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1749 SET_DEST (PATTERN (m1->insn)));
1750 i1 = emit_insn_before (newpat, loop_start);
1752 /* Mark the moved, invariant reg as being allowed to
1753 share a hard reg with the other matching invariant. */
1754 REG_NOTES (i1) = REG_NOTES (m->insn);
1755 r1 = SET_DEST (PATTERN (m->insn));
1756 r2 = SET_DEST (PATTERN (m1->insn));
1758 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1759 gen_rtx_EXPR_LIST (VOIDmode, r2,
1761 delete_insn (m->insn);
1766 if (loop_dump_stream)
1767 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1769 /* If we are to re-generate the item being moved with a
1770 new move insn, first delete what we have and then emit
1771 the move insn before the loop. */
1772 else if (m->move_insn)
1776 for (count = m->consec; count >= 0; count--)
1778 /* If this is the first insn of a library call sequence,
1780 if (GET_CODE (p) != NOTE
1781 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1784 /* If this is the last insn of a libcall sequence, then
1785 delete every insn in the sequence except the last.
1786 The last insn is handled in the normal manner. */
1787 if (GET_CODE (p) != NOTE
1788 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1790 temp = XEXP (temp, 0);
1792 temp = delete_insn (temp);
1796 p = delete_insn (p);
1798 /* simplify_giv_expr expects that it can walk the insns
1799 at m->insn forwards and see this old sequence we are
1800 tossing here. delete_insn does preserve the next
1801 pointers, but when we skip over a NOTE we must fix
1802 it up. Otherwise that code walks into the non-deleted
1804 while (p && GET_CODE (p) == NOTE)
1805 p = NEXT_INSN (temp) = NEXT_INSN (p);
1809 emit_move_insn (m->set_dest, m->set_src);
1810 temp = get_insns ();
1813 add_label_notes (m->set_src, temp);
1815 i1 = emit_insns_before (temp, loop_start);
1816 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1818 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1819 m->set_src, REG_NOTES (i1));
1821 if (loop_dump_stream)
1822 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1824 /* The more regs we move, the less we like moving them. */
1829 for (count = m->consec; count >= 0; count--)
1833 /* If first insn of libcall sequence, skip to end. */
1834 /* Do this at start of loop, since p is guaranteed to
1836 if (GET_CODE (p) != NOTE
1837 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1840 /* If last insn of libcall sequence, move all
1841 insns except the last before the loop. The last
1842 insn is handled in the normal manner. */
1843 if (GET_CODE (p) != NOTE
1844 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1848 rtx fn_address_insn = 0;
1851 for (temp = XEXP (temp, 0); temp != p;
1852 temp = NEXT_INSN (temp))
1858 if (GET_CODE (temp) == NOTE)
1861 body = PATTERN (temp);
1863 /* Find the next insn after TEMP,
1864 not counting USE or NOTE insns. */
1865 for (next = NEXT_INSN (temp); next != p;
1866 next = NEXT_INSN (next))
1867 if (! (GET_CODE (next) == INSN
1868 && GET_CODE (PATTERN (next)) == USE)
1869 && GET_CODE (next) != NOTE)
1872 /* If that is the call, this may be the insn
1873 that loads the function address.
1875 Extract the function address from the insn
1876 that loads it into a register.
1877 If this insn was cse'd, we get incorrect code.
1879 So emit a new move insn that copies the
1880 function address into the register that the
1881 call insn will use. flow.c will delete any
1882 redundant stores that we have created. */
1883 if (GET_CODE (next) == CALL_INSN
1884 && GET_CODE (body) == SET
1885 && GET_CODE (SET_DEST (body)) == REG
1886 && (n = find_reg_note (temp, REG_EQUAL,
1889 fn_reg = SET_SRC (body);
1890 if (GET_CODE (fn_reg) != REG)
1891 fn_reg = SET_DEST (body);
1892 fn_address = XEXP (n, 0);
1893 fn_address_insn = temp;
1895 /* We have the call insn.
1896 If it uses the register we suspect it might,
1897 load it with the correct address directly. */
1898 if (GET_CODE (temp) == CALL_INSN
1900 && reg_referenced_p (fn_reg, body))
1901 emit_insn_after (gen_move_insn (fn_reg,
1905 if (GET_CODE (temp) == CALL_INSN)
1907 i1 = emit_call_insn_before (body, loop_start);
1908 /* Because the USAGE information potentially
1909 contains objects other than hard registers
1910 we need to copy it. */
1911 if (CALL_INSN_FUNCTION_USAGE (temp))
1912 CALL_INSN_FUNCTION_USAGE (i1)
1913 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1916 i1 = emit_insn_before (body, loop_start);
1919 if (temp == fn_address_insn)
1920 fn_address_insn = i1;
1921 REG_NOTES (i1) = REG_NOTES (temp);
1927 if (m->savemode != VOIDmode)
1929 /* P sets REG to zero; but we should clear only
1930 the bits that are not covered by the mode
1932 rtx reg = m->set_dest;
1938 (GET_MODE (reg), and_optab, reg,
1939 GEN_INT ((((HOST_WIDE_INT) 1
1940 << GET_MODE_BITSIZE (m->savemode)))
1942 reg, 1, OPTAB_LIB_WIDEN);
1946 emit_move_insn (reg, tem);
1947 sequence = gen_sequence ();
1949 i1 = emit_insn_before (sequence, loop_start);
1951 else if (GET_CODE (p) == CALL_INSN)
1953 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1954 /* Because the USAGE information potentially
1955 contains objects other than hard registers
1956 we need to copy it. */
1957 if (CALL_INSN_FUNCTION_USAGE (p))
1958 CALL_INSN_FUNCTION_USAGE (i1)
1959 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1961 else if (count == m->consec && m->move_insn_first)
1963 /* The SET_SRC might not be invariant, so we must
1964 use the REG_EQUAL note. */
1966 emit_move_insn (m->set_dest, m->set_src);
1967 temp = get_insns ();
1970 add_label_notes (m->set_src, temp);
1972 i1 = emit_insns_before (temp, loop_start);
1973 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1975 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1977 m->set_src, REG_NOTES (i1));
1980 i1 = emit_insn_before (PATTERN (p), loop_start);
1982 if (REG_NOTES (i1) == 0)
1984 REG_NOTES (i1) = REG_NOTES (p);
1986 /* If there is a REG_EQUAL note present whose value
1987 is not loop invariant, then delete it, since it
1988 may cause problems with later optimization passes.
1989 It is possible for cse to create such notes
1990 like this as a result of record_jump_cond. */
1992 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
1993 && ! loop_invariant_p (loop, XEXP (temp, 0)))
1994 remove_note (i1, temp);
2000 if (loop_dump_stream)
2001 fprintf (loop_dump_stream, " moved to %d",
2004 /* If library call, now fix the REG_NOTES that contain
2005 insn pointers, namely REG_LIBCALL on FIRST
2006 and REG_RETVAL on I1. */
2007 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2009 XEXP (temp, 0) = first;
2010 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2011 XEXP (temp, 0) = i1;
2018 /* simplify_giv_expr expects that it can walk the insns
2019 at m->insn forwards and see this old sequence we are
2020 tossing here. delete_insn does preserve the next
2021 pointers, but when we skip over a NOTE we must fix
2022 it up. Otherwise that code walks into the non-deleted
2024 while (p && GET_CODE (p) == NOTE)
2025 p = NEXT_INSN (temp) = NEXT_INSN (p);
2028 /* The more regs we move, the less we like moving them. */
2032 /* Any other movable that loads the same register
2034 already_moved[regno] = 1;
2036 /* This reg has been moved out of one loop. */
2037 regs->moved_once[regno] = 1;
2039 /* The reg set here is now invariant. */
2041 VARRAY_INT (regs->set_in_loop, regno) = 0;
2045 /* Change the length-of-life info for the register
2046 to say it lives at least the full length of this loop.
2047 This will help guide optimizations in outer loops. */
2049 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2050 /* This is the old insn before all the moved insns.
2051 We can't use the moved insn because it is out of range
2052 in uid_luid. Only the old insns have luids. */
2053 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2054 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2055 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2057 /* Combine with this moved insn any other matching movables. */
2060 for (m1 = movables->head; m1; m1 = m1->next)
2065 /* Schedule the reg loaded by M1
2066 for replacement so that shares the reg of M.
2067 If the modes differ (only possible in restricted
2068 circumstances, make a SUBREG.
2070 Note this assumes that the target dependent files
2071 treat REG and SUBREG equally, including within
2072 GO_IF_LEGITIMATE_ADDRESS and in all the
2073 predicates since we never verify that replacing the
2074 original register with a SUBREG results in a
2075 recognizable insn. */
2076 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2077 reg_map[m1->regno] = m->set_dest;
2080 = gen_lowpart_common (GET_MODE (m1->set_dest),
2083 /* Get rid of the matching insn
2084 and prevent further processing of it. */
2087 /* if library call, delete all insn except last, which
2089 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2092 for (temp = XEXP (temp, 0); temp != m1->insn;
2093 temp = NEXT_INSN (temp))
2096 delete_insn (m1->insn);
2098 /* Any other movable that loads the same register
2100 already_moved[m1->regno] = 1;
2102 /* The reg merged here is now invariant,
2103 if the reg it matches is invariant. */
2105 VARRAY_INT (regs->set_in_loop, m1->regno) = 0;
2108 else if (loop_dump_stream)
2109 fprintf (loop_dump_stream, "not desirable");
2111 else if (loop_dump_stream && !m->match)
2112 fprintf (loop_dump_stream, "not safe");
2114 if (loop_dump_stream)
2115 fprintf (loop_dump_stream, "\n");
2119 new_start = loop_start;
2121 /* Go through all the instructions in the loop, making
2122 all the register substitutions scheduled in REG_MAP. */
2123 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2124 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2125 || GET_CODE (p) == CALL_INSN)
2127 replace_regs (PATTERN (p), reg_map, nregs, 0);
2128 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2134 free (already_moved);
2139 loop_movables_add (movables, m)
2140 struct loop_movables *movables;
2143 if (movables->head == 0)
2146 movables->last->next = m;
2152 loop_movables_free (movables)
2153 struct loop_movables *movables;
2156 struct movable *m_next;
2158 for (m = movables->head; m; m = m_next)
2166 /* Scan X and replace the address of any MEM in it with ADDR.
2167 REG is the address that MEM should have before the replacement. */
2170 replace_call_address (x, reg, addr)
2173 register enum rtx_code code;
2175 register const char *fmt;
2179 code = GET_CODE (x);
2193 /* Short cut for very common case. */
2194 replace_call_address (XEXP (x, 1), reg, addr);
2198 /* Short cut for very common case. */
2199 replace_call_address (XEXP (x, 0), reg, addr);
2203 /* If this MEM uses a reg other than the one we expected,
2204 something is wrong. */
2205 if (XEXP (x, 0) != reg)
2214 fmt = GET_RTX_FORMAT (code);
2215 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2218 replace_call_address (XEXP (x, i), reg, addr);
2219 else if (fmt[i] == 'E')
2222 for (j = 0; j < XVECLEN (x, i); j++)
2223 replace_call_address (XVECEXP (x, i, j), reg, addr);
2229 /* Return the number of memory refs to addresses that vary
2233 count_nonfixed_reads (loop, x)
2234 const struct loop *loop;
2237 register enum rtx_code code;
2239 register const char *fmt;
2245 code = GET_CODE (x);
2259 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2260 + count_nonfixed_reads (loop, XEXP (x, 0)));
2267 fmt = GET_RTX_FORMAT (code);
2268 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2271 value += count_nonfixed_reads (loop, XEXP (x, i));
2275 for (j = 0; j < XVECLEN (x, i); j++)
2276 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2282 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2283 `has_call', `has_volatile', `has_tablejump',
2284 `unknown_address_altered', `unknown_constant_address_altered', and
2285 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2286 list `store_mems' in LOOP. */
2292 register int level = 1;
2294 struct loop_info *loop_info = LOOP_INFO (loop);
2295 rtx start = loop->start;
2296 rtx end = loop->end;
2297 /* The label after END. Jumping here is just like falling off the
2298 end of the loop. We use next_nonnote_insn instead of next_label
2299 as a hedge against the (pathological) case where some actual insn
2300 might end up between the two. */
2301 rtx exit_target = next_nonnote_insn (end);
2303 loop_info->has_indirect_jump = indirect_jump_in_function;
2304 loop_info->has_call = 0;
2305 loop_info->has_volatile = 0;
2306 loop_info->has_tablejump = 0;
2307 loop_info->has_multiple_exit_targets = 0;
2310 loop_info->unknown_address_altered = 0;
2311 loop_info->unknown_constant_address_altered = 0;
2312 loop_info->store_mems = NULL_RTX;
2313 loop_info->first_loop_store_insn = NULL_RTX;
2314 loop_info->mems_idx = 0;
2315 loop_info->num_mem_sets = 0;
2317 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2318 insn = NEXT_INSN (insn))
2320 if (GET_CODE (insn) == NOTE)
2322 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2325 /* Count number of loops contained in this one. */
2328 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2333 else if (GET_CODE (insn) == CALL_INSN)
2335 if (! CONST_CALL_P (insn))
2336 loop_info->unknown_address_altered = 1;
2337 loop_info->has_call = 1;
2339 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2341 rtx label1 = NULL_RTX;
2342 rtx label2 = NULL_RTX;
2344 if (volatile_refs_p (PATTERN (insn)))
2345 loop_info->has_volatile = 1;
2347 if (GET_CODE (insn) == JUMP_INSN
2348 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2349 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2350 loop_info->has_tablejump = 1;
2352 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2353 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2354 loop_info->first_loop_store_insn = insn;
2356 if (! loop_info->has_multiple_exit_targets
2357 && GET_CODE (insn) == JUMP_INSN
2358 && GET_CODE (PATTERN (insn)) == SET
2359 && SET_DEST (PATTERN (insn)) == pc_rtx)
2361 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2363 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2364 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2368 label1 = SET_SRC (PATTERN (insn));
2373 if (label1 && label1 != pc_rtx)
2375 if (GET_CODE (label1) != LABEL_REF)
2377 /* Something tricky. */
2378 loop_info->has_multiple_exit_targets = 1;
2381 else if (XEXP (label1, 0) != exit_target
2382 && LABEL_OUTSIDE_LOOP_P (label1))
2384 /* A jump outside the current loop. */
2385 loop_info->has_multiple_exit_targets = 1;
2396 else if (GET_CODE (insn) == RETURN)
2397 loop_info->has_multiple_exit_targets = 1;
2400 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2401 if (/* An exception thrown by a called function might land us
2403 ! loop_info->has_call
2404 /* We don't want loads for MEMs moved to a location before the
2405 one at which their stack memory becomes allocated. (Note
2406 that this is not a problem for malloc, etc., since those
2407 require actual function calls. */
2408 && ! current_function_calls_alloca
2409 /* There are ways to leave the loop other than falling off the
2411 && ! loop_info->has_multiple_exit_targets)
2412 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2413 insn = NEXT_INSN (insn))
2414 for_each_rtx (&insn, insert_loop_mem, loop_info);
2416 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2417 that loop_invariant_p and load_mems can use true_dependence
2418 to determine what is really clobbered. */
2419 if (loop_info->unknown_address_altered)
2421 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2423 loop_info->store_mems
2424 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2426 if (loop_info->unknown_constant_address_altered)
2428 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2430 RTX_UNCHANGING_P (mem) = 1;
2431 loop_info->store_mems
2432 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2436 /* Scan the function looking for loops. Record the start and end of each loop.
2437 Also mark as invalid loops any loops that contain a setjmp or are branched
2438 to from outside the loop. */
2441 find_and_verify_loops (f, loops)
2443 struct loops *loops;
2448 struct loop *current_loop;
2449 struct loop *next_loop;
2452 num_loops = loops->num;
2454 compute_luids (f, NULL_RTX, 0);
2456 /* If there are jumps to undefined labels,
2457 treat them as jumps out of any/all loops.
2458 This also avoids writing past end of tables when there are no loops. */
2461 /* Find boundaries of loops, mark which loops are contained within
2462 loops, and invalidate loops that have setjmp. */
2465 current_loop = NULL;
2466 for (insn = f; insn; insn = NEXT_INSN (insn))
2468 if (GET_CODE (insn) == NOTE)
2469 switch (NOTE_LINE_NUMBER (insn))
2471 case NOTE_INSN_LOOP_BEG:
2472 next_loop = loops->array + num_loops;
2473 next_loop->num = num_loops;
2475 next_loop->start = insn;
2476 next_loop->outer = current_loop;
2477 current_loop = next_loop;
2480 case NOTE_INSN_SETJMP:
2481 /* In this case, we must invalidate our current loop and any
2483 for (loop = current_loop; loop; loop = loop->outer)
2486 if (loop_dump_stream)
2487 fprintf (loop_dump_stream,
2488 "\nLoop at %d ignored due to setjmp.\n",
2489 INSN_UID (loop->start));
2493 case NOTE_INSN_LOOP_CONT:
2494 current_loop->cont = insn;
2497 case NOTE_INSN_LOOP_VTOP:
2498 current_loop->vtop = insn;
2501 case NOTE_INSN_LOOP_END:
2505 current_loop->end = insn;
2506 current_loop = current_loop->outer;
2513 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2514 enclosing loop, but this doesn't matter. */
2515 uid_loop[INSN_UID (insn)] = current_loop;
2518 /* Any loop containing a label used in an initializer must be invalidated,
2519 because it can be jumped into from anywhere. */
2521 for (label = forced_labels; label; label = XEXP (label, 1))
2523 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2524 loop; loop = loop->outer)
2528 /* Any loop containing a label used for an exception handler must be
2529 invalidated, because it can be jumped into from anywhere. */
2531 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2533 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2534 loop; loop = loop->outer)
2538 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2539 loop that it is not contained within, that loop is marked invalid.
2540 If any INSN or CALL_INSN uses a label's address, then the loop containing
2541 that label is marked invalid, because it could be jumped into from
2544 Also look for blocks of code ending in an unconditional branch that
2545 exits the loop. If such a block is surrounded by a conditional
2546 branch around the block, move the block elsewhere (see below) and
2547 invert the jump to point to the code block. This may eliminate a
2548 label in our loop and will simplify processing by both us and a
2549 possible second cse pass. */
2551 for (insn = f; insn; insn = NEXT_INSN (insn))
2554 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2556 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2558 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2561 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2562 loop; loop = loop->outer)
2567 if (GET_CODE (insn) != JUMP_INSN)
2570 mark_loop_jump (PATTERN (insn), this_loop);
2572 /* See if this is an unconditional branch outside the loop. */
2574 && (GET_CODE (PATTERN (insn)) == RETURN
2575 || (any_uncondjump_p (insn)
2576 && onlyjump_p (insn)
2577 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2579 && get_max_uid () < max_uid_for_loop)
2582 rtx our_next = next_real_insn (insn);
2583 rtx last_insn_to_move = NEXT_INSN (insn);
2584 struct loop *dest_loop;
2585 struct loop *outer_loop = NULL;
2587 /* Go backwards until we reach the start of the loop, a label,
2589 for (p = PREV_INSN (insn);
2590 GET_CODE (p) != CODE_LABEL
2591 && ! (GET_CODE (p) == NOTE
2592 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2593 && GET_CODE (p) != JUMP_INSN;
2597 /* Check for the case where we have a jump to an inner nested
2598 loop, and do not perform the optimization in that case. */
2600 if (JUMP_LABEL (insn))
2602 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2605 for (outer_loop = dest_loop; outer_loop;
2606 outer_loop = outer_loop->outer)
2607 if (outer_loop == this_loop)
2612 /* Make sure that the target of P is within the current loop. */
2614 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2615 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2616 outer_loop = this_loop;
2618 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2619 we have a block of code to try to move.
2621 We look backward and then forward from the target of INSN
2622 to find a BARRIER at the same loop depth as the target.
2623 If we find such a BARRIER, we make a new label for the start
2624 of the block, invert the jump in P and point it to that label,
2625 and move the block of code to the spot we found. */
2628 && GET_CODE (p) == JUMP_INSN
2629 && JUMP_LABEL (p) != 0
2630 /* Just ignore jumps to labels that were never emitted.
2631 These always indicate compilation errors. */
2632 && INSN_UID (JUMP_LABEL (p)) != 0
2633 && any_condjump_p (p) && onlyjump_p (p)
2634 && next_real_insn (JUMP_LABEL (p)) == our_next
2635 /* If it's not safe to move the sequence, then we
2637 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2638 &last_insn_to_move))
2641 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2642 struct loop *target_loop = uid_loop[INSN_UID (target)];
2645 for (loc = target; loc; loc = PREV_INSN (loc))
2646 if (GET_CODE (loc) == BARRIER
2647 /* Don't move things inside a tablejump. */
2648 && ((loc2 = next_nonnote_insn (loc)) == 0
2649 || GET_CODE (loc2) != CODE_LABEL
2650 || (loc2 = next_nonnote_insn (loc2)) == 0
2651 || GET_CODE (loc2) != JUMP_INSN
2652 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2653 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2654 && uid_loop[INSN_UID (loc)] == target_loop)
2658 for (loc = target; loc; loc = NEXT_INSN (loc))
2659 if (GET_CODE (loc) == BARRIER
2660 /* Don't move things inside a tablejump. */
2661 && ((loc2 = next_nonnote_insn (loc)) == 0
2662 || GET_CODE (loc2) != CODE_LABEL
2663 || (loc2 = next_nonnote_insn (loc2)) == 0
2664 || GET_CODE (loc2) != JUMP_INSN
2665 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2666 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2667 && uid_loop[INSN_UID (loc)] == target_loop)
2672 rtx cond_label = JUMP_LABEL (p);
2673 rtx new_label = get_label_after (p);
2675 /* Ensure our label doesn't go away. */
2676 LABEL_NUSES (cond_label)++;
2678 /* Verify that uid_loop is large enough and that
2680 if (invert_jump (p, new_label, 1))
2684 /* If no suitable BARRIER was found, create a suitable
2685 one before TARGET. Since TARGET is a fall through
2686 path, we'll need to insert an jump around our block
2687 and a add a BARRIER before TARGET.
2689 This creates an extra unconditional jump outside
2690 the loop. However, the benefits of removing rarely
2691 executed instructions from inside the loop usually
2692 outweighs the cost of the extra unconditional jump
2693 outside the loop. */
2698 temp = gen_jump (JUMP_LABEL (insn));
2699 temp = emit_jump_insn_before (temp, target);
2700 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2701 LABEL_NUSES (JUMP_LABEL (insn))++;
2702 loc = emit_barrier_before (target);
2705 /* Include the BARRIER after INSN and copy the
2707 new_label = squeeze_notes (new_label,
2709 reorder_insns (new_label, last_insn_to_move, loc);
2711 /* All those insns are now in TARGET_LOOP. */
2713 q != NEXT_INSN (last_insn_to_move);
2715 uid_loop[INSN_UID (q)] = target_loop;
2717 /* The label jumped to by INSN is no longer a loop
2718 exit. Unless INSN does not have a label (e.g.,
2719 it is a RETURN insn), search loop->exit_labels
2720 to find its label_ref, and remove it. Also turn
2721 off LABEL_OUTSIDE_LOOP_P bit. */
2722 if (JUMP_LABEL (insn))
2724 for (q = 0, r = this_loop->exit_labels;
2726 q = r, r = LABEL_NEXTREF (r))
2727 if (XEXP (r, 0) == JUMP_LABEL (insn))
2729 LABEL_OUTSIDE_LOOP_P (r) = 0;
2731 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2733 this_loop->exit_labels = LABEL_NEXTREF (r);
2737 for (loop = this_loop; loop && loop != target_loop;
2741 /* If we didn't find it, then something is
2747 /* P is now a jump outside the loop, so it must be put
2748 in loop->exit_labels, and marked as such.
2749 The easiest way to do this is to just call
2750 mark_loop_jump again for P. */
2751 mark_loop_jump (PATTERN (p), this_loop);
2753 /* If INSN now jumps to the insn after it,
2755 if (JUMP_LABEL (insn) != 0
2756 && (next_real_insn (JUMP_LABEL (insn))
2757 == next_real_insn (insn)))
2761 /* Continue the loop after where the conditional
2762 branch used to jump, since the only branch insn
2763 in the block (if it still remains) is an inter-loop
2764 branch and hence needs no processing. */
2765 insn = NEXT_INSN (cond_label);
2767 if (--LABEL_NUSES (cond_label) == 0)
2768 delete_insn (cond_label);
2770 /* This loop will be continued with NEXT_INSN (insn). */
2771 insn = PREV_INSN (insn);
2778 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2779 loops it is contained in, mark the target loop invalid.
2781 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2784 mark_loop_jump (x, loop)
2788 struct loop *dest_loop;
2789 struct loop *outer_loop;
2792 switch (GET_CODE (x))
2805 /* There could be a label reference in here. */
2806 mark_loop_jump (XEXP (x, 0), loop);
2812 mark_loop_jump (XEXP (x, 0), loop);
2813 mark_loop_jump (XEXP (x, 1), loop);
2817 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2818 mark_loop_jump (XEXP (x, 1), loop);
2823 mark_loop_jump (XEXP (x, 0), loop);
2827 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2829 /* Link together all labels that branch outside the loop. This
2830 is used by final_[bg]iv_value and the loop unrolling code. Also
2831 mark this LABEL_REF so we know that this branch should predict
2834 /* A check to make sure the label is not in an inner nested loop,
2835 since this does not count as a loop exit. */
2838 for (outer_loop = dest_loop; outer_loop;
2839 outer_loop = outer_loop->outer)
2840 if (outer_loop == loop)
2846 if (loop && ! outer_loop)
2848 LABEL_OUTSIDE_LOOP_P (x) = 1;
2849 LABEL_NEXTREF (x) = loop->exit_labels;
2850 loop->exit_labels = x;
2852 for (outer_loop = loop;
2853 outer_loop && outer_loop != dest_loop;
2854 outer_loop = outer_loop->outer)
2855 outer_loop->exit_count++;
2858 /* If this is inside a loop, but not in the current loop or one enclosed
2859 by it, it invalidates at least one loop. */
2864 /* We must invalidate every nested loop containing the target of this
2865 label, except those that also contain the jump insn. */
2867 for (; dest_loop; dest_loop = dest_loop->outer)
2869 /* Stop when we reach a loop that also contains the jump insn. */
2870 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2871 if (dest_loop == outer_loop)
2874 /* If we get here, we know we need to invalidate a loop. */
2875 if (loop_dump_stream && ! dest_loop->invalid)
2876 fprintf (loop_dump_stream,
2877 "\nLoop at %d ignored due to multiple entry points.\n",
2878 INSN_UID (dest_loop->start));
2880 dest_loop->invalid = 1;
2885 /* If this is not setting pc, ignore. */
2886 if (SET_DEST (x) == pc_rtx)
2887 mark_loop_jump (SET_SRC (x), loop);
2891 mark_loop_jump (XEXP (x, 1), loop);
2892 mark_loop_jump (XEXP (x, 2), loop);
2897 for (i = 0; i < XVECLEN (x, 0); i++)
2898 mark_loop_jump (XVECEXP (x, 0, i), loop);
2902 for (i = 0; i < XVECLEN (x, 1); i++)
2903 mark_loop_jump (XVECEXP (x, 1, i), loop);
2907 /* Strictly speaking this is not a jump into the loop, only a possible
2908 jump out of the loop. However, we have no way to link the destination
2909 of this jump onto the list of exit labels. To be safe we mark this
2910 loop and any containing loops as invalid. */
2913 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2915 if (loop_dump_stream && ! outer_loop->invalid)
2916 fprintf (loop_dump_stream,
2917 "\nLoop at %d ignored due to unknown exit jump.\n",
2918 INSN_UID (outer_loop->start));
2919 outer_loop->invalid = 1;
2926 /* Return nonzero if there is a label in the range from
2927 insn INSN to and including the insn whose luid is END
2928 INSN must have an assigned luid (i.e., it must not have
2929 been previously created by loop.c). */
2932 labels_in_range_p (insn, end)
2936 while (insn && INSN_LUID (insn) <= end)
2938 if (GET_CODE (insn) == CODE_LABEL)
2940 insn = NEXT_INSN (insn);
2946 /* Record that a memory reference X is being set. */
2949 note_addr_stored (x, y, data)
2951 rtx y ATTRIBUTE_UNUSED;
2952 void *data ATTRIBUTE_UNUSED;
2954 struct loop_info *loop_info = data;
2956 if (x == 0 || GET_CODE (x) != MEM)
2959 /* Count number of memory writes.
2960 This affects heuristics in strength_reduce. */
2961 loop_info->num_mem_sets++;
2963 /* BLKmode MEM means all memory is clobbered. */
2964 if (GET_MODE (x) == BLKmode)
2966 if (RTX_UNCHANGING_P (x))
2967 loop_info->unknown_constant_address_altered = 1;
2969 loop_info->unknown_address_altered = 1;
2974 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2975 loop_info->store_mems);
2978 /* X is a value modified by an INSN that references a biv inside a loop
2979 exit test (ie, X is somehow related to the value of the biv). If X
2980 is a pseudo that is used more than once, then the biv is (effectively)
2981 used more than once. DATA is a pointer to a loop_regs structure. */
2984 note_set_pseudo_multiple_uses (x, y, data)
2986 rtx y ATTRIBUTE_UNUSED;
2989 struct loop_regs *regs = (struct loop_regs *) data;
2994 while (GET_CODE (x) == STRICT_LOW_PART
2995 || GET_CODE (x) == SIGN_EXTRACT
2996 || GET_CODE (x) == ZERO_EXTRACT
2997 || GET_CODE (x) == SUBREG)
3000 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
3003 /* If we do not have usage information, or if we know the register
3004 is used more than once, note that fact for check_dbra_loop. */
3005 if (REGNO (x) >= max_reg_before_loop
3006 || ! VARRAY_RTX (regs->single_usage, REGNO (x))
3007 || VARRAY_RTX (regs->single_usage, REGNO (x)) == const0_rtx)
3008 regs->multiple_uses = 1;
3011 /* Return nonzero if the rtx X is invariant over the current loop.
3013 The value is 2 if we refer to something only conditionally invariant.
3015 A memory ref is invariant if it is not volatile and does not conflict
3016 with anything stored in `loop_info->store_mems'. */
3019 loop_invariant_p (loop, x)
3020 const struct loop *loop;
3023 struct loop_info *loop_info = LOOP_INFO (loop);
3024 struct loop_regs *regs = LOOP_REGS (loop);
3026 register enum rtx_code code;
3027 register const char *fmt;
3028 int conditional = 0;
3033 code = GET_CODE (x);
3043 /* A LABEL_REF is normally invariant, however, if we are unrolling
3044 loops, and this label is inside the loop, then it isn't invariant.
3045 This is because each unrolled copy of the loop body will have
3046 a copy of this label. If this was invariant, then an insn loading
3047 the address of this label into a register might get moved outside
3048 the loop, and then each loop body would end up using the same label.
3050 We don't know the loop bounds here though, so just fail for all
3052 if (flag_unroll_loops)
3059 case UNSPEC_VOLATILE:
3063 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3064 since the reg might be set by initialization within the loop. */
3066 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3067 || x == arg_pointer_rtx)
3068 && ! current_function_has_nonlocal_goto)
3071 if (LOOP_INFO (loop)->has_call
3072 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3075 if (VARRAY_INT (regs->set_in_loop, REGNO (x)) < 0)
3078 return VARRAY_INT (regs->set_in_loop, REGNO (x)) == 0;
3081 /* Volatile memory references must be rejected. Do this before
3082 checking for read-only items, so that volatile read-only items
3083 will be rejected also. */
3084 if (MEM_VOLATILE_P (x))
3087 /* See if there is any dependence between a store and this load. */
3088 mem_list_entry = loop_info->store_mems;
3089 while (mem_list_entry)
3091 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3095 mem_list_entry = XEXP (mem_list_entry, 1);
3098 /* It's not invalidated by a store in memory
3099 but we must still verify the address is invariant. */
3103 /* Don't mess with insns declared volatile. */
3104 if (MEM_VOLATILE_P (x))
3112 fmt = GET_RTX_FORMAT (code);
3113 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3117 int tem = loop_invariant_p (loop, XEXP (x, i));
3123 else if (fmt[i] == 'E')
3126 for (j = 0; j < XVECLEN (x, i); j++)
3128 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3138 return 1 + conditional;
3141 /* Return nonzero if all the insns in the loop that set REG
3142 are INSN and the immediately following insns,
3143 and if each of those insns sets REG in an invariant way
3144 (not counting uses of REG in them).
3146 The value is 2 if some of these insns are only conditionally invariant.
3148 We assume that INSN itself is the first set of REG
3149 and that its source is invariant. */
3152 consec_sets_invariant_p (loop, reg, n_sets, insn)
3153 const struct loop *loop;
3157 struct loop_regs *regs = LOOP_REGS (loop);
3159 unsigned int regno = REGNO (reg);
3161 /* Number of sets we have to insist on finding after INSN. */
3162 int count = n_sets - 1;
3163 int old = VARRAY_INT (regs->set_in_loop, regno);
3167 /* If N_SETS hit the limit, we can't rely on its value. */
3171 VARRAY_INT (regs->set_in_loop, regno) = 0;
3175 register enum rtx_code code;
3179 code = GET_CODE (p);
3181 /* If library call, skip to end of it. */
3182 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3187 && (set = single_set (p))
3188 && GET_CODE (SET_DEST (set)) == REG
3189 && REGNO (SET_DEST (set)) == regno)
3191 this = loop_invariant_p (loop, SET_SRC (set));
3194 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3196 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3197 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3199 this = (CONSTANT_P (XEXP (temp, 0))
3200 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3201 && loop_invariant_p (loop, XEXP (temp, 0))));
3208 else if (code != NOTE)
3210 VARRAY_INT (regs->set_in_loop, regno) = old;
3215 VARRAY_INT (regs->set_in_loop, regno) = old;
3216 /* If loop_invariant_p ever returned 2, we return 2. */
3217 return 1 + (value & 2);
3221 /* I don't think this condition is sufficient to allow INSN
3222 to be moved, so we no longer test it. */
3224 /* Return 1 if all insns in the basic block of INSN and following INSN
3225 that set REG are invariant according to TABLE. */
3228 all_sets_invariant_p (reg, insn, table)
3232 register rtx p = insn;
3233 register int regno = REGNO (reg);
3237 register enum rtx_code code;
3239 code = GET_CODE (p);
3240 if (code == CODE_LABEL || code == JUMP_INSN)
3242 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3243 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3244 && REGNO (SET_DEST (PATTERN (p))) == regno)
3246 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3253 /* Look at all uses (not sets) of registers in X. For each, if it is
3254 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3255 a different insn, set USAGE[REGNO] to const0_rtx. */
3258 find_single_use_in_loop (insn, x, usage)
3263 enum rtx_code code = GET_CODE (x);
3264 const char *fmt = GET_RTX_FORMAT (code);
3268 VARRAY_RTX (usage, REGNO (x))
3269 = (VARRAY_RTX (usage, REGNO (x)) != 0
3270 && VARRAY_RTX (usage, REGNO (x)) != insn)
3271 ? const0_rtx : insn;
3273 else if (code == SET)
3275 /* Don't count SET_DEST if it is a REG; otherwise count things
3276 in SET_DEST because if a register is partially modified, it won't
3277 show up as a potential movable so we don't care how USAGE is set
3279 if (GET_CODE (SET_DEST (x)) != REG)
3280 find_single_use_in_loop (insn, SET_DEST (x), usage);
3281 find_single_use_in_loop (insn, SET_SRC (x), usage);
3284 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3286 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3287 find_single_use_in_loop (insn, XEXP (x, i), usage);
3288 else if (fmt[i] == 'E')
3289 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3290 find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
3294 /* Count and record any set in X which is contained in INSN. Update
3295 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3298 count_one_set (regs, insn, x, may_not_move, last_set)
3299 struct loop_regs *regs;
3301 varray_type may_not_move;
3304 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3305 /* Don't move a reg that has an explicit clobber.
3306 It's not worth the pain to try to do it correctly. */
3307 VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
3309 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3311 rtx dest = SET_DEST (x);
3312 while (GET_CODE (dest) == SUBREG
3313 || GET_CODE (dest) == ZERO_EXTRACT
3314 || GET_CODE (dest) == SIGN_EXTRACT
3315 || GET_CODE (dest) == STRICT_LOW_PART)
3316 dest = XEXP (dest, 0);
3317 if (GET_CODE (dest) == REG)
3319 register int regno = REGNO (dest);
3320 /* If this is the first setting of this reg
3321 in current basic block, and it was set before,
3322 it must be set in two basic blocks, so it cannot
3323 be moved out of the loop. */
3324 if (VARRAY_INT (regs->set_in_loop, regno) > 0
3325 && last_set[regno] == 0)
3326 VARRAY_CHAR (may_not_move, regno) = 1;
3327 /* If this is not first setting in current basic block,
3328 see if reg was used in between previous one and this.
3329 If so, neither one can be moved. */
3330 if (last_set[regno] != 0
3331 && reg_used_between_p (dest, last_set[regno], insn))
3332 VARRAY_CHAR (may_not_move, regno) = 1;
3333 if (VARRAY_INT (regs->set_in_loop, regno) < 127)
3334 ++VARRAY_INT (regs->set_in_loop, regno);
3335 last_set[regno] = insn;
3340 /* Increment REGS->SET_IN_LOOP at the index of each register
3341 that is modified by an insn between FROM and TO.
3342 If the value of an element of REGS->SET_IN_LOOP becomes 127 or more,
3343 stop incrementing it, to avoid overflow.
3345 Store in SINGLE_USAGE[I] the single insn in which register I is
3346 used, if it is only used once. Otherwise, it is set to 0 (for no
3347 uses) or const0_rtx for more than one use. This parameter may be zero,
3348 in which case this processing is not done.
3350 Store in *COUNT_PTR the number of actual instruction
3351 in the loop. We use this to decide what is worth moving out. */
3353 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3354 In that case, it is the insn that last set reg n. */
3357 count_loop_regs_set (loop, may_not_move, single_usage, count_ptr, nregs)
3358 const struct loop *loop;
3359 varray_type may_not_move;
3360 varray_type single_usage;
3364 struct loop_regs *regs = LOOP_REGS (loop);
3365 register rtx *last_set = (rtx *) xcalloc (nregs, sizeof (rtx));
3367 register int count = 0;
3369 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
3370 insn = NEXT_INSN (insn))
3376 /* Record registers that have exactly one use. */
3377 find_single_use_in_loop (insn, PATTERN (insn), single_usage);
3379 /* Include uses in REG_EQUAL notes. */
3380 if (REG_NOTES (insn))
3381 find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
3383 if (GET_CODE (PATTERN (insn)) == SET
3384 || GET_CODE (PATTERN (insn)) == CLOBBER)
3385 count_one_set (regs, insn, PATTERN (insn), may_not_move, last_set);
3386 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3389 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3390 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
3391 may_not_move, last_set);
3395 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
3396 memset ((char *) last_set, 0, nregs * sizeof (rtx));
3404 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3405 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3406 contained in insn INSN is used by any insn that precedes INSN in
3407 cyclic order starting from the loop entry point.
3409 We don't want to use INSN_LUID here because if we restrict INSN to those
3410 that have a valid INSN_LUID, it means we cannot move an invariant out
3411 from an inner loop past two loops. */
3414 loop_reg_used_before_p (loop, set, insn)
3415 const struct loop *loop;
3418 rtx reg = SET_DEST (set);
3421 /* Scan forward checking for register usage. If we hit INSN, we
3422 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3423 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3425 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3435 /* A "basic induction variable" or biv is a pseudo reg that is set
3436 (within this loop) only by incrementing or decrementing it. */
3437 /* A "general induction variable" or giv is a pseudo reg whose
3438 value is a linear function of a biv. */
3440 /* Bivs are recognized by `basic_induction_var';
3441 Givs by `general_induction_var'. */
3443 /* Communication with routines called via `note_stores'. */
3445 static rtx note_insn;
3447 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3449 static rtx addr_placeholder;
3451 /* ??? Unfinished optimizations, and possible future optimizations,
3452 for the strength reduction code. */
3454 /* ??? The interaction of biv elimination, and recognition of 'constant'
3455 bivs, may cause problems. */
3457 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3458 performance problems.
3460 Perhaps don't eliminate things that can be combined with an addressing
3461 mode. Find all givs that have the same biv, mult_val, and add_val;
3462 then for each giv, check to see if its only use dies in a following
3463 memory address. If so, generate a new memory address and check to see
3464 if it is valid. If it is valid, then store the modified memory address,
3465 otherwise, mark the giv as not done so that it will get its own iv. */
3467 /* ??? Could try to optimize branches when it is known that a biv is always
3470 /* ??? When replace a biv in a compare insn, we should replace with closest
3471 giv so that an optimized branch can still be recognized by the combiner,
3472 e.g. the VAX acb insn. */
3474 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3475 was rerun in loop_optimize whenever a register was added or moved.
3476 Also, some of the optimizations could be a little less conservative. */
3478 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3479 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3482 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3483 loop iteration except for the last one.
3485 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3489 for_each_insn_in_loop (loop, fncall)
3491 loop_insn_callback fncall;
3493 /* This is 1 if current insn is not executed at least once for every loop
3495 int not_every_iteration = 0;
3496 int maybe_multiple = 0;
3497 int past_loop_latch = 0;
3501 /* If loop_scan_start points to the loop exit test, we have to be wary of
3502 subversive use of gotos inside expression statements. */
3503 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3504 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3506 /* Scan through loop to find all possible bivs. */
3508 for (p = next_insn_in_loop (loop, loop->scan_start);
3510 p = next_insn_in_loop (loop, p))
3512 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3514 /* Past CODE_LABEL, we get to insns that may be executed multiple
3515 times. The only way we can be sure that they can't is if every
3516 jump insn between here and the end of the loop either
3517 returns, exits the loop, is a jump to a location that is still
3518 behind the label, or is a jump to the loop start. */
3520 if (GET_CODE (p) == CODE_LABEL)
3528 insn = NEXT_INSN (insn);
3529 if (insn == loop->scan_start)
3531 if (insn == loop->end)
3537 if (insn == loop->scan_start)
3541 if (GET_CODE (insn) == JUMP_INSN
3542 && GET_CODE (PATTERN (insn)) != RETURN
3543 && (!any_condjump_p (insn)
3544 || (JUMP_LABEL (insn) != 0
3545 && JUMP_LABEL (insn) != loop->scan_start
3546 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3554 /* Past a jump, we get to insns for which we can't count
3555 on whether they will be executed during each iteration. */
3556 /* This code appears twice in strength_reduce. There is also similar
3557 code in scan_loop. */
3558 if (GET_CODE (p) == JUMP_INSN
3559 /* If we enter the loop in the middle, and scan around to the
3560 beginning, don't set not_every_iteration for that.
3561 This can be any kind of jump, since we want to know if insns
3562 will be executed if the loop is executed. */
3563 && !(JUMP_LABEL (p) == loop->top
3564 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3565 && any_uncondjump_p (p))
3566 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3570 /* If this is a jump outside the loop, then it also doesn't
3571 matter. Check to see if the target of this branch is on the
3572 loop->exits_labels list. */
3574 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3575 if (XEXP (label, 0) == JUMP_LABEL (p))
3579 not_every_iteration = 1;
3582 else if (GET_CODE (p) == NOTE)
3584 /* At the virtual top of a converted loop, insns are again known to
3585 be executed each iteration: logically, the loop begins here
3586 even though the exit code has been duplicated.
3588 Insns are also again known to be executed each iteration at
3589 the LOOP_CONT note. */
3590 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3591 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3593 not_every_iteration = 0;
3594 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3596 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3600 /* Note if we pass a loop latch. If we do, then we can not clear
3601 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3602 a loop since a jump before the last CODE_LABEL may have started
3603 a new loop iteration.
3605 Note that LOOP_TOP is only set for rotated loops and we need
3606 this check for all loops, so compare against the CODE_LABEL
3607 which immediately follows LOOP_START. */
3608 if (GET_CODE (p) == JUMP_INSN
3609 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3610 past_loop_latch = 1;
3612 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3613 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3614 or not an insn is known to be executed each iteration of the
3615 loop, whether or not any iterations are known to occur.
3617 Therefore, if we have just passed a label and have no more labels
3618 between here and the test insn of the loop, and we have not passed
3619 a jump to the top of the loop, then we know these insns will be
3620 executed each iteration. */
3622 if (not_every_iteration
3624 && GET_CODE (p) == CODE_LABEL
3625 && no_labels_between_p (p, loop->end)
3626 && loop_insn_first_p (p, loop->cont))
3627 not_every_iteration = 0;
3632 loop_bivs_find (loop)
3635 struct loop_regs *regs = LOOP_REGS (loop);
3636 struct loop_ivs *ivs = LOOP_IVS (loop);
3637 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3638 struct iv_class *bl, **backbl;
3639 /* Ratio of extra register life span we can justify
3640 for saving an instruction. More if loop doesn't call subroutines
3641 since in that case saving an insn makes more difference
3642 and more registers are available. */
3643 /* ??? could set this to last value of threshold in move_movables */
3645 ivs->loop_iv_list = 0;
3647 VARRAY_INT_INIT (ivs->reg_iv_type, max_reg_before_loop, "reg_iv_type");
3648 VARRAY_GENERIC_PTR_INIT (ivs->reg_iv_info, max_reg_before_loop,
3650 ivs->reg_biv_class = (struct iv_class **)
3651 xcalloc (max_reg_before_loop, sizeof (struct iv_class *));
3653 for_each_insn_in_loop (loop, check_insn_for_bivs);
3655 /* Scan ivs->loop_iv_list to remove all regs that proved not to be bivs.
3656 Make a sanity check against regs->n_times_set. */
3657 for (backbl = &ivs->loop_iv_list, bl = *backbl; bl; bl = bl->next)
3659 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3660 /* Above happens if register modified by subreg, etc. */
3661 /* Make sure it is not recognized as a basic induction var: */
3662 || VARRAY_INT (regs->n_times_set, bl->regno) != bl->biv_count
3663 /* If never incremented, it is invariant that we decided not to
3664 move. So leave it alone. */
3665 || ! bl->incremented)
3667 if (loop_dump_stream)
3668 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3670 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3671 ? "not induction variable"
3672 : (! bl->incremented ? "never incremented"
3675 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3682 if (loop_dump_stream)
3683 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3689 /* Determine how BIVS are initialised by looking through pre-header
3690 extended basic block. */
3692 loop_bivs_init_find (loop)
3695 struct loop_info *loop_info = LOOP_INFO (loop);
3696 struct loop_ivs *ivs = LOOP_IVS (loop);
3697 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3698 struct iv_class *bl;
3701 /* Find initial value for each biv by searching backwards from loop_start,
3702 halting at first label. Also record any test condition. */
3705 for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3709 if (GET_CODE (p) == CALL_INSN)
3713 note_stores (PATTERN (p), record_initial, ivs);
3715 /* Record any test of a biv that branches around the loop if no store
3716 between it and the start of loop. We only care about tests with
3717 constants and registers and only certain of those. */
3718 if (GET_CODE (p) == JUMP_INSN
3719 && JUMP_LABEL (p) != 0
3720 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3721 && (test = get_condition_for_loop (loop, p)) != 0
3722 && GET_CODE (XEXP (test, 0)) == REG
3723 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3724 && (bl = ivs->reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3725 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3726 && bl->init_insn == 0)
3728 /* If an NE test, we have an initial value! */
3729 if (GET_CODE (test) == NE)
3732 bl->init_set = gen_rtx_SET (VOIDmode,
3733 XEXP (test, 0), XEXP (test, 1));
3736 bl->initial_test = test;
3742 /* Look at the each biv and see if we can say anything better about its
3743 initial value from any initializing insns set up above. (This is done
3744 in two passes to avoid missing SETs in a PARALLEL.) */
3746 loop_bivs_check (loop)
3749 struct loop_ivs *ivs = LOOP_IVS (loop);
3750 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3751 struct iv_class *bl;
3752 struct iv_class **backbl;
3754 for (backbl = &ivs->loop_iv_list; (bl = *backbl); backbl = &bl->next)
3759 if (! bl->init_insn)
3762 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3763 is a constant, use the value of that. */
3764 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3765 && CONSTANT_P (XEXP (note, 0)))
3766 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3767 && CONSTANT_P (XEXP (note, 0))))
3768 src = XEXP (note, 0);
3770 src = SET_SRC (bl->init_set);
3772 if (loop_dump_stream)
3773 fprintf (loop_dump_stream,
3774 "Biv %d initialized at insn %d: initial value ",
3775 bl->regno, INSN_UID (bl->init_insn));
3777 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3778 || GET_MODE (src) == VOIDmode)
3779 && valid_initial_value_p (loop, src, bl->init_insn))
3781 bl->initial_value = src;
3783 if (loop_dump_stream)
3785 if (GET_CODE (src) == CONST_INT)
3787 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
3789 fputc ('\n', loop_dump_stream);
3793 print_rtl (loop_dump_stream, src);
3794 fprintf (loop_dump_stream, "\n");
3798 /* If we can't make it a giv,
3799 let biv keep initial value of "itself". */
3800 else if (loop_dump_stream)
3801 fprintf (loop_dump_stream, "is complex\n");
3806 /* Search the loop for general induction variables. */
3809 loop_givs_find (loop)
3812 for_each_insn_in_loop (loop, check_insn_for_givs);
3816 /* For each giv for which we still don't know whether or not it is
3817 replaceable, check to see if it is replaceable because its final value
3818 can be calculated. */
3821 loop_givs_check (loop)
3824 struct loop_ivs *ivs = LOOP_IVS (loop);
3825 struct iv_class *bl;
3827 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3829 struct induction *v;
3831 for (v = bl->giv; v; v = v->next_iv)
3832 if (! v->replaceable && ! v->not_replaceable)
3833 check_final_value (loop, v);
3839 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3841 struct iv_class *bl;
3845 /* Test whether it will be possible to eliminate this biv
3846 provided all givs are reduced. This is possible if either
3847 the reg is not used outside the loop, or we can compute
3848 what its final value will be.
3850 For architectures with a decrement_and_branch_until_zero insn,
3851 don't do this if we put a REG_NONNEG note on the endtest for
3854 /* Compare against bl->init_insn rather than loop_start.
3855 We aren't concerned with any uses of the biv between
3856 init_insn and loop_start since these won't be affected
3857 by the value of the biv elsewhere in the function, so
3858 long as init_insn doesn't use the biv itself.
3859 March 14, 1989 -- self@bayes.arc.nasa.gov */
3861 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3863 && INSN_UID (bl->init_insn) < max_uid_for_loop
3864 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3865 #ifdef HAVE_decrement_and_branch_until_zero
3868 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3869 || ((final_value = final_biv_value (loop, bl))
3870 #ifdef HAVE_decrement_and_branch_until_zero
3874 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3880 /* Perform strength reduction and induction variable elimination.
3882 Pseudo registers created during this function will be beyond the
3883 last valid index in several tables including regs->n_times_set and
3884 regno_last_uid. This does not cause a problem here, because the
3885 added registers cannot be givs outside of their loop, and hence
3886 will never be reconsidered. But scan_loop must check regnos to
3887 make sure they are in bounds. */
3890 strength_reduce (loop, insn_count, flags)
3895 struct loop_info *loop_info = LOOP_INFO (loop);
3896 struct loop_regs *regs = LOOP_REGS (loop);
3897 struct loop_ivs *ivs = LOOP_IVS (loop);
3899 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3900 struct iv_class *bl, **backbl;
3901 /* Ratio of extra register life span we can justify
3902 for saving an instruction. More if loop doesn't call subroutines
3903 since in that case saving an insn makes more difference
3904 and more registers are available. */
3905 /* ??? could set this to last value of threshold in move_movables */
3906 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3907 /* Map of pseudo-register replacements. */
3908 rtx *reg_map = NULL;
3912 rtx end_insert_before;
3913 int unrolled_insn_copies = 0;
3914 rtx loop_start = loop->start;
3915 rtx loop_end = loop->end;
3916 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
3918 addr_placeholder = gen_reg_rtx (Pmode);
3920 /* Save insn immediately after the loop_end. Insns inserted after loop_end
3921 must be put before this insn, so that they will appear in the right
3922 order (i.e. loop order).
3924 If loop_end is the end of the current function, then emit a
3925 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
3927 if (NEXT_INSN (loop_end) != 0)
3928 end_insert_before = NEXT_INSN (loop_end);
3930 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
3933 /* Find all BIVs in loop. */
3934 loop_bivs_find (loop);
3936 /* Exit if there are no bivs. */
3937 if (! ivs->loop_iv_list)
3939 /* Can still unroll the loop anyways, but indicate that there is no
3940 strength reduction info available. */
3941 if (flags & LOOP_UNROLL)
3942 unroll_loop (loop, insn_count, end_insert_before, 0);
3947 /* Determine how BIVS are initialised by looking through pre-header
3948 extended basic block. */
3949 loop_bivs_init_find (loop);
3951 /* Look at the each biv and see if we can say anything better about its
3952 initial value from any initializing insns set up above. */
3953 loop_bivs_check (loop);
3955 /* Search the loop for general induction variables. */
3956 loop_givs_find (loop);
3958 /* Try to calculate and save the number of loop iterations. This is
3959 set to zero if the actual number can not be calculated. This must
3960 be called after all giv's have been identified, since otherwise it may
3961 fail if the iteration variable is a giv. */
3962 loop_iterations (loop);
3964 /* Now for each giv for which we still don't know whether or not it is
3965 replaceable, check to see if it is replaceable because its final value
3966 can be calculated. This must be done after loop_iterations is called,
3967 so that final_giv_value will work correctly. */
3968 loop_givs_check (loop);
3970 /* Try to prove that the loop counter variable (if any) is always
3971 nonnegative; if so, record that fact with a REG_NONNEG note
3972 so that "decrement and branch until zero" insn can be used. */
3973 check_dbra_loop (loop, insn_count);
3975 /* Create reg_map to hold substitutions for replaceable giv regs.
3976 Some givs might have been made from biv increments, so look at
3977 ivs->reg_iv_type for a suitable size. */
3978 reg_map_size = ivs->reg_iv_type->num_elements;
3979 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
3981 /* Examine each iv class for feasibility of strength reduction/induction
3982 variable elimination. */
3984 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3986 struct induction *v;
3989 rtx final_value = 0;
3991 /* Test whether it will be possible to eliminate this biv
3992 provided all givs are reduced. */
3993 if (!(bl->eliminable = loop_biv_eliminable_p (loop, bl,
3994 threshold, insn_count)))
3996 if (loop_dump_stream)
3998 fprintf (loop_dump_stream,
3999 "Cannot eliminate biv %d.\n",
4001 fprintf (loop_dump_stream,
4002 "First use: insn %d, last use: insn %d.\n",
4003 REGNO_FIRST_UID (bl->regno),
4004 REGNO_LAST_UID (bl->regno));
4008 /* Check each extension dependent giv in this class to see if its
4009 root biv is safe from wrapping in the interior mode. */
4010 check_ext_dependant_givs (bl, loop_info);
4012 /* Combine all giv's for this iv_class. */
4013 combine_givs (regs, bl);
4015 /* This will be true at the end, if all givs which depend on this
4016 biv have been strength reduced.
4017 We can't (currently) eliminate the biv unless this is so. */
4020 /* Check each giv in this class to see if we will benefit by reducing
4021 it. Skip giv's combined with others. */
4022 for (v = bl->giv; v; v = v->next_iv)
4024 struct induction *tv;
4027 if (v->ignore || v->same)
4030 benefit = v->benefit;
4031 PUT_MODE (test_reg, v->mode);
4032 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4033 test_reg, test_reg);
4035 /* Reduce benefit if not replaceable, since we will insert
4036 a move-insn to replace the insn that calculates this giv.
4037 Don't do this unless the giv is a user variable, since it
4038 will often be marked non-replaceable because of the duplication
4039 of the exit code outside the loop. In such a case, the copies
4040 we insert are dead and will be deleted. So they don't have
4041 a cost. Similar situations exist. */
4042 /* ??? The new final_[bg]iv_value code does a much better job
4043 of finding replaceable giv's, and hence this code may no longer
4045 if (! v->replaceable && ! bl->eliminable
4046 && REG_USERVAR_P (v->dest_reg))
4047 benefit -= copy_cost;
4049 /* Decrease the benefit to count the add-insns that we will
4050 insert to increment the reduced reg for the giv.
4051 ??? This can overestimate the run-time cost of the additional
4052 insns, e.g. if there are multiple basic blocks that increment
4053 the biv, but only one of these blocks is executed during each
4054 iteration. There is no good way to detect cases like this with
4055 the current structure of the loop optimizer.
4056 This code is more accurate for determining code size than
4057 run-time benefits. */
4058 benefit -= add_cost * bl->biv_count;
4060 /* Decide whether to strength-reduce this giv or to leave the code
4061 unchanged (recompute it from the biv each time it is used).
4062 This decision can be made independently for each giv. */
4065 /* Attempt to guess whether autoincrement will handle some of the
4066 new add insns; if so, increase BENEFIT (undo the subtraction of
4067 add_cost that was done above). */
4068 if (v->giv_type == DEST_ADDR
4069 /* Increasing the benefit is risky, since this is only a guess.
4070 Avoid increasing register pressure in cases where there would
4071 be no other benefit from reducing this giv. */
4073 && GET_CODE (v->mult_val) == CONST_INT)
4075 if (HAVE_POST_INCREMENT
4076 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4077 benefit += add_cost * bl->biv_count;
4078 else if (HAVE_PRE_INCREMENT
4079 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4080 benefit += add_cost * bl->biv_count;
4081 else if (HAVE_POST_DECREMENT
4082 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4083 benefit += add_cost * bl->biv_count;
4084 else if (HAVE_PRE_DECREMENT
4085 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4086 benefit += add_cost * bl->biv_count;
4090 /* If an insn is not to be strength reduced, then set its ignore
4091 flag, and clear all_reduced. */
4093 /* A giv that depends on a reversed biv must be reduced if it is
4094 used after the loop exit, otherwise, it would have the wrong
4095 value after the loop exit. To make it simple, just reduce all
4096 of such giv's whether or not we know they are used after the loop
4099 if (! flag_reduce_all_givs
4100 && v->lifetime * threshold * benefit < insn_count
4103 if (loop_dump_stream)
4104 fprintf (loop_dump_stream,
4105 "giv of insn %d not worth while, %d vs %d.\n",
4107 v->lifetime * threshold * benefit, insn_count);
4113 /* Check that we can increment the reduced giv without a
4114 multiply insn. If not, reject it. */
4116 for (tv = bl->biv; tv; tv = tv->next_iv)
4117 if (tv->mult_val == const1_rtx
4118 && ! product_cheap_p (tv->add_val, v->mult_val))
4120 if (loop_dump_stream)
4121 fprintf (loop_dump_stream,
4122 "giv of insn %d: would need a multiply.\n",
4123 INSN_UID (v->insn));
4131 /* Check for givs whose first use is their definition and whose
4132 last use is the definition of another giv. If so, it is likely
4133 dead and should not be used to derive another giv nor to
4135 for (v = bl->giv; v; v = v->next_iv)
4138 || (v->same && v->same->ignore))
4141 if (v->giv_type == DEST_REG
4142 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4144 struct induction *v1;
4146 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4147 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4152 /* Reduce each giv that we decided to reduce. */
4154 for (v = bl->giv; v; v = v->next_iv)
4156 struct induction *tv;
4157 if (! v->ignore && v->same == 0)
4159 int auto_inc_opt = 0;
4161 /* If the code for derived givs immediately below has already
4162 allocated a new_reg, we must keep it. */
4164 v->new_reg = gen_reg_rtx (v->mode);
4167 /* If the target has auto-increment addressing modes, and
4168 this is an address giv, then try to put the increment
4169 immediately after its use, so that flow can create an
4170 auto-increment addressing mode. */
4171 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
4172 && bl->biv->always_executed && ! bl->biv->maybe_multiple
4173 /* We don't handle reversed biv's because bl->biv->insn
4174 does not have a valid INSN_LUID. */
4176 && v->always_executed && ! v->maybe_multiple
4177 && INSN_UID (v->insn) < max_uid_for_loop)
4179 /* If other giv's have been combined with this one, then
4180 this will work only if all uses of the other giv's occur
4181 before this giv's insn. This is difficult to check.
4183 We simplify this by looking for the common case where
4184 there is one DEST_REG giv, and this giv's insn is the
4185 last use of the dest_reg of that DEST_REG giv. If the
4186 increment occurs after the address giv, then we can
4187 perform the optimization. (Otherwise, the increment
4188 would have to go before other_giv, and we would not be
4189 able to combine it with the address giv to get an
4190 auto-inc address.) */
4191 if (v->combined_with)
4193 struct induction *other_giv = 0;
4195 for (tv = bl->giv; tv; tv = tv->next_iv)
4203 if (! tv && other_giv
4204 && REGNO (other_giv->dest_reg) < max_reg_before_loop
4205 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
4206 == INSN_UID (v->insn))
4207 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
4210 /* Check for case where increment is before the address
4211 giv. Do this test in "loop order". */
4212 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
4213 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
4214 || (INSN_LUID (bl->biv->insn)
4215 > INSN_LUID (loop->scan_start))))
4216 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
4217 && (INSN_LUID (loop->scan_start)
4218 < INSN_LUID (bl->biv->insn))))
4227 /* We can't put an insn immediately after one setting
4228 cc0, or immediately before one using cc0. */
4229 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
4230 || (auto_inc_opt == -1
4231 && (prev = prev_nonnote_insn (v->insn)) != 0
4233 && sets_cc0_p (PATTERN (prev))))
4239 v->auto_inc_opt = 1;
4243 /* For each place where the biv is incremented, add an insn
4244 to increment the new, reduced reg for the giv. */
4245 for (tv = bl->biv; tv; tv = tv->next_iv)
4250 insert_before = tv->insn;
4251 else if (auto_inc_opt == 1)
4252 insert_before = NEXT_INSN (v->insn);
4254 insert_before = v->insn;
4256 if (tv->mult_val == const1_rtx)
4257 emit_iv_add_mult (tv->add_val, v->mult_val,
4258 v->new_reg, v->new_reg, insert_before);
4259 else /* tv->mult_val == const0_rtx */
4260 /* A multiply is acceptable here
4261 since this is presumed to be seldom executed. */
4262 emit_iv_add_mult (tv->add_val, v->mult_val,
4263 v->add_val, v->new_reg, insert_before);
4266 /* Add code at loop start to initialize giv's reduced reg. */
4268 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4269 v->mult_val, v->add_val, v->new_reg,
4274 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4277 For each giv register that can be reduced now: if replaceable,
4278 substitute reduced reg wherever the old giv occurs;
4279 else add new move insn "giv_reg = reduced_reg". */
4281 for (v = bl->giv; v; v = v->next_iv)
4283 if (v->same && v->same->ignore)
4289 /* Update expression if this was combined, in case other giv was
4292 v->new_reg = replace_rtx (v->new_reg,
4293 v->same->dest_reg, v->same->new_reg);
4295 /* See if this register is known to be a pointer to something. If
4296 so, see if we can find the alignment. First see if there is a
4297 destination register that is a pointer. If so, this shares the
4298 alignment too. Next see if we can deduce anything from the
4299 computational information. If not, and this is a DEST_ADDR
4300 giv, at least we know that it's a pointer, though we don't know
4302 if (GET_CODE (v->new_reg) == REG
4303 && v->giv_type == DEST_REG
4304 && REG_POINTER (v->dest_reg))
4305 mark_reg_pointer (v->new_reg,
4306 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
4307 else if (GET_CODE (v->new_reg) == REG
4308 && REG_POINTER (v->src_reg))
4310 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4313 || GET_CODE (v->add_val) != CONST_INT
4314 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4317 mark_reg_pointer (v->new_reg, align);
4319 else if (GET_CODE (v->new_reg) == REG
4320 && GET_CODE (v->add_val) == REG
4321 && REG_POINTER (v->add_val))
4323 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4325 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4326 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4329 mark_reg_pointer (v->new_reg, align);
4331 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4332 mark_reg_pointer (v->new_reg, 0);
4334 if (v->giv_type == DEST_ADDR)
4335 /* Store reduced reg as the address in the memref where we found
4337 validate_change (v->insn, v->location, v->new_reg, 0);
4338 else if (v->replaceable)
4340 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4343 /* I can no longer duplicate the original problem. Perhaps
4344 this is unnecessary now? */
4346 /* Replaceable; it isn't strictly necessary to delete the old
4347 insn and emit a new one, because v->dest_reg is now dead.
4349 However, especially when unrolling loops, the special
4350 handling for (set REG0 REG1) in the second cse pass may
4351 make v->dest_reg live again. To avoid this problem, emit
4352 an insn to set the original giv reg from the reduced giv.
4353 We can not delete the original insn, since it may be part
4354 of a LIBCALL, and the code in flow that eliminates dead
4355 libcalls will fail if it is deleted. */
4356 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4362 /* Not replaceable; emit an insn to set the original giv reg from
4363 the reduced giv, same as above. */
4364 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4368 /* When a loop is reversed, givs which depend on the reversed
4369 biv, and which are live outside the loop, must be set to their
4370 correct final value. This insn is only needed if the giv is
4371 not replaceable. The correct final value is the same as the
4372 value that the giv starts the reversed loop with. */
4373 if (bl->reversed && ! v->replaceable)
4374 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4375 v->mult_val, v->add_val, v->dest_reg,
4377 else if (v->final_value)
4381 /* If the loop has multiple exits, emit the insn before the
4382 loop to ensure that it will always be executed no matter
4383 how the loop exits. Otherwise, emit the insn after the loop,
4384 since this is slightly more efficient. */
4385 if (loop->exit_count)
4386 insert_before = loop_start;
4388 insert_before = end_insert_before;
4389 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4393 /* If the insn to set the final value of the giv was emitted
4394 before the loop, then we must delete the insn inside the loop
4395 that sets it. If this is a LIBCALL, then we must delete
4396 every insn in the libcall. Note, however, that
4397 final_giv_value will only succeed when there are multiple
4398 exits if the giv is dead at each exit, hence it does not
4399 matter that the original insn remains because it is dead
4401 /* Delete the insn inside the loop that sets the giv since
4402 the giv is now set before (or after) the loop. */
4403 delete_insn (v->insn);
4407 if (loop_dump_stream)
4409 fprintf (loop_dump_stream, "giv at %d reduced to ",
4410 INSN_UID (v->insn));
4411 print_rtl (loop_dump_stream, v->new_reg);
4412 fprintf (loop_dump_stream, "\n");
4416 /* All the givs based on the biv bl have been reduced if they
4419 /* For each giv not marked as maybe dead that has been combined with a
4420 second giv, clear any "maybe dead" mark on that second giv.
4421 v->new_reg will either be or refer to the register of the giv it
4424 Doing this clearing avoids problems in biv elimination where a
4425 giv's new_reg is a complex value that can't be put in the insn but
4426 the giv combined with (with a reg as new_reg) is marked maybe_dead.
4427 Since the register will be used in either case, we'd prefer it be
4428 used from the simpler giv. */
4430 for (v = bl->giv; v; v = v->next_iv)
4431 if (! v->maybe_dead && v->same)
4432 v->same->maybe_dead = 0;
4434 /* Try to eliminate the biv, if it is a candidate.
4435 This won't work if ! all_reduced,
4436 since the givs we planned to use might not have been reduced.
4438 We have to be careful that we didn't initially think we could eliminate
4439 this biv because of a giv that we now think may be dead and shouldn't
4440 be used as a biv replacement.
4442 Also, there is the possibility that we may have a giv that looks
4443 like it can be used to eliminate a biv, but the resulting insn
4444 isn't valid. This can happen, for example, on the 88k, where a
4445 JUMP_INSN can compare a register only with zero. Attempts to
4446 replace it with a compare with a constant will fail.
4448 Note that in cases where this call fails, we may have replaced some
4449 of the occurrences of the biv with a giv, but no harm was done in
4450 doing so in the rare cases where it can occur. */
4452 if (all_reduced == 1 && bl->eliminable
4453 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4455 /* ?? If we created a new test to bypass the loop entirely,
4456 or otherwise drop straight in, based on this test, then
4457 we might want to rewrite it also. This way some later
4458 pass has more hope of removing the initialization of this
4461 /* If final_value != 0, then the biv may be used after loop end
4462 and we must emit an insn to set it just in case.
4464 Reversed bivs already have an insn after the loop setting their
4465 value, so we don't need another one. We can't calculate the
4466 proper final value for such a biv here anyways. */
4467 if (final_value != 0 && ! bl->reversed)
4471 /* If the loop has multiple exits, emit the insn before the
4472 loop to ensure that it will always be executed no matter
4473 how the loop exits. Otherwise, emit the insn after the
4474 loop, since this is slightly more efficient. */
4475 if (loop->exit_count)
4476 insert_before = loop_start;
4478 insert_before = end_insert_before;
4480 emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
4485 /* Delete all of the instructions inside the loop which set
4486 the biv, as they are all dead. If is safe to delete them,
4487 because an insn setting a biv will never be part of a libcall. */
4488 /* However, deleting them will invalidate the regno_last_uid info,
4489 so keeping them around is more convenient. Final_biv_value
4490 will only succeed when there are multiple exits if the biv
4491 is dead at each exit, hence it does not matter that the original
4492 insn remains, because it is dead anyways. */
4493 for (v = bl->biv; v; v = v->next_iv)
4494 delete_insn (v->insn);
4497 if (loop_dump_stream)
4498 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4503 /* Go through all the instructions in the loop, making all the
4504 register substitutions scheduled in REG_MAP. */
4506 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
4507 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4508 || GET_CODE (p) == CALL_INSN)
4510 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4511 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4515 if (loop_info->n_iterations > 0)
4517 /* When we completely unroll a loop we will likely not need the increment
4518 of the loop BIV and we will not need the conditional branch at the
4520 unrolled_insn_copies = insn_count - 2;
4523 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4524 need the comparison before the conditional branch at the end of the
4526 unrolled_insn_copies -= 1;
4529 /* We'll need one copy for each loop iteration. */
4530 unrolled_insn_copies *= loop_info->n_iterations;
4532 /* A little slop to account for the ability to remove initialization
4533 code, better CSE, and other secondary benefits of completely
4534 unrolling some loops. */
4535 unrolled_insn_copies -= 1;
4537 /* Clamp the value. */
4538 if (unrolled_insn_copies < 0)
4539 unrolled_insn_copies = 0;
4542 /* Unroll loops from within strength reduction so that we can use the
4543 induction variable information that strength_reduce has already
4544 collected. Always unroll loops that would be as small or smaller
4545 unrolled than when rolled. */
4546 if ((flags & LOOP_UNROLL)
4547 || (loop_info->n_iterations > 0
4548 && unrolled_insn_copies <= insn_count))
4549 unroll_loop (loop, insn_count, end_insert_before, 1);
4551 #ifdef HAVE_doloop_end
4552 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4553 doloop_optimize (loop);
4554 #endif /* HAVE_doloop_end */
4556 if (loop_dump_stream)
4557 fprintf (loop_dump_stream, "\n");
4560 VARRAY_FREE (ivs->reg_iv_type);
4561 VARRAY_FREE (ivs->reg_iv_info);
4562 free (ivs->reg_biv_class);
4564 struct iv_class *iv = ivs->loop_iv_list;
4567 struct iv_class *next = iv->next;
4568 struct induction *induction;
4569 struct induction *next_induction;
4571 for (induction = iv->biv; induction; induction = next_induction)
4573 next_induction = induction->next_iv;
4576 for (induction = iv->giv; induction; induction = next_induction)
4578 next_induction = induction->next_iv;
4590 /*Record all basic induction variables calculated in the insn. */
4592 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4595 int not_every_iteration;
4598 struct loop_ivs *ivs = LOOP_IVS (loop);
4605 if (GET_CODE (p) == INSN
4606 && (set = single_set (p))
4607 && GET_CODE (SET_DEST (set)) == REG)
4609 dest_reg = SET_DEST (set);
4610 if (REGNO (dest_reg) < max_reg_before_loop
4611 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4612 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4614 if (basic_induction_var (loop, SET_SRC (set),
4615 GET_MODE (SET_SRC (set)),
4616 dest_reg, p, &inc_val, &mult_val,
4619 /* It is a possible basic induction variable.
4620 Create and initialize an induction structure for it. */
4623 = (struct induction *) xmalloc (sizeof (struct induction));
4625 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4626 not_every_iteration, maybe_multiple);
4627 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4629 else if (REGNO (dest_reg) < max_reg_before_loop)
4630 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4636 /* Record all givs calculated in the insn.
4637 A register is a giv if: it is only set once, it is a function of a
4638 biv and a constant (or invariant), and it is not a biv. */
4640 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4643 int not_every_iteration;
4646 struct loop_regs *regs = LOOP_REGS (loop);
4649 /* Look for a general induction variable in a register. */
4650 if (GET_CODE (p) == INSN
4651 && (set = single_set (p))
4652 && GET_CODE (SET_DEST (set)) == REG
4653 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
4662 rtx last_consec_insn;
4664 dest_reg = SET_DEST (set);
4665 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4668 if (/* SET_SRC is a giv. */
4669 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4670 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4671 /* Equivalent expression is a giv. */
4672 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4673 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4674 &add_val, &mult_val, &ext_val, 0,
4675 &benefit, VOIDmode)))
4676 /* Don't try to handle any regs made by loop optimization.
4677 We have nothing on them in regno_first_uid, etc. */
4678 && REGNO (dest_reg) < max_reg_before_loop
4679 /* Don't recognize a BASIC_INDUCT_VAR here. */
4680 && dest_reg != src_reg
4681 /* This must be the only place where the register is set. */
4682 && (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) == 1
4683 /* or all sets must be consecutive and make a giv. */
4684 || (benefit = consec_sets_giv (loop, benefit, p,
4686 &add_val, &mult_val, &ext_val,
4687 &last_consec_insn))))
4690 = (struct induction *) xmalloc (sizeof (struct induction));
4692 /* If this is a library call, increase benefit. */
4693 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4694 benefit += libcall_benefit (p);
4696 /* Skip the consecutive insns, if there are any. */
4697 if (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) != 1)
4698 p = last_consec_insn;
4700 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4701 ext_val, benefit, DEST_REG, not_every_iteration,
4702 maybe_multiple, NULL_PTR);
4707 #ifndef DONT_REDUCE_ADDR
4708 /* Look for givs which are memory addresses. */
4709 /* This resulted in worse code on a VAX 8600. I wonder if it
4711 if (GET_CODE (p) == INSN)
4712 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4716 /* Update the status of whether giv can derive other givs. This can
4717 change when we pass a label or an insn that updates a biv. */
4718 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4719 || GET_CODE (p) == CODE_LABEL)
4720 update_giv_derive (loop, p);
4724 /* Return 1 if X is a valid source for an initial value (or as value being
4725 compared against in an initial test).
4727 X must be either a register or constant and must not be clobbered between
4728 the current insn and the start of the loop.
4730 INSN is the insn containing X. */
4733 valid_initial_value_p (x, insn, call_seen, loop_start)
4742 /* Only consider pseudos we know about initialized in insns whose luids
4744 if (GET_CODE (x) != REG
4745 || REGNO (x) >= max_reg_before_loop)
4748 /* Don't use call-clobbered registers across a call which clobbers it. On
4749 some machines, don't use any hard registers at all. */
4750 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4751 && (SMALL_REGISTER_CLASSES
4752 || (call_used_regs[REGNO (x)] && call_seen)))
4755 /* Don't use registers that have been clobbered before the start of the
4757 if (reg_set_between_p (x, insn, loop_start))
4763 /* Scan X for memory refs and check each memory address
4764 as a possible giv. INSN is the insn whose pattern X comes from.
4765 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4766 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4767 more thanonce in each loop iteration. */
4770 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4771 const struct loop *loop;
4774 int not_every_iteration, maybe_multiple;
4777 register enum rtx_code code;
4778 register const char *fmt;
4783 code = GET_CODE (x);
4808 /* This code used to disable creating GIVs with mult_val == 1 and
4809 add_val == 0. However, this leads to lost optimizations when
4810 it comes time to combine a set of related DEST_ADDR GIVs, since
4811 this one would not be seen. */
4813 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4814 &mult_val, &ext_val, 1, &benefit,
4817 /* Found one; record it. */
4819 = (struct induction *) xmalloc (sizeof (struct induction));
4821 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4822 add_val, ext_val, benefit, DEST_ADDR,
4823 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4825 v->mem_mode = GET_MODE (x);
4834 /* Recursively scan the subexpressions for other mem refs. */
4836 fmt = GET_RTX_FORMAT (code);
4837 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4839 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4841 else if (fmt[i] == 'E')
4842 for (j = 0; j < XVECLEN (x, i); j++)
4843 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4847 /* Fill in the data about one biv update.
4848 V is the `struct induction' in which we record the biv. (It is
4849 allocated by the caller, with alloca.)
4850 INSN is the insn that sets it.
4851 DEST_REG is the biv's reg.
4853 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4854 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4855 being set to INC_VAL.
4857 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4858 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4859 can be executed more than once per iteration. If MAYBE_MULTIPLE
4860 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4861 executed exactly once per iteration. */
4864 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4865 not_every_iteration, maybe_multiple)
4867 struct induction *v;
4873 int not_every_iteration;
4876 struct loop_ivs *ivs = LOOP_IVS (loop);
4877 struct iv_class *bl;
4880 v->src_reg = dest_reg;
4881 v->dest_reg = dest_reg;
4882 v->mult_val = mult_val;
4883 v->add_val = inc_val;
4884 v->ext_dependant = NULL_RTX;
4885 v->location = location;
4886 v->mode = GET_MODE (dest_reg);
4887 v->always_computable = ! not_every_iteration;
4888 v->always_executed = ! not_every_iteration;
4889 v->maybe_multiple = maybe_multiple;
4891 /* Add this to the reg's iv_class, creating a class
4892 if this is the first incrementation of the reg. */
4894 bl = ivs->reg_biv_class[REGNO (dest_reg)];
4897 /* Create and initialize new iv_class. */
4899 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4901 bl->regno = REGNO (dest_reg);
4907 /* Set initial value to the reg itself. */
4908 bl->initial_value = dest_reg;
4909 /* We haven't seen the initializing insn yet */
4912 bl->initial_test = 0;
4913 bl->incremented = 0;
4917 bl->total_benefit = 0;
4919 /* Add this class to ivs->loop_iv_list. */
4920 bl->next = ivs->loop_iv_list;
4921 ivs->loop_iv_list = bl;
4923 /* Put it in the array of biv register classes. */
4924 ivs->reg_biv_class[REGNO (dest_reg)] = bl;
4927 /* Update IV_CLASS entry for this biv. */
4928 v->next_iv = bl->biv;
4931 if (mult_val == const1_rtx)
4932 bl->incremented = 1;
4934 if (loop_dump_stream)
4936 fprintf (loop_dump_stream,
4937 "Insn %d: possible biv, reg %d,",
4938 INSN_UID (insn), REGNO (dest_reg));
4939 if (GET_CODE (inc_val) == CONST_INT)
4941 fprintf (loop_dump_stream, " const =");
4942 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4943 fputc ('\n', loop_dump_stream);
4947 fprintf (loop_dump_stream, " const = ");
4948 print_rtl (loop_dump_stream, inc_val);
4949 fprintf (loop_dump_stream, "\n");
4954 /* Fill in the data about one giv.
4955 V is the `struct induction' in which we record the giv. (It is
4956 allocated by the caller, with alloca.)
4957 INSN is the insn that sets it.
4958 BENEFIT estimates the savings from deleting this insn.
4959 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4960 into a register or is used as a memory address.
4962 SRC_REG is the biv reg which the giv is computed from.
4963 DEST_REG is the giv's reg (if the giv is stored in a reg).
4964 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4965 LOCATION points to the place where this giv's value appears in INSN. */
4968 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4969 benefit, type, not_every_iteration, maybe_multiple, location)
4970 const struct loop *loop;
4971 struct induction *v;
4975 rtx mult_val, add_val, ext_val;
4978 int not_every_iteration, maybe_multiple;
4981 struct loop_ivs *ivs = LOOP_IVS (loop);
4982 struct induction *b;
4983 struct iv_class *bl;
4984 rtx set = single_set (insn);
4987 /* Attempt to prove constantness of the values. */
4988 temp = simplify_rtx (add_val);
4993 v->src_reg = src_reg;
4995 v->dest_reg = dest_reg;
4996 v->mult_val = mult_val;
4997 v->add_val = add_val;
4998 v->ext_dependant = ext_val;
4999 v->benefit = benefit;
5000 v->location = location;
5002 v->combined_with = 0;
5003 v->maybe_multiple = maybe_multiple;
5005 v->derive_adjustment = 0;
5011 v->auto_inc_opt = 0;
5015 /* The v->always_computable field is used in update_giv_derive, to
5016 determine whether a giv can be used to derive another giv. For a
5017 DEST_REG giv, INSN computes a new value for the giv, so its value
5018 isn't computable if INSN insn't executed every iteration.
5019 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5020 it does not compute a new value. Hence the value is always computable
5021 regardless of whether INSN is executed each iteration. */
5023 if (type == DEST_ADDR)
5024 v->always_computable = 1;
5026 v->always_computable = ! not_every_iteration;
5028 v->always_executed = ! not_every_iteration;
5030 if (type == DEST_ADDR)
5032 v->mode = GET_MODE (*location);
5035 else /* type == DEST_REG */
5037 v->mode = GET_MODE (SET_DEST (set));
5039 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
5041 /* If the lifetime is zero, it means that this register is
5042 really a dead store. So mark this as a giv that can be
5043 ignored. This will not prevent the biv from being eliminated. */
5044 if (v->lifetime == 0)
5047 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
5048 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
5051 /* Add the giv to the class of givs computed from one biv. */
5053 bl = ivs->reg_biv_class[REGNO (src_reg)];
5056 v->next_iv = bl->giv;
5058 /* Don't count DEST_ADDR. This is supposed to count the number of
5059 insns that calculate givs. */
5060 if (type == DEST_REG)
5062 bl->total_benefit += benefit;
5065 /* Fatal error, biv missing for this giv? */
5068 if (type == DEST_ADDR)
5072 /* The giv can be replaced outright by the reduced register only if all
5073 of the following conditions are true:
5074 - the insn that sets the giv is always executed on any iteration
5075 on which the giv is used at all
5076 (there are two ways to deduce this:
5077 either the insn is executed on every iteration,
5078 or all uses follow that insn in the same basic block),
5079 - the giv is not used outside the loop
5080 - no assignments to the biv occur during the giv's lifetime. */
5082 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
5083 /* Previous line always fails if INSN was moved by loop opt. */
5084 && REGNO_LAST_LUID (REGNO (dest_reg))
5085 < INSN_LUID (loop->end)
5086 && (! not_every_iteration
5087 || last_use_this_basic_block (dest_reg, insn)))
5089 /* Now check that there are no assignments to the biv within the
5090 giv's lifetime. This requires two separate checks. */
5092 /* Check each biv update, and fail if any are between the first
5093 and last use of the giv.
5095 If this loop contains an inner loop that was unrolled, then
5096 the insn modifying the biv may have been emitted by the loop
5097 unrolling code, and hence does not have a valid luid. Just
5098 mark the biv as not replaceable in this case. It is not very
5099 useful as a biv, because it is used in two different loops.
5100 It is very unlikely that we would be able to optimize the giv
5101 using this biv anyways. */
5104 for (b = bl->biv; b; b = b->next_iv)
5106 if (INSN_UID (b->insn) >= max_uid_for_loop
5107 || ((INSN_LUID (b->insn)
5108 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5109 && (INSN_LUID (b->insn)
5110 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5113 v->not_replaceable = 1;
5118 /* If there are any backwards branches that go from after the
5119 biv update to before it, then this giv is not replaceable. */
5121 for (b = bl->biv; b; b = b->next_iv)
5122 if (back_branch_in_range_p (loop, b->insn))
5125 v->not_replaceable = 1;
5131 /* May still be replaceable, we don't have enough info here to
5134 v->not_replaceable = 0;
5138 /* Record whether the add_val contains a const_int, for later use by
5143 v->no_const_addval = 1;
5144 if (tem == const0_rtx)
5146 else if (CONSTANT_P (add_val))
5147 v->no_const_addval = 0;
5148 if (GET_CODE (tem) == PLUS)
5152 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5153 tem = XEXP (tem, 0);
5154 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5155 tem = XEXP (tem, 1);
5159 if (CONSTANT_P (XEXP (tem, 1)))
5160 v->no_const_addval = 0;
5164 if (loop_dump_stream)
5166 if (type == DEST_REG)
5167 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5168 INSN_UID (insn), REGNO (dest_reg));
5170 fprintf (loop_dump_stream, "Insn %d: dest address",
5173 fprintf (loop_dump_stream, " src reg %d benefit %d",
5174 REGNO (src_reg), v->benefit);
5175 fprintf (loop_dump_stream, " lifetime %d",
5179 fprintf (loop_dump_stream, " replaceable");
5181 if (v->no_const_addval)
5182 fprintf (loop_dump_stream, " ncav");
5184 if (v->ext_dependant)
5186 switch (GET_CODE (v->ext_dependant))
5189 fprintf (loop_dump_stream, " ext se");
5192 fprintf (loop_dump_stream, " ext ze");
5195 fprintf (loop_dump_stream, " ext tr");
5202 if (GET_CODE (mult_val) == CONST_INT)
5204 fprintf (loop_dump_stream, " mult ");
5205 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5209 fprintf (loop_dump_stream, " mult ");
5210 print_rtl (loop_dump_stream, mult_val);
5213 if (GET_CODE (add_val) == CONST_INT)
5215 fprintf (loop_dump_stream, " add ");
5216 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5220 fprintf (loop_dump_stream, " add ");
5221 print_rtl (loop_dump_stream, add_val);
5225 if (loop_dump_stream)
5226 fprintf (loop_dump_stream, "\n");
5230 /* All this does is determine whether a giv can be made replaceable because
5231 its final value can be calculated. This code can not be part of record_giv
5232 above, because final_giv_value requires that the number of loop iterations
5233 be known, and that can not be accurately calculated until after all givs
5234 have been identified. */
5237 check_final_value (loop, v)
5238 const struct loop *loop;
5239 struct induction *v;
5241 struct loop_ivs *ivs = LOOP_IVS (loop);
5242 struct iv_class *bl;
5243 rtx final_value = 0;
5245 bl = ivs->reg_biv_class[REGNO (v->src_reg)];
5247 /* DEST_ADDR givs will never reach here, because they are always marked
5248 replaceable above in record_giv. */
5250 /* The giv can be replaced outright by the reduced register only if all
5251 of the following conditions are true:
5252 - the insn that sets the giv is always executed on any iteration
5253 on which the giv is used at all
5254 (there are two ways to deduce this:
5255 either the insn is executed on every iteration,
5256 or all uses follow that insn in the same basic block),
5257 - its final value can be calculated (this condition is different
5258 than the one above in record_giv)
5259 - it's not used before the it's set
5260 - no assignments to the biv occur during the giv's lifetime. */
5263 /* This is only called now when replaceable is known to be false. */
5264 /* Clear replaceable, so that it won't confuse final_giv_value. */
5268 if ((final_value = final_giv_value (loop, v))
5269 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5271 int biv_increment_seen = 0, before_giv_insn = 0;
5277 /* When trying to determine whether or not a biv increment occurs
5278 during the lifetime of the giv, we can ignore uses of the variable
5279 outside the loop because final_value is true. Hence we can not
5280 use regno_last_uid and regno_first_uid as above in record_giv. */
5282 /* Search the loop to determine whether any assignments to the
5283 biv occur during the giv's lifetime. Start with the insn
5284 that sets the giv, and search around the loop until we come
5285 back to that insn again.
5287 Also fail if there is a jump within the giv's lifetime that jumps
5288 to somewhere outside the lifetime but still within the loop. This
5289 catches spaghetti code where the execution order is not linear, and
5290 hence the above test fails. Here we assume that the giv lifetime
5291 does not extend from one iteration of the loop to the next, so as
5292 to make the test easier. Since the lifetime isn't known yet,
5293 this requires two loops. See also record_giv above. */
5295 last_giv_use = v->insn;
5302 before_giv_insn = 1;
5303 p = NEXT_INSN (loop->start);
5308 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5309 || GET_CODE (p) == CALL_INSN)
5311 /* It is possible for the BIV increment to use the GIV if we
5312 have a cycle. Thus we must be sure to check each insn for
5313 both BIV and GIV uses, and we must check for BIV uses
5316 if (! biv_increment_seen
5317 && reg_set_p (v->src_reg, PATTERN (p)))
5318 biv_increment_seen = 1;
5320 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5322 if (biv_increment_seen || before_giv_insn)
5325 v->not_replaceable = 1;
5333 /* Now that the lifetime of the giv is known, check for branches
5334 from within the lifetime to outside the lifetime if it is still
5344 p = NEXT_INSN (loop->start);
5345 if (p == last_giv_use)
5348 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5349 && LABEL_NAME (JUMP_LABEL (p))
5350 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5351 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5352 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5353 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5356 v->not_replaceable = 1;
5358 if (loop_dump_stream)
5359 fprintf (loop_dump_stream,
5360 "Found branch outside giv lifetime.\n");
5367 /* If it is replaceable, then save the final value. */
5369 v->final_value = final_value;
5372 if (loop_dump_stream && v->replaceable)
5373 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5374 INSN_UID (v->insn), REGNO (v->dest_reg));
5377 /* Update the status of whether a giv can derive other givs.
5379 We need to do something special if there is or may be an update to the biv
5380 between the time the giv is defined and the time it is used to derive
5383 In addition, a giv that is only conditionally set is not allowed to
5384 derive another giv once a label has been passed.
5386 The cases we look at are when a label or an update to a biv is passed. */
5389 update_giv_derive (loop, p)
5390 const struct loop *loop;
5393 struct loop_ivs *ivs = LOOP_IVS (loop);
5394 struct iv_class *bl;
5395 struct induction *biv, *giv;
5399 /* Search all IV classes, then all bivs, and finally all givs.
5401 There are three cases we are concerned with. First we have the situation
5402 of a giv that is only updated conditionally. In that case, it may not
5403 derive any givs after a label is passed.
5405 The second case is when a biv update occurs, or may occur, after the
5406 definition of a giv. For certain biv updates (see below) that are
5407 known to occur between the giv definition and use, we can adjust the
5408 giv definition. For others, or when the biv update is conditional,
5409 we must prevent the giv from deriving any other givs. There are two
5410 sub-cases within this case.
5412 If this is a label, we are concerned with any biv update that is done
5413 conditionally, since it may be done after the giv is defined followed by
5414 a branch here (actually, we need to pass both a jump and a label, but
5415 this extra tracking doesn't seem worth it).
5417 If this is a jump, we are concerned about any biv update that may be
5418 executed multiple times. We are actually only concerned about
5419 backward jumps, but it is probably not worth performing the test
5420 on the jump again here.
5422 If this is a biv update, we must adjust the giv status to show that a
5423 subsequent biv update was performed. If this adjustment cannot be done,
5424 the giv cannot derive further givs. */
5426 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
5427 for (biv = bl->biv; biv; biv = biv->next_iv)
5428 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5431 for (giv = bl->giv; giv; giv = giv->next_iv)
5433 /* If cant_derive is already true, there is no point in
5434 checking all of these conditions again. */
5435 if (giv->cant_derive)
5438 /* If this giv is conditionally set and we have passed a label,
5439 it cannot derive anything. */
5440 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5441 giv->cant_derive = 1;
5443 /* Skip givs that have mult_val == 0, since
5444 they are really invariants. Also skip those that are
5445 replaceable, since we know their lifetime doesn't contain
5447 else if (giv->mult_val == const0_rtx || giv->replaceable)
5450 /* The only way we can allow this giv to derive another
5451 is if this is a biv increment and we can form the product
5452 of biv->add_val and giv->mult_val. In this case, we will
5453 be able to compute a compensation. */
5454 else if (biv->insn == p)
5459 if (biv->mult_val == const1_rtx)
5460 tem = simplify_giv_expr (loop,
5461 gen_rtx_MULT (giv->mode,
5464 &ext_val_dummy, &dummy);
5466 if (tem && giv->derive_adjustment)
5467 tem = simplify_giv_expr
5469 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5470 &ext_val_dummy, &dummy);
5473 giv->derive_adjustment = tem;
5475 giv->cant_derive = 1;
5477 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5478 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5479 giv->cant_derive = 1;
5484 /* Check whether an insn is an increment legitimate for a basic induction var.
5485 X is the source of insn P, or a part of it.
5486 MODE is the mode in which X should be interpreted.
5488 DEST_REG is the putative biv, also the destination of the insn.
5489 We accept patterns of these forms:
5490 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5491 REG = INVARIANT + REG
5493 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5494 store the additive term into *INC_VAL, and store the place where
5495 we found the additive term into *LOCATION.
5497 If X is an assignment of an invariant into DEST_REG, we set
5498 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5500 We also want to detect a BIV when it corresponds to a variable
5501 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5502 of the variable may be a PLUS that adds a SUBREG of that variable to
5503 an invariant and then sign- or zero-extends the result of the PLUS
5506 Most GIVs in such cases will be in the promoted mode, since that is the
5507 probably the natural computation mode (and almost certainly the mode
5508 used for addresses) on the machine. So we view the pseudo-reg containing
5509 the variable as the BIV, as if it were simply incremented.
5511 Note that treating the entire pseudo as a BIV will result in making
5512 simple increments to any GIVs based on it. However, if the variable
5513 overflows in its declared mode but not its promoted mode, the result will
5514 be incorrect. This is acceptable if the variable is signed, since
5515 overflows in such cases are undefined, but not if it is unsigned, since
5516 those overflows are defined. So we only check for SIGN_EXTEND and
5519 If we cannot find a biv, we return 0. */
5522 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5523 const struct loop *loop;
5525 enum machine_mode mode;
5532 register enum rtx_code code;
5536 code = GET_CODE (x);
5541 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5542 || (GET_CODE (XEXP (x, 0)) == SUBREG
5543 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5544 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5546 argp = &XEXP (x, 1);
5548 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5549 || (GET_CODE (XEXP (x, 1)) == SUBREG
5550 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5551 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5553 argp = &XEXP (x, 0);
5559 if (loop_invariant_p (loop, arg) != 1)
5562 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5563 *mult_val = const1_rtx;
5568 /* If this is a SUBREG for a promoted variable, check the inner
5570 if (SUBREG_PROMOTED_VAR_P (x))
5571 return basic_induction_var (loop, SUBREG_REG (x),
5572 GET_MODE (SUBREG_REG (x)),
5573 dest_reg, p, inc_val, mult_val, location);
5577 /* If this register is assigned in a previous insn, look at its
5578 source, but don't go outside the loop or past a label. */
5580 /* If this sets a register to itself, we would repeat any previous
5581 biv increment if we applied this strategy blindly. */
5582 if (rtx_equal_p (dest_reg, x))
5591 insn = PREV_INSN (insn);
5593 while (insn && GET_CODE (insn) == NOTE
5594 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5598 set = single_set (insn);
5601 dest = SET_DEST (set);
5603 || (GET_CODE (dest) == SUBREG
5604 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5605 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5606 && SUBREG_REG (dest) == x))
5607 return basic_induction_var (loop, SET_SRC (set),
5608 (GET_MODE (SET_SRC (set)) == VOIDmode
5610 : GET_MODE (SET_SRC (set))),
5612 inc_val, mult_val, location);
5614 while (GET_CODE (dest) == SIGN_EXTRACT
5615 || GET_CODE (dest) == ZERO_EXTRACT
5616 || GET_CODE (dest) == SUBREG
5617 || GET_CODE (dest) == STRICT_LOW_PART)
5618 dest = XEXP (dest, 0);
5624 /* Can accept constant setting of biv only when inside inner most loop.
5625 Otherwise, a biv of an inner loop may be incorrectly recognized
5626 as a biv of the outer loop,
5627 causing code to be moved INTO the inner loop. */
5629 if (loop_invariant_p (loop, x) != 1)
5634 /* convert_modes aborts if we try to convert to or from CCmode, so just
5635 exclude that case. It is very unlikely that a condition code value
5636 would be a useful iterator anyways. */
5637 if (loop->level == 1
5638 && GET_MODE_CLASS (mode) != MODE_CC
5639 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5641 /* Possible bug here? Perhaps we don't know the mode of X. */
5642 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5643 *mult_val = const0_rtx;
5650 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5651 dest_reg, p, inc_val, mult_val, location);
5654 /* Similar, since this can be a sign extension. */
5655 for (insn = PREV_INSN (p);
5656 (insn && GET_CODE (insn) == NOTE
5657 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5658 insn = PREV_INSN (insn))
5662 set = single_set (insn);
5664 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5665 && set && SET_DEST (set) == XEXP (x, 0)
5666 && GET_CODE (XEXP (x, 1)) == CONST_INT
5667 && INTVAL (XEXP (x, 1)) >= 0
5668 && GET_CODE (SET_SRC (set)) == ASHIFT
5669 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5670 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5671 GET_MODE (XEXP (x, 0)),
5672 dest_reg, insn, inc_val, mult_val,
5681 /* A general induction variable (giv) is any quantity that is a linear
5682 function of a basic induction variable,
5683 i.e. giv = biv * mult_val + add_val.
5684 The coefficients can be any loop invariant quantity.
5685 A giv need not be computed directly from the biv;
5686 it can be computed by way of other givs. */
5688 /* Determine whether X computes a giv.
5689 If it does, return a nonzero value
5690 which is the benefit from eliminating the computation of X;
5691 set *SRC_REG to the register of the biv that it is computed from;
5692 set *ADD_VAL and *MULT_VAL to the coefficients,
5693 such that the value of X is biv * mult + add; */
5696 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5697 is_addr, pbenefit, addr_mode)
5698 const struct loop *loop;
5706 enum machine_mode addr_mode;
5708 struct loop_ivs *ivs = LOOP_IVS (loop);
5711 /* If this is an invariant, forget it, it isn't a giv. */
5712 if (loop_invariant_p (loop, x) == 1)
5716 *ext_val = NULL_RTX;
5717 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5721 switch (GET_CODE (x))
5725 /* Since this is now an invariant and wasn't before, it must be a giv
5726 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5728 *src_reg = ivs->loop_iv_list->biv->dest_reg;
5729 *mult_val = const0_rtx;
5734 /* This is equivalent to a BIV. */
5736 *mult_val = const1_rtx;
5737 *add_val = const0_rtx;
5741 /* Either (plus (biv) (invar)) or
5742 (plus (mult (biv) (invar_1)) (invar_2)). */
5743 if (GET_CODE (XEXP (x, 0)) == MULT)
5745 *src_reg = XEXP (XEXP (x, 0), 0);
5746 *mult_val = XEXP (XEXP (x, 0), 1);
5750 *src_reg = XEXP (x, 0);
5751 *mult_val = const1_rtx;
5753 *add_val = XEXP (x, 1);
5757 /* ADD_VAL is zero. */
5758 *src_reg = XEXP (x, 0);
5759 *mult_val = XEXP (x, 1);
5760 *add_val = const0_rtx;
5767 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5768 unless they are CONST_INT). */
5769 if (GET_CODE (*add_val) == USE)
5770 *add_val = XEXP (*add_val, 0);
5771 if (GET_CODE (*mult_val) == USE)
5772 *mult_val = XEXP (*mult_val, 0);
5775 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5777 *pbenefit += rtx_cost (orig_x, SET);
5779 /* Always return true if this is a giv so it will be detected as such,
5780 even if the benefit is zero or negative. This allows elimination
5781 of bivs that might otherwise not be eliminated. */
5785 /* Given an expression, X, try to form it as a linear function of a biv.
5786 We will canonicalize it to be of the form
5787 (plus (mult (BIV) (invar_1))
5789 with possible degeneracies.
5791 The invariant expressions must each be of a form that can be used as a
5792 machine operand. We surround then with a USE rtx (a hack, but localized
5793 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5794 routine; it is the caller's responsibility to strip them.
5796 If no such canonicalization is possible (i.e., two biv's are used or an
5797 expression that is neither invariant nor a biv or giv), this routine
5800 For a non-zero return, the result will have a code of CONST_INT, USE,
5801 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5803 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5805 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5806 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5809 simplify_giv_expr (loop, x, ext_val, benefit)
5810 const struct loop *loop;
5815 struct loop_ivs *ivs = LOOP_IVS (loop);
5816 struct loop_regs *regs = LOOP_REGS (loop);
5817 enum machine_mode mode = GET_MODE (x);
5821 /* If this is not an integer mode, or if we cannot do arithmetic in this
5822 mode, this can't be a giv. */
5823 if (mode != VOIDmode
5824 && (GET_MODE_CLASS (mode) != MODE_INT
5825 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5828 switch (GET_CODE (x))
5831 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5832 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5833 if (arg0 == 0 || arg1 == 0)
5836 /* Put constant last, CONST_INT last if both constant. */
5837 if ((GET_CODE (arg0) == USE
5838 || GET_CODE (arg0) == CONST_INT)
5839 && ! ((GET_CODE (arg0) == USE
5840 && GET_CODE (arg1) == USE)
5841 || GET_CODE (arg1) == CONST_INT))
5842 tem = arg0, arg0 = arg1, arg1 = tem;
5844 /* Handle addition of zero, then addition of an invariant. */
5845 if (arg1 == const0_rtx)
5847 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5848 switch (GET_CODE (arg0))
5852 /* Adding two invariants must result in an invariant, so enclose
5853 addition operation inside a USE and return it. */
5854 if (GET_CODE (arg0) == USE)
5855 arg0 = XEXP (arg0, 0);
5856 if (GET_CODE (arg1) == USE)
5857 arg1 = XEXP (arg1, 0);
5859 if (GET_CODE (arg0) == CONST_INT)
5860 tem = arg0, arg0 = arg1, arg1 = tem;
5861 if (GET_CODE (arg1) == CONST_INT)
5862 tem = sge_plus_constant (arg0, arg1);
5864 tem = sge_plus (mode, arg0, arg1);
5866 if (GET_CODE (tem) != CONST_INT)
5867 tem = gen_rtx_USE (mode, tem);
5872 /* biv + invar or mult + invar. Return sum. */
5873 return gen_rtx_PLUS (mode, arg0, arg1);
5876 /* (a + invar_1) + invar_2. Associate. */
5878 simplify_giv_expr (loop,
5890 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5891 MULT to reduce cases. */
5892 if (GET_CODE (arg0) == REG)
5893 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5894 if (GET_CODE (arg1) == REG)
5895 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5897 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5898 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5899 Recurse to associate the second PLUS. */
5900 if (GET_CODE (arg1) == MULT)
5901 tem = arg0, arg0 = arg1, arg1 = tem;
5903 if (GET_CODE (arg1) == PLUS)
5905 simplify_giv_expr (loop,
5907 gen_rtx_PLUS (mode, arg0,
5912 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5913 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5916 if (!rtx_equal_p (arg0, arg1))
5919 return simplify_giv_expr (loop,
5928 /* Handle "a - b" as "a + b * (-1)". */
5929 return simplify_giv_expr (loop,
5938 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5939 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5940 if (arg0 == 0 || arg1 == 0)
5943 /* Put constant last, CONST_INT last if both constant. */
5944 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5945 && GET_CODE (arg1) != CONST_INT)
5946 tem = arg0, arg0 = arg1, arg1 = tem;
5948 /* If second argument is not now constant, not giv. */
5949 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5952 /* Handle multiply by 0 or 1. */
5953 if (arg1 == const0_rtx)
5956 else if (arg1 == const1_rtx)
5959 switch (GET_CODE (arg0))
5962 /* biv * invar. Done. */
5963 return gen_rtx_MULT (mode, arg0, arg1);
5966 /* Product of two constants. */
5967 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5970 /* invar * invar is a giv, but attempt to simplify it somehow. */
5971 if (GET_CODE (arg1) != CONST_INT)
5974 arg0 = XEXP (arg0, 0);
5975 if (GET_CODE (arg0) == MULT)
5977 /* (invar_0 * invar_1) * invar_2. Associate. */
5978 return simplify_giv_expr (loop,
5987 /* Porpagate the MULT expressions to the intermost nodes. */
5988 else if (GET_CODE (arg0) == PLUS)
5990 /* (invar_0 + invar_1) * invar_2. Distribute. */
5991 return simplify_giv_expr (loop,
6003 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
6006 /* (a * invar_1) * invar_2. Associate. */
6007 return simplify_giv_expr (loop,
6016 /* (a + invar_1) * invar_2. Distribute. */
6017 return simplify_giv_expr (loop,
6032 /* Shift by constant is multiply by power of two. */
6033 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
6037 simplify_giv_expr (loop,
6040 GEN_INT ((HOST_WIDE_INT) 1
6041 << INTVAL (XEXP (x, 1)))),
6045 /* "-a" is "a * (-1)" */
6046 return simplify_giv_expr (loop,
6047 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
6051 /* "~a" is "-a - 1". Silly, but easy. */
6052 return simplify_giv_expr (loop,
6053 gen_rtx_MINUS (mode,
6054 gen_rtx_NEG (mode, XEXP (x, 0)),
6059 /* Already in proper form for invariant. */
6065 /* Conditionally recognize extensions of simple IVs. After we've
6066 computed loop traversal counts and verified the range of the
6067 source IV, we'll reevaluate this as a GIV. */
6068 if (*ext_val == NULL_RTX)
6070 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
6071 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
6073 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
6080 /* If this is a new register, we can't deal with it. */
6081 if (REGNO (x) >= max_reg_before_loop)
6084 /* Check for biv or giv. */
6085 switch (REG_IV_TYPE (ivs, REGNO (x)))
6089 case GENERAL_INDUCT:
6091 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
6093 /* Form expression from giv and add benefit. Ensure this giv
6094 can derive another and subtract any needed adjustment if so. */
6096 /* Increasing the benefit here is risky. The only case in which it
6097 is arguably correct is if this is the only use of V. In other
6098 cases, this will artificially inflate the benefit of the current
6099 giv, and lead to suboptimal code. Thus, it is disabled, since
6100 potentially not reducing an only marginally beneficial giv is
6101 less harmful than reducing many givs that are not really
6104 rtx single_use = VARRAY_RTX (regs->single_usage, REGNO (x));
6105 if (single_use && single_use != const0_rtx)
6106 *benefit += v->benefit;
6112 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
6113 v->src_reg, v->mult_val),
6116 if (v->derive_adjustment)
6117 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
6118 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
6121 if (!v->ext_dependant)
6126 *ext_val = v->ext_dependant;
6134 /* If it isn't an induction variable, and it is invariant, we
6135 may be able to simplify things further by looking through
6136 the bits we just moved outside the loop. */
6137 if (loop_invariant_p (loop, x) == 1)
6140 struct loop_movables *movables = LOOP_MOVABLES (loop);
6142 for (m = movables->head; m; m = m->next)
6143 if (rtx_equal_p (x, m->set_dest))
6145 /* Ok, we found a match. Substitute and simplify. */
6147 /* If we match another movable, we must use that, as
6148 this one is going away. */
6150 return simplify_giv_expr (loop, m->match->set_dest,
6153 /* If consec is non-zero, this is a member of a group of
6154 instructions that were moved together. We handle this
6155 case only to the point of seeking to the last insn and
6156 looking for a REG_EQUAL. Fail if we don't find one. */
6163 tem = NEXT_INSN (tem);
6167 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6169 tem = XEXP (tem, 0);
6173 tem = single_set (m->insn);
6175 tem = SET_SRC (tem);
6180 /* What we are most interested in is pointer
6181 arithmetic on invariants -- only take
6182 patterns we may be able to do something with. */
6183 if (GET_CODE (tem) == PLUS
6184 || GET_CODE (tem) == MULT
6185 || GET_CODE (tem) == ASHIFT
6186 || GET_CODE (tem) == CONST_INT
6187 || GET_CODE (tem) == SYMBOL_REF)
6189 tem = simplify_giv_expr (loop, tem, ext_val,
6194 else if (GET_CODE (tem) == CONST
6195 && GET_CODE (XEXP (tem, 0)) == PLUS
6196 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6197 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6199 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6211 /* Fall through to general case. */
6213 /* If invariant, return as USE (unless CONST_INT).
6214 Otherwise, not giv. */
6215 if (GET_CODE (x) == USE)
6218 if (loop_invariant_p (loop, x) == 1)
6220 if (GET_CODE (x) == CONST_INT)
6222 if (GET_CODE (x) == CONST
6223 && GET_CODE (XEXP (x, 0)) == PLUS
6224 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6225 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6227 return gen_rtx_USE (mode, x);
6234 /* This routine folds invariants such that there is only ever one
6235 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6238 sge_plus_constant (x, c)
6241 if (GET_CODE (x) == CONST_INT)
6242 return GEN_INT (INTVAL (x) + INTVAL (c));
6243 else if (GET_CODE (x) != PLUS)
6244 return gen_rtx_PLUS (GET_MODE (x), x, c);
6245 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6247 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6248 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6250 else if (GET_CODE (XEXP (x, 0)) == PLUS
6251 || GET_CODE (XEXP (x, 1)) != PLUS)
6253 return gen_rtx_PLUS (GET_MODE (x),
6254 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6258 return gen_rtx_PLUS (GET_MODE (x),
6259 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6264 sge_plus (mode, x, y)
6265 enum machine_mode mode;
6268 while (GET_CODE (y) == PLUS)
6270 rtx a = XEXP (y, 0);
6271 if (GET_CODE (a) == CONST_INT)
6272 x = sge_plus_constant (x, a);
6274 x = gen_rtx_PLUS (mode, x, a);
6277 if (GET_CODE (y) == CONST_INT)
6278 x = sge_plus_constant (x, y);
6280 x = gen_rtx_PLUS (mode, x, y);
6284 /* Help detect a giv that is calculated by several consecutive insns;
6288 The caller has already identified the first insn P as having a giv as dest;
6289 we check that all other insns that set the same register follow
6290 immediately after P, that they alter nothing else,
6291 and that the result of the last is still a giv.
6293 The value is 0 if the reg set in P is not really a giv.
6294 Otherwise, the value is the amount gained by eliminating
6295 all the consecutive insns that compute the value.
6297 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6298 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6300 The coefficients of the ultimate giv value are stored in
6301 *MULT_VAL and *ADD_VAL. */
6304 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6305 add_val, mult_val, ext_val, last_consec_insn)
6306 const struct loop *loop;
6314 rtx *last_consec_insn;
6316 struct loop_ivs *ivs = LOOP_IVS (loop);
6317 struct loop_regs *regs = LOOP_REGS (loop);
6324 /* Indicate that this is a giv so that we can update the value produced in
6325 each insn of the multi-insn sequence.
6327 This induction structure will be used only by the call to
6328 general_induction_var below, so we can allocate it on our stack.
6329 If this is a giv, our caller will replace the induct var entry with
6330 a new induction structure. */
6331 struct induction *v;
6333 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6336 v = (struct induction *) alloca (sizeof (struct induction));
6337 v->src_reg = src_reg;
6338 v->mult_val = *mult_val;
6339 v->add_val = *add_val;
6340 v->benefit = first_benefit;
6342 v->derive_adjustment = 0;
6343 v->ext_dependant = NULL_RTX;
6345 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6346 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6348 count = VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) - 1;
6353 code = GET_CODE (p);
6355 /* If libcall, skip to end of call sequence. */
6356 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6360 && (set = single_set (p))
6361 && GET_CODE (SET_DEST (set)) == REG
6362 && SET_DEST (set) == dest_reg
6363 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6364 add_val, mult_val, ext_val, 0,
6366 /* Giv created by equivalent expression. */
6367 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6368 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6369 add_val, mult_val, ext_val, 0,
6370 &benefit, VOIDmode)))
6371 && src_reg == v->src_reg)
6373 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6374 benefit += libcall_benefit (p);
6377 v->mult_val = *mult_val;
6378 v->add_val = *add_val;
6379 v->benefit += benefit;
6381 else if (code != NOTE)
6383 /* Allow insns that set something other than this giv to a
6384 constant. Such insns are needed on machines which cannot
6385 include long constants and should not disqualify a giv. */
6387 && (set = single_set (p))
6388 && SET_DEST (set) != dest_reg
6389 && CONSTANT_P (SET_SRC (set)))
6392 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6397 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6398 *last_consec_insn = p;
6402 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6403 represented by G1. If no such expression can be found, or it is clear that
6404 it cannot possibly be a valid address, 0 is returned.
6406 To perform the computation, we note that
6409 where `v' is the biv.
6411 So G2 = (y/b) * G1 + (b - a*y/x).
6413 Note that MULT = y/x.
6415 Update: A and B are now allowed to be additive expressions such that
6416 B contains all variables in A. That is, computing B-A will not require
6417 subtracting variables. */
6420 express_from_1 (a, b, mult)
6423 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6425 if (mult == const0_rtx)
6428 /* If MULT is not 1, we cannot handle A with non-constants, since we
6429 would then be required to subtract multiples of the registers in A.
6430 This is theoretically possible, and may even apply to some Fortran
6431 constructs, but it is a lot of work and we do not attempt it here. */
6433 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6436 /* In general these structures are sorted top to bottom (down the PLUS
6437 chain), but not left to right across the PLUS. If B is a higher
6438 order giv than A, we can strip one level and recurse. If A is higher
6439 order, we'll eventually bail out, but won't know that until the end.
6440 If they are the same, we'll strip one level around this loop. */
6442 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6444 rtx ra, rb, oa, ob, tmp;
6446 ra = XEXP (a, 0), oa = XEXP (a, 1);
6447 if (GET_CODE (ra) == PLUS)
6448 tmp = ra, ra = oa, oa = tmp;
6450 rb = XEXP (b, 0), ob = XEXP (b, 1);
6451 if (GET_CODE (rb) == PLUS)
6452 tmp = rb, rb = ob, ob = tmp;
6454 if (rtx_equal_p (ra, rb))
6455 /* We matched: remove one reg completely. */
6457 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6458 /* An alternate match. */
6460 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6461 /* An alternate match. */
6465 /* Indicates an extra register in B. Strip one level from B and
6466 recurse, hoping B was the higher order expression. */
6467 ob = express_from_1 (a, ob, mult);
6470 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6474 /* Here we are at the last level of A, go through the cases hoping to
6475 get rid of everything but a constant. */
6477 if (GET_CODE (a) == PLUS)
6481 ra = XEXP (a, 0), oa = XEXP (a, 1);
6482 if (rtx_equal_p (oa, b))
6484 else if (!rtx_equal_p (ra, b))
6487 if (GET_CODE (oa) != CONST_INT)
6490 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6492 else if (GET_CODE (a) == CONST_INT)
6494 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6496 else if (CONSTANT_P (a))
6498 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6500 else if (GET_CODE (b) == PLUS)
6502 if (rtx_equal_p (a, XEXP (b, 0)))
6504 else if (rtx_equal_p (a, XEXP (b, 1)))
6509 else if (rtx_equal_p (a, b))
6516 express_from (g1, g2)
6517 struct induction *g1, *g2;
6521 /* The value that G1 will be multiplied by must be a constant integer. Also,
6522 the only chance we have of getting a valid address is if b*c/a (see above
6523 for notation) is also an integer. */
6524 if (GET_CODE (g1->mult_val) == CONST_INT
6525 && GET_CODE (g2->mult_val) == CONST_INT)
6527 if (g1->mult_val == const0_rtx
6528 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6530 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6532 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6536 /* ??? Find out if the one is a multiple of the other? */
6540 add = express_from_1 (g1->add_val, g2->add_val, mult);
6541 if (add == NULL_RTX)
6543 /* Failed. If we've got a multiplication factor between G1 and G2,
6544 scale G1's addend and try again. */
6545 if (INTVAL (mult) > 1)
6547 rtx g1_add_val = g1->add_val;
6548 if (GET_CODE (g1_add_val) == MULT
6549 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6552 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6553 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6554 XEXP (g1_add_val, 0), GEN_INT (m));
6558 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6562 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6565 if (add == NULL_RTX)
6568 /* Form simplified final result. */
6569 if (mult == const0_rtx)
6571 else if (mult == const1_rtx)
6572 mult = g1->dest_reg;
6574 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6576 if (add == const0_rtx)
6580 if (GET_CODE (add) == PLUS
6581 && CONSTANT_P (XEXP (add, 1)))
6583 rtx tem = XEXP (add, 1);
6584 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6588 return gen_rtx_PLUS (g2->mode, mult, add);
6592 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6593 represented by G1. This indicates that G2 should be combined with G1 and
6594 that G2 can use (either directly or via an address expression) a register
6595 used to represent G1. */
6598 combine_givs_p (g1, g2)
6599 struct induction *g1, *g2;
6603 /* With the introduction of ext dependant givs, we must care for modes.
6604 G2 must not use a wider mode than G1. */
6605 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6608 ret = comb = express_from (g1, g2);
6609 if (comb == NULL_RTX)
6611 if (g1->mode != g2->mode)
6612 ret = gen_lowpart (g2->mode, comb);
6614 /* If these givs are identical, they can be combined. We use the results
6615 of express_from because the addends are not in a canonical form, so
6616 rtx_equal_p is a weaker test. */
6617 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6618 combination to be the other way round. */
6619 if (comb == g1->dest_reg
6620 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6625 /* If G2 can be expressed as a function of G1 and that function is valid
6626 as an address and no more expensive than using a register for G2,
6627 the expression of G2 in terms of G1 can be used. */
6629 && g2->giv_type == DEST_ADDR
6630 && memory_address_p (g2->mem_mode, ret)
6631 /* ??? Looses, especially with -fforce-addr, where *g2->location
6632 will always be a register, and so anything more complicated
6636 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6638 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6649 /* Check each extension dependant giv in this class to see if its
6650 root biv is safe from wrapping in the interior mode, which would
6651 make the giv illegal. */
6654 check_ext_dependant_givs (bl, loop_info)
6655 struct iv_class *bl;
6656 struct loop_info *loop_info;
6658 int ze_ok = 0, se_ok = 0, info_ok = 0;
6659 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6660 HOST_WIDE_INT start_val;
6661 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6663 struct induction *v;
6665 /* Make sure the iteration data is available. We must have
6666 constants in order to be certain of no overflow. */
6667 /* ??? An unknown iteration count with an increment of +-1
6668 combined with friendly exit tests of against an invariant
6669 value is also ameanable to optimization. Not implemented. */
6670 if (loop_info->n_iterations > 0
6671 && bl->initial_value
6672 && GET_CODE (bl->initial_value) == CONST_INT
6673 && (incr = biv_total_increment (bl))
6674 && GET_CODE (incr) == CONST_INT
6675 /* Make sure the host can represent the arithmetic. */
6676 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6678 unsigned HOST_WIDE_INT abs_incr, total_incr;
6679 HOST_WIDE_INT s_end_val;
6683 start_val = INTVAL (bl->initial_value);
6684 u_start_val = start_val;
6686 neg_incr = 0, abs_incr = INTVAL (incr);
6687 if (INTVAL (incr) < 0)
6688 neg_incr = 1, abs_incr = -abs_incr;
6689 total_incr = abs_incr * loop_info->n_iterations;
6691 /* Check for host arithmatic overflow. */
6692 if (total_incr / loop_info->n_iterations == abs_incr)
6694 unsigned HOST_WIDE_INT u_max;
6695 HOST_WIDE_INT s_max;
6697 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6698 s_end_val = u_end_val;
6699 u_max = GET_MODE_MASK (biv_mode);
6702 /* Check zero extension of biv ok. */
6704 /* Check for host arithmatic overflow. */
6706 ? u_end_val < u_start_val
6707 : u_end_val > u_start_val)
6708 /* Check for target arithmetic overflow. */
6710 ? 1 /* taken care of with host overflow */
6711 : u_end_val <= u_max))
6716 /* Check sign extension of biv ok. */
6717 /* ??? While it is true that overflow with signed and pointer
6718 arithmetic is undefined, I fear too many programmers don't
6719 keep this fact in mind -- myself included on occasion.
6720 So leave alone with the signed overflow optimizations. */
6721 if (start_val >= -s_max - 1
6722 /* Check for host arithmatic overflow. */
6724 ? s_end_val < start_val
6725 : s_end_val > start_val)
6726 /* Check for target arithmetic overflow. */
6728 ? s_end_val >= -s_max - 1
6729 : s_end_val <= s_max))
6736 /* Invalidate givs that fail the tests. */
6737 for (v = bl->giv; v; v = v->next_iv)
6738 if (v->ext_dependant)
6740 enum rtx_code code = GET_CODE (v->ext_dependant);
6753 /* We don't know whether this value is being used as either
6754 signed or unsigned, so to safely truncate we must satisfy
6755 both. The initial check here verifies the BIV itself;
6756 once that is successful we may check its range wrt the
6760 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6761 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6763 /* We know from the above that both endpoints are nonnegative,
6764 and that there is no wrapping. Verify that both endpoints
6765 are within the (signed) range of the outer mode. */
6766 if (u_start_val <= max && u_end_val <= max)
6777 if (loop_dump_stream)
6779 fprintf (loop_dump_stream,
6780 "Verified ext dependant giv at %d of reg %d\n",
6781 INSN_UID (v->insn), bl->regno);
6786 if (loop_dump_stream)
6791 why = "biv iteration values overflowed";
6795 incr = biv_total_increment (bl);
6796 if (incr == const1_rtx)
6797 why = "biv iteration info incomplete; incr by 1";
6799 why = "biv iteration info incomplete";
6802 fprintf (loop_dump_stream,
6803 "Failed ext dependant giv at %d, %s\n",
6804 INSN_UID (v->insn), why);
6811 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6814 extend_value_for_giv (v, value)
6815 struct induction *v;
6818 rtx ext_dep = v->ext_dependant;
6823 /* Recall that check_ext_dependant_givs verified that the known bounds
6824 of a biv did not overflow or wrap with respect to the extension for
6825 the giv. Therefore, constants need no additional adjustment. */
6826 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6829 /* Otherwise, we must adjust the value to compensate for the
6830 differing modes of the biv and the giv. */
6831 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6834 struct combine_givs_stats
6841 cmp_combine_givs_stats (xp, yp)
6845 const struct combine_givs_stats * const x =
6846 (const struct combine_givs_stats *) xp;
6847 const struct combine_givs_stats * const y =
6848 (const struct combine_givs_stats *) yp;
6850 d = y->total_benefit - x->total_benefit;
6851 /* Stabilize the sort. */
6853 d = x->giv_number - y->giv_number;
6857 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6858 any other. If so, point SAME to the giv combined with and set NEW_REG to
6859 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6860 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6863 combine_givs (regs, bl)
6864 struct loop_regs *regs;
6865 struct iv_class *bl;
6867 /* Additional benefit to add for being combined multiple times. */
6868 const int extra_benefit = 3;
6870 struct induction *g1, *g2, **giv_array;
6871 int i, j, k, giv_count;
6872 struct combine_givs_stats *stats;
6875 /* Count givs, because bl->giv_count is incorrect here. */
6877 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6882 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6884 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6886 giv_array[i++] = g1;
6888 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6889 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6891 for (i = 0; i < giv_count; i++)
6897 stats[i].giv_number = i;
6899 /* If a DEST_REG GIV is used only once, do not allow it to combine
6900 with anything, for in doing so we will gain nothing that cannot
6901 be had by simply letting the GIV with which we would have combined
6902 to be reduced on its own. The losage shows up in particular with
6903 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6904 be seen elsewhere as well. */
6905 if (g1->giv_type == DEST_REG
6906 && (single_use = VARRAY_RTX (regs->single_usage,
6907 REGNO (g1->dest_reg)))
6908 && single_use != const0_rtx)
6911 this_benefit = g1->benefit;
6912 /* Add an additional weight for zero addends. */
6913 if (g1->no_const_addval)
6916 for (j = 0; j < giv_count; j++)
6922 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6924 can_combine[i * giv_count + j] = this_combine;
6925 this_benefit += g2->benefit + extra_benefit;
6928 stats[i].total_benefit = this_benefit;
6931 /* Iterate, combining until we can't. */
6933 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6935 if (loop_dump_stream)
6937 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6938 for (k = 0; k < giv_count; k++)
6940 g1 = giv_array[stats[k].giv_number];
6941 if (!g1->combined_with && !g1->same)
6942 fprintf (loop_dump_stream, " {%d, %d}",
6943 INSN_UID (giv_array[stats[k].giv_number]->insn),
6944 stats[k].total_benefit);
6946 putc ('\n', loop_dump_stream);
6949 for (k = 0; k < giv_count; k++)
6951 int g1_add_benefit = 0;
6953 i = stats[k].giv_number;
6956 /* If it has already been combined, skip. */
6957 if (g1->combined_with || g1->same)
6960 for (j = 0; j < giv_count; j++)
6963 if (g1 != g2 && can_combine[i * giv_count + j]
6964 /* If it has already been combined, skip. */
6965 && ! g2->same && ! g2->combined_with)
6969 g2->new_reg = can_combine[i * giv_count + j];
6971 g1->combined_with++;
6972 g1->lifetime += g2->lifetime;
6974 g1_add_benefit += g2->benefit;
6976 /* ??? The new final_[bg]iv_value code does a much better job
6977 of finding replaceable giv's, and hence this code may no
6978 longer be necessary. */
6979 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6980 g1_add_benefit -= copy_cost;
6982 /* To help optimize the next set of combinations, remove
6983 this giv from the benefits of other potential mates. */
6984 for (l = 0; l < giv_count; ++l)
6986 int m = stats[l].giv_number;
6987 if (can_combine[m * giv_count + j])
6988 stats[l].total_benefit -= g2->benefit + extra_benefit;
6991 if (loop_dump_stream)
6992 fprintf (loop_dump_stream,
6993 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
6994 INSN_UID (g2->insn), INSN_UID (g1->insn),
6995 g1->benefit, g1_add_benefit, g1->lifetime);
6999 /* To help optimize the next set of combinations, remove
7000 this giv from the benefits of other potential mates. */
7001 if (g1->combined_with)
7003 for (j = 0; j < giv_count; ++j)
7005 int m = stats[j].giv_number;
7006 if (can_combine[m * giv_count + i])
7007 stats[j].total_benefit -= g1->benefit + extra_benefit;
7010 g1->benefit += g1_add_benefit;
7012 /* We've finished with this giv, and everything it touched.
7013 Restart the combination so that proper weights for the
7014 rest of the givs are properly taken into account. */
7015 /* ??? Ideally we would compact the arrays at this point, so
7016 as to not cover old ground. But sanely compacting
7017 can_combine is tricky. */
7027 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
7030 emit_iv_add_mult (b, m, a, reg, insert_before)
7031 rtx b; /* initial value of basic induction variable */
7032 rtx m; /* multiplicative constant */
7033 rtx a; /* additive constant */
7034 rtx reg; /* destination register */
7040 /* Prevent unexpected sharing of these rtx. */
7044 /* Increase the lifetime of any invariants moved further in code. */
7045 update_reg_last_use (a, insert_before);
7046 update_reg_last_use (b, insert_before);
7047 update_reg_last_use (m, insert_before);
7050 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
7052 emit_move_insn (reg, result);
7053 seq = gen_sequence ();
7056 emit_insn_before (seq, insert_before);
7058 /* It is entirely possible that the expansion created lots of new
7059 registers. Iterate over the sequence we just created and
7062 if (GET_CODE (seq) == SEQUENCE)
7065 for (i = 0; i < XVECLEN (seq, 0); ++i)
7067 rtx set = single_set (XVECEXP (seq, 0, i));
7068 if (set && GET_CODE (SET_DEST (set)) == REG)
7069 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
7072 else if (GET_CODE (seq) == SET
7073 && GET_CODE (SET_DEST (seq)) == REG)
7074 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
7077 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
7080 iv_add_mult_cost (b, m, a, reg)
7081 rtx b; /* initial value of basic induction variable */
7082 rtx m; /* multiplicative constant */
7083 rtx a; /* additive constant */
7084 rtx reg; /* destination register */
7090 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
7092 emit_move_insn (reg, result);
7093 last = get_last_insn ();
7096 rtx t = single_set (last);
7098 cost += rtx_cost (SET_SRC (t), SET);
7099 last = PREV_INSN (last);
7105 /* Test whether A * B can be computed without
7106 an actual multiply insn. Value is 1 if so. */
7109 product_cheap_p (a, b)
7117 /* If only one is constant, make it B. */
7118 if (GET_CODE (a) == CONST_INT)
7119 tmp = a, a = b, b = tmp;
7121 /* If first constant, both constant, so don't need multiply. */
7122 if (GET_CODE (a) == CONST_INT)
7125 /* If second not constant, neither is constant, so would need multiply. */
7126 if (GET_CODE (b) != CONST_INT)
7129 /* One operand is constant, so might not need multiply insn. Generate the
7130 code for the multiply and see if a call or multiply, or long sequence
7131 of insns is generated. */
7134 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
7135 tmp = gen_sequence ();
7138 if (GET_CODE (tmp) == SEQUENCE)
7140 if (XVEC (tmp, 0) == 0)
7142 else if (XVECLEN (tmp, 0) > 3)
7145 for (i = 0; i < XVECLEN (tmp, 0); i++)
7147 rtx insn = XVECEXP (tmp, 0, i);
7149 if (GET_CODE (insn) != INSN
7150 || (GET_CODE (PATTERN (insn)) == SET
7151 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
7152 || (GET_CODE (PATTERN (insn)) == PARALLEL
7153 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
7154 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7161 else if (GET_CODE (tmp) == SET
7162 && GET_CODE (SET_SRC (tmp)) == MULT)
7164 else if (GET_CODE (tmp) == PARALLEL
7165 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7166 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7172 /* Check to see if loop can be terminated by a "decrement and branch until
7173 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7174 Also try reversing an increment loop to a decrement loop
7175 to see if the optimization can be performed.
7176 Value is nonzero if optimization was performed. */
7178 /* This is useful even if the architecture doesn't have such an insn,
7179 because it might change a loops which increments from 0 to n to a loop
7180 which decrements from n to 0. A loop that decrements to zero is usually
7181 faster than one that increments from zero. */
7183 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7184 such as approx_final_value, biv_total_increment, loop_iterations, and
7185 final_[bg]iv_value. */
7188 check_dbra_loop (loop, insn_count)
7192 struct loop_info *loop_info = LOOP_INFO (loop);
7193 struct loop_regs *regs = LOOP_REGS (loop);
7194 struct loop_ivs *ivs = LOOP_IVS (loop);
7195 struct iv_class *bl;
7202 rtx before_comparison;
7206 int compare_and_branch;
7207 rtx loop_start = loop->start;
7208 rtx loop_end = loop->end;
7210 /* If last insn is a conditional branch, and the insn before tests a
7211 register value, try to optimize it. Otherwise, we can't do anything. */
7213 jump = PREV_INSN (loop_end);
7214 comparison = get_condition_for_loop (loop, jump);
7215 if (comparison == 0)
7217 if (!onlyjump_p (jump))
7220 /* Try to compute whether the compare/branch at the loop end is one or
7221 two instructions. */
7222 get_condition (jump, &first_compare);
7223 if (first_compare == jump)
7224 compare_and_branch = 1;
7225 else if (first_compare == prev_nonnote_insn (jump))
7226 compare_and_branch = 2;
7231 /* If more than one condition is present to control the loop, then
7232 do not proceed, as this function does not know how to rewrite
7233 loop tests with more than one condition.
7235 Look backwards from the first insn in the last comparison
7236 sequence and see if we've got another comparison sequence. */
7239 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7240 if (GET_CODE (jump1) == JUMP_INSN)
7244 /* Check all of the bivs to see if the compare uses one of them.
7245 Skip biv's set more than once because we can't guarantee that
7246 it will be zero on the last iteration. Also skip if the biv is
7247 used between its update and the test insn. */
7249 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
7251 if (bl->biv_count == 1
7252 && ! bl->biv->maybe_multiple
7253 && bl->biv->dest_reg == XEXP (comparison, 0)
7254 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7262 /* Look for the case where the basic induction variable is always
7263 nonnegative, and equals zero on the last iteration.
7264 In this case, add a reg_note REG_NONNEG, which allows the
7265 m68k DBRA instruction to be used. */
7267 if (((GET_CODE (comparison) == GT
7268 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7269 && INTVAL (XEXP (comparison, 1)) == -1)
7270 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7271 && GET_CODE (bl->biv->add_val) == CONST_INT
7272 && INTVAL (bl->biv->add_val) < 0)
7274 /* Initial value must be greater than 0,
7275 init_val % -dec_value == 0 to ensure that it equals zero on
7276 the last iteration */
7278 if (GET_CODE (bl->initial_value) == CONST_INT
7279 && INTVAL (bl->initial_value) > 0
7280 && (INTVAL (bl->initial_value)
7281 % (-INTVAL (bl->biv->add_val))) == 0)
7283 /* register always nonnegative, add REG_NOTE to branch */
7284 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7286 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7293 /* If the decrement is 1 and the value was tested as >= 0 before
7294 the loop, then we can safely optimize. */
7295 for (p = loop_start; p; p = PREV_INSN (p))
7297 if (GET_CODE (p) == CODE_LABEL)
7299 if (GET_CODE (p) != JUMP_INSN)
7302 before_comparison = get_condition_for_loop (loop, p);
7303 if (before_comparison
7304 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7305 && GET_CODE (before_comparison) == LT
7306 && XEXP (before_comparison, 1) == const0_rtx
7307 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7308 && INTVAL (bl->biv->add_val) == -1)
7310 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7312 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7320 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7321 && INTVAL (bl->biv->add_val) > 0)
7323 /* Try to change inc to dec, so can apply above optimization. */
7325 all registers modified are induction variables or invariant,
7326 all memory references have non-overlapping addresses
7327 (obviously true if only one write)
7328 allow 2 insns for the compare/jump at the end of the loop. */
7329 /* Also, we must avoid any instructions which use both the reversed
7330 biv and another biv. Such instructions will fail if the loop is
7331 reversed. We meet this condition by requiring that either
7332 no_use_except_counting is true, or else that there is only
7334 int num_nonfixed_reads = 0;
7335 /* 1 if the iteration var is used only to count iterations. */
7336 int no_use_except_counting = 0;
7337 /* 1 if the loop has no memory store, or it has a single memory store
7338 which is reversible. */
7339 int reversible_mem_store = 1;
7341 if (bl->giv_count == 0 && ! loop->exit_count)
7343 rtx bivreg = regno_reg_rtx[bl->regno];
7345 /* If there are no givs for this biv, and the only exit is the
7346 fall through at the end of the loop, then
7347 see if perhaps there are no uses except to count. */
7348 no_use_except_counting = 1;
7349 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7352 rtx set = single_set (p);
7354 if (set && GET_CODE (SET_DEST (set)) == REG
7355 && REGNO (SET_DEST (set)) == bl->regno)
7356 /* An insn that sets the biv is okay. */
7358 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7359 || p == prev_nonnote_insn (loop_end))
7360 && reg_mentioned_p (bivreg, PATTERN (p)))
7362 /* If either of these insns uses the biv and sets a pseudo
7363 that has more than one usage, then the biv has uses
7364 other than counting since it's used to derive a value
7365 that is used more than one time. */
7366 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7368 if (regs->multiple_uses)
7370 no_use_except_counting = 0;
7374 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7376 no_use_except_counting = 0;
7382 if (no_use_except_counting)
7383 /* No need to worry about MEMs. */
7385 else if (loop_info->num_mem_sets <= 1)
7387 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7389 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7391 /* If the loop has a single store, and the destination address is
7392 invariant, then we can't reverse the loop, because this address
7393 might then have the wrong value at loop exit.
7394 This would work if the source was invariant also, however, in that
7395 case, the insn should have been moved out of the loop. */
7397 if (loop_info->num_mem_sets == 1)
7399 struct induction *v;
7401 reversible_mem_store
7402 = (! loop_info->unknown_address_altered
7403 && ! loop_info->unknown_constant_address_altered
7404 && ! loop_invariant_p (loop,
7405 XEXP (XEXP (loop_info->store_mems, 0),
7408 /* If the store depends on a register that is set after the
7409 store, it depends on the initial value, and is thus not
7411 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7413 if (v->giv_type == DEST_REG
7414 && reg_mentioned_p (v->dest_reg,
7415 PATTERN (loop_info->first_loop_store_insn))
7416 && loop_insn_first_p (loop_info->first_loop_store_insn,
7418 reversible_mem_store = 0;
7425 /* This code only acts for innermost loops. Also it simplifies
7426 the memory address check by only reversing loops with
7427 zero or one memory access.
7428 Two memory accesses could involve parts of the same array,
7429 and that can't be reversed.
7430 If the biv is used only for counting, than we don't need to worry
7431 about all these things. */
7433 if ((num_nonfixed_reads <= 1
7434 && ! loop_info->has_call
7435 && ! loop_info->has_volatile
7436 && reversible_mem_store
7437 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7438 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7439 && (bl == ivs->loop_iv_list && bl->next == 0))
7440 || no_use_except_counting)
7444 /* Loop can be reversed. */
7445 if (loop_dump_stream)
7446 fprintf (loop_dump_stream, "Can reverse loop\n");
7448 /* Now check other conditions:
7450 The increment must be a constant, as must the initial value,
7451 and the comparison code must be LT.
7453 This test can probably be improved since +/- 1 in the constant
7454 can be obtained by changing LT to LE and vice versa; this is
7458 /* for constants, LE gets turned into LT */
7459 && (GET_CODE (comparison) == LT
7460 || (GET_CODE (comparison) == LE
7461 && no_use_except_counting)))
7463 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7464 rtx initial_value, comparison_value;
7466 enum rtx_code cmp_code;
7467 int comparison_const_width;
7468 unsigned HOST_WIDE_INT comparison_sign_mask;
7470 add_val = INTVAL (bl->biv->add_val);
7471 comparison_value = XEXP (comparison, 1);
7472 if (GET_MODE (comparison_value) == VOIDmode)
7473 comparison_const_width
7474 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7476 comparison_const_width
7477 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7478 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7479 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7480 comparison_sign_mask
7481 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7483 /* If the comparison value is not a loop invariant, then we
7484 can not reverse this loop.
7486 ??? If the insns which initialize the comparison value as
7487 a whole compute an invariant result, then we could move
7488 them out of the loop and proceed with loop reversal. */
7489 if (! loop_invariant_p (loop, comparison_value))
7492 if (GET_CODE (comparison_value) == CONST_INT)
7493 comparison_val = INTVAL (comparison_value);
7494 initial_value = bl->initial_value;
7496 /* Normalize the initial value if it is an integer and
7497 has no other use except as a counter. This will allow
7498 a few more loops to be reversed. */
7499 if (no_use_except_counting
7500 && GET_CODE (comparison_value) == CONST_INT
7501 && GET_CODE (initial_value) == CONST_INT)
7503 comparison_val = comparison_val - INTVAL (bl->initial_value);
7504 /* The code below requires comparison_val to be a multiple
7505 of add_val in order to do the loop reversal, so
7506 round up comparison_val to a multiple of add_val.
7507 Since comparison_value is constant, we know that the
7508 current comparison code is LT. */
7509 comparison_val = comparison_val + add_val - 1;
7511 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7512 /* We postpone overflow checks for COMPARISON_VAL here;
7513 even if there is an overflow, we might still be able to
7514 reverse the loop, if converting the loop exit test to
7516 initial_value = const0_rtx;
7519 /* First check if we can do a vanilla loop reversal. */
7520 if (initial_value == const0_rtx
7521 /* If we have a decrement_and_branch_on_count,
7522 prefer the NE test, since this will allow that
7523 instruction to be generated. Note that we must
7524 use a vanilla loop reversal if the biv is used to
7525 calculate a giv or has a non-counting use. */
7526 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7527 && defined (HAVE_decrement_and_branch_on_count)
7528 && (! (add_val == 1 && loop->vtop
7529 && (bl->biv_count == 0
7530 || no_use_except_counting)))
7532 && GET_CODE (comparison_value) == CONST_INT
7533 /* Now do postponed overflow checks on COMPARISON_VAL. */
7534 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7535 & comparison_sign_mask))
7537 /* Register will always be nonnegative, with value
7538 0 on last iteration */
7539 add_adjust = add_val;
7543 else if (add_val == 1 && loop->vtop
7544 && (bl->biv_count == 0
7545 || no_use_except_counting))
7553 if (GET_CODE (comparison) == LE)
7554 add_adjust -= add_val;
7556 /* If the initial value is not zero, or if the comparison
7557 value is not an exact multiple of the increment, then we
7558 can not reverse this loop. */
7559 if (initial_value == const0_rtx
7560 && GET_CODE (comparison_value) == CONST_INT)
7562 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7567 if (! no_use_except_counting || add_val != 1)
7571 final_value = comparison_value;
7573 /* Reset these in case we normalized the initial value
7574 and comparison value above. */
7575 if (GET_CODE (comparison_value) == CONST_INT
7576 && GET_CODE (initial_value) == CONST_INT)
7578 comparison_value = GEN_INT (comparison_val);
7580 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7582 bl->initial_value = initial_value;
7584 /* Save some info needed to produce the new insns. */
7585 reg = bl->biv->dest_reg;
7586 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7587 if (jump_label == pc_rtx)
7588 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7589 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7591 /* Set start_value; if this is not a CONST_INT, we need
7593 Initialize biv to start_value before loop start.
7594 The old initializing insn will be deleted as a
7595 dead store by flow.c. */
7596 if (initial_value == const0_rtx
7597 && GET_CODE (comparison_value) == CONST_INT)
7599 start_value = GEN_INT (comparison_val - add_adjust);
7600 emit_insn_before (gen_move_insn (reg, start_value),
7603 else if (GET_CODE (initial_value) == CONST_INT)
7605 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7606 enum machine_mode mode = GET_MODE (reg);
7607 enum insn_code icode
7608 = add_optab->handlers[(int) mode].insn_code;
7610 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7611 || ! ((*insn_data[icode].operand[1].predicate)
7612 (comparison_value, mode))
7613 || ! ((*insn_data[icode].operand[2].predicate)
7617 = gen_rtx_PLUS (mode, comparison_value, offset);
7618 emit_insn_before ((GEN_FCN (icode)
7619 (reg, comparison_value, offset)),
7621 if (GET_CODE (comparison) == LE)
7622 final_value = gen_rtx_PLUS (mode, comparison_value,
7625 else if (! add_adjust)
7627 enum machine_mode mode = GET_MODE (reg);
7628 enum insn_code icode
7629 = sub_optab->handlers[(int) mode].insn_code;
7630 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7631 || ! ((*insn_data[icode].operand[1].predicate)
7632 (comparison_value, mode))
7633 || ! ((*insn_data[icode].operand[2].predicate)
7634 (initial_value, mode)))
7637 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7638 emit_insn_before ((GEN_FCN (icode)
7639 (reg, comparison_value, initial_value)),
7643 /* We could handle the other cases too, but it'll be
7644 better to have a testcase first. */
7647 /* We may not have a single insn which can increment a reg, so
7648 create a sequence to hold all the insns from expand_inc. */
7650 expand_inc (reg, new_add_val);
7651 tem = gen_sequence ();
7654 p = emit_insn_before (tem, bl->biv->insn);
7655 delete_insn (bl->biv->insn);
7657 /* Update biv info to reflect its new status. */
7659 bl->initial_value = start_value;
7660 bl->biv->add_val = new_add_val;
7662 /* Update loop info. */
7663 loop_info->initial_value = reg;
7664 loop_info->initial_equiv_value = reg;
7665 loop_info->final_value = const0_rtx;
7666 loop_info->final_equiv_value = const0_rtx;
7667 loop_info->comparison_value = const0_rtx;
7668 loop_info->comparison_code = cmp_code;
7669 loop_info->increment = new_add_val;
7671 /* Inc LABEL_NUSES so that delete_insn will
7672 not delete the label. */
7673 LABEL_NUSES (XEXP (jump_label, 0))++;
7675 /* Emit an insn after the end of the loop to set the biv's
7676 proper exit value if it is used anywhere outside the loop. */
7677 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7679 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7680 emit_insn_after (gen_move_insn (reg, final_value),
7683 /* Delete compare/branch at end of loop. */
7684 delete_insn (PREV_INSN (loop_end));
7685 if (compare_and_branch == 2)
7686 delete_insn (first_compare);
7688 /* Add new compare/branch insn at end of loop. */
7690 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7691 GET_MODE (reg), 0, 0,
7692 XEXP (jump_label, 0));
7693 tem = gen_sequence ();
7695 emit_jump_insn_before (tem, loop_end);
7697 for (tem = PREV_INSN (loop_end);
7698 tem && GET_CODE (tem) != JUMP_INSN;
7699 tem = PREV_INSN (tem))
7703 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7709 /* Increment of LABEL_NUSES done above. */
7710 /* Register is now always nonnegative,
7711 so add REG_NONNEG note to the branch. */
7712 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7718 /* No insn may reference both the reversed and another biv or it
7719 will fail (see comment near the top of the loop reversal
7721 Earlier on, we have verified that the biv has no use except
7722 counting, or it is the only biv in this function.
7723 However, the code that computes no_use_except_counting does
7724 not verify reg notes. It's possible to have an insn that
7725 references another biv, and has a REG_EQUAL note with an
7726 expression based on the reversed biv. To avoid this case,
7727 remove all REG_EQUAL notes based on the reversed biv
7729 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7733 rtx set = single_set (p);
7734 /* If this is a set of a GIV based on the reversed biv, any
7735 REG_EQUAL notes should still be correct. */
7737 || GET_CODE (SET_DEST (set)) != REG
7738 || (size_t) REGNO (SET_DEST (set)) >= ivs->reg_iv_type->num_elements
7739 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7740 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7741 for (pnote = ®_NOTES (p); *pnote;)
7743 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7744 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7746 *pnote = XEXP (*pnote, 1);
7748 pnote = &XEXP (*pnote, 1);
7752 /* Mark that this biv has been reversed. Each giv which depends
7753 on this biv, and which is also live past the end of the loop
7754 will have to be fixed up. */
7758 if (loop_dump_stream)
7760 fprintf (loop_dump_stream, "Reversed loop");
7762 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7764 fprintf (loop_dump_stream, "\n");
7775 /* Verify whether the biv BL appears to be eliminable,
7776 based on the insns in the loop that refer to it.
7778 If ELIMINATE_P is non-zero, actually do the elimination.
7780 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7781 determine whether invariant insns should be placed inside or at the
7782 start of the loop. */
7785 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7786 const struct loop *loop;
7787 struct iv_class *bl;
7789 int threshold, insn_count;
7791 struct loop_ivs *ivs = LOOP_IVS (loop);
7792 rtx reg = bl->biv->dest_reg;
7793 rtx loop_start = loop->start;
7794 rtx loop_end = loop->end;
7797 /* Scan all insns in the loop, stopping if we find one that uses the
7798 biv in a way that we cannot eliminate. */
7800 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7802 enum rtx_code code = GET_CODE (p);
7803 rtx where = threshold >= insn_count ? loop_start : p;
7805 /* If this is a libcall that sets a giv, skip ahead to its end. */
7806 if (GET_RTX_CLASS (code) == 'i')
7808 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7812 rtx last = XEXP (note, 0);
7813 rtx set = single_set (last);
7815 if (set && GET_CODE (SET_DEST (set)) == REG)
7817 unsigned int regno = REGNO (SET_DEST (set));
7819 if (regno < max_reg_before_loop
7820 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7821 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7826 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7827 && reg_mentioned_p (reg, PATTERN (p))
7828 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7829 eliminate_p, where))
7831 if (loop_dump_stream)
7832 fprintf (loop_dump_stream,
7833 "Cannot eliminate biv %d: biv used in insn %d.\n",
7834 bl->regno, INSN_UID (p));
7841 if (loop_dump_stream)
7842 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7843 bl->regno, eliminate_p ? "was" : "can be");
7850 /* INSN and REFERENCE are instructions in the same insn chain.
7851 Return non-zero if INSN is first. */
7854 loop_insn_first_p (insn, reference)
7855 rtx insn, reference;
7859 for (p = insn, q = reference;;)
7861 /* Start with test for not first so that INSN == REFERENCE yields not
7863 if (q == insn || ! p)
7865 if (p == reference || ! q)
7868 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7869 previous insn, hence the <= comparison below does not work if
7871 if (INSN_UID (p) < max_uid_for_loop
7872 && INSN_UID (q) < max_uid_for_loop
7873 && GET_CODE (p) != NOTE)
7874 return INSN_LUID (p) <= INSN_LUID (q);
7876 if (INSN_UID (p) >= max_uid_for_loop
7877 || GET_CODE (p) == NOTE)
7879 if (INSN_UID (q) >= max_uid_for_loop)
7884 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7885 the offset that we have to take into account due to auto-increment /
7886 div derivation is zero. */
7888 biv_elimination_giv_has_0_offset (biv, giv, insn)
7889 struct induction *biv, *giv;
7892 /* If the giv V had the auto-inc address optimization applied
7893 to it, and INSN occurs between the giv insn and the biv
7894 insn, then we'd have to adjust the value used here.
7895 This is rare, so we don't bother to make this possible. */
7896 if (giv->auto_inc_opt
7897 && ((loop_insn_first_p (giv->insn, insn)
7898 && loop_insn_first_p (insn, biv->insn))
7899 || (loop_insn_first_p (biv->insn, insn)
7900 && loop_insn_first_p (insn, giv->insn))))
7906 /* If BL appears in X (part of the pattern of INSN), see if we can
7907 eliminate its use. If so, return 1. If not, return 0.
7909 If BIV does not appear in X, return 1.
7911 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7912 where extra insns should be added. Depending on how many items have been
7913 moved out of the loop, it will either be before INSN or at the start of
7917 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7918 const struct loop *loop;
7920 struct iv_class *bl;
7924 enum rtx_code code = GET_CODE (x);
7925 rtx reg = bl->biv->dest_reg;
7926 enum machine_mode mode = GET_MODE (reg);
7927 struct induction *v;
7939 /* If we haven't already been able to do something with this BIV,
7940 we can't eliminate it. */
7946 /* If this sets the BIV, it is not a problem. */
7947 if (SET_DEST (x) == reg)
7950 /* If this is an insn that defines a giv, it is also ok because
7951 it will go away when the giv is reduced. */
7952 for (v = bl->giv; v; v = v->next_iv)
7953 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7957 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7959 /* Can replace with any giv that was reduced and
7960 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7961 Require a constant for MULT_VAL, so we know it's nonzero.
7962 ??? We disable this optimization to avoid potential
7965 for (v = bl->giv; v; v = v->next_iv)
7966 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7967 && v->add_val == const0_rtx
7968 && ! v->ignore && ! v->maybe_dead && v->always_computable
7972 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7978 /* If the giv has the opposite direction of change,
7979 then reverse the comparison. */
7980 if (INTVAL (v->mult_val) < 0)
7981 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7982 const0_rtx, v->new_reg);
7986 /* We can probably test that giv's reduced reg. */
7987 if (validate_change (insn, &SET_SRC (x), new, 0))
7991 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7992 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7993 Require a constant for MULT_VAL, so we know it's nonzero.
7994 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7995 overflow problem. */
7997 for (v = bl->giv; v; v = v->next_iv)
7998 if (GET_CODE (v->mult_val) == CONST_INT
7999 && v->mult_val != const0_rtx
8000 && ! v->ignore && ! v->maybe_dead && v->always_computable
8002 && (GET_CODE (v->add_val) == SYMBOL_REF
8003 || GET_CODE (v->add_val) == LABEL_REF
8004 || GET_CODE (v->add_val) == CONST
8005 || (GET_CODE (v->add_val) == REG
8006 && REG_POINTER (v->add_val))))
8008 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8014 /* If the giv has the opposite direction of change,
8015 then reverse the comparison. */
8016 if (INTVAL (v->mult_val) < 0)
8017 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
8020 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
8021 copy_rtx (v->add_val));
8023 /* Replace biv with the giv's reduced register. */
8024 update_reg_last_use (v->add_val, insn);
8025 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8028 /* Insn doesn't support that constant or invariant. Copy it
8029 into a register (it will be a loop invariant.) */
8030 tem = gen_reg_rtx (GET_MODE (v->new_reg));
8032 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
8035 /* Substitute the new register for its invariant value in
8036 the compare expression. */
8037 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
8038 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8047 case GT: case GE: case GTU: case GEU:
8048 case LT: case LE: case LTU: case LEU:
8049 /* See if either argument is the biv. */
8050 if (XEXP (x, 0) == reg)
8051 arg = XEXP (x, 1), arg_operand = 1;
8052 else if (XEXP (x, 1) == reg)
8053 arg = XEXP (x, 0), arg_operand = 0;
8057 if (CONSTANT_P (arg))
8059 /* First try to replace with any giv that has constant positive
8060 mult_val and constant add_val. We might be able to support
8061 negative mult_val, but it seems complex to do it in general. */
8063 for (v = bl->giv; v; v = v->next_iv)
8064 if (GET_CODE (v->mult_val) == CONST_INT
8065 && INTVAL (v->mult_val) > 0
8066 && (GET_CODE (v->add_val) == SYMBOL_REF
8067 || GET_CODE (v->add_val) == LABEL_REF
8068 || GET_CODE (v->add_val) == CONST
8069 || (GET_CODE (v->add_val) == REG
8070 && REG_POINTER (v->add_val)))
8071 && ! v->ignore && ! v->maybe_dead && v->always_computable
8074 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8080 /* Replace biv with the giv's reduced reg. */
8081 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
8083 /* If all constants are actually constant integers and
8084 the derived constant can be directly placed in the COMPARE,
8086 if (GET_CODE (arg) == CONST_INT
8087 && GET_CODE (v->mult_val) == CONST_INT
8088 && GET_CODE (v->add_val) == CONST_INT)
8090 validate_change (insn, &XEXP (x, arg_operand),
8091 GEN_INT (INTVAL (arg)
8092 * INTVAL (v->mult_val)
8093 + INTVAL (v->add_val)), 1);
8097 /* Otherwise, load it into a register. */
8098 tem = gen_reg_rtx (mode);
8099 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8100 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8102 if (apply_change_group ())
8106 /* Look for giv with positive constant mult_val and nonconst add_val.
8107 Insert insns to calculate new compare value.
8108 ??? Turn this off due to possible overflow. */
8110 for (v = bl->giv; v; v = v->next_iv)
8111 if (GET_CODE (v->mult_val) == CONST_INT
8112 && INTVAL (v->mult_val) > 0
8113 && ! v->ignore && ! v->maybe_dead && v->always_computable
8119 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8125 tem = gen_reg_rtx (mode);
8127 /* Replace biv with giv's reduced register. */
8128 validate_change (insn, &XEXP (x, 1 - arg_operand),
8131 /* Compute value to compare against. */
8132 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8133 /* Use it in this insn. */
8134 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8135 if (apply_change_group ())
8139 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
8141 if (loop_invariant_p (loop, arg) == 1)
8143 /* Look for giv with constant positive mult_val and nonconst
8144 add_val. Insert insns to compute new compare value.
8145 ??? Turn this off due to possible overflow. */
8147 for (v = bl->giv; v; v = v->next_iv)
8148 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
8149 && ! v->ignore && ! v->maybe_dead && v->always_computable
8155 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8161 tem = gen_reg_rtx (mode);
8163 /* Replace biv with giv's reduced register. */
8164 validate_change (insn, &XEXP (x, 1 - arg_operand),
8167 /* Compute value to compare against. */
8168 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8170 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8171 if (apply_change_group ())
8176 /* This code has problems. Basically, you can't know when
8177 seeing if we will eliminate BL, whether a particular giv
8178 of ARG will be reduced. If it isn't going to be reduced,
8179 we can't eliminate BL. We can try forcing it to be reduced,
8180 but that can generate poor code.
8182 The problem is that the benefit of reducing TV, below should
8183 be increased if BL can actually be eliminated, but this means
8184 we might have to do a topological sort of the order in which
8185 we try to process biv. It doesn't seem worthwhile to do
8186 this sort of thing now. */
8189 /* Otherwise the reg compared with had better be a biv. */
8190 if (GET_CODE (arg) != REG
8191 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8194 /* Look for a pair of givs, one for each biv,
8195 with identical coefficients. */
8196 for (v = bl->giv; v; v = v->next_iv)
8198 struct induction *tv;
8200 if (v->ignore || v->maybe_dead || v->mode != mode)
8203 for (tv = ivs->reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
8204 if (! tv->ignore && ! tv->maybe_dead
8205 && rtx_equal_p (tv->mult_val, v->mult_val)
8206 && rtx_equal_p (tv->add_val, v->add_val)
8207 && tv->mode == mode)
8209 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8215 /* Replace biv with its giv's reduced reg. */
8216 XEXP (x, 1 - arg_operand) = v->new_reg;
8217 /* Replace other operand with the other giv's
8219 XEXP (x, arg_operand) = tv->new_reg;
8226 /* If we get here, the biv can't be eliminated. */
8230 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8231 biv is used in it, since it will be replaced. */
8232 for (v = bl->giv; v; v = v->next_iv)
8233 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8241 /* See if any subexpression fails elimination. */
8242 fmt = GET_RTX_FORMAT (code);
8243 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8248 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8249 eliminate_p, where))
8254 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8255 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8256 eliminate_p, where))
8265 /* Return nonzero if the last use of REG
8266 is in an insn following INSN in the same basic block. */
8269 last_use_this_basic_block (reg, insn)
8275 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8278 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8284 /* Called via `note_stores' to record the initial value of a biv. Here we
8285 just record the location of the set and process it later. */
8288 record_initial (dest, set, data)
8291 void *data ATTRIBUTE_UNUSED;
8293 struct loop_ivs *ivs = (struct loop_ivs *) data;
8294 struct iv_class *bl;
8296 if (GET_CODE (dest) != REG
8297 || REGNO (dest) >= max_reg_before_loop
8298 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8301 bl = ivs->reg_biv_class[REGNO (dest)];
8303 /* If this is the first set found, record it. */
8304 if (bl->init_insn == 0)
8306 bl->init_insn = note_insn;
8311 /* If any of the registers in X are "old" and currently have a last use earlier
8312 than INSN, update them to have a last use of INSN. Their actual last use
8313 will be the previous insn but it will not have a valid uid_luid so we can't
8317 update_reg_last_use (x, insn)
8321 /* Check for the case where INSN does not have a valid luid. In this case,
8322 there is no need to modify the regno_last_uid, as this can only happen
8323 when code is inserted after the loop_end to set a pseudo's final value,
8324 and hence this insn will never be the last use of x. */
8325 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8326 && INSN_UID (insn) < max_uid_for_loop
8327 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8328 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8332 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8333 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8336 update_reg_last_use (XEXP (x, i), insn);
8337 else if (fmt[i] == 'E')
8338 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8339 update_reg_last_use (XVECEXP (x, i, j), insn);
8344 /* Given an insn INSN and condition COND, return the condition in a
8345 canonical form to simplify testing by callers. Specifically:
8347 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8348 (2) Both operands will be machine operands; (cc0) will have been replaced.
8349 (3) If an operand is a constant, it will be the second operand.
8350 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8351 for GE, GEU, and LEU.
8353 If the condition cannot be understood, or is an inequality floating-point
8354 comparison which needs to be reversed, 0 will be returned.
8356 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8358 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8359 insn used in locating the condition was found. If a replacement test
8360 of the condition is desired, it should be placed in front of that
8361 insn and we will be sure that the inputs are still valid.
8363 If WANT_REG is non-zero, we wish the condition to be relative to that
8364 register, if possible. Therefore, do not canonicalize the condition
8368 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8380 int reverse_code = 0;
8381 int did_reverse_condition = 0;
8382 enum machine_mode mode;
8384 code = GET_CODE (cond);
8385 mode = GET_MODE (cond);
8386 op0 = XEXP (cond, 0);
8387 op1 = XEXP (cond, 1);
8391 code = reverse_condition (code);
8392 did_reverse_condition ^= 1;
8398 /* If we are comparing a register with zero, see if the register is set
8399 in the previous insn to a COMPARE or a comparison operation. Perform
8400 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8403 while (GET_RTX_CLASS (code) == '<'
8404 && op1 == CONST0_RTX (GET_MODE (op0))
8407 /* Set non-zero when we find something of interest. */
8411 /* If comparison with cc0, import actual comparison from compare
8415 if ((prev = prev_nonnote_insn (prev)) == 0
8416 || GET_CODE (prev) != INSN
8417 || (set = single_set (prev)) == 0
8418 || SET_DEST (set) != cc0_rtx)
8421 op0 = SET_SRC (set);
8422 op1 = CONST0_RTX (GET_MODE (op0));
8428 /* If this is a COMPARE, pick up the two things being compared. */
8429 if (GET_CODE (op0) == COMPARE)
8431 op1 = XEXP (op0, 1);
8432 op0 = XEXP (op0, 0);
8435 else if (GET_CODE (op0) != REG)
8438 /* Go back to the previous insn. Stop if it is not an INSN. We also
8439 stop if it isn't a single set or if it has a REG_INC note because
8440 we don't want to bother dealing with it. */
8442 if ((prev = prev_nonnote_insn (prev)) == 0
8443 || GET_CODE (prev) != INSN
8444 || FIND_REG_INC_NOTE (prev, 0)
8445 || (set = single_set (prev)) == 0)
8448 /* If this is setting OP0, get what it sets it to if it looks
8450 if (rtx_equal_p (SET_DEST (set), op0))
8452 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8454 /* ??? We may not combine comparisons done in a CCmode with
8455 comparisons not done in a CCmode. This is to aid targets
8456 like Alpha that have an IEEE compliant EQ instruction, and
8457 a non-IEEE compliant BEQ instruction. The use of CCmode is
8458 actually artificial, simply to prevent the combination, but
8459 should not affect other platforms.
8461 However, we must allow VOIDmode comparisons to match either
8462 CCmode or non-CCmode comparison, because some ports have
8463 modeless comparisons inside branch patterns.
8465 ??? This mode check should perhaps look more like the mode check
8466 in simplify_comparison in combine. */
8468 if ((GET_CODE (SET_SRC (set)) == COMPARE
8471 && GET_MODE_CLASS (inner_mode) == MODE_INT
8472 && (GET_MODE_BITSIZE (inner_mode)
8473 <= HOST_BITS_PER_WIDE_INT)
8474 && (STORE_FLAG_VALUE
8475 & ((HOST_WIDE_INT) 1
8476 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8477 #ifdef FLOAT_STORE_FLAG_VALUE
8479 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8480 && (REAL_VALUE_NEGATIVE
8481 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8484 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8485 && (((GET_MODE_CLASS (mode) == MODE_CC)
8486 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8487 || mode == VOIDmode || inner_mode == VOIDmode))
8489 else if (((code == EQ
8491 && (GET_MODE_BITSIZE (inner_mode)
8492 <= HOST_BITS_PER_WIDE_INT)
8493 && GET_MODE_CLASS (inner_mode) == MODE_INT
8494 && (STORE_FLAG_VALUE
8495 & ((HOST_WIDE_INT) 1
8496 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8497 #ifdef FLOAT_STORE_FLAG_VALUE
8499 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8500 && (REAL_VALUE_NEGATIVE
8501 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8504 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8505 && (((GET_MODE_CLASS (mode) == MODE_CC)
8506 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8507 || mode == VOIDmode || inner_mode == VOIDmode))
8510 /* We might have reversed a LT to get a GE here. But this wasn't
8511 actually the comparison of data, so we don't flag that we
8512 have had to reverse the condition. */
8513 did_reverse_condition ^= 1;
8521 else if (reg_set_p (op0, prev))
8522 /* If this sets OP0, but not directly, we have to give up. */
8527 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8528 code = GET_CODE (x);
8531 code = reverse_condition (code);
8532 if (code == UNKNOWN)
8534 did_reverse_condition ^= 1;
8538 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8544 /* If constant is first, put it last. */
8545 if (CONSTANT_P (op0))
8546 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8548 /* If OP0 is the result of a comparison, we weren't able to find what
8549 was really being compared, so fail. */
8550 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8553 /* Canonicalize any ordered comparison with integers involving equality
8554 if we can do computations in the relevant mode and we do not
8557 if (GET_CODE (op1) == CONST_INT
8558 && GET_MODE (op0) != VOIDmode
8559 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8561 HOST_WIDE_INT const_val = INTVAL (op1);
8562 unsigned HOST_WIDE_INT uconst_val = const_val;
8563 unsigned HOST_WIDE_INT max_val
8564 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8569 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8570 code = LT, op1 = GEN_INT (const_val + 1);
8573 /* When cross-compiling, const_val might be sign-extended from
8574 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8576 if ((HOST_WIDE_INT) (const_val & max_val)
8577 != (((HOST_WIDE_INT) 1
8578 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8579 code = GT, op1 = GEN_INT (const_val - 1);
8583 if (uconst_val < max_val)
8584 code = LTU, op1 = GEN_INT (uconst_val + 1);
8588 if (uconst_val != 0)
8589 code = GTU, op1 = GEN_INT (uconst_val - 1);
8597 /* If this was floating-point and we reversed anything other than an
8598 EQ or NE or (UN)ORDERED, return zero. */
8599 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8600 && did_reverse_condition
8601 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8603 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8607 /* Never return CC0; return zero instead. */
8612 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8615 /* Given a jump insn JUMP, return the condition that will cause it to branch
8616 to its JUMP_LABEL. If the condition cannot be understood, or is an
8617 inequality floating-point comparison which needs to be reversed, 0 will
8620 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8621 insn used in locating the condition was found. If a replacement test
8622 of the condition is desired, it should be placed in front of that
8623 insn and we will be sure that the inputs are still valid. */
8626 get_condition (jump, earliest)
8634 /* If this is not a standard conditional jump, we can't parse it. */
8635 if (GET_CODE (jump) != JUMP_INSN
8636 || ! any_condjump_p (jump))
8638 set = pc_set (jump);
8640 cond = XEXP (SET_SRC (set), 0);
8642 /* If this branches to JUMP_LABEL when the condition is false, reverse
8645 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8646 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8648 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8651 /* Similar to above routine, except that we also put an invariant last
8652 unless both operands are invariants. */
8655 get_condition_for_loop (loop, x)
8656 const struct loop *loop;
8659 rtx comparison = get_condition (x, NULL_PTR);
8662 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8663 || loop_invariant_p (loop, XEXP (comparison, 1)))
8666 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8667 XEXP (comparison, 1), XEXP (comparison, 0));
8670 /* Scan the function and determine whether it has indirect (computed) jumps.
8672 This is taken mostly from flow.c; similar code exists elsewhere
8673 in the compiler. It may be useful to put this into rtlanal.c. */
8675 indirect_jump_in_function_p (start)
8680 for (insn = start; insn; insn = NEXT_INSN (insn))
8681 if (computed_jump_p (insn))
8687 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8688 documentation for LOOP_MEMS for the definition of `appropriate'.
8689 This function is called from prescan_loop via for_each_rtx. */
8692 insert_loop_mem (mem, data)
8694 void *data ATTRIBUTE_UNUSED;
8696 struct loop_info *loop_info = data;
8703 switch (GET_CODE (m))
8709 /* We're not interested in MEMs that are only clobbered. */
8713 /* We're not interested in the MEM associated with a
8714 CONST_DOUBLE, so there's no need to traverse into this. */
8718 /* We're not interested in any MEMs that only appear in notes. */
8722 /* This is not a MEM. */
8726 /* See if we've already seen this MEM. */
8727 for (i = 0; i < loop_info->mems_idx; ++i)
8728 if (rtx_equal_p (m, loop_info->mems[i].mem))
8730 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8731 /* The modes of the two memory accesses are different. If
8732 this happens, something tricky is going on, and we just
8733 don't optimize accesses to this MEM. */
8734 loop_info->mems[i].optimize = 0;
8739 /* Resize the array, if necessary. */
8740 if (loop_info->mems_idx == loop_info->mems_allocated)
8742 if (loop_info->mems_allocated != 0)
8743 loop_info->mems_allocated *= 2;
8745 loop_info->mems_allocated = 32;
8747 loop_info->mems = (loop_mem_info *)
8748 xrealloc (loop_info->mems,
8749 loop_info->mems_allocated * sizeof (loop_mem_info));
8752 /* Actually insert the MEM. */
8753 loop_info->mems[loop_info->mems_idx].mem = m;
8754 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8755 because we can't put it in a register. We still store it in the
8756 table, though, so that if we see the same address later, but in a
8757 non-BLK mode, we'll not think we can optimize it at that point. */
8758 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8759 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8760 ++loop_info->mems_idx;
8765 /* Like load_mems, but also ensures that REGS->SET_IN_LOOP,
8766 REGS->MAY_NOT_OPTIMIZE, REGS->SINGLE_USAGE, and INSN_COUNT have the correct
8767 values after load_mems. */
8770 load_mems_and_recount_loop_regs_set (loop, insn_count)
8771 const struct loop *loop;
8774 struct loop_regs *regs = LOOP_REGS (loop);
8775 int nregs = max_reg_num ();
8779 /* Recalculate regs->set_in_loop and friends since load_mems may have
8780 created new registers. */
8781 if (max_reg_num () > nregs)
8787 nregs = max_reg_num ();
8789 if ((unsigned) nregs > regs->set_in_loop->num_elements)
8791 /* Grow all the arrays. */
8792 VARRAY_GROW (regs->set_in_loop, nregs);
8793 VARRAY_GROW (regs->n_times_set, nregs);
8794 VARRAY_GROW (regs->may_not_optimize, nregs);
8795 VARRAY_GROW (regs->single_usage, nregs);
8797 /* Clear the arrays */
8798 memset ((char *) ®s->set_in_loop->data, 0, nregs * sizeof (int));
8799 memset ((char *) ®s->may_not_optimize->data, 0, nregs * sizeof (char));
8800 memset ((char *) ®s->single_usage->data, 0, nregs * sizeof (rtx));
8802 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
8805 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8807 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8808 VARRAY_INT (regs->set_in_loop, i) = 1;
8811 #ifdef AVOID_CCMODE_COPIES
8812 /* Don't try to move insns which set CC registers if we should not
8813 create CCmode register copies. */
8814 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8815 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8816 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8819 /* Set regs->n_times_set for the new registers. */
8820 bcopy ((char *) (®s->set_in_loop->data.i[0] + old_nregs),
8821 (char *) (®s->n_times_set->data.i[0] + old_nregs),
8822 (nregs - old_nregs) * sizeof (int));
8826 /* Move MEMs into registers for the duration of the loop. */
8830 const struct loop *loop;
8832 struct loop_info *loop_info = LOOP_INFO (loop);
8833 struct loop_regs *regs = LOOP_REGS (loop);
8834 int maybe_never = 0;
8837 rtx label = NULL_RTX;
8839 /* Nonzero if the next instruction may never be executed. */
8840 int next_maybe_never = 0;
8841 int last_max_reg = max_reg_num ();
8843 if (loop_info->mems_idx == 0)
8846 /* We cannot use next_label here because it skips over normal insns. */
8847 end_label = next_nonnote_insn (loop->end);
8848 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8849 end_label = NULL_RTX;
8851 /* Check to see if it's possible that some instructions in the loop are
8852 never executed. Also check if there is a goto out of the loop other
8853 than right after the end of the loop. */
8854 for (p = next_insn_in_loop (loop, loop->scan_start);
8855 p != NULL_RTX && ! maybe_never;
8856 p = next_insn_in_loop (loop, p))
8858 if (GET_CODE (p) == CODE_LABEL)
8860 else if (GET_CODE (p) == JUMP_INSN
8861 /* If we enter the loop in the middle, and scan
8862 around to the beginning, don't set maybe_never
8863 for that. This must be an unconditional jump,
8864 otherwise the code at the top of the loop might
8865 never be executed. Unconditional jumps are
8866 followed a by barrier then loop end. */
8867 && ! (GET_CODE (p) == JUMP_INSN
8868 && JUMP_LABEL (p) == loop->top
8869 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8870 && any_uncondjump_p (p)))
8872 /* If this is a jump outside of the loop but not right
8873 after the end of the loop, we would have to emit new fixup
8874 sequences for each such label. */
8875 if (JUMP_LABEL (p) != end_label
8876 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8877 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8878 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8881 if (!any_condjump_p (p))
8882 /* Something complicated. */
8885 /* If there are any more instructions in the loop, they
8886 might not be reached. */
8887 next_maybe_never = 1;
8889 else if (next_maybe_never)
8893 /* Find start of the extended basic block that enters the loop. */
8894 for (p = loop->start;
8895 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8901 /* Build table of mems that get set to constant values before the
8903 for (; p != loop->start; p = NEXT_INSN (p))
8904 cselib_process_insn (p);
8906 /* Actually move the MEMs. */
8907 for (i = 0; i < loop_info->mems_idx; ++i)
8909 regset_head load_copies;
8910 regset_head store_copies;
8913 rtx mem = loop_info->mems[i].mem;
8916 if (MEM_VOLATILE_P (mem)
8917 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8918 /* There's no telling whether or not MEM is modified. */
8919 loop_info->mems[i].optimize = 0;
8921 /* Go through the MEMs written to in the loop to see if this
8922 one is aliased by one of them. */
8923 mem_list_entry = loop_info->store_mems;
8924 while (mem_list_entry)
8926 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8928 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8931 /* MEM is indeed aliased by this store. */
8932 loop_info->mems[i].optimize = 0;
8935 mem_list_entry = XEXP (mem_list_entry, 1);
8938 if (flag_float_store && written
8939 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8940 loop_info->mems[i].optimize = 0;
8942 /* If this MEM is written to, we must be sure that there
8943 are no reads from another MEM that aliases this one. */
8944 if (loop_info->mems[i].optimize && written)
8948 for (j = 0; j < loop_info->mems_idx; ++j)
8952 else if (true_dependence (mem,
8954 loop_info->mems[j].mem,
8957 /* It's not safe to hoist loop_info->mems[i] out of
8958 the loop because writes to it might not be
8959 seen by reads from loop_info->mems[j]. */
8960 loop_info->mems[i].optimize = 0;
8966 if (maybe_never && may_trap_p (mem))
8967 /* We can't access the MEM outside the loop; it might
8968 cause a trap that wouldn't have happened otherwise. */
8969 loop_info->mems[i].optimize = 0;
8971 if (!loop_info->mems[i].optimize)
8972 /* We thought we were going to lift this MEM out of the
8973 loop, but later discovered that we could not. */
8976 INIT_REG_SET (&load_copies);
8977 INIT_REG_SET (&store_copies);
8979 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8980 order to keep scan_loop from moving stores to this MEM
8981 out of the loop just because this REG is neither a
8982 user-variable nor used in the loop test. */
8983 reg = gen_reg_rtx (GET_MODE (mem));
8984 REG_USERVAR_P (reg) = 1;
8985 loop_info->mems[i].reg = reg;
8987 /* Now, replace all references to the MEM with the
8988 corresponding pesudos. */
8990 for (p = next_insn_in_loop (loop, loop->scan_start);
8992 p = next_insn_in_loop (loop, p))
8998 set = single_set (p);
9000 /* See if this copies the mem into a register that isn't
9001 modified afterwards. We'll try to do copy propagation
9002 a little further on. */
9004 /* @@@ This test is _way_ too conservative. */
9006 && GET_CODE (SET_DEST (set)) == REG
9007 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
9008 && REGNO (SET_DEST (set)) < last_max_reg
9009 && VARRAY_INT (regs->n_times_set,
9010 REGNO (SET_DEST (set))) == 1
9011 && rtx_equal_p (SET_SRC (set), mem))
9012 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
9014 /* See if this copies the mem from a register that isn't
9015 modified afterwards. We'll try to remove the
9016 redundant copy later on by doing a little register
9017 renaming and copy propagation. This will help
9018 to untangle things for the BIV detection code. */
9021 && GET_CODE (SET_SRC (set)) == REG
9022 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
9023 && REGNO (SET_SRC (set)) < last_max_reg
9024 && VARRAY_INT (regs->n_times_set, REGNO (SET_SRC (set))) == 1
9025 && rtx_equal_p (SET_DEST (set), mem))
9026 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
9028 /* Replace the memory reference with the shadow register. */
9029 replace_loop_mems (p, loop_info->mems[i].mem,
9030 loop_info->mems[i].reg);
9033 if (GET_CODE (p) == CODE_LABEL
9034 || GET_CODE (p) == JUMP_INSN)
9038 if (! apply_change_group ())
9039 /* We couldn't replace all occurrences of the MEM. */
9040 loop_info->mems[i].optimize = 0;
9043 /* Load the memory immediately before LOOP->START, which is
9044 the NOTE_LOOP_BEG. */
9045 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
9049 struct elt_loc_list *const_equiv = 0;
9053 struct elt_loc_list *equiv;
9054 struct elt_loc_list *best_equiv = 0;
9055 for (equiv = e->locs; equiv; equiv = equiv->next)
9057 if (CONSTANT_P (equiv->loc))
9058 const_equiv = equiv;
9059 else if (GET_CODE (equiv->loc) == REG
9060 /* Extending hard register lifetimes cuases crash
9061 on SRC targets. Doing so on non-SRC is
9062 probably also not good idea, since we most
9063 probably have pseudoregister equivalence as
9065 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
9068 /* Use the constant equivalence if that is cheap enough. */
9070 best_equiv = const_equiv;
9071 else if (const_equiv
9072 && (rtx_cost (const_equiv->loc, SET)
9073 <= rtx_cost (best_equiv->loc, SET)))
9075 best_equiv = const_equiv;
9079 /* If best_equiv is nonzero, we know that MEM is set to a
9080 constant or register before the loop. We will use this
9081 knowledge to initialize the shadow register with that
9082 constant or reg rather than by loading from MEM. */
9084 best = copy_rtx (best_equiv->loc);
9086 set = gen_move_insn (reg, best);
9087 set = emit_insn_before (set, loop->start);
9089 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
9090 copy_rtx (const_equiv->loc),
9095 if (label == NULL_RTX)
9097 label = gen_label_rtx ();
9098 emit_label_after (label, loop->end);
9101 /* Store the memory immediately after END, which is
9102 the NOTE_LOOP_END. */
9103 set = gen_move_insn (copy_rtx (mem), reg);
9104 emit_insn_after (set, label);
9107 if (loop_dump_stream)
9109 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9110 REGNO (reg), (written ? "r/w" : "r/o"));
9111 print_rtl (loop_dump_stream, mem);
9112 fputc ('\n', loop_dump_stream);
9115 /* Attempt a bit of copy propagation. This helps untangle the
9116 data flow, and enables {basic,general}_induction_var to find
9118 EXECUTE_IF_SET_IN_REG_SET
9119 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9121 try_copy_prop (loop, reg, j);
9123 CLEAR_REG_SET (&load_copies);
9125 EXECUTE_IF_SET_IN_REG_SET
9126 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9128 try_swap_copy_prop (loop, reg, j);
9130 CLEAR_REG_SET (&store_copies);
9134 if (label != NULL_RTX && end_label != NULL_RTX)
9136 /* Now, we need to replace all references to the previous exit
9137 label with the new one. */
9142 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9144 for_each_rtx (&p, replace_label, &rr);
9146 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9147 field. This is not handled by for_each_rtx because it doesn't
9148 handle unprinted ('0') fields. We need to update JUMP_LABEL
9149 because the immediately following unroll pass will use it.
9150 replace_label would not work anyways, because that only handles
9152 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9153 JUMP_LABEL (p) = label;
9160 /* For communication between note_reg_stored and its caller. */
9161 struct note_reg_stored_arg
9167 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9170 note_reg_stored (x, setter, arg)
9171 rtx x, setter ATTRIBUTE_UNUSED;
9174 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9179 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9180 There must be exactly one insn that sets this pseudo; it will be
9181 deleted if all replacements succeed and we can prove that the register
9182 is not used after the loop. */
9185 try_copy_prop (loop, replacement, regno)
9186 const struct loop *loop;
9190 /* This is the reg that we are copying from. */
9191 rtx reg_rtx = regno_reg_rtx[regno];
9194 /* These help keep track of whether we replaced all uses of the reg. */
9195 int replaced_last = 0;
9196 int store_is_first = 0;
9198 for (insn = next_insn_in_loop (loop, loop->scan_start);
9200 insn = next_insn_in_loop (loop, insn))
9204 /* Only substitute within one extended basic block from the initializing
9206 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9209 if (! INSN_P (insn))
9212 /* Is this the initializing insn? */
9213 set = single_set (insn);
9215 && GET_CODE (SET_DEST (set)) == REG
9216 && REGNO (SET_DEST (set)) == regno)
9222 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9226 /* Only substitute after seeing the initializing insn. */
9227 if (init_insn && insn != init_insn)
9229 struct note_reg_stored_arg arg;
9231 replace_loop_regs (insn, reg_rtx, replacement);
9232 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9235 /* Stop replacing when REPLACEMENT is modified. */
9236 arg.reg = replacement;
9238 note_stores (PATTERN (insn), note_reg_stored, &arg);
9245 if (apply_change_group ())
9247 if (loop_dump_stream)
9248 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9249 if (store_is_first && replaced_last)
9251 PUT_CODE (init_insn, NOTE);
9252 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9253 if (loop_dump_stream)
9254 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9255 INSN_UID (init_insn));
9257 if (loop_dump_stream)
9258 fprintf (loop_dump_stream, ".\n");
9262 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9263 loop LOOP if the order of the sets of these registers can be
9264 swapped. There must be exactly one insn within the loop that sets
9265 this pseudo followed immediately by a move insn that sets
9266 REPLACEMENT with REGNO. */
9268 try_swap_copy_prop (loop, replacement, regno)
9269 const struct loop *loop;
9275 unsigned int new_regno;
9277 new_regno = REGNO (replacement);
9279 for (insn = next_insn_in_loop (loop, loop->scan_start);
9281 insn = next_insn_in_loop (loop, insn))
9283 /* Search for the insn that copies REGNO to NEW_REGNO? */
9284 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9285 && (set = single_set (insn))
9286 && GET_CODE (SET_DEST (set)) == REG
9287 && REGNO (SET_DEST (set)) == new_regno
9288 && GET_CODE (SET_SRC (set)) == REG
9289 && REGNO (SET_SRC (set)) == regno)
9293 if (insn != NULL_RTX)
9298 /* Some DEF-USE info would come in handy here to make this
9299 function more general. For now, just check the previous insn
9300 which is the most likely candidate for setting REGNO. */
9302 prev_insn = PREV_INSN (insn);
9304 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9305 && (prev_set = single_set (prev_insn))
9306 && GET_CODE (SET_DEST (prev_set)) == REG
9307 && REGNO (SET_DEST (prev_set)) == regno)
9310 (set (reg regno) (expr))
9311 (set (reg new_regno) (reg regno))
9313 so try converting this to:
9314 (set (reg new_regno) (expr))
9315 (set (reg regno) (reg new_regno))
9317 The former construct is often generated when a global
9318 variable used for an induction variable is shadowed by a
9319 register (NEW_REGNO). The latter construct improves the
9320 chances of GIV replacement and BIV elimination. */
9322 validate_change (prev_insn, &SET_DEST (prev_set),
9324 validate_change (insn, &SET_DEST (set),
9326 validate_change (insn, &SET_SRC (set),
9329 if (apply_change_group ())
9331 if (loop_dump_stream)
9332 fprintf (loop_dump_stream,
9333 " Swapped set of reg %d at %d with reg %d at %d.\n",
9334 regno, INSN_UID (insn),
9335 new_regno, INSN_UID (prev_insn));
9337 /* Update first use of REGNO. */
9338 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9339 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9341 /* Now perform copy propagation to hopefully
9342 remove all uses of REGNO within the loop. */
9343 try_copy_prop (loop, replacement, regno);
9349 /* Replace MEM with its associated pseudo register. This function is
9350 called from load_mems via for_each_rtx. DATA is actually a pointer
9351 to a structure describing the instruction currently being scanned
9352 and the MEM we are currently replacing. */
9355 replace_loop_mem (mem, data)
9359 loop_replace_args *args = (loop_replace_args *) data;
9365 switch (GET_CODE (m))
9371 /* We're not interested in the MEM associated with a
9372 CONST_DOUBLE, so there's no need to traverse into one. */
9376 /* This is not a MEM. */
9380 if (!rtx_equal_p (args->match, m))
9381 /* This is not the MEM we are currently replacing. */
9384 /* Actually replace the MEM. */
9385 validate_change (args->insn, mem, args->replacement, 1);
9391 replace_loop_mems (insn, mem, reg)
9396 loop_replace_args args;
9400 args.replacement = reg;
9402 for_each_rtx (&insn, replace_loop_mem, &args);
9405 /* Replace one register with another. Called through for_each_rtx; PX points
9406 to the rtx being scanned. DATA is actually a pointer to
9407 a structure of arguments. */
9410 replace_loop_reg (px, data)
9415 loop_replace_args *args = (loop_replace_args *) data;
9420 if (x == args->match)
9421 validate_change (args->insn, px, args->replacement, 1);
9427 replace_loop_regs (insn, reg, replacement)
9432 loop_replace_args args;
9436 args.replacement = replacement;
9438 for_each_rtx (&insn, replace_loop_reg, &args);
9441 /* Replace occurrences of the old exit label for the loop with the new
9442 one. DATA is an rtx_pair containing the old and new labels,
9446 replace_label (x, data)
9451 rtx old_label = ((rtx_pair *) data)->r1;
9452 rtx new_label = ((rtx_pair *) data)->r2;
9457 if (GET_CODE (l) != LABEL_REF)
9460 if (XEXP (l, 0) != old_label)
9463 XEXP (l, 0) = new_label;
9464 ++LABEL_NUSES (new_label);
9465 --LABEL_NUSES (old_label);
9470 #define LOOP_BLOCK_NUM_1(INSN) \
9471 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9473 /* The notes do not have an assigned block, so look at the next insn. */
9474 #define LOOP_BLOCK_NUM(INSN) \
9475 ((INSN) ? (GET_CODE (INSN) == NOTE \
9476 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9477 : LOOP_BLOCK_NUM_1 (INSN)) \
9480 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9483 loop_dump_aux (loop, file, verbose)
9484 const struct loop *loop;
9486 int verbose ATTRIBUTE_UNUSED;
9490 if (! loop || ! file)
9493 /* Print diagnostics to compare our concept of a loop with
9494 what the loop notes say. */
9495 if (! PREV_INSN (loop->first->head)
9496 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9497 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9498 != NOTE_INSN_LOOP_BEG)
9499 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9500 INSN_UID (PREV_INSN (loop->first->head)));
9501 if (! NEXT_INSN (loop->last->end)
9502 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9503 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9504 != NOTE_INSN_LOOP_END)
9505 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9506 INSN_UID (NEXT_INSN (loop->last->end)));
9511 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9512 LOOP_BLOCK_NUM (loop->start),
9513 LOOP_INSN_UID (loop->start),
9514 LOOP_BLOCK_NUM (loop->cont),
9515 LOOP_INSN_UID (loop->cont),
9516 LOOP_BLOCK_NUM (loop->cont),
9517 LOOP_INSN_UID (loop->cont),
9518 LOOP_BLOCK_NUM (loop->vtop),
9519 LOOP_INSN_UID (loop->vtop),
9520 LOOP_BLOCK_NUM (loop->end),
9521 LOOP_INSN_UID (loop->end));
9522 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9523 LOOP_BLOCK_NUM (loop->top),
9524 LOOP_INSN_UID (loop->top),
9525 LOOP_BLOCK_NUM (loop->scan_start),
9526 LOOP_INSN_UID (loop->scan_start));
9527 fprintf (file, ";; exit_count %d", loop->exit_count);
9528 if (loop->exit_count)
9530 fputs (", labels:", file);
9531 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9533 fprintf (file, " %d ",
9534 LOOP_INSN_UID (XEXP (label, 0)));
9539 /* This can happen when a marked loop appears as two nested loops,
9540 say from while (a || b) {}. The inner loop won't match
9541 the loop markers but the outer one will. */
9542 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9543 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9547 /* Call this function from the debugger to dump LOOP. */
9551 const struct loop *loop;
9553 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9556 /* Call this function from the debugger to dump LOOPS. */
9560 const struct loops *loops;
9562 flow_loops_dump (loops, stderr, loop_dump_aux, 1);
OSDN Git Service
