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 strength_reduce PARAMS ((struct loop *, int, int));
185 static void find_single_use_in_loop PARAMS ((rtx, rtx, varray_type));
186 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
187 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
188 static void record_biv PARAMS ((struct loop *, struct induction *,
189 rtx, rtx, rtx, rtx, rtx *,
191 static void check_final_value PARAMS ((const struct loop *,
192 struct induction *));
193 static void record_giv PARAMS ((const struct loop *, struct induction *,
194 rtx, rtx, rtx, rtx, rtx, rtx, int,
195 enum g_types, int, int, rtx *));
196 static void update_giv_derive PARAMS ((const struct loop *, rtx));
197 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
198 struct loop_info *));
199 static int basic_induction_var PARAMS ((const struct loop *, rtx,
200 enum machine_mode, rtx, rtx,
201 rtx *, rtx *, rtx **));
202 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
203 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
204 rtx *, rtx *, rtx *, int, int *,
206 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
207 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
208 static int check_dbra_loop PARAMS ((struct loop *, int));
209 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
210 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
211 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
212 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
213 static int product_cheap_p PARAMS ((rtx, rtx));
214 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
216 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
217 struct iv_class *, int, rtx));
218 static int last_use_this_basic_block PARAMS ((rtx, rtx));
219 static void record_initial PARAMS ((rtx, rtx, void *));
220 static void update_reg_last_use PARAMS ((rtx, rtx));
221 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
222 static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
224 static void load_mems PARAMS ((const struct loop *));
225 static int insert_loop_mem PARAMS ((rtx *, void *));
226 static int replace_loop_mem PARAMS ((rtx *, void *));
227 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
228 static int replace_loop_reg PARAMS ((rtx *, void *));
229 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
230 static void note_reg_stored PARAMS ((rtx, rtx, void *));
231 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
232 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
234 static int replace_label PARAMS ((rtx *, void *));
235 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
236 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
237 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
239 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
240 void debug_loop PARAMS ((const struct loop *));
241 void debug_loops PARAMS ((const struct loops *));
243 typedef struct rtx_pair
249 typedef struct loop_replace_args
256 /* Nonzero iff INSN is between START and END, inclusive. */
257 #define INSN_IN_RANGE_P(INSN, START, END) \
258 (INSN_UID (INSN) < max_uid_for_loop \
259 && INSN_LUID (INSN) >= INSN_LUID (START) \
260 && INSN_LUID (INSN) <= INSN_LUID (END))
262 /* Indirect_jump_in_function is computed once per function. */
263 static int indirect_jump_in_function;
264 static int indirect_jump_in_function_p PARAMS ((rtx));
266 static int compute_luids PARAMS ((rtx, rtx, int));
268 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
272 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
273 copy the value of the strength reduced giv to its original register. */
274 static int copy_cost;
276 /* Cost of using a register, to normalize the benefits of a giv. */
277 static int reg_address_cost;
282 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
284 reg_address_cost = address_cost (reg, SImode);
286 copy_cost = COSTS_N_INSNS (1);
289 /* Compute the mapping from uids to luids.
290 LUIDs are numbers assigned to insns, like uids,
291 except that luids increase monotonically through the code.
292 Start at insn START and stop just before END. Assign LUIDs
293 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
295 compute_luids (start, end, prev_luid)
302 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
304 if (INSN_UID (insn) >= max_uid_for_loop)
306 /* Don't assign luids to line-number NOTEs, so that the distance in
307 luids between two insns is not affected by -g. */
308 if (GET_CODE (insn) != NOTE
309 || NOTE_LINE_NUMBER (insn) <= 0)
310 uid_luid[INSN_UID (insn)] = ++i;
312 /* Give a line number note the same luid as preceding insn. */
313 uid_luid[INSN_UID (insn)] = i;
318 /* Entry point of this file. Perform loop optimization
319 on the current function. F is the first insn of the function
320 and DUMPFILE is a stream for output of a trace of actions taken
321 (or 0 if none should be output). */
324 loop_optimize (f, dumpfile, flags)
325 /* f is the first instruction of a chain of insns for one function */
332 struct loops loops_data;
333 struct loops *loops = &loops_data;
334 struct loop_info *loops_info;
335 static char *moved_once;
337 loop_dump_stream = dumpfile;
339 init_recog_no_volatile ();
341 max_reg_before_loop = max_reg_num ();
342 loop_max_reg = max_reg_before_loop;
346 /* Count the number of loops. */
349 for (insn = f; insn; insn = NEXT_INSN (insn))
351 if (GET_CODE (insn) == NOTE
352 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
356 /* Don't waste time if no loops. */
357 if (max_loop_num == 0)
360 loops->num = max_loop_num;
362 moved_once = (char *) xcalloc (max_reg_before_loop, sizeof (char));
364 /* Get size to use for tables indexed by uids.
365 Leave some space for labels allocated by find_and_verify_loops. */
366 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
368 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
369 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
370 sizeof (struct loop *));
372 /* Allocate storage for array of loops. */
373 loops->array = (struct loop *)
374 xcalloc (loops->num, sizeof (struct loop));
376 /* Find and process each loop.
377 First, find them, and record them in order of their beginnings. */
378 find_and_verify_loops (f, loops);
380 /* Allocate and initialize auxiliary loop information. */
381 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
382 for (i = 0; i < loops->num; i++)
383 loops->array[i].aux = loops_info + i;
385 /* Now find all register lifetimes. This must be done after
386 find_and_verify_loops, because it might reorder the insns in the
388 reg_scan (f, max_reg_before_loop, 1);
390 /* This must occur after reg_scan so that registers created by gcse
391 will have entries in the register tables.
393 We could have added a call to reg_scan after gcse_main in toplev.c,
394 but moving this call to init_alias_analysis is more efficient. */
395 init_alias_analysis ();
397 /* See if we went too far. Note that get_max_uid already returns
398 one more that the maximum uid of all insn. */
399 if (get_max_uid () > max_uid_for_loop)
401 /* Now reset it to the actual size we need. See above. */
402 max_uid_for_loop = get_max_uid ();
404 /* find_and_verify_loops has already called compute_luids, but it
405 might have rearranged code afterwards, so we need to recompute
407 max_luid = compute_luids (f, NULL_RTX, 0);
409 /* Don't leave gaps in uid_luid for insns that have been
410 deleted. It is possible that the first or last insn
411 using some register has been deleted by cross-jumping.
412 Make sure that uid_luid for that former insn's uid
413 points to the general area where that insn used to be. */
414 for (i = 0; i < max_uid_for_loop; i++)
416 uid_luid[0] = uid_luid[i];
417 if (uid_luid[0] != 0)
420 for (i = 0; i < max_uid_for_loop; i++)
421 if (uid_luid[i] == 0)
422 uid_luid[i] = uid_luid[i - 1];
424 /* Determine if the function has indirect jump. On some systems
425 this prevents low overhead loop instructions from being used. */
426 indirect_jump_in_function = indirect_jump_in_function_p (f);
428 /* Now scan the loops, last ones first, since this means inner ones are done
429 before outer ones. */
430 for (i = max_loop_num - 1; i >= 0; i--)
432 struct loop *loop = &loops->array[i];
433 struct loop_regs *regs = LOOP_REGS (loop);
435 regs->moved_once = moved_once;
437 if (! loop->invalid && loop->end)
438 scan_loop (loop, flags);
441 /* If there were lexical blocks inside the loop, they have been
442 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
443 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
444 the BLOCKs as well. */
445 if (write_symbols != NO_DEBUG)
448 end_alias_analysis ();
458 /* Returns the next insn, in execution order, after INSN. START and
459 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
460 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
461 insn-stream; it is used with loops that are entered near the
465 next_insn_in_loop (loop, insn)
466 const struct loop *loop;
469 insn = NEXT_INSN (insn);
471 if (insn == loop->end)
474 /* Go to the top of the loop, and continue there. */
481 if (insn == loop->scan_start)
488 /* Optimize one loop described by LOOP. */
490 /* ??? Could also move memory writes out of loops if the destination address
491 is invariant, the source is invariant, the memory write is not volatile,
492 and if we can prove that no read inside the loop can read this address
493 before the write occurs. If there is a read of this address after the
494 write, then we can also mark the memory read as invariant. */
497 scan_loop (loop, flags)
501 struct loop_info *loop_info = LOOP_INFO (loop);
502 struct loop_regs *regs = LOOP_REGS (loop);
504 rtx loop_start = loop->start;
505 rtx loop_end = loop->end;
507 /* 1 if we are scanning insns that could be executed zero times. */
509 /* 1 if we are scanning insns that might never be executed
510 due to a subroutine call which might exit before they are reached. */
512 /* Jump insn that enters the loop, or 0 if control drops in. */
513 rtx loop_entry_jump = 0;
514 /* Number of insns in the loop. */
517 rtx temp, update_start, update_end;
518 /* The SET from an insn, if it is the only SET in the insn. */
520 /* Chain describing insns movable in current loop. */
521 struct loop_movables *movables = LOOP_MOVABLES (loop);
522 /* Ratio of extra register life span we can justify
523 for saving an instruction. More if loop doesn't call subroutines
524 since in that case saving an insn makes more difference
525 and more registers are available. */
527 /* Nonzero if we are scanning instructions in a sub-loop. */
537 /* Determine whether this loop starts with a jump down to a test at
538 the end. This will occur for a small number of loops with a test
539 that is too complex to duplicate in front of the loop.
541 We search for the first insn or label in the loop, skipping NOTEs.
542 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
543 (because we might have a loop executed only once that contains a
544 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
545 (in case we have a degenerate loop).
547 Note that if we mistakenly think that a loop is entered at the top
548 when, in fact, it is entered at the exit test, the only effect will be
549 slightly poorer optimization. Making the opposite error can generate
550 incorrect code. Since very few loops now start with a jump to the
551 exit test, the code here to detect that case is very conservative. */
553 for (p = NEXT_INSN (loop_start);
555 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
556 && (GET_CODE (p) != NOTE
557 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
558 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
562 loop->scan_start = p;
564 /* Set up variables describing this loop. */
566 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
568 /* If loop has a jump before the first label,
569 the true entry is the target of that jump.
570 Start scan from there.
571 But record in LOOP->TOP the place where the end-test jumps
572 back to so we can scan that after the end of the loop. */
573 if (GET_CODE (p) == JUMP_INSN)
577 /* Loop entry must be unconditional jump (and not a RETURN) */
578 if (any_uncondjump_p (p)
579 && JUMP_LABEL (p) != 0
580 /* Check to see whether the jump actually
581 jumps out of the loop (meaning it's no loop).
582 This case can happen for things like
583 do {..} while (0). If this label was generated previously
584 by loop, we can't tell anything about it and have to reject
586 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
588 loop->top = next_label (loop->scan_start);
589 loop->scan_start = JUMP_LABEL (p);
593 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
594 as required by loop_reg_used_before_p. So skip such loops. (This
595 test may never be true, but it's best to play it safe.)
597 Also, skip loops where we do not start scanning at a label. This
598 test also rejects loops starting with a JUMP_INSN that failed the
601 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
602 || GET_CODE (loop->scan_start) != CODE_LABEL)
604 if (loop_dump_stream)
605 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
606 INSN_UID (loop_start), INSN_UID (loop_end));
610 /* Count number of times each reg is set during this loop. Set
611 VARRAY_CHAR (regs->may_not_optimize, I) if it is not safe to move
612 out the setting of register I. Set VARRAY_RTX
613 (regs->single_usage, I). */
615 /* Allocate extra space for REGS that might be created by
616 load_mems. We allocate a little extra slop as well, in the hopes
617 that even after the moving of movables creates some new registers
618 we won't have to reallocate these arrays. However, we do grow
619 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
620 nregs = max_reg_num () + loop_info->mems_idx + 16;
621 VARRAY_INT_INIT (regs->set_in_loop, nregs, "set_in_loop");
622 VARRAY_INT_INIT (regs->n_times_set, nregs, "n_times_set");
623 VARRAY_CHAR_INIT (regs->may_not_optimize, nregs, "may_not_optimize");
624 VARRAY_RTX_INIT (regs->single_usage, nregs, "single_usage");
628 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
631 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
633 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
634 VARRAY_INT (regs->set_in_loop, i) = 1;
637 #ifdef AVOID_CCMODE_COPIES
638 /* Don't try to move insns which set CC registers if we should not
639 create CCmode register copies. */
640 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
641 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
642 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
645 bcopy ((char *) ®s->set_in_loop->data,
646 (char *) ®s->n_times_set->data, nregs * sizeof (int));
648 if (loop_dump_stream)
650 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
651 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
653 fprintf (loop_dump_stream, "Continue at insn %d.\n",
654 INSN_UID (loop->cont));
657 /* Scan through the loop finding insns that are safe to move.
658 Set regs->set_in_loop negative for the reg being set, so that
659 this reg will be considered invariant for subsequent insns.
660 We consider whether subsequent insns use the reg
661 in deciding whether it is worth actually moving.
663 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
664 and therefore it is possible that the insns we are scanning
665 would never be executed. At such times, we must make sure
666 that it is safe to execute the insn once instead of zero times.
667 When MAYBE_NEVER is 0, all insns will be executed at least once
668 so that is not a problem. */
670 for (p = next_insn_in_loop (loop, loop->scan_start);
672 p = next_insn_in_loop (loop, p))
674 if (GET_CODE (p) == INSN
675 && (set = single_set (p))
676 && GET_CODE (SET_DEST (set)) == REG
677 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
682 rtx src = SET_SRC (set);
683 rtx dependencies = 0;
685 /* Figure out what to use as a source of this insn. If a REG_EQUIV
686 note is given or if a REG_EQUAL note with a constant operand is
687 specified, use it as the source and mark that we should move
688 this insn by calling emit_move_insn rather that duplicating the
691 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
693 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
695 src = XEXP (temp, 0), move_insn = 1;
698 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
699 if (temp && CONSTANT_P (XEXP (temp, 0)))
700 src = XEXP (temp, 0), move_insn = 1;
701 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
703 src = XEXP (temp, 0);
704 /* A libcall block can use regs that don't appear in
705 the equivalent expression. To move the libcall,
706 we must move those regs too. */
707 dependencies = libcall_other_reg (p, src);
711 /* Don't try to optimize a register that was made
712 by loop-optimization for an inner loop.
713 We don't know its life-span, so we can't compute the benefit. */
714 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
716 else if (/* The register is used in basic blocks other
717 than the one where it is set (meaning that
718 something after this point in the loop might
719 depend on its value before the set). */
720 ! reg_in_basic_block_p (p, SET_DEST (set))
721 /* And the set is not guaranteed to be executed one
722 the loop starts, or the value before the set is
723 needed before the set occurs...
725 ??? Note we have quadratic behaviour here, mitigated
726 by the fact that the previous test will often fail for
727 large loops. Rather than re-scanning the entire loop
728 each time for register usage, we should build tables
729 of the register usage and use them here instead. */
731 || loop_reg_used_before_p (loop, set, p)))
732 /* It is unsafe to move the set.
734 This code used to consider it OK to move a set of a variable
735 which was not created by the user and not used in an exit test.
736 That behavior is incorrect and was removed. */
738 else if ((tem = loop_invariant_p (loop, src))
739 && (dependencies == 0
740 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
741 && (VARRAY_INT (regs->set_in_loop,
742 REGNO (SET_DEST (set))) == 1
744 = consec_sets_invariant_p
745 (loop, SET_DEST (set),
746 VARRAY_INT (regs->set_in_loop,
747 REGNO (SET_DEST (set))),
749 /* If the insn can cause a trap (such as divide by zero),
750 can't move it unless it's guaranteed to be executed
751 once loop is entered. Even a function call might
752 prevent the trap insn from being reached
753 (since it might exit!) */
754 && ! ((maybe_never || call_passed)
755 && may_trap_p (src)))
757 register struct movable *m;
758 register int regno = REGNO (SET_DEST (set));
760 /* A potential lossage is where we have a case where two insns
761 can be combined as long as they are both in the loop, but
762 we move one of them outside the loop. For large loops,
763 this can lose. The most common case of this is the address
764 of a function being called.
766 Therefore, if this register is marked as being used exactly
767 once if we are in a loop with calls (a "large loop"), see if
768 we can replace the usage of this register with the source
769 of this SET. If we can, delete this insn.
771 Don't do this if P has a REG_RETVAL note or if we have
772 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
774 if (loop_info->has_call
775 && VARRAY_RTX (regs->single_usage, regno) != 0
776 && VARRAY_RTX (regs->single_usage, regno) != const0_rtx
777 && REGNO_FIRST_UID (regno) == INSN_UID (p)
778 && (REGNO_LAST_UID (regno)
779 == INSN_UID (VARRAY_RTX (regs->single_usage, regno)))
780 && VARRAY_INT (regs->set_in_loop, regno) == 1
781 && ! side_effects_p (SET_SRC (set))
782 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
783 && (! SMALL_REGISTER_CLASSES
784 || (! (GET_CODE (SET_SRC (set)) == REG
785 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
786 /* This test is not redundant; SET_SRC (set) might be
787 a call-clobbered register and the life of REGNO
788 might span a call. */
789 && ! modified_between_p (SET_SRC (set), p,
791 (regs->single_usage, regno))
792 && no_labels_between_p (p, VARRAY_RTX (regs->single_usage,
794 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
796 (regs->single_usage, regno)))
798 /* Replace any usage in a REG_EQUAL note. Must copy the
799 new source, so that we don't get rtx sharing between the
800 SET_SOURCE and REG_NOTES of insn p. */
801 REG_NOTES (VARRAY_RTX (regs->single_usage, regno))
802 = replace_rtx (REG_NOTES (VARRAY_RTX
803 (regs->single_usage, regno)),
804 SET_DEST (set), copy_rtx (SET_SRC (set)));
807 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
808 NOTE_SOURCE_FILE (p) = 0;
809 VARRAY_INT (regs->set_in_loop, regno) = 0;
813 m = (struct movable *) xmalloc (sizeof (struct movable));
817 m->dependencies = dependencies;
818 m->set_dest = SET_DEST (set);
820 m->consec = VARRAY_INT (regs->set_in_loop,
821 REGNO (SET_DEST (set))) - 1;
825 m->move_insn = move_insn;
826 m->move_insn_first = 0;
827 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
828 m->savemode = VOIDmode;
830 /* Set M->cond if either loop_invariant_p
831 or consec_sets_invariant_p returned 2
832 (only conditionally invariant). */
833 m->cond = ((tem | tem1 | tem2) > 1);
834 m->global = LOOP_REG_GLOBAL_P (loop, regno);
836 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
837 m->savings = VARRAY_INT (regs->n_times_set, regno);
838 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
839 m->savings += libcall_benefit (p);
840 VARRAY_INT (regs->set_in_loop, regno) = move_insn ? -2 : -1;
841 /* Add M to the end of the chain MOVABLES. */
842 loop_movables_add (movables, m);
846 /* It is possible for the first instruction to have a
847 REG_EQUAL note but a non-invariant SET_SRC, so we must
848 remember the status of the first instruction in case
849 the last instruction doesn't have a REG_EQUAL note. */
850 m->move_insn_first = m->move_insn;
852 /* Skip this insn, not checking REG_LIBCALL notes. */
853 p = next_nonnote_insn (p);
854 /* Skip the consecutive insns, if there are any. */
855 p = skip_consec_insns (p, m->consec);
856 /* Back up to the last insn of the consecutive group. */
857 p = prev_nonnote_insn (p);
859 /* We must now reset m->move_insn, m->is_equiv, and possibly
860 m->set_src to correspond to the effects of all the
862 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
864 m->set_src = XEXP (temp, 0), m->move_insn = 1;
867 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
868 if (temp && CONSTANT_P (XEXP (temp, 0)))
869 m->set_src = XEXP (temp, 0), m->move_insn = 1;
874 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
877 /* If this register is always set within a STRICT_LOW_PART
878 or set to zero, then its high bytes are constant.
879 So clear them outside the loop and within the loop
880 just load the low bytes.
881 We must check that the machine has an instruction to do so.
882 Also, if the value loaded into the register
883 depends on the same register, this cannot be done. */
884 else if (SET_SRC (set) == const0_rtx
885 && GET_CODE (NEXT_INSN (p)) == INSN
886 && (set1 = single_set (NEXT_INSN (p)))
887 && GET_CODE (set1) == SET
888 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
889 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
890 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
892 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
894 register int regno = REGNO (SET_DEST (set));
895 if (VARRAY_INT (regs->set_in_loop, regno) == 2)
897 register struct movable *m;
898 m = (struct movable *) alloca (sizeof (struct movable));
901 m->set_dest = SET_DEST (set);
908 m->move_insn_first = 0;
910 /* If the insn may not be executed on some cycles,
911 we can't clear the whole reg; clear just high part.
912 Not even if the reg is used only within this loop.
919 Clearing x before the inner loop could clobber a value
920 being saved from the last time around the outer loop.
921 However, if the reg is not used outside this loop
922 and all uses of the register are in the same
923 basic block as the store, there is no problem.
925 If this insn was made by loop, we don't know its
926 INSN_LUID and hence must make a conservative
928 m->global = (INSN_UID (p) >= max_uid_for_loop
929 || LOOP_REG_GLOBAL_P (loop, regno)
930 || (labels_in_range_p
931 (p, REGNO_FIRST_LUID (regno))));
932 if (maybe_never && m->global)
933 m->savemode = GET_MODE (SET_SRC (set1));
935 m->savemode = VOIDmode;
939 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
941 VARRAY_INT (regs->set_in_loop, regno) = -1;
942 /* Add M to the end of the chain MOVABLES. */
943 loop_movables_add (movables, m);
947 /* Past a call insn, we get to insns which might not be executed
948 because the call might exit. This matters for insns that trap.
949 Constant and pure call insns always return, so they don't count. */
950 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
952 /* Past a label or a jump, we get to insns for which we
953 can't count on whether or how many times they will be
954 executed during each iteration. Therefore, we can
955 only move out sets of trivial variables
956 (those not used after the loop). */
957 /* Similar code appears twice in strength_reduce. */
958 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
959 /* If we enter the loop in the middle, and scan around to the
960 beginning, don't set maybe_never for that. This must be an
961 unconditional jump, otherwise the code at the top of the
962 loop might never be executed. Unconditional jumps are
963 followed a by barrier then loop end. */
964 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
965 && NEXT_INSN (NEXT_INSN (p)) == loop_end
966 && any_uncondjump_p (p)))
968 else if (GET_CODE (p) == NOTE)
970 /* At the virtual top of a converted loop, insns are again known to
971 be executed: logically, the loop begins here even though the exit
972 code has been duplicated. */
973 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
974 maybe_never = call_passed = 0;
975 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
977 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
982 /* If one movable subsumes another, ignore that other. */
984 ignore_some_movables (movables);
986 /* For each movable insn, see if the reg that it loads
987 leads when it dies right into another conditionally movable insn.
988 If so, record that the second insn "forces" the first one,
989 since the second can be moved only if the first is. */
991 force_movables (movables);
993 /* See if there are multiple movable insns that load the same value.
994 If there are, make all but the first point at the first one
995 through the `match' field, and add the priorities of them
996 all together as the priority of the first. */
998 combine_movables (movables, regs);
1000 /* Now consider each movable insn to decide whether it is worth moving.
1001 Store 0 in regs->set_in_loop for each reg that is moved.
1003 Generally this increases code size, so do not move moveables when
1004 optimizing for code size. */
1006 if (! optimize_size)
1007 move_movables (loop, movables, threshold, insn_count);
1009 /* Now candidates that still are negative are those not moved.
1010 Change regs->set_in_loop to indicate that those are not actually
1012 for (i = 0; i < nregs; i++)
1013 if (VARRAY_INT (regs->set_in_loop, i) < 0)
1014 VARRAY_INT (regs->set_in_loop, i) = VARRAY_INT (regs->n_times_set, i);
1016 /* Now that we've moved some things out of the loop, we might be able to
1017 hoist even more memory references. */
1018 load_mems_and_recount_loop_regs_set (loop, &insn_count);
1020 for (update_start = loop_start;
1021 PREV_INSN (update_start)
1022 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
1023 update_start = PREV_INSN (update_start))
1025 update_end = NEXT_INSN (loop_end);
1027 reg_scan_update (update_start, update_end, loop_max_reg);
1028 loop_max_reg = max_reg_num ();
1030 if (flag_strength_reduce)
1032 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1033 /* Ensure our label doesn't go away. */
1034 LABEL_NUSES (update_end)++;
1036 strength_reduce (loop, insn_count, flags);
1038 reg_scan_update (update_start, update_end, loop_max_reg);
1039 loop_max_reg = max_reg_num ();
1041 if (update_end && GET_CODE (update_end) == CODE_LABEL
1042 && --LABEL_NUSES (update_end) == 0)
1043 delete_insn (update_end);
1047 /* The movable information is required for strength reduction. */
1048 loop_movables_free (movables);
1050 VARRAY_FREE (regs->single_usage);
1051 VARRAY_FREE (regs->set_in_loop);
1052 VARRAY_FREE (regs->n_times_set);
1053 VARRAY_FREE (regs->may_not_optimize);
1056 /* Add elements to *OUTPUT to record all the pseudo-regs
1057 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1060 record_excess_regs (in_this, not_in_this, output)
1061 rtx in_this, not_in_this;
1068 code = GET_CODE (in_this);
1082 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1083 && ! reg_mentioned_p (in_this, not_in_this))
1084 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1091 fmt = GET_RTX_FORMAT (code);
1092 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1099 for (j = 0; j < XVECLEN (in_this, i); j++)
1100 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1104 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1110 /* Check what regs are referred to in the libcall block ending with INSN,
1111 aside from those mentioned in the equivalent value.
1112 If there are none, return 0.
1113 If there are one or more, return an EXPR_LIST containing all of them. */
1116 libcall_other_reg (insn, equiv)
1119 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1120 rtx p = XEXP (note, 0);
1123 /* First, find all the regs used in the libcall block
1124 that are not mentioned as inputs to the result. */
1128 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1129 || GET_CODE (p) == CALL_INSN)
1130 record_excess_regs (PATTERN (p), equiv, &output);
1137 /* Return 1 if all uses of REG
1138 are between INSN and the end of the basic block. */
1141 reg_in_basic_block_p (insn, reg)
1144 int regno = REGNO (reg);
1147 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1150 /* Search this basic block for the already recorded last use of the reg. */
1151 for (p = insn; p; p = NEXT_INSN (p))
1153 switch (GET_CODE (p))
1160 /* Ordinary insn: if this is the last use, we win. */
1161 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1166 /* Jump insn: if this is the last use, we win. */
1167 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1169 /* Otherwise, it's the end of the basic block, so we lose. */
1174 /* It's the end of the basic block, so we lose. */
1182 /* The "last use" that was recorded can't be found after the first
1183 use. This can happen when the last use was deleted while
1184 processing an inner loop, this inner loop was then completely
1185 unrolled, and the outer loop is always exited after the inner loop,
1186 so that everything after the first use becomes a single basic block. */
1190 /* Compute the benefit of eliminating the insns in the block whose
1191 last insn is LAST. This may be a group of insns used to compute a
1192 value directly or can contain a library call. */
1195 libcall_benefit (last)
1201 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1202 insn != last; insn = NEXT_INSN (insn))
1204 if (GET_CODE (insn) == CALL_INSN)
1205 benefit += 10; /* Assume at least this many insns in a library
1207 else if (GET_CODE (insn) == INSN
1208 && GET_CODE (PATTERN (insn)) != USE
1209 && GET_CODE (PATTERN (insn)) != CLOBBER)
1216 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1219 skip_consec_insns (insn, count)
1223 for (; count > 0; count--)
1227 /* If first insn of libcall sequence, skip to end. */
1228 /* Do this at start of loop, since INSN is guaranteed to
1230 if (GET_CODE (insn) != NOTE
1231 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1232 insn = XEXP (temp, 0);
1235 insn = NEXT_INSN (insn);
1236 while (GET_CODE (insn) == NOTE);
1242 /* Ignore any movable whose insn falls within a libcall
1243 which is part of another movable.
1244 We make use of the fact that the movable for the libcall value
1245 was made later and so appears later on the chain. */
1248 ignore_some_movables (movables)
1249 struct loop_movables *movables;
1251 register struct movable *m, *m1;
1253 for (m = movables->head; m; m = m->next)
1255 /* Is this a movable for the value of a libcall? */
1256 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1260 /* Check for earlier movables inside that range,
1261 and mark them invalid. We cannot use LUIDs here because
1262 insns created by loop.c for prior loops don't have LUIDs.
1263 Rather than reject all such insns from movables, we just
1264 explicitly check each insn in the libcall (since invariant
1265 libcalls aren't that common). */
1266 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1267 for (m1 = movables->head; m1 != m; m1 = m1->next)
1268 if (m1->insn == insn)
1274 /* For each movable insn, see if the reg that it loads
1275 leads when it dies right into another conditionally movable insn.
1276 If so, record that the second insn "forces" the first one,
1277 since the second can be moved only if the first is. */
1280 force_movables (movables)
1281 struct loop_movables *movables;
1283 register struct movable *m, *m1;
1284 for (m1 = movables->head; m1; m1 = m1->next)
1285 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1286 if (!m1->partial && !m1->done)
1288 int regno = m1->regno;
1289 for (m = m1->next; m; m = m->next)
1290 /* ??? Could this be a bug? What if CSE caused the
1291 register of M1 to be used after this insn?
1292 Since CSE does not update regno_last_uid,
1293 this insn M->insn might not be where it dies.
1294 But very likely this doesn't matter; what matters is
1295 that M's reg is computed from M1's reg. */
1296 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1299 if (m != 0 && m->set_src == m1->set_dest
1300 /* If m->consec, m->set_src isn't valid. */
1304 /* Increase the priority of the moving the first insn
1305 since it permits the second to be moved as well. */
1309 m1->lifetime += m->lifetime;
1310 m1->savings += m->savings;
1315 /* Find invariant expressions that are equal and can be combined into
1319 combine_movables (movables, regs)
1320 struct loop_movables *movables;
1321 struct loop_regs *regs;
1323 register struct movable *m;
1324 char *matched_regs = (char *) xmalloc (regs->num);
1325 enum machine_mode mode;
1327 /* Regs that are set more than once are not allowed to match
1328 or be matched. I'm no longer sure why not. */
1329 /* Perhaps testing m->consec_sets would be more appropriate here? */
1331 for (m = movables->head; m; m = m->next)
1332 if (m->match == 0 && VARRAY_INT (regs->n_times_set, m->regno) == 1
1335 register struct movable *m1;
1336 int regno = m->regno;
1338 memset (matched_regs, 0, regs->num);
1339 matched_regs[regno] = 1;
1341 /* We want later insns to match the first one. Don't make the first
1342 one match any later ones. So start this loop at m->next. */
1343 for (m1 = m->next; m1; m1 = m1->next)
1344 if (m != m1 && m1->match == 0 && VARRAY_INT (regs->n_times_set,
1346 /* A reg used outside the loop mustn't be eliminated. */
1348 /* A reg used for zero-extending mustn't be eliminated. */
1350 && (matched_regs[m1->regno]
1353 /* Can combine regs with different modes loaded from the
1354 same constant only if the modes are the same or
1355 if both are integer modes with M wider or the same
1356 width as M1. The check for integer is redundant, but
1357 safe, since the only case of differing destination
1358 modes with equal sources is when both sources are
1359 VOIDmode, i.e., CONST_INT. */
1360 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1361 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1362 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1363 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1364 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1365 /* See if the source of M1 says it matches M. */
1366 && ((GET_CODE (m1->set_src) == REG
1367 && matched_regs[REGNO (m1->set_src)])
1368 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1370 && ((m->dependencies == m1->dependencies)
1371 || rtx_equal_p (m->dependencies, m1->dependencies)))
1373 m->lifetime += m1->lifetime;
1374 m->savings += m1->savings;
1377 matched_regs[m1->regno] = 1;
1381 /* Now combine the regs used for zero-extension.
1382 This can be done for those not marked `global'
1383 provided their lives don't overlap. */
1385 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1386 mode = GET_MODE_WIDER_MODE (mode))
1388 register struct movable *m0 = 0;
1390 /* Combine all the registers for extension from mode MODE.
1391 Don't combine any that are used outside this loop. */
1392 for (m = movables->head; m; m = m->next)
1393 if (m->partial && ! m->global
1394 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1396 register struct movable *m1;
1397 int first = REGNO_FIRST_LUID (m->regno);
1398 int last = REGNO_LAST_LUID (m->regno);
1402 /* First one: don't check for overlap, just record it. */
1407 /* Make sure they extend to the same mode.
1408 (Almost always true.) */
1409 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1412 /* We already have one: check for overlap with those
1413 already combined together. */
1414 for (m1 = movables->head; m1 != m; m1 = m1->next)
1415 if (m1 == m0 || (m1->partial && m1->match == m0))
1416 if (! (REGNO_FIRST_LUID (m1->regno) > last
1417 || REGNO_LAST_LUID (m1->regno) < first))
1420 /* No overlap: we can combine this with the others. */
1421 m0->lifetime += m->lifetime;
1422 m0->savings += m->savings;
1432 free (matched_regs);
1435 /* Return 1 if regs X and Y will become the same if moved. */
1438 regs_match_p (x, y, movables)
1440 struct loop_movables *movables;
1442 unsigned int xn = REGNO (x);
1443 unsigned int yn = REGNO (y);
1444 struct movable *mx, *my;
1446 for (mx = movables->head; mx; mx = mx->next)
1447 if (mx->regno == xn)
1450 for (my = movables->head; my; my = my->next)
1451 if (my->regno == yn)
1455 && ((mx->match == my->match && mx->match != 0)
1457 || mx == my->match));
1460 /* Return 1 if X and Y are identical-looking rtx's.
1461 This is the Lisp function EQUAL for rtx arguments.
1463 If two registers are matching movables or a movable register and an
1464 equivalent constant, consider them equal. */
1467 rtx_equal_for_loop_p (x, y, movables, regs)
1469 struct loop_movables *movables;
1470 struct loop_regs *regs;
1474 register struct movable *m;
1475 register enum rtx_code code;
1476 register const char *fmt;
1480 if (x == 0 || y == 0)
1483 code = GET_CODE (x);
1485 /* If we have a register and a constant, they may sometimes be
1487 if (GET_CODE (x) == REG && VARRAY_INT (regs->set_in_loop, REGNO (x)) == -2
1490 for (m = movables->head; m; m = m->next)
1491 if (m->move_insn && m->regno == REGNO (x)
1492 && rtx_equal_p (m->set_src, y))
1495 else if (GET_CODE (y) == REG && VARRAY_INT (regs->set_in_loop,
1499 for (m = movables->head; m; m = m->next)
1500 if (m->move_insn && m->regno == REGNO (y)
1501 && rtx_equal_p (m->set_src, x))
1505 /* Otherwise, rtx's of different codes cannot be equal. */
1506 if (code != GET_CODE (y))
1509 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1510 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1512 if (GET_MODE (x) != GET_MODE (y))
1515 /* These three types of rtx's can be compared nonrecursively. */
1517 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1519 if (code == LABEL_REF)
1520 return XEXP (x, 0) == XEXP (y, 0);
1521 if (code == SYMBOL_REF)
1522 return XSTR (x, 0) == XSTR (y, 0);
1524 /* Compare the elements. If any pair of corresponding elements
1525 fail to match, return 0 for the whole things. */
1527 fmt = GET_RTX_FORMAT (code);
1528 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1533 if (XWINT (x, i) != XWINT (y, i))
1538 if (XINT (x, i) != XINT (y, i))
1543 /* Two vectors must have the same length. */
1544 if (XVECLEN (x, i) != XVECLEN (y, i))
1547 /* And the corresponding elements must match. */
1548 for (j = 0; j < XVECLEN (x, i); j++)
1549 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1550 movables, regs) == 0)
1555 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1561 if (strcmp (XSTR (x, i), XSTR (y, i)))
1566 /* These are just backpointers, so they don't matter. */
1572 /* It is believed that rtx's at this level will never
1573 contain anything but integers and other rtx's,
1574 except for within LABEL_REFs and SYMBOL_REFs. */
1582 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1583 insns in INSNS which use the reference. */
1586 add_label_notes (x, insns)
1590 enum rtx_code code = GET_CODE (x);
1595 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1597 /* This code used to ignore labels that referred to dispatch tables to
1598 avoid flow generating (slighly) worse code.
1600 We no longer ignore such label references (see LABEL_REF handling in
1601 mark_jump_label for additional information). */
1602 for (insn = insns; insn; insn = NEXT_INSN (insn))
1603 if (reg_mentioned_p (XEXP (x, 0), insn))
1604 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1608 fmt = GET_RTX_FORMAT (code);
1609 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1612 add_label_notes (XEXP (x, i), insns);
1613 else if (fmt[i] == 'E')
1614 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1615 add_label_notes (XVECEXP (x, i, j), insns);
1619 /* Scan MOVABLES, and move the insns that deserve to be moved.
1620 If two matching movables are combined, replace one reg with the
1621 other throughout. */
1624 move_movables (loop, movables, threshold, insn_count)
1626 struct loop_movables *movables;
1630 struct loop_regs *regs = LOOP_REGS (loop);
1631 int nregs = regs->num;
1633 register struct movable *m;
1635 rtx loop_start = loop->start;
1636 rtx loop_end = loop->end;
1637 /* Map of pseudo-register replacements to handle combining
1638 when we move several insns that load the same value
1639 into different pseudo-registers. */
1640 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1641 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1645 for (m = movables->head; m; m = m->next)
1647 /* Describe this movable insn. */
1649 if (loop_dump_stream)
1651 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1652 INSN_UID (m->insn), m->regno, m->lifetime);
1654 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1656 fprintf (loop_dump_stream, "cond ");
1658 fprintf (loop_dump_stream, "force ");
1660 fprintf (loop_dump_stream, "global ");
1662 fprintf (loop_dump_stream, "done ");
1664 fprintf (loop_dump_stream, "move-insn ");
1666 fprintf (loop_dump_stream, "matches %d ",
1667 INSN_UID (m->match->insn));
1669 fprintf (loop_dump_stream, "forces %d ",
1670 INSN_UID (m->forces->insn));
1673 /* Count movables. Value used in heuristics in strength_reduce. */
1676 /* Ignore the insn if it's already done (it matched something else).
1677 Otherwise, see if it is now safe to move. */
1681 || (1 == loop_invariant_p (loop, m->set_src)
1682 && (m->dependencies == 0
1683 || 1 == loop_invariant_p (loop, m->dependencies))
1685 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1688 && (! m->forces || m->forces->done))
1692 int savings = m->savings;
1694 /* We have an insn that is safe to move.
1695 Compute its desirability. */
1700 if (loop_dump_stream)
1701 fprintf (loop_dump_stream, "savings %d ", savings);
1703 if (regs->moved_once[regno] && loop_dump_stream)
1704 fprintf (loop_dump_stream, "halved since already moved ");
1706 /* An insn MUST be moved if we already moved something else
1707 which is safe only if this one is moved too: that is,
1708 if already_moved[REGNO] is nonzero. */
1710 /* An insn is desirable to move if the new lifetime of the
1711 register is no more than THRESHOLD times the old lifetime.
1712 If it's not desirable, it means the loop is so big
1713 that moving won't speed things up much,
1714 and it is liable to make register usage worse. */
1716 /* It is also desirable to move if it can be moved at no
1717 extra cost because something else was already moved. */
1719 if (already_moved[regno]
1720 || flag_move_all_movables
1721 || (threshold * savings * m->lifetime) >=
1722 (regs->moved_once[regno] ? insn_count * 2 : insn_count)
1723 || (m->forces && m->forces->done
1724 && VARRAY_INT (regs->n_times_set, m->forces->regno) == 1))
1727 register struct movable *m1;
1728 rtx first = NULL_RTX;
1730 /* Now move the insns that set the reg. */
1732 if (m->partial && m->match)
1736 /* Find the end of this chain of matching regs.
1737 Thus, we load each reg in the chain from that one reg.
1738 And that reg is loaded with 0 directly,
1739 since it has ->match == 0. */
1740 for (m1 = m; m1->match; m1 = m1->match);
1741 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1742 SET_DEST (PATTERN (m1->insn)));
1743 i1 = emit_insn_before (newpat, loop_start);
1745 /* Mark the moved, invariant reg as being allowed to
1746 share a hard reg with the other matching invariant. */
1747 REG_NOTES (i1) = REG_NOTES (m->insn);
1748 r1 = SET_DEST (PATTERN (m->insn));
1749 r2 = SET_DEST (PATTERN (m1->insn));
1751 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1752 gen_rtx_EXPR_LIST (VOIDmode, r2,
1754 delete_insn (m->insn);
1759 if (loop_dump_stream)
1760 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1762 /* If we are to re-generate the item being moved with a
1763 new move insn, first delete what we have and then emit
1764 the move insn before the loop. */
1765 else if (m->move_insn)
1769 for (count = m->consec; count >= 0; count--)
1771 /* If this is the first insn of a library call sequence,
1773 if (GET_CODE (p) != NOTE
1774 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1777 /* If this is the last insn of a libcall sequence, then
1778 delete every insn in the sequence except the last.
1779 The last insn is handled in the normal manner. */
1780 if (GET_CODE (p) != NOTE
1781 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1783 temp = XEXP (temp, 0);
1785 temp = delete_insn (temp);
1789 p = delete_insn (p);
1791 /* simplify_giv_expr expects that it can walk the insns
1792 at m->insn forwards and see this old sequence we are
1793 tossing here. delete_insn does preserve the next
1794 pointers, but when we skip over a NOTE we must fix
1795 it up. Otherwise that code walks into the non-deleted
1797 while (p && GET_CODE (p) == NOTE)
1798 p = NEXT_INSN (temp) = NEXT_INSN (p);
1802 emit_move_insn (m->set_dest, m->set_src);
1803 temp = get_insns ();
1806 add_label_notes (m->set_src, temp);
1808 i1 = emit_insns_before (temp, loop_start);
1809 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1811 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1812 m->set_src, REG_NOTES (i1));
1814 if (loop_dump_stream)
1815 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1817 /* The more regs we move, the less we like moving them. */
1822 for (count = m->consec; count >= 0; count--)
1826 /* If first insn of libcall sequence, skip to end. */
1827 /* Do this at start of loop, since p is guaranteed to
1829 if (GET_CODE (p) != NOTE
1830 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1833 /* If last insn of libcall sequence, move all
1834 insns except the last before the loop. The last
1835 insn is handled in the normal manner. */
1836 if (GET_CODE (p) != NOTE
1837 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1841 rtx fn_address_insn = 0;
1844 for (temp = XEXP (temp, 0); temp != p;
1845 temp = NEXT_INSN (temp))
1851 if (GET_CODE (temp) == NOTE)
1854 body = PATTERN (temp);
1856 /* Find the next insn after TEMP,
1857 not counting USE or NOTE insns. */
1858 for (next = NEXT_INSN (temp); next != p;
1859 next = NEXT_INSN (next))
1860 if (! (GET_CODE (next) == INSN
1861 && GET_CODE (PATTERN (next)) == USE)
1862 && GET_CODE (next) != NOTE)
1865 /* If that is the call, this may be the insn
1866 that loads the function address.
1868 Extract the function address from the insn
1869 that loads it into a register.
1870 If this insn was cse'd, we get incorrect code.
1872 So emit a new move insn that copies the
1873 function address into the register that the
1874 call insn will use. flow.c will delete any
1875 redundant stores that we have created. */
1876 if (GET_CODE (next) == CALL_INSN
1877 && GET_CODE (body) == SET
1878 && GET_CODE (SET_DEST (body)) == REG
1879 && (n = find_reg_note (temp, REG_EQUAL,
1882 fn_reg = SET_SRC (body);
1883 if (GET_CODE (fn_reg) != REG)
1884 fn_reg = SET_DEST (body);
1885 fn_address = XEXP (n, 0);
1886 fn_address_insn = temp;
1888 /* We have the call insn.
1889 If it uses the register we suspect it might,
1890 load it with the correct address directly. */
1891 if (GET_CODE (temp) == CALL_INSN
1893 && reg_referenced_p (fn_reg, body))
1894 emit_insn_after (gen_move_insn (fn_reg,
1898 if (GET_CODE (temp) == CALL_INSN)
1900 i1 = emit_call_insn_before (body, loop_start);
1901 /* Because the USAGE information potentially
1902 contains objects other than hard registers
1903 we need to copy it. */
1904 if (CALL_INSN_FUNCTION_USAGE (temp))
1905 CALL_INSN_FUNCTION_USAGE (i1)
1906 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1909 i1 = emit_insn_before (body, loop_start);
1912 if (temp == fn_address_insn)
1913 fn_address_insn = i1;
1914 REG_NOTES (i1) = REG_NOTES (temp);
1920 if (m->savemode != VOIDmode)
1922 /* P sets REG to zero; but we should clear only
1923 the bits that are not covered by the mode
1925 rtx reg = m->set_dest;
1931 (GET_MODE (reg), and_optab, reg,
1932 GEN_INT ((((HOST_WIDE_INT) 1
1933 << GET_MODE_BITSIZE (m->savemode)))
1935 reg, 1, OPTAB_LIB_WIDEN);
1939 emit_move_insn (reg, tem);
1940 sequence = gen_sequence ();
1942 i1 = emit_insn_before (sequence, loop_start);
1944 else if (GET_CODE (p) == CALL_INSN)
1946 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1947 /* Because the USAGE information potentially
1948 contains objects other than hard registers
1949 we need to copy it. */
1950 if (CALL_INSN_FUNCTION_USAGE (p))
1951 CALL_INSN_FUNCTION_USAGE (i1)
1952 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1954 else if (count == m->consec && m->move_insn_first)
1956 /* The SET_SRC might not be invariant, so we must
1957 use the REG_EQUAL note. */
1959 emit_move_insn (m->set_dest, m->set_src);
1960 temp = get_insns ();
1963 add_label_notes (m->set_src, temp);
1965 i1 = emit_insns_before (temp, loop_start);
1966 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1968 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1970 m->set_src, REG_NOTES (i1));
1973 i1 = emit_insn_before (PATTERN (p), loop_start);
1975 if (REG_NOTES (i1) == 0)
1977 REG_NOTES (i1) = REG_NOTES (p);
1979 /* If there is a REG_EQUAL note present whose value
1980 is not loop invariant, then delete it, since it
1981 may cause problems with later optimization passes.
1982 It is possible for cse to create such notes
1983 like this as a result of record_jump_cond. */
1985 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
1986 && ! loop_invariant_p (loop, XEXP (temp, 0)))
1987 remove_note (i1, temp);
1993 if (loop_dump_stream)
1994 fprintf (loop_dump_stream, " moved to %d",
1997 /* If library call, now fix the REG_NOTES that contain
1998 insn pointers, namely REG_LIBCALL on FIRST
1999 and REG_RETVAL on I1. */
2000 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2002 XEXP (temp, 0) = first;
2003 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2004 XEXP (temp, 0) = i1;
2011 /* simplify_giv_expr expects that it can walk the insns
2012 at m->insn forwards and see this old sequence we are
2013 tossing here. delete_insn does preserve the next
2014 pointers, but when we skip over a NOTE we must fix
2015 it up. Otherwise that code walks into the non-deleted
2017 while (p && GET_CODE (p) == NOTE)
2018 p = NEXT_INSN (temp) = NEXT_INSN (p);
2021 /* The more regs we move, the less we like moving them. */
2025 /* Any other movable that loads the same register
2027 already_moved[regno] = 1;
2029 /* This reg has been moved out of one loop. */
2030 regs->moved_once[regno] = 1;
2032 /* The reg set here is now invariant. */
2034 VARRAY_INT (regs->set_in_loop, regno) = 0;
2038 /* Change the length-of-life info for the register
2039 to say it lives at least the full length of this loop.
2040 This will help guide optimizations in outer loops. */
2042 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2043 /* This is the old insn before all the moved insns.
2044 We can't use the moved insn because it is out of range
2045 in uid_luid. Only the old insns have luids. */
2046 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2047 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2048 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2050 /* Combine with this moved insn any other matching movables. */
2053 for (m1 = movables->head; m1; m1 = m1->next)
2058 /* Schedule the reg loaded by M1
2059 for replacement so that shares the reg of M.
2060 If the modes differ (only possible in restricted
2061 circumstances, make a SUBREG.
2063 Note this assumes that the target dependent files
2064 treat REG and SUBREG equally, including within
2065 GO_IF_LEGITIMATE_ADDRESS and in all the
2066 predicates since we never verify that replacing the
2067 original register with a SUBREG results in a
2068 recognizable insn. */
2069 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2070 reg_map[m1->regno] = m->set_dest;
2073 = gen_lowpart_common (GET_MODE (m1->set_dest),
2076 /* Get rid of the matching insn
2077 and prevent further processing of it. */
2080 /* if library call, delete all insn except last, which
2082 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2085 for (temp = XEXP (temp, 0); temp != m1->insn;
2086 temp = NEXT_INSN (temp))
2089 delete_insn (m1->insn);
2091 /* Any other movable that loads the same register
2093 already_moved[m1->regno] = 1;
2095 /* The reg merged here is now invariant,
2096 if the reg it matches is invariant. */
2098 VARRAY_INT (regs->set_in_loop, m1->regno) = 0;
2101 else if (loop_dump_stream)
2102 fprintf (loop_dump_stream, "not desirable");
2104 else if (loop_dump_stream && !m->match)
2105 fprintf (loop_dump_stream, "not safe");
2107 if (loop_dump_stream)
2108 fprintf (loop_dump_stream, "\n");
2112 new_start = loop_start;
2114 /* Go through all the instructions in the loop, making
2115 all the register substitutions scheduled in REG_MAP. */
2116 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2117 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2118 || GET_CODE (p) == CALL_INSN)
2120 replace_regs (PATTERN (p), reg_map, nregs, 0);
2121 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2127 free (already_moved);
2132 loop_movables_add (movables, m)
2133 struct loop_movables *movables;
2136 if (movables->head == 0)
2139 movables->last->next = m;
2145 loop_movables_free (movables)
2146 struct loop_movables *movables;
2149 struct movable *m_next;
2151 for (m = movables->head; m; m = m_next)
2159 /* Scan X and replace the address of any MEM in it with ADDR.
2160 REG is the address that MEM should have before the replacement. */
2163 replace_call_address (x, reg, addr)
2166 register enum rtx_code code;
2168 register const char *fmt;
2172 code = GET_CODE (x);
2186 /* Short cut for very common case. */
2187 replace_call_address (XEXP (x, 1), reg, addr);
2191 /* Short cut for very common case. */
2192 replace_call_address (XEXP (x, 0), reg, addr);
2196 /* If this MEM uses a reg other than the one we expected,
2197 something is wrong. */
2198 if (XEXP (x, 0) != reg)
2207 fmt = GET_RTX_FORMAT (code);
2208 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2211 replace_call_address (XEXP (x, i), reg, addr);
2212 else if (fmt[i] == 'E')
2215 for (j = 0; j < XVECLEN (x, i); j++)
2216 replace_call_address (XVECEXP (x, i, j), reg, addr);
2222 /* Return the number of memory refs to addresses that vary
2226 count_nonfixed_reads (loop, x)
2227 const struct loop *loop;
2230 register enum rtx_code code;
2232 register const char *fmt;
2238 code = GET_CODE (x);
2252 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2253 + count_nonfixed_reads (loop, XEXP (x, 0)));
2260 fmt = GET_RTX_FORMAT (code);
2261 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2264 value += count_nonfixed_reads (loop, XEXP (x, i));
2268 for (j = 0; j < XVECLEN (x, i); j++)
2269 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2275 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2276 `has_call', `has_volatile', `has_tablejump',
2277 `unknown_address_altered', `unknown_constant_address_altered', and
2278 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2279 list `store_mems' in LOOP. */
2285 register int level = 1;
2287 struct loop_info *loop_info = LOOP_INFO (loop);
2288 rtx start = loop->start;
2289 rtx end = loop->end;
2290 /* The label after END. Jumping here is just like falling off the
2291 end of the loop. We use next_nonnote_insn instead of next_label
2292 as a hedge against the (pathological) case where some actual insn
2293 might end up between the two. */
2294 rtx exit_target = next_nonnote_insn (end);
2296 loop_info->has_indirect_jump = indirect_jump_in_function;
2297 loop_info->has_call = 0;
2298 loop_info->has_volatile = 0;
2299 loop_info->has_tablejump = 0;
2300 loop_info->has_multiple_exit_targets = 0;
2303 loop_info->unknown_address_altered = 0;
2304 loop_info->unknown_constant_address_altered = 0;
2305 loop_info->store_mems = NULL_RTX;
2306 loop_info->first_loop_store_insn = NULL_RTX;
2307 loop_info->mems_idx = 0;
2308 loop_info->num_mem_sets = 0;
2310 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2311 insn = NEXT_INSN (insn))
2313 if (GET_CODE (insn) == NOTE)
2315 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2318 /* Count number of loops contained in this one. */
2321 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2326 else if (GET_CODE (insn) == CALL_INSN)
2328 if (! CONST_CALL_P (insn))
2329 loop_info->unknown_address_altered = 1;
2330 loop_info->has_call = 1;
2332 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2334 rtx label1 = NULL_RTX;
2335 rtx label2 = NULL_RTX;
2337 if (volatile_refs_p (PATTERN (insn)))
2338 loop_info->has_volatile = 1;
2340 if (GET_CODE (insn) == JUMP_INSN
2341 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2342 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2343 loop_info->has_tablejump = 1;
2345 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2346 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2347 loop_info->first_loop_store_insn = insn;
2349 if (! loop_info->has_multiple_exit_targets
2350 && GET_CODE (insn) == JUMP_INSN
2351 && GET_CODE (PATTERN (insn)) == SET
2352 && SET_DEST (PATTERN (insn)) == pc_rtx)
2354 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2356 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2357 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2361 label1 = SET_SRC (PATTERN (insn));
2366 if (label1 && label1 != pc_rtx)
2368 if (GET_CODE (label1) != LABEL_REF)
2370 /* Something tricky. */
2371 loop_info->has_multiple_exit_targets = 1;
2374 else if (XEXP (label1, 0) != exit_target
2375 && LABEL_OUTSIDE_LOOP_P (label1))
2377 /* A jump outside the current loop. */
2378 loop_info->has_multiple_exit_targets = 1;
2389 else if (GET_CODE (insn) == RETURN)
2390 loop_info->has_multiple_exit_targets = 1;
2393 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2394 if (/* An exception thrown by a called function might land us
2396 ! loop_info->has_call
2397 /* We don't want loads for MEMs moved to a location before the
2398 one at which their stack memory becomes allocated. (Note
2399 that this is not a problem for malloc, etc., since those
2400 require actual function calls. */
2401 && ! current_function_calls_alloca
2402 /* There are ways to leave the loop other than falling off the
2404 && ! loop_info->has_multiple_exit_targets)
2405 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2406 insn = NEXT_INSN (insn))
2407 for_each_rtx (&insn, insert_loop_mem, loop_info);
2409 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2410 that loop_invariant_p and load_mems can use true_dependence
2411 to determine what is really clobbered. */
2412 if (loop_info->unknown_address_altered)
2414 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2416 loop_info->store_mems
2417 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2419 if (loop_info->unknown_constant_address_altered)
2421 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2423 RTX_UNCHANGING_P (mem) = 1;
2424 loop_info->store_mems
2425 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2429 /* Scan the function looking for loops. Record the start and end of each loop.
2430 Also mark as invalid loops any loops that contain a setjmp or are branched
2431 to from outside the loop. */
2434 find_and_verify_loops (f, loops)
2436 struct loops *loops;
2441 struct loop *current_loop;
2442 struct loop *next_loop;
2445 num_loops = loops->num;
2447 compute_luids (f, NULL_RTX, 0);
2449 /* If there are jumps to undefined labels,
2450 treat them as jumps out of any/all loops.
2451 This also avoids writing past end of tables when there are no loops. */
2454 /* Find boundaries of loops, mark which loops are contained within
2455 loops, and invalidate loops that have setjmp. */
2458 current_loop = NULL;
2459 for (insn = f; insn; insn = NEXT_INSN (insn))
2461 if (GET_CODE (insn) == NOTE)
2462 switch (NOTE_LINE_NUMBER (insn))
2464 case NOTE_INSN_LOOP_BEG:
2465 next_loop = loops->array + num_loops;
2466 next_loop->num = num_loops;
2468 next_loop->start = insn;
2469 next_loop->outer = current_loop;
2470 current_loop = next_loop;
2473 case NOTE_INSN_SETJMP:
2474 /* In this case, we must invalidate our current loop and any
2476 for (loop = current_loop; loop; loop = loop->outer)
2479 if (loop_dump_stream)
2480 fprintf (loop_dump_stream,
2481 "\nLoop at %d ignored due to setjmp.\n",
2482 INSN_UID (loop->start));
2486 case NOTE_INSN_LOOP_CONT:
2487 current_loop->cont = insn;
2490 case NOTE_INSN_LOOP_VTOP:
2491 current_loop->vtop = insn;
2494 case NOTE_INSN_LOOP_END:
2498 current_loop->end = insn;
2499 current_loop = current_loop->outer;
2506 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2507 enclosing loop, but this doesn't matter. */
2508 uid_loop[INSN_UID (insn)] = current_loop;
2511 /* Any loop containing a label used in an initializer must be invalidated,
2512 because it can be jumped into from anywhere. */
2514 for (label = forced_labels; label; label = XEXP (label, 1))
2516 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2517 loop; loop = loop->outer)
2521 /* Any loop containing a label used for an exception handler must be
2522 invalidated, because it can be jumped into from anywhere. */
2524 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2526 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2527 loop; loop = loop->outer)
2531 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2532 loop that it is not contained within, that loop is marked invalid.
2533 If any INSN or CALL_INSN uses a label's address, then the loop containing
2534 that label is marked invalid, because it could be jumped into from
2537 Also look for blocks of code ending in an unconditional branch that
2538 exits the loop. If such a block is surrounded by a conditional
2539 branch around the block, move the block elsewhere (see below) and
2540 invert the jump to point to the code block. This may eliminate a
2541 label in our loop and will simplify processing by both us and a
2542 possible second cse pass. */
2544 for (insn = f; insn; insn = NEXT_INSN (insn))
2547 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2549 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2551 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2554 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2555 loop; loop = loop->outer)
2560 if (GET_CODE (insn) != JUMP_INSN)
2563 mark_loop_jump (PATTERN (insn), this_loop);
2565 /* See if this is an unconditional branch outside the loop. */
2567 && (GET_CODE (PATTERN (insn)) == RETURN
2568 || (any_uncondjump_p (insn)
2569 && onlyjump_p (insn)
2570 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2572 && get_max_uid () < max_uid_for_loop)
2575 rtx our_next = next_real_insn (insn);
2576 rtx last_insn_to_move = NEXT_INSN (insn);
2577 struct loop *dest_loop;
2578 struct loop *outer_loop = NULL;
2580 /* Go backwards until we reach the start of the loop, a label,
2582 for (p = PREV_INSN (insn);
2583 GET_CODE (p) != CODE_LABEL
2584 && ! (GET_CODE (p) == NOTE
2585 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2586 && GET_CODE (p) != JUMP_INSN;
2590 /* Check for the case where we have a jump to an inner nested
2591 loop, and do not perform the optimization in that case. */
2593 if (JUMP_LABEL (insn))
2595 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2598 for (outer_loop = dest_loop; outer_loop;
2599 outer_loop = outer_loop->outer)
2600 if (outer_loop == this_loop)
2605 /* Make sure that the target of P is within the current loop. */
2607 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2608 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2609 outer_loop = this_loop;
2611 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2612 we have a block of code to try to move.
2614 We look backward and then forward from the target of INSN
2615 to find a BARRIER at the same loop depth as the target.
2616 If we find such a BARRIER, we make a new label for the start
2617 of the block, invert the jump in P and point it to that label,
2618 and move the block of code to the spot we found. */
2621 && GET_CODE (p) == JUMP_INSN
2622 && JUMP_LABEL (p) != 0
2623 /* Just ignore jumps to labels that were never emitted.
2624 These always indicate compilation errors. */
2625 && INSN_UID (JUMP_LABEL (p)) != 0
2626 && any_condjump_p (p) && onlyjump_p (p)
2627 && next_real_insn (JUMP_LABEL (p)) == our_next
2628 /* If it's not safe to move the sequence, then we
2630 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2631 &last_insn_to_move))
2634 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2635 struct loop *target_loop = uid_loop[INSN_UID (target)];
2638 for (loc = target; loc; loc = PREV_INSN (loc))
2639 if (GET_CODE (loc) == BARRIER
2640 /* Don't move things inside a tablejump. */
2641 && ((loc2 = next_nonnote_insn (loc)) == 0
2642 || GET_CODE (loc2) != CODE_LABEL
2643 || (loc2 = next_nonnote_insn (loc2)) == 0
2644 || GET_CODE (loc2) != JUMP_INSN
2645 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2646 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2647 && uid_loop[INSN_UID (loc)] == target_loop)
2651 for (loc = target; loc; loc = NEXT_INSN (loc))
2652 if (GET_CODE (loc) == BARRIER
2653 /* Don't move things inside a tablejump. */
2654 && ((loc2 = next_nonnote_insn (loc)) == 0
2655 || GET_CODE (loc2) != CODE_LABEL
2656 || (loc2 = next_nonnote_insn (loc2)) == 0
2657 || GET_CODE (loc2) != JUMP_INSN
2658 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2659 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2660 && uid_loop[INSN_UID (loc)] == target_loop)
2665 rtx cond_label = JUMP_LABEL (p);
2666 rtx new_label = get_label_after (p);
2668 /* Ensure our label doesn't go away. */
2669 LABEL_NUSES (cond_label)++;
2671 /* Verify that uid_loop is large enough and that
2673 if (invert_jump (p, new_label, 1))
2677 /* If no suitable BARRIER was found, create a suitable
2678 one before TARGET. Since TARGET is a fall through
2679 path, we'll need to insert an jump around our block
2680 and a add a BARRIER before TARGET.
2682 This creates an extra unconditional jump outside
2683 the loop. However, the benefits of removing rarely
2684 executed instructions from inside the loop usually
2685 outweighs the cost of the extra unconditional jump
2686 outside the loop. */
2691 temp = gen_jump (JUMP_LABEL (insn));
2692 temp = emit_jump_insn_before (temp, target);
2693 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2694 LABEL_NUSES (JUMP_LABEL (insn))++;
2695 loc = emit_barrier_before (target);
2698 /* Include the BARRIER after INSN and copy the
2700 new_label = squeeze_notes (new_label,
2702 reorder_insns (new_label, last_insn_to_move, loc);
2704 /* All those insns are now in TARGET_LOOP. */
2706 q != NEXT_INSN (last_insn_to_move);
2708 uid_loop[INSN_UID (q)] = target_loop;
2710 /* The label jumped to by INSN is no longer a loop
2711 exit. Unless INSN does not have a label (e.g.,
2712 it is a RETURN insn), search loop->exit_labels
2713 to find its label_ref, and remove it. Also turn
2714 off LABEL_OUTSIDE_LOOP_P bit. */
2715 if (JUMP_LABEL (insn))
2717 for (q = 0, r = this_loop->exit_labels;
2719 q = r, r = LABEL_NEXTREF (r))
2720 if (XEXP (r, 0) == JUMP_LABEL (insn))
2722 LABEL_OUTSIDE_LOOP_P (r) = 0;
2724 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2726 this_loop->exit_labels = LABEL_NEXTREF (r);
2730 for (loop = this_loop; loop && loop != target_loop;
2734 /* If we didn't find it, then something is
2740 /* P is now a jump outside the loop, so it must be put
2741 in loop->exit_labels, and marked as such.
2742 The easiest way to do this is to just call
2743 mark_loop_jump again for P. */
2744 mark_loop_jump (PATTERN (p), this_loop);
2746 /* If INSN now jumps to the insn after it,
2748 if (JUMP_LABEL (insn) != 0
2749 && (next_real_insn (JUMP_LABEL (insn))
2750 == next_real_insn (insn)))
2754 /* Continue the loop after where the conditional
2755 branch used to jump, since the only branch insn
2756 in the block (if it still remains) is an inter-loop
2757 branch and hence needs no processing. */
2758 insn = NEXT_INSN (cond_label);
2760 if (--LABEL_NUSES (cond_label) == 0)
2761 delete_insn (cond_label);
2763 /* This loop will be continued with NEXT_INSN (insn). */
2764 insn = PREV_INSN (insn);
2771 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2772 loops it is contained in, mark the target loop invalid.
2774 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2777 mark_loop_jump (x, loop)
2781 struct loop *dest_loop;
2782 struct loop *outer_loop;
2785 switch (GET_CODE (x))
2798 /* There could be a label reference in here. */
2799 mark_loop_jump (XEXP (x, 0), loop);
2805 mark_loop_jump (XEXP (x, 0), loop);
2806 mark_loop_jump (XEXP (x, 1), loop);
2810 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2811 mark_loop_jump (XEXP (x, 1), loop);
2816 mark_loop_jump (XEXP (x, 0), loop);
2820 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2822 /* Link together all labels that branch outside the loop. This
2823 is used by final_[bg]iv_value and the loop unrolling code. Also
2824 mark this LABEL_REF so we know that this branch should predict
2827 /* A check to make sure the label is not in an inner nested loop,
2828 since this does not count as a loop exit. */
2831 for (outer_loop = dest_loop; outer_loop;
2832 outer_loop = outer_loop->outer)
2833 if (outer_loop == loop)
2839 if (loop && ! outer_loop)
2841 LABEL_OUTSIDE_LOOP_P (x) = 1;
2842 LABEL_NEXTREF (x) = loop->exit_labels;
2843 loop->exit_labels = x;
2845 for (outer_loop = loop;
2846 outer_loop && outer_loop != dest_loop;
2847 outer_loop = outer_loop->outer)
2848 outer_loop->exit_count++;
2851 /* If this is inside a loop, but not in the current loop or one enclosed
2852 by it, it invalidates at least one loop. */
2857 /* We must invalidate every nested loop containing the target of this
2858 label, except those that also contain the jump insn. */
2860 for (; dest_loop; dest_loop = dest_loop->outer)
2862 /* Stop when we reach a loop that also contains the jump insn. */
2863 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2864 if (dest_loop == outer_loop)
2867 /* If we get here, we know we need to invalidate a loop. */
2868 if (loop_dump_stream && ! dest_loop->invalid)
2869 fprintf (loop_dump_stream,
2870 "\nLoop at %d ignored due to multiple entry points.\n",
2871 INSN_UID (dest_loop->start));
2873 dest_loop->invalid = 1;
2878 /* If this is not setting pc, ignore. */
2879 if (SET_DEST (x) == pc_rtx)
2880 mark_loop_jump (SET_SRC (x), loop);
2884 mark_loop_jump (XEXP (x, 1), loop);
2885 mark_loop_jump (XEXP (x, 2), loop);
2890 for (i = 0; i < XVECLEN (x, 0); i++)
2891 mark_loop_jump (XVECEXP (x, 0, i), loop);
2895 for (i = 0; i < XVECLEN (x, 1); i++)
2896 mark_loop_jump (XVECEXP (x, 1, i), loop);
2900 /* Strictly speaking this is not a jump into the loop, only a possible
2901 jump out of the loop. However, we have no way to link the destination
2902 of this jump onto the list of exit labels. To be safe we mark this
2903 loop and any containing loops as invalid. */
2906 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2908 if (loop_dump_stream && ! outer_loop->invalid)
2909 fprintf (loop_dump_stream,
2910 "\nLoop at %d ignored due to unknown exit jump.\n",
2911 INSN_UID (outer_loop->start));
2912 outer_loop->invalid = 1;
2919 /* Return nonzero if there is a label in the range from
2920 insn INSN to and including the insn whose luid is END
2921 INSN must have an assigned luid (i.e., it must not have
2922 been previously created by loop.c). */
2925 labels_in_range_p (insn, end)
2929 while (insn && INSN_LUID (insn) <= end)
2931 if (GET_CODE (insn) == CODE_LABEL)
2933 insn = NEXT_INSN (insn);
2939 /* Record that a memory reference X is being set. */
2942 note_addr_stored (x, y, data)
2944 rtx y ATTRIBUTE_UNUSED;
2945 void *data ATTRIBUTE_UNUSED;
2947 struct loop_info *loop_info = data;
2949 if (x == 0 || GET_CODE (x) != MEM)
2952 /* Count number of memory writes.
2953 This affects heuristics in strength_reduce. */
2954 loop_info->num_mem_sets++;
2956 /* BLKmode MEM means all memory is clobbered. */
2957 if (GET_MODE (x) == BLKmode)
2959 if (RTX_UNCHANGING_P (x))
2960 loop_info->unknown_constant_address_altered = 1;
2962 loop_info->unknown_address_altered = 1;
2967 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2968 loop_info->store_mems);
2971 /* X is a value modified by an INSN that references a biv inside a loop
2972 exit test (ie, X is somehow related to the value of the biv). If X
2973 is a pseudo that is used more than once, then the biv is (effectively)
2974 used more than once. DATA is a pointer to a loop_regs structure. */
2977 note_set_pseudo_multiple_uses (x, y, data)
2979 rtx y ATTRIBUTE_UNUSED;
2982 struct loop_regs *regs = (struct loop_regs *) data;
2987 while (GET_CODE (x) == STRICT_LOW_PART
2988 || GET_CODE (x) == SIGN_EXTRACT
2989 || GET_CODE (x) == ZERO_EXTRACT
2990 || GET_CODE (x) == SUBREG)
2993 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
2996 /* If we do not have usage information, or if we know the register
2997 is used more than once, note that fact for check_dbra_loop. */
2998 if (REGNO (x) >= max_reg_before_loop
2999 || ! VARRAY_RTX (regs->single_usage, REGNO (x))
3000 || VARRAY_RTX (regs->single_usage, REGNO (x)) == const0_rtx)
3001 regs->multiple_uses = 1;
3004 /* Return nonzero if the rtx X is invariant over the current loop.
3006 The value is 2 if we refer to something only conditionally invariant.
3008 A memory ref is invariant if it is not volatile and does not conflict
3009 with anything stored in `loop_info->store_mems'. */
3012 loop_invariant_p (loop, x)
3013 const struct loop *loop;
3016 struct loop_info *loop_info = LOOP_INFO (loop);
3017 struct loop_regs *regs = LOOP_REGS (loop);
3019 register enum rtx_code code;
3020 register const char *fmt;
3021 int conditional = 0;
3026 code = GET_CODE (x);
3036 /* A LABEL_REF is normally invariant, however, if we are unrolling
3037 loops, and this label is inside the loop, then it isn't invariant.
3038 This is because each unrolled copy of the loop body will have
3039 a copy of this label. If this was invariant, then an insn loading
3040 the address of this label into a register might get moved outside
3041 the loop, and then each loop body would end up using the same label.
3043 We don't know the loop bounds here though, so just fail for all
3045 if (flag_unroll_loops)
3052 case UNSPEC_VOLATILE:
3056 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3057 since the reg might be set by initialization within the loop. */
3059 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3060 || x == arg_pointer_rtx)
3061 && ! current_function_has_nonlocal_goto)
3064 if (LOOP_INFO (loop)->has_call
3065 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3068 if (VARRAY_INT (regs->set_in_loop, REGNO (x)) < 0)
3071 return VARRAY_INT (regs->set_in_loop, REGNO (x)) == 0;
3074 /* Volatile memory references must be rejected. Do this before
3075 checking for read-only items, so that volatile read-only items
3076 will be rejected also. */
3077 if (MEM_VOLATILE_P (x))
3080 /* See if there is any dependence between a store and this load. */
3081 mem_list_entry = loop_info->store_mems;
3082 while (mem_list_entry)
3084 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3088 mem_list_entry = XEXP (mem_list_entry, 1);
3091 /* It's not invalidated by a store in memory
3092 but we must still verify the address is invariant. */
3096 /* Don't mess with insns declared volatile. */
3097 if (MEM_VOLATILE_P (x))
3105 fmt = GET_RTX_FORMAT (code);
3106 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3110 int tem = loop_invariant_p (loop, XEXP (x, i));
3116 else if (fmt[i] == 'E')
3119 for (j = 0; j < XVECLEN (x, i); j++)
3121 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3131 return 1 + conditional;
3134 /* Return nonzero if all the insns in the loop that set REG
3135 are INSN and the immediately following insns,
3136 and if each of those insns sets REG in an invariant way
3137 (not counting uses of REG in them).
3139 The value is 2 if some of these insns are only conditionally invariant.
3141 We assume that INSN itself is the first set of REG
3142 and that its source is invariant. */
3145 consec_sets_invariant_p (loop, reg, n_sets, insn)
3146 const struct loop *loop;
3150 struct loop_regs *regs = LOOP_REGS (loop);
3152 unsigned int regno = REGNO (reg);
3154 /* Number of sets we have to insist on finding after INSN. */
3155 int count = n_sets - 1;
3156 int old = VARRAY_INT (regs->set_in_loop, regno);
3160 /* If N_SETS hit the limit, we can't rely on its value. */
3164 VARRAY_INT (regs->set_in_loop, regno) = 0;
3168 register enum rtx_code code;
3172 code = GET_CODE (p);
3174 /* If library call, skip to end of it. */
3175 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3180 && (set = single_set (p))
3181 && GET_CODE (SET_DEST (set)) == REG
3182 && REGNO (SET_DEST (set)) == regno)
3184 this = loop_invariant_p (loop, SET_SRC (set));
3187 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3189 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3190 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3192 this = (CONSTANT_P (XEXP (temp, 0))
3193 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3194 && loop_invariant_p (loop, XEXP (temp, 0))));
3201 else if (code != NOTE)
3203 VARRAY_INT (regs->set_in_loop, regno) = old;
3208 VARRAY_INT (regs->set_in_loop, regno) = old;
3209 /* If loop_invariant_p ever returned 2, we return 2. */
3210 return 1 + (value & 2);
3214 /* I don't think this condition is sufficient to allow INSN
3215 to be moved, so we no longer test it. */
3217 /* Return 1 if all insns in the basic block of INSN and following INSN
3218 that set REG are invariant according to TABLE. */
3221 all_sets_invariant_p (reg, insn, table)
3225 register rtx p = insn;
3226 register int regno = REGNO (reg);
3230 register enum rtx_code code;
3232 code = GET_CODE (p);
3233 if (code == CODE_LABEL || code == JUMP_INSN)
3235 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3236 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3237 && REGNO (SET_DEST (PATTERN (p))) == regno)
3239 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3246 /* Look at all uses (not sets) of registers in X. For each, if it is
3247 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3248 a different insn, set USAGE[REGNO] to const0_rtx. */
3251 find_single_use_in_loop (insn, x, usage)
3256 enum rtx_code code = GET_CODE (x);
3257 const char *fmt = GET_RTX_FORMAT (code);
3261 VARRAY_RTX (usage, REGNO (x))
3262 = (VARRAY_RTX (usage, REGNO (x)) != 0
3263 && VARRAY_RTX (usage, REGNO (x)) != insn)
3264 ? const0_rtx : insn;
3266 else if (code == SET)
3268 /* Don't count SET_DEST if it is a REG; otherwise count things
3269 in SET_DEST because if a register is partially modified, it won't
3270 show up as a potential movable so we don't care how USAGE is set
3272 if (GET_CODE (SET_DEST (x)) != REG)
3273 find_single_use_in_loop (insn, SET_DEST (x), usage);
3274 find_single_use_in_loop (insn, SET_SRC (x), usage);
3277 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3279 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3280 find_single_use_in_loop (insn, XEXP (x, i), usage);
3281 else if (fmt[i] == 'E')
3282 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3283 find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
3287 /* Count and record any set in X which is contained in INSN. Update
3288 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3291 count_one_set (regs, insn, x, may_not_move, last_set)
3292 struct loop_regs *regs;
3294 varray_type may_not_move;
3297 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3298 /* Don't move a reg that has an explicit clobber.
3299 It's not worth the pain to try to do it correctly. */
3300 VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
3302 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3304 rtx dest = SET_DEST (x);
3305 while (GET_CODE (dest) == SUBREG
3306 || GET_CODE (dest) == ZERO_EXTRACT
3307 || GET_CODE (dest) == SIGN_EXTRACT
3308 || GET_CODE (dest) == STRICT_LOW_PART)
3309 dest = XEXP (dest, 0);
3310 if (GET_CODE (dest) == REG)
3312 register int regno = REGNO (dest);
3313 /* If this is the first setting of this reg
3314 in current basic block, and it was set before,
3315 it must be set in two basic blocks, so it cannot
3316 be moved out of the loop. */
3317 if (VARRAY_INT (regs->set_in_loop, regno) > 0
3318 && last_set[regno] == 0)
3319 VARRAY_CHAR (may_not_move, regno) = 1;
3320 /* If this is not first setting in current basic block,
3321 see if reg was used in between previous one and this.
3322 If so, neither one can be moved. */
3323 if (last_set[regno] != 0
3324 && reg_used_between_p (dest, last_set[regno], insn))
3325 VARRAY_CHAR (may_not_move, regno) = 1;
3326 if (VARRAY_INT (regs->set_in_loop, regno) < 127)
3327 ++VARRAY_INT (regs->set_in_loop, regno);
3328 last_set[regno] = insn;
3333 /* Increment REGS->SET_IN_LOOP at the index of each register
3334 that is modified by an insn between FROM and TO.
3335 If the value of an element of REGS->SET_IN_LOOP becomes 127 or more,
3336 stop incrementing it, to avoid overflow.
3338 Store in SINGLE_USAGE[I] the single insn in which register I is
3339 used, if it is only used once. Otherwise, it is set to 0 (for no
3340 uses) or const0_rtx for more than one use. This parameter may be zero,
3341 in which case this processing is not done.
3343 Store in *COUNT_PTR the number of actual instruction
3344 in the loop. We use this to decide what is worth moving out. */
3346 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3347 In that case, it is the insn that last set reg n. */
3350 count_loop_regs_set (loop, may_not_move, single_usage, count_ptr, nregs)
3351 const struct loop *loop;
3352 varray_type may_not_move;
3353 varray_type single_usage;
3357 struct loop_regs *regs = LOOP_REGS (loop);
3358 register rtx *last_set = (rtx *) xcalloc (nregs, sizeof (rtx));
3360 register int count = 0;
3362 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
3363 insn = NEXT_INSN (insn))
3369 /* Record registers that have exactly one use. */
3370 find_single_use_in_loop (insn, PATTERN (insn), single_usage);
3372 /* Include uses in REG_EQUAL notes. */
3373 if (REG_NOTES (insn))
3374 find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
3376 if (GET_CODE (PATTERN (insn)) == SET
3377 || GET_CODE (PATTERN (insn)) == CLOBBER)
3378 count_one_set (regs, insn, PATTERN (insn), may_not_move, last_set);
3379 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3382 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3383 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
3384 may_not_move, last_set);
3388 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
3389 memset ((char *) last_set, 0, nregs * sizeof (rtx));
3397 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3398 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3399 contained in insn INSN is used by any insn that precedes INSN in
3400 cyclic order starting from the loop entry point.
3402 We don't want to use INSN_LUID here because if we restrict INSN to those
3403 that have a valid INSN_LUID, it means we cannot move an invariant out
3404 from an inner loop past two loops. */
3407 loop_reg_used_before_p (loop, set, insn)
3408 const struct loop *loop;
3411 rtx reg = SET_DEST (set);
3414 /* Scan forward checking for register usage. If we hit INSN, we
3415 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3416 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3418 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3428 /* A "basic induction variable" or biv is a pseudo reg that is set
3429 (within this loop) only by incrementing or decrementing it. */
3430 /* A "general induction variable" or giv is a pseudo reg whose
3431 value is a linear function of a biv. */
3433 /* Bivs are recognized by `basic_induction_var';
3434 Givs by `general_induction_var'. */
3436 /* Communication with routines called via `note_stores'. */
3438 static rtx note_insn;
3440 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3442 static rtx addr_placeholder;
3444 /* ??? Unfinished optimizations, and possible future optimizations,
3445 for the strength reduction code. */
3447 /* ??? The interaction of biv elimination, and recognition of 'constant'
3448 bivs, may cause problems. */
3450 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3451 performance problems.
3453 Perhaps don't eliminate things that can be combined with an addressing
3454 mode. Find all givs that have the same biv, mult_val, and add_val;
3455 then for each giv, check to see if its only use dies in a following
3456 memory address. If so, generate a new memory address and check to see
3457 if it is valid. If it is valid, then store the modified memory address,
3458 otherwise, mark the giv as not done so that it will get its own iv. */
3460 /* ??? Could try to optimize branches when it is known that a biv is always
3463 /* ??? When replace a biv in a compare insn, we should replace with closest
3464 giv so that an optimized branch can still be recognized by the combiner,
3465 e.g. the VAX acb insn. */
3467 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3468 was rerun in loop_optimize whenever a register was added or moved.
3469 Also, some of the optimizations could be a little less conservative. */
3471 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3472 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3475 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3476 loop iteration except for the last one.
3478 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3482 for_each_insn_in_loop (loop, fncall)
3484 loop_insn_callback fncall;
3486 /* This is 1 if current insn is not executed at least once for every loop
3488 int not_every_iteration = 0;
3489 int maybe_multiple = 0;
3490 int past_loop_latch = 0;
3494 /* If loop_scan_start points to the loop exit test, we have to be wary of
3495 subversive use of gotos inside expression statements. */
3496 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3497 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3499 /* Scan through loop to find all possible bivs. */
3501 for (p = next_insn_in_loop (loop, loop->scan_start);
3503 p = next_insn_in_loop (loop, p))
3505 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3507 /* Past CODE_LABEL, we get to insns that may be executed multiple
3508 times. The only way we can be sure that they can't is if every
3509 jump insn between here and the end of the loop either
3510 returns, exits the loop, is a jump to a location that is still
3511 behind the label, or is a jump to the loop start. */
3513 if (GET_CODE (p) == CODE_LABEL)
3521 insn = NEXT_INSN (insn);
3522 if (insn == loop->scan_start)
3524 if (insn == loop->end)
3530 if (insn == loop->scan_start)
3534 if (GET_CODE (insn) == JUMP_INSN
3535 && GET_CODE (PATTERN (insn)) != RETURN
3536 && (!any_condjump_p (insn)
3537 || (JUMP_LABEL (insn) != 0
3538 && JUMP_LABEL (insn) != loop->scan_start
3539 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3547 /* Past a jump, we get to insns for which we can't count
3548 on whether they will be executed during each iteration. */
3549 /* This code appears twice in strength_reduce. There is also similar
3550 code in scan_loop. */
3551 if (GET_CODE (p) == JUMP_INSN
3552 /* If we enter the loop in the middle, and scan around to the
3553 beginning, don't set not_every_iteration for that.
3554 This can be any kind of jump, since we want to know if insns
3555 will be executed if the loop is executed. */
3556 && !(JUMP_LABEL (p) == loop->top
3557 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3558 && any_uncondjump_p (p))
3559 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3563 /* If this is a jump outside the loop, then it also doesn't
3564 matter. Check to see if the target of this branch is on the
3565 loop->exits_labels list. */
3567 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3568 if (XEXP (label, 0) == JUMP_LABEL (p))
3572 not_every_iteration = 1;
3575 else if (GET_CODE (p) == NOTE)
3577 /* At the virtual top of a converted loop, insns are again known to
3578 be executed each iteration: logically, the loop begins here
3579 even though the exit code has been duplicated.
3581 Insns are also again known to be executed each iteration at
3582 the LOOP_CONT note. */
3583 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3584 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3586 not_every_iteration = 0;
3587 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3589 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3593 /* Note if we pass a loop latch. If we do, then we can not clear
3594 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3595 a loop since a jump before the last CODE_LABEL may have started
3596 a new loop iteration.
3598 Note that LOOP_TOP is only set for rotated loops and we need
3599 this check for all loops, so compare against the CODE_LABEL
3600 which immediately follows LOOP_START. */
3601 if (GET_CODE (p) == JUMP_INSN
3602 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3603 past_loop_latch = 1;
3605 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3606 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3607 or not an insn is known to be executed each iteration of the
3608 loop, whether or not any iterations are known to occur.
3610 Therefore, if we have just passed a label and have no more labels
3611 between here and the test insn of the loop, and we have not passed
3612 a jump to the top of the loop, then we know these insns will be
3613 executed each iteration. */
3615 if (not_every_iteration
3617 && GET_CODE (p) == CODE_LABEL
3618 && no_labels_between_p (p, loop->end)
3619 && loop_insn_first_p (p, loop->cont))
3620 not_every_iteration = 0;
3624 /* Perform strength reduction and induction variable elimination.
3626 Pseudo registers created during this function will be beyond the
3627 last valid index in several tables including regs->n_times_set and
3628 regno_last_uid. This does not cause a problem here, because the
3629 added registers cannot be givs outside of their loop, and hence
3630 will never be reconsidered. But scan_loop must check regnos to
3631 make sure they are in bounds. */
3634 strength_reduce (loop, insn_count, flags)
3639 struct loop_info *loop_info = LOOP_INFO (loop);
3640 struct loop_regs *regs = LOOP_REGS (loop);
3641 struct loop_ivs *ivs = LOOP_IVS (loop);
3643 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3644 struct iv_class *bl, **backbl;
3645 /* Ratio of extra register life span we can justify
3646 for saving an instruction. More if loop doesn't call subroutines
3647 since in that case saving an insn makes more difference
3648 and more registers are available. */
3649 /* ??? could set this to last value of threshold in move_movables */
3650 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3651 /* Map of pseudo-register replacements. */
3652 rtx *reg_map = NULL;
3656 rtx end_insert_before;
3657 int unrolled_insn_copies = 0;
3658 rtx loop_start = loop->start;
3659 rtx loop_end = loop->end;
3660 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
3662 VARRAY_INT_INIT (ivs->reg_iv_type, max_reg_before_loop, "reg_iv_type");
3663 VARRAY_GENERIC_PTR_INIT (ivs->reg_iv_info, max_reg_before_loop, "reg_iv_info");
3664 ivs->reg_biv_class = (struct iv_class **)
3665 xcalloc (max_reg_before_loop, sizeof (struct iv_class *));
3667 ivs->loop_iv_list = 0;
3668 addr_placeholder = gen_reg_rtx (Pmode);
3670 /* Save insn immediately after the loop_end. Insns inserted after loop_end
3671 must be put before this insn, so that they will appear in the right
3672 order (i.e. loop order).
3674 If loop_end is the end of the current function, then emit a
3675 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
3677 if (NEXT_INSN (loop_end) != 0)
3678 end_insert_before = NEXT_INSN (loop_end);
3680 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
3682 for_each_insn_in_loop (loop, check_insn_for_bivs);
3684 /* Scan ivs->loop_iv_list to remove all regs that proved not to be bivs.
3685 Make a sanity check against regs->n_times_set. */
3686 for (backbl = &ivs->loop_iv_list, bl = *backbl; bl; bl = bl->next)
3688 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3689 /* Above happens if register modified by subreg, etc. */
3690 /* Make sure it is not recognized as a basic induction var: */
3691 || VARRAY_INT (regs->n_times_set, bl->regno) != bl->biv_count
3692 /* If never incremented, it is invariant that we decided not to
3693 move. So leave it alone. */
3694 || ! bl->incremented)
3696 if (loop_dump_stream)
3697 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3699 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3700 ? "not induction variable"
3701 : (! bl->incremented ? "never incremented"
3704 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3711 if (loop_dump_stream)
3712 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3716 /* Exit if there are no bivs. */
3717 if (! ivs->loop_iv_list)
3719 /* Can still unroll the loop anyways, but indicate that there is no
3720 strength reduction info available. */
3721 if (flags & LOOP_UNROLL)
3722 unroll_loop (loop, insn_count, end_insert_before, 0);
3727 /* Find initial value for each biv by searching backwards from loop_start,
3728 halting at first label. Also record any test condition. */
3731 for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3735 if (GET_CODE (p) == CALL_INSN)
3739 note_stores (PATTERN (p), record_initial, ivs);
3741 /* Record any test of a biv that branches around the loop if no store
3742 between it and the start of loop. We only care about tests with
3743 constants and registers and only certain of those. */
3744 if (GET_CODE (p) == JUMP_INSN
3745 && JUMP_LABEL (p) != 0
3746 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3747 && (test = get_condition_for_loop (loop, p)) != 0
3748 && GET_CODE (XEXP (test, 0)) == REG
3749 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3750 && (bl = ivs->reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3751 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3752 && bl->init_insn == 0)
3754 /* If an NE test, we have an initial value! */
3755 if (GET_CODE (test) == NE)
3758 bl->init_set = gen_rtx_SET (VOIDmode,
3759 XEXP (test, 0), XEXP (test, 1));
3762 bl->initial_test = test;
3766 /* Look at the each biv and see if we can say anything better about its
3767 initial value from any initializing insns set up above. (This is done
3768 in two passes to avoid missing SETs in a PARALLEL.) */
3769 for (backbl = &ivs->loop_iv_list; (bl = *backbl); backbl = &bl->next)
3774 if (! bl->init_insn)
3777 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3778 is a constant, use the value of that. */
3779 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3780 && CONSTANT_P (XEXP (note, 0)))
3781 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3782 && CONSTANT_P (XEXP (note, 0))))
3783 src = XEXP (note, 0);
3785 src = SET_SRC (bl->init_set);
3787 if (loop_dump_stream)
3788 fprintf (loop_dump_stream,
3789 "Biv %d initialized at insn %d: initial value ",
3790 bl->regno, INSN_UID (bl->init_insn));
3792 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3793 || GET_MODE (src) == VOIDmode)
3794 && valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3796 bl->initial_value = src;
3798 if (loop_dump_stream)
3800 if (GET_CODE (src) == CONST_INT)
3802 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (src));
3803 fputc ('\n', loop_dump_stream);
3807 print_rtl (loop_dump_stream, src);
3808 fprintf (loop_dump_stream, "\n");
3812 /* If we can't make it a giv,
3813 let biv keep initial value of "itself". */
3814 else if (loop_dump_stream)
3815 fprintf (loop_dump_stream, "is complex\n");
3818 /* Search the loop for general induction variables. */
3820 for_each_insn_in_loop (loop, check_insn_for_givs);
3822 /* Try to calculate and save the number of loop iterations. This is
3823 set to zero if the actual number can not be calculated. This must
3824 be called after all giv's have been identified, since otherwise it may
3825 fail if the iteration variable is a giv. */
3827 loop_iterations (loop);
3829 /* Now for each giv for which we still don't know whether or not it is
3830 replaceable, check to see if it is replaceable because its final value
3831 can be calculated. This must be done after loop_iterations is called,
3832 so that final_giv_value will work correctly. */
3834 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3836 struct induction *v;
3838 for (v = bl->giv; v; v = v->next_iv)
3839 if (! v->replaceable && ! v->not_replaceable)
3840 check_final_value (loop, v);
3843 /* Try to prove that the loop counter variable (if any) is always
3844 nonnegative; if so, record that fact with a REG_NONNEG note
3845 so that "decrement and branch until zero" insn can be used. */
3846 check_dbra_loop (loop, insn_count);
3848 /* Create reg_map to hold substitutions for replaceable giv regs.
3849 Some givs might have been made from biv increments, so look at
3850 ivs->reg_iv_type for a suitable size. */
3851 reg_map_size = ivs->reg_iv_type->num_elements;
3852 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
3854 /* Examine each iv class for feasibility of strength reduction/induction
3855 variable elimination. */
3857 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3859 struct induction *v;
3862 rtx final_value = 0;
3864 /* Test whether it will be possible to eliminate this biv
3865 provided all givs are reduced. This is possible if either
3866 the reg is not used outside the loop, or we can compute
3867 what its final value will be.
3869 For architectures with a decrement_and_branch_until_zero insn,
3870 don't do this if we put a REG_NONNEG note on the endtest for
3873 /* Compare against bl->init_insn rather than loop_start.
3874 We aren't concerned with any uses of the biv between
3875 init_insn and loop_start since these won't be affected
3876 by the value of the biv elsewhere in the function, so
3877 long as init_insn doesn't use the biv itself.
3878 March 14, 1989 -- self@bayes.arc.nasa.gov */
3880 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop_end)
3882 && INSN_UID (bl->init_insn) < max_uid_for_loop
3883 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3884 #ifdef HAVE_decrement_and_branch_until_zero
3887 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3888 || ((final_value = final_biv_value (loop, bl))
3889 #ifdef HAVE_decrement_and_branch_until_zero
3893 bl->eliminable = maybe_eliminate_biv (loop, bl, 0, threshold,
3897 if (loop_dump_stream)
3899 fprintf (loop_dump_stream,
3900 "Cannot eliminate biv %d.\n",
3902 fprintf (loop_dump_stream,
3903 "First use: insn %d, last use: insn %d.\n",
3904 REGNO_FIRST_UID (bl->regno),
3905 REGNO_LAST_UID (bl->regno));
3909 /* Check each extension dependant giv in this class to see if its
3910 root biv is safe from wrapping in the interior mode. */
3911 check_ext_dependant_givs (bl, loop_info);
3913 /* Combine all giv's for this iv_class. */
3914 combine_givs (regs, bl);
3916 /* This will be true at the end, if all givs which depend on this
3917 biv have been strength reduced.
3918 We can't (currently) eliminate the biv unless this is so. */
3921 /* Check each giv in this class to see if we will benefit by reducing
3922 it. Skip giv's combined with others. */
3923 for (v = bl->giv; v; v = v->next_iv)
3925 struct induction *tv;
3928 if (v->ignore || v->same)
3931 benefit = v->benefit;
3932 PUT_MODE (test_reg, v->mode);
3933 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
3934 test_reg, test_reg);
3936 /* Reduce benefit if not replaceable, since we will insert
3937 a move-insn to replace the insn that calculates this giv.
3938 Don't do this unless the giv is a user variable, since it
3939 will often be marked non-replaceable because of the duplication
3940 of the exit code outside the loop. In such a case, the copies
3941 we insert are dead and will be deleted. So they don't have
3942 a cost. Similar situations exist. */
3943 /* ??? The new final_[bg]iv_value code does a much better job
3944 of finding replaceable giv's, and hence this code may no longer
3946 if (! v->replaceable && ! bl->eliminable
3947 && REG_USERVAR_P (v->dest_reg))
3948 benefit -= copy_cost;
3950 /* Decrease the benefit to count the add-insns that we will
3951 insert to increment the reduced reg for the giv.
3952 ??? This can overestimate the run-time cost of the additional
3953 insns, e.g. if there are multiple basic blocks that increment
3954 the biv, but only one of these blocks is executed during each
3955 iteration. There is no good way to detect cases like this with
3956 the current structure of the loop optimizer.
3957 This code is more accurate for determining code size than
3958 run-time benefits. */
3959 benefit -= add_cost * bl->biv_count;
3961 /* Decide whether to strength-reduce this giv or to leave the code
3962 unchanged (recompute it from the biv each time it is used).
3963 This decision can be made independently for each giv. */
3966 /* Attempt to guess whether autoincrement will handle some of the
3967 new add insns; if so, increase BENEFIT (undo the subtraction of
3968 add_cost that was done above). */
3969 if (v->giv_type == DEST_ADDR
3970 /* Increasing the benefit is risky, since this is only a guess.
3971 Avoid increasing register pressure in cases where there would
3972 be no other benefit from reducing this giv. */
3974 && GET_CODE (v->mult_val) == CONST_INT)
3976 if (HAVE_POST_INCREMENT
3977 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3978 benefit += add_cost * bl->biv_count;
3979 else if (HAVE_PRE_INCREMENT
3980 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3981 benefit += add_cost * bl->biv_count;
3982 else if (HAVE_POST_DECREMENT
3983 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3984 benefit += add_cost * bl->biv_count;
3985 else if (HAVE_PRE_DECREMENT
3986 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3987 benefit += add_cost * bl->biv_count;
3991 /* If an insn is not to be strength reduced, then set its ignore
3992 flag, and clear all_reduced. */
3994 /* A giv that depends on a reversed biv must be reduced if it is
3995 used after the loop exit, otherwise, it would have the wrong
3996 value after the loop exit. To make it simple, just reduce all
3997 of such giv's whether or not we know they are used after the loop
4000 if ( ! flag_reduce_all_givs && v->lifetime * threshold * benefit < insn_count
4003 if (loop_dump_stream)
4004 fprintf (loop_dump_stream,
4005 "giv of insn %d not worth while, %d vs %d.\n",
4007 v->lifetime * threshold * benefit, insn_count);
4013 /* Check that we can increment the reduced giv without a
4014 multiply insn. If not, reject it. */
4016 for (tv = bl->biv; tv; tv = tv->next_iv)
4017 if (tv->mult_val == const1_rtx
4018 && ! product_cheap_p (tv->add_val, v->mult_val))
4020 if (loop_dump_stream)
4021 fprintf (loop_dump_stream,
4022 "giv of insn %d: would need a multiply.\n",
4023 INSN_UID (v->insn));
4031 /* Check for givs whose first use is their definition and whose
4032 last use is the definition of another giv. If so, it is likely
4033 dead and should not be used to derive another giv nor to
4035 for (v = bl->giv; v; v = v->next_iv)
4038 || (v->same && v->same->ignore))
4041 if (v->giv_type == DEST_REG
4042 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4044 struct induction *v1;
4046 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4047 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4052 /* Reduce each giv that we decided to reduce. */
4054 for (v = bl->giv; v; v = v->next_iv)
4056 struct induction *tv;
4057 if (! v->ignore && v->same == 0)
4059 int auto_inc_opt = 0;
4061 /* If the code for derived givs immediately below has already
4062 allocated a new_reg, we must keep it. */
4064 v->new_reg = gen_reg_rtx (v->mode);
4067 /* If the target has auto-increment addressing modes, and
4068 this is an address giv, then try to put the increment
4069 immediately after its use, so that flow can create an
4070 auto-increment addressing mode. */
4071 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
4072 && bl->biv->always_executed && ! bl->biv->maybe_multiple
4073 /* We don't handle reversed biv's because bl->biv->insn
4074 does not have a valid INSN_LUID. */
4076 && v->always_executed && ! v->maybe_multiple
4077 && INSN_UID (v->insn) < max_uid_for_loop)
4079 /* If other giv's have been combined with this one, then
4080 this will work only if all uses of the other giv's occur
4081 before this giv's insn. This is difficult to check.
4083 We simplify this by looking for the common case where
4084 there is one DEST_REG giv, and this giv's insn is the
4085 last use of the dest_reg of that DEST_REG giv. If the
4086 increment occurs after the address giv, then we can
4087 perform the optimization. (Otherwise, the increment
4088 would have to go before other_giv, and we would not be
4089 able to combine it with the address giv to get an
4090 auto-inc address.) */
4091 if (v->combined_with)
4093 struct induction *other_giv = 0;
4095 for (tv = bl->giv; tv; tv = tv->next_iv)
4103 if (! tv && other_giv
4104 && REGNO (other_giv->dest_reg) < max_reg_before_loop
4105 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
4106 == INSN_UID (v->insn))
4107 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
4110 /* Check for case where increment is before the address
4111 giv. Do this test in "loop order". */
4112 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
4113 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
4114 || (INSN_LUID (bl->biv->insn)
4115 > INSN_LUID (loop->scan_start))))
4116 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
4117 && (INSN_LUID (loop->scan_start)
4118 < INSN_LUID (bl->biv->insn))))
4127 /* We can't put an insn immediately after one setting
4128 cc0, or immediately before one using cc0. */
4129 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
4130 || (auto_inc_opt == -1
4131 && (prev = prev_nonnote_insn (v->insn)) != 0
4133 && sets_cc0_p (PATTERN (prev))))
4139 v->auto_inc_opt = 1;
4143 /* For each place where the biv is incremented, add an insn
4144 to increment the new, reduced reg for the giv. */
4145 for (tv = bl->biv; tv; tv = tv->next_iv)
4150 insert_before = tv->insn;
4151 else if (auto_inc_opt == 1)
4152 insert_before = NEXT_INSN (v->insn);
4154 insert_before = v->insn;
4156 if (tv->mult_val == const1_rtx)
4157 emit_iv_add_mult (tv->add_val, v->mult_val,
4158 v->new_reg, v->new_reg, insert_before);
4159 else /* tv->mult_val == const0_rtx */
4160 /* A multiply is acceptable here
4161 since this is presumed to be seldom executed. */
4162 emit_iv_add_mult (tv->add_val, v->mult_val,
4163 v->add_val, v->new_reg, insert_before);
4166 /* Add code at loop start to initialize giv's reduced reg. */
4168 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4169 v->mult_val, v->add_val, v->new_reg,
4174 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4177 For each giv register that can be reduced now: if replaceable,
4178 substitute reduced reg wherever the old giv occurs;
4179 else add new move insn "giv_reg = reduced_reg". */
4181 for (v = bl->giv; v; v = v->next_iv)
4183 if (v->same && v->same->ignore)
4189 /* Update expression if this was combined, in case other giv was
4192 v->new_reg = replace_rtx (v->new_reg,
4193 v->same->dest_reg, v->same->new_reg);
4195 /* See if this register is known to be a pointer to something. If
4196 so, see if we can find the alignment. First see if there is a
4197 destination register that is a pointer. If so, this shares the
4198 alignment too. Next see if we can deduce anything from the
4199 computational information. If not, and this is a DEST_ADDR
4200 giv, at least we know that it's a pointer, though we don't know
4202 if (GET_CODE (v->new_reg) == REG
4203 && v->giv_type == DEST_REG
4204 && REG_POINTER (v->dest_reg))
4205 mark_reg_pointer (v->new_reg,
4206 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
4207 else if (GET_CODE (v->new_reg) == REG
4208 && REG_POINTER (v->src_reg))
4210 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4213 || GET_CODE (v->add_val) != CONST_INT
4214 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4217 mark_reg_pointer (v->new_reg, align);
4219 else if (GET_CODE (v->new_reg) == REG
4220 && GET_CODE (v->add_val) == REG
4221 && REG_POINTER (v->add_val))
4223 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4225 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4226 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4229 mark_reg_pointer (v->new_reg, align);
4231 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4232 mark_reg_pointer (v->new_reg, 0);
4234 if (v->giv_type == DEST_ADDR)
4235 /* Store reduced reg as the address in the memref where we found
4237 validate_change (v->insn, v->location, v->new_reg, 0);
4238 else if (v->replaceable)
4240 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4243 /* I can no longer duplicate the original problem. Perhaps
4244 this is unnecessary now? */
4246 /* Replaceable; it isn't strictly necessary to delete the old
4247 insn and emit a new one, because v->dest_reg is now dead.
4249 However, especially when unrolling loops, the special
4250 handling for (set REG0 REG1) in the second cse pass may
4251 make v->dest_reg live again. To avoid this problem, emit
4252 an insn to set the original giv reg from the reduced giv.
4253 We can not delete the original insn, since it may be part
4254 of a LIBCALL, and the code in flow that eliminates dead
4255 libcalls will fail if it is deleted. */
4256 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4262 /* Not replaceable; emit an insn to set the original giv reg from
4263 the reduced giv, same as above. */
4264 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4268 /* When a loop is reversed, givs which depend on the reversed
4269 biv, and which are live outside the loop, must be set to their
4270 correct final value. This insn is only needed if the giv is
4271 not replaceable. The correct final value is the same as the
4272 value that the giv starts the reversed loop with. */
4273 if (bl->reversed && ! v->replaceable)
4274 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4275 v->mult_val, v->add_val, v->dest_reg,
4277 else if (v->final_value)
4281 /* If the loop has multiple exits, emit the insn before the
4282 loop to ensure that it will always be executed no matter
4283 how the loop exits. Otherwise, emit the insn after the loop,
4284 since this is slightly more efficient. */
4285 if (loop->exit_count)
4286 insert_before = loop_start;
4288 insert_before = end_insert_before;
4289 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4293 /* If the insn to set the final value of the giv was emitted
4294 before the loop, then we must delete the insn inside the loop
4295 that sets it. If this is a LIBCALL, then we must delete
4296 every insn in the libcall. Note, however, that
4297 final_giv_value will only succeed when there are multiple
4298 exits if the giv is dead at each exit, hence it does not
4299 matter that the original insn remains because it is dead
4301 /* Delete the insn inside the loop that sets the giv since
4302 the giv is now set before (or after) the loop. */
4303 delete_insn (v->insn);
4307 if (loop_dump_stream)
4309 fprintf (loop_dump_stream, "giv at %d reduced to ",
4310 INSN_UID (v->insn));
4311 print_rtl (loop_dump_stream, v->new_reg);
4312 fprintf (loop_dump_stream, "\n");
4316 /* All the givs based on the biv bl have been reduced if they
4319 /* For each giv not marked as maybe dead that has been combined with a
4320 second giv, clear any "maybe dead" mark on that second giv.
4321 v->new_reg will either be or refer to the register of the giv it
4324 Doing this clearing avoids problems in biv elimination where a
4325 giv's new_reg is a complex value that can't be put in the insn but
4326 the giv combined with (with a reg as new_reg) is marked maybe_dead.
4327 Since the register will be used in either case, we'd prefer it be
4328 used from the simpler giv. */
4330 for (v = bl->giv; v; v = v->next_iv)
4331 if (! v->maybe_dead && v->same)
4332 v->same->maybe_dead = 0;
4334 /* Try to eliminate the biv, if it is a candidate.
4335 This won't work if ! all_reduced,
4336 since the givs we planned to use might not have been reduced.
4338 We have to be careful that we didn't initially think we could eliminate
4339 this biv because of a giv that we now think may be dead and shouldn't
4340 be used as a biv replacement.
4342 Also, there is the possibility that we may have a giv that looks
4343 like it can be used to eliminate a biv, but the resulting insn
4344 isn't valid. This can happen, for example, on the 88k, where a
4345 JUMP_INSN can compare a register only with zero. Attempts to
4346 replace it with a compare with a constant will fail.
4348 Note that in cases where this call fails, we may have replaced some
4349 of the occurrences of the biv with a giv, but no harm was done in
4350 doing so in the rare cases where it can occur. */
4352 if (all_reduced == 1 && bl->eliminable
4353 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4355 /* ?? If we created a new test to bypass the loop entirely,
4356 or otherwise drop straight in, based on this test, then
4357 we might want to rewrite it also. This way some later
4358 pass has more hope of removing the initialization of this
4361 /* If final_value != 0, then the biv may be used after loop end
4362 and we must emit an insn to set it just in case.
4364 Reversed bivs already have an insn after the loop setting their
4365 value, so we don't need another one. We can't calculate the
4366 proper final value for such a biv here anyways. */
4367 if (final_value != 0 && ! bl->reversed)
4371 /* If the loop has multiple exits, emit the insn before the
4372 loop to ensure that it will always be executed no matter
4373 how the loop exits. Otherwise, emit the insn after the
4374 loop, since this is slightly more efficient. */
4375 if (loop->exit_count)
4376 insert_before = loop_start;
4378 insert_before = end_insert_before;
4380 emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
4385 /* Delete all of the instructions inside the loop which set
4386 the biv, as they are all dead. If is safe to delete them,
4387 because an insn setting a biv will never be part of a libcall. */
4388 /* However, deleting them will invalidate the regno_last_uid info,
4389 so keeping them around is more convenient. Final_biv_value
4390 will only succeed when there are multiple exits if the biv
4391 is dead at each exit, hence it does not matter that the original
4392 insn remains, because it is dead anyways. */
4393 for (v = bl->biv; v; v = v->next_iv)
4394 delete_insn (v->insn);
4397 if (loop_dump_stream)
4398 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4403 /* Go through all the instructions in the loop, making all the
4404 register substitutions scheduled in REG_MAP. */
4406 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
4407 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4408 || GET_CODE (p) == CALL_INSN)
4410 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4411 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4415 if (loop_info->n_iterations > 0)
4417 /* When we completely unroll a loop we will likely not need the increment
4418 of the loop BIV and we will not need the conditional branch at the
4420 unrolled_insn_copies = insn_count - 2;
4423 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4424 need the comparison before the conditional branch at the end of the
4426 unrolled_insn_copies -= 1;
4429 /* We'll need one copy for each loop iteration. */
4430 unrolled_insn_copies *= loop_info->n_iterations;
4432 /* A little slop to account for the ability to remove initialization
4433 code, better CSE, and other secondary benefits of completely
4434 unrolling some loops. */
4435 unrolled_insn_copies -= 1;
4437 /* Clamp the value. */
4438 if (unrolled_insn_copies < 0)
4439 unrolled_insn_copies = 0;
4442 /* Unroll loops from within strength reduction so that we can use the
4443 induction variable information that strength_reduce has already
4444 collected. Always unroll loops that would be as small or smaller
4445 unrolled than when rolled. */
4446 if ((flags & LOOP_UNROLL)
4447 || (loop_info->n_iterations > 0
4448 && unrolled_insn_copies <= insn_count))
4449 unroll_loop (loop, insn_count, end_insert_before, 1);
4451 #ifdef HAVE_doloop_end
4452 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4453 doloop_optimize (loop);
4454 #endif /* HAVE_doloop_end */
4456 if (loop_dump_stream)
4457 fprintf (loop_dump_stream, "\n");
4460 VARRAY_FREE (ivs->reg_iv_type);
4461 VARRAY_FREE (ivs->reg_iv_info);
4462 free (ivs->reg_biv_class);
4464 struct iv_class *iv = ivs->loop_iv_list;
4467 struct iv_class *next = iv->next;
4468 struct induction *induction;
4469 struct induction *next_induction;
4471 for (induction = iv->biv; induction; induction = next_induction)
4473 next_induction = induction->next_iv;
4476 for (induction = iv->giv; induction; induction = next_induction)
4478 next_induction = induction->next_iv;
4490 /*Record all basic induction variables calculated in the insn. */
4492 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4495 int not_every_iteration;
4498 struct loop_ivs *ivs = LOOP_IVS (loop);
4505 if (GET_CODE (p) == INSN
4506 && (set = single_set (p))
4507 && GET_CODE (SET_DEST (set)) == REG)
4509 dest_reg = SET_DEST (set);
4510 if (REGNO (dest_reg) < max_reg_before_loop
4511 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4512 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4514 if (basic_induction_var (loop, SET_SRC (set),
4515 GET_MODE (SET_SRC (set)),
4516 dest_reg, p, &inc_val, &mult_val,
4519 /* It is a possible basic induction variable.
4520 Create and initialize an induction structure for it. */
4523 = (struct induction *) xmalloc (sizeof (struct induction));
4525 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4526 not_every_iteration, maybe_multiple);
4527 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4529 else if (REGNO (dest_reg) < max_reg_before_loop)
4530 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4536 /* Record all givs calculated in the insn.
4537 A register is a giv if: it is only set once, it is a function of a
4538 biv and a constant (or invariant), and it is not a biv. */
4540 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4543 int not_every_iteration;
4546 struct loop_regs *regs = LOOP_REGS (loop);
4549 /* Look for a general induction variable in a register. */
4550 if (GET_CODE (p) == INSN
4551 && (set = single_set (p))
4552 && GET_CODE (SET_DEST (set)) == REG
4553 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
4562 rtx last_consec_insn;
4564 dest_reg = SET_DEST (set);
4565 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4568 if (/* SET_SRC is a giv. */
4569 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4570 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4571 /* Equivalent expression is a giv. */
4572 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4573 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4574 &add_val, &mult_val, &ext_val, 0,
4575 &benefit, VOIDmode)))
4576 /* Don't try to handle any regs made by loop optimization.
4577 We have nothing on them in regno_first_uid, etc. */
4578 && REGNO (dest_reg) < max_reg_before_loop
4579 /* Don't recognize a BASIC_INDUCT_VAR here. */
4580 && dest_reg != src_reg
4581 /* This must be the only place where the register is set. */
4582 && (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) == 1
4583 /* or all sets must be consecutive and make a giv. */
4584 || (benefit = consec_sets_giv (loop, benefit, p,
4586 &add_val, &mult_val, &ext_val,
4587 &last_consec_insn))))
4590 = (struct induction *) xmalloc (sizeof (struct induction));
4592 /* If this is a library call, increase benefit. */
4593 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4594 benefit += libcall_benefit (p);
4596 /* Skip the consecutive insns, if there are any. */
4597 if (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) != 1)
4598 p = last_consec_insn;
4600 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4601 ext_val, benefit, DEST_REG, not_every_iteration,
4602 maybe_multiple, NULL_PTR);
4607 #ifndef DONT_REDUCE_ADDR
4608 /* Look for givs which are memory addresses. */
4609 /* This resulted in worse code on a VAX 8600. I wonder if it
4611 if (GET_CODE (p) == INSN)
4612 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4616 /* Update the status of whether giv can derive other givs. This can
4617 change when we pass a label or an insn that updates a biv. */
4618 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4619 || GET_CODE (p) == CODE_LABEL)
4620 update_giv_derive (loop, p);
4624 /* Return 1 if X is a valid source for an initial value (or as value being
4625 compared against in an initial test).
4627 X must be either a register or constant and must not be clobbered between
4628 the current insn and the start of the loop.
4630 INSN is the insn containing X. */
4633 valid_initial_value_p (x, insn, call_seen, loop_start)
4642 /* Only consider pseudos we know about initialized in insns whose luids
4644 if (GET_CODE (x) != REG
4645 || REGNO (x) >= max_reg_before_loop)
4648 /* Don't use call-clobbered registers across a call which clobbers it. On
4649 some machines, don't use any hard registers at all. */
4650 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4651 && (SMALL_REGISTER_CLASSES
4652 || (call_used_regs[REGNO (x)] && call_seen)))
4655 /* Don't use registers that have been clobbered before the start of the
4657 if (reg_set_between_p (x, insn, loop_start))
4663 /* Scan X for memory refs and check each memory address
4664 as a possible giv. INSN is the insn whose pattern X comes from.
4665 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4666 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4667 more thanonce in each loop iteration. */
4670 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4671 const struct loop *loop;
4674 int not_every_iteration, maybe_multiple;
4677 register enum rtx_code code;
4678 register const char *fmt;
4683 code = GET_CODE (x);
4708 /* This code used to disable creating GIVs with mult_val == 1 and
4709 add_val == 0. However, this leads to lost optimizations when
4710 it comes time to combine a set of related DEST_ADDR GIVs, since
4711 this one would not be seen. */
4713 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4714 &mult_val, &ext_val, 1, &benefit,
4717 /* Found one; record it. */
4719 = (struct induction *) xmalloc (sizeof (struct induction));
4721 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4722 add_val, ext_val, benefit, DEST_ADDR,
4723 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4725 v->mem_mode = GET_MODE (x);
4734 /* Recursively scan the subexpressions for other mem refs. */
4736 fmt = GET_RTX_FORMAT (code);
4737 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4739 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4741 else if (fmt[i] == 'E')
4742 for (j = 0; j < XVECLEN (x, i); j++)
4743 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4747 /* Fill in the data about one biv update.
4748 V is the `struct induction' in which we record the biv. (It is
4749 allocated by the caller, with alloca.)
4750 INSN is the insn that sets it.
4751 DEST_REG is the biv's reg.
4753 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4754 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4755 being set to INC_VAL.
4757 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4758 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4759 can be executed more than once per iteration. If MAYBE_MULTIPLE
4760 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4761 executed exactly once per iteration. */
4764 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4765 not_every_iteration, maybe_multiple)
4767 struct induction *v;
4773 int not_every_iteration;
4776 struct loop_ivs *ivs = LOOP_IVS (loop);
4777 struct iv_class *bl;
4780 v->src_reg = dest_reg;
4781 v->dest_reg = dest_reg;
4782 v->mult_val = mult_val;
4783 v->add_val = inc_val;
4784 v->ext_dependant = NULL_RTX;
4785 v->location = location;
4786 v->mode = GET_MODE (dest_reg);
4787 v->always_computable = ! not_every_iteration;
4788 v->always_executed = ! not_every_iteration;
4789 v->maybe_multiple = maybe_multiple;
4791 /* Add this to the reg's iv_class, creating a class
4792 if this is the first incrementation of the reg. */
4794 bl = ivs->reg_biv_class[REGNO (dest_reg)];
4797 /* Create and initialize new iv_class. */
4799 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4801 bl->regno = REGNO (dest_reg);
4807 /* Set initial value to the reg itself. */
4808 bl->initial_value = dest_reg;
4809 /* We haven't seen the initializing insn yet */
4812 bl->initial_test = 0;
4813 bl->incremented = 0;
4817 bl->total_benefit = 0;
4819 /* Add this class to ivs->loop_iv_list. */
4820 bl->next = ivs->loop_iv_list;
4821 ivs->loop_iv_list = bl;
4823 /* Put it in the array of biv register classes. */
4824 ivs->reg_biv_class[REGNO (dest_reg)] = bl;
4827 /* Update IV_CLASS entry for this biv. */
4828 v->next_iv = bl->biv;
4831 if (mult_val == const1_rtx)
4832 bl->incremented = 1;
4834 if (loop_dump_stream)
4836 fprintf (loop_dump_stream,
4837 "Insn %d: possible biv, reg %d,",
4838 INSN_UID (insn), REGNO (dest_reg));
4839 if (GET_CODE (inc_val) == CONST_INT)
4841 fprintf (loop_dump_stream, " const =");
4842 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4843 fputc ('\n', loop_dump_stream);
4847 fprintf (loop_dump_stream, " const = ");
4848 print_rtl (loop_dump_stream, inc_val);
4849 fprintf (loop_dump_stream, "\n");
4854 /* Fill in the data about one giv.
4855 V is the `struct induction' in which we record the giv. (It is
4856 allocated by the caller, with alloca.)
4857 INSN is the insn that sets it.
4858 BENEFIT estimates the savings from deleting this insn.
4859 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4860 into a register or is used as a memory address.
4862 SRC_REG is the biv reg which the giv is computed from.
4863 DEST_REG is the giv's reg (if the giv is stored in a reg).
4864 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4865 LOCATION points to the place where this giv's value appears in INSN. */
4868 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4869 benefit, type, not_every_iteration, maybe_multiple, location)
4870 const struct loop *loop;
4871 struct induction *v;
4875 rtx mult_val, add_val, ext_val;
4878 int not_every_iteration, maybe_multiple;
4881 struct loop_ivs *ivs = LOOP_IVS (loop);
4882 struct induction *b;
4883 struct iv_class *bl;
4884 rtx set = single_set (insn);
4887 /* Attempt to prove constantness of the values. */
4888 temp = simplify_rtx (add_val);
4893 v->src_reg = src_reg;
4895 v->dest_reg = dest_reg;
4896 v->mult_val = mult_val;
4897 v->add_val = add_val;
4898 v->ext_dependant = ext_val;
4899 v->benefit = benefit;
4900 v->location = location;
4902 v->combined_with = 0;
4903 v->maybe_multiple = maybe_multiple;
4905 v->derive_adjustment = 0;
4911 v->auto_inc_opt = 0;
4915 /* The v->always_computable field is used in update_giv_derive, to
4916 determine whether a giv can be used to derive another giv. For a
4917 DEST_REG giv, INSN computes a new value for the giv, so its value
4918 isn't computable if INSN insn't executed every iteration.
4919 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4920 it does not compute a new value. Hence the value is always computable
4921 regardless of whether INSN is executed each iteration. */
4923 if (type == DEST_ADDR)
4924 v->always_computable = 1;
4926 v->always_computable = ! not_every_iteration;
4928 v->always_executed = ! not_every_iteration;
4930 if (type == DEST_ADDR)
4932 v->mode = GET_MODE (*location);
4935 else /* type == DEST_REG */
4937 v->mode = GET_MODE (SET_DEST (set));
4939 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
4941 /* If the lifetime is zero, it means that this register is
4942 really a dead store. So mark this as a giv that can be
4943 ignored. This will not prevent the biv from being eliminated. */
4944 if (v->lifetime == 0)
4947 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
4948 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
4951 /* Add the giv to the class of givs computed from one biv. */
4953 bl = ivs->reg_biv_class[REGNO (src_reg)];
4956 v->next_iv = bl->giv;
4958 /* Don't count DEST_ADDR. This is supposed to count the number of
4959 insns that calculate givs. */
4960 if (type == DEST_REG)
4962 bl->total_benefit += benefit;
4965 /* Fatal error, biv missing for this giv? */
4968 if (type == DEST_ADDR)
4972 /* The giv can be replaced outright by the reduced register only if all
4973 of the following conditions are true:
4974 - the insn that sets the giv is always executed on any iteration
4975 on which the giv is used at all
4976 (there are two ways to deduce this:
4977 either the insn is executed on every iteration,
4978 or all uses follow that insn in the same basic block),
4979 - the giv is not used outside the loop
4980 - no assignments to the biv occur during the giv's lifetime. */
4982 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
4983 /* Previous line always fails if INSN was moved by loop opt. */
4984 && REGNO_LAST_LUID (REGNO (dest_reg))
4985 < INSN_LUID (loop->end)
4986 && (! not_every_iteration
4987 || last_use_this_basic_block (dest_reg, insn)))
4989 /* Now check that there are no assignments to the biv within the
4990 giv's lifetime. This requires two separate checks. */
4992 /* Check each biv update, and fail if any are between the first
4993 and last use of the giv.
4995 If this loop contains an inner loop that was unrolled, then
4996 the insn modifying the biv may have been emitted by the loop
4997 unrolling code, and hence does not have a valid luid. Just
4998 mark the biv as not replaceable in this case. It is not very
4999 useful as a biv, because it is used in two different loops.
5000 It is very unlikely that we would be able to optimize the giv
5001 using this biv anyways. */
5004 for (b = bl->biv; b; b = b->next_iv)
5006 if (INSN_UID (b->insn) >= max_uid_for_loop
5007 || ((INSN_LUID (b->insn)
5008 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5009 && (INSN_LUID (b->insn)
5010 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5013 v->not_replaceable = 1;
5018 /* If there are any backwards branches that go from after the
5019 biv update to before it, then this giv is not replaceable. */
5021 for (b = bl->biv; b; b = b->next_iv)
5022 if (back_branch_in_range_p (loop, b->insn))
5025 v->not_replaceable = 1;
5031 /* May still be replaceable, we don't have enough info here to
5034 v->not_replaceable = 0;
5038 /* Record whether the add_val contains a const_int, for later use by
5043 v->no_const_addval = 1;
5044 if (tem == const0_rtx)
5046 else if (CONSTANT_P (add_val))
5047 v->no_const_addval = 0;
5048 if (GET_CODE (tem) == PLUS)
5052 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5053 tem = XEXP (tem, 0);
5054 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5055 tem = XEXP (tem, 1);
5059 if (CONSTANT_P (XEXP (tem, 1)))
5060 v->no_const_addval = 0;
5064 if (loop_dump_stream)
5066 if (type == DEST_REG)
5067 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5068 INSN_UID (insn), REGNO (dest_reg));
5070 fprintf (loop_dump_stream, "Insn %d: dest address",
5073 fprintf (loop_dump_stream, " src reg %d benefit %d",
5074 REGNO (src_reg), v->benefit);
5075 fprintf (loop_dump_stream, " lifetime %d",
5079 fprintf (loop_dump_stream, " replaceable");
5081 if (v->no_const_addval)
5082 fprintf (loop_dump_stream, " ncav");
5084 if (v->ext_dependant)
5086 switch (GET_CODE (v->ext_dependant))
5089 fprintf (loop_dump_stream, " ext se");
5092 fprintf (loop_dump_stream, " ext ze");
5095 fprintf (loop_dump_stream, " ext tr");
5102 if (GET_CODE (mult_val) == CONST_INT)
5104 fprintf (loop_dump_stream, " mult ");
5105 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5109 fprintf (loop_dump_stream, " mult ");
5110 print_rtl (loop_dump_stream, mult_val);
5113 if (GET_CODE (add_val) == CONST_INT)
5115 fprintf (loop_dump_stream, " add ");
5116 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5120 fprintf (loop_dump_stream, " add ");
5121 print_rtl (loop_dump_stream, add_val);
5125 if (loop_dump_stream)
5126 fprintf (loop_dump_stream, "\n");
5130 /* All this does is determine whether a giv can be made replaceable because
5131 its final value can be calculated. This code can not be part of record_giv
5132 above, because final_giv_value requires that the number of loop iterations
5133 be known, and that can not be accurately calculated until after all givs
5134 have been identified. */
5137 check_final_value (loop, v)
5138 const struct loop *loop;
5139 struct induction *v;
5141 struct loop_ivs *ivs = LOOP_IVS (loop);
5142 struct iv_class *bl;
5143 rtx final_value = 0;
5145 bl = ivs->reg_biv_class[REGNO (v->src_reg)];
5147 /* DEST_ADDR givs will never reach here, because they are always marked
5148 replaceable above in record_giv. */
5150 /* The giv can be replaced outright by the reduced register only if all
5151 of the following conditions are true:
5152 - the insn that sets the giv is always executed on any iteration
5153 on which the giv is used at all
5154 (there are two ways to deduce this:
5155 either the insn is executed on every iteration,
5156 or all uses follow that insn in the same basic block),
5157 - its final value can be calculated (this condition is different
5158 than the one above in record_giv)
5159 - it's not used before the it's set
5160 - no assignments to the biv occur during the giv's lifetime. */
5163 /* This is only called now when replaceable is known to be false. */
5164 /* Clear replaceable, so that it won't confuse final_giv_value. */
5168 if ((final_value = final_giv_value (loop, v))
5169 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5171 int biv_increment_seen = 0, before_giv_insn = 0;
5177 /* When trying to determine whether or not a biv increment occurs
5178 during the lifetime of the giv, we can ignore uses of the variable
5179 outside the loop because final_value is true. Hence we can not
5180 use regno_last_uid and regno_first_uid as above in record_giv. */
5182 /* Search the loop to determine whether any assignments to the
5183 biv occur during the giv's lifetime. Start with the insn
5184 that sets the giv, and search around the loop until we come
5185 back to that insn again.
5187 Also fail if there is a jump within the giv's lifetime that jumps
5188 to somewhere outside the lifetime but still within the loop. This
5189 catches spaghetti code where the execution order is not linear, and
5190 hence the above test fails. Here we assume that the giv lifetime
5191 does not extend from one iteration of the loop to the next, so as
5192 to make the test easier. Since the lifetime isn't known yet,
5193 this requires two loops. See also record_giv above. */
5195 last_giv_use = v->insn;
5202 before_giv_insn = 1;
5203 p = NEXT_INSN (loop->start);
5208 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5209 || GET_CODE (p) == CALL_INSN)
5211 /* It is possible for the BIV increment to use the GIV if we
5212 have a cycle. Thus we must be sure to check each insn for
5213 both BIV and GIV uses, and we must check for BIV uses
5216 if (! biv_increment_seen
5217 && reg_set_p (v->src_reg, PATTERN (p)))
5218 biv_increment_seen = 1;
5220 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5222 if (biv_increment_seen || before_giv_insn)
5225 v->not_replaceable = 1;
5233 /* Now that the lifetime of the giv is known, check for branches
5234 from within the lifetime to outside the lifetime if it is still
5244 p = NEXT_INSN (loop->start);
5245 if (p == last_giv_use)
5248 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5249 && LABEL_NAME (JUMP_LABEL (p))
5250 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5251 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5252 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5253 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5256 v->not_replaceable = 1;
5258 if (loop_dump_stream)
5259 fprintf (loop_dump_stream,
5260 "Found branch outside giv lifetime.\n");
5267 /* If it is replaceable, then save the final value. */
5269 v->final_value = final_value;
5272 if (loop_dump_stream && v->replaceable)
5273 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5274 INSN_UID (v->insn), REGNO (v->dest_reg));
5277 /* Update the status of whether a giv can derive other givs.
5279 We need to do something special if there is or may be an update to the biv
5280 between the time the giv is defined and the time it is used to derive
5283 In addition, a giv that is only conditionally set is not allowed to
5284 derive another giv once a label has been passed.
5286 The cases we look at are when a label or an update to a biv is passed. */
5289 update_giv_derive (loop, p)
5290 const struct loop *loop;
5293 struct loop_ivs *ivs = LOOP_IVS (loop);
5294 struct iv_class *bl;
5295 struct induction *biv, *giv;
5299 /* Search all IV classes, then all bivs, and finally all givs.
5301 There are three cases we are concerned with. First we have the situation
5302 of a giv that is only updated conditionally. In that case, it may not
5303 derive any givs after a label is passed.
5305 The second case is when a biv update occurs, or may occur, after the
5306 definition of a giv. For certain biv updates (see below) that are
5307 known to occur between the giv definition and use, we can adjust the
5308 giv definition. For others, or when the biv update is conditional,
5309 we must prevent the giv from deriving any other givs. There are two
5310 sub-cases within this case.
5312 If this is a label, we are concerned with any biv update that is done
5313 conditionally, since it may be done after the giv is defined followed by
5314 a branch here (actually, we need to pass both a jump and a label, but
5315 this extra tracking doesn't seem worth it).
5317 If this is a jump, we are concerned about any biv update that may be
5318 executed multiple times. We are actually only concerned about
5319 backward jumps, but it is probably not worth performing the test
5320 on the jump again here.
5322 If this is a biv update, we must adjust the giv status to show that a
5323 subsequent biv update was performed. If this adjustment cannot be done,
5324 the giv cannot derive further givs. */
5326 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
5327 for (biv = bl->biv; biv; biv = biv->next_iv)
5328 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5331 for (giv = bl->giv; giv; giv = giv->next_iv)
5333 /* If cant_derive is already true, there is no point in
5334 checking all of these conditions again. */
5335 if (giv->cant_derive)
5338 /* If this giv is conditionally set and we have passed a label,
5339 it cannot derive anything. */
5340 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5341 giv->cant_derive = 1;
5343 /* Skip givs that have mult_val == 0, since
5344 they are really invariants. Also skip those that are
5345 replaceable, since we know their lifetime doesn't contain
5347 else if (giv->mult_val == const0_rtx || giv->replaceable)
5350 /* The only way we can allow this giv to derive another
5351 is if this is a biv increment and we can form the product
5352 of biv->add_val and giv->mult_val. In this case, we will
5353 be able to compute a compensation. */
5354 else if (biv->insn == p)
5359 if (biv->mult_val == const1_rtx)
5360 tem = simplify_giv_expr (loop,
5361 gen_rtx_MULT (giv->mode,
5364 &ext_val_dummy, &dummy);
5366 if (tem && giv->derive_adjustment)
5367 tem = simplify_giv_expr
5369 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5370 &ext_val_dummy, &dummy);
5373 giv->derive_adjustment = tem;
5375 giv->cant_derive = 1;
5377 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5378 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5379 giv->cant_derive = 1;
5384 /* Check whether an insn is an increment legitimate for a basic induction var.
5385 X is the source of insn P, or a part of it.
5386 MODE is the mode in which X should be interpreted.
5388 DEST_REG is the putative biv, also the destination of the insn.
5389 We accept patterns of these forms:
5390 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5391 REG = INVARIANT + REG
5393 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5394 store the additive term into *INC_VAL, and store the place where
5395 we found the additive term into *LOCATION.
5397 If X is an assignment of an invariant into DEST_REG, we set
5398 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5400 We also want to detect a BIV when it corresponds to a variable
5401 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5402 of the variable may be a PLUS that adds a SUBREG of that variable to
5403 an invariant and then sign- or zero-extends the result of the PLUS
5406 Most GIVs in such cases will be in the promoted mode, since that is the
5407 probably the natural computation mode (and almost certainly the mode
5408 used for addresses) on the machine. So we view the pseudo-reg containing
5409 the variable as the BIV, as if it were simply incremented.
5411 Note that treating the entire pseudo as a BIV will result in making
5412 simple increments to any GIVs based on it. However, if the variable
5413 overflows in its declared mode but not its promoted mode, the result will
5414 be incorrect. This is acceptable if the variable is signed, since
5415 overflows in such cases are undefined, but not if it is unsigned, since
5416 those overflows are defined. So we only check for SIGN_EXTEND and
5419 If we cannot find a biv, we return 0. */
5422 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5423 const struct loop *loop;
5425 enum machine_mode mode;
5432 register enum rtx_code code;
5436 code = GET_CODE (x);
5441 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5442 || (GET_CODE (XEXP (x, 0)) == SUBREG
5443 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5444 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5446 argp = &XEXP (x, 1);
5448 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5449 || (GET_CODE (XEXP (x, 1)) == SUBREG
5450 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5451 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5453 argp = &XEXP (x, 0);
5459 if (loop_invariant_p (loop, arg) != 1)
5462 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5463 *mult_val = const1_rtx;
5468 /* If this is a SUBREG for a promoted variable, check the inner
5470 if (SUBREG_PROMOTED_VAR_P (x))
5471 return basic_induction_var (loop, SUBREG_REG (x),
5472 GET_MODE (SUBREG_REG (x)),
5473 dest_reg, p, inc_val, mult_val, location);
5477 /* If this register is assigned in a previous insn, look at its
5478 source, but don't go outside the loop or past a label. */
5480 /* If this sets a register to itself, we would repeat any previous
5481 biv increment if we applied this strategy blindly. */
5482 if (rtx_equal_p (dest_reg, x))
5491 insn = PREV_INSN (insn);
5493 while (insn && GET_CODE (insn) == NOTE
5494 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5498 set = single_set (insn);
5501 dest = SET_DEST (set);
5503 || (GET_CODE (dest) == SUBREG
5504 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5505 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5506 && SUBREG_REG (dest) == x))
5507 return basic_induction_var (loop, SET_SRC (set),
5508 (GET_MODE (SET_SRC (set)) == VOIDmode
5510 : GET_MODE (SET_SRC (set))),
5512 inc_val, mult_val, location);
5514 while (GET_CODE (dest) == SIGN_EXTRACT
5515 || GET_CODE (dest) == ZERO_EXTRACT
5516 || GET_CODE (dest) == SUBREG
5517 || GET_CODE (dest) == STRICT_LOW_PART)
5518 dest = XEXP (dest, 0);
5524 /* Can accept constant setting of biv only when inside inner most loop.
5525 Otherwise, a biv of an inner loop may be incorrectly recognized
5526 as a biv of the outer loop,
5527 causing code to be moved INTO the inner loop. */
5529 if (loop_invariant_p (loop, x) != 1)
5534 /* convert_modes aborts if we try to convert to or from CCmode, so just
5535 exclude that case. It is very unlikely that a condition code value
5536 would be a useful iterator anyways. */
5537 if (loop->level == 1
5538 && GET_MODE_CLASS (mode) != MODE_CC
5539 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5541 /* Possible bug here? Perhaps we don't know the mode of X. */
5542 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5543 *mult_val = const0_rtx;
5550 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5551 dest_reg, p, inc_val, mult_val, location);
5554 /* Similar, since this can be a sign extension. */
5555 for (insn = PREV_INSN (p);
5556 (insn && GET_CODE (insn) == NOTE
5557 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5558 insn = PREV_INSN (insn))
5562 set = single_set (insn);
5564 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5565 && set && SET_DEST (set) == XEXP (x, 0)
5566 && GET_CODE (XEXP (x, 1)) == CONST_INT
5567 && INTVAL (XEXP (x, 1)) >= 0
5568 && GET_CODE (SET_SRC (set)) == ASHIFT
5569 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5570 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5571 GET_MODE (XEXP (x, 0)),
5572 dest_reg, insn, inc_val, mult_val,
5581 /* A general induction variable (giv) is any quantity that is a linear
5582 function of a basic induction variable,
5583 i.e. giv = biv * mult_val + add_val.
5584 The coefficients can be any loop invariant quantity.
5585 A giv need not be computed directly from the biv;
5586 it can be computed by way of other givs. */
5588 /* Determine whether X computes a giv.
5589 If it does, return a nonzero value
5590 which is the benefit from eliminating the computation of X;
5591 set *SRC_REG to the register of the biv that it is computed from;
5592 set *ADD_VAL and *MULT_VAL to the coefficients,
5593 such that the value of X is biv * mult + add; */
5596 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5597 is_addr, pbenefit, addr_mode)
5598 const struct loop *loop;
5606 enum machine_mode addr_mode;
5608 struct loop_ivs *ivs = LOOP_IVS (loop);
5611 /* If this is an invariant, forget it, it isn't a giv. */
5612 if (loop_invariant_p (loop, x) == 1)
5616 *ext_val = NULL_RTX;
5617 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5621 switch (GET_CODE (x))
5625 /* Since this is now an invariant and wasn't before, it must be a giv
5626 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5628 *src_reg = ivs->loop_iv_list->biv->dest_reg;
5629 *mult_val = const0_rtx;
5634 /* This is equivalent to a BIV. */
5636 *mult_val = const1_rtx;
5637 *add_val = const0_rtx;
5641 /* Either (plus (biv) (invar)) or
5642 (plus (mult (biv) (invar_1)) (invar_2)). */
5643 if (GET_CODE (XEXP (x, 0)) == MULT)
5645 *src_reg = XEXP (XEXP (x, 0), 0);
5646 *mult_val = XEXP (XEXP (x, 0), 1);
5650 *src_reg = XEXP (x, 0);
5651 *mult_val = const1_rtx;
5653 *add_val = XEXP (x, 1);
5657 /* ADD_VAL is zero. */
5658 *src_reg = XEXP (x, 0);
5659 *mult_val = XEXP (x, 1);
5660 *add_val = const0_rtx;
5667 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5668 unless they are CONST_INT). */
5669 if (GET_CODE (*add_val) == USE)
5670 *add_val = XEXP (*add_val, 0);
5671 if (GET_CODE (*mult_val) == USE)
5672 *mult_val = XEXP (*mult_val, 0);
5675 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5677 *pbenefit += rtx_cost (orig_x, SET);
5679 /* Always return true if this is a giv so it will be detected as such,
5680 even if the benefit is zero or negative. This allows elimination
5681 of bivs that might otherwise not be eliminated. */
5685 /* Given an expression, X, try to form it as a linear function of a biv.
5686 We will canonicalize it to be of the form
5687 (plus (mult (BIV) (invar_1))
5689 with possible degeneracies.
5691 The invariant expressions must each be of a form that can be used as a
5692 machine operand. We surround then with a USE rtx (a hack, but localized
5693 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5694 routine; it is the caller's responsibility to strip them.
5696 If no such canonicalization is possible (i.e., two biv's are used or an
5697 expression that is neither invariant nor a biv or giv), this routine
5700 For a non-zero return, the result will have a code of CONST_INT, USE,
5701 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5703 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5705 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5706 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5709 simplify_giv_expr (loop, x, ext_val, benefit)
5710 const struct loop *loop;
5715 struct loop_ivs *ivs = LOOP_IVS (loop);
5716 struct loop_regs *regs = LOOP_REGS (loop);
5717 enum machine_mode mode = GET_MODE (x);
5721 /* If this is not an integer mode, or if we cannot do arithmetic in this
5722 mode, this can't be a giv. */
5723 if (mode != VOIDmode
5724 && (GET_MODE_CLASS (mode) != MODE_INT
5725 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5728 switch (GET_CODE (x))
5731 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5732 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5733 if (arg0 == 0 || arg1 == 0)
5736 /* Put constant last, CONST_INT last if both constant. */
5737 if ((GET_CODE (arg0) == USE
5738 || GET_CODE (arg0) == CONST_INT)
5739 && ! ((GET_CODE (arg0) == USE
5740 && GET_CODE (arg1) == USE)
5741 || GET_CODE (arg1) == CONST_INT))
5742 tem = arg0, arg0 = arg1, arg1 = tem;
5744 /* Handle addition of zero, then addition of an invariant. */
5745 if (arg1 == const0_rtx)
5747 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5748 switch (GET_CODE (arg0))
5752 /* Adding two invariants must result in an invariant, so enclose
5753 addition operation inside a USE and return it. */
5754 if (GET_CODE (arg0) == USE)
5755 arg0 = XEXP (arg0, 0);
5756 if (GET_CODE (arg1) == USE)
5757 arg1 = XEXP (arg1, 0);
5759 if (GET_CODE (arg0) == CONST_INT)
5760 tem = arg0, arg0 = arg1, arg1 = tem;
5761 if (GET_CODE (arg1) == CONST_INT)
5762 tem = sge_plus_constant (arg0, arg1);
5764 tem = sge_plus (mode, arg0, arg1);
5766 if (GET_CODE (tem) != CONST_INT)
5767 tem = gen_rtx_USE (mode, tem);
5772 /* biv + invar or mult + invar. Return sum. */
5773 return gen_rtx_PLUS (mode, arg0, arg1);
5776 /* (a + invar_1) + invar_2. Associate. */
5778 simplify_giv_expr (loop,
5790 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5791 MULT to reduce cases. */
5792 if (GET_CODE (arg0) == REG)
5793 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5794 if (GET_CODE (arg1) == REG)
5795 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5797 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5798 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5799 Recurse to associate the second PLUS. */
5800 if (GET_CODE (arg1) == MULT)
5801 tem = arg0, arg0 = arg1, arg1 = tem;
5803 if (GET_CODE (arg1) == PLUS)
5805 simplify_giv_expr (loop,
5807 gen_rtx_PLUS (mode, arg0,
5812 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5813 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5816 if (!rtx_equal_p (arg0, arg1))
5819 return simplify_giv_expr (loop,
5828 /* Handle "a - b" as "a + b * (-1)". */
5829 return simplify_giv_expr (loop,
5838 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5839 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5840 if (arg0 == 0 || arg1 == 0)
5843 /* Put constant last, CONST_INT last if both constant. */
5844 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5845 && GET_CODE (arg1) != CONST_INT)
5846 tem = arg0, arg0 = arg1, arg1 = tem;
5848 /* If second argument is not now constant, not giv. */
5849 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5852 /* Handle multiply by 0 or 1. */
5853 if (arg1 == const0_rtx)
5856 else if (arg1 == const1_rtx)
5859 switch (GET_CODE (arg0))
5862 /* biv * invar. Done. */
5863 return gen_rtx_MULT (mode, arg0, arg1);
5866 /* Product of two constants. */
5867 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5870 /* invar * invar is a giv, but attempt to simplify it somehow. */
5871 if (GET_CODE (arg1) != CONST_INT)
5874 arg0 = XEXP (arg0, 0);
5875 if (GET_CODE (arg0) == MULT)
5877 /* (invar_0 * invar_1) * invar_2. Associate. */
5878 return simplify_giv_expr (loop,
5887 /* Porpagate the MULT expressions to the intermost nodes. */
5888 else if (GET_CODE (arg0) == PLUS)
5890 /* (invar_0 + invar_1) * invar_2. Distribute. */
5891 return simplify_giv_expr (loop,
5903 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
5906 /* (a * invar_1) * invar_2. Associate. */
5907 return simplify_giv_expr (loop,
5916 /* (a + invar_1) * invar_2. Distribute. */
5917 return simplify_giv_expr (loop,
5932 /* Shift by constant is multiply by power of two. */
5933 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5937 simplify_giv_expr (loop,
5940 GEN_INT ((HOST_WIDE_INT) 1
5941 << INTVAL (XEXP (x, 1)))),
5945 /* "-a" is "a * (-1)" */
5946 return simplify_giv_expr (loop,
5947 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
5951 /* "~a" is "-a - 1". Silly, but easy. */
5952 return simplify_giv_expr (loop,
5953 gen_rtx_MINUS (mode,
5954 gen_rtx_NEG (mode, XEXP (x, 0)),
5959 /* Already in proper form for invariant. */
5965 /* Conditionally recognize extensions of simple IVs. After we've
5966 computed loop traversal counts and verified the range of the
5967 source IV, we'll reevaluate this as a GIV. */
5968 if (*ext_val == NULL_RTX)
5970 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5971 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
5973 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
5980 /* If this is a new register, we can't deal with it. */
5981 if (REGNO (x) >= max_reg_before_loop)
5984 /* Check for biv or giv. */
5985 switch (REG_IV_TYPE (ivs, REGNO (x)))
5989 case GENERAL_INDUCT:
5991 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
5993 /* Form expression from giv and add benefit. Ensure this giv
5994 can derive another and subtract any needed adjustment if so. */
5996 /* Increasing the benefit here is risky. The only case in which it
5997 is arguably correct is if this is the only use of V. In other
5998 cases, this will artificially inflate the benefit of the current
5999 giv, and lead to suboptimal code. Thus, it is disabled, since
6000 potentially not reducing an only marginally beneficial giv is
6001 less harmful than reducing many givs that are not really
6004 rtx single_use = VARRAY_RTX (regs->single_usage, REGNO (x));
6005 if (single_use && single_use != const0_rtx)
6006 *benefit += v->benefit;
6012 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
6013 v->src_reg, v->mult_val),
6016 if (v->derive_adjustment)
6017 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
6018 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
6021 if (!v->ext_dependant)
6026 *ext_val = v->ext_dependant;
6034 /* If it isn't an induction variable, and it is invariant, we
6035 may be able to simplify things further by looking through
6036 the bits we just moved outside the loop. */
6037 if (loop_invariant_p (loop, x) == 1)
6040 struct loop_movables *movables = LOOP_MOVABLES (loop);
6042 for (m = movables->head; m; m = m->next)
6043 if (rtx_equal_p (x, m->set_dest))
6045 /* Ok, we found a match. Substitute and simplify. */
6047 /* If we match another movable, we must use that, as
6048 this one is going away. */
6050 return simplify_giv_expr (loop, m->match->set_dest,
6053 /* If consec is non-zero, this is a member of a group of
6054 instructions that were moved together. We handle this
6055 case only to the point of seeking to the last insn and
6056 looking for a REG_EQUAL. Fail if we don't find one. */
6063 tem = NEXT_INSN (tem);
6067 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6069 tem = XEXP (tem, 0);
6073 tem = single_set (m->insn);
6075 tem = SET_SRC (tem);
6080 /* What we are most interested in is pointer
6081 arithmetic on invariants -- only take
6082 patterns we may be able to do something with. */
6083 if (GET_CODE (tem) == PLUS
6084 || GET_CODE (tem) == MULT
6085 || GET_CODE (tem) == ASHIFT
6086 || GET_CODE (tem) == CONST_INT
6087 || GET_CODE (tem) == SYMBOL_REF)
6089 tem = simplify_giv_expr (loop, tem, ext_val,
6094 else if (GET_CODE (tem) == CONST
6095 && GET_CODE (XEXP (tem, 0)) == PLUS
6096 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6097 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6099 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6111 /* Fall through to general case. */
6113 /* If invariant, return as USE (unless CONST_INT).
6114 Otherwise, not giv. */
6115 if (GET_CODE (x) == USE)
6118 if (loop_invariant_p (loop, x) == 1)
6120 if (GET_CODE (x) == CONST_INT)
6122 if (GET_CODE (x) == CONST
6123 && GET_CODE (XEXP (x, 0)) == PLUS
6124 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6125 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6127 return gen_rtx_USE (mode, x);
6134 /* This routine folds invariants such that there is only ever one
6135 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6138 sge_plus_constant (x, c)
6141 if (GET_CODE (x) == CONST_INT)
6142 return GEN_INT (INTVAL (x) + INTVAL (c));
6143 else if (GET_CODE (x) != PLUS)
6144 return gen_rtx_PLUS (GET_MODE (x), x, c);
6145 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6147 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6148 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6150 else if (GET_CODE (XEXP (x, 0)) == PLUS
6151 || GET_CODE (XEXP (x, 1)) != PLUS)
6153 return gen_rtx_PLUS (GET_MODE (x),
6154 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6158 return gen_rtx_PLUS (GET_MODE (x),
6159 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6164 sge_plus (mode, x, y)
6165 enum machine_mode mode;
6168 while (GET_CODE (y) == PLUS)
6170 rtx a = XEXP (y, 0);
6171 if (GET_CODE (a) == CONST_INT)
6172 x = sge_plus_constant (x, a);
6174 x = gen_rtx_PLUS (mode, x, a);
6177 if (GET_CODE (y) == CONST_INT)
6178 x = sge_plus_constant (x, y);
6180 x = gen_rtx_PLUS (mode, x, y);
6184 /* Help detect a giv that is calculated by several consecutive insns;
6188 The caller has already identified the first insn P as having a giv as dest;
6189 we check that all other insns that set the same register follow
6190 immediately after P, that they alter nothing else,
6191 and that the result of the last is still a giv.
6193 The value is 0 if the reg set in P is not really a giv.
6194 Otherwise, the value is the amount gained by eliminating
6195 all the consecutive insns that compute the value.
6197 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6198 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6200 The coefficients of the ultimate giv value are stored in
6201 *MULT_VAL and *ADD_VAL. */
6204 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6205 add_val, mult_val, ext_val, last_consec_insn)
6206 const struct loop *loop;
6214 rtx *last_consec_insn;
6216 struct loop_ivs *ivs = LOOP_IVS (loop);
6217 struct loop_regs *regs = LOOP_REGS (loop);
6224 /* Indicate that this is a giv so that we can update the value produced in
6225 each insn of the multi-insn sequence.
6227 This induction structure will be used only by the call to
6228 general_induction_var below, so we can allocate it on our stack.
6229 If this is a giv, our caller will replace the induct var entry with
6230 a new induction structure. */
6231 struct induction *v;
6233 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6236 v = (struct induction *) alloca (sizeof (struct induction));
6237 v->src_reg = src_reg;
6238 v->mult_val = *mult_val;
6239 v->add_val = *add_val;
6240 v->benefit = first_benefit;
6242 v->derive_adjustment = 0;
6243 v->ext_dependant = NULL_RTX;
6245 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6246 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6248 count = VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) - 1;
6253 code = GET_CODE (p);
6255 /* If libcall, skip to end of call sequence. */
6256 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6260 && (set = single_set (p))
6261 && GET_CODE (SET_DEST (set)) == REG
6262 && SET_DEST (set) == dest_reg
6263 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6264 add_val, mult_val, ext_val, 0,
6266 /* Giv created by equivalent expression. */
6267 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6268 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6269 add_val, mult_val, ext_val, 0,
6270 &benefit, VOIDmode)))
6271 && src_reg == v->src_reg)
6273 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6274 benefit += libcall_benefit (p);
6277 v->mult_val = *mult_val;
6278 v->add_val = *add_val;
6279 v->benefit += benefit;
6281 else if (code != NOTE)
6283 /* Allow insns that set something other than this giv to a
6284 constant. Such insns are needed on machines which cannot
6285 include long constants and should not disqualify a giv. */
6287 && (set = single_set (p))
6288 && SET_DEST (set) != dest_reg
6289 && CONSTANT_P (SET_SRC (set)))
6292 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6297 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6298 *last_consec_insn = p;
6302 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6303 represented by G1. If no such expression can be found, or it is clear that
6304 it cannot possibly be a valid address, 0 is returned.
6306 To perform the computation, we note that
6309 where `v' is the biv.
6311 So G2 = (y/b) * G1 + (b - a*y/x).
6313 Note that MULT = y/x.
6315 Update: A and B are now allowed to be additive expressions such that
6316 B contains all variables in A. That is, computing B-A will not require
6317 subtracting variables. */
6320 express_from_1 (a, b, mult)
6323 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6325 if (mult == const0_rtx)
6328 /* If MULT is not 1, we cannot handle A with non-constants, since we
6329 would then be required to subtract multiples of the registers in A.
6330 This is theoretically possible, and may even apply to some Fortran
6331 constructs, but it is a lot of work and we do not attempt it here. */
6333 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6336 /* In general these structures are sorted top to bottom (down the PLUS
6337 chain), but not left to right across the PLUS. If B is a higher
6338 order giv than A, we can strip one level and recurse. If A is higher
6339 order, we'll eventually bail out, but won't know that until the end.
6340 If they are the same, we'll strip one level around this loop. */
6342 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6344 rtx ra, rb, oa, ob, tmp;
6346 ra = XEXP (a, 0), oa = XEXP (a, 1);
6347 if (GET_CODE (ra) == PLUS)
6348 tmp = ra, ra = oa, oa = tmp;
6350 rb = XEXP (b, 0), ob = XEXP (b, 1);
6351 if (GET_CODE (rb) == PLUS)
6352 tmp = rb, rb = ob, ob = tmp;
6354 if (rtx_equal_p (ra, rb))
6355 /* We matched: remove one reg completely. */
6357 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6358 /* An alternate match. */
6360 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6361 /* An alternate match. */
6365 /* Indicates an extra register in B. Strip one level from B and
6366 recurse, hoping B was the higher order expression. */
6367 ob = express_from_1 (a, ob, mult);
6370 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6374 /* Here we are at the last level of A, go through the cases hoping to
6375 get rid of everything but a constant. */
6377 if (GET_CODE (a) == PLUS)
6381 ra = XEXP (a, 0), oa = XEXP (a, 1);
6382 if (rtx_equal_p (oa, b))
6384 else if (!rtx_equal_p (ra, b))
6387 if (GET_CODE (oa) != CONST_INT)
6390 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6392 else if (GET_CODE (a) == CONST_INT)
6394 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6396 else if (CONSTANT_P (a))
6398 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6400 else if (GET_CODE (b) == PLUS)
6402 if (rtx_equal_p (a, XEXP (b, 0)))
6404 else if (rtx_equal_p (a, XEXP (b, 1)))
6409 else if (rtx_equal_p (a, b))
6416 express_from (g1, g2)
6417 struct induction *g1, *g2;
6421 /* The value that G1 will be multiplied by must be a constant integer. Also,
6422 the only chance we have of getting a valid address is if b*c/a (see above
6423 for notation) is also an integer. */
6424 if (GET_CODE (g1->mult_val) == CONST_INT
6425 && GET_CODE (g2->mult_val) == CONST_INT)
6427 if (g1->mult_val == const0_rtx
6428 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6430 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6432 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6436 /* ??? Find out if the one is a multiple of the other? */
6440 add = express_from_1 (g1->add_val, g2->add_val, mult);
6441 if (add == NULL_RTX)
6443 /* Failed. If we've got a multiplication factor between G1 and G2,
6444 scale G1's addend and try again. */
6445 if (INTVAL (mult) > 1)
6447 rtx g1_add_val = g1->add_val;
6448 if (GET_CODE (g1_add_val) == MULT
6449 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6452 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6453 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6454 XEXP (g1_add_val, 0), GEN_INT (m));
6458 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6462 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6465 if (add == NULL_RTX)
6468 /* Form simplified final result. */
6469 if (mult == const0_rtx)
6471 else if (mult == const1_rtx)
6472 mult = g1->dest_reg;
6474 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6476 if (add == const0_rtx)
6480 if (GET_CODE (add) == PLUS
6481 && CONSTANT_P (XEXP (add, 1)))
6483 rtx tem = XEXP (add, 1);
6484 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6488 return gen_rtx_PLUS (g2->mode, mult, add);
6492 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6493 represented by G1. This indicates that G2 should be combined with G1 and
6494 that G2 can use (either directly or via an address expression) a register
6495 used to represent G1. */
6498 combine_givs_p (g1, g2)
6499 struct induction *g1, *g2;
6503 /* With the introduction of ext dependant givs, we must care for modes.
6504 G2 must not use a wider mode than G1. */
6505 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6508 ret = comb = express_from (g1, g2);
6509 if (comb == NULL_RTX)
6511 if (g1->mode != g2->mode)
6512 ret = gen_lowpart (g2->mode, comb);
6514 /* If these givs are identical, they can be combined. We use the results
6515 of express_from because the addends are not in a canonical form, so
6516 rtx_equal_p is a weaker test. */
6517 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6518 combination to be the other way round. */
6519 if (comb == g1->dest_reg
6520 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6525 /* If G2 can be expressed as a function of G1 and that function is valid
6526 as an address and no more expensive than using a register for G2,
6527 the expression of G2 in terms of G1 can be used. */
6529 && g2->giv_type == DEST_ADDR
6530 && memory_address_p (g2->mem_mode, ret)
6531 /* ??? Looses, especially with -fforce-addr, where *g2->location
6532 will always be a register, and so anything more complicated
6536 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6538 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6549 /* Check each extension dependant giv in this class to see if its
6550 root biv is safe from wrapping in the interior mode, which would
6551 make the giv illegal. */
6554 check_ext_dependant_givs (bl, loop_info)
6555 struct iv_class *bl;
6556 struct loop_info *loop_info;
6558 int ze_ok = 0, se_ok = 0, info_ok = 0;
6559 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6560 HOST_WIDE_INT start_val;
6561 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6563 struct induction *v;
6565 /* Make sure the iteration data is available. We must have
6566 constants in order to be certain of no overflow. */
6567 /* ??? An unknown iteration count with an increment of +-1
6568 combined with friendly exit tests of against an invariant
6569 value is also ameanable to optimization. Not implemented. */
6570 if (loop_info->n_iterations > 0
6571 && bl->initial_value
6572 && GET_CODE (bl->initial_value) == CONST_INT
6573 && (incr = biv_total_increment (bl))
6574 && GET_CODE (incr) == CONST_INT
6575 /* Make sure the host can represent the arithmetic. */
6576 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6578 unsigned HOST_WIDE_INT abs_incr, total_incr;
6579 HOST_WIDE_INT s_end_val;
6583 start_val = INTVAL (bl->initial_value);
6584 u_start_val = start_val;
6586 neg_incr = 0, abs_incr = INTVAL (incr);
6587 if (INTVAL (incr) < 0)
6588 neg_incr = 1, abs_incr = -abs_incr;
6589 total_incr = abs_incr * loop_info->n_iterations;
6591 /* Check for host arithmatic overflow. */
6592 if (total_incr / loop_info->n_iterations == abs_incr)
6594 unsigned HOST_WIDE_INT u_max;
6595 HOST_WIDE_INT s_max;
6597 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6598 s_end_val = u_end_val;
6599 u_max = GET_MODE_MASK (biv_mode);
6602 /* Check zero extension of biv ok. */
6604 /* Check for host arithmatic overflow. */
6606 ? u_end_val < u_start_val
6607 : u_end_val > u_start_val)
6608 /* Check for target arithmetic overflow. */
6610 ? 1 /* taken care of with host overflow */
6611 : u_end_val <= u_max))
6616 /* Check sign extension of biv ok. */
6617 /* ??? While it is true that overflow with signed and pointer
6618 arithmetic is undefined, I fear too many programmers don't
6619 keep this fact in mind -- myself included on occasion.
6620 So leave alone with the signed overflow optimizations. */
6621 if (start_val >= -s_max - 1
6622 /* Check for host arithmatic overflow. */
6624 ? s_end_val < start_val
6625 : s_end_val > start_val)
6626 /* Check for target arithmetic overflow. */
6628 ? s_end_val >= -s_max - 1
6629 : s_end_val <= s_max))
6636 /* Invalidate givs that fail the tests. */
6637 for (v = bl->giv; v; v = v->next_iv)
6638 if (v->ext_dependant)
6640 enum rtx_code code = GET_CODE (v->ext_dependant);
6653 /* We don't know whether this value is being used as either
6654 signed or unsigned, so to safely truncate we must satisfy
6655 both. The initial check here verifies the BIV itself;
6656 once that is successful we may check its range wrt the
6660 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6661 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6663 /* We know from the above that both endpoints are nonnegative,
6664 and that there is no wrapping. Verify that both endpoints
6665 are within the (signed) range of the outer mode. */
6666 if (u_start_val <= max && u_end_val <= max)
6677 if (loop_dump_stream)
6679 fprintf (loop_dump_stream,
6680 "Verified ext dependant giv at %d of reg %d\n",
6681 INSN_UID (v->insn), bl->regno);
6686 if (loop_dump_stream)
6691 why = "biv iteration values overflowed";
6695 incr = biv_total_increment (bl);
6696 if (incr == const1_rtx)
6697 why = "biv iteration info incomplete; incr by 1";
6699 why = "biv iteration info incomplete";
6702 fprintf (loop_dump_stream,
6703 "Failed ext dependant giv at %d, %s\n",
6704 INSN_UID (v->insn), why);
6711 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6714 extend_value_for_giv (v, value)
6715 struct induction *v;
6718 rtx ext_dep = v->ext_dependant;
6723 /* Recall that check_ext_dependant_givs verified that the known bounds
6724 of a biv did not overflow or wrap with respect to the extension for
6725 the giv. Therefore, constants need no additional adjustment. */
6726 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6729 /* Otherwise, we must adjust the value to compensate for the
6730 differing modes of the biv and the giv. */
6731 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6734 struct combine_givs_stats
6741 cmp_combine_givs_stats (xp, yp)
6745 const struct combine_givs_stats * const x =
6746 (const struct combine_givs_stats *) xp;
6747 const struct combine_givs_stats * const y =
6748 (const struct combine_givs_stats *) yp;
6750 d = y->total_benefit - x->total_benefit;
6751 /* Stabilize the sort. */
6753 d = x->giv_number - y->giv_number;
6757 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6758 any other. If so, point SAME to the giv combined with and set NEW_REG to
6759 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6760 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6763 combine_givs (regs, bl)
6764 struct loop_regs *regs;
6765 struct iv_class *bl;
6767 /* Additional benefit to add for being combined multiple times. */
6768 const int extra_benefit = 3;
6770 struct induction *g1, *g2, **giv_array;
6771 int i, j, k, giv_count;
6772 struct combine_givs_stats *stats;
6775 /* Count givs, because bl->giv_count is incorrect here. */
6777 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6782 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6784 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6786 giv_array[i++] = g1;
6788 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6789 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6791 for (i = 0; i < giv_count; i++)
6797 stats[i].giv_number = i;
6799 /* If a DEST_REG GIV is used only once, do not allow it to combine
6800 with anything, for in doing so we will gain nothing that cannot
6801 be had by simply letting the GIV with which we would have combined
6802 to be reduced on its own. The losage shows up in particular with
6803 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6804 be seen elsewhere as well. */
6805 if (g1->giv_type == DEST_REG
6806 && (single_use = VARRAY_RTX (regs->single_usage,
6807 REGNO (g1->dest_reg)))
6808 && single_use != const0_rtx)
6811 this_benefit = g1->benefit;
6812 /* Add an additional weight for zero addends. */
6813 if (g1->no_const_addval)
6816 for (j = 0; j < giv_count; j++)
6822 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6824 can_combine[i * giv_count + j] = this_combine;
6825 this_benefit += g2->benefit + extra_benefit;
6828 stats[i].total_benefit = this_benefit;
6831 /* Iterate, combining until we can't. */
6833 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6835 if (loop_dump_stream)
6837 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6838 for (k = 0; k < giv_count; k++)
6840 g1 = giv_array[stats[k].giv_number];
6841 if (!g1->combined_with && !g1->same)
6842 fprintf (loop_dump_stream, " {%d, %d}",
6843 INSN_UID (giv_array[stats[k].giv_number]->insn),
6844 stats[k].total_benefit);
6846 putc ('\n', loop_dump_stream);
6849 for (k = 0; k < giv_count; k++)
6851 int g1_add_benefit = 0;
6853 i = stats[k].giv_number;
6856 /* If it has already been combined, skip. */
6857 if (g1->combined_with || g1->same)
6860 for (j = 0; j < giv_count; j++)
6863 if (g1 != g2 && can_combine[i * giv_count + j]
6864 /* If it has already been combined, skip. */
6865 && ! g2->same && ! g2->combined_with)
6869 g2->new_reg = can_combine[i * giv_count + j];
6871 g1->combined_with++;
6872 g1->lifetime += g2->lifetime;
6874 g1_add_benefit += g2->benefit;
6876 /* ??? The new final_[bg]iv_value code does a much better job
6877 of finding replaceable giv's, and hence this code may no
6878 longer be necessary. */
6879 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6880 g1_add_benefit -= copy_cost;
6882 /* To help optimize the next set of combinations, remove
6883 this giv from the benefits of other potential mates. */
6884 for (l = 0; l < giv_count; ++l)
6886 int m = stats[l].giv_number;
6887 if (can_combine[m * giv_count + j])
6888 stats[l].total_benefit -= g2->benefit + extra_benefit;
6891 if (loop_dump_stream)
6892 fprintf (loop_dump_stream,
6893 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
6894 INSN_UID (g2->insn), INSN_UID (g1->insn),
6895 g1->benefit, g1_add_benefit, g1->lifetime);
6899 /* To help optimize the next set of combinations, remove
6900 this giv from the benefits of other potential mates. */
6901 if (g1->combined_with)
6903 for (j = 0; j < giv_count; ++j)
6905 int m = stats[j].giv_number;
6906 if (can_combine[m * giv_count + i])
6907 stats[j].total_benefit -= g1->benefit + extra_benefit;
6910 g1->benefit += g1_add_benefit;
6912 /* We've finished with this giv, and everything it touched.
6913 Restart the combination so that proper weights for the
6914 rest of the givs are properly taken into account. */
6915 /* ??? Ideally we would compact the arrays at this point, so
6916 as to not cover old ground. But sanely compacting
6917 can_combine is tricky. */
6927 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
6930 emit_iv_add_mult (b, m, a, reg, insert_before)
6931 rtx b; /* initial value of basic induction variable */
6932 rtx m; /* multiplicative constant */
6933 rtx a; /* additive constant */
6934 rtx reg; /* destination register */
6940 /* Prevent unexpected sharing of these rtx. */
6944 /* Increase the lifetime of any invariants moved further in code. */
6945 update_reg_last_use (a, insert_before);
6946 update_reg_last_use (b, insert_before);
6947 update_reg_last_use (m, insert_before);
6950 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
6952 emit_move_insn (reg, result);
6953 seq = gen_sequence ();
6956 emit_insn_before (seq, insert_before);
6958 /* It is entirely possible that the expansion created lots of new
6959 registers. Iterate over the sequence we just created and
6962 if (GET_CODE (seq) == SEQUENCE)
6965 for (i = 0; i < XVECLEN (seq, 0); ++i)
6967 rtx set = single_set (XVECEXP (seq, 0, i));
6968 if (set && GET_CODE (SET_DEST (set)) == REG)
6969 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6972 else if (GET_CODE (seq) == SET
6973 && GET_CODE (SET_DEST (seq)) == REG)
6974 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
6977 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
6980 iv_add_mult_cost (b, m, a, reg)
6981 rtx b; /* initial value of basic induction variable */
6982 rtx m; /* multiplicative constant */
6983 rtx a; /* additive constant */
6984 rtx reg; /* destination register */
6990 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
6992 emit_move_insn (reg, result);
6993 last = get_last_insn ();
6996 rtx t = single_set (last);
6998 cost += rtx_cost (SET_SRC (t), SET);
6999 last = PREV_INSN (last);
7005 /* Test whether A * B can be computed without
7006 an actual multiply insn. Value is 1 if so. */
7009 product_cheap_p (a, b)
7017 /* If only one is constant, make it B. */
7018 if (GET_CODE (a) == CONST_INT)
7019 tmp = a, a = b, b = tmp;
7021 /* If first constant, both constant, so don't need multiply. */
7022 if (GET_CODE (a) == CONST_INT)
7025 /* If second not constant, neither is constant, so would need multiply. */
7026 if (GET_CODE (b) != CONST_INT)
7029 /* One operand is constant, so might not need multiply insn. Generate the
7030 code for the multiply and see if a call or multiply, or long sequence
7031 of insns is generated. */
7034 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
7035 tmp = gen_sequence ();
7038 if (GET_CODE (tmp) == SEQUENCE)
7040 if (XVEC (tmp, 0) == 0)
7042 else if (XVECLEN (tmp, 0) > 3)
7045 for (i = 0; i < XVECLEN (tmp, 0); i++)
7047 rtx insn = XVECEXP (tmp, 0, i);
7049 if (GET_CODE (insn) != INSN
7050 || (GET_CODE (PATTERN (insn)) == SET
7051 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
7052 || (GET_CODE (PATTERN (insn)) == PARALLEL
7053 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
7054 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7061 else if (GET_CODE (tmp) == SET
7062 && GET_CODE (SET_SRC (tmp)) == MULT)
7064 else if (GET_CODE (tmp) == PARALLEL
7065 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7066 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7072 /* Check to see if loop can be terminated by a "decrement and branch until
7073 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7074 Also try reversing an increment loop to a decrement loop
7075 to see if the optimization can be performed.
7076 Value is nonzero if optimization was performed. */
7078 /* This is useful even if the architecture doesn't have such an insn,
7079 because it might change a loops which increments from 0 to n to a loop
7080 which decrements from n to 0. A loop that decrements to zero is usually
7081 faster than one that increments from zero. */
7083 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7084 such as approx_final_value, biv_total_increment, loop_iterations, and
7085 final_[bg]iv_value. */
7088 check_dbra_loop (loop, insn_count)
7092 struct loop_info *loop_info = LOOP_INFO (loop);
7093 struct loop_regs *regs = LOOP_REGS (loop);
7094 struct loop_ivs *ivs = LOOP_IVS (loop);
7095 struct iv_class *bl;
7102 rtx before_comparison;
7106 int compare_and_branch;
7107 rtx loop_start = loop->start;
7108 rtx loop_end = loop->end;
7110 /* If last insn is a conditional branch, and the insn before tests a
7111 register value, try to optimize it. Otherwise, we can't do anything. */
7113 jump = PREV_INSN (loop_end);
7114 comparison = get_condition_for_loop (loop, jump);
7115 if (comparison == 0)
7117 if (!onlyjump_p (jump))
7120 /* Try to compute whether the compare/branch at the loop end is one or
7121 two instructions. */
7122 get_condition (jump, &first_compare);
7123 if (first_compare == jump)
7124 compare_and_branch = 1;
7125 else if (first_compare == prev_nonnote_insn (jump))
7126 compare_and_branch = 2;
7131 /* If more than one condition is present to control the loop, then
7132 do not proceed, as this function does not know how to rewrite
7133 loop tests with more than one condition.
7135 Look backwards from the first insn in the last comparison
7136 sequence and see if we've got another comparison sequence. */
7139 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7140 if (GET_CODE (jump1) == JUMP_INSN)
7144 /* Check all of the bivs to see if the compare uses one of them.
7145 Skip biv's set more than once because we can't guarantee that
7146 it will be zero on the last iteration. Also skip if the biv is
7147 used between its update and the test insn. */
7149 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
7151 if (bl->biv_count == 1
7152 && ! bl->biv->maybe_multiple
7153 && bl->biv->dest_reg == XEXP (comparison, 0)
7154 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7162 /* Look for the case where the basic induction variable is always
7163 nonnegative, and equals zero on the last iteration.
7164 In this case, add a reg_note REG_NONNEG, which allows the
7165 m68k DBRA instruction to be used. */
7167 if (((GET_CODE (comparison) == GT
7168 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7169 && INTVAL (XEXP (comparison, 1)) == -1)
7170 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7171 && GET_CODE (bl->biv->add_val) == CONST_INT
7172 && INTVAL (bl->biv->add_val) < 0)
7174 /* Initial value must be greater than 0,
7175 init_val % -dec_value == 0 to ensure that it equals zero on
7176 the last iteration */
7178 if (GET_CODE (bl->initial_value) == CONST_INT
7179 && INTVAL (bl->initial_value) > 0
7180 && (INTVAL (bl->initial_value)
7181 % (-INTVAL (bl->biv->add_val))) == 0)
7183 /* register always nonnegative, add REG_NOTE to branch */
7184 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7186 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7193 /* If the decrement is 1 and the value was tested as >= 0 before
7194 the loop, then we can safely optimize. */
7195 for (p = loop_start; p; p = PREV_INSN (p))
7197 if (GET_CODE (p) == CODE_LABEL)
7199 if (GET_CODE (p) != JUMP_INSN)
7202 before_comparison = get_condition_for_loop (loop, p);
7203 if (before_comparison
7204 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7205 && GET_CODE (before_comparison) == LT
7206 && XEXP (before_comparison, 1) == const0_rtx
7207 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7208 && INTVAL (bl->biv->add_val) == -1)
7210 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7212 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7220 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7221 && INTVAL (bl->biv->add_val) > 0)
7223 /* Try to change inc to dec, so can apply above optimization. */
7225 all registers modified are induction variables or invariant,
7226 all memory references have non-overlapping addresses
7227 (obviously true if only one write)
7228 allow 2 insns for the compare/jump at the end of the loop. */
7229 /* Also, we must avoid any instructions which use both the reversed
7230 biv and another biv. Such instructions will fail if the loop is
7231 reversed. We meet this condition by requiring that either
7232 no_use_except_counting is true, or else that there is only
7234 int num_nonfixed_reads = 0;
7235 /* 1 if the iteration var is used only to count iterations. */
7236 int no_use_except_counting = 0;
7237 /* 1 if the loop has no memory store, or it has a single memory store
7238 which is reversible. */
7239 int reversible_mem_store = 1;
7241 if (bl->giv_count == 0 && ! loop->exit_count)
7243 rtx bivreg = regno_reg_rtx[bl->regno];
7245 /* If there are no givs for this biv, and the only exit is the
7246 fall through at the end of the loop, then
7247 see if perhaps there are no uses except to count. */
7248 no_use_except_counting = 1;
7249 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7252 rtx set = single_set (p);
7254 if (set && GET_CODE (SET_DEST (set)) == REG
7255 && REGNO (SET_DEST (set)) == bl->regno)
7256 /* An insn that sets the biv is okay. */
7258 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7259 || p == prev_nonnote_insn (loop_end))
7260 && reg_mentioned_p (bivreg, PATTERN (p)))
7262 /* If either of these insns uses the biv and sets a pseudo
7263 that has more than one usage, then the biv has uses
7264 other than counting since it's used to derive a value
7265 that is used more than one time. */
7266 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7268 if (regs->multiple_uses)
7270 no_use_except_counting = 0;
7274 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7276 no_use_except_counting = 0;
7282 if (no_use_except_counting)
7283 /* No need to worry about MEMs. */
7285 else if (loop_info->num_mem_sets <= 1)
7287 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7289 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7291 /* If the loop has a single store, and the destination address is
7292 invariant, then we can't reverse the loop, because this address
7293 might then have the wrong value at loop exit.
7294 This would work if the source was invariant also, however, in that
7295 case, the insn should have been moved out of the loop. */
7297 if (loop_info->num_mem_sets == 1)
7299 struct induction *v;
7301 reversible_mem_store
7302 = (! loop_info->unknown_address_altered
7303 && ! loop_info->unknown_constant_address_altered
7304 && ! loop_invariant_p (loop,
7305 XEXP (XEXP (loop_info->store_mems, 0),
7308 /* If the store depends on a register that is set after the
7309 store, it depends on the initial value, and is thus not
7311 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7313 if (v->giv_type == DEST_REG
7314 && reg_mentioned_p (v->dest_reg,
7315 PATTERN (loop_info->first_loop_store_insn))
7316 && loop_insn_first_p (loop_info->first_loop_store_insn,
7318 reversible_mem_store = 0;
7325 /* This code only acts for innermost loops. Also it simplifies
7326 the memory address check by only reversing loops with
7327 zero or one memory access.
7328 Two memory accesses could involve parts of the same array,
7329 and that can't be reversed.
7330 If the biv is used only for counting, than we don't need to worry
7331 about all these things. */
7333 if ((num_nonfixed_reads <= 1
7334 && ! loop_info->has_call
7335 && ! loop_info->has_volatile
7336 && reversible_mem_store
7337 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7338 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7339 && (bl == ivs->loop_iv_list && bl->next == 0))
7340 || no_use_except_counting)
7344 /* Loop can be reversed. */
7345 if (loop_dump_stream)
7346 fprintf (loop_dump_stream, "Can reverse loop\n");
7348 /* Now check other conditions:
7350 The increment must be a constant, as must the initial value,
7351 and the comparison code must be LT.
7353 This test can probably be improved since +/- 1 in the constant
7354 can be obtained by changing LT to LE and vice versa; this is
7358 /* for constants, LE gets turned into LT */
7359 && (GET_CODE (comparison) == LT
7360 || (GET_CODE (comparison) == LE
7361 && no_use_except_counting)))
7363 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7364 rtx initial_value, comparison_value;
7366 enum rtx_code cmp_code;
7367 int comparison_const_width;
7368 unsigned HOST_WIDE_INT comparison_sign_mask;
7370 add_val = INTVAL (bl->biv->add_val);
7371 comparison_value = XEXP (comparison, 1);
7372 if (GET_MODE (comparison_value) == VOIDmode)
7373 comparison_const_width
7374 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7376 comparison_const_width
7377 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7378 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7379 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7380 comparison_sign_mask
7381 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7383 /* If the comparison value is not a loop invariant, then we
7384 can not reverse this loop.
7386 ??? If the insns which initialize the comparison value as
7387 a whole compute an invariant result, then we could move
7388 them out of the loop and proceed with loop reversal. */
7389 if (! loop_invariant_p (loop, comparison_value))
7392 if (GET_CODE (comparison_value) == CONST_INT)
7393 comparison_val = INTVAL (comparison_value);
7394 initial_value = bl->initial_value;
7396 /* Normalize the initial value if it is an integer and
7397 has no other use except as a counter. This will allow
7398 a few more loops to be reversed. */
7399 if (no_use_except_counting
7400 && GET_CODE (comparison_value) == CONST_INT
7401 && GET_CODE (initial_value) == CONST_INT)
7403 comparison_val = comparison_val - INTVAL (bl->initial_value);
7404 /* The code below requires comparison_val to be a multiple
7405 of add_val in order to do the loop reversal, so
7406 round up comparison_val to a multiple of add_val.
7407 Since comparison_value is constant, we know that the
7408 current comparison code is LT. */
7409 comparison_val = comparison_val + add_val - 1;
7411 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7412 /* We postpone overflow checks for COMPARISON_VAL here;
7413 even if there is an overflow, we might still be able to
7414 reverse the loop, if converting the loop exit test to
7416 initial_value = const0_rtx;
7419 /* First check if we can do a vanilla loop reversal. */
7420 if (initial_value == const0_rtx
7421 /* If we have a decrement_and_branch_on_count,
7422 prefer the NE test, since this will allow that
7423 instruction to be generated. Note that we must
7424 use a vanilla loop reversal if the biv is used to
7425 calculate a giv or has a non-counting use. */
7426 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7427 && defined (HAVE_decrement_and_branch_on_count)
7428 && (! (add_val == 1 && loop->vtop
7429 && (bl->biv_count == 0
7430 || no_use_except_counting)))
7432 && GET_CODE (comparison_value) == CONST_INT
7433 /* Now do postponed overflow checks on COMPARISON_VAL. */
7434 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7435 & comparison_sign_mask))
7437 /* Register will always be nonnegative, with value
7438 0 on last iteration */
7439 add_adjust = add_val;
7443 else if (add_val == 1 && loop->vtop
7444 && (bl->biv_count == 0
7445 || no_use_except_counting))
7453 if (GET_CODE (comparison) == LE)
7454 add_adjust -= add_val;
7456 /* If the initial value is not zero, or if the comparison
7457 value is not an exact multiple of the increment, then we
7458 can not reverse this loop. */
7459 if (initial_value == const0_rtx
7460 && GET_CODE (comparison_value) == CONST_INT)
7462 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7467 if (! no_use_except_counting || add_val != 1)
7471 final_value = comparison_value;
7473 /* Reset these in case we normalized the initial value
7474 and comparison value above. */
7475 if (GET_CODE (comparison_value) == CONST_INT
7476 && GET_CODE (initial_value) == CONST_INT)
7478 comparison_value = GEN_INT (comparison_val);
7480 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7482 bl->initial_value = initial_value;
7484 /* Save some info needed to produce the new insns. */
7485 reg = bl->biv->dest_reg;
7486 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7487 if (jump_label == pc_rtx)
7488 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7489 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7491 /* Set start_value; if this is not a CONST_INT, we need
7493 Initialize biv to start_value before loop start.
7494 The old initializing insn will be deleted as a
7495 dead store by flow.c. */
7496 if (initial_value == const0_rtx
7497 && GET_CODE (comparison_value) == CONST_INT)
7499 start_value = GEN_INT (comparison_val - add_adjust);
7500 emit_insn_before (gen_move_insn (reg, start_value),
7503 else if (GET_CODE (initial_value) == CONST_INT)
7505 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7506 enum machine_mode mode = GET_MODE (reg);
7507 enum insn_code icode
7508 = add_optab->handlers[(int) mode].insn_code;
7510 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7511 || ! ((*insn_data[icode].operand[1].predicate)
7512 (comparison_value, mode))
7513 || ! ((*insn_data[icode].operand[2].predicate)
7517 = gen_rtx_PLUS (mode, comparison_value, offset);
7518 emit_insn_before ((GEN_FCN (icode)
7519 (reg, comparison_value, offset)),
7521 if (GET_CODE (comparison) == LE)
7522 final_value = gen_rtx_PLUS (mode, comparison_value,
7525 else if (! add_adjust)
7527 enum machine_mode mode = GET_MODE (reg);
7528 enum insn_code icode
7529 = sub_optab->handlers[(int) mode].insn_code;
7530 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7531 || ! ((*insn_data[icode].operand[1].predicate)
7532 (comparison_value, mode))
7533 || ! ((*insn_data[icode].operand[2].predicate)
7534 (initial_value, mode)))
7537 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7538 emit_insn_before ((GEN_FCN (icode)
7539 (reg, comparison_value, initial_value)),
7543 /* We could handle the other cases too, but it'll be
7544 better to have a testcase first. */
7547 /* We may not have a single insn which can increment a reg, so
7548 create a sequence to hold all the insns from expand_inc. */
7550 expand_inc (reg, new_add_val);
7551 tem = gen_sequence ();
7554 p = emit_insn_before (tem, bl->biv->insn);
7555 delete_insn (bl->biv->insn);
7557 /* Update biv info to reflect its new status. */
7559 bl->initial_value = start_value;
7560 bl->biv->add_val = new_add_val;
7562 /* Update loop info. */
7563 loop_info->initial_value = reg;
7564 loop_info->initial_equiv_value = reg;
7565 loop_info->final_value = const0_rtx;
7566 loop_info->final_equiv_value = const0_rtx;
7567 loop_info->comparison_value = const0_rtx;
7568 loop_info->comparison_code = cmp_code;
7569 loop_info->increment = new_add_val;
7571 /* Inc LABEL_NUSES so that delete_insn will
7572 not delete the label. */
7573 LABEL_NUSES (XEXP (jump_label, 0))++;
7575 /* Emit an insn after the end of the loop to set the biv's
7576 proper exit value if it is used anywhere outside the loop. */
7577 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7579 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7580 emit_insn_after (gen_move_insn (reg, final_value),
7583 /* Delete compare/branch at end of loop. */
7584 delete_insn (PREV_INSN (loop_end));
7585 if (compare_and_branch == 2)
7586 delete_insn (first_compare);
7588 /* Add new compare/branch insn at end of loop. */
7590 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7591 GET_MODE (reg), 0, 0,
7592 XEXP (jump_label, 0));
7593 tem = gen_sequence ();
7595 emit_jump_insn_before (tem, loop_end);
7597 for (tem = PREV_INSN (loop_end);
7598 tem && GET_CODE (tem) != JUMP_INSN;
7599 tem = PREV_INSN (tem))
7603 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7609 /* Increment of LABEL_NUSES done above. */
7610 /* Register is now always nonnegative,
7611 so add REG_NONNEG note to the branch. */
7612 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7618 /* No insn may reference both the reversed and another biv or it
7619 will fail (see comment near the top of the loop reversal
7621 Earlier on, we have verified that the biv has no use except
7622 counting, or it is the only biv in this function.
7623 However, the code that computes no_use_except_counting does
7624 not verify reg notes. It's possible to have an insn that
7625 references another biv, and has a REG_EQUAL note with an
7626 expression based on the reversed biv. To avoid this case,
7627 remove all REG_EQUAL notes based on the reversed biv
7629 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7633 rtx set = single_set (p);
7634 /* If this is a set of a GIV based on the reversed biv, any
7635 REG_EQUAL notes should still be correct. */
7637 || GET_CODE (SET_DEST (set)) != REG
7638 || (size_t) REGNO (SET_DEST (set)) >= ivs->reg_iv_type->num_elements
7639 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7640 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7641 for (pnote = ®_NOTES (p); *pnote;)
7643 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7644 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7646 *pnote = XEXP (*pnote, 1);
7648 pnote = &XEXP (*pnote, 1);
7652 /* Mark that this biv has been reversed. Each giv which depends
7653 on this biv, and which is also live past the end of the loop
7654 will have to be fixed up. */
7658 if (loop_dump_stream)
7660 fprintf (loop_dump_stream, "Reversed loop");
7662 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7664 fprintf (loop_dump_stream, "\n");
7675 /* Verify whether the biv BL appears to be eliminable,
7676 based on the insns in the loop that refer to it.
7678 If ELIMINATE_P is non-zero, actually do the elimination.
7680 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7681 determine whether invariant insns should be placed inside or at the
7682 start of the loop. */
7685 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7686 const struct loop *loop;
7687 struct iv_class *bl;
7689 int threshold, insn_count;
7691 struct loop_ivs *ivs = LOOP_IVS (loop);
7692 rtx reg = bl->biv->dest_reg;
7693 rtx loop_start = loop->start;
7694 rtx loop_end = loop->end;
7697 /* Scan all insns in the loop, stopping if we find one that uses the
7698 biv in a way that we cannot eliminate. */
7700 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7702 enum rtx_code code = GET_CODE (p);
7703 rtx where = threshold >= insn_count ? loop_start : p;
7705 /* If this is a libcall that sets a giv, skip ahead to its end. */
7706 if (GET_RTX_CLASS (code) == 'i')
7708 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7712 rtx last = XEXP (note, 0);
7713 rtx set = single_set (last);
7715 if (set && GET_CODE (SET_DEST (set)) == REG)
7717 unsigned int regno = REGNO (SET_DEST (set));
7719 if (regno < max_reg_before_loop
7720 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7721 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7726 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7727 && reg_mentioned_p (reg, PATTERN (p))
7728 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7729 eliminate_p, where))
7731 if (loop_dump_stream)
7732 fprintf (loop_dump_stream,
7733 "Cannot eliminate biv %d: biv used in insn %d.\n",
7734 bl->regno, INSN_UID (p));
7741 if (loop_dump_stream)
7742 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7743 bl->regno, eliminate_p ? "was" : "can be");
7750 /* INSN and REFERENCE are instructions in the same insn chain.
7751 Return non-zero if INSN is first. */
7754 loop_insn_first_p (insn, reference)
7755 rtx insn, reference;
7759 for (p = insn, q = reference;;)
7761 /* Start with test for not first so that INSN == REFERENCE yields not
7763 if (q == insn || ! p)
7765 if (p == reference || ! q)
7768 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7769 previous insn, hence the <= comparison below does not work if
7771 if (INSN_UID (p) < max_uid_for_loop
7772 && INSN_UID (q) < max_uid_for_loop
7773 && GET_CODE (p) != NOTE)
7774 return INSN_LUID (p) <= INSN_LUID (q);
7776 if (INSN_UID (p) >= max_uid_for_loop
7777 || GET_CODE (p) == NOTE)
7779 if (INSN_UID (q) >= max_uid_for_loop)
7784 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7785 the offset that we have to take into account due to auto-increment /
7786 div derivation is zero. */
7788 biv_elimination_giv_has_0_offset (biv, giv, insn)
7789 struct induction *biv, *giv;
7792 /* If the giv V had the auto-inc address optimization applied
7793 to it, and INSN occurs between the giv insn and the biv
7794 insn, then we'd have to adjust the value used here.
7795 This is rare, so we don't bother to make this possible. */
7796 if (giv->auto_inc_opt
7797 && ((loop_insn_first_p (giv->insn, insn)
7798 && loop_insn_first_p (insn, biv->insn))
7799 || (loop_insn_first_p (biv->insn, insn)
7800 && loop_insn_first_p (insn, giv->insn))))
7806 /* If BL appears in X (part of the pattern of INSN), see if we can
7807 eliminate its use. If so, return 1. If not, return 0.
7809 If BIV does not appear in X, return 1.
7811 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7812 where extra insns should be added. Depending on how many items have been
7813 moved out of the loop, it will either be before INSN or at the start of
7817 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7818 const struct loop *loop;
7820 struct iv_class *bl;
7824 enum rtx_code code = GET_CODE (x);
7825 rtx reg = bl->biv->dest_reg;
7826 enum machine_mode mode = GET_MODE (reg);
7827 struct induction *v;
7839 /* If we haven't already been able to do something with this BIV,
7840 we can't eliminate it. */
7846 /* If this sets the BIV, it is not a problem. */
7847 if (SET_DEST (x) == reg)
7850 /* If this is an insn that defines a giv, it is also ok because
7851 it will go away when the giv is reduced. */
7852 for (v = bl->giv; v; v = v->next_iv)
7853 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7857 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7859 /* Can replace with any giv that was reduced and
7860 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7861 Require a constant for MULT_VAL, so we know it's nonzero.
7862 ??? We disable this optimization to avoid potential
7865 for (v = bl->giv; v; v = v->next_iv)
7866 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7867 && v->add_val == const0_rtx
7868 && ! v->ignore && ! v->maybe_dead && v->always_computable
7872 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7878 /* If the giv has the opposite direction of change,
7879 then reverse the comparison. */
7880 if (INTVAL (v->mult_val) < 0)
7881 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7882 const0_rtx, v->new_reg);
7886 /* We can probably test that giv's reduced reg. */
7887 if (validate_change (insn, &SET_SRC (x), new, 0))
7891 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7892 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7893 Require a constant for MULT_VAL, so we know it's nonzero.
7894 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7895 overflow problem. */
7897 for (v = bl->giv; v; v = v->next_iv)
7898 if (GET_CODE (v->mult_val) == CONST_INT
7899 && v->mult_val != const0_rtx
7900 && ! v->ignore && ! v->maybe_dead && v->always_computable
7902 && (GET_CODE (v->add_val) == SYMBOL_REF
7903 || GET_CODE (v->add_val) == LABEL_REF
7904 || GET_CODE (v->add_val) == CONST
7905 || (GET_CODE (v->add_val) == REG
7906 && REG_POINTER (v->add_val))))
7908 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7914 /* If the giv has the opposite direction of change,
7915 then reverse the comparison. */
7916 if (INTVAL (v->mult_val) < 0)
7917 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
7920 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
7921 copy_rtx (v->add_val));
7923 /* Replace biv with the giv's reduced register. */
7924 update_reg_last_use (v->add_val, insn);
7925 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7928 /* Insn doesn't support that constant or invariant. Copy it
7929 into a register (it will be a loop invariant.) */
7930 tem = gen_reg_rtx (GET_MODE (v->new_reg));
7932 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
7935 /* Substitute the new register for its invariant value in
7936 the compare expression. */
7937 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
7938 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7947 case GT: case GE: case GTU: case GEU:
7948 case LT: case LE: case LTU: case LEU:
7949 /* See if either argument is the biv. */
7950 if (XEXP (x, 0) == reg)
7951 arg = XEXP (x, 1), arg_operand = 1;
7952 else if (XEXP (x, 1) == reg)
7953 arg = XEXP (x, 0), arg_operand = 0;
7957 if (CONSTANT_P (arg))
7959 /* First try to replace with any giv that has constant positive
7960 mult_val and constant add_val. We might be able to support
7961 negative mult_val, but it seems complex to do it in general. */
7963 for (v = bl->giv; v; v = v->next_iv)
7964 if (GET_CODE (v->mult_val) == CONST_INT
7965 && INTVAL (v->mult_val) > 0
7966 && (GET_CODE (v->add_val) == SYMBOL_REF
7967 || GET_CODE (v->add_val) == LABEL_REF
7968 || GET_CODE (v->add_val) == CONST
7969 || (GET_CODE (v->add_val) == REG
7970 && REG_POINTER (v->add_val)))
7971 && ! v->ignore && ! v->maybe_dead && v->always_computable
7974 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7980 /* Replace biv with the giv's reduced reg. */
7981 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
7983 /* If all constants are actually constant integers and
7984 the derived constant can be directly placed in the COMPARE,
7986 if (GET_CODE (arg) == CONST_INT
7987 && GET_CODE (v->mult_val) == CONST_INT
7988 && GET_CODE (v->add_val) == CONST_INT)
7990 validate_change (insn, &XEXP (x, arg_operand),
7991 GEN_INT (INTVAL (arg)
7992 * INTVAL (v->mult_val)
7993 + INTVAL (v->add_val)), 1);
7997 /* Otherwise, load it into a register. */
7998 tem = gen_reg_rtx (mode);
7999 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8000 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8002 if (apply_change_group ())
8006 /* Look for giv with positive constant mult_val and nonconst add_val.
8007 Insert insns to calculate new compare value.
8008 ??? Turn this off due to possible overflow. */
8010 for (v = bl->giv; v; v = v->next_iv)
8011 if (GET_CODE (v->mult_val) == CONST_INT
8012 && INTVAL (v->mult_val) > 0
8013 && ! v->ignore && ! v->maybe_dead && v->always_computable
8019 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8025 tem = gen_reg_rtx (mode);
8027 /* Replace biv with giv's reduced register. */
8028 validate_change (insn, &XEXP (x, 1 - arg_operand),
8031 /* Compute value to compare against. */
8032 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8033 /* Use it in this insn. */
8034 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8035 if (apply_change_group ())
8039 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
8041 if (loop_invariant_p (loop, arg) == 1)
8043 /* Look for giv with constant positive mult_val and nonconst
8044 add_val. Insert insns to compute new compare value.
8045 ??? Turn this off due to possible overflow. */
8047 for (v = bl->giv; v; v = v->next_iv)
8048 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
8049 && ! v->ignore && ! v->maybe_dead && v->always_computable
8055 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8061 tem = gen_reg_rtx (mode);
8063 /* Replace biv with giv's reduced register. */
8064 validate_change (insn, &XEXP (x, 1 - arg_operand),
8067 /* Compute value to compare against. */
8068 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8070 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8071 if (apply_change_group ())
8076 /* This code has problems. Basically, you can't know when
8077 seeing if we will eliminate BL, whether a particular giv
8078 of ARG will be reduced. If it isn't going to be reduced,
8079 we can't eliminate BL. We can try forcing it to be reduced,
8080 but that can generate poor code.
8082 The problem is that the benefit of reducing TV, below should
8083 be increased if BL can actually be eliminated, but this means
8084 we might have to do a topological sort of the order in which
8085 we try to process biv. It doesn't seem worthwhile to do
8086 this sort of thing now. */
8089 /* Otherwise the reg compared with had better be a biv. */
8090 if (GET_CODE (arg) != REG
8091 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8094 /* Look for a pair of givs, one for each biv,
8095 with identical coefficients. */
8096 for (v = bl->giv; v; v = v->next_iv)
8098 struct induction *tv;
8100 if (v->ignore || v->maybe_dead || v->mode != mode)
8103 for (tv = ivs->reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
8104 if (! tv->ignore && ! tv->maybe_dead
8105 && rtx_equal_p (tv->mult_val, v->mult_val)
8106 && rtx_equal_p (tv->add_val, v->add_val)
8107 && tv->mode == mode)
8109 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8115 /* Replace biv with its giv's reduced reg. */
8116 XEXP (x, 1 - arg_operand) = v->new_reg;
8117 /* Replace other operand with the other giv's
8119 XEXP (x, arg_operand) = tv->new_reg;
8126 /* If we get here, the biv can't be eliminated. */
8130 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8131 biv is used in it, since it will be replaced. */
8132 for (v = bl->giv; v; v = v->next_iv)
8133 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8141 /* See if any subexpression fails elimination. */
8142 fmt = GET_RTX_FORMAT (code);
8143 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8148 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8149 eliminate_p, where))
8154 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8155 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8156 eliminate_p, where))
8165 /* Return nonzero if the last use of REG
8166 is in an insn following INSN in the same basic block. */
8169 last_use_this_basic_block (reg, insn)
8175 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8178 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8184 /* Called via `note_stores' to record the initial value of a biv. Here we
8185 just record the location of the set and process it later. */
8188 record_initial (dest, set, data)
8191 void *data ATTRIBUTE_UNUSED;
8193 struct loop_ivs *ivs = (struct loop_ivs *) data;
8194 struct iv_class *bl;
8196 if (GET_CODE (dest) != REG
8197 || REGNO (dest) >= max_reg_before_loop
8198 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8201 bl = ivs->reg_biv_class[REGNO (dest)];
8203 /* If this is the first set found, record it. */
8204 if (bl->init_insn == 0)
8206 bl->init_insn = note_insn;
8211 /* If any of the registers in X are "old" and currently have a last use earlier
8212 than INSN, update them to have a last use of INSN. Their actual last use
8213 will be the previous insn but it will not have a valid uid_luid so we can't
8217 update_reg_last_use (x, insn)
8221 /* Check for the case where INSN does not have a valid luid. In this case,
8222 there is no need to modify the regno_last_uid, as this can only happen
8223 when code is inserted after the loop_end to set a pseudo's final value,
8224 and hence this insn will never be the last use of x. */
8225 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8226 && INSN_UID (insn) < max_uid_for_loop
8227 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8228 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8232 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8233 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8236 update_reg_last_use (XEXP (x, i), insn);
8237 else if (fmt[i] == 'E')
8238 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8239 update_reg_last_use (XVECEXP (x, i, j), insn);
8244 /* Given an insn INSN and condition COND, return the condition in a
8245 canonical form to simplify testing by callers. Specifically:
8247 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8248 (2) Both operands will be machine operands; (cc0) will have been replaced.
8249 (3) If an operand is a constant, it will be the second operand.
8250 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8251 for GE, GEU, and LEU.
8253 If the condition cannot be understood, or is an inequality floating-point
8254 comparison which needs to be reversed, 0 will be returned.
8256 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8258 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8259 insn used in locating the condition was found. If a replacement test
8260 of the condition is desired, it should be placed in front of that
8261 insn and we will be sure that the inputs are still valid.
8263 If WANT_REG is non-zero, we wish the condition to be relative to that
8264 register, if possible. Therefore, do not canonicalize the condition
8268 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8280 int reverse_code = 0;
8281 int did_reverse_condition = 0;
8282 enum machine_mode mode;
8284 code = GET_CODE (cond);
8285 mode = GET_MODE (cond);
8286 op0 = XEXP (cond, 0);
8287 op1 = XEXP (cond, 1);
8291 code = reverse_condition (code);
8292 did_reverse_condition ^= 1;
8298 /* If we are comparing a register with zero, see if the register is set
8299 in the previous insn to a COMPARE or a comparison operation. Perform
8300 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8303 while (GET_RTX_CLASS (code) == '<'
8304 && op1 == CONST0_RTX (GET_MODE (op0))
8307 /* Set non-zero when we find something of interest. */
8311 /* If comparison with cc0, import actual comparison from compare
8315 if ((prev = prev_nonnote_insn (prev)) == 0
8316 || GET_CODE (prev) != INSN
8317 || (set = single_set (prev)) == 0
8318 || SET_DEST (set) != cc0_rtx)
8321 op0 = SET_SRC (set);
8322 op1 = CONST0_RTX (GET_MODE (op0));
8328 /* If this is a COMPARE, pick up the two things being compared. */
8329 if (GET_CODE (op0) == COMPARE)
8331 op1 = XEXP (op0, 1);
8332 op0 = XEXP (op0, 0);
8335 else if (GET_CODE (op0) != REG)
8338 /* Go back to the previous insn. Stop if it is not an INSN. We also
8339 stop if it isn't a single set or if it has a REG_INC note because
8340 we don't want to bother dealing with it. */
8342 if ((prev = prev_nonnote_insn (prev)) == 0
8343 || GET_CODE (prev) != INSN
8344 || FIND_REG_INC_NOTE (prev, 0)
8345 || (set = single_set (prev)) == 0)
8348 /* If this is setting OP0, get what it sets it to if it looks
8350 if (rtx_equal_p (SET_DEST (set), op0))
8352 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8354 /* ??? We may not combine comparisons done in a CCmode with
8355 comparisons not done in a CCmode. This is to aid targets
8356 like Alpha that have an IEEE compliant EQ instruction, and
8357 a non-IEEE compliant BEQ instruction. The use of CCmode is
8358 actually artificial, simply to prevent the combination, but
8359 should not affect other platforms.
8361 However, we must allow VOIDmode comparisons to match either
8362 CCmode or non-CCmode comparison, because some ports have
8363 modeless comparisons inside branch patterns.
8365 ??? This mode check should perhaps look more like the mode check
8366 in simplify_comparison in combine. */
8368 if ((GET_CODE (SET_SRC (set)) == COMPARE
8371 && GET_MODE_CLASS (inner_mode) == MODE_INT
8372 && (GET_MODE_BITSIZE (inner_mode)
8373 <= HOST_BITS_PER_WIDE_INT)
8374 && (STORE_FLAG_VALUE
8375 & ((HOST_WIDE_INT) 1
8376 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8377 #ifdef FLOAT_STORE_FLAG_VALUE
8379 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8380 && (REAL_VALUE_NEGATIVE
8381 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8384 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8385 && (((GET_MODE_CLASS (mode) == MODE_CC)
8386 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8387 || mode == VOIDmode || inner_mode == VOIDmode))
8389 else if (((code == EQ
8391 && (GET_MODE_BITSIZE (inner_mode)
8392 <= HOST_BITS_PER_WIDE_INT)
8393 && GET_MODE_CLASS (inner_mode) == MODE_INT
8394 && (STORE_FLAG_VALUE
8395 & ((HOST_WIDE_INT) 1
8396 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8397 #ifdef FLOAT_STORE_FLAG_VALUE
8399 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8400 && (REAL_VALUE_NEGATIVE
8401 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8404 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8405 && (((GET_MODE_CLASS (mode) == MODE_CC)
8406 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8407 || mode == VOIDmode || inner_mode == VOIDmode))
8410 /* We might have reversed a LT to get a GE here. But this wasn't
8411 actually the comparison of data, so we don't flag that we
8412 have had to reverse the condition. */
8413 did_reverse_condition ^= 1;
8421 else if (reg_set_p (op0, prev))
8422 /* If this sets OP0, but not directly, we have to give up. */
8427 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8428 code = GET_CODE (x);
8431 code = reverse_condition (code);
8432 if (code == UNKNOWN)
8434 did_reverse_condition ^= 1;
8438 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8444 /* If constant is first, put it last. */
8445 if (CONSTANT_P (op0))
8446 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8448 /* If OP0 is the result of a comparison, we weren't able to find what
8449 was really being compared, so fail. */
8450 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8453 /* Canonicalize any ordered comparison with integers involving equality
8454 if we can do computations in the relevant mode and we do not
8457 if (GET_CODE (op1) == CONST_INT
8458 && GET_MODE (op0) != VOIDmode
8459 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8461 HOST_WIDE_INT const_val = INTVAL (op1);
8462 unsigned HOST_WIDE_INT uconst_val = const_val;
8463 unsigned HOST_WIDE_INT max_val
8464 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8469 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8470 code = LT, op1 = GEN_INT (const_val + 1);
8473 /* When cross-compiling, const_val might be sign-extended from
8474 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8476 if ((HOST_WIDE_INT) (const_val & max_val)
8477 != (((HOST_WIDE_INT) 1
8478 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8479 code = GT, op1 = GEN_INT (const_val - 1);
8483 if (uconst_val < max_val)
8484 code = LTU, op1 = GEN_INT (uconst_val + 1);
8488 if (uconst_val != 0)
8489 code = GTU, op1 = GEN_INT (uconst_val - 1);
8497 /* If this was floating-point and we reversed anything other than an
8498 EQ or NE or (UN)ORDERED, return zero. */
8499 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8500 && did_reverse_condition
8501 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8503 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8507 /* Never return CC0; return zero instead. */
8512 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8515 /* Given a jump insn JUMP, return the condition that will cause it to branch
8516 to its JUMP_LABEL. If the condition cannot be understood, or is an
8517 inequality floating-point comparison which needs to be reversed, 0 will
8520 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8521 insn used in locating the condition was found. If a replacement test
8522 of the condition is desired, it should be placed in front of that
8523 insn and we will be sure that the inputs are still valid. */
8526 get_condition (jump, earliest)
8534 /* If this is not a standard conditional jump, we can't parse it. */
8535 if (GET_CODE (jump) != JUMP_INSN
8536 || ! any_condjump_p (jump))
8538 set = pc_set (jump);
8540 cond = XEXP (SET_SRC (set), 0);
8542 /* If this branches to JUMP_LABEL when the condition is false, reverse
8545 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8546 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8548 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8551 /* Similar to above routine, except that we also put an invariant last
8552 unless both operands are invariants. */
8555 get_condition_for_loop (loop, x)
8556 const struct loop *loop;
8559 rtx comparison = get_condition (x, NULL_PTR);
8562 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8563 || loop_invariant_p (loop, XEXP (comparison, 1)))
8566 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8567 XEXP (comparison, 1), XEXP (comparison, 0));
8570 /* Scan the function and determine whether it has indirect (computed) jumps.
8572 This is taken mostly from flow.c; similar code exists elsewhere
8573 in the compiler. It may be useful to put this into rtlanal.c. */
8575 indirect_jump_in_function_p (start)
8580 for (insn = start; insn; insn = NEXT_INSN (insn))
8581 if (computed_jump_p (insn))
8587 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8588 documentation for LOOP_MEMS for the definition of `appropriate'.
8589 This function is called from prescan_loop via for_each_rtx. */
8592 insert_loop_mem (mem, data)
8594 void *data ATTRIBUTE_UNUSED;
8596 struct loop_info *loop_info = data;
8603 switch (GET_CODE (m))
8609 /* We're not interested in MEMs that are only clobbered. */
8613 /* We're not interested in the MEM associated with a
8614 CONST_DOUBLE, so there's no need to traverse into this. */
8618 /* We're not interested in any MEMs that only appear in notes. */
8622 /* This is not a MEM. */
8626 /* See if we've already seen this MEM. */
8627 for (i = 0; i < loop_info->mems_idx; ++i)
8628 if (rtx_equal_p (m, loop_info->mems[i].mem))
8630 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8631 /* The modes of the two memory accesses are different. If
8632 this happens, something tricky is going on, and we just
8633 don't optimize accesses to this MEM. */
8634 loop_info->mems[i].optimize = 0;
8639 /* Resize the array, if necessary. */
8640 if (loop_info->mems_idx == loop_info->mems_allocated)
8642 if (loop_info->mems_allocated != 0)
8643 loop_info->mems_allocated *= 2;
8645 loop_info->mems_allocated = 32;
8647 loop_info->mems = (loop_mem_info *)
8648 xrealloc (loop_info->mems,
8649 loop_info->mems_allocated * sizeof (loop_mem_info));
8652 /* Actually insert the MEM. */
8653 loop_info->mems[loop_info->mems_idx].mem = m;
8654 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8655 because we can't put it in a register. We still store it in the
8656 table, though, so that if we see the same address later, but in a
8657 non-BLK mode, we'll not think we can optimize it at that point. */
8658 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8659 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8660 ++loop_info->mems_idx;
8665 /* Like load_mems, but also ensures that REGS->SET_IN_LOOP,
8666 REGS->MAY_NOT_OPTIMIZE, REGS->SINGLE_USAGE, and INSN_COUNT have the correct
8667 values after load_mems. */
8670 load_mems_and_recount_loop_regs_set (loop, insn_count)
8671 const struct loop *loop;
8674 struct loop_regs *regs = LOOP_REGS (loop);
8675 int nregs = max_reg_num ();
8679 /* Recalculate regs->set_in_loop and friends since load_mems may have
8680 created new registers. */
8681 if (max_reg_num () > nregs)
8687 nregs = max_reg_num ();
8689 if ((unsigned) nregs > regs->set_in_loop->num_elements)
8691 /* Grow all the arrays. */
8692 VARRAY_GROW (regs->set_in_loop, nregs);
8693 VARRAY_GROW (regs->n_times_set, nregs);
8694 VARRAY_GROW (regs->may_not_optimize, nregs);
8695 VARRAY_GROW (regs->single_usage, nregs);
8697 /* Clear the arrays */
8698 memset ((char *) ®s->set_in_loop->data, 0, nregs * sizeof (int));
8699 memset ((char *) ®s->may_not_optimize->data, 0, nregs * sizeof (char));
8700 memset ((char *) ®s->single_usage->data, 0, nregs * sizeof (rtx));
8702 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
8705 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8707 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8708 VARRAY_INT (regs->set_in_loop, i) = 1;
8711 #ifdef AVOID_CCMODE_COPIES
8712 /* Don't try to move insns which set CC registers if we should not
8713 create CCmode register copies. */
8714 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8715 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8716 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8719 /* Set regs->n_times_set for the new registers. */
8720 bcopy ((char *) (®s->set_in_loop->data.i[0] + old_nregs),
8721 (char *) (®s->n_times_set->data.i[0] + old_nregs),
8722 (nregs - old_nregs) * sizeof (int));
8726 /* Move MEMs into registers for the duration of the loop. */
8730 const struct loop *loop;
8732 struct loop_info *loop_info = LOOP_INFO (loop);
8733 struct loop_regs *regs = LOOP_REGS (loop);
8734 int maybe_never = 0;
8737 rtx label = NULL_RTX;
8739 /* Nonzero if the next instruction may never be executed. */
8740 int next_maybe_never = 0;
8741 int last_max_reg = max_reg_num ();
8743 if (loop_info->mems_idx == 0)
8746 /* We cannot use next_label here because it skips over normal insns. */
8747 end_label = next_nonnote_insn (loop->end);
8748 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8749 end_label = NULL_RTX;
8751 /* Check to see if it's possible that some instructions in the loop are
8752 never executed. Also check if there is a goto out of the loop other
8753 than right after the end of the loop. */
8754 for (p = next_insn_in_loop (loop, loop->scan_start);
8755 p != NULL_RTX && ! maybe_never;
8756 p = next_insn_in_loop (loop, p))
8758 if (GET_CODE (p) == CODE_LABEL)
8760 else if (GET_CODE (p) == JUMP_INSN
8761 /* If we enter the loop in the middle, and scan
8762 around to the beginning, don't set maybe_never
8763 for that. This must be an unconditional jump,
8764 otherwise the code at the top of the loop might
8765 never be executed. Unconditional jumps are
8766 followed a by barrier then loop end. */
8767 && ! (GET_CODE (p) == JUMP_INSN
8768 && JUMP_LABEL (p) == loop->top
8769 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8770 && any_uncondjump_p (p)))
8772 /* If this is a jump outside of the loop but not right
8773 after the end of the loop, we would have to emit new fixup
8774 sequences for each such label. */
8775 if (JUMP_LABEL (p) != end_label
8776 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8777 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8778 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8781 if (!any_condjump_p (p))
8782 /* Something complicated. */
8785 /* If there are any more instructions in the loop, they
8786 might not be reached. */
8787 next_maybe_never = 1;
8789 else if (next_maybe_never)
8793 /* Find start of the extended basic block that enters the loop. */
8794 for (p = loop->start;
8795 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8801 /* Build table of mems that get set to constant values before the
8803 for (; p != loop->start; p = NEXT_INSN (p))
8804 cselib_process_insn (p);
8806 /* Actually move the MEMs. */
8807 for (i = 0; i < loop_info->mems_idx; ++i)
8809 regset_head load_copies;
8810 regset_head store_copies;
8813 rtx mem = loop_info->mems[i].mem;
8816 if (MEM_VOLATILE_P (mem)
8817 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8818 /* There's no telling whether or not MEM is modified. */
8819 loop_info->mems[i].optimize = 0;
8821 /* Go through the MEMs written to in the loop to see if this
8822 one is aliased by one of them. */
8823 mem_list_entry = loop_info->store_mems;
8824 while (mem_list_entry)
8826 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8828 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8831 /* MEM is indeed aliased by this store. */
8832 loop_info->mems[i].optimize = 0;
8835 mem_list_entry = XEXP (mem_list_entry, 1);
8838 if (flag_float_store && written
8839 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8840 loop_info->mems[i].optimize = 0;
8842 /* If this MEM is written to, we must be sure that there
8843 are no reads from another MEM that aliases this one. */
8844 if (loop_info->mems[i].optimize && written)
8848 for (j = 0; j < loop_info->mems_idx; ++j)
8852 else if (true_dependence (mem,
8854 loop_info->mems[j].mem,
8857 /* It's not safe to hoist loop_info->mems[i] out of
8858 the loop because writes to it might not be
8859 seen by reads from loop_info->mems[j]. */
8860 loop_info->mems[i].optimize = 0;
8866 if (maybe_never && may_trap_p (mem))
8867 /* We can't access the MEM outside the loop; it might
8868 cause a trap that wouldn't have happened otherwise. */
8869 loop_info->mems[i].optimize = 0;
8871 if (!loop_info->mems[i].optimize)
8872 /* We thought we were going to lift this MEM out of the
8873 loop, but later discovered that we could not. */
8876 INIT_REG_SET (&load_copies);
8877 INIT_REG_SET (&store_copies);
8879 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8880 order to keep scan_loop from moving stores to this MEM
8881 out of the loop just because this REG is neither a
8882 user-variable nor used in the loop test. */
8883 reg = gen_reg_rtx (GET_MODE (mem));
8884 REG_USERVAR_P (reg) = 1;
8885 loop_info->mems[i].reg = reg;
8887 /* Now, replace all references to the MEM with the
8888 corresponding pesudos. */
8890 for (p = next_insn_in_loop (loop, loop->scan_start);
8892 p = next_insn_in_loop (loop, p))
8898 set = single_set (p);
8900 /* See if this copies the mem into a register that isn't
8901 modified afterwards. We'll try to do copy propagation
8902 a little further on. */
8904 /* @@@ This test is _way_ too conservative. */
8906 && GET_CODE (SET_DEST (set)) == REG
8907 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
8908 && REGNO (SET_DEST (set)) < last_max_reg
8909 && VARRAY_INT (regs->n_times_set,
8910 REGNO (SET_DEST (set))) == 1
8911 && rtx_equal_p (SET_SRC (set), mem))
8912 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
8914 /* See if this copies the mem from a register that isn't
8915 modified afterwards. We'll try to remove the
8916 redundant copy later on by doing a little register
8917 renaming and copy propagation. This will help
8918 to untangle things for the BIV detection code. */
8921 && GET_CODE (SET_SRC (set)) == REG
8922 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
8923 && REGNO (SET_SRC (set)) < last_max_reg
8924 && VARRAY_INT (regs->n_times_set, REGNO (SET_SRC (set))) == 1
8925 && rtx_equal_p (SET_DEST (set), mem))
8926 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
8928 /* Replace the memory reference with the shadow register. */
8929 replace_loop_mems (p, loop_info->mems[i].mem,
8930 loop_info->mems[i].reg);
8933 if (GET_CODE (p) == CODE_LABEL
8934 || GET_CODE (p) == JUMP_INSN)
8938 if (! apply_change_group ())
8939 /* We couldn't replace all occurrences of the MEM. */
8940 loop_info->mems[i].optimize = 0;
8943 /* Load the memory immediately before LOOP->START, which is
8944 the NOTE_LOOP_BEG. */
8945 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
8949 struct elt_loc_list *const_equiv = 0;
8953 struct elt_loc_list *equiv;
8954 struct elt_loc_list *best_equiv = 0;
8955 for (equiv = e->locs; equiv; equiv = equiv->next)
8957 if (CONSTANT_P (equiv->loc))
8958 const_equiv = equiv;
8959 else if (GET_CODE (equiv->loc) == REG
8960 /* Extending hard register lifetimes cuases crash
8961 on SRC targets. Doing so on non-SRC is
8962 probably also not good idea, since we most
8963 probably have pseudoregister equivalence as
8965 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
8968 /* Use the constant equivalence if that is cheap enough. */
8970 best_equiv = const_equiv;
8971 else if (const_equiv
8972 && (rtx_cost (const_equiv->loc, SET)
8973 <= rtx_cost (best_equiv->loc, SET)))
8975 best_equiv = const_equiv;
8979 /* If best_equiv is nonzero, we know that MEM is set to a
8980 constant or register before the loop. We will use this
8981 knowledge to initialize the shadow register with that
8982 constant or reg rather than by loading from MEM. */
8984 best = copy_rtx (best_equiv->loc);
8986 set = gen_move_insn (reg, best);
8987 set = emit_insn_before (set, loop->start);
8989 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
8990 copy_rtx (const_equiv->loc),
8995 if (label == NULL_RTX)
8997 label = gen_label_rtx ();
8998 emit_label_after (label, loop->end);
9001 /* Store the memory immediately after END, which is
9002 the NOTE_LOOP_END. */
9003 set = gen_move_insn (copy_rtx (mem), reg);
9004 emit_insn_after (set, label);
9007 if (loop_dump_stream)
9009 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9010 REGNO (reg), (written ? "r/w" : "r/o"));
9011 print_rtl (loop_dump_stream, mem);
9012 fputc ('\n', loop_dump_stream);
9015 /* Attempt a bit of copy propagation. This helps untangle the
9016 data flow, and enables {basic,general}_induction_var to find
9018 EXECUTE_IF_SET_IN_REG_SET
9019 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9021 try_copy_prop (loop, reg, j);
9023 CLEAR_REG_SET (&load_copies);
9025 EXECUTE_IF_SET_IN_REG_SET
9026 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9028 try_swap_copy_prop (loop, reg, j);
9030 CLEAR_REG_SET (&store_copies);
9034 if (label != NULL_RTX && end_label != NULL_RTX)
9036 /* Now, we need to replace all references to the previous exit
9037 label with the new one. */
9042 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9044 for_each_rtx (&p, replace_label, &rr);
9046 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9047 field. This is not handled by for_each_rtx because it doesn't
9048 handle unprinted ('0') fields. We need to update JUMP_LABEL
9049 because the immediately following unroll pass will use it.
9050 replace_label would not work anyways, because that only handles
9052 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9053 JUMP_LABEL (p) = label;
9060 /* For communication between note_reg_stored and its caller. */
9061 struct note_reg_stored_arg
9067 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9070 note_reg_stored (x, setter, arg)
9071 rtx x, setter ATTRIBUTE_UNUSED;
9074 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9079 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9080 There must be exactly one insn that sets this pseudo; it will be
9081 deleted if all replacements succeed and we can prove that the register
9082 is not used after the loop. */
9085 try_copy_prop (loop, replacement, regno)
9086 const struct loop *loop;
9090 /* This is the reg that we are copying from. */
9091 rtx reg_rtx = regno_reg_rtx[regno];
9094 /* These help keep track of whether we replaced all uses of the reg. */
9095 int replaced_last = 0;
9096 int store_is_first = 0;
9098 for (insn = next_insn_in_loop (loop, loop->scan_start);
9100 insn = next_insn_in_loop (loop, insn))
9104 /* Only substitute within one extended basic block from the initializing
9106 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9109 if (! INSN_P (insn))
9112 /* Is this the initializing insn? */
9113 set = single_set (insn);
9115 && GET_CODE (SET_DEST (set)) == REG
9116 && REGNO (SET_DEST (set)) == regno)
9122 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9126 /* Only substitute after seeing the initializing insn. */
9127 if (init_insn && insn != init_insn)
9129 struct note_reg_stored_arg arg;
9131 replace_loop_regs (insn, reg_rtx, replacement);
9132 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9135 /* Stop replacing when REPLACEMENT is modified. */
9136 arg.reg = replacement;
9138 note_stores (PATTERN (insn), note_reg_stored, &arg);
9145 if (apply_change_group ())
9147 if (loop_dump_stream)
9148 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9149 if (store_is_first && replaced_last)
9151 PUT_CODE (init_insn, NOTE);
9152 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9153 if (loop_dump_stream)
9154 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9155 INSN_UID (init_insn));
9157 if (loop_dump_stream)
9158 fprintf (loop_dump_stream, ".\n");
9162 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9163 loop LOOP if the order of the sets of these registers can be
9164 swapped. There must be exactly one insn within the loop that sets
9165 this pseudo followed immediately by a move insn that sets
9166 REPLACEMENT with REGNO. */
9168 try_swap_copy_prop (loop, replacement, regno)
9169 const struct loop *loop;
9175 unsigned int new_regno;
9177 new_regno = REGNO (replacement);
9179 for (insn = next_insn_in_loop (loop, loop->scan_start);
9181 insn = next_insn_in_loop (loop, insn))
9183 /* Search for the insn that copies REGNO to NEW_REGNO? */
9184 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9185 && (set = single_set (insn))
9186 && GET_CODE (SET_DEST (set)) == REG
9187 && REGNO (SET_DEST (set)) == new_regno
9188 && GET_CODE (SET_SRC (set)) == REG
9189 && REGNO (SET_SRC (set)) == regno)
9193 if (insn != NULL_RTX)
9198 /* Some DEF-USE info would come in handy here to make this
9199 function more general. For now, just check the previous insn
9200 which is the most likely candidate for setting REGNO. */
9202 prev_insn = PREV_INSN (insn);
9204 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9205 && (prev_set = single_set (prev_insn))
9206 && GET_CODE (SET_DEST (prev_set)) == REG
9207 && REGNO (SET_DEST (prev_set)) == regno)
9210 (set (reg regno) (expr))
9211 (set (reg new_regno) (reg regno))
9213 so try converting this to:
9214 (set (reg new_regno) (expr))
9215 (set (reg regno) (reg new_regno))
9217 The former construct is often generated when a global
9218 variable used for an induction variable is shadowed by a
9219 register (NEW_REGNO). The latter construct improves the
9220 chances of GIV replacement and BIV elimination. */
9222 validate_change (prev_insn, &SET_DEST (prev_set),
9224 validate_change (insn, &SET_DEST (set),
9226 validate_change (insn, &SET_SRC (set),
9229 if (apply_change_group ())
9231 if (loop_dump_stream)
9232 fprintf (loop_dump_stream,
9233 " Swapped set of reg %d at %d with reg %d at %d.\n",
9234 regno, INSN_UID (insn),
9235 new_regno, INSN_UID (prev_insn));
9237 /* Update first use of REGNO. */
9238 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9239 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9241 /* Now perform copy propagation to hopefully
9242 remove all uses of REGNO within the loop. */
9243 try_copy_prop (loop, replacement, regno);
9249 /* Replace MEM with its associated pseudo register. This function is
9250 called from load_mems via for_each_rtx. DATA is actually a pointer
9251 to a structure describing the instruction currently being scanned
9252 and the MEM we are currently replacing. */
9255 replace_loop_mem (mem, data)
9259 loop_replace_args *args = (loop_replace_args *) data;
9265 switch (GET_CODE (m))
9271 /* We're not interested in the MEM associated with a
9272 CONST_DOUBLE, so there's no need to traverse into one. */
9276 /* This is not a MEM. */
9280 if (!rtx_equal_p (args->match, m))
9281 /* This is not the MEM we are currently replacing. */
9284 /* Actually replace the MEM. */
9285 validate_change (args->insn, mem, args->replacement, 1);
9291 replace_loop_mems (insn, mem, reg)
9296 loop_replace_args args;
9300 args.replacement = reg;
9302 for_each_rtx (&insn, replace_loop_mem, &args);
9305 /* Replace one register with another. Called through for_each_rtx; PX points
9306 to the rtx being scanned. DATA is actually a pointer to
9307 a structure of arguments. */
9310 replace_loop_reg (px, data)
9315 loop_replace_args *args = (loop_replace_args *) data;
9320 if (x == args->match)
9321 validate_change (args->insn, px, args->replacement, 1);
9327 replace_loop_regs (insn, reg, replacement)
9332 loop_replace_args args;
9336 args.replacement = replacement;
9338 for_each_rtx (&insn, replace_loop_reg, &args);
9341 /* Replace occurrences of the old exit label for the loop with the new
9342 one. DATA is an rtx_pair containing the old and new labels,
9346 replace_label (x, data)
9351 rtx old_label = ((rtx_pair *) data)->r1;
9352 rtx new_label = ((rtx_pair *) data)->r2;
9357 if (GET_CODE (l) != LABEL_REF)
9360 if (XEXP (l, 0) != old_label)
9363 XEXP (l, 0) = new_label;
9364 ++LABEL_NUSES (new_label);
9365 --LABEL_NUSES (old_label);
9370 #define LOOP_BLOCK_NUM_1(INSN) \
9371 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9373 /* The notes do not have an assigned block, so look at the next insn. */
9374 #define LOOP_BLOCK_NUM(INSN) \
9375 ((INSN) ? (GET_CODE (INSN) == NOTE \
9376 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9377 : LOOP_BLOCK_NUM_1 (INSN)) \
9380 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9383 loop_dump_aux (loop, file, verbose)
9384 const struct loop *loop;
9386 int verbose ATTRIBUTE_UNUSED;
9390 if (! loop || ! file)
9393 /* Print diagnostics to compare our concept of a loop with
9394 what the loop notes say. */
9395 if (! PREV_INSN (loop->first->head)
9396 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9397 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9398 != NOTE_INSN_LOOP_BEG)
9399 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9400 INSN_UID (PREV_INSN (loop->first->head)));
9401 if (! NEXT_INSN (loop->last->end)
9402 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9403 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9404 != NOTE_INSN_LOOP_END)
9405 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9406 INSN_UID (NEXT_INSN (loop->last->end)));
9411 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9412 LOOP_BLOCK_NUM (loop->start),
9413 LOOP_INSN_UID (loop->start),
9414 LOOP_BLOCK_NUM (loop->cont),
9415 LOOP_INSN_UID (loop->cont),
9416 LOOP_BLOCK_NUM (loop->cont),
9417 LOOP_INSN_UID (loop->cont),
9418 LOOP_BLOCK_NUM (loop->vtop),
9419 LOOP_INSN_UID (loop->vtop),
9420 LOOP_BLOCK_NUM (loop->end),
9421 LOOP_INSN_UID (loop->end));
9422 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9423 LOOP_BLOCK_NUM (loop->top),
9424 LOOP_INSN_UID (loop->top),
9425 LOOP_BLOCK_NUM (loop->scan_start),
9426 LOOP_INSN_UID (loop->scan_start));
9427 fprintf (file, ";; exit_count %d", loop->exit_count);
9428 if (loop->exit_count)
9430 fputs (", labels:", file);
9431 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9433 fprintf (file, " %d ",
9434 LOOP_INSN_UID (XEXP (label, 0)));
9439 /* This can happen when a marked loop appears as two nested loops,
9440 say from while (a || b) {}. The inner loop won't match
9441 the loop markers but the outer one will. */
9442 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9443 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9447 /* Call this function from the debugger to dump LOOP. */
9451 const struct loop *loop;
9453 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9456 /* Call this function from the debugger to dump LOOPS. */
9460 const struct loops *loops;
9462 flow_loops_dump (loops, stderr, loop_dump_aux, 1);
OSDN Git Service
