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->list. */
3656 struct iv_class *bl, **backbl;
3660 for_each_insn_in_loop (loop, check_insn_for_bivs);
3662 /* Scan ivs->list to remove all regs that proved not to be bivs.
3663 Make a sanity check against regs->n_times_set. */
3664 for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
3666 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3667 /* Above happens if register modified by subreg, etc. */
3668 /* Make sure it is not recognized as a basic induction var: */
3669 || VARRAY_INT (regs->n_times_set, bl->regno) != bl->biv_count
3670 /* If never incremented, it is invariant that we decided not to
3671 move. So leave it alone. */
3672 || ! bl->incremented)
3674 if (loop_dump_stream)
3675 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3677 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3678 ? "not induction variable"
3679 : (! bl->incremented ? "never incremented"
3682 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3689 if (loop_dump_stream)
3690 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3696 /* Determine how BIVS are initialised by looking through pre-header
3697 extended basic block. */
3699 loop_bivs_init_find (loop)
3702 struct loop_ivs *ivs = LOOP_IVS (loop);
3703 /* Temporary list pointers for traversing ivs->list. */
3704 struct iv_class *bl;
3708 /* Find initial value for each biv by searching backwards from loop_start,
3709 halting at first label. Also record any test condition. */
3712 for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3718 if (GET_CODE (p) == CALL_INSN)
3722 note_stores (PATTERN (p), record_initial, ivs);
3724 /* Record any test of a biv that branches around the loop if no store
3725 between it and the start of loop. We only care about tests with
3726 constants and registers and only certain of those. */
3727 if (GET_CODE (p) == JUMP_INSN
3728 && JUMP_LABEL (p) != 0
3729 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
3730 && (test = get_condition_for_loop (loop, p)) != 0
3731 && GET_CODE (XEXP (test, 0)) == REG
3732 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3733 && (bl = REG_IV_CLASS (ivs, REGNO (XEXP (test, 0)))) != 0
3734 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop->start)
3735 && bl->init_insn == 0)
3737 /* If an NE test, we have an initial value! */
3738 if (GET_CODE (test) == NE)
3741 bl->init_set = gen_rtx_SET (VOIDmode,
3742 XEXP (test, 0), XEXP (test, 1));
3745 bl->initial_test = test;
3751 /* Look at the each biv and see if we can say anything better about its
3752 initial value from any initializing insns set up above. (This is done
3753 in two passes to avoid missing SETs in a PARALLEL.) */
3755 loop_bivs_check (loop)
3758 struct loop_ivs *ivs = LOOP_IVS (loop);
3759 /* Temporary list pointers for traversing ivs->list. */
3760 struct iv_class *bl;
3761 struct iv_class **backbl;
3763 for (backbl = &ivs->list; (bl = *backbl); backbl = &bl->next)
3768 if (! bl->init_insn)
3771 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3772 is a constant, use the value of that. */
3773 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3774 && CONSTANT_P (XEXP (note, 0)))
3775 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3776 && CONSTANT_P (XEXP (note, 0))))
3777 src = XEXP (note, 0);
3779 src = SET_SRC (bl->init_set);
3781 if (loop_dump_stream)
3782 fprintf (loop_dump_stream,
3783 "Biv %d initialized at insn %d: initial value ",
3784 bl->regno, INSN_UID (bl->init_insn));
3786 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3787 || GET_MODE (src) == VOIDmode)
3788 && valid_initial_value_p (src, bl->init_insn,
3789 LOOP_INFO (loop)->pre_header_has_call,
3792 bl->initial_value = src;
3794 if (loop_dump_stream)
3796 if (GET_CODE (src) == CONST_INT)
3798 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
3800 fputc ('\n', loop_dump_stream);
3804 print_rtl (loop_dump_stream, src);
3805 fprintf (loop_dump_stream, "\n");
3809 /* If we can't make it a giv,
3810 let biv keep initial value of "itself". */
3811 else if (loop_dump_stream)
3812 fprintf (loop_dump_stream, "is complex\n");
3817 /* Search the loop for general induction variables. */
3820 loop_givs_find (loop)
3823 for_each_insn_in_loop (loop, check_insn_for_givs);
3827 /* For each giv for which we still don't know whether or not it is
3828 replaceable, check to see if it is replaceable because its final value
3829 can be calculated. */
3832 loop_givs_check (loop)
3835 struct loop_ivs *ivs = LOOP_IVS (loop);
3836 struct iv_class *bl;
3838 for (bl = ivs->list; bl; bl = bl->next)
3840 struct induction *v;
3842 for (v = bl->giv; v; v = v->next_iv)
3843 if (! v->replaceable && ! v->not_replaceable)
3844 check_final_value (loop, v);
3849 /* Return non-zero if it is possible to eliminate the biv BL provided
3850 all givs are reduced. This is possible if either the reg is not
3851 used outside the loop, or we can compute what its final value will
3855 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3857 struct iv_class *bl;
3861 /* For architectures with a decrement_and_branch_until_zero insn,
3862 don't do this if we put a REG_NONNEG note on the endtest for this
3865 #ifdef HAVE_decrement_and_branch_until_zero
3868 if (loop_dump_stream)
3869 fprintf (loop_dump_stream,
3870 "Cannot eliminate nonneg biv %d.\n", bl->regno);
3875 /* Check that biv is used outside loop or if it has a final value.
3876 Compare against bl->init_insn rather than loop->start. We aren't
3877 concerned with any uses of the biv between init_insn and
3878 loop->start since these won't be affected by the value of the biv
3879 elsewhere in the function, so long as init_insn doesn't use the
3882 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3884 && INSN_UID (bl->init_insn) < max_uid_for_loop
3885 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3886 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3887 || (bl->final_value = final_biv_value (loop, bl)))
3888 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3890 if (loop_dump_stream)
3892 fprintf (loop_dump_stream,
3893 "Cannot eliminate biv %d.\n",
3895 fprintf (loop_dump_stream,
3896 "First use: insn %d, last use: insn %d.\n",
3897 REGNO_FIRST_UID (bl->regno),
3898 REGNO_LAST_UID (bl->regno));
3904 /* Reduce each giv of BL that we have decided to reduce. */
3907 loop_givs_reduce (loop, bl)
3909 struct iv_class *bl;
3911 struct induction *v;
3913 for (v = bl->giv; v; v = v->next_iv)
3915 struct induction *tv;
3916 if (! v->ignore && v->same == 0)
3918 int auto_inc_opt = 0;
3920 /* If the code for derived givs immediately below has already
3921 allocated a new_reg, we must keep it. */
3923 v->new_reg = gen_reg_rtx (v->mode);
3926 /* If the target has auto-increment addressing modes, and
3927 this is an address giv, then try to put the increment
3928 immediately after its use, so that flow can create an
3929 auto-increment addressing mode. */
3930 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
3931 && bl->biv->always_executed && ! bl->biv->maybe_multiple
3932 /* We don't handle reversed biv's because bl->biv->insn
3933 does not have a valid INSN_LUID. */
3935 && v->always_executed && ! v->maybe_multiple
3936 && INSN_UID (v->insn) < max_uid_for_loop)
3938 /* If other giv's have been combined with this one, then
3939 this will work only if all uses of the other giv's occur
3940 before this giv's insn. This is difficult to check.
3942 We simplify this by looking for the common case where
3943 there is one DEST_REG giv, and this giv's insn is the
3944 last use of the dest_reg of that DEST_REG giv. If the
3945 increment occurs after the address giv, then we can
3946 perform the optimization. (Otherwise, the increment
3947 would have to go before other_giv, and we would not be
3948 able to combine it with the address giv to get an
3949 auto-inc address.) */
3950 if (v->combined_with)
3952 struct induction *other_giv = 0;
3954 for (tv = bl->giv; tv; tv = tv->next_iv)
3962 if (! tv && other_giv
3963 && REGNO (other_giv->dest_reg) < max_reg_before_loop
3964 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
3965 == INSN_UID (v->insn))
3966 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
3969 /* Check for case where increment is before the address
3970 giv. Do this test in "loop order". */
3971 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
3972 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3973 || (INSN_LUID (bl->biv->insn)
3974 > INSN_LUID (loop->scan_start))))
3975 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3976 && (INSN_LUID (loop->scan_start)
3977 < INSN_LUID (bl->biv->insn))))
3986 /* We can't put an insn immediately after one setting
3987 cc0, or immediately before one using cc0. */
3988 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
3989 || (auto_inc_opt == -1
3990 && (prev = prev_nonnote_insn (v->insn)) != 0
3992 && sets_cc0_p (PATTERN (prev))))
3998 v->auto_inc_opt = 1;
4002 /* For each place where the biv is incremented, add an insn
4003 to increment the new, reduced reg for the giv. */
4004 for (tv = bl->biv; tv; tv = tv->next_iv)
4009 insert_before = tv->insn;
4010 else if (auto_inc_opt == 1)
4011 insert_before = NEXT_INSN (v->insn);
4013 insert_before = v->insn;
4015 if (tv->mult_val == const1_rtx)
4016 emit_iv_add_mult (tv->add_val, v->mult_val,
4017 v->new_reg, v->new_reg, insert_before);
4018 else /* tv->mult_val == const0_rtx */
4019 /* A multiply is acceptable here
4020 since this is presumed to be seldom executed. */
4021 emit_iv_add_mult (tv->add_val, v->mult_val,
4022 v->add_val, v->new_reg, insert_before);
4025 /* Add code at loop start to initialize giv's reduced reg. */
4027 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4028 v->mult_val, v->add_val, v->new_reg,
4035 /* Check for givs whose first use is their definition and whose
4036 last use is the definition of another giv. If so, it is likely
4037 dead and should not be used to derive another giv nor to
4041 loop_givs_dead_check (loop, bl)
4042 struct loop *loop ATTRIBUTE_UNUSED;
4043 struct iv_class *bl;
4045 struct induction *v;
4047 for (v = bl->giv; v; v = v->next_iv)
4050 || (v->same && v->same->ignore))
4053 if (v->giv_type == DEST_REG
4054 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4056 struct induction *v1;
4058 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4059 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4067 loop_givs_rescan (loop, bl, reg_map, end_insert_before)
4069 struct iv_class *bl;
4071 rtx end_insert_before;
4073 struct induction *v;
4075 for (v = bl->giv; v; v = v->next_iv)
4077 if (v->same && v->same->ignore)
4083 /* Update expression if this was combined, in case other giv was
4086 v->new_reg = replace_rtx (v->new_reg,
4087 v->same->dest_reg, v->same->new_reg);
4089 /* See if this register is known to be a pointer to something. If
4090 so, see if we can find the alignment. First see if there is a
4091 destination register that is a pointer. If so, this shares the
4092 alignment too. Next see if we can deduce anything from the
4093 computational information. If not, and this is a DEST_ADDR
4094 giv, at least we know that it's a pointer, though we don't know
4096 if (GET_CODE (v->new_reg) == REG
4097 && v->giv_type == DEST_REG
4098 && REG_POINTER (v->dest_reg))
4099 mark_reg_pointer (v->new_reg,
4100 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
4101 else if (GET_CODE (v->new_reg) == REG
4102 && REG_POINTER (v->src_reg))
4104 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4107 || GET_CODE (v->add_val) != CONST_INT
4108 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4111 mark_reg_pointer (v->new_reg, align);
4113 else if (GET_CODE (v->new_reg) == REG
4114 && GET_CODE (v->add_val) == REG
4115 && REG_POINTER (v->add_val))
4117 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4119 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4120 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4123 mark_reg_pointer (v->new_reg, align);
4125 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4126 mark_reg_pointer (v->new_reg, 0);
4128 if (v->giv_type == DEST_ADDR)
4129 /* Store reduced reg as the address in the memref where we found
4131 validate_change (v->insn, v->location, v->new_reg, 0);
4132 else if (v->replaceable)
4134 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4138 /* Not replaceable; emit an insn to set the original giv reg from
4139 the reduced giv, same as above. */
4140 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4144 /* When a loop is reversed, givs which depend on the reversed
4145 biv, and which are live outside the loop, must be set to their
4146 correct final value. This insn is only needed if the giv is
4147 not replaceable. The correct final value is the same as the
4148 value that the giv starts the reversed loop with. */
4149 if (bl->reversed && ! v->replaceable)
4150 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4151 v->mult_val, v->add_val, v->dest_reg,
4153 else if (v->final_value)
4157 /* If the loop has multiple exits, emit the insn before the
4158 loop to ensure that it will always be executed no matter
4159 how the loop exits. Otherwise, emit the insn after the loop,
4160 since this is slightly more efficient. */
4161 if (loop->exit_count)
4162 insert_before = loop->start;
4164 insert_before = end_insert_before;
4165 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4169 if (loop_dump_stream)
4171 fprintf (loop_dump_stream, "giv at %d reduced to ",
4172 INSN_UID (v->insn));
4173 print_rtl (loop_dump_stream, v->new_reg);
4174 fprintf (loop_dump_stream, "\n");
4181 loop_giv_reduce_benefit (loop, bl, v, test_reg)
4182 struct loop *loop ATTRIBUTE_UNUSED;
4183 struct iv_class *bl;
4184 struct induction *v;
4190 benefit = v->benefit;
4191 PUT_MODE (test_reg, v->mode);
4192 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4193 test_reg, test_reg);
4195 /* Reduce benefit if not replaceable, since we will insert a
4196 move-insn to replace the insn that calculates this giv. Don't do
4197 this unless the giv is a user variable, since it will often be
4198 marked non-replaceable because of the duplication of the exit
4199 code outside the loop. In such a case, the copies we insert are
4200 dead and will be deleted. So they don't have a cost. Similar
4201 situations exist. */
4202 /* ??? The new final_[bg]iv_value code does a much better job of
4203 finding replaceable giv's, and hence this code may no longer be
4205 if (! v->replaceable && ! bl->eliminable
4206 && REG_USERVAR_P (v->dest_reg))
4207 benefit -= copy_cost;
4209 /* Decrease the benefit to count the add-insns that we will insert
4210 to increment the reduced reg for the giv. ??? This can
4211 overestimate the run-time cost of the additional insns, e.g. if
4212 there are multiple basic blocks that increment the biv, but only
4213 one of these blocks is executed during each iteration. There is
4214 no good way to detect cases like this with the current structure
4215 of the loop optimizer. This code is more accurate for
4216 determining code size than run-time benefits. */
4217 benefit -= add_cost * bl->biv_count;
4219 /* Decide whether to strength-reduce this giv or to leave the code
4220 unchanged (recompute it from the biv each time it is used). This
4221 decision can be made independently for each giv. */
4224 /* Attempt to guess whether autoincrement will handle some of the
4225 new add insns; if so, increase BENEFIT (undo the subtraction of
4226 add_cost that was done above). */
4227 if (v->giv_type == DEST_ADDR
4228 /* Increasing the benefit is risky, since this is only a guess.
4229 Avoid increasing register pressure in cases where there would
4230 be no other benefit from reducing this giv. */
4232 && GET_CODE (v->mult_val) == CONST_INT)
4234 if (HAVE_POST_INCREMENT
4235 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4236 benefit += add_cost * bl->biv_count;
4237 else if (HAVE_PRE_INCREMENT
4238 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4239 benefit += add_cost * bl->biv_count;
4240 else if (HAVE_POST_DECREMENT
4241 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4242 benefit += add_cost * bl->biv_count;
4243 else if (HAVE_PRE_DECREMENT
4244 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4245 benefit += add_cost * bl->biv_count;
4253 /* Perform strength reduction and induction variable elimination.
4255 Pseudo registers created during this function will be beyond the
4256 last valid index in several tables including regs->n_times_set and
4257 regno_last_uid. This does not cause a problem here, because the
4258 added registers cannot be givs outside of their loop, and hence
4259 will never be reconsidered. But scan_loop must check regnos to
4260 make sure they are in bounds. */
4263 strength_reduce (loop, insn_count, flags)
4268 struct loop_info *loop_info = LOOP_INFO (loop);
4269 struct loop_regs *regs = LOOP_REGS (loop);
4270 struct loop_ivs *ivs = LOOP_IVS (loop);
4272 /* Temporary list pointer for traversing ivs->list. */
4273 struct iv_class *bl;
4274 /* Ratio of extra register life span we can justify
4275 for saving an instruction. More if loop doesn't call subroutines
4276 since in that case saving an insn makes more difference
4277 and more registers are available. */
4278 /* ??? could set this to last value of threshold in move_movables */
4279 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
4280 /* Map of pseudo-register replacements. */
4281 rtx *reg_map = NULL;
4283 rtx end_insert_before;
4284 int unrolled_insn_copies = 0;
4285 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
4287 addr_placeholder = gen_reg_rtx (Pmode);
4289 /* Save insn immediately after the loop_end. Insns inserted after loop_end
4290 must be put before this insn, so that they will appear in the right
4291 order (i.e. loop order).
4293 If loop_end is the end of the current function, then emit a
4294 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
4296 if (NEXT_INSN (loop->end) != 0)
4297 end_insert_before = NEXT_INSN (loop->end);
4299 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop->end);
4301 ivs->n_regs = max_reg_before_loop;
4302 ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
4304 /* Find all BIVs in loop. */
4305 loop_bivs_find (loop);
4307 /* Exit if there are no bivs. */
4310 /* Can still unroll the loop anyways, but indicate that there is no
4311 strength reduction info available. */
4312 if (flags & LOOP_UNROLL)
4313 unroll_loop (loop, insn_count, end_insert_before, 0);
4318 /* Determine how BIVS are initialised by looking through pre-header
4319 extended basic block. */
4320 loop_bivs_init_find (loop);
4322 /* Look at the each biv and see if we can say anything better about its
4323 initial value from any initializing insns set up above. */
4324 loop_bivs_check (loop);
4326 /* Search the loop for general induction variables. */
4327 loop_givs_find (loop);
4329 /* Try to calculate and save the number of loop iterations. This is
4330 set to zero if the actual number can not be calculated. This must
4331 be called after all giv's have been identified, since otherwise it may
4332 fail if the iteration variable is a giv. */
4333 loop_iterations (loop);
4335 /* Now for each giv for which we still don't know whether or not it is
4336 replaceable, check to see if it is replaceable because its final value
4337 can be calculated. This must be done after loop_iterations is called,
4338 so that final_giv_value will work correctly. */
4339 loop_givs_check (loop);
4341 /* Try to prove that the loop counter variable (if any) is always
4342 nonnegative; if so, record that fact with a REG_NONNEG note
4343 so that "decrement and branch until zero" insn can be used. */
4344 check_dbra_loop (loop, insn_count);
4346 /* Create reg_map to hold substitutions for replaceable giv regs.
4347 Some givs might have been made from biv increments, so look at
4348 ivs->reg_iv_type for a suitable size. */
4349 reg_map_size = ivs->n_regs;
4350 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
4352 /* Examine each iv class for feasibility of strength reduction/induction
4353 variable elimination. */
4355 for (bl = ivs->list; bl; bl = bl->next)
4357 struct induction *v;
4360 /* Test whether it will be possible to eliminate this biv
4361 provided all givs are reduced. */
4362 bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
4364 /* Check each extension dependent giv in this class to see if its
4365 root biv is safe from wrapping in the interior mode. */
4366 check_ext_dependant_givs (bl, loop_info);
4368 /* Combine all giv's for this iv_class. */
4369 combine_givs (regs, bl);
4371 /* This will be true at the end, if all givs which depend on this
4372 biv have been strength reduced.
4373 We can't (currently) eliminate the biv unless this is so. */
4374 bl->all_reduced = 1;
4376 for (v = bl->giv; v; v = v->next_iv)
4378 struct induction *tv;
4380 if (v->ignore || v->same)
4383 benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
4385 /* If an insn is not to be strength reduced, then set its ignore
4386 flag, and clear bl->all_reduced. */
4388 /* A giv that depends on a reversed biv must be reduced if it is
4389 used after the loop exit, otherwise, it would have the wrong
4390 value after the loop exit. To make it simple, just reduce all
4391 of such giv's whether or not we know they are used after the loop
4394 if (! flag_reduce_all_givs
4395 && v->lifetime * threshold * benefit < insn_count
4398 if (loop_dump_stream)
4399 fprintf (loop_dump_stream,
4400 "giv of insn %d not worth while, %d vs %d.\n",
4402 v->lifetime * threshold * benefit, insn_count);
4404 bl->all_reduced = 0;
4408 /* Check that we can increment the reduced giv without a
4409 multiply insn. If not, reject it. */
4411 for (tv = bl->biv; tv; tv = tv->next_iv)
4412 if (tv->mult_val == const1_rtx
4413 && ! product_cheap_p (tv->add_val, v->mult_val))
4415 if (loop_dump_stream)
4416 fprintf (loop_dump_stream,
4417 "giv of insn %d: would need a multiply.\n",
4418 INSN_UID (v->insn));
4420 bl->all_reduced = 0;
4426 /* Check for givs whose first use is their definition and whose
4427 last use is the definition of another giv. If so, it is likely
4428 dead and should not be used to derive another giv nor to
4430 loop_givs_dead_check (loop, bl);
4432 /* Reduce each giv that we decided to reduce. */
4433 loop_givs_reduce (loop, bl);
4435 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4438 For each giv register that can be reduced now: if replaceable,
4439 substitute reduced reg wherever the old giv occurs;
4440 else add new move insn "giv_reg = reduced_reg". */
4441 loop_givs_rescan (loop, bl, reg_map, end_insert_before);
4443 /* All the givs based on the biv bl have been reduced if they
4446 /* For each giv not marked as maybe dead that has been combined with a
4447 second giv, clear any "maybe dead" mark on that second giv.
4448 v->new_reg will either be or refer to the register of the giv it
4451 Doing this clearing avoids problems in biv elimination where
4452 a giv's new_reg is a complex value that can't be put in the
4453 insn but the giv combined with (with a reg as new_reg) is
4454 marked maybe_dead. Since the register will be used in either
4455 case, we'd prefer it be used from the simpler giv. */
4457 for (v = bl->giv; v; v = v->next_iv)
4458 if (! v->maybe_dead && v->same)
4459 v->same->maybe_dead = 0;
4461 /* Try to eliminate the biv, if it is a candidate.
4462 This won't work if ! bl->all_reduced,
4463 since the givs we planned to use might not have been reduced.
4465 We have to be careful that we didn't initially think we could
4466 eliminate this biv because of a giv that we now think may be
4467 dead and shouldn't be used as a biv replacement.
4469 Also, there is the possibility that we may have a giv that looks
4470 like it can be used to eliminate a biv, but the resulting insn
4471 isn't valid. This can happen, for example, on the 88k, where a
4472 JUMP_INSN can compare a register only with zero. Attempts to
4473 replace it with a compare with a constant will fail.
4475 Note that in cases where this call fails, we may have replaced some
4476 of the occurrences of the biv with a giv, but no harm was done in
4477 doing so in the rare cases where it can occur. */
4479 if (bl->all_reduced == 1 && bl->eliminable
4480 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4482 /* ?? If we created a new test to bypass the loop entirely,
4483 or otherwise drop straight in, based on this test, then
4484 we might want to rewrite it also. This way some later
4485 pass has more hope of removing the initialization of this
4488 /* If final_value != 0, then the biv may be used after loop end
4489 and we must emit an insn to set it just in case.
4491 Reversed bivs already have an insn after the loop setting their
4492 value, so we don't need another one. We can't calculate the
4493 proper final value for such a biv here anyways. */
4494 if (bl->final_value && ! bl->reversed)
4498 /* If the loop has multiple exits, emit the insn before the
4499 loop to ensure that it will always be executed no matter
4500 how the loop exits. Otherwise, emit the insn after the
4501 loop, since this is slightly more efficient. */
4502 if (loop->exit_count)
4503 insert_before = loop->start;
4505 insert_before = end_insert_before;
4507 emit_insn_before (gen_move_insn (bl->biv->dest_reg,
4512 if (loop_dump_stream)
4513 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4518 /* Go through all the instructions in the loop, making all the
4519 register substitutions scheduled in REG_MAP. */
4521 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
4522 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4523 || GET_CODE (p) == CALL_INSN)
4525 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4526 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4530 if (loop_info->n_iterations > 0)
4532 /* When we completely unroll a loop we will likely not need the increment
4533 of the loop BIV and we will not need the conditional branch at the
4535 unrolled_insn_copies = insn_count - 2;
4538 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4539 need the comparison before the conditional branch at the end of the
4541 unrolled_insn_copies -= 1;
4544 /* We'll need one copy for each loop iteration. */
4545 unrolled_insn_copies *= loop_info->n_iterations;
4547 /* A little slop to account for the ability to remove initialization
4548 code, better CSE, and other secondary benefits of completely
4549 unrolling some loops. */
4550 unrolled_insn_copies -= 1;
4552 /* Clamp the value. */
4553 if (unrolled_insn_copies < 0)
4554 unrolled_insn_copies = 0;
4557 /* Unroll loops from within strength reduction so that we can use the
4558 induction variable information that strength_reduce has already
4559 collected. Always unroll loops that would be as small or smaller
4560 unrolled than when rolled. */
4561 if ((flags & LOOP_UNROLL)
4562 || (loop_info->n_iterations > 0
4563 && unrolled_insn_copies <= insn_count))
4564 unroll_loop (loop, insn_count, end_insert_before, 1);
4566 #ifdef HAVE_doloop_end
4567 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4568 doloop_optimize (loop);
4569 #endif /* HAVE_doloop_end */
4571 if (loop_dump_stream)
4572 fprintf (loop_dump_stream, "\n");
4577 struct iv_class *iv = ivs->list;
4580 struct iv_class *next = iv->next;
4581 struct induction *induction;
4582 struct induction *next_induction;
4584 for (induction = iv->biv; induction; induction = next_induction)
4586 next_induction = induction->next_iv;
4589 for (induction = iv->giv; induction; induction = next_induction)
4591 next_induction = induction->next_iv;
4603 /*Record all basic induction variables calculated in the insn. */
4605 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4608 int not_every_iteration;
4611 struct loop_ivs *ivs = LOOP_IVS (loop);
4618 if (GET_CODE (p) == INSN
4619 && (set = single_set (p))
4620 && GET_CODE (SET_DEST (set)) == REG)
4622 dest_reg = SET_DEST (set);
4623 if (REGNO (dest_reg) < max_reg_before_loop
4624 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4625 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4627 if (basic_induction_var (loop, SET_SRC (set),
4628 GET_MODE (SET_SRC (set)),
4629 dest_reg, p, &inc_val, &mult_val,
4632 /* It is a possible basic induction variable.
4633 Create and initialize an induction structure for it. */
4636 = (struct induction *) xmalloc (sizeof (struct induction));
4638 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4639 not_every_iteration, maybe_multiple);
4640 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4642 else if (REGNO (dest_reg) < max_reg_before_loop)
4643 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4649 /* Record all givs calculated in the insn.
4650 A register is a giv if: it is only set once, it is a function of a
4651 biv and a constant (or invariant), and it is not a biv. */
4653 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4656 int not_every_iteration;
4659 struct loop_regs *regs = LOOP_REGS (loop);
4662 /* Look for a general induction variable in a register. */
4663 if (GET_CODE (p) == INSN
4664 && (set = single_set (p))
4665 && GET_CODE (SET_DEST (set)) == REG
4666 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
4675 rtx last_consec_insn;
4677 dest_reg = SET_DEST (set);
4678 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4681 if (/* SET_SRC is a giv. */
4682 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4683 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4684 /* Equivalent expression is a giv. */
4685 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4686 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4687 &add_val, &mult_val, &ext_val, 0,
4688 &benefit, VOIDmode)))
4689 /* Don't try to handle any regs made by loop optimization.
4690 We have nothing on them in regno_first_uid, etc. */
4691 && REGNO (dest_reg) < max_reg_before_loop
4692 /* Don't recognize a BASIC_INDUCT_VAR here. */
4693 && dest_reg != src_reg
4694 /* This must be the only place where the register is set. */
4695 && (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) == 1
4696 /* or all sets must be consecutive and make a giv. */
4697 || (benefit = consec_sets_giv (loop, benefit, p,
4699 &add_val, &mult_val, &ext_val,
4700 &last_consec_insn))))
4703 = (struct induction *) xmalloc (sizeof (struct induction));
4705 /* If this is a library call, increase benefit. */
4706 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4707 benefit += libcall_benefit (p);
4709 /* Skip the consecutive insns, if there are any. */
4710 if (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) != 1)
4711 p = last_consec_insn;
4713 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4714 ext_val, benefit, DEST_REG, not_every_iteration,
4715 maybe_multiple, NULL_PTR);
4720 #ifndef DONT_REDUCE_ADDR
4721 /* Look for givs which are memory addresses. */
4722 /* This resulted in worse code on a VAX 8600. I wonder if it
4724 if (GET_CODE (p) == INSN)
4725 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4729 /* Update the status of whether giv can derive other givs. This can
4730 change when we pass a label or an insn that updates a biv. */
4731 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4732 || GET_CODE (p) == CODE_LABEL)
4733 update_giv_derive (loop, p);
4737 /* Return 1 if X is a valid source for an initial value (or as value being
4738 compared against in an initial test).
4740 X must be either a register or constant and must not be clobbered between
4741 the current insn and the start of the loop.
4743 INSN is the insn containing X. */
4746 valid_initial_value_p (x, insn, call_seen, loop_start)
4755 /* Only consider pseudos we know about initialized in insns whose luids
4757 if (GET_CODE (x) != REG
4758 || REGNO (x) >= max_reg_before_loop)
4761 /* Don't use call-clobbered registers across a call which clobbers it. On
4762 some machines, don't use any hard registers at all. */
4763 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4764 && (SMALL_REGISTER_CLASSES
4765 || (call_used_regs[REGNO (x)] && call_seen)))
4768 /* Don't use registers that have been clobbered before the start of the
4770 if (reg_set_between_p (x, insn, loop_start))
4776 /* Scan X for memory refs and check each memory address
4777 as a possible giv. INSN is the insn whose pattern X comes from.
4778 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4779 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4780 more thanonce in each loop iteration. */
4783 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4784 const struct loop *loop;
4787 int not_every_iteration, maybe_multiple;
4790 register enum rtx_code code;
4791 register const char *fmt;
4796 code = GET_CODE (x);
4821 /* This code used to disable creating GIVs with mult_val == 1 and
4822 add_val == 0. However, this leads to lost optimizations when
4823 it comes time to combine a set of related DEST_ADDR GIVs, since
4824 this one would not be seen. */
4826 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4827 &mult_val, &ext_val, 1, &benefit,
4830 /* Found one; record it. */
4832 = (struct induction *) xmalloc (sizeof (struct induction));
4834 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4835 add_val, ext_val, benefit, DEST_ADDR,
4836 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4838 v->mem_mode = GET_MODE (x);
4847 /* Recursively scan the subexpressions for other mem refs. */
4849 fmt = GET_RTX_FORMAT (code);
4850 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4852 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4854 else if (fmt[i] == 'E')
4855 for (j = 0; j < XVECLEN (x, i); j++)
4856 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4860 /* Fill in the data about one biv update.
4861 V is the `struct induction' in which we record the biv. (It is
4862 allocated by the caller, with alloca.)
4863 INSN is the insn that sets it.
4864 DEST_REG is the biv's reg.
4866 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4867 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4868 being set to INC_VAL.
4870 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4871 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4872 can be executed more than once per iteration. If MAYBE_MULTIPLE
4873 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4874 executed exactly once per iteration. */
4877 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4878 not_every_iteration, maybe_multiple)
4880 struct induction *v;
4886 int not_every_iteration;
4889 struct loop_ivs *ivs = LOOP_IVS (loop);
4890 struct iv_class *bl;
4893 v->src_reg = dest_reg;
4894 v->dest_reg = dest_reg;
4895 v->mult_val = mult_val;
4896 v->add_val = inc_val;
4897 v->ext_dependant = NULL_RTX;
4898 v->location = location;
4899 v->mode = GET_MODE (dest_reg);
4900 v->always_computable = ! not_every_iteration;
4901 v->always_executed = ! not_every_iteration;
4902 v->maybe_multiple = maybe_multiple;
4904 /* Add this to the reg's iv_class, creating a class
4905 if this is the first incrementation of the reg. */
4907 bl = REG_IV_CLASS (ivs, REGNO (dest_reg));
4910 /* Create and initialize new iv_class. */
4912 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4914 bl->regno = REGNO (dest_reg);
4920 /* Set initial value to the reg itself. */
4921 bl->initial_value = dest_reg;
4922 bl->final_value = 0;
4923 /* We haven't seen the initializing insn yet */
4926 bl->initial_test = 0;
4927 bl->incremented = 0;
4931 bl->total_benefit = 0;
4933 /* Add this class to ivs->list. */
4934 bl->next = ivs->list;
4937 /* Put it in the array of biv register classes. */
4938 REG_IV_CLASS (ivs, REGNO (dest_reg)) = bl;
4941 /* Update IV_CLASS entry for this biv. */
4942 v->next_iv = bl->biv;
4945 if (mult_val == const1_rtx)
4946 bl->incremented = 1;
4948 if (loop_dump_stream)
4950 fprintf (loop_dump_stream,
4951 "Insn %d: possible biv, reg %d,",
4952 INSN_UID (insn), REGNO (dest_reg));
4953 if (GET_CODE (inc_val) == CONST_INT)
4955 fprintf (loop_dump_stream, " const =");
4956 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4957 fputc ('\n', loop_dump_stream);
4961 fprintf (loop_dump_stream, " const = ");
4962 print_rtl (loop_dump_stream, inc_val);
4963 fprintf (loop_dump_stream, "\n");
4968 /* Fill in the data about one giv.
4969 V is the `struct induction' in which we record the giv. (It is
4970 allocated by the caller, with alloca.)
4971 INSN is the insn that sets it.
4972 BENEFIT estimates the savings from deleting this insn.
4973 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4974 into a register or is used as a memory address.
4976 SRC_REG is the biv reg which the giv is computed from.
4977 DEST_REG is the giv's reg (if the giv is stored in a reg).
4978 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4979 LOCATION points to the place where this giv's value appears in INSN. */
4982 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4983 benefit, type, not_every_iteration, maybe_multiple, location)
4984 const struct loop *loop;
4985 struct induction *v;
4989 rtx mult_val, add_val, ext_val;
4992 int not_every_iteration, maybe_multiple;
4995 struct loop_ivs *ivs = LOOP_IVS (loop);
4996 struct induction *b;
4997 struct iv_class *bl;
4998 rtx set = single_set (insn);
5001 /* Attempt to prove constantness of the values. */
5002 temp = simplify_rtx (add_val);
5007 v->src_reg = src_reg;
5009 v->dest_reg = dest_reg;
5010 v->mult_val = mult_val;
5011 v->add_val = add_val;
5012 v->ext_dependant = ext_val;
5013 v->benefit = benefit;
5014 v->location = location;
5016 v->combined_with = 0;
5017 v->maybe_multiple = maybe_multiple;
5019 v->derive_adjustment = 0;
5025 v->auto_inc_opt = 0;
5029 /* The v->always_computable field is used in update_giv_derive, to
5030 determine whether a giv can be used to derive another giv. For a
5031 DEST_REG giv, INSN computes a new value for the giv, so its value
5032 isn't computable if INSN insn't executed every iteration.
5033 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
5034 it does not compute a new value. Hence the value is always computable
5035 regardless of whether INSN is executed each iteration. */
5037 if (type == DEST_ADDR)
5038 v->always_computable = 1;
5040 v->always_computable = ! not_every_iteration;
5042 v->always_executed = ! not_every_iteration;
5044 if (type == DEST_ADDR)
5046 v->mode = GET_MODE (*location);
5049 else /* type == DEST_REG */
5051 v->mode = GET_MODE (SET_DEST (set));
5053 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
5055 /* If the lifetime is zero, it means that this register is
5056 really a dead store. So mark this as a giv that can be
5057 ignored. This will not prevent the biv from being eliminated. */
5058 if (v->lifetime == 0)
5061 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
5062 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
5065 /* Add the giv to the class of givs computed from one biv. */
5067 bl = REG_IV_CLASS (ivs, REGNO (src_reg));
5070 v->next_iv = bl->giv;
5072 /* Don't count DEST_ADDR. This is supposed to count the number of
5073 insns that calculate givs. */
5074 if (type == DEST_REG)
5076 bl->total_benefit += benefit;
5079 /* Fatal error, biv missing for this giv? */
5082 if (type == DEST_ADDR)
5086 /* The giv can be replaced outright by the reduced register only if all
5087 of the following conditions are true:
5088 - the insn that sets the giv is always executed on any iteration
5089 on which the giv is used at all
5090 (there are two ways to deduce this:
5091 either the insn is executed on every iteration,
5092 or all uses follow that insn in the same basic block),
5093 - the giv is not used outside the loop
5094 - no assignments to the biv occur during the giv's lifetime. */
5096 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
5097 /* Previous line always fails if INSN was moved by loop opt. */
5098 && REGNO_LAST_LUID (REGNO (dest_reg))
5099 < INSN_LUID (loop->end)
5100 && (! not_every_iteration
5101 || last_use_this_basic_block (dest_reg, insn)))
5103 /* Now check that there are no assignments to the biv within the
5104 giv's lifetime. This requires two separate checks. */
5106 /* Check each biv update, and fail if any are between the first
5107 and last use of the giv.
5109 If this loop contains an inner loop that was unrolled, then
5110 the insn modifying the biv may have been emitted by the loop
5111 unrolling code, and hence does not have a valid luid. Just
5112 mark the biv as not replaceable in this case. It is not very
5113 useful as a biv, because it is used in two different loops.
5114 It is very unlikely that we would be able to optimize the giv
5115 using this biv anyways. */
5118 for (b = bl->biv; b; b = b->next_iv)
5120 if (INSN_UID (b->insn) >= max_uid_for_loop
5121 || ((INSN_LUID (b->insn)
5122 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5123 && (INSN_LUID (b->insn)
5124 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5127 v->not_replaceable = 1;
5132 /* If there are any backwards branches that go from after the
5133 biv update to before it, then this giv is not replaceable. */
5135 for (b = bl->biv; b; b = b->next_iv)
5136 if (back_branch_in_range_p (loop, b->insn))
5139 v->not_replaceable = 1;
5145 /* May still be replaceable, we don't have enough info here to
5148 v->not_replaceable = 0;
5152 /* Record whether the add_val contains a const_int, for later use by
5157 v->no_const_addval = 1;
5158 if (tem == const0_rtx)
5160 else if (CONSTANT_P (add_val))
5161 v->no_const_addval = 0;
5162 if (GET_CODE (tem) == PLUS)
5166 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5167 tem = XEXP (tem, 0);
5168 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5169 tem = XEXP (tem, 1);
5173 if (CONSTANT_P (XEXP (tem, 1)))
5174 v->no_const_addval = 0;
5178 if (loop_dump_stream)
5180 if (type == DEST_REG)
5181 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5182 INSN_UID (insn), REGNO (dest_reg));
5184 fprintf (loop_dump_stream, "Insn %d: dest address",
5187 fprintf (loop_dump_stream, " src reg %d benefit %d",
5188 REGNO (src_reg), v->benefit);
5189 fprintf (loop_dump_stream, " lifetime %d",
5193 fprintf (loop_dump_stream, " replaceable");
5195 if (v->no_const_addval)
5196 fprintf (loop_dump_stream, " ncav");
5198 if (v->ext_dependant)
5200 switch (GET_CODE (v->ext_dependant))
5203 fprintf (loop_dump_stream, " ext se");
5206 fprintf (loop_dump_stream, " ext ze");
5209 fprintf (loop_dump_stream, " ext tr");
5216 if (GET_CODE (mult_val) == CONST_INT)
5218 fprintf (loop_dump_stream, " mult ");
5219 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5223 fprintf (loop_dump_stream, " mult ");
5224 print_rtl (loop_dump_stream, mult_val);
5227 if (GET_CODE (add_val) == CONST_INT)
5229 fprintf (loop_dump_stream, " add ");
5230 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5234 fprintf (loop_dump_stream, " add ");
5235 print_rtl (loop_dump_stream, add_val);
5239 if (loop_dump_stream)
5240 fprintf (loop_dump_stream, "\n");
5244 /* All this does is determine whether a giv can be made replaceable because
5245 its final value can be calculated. This code can not be part of record_giv
5246 above, because final_giv_value requires that the number of loop iterations
5247 be known, and that can not be accurately calculated until after all givs
5248 have been identified. */
5251 check_final_value (loop, v)
5252 const struct loop *loop;
5253 struct induction *v;
5255 struct loop_ivs *ivs = LOOP_IVS (loop);
5256 struct iv_class *bl;
5257 rtx final_value = 0;
5259 bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
5261 /* DEST_ADDR givs will never reach here, because they are always marked
5262 replaceable above in record_giv. */
5264 /* The giv can be replaced outright by the reduced register only if all
5265 of the following conditions are true:
5266 - the insn that sets the giv is always executed on any iteration
5267 on which the giv is used at all
5268 (there are two ways to deduce this:
5269 either the insn is executed on every iteration,
5270 or all uses follow that insn in the same basic block),
5271 - its final value can be calculated (this condition is different
5272 than the one above in record_giv)
5273 - it's not used before the it's set
5274 - no assignments to the biv occur during the giv's lifetime. */
5277 /* This is only called now when replaceable is known to be false. */
5278 /* Clear replaceable, so that it won't confuse final_giv_value. */
5282 if ((final_value = final_giv_value (loop, v))
5283 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5285 int biv_increment_seen = 0, before_giv_insn = 0;
5291 /* When trying to determine whether or not a biv increment occurs
5292 during the lifetime of the giv, we can ignore uses of the variable
5293 outside the loop because final_value is true. Hence we can not
5294 use regno_last_uid and regno_first_uid as above in record_giv. */
5296 /* Search the loop to determine whether any assignments to the
5297 biv occur during the giv's lifetime. Start with the insn
5298 that sets the giv, and search around the loop until we come
5299 back to that insn again.
5301 Also fail if there is a jump within the giv's lifetime that jumps
5302 to somewhere outside the lifetime but still within the loop. This
5303 catches spaghetti code where the execution order is not linear, and
5304 hence the above test fails. Here we assume that the giv lifetime
5305 does not extend from one iteration of the loop to the next, so as
5306 to make the test easier. Since the lifetime isn't known yet,
5307 this requires two loops. See also record_giv above. */
5309 last_giv_use = v->insn;
5316 before_giv_insn = 1;
5317 p = NEXT_INSN (loop->start);
5322 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5323 || GET_CODE (p) == CALL_INSN)
5325 /* It is possible for the BIV increment to use the GIV if we
5326 have a cycle. Thus we must be sure to check each insn for
5327 both BIV and GIV uses, and we must check for BIV uses
5330 if (! biv_increment_seen
5331 && reg_set_p (v->src_reg, PATTERN (p)))
5332 biv_increment_seen = 1;
5334 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5336 if (biv_increment_seen || before_giv_insn)
5339 v->not_replaceable = 1;
5347 /* Now that the lifetime of the giv is known, check for branches
5348 from within the lifetime to outside the lifetime if it is still
5358 p = NEXT_INSN (loop->start);
5359 if (p == last_giv_use)
5362 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5363 && LABEL_NAME (JUMP_LABEL (p))
5364 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5365 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5366 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5367 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5370 v->not_replaceable = 1;
5372 if (loop_dump_stream)
5373 fprintf (loop_dump_stream,
5374 "Found branch outside giv lifetime.\n");
5381 /* If it is replaceable, then save the final value. */
5383 v->final_value = final_value;
5386 if (loop_dump_stream && v->replaceable)
5387 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5388 INSN_UID (v->insn), REGNO (v->dest_reg));
5391 /* Update the status of whether a giv can derive other givs.
5393 We need to do something special if there is or may be an update to the biv
5394 between the time the giv is defined and the time it is used to derive
5397 In addition, a giv that is only conditionally set is not allowed to
5398 derive another giv once a label has been passed.
5400 The cases we look at are when a label or an update to a biv is passed. */
5403 update_giv_derive (loop, p)
5404 const struct loop *loop;
5407 struct loop_ivs *ivs = LOOP_IVS (loop);
5408 struct iv_class *bl;
5409 struct induction *biv, *giv;
5413 /* Search all IV classes, then all bivs, and finally all givs.
5415 There are three cases we are concerned with. First we have the situation
5416 of a giv that is only updated conditionally. In that case, it may not
5417 derive any givs after a label is passed.
5419 The second case is when a biv update occurs, or may occur, after the
5420 definition of a giv. For certain biv updates (see below) that are
5421 known to occur between the giv definition and use, we can adjust the
5422 giv definition. For others, or when the biv update is conditional,
5423 we must prevent the giv from deriving any other givs. There are two
5424 sub-cases within this case.
5426 If this is a label, we are concerned with any biv update that is done
5427 conditionally, since it may be done after the giv is defined followed by
5428 a branch here (actually, we need to pass both a jump and a label, but
5429 this extra tracking doesn't seem worth it).
5431 If this is a jump, we are concerned about any biv update that may be
5432 executed multiple times. We are actually only concerned about
5433 backward jumps, but it is probably not worth performing the test
5434 on the jump again here.
5436 If this is a biv update, we must adjust the giv status to show that a
5437 subsequent biv update was performed. If this adjustment cannot be done,
5438 the giv cannot derive further givs. */
5440 for (bl = ivs->list; bl; bl = bl->next)
5441 for (biv = bl->biv; biv; biv = biv->next_iv)
5442 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5445 for (giv = bl->giv; giv; giv = giv->next_iv)
5447 /* If cant_derive is already true, there is no point in
5448 checking all of these conditions again. */
5449 if (giv->cant_derive)
5452 /* If this giv is conditionally set and we have passed a label,
5453 it cannot derive anything. */
5454 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5455 giv->cant_derive = 1;
5457 /* Skip givs that have mult_val == 0, since
5458 they are really invariants. Also skip those that are
5459 replaceable, since we know their lifetime doesn't contain
5461 else if (giv->mult_val == const0_rtx || giv->replaceable)
5464 /* The only way we can allow this giv to derive another
5465 is if this is a biv increment and we can form the product
5466 of biv->add_val and giv->mult_val. In this case, we will
5467 be able to compute a compensation. */
5468 else if (biv->insn == p)
5473 if (biv->mult_val == const1_rtx)
5474 tem = simplify_giv_expr (loop,
5475 gen_rtx_MULT (giv->mode,
5478 &ext_val_dummy, &dummy);
5480 if (tem && giv->derive_adjustment)
5481 tem = simplify_giv_expr
5483 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5484 &ext_val_dummy, &dummy);
5487 giv->derive_adjustment = tem;
5489 giv->cant_derive = 1;
5491 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5492 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5493 giv->cant_derive = 1;
5498 /* Check whether an insn is an increment legitimate for a basic induction var.
5499 X is the source of insn P, or a part of it.
5500 MODE is the mode in which X should be interpreted.
5502 DEST_REG is the putative biv, also the destination of the insn.
5503 We accept patterns of these forms:
5504 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5505 REG = INVARIANT + REG
5507 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5508 store the additive term into *INC_VAL, and store the place where
5509 we found the additive term into *LOCATION.
5511 If X is an assignment of an invariant into DEST_REG, we set
5512 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5514 We also want to detect a BIV when it corresponds to a variable
5515 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5516 of the variable may be a PLUS that adds a SUBREG of that variable to
5517 an invariant and then sign- or zero-extends the result of the PLUS
5520 Most GIVs in such cases will be in the promoted mode, since that is the
5521 probably the natural computation mode (and almost certainly the mode
5522 used for addresses) on the machine. So we view the pseudo-reg containing
5523 the variable as the BIV, as if it were simply incremented.
5525 Note that treating the entire pseudo as a BIV will result in making
5526 simple increments to any GIVs based on it. However, if the variable
5527 overflows in its declared mode but not its promoted mode, the result will
5528 be incorrect. This is acceptable if the variable is signed, since
5529 overflows in such cases are undefined, but not if it is unsigned, since
5530 those overflows are defined. So we only check for SIGN_EXTEND and
5533 If we cannot find a biv, we return 0. */
5536 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5537 const struct loop *loop;
5539 enum machine_mode mode;
5546 register enum rtx_code code;
5550 code = GET_CODE (x);
5555 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5556 || (GET_CODE (XEXP (x, 0)) == SUBREG
5557 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5558 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5560 argp = &XEXP (x, 1);
5562 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5563 || (GET_CODE (XEXP (x, 1)) == SUBREG
5564 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5565 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5567 argp = &XEXP (x, 0);
5573 if (loop_invariant_p (loop, arg) != 1)
5576 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5577 *mult_val = const1_rtx;
5582 /* If this is a SUBREG for a promoted variable, check the inner
5584 if (SUBREG_PROMOTED_VAR_P (x))
5585 return basic_induction_var (loop, SUBREG_REG (x),
5586 GET_MODE (SUBREG_REG (x)),
5587 dest_reg, p, inc_val, mult_val, location);
5591 /* If this register is assigned in a previous insn, look at its
5592 source, but don't go outside the loop or past a label. */
5594 /* If this sets a register to itself, we would repeat any previous
5595 biv increment if we applied this strategy blindly. */
5596 if (rtx_equal_p (dest_reg, x))
5605 insn = PREV_INSN (insn);
5607 while (insn && GET_CODE (insn) == NOTE
5608 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5612 set = single_set (insn);
5615 dest = SET_DEST (set);
5617 || (GET_CODE (dest) == SUBREG
5618 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5619 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5620 && SUBREG_REG (dest) == x))
5621 return basic_induction_var (loop, SET_SRC (set),
5622 (GET_MODE (SET_SRC (set)) == VOIDmode
5624 : GET_MODE (SET_SRC (set))),
5626 inc_val, mult_val, location);
5628 while (GET_CODE (dest) == SIGN_EXTRACT
5629 || GET_CODE (dest) == ZERO_EXTRACT
5630 || GET_CODE (dest) == SUBREG
5631 || GET_CODE (dest) == STRICT_LOW_PART)
5632 dest = XEXP (dest, 0);
5638 /* Can accept constant setting of biv only when inside inner most loop.
5639 Otherwise, a biv of an inner loop may be incorrectly recognized
5640 as a biv of the outer loop,
5641 causing code to be moved INTO the inner loop. */
5643 if (loop_invariant_p (loop, x) != 1)
5648 /* convert_modes aborts if we try to convert to or from CCmode, so just
5649 exclude that case. It is very unlikely that a condition code value
5650 would be a useful iterator anyways. */
5651 if (loop->level == 1
5652 && GET_MODE_CLASS (mode) != MODE_CC
5653 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5655 /* Possible bug here? Perhaps we don't know the mode of X. */
5656 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5657 *mult_val = const0_rtx;
5664 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5665 dest_reg, p, inc_val, mult_val, location);
5668 /* Similar, since this can be a sign extension. */
5669 for (insn = PREV_INSN (p);
5670 (insn && GET_CODE (insn) == NOTE
5671 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5672 insn = PREV_INSN (insn))
5676 set = single_set (insn);
5678 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5679 && set && SET_DEST (set) == XEXP (x, 0)
5680 && GET_CODE (XEXP (x, 1)) == CONST_INT
5681 && INTVAL (XEXP (x, 1)) >= 0
5682 && GET_CODE (SET_SRC (set)) == ASHIFT
5683 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5684 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5685 GET_MODE (XEXP (x, 0)),
5686 dest_reg, insn, inc_val, mult_val,
5695 /* A general induction variable (giv) is any quantity that is a linear
5696 function of a basic induction variable,
5697 i.e. giv = biv * mult_val + add_val.
5698 The coefficients can be any loop invariant quantity.
5699 A giv need not be computed directly from the biv;
5700 it can be computed by way of other givs. */
5702 /* Determine whether X computes a giv.
5703 If it does, return a nonzero value
5704 which is the benefit from eliminating the computation of X;
5705 set *SRC_REG to the register of the biv that it is computed from;
5706 set *ADD_VAL and *MULT_VAL to the coefficients,
5707 such that the value of X is biv * mult + add; */
5710 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5711 is_addr, pbenefit, addr_mode)
5712 const struct loop *loop;
5720 enum machine_mode addr_mode;
5722 struct loop_ivs *ivs = LOOP_IVS (loop);
5725 /* If this is an invariant, forget it, it isn't a giv. */
5726 if (loop_invariant_p (loop, x) == 1)
5730 *ext_val = NULL_RTX;
5731 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5735 switch (GET_CODE (x))
5739 /* Since this is now an invariant and wasn't before, it must be a giv
5740 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5742 *src_reg = ivs->list->biv->dest_reg;
5743 *mult_val = const0_rtx;
5748 /* This is equivalent to a BIV. */
5750 *mult_val = const1_rtx;
5751 *add_val = const0_rtx;
5755 /* Either (plus (biv) (invar)) or
5756 (plus (mult (biv) (invar_1)) (invar_2)). */
5757 if (GET_CODE (XEXP (x, 0)) == MULT)
5759 *src_reg = XEXP (XEXP (x, 0), 0);
5760 *mult_val = XEXP (XEXP (x, 0), 1);
5764 *src_reg = XEXP (x, 0);
5765 *mult_val = const1_rtx;
5767 *add_val = XEXP (x, 1);
5771 /* ADD_VAL is zero. */
5772 *src_reg = XEXP (x, 0);
5773 *mult_val = XEXP (x, 1);
5774 *add_val = const0_rtx;
5781 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5782 unless they are CONST_INT). */
5783 if (GET_CODE (*add_val) == USE)
5784 *add_val = XEXP (*add_val, 0);
5785 if (GET_CODE (*mult_val) == USE)
5786 *mult_val = XEXP (*mult_val, 0);
5789 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5791 *pbenefit += rtx_cost (orig_x, SET);
5793 /* Always return true if this is a giv so it will be detected as such,
5794 even if the benefit is zero or negative. This allows elimination
5795 of bivs that might otherwise not be eliminated. */
5799 /* Given an expression, X, try to form it as a linear function of a biv.
5800 We will canonicalize it to be of the form
5801 (plus (mult (BIV) (invar_1))
5803 with possible degeneracies.
5805 The invariant expressions must each be of a form that can be used as a
5806 machine operand. We surround then with a USE rtx (a hack, but localized
5807 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5808 routine; it is the caller's responsibility to strip them.
5810 If no such canonicalization is possible (i.e., two biv's are used or an
5811 expression that is neither invariant nor a biv or giv), this routine
5814 For a non-zero return, the result will have a code of CONST_INT, USE,
5815 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5817 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5819 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5820 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5823 simplify_giv_expr (loop, x, ext_val, benefit)
5824 const struct loop *loop;
5829 struct loop_ivs *ivs = LOOP_IVS (loop);
5830 struct loop_regs *regs = LOOP_REGS (loop);
5831 enum machine_mode mode = GET_MODE (x);
5835 /* If this is not an integer mode, or if we cannot do arithmetic in this
5836 mode, this can't be a giv. */
5837 if (mode != VOIDmode
5838 && (GET_MODE_CLASS (mode) != MODE_INT
5839 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5842 switch (GET_CODE (x))
5845 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5846 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5847 if (arg0 == 0 || arg1 == 0)
5850 /* Put constant last, CONST_INT last if both constant. */
5851 if ((GET_CODE (arg0) == USE
5852 || GET_CODE (arg0) == CONST_INT)
5853 && ! ((GET_CODE (arg0) == USE
5854 && GET_CODE (arg1) == USE)
5855 || GET_CODE (arg1) == CONST_INT))
5856 tem = arg0, arg0 = arg1, arg1 = tem;
5858 /* Handle addition of zero, then addition of an invariant. */
5859 if (arg1 == const0_rtx)
5861 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5862 switch (GET_CODE (arg0))
5866 /* Adding two invariants must result in an invariant, so enclose
5867 addition operation inside a USE and return it. */
5868 if (GET_CODE (arg0) == USE)
5869 arg0 = XEXP (arg0, 0);
5870 if (GET_CODE (arg1) == USE)
5871 arg1 = XEXP (arg1, 0);
5873 if (GET_CODE (arg0) == CONST_INT)
5874 tem = arg0, arg0 = arg1, arg1 = tem;
5875 if (GET_CODE (arg1) == CONST_INT)
5876 tem = sge_plus_constant (arg0, arg1);
5878 tem = sge_plus (mode, arg0, arg1);
5880 if (GET_CODE (tem) != CONST_INT)
5881 tem = gen_rtx_USE (mode, tem);
5886 /* biv + invar or mult + invar. Return sum. */
5887 return gen_rtx_PLUS (mode, arg0, arg1);
5890 /* (a + invar_1) + invar_2. Associate. */
5892 simplify_giv_expr (loop,
5904 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5905 MULT to reduce cases. */
5906 if (GET_CODE (arg0) == REG)
5907 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5908 if (GET_CODE (arg1) == REG)
5909 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5911 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5912 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5913 Recurse to associate the second PLUS. */
5914 if (GET_CODE (arg1) == MULT)
5915 tem = arg0, arg0 = arg1, arg1 = tem;
5917 if (GET_CODE (arg1) == PLUS)
5919 simplify_giv_expr (loop,
5921 gen_rtx_PLUS (mode, arg0,
5926 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5927 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5930 if (!rtx_equal_p (arg0, arg1))
5933 return simplify_giv_expr (loop,
5942 /* Handle "a - b" as "a + b * (-1)". */
5943 return simplify_giv_expr (loop,
5952 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5953 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5954 if (arg0 == 0 || arg1 == 0)
5957 /* Put constant last, CONST_INT last if both constant. */
5958 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5959 && GET_CODE (arg1) != CONST_INT)
5960 tem = arg0, arg0 = arg1, arg1 = tem;
5962 /* If second argument is not now constant, not giv. */
5963 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5966 /* Handle multiply by 0 or 1. */
5967 if (arg1 == const0_rtx)
5970 else if (arg1 == const1_rtx)
5973 switch (GET_CODE (arg0))
5976 /* biv * invar. Done. */
5977 return gen_rtx_MULT (mode, arg0, arg1);
5980 /* Product of two constants. */
5981 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5984 /* invar * invar is a giv, but attempt to simplify it somehow. */
5985 if (GET_CODE (arg1) != CONST_INT)
5988 arg0 = XEXP (arg0, 0);
5989 if (GET_CODE (arg0) == MULT)
5991 /* (invar_0 * invar_1) * invar_2. Associate. */
5992 return simplify_giv_expr (loop,
6001 /* Porpagate the MULT expressions to the intermost nodes. */
6002 else if (GET_CODE (arg0) == PLUS)
6004 /* (invar_0 + invar_1) * invar_2. Distribute. */
6005 return simplify_giv_expr (loop,
6017 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
6020 /* (a * invar_1) * invar_2. Associate. */
6021 return simplify_giv_expr (loop,
6030 /* (a + invar_1) * invar_2. Distribute. */
6031 return simplify_giv_expr (loop,
6046 /* Shift by constant is multiply by power of two. */
6047 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
6051 simplify_giv_expr (loop,
6054 GEN_INT ((HOST_WIDE_INT) 1
6055 << INTVAL (XEXP (x, 1)))),
6059 /* "-a" is "a * (-1)" */
6060 return simplify_giv_expr (loop,
6061 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
6065 /* "~a" is "-a - 1". Silly, but easy. */
6066 return simplify_giv_expr (loop,
6067 gen_rtx_MINUS (mode,
6068 gen_rtx_NEG (mode, XEXP (x, 0)),
6073 /* Already in proper form for invariant. */
6079 /* Conditionally recognize extensions of simple IVs. After we've
6080 computed loop traversal counts and verified the range of the
6081 source IV, we'll reevaluate this as a GIV. */
6082 if (*ext_val == NULL_RTX)
6084 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
6085 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
6087 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
6094 /* If this is a new register, we can't deal with it. */
6095 if (REGNO (x) >= max_reg_before_loop)
6098 /* Check for biv or giv. */
6099 switch (REG_IV_TYPE (ivs, REGNO (x)))
6103 case GENERAL_INDUCT:
6105 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
6107 /* Form expression from giv and add benefit. Ensure this giv
6108 can derive another and subtract any needed adjustment if so. */
6110 /* Increasing the benefit here is risky. The only case in which it
6111 is arguably correct is if this is the only use of V. In other
6112 cases, this will artificially inflate the benefit of the current
6113 giv, and lead to suboptimal code. Thus, it is disabled, since
6114 potentially not reducing an only marginally beneficial giv is
6115 less harmful than reducing many givs that are not really
6118 rtx single_use = VARRAY_RTX (regs->single_usage, REGNO (x));
6119 if (single_use && single_use != const0_rtx)
6120 *benefit += v->benefit;
6126 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
6127 v->src_reg, v->mult_val),
6130 if (v->derive_adjustment)
6131 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
6132 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
6135 if (!v->ext_dependant)
6140 *ext_val = v->ext_dependant;
6148 /* If it isn't an induction variable, and it is invariant, we
6149 may be able to simplify things further by looking through
6150 the bits we just moved outside the loop. */
6151 if (loop_invariant_p (loop, x) == 1)
6154 struct loop_movables *movables = LOOP_MOVABLES (loop);
6156 for (m = movables->head; m; m = m->next)
6157 if (rtx_equal_p (x, m->set_dest))
6159 /* Ok, we found a match. Substitute and simplify. */
6161 /* If we match another movable, we must use that, as
6162 this one is going away. */
6164 return simplify_giv_expr (loop, m->match->set_dest,
6167 /* If consec is non-zero, this is a member of a group of
6168 instructions that were moved together. We handle this
6169 case only to the point of seeking to the last insn and
6170 looking for a REG_EQUAL. Fail if we don't find one. */
6177 tem = NEXT_INSN (tem);
6181 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6183 tem = XEXP (tem, 0);
6187 tem = single_set (m->insn);
6189 tem = SET_SRC (tem);
6194 /* What we are most interested in is pointer
6195 arithmetic on invariants -- only take
6196 patterns we may be able to do something with. */
6197 if (GET_CODE (tem) == PLUS
6198 || GET_CODE (tem) == MULT
6199 || GET_CODE (tem) == ASHIFT
6200 || GET_CODE (tem) == CONST_INT
6201 || GET_CODE (tem) == SYMBOL_REF)
6203 tem = simplify_giv_expr (loop, tem, ext_val,
6208 else if (GET_CODE (tem) == CONST
6209 && GET_CODE (XEXP (tem, 0)) == PLUS
6210 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6211 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6213 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6225 /* Fall through to general case. */
6227 /* If invariant, return as USE (unless CONST_INT).
6228 Otherwise, not giv. */
6229 if (GET_CODE (x) == USE)
6232 if (loop_invariant_p (loop, x) == 1)
6234 if (GET_CODE (x) == CONST_INT)
6236 if (GET_CODE (x) == CONST
6237 && GET_CODE (XEXP (x, 0)) == PLUS
6238 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6239 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6241 return gen_rtx_USE (mode, x);
6248 /* This routine folds invariants such that there is only ever one
6249 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6252 sge_plus_constant (x, c)
6255 if (GET_CODE (x) == CONST_INT)
6256 return GEN_INT (INTVAL (x) + INTVAL (c));
6257 else if (GET_CODE (x) != PLUS)
6258 return gen_rtx_PLUS (GET_MODE (x), x, c);
6259 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6261 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6262 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6264 else if (GET_CODE (XEXP (x, 0)) == PLUS
6265 || GET_CODE (XEXP (x, 1)) != PLUS)
6267 return gen_rtx_PLUS (GET_MODE (x),
6268 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6272 return gen_rtx_PLUS (GET_MODE (x),
6273 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6278 sge_plus (mode, x, y)
6279 enum machine_mode mode;
6282 while (GET_CODE (y) == PLUS)
6284 rtx a = XEXP (y, 0);
6285 if (GET_CODE (a) == CONST_INT)
6286 x = sge_plus_constant (x, a);
6288 x = gen_rtx_PLUS (mode, x, a);
6291 if (GET_CODE (y) == CONST_INT)
6292 x = sge_plus_constant (x, y);
6294 x = gen_rtx_PLUS (mode, x, y);
6298 /* Help detect a giv that is calculated by several consecutive insns;
6302 The caller has already identified the first insn P as having a giv as dest;
6303 we check that all other insns that set the same register follow
6304 immediately after P, that they alter nothing else,
6305 and that the result of the last is still a giv.
6307 The value is 0 if the reg set in P is not really a giv.
6308 Otherwise, the value is the amount gained by eliminating
6309 all the consecutive insns that compute the value.
6311 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6312 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6314 The coefficients of the ultimate giv value are stored in
6315 *MULT_VAL and *ADD_VAL. */
6318 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6319 add_val, mult_val, ext_val, last_consec_insn)
6320 const struct loop *loop;
6328 rtx *last_consec_insn;
6330 struct loop_ivs *ivs = LOOP_IVS (loop);
6331 struct loop_regs *regs = LOOP_REGS (loop);
6338 /* Indicate that this is a giv so that we can update the value produced in
6339 each insn of the multi-insn sequence.
6341 This induction structure will be used only by the call to
6342 general_induction_var below, so we can allocate it on our stack.
6343 If this is a giv, our caller will replace the induct var entry with
6344 a new induction structure. */
6345 struct induction *v;
6347 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6350 v = (struct induction *) alloca (sizeof (struct induction));
6351 v->src_reg = src_reg;
6352 v->mult_val = *mult_val;
6353 v->add_val = *add_val;
6354 v->benefit = first_benefit;
6356 v->derive_adjustment = 0;
6357 v->ext_dependant = NULL_RTX;
6359 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6360 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6362 count = VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) - 1;
6367 code = GET_CODE (p);
6369 /* If libcall, skip to end of call sequence. */
6370 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6374 && (set = single_set (p))
6375 && GET_CODE (SET_DEST (set)) == REG
6376 && SET_DEST (set) == dest_reg
6377 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6378 add_val, mult_val, ext_val, 0,
6380 /* Giv created by equivalent expression. */
6381 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6382 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6383 add_val, mult_val, ext_val, 0,
6384 &benefit, VOIDmode)))
6385 && src_reg == v->src_reg)
6387 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6388 benefit += libcall_benefit (p);
6391 v->mult_val = *mult_val;
6392 v->add_val = *add_val;
6393 v->benefit += benefit;
6395 else if (code != NOTE)
6397 /* Allow insns that set something other than this giv to a
6398 constant. Such insns are needed on machines which cannot
6399 include long constants and should not disqualify a giv. */
6401 && (set = single_set (p))
6402 && SET_DEST (set) != dest_reg
6403 && CONSTANT_P (SET_SRC (set)))
6406 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6411 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6412 *last_consec_insn = p;
6416 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6417 represented by G1. If no such expression can be found, or it is clear that
6418 it cannot possibly be a valid address, 0 is returned.
6420 To perform the computation, we note that
6423 where `v' is the biv.
6425 So G2 = (y/b) * G1 + (b - a*y/x).
6427 Note that MULT = y/x.
6429 Update: A and B are now allowed to be additive expressions such that
6430 B contains all variables in A. That is, computing B-A will not require
6431 subtracting variables. */
6434 express_from_1 (a, b, mult)
6437 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6439 if (mult == const0_rtx)
6442 /* If MULT is not 1, we cannot handle A with non-constants, since we
6443 would then be required to subtract multiples of the registers in A.
6444 This is theoretically possible, and may even apply to some Fortran
6445 constructs, but it is a lot of work and we do not attempt it here. */
6447 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6450 /* In general these structures are sorted top to bottom (down the PLUS
6451 chain), but not left to right across the PLUS. If B is a higher
6452 order giv than A, we can strip one level and recurse. If A is higher
6453 order, we'll eventually bail out, but won't know that until the end.
6454 If they are the same, we'll strip one level around this loop. */
6456 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6458 rtx ra, rb, oa, ob, tmp;
6460 ra = XEXP (a, 0), oa = XEXP (a, 1);
6461 if (GET_CODE (ra) == PLUS)
6462 tmp = ra, ra = oa, oa = tmp;
6464 rb = XEXP (b, 0), ob = XEXP (b, 1);
6465 if (GET_CODE (rb) == PLUS)
6466 tmp = rb, rb = ob, ob = tmp;
6468 if (rtx_equal_p (ra, rb))
6469 /* We matched: remove one reg completely. */
6471 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6472 /* An alternate match. */
6474 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6475 /* An alternate match. */
6479 /* Indicates an extra register in B. Strip one level from B and
6480 recurse, hoping B was the higher order expression. */
6481 ob = express_from_1 (a, ob, mult);
6484 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6488 /* Here we are at the last level of A, go through the cases hoping to
6489 get rid of everything but a constant. */
6491 if (GET_CODE (a) == PLUS)
6495 ra = XEXP (a, 0), oa = XEXP (a, 1);
6496 if (rtx_equal_p (oa, b))
6498 else if (!rtx_equal_p (ra, b))
6501 if (GET_CODE (oa) != CONST_INT)
6504 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6506 else if (GET_CODE (a) == CONST_INT)
6508 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6510 else if (CONSTANT_P (a))
6512 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6514 else if (GET_CODE (b) == PLUS)
6516 if (rtx_equal_p (a, XEXP (b, 0)))
6518 else if (rtx_equal_p (a, XEXP (b, 1)))
6523 else if (rtx_equal_p (a, b))
6530 express_from (g1, g2)
6531 struct induction *g1, *g2;
6535 /* The value that G1 will be multiplied by must be a constant integer. Also,
6536 the only chance we have of getting a valid address is if b*c/a (see above
6537 for notation) is also an integer. */
6538 if (GET_CODE (g1->mult_val) == CONST_INT
6539 && GET_CODE (g2->mult_val) == CONST_INT)
6541 if (g1->mult_val == const0_rtx
6542 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6544 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6546 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6550 /* ??? Find out if the one is a multiple of the other? */
6554 add = express_from_1 (g1->add_val, g2->add_val, mult);
6555 if (add == NULL_RTX)
6557 /* Failed. If we've got a multiplication factor between G1 and G2,
6558 scale G1's addend and try again. */
6559 if (INTVAL (mult) > 1)
6561 rtx g1_add_val = g1->add_val;
6562 if (GET_CODE (g1_add_val) == MULT
6563 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6566 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6567 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6568 XEXP (g1_add_val, 0), GEN_INT (m));
6572 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6576 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6579 if (add == NULL_RTX)
6582 /* Form simplified final result. */
6583 if (mult == const0_rtx)
6585 else if (mult == const1_rtx)
6586 mult = g1->dest_reg;
6588 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6590 if (add == const0_rtx)
6594 if (GET_CODE (add) == PLUS
6595 && CONSTANT_P (XEXP (add, 1)))
6597 rtx tem = XEXP (add, 1);
6598 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6602 return gen_rtx_PLUS (g2->mode, mult, add);
6606 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6607 represented by G1. This indicates that G2 should be combined with G1 and
6608 that G2 can use (either directly or via an address expression) a register
6609 used to represent G1. */
6612 combine_givs_p (g1, g2)
6613 struct induction *g1, *g2;
6617 /* With the introduction of ext dependant givs, we must care for modes.
6618 G2 must not use a wider mode than G1. */
6619 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6622 ret = comb = express_from (g1, g2);
6623 if (comb == NULL_RTX)
6625 if (g1->mode != g2->mode)
6626 ret = gen_lowpart (g2->mode, comb);
6628 /* If these givs are identical, they can be combined. We use the results
6629 of express_from because the addends are not in a canonical form, so
6630 rtx_equal_p is a weaker test. */
6631 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6632 combination to be the other way round. */
6633 if (comb == g1->dest_reg
6634 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6639 /* If G2 can be expressed as a function of G1 and that function is valid
6640 as an address and no more expensive than using a register for G2,
6641 the expression of G2 in terms of G1 can be used. */
6643 && g2->giv_type == DEST_ADDR
6644 && memory_address_p (g2->mem_mode, ret)
6645 /* ??? Looses, especially with -fforce-addr, where *g2->location
6646 will always be a register, and so anything more complicated
6650 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6652 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6663 /* Check each extension dependant giv in this class to see if its
6664 root biv is safe from wrapping in the interior mode, which would
6665 make the giv illegal. */
6668 check_ext_dependant_givs (bl, loop_info)
6669 struct iv_class *bl;
6670 struct loop_info *loop_info;
6672 int ze_ok = 0, se_ok = 0, info_ok = 0;
6673 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6674 HOST_WIDE_INT start_val;
6675 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6677 struct induction *v;
6679 /* Make sure the iteration data is available. We must have
6680 constants in order to be certain of no overflow. */
6681 /* ??? An unknown iteration count with an increment of +-1
6682 combined with friendly exit tests of against an invariant
6683 value is also ameanable to optimization. Not implemented. */
6684 if (loop_info->n_iterations > 0
6685 && bl->initial_value
6686 && GET_CODE (bl->initial_value) == CONST_INT
6687 && (incr = biv_total_increment (bl))
6688 && GET_CODE (incr) == CONST_INT
6689 /* Make sure the host can represent the arithmetic. */
6690 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6692 unsigned HOST_WIDE_INT abs_incr, total_incr;
6693 HOST_WIDE_INT s_end_val;
6697 start_val = INTVAL (bl->initial_value);
6698 u_start_val = start_val;
6700 neg_incr = 0, abs_incr = INTVAL (incr);
6701 if (INTVAL (incr) < 0)
6702 neg_incr = 1, abs_incr = -abs_incr;
6703 total_incr = abs_incr * loop_info->n_iterations;
6705 /* Check for host arithmatic overflow. */
6706 if (total_incr / loop_info->n_iterations == abs_incr)
6708 unsigned HOST_WIDE_INT u_max;
6709 HOST_WIDE_INT s_max;
6711 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6712 s_end_val = u_end_val;
6713 u_max = GET_MODE_MASK (biv_mode);
6716 /* Check zero extension of biv ok. */
6718 /* Check for host arithmatic overflow. */
6720 ? u_end_val < u_start_val
6721 : u_end_val > u_start_val)
6722 /* Check for target arithmetic overflow. */
6724 ? 1 /* taken care of with host overflow */
6725 : u_end_val <= u_max))
6730 /* Check sign extension of biv ok. */
6731 /* ??? While it is true that overflow with signed and pointer
6732 arithmetic is undefined, I fear too many programmers don't
6733 keep this fact in mind -- myself included on occasion.
6734 So leave alone with the signed overflow optimizations. */
6735 if (start_val >= -s_max - 1
6736 /* Check for host arithmatic overflow. */
6738 ? s_end_val < start_val
6739 : s_end_val > start_val)
6740 /* Check for target arithmetic overflow. */
6742 ? s_end_val >= -s_max - 1
6743 : s_end_val <= s_max))
6750 /* Invalidate givs that fail the tests. */
6751 for (v = bl->giv; v; v = v->next_iv)
6752 if (v->ext_dependant)
6754 enum rtx_code code = GET_CODE (v->ext_dependant);
6767 /* We don't know whether this value is being used as either
6768 signed or unsigned, so to safely truncate we must satisfy
6769 both. The initial check here verifies the BIV itself;
6770 once that is successful we may check its range wrt the
6774 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6775 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6777 /* We know from the above that both endpoints are nonnegative,
6778 and that there is no wrapping. Verify that both endpoints
6779 are within the (signed) range of the outer mode. */
6780 if (u_start_val <= max && u_end_val <= max)
6791 if (loop_dump_stream)
6793 fprintf (loop_dump_stream,
6794 "Verified ext dependant giv at %d of reg %d\n",
6795 INSN_UID (v->insn), bl->regno);
6800 if (loop_dump_stream)
6805 why = "biv iteration values overflowed";
6809 incr = biv_total_increment (bl);
6810 if (incr == const1_rtx)
6811 why = "biv iteration info incomplete; incr by 1";
6813 why = "biv iteration info incomplete";
6816 fprintf (loop_dump_stream,
6817 "Failed ext dependant giv at %d, %s\n",
6818 INSN_UID (v->insn), why);
6825 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6828 extend_value_for_giv (v, value)
6829 struct induction *v;
6832 rtx ext_dep = v->ext_dependant;
6837 /* Recall that check_ext_dependant_givs verified that the known bounds
6838 of a biv did not overflow or wrap with respect to the extension for
6839 the giv. Therefore, constants need no additional adjustment. */
6840 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6843 /* Otherwise, we must adjust the value to compensate for the
6844 differing modes of the biv and the giv. */
6845 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6848 struct combine_givs_stats
6855 cmp_combine_givs_stats (xp, yp)
6859 const struct combine_givs_stats * const x =
6860 (const struct combine_givs_stats *) xp;
6861 const struct combine_givs_stats * const y =
6862 (const struct combine_givs_stats *) yp;
6864 d = y->total_benefit - x->total_benefit;
6865 /* Stabilize the sort. */
6867 d = x->giv_number - y->giv_number;
6871 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6872 any other. If so, point SAME to the giv combined with and set NEW_REG to
6873 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6874 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6877 combine_givs (regs, bl)
6878 struct loop_regs *regs;
6879 struct iv_class *bl;
6881 /* Additional benefit to add for being combined multiple times. */
6882 const int extra_benefit = 3;
6884 struct induction *g1, *g2, **giv_array;
6885 int i, j, k, giv_count;
6886 struct combine_givs_stats *stats;
6889 /* Count givs, because bl->giv_count is incorrect here. */
6891 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6896 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6898 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6900 giv_array[i++] = g1;
6902 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6903 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6905 for (i = 0; i < giv_count; i++)
6911 stats[i].giv_number = i;
6913 /* If a DEST_REG GIV is used only once, do not allow it to combine
6914 with anything, for in doing so we will gain nothing that cannot
6915 be had by simply letting the GIV with which we would have combined
6916 to be reduced on its own. The losage shows up in particular with
6917 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6918 be seen elsewhere as well. */
6919 if (g1->giv_type == DEST_REG
6920 && (single_use = VARRAY_RTX (regs->single_usage,
6921 REGNO (g1->dest_reg)))
6922 && single_use != const0_rtx)
6925 this_benefit = g1->benefit;
6926 /* Add an additional weight for zero addends. */
6927 if (g1->no_const_addval)
6930 for (j = 0; j < giv_count; j++)
6936 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6938 can_combine[i * giv_count + j] = this_combine;
6939 this_benefit += g2->benefit + extra_benefit;
6942 stats[i].total_benefit = this_benefit;
6945 /* Iterate, combining until we can't. */
6947 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6949 if (loop_dump_stream)
6951 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6952 for (k = 0; k < giv_count; k++)
6954 g1 = giv_array[stats[k].giv_number];
6955 if (!g1->combined_with && !g1->same)
6956 fprintf (loop_dump_stream, " {%d, %d}",
6957 INSN_UID (giv_array[stats[k].giv_number]->insn),
6958 stats[k].total_benefit);
6960 putc ('\n', loop_dump_stream);
6963 for (k = 0; k < giv_count; k++)
6965 int g1_add_benefit = 0;
6967 i = stats[k].giv_number;
6970 /* If it has already been combined, skip. */
6971 if (g1->combined_with || g1->same)
6974 for (j = 0; j < giv_count; j++)
6977 if (g1 != g2 && can_combine[i * giv_count + j]
6978 /* If it has already been combined, skip. */
6979 && ! g2->same && ! g2->combined_with)
6983 g2->new_reg = can_combine[i * giv_count + j];
6985 g1->combined_with++;
6986 g1->lifetime += g2->lifetime;
6988 g1_add_benefit += g2->benefit;
6990 /* ??? The new final_[bg]iv_value code does a much better job
6991 of finding replaceable giv's, and hence this code may no
6992 longer be necessary. */
6993 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6994 g1_add_benefit -= copy_cost;
6996 /* To help optimize the next set of combinations, remove
6997 this giv from the benefits of other potential mates. */
6998 for (l = 0; l < giv_count; ++l)
7000 int m = stats[l].giv_number;
7001 if (can_combine[m * giv_count + j])
7002 stats[l].total_benefit -= g2->benefit + extra_benefit;
7005 if (loop_dump_stream)
7006 fprintf (loop_dump_stream,
7007 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
7008 INSN_UID (g2->insn), INSN_UID (g1->insn),
7009 g1->benefit, g1_add_benefit, g1->lifetime);
7013 /* To help optimize the next set of combinations, remove
7014 this giv from the benefits of other potential mates. */
7015 if (g1->combined_with)
7017 for (j = 0; j < giv_count; ++j)
7019 int m = stats[j].giv_number;
7020 if (can_combine[m * giv_count + i])
7021 stats[j].total_benefit -= g1->benefit + extra_benefit;
7024 g1->benefit += g1_add_benefit;
7026 /* We've finished with this giv, and everything it touched.
7027 Restart the combination so that proper weights for the
7028 rest of the givs are properly taken into account. */
7029 /* ??? Ideally we would compact the arrays at this point, so
7030 as to not cover old ground. But sanely compacting
7031 can_combine is tricky. */
7041 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
7044 emit_iv_add_mult (b, m, a, reg, insert_before)
7045 rtx b; /* initial value of basic induction variable */
7046 rtx m; /* multiplicative constant */
7047 rtx a; /* additive constant */
7048 rtx reg; /* destination register */
7054 /* Prevent unexpected sharing of these rtx. */
7058 /* Increase the lifetime of any invariants moved further in code. */
7059 update_reg_last_use (a, insert_before);
7060 update_reg_last_use (b, insert_before);
7061 update_reg_last_use (m, insert_before);
7064 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
7066 emit_move_insn (reg, result);
7067 seq = gen_sequence ();
7070 emit_insn_before (seq, insert_before);
7072 /* It is entirely possible that the expansion created lots of new
7073 registers. Iterate over the sequence we just created and
7076 if (GET_CODE (seq) == SEQUENCE)
7079 for (i = 0; i < XVECLEN (seq, 0); ++i)
7081 rtx set = single_set (XVECEXP (seq, 0, i));
7082 if (set && GET_CODE (SET_DEST (set)) == REG)
7083 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
7086 else if (GET_CODE (seq) == SET
7087 && GET_CODE (SET_DEST (seq)) == REG)
7088 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
7091 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
7094 iv_add_mult_cost (b, m, a, reg)
7095 rtx b; /* initial value of basic induction variable */
7096 rtx m; /* multiplicative constant */
7097 rtx a; /* additive constant */
7098 rtx reg; /* destination register */
7104 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
7106 emit_move_insn (reg, result);
7107 last = get_last_insn ();
7110 rtx t = single_set (last);
7112 cost += rtx_cost (SET_SRC (t), SET);
7113 last = PREV_INSN (last);
7119 /* Test whether A * B can be computed without
7120 an actual multiply insn. Value is 1 if so. */
7123 product_cheap_p (a, b)
7131 /* If only one is constant, make it B. */
7132 if (GET_CODE (a) == CONST_INT)
7133 tmp = a, a = b, b = tmp;
7135 /* If first constant, both constant, so don't need multiply. */
7136 if (GET_CODE (a) == CONST_INT)
7139 /* If second not constant, neither is constant, so would need multiply. */
7140 if (GET_CODE (b) != CONST_INT)
7143 /* One operand is constant, so might not need multiply insn. Generate the
7144 code for the multiply and see if a call or multiply, or long sequence
7145 of insns is generated. */
7148 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
7149 tmp = gen_sequence ();
7152 if (GET_CODE (tmp) == SEQUENCE)
7154 if (XVEC (tmp, 0) == 0)
7156 else if (XVECLEN (tmp, 0) > 3)
7159 for (i = 0; i < XVECLEN (tmp, 0); i++)
7161 rtx insn = XVECEXP (tmp, 0, i);
7163 if (GET_CODE (insn) != INSN
7164 || (GET_CODE (PATTERN (insn)) == SET
7165 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
7166 || (GET_CODE (PATTERN (insn)) == PARALLEL
7167 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
7168 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7175 else if (GET_CODE (tmp) == SET
7176 && GET_CODE (SET_SRC (tmp)) == MULT)
7178 else if (GET_CODE (tmp) == PARALLEL
7179 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7180 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7186 /* Check to see if loop can be terminated by a "decrement and branch until
7187 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7188 Also try reversing an increment loop to a decrement loop
7189 to see if the optimization can be performed.
7190 Value is nonzero if optimization was performed. */
7192 /* This is useful even if the architecture doesn't have such an insn,
7193 because it might change a loops which increments from 0 to n to a loop
7194 which decrements from n to 0. A loop that decrements to zero is usually
7195 faster than one that increments from zero. */
7197 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7198 such as approx_final_value, biv_total_increment, loop_iterations, and
7199 final_[bg]iv_value. */
7202 check_dbra_loop (loop, insn_count)
7206 struct loop_info *loop_info = LOOP_INFO (loop);
7207 struct loop_regs *regs = LOOP_REGS (loop);
7208 struct loop_ivs *ivs = LOOP_IVS (loop);
7209 struct iv_class *bl;
7216 rtx before_comparison;
7220 int compare_and_branch;
7221 rtx loop_start = loop->start;
7222 rtx loop_end = loop->end;
7224 /* If last insn is a conditional branch, and the insn before tests a
7225 register value, try to optimize it. Otherwise, we can't do anything. */
7227 jump = PREV_INSN (loop_end);
7228 comparison = get_condition_for_loop (loop, jump);
7229 if (comparison == 0)
7231 if (!onlyjump_p (jump))
7234 /* Try to compute whether the compare/branch at the loop end is one or
7235 two instructions. */
7236 get_condition (jump, &first_compare);
7237 if (first_compare == jump)
7238 compare_and_branch = 1;
7239 else if (first_compare == prev_nonnote_insn (jump))
7240 compare_and_branch = 2;
7245 /* If more than one condition is present to control the loop, then
7246 do not proceed, as this function does not know how to rewrite
7247 loop tests with more than one condition.
7249 Look backwards from the first insn in the last comparison
7250 sequence and see if we've got another comparison sequence. */
7253 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7254 if (GET_CODE (jump1) == JUMP_INSN)
7258 /* Check all of the bivs to see if the compare uses one of them.
7259 Skip biv's set more than once because we can't guarantee that
7260 it will be zero on the last iteration. Also skip if the biv is
7261 used between its update and the test insn. */
7263 for (bl = ivs->list; bl; bl = bl->next)
7265 if (bl->biv_count == 1
7266 && ! bl->biv->maybe_multiple
7267 && bl->biv->dest_reg == XEXP (comparison, 0)
7268 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7276 /* Look for the case where the basic induction variable is always
7277 nonnegative, and equals zero on the last iteration.
7278 In this case, add a reg_note REG_NONNEG, which allows the
7279 m68k DBRA instruction to be used. */
7281 if (((GET_CODE (comparison) == GT
7282 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7283 && INTVAL (XEXP (comparison, 1)) == -1)
7284 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7285 && GET_CODE (bl->biv->add_val) == CONST_INT
7286 && INTVAL (bl->biv->add_val) < 0)
7288 /* Initial value must be greater than 0,
7289 init_val % -dec_value == 0 to ensure that it equals zero on
7290 the last iteration */
7292 if (GET_CODE (bl->initial_value) == CONST_INT
7293 && INTVAL (bl->initial_value) > 0
7294 && (INTVAL (bl->initial_value)
7295 % (-INTVAL (bl->biv->add_val))) == 0)
7297 /* register always nonnegative, add REG_NOTE to branch */
7298 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7300 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7307 /* If the decrement is 1 and the value was tested as >= 0 before
7308 the loop, then we can safely optimize. */
7309 for (p = loop_start; p; p = PREV_INSN (p))
7311 if (GET_CODE (p) == CODE_LABEL)
7313 if (GET_CODE (p) != JUMP_INSN)
7316 before_comparison = get_condition_for_loop (loop, p);
7317 if (before_comparison
7318 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7319 && GET_CODE (before_comparison) == LT
7320 && XEXP (before_comparison, 1) == const0_rtx
7321 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7322 && INTVAL (bl->biv->add_val) == -1)
7324 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7326 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7334 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7335 && INTVAL (bl->biv->add_val) > 0)
7337 /* Try to change inc to dec, so can apply above optimization. */
7339 all registers modified are induction variables or invariant,
7340 all memory references have non-overlapping addresses
7341 (obviously true if only one write)
7342 allow 2 insns for the compare/jump at the end of the loop. */
7343 /* Also, we must avoid any instructions which use both the reversed
7344 biv and another biv. Such instructions will fail if the loop is
7345 reversed. We meet this condition by requiring that either
7346 no_use_except_counting is true, or else that there is only
7348 int num_nonfixed_reads = 0;
7349 /* 1 if the iteration var is used only to count iterations. */
7350 int no_use_except_counting = 0;
7351 /* 1 if the loop has no memory store, or it has a single memory store
7352 which is reversible. */
7353 int reversible_mem_store = 1;
7355 if (bl->giv_count == 0 && ! loop->exit_count)
7357 rtx bivreg = regno_reg_rtx[bl->regno];
7359 /* If there are no givs for this biv, and the only exit is the
7360 fall through at the end of the loop, then
7361 see if perhaps there are no uses except to count. */
7362 no_use_except_counting = 1;
7363 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7366 rtx set = single_set (p);
7368 if (set && GET_CODE (SET_DEST (set)) == REG
7369 && REGNO (SET_DEST (set)) == bl->regno)
7370 /* An insn that sets the biv is okay. */
7372 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7373 || p == prev_nonnote_insn (loop_end))
7374 && reg_mentioned_p (bivreg, PATTERN (p)))
7376 /* If either of these insns uses the biv and sets a pseudo
7377 that has more than one usage, then the biv has uses
7378 other than counting since it's used to derive a value
7379 that is used more than one time. */
7380 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7382 if (regs->multiple_uses)
7384 no_use_except_counting = 0;
7388 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7390 no_use_except_counting = 0;
7396 if (no_use_except_counting)
7397 /* No need to worry about MEMs. */
7399 else if (loop_info->num_mem_sets <= 1)
7401 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7403 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7405 /* If the loop has a single store, and the destination address is
7406 invariant, then we can't reverse the loop, because this address
7407 might then have the wrong value at loop exit.
7408 This would work if the source was invariant also, however, in that
7409 case, the insn should have been moved out of the loop. */
7411 if (loop_info->num_mem_sets == 1)
7413 struct induction *v;
7415 reversible_mem_store
7416 = (! loop_info->unknown_address_altered
7417 && ! loop_info->unknown_constant_address_altered
7418 && ! loop_invariant_p (loop,
7419 XEXP (XEXP (loop_info->store_mems, 0),
7422 /* If the store depends on a register that is set after the
7423 store, it depends on the initial value, and is thus not
7425 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7427 if (v->giv_type == DEST_REG
7428 && reg_mentioned_p (v->dest_reg,
7429 PATTERN (loop_info->first_loop_store_insn))
7430 && loop_insn_first_p (loop_info->first_loop_store_insn,
7432 reversible_mem_store = 0;
7439 /* This code only acts for innermost loops. Also it simplifies
7440 the memory address check by only reversing loops with
7441 zero or one memory access.
7442 Two memory accesses could involve parts of the same array,
7443 and that can't be reversed.
7444 If the biv is used only for counting, than we don't need to worry
7445 about all these things. */
7447 if ((num_nonfixed_reads <= 1
7448 && ! loop_info->has_call
7449 && ! loop_info->has_volatile
7450 && reversible_mem_store
7451 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7452 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7453 && (bl == ivs->list && bl->next == 0))
7454 || no_use_except_counting)
7458 /* Loop can be reversed. */
7459 if (loop_dump_stream)
7460 fprintf (loop_dump_stream, "Can reverse loop\n");
7462 /* Now check other conditions:
7464 The increment must be a constant, as must the initial value,
7465 and the comparison code must be LT.
7467 This test can probably be improved since +/- 1 in the constant
7468 can be obtained by changing LT to LE and vice versa; this is
7472 /* for constants, LE gets turned into LT */
7473 && (GET_CODE (comparison) == LT
7474 || (GET_CODE (comparison) == LE
7475 && no_use_except_counting)))
7477 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7478 rtx initial_value, comparison_value;
7480 enum rtx_code cmp_code;
7481 int comparison_const_width;
7482 unsigned HOST_WIDE_INT comparison_sign_mask;
7484 add_val = INTVAL (bl->biv->add_val);
7485 comparison_value = XEXP (comparison, 1);
7486 if (GET_MODE (comparison_value) == VOIDmode)
7487 comparison_const_width
7488 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7490 comparison_const_width
7491 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7492 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7493 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7494 comparison_sign_mask
7495 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7497 /* If the comparison value is not a loop invariant, then we
7498 can not reverse this loop.
7500 ??? If the insns which initialize the comparison value as
7501 a whole compute an invariant result, then we could move
7502 them out of the loop and proceed with loop reversal. */
7503 if (! loop_invariant_p (loop, comparison_value))
7506 if (GET_CODE (comparison_value) == CONST_INT)
7507 comparison_val = INTVAL (comparison_value);
7508 initial_value = bl->initial_value;
7510 /* Normalize the initial value if it is an integer and
7511 has no other use except as a counter. This will allow
7512 a few more loops to be reversed. */
7513 if (no_use_except_counting
7514 && GET_CODE (comparison_value) == CONST_INT
7515 && GET_CODE (initial_value) == CONST_INT)
7517 comparison_val = comparison_val - INTVAL (bl->initial_value);
7518 /* The code below requires comparison_val to be a multiple
7519 of add_val in order to do the loop reversal, so
7520 round up comparison_val to a multiple of add_val.
7521 Since comparison_value is constant, we know that the
7522 current comparison code is LT. */
7523 comparison_val = comparison_val + add_val - 1;
7525 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7526 /* We postpone overflow checks for COMPARISON_VAL here;
7527 even if there is an overflow, we might still be able to
7528 reverse the loop, if converting the loop exit test to
7530 initial_value = const0_rtx;
7533 /* First check if we can do a vanilla loop reversal. */
7534 if (initial_value == const0_rtx
7535 /* If we have a decrement_and_branch_on_count,
7536 prefer the NE test, since this will allow that
7537 instruction to be generated. Note that we must
7538 use a vanilla loop reversal if the biv is used to
7539 calculate a giv or has a non-counting use. */
7540 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7541 && defined (HAVE_decrement_and_branch_on_count)
7542 && (! (add_val == 1 && loop->vtop
7543 && (bl->biv_count == 0
7544 || no_use_except_counting)))
7546 && GET_CODE (comparison_value) == CONST_INT
7547 /* Now do postponed overflow checks on COMPARISON_VAL. */
7548 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7549 & comparison_sign_mask))
7551 /* Register will always be nonnegative, with value
7552 0 on last iteration */
7553 add_adjust = add_val;
7557 else if (add_val == 1 && loop->vtop
7558 && (bl->biv_count == 0
7559 || no_use_except_counting))
7567 if (GET_CODE (comparison) == LE)
7568 add_adjust -= add_val;
7570 /* If the initial value is not zero, or if the comparison
7571 value is not an exact multiple of the increment, then we
7572 can not reverse this loop. */
7573 if (initial_value == const0_rtx
7574 && GET_CODE (comparison_value) == CONST_INT)
7576 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7581 if (! no_use_except_counting || add_val != 1)
7585 final_value = comparison_value;
7587 /* Reset these in case we normalized the initial value
7588 and comparison value above. */
7589 if (GET_CODE (comparison_value) == CONST_INT
7590 && GET_CODE (initial_value) == CONST_INT)
7592 comparison_value = GEN_INT (comparison_val);
7594 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7596 bl->initial_value = initial_value;
7598 /* Save some info needed to produce the new insns. */
7599 reg = bl->biv->dest_reg;
7600 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7601 if (jump_label == pc_rtx)
7602 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7603 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7605 /* Set start_value; if this is not a CONST_INT, we need
7607 Initialize biv to start_value before loop start.
7608 The old initializing insn will be deleted as a
7609 dead store by flow.c. */
7610 if (initial_value == const0_rtx
7611 && GET_CODE (comparison_value) == CONST_INT)
7613 start_value = GEN_INT (comparison_val - add_adjust);
7614 emit_insn_before (gen_move_insn (reg, start_value),
7617 else if (GET_CODE (initial_value) == CONST_INT)
7619 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7620 enum machine_mode mode = GET_MODE (reg);
7621 enum insn_code icode
7622 = add_optab->handlers[(int) mode].insn_code;
7624 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7625 || ! ((*insn_data[icode].operand[1].predicate)
7626 (comparison_value, mode))
7627 || ! ((*insn_data[icode].operand[2].predicate)
7631 = gen_rtx_PLUS (mode, comparison_value, offset);
7632 emit_insn_before ((GEN_FCN (icode)
7633 (reg, comparison_value, offset)),
7635 if (GET_CODE (comparison) == LE)
7636 final_value = gen_rtx_PLUS (mode, comparison_value,
7639 else if (! add_adjust)
7641 enum machine_mode mode = GET_MODE (reg);
7642 enum insn_code icode
7643 = sub_optab->handlers[(int) mode].insn_code;
7644 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7645 || ! ((*insn_data[icode].operand[1].predicate)
7646 (comparison_value, mode))
7647 || ! ((*insn_data[icode].operand[2].predicate)
7648 (initial_value, mode)))
7651 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7652 emit_insn_before ((GEN_FCN (icode)
7653 (reg, comparison_value, initial_value)),
7657 /* We could handle the other cases too, but it'll be
7658 better to have a testcase first. */
7661 /* We may not have a single insn which can increment a reg, so
7662 create a sequence to hold all the insns from expand_inc. */
7664 expand_inc (reg, new_add_val);
7665 tem = gen_sequence ();
7668 p = emit_insn_before (tem, bl->biv->insn);
7669 delete_insn (bl->biv->insn);
7671 /* Update biv info to reflect its new status. */
7673 bl->initial_value = start_value;
7674 bl->biv->add_val = new_add_val;
7676 /* Update loop info. */
7677 loop_info->initial_value = reg;
7678 loop_info->initial_equiv_value = reg;
7679 loop_info->final_value = const0_rtx;
7680 loop_info->final_equiv_value = const0_rtx;
7681 loop_info->comparison_value = const0_rtx;
7682 loop_info->comparison_code = cmp_code;
7683 loop_info->increment = new_add_val;
7685 /* Inc LABEL_NUSES so that delete_insn will
7686 not delete the label. */
7687 LABEL_NUSES (XEXP (jump_label, 0))++;
7689 /* Emit an insn after the end of the loop to set the biv's
7690 proper exit value if it is used anywhere outside the loop. */
7691 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7693 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7694 emit_insn_after (gen_move_insn (reg, final_value),
7697 /* Delete compare/branch at end of loop. */
7698 delete_insn (PREV_INSN (loop_end));
7699 if (compare_and_branch == 2)
7700 delete_insn (first_compare);
7702 /* Add new compare/branch insn at end of loop. */
7704 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7705 GET_MODE (reg), 0, 0,
7706 XEXP (jump_label, 0));
7707 tem = gen_sequence ();
7709 emit_jump_insn_before (tem, loop_end);
7711 for (tem = PREV_INSN (loop_end);
7712 tem && GET_CODE (tem) != JUMP_INSN;
7713 tem = PREV_INSN (tem))
7717 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7723 /* Increment of LABEL_NUSES done above. */
7724 /* Register is now always nonnegative,
7725 so add REG_NONNEG note to the branch. */
7726 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7732 /* No insn may reference both the reversed and another biv or it
7733 will fail (see comment near the top of the loop reversal
7735 Earlier on, we have verified that the biv has no use except
7736 counting, or it is the only biv in this function.
7737 However, the code that computes no_use_except_counting does
7738 not verify reg notes. It's possible to have an insn that
7739 references another biv, and has a REG_EQUAL note with an
7740 expression based on the reversed biv. To avoid this case,
7741 remove all REG_EQUAL notes based on the reversed biv
7743 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7747 rtx set = single_set (p);
7748 /* If this is a set of a GIV based on the reversed biv, any
7749 REG_EQUAL notes should still be correct. */
7751 || GET_CODE (SET_DEST (set)) != REG
7752 || (size_t) REGNO (SET_DEST (set)) >= ivs->n_regs
7753 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7754 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7755 for (pnote = ®_NOTES (p); *pnote;)
7757 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7758 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7760 *pnote = XEXP (*pnote, 1);
7762 pnote = &XEXP (*pnote, 1);
7766 /* Mark that this biv has been reversed. Each giv which depends
7767 on this biv, and which is also live past the end of the loop
7768 will have to be fixed up. */
7772 if (loop_dump_stream)
7774 fprintf (loop_dump_stream, "Reversed loop");
7776 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7778 fprintf (loop_dump_stream, "\n");
7789 /* Verify whether the biv BL appears to be eliminable,
7790 based on the insns in the loop that refer to it.
7792 If ELIMINATE_P is non-zero, actually do the elimination.
7794 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7795 determine whether invariant insns should be placed inside or at the
7796 start of the loop. */
7799 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7800 const struct loop *loop;
7801 struct iv_class *bl;
7803 int threshold, insn_count;
7805 struct loop_ivs *ivs = LOOP_IVS (loop);
7806 rtx reg = bl->biv->dest_reg;
7807 rtx loop_start = loop->start;
7808 rtx loop_end = loop->end;
7811 /* Scan all insns in the loop, stopping if we find one that uses the
7812 biv in a way that we cannot eliminate. */
7814 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7816 enum rtx_code code = GET_CODE (p);
7817 rtx where = threshold >= insn_count ? loop_start : p;
7819 /* If this is a libcall that sets a giv, skip ahead to its end. */
7820 if (GET_RTX_CLASS (code) == 'i')
7822 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7826 rtx last = XEXP (note, 0);
7827 rtx set = single_set (last);
7829 if (set && GET_CODE (SET_DEST (set)) == REG)
7831 unsigned int regno = REGNO (SET_DEST (set));
7833 if (regno < max_reg_before_loop
7834 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7835 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7840 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7841 && reg_mentioned_p (reg, PATTERN (p))
7842 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7843 eliminate_p, where))
7845 if (loop_dump_stream)
7846 fprintf (loop_dump_stream,
7847 "Cannot eliminate biv %d: biv used in insn %d.\n",
7848 bl->regno, INSN_UID (p));
7855 if (loop_dump_stream)
7856 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7857 bl->regno, eliminate_p ? "was" : "can be");
7864 /* INSN and REFERENCE are instructions in the same insn chain.
7865 Return non-zero if INSN is first. */
7868 loop_insn_first_p (insn, reference)
7869 rtx insn, reference;
7873 for (p = insn, q = reference;;)
7875 /* Start with test for not first so that INSN == REFERENCE yields not
7877 if (q == insn || ! p)
7879 if (p == reference || ! q)
7882 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7883 previous insn, hence the <= comparison below does not work if
7885 if (INSN_UID (p) < max_uid_for_loop
7886 && INSN_UID (q) < max_uid_for_loop
7887 && GET_CODE (p) != NOTE)
7888 return INSN_LUID (p) <= INSN_LUID (q);
7890 if (INSN_UID (p) >= max_uid_for_loop
7891 || GET_CODE (p) == NOTE)
7893 if (INSN_UID (q) >= max_uid_for_loop)
7898 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7899 the offset that we have to take into account due to auto-increment /
7900 div derivation is zero. */
7902 biv_elimination_giv_has_0_offset (biv, giv, insn)
7903 struct induction *biv, *giv;
7906 /* If the giv V had the auto-inc address optimization applied
7907 to it, and INSN occurs between the giv insn and the biv
7908 insn, then we'd have to adjust the value used here.
7909 This is rare, so we don't bother to make this possible. */
7910 if (giv->auto_inc_opt
7911 && ((loop_insn_first_p (giv->insn, insn)
7912 && loop_insn_first_p (insn, biv->insn))
7913 || (loop_insn_first_p (biv->insn, insn)
7914 && loop_insn_first_p (insn, giv->insn))))
7920 /* If BL appears in X (part of the pattern of INSN), see if we can
7921 eliminate its use. If so, return 1. If not, return 0.
7923 If BIV does not appear in X, return 1.
7925 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7926 where extra insns should be added. Depending on how many items have been
7927 moved out of the loop, it will either be before INSN or at the start of
7931 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7932 const struct loop *loop;
7934 struct iv_class *bl;
7938 enum rtx_code code = GET_CODE (x);
7939 rtx reg = bl->biv->dest_reg;
7940 enum machine_mode mode = GET_MODE (reg);
7941 struct induction *v;
7953 /* If we haven't already been able to do something with this BIV,
7954 we can't eliminate it. */
7960 /* If this sets the BIV, it is not a problem. */
7961 if (SET_DEST (x) == reg)
7964 /* If this is an insn that defines a giv, it is also ok because
7965 it will go away when the giv is reduced. */
7966 for (v = bl->giv; v; v = v->next_iv)
7967 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7971 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7973 /* Can replace with any giv that was reduced and
7974 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7975 Require a constant for MULT_VAL, so we know it's nonzero.
7976 ??? We disable this optimization to avoid potential
7979 for (v = bl->giv; v; v = v->next_iv)
7980 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7981 && v->add_val == const0_rtx
7982 && ! v->ignore && ! v->maybe_dead && v->always_computable
7986 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7992 /* If the giv has the opposite direction of change,
7993 then reverse the comparison. */
7994 if (INTVAL (v->mult_val) < 0)
7995 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7996 const0_rtx, v->new_reg);
8000 /* We can probably test that giv's reduced reg. */
8001 if (validate_change (insn, &SET_SRC (x), new, 0))
8005 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
8006 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
8007 Require a constant for MULT_VAL, so we know it's nonzero.
8008 ??? Do this only if ADD_VAL is a pointer to avoid a potential
8009 overflow problem. */
8011 for (v = bl->giv; v; v = v->next_iv)
8012 if (GET_CODE (v->mult_val) == CONST_INT
8013 && v->mult_val != const0_rtx
8014 && ! v->ignore && ! v->maybe_dead && v->always_computable
8016 && (GET_CODE (v->add_val) == SYMBOL_REF
8017 || GET_CODE (v->add_val) == LABEL_REF
8018 || GET_CODE (v->add_val) == CONST
8019 || (GET_CODE (v->add_val) == REG
8020 && REG_POINTER (v->add_val))))
8022 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8028 /* If the giv has the opposite direction of change,
8029 then reverse the comparison. */
8030 if (INTVAL (v->mult_val) < 0)
8031 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
8034 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
8035 copy_rtx (v->add_val));
8037 /* Replace biv with the giv's reduced register. */
8038 update_reg_last_use (v->add_val, insn);
8039 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8042 /* Insn doesn't support that constant or invariant. Copy it
8043 into a register (it will be a loop invariant.) */
8044 tem = gen_reg_rtx (GET_MODE (v->new_reg));
8046 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
8049 /* Substitute the new register for its invariant value in
8050 the compare expression. */
8051 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
8052 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
8061 case GT: case GE: case GTU: case GEU:
8062 case LT: case LE: case LTU: case LEU:
8063 /* See if either argument is the biv. */
8064 if (XEXP (x, 0) == reg)
8065 arg = XEXP (x, 1), arg_operand = 1;
8066 else if (XEXP (x, 1) == reg)
8067 arg = XEXP (x, 0), arg_operand = 0;
8071 if (CONSTANT_P (arg))
8073 /* First try to replace with any giv that has constant positive
8074 mult_val and constant add_val. We might be able to support
8075 negative mult_val, but it seems complex to do it in general. */
8077 for (v = bl->giv; v; v = v->next_iv)
8078 if (GET_CODE (v->mult_val) == CONST_INT
8079 && INTVAL (v->mult_val) > 0
8080 && (GET_CODE (v->add_val) == SYMBOL_REF
8081 || GET_CODE (v->add_val) == LABEL_REF
8082 || GET_CODE (v->add_val) == CONST
8083 || (GET_CODE (v->add_val) == REG
8084 && REG_POINTER (v->add_val)))
8085 && ! v->ignore && ! v->maybe_dead && v->always_computable
8088 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8094 /* Replace biv with the giv's reduced reg. */
8095 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
8097 /* If all constants are actually constant integers and
8098 the derived constant can be directly placed in the COMPARE,
8100 if (GET_CODE (arg) == CONST_INT
8101 && GET_CODE (v->mult_val) == CONST_INT
8102 && GET_CODE (v->add_val) == CONST_INT)
8104 validate_change (insn, &XEXP (x, arg_operand),
8105 GEN_INT (INTVAL (arg)
8106 * INTVAL (v->mult_val)
8107 + INTVAL (v->add_val)), 1);
8111 /* Otherwise, load it into a register. */
8112 tem = gen_reg_rtx (mode);
8113 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8114 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8116 if (apply_change_group ())
8120 /* Look for giv with positive constant mult_val and nonconst add_val.
8121 Insert insns to calculate new compare value.
8122 ??? Turn this off due to possible overflow. */
8124 for (v = bl->giv; v; v = v->next_iv)
8125 if (GET_CODE (v->mult_val) == CONST_INT
8126 && INTVAL (v->mult_val) > 0
8127 && ! v->ignore && ! v->maybe_dead && v->always_computable
8133 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8139 tem = gen_reg_rtx (mode);
8141 /* Replace biv with giv's reduced register. */
8142 validate_change (insn, &XEXP (x, 1 - arg_operand),
8145 /* Compute value to compare against. */
8146 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
8147 /* Use it in this insn. */
8148 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8149 if (apply_change_group ())
8153 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
8155 if (loop_invariant_p (loop, arg) == 1)
8157 /* Look for giv with constant positive mult_val and nonconst
8158 add_val. Insert insns to compute new compare value.
8159 ??? Turn this off due to possible overflow. */
8161 for (v = bl->giv; v; v = v->next_iv)
8162 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
8163 && ! v->ignore && ! v->maybe_dead && v->always_computable
8169 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8175 tem = gen_reg_rtx (mode);
8177 /* Replace biv with giv's reduced register. */
8178 validate_change (insn, &XEXP (x, 1 - arg_operand),
8181 /* Compute value to compare against. */
8182 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8184 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8185 if (apply_change_group ())
8190 /* This code has problems. Basically, you can't know when
8191 seeing if we will eliminate BL, whether a particular giv
8192 of ARG will be reduced. If it isn't going to be reduced,
8193 we can't eliminate BL. We can try forcing it to be reduced,
8194 but that can generate poor code.
8196 The problem is that the benefit of reducing TV, below should
8197 be increased if BL can actually be eliminated, but this means
8198 we might have to do a topological sort of the order in which
8199 we try to process biv. It doesn't seem worthwhile to do
8200 this sort of thing now. */
8203 /* Otherwise the reg compared with had better be a biv. */
8204 if (GET_CODE (arg) != REG
8205 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8208 /* Look for a pair of givs, one for each biv,
8209 with identical coefficients. */
8210 for (v = bl->giv; v; v = v->next_iv)
8212 struct induction *tv;
8214 if (v->ignore || v->maybe_dead || v->mode != mode)
8217 for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
8219 if (! tv->ignore && ! tv->maybe_dead
8220 && rtx_equal_p (tv->mult_val, v->mult_val)
8221 && rtx_equal_p (tv->add_val, v->add_val)
8222 && tv->mode == mode)
8224 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8230 /* Replace biv with its giv's reduced reg. */
8231 XEXP (x, 1 - arg_operand) = v->new_reg;
8232 /* Replace other operand with the other giv's
8234 XEXP (x, arg_operand) = tv->new_reg;
8241 /* If we get here, the biv can't be eliminated. */
8245 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8246 biv is used in it, since it will be replaced. */
8247 for (v = bl->giv; v; v = v->next_iv)
8248 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8256 /* See if any subexpression fails elimination. */
8257 fmt = GET_RTX_FORMAT (code);
8258 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8263 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8264 eliminate_p, where))
8269 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8270 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8271 eliminate_p, where))
8280 /* Return nonzero if the last use of REG
8281 is in an insn following INSN in the same basic block. */
8284 last_use_this_basic_block (reg, insn)
8290 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8293 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8299 /* Called via `note_stores' to record the initial value of a biv. Here we
8300 just record the location of the set and process it later. */
8303 record_initial (dest, set, data)
8306 void *data ATTRIBUTE_UNUSED;
8308 struct loop_ivs *ivs = (struct loop_ivs *) data;
8309 struct iv_class *bl;
8311 if (GET_CODE (dest) != REG
8312 || REGNO (dest) >= max_reg_before_loop
8313 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8316 bl = REG_IV_CLASS (ivs, REGNO (dest));
8318 /* If this is the first set found, record it. */
8319 if (bl->init_insn == 0)
8321 bl->init_insn = note_insn;
8326 /* If any of the registers in X are "old" and currently have a last use earlier
8327 than INSN, update them to have a last use of INSN. Their actual last use
8328 will be the previous insn but it will not have a valid uid_luid so we can't
8332 update_reg_last_use (x, insn)
8336 /* Check for the case where INSN does not have a valid luid. In this case,
8337 there is no need to modify the regno_last_uid, as this can only happen
8338 when code is inserted after the loop_end to set a pseudo's final value,
8339 and hence this insn will never be the last use of x. */
8340 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8341 && INSN_UID (insn) < max_uid_for_loop
8342 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8343 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8347 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8348 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8351 update_reg_last_use (XEXP (x, i), insn);
8352 else if (fmt[i] == 'E')
8353 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8354 update_reg_last_use (XVECEXP (x, i, j), insn);
8359 /* Given an insn INSN and condition COND, return the condition in a
8360 canonical form to simplify testing by callers. Specifically:
8362 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8363 (2) Both operands will be machine operands; (cc0) will have been replaced.
8364 (3) If an operand is a constant, it will be the second operand.
8365 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8366 for GE, GEU, and LEU.
8368 If the condition cannot be understood, or is an inequality floating-point
8369 comparison which needs to be reversed, 0 will be returned.
8371 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8373 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8374 insn used in locating the condition was found. If a replacement test
8375 of the condition is desired, it should be placed in front of that
8376 insn and we will be sure that the inputs are still valid.
8378 If WANT_REG is non-zero, we wish the condition to be relative to that
8379 register, if possible. Therefore, do not canonicalize the condition
8383 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8395 int reverse_code = 0;
8396 int did_reverse_condition = 0;
8397 enum machine_mode mode;
8399 code = GET_CODE (cond);
8400 mode = GET_MODE (cond);
8401 op0 = XEXP (cond, 0);
8402 op1 = XEXP (cond, 1);
8406 code = reverse_condition (code);
8407 did_reverse_condition ^= 1;
8413 /* If we are comparing a register with zero, see if the register is set
8414 in the previous insn to a COMPARE or a comparison operation. Perform
8415 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8418 while (GET_RTX_CLASS (code) == '<'
8419 && op1 == CONST0_RTX (GET_MODE (op0))
8422 /* Set non-zero when we find something of interest. */
8426 /* If comparison with cc0, import actual comparison from compare
8430 if ((prev = prev_nonnote_insn (prev)) == 0
8431 || GET_CODE (prev) != INSN
8432 || (set = single_set (prev)) == 0
8433 || SET_DEST (set) != cc0_rtx)
8436 op0 = SET_SRC (set);
8437 op1 = CONST0_RTX (GET_MODE (op0));
8443 /* If this is a COMPARE, pick up the two things being compared. */
8444 if (GET_CODE (op0) == COMPARE)
8446 op1 = XEXP (op0, 1);
8447 op0 = XEXP (op0, 0);
8450 else if (GET_CODE (op0) != REG)
8453 /* Go back to the previous insn. Stop if it is not an INSN. We also
8454 stop if it isn't a single set or if it has a REG_INC note because
8455 we don't want to bother dealing with it. */
8457 if ((prev = prev_nonnote_insn (prev)) == 0
8458 || GET_CODE (prev) != INSN
8459 || FIND_REG_INC_NOTE (prev, 0)
8460 || (set = single_set (prev)) == 0)
8463 /* If this is setting OP0, get what it sets it to if it looks
8465 if (rtx_equal_p (SET_DEST (set), op0))
8467 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8469 /* ??? We may not combine comparisons done in a CCmode with
8470 comparisons not done in a CCmode. This is to aid targets
8471 like Alpha that have an IEEE compliant EQ instruction, and
8472 a non-IEEE compliant BEQ instruction. The use of CCmode is
8473 actually artificial, simply to prevent the combination, but
8474 should not affect other platforms.
8476 However, we must allow VOIDmode comparisons to match either
8477 CCmode or non-CCmode comparison, because some ports have
8478 modeless comparisons inside branch patterns.
8480 ??? This mode check should perhaps look more like the mode check
8481 in simplify_comparison in combine. */
8483 if ((GET_CODE (SET_SRC (set)) == COMPARE
8486 && GET_MODE_CLASS (inner_mode) == MODE_INT
8487 && (GET_MODE_BITSIZE (inner_mode)
8488 <= HOST_BITS_PER_WIDE_INT)
8489 && (STORE_FLAG_VALUE
8490 & ((HOST_WIDE_INT) 1
8491 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8492 #ifdef FLOAT_STORE_FLAG_VALUE
8494 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8495 && (REAL_VALUE_NEGATIVE
8496 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8499 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8500 && (((GET_MODE_CLASS (mode) == MODE_CC)
8501 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8502 || mode == VOIDmode || inner_mode == VOIDmode))
8504 else if (((code == EQ
8506 && (GET_MODE_BITSIZE (inner_mode)
8507 <= HOST_BITS_PER_WIDE_INT)
8508 && GET_MODE_CLASS (inner_mode) == MODE_INT
8509 && (STORE_FLAG_VALUE
8510 & ((HOST_WIDE_INT) 1
8511 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8512 #ifdef FLOAT_STORE_FLAG_VALUE
8514 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8515 && (REAL_VALUE_NEGATIVE
8516 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8519 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8520 && (((GET_MODE_CLASS (mode) == MODE_CC)
8521 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8522 || mode == VOIDmode || inner_mode == VOIDmode))
8525 /* We might have reversed a LT to get a GE here. But this wasn't
8526 actually the comparison of data, so we don't flag that we
8527 have had to reverse the condition. */
8528 did_reverse_condition ^= 1;
8536 else if (reg_set_p (op0, prev))
8537 /* If this sets OP0, but not directly, we have to give up. */
8542 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8543 code = GET_CODE (x);
8546 code = reverse_condition (code);
8547 if (code == UNKNOWN)
8549 did_reverse_condition ^= 1;
8553 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8559 /* If constant is first, put it last. */
8560 if (CONSTANT_P (op0))
8561 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8563 /* If OP0 is the result of a comparison, we weren't able to find what
8564 was really being compared, so fail. */
8565 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8568 /* Canonicalize any ordered comparison with integers involving equality
8569 if we can do computations in the relevant mode and we do not
8572 if (GET_CODE (op1) == CONST_INT
8573 && GET_MODE (op0) != VOIDmode
8574 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8576 HOST_WIDE_INT const_val = INTVAL (op1);
8577 unsigned HOST_WIDE_INT uconst_val = const_val;
8578 unsigned HOST_WIDE_INT max_val
8579 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8584 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8585 code = LT, op1 = GEN_INT (const_val + 1);
8588 /* When cross-compiling, const_val might be sign-extended from
8589 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8591 if ((HOST_WIDE_INT) (const_val & max_val)
8592 != (((HOST_WIDE_INT) 1
8593 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8594 code = GT, op1 = GEN_INT (const_val - 1);
8598 if (uconst_val < max_val)
8599 code = LTU, op1 = GEN_INT (uconst_val + 1);
8603 if (uconst_val != 0)
8604 code = GTU, op1 = GEN_INT (uconst_val - 1);
8612 /* If this was floating-point and we reversed anything other than an
8613 EQ or NE or (UN)ORDERED, return zero. */
8614 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8615 && did_reverse_condition
8616 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8618 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8622 /* Never return CC0; return zero instead. */
8627 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8630 /* Given a jump insn JUMP, return the condition that will cause it to branch
8631 to its JUMP_LABEL. If the condition cannot be understood, or is an
8632 inequality floating-point comparison which needs to be reversed, 0 will
8635 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8636 insn used in locating the condition was found. If a replacement test
8637 of the condition is desired, it should be placed in front of that
8638 insn and we will be sure that the inputs are still valid. */
8641 get_condition (jump, earliest)
8649 /* If this is not a standard conditional jump, we can't parse it. */
8650 if (GET_CODE (jump) != JUMP_INSN
8651 || ! any_condjump_p (jump))
8653 set = pc_set (jump);
8655 cond = XEXP (SET_SRC (set), 0);
8657 /* If this branches to JUMP_LABEL when the condition is false, reverse
8660 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8661 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8663 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8666 /* Similar to above routine, except that we also put an invariant last
8667 unless both operands are invariants. */
8670 get_condition_for_loop (loop, x)
8671 const struct loop *loop;
8674 rtx comparison = get_condition (x, NULL_PTR);
8677 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8678 || loop_invariant_p (loop, XEXP (comparison, 1)))
8681 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8682 XEXP (comparison, 1), XEXP (comparison, 0));
8685 /* Scan the function and determine whether it has indirect (computed) jumps.
8687 This is taken mostly from flow.c; similar code exists elsewhere
8688 in the compiler. It may be useful to put this into rtlanal.c. */
8690 indirect_jump_in_function_p (start)
8695 for (insn = start; insn; insn = NEXT_INSN (insn))
8696 if (computed_jump_p (insn))
8702 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8703 documentation for LOOP_MEMS for the definition of `appropriate'.
8704 This function is called from prescan_loop via for_each_rtx. */
8707 insert_loop_mem (mem, data)
8709 void *data ATTRIBUTE_UNUSED;
8711 struct loop_info *loop_info = data;
8718 switch (GET_CODE (m))
8724 /* We're not interested in MEMs that are only clobbered. */
8728 /* We're not interested in the MEM associated with a
8729 CONST_DOUBLE, so there's no need to traverse into this. */
8733 /* We're not interested in any MEMs that only appear in notes. */
8737 /* This is not a MEM. */
8741 /* See if we've already seen this MEM. */
8742 for (i = 0; i < loop_info->mems_idx; ++i)
8743 if (rtx_equal_p (m, loop_info->mems[i].mem))
8745 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8746 /* The modes of the two memory accesses are different. If
8747 this happens, something tricky is going on, and we just
8748 don't optimize accesses to this MEM. */
8749 loop_info->mems[i].optimize = 0;
8754 /* Resize the array, if necessary. */
8755 if (loop_info->mems_idx == loop_info->mems_allocated)
8757 if (loop_info->mems_allocated != 0)
8758 loop_info->mems_allocated *= 2;
8760 loop_info->mems_allocated = 32;
8762 loop_info->mems = (loop_mem_info *)
8763 xrealloc (loop_info->mems,
8764 loop_info->mems_allocated * sizeof (loop_mem_info));
8767 /* Actually insert the MEM. */
8768 loop_info->mems[loop_info->mems_idx].mem = m;
8769 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8770 because we can't put it in a register. We still store it in the
8771 table, though, so that if we see the same address later, but in a
8772 non-BLK mode, we'll not think we can optimize it at that point. */
8773 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8774 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8775 ++loop_info->mems_idx;
8780 /* Like load_mems, but also ensures that REGS->SET_IN_LOOP,
8781 REGS->MAY_NOT_OPTIMIZE, REGS->SINGLE_USAGE, and INSN_COUNT have the correct
8782 values after load_mems. */
8785 load_mems_and_recount_loop_regs_set (loop, insn_count)
8786 const struct loop *loop;
8789 struct loop_regs *regs = LOOP_REGS (loop);
8790 int nregs = max_reg_num ();
8794 /* Recalculate regs->set_in_loop and friends since load_mems may have
8795 created new registers. */
8796 if (max_reg_num () > nregs)
8802 nregs = max_reg_num ();
8804 if ((unsigned) nregs > regs->set_in_loop->num_elements)
8806 /* Grow all the arrays. */
8807 VARRAY_GROW (regs->set_in_loop, nregs);
8808 VARRAY_GROW (regs->n_times_set, nregs);
8809 VARRAY_GROW (regs->may_not_optimize, nregs);
8810 VARRAY_GROW (regs->single_usage, nregs);
8812 /* Clear the arrays */
8813 memset ((char *) ®s->set_in_loop->data, 0, nregs * sizeof (int));
8814 memset ((char *) ®s->may_not_optimize->data, 0, nregs * sizeof (char));
8815 memset ((char *) ®s->single_usage->data, 0, nregs * sizeof (rtx));
8817 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
8820 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8822 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8823 VARRAY_INT (regs->set_in_loop, i) = 1;
8826 #ifdef AVOID_CCMODE_COPIES
8827 /* Don't try to move insns which set CC registers if we should not
8828 create CCmode register copies. */
8829 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8830 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8831 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8834 /* Set regs->n_times_set for the new registers. */
8835 bcopy ((char *) (®s->set_in_loop->data.i[0] + old_nregs),
8836 (char *) (®s->n_times_set->data.i[0] + old_nregs),
8837 (nregs - old_nregs) * sizeof (int));
8841 /* Move MEMs into registers for the duration of the loop. */
8845 const struct loop *loop;
8847 struct loop_info *loop_info = LOOP_INFO (loop);
8848 struct loop_regs *regs = LOOP_REGS (loop);
8849 int maybe_never = 0;
8852 rtx label = NULL_RTX;
8854 /* Nonzero if the next instruction may never be executed. */
8855 int next_maybe_never = 0;
8856 int last_max_reg = max_reg_num ();
8858 if (loop_info->mems_idx == 0)
8861 /* We cannot use next_label here because it skips over normal insns. */
8862 end_label = next_nonnote_insn (loop->end);
8863 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8864 end_label = NULL_RTX;
8866 /* Check to see if it's possible that some instructions in the loop are
8867 never executed. Also check if there is a goto out of the loop other
8868 than right after the end of the loop. */
8869 for (p = next_insn_in_loop (loop, loop->scan_start);
8870 p != NULL_RTX && ! maybe_never;
8871 p = next_insn_in_loop (loop, p))
8873 if (GET_CODE (p) == CODE_LABEL)
8875 else if (GET_CODE (p) == JUMP_INSN
8876 /* If we enter the loop in the middle, and scan
8877 around to the beginning, don't set maybe_never
8878 for that. This must be an unconditional jump,
8879 otherwise the code at the top of the loop might
8880 never be executed. Unconditional jumps are
8881 followed a by barrier then loop end. */
8882 && ! (GET_CODE (p) == JUMP_INSN
8883 && JUMP_LABEL (p) == loop->top
8884 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8885 && any_uncondjump_p (p)))
8887 /* If this is a jump outside of the loop but not right
8888 after the end of the loop, we would have to emit new fixup
8889 sequences for each such label. */
8890 if (JUMP_LABEL (p) != end_label
8891 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8892 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8893 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8896 if (!any_condjump_p (p))
8897 /* Something complicated. */
8900 /* If there are any more instructions in the loop, they
8901 might not be reached. */
8902 next_maybe_never = 1;
8904 else if (next_maybe_never)
8908 /* Find start of the extended basic block that enters the loop. */
8909 for (p = loop->start;
8910 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8916 /* Build table of mems that get set to constant values before the
8918 for (; p != loop->start; p = NEXT_INSN (p))
8919 cselib_process_insn (p);
8921 /* Actually move the MEMs. */
8922 for (i = 0; i < loop_info->mems_idx; ++i)
8924 regset_head load_copies;
8925 regset_head store_copies;
8928 rtx mem = loop_info->mems[i].mem;
8931 if (MEM_VOLATILE_P (mem)
8932 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8933 /* There's no telling whether or not MEM is modified. */
8934 loop_info->mems[i].optimize = 0;
8936 /* Go through the MEMs written to in the loop to see if this
8937 one is aliased by one of them. */
8938 mem_list_entry = loop_info->store_mems;
8939 while (mem_list_entry)
8941 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8943 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8946 /* MEM is indeed aliased by this store. */
8947 loop_info->mems[i].optimize = 0;
8950 mem_list_entry = XEXP (mem_list_entry, 1);
8953 if (flag_float_store && written
8954 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8955 loop_info->mems[i].optimize = 0;
8957 /* If this MEM is written to, we must be sure that there
8958 are no reads from another MEM that aliases this one. */
8959 if (loop_info->mems[i].optimize && written)
8963 for (j = 0; j < loop_info->mems_idx; ++j)
8967 else if (true_dependence (mem,
8969 loop_info->mems[j].mem,
8972 /* It's not safe to hoist loop_info->mems[i] out of
8973 the loop because writes to it might not be
8974 seen by reads from loop_info->mems[j]. */
8975 loop_info->mems[i].optimize = 0;
8981 if (maybe_never && may_trap_p (mem))
8982 /* We can't access the MEM outside the loop; it might
8983 cause a trap that wouldn't have happened otherwise. */
8984 loop_info->mems[i].optimize = 0;
8986 if (!loop_info->mems[i].optimize)
8987 /* We thought we were going to lift this MEM out of the
8988 loop, but later discovered that we could not. */
8991 INIT_REG_SET (&load_copies);
8992 INIT_REG_SET (&store_copies);
8994 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8995 order to keep scan_loop from moving stores to this MEM
8996 out of the loop just because this REG is neither a
8997 user-variable nor used in the loop test. */
8998 reg = gen_reg_rtx (GET_MODE (mem));
8999 REG_USERVAR_P (reg) = 1;
9000 loop_info->mems[i].reg = reg;
9002 /* Now, replace all references to the MEM with the
9003 corresponding pesudos. */
9005 for (p = next_insn_in_loop (loop, loop->scan_start);
9007 p = next_insn_in_loop (loop, p))
9013 set = single_set (p);
9015 /* See if this copies the mem into a register that isn't
9016 modified afterwards. We'll try to do copy propagation
9017 a little further on. */
9019 /* @@@ This test is _way_ too conservative. */
9021 && GET_CODE (SET_DEST (set)) == REG
9022 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
9023 && REGNO (SET_DEST (set)) < last_max_reg
9024 && VARRAY_INT (regs->n_times_set,
9025 REGNO (SET_DEST (set))) == 1
9026 && rtx_equal_p (SET_SRC (set), mem))
9027 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
9029 /* See if this copies the mem from a register that isn't
9030 modified afterwards. We'll try to remove the
9031 redundant copy later on by doing a little register
9032 renaming and copy propagation. This will help
9033 to untangle things for the BIV detection code. */
9036 && GET_CODE (SET_SRC (set)) == REG
9037 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
9038 && REGNO (SET_SRC (set)) < last_max_reg
9039 && VARRAY_INT (regs->n_times_set, REGNO (SET_SRC (set))) == 1
9040 && rtx_equal_p (SET_DEST (set), mem))
9041 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
9043 /* Replace the memory reference with the shadow register. */
9044 replace_loop_mems (p, loop_info->mems[i].mem,
9045 loop_info->mems[i].reg);
9048 if (GET_CODE (p) == CODE_LABEL
9049 || GET_CODE (p) == JUMP_INSN)
9053 if (! apply_change_group ())
9054 /* We couldn't replace all occurrences of the MEM. */
9055 loop_info->mems[i].optimize = 0;
9058 /* Load the memory immediately before LOOP->START, which is
9059 the NOTE_LOOP_BEG. */
9060 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
9064 struct elt_loc_list *const_equiv = 0;
9068 struct elt_loc_list *equiv;
9069 struct elt_loc_list *best_equiv = 0;
9070 for (equiv = e->locs; equiv; equiv = equiv->next)
9072 if (CONSTANT_P (equiv->loc))
9073 const_equiv = equiv;
9074 else if (GET_CODE (equiv->loc) == REG
9075 /* Extending hard register lifetimes cuases crash
9076 on SRC targets. Doing so on non-SRC is
9077 probably also not good idea, since we most
9078 probably have pseudoregister equivalence as
9080 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
9083 /* Use the constant equivalence if that is cheap enough. */
9085 best_equiv = const_equiv;
9086 else if (const_equiv
9087 && (rtx_cost (const_equiv->loc, SET)
9088 <= rtx_cost (best_equiv->loc, SET)))
9090 best_equiv = const_equiv;
9094 /* If best_equiv is nonzero, we know that MEM is set to a
9095 constant or register before the loop. We will use this
9096 knowledge to initialize the shadow register with that
9097 constant or reg rather than by loading from MEM. */
9099 best = copy_rtx (best_equiv->loc);
9101 set = gen_move_insn (reg, best);
9102 set = emit_insn_before (set, loop->start);
9104 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
9105 copy_rtx (const_equiv->loc),
9110 if (label == NULL_RTX)
9112 label = gen_label_rtx ();
9113 emit_label_after (label, loop->end);
9116 /* Store the memory immediately after END, which is
9117 the NOTE_LOOP_END. */
9118 set = gen_move_insn (copy_rtx (mem), reg);
9119 emit_insn_after (set, label);
9122 if (loop_dump_stream)
9124 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9125 REGNO (reg), (written ? "r/w" : "r/o"));
9126 print_rtl (loop_dump_stream, mem);
9127 fputc ('\n', loop_dump_stream);
9130 /* Attempt a bit of copy propagation. This helps untangle the
9131 data flow, and enables {basic,general}_induction_var to find
9133 EXECUTE_IF_SET_IN_REG_SET
9134 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9136 try_copy_prop (loop, reg, j);
9138 CLEAR_REG_SET (&load_copies);
9140 EXECUTE_IF_SET_IN_REG_SET
9141 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9143 try_swap_copy_prop (loop, reg, j);
9145 CLEAR_REG_SET (&store_copies);
9149 if (label != NULL_RTX && end_label != NULL_RTX)
9151 /* Now, we need to replace all references to the previous exit
9152 label with the new one. */
9157 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9159 for_each_rtx (&p, replace_label, &rr);
9161 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9162 field. This is not handled by for_each_rtx because it doesn't
9163 handle unprinted ('0') fields. We need to update JUMP_LABEL
9164 because the immediately following unroll pass will use it.
9165 replace_label would not work anyways, because that only handles
9167 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9168 JUMP_LABEL (p) = label;
9175 /* For communication between note_reg_stored and its caller. */
9176 struct note_reg_stored_arg
9182 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9185 note_reg_stored (x, setter, arg)
9186 rtx x, setter ATTRIBUTE_UNUSED;
9189 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9194 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9195 There must be exactly one insn that sets this pseudo; it will be
9196 deleted if all replacements succeed and we can prove that the register
9197 is not used after the loop. */
9200 try_copy_prop (loop, replacement, regno)
9201 const struct loop *loop;
9205 /* This is the reg that we are copying from. */
9206 rtx reg_rtx = regno_reg_rtx[regno];
9209 /* These help keep track of whether we replaced all uses of the reg. */
9210 int replaced_last = 0;
9211 int store_is_first = 0;
9213 for (insn = next_insn_in_loop (loop, loop->scan_start);
9215 insn = next_insn_in_loop (loop, insn))
9219 /* Only substitute within one extended basic block from the initializing
9221 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9224 if (! INSN_P (insn))
9227 /* Is this the initializing insn? */
9228 set = single_set (insn);
9230 && GET_CODE (SET_DEST (set)) == REG
9231 && REGNO (SET_DEST (set)) == regno)
9237 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9241 /* Only substitute after seeing the initializing insn. */
9242 if (init_insn && insn != init_insn)
9244 struct note_reg_stored_arg arg;
9246 replace_loop_regs (insn, reg_rtx, replacement);
9247 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9250 /* Stop replacing when REPLACEMENT is modified. */
9251 arg.reg = replacement;
9253 note_stores (PATTERN (insn), note_reg_stored, &arg);
9260 if (apply_change_group ())
9262 if (loop_dump_stream)
9263 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9264 if (store_is_first && replaced_last)
9266 PUT_CODE (init_insn, NOTE);
9267 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9268 if (loop_dump_stream)
9269 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9270 INSN_UID (init_insn));
9272 if (loop_dump_stream)
9273 fprintf (loop_dump_stream, ".\n");
9277 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9278 loop LOOP if the order of the sets of these registers can be
9279 swapped. There must be exactly one insn within the loop that sets
9280 this pseudo followed immediately by a move insn that sets
9281 REPLACEMENT with REGNO. */
9283 try_swap_copy_prop (loop, replacement, regno)
9284 const struct loop *loop;
9290 unsigned int new_regno;
9292 new_regno = REGNO (replacement);
9294 for (insn = next_insn_in_loop (loop, loop->scan_start);
9296 insn = next_insn_in_loop (loop, insn))
9298 /* Search for the insn that copies REGNO to NEW_REGNO? */
9299 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9300 && (set = single_set (insn))
9301 && GET_CODE (SET_DEST (set)) == REG
9302 && REGNO (SET_DEST (set)) == new_regno
9303 && GET_CODE (SET_SRC (set)) == REG
9304 && REGNO (SET_SRC (set)) == regno)
9308 if (insn != NULL_RTX)
9313 /* Some DEF-USE info would come in handy here to make this
9314 function more general. For now, just check the previous insn
9315 which is the most likely candidate for setting REGNO. */
9317 prev_insn = PREV_INSN (insn);
9319 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9320 && (prev_set = single_set (prev_insn))
9321 && GET_CODE (SET_DEST (prev_set)) == REG
9322 && REGNO (SET_DEST (prev_set)) == regno)
9325 (set (reg regno) (expr))
9326 (set (reg new_regno) (reg regno))
9328 so try converting this to:
9329 (set (reg new_regno) (expr))
9330 (set (reg regno) (reg new_regno))
9332 The former construct is often generated when a global
9333 variable used for an induction variable is shadowed by a
9334 register (NEW_REGNO). The latter construct improves the
9335 chances of GIV replacement and BIV elimination. */
9337 validate_change (prev_insn, &SET_DEST (prev_set),
9339 validate_change (insn, &SET_DEST (set),
9341 validate_change (insn, &SET_SRC (set),
9344 if (apply_change_group ())
9346 if (loop_dump_stream)
9347 fprintf (loop_dump_stream,
9348 " Swapped set of reg %d at %d with reg %d at %d.\n",
9349 regno, INSN_UID (insn),
9350 new_regno, INSN_UID (prev_insn));
9352 /* Update first use of REGNO. */
9353 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9354 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9356 /* Now perform copy propagation to hopefully
9357 remove all uses of REGNO within the loop. */
9358 try_copy_prop (loop, replacement, regno);
9364 /* Replace MEM with its associated pseudo register. This function is
9365 called from load_mems via for_each_rtx. DATA is actually a pointer
9366 to a structure describing the instruction currently being scanned
9367 and the MEM we are currently replacing. */
9370 replace_loop_mem (mem, data)
9374 loop_replace_args *args = (loop_replace_args *) data;
9380 switch (GET_CODE (m))
9386 /* We're not interested in the MEM associated with a
9387 CONST_DOUBLE, so there's no need to traverse into one. */
9391 /* This is not a MEM. */
9395 if (!rtx_equal_p (args->match, m))
9396 /* This is not the MEM we are currently replacing. */
9399 /* Actually replace the MEM. */
9400 validate_change (args->insn, mem, args->replacement, 1);
9406 replace_loop_mems (insn, mem, reg)
9411 loop_replace_args args;
9415 args.replacement = reg;
9417 for_each_rtx (&insn, replace_loop_mem, &args);
9420 /* Replace one register with another. Called through for_each_rtx; PX points
9421 to the rtx being scanned. DATA is actually a pointer to
9422 a structure of arguments. */
9425 replace_loop_reg (px, data)
9430 loop_replace_args *args = (loop_replace_args *) data;
9435 if (x == args->match)
9436 validate_change (args->insn, px, args->replacement, 1);
9442 replace_loop_regs (insn, reg, replacement)
9447 loop_replace_args args;
9451 args.replacement = replacement;
9453 for_each_rtx (&insn, replace_loop_reg, &args);
9456 /* Replace occurrences of the old exit label for the loop with the new
9457 one. DATA is an rtx_pair containing the old and new labels,
9461 replace_label (x, data)
9466 rtx old_label = ((rtx_pair *) data)->r1;
9467 rtx new_label = ((rtx_pair *) data)->r2;
9472 if (GET_CODE (l) != LABEL_REF)
9475 if (XEXP (l, 0) != old_label)
9478 XEXP (l, 0) = new_label;
9479 ++LABEL_NUSES (new_label);
9480 --LABEL_NUSES (old_label);
9485 #define LOOP_BLOCK_NUM_1(INSN) \
9486 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9488 /* The notes do not have an assigned block, so look at the next insn. */
9489 #define LOOP_BLOCK_NUM(INSN) \
9490 ((INSN) ? (GET_CODE (INSN) == NOTE \
9491 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9492 : LOOP_BLOCK_NUM_1 (INSN)) \
9495 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9498 loop_dump_aux (loop, file, verbose)
9499 const struct loop *loop;
9501 int verbose ATTRIBUTE_UNUSED;
9505 if (! loop || ! file)
9508 /* Print diagnostics to compare our concept of a loop with
9509 what the loop notes say. */
9510 if (! PREV_INSN (loop->first->head)
9511 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9512 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9513 != NOTE_INSN_LOOP_BEG)
9514 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9515 INSN_UID (PREV_INSN (loop->first->head)));
9516 if (! NEXT_INSN (loop->last->end)
9517 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9518 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9519 != NOTE_INSN_LOOP_END)
9520 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9521 INSN_UID (NEXT_INSN (loop->last->end)));
9526 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9527 LOOP_BLOCK_NUM (loop->start),
9528 LOOP_INSN_UID (loop->start),
9529 LOOP_BLOCK_NUM (loop->cont),
9530 LOOP_INSN_UID (loop->cont),
9531 LOOP_BLOCK_NUM (loop->cont),
9532 LOOP_INSN_UID (loop->cont),
9533 LOOP_BLOCK_NUM (loop->vtop),
9534 LOOP_INSN_UID (loop->vtop),
9535 LOOP_BLOCK_NUM (loop->end),
9536 LOOP_INSN_UID (loop->end));
9537 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9538 LOOP_BLOCK_NUM (loop->top),
9539 LOOP_INSN_UID (loop->top),
9540 LOOP_BLOCK_NUM (loop->scan_start),
9541 LOOP_INSN_UID (loop->scan_start));
9542 fprintf (file, ";; exit_count %d", loop->exit_count);
9543 if (loop->exit_count)
9545 fputs (", labels:", file);
9546 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9548 fprintf (file, " %d ",
9549 LOOP_INSN_UID (XEXP (label, 0)));
9554 /* This can happen when a marked loop appears as two nested loops,
9555 say from while (a || b) {}. The inner loop won't match
9556 the loop markers but the outer one will. */
9557 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9558 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9562 /* Call this function from the debugger to dump LOOP. */
9566 const struct loop *loop;
9568 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9571 /* Call this function from the debugger to dump LOOPS. */
9575 const struct loops *loops;
9577 flow_loops_dump (loops, stderr, loop_dump_aux, 1);
OSDN Git Service
