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 strength_reduce PARAMS ((struct loop *, int, int));
198 static void find_single_use_in_loop PARAMS ((rtx, rtx, varray_type));
199 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
200 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
201 static void record_biv PARAMS ((struct loop *, struct induction *,
202 rtx, rtx, rtx, rtx, rtx *,
204 static void check_final_value PARAMS ((const struct loop *,
205 struct induction *));
206 static void record_giv PARAMS ((const struct loop *, struct induction *,
207 rtx, rtx, rtx, rtx, rtx, rtx, int,
208 enum g_types, int, int, rtx *));
209 static void update_giv_derive PARAMS ((const struct loop *, rtx));
210 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
211 struct loop_info *));
212 static int basic_induction_var PARAMS ((const struct loop *, rtx,
213 enum machine_mode, rtx, rtx,
214 rtx *, rtx *, rtx **));
215 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
216 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
217 rtx *, rtx *, rtx *, int, int *,
219 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
220 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
221 static int check_dbra_loop PARAMS ((struct loop *, int));
222 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
223 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
224 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
225 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
226 static int product_cheap_p PARAMS ((rtx, rtx));
227 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
229 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
230 struct iv_class *, int, rtx));
231 static int last_use_this_basic_block PARAMS ((rtx, rtx));
232 static void record_initial PARAMS ((rtx, rtx, void *));
233 static void update_reg_last_use PARAMS ((rtx, rtx));
234 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
235 static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
237 static void load_mems PARAMS ((const struct loop *));
238 static int insert_loop_mem PARAMS ((rtx *, void *));
239 static int replace_loop_mem PARAMS ((rtx *, void *));
240 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
241 static int replace_loop_reg PARAMS ((rtx *, void *));
242 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
243 static void note_reg_stored PARAMS ((rtx, rtx, void *));
244 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
245 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
247 static int replace_label PARAMS ((rtx *, void *));
248 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
249 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
250 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
252 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
253 void debug_loop PARAMS ((const struct loop *));
254 void debug_loops PARAMS ((const struct loops *));
256 typedef struct rtx_pair
262 typedef struct loop_replace_args
269 /* Nonzero iff INSN is between START and END, inclusive. */
270 #define INSN_IN_RANGE_P(INSN, START, END) \
271 (INSN_UID (INSN) < max_uid_for_loop \
272 && INSN_LUID (INSN) >= INSN_LUID (START) \
273 && INSN_LUID (INSN) <= INSN_LUID (END))
275 /* Indirect_jump_in_function is computed once per function. */
276 static int indirect_jump_in_function;
277 static int indirect_jump_in_function_p PARAMS ((rtx));
279 static int compute_luids PARAMS ((rtx, rtx, int));
281 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
285 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
286 copy the value of the strength reduced giv to its original register. */
287 static int copy_cost;
289 /* Cost of using a register, to normalize the benefits of a giv. */
290 static int reg_address_cost;
295 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
297 reg_address_cost = address_cost (reg, SImode);
299 copy_cost = COSTS_N_INSNS (1);
302 /* Compute the mapping from uids to luids.
303 LUIDs are numbers assigned to insns, like uids,
304 except that luids increase monotonically through the code.
305 Start at insn START and stop just before END. Assign LUIDs
306 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
308 compute_luids (start, end, prev_luid)
315 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
317 if (INSN_UID (insn) >= max_uid_for_loop)
319 /* Don't assign luids to line-number NOTEs, so that the distance in
320 luids between two insns is not affected by -g. */
321 if (GET_CODE (insn) != NOTE
322 || NOTE_LINE_NUMBER (insn) <= 0)
323 uid_luid[INSN_UID (insn)] = ++i;
325 /* Give a line number note the same luid as preceding insn. */
326 uid_luid[INSN_UID (insn)] = i;
331 /* Entry point of this file. Perform loop optimization
332 on the current function. F is the first insn of the function
333 and DUMPFILE is a stream for output of a trace of actions taken
334 (or 0 if none should be output). */
337 loop_optimize (f, dumpfile, flags)
338 /* f is the first instruction of a chain of insns for one function */
345 struct loops loops_data;
346 struct loops *loops = &loops_data;
347 struct loop_info *loops_info;
348 static char *moved_once;
350 loop_dump_stream = dumpfile;
352 init_recog_no_volatile ();
354 max_reg_before_loop = max_reg_num ();
355 loop_max_reg = max_reg_before_loop;
359 /* Count the number of loops. */
362 for (insn = f; insn; insn = NEXT_INSN (insn))
364 if (GET_CODE (insn) == NOTE
365 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
369 /* Don't waste time if no loops. */
370 if (max_loop_num == 0)
373 loops->num = max_loop_num;
375 moved_once = (char *) xcalloc (max_reg_before_loop, sizeof (char));
377 /* Get size to use for tables indexed by uids.
378 Leave some space for labels allocated by find_and_verify_loops. */
379 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
381 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
382 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
383 sizeof (struct loop *));
385 /* Allocate storage for array of loops. */
386 loops->array = (struct loop *)
387 xcalloc (loops->num, sizeof (struct loop));
389 /* Find and process each loop.
390 First, find them, and record them in order of their beginnings. */
391 find_and_verify_loops (f, loops);
393 /* Allocate and initialize auxiliary loop information. */
394 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
395 for (i = 0; i < loops->num; i++)
396 loops->array[i].aux = loops_info + i;
398 /* Now find all register lifetimes. This must be done after
399 find_and_verify_loops, because it might reorder the insns in the
401 reg_scan (f, max_reg_before_loop, 1);
403 /* This must occur after reg_scan so that registers created by gcse
404 will have entries in the register tables.
406 We could have added a call to reg_scan after gcse_main in toplev.c,
407 but moving this call to init_alias_analysis is more efficient. */
408 init_alias_analysis ();
410 /* See if we went too far. Note that get_max_uid already returns
411 one more that the maximum uid of all insn. */
412 if (get_max_uid () > max_uid_for_loop)
414 /* Now reset it to the actual size we need. See above. */
415 max_uid_for_loop = get_max_uid ();
417 /* find_and_verify_loops has already called compute_luids, but it
418 might have rearranged code afterwards, so we need to recompute
420 max_luid = compute_luids (f, NULL_RTX, 0);
422 /* Don't leave gaps in uid_luid for insns that have been
423 deleted. It is possible that the first or last insn
424 using some register has been deleted by cross-jumping.
425 Make sure that uid_luid for that former insn's uid
426 points to the general area where that insn used to be. */
427 for (i = 0; i < max_uid_for_loop; i++)
429 uid_luid[0] = uid_luid[i];
430 if (uid_luid[0] != 0)
433 for (i = 0; i < max_uid_for_loop; i++)
434 if (uid_luid[i] == 0)
435 uid_luid[i] = uid_luid[i - 1];
437 /* Determine if the function has indirect jump. On some systems
438 this prevents low overhead loop instructions from being used. */
439 indirect_jump_in_function = indirect_jump_in_function_p (f);
441 /* Now scan the loops, last ones first, since this means inner ones are done
442 before outer ones. */
443 for (i = max_loop_num - 1; i >= 0; i--)
445 struct loop *loop = &loops->array[i];
446 struct loop_regs *regs = LOOP_REGS (loop);
448 regs->moved_once = moved_once;
450 if (! loop->invalid && loop->end)
451 scan_loop (loop, flags);
454 /* If there were lexical blocks inside the loop, they have been
455 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
456 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
457 the BLOCKs as well. */
458 if (write_symbols != NO_DEBUG)
461 end_alias_analysis ();
471 /* Returns the next insn, in execution order, after INSN. START and
472 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
473 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
474 insn-stream; it is used with loops that are entered near the
478 next_insn_in_loop (loop, insn)
479 const struct loop *loop;
482 insn = NEXT_INSN (insn);
484 if (insn == loop->end)
487 /* Go to the top of the loop, and continue there. */
494 if (insn == loop->scan_start)
501 /* Optimize one loop described by LOOP. */
503 /* ??? Could also move memory writes out of loops if the destination address
504 is invariant, the source is invariant, the memory write is not volatile,
505 and if we can prove that no read inside the loop can read this address
506 before the write occurs. If there is a read of this address after the
507 write, then we can also mark the memory read as invariant. */
510 scan_loop (loop, flags)
514 struct loop_info *loop_info = LOOP_INFO (loop);
515 struct loop_regs *regs = LOOP_REGS (loop);
517 rtx loop_start = loop->start;
518 rtx loop_end = loop->end;
520 /* 1 if we are scanning insns that could be executed zero times. */
522 /* 1 if we are scanning insns that might never be executed
523 due to a subroutine call which might exit before they are reached. */
525 /* Jump insn that enters the loop, or 0 if control drops in. */
526 rtx loop_entry_jump = 0;
527 /* Number of insns in the loop. */
530 rtx temp, update_start, update_end;
531 /* The SET from an insn, if it is the only SET in the insn. */
533 /* Chain describing insns movable in current loop. */
534 struct loop_movables *movables = LOOP_MOVABLES (loop);
535 /* Ratio of extra register life span we can justify
536 for saving an instruction. More if loop doesn't call subroutines
537 since in that case saving an insn makes more difference
538 and more registers are available. */
540 /* Nonzero if we are scanning instructions in a sub-loop. */
550 /* Determine whether this loop starts with a jump down to a test at
551 the end. This will occur for a small number of loops with a test
552 that is too complex to duplicate in front of the loop.
554 We search for the first insn or label in the loop, skipping NOTEs.
555 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
556 (because we might have a loop executed only once that contains a
557 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
558 (in case we have a degenerate loop).
560 Note that if we mistakenly think that a loop is entered at the top
561 when, in fact, it is entered at the exit test, the only effect will be
562 slightly poorer optimization. Making the opposite error can generate
563 incorrect code. Since very few loops now start with a jump to the
564 exit test, the code here to detect that case is very conservative. */
566 for (p = NEXT_INSN (loop_start);
568 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
569 && (GET_CODE (p) != NOTE
570 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
571 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
575 loop->scan_start = p;
577 /* Set up variables describing this loop. */
579 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
581 /* If loop has a jump before the first label,
582 the true entry is the target of that jump.
583 Start scan from there.
584 But record in LOOP->TOP the place where the end-test jumps
585 back to so we can scan that after the end of the loop. */
586 if (GET_CODE (p) == JUMP_INSN)
590 /* Loop entry must be unconditional jump (and not a RETURN) */
591 if (any_uncondjump_p (p)
592 && JUMP_LABEL (p) != 0
593 /* Check to see whether the jump actually
594 jumps out of the loop (meaning it's no loop).
595 This case can happen for things like
596 do {..} while (0). If this label was generated previously
597 by loop, we can't tell anything about it and have to reject
599 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
601 loop->top = next_label (loop->scan_start);
602 loop->scan_start = JUMP_LABEL (p);
606 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
607 as required by loop_reg_used_before_p. So skip such loops. (This
608 test may never be true, but it's best to play it safe.)
610 Also, skip loops where we do not start scanning at a label. This
611 test also rejects loops starting with a JUMP_INSN that failed the
614 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
615 || GET_CODE (loop->scan_start) != CODE_LABEL)
617 if (loop_dump_stream)
618 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
619 INSN_UID (loop_start), INSN_UID (loop_end));
623 /* Count number of times each reg is set during this loop. Set
624 VARRAY_CHAR (regs->may_not_optimize, I) if it is not safe to move
625 out the setting of register I. Set VARRAY_RTX
626 (regs->single_usage, I). */
628 /* Allocate extra space for REGS that might be created by
629 load_mems. We allocate a little extra slop as well, in the hopes
630 that even after the moving of movables creates some new registers
631 we won't have to reallocate these arrays. However, we do grow
632 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
633 nregs = max_reg_num () + loop_info->mems_idx + 16;
634 VARRAY_INT_INIT (regs->set_in_loop, nregs, "set_in_loop");
635 VARRAY_INT_INIT (regs->n_times_set, nregs, "n_times_set");
636 VARRAY_CHAR_INIT (regs->may_not_optimize, nregs, "may_not_optimize");
637 VARRAY_RTX_INIT (regs->single_usage, nregs, "single_usage");
641 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
644 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
646 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
647 VARRAY_INT (regs->set_in_loop, i) = 1;
650 #ifdef AVOID_CCMODE_COPIES
651 /* Don't try to move insns which set CC registers if we should not
652 create CCmode register copies. */
653 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
654 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
655 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
658 bcopy ((char *) ®s->set_in_loop->data,
659 (char *) ®s->n_times_set->data, nregs * sizeof (int));
661 if (loop_dump_stream)
663 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
664 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
666 fprintf (loop_dump_stream, "Continue at insn %d.\n",
667 INSN_UID (loop->cont));
670 /* Scan through the loop finding insns that are safe to move.
671 Set regs->set_in_loop negative for the reg being set, so that
672 this reg will be considered invariant for subsequent insns.
673 We consider whether subsequent insns use the reg
674 in deciding whether it is worth actually moving.
676 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
677 and therefore it is possible that the insns we are scanning
678 would never be executed. At such times, we must make sure
679 that it is safe to execute the insn once instead of zero times.
680 When MAYBE_NEVER is 0, all insns will be executed at least once
681 so that is not a problem. */
683 for (p = next_insn_in_loop (loop, loop->scan_start);
685 p = next_insn_in_loop (loop, p))
687 if (GET_CODE (p) == INSN
688 && (set = single_set (p))
689 && GET_CODE (SET_DEST (set)) == REG
690 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
695 rtx src = SET_SRC (set);
696 rtx dependencies = 0;
698 /* Figure out what to use as a source of this insn. If a REG_EQUIV
699 note is given or if a REG_EQUAL note with a constant operand is
700 specified, use it as the source and mark that we should move
701 this insn by calling emit_move_insn rather that duplicating the
704 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
706 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
708 src = XEXP (temp, 0), move_insn = 1;
711 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
712 if (temp && CONSTANT_P (XEXP (temp, 0)))
713 src = XEXP (temp, 0), move_insn = 1;
714 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
716 src = XEXP (temp, 0);
717 /* A libcall block can use regs that don't appear in
718 the equivalent expression. To move the libcall,
719 we must move those regs too. */
720 dependencies = libcall_other_reg (p, src);
724 /* Don't try to optimize a register that was made
725 by loop-optimization for an inner loop.
726 We don't know its life-span, so we can't compute the benefit. */
727 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
729 else if (/* The register is used in basic blocks other
730 than the one where it is set (meaning that
731 something after this point in the loop might
732 depend on its value before the set). */
733 ! reg_in_basic_block_p (p, SET_DEST (set))
734 /* And the set is not guaranteed to be executed one
735 the loop starts, or the value before the set is
736 needed before the set occurs...
738 ??? Note we have quadratic behaviour here, mitigated
739 by the fact that the previous test will often fail for
740 large loops. Rather than re-scanning the entire loop
741 each time for register usage, we should build tables
742 of the register usage and use them here instead. */
744 || loop_reg_used_before_p (loop, set, p)))
745 /* It is unsafe to move the set.
747 This code used to consider it OK to move a set of a variable
748 which was not created by the user and not used in an exit test.
749 That behavior is incorrect and was removed. */
751 else if ((tem = loop_invariant_p (loop, src))
752 && (dependencies == 0
753 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
754 && (VARRAY_INT (regs->set_in_loop,
755 REGNO (SET_DEST (set))) == 1
757 = consec_sets_invariant_p
758 (loop, SET_DEST (set),
759 VARRAY_INT (regs->set_in_loop,
760 REGNO (SET_DEST (set))),
762 /* If the insn can cause a trap (such as divide by zero),
763 can't move it unless it's guaranteed to be executed
764 once loop is entered. Even a function call might
765 prevent the trap insn from being reached
766 (since it might exit!) */
767 && ! ((maybe_never || call_passed)
768 && may_trap_p (src)))
770 register struct movable *m;
771 register int regno = REGNO (SET_DEST (set));
773 /* A potential lossage is where we have a case where two insns
774 can be combined as long as they are both in the loop, but
775 we move one of them outside the loop. For large loops,
776 this can lose. The most common case of this is the address
777 of a function being called.
779 Therefore, if this register is marked as being used exactly
780 once if we are in a loop with calls (a "large loop"), see if
781 we can replace the usage of this register with the source
782 of this SET. If we can, delete this insn.
784 Don't do this if P has a REG_RETVAL note or if we have
785 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
787 if (loop_info->has_call
788 && VARRAY_RTX (regs->single_usage, regno) != 0
789 && VARRAY_RTX (regs->single_usage, regno) != const0_rtx
790 && REGNO_FIRST_UID (regno) == INSN_UID (p)
791 && (REGNO_LAST_UID (regno)
792 == INSN_UID (VARRAY_RTX (regs->single_usage, regno)))
793 && VARRAY_INT (regs->set_in_loop, regno) == 1
794 && ! side_effects_p (SET_SRC (set))
795 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
796 && (! SMALL_REGISTER_CLASSES
797 || (! (GET_CODE (SET_SRC (set)) == REG
798 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
799 /* This test is not redundant; SET_SRC (set) might be
800 a call-clobbered register and the life of REGNO
801 might span a call. */
802 && ! modified_between_p (SET_SRC (set), p,
804 (regs->single_usage, regno))
805 && no_labels_between_p (p, VARRAY_RTX (regs->single_usage,
807 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
809 (regs->single_usage, regno)))
811 /* Replace any usage in a REG_EQUAL note. Must copy the
812 new source, so that we don't get rtx sharing between the
813 SET_SOURCE and REG_NOTES of insn p. */
814 REG_NOTES (VARRAY_RTX (regs->single_usage, regno))
815 = replace_rtx (REG_NOTES (VARRAY_RTX
816 (regs->single_usage, regno)),
817 SET_DEST (set), copy_rtx (SET_SRC (set)));
820 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
821 NOTE_SOURCE_FILE (p) = 0;
822 VARRAY_INT (regs->set_in_loop, regno) = 0;
826 m = (struct movable *) xmalloc (sizeof (struct movable));
830 m->dependencies = dependencies;
831 m->set_dest = SET_DEST (set);
833 m->consec = VARRAY_INT (regs->set_in_loop,
834 REGNO (SET_DEST (set))) - 1;
838 m->move_insn = move_insn;
839 m->move_insn_first = 0;
840 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
841 m->savemode = VOIDmode;
843 /* Set M->cond if either loop_invariant_p
844 or consec_sets_invariant_p returned 2
845 (only conditionally invariant). */
846 m->cond = ((tem | tem1 | tem2) > 1);
847 m->global = LOOP_REG_GLOBAL_P (loop, regno);
849 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
850 m->savings = VARRAY_INT (regs->n_times_set, regno);
851 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
852 m->savings += libcall_benefit (p);
853 VARRAY_INT (regs->set_in_loop, regno) = move_insn ? -2 : -1;
854 /* Add M to the end of the chain MOVABLES. */
855 loop_movables_add (movables, m);
859 /* It is possible for the first instruction to have a
860 REG_EQUAL note but a non-invariant SET_SRC, so we must
861 remember the status of the first instruction in case
862 the last instruction doesn't have a REG_EQUAL note. */
863 m->move_insn_first = m->move_insn;
865 /* Skip this insn, not checking REG_LIBCALL notes. */
866 p = next_nonnote_insn (p);
867 /* Skip the consecutive insns, if there are any. */
868 p = skip_consec_insns (p, m->consec);
869 /* Back up to the last insn of the consecutive group. */
870 p = prev_nonnote_insn (p);
872 /* We must now reset m->move_insn, m->is_equiv, and possibly
873 m->set_src to correspond to the effects of all the
875 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
877 m->set_src = XEXP (temp, 0), m->move_insn = 1;
880 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
881 if (temp && CONSTANT_P (XEXP (temp, 0)))
882 m->set_src = XEXP (temp, 0), m->move_insn = 1;
887 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
890 /* If this register is always set within a STRICT_LOW_PART
891 or set to zero, then its high bytes are constant.
892 So clear them outside the loop and within the loop
893 just load the low bytes.
894 We must check that the machine has an instruction to do so.
895 Also, if the value loaded into the register
896 depends on the same register, this cannot be done. */
897 else if (SET_SRC (set) == const0_rtx
898 && GET_CODE (NEXT_INSN (p)) == INSN
899 && (set1 = single_set (NEXT_INSN (p)))
900 && GET_CODE (set1) == SET
901 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
902 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
903 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
905 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
907 register int regno = REGNO (SET_DEST (set));
908 if (VARRAY_INT (regs->set_in_loop, regno) == 2)
910 register struct movable *m;
911 m = (struct movable *) alloca (sizeof (struct movable));
914 m->set_dest = SET_DEST (set);
921 m->move_insn_first = 0;
923 /* If the insn may not be executed on some cycles,
924 we can't clear the whole reg; clear just high part.
925 Not even if the reg is used only within this loop.
932 Clearing x before the inner loop could clobber a value
933 being saved from the last time around the outer loop.
934 However, if the reg is not used outside this loop
935 and all uses of the register are in the same
936 basic block as the store, there is no problem.
938 If this insn was made by loop, we don't know its
939 INSN_LUID and hence must make a conservative
941 m->global = (INSN_UID (p) >= max_uid_for_loop
942 || LOOP_REG_GLOBAL_P (loop, regno)
943 || (labels_in_range_p
944 (p, REGNO_FIRST_LUID (regno))));
945 if (maybe_never && m->global)
946 m->savemode = GET_MODE (SET_SRC (set1));
948 m->savemode = VOIDmode;
952 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
954 VARRAY_INT (regs->set_in_loop, regno) = -1;
955 /* Add M to the end of the chain MOVABLES. */
956 loop_movables_add (movables, m);
960 /* Past a call insn, we get to insns which might not be executed
961 because the call might exit. This matters for insns that trap.
962 Constant and pure call insns always return, so they don't count. */
963 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
965 /* Past a label or a jump, we get to insns for which we
966 can't count on whether or how many times they will be
967 executed during each iteration. Therefore, we can
968 only move out sets of trivial variables
969 (those not used after the loop). */
970 /* Similar code appears twice in strength_reduce. */
971 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
972 /* If we enter the loop in the middle, and scan around to the
973 beginning, don't set maybe_never for that. This must be an
974 unconditional jump, otherwise the code at the top of the
975 loop might never be executed. Unconditional jumps are
976 followed a by barrier then loop end. */
977 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
978 && NEXT_INSN (NEXT_INSN (p)) == loop_end
979 && any_uncondjump_p (p)))
981 else if (GET_CODE (p) == NOTE)
983 /* At the virtual top of a converted loop, insns are again known to
984 be executed: logically, the loop begins here even though the exit
985 code has been duplicated. */
986 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
987 maybe_never = call_passed = 0;
988 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
990 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
995 /* If one movable subsumes another, ignore that other. */
997 ignore_some_movables (movables);
999 /* For each movable insn, see if the reg that it loads
1000 leads when it dies right into another conditionally movable insn.
1001 If so, record that the second insn "forces" the first one,
1002 since the second can be moved only if the first is. */
1004 force_movables (movables);
1006 /* See if there are multiple movable insns that load the same value.
1007 If there are, make all but the first point at the first one
1008 through the `match' field, and add the priorities of them
1009 all together as the priority of the first. */
1011 combine_movables (movables, regs);
1013 /* Now consider each movable insn to decide whether it is worth moving.
1014 Store 0 in regs->set_in_loop for each reg that is moved.
1016 Generally this increases code size, so do not move moveables when
1017 optimizing for code size. */
1019 if (! optimize_size)
1020 move_movables (loop, movables, threshold, insn_count);
1022 /* Now candidates that still are negative are those not moved.
1023 Change regs->set_in_loop to indicate that those are not actually
1025 for (i = 0; i < nregs; i++)
1026 if (VARRAY_INT (regs->set_in_loop, i) < 0)
1027 VARRAY_INT (regs->set_in_loop, i) = VARRAY_INT (regs->n_times_set, i);
1029 /* Now that we've moved some things out of the loop, we might be able to
1030 hoist even more memory references. */
1031 load_mems_and_recount_loop_regs_set (loop, &insn_count);
1033 for (update_start = loop_start;
1034 PREV_INSN (update_start)
1035 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
1036 update_start = PREV_INSN (update_start))
1038 update_end = NEXT_INSN (loop_end);
1040 reg_scan_update (update_start, update_end, loop_max_reg);
1041 loop_max_reg = max_reg_num ();
1043 if (flag_strength_reduce)
1045 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1046 /* Ensure our label doesn't go away. */
1047 LABEL_NUSES (update_end)++;
1049 strength_reduce (loop, insn_count, flags);
1051 reg_scan_update (update_start, update_end, loop_max_reg);
1052 loop_max_reg = max_reg_num ();
1054 if (update_end && GET_CODE (update_end) == CODE_LABEL
1055 && --LABEL_NUSES (update_end) == 0)
1056 delete_insn (update_end);
1060 /* The movable information is required for strength reduction. */
1061 loop_movables_free (movables);
1063 VARRAY_FREE (regs->single_usage);
1064 VARRAY_FREE (regs->set_in_loop);
1065 VARRAY_FREE (regs->n_times_set);
1066 VARRAY_FREE (regs->may_not_optimize);
1069 /* Add elements to *OUTPUT to record all the pseudo-regs
1070 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1073 record_excess_regs (in_this, not_in_this, output)
1074 rtx in_this, not_in_this;
1081 code = GET_CODE (in_this);
1095 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1096 && ! reg_mentioned_p (in_this, not_in_this))
1097 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1104 fmt = GET_RTX_FORMAT (code);
1105 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1112 for (j = 0; j < XVECLEN (in_this, i); j++)
1113 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1117 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1123 /* Check what regs are referred to in the libcall block ending with INSN,
1124 aside from those mentioned in the equivalent value.
1125 If there are none, return 0.
1126 If there are one or more, return an EXPR_LIST containing all of them. */
1129 libcall_other_reg (insn, equiv)
1132 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1133 rtx p = XEXP (note, 0);
1136 /* First, find all the regs used in the libcall block
1137 that are not mentioned as inputs to the result. */
1141 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1142 || GET_CODE (p) == CALL_INSN)
1143 record_excess_regs (PATTERN (p), equiv, &output);
1150 /* Return 1 if all uses of REG
1151 are between INSN and the end of the basic block. */
1154 reg_in_basic_block_p (insn, reg)
1157 int regno = REGNO (reg);
1160 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1163 /* Search this basic block for the already recorded last use of the reg. */
1164 for (p = insn; p; p = NEXT_INSN (p))
1166 switch (GET_CODE (p))
1173 /* Ordinary insn: if this is the last use, we win. */
1174 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1179 /* Jump insn: if this is the last use, we win. */
1180 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1182 /* Otherwise, it's the end of the basic block, so we lose. */
1187 /* It's the end of the basic block, so we lose. */
1195 /* The "last use" that was recorded can't be found after the first
1196 use. This can happen when the last use was deleted while
1197 processing an inner loop, this inner loop was then completely
1198 unrolled, and the outer loop is always exited after the inner loop,
1199 so that everything after the first use becomes a single basic block. */
1203 /* Compute the benefit of eliminating the insns in the block whose
1204 last insn is LAST. This may be a group of insns used to compute a
1205 value directly or can contain a library call. */
1208 libcall_benefit (last)
1214 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1215 insn != last; insn = NEXT_INSN (insn))
1217 if (GET_CODE (insn) == CALL_INSN)
1218 benefit += 10; /* Assume at least this many insns in a library
1220 else if (GET_CODE (insn) == INSN
1221 && GET_CODE (PATTERN (insn)) != USE
1222 && GET_CODE (PATTERN (insn)) != CLOBBER)
1229 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1232 skip_consec_insns (insn, count)
1236 for (; count > 0; count--)
1240 /* If first insn of libcall sequence, skip to end. */
1241 /* Do this at start of loop, since INSN is guaranteed to
1243 if (GET_CODE (insn) != NOTE
1244 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1245 insn = XEXP (temp, 0);
1248 insn = NEXT_INSN (insn);
1249 while (GET_CODE (insn) == NOTE);
1255 /* Ignore any movable whose insn falls within a libcall
1256 which is part of another movable.
1257 We make use of the fact that the movable for the libcall value
1258 was made later and so appears later on the chain. */
1261 ignore_some_movables (movables)
1262 struct loop_movables *movables;
1264 register struct movable *m, *m1;
1266 for (m = movables->head; m; m = m->next)
1268 /* Is this a movable for the value of a libcall? */
1269 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1273 /* Check for earlier movables inside that range,
1274 and mark them invalid. We cannot use LUIDs here because
1275 insns created by loop.c for prior loops don't have LUIDs.
1276 Rather than reject all such insns from movables, we just
1277 explicitly check each insn in the libcall (since invariant
1278 libcalls aren't that common). */
1279 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1280 for (m1 = movables->head; m1 != m; m1 = m1->next)
1281 if (m1->insn == insn)
1287 /* For each movable insn, see if the reg that it loads
1288 leads when it dies right into another conditionally movable insn.
1289 If so, record that the second insn "forces" the first one,
1290 since the second can be moved only if the first is. */
1293 force_movables (movables)
1294 struct loop_movables *movables;
1296 register struct movable *m, *m1;
1297 for (m1 = movables->head; m1; m1 = m1->next)
1298 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1299 if (!m1->partial && !m1->done)
1301 int regno = m1->regno;
1302 for (m = m1->next; m; m = m->next)
1303 /* ??? Could this be a bug? What if CSE caused the
1304 register of M1 to be used after this insn?
1305 Since CSE does not update regno_last_uid,
1306 this insn M->insn might not be where it dies.
1307 But very likely this doesn't matter; what matters is
1308 that M's reg is computed from M1's reg. */
1309 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1312 if (m != 0 && m->set_src == m1->set_dest
1313 /* If m->consec, m->set_src isn't valid. */
1317 /* Increase the priority of the moving the first insn
1318 since it permits the second to be moved as well. */
1322 m1->lifetime += m->lifetime;
1323 m1->savings += m->savings;
1328 /* Find invariant expressions that are equal and can be combined into
1332 combine_movables (movables, regs)
1333 struct loop_movables *movables;
1334 struct loop_regs *regs;
1336 register struct movable *m;
1337 char *matched_regs = (char *) xmalloc (regs->num);
1338 enum machine_mode mode;
1340 /* Regs that are set more than once are not allowed to match
1341 or be matched. I'm no longer sure why not. */
1342 /* Perhaps testing m->consec_sets would be more appropriate here? */
1344 for (m = movables->head; m; m = m->next)
1345 if (m->match == 0 && VARRAY_INT (regs->n_times_set, m->regno) == 1
1348 register struct movable *m1;
1349 int regno = m->regno;
1351 memset (matched_regs, 0, regs->num);
1352 matched_regs[regno] = 1;
1354 /* We want later insns to match the first one. Don't make the first
1355 one match any later ones. So start this loop at m->next. */
1356 for (m1 = m->next; m1; m1 = m1->next)
1357 if (m != m1 && m1->match == 0 && VARRAY_INT (regs->n_times_set,
1359 /* A reg used outside the loop mustn't be eliminated. */
1361 /* A reg used for zero-extending mustn't be eliminated. */
1363 && (matched_regs[m1->regno]
1366 /* Can combine regs with different modes loaded from the
1367 same constant only if the modes are the same or
1368 if both are integer modes with M wider or the same
1369 width as M1. The check for integer is redundant, but
1370 safe, since the only case of differing destination
1371 modes with equal sources is when both sources are
1372 VOIDmode, i.e., CONST_INT. */
1373 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1374 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1375 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1376 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1377 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1378 /* See if the source of M1 says it matches M. */
1379 && ((GET_CODE (m1->set_src) == REG
1380 && matched_regs[REGNO (m1->set_src)])
1381 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1383 && ((m->dependencies == m1->dependencies)
1384 || rtx_equal_p (m->dependencies, m1->dependencies)))
1386 m->lifetime += m1->lifetime;
1387 m->savings += m1->savings;
1390 matched_regs[m1->regno] = 1;
1394 /* Now combine the regs used for zero-extension.
1395 This can be done for those not marked `global'
1396 provided their lives don't overlap. */
1398 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1399 mode = GET_MODE_WIDER_MODE (mode))
1401 register struct movable *m0 = 0;
1403 /* Combine all the registers for extension from mode MODE.
1404 Don't combine any that are used outside this loop. */
1405 for (m = movables->head; m; m = m->next)
1406 if (m->partial && ! m->global
1407 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1409 register struct movable *m1;
1410 int first = REGNO_FIRST_LUID (m->regno);
1411 int last = REGNO_LAST_LUID (m->regno);
1415 /* First one: don't check for overlap, just record it. */
1420 /* Make sure they extend to the same mode.
1421 (Almost always true.) */
1422 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1425 /* We already have one: check for overlap with those
1426 already combined together. */
1427 for (m1 = movables->head; m1 != m; m1 = m1->next)
1428 if (m1 == m0 || (m1->partial && m1->match == m0))
1429 if (! (REGNO_FIRST_LUID (m1->regno) > last
1430 || REGNO_LAST_LUID (m1->regno) < first))
1433 /* No overlap: we can combine this with the others. */
1434 m0->lifetime += m->lifetime;
1435 m0->savings += m->savings;
1445 free (matched_regs);
1448 /* Return 1 if regs X and Y will become the same if moved. */
1451 regs_match_p (x, y, movables)
1453 struct loop_movables *movables;
1455 unsigned int xn = REGNO (x);
1456 unsigned int yn = REGNO (y);
1457 struct movable *mx, *my;
1459 for (mx = movables->head; mx; mx = mx->next)
1460 if (mx->regno == xn)
1463 for (my = movables->head; my; my = my->next)
1464 if (my->regno == yn)
1468 && ((mx->match == my->match && mx->match != 0)
1470 || mx == my->match));
1473 /* Return 1 if X and Y are identical-looking rtx's.
1474 This is the Lisp function EQUAL for rtx arguments.
1476 If two registers are matching movables or a movable register and an
1477 equivalent constant, consider them equal. */
1480 rtx_equal_for_loop_p (x, y, movables, regs)
1482 struct loop_movables *movables;
1483 struct loop_regs *regs;
1487 register struct movable *m;
1488 register enum rtx_code code;
1489 register const char *fmt;
1493 if (x == 0 || y == 0)
1496 code = GET_CODE (x);
1498 /* If we have a register and a constant, they may sometimes be
1500 if (GET_CODE (x) == REG && VARRAY_INT (regs->set_in_loop, REGNO (x)) == -2
1503 for (m = movables->head; m; m = m->next)
1504 if (m->move_insn && m->regno == REGNO (x)
1505 && rtx_equal_p (m->set_src, y))
1508 else if (GET_CODE (y) == REG && VARRAY_INT (regs->set_in_loop,
1512 for (m = movables->head; m; m = m->next)
1513 if (m->move_insn && m->regno == REGNO (y)
1514 && rtx_equal_p (m->set_src, x))
1518 /* Otherwise, rtx's of different codes cannot be equal. */
1519 if (code != GET_CODE (y))
1522 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1523 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1525 if (GET_MODE (x) != GET_MODE (y))
1528 /* These three types of rtx's can be compared nonrecursively. */
1530 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1532 if (code == LABEL_REF)
1533 return XEXP (x, 0) == XEXP (y, 0);
1534 if (code == SYMBOL_REF)
1535 return XSTR (x, 0) == XSTR (y, 0);
1537 /* Compare the elements. If any pair of corresponding elements
1538 fail to match, return 0 for the whole things. */
1540 fmt = GET_RTX_FORMAT (code);
1541 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1546 if (XWINT (x, i) != XWINT (y, i))
1551 if (XINT (x, i) != XINT (y, i))
1556 /* Two vectors must have the same length. */
1557 if (XVECLEN (x, i) != XVECLEN (y, i))
1560 /* And the corresponding elements must match. */
1561 for (j = 0; j < XVECLEN (x, i); j++)
1562 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1563 movables, regs) == 0)
1568 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1574 if (strcmp (XSTR (x, i), XSTR (y, i)))
1579 /* These are just backpointers, so they don't matter. */
1585 /* It is believed that rtx's at this level will never
1586 contain anything but integers and other rtx's,
1587 except for within LABEL_REFs and SYMBOL_REFs. */
1595 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1596 insns in INSNS which use the reference. */
1599 add_label_notes (x, insns)
1603 enum rtx_code code = GET_CODE (x);
1608 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1610 /* This code used to ignore labels that referred to dispatch tables to
1611 avoid flow generating (slighly) worse code.
1613 We no longer ignore such label references (see LABEL_REF handling in
1614 mark_jump_label for additional information). */
1615 for (insn = insns; insn; insn = NEXT_INSN (insn))
1616 if (reg_mentioned_p (XEXP (x, 0), insn))
1617 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1621 fmt = GET_RTX_FORMAT (code);
1622 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1625 add_label_notes (XEXP (x, i), insns);
1626 else if (fmt[i] == 'E')
1627 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1628 add_label_notes (XVECEXP (x, i, j), insns);
1632 /* Scan MOVABLES, and move the insns that deserve to be moved.
1633 If two matching movables are combined, replace one reg with the
1634 other throughout. */
1637 move_movables (loop, movables, threshold, insn_count)
1639 struct loop_movables *movables;
1643 struct loop_regs *regs = LOOP_REGS (loop);
1644 int nregs = regs->num;
1646 register struct movable *m;
1648 rtx loop_start = loop->start;
1649 rtx loop_end = loop->end;
1650 /* Map of pseudo-register replacements to handle combining
1651 when we move several insns that load the same value
1652 into different pseudo-registers. */
1653 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1654 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1658 for (m = movables->head; m; m = m->next)
1660 /* Describe this movable insn. */
1662 if (loop_dump_stream)
1664 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1665 INSN_UID (m->insn), m->regno, m->lifetime);
1667 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1669 fprintf (loop_dump_stream, "cond ");
1671 fprintf (loop_dump_stream, "force ");
1673 fprintf (loop_dump_stream, "global ");
1675 fprintf (loop_dump_stream, "done ");
1677 fprintf (loop_dump_stream, "move-insn ");
1679 fprintf (loop_dump_stream, "matches %d ",
1680 INSN_UID (m->match->insn));
1682 fprintf (loop_dump_stream, "forces %d ",
1683 INSN_UID (m->forces->insn));
1686 /* Count movables. Value used in heuristics in strength_reduce. */
1689 /* Ignore the insn if it's already done (it matched something else).
1690 Otherwise, see if it is now safe to move. */
1694 || (1 == loop_invariant_p (loop, m->set_src)
1695 && (m->dependencies == 0
1696 || 1 == loop_invariant_p (loop, m->dependencies))
1698 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1701 && (! m->forces || m->forces->done))
1705 int savings = m->savings;
1707 /* We have an insn that is safe to move.
1708 Compute its desirability. */
1713 if (loop_dump_stream)
1714 fprintf (loop_dump_stream, "savings %d ", savings);
1716 if (regs->moved_once[regno] && loop_dump_stream)
1717 fprintf (loop_dump_stream, "halved since already moved ");
1719 /* An insn MUST be moved if we already moved something else
1720 which is safe only if this one is moved too: that is,
1721 if already_moved[REGNO] is nonzero. */
1723 /* An insn is desirable to move if the new lifetime of the
1724 register is no more than THRESHOLD times the old lifetime.
1725 If it's not desirable, it means the loop is so big
1726 that moving won't speed things up much,
1727 and it is liable to make register usage worse. */
1729 /* It is also desirable to move if it can be moved at no
1730 extra cost because something else was already moved. */
1732 if (already_moved[regno]
1733 || flag_move_all_movables
1734 || (threshold * savings * m->lifetime) >=
1735 (regs->moved_once[regno] ? insn_count * 2 : insn_count)
1736 || (m->forces && m->forces->done
1737 && VARRAY_INT (regs->n_times_set, m->forces->regno) == 1))
1740 register struct movable *m1;
1741 rtx first = NULL_RTX;
1743 /* Now move the insns that set the reg. */
1745 if (m->partial && m->match)
1749 /* Find the end of this chain of matching regs.
1750 Thus, we load each reg in the chain from that one reg.
1751 And that reg is loaded with 0 directly,
1752 since it has ->match == 0. */
1753 for (m1 = m; m1->match; m1 = m1->match);
1754 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1755 SET_DEST (PATTERN (m1->insn)));
1756 i1 = emit_insn_before (newpat, loop_start);
1758 /* Mark the moved, invariant reg as being allowed to
1759 share a hard reg with the other matching invariant. */
1760 REG_NOTES (i1) = REG_NOTES (m->insn);
1761 r1 = SET_DEST (PATTERN (m->insn));
1762 r2 = SET_DEST (PATTERN (m1->insn));
1764 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1765 gen_rtx_EXPR_LIST (VOIDmode, r2,
1767 delete_insn (m->insn);
1772 if (loop_dump_stream)
1773 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1775 /* If we are to re-generate the item being moved with a
1776 new move insn, first delete what we have and then emit
1777 the move insn before the loop. */
1778 else if (m->move_insn)
1782 for (count = m->consec; count >= 0; count--)
1784 /* If this is the first insn of a library call sequence,
1786 if (GET_CODE (p) != NOTE
1787 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1790 /* If this is the last insn of a libcall sequence, then
1791 delete every insn in the sequence except the last.
1792 The last insn is handled in the normal manner. */
1793 if (GET_CODE (p) != NOTE
1794 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1796 temp = XEXP (temp, 0);
1798 temp = delete_insn (temp);
1802 p = delete_insn (p);
1804 /* simplify_giv_expr expects that it can walk the insns
1805 at m->insn forwards and see this old sequence we are
1806 tossing here. delete_insn does preserve the next
1807 pointers, but when we skip over a NOTE we must fix
1808 it up. Otherwise that code walks into the non-deleted
1810 while (p && GET_CODE (p) == NOTE)
1811 p = NEXT_INSN (temp) = NEXT_INSN (p);
1815 emit_move_insn (m->set_dest, m->set_src);
1816 temp = get_insns ();
1819 add_label_notes (m->set_src, temp);
1821 i1 = emit_insns_before (temp, loop_start);
1822 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1824 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1825 m->set_src, REG_NOTES (i1));
1827 if (loop_dump_stream)
1828 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1830 /* The more regs we move, the less we like moving them. */
1835 for (count = m->consec; count >= 0; count--)
1839 /* If first insn of libcall sequence, skip to end. */
1840 /* Do this at start of loop, since p is guaranteed to
1842 if (GET_CODE (p) != NOTE
1843 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1846 /* If last insn of libcall sequence, move all
1847 insns except the last before the loop. The last
1848 insn is handled in the normal manner. */
1849 if (GET_CODE (p) != NOTE
1850 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1854 rtx fn_address_insn = 0;
1857 for (temp = XEXP (temp, 0); temp != p;
1858 temp = NEXT_INSN (temp))
1864 if (GET_CODE (temp) == NOTE)
1867 body = PATTERN (temp);
1869 /* Find the next insn after TEMP,
1870 not counting USE or NOTE insns. */
1871 for (next = NEXT_INSN (temp); next != p;
1872 next = NEXT_INSN (next))
1873 if (! (GET_CODE (next) == INSN
1874 && GET_CODE (PATTERN (next)) == USE)
1875 && GET_CODE (next) != NOTE)
1878 /* If that is the call, this may be the insn
1879 that loads the function address.
1881 Extract the function address from the insn
1882 that loads it into a register.
1883 If this insn was cse'd, we get incorrect code.
1885 So emit a new move insn that copies the
1886 function address into the register that the
1887 call insn will use. flow.c will delete any
1888 redundant stores that we have created. */
1889 if (GET_CODE (next) == CALL_INSN
1890 && GET_CODE (body) == SET
1891 && GET_CODE (SET_DEST (body)) == REG
1892 && (n = find_reg_note (temp, REG_EQUAL,
1895 fn_reg = SET_SRC (body);
1896 if (GET_CODE (fn_reg) != REG)
1897 fn_reg = SET_DEST (body);
1898 fn_address = XEXP (n, 0);
1899 fn_address_insn = temp;
1901 /* We have the call insn.
1902 If it uses the register we suspect it might,
1903 load it with the correct address directly. */
1904 if (GET_CODE (temp) == CALL_INSN
1906 && reg_referenced_p (fn_reg, body))
1907 emit_insn_after (gen_move_insn (fn_reg,
1911 if (GET_CODE (temp) == CALL_INSN)
1913 i1 = emit_call_insn_before (body, loop_start);
1914 /* Because the USAGE information potentially
1915 contains objects other than hard registers
1916 we need to copy it. */
1917 if (CALL_INSN_FUNCTION_USAGE (temp))
1918 CALL_INSN_FUNCTION_USAGE (i1)
1919 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1922 i1 = emit_insn_before (body, loop_start);
1925 if (temp == fn_address_insn)
1926 fn_address_insn = i1;
1927 REG_NOTES (i1) = REG_NOTES (temp);
1933 if (m->savemode != VOIDmode)
1935 /* P sets REG to zero; but we should clear only
1936 the bits that are not covered by the mode
1938 rtx reg = m->set_dest;
1944 (GET_MODE (reg), and_optab, reg,
1945 GEN_INT ((((HOST_WIDE_INT) 1
1946 << GET_MODE_BITSIZE (m->savemode)))
1948 reg, 1, OPTAB_LIB_WIDEN);
1952 emit_move_insn (reg, tem);
1953 sequence = gen_sequence ();
1955 i1 = emit_insn_before (sequence, loop_start);
1957 else if (GET_CODE (p) == CALL_INSN)
1959 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1960 /* Because the USAGE information potentially
1961 contains objects other than hard registers
1962 we need to copy it. */
1963 if (CALL_INSN_FUNCTION_USAGE (p))
1964 CALL_INSN_FUNCTION_USAGE (i1)
1965 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1967 else if (count == m->consec && m->move_insn_first)
1969 /* The SET_SRC might not be invariant, so we must
1970 use the REG_EQUAL note. */
1972 emit_move_insn (m->set_dest, m->set_src);
1973 temp = get_insns ();
1976 add_label_notes (m->set_src, temp);
1978 i1 = emit_insns_before (temp, loop_start);
1979 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1981 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1983 m->set_src, REG_NOTES (i1));
1986 i1 = emit_insn_before (PATTERN (p), loop_start);
1988 if (REG_NOTES (i1) == 0)
1990 REG_NOTES (i1) = REG_NOTES (p);
1992 /* If there is a REG_EQUAL note present whose value
1993 is not loop invariant, then delete it, since it
1994 may cause problems with later optimization passes.
1995 It is possible for cse to create such notes
1996 like this as a result of record_jump_cond. */
1998 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
1999 && ! loop_invariant_p (loop, XEXP (temp, 0)))
2000 remove_note (i1, temp);
2006 if (loop_dump_stream)
2007 fprintf (loop_dump_stream, " moved to %d",
2010 /* If library call, now fix the REG_NOTES that contain
2011 insn pointers, namely REG_LIBCALL on FIRST
2012 and REG_RETVAL on I1. */
2013 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2015 XEXP (temp, 0) = first;
2016 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2017 XEXP (temp, 0) = i1;
2024 /* simplify_giv_expr expects that it can walk the insns
2025 at m->insn forwards and see this old sequence we are
2026 tossing here. delete_insn does preserve the next
2027 pointers, but when we skip over a NOTE we must fix
2028 it up. Otherwise that code walks into the non-deleted
2030 while (p && GET_CODE (p) == NOTE)
2031 p = NEXT_INSN (temp) = NEXT_INSN (p);
2034 /* The more regs we move, the less we like moving them. */
2038 /* Any other movable that loads the same register
2040 already_moved[regno] = 1;
2042 /* This reg has been moved out of one loop. */
2043 regs->moved_once[regno] = 1;
2045 /* The reg set here is now invariant. */
2047 VARRAY_INT (regs->set_in_loop, regno) = 0;
2051 /* Change the length-of-life info for the register
2052 to say it lives at least the full length of this loop.
2053 This will help guide optimizations in outer loops. */
2055 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2056 /* This is the old insn before all the moved insns.
2057 We can't use the moved insn because it is out of range
2058 in uid_luid. Only the old insns have luids. */
2059 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2060 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2061 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2063 /* Combine with this moved insn any other matching movables. */
2066 for (m1 = movables->head; m1; m1 = m1->next)
2071 /* Schedule the reg loaded by M1
2072 for replacement so that shares the reg of M.
2073 If the modes differ (only possible in restricted
2074 circumstances, make a SUBREG.
2076 Note this assumes that the target dependent files
2077 treat REG and SUBREG equally, including within
2078 GO_IF_LEGITIMATE_ADDRESS and in all the
2079 predicates since we never verify that replacing the
2080 original register with a SUBREG results in a
2081 recognizable insn. */
2082 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2083 reg_map[m1->regno] = m->set_dest;
2086 = gen_lowpart_common (GET_MODE (m1->set_dest),
2089 /* Get rid of the matching insn
2090 and prevent further processing of it. */
2093 /* if library call, delete all insn except last, which
2095 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2098 for (temp = XEXP (temp, 0); temp != m1->insn;
2099 temp = NEXT_INSN (temp))
2102 delete_insn (m1->insn);
2104 /* Any other movable that loads the same register
2106 already_moved[m1->regno] = 1;
2108 /* The reg merged here is now invariant,
2109 if the reg it matches is invariant. */
2111 VARRAY_INT (regs->set_in_loop, m1->regno) = 0;
2114 else if (loop_dump_stream)
2115 fprintf (loop_dump_stream, "not desirable");
2117 else if (loop_dump_stream && !m->match)
2118 fprintf (loop_dump_stream, "not safe");
2120 if (loop_dump_stream)
2121 fprintf (loop_dump_stream, "\n");
2125 new_start = loop_start;
2127 /* Go through all the instructions in the loop, making
2128 all the register substitutions scheduled in REG_MAP. */
2129 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2130 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2131 || GET_CODE (p) == CALL_INSN)
2133 replace_regs (PATTERN (p), reg_map, nregs, 0);
2134 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2140 free (already_moved);
2145 loop_movables_add (movables, m)
2146 struct loop_movables *movables;
2149 if (movables->head == 0)
2152 movables->last->next = m;
2158 loop_movables_free (movables)
2159 struct loop_movables *movables;
2162 struct movable *m_next;
2164 for (m = movables->head; m; m = m_next)
2172 /* Scan X and replace the address of any MEM in it with ADDR.
2173 REG is the address that MEM should have before the replacement. */
2176 replace_call_address (x, reg, addr)
2179 register enum rtx_code code;
2181 register const char *fmt;
2185 code = GET_CODE (x);
2199 /* Short cut for very common case. */
2200 replace_call_address (XEXP (x, 1), reg, addr);
2204 /* Short cut for very common case. */
2205 replace_call_address (XEXP (x, 0), reg, addr);
2209 /* If this MEM uses a reg other than the one we expected,
2210 something is wrong. */
2211 if (XEXP (x, 0) != reg)
2220 fmt = GET_RTX_FORMAT (code);
2221 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2224 replace_call_address (XEXP (x, i), reg, addr);
2225 else if (fmt[i] == 'E')
2228 for (j = 0; j < XVECLEN (x, i); j++)
2229 replace_call_address (XVECEXP (x, i, j), reg, addr);
2235 /* Return the number of memory refs to addresses that vary
2239 count_nonfixed_reads (loop, x)
2240 const struct loop *loop;
2243 register enum rtx_code code;
2245 register const char *fmt;
2251 code = GET_CODE (x);
2265 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2266 + count_nonfixed_reads (loop, XEXP (x, 0)));
2273 fmt = GET_RTX_FORMAT (code);
2274 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2277 value += count_nonfixed_reads (loop, XEXP (x, i));
2281 for (j = 0; j < XVECLEN (x, i); j++)
2282 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2288 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2289 `has_call', `has_volatile', `has_tablejump',
2290 `unknown_address_altered', `unknown_constant_address_altered', and
2291 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2292 list `store_mems' in LOOP. */
2298 register int level = 1;
2300 struct loop_info *loop_info = LOOP_INFO (loop);
2301 rtx start = loop->start;
2302 rtx end = loop->end;
2303 /* The label after END. Jumping here is just like falling off the
2304 end of the loop. We use next_nonnote_insn instead of next_label
2305 as a hedge against the (pathological) case where some actual insn
2306 might end up between the two. */
2307 rtx exit_target = next_nonnote_insn (end);
2309 loop_info->has_indirect_jump = indirect_jump_in_function;
2310 loop_info->pre_header_has_call = 0;
2311 loop_info->has_call = 0;
2312 loop_info->has_volatile = 0;
2313 loop_info->has_tablejump = 0;
2314 loop_info->has_multiple_exit_targets = 0;
2317 loop_info->unknown_address_altered = 0;
2318 loop_info->unknown_constant_address_altered = 0;
2319 loop_info->store_mems = NULL_RTX;
2320 loop_info->first_loop_store_insn = NULL_RTX;
2321 loop_info->mems_idx = 0;
2322 loop_info->num_mem_sets = 0;
2325 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
2326 insn = PREV_INSN (insn))
2328 if (GET_CODE (insn) == CALL_INSN)
2330 loop_info->pre_header_has_call = 1;
2335 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2336 insn = NEXT_INSN (insn))
2338 if (GET_CODE (insn) == NOTE)
2340 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2343 /* Count number of loops contained in this one. */
2346 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2351 else if (GET_CODE (insn) == CALL_INSN)
2353 if (! CONST_CALL_P (insn))
2354 loop_info->unknown_address_altered = 1;
2355 loop_info->has_call = 1;
2357 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2359 rtx label1 = NULL_RTX;
2360 rtx label2 = NULL_RTX;
2362 if (volatile_refs_p (PATTERN (insn)))
2363 loop_info->has_volatile = 1;
2365 if (GET_CODE (insn) == JUMP_INSN
2366 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2367 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2368 loop_info->has_tablejump = 1;
2370 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2371 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2372 loop_info->first_loop_store_insn = insn;
2374 if (! loop_info->has_multiple_exit_targets
2375 && GET_CODE (insn) == JUMP_INSN
2376 && GET_CODE (PATTERN (insn)) == SET
2377 && SET_DEST (PATTERN (insn)) == pc_rtx)
2379 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2381 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2382 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2386 label1 = SET_SRC (PATTERN (insn));
2391 if (label1 && label1 != pc_rtx)
2393 if (GET_CODE (label1) != LABEL_REF)
2395 /* Something tricky. */
2396 loop_info->has_multiple_exit_targets = 1;
2399 else if (XEXP (label1, 0) != exit_target
2400 && LABEL_OUTSIDE_LOOP_P (label1))
2402 /* A jump outside the current loop. */
2403 loop_info->has_multiple_exit_targets = 1;
2414 else if (GET_CODE (insn) == RETURN)
2415 loop_info->has_multiple_exit_targets = 1;
2418 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2419 if (/* An exception thrown by a called function might land us
2421 ! loop_info->has_call
2422 /* We don't want loads for MEMs moved to a location before the
2423 one at which their stack memory becomes allocated. (Note
2424 that this is not a problem for malloc, etc., since those
2425 require actual function calls. */
2426 && ! current_function_calls_alloca
2427 /* There are ways to leave the loop other than falling off the
2429 && ! loop_info->has_multiple_exit_targets)
2430 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2431 insn = NEXT_INSN (insn))
2432 for_each_rtx (&insn, insert_loop_mem, loop_info);
2434 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2435 that loop_invariant_p and load_mems can use true_dependence
2436 to determine what is really clobbered. */
2437 if (loop_info->unknown_address_altered)
2439 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2441 loop_info->store_mems
2442 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2444 if (loop_info->unknown_constant_address_altered)
2446 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2448 RTX_UNCHANGING_P (mem) = 1;
2449 loop_info->store_mems
2450 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2454 /* Scan the function looking for loops. Record the start and end of each loop.
2455 Also mark as invalid loops any loops that contain a setjmp or are branched
2456 to from outside the loop. */
2459 find_and_verify_loops (f, loops)
2461 struct loops *loops;
2466 struct loop *current_loop;
2467 struct loop *next_loop;
2470 num_loops = loops->num;
2472 compute_luids (f, NULL_RTX, 0);
2474 /* If there are jumps to undefined labels,
2475 treat them as jumps out of any/all loops.
2476 This also avoids writing past end of tables when there are no loops. */
2479 /* Find boundaries of loops, mark which loops are contained within
2480 loops, and invalidate loops that have setjmp. */
2483 current_loop = NULL;
2484 for (insn = f; insn; insn = NEXT_INSN (insn))
2486 if (GET_CODE (insn) == NOTE)
2487 switch (NOTE_LINE_NUMBER (insn))
2489 case NOTE_INSN_LOOP_BEG:
2490 next_loop = loops->array + num_loops;
2491 next_loop->num = num_loops;
2493 next_loop->start = insn;
2494 next_loop->outer = current_loop;
2495 current_loop = next_loop;
2498 case NOTE_INSN_SETJMP:
2499 /* In this case, we must invalidate our current loop and any
2501 for (loop = current_loop; loop; loop = loop->outer)
2504 if (loop_dump_stream)
2505 fprintf (loop_dump_stream,
2506 "\nLoop at %d ignored due to setjmp.\n",
2507 INSN_UID (loop->start));
2511 case NOTE_INSN_LOOP_CONT:
2512 current_loop->cont = insn;
2515 case NOTE_INSN_LOOP_VTOP:
2516 current_loop->vtop = insn;
2519 case NOTE_INSN_LOOP_END:
2523 current_loop->end = insn;
2524 current_loop = current_loop->outer;
2531 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2532 enclosing loop, but this doesn't matter. */
2533 uid_loop[INSN_UID (insn)] = current_loop;
2536 /* Any loop containing a label used in an initializer must be invalidated,
2537 because it can be jumped into from anywhere. */
2539 for (label = forced_labels; label; label = XEXP (label, 1))
2541 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2542 loop; loop = loop->outer)
2546 /* Any loop containing a label used for an exception handler must be
2547 invalidated, because it can be jumped into from anywhere. */
2549 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2551 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2552 loop; loop = loop->outer)
2556 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2557 loop that it is not contained within, that loop is marked invalid.
2558 If any INSN or CALL_INSN uses a label's address, then the loop containing
2559 that label is marked invalid, because it could be jumped into from
2562 Also look for blocks of code ending in an unconditional branch that
2563 exits the loop. If such a block is surrounded by a conditional
2564 branch around the block, move the block elsewhere (see below) and
2565 invert the jump to point to the code block. This may eliminate a
2566 label in our loop and will simplify processing by both us and a
2567 possible second cse pass. */
2569 for (insn = f; insn; insn = NEXT_INSN (insn))
2572 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2574 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2576 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2579 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2580 loop; loop = loop->outer)
2585 if (GET_CODE (insn) != JUMP_INSN)
2588 mark_loop_jump (PATTERN (insn), this_loop);
2590 /* See if this is an unconditional branch outside the loop. */
2592 && (GET_CODE (PATTERN (insn)) == RETURN
2593 || (any_uncondjump_p (insn)
2594 && onlyjump_p (insn)
2595 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2597 && get_max_uid () < max_uid_for_loop)
2600 rtx our_next = next_real_insn (insn);
2601 rtx last_insn_to_move = NEXT_INSN (insn);
2602 struct loop *dest_loop;
2603 struct loop *outer_loop = NULL;
2605 /* Go backwards until we reach the start of the loop, a label,
2607 for (p = PREV_INSN (insn);
2608 GET_CODE (p) != CODE_LABEL
2609 && ! (GET_CODE (p) == NOTE
2610 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2611 && GET_CODE (p) != JUMP_INSN;
2615 /* Check for the case where we have a jump to an inner nested
2616 loop, and do not perform the optimization in that case. */
2618 if (JUMP_LABEL (insn))
2620 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2623 for (outer_loop = dest_loop; outer_loop;
2624 outer_loop = outer_loop->outer)
2625 if (outer_loop == this_loop)
2630 /* Make sure that the target of P is within the current loop. */
2632 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2633 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2634 outer_loop = this_loop;
2636 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2637 we have a block of code to try to move.
2639 We look backward and then forward from the target of INSN
2640 to find a BARRIER at the same loop depth as the target.
2641 If we find such a BARRIER, we make a new label for the start
2642 of the block, invert the jump in P and point it to that label,
2643 and move the block of code to the spot we found. */
2646 && GET_CODE (p) == JUMP_INSN
2647 && JUMP_LABEL (p) != 0
2648 /* Just ignore jumps to labels that were never emitted.
2649 These always indicate compilation errors. */
2650 && INSN_UID (JUMP_LABEL (p)) != 0
2651 && any_condjump_p (p) && onlyjump_p (p)
2652 && next_real_insn (JUMP_LABEL (p)) == our_next
2653 /* If it's not safe to move the sequence, then we
2655 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2656 &last_insn_to_move))
2659 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2660 struct loop *target_loop = uid_loop[INSN_UID (target)];
2663 for (loc = target; loc; loc = PREV_INSN (loc))
2664 if (GET_CODE (loc) == BARRIER
2665 /* Don't move things inside a tablejump. */
2666 && ((loc2 = next_nonnote_insn (loc)) == 0
2667 || GET_CODE (loc2) != CODE_LABEL
2668 || (loc2 = next_nonnote_insn (loc2)) == 0
2669 || GET_CODE (loc2) != JUMP_INSN
2670 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2671 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2672 && uid_loop[INSN_UID (loc)] == target_loop)
2676 for (loc = target; loc; loc = NEXT_INSN (loc))
2677 if (GET_CODE (loc) == BARRIER
2678 /* Don't move things inside a tablejump. */
2679 && ((loc2 = next_nonnote_insn (loc)) == 0
2680 || GET_CODE (loc2) != CODE_LABEL
2681 || (loc2 = next_nonnote_insn (loc2)) == 0
2682 || GET_CODE (loc2) != JUMP_INSN
2683 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2684 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2685 && uid_loop[INSN_UID (loc)] == target_loop)
2690 rtx cond_label = JUMP_LABEL (p);
2691 rtx new_label = get_label_after (p);
2693 /* Ensure our label doesn't go away. */
2694 LABEL_NUSES (cond_label)++;
2696 /* Verify that uid_loop is large enough and that
2698 if (invert_jump (p, new_label, 1))
2702 /* If no suitable BARRIER was found, create a suitable
2703 one before TARGET. Since TARGET is a fall through
2704 path, we'll need to insert an jump around our block
2705 and a add a BARRIER before TARGET.
2707 This creates an extra unconditional jump outside
2708 the loop. However, the benefits of removing rarely
2709 executed instructions from inside the loop usually
2710 outweighs the cost of the extra unconditional jump
2711 outside the loop. */
2716 temp = gen_jump (JUMP_LABEL (insn));
2717 temp = emit_jump_insn_before (temp, target);
2718 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2719 LABEL_NUSES (JUMP_LABEL (insn))++;
2720 loc = emit_barrier_before (target);
2723 /* Include the BARRIER after INSN and copy the
2725 new_label = squeeze_notes (new_label,
2727 reorder_insns (new_label, last_insn_to_move, loc);
2729 /* All those insns are now in TARGET_LOOP. */
2731 q != NEXT_INSN (last_insn_to_move);
2733 uid_loop[INSN_UID (q)] = target_loop;
2735 /* The label jumped to by INSN is no longer a loop
2736 exit. Unless INSN does not have a label (e.g.,
2737 it is a RETURN insn), search loop->exit_labels
2738 to find its label_ref, and remove it. Also turn
2739 off LABEL_OUTSIDE_LOOP_P bit. */
2740 if (JUMP_LABEL (insn))
2742 for (q = 0, r = this_loop->exit_labels;
2744 q = r, r = LABEL_NEXTREF (r))
2745 if (XEXP (r, 0) == JUMP_LABEL (insn))
2747 LABEL_OUTSIDE_LOOP_P (r) = 0;
2749 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2751 this_loop->exit_labels = LABEL_NEXTREF (r);
2755 for (loop = this_loop; loop && loop != target_loop;
2759 /* If we didn't find it, then something is
2765 /* P is now a jump outside the loop, so it must be put
2766 in loop->exit_labels, and marked as such.
2767 The easiest way to do this is to just call
2768 mark_loop_jump again for P. */
2769 mark_loop_jump (PATTERN (p), this_loop);
2771 /* If INSN now jumps to the insn after it,
2773 if (JUMP_LABEL (insn) != 0
2774 && (next_real_insn (JUMP_LABEL (insn))
2775 == next_real_insn (insn)))
2779 /* Continue the loop after where the conditional
2780 branch used to jump, since the only branch insn
2781 in the block (if it still remains) is an inter-loop
2782 branch and hence needs no processing. */
2783 insn = NEXT_INSN (cond_label);
2785 if (--LABEL_NUSES (cond_label) == 0)
2786 delete_insn (cond_label);
2788 /* This loop will be continued with NEXT_INSN (insn). */
2789 insn = PREV_INSN (insn);
2796 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2797 loops it is contained in, mark the target loop invalid.
2799 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2802 mark_loop_jump (x, loop)
2806 struct loop *dest_loop;
2807 struct loop *outer_loop;
2810 switch (GET_CODE (x))
2823 /* There could be a label reference in here. */
2824 mark_loop_jump (XEXP (x, 0), loop);
2830 mark_loop_jump (XEXP (x, 0), loop);
2831 mark_loop_jump (XEXP (x, 1), loop);
2835 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2836 mark_loop_jump (XEXP (x, 1), loop);
2841 mark_loop_jump (XEXP (x, 0), loop);
2845 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2847 /* Link together all labels that branch outside the loop. This
2848 is used by final_[bg]iv_value and the loop unrolling code. Also
2849 mark this LABEL_REF so we know that this branch should predict
2852 /* A check to make sure the label is not in an inner nested loop,
2853 since this does not count as a loop exit. */
2856 for (outer_loop = dest_loop; outer_loop;
2857 outer_loop = outer_loop->outer)
2858 if (outer_loop == loop)
2864 if (loop && ! outer_loop)
2866 LABEL_OUTSIDE_LOOP_P (x) = 1;
2867 LABEL_NEXTREF (x) = loop->exit_labels;
2868 loop->exit_labels = x;
2870 for (outer_loop = loop;
2871 outer_loop && outer_loop != dest_loop;
2872 outer_loop = outer_loop->outer)
2873 outer_loop->exit_count++;
2876 /* If this is inside a loop, but not in the current loop or one enclosed
2877 by it, it invalidates at least one loop. */
2882 /* We must invalidate every nested loop containing the target of this
2883 label, except those that also contain the jump insn. */
2885 for (; dest_loop; dest_loop = dest_loop->outer)
2887 /* Stop when we reach a loop that also contains the jump insn. */
2888 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2889 if (dest_loop == outer_loop)
2892 /* If we get here, we know we need to invalidate a loop. */
2893 if (loop_dump_stream && ! dest_loop->invalid)
2894 fprintf (loop_dump_stream,
2895 "\nLoop at %d ignored due to multiple entry points.\n",
2896 INSN_UID (dest_loop->start));
2898 dest_loop->invalid = 1;
2903 /* If this is not setting pc, ignore. */
2904 if (SET_DEST (x) == pc_rtx)
2905 mark_loop_jump (SET_SRC (x), loop);
2909 mark_loop_jump (XEXP (x, 1), loop);
2910 mark_loop_jump (XEXP (x, 2), loop);
2915 for (i = 0; i < XVECLEN (x, 0); i++)
2916 mark_loop_jump (XVECEXP (x, 0, i), loop);
2920 for (i = 0; i < XVECLEN (x, 1); i++)
2921 mark_loop_jump (XVECEXP (x, 1, i), loop);
2925 /* Strictly speaking this is not a jump into the loop, only a possible
2926 jump out of the loop. However, we have no way to link the destination
2927 of this jump onto the list of exit labels. To be safe we mark this
2928 loop and any containing loops as invalid. */
2931 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2933 if (loop_dump_stream && ! outer_loop->invalid)
2934 fprintf (loop_dump_stream,
2935 "\nLoop at %d ignored due to unknown exit jump.\n",
2936 INSN_UID (outer_loop->start));
2937 outer_loop->invalid = 1;
2944 /* Return nonzero if there is a label in the range from
2945 insn INSN to and including the insn whose luid is END
2946 INSN must have an assigned luid (i.e., it must not have
2947 been previously created by loop.c). */
2950 labels_in_range_p (insn, end)
2954 while (insn && INSN_LUID (insn) <= end)
2956 if (GET_CODE (insn) == CODE_LABEL)
2958 insn = NEXT_INSN (insn);
2964 /* Record that a memory reference X is being set. */
2967 note_addr_stored (x, y, data)
2969 rtx y ATTRIBUTE_UNUSED;
2970 void *data ATTRIBUTE_UNUSED;
2972 struct loop_info *loop_info = data;
2974 if (x == 0 || GET_CODE (x) != MEM)
2977 /* Count number of memory writes.
2978 This affects heuristics in strength_reduce. */
2979 loop_info->num_mem_sets++;
2981 /* BLKmode MEM means all memory is clobbered. */
2982 if (GET_MODE (x) == BLKmode)
2984 if (RTX_UNCHANGING_P (x))
2985 loop_info->unknown_constant_address_altered = 1;
2987 loop_info->unknown_address_altered = 1;
2992 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2993 loop_info->store_mems);
2996 /* X is a value modified by an INSN that references a biv inside a loop
2997 exit test (ie, X is somehow related to the value of the biv). If X
2998 is a pseudo that is used more than once, then the biv is (effectively)
2999 used more than once. DATA is a pointer to a loop_regs structure. */
3002 note_set_pseudo_multiple_uses (x, y, data)
3004 rtx y ATTRIBUTE_UNUSED;
3007 struct loop_regs *regs = (struct loop_regs *) data;
3012 while (GET_CODE (x) == STRICT_LOW_PART
3013 || GET_CODE (x) == SIGN_EXTRACT
3014 || GET_CODE (x) == ZERO_EXTRACT
3015 || GET_CODE (x) == SUBREG)
3018 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
3021 /* If we do not have usage information, or if we know the register
3022 is used more than once, note that fact for check_dbra_loop. */
3023 if (REGNO (x) >= max_reg_before_loop
3024 || ! VARRAY_RTX (regs->single_usage, REGNO (x))
3025 || VARRAY_RTX (regs->single_usage, REGNO (x)) == const0_rtx)
3026 regs->multiple_uses = 1;
3029 /* Return nonzero if the rtx X is invariant over the current loop.
3031 The value is 2 if we refer to something only conditionally invariant.
3033 A memory ref is invariant if it is not volatile and does not conflict
3034 with anything stored in `loop_info->store_mems'. */
3037 loop_invariant_p (loop, x)
3038 const struct loop *loop;
3041 struct loop_info *loop_info = LOOP_INFO (loop);
3042 struct loop_regs *regs = LOOP_REGS (loop);
3044 register enum rtx_code code;
3045 register const char *fmt;
3046 int conditional = 0;
3051 code = GET_CODE (x);
3061 /* A LABEL_REF is normally invariant, however, if we are unrolling
3062 loops, and this label is inside the loop, then it isn't invariant.
3063 This is because each unrolled copy of the loop body will have
3064 a copy of this label. If this was invariant, then an insn loading
3065 the address of this label into a register might get moved outside
3066 the loop, and then each loop body would end up using the same label.
3068 We don't know the loop bounds here though, so just fail for all
3070 if (flag_unroll_loops)
3077 case UNSPEC_VOLATILE:
3081 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3082 since the reg might be set by initialization within the loop. */
3084 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3085 || x == arg_pointer_rtx)
3086 && ! current_function_has_nonlocal_goto)
3089 if (LOOP_INFO (loop)->has_call
3090 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3093 if (VARRAY_INT (regs->set_in_loop, REGNO (x)) < 0)
3096 return VARRAY_INT (regs->set_in_loop, REGNO (x)) == 0;
3099 /* Volatile memory references must be rejected. Do this before
3100 checking for read-only items, so that volatile read-only items
3101 will be rejected also. */
3102 if (MEM_VOLATILE_P (x))
3105 /* See if there is any dependence between a store and this load. */
3106 mem_list_entry = loop_info->store_mems;
3107 while (mem_list_entry)
3109 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3113 mem_list_entry = XEXP (mem_list_entry, 1);
3116 /* It's not invalidated by a store in memory
3117 but we must still verify the address is invariant. */
3121 /* Don't mess with insns declared volatile. */
3122 if (MEM_VOLATILE_P (x))
3130 fmt = GET_RTX_FORMAT (code);
3131 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3135 int tem = loop_invariant_p (loop, XEXP (x, i));
3141 else if (fmt[i] == 'E')
3144 for (j = 0; j < XVECLEN (x, i); j++)
3146 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3156 return 1 + conditional;
3159 /* Return nonzero if all the insns in the loop that set REG
3160 are INSN and the immediately following insns,
3161 and if each of those insns sets REG in an invariant way
3162 (not counting uses of REG in them).
3164 The value is 2 if some of these insns are only conditionally invariant.
3166 We assume that INSN itself is the first set of REG
3167 and that its source is invariant. */
3170 consec_sets_invariant_p (loop, reg, n_sets, insn)
3171 const struct loop *loop;
3175 struct loop_regs *regs = LOOP_REGS (loop);
3177 unsigned int regno = REGNO (reg);
3179 /* Number of sets we have to insist on finding after INSN. */
3180 int count = n_sets - 1;
3181 int old = VARRAY_INT (regs->set_in_loop, regno);
3185 /* If N_SETS hit the limit, we can't rely on its value. */
3189 VARRAY_INT (regs->set_in_loop, regno) = 0;
3193 register enum rtx_code code;
3197 code = GET_CODE (p);
3199 /* If library call, skip to end of it. */
3200 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3205 && (set = single_set (p))
3206 && GET_CODE (SET_DEST (set)) == REG
3207 && REGNO (SET_DEST (set)) == regno)
3209 this = loop_invariant_p (loop, SET_SRC (set));
3212 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3214 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3215 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3217 this = (CONSTANT_P (XEXP (temp, 0))
3218 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3219 && loop_invariant_p (loop, XEXP (temp, 0))));
3226 else if (code != NOTE)
3228 VARRAY_INT (regs->set_in_loop, regno) = old;
3233 VARRAY_INT (regs->set_in_loop, regno) = old;
3234 /* If loop_invariant_p ever returned 2, we return 2. */
3235 return 1 + (value & 2);
3239 /* I don't think this condition is sufficient to allow INSN
3240 to be moved, so we no longer test it. */
3242 /* Return 1 if all insns in the basic block of INSN and following INSN
3243 that set REG are invariant according to TABLE. */
3246 all_sets_invariant_p (reg, insn, table)
3250 register rtx p = insn;
3251 register int regno = REGNO (reg);
3255 register enum rtx_code code;
3257 code = GET_CODE (p);
3258 if (code == CODE_LABEL || code == JUMP_INSN)
3260 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3261 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3262 && REGNO (SET_DEST (PATTERN (p))) == regno)
3264 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3271 /* Look at all uses (not sets) of registers in X. For each, if it is
3272 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3273 a different insn, set USAGE[REGNO] to const0_rtx. */
3276 find_single_use_in_loop (insn, x, usage)
3281 enum rtx_code code = GET_CODE (x);
3282 const char *fmt = GET_RTX_FORMAT (code);
3286 VARRAY_RTX (usage, REGNO (x))
3287 = (VARRAY_RTX (usage, REGNO (x)) != 0
3288 && VARRAY_RTX (usage, REGNO (x)) != insn)
3289 ? const0_rtx : insn;
3291 else if (code == SET)
3293 /* Don't count SET_DEST if it is a REG; otherwise count things
3294 in SET_DEST because if a register is partially modified, it won't
3295 show up as a potential movable so we don't care how USAGE is set
3297 if (GET_CODE (SET_DEST (x)) != REG)
3298 find_single_use_in_loop (insn, SET_DEST (x), usage);
3299 find_single_use_in_loop (insn, SET_SRC (x), usage);
3302 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3304 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3305 find_single_use_in_loop (insn, XEXP (x, i), usage);
3306 else if (fmt[i] == 'E')
3307 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3308 find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
3312 /* Count and record any set in X which is contained in INSN. Update
3313 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3316 count_one_set (regs, insn, x, may_not_move, last_set)
3317 struct loop_regs *regs;
3319 varray_type may_not_move;
3322 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3323 /* Don't move a reg that has an explicit clobber.
3324 It's not worth the pain to try to do it correctly. */
3325 VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
3327 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3329 rtx dest = SET_DEST (x);
3330 while (GET_CODE (dest) == SUBREG
3331 || GET_CODE (dest) == ZERO_EXTRACT
3332 || GET_CODE (dest) == SIGN_EXTRACT
3333 || GET_CODE (dest) == STRICT_LOW_PART)
3334 dest = XEXP (dest, 0);
3335 if (GET_CODE (dest) == REG)
3337 register int regno = REGNO (dest);
3338 /* If this is the first setting of this reg
3339 in current basic block, and it was set before,
3340 it must be set in two basic blocks, so it cannot
3341 be moved out of the loop. */
3342 if (VARRAY_INT (regs->set_in_loop, regno) > 0
3343 && last_set[regno] == 0)
3344 VARRAY_CHAR (may_not_move, regno) = 1;
3345 /* If this is not first setting in current basic block,
3346 see if reg was used in between previous one and this.
3347 If so, neither one can be moved. */
3348 if (last_set[regno] != 0
3349 && reg_used_between_p (dest, last_set[regno], insn))
3350 VARRAY_CHAR (may_not_move, regno) = 1;
3351 if (VARRAY_INT (regs->set_in_loop, regno) < 127)
3352 ++VARRAY_INT (regs->set_in_loop, regno);
3353 last_set[regno] = insn;
3358 /* Increment REGS->SET_IN_LOOP at the index of each register
3359 that is modified by an insn between FROM and TO.
3360 If the value of an element of REGS->SET_IN_LOOP becomes 127 or more,
3361 stop incrementing it, to avoid overflow.
3363 Store in SINGLE_USAGE[I] the single insn in which register I is
3364 used, if it is only used once. Otherwise, it is set to 0 (for no
3365 uses) or const0_rtx for more than one use. This parameter may be zero,
3366 in which case this processing is not done.
3368 Store in *COUNT_PTR the number of actual instruction
3369 in the loop. We use this to decide what is worth moving out. */
3371 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3372 In that case, it is the insn that last set reg n. */
3375 count_loop_regs_set (loop, may_not_move, single_usage, count_ptr, nregs)
3376 const struct loop *loop;
3377 varray_type may_not_move;
3378 varray_type single_usage;
3382 struct loop_regs *regs = LOOP_REGS (loop);
3383 register rtx *last_set = (rtx *) xcalloc (nregs, sizeof (rtx));
3385 register int count = 0;
3387 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
3388 insn = NEXT_INSN (insn))
3394 /* Record registers that have exactly one use. */
3395 find_single_use_in_loop (insn, PATTERN (insn), single_usage);
3397 /* Include uses in REG_EQUAL notes. */
3398 if (REG_NOTES (insn))
3399 find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
3401 if (GET_CODE (PATTERN (insn)) == SET
3402 || GET_CODE (PATTERN (insn)) == CLOBBER)
3403 count_one_set (regs, insn, PATTERN (insn), may_not_move, last_set);
3404 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3407 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3408 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
3409 may_not_move, last_set);
3413 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
3414 memset ((char *) last_set, 0, nregs * sizeof (rtx));
3422 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3423 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3424 contained in insn INSN is used by any insn that precedes INSN in
3425 cyclic order starting from the loop entry point.
3427 We don't want to use INSN_LUID here because if we restrict INSN to those
3428 that have a valid INSN_LUID, it means we cannot move an invariant out
3429 from an inner loop past two loops. */
3432 loop_reg_used_before_p (loop, set, insn)
3433 const struct loop *loop;
3436 rtx reg = SET_DEST (set);
3439 /* Scan forward checking for register usage. If we hit INSN, we
3440 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3441 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3443 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3453 /* A "basic induction variable" or biv is a pseudo reg that is set
3454 (within this loop) only by incrementing or decrementing it. */
3455 /* A "general induction variable" or giv is a pseudo reg whose
3456 value is a linear function of a biv. */
3458 /* Bivs are recognized by `basic_induction_var';
3459 Givs by `general_induction_var'. */
3461 /* Communication with routines called via `note_stores'. */
3463 static rtx note_insn;
3465 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3467 static rtx addr_placeholder;
3469 /* ??? Unfinished optimizations, and possible future optimizations,
3470 for the strength reduction code. */
3472 /* ??? The interaction of biv elimination, and recognition of 'constant'
3473 bivs, may cause problems. */
3475 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3476 performance problems.
3478 Perhaps don't eliminate things that can be combined with an addressing
3479 mode. Find all givs that have the same biv, mult_val, and add_val;
3480 then for each giv, check to see if its only use dies in a following
3481 memory address. If so, generate a new memory address and check to see
3482 if it is valid. If it is valid, then store the modified memory address,
3483 otherwise, mark the giv as not done so that it will get its own iv. */
3485 /* ??? Could try to optimize branches when it is known that a biv is always
3488 /* ??? When replace a biv in a compare insn, we should replace with closest
3489 giv so that an optimized branch can still be recognized by the combiner,
3490 e.g. the VAX acb insn. */
3492 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3493 was rerun in loop_optimize whenever a register was added or moved.
3494 Also, some of the optimizations could be a little less conservative. */
3496 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3497 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3500 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3501 loop iteration except for the last one.
3503 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3507 for_each_insn_in_loop (loop, fncall)
3509 loop_insn_callback fncall;
3511 /* This is 1 if current insn is not executed at least once for every loop
3513 int not_every_iteration = 0;
3514 int maybe_multiple = 0;
3515 int past_loop_latch = 0;
3519 /* If loop_scan_start points to the loop exit test, we have to be wary of
3520 subversive use of gotos inside expression statements. */
3521 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3522 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3524 /* Scan through loop to find all possible bivs. */
3526 for (p = next_insn_in_loop (loop, loop->scan_start);
3528 p = next_insn_in_loop (loop, p))
3530 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3532 /* Past CODE_LABEL, we get to insns that may be executed multiple
3533 times. The only way we can be sure that they can't is if every
3534 jump insn between here and the end of the loop either
3535 returns, exits the loop, is a jump to a location that is still
3536 behind the label, or is a jump to the loop start. */
3538 if (GET_CODE (p) == CODE_LABEL)
3546 insn = NEXT_INSN (insn);
3547 if (insn == loop->scan_start)
3549 if (insn == loop->end)
3555 if (insn == loop->scan_start)
3559 if (GET_CODE (insn) == JUMP_INSN
3560 && GET_CODE (PATTERN (insn)) != RETURN
3561 && (!any_condjump_p (insn)
3562 || (JUMP_LABEL (insn) != 0
3563 && JUMP_LABEL (insn) != loop->scan_start
3564 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3572 /* Past a jump, we get to insns for which we can't count
3573 on whether they will be executed during each iteration. */
3574 /* This code appears twice in strength_reduce. There is also similar
3575 code in scan_loop. */
3576 if (GET_CODE (p) == JUMP_INSN
3577 /* If we enter the loop in the middle, and scan around to the
3578 beginning, don't set not_every_iteration for that.
3579 This can be any kind of jump, since we want to know if insns
3580 will be executed if the loop is executed. */
3581 && !(JUMP_LABEL (p) == loop->top
3582 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3583 && any_uncondjump_p (p))
3584 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3588 /* If this is a jump outside the loop, then it also doesn't
3589 matter. Check to see if the target of this branch is on the
3590 loop->exits_labels list. */
3592 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3593 if (XEXP (label, 0) == JUMP_LABEL (p))
3597 not_every_iteration = 1;
3600 else if (GET_CODE (p) == NOTE)
3602 /* At the virtual top of a converted loop, insns are again known to
3603 be executed each iteration: logically, the loop begins here
3604 even though the exit code has been duplicated.
3606 Insns are also again known to be executed each iteration at
3607 the LOOP_CONT note. */
3608 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3609 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3611 not_every_iteration = 0;
3612 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3614 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3618 /* Note if we pass a loop latch. If we do, then we can not clear
3619 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3620 a loop since a jump before the last CODE_LABEL may have started
3621 a new loop iteration.
3623 Note that LOOP_TOP is only set for rotated loops and we need
3624 this check for all loops, so compare against the CODE_LABEL
3625 which immediately follows LOOP_START. */
3626 if (GET_CODE (p) == JUMP_INSN
3627 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3628 past_loop_latch = 1;
3630 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3631 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3632 or not an insn is known to be executed each iteration of the
3633 loop, whether or not any iterations are known to occur.
3635 Therefore, if we have just passed a label and have no more labels
3636 between here and the test insn of the loop, and we have not passed
3637 a jump to the top of the loop, then we know these insns will be
3638 executed each iteration. */
3640 if (not_every_iteration
3642 && GET_CODE (p) == CODE_LABEL
3643 && no_labels_between_p (p, loop->end)
3644 && loop_insn_first_p (p, loop->cont))
3645 not_every_iteration = 0;
3650 loop_bivs_find (loop)
3653 struct loop_regs *regs = LOOP_REGS (loop);
3654 struct loop_ivs *ivs = LOOP_IVS (loop);
3655 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3656 struct iv_class *bl, **backbl;
3657 /* Ratio of extra register life span we can justify
3658 for saving an instruction. More if loop doesn't call subroutines
3659 since in that case saving an insn makes more difference
3660 and more registers are available. */
3661 /* ??? could set this to last value of threshold in move_movables */
3663 ivs->loop_iv_list = 0;
3665 VARRAY_INT_INIT (ivs->reg_iv_type, max_reg_before_loop, "reg_iv_type");
3666 VARRAY_GENERIC_PTR_INIT (ivs->reg_iv_info, max_reg_before_loop,
3668 ivs->reg_biv_class = (struct iv_class **)
3669 xcalloc (max_reg_before_loop, sizeof (struct iv_class *));
3671 for_each_insn_in_loop (loop, check_insn_for_bivs);
3673 /* Scan ivs->loop_iv_list to remove all regs that proved not to be bivs.
3674 Make a sanity check against regs->n_times_set. */
3675 for (backbl = &ivs->loop_iv_list, bl = *backbl; bl; bl = bl->next)
3677 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3678 /* Above happens if register modified by subreg, etc. */
3679 /* Make sure it is not recognized as a basic induction var: */
3680 || VARRAY_INT (regs->n_times_set, bl->regno) != bl->biv_count
3681 /* If never incremented, it is invariant that we decided not to
3682 move. So leave it alone. */
3683 || ! bl->incremented)
3685 if (loop_dump_stream)
3686 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3688 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3689 ? "not induction variable"
3690 : (! bl->incremented ? "never incremented"
3693 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3700 if (loop_dump_stream)
3701 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3707 /* Determine how BIVS are initialised by looking through pre-header
3708 extended basic block. */
3710 loop_bivs_init_find (loop)
3713 struct loop_ivs *ivs = LOOP_IVS (loop);
3714 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3715 struct iv_class *bl;
3719 /* Find initial value for each biv by searching backwards from loop_start,
3720 halting at first label. Also record any test condition. */
3723 for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3729 if (GET_CODE (p) == CALL_INSN)
3733 note_stores (PATTERN (p), record_initial, ivs);
3735 /* Record any test of a biv that branches around the loop if no store
3736 between it and the start of loop. We only care about tests with
3737 constants and registers and only certain of those. */
3738 if (GET_CODE (p) == JUMP_INSN
3739 && JUMP_LABEL (p) != 0
3740 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
3741 && (test = get_condition_for_loop (loop, p)) != 0
3742 && GET_CODE (XEXP (test, 0)) == REG
3743 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3744 && (bl = ivs->reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3745 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop->start)
3746 && bl->init_insn == 0)
3748 /* If an NE test, we have an initial value! */
3749 if (GET_CODE (test) == NE)
3752 bl->init_set = gen_rtx_SET (VOIDmode,
3753 XEXP (test, 0), XEXP (test, 1));
3756 bl->initial_test = test;
3762 /* Look at the each biv and see if we can say anything better about its
3763 initial value from any initializing insns set up above. (This is done
3764 in two passes to avoid missing SETs in a PARALLEL.) */
3766 loop_bivs_check (loop)
3769 struct loop_ivs *ivs = LOOP_IVS (loop);
3770 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3771 struct iv_class *bl;
3772 struct iv_class **backbl;
3774 for (backbl = &ivs->loop_iv_list; (bl = *backbl); backbl = &bl->next)
3779 if (! bl->init_insn)
3782 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3783 is a constant, use the value of that. */
3784 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3785 && CONSTANT_P (XEXP (note, 0)))
3786 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3787 && CONSTANT_P (XEXP (note, 0))))
3788 src = XEXP (note, 0);
3790 src = SET_SRC (bl->init_set);
3792 if (loop_dump_stream)
3793 fprintf (loop_dump_stream,
3794 "Biv %d initialized at insn %d: initial value ",
3795 bl->regno, INSN_UID (bl->init_insn));
3797 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3798 || GET_MODE (src) == VOIDmode)
3799 && valid_initial_value_p (src, bl->init_insn,
3800 LOOP_INFO (loop)->pre_header_has_call,
3803 bl->initial_value = src;
3805 if (loop_dump_stream)
3807 if (GET_CODE (src) == CONST_INT)
3809 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
3811 fputc ('\n', loop_dump_stream);
3815 print_rtl (loop_dump_stream, src);
3816 fprintf (loop_dump_stream, "\n");
3820 /* If we can't make it a giv,
3821 let biv keep initial value of "itself". */
3822 else if (loop_dump_stream)
3823 fprintf (loop_dump_stream, "is complex\n");
3828 /* Search the loop for general induction variables. */
3831 loop_givs_find (loop)
3834 for_each_insn_in_loop (loop, check_insn_for_givs);
3838 /* For each giv for which we still don't know whether or not it is
3839 replaceable, check to see if it is replaceable because its final value
3840 can be calculated. */
3843 loop_givs_check (loop)
3846 struct loop_ivs *ivs = LOOP_IVS (loop);
3847 struct iv_class *bl;
3849 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3851 struct induction *v;
3853 for (v = bl->giv; v; v = v->next_iv)
3854 if (! v->replaceable && ! v->not_replaceable)
3855 check_final_value (loop, v);
3860 /* Return non-zero if it is possible to eliminate the biv BL provided
3861 all givs are reduced. This is possible if either the reg is not
3862 used outside the loop, or we can compute what its final value will
3866 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3868 struct iv_class *bl;
3872 /* For architectures with a decrement_and_branch_until_zero insn,
3873 don't do this if we put a REG_NONNEG note on the endtest for this
3876 #ifdef HAVE_decrement_and_branch_until_zero
3879 if (loop_dump_stream)
3880 fprintf (loop_dump_stream,
3881 "Cannot eliminate nonneg biv %d.\n", bl->regno);
3886 /* Check that biv is used outside loop or if it has a final value.
3887 Compare against bl->init_insn rather than loop->start. We aren't
3888 concerned with any uses of the biv between init_insn and
3889 loop->start since these won't be affected by the value of the biv
3890 elsewhere in the function, so long as init_insn doesn't use the
3893 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3895 && INSN_UID (bl->init_insn) < max_uid_for_loop
3896 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3897 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3898 || (bl->final_value = final_biv_value (loop, bl)))
3899 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3901 if (loop_dump_stream)
3903 fprintf (loop_dump_stream,
3904 "Cannot eliminate biv %d.\n",
3906 fprintf (loop_dump_stream,
3907 "First use: insn %d, last use: insn %d.\n",
3908 REGNO_FIRST_UID (bl->regno),
3909 REGNO_LAST_UID (bl->regno));
3915 /* Reduce each giv of BL that we have decided to reduce. */
3918 loop_givs_reduce (loop, bl)
3920 struct iv_class *bl;
3922 struct induction *v;
3924 for (v = bl->giv; v; v = v->next_iv)
3926 struct induction *tv;
3927 if (! v->ignore && v->same == 0)
3929 int auto_inc_opt = 0;
3931 /* If the code for derived givs immediately below has already
3932 allocated a new_reg, we must keep it. */
3934 v->new_reg = gen_reg_rtx (v->mode);
3937 /* If the target has auto-increment addressing modes, and
3938 this is an address giv, then try to put the increment
3939 immediately after its use, so that flow can create an
3940 auto-increment addressing mode. */
3941 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
3942 && bl->biv->always_executed && ! bl->biv->maybe_multiple
3943 /* We don't handle reversed biv's because bl->biv->insn
3944 does not have a valid INSN_LUID. */
3946 && v->always_executed && ! v->maybe_multiple
3947 && INSN_UID (v->insn) < max_uid_for_loop)
3949 /* If other giv's have been combined with this one, then
3950 this will work only if all uses of the other giv's occur
3951 before this giv's insn. This is difficult to check.
3953 We simplify this by looking for the common case where
3954 there is one DEST_REG giv, and this giv's insn is the
3955 last use of the dest_reg of that DEST_REG giv. If the
3956 increment occurs after the address giv, then we can
3957 perform the optimization. (Otherwise, the increment
3958 would have to go before other_giv, and we would not be
3959 able to combine it with the address giv to get an
3960 auto-inc address.) */
3961 if (v->combined_with)
3963 struct induction *other_giv = 0;
3965 for (tv = bl->giv; tv; tv = tv->next_iv)
3973 if (! tv && other_giv
3974 && REGNO (other_giv->dest_reg) < max_reg_before_loop
3975 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
3976 == INSN_UID (v->insn))
3977 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
3980 /* Check for case where increment is before the address
3981 giv. Do this test in "loop order". */
3982 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
3983 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3984 || (INSN_LUID (bl->biv->insn)
3985 > INSN_LUID (loop->scan_start))))
3986 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3987 && (INSN_LUID (loop->scan_start)
3988 < INSN_LUID (bl->biv->insn))))
3997 /* We can't put an insn immediately after one setting
3998 cc0, or immediately before one using cc0. */
3999 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
4000 || (auto_inc_opt == -1
4001 && (prev = prev_nonnote_insn (v->insn)) != 0
4003 && sets_cc0_p (PATTERN (prev))))
4009 v->auto_inc_opt = 1;
4013 /* For each place where the biv is incremented, add an insn
4014 to increment the new, reduced reg for the giv. */
4015 for (tv = bl->biv; tv; tv = tv->next_iv)
4020 insert_before = tv->insn;
4021 else if (auto_inc_opt == 1)
4022 insert_before = NEXT_INSN (v->insn);
4024 insert_before = v->insn;
4026 if (tv->mult_val == const1_rtx)
4027 emit_iv_add_mult (tv->add_val, v->mult_val,
4028 v->new_reg, v->new_reg, insert_before);
4029 else /* tv->mult_val == const0_rtx */
4030 /* A multiply is acceptable here
4031 since this is presumed to be seldom executed. */
4032 emit_iv_add_mult (tv->add_val, v->mult_val,
4033 v->add_val, v->new_reg, insert_before);
4036 /* Add code at loop start to initialize giv's reduced reg. */
4038 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4039 v->mult_val, v->add_val, v->new_reg,
4046 /* Check for givs whose first use is their definition and whose
4047 last use is the definition of another giv. If so, it is likely
4048 dead and should not be used to derive another giv nor to
4052 loop_givs_dead_check (loop, bl)
4053 struct loop *loop ATTRIBUTE_UNUSED;
4054 struct iv_class *bl;
4056 struct induction *v;
4058 for (v = bl->giv; v; v = v->next_iv)
4061 || (v->same && v->same->ignore))
4064 if (v->giv_type == DEST_REG
4065 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4067 struct induction *v1;
4069 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4070 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4078 loop_givs_rescan (loop, bl, reg_map, end_insert_before)
4080 struct iv_class *bl;
4082 rtx end_insert_before;
4084 struct induction *v;
4086 for (v = bl->giv; v; v = v->next_iv)
4088 if (v->same && v->same->ignore)
4094 /* Update expression if this was combined, in case other giv was
4097 v->new_reg = replace_rtx (v->new_reg,
4098 v->same->dest_reg, v->same->new_reg);
4100 /* See if this register is known to be a pointer to something. If
4101 so, see if we can find the alignment. First see if there is a
4102 destination register that is a pointer. If so, this shares the
4103 alignment too. Next see if we can deduce anything from the
4104 computational information. If not, and this is a DEST_ADDR
4105 giv, at least we know that it's a pointer, though we don't know
4107 if (GET_CODE (v->new_reg) == REG
4108 && v->giv_type == DEST_REG
4109 && REG_POINTER (v->dest_reg))
4110 mark_reg_pointer (v->new_reg,
4111 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
4112 else if (GET_CODE (v->new_reg) == REG
4113 && REG_POINTER (v->src_reg))
4115 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4118 || GET_CODE (v->add_val) != CONST_INT
4119 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4122 mark_reg_pointer (v->new_reg, align);
4124 else if (GET_CODE (v->new_reg) == REG
4125 && GET_CODE (v->add_val) == REG
4126 && REG_POINTER (v->add_val))
4128 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4130 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4131 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4134 mark_reg_pointer (v->new_reg, align);
4136 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4137 mark_reg_pointer (v->new_reg, 0);
4139 if (v->giv_type == DEST_ADDR)
4140 /* Store reduced reg as the address in the memref where we found
4142 validate_change (v->insn, v->location, v->new_reg, 0);
4143 else if (v->replaceable)
4145 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4149 /* Not replaceable; emit an insn to set the original giv reg from
4150 the reduced giv, same as above. */
4151 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4155 /* When a loop is reversed, givs which depend on the reversed
4156 biv, and which are live outside the loop, must be set to their
4157 correct final value. This insn is only needed if the giv is
4158 not replaceable. The correct final value is the same as the
4159 value that the giv starts the reversed loop with. */
4160 if (bl->reversed && ! v->replaceable)
4161 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4162 v->mult_val, v->add_val, v->dest_reg,
4164 else if (v->final_value)
4168 /* If the loop has multiple exits, emit the insn before the
4169 loop to ensure that it will always be executed no matter
4170 how the loop exits. Otherwise, emit the insn after the loop,
4171 since this is slightly more efficient. */
4172 if (loop->exit_count)
4173 insert_before = loop->start;
4175 insert_before = end_insert_before;
4176 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4180 if (loop_dump_stream)
4182 fprintf (loop_dump_stream, "giv at %d reduced to ",
4183 INSN_UID (v->insn));
4184 print_rtl (loop_dump_stream, v->new_reg);
4185 fprintf (loop_dump_stream, "\n");
4192 loop_giv_reduce_benefit (loop, bl, v, test_reg)
4193 struct loop *loop ATTRIBUTE_UNUSED;
4194 struct iv_class *bl;
4195 struct induction *v;
4201 benefit = v->benefit;
4202 PUT_MODE (test_reg, v->mode);
4203 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4204 test_reg, test_reg);
4206 /* Reduce benefit if not replaceable, since we will insert a
4207 move-insn to replace the insn that calculates this giv. Don't do
4208 this unless the giv is a user variable, since it will often be
4209 marked non-replaceable because of the duplication of the exit
4210 code outside the loop. In such a case, the copies we insert are
4211 dead and will be deleted. So they don't have a cost. Similar
4212 situations exist. */
4213 /* ??? The new final_[bg]iv_value code does a much better job of
4214 finding replaceable giv's, and hence this code may no longer be
4216 if (! v->replaceable && ! bl->eliminable
4217 && REG_USERVAR_P (v->dest_reg))
4218 benefit -= copy_cost;
4220 /* Decrease the benefit to count the add-insns that we will insert
4221 to increment the reduced reg for the giv. ??? This can
4222 overestimate the run-time cost of the additional insns, e.g. if
4223 there are multiple basic blocks that increment the biv, but only
4224 one of these blocks is executed during each iteration. There is
4225 no good way to detect cases like this with the current structure
4226 of the loop optimizer. This code is more accurate for
4227 determining code size than run-time benefits. */
4228 benefit -= add_cost * bl->biv_count;
4230 /* Decide whether to strength-reduce this giv or to leave the code
4231 unchanged (recompute it from the biv each time it is used). This
4232 decision can be made independently for each giv. */
4235 /* Attempt to guess whether autoincrement will handle some of the
4236 new add insns; if so, increase BENEFIT (undo the subtraction of
4237 add_cost that was done above). */
4238 if (v->giv_type == DEST_ADDR
4239 /* Increasing the benefit is risky, since this is only a guess.
4240 Avoid increasing register pressure in cases where there would
4241 be no other benefit from reducing this giv. */
4243 && GET_CODE (v->mult_val) == CONST_INT)
4245 if (HAVE_POST_INCREMENT
4246 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4247 benefit += add_cost * bl->biv_count;
4248 else if (HAVE_PRE_INCREMENT
4249 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4250 benefit += add_cost * bl->biv_count;
4251 else if (HAVE_POST_DECREMENT
4252 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4253 benefit += add_cost * bl->biv_count;
4254 else if (HAVE_PRE_DECREMENT
4255 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4256 benefit += add_cost * bl->biv_count;
4264 /* Perform strength reduction and induction variable elimination.
4266 Pseudo registers created during this function will be beyond the
4267 last valid index in several tables including regs->n_times_set and
4268 regno_last_uid. This does not cause a problem here, because the
4269 added registers cannot be givs outside of their loop, and hence
4270 will never be reconsidered. But scan_loop must check regnos to
4271 make sure they are in bounds. */
4274 strength_reduce (loop, insn_count, flags)
4279 struct loop_info *loop_info = LOOP_INFO (loop);
4280 struct loop_regs *regs = LOOP_REGS (loop);
4281 struct loop_ivs *ivs = LOOP_IVS (loop);
4283 /* Temporary list pointer for traversing ivs->loop_iv_list. */
4284 struct iv_class *bl;
4285 /* Ratio of extra register life span we can justify
4286 for saving an instruction. More if loop doesn't call subroutines
4287 since in that case saving an insn makes more difference
4288 and more registers are available. */
4289 /* ??? could set this to last value of threshold in move_movables */
4290 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
4291 /* Map of pseudo-register replacements. */
4292 rtx *reg_map = NULL;
4294 rtx end_insert_before;
4295 int unrolled_insn_copies = 0;
4296 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
4298 addr_placeholder = gen_reg_rtx (Pmode);
4300 /* Save insn immediately after the loop_end. Insns inserted after loop_end
4301 must be put before this insn, so that they will appear in the right
4302 order (i.e. loop order).
4304 If loop_end is the end of the current function, then emit a
4305 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
4307 if (NEXT_INSN (loop->end) != 0)
4308 end_insert_before = NEXT_INSN (loop->end);
4310 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop->end);
4313 /* Find all BIVs in loop. */
4314 loop_bivs_find (loop);
4316 /* Exit if there are no bivs. */
4317 if (! ivs->loop_iv_list)
4319 /* Can still unroll the loop anyways, but indicate that there is no
4320 strength reduction info available. */
4321 if (flags & LOOP_UNROLL)
4322 unroll_loop (loop, insn_count, end_insert_before, 0);
4327 /* Determine how BIVS are initialised by looking through pre-header
4328 extended basic block. */
4329 loop_bivs_init_find (loop);
4331 /* Look at the each biv and see if we can say anything better about its
4332 initial value from any initializing insns set up above. */
4333 loop_bivs_check (loop);
4335 /* Search the loop for general induction variables. */
4336 loop_givs_find (loop);
4338 /* Try to calculate and save the number of loop iterations. This is
4339 set to zero if the actual number can not be calculated. This must
4340 be called after all giv's have been identified, since otherwise it may
4341 fail if the iteration variable is a giv. */
4342 loop_iterations (loop);
4344 /* Now for each giv for which we still don't know whether or not it is
4345 replaceable, check to see if it is replaceable because its final value
4346 can be calculated. This must be done after loop_iterations is called,
4347 so that final_giv_value will work correctly. */
4348 loop_givs_check (loop);
4350 /* Try to prove that the loop counter variable (if any) is always
4351 nonnegative; if so, record that fact with a REG_NONNEG note
4352 so that "decrement and branch until zero" insn can be used. */
4353 check_dbra_loop (loop, insn_count);
4355 /* Create reg_map to hold substitutions for replaceable giv regs.
4356 Some givs might have been made from biv increments, so look at
4357 ivs->reg_iv_type for a suitable size. */
4358 reg_map_size = ivs->reg_iv_type->num_elements;
4359 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
4361 /* Examine each iv class for feasibility of strength reduction/induction
4362 variable elimination. */
4364 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
4366 struct induction *v;
4369 /* Test whether it will be possible to eliminate this biv
4370 provided all givs are reduced. */
4371 bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
4373 /* Check each extension dependent giv in this class to see if its
4374 root biv is safe from wrapping in the interior mode. */
4375 check_ext_dependant_givs (bl, loop_info);
4377 /* Combine all giv's for this iv_class. */
4378 combine_givs (regs, bl);
4380 /* This will be true at the end, if all givs which depend on this
4381 biv have been strength reduced.
4382 We can't (currently) eliminate the biv unless this is so. */
4383 bl->all_reduced = 1;
4385 for (v = bl->giv; v; v = v->next_iv)
4387 struct induction *tv;
4389 if (v->ignore || v->same)
4392 benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
4394 /* If an insn is not to be strength reduced, then set its ignore
4395 flag, and clear bl->all_reduced. */
4397 /* A giv that depends on a reversed biv must be reduced if it is
4398 used after the loop exit, otherwise, it would have the wrong
4399 value after the loop exit. To make it simple, just reduce all
4400 of such giv's whether or not we know they are used after the loop
4403 if (! flag_reduce_all_givs
4404 && v->lifetime * threshold * benefit < insn_count
4407 if (loop_dump_stream)
4408 fprintf (loop_dump_stream,
4409 "giv of insn %d not worth while, %d vs %d.\n",
4411 v->lifetime * threshold * benefit, insn_count);
4413 bl->all_reduced = 0;
4417 /* Check that we can increment the reduced giv without a
4418 multiply insn. If not, reject it. */
4420 for (tv = bl->biv; tv; tv = tv->next_iv)
4421 if (tv->mult_val == const1_rtx
4422 && ! product_cheap_p (tv->add_val, v->mult_val))
4424 if (loop_dump_stream)
4425 fprintf (loop_dump_stream,
4426 "giv of insn %d: would need a multiply.\n",
4427 INSN_UID (v->insn));
4429 bl->all_reduced = 0;
4435 /* Check for givs whose first use is their definition and whose
4436 last use is the definition of another giv. If so, it is likely
4437 dead and should not be used to derive another giv nor to
4439 loop_givs_dead_check (loop, bl);
4441 /* Reduce each giv that we decided to reduce. */
4442 loop_givs_reduce (loop, bl);
4444 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4447 For each giv register that can be reduced now: if replaceable,
4448 substitute reduced reg wherever the old giv occurs;
4449 else add new move insn "giv_reg = reduced_reg". */
4450 loop_givs_rescan (loop, bl, reg_map, end_insert_before);
4452 /* All the givs based on the biv bl have been reduced if they
4455 /* For each giv not marked as maybe dead that has been combined with a
4456 second giv, clear any "maybe dead" mark on that second giv.
4457 v->new_reg will either be or refer to the register of the giv it
4460 Doing this clearing avoids problems in biv elimination where
4461 a giv's new_reg is a complex value that can't be put in the
4462 insn but the giv combined with (with a reg as new_reg) is
4463 marked maybe_dead. Since the register will be used in either
4464 case, we'd prefer it be used from the simpler giv. */
4466 for (v = bl->giv; v; v = v->next_iv)
4467 if (! v->maybe_dead && v->same)
4468 v->same->maybe_dead = 0;
4470 /* Try to eliminate the biv, if it is a candidate.
4471 This won't work if ! bl->all_reduced,
4472 since the givs we planned to use might not have been reduced.
4474 We have to be careful that we didn't initially think we could
4475 eliminate this biv because of a giv that we now think may be
4476 dead and shouldn't be used as a biv replacement.
4478 Also, there is the possibility that we may have a giv that looks
4479 like it can be used to eliminate a biv, but the resulting insn
4480 isn't valid. This can happen, for example, on the 88k, where a
4481 JUMP_INSN can compare a register only with zero. Attempts to
4482 replace it with a compare with a constant will fail.
4484 Note that in cases where this call fails, we may have replaced some
4485 of the occurrences of the biv with a giv, but no harm was done in
4486 doing so in the rare cases where it can occur. */
4488 if (bl->all_reduced == 1 && bl->eliminable
4489 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4491 /* ?? If we created a new test to bypass the loop entirely,
4492 or otherwise drop straight in, based on this test, then
4493 we might want to rewrite it also. This way some later
4494 pass has more hope of removing the initialization of this
4497 /* If final_value != 0, then the biv may be used after loop end
4498 and we must emit an insn to set it just in case.
4500 Reversed bivs already have an insn after the loop setting their
4501 value, so we don't need another one. We can't calculate the
4502 proper final value for such a biv here anyways. */
4503 if (bl->final_value && ! bl->reversed)
4507 /* If the loop has multiple exits, emit the insn before the
4508 loop to ensure that it will always be executed no matter
4509 how the loop exits. Otherwise, emit the insn after the
4510 loop, since this is slightly more efficient. */
4511 if (loop->exit_count)
4512 insert_before = loop->start;
4514 insert_before = end_insert_before;
4516 emit_insn_before (gen_move_insn (bl->biv->dest_reg,
4521 if (loop_dump_stream)
4522 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4527 /* Go through all the instructions in the loop, making all the
4528 register substitutions scheduled in REG_MAP. */
4530 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
4531 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4532 || GET_CODE (p) == CALL_INSN)
4534 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4535 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4539 if (loop_info->n_iterations > 0)
4541 /* When we completely unroll a loop we will likely not need the increment
4542 of the loop BIV and we will not need the conditional branch at the
4544 unrolled_insn_copies = insn_count - 2;
4547 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4548 need the comparison before the conditional branch at the end of the
4550 unrolled_insn_copies -= 1;
4553 /* We'll need one copy for each loop iteration. */
4554 unrolled_insn_copies *= loop_info->n_iterations;
4556 /* A little slop to account for the ability to remove initialization
4557 code, better CSE, and other secondary benefits of completely
4558 unrolling some loops. */
4559 unrolled_insn_copies -= 1;
4561 /* Clamp the value. */
4562 if (unrolled_insn_copies < 0)
4563 unrolled_insn_copies = 0;
4566 /* Unroll loops from within strength reduction so that we can use the
4567 induction variable information that strength_reduce has already
4568 collected. Always unroll loops that would be as small or smaller
4569 unrolled than when rolled. */
4570 if ((flags & LOOP_UNROLL)
4571 || (loop_info->n_iterations > 0
4572 && unrolled_insn_copies <= insn_count))
4573 unroll_loop (loop, insn_count, end_insert_before, 1);
4575 #ifdef HAVE_doloop_end
4576 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4577 doloop_optimize (loop);
4578 #endif /* HAVE_doloop_end */
4580 if (loop_dump_stream)
4581 fprintf (loop_dump_stream, "\n");
4584 VARRAY_FREE (ivs->reg_iv_type);
4585 VARRAY_FREE (ivs->reg_iv_info);
4586 free (ivs->reg_biv_class);
4588 struct iv_class *iv = ivs->loop_iv_list;
4591 struct iv_class *next = iv->next;
4592 struct induction *induction;
4593 struct induction *next_induction;
4595 for (induction = iv->biv; induction; induction = next_induction)
4597 next_induction = induction->next_iv;
4600 for (induction = iv->giv; induction; induction = next_induction)
4602 next_induction = induction->next_iv;
4614 /*Record all basic induction variables calculated in the insn. */
4616 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4619 int not_every_iteration;
4622 struct loop_ivs *ivs = LOOP_IVS (loop);
4629 if (GET_CODE (p) == INSN
4630 && (set = single_set (p))
4631 && GET_CODE (SET_DEST (set)) == REG)
4633 dest_reg = SET_DEST (set);
4634 if (REGNO (dest_reg) < max_reg_before_loop
4635 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4636 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4638 if (basic_induction_var (loop, SET_SRC (set),
4639 GET_MODE (SET_SRC (set)),
4640 dest_reg, p, &inc_val, &mult_val,
4643 /* It is a possible basic induction variable.
4644 Create and initialize an induction structure for it. */
4647 = (struct induction *) xmalloc (sizeof (struct induction));
4649 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4650 not_every_iteration, maybe_multiple);
4651 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4653 else if (REGNO (dest_reg) < max_reg_before_loop)
4654 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4660 /* Record all givs calculated in the insn.
4661 A register is a giv if: it is only set once, it is a function of a
4662 biv and a constant (or invariant), and it is not a biv. */
4664 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4667 int not_every_iteration;
4670 struct loop_regs *regs = LOOP_REGS (loop);
4673 /* Look for a general induction variable in a register. */
4674 if (GET_CODE (p) == INSN
4675 && (set = single_set (p))
4676 && GET_CODE (SET_DEST (set)) == REG
4677 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
4686 rtx last_consec_insn;
4688 dest_reg = SET_DEST (set);
4689 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4692 if (/* SET_SRC is a giv. */
4693 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4694 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4695 /* Equivalent expression is a giv. */
4696 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4697 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4698 &add_val, &mult_val, &ext_val, 0,
4699 &benefit, VOIDmode)))
4700 /* Don't try to handle any regs made by loop optimization.
4701 We have nothing on them in regno_first_uid, etc. */
4702 && REGNO (dest_reg) < max_reg_before_loop
4703 /* Don't recognize a BASIC_INDUCT_VAR here. */
4704 && dest_reg != src_reg
4705 /* This must be the only place where the register is set. */
4706 && (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) == 1
4707 /* or all sets must be consecutive and make a giv. */
4708 || (benefit = consec_sets_giv (loop, benefit, p,
4710 &add_val, &mult_val, &ext_val,
4711 &last_consec_insn))))
4714 = (struct induction *) xmalloc (sizeof (struct induction));
4716 /* If this is a library call, increase benefit. */
4717 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4718 benefit += libcall_benefit (p);
4720 /* Skip the consecutive insns, if there are any. */
4721 if (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) != 1)
4722 p = last_consec_insn;
4724 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4725 ext_val, benefit, DEST_REG, not_every_iteration,
4726 maybe_multiple, NULL_PTR);
4731 #ifndef DONT_REDUCE_ADDR
4732 /* Look for givs which are memory addresses. */
4733 /* This resulted in worse code on a VAX 8600. I wonder if it
4735 if (GET_CODE (p) == INSN)
4736 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4740 /* Update the status of whether giv can derive other givs. This can
4741 change when we pass a label or an insn that updates a biv. */
4742 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4743 || GET_CODE (p) == CODE_LABEL)
4744 update_giv_derive (loop, p);
4748 /* Return 1 if X is a valid source for an initial value (or as value being
4749 compared against in an initial test).
4751 X must be either a register or constant and must not be clobbered between
4752 the current insn and the start of the loop.
4754 INSN is the insn containing X. */
4757 valid_initial_value_p (x, insn, call_seen, loop_start)
4766 /* Only consider pseudos we know about initialized in insns whose luids
4768 if (GET_CODE (x) != REG
4769 || REGNO (x) >= max_reg_before_loop)
4772 /* Don't use call-clobbered registers across a call which clobbers it. On
4773 some machines, don't use any hard registers at all. */
4774 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4775 && (SMALL_REGISTER_CLASSES
4776 || (call_used_regs[REGNO (x)] && call_seen)))
4779 /* Don't use registers that have been clobbered before the start of the
4781 if (reg_set_between_p (x, insn, loop_start))
4787 /* Scan X for memory refs and check each memory address
4788 as a possible giv. INSN is the insn whose pattern X comes from.
4789 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4790 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4791 more thanonce in each loop iteration. */
4794 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4795 const struct loop *loop;
4798 int not_every_iteration, maybe_multiple;
4801 register enum rtx_code code;
4802 register const char *fmt;
4807 code = GET_CODE (x);
4832 /* This code used to disable creating GIVs with mult_val == 1 and
4833 add_val == 0. However, this leads to lost optimizations when
4834 it comes time to combine a set of related DEST_ADDR GIVs, since
4835 this one would not be seen. */
4837 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4838 &mult_val, &ext_val, 1, &benefit,
4841 /* Found one; record it. */
4843 = (struct induction *) xmalloc (sizeof (struct induction));
4845 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4846 add_val, ext_val, benefit, DEST_ADDR,
4847 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4849 v->mem_mode = GET_MODE (x);
4858 /* Recursively scan the subexpressions for other mem refs. */
4860 fmt = GET_RTX_FORMAT (code);
4861 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4863 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4865 else if (fmt[i] == 'E')
4866 for (j = 0; j < XVECLEN (x, i); j++)
4867 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4871 /* Fill in the data about one biv update.
4872 V is the `struct induction' in which we record the biv. (It is
4873 allocated by the caller, with alloca.)
4874 INSN is the insn that sets it.
4875 DEST_REG is the biv's reg.
4877 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4878 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4879 being set to INC_VAL.
4881 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4882 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4883 can be executed more than once per iteration. If MAYBE_MULTIPLE
4884 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4885 executed exactly once per iteration. */
4888 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4889 not_every_iteration, maybe_multiple)
4891 struct induction *v;
4897 int not_every_iteration;
4900 struct loop_ivs *ivs = LOOP_IVS (loop);
4901 struct iv_class *bl;
4904 v->src_reg = dest_reg;
4905 v->dest_reg = dest_reg;
4906 v->mult_val = mult_val;
4907 v->add_val = inc_val;
4908 v->ext_dependant = NULL_RTX;
4909 v->location = location;
4910 v->mode = GET_MODE (dest_reg);
4911 v->always_computable = ! not_every_iteration;
4912 v->always_executed = ! not_every_iteration;
4913 v->maybe_multiple = maybe_multiple;
4915 /* Add this to the reg's iv_class, creating a class
4916 if this is the first incrementation of the reg. */
4918 bl = ivs->reg_biv_class[REGNO (dest_reg)];
4921 /* Create and initialize new iv_class. */
4923 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4925 bl->regno = REGNO (dest_reg);
4931 /* Set initial value to the reg itself. */
4932 bl->initial_value = dest_reg;
4933 bl->final_value = 0;
4934 /* We haven't seen the initializing insn yet */
4937 bl->initial_test = 0;
4938 bl->incremented = 0;
4942 bl->total_benefit = 0;
4944 /* Add this class to ivs->loop_iv_list. */
4945 bl->next = ivs->loop_iv_list;
4946 ivs->loop_iv_list = bl;
4948 /* Put it in the array of biv register classes. */
4949 ivs->reg_biv_class[REGNO (dest_reg)] = bl;
4952 /* Update IV_CLASS entry for this biv. */
4953 v->next_iv = bl->biv;
4956 if (mult_val == const1_rtx)
4957 bl->incremented = 1;
4959 if (loop_dump_stream)
4961 fprintf (loop_dump_stream,
4962 "Insn %d: possible biv, reg %d,",
4963 INSN_UID (insn), REGNO (dest_reg));
4964 if (GET_CODE (inc_val) == CONST_INT)
4966 fprintf (loop_dump_stream, " const =");
4967 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4968 fputc ('\n', loop_dump_stream);
4972 fprintf (loop_dump_stream, " const = ");
4973 print_rtl (loop_dump_stream, inc_val);
4974 fprintf (loop_dump_stream, "\n");
4979 /* Fill in the data about one giv.
4980 V is the `struct induction' in which we record the giv. (It is
4981 allocated by the caller, with alloca.)
4982 INSN is the insn that sets it.
4983 BENEFIT estimates the savings from deleting this insn.
4984 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4985 into a register or is used as a memory address.
4987 SRC_REG is the biv reg which the giv is computed from.
4988 DEST_REG is the giv's reg (if the giv is stored in a reg).
4989 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4990 LOCATION points to the place where this giv's value appears in INSN. */
4993 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4994 benefit, type, not_every_iteration, maybe_multiple, location)
4995 const struct loop *loop;
4996 struct induction *v;
5000 rtx mult_val, add_val, ext_val;
5003 int not_every_iteration, maybe_multiple;
5006 struct loop_ivs *ivs = LOOP_IVS (loop);
5007 struct induction *b;
5008 struct iv_class *bl;
5009 rtx set = single_set (insn);
5012 /* Attempt to prove constantness of the values. */
5013 temp = simplify_rtx (add_val);
5018 v->src_reg = src_reg;
5020 v->dest_reg = dest_reg;
5021 v->mult_val = mult_val;
5022 v->add_val = add_val;
5023 v->ext_dependant = ext_val;
5024 v->benefit = benefit;
5025 v->location = location;
5027 v->combined_with = 0;
5028 v->maybe_multiple = maybe_multiple;
5030 v->derive_adjustment = 0;
5036 v->auto_inc_opt = 0;
5040 /* The v->always_computable field is used in update_giv_derive, to
5041 determine whether a giv can be used to derive another giv. For a
5042 DEST_REG giv, INSN computes a new value for the giv, so its value
5043 isn't computable if INSN insn't executed every iteration.
5044 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5045 it does not compute a new value. Hence the value is always computable
5046 regardless of whether INSN is executed each iteration. */
5048 if (type == DEST_ADDR)
5049 v->always_computable = 1;
5051 v->always_computable = ! not_every_iteration;
5053 v->always_executed = ! not_every_iteration;
5055 if (type == DEST_ADDR)
5057 v->mode = GET_MODE (*location);
5060 else /* type == DEST_REG */
5062 v->mode = GET_MODE (SET_DEST (set));
5064 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
5066 /* If the lifetime is zero, it means that this register is
5067 really a dead store. So mark this as a giv that can be
5068 ignored. This will not prevent the biv from being eliminated. */
5069 if (v->lifetime == 0)
5072 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
5073 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
5076 /* Add the giv to the class of givs computed from one biv. */
5078 bl = ivs->reg_biv_class[REGNO (src_reg)];
5081 v->next_iv = bl->giv;
5083 /* Don't count DEST_ADDR. This is supposed to count the number of
5084 insns that calculate givs. */
5085 if (type == DEST_REG)
5087 bl->total_benefit += benefit;
5090 /* Fatal error, biv missing for this giv? */
5093 if (type == DEST_ADDR)
5097 /* The giv can be replaced outright by the reduced register only if all
5098 of the following conditions are true:
5099 - the insn that sets the giv is always executed on any iteration
5100 on which the giv is used at all
5101 (there are two ways to deduce this:
5102 either the insn is executed on every iteration,
5103 or all uses follow that insn in the same basic block),
5104 - the giv is not used outside the loop
5105 - no assignments to the biv occur during the giv's lifetime. */
5107 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
5108 /* Previous line always fails if INSN was moved by loop opt. */
5109 && REGNO_LAST_LUID (REGNO (dest_reg))
5110 < INSN_LUID (loop->end)
5111 && (! not_every_iteration
5112 || last_use_this_basic_block (dest_reg, insn)))
5114 /* Now check that there are no assignments to the biv within the
5115 giv's lifetime. This requires two separate checks. */
5117 /* Check each biv update, and fail if any are between the first
5118 and last use of the giv.
5120 If this loop contains an inner loop that was unrolled, then
5121 the insn modifying the biv may have been emitted by the loop
5122 unrolling code, and hence does not have a valid luid. Just
5123 mark the biv as not replaceable in this case. It is not very
5124 useful as a biv, because it is used in two different loops.
5125 It is very unlikely that we would be able to optimize the giv
5126 using this biv anyways. */
5129 for (b = bl->biv; b; b = b->next_iv)
5131 if (INSN_UID (b->insn) >= max_uid_for_loop
5132 || ((INSN_LUID (b->insn)
5133 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5134 && (INSN_LUID (b->insn)
5135 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5138 v->not_replaceable = 1;
5143 /* If there are any backwards branches that go from after the
5144 biv update to before it, then this giv is not replaceable. */
5146 for (b = bl->biv; b; b = b->next_iv)
5147 if (back_branch_in_range_p (loop, b->insn))
5150 v->not_replaceable = 1;
5156 /* May still be replaceable, we don't have enough info here to
5159 v->not_replaceable = 0;
5163 /* Record whether the add_val contains a const_int, for later use by
5168 v->no_const_addval = 1;
5169 if (tem == const0_rtx)
5171 else if (CONSTANT_P (add_val))
5172 v->no_const_addval = 0;
5173 if (GET_CODE (tem) == PLUS)
5177 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5178 tem = XEXP (tem, 0);
5179 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5180 tem = XEXP (tem, 1);
5184 if (CONSTANT_P (XEXP (tem, 1)))
5185 v->no_const_addval = 0;
5189 if (loop_dump_stream)
5191 if (type == DEST_REG)
5192 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5193 INSN_UID (insn), REGNO (dest_reg));
5195 fprintf (loop_dump_stream, "Insn %d: dest address",
5198 fprintf (loop_dump_stream, " src reg %d benefit %d",
5199 REGNO (src_reg), v->benefit);
5200 fprintf (loop_dump_stream, " lifetime %d",
5204 fprintf (loop_dump_stream, " replaceable");
5206 if (v->no_const_addval)
5207 fprintf (loop_dump_stream, " ncav");
5209 if (v->ext_dependant)
5211 switch (GET_CODE (v->ext_dependant))
5214 fprintf (loop_dump_stream, " ext se");
5217 fprintf (loop_dump_stream, " ext ze");
5220 fprintf (loop_dump_stream, " ext tr");
5227 if (GET_CODE (mult_val) == CONST_INT)
5229 fprintf (loop_dump_stream, " mult ");
5230 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5234 fprintf (loop_dump_stream, " mult ");
5235 print_rtl (loop_dump_stream, mult_val);
5238 if (GET_CODE (add_val) == CONST_INT)
5240 fprintf (loop_dump_stream, " add ");
5241 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5245 fprintf (loop_dump_stream, " add ");
5246 print_rtl (loop_dump_stream, add_val);
5250 if (loop_dump_stream)
5251 fprintf (loop_dump_stream, "\n");
5255 /* All this does is determine whether a giv can be made replaceable because
5256 its final value can be calculated. This code can not be part of record_giv
5257 above, because final_giv_value requires that the number of loop iterations
5258 be known, and that can not be accurately calculated until after all givs
5259 have been identified. */
5262 check_final_value (loop, v)
5263 const struct loop *loop;
5264 struct induction *v;
5266 struct loop_ivs *ivs = LOOP_IVS (loop);
5267 struct iv_class *bl;
5268 rtx final_value = 0;
5270 bl = ivs->reg_biv_class[REGNO (v->src_reg)];
5272 /* DEST_ADDR givs will never reach here, because they are always marked
5273 replaceable above in record_giv. */
5275 /* The giv can be replaced outright by the reduced register only if all
5276 of the following conditions are true:
5277 - the insn that sets the giv is always executed on any iteration
5278 on which the giv is used at all
5279 (there are two ways to deduce this:
5280 either the insn is executed on every iteration,
5281 or all uses follow that insn in the same basic block),
5282 - its final value can be calculated (this condition is different
5283 than the one above in record_giv)
5284 - it's not used before the it's set
5285 - no assignments to the biv occur during the giv's lifetime. */
5288 /* This is only called now when replaceable is known to be false. */
5289 /* Clear replaceable, so that it won't confuse final_giv_value. */
5293 if ((final_value = final_giv_value (loop, v))
5294 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5296 int biv_increment_seen = 0, before_giv_insn = 0;
5302 /* When trying to determine whether or not a biv increment occurs
5303 during the lifetime of the giv, we can ignore uses of the variable
5304 outside the loop because final_value is true. Hence we can not
5305 use regno_last_uid and regno_first_uid as above in record_giv. */
5307 /* Search the loop to determine whether any assignments to the
5308 biv occur during the giv's lifetime. Start with the insn
5309 that sets the giv, and search around the loop until we come
5310 back to that insn again.
5312 Also fail if there is a jump within the giv's lifetime that jumps
5313 to somewhere outside the lifetime but still within the loop. This
5314 catches spaghetti code where the execution order is not linear, and
5315 hence the above test fails. Here we assume that the giv lifetime
5316 does not extend from one iteration of the loop to the next, so as
5317 to make the test easier. Since the lifetime isn't known yet,
5318 this requires two loops. See also record_giv above. */
5320 last_giv_use = v->insn;
5327 before_giv_insn = 1;
5328 p = NEXT_INSN (loop->start);
5333 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5334 || GET_CODE (p) == CALL_INSN)
5336 /* It is possible for the BIV increment to use the GIV if we
5337 have a cycle. Thus we must be sure to check each insn for
5338 both BIV and GIV uses, and we must check for BIV uses
5341 if (! biv_increment_seen
5342 && reg_set_p (v->src_reg, PATTERN (p)))
5343 biv_increment_seen = 1;
5345 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5347 if (biv_increment_seen || before_giv_insn)
5350 v->not_replaceable = 1;
5358 /* Now that the lifetime of the giv is known, check for branches
5359 from within the lifetime to outside the lifetime if it is still
5369 p = NEXT_INSN (loop->start);
5370 if (p == last_giv_use)
5373 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5374 && LABEL_NAME (JUMP_LABEL (p))
5375 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5376 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5377 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5378 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5381 v->not_replaceable = 1;
5383 if (loop_dump_stream)
5384 fprintf (loop_dump_stream,
5385 "Found branch outside giv lifetime.\n");
5392 /* If it is replaceable, then save the final value. */
5394 v->final_value = final_value;
5397 if (loop_dump_stream && v->replaceable)
5398 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5399 INSN_UID (v->insn), REGNO (v->dest_reg));
5402 /* Update the status of whether a giv can derive other givs.
5404 We need to do something special if there is or may be an update to the biv
5405 between the time the giv is defined and the time it is used to derive
5408 In addition, a giv that is only conditionally set is not allowed to
5409 derive another giv once a label has been passed.
5411 The cases we look at are when a label or an update to a biv is passed. */
5414 update_giv_derive (loop, p)
5415 const struct loop *loop;
5418 struct loop_ivs *ivs = LOOP_IVS (loop);
5419 struct iv_class *bl;
5420 struct induction *biv, *giv;
5424 /* Search all IV classes, then all bivs, and finally all givs.
5426 There are three cases we are concerned with. First we have the situation
5427 of a giv that is only updated conditionally. In that case, it may not
5428 derive any givs after a label is passed.
5430 The second case is when a biv update occurs, or may occur, after the
5431 definition of a giv. For certain biv updates (see below) that are
5432 known to occur between the giv definition and use, we can adjust the
5433 giv definition. For others, or when the biv update is conditional,
5434 we must prevent the giv from deriving any other givs. There are two
5435 sub-cases within this case.
5437 If this is a label, we are concerned with any biv update that is done
5438 conditionally, since it may be done after the giv is defined followed by
5439 a branch here (actually, we need to pass both a jump and a label, but
5440 this extra tracking doesn't seem worth it).
5442 If this is a jump, we are concerned about any biv update that may be
5443 executed multiple times. We are actually only concerned about
5444 backward jumps, but it is probably not worth performing the test
5445 on the jump again here.
5447 If this is a biv update, we must adjust the giv status to show that a
5448 subsequent biv update was performed. If this adjustment cannot be done,
5449 the giv cannot derive further givs. */
5451 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
5452 for (biv = bl->biv; biv; biv = biv->next_iv)
5453 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5456 for (giv = bl->giv; giv; giv = giv->next_iv)
5458 /* If cant_derive is already true, there is no point in
5459 checking all of these conditions again. */
5460 if (giv->cant_derive)
5463 /* If this giv is conditionally set and we have passed a label,
5464 it cannot derive anything. */
5465 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5466 giv->cant_derive = 1;
5468 /* Skip givs that have mult_val == 0, since
5469 they are really invariants. Also skip those that are
5470 replaceable, since we know their lifetime doesn't contain
5472 else if (giv->mult_val == const0_rtx || giv->replaceable)
5475 /* The only way we can allow this giv to derive another
5476 is if this is a biv increment and we can form the product
5477 of biv->add_val and giv->mult_val. In this case, we will
5478 be able to compute a compensation. */
5479 else if (biv->insn == p)
5484 if (biv->mult_val == const1_rtx)
5485 tem = simplify_giv_expr (loop,
5486 gen_rtx_MULT (giv->mode,
5489 &ext_val_dummy, &dummy);
5491 if (tem && giv->derive_adjustment)
5492 tem = simplify_giv_expr
5494 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5495 &ext_val_dummy, &dummy);
5498 giv->derive_adjustment = tem;
5500 giv->cant_derive = 1;
5502 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5503 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5504 giv->cant_derive = 1;
5509 /* Check whether an insn is an increment legitimate for a basic induction var.
5510 X is the source of insn P, or a part of it.
5511 MODE is the mode in which X should be interpreted.
5513 DEST_REG is the putative biv, also the destination of the insn.
5514 We accept patterns of these forms:
5515 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5516 REG = INVARIANT + REG
5518 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5519 store the additive term into *INC_VAL, and store the place where
5520 we found the additive term into *LOCATION.
5522 If X is an assignment of an invariant into DEST_REG, we set
5523 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5525 We also want to detect a BIV when it corresponds to a variable
5526 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5527 of the variable may be a PLUS that adds a SUBREG of that variable to
5528 an invariant and then sign- or zero-extends the result of the PLUS
5531 Most GIVs in such cases will be in the promoted mode, since that is the
5532 probably the natural computation mode (and almost certainly the mode
5533 used for addresses) on the machine. So we view the pseudo-reg containing
5534 the variable as the BIV, as if it were simply incremented.
5536 Note that treating the entire pseudo as a BIV will result in making
5537 simple increments to any GIVs based on it. However, if the variable
5538 overflows in its declared mode but not its promoted mode, the result will
5539 be incorrect. This is acceptable if the variable is signed, since
5540 overflows in such cases are undefined, but not if it is unsigned, since
5541 those overflows are defined. So we only check for SIGN_EXTEND and
5544 If we cannot find a biv, we return 0. */
5547 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5548 const struct loop *loop;
5550 enum machine_mode mode;
5557 register enum rtx_code code;
5561 code = GET_CODE (x);
5566 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5567 || (GET_CODE (XEXP (x, 0)) == SUBREG
5568 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5569 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5571 argp = &XEXP (x, 1);
5573 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5574 || (GET_CODE (XEXP (x, 1)) == SUBREG
5575 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5576 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5578 argp = &XEXP (x, 0);
5584 if (loop_invariant_p (loop, arg) != 1)
5587 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5588 *mult_val = const1_rtx;
5593 /* If this is a SUBREG for a promoted variable, check the inner
5595 if (SUBREG_PROMOTED_VAR_P (x))
5596 return basic_induction_var (loop, SUBREG_REG (x),
5597 GET_MODE (SUBREG_REG (x)),
5598 dest_reg, p, inc_val, mult_val, location);
5602 /* If this register is assigned in a previous insn, look at its
5603 source, but don't go outside the loop or past a label. */
5605 /* If this sets a register to itself, we would repeat any previous
5606 biv increment if we applied this strategy blindly. */
5607 if (rtx_equal_p (dest_reg, x))
5616 insn = PREV_INSN (insn);
5618 while (insn && GET_CODE (insn) == NOTE
5619 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5623 set = single_set (insn);
5626 dest = SET_DEST (set);
5628 || (GET_CODE (dest) == SUBREG
5629 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5630 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5631 && SUBREG_REG (dest) == x))
5632 return basic_induction_var (loop, SET_SRC (set),
5633 (GET_MODE (SET_SRC (set)) == VOIDmode
5635 : GET_MODE (SET_SRC (set))),
5637 inc_val, mult_val, location);
5639 while (GET_CODE (dest) == SIGN_EXTRACT
5640 || GET_CODE (dest) == ZERO_EXTRACT
5641 || GET_CODE (dest) == SUBREG
5642 || GET_CODE (dest) == STRICT_LOW_PART)
5643 dest = XEXP (dest, 0);
5649 /* Can accept constant setting of biv only when inside inner most loop.
5650 Otherwise, a biv of an inner loop may be incorrectly recognized
5651 as a biv of the outer loop,
5652 causing code to be moved INTO the inner loop. */
5654 if (loop_invariant_p (loop, x) != 1)
5659 /* convert_modes aborts if we try to convert to or from CCmode, so just
5660 exclude that case. It is very unlikely that a condition code value
5661 would be a useful iterator anyways. */
5662 if (loop->level == 1
5663 && GET_MODE_CLASS (mode) != MODE_CC
5664 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5666 /* Possible bug here? Perhaps we don't know the mode of X. */
5667 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5668 *mult_val = const0_rtx;
5675 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5676 dest_reg, p, inc_val, mult_val, location);
5679 /* Similar, since this can be a sign extension. */
5680 for (insn = PREV_INSN (p);
5681 (insn && GET_CODE (insn) == NOTE
5682 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5683 insn = PREV_INSN (insn))
5687 set = single_set (insn);
5689 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5690 && set && SET_DEST (set) == XEXP (x, 0)
5691 && GET_CODE (XEXP (x, 1)) == CONST_INT
5692 && INTVAL (XEXP (x, 1)) >= 0
5693 && GET_CODE (SET_SRC (set)) == ASHIFT
5694 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5695 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5696 GET_MODE (XEXP (x, 0)),
5697 dest_reg, insn, inc_val, mult_val,
5706 /* A general induction variable (giv) is any quantity that is a linear
5707 function of a basic induction variable,
5708 i.e. giv = biv * mult_val + add_val.
5709 The coefficients can be any loop invariant quantity.
5710 A giv need not be computed directly from the biv;
5711 it can be computed by way of other givs. */
5713 /* Determine whether X computes a giv.
5714 If it does, return a nonzero value
5715 which is the benefit from eliminating the computation of X;
5716 set *SRC_REG to the register of the biv that it is computed from;
5717 set *ADD_VAL and *MULT_VAL to the coefficients,
5718 such that the value of X is biv * mult + add; */
5721 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5722 is_addr, pbenefit, addr_mode)
5723 const struct loop *loop;
5731 enum machine_mode addr_mode;
5733 struct loop_ivs *ivs = LOOP_IVS (loop);
5736 /* If this is an invariant, forget it, it isn't a giv. */
5737 if (loop_invariant_p (loop, x) == 1)
5741 *ext_val = NULL_RTX;
5742 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5746 switch (GET_CODE (x))
5750 /* Since this is now an invariant and wasn't before, it must be a giv
5751 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5753 *src_reg = ivs->loop_iv_list->biv->dest_reg;
5754 *mult_val = const0_rtx;
5759 /* This is equivalent to a BIV. */
5761 *mult_val = const1_rtx;
5762 *add_val = const0_rtx;
5766 /* Either (plus (biv) (invar)) or
5767 (plus (mult (biv) (invar_1)) (invar_2)). */
5768 if (GET_CODE (XEXP (x, 0)) == MULT)
5770 *src_reg = XEXP (XEXP (x, 0), 0);
5771 *mult_val = XEXP (XEXP (x, 0), 1);
5775 *src_reg = XEXP (x, 0);
5776 *mult_val = const1_rtx;
5778 *add_val = XEXP (x, 1);
5782 /* ADD_VAL is zero. */
5783 *src_reg = XEXP (x, 0);
5784 *mult_val = XEXP (x, 1);
5785 *add_val = const0_rtx;
5792 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5793 unless they are CONST_INT). */
5794 if (GET_CODE (*add_val) == USE)
5795 *add_val = XEXP (*add_val, 0);
5796 if (GET_CODE (*mult_val) == USE)
5797 *mult_val = XEXP (*mult_val, 0);
5800 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5802 *pbenefit += rtx_cost (orig_x, SET);
5804 /* Always return true if this is a giv so it will be detected as such,
5805 even if the benefit is zero or negative. This allows elimination
5806 of bivs that might otherwise not be eliminated. */
5810 /* Given an expression, X, try to form it as a linear function of a biv.
5811 We will canonicalize it to be of the form
5812 (plus (mult (BIV) (invar_1))
5814 with possible degeneracies.
5816 The invariant expressions must each be of a form that can be used as a
5817 machine operand. We surround then with a USE rtx (a hack, but localized
5818 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5819 routine; it is the caller's responsibility to strip them.
5821 If no such canonicalization is possible (i.e., two biv's are used or an
5822 expression that is neither invariant nor a biv or giv), this routine
5825 For a non-zero return, the result will have a code of CONST_INT, USE,
5826 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5828 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5830 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5831 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5834 simplify_giv_expr (loop, x, ext_val, benefit)
5835 const struct loop *loop;
5840 struct loop_ivs *ivs = LOOP_IVS (loop);
5841 struct loop_regs *regs = LOOP_REGS (loop);
5842 enum machine_mode mode = GET_MODE (x);
5846 /* If this is not an integer mode, or if we cannot do arithmetic in this
5847 mode, this can't be a giv. */
5848 if (mode != VOIDmode
5849 && (GET_MODE_CLASS (mode) != MODE_INT
5850 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5853 switch (GET_CODE (x))
5856 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5857 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5858 if (arg0 == 0 || arg1 == 0)
5861 /* Put constant last, CONST_INT last if both constant. */
5862 if ((GET_CODE (arg0) == USE
5863 || GET_CODE (arg0) == CONST_INT)
5864 && ! ((GET_CODE (arg0) == USE
5865 && GET_CODE (arg1) == USE)
5866 || GET_CODE (arg1) == CONST_INT))
5867 tem = arg0, arg0 = arg1, arg1 = tem;
5869 /* Handle addition of zero, then addition of an invariant. */
5870 if (arg1 == const0_rtx)
5872 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5873 switch (GET_CODE (arg0))
5877 /* Adding two invariants must result in an invariant, so enclose
5878 addition operation inside a USE and return it. */
5879 if (GET_CODE (arg0) == USE)
5880 arg0 = XEXP (arg0, 0);
5881 if (GET_CODE (arg1) == USE)
5882 arg1 = XEXP (arg1, 0);
5884 if (GET_CODE (arg0) == CONST_INT)
5885 tem = arg0, arg0 = arg1, arg1 = tem;
5886 if (GET_CODE (arg1) == CONST_INT)
5887 tem = sge_plus_constant (arg0, arg1);
5889 tem = sge_plus (mode, arg0, arg1);
5891 if (GET_CODE (tem) != CONST_INT)
5892 tem = gen_rtx_USE (mode, tem);
5897 /* biv + invar or mult + invar. Return sum. */
5898 return gen_rtx_PLUS (mode, arg0, arg1);
5901 /* (a + invar_1) + invar_2. Associate. */
5903 simplify_giv_expr (loop,
5915 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5916 MULT to reduce cases. */
5917 if (GET_CODE (arg0) == REG)
5918 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5919 if (GET_CODE (arg1) == REG)
5920 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5922 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5923 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5924 Recurse to associate the second PLUS. */
5925 if (GET_CODE (arg1) == MULT)
5926 tem = arg0, arg0 = arg1, arg1 = tem;
5928 if (GET_CODE (arg1) == PLUS)
5930 simplify_giv_expr (loop,
5932 gen_rtx_PLUS (mode, arg0,
5937 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5938 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5941 if (!rtx_equal_p (arg0, arg1))
5944 return simplify_giv_expr (loop,
5953 /* Handle "a - b" as "a + b * (-1)". */
5954 return simplify_giv_expr (loop,
5963 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5964 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5965 if (arg0 == 0 || arg1 == 0)
5968 /* Put constant last, CONST_INT last if both constant. */
5969 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5970 && GET_CODE (arg1) != CONST_INT)
5971 tem = arg0, arg0 = arg1, arg1 = tem;
5973 /* If second argument is not now constant, not giv. */
5974 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5977 /* Handle multiply by 0 or 1. */
5978 if (arg1 == const0_rtx)
5981 else if (arg1 == const1_rtx)
5984 switch (GET_CODE (arg0))
5987 /* biv * invar. Done. */
5988 return gen_rtx_MULT (mode, arg0, arg1);
5991 /* Product of two constants. */
5992 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5995 /* invar * invar is a giv, but attempt to simplify it somehow. */
5996 if (GET_CODE (arg1) != CONST_INT)
5999 arg0 = XEXP (arg0, 0);
6000 if (GET_CODE (arg0) == MULT)
6002 /* (invar_0 * invar_1) * invar_2. Associate. */
6003 return simplify_giv_expr (loop,
6012 /* Porpagate the MULT expressions to the intermost nodes. */
6013 else if (GET_CODE (arg0) == PLUS)
6015 /* (invar_0 + invar_1) * invar_2. Distribute. */
6016 return simplify_giv_expr (loop,
6028 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
6031 /* (a * invar_1) * invar_2. Associate. */
6032 return simplify_giv_expr (loop,
6041 /* (a + invar_1) * invar_2. Distribute. */
6042 return simplify_giv_expr (loop,
6057 /* Shift by constant is multiply by power of two. */
6058 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
6062 simplify_giv_expr (loop,
6065 GEN_INT ((HOST_WIDE_INT) 1
6066 << INTVAL (XEXP (x, 1)))),
6070 /* "-a" is "a * (-1)" */
6071 return simplify_giv_expr (loop,
6072 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
6076 /* "~a" is "-a - 1". Silly, but easy. */
6077 return simplify_giv_expr (loop,
6078 gen_rtx_MINUS (mode,
6079 gen_rtx_NEG (mode, XEXP (x, 0)),
6084 /* Already in proper form for invariant. */
6090 /* Conditionally recognize extensions of simple IVs. After we've
6091 computed loop traversal counts and verified the range of the
6092 source IV, we'll reevaluate this as a GIV. */
6093 if (*ext_val == NULL_RTX)
6095 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
6096 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
6098 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
6105 /* If this is a new register, we can't deal with it. */
6106 if (REGNO (x) >= max_reg_before_loop)
6109 /* Check for biv or giv. */
6110 switch (REG_IV_TYPE (ivs, REGNO (x)))
6114 case GENERAL_INDUCT:
6116 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
6118 /* Form expression from giv and add benefit. Ensure this giv
6119 can derive another and subtract any needed adjustment if so. */
6121 /* Increasing the benefit here is risky. The only case in which it
6122 is arguably correct is if this is the only use of V. In other
6123 cases, this will artificially inflate the benefit of the current
6124 giv, and lead to suboptimal code. Thus, it is disabled, since
6125 potentially not reducing an only marginally beneficial giv is
6126 less harmful than reducing many givs that are not really
6129 rtx single_use = VARRAY_RTX (regs->single_usage, REGNO (x));
6130 if (single_use && single_use != const0_rtx)
6131 *benefit += v->benefit;
6137 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
6138 v->src_reg, v->mult_val),
6141 if (v->derive_adjustment)
6142 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
6143 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
6146 if (!v->ext_dependant)
6151 *ext_val = v->ext_dependant;
6159 /* If it isn't an induction variable, and it is invariant, we
6160 may be able to simplify things further by looking through
6161 the bits we just moved outside the loop. */
6162 if (loop_invariant_p (loop, x) == 1)
6165 struct loop_movables *movables = LOOP_MOVABLES (loop);
6167 for (m = movables->head; m; m = m->next)
6168 if (rtx_equal_p (x, m->set_dest))
6170 /* Ok, we found a match. Substitute and simplify. */
6172 /* If we match another movable, we must use that, as
6173 this one is going away. */
6175 return simplify_giv_expr (loop, m->match->set_dest,
6178 /* If consec is non-zero, this is a member of a group of
6179 instructions that were moved together. We handle this
6180 case only to the point of seeking to the last insn and
6181 looking for a REG_EQUAL. Fail if we don't find one. */
6188 tem = NEXT_INSN (tem);
6192 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6194 tem = XEXP (tem, 0);
6198 tem = single_set (m->insn);
6200 tem = SET_SRC (tem);
6205 /* What we are most interested in is pointer
6206 arithmetic on invariants -- only take
6207 patterns we may be able to do something with. */
6208 if (GET_CODE (tem) == PLUS
6209 || GET_CODE (tem) == MULT
6210 || GET_CODE (tem) == ASHIFT
6211 || GET_CODE (tem) == CONST_INT
6212 || GET_CODE (tem) == SYMBOL_REF)
6214 tem = simplify_giv_expr (loop, tem, ext_val,
6219 else if (GET_CODE (tem) == CONST
6220 && GET_CODE (XEXP (tem, 0)) == PLUS
6221 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6222 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6224 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6236 /* Fall through to general case. */
6238 /* If invariant, return as USE (unless CONST_INT).
6239 Otherwise, not giv. */
6240 if (GET_CODE (x) == USE)
6243 if (loop_invariant_p (loop, x) == 1)
6245 if (GET_CODE (x) == CONST_INT)
6247 if (GET_CODE (x) == CONST
6248 && GET_CODE (XEXP (x, 0)) == PLUS
6249 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6250 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6252 return gen_rtx_USE (mode, x);
6259 /* This routine folds invariants such that there is only ever one
6260 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6263 sge_plus_constant (x, c)
6266 if (GET_CODE (x) == CONST_INT)
6267 return GEN_INT (INTVAL (x) + INTVAL (c));
6268 else if (GET_CODE (x) != PLUS)
6269 return gen_rtx_PLUS (GET_MODE (x), x, c);
6270 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6272 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6273 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6275 else if (GET_CODE (XEXP (x, 0)) == PLUS
6276 || GET_CODE (XEXP (x, 1)) != PLUS)
6278 return gen_rtx_PLUS (GET_MODE (x),
6279 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6283 return gen_rtx_PLUS (GET_MODE (x),
6284 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6289 sge_plus (mode, x, y)
6290 enum machine_mode mode;
6293 while (GET_CODE (y) == PLUS)
6295 rtx a = XEXP (y, 0);
6296 if (GET_CODE (a) == CONST_INT)
6297 x = sge_plus_constant (x, a);
6299 x = gen_rtx_PLUS (mode, x, a);
6302 if (GET_CODE (y) == CONST_INT)
6303 x = sge_plus_constant (x, y);
6305 x = gen_rtx_PLUS (mode, x, y);
6309 /* Help detect a giv that is calculated by several consecutive insns;
6313 The caller has already identified the first insn P as having a giv as dest;
6314 we check that all other insns that set the same register follow
6315 immediately after P, that they alter nothing else,
6316 and that the result of the last is still a giv.
6318 The value is 0 if the reg set in P is not really a giv.
6319 Otherwise, the value is the amount gained by eliminating
6320 all the consecutive insns that compute the value.
6322 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6323 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6325 The coefficients of the ultimate giv value are stored in
6326 *MULT_VAL and *ADD_VAL. */
6329 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6330 add_val, mult_val, ext_val, last_consec_insn)
6331 const struct loop *loop;
6339 rtx *last_consec_insn;
6341 struct loop_ivs *ivs = LOOP_IVS (loop);
6342 struct loop_regs *regs = LOOP_REGS (loop);
6349 /* Indicate that this is a giv so that we can update the value produced in
6350 each insn of the multi-insn sequence.
6352 This induction structure will be used only by the call to
6353 general_induction_var below, so we can allocate it on our stack.
6354 If this is a giv, our caller will replace the induct var entry with
6355 a new induction structure. */
6356 struct induction *v;
6358 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6361 v = (struct induction *) alloca (sizeof (struct induction));
6362 v->src_reg = src_reg;
6363 v->mult_val = *mult_val;
6364 v->add_val = *add_val;
6365 v->benefit = first_benefit;
6367 v->derive_adjustment = 0;
6368 v->ext_dependant = NULL_RTX;
6370 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6371 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6373 count = VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) - 1;
6378 code = GET_CODE (p);
6380 /* If libcall, skip to end of call sequence. */
6381 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6385 && (set = single_set (p))
6386 && GET_CODE (SET_DEST (set)) == REG
6387 && SET_DEST (set) == dest_reg
6388 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6389 add_val, mult_val, ext_val, 0,
6391 /* Giv created by equivalent expression. */
6392 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6393 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6394 add_val, mult_val, ext_val, 0,
6395 &benefit, VOIDmode)))
6396 && src_reg == v->src_reg)
6398 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6399 benefit += libcall_benefit (p);
6402 v->mult_val = *mult_val;
6403 v->add_val = *add_val;
6404 v->benefit += benefit;
6406 else if (code != NOTE)
6408 /* Allow insns that set something other than this giv to a
6409 constant. Such insns are needed on machines which cannot
6410 include long constants and should not disqualify a giv. */
6412 && (set = single_set (p))
6413 && SET_DEST (set) != dest_reg
6414 && CONSTANT_P (SET_SRC (set)))
6417 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6422 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6423 *last_consec_insn = p;
6427 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6428 represented by G1. If no such expression can be found, or it is clear that
6429 it cannot possibly be a valid address, 0 is returned.
6431 To perform the computation, we note that
6434 where `v' is the biv.
6436 So G2 = (y/b) * G1 + (b - a*y/x).
6438 Note that MULT = y/x.
6440 Update: A and B are now allowed to be additive expressions such that
6441 B contains all variables in A. That is, computing B-A will not require
6442 subtracting variables. */
6445 express_from_1 (a, b, mult)
6448 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6450 if (mult == const0_rtx)
6453 /* If MULT is not 1, we cannot handle A with non-constants, since we
6454 would then be required to subtract multiples of the registers in A.
6455 This is theoretically possible, and may even apply to some Fortran
6456 constructs, but it is a lot of work and we do not attempt it here. */
6458 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6461 /* In general these structures are sorted top to bottom (down the PLUS
6462 chain), but not left to right across the PLUS. If B is a higher
6463 order giv than A, we can strip one level and recurse. If A is higher
6464 order, we'll eventually bail out, but won't know that until the end.
6465 If they are the same, we'll strip one level around this loop. */
6467 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6469 rtx ra, rb, oa, ob, tmp;
6471 ra = XEXP (a, 0), oa = XEXP (a, 1);
6472 if (GET_CODE (ra) == PLUS)
6473 tmp = ra, ra = oa, oa = tmp;
6475 rb = XEXP (b, 0), ob = XEXP (b, 1);
6476 if (GET_CODE (rb) == PLUS)
6477 tmp = rb, rb = ob, ob = tmp;
6479 if (rtx_equal_p (ra, rb))
6480 /* We matched: remove one reg completely. */
6482 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6483 /* An alternate match. */
6485 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6486 /* An alternate match. */
6490 /* Indicates an extra register in B. Strip one level from B and
6491 recurse, hoping B was the higher order expression. */
6492 ob = express_from_1 (a, ob, mult);
6495 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6499 /* Here we are at the last level of A, go through the cases hoping to
6500 get rid of everything but a constant. */
6502 if (GET_CODE (a) == PLUS)
6506 ra = XEXP (a, 0), oa = XEXP (a, 1);
6507 if (rtx_equal_p (oa, b))
6509 else if (!rtx_equal_p (ra, b))
6512 if (GET_CODE (oa) != CONST_INT)
6515 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6517 else if (GET_CODE (a) == CONST_INT)
6519 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6521 else if (CONSTANT_P (a))
6523 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6525 else if (GET_CODE (b) == PLUS)
6527 if (rtx_equal_p (a, XEXP (b, 0)))
6529 else if (rtx_equal_p (a, XEXP (b, 1)))
6534 else if (rtx_equal_p (a, b))
6541 express_from (g1, g2)
6542 struct induction *g1, *g2;
6546 /* The value that G1 will be multiplied by must be a constant integer. Also,
6547 the only chance we have of getting a valid address is if b*c/a (see above
6548 for notation) is also an integer. */
6549 if (GET_CODE (g1->mult_val) == CONST_INT
6550 && GET_CODE (g2->mult_val) == CONST_INT)
6552 if (g1->mult_val == const0_rtx
6553 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6555 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6557 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6561 /* ??? Find out if the one is a multiple of the other? */
6565 add = express_from_1 (g1->add_val, g2->add_val, mult);
6566 if (add == NULL_RTX)
6568 /* Failed. If we've got a multiplication factor between G1 and G2,
6569 scale G1's addend and try again. */
6570 if (INTVAL (mult) > 1)
6572 rtx g1_add_val = g1->add_val;
6573 if (GET_CODE (g1_add_val) == MULT
6574 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6577 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6578 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6579 XEXP (g1_add_val, 0), GEN_INT (m));
6583 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6587 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6590 if (add == NULL_RTX)
6593 /* Form simplified final result. */
6594 if (mult == const0_rtx)
6596 else if (mult == const1_rtx)
6597 mult = g1->dest_reg;
6599 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6601 if (add == const0_rtx)
6605 if (GET_CODE (add) == PLUS
6606 && CONSTANT_P (XEXP (add, 1)))
6608 rtx tem = XEXP (add, 1);
6609 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6613 return gen_rtx_PLUS (g2->mode, mult, add);
6617 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6618 represented by G1. This indicates that G2 should be combined with G1 and
6619 that G2 can use (either directly or via an address expression) a register
6620 used to represent G1. */
6623 combine_givs_p (g1, g2)
6624 struct induction *g1, *g2;
6628 /* With the introduction of ext dependant givs, we must care for modes.
6629 G2 must not use a wider mode than G1. */
6630 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6633 ret = comb = express_from (g1, g2);
6634 if (comb == NULL_RTX)
6636 if (g1->mode != g2->mode)
6637 ret = gen_lowpart (g2->mode, comb);
6639 /* If these givs are identical, they can be combined. We use the results
6640 of express_from because the addends are not in a canonical form, so
6641 rtx_equal_p is a weaker test. */
6642 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6643 combination to be the other way round. */
6644 if (comb == g1->dest_reg
6645 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6650 /* If G2 can be expressed as a function of G1 and that function is valid
6651 as an address and no more expensive than using a register for G2,
6652 the expression of G2 in terms of G1 can be used. */
6654 && g2->giv_type == DEST_ADDR
6655 && memory_address_p (g2->mem_mode, ret)
6656 /* ??? Looses, especially with -fforce-addr, where *g2->location
6657 will always be a register, and so anything more complicated
6661 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6663 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6674 /* Check each extension dependant giv in this class to see if its
6675 root biv is safe from wrapping in the interior mode, which would
6676 make the giv illegal. */
6679 check_ext_dependant_givs (bl, loop_info)
6680 struct iv_class *bl;
6681 struct loop_info *loop_info;
6683 int ze_ok = 0, se_ok = 0, info_ok = 0;
6684 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6685 HOST_WIDE_INT start_val;
6686 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6688 struct induction *v;
6690 /* Make sure the iteration data is available. We must have
6691 constants in order to be certain of no overflow. */
6692 /* ??? An unknown iteration count with an increment of +-1
6693 combined with friendly exit tests of against an invariant
6694 value is also ameanable to optimization. Not implemented. */
6695 if (loop_info->n_iterations > 0
6696 && bl->initial_value
6697 && GET_CODE (bl->initial_value) == CONST_INT
6698 && (incr = biv_total_increment (bl))
6699 && GET_CODE (incr) == CONST_INT
6700 /* Make sure the host can represent the arithmetic. */
6701 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6703 unsigned HOST_WIDE_INT abs_incr, total_incr;
6704 HOST_WIDE_INT s_end_val;
6708 start_val = INTVAL (bl->initial_value);
6709 u_start_val = start_val;
6711 neg_incr = 0, abs_incr = INTVAL (incr);
6712 if (INTVAL (incr) < 0)
6713 neg_incr = 1, abs_incr = -abs_incr;
6714 total_incr = abs_incr * loop_info->n_iterations;
6716 /* Check for host arithmatic overflow. */
6717 if (total_incr / loop_info->n_iterations == abs_incr)
6719 unsigned HOST_WIDE_INT u_max;
6720 HOST_WIDE_INT s_max;
6722 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6723 s_end_val = u_end_val;
6724 u_max = GET_MODE_MASK (biv_mode);
6727 /* Check zero extension of biv ok. */
6729 /* Check for host arithmatic overflow. */
6731 ? u_end_val < u_start_val
6732 : u_end_val > u_start_val)
6733 /* Check for target arithmetic overflow. */
6735 ? 1 /* taken care of with host overflow */
6736 : u_end_val <= u_max))
6741 /* Check sign extension of biv ok. */
6742 /* ??? While it is true that overflow with signed and pointer
6743 arithmetic is undefined, I fear too many programmers don't
6744 keep this fact in mind -- myself included on occasion.
6745 So leave alone with the signed overflow optimizations. */
6746 if (start_val >= -s_max - 1
6747 /* Check for host arithmatic overflow. */
6749 ? s_end_val < start_val
6750 : s_end_val > start_val)
6751 /* Check for target arithmetic overflow. */
6753 ? s_end_val >= -s_max - 1
6754 : s_end_val <= s_max))
6761 /* Invalidate givs that fail the tests. */
6762 for (v = bl->giv; v; v = v->next_iv)
6763 if (v->ext_dependant)
6765 enum rtx_code code = GET_CODE (v->ext_dependant);
6778 /* We don't know whether this value is being used as either
6779 signed or unsigned, so to safely truncate we must satisfy
6780 both. The initial check here verifies the BIV itself;
6781 once that is successful we may check its range wrt the
6785 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6786 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6788 /* We know from the above that both endpoints are nonnegative,
6789 and that there is no wrapping. Verify that both endpoints
6790 are within the (signed) range of the outer mode. */
6791 if (u_start_val <= max && u_end_val <= max)
6802 if (loop_dump_stream)
6804 fprintf (loop_dump_stream,
6805 "Verified ext dependant giv at %d of reg %d\n",
6806 INSN_UID (v->insn), bl->regno);
6811 if (loop_dump_stream)
6816 why = "biv iteration values overflowed";
6820 incr = biv_total_increment (bl);
6821 if (incr == const1_rtx)
6822 why = "biv iteration info incomplete; incr by 1";
6824 why = "biv iteration info incomplete";
6827 fprintf (loop_dump_stream,
6828 "Failed ext dependant giv at %d, %s\n",
6829 INSN_UID (v->insn), why);
6836 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6839 extend_value_for_giv (v, value)
6840 struct induction *v;
6843 rtx ext_dep = v->ext_dependant;
6848 /* Recall that check_ext_dependant_givs verified that the known bounds
6849 of a biv did not overflow or wrap with respect to the extension for
6850 the giv. Therefore, constants need no additional adjustment. */
6851 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6854 /* Otherwise, we must adjust the value to compensate for the
6855 differing modes of the biv and the giv. */
6856 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6859 struct combine_givs_stats
6866 cmp_combine_givs_stats (xp, yp)
6870 const struct combine_givs_stats * const x =
6871 (const struct combine_givs_stats *) xp;
6872 const struct combine_givs_stats * const y =
6873 (const struct combine_givs_stats *) yp;
6875 d = y->total_benefit - x->total_benefit;
6876 /* Stabilize the sort. */
6878 d = x->giv_number - y->giv_number;
6882 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6883 any other. If so, point SAME to the giv combined with and set NEW_REG to
6884 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6885 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6888 combine_givs (regs, bl)
6889 struct loop_regs *regs;
6890 struct iv_class *bl;
6892 /* Additional benefit to add for being combined multiple times. */
6893 const int extra_benefit = 3;
6895 struct induction *g1, *g2, **giv_array;
6896 int i, j, k, giv_count;
6897 struct combine_givs_stats *stats;
6900 /* Count givs, because bl->giv_count is incorrect here. */
6902 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6907 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6909 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6911 giv_array[i++] = g1;
6913 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6914 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6916 for (i = 0; i < giv_count; i++)
6922 stats[i].giv_number = i;
6924 /* If a DEST_REG GIV is used only once, do not allow it to combine
6925 with anything, for in doing so we will gain nothing that cannot
6926 be had by simply letting the GIV with which we would have combined
6927 to be reduced on its own. The losage shows up in particular with
6928 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6929 be seen elsewhere as well. */
6930 if (g1->giv_type == DEST_REG
6931 && (single_use = VARRAY_RTX (regs->single_usage,
6932 REGNO (g1->dest_reg)))
6933 && single_use != const0_rtx)
6936 this_benefit = g1->benefit;
6937 /* Add an additional weight for zero addends. */
6938 if (g1->no_const_addval)
6941 for (j = 0; j < giv_count; j++)
6947 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6949 can_combine[i * giv_count + j] = this_combine;
6950 this_benefit += g2->benefit + extra_benefit;
6953 stats[i].total_benefit = this_benefit;
6956 /* Iterate, combining until we can't. */
6958 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6960 if (loop_dump_stream)
6962 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6963 for (k = 0; k < giv_count; k++)
6965 g1 = giv_array[stats[k].giv_number];
6966 if (!g1->combined_with && !g1->same)
6967 fprintf (loop_dump_stream, " {%d, %d}",
6968 INSN_UID (giv_array[stats[k].giv_number]->insn),
6969 stats[k].total_benefit);
6971 putc ('\n', loop_dump_stream);
6974 for (k = 0; k < giv_count; k++)
6976 int g1_add_benefit = 0;
6978 i = stats[k].giv_number;
6981 /* If it has already been combined, skip. */
6982 if (g1->combined_with || g1->same)
6985 for (j = 0; j < giv_count; j++)
6988 if (g1 != g2 && can_combine[i * giv_count + j]
6989 /* If it has already been combined, skip. */
6990 && ! g2->same && ! g2->combined_with)
6994 g2->new_reg = can_combine[i * giv_count + j];
6996 g1->combined_with++;
6997 g1->lifetime += g2->lifetime;
6999 g1_add_benefit += g2->benefit;
7001 /* ??? The new final_[bg]iv_value code does a much better job
7002 of finding replaceable giv's, and hence this code may no
7003 longer be necessary. */
7004 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
7005 g1_add_benefit -= copy_cost;
7007 /* To help optimize the next set of combinations, remove
7008 this giv from the benefits of other potential mates. */
7009 for (l = 0; l < giv_count; ++l)
7011 int m = stats[l].giv_number;
7012 if (can_combine[m * giv_count + j])
7013 stats[l].total_benefit -= g2->benefit + extra_benefit;
7016 if (loop_dump_stream)
7017 fprintf (loop_dump_stream,
7018 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
7019 INSN_UID (g2->insn), INSN_UID (g1->insn),
7020 g1->benefit, g1_add_benefit, g1->lifetime);
7024 /* To help optimize the next set of combinations, remove
7025 this giv from the benefits of other potential mates. */
7026 if (g1->combined_with)
7028 for (j = 0; j < giv_count; ++j)
7030 int m = stats[j].giv_number;
7031 if (can_combine[m * giv_count + i])
7032 stats[j].total_benefit -= g1->benefit + extra_benefit;
7035 g1->benefit += g1_add_benefit;
7037 /* We've finished with this giv, and everything it touched.
7038 Restart the combination so that proper weights for the
7039 rest of the givs are properly taken into account. */
7040 /* ??? Ideally we would compact the arrays at this point, so
7041 as to not cover old ground. But sanely compacting
7042 can_combine is tricky. */
7052 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
7055 emit_iv_add_mult (b, m, a, reg, insert_before)
7056 rtx b; /* initial value of basic induction variable */
7057 rtx m; /* multiplicative constant */
7058 rtx a; /* additive constant */
7059 rtx reg; /* destination register */
7065 /* Prevent unexpected sharing of these rtx. */
7069 /* Increase the lifetime of any invariants moved further in code. */
7070 update_reg_last_use (a, insert_before);
7071 update_reg_last_use (b, insert_before);
7072 update_reg_last_use (m, insert_before);
7075 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
7077 emit_move_insn (reg, result);
7078 seq = gen_sequence ();
7081 emit_insn_before (seq, insert_before);
7083 /* It is entirely possible that the expansion created lots of new
7084 registers. Iterate over the sequence we just created and
7087 if (GET_CODE (seq) == SEQUENCE)
7090 for (i = 0; i < XVECLEN (seq, 0); ++i)
7092 rtx set = single_set (XVECEXP (seq, 0, i));
7093 if (set && GET_CODE (SET_DEST (set)) == REG)
7094 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
7097 else if (GET_CODE (seq) == SET
7098 && GET_CODE (SET_DEST (seq)) == REG)
7099 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
7102 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
7105 iv_add_mult_cost (b, m, a, reg)
7106 rtx b; /* initial value of basic induction variable */
7107 rtx m; /* multiplicative constant */
7108 rtx a; /* additive constant */
7109 rtx reg; /* destination register */
7115 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
7117 emit_move_insn (reg, result);
7118 last = get_last_insn ();
7121 rtx t = single_set (last);
7123 cost += rtx_cost (SET_SRC (t), SET);
7124 last = PREV_INSN (last);
7130 /* Test whether A * B can be computed without
7131 an actual multiply insn. Value is 1 if so. */
7134 product_cheap_p (a, b)
7142 /* If only one is constant, make it B. */
7143 if (GET_CODE (a) == CONST_INT)
7144 tmp = a, a = b, b = tmp;
7146 /* If first constant, both constant, so don't need multiply. */
7147 if (GET_CODE (a) == CONST_INT)
7150 /* If second not constant, neither is constant, so would need multiply. */
7151 if (GET_CODE (b) != CONST_INT)
7154 /* One operand is constant, so might not need multiply insn. Generate the
7155 code for the multiply and see if a call or multiply, or long sequence
7156 of insns is generated. */
7159 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
7160 tmp = gen_sequence ();
7163 if (GET_CODE (tmp) == SEQUENCE)
7165 if (XVEC (tmp, 0) == 0)
7167 else if (XVECLEN (tmp, 0) > 3)
7170 for (i = 0; i < XVECLEN (tmp, 0); i++)
7172 rtx insn = XVECEXP (tmp, 0, i);
7174 if (GET_CODE (insn) != INSN
7175 || (GET_CODE (PATTERN (insn)) == SET
7176 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
7177 || (GET_CODE (PATTERN (insn)) == PARALLEL
7178 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
7179 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7186 else if (GET_CODE (tmp) == SET
7187 && GET_CODE (SET_SRC (tmp)) == MULT)
7189 else if (GET_CODE (tmp) == PARALLEL
7190 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7191 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7197 /* Check to see if loop can be terminated by a "decrement and branch until
7198 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7199 Also try reversing an increment loop to a decrement loop
7200 to see if the optimization can be performed.
7201 Value is nonzero if optimization was performed. */
7203 /* This is useful even if the architecture doesn't have such an insn,
7204 because it might change a loops which increments from 0 to n to a loop
7205 which decrements from n to 0. A loop that decrements to zero is usually
7206 faster than one that increments from zero. */
7208 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7209 such as approx_final_value, biv_total_increment, loop_iterations, and
7210 final_[bg]iv_value. */
7213 check_dbra_loop (loop, insn_count)
7217 struct loop_info *loop_info = LOOP_INFO (loop);
7218 struct loop_regs *regs = LOOP_REGS (loop);
7219 struct loop_ivs *ivs = LOOP_IVS (loop);
7220 struct iv_class *bl;
7227 rtx before_comparison;
7231 int compare_and_branch;
7232 rtx loop_start = loop->start;
7233 rtx loop_end = loop->end;
7235 /* If last insn is a conditional branch, and the insn before tests a
7236 register value, try to optimize it. Otherwise, we can't do anything. */
7238 jump = PREV_INSN (loop_end);
7239 comparison = get_condition_for_loop (loop, jump);
7240 if (comparison == 0)
7242 if (!onlyjump_p (jump))
7245 /* Try to compute whether the compare/branch at the loop end is one or
7246 two instructions. */
7247 get_condition (jump, &first_compare);
7248 if (first_compare == jump)
7249 compare_and_branch = 1;
7250 else if (first_compare == prev_nonnote_insn (jump))
7251 compare_and_branch = 2;
7256 /* If more than one condition is present to control the loop, then
7257 do not proceed, as this function does not know how to rewrite
7258 loop tests with more than one condition.
7260 Look backwards from the first insn in the last comparison
7261 sequence and see if we've got another comparison sequence. */
7264 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7265 if (GET_CODE (jump1) == JUMP_INSN)
7269 /* Check all of the bivs to see if the compare uses one of them.
7270 Skip biv's set more than once because we can't guarantee that
7271 it will be zero on the last iteration. Also skip if the biv is
7272 used between its update and the test insn. */
7274 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
7276 if (bl->biv_count == 1
7277 && ! bl->biv->maybe_multiple
7278 && bl->biv->dest_reg == XEXP (comparison, 0)
7279 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7287 /* Look for the case where the basic induction variable is always
7288 nonnegative, and equals zero on the last iteration.
7289 In this case, add a reg_note REG_NONNEG, which allows the
7290 m68k DBRA instruction to be used. */
7292 if (((GET_CODE (comparison) == GT
7293 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7294 && INTVAL (XEXP (comparison, 1)) == -1)
7295 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7296 && GET_CODE (bl->biv->add_val) == CONST_INT
7297 && INTVAL (bl->biv->add_val) < 0)
7299 /* Initial value must be greater than 0,
7300 init_val % -dec_value == 0 to ensure that it equals zero on
7301 the last iteration */
7303 if (GET_CODE (bl->initial_value) == CONST_INT
7304 && INTVAL (bl->initial_value) > 0
7305 && (INTVAL (bl->initial_value)
7306 % (-INTVAL (bl->biv->add_val))) == 0)
7308 /* register always nonnegative, add REG_NOTE to branch */
7309 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7311 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7318 /* If the decrement is 1 and the value was tested as >= 0 before
7319 the loop, then we can safely optimize. */
7320 for (p = loop_start; p; p = PREV_INSN (p))
7322 if (GET_CODE (p) == CODE_LABEL)
7324 if (GET_CODE (p) != JUMP_INSN)
7327 before_comparison = get_condition_for_loop (loop, p);
7328 if (before_comparison
7329 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7330 && GET_CODE (before_comparison) == LT
7331 && XEXP (before_comparison, 1) == const0_rtx
7332 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7333 && INTVAL (bl->biv->add_val) == -1)
7335 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7337 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7345 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7346 && INTVAL (bl->biv->add_val) > 0)
7348 /* Try to change inc to dec, so can apply above optimization. */
7350 all registers modified are induction variables or invariant,
7351 all memory references have non-overlapping addresses
7352 (obviously true if only one write)
7353 allow 2 insns for the compare/jump at the end of the loop. */
7354 /* Also, we must avoid any instructions which use both the reversed
7355 biv and another biv. Such instructions will fail if the loop is
7356 reversed. We meet this condition by requiring that either
7357 no_use_except_counting is true, or else that there is only
7359 int num_nonfixed_reads = 0;
7360 /* 1 if the iteration var is used only to count iterations. */
7361 int no_use_except_counting = 0;
7362 /* 1 if the loop has no memory store, or it has a single memory store
7363 which is reversible. */
7364 int reversible_mem_store = 1;
7366 if (bl->giv_count == 0 && ! loop->exit_count)
7368 rtx bivreg = regno_reg_rtx[bl->regno];
7370 /* If there are no givs for this biv, and the only exit is the
7371 fall through at the end of the loop, then
7372 see if perhaps there are no uses except to count. */
7373 no_use_except_counting = 1;
7374 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7377 rtx set = single_set (p);
7379 if (set && GET_CODE (SET_DEST (set)) == REG
7380 && REGNO (SET_DEST (set)) == bl->regno)
7381 /* An insn that sets the biv is okay. */
7383 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7384 || p == prev_nonnote_insn (loop_end))
7385 && reg_mentioned_p (bivreg, PATTERN (p)))
7387 /* If either of these insns uses the biv and sets a pseudo
7388 that has more than one usage, then the biv has uses
7389 other than counting since it's used to derive a value
7390 that is used more than one time. */
7391 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7393 if (regs->multiple_uses)
7395 no_use_except_counting = 0;
7399 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7401 no_use_except_counting = 0;
7407 if (no_use_except_counting)
7408 /* No need to worry about MEMs. */
7410 else if (loop_info->num_mem_sets <= 1)
7412 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7414 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7416 /* If the loop has a single store, and the destination address is
7417 invariant, then we can't reverse the loop, because this address
7418 might then have the wrong value at loop exit.
7419 This would work if the source was invariant also, however, in that
7420 case, the insn should have been moved out of the loop. */
7422 if (loop_info->num_mem_sets == 1)
7424 struct induction *v;
7426 reversible_mem_store
7427 = (! loop_info->unknown_address_altered
7428 && ! loop_info->unknown_constant_address_altered
7429 && ! loop_invariant_p (loop,
7430 XEXP (XEXP (loop_info->store_mems, 0),
7433 /* If the store depends on a register that is set after the
7434 store, it depends on the initial value, and is thus not
7436 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7438 if (v->giv_type == DEST_REG
7439 && reg_mentioned_p (v->dest_reg,
7440 PATTERN (loop_info->first_loop_store_insn))
7441 && loop_insn_first_p (loop_info->first_loop_store_insn,
7443 reversible_mem_store = 0;
7450 /* This code only acts for innermost loops. Also it simplifies
7451 the memory address check by only reversing loops with
7452 zero or one memory access.
7453 Two memory accesses could involve parts of the same array,
7454 and that can't be reversed.
7455 If the biv is used only for counting, than we don't need to worry
7456 about all these things. */
7458 if ((num_nonfixed_reads <= 1
7459 && ! loop_info->has_call
7460 && ! loop_info->has_volatile
7461 && reversible_mem_store
7462 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7463 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7464 && (bl == ivs->loop_iv_list && bl->next == 0))
7465 || no_use_except_counting)
7469 /* Loop can be reversed. */
7470 if (loop_dump_stream)
7471 fprintf (loop_dump_stream, "Can reverse loop\n");
7473 /* Now check other conditions:
7475 The increment must be a constant, as must the initial value,
7476 and the comparison code must be LT.
7478 This test can probably be improved since +/- 1 in the constant
7479 can be obtained by changing LT to LE and vice versa; this is
7483 /* for constants, LE gets turned into LT */
7484 && (GET_CODE (comparison) == LT
7485 || (GET_CODE (comparison) == LE
7486 && no_use_except_counting)))
7488 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7489 rtx initial_value, comparison_value;
7491 enum rtx_code cmp_code;
7492 int comparison_const_width;
7493 unsigned HOST_WIDE_INT comparison_sign_mask;
7495 add_val = INTVAL (bl->biv->add_val);
7496 comparison_value = XEXP (comparison, 1);
7497 if (GET_MODE (comparison_value) == VOIDmode)
7498 comparison_const_width
7499 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7501 comparison_const_width
7502 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7503 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7504 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7505 comparison_sign_mask
7506 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7508 /* If the comparison value is not a loop invariant, then we
7509 can not reverse this loop.
7511 ??? If the insns which initialize the comparison value as
7512 a whole compute an invariant result, then we could move
7513 them out of the loop and proceed with loop reversal. */
7514 if (! loop_invariant_p (loop, comparison_value))
7517 if (GET_CODE (comparison_value) == CONST_INT)
7518 comparison_val = INTVAL (comparison_value);
7519 initial_value = bl->initial_value;
7521 /* Normalize the initial value if it is an integer and
7522 has no other use except as a counter. This will allow
7523 a few more loops to be reversed. */
7524 if (no_use_except_counting
7525 && GET_CODE (comparison_value) == CONST_INT
7526 && GET_CODE (initial_value) == CONST_INT)
7528 comparison_val = comparison_val - INTVAL (bl->initial_value);
7529 /* The code below requires comparison_val to be a multiple
7530 of add_val in order to do the loop reversal, so
7531 round up comparison_val to a multiple of add_val.
7532 Since comparison_value is constant, we know that the
7533 current comparison code is LT. */
7534 comparison_val = comparison_val + add_val - 1;
7536 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7537 /* We postpone overflow checks for COMPARISON_VAL here;
7538 even if there is an overflow, we might still be able to
7539 reverse the loop, if converting the loop exit test to
7541 initial_value = const0_rtx;
7544 /* First check if we can do a vanilla loop reversal. */
7545 if (initial_value == const0_rtx
7546 /* If we have a decrement_and_branch_on_count,
7547 prefer the NE test, since this will allow that
7548 instruction to be generated. Note that we must
7549 use a vanilla loop reversal if the biv is used to
7550 calculate a giv or has a non-counting use. */
7551 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7552 && defined (HAVE_decrement_and_branch_on_count)
7553 && (! (add_val == 1 && loop->vtop
7554 && (bl->biv_count == 0
7555 || no_use_except_counting)))
7557 && GET_CODE (comparison_value) == CONST_INT
7558 /* Now do postponed overflow checks on COMPARISON_VAL. */
7559 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7560 & comparison_sign_mask))
7562 /* Register will always be nonnegative, with value
7563 0 on last iteration */
7564 add_adjust = add_val;
7568 else if (add_val == 1 && loop->vtop
7569 && (bl->biv_count == 0
7570 || no_use_except_counting))
7578 if (GET_CODE (comparison) == LE)
7579 add_adjust -= add_val;
7581 /* If the initial value is not zero, or if the comparison
7582 value is not an exact multiple of the increment, then we
7583 can not reverse this loop. */
7584 if (initial_value == const0_rtx
7585 && GET_CODE (comparison_value) == CONST_INT)
7587 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7592 if (! no_use_except_counting || add_val != 1)
7596 final_value = comparison_value;
7598 /* Reset these in case we normalized the initial value
7599 and comparison value above. */
7600 if (GET_CODE (comparison_value) == CONST_INT
7601 && GET_CODE (initial_value) == CONST_INT)
7603 comparison_value = GEN_INT (comparison_val);
7605 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7607 bl->initial_value = initial_value;
7609 /* Save some info needed to produce the new insns. */
7610 reg = bl->biv->dest_reg;
7611 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7612 if (jump_label == pc_rtx)
7613 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7614 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7616 /* Set start_value; if this is not a CONST_INT, we need
7618 Initialize biv to start_value before loop start.
7619 The old initializing insn will be deleted as a
7620 dead store by flow.c. */
7621 if (initial_value == const0_rtx
7622 && GET_CODE (comparison_value) == CONST_INT)
7624 start_value = GEN_INT (comparison_val - add_adjust);
7625 emit_insn_before (gen_move_insn (reg, start_value),
7628 else if (GET_CODE (initial_value) == CONST_INT)
7630 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7631 enum machine_mode mode = GET_MODE (reg);
7632 enum insn_code icode
7633 = add_optab->handlers[(int) mode].insn_code;
7635 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7636 || ! ((*insn_data[icode].operand[1].predicate)
7637 (comparison_value, mode))
7638 || ! ((*insn_data[icode].operand[2].predicate)
7642 = gen_rtx_PLUS (mode, comparison_value, offset);
7643 emit_insn_before ((GEN_FCN (icode)
7644 (reg, comparison_value, offset)),
7646 if (GET_CODE (comparison) == LE)
7647 final_value = gen_rtx_PLUS (mode, comparison_value,
7650 else if (! add_adjust)
7652 enum machine_mode mode = GET_MODE (reg);
7653 enum insn_code icode
7654 = sub_optab->handlers[(int) mode].insn_code;
7655 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7656 || ! ((*insn_data[icode].operand[1].predicate)
7657 (comparison_value, mode))
7658 || ! ((*insn_data[icode].operand[2].predicate)
7659 (initial_value, mode)))
7662 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7663 emit_insn_before ((GEN_FCN (icode)
7664 (reg, comparison_value, initial_value)),
7668 /* We could handle the other cases too, but it'll be
7669 better to have a testcase first. */
7672 /* We may not have a single insn which can increment a reg, so
7673 create a sequence to hold all the insns from expand_inc. */
7675 expand_inc (reg, new_add_val);
7676 tem = gen_sequence ();
7679 p = emit_insn_before (tem, bl->biv->insn);
7680 delete_insn (bl->biv->insn);
7682 /* Update biv info to reflect its new status. */
7684 bl->initial_value = start_value;
7685 bl->biv->add_val = new_add_val;
7687 /* Update loop info. */
7688 loop_info->initial_value = reg;
7689 loop_info->initial_equiv_value = reg;
7690 loop_info->final_value = const0_rtx;
7691 loop_info->final_equiv_value = const0_rtx;
7692 loop_info->comparison_value = const0_rtx;
7693 loop_info->comparison_code = cmp_code;
7694 loop_info->increment = new_add_val;
7696 /* Inc LABEL_NUSES so that delete_insn will
7697 not delete the label. */
7698 LABEL_NUSES (XEXP (jump_label, 0))++;
7700 /* Emit an insn after the end of the loop to set the biv's
7701 proper exit value if it is used anywhere outside the loop. */
7702 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7704 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7705 emit_insn_after (gen_move_insn (reg, final_value),
7708 /* Delete compare/branch at end of loop. */
7709 delete_insn (PREV_INSN (loop_end));
7710 if (compare_and_branch == 2)
7711 delete_insn (first_compare);
7713 /* Add new compare/branch insn at end of loop. */
7715 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7716 GET_MODE (reg), 0, 0,
7717 XEXP (jump_label, 0));
7718 tem = gen_sequence ();
7720 emit_jump_insn_before (tem, loop_end);
7722 for (tem = PREV_INSN (loop_end);
7723 tem && GET_CODE (tem) != JUMP_INSN;
7724 tem = PREV_INSN (tem))
7728 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7734 /* Increment of LABEL_NUSES done above. */
7735 /* Register is now always nonnegative,
7736 so add REG_NONNEG note to the branch. */
7737 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7743 /* No insn may reference both the reversed and another biv or it
7744 will fail (see comment near the top of the loop reversal
7746 Earlier on, we have verified that the biv has no use except
7747 counting, or it is the only biv in this function.
7748 However, the code that computes no_use_except_counting does
7749 not verify reg notes. It's possible to have an insn that
7750 references another biv, and has a REG_EQUAL note with an
7751 expression based on the reversed biv. To avoid this case,
7752 remove all REG_EQUAL notes based on the reversed biv
7754 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7758 rtx set = single_set (p);
7759 /* If this is a set of a GIV based on the reversed biv, any
7760 REG_EQUAL notes should still be correct. */
7762 || GET_CODE (SET_DEST (set)) != REG
7763 || (size_t) REGNO (SET_DEST (set)) >= ivs->reg_iv_type->num_elements
7764 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7765 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7766 for (pnote = ®_NOTES (p); *pnote;)
7768 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7769 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7771 *pnote = XEXP (*pnote, 1);
7773 pnote = &XEXP (*pnote, 1);
7777 /* Mark that this biv has been reversed. Each giv which depends
7778 on this biv, and which is also live past the end of the loop
7779 will have to be fixed up. */
7783 if (loop_dump_stream)
7785 fprintf (loop_dump_stream, "Reversed loop");
7787 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7789 fprintf (loop_dump_stream, "\n");
7800 /* Verify whether the biv BL appears to be eliminable,
7801 based on the insns in the loop that refer to it.
7803 If ELIMINATE_P is non-zero, actually do the elimination.
7805 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7806 determine whether invariant insns should be placed inside or at the
7807 start of the loop. */
7810 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7811 const struct loop *loop;
7812 struct iv_class *bl;
7814 int threshold, insn_count;
7816 struct loop_ivs *ivs = LOOP_IVS (loop);
7817 rtx reg = bl->biv->dest_reg;
7818 rtx loop_start = loop->start;
7819 rtx loop_end = loop->end;
7822 /* Scan all insns in the loop, stopping if we find one that uses the
7823 biv in a way that we cannot eliminate. */
7825 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7827 enum rtx_code code = GET_CODE (p);
7828 rtx where = threshold >= insn_count ? loop_start : p;
7830 /* If this is a libcall that sets a giv, skip ahead to its end. */
7831 if (GET_RTX_CLASS (code) == 'i')
7833 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7837 rtx last = XEXP (note, 0);
7838 rtx set = single_set (last);
7840 if (set && GET_CODE (SET_DEST (set)) == REG)
7842 unsigned int regno = REGNO (SET_DEST (set));
7844 if (regno < max_reg_before_loop
7845 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7846 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7851 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7852 && reg_mentioned_p (reg, PATTERN (p))
7853 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7854 eliminate_p, where))
7856 if (loop_dump_stream)
7857 fprintf (loop_dump_stream,
7858 "Cannot eliminate biv %d: biv used in insn %d.\n",
7859 bl->regno, INSN_UID (p));
7866 if (loop_dump_stream)
7867 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7868 bl->regno, eliminate_p ? "was" : "can be");
7875 /* INSN and REFERENCE are instructions in the same insn chain.
7876 Return non-zero if INSN is first. */
7879 loop_insn_first_p (insn, reference)
7880 rtx insn, reference;
7884 for (p = insn, q = reference;;)
7886 /* Start with test for not first so that INSN == REFERENCE yields not
7888 if (q == insn || ! p)
7890 if (p == reference || ! q)
7893 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7894 previous insn, hence the <= comparison below does not work if
7896 if (INSN_UID (p) < max_uid_for_loop
7897 && INSN_UID (q) < max_uid_for_loop
7898 && GET_CODE (p) != NOTE)
7899 return INSN_LUID (p) <= INSN_LUID (q);
7901 if (INSN_UID (p) >= max_uid_for_loop
7902 || GET_CODE (p) == NOTE)
7904 if (INSN_UID (q) >= max_uid_for_loop)
7909 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7910 the offset that we have to take into account due to auto-increment /
7911 div derivation is zero. */
7913 biv_elimination_giv_has_0_offset (biv, giv, insn)
7914 struct induction *biv, *giv;
7917 /* If the giv V had the auto-inc address optimization applied
7918 to it, and INSN occurs between the giv insn and the biv
7919 insn, then we'd have to adjust the value used here.
7920 This is rare, so we don't bother to make this possible. */
7921 if (giv->auto_inc_opt
7922 && ((loop_insn_first_p (giv->insn, insn)
7923 && loop_insn_first_p (insn, biv->insn))
7924 || (loop_insn_first_p (biv->insn, insn)
7925 && loop_insn_first_p (insn, giv->insn))))
7931 /* If BL appears in X (part of the pattern of INSN), see if we can
7932 eliminate its use. If so, return 1. If not, return 0.
7934 If BIV does not appear in X, return 1.
7936 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7937 where extra insns should be added. Depending on how many items have been
7938 moved out of the loop, it will either be before INSN or at the start of
7942 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7943 const struct loop *loop;
7945 struct iv_class *bl;
7949 enum rtx_code code = GET_CODE (x);
7950 rtx reg = bl->biv->dest_reg;
7951 enum machine_mode mode = GET_MODE (reg);
7952 struct induction *v;
7964 /* If we haven't already been able to do something with this BIV,
7965 we can't eliminate it. */
7971 /* If this sets the BIV, it is not a problem. */
7972 if (SET_DEST (x) == reg)
7975 /* If this is an insn that defines a giv, it is also ok because
7976 it will go away when the giv is reduced. */
7977 for (v = bl->giv; v; v = v->next_iv)
7978 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7982 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7984 /* Can replace with any giv that was reduced and
7985 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7986 Require a constant for MULT_VAL, so we know it's nonzero.
7987 ??? We disable this optimization to avoid potential
7990 for (v = bl->giv; v; v = v->next_iv)
7991 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7992 && v->add_val == const0_rtx
7993 && ! v->ignore && ! v->maybe_dead && v->always_computable
7997 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8003 /* If the giv has the opposite direction of change,
8004 then reverse the comparison. */
8005 if (INTVAL (v->mult_val) < 0)
8006 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
8007 const0_rtx, v->new_reg);
8011 /* We can probably test that giv's reduced reg. */
8012 if (validate_change (insn, &SET_SRC (x), new, 0))
8016 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
8017 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
8018 Require a constant for MULT_VAL, so we know it's nonzero.
8019 ??? Do this only if ADD_VAL is a pointer to avoid a potential
8020 overflow problem. */
8022 for (v = bl->giv; v; v = v->next_iv)
8023 if (GET_CODE (v->mult_val) == CONST_INT
8024 && v->mult_val != const0_rtx
8025 && ! v->ignore && ! v->maybe_dead && v->always_computable
8027 && (GET_CODE (v->add_val) == SYMBOL_REF
8028 || GET_CODE (v->add_val) == LABEL_REF
8029 || GET_CODE (v->add_val) == CONST
8030 || (GET_CODE (v->add_val) == REG
8031 && REG_POINTER (v->add_val))))
8033 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8039 /* If the giv has the opposite direction of change,
8040 then reverse the comparison. */
8041 if (INTVAL (v->mult_val) < 0)
8042 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
8045 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
8046 copy_rtx (v->add_val));
8048 /* Replace biv with the giv's reduced register. */
8049 update_reg_last_use (v->add_val, insn);
8050 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8053 /* Insn doesn't support that constant or invariant. Copy it
8054 into a register (it will be a loop invariant.) */
8055 tem = gen_reg_rtx (GET_MODE (v->new_reg));
8057 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
8060 /* Substitute the new register for its invariant value in
8061 the compare expression. */
8062 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
8063 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8072 case GT: case GE: case GTU: case GEU:
8073 case LT: case LE: case LTU: case LEU:
8074 /* See if either argument is the biv. */
8075 if (XEXP (x, 0) == reg)
8076 arg = XEXP (x, 1), arg_operand = 1;
8077 else if (XEXP (x, 1) == reg)
8078 arg = XEXP (x, 0), arg_operand = 0;
8082 if (CONSTANT_P (arg))
8084 /* First try to replace with any giv that has constant positive
8085 mult_val and constant add_val. We might be able to support
8086 negative mult_val, but it seems complex to do it in general. */
8088 for (v = bl->giv; v; v = v->next_iv)
8089 if (GET_CODE (v->mult_val) == CONST_INT
8090 && INTVAL (v->mult_val) > 0
8091 && (GET_CODE (v->add_val) == SYMBOL_REF
8092 || GET_CODE (v->add_val) == LABEL_REF
8093 || GET_CODE (v->add_val) == CONST
8094 || (GET_CODE (v->add_val) == REG
8095 && REG_POINTER (v->add_val)))
8096 && ! v->ignore && ! v->maybe_dead && v->always_computable
8099 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8105 /* Replace biv with the giv's reduced reg. */
8106 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
8108 /* If all constants are actually constant integers and
8109 the derived constant can be directly placed in the COMPARE,
8111 if (GET_CODE (arg) == CONST_INT
8112 && GET_CODE (v->mult_val) == CONST_INT
8113 && GET_CODE (v->add_val) == CONST_INT)
8115 validate_change (insn, &XEXP (x, arg_operand),
8116 GEN_INT (INTVAL (arg)
8117 * INTVAL (v->mult_val)
8118 + INTVAL (v->add_val)), 1);
8122 /* Otherwise, load it into a register. */
8123 tem = gen_reg_rtx (mode);
8124 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8125 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8127 if (apply_change_group ())
8131 /* Look for giv with positive constant mult_val and nonconst add_val.
8132 Insert insns to calculate new compare value.
8133 ??? Turn this off due to possible overflow. */
8135 for (v = bl->giv; v; v = v->next_iv)
8136 if (GET_CODE (v->mult_val) == CONST_INT
8137 && INTVAL (v->mult_val) > 0
8138 && ! v->ignore && ! v->maybe_dead && v->always_computable
8144 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8150 tem = gen_reg_rtx (mode);
8152 /* Replace biv with giv's reduced register. */
8153 validate_change (insn, &XEXP (x, 1 - arg_operand),
8156 /* Compute value to compare against. */
8157 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8158 /* Use it in this insn. */
8159 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8160 if (apply_change_group ())
8164 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
8166 if (loop_invariant_p (loop, arg) == 1)
8168 /* Look for giv with constant positive mult_val and nonconst
8169 add_val. Insert insns to compute new compare value.
8170 ??? Turn this off due to possible overflow. */
8172 for (v = bl->giv; v; v = v->next_iv)
8173 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
8174 && ! v->ignore && ! v->maybe_dead && v->always_computable
8180 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8186 tem = gen_reg_rtx (mode);
8188 /* Replace biv with giv's reduced register. */
8189 validate_change (insn, &XEXP (x, 1 - arg_operand),
8192 /* Compute value to compare against. */
8193 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8195 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8196 if (apply_change_group ())
8201 /* This code has problems. Basically, you can't know when
8202 seeing if we will eliminate BL, whether a particular giv
8203 of ARG will be reduced. If it isn't going to be reduced,
8204 we can't eliminate BL. We can try forcing it to be reduced,
8205 but that can generate poor code.
8207 The problem is that the benefit of reducing TV, below should
8208 be increased if BL can actually be eliminated, but this means
8209 we might have to do a topological sort of the order in which
8210 we try to process biv. It doesn't seem worthwhile to do
8211 this sort of thing now. */
8214 /* Otherwise the reg compared with had better be a biv. */
8215 if (GET_CODE (arg) != REG
8216 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8219 /* Look for a pair of givs, one for each biv,
8220 with identical coefficients. */
8221 for (v = bl->giv; v; v = v->next_iv)
8223 struct induction *tv;
8225 if (v->ignore || v->maybe_dead || v->mode != mode)
8228 for (tv = ivs->reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
8229 if (! tv->ignore && ! tv->maybe_dead
8230 && rtx_equal_p (tv->mult_val, v->mult_val)
8231 && rtx_equal_p (tv->add_val, v->add_val)
8232 && tv->mode == mode)
8234 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8240 /* Replace biv with its giv's reduced reg. */
8241 XEXP (x, 1 - arg_operand) = v->new_reg;
8242 /* Replace other operand with the other giv's
8244 XEXP (x, arg_operand) = tv->new_reg;
8251 /* If we get here, the biv can't be eliminated. */
8255 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8256 biv is used in it, since it will be replaced. */
8257 for (v = bl->giv; v; v = v->next_iv)
8258 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8266 /* See if any subexpression fails elimination. */
8267 fmt = GET_RTX_FORMAT (code);
8268 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8273 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8274 eliminate_p, where))
8279 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8280 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8281 eliminate_p, where))
8290 /* Return nonzero if the last use of REG
8291 is in an insn following INSN in the same basic block. */
8294 last_use_this_basic_block (reg, insn)
8300 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8303 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8309 /* Called via `note_stores' to record the initial value of a biv. Here we
8310 just record the location of the set and process it later. */
8313 record_initial (dest, set, data)
8316 void *data ATTRIBUTE_UNUSED;
8318 struct loop_ivs *ivs = (struct loop_ivs *) data;
8319 struct iv_class *bl;
8321 if (GET_CODE (dest) != REG
8322 || REGNO (dest) >= max_reg_before_loop
8323 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8326 bl = ivs->reg_biv_class[REGNO (dest)];
8328 /* If this is the first set found, record it. */
8329 if (bl->init_insn == 0)
8331 bl->init_insn = note_insn;
8336 /* If any of the registers in X are "old" and currently have a last use earlier
8337 than INSN, update them to have a last use of INSN. Their actual last use
8338 will be the previous insn but it will not have a valid uid_luid so we can't
8342 update_reg_last_use (x, insn)
8346 /* Check for the case where INSN does not have a valid luid. In this case,
8347 there is no need to modify the regno_last_uid, as this can only happen
8348 when code is inserted after the loop_end to set a pseudo's final value,
8349 and hence this insn will never be the last use of x. */
8350 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8351 && INSN_UID (insn) < max_uid_for_loop
8352 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8353 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8357 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8358 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8361 update_reg_last_use (XEXP (x, i), insn);
8362 else if (fmt[i] == 'E')
8363 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8364 update_reg_last_use (XVECEXP (x, i, j), insn);
8369 /* Given an insn INSN and condition COND, return the condition in a
8370 canonical form to simplify testing by callers. Specifically:
8372 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8373 (2) Both operands will be machine operands; (cc0) will have been replaced.
8374 (3) If an operand is a constant, it will be the second operand.
8375 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8376 for GE, GEU, and LEU.
8378 If the condition cannot be understood, or is an inequality floating-point
8379 comparison which needs to be reversed, 0 will be returned.
8381 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8383 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8384 insn used in locating the condition was found. If a replacement test
8385 of the condition is desired, it should be placed in front of that
8386 insn and we will be sure that the inputs are still valid.
8388 If WANT_REG is non-zero, we wish the condition to be relative to that
8389 register, if possible. Therefore, do not canonicalize the condition
8393 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8405 int reverse_code = 0;
8406 int did_reverse_condition = 0;
8407 enum machine_mode mode;
8409 code = GET_CODE (cond);
8410 mode = GET_MODE (cond);
8411 op0 = XEXP (cond, 0);
8412 op1 = XEXP (cond, 1);
8416 code = reverse_condition (code);
8417 did_reverse_condition ^= 1;
8423 /* If we are comparing a register with zero, see if the register is set
8424 in the previous insn to a COMPARE or a comparison operation. Perform
8425 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8428 while (GET_RTX_CLASS (code) == '<'
8429 && op1 == CONST0_RTX (GET_MODE (op0))
8432 /* Set non-zero when we find something of interest. */
8436 /* If comparison with cc0, import actual comparison from compare
8440 if ((prev = prev_nonnote_insn (prev)) == 0
8441 || GET_CODE (prev) != INSN
8442 || (set = single_set (prev)) == 0
8443 || SET_DEST (set) != cc0_rtx)
8446 op0 = SET_SRC (set);
8447 op1 = CONST0_RTX (GET_MODE (op0));
8453 /* If this is a COMPARE, pick up the two things being compared. */
8454 if (GET_CODE (op0) == COMPARE)
8456 op1 = XEXP (op0, 1);
8457 op0 = XEXP (op0, 0);
8460 else if (GET_CODE (op0) != REG)
8463 /* Go back to the previous insn. Stop if it is not an INSN. We also
8464 stop if it isn't a single set or if it has a REG_INC note because
8465 we don't want to bother dealing with it. */
8467 if ((prev = prev_nonnote_insn (prev)) == 0
8468 || GET_CODE (prev) != INSN
8469 || FIND_REG_INC_NOTE (prev, 0)
8470 || (set = single_set (prev)) == 0)
8473 /* If this is setting OP0, get what it sets it to if it looks
8475 if (rtx_equal_p (SET_DEST (set), op0))
8477 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8479 /* ??? We may not combine comparisons done in a CCmode with
8480 comparisons not done in a CCmode. This is to aid targets
8481 like Alpha that have an IEEE compliant EQ instruction, and
8482 a non-IEEE compliant BEQ instruction. The use of CCmode is
8483 actually artificial, simply to prevent the combination, but
8484 should not affect other platforms.
8486 However, we must allow VOIDmode comparisons to match either
8487 CCmode or non-CCmode comparison, because some ports have
8488 modeless comparisons inside branch patterns.
8490 ??? This mode check should perhaps look more like the mode check
8491 in simplify_comparison in combine. */
8493 if ((GET_CODE (SET_SRC (set)) == COMPARE
8496 && GET_MODE_CLASS (inner_mode) == MODE_INT
8497 && (GET_MODE_BITSIZE (inner_mode)
8498 <= HOST_BITS_PER_WIDE_INT)
8499 && (STORE_FLAG_VALUE
8500 & ((HOST_WIDE_INT) 1
8501 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8502 #ifdef FLOAT_STORE_FLAG_VALUE
8504 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8505 && (REAL_VALUE_NEGATIVE
8506 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8509 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8510 && (((GET_MODE_CLASS (mode) == MODE_CC)
8511 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8512 || mode == VOIDmode || inner_mode == VOIDmode))
8514 else if (((code == EQ
8516 && (GET_MODE_BITSIZE (inner_mode)
8517 <= HOST_BITS_PER_WIDE_INT)
8518 && GET_MODE_CLASS (inner_mode) == MODE_INT
8519 && (STORE_FLAG_VALUE
8520 & ((HOST_WIDE_INT) 1
8521 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8522 #ifdef FLOAT_STORE_FLAG_VALUE
8524 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8525 && (REAL_VALUE_NEGATIVE
8526 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8529 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8530 && (((GET_MODE_CLASS (mode) == MODE_CC)
8531 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8532 || mode == VOIDmode || inner_mode == VOIDmode))
8535 /* We might have reversed a LT to get a GE here. But this wasn't
8536 actually the comparison of data, so we don't flag that we
8537 have had to reverse the condition. */
8538 did_reverse_condition ^= 1;
8546 else if (reg_set_p (op0, prev))
8547 /* If this sets OP0, but not directly, we have to give up. */
8552 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8553 code = GET_CODE (x);
8556 code = reverse_condition (code);
8557 if (code == UNKNOWN)
8559 did_reverse_condition ^= 1;
8563 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8569 /* If constant is first, put it last. */
8570 if (CONSTANT_P (op0))
8571 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8573 /* If OP0 is the result of a comparison, we weren't able to find what
8574 was really being compared, so fail. */
8575 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8578 /* Canonicalize any ordered comparison with integers involving equality
8579 if we can do computations in the relevant mode and we do not
8582 if (GET_CODE (op1) == CONST_INT
8583 && GET_MODE (op0) != VOIDmode
8584 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8586 HOST_WIDE_INT const_val = INTVAL (op1);
8587 unsigned HOST_WIDE_INT uconst_val = const_val;
8588 unsigned HOST_WIDE_INT max_val
8589 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8594 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8595 code = LT, op1 = GEN_INT (const_val + 1);
8598 /* When cross-compiling, const_val might be sign-extended from
8599 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8601 if ((HOST_WIDE_INT) (const_val & max_val)
8602 != (((HOST_WIDE_INT) 1
8603 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8604 code = GT, op1 = GEN_INT (const_val - 1);
8608 if (uconst_val < max_val)
8609 code = LTU, op1 = GEN_INT (uconst_val + 1);
8613 if (uconst_val != 0)
8614 code = GTU, op1 = GEN_INT (uconst_val - 1);
8622 /* If this was floating-point and we reversed anything other than an
8623 EQ or NE or (UN)ORDERED, return zero. */
8624 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8625 && did_reverse_condition
8626 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8628 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8632 /* Never return CC0; return zero instead. */
8637 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8640 /* Given a jump insn JUMP, return the condition that will cause it to branch
8641 to its JUMP_LABEL. If the condition cannot be understood, or is an
8642 inequality floating-point comparison which needs to be reversed, 0 will
8645 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8646 insn used in locating the condition was found. If a replacement test
8647 of the condition is desired, it should be placed in front of that
8648 insn and we will be sure that the inputs are still valid. */
8651 get_condition (jump, earliest)
8659 /* If this is not a standard conditional jump, we can't parse it. */
8660 if (GET_CODE (jump) != JUMP_INSN
8661 || ! any_condjump_p (jump))
8663 set = pc_set (jump);
8665 cond = XEXP (SET_SRC (set), 0);
8667 /* If this branches to JUMP_LABEL when the condition is false, reverse
8670 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8671 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8673 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8676 /* Similar to above routine, except that we also put an invariant last
8677 unless both operands are invariants. */
8680 get_condition_for_loop (loop, x)
8681 const struct loop *loop;
8684 rtx comparison = get_condition (x, NULL_PTR);
8687 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8688 || loop_invariant_p (loop, XEXP (comparison, 1)))
8691 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8692 XEXP (comparison, 1), XEXP (comparison, 0));
8695 /* Scan the function and determine whether it has indirect (computed) jumps.
8697 This is taken mostly from flow.c; similar code exists elsewhere
8698 in the compiler. It may be useful to put this into rtlanal.c. */
8700 indirect_jump_in_function_p (start)
8705 for (insn = start; insn; insn = NEXT_INSN (insn))
8706 if (computed_jump_p (insn))
8712 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8713 documentation for LOOP_MEMS for the definition of `appropriate'.
8714 This function is called from prescan_loop via for_each_rtx. */
8717 insert_loop_mem (mem, data)
8719 void *data ATTRIBUTE_UNUSED;
8721 struct loop_info *loop_info = data;
8728 switch (GET_CODE (m))
8734 /* We're not interested in MEMs that are only clobbered. */
8738 /* We're not interested in the MEM associated with a
8739 CONST_DOUBLE, so there's no need to traverse into this. */
8743 /* We're not interested in any MEMs that only appear in notes. */
8747 /* This is not a MEM. */
8751 /* See if we've already seen this MEM. */
8752 for (i = 0; i < loop_info->mems_idx; ++i)
8753 if (rtx_equal_p (m, loop_info->mems[i].mem))
8755 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8756 /* The modes of the two memory accesses are different. If
8757 this happens, something tricky is going on, and we just
8758 don't optimize accesses to this MEM. */
8759 loop_info->mems[i].optimize = 0;
8764 /* Resize the array, if necessary. */
8765 if (loop_info->mems_idx == loop_info->mems_allocated)
8767 if (loop_info->mems_allocated != 0)
8768 loop_info->mems_allocated *= 2;
8770 loop_info->mems_allocated = 32;
8772 loop_info->mems = (loop_mem_info *)
8773 xrealloc (loop_info->mems,
8774 loop_info->mems_allocated * sizeof (loop_mem_info));
8777 /* Actually insert the MEM. */
8778 loop_info->mems[loop_info->mems_idx].mem = m;
8779 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8780 because we can't put it in a register. We still store it in the
8781 table, though, so that if we see the same address later, but in a
8782 non-BLK mode, we'll not think we can optimize it at that point. */
8783 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8784 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8785 ++loop_info->mems_idx;
8790 /* Like load_mems, but also ensures that REGS->SET_IN_LOOP,
8791 REGS->MAY_NOT_OPTIMIZE, REGS->SINGLE_USAGE, and INSN_COUNT have the correct
8792 values after load_mems. */
8795 load_mems_and_recount_loop_regs_set (loop, insn_count)
8796 const struct loop *loop;
8799 struct loop_regs *regs = LOOP_REGS (loop);
8800 int nregs = max_reg_num ();
8804 /* Recalculate regs->set_in_loop and friends since load_mems may have
8805 created new registers. */
8806 if (max_reg_num () > nregs)
8812 nregs = max_reg_num ();
8814 if ((unsigned) nregs > regs->set_in_loop->num_elements)
8816 /* Grow all the arrays. */
8817 VARRAY_GROW (regs->set_in_loop, nregs);
8818 VARRAY_GROW (regs->n_times_set, nregs);
8819 VARRAY_GROW (regs->may_not_optimize, nregs);
8820 VARRAY_GROW (regs->single_usage, nregs);
8822 /* Clear the arrays */
8823 memset ((char *) ®s->set_in_loop->data, 0, nregs * sizeof (int));
8824 memset ((char *) ®s->may_not_optimize->data, 0, nregs * sizeof (char));
8825 memset ((char *) ®s->single_usage->data, 0, nregs * sizeof (rtx));
8827 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
8830 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8832 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8833 VARRAY_INT (regs->set_in_loop, i) = 1;
8836 #ifdef AVOID_CCMODE_COPIES
8837 /* Don't try to move insns which set CC registers if we should not
8838 create CCmode register copies. */
8839 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8840 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8841 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8844 /* Set regs->n_times_set for the new registers. */
8845 bcopy ((char *) (®s->set_in_loop->data.i[0] + old_nregs),
8846 (char *) (®s->n_times_set->data.i[0] + old_nregs),
8847 (nregs - old_nregs) * sizeof (int));
8851 /* Move MEMs into registers for the duration of the loop. */
8855 const struct loop *loop;
8857 struct loop_info *loop_info = LOOP_INFO (loop);
8858 struct loop_regs *regs = LOOP_REGS (loop);
8859 int maybe_never = 0;
8862 rtx label = NULL_RTX;
8864 /* Nonzero if the next instruction may never be executed. */
8865 int next_maybe_never = 0;
8866 int last_max_reg = max_reg_num ();
8868 if (loop_info->mems_idx == 0)
8871 /* We cannot use next_label here because it skips over normal insns. */
8872 end_label = next_nonnote_insn (loop->end);
8873 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8874 end_label = NULL_RTX;
8876 /* Check to see if it's possible that some instructions in the loop are
8877 never executed. Also check if there is a goto out of the loop other
8878 than right after the end of the loop. */
8879 for (p = next_insn_in_loop (loop, loop->scan_start);
8880 p != NULL_RTX && ! maybe_never;
8881 p = next_insn_in_loop (loop, p))
8883 if (GET_CODE (p) == CODE_LABEL)
8885 else if (GET_CODE (p) == JUMP_INSN
8886 /* If we enter the loop in the middle, and scan
8887 around to the beginning, don't set maybe_never
8888 for that. This must be an unconditional jump,
8889 otherwise the code at the top of the loop might
8890 never be executed. Unconditional jumps are
8891 followed a by barrier then loop end. */
8892 && ! (GET_CODE (p) == JUMP_INSN
8893 && JUMP_LABEL (p) == loop->top
8894 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8895 && any_uncondjump_p (p)))
8897 /* If this is a jump outside of the loop but not right
8898 after the end of the loop, we would have to emit new fixup
8899 sequences for each such label. */
8900 if (JUMP_LABEL (p) != end_label
8901 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8902 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8903 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8906 if (!any_condjump_p (p))
8907 /* Something complicated. */
8910 /* If there are any more instructions in the loop, they
8911 might not be reached. */
8912 next_maybe_never = 1;
8914 else if (next_maybe_never)
8918 /* Find start of the extended basic block that enters the loop. */
8919 for (p = loop->start;
8920 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8926 /* Build table of mems that get set to constant values before the
8928 for (; p != loop->start; p = NEXT_INSN (p))
8929 cselib_process_insn (p);
8931 /* Actually move the MEMs. */
8932 for (i = 0; i < loop_info->mems_idx; ++i)
8934 regset_head load_copies;
8935 regset_head store_copies;
8938 rtx mem = loop_info->mems[i].mem;
8941 if (MEM_VOLATILE_P (mem)
8942 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8943 /* There's no telling whether or not MEM is modified. */
8944 loop_info->mems[i].optimize = 0;
8946 /* Go through the MEMs written to in the loop to see if this
8947 one is aliased by one of them. */
8948 mem_list_entry = loop_info->store_mems;
8949 while (mem_list_entry)
8951 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8953 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8956 /* MEM is indeed aliased by this store. */
8957 loop_info->mems[i].optimize = 0;
8960 mem_list_entry = XEXP (mem_list_entry, 1);
8963 if (flag_float_store && written
8964 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8965 loop_info->mems[i].optimize = 0;
8967 /* If this MEM is written to, we must be sure that there
8968 are no reads from another MEM that aliases this one. */
8969 if (loop_info->mems[i].optimize && written)
8973 for (j = 0; j < loop_info->mems_idx; ++j)
8977 else if (true_dependence (mem,
8979 loop_info->mems[j].mem,
8982 /* It's not safe to hoist loop_info->mems[i] out of
8983 the loop because writes to it might not be
8984 seen by reads from loop_info->mems[j]. */
8985 loop_info->mems[i].optimize = 0;
8991 if (maybe_never && may_trap_p (mem))
8992 /* We can't access the MEM outside the loop; it might
8993 cause a trap that wouldn't have happened otherwise. */
8994 loop_info->mems[i].optimize = 0;
8996 if (!loop_info->mems[i].optimize)
8997 /* We thought we were going to lift this MEM out of the
8998 loop, but later discovered that we could not. */
9001 INIT_REG_SET (&load_copies);
9002 INIT_REG_SET (&store_copies);
9004 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
9005 order to keep scan_loop from moving stores to this MEM
9006 out of the loop just because this REG is neither a
9007 user-variable nor used in the loop test. */
9008 reg = gen_reg_rtx (GET_MODE (mem));
9009 REG_USERVAR_P (reg) = 1;
9010 loop_info->mems[i].reg = reg;
9012 /* Now, replace all references to the MEM with the
9013 corresponding pesudos. */
9015 for (p = next_insn_in_loop (loop, loop->scan_start);
9017 p = next_insn_in_loop (loop, p))
9023 set = single_set (p);
9025 /* See if this copies the mem into a register that isn't
9026 modified afterwards. We'll try to do copy propagation
9027 a little further on. */
9029 /* @@@ This test is _way_ too conservative. */
9031 && GET_CODE (SET_DEST (set)) == REG
9032 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
9033 && REGNO (SET_DEST (set)) < last_max_reg
9034 && VARRAY_INT (regs->n_times_set,
9035 REGNO (SET_DEST (set))) == 1
9036 && rtx_equal_p (SET_SRC (set), mem))
9037 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
9039 /* See if this copies the mem from a register that isn't
9040 modified afterwards. We'll try to remove the
9041 redundant copy later on by doing a little register
9042 renaming and copy propagation. This will help
9043 to untangle things for the BIV detection code. */
9046 && GET_CODE (SET_SRC (set)) == REG
9047 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
9048 && REGNO (SET_SRC (set)) < last_max_reg
9049 && VARRAY_INT (regs->n_times_set, REGNO (SET_SRC (set))) == 1
9050 && rtx_equal_p (SET_DEST (set), mem))
9051 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
9053 /* Replace the memory reference with the shadow register. */
9054 replace_loop_mems (p, loop_info->mems[i].mem,
9055 loop_info->mems[i].reg);
9058 if (GET_CODE (p) == CODE_LABEL
9059 || GET_CODE (p) == JUMP_INSN)
9063 if (! apply_change_group ())
9064 /* We couldn't replace all occurrences of the MEM. */
9065 loop_info->mems[i].optimize = 0;
9068 /* Load the memory immediately before LOOP->START, which is
9069 the NOTE_LOOP_BEG. */
9070 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
9074 struct elt_loc_list *const_equiv = 0;
9078 struct elt_loc_list *equiv;
9079 struct elt_loc_list *best_equiv = 0;
9080 for (equiv = e->locs; equiv; equiv = equiv->next)
9082 if (CONSTANT_P (equiv->loc))
9083 const_equiv = equiv;
9084 else if (GET_CODE (equiv->loc) == REG
9085 /* Extending hard register lifetimes cuases crash
9086 on SRC targets. Doing so on non-SRC is
9087 probably also not good idea, since we most
9088 probably have pseudoregister equivalence as
9090 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
9093 /* Use the constant equivalence if that is cheap enough. */
9095 best_equiv = const_equiv;
9096 else if (const_equiv
9097 && (rtx_cost (const_equiv->loc, SET)
9098 <= rtx_cost (best_equiv->loc, SET)))
9100 best_equiv = const_equiv;
9104 /* If best_equiv is nonzero, we know that MEM is set to a
9105 constant or register before the loop. We will use this
9106 knowledge to initialize the shadow register with that
9107 constant or reg rather than by loading from MEM. */
9109 best = copy_rtx (best_equiv->loc);
9111 set = gen_move_insn (reg, best);
9112 set = emit_insn_before (set, loop->start);
9114 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
9115 copy_rtx (const_equiv->loc),
9120 if (label == NULL_RTX)
9122 label = gen_label_rtx ();
9123 emit_label_after (label, loop->end);
9126 /* Store the memory immediately after END, which is
9127 the NOTE_LOOP_END. */
9128 set = gen_move_insn (copy_rtx (mem), reg);
9129 emit_insn_after (set, label);
9132 if (loop_dump_stream)
9134 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9135 REGNO (reg), (written ? "r/w" : "r/o"));
9136 print_rtl (loop_dump_stream, mem);
9137 fputc ('\n', loop_dump_stream);
9140 /* Attempt a bit of copy propagation. This helps untangle the
9141 data flow, and enables {basic,general}_induction_var to find
9143 EXECUTE_IF_SET_IN_REG_SET
9144 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9146 try_copy_prop (loop, reg, j);
9148 CLEAR_REG_SET (&load_copies);
9150 EXECUTE_IF_SET_IN_REG_SET
9151 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9153 try_swap_copy_prop (loop, reg, j);
9155 CLEAR_REG_SET (&store_copies);
9159 if (label != NULL_RTX && end_label != NULL_RTX)
9161 /* Now, we need to replace all references to the previous exit
9162 label with the new one. */
9167 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9169 for_each_rtx (&p, replace_label, &rr);
9171 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9172 field. This is not handled by for_each_rtx because it doesn't
9173 handle unprinted ('0') fields. We need to update JUMP_LABEL
9174 because the immediately following unroll pass will use it.
9175 replace_label would not work anyways, because that only handles
9177 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9178 JUMP_LABEL (p) = label;
9185 /* For communication between note_reg_stored and its caller. */
9186 struct note_reg_stored_arg
9192 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9195 note_reg_stored (x, setter, arg)
9196 rtx x, setter ATTRIBUTE_UNUSED;
9199 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9204 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9205 There must be exactly one insn that sets this pseudo; it will be
9206 deleted if all replacements succeed and we can prove that the register
9207 is not used after the loop. */
9210 try_copy_prop (loop, replacement, regno)
9211 const struct loop *loop;
9215 /* This is the reg that we are copying from. */
9216 rtx reg_rtx = regno_reg_rtx[regno];
9219 /* These help keep track of whether we replaced all uses of the reg. */
9220 int replaced_last = 0;
9221 int store_is_first = 0;
9223 for (insn = next_insn_in_loop (loop, loop->scan_start);
9225 insn = next_insn_in_loop (loop, insn))
9229 /* Only substitute within one extended basic block from the initializing
9231 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9234 if (! INSN_P (insn))
9237 /* Is this the initializing insn? */
9238 set = single_set (insn);
9240 && GET_CODE (SET_DEST (set)) == REG
9241 && REGNO (SET_DEST (set)) == regno)
9247 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9251 /* Only substitute after seeing the initializing insn. */
9252 if (init_insn && insn != init_insn)
9254 struct note_reg_stored_arg arg;
9256 replace_loop_regs (insn, reg_rtx, replacement);
9257 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9260 /* Stop replacing when REPLACEMENT is modified. */
9261 arg.reg = replacement;
9263 note_stores (PATTERN (insn), note_reg_stored, &arg);
9270 if (apply_change_group ())
9272 if (loop_dump_stream)
9273 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9274 if (store_is_first && replaced_last)
9276 PUT_CODE (init_insn, NOTE);
9277 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9278 if (loop_dump_stream)
9279 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9280 INSN_UID (init_insn));
9282 if (loop_dump_stream)
9283 fprintf (loop_dump_stream, ".\n");
9287 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9288 loop LOOP if the order of the sets of these registers can be
9289 swapped. There must be exactly one insn within the loop that sets
9290 this pseudo followed immediately by a move insn that sets
9291 REPLACEMENT with REGNO. */
9293 try_swap_copy_prop (loop, replacement, regno)
9294 const struct loop *loop;
9300 unsigned int new_regno;
9302 new_regno = REGNO (replacement);
9304 for (insn = next_insn_in_loop (loop, loop->scan_start);
9306 insn = next_insn_in_loop (loop, insn))
9308 /* Search for the insn that copies REGNO to NEW_REGNO? */
9309 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9310 && (set = single_set (insn))
9311 && GET_CODE (SET_DEST (set)) == REG
9312 && REGNO (SET_DEST (set)) == new_regno
9313 && GET_CODE (SET_SRC (set)) == REG
9314 && REGNO (SET_SRC (set)) == regno)
9318 if (insn != NULL_RTX)
9323 /* Some DEF-USE info would come in handy here to make this
9324 function more general. For now, just check the previous insn
9325 which is the most likely candidate for setting REGNO. */
9327 prev_insn = PREV_INSN (insn);
9329 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9330 && (prev_set = single_set (prev_insn))
9331 && GET_CODE (SET_DEST (prev_set)) == REG
9332 && REGNO (SET_DEST (prev_set)) == regno)
9335 (set (reg regno) (expr))
9336 (set (reg new_regno) (reg regno))
9338 so try converting this to:
9339 (set (reg new_regno) (expr))
9340 (set (reg regno) (reg new_regno))
9342 The former construct is often generated when a global
9343 variable used for an induction variable is shadowed by a
9344 register (NEW_REGNO). The latter construct improves the
9345 chances of GIV replacement and BIV elimination. */
9347 validate_change (prev_insn, &SET_DEST (prev_set),
9349 validate_change (insn, &SET_DEST (set),
9351 validate_change (insn, &SET_SRC (set),
9354 if (apply_change_group ())
9356 if (loop_dump_stream)
9357 fprintf (loop_dump_stream,
9358 " Swapped set of reg %d at %d with reg %d at %d.\n",
9359 regno, INSN_UID (insn),
9360 new_regno, INSN_UID (prev_insn));
9362 /* Update first use of REGNO. */
9363 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9364 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9366 /* Now perform copy propagation to hopefully
9367 remove all uses of REGNO within the loop. */
9368 try_copy_prop (loop, replacement, regno);
9374 /* Replace MEM with its associated pseudo register. This function is
9375 called from load_mems via for_each_rtx. DATA is actually a pointer
9376 to a structure describing the instruction currently being scanned
9377 and the MEM we are currently replacing. */
9380 replace_loop_mem (mem, data)
9384 loop_replace_args *args = (loop_replace_args *) data;
9390 switch (GET_CODE (m))
9396 /* We're not interested in the MEM associated with a
9397 CONST_DOUBLE, so there's no need to traverse into one. */
9401 /* This is not a MEM. */
9405 if (!rtx_equal_p (args->match, m))
9406 /* This is not the MEM we are currently replacing. */
9409 /* Actually replace the MEM. */
9410 validate_change (args->insn, mem, args->replacement, 1);
9416 replace_loop_mems (insn, mem, reg)
9421 loop_replace_args args;
9425 args.replacement = reg;
9427 for_each_rtx (&insn, replace_loop_mem, &args);
9430 /* Replace one register with another. Called through for_each_rtx; PX points
9431 to the rtx being scanned. DATA is actually a pointer to
9432 a structure of arguments. */
9435 replace_loop_reg (px, data)
9440 loop_replace_args *args = (loop_replace_args *) data;
9445 if (x == args->match)
9446 validate_change (args->insn, px, args->replacement, 1);
9452 replace_loop_regs (insn, reg, replacement)
9457 loop_replace_args args;
9461 args.replacement = replacement;
9463 for_each_rtx (&insn, replace_loop_reg, &args);
9466 /* Replace occurrences of the old exit label for the loop with the new
9467 one. DATA is an rtx_pair containing the old and new labels,
9471 replace_label (x, data)
9476 rtx old_label = ((rtx_pair *) data)->r1;
9477 rtx new_label = ((rtx_pair *) data)->r2;
9482 if (GET_CODE (l) != LABEL_REF)
9485 if (XEXP (l, 0) != old_label)
9488 XEXP (l, 0) = new_label;
9489 ++LABEL_NUSES (new_label);
9490 --LABEL_NUSES (old_label);
9495 #define LOOP_BLOCK_NUM_1(INSN) \
9496 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9498 /* The notes do not have an assigned block, so look at the next insn. */
9499 #define LOOP_BLOCK_NUM(INSN) \
9500 ((INSN) ? (GET_CODE (INSN) == NOTE \
9501 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9502 : LOOP_BLOCK_NUM_1 (INSN)) \
9505 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9508 loop_dump_aux (loop, file, verbose)
9509 const struct loop *loop;
9511 int verbose ATTRIBUTE_UNUSED;
9515 if (! loop || ! file)
9518 /* Print diagnostics to compare our concept of a loop with
9519 what the loop notes say. */
9520 if (! PREV_INSN (loop->first->head)
9521 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9522 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9523 != NOTE_INSN_LOOP_BEG)
9524 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9525 INSN_UID (PREV_INSN (loop->first->head)));
9526 if (! NEXT_INSN (loop->last->end)
9527 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9528 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9529 != NOTE_INSN_LOOP_END)
9530 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9531 INSN_UID (NEXT_INSN (loop->last->end)));
9536 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9537 LOOP_BLOCK_NUM (loop->start),
9538 LOOP_INSN_UID (loop->start),
9539 LOOP_BLOCK_NUM (loop->cont),
9540 LOOP_INSN_UID (loop->cont),
9541 LOOP_BLOCK_NUM (loop->cont),
9542 LOOP_INSN_UID (loop->cont),
9543 LOOP_BLOCK_NUM (loop->vtop),
9544 LOOP_INSN_UID (loop->vtop),
9545 LOOP_BLOCK_NUM (loop->end),
9546 LOOP_INSN_UID (loop->end));
9547 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9548 LOOP_BLOCK_NUM (loop->top),
9549 LOOP_INSN_UID (loop->top),
9550 LOOP_BLOCK_NUM (loop->scan_start),
9551 LOOP_INSN_UID (loop->scan_start));
9552 fprintf (file, ";; exit_count %d", loop->exit_count);
9553 if (loop->exit_count)
9555 fputs (", labels:", file);
9556 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9558 fprintf (file, " %d ",
9559 LOOP_INSN_UID (XEXP (label, 0)));
9564 /* This can happen when a marked loop appears as two nested loops,
9565 say from while (a || b) {}. The inner loop won't match
9566 the loop markers but the outer one will. */
9567 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9568 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9572 /* Call this function from the debugger to dump LOOP. */
9576 const struct loop *loop;
9578 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9581 /* Call this function from the debugger to dump LOOPS. */
9585 const struct loops *loops;
9587 flow_loops_dump (loops, stderr, loop_dump_aux, 1);
OSDN Git Service
