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, 2001 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, rtx *));
156 static void note_addr_stored PARAMS ((rtx, rtx, void *));
157 static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
158 static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
159 static void scan_loop PARAMS ((struct loop*, int));
161 static void replace_call_address PARAMS ((rtx, rtx, rtx));
163 static rtx skip_consec_insns PARAMS ((rtx, int));
164 static int libcall_benefit PARAMS ((rtx));
165 static void ignore_some_movables PARAMS ((struct loop_movables *));
166 static void force_movables PARAMS ((struct loop_movables *));
167 static void combine_movables PARAMS ((struct loop_movables *,
168 struct loop_regs *));
169 static int regs_match_p PARAMS ((rtx, rtx, struct loop_movables *));
170 static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct loop_movables *,
171 struct loop_regs *));
172 static void add_label_notes PARAMS ((rtx, rtx));
173 static void move_movables PARAMS ((struct loop *loop, struct loop_movables *,
175 static void loop_movables_add PARAMS((struct loop_movables *,
177 static void loop_movables_free PARAMS((struct loop_movables *));
178 static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
179 static void loop_bivs_find PARAMS((struct loop *));
180 static void loop_bivs_init_find PARAMS((struct loop *));
181 static void loop_bivs_check PARAMS((struct loop *));
182 static void loop_givs_find PARAMS((struct loop *));
183 static void loop_givs_check PARAMS((struct loop *));
184 static int loop_biv_eliminable_p PARAMS((struct loop *, struct iv_class *,
186 static int loop_giv_reduce_benefit PARAMS((struct loop *, struct iv_class *,
187 struct induction *, rtx));
188 static void loop_givs_dead_check PARAMS((struct loop *, struct iv_class *));
189 static void loop_givs_reduce PARAMS((struct loop *, struct iv_class *));
190 static void loop_givs_rescan PARAMS((struct loop *, struct iv_class *,
192 static void loop_ivs_free PARAMS((struct loop *));
193 static void strength_reduce PARAMS ((struct loop *, int, int));
194 static void find_single_use_in_loop PARAMS ((struct loop_regs *, rtx, rtx));
195 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
196 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
197 static void record_biv PARAMS ((struct loop *, struct induction *,
198 rtx, rtx, rtx, rtx, rtx *,
200 static void check_final_value PARAMS ((const struct loop *,
201 struct induction *));
202 static void loop_biv_dump PARAMS((const struct induction *, FILE *, int));
203 static void loop_giv_dump PARAMS((const struct induction *, FILE *, int));
204 static void record_giv PARAMS ((const struct loop *, struct induction *,
205 rtx, rtx, rtx, rtx, rtx, rtx, int,
206 enum g_types, int, int, rtx *));
207 static void update_giv_derive PARAMS ((const struct loop *, rtx));
208 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
209 struct loop_info *));
210 static int basic_induction_var PARAMS ((const struct loop *, rtx,
211 enum machine_mode, rtx, rtx,
212 rtx *, rtx *, rtx **));
213 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
214 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
215 rtx *, rtx *, rtx *, int, int *,
217 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
218 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
219 static int check_dbra_loop PARAMS ((struct loop *, int));
220 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
221 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
222 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
223 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
224 static int product_cheap_p PARAMS ((rtx, rtx));
225 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
227 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
228 struct iv_class *, int, rtx));
229 static int last_use_this_basic_block PARAMS ((rtx, rtx));
230 static void record_initial PARAMS ((rtx, rtx, void *));
231 static void update_reg_last_use PARAMS ((rtx, rtx));
232 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
233 static void loop_regs_scan PARAMS ((const struct loop*, int, int *));
234 static void load_mems PARAMS ((const struct loop *));
235 static int insert_loop_mem PARAMS ((rtx *, void *));
236 static int replace_loop_mem PARAMS ((rtx *, void *));
237 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
238 static int replace_loop_reg PARAMS ((rtx *, void *));
239 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
240 static void note_reg_stored PARAMS ((rtx, rtx, void *));
241 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
242 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
244 static int replace_label PARAMS ((rtx *, void *));
245 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
246 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
247 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
249 static rtx loop_insn_emit_before PARAMS((const struct loop *, basic_block,
252 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
253 void debug_biv PARAMS ((const struct induction *));
254 void debug_giv PARAMS ((const struct induction *));
255 void debug_loop PARAMS ((const struct loop *));
256 void debug_loops PARAMS ((const struct loops *));
258 typedef struct rtx_pair
264 typedef struct loop_replace_args
271 /* Nonzero iff INSN is between START and END, inclusive. */
272 #define INSN_IN_RANGE_P(INSN, START, END) \
273 (INSN_UID (INSN) < max_uid_for_loop \
274 && INSN_LUID (INSN) >= INSN_LUID (START) \
275 && INSN_LUID (INSN) <= INSN_LUID (END))
277 /* Indirect_jump_in_function is computed once per function. */
278 static int indirect_jump_in_function;
279 static int indirect_jump_in_function_p PARAMS ((rtx));
281 static int compute_luids PARAMS ((rtx, rtx, int));
283 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
287 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
288 copy the value of the strength reduced giv to its original register. */
289 static int copy_cost;
291 /* Cost of using a register, to normalize the benefits of a giv. */
292 static int reg_address_cost;
297 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
299 reg_address_cost = address_cost (reg, SImode);
301 copy_cost = COSTS_N_INSNS (1);
304 /* Compute the mapping from uids to luids.
305 LUIDs are numbers assigned to insns, like uids,
306 except that luids increase monotonically through the code.
307 Start at insn START and stop just before END. Assign LUIDs
308 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
310 compute_luids (start, end, prev_luid)
317 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
319 if (INSN_UID (insn) >= max_uid_for_loop)
321 /* Don't assign luids to line-number NOTEs, so that the distance in
322 luids between two insns is not affected by -g. */
323 if (GET_CODE (insn) != NOTE
324 || NOTE_LINE_NUMBER (insn) <= 0)
325 uid_luid[INSN_UID (insn)] = ++i;
327 /* Give a line number note the same luid as preceding insn. */
328 uid_luid[INSN_UID (insn)] = i;
333 /* Entry point of this file. Perform loop optimization
334 on the current function. F is the first insn of the function
335 and DUMPFILE is a stream for output of a trace of actions taken
336 (or 0 if none should be output). */
339 loop_optimize (f, dumpfile, flags)
340 /* f is the first instruction of a chain of insns for one function */
347 struct loops loops_data;
348 struct loops *loops = &loops_data;
349 struct loop_info *loops_info;
351 loop_dump_stream = dumpfile;
353 init_recog_no_volatile ();
355 max_reg_before_loop = max_reg_num ();
356 loop_max_reg = max_reg_before_loop;
360 /* Count the number of loops. */
363 for (insn = f; insn; insn = NEXT_INSN (insn))
365 if (GET_CODE (insn) == NOTE
366 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
370 /* Don't waste time if no loops. */
371 if (max_loop_num == 0)
374 loops->num = max_loop_num;
376 /* Get size to use for tables indexed by uids.
377 Leave some space for labels allocated by find_and_verify_loops. */
378 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
380 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
381 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
382 sizeof (struct loop *));
384 /* Allocate storage for array of loops. */
385 loops->array = (struct loop *)
386 xcalloc (loops->num, sizeof (struct loop));
388 /* Find and process each loop.
389 First, find them, and record them in order of their beginnings. */
390 find_and_verify_loops (f, loops);
392 /* Allocate and initialize auxiliary loop information. */
393 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
394 for (i = 0; i < loops->num; i++)
395 loops->array[i].aux = loops_info + i;
397 /* Now find all register lifetimes. This must be done after
398 find_and_verify_loops, because it might reorder the insns in the
400 reg_scan (f, max_reg_before_loop, 1);
402 /* This must occur after reg_scan so that registers created by gcse
403 will have entries in the register tables.
405 We could have added a call to reg_scan after gcse_main in toplev.c,
406 but moving this call to init_alias_analysis is more efficient. */
407 init_alias_analysis ();
409 /* See if we went too far. Note that get_max_uid already returns
410 one more that the maximum uid of all insn. */
411 if (get_max_uid () > max_uid_for_loop)
413 /* Now reset it to the actual size we need. See above. */
414 max_uid_for_loop = get_max_uid ();
416 /* find_and_verify_loops has already called compute_luids, but it
417 might have rearranged code afterwards, so we need to recompute
419 max_luid = compute_luids (f, NULL_RTX, 0);
421 /* Don't leave gaps in uid_luid for insns that have been
422 deleted. It is possible that the first or last insn
423 using some register has been deleted by cross-jumping.
424 Make sure that uid_luid for that former insn's uid
425 points to the general area where that insn used to be. */
426 for (i = 0; i < max_uid_for_loop; i++)
428 uid_luid[0] = uid_luid[i];
429 if (uid_luid[0] != 0)
432 for (i = 0; i < max_uid_for_loop; i++)
433 if (uid_luid[i] == 0)
434 uid_luid[i] = uid_luid[i - 1];
436 /* Determine if the function has indirect jump. On some systems
437 this prevents low overhead loop instructions from being used. */
438 indirect_jump_in_function = indirect_jump_in_function_p (f);
440 /* Now scan the loops, last ones first, since this means inner ones are done
441 before outer ones. */
442 for (i = max_loop_num - 1; i >= 0; i--)
444 struct loop *loop = &loops->array[i];
446 if (! loop->invalid && loop->end)
447 scan_loop (loop, flags);
450 /* If there were lexical blocks inside the loop, they have been
451 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
452 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
453 the BLOCKs as well. */
454 if (write_symbols != NO_DEBUG)
457 end_alias_analysis ();
466 /* Returns the next insn, in execution order, after INSN. START and
467 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
468 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
469 insn-stream; it is used with loops that are entered near the
473 next_insn_in_loop (loop, insn)
474 const struct loop *loop;
477 insn = NEXT_INSN (insn);
479 if (insn == loop->end)
482 /* Go to the top of the loop, and continue there. */
489 if (insn == loop->scan_start)
496 /* Optimize one loop described by LOOP. */
498 /* ??? Could also move memory writes out of loops if the destination address
499 is invariant, the source is invariant, the memory write is not volatile,
500 and if we can prove that no read inside the loop can read this address
501 before the write occurs. If there is a read of this address after the
502 write, then we can also mark the memory read as invariant. */
505 scan_loop (loop, flags)
509 struct loop_info *loop_info = LOOP_INFO (loop);
510 struct loop_regs *regs = LOOP_REGS (loop);
512 rtx loop_start = loop->start;
513 rtx loop_end = loop->end;
515 /* 1 if we are scanning insns that could be executed zero times. */
517 /* 1 if we are scanning insns that might never be executed
518 due to a subroutine call which might exit before they are reached. */
520 /* Jump insn that enters the loop, or 0 if control drops in. */
521 rtx loop_entry_jump = 0;
522 /* Number of insns in the loop. */
525 rtx temp, update_start, update_end;
526 /* The SET from an insn, if it is the only SET in the insn. */
528 /* Chain describing insns movable in current loop. */
529 struct loop_movables *movables = LOOP_MOVABLES (loop);
530 /* Ratio of extra register life span we can justify
531 for saving an instruction. More if loop doesn't call subroutines
532 since in that case saving an insn makes more difference
533 and more registers are available. */
535 /* Nonzero if we are scanning instructions in a sub-loop. */
544 /* Determine whether this loop starts with a jump down to a test at
545 the end. This will occur for a small number of loops with a test
546 that is too complex to duplicate in front of the loop.
548 We search for the first insn or label in the loop, skipping NOTEs.
549 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
550 (because we might have a loop executed only once that contains a
551 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
552 (in case we have a degenerate loop).
554 Note that if we mistakenly think that a loop is entered at the top
555 when, in fact, it is entered at the exit test, the only effect will be
556 slightly poorer optimization. Making the opposite error can generate
557 incorrect code. Since very few loops now start with a jump to the
558 exit test, the code here to detect that case is very conservative. */
560 for (p = NEXT_INSN (loop_start);
562 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
563 && (GET_CODE (p) != NOTE
564 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
565 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
569 loop->scan_start = p;
571 /* Set up variables describing this loop. */
573 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
575 /* If loop has a jump before the first label,
576 the true entry is the target of that jump.
577 Start scan from there.
578 But record in LOOP->TOP the place where the end-test jumps
579 back to so we can scan that after the end of the loop. */
580 if (GET_CODE (p) == JUMP_INSN)
584 /* Loop entry must be unconditional jump (and not a RETURN) */
585 if (any_uncondjump_p (p)
586 && JUMP_LABEL (p) != 0
587 /* Check to see whether the jump actually
588 jumps out of the loop (meaning it's no loop).
589 This case can happen for things like
590 do {..} while (0). If this label was generated previously
591 by loop, we can't tell anything about it and have to reject
593 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
595 loop->top = next_label (loop->scan_start);
596 loop->scan_start = JUMP_LABEL (p);
600 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
601 as required by loop_reg_used_before_p. So skip such loops. (This
602 test may never be true, but it's best to play it safe.)
604 Also, skip loops where we do not start scanning at a label. This
605 test also rejects loops starting with a JUMP_INSN that failed the
608 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
609 || GET_CODE (loop->scan_start) != CODE_LABEL)
611 if (loop_dump_stream)
612 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
613 INSN_UID (loop_start), INSN_UID (loop_end));
617 /* Allocate extra space for REGs that might be created by load_mems.
618 We allocate a little extra slop as well, in the hopes that we
619 won't have to reallocate the regs array. */
620 loop_regs_scan (loop, loop_info->mems_idx + 16, &insn_count);
622 if (loop_dump_stream)
624 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
625 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
627 fprintf (loop_dump_stream, "Continue at insn %d.\n",
628 INSN_UID (loop->cont));
631 /* Scan through the loop finding insns that are safe to move.
632 Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
633 this reg will be considered invariant for subsequent insns.
634 We consider whether subsequent insns use the reg
635 in deciding whether it is worth actually moving.
637 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
638 and therefore it is possible that the insns we are scanning
639 would never be executed. At such times, we must make sure
640 that it is safe to execute the insn once instead of zero times.
641 When MAYBE_NEVER is 0, all insns will be executed at least once
642 so that is not a problem. */
644 for (p = next_insn_in_loop (loop, loop->scan_start);
646 p = next_insn_in_loop (loop, p))
648 if (GET_CODE (p) == INSN
649 && (set = single_set (p))
650 && GET_CODE (SET_DEST (set)) == REG
651 && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
656 rtx src = SET_SRC (set);
657 rtx dependencies = 0;
659 /* Figure out what to use as a source of this insn. If a REG_EQUIV
660 note is given or if a REG_EQUAL note with a constant operand is
661 specified, use it as the source and mark that we should move
662 this insn by calling emit_move_insn rather that duplicating the
665 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
667 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
669 src = XEXP (temp, 0), move_insn = 1;
672 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
673 if (temp && CONSTANT_P (XEXP (temp, 0)))
674 src = XEXP (temp, 0), move_insn = 1;
675 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
677 src = XEXP (temp, 0);
678 /* A libcall block can use regs that don't appear in
679 the equivalent expression. To move the libcall,
680 we must move those regs too. */
681 dependencies = libcall_other_reg (p, src);
685 /* Don't try to optimize a register that was made
686 by loop-optimization for an inner loop.
687 We don't know its life-span, so we can't compute the benefit. */
688 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
690 else if (/* The register is used in basic blocks other
691 than the one where it is set (meaning that
692 something after this point in the loop might
693 depend on its value before the set). */
694 ! reg_in_basic_block_p (p, SET_DEST (set))
695 /* And the set is not guaranteed to be executed one
696 the loop starts, or the value before the set is
697 needed before the set occurs...
699 ??? Note we have quadratic behaviour here, mitigated
700 by the fact that the previous test will often fail for
701 large loops. Rather than re-scanning the entire loop
702 each time for register usage, we should build tables
703 of the register usage and use them here instead. */
705 || loop_reg_used_before_p (loop, set, p)))
706 /* It is unsafe to move the set.
708 This code used to consider it OK to move a set of a variable
709 which was not created by the user and not used in an exit test.
710 That behavior is incorrect and was removed. */
712 else if ((tem = loop_invariant_p (loop, src))
713 && (dependencies == 0
714 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
715 && (regs->array[REGNO (SET_DEST (set))].set_in_loop == 1
717 = consec_sets_invariant_p
718 (loop, SET_DEST (set),
719 regs->array[REGNO (SET_DEST (set))].set_in_loop,
721 /* If the insn can cause a trap (such as divide by zero),
722 can't move it unless it's guaranteed to be executed
723 once loop is entered. Even a function call might
724 prevent the trap insn from being reached
725 (since it might exit!) */
726 && ! ((maybe_never || call_passed)
727 && may_trap_p (src)))
729 register struct movable *m;
730 register int regno = REGNO (SET_DEST (set));
732 /* A potential lossage is where we have a case where two insns
733 can be combined as long as they are both in the loop, but
734 we move one of them outside the loop. For large loops,
735 this can lose. The most common case of this is the address
736 of a function being called.
738 Therefore, if this register is marked as being used exactly
739 once if we are in a loop with calls (a "large loop"), see if
740 we can replace the usage of this register with the source
741 of this SET. If we can, delete this insn.
743 Don't do this if P has a REG_RETVAL note or if we have
744 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
746 if (loop_info->has_call
747 && regs->array[regno].single_usage != 0
748 && regs->array[regno].single_usage != const0_rtx
749 && REGNO_FIRST_UID (regno) == INSN_UID (p)
750 && (REGNO_LAST_UID (regno)
751 == INSN_UID (regs->array[regno].single_usage))
752 && regs->array[regno].set_in_loop == 1
753 && ! side_effects_p (SET_SRC (set))
754 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
755 && (! SMALL_REGISTER_CLASSES
756 || (! (GET_CODE (SET_SRC (set)) == REG
757 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
758 /* This test is not redundant; SET_SRC (set) might be
759 a call-clobbered register and the life of REGNO
760 might span a call. */
761 && ! modified_between_p (SET_SRC (set), p,
762 regs->array[regno].single_usage)
763 && no_labels_between_p (p, regs->array[regno].single_usage)
764 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
765 regs->array[regno].single_usage))
767 /* Replace any usage in a REG_EQUAL note. Must copy the
768 new source, so that we don't get rtx sharing between the
769 SET_SOURCE and REG_NOTES of insn p. */
770 REG_NOTES (regs->array[regno].single_usage)
771 = replace_rtx (REG_NOTES (regs->array[regno].single_usage),
772 SET_DEST (set), copy_rtx (SET_SRC (set)));
775 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
776 NOTE_SOURCE_FILE (p) = 0;
777 regs->array[regno].set_in_loop = 0;
781 m = (struct movable *) xmalloc (sizeof (struct movable));
785 m->dependencies = dependencies;
786 m->set_dest = SET_DEST (set);
788 m->consec = regs->array[REGNO (SET_DEST (set))].set_in_loop - 1;
792 m->move_insn = move_insn;
793 m->move_insn_first = 0;
794 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
795 m->savemode = VOIDmode;
797 /* Set M->cond if either loop_invariant_p
798 or consec_sets_invariant_p returned 2
799 (only conditionally invariant). */
800 m->cond = ((tem | tem1 | tem2) > 1);
801 m->global = LOOP_REG_GLOBAL_P (loop, regno);
803 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
804 m->savings = regs->array[regno].n_times_set;
805 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
806 m->savings += libcall_benefit (p);
807 regs->array[regno].set_in_loop = move_insn ? -2 : -1;
808 /* Add M to the end of the chain MOVABLES. */
809 loop_movables_add (movables, m);
813 /* It is possible for the first instruction to have a
814 REG_EQUAL note but a non-invariant SET_SRC, so we must
815 remember the status of the first instruction in case
816 the last instruction doesn't have a REG_EQUAL note. */
817 m->move_insn_first = m->move_insn;
819 /* Skip this insn, not checking REG_LIBCALL notes. */
820 p = next_nonnote_insn (p);
821 /* Skip the consecutive insns, if there are any. */
822 p = skip_consec_insns (p, m->consec);
823 /* Back up to the last insn of the consecutive group. */
824 p = prev_nonnote_insn (p);
826 /* We must now reset m->move_insn, m->is_equiv, and possibly
827 m->set_src to correspond to the effects of all the
829 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
831 m->set_src = XEXP (temp, 0), m->move_insn = 1;
834 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
835 if (temp && CONSTANT_P (XEXP (temp, 0)))
836 m->set_src = XEXP (temp, 0), m->move_insn = 1;
841 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
844 /* If this register is always set within a STRICT_LOW_PART
845 or set to zero, then its high bytes are constant.
846 So clear them outside the loop and within the loop
847 just load the low bytes.
848 We must check that the machine has an instruction to do so.
849 Also, if the value loaded into the register
850 depends on the same register, this cannot be done. */
851 else if (SET_SRC (set) == const0_rtx
852 && GET_CODE (NEXT_INSN (p)) == INSN
853 && (set1 = single_set (NEXT_INSN (p)))
854 && GET_CODE (set1) == SET
855 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
856 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
857 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
859 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
861 register int regno = REGNO (SET_DEST (set));
862 if (regs->array[regno].set_in_loop == 2)
864 register struct movable *m;
865 m = (struct movable *) xmalloc (sizeof (struct movable));
868 m->set_dest = SET_DEST (set);
875 m->move_insn_first = 0;
877 /* If the insn may not be executed on some cycles,
878 we can't clear the whole reg; clear just high part.
879 Not even if the reg is used only within this loop.
886 Clearing x before the inner loop could clobber a value
887 being saved from the last time around the outer loop.
888 However, if the reg is not used outside this loop
889 and all uses of the register are in the same
890 basic block as the store, there is no problem.
892 If this insn was made by loop, we don't know its
893 INSN_LUID and hence must make a conservative
895 m->global = (INSN_UID (p) >= max_uid_for_loop
896 || LOOP_REG_GLOBAL_P (loop, regno)
897 || (labels_in_range_p
898 (p, REGNO_FIRST_LUID (regno))));
899 if (maybe_never && m->global)
900 m->savemode = GET_MODE (SET_SRC (set1));
902 m->savemode = VOIDmode;
906 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
908 regs->array[regno].set_in_loop = -1;
909 /* Add M to the end of the chain MOVABLES. */
910 loop_movables_add (movables, m);
914 /* Past a call insn, we get to insns which might not be executed
915 because the call might exit. This matters for insns that trap.
916 Constant and pure call insns always return, so they don't count. */
917 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
919 /* Past a label or a jump, we get to insns for which we
920 can't count on whether or how many times they will be
921 executed during each iteration. Therefore, we can
922 only move out sets of trivial variables
923 (those not used after the loop). */
924 /* Similar code appears twice in strength_reduce. */
925 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
926 /* If we enter the loop in the middle, and scan around to the
927 beginning, don't set maybe_never for that. This must be an
928 unconditional jump, otherwise the code at the top of the
929 loop might never be executed. Unconditional jumps are
930 followed a by barrier then loop end. */
931 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
932 && NEXT_INSN (NEXT_INSN (p)) == loop_end
933 && any_uncondjump_p (p)))
935 else if (GET_CODE (p) == NOTE)
937 /* At the virtual top of a converted loop, insns are again known to
938 be executed: logically, the loop begins here even though the exit
939 code has been duplicated. */
940 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
941 maybe_never = call_passed = 0;
942 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
944 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
949 /* If one movable subsumes another, ignore that other. */
951 ignore_some_movables (movables);
953 /* For each movable insn, see if the reg that it loads
954 leads when it dies right into another conditionally movable insn.
955 If so, record that the second insn "forces" the first one,
956 since the second can be moved only if the first is. */
958 force_movables (movables);
960 /* See if there are multiple movable insns that load the same value.
961 If there are, make all but the first point at the first one
962 through the `match' field, and add the priorities of them
963 all together as the priority of the first. */
965 combine_movables (movables, regs);
967 /* Now consider each movable insn to decide whether it is worth moving.
968 Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
970 Generally this increases code size, so do not move moveables when
971 optimizing for code size. */
974 move_movables (loop, movables, threshold, insn_count);
976 /* Now candidates that still are negative are those not moved.
977 Change regs->array[I].set_in_loop to indicate that those are not actually
979 for (i = 0; i < regs->num; i++)
980 if (regs->array[i].set_in_loop < 0)
981 regs->array[i].set_in_loop = regs->array[i].n_times_set;
983 /* Now that we've moved some things out of the loop, we might be able to
984 hoist even more memory references. */
987 /* Recalculate regs->array if load_mems has created new registers. */
988 if (max_reg_num () > regs->num)
989 loop_regs_scan (loop, 0, &insn_count);
991 for (update_start = loop_start;
992 PREV_INSN (update_start)
993 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
994 update_start = PREV_INSN (update_start))
996 update_end = NEXT_INSN (loop_end);
998 reg_scan_update (update_start, update_end, loop_max_reg);
999 loop_max_reg = max_reg_num ();
1001 if (flag_strength_reduce)
1003 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1004 /* Ensure our label doesn't go away. */
1005 LABEL_NUSES (update_end)++;
1007 strength_reduce (loop, insn_count, flags);
1009 reg_scan_update (update_start, update_end, loop_max_reg);
1010 loop_max_reg = max_reg_num ();
1012 if (update_end && GET_CODE (update_end) == CODE_LABEL
1013 && --LABEL_NUSES (update_end) == 0)
1014 delete_insn (update_end);
1018 /* The movable information is required for strength reduction. */
1019 loop_movables_free (movables);
1026 /* Add elements to *OUTPUT to record all the pseudo-regs
1027 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1030 record_excess_regs (in_this, not_in_this, output)
1031 rtx in_this, not_in_this;
1038 code = GET_CODE (in_this);
1052 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1053 && ! reg_mentioned_p (in_this, not_in_this))
1054 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1061 fmt = GET_RTX_FORMAT (code);
1062 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1069 for (j = 0; j < XVECLEN (in_this, i); j++)
1070 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1074 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1080 /* Check what regs are referred to in the libcall block ending with INSN,
1081 aside from those mentioned in the equivalent value.
1082 If there are none, return 0.
1083 If there are one or more, return an EXPR_LIST containing all of them. */
1086 libcall_other_reg (insn, equiv)
1089 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1090 rtx p = XEXP (note, 0);
1093 /* First, find all the regs used in the libcall block
1094 that are not mentioned as inputs to the result. */
1098 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1099 || GET_CODE (p) == CALL_INSN)
1100 record_excess_regs (PATTERN (p), equiv, &output);
1107 /* Return 1 if all uses of REG
1108 are between INSN and the end of the basic block. */
1111 reg_in_basic_block_p (insn, reg)
1114 int regno = REGNO (reg);
1117 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1120 /* Search this basic block for the already recorded last use of the reg. */
1121 for (p = insn; p; p = NEXT_INSN (p))
1123 switch (GET_CODE (p))
1130 /* Ordinary insn: if this is the last use, we win. */
1131 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1136 /* Jump insn: if this is the last use, we win. */
1137 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1139 /* Otherwise, it's the end of the basic block, so we lose. */
1144 /* It's the end of the basic block, so we lose. */
1152 /* The "last use" that was recorded can't be found after the first
1153 use. This can happen when the last use was deleted while
1154 processing an inner loop, this inner loop was then completely
1155 unrolled, and the outer loop is always exited after the inner loop,
1156 so that everything after the first use becomes a single basic block. */
1160 /* Compute the benefit of eliminating the insns in the block whose
1161 last insn is LAST. This may be a group of insns used to compute a
1162 value directly or can contain a library call. */
1165 libcall_benefit (last)
1171 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1172 insn != last; insn = NEXT_INSN (insn))
1174 if (GET_CODE (insn) == CALL_INSN)
1175 benefit += 10; /* Assume at least this many insns in a library
1177 else if (GET_CODE (insn) == INSN
1178 && GET_CODE (PATTERN (insn)) != USE
1179 && GET_CODE (PATTERN (insn)) != CLOBBER)
1186 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1189 skip_consec_insns (insn, count)
1193 for (; count > 0; count--)
1197 /* If first insn of libcall sequence, skip to end. */
1198 /* Do this at start of loop, since INSN is guaranteed to
1200 if (GET_CODE (insn) != NOTE
1201 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1202 insn = XEXP (temp, 0);
1205 insn = NEXT_INSN (insn);
1206 while (GET_CODE (insn) == NOTE);
1212 /* Ignore any movable whose insn falls within a libcall
1213 which is part of another movable.
1214 We make use of the fact that the movable for the libcall value
1215 was made later and so appears later on the chain. */
1218 ignore_some_movables (movables)
1219 struct loop_movables *movables;
1221 register struct movable *m, *m1;
1223 for (m = movables->head; m; m = m->next)
1225 /* Is this a movable for the value of a libcall? */
1226 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1230 /* Check for earlier movables inside that range,
1231 and mark them invalid. We cannot use LUIDs here because
1232 insns created by loop.c for prior loops don't have LUIDs.
1233 Rather than reject all such insns from movables, we just
1234 explicitly check each insn in the libcall (since invariant
1235 libcalls aren't that common). */
1236 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1237 for (m1 = movables->head; m1 != m; m1 = m1->next)
1238 if (m1->insn == insn)
1244 /* For each movable insn, see if the reg that it loads
1245 leads when it dies right into another conditionally movable insn.
1246 If so, record that the second insn "forces" the first one,
1247 since the second can be moved only if the first is. */
1250 force_movables (movables)
1251 struct loop_movables *movables;
1253 register struct movable *m, *m1;
1254 for (m1 = movables->head; m1; m1 = m1->next)
1255 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1256 if (!m1->partial && !m1->done)
1258 int regno = m1->regno;
1259 for (m = m1->next; m; m = m->next)
1260 /* ??? Could this be a bug? What if CSE caused the
1261 register of M1 to be used after this insn?
1262 Since CSE does not update regno_last_uid,
1263 this insn M->insn might not be where it dies.
1264 But very likely this doesn't matter; what matters is
1265 that M's reg is computed from M1's reg. */
1266 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1269 if (m != 0 && m->set_src == m1->set_dest
1270 /* If m->consec, m->set_src isn't valid. */
1274 /* Increase the priority of the moving the first insn
1275 since it permits the second to be moved as well. */
1279 m1->lifetime += m->lifetime;
1280 m1->savings += m->savings;
1285 /* Find invariant expressions that are equal and can be combined into
1289 combine_movables (movables, regs)
1290 struct loop_movables *movables;
1291 struct loop_regs *regs;
1293 register struct movable *m;
1294 char *matched_regs = (char *) xmalloc (regs->num);
1295 enum machine_mode mode;
1297 /* Regs that are set more than once are not allowed to match
1298 or be matched. I'm no longer sure why not. */
1299 /* Perhaps testing m->consec_sets would be more appropriate here? */
1301 for (m = movables->head; m; m = m->next)
1302 if (m->match == 0 && regs->array[m->regno].n_times_set == 1
1305 register struct movable *m1;
1306 int regno = m->regno;
1308 memset (matched_regs, 0, regs->num);
1309 matched_regs[regno] = 1;
1311 /* We want later insns to match the first one. Don't make the first
1312 one match any later ones. So start this loop at m->next. */
1313 for (m1 = m->next; m1; m1 = m1->next)
1314 if (m != m1 && m1->match == 0
1315 && regs->array[m1->regno].n_times_set == 1
1316 /* A reg used outside the loop mustn't be eliminated. */
1318 /* A reg used for zero-extending mustn't be eliminated. */
1320 && (matched_regs[m1->regno]
1323 /* Can combine regs with different modes loaded from the
1324 same constant only if the modes are the same or
1325 if both are integer modes with M wider or the same
1326 width as M1. The check for integer is redundant, but
1327 safe, since the only case of differing destination
1328 modes with equal sources is when both sources are
1329 VOIDmode, i.e., CONST_INT. */
1330 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1331 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1332 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1333 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1334 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1335 /* See if the source of M1 says it matches M. */
1336 && ((GET_CODE (m1->set_src) == REG
1337 && matched_regs[REGNO (m1->set_src)])
1338 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1340 && ((m->dependencies == m1->dependencies)
1341 || rtx_equal_p (m->dependencies, m1->dependencies)))
1343 m->lifetime += m1->lifetime;
1344 m->savings += m1->savings;
1347 matched_regs[m1->regno] = 1;
1351 /* Now combine the regs used for zero-extension.
1352 This can be done for those not marked `global'
1353 provided their lives don't overlap. */
1355 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1356 mode = GET_MODE_WIDER_MODE (mode))
1358 register struct movable *m0 = 0;
1360 /* Combine all the registers for extension from mode MODE.
1361 Don't combine any that are used outside this loop. */
1362 for (m = movables->head; m; m = m->next)
1363 if (m->partial && ! m->global
1364 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1366 register struct movable *m1;
1367 int first = REGNO_FIRST_LUID (m->regno);
1368 int last = REGNO_LAST_LUID (m->regno);
1372 /* First one: don't check for overlap, just record it. */
1377 /* Make sure they extend to the same mode.
1378 (Almost always true.) */
1379 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1382 /* We already have one: check for overlap with those
1383 already combined together. */
1384 for (m1 = movables->head; m1 != m; m1 = m1->next)
1385 if (m1 == m0 || (m1->partial && m1->match == m0))
1386 if (! (REGNO_FIRST_LUID (m1->regno) > last
1387 || REGNO_LAST_LUID (m1->regno) < first))
1390 /* No overlap: we can combine this with the others. */
1391 m0->lifetime += m->lifetime;
1392 m0->savings += m->savings;
1402 free (matched_regs);
1405 /* Return 1 if regs X and Y will become the same if moved. */
1408 regs_match_p (x, y, movables)
1410 struct loop_movables *movables;
1412 unsigned int xn = REGNO (x);
1413 unsigned int yn = REGNO (y);
1414 struct movable *mx, *my;
1416 for (mx = movables->head; mx; mx = mx->next)
1417 if (mx->regno == xn)
1420 for (my = movables->head; my; my = my->next)
1421 if (my->regno == yn)
1425 && ((mx->match == my->match && mx->match != 0)
1427 || mx == my->match));
1430 /* Return 1 if X and Y are identical-looking rtx's.
1431 This is the Lisp function EQUAL for rtx arguments.
1433 If two registers are matching movables or a movable register and an
1434 equivalent constant, consider them equal. */
1437 rtx_equal_for_loop_p (x, y, movables, regs)
1439 struct loop_movables *movables;
1440 struct loop_regs *regs;
1444 register struct movable *m;
1445 register enum rtx_code code;
1446 register const char *fmt;
1450 if (x == 0 || y == 0)
1453 code = GET_CODE (x);
1455 /* If we have a register and a constant, they may sometimes be
1457 if (GET_CODE (x) == REG && regs->array[REGNO (x)].set_in_loop == -2
1460 for (m = movables->head; m; m = m->next)
1461 if (m->move_insn && m->regno == REGNO (x)
1462 && rtx_equal_p (m->set_src, y))
1465 else if (GET_CODE (y) == REG && regs->array[REGNO (y)].set_in_loop == -2
1468 for (m = movables->head; m; m = m->next)
1469 if (m->move_insn && m->regno == REGNO (y)
1470 && rtx_equal_p (m->set_src, x))
1474 /* Otherwise, rtx's of different codes cannot be equal. */
1475 if (code != GET_CODE (y))
1478 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1479 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1481 if (GET_MODE (x) != GET_MODE (y))
1484 /* These three types of rtx's can be compared nonrecursively. */
1486 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1488 if (code == LABEL_REF)
1489 return XEXP (x, 0) == XEXP (y, 0);
1490 if (code == SYMBOL_REF)
1491 return XSTR (x, 0) == XSTR (y, 0);
1493 /* Compare the elements. If any pair of corresponding elements
1494 fail to match, return 0 for the whole things. */
1496 fmt = GET_RTX_FORMAT (code);
1497 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1502 if (XWINT (x, i) != XWINT (y, i))
1507 if (XINT (x, i) != XINT (y, i))
1512 /* Two vectors must have the same length. */
1513 if (XVECLEN (x, i) != XVECLEN (y, i))
1516 /* And the corresponding elements must match. */
1517 for (j = 0; j < XVECLEN (x, i); j++)
1518 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1519 movables, regs) == 0)
1524 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1530 if (strcmp (XSTR (x, i), XSTR (y, i)))
1535 /* These are just backpointers, so they don't matter. */
1541 /* It is believed that rtx's at this level will never
1542 contain anything but integers and other rtx's,
1543 except for within LABEL_REFs and SYMBOL_REFs. */
1551 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1552 insns in INSNS which use the reference. LABEL_NUSES for CODE_LABEL
1553 references is incremented once for each added note. */
1556 add_label_notes (x, insns)
1560 enum rtx_code code = GET_CODE (x);
1565 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1567 /* This code used to ignore labels that referred to dispatch tables to
1568 avoid flow generating (slighly) worse code.
1570 We no longer ignore such label references (see LABEL_REF handling in
1571 mark_jump_label for additional information). */
1572 for (insn = insns; insn; insn = NEXT_INSN (insn))
1573 if (reg_mentioned_p (XEXP (x, 0), insn))
1575 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1577 if (LABEL_P (XEXP (x, 0)))
1578 LABEL_NUSES (XEXP (x, 0))++;
1582 fmt = GET_RTX_FORMAT (code);
1583 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1586 add_label_notes (XEXP (x, i), insns);
1587 else if (fmt[i] == 'E')
1588 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1589 add_label_notes (XVECEXP (x, i, j), insns);
1593 /* Scan MOVABLES, and move the insns that deserve to be moved.
1594 If two matching movables are combined, replace one reg with the
1595 other throughout. */
1598 move_movables (loop, movables, threshold, insn_count)
1600 struct loop_movables *movables;
1604 struct loop_regs *regs = LOOP_REGS (loop);
1605 int nregs = regs->num;
1607 register struct movable *m;
1609 rtx loop_start = loop->start;
1610 rtx loop_end = loop->end;
1611 /* Map of pseudo-register replacements to handle combining
1612 when we move several insns that load the same value
1613 into different pseudo-registers. */
1614 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1615 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1619 for (m = movables->head; m; m = m->next)
1621 /* Describe this movable insn. */
1623 if (loop_dump_stream)
1625 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1626 INSN_UID (m->insn), m->regno, m->lifetime);
1628 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1630 fprintf (loop_dump_stream, "cond ");
1632 fprintf (loop_dump_stream, "force ");
1634 fprintf (loop_dump_stream, "global ");
1636 fprintf (loop_dump_stream, "done ");
1638 fprintf (loop_dump_stream, "move-insn ");
1640 fprintf (loop_dump_stream, "matches %d ",
1641 INSN_UID (m->match->insn));
1643 fprintf (loop_dump_stream, "forces %d ",
1644 INSN_UID (m->forces->insn));
1647 /* Count movables. Value used in heuristics in strength_reduce. */
1650 /* Ignore the insn if it's already done (it matched something else).
1651 Otherwise, see if it is now safe to move. */
1655 || (1 == loop_invariant_p (loop, m->set_src)
1656 && (m->dependencies == 0
1657 || 1 == loop_invariant_p (loop, m->dependencies))
1659 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1662 && (! m->forces || m->forces->done))
1666 int savings = m->savings;
1668 /* We have an insn that is safe to move.
1669 Compute its desirability. */
1674 if (loop_dump_stream)
1675 fprintf (loop_dump_stream, "savings %d ", savings);
1677 if (regs->array[regno].moved_once && loop_dump_stream)
1678 fprintf (loop_dump_stream, "halved since already moved ");
1680 /* An insn MUST be moved if we already moved something else
1681 which is safe only if this one is moved too: that is,
1682 if already_moved[REGNO] is nonzero. */
1684 /* An insn is desirable to move if the new lifetime of the
1685 register is no more than THRESHOLD times the old lifetime.
1686 If it's not desirable, it means the loop is so big
1687 that moving won't speed things up much,
1688 and it is liable to make register usage worse. */
1690 /* It is also desirable to move if it can be moved at no
1691 extra cost because something else was already moved. */
1693 if (already_moved[regno]
1694 || flag_move_all_movables
1695 || (threshold * savings * m->lifetime) >=
1696 (regs->array[regno].moved_once ? insn_count * 2 : insn_count)
1697 || (m->forces && m->forces->done
1698 && regs->array[m->forces->regno].n_times_set == 1))
1701 register struct movable *m1;
1702 rtx first = NULL_RTX;
1704 /* Now move the insns that set the reg. */
1706 if (m->partial && m->match)
1710 /* Find the end of this chain of matching regs.
1711 Thus, we load each reg in the chain from that one reg.
1712 And that reg is loaded with 0 directly,
1713 since it has ->match == 0. */
1714 for (m1 = m; m1->match; m1 = m1->match);
1715 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1716 SET_DEST (PATTERN (m1->insn)));
1717 i1 = loop_insn_hoist (loop, newpat);
1719 /* Mark the moved, invariant reg as being allowed to
1720 share a hard reg with the other matching invariant. */
1721 REG_NOTES (i1) = REG_NOTES (m->insn);
1722 r1 = SET_DEST (PATTERN (m->insn));
1723 r2 = SET_DEST (PATTERN (m1->insn));
1725 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1726 gen_rtx_EXPR_LIST (VOIDmode, r2,
1728 delete_insn (m->insn);
1733 if (loop_dump_stream)
1734 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1736 /* If we are to re-generate the item being moved with a
1737 new move insn, first delete what we have and then emit
1738 the move insn before the loop. */
1739 else if (m->move_insn)
1743 for (count = m->consec; count >= 0; count--)
1745 /* If this is the first insn of a library call sequence,
1747 if (GET_CODE (p) != NOTE
1748 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1751 /* If this is the last insn of a libcall sequence, then
1752 delete every insn in the sequence except the last.
1753 The last insn is handled in the normal manner. */
1754 if (GET_CODE (p) != NOTE
1755 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1757 temp = XEXP (temp, 0);
1759 temp = delete_insn (temp);
1763 p = delete_insn (p);
1765 /* simplify_giv_expr expects that it can walk the insns
1766 at m->insn forwards and see this old sequence we are
1767 tossing here. delete_insn does preserve the next
1768 pointers, but when we skip over a NOTE we must fix
1769 it up. Otherwise that code walks into the non-deleted
1771 while (p && GET_CODE (p) == NOTE)
1772 p = NEXT_INSN (temp) = NEXT_INSN (p);
1776 emit_move_insn (m->set_dest, m->set_src);
1777 temp = get_insns ();
1778 seq = gen_sequence ();
1781 add_label_notes (m->set_src, temp);
1783 i1 = loop_insn_hoist (loop, seq);
1784 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1786 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1787 m->set_src, REG_NOTES (i1));
1789 if (loop_dump_stream)
1790 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1792 /* The more regs we move, the less we like moving them. */
1797 for (count = m->consec; count >= 0; count--)
1801 /* If first insn of libcall sequence, skip to end. */
1802 /* Do this at start of loop, since p is guaranteed to
1804 if (GET_CODE (p) != NOTE
1805 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1808 /* If last insn of libcall sequence, move all
1809 insns except the last before the loop. The last
1810 insn is handled in the normal manner. */
1811 if (GET_CODE (p) != NOTE
1812 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1816 rtx fn_address_insn = 0;
1819 for (temp = XEXP (temp, 0); temp != p;
1820 temp = NEXT_INSN (temp))
1826 if (GET_CODE (temp) == NOTE)
1829 body = PATTERN (temp);
1831 /* Find the next insn after TEMP,
1832 not counting USE or NOTE insns. */
1833 for (next = NEXT_INSN (temp); next != p;
1834 next = NEXT_INSN (next))
1835 if (! (GET_CODE (next) == INSN
1836 && GET_CODE (PATTERN (next)) == USE)
1837 && GET_CODE (next) != NOTE)
1840 /* If that is the call, this may be the insn
1841 that loads the function address.
1843 Extract the function address from the insn
1844 that loads it into a register.
1845 If this insn was cse'd, we get incorrect code.
1847 So emit a new move insn that copies the
1848 function address into the register that the
1849 call insn will use. flow.c will delete any
1850 redundant stores that we have created. */
1851 if (GET_CODE (next) == CALL_INSN
1852 && GET_CODE (body) == SET
1853 && GET_CODE (SET_DEST (body)) == REG
1854 && (n = find_reg_note (temp, REG_EQUAL,
1857 fn_reg = SET_SRC (body);
1858 if (GET_CODE (fn_reg) != REG)
1859 fn_reg = SET_DEST (body);
1860 fn_address = XEXP (n, 0);
1861 fn_address_insn = temp;
1863 /* We have the call insn.
1864 If it uses the register we suspect it might,
1865 load it with the correct address directly. */
1866 if (GET_CODE (temp) == CALL_INSN
1868 && reg_referenced_p (fn_reg, body))
1869 emit_insn_after (gen_move_insn (fn_reg,
1873 if (GET_CODE (temp) == CALL_INSN)
1875 i1 = emit_call_insn_before (body, loop_start);
1876 /* Because the USAGE information potentially
1877 contains objects other than hard registers
1878 we need to copy it. */
1879 if (CALL_INSN_FUNCTION_USAGE (temp))
1880 CALL_INSN_FUNCTION_USAGE (i1)
1881 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1884 i1 = loop_insn_hoist (loop, body);
1887 if (temp == fn_address_insn)
1888 fn_address_insn = i1;
1889 REG_NOTES (i1) = REG_NOTES (temp);
1895 if (m->savemode != VOIDmode)
1897 /* P sets REG to zero; but we should clear only
1898 the bits that are not covered by the mode
1900 rtx reg = m->set_dest;
1906 (GET_MODE (reg), and_optab, reg,
1907 GEN_INT ((((HOST_WIDE_INT) 1
1908 << GET_MODE_BITSIZE (m->savemode)))
1910 reg, 1, OPTAB_LIB_WIDEN);
1914 emit_move_insn (reg, tem);
1915 sequence = gen_sequence ();
1917 i1 = loop_insn_hoist (loop, sequence);
1919 else if (GET_CODE (p) == CALL_INSN)
1921 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1922 /* Because the USAGE information potentially
1923 contains objects other than hard registers
1924 we need to copy it. */
1925 if (CALL_INSN_FUNCTION_USAGE (p))
1926 CALL_INSN_FUNCTION_USAGE (i1)
1927 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1929 else if (count == m->consec && m->move_insn_first)
1932 /* The SET_SRC might not be invariant, so we must
1933 use the REG_EQUAL note. */
1935 emit_move_insn (m->set_dest, m->set_src);
1936 temp = get_insns ();
1937 seq = gen_sequence ();
1940 add_label_notes (m->set_src, temp);
1942 i1 = loop_insn_hoist (loop, seq);
1943 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1945 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1947 m->set_src, REG_NOTES (i1));
1950 i1 = loop_insn_hoist (loop, PATTERN (p));
1952 if (REG_NOTES (i1) == 0)
1954 REG_NOTES (i1) = REG_NOTES (p);
1956 /* If there is a REG_EQUAL note present whose value
1957 is not loop invariant, then delete it, since it
1958 may cause problems with later optimization passes.
1959 It is possible for cse to create such notes
1960 like this as a result of record_jump_cond. */
1962 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
1963 && ! loop_invariant_p (loop, XEXP (temp, 0)))
1964 remove_note (i1, temp);
1970 if (loop_dump_stream)
1971 fprintf (loop_dump_stream, " moved to %d",
1974 /* If library call, now fix the REG_NOTES that contain
1975 insn pointers, namely REG_LIBCALL on FIRST
1976 and REG_RETVAL on I1. */
1977 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
1979 XEXP (temp, 0) = first;
1980 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
1981 XEXP (temp, 0) = i1;
1988 /* simplify_giv_expr expects that it can walk the insns
1989 at m->insn forwards and see this old sequence we are
1990 tossing here. delete_insn does preserve the next
1991 pointers, but when we skip over a NOTE we must fix
1992 it up. Otherwise that code walks into the non-deleted
1994 while (p && GET_CODE (p) == NOTE)
1995 p = NEXT_INSN (temp) = NEXT_INSN (p);
1998 /* The more regs we move, the less we like moving them. */
2002 /* Any other movable that loads the same register
2004 already_moved[regno] = 1;
2006 /* This reg has been moved out of one loop. */
2007 regs->array[regno].moved_once = 1;
2009 /* The reg set here is now invariant. */
2011 regs->array[regno].set_in_loop = 0;
2015 /* Change the length-of-life info for the register
2016 to say it lives at least the full length of this loop.
2017 This will help guide optimizations in outer loops. */
2019 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2020 /* This is the old insn before all the moved insns.
2021 We can't use the moved insn because it is out of range
2022 in uid_luid. Only the old insns have luids. */
2023 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2024 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2025 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2027 /* Combine with this moved insn any other matching movables. */
2030 for (m1 = movables->head; m1; m1 = m1->next)
2035 /* Schedule the reg loaded by M1
2036 for replacement so that shares the reg of M.
2037 If the modes differ (only possible in restricted
2038 circumstances, make a SUBREG.
2040 Note this assumes that the target dependent files
2041 treat REG and SUBREG equally, including within
2042 GO_IF_LEGITIMATE_ADDRESS and in all the
2043 predicates since we never verify that replacing the
2044 original register with a SUBREG results in a
2045 recognizable insn. */
2046 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2047 reg_map[m1->regno] = m->set_dest;
2050 = gen_lowpart_common (GET_MODE (m1->set_dest),
2053 /* Get rid of the matching insn
2054 and prevent further processing of it. */
2057 /* if library call, delete all insn except last, which
2059 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2062 for (temp = XEXP (temp, 0); temp != m1->insn;
2063 temp = NEXT_INSN (temp))
2066 delete_insn (m1->insn);
2068 /* Any other movable that loads the same register
2070 already_moved[m1->regno] = 1;
2072 /* The reg merged here is now invariant,
2073 if the reg it matches is invariant. */
2075 regs->array[m1->regno].set_in_loop = 0;
2078 else if (loop_dump_stream)
2079 fprintf (loop_dump_stream, "not desirable");
2081 else if (loop_dump_stream && !m->match)
2082 fprintf (loop_dump_stream, "not safe");
2084 if (loop_dump_stream)
2085 fprintf (loop_dump_stream, "\n");
2089 new_start = loop_start;
2091 /* Go through all the instructions in the loop, making
2092 all the register substitutions scheduled in REG_MAP. */
2093 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2094 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2095 || GET_CODE (p) == CALL_INSN)
2097 replace_regs (PATTERN (p), reg_map, nregs, 0);
2098 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2104 free (already_moved);
2109 loop_movables_add (movables, m)
2110 struct loop_movables *movables;
2113 if (movables->head == 0)
2116 movables->last->next = m;
2122 loop_movables_free (movables)
2123 struct loop_movables *movables;
2126 struct movable *m_next;
2128 for (m = movables->head; m; m = m_next)
2136 /* Scan X and replace the address of any MEM in it with ADDR.
2137 REG is the address that MEM should have before the replacement. */
2140 replace_call_address (x, reg, addr)
2143 register enum rtx_code code;
2145 register const char *fmt;
2149 code = GET_CODE (x);
2163 /* Short cut for very common case. */
2164 replace_call_address (XEXP (x, 1), reg, addr);
2168 /* Short cut for very common case. */
2169 replace_call_address (XEXP (x, 0), reg, addr);
2173 /* If this MEM uses a reg other than the one we expected,
2174 something is wrong. */
2175 if (XEXP (x, 0) != reg)
2184 fmt = GET_RTX_FORMAT (code);
2185 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2188 replace_call_address (XEXP (x, i), reg, addr);
2189 else if (fmt[i] == 'E')
2192 for (j = 0; j < XVECLEN (x, i); j++)
2193 replace_call_address (XVECEXP (x, i, j), reg, addr);
2199 /* Return the number of memory refs to addresses that vary
2203 count_nonfixed_reads (loop, x)
2204 const struct loop *loop;
2207 register enum rtx_code code;
2209 register const char *fmt;
2215 code = GET_CODE (x);
2229 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2230 + count_nonfixed_reads (loop, XEXP (x, 0)));
2237 fmt = GET_RTX_FORMAT (code);
2238 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2241 value += count_nonfixed_reads (loop, XEXP (x, i));
2245 for (j = 0; j < XVECLEN (x, i); j++)
2246 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2252 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2253 `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2254 `unknown_address_altered', `unknown_constant_address_altered', and
2255 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2256 list `store_mems' in LOOP. */
2262 register int level = 1;
2264 struct loop_info *loop_info = LOOP_INFO (loop);
2265 rtx start = loop->start;
2266 rtx end = loop->end;
2267 /* The label after END. Jumping here is just like falling off the
2268 end of the loop. We use next_nonnote_insn instead of next_label
2269 as a hedge against the (pathological) case where some actual insn
2270 might end up between the two. */
2271 rtx exit_target = next_nonnote_insn (end);
2273 loop_info->has_indirect_jump = indirect_jump_in_function;
2274 loop_info->pre_header_has_call = 0;
2275 loop_info->has_call = 0;
2276 loop_info->has_nonconst_call = 0;
2277 loop_info->has_volatile = 0;
2278 loop_info->has_tablejump = 0;
2279 loop_info->has_multiple_exit_targets = 0;
2282 loop_info->unknown_address_altered = 0;
2283 loop_info->unknown_constant_address_altered = 0;
2284 loop_info->store_mems = NULL_RTX;
2285 loop_info->first_loop_store_insn = NULL_RTX;
2286 loop_info->mems_idx = 0;
2287 loop_info->num_mem_sets = 0;
2290 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
2291 insn = PREV_INSN (insn))
2293 if (GET_CODE (insn) == CALL_INSN)
2295 loop_info->pre_header_has_call = 1;
2300 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2301 insn = NEXT_INSN (insn))
2303 if (GET_CODE (insn) == NOTE)
2305 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2308 /* Count number of loops contained in this one. */
2311 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2316 else if (GET_CODE (insn) == CALL_INSN)
2318 if (! CONST_CALL_P (insn))
2320 loop_info->unknown_address_altered = 1;
2321 loop_info->has_nonconst_call = 1;
2323 loop_info->has_call = 1;
2325 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2327 rtx label1 = NULL_RTX;
2328 rtx label2 = NULL_RTX;
2330 if (volatile_refs_p (PATTERN (insn)))
2331 loop_info->has_volatile = 1;
2333 if (GET_CODE (insn) == JUMP_INSN
2334 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2335 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2336 loop_info->has_tablejump = 1;
2338 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2339 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2340 loop_info->first_loop_store_insn = insn;
2342 if (! loop_info->has_multiple_exit_targets
2343 && GET_CODE (insn) == JUMP_INSN
2344 && GET_CODE (PATTERN (insn)) == SET
2345 && SET_DEST (PATTERN (insn)) == pc_rtx)
2347 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2349 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2350 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2354 label1 = SET_SRC (PATTERN (insn));
2359 if (label1 && label1 != pc_rtx)
2361 if (GET_CODE (label1) != LABEL_REF)
2363 /* Something tricky. */
2364 loop_info->has_multiple_exit_targets = 1;
2367 else if (XEXP (label1, 0) != exit_target
2368 && LABEL_OUTSIDE_LOOP_P (label1))
2370 /* A jump outside the current loop. */
2371 loop_info->has_multiple_exit_targets = 1;
2382 else if (GET_CODE (insn) == RETURN)
2383 loop_info->has_multiple_exit_targets = 1;
2386 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2387 if (/* An exception thrown by a called function might land us
2389 ! loop_info->has_nonconst_call
2390 /* We don't want loads for MEMs moved to a location before the
2391 one at which their stack memory becomes allocated. (Note
2392 that this is not a problem for malloc, etc., since those
2393 require actual function calls. */
2394 && ! current_function_calls_alloca
2395 /* There are ways to leave the loop other than falling off the
2397 && ! loop_info->has_multiple_exit_targets)
2398 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2399 insn = NEXT_INSN (insn))
2400 for_each_rtx (&insn, insert_loop_mem, loop_info);
2402 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2403 that loop_invariant_p and load_mems can use true_dependence
2404 to determine what is really clobbered. */
2405 if (loop_info->unknown_address_altered)
2407 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2409 loop_info->store_mems
2410 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2412 if (loop_info->unknown_constant_address_altered)
2414 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2416 RTX_UNCHANGING_P (mem) = 1;
2417 loop_info->store_mems
2418 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2422 /* Scan the function looking for loops. Record the start and end of each loop.
2423 Also mark as invalid loops any loops that contain a setjmp or are branched
2424 to from outside the loop. */
2427 find_and_verify_loops (f, loops)
2429 struct loops *loops;
2434 struct loop *current_loop;
2435 struct loop *next_loop;
2438 num_loops = loops->num;
2440 compute_luids (f, NULL_RTX, 0);
2442 /* If there are jumps to undefined labels,
2443 treat them as jumps out of any/all loops.
2444 This also avoids writing past end of tables when there are no loops. */
2447 /* Find boundaries of loops, mark which loops are contained within
2448 loops, and invalidate loops that have setjmp. */
2451 current_loop = NULL;
2452 for (insn = f; insn; insn = NEXT_INSN (insn))
2454 if (GET_CODE (insn) == NOTE)
2455 switch (NOTE_LINE_NUMBER (insn))
2457 case NOTE_INSN_LOOP_BEG:
2458 next_loop = loops->array + num_loops;
2459 next_loop->num = num_loops;
2461 next_loop->start = insn;
2462 next_loop->outer = current_loop;
2463 current_loop = next_loop;
2466 case NOTE_INSN_SETJMP:
2467 /* In this case, we must invalidate our current loop and any
2469 for (loop = current_loop; loop; loop = loop->outer)
2472 if (loop_dump_stream)
2473 fprintf (loop_dump_stream,
2474 "\nLoop at %d ignored due to setjmp.\n",
2475 INSN_UID (loop->start));
2479 case NOTE_INSN_LOOP_CONT:
2480 current_loop->cont = insn;
2483 case NOTE_INSN_LOOP_VTOP:
2484 current_loop->vtop = insn;
2487 case NOTE_INSN_LOOP_END:
2491 current_loop->end = insn;
2492 current_loop = current_loop->outer;
2499 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2500 enclosing loop, but this doesn't matter. */
2501 uid_loop[INSN_UID (insn)] = current_loop;
2504 /* Any loop containing a label used in an initializer must be invalidated,
2505 because it can be jumped into from anywhere. */
2507 for (label = forced_labels; label; label = XEXP (label, 1))
2509 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2510 loop; loop = loop->outer)
2514 /* Any loop containing a label used for an exception handler must be
2515 invalidated, because it can be jumped into from anywhere. */
2517 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2519 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2520 loop; loop = loop->outer)
2524 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2525 loop that it is not contained within, that loop is marked invalid.
2526 If any INSN or CALL_INSN uses a label's address, then the loop containing
2527 that label is marked invalid, because it could be jumped into from
2530 Also look for blocks of code ending in an unconditional branch that
2531 exits the loop. If such a block is surrounded by a conditional
2532 branch around the block, move the block elsewhere (see below) and
2533 invert the jump to point to the code block. This may eliminate a
2534 label in our loop and will simplify processing by both us and a
2535 possible second cse pass. */
2537 for (insn = f; insn; insn = NEXT_INSN (insn))
2540 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2542 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2544 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2547 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2548 loop; loop = loop->outer)
2553 if (GET_CODE (insn) != JUMP_INSN)
2556 mark_loop_jump (PATTERN (insn), this_loop);
2558 /* See if this is an unconditional branch outside the loop. */
2560 && (GET_CODE (PATTERN (insn)) == RETURN
2561 || (any_uncondjump_p (insn)
2562 && onlyjump_p (insn)
2563 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2565 && get_max_uid () < max_uid_for_loop)
2568 rtx our_next = next_real_insn (insn);
2569 rtx last_insn_to_move = NEXT_INSN (insn);
2570 struct loop *dest_loop;
2571 struct loop *outer_loop = NULL;
2573 /* Go backwards until we reach the start of the loop, a label,
2575 for (p = PREV_INSN (insn);
2576 GET_CODE (p) != CODE_LABEL
2577 && ! (GET_CODE (p) == NOTE
2578 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2579 && GET_CODE (p) != JUMP_INSN;
2583 /* Check for the case where we have a jump to an inner nested
2584 loop, and do not perform the optimization in that case. */
2586 if (JUMP_LABEL (insn))
2588 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2591 for (outer_loop = dest_loop; outer_loop;
2592 outer_loop = outer_loop->outer)
2593 if (outer_loop == this_loop)
2598 /* Make sure that the target of P is within the current loop. */
2600 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2601 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2602 outer_loop = this_loop;
2604 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2605 we have a block of code to try to move.
2607 We look backward and then forward from the target of INSN
2608 to find a BARRIER at the same loop depth as the target.
2609 If we find such a BARRIER, we make a new label for the start
2610 of the block, invert the jump in P and point it to that label,
2611 and move the block of code to the spot we found. */
2614 && GET_CODE (p) == JUMP_INSN
2615 && JUMP_LABEL (p) != 0
2616 /* Just ignore jumps to labels that were never emitted.
2617 These always indicate compilation errors. */
2618 && INSN_UID (JUMP_LABEL (p)) != 0
2619 && any_condjump_p (p) && onlyjump_p (p)
2620 && next_real_insn (JUMP_LABEL (p)) == our_next
2621 /* If it's not safe to move the sequence, then we
2623 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2624 &last_insn_to_move))
2627 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2628 struct loop *target_loop = uid_loop[INSN_UID (target)];
2631 for (loc = target; loc; loc = PREV_INSN (loc))
2632 if (GET_CODE (loc) == BARRIER
2633 /* Don't move things inside a tablejump. */
2634 && ((loc2 = next_nonnote_insn (loc)) == 0
2635 || GET_CODE (loc2) != CODE_LABEL
2636 || (loc2 = next_nonnote_insn (loc2)) == 0
2637 || GET_CODE (loc2) != JUMP_INSN
2638 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2639 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2640 && uid_loop[INSN_UID (loc)] == target_loop)
2644 for (loc = target; loc; loc = NEXT_INSN (loc))
2645 if (GET_CODE (loc) == BARRIER
2646 /* Don't move things inside a tablejump. */
2647 && ((loc2 = next_nonnote_insn (loc)) == 0
2648 || GET_CODE (loc2) != CODE_LABEL
2649 || (loc2 = next_nonnote_insn (loc2)) == 0
2650 || GET_CODE (loc2) != JUMP_INSN
2651 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2652 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2653 && uid_loop[INSN_UID (loc)] == target_loop)
2658 rtx cond_label = JUMP_LABEL (p);
2659 rtx new_label = get_label_after (p);
2661 /* Ensure our label doesn't go away. */
2662 LABEL_NUSES (cond_label)++;
2664 /* Verify that uid_loop is large enough and that
2666 if (invert_jump (p, new_label, 1))
2670 /* If no suitable BARRIER was found, create a suitable
2671 one before TARGET. Since TARGET is a fall through
2672 path, we'll need to insert an jump around our block
2673 and a add a BARRIER before TARGET.
2675 This creates an extra unconditional jump outside
2676 the loop. However, the benefits of removing rarely
2677 executed instructions from inside the loop usually
2678 outweighs the cost of the extra unconditional jump
2679 outside the loop. */
2684 temp = gen_jump (JUMP_LABEL (insn));
2685 temp = emit_jump_insn_before (temp, target);
2686 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2687 LABEL_NUSES (JUMP_LABEL (insn))++;
2688 loc = emit_barrier_before (target);
2691 /* Include the BARRIER after INSN and copy the
2693 new_label = squeeze_notes (new_label,
2695 reorder_insns (new_label, last_insn_to_move, loc);
2697 /* All those insns are now in TARGET_LOOP. */
2699 q != NEXT_INSN (last_insn_to_move);
2701 uid_loop[INSN_UID (q)] = target_loop;
2703 /* The label jumped to by INSN is no longer a loop
2704 exit. Unless INSN does not have a label (e.g.,
2705 it is a RETURN insn), search loop->exit_labels
2706 to find its label_ref, and remove it. Also turn
2707 off LABEL_OUTSIDE_LOOP_P bit. */
2708 if (JUMP_LABEL (insn))
2710 for (q = 0, r = this_loop->exit_labels;
2712 q = r, r = LABEL_NEXTREF (r))
2713 if (XEXP (r, 0) == JUMP_LABEL (insn))
2715 LABEL_OUTSIDE_LOOP_P (r) = 0;
2717 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2719 this_loop->exit_labels = LABEL_NEXTREF (r);
2723 for (loop = this_loop; loop && loop != target_loop;
2727 /* If we didn't find it, then something is
2733 /* P is now a jump outside the loop, so it must be put
2734 in loop->exit_labels, and marked as such.
2735 The easiest way to do this is to just call
2736 mark_loop_jump again for P. */
2737 mark_loop_jump (PATTERN (p), this_loop);
2739 /* If INSN now jumps to the insn after it,
2741 if (JUMP_LABEL (insn) != 0
2742 && (next_real_insn (JUMP_LABEL (insn))
2743 == next_real_insn (insn)))
2747 /* Continue the loop after where the conditional
2748 branch used to jump, since the only branch insn
2749 in the block (if it still remains) is an inter-loop
2750 branch and hence needs no processing. */
2751 insn = NEXT_INSN (cond_label);
2753 if (--LABEL_NUSES (cond_label) == 0)
2754 delete_insn (cond_label);
2756 /* This loop will be continued with NEXT_INSN (insn). */
2757 insn = PREV_INSN (insn);
2764 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2765 loops it is contained in, mark the target loop invalid.
2767 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2770 mark_loop_jump (x, loop)
2774 struct loop *dest_loop;
2775 struct loop *outer_loop;
2778 switch (GET_CODE (x))
2791 /* There could be a label reference in here. */
2792 mark_loop_jump (XEXP (x, 0), loop);
2798 mark_loop_jump (XEXP (x, 0), loop);
2799 mark_loop_jump (XEXP (x, 1), loop);
2803 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2804 mark_loop_jump (XEXP (x, 1), loop);
2809 mark_loop_jump (XEXP (x, 0), loop);
2813 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2815 /* Link together all labels that branch outside the loop. This
2816 is used by final_[bg]iv_value and the loop unrolling code. Also
2817 mark this LABEL_REF so we know that this branch should predict
2820 /* A check to make sure the label is not in an inner nested loop,
2821 since this does not count as a loop exit. */
2824 for (outer_loop = dest_loop; outer_loop;
2825 outer_loop = outer_loop->outer)
2826 if (outer_loop == loop)
2832 if (loop && ! outer_loop)
2834 LABEL_OUTSIDE_LOOP_P (x) = 1;
2835 LABEL_NEXTREF (x) = loop->exit_labels;
2836 loop->exit_labels = x;
2838 for (outer_loop = loop;
2839 outer_loop && outer_loop != dest_loop;
2840 outer_loop = outer_loop->outer)
2841 outer_loop->exit_count++;
2844 /* If this is inside a loop, but not in the current loop or one enclosed
2845 by it, it invalidates at least one loop. */
2850 /* We must invalidate every nested loop containing the target of this
2851 label, except those that also contain the jump insn. */
2853 for (; dest_loop; dest_loop = dest_loop->outer)
2855 /* Stop when we reach a loop that also contains the jump insn. */
2856 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2857 if (dest_loop == outer_loop)
2860 /* If we get here, we know we need to invalidate a loop. */
2861 if (loop_dump_stream && ! dest_loop->invalid)
2862 fprintf (loop_dump_stream,
2863 "\nLoop at %d ignored due to multiple entry points.\n",
2864 INSN_UID (dest_loop->start));
2866 dest_loop->invalid = 1;
2871 /* If this is not setting pc, ignore. */
2872 if (SET_DEST (x) == pc_rtx)
2873 mark_loop_jump (SET_SRC (x), loop);
2877 mark_loop_jump (XEXP (x, 1), loop);
2878 mark_loop_jump (XEXP (x, 2), loop);
2883 for (i = 0; i < XVECLEN (x, 0); i++)
2884 mark_loop_jump (XVECEXP (x, 0, i), loop);
2888 for (i = 0; i < XVECLEN (x, 1); i++)
2889 mark_loop_jump (XVECEXP (x, 1, i), loop);
2893 /* Strictly speaking this is not a jump into the loop, only a possible
2894 jump out of the loop. However, we have no way to link the destination
2895 of this jump onto the list of exit labels. To be safe we mark this
2896 loop and any containing loops as invalid. */
2899 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2901 if (loop_dump_stream && ! outer_loop->invalid)
2902 fprintf (loop_dump_stream,
2903 "\nLoop at %d ignored due to unknown exit jump.\n",
2904 INSN_UID (outer_loop->start));
2905 outer_loop->invalid = 1;
2912 /* Return nonzero if there is a label in the range from
2913 insn INSN to and including the insn whose luid is END
2914 INSN must have an assigned luid (i.e., it must not have
2915 been previously created by loop.c). */
2918 labels_in_range_p (insn, end)
2922 while (insn && INSN_LUID (insn) <= end)
2924 if (GET_CODE (insn) == CODE_LABEL)
2926 insn = NEXT_INSN (insn);
2932 /* Record that a memory reference X is being set. */
2935 note_addr_stored (x, y, data)
2937 rtx y ATTRIBUTE_UNUSED;
2938 void *data ATTRIBUTE_UNUSED;
2940 struct loop_info *loop_info = data;
2942 if (x == 0 || GET_CODE (x) != MEM)
2945 /* Count number of memory writes.
2946 This affects heuristics in strength_reduce. */
2947 loop_info->num_mem_sets++;
2949 /* BLKmode MEM means all memory is clobbered. */
2950 if (GET_MODE (x) == BLKmode)
2952 if (RTX_UNCHANGING_P (x))
2953 loop_info->unknown_constant_address_altered = 1;
2955 loop_info->unknown_address_altered = 1;
2960 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2961 loop_info->store_mems);
2964 /* X is a value modified by an INSN that references a biv inside a loop
2965 exit test (ie, X is somehow related to the value of the biv). If X
2966 is a pseudo that is used more than once, then the biv is (effectively)
2967 used more than once. DATA is a pointer to a loop_regs structure. */
2970 note_set_pseudo_multiple_uses (x, y, data)
2972 rtx y ATTRIBUTE_UNUSED;
2975 struct loop_regs *regs = (struct loop_regs *) data;
2980 while (GET_CODE (x) == STRICT_LOW_PART
2981 || GET_CODE (x) == SIGN_EXTRACT
2982 || GET_CODE (x) == ZERO_EXTRACT
2983 || GET_CODE (x) == SUBREG)
2986 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
2989 /* If we do not have usage information, or if we know the register
2990 is used more than once, note that fact for check_dbra_loop. */
2991 if (REGNO (x) >= max_reg_before_loop
2992 || ! regs->array[REGNO (x)].single_usage
2993 || regs->array[REGNO (x)].single_usage == const0_rtx)
2994 regs->multiple_uses = 1;
2997 /* Return nonzero if the rtx X is invariant over the current loop.
2999 The value is 2 if we refer to something only conditionally invariant.
3001 A memory ref is invariant if it is not volatile and does not conflict
3002 with anything stored in `loop_info->store_mems'. */
3005 loop_invariant_p (loop, x)
3006 const struct loop *loop;
3009 struct loop_info *loop_info = LOOP_INFO (loop);
3010 struct loop_regs *regs = LOOP_REGS (loop);
3012 register enum rtx_code code;
3013 register const char *fmt;
3014 int conditional = 0;
3019 code = GET_CODE (x);
3029 /* A LABEL_REF is normally invariant, however, if we are unrolling
3030 loops, and this label is inside the loop, then it isn't invariant.
3031 This is because each unrolled copy of the loop body will have
3032 a copy of this label. If this was invariant, then an insn loading
3033 the address of this label into a register might get moved outside
3034 the loop, and then each loop body would end up using the same label.
3036 We don't know the loop bounds here though, so just fail for all
3038 if (flag_unroll_loops)
3045 case UNSPEC_VOLATILE:
3049 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3050 since the reg might be set by initialization within the loop. */
3052 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3053 || x == arg_pointer_rtx)
3054 && ! current_function_has_nonlocal_goto)
3057 if (LOOP_INFO (loop)->has_call
3058 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3061 if (regs->array[REGNO (x)].set_in_loop < 0)
3064 return regs->array[REGNO (x)].set_in_loop == 0;
3067 /* Volatile memory references must be rejected. Do this before
3068 checking for read-only items, so that volatile read-only items
3069 will be rejected also. */
3070 if (MEM_VOLATILE_P (x))
3073 /* See if there is any dependence between a store and this load. */
3074 mem_list_entry = loop_info->store_mems;
3075 while (mem_list_entry)
3077 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3081 mem_list_entry = XEXP (mem_list_entry, 1);
3084 /* It's not invalidated by a store in memory
3085 but we must still verify the address is invariant. */
3089 /* Don't mess with insns declared volatile. */
3090 if (MEM_VOLATILE_P (x))
3098 fmt = GET_RTX_FORMAT (code);
3099 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3103 int tem = loop_invariant_p (loop, XEXP (x, i));
3109 else if (fmt[i] == 'E')
3112 for (j = 0; j < XVECLEN (x, i); j++)
3114 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3124 return 1 + conditional;
3127 /* Return nonzero if all the insns in the loop that set REG
3128 are INSN and the immediately following insns,
3129 and if each of those insns sets REG in an invariant way
3130 (not counting uses of REG in them).
3132 The value is 2 if some of these insns are only conditionally invariant.
3134 We assume that INSN itself is the first set of REG
3135 and that its source is invariant. */
3138 consec_sets_invariant_p (loop, reg, n_sets, insn)
3139 const struct loop *loop;
3143 struct loop_regs *regs = LOOP_REGS (loop);
3145 unsigned int regno = REGNO (reg);
3147 /* Number of sets we have to insist on finding after INSN. */
3148 int count = n_sets - 1;
3149 int old = regs->array[regno].set_in_loop;
3153 /* If N_SETS hit the limit, we can't rely on its value. */
3157 regs->array[regno].set_in_loop = 0;
3161 register enum rtx_code code;
3165 code = GET_CODE (p);
3167 /* If library call, skip to end of it. */
3168 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3173 && (set = single_set (p))
3174 && GET_CODE (SET_DEST (set)) == REG
3175 && REGNO (SET_DEST (set)) == regno)
3177 this = loop_invariant_p (loop, SET_SRC (set));
3180 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3182 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3183 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3185 this = (CONSTANT_P (XEXP (temp, 0))
3186 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3187 && loop_invariant_p (loop, XEXP (temp, 0))));
3194 else if (code != NOTE)
3196 regs->array[regno].set_in_loop = old;
3201 regs->array[regno].set_in_loop = old;
3202 /* If loop_invariant_p ever returned 2, we return 2. */
3203 return 1 + (value & 2);
3207 /* I don't think this condition is sufficient to allow INSN
3208 to be moved, so we no longer test it. */
3210 /* Return 1 if all insns in the basic block of INSN and following INSN
3211 that set REG are invariant according to TABLE. */
3214 all_sets_invariant_p (reg, insn, table)
3218 register rtx p = insn;
3219 register int regno = REGNO (reg);
3223 register enum rtx_code code;
3225 code = GET_CODE (p);
3226 if (code == CODE_LABEL || code == JUMP_INSN)
3228 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3229 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3230 && REGNO (SET_DEST (PATTERN (p))) == regno)
3232 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3239 /* Look at all uses (not sets) of registers in X. For each, if it is
3240 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3241 a different insn, set USAGE[REGNO] to const0_rtx. */
3244 find_single_use_in_loop (regs, insn, x)
3245 struct loop_regs *regs;
3249 enum rtx_code code = GET_CODE (x);
3250 const char *fmt = GET_RTX_FORMAT (code);
3254 regs->array[REGNO (x)].single_usage
3255 = (regs->array[REGNO (x)].single_usage != 0
3256 && regs->array[REGNO (x)].single_usage != insn)
3257 ? const0_rtx : insn;
3259 else if (code == SET)
3261 /* Don't count SET_DEST if it is a REG; otherwise count things
3262 in SET_DEST because if a register is partially modified, it won't
3263 show up as a potential movable so we don't care how USAGE is set
3265 if (GET_CODE (SET_DEST (x)) != REG)
3266 find_single_use_in_loop (regs, insn, SET_DEST (x));
3267 find_single_use_in_loop (regs, insn, SET_SRC (x));
3270 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3272 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3273 find_single_use_in_loop (regs, insn, XEXP (x, i));
3274 else if (fmt[i] == 'E')
3275 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3276 find_single_use_in_loop (regs, insn, XVECEXP (x, i, j));
3280 /* Count and record any set in X which is contained in INSN. Update
3281 REGS->array[I].MAY_NOT_OPTIMIZE and LAST_SET for any register I set
3285 count_one_set (regs, insn, x, last_set)
3286 struct loop_regs *regs;
3290 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3291 /* Don't move a reg that has an explicit clobber.
3292 It's not worth the pain to try to do it correctly. */
3293 regs->array[REGNO (XEXP (x, 0))].may_not_optimize = 1;
3295 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3297 rtx dest = SET_DEST (x);
3298 while (GET_CODE (dest) == SUBREG
3299 || GET_CODE (dest) == ZERO_EXTRACT
3300 || GET_CODE (dest) == SIGN_EXTRACT
3301 || GET_CODE (dest) == STRICT_LOW_PART)
3302 dest = XEXP (dest, 0);
3303 if (GET_CODE (dest) == REG)
3305 register int regno = REGNO (dest);
3306 /* If this is the first setting of this reg
3307 in current basic block, and it was set before,
3308 it must be set in two basic blocks, so it cannot
3309 be moved out of the loop. */
3310 if (regs->array[regno].set_in_loop > 0
3312 regs->array[regno].may_not_optimize = 1;
3313 /* If this is not first setting in current basic block,
3314 see if reg was used in between previous one and this.
3315 If so, neither one can be moved. */
3316 if (last_set[regno] != 0
3317 && reg_used_between_p (dest, last_set[regno], insn))
3318 regs->array[regno].may_not_optimize = 1;
3319 if (regs->array[regno].set_in_loop < 127)
3320 ++regs->array[regno].set_in_loop;
3321 last_set[regno] = insn;
3326 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3327 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3328 contained in insn INSN is used by any insn that precedes INSN in
3329 cyclic order starting from the loop entry point.
3331 We don't want to use INSN_LUID here because if we restrict INSN to those
3332 that have a valid INSN_LUID, it means we cannot move an invariant out
3333 from an inner loop past two loops. */
3336 loop_reg_used_before_p (loop, set, insn)
3337 const struct loop *loop;
3340 rtx reg = SET_DEST (set);
3343 /* Scan forward checking for register usage. If we hit INSN, we
3344 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3345 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3347 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3357 /* A "basic induction variable" or biv is a pseudo reg that is set
3358 (within this loop) only by incrementing or decrementing it. */
3359 /* A "general induction variable" or giv is a pseudo reg whose
3360 value is a linear function of a biv. */
3362 /* Bivs are recognized by `basic_induction_var';
3363 Givs by `general_induction_var'. */
3365 /* Communication with routines called via `note_stores'. */
3367 static rtx note_insn;
3369 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3371 static rtx addr_placeholder;
3373 /* ??? Unfinished optimizations, and possible future optimizations,
3374 for the strength reduction code. */
3376 /* ??? The interaction of biv elimination, and recognition of 'constant'
3377 bivs, may cause problems. */
3379 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3380 performance problems.
3382 Perhaps don't eliminate things that can be combined with an addressing
3383 mode. Find all givs that have the same biv, mult_val, and add_val;
3384 then for each giv, check to see if its only use dies in a following
3385 memory address. If so, generate a new memory address and check to see
3386 if it is valid. If it is valid, then store the modified memory address,
3387 otherwise, mark the giv as not done so that it will get its own iv. */
3389 /* ??? Could try to optimize branches when it is known that a biv is always
3392 /* ??? When replace a biv in a compare insn, we should replace with closest
3393 giv so that an optimized branch can still be recognized by the combiner,
3394 e.g. the VAX acb insn. */
3396 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3397 was rerun in loop_optimize whenever a register was added or moved.
3398 Also, some of the optimizations could be a little less conservative. */
3400 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3401 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3404 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3405 loop iteration except for the last one.
3407 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3411 for_each_insn_in_loop (loop, fncall)
3413 loop_insn_callback fncall;
3415 /* This is 1 if current insn is not executed at least once for every loop
3417 int not_every_iteration = 0;
3418 int maybe_multiple = 0;
3419 int past_loop_latch = 0;
3423 /* If loop_scan_start points to the loop exit test, we have to be wary of
3424 subversive use of gotos inside expression statements. */
3425 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3426 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3428 /* Scan through loop to find all possible bivs. */
3430 for (p = next_insn_in_loop (loop, loop->scan_start);
3432 p = next_insn_in_loop (loop, p))
3434 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3436 /* Past CODE_LABEL, we get to insns that may be executed multiple
3437 times. The only way we can be sure that they can't is if every
3438 jump insn between here and the end of the loop either
3439 returns, exits the loop, is a jump to a location that is still
3440 behind the label, or is a jump to the loop start. */
3442 if (GET_CODE (p) == CODE_LABEL)
3450 insn = NEXT_INSN (insn);
3451 if (insn == loop->scan_start)
3453 if (insn == loop->end)
3459 if (insn == loop->scan_start)
3463 if (GET_CODE (insn) == JUMP_INSN
3464 && GET_CODE (PATTERN (insn)) != RETURN
3465 && (!any_condjump_p (insn)
3466 || (JUMP_LABEL (insn) != 0
3467 && JUMP_LABEL (insn) != loop->scan_start
3468 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3476 /* Past a jump, we get to insns for which we can't count
3477 on whether they will be executed during each iteration. */
3478 /* This code appears twice in strength_reduce. There is also similar
3479 code in scan_loop. */
3480 if (GET_CODE (p) == JUMP_INSN
3481 /* If we enter the loop in the middle, and scan around to the
3482 beginning, don't set not_every_iteration for that.
3483 This can be any kind of jump, since we want to know if insns
3484 will be executed if the loop is executed. */
3485 && !(JUMP_LABEL (p) == loop->top
3486 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3487 && any_uncondjump_p (p))
3488 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3492 /* If this is a jump outside the loop, then it also doesn't
3493 matter. Check to see if the target of this branch is on the
3494 loop->exits_labels list. */
3496 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3497 if (XEXP (label, 0) == JUMP_LABEL (p))
3501 not_every_iteration = 1;
3504 else if (GET_CODE (p) == NOTE)
3506 /* At the virtual top of a converted loop, insns are again known to
3507 be executed each iteration: logically, the loop begins here
3508 even though the exit code has been duplicated.
3510 Insns are also again known to be executed each iteration at
3511 the LOOP_CONT note. */
3512 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3513 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3515 not_every_iteration = 0;
3516 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3518 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3522 /* Note if we pass a loop latch. If we do, then we can not clear
3523 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3524 a loop since a jump before the last CODE_LABEL may have started
3525 a new loop iteration.
3527 Note that LOOP_TOP is only set for rotated loops and we need
3528 this check for all loops, so compare against the CODE_LABEL
3529 which immediately follows LOOP_START. */
3530 if (GET_CODE (p) == JUMP_INSN
3531 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3532 past_loop_latch = 1;
3534 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3535 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3536 or not an insn is known to be executed each iteration of the
3537 loop, whether or not any iterations are known to occur.
3539 Therefore, if we have just passed a label and have no more labels
3540 between here and the test insn of the loop, and we have not passed
3541 a jump to the top of the loop, then we know these insns will be
3542 executed each iteration. */
3544 if (not_every_iteration
3546 && GET_CODE (p) == CODE_LABEL
3547 && no_labels_between_p (p, loop->end)
3548 && loop_insn_first_p (p, loop->cont))
3549 not_every_iteration = 0;
3554 loop_bivs_find (loop)
3557 struct loop_regs *regs = LOOP_REGS (loop);
3558 struct loop_ivs *ivs = LOOP_IVS (loop);
3559 /* Temporary list pointers for traversing ivs->list. */
3560 struct iv_class *bl, **backbl;
3564 for_each_insn_in_loop (loop, check_insn_for_bivs);
3566 /* Scan ivs->list to remove all regs that proved not to be bivs.
3567 Make a sanity check against regs->n_times_set. */
3568 for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
3570 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3571 /* Above happens if register modified by subreg, etc. */
3572 /* Make sure it is not recognized as a basic induction var: */
3573 || regs->array[bl->regno].n_times_set != bl->biv_count
3574 /* If never incremented, it is invariant that we decided not to
3575 move. So leave it alone. */
3576 || ! bl->incremented)
3578 if (loop_dump_stream)
3579 fprintf (loop_dump_stream, "Biv %d: discarded, %s\n",
3581 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3582 ? "not induction variable"
3583 : (! bl->incremented ? "never incremented"
3586 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3593 if (loop_dump_stream)
3594 fprintf (loop_dump_stream, "Biv %d: verified\n", bl->regno);
3600 /* Determine how BIVS are initialised by looking through pre-header
3601 extended basic block. */
3603 loop_bivs_init_find (loop)
3606 struct loop_ivs *ivs = LOOP_IVS (loop);
3607 /* Temporary list pointers for traversing ivs->list. */
3608 struct iv_class *bl;
3612 /* Find initial value for each biv by searching backwards from loop_start,
3613 halting at first label. Also record any test condition. */
3616 for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3622 if (GET_CODE (p) == CALL_INSN)
3626 note_stores (PATTERN (p), record_initial, ivs);
3628 /* Record any test of a biv that branches around the loop if no store
3629 between it and the start of loop. We only care about tests with
3630 constants and registers and only certain of those. */
3631 if (GET_CODE (p) == JUMP_INSN
3632 && JUMP_LABEL (p) != 0
3633 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
3634 && (test = get_condition_for_loop (loop, p)) != 0
3635 && GET_CODE (XEXP (test, 0)) == REG
3636 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3637 && (bl = REG_IV_CLASS (ivs, REGNO (XEXP (test, 0)))) != 0
3638 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop->start)
3639 && bl->init_insn == 0)
3641 /* If an NE test, we have an initial value! */
3642 if (GET_CODE (test) == NE)
3645 bl->init_set = gen_rtx_SET (VOIDmode,
3646 XEXP (test, 0), XEXP (test, 1));
3649 bl->initial_test = test;
3655 /* Look at the each biv and see if we can say anything better about its
3656 initial value from any initializing insns set up above. (This is done
3657 in two passes to avoid missing SETs in a PARALLEL.) */
3659 loop_bivs_check (loop)
3662 struct loop_ivs *ivs = LOOP_IVS (loop);
3663 /* Temporary list pointers for traversing ivs->list. */
3664 struct iv_class *bl;
3665 struct iv_class **backbl;
3667 for (backbl = &ivs->list; (bl = *backbl); backbl = &bl->next)
3672 if (! bl->init_insn)
3675 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3676 is a constant, use the value of that. */
3677 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3678 && CONSTANT_P (XEXP (note, 0)))
3679 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3680 && CONSTANT_P (XEXP (note, 0))))
3681 src = XEXP (note, 0);
3683 src = SET_SRC (bl->init_set);
3685 if (loop_dump_stream)
3686 fprintf (loop_dump_stream,
3687 "Biv %d: initialized at insn %d: initial value ",
3688 bl->regno, INSN_UID (bl->init_insn));
3690 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3691 || GET_MODE (src) == VOIDmode)
3692 && valid_initial_value_p (src, bl->init_insn,
3693 LOOP_INFO (loop)->pre_header_has_call,
3696 bl->initial_value = src;
3698 if (loop_dump_stream)
3700 print_simple_rtl (loop_dump_stream, src);
3701 fputc ('\n', loop_dump_stream);
3704 /* If we can't make it a giv,
3705 let biv keep initial value of "itself". */
3706 else if (loop_dump_stream)
3707 fprintf (loop_dump_stream, "is complex\n");
3712 /* Search the loop for general induction variables. */
3715 loop_givs_find (loop)
3718 for_each_insn_in_loop (loop, check_insn_for_givs);
3722 /* For each giv for which we still don't know whether or not it is
3723 replaceable, check to see if it is replaceable because its final value
3724 can be calculated. */
3727 loop_givs_check (loop)
3730 struct loop_ivs *ivs = LOOP_IVS (loop);
3731 struct iv_class *bl;
3733 for (bl = ivs->list; bl; bl = bl->next)
3735 struct induction *v;
3737 for (v = bl->giv; v; v = v->next_iv)
3738 if (! v->replaceable && ! v->not_replaceable)
3739 check_final_value (loop, v);
3744 /* Return non-zero if it is possible to eliminate the biv BL provided
3745 all givs are reduced. This is possible if either the reg is not
3746 used outside the loop, or we can compute what its final value will
3750 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3752 struct iv_class *bl;
3756 /* For architectures with a decrement_and_branch_until_zero insn,
3757 don't do this if we put a REG_NONNEG note on the endtest for this
3760 #ifdef HAVE_decrement_and_branch_until_zero
3763 if (loop_dump_stream)
3764 fprintf (loop_dump_stream,
3765 "Cannot eliminate nonneg biv %d.\n", bl->regno);
3770 /* Check that biv is used outside loop or if it has a final value.
3771 Compare against bl->init_insn rather than loop->start. We aren't
3772 concerned with any uses of the biv between init_insn and
3773 loop->start since these won't be affected by the value of the biv
3774 elsewhere in the function, so long as init_insn doesn't use the
3777 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3779 && INSN_UID (bl->init_insn) < max_uid_for_loop
3780 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3781 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3782 || (bl->final_value = final_biv_value (loop, bl)))
3783 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3785 if (loop_dump_stream)
3787 fprintf (loop_dump_stream,
3788 "Cannot eliminate biv %d.\n",
3790 fprintf (loop_dump_stream,
3791 "First use: insn %d, last use: insn %d.\n",
3792 REGNO_FIRST_UID (bl->regno),
3793 REGNO_LAST_UID (bl->regno));
3799 /* Reduce each giv of BL that we have decided to reduce. */
3802 loop_givs_reduce (loop, bl)
3804 struct iv_class *bl;
3806 struct induction *v;
3808 for (v = bl->giv; v; v = v->next_iv)
3810 struct induction *tv;
3811 if (! v->ignore && v->same == 0)
3813 int auto_inc_opt = 0;
3815 /* If the code for derived givs immediately below has already
3816 allocated a new_reg, we must keep it. */
3818 v->new_reg = gen_reg_rtx (v->mode);
3821 /* If the target has auto-increment addressing modes, and
3822 this is an address giv, then try to put the increment
3823 immediately after its use, so that flow can create an
3824 auto-increment addressing mode. */
3825 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
3826 && bl->biv->always_executed && ! bl->biv->maybe_multiple
3827 /* We don't handle reversed biv's because bl->biv->insn
3828 does not have a valid INSN_LUID. */
3830 && v->always_executed && ! v->maybe_multiple
3831 && INSN_UID (v->insn) < max_uid_for_loop)
3833 /* If other giv's have been combined with this one, then
3834 this will work only if all uses of the other giv's occur
3835 before this giv's insn. This is difficult to check.
3837 We simplify this by looking for the common case where
3838 there is one DEST_REG giv, and this giv's insn is the
3839 last use of the dest_reg of that DEST_REG giv. If the
3840 increment occurs after the address giv, then we can
3841 perform the optimization. (Otherwise, the increment
3842 would have to go before other_giv, and we would not be
3843 able to combine it with the address giv to get an
3844 auto-inc address.) */
3845 if (v->combined_with)
3847 struct induction *other_giv = 0;
3849 for (tv = bl->giv; tv; tv = tv->next_iv)
3857 if (! tv && other_giv
3858 && REGNO (other_giv->dest_reg) < max_reg_before_loop
3859 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
3860 == INSN_UID (v->insn))
3861 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
3864 /* Check for case where increment is before the address
3865 giv. Do this test in "loop order". */
3866 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
3867 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3868 || (INSN_LUID (bl->biv->insn)
3869 > INSN_LUID (loop->scan_start))))
3870 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3871 && (INSN_LUID (loop->scan_start)
3872 < INSN_LUID (bl->biv->insn))))
3881 /* We can't put an insn immediately after one setting
3882 cc0, or immediately before one using cc0. */
3883 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
3884 || (auto_inc_opt == -1
3885 && (prev = prev_nonnote_insn (v->insn)) != 0
3887 && sets_cc0_p (PATTERN (prev))))
3893 v->auto_inc_opt = 1;
3897 /* For each place where the biv is incremented, add an insn
3898 to increment the new, reduced reg for the giv. */
3899 for (tv = bl->biv; tv; tv = tv->next_iv)
3904 insert_before = tv->insn;
3905 else if (auto_inc_opt == 1)
3906 insert_before = NEXT_INSN (v->insn);
3908 insert_before = v->insn;
3910 if (tv->mult_val == const1_rtx)
3911 emit_iv_add_mult (tv->add_val, v->mult_val,
3912 v->new_reg, v->new_reg, insert_before);
3913 else /* tv->mult_val == const0_rtx */
3914 /* A multiply is acceptable here
3915 since this is presumed to be seldom executed. */
3916 emit_iv_add_mult (tv->add_val, v->mult_val,
3917 v->add_val, v->new_reg, insert_before);
3920 /* Add code at loop start to initialize giv's reduced reg. */
3922 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
3923 v->mult_val, v->add_val, v->new_reg,
3930 /* Check for givs whose first use is their definition and whose
3931 last use is the definition of another giv. If so, it is likely
3932 dead and should not be used to derive another giv nor to
3936 loop_givs_dead_check (loop, bl)
3937 struct loop *loop ATTRIBUTE_UNUSED;
3938 struct iv_class *bl;
3940 struct induction *v;
3942 for (v = bl->giv; v; v = v->next_iv)
3945 || (v->same && v->same->ignore))
3948 if (v->giv_type == DEST_REG
3949 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
3951 struct induction *v1;
3953 for (v1 = bl->giv; v1; v1 = v1->next_iv)
3954 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
3962 loop_givs_rescan (loop, bl, reg_map, end_insert_before)
3964 struct iv_class *bl;
3966 rtx end_insert_before;
3968 struct induction *v;
3970 for (v = bl->giv; v; v = v->next_iv)
3972 if (v->same && v->same->ignore)
3978 /* Update expression if this was combined, in case other giv was
3981 v->new_reg = replace_rtx (v->new_reg,
3982 v->same->dest_reg, v->same->new_reg);
3984 /* See if this register is known to be a pointer to something. If
3985 so, see if we can find the alignment. First see if there is a
3986 destination register that is a pointer. If so, this shares the
3987 alignment too. Next see if we can deduce anything from the
3988 computational information. If not, and this is a DEST_ADDR
3989 giv, at least we know that it's a pointer, though we don't know
3991 if (GET_CODE (v->new_reg) == REG
3992 && v->giv_type == DEST_REG
3993 && REG_POINTER (v->dest_reg))
3994 mark_reg_pointer (v->new_reg,
3995 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
3996 else if (GET_CODE (v->new_reg) == REG
3997 && REG_POINTER (v->src_reg))
3999 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4002 || GET_CODE (v->add_val) != CONST_INT
4003 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4006 mark_reg_pointer (v->new_reg, align);
4008 else if (GET_CODE (v->new_reg) == REG
4009 && GET_CODE (v->add_val) == REG
4010 && REG_POINTER (v->add_val))
4012 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4014 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4015 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4018 mark_reg_pointer (v->new_reg, align);
4020 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4021 mark_reg_pointer (v->new_reg, 0);
4023 if (v->giv_type == DEST_ADDR)
4024 /* Store reduced reg as the address in the memref where we found
4026 validate_change (v->insn, v->location, v->new_reg, 0);
4027 else if (v->replaceable)
4029 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4033 /* Not replaceable; emit an insn to set the original giv reg from
4034 the reduced giv, same as above. */
4035 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4039 /* When a loop is reversed, givs which depend on the reversed
4040 biv, and which are live outside the loop, must be set to their
4041 correct final value. This insn is only needed if the giv is
4042 not replaceable. The correct final value is the same as the
4043 value that the giv starts the reversed loop with. */
4044 if (bl->reversed && ! v->replaceable)
4045 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4046 v->mult_val, v->add_val, v->dest_reg,
4048 else if (v->final_value)
4050 /* If the loop has multiple exits, emit the insn before the
4051 loop to ensure that it will always be executed no matter
4052 how the loop exits. Otherwise, emit the insn after the loop,
4053 since this is slightly more efficient. */
4054 if (loop->exit_count)
4055 loop_insn_hoist (loop,
4056 gen_move_insn (v->dest_reg, v->final_value));
4058 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4062 if (loop_dump_stream)
4064 fprintf (loop_dump_stream, "giv at %d reduced to ",
4065 INSN_UID (v->insn));
4066 print_simple_rtl (loop_dump_stream, v->new_reg);
4067 fprintf (loop_dump_stream, "\n");
4074 loop_giv_reduce_benefit (loop, bl, v, test_reg)
4075 struct loop *loop ATTRIBUTE_UNUSED;
4076 struct iv_class *bl;
4077 struct induction *v;
4083 benefit = v->benefit;
4084 PUT_MODE (test_reg, v->mode);
4085 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4086 test_reg, test_reg);
4088 /* Reduce benefit if not replaceable, since we will insert a
4089 move-insn to replace the insn that calculates this giv. Don't do
4090 this unless the giv is a user variable, since it will often be
4091 marked non-replaceable because of the duplication of the exit
4092 code outside the loop. In such a case, the copies we insert are
4093 dead and will be deleted. So they don't have a cost. Similar
4094 situations exist. */
4095 /* ??? The new final_[bg]iv_value code does a much better job of
4096 finding replaceable giv's, and hence this code may no longer be
4098 if (! v->replaceable && ! bl->eliminable
4099 && REG_USERVAR_P (v->dest_reg))
4100 benefit -= copy_cost;
4102 /* Decrease the benefit to count the add-insns that we will insert
4103 to increment the reduced reg for the giv. ??? This can
4104 overestimate the run-time cost of the additional insns, e.g. if
4105 there are multiple basic blocks that increment the biv, but only
4106 one of these blocks is executed during each iteration. There is
4107 no good way to detect cases like this with the current structure
4108 of the loop optimizer. This code is more accurate for
4109 determining code size than run-time benefits. */
4110 benefit -= add_cost * bl->biv_count;
4112 /* Decide whether to strength-reduce this giv or to leave the code
4113 unchanged (recompute it from the biv each time it is used). This
4114 decision can be made independently for each giv. */
4117 /* Attempt to guess whether autoincrement will handle some of the
4118 new add insns; if so, increase BENEFIT (undo the subtraction of
4119 add_cost that was done above). */
4120 if (v->giv_type == DEST_ADDR
4121 /* Increasing the benefit is risky, since this is only a guess.
4122 Avoid increasing register pressure in cases where there would
4123 be no other benefit from reducing this giv. */
4125 && GET_CODE (v->mult_val) == CONST_INT)
4127 if (HAVE_POST_INCREMENT
4128 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4129 benefit += add_cost * bl->biv_count;
4130 else if (HAVE_PRE_INCREMENT
4131 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4132 benefit += add_cost * bl->biv_count;
4133 else if (HAVE_POST_DECREMENT
4134 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4135 benefit += add_cost * bl->biv_count;
4136 else if (HAVE_PRE_DECREMENT
4137 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4138 benefit += add_cost * bl->biv_count;
4146 /* Free IV structures for LOOP. */
4149 loop_ivs_free (loop)
4152 struct loop_ivs *ivs = LOOP_IVS (loop);
4153 struct iv_class *iv = ivs->list;
4159 struct iv_class *next = iv->next;
4160 struct induction *induction;
4161 struct induction *next_induction;
4163 for (induction = iv->biv; induction; induction = next_induction)
4165 next_induction = induction->next_iv;
4168 for (induction = iv->giv; induction; induction = next_induction)
4170 next_induction = induction->next_iv;
4180 /* Perform strength reduction and induction variable elimination.
4182 Pseudo registers created during this function will be beyond the
4183 last valid index in several tables including
4184 REGS->ARRAY[I].N_TIMES_SET and REGNO_LAST_UID. This does not cause a
4185 problem here, because the added registers cannot be givs outside of
4186 their loop, and hence will never be reconsidered. But scan_loop
4187 must check regnos to make sure they are in bounds. */
4190 strength_reduce (loop, insn_count, flags)
4195 struct loop_info *loop_info = LOOP_INFO (loop);
4196 struct loop_regs *regs = LOOP_REGS (loop);
4197 struct loop_ivs *ivs = LOOP_IVS (loop);
4199 /* Temporary list pointer for traversing ivs->list. */
4200 struct iv_class *bl;
4201 /* Ratio of extra register life span we can justify
4202 for saving an instruction. More if loop doesn't call subroutines
4203 since in that case saving an insn makes more difference
4204 and more registers are available. */
4205 /* ??? could set this to last value of threshold in move_movables */
4206 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
4207 /* Map of pseudo-register replacements. */
4208 rtx *reg_map = NULL;
4210 rtx end_insert_before;
4211 int unrolled_insn_copies = 0;
4212 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
4214 addr_placeholder = gen_reg_rtx (Pmode);
4216 /* Save insn immediately after the loop_end. Insns inserted after loop_end
4217 must be put before this insn, so that they will appear in the right
4218 order (i.e. loop order).
4220 If loop_end is the end of the current function, then emit a
4221 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
4223 if (NEXT_INSN (loop->end) != 0)
4224 end_insert_before = NEXT_INSN (loop->end);
4226 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop->end);
4228 ivs->n_regs = max_reg_before_loop;
4229 ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
4231 /* Find all BIVs in loop. */
4232 loop_bivs_find (loop);
4234 /* Exit if there are no bivs. */
4237 /* Can still unroll the loop anyways, but indicate that there is no
4238 strength reduction info available. */
4239 if (flags & LOOP_UNROLL)
4240 unroll_loop (loop, insn_count, end_insert_before, 0);
4242 loop_ivs_free (loop);
4246 /* Determine how BIVS are initialised by looking through pre-header
4247 extended basic block. */
4248 loop_bivs_init_find (loop);
4250 /* Look at the each biv and see if we can say anything better about its
4251 initial value from any initializing insns set up above. */
4252 loop_bivs_check (loop);
4254 /* Search the loop for general induction variables. */
4255 loop_givs_find (loop);
4257 /* Try to calculate and save the number of loop iterations. This is
4258 set to zero if the actual number can not be calculated. This must
4259 be called after all giv's have been identified, since otherwise it may
4260 fail if the iteration variable is a giv. */
4261 loop_iterations (loop);
4263 /* Now for each giv for which we still don't know whether or not it is
4264 replaceable, check to see if it is replaceable because its final value
4265 can be calculated. This must be done after loop_iterations is called,
4266 so that final_giv_value will work correctly. */
4267 loop_givs_check (loop);
4269 /* Try to prove that the loop counter variable (if any) is always
4270 nonnegative; if so, record that fact with a REG_NONNEG note
4271 so that "decrement and branch until zero" insn can be used. */
4272 check_dbra_loop (loop, insn_count);
4274 /* Create reg_map to hold substitutions for replaceable giv regs.
4275 Some givs might have been made from biv increments, so look at
4276 ivs->reg_iv_type for a suitable size. */
4277 reg_map_size = ivs->n_regs;
4278 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
4280 /* Examine each iv class for feasibility of strength reduction/induction
4281 variable elimination. */
4283 for (bl = ivs->list; bl; bl = bl->next)
4285 struct induction *v;
4288 /* Test whether it will be possible to eliminate this biv
4289 provided all givs are reduced. */
4290 bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
4292 /* Check each extension dependent giv in this class to see if its
4293 root biv is safe from wrapping in the interior mode. */
4294 check_ext_dependant_givs (bl, loop_info);
4296 /* Combine all giv's for this iv_class. */
4297 combine_givs (regs, bl);
4299 /* This will be true at the end, if all givs which depend on this
4300 biv have been strength reduced.
4301 We can't (currently) eliminate the biv unless this is so. */
4302 bl->all_reduced = 1;
4304 for (v = bl->giv; v; v = v->next_iv)
4306 struct induction *tv;
4308 if (v->ignore || v->same)
4311 benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
4313 /* If an insn is not to be strength reduced, then set its ignore
4314 flag, and clear bl->all_reduced. */
4316 /* A giv that depends on a reversed biv must be reduced if it is
4317 used after the loop exit, otherwise, it would have the wrong
4318 value after the loop exit. To make it simple, just reduce all
4319 of such giv's whether or not we know they are used after the loop
4322 if (! flag_reduce_all_givs
4323 && v->lifetime * threshold * benefit < insn_count
4326 if (loop_dump_stream)
4327 fprintf (loop_dump_stream,
4328 "giv of insn %d not worth while, %d vs %d.\n",
4330 v->lifetime * threshold * benefit, insn_count);
4332 bl->all_reduced = 0;
4336 /* Check that we can increment the reduced giv without a
4337 multiply insn. If not, reject it. */
4339 for (tv = bl->biv; tv; tv = tv->next_iv)
4340 if (tv->mult_val == const1_rtx
4341 && ! product_cheap_p (tv->add_val, v->mult_val))
4343 if (loop_dump_stream)
4344 fprintf (loop_dump_stream,
4345 "giv of insn %d: would need a multiply.\n",
4346 INSN_UID (v->insn));
4348 bl->all_reduced = 0;
4354 /* Check for givs whose first use is their definition and whose
4355 last use is the definition of another giv. If so, it is likely
4356 dead and should not be used to derive another giv nor to
4358 loop_givs_dead_check (loop, bl);
4360 /* Reduce each giv that we decided to reduce. */
4361 loop_givs_reduce (loop, bl);
4363 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4366 For each giv register that can be reduced now: if replaceable,
4367 substitute reduced reg wherever the old giv occurs;
4368 else add new move insn "giv_reg = reduced_reg". */
4369 loop_givs_rescan (loop, bl, reg_map, end_insert_before);
4371 /* All the givs based on the biv bl have been reduced if they
4374 /* For each giv not marked as maybe dead that has been combined with a
4375 second giv, clear any "maybe dead" mark on that second giv.
4376 v->new_reg will either be or refer to the register of the giv it
4379 Doing this clearing avoids problems in biv elimination where
4380 a giv's new_reg is a complex value that can't be put in the
4381 insn but the giv combined with (with a reg as new_reg) is
4382 marked maybe_dead. Since the register will be used in either
4383 case, we'd prefer it be used from the simpler giv. */
4385 for (v = bl->giv; v; v = v->next_iv)
4386 if (! v->maybe_dead && v->same)
4387 v->same->maybe_dead = 0;
4389 /* Try to eliminate the biv, if it is a candidate.
4390 This won't work if ! bl->all_reduced,
4391 since the givs we planned to use might not have been reduced.
4393 We have to be careful that we didn't initially think we could
4394 eliminate this biv because of a giv that we now think may be
4395 dead and shouldn't be used as a biv replacement.
4397 Also, there is the possibility that we may have a giv that looks
4398 like it can be used to eliminate a biv, but the resulting insn
4399 isn't valid. This can happen, for example, on the 88k, where a
4400 JUMP_INSN can compare a register only with zero. Attempts to
4401 replace it with a compare with a constant will fail.
4403 Note that in cases where this call fails, we may have replaced some
4404 of the occurrences of the biv with a giv, but no harm was done in
4405 doing so in the rare cases where it can occur. */
4407 if (bl->all_reduced == 1 && bl->eliminable
4408 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4410 /* ?? If we created a new test to bypass the loop entirely,
4411 or otherwise drop straight in, based on this test, then
4412 we might want to rewrite it also. This way some later
4413 pass has more hope of removing the initialization of this
4416 /* If final_value != 0, then the biv may be used after loop end
4417 and we must emit an insn to set it just in case.
4419 Reversed bivs already have an insn after the loop setting their
4420 value, so we don't need another one. We can't calculate the
4421 proper final value for such a biv here anyways. */
4422 if (bl->final_value && ! bl->reversed)
4426 /* If the loop has multiple exits, emit the insn before the
4427 loop to ensure that it will always be executed no matter
4428 how the loop exits. Otherwise, emit the insn after the
4429 loop, since this is slightly more efficient. */
4430 if (loop->exit_count)
4431 insert_before = loop->start;
4433 insert_before = end_insert_before;
4435 emit_insn_before (gen_move_insn (bl->biv->dest_reg,
4440 if (loop_dump_stream)
4441 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4446 /* Go through all the instructions in the loop, making all the
4447 register substitutions scheduled in REG_MAP. */
4449 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
4450 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4451 || GET_CODE (p) == CALL_INSN)
4453 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4454 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4458 if (loop_info->n_iterations > 0)
4460 /* When we completely unroll a loop we will likely not need the increment
4461 of the loop BIV and we will not need the conditional branch at the
4463 unrolled_insn_copies = insn_count - 2;
4466 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4467 need the comparison before the conditional branch at the end of the
4469 unrolled_insn_copies -= 1;
4472 /* We'll need one copy for each loop iteration. */
4473 unrolled_insn_copies *= loop_info->n_iterations;
4475 /* A little slop to account for the ability to remove initialization
4476 code, better CSE, and other secondary benefits of completely
4477 unrolling some loops. */
4478 unrolled_insn_copies -= 1;
4480 /* Clamp the value. */
4481 if (unrolled_insn_copies < 0)
4482 unrolled_insn_copies = 0;
4485 /* Unroll loops from within strength reduction so that we can use the
4486 induction variable information that strength_reduce has already
4487 collected. Always unroll loops that would be as small or smaller
4488 unrolled than when rolled. */
4489 if ((flags & LOOP_UNROLL)
4490 || (loop_info->n_iterations > 0
4491 && unrolled_insn_copies <= insn_count))
4492 unroll_loop (loop, insn_count, end_insert_before, 1);
4494 #ifdef HAVE_doloop_end
4495 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4496 doloop_optimize (loop);
4497 #endif /* HAVE_doloop_end */
4499 if (loop_dump_stream)
4500 fprintf (loop_dump_stream, "\n");
4502 loop_ivs_free (loop);
4507 /*Record all basic induction variables calculated in the insn. */
4509 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4512 int not_every_iteration;
4515 struct loop_ivs *ivs = LOOP_IVS (loop);
4522 if (GET_CODE (p) == INSN
4523 && (set = single_set (p))
4524 && GET_CODE (SET_DEST (set)) == REG)
4526 dest_reg = SET_DEST (set);
4527 if (REGNO (dest_reg) < max_reg_before_loop
4528 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4529 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4531 if (basic_induction_var (loop, SET_SRC (set),
4532 GET_MODE (SET_SRC (set)),
4533 dest_reg, p, &inc_val, &mult_val,
4536 /* It is a possible basic induction variable.
4537 Create and initialize an induction structure for it. */
4540 = (struct induction *) xmalloc (sizeof (struct induction));
4542 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4543 not_every_iteration, maybe_multiple);
4544 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4546 else if (REGNO (dest_reg) < ivs->n_regs)
4547 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4553 /* Record all givs calculated in the insn.
4554 A register is a giv if: it is only set once, it is a function of a
4555 biv and a constant (or invariant), and it is not a biv. */
4557 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4560 int not_every_iteration;
4563 struct loop_regs *regs = LOOP_REGS (loop);
4566 /* Look for a general induction variable in a register. */
4567 if (GET_CODE (p) == INSN
4568 && (set = single_set (p))
4569 && GET_CODE (SET_DEST (set)) == REG
4570 && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
4579 rtx last_consec_insn;
4581 dest_reg = SET_DEST (set);
4582 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4585 if (/* SET_SRC is a giv. */
4586 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4587 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4588 /* Equivalent expression is a giv. */
4589 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4590 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4591 &add_val, &mult_val, &ext_val, 0,
4592 &benefit, VOIDmode)))
4593 /* Don't try to handle any regs made by loop optimization.
4594 We have nothing on them in regno_first_uid, etc. */
4595 && REGNO (dest_reg) < max_reg_before_loop
4596 /* Don't recognize a BASIC_INDUCT_VAR here. */
4597 && dest_reg != src_reg
4598 /* This must be the only place where the register is set. */
4599 && (regs->array[REGNO (dest_reg)].n_times_set == 1
4600 /* or all sets must be consecutive and make a giv. */
4601 || (benefit = consec_sets_giv (loop, benefit, p,
4603 &add_val, &mult_val, &ext_val,
4604 &last_consec_insn))))
4607 = (struct induction *) xmalloc (sizeof (struct induction));
4609 /* If this is a library call, increase benefit. */
4610 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4611 benefit += libcall_benefit (p);
4613 /* Skip the consecutive insns, if there are any. */
4614 if (regs->array[REGNO (dest_reg)].n_times_set != 1)
4615 p = last_consec_insn;
4617 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4618 ext_val, benefit, DEST_REG, not_every_iteration,
4619 maybe_multiple, NULL_PTR);
4624 #ifndef DONT_REDUCE_ADDR
4625 /* Look for givs which are memory addresses. */
4626 /* This resulted in worse code on a VAX 8600. I wonder if it
4628 if (GET_CODE (p) == INSN)
4629 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4633 /* Update the status of whether giv can derive other givs. This can
4634 change when we pass a label or an insn that updates a biv. */
4635 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4636 || GET_CODE (p) == CODE_LABEL)
4637 update_giv_derive (loop, p);
4641 /* Return 1 if X is a valid source for an initial value (or as value being
4642 compared against in an initial test).
4644 X must be either a register or constant and must not be clobbered between
4645 the current insn and the start of the loop.
4647 INSN is the insn containing X. */
4650 valid_initial_value_p (x, insn, call_seen, loop_start)
4659 /* Only consider pseudos we know about initialized in insns whose luids
4661 if (GET_CODE (x) != REG
4662 || REGNO (x) >= max_reg_before_loop)
4665 /* Don't use call-clobbered registers across a call which clobbers it. On
4666 some machines, don't use any hard registers at all. */
4667 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4668 && (SMALL_REGISTER_CLASSES
4669 || (call_used_regs[REGNO (x)] && call_seen)))
4672 /* Don't use registers that have been clobbered before the start of the
4674 if (reg_set_between_p (x, insn, loop_start))
4680 /* Scan X for memory refs and check each memory address
4681 as a possible giv. INSN is the insn whose pattern X comes from.
4682 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4683 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4684 more thanonce in each loop iteration. */
4687 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4688 const struct loop *loop;
4691 int not_every_iteration, maybe_multiple;
4694 register enum rtx_code code;
4695 register const char *fmt;
4700 code = GET_CODE (x);
4725 /* This code used to disable creating GIVs with mult_val == 1 and
4726 add_val == 0. However, this leads to lost optimizations when
4727 it comes time to combine a set of related DEST_ADDR GIVs, since
4728 this one would not be seen. */
4730 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4731 &mult_val, &ext_val, 1, &benefit,
4734 /* Found one; record it. */
4736 = (struct induction *) xmalloc (sizeof (struct induction));
4738 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4739 add_val, ext_val, benefit, DEST_ADDR,
4740 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4742 v->mem_mode = GET_MODE (x);
4751 /* Recursively scan the subexpressions for other mem refs. */
4753 fmt = GET_RTX_FORMAT (code);
4754 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4756 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4758 else if (fmt[i] == 'E')
4759 for (j = 0; j < XVECLEN (x, i); j++)
4760 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4764 /* Fill in the data about one biv update.
4765 V is the `struct induction' in which we record the biv. (It is
4766 allocated by the caller, with alloca.)
4767 INSN is the insn that sets it.
4768 DEST_REG is the biv's reg.
4770 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4771 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4772 being set to INC_VAL.
4774 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4775 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4776 can be executed more than once per iteration. If MAYBE_MULTIPLE
4777 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4778 executed exactly once per iteration. */
4781 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4782 not_every_iteration, maybe_multiple)
4784 struct induction *v;
4790 int not_every_iteration;
4793 struct loop_ivs *ivs = LOOP_IVS (loop);
4794 struct iv_class *bl;
4797 v->src_reg = dest_reg;
4798 v->dest_reg = dest_reg;
4799 v->mult_val = mult_val;
4800 v->add_val = inc_val;
4801 v->ext_dependant = NULL_RTX;
4802 v->location = location;
4803 v->mode = GET_MODE (dest_reg);
4804 v->always_computable = ! not_every_iteration;
4805 v->always_executed = ! not_every_iteration;
4806 v->maybe_multiple = maybe_multiple;
4808 /* Add this to the reg's iv_class, creating a class
4809 if this is the first incrementation of the reg. */
4811 bl = REG_IV_CLASS (ivs, REGNO (dest_reg));
4814 /* Create and initialize new iv_class. */
4816 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4818 bl->regno = REGNO (dest_reg);
4824 /* Set initial value to the reg itself. */
4825 bl->initial_value = dest_reg;
4826 bl->final_value = 0;
4827 /* We haven't seen the initializing insn yet */
4830 bl->initial_test = 0;
4831 bl->incremented = 0;
4835 bl->total_benefit = 0;
4837 /* Add this class to ivs->list. */
4838 bl->next = ivs->list;
4841 /* Put it in the array of biv register classes. */
4842 REG_IV_CLASS (ivs, REGNO (dest_reg)) = bl;
4845 /* Update IV_CLASS entry for this biv. */
4846 v->next_iv = bl->biv;
4849 if (mult_val == const1_rtx)
4850 bl->incremented = 1;
4852 if (loop_dump_stream)
4853 loop_biv_dump (v, loop_dump_stream, 0);
4856 /* Fill in the data about one giv.
4857 V is the `struct induction' in which we record the giv. (It is
4858 allocated by the caller, with alloca.)
4859 INSN is the insn that sets it.
4860 BENEFIT estimates the savings from deleting this insn.
4861 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4862 into a register or is used as a memory address.
4864 SRC_REG is the biv reg which the giv is computed from.
4865 DEST_REG is the giv's reg (if the giv is stored in a reg).
4866 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4867 LOCATION points to the place where this giv's value appears in INSN. */
4870 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4871 benefit, type, not_every_iteration, maybe_multiple, location)
4872 const struct loop *loop;
4873 struct induction *v;
4877 rtx mult_val, add_val, ext_val;
4880 int not_every_iteration, maybe_multiple;
4883 struct loop_ivs *ivs = LOOP_IVS (loop);
4884 struct induction *b;
4885 struct iv_class *bl;
4886 rtx set = single_set (insn);
4889 /* Attempt to prove constantness of the values. */
4890 temp = simplify_rtx (add_val);
4895 v->src_reg = src_reg;
4897 v->dest_reg = dest_reg;
4898 v->mult_val = mult_val;
4899 v->add_val = add_val;
4900 v->ext_dependant = ext_val;
4901 v->benefit = benefit;
4902 v->location = location;
4904 v->combined_with = 0;
4905 v->maybe_multiple = maybe_multiple;
4907 v->derive_adjustment = 0;
4913 v->auto_inc_opt = 0;
4917 /* The v->always_computable field is used in update_giv_derive, to
4918 determine whether a giv can be used to derive another giv. For a
4919 DEST_REG giv, INSN computes a new value for the giv, so its value
4920 isn't computable if INSN insn't executed every iteration.
4921 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4922 it does not compute a new value. Hence the value is always computable
4923 regardless of whether INSN is executed each iteration. */
4925 if (type == DEST_ADDR)
4926 v->always_computable = 1;
4928 v->always_computable = ! not_every_iteration;
4930 v->always_executed = ! not_every_iteration;
4932 if (type == DEST_ADDR)
4934 v->mode = GET_MODE (*location);
4937 else /* type == DEST_REG */
4939 v->mode = GET_MODE (SET_DEST (set));
4941 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
4943 /* If the lifetime is zero, it means that this register is
4944 really a dead store. So mark this as a giv that can be
4945 ignored. This will not prevent the biv from being eliminated. */
4946 if (v->lifetime == 0)
4949 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
4950 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
4953 /* Add the giv to the class of givs computed from one biv. */
4955 bl = REG_IV_CLASS (ivs, REGNO (src_reg));
4958 v->next_iv = bl->giv;
4960 /* Don't count DEST_ADDR. This is supposed to count the number of
4961 insns that calculate givs. */
4962 if (type == DEST_REG)
4964 bl->total_benefit += benefit;
4967 /* Fatal error, biv missing for this giv? */
4970 if (type == DEST_ADDR)
4974 /* The giv can be replaced outright by the reduced register only if all
4975 of the following conditions are true:
4976 - the insn that sets the giv is always executed on any iteration
4977 on which the giv is used at all
4978 (there are two ways to deduce this:
4979 either the insn is executed on every iteration,
4980 or all uses follow that insn in the same basic block),
4981 - the giv is not used outside the loop
4982 - no assignments to the biv occur during the giv's lifetime. */
4984 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
4985 /* Previous line always fails if INSN was moved by loop opt. */
4986 && REGNO_LAST_LUID (REGNO (dest_reg))
4987 < INSN_LUID (loop->end)
4988 && (! not_every_iteration
4989 || last_use_this_basic_block (dest_reg, insn)))
4991 /* Now check that there are no assignments to the biv within the
4992 giv's lifetime. This requires two separate checks. */
4994 /* Check each biv update, and fail if any are between the first
4995 and last use of the giv.
4997 If this loop contains an inner loop that was unrolled, then
4998 the insn modifying the biv may have been emitted by the loop
4999 unrolling code, and hence does not have a valid luid. Just
5000 mark the biv as not replaceable in this case. It is not very
5001 useful as a biv, because it is used in two different loops.
5002 It is very unlikely that we would be able to optimize the giv
5003 using this biv anyways. */
5006 for (b = bl->biv; b; b = b->next_iv)
5008 if (INSN_UID (b->insn) >= max_uid_for_loop
5009 || ((INSN_LUID (b->insn)
5010 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
5011 && (INSN_LUID (b->insn)
5012 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
5015 v->not_replaceable = 1;
5020 /* If there are any backwards branches that go from after the
5021 biv update to before it, then this giv is not replaceable. */
5023 for (b = bl->biv; b; b = b->next_iv)
5024 if (back_branch_in_range_p (loop, b->insn))
5027 v->not_replaceable = 1;
5033 /* May still be replaceable, we don't have enough info here to
5036 v->not_replaceable = 0;
5040 /* Record whether the add_val contains a const_int, for later use by
5045 v->no_const_addval = 1;
5046 if (tem == const0_rtx)
5048 else if (CONSTANT_P (add_val))
5049 v->no_const_addval = 0;
5050 if (GET_CODE (tem) == PLUS)
5054 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5055 tem = XEXP (tem, 0);
5056 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5057 tem = XEXP (tem, 1);
5061 if (CONSTANT_P (XEXP (tem, 1)))
5062 v->no_const_addval = 0;
5066 if (loop_dump_stream)
5067 loop_giv_dump (v, loop_dump_stream, 0);
5070 /* All this does is determine whether a giv can be made replaceable because
5071 its final value can be calculated. This code can not be part of record_giv
5072 above, because final_giv_value requires that the number of loop iterations
5073 be known, and that can not be accurately calculated until after all givs
5074 have been identified. */
5077 check_final_value (loop, v)
5078 const struct loop *loop;
5079 struct induction *v;
5081 struct loop_ivs *ivs = LOOP_IVS (loop);
5082 struct iv_class *bl;
5083 rtx final_value = 0;
5085 bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
5087 /* DEST_ADDR givs will never reach here, because they are always marked
5088 replaceable above in record_giv. */
5090 /* The giv can be replaced outright by the reduced register only if all
5091 of the following conditions are true:
5092 - the insn that sets the giv is always executed on any iteration
5093 on which the giv is used at all
5094 (there are two ways to deduce this:
5095 either the insn is executed on every iteration,
5096 or all uses follow that insn in the same basic block),
5097 - its final value can be calculated (this condition is different
5098 than the one above in record_giv)
5099 - it's not used before the it's set
5100 - no assignments to the biv occur during the giv's lifetime. */
5103 /* This is only called now when replaceable is known to be false. */
5104 /* Clear replaceable, so that it won't confuse final_giv_value. */
5108 if ((final_value = final_giv_value (loop, v))
5109 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5111 int biv_increment_seen = 0, before_giv_insn = 0;
5117 /* When trying to determine whether or not a biv increment occurs
5118 during the lifetime of the giv, we can ignore uses of the variable
5119 outside the loop because final_value is true. Hence we can not
5120 use regno_last_uid and regno_first_uid as above in record_giv. */
5122 /* Search the loop to determine whether any assignments to the
5123 biv occur during the giv's lifetime. Start with the insn
5124 that sets the giv, and search around the loop until we come
5125 back to that insn again.
5127 Also fail if there is a jump within the giv's lifetime that jumps
5128 to somewhere outside the lifetime but still within the loop. This
5129 catches spaghetti code where the execution order is not linear, and
5130 hence the above test fails. Here we assume that the giv lifetime
5131 does not extend from one iteration of the loop to the next, so as
5132 to make the test easier. Since the lifetime isn't known yet,
5133 this requires two loops. See also record_giv above. */
5135 last_giv_use = v->insn;
5142 before_giv_insn = 1;
5143 p = NEXT_INSN (loop->start);
5148 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5149 || GET_CODE (p) == CALL_INSN)
5151 /* It is possible for the BIV increment to use the GIV if we
5152 have a cycle. Thus we must be sure to check each insn for
5153 both BIV and GIV uses, and we must check for BIV uses
5156 if (! biv_increment_seen
5157 && reg_set_p (v->src_reg, PATTERN (p)))
5158 biv_increment_seen = 1;
5160 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5162 if (biv_increment_seen || before_giv_insn)
5165 v->not_replaceable = 1;
5173 /* Now that the lifetime of the giv is known, check for branches
5174 from within the lifetime to outside the lifetime if it is still
5184 p = NEXT_INSN (loop->start);
5185 if (p == last_giv_use)
5188 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5189 && LABEL_NAME (JUMP_LABEL (p))
5190 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5191 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5192 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5193 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5196 v->not_replaceable = 1;
5198 if (loop_dump_stream)
5199 fprintf (loop_dump_stream,
5200 "Found branch outside giv lifetime.\n");
5207 /* If it is replaceable, then save the final value. */
5209 v->final_value = final_value;
5212 if (loop_dump_stream && v->replaceable)
5213 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5214 INSN_UID (v->insn), REGNO (v->dest_reg));
5217 /* Update the status of whether a giv can derive other givs.
5219 We need to do something special if there is or may be an update to the biv
5220 between the time the giv is defined and the time it is used to derive
5223 In addition, a giv that is only conditionally set is not allowed to
5224 derive another giv once a label has been passed.
5226 The cases we look at are when a label or an update to a biv is passed. */
5229 update_giv_derive (loop, p)
5230 const struct loop *loop;
5233 struct loop_ivs *ivs = LOOP_IVS (loop);
5234 struct iv_class *bl;
5235 struct induction *biv, *giv;
5239 /* Search all IV classes, then all bivs, and finally all givs.
5241 There are three cases we are concerned with. First we have the situation
5242 of a giv that is only updated conditionally. In that case, it may not
5243 derive any givs after a label is passed.
5245 The second case is when a biv update occurs, or may occur, after the
5246 definition of a giv. For certain biv updates (see below) that are
5247 known to occur between the giv definition and use, we can adjust the
5248 giv definition. For others, or when the biv update is conditional,
5249 we must prevent the giv from deriving any other givs. There are two
5250 sub-cases within this case.
5252 If this is a label, we are concerned with any biv update that is done
5253 conditionally, since it may be done after the giv is defined followed by
5254 a branch here (actually, we need to pass both a jump and a label, but
5255 this extra tracking doesn't seem worth it).
5257 If this is a jump, we are concerned about any biv update that may be
5258 executed multiple times. We are actually only concerned about
5259 backward jumps, but it is probably not worth performing the test
5260 on the jump again here.
5262 If this is a biv update, we must adjust the giv status to show that a
5263 subsequent biv update was performed. If this adjustment cannot be done,
5264 the giv cannot derive further givs. */
5266 for (bl = ivs->list; bl; bl = bl->next)
5267 for (biv = bl->biv; biv; biv = biv->next_iv)
5268 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5271 for (giv = bl->giv; giv; giv = giv->next_iv)
5273 /* If cant_derive is already true, there is no point in
5274 checking all of these conditions again. */
5275 if (giv->cant_derive)
5278 /* If this giv is conditionally set and we have passed a label,
5279 it cannot derive anything. */
5280 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5281 giv->cant_derive = 1;
5283 /* Skip givs that have mult_val == 0, since
5284 they are really invariants. Also skip those that are
5285 replaceable, since we know their lifetime doesn't contain
5287 else if (giv->mult_val == const0_rtx || giv->replaceable)
5290 /* The only way we can allow this giv to derive another
5291 is if this is a biv increment and we can form the product
5292 of biv->add_val and giv->mult_val. In this case, we will
5293 be able to compute a compensation. */
5294 else if (biv->insn == p)
5299 if (biv->mult_val == const1_rtx)
5300 tem = simplify_giv_expr (loop,
5301 gen_rtx_MULT (giv->mode,
5304 &ext_val_dummy, &dummy);
5306 if (tem && giv->derive_adjustment)
5307 tem = simplify_giv_expr
5309 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5310 &ext_val_dummy, &dummy);
5313 giv->derive_adjustment = tem;
5315 giv->cant_derive = 1;
5317 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5318 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5319 giv->cant_derive = 1;
5324 /* Check whether an insn is an increment legitimate for a basic induction var.
5325 X is the source of insn P, or a part of it.
5326 MODE is the mode in which X should be interpreted.
5328 DEST_REG is the putative biv, also the destination of the insn.
5329 We accept patterns of these forms:
5330 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5331 REG = INVARIANT + REG
5333 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5334 store the additive term into *INC_VAL, and store the place where
5335 we found the additive term into *LOCATION.
5337 If X is an assignment of an invariant into DEST_REG, we set
5338 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5340 We also want to detect a BIV when it corresponds to a variable
5341 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5342 of the variable may be a PLUS that adds a SUBREG of that variable to
5343 an invariant and then sign- or zero-extends the result of the PLUS
5346 Most GIVs in such cases will be in the promoted mode, since that is the
5347 probably the natural computation mode (and almost certainly the mode
5348 used for addresses) on the machine. So we view the pseudo-reg containing
5349 the variable as the BIV, as if it were simply incremented.
5351 Note that treating the entire pseudo as a BIV will result in making
5352 simple increments to any GIVs based on it. However, if the variable
5353 overflows in its declared mode but not its promoted mode, the result will
5354 be incorrect. This is acceptable if the variable is signed, since
5355 overflows in such cases are undefined, but not if it is unsigned, since
5356 those overflows are defined. So we only check for SIGN_EXTEND and
5359 If we cannot find a biv, we return 0. */
5362 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5363 const struct loop *loop;
5365 enum machine_mode mode;
5372 register enum rtx_code code;
5376 code = GET_CODE (x);
5381 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5382 || (GET_CODE (XEXP (x, 0)) == SUBREG
5383 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5384 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5386 argp = &XEXP (x, 1);
5388 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5389 || (GET_CODE (XEXP (x, 1)) == SUBREG
5390 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5391 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5393 argp = &XEXP (x, 0);
5399 if (loop_invariant_p (loop, arg) != 1)
5402 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5403 *mult_val = const1_rtx;
5408 /* If this is a SUBREG for a promoted variable, check the inner
5410 if (SUBREG_PROMOTED_VAR_P (x))
5411 return basic_induction_var (loop, SUBREG_REG (x),
5412 GET_MODE (SUBREG_REG (x)),
5413 dest_reg, p, inc_val, mult_val, location);
5417 /* If this register is assigned in a previous insn, look at its
5418 source, but don't go outside the loop or past a label. */
5420 /* If this sets a register to itself, we would repeat any previous
5421 biv increment if we applied this strategy blindly. */
5422 if (rtx_equal_p (dest_reg, x))
5431 insn = PREV_INSN (insn);
5433 while (insn && GET_CODE (insn) == NOTE
5434 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5438 set = single_set (insn);
5441 dest = SET_DEST (set);
5443 || (GET_CODE (dest) == SUBREG
5444 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5445 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5446 && SUBREG_REG (dest) == x))
5447 return basic_induction_var (loop, SET_SRC (set),
5448 (GET_MODE (SET_SRC (set)) == VOIDmode
5450 : GET_MODE (SET_SRC (set))),
5452 inc_val, mult_val, location);
5454 while (GET_CODE (dest) == SIGN_EXTRACT
5455 || GET_CODE (dest) == ZERO_EXTRACT
5456 || GET_CODE (dest) == SUBREG
5457 || GET_CODE (dest) == STRICT_LOW_PART)
5458 dest = XEXP (dest, 0);
5464 /* Can accept constant setting of biv only when inside inner most loop.
5465 Otherwise, a biv of an inner loop may be incorrectly recognized
5466 as a biv of the outer loop,
5467 causing code to be moved INTO the inner loop. */
5469 if (loop_invariant_p (loop, x) != 1)
5474 /* convert_modes aborts if we try to convert to or from CCmode, so just
5475 exclude that case. It is very unlikely that a condition code value
5476 would be a useful iterator anyways. */
5477 if (loop->level == 1
5478 && GET_MODE_CLASS (mode) != MODE_CC
5479 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5481 /* Possible bug here? Perhaps we don't know the mode of X. */
5482 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5483 *mult_val = const0_rtx;
5490 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5491 dest_reg, p, inc_val, mult_val, location);
5494 /* Similar, since this can be a sign extension. */
5495 for (insn = PREV_INSN (p);
5496 (insn && GET_CODE (insn) == NOTE
5497 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5498 insn = PREV_INSN (insn))
5502 set = single_set (insn);
5504 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5505 && set && SET_DEST (set) == XEXP (x, 0)
5506 && GET_CODE (XEXP (x, 1)) == CONST_INT
5507 && INTVAL (XEXP (x, 1)) >= 0
5508 && GET_CODE (SET_SRC (set)) == ASHIFT
5509 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5510 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5511 GET_MODE (XEXP (x, 0)),
5512 dest_reg, insn, inc_val, mult_val,
5521 /* A general induction variable (giv) is any quantity that is a linear
5522 function of a basic induction variable,
5523 i.e. giv = biv * mult_val + add_val.
5524 The coefficients can be any loop invariant quantity.
5525 A giv need not be computed directly from the biv;
5526 it can be computed by way of other givs. */
5528 /* Determine whether X computes a giv.
5529 If it does, return a nonzero value
5530 which is the benefit from eliminating the computation of X;
5531 set *SRC_REG to the register of the biv that it is computed from;
5532 set *ADD_VAL and *MULT_VAL to the coefficients,
5533 such that the value of X is biv * mult + add; */
5536 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5537 is_addr, pbenefit, addr_mode)
5538 const struct loop *loop;
5546 enum machine_mode addr_mode;
5548 struct loop_ivs *ivs = LOOP_IVS (loop);
5551 /* If this is an invariant, forget it, it isn't a giv. */
5552 if (loop_invariant_p (loop, x) == 1)
5556 *ext_val = NULL_RTX;
5557 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5561 switch (GET_CODE (x))
5565 /* Since this is now an invariant and wasn't before, it must be a giv
5566 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5568 *src_reg = ivs->list->biv->dest_reg;
5569 *mult_val = const0_rtx;
5574 /* This is equivalent to a BIV. */
5576 *mult_val = const1_rtx;
5577 *add_val = const0_rtx;
5581 /* Either (plus (biv) (invar)) or
5582 (plus (mult (biv) (invar_1)) (invar_2)). */
5583 if (GET_CODE (XEXP (x, 0)) == MULT)
5585 *src_reg = XEXP (XEXP (x, 0), 0);
5586 *mult_val = XEXP (XEXP (x, 0), 1);
5590 *src_reg = XEXP (x, 0);
5591 *mult_val = const1_rtx;
5593 *add_val = XEXP (x, 1);
5597 /* ADD_VAL is zero. */
5598 *src_reg = XEXP (x, 0);
5599 *mult_val = XEXP (x, 1);
5600 *add_val = const0_rtx;
5607 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5608 unless they are CONST_INT). */
5609 if (GET_CODE (*add_val) == USE)
5610 *add_val = XEXP (*add_val, 0);
5611 if (GET_CODE (*mult_val) == USE)
5612 *mult_val = XEXP (*mult_val, 0);
5615 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5617 *pbenefit += rtx_cost (orig_x, SET);
5619 /* Always return true if this is a giv so it will be detected as such,
5620 even if the benefit is zero or negative. This allows elimination
5621 of bivs that might otherwise not be eliminated. */
5625 /* Given an expression, X, try to form it as a linear function of a biv.
5626 We will canonicalize it to be of the form
5627 (plus (mult (BIV) (invar_1))
5629 with possible degeneracies.
5631 The invariant expressions must each be of a form that can be used as a
5632 machine operand. We surround then with a USE rtx (a hack, but localized
5633 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5634 routine; it is the caller's responsibility to strip them.
5636 If no such canonicalization is possible (i.e., two biv's are used or an
5637 expression that is neither invariant nor a biv or giv), this routine
5640 For a non-zero return, the result will have a code of CONST_INT, USE,
5641 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5643 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5645 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5646 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5649 simplify_giv_expr (loop, x, ext_val, benefit)
5650 const struct loop *loop;
5655 struct loop_ivs *ivs = LOOP_IVS (loop);
5656 struct loop_regs *regs = LOOP_REGS (loop);
5657 enum machine_mode mode = GET_MODE (x);
5661 /* If this is not an integer mode, or if we cannot do arithmetic in this
5662 mode, this can't be a giv. */
5663 if (mode != VOIDmode
5664 && (GET_MODE_CLASS (mode) != MODE_INT
5665 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5668 switch (GET_CODE (x))
5671 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5672 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5673 if (arg0 == 0 || arg1 == 0)
5676 /* Put constant last, CONST_INT last if both constant. */
5677 if ((GET_CODE (arg0) == USE
5678 || GET_CODE (arg0) == CONST_INT)
5679 && ! ((GET_CODE (arg0) == USE
5680 && GET_CODE (arg1) == USE)
5681 || GET_CODE (arg1) == CONST_INT))
5682 tem = arg0, arg0 = arg1, arg1 = tem;
5684 /* Handle addition of zero, then addition of an invariant. */
5685 if (arg1 == const0_rtx)
5687 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5688 switch (GET_CODE (arg0))
5692 /* Adding two invariants must result in an invariant, so enclose
5693 addition operation inside a USE and return it. */
5694 if (GET_CODE (arg0) == USE)
5695 arg0 = XEXP (arg0, 0);
5696 if (GET_CODE (arg1) == USE)
5697 arg1 = XEXP (arg1, 0);
5699 if (GET_CODE (arg0) == CONST_INT)
5700 tem = arg0, arg0 = arg1, arg1 = tem;
5701 if (GET_CODE (arg1) == CONST_INT)
5702 tem = sge_plus_constant (arg0, arg1);
5704 tem = sge_plus (mode, arg0, arg1);
5706 if (GET_CODE (tem) != CONST_INT)
5707 tem = gen_rtx_USE (mode, tem);
5712 /* biv + invar or mult + invar. Return sum. */
5713 return gen_rtx_PLUS (mode, arg0, arg1);
5716 /* (a + invar_1) + invar_2. Associate. */
5718 simplify_giv_expr (loop,
5730 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5731 MULT to reduce cases. */
5732 if (GET_CODE (arg0) == REG)
5733 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5734 if (GET_CODE (arg1) == REG)
5735 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5737 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5738 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5739 Recurse to associate the second PLUS. */
5740 if (GET_CODE (arg1) == MULT)
5741 tem = arg0, arg0 = arg1, arg1 = tem;
5743 if (GET_CODE (arg1) == PLUS)
5745 simplify_giv_expr (loop,
5747 gen_rtx_PLUS (mode, arg0,
5752 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5753 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5756 if (!rtx_equal_p (arg0, arg1))
5759 return simplify_giv_expr (loop,
5768 /* Handle "a - b" as "a + b * (-1)". */
5769 return simplify_giv_expr (loop,
5778 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5779 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5780 if (arg0 == 0 || arg1 == 0)
5783 /* Put constant last, CONST_INT last if both constant. */
5784 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5785 && GET_CODE (arg1) != CONST_INT)
5786 tem = arg0, arg0 = arg1, arg1 = tem;
5788 /* If second argument is not now constant, not giv. */
5789 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5792 /* Handle multiply by 0 or 1. */
5793 if (arg1 == const0_rtx)
5796 else if (arg1 == const1_rtx)
5799 switch (GET_CODE (arg0))
5802 /* biv * invar. Done. */
5803 return gen_rtx_MULT (mode, arg0, arg1);
5806 /* Product of two constants. */
5807 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5810 /* invar * invar is a giv, but attempt to simplify it somehow. */
5811 if (GET_CODE (arg1) != CONST_INT)
5814 arg0 = XEXP (arg0, 0);
5815 if (GET_CODE (arg0) == MULT)
5817 /* (invar_0 * invar_1) * invar_2. Associate. */
5818 return simplify_giv_expr (loop,
5827 /* Porpagate the MULT expressions to the intermost nodes. */
5828 else if (GET_CODE (arg0) == PLUS)
5830 /* (invar_0 + invar_1) * invar_2. Distribute. */
5831 return simplify_giv_expr (loop,
5843 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
5846 /* (a * invar_1) * invar_2. Associate. */
5847 return simplify_giv_expr (loop,
5856 /* (a + invar_1) * invar_2. Distribute. */
5857 return simplify_giv_expr (loop,
5872 /* Shift by constant is multiply by power of two. */
5873 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5877 simplify_giv_expr (loop,
5880 GEN_INT ((HOST_WIDE_INT) 1
5881 << INTVAL (XEXP (x, 1)))),
5885 /* "-a" is "a * (-1)" */
5886 return simplify_giv_expr (loop,
5887 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
5891 /* "~a" is "-a - 1". Silly, but easy. */
5892 return simplify_giv_expr (loop,
5893 gen_rtx_MINUS (mode,
5894 gen_rtx_NEG (mode, XEXP (x, 0)),
5899 /* Already in proper form for invariant. */
5905 /* Conditionally recognize extensions of simple IVs. After we've
5906 computed loop traversal counts and verified the range of the
5907 source IV, we'll reevaluate this as a GIV. */
5908 if (*ext_val == NULL_RTX)
5910 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5911 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
5913 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
5920 /* If this is a new register, we can't deal with it. */
5921 if (REGNO (x) >= max_reg_before_loop)
5924 /* Check for biv or giv. */
5925 switch (REG_IV_TYPE (ivs, REGNO (x)))
5929 case GENERAL_INDUCT:
5931 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
5933 /* Form expression from giv and add benefit. Ensure this giv
5934 can derive another and subtract any needed adjustment if so. */
5936 /* Increasing the benefit here is risky. The only case in which it
5937 is arguably correct is if this is the only use of V. In other
5938 cases, this will artificially inflate the benefit of the current
5939 giv, and lead to suboptimal code. Thus, it is disabled, since
5940 potentially not reducing an only marginally beneficial giv is
5941 less harmful than reducing many givs that are not really
5944 rtx single_use = regs->array[REGNO (x)].single_usage;
5945 if (single_use && single_use != const0_rtx)
5946 *benefit += v->benefit;
5952 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
5953 v->src_reg, v->mult_val),
5956 if (v->derive_adjustment)
5957 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
5958 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
5961 if (!v->ext_dependant)
5966 *ext_val = v->ext_dependant;
5974 /* If it isn't an induction variable, and it is invariant, we
5975 may be able to simplify things further by looking through
5976 the bits we just moved outside the loop. */
5977 if (loop_invariant_p (loop, x) == 1)
5980 struct loop_movables *movables = LOOP_MOVABLES (loop);
5982 for (m = movables->head; m; m = m->next)
5983 if (rtx_equal_p (x, m->set_dest))
5985 /* Ok, we found a match. Substitute and simplify. */
5987 /* If we match another movable, we must use that, as
5988 this one is going away. */
5990 return simplify_giv_expr (loop, m->match->set_dest,
5993 /* If consec is non-zero, this is a member of a group of
5994 instructions that were moved together. We handle this
5995 case only to the point of seeking to the last insn and
5996 looking for a REG_EQUAL. Fail if we don't find one. */
6003 tem = NEXT_INSN (tem);
6007 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6009 tem = XEXP (tem, 0);
6013 tem = single_set (m->insn);
6015 tem = SET_SRC (tem);
6020 /* What we are most interested in is pointer
6021 arithmetic on invariants -- only take
6022 patterns we may be able to do something with. */
6023 if (GET_CODE (tem) == PLUS
6024 || GET_CODE (tem) == MULT
6025 || GET_CODE (tem) == ASHIFT
6026 || GET_CODE (tem) == CONST_INT
6027 || GET_CODE (tem) == SYMBOL_REF)
6029 tem = simplify_giv_expr (loop, tem, ext_val,
6034 else if (GET_CODE (tem) == CONST
6035 && GET_CODE (XEXP (tem, 0)) == PLUS
6036 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6037 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6039 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6051 /* Fall through to general case. */
6053 /* If invariant, return as USE (unless CONST_INT).
6054 Otherwise, not giv. */
6055 if (GET_CODE (x) == USE)
6058 if (loop_invariant_p (loop, x) == 1)
6060 if (GET_CODE (x) == CONST_INT)
6062 if (GET_CODE (x) == CONST
6063 && GET_CODE (XEXP (x, 0)) == PLUS
6064 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6065 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6067 return gen_rtx_USE (mode, x);
6074 /* This routine folds invariants such that there is only ever one
6075 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6078 sge_plus_constant (x, c)
6081 if (GET_CODE (x) == CONST_INT)
6082 return GEN_INT (INTVAL (x) + INTVAL (c));
6083 else if (GET_CODE (x) != PLUS)
6084 return gen_rtx_PLUS (GET_MODE (x), x, c);
6085 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6087 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6088 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6090 else if (GET_CODE (XEXP (x, 0)) == PLUS
6091 || GET_CODE (XEXP (x, 1)) != PLUS)
6093 return gen_rtx_PLUS (GET_MODE (x),
6094 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6098 return gen_rtx_PLUS (GET_MODE (x),
6099 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6104 sge_plus (mode, x, y)
6105 enum machine_mode mode;
6108 while (GET_CODE (y) == PLUS)
6110 rtx a = XEXP (y, 0);
6111 if (GET_CODE (a) == CONST_INT)
6112 x = sge_plus_constant (x, a);
6114 x = gen_rtx_PLUS (mode, x, a);
6117 if (GET_CODE (y) == CONST_INT)
6118 x = sge_plus_constant (x, y);
6120 x = gen_rtx_PLUS (mode, x, y);
6124 /* Help detect a giv that is calculated by several consecutive insns;
6128 The caller has already identified the first insn P as having a giv as dest;
6129 we check that all other insns that set the same register follow
6130 immediately after P, that they alter nothing else,
6131 and that the result of the last is still a giv.
6133 The value is 0 if the reg set in P is not really a giv.
6134 Otherwise, the value is the amount gained by eliminating
6135 all the consecutive insns that compute the value.
6137 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6138 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6140 The coefficients of the ultimate giv value are stored in
6141 *MULT_VAL and *ADD_VAL. */
6144 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6145 add_val, mult_val, ext_val, last_consec_insn)
6146 const struct loop *loop;
6154 rtx *last_consec_insn;
6156 struct loop_ivs *ivs = LOOP_IVS (loop);
6157 struct loop_regs *regs = LOOP_REGS (loop);
6164 /* Indicate that this is a giv so that we can update the value produced in
6165 each insn of the multi-insn sequence.
6167 This induction structure will be used only by the call to
6168 general_induction_var below, so we can allocate it on our stack.
6169 If this is a giv, our caller will replace the induct var entry with
6170 a new induction structure. */
6171 struct induction *v;
6173 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6176 v = (struct induction *) alloca (sizeof (struct induction));
6177 v->src_reg = src_reg;
6178 v->mult_val = *mult_val;
6179 v->add_val = *add_val;
6180 v->benefit = first_benefit;
6182 v->derive_adjustment = 0;
6183 v->ext_dependant = NULL_RTX;
6185 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6186 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6188 count = regs->array[REGNO (dest_reg)].n_times_set - 1;
6193 code = GET_CODE (p);
6195 /* If libcall, skip to end of call sequence. */
6196 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6200 && (set = single_set (p))
6201 && GET_CODE (SET_DEST (set)) == REG
6202 && SET_DEST (set) == dest_reg
6203 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6204 add_val, mult_val, ext_val, 0,
6206 /* Giv created by equivalent expression. */
6207 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6208 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6209 add_val, mult_val, ext_val, 0,
6210 &benefit, VOIDmode)))
6211 && src_reg == v->src_reg)
6213 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6214 benefit += libcall_benefit (p);
6217 v->mult_val = *mult_val;
6218 v->add_val = *add_val;
6219 v->benefit += benefit;
6221 else if (code != NOTE)
6223 /* Allow insns that set something other than this giv to a
6224 constant. Such insns are needed on machines which cannot
6225 include long constants and should not disqualify a giv. */
6227 && (set = single_set (p))
6228 && SET_DEST (set) != dest_reg
6229 && CONSTANT_P (SET_SRC (set)))
6232 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6237 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6238 *last_consec_insn = p;
6242 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6243 represented by G1. If no such expression can be found, or it is clear that
6244 it cannot possibly be a valid address, 0 is returned.
6246 To perform the computation, we note that
6249 where `v' is the biv.
6251 So G2 = (y/b) * G1 + (b - a*y/x).
6253 Note that MULT = y/x.
6255 Update: A and B are now allowed to be additive expressions such that
6256 B contains all variables in A. That is, computing B-A will not require
6257 subtracting variables. */
6260 express_from_1 (a, b, mult)
6263 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6265 if (mult == const0_rtx)
6268 /* If MULT is not 1, we cannot handle A with non-constants, since we
6269 would then be required to subtract multiples of the registers in A.
6270 This is theoretically possible, and may even apply to some Fortran
6271 constructs, but it is a lot of work and we do not attempt it here. */
6273 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6276 /* In general these structures are sorted top to bottom (down the PLUS
6277 chain), but not left to right across the PLUS. If B is a higher
6278 order giv than A, we can strip one level and recurse. If A is higher
6279 order, we'll eventually bail out, but won't know that until the end.
6280 If they are the same, we'll strip one level around this loop. */
6282 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6284 rtx ra, rb, oa, ob, tmp;
6286 ra = XEXP (a, 0), oa = XEXP (a, 1);
6287 if (GET_CODE (ra) == PLUS)
6288 tmp = ra, ra = oa, oa = tmp;
6290 rb = XEXP (b, 0), ob = XEXP (b, 1);
6291 if (GET_CODE (rb) == PLUS)
6292 tmp = rb, rb = ob, ob = tmp;
6294 if (rtx_equal_p (ra, rb))
6295 /* We matched: remove one reg completely. */
6297 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6298 /* An alternate match. */
6300 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6301 /* An alternate match. */
6305 /* Indicates an extra register in B. Strip one level from B and
6306 recurse, hoping B was the higher order expression. */
6307 ob = express_from_1 (a, ob, mult);
6310 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6314 /* Here we are at the last level of A, go through the cases hoping to
6315 get rid of everything but a constant. */
6317 if (GET_CODE (a) == PLUS)
6321 ra = XEXP (a, 0), oa = XEXP (a, 1);
6322 if (rtx_equal_p (oa, b))
6324 else if (!rtx_equal_p (ra, b))
6327 if (GET_CODE (oa) != CONST_INT)
6330 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6332 else if (GET_CODE (a) == CONST_INT)
6334 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6336 else if (CONSTANT_P (a))
6338 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6340 else if (GET_CODE (b) == PLUS)
6342 if (rtx_equal_p (a, XEXP (b, 0)))
6344 else if (rtx_equal_p (a, XEXP (b, 1)))
6349 else if (rtx_equal_p (a, b))
6356 express_from (g1, g2)
6357 struct induction *g1, *g2;
6361 /* The value that G1 will be multiplied by must be a constant integer. Also,
6362 the only chance we have of getting a valid address is if b*c/a (see above
6363 for notation) is also an integer. */
6364 if (GET_CODE (g1->mult_val) == CONST_INT
6365 && GET_CODE (g2->mult_val) == CONST_INT)
6367 if (g1->mult_val == const0_rtx
6368 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6370 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6372 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6376 /* ??? Find out if the one is a multiple of the other? */
6380 add = express_from_1 (g1->add_val, g2->add_val, mult);
6381 if (add == NULL_RTX)
6383 /* Failed. If we've got a multiplication factor between G1 and G2,
6384 scale G1's addend and try again. */
6385 if (INTVAL (mult) > 1)
6387 rtx g1_add_val = g1->add_val;
6388 if (GET_CODE (g1_add_val) == MULT
6389 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6392 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6393 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6394 XEXP (g1_add_val, 0), GEN_INT (m));
6398 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6402 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6405 if (add == NULL_RTX)
6408 /* Form simplified final result. */
6409 if (mult == const0_rtx)
6411 else if (mult == const1_rtx)
6412 mult = g1->dest_reg;
6414 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6416 if (add == const0_rtx)
6420 if (GET_CODE (add) == PLUS
6421 && CONSTANT_P (XEXP (add, 1)))
6423 rtx tem = XEXP (add, 1);
6424 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6428 return gen_rtx_PLUS (g2->mode, mult, add);
6432 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6433 represented by G1. This indicates that G2 should be combined with G1 and
6434 that G2 can use (either directly or via an address expression) a register
6435 used to represent G1. */
6438 combine_givs_p (g1, g2)
6439 struct induction *g1, *g2;
6443 /* With the introduction of ext dependant givs, we must care for modes.
6444 G2 must not use a wider mode than G1. */
6445 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6448 ret = comb = express_from (g1, g2);
6449 if (comb == NULL_RTX)
6451 if (g1->mode != g2->mode)
6452 ret = gen_lowpart (g2->mode, comb);
6454 /* If these givs are identical, they can be combined. We use the results
6455 of express_from because the addends are not in a canonical form, so
6456 rtx_equal_p is a weaker test. */
6457 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6458 combination to be the other way round. */
6459 if (comb == g1->dest_reg
6460 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6465 /* If G2 can be expressed as a function of G1 and that function is valid
6466 as an address and no more expensive than using a register for G2,
6467 the expression of G2 in terms of G1 can be used. */
6469 && g2->giv_type == DEST_ADDR
6470 && memory_address_p (g2->mem_mode, ret)
6471 /* ??? Looses, especially with -fforce-addr, where *g2->location
6472 will always be a register, and so anything more complicated
6476 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6478 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6489 /* Check each extension dependant giv in this class to see if its
6490 root biv is safe from wrapping in the interior mode, which would
6491 make the giv illegal. */
6494 check_ext_dependant_givs (bl, loop_info)
6495 struct iv_class *bl;
6496 struct loop_info *loop_info;
6498 int ze_ok = 0, se_ok = 0, info_ok = 0;
6499 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6500 HOST_WIDE_INT start_val;
6501 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6503 struct induction *v;
6505 /* Make sure the iteration data is available. We must have
6506 constants in order to be certain of no overflow. */
6507 /* ??? An unknown iteration count with an increment of +-1
6508 combined with friendly exit tests of against an invariant
6509 value is also ameanable to optimization. Not implemented. */
6510 if (loop_info->n_iterations > 0
6511 && bl->initial_value
6512 && GET_CODE (bl->initial_value) == CONST_INT
6513 && (incr = biv_total_increment (bl))
6514 && GET_CODE (incr) == CONST_INT
6515 /* Make sure the host can represent the arithmetic. */
6516 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6518 unsigned HOST_WIDE_INT abs_incr, total_incr;
6519 HOST_WIDE_INT s_end_val;
6523 start_val = INTVAL (bl->initial_value);
6524 u_start_val = start_val;
6526 neg_incr = 0, abs_incr = INTVAL (incr);
6527 if (INTVAL (incr) < 0)
6528 neg_incr = 1, abs_incr = -abs_incr;
6529 total_incr = abs_incr * loop_info->n_iterations;
6531 /* Check for host arithmatic overflow. */
6532 if (total_incr / loop_info->n_iterations == abs_incr)
6534 unsigned HOST_WIDE_INT u_max;
6535 HOST_WIDE_INT s_max;
6537 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6538 s_end_val = u_end_val;
6539 u_max = GET_MODE_MASK (biv_mode);
6542 /* Check zero extension of biv ok. */
6544 /* Check for host arithmatic overflow. */
6546 ? u_end_val < u_start_val
6547 : u_end_val > u_start_val)
6548 /* Check for target arithmetic overflow. */
6550 ? 1 /* taken care of with host overflow */
6551 : u_end_val <= u_max))
6556 /* Check sign extension of biv ok. */
6557 /* ??? While it is true that overflow with signed and pointer
6558 arithmetic is undefined, I fear too many programmers don't
6559 keep this fact in mind -- myself included on occasion.
6560 So leave alone with the signed overflow optimizations. */
6561 if (start_val >= -s_max - 1
6562 /* Check for host arithmatic overflow. */
6564 ? s_end_val < start_val
6565 : s_end_val > start_val)
6566 /* Check for target arithmetic overflow. */
6568 ? s_end_val >= -s_max - 1
6569 : s_end_val <= s_max))
6576 /* Invalidate givs that fail the tests. */
6577 for (v = bl->giv; v; v = v->next_iv)
6578 if (v->ext_dependant)
6580 enum rtx_code code = GET_CODE (v->ext_dependant);
6593 /* We don't know whether this value is being used as either
6594 signed or unsigned, so to safely truncate we must satisfy
6595 both. The initial check here verifies the BIV itself;
6596 once that is successful we may check its range wrt the
6600 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6601 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6603 /* We know from the above that both endpoints are nonnegative,
6604 and that there is no wrapping. Verify that both endpoints
6605 are within the (signed) range of the outer mode. */
6606 if (u_start_val <= max && u_end_val <= max)
6617 if (loop_dump_stream)
6619 fprintf (loop_dump_stream,
6620 "Verified ext dependant giv at %d of reg %d\n",
6621 INSN_UID (v->insn), bl->regno);
6626 if (loop_dump_stream)
6631 why = "biv iteration values overflowed";
6635 incr = biv_total_increment (bl);
6636 if (incr == const1_rtx)
6637 why = "biv iteration info incomplete; incr by 1";
6639 why = "biv iteration info incomplete";
6642 fprintf (loop_dump_stream,
6643 "Failed ext dependant giv at %d, %s\n",
6644 INSN_UID (v->insn), why);
6651 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6654 extend_value_for_giv (v, value)
6655 struct induction *v;
6658 rtx ext_dep = v->ext_dependant;
6663 /* Recall that check_ext_dependant_givs verified that the known bounds
6664 of a biv did not overflow or wrap with respect to the extension for
6665 the giv. Therefore, constants need no additional adjustment. */
6666 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6669 /* Otherwise, we must adjust the value to compensate for the
6670 differing modes of the biv and the giv. */
6671 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6674 struct combine_givs_stats
6681 cmp_combine_givs_stats (xp, yp)
6685 const struct combine_givs_stats * const x =
6686 (const struct combine_givs_stats *) xp;
6687 const struct combine_givs_stats * const y =
6688 (const struct combine_givs_stats *) yp;
6690 d = y->total_benefit - x->total_benefit;
6691 /* Stabilize the sort. */
6693 d = x->giv_number - y->giv_number;
6697 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6698 any other. If so, point SAME to the giv combined with and set NEW_REG to
6699 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6700 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6703 combine_givs (regs, bl)
6704 struct loop_regs *regs;
6705 struct iv_class *bl;
6707 /* Additional benefit to add for being combined multiple times. */
6708 const int extra_benefit = 3;
6710 struct induction *g1, *g2, **giv_array;
6711 int i, j, k, giv_count;
6712 struct combine_givs_stats *stats;
6715 /* Count givs, because bl->giv_count is incorrect here. */
6717 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6722 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6724 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6726 giv_array[i++] = g1;
6728 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6729 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6731 for (i = 0; i < giv_count; i++)
6737 stats[i].giv_number = i;
6739 /* If a DEST_REG GIV is used only once, do not allow it to combine
6740 with anything, for in doing so we will gain nothing that cannot
6741 be had by simply letting the GIV with which we would have combined
6742 to be reduced on its own. The losage shows up in particular with
6743 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6744 be seen elsewhere as well. */
6745 if (g1->giv_type == DEST_REG
6746 && (single_use = regs->array[REGNO (g1->dest_reg)].single_usage)
6747 && single_use != const0_rtx)
6750 this_benefit = g1->benefit;
6751 /* Add an additional weight for zero addends. */
6752 if (g1->no_const_addval)
6755 for (j = 0; j < giv_count; j++)
6761 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6763 can_combine[i * giv_count + j] = this_combine;
6764 this_benefit += g2->benefit + extra_benefit;
6767 stats[i].total_benefit = this_benefit;
6770 /* Iterate, combining until we can't. */
6772 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6774 if (loop_dump_stream)
6776 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6777 for (k = 0; k < giv_count; k++)
6779 g1 = giv_array[stats[k].giv_number];
6780 if (!g1->combined_with && !g1->same)
6781 fprintf (loop_dump_stream, " {%d, %d}",
6782 INSN_UID (giv_array[stats[k].giv_number]->insn),
6783 stats[k].total_benefit);
6785 putc ('\n', loop_dump_stream);
6788 for (k = 0; k < giv_count; k++)
6790 int g1_add_benefit = 0;
6792 i = stats[k].giv_number;
6795 /* If it has already been combined, skip. */
6796 if (g1->combined_with || g1->same)
6799 for (j = 0; j < giv_count; j++)
6802 if (g1 != g2 && can_combine[i * giv_count + j]
6803 /* If it has already been combined, skip. */
6804 && ! g2->same && ! g2->combined_with)
6808 g2->new_reg = can_combine[i * giv_count + j];
6810 g1->combined_with++;
6811 g1->lifetime += g2->lifetime;
6813 g1_add_benefit += g2->benefit;
6815 /* ??? The new final_[bg]iv_value code does a much better job
6816 of finding replaceable giv's, and hence this code may no
6817 longer be necessary. */
6818 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6819 g1_add_benefit -= copy_cost;
6821 /* To help optimize the next set of combinations, remove
6822 this giv from the benefits of other potential mates. */
6823 for (l = 0; l < giv_count; ++l)
6825 int m = stats[l].giv_number;
6826 if (can_combine[m * giv_count + j])
6827 stats[l].total_benefit -= g2->benefit + extra_benefit;
6830 if (loop_dump_stream)
6831 fprintf (loop_dump_stream,
6832 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
6833 INSN_UID (g2->insn), INSN_UID (g1->insn),
6834 g1->benefit, g1_add_benefit, g1->lifetime);
6838 /* To help optimize the next set of combinations, remove
6839 this giv from the benefits of other potential mates. */
6840 if (g1->combined_with)
6842 for (j = 0; j < giv_count; ++j)
6844 int m = stats[j].giv_number;
6845 if (can_combine[m * giv_count + i])
6846 stats[j].total_benefit -= g1->benefit + extra_benefit;
6849 g1->benefit += g1_add_benefit;
6851 /* We've finished with this giv, and everything it touched.
6852 Restart the combination so that proper weights for the
6853 rest of the givs are properly taken into account. */
6854 /* ??? Ideally we would compact the arrays at this point, so
6855 as to not cover old ground. But sanely compacting
6856 can_combine is tricky. */
6866 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
6869 emit_iv_add_mult (b, m, a, reg, insert_before)
6870 rtx b; /* initial value of basic induction variable */
6871 rtx m; /* multiplicative constant */
6872 rtx a; /* additive constant */
6873 rtx reg; /* destination register */
6879 /* Prevent unexpected sharing of these rtx. */
6883 /* Increase the lifetime of any invariants moved further in code. */
6884 update_reg_last_use (a, insert_before);
6885 update_reg_last_use (b, insert_before);
6886 update_reg_last_use (m, insert_before);
6889 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
6891 emit_move_insn (reg, result);
6892 seq = gen_sequence ();
6895 emit_insn_before (seq, insert_before);
6897 /* It is entirely possible that the expansion created lots of new
6898 registers. Iterate over the sequence we just created and
6901 if (GET_CODE (seq) == SEQUENCE)
6904 for (i = 0; i < XVECLEN (seq, 0); ++i)
6906 rtx set = single_set (XVECEXP (seq, 0, i));
6907 if (set && GET_CODE (SET_DEST (set)) == REG)
6908 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6913 rtx set = single_set (seq);
6914 if (set && GET_CODE (SET_DEST (set)) == REG)
6915 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6919 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
6922 iv_add_mult_cost (b, m, a, reg)
6923 rtx b; /* initial value of basic induction variable */
6924 rtx m; /* multiplicative constant */
6925 rtx a; /* additive constant */
6926 rtx reg; /* destination register */
6932 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
6934 emit_move_insn (reg, result);
6935 last = get_last_insn ();
6938 rtx t = single_set (last);
6940 cost += rtx_cost (SET_SRC (t), SET);
6941 last = PREV_INSN (last);
6947 /* Test whether A * B can be computed without
6948 an actual multiply insn. Value is 1 if so. */
6951 product_cheap_p (a, b)
6959 /* If only one is constant, make it B. */
6960 if (GET_CODE (a) == CONST_INT)
6961 tmp = a, a = b, b = tmp;
6963 /* If first constant, both constant, so don't need multiply. */
6964 if (GET_CODE (a) == CONST_INT)
6967 /* If second not constant, neither is constant, so would need multiply. */
6968 if (GET_CODE (b) != CONST_INT)
6971 /* One operand is constant, so might not need multiply insn. Generate the
6972 code for the multiply and see if a call or multiply, or long sequence
6973 of insns is generated. */
6976 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
6977 tmp = gen_sequence ();
6980 if (GET_CODE (tmp) == SEQUENCE)
6982 if (XVEC (tmp, 0) == 0)
6984 else if (XVECLEN (tmp, 0) > 3)
6987 for (i = 0; i < XVECLEN (tmp, 0); i++)
6989 rtx insn = XVECEXP (tmp, 0, i);
6991 if (GET_CODE (insn) != INSN
6992 || (GET_CODE (PATTERN (insn)) == SET
6993 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
6994 || (GET_CODE (PATTERN (insn)) == PARALLEL
6995 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
6996 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7003 else if (GET_CODE (tmp) == SET
7004 && GET_CODE (SET_SRC (tmp)) == MULT)
7006 else if (GET_CODE (tmp) == PARALLEL
7007 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7008 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7014 /* Check to see if loop can be terminated by a "decrement and branch until
7015 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7016 Also try reversing an increment loop to a decrement loop
7017 to see if the optimization can be performed.
7018 Value is nonzero if optimization was performed. */
7020 /* This is useful even if the architecture doesn't have such an insn,
7021 because it might change a loops which increments from 0 to n to a loop
7022 which decrements from n to 0. A loop that decrements to zero is usually
7023 faster than one that increments from zero. */
7025 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7026 such as approx_final_value, biv_total_increment, loop_iterations, and
7027 final_[bg]iv_value. */
7030 check_dbra_loop (loop, insn_count)
7034 struct loop_info *loop_info = LOOP_INFO (loop);
7035 struct loop_regs *regs = LOOP_REGS (loop);
7036 struct loop_ivs *ivs = LOOP_IVS (loop);
7037 struct iv_class *bl;
7044 rtx before_comparison;
7048 int compare_and_branch;
7049 rtx loop_start = loop->start;
7050 rtx loop_end = loop->end;
7052 /* If last insn is a conditional branch, and the insn before tests a
7053 register value, try to optimize it. Otherwise, we can't do anything. */
7055 jump = PREV_INSN (loop_end);
7056 comparison = get_condition_for_loop (loop, jump);
7057 if (comparison == 0)
7059 if (!onlyjump_p (jump))
7062 /* Try to compute whether the compare/branch at the loop end is one or
7063 two instructions. */
7064 get_condition (jump, &first_compare);
7065 if (first_compare == jump)
7066 compare_and_branch = 1;
7067 else if (first_compare == prev_nonnote_insn (jump))
7068 compare_and_branch = 2;
7073 /* If more than one condition is present to control the loop, then
7074 do not proceed, as this function does not know how to rewrite
7075 loop tests with more than one condition.
7077 Look backwards from the first insn in the last comparison
7078 sequence and see if we've got another comparison sequence. */
7081 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7082 if (GET_CODE (jump1) == JUMP_INSN)
7086 /* Check all of the bivs to see if the compare uses one of them.
7087 Skip biv's set more than once because we can't guarantee that
7088 it will be zero on the last iteration. Also skip if the biv is
7089 used between its update and the test insn. */
7091 for (bl = ivs->list; bl; bl = bl->next)
7093 if (bl->biv_count == 1
7094 && ! bl->biv->maybe_multiple
7095 && bl->biv->dest_reg == XEXP (comparison, 0)
7096 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7104 /* Look for the case where the basic induction variable is always
7105 nonnegative, and equals zero on the last iteration.
7106 In this case, add a reg_note REG_NONNEG, which allows the
7107 m68k DBRA instruction to be used. */
7109 if (((GET_CODE (comparison) == GT
7110 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7111 && INTVAL (XEXP (comparison, 1)) == -1)
7112 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7113 && GET_CODE (bl->biv->add_val) == CONST_INT
7114 && INTVAL (bl->biv->add_val) < 0)
7116 /* Initial value must be greater than 0,
7117 init_val % -dec_value == 0 to ensure that it equals zero on
7118 the last iteration */
7120 if (GET_CODE (bl->initial_value) == CONST_INT
7121 && INTVAL (bl->initial_value) > 0
7122 && (INTVAL (bl->initial_value)
7123 % (-INTVAL (bl->biv->add_val))) == 0)
7125 /* register always nonnegative, add REG_NOTE to branch */
7126 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7128 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7135 /* If the decrement is 1 and the value was tested as >= 0 before
7136 the loop, then we can safely optimize. */
7137 for (p = loop_start; p; p = PREV_INSN (p))
7139 if (GET_CODE (p) == CODE_LABEL)
7141 if (GET_CODE (p) != JUMP_INSN)
7144 before_comparison = get_condition_for_loop (loop, p);
7145 if (before_comparison
7146 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7147 && GET_CODE (before_comparison) == LT
7148 && XEXP (before_comparison, 1) == const0_rtx
7149 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7150 && INTVAL (bl->biv->add_val) == -1)
7152 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7154 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7162 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7163 && INTVAL (bl->biv->add_val) > 0)
7165 /* Try to change inc to dec, so can apply above optimization. */
7167 all registers modified are induction variables or invariant,
7168 all memory references have non-overlapping addresses
7169 (obviously true if only one write)
7170 allow 2 insns for the compare/jump at the end of the loop. */
7171 /* Also, we must avoid any instructions which use both the reversed
7172 biv and another biv. Such instructions will fail if the loop is
7173 reversed. We meet this condition by requiring that either
7174 no_use_except_counting is true, or else that there is only
7176 int num_nonfixed_reads = 0;
7177 /* 1 if the iteration var is used only to count iterations. */
7178 int no_use_except_counting = 0;
7179 /* 1 if the loop has no memory store, or it has a single memory store
7180 which is reversible. */
7181 int reversible_mem_store = 1;
7183 if (bl->giv_count == 0 && ! loop->exit_count)
7185 rtx bivreg = regno_reg_rtx[bl->regno];
7187 /* If there are no givs for this biv, and the only exit is the
7188 fall through at the end of the loop, then
7189 see if perhaps there are no uses except to count. */
7190 no_use_except_counting = 1;
7191 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7194 rtx set = single_set (p);
7196 if (set && GET_CODE (SET_DEST (set)) == REG
7197 && REGNO (SET_DEST (set)) == bl->regno)
7198 /* An insn that sets the biv is okay. */
7200 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7201 || p == prev_nonnote_insn (loop_end))
7202 && reg_mentioned_p (bivreg, PATTERN (p)))
7204 /* If either of these insns uses the biv and sets a pseudo
7205 that has more than one usage, then the biv has uses
7206 other than counting since it's used to derive a value
7207 that is used more than one time. */
7208 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7210 if (regs->multiple_uses)
7212 no_use_except_counting = 0;
7216 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7218 no_use_except_counting = 0;
7224 if (no_use_except_counting)
7225 /* No need to worry about MEMs. */
7227 else if (loop_info->num_mem_sets <= 1)
7229 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7231 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7233 /* If the loop has a single store, and the destination address is
7234 invariant, then we can't reverse the loop, because this address
7235 might then have the wrong value at loop exit.
7236 This would work if the source was invariant also, however, in that
7237 case, the insn should have been moved out of the loop. */
7239 if (loop_info->num_mem_sets == 1)
7241 struct induction *v;
7243 reversible_mem_store
7244 = (! loop_info->unknown_address_altered
7245 && ! loop_info->unknown_constant_address_altered
7246 && ! loop_invariant_p (loop,
7247 XEXP (XEXP (loop_info->store_mems, 0),
7250 /* If the store depends on a register that is set after the
7251 store, it depends on the initial value, and is thus not
7253 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7255 if (v->giv_type == DEST_REG
7256 && reg_mentioned_p (v->dest_reg,
7257 PATTERN (loop_info->first_loop_store_insn))
7258 && loop_insn_first_p (loop_info->first_loop_store_insn,
7260 reversible_mem_store = 0;
7267 /* This code only acts for innermost loops. Also it simplifies
7268 the memory address check by only reversing loops with
7269 zero or one memory access.
7270 Two memory accesses could involve parts of the same array,
7271 and that can't be reversed.
7272 If the biv is used only for counting, than we don't need to worry
7273 about all these things. */
7275 if ((num_nonfixed_reads <= 1
7276 && ! loop_info->has_nonconst_call
7277 && ! loop_info->has_volatile
7278 && reversible_mem_store
7279 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7280 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7281 && (bl == ivs->list && bl->next == 0))
7282 || no_use_except_counting)
7286 /* Loop can be reversed. */
7287 if (loop_dump_stream)
7288 fprintf (loop_dump_stream, "Can reverse loop\n");
7290 /* Now check other conditions:
7292 The increment must be a constant, as must the initial value,
7293 and the comparison code must be LT.
7295 This test can probably be improved since +/- 1 in the constant
7296 can be obtained by changing LT to LE and vice versa; this is
7300 /* for constants, LE gets turned into LT */
7301 && (GET_CODE (comparison) == LT
7302 || (GET_CODE (comparison) == LE
7303 && no_use_except_counting)))
7305 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7306 rtx initial_value, comparison_value;
7308 enum rtx_code cmp_code;
7309 int comparison_const_width;
7310 unsigned HOST_WIDE_INT comparison_sign_mask;
7312 add_val = INTVAL (bl->biv->add_val);
7313 comparison_value = XEXP (comparison, 1);
7314 if (GET_MODE (comparison_value) == VOIDmode)
7315 comparison_const_width
7316 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7318 comparison_const_width
7319 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7320 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7321 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7322 comparison_sign_mask
7323 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7325 /* If the comparison value is not a loop invariant, then we
7326 can not reverse this loop.
7328 ??? If the insns which initialize the comparison value as
7329 a whole compute an invariant result, then we could move
7330 them out of the loop and proceed with loop reversal. */
7331 if (! loop_invariant_p (loop, comparison_value))
7334 if (GET_CODE (comparison_value) == CONST_INT)
7335 comparison_val = INTVAL (comparison_value);
7336 initial_value = bl->initial_value;
7338 /* Normalize the initial value if it is an integer and
7339 has no other use except as a counter. This will allow
7340 a few more loops to be reversed. */
7341 if (no_use_except_counting
7342 && GET_CODE (comparison_value) == CONST_INT
7343 && GET_CODE (initial_value) == CONST_INT)
7345 comparison_val = comparison_val - INTVAL (bl->initial_value);
7346 /* The code below requires comparison_val to be a multiple
7347 of add_val in order to do the loop reversal, so
7348 round up comparison_val to a multiple of add_val.
7349 Since comparison_value is constant, we know that the
7350 current comparison code is LT. */
7351 comparison_val = comparison_val + add_val - 1;
7353 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7354 /* We postpone overflow checks for COMPARISON_VAL here;
7355 even if there is an overflow, we might still be able to
7356 reverse the loop, if converting the loop exit test to
7358 initial_value = const0_rtx;
7361 /* First check if we can do a vanilla loop reversal. */
7362 if (initial_value == const0_rtx
7363 /* If we have a decrement_and_branch_on_count,
7364 prefer the NE test, since this will allow that
7365 instruction to be generated. Note that we must
7366 use a vanilla loop reversal if the biv is used to
7367 calculate a giv or has a non-counting use. */
7368 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7369 && defined (HAVE_decrement_and_branch_on_count)
7370 && (! (add_val == 1 && loop->vtop
7371 && (bl->biv_count == 0
7372 || no_use_except_counting)))
7374 && GET_CODE (comparison_value) == CONST_INT
7375 /* Now do postponed overflow checks on COMPARISON_VAL. */
7376 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7377 & comparison_sign_mask))
7379 /* Register will always be nonnegative, with value
7380 0 on last iteration */
7381 add_adjust = add_val;
7385 else if (add_val == 1 && loop->vtop
7386 && (bl->biv_count == 0
7387 || no_use_except_counting))
7395 if (GET_CODE (comparison) == LE)
7396 add_adjust -= add_val;
7398 /* If the initial value is not zero, or if the comparison
7399 value is not an exact multiple of the increment, then we
7400 can not reverse this loop. */
7401 if (initial_value == const0_rtx
7402 && GET_CODE (comparison_value) == CONST_INT)
7404 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7409 if (! no_use_except_counting || add_val != 1)
7413 final_value = comparison_value;
7415 /* Reset these in case we normalized the initial value
7416 and comparison value above. */
7417 if (GET_CODE (comparison_value) == CONST_INT
7418 && GET_CODE (initial_value) == CONST_INT)
7420 comparison_value = GEN_INT (comparison_val);
7422 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7424 bl->initial_value = initial_value;
7426 /* Save some info needed to produce the new insns. */
7427 reg = bl->biv->dest_reg;
7428 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7429 if (jump_label == pc_rtx)
7430 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7431 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7433 /* Set start_value; if this is not a CONST_INT, we need
7435 Initialize biv to start_value before loop start.
7436 The old initializing insn will be deleted as a
7437 dead store by flow.c. */
7438 if (initial_value == const0_rtx
7439 && GET_CODE (comparison_value) == CONST_INT)
7441 start_value = GEN_INT (comparison_val - add_adjust);
7442 loop_insn_hoist (loop, gen_move_insn (reg, start_value));
7444 else if (GET_CODE (initial_value) == CONST_INT)
7446 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7447 enum machine_mode mode = GET_MODE (reg);
7448 enum insn_code icode
7449 = add_optab->handlers[(int) mode].insn_code;
7451 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7452 || ! ((*insn_data[icode].operand[1].predicate)
7453 (comparison_value, mode))
7454 || ! ((*insn_data[icode].operand[2].predicate)
7458 = gen_rtx_PLUS (mode, comparison_value, offset);
7459 loop_insn_hoist (loop, (GEN_FCN (icode)
7460 (reg, comparison_value, offset)));
7461 if (GET_CODE (comparison) == LE)
7462 final_value = gen_rtx_PLUS (mode, comparison_value,
7465 else if (! add_adjust)
7467 enum machine_mode mode = GET_MODE (reg);
7468 enum insn_code icode
7469 = sub_optab->handlers[(int) mode].insn_code;
7470 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7471 || ! ((*insn_data[icode].operand[1].predicate)
7472 (comparison_value, mode))
7473 || ! ((*insn_data[icode].operand[2].predicate)
7474 (initial_value, mode)))
7477 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7478 loop_insn_hoist (loop, (GEN_FCN (icode)
7479 (reg, comparison_value,
7483 /* We could handle the other cases too, but it'll be
7484 better to have a testcase first. */
7487 /* We may not have a single insn which can increment a reg, so
7488 create a sequence to hold all the insns from expand_inc. */
7490 expand_inc (reg, new_add_val);
7491 tem = gen_sequence ();
7494 p = emit_insn_before (tem, bl->biv->insn);
7495 delete_insn (bl->biv->insn);
7497 /* Update biv info to reflect its new status. */
7499 bl->initial_value = start_value;
7500 bl->biv->add_val = new_add_val;
7502 /* Update loop info. */
7503 loop_info->initial_value = reg;
7504 loop_info->initial_equiv_value = reg;
7505 loop_info->final_value = const0_rtx;
7506 loop_info->final_equiv_value = const0_rtx;
7507 loop_info->comparison_value = const0_rtx;
7508 loop_info->comparison_code = cmp_code;
7509 loop_info->increment = new_add_val;
7511 /* Inc LABEL_NUSES so that delete_insn will
7512 not delete the label. */
7513 LABEL_NUSES (XEXP (jump_label, 0))++;
7515 /* Emit an insn after the end of the loop to set the biv's
7516 proper exit value if it is used anywhere outside the loop. */
7517 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7519 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7520 emit_insn_after (gen_move_insn (reg, final_value),
7523 /* Delete compare/branch at end of loop. */
7524 delete_insn (PREV_INSN (loop_end));
7525 if (compare_and_branch == 2)
7526 delete_insn (first_compare);
7528 /* Add new compare/branch insn at end of loop. */
7530 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7531 GET_MODE (reg), 0, 0,
7532 XEXP (jump_label, 0));
7533 tem = gen_sequence ();
7535 emit_jump_insn_before (tem, loop_end);
7537 for (tem = PREV_INSN (loop_end);
7538 tem && GET_CODE (tem) != JUMP_INSN;
7539 tem = PREV_INSN (tem))
7543 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7549 /* Increment of LABEL_NUSES done above. */
7550 /* Register is now always nonnegative,
7551 so add REG_NONNEG note to the branch. */
7552 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7558 /* No insn may reference both the reversed and another biv or it
7559 will fail (see comment near the top of the loop reversal
7561 Earlier on, we have verified that the biv has no use except
7562 counting, or it is the only biv in this function.
7563 However, the code that computes no_use_except_counting does
7564 not verify reg notes. It's possible to have an insn that
7565 references another biv, and has a REG_EQUAL note with an
7566 expression based on the reversed biv. To avoid this case,
7567 remove all REG_EQUAL notes based on the reversed biv
7569 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7573 rtx set = single_set (p);
7574 /* If this is a set of a GIV based on the reversed biv, any
7575 REG_EQUAL notes should still be correct. */
7577 || GET_CODE (SET_DEST (set)) != REG
7578 || (size_t) REGNO (SET_DEST (set)) >= ivs->n_regs
7579 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7580 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7581 for (pnote = ®_NOTES (p); *pnote;)
7583 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7584 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7586 *pnote = XEXP (*pnote, 1);
7588 pnote = &XEXP (*pnote, 1);
7592 /* Mark that this biv has been reversed. Each giv which depends
7593 on this biv, and which is also live past the end of the loop
7594 will have to be fixed up. */
7598 if (loop_dump_stream)
7600 fprintf (loop_dump_stream, "Reversed loop");
7602 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7604 fprintf (loop_dump_stream, "\n");
7615 /* Verify whether the biv BL appears to be eliminable,
7616 based on the insns in the loop that refer to it.
7618 If ELIMINATE_P is non-zero, actually do the elimination.
7620 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7621 determine whether invariant insns should be placed inside or at the
7622 start of the loop. */
7625 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7626 const struct loop *loop;
7627 struct iv_class *bl;
7629 int threshold, insn_count;
7631 struct loop_ivs *ivs = LOOP_IVS (loop);
7632 rtx reg = bl->biv->dest_reg;
7633 rtx loop_start = loop->start;
7634 rtx loop_end = loop->end;
7637 /* Scan all insns in the loop, stopping if we find one that uses the
7638 biv in a way that we cannot eliminate. */
7640 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7642 enum rtx_code code = GET_CODE (p);
7643 rtx where = threshold >= insn_count ? loop_start : p;
7645 /* If this is a libcall that sets a giv, skip ahead to its end. */
7646 if (GET_RTX_CLASS (code) == 'i')
7648 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7652 rtx last = XEXP (note, 0);
7653 rtx set = single_set (last);
7655 if (set && GET_CODE (SET_DEST (set)) == REG)
7657 unsigned int regno = REGNO (SET_DEST (set));
7659 if (regno < ivs->n_regs
7660 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7661 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7666 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7667 && reg_mentioned_p (reg, PATTERN (p))
7668 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7669 eliminate_p, where))
7671 if (loop_dump_stream)
7672 fprintf (loop_dump_stream,
7673 "Cannot eliminate biv %d: biv used in insn %d.\n",
7674 bl->regno, INSN_UID (p));
7681 if (loop_dump_stream)
7682 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7683 bl->regno, eliminate_p ? "was" : "can be");
7690 /* INSN and REFERENCE are instructions in the same insn chain.
7691 Return non-zero if INSN is first. */
7694 loop_insn_first_p (insn, reference)
7695 rtx insn, reference;
7699 for (p = insn, q = reference;;)
7701 /* Start with test for not first so that INSN == REFERENCE yields not
7703 if (q == insn || ! p)
7705 if (p == reference || ! q)
7708 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7709 previous insn, hence the <= comparison below does not work if
7711 if (INSN_UID (p) < max_uid_for_loop
7712 && INSN_UID (q) < max_uid_for_loop
7713 && GET_CODE (p) != NOTE)
7714 return INSN_LUID (p) <= INSN_LUID (q);
7716 if (INSN_UID (p) >= max_uid_for_loop
7717 || GET_CODE (p) == NOTE)
7719 if (INSN_UID (q) >= max_uid_for_loop)
7724 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7725 the offset that we have to take into account due to auto-increment /
7726 div derivation is zero. */
7728 biv_elimination_giv_has_0_offset (biv, giv, insn)
7729 struct induction *biv, *giv;
7732 /* If the giv V had the auto-inc address optimization applied
7733 to it, and INSN occurs between the giv insn and the biv
7734 insn, then we'd have to adjust the value used here.
7735 This is rare, so we don't bother to make this possible. */
7736 if (giv->auto_inc_opt
7737 && ((loop_insn_first_p (giv->insn, insn)
7738 && loop_insn_first_p (insn, biv->insn))
7739 || (loop_insn_first_p (biv->insn, insn)
7740 && loop_insn_first_p (insn, giv->insn))))
7746 /* If BL appears in X (part of the pattern of INSN), see if we can
7747 eliminate its use. If so, return 1. If not, return 0.
7749 If BIV does not appear in X, return 1.
7751 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7752 where extra insns should be added. Depending on how many items have been
7753 moved out of the loop, it will either be before INSN or at the start of
7757 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7758 const struct loop *loop;
7760 struct iv_class *bl;
7764 enum rtx_code code = GET_CODE (x);
7765 rtx reg = bl->biv->dest_reg;
7766 enum machine_mode mode = GET_MODE (reg);
7767 struct induction *v;
7779 /* If we haven't already been able to do something with this BIV,
7780 we can't eliminate it. */
7786 /* If this sets the BIV, it is not a problem. */
7787 if (SET_DEST (x) == reg)
7790 /* If this is an insn that defines a giv, it is also ok because
7791 it will go away when the giv is reduced. */
7792 for (v = bl->giv; v; v = v->next_iv)
7793 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7797 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7799 /* Can replace with any giv that was reduced and
7800 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7801 Require a constant for MULT_VAL, so we know it's nonzero.
7802 ??? We disable this optimization to avoid potential
7805 for (v = bl->giv; v; v = v->next_iv)
7806 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7807 && v->add_val == const0_rtx
7808 && ! v->ignore && ! v->maybe_dead && v->always_computable
7812 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7818 /* If the giv has the opposite direction of change,
7819 then reverse the comparison. */
7820 if (INTVAL (v->mult_val) < 0)
7821 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7822 const0_rtx, v->new_reg);
7826 /* We can probably test that giv's reduced reg. */
7827 if (validate_change (insn, &SET_SRC (x), new, 0))
7831 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7832 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7833 Require a constant for MULT_VAL, so we know it's nonzero.
7834 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7835 overflow problem. */
7837 for (v = bl->giv; v; v = v->next_iv)
7838 if (GET_CODE (v->mult_val) == CONST_INT
7839 && v->mult_val != const0_rtx
7840 && ! v->ignore && ! v->maybe_dead && v->always_computable
7842 && (GET_CODE (v->add_val) == SYMBOL_REF
7843 || GET_CODE (v->add_val) == LABEL_REF
7844 || GET_CODE (v->add_val) == CONST
7845 || (GET_CODE (v->add_val) == REG
7846 && REG_POINTER (v->add_val))))
7848 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7854 /* If the giv has the opposite direction of change,
7855 then reverse the comparison. */
7856 if (INTVAL (v->mult_val) < 0)
7857 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
7860 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
7861 copy_rtx (v->add_val));
7863 /* Replace biv with the giv's reduced register. */
7864 update_reg_last_use (v->add_val, insn);
7865 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7868 /* Insn doesn't support that constant or invariant. Copy it
7869 into a register (it will be a loop invariant.) */
7870 tem = gen_reg_rtx (GET_MODE (v->new_reg));
7872 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
7875 /* Substitute the new register for its invariant value in
7876 the compare expression. */
7877 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
7878 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7887 case GT: case GE: case GTU: case GEU:
7888 case LT: case LE: case LTU: case LEU:
7889 /* See if either argument is the biv. */
7890 if (XEXP (x, 0) == reg)
7891 arg = XEXP (x, 1), arg_operand = 1;
7892 else if (XEXP (x, 1) == reg)
7893 arg = XEXP (x, 0), arg_operand = 0;
7897 if (CONSTANT_P (arg))
7899 /* First try to replace with any giv that has constant positive
7900 mult_val and constant add_val. We might be able to support
7901 negative mult_val, but it seems complex to do it in general. */
7903 for (v = bl->giv; v; v = v->next_iv)
7904 if (GET_CODE (v->mult_val) == CONST_INT
7905 && INTVAL (v->mult_val) > 0
7906 && (GET_CODE (v->add_val) == SYMBOL_REF
7907 || GET_CODE (v->add_val) == LABEL_REF
7908 || GET_CODE (v->add_val) == CONST
7909 || (GET_CODE (v->add_val) == REG
7910 && REG_POINTER (v->add_val)))
7911 && ! v->ignore && ! v->maybe_dead && v->always_computable
7914 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7920 /* Replace biv with the giv's reduced reg. */
7921 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
7923 /* If all constants are actually constant integers and
7924 the derived constant can be directly placed in the COMPARE,
7926 if (GET_CODE (arg) == CONST_INT
7927 && GET_CODE (v->mult_val) == CONST_INT
7928 && GET_CODE (v->add_val) == CONST_INT)
7930 validate_change (insn, &XEXP (x, arg_operand),
7931 GEN_INT (INTVAL (arg)
7932 * INTVAL (v->mult_val)
7933 + INTVAL (v->add_val)), 1);
7937 /* Otherwise, load it into a register. */
7938 tem = gen_reg_rtx (mode);
7939 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7940 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7942 if (apply_change_group ())
7946 /* Look for giv with positive constant mult_val and nonconst add_val.
7947 Insert insns to calculate new compare value.
7948 ??? Turn this off due to possible overflow. */
7950 for (v = bl->giv; v; v = v->next_iv)
7951 if (GET_CODE (v->mult_val) == CONST_INT
7952 && INTVAL (v->mult_val) > 0
7953 && ! v->ignore && ! v->maybe_dead && v->always_computable
7959 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7965 tem = gen_reg_rtx (mode);
7967 /* Replace biv with giv's reduced register. */
7968 validate_change (insn, &XEXP (x, 1 - arg_operand),
7971 /* Compute value to compare against. */
7972 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7973 /* Use it in this insn. */
7974 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7975 if (apply_change_group ())
7979 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
7981 if (loop_invariant_p (loop, arg) == 1)
7983 /* Look for giv with constant positive mult_val and nonconst
7984 add_val. Insert insns to compute new compare value.
7985 ??? Turn this off due to possible overflow. */
7987 for (v = bl->giv; v; v = v->next_iv)
7988 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
7989 && ! v->ignore && ! v->maybe_dead && v->always_computable
7995 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8001 tem = gen_reg_rtx (mode);
8003 /* Replace biv with giv's reduced register. */
8004 validate_change (insn, &XEXP (x, 1 - arg_operand),
8007 /* Compute value to compare against. */
8008 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8010 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8011 if (apply_change_group ())
8016 /* This code has problems. Basically, you can't know when
8017 seeing if we will eliminate BL, whether a particular giv
8018 of ARG will be reduced. If it isn't going to be reduced,
8019 we can't eliminate BL. We can try forcing it to be reduced,
8020 but that can generate poor code.
8022 The problem is that the benefit of reducing TV, below should
8023 be increased if BL can actually be eliminated, but this means
8024 we might have to do a topological sort of the order in which
8025 we try to process biv. It doesn't seem worthwhile to do
8026 this sort of thing now. */
8029 /* Otherwise the reg compared with had better be a biv. */
8030 if (GET_CODE (arg) != REG
8031 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8034 /* Look for a pair of givs, one for each biv,
8035 with identical coefficients. */
8036 for (v = bl->giv; v; v = v->next_iv)
8038 struct induction *tv;
8040 if (v->ignore || v->maybe_dead || v->mode != mode)
8043 for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
8045 if (! tv->ignore && ! tv->maybe_dead
8046 && rtx_equal_p (tv->mult_val, v->mult_val)
8047 && rtx_equal_p (tv->add_val, v->add_val)
8048 && tv->mode == mode)
8050 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8056 /* Replace biv with its giv's reduced reg. */
8057 XEXP (x, 1 - arg_operand) = v->new_reg;
8058 /* Replace other operand with the other giv's
8060 XEXP (x, arg_operand) = tv->new_reg;
8067 /* If we get here, the biv can't be eliminated. */
8071 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8072 biv is used in it, since it will be replaced. */
8073 for (v = bl->giv; v; v = v->next_iv)
8074 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8082 /* See if any subexpression fails elimination. */
8083 fmt = GET_RTX_FORMAT (code);
8084 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8089 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8090 eliminate_p, where))
8095 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8096 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8097 eliminate_p, where))
8106 /* Return nonzero if the last use of REG
8107 is in an insn following INSN in the same basic block. */
8110 last_use_this_basic_block (reg, insn)
8116 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8119 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8125 /* Called via `note_stores' to record the initial value of a biv. Here we
8126 just record the location of the set and process it later. */
8129 record_initial (dest, set, data)
8132 void *data ATTRIBUTE_UNUSED;
8134 struct loop_ivs *ivs = (struct loop_ivs *) data;
8135 struct iv_class *bl;
8137 if (GET_CODE (dest) != REG
8138 || REGNO (dest) >= ivs->n_regs
8139 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8142 bl = REG_IV_CLASS (ivs, REGNO (dest));
8144 /* If this is the first set found, record it. */
8145 if (bl->init_insn == 0)
8147 bl->init_insn = note_insn;
8152 /* If any of the registers in X are "old" and currently have a last use earlier
8153 than INSN, update them to have a last use of INSN. Their actual last use
8154 will be the previous insn but it will not have a valid uid_luid so we can't
8158 update_reg_last_use (x, insn)
8162 /* Check for the case where INSN does not have a valid luid. In this case,
8163 there is no need to modify the regno_last_uid, as this can only happen
8164 when code is inserted after the loop_end to set a pseudo's final value,
8165 and hence this insn will never be the last use of x. */
8166 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8167 && INSN_UID (insn) < max_uid_for_loop
8168 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8169 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8173 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8174 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8177 update_reg_last_use (XEXP (x, i), insn);
8178 else if (fmt[i] == 'E')
8179 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8180 update_reg_last_use (XVECEXP (x, i, j), insn);
8185 /* Given an insn INSN and condition COND, return the condition in a
8186 canonical form to simplify testing by callers. Specifically:
8188 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8189 (2) Both operands will be machine operands; (cc0) will have been replaced.
8190 (3) If an operand is a constant, it will be the second operand.
8191 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8192 for GE, GEU, and LEU.
8194 If the condition cannot be understood, or is an inequality floating-point
8195 comparison which needs to be reversed, 0 will be returned.
8197 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8199 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8200 insn used in locating the condition was found. If a replacement test
8201 of the condition is desired, it should be placed in front of that
8202 insn and we will be sure that the inputs are still valid.
8204 If WANT_REG is non-zero, we wish the condition to be relative to that
8205 register, if possible. Therefore, do not canonicalize the condition
8209 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8221 int reverse_code = 0;
8222 int did_reverse_condition = 0;
8223 enum machine_mode mode;
8225 code = GET_CODE (cond);
8226 mode = GET_MODE (cond);
8227 op0 = XEXP (cond, 0);
8228 op1 = XEXP (cond, 1);
8232 code = reverse_condition (code);
8233 did_reverse_condition ^= 1;
8239 /* If we are comparing a register with zero, see if the register is set
8240 in the previous insn to a COMPARE or a comparison operation. Perform
8241 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8244 while (GET_RTX_CLASS (code) == '<'
8245 && op1 == CONST0_RTX (GET_MODE (op0))
8248 /* Set non-zero when we find something of interest. */
8252 /* If comparison with cc0, import actual comparison from compare
8256 if ((prev = prev_nonnote_insn (prev)) == 0
8257 || GET_CODE (prev) != INSN
8258 || (set = single_set (prev)) == 0
8259 || SET_DEST (set) != cc0_rtx)
8262 op0 = SET_SRC (set);
8263 op1 = CONST0_RTX (GET_MODE (op0));
8269 /* If this is a COMPARE, pick up the two things being compared. */
8270 if (GET_CODE (op0) == COMPARE)
8272 op1 = XEXP (op0, 1);
8273 op0 = XEXP (op0, 0);
8276 else if (GET_CODE (op0) != REG)
8279 /* Go back to the previous insn. Stop if it is not an INSN. We also
8280 stop if it isn't a single set or if it has a REG_INC note because
8281 we don't want to bother dealing with it. */
8283 if ((prev = prev_nonnote_insn (prev)) == 0
8284 || GET_CODE (prev) != INSN
8285 || FIND_REG_INC_NOTE (prev, 0)
8286 || (set = single_set (prev)) == 0)
8289 /* If this is setting OP0, get what it sets it to if it looks
8291 if (rtx_equal_p (SET_DEST (set), op0))
8293 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8295 /* ??? We may not combine comparisons done in a CCmode with
8296 comparisons not done in a CCmode. This is to aid targets
8297 like Alpha that have an IEEE compliant EQ instruction, and
8298 a non-IEEE compliant BEQ instruction. The use of CCmode is
8299 actually artificial, simply to prevent the combination, but
8300 should not affect other platforms.
8302 However, we must allow VOIDmode comparisons to match either
8303 CCmode or non-CCmode comparison, because some ports have
8304 modeless comparisons inside branch patterns.
8306 ??? This mode check should perhaps look more like the mode check
8307 in simplify_comparison in combine. */
8309 if ((GET_CODE (SET_SRC (set)) == COMPARE
8312 && GET_MODE_CLASS (inner_mode) == MODE_INT
8313 && (GET_MODE_BITSIZE (inner_mode)
8314 <= HOST_BITS_PER_WIDE_INT)
8315 && (STORE_FLAG_VALUE
8316 & ((HOST_WIDE_INT) 1
8317 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8318 #ifdef FLOAT_STORE_FLAG_VALUE
8320 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8321 && (REAL_VALUE_NEGATIVE
8322 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8325 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8326 && (((GET_MODE_CLASS (mode) == MODE_CC)
8327 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8328 || mode == VOIDmode || inner_mode == VOIDmode))
8330 else if (((code == EQ
8332 && (GET_MODE_BITSIZE (inner_mode)
8333 <= HOST_BITS_PER_WIDE_INT)
8334 && GET_MODE_CLASS (inner_mode) == MODE_INT
8335 && (STORE_FLAG_VALUE
8336 & ((HOST_WIDE_INT) 1
8337 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8338 #ifdef FLOAT_STORE_FLAG_VALUE
8340 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8341 && (REAL_VALUE_NEGATIVE
8342 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8345 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8346 && (((GET_MODE_CLASS (mode) == MODE_CC)
8347 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8348 || mode == VOIDmode || inner_mode == VOIDmode))
8351 /* We might have reversed a LT to get a GE here. But this wasn't
8352 actually the comparison of data, so we don't flag that we
8353 have had to reverse the condition. */
8354 did_reverse_condition ^= 1;
8362 else if (reg_set_p (op0, prev))
8363 /* If this sets OP0, but not directly, we have to give up. */
8368 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8369 code = GET_CODE (x);
8372 code = reverse_condition (code);
8373 if (code == UNKNOWN)
8375 did_reverse_condition ^= 1;
8379 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8385 /* If constant is first, put it last. */
8386 if (CONSTANT_P (op0))
8387 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8389 /* If OP0 is the result of a comparison, we weren't able to find what
8390 was really being compared, so fail. */
8391 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8394 /* Canonicalize any ordered comparison with integers involving equality
8395 if we can do computations in the relevant mode and we do not
8398 if (GET_CODE (op1) == CONST_INT
8399 && GET_MODE (op0) != VOIDmode
8400 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8402 HOST_WIDE_INT const_val = INTVAL (op1);
8403 unsigned HOST_WIDE_INT uconst_val = const_val;
8404 unsigned HOST_WIDE_INT max_val
8405 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8410 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8411 code = LT, op1 = GEN_INT (const_val + 1);
8414 /* When cross-compiling, const_val might be sign-extended from
8415 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8417 if ((HOST_WIDE_INT) (const_val & max_val)
8418 != (((HOST_WIDE_INT) 1
8419 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8420 code = GT, op1 = GEN_INT (const_val - 1);
8424 if (uconst_val < max_val)
8425 code = LTU, op1 = GEN_INT (uconst_val + 1);
8429 if (uconst_val != 0)
8430 code = GTU, op1 = GEN_INT (uconst_val - 1);
8438 /* If this was floating-point and we reversed anything other than an
8439 EQ or NE or (UN)ORDERED, return zero. */
8440 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8441 && did_reverse_condition
8442 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8444 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8448 /* Never return CC0; return zero instead. */
8453 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8456 /* Given a jump insn JUMP, return the condition that will cause it to branch
8457 to its JUMP_LABEL. If the condition cannot be understood, or is an
8458 inequality floating-point comparison which needs to be reversed, 0 will
8461 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8462 insn used in locating the condition was found. If a replacement test
8463 of the condition is desired, it should be placed in front of that
8464 insn and we will be sure that the inputs are still valid. */
8467 get_condition (jump, earliest)
8475 /* If this is not a standard conditional jump, we can't parse it. */
8476 if (GET_CODE (jump) != JUMP_INSN
8477 || ! any_condjump_p (jump))
8479 set = pc_set (jump);
8481 cond = XEXP (SET_SRC (set), 0);
8483 /* If this branches to JUMP_LABEL when the condition is false, reverse
8486 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8487 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8489 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8492 /* Similar to above routine, except that we also put an invariant last
8493 unless both operands are invariants. */
8496 get_condition_for_loop (loop, x)
8497 const struct loop *loop;
8500 rtx comparison = get_condition (x, NULL_PTR);
8503 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8504 || loop_invariant_p (loop, XEXP (comparison, 1)))
8507 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8508 XEXP (comparison, 1), XEXP (comparison, 0));
8511 /* Scan the function and determine whether it has indirect (computed) jumps.
8513 This is taken mostly from flow.c; similar code exists elsewhere
8514 in the compiler. It may be useful to put this into rtlanal.c. */
8516 indirect_jump_in_function_p (start)
8521 for (insn = start; insn; insn = NEXT_INSN (insn))
8522 if (computed_jump_p (insn))
8528 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8529 documentation for LOOP_MEMS for the definition of `appropriate'.
8530 This function is called from prescan_loop via for_each_rtx. */
8533 insert_loop_mem (mem, data)
8535 void *data ATTRIBUTE_UNUSED;
8537 struct loop_info *loop_info = data;
8544 switch (GET_CODE (m))
8550 /* We're not interested in MEMs that are only clobbered. */
8554 /* We're not interested in the MEM associated with a
8555 CONST_DOUBLE, so there's no need to traverse into this. */
8559 /* We're not interested in any MEMs that only appear in notes. */
8563 /* This is not a MEM. */
8567 /* See if we've already seen this MEM. */
8568 for (i = 0; i < loop_info->mems_idx; ++i)
8569 if (rtx_equal_p (m, loop_info->mems[i].mem))
8571 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8572 /* The modes of the two memory accesses are different. If
8573 this happens, something tricky is going on, and we just
8574 don't optimize accesses to this MEM. */
8575 loop_info->mems[i].optimize = 0;
8580 /* Resize the array, if necessary. */
8581 if (loop_info->mems_idx == loop_info->mems_allocated)
8583 if (loop_info->mems_allocated != 0)
8584 loop_info->mems_allocated *= 2;
8586 loop_info->mems_allocated = 32;
8588 loop_info->mems = (loop_mem_info *)
8589 xrealloc (loop_info->mems,
8590 loop_info->mems_allocated * sizeof (loop_mem_info));
8593 /* Actually insert the MEM. */
8594 loop_info->mems[loop_info->mems_idx].mem = m;
8595 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8596 because we can't put it in a register. We still store it in the
8597 table, though, so that if we see the same address later, but in a
8598 non-BLK mode, we'll not think we can optimize it at that point. */
8599 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8600 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8601 ++loop_info->mems_idx;
8607 /* Allocate REGS->ARRAY or reallocate it if it is too small.
8609 Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
8610 register that is modified by an insn between FROM and TO. If the
8611 value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
8612 more, stop incrementing it, to avoid overflow.
8614 Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
8615 register I is used, if it is only used once. Otherwise, it is set
8616 to 0 (for no uses) or const0_rtx for more than one use. This
8617 parameter may be zero, in which case this processing is not done.
8619 Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
8620 optimize register I.
8622 Store in *COUNT_PTR the number of actual instructions
8623 in the loop. We use this to decide what is worth moving out. */
8626 loop_regs_scan (loop, extra_size, count_ptr)
8627 const struct loop *loop;
8631 struct loop_regs *regs = LOOP_REGS (loop);
8633 /* last_set[n] is nonzero iff reg n has been set in the current
8634 basic block. In that case, it is the insn that last set reg n. */
8640 old_nregs = regs->num;
8641 regs->num = max_reg_num ();
8643 /* Grow the regs array if not allocated or too small. */
8644 if (regs->num >= regs->size)
8646 regs->size = regs->num + extra_size;
8648 regs->array = (struct loop_reg *)
8649 xrealloc (regs->array, regs->size * sizeof (*regs->array));
8651 /* Zero the new elements. */
8652 memset (regs->array + old_nregs, 0,
8653 (regs->size - old_nregs) * sizeof (*regs->array));
8656 /* Clear previously scanned fields but do not clear n_times_set. */
8657 for (i = 0; i < old_nregs; i++)
8659 regs->array[i].set_in_loop = 0;
8660 regs->array[i].may_not_optimize = 0;
8661 regs->array[i].single_usage = NULL_RTX;
8664 last_set = (rtx *) xcalloc (regs->num, sizeof (rtx));
8666 /* Scan the loop, recording register usage. */
8667 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
8668 insn = NEXT_INSN (insn))
8674 /* Record registers that have exactly one use. */
8675 find_single_use_in_loop (regs, insn, PATTERN (insn));
8677 /* Include uses in REG_EQUAL notes. */
8678 if (REG_NOTES (insn))
8679 find_single_use_in_loop (regs, insn, REG_NOTES (insn));
8681 if (GET_CODE (PATTERN (insn)) == SET
8682 || GET_CODE (PATTERN (insn)) == CLOBBER)
8683 count_one_set (regs, insn, PATTERN (insn), last_set);
8684 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
8687 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
8688 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
8693 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
8694 memset (last_set, 0, regs->num * sizeof (rtx));
8697 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8699 regs->array[i].may_not_optimize = 1;
8700 regs->array[i].set_in_loop = 1;
8703 #ifdef AVOID_CCMODE_COPIES
8704 /* Don't try to move insns which set CC registers if we should not
8705 create CCmode register copies. */
8706 for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8707 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8708 regs->array[i].may_not_optimize = 1;
8711 /* Set regs->array[I].n_times_set for the new registers. */
8712 for (i = old_nregs; i < regs->num; i++)
8713 regs->array[i].n_times_set = regs->array[i].set_in_loop;
8720 /* Move MEMs into registers for the duration of the loop. */
8724 const struct loop *loop;
8726 struct loop_info *loop_info = LOOP_INFO (loop);
8727 struct loop_regs *regs = LOOP_REGS (loop);
8728 int maybe_never = 0;
8731 rtx label = NULL_RTX;
8733 /* Nonzero if the next instruction may never be executed. */
8734 int next_maybe_never = 0;
8735 int last_max_reg = max_reg_num ();
8737 if (loop_info->mems_idx == 0)
8740 /* We cannot use next_label here because it skips over normal insns. */
8741 end_label = next_nonnote_insn (loop->end);
8742 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8743 end_label = NULL_RTX;
8745 /* Check to see if it's possible that some instructions in the loop are
8746 never executed. Also check if there is a goto out of the loop other
8747 than right after the end of the loop. */
8748 for (p = next_insn_in_loop (loop, loop->scan_start);
8749 p != NULL_RTX && ! maybe_never;
8750 p = next_insn_in_loop (loop, p))
8752 if (GET_CODE (p) == CODE_LABEL)
8754 else if (GET_CODE (p) == JUMP_INSN
8755 /* If we enter the loop in the middle, and scan
8756 around to the beginning, don't set maybe_never
8757 for that. This must be an unconditional jump,
8758 otherwise the code at the top of the loop might
8759 never be executed. Unconditional jumps are
8760 followed a by barrier then loop end. */
8761 && ! (GET_CODE (p) == JUMP_INSN
8762 && JUMP_LABEL (p) == loop->top
8763 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8764 && any_uncondjump_p (p)))
8766 /* If this is a jump outside of the loop but not right
8767 after the end of the loop, we would have to emit new fixup
8768 sequences for each such label. */
8769 if (JUMP_LABEL (p) != end_label
8770 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8771 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8772 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8775 if (!any_condjump_p (p))
8776 /* Something complicated. */
8779 /* If there are any more instructions in the loop, they
8780 might not be reached. */
8781 next_maybe_never = 1;
8783 else if (next_maybe_never)
8787 /* Find start of the extended basic block that enters the loop. */
8788 for (p = loop->start;
8789 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8795 /* Build table of mems that get set to constant values before the
8797 for (; p != loop->start; p = NEXT_INSN (p))
8798 cselib_process_insn (p);
8800 /* Actually move the MEMs. */
8801 for (i = 0; i < loop_info->mems_idx; ++i)
8803 regset_head load_copies;
8804 regset_head store_copies;
8807 rtx mem = loop_info->mems[i].mem;
8810 if (MEM_VOLATILE_P (mem)
8811 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8812 /* There's no telling whether or not MEM is modified. */
8813 loop_info->mems[i].optimize = 0;
8815 /* Go through the MEMs written to in the loop to see if this
8816 one is aliased by one of them. */
8817 mem_list_entry = loop_info->store_mems;
8818 while (mem_list_entry)
8820 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8822 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8825 /* MEM is indeed aliased by this store. */
8826 loop_info->mems[i].optimize = 0;
8829 mem_list_entry = XEXP (mem_list_entry, 1);
8832 if (flag_float_store && written
8833 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8834 loop_info->mems[i].optimize = 0;
8836 /* If this MEM is written to, we must be sure that there
8837 are no reads from another MEM that aliases this one. */
8838 if (loop_info->mems[i].optimize && written)
8842 for (j = 0; j < loop_info->mems_idx; ++j)
8846 else if (true_dependence (mem,
8848 loop_info->mems[j].mem,
8851 /* It's not safe to hoist loop_info->mems[i] out of
8852 the loop because writes to it might not be
8853 seen by reads from loop_info->mems[j]. */
8854 loop_info->mems[i].optimize = 0;
8860 if (maybe_never && may_trap_p (mem))
8861 /* We can't access the MEM outside the loop; it might
8862 cause a trap that wouldn't have happened otherwise. */
8863 loop_info->mems[i].optimize = 0;
8865 if (!loop_info->mems[i].optimize)
8866 /* We thought we were going to lift this MEM out of the
8867 loop, but later discovered that we could not. */
8870 INIT_REG_SET (&load_copies);
8871 INIT_REG_SET (&store_copies);
8873 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8874 order to keep scan_loop from moving stores to this MEM
8875 out of the loop just because this REG is neither a
8876 user-variable nor used in the loop test. */
8877 reg = gen_reg_rtx (GET_MODE (mem));
8878 REG_USERVAR_P (reg) = 1;
8879 loop_info->mems[i].reg = reg;
8881 /* Now, replace all references to the MEM with the
8882 corresponding pesudos. */
8884 for (p = next_insn_in_loop (loop, loop->scan_start);
8886 p = next_insn_in_loop (loop, p))
8892 set = single_set (p);
8894 /* See if this copies the mem into a register that isn't
8895 modified afterwards. We'll try to do copy propagation
8896 a little further on. */
8898 /* @@@ This test is _way_ too conservative. */
8900 && GET_CODE (SET_DEST (set)) == REG
8901 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
8902 && REGNO (SET_DEST (set)) < last_max_reg
8903 && regs->array[REGNO (SET_DEST (set))].n_times_set == 1
8904 && rtx_equal_p (SET_SRC (set), mem))
8905 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
8907 /* See if this copies the mem from a register that isn't
8908 modified afterwards. We'll try to remove the
8909 redundant copy later on by doing a little register
8910 renaming and copy propagation. This will help
8911 to untangle things for the BIV detection code. */
8914 && GET_CODE (SET_SRC (set)) == REG
8915 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
8916 && REGNO (SET_SRC (set)) < last_max_reg
8917 && regs->array[REGNO (SET_SRC (set))].n_times_set == 1
8918 && rtx_equal_p (SET_DEST (set), mem))
8919 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
8921 /* Replace the memory reference with the shadow register. */
8922 replace_loop_mems (p, loop_info->mems[i].mem,
8923 loop_info->mems[i].reg);
8926 if (GET_CODE (p) == CODE_LABEL
8927 || GET_CODE (p) == JUMP_INSN)
8931 if (! apply_change_group ())
8932 /* We couldn't replace all occurrences of the MEM. */
8933 loop_info->mems[i].optimize = 0;
8936 /* Load the memory immediately before LOOP->START, which is
8937 the NOTE_LOOP_BEG. */
8938 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
8942 struct elt_loc_list *const_equiv = 0;
8946 struct elt_loc_list *equiv;
8947 struct elt_loc_list *best_equiv = 0;
8948 for (equiv = e->locs; equiv; equiv = equiv->next)
8950 if (CONSTANT_P (equiv->loc))
8951 const_equiv = equiv;
8952 else if (GET_CODE (equiv->loc) == REG
8953 /* Extending hard register lifetimes cuases crash
8954 on SRC targets. Doing so on non-SRC is
8955 probably also not good idea, since we most
8956 probably have pseudoregister equivalence as
8958 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
8961 /* Use the constant equivalence if that is cheap enough. */
8963 best_equiv = const_equiv;
8964 else if (const_equiv
8965 && (rtx_cost (const_equiv->loc, SET)
8966 <= rtx_cost (best_equiv->loc, SET)))
8968 best_equiv = const_equiv;
8972 /* If best_equiv is nonzero, we know that MEM is set to a
8973 constant or register before the loop. We will use this
8974 knowledge to initialize the shadow register with that
8975 constant or reg rather than by loading from MEM. */
8977 best = copy_rtx (best_equiv->loc);
8979 set = gen_move_insn (reg, best);
8980 set = loop_insn_hoist (loop, set);
8982 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
8983 copy_rtx (const_equiv->loc),
8988 if (label == NULL_RTX)
8990 label = gen_label_rtx ();
8991 emit_label_after (label, loop->end);
8994 /* Store the memory immediately after END, which is
8995 the NOTE_LOOP_END. */
8996 set = gen_move_insn (copy_rtx (mem), reg);
8997 emit_insn_after (set, label);
9000 if (loop_dump_stream)
9002 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9003 REGNO (reg), (written ? "r/w" : "r/o"));
9004 print_rtl (loop_dump_stream, mem);
9005 fputc ('\n', loop_dump_stream);
9008 /* Attempt a bit of copy propagation. This helps untangle the
9009 data flow, and enables {basic,general}_induction_var to find
9011 EXECUTE_IF_SET_IN_REG_SET
9012 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9014 try_copy_prop (loop, reg, j);
9016 CLEAR_REG_SET (&load_copies);
9018 EXECUTE_IF_SET_IN_REG_SET
9019 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9021 try_swap_copy_prop (loop, reg, j);
9023 CLEAR_REG_SET (&store_copies);
9027 if (label != NULL_RTX && end_label != NULL_RTX)
9029 /* Now, we need to replace all references to the previous exit
9030 label with the new one. */
9035 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9037 for_each_rtx (&p, replace_label, &rr);
9039 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9040 field. This is not handled by for_each_rtx because it doesn't
9041 handle unprinted ('0') fields. We need to update JUMP_LABEL
9042 because the immediately following unroll pass will use it.
9043 replace_label would not work anyways, because that only handles
9045 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9046 JUMP_LABEL (p) = label;
9053 /* For communication between note_reg_stored and its caller. */
9054 struct note_reg_stored_arg
9060 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9063 note_reg_stored (x, setter, arg)
9064 rtx x, setter ATTRIBUTE_UNUSED;
9067 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9072 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9073 There must be exactly one insn that sets this pseudo; it will be
9074 deleted if all replacements succeed and we can prove that the register
9075 is not used after the loop. */
9078 try_copy_prop (loop, replacement, regno)
9079 const struct loop *loop;
9083 /* This is the reg that we are copying from. */
9084 rtx reg_rtx = regno_reg_rtx[regno];
9087 /* These help keep track of whether we replaced all uses of the reg. */
9088 int replaced_last = 0;
9089 int store_is_first = 0;
9091 for (insn = next_insn_in_loop (loop, loop->scan_start);
9093 insn = next_insn_in_loop (loop, insn))
9097 /* Only substitute within one extended basic block from the initializing
9099 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9102 if (! INSN_P (insn))
9105 /* Is this the initializing insn? */
9106 set = single_set (insn);
9108 && GET_CODE (SET_DEST (set)) == REG
9109 && REGNO (SET_DEST (set)) == regno)
9115 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9119 /* Only substitute after seeing the initializing insn. */
9120 if (init_insn && insn != init_insn)
9122 struct note_reg_stored_arg arg;
9124 replace_loop_regs (insn, reg_rtx, replacement);
9125 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9128 /* Stop replacing when REPLACEMENT is modified. */
9129 arg.reg = replacement;
9131 note_stores (PATTERN (insn), note_reg_stored, &arg);
9138 if (apply_change_group ())
9140 if (loop_dump_stream)
9141 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9142 if (store_is_first && replaced_last)
9144 PUT_CODE (init_insn, NOTE);
9145 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9146 if (loop_dump_stream)
9147 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9148 INSN_UID (init_insn));
9150 if (loop_dump_stream)
9151 fprintf (loop_dump_stream, ".\n");
9155 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9156 loop LOOP if the order of the sets of these registers can be
9157 swapped. There must be exactly one insn within the loop that sets
9158 this pseudo followed immediately by a move insn that sets
9159 REPLACEMENT with REGNO. */
9161 try_swap_copy_prop (loop, replacement, regno)
9162 const struct loop *loop;
9168 unsigned int new_regno;
9170 new_regno = REGNO (replacement);
9172 for (insn = next_insn_in_loop (loop, loop->scan_start);
9174 insn = next_insn_in_loop (loop, insn))
9176 /* Search for the insn that copies REGNO to NEW_REGNO? */
9177 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9178 && (set = single_set (insn))
9179 && GET_CODE (SET_DEST (set)) == REG
9180 && REGNO (SET_DEST (set)) == new_regno
9181 && GET_CODE (SET_SRC (set)) == REG
9182 && REGNO (SET_SRC (set)) == regno)
9186 if (insn != NULL_RTX)
9191 /* Some DEF-USE info would come in handy here to make this
9192 function more general. For now, just check the previous insn
9193 which is the most likely candidate for setting REGNO. */
9195 prev_insn = PREV_INSN (insn);
9197 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9198 && (prev_set = single_set (prev_insn))
9199 && GET_CODE (SET_DEST (prev_set)) == REG
9200 && REGNO (SET_DEST (prev_set)) == regno)
9203 (set (reg regno) (expr))
9204 (set (reg new_regno) (reg regno))
9206 so try converting this to:
9207 (set (reg new_regno) (expr))
9208 (set (reg regno) (reg new_regno))
9210 The former construct is often generated when a global
9211 variable used for an induction variable is shadowed by a
9212 register (NEW_REGNO). The latter construct improves the
9213 chances of GIV replacement and BIV elimination. */
9215 validate_change (prev_insn, &SET_DEST (prev_set),
9217 validate_change (insn, &SET_DEST (set),
9219 validate_change (insn, &SET_SRC (set),
9222 if (apply_change_group ())
9224 if (loop_dump_stream)
9225 fprintf (loop_dump_stream,
9226 " Swapped set of reg %d at %d with reg %d at %d.\n",
9227 regno, INSN_UID (insn),
9228 new_regno, INSN_UID (prev_insn));
9230 /* Update first use of REGNO. */
9231 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9232 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9234 /* Now perform copy propagation to hopefully
9235 remove all uses of REGNO within the loop. */
9236 try_copy_prop (loop, replacement, regno);
9242 /* Replace MEM with its associated pseudo register. This function is
9243 called from load_mems via for_each_rtx. DATA is actually a pointer
9244 to a structure describing the instruction currently being scanned
9245 and the MEM we are currently replacing. */
9248 replace_loop_mem (mem, data)
9252 loop_replace_args *args = (loop_replace_args *) data;
9258 switch (GET_CODE (m))
9264 /* We're not interested in the MEM associated with a
9265 CONST_DOUBLE, so there's no need to traverse into one. */
9269 /* This is not a MEM. */
9273 if (!rtx_equal_p (args->match, m))
9274 /* This is not the MEM we are currently replacing. */
9277 /* Actually replace the MEM. */
9278 validate_change (args->insn, mem, args->replacement, 1);
9284 replace_loop_mems (insn, mem, reg)
9289 loop_replace_args args;
9293 args.replacement = reg;
9295 for_each_rtx (&insn, replace_loop_mem, &args);
9298 /* Replace one register with another. Called through for_each_rtx; PX points
9299 to the rtx being scanned. DATA is actually a pointer to
9300 a structure of arguments. */
9303 replace_loop_reg (px, data)
9308 loop_replace_args *args = (loop_replace_args *) data;
9313 if (x == args->match)
9314 validate_change (args->insn, px, args->replacement, 1);
9320 replace_loop_regs (insn, reg, replacement)
9325 loop_replace_args args;
9329 args.replacement = replacement;
9331 for_each_rtx (&insn, replace_loop_reg, &args);
9334 /* Replace occurrences of the old exit label for the loop with the new
9335 one. DATA is an rtx_pair containing the old and new labels,
9339 replace_label (x, data)
9344 rtx old_label = ((rtx_pair *) data)->r1;
9345 rtx new_label = ((rtx_pair *) data)->r2;
9350 if (GET_CODE (l) != LABEL_REF)
9353 if (XEXP (l, 0) != old_label)
9356 XEXP (l, 0) = new_label;
9357 ++LABEL_NUSES (new_label);
9358 --LABEL_NUSES (old_label);
9363 /* If WHERE_INSN is non-zero emit insn for PATTERN before WHERE_INSN
9364 in basic block WHERE_BB (ignored in the interim) within the loop
9365 otherwise hoist PATTERN into the loop pre-header. */
9368 loop_insn_emit_before (loop, where_bb, where_insn, pattern)
9369 const struct loop *loop;
9370 basic_block where_bb ATTRIBUTE_UNUSED;
9375 return loop_insn_hoist (loop, pattern);
9376 return emit_insn_before (pattern, where_insn);
9380 /* Hoist insn for PATTERN into the loop pre-header. */
9383 loop_insn_hoist (loop, pattern)
9384 const struct loop *loop;
9387 return loop_insn_emit_before (loop, 0, loop->start, pattern);
9391 loop_biv_dump (v, file, verbose)
9392 const struct induction *v;
9401 REGNO (v->dest_reg), INSN_UID (v->insn));
9402 fprintf (file, " const ");
9403 print_simple_rtl (file, v->add_val);
9405 if (verbose && v->final_value)
9408 fprintf (file, " final ");
9409 print_simple_rtl (file, v->final_value);
9417 loop_giv_dump (v, file, verbose)
9418 const struct induction *v;
9425 if (v->giv_type == DEST_REG)
9426 fprintf (file, "Giv %d: insn %d",
9427 REGNO (v->dest_reg), INSN_UID (v->insn));
9429 fprintf (file, "Dest address: insn %d",
9430 INSN_UID (v->insn));
9432 fprintf (file, " src reg %d benefit %d",
9433 REGNO (v->src_reg), v->benefit);
9434 fprintf (file, " lifetime %d",
9438 fprintf (file, " replaceable");
9440 if (v->no_const_addval)
9441 fprintf (file, " ncav");
9443 if (v->ext_dependant)
9445 switch (GET_CODE (v->ext_dependant))
9448 fprintf (file, " ext se");
9451 fprintf (file, " ext ze");
9454 fprintf (file, " ext tr");
9462 fprintf (file, " mult ");
9463 print_simple_rtl (file, v->mult_val);
9466 fprintf (file, " add ");
9467 print_simple_rtl (file, v->add_val);
9469 if (verbose && v->final_value)
9472 fprintf (file, " final ");
9473 print_simple_rtl (file, v->final_value);
9482 const struct induction *v;
9484 loop_biv_dump (v, stderr, 1);
9490 const struct induction *v;
9492 loop_giv_dump (v, stderr, 1);
9496 #define LOOP_BLOCK_NUM_1(INSN) \
9497 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9499 /* The notes do not have an assigned block, so look at the next insn. */
9500 #define LOOP_BLOCK_NUM(INSN) \
9501 ((INSN) ? (GET_CODE (INSN) == NOTE \
9502 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9503 : LOOP_BLOCK_NUM_1 (INSN)) \
9506 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9509 loop_dump_aux (loop, file, verbose)
9510 const struct loop *loop;
9512 int verbose ATTRIBUTE_UNUSED;
9516 if (! loop || ! file)
9519 /* Print diagnostics to compare our concept of a loop with
9520 what the loop notes say. */
9521 if (! PREV_INSN (loop->first->head)
9522 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9523 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9524 != NOTE_INSN_LOOP_BEG)
9525 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9526 INSN_UID (PREV_INSN (loop->first->head)));
9527 if (! NEXT_INSN (loop->last->end)
9528 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9529 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9530 != NOTE_INSN_LOOP_END)
9531 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9532 INSN_UID (NEXT_INSN (loop->last->end)));
9537 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9538 LOOP_BLOCK_NUM (loop->start),
9539 LOOP_INSN_UID (loop->start),
9540 LOOP_BLOCK_NUM (loop->cont),
9541 LOOP_INSN_UID (loop->cont),
9542 LOOP_BLOCK_NUM (loop->cont),
9543 LOOP_INSN_UID (loop->cont),
9544 LOOP_BLOCK_NUM (loop->vtop),
9545 LOOP_INSN_UID (loop->vtop),
9546 LOOP_BLOCK_NUM (loop->end),
9547 LOOP_INSN_UID (loop->end));
9548 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9549 LOOP_BLOCK_NUM (loop->top),
9550 LOOP_INSN_UID (loop->top),
9551 LOOP_BLOCK_NUM (loop->scan_start),
9552 LOOP_INSN_UID (loop->scan_start));
9553 fprintf (file, ";; exit_count %d", loop->exit_count);
9554 if (loop->exit_count)
9556 fputs (", labels:", file);
9557 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9559 fprintf (file, " %d ",
9560 LOOP_INSN_UID (XEXP (label, 0)));
9565 /* This can happen when a marked loop appears as two nested loops,
9566 say from while (a || b) {}. The inner loop won't match
9567 the loop markers but the outer one will. */
9568 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9569 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9573 /* Call this function from the debugger to dump LOOP. */
9577 const struct loop *loop;
9579 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9582 /* Call this function from the debugger to dump LOOPS. */
9586 const struct loops *loops;
9588 flow_loops_dump (loops, stderr, loop_dump_aux, 1);