1 /* Perform various loop optimizations, including strength reduction.
2 Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
22 /* This is the loop optimization pass of the compiler.
23 It finds invariant computations within loops and moves them
24 to the beginning of the loop. Then it identifies basic and
25 general induction variables. Strength reduction is applied to the general
26 induction variables, and induction variable elimination is applied to
27 the basic induction variables.
29 It also finds cases where
30 a register is set within the loop by zero-extending a narrower value
31 and changes these to zero the entire register once before the loop
32 and merely copy the low part within the loop.
34 Most of the complexity is in heuristics to decide when it is worth
35 while to do these things. */
44 #include "hard-reg-set.h"
45 #include "basic-block.h"
46 #include "insn-config.h"
47 #include "insn-flags.h"
57 #define LOOP_REG_LIFETIME(LOOP, REGNO) \
58 ((REGNO_LAST_LUID (REGNO) - REGNO_FIRST_LUID (REGNO)))
60 #define LOOP_REG_GLOBAL_P(LOOP, REGNO) \
61 ((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
62 || REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start)))
65 /* Vector mapping INSN_UIDs to luids.
66 The luids are like uids but increase monotonically always.
67 We use them to see whether a jump comes from outside a given loop. */
71 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
72 number the insn is contained in. */
74 struct loop **uid_loop;
76 /* 1 + largest uid of any insn. */
80 /* 1 + luid of last insn. */
84 /* Number of loops detected in current function. Used as index to the
87 static int max_loop_num;
89 /* Bound on pseudo register number before loop optimization.
90 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
91 unsigned int max_reg_before_loop;
93 /* The value to pass to the next call of reg_scan_update. */
94 static int loop_max_reg;
96 #define obstack_chunk_alloc xmalloc
97 #define obstack_chunk_free free
99 /* During the analysis of a loop, a chain of `struct movable's
100 is made to record all the movable insns found.
101 Then the entire chain can be scanned to decide which to move. */
105 rtx insn; /* A movable insn */
106 rtx set_src; /* The expression this reg is set from. */
107 rtx set_dest; /* The destination of this SET. */
108 rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
109 of any registers used within the LIBCALL. */
110 int consec; /* Number of consecutive following insns
111 that must be moved with this one. */
112 unsigned int regno; /* The register it sets */
113 short lifetime; /* lifetime of that register;
114 may be adjusted when matching movables
115 that load the same value are found. */
116 short savings; /* Number of insns we can move for this reg,
117 including other movables that force this
118 or match this one. */
119 unsigned int cond : 1; /* 1 if only conditionally movable */
120 unsigned int force : 1; /* 1 means MUST move this insn */
121 unsigned int global : 1; /* 1 means reg is live outside this loop */
122 /* If PARTIAL is 1, GLOBAL means something different:
123 that the reg is live outside the range from where it is set
124 to the following label. */
125 unsigned int done : 1; /* 1 inhibits further processing of this */
127 unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
128 In particular, moving it does not make it
130 unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
131 load SRC, rather than copying INSN. */
132 unsigned int move_insn_first:1;/* Same as above, if this is necessary for the
133 first insn of a consecutive sets group. */
134 unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
135 enum machine_mode savemode; /* Nonzero means it is a mode for a low part
136 that we should avoid changing when clearing
137 the rest of the reg. */
138 struct movable *match; /* First entry for same value */
139 struct movable *forces; /* An insn that must be moved if this is */
140 struct movable *next;
144 FILE *loop_dump_stream;
146 /* Forward declarations. */
148 static void find_and_verify_loops PARAMS ((rtx, struct loops *));
149 static void mark_loop_jump PARAMS ((rtx, struct loop *));
150 static void prescan_loop PARAMS ((struct loop *));
151 static int reg_in_basic_block_p PARAMS ((rtx, rtx));
152 static int consec_sets_invariant_p PARAMS ((const struct loop *,
154 static int labels_in_range_p PARAMS ((rtx, int));
155 static void count_one_set PARAMS ((struct loop_regs *, rtx, rtx,
156 varray_type, rtx *));
158 static void count_loop_regs_set PARAMS ((const struct loop*,
159 varray_type, varray_type,
161 static void note_addr_stored PARAMS ((rtx, rtx, void *));
162 static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
163 static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
164 static void scan_loop PARAMS ((struct loop*, int));
166 static void replace_call_address PARAMS ((rtx, rtx, rtx));
168 static rtx skip_consec_insns PARAMS ((rtx, int));
169 static int libcall_benefit PARAMS ((rtx));
170 static void ignore_some_movables PARAMS ((struct loop_movables *));
171 static void force_movables PARAMS ((struct loop_movables *));
172 static void combine_movables PARAMS ((struct loop_movables *,
173 struct loop_regs *));
174 static int regs_match_p PARAMS ((rtx, rtx, struct loop_movables *));
175 static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct loop_movables *,
176 struct loop_regs *));
177 static void add_label_notes PARAMS ((rtx, rtx));
178 static void move_movables PARAMS ((struct loop *loop, struct loop_movables *,
180 static void loop_movables_add PARAMS((struct loop_movables *,
182 static void loop_movables_free PARAMS((struct loop_movables *));
183 static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
184 static void loop_bivs_find PARAMS((struct loop *));
185 static void loop_bivs_init_find PARAMS((struct loop *));
186 static void loop_bivs_check PARAMS((struct loop *));
187 static void loop_givs_find PARAMS((struct loop *));
188 static void loop_givs_check PARAMS((struct loop *));
189 static int loop_biv_eliminable_p PARAMS((struct loop *, struct iv_class *,
191 static int loop_giv_reduce_benefit PARAMS((struct loop *, struct iv_class *,
192 struct induction *, rtx));
193 static void loop_givs_dead_check PARAMS((struct loop *, struct iv_class *));
194 static void loop_givs_reduce PARAMS((struct loop *, struct iv_class *));
195 static void loop_givs_rescan PARAMS((struct loop *, struct iv_class *,
197 static void loop_ivs_free PARAMS((struct loop *));
198 static void strength_reduce PARAMS ((struct loop *, int, int));
199 static void find_single_use_in_loop PARAMS ((rtx, rtx, varray_type));
200 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
201 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
202 static void record_biv PARAMS ((struct loop *, struct induction *,
203 rtx, rtx, rtx, rtx, rtx *,
205 static void check_final_value PARAMS ((const struct loop *,
206 struct induction *));
207 static void record_giv PARAMS ((const struct loop *, struct induction *,
208 rtx, rtx, rtx, rtx, rtx, rtx, int,
209 enum g_types, int, int, rtx *));
210 static void update_giv_derive PARAMS ((const struct loop *, rtx));
211 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
212 struct loop_info *));
213 static int basic_induction_var PARAMS ((const struct loop *, rtx,
214 enum machine_mode, rtx, rtx,
215 rtx *, rtx *, rtx **));
216 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
217 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
218 rtx *, rtx *, rtx *, int, int *,
220 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
221 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
222 static int check_dbra_loop PARAMS ((struct loop *, int));
223 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
224 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
225 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
226 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
227 static int product_cheap_p PARAMS ((rtx, rtx));
228 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
230 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
231 struct iv_class *, int, rtx));
232 static int last_use_this_basic_block PARAMS ((rtx, rtx));
233 static void record_initial PARAMS ((rtx, rtx, void *));
234 static void update_reg_last_use PARAMS ((rtx, rtx));
235 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
236 static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
238 static void load_mems PARAMS ((const struct loop *));
239 static int insert_loop_mem PARAMS ((rtx *, void *));
240 static int replace_loop_mem PARAMS ((rtx *, void *));
241 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
242 static int replace_loop_reg PARAMS ((rtx *, void *));
243 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
244 static void note_reg_stored PARAMS ((rtx, rtx, void *));
245 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
246 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
248 static int replace_label PARAMS ((rtx *, void *));
249 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
250 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
251 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
253 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
254 void debug_loop PARAMS ((const struct loop *));
255 void debug_loops PARAMS ((const struct loops *));
257 typedef struct rtx_pair
263 typedef struct loop_replace_args
270 /* Nonzero iff INSN is between START and END, inclusive. */
271 #define INSN_IN_RANGE_P(INSN, START, END) \
272 (INSN_UID (INSN) < max_uid_for_loop \
273 && INSN_LUID (INSN) >= INSN_LUID (START) \
274 && INSN_LUID (INSN) <= INSN_LUID (END))
276 /* Indirect_jump_in_function is computed once per function. */
277 static int indirect_jump_in_function;
278 static int indirect_jump_in_function_p PARAMS ((rtx));
280 static int compute_luids PARAMS ((rtx, rtx, int));
282 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
286 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
287 copy the value of the strength reduced giv to its original register. */
288 static int copy_cost;
290 /* Cost of using a register, to normalize the benefits of a giv. */
291 static int reg_address_cost;
296 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
298 reg_address_cost = address_cost (reg, SImode);
300 copy_cost = COSTS_N_INSNS (1);
303 /* Compute the mapping from uids to luids.
304 LUIDs are numbers assigned to insns, like uids,
305 except that luids increase monotonically through the code.
306 Start at insn START and stop just before END. Assign LUIDs
307 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
309 compute_luids (start, end, prev_luid)
316 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
318 if (INSN_UID (insn) >= max_uid_for_loop)
320 /* Don't assign luids to line-number NOTEs, so that the distance in
321 luids between two insns is not affected by -g. */
322 if (GET_CODE (insn) != NOTE
323 || NOTE_LINE_NUMBER (insn) <= 0)
324 uid_luid[INSN_UID (insn)] = ++i;
326 /* Give a line number note the same luid as preceding insn. */
327 uid_luid[INSN_UID (insn)] = i;
332 /* Entry point of this file. Perform loop optimization
333 on the current function. F is the first insn of the function
334 and DUMPFILE is a stream for output of a trace of actions taken
335 (or 0 if none should be output). */
338 loop_optimize (f, dumpfile, flags)
339 /* f is the first instruction of a chain of insns for one function */
346 struct loops loops_data;
347 struct loops *loops = &loops_data;
348 struct loop_info *loops_info;
349 static char *moved_once;
351 loop_dump_stream = dumpfile;
353 init_recog_no_volatile ();
355 max_reg_before_loop = max_reg_num ();
356 loop_max_reg = max_reg_before_loop;
360 /* Count the number of loops. */
363 for (insn = f; insn; insn = NEXT_INSN (insn))
365 if (GET_CODE (insn) == NOTE
366 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
370 /* Don't waste time if no loops. */
371 if (max_loop_num == 0)
374 loops->num = max_loop_num;
376 moved_once = (char *) xcalloc (max_reg_before_loop, sizeof (char));
378 /* Get size to use for tables indexed by uids.
379 Leave some space for labels allocated by find_and_verify_loops. */
380 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
382 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
383 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
384 sizeof (struct loop *));
386 /* Allocate storage for array of loops. */
387 loops->array = (struct loop *)
388 xcalloc (loops->num, sizeof (struct loop));
390 /* Find and process each loop.
391 First, find them, and record them in order of their beginnings. */
392 find_and_verify_loops (f, loops);
394 /* Allocate and initialize auxiliary loop information. */
395 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
396 for (i = 0; i < loops->num; i++)
397 loops->array[i].aux = loops_info + i;
399 /* Now find all register lifetimes. This must be done after
400 find_and_verify_loops, because it might reorder the insns in the
402 reg_scan (f, max_reg_before_loop, 1);
404 /* This must occur after reg_scan so that registers created by gcse
405 will have entries in the register tables.
407 We could have added a call to reg_scan after gcse_main in toplev.c,
408 but moving this call to init_alias_analysis is more efficient. */
409 init_alias_analysis ();
411 /* See if we went too far. Note that get_max_uid already returns
412 one more that the maximum uid of all insn. */
413 if (get_max_uid () > max_uid_for_loop)
415 /* Now reset it to the actual size we need. See above. */
416 max_uid_for_loop = get_max_uid ();
418 /* find_and_verify_loops has already called compute_luids, but it
419 might have rearranged code afterwards, so we need to recompute
421 max_luid = compute_luids (f, NULL_RTX, 0);
423 /* Don't leave gaps in uid_luid for insns that have been
424 deleted. It is possible that the first or last insn
425 using some register has been deleted by cross-jumping.
426 Make sure that uid_luid for that former insn's uid
427 points to the general area where that insn used to be. */
428 for (i = 0; i < max_uid_for_loop; i++)
430 uid_luid[0] = uid_luid[i];
431 if (uid_luid[0] != 0)
434 for (i = 0; i < max_uid_for_loop; i++)
435 if (uid_luid[i] == 0)
436 uid_luid[i] = uid_luid[i - 1];
438 /* Determine if the function has indirect jump. On some systems
439 this prevents low overhead loop instructions from being used. */
440 indirect_jump_in_function = indirect_jump_in_function_p (f);
442 /* Now scan the loops, last ones first, since this means inner ones are done
443 before outer ones. */
444 for (i = max_loop_num - 1; i >= 0; i--)
446 struct loop *loop = &loops->array[i];
447 struct loop_regs *regs = LOOP_REGS (loop);
449 regs->moved_once = moved_once;
451 if (! loop->invalid && loop->end)
452 scan_loop (loop, flags);
455 /* If there were lexical blocks inside the loop, they have been
456 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
457 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
458 the BLOCKs as well. */
459 if (write_symbols != NO_DEBUG)
462 end_alias_analysis ();
472 /* Returns the next insn, in execution order, after INSN. START and
473 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
474 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
475 insn-stream; it is used with loops that are entered near the
479 next_insn_in_loop (loop, insn)
480 const struct loop *loop;
483 insn = NEXT_INSN (insn);
485 if (insn == loop->end)
488 /* Go to the top of the loop, and continue there. */
495 if (insn == loop->scan_start)
502 /* Optimize one loop described by LOOP. */
504 /* ??? Could also move memory writes out of loops if the destination address
505 is invariant, the source is invariant, the memory write is not volatile,
506 and if we can prove that no read inside the loop can read this address
507 before the write occurs. If there is a read of this address after the
508 write, then we can also mark the memory read as invariant. */
511 scan_loop (loop, flags)
515 struct loop_info *loop_info = LOOP_INFO (loop);
516 struct loop_regs *regs = LOOP_REGS (loop);
518 rtx loop_start = loop->start;
519 rtx loop_end = loop->end;
521 /* 1 if we are scanning insns that could be executed zero times. */
523 /* 1 if we are scanning insns that might never be executed
524 due to a subroutine call which might exit before they are reached. */
526 /* Jump insn that enters the loop, or 0 if control drops in. */
527 rtx loop_entry_jump = 0;
528 /* Number of insns in the loop. */
531 rtx temp, update_start, update_end;
532 /* The SET from an insn, if it is the only SET in the insn. */
534 /* Chain describing insns movable in current loop. */
535 struct loop_movables *movables = LOOP_MOVABLES (loop);
536 /* Ratio of extra register life span we can justify
537 for saving an instruction. More if loop doesn't call subroutines
538 since in that case saving an insn makes more difference
539 and more registers are available. */
541 /* Nonzero if we are scanning instructions in a sub-loop. */
551 /* Determine whether this loop starts with a jump down to a test at
552 the end. This will occur for a small number of loops with a test
553 that is too complex to duplicate in front of the loop.
555 We search for the first insn or label in the loop, skipping NOTEs.
556 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
557 (because we might have a loop executed only once that contains a
558 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
559 (in case we have a degenerate loop).
561 Note that if we mistakenly think that a loop is entered at the top
562 when, in fact, it is entered at the exit test, the only effect will be
563 slightly poorer optimization. Making the opposite error can generate
564 incorrect code. Since very few loops now start with a jump to the
565 exit test, the code here to detect that case is very conservative. */
567 for (p = NEXT_INSN (loop_start);
569 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
570 && (GET_CODE (p) != NOTE
571 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
572 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
576 loop->scan_start = p;
578 /* Set up variables describing this loop. */
580 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
582 /* If loop has a jump before the first label,
583 the true entry is the target of that jump.
584 Start scan from there.
585 But record in LOOP->TOP the place where the end-test jumps
586 back to so we can scan that after the end of the loop. */
587 if (GET_CODE (p) == JUMP_INSN)
591 /* Loop entry must be unconditional jump (and not a RETURN) */
592 if (any_uncondjump_p (p)
593 && JUMP_LABEL (p) != 0
594 /* Check to see whether the jump actually
595 jumps out of the loop (meaning it's no loop).
596 This case can happen for things like
597 do {..} while (0). If this label was generated previously
598 by loop, we can't tell anything about it and have to reject
600 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
602 loop->top = next_label (loop->scan_start);
603 loop->scan_start = JUMP_LABEL (p);
607 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
608 as required by loop_reg_used_before_p. So skip such loops. (This
609 test may never be true, but it's best to play it safe.)
611 Also, skip loops where we do not start scanning at a label. This
612 test also rejects loops starting with a JUMP_INSN that failed the
615 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
616 || GET_CODE (loop->scan_start) != CODE_LABEL)
618 if (loop_dump_stream)
619 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
620 INSN_UID (loop_start), INSN_UID (loop_end));
624 /* Count number of times each reg is set during this loop. Set
625 VARRAY_CHAR (regs->may_not_optimize, I) if it is not safe to move
626 out the setting of register I. Set VARRAY_RTX
627 (regs->single_usage, I). */
629 /* Allocate extra space for REGS that might be created by
630 load_mems. We allocate a little extra slop as well, in the hopes
631 that even after the moving of movables creates some new registers
632 we won't have to reallocate these arrays. However, we do grow
633 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
634 nregs = max_reg_num () + loop_info->mems_idx + 16;
635 VARRAY_INT_INIT (regs->set_in_loop, nregs, "set_in_loop");
636 VARRAY_INT_INIT (regs->n_times_set, nregs, "n_times_set");
637 VARRAY_CHAR_INIT (regs->may_not_optimize, nregs, "may_not_optimize");
638 VARRAY_RTX_INIT (regs->single_usage, nregs, "single_usage");
642 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
645 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
647 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
648 VARRAY_INT (regs->set_in_loop, i) = 1;
651 #ifdef AVOID_CCMODE_COPIES
652 /* Don't try to move insns which set CC registers if we should not
653 create CCmode register copies. */
654 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
655 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
656 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
659 bcopy ((char *) ®s->set_in_loop->data,
660 (char *) ®s->n_times_set->data, nregs * sizeof (int));
662 if (loop_dump_stream)
664 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
665 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
667 fprintf (loop_dump_stream, "Continue at insn %d.\n",
668 INSN_UID (loop->cont));
671 /* Scan through the loop finding insns that are safe to move.
672 Set regs->set_in_loop negative for the reg being set, so that
673 this reg will be considered invariant for subsequent insns.
674 We consider whether subsequent insns use the reg
675 in deciding whether it is worth actually moving.
677 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
678 and therefore it is possible that the insns we are scanning
679 would never be executed. At such times, we must make sure
680 that it is safe to execute the insn once instead of zero times.
681 When MAYBE_NEVER is 0, all insns will be executed at least once
682 so that is not a problem. */
684 for (p = next_insn_in_loop (loop, loop->scan_start);
686 p = next_insn_in_loop (loop, p))
688 if (GET_CODE (p) == INSN
689 && (set = single_set (p))
690 && GET_CODE (SET_DEST (set)) == REG
691 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
696 rtx src = SET_SRC (set);
697 rtx dependencies = 0;
699 /* Figure out what to use as a source of this insn. If a REG_EQUIV
700 note is given or if a REG_EQUAL note with a constant operand is
701 specified, use it as the source and mark that we should move
702 this insn by calling emit_move_insn rather that duplicating the
705 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
707 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
709 src = XEXP (temp, 0), move_insn = 1;
712 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
713 if (temp && CONSTANT_P (XEXP (temp, 0)))
714 src = XEXP (temp, 0), move_insn = 1;
715 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
717 src = XEXP (temp, 0);
718 /* A libcall block can use regs that don't appear in
719 the equivalent expression. To move the libcall,
720 we must move those regs too. */
721 dependencies = libcall_other_reg (p, src);
725 /* Don't try to optimize a register that was made
726 by loop-optimization for an inner loop.
727 We don't know its life-span, so we can't compute the benefit. */
728 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
730 else if (/* The register is used in basic blocks other
731 than the one where it is set (meaning that
732 something after this point in the loop might
733 depend on its value before the set). */
734 ! reg_in_basic_block_p (p, SET_DEST (set))
735 /* And the set is not guaranteed to be executed one
736 the loop starts, or the value before the set is
737 needed before the set occurs...
739 ??? Note we have quadratic behaviour here, mitigated
740 by the fact that the previous test will often fail for
741 large loops. Rather than re-scanning the entire loop
742 each time for register usage, we should build tables
743 of the register usage and use them here instead. */
745 || loop_reg_used_before_p (loop, set, p)))
746 /* It is unsafe to move the set.
748 This code used to consider it OK to move a set of a variable
749 which was not created by the user and not used in an exit test.
750 That behavior is incorrect and was removed. */
752 else if ((tem = loop_invariant_p (loop, src))
753 && (dependencies == 0
754 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
755 && (VARRAY_INT (regs->set_in_loop,
756 REGNO (SET_DEST (set))) == 1
758 = consec_sets_invariant_p
759 (loop, SET_DEST (set),
760 VARRAY_INT (regs->set_in_loop,
761 REGNO (SET_DEST (set))),
763 /* If the insn can cause a trap (such as divide by zero),
764 can't move it unless it's guaranteed to be executed
765 once loop is entered. Even a function call might
766 prevent the trap insn from being reached
767 (since it might exit!) */
768 && ! ((maybe_never || call_passed)
769 && may_trap_p (src)))
771 register struct movable *m;
772 register int regno = REGNO (SET_DEST (set));
774 /* A potential lossage is where we have a case where two insns
775 can be combined as long as they are both in the loop, but
776 we move one of them outside the loop. For large loops,
777 this can lose. The most common case of this is the address
778 of a function being called.
780 Therefore, if this register is marked as being used exactly
781 once if we are in a loop with calls (a "large loop"), see if
782 we can replace the usage of this register with the source
783 of this SET. If we can, delete this insn.
785 Don't do this if P has a REG_RETVAL note or if we have
786 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
788 if (loop_info->has_call
789 && VARRAY_RTX (regs->single_usage, regno) != 0
790 && VARRAY_RTX (regs->single_usage, regno) != const0_rtx
791 && REGNO_FIRST_UID (regno) == INSN_UID (p)
792 && (REGNO_LAST_UID (regno)
793 == INSN_UID (VARRAY_RTX (regs->single_usage, regno)))
794 && VARRAY_INT (regs->set_in_loop, regno) == 1
795 && ! side_effects_p (SET_SRC (set))
796 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
797 && (! SMALL_REGISTER_CLASSES
798 || (! (GET_CODE (SET_SRC (set)) == REG
799 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
800 /* This test is not redundant; SET_SRC (set) might be
801 a call-clobbered register and the life of REGNO
802 might span a call. */
803 && ! modified_between_p (SET_SRC (set), p,
805 (regs->single_usage, regno))
806 && no_labels_between_p (p, VARRAY_RTX (regs->single_usage,
808 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
810 (regs->single_usage, regno)))
812 /* Replace any usage in a REG_EQUAL note. Must copy the
813 new source, so that we don't get rtx sharing between the
814 SET_SOURCE and REG_NOTES of insn p. */
815 REG_NOTES (VARRAY_RTX (regs->single_usage, regno))
816 = replace_rtx (REG_NOTES (VARRAY_RTX
817 (regs->single_usage, regno)),
818 SET_DEST (set), copy_rtx (SET_SRC (set)));
821 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
822 NOTE_SOURCE_FILE (p) = 0;
823 VARRAY_INT (regs->set_in_loop, regno) = 0;
827 m = (struct movable *) xmalloc (sizeof (struct movable));
831 m->dependencies = dependencies;
832 m->set_dest = SET_DEST (set);
834 m->consec = VARRAY_INT (regs->set_in_loop,
835 REGNO (SET_DEST (set))) - 1;
839 m->move_insn = move_insn;
840 m->move_insn_first = 0;
841 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
842 m->savemode = VOIDmode;
844 /* Set M->cond if either loop_invariant_p
845 or consec_sets_invariant_p returned 2
846 (only conditionally invariant). */
847 m->cond = ((tem | tem1 | tem2) > 1);
848 m->global = LOOP_REG_GLOBAL_P (loop, regno);
850 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
851 m->savings = VARRAY_INT (regs->n_times_set, regno);
852 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
853 m->savings += libcall_benefit (p);
854 VARRAY_INT (regs->set_in_loop, regno) = move_insn ? -2 : -1;
855 /* Add M to the end of the chain MOVABLES. */
856 loop_movables_add (movables, m);
860 /* It is possible for the first instruction to have a
861 REG_EQUAL note but a non-invariant SET_SRC, so we must
862 remember the status of the first instruction in case
863 the last instruction doesn't have a REG_EQUAL note. */
864 m->move_insn_first = m->move_insn;
866 /* Skip this insn, not checking REG_LIBCALL notes. */
867 p = next_nonnote_insn (p);
868 /* Skip the consecutive insns, if there are any. */
869 p = skip_consec_insns (p, m->consec);
870 /* Back up to the last insn of the consecutive group. */
871 p = prev_nonnote_insn (p);
873 /* We must now reset m->move_insn, m->is_equiv, and possibly
874 m->set_src to correspond to the effects of all the
876 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
878 m->set_src = XEXP (temp, 0), m->move_insn = 1;
881 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
882 if (temp && CONSTANT_P (XEXP (temp, 0)))
883 m->set_src = XEXP (temp, 0), m->move_insn = 1;
888 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
891 /* If this register is always set within a STRICT_LOW_PART
892 or set to zero, then its high bytes are constant.
893 So clear them outside the loop and within the loop
894 just load the low bytes.
895 We must check that the machine has an instruction to do so.
896 Also, if the value loaded into the register
897 depends on the same register, this cannot be done. */
898 else if (SET_SRC (set) == const0_rtx
899 && GET_CODE (NEXT_INSN (p)) == INSN
900 && (set1 = single_set (NEXT_INSN (p)))
901 && GET_CODE (set1) == SET
902 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
903 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
904 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
906 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
908 register int regno = REGNO (SET_DEST (set));
909 if (VARRAY_INT (regs->set_in_loop, regno) == 2)
911 register struct movable *m;
912 m = (struct movable *) alloca (sizeof (struct movable));
915 m->set_dest = SET_DEST (set);
922 m->move_insn_first = 0;
924 /* If the insn may not be executed on some cycles,
925 we can't clear the whole reg; clear just high part.
926 Not even if the reg is used only within this loop.
933 Clearing x before the inner loop could clobber a value
934 being saved from the last time around the outer loop.
935 However, if the reg is not used outside this loop
936 and all uses of the register are in the same
937 basic block as the store, there is no problem.
939 If this insn was made by loop, we don't know its
940 INSN_LUID and hence must make a conservative
942 m->global = (INSN_UID (p) >= max_uid_for_loop
943 || LOOP_REG_GLOBAL_P (loop, regno)
944 || (labels_in_range_p
945 (p, REGNO_FIRST_LUID (regno))));
946 if (maybe_never && m->global)
947 m->savemode = GET_MODE (SET_SRC (set1));
949 m->savemode = VOIDmode;
953 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
955 VARRAY_INT (regs->set_in_loop, regno) = -1;
956 /* Add M to the end of the chain MOVABLES. */
957 loop_movables_add (movables, m);
961 /* Past a call insn, we get to insns which might not be executed
962 because the call might exit. This matters for insns that trap.
963 Constant and pure call insns always return, so they don't count. */
964 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
966 /* Past a label or a jump, we get to insns for which we
967 can't count on whether or how many times they will be
968 executed during each iteration. Therefore, we can
969 only move out sets of trivial variables
970 (those not used after the loop). */
971 /* Similar code appears twice in strength_reduce. */
972 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
973 /* If we enter the loop in the middle, and scan around to the
974 beginning, don't set maybe_never for that. This must be an
975 unconditional jump, otherwise the code at the top of the
976 loop might never be executed. Unconditional jumps are
977 followed a by barrier then loop end. */
978 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
979 && NEXT_INSN (NEXT_INSN (p)) == loop_end
980 && any_uncondjump_p (p)))
982 else if (GET_CODE (p) == NOTE)
984 /* At the virtual top of a converted loop, insns are again known to
985 be executed: logically, the loop begins here even though the exit
986 code has been duplicated. */
987 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
988 maybe_never = call_passed = 0;
989 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
991 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
996 /* If one movable subsumes another, ignore that other. */
998 ignore_some_movables (movables);
1000 /* For each movable insn, see if the reg that it loads
1001 leads when it dies right into another conditionally movable insn.
1002 If so, record that the second insn "forces" the first one,
1003 since the second can be moved only if the first is. */
1005 force_movables (movables);
1007 /* See if there are multiple movable insns that load the same value.
1008 If there are, make all but the first point at the first one
1009 through the `match' field, and add the priorities of them
1010 all together as the priority of the first. */
1012 combine_movables (movables, regs);
1014 /* Now consider each movable insn to decide whether it is worth moving.
1015 Store 0 in regs->set_in_loop for each reg that is moved.
1017 Generally this increases code size, so do not move moveables when
1018 optimizing for code size. */
1020 if (! optimize_size)
1021 move_movables (loop, movables, threshold, insn_count);
1023 /* Now candidates that still are negative are those not moved.
1024 Change regs->set_in_loop to indicate that those are not actually
1026 for (i = 0; i < nregs; i++)
1027 if (VARRAY_INT (regs->set_in_loop, i) < 0)
1028 VARRAY_INT (regs->set_in_loop, i) = VARRAY_INT (regs->n_times_set, i);
1030 /* Now that we've moved some things out of the loop, we might be able to
1031 hoist even more memory references. */
1032 load_mems_and_recount_loop_regs_set (loop, &insn_count);
1034 for (update_start = loop_start;
1035 PREV_INSN (update_start)
1036 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
1037 update_start = PREV_INSN (update_start))
1039 update_end = NEXT_INSN (loop_end);
1041 reg_scan_update (update_start, update_end, loop_max_reg);
1042 loop_max_reg = max_reg_num ();
1044 if (flag_strength_reduce)
1046 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1047 /* Ensure our label doesn't go away. */
1048 LABEL_NUSES (update_end)++;
1050 strength_reduce (loop, insn_count, flags);
1052 reg_scan_update (update_start, update_end, loop_max_reg);
1053 loop_max_reg = max_reg_num ();
1055 if (update_end && GET_CODE (update_end) == CODE_LABEL
1056 && --LABEL_NUSES (update_end) == 0)
1057 delete_insn (update_end);
1061 /* The movable information is required for strength reduction. */
1062 loop_movables_free (movables);
1064 VARRAY_FREE (regs->single_usage);
1065 VARRAY_FREE (regs->set_in_loop);
1066 VARRAY_FREE (regs->n_times_set);
1067 VARRAY_FREE (regs->may_not_optimize);
1070 /* Add elements to *OUTPUT to record all the pseudo-regs
1071 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1074 record_excess_regs (in_this, not_in_this, output)
1075 rtx in_this, not_in_this;
1082 code = GET_CODE (in_this);
1096 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1097 && ! reg_mentioned_p (in_this, not_in_this))
1098 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1105 fmt = GET_RTX_FORMAT (code);
1106 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1113 for (j = 0; j < XVECLEN (in_this, i); j++)
1114 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1118 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1124 /* Check what regs are referred to in the libcall block ending with INSN,
1125 aside from those mentioned in the equivalent value.
1126 If there are none, return 0.
1127 If there are one or more, return an EXPR_LIST containing all of them. */
1130 libcall_other_reg (insn, equiv)
1133 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1134 rtx p = XEXP (note, 0);
1137 /* First, find all the regs used in the libcall block
1138 that are not mentioned as inputs to the result. */
1142 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1143 || GET_CODE (p) == CALL_INSN)
1144 record_excess_regs (PATTERN (p), equiv, &output);
1151 /* Return 1 if all uses of REG
1152 are between INSN and the end of the basic block. */
1155 reg_in_basic_block_p (insn, reg)
1158 int regno = REGNO (reg);
1161 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1164 /* Search this basic block for the already recorded last use of the reg. */
1165 for (p = insn; p; p = NEXT_INSN (p))
1167 switch (GET_CODE (p))
1174 /* Ordinary insn: if this is the last use, we win. */
1175 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1180 /* Jump insn: if this is the last use, we win. */
1181 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1183 /* Otherwise, it's the end of the basic block, so we lose. */
1188 /* It's the end of the basic block, so we lose. */
1196 /* The "last use" that was recorded can't be found after the first
1197 use. This can happen when the last use was deleted while
1198 processing an inner loop, this inner loop was then completely
1199 unrolled, and the outer loop is always exited after the inner loop,
1200 so that everything after the first use becomes a single basic block. */
1204 /* Compute the benefit of eliminating the insns in the block whose
1205 last insn is LAST. This may be a group of insns used to compute a
1206 value directly or can contain a library call. */
1209 libcall_benefit (last)
1215 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1216 insn != last; insn = NEXT_INSN (insn))
1218 if (GET_CODE (insn) == CALL_INSN)
1219 benefit += 10; /* Assume at least this many insns in a library
1221 else if (GET_CODE (insn) == INSN
1222 && GET_CODE (PATTERN (insn)) != USE
1223 && GET_CODE (PATTERN (insn)) != CLOBBER)
1230 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1233 skip_consec_insns (insn, count)
1237 for (; count > 0; count--)
1241 /* If first insn of libcall sequence, skip to end. */
1242 /* Do this at start of loop, since INSN is guaranteed to
1244 if (GET_CODE (insn) != NOTE
1245 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1246 insn = XEXP (temp, 0);
1249 insn = NEXT_INSN (insn);
1250 while (GET_CODE (insn) == NOTE);
1256 /* Ignore any movable whose insn falls within a libcall
1257 which is part of another movable.
1258 We make use of the fact that the movable for the libcall value
1259 was made later and so appears later on the chain. */
1262 ignore_some_movables (movables)
1263 struct loop_movables *movables;
1265 register struct movable *m, *m1;
1267 for (m = movables->head; m; m = m->next)
1269 /* Is this a movable for the value of a libcall? */
1270 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1274 /* Check for earlier movables inside that range,
1275 and mark them invalid. We cannot use LUIDs here because
1276 insns created by loop.c for prior loops don't have LUIDs.
1277 Rather than reject all such insns from movables, we just
1278 explicitly check each insn in the libcall (since invariant
1279 libcalls aren't that common). */
1280 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1281 for (m1 = movables->head; m1 != m; m1 = m1->next)
1282 if (m1->insn == insn)
1288 /* For each movable insn, see if the reg that it loads
1289 leads when it dies right into another conditionally movable insn.
1290 If so, record that the second insn "forces" the first one,
1291 since the second can be moved only if the first is. */
1294 force_movables (movables)
1295 struct loop_movables *movables;
1297 register struct movable *m, *m1;
1298 for (m1 = movables->head; m1; m1 = m1->next)
1299 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1300 if (!m1->partial && !m1->done)
1302 int regno = m1->regno;
1303 for (m = m1->next; m; m = m->next)
1304 /* ??? Could this be a bug? What if CSE caused the
1305 register of M1 to be used after this insn?
1306 Since CSE does not update regno_last_uid,
1307 this insn M->insn might not be where it dies.
1308 But very likely this doesn't matter; what matters is
1309 that M's reg is computed from M1's reg. */
1310 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1313 if (m != 0 && m->set_src == m1->set_dest
1314 /* If m->consec, m->set_src isn't valid. */
1318 /* Increase the priority of the moving the first insn
1319 since it permits the second to be moved as well. */
1323 m1->lifetime += m->lifetime;
1324 m1->savings += m->savings;
1329 /* Find invariant expressions that are equal and can be combined into
1333 combine_movables (movables, regs)
1334 struct loop_movables *movables;
1335 struct loop_regs *regs;
1337 register struct movable *m;
1338 char *matched_regs = (char *) xmalloc (regs->num);
1339 enum machine_mode mode;
1341 /* Regs that are set more than once are not allowed to match
1342 or be matched. I'm no longer sure why not. */
1343 /* Perhaps testing m->consec_sets would be more appropriate here? */
1345 for (m = movables->head; m; m = m->next)
1346 if (m->match == 0 && VARRAY_INT (regs->n_times_set, m->regno) == 1
1349 register struct movable *m1;
1350 int regno = m->regno;
1352 memset (matched_regs, 0, regs->num);
1353 matched_regs[regno] = 1;
1355 /* We want later insns to match the first one. Don't make the first
1356 one match any later ones. So start this loop at m->next. */
1357 for (m1 = m->next; m1; m1 = m1->next)
1358 if (m != m1 && m1->match == 0 && VARRAY_INT (regs->n_times_set,
1360 /* A reg used outside the loop mustn't be eliminated. */
1362 /* A reg used for zero-extending mustn't be eliminated. */
1364 && (matched_regs[m1->regno]
1367 /* Can combine regs with different modes loaded from the
1368 same constant only if the modes are the same or
1369 if both are integer modes with M wider or the same
1370 width as M1. The check for integer is redundant, but
1371 safe, since the only case of differing destination
1372 modes with equal sources is when both sources are
1373 VOIDmode, i.e., CONST_INT. */
1374 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1375 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1376 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1377 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1378 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1379 /* See if the source of M1 says it matches M. */
1380 && ((GET_CODE (m1->set_src) == REG
1381 && matched_regs[REGNO (m1->set_src)])
1382 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1384 && ((m->dependencies == m1->dependencies)
1385 || rtx_equal_p (m->dependencies, m1->dependencies)))
1387 m->lifetime += m1->lifetime;
1388 m->savings += m1->savings;
1391 matched_regs[m1->regno] = 1;
1395 /* Now combine the regs used for zero-extension.
1396 This can be done for those not marked `global'
1397 provided their lives don't overlap. */
1399 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1400 mode = GET_MODE_WIDER_MODE (mode))
1402 register struct movable *m0 = 0;
1404 /* Combine all the registers for extension from mode MODE.
1405 Don't combine any that are used outside this loop. */
1406 for (m = movables->head; m; m = m->next)
1407 if (m->partial && ! m->global
1408 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1410 register struct movable *m1;
1411 int first = REGNO_FIRST_LUID (m->regno);
1412 int last = REGNO_LAST_LUID (m->regno);
1416 /* First one: don't check for overlap, just record it. */
1421 /* Make sure they extend to the same mode.
1422 (Almost always true.) */
1423 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1426 /* We already have one: check for overlap with those
1427 already combined together. */
1428 for (m1 = movables->head; m1 != m; m1 = m1->next)
1429 if (m1 == m0 || (m1->partial && m1->match == m0))
1430 if (! (REGNO_FIRST_LUID (m1->regno) > last
1431 || REGNO_LAST_LUID (m1->regno) < first))
1434 /* No overlap: we can combine this with the others. */
1435 m0->lifetime += m->lifetime;
1436 m0->savings += m->savings;
1446 free (matched_regs);
1449 /* Return 1 if regs X and Y will become the same if moved. */
1452 regs_match_p (x, y, movables)
1454 struct loop_movables *movables;
1456 unsigned int xn = REGNO (x);
1457 unsigned int yn = REGNO (y);
1458 struct movable *mx, *my;
1460 for (mx = movables->head; mx; mx = mx->next)
1461 if (mx->regno == xn)
1464 for (my = movables->head; my; my = my->next)
1465 if (my->regno == yn)
1469 && ((mx->match == my->match && mx->match != 0)
1471 || mx == my->match));
1474 /* Return 1 if X and Y are identical-looking rtx's.
1475 This is the Lisp function EQUAL for rtx arguments.
1477 If two registers are matching movables or a movable register and an
1478 equivalent constant, consider them equal. */
1481 rtx_equal_for_loop_p (x, y, movables, regs)
1483 struct loop_movables *movables;
1484 struct loop_regs *regs;
1488 register struct movable *m;
1489 register enum rtx_code code;
1490 register const char *fmt;
1494 if (x == 0 || y == 0)
1497 code = GET_CODE (x);
1499 /* If we have a register and a constant, they may sometimes be
1501 if (GET_CODE (x) == REG && VARRAY_INT (regs->set_in_loop, REGNO (x)) == -2
1504 for (m = movables->head; m; m = m->next)
1505 if (m->move_insn && m->regno == REGNO (x)
1506 && rtx_equal_p (m->set_src, y))
1509 else if (GET_CODE (y) == REG && VARRAY_INT (regs->set_in_loop,
1513 for (m = movables->head; m; m = m->next)
1514 if (m->move_insn && m->regno == REGNO (y)
1515 && rtx_equal_p (m->set_src, x))
1519 /* Otherwise, rtx's of different codes cannot be equal. */
1520 if (code != GET_CODE (y))
1523 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1524 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1526 if (GET_MODE (x) != GET_MODE (y))
1529 /* These three types of rtx's can be compared nonrecursively. */
1531 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1533 if (code == LABEL_REF)
1534 return XEXP (x, 0) == XEXP (y, 0);
1535 if (code == SYMBOL_REF)
1536 return XSTR (x, 0) == XSTR (y, 0);
1538 /* Compare the elements. If any pair of corresponding elements
1539 fail to match, return 0 for the whole things. */
1541 fmt = GET_RTX_FORMAT (code);
1542 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1547 if (XWINT (x, i) != XWINT (y, i))
1552 if (XINT (x, i) != XINT (y, i))
1557 /* Two vectors must have the same length. */
1558 if (XVECLEN (x, i) != XVECLEN (y, i))
1561 /* And the corresponding elements must match. */
1562 for (j = 0; j < XVECLEN (x, i); j++)
1563 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1564 movables, regs) == 0)
1569 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1575 if (strcmp (XSTR (x, i), XSTR (y, i)))
1580 /* These are just backpointers, so they don't matter. */
1586 /* It is believed that rtx's at this level will never
1587 contain anything but integers and other rtx's,
1588 except for within LABEL_REFs and SYMBOL_REFs. */
1596 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1597 insns in INSNS which use the reference. */
1600 add_label_notes (x, insns)
1604 enum rtx_code code = GET_CODE (x);
1609 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1611 /* This code used to ignore labels that referred to dispatch tables to
1612 avoid flow generating (slighly) worse code.
1614 We no longer ignore such label references (see LABEL_REF handling in
1615 mark_jump_label for additional information). */
1616 for (insn = insns; insn; insn = NEXT_INSN (insn))
1617 if (reg_mentioned_p (XEXP (x, 0), insn))
1618 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1622 fmt = GET_RTX_FORMAT (code);
1623 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1626 add_label_notes (XEXP (x, i), insns);
1627 else if (fmt[i] == 'E')
1628 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1629 add_label_notes (XVECEXP (x, i, j), insns);
1633 /* Scan MOVABLES, and move the insns that deserve to be moved.
1634 If two matching movables are combined, replace one reg with the
1635 other throughout. */
1638 move_movables (loop, movables, threshold, insn_count)
1640 struct loop_movables *movables;
1644 struct loop_regs *regs = LOOP_REGS (loop);
1645 int nregs = regs->num;
1647 register struct movable *m;
1649 rtx loop_start = loop->start;
1650 rtx loop_end = loop->end;
1651 /* Map of pseudo-register replacements to handle combining
1652 when we move several insns that load the same value
1653 into different pseudo-registers. */
1654 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1655 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1659 for (m = movables->head; m; m = m->next)
1661 /* Describe this movable insn. */
1663 if (loop_dump_stream)
1665 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1666 INSN_UID (m->insn), m->regno, m->lifetime);
1668 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1670 fprintf (loop_dump_stream, "cond ");
1672 fprintf (loop_dump_stream, "force ");
1674 fprintf (loop_dump_stream, "global ");
1676 fprintf (loop_dump_stream, "done ");
1678 fprintf (loop_dump_stream, "move-insn ");
1680 fprintf (loop_dump_stream, "matches %d ",
1681 INSN_UID (m->match->insn));
1683 fprintf (loop_dump_stream, "forces %d ",
1684 INSN_UID (m->forces->insn));
1687 /* Count movables. Value used in heuristics in strength_reduce. */
1690 /* Ignore the insn if it's already done (it matched something else).
1691 Otherwise, see if it is now safe to move. */
1695 || (1 == loop_invariant_p (loop, m->set_src)
1696 && (m->dependencies == 0
1697 || 1 == loop_invariant_p (loop, m->dependencies))
1699 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1702 && (! m->forces || m->forces->done))
1706 int savings = m->savings;
1708 /* We have an insn that is safe to move.
1709 Compute its desirability. */
1714 if (loop_dump_stream)
1715 fprintf (loop_dump_stream, "savings %d ", savings);
1717 if (regs->moved_once[regno] && loop_dump_stream)
1718 fprintf (loop_dump_stream, "halved since already moved ");
1720 /* An insn MUST be moved if we already moved something else
1721 which is safe only if this one is moved too: that is,
1722 if already_moved[REGNO] is nonzero. */
1724 /* An insn is desirable to move if the new lifetime of the
1725 register is no more than THRESHOLD times the old lifetime.
1726 If it's not desirable, it means the loop is so big
1727 that moving won't speed things up much,
1728 and it is liable to make register usage worse. */
1730 /* It is also desirable to move if it can be moved at no
1731 extra cost because something else was already moved. */
1733 if (already_moved[regno]
1734 || flag_move_all_movables
1735 || (threshold * savings * m->lifetime) >=
1736 (regs->moved_once[regno] ? insn_count * 2 : insn_count)
1737 || (m->forces && m->forces->done
1738 && VARRAY_INT (regs->n_times_set, m->forces->regno) == 1))
1741 register struct movable *m1;
1742 rtx first = NULL_RTX;
1744 /* Now move the insns that set the reg. */
1746 if (m->partial && m->match)
1750 /* Find the end of this chain of matching regs.
1751 Thus, we load each reg in the chain from that one reg.
1752 And that reg is loaded with 0 directly,
1753 since it has ->match == 0. */
1754 for (m1 = m; m1->match; m1 = m1->match);
1755 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1756 SET_DEST (PATTERN (m1->insn)));
1757 i1 = emit_insn_before (newpat, loop_start);
1759 /* Mark the moved, invariant reg as being allowed to
1760 share a hard reg with the other matching invariant. */
1761 REG_NOTES (i1) = REG_NOTES (m->insn);
1762 r1 = SET_DEST (PATTERN (m->insn));
1763 r2 = SET_DEST (PATTERN (m1->insn));
1765 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1766 gen_rtx_EXPR_LIST (VOIDmode, r2,
1768 delete_insn (m->insn);
1773 if (loop_dump_stream)
1774 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1776 /* If we are to re-generate the item being moved with a
1777 new move insn, first delete what we have and then emit
1778 the move insn before the loop. */
1779 else if (m->move_insn)
1783 for (count = m->consec; count >= 0; count--)
1785 /* If this is the first insn of a library call sequence,
1787 if (GET_CODE (p) != NOTE
1788 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1791 /* If this is the last insn of a libcall sequence, then
1792 delete every insn in the sequence except the last.
1793 The last insn is handled in the normal manner. */
1794 if (GET_CODE (p) != NOTE
1795 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1797 temp = XEXP (temp, 0);
1799 temp = delete_insn (temp);
1803 p = delete_insn (p);
1805 /* simplify_giv_expr expects that it can walk the insns
1806 at m->insn forwards and see this old sequence we are
1807 tossing here. delete_insn does preserve the next
1808 pointers, but when we skip over a NOTE we must fix
1809 it up. Otherwise that code walks into the non-deleted
1811 while (p && GET_CODE (p) == NOTE)
1812 p = NEXT_INSN (temp) = NEXT_INSN (p);
1816 emit_move_insn (m->set_dest, m->set_src);
1817 temp = get_insns ();
1820 add_label_notes (m->set_src, temp);
1822 i1 = emit_insns_before (temp, loop_start);
1823 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1825 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1826 m->set_src, REG_NOTES (i1));
1828 if (loop_dump_stream)
1829 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1831 /* The more regs we move, the less we like moving them. */
1836 for (count = m->consec; count >= 0; count--)
1840 /* If first insn of libcall sequence, skip to end. */
1841 /* Do this at start of loop, since p is guaranteed to
1843 if (GET_CODE (p) != NOTE
1844 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1847 /* If last insn of libcall sequence, move all
1848 insns except the last before the loop. The last
1849 insn is handled in the normal manner. */
1850 if (GET_CODE (p) != NOTE
1851 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1855 rtx fn_address_insn = 0;
1858 for (temp = XEXP (temp, 0); temp != p;
1859 temp = NEXT_INSN (temp))
1865 if (GET_CODE (temp) == NOTE)
1868 body = PATTERN (temp);
1870 /* Find the next insn after TEMP,
1871 not counting USE or NOTE insns. */
1872 for (next = NEXT_INSN (temp); next != p;
1873 next = NEXT_INSN (next))
1874 if (! (GET_CODE (next) == INSN
1875 && GET_CODE (PATTERN (next)) == USE)
1876 && GET_CODE (next) != NOTE)
1879 /* If that is the call, this may be the insn
1880 that loads the function address.
1882 Extract the function address from the insn
1883 that loads it into a register.
1884 If this insn was cse'd, we get incorrect code.
1886 So emit a new move insn that copies the
1887 function address into the register that the
1888 call insn will use. flow.c will delete any
1889 redundant stores that we have created. */
1890 if (GET_CODE (next) == CALL_INSN
1891 && GET_CODE (body) == SET
1892 && GET_CODE (SET_DEST (body)) == REG
1893 && (n = find_reg_note (temp, REG_EQUAL,
1896 fn_reg = SET_SRC (body);
1897 if (GET_CODE (fn_reg) != REG)
1898 fn_reg = SET_DEST (body);
1899 fn_address = XEXP (n, 0);
1900 fn_address_insn = temp;
1902 /* We have the call insn.
1903 If it uses the register we suspect it might,
1904 load it with the correct address directly. */
1905 if (GET_CODE (temp) == CALL_INSN
1907 && reg_referenced_p (fn_reg, body))
1908 emit_insn_after (gen_move_insn (fn_reg,
1912 if (GET_CODE (temp) == CALL_INSN)
1914 i1 = emit_call_insn_before (body, loop_start);
1915 /* Because the USAGE information potentially
1916 contains objects other than hard registers
1917 we need to copy it. */
1918 if (CALL_INSN_FUNCTION_USAGE (temp))
1919 CALL_INSN_FUNCTION_USAGE (i1)
1920 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1923 i1 = emit_insn_before (body, loop_start);
1926 if (temp == fn_address_insn)
1927 fn_address_insn = i1;
1928 REG_NOTES (i1) = REG_NOTES (temp);
1934 if (m->savemode != VOIDmode)
1936 /* P sets REG to zero; but we should clear only
1937 the bits that are not covered by the mode
1939 rtx reg = m->set_dest;
1945 (GET_MODE (reg), and_optab, reg,
1946 GEN_INT ((((HOST_WIDE_INT) 1
1947 << GET_MODE_BITSIZE (m->savemode)))
1949 reg, 1, OPTAB_LIB_WIDEN);
1953 emit_move_insn (reg, tem);
1954 sequence = gen_sequence ();
1956 i1 = emit_insn_before (sequence, loop_start);
1958 else if (GET_CODE (p) == CALL_INSN)
1960 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1961 /* Because the USAGE information potentially
1962 contains objects other than hard registers
1963 we need to copy it. */
1964 if (CALL_INSN_FUNCTION_USAGE (p))
1965 CALL_INSN_FUNCTION_USAGE (i1)
1966 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1968 else if (count == m->consec && m->move_insn_first)
1970 /* The SET_SRC might not be invariant, so we must
1971 use the REG_EQUAL note. */
1973 emit_move_insn (m->set_dest, m->set_src);
1974 temp = get_insns ();
1977 add_label_notes (m->set_src, temp);
1979 i1 = emit_insns_before (temp, loop_start);
1980 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1982 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1984 m->set_src, REG_NOTES (i1));
1987 i1 = emit_insn_before (PATTERN (p), loop_start);
1989 if (REG_NOTES (i1) == 0)
1991 REG_NOTES (i1) = REG_NOTES (p);
1993 /* If there is a REG_EQUAL note present whose value
1994 is not loop invariant, then delete it, since it
1995 may cause problems with later optimization passes.
1996 It is possible for cse to create such notes
1997 like this as a result of record_jump_cond. */
1999 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
2000 && ! loop_invariant_p (loop, XEXP (temp, 0)))
2001 remove_note (i1, temp);
2007 if (loop_dump_stream)
2008 fprintf (loop_dump_stream, " moved to %d",
2011 /* If library call, now fix the REG_NOTES that contain
2012 insn pointers, namely REG_LIBCALL on FIRST
2013 and REG_RETVAL on I1. */
2014 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2016 XEXP (temp, 0) = first;
2017 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2018 XEXP (temp, 0) = i1;
2025 /* simplify_giv_expr expects that it can walk the insns
2026 at m->insn forwards and see this old sequence we are
2027 tossing here. delete_insn does preserve the next
2028 pointers, but when we skip over a NOTE we must fix
2029 it up. Otherwise that code walks into the non-deleted
2031 while (p && GET_CODE (p) == NOTE)
2032 p = NEXT_INSN (temp) = NEXT_INSN (p);
2035 /* The more regs we move, the less we like moving them. */
2039 /* Any other movable that loads the same register
2041 already_moved[regno] = 1;
2043 /* This reg has been moved out of one loop. */
2044 regs->moved_once[regno] = 1;
2046 /* The reg set here is now invariant. */
2048 VARRAY_INT (regs->set_in_loop, regno) = 0;
2052 /* Change the length-of-life info for the register
2053 to say it lives at least the full length of this loop.
2054 This will help guide optimizations in outer loops. */
2056 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2057 /* This is the old insn before all the moved insns.
2058 We can't use the moved insn because it is out of range
2059 in uid_luid. Only the old insns have luids. */
2060 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2061 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2062 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2064 /* Combine with this moved insn any other matching movables. */
2067 for (m1 = movables->head; m1; m1 = m1->next)
2072 /* Schedule the reg loaded by M1
2073 for replacement so that shares the reg of M.
2074 If the modes differ (only possible in restricted
2075 circumstances, make a SUBREG.
2077 Note this assumes that the target dependent files
2078 treat REG and SUBREG equally, including within
2079 GO_IF_LEGITIMATE_ADDRESS and in all the
2080 predicates since we never verify that replacing the
2081 original register with a SUBREG results in a
2082 recognizable insn. */
2083 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2084 reg_map[m1->regno] = m->set_dest;
2087 = gen_lowpart_common (GET_MODE (m1->set_dest),
2090 /* Get rid of the matching insn
2091 and prevent further processing of it. */
2094 /* if library call, delete all insn except last, which
2096 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2099 for (temp = XEXP (temp, 0); temp != m1->insn;
2100 temp = NEXT_INSN (temp))
2103 delete_insn (m1->insn);
2105 /* Any other movable that loads the same register
2107 already_moved[m1->regno] = 1;
2109 /* The reg merged here is now invariant,
2110 if the reg it matches is invariant. */
2112 VARRAY_INT (regs->set_in_loop, m1->regno) = 0;
2115 else if (loop_dump_stream)
2116 fprintf (loop_dump_stream, "not desirable");
2118 else if (loop_dump_stream && !m->match)
2119 fprintf (loop_dump_stream, "not safe");
2121 if (loop_dump_stream)
2122 fprintf (loop_dump_stream, "\n");
2126 new_start = loop_start;
2128 /* Go through all the instructions in the loop, making
2129 all the register substitutions scheduled in REG_MAP. */
2130 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2131 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2132 || GET_CODE (p) == CALL_INSN)
2134 replace_regs (PATTERN (p), reg_map, nregs, 0);
2135 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2141 free (already_moved);
2146 loop_movables_add (movables, m)
2147 struct loop_movables *movables;
2150 if (movables->head == 0)
2153 movables->last->next = m;
2159 loop_movables_free (movables)
2160 struct loop_movables *movables;
2163 struct movable *m_next;
2165 for (m = movables->head; m; m = m_next)
2173 /* Scan X and replace the address of any MEM in it with ADDR.
2174 REG is the address that MEM should have before the replacement. */
2177 replace_call_address (x, reg, addr)
2180 register enum rtx_code code;
2182 register const char *fmt;
2186 code = GET_CODE (x);
2200 /* Short cut for very common case. */
2201 replace_call_address (XEXP (x, 1), reg, addr);
2205 /* Short cut for very common case. */
2206 replace_call_address (XEXP (x, 0), reg, addr);
2210 /* If this MEM uses a reg other than the one we expected,
2211 something is wrong. */
2212 if (XEXP (x, 0) != reg)
2221 fmt = GET_RTX_FORMAT (code);
2222 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2225 replace_call_address (XEXP (x, i), reg, addr);
2226 else if (fmt[i] == 'E')
2229 for (j = 0; j < XVECLEN (x, i); j++)
2230 replace_call_address (XVECEXP (x, i, j), reg, addr);
2236 /* Return the number of memory refs to addresses that vary
2240 count_nonfixed_reads (loop, x)
2241 const struct loop *loop;
2244 register enum rtx_code code;
2246 register const char *fmt;
2252 code = GET_CODE (x);
2266 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2267 + count_nonfixed_reads (loop, XEXP (x, 0)));
2274 fmt = GET_RTX_FORMAT (code);
2275 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2278 value += count_nonfixed_reads (loop, XEXP (x, i));
2282 for (j = 0; j < XVECLEN (x, i); j++)
2283 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2289 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2290 `has_call', `has_volatile', `has_tablejump',
2291 `unknown_address_altered', `unknown_constant_address_altered', and
2292 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2293 list `store_mems' in LOOP. */
2299 register int level = 1;
2301 struct loop_info *loop_info = LOOP_INFO (loop);
2302 rtx start = loop->start;
2303 rtx end = loop->end;
2304 /* The label after END. Jumping here is just like falling off the
2305 end of the loop. We use next_nonnote_insn instead of next_label
2306 as a hedge against the (pathological) case where some actual insn
2307 might end up between the two. */
2308 rtx exit_target = next_nonnote_insn (end);
2310 loop_info->has_indirect_jump = indirect_jump_in_function;
2311 loop_info->pre_header_has_call = 0;
2312 loop_info->has_call = 0;
2313 loop_info->has_volatile = 0;
2314 loop_info->has_tablejump = 0;
2315 loop_info->has_multiple_exit_targets = 0;
2318 loop_info->unknown_address_altered = 0;
2319 loop_info->unknown_constant_address_altered = 0;
2320 loop_info->store_mems = NULL_RTX;
2321 loop_info->first_loop_store_insn = NULL_RTX;
2322 loop_info->mems_idx = 0;
2323 loop_info->num_mem_sets = 0;
2326 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
2327 insn = PREV_INSN (insn))
2329 if (GET_CODE (insn) == CALL_INSN)
2331 loop_info->pre_header_has_call = 1;
2336 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2337 insn = NEXT_INSN (insn))
2339 if (GET_CODE (insn) == NOTE)
2341 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2344 /* Count number of loops contained in this one. */
2347 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2352 else if (GET_CODE (insn) == CALL_INSN)
2354 if (! CONST_CALL_P (insn))
2355 loop_info->unknown_address_altered = 1;
2356 loop_info->has_call = 1;
2358 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2360 rtx label1 = NULL_RTX;
2361 rtx label2 = NULL_RTX;
2363 if (volatile_refs_p (PATTERN (insn)))
2364 loop_info->has_volatile = 1;
2366 if (GET_CODE (insn) == JUMP_INSN
2367 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2368 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2369 loop_info->has_tablejump = 1;
2371 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2372 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2373 loop_info->first_loop_store_insn = insn;
2375 if (! loop_info->has_multiple_exit_targets
2376 && GET_CODE (insn) == JUMP_INSN
2377 && GET_CODE (PATTERN (insn)) == SET
2378 && SET_DEST (PATTERN (insn)) == pc_rtx)
2380 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2382 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2383 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2387 label1 = SET_SRC (PATTERN (insn));
2392 if (label1 && label1 != pc_rtx)
2394 if (GET_CODE (label1) != LABEL_REF)
2396 /* Something tricky. */
2397 loop_info->has_multiple_exit_targets = 1;
2400 else if (XEXP (label1, 0) != exit_target
2401 && LABEL_OUTSIDE_LOOP_P (label1))
2403 /* A jump outside the current loop. */
2404 loop_info->has_multiple_exit_targets = 1;
2415 else if (GET_CODE (insn) == RETURN)
2416 loop_info->has_multiple_exit_targets = 1;
2419 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2420 if (/* An exception thrown by a called function might land us
2422 ! loop_info->has_call
2423 /* We don't want loads for MEMs moved to a location before the
2424 one at which their stack memory becomes allocated. (Note
2425 that this is not a problem for malloc, etc., since those
2426 require actual function calls. */
2427 && ! current_function_calls_alloca
2428 /* There are ways to leave the loop other than falling off the
2430 && ! loop_info->has_multiple_exit_targets)
2431 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2432 insn = NEXT_INSN (insn))
2433 for_each_rtx (&insn, insert_loop_mem, loop_info);
2435 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2436 that loop_invariant_p and load_mems can use true_dependence
2437 to determine what is really clobbered. */
2438 if (loop_info->unknown_address_altered)
2440 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2442 loop_info->store_mems
2443 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2445 if (loop_info->unknown_constant_address_altered)
2447 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2449 RTX_UNCHANGING_P (mem) = 1;
2450 loop_info->store_mems
2451 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2455 /* Scan the function looking for loops. Record the start and end of each loop.
2456 Also mark as invalid loops any loops that contain a setjmp or are branched
2457 to from outside the loop. */
2460 find_and_verify_loops (f, loops)
2462 struct loops *loops;
2467 struct loop *current_loop;
2468 struct loop *next_loop;
2471 num_loops = loops->num;
2473 compute_luids (f, NULL_RTX, 0);
2475 /* If there are jumps to undefined labels,
2476 treat them as jumps out of any/all loops.
2477 This also avoids writing past end of tables when there are no loops. */
2480 /* Find boundaries of loops, mark which loops are contained within
2481 loops, and invalidate loops that have setjmp. */
2484 current_loop = NULL;
2485 for (insn = f; insn; insn = NEXT_INSN (insn))
2487 if (GET_CODE (insn) == NOTE)
2488 switch (NOTE_LINE_NUMBER (insn))
2490 case NOTE_INSN_LOOP_BEG:
2491 next_loop = loops->array + num_loops;
2492 next_loop->num = num_loops;
2494 next_loop->start = insn;
2495 next_loop->outer = current_loop;
2496 current_loop = next_loop;
2499 case NOTE_INSN_SETJMP:
2500 /* In this case, we must invalidate our current loop and any
2502 for (loop = current_loop; loop; loop = loop->outer)
2505 if (loop_dump_stream)
2506 fprintf (loop_dump_stream,
2507 "\nLoop at %d ignored due to setjmp.\n",
2508 INSN_UID (loop->start));
2512 case NOTE_INSN_LOOP_CONT:
2513 current_loop->cont = insn;
2516 case NOTE_INSN_LOOP_VTOP:
2517 current_loop->vtop = insn;
2520 case NOTE_INSN_LOOP_END:
2524 current_loop->end = insn;
2525 current_loop = current_loop->outer;
2532 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2533 enclosing loop, but this doesn't matter. */
2534 uid_loop[INSN_UID (insn)] = current_loop;
2537 /* Any loop containing a label used in an initializer must be invalidated,
2538 because it can be jumped into from anywhere. */
2540 for (label = forced_labels; label; label = XEXP (label, 1))
2542 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2543 loop; loop = loop->outer)
2547 /* Any loop containing a label used for an exception handler must be
2548 invalidated, because it can be jumped into from anywhere. */
2550 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2552 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2553 loop; loop = loop->outer)
2557 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2558 loop that it is not contained within, that loop is marked invalid.
2559 If any INSN or CALL_INSN uses a label's address, then the loop containing
2560 that label is marked invalid, because it could be jumped into from
2563 Also look for blocks of code ending in an unconditional branch that
2564 exits the loop. If such a block is surrounded by a conditional
2565 branch around the block, move the block elsewhere (see below) and
2566 invert the jump to point to the code block. This may eliminate a
2567 label in our loop and will simplify processing by both us and a
2568 possible second cse pass. */
2570 for (insn = f; insn; insn = NEXT_INSN (insn))
2573 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2575 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2577 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2580 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2581 loop; loop = loop->outer)
2586 if (GET_CODE (insn) != JUMP_INSN)
2589 mark_loop_jump (PATTERN (insn), this_loop);
2591 /* See if this is an unconditional branch outside the loop. */
2593 && (GET_CODE (PATTERN (insn)) == RETURN
2594 || (any_uncondjump_p (insn)
2595 && onlyjump_p (insn)
2596 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2598 && get_max_uid () < max_uid_for_loop)
2601 rtx our_next = next_real_insn (insn);
2602 rtx last_insn_to_move = NEXT_INSN (insn);
2603 struct loop *dest_loop;
2604 struct loop *outer_loop = NULL;
2606 /* Go backwards until we reach the start of the loop, a label,
2608 for (p = PREV_INSN (insn);
2609 GET_CODE (p) != CODE_LABEL
2610 && ! (GET_CODE (p) == NOTE
2611 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2612 && GET_CODE (p) != JUMP_INSN;
2616 /* Check for the case where we have a jump to an inner nested
2617 loop, and do not perform the optimization in that case. */
2619 if (JUMP_LABEL (insn))
2621 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2624 for (outer_loop = dest_loop; outer_loop;
2625 outer_loop = outer_loop->outer)
2626 if (outer_loop == this_loop)
2631 /* Make sure that the target of P is within the current loop. */
2633 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2634 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2635 outer_loop = this_loop;
2637 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2638 we have a block of code to try to move.
2640 We look backward and then forward from the target of INSN
2641 to find a BARRIER at the same loop depth as the target.
2642 If we find such a BARRIER, we make a new label for the start
2643 of the block, invert the jump in P and point it to that label,
2644 and move the block of code to the spot we found. */
2647 && GET_CODE (p) == JUMP_INSN
2648 && JUMP_LABEL (p) != 0
2649 /* Just ignore jumps to labels that were never emitted.
2650 These always indicate compilation errors. */
2651 && INSN_UID (JUMP_LABEL (p)) != 0
2652 && any_condjump_p (p) && onlyjump_p (p)
2653 && next_real_insn (JUMP_LABEL (p)) == our_next
2654 /* If it's not safe to move the sequence, then we
2656 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2657 &last_insn_to_move))
2660 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2661 struct loop *target_loop = uid_loop[INSN_UID (target)];
2664 for (loc = target; loc; loc = PREV_INSN (loc))
2665 if (GET_CODE (loc) == BARRIER
2666 /* Don't move things inside a tablejump. */
2667 && ((loc2 = next_nonnote_insn (loc)) == 0
2668 || GET_CODE (loc2) != CODE_LABEL
2669 || (loc2 = next_nonnote_insn (loc2)) == 0
2670 || GET_CODE (loc2) != JUMP_INSN
2671 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2672 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2673 && uid_loop[INSN_UID (loc)] == target_loop)
2677 for (loc = target; loc; loc = NEXT_INSN (loc))
2678 if (GET_CODE (loc) == BARRIER
2679 /* Don't move things inside a tablejump. */
2680 && ((loc2 = next_nonnote_insn (loc)) == 0
2681 || GET_CODE (loc2) != CODE_LABEL
2682 || (loc2 = next_nonnote_insn (loc2)) == 0
2683 || GET_CODE (loc2) != JUMP_INSN
2684 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2685 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2686 && uid_loop[INSN_UID (loc)] == target_loop)
2691 rtx cond_label = JUMP_LABEL (p);
2692 rtx new_label = get_label_after (p);
2694 /* Ensure our label doesn't go away. */
2695 LABEL_NUSES (cond_label)++;
2697 /* Verify that uid_loop is large enough and that
2699 if (invert_jump (p, new_label, 1))
2703 /* If no suitable BARRIER was found, create a suitable
2704 one before TARGET. Since TARGET is a fall through
2705 path, we'll need to insert an jump around our block
2706 and a add a BARRIER before TARGET.
2708 This creates an extra unconditional jump outside
2709 the loop. However, the benefits of removing rarely
2710 executed instructions from inside the loop usually
2711 outweighs the cost of the extra unconditional jump
2712 outside the loop. */
2717 temp = gen_jump (JUMP_LABEL (insn));
2718 temp = emit_jump_insn_before (temp, target);
2719 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2720 LABEL_NUSES (JUMP_LABEL (insn))++;
2721 loc = emit_barrier_before (target);
2724 /* Include the BARRIER after INSN and copy the
2726 new_label = squeeze_notes (new_label,
2728 reorder_insns (new_label, last_insn_to_move, loc);
2730 /* All those insns are now in TARGET_LOOP. */
2732 q != NEXT_INSN (last_insn_to_move);
2734 uid_loop[INSN_UID (q)] = target_loop;
2736 /* The label jumped to by INSN is no longer a loop
2737 exit. Unless INSN does not have a label (e.g.,
2738 it is a RETURN insn), search loop->exit_labels
2739 to find its label_ref, and remove it. Also turn
2740 off LABEL_OUTSIDE_LOOP_P bit. */
2741 if (JUMP_LABEL (insn))
2743 for (q = 0, r = this_loop->exit_labels;
2745 q = r, r = LABEL_NEXTREF (r))
2746 if (XEXP (r, 0) == JUMP_LABEL (insn))
2748 LABEL_OUTSIDE_LOOP_P (r) = 0;
2750 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2752 this_loop->exit_labels = LABEL_NEXTREF (r);
2756 for (loop = this_loop; loop && loop != target_loop;
2760 /* If we didn't find it, then something is
2766 /* P is now a jump outside the loop, so it must be put
2767 in loop->exit_labels, and marked as such.
2768 The easiest way to do this is to just call
2769 mark_loop_jump again for P. */
2770 mark_loop_jump (PATTERN (p), this_loop);
2772 /* If INSN now jumps to the insn after it,
2774 if (JUMP_LABEL (insn) != 0
2775 && (next_real_insn (JUMP_LABEL (insn))
2776 == next_real_insn (insn)))
2780 /* Continue the loop after where the conditional
2781 branch used to jump, since the only branch insn
2782 in the block (if it still remains) is an inter-loop
2783 branch and hence needs no processing. */
2784 insn = NEXT_INSN (cond_label);
2786 if (--LABEL_NUSES (cond_label) == 0)
2787 delete_insn (cond_label);
2789 /* This loop will be continued with NEXT_INSN (insn). */
2790 insn = PREV_INSN (insn);
2797 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2798 loops it is contained in, mark the target loop invalid.
2800 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2803 mark_loop_jump (x, loop)
2807 struct loop *dest_loop;
2808 struct loop *outer_loop;
2811 switch (GET_CODE (x))
2824 /* There could be a label reference in here. */
2825 mark_loop_jump (XEXP (x, 0), loop);
2831 mark_loop_jump (XEXP (x, 0), loop);
2832 mark_loop_jump (XEXP (x, 1), loop);
2836 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2837 mark_loop_jump (XEXP (x, 1), loop);
2842 mark_loop_jump (XEXP (x, 0), loop);
2846 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2848 /* Link together all labels that branch outside the loop. This
2849 is used by final_[bg]iv_value and the loop unrolling code. Also
2850 mark this LABEL_REF so we know that this branch should predict
2853 /* A check to make sure the label is not in an inner nested loop,
2854 since this does not count as a loop exit. */
2857 for (outer_loop = dest_loop; outer_loop;
2858 outer_loop = outer_loop->outer)
2859 if (outer_loop == loop)
2865 if (loop && ! outer_loop)
2867 LABEL_OUTSIDE_LOOP_P (x) = 1;
2868 LABEL_NEXTREF (x) = loop->exit_labels;
2869 loop->exit_labels = x;
2871 for (outer_loop = loop;
2872 outer_loop && outer_loop != dest_loop;
2873 outer_loop = outer_loop->outer)
2874 outer_loop->exit_count++;
2877 /* If this is inside a loop, but not in the current loop or one enclosed
2878 by it, it invalidates at least one loop. */
2883 /* We must invalidate every nested loop containing the target of this
2884 label, except those that also contain the jump insn. */
2886 for (; dest_loop; dest_loop = dest_loop->outer)
2888 /* Stop when we reach a loop that also contains the jump insn. */
2889 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2890 if (dest_loop == outer_loop)
2893 /* If we get here, we know we need to invalidate a loop. */
2894 if (loop_dump_stream && ! dest_loop->invalid)
2895 fprintf (loop_dump_stream,
2896 "\nLoop at %d ignored due to multiple entry points.\n",
2897 INSN_UID (dest_loop->start));
2899 dest_loop->invalid = 1;
2904 /* If this is not setting pc, ignore. */
2905 if (SET_DEST (x) == pc_rtx)
2906 mark_loop_jump (SET_SRC (x), loop);
2910 mark_loop_jump (XEXP (x, 1), loop);
2911 mark_loop_jump (XEXP (x, 2), loop);
2916 for (i = 0; i < XVECLEN (x, 0); i++)
2917 mark_loop_jump (XVECEXP (x, 0, i), loop);
2921 for (i = 0; i < XVECLEN (x, 1); i++)
2922 mark_loop_jump (XVECEXP (x, 1, i), loop);
2926 /* Strictly speaking this is not a jump into the loop, only a possible
2927 jump out of the loop. However, we have no way to link the destination
2928 of this jump onto the list of exit labels. To be safe we mark this
2929 loop and any containing loops as invalid. */
2932 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2934 if (loop_dump_stream && ! outer_loop->invalid)
2935 fprintf (loop_dump_stream,
2936 "\nLoop at %d ignored due to unknown exit jump.\n",
2937 INSN_UID (outer_loop->start));
2938 outer_loop->invalid = 1;
2945 /* Return nonzero if there is a label in the range from
2946 insn INSN to and including the insn whose luid is END
2947 INSN must have an assigned luid (i.e., it must not have
2948 been previously created by loop.c). */
2951 labels_in_range_p (insn, end)
2955 while (insn && INSN_LUID (insn) <= end)
2957 if (GET_CODE (insn) == CODE_LABEL)
2959 insn = NEXT_INSN (insn);
2965 /* Record that a memory reference X is being set. */
2968 note_addr_stored (x, y, data)
2970 rtx y ATTRIBUTE_UNUSED;
2971 void *data ATTRIBUTE_UNUSED;
2973 struct loop_info *loop_info = data;
2975 if (x == 0 || GET_CODE (x) != MEM)
2978 /* Count number of memory writes.
2979 This affects heuristics in strength_reduce. */
2980 loop_info->num_mem_sets++;
2982 /* BLKmode MEM means all memory is clobbered. */
2983 if (GET_MODE (x) == BLKmode)
2985 if (RTX_UNCHANGING_P (x))
2986 loop_info->unknown_constant_address_altered = 1;
2988 loop_info->unknown_address_altered = 1;
2993 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2994 loop_info->store_mems);
2997 /* X is a value modified by an INSN that references a biv inside a loop
2998 exit test (ie, X is somehow related to the value of the biv). If X
2999 is a pseudo that is used more than once, then the biv is (effectively)
3000 used more than once. DATA is a pointer to a loop_regs structure. */
3003 note_set_pseudo_multiple_uses (x, y, data)
3005 rtx y ATTRIBUTE_UNUSED;
3008 struct loop_regs *regs = (struct loop_regs *) data;
3013 while (GET_CODE (x) == STRICT_LOW_PART
3014 || GET_CODE (x) == SIGN_EXTRACT
3015 || GET_CODE (x) == ZERO_EXTRACT
3016 || GET_CODE (x) == SUBREG)
3019 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
3022 /* If we do not have usage information, or if we know the register
3023 is used more than once, note that fact for check_dbra_loop. */
3024 if (REGNO (x) >= max_reg_before_loop
3025 || ! VARRAY_RTX (regs->single_usage, REGNO (x))
3026 || VARRAY_RTX (regs->single_usage, REGNO (x)) == const0_rtx)
3027 regs->multiple_uses = 1;
3030 /* Return nonzero if the rtx X is invariant over the current loop.
3032 The value is 2 if we refer to something only conditionally invariant.
3034 A memory ref is invariant if it is not volatile and does not conflict
3035 with anything stored in `loop_info->store_mems'. */
3038 loop_invariant_p (loop, x)
3039 const struct loop *loop;
3042 struct loop_info *loop_info = LOOP_INFO (loop);
3043 struct loop_regs *regs = LOOP_REGS (loop);
3045 register enum rtx_code code;
3046 register const char *fmt;
3047 int conditional = 0;
3052 code = GET_CODE (x);
3062 /* A LABEL_REF is normally invariant, however, if we are unrolling
3063 loops, and this label is inside the loop, then it isn't invariant.
3064 This is because each unrolled copy of the loop body will have
3065 a copy of this label. If this was invariant, then an insn loading
3066 the address of this label into a register might get moved outside
3067 the loop, and then each loop body would end up using the same label.
3069 We don't know the loop bounds here though, so just fail for all
3071 if (flag_unroll_loops)
3078 case UNSPEC_VOLATILE:
3082 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3083 since the reg might be set by initialization within the loop. */
3085 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3086 || x == arg_pointer_rtx)
3087 && ! current_function_has_nonlocal_goto)
3090 if (LOOP_INFO (loop)->has_call
3091 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3094 if (VARRAY_INT (regs->set_in_loop, REGNO (x)) < 0)
3097 return VARRAY_INT (regs->set_in_loop, REGNO (x)) == 0;
3100 /* Volatile memory references must be rejected. Do this before
3101 checking for read-only items, so that volatile read-only items
3102 will be rejected also. */
3103 if (MEM_VOLATILE_P (x))
3106 /* See if there is any dependence between a store and this load. */
3107 mem_list_entry = loop_info->store_mems;
3108 while (mem_list_entry)
3110 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3114 mem_list_entry = XEXP (mem_list_entry, 1);
3117 /* It's not invalidated by a store in memory
3118 but we must still verify the address is invariant. */
3122 /* Don't mess with insns declared volatile. */
3123 if (MEM_VOLATILE_P (x))
3131 fmt = GET_RTX_FORMAT (code);
3132 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3136 int tem = loop_invariant_p (loop, XEXP (x, i));
3142 else if (fmt[i] == 'E')
3145 for (j = 0; j < XVECLEN (x, i); j++)
3147 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3157 return 1 + conditional;
3160 /* Return nonzero if all the insns in the loop that set REG
3161 are INSN and the immediately following insns,
3162 and if each of those insns sets REG in an invariant way
3163 (not counting uses of REG in them).
3165 The value is 2 if some of these insns are only conditionally invariant.
3167 We assume that INSN itself is the first set of REG
3168 and that its source is invariant. */
3171 consec_sets_invariant_p (loop, reg, n_sets, insn)
3172 const struct loop *loop;
3176 struct loop_regs *regs = LOOP_REGS (loop);
3178 unsigned int regno = REGNO (reg);
3180 /* Number of sets we have to insist on finding after INSN. */
3181 int count = n_sets - 1;
3182 int old = VARRAY_INT (regs->set_in_loop, regno);
3186 /* If N_SETS hit the limit, we can't rely on its value. */
3190 VARRAY_INT (regs->set_in_loop, regno) = 0;
3194 register enum rtx_code code;
3198 code = GET_CODE (p);
3200 /* If library call, skip to end of it. */
3201 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3206 && (set = single_set (p))
3207 && GET_CODE (SET_DEST (set)) == REG
3208 && REGNO (SET_DEST (set)) == regno)
3210 this = loop_invariant_p (loop, SET_SRC (set));
3213 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3215 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3216 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3218 this = (CONSTANT_P (XEXP (temp, 0))
3219 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3220 && loop_invariant_p (loop, XEXP (temp, 0))));
3227 else if (code != NOTE)
3229 VARRAY_INT (regs->set_in_loop, regno) = old;
3234 VARRAY_INT (regs->set_in_loop, regno) = old;
3235 /* If loop_invariant_p ever returned 2, we return 2. */
3236 return 1 + (value & 2);
3240 /* I don't think this condition is sufficient to allow INSN
3241 to be moved, so we no longer test it. */
3243 /* Return 1 if all insns in the basic block of INSN and following INSN
3244 that set REG are invariant according to TABLE. */
3247 all_sets_invariant_p (reg, insn, table)
3251 register rtx p = insn;
3252 register int regno = REGNO (reg);
3256 register enum rtx_code code;
3258 code = GET_CODE (p);
3259 if (code == CODE_LABEL || code == JUMP_INSN)
3261 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3262 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3263 && REGNO (SET_DEST (PATTERN (p))) == regno)
3265 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3272 /* Look at all uses (not sets) of registers in X. For each, if it is
3273 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3274 a different insn, set USAGE[REGNO] to const0_rtx. */
3277 find_single_use_in_loop (insn, x, usage)
3282 enum rtx_code code = GET_CODE (x);
3283 const char *fmt = GET_RTX_FORMAT (code);
3287 VARRAY_RTX (usage, REGNO (x))
3288 = (VARRAY_RTX (usage, REGNO (x)) != 0
3289 && VARRAY_RTX (usage, REGNO (x)) != insn)
3290 ? const0_rtx : insn;
3292 else if (code == SET)
3294 /* Don't count SET_DEST if it is a REG; otherwise count things
3295 in SET_DEST because if a register is partially modified, it won't
3296 show up as a potential movable so we don't care how USAGE is set
3298 if (GET_CODE (SET_DEST (x)) != REG)
3299 find_single_use_in_loop (insn, SET_DEST (x), usage);
3300 find_single_use_in_loop (insn, SET_SRC (x), usage);
3303 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3305 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3306 find_single_use_in_loop (insn, XEXP (x, i), usage);
3307 else if (fmt[i] == 'E')
3308 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3309 find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
3313 /* Count and record any set in X which is contained in INSN. Update
3314 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3317 count_one_set (regs, insn, x, may_not_move, last_set)
3318 struct loop_regs *regs;
3320 varray_type may_not_move;
3323 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3324 /* Don't move a reg that has an explicit clobber.
3325 It's not worth the pain to try to do it correctly. */
3326 VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
3328 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3330 rtx dest = SET_DEST (x);
3331 while (GET_CODE (dest) == SUBREG
3332 || GET_CODE (dest) == ZERO_EXTRACT
3333 || GET_CODE (dest) == SIGN_EXTRACT
3334 || GET_CODE (dest) == STRICT_LOW_PART)
3335 dest = XEXP (dest, 0);
3336 if (GET_CODE (dest) == REG)
3338 register int regno = REGNO (dest);
3339 /* If this is the first setting of this reg
3340 in current basic block, and it was set before,
3341 it must be set in two basic blocks, so it cannot
3342 be moved out of the loop. */
3343 if (VARRAY_INT (regs->set_in_loop, regno) > 0
3344 && last_set[regno] == 0)
3345 VARRAY_CHAR (may_not_move, regno) = 1;
3346 /* If this is not first setting in current basic block,
3347 see if reg was used in between previous one and this.
3348 If so, neither one can be moved. */
3349 if (last_set[regno] != 0
3350 && reg_used_between_p (dest, last_set[regno], insn))
3351 VARRAY_CHAR (may_not_move, regno) = 1;
3352 if (VARRAY_INT (regs->set_in_loop, regno) < 127)
3353 ++VARRAY_INT (regs->set_in_loop, regno);
3354 last_set[regno] = insn;
3359 /* Increment REGS->SET_IN_LOOP at the index of each register
3360 that is modified by an insn between FROM and TO.
3361 If the value of an element of REGS->SET_IN_LOOP becomes 127 or more,
3362 stop incrementing it, to avoid overflow.
3364 Store in SINGLE_USAGE[I] the single insn in which register I is
3365 used, if it is only used once. Otherwise, it is set to 0 (for no
3366 uses) or const0_rtx for more than one use. This parameter may be zero,
3367 in which case this processing is not done.
3369 Store in *COUNT_PTR the number of actual instruction
3370 in the loop. We use this to decide what is worth moving out. */
3372 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3373 In that case, it is the insn that last set reg n. */
3376 count_loop_regs_set (loop, may_not_move, single_usage, count_ptr, nregs)
3377 const struct loop *loop;
3378 varray_type may_not_move;
3379 varray_type single_usage;
3383 struct loop_regs *regs = LOOP_REGS (loop);
3384 register rtx *last_set = (rtx *) xcalloc (nregs, sizeof (rtx));
3386 register int count = 0;
3388 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
3389 insn = NEXT_INSN (insn))
3395 /* Record registers that have exactly one use. */
3396 find_single_use_in_loop (insn, PATTERN (insn), single_usage);
3398 /* Include uses in REG_EQUAL notes. */
3399 if (REG_NOTES (insn))
3400 find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
3402 if (GET_CODE (PATTERN (insn)) == SET
3403 || GET_CODE (PATTERN (insn)) == CLOBBER)
3404 count_one_set (regs, insn, PATTERN (insn), may_not_move, last_set);
3405 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3408 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3409 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
3410 may_not_move, last_set);
3414 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
3415 memset ((char *) last_set, 0, nregs * sizeof (rtx));
3423 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3424 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3425 contained in insn INSN is used by any insn that precedes INSN in
3426 cyclic order starting from the loop entry point.
3428 We don't want to use INSN_LUID here because if we restrict INSN to those
3429 that have a valid INSN_LUID, it means we cannot move an invariant out
3430 from an inner loop past two loops. */
3433 loop_reg_used_before_p (loop, set, insn)
3434 const struct loop *loop;
3437 rtx reg = SET_DEST (set);
3440 /* Scan forward checking for register usage. If we hit INSN, we
3441 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3442 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3444 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3454 /* A "basic induction variable" or biv is a pseudo reg that is set
3455 (within this loop) only by incrementing or decrementing it. */
3456 /* A "general induction variable" or giv is a pseudo reg whose
3457 value is a linear function of a biv. */
3459 /* Bivs are recognized by `basic_induction_var';
3460 Givs by `general_induction_var'. */
3462 /* Communication with routines called via `note_stores'. */
3464 static rtx note_insn;
3466 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3468 static rtx addr_placeholder;
3470 /* ??? Unfinished optimizations, and possible future optimizations,
3471 for the strength reduction code. */
3473 /* ??? The interaction of biv elimination, and recognition of 'constant'
3474 bivs, may cause problems. */
3476 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3477 performance problems.
3479 Perhaps don't eliminate things that can be combined with an addressing
3480 mode. Find all givs that have the same biv, mult_val, and add_val;
3481 then for each giv, check to see if its only use dies in a following
3482 memory address. If so, generate a new memory address and check to see
3483 if it is valid. If it is valid, then store the modified memory address,
3484 otherwise, mark the giv as not done so that it will get its own iv. */
3486 /* ??? Could try to optimize branches when it is known that a biv is always
3489 /* ??? When replace a biv in a compare insn, we should replace with closest
3490 giv so that an optimized branch can still be recognized by the combiner,
3491 e.g. the VAX acb insn. */
3493 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3494 was rerun in loop_optimize whenever a register was added or moved.
3495 Also, some of the optimizations could be a little less conservative. */
3497 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3498 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3501 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3502 loop iteration except for the last one.
3504 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3508 for_each_insn_in_loop (loop, fncall)
3510 loop_insn_callback fncall;
3512 /* This is 1 if current insn is not executed at least once for every loop
3514 int not_every_iteration = 0;
3515 int maybe_multiple = 0;
3516 int past_loop_latch = 0;
3520 /* If loop_scan_start points to the loop exit test, we have to be wary of
3521 subversive use of gotos inside expression statements. */
3522 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3523 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3525 /* Scan through loop to find all possible bivs. */
3527 for (p = next_insn_in_loop (loop, loop->scan_start);
3529 p = next_insn_in_loop (loop, p))
3531 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3533 /* Past CODE_LABEL, we get to insns that may be executed multiple
3534 times. The only way we can be sure that they can't is if every
3535 jump insn between here and the end of the loop either
3536 returns, exits the loop, is a jump to a location that is still
3537 behind the label, or is a jump to the loop start. */
3539 if (GET_CODE (p) == CODE_LABEL)
3547 insn = NEXT_INSN (insn);
3548 if (insn == loop->scan_start)
3550 if (insn == loop->end)
3556 if (insn == loop->scan_start)
3560 if (GET_CODE (insn) == JUMP_INSN
3561 && GET_CODE (PATTERN (insn)) != RETURN
3562 && (!any_condjump_p (insn)
3563 || (JUMP_LABEL (insn) != 0
3564 && JUMP_LABEL (insn) != loop->scan_start
3565 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3573 /* Past a jump, we get to insns for which we can't count
3574 on whether they will be executed during each iteration. */
3575 /* This code appears twice in strength_reduce. There is also similar
3576 code in scan_loop. */
3577 if (GET_CODE (p) == JUMP_INSN
3578 /* If we enter the loop in the middle, and scan around to the
3579 beginning, don't set not_every_iteration for that.
3580 This can be any kind of jump, since we want to know if insns
3581 will be executed if the loop is executed. */
3582 && !(JUMP_LABEL (p) == loop->top
3583 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3584 && any_uncondjump_p (p))
3585 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3589 /* If this is a jump outside the loop, then it also doesn't
3590 matter. Check to see if the target of this branch is on the
3591 loop->exits_labels list. */
3593 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3594 if (XEXP (label, 0) == JUMP_LABEL (p))
3598 not_every_iteration = 1;
3601 else if (GET_CODE (p) == NOTE)
3603 /* At the virtual top of a converted loop, insns are again known to
3604 be executed each iteration: logically, the loop begins here
3605 even though the exit code has been duplicated.
3607 Insns are also again known to be executed each iteration at
3608 the LOOP_CONT note. */
3609 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3610 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3612 not_every_iteration = 0;
3613 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3615 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3619 /* Note if we pass a loop latch. If we do, then we can not clear
3620 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3621 a loop since a jump before the last CODE_LABEL may have started
3622 a new loop iteration.
3624 Note that LOOP_TOP is only set for rotated loops and we need
3625 this check for all loops, so compare against the CODE_LABEL
3626 which immediately follows LOOP_START. */
3627 if (GET_CODE (p) == JUMP_INSN
3628 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3629 past_loop_latch = 1;
3631 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3632 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3633 or not an insn is known to be executed each iteration of the
3634 loop, whether or not any iterations are known to occur.
3636 Therefore, if we have just passed a label and have no more labels
3637 between here and the test insn of the loop, and we have not passed
3638 a jump to the top of the loop, then we know these insns will be
3639 executed each iteration. */
3641 if (not_every_iteration
3643 && GET_CODE (p) == CODE_LABEL
3644 && no_labels_between_p (p, loop->end)
3645 && loop_insn_first_p (p, loop->cont))
3646 not_every_iteration = 0;
3651 loop_bivs_find (loop)
3654 struct loop_regs *regs = LOOP_REGS (loop);
3655 struct loop_ivs *ivs = LOOP_IVS (loop);
3656 /* Temporary list pointers for traversing ivs->list. */
3657 struct iv_class *bl, **backbl;
3661 for_each_insn_in_loop (loop, check_insn_for_bivs);
3663 /* Scan ivs->list to remove all regs that proved not to be bivs.
3664 Make a sanity check against regs->n_times_set. */
3665 for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
3667 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3668 /* Above happens if register modified by subreg, etc. */
3669 /* Make sure it is not recognized as a basic induction var: */
3670 || VARRAY_INT (regs->n_times_set, bl->regno) != bl->biv_count
3671 /* If never incremented, it is invariant that we decided not to
3672 move. So leave it alone. */
3673 || ! bl->incremented)
3675 if (loop_dump_stream)
3676 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3678 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3679 ? "not induction variable"
3680 : (! bl->incremented ? "never incremented"
3683 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3690 if (loop_dump_stream)
3691 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3697 /* Determine how BIVS are initialised by looking through pre-header
3698 extended basic block. */
3700 loop_bivs_init_find (loop)
3703 struct loop_ivs *ivs = LOOP_IVS (loop);
3704 /* Temporary list pointers for traversing ivs->list. */
3705 struct iv_class *bl;
3709 /* Find initial value for each biv by searching backwards from loop_start,
3710 halting at first label. Also record any test condition. */
3713 for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3719 if (GET_CODE (p) == CALL_INSN)
3723 note_stores (PATTERN (p), record_initial, ivs);
3725 /* Record any test of a biv that branches around the loop if no store
3726 between it and the start of loop. We only care about tests with
3727 constants and registers and only certain of those. */
3728 if (GET_CODE (p) == JUMP_INSN
3729 && JUMP_LABEL (p) != 0
3730 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
3731 && (test = get_condition_for_loop (loop, p)) != 0
3732 && GET_CODE (XEXP (test, 0)) == REG
3733 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3734 && (bl = REG_IV_CLASS (ivs, REGNO (XEXP (test, 0)))) != 0
3735 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop->start)
3736 && bl->init_insn == 0)
3738 /* If an NE test, we have an initial value! */
3739 if (GET_CODE (test) == NE)
3742 bl->init_set = gen_rtx_SET (VOIDmode,
3743 XEXP (test, 0), XEXP (test, 1));
3746 bl->initial_test = test;
3752 /* Look at the each biv and see if we can say anything better about its
3753 initial value from any initializing insns set up above. (This is done
3754 in two passes to avoid missing SETs in a PARALLEL.) */
3756 loop_bivs_check (loop)
3759 struct loop_ivs *ivs = LOOP_IVS (loop);
3760 /* Temporary list pointers for traversing ivs->list. */
3761 struct iv_class *bl;
3762 struct iv_class **backbl;
3764 for (backbl = &ivs->list; (bl = *backbl); backbl = &bl->next)
3769 if (! bl->init_insn)
3772 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3773 is a constant, use the value of that. */
3774 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3775 && CONSTANT_P (XEXP (note, 0)))
3776 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3777 && CONSTANT_P (XEXP (note, 0))))
3778 src = XEXP (note, 0);
3780 src = SET_SRC (bl->init_set);
3782 if (loop_dump_stream)
3783 fprintf (loop_dump_stream,
3784 "Biv %d initialized at insn %d: initial value ",
3785 bl->regno, INSN_UID (bl->init_insn));
3787 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3788 || GET_MODE (src) == VOIDmode)
3789 && valid_initial_value_p (src, bl->init_insn,
3790 LOOP_INFO (loop)->pre_header_has_call,
3793 bl->initial_value = src;
3795 if (loop_dump_stream)
3797 if (GET_CODE (src) == CONST_INT)
3799 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
3801 fputc ('\n', loop_dump_stream);
3805 print_rtl (loop_dump_stream, src);
3806 fprintf (loop_dump_stream, "\n");
3810 /* If we can't make it a giv,
3811 let biv keep initial value of "itself". */
3812 else if (loop_dump_stream)
3813 fprintf (loop_dump_stream, "is complex\n");
3818 /* Search the loop for general induction variables. */
3821 loop_givs_find (loop)
3824 for_each_insn_in_loop (loop, check_insn_for_givs);
3828 /* For each giv for which we still don't know whether or not it is
3829 replaceable, check to see if it is replaceable because its final value
3830 can be calculated. */
3833 loop_givs_check (loop)
3836 struct loop_ivs *ivs = LOOP_IVS (loop);
3837 struct iv_class *bl;
3839 for (bl = ivs->list; bl; bl = bl->next)
3841 struct induction *v;
3843 for (v = bl->giv; v; v = v->next_iv)
3844 if (! v->replaceable && ! v->not_replaceable)
3845 check_final_value (loop, v);
3850 /* Return non-zero if it is possible to eliminate the biv BL provided
3851 all givs are reduced. This is possible if either the reg is not
3852 used outside the loop, or we can compute what its final value will
3856 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3858 struct iv_class *bl;
3862 /* For architectures with a decrement_and_branch_until_zero insn,
3863 don't do this if we put a REG_NONNEG note on the endtest for this
3866 #ifdef HAVE_decrement_and_branch_until_zero
3869 if (loop_dump_stream)
3870 fprintf (loop_dump_stream,
3871 "Cannot eliminate nonneg biv %d.\n", bl->regno);
3876 /* Check that biv is used outside loop or if it has a final value.
3877 Compare against bl->init_insn rather than loop->start. We aren't
3878 concerned with any uses of the biv between init_insn and
3879 loop->start since these won't be affected by the value of the biv
3880 elsewhere in the function, so long as init_insn doesn't use the
3883 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3885 && INSN_UID (bl->init_insn) < max_uid_for_loop
3886 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3887 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3888 || (bl->final_value = final_biv_value (loop, bl)))
3889 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3891 if (loop_dump_stream)
3893 fprintf (loop_dump_stream,
3894 "Cannot eliminate biv %d.\n",
3896 fprintf (loop_dump_stream,
3897 "First use: insn %d, last use: insn %d.\n",
3898 REGNO_FIRST_UID (bl->regno),
3899 REGNO_LAST_UID (bl->regno));
3905 /* Reduce each giv of BL that we have decided to reduce. */
3908 loop_givs_reduce (loop, bl)
3910 struct iv_class *bl;
3912 struct induction *v;
3914 for (v = bl->giv; v; v = v->next_iv)
3916 struct induction *tv;
3917 if (! v->ignore && v->same == 0)
3919 int auto_inc_opt = 0;
3921 /* If the code for derived givs immediately below has already
3922 allocated a new_reg, we must keep it. */
3924 v->new_reg = gen_reg_rtx (v->mode);
3927 /* If the target has auto-increment addressing modes, and
3928 this is an address giv, then try to put the increment
3929 immediately after its use, so that flow can create an
3930 auto-increment addressing mode. */
3931 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
3932 && bl->biv->always_executed && ! bl->biv->maybe_multiple
3933 /* We don't handle reversed biv's because bl->biv->insn
3934 does not have a valid INSN_LUID. */
3936 && v->always_executed && ! v->maybe_multiple
3937 && INSN_UID (v->insn) < max_uid_for_loop)
3939 /* If other giv's have been combined with this one, then
3940 this will work only if all uses of the other giv's occur
3941 before this giv's insn. This is difficult to check.
3943 We simplify this by looking for the common case where
3944 there is one DEST_REG giv, and this giv's insn is the
3945 last use of the dest_reg of that DEST_REG giv. If the
3946 increment occurs after the address giv, then we can
3947 perform the optimization. (Otherwise, the increment
3948 would have to go before other_giv, and we would not be
3949 able to combine it with the address giv to get an
3950 auto-inc address.) */
3951 if (v->combined_with)
3953 struct induction *other_giv = 0;
3955 for (tv = bl->giv; tv; tv = tv->next_iv)
3963 if (! tv && other_giv
3964 && REGNO (other_giv->dest_reg) < max_reg_before_loop
3965 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
3966 == INSN_UID (v->insn))
3967 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
3970 /* Check for case where increment is before the address
3971 giv. Do this test in "loop order". */
3972 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
3973 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3974 || (INSN_LUID (bl->biv->insn)
3975 > INSN_LUID (loop->scan_start))))
3976 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3977 && (INSN_LUID (loop->scan_start)
3978 < INSN_LUID (bl->biv->insn))))
3987 /* We can't put an insn immediately after one setting
3988 cc0, or immediately before one using cc0. */
3989 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
3990 || (auto_inc_opt == -1
3991 && (prev = prev_nonnote_insn (v->insn)) != 0
3993 && sets_cc0_p (PATTERN (prev))))
3999 v->auto_inc_opt = 1;
4003 /* For each place where the biv is incremented, add an insn
4004 to increment the new, reduced reg for the giv. */
4005 for (tv = bl->biv; tv; tv = tv->next_iv)
4010 insert_before = tv->insn;
4011 else if (auto_inc_opt == 1)
4012 insert_before = NEXT_INSN (v->insn);
4014 insert_before = v->insn;
4016 if (tv->mult_val == const1_rtx)
4017 emit_iv_add_mult (tv->add_val, v->mult_val,
4018 v->new_reg, v->new_reg, insert_before);
4019 else /* tv->mult_val == const0_rtx */
4020 /* A multiply is acceptable here
4021 since this is presumed to be seldom executed. */
4022 emit_iv_add_mult (tv->add_val, v->mult_val,
4023 v->add_val, v->new_reg, insert_before);
4026 /* Add code at loop start to initialize giv's reduced reg. */
4028 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4029 v->mult_val, v->add_val, v->new_reg,
4036 /* Check for givs whose first use is their definition and whose
4037 last use is the definition of another giv. If so, it is likely
4038 dead and should not be used to derive another giv nor to
4042 loop_givs_dead_check (loop, bl)
4043 struct loop *loop ATTRIBUTE_UNUSED;
4044 struct iv_class *bl;
4046 struct induction *v;
4048 for (v = bl->giv; v; v = v->next_iv)
4051 || (v->same && v->same->ignore))
4054 if (v->giv_type == DEST_REG
4055 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4057 struct induction *v1;
4059 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4060 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4068 loop_givs_rescan (loop, bl, reg_map, end_insert_before)
4070 struct iv_class *bl;
4072 rtx end_insert_before;
4074 struct induction *v;
4076 for (v = bl->giv; v; v = v->next_iv)
4078 if (v->same && v->same->ignore)
4084 /* Update expression if this was combined, in case other giv was
4087 v->new_reg = replace_rtx (v->new_reg,
4088 v->same->dest_reg, v->same->new_reg);
4090 /* See if this register is known to be a pointer to something. If
4091 so, see if we can find the alignment. First see if there is a
4092 destination register that is a pointer. If so, this shares the
4093 alignment too. Next see if we can deduce anything from the
4094 computational information. If not, and this is a DEST_ADDR
4095 giv, at least we know that it's a pointer, though we don't know
4097 if (GET_CODE (v->new_reg) == REG
4098 && v->giv_type == DEST_REG
4099 && REG_POINTER (v->dest_reg))
4100 mark_reg_pointer (v->new_reg,
4101 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
4102 else if (GET_CODE (v->new_reg) == REG
4103 && REG_POINTER (v->src_reg))
4105 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4108 || GET_CODE (v->add_val) != CONST_INT
4109 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4112 mark_reg_pointer (v->new_reg, align);
4114 else if (GET_CODE (v->new_reg) == REG
4115 && GET_CODE (v->add_val) == REG
4116 && REG_POINTER (v->add_val))
4118 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4120 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4121 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4124 mark_reg_pointer (v->new_reg, align);
4126 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4127 mark_reg_pointer (v->new_reg, 0);
4129 if (v->giv_type == DEST_ADDR)
4130 /* Store reduced reg as the address in the memref where we found
4132 validate_change (v->insn, v->location, v->new_reg, 0);
4133 else if (v->replaceable)
4135 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4139 /* Not replaceable; emit an insn to set the original giv reg from
4140 the reduced giv, same as above. */
4141 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4145 /* When a loop is reversed, givs which depend on the reversed
4146 biv, and which are live outside the loop, must be set to their
4147 correct final value. This insn is only needed if the giv is
4148 not replaceable. The correct final value is the same as the
4149 value that the giv starts the reversed loop with. */
4150 if (bl->reversed && ! v->replaceable)
4151 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4152 v->mult_val, v->add_val, v->dest_reg,
4154 else if (v->final_value)
4158 /* If the loop has multiple exits, emit the insn before the
4159 loop to ensure that it will always be executed no matter
4160 how the loop exits. Otherwise, emit the insn after the loop,
4161 since this is slightly more efficient. */
4162 if (loop->exit_count)
4163 insert_before = loop->start;
4165 insert_before = end_insert_before;
4166 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4170 if (loop_dump_stream)
4172 fprintf (loop_dump_stream, "giv at %d reduced to ",
4173 INSN_UID (v->insn));
4174 print_rtl (loop_dump_stream, v->new_reg);
4175 fprintf (loop_dump_stream, "\n");
4182 loop_giv_reduce_benefit (loop, bl, v, test_reg)
4183 struct loop *loop ATTRIBUTE_UNUSED;
4184 struct iv_class *bl;
4185 struct induction *v;
4191 benefit = v->benefit;
4192 PUT_MODE (test_reg, v->mode);
4193 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4194 test_reg, test_reg);
4196 /* Reduce benefit if not replaceable, since we will insert a
4197 move-insn to replace the insn that calculates this giv. Don't do
4198 this unless the giv is a user variable, since it will often be
4199 marked non-replaceable because of the duplication of the exit
4200 code outside the loop. In such a case, the copies we insert are
4201 dead and will be deleted. So they don't have a cost. Similar
4202 situations exist. */
4203 /* ??? The new final_[bg]iv_value code does a much better job of
4204 finding replaceable giv's, and hence this code may no longer be
4206 if (! v->replaceable && ! bl->eliminable
4207 && REG_USERVAR_P (v->dest_reg))
4208 benefit -= copy_cost;
4210 /* Decrease the benefit to count the add-insns that we will insert
4211 to increment the reduced reg for the giv. ??? This can
4212 overestimate the run-time cost of the additional insns, e.g. if
4213 there are multiple basic blocks that increment the biv, but only
4214 one of these blocks is executed during each iteration. There is
4215 no good way to detect cases like this with the current structure
4216 of the loop optimizer. This code is more accurate for
4217 determining code size than run-time benefits. */
4218 benefit -= add_cost * bl->biv_count;
4220 /* Decide whether to strength-reduce this giv or to leave the code
4221 unchanged (recompute it from the biv each time it is used). This
4222 decision can be made independently for each giv. */
4225 /* Attempt to guess whether autoincrement will handle some of the
4226 new add insns; if so, increase BENEFIT (undo the subtraction of
4227 add_cost that was done above). */
4228 if (v->giv_type == DEST_ADDR
4229 /* Increasing the benefit is risky, since this is only a guess.
4230 Avoid increasing register pressure in cases where there would
4231 be no other benefit from reducing this giv. */
4233 && GET_CODE (v->mult_val) == CONST_INT)
4235 if (HAVE_POST_INCREMENT
4236 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4237 benefit += add_cost * bl->biv_count;
4238 else if (HAVE_PRE_INCREMENT
4239 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4240 benefit += add_cost * bl->biv_count;
4241 else if (HAVE_POST_DECREMENT
4242 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4243 benefit += add_cost * bl->biv_count;
4244 else if (HAVE_PRE_DECREMENT
4245 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4246 benefit += add_cost * bl->biv_count;
4254 /* Free IV structures for LOOP. */
4257 loop_ivs_free (loop)
4260 struct loop_ivs *ivs = LOOP_IVS (loop);
4261 struct iv_class *iv = ivs->list;
4267 struct iv_class *next = iv->next;
4268 struct induction *induction;
4269 struct induction *next_induction;
4271 for (induction = iv->biv; induction; induction = next_induction)
4273 next_induction = induction->next_iv;
4276 for (induction = iv->giv; induction; induction = next_induction)
4278 next_induction = induction->next_iv;
4288 /* Perform strength reduction and induction variable elimination.
4290 Pseudo registers created during this function will be beyond the
4291 last valid index in several tables including regs->n_times_set and
4292 regno_last_uid. This does not cause a problem here, because the
4293 added registers cannot be givs outside of their loop, and hence
4294 will never be reconsidered. But scan_loop must check regnos to
4295 make sure they are in bounds. */
4298 strength_reduce (loop, insn_count, flags)
4303 struct loop_info *loop_info = LOOP_INFO (loop);
4304 struct loop_regs *regs = LOOP_REGS (loop);
4305 struct loop_ivs *ivs = LOOP_IVS (loop);
4307 /* Temporary list pointer for traversing ivs->list. */
4308 struct iv_class *bl;
4309 /* Ratio of extra register life span we can justify
4310 for saving an instruction. More if loop doesn't call subroutines
4311 since in that case saving an insn makes more difference
4312 and more registers are available. */
4313 /* ??? could set this to last value of threshold in move_movables */
4314 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
4315 /* Map of pseudo-register replacements. */
4316 rtx *reg_map = NULL;
4318 rtx end_insert_before;
4319 int unrolled_insn_copies = 0;
4320 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
4322 addr_placeholder = gen_reg_rtx (Pmode);
4324 /* Save insn immediately after the loop_end. Insns inserted after loop_end
4325 must be put before this insn, so that they will appear in the right
4326 order (i.e. loop order).
4328 If loop_end is the end of the current function, then emit a
4329 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
4331 if (NEXT_INSN (loop->end) != 0)
4332 end_insert_before = NEXT_INSN (loop->end);
4334 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop->end);
4336 ivs->n_regs = max_reg_before_loop;
4337 ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
4339 /* Find all BIVs in loop. */
4340 loop_bivs_find (loop);
4342 /* Exit if there are no bivs. */
4345 /* Can still unroll the loop anyways, but indicate that there is no
4346 strength reduction info available. */
4347 if (flags & LOOP_UNROLL)
4348 unroll_loop (loop, insn_count, end_insert_before, 0);
4350 loop_ivs_free (loop);
4354 /* Determine how BIVS are initialised by looking through pre-header
4355 extended basic block. */
4356 loop_bivs_init_find (loop);
4358 /* Look at the each biv and see if we can say anything better about its
4359 initial value from any initializing insns set up above. */
4360 loop_bivs_check (loop);
4362 /* Search the loop for general induction variables. */
4363 loop_givs_find (loop);
4365 /* Try to calculate and save the number of loop iterations. This is
4366 set to zero if the actual number can not be calculated. This must
4367 be called after all giv's have been identified, since otherwise it may
4368 fail if the iteration variable is a giv. */
4369 loop_iterations (loop);
4371 /* Now for each giv for which we still don't know whether or not it is
4372 replaceable, check to see if it is replaceable because its final value
4373 can be calculated. This must be done after loop_iterations is called,
4374 so that final_giv_value will work correctly. */
4375 loop_givs_check (loop);
4377 /* Try to prove that the loop counter variable (if any) is always
4378 nonnegative; if so, record that fact with a REG_NONNEG note
4379 so that "decrement and branch until zero" insn can be used. */
4380 check_dbra_loop (loop, insn_count);
4382 /* Create reg_map to hold substitutions for replaceable giv regs.
4383 Some givs might have been made from biv increments, so look at
4384 ivs->reg_iv_type for a suitable size. */
4385 reg_map_size = ivs->n_regs;
4386 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
4388 /* Examine each iv class for feasibility of strength reduction/induction
4389 variable elimination. */
4391 for (bl = ivs->list; bl; bl = bl->next)
4393 struct induction *v;
4396 /* Test whether it will be possible to eliminate this biv
4397 provided all givs are reduced. */
4398 bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
4400 /* Check each extension dependent giv in this class to see if its
4401 root biv is safe from wrapping in the interior mode. */
4402 check_ext_dependant_givs (bl, loop_info);
4404 /* Combine all giv's for this iv_class. */
4405 combine_givs (regs, bl);
4407 /* This will be true at the end, if all givs which depend on this
4408 biv have been strength reduced.
4409 We can't (currently) eliminate the biv unless this is so. */
4410 bl->all_reduced = 1;
4412 for (v = bl->giv; v; v = v->next_iv)
4414 struct induction *tv;
4416 if (v->ignore || v->same)
4419 benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
4421 /* If an insn is not to be strength reduced, then set its ignore
4422 flag, and clear bl->all_reduced. */
4424 /* A giv that depends on a reversed biv must be reduced if it is
4425 used after the loop exit, otherwise, it would have the wrong
4426 value after the loop exit. To make it simple, just reduce all
4427 of such giv's whether or not we know they are used after the loop
4430 if (! flag_reduce_all_givs
4431 && v->lifetime * threshold * benefit < insn_count
4434 if (loop_dump_stream)
4435 fprintf (loop_dump_stream,
4436 "giv of insn %d not worth while, %d vs %d.\n",
4438 v->lifetime * threshold * benefit, insn_count);
4440 bl->all_reduced = 0;
4444 /* Check that we can increment the reduced giv without a
4445 multiply insn. If not, reject it. */
4447 for (tv = bl->biv; tv; tv = tv->next_iv)
4448 if (tv->mult_val == const1_rtx
4449 && ! product_cheap_p (tv->add_val, v->mult_val))
4451 if (loop_dump_stream)
4452 fprintf (loop_dump_stream,
4453 "giv of insn %d: would need a multiply.\n",
4454 INSN_UID (v->insn));
4456 bl->all_reduced = 0;
4462 /* Check for givs whose first use is their definition and whose
4463 last use is the definition of another giv. If so, it is likely
4464 dead and should not be used to derive another giv nor to
4466 loop_givs_dead_check (loop, bl);
4468 /* Reduce each giv that we decided to reduce. */
4469 loop_givs_reduce (loop, bl);
4471 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4474 For each giv register that can be reduced now: if replaceable,
4475 substitute reduced reg wherever the old giv occurs;
4476 else add new move insn "giv_reg = reduced_reg". */
4477 loop_givs_rescan (loop, bl, reg_map, end_insert_before);
4479 /* All the givs based on the biv bl have been reduced if they
4482 /* For each giv not marked as maybe dead that has been combined with a
4483 second giv, clear any "maybe dead" mark on that second giv.
4484 v->new_reg will either be or refer to the register of the giv it
4487 Doing this clearing avoids problems in biv elimination where
4488 a giv's new_reg is a complex value that can't be put in the
4489 insn but the giv combined with (with a reg as new_reg) is
4490 marked maybe_dead. Since the register will be used in either
4491 case, we'd prefer it be used from the simpler giv. */
4493 for (v = bl->giv; v; v = v->next_iv)
4494 if (! v->maybe_dead && v->same)
4495 v->same->maybe_dead = 0;
4497 /* Try to eliminate the biv, if it is a candidate.
4498 This won't work if ! bl->all_reduced,
4499 since the givs we planned to use might not have been reduced.
4501 We have to be careful that we didn't initially think we could
4502 eliminate this biv because of a giv that we now think may be
4503 dead and shouldn't be used as a biv replacement.
4505 Also, there is the possibility that we may have a giv that looks
4506 like it can be used to eliminate a biv, but the resulting insn
4507 isn't valid. This can happen, for example, on the 88k, where a
4508 JUMP_INSN can compare a register only with zero. Attempts to
4509 replace it with a compare with a constant will fail.
4511 Note that in cases where this call fails, we may have replaced some
4512 of the occurrences of the biv with a giv, but no harm was done in
4513 doing so in the rare cases where it can occur. */
4515 if (bl->all_reduced == 1 && bl->eliminable
4516 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4518 /* ?? If we created a new test to bypass the loop entirely,
4519 or otherwise drop straight in, based on this test, then
4520 we might want to rewrite it also. This way some later
4521 pass has more hope of removing the initialization of this
4524 /* If final_value != 0, then the biv may be used after loop end
4525 and we must emit an insn to set it just in case.
4527 Reversed bivs already have an insn after the loop setting their
4528 value, so we don't need another one. We can't calculate the
4529 proper final value for such a biv here anyways. */
4530 if (bl->final_value && ! bl->reversed)
4534 /* If the loop has multiple exits, emit the insn before the
4535 loop to ensure that it will always be executed no matter
4536 how the loop exits. Otherwise, emit the insn after the
4537 loop, since this is slightly more efficient. */
4538 if (loop->exit_count)
4539 insert_before = loop->start;
4541 insert_before = end_insert_before;
4543 emit_insn_before (gen_move_insn (bl->biv->dest_reg,
4548 if (loop_dump_stream)
4549 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4554 /* Go through all the instructions in the loop, making all the
4555 register substitutions scheduled in REG_MAP. */
4557 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
4558 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4559 || GET_CODE (p) == CALL_INSN)
4561 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4562 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4566 if (loop_info->n_iterations > 0)
4568 /* When we completely unroll a loop we will likely not need the increment
4569 of the loop BIV and we will not need the conditional branch at the
4571 unrolled_insn_copies = insn_count - 2;
4574 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4575 need the comparison before the conditional branch at the end of the
4577 unrolled_insn_copies -= 1;
4580 /* We'll need one copy for each loop iteration. */
4581 unrolled_insn_copies *= loop_info->n_iterations;
4583 /* A little slop to account for the ability to remove initialization
4584 code, better CSE, and other secondary benefits of completely
4585 unrolling some loops. */
4586 unrolled_insn_copies -= 1;
4588 /* Clamp the value. */
4589 if (unrolled_insn_copies < 0)
4590 unrolled_insn_copies = 0;
4593 /* Unroll loops from within strength reduction so that we can use the
4594 induction variable information that strength_reduce has already
4595 collected. Always unroll loops that would be as small or smaller
4596 unrolled than when rolled. */
4597 if ((flags & LOOP_UNROLL)
4598 || (loop_info->n_iterations > 0
4599 && unrolled_insn_copies <= insn_count))
4600 unroll_loop (loop, insn_count, end_insert_before, 1);
4602 #ifdef HAVE_doloop_end
4603 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4604 doloop_optimize (loop);
4605 #endif /* HAVE_doloop_end */
4607 if (loop_dump_stream)
4608 fprintf (loop_dump_stream, "\n");
4610 loop_ivs_free (loop);
4615 /*Record all basic induction variables calculated in the insn. */
4617 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4620 int not_every_iteration;
4623 struct loop_ivs *ivs = LOOP_IVS (loop);
4630 if (GET_CODE (p) == INSN
4631 && (set = single_set (p))
4632 && GET_CODE (SET_DEST (set)) == REG)
4634 dest_reg = SET_DEST (set);
4635 if (REGNO (dest_reg) < max_reg_before_loop
4636 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4637 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4639 if (basic_induction_var (loop, SET_SRC (set),
4640 GET_MODE (SET_SRC (set)),
4641 dest_reg, p, &inc_val, &mult_val,
4644 /* It is a possible basic induction variable.
4645 Create and initialize an induction structure for it. */
4648 = (struct induction *) xmalloc (sizeof (struct induction));
4650 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4651 not_every_iteration, maybe_multiple);
4652 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4654 else if (REGNO (dest_reg) < ivs->n_regs)
4655 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4661 /* Record all givs calculated in the insn.
4662 A register is a giv if: it is only set once, it is a function of a
4663 biv and a constant (or invariant), and it is not a biv. */
4665 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4668 int not_every_iteration;
4671 struct loop_regs *regs = LOOP_REGS (loop);
4674 /* Look for a general induction variable in a register. */
4675 if (GET_CODE (p) == INSN
4676 && (set = single_set (p))
4677 && GET_CODE (SET_DEST (set)) == REG
4678 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
4687 rtx last_consec_insn;
4689 dest_reg = SET_DEST (set);
4690 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4693 if (/* SET_SRC is a giv. */
4694 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4695 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4696 /* Equivalent expression is a giv. */
4697 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4698 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4699 &add_val, &mult_val, &ext_val, 0,
4700 &benefit, VOIDmode)))
4701 /* Don't try to handle any regs made by loop optimization.
4702 We have nothing on them in regno_first_uid, etc. */
4703 && REGNO (dest_reg) < max_reg_before_loop
4704 /* Don't recognize a BASIC_INDUCT_VAR here. */
4705 && dest_reg != src_reg
4706 /* This must be the only place where the register is set. */
4707 && (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) == 1
4708 /* or all sets must be consecutive and make a giv. */
4709 || (benefit = consec_sets_giv (loop, benefit, p,
4711 &add_val, &mult_val, &ext_val,
4712 &last_consec_insn))))
4715 = (struct induction *) xmalloc (sizeof (struct induction));
4717 /* If this is a library call, increase benefit. */
4718 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4719 benefit += libcall_benefit (p);
4721 /* Skip the consecutive insns, if there are any. */
4722 if (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) != 1)
4723 p = last_consec_insn;
4725 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4726 ext_val, benefit, DEST_REG, not_every_iteration,
4727 maybe_multiple, NULL_PTR);
4732 #ifndef DONT_REDUCE_ADDR
4733 /* Look for givs which are memory addresses. */
4734 /* This resulted in worse code on a VAX 8600. I wonder if it
4736 if (GET_CODE (p) == INSN)
4737 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4741 /* Update the status of whether giv can derive other givs. This can
4742 change when we pass a label or an insn that updates a biv. */
4743 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4744 || GET_CODE (p) == CODE_LABEL)
4745 update_giv_derive (loop, p);
4749 /* Return 1 if X is a valid source for an initial value (or as value being
4750 compared against in an initial test).
4752 X must be either a register or constant and must not be clobbered between
4753 the current insn and the start of the loop.
4755 INSN is the insn containing X. */
4758 valid_initial_value_p (x, insn, call_seen, loop_start)
4767 /* Only consider pseudos we know about initialized in insns whose luids
4769 if (GET_CODE (x) != REG
4770 || REGNO (x) >= max_reg_before_loop)
4773 /* Don't use call-clobbered registers across a call which clobbers it. On
4774 some machines, don't use any hard registers at all. */
4775 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4776 && (SMALL_REGISTER_CLASSES
4777 || (call_used_regs[REGNO (x)] && call_seen)))
4780 /* Don't use registers that have been clobbered before the start of the
4782 if (reg_set_between_p (x, insn, loop_start))
4788 /* Scan X for memory refs and check each memory address
4789 as a possible giv. INSN is the insn whose pattern X comes from.
4790 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4791 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4792 more thanonce in each loop iteration. */
4795 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4796 const struct loop *loop;
4799 int not_every_iteration, maybe_multiple;
4802 register enum rtx_code code;
4803 register const char *fmt;
4808 code = GET_CODE (x);
4833 /* This code used to disable creating GIVs with mult_val == 1 and
4834 add_val == 0. However, this leads to lost optimizations when
4835 it comes time to combine a set of related DEST_ADDR GIVs, since
4836 this one would not be seen. */
4838 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4839 &mult_val, &ext_val, 1, &benefit,
4842 /* Found one; record it. */
4844 = (struct induction *) xmalloc (sizeof (struct induction));
4846 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4847 add_val, ext_val, benefit, DEST_ADDR,
4848 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4850 v->mem_mode = GET_MODE (x);
4859 /* Recursively scan the subexpressions for other mem refs. */
4861 fmt = GET_RTX_FORMAT (code);
4862 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4864 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4866 else if (fmt[i] == 'E')
4867 for (j = 0; j < XVECLEN (x, i); j++)
4868 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4872 /* Fill in the data about one biv update.
4873 V is the `struct induction' in which we record the biv. (It is
4874 allocated by the caller, with alloca.)
4875 INSN is the insn that sets it.
4876 DEST_REG is the biv's reg.
4878 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4879 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4880 being set to INC_VAL.
4882 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4883 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4884 can be executed more than once per iteration. If MAYBE_MULTIPLE
4885 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4886 executed exactly once per iteration. */
4889 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4890 not_every_iteration, maybe_multiple)
4892 struct induction *v;
4898 int not_every_iteration;
4901 struct loop_ivs *ivs = LOOP_IVS (loop);
4902 struct iv_class *bl;
4905 v->src_reg = dest_reg;
4906 v->dest_reg = dest_reg;
4907 v->mult_val = mult_val;
4908 v->add_val = inc_val;
4909 v->ext_dependant = NULL_RTX;
4910 v->location = location;
4911 v->mode = GET_MODE (dest_reg);
4912 v->always_computable = ! not_every_iteration;
4913 v->always_executed = ! not_every_iteration;
4914 v->maybe_multiple = maybe_multiple;
4916 /* Add this to the reg's iv_class, creating a class
4917 if this is the first incrementation of the reg. */
4919 bl = REG_IV_CLASS (ivs, REGNO (dest_reg));
4922 /* Create and initialize new iv_class. */
4924 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4926 bl->regno = REGNO (dest_reg);
4932 /* Set initial value to the reg itself. */
4933 bl->initial_value = dest_reg;
4934 bl->final_value = 0;
4935 /* We haven't seen the initializing insn yet */
4938 bl->initial_test = 0;
4939 bl->incremented = 0;
4943 bl->total_benefit = 0;
4945 /* Add this class to ivs->list. */
4946 bl->next = ivs->list;
4949 /* Put it in the array of biv register classes. */
4950 REG_IV_CLASS (ivs, REGNO (dest_reg)) = bl;
4953 /* Update IV_CLASS entry for this biv. */
4954 v->next_iv = bl->biv;
4957 if (mult_val == const1_rtx)
4958 bl->incremented = 1;
4960 if (loop_dump_stream)
4962 fprintf (loop_dump_stream,
4963 "Insn %d: possible biv, reg %d,",
4964 INSN_UID (insn), REGNO (dest_reg));
4965 if (GET_CODE (inc_val) == CONST_INT)
4967 fprintf (loop_dump_stream, " const =");
4968 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4969 fputc ('\n', loop_dump_stream);
4973 fprintf (loop_dump_stream, " const = ");
4974 print_rtl (loop_dump_stream, inc_val);
4975 fprintf (loop_dump_stream, "\n");
4980 /* Fill in the data about one giv.
4981 V is the `struct induction' in which we record the giv. (It is
4982 allocated by the caller, with alloca.)
4983 INSN is the insn that sets it.
4984 BENEFIT estimates the savings from deleting this insn.
4985 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4986 into a register or is used as a memory address.
4988 SRC_REG is the biv reg which the giv is computed from.
4989 DEST_REG is the giv's reg (if the giv is stored in a reg).
4990 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4991 LOCATION points to the place where this giv's value appears in INSN. */
4994 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4995 benefit, type, not_every_iteration, maybe_multiple, location)
4996 const struct loop *loop;
4997 struct induction *v;
5001 rtx mult_val, add_val, ext_val;
5004 int not_every_iteration, maybe_multiple;
5007 struct loop_ivs *ivs = LOOP_IVS (loop);
5008 struct induction *b;
5009 struct iv_class *bl;
5010 rtx set = single_set (insn);
5013 /* Attempt to prove constantness of the values. */
5014 temp = simplify_rtx (add_val);
5019 v->src_reg = src_reg;
5021 v->dest_reg = dest_reg;
5022 v->mult_val = mult_val;
5023 v->add_val = add_val;
5024 v->ext_dependant = ext_val;
5025 v->benefit = benefit;
5026 v->location = location;
5028 v->combined_with = 0;
5029 v->maybe_multiple = maybe_multiple;
5031 v->derive_adjustment = 0;
5037 v->auto_inc_opt = 0;
5041 /* The v->always_computable field is used in update_giv_derive, to
5042 determine whether a giv can be used to derive another giv. For a
5043 DEST_REG giv, INSN computes a new value for the giv, so its value
5044 isn't computable if INSN insn't executed every iteration.
5045 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5046 it does not compute a new value. Hence the value is always computable
5047 regardless of whether INSN is executed each iteration. */
5049 if (type == DEST_ADDR)
5050 v->always_computable = 1;
5052 v->always_computable = ! not_every_iteration;
5054 v->always_executed = ! not_every_iteration;
5056 if (type == DEST_ADDR)
5058 v->mode = GET_MODE (*location);
5061 else /* type == DEST_REG */
5063 v->mode = GET_MODE (SET_DEST (set));
5065 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
5067 /* If the lifetime is zero, it means that this register is
5068 really a dead store. So mark this as a giv that can be
5069 ignored. This will not prevent the biv from being eliminated. */
5070 if (v->lifetime == 0)
5073 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
5074 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
5077 /* Add the giv to the class of givs computed from one biv. */
5079 bl = REG_IV_CLASS (ivs, REGNO (src_reg));
5082 v->next_iv = bl->giv;
5084 /* Don't count DEST_ADDR. This is supposed to count the number of
5085 insns that calculate givs. */
5086 if (type == DEST_REG)
5088 bl->total_benefit += benefit;
5091 /* Fatal error, biv missing for this giv? */
5094 if (type == DEST_ADDR)
5098 /* The giv can be replaced outright by the reduced register only if all
5099 of the following conditions are true:
5100 - the insn that sets the giv is always executed on any iteration
5101 on which the giv is used at all
5102 (there are two ways to deduce this:
5103 either the insn is executed on every iteration,
5104 or all uses follow that insn in the same basic block),
5105 - the giv is not used outside the loop
5106 - no assignments to the biv occur during the giv's lifetime. */
5108 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
5109 /* Previous line always fails if INSN was moved by loop opt. */
5110 && REGNO_LAST_LUID (REGNO (dest_reg))
5111 < INSN_LUID (loop->end)
5112 && (! not_every_iteration
5113 || last_use_this_basic_block (dest_reg, insn)))
5115 /* Now check that there are no assignments to the biv within the
5116 giv's lifetime. This requires two separate checks. */
5118 /* Check each biv update, and fail if any are between the first
5119 and last use of the giv.
5121 If this loop contains an inner loop that was unrolled, then
5122 the insn modifying the biv may have been emitted by the loop
5123 unrolling code, and hence does not have a valid luid. Just
5124 mark the biv as not replaceable in this case. It is not very
5125 useful as a biv, because it is used in two different loops.
5126 It is very unlikely that we would be able to optimize the giv
5127 using this biv anyways. */
5130 for (b = bl->biv; b; b = b->next_iv)
5132 if (INSN_UID (b->insn) >= max_uid_for_loop
5133 || ((INSN_LUID (b->insn)
5134 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5135 && (INSN_LUID (b->insn)
5136 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5139 v->not_replaceable = 1;
5144 /* If there are any backwards branches that go from after the
5145 biv update to before it, then this giv is not replaceable. */
5147 for (b = bl->biv; b; b = b->next_iv)
5148 if (back_branch_in_range_p (loop, b->insn))
5151 v->not_replaceable = 1;
5157 /* May still be replaceable, we don't have enough info here to
5160 v->not_replaceable = 0;
5164 /* Record whether the add_val contains a const_int, for later use by
5169 v->no_const_addval = 1;
5170 if (tem == const0_rtx)
5172 else if (CONSTANT_P (add_val))
5173 v->no_const_addval = 0;
5174 if (GET_CODE (tem) == PLUS)
5178 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5179 tem = XEXP (tem, 0);
5180 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5181 tem = XEXP (tem, 1);
5185 if (CONSTANT_P (XEXP (tem, 1)))
5186 v->no_const_addval = 0;
5190 if (loop_dump_stream)
5192 if (type == DEST_REG)
5193 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5194 INSN_UID (insn), REGNO (dest_reg));
5196 fprintf (loop_dump_stream, "Insn %d: dest address",
5199 fprintf (loop_dump_stream, " src reg %d benefit %d",
5200 REGNO (src_reg), v->benefit);
5201 fprintf (loop_dump_stream, " lifetime %d",
5205 fprintf (loop_dump_stream, " replaceable");
5207 if (v->no_const_addval)
5208 fprintf (loop_dump_stream, " ncav");
5210 if (v->ext_dependant)
5212 switch (GET_CODE (v->ext_dependant))
5215 fprintf (loop_dump_stream, " ext se");
5218 fprintf (loop_dump_stream, " ext ze");
5221 fprintf (loop_dump_stream, " ext tr");
5228 if (GET_CODE (mult_val) == CONST_INT)
5230 fprintf (loop_dump_stream, " mult ");
5231 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5235 fprintf (loop_dump_stream, " mult ");
5236 print_rtl (loop_dump_stream, mult_val);
5239 if (GET_CODE (add_val) == CONST_INT)
5241 fprintf (loop_dump_stream, " add ");
5242 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5246 fprintf (loop_dump_stream, " add ");
5247 print_rtl (loop_dump_stream, add_val);
5251 if (loop_dump_stream)
5252 fprintf (loop_dump_stream, "\n");
5256 /* All this does is determine whether a giv can be made replaceable because
5257 its final value can be calculated. This code can not be part of record_giv
5258 above, because final_giv_value requires that the number of loop iterations
5259 be known, and that can not be accurately calculated until after all givs
5260 have been identified. */
5263 check_final_value (loop, v)
5264 const struct loop *loop;
5265 struct induction *v;
5267 struct loop_ivs *ivs = LOOP_IVS (loop);
5268 struct iv_class *bl;
5269 rtx final_value = 0;
5271 bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
5273 /* DEST_ADDR givs will never reach here, because they are always marked
5274 replaceable above in record_giv. */
5276 /* The giv can be replaced outright by the reduced register only if all
5277 of the following conditions are true:
5278 - the insn that sets the giv is always executed on any iteration
5279 on which the giv is used at all
5280 (there are two ways to deduce this:
5281 either the insn is executed on every iteration,
5282 or all uses follow that insn in the same basic block),
5283 - its final value can be calculated (this condition is different
5284 than the one above in record_giv)
5285 - it's not used before the it's set
5286 - no assignments to the biv occur during the giv's lifetime. */
5289 /* This is only called now when replaceable is known to be false. */
5290 /* Clear replaceable, so that it won't confuse final_giv_value. */
5294 if ((final_value = final_giv_value (loop, v))
5295 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5297 int biv_increment_seen = 0, before_giv_insn = 0;
5303 /* When trying to determine whether or not a biv increment occurs
5304 during the lifetime of the giv, we can ignore uses of the variable
5305 outside the loop because final_value is true. Hence we can not
5306 use regno_last_uid and regno_first_uid as above in record_giv. */
5308 /* Search the loop to determine whether any assignments to the
5309 biv occur during the giv's lifetime. Start with the insn
5310 that sets the giv, and search around the loop until we come
5311 back to that insn again.
5313 Also fail if there is a jump within the giv's lifetime that jumps
5314 to somewhere outside the lifetime but still within the loop. This
5315 catches spaghetti code where the execution order is not linear, and
5316 hence the above test fails. Here we assume that the giv lifetime
5317 does not extend from one iteration of the loop to the next, so as
5318 to make the test easier. Since the lifetime isn't known yet,
5319 this requires two loops. See also record_giv above. */
5321 last_giv_use = v->insn;
5328 before_giv_insn = 1;
5329 p = NEXT_INSN (loop->start);
5334 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5335 || GET_CODE (p) == CALL_INSN)
5337 /* It is possible for the BIV increment to use the GIV if we
5338 have a cycle. Thus we must be sure to check each insn for
5339 both BIV and GIV uses, and we must check for BIV uses
5342 if (! biv_increment_seen
5343 && reg_set_p (v->src_reg, PATTERN (p)))
5344 biv_increment_seen = 1;
5346 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5348 if (biv_increment_seen || before_giv_insn)
5351 v->not_replaceable = 1;
5359 /* Now that the lifetime of the giv is known, check for branches
5360 from within the lifetime to outside the lifetime if it is still
5370 p = NEXT_INSN (loop->start);
5371 if (p == last_giv_use)
5374 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5375 && LABEL_NAME (JUMP_LABEL (p))
5376 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5377 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5378 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5379 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5382 v->not_replaceable = 1;
5384 if (loop_dump_stream)
5385 fprintf (loop_dump_stream,
5386 "Found branch outside giv lifetime.\n");
5393 /* If it is replaceable, then save the final value. */
5395 v->final_value = final_value;
5398 if (loop_dump_stream && v->replaceable)
5399 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5400 INSN_UID (v->insn), REGNO (v->dest_reg));
5403 /* Update the status of whether a giv can derive other givs.
5405 We need to do something special if there is or may be an update to the biv
5406 between the time the giv is defined and the time it is used to derive
5409 In addition, a giv that is only conditionally set is not allowed to
5410 derive another giv once a label has been passed.
5412 The cases we look at are when a label or an update to a biv is passed. */
5415 update_giv_derive (loop, p)
5416 const struct loop *loop;
5419 struct loop_ivs *ivs = LOOP_IVS (loop);
5420 struct iv_class *bl;
5421 struct induction *biv, *giv;
5425 /* Search all IV classes, then all bivs, and finally all givs.
5427 There are three cases we are concerned with. First we have the situation
5428 of a giv that is only updated conditionally. In that case, it may not
5429 derive any givs after a label is passed.
5431 The second case is when a biv update occurs, or may occur, after the
5432 definition of a giv. For certain biv updates (see below) that are
5433 known to occur between the giv definition and use, we can adjust the
5434 giv definition. For others, or when the biv update is conditional,
5435 we must prevent the giv from deriving any other givs. There are two
5436 sub-cases within this case.
5438 If this is a label, we are concerned with any biv update that is done
5439 conditionally, since it may be done after the giv is defined followed by
5440 a branch here (actually, we need to pass both a jump and a label, but
5441 this extra tracking doesn't seem worth it).
5443 If this is a jump, we are concerned about any biv update that may be
5444 executed multiple times. We are actually only concerned about
5445 backward jumps, but it is probably not worth performing the test
5446 on the jump again here.
5448 If this is a biv update, we must adjust the giv status to show that a
5449 subsequent biv update was performed. If this adjustment cannot be done,
5450 the giv cannot derive further givs. */
5452 for (bl = ivs->list; bl; bl = bl->next)
5453 for (biv = bl->biv; biv; biv = biv->next_iv)
5454 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5457 for (giv = bl->giv; giv; giv = giv->next_iv)
5459 /* If cant_derive is already true, there is no point in
5460 checking all of these conditions again. */
5461 if (giv->cant_derive)
5464 /* If this giv is conditionally set and we have passed a label,
5465 it cannot derive anything. */
5466 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5467 giv->cant_derive = 1;
5469 /* Skip givs that have mult_val == 0, since
5470 they are really invariants. Also skip those that are
5471 replaceable, since we know their lifetime doesn't contain
5473 else if (giv->mult_val == const0_rtx || giv->replaceable)
5476 /* The only way we can allow this giv to derive another
5477 is if this is a biv increment and we can form the product
5478 of biv->add_val and giv->mult_val. In this case, we will
5479 be able to compute a compensation. */
5480 else if (biv->insn == p)
5485 if (biv->mult_val == const1_rtx)
5486 tem = simplify_giv_expr (loop,
5487 gen_rtx_MULT (giv->mode,
5490 &ext_val_dummy, &dummy);
5492 if (tem && giv->derive_adjustment)
5493 tem = simplify_giv_expr
5495 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5496 &ext_val_dummy, &dummy);
5499 giv->derive_adjustment = tem;
5501 giv->cant_derive = 1;
5503 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5504 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5505 giv->cant_derive = 1;
5510 /* Check whether an insn is an increment legitimate for a basic induction var.
5511 X is the source of insn P, or a part of it.
5512 MODE is the mode in which X should be interpreted.
5514 DEST_REG is the putative biv, also the destination of the insn.
5515 We accept patterns of these forms:
5516 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5517 REG = INVARIANT + REG
5519 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5520 store the additive term into *INC_VAL, and store the place where
5521 we found the additive term into *LOCATION.
5523 If X is an assignment of an invariant into DEST_REG, we set
5524 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5526 We also want to detect a BIV when it corresponds to a variable
5527 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5528 of the variable may be a PLUS that adds a SUBREG of that variable to
5529 an invariant and then sign- or zero-extends the result of the PLUS
5532 Most GIVs in such cases will be in the promoted mode, since that is the
5533 probably the natural computation mode (and almost certainly the mode
5534 used for addresses) on the machine. So we view the pseudo-reg containing
5535 the variable as the BIV, as if it were simply incremented.
5537 Note that treating the entire pseudo as a BIV will result in making
5538 simple increments to any GIVs based on it. However, if the variable
5539 overflows in its declared mode but not its promoted mode, the result will
5540 be incorrect. This is acceptable if the variable is signed, since
5541 overflows in such cases are undefined, but not if it is unsigned, since
5542 those overflows are defined. So we only check for SIGN_EXTEND and
5545 If we cannot find a biv, we return 0. */
5548 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5549 const struct loop *loop;
5551 enum machine_mode mode;
5558 register enum rtx_code code;
5562 code = GET_CODE (x);
5567 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5568 || (GET_CODE (XEXP (x, 0)) == SUBREG
5569 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5570 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5572 argp = &XEXP (x, 1);
5574 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5575 || (GET_CODE (XEXP (x, 1)) == SUBREG
5576 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5577 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5579 argp = &XEXP (x, 0);
5585 if (loop_invariant_p (loop, arg) != 1)
5588 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5589 *mult_val = const1_rtx;
5594 /* If this is a SUBREG for a promoted variable, check the inner
5596 if (SUBREG_PROMOTED_VAR_P (x))
5597 return basic_induction_var (loop, SUBREG_REG (x),
5598 GET_MODE (SUBREG_REG (x)),
5599 dest_reg, p, inc_val, mult_val, location);
5603 /* If this register is assigned in a previous insn, look at its
5604 source, but don't go outside the loop or past a label. */
5606 /* If this sets a register to itself, we would repeat any previous
5607 biv increment if we applied this strategy blindly. */
5608 if (rtx_equal_p (dest_reg, x))
5617 insn = PREV_INSN (insn);
5619 while (insn && GET_CODE (insn) == NOTE
5620 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5624 set = single_set (insn);
5627 dest = SET_DEST (set);
5629 || (GET_CODE (dest) == SUBREG
5630 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5631 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5632 && SUBREG_REG (dest) == x))
5633 return basic_induction_var (loop, SET_SRC (set),
5634 (GET_MODE (SET_SRC (set)) == VOIDmode
5636 : GET_MODE (SET_SRC (set))),
5638 inc_val, mult_val, location);
5640 while (GET_CODE (dest) == SIGN_EXTRACT
5641 || GET_CODE (dest) == ZERO_EXTRACT
5642 || GET_CODE (dest) == SUBREG
5643 || GET_CODE (dest) == STRICT_LOW_PART)
5644 dest = XEXP (dest, 0);
5650 /* Can accept constant setting of biv only when inside inner most loop.
5651 Otherwise, a biv of an inner loop may be incorrectly recognized
5652 as a biv of the outer loop,
5653 causing code to be moved INTO the inner loop. */
5655 if (loop_invariant_p (loop, x) != 1)
5660 /* convert_modes aborts if we try to convert to or from CCmode, so just
5661 exclude that case. It is very unlikely that a condition code value
5662 would be a useful iterator anyways. */
5663 if (loop->level == 1
5664 && GET_MODE_CLASS (mode) != MODE_CC
5665 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5667 /* Possible bug here? Perhaps we don't know the mode of X. */
5668 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5669 *mult_val = const0_rtx;
5676 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5677 dest_reg, p, inc_val, mult_val, location);
5680 /* Similar, since this can be a sign extension. */
5681 for (insn = PREV_INSN (p);
5682 (insn && GET_CODE (insn) == NOTE
5683 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5684 insn = PREV_INSN (insn))
5688 set = single_set (insn);
5690 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5691 && set && SET_DEST (set) == XEXP (x, 0)
5692 && GET_CODE (XEXP (x, 1)) == CONST_INT
5693 && INTVAL (XEXP (x, 1)) >= 0
5694 && GET_CODE (SET_SRC (set)) == ASHIFT
5695 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5696 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5697 GET_MODE (XEXP (x, 0)),
5698 dest_reg, insn, inc_val, mult_val,
5707 /* A general induction variable (giv) is any quantity that is a linear
5708 function of a basic induction variable,
5709 i.e. giv = biv * mult_val + add_val.
5710 The coefficients can be any loop invariant quantity.
5711 A giv need not be computed directly from the biv;
5712 it can be computed by way of other givs. */
5714 /* Determine whether X computes a giv.
5715 If it does, return a nonzero value
5716 which is the benefit from eliminating the computation of X;
5717 set *SRC_REG to the register of the biv that it is computed from;
5718 set *ADD_VAL and *MULT_VAL to the coefficients,
5719 such that the value of X is biv * mult + add; */
5722 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5723 is_addr, pbenefit, addr_mode)
5724 const struct loop *loop;
5732 enum machine_mode addr_mode;
5734 struct loop_ivs *ivs = LOOP_IVS (loop);
5737 /* If this is an invariant, forget it, it isn't a giv. */
5738 if (loop_invariant_p (loop, x) == 1)
5742 *ext_val = NULL_RTX;
5743 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5747 switch (GET_CODE (x))
5751 /* Since this is now an invariant and wasn't before, it must be a giv
5752 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5754 *src_reg = ivs->list->biv->dest_reg;
5755 *mult_val = const0_rtx;
5760 /* This is equivalent to a BIV. */
5762 *mult_val = const1_rtx;
5763 *add_val = const0_rtx;
5767 /* Either (plus (biv) (invar)) or
5768 (plus (mult (biv) (invar_1)) (invar_2)). */
5769 if (GET_CODE (XEXP (x, 0)) == MULT)
5771 *src_reg = XEXP (XEXP (x, 0), 0);
5772 *mult_val = XEXP (XEXP (x, 0), 1);
5776 *src_reg = XEXP (x, 0);
5777 *mult_val = const1_rtx;
5779 *add_val = XEXP (x, 1);
5783 /* ADD_VAL is zero. */
5784 *src_reg = XEXP (x, 0);
5785 *mult_val = XEXP (x, 1);
5786 *add_val = const0_rtx;
5793 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5794 unless they are CONST_INT). */
5795 if (GET_CODE (*add_val) == USE)
5796 *add_val = XEXP (*add_val, 0);
5797 if (GET_CODE (*mult_val) == USE)
5798 *mult_val = XEXP (*mult_val, 0);
5801 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5803 *pbenefit += rtx_cost (orig_x, SET);
5805 /* Always return true if this is a giv so it will be detected as such,
5806 even if the benefit is zero or negative. This allows elimination
5807 of bivs that might otherwise not be eliminated. */
5811 /* Given an expression, X, try to form it as a linear function of a biv.
5812 We will canonicalize it to be of the form
5813 (plus (mult (BIV) (invar_1))
5815 with possible degeneracies.
5817 The invariant expressions must each be of a form that can be used as a
5818 machine operand. We surround then with a USE rtx (a hack, but localized
5819 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5820 routine; it is the caller's responsibility to strip them.
5822 If no such canonicalization is possible (i.e., two biv's are used or an
5823 expression that is neither invariant nor a biv or giv), this routine
5826 For a non-zero return, the result will have a code of CONST_INT, USE,
5827 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5829 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5831 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5832 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5835 simplify_giv_expr (loop, x, ext_val, benefit)
5836 const struct loop *loop;
5841 struct loop_ivs *ivs = LOOP_IVS (loop);
5842 struct loop_regs *regs = LOOP_REGS (loop);
5843 enum machine_mode mode = GET_MODE (x);
5847 /* If this is not an integer mode, or if we cannot do arithmetic in this
5848 mode, this can't be a giv. */
5849 if (mode != VOIDmode
5850 && (GET_MODE_CLASS (mode) != MODE_INT
5851 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5854 switch (GET_CODE (x))
5857 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5858 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5859 if (arg0 == 0 || arg1 == 0)
5862 /* Put constant last, CONST_INT last if both constant. */
5863 if ((GET_CODE (arg0) == USE
5864 || GET_CODE (arg0) == CONST_INT)
5865 && ! ((GET_CODE (arg0) == USE
5866 && GET_CODE (arg1) == USE)
5867 || GET_CODE (arg1) == CONST_INT))
5868 tem = arg0, arg0 = arg1, arg1 = tem;
5870 /* Handle addition of zero, then addition of an invariant. */
5871 if (arg1 == const0_rtx)
5873 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5874 switch (GET_CODE (arg0))
5878 /* Adding two invariants must result in an invariant, so enclose
5879 addition operation inside a USE and return it. */
5880 if (GET_CODE (arg0) == USE)
5881 arg0 = XEXP (arg0, 0);
5882 if (GET_CODE (arg1) == USE)
5883 arg1 = XEXP (arg1, 0);
5885 if (GET_CODE (arg0) == CONST_INT)
5886 tem = arg0, arg0 = arg1, arg1 = tem;
5887 if (GET_CODE (arg1) == CONST_INT)
5888 tem = sge_plus_constant (arg0, arg1);
5890 tem = sge_plus (mode, arg0, arg1);
5892 if (GET_CODE (tem) != CONST_INT)
5893 tem = gen_rtx_USE (mode, tem);
5898 /* biv + invar or mult + invar. Return sum. */
5899 return gen_rtx_PLUS (mode, arg0, arg1);
5902 /* (a + invar_1) + invar_2. Associate. */
5904 simplify_giv_expr (loop,
5916 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5917 MULT to reduce cases. */
5918 if (GET_CODE (arg0) == REG)
5919 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5920 if (GET_CODE (arg1) == REG)
5921 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5923 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5924 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5925 Recurse to associate the second PLUS. */
5926 if (GET_CODE (arg1) == MULT)
5927 tem = arg0, arg0 = arg1, arg1 = tem;
5929 if (GET_CODE (arg1) == PLUS)
5931 simplify_giv_expr (loop,
5933 gen_rtx_PLUS (mode, arg0,
5938 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5939 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5942 if (!rtx_equal_p (arg0, arg1))
5945 return simplify_giv_expr (loop,
5954 /* Handle "a - b" as "a + b * (-1)". */
5955 return simplify_giv_expr (loop,
5964 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5965 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5966 if (arg0 == 0 || arg1 == 0)
5969 /* Put constant last, CONST_INT last if both constant. */
5970 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5971 && GET_CODE (arg1) != CONST_INT)
5972 tem = arg0, arg0 = arg1, arg1 = tem;
5974 /* If second argument is not now constant, not giv. */
5975 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5978 /* Handle multiply by 0 or 1. */
5979 if (arg1 == const0_rtx)
5982 else if (arg1 == const1_rtx)
5985 switch (GET_CODE (arg0))
5988 /* biv * invar. Done. */
5989 return gen_rtx_MULT (mode, arg0, arg1);
5992 /* Product of two constants. */
5993 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5996 /* invar * invar is a giv, but attempt to simplify it somehow. */
5997 if (GET_CODE (arg1) != CONST_INT)
6000 arg0 = XEXP (arg0, 0);
6001 if (GET_CODE (arg0) == MULT)
6003 /* (invar_0 * invar_1) * invar_2. Associate. */
6004 return simplify_giv_expr (loop,
6013 /* Porpagate the MULT expressions to the intermost nodes. */
6014 else if (GET_CODE (arg0) == PLUS)
6016 /* (invar_0 + invar_1) * invar_2. Distribute. */
6017 return simplify_giv_expr (loop,
6029 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
6032 /* (a * invar_1) * invar_2. Associate. */
6033 return simplify_giv_expr (loop,
6042 /* (a + invar_1) * invar_2. Distribute. */
6043 return simplify_giv_expr (loop,
6058 /* Shift by constant is multiply by power of two. */
6059 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
6063 simplify_giv_expr (loop,
6066 GEN_INT ((HOST_WIDE_INT) 1
6067 << INTVAL (XEXP (x, 1)))),
6071 /* "-a" is "a * (-1)" */
6072 return simplify_giv_expr (loop,
6073 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
6077 /* "~a" is "-a - 1". Silly, but easy. */
6078 return simplify_giv_expr (loop,
6079 gen_rtx_MINUS (mode,
6080 gen_rtx_NEG (mode, XEXP (x, 0)),
6085 /* Already in proper form for invariant. */
6091 /* Conditionally recognize extensions of simple IVs. After we've
6092 computed loop traversal counts and verified the range of the
6093 source IV, we'll reevaluate this as a GIV. */
6094 if (*ext_val == NULL_RTX)
6096 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
6097 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
6099 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
6106 /* If this is a new register, we can't deal with it. */
6107 if (REGNO (x) >= max_reg_before_loop)
6110 /* Check for biv or giv. */
6111 switch (REG_IV_TYPE (ivs, REGNO (x)))
6115 case GENERAL_INDUCT:
6117 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
6119 /* Form expression from giv and add benefit. Ensure this giv
6120 can derive another and subtract any needed adjustment if so. */
6122 /* Increasing the benefit here is risky. The only case in which it
6123 is arguably correct is if this is the only use of V. In other
6124 cases, this will artificially inflate the benefit of the current
6125 giv, and lead to suboptimal code. Thus, it is disabled, since
6126 potentially not reducing an only marginally beneficial giv is
6127 less harmful than reducing many givs that are not really
6130 rtx single_use = VARRAY_RTX (regs->single_usage, REGNO (x));
6131 if (single_use && single_use != const0_rtx)
6132 *benefit += v->benefit;
6138 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
6139 v->src_reg, v->mult_val),
6142 if (v->derive_adjustment)
6143 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
6144 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
6147 if (!v->ext_dependant)
6152 *ext_val = v->ext_dependant;
6160 /* If it isn't an induction variable, and it is invariant, we
6161 may be able to simplify things further by looking through
6162 the bits we just moved outside the loop. */
6163 if (loop_invariant_p (loop, x) == 1)
6166 struct loop_movables *movables = LOOP_MOVABLES (loop);
6168 for (m = movables->head; m; m = m->next)
6169 if (rtx_equal_p (x, m->set_dest))
6171 /* Ok, we found a match. Substitute and simplify. */
6173 /* If we match another movable, we must use that, as
6174 this one is going away. */
6176 return simplify_giv_expr (loop, m->match->set_dest,
6179 /* If consec is non-zero, this is a member of a group of
6180 instructions that were moved together. We handle this
6181 case only to the point of seeking to the last insn and
6182 looking for a REG_EQUAL. Fail if we don't find one. */
6189 tem = NEXT_INSN (tem);
6193 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6195 tem = XEXP (tem, 0);
6199 tem = single_set (m->insn);
6201 tem = SET_SRC (tem);
6206 /* What we are most interested in is pointer
6207 arithmetic on invariants -- only take
6208 patterns we may be able to do something with. */
6209 if (GET_CODE (tem) == PLUS
6210 || GET_CODE (tem) == MULT
6211 || GET_CODE (tem) == ASHIFT
6212 || GET_CODE (tem) == CONST_INT
6213 || GET_CODE (tem) == SYMBOL_REF)
6215 tem = simplify_giv_expr (loop, tem, ext_val,
6220 else if (GET_CODE (tem) == CONST
6221 && GET_CODE (XEXP (tem, 0)) == PLUS
6222 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6223 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6225 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6237 /* Fall through to general case. */
6239 /* If invariant, return as USE (unless CONST_INT).
6240 Otherwise, not giv. */
6241 if (GET_CODE (x) == USE)
6244 if (loop_invariant_p (loop, x) == 1)
6246 if (GET_CODE (x) == CONST_INT)
6248 if (GET_CODE (x) == CONST
6249 && GET_CODE (XEXP (x, 0)) == PLUS
6250 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6251 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6253 return gen_rtx_USE (mode, x);
6260 /* This routine folds invariants such that there is only ever one
6261 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6264 sge_plus_constant (x, c)
6267 if (GET_CODE (x) == CONST_INT)
6268 return GEN_INT (INTVAL (x) + INTVAL (c));
6269 else if (GET_CODE (x) != PLUS)
6270 return gen_rtx_PLUS (GET_MODE (x), x, c);
6271 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6273 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6274 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6276 else if (GET_CODE (XEXP (x, 0)) == PLUS
6277 || GET_CODE (XEXP (x, 1)) != PLUS)
6279 return gen_rtx_PLUS (GET_MODE (x),
6280 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6284 return gen_rtx_PLUS (GET_MODE (x),
6285 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6290 sge_plus (mode, x, y)
6291 enum machine_mode mode;
6294 while (GET_CODE (y) == PLUS)
6296 rtx a = XEXP (y, 0);
6297 if (GET_CODE (a) == CONST_INT)
6298 x = sge_plus_constant (x, a);
6300 x = gen_rtx_PLUS (mode, x, a);
6303 if (GET_CODE (y) == CONST_INT)
6304 x = sge_plus_constant (x, y);
6306 x = gen_rtx_PLUS (mode, x, y);
6310 /* Help detect a giv that is calculated by several consecutive insns;
6314 The caller has already identified the first insn P as having a giv as dest;
6315 we check that all other insns that set the same register follow
6316 immediately after P, that they alter nothing else,
6317 and that the result of the last is still a giv.
6319 The value is 0 if the reg set in P is not really a giv.
6320 Otherwise, the value is the amount gained by eliminating
6321 all the consecutive insns that compute the value.
6323 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6324 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6326 The coefficients of the ultimate giv value are stored in
6327 *MULT_VAL and *ADD_VAL. */
6330 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6331 add_val, mult_val, ext_val, last_consec_insn)
6332 const struct loop *loop;
6340 rtx *last_consec_insn;
6342 struct loop_ivs *ivs = LOOP_IVS (loop);
6343 struct loop_regs *regs = LOOP_REGS (loop);
6350 /* Indicate that this is a giv so that we can update the value produced in
6351 each insn of the multi-insn sequence.
6353 This induction structure will be used only by the call to
6354 general_induction_var below, so we can allocate it on our stack.
6355 If this is a giv, our caller will replace the induct var entry with
6356 a new induction structure. */
6357 struct induction *v;
6359 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6362 v = (struct induction *) alloca (sizeof (struct induction));
6363 v->src_reg = src_reg;
6364 v->mult_val = *mult_val;
6365 v->add_val = *add_val;
6366 v->benefit = first_benefit;
6368 v->derive_adjustment = 0;
6369 v->ext_dependant = NULL_RTX;
6371 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6372 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6374 count = VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) - 1;
6379 code = GET_CODE (p);
6381 /* If libcall, skip to end of call sequence. */
6382 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6386 && (set = single_set (p))
6387 && GET_CODE (SET_DEST (set)) == REG
6388 && SET_DEST (set) == dest_reg
6389 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6390 add_val, mult_val, ext_val, 0,
6392 /* Giv created by equivalent expression. */
6393 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6394 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6395 add_val, mult_val, ext_val, 0,
6396 &benefit, VOIDmode)))
6397 && src_reg == v->src_reg)
6399 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6400 benefit += libcall_benefit (p);
6403 v->mult_val = *mult_val;
6404 v->add_val = *add_val;
6405 v->benefit += benefit;
6407 else if (code != NOTE)
6409 /* Allow insns that set something other than this giv to a
6410 constant. Such insns are needed on machines which cannot
6411 include long constants and should not disqualify a giv. */
6413 && (set = single_set (p))
6414 && SET_DEST (set) != dest_reg
6415 && CONSTANT_P (SET_SRC (set)))
6418 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6423 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6424 *last_consec_insn = p;
6428 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6429 represented by G1. If no such expression can be found, or it is clear that
6430 it cannot possibly be a valid address, 0 is returned.
6432 To perform the computation, we note that
6435 where `v' is the biv.
6437 So G2 = (y/b) * G1 + (b - a*y/x).
6439 Note that MULT = y/x.
6441 Update: A and B are now allowed to be additive expressions such that
6442 B contains all variables in A. That is, computing B-A will not require
6443 subtracting variables. */
6446 express_from_1 (a, b, mult)
6449 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6451 if (mult == const0_rtx)
6454 /* If MULT is not 1, we cannot handle A with non-constants, since we
6455 would then be required to subtract multiples of the registers in A.
6456 This is theoretically possible, and may even apply to some Fortran
6457 constructs, but it is a lot of work and we do not attempt it here. */
6459 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6462 /* In general these structures are sorted top to bottom (down the PLUS
6463 chain), but not left to right across the PLUS. If B is a higher
6464 order giv than A, we can strip one level and recurse. If A is higher
6465 order, we'll eventually bail out, but won't know that until the end.
6466 If they are the same, we'll strip one level around this loop. */
6468 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6470 rtx ra, rb, oa, ob, tmp;
6472 ra = XEXP (a, 0), oa = XEXP (a, 1);
6473 if (GET_CODE (ra) == PLUS)
6474 tmp = ra, ra = oa, oa = tmp;
6476 rb = XEXP (b, 0), ob = XEXP (b, 1);
6477 if (GET_CODE (rb) == PLUS)
6478 tmp = rb, rb = ob, ob = tmp;
6480 if (rtx_equal_p (ra, rb))
6481 /* We matched: remove one reg completely. */
6483 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6484 /* An alternate match. */
6486 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6487 /* An alternate match. */
6491 /* Indicates an extra register in B. Strip one level from B and
6492 recurse, hoping B was the higher order expression. */
6493 ob = express_from_1 (a, ob, mult);
6496 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6500 /* Here we are at the last level of A, go through the cases hoping to
6501 get rid of everything but a constant. */
6503 if (GET_CODE (a) == PLUS)
6507 ra = XEXP (a, 0), oa = XEXP (a, 1);
6508 if (rtx_equal_p (oa, b))
6510 else if (!rtx_equal_p (ra, b))
6513 if (GET_CODE (oa) != CONST_INT)
6516 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6518 else if (GET_CODE (a) == CONST_INT)
6520 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6522 else if (CONSTANT_P (a))
6524 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6526 else if (GET_CODE (b) == PLUS)
6528 if (rtx_equal_p (a, XEXP (b, 0)))
6530 else if (rtx_equal_p (a, XEXP (b, 1)))
6535 else if (rtx_equal_p (a, b))
6542 express_from (g1, g2)
6543 struct induction *g1, *g2;
6547 /* The value that G1 will be multiplied by must be a constant integer. Also,
6548 the only chance we have of getting a valid address is if b*c/a (see above
6549 for notation) is also an integer. */
6550 if (GET_CODE (g1->mult_val) == CONST_INT
6551 && GET_CODE (g2->mult_val) == CONST_INT)
6553 if (g1->mult_val == const0_rtx
6554 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6556 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6558 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6562 /* ??? Find out if the one is a multiple of the other? */
6566 add = express_from_1 (g1->add_val, g2->add_val, mult);
6567 if (add == NULL_RTX)
6569 /* Failed. If we've got a multiplication factor between G1 and G2,
6570 scale G1's addend and try again. */
6571 if (INTVAL (mult) > 1)
6573 rtx g1_add_val = g1->add_val;
6574 if (GET_CODE (g1_add_val) == MULT
6575 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6578 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6579 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6580 XEXP (g1_add_val, 0), GEN_INT (m));
6584 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6588 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6591 if (add == NULL_RTX)
6594 /* Form simplified final result. */
6595 if (mult == const0_rtx)
6597 else if (mult == const1_rtx)
6598 mult = g1->dest_reg;
6600 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6602 if (add == const0_rtx)
6606 if (GET_CODE (add) == PLUS
6607 && CONSTANT_P (XEXP (add, 1)))
6609 rtx tem = XEXP (add, 1);
6610 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6614 return gen_rtx_PLUS (g2->mode, mult, add);
6618 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6619 represented by G1. This indicates that G2 should be combined with G1 and
6620 that G2 can use (either directly or via an address expression) a register
6621 used to represent G1. */
6624 combine_givs_p (g1, g2)
6625 struct induction *g1, *g2;
6629 /* With the introduction of ext dependant givs, we must care for modes.
6630 G2 must not use a wider mode than G1. */
6631 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6634 ret = comb = express_from (g1, g2);
6635 if (comb == NULL_RTX)
6637 if (g1->mode != g2->mode)
6638 ret = gen_lowpart (g2->mode, comb);
6640 /* If these givs are identical, they can be combined. We use the results
6641 of express_from because the addends are not in a canonical form, so
6642 rtx_equal_p is a weaker test. */
6643 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6644 combination to be the other way round. */
6645 if (comb == g1->dest_reg
6646 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6651 /* If G2 can be expressed as a function of G1 and that function is valid
6652 as an address and no more expensive than using a register for G2,
6653 the expression of G2 in terms of G1 can be used. */
6655 && g2->giv_type == DEST_ADDR
6656 && memory_address_p (g2->mem_mode, ret)
6657 /* ??? Looses, especially with -fforce-addr, where *g2->location
6658 will always be a register, and so anything more complicated
6662 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6664 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6675 /* Check each extension dependant giv in this class to see if its
6676 root biv is safe from wrapping in the interior mode, which would
6677 make the giv illegal. */
6680 check_ext_dependant_givs (bl, loop_info)
6681 struct iv_class *bl;
6682 struct loop_info *loop_info;
6684 int ze_ok = 0, se_ok = 0, info_ok = 0;
6685 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6686 HOST_WIDE_INT start_val;
6687 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6689 struct induction *v;
6691 /* Make sure the iteration data is available. We must have
6692 constants in order to be certain of no overflow. */
6693 /* ??? An unknown iteration count with an increment of +-1
6694 combined with friendly exit tests of against an invariant
6695 value is also ameanable to optimization. Not implemented. */
6696 if (loop_info->n_iterations > 0
6697 && bl->initial_value
6698 && GET_CODE (bl->initial_value) == CONST_INT
6699 && (incr = biv_total_increment (bl))
6700 && GET_CODE (incr) == CONST_INT
6701 /* Make sure the host can represent the arithmetic. */
6702 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6704 unsigned HOST_WIDE_INT abs_incr, total_incr;
6705 HOST_WIDE_INT s_end_val;
6709 start_val = INTVAL (bl->initial_value);
6710 u_start_val = start_val;
6712 neg_incr = 0, abs_incr = INTVAL (incr);
6713 if (INTVAL (incr) < 0)
6714 neg_incr = 1, abs_incr = -abs_incr;
6715 total_incr = abs_incr * loop_info->n_iterations;
6717 /* Check for host arithmatic overflow. */
6718 if (total_incr / loop_info->n_iterations == abs_incr)
6720 unsigned HOST_WIDE_INT u_max;
6721 HOST_WIDE_INT s_max;
6723 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6724 s_end_val = u_end_val;
6725 u_max = GET_MODE_MASK (biv_mode);
6728 /* Check zero extension of biv ok. */
6730 /* Check for host arithmatic overflow. */
6732 ? u_end_val < u_start_val
6733 : u_end_val > u_start_val)
6734 /* Check for target arithmetic overflow. */
6736 ? 1 /* taken care of with host overflow */
6737 : u_end_val <= u_max))
6742 /* Check sign extension of biv ok. */
6743 /* ??? While it is true that overflow with signed and pointer
6744 arithmetic is undefined, I fear too many programmers don't
6745 keep this fact in mind -- myself included on occasion.
6746 So leave alone with the signed overflow optimizations. */
6747 if (start_val >= -s_max - 1
6748 /* Check for host arithmatic overflow. */
6750 ? s_end_val < start_val
6751 : s_end_val > start_val)
6752 /* Check for target arithmetic overflow. */
6754 ? s_end_val >= -s_max - 1
6755 : s_end_val <= s_max))
6762 /* Invalidate givs that fail the tests. */
6763 for (v = bl->giv; v; v = v->next_iv)
6764 if (v->ext_dependant)
6766 enum rtx_code code = GET_CODE (v->ext_dependant);
6779 /* We don't know whether this value is being used as either
6780 signed or unsigned, so to safely truncate we must satisfy
6781 both. The initial check here verifies the BIV itself;
6782 once that is successful we may check its range wrt the
6786 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6787 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6789 /* We know from the above that both endpoints are nonnegative,
6790 and that there is no wrapping. Verify that both endpoints
6791 are within the (signed) range of the outer mode. */
6792 if (u_start_val <= max && u_end_val <= max)
6803 if (loop_dump_stream)
6805 fprintf (loop_dump_stream,
6806 "Verified ext dependant giv at %d of reg %d\n",
6807 INSN_UID (v->insn), bl->regno);
6812 if (loop_dump_stream)
6817 why = "biv iteration values overflowed";
6821 incr = biv_total_increment (bl);
6822 if (incr == const1_rtx)
6823 why = "biv iteration info incomplete; incr by 1";
6825 why = "biv iteration info incomplete";
6828 fprintf (loop_dump_stream,
6829 "Failed ext dependant giv at %d, %s\n",
6830 INSN_UID (v->insn), why);
6837 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6840 extend_value_for_giv (v, value)
6841 struct induction *v;
6844 rtx ext_dep = v->ext_dependant;
6849 /* Recall that check_ext_dependant_givs verified that the known bounds
6850 of a biv did not overflow or wrap with respect to the extension for
6851 the giv. Therefore, constants need no additional adjustment. */
6852 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6855 /* Otherwise, we must adjust the value to compensate for the
6856 differing modes of the biv and the giv. */
6857 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6860 struct combine_givs_stats
6867 cmp_combine_givs_stats (xp, yp)
6871 const struct combine_givs_stats * const x =
6872 (const struct combine_givs_stats *) xp;
6873 const struct combine_givs_stats * const y =
6874 (const struct combine_givs_stats *) yp;
6876 d = y->total_benefit - x->total_benefit;
6877 /* Stabilize the sort. */
6879 d = x->giv_number - y->giv_number;
6883 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6884 any other. If so, point SAME to the giv combined with and set NEW_REG to
6885 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6886 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6889 combine_givs (regs, bl)
6890 struct loop_regs *regs;
6891 struct iv_class *bl;
6893 /* Additional benefit to add for being combined multiple times. */
6894 const int extra_benefit = 3;
6896 struct induction *g1, *g2, **giv_array;
6897 int i, j, k, giv_count;
6898 struct combine_givs_stats *stats;
6901 /* Count givs, because bl->giv_count is incorrect here. */
6903 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6908 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6910 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6912 giv_array[i++] = g1;
6914 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6915 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6917 for (i = 0; i < giv_count; i++)
6923 stats[i].giv_number = i;
6925 /* If a DEST_REG GIV is used only once, do not allow it to combine
6926 with anything, for in doing so we will gain nothing that cannot
6927 be had by simply letting the GIV with which we would have combined
6928 to be reduced on its own. The losage shows up in particular with
6929 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6930 be seen elsewhere as well. */
6931 if (g1->giv_type == DEST_REG
6932 && (single_use = VARRAY_RTX (regs->single_usage,
6933 REGNO (g1->dest_reg)))
6934 && single_use != const0_rtx)
6937 this_benefit = g1->benefit;
6938 /* Add an additional weight for zero addends. */
6939 if (g1->no_const_addval)
6942 for (j = 0; j < giv_count; j++)
6948 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6950 can_combine[i * giv_count + j] = this_combine;
6951 this_benefit += g2->benefit + extra_benefit;
6954 stats[i].total_benefit = this_benefit;
6957 /* Iterate, combining until we can't. */
6959 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6961 if (loop_dump_stream)
6963 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6964 for (k = 0; k < giv_count; k++)
6966 g1 = giv_array[stats[k].giv_number];
6967 if (!g1->combined_with && !g1->same)
6968 fprintf (loop_dump_stream, " {%d, %d}",
6969 INSN_UID (giv_array[stats[k].giv_number]->insn),
6970 stats[k].total_benefit);
6972 putc ('\n', loop_dump_stream);
6975 for (k = 0; k < giv_count; k++)
6977 int g1_add_benefit = 0;
6979 i = stats[k].giv_number;
6982 /* If it has already been combined, skip. */
6983 if (g1->combined_with || g1->same)
6986 for (j = 0; j < giv_count; j++)
6989 if (g1 != g2 && can_combine[i * giv_count + j]
6990 /* If it has already been combined, skip. */
6991 && ! g2->same && ! g2->combined_with)
6995 g2->new_reg = can_combine[i * giv_count + j];
6997 g1->combined_with++;
6998 g1->lifetime += g2->lifetime;
7000 g1_add_benefit += g2->benefit;
7002 /* ??? The new final_[bg]iv_value code does a much better job
7003 of finding replaceable giv's, and hence this code may no
7004 longer be necessary. */
7005 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
7006 g1_add_benefit -= copy_cost;
7008 /* To help optimize the next set of combinations, remove
7009 this giv from the benefits of other potential mates. */
7010 for (l = 0; l < giv_count; ++l)
7012 int m = stats[l].giv_number;
7013 if (can_combine[m * giv_count + j])
7014 stats[l].total_benefit -= g2->benefit + extra_benefit;
7017 if (loop_dump_stream)
7018 fprintf (loop_dump_stream,
7019 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
7020 INSN_UID (g2->insn), INSN_UID (g1->insn),
7021 g1->benefit, g1_add_benefit, g1->lifetime);
7025 /* To help optimize the next set of combinations, remove
7026 this giv from the benefits of other potential mates. */
7027 if (g1->combined_with)
7029 for (j = 0; j < giv_count; ++j)
7031 int m = stats[j].giv_number;
7032 if (can_combine[m * giv_count + i])
7033 stats[j].total_benefit -= g1->benefit + extra_benefit;
7036 g1->benefit += g1_add_benefit;
7038 /* We've finished with this giv, and everything it touched.
7039 Restart the combination so that proper weights for the
7040 rest of the givs are properly taken into account. */
7041 /* ??? Ideally we would compact the arrays at this point, so
7042 as to not cover old ground. But sanely compacting
7043 can_combine is tricky. */
7053 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
7056 emit_iv_add_mult (b, m, a, reg, insert_before)
7057 rtx b; /* initial value of basic induction variable */
7058 rtx m; /* multiplicative constant */
7059 rtx a; /* additive constant */
7060 rtx reg; /* destination register */
7066 /* Prevent unexpected sharing of these rtx. */
7070 /* Increase the lifetime of any invariants moved further in code. */
7071 update_reg_last_use (a, insert_before);
7072 update_reg_last_use (b, insert_before);
7073 update_reg_last_use (m, insert_before);
7076 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
7078 emit_move_insn (reg, result);
7079 seq = gen_sequence ();
7082 emit_insn_before (seq, insert_before);
7084 /* It is entirely possible that the expansion created lots of new
7085 registers. Iterate over the sequence we just created and
7088 if (GET_CODE (seq) == SEQUENCE)
7091 for (i = 0; i < XVECLEN (seq, 0); ++i)
7093 rtx set = single_set (XVECEXP (seq, 0, i));
7094 if (set && GET_CODE (SET_DEST (set)) == REG)
7095 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
7098 else if (GET_CODE (seq) == SET
7099 && GET_CODE (SET_DEST (seq)) == REG)
7100 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
7103 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
7106 iv_add_mult_cost (b, m, a, reg)
7107 rtx b; /* initial value of basic induction variable */
7108 rtx m; /* multiplicative constant */
7109 rtx a; /* additive constant */
7110 rtx reg; /* destination register */
7116 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
7118 emit_move_insn (reg, result);
7119 last = get_last_insn ();
7122 rtx t = single_set (last);
7124 cost += rtx_cost (SET_SRC (t), SET);
7125 last = PREV_INSN (last);
7131 /* Test whether A * B can be computed without
7132 an actual multiply insn. Value is 1 if so. */
7135 product_cheap_p (a, b)
7143 /* If only one is constant, make it B. */
7144 if (GET_CODE (a) == CONST_INT)
7145 tmp = a, a = b, b = tmp;
7147 /* If first constant, both constant, so don't need multiply. */
7148 if (GET_CODE (a) == CONST_INT)
7151 /* If second not constant, neither is constant, so would need multiply. */
7152 if (GET_CODE (b) != CONST_INT)
7155 /* One operand is constant, so might not need multiply insn. Generate the
7156 code for the multiply and see if a call or multiply, or long sequence
7157 of insns is generated. */
7160 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
7161 tmp = gen_sequence ();
7164 if (GET_CODE (tmp) == SEQUENCE)
7166 if (XVEC (tmp, 0) == 0)
7168 else if (XVECLEN (tmp, 0) > 3)
7171 for (i = 0; i < XVECLEN (tmp, 0); i++)
7173 rtx insn = XVECEXP (tmp, 0, i);
7175 if (GET_CODE (insn) != INSN
7176 || (GET_CODE (PATTERN (insn)) == SET
7177 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
7178 || (GET_CODE (PATTERN (insn)) == PARALLEL
7179 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
7180 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7187 else if (GET_CODE (tmp) == SET
7188 && GET_CODE (SET_SRC (tmp)) == MULT)
7190 else if (GET_CODE (tmp) == PARALLEL
7191 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7192 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7198 /* Check to see if loop can be terminated by a "decrement and branch until
7199 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7200 Also try reversing an increment loop to a decrement loop
7201 to see if the optimization can be performed.
7202 Value is nonzero if optimization was performed. */
7204 /* This is useful even if the architecture doesn't have such an insn,
7205 because it might change a loops which increments from 0 to n to a loop
7206 which decrements from n to 0. A loop that decrements to zero is usually
7207 faster than one that increments from zero. */
7209 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7210 such as approx_final_value, biv_total_increment, loop_iterations, and
7211 final_[bg]iv_value. */
7214 check_dbra_loop (loop, insn_count)
7218 struct loop_info *loop_info = LOOP_INFO (loop);
7219 struct loop_regs *regs = LOOP_REGS (loop);
7220 struct loop_ivs *ivs = LOOP_IVS (loop);
7221 struct iv_class *bl;
7228 rtx before_comparison;
7232 int compare_and_branch;
7233 rtx loop_start = loop->start;
7234 rtx loop_end = loop->end;
7236 /* If last insn is a conditional branch, and the insn before tests a
7237 register value, try to optimize it. Otherwise, we can't do anything. */
7239 jump = PREV_INSN (loop_end);
7240 comparison = get_condition_for_loop (loop, jump);
7241 if (comparison == 0)
7243 if (!onlyjump_p (jump))
7246 /* Try to compute whether the compare/branch at the loop end is one or
7247 two instructions. */
7248 get_condition (jump, &first_compare);
7249 if (first_compare == jump)
7250 compare_and_branch = 1;
7251 else if (first_compare == prev_nonnote_insn (jump))
7252 compare_and_branch = 2;
7257 /* If more than one condition is present to control the loop, then
7258 do not proceed, as this function does not know how to rewrite
7259 loop tests with more than one condition.
7261 Look backwards from the first insn in the last comparison
7262 sequence and see if we've got another comparison sequence. */
7265 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7266 if (GET_CODE (jump1) == JUMP_INSN)
7270 /* Check all of the bivs to see if the compare uses one of them.
7271 Skip biv's set more than once because we can't guarantee that
7272 it will be zero on the last iteration. Also skip if the biv is
7273 used between its update and the test insn. */
7275 for (bl = ivs->list; bl; bl = bl->next)
7277 if (bl->biv_count == 1
7278 && ! bl->biv->maybe_multiple
7279 && bl->biv->dest_reg == XEXP (comparison, 0)
7280 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7288 /* Look for the case where the basic induction variable is always
7289 nonnegative, and equals zero on the last iteration.
7290 In this case, add a reg_note REG_NONNEG, which allows the
7291 m68k DBRA instruction to be used. */
7293 if (((GET_CODE (comparison) == GT
7294 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7295 && INTVAL (XEXP (comparison, 1)) == -1)
7296 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7297 && GET_CODE (bl->biv->add_val) == CONST_INT
7298 && INTVAL (bl->biv->add_val) < 0)
7300 /* Initial value must be greater than 0,
7301 init_val % -dec_value == 0 to ensure that it equals zero on
7302 the last iteration */
7304 if (GET_CODE (bl->initial_value) == CONST_INT
7305 && INTVAL (bl->initial_value) > 0
7306 && (INTVAL (bl->initial_value)
7307 % (-INTVAL (bl->biv->add_val))) == 0)
7309 /* register always nonnegative, add REG_NOTE to branch */
7310 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7312 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7319 /* If the decrement is 1 and the value was tested as >= 0 before
7320 the loop, then we can safely optimize. */
7321 for (p = loop_start; p; p = PREV_INSN (p))
7323 if (GET_CODE (p) == CODE_LABEL)
7325 if (GET_CODE (p) != JUMP_INSN)
7328 before_comparison = get_condition_for_loop (loop, p);
7329 if (before_comparison
7330 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7331 && GET_CODE (before_comparison) == LT
7332 && XEXP (before_comparison, 1) == const0_rtx
7333 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7334 && INTVAL (bl->biv->add_val) == -1)
7336 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7338 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7346 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7347 && INTVAL (bl->biv->add_val) > 0)
7349 /* Try to change inc to dec, so can apply above optimization. */
7351 all registers modified are induction variables or invariant,
7352 all memory references have non-overlapping addresses
7353 (obviously true if only one write)
7354 allow 2 insns for the compare/jump at the end of the loop. */
7355 /* Also, we must avoid any instructions which use both the reversed
7356 biv and another biv. Such instructions will fail if the loop is
7357 reversed. We meet this condition by requiring that either
7358 no_use_except_counting is true, or else that there is only
7360 int num_nonfixed_reads = 0;
7361 /* 1 if the iteration var is used only to count iterations. */
7362 int no_use_except_counting = 0;
7363 /* 1 if the loop has no memory store, or it has a single memory store
7364 which is reversible. */
7365 int reversible_mem_store = 1;
7367 if (bl->giv_count == 0 && ! loop->exit_count)
7369 rtx bivreg = regno_reg_rtx[bl->regno];
7371 /* If there are no givs for this biv, and the only exit is the
7372 fall through at the end of the loop, then
7373 see if perhaps there are no uses except to count. */
7374 no_use_except_counting = 1;
7375 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7378 rtx set = single_set (p);
7380 if (set && GET_CODE (SET_DEST (set)) == REG
7381 && REGNO (SET_DEST (set)) == bl->regno)
7382 /* An insn that sets the biv is okay. */
7384 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7385 || p == prev_nonnote_insn (loop_end))
7386 && reg_mentioned_p (bivreg, PATTERN (p)))
7388 /* If either of these insns uses the biv and sets a pseudo
7389 that has more than one usage, then the biv has uses
7390 other than counting since it's used to derive a value
7391 that is used more than one time. */
7392 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7394 if (regs->multiple_uses)
7396 no_use_except_counting = 0;
7400 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7402 no_use_except_counting = 0;
7408 if (no_use_except_counting)
7409 /* No need to worry about MEMs. */
7411 else if (loop_info->num_mem_sets <= 1)
7413 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7415 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7417 /* If the loop has a single store, and the destination address is
7418 invariant, then we can't reverse the loop, because this address
7419 might then have the wrong value at loop exit.
7420 This would work if the source was invariant also, however, in that
7421 case, the insn should have been moved out of the loop. */
7423 if (loop_info->num_mem_sets == 1)
7425 struct induction *v;
7427 reversible_mem_store
7428 = (! loop_info->unknown_address_altered
7429 && ! loop_info->unknown_constant_address_altered
7430 && ! loop_invariant_p (loop,
7431 XEXP (XEXP (loop_info->store_mems, 0),
7434 /* If the store depends on a register that is set after the
7435 store, it depends on the initial value, and is thus not
7437 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7439 if (v->giv_type == DEST_REG
7440 && reg_mentioned_p (v->dest_reg,
7441 PATTERN (loop_info->first_loop_store_insn))
7442 && loop_insn_first_p (loop_info->first_loop_store_insn,
7444 reversible_mem_store = 0;
7451 /* This code only acts for innermost loops. Also it simplifies
7452 the memory address check by only reversing loops with
7453 zero or one memory access.
7454 Two memory accesses could involve parts of the same array,
7455 and that can't be reversed.
7456 If the biv is used only for counting, than we don't need to worry
7457 about all these things. */
7459 if ((num_nonfixed_reads <= 1
7460 && ! loop_info->has_call
7461 && ! loop_info->has_volatile
7462 && reversible_mem_store
7463 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7464 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7465 && (bl == ivs->list && bl->next == 0))
7466 || no_use_except_counting)
7470 /* Loop can be reversed. */
7471 if (loop_dump_stream)
7472 fprintf (loop_dump_stream, "Can reverse loop\n");
7474 /* Now check other conditions:
7476 The increment must be a constant, as must the initial value,
7477 and the comparison code must be LT.
7479 This test can probably be improved since +/- 1 in the constant
7480 can be obtained by changing LT to LE and vice versa; this is
7484 /* for constants, LE gets turned into LT */
7485 && (GET_CODE (comparison) == LT
7486 || (GET_CODE (comparison) == LE
7487 && no_use_except_counting)))
7489 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7490 rtx initial_value, comparison_value;
7492 enum rtx_code cmp_code;
7493 int comparison_const_width;
7494 unsigned HOST_WIDE_INT comparison_sign_mask;
7496 add_val = INTVAL (bl->biv->add_val);
7497 comparison_value = XEXP (comparison, 1);
7498 if (GET_MODE (comparison_value) == VOIDmode)
7499 comparison_const_width
7500 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7502 comparison_const_width
7503 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7504 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7505 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7506 comparison_sign_mask
7507 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7509 /* If the comparison value is not a loop invariant, then we
7510 can not reverse this loop.
7512 ??? If the insns which initialize the comparison value as
7513 a whole compute an invariant result, then we could move
7514 them out of the loop and proceed with loop reversal. */
7515 if (! loop_invariant_p (loop, comparison_value))
7518 if (GET_CODE (comparison_value) == CONST_INT)
7519 comparison_val = INTVAL (comparison_value);
7520 initial_value = bl->initial_value;
7522 /* Normalize the initial value if it is an integer and
7523 has no other use except as a counter. This will allow
7524 a few more loops to be reversed. */
7525 if (no_use_except_counting
7526 && GET_CODE (comparison_value) == CONST_INT
7527 && GET_CODE (initial_value) == CONST_INT)
7529 comparison_val = comparison_val - INTVAL (bl->initial_value);
7530 /* The code below requires comparison_val to be a multiple
7531 of add_val in order to do the loop reversal, so
7532 round up comparison_val to a multiple of add_val.
7533 Since comparison_value is constant, we know that the
7534 current comparison code is LT. */
7535 comparison_val = comparison_val + add_val - 1;
7537 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7538 /* We postpone overflow checks for COMPARISON_VAL here;
7539 even if there is an overflow, we might still be able to
7540 reverse the loop, if converting the loop exit test to
7542 initial_value = const0_rtx;
7545 /* First check if we can do a vanilla loop reversal. */
7546 if (initial_value == const0_rtx
7547 /* If we have a decrement_and_branch_on_count,
7548 prefer the NE test, since this will allow that
7549 instruction to be generated. Note that we must
7550 use a vanilla loop reversal if the biv is used to
7551 calculate a giv or has a non-counting use. */
7552 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7553 && defined (HAVE_decrement_and_branch_on_count)
7554 && (! (add_val == 1 && loop->vtop
7555 && (bl->biv_count == 0
7556 || no_use_except_counting)))
7558 && GET_CODE (comparison_value) == CONST_INT
7559 /* Now do postponed overflow checks on COMPARISON_VAL. */
7560 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7561 & comparison_sign_mask))
7563 /* Register will always be nonnegative, with value
7564 0 on last iteration */
7565 add_adjust = add_val;
7569 else if (add_val == 1 && loop->vtop
7570 && (bl->biv_count == 0
7571 || no_use_except_counting))
7579 if (GET_CODE (comparison) == LE)
7580 add_adjust -= add_val;
7582 /* If the initial value is not zero, or if the comparison
7583 value is not an exact multiple of the increment, then we
7584 can not reverse this loop. */
7585 if (initial_value == const0_rtx
7586 && GET_CODE (comparison_value) == CONST_INT)
7588 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7593 if (! no_use_except_counting || add_val != 1)
7597 final_value = comparison_value;
7599 /* Reset these in case we normalized the initial value
7600 and comparison value above. */
7601 if (GET_CODE (comparison_value) == CONST_INT
7602 && GET_CODE (initial_value) == CONST_INT)
7604 comparison_value = GEN_INT (comparison_val);
7606 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7608 bl->initial_value = initial_value;
7610 /* Save some info needed to produce the new insns. */
7611 reg = bl->biv->dest_reg;
7612 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7613 if (jump_label == pc_rtx)
7614 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7615 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7617 /* Set start_value; if this is not a CONST_INT, we need
7619 Initialize biv to start_value before loop start.
7620 The old initializing insn will be deleted as a
7621 dead store by flow.c. */
7622 if (initial_value == const0_rtx
7623 && GET_CODE (comparison_value) == CONST_INT)
7625 start_value = GEN_INT (comparison_val - add_adjust);
7626 emit_insn_before (gen_move_insn (reg, start_value),
7629 else if (GET_CODE (initial_value) == CONST_INT)
7631 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7632 enum machine_mode mode = GET_MODE (reg);
7633 enum insn_code icode
7634 = add_optab->handlers[(int) mode].insn_code;
7636 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7637 || ! ((*insn_data[icode].operand[1].predicate)
7638 (comparison_value, mode))
7639 || ! ((*insn_data[icode].operand[2].predicate)
7643 = gen_rtx_PLUS (mode, comparison_value, offset);
7644 emit_insn_before ((GEN_FCN (icode)
7645 (reg, comparison_value, offset)),
7647 if (GET_CODE (comparison) == LE)
7648 final_value = gen_rtx_PLUS (mode, comparison_value,
7651 else if (! add_adjust)
7653 enum machine_mode mode = GET_MODE (reg);
7654 enum insn_code icode
7655 = sub_optab->handlers[(int) mode].insn_code;
7656 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7657 || ! ((*insn_data[icode].operand[1].predicate)
7658 (comparison_value, mode))
7659 || ! ((*insn_data[icode].operand[2].predicate)
7660 (initial_value, mode)))
7663 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7664 emit_insn_before ((GEN_FCN (icode)
7665 (reg, comparison_value, initial_value)),
7669 /* We could handle the other cases too, but it'll be
7670 better to have a testcase first. */
7673 /* We may not have a single insn which can increment a reg, so
7674 create a sequence to hold all the insns from expand_inc. */
7676 expand_inc (reg, new_add_val);
7677 tem = gen_sequence ();
7680 p = emit_insn_before (tem, bl->biv->insn);
7681 delete_insn (bl->biv->insn);
7683 /* Update biv info to reflect its new status. */
7685 bl->initial_value = start_value;
7686 bl->biv->add_val = new_add_val;
7688 /* Update loop info. */
7689 loop_info->initial_value = reg;
7690 loop_info->initial_equiv_value = reg;
7691 loop_info->final_value = const0_rtx;
7692 loop_info->final_equiv_value = const0_rtx;
7693 loop_info->comparison_value = const0_rtx;
7694 loop_info->comparison_code = cmp_code;
7695 loop_info->increment = new_add_val;
7697 /* Inc LABEL_NUSES so that delete_insn will
7698 not delete the label. */
7699 LABEL_NUSES (XEXP (jump_label, 0))++;
7701 /* Emit an insn after the end of the loop to set the biv's
7702 proper exit value if it is used anywhere outside the loop. */
7703 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7705 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7706 emit_insn_after (gen_move_insn (reg, final_value),
7709 /* Delete compare/branch at end of loop. */
7710 delete_insn (PREV_INSN (loop_end));
7711 if (compare_and_branch == 2)
7712 delete_insn (first_compare);
7714 /* Add new compare/branch insn at end of loop. */
7716 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7717 GET_MODE (reg), 0, 0,
7718 XEXP (jump_label, 0));
7719 tem = gen_sequence ();
7721 emit_jump_insn_before (tem, loop_end);
7723 for (tem = PREV_INSN (loop_end);
7724 tem && GET_CODE (tem) != JUMP_INSN;
7725 tem = PREV_INSN (tem))
7729 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7735 /* Increment of LABEL_NUSES done above. */
7736 /* Register is now always nonnegative,
7737 so add REG_NONNEG note to the branch. */
7738 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7744 /* No insn may reference both the reversed and another biv or it
7745 will fail (see comment near the top of the loop reversal
7747 Earlier on, we have verified that the biv has no use except
7748 counting, or it is the only biv in this function.
7749 However, the code that computes no_use_except_counting does
7750 not verify reg notes. It's possible to have an insn that
7751 references another biv, and has a REG_EQUAL note with an
7752 expression based on the reversed biv. To avoid this case,
7753 remove all REG_EQUAL notes based on the reversed biv
7755 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7759 rtx set = single_set (p);
7760 /* If this is a set of a GIV based on the reversed biv, any
7761 REG_EQUAL notes should still be correct. */
7763 || GET_CODE (SET_DEST (set)) != REG
7764 || (size_t) REGNO (SET_DEST (set)) >= ivs->n_regs
7765 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7766 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7767 for (pnote = ®_NOTES (p); *pnote;)
7769 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7770 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7772 *pnote = XEXP (*pnote, 1);
7774 pnote = &XEXP (*pnote, 1);
7778 /* Mark that this biv has been reversed. Each giv which depends
7779 on this biv, and which is also live past the end of the loop
7780 will have to be fixed up. */
7784 if (loop_dump_stream)
7786 fprintf (loop_dump_stream, "Reversed loop");
7788 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7790 fprintf (loop_dump_stream, "\n");
7801 /* Verify whether the biv BL appears to be eliminable,
7802 based on the insns in the loop that refer to it.
7804 If ELIMINATE_P is non-zero, actually do the elimination.
7806 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7807 determine whether invariant insns should be placed inside or at the
7808 start of the loop. */
7811 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7812 const struct loop *loop;
7813 struct iv_class *bl;
7815 int threshold, insn_count;
7817 struct loop_ivs *ivs = LOOP_IVS (loop);
7818 rtx reg = bl->biv->dest_reg;
7819 rtx loop_start = loop->start;
7820 rtx loop_end = loop->end;
7823 /* Scan all insns in the loop, stopping if we find one that uses the
7824 biv in a way that we cannot eliminate. */
7826 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7828 enum rtx_code code = GET_CODE (p);
7829 rtx where = threshold >= insn_count ? loop_start : p;
7831 /* If this is a libcall that sets a giv, skip ahead to its end. */
7832 if (GET_RTX_CLASS (code) == 'i')
7834 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7838 rtx last = XEXP (note, 0);
7839 rtx set = single_set (last);
7841 if (set && GET_CODE (SET_DEST (set)) == REG)
7843 unsigned int regno = REGNO (SET_DEST (set));
7845 if (regno < ivs->n_regs
7846 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7847 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7852 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7853 && reg_mentioned_p (reg, PATTERN (p))
7854 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7855 eliminate_p, where))
7857 if (loop_dump_stream)
7858 fprintf (loop_dump_stream,
7859 "Cannot eliminate biv %d: biv used in insn %d.\n",
7860 bl->regno, INSN_UID (p));
7867 if (loop_dump_stream)
7868 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7869 bl->regno, eliminate_p ? "was" : "can be");
7876 /* INSN and REFERENCE are instructions in the same insn chain.
7877 Return non-zero if INSN is first. */
7880 loop_insn_first_p (insn, reference)
7881 rtx insn, reference;
7885 for (p = insn, q = reference;;)
7887 /* Start with test for not first so that INSN == REFERENCE yields not
7889 if (q == insn || ! p)
7891 if (p == reference || ! q)
7894 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7895 previous insn, hence the <= comparison below does not work if
7897 if (INSN_UID (p) < max_uid_for_loop
7898 && INSN_UID (q) < max_uid_for_loop
7899 && GET_CODE (p) != NOTE)
7900 return INSN_LUID (p) <= INSN_LUID (q);
7902 if (INSN_UID (p) >= max_uid_for_loop
7903 || GET_CODE (p) == NOTE)
7905 if (INSN_UID (q) >= max_uid_for_loop)
7910 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7911 the offset that we have to take into account due to auto-increment /
7912 div derivation is zero. */
7914 biv_elimination_giv_has_0_offset (biv, giv, insn)
7915 struct induction *biv, *giv;
7918 /* If the giv V had the auto-inc address optimization applied
7919 to it, and INSN occurs between the giv insn and the biv
7920 insn, then we'd have to adjust the value used here.
7921 This is rare, so we don't bother to make this possible. */
7922 if (giv->auto_inc_opt
7923 && ((loop_insn_first_p (giv->insn, insn)
7924 && loop_insn_first_p (insn, biv->insn))
7925 || (loop_insn_first_p (biv->insn, insn)
7926 && loop_insn_first_p (insn, giv->insn))))
7932 /* If BL appears in X (part of the pattern of INSN), see if we can
7933 eliminate its use. If so, return 1. If not, return 0.
7935 If BIV does not appear in X, return 1.
7937 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7938 where extra insns should be added. Depending on how many items have been
7939 moved out of the loop, it will either be before INSN or at the start of
7943 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7944 const struct loop *loop;
7946 struct iv_class *bl;
7950 enum rtx_code code = GET_CODE (x);
7951 rtx reg = bl->biv->dest_reg;
7952 enum machine_mode mode = GET_MODE (reg);
7953 struct induction *v;
7965 /* If we haven't already been able to do something with this BIV,
7966 we can't eliminate it. */
7972 /* If this sets the BIV, it is not a problem. */
7973 if (SET_DEST (x) == reg)
7976 /* If this is an insn that defines a giv, it is also ok because
7977 it will go away when the giv is reduced. */
7978 for (v = bl->giv; v; v = v->next_iv)
7979 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7983 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7985 /* Can replace with any giv that was reduced and
7986 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7987 Require a constant for MULT_VAL, so we know it's nonzero.
7988 ??? We disable this optimization to avoid potential
7991 for (v = bl->giv; v; v = v->next_iv)
7992 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7993 && v->add_val == const0_rtx
7994 && ! v->ignore && ! v->maybe_dead && v->always_computable
7998 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8004 /* If the giv has the opposite direction of change,
8005 then reverse the comparison. */
8006 if (INTVAL (v->mult_val) < 0)
8007 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
8008 const0_rtx, v->new_reg);
8012 /* We can probably test that giv's reduced reg. */
8013 if (validate_change (insn, &SET_SRC (x), new, 0))
8017 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
8018 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
8019 Require a constant for MULT_VAL, so we know it's nonzero.
8020 ??? Do this only if ADD_VAL is a pointer to avoid a potential
8021 overflow problem. */
8023 for (v = bl->giv; v; v = v->next_iv)
8024 if (GET_CODE (v->mult_val) == CONST_INT
8025 && v->mult_val != const0_rtx
8026 && ! v->ignore && ! v->maybe_dead && v->always_computable
8028 && (GET_CODE (v->add_val) == SYMBOL_REF
8029 || GET_CODE (v->add_val) == LABEL_REF
8030 || GET_CODE (v->add_val) == CONST
8031 || (GET_CODE (v->add_val) == REG
8032 && REG_POINTER (v->add_val))))
8034 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8040 /* If the giv has the opposite direction of change,
8041 then reverse the comparison. */
8042 if (INTVAL (v->mult_val) < 0)
8043 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
8046 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
8047 copy_rtx (v->add_val));
8049 /* Replace biv with the giv's reduced register. */
8050 update_reg_last_use (v->add_val, insn);
8051 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8054 /* Insn doesn't support that constant or invariant. Copy it
8055 into a register (it will be a loop invariant.) */
8056 tem = gen_reg_rtx (GET_MODE (v->new_reg));
8058 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
8061 /* Substitute the new register for its invariant value in
8062 the compare expression. */
8063 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
8064 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8073 case GT: case GE: case GTU: case GEU:
8074 case LT: case LE: case LTU: case LEU:
8075 /* See if either argument is the biv. */
8076 if (XEXP (x, 0) == reg)
8077 arg = XEXP (x, 1), arg_operand = 1;
8078 else if (XEXP (x, 1) == reg)
8079 arg = XEXP (x, 0), arg_operand = 0;
8083 if (CONSTANT_P (arg))
8085 /* First try to replace with any giv that has constant positive
8086 mult_val and constant add_val. We might be able to support
8087 negative mult_val, but it seems complex to do it in general. */
8089 for (v = bl->giv; v; v = v->next_iv)
8090 if (GET_CODE (v->mult_val) == CONST_INT
8091 && INTVAL (v->mult_val) > 0
8092 && (GET_CODE (v->add_val) == SYMBOL_REF
8093 || GET_CODE (v->add_val) == LABEL_REF
8094 || GET_CODE (v->add_val) == CONST
8095 || (GET_CODE (v->add_val) == REG
8096 && REG_POINTER (v->add_val)))
8097 && ! v->ignore && ! v->maybe_dead && v->always_computable
8100 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8106 /* Replace biv with the giv's reduced reg. */
8107 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
8109 /* If all constants are actually constant integers and
8110 the derived constant can be directly placed in the COMPARE,
8112 if (GET_CODE (arg) == CONST_INT
8113 && GET_CODE (v->mult_val) == CONST_INT
8114 && GET_CODE (v->add_val) == CONST_INT)
8116 validate_change (insn, &XEXP (x, arg_operand),
8117 GEN_INT (INTVAL (arg)
8118 * INTVAL (v->mult_val)
8119 + INTVAL (v->add_val)), 1);
8123 /* Otherwise, load it into a register. */
8124 tem = gen_reg_rtx (mode);
8125 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8126 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8128 if (apply_change_group ())
8132 /* Look for giv with positive constant mult_val and nonconst add_val.
8133 Insert insns to calculate new compare value.
8134 ??? Turn this off due to possible overflow. */
8136 for (v = bl->giv; v; v = v->next_iv)
8137 if (GET_CODE (v->mult_val) == CONST_INT
8138 && INTVAL (v->mult_val) > 0
8139 && ! v->ignore && ! v->maybe_dead && v->always_computable
8145 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8151 tem = gen_reg_rtx (mode);
8153 /* Replace biv with giv's reduced register. */
8154 validate_change (insn, &XEXP (x, 1 - arg_operand),
8157 /* Compute value to compare against. */
8158 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8159 /* Use it in this insn. */
8160 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8161 if (apply_change_group ())
8165 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
8167 if (loop_invariant_p (loop, arg) == 1)
8169 /* Look for giv with constant positive mult_val and nonconst
8170 add_val. Insert insns to compute new compare value.
8171 ??? Turn this off due to possible overflow. */
8173 for (v = bl->giv; v; v = v->next_iv)
8174 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
8175 && ! v->ignore && ! v->maybe_dead && v->always_computable
8181 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8187 tem = gen_reg_rtx (mode);
8189 /* Replace biv with giv's reduced register. */
8190 validate_change (insn, &XEXP (x, 1 - arg_operand),
8193 /* Compute value to compare against. */
8194 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8196 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8197 if (apply_change_group ())
8202 /* This code has problems. Basically, you can't know when
8203 seeing if we will eliminate BL, whether a particular giv
8204 of ARG will be reduced. If it isn't going to be reduced,
8205 we can't eliminate BL. We can try forcing it to be reduced,
8206 but that can generate poor code.
8208 The problem is that the benefit of reducing TV, below should
8209 be increased if BL can actually be eliminated, but this means
8210 we might have to do a topological sort of the order in which
8211 we try to process biv. It doesn't seem worthwhile to do
8212 this sort of thing now. */
8215 /* Otherwise the reg compared with had better be a biv. */
8216 if (GET_CODE (arg) != REG
8217 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8220 /* Look for a pair of givs, one for each biv,
8221 with identical coefficients. */
8222 for (v = bl->giv; v; v = v->next_iv)
8224 struct induction *tv;
8226 if (v->ignore || v->maybe_dead || v->mode != mode)
8229 for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
8231 if (! tv->ignore && ! tv->maybe_dead
8232 && rtx_equal_p (tv->mult_val, v->mult_val)
8233 && rtx_equal_p (tv->add_val, v->add_val)
8234 && tv->mode == mode)
8236 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8242 /* Replace biv with its giv's reduced reg. */
8243 XEXP (x, 1 - arg_operand) = v->new_reg;
8244 /* Replace other operand with the other giv's
8246 XEXP (x, arg_operand) = tv->new_reg;
8253 /* If we get here, the biv can't be eliminated. */
8257 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8258 biv is used in it, since it will be replaced. */
8259 for (v = bl->giv; v; v = v->next_iv)
8260 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8268 /* See if any subexpression fails elimination. */
8269 fmt = GET_RTX_FORMAT (code);
8270 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8275 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8276 eliminate_p, where))
8281 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8282 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8283 eliminate_p, where))
8292 /* Return nonzero if the last use of REG
8293 is in an insn following INSN in the same basic block. */
8296 last_use_this_basic_block (reg, insn)
8302 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8305 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8311 /* Called via `note_stores' to record the initial value of a biv. Here we
8312 just record the location of the set and process it later. */
8315 record_initial (dest, set, data)
8318 void *data ATTRIBUTE_UNUSED;
8320 struct loop_ivs *ivs = (struct loop_ivs *) data;
8321 struct iv_class *bl;
8323 if (GET_CODE (dest) != REG
8324 || REGNO (dest) >= ivs->n_regs
8325 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8328 bl = REG_IV_CLASS (ivs, REGNO (dest));
8330 /* If this is the first set found, record it. */
8331 if (bl->init_insn == 0)
8333 bl->init_insn = note_insn;
8338 /* If any of the registers in X are "old" and currently have a last use earlier
8339 than INSN, update them to have a last use of INSN. Their actual last use
8340 will be the previous insn but it will not have a valid uid_luid so we can't
8344 update_reg_last_use (x, insn)
8348 /* Check for the case where INSN does not have a valid luid. In this case,
8349 there is no need to modify the regno_last_uid, as this can only happen
8350 when code is inserted after the loop_end to set a pseudo's final value,
8351 and hence this insn will never be the last use of x. */
8352 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8353 && INSN_UID (insn) < max_uid_for_loop
8354 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8355 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8359 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8360 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8363 update_reg_last_use (XEXP (x, i), insn);
8364 else if (fmt[i] == 'E')
8365 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8366 update_reg_last_use (XVECEXP (x, i, j), insn);
8371 /* Given an insn INSN and condition COND, return the condition in a
8372 canonical form to simplify testing by callers. Specifically:
8374 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8375 (2) Both operands will be machine operands; (cc0) will have been replaced.
8376 (3) If an operand is a constant, it will be the second operand.
8377 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8378 for GE, GEU, and LEU.
8380 If the condition cannot be understood, or is an inequality floating-point
8381 comparison which needs to be reversed, 0 will be returned.
8383 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8385 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8386 insn used in locating the condition was found. If a replacement test
8387 of the condition is desired, it should be placed in front of that
8388 insn and we will be sure that the inputs are still valid.
8390 If WANT_REG is non-zero, we wish the condition to be relative to that
8391 register, if possible. Therefore, do not canonicalize the condition
8395 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8407 int reverse_code = 0;
8408 int did_reverse_condition = 0;
8409 enum machine_mode mode;
8411 code = GET_CODE (cond);
8412 mode = GET_MODE (cond);
8413 op0 = XEXP (cond, 0);
8414 op1 = XEXP (cond, 1);
8418 code = reverse_condition (code);
8419 did_reverse_condition ^= 1;
8425 /* If we are comparing a register with zero, see if the register is set
8426 in the previous insn to a COMPARE or a comparison operation. Perform
8427 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8430 while (GET_RTX_CLASS (code) == '<'
8431 && op1 == CONST0_RTX (GET_MODE (op0))
8434 /* Set non-zero when we find something of interest. */
8438 /* If comparison with cc0, import actual comparison from compare
8442 if ((prev = prev_nonnote_insn (prev)) == 0
8443 || GET_CODE (prev) != INSN
8444 || (set = single_set (prev)) == 0
8445 || SET_DEST (set) != cc0_rtx)
8448 op0 = SET_SRC (set);
8449 op1 = CONST0_RTX (GET_MODE (op0));
8455 /* If this is a COMPARE, pick up the two things being compared. */
8456 if (GET_CODE (op0) == COMPARE)
8458 op1 = XEXP (op0, 1);
8459 op0 = XEXP (op0, 0);
8462 else if (GET_CODE (op0) != REG)
8465 /* Go back to the previous insn. Stop if it is not an INSN. We also
8466 stop if it isn't a single set or if it has a REG_INC note because
8467 we don't want to bother dealing with it. */
8469 if ((prev = prev_nonnote_insn (prev)) == 0
8470 || GET_CODE (prev) != INSN
8471 || FIND_REG_INC_NOTE (prev, 0)
8472 || (set = single_set (prev)) == 0)
8475 /* If this is setting OP0, get what it sets it to if it looks
8477 if (rtx_equal_p (SET_DEST (set), op0))
8479 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8481 /* ??? We may not combine comparisons done in a CCmode with
8482 comparisons not done in a CCmode. This is to aid targets
8483 like Alpha that have an IEEE compliant EQ instruction, and
8484 a non-IEEE compliant BEQ instruction. The use of CCmode is
8485 actually artificial, simply to prevent the combination, but
8486 should not affect other platforms.
8488 However, we must allow VOIDmode comparisons to match either
8489 CCmode or non-CCmode comparison, because some ports have
8490 modeless comparisons inside branch patterns.
8492 ??? This mode check should perhaps look more like the mode check
8493 in simplify_comparison in combine. */
8495 if ((GET_CODE (SET_SRC (set)) == COMPARE
8498 && GET_MODE_CLASS (inner_mode) == MODE_INT
8499 && (GET_MODE_BITSIZE (inner_mode)
8500 <= HOST_BITS_PER_WIDE_INT)
8501 && (STORE_FLAG_VALUE
8502 & ((HOST_WIDE_INT) 1
8503 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8504 #ifdef FLOAT_STORE_FLAG_VALUE
8506 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8507 && (REAL_VALUE_NEGATIVE
8508 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8511 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8512 && (((GET_MODE_CLASS (mode) == MODE_CC)
8513 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8514 || mode == VOIDmode || inner_mode == VOIDmode))
8516 else if (((code == EQ
8518 && (GET_MODE_BITSIZE (inner_mode)
8519 <= HOST_BITS_PER_WIDE_INT)
8520 && GET_MODE_CLASS (inner_mode) == MODE_INT
8521 && (STORE_FLAG_VALUE
8522 & ((HOST_WIDE_INT) 1
8523 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8524 #ifdef FLOAT_STORE_FLAG_VALUE
8526 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8527 && (REAL_VALUE_NEGATIVE
8528 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8531 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8532 && (((GET_MODE_CLASS (mode) == MODE_CC)
8533 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8534 || mode == VOIDmode || inner_mode == VOIDmode))
8537 /* We might have reversed a LT to get a GE here. But this wasn't
8538 actually the comparison of data, so we don't flag that we
8539 have had to reverse the condition. */
8540 did_reverse_condition ^= 1;
8548 else if (reg_set_p (op0, prev))
8549 /* If this sets OP0, but not directly, we have to give up. */
8554 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8555 code = GET_CODE (x);
8558 code = reverse_condition (code);
8559 if (code == UNKNOWN)
8561 did_reverse_condition ^= 1;
8565 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8571 /* If constant is first, put it last. */
8572 if (CONSTANT_P (op0))
8573 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8575 /* If OP0 is the result of a comparison, we weren't able to find what
8576 was really being compared, so fail. */
8577 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8580 /* Canonicalize any ordered comparison with integers involving equality
8581 if we can do computations in the relevant mode and we do not
8584 if (GET_CODE (op1) == CONST_INT
8585 && GET_MODE (op0) != VOIDmode
8586 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8588 HOST_WIDE_INT const_val = INTVAL (op1);
8589 unsigned HOST_WIDE_INT uconst_val = const_val;
8590 unsigned HOST_WIDE_INT max_val
8591 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8596 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8597 code = LT, op1 = GEN_INT (const_val + 1);
8600 /* When cross-compiling, const_val might be sign-extended from
8601 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8603 if ((HOST_WIDE_INT) (const_val & max_val)
8604 != (((HOST_WIDE_INT) 1
8605 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8606 code = GT, op1 = GEN_INT (const_val - 1);
8610 if (uconst_val < max_val)
8611 code = LTU, op1 = GEN_INT (uconst_val + 1);
8615 if (uconst_val != 0)
8616 code = GTU, op1 = GEN_INT (uconst_val - 1);
8624 /* If this was floating-point and we reversed anything other than an
8625 EQ or NE or (UN)ORDERED, return zero. */
8626 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8627 && did_reverse_condition
8628 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8630 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8634 /* Never return CC0; return zero instead. */
8639 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8642 /* Given a jump insn JUMP, return the condition that will cause it to branch
8643 to its JUMP_LABEL. If the condition cannot be understood, or is an
8644 inequality floating-point comparison which needs to be reversed, 0 will
8647 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8648 insn used in locating the condition was found. If a replacement test
8649 of the condition is desired, it should be placed in front of that
8650 insn and we will be sure that the inputs are still valid. */
8653 get_condition (jump, earliest)
8661 /* If this is not a standard conditional jump, we can't parse it. */
8662 if (GET_CODE (jump) != JUMP_INSN
8663 || ! any_condjump_p (jump))
8665 set = pc_set (jump);
8667 cond = XEXP (SET_SRC (set), 0);
8669 /* If this branches to JUMP_LABEL when the condition is false, reverse
8672 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8673 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8675 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8678 /* Similar to above routine, except that we also put an invariant last
8679 unless both operands are invariants. */
8682 get_condition_for_loop (loop, x)
8683 const struct loop *loop;
8686 rtx comparison = get_condition (x, NULL_PTR);
8689 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8690 || loop_invariant_p (loop, XEXP (comparison, 1)))
8693 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8694 XEXP (comparison, 1), XEXP (comparison, 0));
8697 /* Scan the function and determine whether it has indirect (computed) jumps.
8699 This is taken mostly from flow.c; similar code exists elsewhere
8700 in the compiler. It may be useful to put this into rtlanal.c. */
8702 indirect_jump_in_function_p (start)
8707 for (insn = start; insn; insn = NEXT_INSN (insn))
8708 if (computed_jump_p (insn))
8714 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8715 documentation for LOOP_MEMS for the definition of `appropriate'.
8716 This function is called from prescan_loop via for_each_rtx. */
8719 insert_loop_mem (mem, data)
8721 void *data ATTRIBUTE_UNUSED;
8723 struct loop_info *loop_info = data;
8730 switch (GET_CODE (m))
8736 /* We're not interested in MEMs that are only clobbered. */
8740 /* We're not interested in the MEM associated with a
8741 CONST_DOUBLE, so there's no need to traverse into this. */
8745 /* We're not interested in any MEMs that only appear in notes. */
8749 /* This is not a MEM. */
8753 /* See if we've already seen this MEM. */
8754 for (i = 0; i < loop_info->mems_idx; ++i)
8755 if (rtx_equal_p (m, loop_info->mems[i].mem))
8757 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8758 /* The modes of the two memory accesses are different. If
8759 this happens, something tricky is going on, and we just
8760 don't optimize accesses to this MEM. */
8761 loop_info->mems[i].optimize = 0;
8766 /* Resize the array, if necessary. */
8767 if (loop_info->mems_idx == loop_info->mems_allocated)
8769 if (loop_info->mems_allocated != 0)
8770 loop_info->mems_allocated *= 2;
8772 loop_info->mems_allocated = 32;
8774 loop_info->mems = (loop_mem_info *)
8775 xrealloc (loop_info->mems,
8776 loop_info->mems_allocated * sizeof (loop_mem_info));
8779 /* Actually insert the MEM. */
8780 loop_info->mems[loop_info->mems_idx].mem = m;
8781 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8782 because we can't put it in a register. We still store it in the
8783 table, though, so that if we see the same address later, but in a
8784 non-BLK mode, we'll not think we can optimize it at that point. */
8785 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8786 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8787 ++loop_info->mems_idx;
8792 /* Like load_mems, but also ensures that REGS->SET_IN_LOOP,
8793 REGS->MAY_NOT_OPTIMIZE, REGS->SINGLE_USAGE, and INSN_COUNT have the correct
8794 values after load_mems. */
8797 load_mems_and_recount_loop_regs_set (loop, insn_count)
8798 const struct loop *loop;
8801 struct loop_regs *regs = LOOP_REGS (loop);
8802 int nregs = max_reg_num ();
8806 /* Recalculate regs->set_in_loop and friends since load_mems may have
8807 created new registers. */
8808 if (max_reg_num () > nregs)
8814 nregs = max_reg_num ();
8816 if ((unsigned) nregs > regs->set_in_loop->num_elements)
8818 /* Grow all the arrays. */
8819 VARRAY_GROW (regs->set_in_loop, nregs);
8820 VARRAY_GROW (regs->n_times_set, nregs);
8821 VARRAY_GROW (regs->may_not_optimize, nregs);
8822 VARRAY_GROW (regs->single_usage, nregs);
8824 /* Clear the arrays */
8825 memset ((char *) ®s->set_in_loop->data, 0, nregs * sizeof (int));
8826 memset ((char *) ®s->may_not_optimize->data, 0, nregs * sizeof (char));
8827 memset ((char *) ®s->single_usage->data, 0, nregs * sizeof (rtx));
8829 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
8832 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8834 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8835 VARRAY_INT (regs->set_in_loop, i) = 1;
8838 #ifdef AVOID_CCMODE_COPIES
8839 /* Don't try to move insns which set CC registers if we should not
8840 create CCmode register copies. */
8841 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8842 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8843 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8846 /* Set regs->n_times_set for the new registers. */
8847 bcopy ((char *) (®s->set_in_loop->data.i[0] + old_nregs),
8848 (char *) (®s->n_times_set->data.i[0] + old_nregs),
8849 (nregs - old_nregs) * sizeof (int));
8853 /* Move MEMs into registers for the duration of the loop. */
8857 const struct loop *loop;
8859 struct loop_info *loop_info = LOOP_INFO (loop);
8860 struct loop_regs *regs = LOOP_REGS (loop);
8861 int maybe_never = 0;
8864 rtx label = NULL_RTX;
8866 /* Nonzero if the next instruction may never be executed. */
8867 int next_maybe_never = 0;
8868 int last_max_reg = max_reg_num ();
8870 if (loop_info->mems_idx == 0)
8873 /* We cannot use next_label here because it skips over normal insns. */
8874 end_label = next_nonnote_insn (loop->end);
8875 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8876 end_label = NULL_RTX;
8878 /* Check to see if it's possible that some instructions in the loop are
8879 never executed. Also check if there is a goto out of the loop other
8880 than right after the end of the loop. */
8881 for (p = next_insn_in_loop (loop, loop->scan_start);
8882 p != NULL_RTX && ! maybe_never;
8883 p = next_insn_in_loop (loop, p))
8885 if (GET_CODE (p) == CODE_LABEL)
8887 else if (GET_CODE (p) == JUMP_INSN
8888 /* If we enter the loop in the middle, and scan
8889 around to the beginning, don't set maybe_never
8890 for that. This must be an unconditional jump,
8891 otherwise the code at the top of the loop might
8892 never be executed. Unconditional jumps are
8893 followed a by barrier then loop end. */
8894 && ! (GET_CODE (p) == JUMP_INSN
8895 && JUMP_LABEL (p) == loop->top
8896 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8897 && any_uncondjump_p (p)))
8899 /* If this is a jump outside of the loop but not right
8900 after the end of the loop, we would have to emit new fixup
8901 sequences for each such label. */
8902 if (JUMP_LABEL (p) != end_label
8903 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8904 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8905 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8908 if (!any_condjump_p (p))
8909 /* Something complicated. */
8912 /* If there are any more instructions in the loop, they
8913 might not be reached. */
8914 next_maybe_never = 1;
8916 else if (next_maybe_never)
8920 /* Find start of the extended basic block that enters the loop. */
8921 for (p = loop->start;
8922 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8928 /* Build table of mems that get set to constant values before the
8930 for (; p != loop->start; p = NEXT_INSN (p))
8931 cselib_process_insn (p);
8933 /* Actually move the MEMs. */
8934 for (i = 0; i < loop_info->mems_idx; ++i)
8936 regset_head load_copies;
8937 regset_head store_copies;
8940 rtx mem = loop_info->mems[i].mem;
8943 if (MEM_VOLATILE_P (mem)
8944 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8945 /* There's no telling whether or not MEM is modified. */
8946 loop_info->mems[i].optimize = 0;
8948 /* Go through the MEMs written to in the loop to see if this
8949 one is aliased by one of them. */
8950 mem_list_entry = loop_info->store_mems;
8951 while (mem_list_entry)
8953 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8955 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8958 /* MEM is indeed aliased by this store. */
8959 loop_info->mems[i].optimize = 0;
8962 mem_list_entry = XEXP (mem_list_entry, 1);
8965 if (flag_float_store && written
8966 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8967 loop_info->mems[i].optimize = 0;
8969 /* If this MEM is written to, we must be sure that there
8970 are no reads from another MEM that aliases this one. */
8971 if (loop_info->mems[i].optimize && written)
8975 for (j = 0; j < loop_info->mems_idx; ++j)
8979 else if (true_dependence (mem,
8981 loop_info->mems[j].mem,
8984 /* It's not safe to hoist loop_info->mems[i] out of
8985 the loop because writes to it might not be
8986 seen by reads from loop_info->mems[j]. */
8987 loop_info->mems[i].optimize = 0;
8993 if (maybe_never && may_trap_p (mem))
8994 /* We can't access the MEM outside the loop; it might
8995 cause a trap that wouldn't have happened otherwise. */
8996 loop_info->mems[i].optimize = 0;
8998 if (!loop_info->mems[i].optimize)
8999 /* We thought we were going to lift this MEM out of the
9000 loop, but later discovered that we could not. */
9003 INIT_REG_SET (&load_copies);
9004 INIT_REG_SET (&store_copies);
9006 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
9007 order to keep scan_loop from moving stores to this MEM
9008 out of the loop just because this REG is neither a
9009 user-variable nor used in the loop test. */
9010 reg = gen_reg_rtx (GET_MODE (mem));
9011 REG_USERVAR_P (reg) = 1;
9012 loop_info->mems[i].reg = reg;
9014 /* Now, replace all references to the MEM with the
9015 corresponding pesudos. */
9017 for (p = next_insn_in_loop (loop, loop->scan_start);
9019 p = next_insn_in_loop (loop, p))
9025 set = single_set (p);
9027 /* See if this copies the mem into a register that isn't
9028 modified afterwards. We'll try to do copy propagation
9029 a little further on. */
9031 /* @@@ This test is _way_ too conservative. */
9033 && GET_CODE (SET_DEST (set)) == REG
9034 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
9035 && REGNO (SET_DEST (set)) < last_max_reg
9036 && VARRAY_INT (regs->n_times_set,
9037 REGNO (SET_DEST (set))) == 1
9038 && rtx_equal_p (SET_SRC (set), mem))
9039 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
9041 /* See if this copies the mem from a register that isn't
9042 modified afterwards. We'll try to remove the
9043 redundant copy later on by doing a little register
9044 renaming and copy propagation. This will help
9045 to untangle things for the BIV detection code. */
9048 && GET_CODE (SET_SRC (set)) == REG
9049 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
9050 && REGNO (SET_SRC (set)) < last_max_reg
9051 && VARRAY_INT (regs->n_times_set, REGNO (SET_SRC (set))) == 1
9052 && rtx_equal_p (SET_DEST (set), mem))
9053 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
9055 /* Replace the memory reference with the shadow register. */
9056 replace_loop_mems (p, loop_info->mems[i].mem,
9057 loop_info->mems[i].reg);
9060 if (GET_CODE (p) == CODE_LABEL
9061 || GET_CODE (p) == JUMP_INSN)
9065 if (! apply_change_group ())
9066 /* We couldn't replace all occurrences of the MEM. */
9067 loop_info->mems[i].optimize = 0;
9070 /* Load the memory immediately before LOOP->START, which is
9071 the NOTE_LOOP_BEG. */
9072 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
9076 struct elt_loc_list *const_equiv = 0;
9080 struct elt_loc_list *equiv;
9081 struct elt_loc_list *best_equiv = 0;
9082 for (equiv = e->locs; equiv; equiv = equiv->next)
9084 if (CONSTANT_P (equiv->loc))
9085 const_equiv = equiv;
9086 else if (GET_CODE (equiv->loc) == REG
9087 /* Extending hard register lifetimes cuases crash
9088 on SRC targets. Doing so on non-SRC is
9089 probably also not good idea, since we most
9090 probably have pseudoregister equivalence as
9092 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
9095 /* Use the constant equivalence if that is cheap enough. */
9097 best_equiv = const_equiv;
9098 else if (const_equiv
9099 && (rtx_cost (const_equiv->loc, SET)
9100 <= rtx_cost (best_equiv->loc, SET)))
9102 best_equiv = const_equiv;
9106 /* If best_equiv is nonzero, we know that MEM is set to a
9107 constant or register before the loop. We will use this
9108 knowledge to initialize the shadow register with that
9109 constant or reg rather than by loading from MEM. */
9111 best = copy_rtx (best_equiv->loc);
9113 set = gen_move_insn (reg, best);
9114 set = emit_insn_before (set, loop->start);
9116 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
9117 copy_rtx (const_equiv->loc),
9122 if (label == NULL_RTX)
9124 label = gen_label_rtx ();
9125 emit_label_after (label, loop->end);
9128 /* Store the memory immediately after END, which is
9129 the NOTE_LOOP_END. */
9130 set = gen_move_insn (copy_rtx (mem), reg);
9131 emit_insn_after (set, label);
9134 if (loop_dump_stream)
9136 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9137 REGNO (reg), (written ? "r/w" : "r/o"));
9138 print_rtl (loop_dump_stream, mem);
9139 fputc ('\n', loop_dump_stream);
9142 /* Attempt a bit of copy propagation. This helps untangle the
9143 data flow, and enables {basic,general}_induction_var to find
9145 EXECUTE_IF_SET_IN_REG_SET
9146 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9148 try_copy_prop (loop, reg, j);
9150 CLEAR_REG_SET (&load_copies);
9152 EXECUTE_IF_SET_IN_REG_SET
9153 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9155 try_swap_copy_prop (loop, reg, j);
9157 CLEAR_REG_SET (&store_copies);
9161 if (label != NULL_RTX && end_label != NULL_RTX)
9163 /* Now, we need to replace all references to the previous exit
9164 label with the new one. */
9169 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9171 for_each_rtx (&p, replace_label, &rr);
9173 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9174 field. This is not handled by for_each_rtx because it doesn't
9175 handle unprinted ('0') fields. We need to update JUMP_LABEL
9176 because the immediately following unroll pass will use it.
9177 replace_label would not work anyways, because that only handles
9179 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9180 JUMP_LABEL (p) = label;
9187 /* For communication between note_reg_stored and its caller. */
9188 struct note_reg_stored_arg
9194 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9197 note_reg_stored (x, setter, arg)
9198 rtx x, setter ATTRIBUTE_UNUSED;
9201 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9206 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9207 There must be exactly one insn that sets this pseudo; it will be
9208 deleted if all replacements succeed and we can prove that the register
9209 is not used after the loop. */
9212 try_copy_prop (loop, replacement, regno)
9213 const struct loop *loop;
9217 /* This is the reg that we are copying from. */
9218 rtx reg_rtx = regno_reg_rtx[regno];
9221 /* These help keep track of whether we replaced all uses of the reg. */
9222 int replaced_last = 0;
9223 int store_is_first = 0;
9225 for (insn = next_insn_in_loop (loop, loop->scan_start);
9227 insn = next_insn_in_loop (loop, insn))
9231 /* Only substitute within one extended basic block from the initializing
9233 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9236 if (! INSN_P (insn))
9239 /* Is this the initializing insn? */
9240 set = single_set (insn);
9242 && GET_CODE (SET_DEST (set)) == REG
9243 && REGNO (SET_DEST (set)) == regno)
9249 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9253 /* Only substitute after seeing the initializing insn. */
9254 if (init_insn && insn != init_insn)
9256 struct note_reg_stored_arg arg;
9258 replace_loop_regs (insn, reg_rtx, replacement);
9259 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9262 /* Stop replacing when REPLACEMENT is modified. */
9263 arg.reg = replacement;
9265 note_stores (PATTERN (insn), note_reg_stored, &arg);
9272 if (apply_change_group ())
9274 if (loop_dump_stream)
9275 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9276 if (store_is_first && replaced_last)
9278 PUT_CODE (init_insn, NOTE);
9279 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9280 if (loop_dump_stream)
9281 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9282 INSN_UID (init_insn));
9284 if (loop_dump_stream)
9285 fprintf (loop_dump_stream, ".\n");
9289 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9290 loop LOOP if the order of the sets of these registers can be
9291 swapped. There must be exactly one insn within the loop that sets
9292 this pseudo followed immediately by a move insn that sets
9293 REPLACEMENT with REGNO. */
9295 try_swap_copy_prop (loop, replacement, regno)
9296 const struct loop *loop;
9302 unsigned int new_regno;
9304 new_regno = REGNO (replacement);
9306 for (insn = next_insn_in_loop (loop, loop->scan_start);
9308 insn = next_insn_in_loop (loop, insn))
9310 /* Search for the insn that copies REGNO to NEW_REGNO? */
9311 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9312 && (set = single_set (insn))
9313 && GET_CODE (SET_DEST (set)) == REG
9314 && REGNO (SET_DEST (set)) == new_regno
9315 && GET_CODE (SET_SRC (set)) == REG
9316 && REGNO (SET_SRC (set)) == regno)
9320 if (insn != NULL_RTX)
9325 /* Some DEF-USE info would come in handy here to make this
9326 function more general. For now, just check the previous insn
9327 which is the most likely candidate for setting REGNO. */
9329 prev_insn = PREV_INSN (insn);
9331 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9332 && (prev_set = single_set (prev_insn))
9333 && GET_CODE (SET_DEST (prev_set)) == REG
9334 && REGNO (SET_DEST (prev_set)) == regno)
9337 (set (reg regno) (expr))
9338 (set (reg new_regno) (reg regno))
9340 so try converting this to:
9341 (set (reg new_regno) (expr))
9342 (set (reg regno) (reg new_regno))
9344 The former construct is often generated when a global
9345 variable used for an induction variable is shadowed by a
9346 register (NEW_REGNO). The latter construct improves the
9347 chances of GIV replacement and BIV elimination. */
9349 validate_change (prev_insn, &SET_DEST (prev_set),
9351 validate_change (insn, &SET_DEST (set),
9353 validate_change (insn, &SET_SRC (set),
9356 if (apply_change_group ())
9358 if (loop_dump_stream)
9359 fprintf (loop_dump_stream,
9360 " Swapped set of reg %d at %d with reg %d at %d.\n",
9361 regno, INSN_UID (insn),
9362 new_regno, INSN_UID (prev_insn));
9364 /* Update first use of REGNO. */
9365 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9366 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9368 /* Now perform copy propagation to hopefully
9369 remove all uses of REGNO within the loop. */
9370 try_copy_prop (loop, replacement, regno);
9376 /* Replace MEM with its associated pseudo register. This function is
9377 called from load_mems via for_each_rtx. DATA is actually a pointer
9378 to a structure describing the instruction currently being scanned
9379 and the MEM we are currently replacing. */
9382 replace_loop_mem (mem, data)
9386 loop_replace_args *args = (loop_replace_args *) data;
9392 switch (GET_CODE (m))
9398 /* We're not interested in the MEM associated with a
9399 CONST_DOUBLE, so there's no need to traverse into one. */
9403 /* This is not a MEM. */
9407 if (!rtx_equal_p (args->match, m))
9408 /* This is not the MEM we are currently replacing. */
9411 /* Actually replace the MEM. */
9412 validate_change (args->insn, mem, args->replacement, 1);
9418 replace_loop_mems (insn, mem, reg)
9423 loop_replace_args args;
9427 args.replacement = reg;
9429 for_each_rtx (&insn, replace_loop_mem, &args);
9432 /* Replace one register with another. Called through for_each_rtx; PX points
9433 to the rtx being scanned. DATA is actually a pointer to
9434 a structure of arguments. */
9437 replace_loop_reg (px, data)
9442 loop_replace_args *args = (loop_replace_args *) data;
9447 if (x == args->match)
9448 validate_change (args->insn, px, args->replacement, 1);
9454 replace_loop_regs (insn, reg, replacement)
9459 loop_replace_args args;
9463 args.replacement = replacement;
9465 for_each_rtx (&insn, replace_loop_reg, &args);
9468 /* Replace occurrences of the old exit label for the loop with the new
9469 one. DATA is an rtx_pair containing the old and new labels,
9473 replace_label (x, data)
9478 rtx old_label = ((rtx_pair *) data)->r1;
9479 rtx new_label = ((rtx_pair *) data)->r2;
9484 if (GET_CODE (l) != LABEL_REF)
9487 if (XEXP (l, 0) != old_label)
9490 XEXP (l, 0) = new_label;
9491 ++LABEL_NUSES (new_label);
9492 --LABEL_NUSES (old_label);
9497 #define LOOP_BLOCK_NUM_1(INSN) \
9498 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9500 /* The notes do not have an assigned block, so look at the next insn. */
9501 #define LOOP_BLOCK_NUM(INSN) \
9502 ((INSN) ? (GET_CODE (INSN) == NOTE \
9503 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9504 : LOOP_BLOCK_NUM_1 (INSN)) \
9507 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9510 loop_dump_aux (loop, file, verbose)
9511 const struct loop *loop;
9513 int verbose ATTRIBUTE_UNUSED;
9517 if (! loop || ! file)
9520 /* Print diagnostics to compare our concept of a loop with
9521 what the loop notes say. */
9522 if (! PREV_INSN (loop->first->head)
9523 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9524 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9525 != NOTE_INSN_LOOP_BEG)
9526 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9527 INSN_UID (PREV_INSN (loop->first->head)));
9528 if (! NEXT_INSN (loop->last->end)
9529 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9530 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9531 != NOTE_INSN_LOOP_END)
9532 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9533 INSN_UID (NEXT_INSN (loop->last->end)));
9538 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9539 LOOP_BLOCK_NUM (loop->start),
9540 LOOP_INSN_UID (loop->start),
9541 LOOP_BLOCK_NUM (loop->cont),
9542 LOOP_INSN_UID (loop->cont),
9543 LOOP_BLOCK_NUM (loop->cont),
9544 LOOP_INSN_UID (loop->cont),
9545 LOOP_BLOCK_NUM (loop->vtop),
9546 LOOP_INSN_UID (loop->vtop),
9547 LOOP_BLOCK_NUM (loop->end),
9548 LOOP_INSN_UID (loop->end));
9549 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9550 LOOP_BLOCK_NUM (loop->top),
9551 LOOP_INSN_UID (loop->top),
9552 LOOP_BLOCK_NUM (loop->scan_start),
9553 LOOP_INSN_UID (loop->scan_start));
9554 fprintf (file, ";; exit_count %d", loop->exit_count);
9555 if (loop->exit_count)
9557 fputs (", labels:", file);
9558 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9560 fprintf (file, " %d ",
9561 LOOP_INSN_UID (XEXP (label, 0)));
9566 /* This can happen when a marked loop appears as two nested loops,
9567 say from while (a || b) {}. The inner loop won't match
9568 the loop markers but the outer one will. */
9569 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9570 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9574 /* Call this function from the debugger to dump LOOP. */
9578 const struct loop *loop;
9580 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9583 /* Call this function from the debugger to dump LOOPS. */
9587 const struct loops *loops;
9589 flow_loops_dump (loops, stderr, loop_dump_aux, 1);
OSDN Git Service
