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_ivs_dump PARAMS((const struct loop *, FILE *, int));
203 static void loop_iv_class_dump PARAMS((const struct iv_class *, FILE *, int));
204 static void loop_biv_dump PARAMS((const struct induction *, FILE *, int));
205 static void loop_giv_dump PARAMS((const struct induction *, FILE *, int));
206 static void record_giv PARAMS ((const struct loop *, struct induction *,
207 rtx, rtx, rtx, rtx, rtx, rtx, int,
208 enum g_types, int, int, rtx *));
209 static void update_giv_derive PARAMS ((const struct loop *, rtx));
210 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
211 struct loop_info *));
212 static int basic_induction_var PARAMS ((const struct loop *, rtx,
213 enum machine_mode, rtx, rtx,
214 rtx *, rtx *, rtx **));
215 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
216 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
217 rtx *, rtx *, rtx *, int, int *,
219 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
220 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
221 static int check_dbra_loop PARAMS ((struct loop *, int));
222 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
223 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
224 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
225 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
226 static int product_cheap_p PARAMS ((rtx, rtx));
227 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
229 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
230 struct iv_class *, int,
232 static int last_use_this_basic_block PARAMS ((rtx, rtx));
233 static void record_initial PARAMS ((rtx, rtx, void *));
234 static void update_reg_last_use PARAMS ((rtx, rtx));
235 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
236 static void loop_regs_scan PARAMS ((const struct loop*, int, int *));
237 static void load_mems PARAMS ((const struct loop *));
238 static int insert_loop_mem PARAMS ((rtx *, void *));
239 static int replace_loop_mem PARAMS ((rtx *, void *));
240 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
241 static int replace_loop_reg PARAMS ((rtx *, void *));
242 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
243 static void note_reg_stored PARAMS ((rtx, rtx, void *));
244 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
245 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
247 static int replace_label PARAMS ((rtx *, void *));
248 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
249 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
250 static rtx gen_add_mult PARAMS ((rtx, rtx, rtx, rtx));
251 static void loop_regs_update PARAMS ((const struct loop *, rtx));
252 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
254 static rtx loop_insn_emit_after PARAMS((const struct loop *, basic_block,
256 static rtx loop_call_insn_emit_before PARAMS((const struct loop *,
257 basic_block, rtx, rtx));
258 static rtx loop_call_insn_hoist PARAMS((const struct loop *, rtx));
259 static rtx loop_insn_sink_or_swim PARAMS((const struct loop *, rtx));
261 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
262 void debug_ivs PARAMS ((const struct loop *));
263 void debug_iv_class PARAMS ((const struct iv_class *));
264 void debug_biv PARAMS ((const struct induction *));
265 void debug_giv PARAMS ((const struct induction *));
266 void debug_loop PARAMS ((const struct loop *));
267 void debug_loops PARAMS ((const struct loops *));
269 typedef struct rtx_pair
275 typedef struct loop_replace_args
282 /* Nonzero iff INSN is between START and END, inclusive. */
283 #define INSN_IN_RANGE_P(INSN, START, END) \
284 (INSN_UID (INSN) < max_uid_for_loop \
285 && INSN_LUID (INSN) >= INSN_LUID (START) \
286 && INSN_LUID (INSN) <= INSN_LUID (END))
288 /* Indirect_jump_in_function is computed once per function. */
289 static int indirect_jump_in_function;
290 static int indirect_jump_in_function_p PARAMS ((rtx));
292 static int compute_luids PARAMS ((rtx, rtx, int));
294 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
298 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
299 copy the value of the strength reduced giv to its original register. */
300 static int copy_cost;
302 /* Cost of using a register, to normalize the benefits of a giv. */
303 static int reg_address_cost;
308 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
310 reg_address_cost = address_cost (reg, SImode);
312 copy_cost = COSTS_N_INSNS (1);
315 /* Compute the mapping from uids to luids.
316 LUIDs are numbers assigned to insns, like uids,
317 except that luids increase monotonically through the code.
318 Start at insn START and stop just before END. Assign LUIDs
319 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
321 compute_luids (start, end, prev_luid)
328 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
330 if (INSN_UID (insn) >= max_uid_for_loop)
332 /* Don't assign luids to line-number NOTEs, so that the distance in
333 luids between two insns is not affected by -g. */
334 if (GET_CODE (insn) != NOTE
335 || NOTE_LINE_NUMBER (insn) <= 0)
336 uid_luid[INSN_UID (insn)] = ++i;
338 /* Give a line number note the same luid as preceding insn. */
339 uid_luid[INSN_UID (insn)] = i;
344 /* Entry point of this file. Perform loop optimization
345 on the current function. F is the first insn of the function
346 and DUMPFILE is a stream for output of a trace of actions taken
347 (or 0 if none should be output). */
350 loop_optimize (f, dumpfile, flags)
351 /* f is the first instruction of a chain of insns for one function */
358 struct loops loops_data;
359 struct loops *loops = &loops_data;
360 struct loop_info *loops_info;
362 loop_dump_stream = dumpfile;
364 init_recog_no_volatile ();
366 max_reg_before_loop = max_reg_num ();
367 loop_max_reg = max_reg_before_loop;
371 /* Count the number of loops. */
374 for (insn = f; insn; insn = NEXT_INSN (insn))
376 if (GET_CODE (insn) == NOTE
377 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
381 /* Don't waste time if no loops. */
382 if (max_loop_num == 0)
385 loops->num = max_loop_num;
387 /* Get size to use for tables indexed by uids.
388 Leave some space for labels allocated by find_and_verify_loops. */
389 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
391 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
392 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
393 sizeof (struct loop *));
395 /* Allocate storage for array of loops. */
396 loops->array = (struct loop *)
397 xcalloc (loops->num, sizeof (struct loop));
399 /* Find and process each loop.
400 First, find them, and record them in order of their beginnings. */
401 find_and_verify_loops (f, loops);
403 /* Allocate and initialize auxiliary loop information. */
404 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
405 for (i = 0; i < loops->num; i++)
406 loops->array[i].aux = loops_info + i;
408 /* Now find all register lifetimes. This must be done after
409 find_and_verify_loops, because it might reorder the insns in the
411 reg_scan (f, max_reg_before_loop, 1);
413 /* This must occur after reg_scan so that registers created by gcse
414 will have entries in the register tables.
416 We could have added a call to reg_scan after gcse_main in toplev.c,
417 but moving this call to init_alias_analysis is more efficient. */
418 init_alias_analysis ();
420 /* See if we went too far. Note that get_max_uid already returns
421 one more that the maximum uid of all insn. */
422 if (get_max_uid () > max_uid_for_loop)
424 /* Now reset it to the actual size we need. See above. */
425 max_uid_for_loop = get_max_uid ();
427 /* find_and_verify_loops has already called compute_luids, but it
428 might have rearranged code afterwards, so we need to recompute
430 max_luid = compute_luids (f, NULL_RTX, 0);
432 /* Don't leave gaps in uid_luid for insns that have been
433 deleted. It is possible that the first or last insn
434 using some register has been deleted by cross-jumping.
435 Make sure that uid_luid for that former insn's uid
436 points to the general area where that insn used to be. */
437 for (i = 0; i < max_uid_for_loop; i++)
439 uid_luid[0] = uid_luid[i];
440 if (uid_luid[0] != 0)
443 for (i = 0; i < max_uid_for_loop; i++)
444 if (uid_luid[i] == 0)
445 uid_luid[i] = uid_luid[i - 1];
447 /* Determine if the function has indirect jump. On some systems
448 this prevents low overhead loop instructions from being used. */
449 indirect_jump_in_function = indirect_jump_in_function_p (f);
451 /* Now scan the loops, last ones first, since this means inner ones are done
452 before outer ones. */
453 for (i = max_loop_num - 1; i >= 0; i--)
455 struct loop *loop = &loops->array[i];
457 if (! loop->invalid && loop->end)
458 scan_loop (loop, flags);
461 /* If there were lexical blocks inside the loop, they have been
462 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
463 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
464 the BLOCKs as well. */
465 if (write_symbols != NO_DEBUG)
468 end_alias_analysis ();
477 /* Returns the next insn, in execution order, after INSN. START and
478 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
479 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
480 insn-stream; it is used with loops that are entered near the
484 next_insn_in_loop (loop, insn)
485 const struct loop *loop;
488 insn = NEXT_INSN (insn);
490 if (insn == loop->end)
493 /* Go to the top of the loop, and continue there. */
500 if (insn == loop->scan_start)
507 /* Optimize one loop described by LOOP. */
509 /* ??? Could also move memory writes out of loops if the destination address
510 is invariant, the source is invariant, the memory write is not volatile,
511 and if we can prove that no read inside the loop can read this address
512 before the write occurs. If there is a read of this address after the
513 write, then we can also mark the memory read as invariant. */
516 scan_loop (loop, flags)
520 struct loop_info *loop_info = LOOP_INFO (loop);
521 struct loop_regs *regs = LOOP_REGS (loop);
523 rtx loop_start = loop->start;
524 rtx loop_end = loop->end;
526 /* 1 if we are scanning insns that could be executed zero times. */
528 /* 1 if we are scanning insns that might never be executed
529 due to a subroutine call which might exit before they are reached. */
531 /* Jump insn that enters the loop, or 0 if control drops in. */
532 rtx loop_entry_jump = 0;
533 /* Number of insns in the loop. */
536 rtx temp, update_start, update_end;
537 /* The SET from an insn, if it is the only SET in the insn. */
539 /* Chain describing insns movable in current loop. */
540 struct loop_movables *movables = LOOP_MOVABLES (loop);
541 /* Ratio of extra register life span we can justify
542 for saving an instruction. More if loop doesn't call subroutines
543 since in that case saving an insn makes more difference
544 and more registers are available. */
546 /* Nonzero if we are scanning instructions in a sub-loop. */
555 /* Determine whether this loop starts with a jump down to a test at
556 the end. This will occur for a small number of loops with a test
557 that is too complex to duplicate in front of the loop.
559 We search for the first insn or label in the loop, skipping NOTEs.
560 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
561 (because we might have a loop executed only once that contains a
562 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
563 (in case we have a degenerate loop).
565 Note that if we mistakenly think that a loop is entered at the top
566 when, in fact, it is entered at the exit test, the only effect will be
567 slightly poorer optimization. Making the opposite error can generate
568 incorrect code. Since very few loops now start with a jump to the
569 exit test, the code here to detect that case is very conservative. */
571 for (p = NEXT_INSN (loop_start);
573 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
574 && (GET_CODE (p) != NOTE
575 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
576 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
580 loop->scan_start = p;
582 /* If loop end is the end of the current function, then emit a
583 NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy
584 note insn. This is the position we use when sinking insns out of
586 if (NEXT_INSN (loop->end) != 0)
587 loop->sink = NEXT_INSN (loop->end);
589 loop->sink = emit_note_after (NOTE_INSN_DELETED, loop->end);
591 /* Set up variables describing this loop. */
593 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
595 /* If loop has a jump before the first label,
596 the true entry is the target of that jump.
597 Start scan from there.
598 But record in LOOP->TOP the place where the end-test jumps
599 back to so we can scan that after the end of the loop. */
600 if (GET_CODE (p) == JUMP_INSN)
604 /* Loop entry must be unconditional jump (and not a RETURN) */
605 if (any_uncondjump_p (p)
606 && JUMP_LABEL (p) != 0
607 /* Check to see whether the jump actually
608 jumps out of the loop (meaning it's no loop).
609 This case can happen for things like
610 do {..} while (0). If this label was generated previously
611 by loop, we can't tell anything about it and have to reject
613 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
615 loop->top = next_label (loop->scan_start);
616 loop->scan_start = JUMP_LABEL (p);
620 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
621 as required by loop_reg_used_before_p. So skip such loops. (This
622 test may never be true, but it's best to play it safe.)
624 Also, skip loops where we do not start scanning at a label. This
625 test also rejects loops starting with a JUMP_INSN that failed the
628 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
629 || GET_CODE (loop->scan_start) != CODE_LABEL)
631 if (loop_dump_stream)
632 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
633 INSN_UID (loop_start), INSN_UID (loop_end));
637 /* Allocate extra space for REGs that might be created by load_mems.
638 We allocate a little extra slop as well, in the hopes that we
639 won't have to reallocate the regs array. */
640 loop_regs_scan (loop, loop_info->mems_idx + 16, &insn_count);
642 if (loop_dump_stream)
644 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
645 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
647 fprintf (loop_dump_stream, "Continue at insn %d.\n",
648 INSN_UID (loop->cont));
651 /* Scan through the loop finding insns that are safe to move.
652 Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
653 this reg will be considered invariant for subsequent insns.
654 We consider whether subsequent insns use the reg
655 in deciding whether it is worth actually moving.
657 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
658 and therefore it is possible that the insns we are scanning
659 would never be executed. At such times, we must make sure
660 that it is safe to execute the insn once instead of zero times.
661 When MAYBE_NEVER is 0, all insns will be executed at least once
662 so that is not a problem. */
664 for (p = next_insn_in_loop (loop, loop->scan_start);
666 p = next_insn_in_loop (loop, p))
668 if (GET_CODE (p) == INSN
669 && (set = single_set (p))
670 && GET_CODE (SET_DEST (set)) == REG
671 && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
676 rtx src = SET_SRC (set);
677 rtx dependencies = 0;
679 /* Figure out what to use as a source of this insn. If a REG_EQUIV
680 note is given or if a REG_EQUAL note with a constant operand is
681 specified, use it as the source and mark that we should move
682 this insn by calling emit_move_insn rather that duplicating the
685 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
687 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
689 src = XEXP (temp, 0), move_insn = 1;
692 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
693 if (temp && CONSTANT_P (XEXP (temp, 0)))
694 src = XEXP (temp, 0), move_insn = 1;
695 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
697 src = XEXP (temp, 0);
698 /* A libcall block can use regs that don't appear in
699 the equivalent expression. To move the libcall,
700 we must move those regs too. */
701 dependencies = libcall_other_reg (p, src);
705 /* Don't try to optimize a register that was made
706 by loop-optimization for an inner loop.
707 We don't know its life-span, so we can't compute the benefit. */
708 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
710 else if (/* The register is used in basic blocks other
711 than the one where it is set (meaning that
712 something after this point in the loop might
713 depend on its value before the set). */
714 ! reg_in_basic_block_p (p, SET_DEST (set))
715 /* And the set is not guaranteed to be executed one
716 the loop starts, or the value before the set is
717 needed before the set occurs...
719 ??? Note we have quadratic behaviour here, mitigated
720 by the fact that the previous test will often fail for
721 large loops. Rather than re-scanning the entire loop
722 each time for register usage, we should build tables
723 of the register usage and use them here instead. */
725 || loop_reg_used_before_p (loop, set, p)))
726 /* It is unsafe to move the set.
728 This code used to consider it OK to move a set of a variable
729 which was not created by the user and not used in an exit test.
730 That behavior is incorrect and was removed. */
732 else if ((tem = loop_invariant_p (loop, src))
733 && (dependencies == 0
734 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
735 && (regs->array[REGNO (SET_DEST (set))].set_in_loop == 1
737 = consec_sets_invariant_p
738 (loop, SET_DEST (set),
739 regs->array[REGNO (SET_DEST (set))].set_in_loop,
741 /* If the insn can cause a trap (such as divide by zero),
742 can't move it unless it's guaranteed to be executed
743 once loop is entered. Even a function call might
744 prevent the trap insn from being reached
745 (since it might exit!) */
746 && ! ((maybe_never || call_passed)
747 && may_trap_p (src)))
749 register struct movable *m;
750 register int regno = REGNO (SET_DEST (set));
752 /* A potential lossage is where we have a case where two insns
753 can be combined as long as they are both in the loop, but
754 we move one of them outside the loop. For large loops,
755 this can lose. The most common case of this is the address
756 of a function being called.
758 Therefore, if this register is marked as being used exactly
759 once if we are in a loop with calls (a "large loop"), see if
760 we can replace the usage of this register with the source
761 of this SET. If we can, delete this insn.
763 Don't do this if P has a REG_RETVAL note or if we have
764 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
766 if (loop_info->has_call
767 && regs->array[regno].single_usage != 0
768 && regs->array[regno].single_usage != const0_rtx
769 && REGNO_FIRST_UID (regno) == INSN_UID (p)
770 && (REGNO_LAST_UID (regno)
771 == INSN_UID (regs->array[regno].single_usage))
772 && regs->array[regno].set_in_loop == 1
773 && ! side_effects_p (SET_SRC (set))
774 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
775 && (! SMALL_REGISTER_CLASSES
776 || (! (GET_CODE (SET_SRC (set)) == REG
777 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
778 /* This test is not redundant; SET_SRC (set) might be
779 a call-clobbered register and the life of REGNO
780 might span a call. */
781 && ! modified_between_p (SET_SRC (set), p,
782 regs->array[regno].single_usage)
783 && no_labels_between_p (p, regs->array[regno].single_usage)
784 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
785 regs->array[regno].single_usage))
787 /* Replace any usage in a REG_EQUAL note. Must copy the
788 new source, so that we don't get rtx sharing between the
789 SET_SOURCE and REG_NOTES of insn p. */
790 REG_NOTES (regs->array[regno].single_usage)
791 = replace_rtx (REG_NOTES (regs->array[regno].single_usage),
792 SET_DEST (set), copy_rtx (SET_SRC (set)));
795 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
796 NOTE_SOURCE_FILE (p) = 0;
797 regs->array[regno].set_in_loop = 0;
801 m = (struct movable *) xmalloc (sizeof (struct movable));
805 m->dependencies = dependencies;
806 m->set_dest = SET_DEST (set);
808 m->consec = regs->array[REGNO (SET_DEST (set))].set_in_loop - 1;
812 m->move_insn = move_insn;
813 m->move_insn_first = 0;
814 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
815 m->savemode = VOIDmode;
817 /* Set M->cond if either loop_invariant_p
818 or consec_sets_invariant_p returned 2
819 (only conditionally invariant). */
820 m->cond = ((tem | tem1 | tem2) > 1);
821 m->global = LOOP_REG_GLOBAL_P (loop, regno);
823 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
824 m->savings = regs->array[regno].n_times_set;
825 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
826 m->savings += libcall_benefit (p);
827 regs->array[regno].set_in_loop = move_insn ? -2 : -1;
828 /* Add M to the end of the chain MOVABLES. */
829 loop_movables_add (movables, m);
833 /* It is possible for the first instruction to have a
834 REG_EQUAL note but a non-invariant SET_SRC, so we must
835 remember the status of the first instruction in case
836 the last instruction doesn't have a REG_EQUAL note. */
837 m->move_insn_first = m->move_insn;
839 /* Skip this insn, not checking REG_LIBCALL notes. */
840 p = next_nonnote_insn (p);
841 /* Skip the consecutive insns, if there are any. */
842 p = skip_consec_insns (p, m->consec);
843 /* Back up to the last insn of the consecutive group. */
844 p = prev_nonnote_insn (p);
846 /* We must now reset m->move_insn, m->is_equiv, and possibly
847 m->set_src to correspond to the effects of all the
849 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
851 m->set_src = XEXP (temp, 0), m->move_insn = 1;
854 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
855 if (temp && CONSTANT_P (XEXP (temp, 0)))
856 m->set_src = XEXP (temp, 0), m->move_insn = 1;
861 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
864 /* If this register is always set within a STRICT_LOW_PART
865 or set to zero, then its high bytes are constant.
866 So clear them outside the loop and within the loop
867 just load the low bytes.
868 We must check that the machine has an instruction to do so.
869 Also, if the value loaded into the register
870 depends on the same register, this cannot be done. */
871 else if (SET_SRC (set) == const0_rtx
872 && GET_CODE (NEXT_INSN (p)) == INSN
873 && (set1 = single_set (NEXT_INSN (p)))
874 && GET_CODE (set1) == SET
875 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
876 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
877 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
879 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
881 register int regno = REGNO (SET_DEST (set));
882 if (regs->array[regno].set_in_loop == 2)
884 register struct movable *m;
885 m = (struct movable *) xmalloc (sizeof (struct movable));
888 m->set_dest = SET_DEST (set);
895 m->move_insn_first = 0;
897 /* If the insn may not be executed on some cycles,
898 we can't clear the whole reg; clear just high part.
899 Not even if the reg is used only within this loop.
906 Clearing x before the inner loop could clobber a value
907 being saved from the last time around the outer loop.
908 However, if the reg is not used outside this loop
909 and all uses of the register are in the same
910 basic block as the store, there is no problem.
912 If this insn was made by loop, we don't know its
913 INSN_LUID and hence must make a conservative
915 m->global = (INSN_UID (p) >= max_uid_for_loop
916 || LOOP_REG_GLOBAL_P (loop, regno)
917 || (labels_in_range_p
918 (p, REGNO_FIRST_LUID (regno))));
919 if (maybe_never && m->global)
920 m->savemode = GET_MODE (SET_SRC (set1));
922 m->savemode = VOIDmode;
926 m->lifetime = LOOP_REG_LIFETIME (loop, regno);
928 regs->array[regno].set_in_loop = -1;
929 /* Add M to the end of the chain MOVABLES. */
930 loop_movables_add (movables, m);
934 /* Past a call insn, we get to insns which might not be executed
935 because the call might exit. This matters for insns that trap.
936 Constant and pure call insns always return, so they don't count. */
937 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
939 /* Past a label or a jump, we get to insns for which we
940 can't count on whether or how many times they will be
941 executed during each iteration. Therefore, we can
942 only move out sets of trivial variables
943 (those not used after the loop). */
944 /* Similar code appears twice in strength_reduce. */
945 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
946 /* If we enter the loop in the middle, and scan around to the
947 beginning, don't set maybe_never for that. This must be an
948 unconditional jump, otherwise the code at the top of the
949 loop might never be executed. Unconditional jumps are
950 followed a by barrier then loop end. */
951 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
952 && NEXT_INSN (NEXT_INSN (p)) == loop_end
953 && any_uncondjump_p (p)))
955 else if (GET_CODE (p) == NOTE)
957 /* At the virtual top of a converted loop, insns are again known to
958 be executed: logically, the loop begins here even though the exit
959 code has been duplicated. */
960 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
961 maybe_never = call_passed = 0;
962 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
964 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
969 /* If one movable subsumes another, ignore that other. */
971 ignore_some_movables (movables);
973 /* For each movable insn, see if the reg that it loads
974 leads when it dies right into another conditionally movable insn.
975 If so, record that the second insn "forces" the first one,
976 since the second can be moved only if the first is. */
978 force_movables (movables);
980 /* See if there are multiple movable insns that load the same value.
981 If there are, make all but the first point at the first one
982 through the `match' field, and add the priorities of them
983 all together as the priority of the first. */
985 combine_movables (movables, regs);
987 /* Now consider each movable insn to decide whether it is worth moving.
988 Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
990 Generally this increases code size, so do not move moveables when
991 optimizing for code size. */
994 move_movables (loop, movables, threshold, insn_count);
996 /* Now candidates that still are negative are those not moved.
997 Change regs->array[I].set_in_loop to indicate that those are not actually
999 for (i = 0; i < regs->num; i++)
1000 if (regs->array[i].set_in_loop < 0)
1001 regs->array[i].set_in_loop = regs->array[i].n_times_set;
1003 /* Now that we've moved some things out of the loop, we might be able to
1004 hoist even more memory references. */
1007 /* Recalculate regs->array if load_mems has created new registers. */
1008 if (max_reg_num () > regs->num)
1009 loop_regs_scan (loop, 0, &insn_count);
1011 for (update_start = loop_start;
1012 PREV_INSN (update_start)
1013 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
1014 update_start = PREV_INSN (update_start))
1016 update_end = NEXT_INSN (loop_end);
1018 reg_scan_update (update_start, update_end, loop_max_reg);
1019 loop_max_reg = max_reg_num ();
1021 if (flag_strength_reduce)
1023 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1024 /* Ensure our label doesn't go away. */
1025 LABEL_NUSES (update_end)++;
1027 strength_reduce (loop, insn_count, flags);
1029 reg_scan_update (update_start, update_end, loop_max_reg);
1030 loop_max_reg = max_reg_num ();
1032 if (update_end && GET_CODE (update_end) == CODE_LABEL
1033 && --LABEL_NUSES (update_end) == 0)
1034 delete_insn (update_end);
1038 /* The movable information is required for strength reduction. */
1039 loop_movables_free (movables);
1046 /* Add elements to *OUTPUT to record all the pseudo-regs
1047 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1050 record_excess_regs (in_this, not_in_this, output)
1051 rtx in_this, not_in_this;
1058 code = GET_CODE (in_this);
1072 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1073 && ! reg_mentioned_p (in_this, not_in_this))
1074 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1081 fmt = GET_RTX_FORMAT (code);
1082 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1089 for (j = 0; j < XVECLEN (in_this, i); j++)
1090 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1094 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1100 /* Check what regs are referred to in the libcall block ending with INSN,
1101 aside from those mentioned in the equivalent value.
1102 If there are none, return 0.
1103 If there are one or more, return an EXPR_LIST containing all of them. */
1106 libcall_other_reg (insn, equiv)
1109 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1110 rtx p = XEXP (note, 0);
1113 /* First, find all the regs used in the libcall block
1114 that are not mentioned as inputs to the result. */
1118 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1119 || GET_CODE (p) == CALL_INSN)
1120 record_excess_regs (PATTERN (p), equiv, &output);
1127 /* Return 1 if all uses of REG
1128 are between INSN and the end of the basic block. */
1131 reg_in_basic_block_p (insn, reg)
1134 int regno = REGNO (reg);
1137 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1140 /* Search this basic block for the already recorded last use of the reg. */
1141 for (p = insn; p; p = NEXT_INSN (p))
1143 switch (GET_CODE (p))
1150 /* Ordinary insn: if this is the last use, we win. */
1151 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1156 /* Jump insn: if this is the last use, we win. */
1157 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1159 /* Otherwise, it's the end of the basic block, so we lose. */
1164 /* It's the end of the basic block, so we lose. */
1172 /* The "last use" that was recorded can't be found after the first
1173 use. This can happen when the last use was deleted while
1174 processing an inner loop, this inner loop was then completely
1175 unrolled, and the outer loop is always exited after the inner loop,
1176 so that everything after the first use becomes a single basic block. */
1180 /* Compute the benefit of eliminating the insns in the block whose
1181 last insn is LAST. This may be a group of insns used to compute a
1182 value directly or can contain a library call. */
1185 libcall_benefit (last)
1191 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1192 insn != last; insn = NEXT_INSN (insn))
1194 if (GET_CODE (insn) == CALL_INSN)
1195 benefit += 10; /* Assume at least this many insns in a library
1197 else if (GET_CODE (insn) == INSN
1198 && GET_CODE (PATTERN (insn)) != USE
1199 && GET_CODE (PATTERN (insn)) != CLOBBER)
1206 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1209 skip_consec_insns (insn, count)
1213 for (; count > 0; count--)
1217 /* If first insn of libcall sequence, skip to end. */
1218 /* Do this at start of loop, since INSN is guaranteed to
1220 if (GET_CODE (insn) != NOTE
1221 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1222 insn = XEXP (temp, 0);
1225 insn = NEXT_INSN (insn);
1226 while (GET_CODE (insn) == NOTE);
1232 /* Ignore any movable whose insn falls within a libcall
1233 which is part of another movable.
1234 We make use of the fact that the movable for the libcall value
1235 was made later and so appears later on the chain. */
1238 ignore_some_movables (movables)
1239 struct loop_movables *movables;
1241 register struct movable *m, *m1;
1243 for (m = movables->head; m; m = m->next)
1245 /* Is this a movable for the value of a libcall? */
1246 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1250 /* Check for earlier movables inside that range,
1251 and mark them invalid. We cannot use LUIDs here because
1252 insns created by loop.c for prior loops don't have LUIDs.
1253 Rather than reject all such insns from movables, we just
1254 explicitly check each insn in the libcall (since invariant
1255 libcalls aren't that common). */
1256 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1257 for (m1 = movables->head; m1 != m; m1 = m1->next)
1258 if (m1->insn == insn)
1264 /* For each movable insn, see if the reg that it loads
1265 leads when it dies right into another conditionally movable insn.
1266 If so, record that the second insn "forces" the first one,
1267 since the second can be moved only if the first is. */
1270 force_movables (movables)
1271 struct loop_movables *movables;
1273 register struct movable *m, *m1;
1274 for (m1 = movables->head; m1; m1 = m1->next)
1275 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1276 if (!m1->partial && !m1->done)
1278 int regno = m1->regno;
1279 for (m = m1->next; m; m = m->next)
1280 /* ??? Could this be a bug? What if CSE caused the
1281 register of M1 to be used after this insn?
1282 Since CSE does not update regno_last_uid,
1283 this insn M->insn might not be where it dies.
1284 But very likely this doesn't matter; what matters is
1285 that M's reg is computed from M1's reg. */
1286 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1289 if (m != 0 && m->set_src == m1->set_dest
1290 /* If m->consec, m->set_src isn't valid. */
1294 /* Increase the priority of the moving the first insn
1295 since it permits the second to be moved as well. */
1299 m1->lifetime += m->lifetime;
1300 m1->savings += m->savings;
1305 /* Find invariant expressions that are equal and can be combined into
1309 combine_movables (movables, regs)
1310 struct loop_movables *movables;
1311 struct loop_regs *regs;
1313 register struct movable *m;
1314 char *matched_regs = (char *) xmalloc (regs->num);
1315 enum machine_mode mode;
1317 /* Regs that are set more than once are not allowed to match
1318 or be matched. I'm no longer sure why not. */
1319 /* Perhaps testing m->consec_sets would be more appropriate here? */
1321 for (m = movables->head; m; m = m->next)
1322 if (m->match == 0 && regs->array[m->regno].n_times_set == 1
1325 register struct movable *m1;
1326 int regno = m->regno;
1328 memset (matched_regs, 0, regs->num);
1329 matched_regs[regno] = 1;
1331 /* We want later insns to match the first one. Don't make the first
1332 one match any later ones. So start this loop at m->next. */
1333 for (m1 = m->next; m1; m1 = m1->next)
1334 if (m != m1 && m1->match == 0
1335 && regs->array[m1->regno].n_times_set == 1
1336 /* A reg used outside the loop mustn't be eliminated. */
1338 /* A reg used for zero-extending mustn't be eliminated. */
1340 && (matched_regs[m1->regno]
1343 /* Can combine regs with different modes loaded from the
1344 same constant only if the modes are the same or
1345 if both are integer modes with M wider or the same
1346 width as M1. The check for integer is redundant, but
1347 safe, since the only case of differing destination
1348 modes with equal sources is when both sources are
1349 VOIDmode, i.e., CONST_INT. */
1350 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1351 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1352 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1353 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1354 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1355 /* See if the source of M1 says it matches M. */
1356 && ((GET_CODE (m1->set_src) == REG
1357 && matched_regs[REGNO (m1->set_src)])
1358 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1360 && ((m->dependencies == m1->dependencies)
1361 || rtx_equal_p (m->dependencies, m1->dependencies)))
1363 m->lifetime += m1->lifetime;
1364 m->savings += m1->savings;
1367 matched_regs[m1->regno] = 1;
1371 /* Now combine the regs used for zero-extension.
1372 This can be done for those not marked `global'
1373 provided their lives don't overlap. */
1375 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1376 mode = GET_MODE_WIDER_MODE (mode))
1378 register struct movable *m0 = 0;
1380 /* Combine all the registers for extension from mode MODE.
1381 Don't combine any that are used outside this loop. */
1382 for (m = movables->head; m; m = m->next)
1383 if (m->partial && ! m->global
1384 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1386 register struct movable *m1;
1387 int first = REGNO_FIRST_LUID (m->regno);
1388 int last = REGNO_LAST_LUID (m->regno);
1392 /* First one: don't check for overlap, just record it. */
1397 /* Make sure they extend to the same mode.
1398 (Almost always true.) */
1399 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1402 /* We already have one: check for overlap with those
1403 already combined together. */
1404 for (m1 = movables->head; m1 != m; m1 = m1->next)
1405 if (m1 == m0 || (m1->partial && m1->match == m0))
1406 if (! (REGNO_FIRST_LUID (m1->regno) > last
1407 || REGNO_LAST_LUID (m1->regno) < first))
1410 /* No overlap: we can combine this with the others. */
1411 m0->lifetime += m->lifetime;
1412 m0->savings += m->savings;
1422 free (matched_regs);
1425 /* Return 1 if regs X and Y will become the same if moved. */
1428 regs_match_p (x, y, movables)
1430 struct loop_movables *movables;
1432 unsigned int xn = REGNO (x);
1433 unsigned int yn = REGNO (y);
1434 struct movable *mx, *my;
1436 for (mx = movables->head; mx; mx = mx->next)
1437 if (mx->regno == xn)
1440 for (my = movables->head; my; my = my->next)
1441 if (my->regno == yn)
1445 && ((mx->match == my->match && mx->match != 0)
1447 || mx == my->match));
1450 /* Return 1 if X and Y are identical-looking rtx's.
1451 This is the Lisp function EQUAL for rtx arguments.
1453 If two registers are matching movables or a movable register and an
1454 equivalent constant, consider them equal. */
1457 rtx_equal_for_loop_p (x, y, movables, regs)
1459 struct loop_movables *movables;
1460 struct loop_regs *regs;
1464 register struct movable *m;
1465 register enum rtx_code code;
1466 register const char *fmt;
1470 if (x == 0 || y == 0)
1473 code = GET_CODE (x);
1475 /* If we have a register and a constant, they may sometimes be
1477 if (GET_CODE (x) == REG && regs->array[REGNO (x)].set_in_loop == -2
1480 for (m = movables->head; m; m = m->next)
1481 if (m->move_insn && m->regno == REGNO (x)
1482 && rtx_equal_p (m->set_src, y))
1485 else if (GET_CODE (y) == REG && regs->array[REGNO (y)].set_in_loop == -2
1488 for (m = movables->head; m; m = m->next)
1489 if (m->move_insn && m->regno == REGNO (y)
1490 && rtx_equal_p (m->set_src, x))
1494 /* Otherwise, rtx's of different codes cannot be equal. */
1495 if (code != GET_CODE (y))
1498 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1499 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1501 if (GET_MODE (x) != GET_MODE (y))
1504 /* These three types of rtx's can be compared nonrecursively. */
1506 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1508 if (code == LABEL_REF)
1509 return XEXP (x, 0) == XEXP (y, 0);
1510 if (code == SYMBOL_REF)
1511 return XSTR (x, 0) == XSTR (y, 0);
1513 /* Compare the elements. If any pair of corresponding elements
1514 fail to match, return 0 for the whole things. */
1516 fmt = GET_RTX_FORMAT (code);
1517 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1522 if (XWINT (x, i) != XWINT (y, i))
1527 if (XINT (x, i) != XINT (y, i))
1532 /* Two vectors must have the same length. */
1533 if (XVECLEN (x, i) != XVECLEN (y, i))
1536 /* And the corresponding elements must match. */
1537 for (j = 0; j < XVECLEN (x, i); j++)
1538 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1539 movables, regs) == 0)
1544 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1550 if (strcmp (XSTR (x, i), XSTR (y, i)))
1555 /* These are just backpointers, so they don't matter. */
1561 /* It is believed that rtx's at this level will never
1562 contain anything but integers and other rtx's,
1563 except for within LABEL_REFs and SYMBOL_REFs. */
1571 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1572 insns in INSNS which use the reference. LABEL_NUSES for CODE_LABEL
1573 references is incremented once for each added note. */
1576 add_label_notes (x, insns)
1580 enum rtx_code code = GET_CODE (x);
1585 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1587 /* This code used to ignore labels that referred to dispatch tables to
1588 avoid flow generating (slighly) worse code.
1590 We no longer ignore such label references (see LABEL_REF handling in
1591 mark_jump_label for additional information). */
1592 for (insn = insns; insn; insn = NEXT_INSN (insn))
1593 if (reg_mentioned_p (XEXP (x, 0), insn))
1595 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1597 if (LABEL_P (XEXP (x, 0)))
1598 LABEL_NUSES (XEXP (x, 0))++;
1602 fmt = GET_RTX_FORMAT (code);
1603 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1606 add_label_notes (XEXP (x, i), insns);
1607 else if (fmt[i] == 'E')
1608 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1609 add_label_notes (XVECEXP (x, i, j), insns);
1613 /* Scan MOVABLES, and move the insns that deserve to be moved.
1614 If two matching movables are combined, replace one reg with the
1615 other throughout. */
1618 move_movables (loop, movables, threshold, insn_count)
1620 struct loop_movables *movables;
1624 struct loop_regs *regs = LOOP_REGS (loop);
1625 int nregs = regs->num;
1627 register struct movable *m;
1629 rtx loop_start = loop->start;
1630 rtx loop_end = loop->end;
1631 /* Map of pseudo-register replacements to handle combining
1632 when we move several insns that load the same value
1633 into different pseudo-registers. */
1634 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1635 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1639 for (m = movables->head; m; m = m->next)
1641 /* Describe this movable insn. */
1643 if (loop_dump_stream)
1645 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1646 INSN_UID (m->insn), m->regno, m->lifetime);
1648 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1650 fprintf (loop_dump_stream, "cond ");
1652 fprintf (loop_dump_stream, "force ");
1654 fprintf (loop_dump_stream, "global ");
1656 fprintf (loop_dump_stream, "done ");
1658 fprintf (loop_dump_stream, "move-insn ");
1660 fprintf (loop_dump_stream, "matches %d ",
1661 INSN_UID (m->match->insn));
1663 fprintf (loop_dump_stream, "forces %d ",
1664 INSN_UID (m->forces->insn));
1667 /* Count movables. Value used in heuristics in strength_reduce. */
1670 /* Ignore the insn if it's already done (it matched something else).
1671 Otherwise, see if it is now safe to move. */
1675 || (1 == loop_invariant_p (loop, m->set_src)
1676 && (m->dependencies == 0
1677 || 1 == loop_invariant_p (loop, m->dependencies))
1679 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1682 && (! m->forces || m->forces->done))
1686 int savings = m->savings;
1688 /* We have an insn that is safe to move.
1689 Compute its desirability. */
1694 if (loop_dump_stream)
1695 fprintf (loop_dump_stream, "savings %d ", savings);
1697 if (regs->array[regno].moved_once && loop_dump_stream)
1698 fprintf (loop_dump_stream, "halved since already moved ");
1700 /* An insn MUST be moved if we already moved something else
1701 which is safe only if this one is moved too: that is,
1702 if already_moved[REGNO] is nonzero. */
1704 /* An insn is desirable to move if the new lifetime of the
1705 register is no more than THRESHOLD times the old lifetime.
1706 If it's not desirable, it means the loop is so big
1707 that moving won't speed things up much,
1708 and it is liable to make register usage worse. */
1710 /* It is also desirable to move if it can be moved at no
1711 extra cost because something else was already moved. */
1713 if (already_moved[regno]
1714 || flag_move_all_movables
1715 || (threshold * savings * m->lifetime) >=
1716 (regs->array[regno].moved_once ? insn_count * 2 : insn_count)
1717 || (m->forces && m->forces->done
1718 && regs->array[m->forces->regno].n_times_set == 1))
1721 register struct movable *m1;
1722 rtx first = NULL_RTX;
1724 /* Now move the insns that set the reg. */
1726 if (m->partial && m->match)
1730 /* Find the end of this chain of matching regs.
1731 Thus, we load each reg in the chain from that one reg.
1732 And that reg is loaded with 0 directly,
1733 since it has ->match == 0. */
1734 for (m1 = m; m1->match; m1 = m1->match);
1735 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1736 SET_DEST (PATTERN (m1->insn)));
1737 i1 = loop_insn_hoist (loop, newpat);
1739 /* Mark the moved, invariant reg as being allowed to
1740 share a hard reg with the other matching invariant. */
1741 REG_NOTES (i1) = REG_NOTES (m->insn);
1742 r1 = SET_DEST (PATTERN (m->insn));
1743 r2 = SET_DEST (PATTERN (m1->insn));
1745 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1746 gen_rtx_EXPR_LIST (VOIDmode, r2,
1748 delete_insn (m->insn);
1753 if (loop_dump_stream)
1754 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1756 /* If we are to re-generate the item being moved with a
1757 new move insn, first delete what we have and then emit
1758 the move insn before the loop. */
1759 else if (m->move_insn)
1763 for (count = m->consec; count >= 0; count--)
1765 /* If this is the first insn of a library call sequence,
1767 if (GET_CODE (p) != NOTE
1768 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1771 /* If this is the last insn of a libcall sequence, then
1772 delete every insn in the sequence except the last.
1773 The last insn is handled in the normal manner. */
1774 if (GET_CODE (p) != NOTE
1775 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1777 temp = XEXP (temp, 0);
1779 temp = delete_insn (temp);
1783 p = delete_insn (p);
1785 /* simplify_giv_expr expects that it can walk the insns
1786 at m->insn forwards and see this old sequence we are
1787 tossing here. delete_insn does preserve the next
1788 pointers, but when we skip over a NOTE we must fix
1789 it up. Otherwise that code walks into the non-deleted
1791 while (p && GET_CODE (p) == NOTE)
1792 p = NEXT_INSN (temp) = NEXT_INSN (p);
1796 emit_move_insn (m->set_dest, m->set_src);
1797 temp = get_insns ();
1798 seq = gen_sequence ();
1801 add_label_notes (m->set_src, temp);
1803 i1 = loop_insn_hoist (loop, seq);
1804 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1806 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1807 m->set_src, REG_NOTES (i1));
1809 if (loop_dump_stream)
1810 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1812 /* The more regs we move, the less we like moving them. */
1817 for (count = m->consec; count >= 0; count--)
1821 /* If first insn of libcall sequence, skip to end. */
1822 /* Do this at start of loop, since p is guaranteed to
1824 if (GET_CODE (p) != NOTE
1825 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1828 /* If last insn of libcall sequence, move all
1829 insns except the last before the loop. The last
1830 insn is handled in the normal manner. */
1831 if (GET_CODE (p) != NOTE
1832 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1836 rtx fn_address_insn = 0;
1839 for (temp = XEXP (temp, 0); temp != p;
1840 temp = NEXT_INSN (temp))
1846 if (GET_CODE (temp) == NOTE)
1849 body = PATTERN (temp);
1851 /* Find the next insn after TEMP,
1852 not counting USE or NOTE insns. */
1853 for (next = NEXT_INSN (temp); next != p;
1854 next = NEXT_INSN (next))
1855 if (! (GET_CODE (next) == INSN
1856 && GET_CODE (PATTERN (next)) == USE)
1857 && GET_CODE (next) != NOTE)
1860 /* If that is the call, this may be the insn
1861 that loads the function address.
1863 Extract the function address from the insn
1864 that loads it into a register.
1865 If this insn was cse'd, we get incorrect code.
1867 So emit a new move insn that copies the
1868 function address into the register that the
1869 call insn will use. flow.c will delete any
1870 redundant stores that we have created. */
1871 if (GET_CODE (next) == CALL_INSN
1872 && GET_CODE (body) == SET
1873 && GET_CODE (SET_DEST (body)) == REG
1874 && (n = find_reg_note (temp, REG_EQUAL,
1877 fn_reg = SET_SRC (body);
1878 if (GET_CODE (fn_reg) != REG)
1879 fn_reg = SET_DEST (body);
1880 fn_address = XEXP (n, 0);
1881 fn_address_insn = temp;
1883 /* We have the call insn.
1884 If it uses the register we suspect it might,
1885 load it with the correct address directly. */
1886 if (GET_CODE (temp) == CALL_INSN
1888 && reg_referenced_p (fn_reg, body))
1889 loop_insn_emit_after (loop, 0, fn_address_insn,
1891 (fn_reg, fn_address));
1893 if (GET_CODE (temp) == CALL_INSN)
1895 i1 = loop_call_insn_hoist (loop, body);
1896 /* Because the USAGE information potentially
1897 contains objects other than hard registers
1898 we need to copy it. */
1899 if (CALL_INSN_FUNCTION_USAGE (temp))
1900 CALL_INSN_FUNCTION_USAGE (i1)
1901 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1904 i1 = loop_insn_hoist (loop, body);
1907 if (temp == fn_address_insn)
1908 fn_address_insn = i1;
1909 REG_NOTES (i1) = REG_NOTES (temp);
1915 if (m->savemode != VOIDmode)
1917 /* P sets REG to zero; but we should clear only
1918 the bits that are not covered by the mode
1920 rtx reg = m->set_dest;
1926 (GET_MODE (reg), and_optab, reg,
1927 GEN_INT ((((HOST_WIDE_INT) 1
1928 << GET_MODE_BITSIZE (m->savemode)))
1930 reg, 1, OPTAB_LIB_WIDEN);
1934 emit_move_insn (reg, tem);
1935 sequence = gen_sequence ();
1937 i1 = loop_insn_hoist (loop, sequence);
1939 else if (GET_CODE (p) == CALL_INSN)
1941 i1 = loop_call_insn_hoist (loop, PATTERN (p));
1942 /* Because the USAGE information potentially
1943 contains objects other than hard registers
1944 we need to copy it. */
1945 if (CALL_INSN_FUNCTION_USAGE (p))
1946 CALL_INSN_FUNCTION_USAGE (i1)
1947 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1949 else if (count == m->consec && m->move_insn_first)
1952 /* The SET_SRC might not be invariant, so we must
1953 use the REG_EQUAL note. */
1955 emit_move_insn (m->set_dest, m->set_src);
1956 temp = get_insns ();
1957 seq = gen_sequence ();
1960 add_label_notes (m->set_src, temp);
1962 i1 = loop_insn_hoist (loop, seq);
1963 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1965 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1967 m->set_src, REG_NOTES (i1));
1970 i1 = loop_insn_hoist (loop, PATTERN (p));
1972 if (REG_NOTES (i1) == 0)
1974 REG_NOTES (i1) = REG_NOTES (p);
1976 /* If there is a REG_EQUAL note present whose value
1977 is not loop invariant, then delete it, since it
1978 may cause problems with later optimization passes.
1979 It is possible for cse to create such notes
1980 like this as a result of record_jump_cond. */
1982 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
1983 && ! loop_invariant_p (loop, XEXP (temp, 0)))
1984 remove_note (i1, temp);
1990 if (loop_dump_stream)
1991 fprintf (loop_dump_stream, " moved to %d",
1994 /* If library call, now fix the REG_NOTES that contain
1995 insn pointers, namely REG_LIBCALL on FIRST
1996 and REG_RETVAL on I1. */
1997 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
1999 XEXP (temp, 0) = first;
2000 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2001 XEXP (temp, 0) = i1;
2008 /* simplify_giv_expr expects that it can walk the insns
2009 at m->insn forwards and see this old sequence we are
2010 tossing here. delete_insn does preserve the next
2011 pointers, but when we skip over a NOTE we must fix
2012 it up. Otherwise that code walks into the non-deleted
2014 while (p && GET_CODE (p) == NOTE)
2015 p = NEXT_INSN (temp) = NEXT_INSN (p);
2018 /* The more regs we move, the less we like moving them. */
2022 /* Any other movable that loads the same register
2024 already_moved[regno] = 1;
2026 /* This reg has been moved out of one loop. */
2027 regs->array[regno].moved_once = 1;
2029 /* The reg set here is now invariant. */
2031 regs->array[regno].set_in_loop = 0;
2035 /* Change the length-of-life info for the register
2036 to say it lives at least the full length of this loop.
2037 This will help guide optimizations in outer loops. */
2039 if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2040 /* This is the old insn before all the moved insns.
2041 We can't use the moved insn because it is out of range
2042 in uid_luid. Only the old insns have luids. */
2043 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2044 if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2045 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2047 /* Combine with this moved insn any other matching movables. */
2050 for (m1 = movables->head; m1; m1 = m1->next)
2055 /* Schedule the reg loaded by M1
2056 for replacement so that shares the reg of M.
2057 If the modes differ (only possible in restricted
2058 circumstances, make a SUBREG.
2060 Note this assumes that the target dependent files
2061 treat REG and SUBREG equally, including within
2062 GO_IF_LEGITIMATE_ADDRESS and in all the
2063 predicates since we never verify that replacing the
2064 original register with a SUBREG results in a
2065 recognizable insn. */
2066 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2067 reg_map[m1->regno] = m->set_dest;
2070 = gen_lowpart_common (GET_MODE (m1->set_dest),
2073 /* Get rid of the matching insn
2074 and prevent further processing of it. */
2077 /* if library call, delete all insn except last, which
2079 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2082 for (temp = XEXP (temp, 0); temp != m1->insn;
2083 temp = NEXT_INSN (temp))
2086 delete_insn (m1->insn);
2088 /* Any other movable that loads the same register
2090 already_moved[m1->regno] = 1;
2092 /* The reg merged here is now invariant,
2093 if the reg it matches is invariant. */
2095 regs->array[m1->regno].set_in_loop = 0;
2098 else if (loop_dump_stream)
2099 fprintf (loop_dump_stream, "not desirable");
2101 else if (loop_dump_stream && !m->match)
2102 fprintf (loop_dump_stream, "not safe");
2104 if (loop_dump_stream)
2105 fprintf (loop_dump_stream, "\n");
2109 new_start = loop_start;
2111 /* Go through all the instructions in the loop, making
2112 all the register substitutions scheduled in REG_MAP. */
2113 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2114 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2115 || GET_CODE (p) == CALL_INSN)
2117 replace_regs (PATTERN (p), reg_map, nregs, 0);
2118 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2124 free (already_moved);
2129 loop_movables_add (movables, m)
2130 struct loop_movables *movables;
2133 if (movables->head == 0)
2136 movables->last->next = m;
2142 loop_movables_free (movables)
2143 struct loop_movables *movables;
2146 struct movable *m_next;
2148 for (m = movables->head; m; m = m_next)
2156 /* Scan X and replace the address of any MEM in it with ADDR.
2157 REG is the address that MEM should have before the replacement. */
2160 replace_call_address (x, reg, addr)
2163 register enum rtx_code code;
2165 register const char *fmt;
2169 code = GET_CODE (x);
2183 /* Short cut for very common case. */
2184 replace_call_address (XEXP (x, 1), reg, addr);
2188 /* Short cut for very common case. */
2189 replace_call_address (XEXP (x, 0), reg, addr);
2193 /* If this MEM uses a reg other than the one we expected,
2194 something is wrong. */
2195 if (XEXP (x, 0) != reg)
2204 fmt = GET_RTX_FORMAT (code);
2205 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2208 replace_call_address (XEXP (x, i), reg, addr);
2209 else if (fmt[i] == 'E')
2212 for (j = 0; j < XVECLEN (x, i); j++)
2213 replace_call_address (XVECEXP (x, i, j), reg, addr);
2219 /* Return the number of memory refs to addresses that vary
2223 count_nonfixed_reads (loop, x)
2224 const struct loop *loop;
2227 register enum rtx_code code;
2229 register const char *fmt;
2235 code = GET_CODE (x);
2249 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2250 + count_nonfixed_reads (loop, XEXP (x, 0)));
2257 fmt = GET_RTX_FORMAT (code);
2258 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2261 value += count_nonfixed_reads (loop, XEXP (x, i));
2265 for (j = 0; j < XVECLEN (x, i); j++)
2266 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2272 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2273 `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2274 `unknown_address_altered', `unknown_constant_address_altered', and
2275 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2276 list `store_mems' in LOOP. */
2282 register int level = 1;
2284 struct loop_info *loop_info = LOOP_INFO (loop);
2285 rtx start = loop->start;
2286 rtx end = loop->end;
2287 /* The label after END. Jumping here is just like falling off the
2288 end of the loop. We use next_nonnote_insn instead of next_label
2289 as a hedge against the (pathological) case where some actual insn
2290 might end up between the two. */
2291 rtx exit_target = next_nonnote_insn (end);
2293 loop_info->has_indirect_jump = indirect_jump_in_function;
2294 loop_info->pre_header_has_call = 0;
2295 loop_info->has_call = 0;
2296 loop_info->has_nonconst_call = 0;
2297 loop_info->has_volatile = 0;
2298 loop_info->has_tablejump = 0;
2299 loop_info->has_multiple_exit_targets = 0;
2302 loop_info->unknown_address_altered = 0;
2303 loop_info->unknown_constant_address_altered = 0;
2304 loop_info->store_mems = NULL_RTX;
2305 loop_info->first_loop_store_insn = NULL_RTX;
2306 loop_info->mems_idx = 0;
2307 loop_info->num_mem_sets = 0;
2310 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
2311 insn = PREV_INSN (insn))
2313 if (GET_CODE (insn) == CALL_INSN)
2315 loop_info->pre_header_has_call = 1;
2320 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2321 insn = NEXT_INSN (insn))
2323 if (GET_CODE (insn) == NOTE)
2325 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2328 /* Count number of loops contained in this one. */
2331 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2336 else if (GET_CODE (insn) == CALL_INSN)
2338 if (! CONST_CALL_P (insn))
2340 loop_info->unknown_address_altered = 1;
2341 loop_info->has_nonconst_call = 1;
2343 loop_info->has_call = 1;
2345 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2347 rtx label1 = NULL_RTX;
2348 rtx label2 = NULL_RTX;
2350 if (volatile_refs_p (PATTERN (insn)))
2351 loop_info->has_volatile = 1;
2353 if (GET_CODE (insn) == JUMP_INSN
2354 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2355 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2356 loop_info->has_tablejump = 1;
2358 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2359 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2360 loop_info->first_loop_store_insn = insn;
2362 if (! loop_info->has_multiple_exit_targets
2363 && GET_CODE (insn) == JUMP_INSN
2364 && GET_CODE (PATTERN (insn)) == SET
2365 && SET_DEST (PATTERN (insn)) == pc_rtx)
2367 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2369 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2370 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2374 label1 = SET_SRC (PATTERN (insn));
2379 if (label1 && label1 != pc_rtx)
2381 if (GET_CODE (label1) != LABEL_REF)
2383 /* Something tricky. */
2384 loop_info->has_multiple_exit_targets = 1;
2387 else if (XEXP (label1, 0) != exit_target
2388 && LABEL_OUTSIDE_LOOP_P (label1))
2390 /* A jump outside the current loop. */
2391 loop_info->has_multiple_exit_targets = 1;
2402 else if (GET_CODE (insn) == RETURN)
2403 loop_info->has_multiple_exit_targets = 1;
2406 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2407 if (/* An exception thrown by a called function might land us
2409 ! loop_info->has_nonconst_call
2410 /* We don't want loads for MEMs moved to a location before the
2411 one at which their stack memory becomes allocated. (Note
2412 that this is not a problem for malloc, etc., since those
2413 require actual function calls. */
2414 && ! current_function_calls_alloca
2415 /* There are ways to leave the loop other than falling off the
2417 && ! loop_info->has_multiple_exit_targets)
2418 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2419 insn = NEXT_INSN (insn))
2420 for_each_rtx (&insn, insert_loop_mem, loop_info);
2422 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2423 that loop_invariant_p and load_mems can use true_dependence
2424 to determine what is really clobbered. */
2425 if (loop_info->unknown_address_altered)
2427 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2429 loop_info->store_mems
2430 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2432 if (loop_info->unknown_constant_address_altered)
2434 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2436 RTX_UNCHANGING_P (mem) = 1;
2437 loop_info->store_mems
2438 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2442 /* Scan the function looking for loops. Record the start and end of each loop.
2443 Also mark as invalid loops any loops that contain a setjmp or are branched
2444 to from outside the loop. */
2447 find_and_verify_loops (f, loops)
2449 struct loops *loops;
2454 struct loop *current_loop;
2455 struct loop *next_loop;
2458 num_loops = loops->num;
2460 compute_luids (f, NULL_RTX, 0);
2462 /* If there are jumps to undefined labels,
2463 treat them as jumps out of any/all loops.
2464 This also avoids writing past end of tables when there are no loops. */
2467 /* Find boundaries of loops, mark which loops are contained within
2468 loops, and invalidate loops that have setjmp. */
2471 current_loop = NULL;
2472 for (insn = f; insn; insn = NEXT_INSN (insn))
2474 if (GET_CODE (insn) == NOTE)
2475 switch (NOTE_LINE_NUMBER (insn))
2477 case NOTE_INSN_LOOP_BEG:
2478 next_loop = loops->array + num_loops;
2479 next_loop->num = num_loops;
2481 next_loop->start = insn;
2482 next_loop->outer = current_loop;
2483 current_loop = next_loop;
2486 case NOTE_INSN_SETJMP:
2487 /* In this case, we must invalidate our current loop and any
2489 for (loop = current_loop; loop; loop = loop->outer)
2492 if (loop_dump_stream)
2493 fprintf (loop_dump_stream,
2494 "\nLoop at %d ignored due to setjmp.\n",
2495 INSN_UID (loop->start));
2499 case NOTE_INSN_LOOP_CONT:
2500 current_loop->cont = insn;
2503 case NOTE_INSN_LOOP_VTOP:
2504 current_loop->vtop = insn;
2507 case NOTE_INSN_LOOP_END:
2511 current_loop->end = insn;
2512 current_loop = current_loop->outer;
2519 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2520 enclosing loop, but this doesn't matter. */
2521 uid_loop[INSN_UID (insn)] = current_loop;
2524 /* Any loop containing a label used in an initializer must be invalidated,
2525 because it can be jumped into from anywhere. */
2527 for (label = forced_labels; label; label = XEXP (label, 1))
2529 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2530 loop; loop = loop->outer)
2534 /* Any loop containing a label used for an exception handler must be
2535 invalidated, because it can be jumped into from anywhere. */
2537 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2539 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2540 loop; loop = loop->outer)
2544 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2545 loop that it is not contained within, that loop is marked invalid.
2546 If any INSN or CALL_INSN uses a label's address, then the loop containing
2547 that label is marked invalid, because it could be jumped into from
2550 Also look for blocks of code ending in an unconditional branch that
2551 exits the loop. If such a block is surrounded by a conditional
2552 branch around the block, move the block elsewhere (see below) and
2553 invert the jump to point to the code block. This may eliminate a
2554 label in our loop and will simplify processing by both us and a
2555 possible second cse pass. */
2557 for (insn = f; insn; insn = NEXT_INSN (insn))
2560 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2562 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2564 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2567 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2568 loop; loop = loop->outer)
2573 if (GET_CODE (insn) != JUMP_INSN)
2576 mark_loop_jump (PATTERN (insn), this_loop);
2578 /* See if this is an unconditional branch outside the loop. */
2580 && (GET_CODE (PATTERN (insn)) == RETURN
2581 || (any_uncondjump_p (insn)
2582 && onlyjump_p (insn)
2583 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2585 && get_max_uid () < max_uid_for_loop)
2588 rtx our_next = next_real_insn (insn);
2589 rtx last_insn_to_move = NEXT_INSN (insn);
2590 struct loop *dest_loop;
2591 struct loop *outer_loop = NULL;
2593 /* Go backwards until we reach the start of the loop, a label,
2595 for (p = PREV_INSN (insn);
2596 GET_CODE (p) != CODE_LABEL
2597 && ! (GET_CODE (p) == NOTE
2598 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2599 && GET_CODE (p) != JUMP_INSN;
2603 /* Check for the case where we have a jump to an inner nested
2604 loop, and do not perform the optimization in that case. */
2606 if (JUMP_LABEL (insn))
2608 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2611 for (outer_loop = dest_loop; outer_loop;
2612 outer_loop = outer_loop->outer)
2613 if (outer_loop == this_loop)
2618 /* Make sure that the target of P is within the current loop. */
2620 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2621 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2622 outer_loop = this_loop;
2624 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2625 we have a block of code to try to move.
2627 We look backward and then forward from the target of INSN
2628 to find a BARRIER at the same loop depth as the target.
2629 If we find such a BARRIER, we make a new label for the start
2630 of the block, invert the jump in P and point it to that label,
2631 and move the block of code to the spot we found. */
2634 && GET_CODE (p) == JUMP_INSN
2635 && JUMP_LABEL (p) != 0
2636 /* Just ignore jumps to labels that were never emitted.
2637 These always indicate compilation errors. */
2638 && INSN_UID (JUMP_LABEL (p)) != 0
2639 && any_condjump_p (p) && onlyjump_p (p)
2640 && next_real_insn (JUMP_LABEL (p)) == our_next
2641 /* If it's not safe to move the sequence, then we
2643 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2644 &last_insn_to_move))
2647 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2648 struct loop *target_loop = uid_loop[INSN_UID (target)];
2651 for (loc = target; loc; loc = PREV_INSN (loc))
2652 if (GET_CODE (loc) == BARRIER
2653 /* Don't move things inside a tablejump. */
2654 && ((loc2 = next_nonnote_insn (loc)) == 0
2655 || GET_CODE (loc2) != CODE_LABEL
2656 || (loc2 = next_nonnote_insn (loc2)) == 0
2657 || GET_CODE (loc2) != JUMP_INSN
2658 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2659 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2660 && uid_loop[INSN_UID (loc)] == target_loop)
2664 for (loc = target; loc; loc = NEXT_INSN (loc))
2665 if (GET_CODE (loc) == BARRIER
2666 /* Don't move things inside a tablejump. */
2667 && ((loc2 = next_nonnote_insn (loc)) == 0
2668 || GET_CODE (loc2) != CODE_LABEL
2669 || (loc2 = next_nonnote_insn (loc2)) == 0
2670 || GET_CODE (loc2) != JUMP_INSN
2671 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2672 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2673 && uid_loop[INSN_UID (loc)] == target_loop)
2678 rtx cond_label = JUMP_LABEL (p);
2679 rtx new_label = get_label_after (p);
2681 /* Ensure our label doesn't go away. */
2682 LABEL_NUSES (cond_label)++;
2684 /* Verify that uid_loop is large enough and that
2686 if (invert_jump (p, new_label, 1))
2690 /* If no suitable BARRIER was found, create a suitable
2691 one before TARGET. Since TARGET is a fall through
2692 path, we'll need to insert an jump around our block
2693 and a add a BARRIER before TARGET.
2695 This creates an extra unconditional jump outside
2696 the loop. However, the benefits of removing rarely
2697 executed instructions from inside the loop usually
2698 outweighs the cost of the extra unconditional jump
2699 outside the loop. */
2704 temp = gen_jump (JUMP_LABEL (insn));
2705 temp = emit_jump_insn_before (temp, target);
2706 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2707 LABEL_NUSES (JUMP_LABEL (insn))++;
2708 loc = emit_barrier_before (target);
2711 /* Include the BARRIER after INSN and copy the
2713 new_label = squeeze_notes (new_label,
2715 reorder_insns (new_label, last_insn_to_move, loc);
2717 /* All those insns are now in TARGET_LOOP. */
2719 q != NEXT_INSN (last_insn_to_move);
2721 uid_loop[INSN_UID (q)] = target_loop;
2723 /* The label jumped to by INSN is no longer a loop
2724 exit. Unless INSN does not have a label (e.g.,
2725 it is a RETURN insn), search loop->exit_labels
2726 to find its label_ref, and remove it. Also turn
2727 off LABEL_OUTSIDE_LOOP_P bit. */
2728 if (JUMP_LABEL (insn))
2730 for (q = 0, r = this_loop->exit_labels;
2732 q = r, r = LABEL_NEXTREF (r))
2733 if (XEXP (r, 0) == JUMP_LABEL (insn))
2735 LABEL_OUTSIDE_LOOP_P (r) = 0;
2737 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2739 this_loop->exit_labels = LABEL_NEXTREF (r);
2743 for (loop = this_loop; loop && loop != target_loop;
2747 /* If we didn't find it, then something is
2753 /* P is now a jump outside the loop, so it must be put
2754 in loop->exit_labels, and marked as such.
2755 The easiest way to do this is to just call
2756 mark_loop_jump again for P. */
2757 mark_loop_jump (PATTERN (p), this_loop);
2759 /* If INSN now jumps to the insn after it,
2761 if (JUMP_LABEL (insn) != 0
2762 && (next_real_insn (JUMP_LABEL (insn))
2763 == next_real_insn (insn)))
2767 /* Continue the loop after where the conditional
2768 branch used to jump, since the only branch insn
2769 in the block (if it still remains) is an inter-loop
2770 branch and hence needs no processing. */
2771 insn = NEXT_INSN (cond_label);
2773 if (--LABEL_NUSES (cond_label) == 0)
2774 delete_insn (cond_label);
2776 /* This loop will be continued with NEXT_INSN (insn). */
2777 insn = PREV_INSN (insn);
2784 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2785 loops it is contained in, mark the target loop invalid.
2787 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2790 mark_loop_jump (x, loop)
2794 struct loop *dest_loop;
2795 struct loop *outer_loop;
2798 switch (GET_CODE (x))
2811 /* There could be a label reference in here. */
2812 mark_loop_jump (XEXP (x, 0), loop);
2818 mark_loop_jump (XEXP (x, 0), loop);
2819 mark_loop_jump (XEXP (x, 1), loop);
2823 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2824 mark_loop_jump (XEXP (x, 1), loop);
2829 mark_loop_jump (XEXP (x, 0), loop);
2833 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2835 /* Link together all labels that branch outside the loop. This
2836 is used by final_[bg]iv_value and the loop unrolling code. Also
2837 mark this LABEL_REF so we know that this branch should predict
2840 /* A check to make sure the label is not in an inner nested loop,
2841 since this does not count as a loop exit. */
2844 for (outer_loop = dest_loop; outer_loop;
2845 outer_loop = outer_loop->outer)
2846 if (outer_loop == loop)
2852 if (loop && ! outer_loop)
2854 LABEL_OUTSIDE_LOOP_P (x) = 1;
2855 LABEL_NEXTREF (x) = loop->exit_labels;
2856 loop->exit_labels = x;
2858 for (outer_loop = loop;
2859 outer_loop && outer_loop != dest_loop;
2860 outer_loop = outer_loop->outer)
2861 outer_loop->exit_count++;
2864 /* If this is inside a loop, but not in the current loop or one enclosed
2865 by it, it invalidates at least one loop. */
2870 /* We must invalidate every nested loop containing the target of this
2871 label, except those that also contain the jump insn. */
2873 for (; dest_loop; dest_loop = dest_loop->outer)
2875 /* Stop when we reach a loop that also contains the jump insn. */
2876 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2877 if (dest_loop == outer_loop)
2880 /* If we get here, we know we need to invalidate a loop. */
2881 if (loop_dump_stream && ! dest_loop->invalid)
2882 fprintf (loop_dump_stream,
2883 "\nLoop at %d ignored due to multiple entry points.\n",
2884 INSN_UID (dest_loop->start));
2886 dest_loop->invalid = 1;
2891 /* If this is not setting pc, ignore. */
2892 if (SET_DEST (x) == pc_rtx)
2893 mark_loop_jump (SET_SRC (x), loop);
2897 mark_loop_jump (XEXP (x, 1), loop);
2898 mark_loop_jump (XEXP (x, 2), loop);
2903 for (i = 0; i < XVECLEN (x, 0); i++)
2904 mark_loop_jump (XVECEXP (x, 0, i), loop);
2908 for (i = 0; i < XVECLEN (x, 1); i++)
2909 mark_loop_jump (XVECEXP (x, 1, i), loop);
2913 /* Strictly speaking this is not a jump into the loop, only a possible
2914 jump out of the loop. However, we have no way to link the destination
2915 of this jump onto the list of exit labels. To be safe we mark this
2916 loop and any containing loops as invalid. */
2919 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2921 if (loop_dump_stream && ! outer_loop->invalid)
2922 fprintf (loop_dump_stream,
2923 "\nLoop at %d ignored due to unknown exit jump.\n",
2924 INSN_UID (outer_loop->start));
2925 outer_loop->invalid = 1;
2932 /* Return nonzero if there is a label in the range from
2933 insn INSN to and including the insn whose luid is END
2934 INSN must have an assigned luid (i.e., it must not have
2935 been previously created by loop.c). */
2938 labels_in_range_p (insn, end)
2942 while (insn && INSN_LUID (insn) <= end)
2944 if (GET_CODE (insn) == CODE_LABEL)
2946 insn = NEXT_INSN (insn);
2952 /* Record that a memory reference X is being set. */
2955 note_addr_stored (x, y, data)
2957 rtx y ATTRIBUTE_UNUSED;
2958 void *data ATTRIBUTE_UNUSED;
2960 struct loop_info *loop_info = data;
2962 if (x == 0 || GET_CODE (x) != MEM)
2965 /* Count number of memory writes.
2966 This affects heuristics in strength_reduce. */
2967 loop_info->num_mem_sets++;
2969 /* BLKmode MEM means all memory is clobbered. */
2970 if (GET_MODE (x) == BLKmode)
2972 if (RTX_UNCHANGING_P (x))
2973 loop_info->unknown_constant_address_altered = 1;
2975 loop_info->unknown_address_altered = 1;
2980 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2981 loop_info->store_mems);
2984 /* X is a value modified by an INSN that references a biv inside a loop
2985 exit test (ie, X is somehow related to the value of the biv). If X
2986 is a pseudo that is used more than once, then the biv is (effectively)
2987 used more than once. DATA is a pointer to a loop_regs structure. */
2990 note_set_pseudo_multiple_uses (x, y, data)
2992 rtx y ATTRIBUTE_UNUSED;
2995 struct loop_regs *regs = (struct loop_regs *) data;
3000 while (GET_CODE (x) == STRICT_LOW_PART
3001 || GET_CODE (x) == SIGN_EXTRACT
3002 || GET_CODE (x) == ZERO_EXTRACT
3003 || GET_CODE (x) == SUBREG)
3006 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
3009 /* If we do not have usage information, or if we know the register
3010 is used more than once, note that fact for check_dbra_loop. */
3011 if (REGNO (x) >= max_reg_before_loop
3012 || ! regs->array[REGNO (x)].single_usage
3013 || regs->array[REGNO (x)].single_usage == const0_rtx)
3014 regs->multiple_uses = 1;
3017 /* Return nonzero if the rtx X is invariant over the current loop.
3019 The value is 2 if we refer to something only conditionally invariant.
3021 A memory ref is invariant if it is not volatile and does not conflict
3022 with anything stored in `loop_info->store_mems'. */
3025 loop_invariant_p (loop, x)
3026 const struct loop *loop;
3029 struct loop_info *loop_info = LOOP_INFO (loop);
3030 struct loop_regs *regs = LOOP_REGS (loop);
3032 register enum rtx_code code;
3033 register const char *fmt;
3034 int conditional = 0;
3039 code = GET_CODE (x);
3049 /* A LABEL_REF is normally invariant, however, if we are unrolling
3050 loops, and this label is inside the loop, then it isn't invariant.
3051 This is because each unrolled copy of the loop body will have
3052 a copy of this label. If this was invariant, then an insn loading
3053 the address of this label into a register might get moved outside
3054 the loop, and then each loop body would end up using the same label.
3056 We don't know the loop bounds here though, so just fail for all
3058 if (flag_unroll_loops)
3065 case UNSPEC_VOLATILE:
3069 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3070 since the reg might be set by initialization within the loop. */
3072 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3073 || x == arg_pointer_rtx)
3074 && ! current_function_has_nonlocal_goto)
3077 if (LOOP_INFO (loop)->has_call
3078 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3081 if (regs->array[REGNO (x)].set_in_loop < 0)
3084 return regs->array[REGNO (x)].set_in_loop == 0;
3087 /* Volatile memory references must be rejected. Do this before
3088 checking for read-only items, so that volatile read-only items
3089 will be rejected also. */
3090 if (MEM_VOLATILE_P (x))
3093 /* See if there is any dependence between a store and this load. */
3094 mem_list_entry = loop_info->store_mems;
3095 while (mem_list_entry)
3097 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3101 mem_list_entry = XEXP (mem_list_entry, 1);
3104 /* It's not invalidated by a store in memory
3105 but we must still verify the address is invariant. */
3109 /* Don't mess with insns declared volatile. */
3110 if (MEM_VOLATILE_P (x))
3118 fmt = GET_RTX_FORMAT (code);
3119 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3123 int tem = loop_invariant_p (loop, XEXP (x, i));
3129 else if (fmt[i] == 'E')
3132 for (j = 0; j < XVECLEN (x, i); j++)
3134 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3144 return 1 + conditional;
3147 /* Return nonzero if all the insns in the loop that set REG
3148 are INSN and the immediately following insns,
3149 and if each of those insns sets REG in an invariant way
3150 (not counting uses of REG in them).
3152 The value is 2 if some of these insns are only conditionally invariant.
3154 We assume that INSN itself is the first set of REG
3155 and that its source is invariant. */
3158 consec_sets_invariant_p (loop, reg, n_sets, insn)
3159 const struct loop *loop;
3163 struct loop_regs *regs = LOOP_REGS (loop);
3165 unsigned int regno = REGNO (reg);
3167 /* Number of sets we have to insist on finding after INSN. */
3168 int count = n_sets - 1;
3169 int old = regs->array[regno].set_in_loop;
3173 /* If N_SETS hit the limit, we can't rely on its value. */
3177 regs->array[regno].set_in_loop = 0;
3181 register enum rtx_code code;
3185 code = GET_CODE (p);
3187 /* If library call, skip to end of it. */
3188 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3193 && (set = single_set (p))
3194 && GET_CODE (SET_DEST (set)) == REG
3195 && REGNO (SET_DEST (set)) == regno)
3197 this = loop_invariant_p (loop, SET_SRC (set));
3200 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3202 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3203 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3205 this = (CONSTANT_P (XEXP (temp, 0))
3206 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3207 && loop_invariant_p (loop, XEXP (temp, 0))));
3214 else if (code != NOTE)
3216 regs->array[regno].set_in_loop = old;
3221 regs->array[regno].set_in_loop = old;
3222 /* If loop_invariant_p ever returned 2, we return 2. */
3223 return 1 + (value & 2);
3227 /* I don't think this condition is sufficient to allow INSN
3228 to be moved, so we no longer test it. */
3230 /* Return 1 if all insns in the basic block of INSN and following INSN
3231 that set REG are invariant according to TABLE. */
3234 all_sets_invariant_p (reg, insn, table)
3238 register rtx p = insn;
3239 register int regno = REGNO (reg);
3243 register enum rtx_code code;
3245 code = GET_CODE (p);
3246 if (code == CODE_LABEL || code == JUMP_INSN)
3248 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3249 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3250 && REGNO (SET_DEST (PATTERN (p))) == regno)
3252 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3259 /* Look at all uses (not sets) of registers in X. For each, if it is
3260 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3261 a different insn, set USAGE[REGNO] to const0_rtx. */
3264 find_single_use_in_loop (regs, insn, x)
3265 struct loop_regs *regs;
3269 enum rtx_code code = GET_CODE (x);
3270 const char *fmt = GET_RTX_FORMAT (code);
3274 regs->array[REGNO (x)].single_usage
3275 = (regs->array[REGNO (x)].single_usage != 0
3276 && regs->array[REGNO (x)].single_usage != insn)
3277 ? const0_rtx : insn;
3279 else if (code == SET)
3281 /* Don't count SET_DEST if it is a REG; otherwise count things
3282 in SET_DEST because if a register is partially modified, it won't
3283 show up as a potential movable so we don't care how USAGE is set
3285 if (GET_CODE (SET_DEST (x)) != REG)
3286 find_single_use_in_loop (regs, insn, SET_DEST (x));
3287 find_single_use_in_loop (regs, insn, SET_SRC (x));
3290 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3292 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3293 find_single_use_in_loop (regs, insn, XEXP (x, i));
3294 else if (fmt[i] == 'E')
3295 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3296 find_single_use_in_loop (regs, insn, XVECEXP (x, i, j));
3300 /* Count and record any set in X which is contained in INSN. Update
3301 REGS->array[I].MAY_NOT_OPTIMIZE and LAST_SET for any register I set
3305 count_one_set (regs, insn, x, last_set)
3306 struct loop_regs *regs;
3310 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3311 /* Don't move a reg that has an explicit clobber.
3312 It's not worth the pain to try to do it correctly. */
3313 regs->array[REGNO (XEXP (x, 0))].may_not_optimize = 1;
3315 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3317 rtx dest = SET_DEST (x);
3318 while (GET_CODE (dest) == SUBREG
3319 || GET_CODE (dest) == ZERO_EXTRACT
3320 || GET_CODE (dest) == SIGN_EXTRACT
3321 || GET_CODE (dest) == STRICT_LOW_PART)
3322 dest = XEXP (dest, 0);
3323 if (GET_CODE (dest) == REG)
3325 register int regno = REGNO (dest);
3326 /* If this is the first setting of this reg
3327 in current basic block, and it was set before,
3328 it must be set in two basic blocks, so it cannot
3329 be moved out of the loop. */
3330 if (regs->array[regno].set_in_loop > 0
3332 regs->array[regno].may_not_optimize = 1;
3333 /* If this is not first setting in current basic block,
3334 see if reg was used in between previous one and this.
3335 If so, neither one can be moved. */
3336 if (last_set[regno] != 0
3337 && reg_used_between_p (dest, last_set[regno], insn))
3338 regs->array[regno].may_not_optimize = 1;
3339 if (regs->array[regno].set_in_loop < 127)
3340 ++regs->array[regno].set_in_loop;
3341 last_set[regno] = insn;
3346 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3347 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3348 contained in insn INSN is used by any insn that precedes INSN in
3349 cyclic order starting from the loop entry point.
3351 We don't want to use INSN_LUID here because if we restrict INSN to those
3352 that have a valid INSN_LUID, it means we cannot move an invariant out
3353 from an inner loop past two loops. */
3356 loop_reg_used_before_p (loop, set, insn)
3357 const struct loop *loop;
3360 rtx reg = SET_DEST (set);
3363 /* Scan forward checking for register usage. If we hit INSN, we
3364 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3365 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3367 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3377 /* A "basic induction variable" or biv is a pseudo reg that is set
3378 (within this loop) only by incrementing or decrementing it. */
3379 /* A "general induction variable" or giv is a pseudo reg whose
3380 value is a linear function of a biv. */
3382 /* Bivs are recognized by `basic_induction_var';
3383 Givs by `general_induction_var'. */
3385 /* Communication with routines called via `note_stores'. */
3387 static rtx note_insn;
3389 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3391 static rtx addr_placeholder;
3393 /* ??? Unfinished optimizations, and possible future optimizations,
3394 for the strength reduction code. */
3396 /* ??? The interaction of biv elimination, and recognition of 'constant'
3397 bivs, may cause problems. */
3399 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3400 performance problems.
3402 Perhaps don't eliminate things that can be combined with an addressing
3403 mode. Find all givs that have the same biv, mult_val, and add_val;
3404 then for each giv, check to see if its only use dies in a following
3405 memory address. If so, generate a new memory address and check to see
3406 if it is valid. If it is valid, then store the modified memory address,
3407 otherwise, mark the giv as not done so that it will get its own iv. */
3409 /* ??? Could try to optimize branches when it is known that a biv is always
3412 /* ??? When replace a biv in a compare insn, we should replace with closest
3413 giv so that an optimized branch can still be recognized by the combiner,
3414 e.g. the VAX acb insn. */
3416 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3417 was rerun in loop_optimize whenever a register was added or moved.
3418 Also, some of the optimizations could be a little less conservative. */
3420 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3421 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3424 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3425 loop iteration except for the last one.
3427 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3431 for_each_insn_in_loop (loop, fncall)
3433 loop_insn_callback fncall;
3435 /* This is 1 if current insn is not executed at least once for every loop
3437 int not_every_iteration = 0;
3438 int maybe_multiple = 0;
3439 int past_loop_latch = 0;
3443 /* If loop_scan_start points to the loop exit test, we have to be wary of
3444 subversive use of gotos inside expression statements. */
3445 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3446 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3448 /* Scan through loop to find all possible bivs. */
3450 for (p = next_insn_in_loop (loop, loop->scan_start);
3452 p = next_insn_in_loop (loop, p))
3454 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3456 /* Past CODE_LABEL, we get to insns that may be executed multiple
3457 times. The only way we can be sure that they can't is if every
3458 jump insn between here and the end of the loop either
3459 returns, exits the loop, is a jump to a location that is still
3460 behind the label, or is a jump to the loop start. */
3462 if (GET_CODE (p) == CODE_LABEL)
3470 insn = NEXT_INSN (insn);
3471 if (insn == loop->scan_start)
3473 if (insn == loop->end)
3479 if (insn == loop->scan_start)
3483 if (GET_CODE (insn) == JUMP_INSN
3484 && GET_CODE (PATTERN (insn)) != RETURN
3485 && (!any_condjump_p (insn)
3486 || (JUMP_LABEL (insn) != 0
3487 && JUMP_LABEL (insn) != loop->scan_start
3488 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3496 /* Past a jump, we get to insns for which we can't count
3497 on whether they will be executed during each iteration. */
3498 /* This code appears twice in strength_reduce. There is also similar
3499 code in scan_loop. */
3500 if (GET_CODE (p) == JUMP_INSN
3501 /* If we enter the loop in the middle, and scan around to the
3502 beginning, don't set not_every_iteration for that.
3503 This can be any kind of jump, since we want to know if insns
3504 will be executed if the loop is executed. */
3505 && !(JUMP_LABEL (p) == loop->top
3506 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3507 && any_uncondjump_p (p))
3508 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3512 /* If this is a jump outside the loop, then it also doesn't
3513 matter. Check to see if the target of this branch is on the
3514 loop->exits_labels list. */
3516 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3517 if (XEXP (label, 0) == JUMP_LABEL (p))
3521 not_every_iteration = 1;
3524 else if (GET_CODE (p) == NOTE)
3526 /* At the virtual top of a converted loop, insns are again known to
3527 be executed each iteration: logically, the loop begins here
3528 even though the exit code has been duplicated.
3530 Insns are also again known to be executed each iteration at
3531 the LOOP_CONT note. */
3532 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3533 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3535 not_every_iteration = 0;
3536 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3538 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3542 /* Note if we pass a loop latch. If we do, then we can not clear
3543 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3544 a loop since a jump before the last CODE_LABEL may have started
3545 a new loop iteration.
3547 Note that LOOP_TOP is only set for rotated loops and we need
3548 this check for all loops, so compare against the CODE_LABEL
3549 which immediately follows LOOP_START. */
3550 if (GET_CODE (p) == JUMP_INSN
3551 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3552 past_loop_latch = 1;
3554 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3555 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3556 or not an insn is known to be executed each iteration of the
3557 loop, whether or not any iterations are known to occur.
3559 Therefore, if we have just passed a label and have no more labels
3560 between here and the test insn of the loop, and we have not passed
3561 a jump to the top of the loop, then we know these insns will be
3562 executed each iteration. */
3564 if (not_every_iteration
3566 && GET_CODE (p) == CODE_LABEL
3567 && no_labels_between_p (p, loop->end)
3568 && loop_insn_first_p (p, loop->cont))
3569 not_every_iteration = 0;
3574 loop_bivs_find (loop)
3577 struct loop_regs *regs = LOOP_REGS (loop);
3578 struct loop_ivs *ivs = LOOP_IVS (loop);
3579 /* Temporary list pointers for traversing ivs->list. */
3580 struct iv_class *bl, **backbl;
3584 for_each_insn_in_loop (loop, check_insn_for_bivs);
3586 /* Scan ivs->list to remove all regs that proved not to be bivs.
3587 Make a sanity check against regs->n_times_set. */
3588 for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
3590 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3591 /* Above happens if register modified by subreg, etc. */
3592 /* Make sure it is not recognized as a basic induction var: */
3593 || regs->array[bl->regno].n_times_set != bl->biv_count
3594 /* If never incremented, it is invariant that we decided not to
3595 move. So leave it alone. */
3596 || ! bl->incremented)
3598 if (loop_dump_stream)
3599 fprintf (loop_dump_stream, "Biv %d: discarded, %s\n",
3601 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3602 ? "not induction variable"
3603 : (! bl->incremented ? "never incremented"
3606 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3613 if (loop_dump_stream)
3614 fprintf (loop_dump_stream, "Biv %d: verified\n", bl->regno);
3620 /* Determine how BIVS are initialised by looking through pre-header
3621 extended basic block. */
3623 loop_bivs_init_find (loop)
3626 struct loop_ivs *ivs = LOOP_IVS (loop);
3627 /* Temporary list pointers for traversing ivs->list. */
3628 struct iv_class *bl;
3632 /* Find initial value for each biv by searching backwards from loop_start,
3633 halting at first label. Also record any test condition. */
3636 for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3642 if (GET_CODE (p) == CALL_INSN)
3646 note_stores (PATTERN (p), record_initial, ivs);
3648 /* Record any test of a biv that branches around the loop if no store
3649 between it and the start of loop. We only care about tests with
3650 constants and registers and only certain of those. */
3651 if (GET_CODE (p) == JUMP_INSN
3652 && JUMP_LABEL (p) != 0
3653 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
3654 && (test = get_condition_for_loop (loop, p)) != 0
3655 && GET_CODE (XEXP (test, 0)) == REG
3656 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3657 && (bl = REG_IV_CLASS (ivs, REGNO (XEXP (test, 0)))) != 0
3658 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop->start)
3659 && bl->init_insn == 0)
3661 /* If an NE test, we have an initial value! */
3662 if (GET_CODE (test) == NE)
3665 bl->init_set = gen_rtx_SET (VOIDmode,
3666 XEXP (test, 0), XEXP (test, 1));
3669 bl->initial_test = test;
3675 /* Look at the each biv and see if we can say anything better about its
3676 initial value from any initializing insns set up above. (This is done
3677 in two passes to avoid missing SETs in a PARALLEL.) */
3679 loop_bivs_check (loop)
3682 struct loop_ivs *ivs = LOOP_IVS (loop);
3683 /* Temporary list pointers for traversing ivs->list. */
3684 struct iv_class *bl;
3685 struct iv_class **backbl;
3687 for (backbl = &ivs->list; (bl = *backbl); backbl = &bl->next)
3692 if (! bl->init_insn)
3695 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3696 is a constant, use the value of that. */
3697 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3698 && CONSTANT_P (XEXP (note, 0)))
3699 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3700 && CONSTANT_P (XEXP (note, 0))))
3701 src = XEXP (note, 0);
3703 src = SET_SRC (bl->init_set);
3705 if (loop_dump_stream)
3706 fprintf (loop_dump_stream,
3707 "Biv %d: initialized at insn %d: initial value ",
3708 bl->regno, INSN_UID (bl->init_insn));
3710 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3711 || GET_MODE (src) == VOIDmode)
3712 && valid_initial_value_p (src, bl->init_insn,
3713 LOOP_INFO (loop)->pre_header_has_call,
3716 bl->initial_value = src;
3718 if (loop_dump_stream)
3720 print_simple_rtl (loop_dump_stream, src);
3721 fputc ('\n', loop_dump_stream);
3724 /* If we can't make it a giv,
3725 let biv keep initial value of "itself". */
3726 else if (loop_dump_stream)
3727 fprintf (loop_dump_stream, "is complex\n");
3732 /* Search the loop for general induction variables. */
3735 loop_givs_find (loop)
3738 for_each_insn_in_loop (loop, check_insn_for_givs);
3742 /* For each giv for which we still don't know whether or not it is
3743 replaceable, check to see if it is replaceable because its final value
3744 can be calculated. */
3747 loop_givs_check (loop)
3750 struct loop_ivs *ivs = LOOP_IVS (loop);
3751 struct iv_class *bl;
3753 for (bl = ivs->list; bl; bl = bl->next)
3755 struct induction *v;
3757 for (v = bl->giv; v; v = v->next_iv)
3758 if (! v->replaceable && ! v->not_replaceable)
3759 check_final_value (loop, v);
3764 /* Return non-zero if it is possible to eliminate the biv BL provided
3765 all givs are reduced. This is possible if either the reg is not
3766 used outside the loop, or we can compute what its final value will
3770 loop_biv_eliminable_p (loop, bl, threshold, insn_count)
3772 struct iv_class *bl;
3776 /* For architectures with a decrement_and_branch_until_zero insn,
3777 don't do this if we put a REG_NONNEG note on the endtest for this
3780 #ifdef HAVE_decrement_and_branch_until_zero
3783 if (loop_dump_stream)
3784 fprintf (loop_dump_stream,
3785 "Cannot eliminate nonneg biv %d.\n", bl->regno);
3790 /* Check that biv is used outside loop or if it has a final value.
3791 Compare against bl->init_insn rather than loop->start. We aren't
3792 concerned with any uses of the biv between init_insn and
3793 loop->start since these won't be affected by the value of the biv
3794 elsewhere in the function, so long as init_insn doesn't use the
3797 if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
3799 && INSN_UID (bl->init_insn) < max_uid_for_loop
3800 && REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
3801 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3802 || (bl->final_value = final_biv_value (loop, bl)))
3803 return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
3805 if (loop_dump_stream)
3807 fprintf (loop_dump_stream,
3808 "Cannot eliminate biv %d.\n",
3810 fprintf (loop_dump_stream,
3811 "First use: insn %d, last use: insn %d.\n",
3812 REGNO_FIRST_UID (bl->regno),
3813 REGNO_LAST_UID (bl->regno));
3819 /* Reduce each giv of BL that we have decided to reduce. */
3822 loop_givs_reduce (loop, bl)
3824 struct iv_class *bl;
3826 struct induction *v;
3828 for (v = bl->giv; v; v = v->next_iv)
3830 struct induction *tv;
3831 if (! v->ignore && v->same == 0)
3833 int auto_inc_opt = 0;
3835 /* If the code for derived givs immediately below has already
3836 allocated a new_reg, we must keep it. */
3838 v->new_reg = gen_reg_rtx (v->mode);
3841 /* If the target has auto-increment addressing modes, and
3842 this is an address giv, then try to put the increment
3843 immediately after its use, so that flow can create an
3844 auto-increment addressing mode. */
3845 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
3846 && bl->biv->always_executed && ! bl->biv->maybe_multiple
3847 /* We don't handle reversed biv's because bl->biv->insn
3848 does not have a valid INSN_LUID. */
3850 && v->always_executed && ! v->maybe_multiple
3851 && INSN_UID (v->insn) < max_uid_for_loop)
3853 /* If other giv's have been combined with this one, then
3854 this will work only if all uses of the other giv's occur
3855 before this giv's insn. This is difficult to check.
3857 We simplify this by looking for the common case where
3858 there is one DEST_REG giv, and this giv's insn is the
3859 last use of the dest_reg of that DEST_REG giv. If the
3860 increment occurs after the address giv, then we can
3861 perform the optimization. (Otherwise, the increment
3862 would have to go before other_giv, and we would not be
3863 able to combine it with the address giv to get an
3864 auto-inc address.) */
3865 if (v->combined_with)
3867 struct induction *other_giv = 0;
3869 for (tv = bl->giv; tv; tv = tv->next_iv)
3877 if (! tv && other_giv
3878 && REGNO (other_giv->dest_reg) < max_reg_before_loop
3879 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
3880 == INSN_UID (v->insn))
3881 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
3884 /* Check for case where increment is before the address
3885 giv. Do this test in "loop order". */
3886 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
3887 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3888 || (INSN_LUID (bl->biv->insn)
3889 > INSN_LUID (loop->scan_start))))
3890 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
3891 && (INSN_LUID (loop->scan_start)
3892 < INSN_LUID (bl->biv->insn))))
3901 /* We can't put an insn immediately after one setting
3902 cc0, or immediately before one using cc0. */
3903 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
3904 || (auto_inc_opt == -1
3905 && (prev = prev_nonnote_insn (v->insn)) != 0
3907 && sets_cc0_p (PATTERN (prev))))
3913 v->auto_inc_opt = 1;
3917 /* For each place where the biv is incremented, add an insn
3918 to increment the new, reduced reg for the giv. */
3919 for (tv = bl->biv; tv; tv = tv->next_iv)
3924 insert_before = tv->insn;
3925 else if (auto_inc_opt == 1)
3926 insert_before = NEXT_INSN (v->insn);
3928 insert_before = v->insn;
3930 if (tv->mult_val == const1_rtx)
3931 loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val,
3932 v->new_reg, v->new_reg,
3934 else /* tv->mult_val == const0_rtx */
3935 /* A multiply is acceptable here
3936 since this is presumed to be seldom executed. */
3937 loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val,
3938 v->add_val, v->new_reg,
3942 /* Add code at loop start to initialize giv's reduced reg. */
3944 loop_iv_add_mult_hoist (loop,
3945 extend_value_for_giv (v, bl->initial_value),
3946 v->mult_val, v->add_val, v->new_reg);
3952 /* Check for givs whose first use is their definition and whose
3953 last use is the definition of another giv. If so, it is likely
3954 dead and should not be used to derive another giv nor to
3958 loop_givs_dead_check (loop, bl)
3959 struct loop *loop ATTRIBUTE_UNUSED;
3960 struct iv_class *bl;
3962 struct induction *v;
3964 for (v = bl->giv; v; v = v->next_iv)
3967 || (v->same && v->same->ignore))
3970 if (v->giv_type == DEST_REG
3971 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
3973 struct induction *v1;
3975 for (v1 = bl->giv; v1; v1 = v1->next_iv)
3976 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
3984 loop_givs_rescan (loop, bl, reg_map)
3986 struct iv_class *bl;
3989 struct induction *v;
3991 for (v = bl->giv; v; v = v->next_iv)
3993 if (v->same && v->same->ignore)
3999 /* Update expression if this was combined, in case other giv was
4002 v->new_reg = replace_rtx (v->new_reg,
4003 v->same->dest_reg, v->same->new_reg);
4005 /* See if this register is known to be a pointer to something. If
4006 so, see if we can find the alignment. First see if there is a
4007 destination register that is a pointer. If so, this shares the
4008 alignment too. Next see if we can deduce anything from the
4009 computational information. If not, and this is a DEST_ADDR
4010 giv, at least we know that it's a pointer, though we don't know
4012 if (GET_CODE (v->new_reg) == REG
4013 && v->giv_type == DEST_REG
4014 && REG_POINTER (v->dest_reg))
4015 mark_reg_pointer (v->new_reg,
4016 REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
4017 else if (GET_CODE (v->new_reg) == REG
4018 && REG_POINTER (v->src_reg))
4020 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
4023 || GET_CODE (v->add_val) != CONST_INT
4024 || INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
4027 mark_reg_pointer (v->new_reg, align);
4029 else if (GET_CODE (v->new_reg) == REG
4030 && GET_CODE (v->add_val) == REG
4031 && REG_POINTER (v->add_val))
4033 unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
4035 if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
4036 || INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
4039 mark_reg_pointer (v->new_reg, align);
4041 else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
4042 mark_reg_pointer (v->new_reg, 0);
4044 if (v->giv_type == DEST_ADDR)
4045 /* Store reduced reg as the address in the memref where we found
4047 validate_change (v->insn, v->location, v->new_reg, 0);
4048 else if (v->replaceable)
4050 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4054 /* Not replaceable; emit an insn to set the original giv reg from
4055 the reduced giv, same as above. */
4056 loop_insn_emit_after (loop, 0, v->insn,
4057 gen_move_insn (v->dest_reg, v->new_reg));
4060 /* When a loop is reversed, givs which depend on the reversed
4061 biv, and which are live outside the loop, must be set to their
4062 correct final value. This insn is only needed if the giv is
4063 not replaceable. The correct final value is the same as the
4064 value that the giv starts the reversed loop with. */
4065 if (bl->reversed && ! v->replaceable)
4066 loop_iv_add_mult_sink (loop,
4067 extend_value_for_giv (v, bl->initial_value),
4068 v->mult_val, v->add_val, v->dest_reg);
4069 else if (v->final_value)
4070 loop_insn_sink_or_swim (loop,
4071 gen_move_insn (v->dest_reg, v->final_value));
4073 if (loop_dump_stream)
4075 fprintf (loop_dump_stream, "giv at %d reduced to ",
4076 INSN_UID (v->insn));
4077 print_simple_rtl (loop_dump_stream, v->new_reg);
4078 fprintf (loop_dump_stream, "\n");
4085 loop_giv_reduce_benefit (loop, bl, v, test_reg)
4086 struct loop *loop ATTRIBUTE_UNUSED;
4087 struct iv_class *bl;
4088 struct induction *v;
4094 benefit = v->benefit;
4095 PUT_MODE (test_reg, v->mode);
4096 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
4097 test_reg, test_reg);
4099 /* Reduce benefit if not replaceable, since we will insert a
4100 move-insn to replace the insn that calculates this giv. Don't do
4101 this unless the giv is a user variable, since it will often be
4102 marked non-replaceable because of the duplication of the exit
4103 code outside the loop. In such a case, the copies we insert are
4104 dead and will be deleted. So they don't have a cost. Similar
4105 situations exist. */
4106 /* ??? The new final_[bg]iv_value code does a much better job of
4107 finding replaceable giv's, and hence this code may no longer be
4109 if (! v->replaceable && ! bl->eliminable
4110 && REG_USERVAR_P (v->dest_reg))
4111 benefit -= copy_cost;
4113 /* Decrease the benefit to count the add-insns that we will insert
4114 to increment the reduced reg for the giv. ??? This can
4115 overestimate the run-time cost of the additional insns, e.g. if
4116 there are multiple basic blocks that increment the biv, but only
4117 one of these blocks is executed during each iteration. There is
4118 no good way to detect cases like this with the current structure
4119 of the loop optimizer. This code is more accurate for
4120 determining code size than run-time benefits. */
4121 benefit -= add_cost * bl->biv_count;
4123 /* Decide whether to strength-reduce this giv or to leave the code
4124 unchanged (recompute it from the biv each time it is used). This
4125 decision can be made independently for each giv. */
4128 /* Attempt to guess whether autoincrement will handle some of the
4129 new add insns; if so, increase BENEFIT (undo the subtraction of
4130 add_cost that was done above). */
4131 if (v->giv_type == DEST_ADDR
4132 /* Increasing the benefit is risky, since this is only a guess.
4133 Avoid increasing register pressure in cases where there would
4134 be no other benefit from reducing this giv. */
4136 && GET_CODE (v->mult_val) == CONST_INT)
4138 if (HAVE_POST_INCREMENT
4139 && INTVAL (v->mult_val) == GET_MODE_SIZE (GET_MODE (v->mem)))
4140 benefit += add_cost * bl->biv_count;
4141 else if (HAVE_PRE_INCREMENT
4142 && INTVAL (v->mult_val) == GET_MODE_SIZE (GET_MODE (v->mem)))
4143 benefit += add_cost * bl->biv_count;
4144 else if (HAVE_POST_DECREMENT
4145 && -INTVAL (v->mult_val) == GET_MODE_SIZE (GET_MODE (v->mem)))
4146 benefit += add_cost * bl->biv_count;
4147 else if (HAVE_PRE_DECREMENT
4148 && -INTVAL (v->mult_val) == GET_MODE_SIZE (GET_MODE (v->mem)))
4149 benefit += add_cost * bl->biv_count;
4157 /* Free IV structures for LOOP. */
4160 loop_ivs_free (loop)
4163 struct loop_ivs *ivs = LOOP_IVS (loop);
4164 struct iv_class *iv = ivs->list;
4170 struct iv_class *next = iv->next;
4171 struct induction *induction;
4172 struct induction *next_induction;
4174 for (induction = iv->biv; induction; induction = next_induction)
4176 next_induction = induction->next_iv;
4179 for (induction = iv->giv; induction; induction = next_induction)
4181 next_induction = induction->next_iv;
4191 /* Perform strength reduction and induction variable elimination.
4193 Pseudo registers created during this function will be beyond the
4194 last valid index in several tables including
4195 REGS->ARRAY[I].N_TIMES_SET and REGNO_LAST_UID. This does not cause a
4196 problem here, because the added registers cannot be givs outside of
4197 their loop, and hence will never be reconsidered. But scan_loop
4198 must check regnos to make sure they are in bounds. */
4201 strength_reduce (loop, insn_count, flags)
4206 struct loop_info *loop_info = LOOP_INFO (loop);
4207 struct loop_regs *regs = LOOP_REGS (loop);
4208 struct loop_ivs *ivs = LOOP_IVS (loop);
4210 /* Temporary list pointer for traversing ivs->list. */
4211 struct iv_class *bl;
4212 /* Ratio of extra register life span we can justify
4213 for saving an instruction. More if loop doesn't call subroutines
4214 since in that case saving an insn makes more difference
4215 and more registers are available. */
4216 /* ??? could set this to last value of threshold in move_movables */
4217 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
4218 /* Map of pseudo-register replacements. */
4219 rtx *reg_map = NULL;
4221 int unrolled_insn_copies = 0;
4222 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
4224 addr_placeholder = gen_reg_rtx (Pmode);
4226 ivs->n_regs = max_reg_before_loop;
4227 ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
4229 /* Find all BIVs in loop. */
4230 loop_bivs_find (loop);
4232 /* Exit if there are no bivs. */
4235 /* Can still unroll the loop anyways, but indicate that there is no
4236 strength reduction info available. */
4237 if (flags & LOOP_UNROLL)
4238 unroll_loop (loop, insn_count, 0);
4240 loop_ivs_free (loop);
4244 /* Determine how BIVS are initialised by looking through pre-header
4245 extended basic block. */
4246 loop_bivs_init_find (loop);
4248 /* Look at the each biv and see if we can say anything better about its
4249 initial value from any initializing insns set up above. */
4250 loop_bivs_check (loop);
4252 /* Search the loop for general induction variables. */
4253 loop_givs_find (loop);
4255 /* Try to calculate and save the number of loop iterations. This is
4256 set to zero if the actual number can not be calculated. This must
4257 be called after all giv's have been identified, since otherwise it may
4258 fail if the iteration variable is a giv. */
4259 loop_iterations (loop);
4261 /* Now for each giv for which we still don't know whether or not it is
4262 replaceable, check to see if it is replaceable because its final value
4263 can be calculated. This must be done after loop_iterations is called,
4264 so that final_giv_value will work correctly. */
4265 loop_givs_check (loop);
4267 /* Try to prove that the loop counter variable (if any) is always
4268 nonnegative; if so, record that fact with a REG_NONNEG note
4269 so that "decrement and branch until zero" insn can be used. */
4270 check_dbra_loop (loop, insn_count);
4272 /* Create reg_map to hold substitutions for replaceable giv regs.
4273 Some givs might have been made from biv increments, so look at
4274 ivs->reg_iv_type for a suitable size. */
4275 reg_map_size = ivs->n_regs;
4276 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
4278 /* Examine each iv class for feasibility of strength reduction/induction
4279 variable elimination. */
4281 for (bl = ivs->list; bl; bl = bl->next)
4283 struct induction *v;
4286 /* Test whether it will be possible to eliminate this biv
4287 provided all givs are reduced. */
4288 bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
4290 /* Check each extension dependent giv in this class to see if its
4291 root biv is safe from wrapping in the interior mode. */
4292 check_ext_dependant_givs (bl, loop_info);
4294 /* Combine all giv's for this iv_class. */
4295 combine_givs (regs, bl);
4297 /* This will be true at the end, if all givs which depend on this
4298 biv have been strength reduced.
4299 We can't (currently) eliminate the biv unless this is so. */
4300 bl->all_reduced = 1;
4302 for (v = bl->giv; v; v = v->next_iv)
4304 struct induction *tv;
4306 if (v->ignore || v->same)
4309 benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
4311 /* If an insn is not to be strength reduced, then set its ignore
4312 flag, and clear bl->all_reduced. */
4314 /* A giv that depends on a reversed biv must be reduced if it is
4315 used after the loop exit, otherwise, it would have the wrong
4316 value after the loop exit. To make it simple, just reduce all
4317 of such giv's whether or not we know they are used after the loop
4320 if (! flag_reduce_all_givs
4321 && v->lifetime * threshold * benefit < insn_count
4324 if (loop_dump_stream)
4325 fprintf (loop_dump_stream,
4326 "giv of insn %d not worth while, %d vs %d.\n",
4328 v->lifetime * threshold * benefit, insn_count);
4330 bl->all_reduced = 0;
4334 /* Check that we can increment the reduced giv without a
4335 multiply insn. If not, reject it. */
4337 for (tv = bl->biv; tv; tv = tv->next_iv)
4338 if (tv->mult_val == const1_rtx
4339 && ! product_cheap_p (tv->add_val, v->mult_val))
4341 if (loop_dump_stream)
4342 fprintf (loop_dump_stream,
4343 "giv of insn %d: would need a multiply.\n",
4344 INSN_UID (v->insn));
4346 bl->all_reduced = 0;
4352 /* Check for givs whose first use is their definition and whose
4353 last use is the definition of another giv. If so, it is likely
4354 dead and should not be used to derive another giv nor to
4356 loop_givs_dead_check (loop, bl);
4358 /* Reduce each giv that we decided to reduce. */
4359 loop_givs_reduce (loop, bl);
4361 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4364 For each giv register that can be reduced now: if replaceable,
4365 substitute reduced reg wherever the old giv occurs;
4366 else add new move insn "giv_reg = reduced_reg". */
4367 loop_givs_rescan (loop, bl, reg_map);
4369 /* All the givs based on the biv bl have been reduced if they
4372 /* For each giv not marked as maybe dead that has been combined with a
4373 second giv, clear any "maybe dead" mark on that second giv.
4374 v->new_reg will either be or refer to the register of the giv it
4377 Doing this clearing avoids problems in biv elimination where
4378 a giv's new_reg is a complex value that can't be put in the
4379 insn but the giv combined with (with a reg as new_reg) is
4380 marked maybe_dead. Since the register will be used in either
4381 case, we'd prefer it be used from the simpler giv. */
4383 for (v = bl->giv; v; v = v->next_iv)
4384 if (! v->maybe_dead && v->same)
4385 v->same->maybe_dead = 0;
4387 /* Try to eliminate the biv, if it is a candidate.
4388 This won't work if ! bl->all_reduced,
4389 since the givs we planned to use might not have been reduced.
4391 We have to be careful that we didn't initially think we could
4392 eliminate this biv because of a giv that we now think may be
4393 dead and shouldn't be used as a biv replacement.
4395 Also, there is the possibility that we may have a giv that looks
4396 like it can be used to eliminate a biv, but the resulting insn
4397 isn't valid. This can happen, for example, on the 88k, where a
4398 JUMP_INSN can compare a register only with zero. Attempts to
4399 replace it with a compare with a constant will fail.
4401 Note that in cases where this call fails, we may have replaced some
4402 of the occurrences of the biv with a giv, but no harm was done in
4403 doing so in the rare cases where it can occur. */
4405 if (bl->all_reduced == 1 && bl->eliminable
4406 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4408 /* ?? If we created a new test to bypass the loop entirely,
4409 or otherwise drop straight in, based on this test, then
4410 we might want to rewrite it also. This way some later
4411 pass has more hope of removing the initialization of this
4414 /* If final_value != 0, then the biv may be used after loop end
4415 and we must emit an insn to set it just in case.
4417 Reversed bivs already have an insn after the loop setting their
4418 value, so we don't need another one. We can't calculate the
4419 proper final value for such a biv here anyways. */
4420 if (bl->final_value && ! bl->reversed)
4421 loop_insn_sink_or_swim (loop, gen_move_insn
4422 (bl->biv->dest_reg, bl->final_value));
4424 if (loop_dump_stream)
4425 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4430 /* Go through all the instructions in the loop, making all the
4431 register substitutions scheduled in REG_MAP. */
4433 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
4434 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4435 || GET_CODE (p) == CALL_INSN)
4437 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4438 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4442 if (loop_info->n_iterations > 0)
4444 /* When we completely unroll a loop we will likely not need the increment
4445 of the loop BIV and we will not need the conditional branch at the
4447 unrolled_insn_copies = insn_count - 2;
4450 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4451 need the comparison before the conditional branch at the end of the
4453 unrolled_insn_copies -= 1;
4456 /* We'll need one copy for each loop iteration. */
4457 unrolled_insn_copies *= loop_info->n_iterations;
4459 /* A little slop to account for the ability to remove initialization
4460 code, better CSE, and other secondary benefits of completely
4461 unrolling some loops. */
4462 unrolled_insn_copies -= 1;
4464 /* Clamp the value. */
4465 if (unrolled_insn_copies < 0)
4466 unrolled_insn_copies = 0;
4469 /* Unroll loops from within strength reduction so that we can use the
4470 induction variable information that strength_reduce has already
4471 collected. Always unroll loops that would be as small or smaller
4472 unrolled than when rolled. */
4473 if ((flags & LOOP_UNROLL)
4474 || (loop_info->n_iterations > 0
4475 && unrolled_insn_copies <= insn_count))
4476 unroll_loop (loop, insn_count, 1);
4478 #ifdef HAVE_doloop_end
4479 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4480 doloop_optimize (loop);
4481 #endif /* HAVE_doloop_end */
4483 if (loop_dump_stream)
4484 fprintf (loop_dump_stream, "\n");
4486 loop_ivs_free (loop);
4491 /*Record all basic induction variables calculated in the insn. */
4493 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4496 int not_every_iteration;
4499 struct loop_ivs *ivs = LOOP_IVS (loop);
4506 if (GET_CODE (p) == INSN
4507 && (set = single_set (p))
4508 && GET_CODE (SET_DEST (set)) == REG)
4510 dest_reg = SET_DEST (set);
4511 if (REGNO (dest_reg) < max_reg_before_loop
4512 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4513 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4515 if (basic_induction_var (loop, SET_SRC (set),
4516 GET_MODE (SET_SRC (set)),
4517 dest_reg, p, &inc_val, &mult_val,
4520 /* It is a possible basic induction variable.
4521 Create and initialize an induction structure for it. */
4524 = (struct induction *) xmalloc (sizeof (struct induction));
4526 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4527 not_every_iteration, maybe_multiple);
4528 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4530 else if (REGNO (dest_reg) < ivs->n_regs)
4531 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4537 /* Record all givs calculated in the insn.
4538 A register is a giv if: it is only set once, it is a function of a
4539 biv and a constant (or invariant), and it is not a biv. */
4541 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4544 int not_every_iteration;
4547 struct loop_regs *regs = LOOP_REGS (loop);
4550 /* Look for a general induction variable in a register. */
4551 if (GET_CODE (p) == INSN
4552 && (set = single_set (p))
4553 && GET_CODE (SET_DEST (set)) == REG
4554 && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
4563 rtx last_consec_insn;
4565 dest_reg = SET_DEST (set);
4566 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4569 if (/* SET_SRC is a giv. */
4570 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4571 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4572 /* Equivalent expression is a giv. */
4573 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4574 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4575 &add_val, &mult_val, &ext_val, 0,
4576 &benefit, VOIDmode)))
4577 /* Don't try to handle any regs made by loop optimization.
4578 We have nothing on them in regno_first_uid, etc. */
4579 && REGNO (dest_reg) < max_reg_before_loop
4580 /* Don't recognize a BASIC_INDUCT_VAR here. */
4581 && dest_reg != src_reg
4582 /* This must be the only place where the register is set. */
4583 && (regs->array[REGNO (dest_reg)].n_times_set == 1
4584 /* or all sets must be consecutive and make a giv. */
4585 || (benefit = consec_sets_giv (loop, benefit, p,
4587 &add_val, &mult_val, &ext_val,
4588 &last_consec_insn))))
4591 = (struct induction *) xmalloc (sizeof (struct induction));
4593 /* If this is a library call, increase benefit. */
4594 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4595 benefit += libcall_benefit (p);
4597 /* Skip the consecutive insns, if there are any. */
4598 if (regs->array[REGNO (dest_reg)].n_times_set != 1)
4599 p = last_consec_insn;
4601 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4602 ext_val, benefit, DEST_REG, not_every_iteration,
4603 maybe_multiple, NULL_PTR);
4608 #ifndef DONT_REDUCE_ADDR
4609 /* Look for givs which are memory addresses. */
4610 /* This resulted in worse code on a VAX 8600. I wonder if it
4612 if (GET_CODE (p) == INSN)
4613 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4617 /* Update the status of whether giv can derive other givs. This can
4618 change when we pass a label or an insn that updates a biv. */
4619 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4620 || GET_CODE (p) == CODE_LABEL)
4621 update_giv_derive (loop, p);
4625 /* Return 1 if X is a valid source for an initial value (or as value being
4626 compared against in an initial test).
4628 X must be either a register or constant and must not be clobbered between
4629 the current insn and the start of the loop.
4631 INSN is the insn containing X. */
4634 valid_initial_value_p (x, insn, call_seen, loop_start)
4643 /* Only consider pseudos we know about initialized in insns whose luids
4645 if (GET_CODE (x) != REG
4646 || REGNO (x) >= max_reg_before_loop)
4649 /* Don't use call-clobbered registers across a call which clobbers it. On
4650 some machines, don't use any hard registers at all. */
4651 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4652 && (SMALL_REGISTER_CLASSES
4653 || (call_used_regs[REGNO (x)] && call_seen)))
4656 /* Don't use registers that have been clobbered before the start of the
4658 if (reg_set_between_p (x, insn, loop_start))
4664 /* Scan X for memory refs and check each memory address
4665 as a possible giv. INSN is the insn whose pattern X comes from.
4666 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4667 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4668 more thanonce in each loop iteration. */
4671 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4672 const struct loop *loop;
4675 int not_every_iteration, maybe_multiple;
4678 register enum rtx_code code;
4679 register const char *fmt;
4684 code = GET_CODE (x);
4709 /* This code used to disable creating GIVs with mult_val == 1 and
4710 add_val == 0. However, this leads to lost optimizations when
4711 it comes time to combine a set of related DEST_ADDR GIVs, since
4712 this one would not be seen. */
4714 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4715 &mult_val, &ext_val, 1, &benefit,
4718 /* Found one; record it. */
4720 = (struct induction *) xmalloc (sizeof (struct induction));
4722 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4723 add_val, ext_val, benefit, DEST_ADDR,
4724 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4735 /* Recursively scan the subexpressions for other mem refs. */
4737 fmt = GET_RTX_FORMAT (code);
4738 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4740 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4742 else if (fmt[i] == 'E')
4743 for (j = 0; j < XVECLEN (x, i); j++)
4744 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4748 /* Fill in the data about one biv update.
4749 V is the `struct induction' in which we record the biv. (It is
4750 allocated by the caller, with alloca.)
4751 INSN is the insn that sets it.
4752 DEST_REG is the biv's reg.
4754 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4755 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4756 being set to INC_VAL.
4758 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4759 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4760 can be executed more than once per iteration. If MAYBE_MULTIPLE
4761 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4762 executed exactly once per iteration. */
4765 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4766 not_every_iteration, maybe_multiple)
4768 struct induction *v;
4774 int not_every_iteration;
4777 struct loop_ivs *ivs = LOOP_IVS (loop);
4778 struct iv_class *bl;
4781 v->src_reg = dest_reg;
4782 v->dest_reg = dest_reg;
4783 v->mult_val = mult_val;
4784 v->add_val = inc_val;
4785 v->ext_dependant = NULL_RTX;
4786 v->location = location;
4787 v->mode = GET_MODE (dest_reg);
4788 v->always_computable = ! not_every_iteration;
4789 v->always_executed = ! not_every_iteration;
4790 v->maybe_multiple = maybe_multiple;
4792 /* Add this to the reg's iv_class, creating a class
4793 if this is the first incrementation of the reg. */
4795 bl = REG_IV_CLASS (ivs, REGNO (dest_reg));
4798 /* Create and initialize new iv_class. */
4800 bl = (struct iv_class *) xmalloc (sizeof (struct iv_class));
4802 bl->regno = REGNO (dest_reg);
4808 /* Set initial value to the reg itself. */
4809 bl->initial_value = dest_reg;
4810 bl->final_value = 0;
4811 /* We haven't seen the initializing insn yet */
4814 bl->initial_test = 0;
4815 bl->incremented = 0;
4819 bl->total_benefit = 0;
4821 /* Add this class to ivs->list. */
4822 bl->next = ivs->list;
4825 /* Put it in the array of biv register classes. */
4826 REG_IV_CLASS (ivs, REGNO (dest_reg)) = bl;
4829 /* Update IV_CLASS entry for this biv. */
4830 v->next_iv = bl->biv;
4833 if (mult_val == const1_rtx)
4834 bl->incremented = 1;
4836 if (loop_dump_stream)
4837 loop_biv_dump (v, loop_dump_stream, 0);
4840 /* Fill in the data about one giv.
4841 V is the `struct induction' in which we record the giv. (It is
4842 allocated by the caller, with alloca.)
4843 INSN is the insn that sets it.
4844 BENEFIT estimates the savings from deleting this insn.
4845 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4846 into a register or is used as a memory address.
4848 SRC_REG is the biv reg which the giv is computed from.
4849 DEST_REG is the giv's reg (if the giv is stored in a reg).
4850 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4851 LOCATION points to the place where this giv's value appears in INSN. */
4854 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4855 benefit, type, not_every_iteration, maybe_multiple, location)
4856 const struct loop *loop;
4857 struct induction *v;
4861 rtx mult_val, add_val, ext_val;
4864 int not_every_iteration, maybe_multiple;
4867 struct loop_ivs *ivs = LOOP_IVS (loop);
4868 struct induction *b;
4869 struct iv_class *bl;
4870 rtx set = single_set (insn);
4873 /* Attempt to prove constantness of the values. */
4874 temp = simplify_rtx (add_val);
4879 v->src_reg = src_reg;
4881 v->dest_reg = dest_reg;
4882 v->mult_val = mult_val;
4883 v->add_val = add_val;
4884 v->ext_dependant = ext_val;
4885 v->benefit = benefit;
4886 v->location = location;
4888 v->combined_with = 0;
4889 v->maybe_multiple = maybe_multiple;
4891 v->derive_adjustment = 0;
4897 v->auto_inc_opt = 0;
4901 /* The v->always_computable field is used in update_giv_derive, to
4902 determine whether a giv can be used to derive another giv. For a
4903 DEST_REG giv, INSN computes a new value for the giv, so its value
4904 isn't computable if INSN insn't executed every iteration.
4905 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4906 it does not compute a new value. Hence the value is always computable
4907 regardless of whether INSN is executed each iteration. */
4909 if (type == DEST_ADDR)
4910 v->always_computable = 1;
4912 v->always_computable = ! not_every_iteration;
4914 v->always_executed = ! not_every_iteration;
4916 if (type == DEST_ADDR)
4918 v->mode = GET_MODE (*location);
4921 else /* type == DEST_REG */
4923 v->mode = GET_MODE (SET_DEST (set));
4925 v->lifetime = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
4927 /* If the lifetime is zero, it means that this register is
4928 really a dead store. So mark this as a giv that can be
4929 ignored. This will not prevent the biv from being eliminated. */
4930 if (v->lifetime == 0)
4933 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
4934 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
4937 /* Add the giv to the class of givs computed from one biv. */
4939 bl = REG_IV_CLASS (ivs, REGNO (src_reg));
4942 v->next_iv = bl->giv;
4944 /* Don't count DEST_ADDR. This is supposed to count the number of
4945 insns that calculate givs. */
4946 if (type == DEST_REG)
4948 bl->total_benefit += benefit;
4951 /* Fatal error, biv missing for this giv? */
4954 if (type == DEST_ADDR)
4958 /* The giv can be replaced outright by the reduced register only if all
4959 of the following conditions are true:
4960 - the insn that sets the giv is always executed on any iteration
4961 on which the giv is used at all
4962 (there are two ways to deduce this:
4963 either the insn is executed on every iteration,
4964 or all uses follow that insn in the same basic block),
4965 - the giv is not used outside the loop
4966 - no assignments to the biv occur during the giv's lifetime. */
4968 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
4969 /* Previous line always fails if INSN was moved by loop opt. */
4970 && REGNO_LAST_LUID (REGNO (dest_reg))
4971 < INSN_LUID (loop->end)
4972 && (! not_every_iteration
4973 || last_use_this_basic_block (dest_reg, insn)))
4975 /* Now check that there are no assignments to the biv within the
4976 giv's lifetime. This requires two separate checks. */
4978 /* Check each biv update, and fail if any are between the first
4979 and last use of the giv.
4981 If this loop contains an inner loop that was unrolled, then
4982 the insn modifying the biv may have been emitted by the loop
4983 unrolling code, and hence does not have a valid luid. Just
4984 mark the biv as not replaceable in this case. It is not very
4985 useful as a biv, because it is used in two different loops.
4986 It is very unlikely that we would be able to optimize the giv
4987 using this biv anyways. */
4990 for (b = bl->biv; b; b = b->next_iv)
4992 if (INSN_UID (b->insn) >= max_uid_for_loop
4993 || ((INSN_LUID (b->insn)
4994 >= REGNO_FIRST_LUID (REGNO (dest_reg)))
4995 && (INSN_LUID (b->insn)
4996 <= REGNO_LAST_LUID (REGNO (dest_reg)))))
4999 v->not_replaceable = 1;
5004 /* If there are any backwards branches that go from after the
5005 biv update to before it, then this giv is not replaceable. */
5007 for (b = bl->biv; b; b = b->next_iv)
5008 if (back_branch_in_range_p (loop, b->insn))
5011 v->not_replaceable = 1;
5017 /* May still be replaceable, we don't have enough info here to
5020 v->not_replaceable = 0;
5024 /* Record whether the add_val contains a const_int, for later use by
5029 v->no_const_addval = 1;
5030 if (tem == const0_rtx)
5032 else if (CONSTANT_P (add_val))
5033 v->no_const_addval = 0;
5034 if (GET_CODE (tem) == PLUS)
5038 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5039 tem = XEXP (tem, 0);
5040 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5041 tem = XEXP (tem, 1);
5045 if (CONSTANT_P (XEXP (tem, 1)))
5046 v->no_const_addval = 0;
5050 if (loop_dump_stream)
5051 loop_giv_dump (v, loop_dump_stream, 0);
5054 /* All this does is determine whether a giv can be made replaceable because
5055 its final value can be calculated. This code can not be part of record_giv
5056 above, because final_giv_value requires that the number of loop iterations
5057 be known, and that can not be accurately calculated until after all givs
5058 have been identified. */
5061 check_final_value (loop, v)
5062 const struct loop *loop;
5063 struct induction *v;
5065 struct loop_ivs *ivs = LOOP_IVS (loop);
5066 struct iv_class *bl;
5067 rtx final_value = 0;
5069 bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
5071 /* DEST_ADDR givs will never reach here, because they are always marked
5072 replaceable above in record_giv. */
5074 /* The giv can be replaced outright by the reduced register only if all
5075 of the following conditions are true:
5076 - the insn that sets the giv is always executed on any iteration
5077 on which the giv is used at all
5078 (there are two ways to deduce this:
5079 either the insn is executed on every iteration,
5080 or all uses follow that insn in the same basic block),
5081 - its final value can be calculated (this condition is different
5082 than the one above in record_giv)
5083 - it's not used before the it's set
5084 - no assignments to the biv occur during the giv's lifetime. */
5087 /* This is only called now when replaceable is known to be false. */
5088 /* Clear replaceable, so that it won't confuse final_giv_value. */
5092 if ((final_value = final_giv_value (loop, v))
5093 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5095 int biv_increment_seen = 0, before_giv_insn = 0;
5101 /* When trying to determine whether or not a biv increment occurs
5102 during the lifetime of the giv, we can ignore uses of the variable
5103 outside the loop because final_value is true. Hence we can not
5104 use regno_last_uid and regno_first_uid as above in record_giv. */
5106 /* Search the loop to determine whether any assignments to the
5107 biv occur during the giv's lifetime. Start with the insn
5108 that sets the giv, and search around the loop until we come
5109 back to that insn again.
5111 Also fail if there is a jump within the giv's lifetime that jumps
5112 to somewhere outside the lifetime but still within the loop. This
5113 catches spaghetti code where the execution order is not linear, and
5114 hence the above test fails. Here we assume that the giv lifetime
5115 does not extend from one iteration of the loop to the next, so as
5116 to make the test easier. Since the lifetime isn't known yet,
5117 this requires two loops. See also record_giv above. */
5119 last_giv_use = v->insn;
5126 before_giv_insn = 1;
5127 p = NEXT_INSN (loop->start);
5132 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5133 || GET_CODE (p) == CALL_INSN)
5135 /* It is possible for the BIV increment to use the GIV if we
5136 have a cycle. Thus we must be sure to check each insn for
5137 both BIV and GIV uses, and we must check for BIV uses
5140 if (! biv_increment_seen
5141 && reg_set_p (v->src_reg, PATTERN (p)))
5142 biv_increment_seen = 1;
5144 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5146 if (biv_increment_seen || before_giv_insn)
5149 v->not_replaceable = 1;
5157 /* Now that the lifetime of the giv is known, check for branches
5158 from within the lifetime to outside the lifetime if it is still
5168 p = NEXT_INSN (loop->start);
5169 if (p == last_giv_use)
5172 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5173 && LABEL_NAME (JUMP_LABEL (p))
5174 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5175 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5176 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5177 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5180 v->not_replaceable = 1;
5182 if (loop_dump_stream)
5183 fprintf (loop_dump_stream,
5184 "Found branch outside giv lifetime.\n");
5191 /* If it is replaceable, then save the final value. */
5193 v->final_value = final_value;
5196 if (loop_dump_stream && v->replaceable)
5197 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5198 INSN_UID (v->insn), REGNO (v->dest_reg));
5201 /* Update the status of whether a giv can derive other givs.
5203 We need to do something special if there is or may be an update to the biv
5204 between the time the giv is defined and the time it is used to derive
5207 In addition, a giv that is only conditionally set is not allowed to
5208 derive another giv once a label has been passed.
5210 The cases we look at are when a label or an update to a biv is passed. */
5213 update_giv_derive (loop, p)
5214 const struct loop *loop;
5217 struct loop_ivs *ivs = LOOP_IVS (loop);
5218 struct iv_class *bl;
5219 struct induction *biv, *giv;
5223 /* Search all IV classes, then all bivs, and finally all givs.
5225 There are three cases we are concerned with. First we have the situation
5226 of a giv that is only updated conditionally. In that case, it may not
5227 derive any givs after a label is passed.
5229 The second case is when a biv update occurs, or may occur, after the
5230 definition of a giv. For certain biv updates (see below) that are
5231 known to occur between the giv definition and use, we can adjust the
5232 giv definition. For others, or when the biv update is conditional,
5233 we must prevent the giv from deriving any other givs. There are two
5234 sub-cases within this case.
5236 If this is a label, we are concerned with any biv update that is done
5237 conditionally, since it may be done after the giv is defined followed by
5238 a branch here (actually, we need to pass both a jump and a label, but
5239 this extra tracking doesn't seem worth it).
5241 If this is a jump, we are concerned about any biv update that may be
5242 executed multiple times. We are actually only concerned about
5243 backward jumps, but it is probably not worth performing the test
5244 on the jump again here.
5246 If this is a biv update, we must adjust the giv status to show that a
5247 subsequent biv update was performed. If this adjustment cannot be done,
5248 the giv cannot derive further givs. */
5250 for (bl = ivs->list; bl; bl = bl->next)
5251 for (biv = bl->biv; biv; biv = biv->next_iv)
5252 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5255 for (giv = bl->giv; giv; giv = giv->next_iv)
5257 /* If cant_derive is already true, there is no point in
5258 checking all of these conditions again. */
5259 if (giv->cant_derive)
5262 /* If this giv is conditionally set and we have passed a label,
5263 it cannot derive anything. */
5264 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5265 giv->cant_derive = 1;
5267 /* Skip givs that have mult_val == 0, since
5268 they are really invariants. Also skip those that are
5269 replaceable, since we know their lifetime doesn't contain
5271 else if (giv->mult_val == const0_rtx || giv->replaceable)
5274 /* The only way we can allow this giv to derive another
5275 is if this is a biv increment and we can form the product
5276 of biv->add_val and giv->mult_val. In this case, we will
5277 be able to compute a compensation. */
5278 else if (biv->insn == p)
5283 if (biv->mult_val == const1_rtx)
5284 tem = simplify_giv_expr (loop,
5285 gen_rtx_MULT (giv->mode,
5288 &ext_val_dummy, &dummy);
5290 if (tem && giv->derive_adjustment)
5291 tem = simplify_giv_expr
5293 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5294 &ext_val_dummy, &dummy);
5297 giv->derive_adjustment = tem;
5299 giv->cant_derive = 1;
5301 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5302 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5303 giv->cant_derive = 1;
5308 /* Check whether an insn is an increment legitimate for a basic induction var.
5309 X is the source of insn P, or a part of it.
5310 MODE is the mode in which X should be interpreted.
5312 DEST_REG is the putative biv, also the destination of the insn.
5313 We accept patterns of these forms:
5314 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5315 REG = INVARIANT + REG
5317 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5318 store the additive term into *INC_VAL, and store the place where
5319 we found the additive term into *LOCATION.
5321 If X is an assignment of an invariant into DEST_REG, we set
5322 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5324 We also want to detect a BIV when it corresponds to a variable
5325 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5326 of the variable may be a PLUS that adds a SUBREG of that variable to
5327 an invariant and then sign- or zero-extends the result of the PLUS
5330 Most GIVs in such cases will be in the promoted mode, since that is the
5331 probably the natural computation mode (and almost certainly the mode
5332 used for addresses) on the machine. So we view the pseudo-reg containing
5333 the variable as the BIV, as if it were simply incremented.
5335 Note that treating the entire pseudo as a BIV will result in making
5336 simple increments to any GIVs based on it. However, if the variable
5337 overflows in its declared mode but not its promoted mode, the result will
5338 be incorrect. This is acceptable if the variable is signed, since
5339 overflows in such cases are undefined, but not if it is unsigned, since
5340 those overflows are defined. So we only check for SIGN_EXTEND and
5343 If we cannot find a biv, we return 0. */
5346 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5347 const struct loop *loop;
5349 enum machine_mode mode;
5356 register enum rtx_code code;
5360 code = GET_CODE (x);
5365 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5366 || (GET_CODE (XEXP (x, 0)) == SUBREG
5367 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5368 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5370 argp = &XEXP (x, 1);
5372 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5373 || (GET_CODE (XEXP (x, 1)) == SUBREG
5374 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5375 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5377 argp = &XEXP (x, 0);
5383 if (loop_invariant_p (loop, arg) != 1)
5386 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5387 *mult_val = const1_rtx;
5392 /* If this is a SUBREG for a promoted variable, check the inner
5394 if (SUBREG_PROMOTED_VAR_P (x))
5395 return basic_induction_var (loop, SUBREG_REG (x),
5396 GET_MODE (SUBREG_REG (x)),
5397 dest_reg, p, inc_val, mult_val, location);
5401 /* If this register is assigned in a previous insn, look at its
5402 source, but don't go outside the loop or past a label. */
5404 /* If this sets a register to itself, we would repeat any previous
5405 biv increment if we applied this strategy blindly. */
5406 if (rtx_equal_p (dest_reg, x))
5415 insn = PREV_INSN (insn);
5417 while (insn && GET_CODE (insn) == NOTE
5418 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5422 set = single_set (insn);
5425 dest = SET_DEST (set);
5427 || (GET_CODE (dest) == SUBREG
5428 && (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
5429 && (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
5430 && SUBREG_REG (dest) == x))
5431 return basic_induction_var (loop, SET_SRC (set),
5432 (GET_MODE (SET_SRC (set)) == VOIDmode
5434 : GET_MODE (SET_SRC (set))),
5436 inc_val, mult_val, location);
5438 while (GET_CODE (dest) == SIGN_EXTRACT
5439 || GET_CODE (dest) == ZERO_EXTRACT
5440 || GET_CODE (dest) == SUBREG
5441 || GET_CODE (dest) == STRICT_LOW_PART)
5442 dest = XEXP (dest, 0);
5448 /* Can accept constant setting of biv only when inside inner most loop.
5449 Otherwise, a biv of an inner loop may be incorrectly recognized
5450 as a biv of the outer loop,
5451 causing code to be moved INTO the inner loop. */
5453 if (loop_invariant_p (loop, x) != 1)
5458 /* convert_modes aborts if we try to convert to or from CCmode, so just
5459 exclude that case. It is very unlikely that a condition code value
5460 would be a useful iterator anyways. */
5461 if (loop->level == 1
5462 && GET_MODE_CLASS (mode) != MODE_CC
5463 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5465 /* Possible bug here? Perhaps we don't know the mode of X. */
5466 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5467 *mult_val = const0_rtx;
5474 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5475 dest_reg, p, inc_val, mult_val, location);
5478 /* Similar, since this can be a sign extension. */
5479 for (insn = PREV_INSN (p);
5480 (insn && GET_CODE (insn) == NOTE
5481 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5482 insn = PREV_INSN (insn))
5486 set = single_set (insn);
5488 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5489 && set && SET_DEST (set) == XEXP (x, 0)
5490 && GET_CODE (XEXP (x, 1)) == CONST_INT
5491 && INTVAL (XEXP (x, 1)) >= 0
5492 && GET_CODE (SET_SRC (set)) == ASHIFT
5493 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5494 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5495 GET_MODE (XEXP (x, 0)),
5496 dest_reg, insn, inc_val, mult_val,
5505 /* A general induction variable (giv) is any quantity that is a linear
5506 function of a basic induction variable,
5507 i.e. giv = biv * mult_val + add_val.
5508 The coefficients can be any loop invariant quantity.
5509 A giv need not be computed directly from the biv;
5510 it can be computed by way of other givs. */
5512 /* Determine whether X computes a giv.
5513 If it does, return a nonzero value
5514 which is the benefit from eliminating the computation of X;
5515 set *SRC_REG to the register of the biv that it is computed from;
5516 set *ADD_VAL and *MULT_VAL to the coefficients,
5517 such that the value of X is biv * mult + add; */
5520 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5521 is_addr, pbenefit, addr_mode)
5522 const struct loop *loop;
5530 enum machine_mode addr_mode;
5532 struct loop_ivs *ivs = LOOP_IVS (loop);
5535 /* If this is an invariant, forget it, it isn't a giv. */
5536 if (loop_invariant_p (loop, x) == 1)
5540 *ext_val = NULL_RTX;
5541 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5545 switch (GET_CODE (x))
5549 /* Since this is now an invariant and wasn't before, it must be a giv
5550 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5552 *src_reg = ivs->list->biv->dest_reg;
5553 *mult_val = const0_rtx;
5558 /* This is equivalent to a BIV. */
5560 *mult_val = const1_rtx;
5561 *add_val = const0_rtx;
5565 /* Either (plus (biv) (invar)) or
5566 (plus (mult (biv) (invar_1)) (invar_2)). */
5567 if (GET_CODE (XEXP (x, 0)) == MULT)
5569 *src_reg = XEXP (XEXP (x, 0), 0);
5570 *mult_val = XEXP (XEXP (x, 0), 1);
5574 *src_reg = XEXP (x, 0);
5575 *mult_val = const1_rtx;
5577 *add_val = XEXP (x, 1);
5581 /* ADD_VAL is zero. */
5582 *src_reg = XEXP (x, 0);
5583 *mult_val = XEXP (x, 1);
5584 *add_val = const0_rtx;
5591 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5592 unless they are CONST_INT). */
5593 if (GET_CODE (*add_val) == USE)
5594 *add_val = XEXP (*add_val, 0);
5595 if (GET_CODE (*mult_val) == USE)
5596 *mult_val = XEXP (*mult_val, 0);
5599 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5601 *pbenefit += rtx_cost (orig_x, SET);
5603 /* Always return true if this is a giv so it will be detected as such,
5604 even if the benefit is zero or negative. This allows elimination
5605 of bivs that might otherwise not be eliminated. */
5609 /* Given an expression, X, try to form it as a linear function of a biv.
5610 We will canonicalize it to be of the form
5611 (plus (mult (BIV) (invar_1))
5613 with possible degeneracies.
5615 The invariant expressions must each be of a form that can be used as a
5616 machine operand. We surround then with a USE rtx (a hack, but localized
5617 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5618 routine; it is the caller's responsibility to strip them.
5620 If no such canonicalization is possible (i.e., two biv's are used or an
5621 expression that is neither invariant nor a biv or giv), this routine
5624 For a non-zero return, the result will have a code of CONST_INT, USE,
5625 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5627 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5629 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5630 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5633 simplify_giv_expr (loop, x, ext_val, benefit)
5634 const struct loop *loop;
5639 struct loop_ivs *ivs = LOOP_IVS (loop);
5640 struct loop_regs *regs = LOOP_REGS (loop);
5641 enum machine_mode mode = GET_MODE (x);
5645 /* If this is not an integer mode, or if we cannot do arithmetic in this
5646 mode, this can't be a giv. */
5647 if (mode != VOIDmode
5648 && (GET_MODE_CLASS (mode) != MODE_INT
5649 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5652 switch (GET_CODE (x))
5655 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5656 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5657 if (arg0 == 0 || arg1 == 0)
5660 /* Put constant last, CONST_INT last if both constant. */
5661 if ((GET_CODE (arg0) == USE
5662 || GET_CODE (arg0) == CONST_INT)
5663 && ! ((GET_CODE (arg0) == USE
5664 && GET_CODE (arg1) == USE)
5665 || GET_CODE (arg1) == CONST_INT))
5666 tem = arg0, arg0 = arg1, arg1 = tem;
5668 /* Handle addition of zero, then addition of an invariant. */
5669 if (arg1 == const0_rtx)
5671 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5672 switch (GET_CODE (arg0))
5676 /* Adding two invariants must result in an invariant, so enclose
5677 addition operation inside a USE and return it. */
5678 if (GET_CODE (arg0) == USE)
5679 arg0 = XEXP (arg0, 0);
5680 if (GET_CODE (arg1) == USE)
5681 arg1 = XEXP (arg1, 0);
5683 if (GET_CODE (arg0) == CONST_INT)
5684 tem = arg0, arg0 = arg1, arg1 = tem;
5685 if (GET_CODE (arg1) == CONST_INT)
5686 tem = sge_plus_constant (arg0, arg1);
5688 tem = sge_plus (mode, arg0, arg1);
5690 if (GET_CODE (tem) != CONST_INT)
5691 tem = gen_rtx_USE (mode, tem);
5696 /* biv + invar or mult + invar. Return sum. */
5697 return gen_rtx_PLUS (mode, arg0, arg1);
5700 /* (a + invar_1) + invar_2. Associate. */
5702 simplify_giv_expr (loop,
5714 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5715 MULT to reduce cases. */
5716 if (GET_CODE (arg0) == REG)
5717 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5718 if (GET_CODE (arg1) == REG)
5719 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5721 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5722 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5723 Recurse to associate the second PLUS. */
5724 if (GET_CODE (arg1) == MULT)
5725 tem = arg0, arg0 = arg1, arg1 = tem;
5727 if (GET_CODE (arg1) == PLUS)
5729 simplify_giv_expr (loop,
5731 gen_rtx_PLUS (mode, arg0,
5736 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5737 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5740 if (!rtx_equal_p (arg0, arg1))
5743 return simplify_giv_expr (loop,
5752 /* Handle "a - b" as "a + b * (-1)". */
5753 return simplify_giv_expr (loop,
5762 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5763 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5764 if (arg0 == 0 || arg1 == 0)
5767 /* Put constant last, CONST_INT last if both constant. */
5768 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5769 && GET_CODE (arg1) != CONST_INT)
5770 tem = arg0, arg0 = arg1, arg1 = tem;
5772 /* If second argument is not now constant, not giv. */
5773 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5776 /* Handle multiply by 0 or 1. */
5777 if (arg1 == const0_rtx)
5780 else if (arg1 == const1_rtx)
5783 switch (GET_CODE (arg0))
5786 /* biv * invar. Done. */
5787 return gen_rtx_MULT (mode, arg0, arg1);
5790 /* Product of two constants. */
5791 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5794 /* invar * invar is a giv, but attempt to simplify it somehow. */
5795 if (GET_CODE (arg1) != CONST_INT)
5798 arg0 = XEXP (arg0, 0);
5799 if (GET_CODE (arg0) == MULT)
5801 /* (invar_0 * invar_1) * invar_2. Associate. */
5802 return simplify_giv_expr (loop,
5811 /* Porpagate the MULT expressions to the intermost nodes. */
5812 else if (GET_CODE (arg0) == PLUS)
5814 /* (invar_0 + invar_1) * invar_2. Distribute. */
5815 return simplify_giv_expr (loop,
5827 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
5830 /* (a * invar_1) * invar_2. Associate. */
5831 return simplify_giv_expr (loop,
5840 /* (a + invar_1) * invar_2. Distribute. */
5841 return simplify_giv_expr (loop,
5856 /* Shift by constant is multiply by power of two. */
5857 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5861 simplify_giv_expr (loop,
5864 GEN_INT ((HOST_WIDE_INT) 1
5865 << INTVAL (XEXP (x, 1)))),
5869 /* "-a" is "a * (-1)" */
5870 return simplify_giv_expr (loop,
5871 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
5875 /* "~a" is "-a - 1". Silly, but easy. */
5876 return simplify_giv_expr (loop,
5877 gen_rtx_MINUS (mode,
5878 gen_rtx_NEG (mode, XEXP (x, 0)),
5883 /* Already in proper form for invariant. */
5889 /* Conditionally recognize extensions of simple IVs. After we've
5890 computed loop traversal counts and verified the range of the
5891 source IV, we'll reevaluate this as a GIV. */
5892 if (*ext_val == NULL_RTX)
5894 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5895 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
5897 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
5904 /* If this is a new register, we can't deal with it. */
5905 if (REGNO (x) >= max_reg_before_loop)
5908 /* Check for biv or giv. */
5909 switch (REG_IV_TYPE (ivs, REGNO (x)))
5913 case GENERAL_INDUCT:
5915 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
5917 /* Form expression from giv and add benefit. Ensure this giv
5918 can derive another and subtract any needed adjustment if so. */
5920 /* Increasing the benefit here is risky. The only case in which it
5921 is arguably correct is if this is the only use of V. In other
5922 cases, this will artificially inflate the benefit of the current
5923 giv, and lead to suboptimal code. Thus, it is disabled, since
5924 potentially not reducing an only marginally beneficial giv is
5925 less harmful than reducing many givs that are not really
5928 rtx single_use = regs->array[REGNO (x)].single_usage;
5929 if (single_use && single_use != const0_rtx)
5930 *benefit += v->benefit;
5936 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
5937 v->src_reg, v->mult_val),
5940 if (v->derive_adjustment)
5941 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
5942 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
5945 if (!v->ext_dependant)
5950 *ext_val = v->ext_dependant;
5958 /* If it isn't an induction variable, and it is invariant, we
5959 may be able to simplify things further by looking through
5960 the bits we just moved outside the loop. */
5961 if (loop_invariant_p (loop, x) == 1)
5964 struct loop_movables *movables = LOOP_MOVABLES (loop);
5966 for (m = movables->head; m; m = m->next)
5967 if (rtx_equal_p (x, m->set_dest))
5969 /* Ok, we found a match. Substitute and simplify. */
5971 /* If we match another movable, we must use that, as
5972 this one is going away. */
5974 return simplify_giv_expr (loop, m->match->set_dest,
5977 /* If consec is non-zero, this is a member of a group of
5978 instructions that were moved together. We handle this
5979 case only to the point of seeking to the last insn and
5980 looking for a REG_EQUAL. Fail if we don't find one. */
5987 tem = NEXT_INSN (tem);
5991 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
5993 tem = XEXP (tem, 0);
5997 tem = single_set (m->insn);
5999 tem = SET_SRC (tem);
6004 /* What we are most interested in is pointer
6005 arithmetic on invariants -- only take
6006 patterns we may be able to do something with. */
6007 if (GET_CODE (tem) == PLUS
6008 || GET_CODE (tem) == MULT
6009 || GET_CODE (tem) == ASHIFT
6010 || GET_CODE (tem) == CONST_INT
6011 || GET_CODE (tem) == SYMBOL_REF)
6013 tem = simplify_giv_expr (loop, tem, ext_val,
6018 else if (GET_CODE (tem) == CONST
6019 && GET_CODE (XEXP (tem, 0)) == PLUS
6020 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6021 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6023 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6035 /* Fall through to general case. */
6037 /* If invariant, return as USE (unless CONST_INT).
6038 Otherwise, not giv. */
6039 if (GET_CODE (x) == USE)
6042 if (loop_invariant_p (loop, x) == 1)
6044 if (GET_CODE (x) == CONST_INT)
6046 if (GET_CODE (x) == CONST
6047 && GET_CODE (XEXP (x, 0)) == PLUS
6048 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6049 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6051 return gen_rtx_USE (mode, x);
6058 /* This routine folds invariants such that there is only ever one
6059 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6062 sge_plus_constant (x, c)
6065 if (GET_CODE (x) == CONST_INT)
6066 return GEN_INT (INTVAL (x) + INTVAL (c));
6067 else if (GET_CODE (x) != PLUS)
6068 return gen_rtx_PLUS (GET_MODE (x), x, c);
6069 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6071 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6072 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6074 else if (GET_CODE (XEXP (x, 0)) == PLUS
6075 || GET_CODE (XEXP (x, 1)) != PLUS)
6077 return gen_rtx_PLUS (GET_MODE (x),
6078 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6082 return gen_rtx_PLUS (GET_MODE (x),
6083 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6088 sge_plus (mode, x, y)
6089 enum machine_mode mode;
6092 while (GET_CODE (y) == PLUS)
6094 rtx a = XEXP (y, 0);
6095 if (GET_CODE (a) == CONST_INT)
6096 x = sge_plus_constant (x, a);
6098 x = gen_rtx_PLUS (mode, x, a);
6101 if (GET_CODE (y) == CONST_INT)
6102 x = sge_plus_constant (x, y);
6104 x = gen_rtx_PLUS (mode, x, y);
6108 /* Help detect a giv that is calculated by several consecutive insns;
6112 The caller has already identified the first insn P as having a giv as dest;
6113 we check that all other insns that set the same register follow
6114 immediately after P, that they alter nothing else,
6115 and that the result of the last is still a giv.
6117 The value is 0 if the reg set in P is not really a giv.
6118 Otherwise, the value is the amount gained by eliminating
6119 all the consecutive insns that compute the value.
6121 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6122 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6124 The coefficients of the ultimate giv value are stored in
6125 *MULT_VAL and *ADD_VAL. */
6128 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6129 add_val, mult_val, ext_val, last_consec_insn)
6130 const struct loop *loop;
6138 rtx *last_consec_insn;
6140 struct loop_ivs *ivs = LOOP_IVS (loop);
6141 struct loop_regs *regs = LOOP_REGS (loop);
6148 /* Indicate that this is a giv so that we can update the value produced in
6149 each insn of the multi-insn sequence.
6151 This induction structure will be used only by the call to
6152 general_induction_var below, so we can allocate it on our stack.
6153 If this is a giv, our caller will replace the induct var entry with
6154 a new induction structure. */
6155 struct induction *v;
6157 if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
6160 v = (struct induction *) alloca (sizeof (struct induction));
6161 v->src_reg = src_reg;
6162 v->mult_val = *mult_val;
6163 v->add_val = *add_val;
6164 v->benefit = first_benefit;
6166 v->derive_adjustment = 0;
6167 v->ext_dependant = NULL_RTX;
6169 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6170 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6172 count = regs->array[REGNO (dest_reg)].n_times_set - 1;
6177 code = GET_CODE (p);
6179 /* If libcall, skip to end of call sequence. */
6180 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6184 && (set = single_set (p))
6185 && GET_CODE (SET_DEST (set)) == REG
6186 && SET_DEST (set) == dest_reg
6187 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6188 add_val, mult_val, ext_val, 0,
6190 /* Giv created by equivalent expression. */
6191 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6192 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6193 add_val, mult_val, ext_val, 0,
6194 &benefit, VOIDmode)))
6195 && src_reg == v->src_reg)
6197 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6198 benefit += libcall_benefit (p);
6201 v->mult_val = *mult_val;
6202 v->add_val = *add_val;
6203 v->benefit += benefit;
6205 else if (code != NOTE)
6207 /* Allow insns that set something other than this giv to a
6208 constant. Such insns are needed on machines which cannot
6209 include long constants and should not disqualify a giv. */
6211 && (set = single_set (p))
6212 && SET_DEST (set) != dest_reg
6213 && CONSTANT_P (SET_SRC (set)))
6216 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6221 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6222 *last_consec_insn = p;
6226 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6227 represented by G1. If no such expression can be found, or it is clear that
6228 it cannot possibly be a valid address, 0 is returned.
6230 To perform the computation, we note that
6233 where `v' is the biv.
6235 So G2 = (y/b) * G1 + (b - a*y/x).
6237 Note that MULT = y/x.
6239 Update: A and B are now allowed to be additive expressions such that
6240 B contains all variables in A. That is, computing B-A will not require
6241 subtracting variables. */
6244 express_from_1 (a, b, mult)
6247 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6249 if (mult == const0_rtx)
6252 /* If MULT is not 1, we cannot handle A with non-constants, since we
6253 would then be required to subtract multiples of the registers in A.
6254 This is theoretically possible, and may even apply to some Fortran
6255 constructs, but it is a lot of work and we do not attempt it here. */
6257 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6260 /* In general these structures are sorted top to bottom (down the PLUS
6261 chain), but not left to right across the PLUS. If B is a higher
6262 order giv than A, we can strip one level and recurse. If A is higher
6263 order, we'll eventually bail out, but won't know that until the end.
6264 If they are the same, we'll strip one level around this loop. */
6266 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6268 rtx ra, rb, oa, ob, tmp;
6270 ra = XEXP (a, 0), oa = XEXP (a, 1);
6271 if (GET_CODE (ra) == PLUS)
6272 tmp = ra, ra = oa, oa = tmp;
6274 rb = XEXP (b, 0), ob = XEXP (b, 1);
6275 if (GET_CODE (rb) == PLUS)
6276 tmp = rb, rb = ob, ob = tmp;
6278 if (rtx_equal_p (ra, rb))
6279 /* We matched: remove one reg completely. */
6281 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6282 /* An alternate match. */
6284 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6285 /* An alternate match. */
6289 /* Indicates an extra register in B. Strip one level from B and
6290 recurse, hoping B was the higher order expression. */
6291 ob = express_from_1 (a, ob, mult);
6294 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6298 /* Here we are at the last level of A, go through the cases hoping to
6299 get rid of everything but a constant. */
6301 if (GET_CODE (a) == PLUS)
6305 ra = XEXP (a, 0), oa = XEXP (a, 1);
6306 if (rtx_equal_p (oa, b))
6308 else if (!rtx_equal_p (ra, b))
6311 if (GET_CODE (oa) != CONST_INT)
6314 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6316 else if (GET_CODE (a) == CONST_INT)
6318 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6320 else if (CONSTANT_P (a))
6322 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6324 else if (GET_CODE (b) == PLUS)
6326 if (rtx_equal_p (a, XEXP (b, 0)))
6328 else if (rtx_equal_p (a, XEXP (b, 1)))
6333 else if (rtx_equal_p (a, b))
6340 express_from (g1, g2)
6341 struct induction *g1, *g2;
6345 /* The value that G1 will be multiplied by must be a constant integer. Also,
6346 the only chance we have of getting a valid address is if b*c/a (see above
6347 for notation) is also an integer. */
6348 if (GET_CODE (g1->mult_val) == CONST_INT
6349 && GET_CODE (g2->mult_val) == CONST_INT)
6351 if (g1->mult_val == const0_rtx
6352 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6354 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6356 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6360 /* ??? Find out if the one is a multiple of the other? */
6364 add = express_from_1 (g1->add_val, g2->add_val, mult);
6365 if (add == NULL_RTX)
6367 /* Failed. If we've got a multiplication factor between G1 and G2,
6368 scale G1's addend and try again. */
6369 if (INTVAL (mult) > 1)
6371 rtx g1_add_val = g1->add_val;
6372 if (GET_CODE (g1_add_val) == MULT
6373 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6376 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6377 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6378 XEXP (g1_add_val, 0), GEN_INT (m));
6382 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6386 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6389 if (add == NULL_RTX)
6392 /* Form simplified final result. */
6393 if (mult == const0_rtx)
6395 else if (mult == const1_rtx)
6396 mult = g1->dest_reg;
6398 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6400 if (add == const0_rtx)
6404 if (GET_CODE (add) == PLUS
6405 && CONSTANT_P (XEXP (add, 1)))
6407 rtx tem = XEXP (add, 1);
6408 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6412 return gen_rtx_PLUS (g2->mode, mult, add);
6416 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6417 represented by G1. This indicates that G2 should be combined with G1 and
6418 that G2 can use (either directly or via an address expression) a register
6419 used to represent G1. */
6422 combine_givs_p (g1, g2)
6423 struct induction *g1, *g2;
6427 /* With the introduction of ext dependant givs, we must care for modes.
6428 G2 must not use a wider mode than G1. */
6429 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6432 ret = comb = express_from (g1, g2);
6433 if (comb == NULL_RTX)
6435 if (g1->mode != g2->mode)
6436 ret = gen_lowpart (g2->mode, comb);
6438 /* If these givs are identical, they can be combined. We use the results
6439 of express_from because the addends are not in a canonical form, so
6440 rtx_equal_p is a weaker test. */
6441 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6442 combination to be the other way round. */
6443 if (comb == g1->dest_reg
6444 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6449 /* If G2 can be expressed as a function of G1 and that function is valid
6450 as an address and no more expensive than using a register for G2,
6451 the expression of G2 in terms of G1 can be used. */
6453 && g2->giv_type == DEST_ADDR
6454 && memory_address_p (GET_MODE (g2->mem), ret)
6455 /* ??? Looses, especially with -fforce-addr, where *g2->location
6456 will always be a register, and so anything more complicated
6460 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6462 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6473 /* Check each extension dependant giv in this class to see if its
6474 root biv is safe from wrapping in the interior mode, which would
6475 make the giv illegal. */
6478 check_ext_dependant_givs (bl, loop_info)
6479 struct iv_class *bl;
6480 struct loop_info *loop_info;
6482 int ze_ok = 0, se_ok = 0, info_ok = 0;
6483 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6484 HOST_WIDE_INT start_val;
6485 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6487 struct induction *v;
6489 /* Make sure the iteration data is available. We must have
6490 constants in order to be certain of no overflow. */
6491 /* ??? An unknown iteration count with an increment of +-1
6492 combined with friendly exit tests of against an invariant
6493 value is also ameanable to optimization. Not implemented. */
6494 if (loop_info->n_iterations > 0
6495 && bl->initial_value
6496 && GET_CODE (bl->initial_value) == CONST_INT
6497 && (incr = biv_total_increment (bl))
6498 && GET_CODE (incr) == CONST_INT
6499 /* Make sure the host can represent the arithmetic. */
6500 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6502 unsigned HOST_WIDE_INT abs_incr, total_incr;
6503 HOST_WIDE_INT s_end_val;
6507 start_val = INTVAL (bl->initial_value);
6508 u_start_val = start_val;
6510 neg_incr = 0, abs_incr = INTVAL (incr);
6511 if (INTVAL (incr) < 0)
6512 neg_incr = 1, abs_incr = -abs_incr;
6513 total_incr = abs_incr * loop_info->n_iterations;
6515 /* Check for host arithmatic overflow. */
6516 if (total_incr / loop_info->n_iterations == abs_incr)
6518 unsigned HOST_WIDE_INT u_max;
6519 HOST_WIDE_INT s_max;
6521 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6522 s_end_val = u_end_val;
6523 u_max = GET_MODE_MASK (biv_mode);
6526 /* Check zero extension of biv ok. */
6528 /* Check for host arithmatic overflow. */
6530 ? u_end_val < u_start_val
6531 : u_end_val > u_start_val)
6532 /* Check for target arithmetic overflow. */
6534 ? 1 /* taken care of with host overflow */
6535 : u_end_val <= u_max))
6540 /* Check sign extension of biv ok. */
6541 /* ??? While it is true that overflow with signed and pointer
6542 arithmetic is undefined, I fear too many programmers don't
6543 keep this fact in mind -- myself included on occasion.
6544 So leave alone with the signed overflow optimizations. */
6545 if (start_val >= -s_max - 1
6546 /* Check for host arithmatic overflow. */
6548 ? s_end_val < start_val
6549 : s_end_val > start_val)
6550 /* Check for target arithmetic overflow. */
6552 ? s_end_val >= -s_max - 1
6553 : s_end_val <= s_max))
6560 /* Invalidate givs that fail the tests. */
6561 for (v = bl->giv; v; v = v->next_iv)
6562 if (v->ext_dependant)
6564 enum rtx_code code = GET_CODE (v->ext_dependant);
6577 /* We don't know whether this value is being used as either
6578 signed or unsigned, so to safely truncate we must satisfy
6579 both. The initial check here verifies the BIV itself;
6580 once that is successful we may check its range wrt the
6584 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6585 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6587 /* We know from the above that both endpoints are nonnegative,
6588 and that there is no wrapping. Verify that both endpoints
6589 are within the (signed) range of the outer mode. */
6590 if (u_start_val <= max && u_end_val <= max)
6601 if (loop_dump_stream)
6603 fprintf (loop_dump_stream,
6604 "Verified ext dependant giv at %d of reg %d\n",
6605 INSN_UID (v->insn), bl->regno);
6610 if (loop_dump_stream)
6615 why = "biv iteration values overflowed";
6619 incr = biv_total_increment (bl);
6620 if (incr == const1_rtx)
6621 why = "biv iteration info incomplete; incr by 1";
6623 why = "biv iteration info incomplete";
6626 fprintf (loop_dump_stream,
6627 "Failed ext dependant giv at %d, %s\n",
6628 INSN_UID (v->insn), why);
6635 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6638 extend_value_for_giv (v, value)
6639 struct induction *v;
6642 rtx ext_dep = v->ext_dependant;
6647 /* Recall that check_ext_dependant_givs verified that the known bounds
6648 of a biv did not overflow or wrap with respect to the extension for
6649 the giv. Therefore, constants need no additional adjustment. */
6650 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6653 /* Otherwise, we must adjust the value to compensate for the
6654 differing modes of the biv and the giv. */
6655 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6658 struct combine_givs_stats
6665 cmp_combine_givs_stats (xp, yp)
6669 const struct combine_givs_stats * const x =
6670 (const struct combine_givs_stats *) xp;
6671 const struct combine_givs_stats * const y =
6672 (const struct combine_givs_stats *) yp;
6674 d = y->total_benefit - x->total_benefit;
6675 /* Stabilize the sort. */
6677 d = x->giv_number - y->giv_number;
6681 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6682 any other. If so, point SAME to the giv combined with and set NEW_REG to
6683 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6684 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6687 combine_givs (regs, bl)
6688 struct loop_regs *regs;
6689 struct iv_class *bl;
6691 /* Additional benefit to add for being combined multiple times. */
6692 const int extra_benefit = 3;
6694 struct induction *g1, *g2, **giv_array;
6695 int i, j, k, giv_count;
6696 struct combine_givs_stats *stats;
6699 /* Count givs, because bl->giv_count is incorrect here. */
6701 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6706 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6708 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6710 giv_array[i++] = g1;
6712 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6713 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6715 for (i = 0; i < giv_count; i++)
6721 stats[i].giv_number = i;
6723 /* If a DEST_REG GIV is used only once, do not allow it to combine
6724 with anything, for in doing so we will gain nothing that cannot
6725 be had by simply letting the GIV with which we would have combined
6726 to be reduced on its own. The losage shows up in particular with
6727 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6728 be seen elsewhere as well. */
6729 if (g1->giv_type == DEST_REG
6730 && (single_use = regs->array[REGNO (g1->dest_reg)].single_usage)
6731 && single_use != const0_rtx)
6734 this_benefit = g1->benefit;
6735 /* Add an additional weight for zero addends. */
6736 if (g1->no_const_addval)
6739 for (j = 0; j < giv_count; j++)
6745 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6747 can_combine[i * giv_count + j] = this_combine;
6748 this_benefit += g2->benefit + extra_benefit;
6751 stats[i].total_benefit = this_benefit;
6754 /* Iterate, combining until we can't. */
6756 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6758 if (loop_dump_stream)
6760 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6761 for (k = 0; k < giv_count; k++)
6763 g1 = giv_array[stats[k].giv_number];
6764 if (!g1->combined_with && !g1->same)
6765 fprintf (loop_dump_stream, " {%d, %d}",
6766 INSN_UID (giv_array[stats[k].giv_number]->insn),
6767 stats[k].total_benefit);
6769 putc ('\n', loop_dump_stream);
6772 for (k = 0; k < giv_count; k++)
6774 int g1_add_benefit = 0;
6776 i = stats[k].giv_number;
6779 /* If it has already been combined, skip. */
6780 if (g1->combined_with || g1->same)
6783 for (j = 0; j < giv_count; j++)
6786 if (g1 != g2 && can_combine[i * giv_count + j]
6787 /* If it has already been combined, skip. */
6788 && ! g2->same && ! g2->combined_with)
6792 g2->new_reg = can_combine[i * giv_count + j];
6794 g1->combined_with++;
6795 g1->lifetime += g2->lifetime;
6797 g1_add_benefit += g2->benefit;
6799 /* ??? The new final_[bg]iv_value code does a much better job
6800 of finding replaceable giv's, and hence this code may no
6801 longer be necessary. */
6802 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6803 g1_add_benefit -= copy_cost;
6805 /* To help optimize the next set of combinations, remove
6806 this giv from the benefits of other potential mates. */
6807 for (l = 0; l < giv_count; ++l)
6809 int m = stats[l].giv_number;
6810 if (can_combine[m * giv_count + j])
6811 stats[l].total_benefit -= g2->benefit + extra_benefit;
6814 if (loop_dump_stream)
6815 fprintf (loop_dump_stream,
6816 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
6817 INSN_UID (g2->insn), INSN_UID (g1->insn),
6818 g1->benefit, g1_add_benefit, g1->lifetime);
6822 /* To help optimize the next set of combinations, remove
6823 this giv from the benefits of other potential mates. */
6824 if (g1->combined_with)
6826 for (j = 0; j < giv_count; ++j)
6828 int m = stats[j].giv_number;
6829 if (can_combine[m * giv_count + i])
6830 stats[j].total_benefit -= g1->benefit + extra_benefit;
6833 g1->benefit += g1_add_benefit;
6835 /* We've finished with this giv, and everything it touched.
6836 Restart the combination so that proper weights for the
6837 rest of the givs are properly taken into account. */
6838 /* ??? Ideally we would compact the arrays at this point, so
6839 as to not cover old ground. But sanely compacting
6840 can_combine is tricky. */
6850 /* Generate sequence for REG = B * M + A. */
6853 gen_add_mult (b, m, a, reg)
6854 rtx b; /* initial value of basic induction variable */
6855 rtx m; /* multiplicative constant */
6856 rtx a; /* additive constant */
6857 rtx reg; /* destination register */
6863 /* Use unsigned arithmetic. */
6864 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
6866 emit_move_insn (reg, result);
6867 seq = gen_sequence ();
6874 /* Update registers created in insn sequence SEQ. */
6877 loop_regs_update (loop, seq)
6878 const struct loop *loop ATTRIBUTE_UNUSED;
6881 /* Update register info for alias analysis. */
6883 if (GET_CODE (seq) == SEQUENCE)
6886 for (i = 0; i < XVECLEN (seq, 0); ++i)
6888 rtx set = single_set (XVECEXP (seq, 0, i));
6889 if (set && GET_CODE (SET_DEST (set)) == REG)
6890 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6895 rtx set = single_set (seq);
6896 if (set && GET_CODE (SET_DEST (set)) == REG)
6897 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6902 /* EMIT code before BEFORE_BB/BEFORE_INSN to set REG = B * M + A. */
6905 loop_iv_add_mult_emit_before (loop, b, m, a, reg, before_bb, before_insn)
6906 const struct loop *loop;
6907 rtx b; /* initial value of basic induction variable */
6908 rtx m; /* multiplicative constant */
6909 rtx a; /* additive constant */
6910 rtx reg; /* destination register */
6911 basic_block before_bb;
6918 loop_iv_add_mult_hoist (loop, b, m, a, reg);
6922 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
6923 seq = gen_add_mult (copy_rtx (b), m, copy_rtx (a), reg);
6925 /* Increase the lifetime of any invariants moved further in code. */
6926 update_reg_last_use (a, before_insn);
6927 update_reg_last_use (b, before_insn);
6928 update_reg_last_use (m, before_insn);
6930 loop_insn_emit_before (loop, before_bb, before_insn, seq);
6932 /* It is possible that the expansion created lots of new registers.
6933 Iterate over the sequence we just created and record them all. */
6934 loop_regs_update (loop, seq);
6938 /* Emit insns in loop pre-header to set REG = B * M + A. */
6941 loop_iv_add_mult_sink (loop, b, m, a, reg)
6942 const struct loop *loop;
6943 rtx b; /* initial value of basic induction variable */
6944 rtx m; /* multiplicative constant */
6945 rtx a; /* additive constant */
6946 rtx reg; /* destination register */
6950 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
6951 seq = gen_add_mult (copy_rtx (b), m, copy_rtx (a), reg);
6953 /* Increase the lifetime of any invariants moved further in code.
6954 ???? Is this really necessary? */
6955 update_reg_last_use (a, loop->sink);
6956 update_reg_last_use (b, loop->sink);
6957 update_reg_last_use (m, loop->sink);
6959 loop_insn_sink (loop, seq);
6961 /* It is possible that the expansion created lots of new registers.
6962 Iterate over the sequence we just created and record them all. */
6963 loop_regs_update (loop, seq);
6967 /* Emit insns after loop to set REG = B * M + A. */
6970 loop_iv_add_mult_hoist (loop, b, m, a, reg)
6971 const struct loop *loop;
6972 rtx b; /* initial value of basic induction variable */
6973 rtx m; /* multiplicative constant */
6974 rtx a; /* additive constant */
6975 rtx reg; /* destination register */
6979 /* Use copy_rtx to prevent unexpected sharing of these rtx. */
6980 seq = gen_add_mult (copy_rtx (b), m, copy_rtx (a), reg);
6982 loop_insn_hoist (loop, seq);
6984 /* It is possible that the expansion created lots of new registers.
6985 Iterate over the sequence we just created and record them all. */
6986 loop_regs_update (loop, seq);
6991 /* Similar to gen_add_mult, but compute cost rather than generating
6995 iv_add_mult_cost (b, m, a, reg)
6996 rtx b; /* initial value of basic induction variable */
6997 rtx m; /* multiplicative constant */
6998 rtx a; /* additive constant */
6999 rtx reg; /* destination register */
7005 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
7007 emit_move_insn (reg, result);
7008 last = get_last_insn ();
7011 rtx t = single_set (last);
7013 cost += rtx_cost (SET_SRC (t), SET);
7014 last = PREV_INSN (last);
7020 /* Test whether A * B can be computed without
7021 an actual multiply insn. Value is 1 if so. */
7024 product_cheap_p (a, b)
7032 /* If only one is constant, make it B. */
7033 if (GET_CODE (a) == CONST_INT)
7034 tmp = a, a = b, b = tmp;
7036 /* If first constant, both constant, so don't need multiply. */
7037 if (GET_CODE (a) == CONST_INT)
7040 /* If second not constant, neither is constant, so would need multiply. */
7041 if (GET_CODE (b) != CONST_INT)
7044 /* One operand is constant, so might not need multiply insn. Generate the
7045 code for the multiply and see if a call or multiply, or long sequence
7046 of insns is generated. */
7049 expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
7050 tmp = gen_sequence ();
7053 if (GET_CODE (tmp) == SEQUENCE)
7055 if (XVEC (tmp, 0) == 0)
7057 else if (XVECLEN (tmp, 0) > 3)
7060 for (i = 0; i < XVECLEN (tmp, 0); i++)
7062 rtx insn = XVECEXP (tmp, 0, i);
7064 if (GET_CODE (insn) != INSN
7065 || (GET_CODE (PATTERN (insn)) == SET
7066 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
7067 || (GET_CODE (PATTERN (insn)) == PARALLEL
7068 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
7069 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
7076 else if (GET_CODE (tmp) == SET
7077 && GET_CODE (SET_SRC (tmp)) == MULT)
7079 else if (GET_CODE (tmp) == PARALLEL
7080 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
7081 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7087 /* Check to see if loop can be terminated by a "decrement and branch until
7088 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7089 Also try reversing an increment loop to a decrement loop
7090 to see if the optimization can be performed.
7091 Value is nonzero if optimization was performed. */
7093 /* This is useful even if the architecture doesn't have such an insn,
7094 because it might change a loops which increments from 0 to n to a loop
7095 which decrements from n to 0. A loop that decrements to zero is usually
7096 faster than one that increments from zero. */
7098 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7099 such as approx_final_value, biv_total_increment, loop_iterations, and
7100 final_[bg]iv_value. */
7103 check_dbra_loop (loop, insn_count)
7107 struct loop_info *loop_info = LOOP_INFO (loop);
7108 struct loop_regs *regs = LOOP_REGS (loop);
7109 struct loop_ivs *ivs = LOOP_IVS (loop);
7110 struct iv_class *bl;
7117 rtx before_comparison;
7121 int compare_and_branch;
7122 rtx loop_start = loop->start;
7123 rtx loop_end = loop->end;
7125 /* If last insn is a conditional branch, and the insn before tests a
7126 register value, try to optimize it. Otherwise, we can't do anything. */
7128 jump = PREV_INSN (loop_end);
7129 comparison = get_condition_for_loop (loop, jump);
7130 if (comparison == 0)
7132 if (!onlyjump_p (jump))
7135 /* Try to compute whether the compare/branch at the loop end is one or
7136 two instructions. */
7137 get_condition (jump, &first_compare);
7138 if (first_compare == jump)
7139 compare_and_branch = 1;
7140 else if (first_compare == prev_nonnote_insn (jump))
7141 compare_and_branch = 2;
7146 /* If more than one condition is present to control the loop, then
7147 do not proceed, as this function does not know how to rewrite
7148 loop tests with more than one condition.
7150 Look backwards from the first insn in the last comparison
7151 sequence and see if we've got another comparison sequence. */
7154 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7155 if (GET_CODE (jump1) == JUMP_INSN)
7159 /* Check all of the bivs to see if the compare uses one of them.
7160 Skip biv's set more than once because we can't guarantee that
7161 it will be zero on the last iteration. Also skip if the biv is
7162 used between its update and the test insn. */
7164 for (bl = ivs->list; bl; bl = bl->next)
7166 if (bl->biv_count == 1
7167 && ! bl->biv->maybe_multiple
7168 && bl->biv->dest_reg == XEXP (comparison, 0)
7169 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7177 /* Look for the case where the basic induction variable is always
7178 nonnegative, and equals zero on the last iteration.
7179 In this case, add a reg_note REG_NONNEG, which allows the
7180 m68k DBRA instruction to be used. */
7182 if (((GET_CODE (comparison) == GT
7183 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7184 && INTVAL (XEXP (comparison, 1)) == -1)
7185 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7186 && GET_CODE (bl->biv->add_val) == CONST_INT
7187 && INTVAL (bl->biv->add_val) < 0)
7189 /* Initial value must be greater than 0,
7190 init_val % -dec_value == 0 to ensure that it equals zero on
7191 the last iteration */
7193 if (GET_CODE (bl->initial_value) == CONST_INT
7194 && INTVAL (bl->initial_value) > 0
7195 && (INTVAL (bl->initial_value)
7196 % (-INTVAL (bl->biv->add_val))) == 0)
7198 /* register always nonnegative, add REG_NOTE to branch */
7199 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7201 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7208 /* If the decrement is 1 and the value was tested as >= 0 before
7209 the loop, then we can safely optimize. */
7210 for (p = loop_start; p; p = PREV_INSN (p))
7212 if (GET_CODE (p) == CODE_LABEL)
7214 if (GET_CODE (p) != JUMP_INSN)
7217 before_comparison = get_condition_for_loop (loop, p);
7218 if (before_comparison
7219 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7220 && GET_CODE (before_comparison) == LT
7221 && XEXP (before_comparison, 1) == const0_rtx
7222 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7223 && INTVAL (bl->biv->add_val) == -1)
7225 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7227 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7235 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7236 && INTVAL (bl->biv->add_val) > 0)
7238 /* Try to change inc to dec, so can apply above optimization. */
7240 all registers modified are induction variables or invariant,
7241 all memory references have non-overlapping addresses
7242 (obviously true if only one write)
7243 allow 2 insns for the compare/jump at the end of the loop. */
7244 /* Also, we must avoid any instructions which use both the reversed
7245 biv and another biv. Such instructions will fail if the loop is
7246 reversed. We meet this condition by requiring that either
7247 no_use_except_counting is true, or else that there is only
7249 int num_nonfixed_reads = 0;
7250 /* 1 if the iteration var is used only to count iterations. */
7251 int no_use_except_counting = 0;
7252 /* 1 if the loop has no memory store, or it has a single memory store
7253 which is reversible. */
7254 int reversible_mem_store = 1;
7256 if (bl->giv_count == 0 && ! loop->exit_count)
7258 rtx bivreg = regno_reg_rtx[bl->regno];
7260 /* If there are no givs for this biv, and the only exit is the
7261 fall through at the end of the loop, then
7262 see if perhaps there are no uses except to count. */
7263 no_use_except_counting = 1;
7264 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7267 rtx set = single_set (p);
7269 if (set && GET_CODE (SET_DEST (set)) == REG
7270 && REGNO (SET_DEST (set)) == bl->regno)
7271 /* An insn that sets the biv is okay. */
7273 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7274 || p == prev_nonnote_insn (loop_end))
7275 && reg_mentioned_p (bivreg, PATTERN (p)))
7277 /* If either of these insns uses the biv and sets a pseudo
7278 that has more than one usage, then the biv has uses
7279 other than counting since it's used to derive a value
7280 that is used more than one time. */
7281 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7283 if (regs->multiple_uses)
7285 no_use_except_counting = 0;
7289 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7291 no_use_except_counting = 0;
7297 if (no_use_except_counting)
7298 /* No need to worry about MEMs. */
7300 else if (loop_info->num_mem_sets <= 1)
7302 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7304 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7306 /* If the loop has a single store, and the destination address is
7307 invariant, then we can't reverse the loop, because this address
7308 might then have the wrong value at loop exit.
7309 This would work if the source was invariant also, however, in that
7310 case, the insn should have been moved out of the loop. */
7312 if (loop_info->num_mem_sets == 1)
7314 struct induction *v;
7316 reversible_mem_store
7317 = (! loop_info->unknown_address_altered
7318 && ! loop_info->unknown_constant_address_altered
7319 && ! loop_invariant_p (loop,
7320 XEXP (XEXP (loop_info->store_mems, 0),
7323 /* If the store depends on a register that is set after the
7324 store, it depends on the initial value, and is thus not
7326 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7328 if (v->giv_type == DEST_REG
7329 && reg_mentioned_p (v->dest_reg,
7330 PATTERN (loop_info->first_loop_store_insn))
7331 && loop_insn_first_p (loop_info->first_loop_store_insn,
7333 reversible_mem_store = 0;
7340 /* This code only acts for innermost loops. Also it simplifies
7341 the memory address check by only reversing loops with
7342 zero or one memory access.
7343 Two memory accesses could involve parts of the same array,
7344 and that can't be reversed.
7345 If the biv is used only for counting, than we don't need to worry
7346 about all these things. */
7348 if ((num_nonfixed_reads <= 1
7349 && ! loop_info->has_nonconst_call
7350 && ! loop_info->has_volatile
7351 && reversible_mem_store
7352 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7353 + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
7354 && (bl == ivs->list && bl->next == 0))
7355 || no_use_except_counting)
7359 /* Loop can be reversed. */
7360 if (loop_dump_stream)
7361 fprintf (loop_dump_stream, "Can reverse loop\n");
7363 /* Now check other conditions:
7365 The increment must be a constant, as must the initial value,
7366 and the comparison code must be LT.
7368 This test can probably be improved since +/- 1 in the constant
7369 can be obtained by changing LT to LE and vice versa; this is
7373 /* for constants, LE gets turned into LT */
7374 && (GET_CODE (comparison) == LT
7375 || (GET_CODE (comparison) == LE
7376 && no_use_except_counting)))
7378 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7379 rtx initial_value, comparison_value;
7381 enum rtx_code cmp_code;
7382 int comparison_const_width;
7383 unsigned HOST_WIDE_INT comparison_sign_mask;
7385 add_val = INTVAL (bl->biv->add_val);
7386 comparison_value = XEXP (comparison, 1);
7387 if (GET_MODE (comparison_value) == VOIDmode)
7388 comparison_const_width
7389 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7391 comparison_const_width
7392 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7393 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7394 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7395 comparison_sign_mask
7396 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7398 /* If the comparison value is not a loop invariant, then we
7399 can not reverse this loop.
7401 ??? If the insns which initialize the comparison value as
7402 a whole compute an invariant result, then we could move
7403 them out of the loop and proceed with loop reversal. */
7404 if (! loop_invariant_p (loop, comparison_value))
7407 if (GET_CODE (comparison_value) == CONST_INT)
7408 comparison_val = INTVAL (comparison_value);
7409 initial_value = bl->initial_value;
7411 /* Normalize the initial value if it is an integer and
7412 has no other use except as a counter. This will allow
7413 a few more loops to be reversed. */
7414 if (no_use_except_counting
7415 && GET_CODE (comparison_value) == CONST_INT
7416 && GET_CODE (initial_value) == CONST_INT)
7418 comparison_val = comparison_val - INTVAL (bl->initial_value);
7419 /* The code below requires comparison_val to be a multiple
7420 of add_val in order to do the loop reversal, so
7421 round up comparison_val to a multiple of add_val.
7422 Since comparison_value is constant, we know that the
7423 current comparison code is LT. */
7424 comparison_val = comparison_val + add_val - 1;
7426 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7427 /* We postpone overflow checks for COMPARISON_VAL here;
7428 even if there is an overflow, we might still be able to
7429 reverse the loop, if converting the loop exit test to
7431 initial_value = const0_rtx;
7434 /* First check if we can do a vanilla loop reversal. */
7435 if (initial_value == const0_rtx
7436 /* If we have a decrement_and_branch_on_count,
7437 prefer the NE test, since this will allow that
7438 instruction to be generated. Note that we must
7439 use a vanilla loop reversal if the biv is used to
7440 calculate a giv or has a non-counting use. */
7441 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7442 && defined (HAVE_decrement_and_branch_on_count)
7443 && (! (add_val == 1 && loop->vtop
7444 && (bl->biv_count == 0
7445 || no_use_except_counting)))
7447 && GET_CODE (comparison_value) == CONST_INT
7448 /* Now do postponed overflow checks on COMPARISON_VAL. */
7449 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7450 & comparison_sign_mask))
7452 /* Register will always be nonnegative, with value
7453 0 on last iteration */
7454 add_adjust = add_val;
7458 else if (add_val == 1 && loop->vtop
7459 && (bl->biv_count == 0
7460 || no_use_except_counting))
7468 if (GET_CODE (comparison) == LE)
7469 add_adjust -= add_val;
7471 /* If the initial value is not zero, or if the comparison
7472 value is not an exact multiple of the increment, then we
7473 can not reverse this loop. */
7474 if (initial_value == const0_rtx
7475 && GET_CODE (comparison_value) == CONST_INT)
7477 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7482 if (! no_use_except_counting || add_val != 1)
7486 final_value = comparison_value;
7488 /* Reset these in case we normalized the initial value
7489 and comparison value above. */
7490 if (GET_CODE (comparison_value) == CONST_INT
7491 && GET_CODE (initial_value) == CONST_INT)
7493 comparison_value = GEN_INT (comparison_val);
7495 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7497 bl->initial_value = initial_value;
7499 /* Save some info needed to produce the new insns. */
7500 reg = bl->biv->dest_reg;
7501 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7502 if (jump_label == pc_rtx)
7503 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7504 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7506 /* Set start_value; if this is not a CONST_INT, we need
7508 Initialize biv to start_value before loop start.
7509 The old initializing insn will be deleted as a
7510 dead store by flow.c. */
7511 if (initial_value == const0_rtx
7512 && GET_CODE (comparison_value) == CONST_INT)
7514 start_value = GEN_INT (comparison_val - add_adjust);
7515 loop_insn_hoist (loop, gen_move_insn (reg, start_value));
7517 else if (GET_CODE (initial_value) == CONST_INT)
7519 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7520 enum machine_mode mode = GET_MODE (reg);
7521 enum insn_code icode
7522 = add_optab->handlers[(int) mode].insn_code;
7524 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7525 || ! ((*insn_data[icode].operand[1].predicate)
7526 (comparison_value, mode))
7527 || ! ((*insn_data[icode].operand[2].predicate)
7531 = gen_rtx_PLUS (mode, comparison_value, offset);
7532 loop_insn_hoist (loop, (GEN_FCN (icode)
7533 (reg, comparison_value, offset)));
7534 if (GET_CODE (comparison) == LE)
7535 final_value = gen_rtx_PLUS (mode, comparison_value,
7538 else if (! add_adjust)
7540 enum machine_mode mode = GET_MODE (reg);
7541 enum insn_code icode
7542 = sub_optab->handlers[(int) mode].insn_code;
7543 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7544 || ! ((*insn_data[icode].operand[1].predicate)
7545 (comparison_value, mode))
7546 || ! ((*insn_data[icode].operand[2].predicate)
7547 (initial_value, mode)))
7550 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7551 loop_insn_hoist (loop, (GEN_FCN (icode)
7552 (reg, comparison_value,
7556 /* We could handle the other cases too, but it'll be
7557 better to have a testcase first. */
7560 /* We may not have a single insn which can increment a reg, so
7561 create a sequence to hold all the insns from expand_inc. */
7563 expand_inc (reg, new_add_val);
7564 tem = gen_sequence ();
7567 p = loop_insn_emit_before (loop, 0, bl->biv->insn, tem);
7568 delete_insn (bl->biv->insn);
7570 /* Update biv info to reflect its new status. */
7572 bl->initial_value = start_value;
7573 bl->biv->add_val = new_add_val;
7575 /* Update loop info. */
7576 loop_info->initial_value = reg;
7577 loop_info->initial_equiv_value = reg;
7578 loop_info->final_value = const0_rtx;
7579 loop_info->final_equiv_value = const0_rtx;
7580 loop_info->comparison_value = const0_rtx;
7581 loop_info->comparison_code = cmp_code;
7582 loop_info->increment = new_add_val;
7584 /* Inc LABEL_NUSES so that delete_insn will
7585 not delete the label. */
7586 LABEL_NUSES (XEXP (jump_label, 0))++;
7588 /* Emit an insn after the end of the loop to set the biv's
7589 proper exit value if it is used anywhere outside the loop. */
7590 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7592 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7593 loop_insn_sink (loop, gen_move_insn (reg, final_value));
7595 /* Delete compare/branch at end of loop. */
7596 delete_insn (PREV_INSN (loop_end));
7597 if (compare_and_branch == 2)
7598 delete_insn (first_compare);
7600 /* Add new compare/branch insn at end of loop. */
7602 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7603 GET_MODE (reg), 0, 0,
7604 XEXP (jump_label, 0));
7605 tem = gen_sequence ();
7607 emit_jump_insn_before (tem, loop_end);
7609 for (tem = PREV_INSN (loop_end);
7610 tem && GET_CODE (tem) != JUMP_INSN;
7611 tem = PREV_INSN (tem))
7615 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7621 /* Increment of LABEL_NUSES done above. */
7622 /* Register is now always nonnegative,
7623 so add REG_NONNEG note to the branch. */
7624 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7630 /* No insn may reference both the reversed and another biv or it
7631 will fail (see comment near the top of the loop reversal
7633 Earlier on, we have verified that the biv has no use except
7634 counting, or it is the only biv in this function.
7635 However, the code that computes no_use_except_counting does
7636 not verify reg notes. It's possible to have an insn that
7637 references another biv, and has a REG_EQUAL note with an
7638 expression based on the reversed biv. To avoid this case,
7639 remove all REG_EQUAL notes based on the reversed biv
7641 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7645 rtx set = single_set (p);
7646 /* If this is a set of a GIV based on the reversed biv, any
7647 REG_EQUAL notes should still be correct. */
7649 || GET_CODE (SET_DEST (set)) != REG
7650 || (size_t) REGNO (SET_DEST (set)) >= ivs->n_regs
7651 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7652 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7653 for (pnote = ®_NOTES (p); *pnote;)
7655 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7656 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7658 *pnote = XEXP (*pnote, 1);
7660 pnote = &XEXP (*pnote, 1);
7664 /* Mark that this biv has been reversed. Each giv which depends
7665 on this biv, and which is also live past the end of the loop
7666 will have to be fixed up. */
7670 if (loop_dump_stream)
7672 fprintf (loop_dump_stream, "Reversed loop");
7674 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7676 fprintf (loop_dump_stream, "\n");
7687 /* Verify whether the biv BL appears to be eliminable,
7688 based on the insns in the loop that refer to it.
7690 If ELIMINATE_P is non-zero, actually do the elimination.
7692 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7693 determine whether invariant insns should be placed inside or at the
7694 start of the loop. */
7697 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7698 const struct loop *loop;
7699 struct iv_class *bl;
7701 int threshold, insn_count;
7703 struct loop_ivs *ivs = LOOP_IVS (loop);
7704 rtx reg = bl->biv->dest_reg;
7707 /* Scan all insns in the loop, stopping if we find one that uses the
7708 biv in a way that we cannot eliminate. */
7710 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
7712 enum rtx_code code = GET_CODE (p);
7713 basic_block where_bb = 0;
7714 rtx where_insn = threshold >= insn_count ? 0 : p;
7716 /* If this is a libcall that sets a giv, skip ahead to its end. */
7717 if (GET_RTX_CLASS (code) == 'i')
7719 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7723 rtx last = XEXP (note, 0);
7724 rtx set = single_set (last);
7726 if (set && GET_CODE (SET_DEST (set)) == REG)
7728 unsigned int regno = REGNO (SET_DEST (set));
7730 if (regno < ivs->n_regs
7731 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7732 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7737 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7738 && reg_mentioned_p (reg, PATTERN (p))
7739 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7740 eliminate_p, where_bb, where_insn))
7742 if (loop_dump_stream)
7743 fprintf (loop_dump_stream,
7744 "Cannot eliminate biv %d: biv used in insn %d.\n",
7745 bl->regno, INSN_UID (p));
7752 if (loop_dump_stream)
7753 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7754 bl->regno, eliminate_p ? "was" : "can be");
7761 /* INSN and REFERENCE are instructions in the same insn chain.
7762 Return non-zero if INSN is first. */
7765 loop_insn_first_p (insn, reference)
7766 rtx insn, reference;
7770 for (p = insn, q = reference;;)
7772 /* Start with test for not first so that INSN == REFERENCE yields not
7774 if (q == insn || ! p)
7776 if (p == reference || ! q)
7779 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7780 previous insn, hence the <= comparison below does not work if
7782 if (INSN_UID (p) < max_uid_for_loop
7783 && INSN_UID (q) < max_uid_for_loop
7784 && GET_CODE (p) != NOTE)
7785 return INSN_LUID (p) <= INSN_LUID (q);
7787 if (INSN_UID (p) >= max_uid_for_loop
7788 || GET_CODE (p) == NOTE)
7790 if (INSN_UID (q) >= max_uid_for_loop)
7795 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7796 the offset that we have to take into account due to auto-increment /
7797 div derivation is zero. */
7799 biv_elimination_giv_has_0_offset (biv, giv, insn)
7800 struct induction *biv, *giv;
7803 /* If the giv V had the auto-inc address optimization applied
7804 to it, and INSN occurs between the giv insn and the biv
7805 insn, then we'd have to adjust the value used here.
7806 This is rare, so we don't bother to make this possible. */
7807 if (giv->auto_inc_opt
7808 && ((loop_insn_first_p (giv->insn, insn)
7809 && loop_insn_first_p (insn, biv->insn))
7810 || (loop_insn_first_p (biv->insn, insn)
7811 && loop_insn_first_p (insn, giv->insn))))
7817 /* If BL appears in X (part of the pattern of INSN), see if we can
7818 eliminate its use. If so, return 1. If not, return 0.
7820 If BIV does not appear in X, return 1.
7822 If ELIMINATE_P is non-zero, actually do the elimination.
7823 WHERE_INSN/WHERE_BB indicate where extra insns should be added.
7824 Depending on how many items have been moved out of the loop, it
7825 will either be before INSN (when WHERE_INSN is non-zero) or at the
7826 start of the loop (when WHERE_INSN is zero). */
7829 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where_bb, where_insn)
7830 const struct loop *loop;
7832 struct iv_class *bl;
7834 basic_block where_bb;
7837 enum rtx_code code = GET_CODE (x);
7838 rtx reg = bl->biv->dest_reg;
7839 enum machine_mode mode = GET_MODE (reg);
7840 struct induction *v;
7852 /* If we haven't already been able to do something with this BIV,
7853 we can't eliminate it. */
7859 /* If this sets the BIV, it is not a problem. */
7860 if (SET_DEST (x) == reg)
7863 /* If this is an insn that defines a giv, it is also ok because
7864 it will go away when the giv is reduced. */
7865 for (v = bl->giv; v; v = v->next_iv)
7866 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7870 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7872 /* Can replace with any giv that was reduced and
7873 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7874 Require a constant for MULT_VAL, so we know it's nonzero.
7875 ??? We disable this optimization to avoid potential
7878 for (v = bl->giv; v; v = v->next_iv)
7879 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7880 && v->add_val == const0_rtx
7881 && ! v->ignore && ! v->maybe_dead && v->always_computable
7885 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7891 /* If the giv has the opposite direction of change,
7892 then reverse the comparison. */
7893 if (INTVAL (v->mult_val) < 0)
7894 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7895 const0_rtx, v->new_reg);
7899 /* We can probably test that giv's reduced reg. */
7900 if (validate_change (insn, &SET_SRC (x), new, 0))
7904 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7905 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7906 Require a constant for MULT_VAL, so we know it's nonzero.
7907 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7908 overflow problem. */
7910 for (v = bl->giv; v; v = v->next_iv)
7911 if (GET_CODE (v->mult_val) == CONST_INT
7912 && v->mult_val != const0_rtx
7913 && ! v->ignore && ! v->maybe_dead && v->always_computable
7915 && (GET_CODE (v->add_val) == SYMBOL_REF
7916 || GET_CODE (v->add_val) == LABEL_REF
7917 || GET_CODE (v->add_val) == CONST
7918 || (GET_CODE (v->add_val) == REG
7919 && REG_POINTER (v->add_val))))
7921 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7927 /* If the giv has the opposite direction of change,
7928 then reverse the comparison. */
7929 if (INTVAL (v->mult_val) < 0)
7930 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
7933 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
7934 copy_rtx (v->add_val));
7936 /* Replace biv with the giv's reduced register. */
7937 update_reg_last_use (v->add_val, insn);
7938 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7941 /* Insn doesn't support that constant or invariant. Copy it
7942 into a register (it will be a loop invariant.) */
7943 tem = gen_reg_rtx (GET_MODE (v->new_reg));
7945 loop_insn_emit_before (loop, 0, where_insn,
7947 copy_rtx (v->add_val)));
7949 /* Substitute the new register for its invariant value in
7950 the compare expression. */
7951 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
7952 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7961 case GT: case GE: case GTU: case GEU:
7962 case LT: case LE: case LTU: case LEU:
7963 /* See if either argument is the biv. */
7964 if (XEXP (x, 0) == reg)
7965 arg = XEXP (x, 1), arg_operand = 1;
7966 else if (XEXP (x, 1) == reg)
7967 arg = XEXP (x, 0), arg_operand = 0;
7971 if (CONSTANT_P (arg))
7973 /* First try to replace with any giv that has constant positive
7974 mult_val and constant add_val. We might be able to support
7975 negative mult_val, but it seems complex to do it in general. */
7977 for (v = bl->giv; v; v = v->next_iv)
7978 if (GET_CODE (v->mult_val) == CONST_INT
7979 && INTVAL (v->mult_val) > 0
7980 && (GET_CODE (v->add_val) == SYMBOL_REF
7981 || GET_CODE (v->add_val) == LABEL_REF
7982 || GET_CODE (v->add_val) == CONST
7983 || (GET_CODE (v->add_val) == REG
7984 && REG_POINTER (v->add_val)))
7985 && ! v->ignore && ! v->maybe_dead && v->always_computable
7988 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7994 /* Replace biv with the giv's reduced reg. */
7995 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
7997 /* If all constants are actually constant integers and
7998 the derived constant can be directly placed in the COMPARE,
8000 if (GET_CODE (arg) == CONST_INT
8001 && GET_CODE (v->mult_val) == CONST_INT
8002 && GET_CODE (v->add_val) == CONST_INT)
8004 validate_change (insn, &XEXP (x, arg_operand),
8005 GEN_INT (INTVAL (arg)
8006 * INTVAL (v->mult_val)
8007 + INTVAL (v->add_val)), 1);
8011 /* Otherwise, load it into a register. */
8012 tem = gen_reg_rtx (mode);
8013 loop_iv_add_mult_emit_before (loop, arg,
8014 v->mult_val, v->add_val,
8015 tem, where_bb, where_insn);
8016 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8018 if (apply_change_group ())
8022 /* Look for giv with positive constant mult_val and nonconst add_val.
8023 Insert insns to calculate new compare value.
8024 ??? Turn this off due to possible overflow. */
8026 for (v = bl->giv; v; v = v->next_iv)
8027 if (GET_CODE (v->mult_val) == CONST_INT
8028 && INTVAL (v->mult_val) > 0
8029 && ! v->ignore && ! v->maybe_dead && v->always_computable
8035 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8041 tem = gen_reg_rtx (mode);
8043 /* Replace biv with giv's reduced register. */
8044 validate_change (insn, &XEXP (x, 1 - arg_operand),
8047 /* Compute value to compare against. */
8048 loop_iv_add_mult_emit_before (loop, arg,
8049 v->mult_val, v->add_val,
8050 tem, where_bb, where_insn);
8051 /* Use it in this insn. */
8052 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8053 if (apply_change_group ())
8057 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
8059 if (loop_invariant_p (loop, arg) == 1)
8061 /* Look for giv with constant positive mult_val and nonconst
8062 add_val. Insert insns to compute new compare value.
8063 ??? Turn this off due to possible overflow. */
8065 for (v = bl->giv; v; v = v->next_iv)
8066 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
8067 && ! v->ignore && ! v->maybe_dead && v->always_computable
8073 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8079 tem = gen_reg_rtx (mode);
8081 /* Replace biv with giv's reduced register. */
8082 validate_change (insn, &XEXP (x, 1 - arg_operand),
8085 /* Compute value to compare against. */
8086 loop_iv_add_mult_emit_before (loop, arg,
8087 v->mult_val, v->add_val,
8088 tem, where_bb, where_insn);
8089 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8090 if (apply_change_group ())
8095 /* This code has problems. Basically, you can't know when
8096 seeing if we will eliminate BL, whether a particular giv
8097 of ARG will be reduced. If it isn't going to be reduced,
8098 we can't eliminate BL. We can try forcing it to be reduced,
8099 but that can generate poor code.
8101 The problem is that the benefit of reducing TV, below should
8102 be increased if BL can actually be eliminated, but this means
8103 we might have to do a topological sort of the order in which
8104 we try to process biv. It doesn't seem worthwhile to do
8105 this sort of thing now. */
8108 /* Otherwise the reg compared with had better be a biv. */
8109 if (GET_CODE (arg) != REG
8110 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8113 /* Look for a pair of givs, one for each biv,
8114 with identical coefficients. */
8115 for (v = bl->giv; v; v = v->next_iv)
8117 struct induction *tv;
8119 if (v->ignore || v->maybe_dead || v->mode != mode)
8122 for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
8124 if (! tv->ignore && ! tv->maybe_dead
8125 && rtx_equal_p (tv->mult_val, v->mult_val)
8126 && rtx_equal_p (tv->add_val, v->add_val)
8127 && tv->mode == mode)
8129 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8135 /* Replace biv with its giv's reduced reg. */
8136 XEXP (x, 1 - arg_operand) = v->new_reg;
8137 /* Replace other operand with the other giv's
8139 XEXP (x, arg_operand) = tv->new_reg;
8146 /* If we get here, the biv can't be eliminated. */
8150 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8151 biv is used in it, since it will be replaced. */
8152 for (v = bl->giv; v; v = v->next_iv)
8153 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8161 /* See if any subexpression fails elimination. */
8162 fmt = GET_RTX_FORMAT (code);
8163 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8168 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8169 eliminate_p, where_bb, where_insn))
8174 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8175 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8176 eliminate_p, where_bb, where_insn))
8185 /* Return nonzero if the last use of REG
8186 is in an insn following INSN in the same basic block. */
8189 last_use_this_basic_block (reg, insn)
8195 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8198 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8204 /* Called via `note_stores' to record the initial value of a biv. Here we
8205 just record the location of the set and process it later. */
8208 record_initial (dest, set, data)
8211 void *data ATTRIBUTE_UNUSED;
8213 struct loop_ivs *ivs = (struct loop_ivs *) data;
8214 struct iv_class *bl;
8216 if (GET_CODE (dest) != REG
8217 || REGNO (dest) >= ivs->n_regs
8218 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8221 bl = REG_IV_CLASS (ivs, REGNO (dest));
8223 /* If this is the first set found, record it. */
8224 if (bl->init_insn == 0)
8226 bl->init_insn = note_insn;
8231 /* If any of the registers in X are "old" and currently have a last use earlier
8232 than INSN, update them to have a last use of INSN. Their actual last use
8233 will be the previous insn but it will not have a valid uid_luid so we can't
8234 use it. X must be a source expression only. */
8237 update_reg_last_use (x, insn)
8241 /* Check for the case where INSN does not have a valid luid. In this case,
8242 there is no need to modify the regno_last_uid, as this can only happen
8243 when code is inserted after the loop_end to set a pseudo's final value,
8244 and hence this insn will never be the last use of x.
8245 ???? This comment is not correct. See for example loop_givs_reduce.
8246 This may insert an insn before another new insn. */
8247 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8248 && INSN_UID (insn) < max_uid_for_loop
8249 && REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
8251 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8256 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8257 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8260 update_reg_last_use (XEXP (x, i), insn);
8261 else if (fmt[i] == 'E')
8262 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8263 update_reg_last_use (XVECEXP (x, i, j), insn);
8268 /* Given an insn INSN and condition COND, return the condition in a
8269 canonical form to simplify testing by callers. Specifically:
8271 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8272 (2) Both operands will be machine operands; (cc0) will have been replaced.
8273 (3) If an operand is a constant, it will be the second operand.
8274 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8275 for GE, GEU, and LEU.
8277 If the condition cannot be understood, or is an inequality floating-point
8278 comparison which needs to be reversed, 0 will be returned.
8280 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8282 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8283 insn used in locating the condition was found. If a replacement test
8284 of the condition is desired, it should be placed in front of that
8285 insn and we will be sure that the inputs are still valid.
8287 If WANT_REG is non-zero, we wish the condition to be relative to that
8288 register, if possible. Therefore, do not canonicalize the condition
8292 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8304 int reverse_code = 0;
8305 int did_reverse_condition = 0;
8306 enum machine_mode mode;
8308 code = GET_CODE (cond);
8309 mode = GET_MODE (cond);
8310 op0 = XEXP (cond, 0);
8311 op1 = XEXP (cond, 1);
8315 code = reverse_condition (code);
8316 did_reverse_condition ^= 1;
8322 /* If we are comparing a register with zero, see if the register is set
8323 in the previous insn to a COMPARE or a comparison operation. Perform
8324 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8327 while (GET_RTX_CLASS (code) == '<'
8328 && op1 == CONST0_RTX (GET_MODE (op0))
8331 /* Set non-zero when we find something of interest. */
8335 /* If comparison with cc0, import actual comparison from compare
8339 if ((prev = prev_nonnote_insn (prev)) == 0
8340 || GET_CODE (prev) != INSN
8341 || (set = single_set (prev)) == 0
8342 || SET_DEST (set) != cc0_rtx)
8345 op0 = SET_SRC (set);
8346 op1 = CONST0_RTX (GET_MODE (op0));
8352 /* If this is a COMPARE, pick up the two things being compared. */
8353 if (GET_CODE (op0) == COMPARE)
8355 op1 = XEXP (op0, 1);
8356 op0 = XEXP (op0, 0);
8359 else if (GET_CODE (op0) != REG)
8362 /* Go back to the previous insn. Stop if it is not an INSN. We also
8363 stop if it isn't a single set or if it has a REG_INC note because
8364 we don't want to bother dealing with it. */
8366 if ((prev = prev_nonnote_insn (prev)) == 0
8367 || GET_CODE (prev) != INSN
8368 || FIND_REG_INC_NOTE (prev, 0)
8369 || (set = single_set (prev)) == 0)
8372 /* If this is setting OP0, get what it sets it to if it looks
8374 if (rtx_equal_p (SET_DEST (set), op0))
8376 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8378 /* ??? We may not combine comparisons done in a CCmode with
8379 comparisons not done in a CCmode. This is to aid targets
8380 like Alpha that have an IEEE compliant EQ instruction, and
8381 a non-IEEE compliant BEQ instruction. The use of CCmode is
8382 actually artificial, simply to prevent the combination, but
8383 should not affect other platforms.
8385 However, we must allow VOIDmode comparisons to match either
8386 CCmode or non-CCmode comparison, because some ports have
8387 modeless comparisons inside branch patterns.
8389 ??? This mode check should perhaps look more like the mode check
8390 in simplify_comparison in combine. */
8392 if ((GET_CODE (SET_SRC (set)) == COMPARE
8395 && GET_MODE_CLASS (inner_mode) == MODE_INT
8396 && (GET_MODE_BITSIZE (inner_mode)
8397 <= HOST_BITS_PER_WIDE_INT)
8398 && (STORE_FLAG_VALUE
8399 & ((HOST_WIDE_INT) 1
8400 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8401 #ifdef FLOAT_STORE_FLAG_VALUE
8403 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8404 && (REAL_VALUE_NEGATIVE
8405 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8408 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8409 && (((GET_MODE_CLASS (mode) == MODE_CC)
8410 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8411 || mode == VOIDmode || inner_mode == VOIDmode))
8413 else if (((code == EQ
8415 && (GET_MODE_BITSIZE (inner_mode)
8416 <= HOST_BITS_PER_WIDE_INT)
8417 && GET_MODE_CLASS (inner_mode) == MODE_INT
8418 && (STORE_FLAG_VALUE
8419 & ((HOST_WIDE_INT) 1
8420 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8421 #ifdef FLOAT_STORE_FLAG_VALUE
8423 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8424 && (REAL_VALUE_NEGATIVE
8425 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8428 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8429 && (((GET_MODE_CLASS (mode) == MODE_CC)
8430 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8431 || mode == VOIDmode || inner_mode == VOIDmode))
8434 /* We might have reversed a LT to get a GE here. But this wasn't
8435 actually the comparison of data, so we don't flag that we
8436 have had to reverse the condition. */
8437 did_reverse_condition ^= 1;
8445 else if (reg_set_p (op0, prev))
8446 /* If this sets OP0, but not directly, we have to give up. */
8451 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8452 code = GET_CODE (x);
8455 code = reverse_condition (code);
8456 if (code == UNKNOWN)
8458 did_reverse_condition ^= 1;
8462 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8468 /* If constant is first, put it last. */
8469 if (CONSTANT_P (op0))
8470 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8472 /* If OP0 is the result of a comparison, we weren't able to find what
8473 was really being compared, so fail. */
8474 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8477 /* Canonicalize any ordered comparison with integers involving equality
8478 if we can do computations in the relevant mode and we do not
8481 if (GET_CODE (op1) == CONST_INT
8482 && GET_MODE (op0) != VOIDmode
8483 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8485 HOST_WIDE_INT const_val = INTVAL (op1);
8486 unsigned HOST_WIDE_INT uconst_val = const_val;
8487 unsigned HOST_WIDE_INT max_val
8488 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8493 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8494 code = LT, op1 = GEN_INT (const_val + 1);
8497 /* When cross-compiling, const_val might be sign-extended from
8498 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8500 if ((HOST_WIDE_INT) (const_val & max_val)
8501 != (((HOST_WIDE_INT) 1
8502 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8503 code = GT, op1 = GEN_INT (const_val - 1);
8507 if (uconst_val < max_val)
8508 code = LTU, op1 = GEN_INT (uconst_val + 1);
8512 if (uconst_val != 0)
8513 code = GTU, op1 = GEN_INT (uconst_val - 1);
8521 /* If this was floating-point and we reversed anything other than an
8522 EQ or NE or (UN)ORDERED, return zero. */
8523 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8524 && did_reverse_condition
8525 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8527 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8531 /* Never return CC0; return zero instead. */
8536 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8539 /* Given a jump insn JUMP, return the condition that will cause it to branch
8540 to its JUMP_LABEL. If the condition cannot be understood, or is an
8541 inequality floating-point comparison which needs to be reversed, 0 will
8544 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8545 insn used in locating the condition was found. If a replacement test
8546 of the condition is desired, it should be placed in front of that
8547 insn and we will be sure that the inputs are still valid. */
8550 get_condition (jump, earliest)
8558 /* If this is not a standard conditional jump, we can't parse it. */
8559 if (GET_CODE (jump) != JUMP_INSN
8560 || ! any_condjump_p (jump))
8562 set = pc_set (jump);
8564 cond = XEXP (SET_SRC (set), 0);
8566 /* If this branches to JUMP_LABEL when the condition is false, reverse
8569 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8570 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8572 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8575 /* Similar to above routine, except that we also put an invariant last
8576 unless both operands are invariants. */
8579 get_condition_for_loop (loop, x)
8580 const struct loop *loop;
8583 rtx comparison = get_condition (x, NULL_PTR);
8586 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8587 || loop_invariant_p (loop, XEXP (comparison, 1)))
8590 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8591 XEXP (comparison, 1), XEXP (comparison, 0));
8594 /* Scan the function and determine whether it has indirect (computed) jumps.
8596 This is taken mostly from flow.c; similar code exists elsewhere
8597 in the compiler. It may be useful to put this into rtlanal.c. */
8599 indirect_jump_in_function_p (start)
8604 for (insn = start; insn; insn = NEXT_INSN (insn))
8605 if (computed_jump_p (insn))
8611 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8612 documentation for LOOP_MEMS for the definition of `appropriate'.
8613 This function is called from prescan_loop via for_each_rtx. */
8616 insert_loop_mem (mem, data)
8618 void *data ATTRIBUTE_UNUSED;
8620 struct loop_info *loop_info = data;
8627 switch (GET_CODE (m))
8633 /* We're not interested in MEMs that are only clobbered. */
8637 /* We're not interested in the MEM associated with a
8638 CONST_DOUBLE, so there's no need to traverse into this. */
8642 /* We're not interested in any MEMs that only appear in notes. */
8646 /* This is not a MEM. */
8650 /* See if we've already seen this MEM. */
8651 for (i = 0; i < loop_info->mems_idx; ++i)
8652 if (rtx_equal_p (m, loop_info->mems[i].mem))
8654 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8655 /* The modes of the two memory accesses are different. If
8656 this happens, something tricky is going on, and we just
8657 don't optimize accesses to this MEM. */
8658 loop_info->mems[i].optimize = 0;
8663 /* Resize the array, if necessary. */
8664 if (loop_info->mems_idx == loop_info->mems_allocated)
8666 if (loop_info->mems_allocated != 0)
8667 loop_info->mems_allocated *= 2;
8669 loop_info->mems_allocated = 32;
8671 loop_info->mems = (loop_mem_info *)
8672 xrealloc (loop_info->mems,
8673 loop_info->mems_allocated * sizeof (loop_mem_info));
8676 /* Actually insert the MEM. */
8677 loop_info->mems[loop_info->mems_idx].mem = m;
8678 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8679 because we can't put it in a register. We still store it in the
8680 table, though, so that if we see the same address later, but in a
8681 non-BLK mode, we'll not think we can optimize it at that point. */
8682 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8683 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8684 ++loop_info->mems_idx;
8690 /* Allocate REGS->ARRAY or reallocate it if it is too small.
8692 Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
8693 register that is modified by an insn between FROM and TO. If the
8694 value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
8695 more, stop incrementing it, to avoid overflow.
8697 Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
8698 register I is used, if it is only used once. Otherwise, it is set
8699 to 0 (for no uses) or const0_rtx for more than one use. This
8700 parameter may be zero, in which case this processing is not done.
8702 Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
8703 optimize register I.
8705 Store in *COUNT_PTR the number of actual instructions
8706 in the loop. We use this to decide what is worth moving out. */
8709 loop_regs_scan (loop, extra_size, count_ptr)
8710 const struct loop *loop;
8714 struct loop_regs *regs = LOOP_REGS (loop);
8716 /* last_set[n] is nonzero iff reg n has been set in the current
8717 basic block. In that case, it is the insn that last set reg n. */
8723 old_nregs = regs->num;
8724 regs->num = max_reg_num ();
8726 /* Grow the regs array if not allocated or too small. */
8727 if (regs->num >= regs->size)
8729 regs->size = regs->num + extra_size;
8731 regs->array = (struct loop_reg *)
8732 xrealloc (regs->array, regs->size * sizeof (*regs->array));
8734 /* Zero the new elements. */
8735 memset (regs->array + old_nregs, 0,
8736 (regs->size - old_nregs) * sizeof (*regs->array));
8739 /* Clear previously scanned fields but do not clear n_times_set. */
8740 for (i = 0; i < old_nregs; i++)
8742 regs->array[i].set_in_loop = 0;
8743 regs->array[i].may_not_optimize = 0;
8744 regs->array[i].single_usage = NULL_RTX;
8747 last_set = (rtx *) xcalloc (regs->num, sizeof (rtx));
8749 /* Scan the loop, recording register usage. */
8750 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
8751 insn = NEXT_INSN (insn))
8757 /* Record registers that have exactly one use. */
8758 find_single_use_in_loop (regs, insn, PATTERN (insn));
8760 /* Include uses in REG_EQUAL notes. */
8761 if (REG_NOTES (insn))
8762 find_single_use_in_loop (regs, insn, REG_NOTES (insn));
8764 if (GET_CODE (PATTERN (insn)) == SET
8765 || GET_CODE (PATTERN (insn)) == CLOBBER)
8766 count_one_set (regs, insn, PATTERN (insn), last_set);
8767 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
8770 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
8771 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
8776 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
8777 memset (last_set, 0, regs->num * sizeof (rtx));
8780 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8782 regs->array[i].may_not_optimize = 1;
8783 regs->array[i].set_in_loop = 1;
8786 #ifdef AVOID_CCMODE_COPIES
8787 /* Don't try to move insns which set CC registers if we should not
8788 create CCmode register copies. */
8789 for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8790 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8791 regs->array[i].may_not_optimize = 1;
8794 /* Set regs->array[I].n_times_set for the new registers. */
8795 for (i = old_nregs; i < regs->num; i++)
8796 regs->array[i].n_times_set = regs->array[i].set_in_loop;
8803 /* Move MEMs into registers for the duration of the loop. */
8807 const struct loop *loop;
8809 struct loop_info *loop_info = LOOP_INFO (loop);
8810 struct loop_regs *regs = LOOP_REGS (loop);
8811 int maybe_never = 0;
8814 rtx label = NULL_RTX;
8816 /* Nonzero if the next instruction may never be executed. */
8817 int next_maybe_never = 0;
8818 int last_max_reg = max_reg_num ();
8820 if (loop_info->mems_idx == 0)
8823 /* We cannot use next_label here because it skips over normal insns. */
8824 end_label = next_nonnote_insn (loop->end);
8825 if (end_label && GET_CODE (end_label) != CODE_LABEL)
8826 end_label = NULL_RTX;
8828 /* Check to see if it's possible that some instructions in the loop are
8829 never executed. Also check if there is a goto out of the loop other
8830 than right after the end of the loop. */
8831 for (p = next_insn_in_loop (loop, loop->scan_start);
8832 p != NULL_RTX && ! maybe_never;
8833 p = next_insn_in_loop (loop, p))
8835 if (GET_CODE (p) == CODE_LABEL)
8837 else if (GET_CODE (p) == JUMP_INSN
8838 /* If we enter the loop in the middle, and scan
8839 around to the beginning, don't set maybe_never
8840 for that. This must be an unconditional jump,
8841 otherwise the code at the top of the loop might
8842 never be executed. Unconditional jumps are
8843 followed a by barrier then loop end. */
8844 && ! (GET_CODE (p) == JUMP_INSN
8845 && JUMP_LABEL (p) == loop->top
8846 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8847 && any_uncondjump_p (p)))
8849 /* If this is a jump outside of the loop but not right
8850 after the end of the loop, we would have to emit new fixup
8851 sequences for each such label. */
8852 if (JUMP_LABEL (p) != end_label
8853 && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
8854 || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
8855 || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
8858 if (!any_condjump_p (p))
8859 /* Something complicated. */
8862 /* If there are any more instructions in the loop, they
8863 might not be reached. */
8864 next_maybe_never = 1;
8866 else if (next_maybe_never)
8870 /* Find start of the extended basic block that enters the loop. */
8871 for (p = loop->start;
8872 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8878 /* Build table of mems that get set to constant values before the
8880 for (; p != loop->start; p = NEXT_INSN (p))
8881 cselib_process_insn (p);
8883 /* Actually move the MEMs. */
8884 for (i = 0; i < loop_info->mems_idx; ++i)
8886 regset_head load_copies;
8887 regset_head store_copies;
8890 rtx mem = loop_info->mems[i].mem;
8893 if (MEM_VOLATILE_P (mem)
8894 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8895 /* There's no telling whether or not MEM is modified. */
8896 loop_info->mems[i].optimize = 0;
8898 /* Go through the MEMs written to in the loop to see if this
8899 one is aliased by one of them. */
8900 mem_list_entry = loop_info->store_mems;
8901 while (mem_list_entry)
8903 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8905 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8908 /* MEM is indeed aliased by this store. */
8909 loop_info->mems[i].optimize = 0;
8912 mem_list_entry = XEXP (mem_list_entry, 1);
8915 if (flag_float_store && written
8916 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8917 loop_info->mems[i].optimize = 0;
8919 /* If this MEM is written to, we must be sure that there
8920 are no reads from another MEM that aliases this one. */
8921 if (loop_info->mems[i].optimize && written)
8925 for (j = 0; j < loop_info->mems_idx; ++j)
8929 else if (true_dependence (mem,
8931 loop_info->mems[j].mem,
8934 /* It's not safe to hoist loop_info->mems[i] out of
8935 the loop because writes to it might not be
8936 seen by reads from loop_info->mems[j]. */
8937 loop_info->mems[i].optimize = 0;
8943 if (maybe_never && may_trap_p (mem))
8944 /* We can't access the MEM outside the loop; it might
8945 cause a trap that wouldn't have happened otherwise. */
8946 loop_info->mems[i].optimize = 0;
8948 if (!loop_info->mems[i].optimize)
8949 /* We thought we were going to lift this MEM out of the
8950 loop, but later discovered that we could not. */
8953 INIT_REG_SET (&load_copies);
8954 INIT_REG_SET (&store_copies);
8956 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8957 order to keep scan_loop from moving stores to this MEM
8958 out of the loop just because this REG is neither a
8959 user-variable nor used in the loop test. */
8960 reg = gen_reg_rtx (GET_MODE (mem));
8961 REG_USERVAR_P (reg) = 1;
8962 loop_info->mems[i].reg = reg;
8964 /* Now, replace all references to the MEM with the
8965 corresponding pesudos. */
8967 for (p = next_insn_in_loop (loop, loop->scan_start);
8969 p = next_insn_in_loop (loop, p))
8975 set = single_set (p);
8977 /* See if this copies the mem into a register that isn't
8978 modified afterwards. We'll try to do copy propagation
8979 a little further on. */
8981 /* @@@ This test is _way_ too conservative. */
8983 && GET_CODE (SET_DEST (set)) == REG
8984 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
8985 && REGNO (SET_DEST (set)) < last_max_reg
8986 && regs->array[REGNO (SET_DEST (set))].n_times_set == 1
8987 && rtx_equal_p (SET_SRC (set), mem))
8988 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
8990 /* See if this copies the mem from a register that isn't
8991 modified afterwards. We'll try to remove the
8992 redundant copy later on by doing a little register
8993 renaming and copy propagation. This will help
8994 to untangle things for the BIV detection code. */
8997 && GET_CODE (SET_SRC (set)) == REG
8998 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
8999 && REGNO (SET_SRC (set)) < last_max_reg
9000 && regs->array[REGNO (SET_SRC (set))].n_times_set == 1
9001 && rtx_equal_p (SET_DEST (set), mem))
9002 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
9004 /* Replace the memory reference with the shadow register. */
9005 replace_loop_mems (p, loop_info->mems[i].mem,
9006 loop_info->mems[i].reg);
9009 if (GET_CODE (p) == CODE_LABEL
9010 || GET_CODE (p) == JUMP_INSN)
9014 if (! apply_change_group ())
9015 /* We couldn't replace all occurrences of the MEM. */
9016 loop_info->mems[i].optimize = 0;
9019 /* Load the memory immediately before LOOP->START, which is
9020 the NOTE_LOOP_BEG. */
9021 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
9025 struct elt_loc_list *const_equiv = 0;
9029 struct elt_loc_list *equiv;
9030 struct elt_loc_list *best_equiv = 0;
9031 for (equiv = e->locs; equiv; equiv = equiv->next)
9033 if (CONSTANT_P (equiv->loc))
9034 const_equiv = equiv;
9035 else if (GET_CODE (equiv->loc) == REG
9036 /* Extending hard register lifetimes cuases crash
9037 on SRC targets. Doing so on non-SRC is
9038 probably also not good idea, since we most
9039 probably have pseudoregister equivalence as
9041 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
9044 /* Use the constant equivalence if that is cheap enough. */
9046 best_equiv = const_equiv;
9047 else if (const_equiv
9048 && (rtx_cost (const_equiv->loc, SET)
9049 <= rtx_cost (best_equiv->loc, SET)))
9051 best_equiv = const_equiv;
9055 /* If best_equiv is nonzero, we know that MEM is set to a
9056 constant or register before the loop. We will use this
9057 knowledge to initialize the shadow register with that
9058 constant or reg rather than by loading from MEM. */
9060 best = copy_rtx (best_equiv->loc);
9062 set = gen_move_insn (reg, best);
9063 set = loop_insn_hoist (loop, set);
9065 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
9066 copy_rtx (const_equiv->loc),
9071 if (label == NULL_RTX)
9073 label = gen_label_rtx ();
9074 emit_label_after (label, loop->end);
9077 /* Store the memory immediately after END, which is
9078 the NOTE_LOOP_END. */
9079 set = gen_move_insn (copy_rtx (mem), reg);
9080 loop_insn_emit_after (loop, 0, label, set);
9083 if (loop_dump_stream)
9085 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
9086 REGNO (reg), (written ? "r/w" : "r/o"));
9087 print_rtl (loop_dump_stream, mem);
9088 fputc ('\n', loop_dump_stream);
9091 /* Attempt a bit of copy propagation. This helps untangle the
9092 data flow, and enables {basic,general}_induction_var to find
9094 EXECUTE_IF_SET_IN_REG_SET
9095 (&load_copies, FIRST_PSEUDO_REGISTER, j,
9097 try_copy_prop (loop, reg, j);
9099 CLEAR_REG_SET (&load_copies);
9101 EXECUTE_IF_SET_IN_REG_SET
9102 (&store_copies, FIRST_PSEUDO_REGISTER, j,
9104 try_swap_copy_prop (loop, reg, j);
9106 CLEAR_REG_SET (&store_copies);
9110 if (label != NULL_RTX && end_label != NULL_RTX)
9112 /* Now, we need to replace all references to the previous exit
9113 label with the new one. */
9118 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
9120 for_each_rtx (&p, replace_label, &rr);
9122 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
9123 field. This is not handled by for_each_rtx because it doesn't
9124 handle unprinted ('0') fields. We need to update JUMP_LABEL
9125 because the immediately following unroll pass will use it.
9126 replace_label would not work anyways, because that only handles
9128 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
9129 JUMP_LABEL (p) = label;
9136 /* For communication between note_reg_stored and its caller. */
9137 struct note_reg_stored_arg
9143 /* Called via note_stores, record in SET_SEEN whether X, which is written,
9146 note_reg_stored (x, setter, arg)
9147 rtx x, setter ATTRIBUTE_UNUSED;
9150 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9155 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9156 There must be exactly one insn that sets this pseudo; it will be
9157 deleted if all replacements succeed and we can prove that the register
9158 is not used after the loop. */
9161 try_copy_prop (loop, replacement, regno)
9162 const struct loop *loop;
9166 /* This is the reg that we are copying from. */
9167 rtx reg_rtx = regno_reg_rtx[regno];
9170 /* These help keep track of whether we replaced all uses of the reg. */
9171 int replaced_last = 0;
9172 int store_is_first = 0;
9174 for (insn = next_insn_in_loop (loop, loop->scan_start);
9176 insn = next_insn_in_loop (loop, insn))
9180 /* Only substitute within one extended basic block from the initializing
9182 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9185 if (! INSN_P (insn))
9188 /* Is this the initializing insn? */
9189 set = single_set (insn);
9191 && GET_CODE (SET_DEST (set)) == REG
9192 && REGNO (SET_DEST (set)) == regno)
9198 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9202 /* Only substitute after seeing the initializing insn. */
9203 if (init_insn && insn != init_insn)
9205 struct note_reg_stored_arg arg;
9207 replace_loop_regs (insn, reg_rtx, replacement);
9208 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9211 /* Stop replacing when REPLACEMENT is modified. */
9212 arg.reg = replacement;
9214 note_stores (PATTERN (insn), note_reg_stored, &arg);
9221 if (apply_change_group ())
9223 if (loop_dump_stream)
9224 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9225 if (store_is_first && replaced_last)
9227 PUT_CODE (init_insn, NOTE);
9228 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9229 if (loop_dump_stream)
9230 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9231 INSN_UID (init_insn));
9233 if (loop_dump_stream)
9234 fprintf (loop_dump_stream, ".\n");
9238 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9239 loop LOOP if the order of the sets of these registers can be
9240 swapped. There must be exactly one insn within the loop that sets
9241 this pseudo followed immediately by a move insn that sets
9242 REPLACEMENT with REGNO. */
9244 try_swap_copy_prop (loop, replacement, regno)
9245 const struct loop *loop;
9251 unsigned int new_regno;
9253 new_regno = REGNO (replacement);
9255 for (insn = next_insn_in_loop (loop, loop->scan_start);
9257 insn = next_insn_in_loop (loop, insn))
9259 /* Search for the insn that copies REGNO to NEW_REGNO? */
9260 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9261 && (set = single_set (insn))
9262 && GET_CODE (SET_DEST (set)) == REG
9263 && REGNO (SET_DEST (set)) == new_regno
9264 && GET_CODE (SET_SRC (set)) == REG
9265 && REGNO (SET_SRC (set)) == regno)
9269 if (insn != NULL_RTX)
9274 /* Some DEF-USE info would come in handy here to make this
9275 function more general. For now, just check the previous insn
9276 which is the most likely candidate for setting REGNO. */
9278 prev_insn = PREV_INSN (insn);
9280 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9281 && (prev_set = single_set (prev_insn))
9282 && GET_CODE (SET_DEST (prev_set)) == REG
9283 && REGNO (SET_DEST (prev_set)) == regno)
9286 (set (reg regno) (expr))
9287 (set (reg new_regno) (reg regno))
9289 so try converting this to:
9290 (set (reg new_regno) (expr))
9291 (set (reg regno) (reg new_regno))
9293 The former construct is often generated when a global
9294 variable used for an induction variable is shadowed by a
9295 register (NEW_REGNO). The latter construct improves the
9296 chances of GIV replacement and BIV elimination. */
9298 validate_change (prev_insn, &SET_DEST (prev_set),
9300 validate_change (insn, &SET_DEST (set),
9302 validate_change (insn, &SET_SRC (set),
9305 if (apply_change_group ())
9307 if (loop_dump_stream)
9308 fprintf (loop_dump_stream,
9309 " Swapped set of reg %d at %d with reg %d at %d.\n",
9310 regno, INSN_UID (insn),
9311 new_regno, INSN_UID (prev_insn));
9313 /* Update first use of REGNO. */
9314 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9315 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9317 /* Now perform copy propagation to hopefully
9318 remove all uses of REGNO within the loop. */
9319 try_copy_prop (loop, replacement, regno);
9325 /* Replace MEM with its associated pseudo register. This function is
9326 called from load_mems via for_each_rtx. DATA is actually a pointer
9327 to a structure describing the instruction currently being scanned
9328 and the MEM we are currently replacing. */
9331 replace_loop_mem (mem, data)
9335 loop_replace_args *args = (loop_replace_args *) data;
9341 switch (GET_CODE (m))
9347 /* We're not interested in the MEM associated with a
9348 CONST_DOUBLE, so there's no need to traverse into one. */
9352 /* This is not a MEM. */
9356 if (!rtx_equal_p (args->match, m))
9357 /* This is not the MEM we are currently replacing. */
9360 /* Actually replace the MEM. */
9361 validate_change (args->insn, mem, args->replacement, 1);
9367 replace_loop_mems (insn, mem, reg)
9372 loop_replace_args args;
9376 args.replacement = reg;
9378 for_each_rtx (&insn, replace_loop_mem, &args);
9381 /* Replace one register with another. Called through for_each_rtx; PX points
9382 to the rtx being scanned. DATA is actually a pointer to
9383 a structure of arguments. */
9386 replace_loop_reg (px, data)
9391 loop_replace_args *args = (loop_replace_args *) data;
9396 if (x == args->match)
9397 validate_change (args->insn, px, args->replacement, 1);
9403 replace_loop_regs (insn, reg, replacement)
9408 loop_replace_args args;
9412 args.replacement = replacement;
9414 for_each_rtx (&insn, replace_loop_reg, &args);
9417 /* Replace occurrences of the old exit label for the loop with the new
9418 one. DATA is an rtx_pair containing the old and new labels,
9422 replace_label (x, data)
9427 rtx old_label = ((rtx_pair *) data)->r1;
9428 rtx new_label = ((rtx_pair *) data)->r2;
9433 if (GET_CODE (l) != LABEL_REF)
9436 if (XEXP (l, 0) != old_label)
9439 XEXP (l, 0) = new_label;
9440 ++LABEL_NUSES (new_label);
9441 --LABEL_NUSES (old_label);
9446 /* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB
9447 (ignored in the interim). */
9450 loop_insn_emit_after (loop, where_bb, where_insn, pattern)
9451 const struct loop *loop ATTRIBUTE_UNUSED;
9452 basic_block where_bb ATTRIBUTE_UNUSED;
9456 return emit_insn_after (pattern, where_insn);
9460 /* If WHERE_INSN is non-zero emit insn for PATTERN before WHERE_INSN
9461 in basic block WHERE_BB (ignored in the interim) within the loop
9462 otherwise hoist PATTERN into the loop pre-header. */
9465 loop_insn_emit_before (loop, where_bb, where_insn, pattern)
9466 const struct loop *loop;
9467 basic_block where_bb ATTRIBUTE_UNUSED;
9472 return loop_insn_hoist (loop, pattern);
9473 return emit_insn_before (pattern, where_insn);
9477 /* Emit call insn for PATTERN before WHERE_INSN in basic block
9478 WHERE_BB (ignored in the interim) within the loop. */
9481 loop_call_insn_emit_before (loop, where_bb, where_insn, pattern)
9482 const struct loop *loop ATTRIBUTE_UNUSED;
9483 basic_block where_bb ATTRIBUTE_UNUSED;
9487 return emit_call_insn_before (pattern, where_insn);
9491 /* Hoist insn for PATTERN into the loop pre-header. */
9494 loop_insn_hoist (loop, pattern)
9495 const struct loop *loop;
9498 return loop_insn_emit_before (loop, 0, loop->start, pattern);
9502 /* Hoist call insn for PATTERN into the loop pre-header. */
9505 loop_call_insn_hoist (loop, pattern)
9506 const struct loop *loop;
9509 return loop_call_insn_emit_before (loop, 0, loop->start, pattern);
9513 /* Sink insn for PATTERN after the loop end. */
9516 loop_insn_sink (loop, pattern)
9517 const struct loop *loop;
9520 return loop_insn_emit_before (loop, 0, loop->sink, pattern);
9524 /* If the loop has multiple exits, emit insn for PATTERN before the
9525 loop to ensure that it will always be executed no matter how the
9526 loop exits. Otherwise, emit the insn for PATTERN after the loop,
9527 since this is slightly more efficient. */
9530 loop_insn_sink_or_swim (loop, pattern)
9531 const struct loop *loop;
9534 if (loop->exit_count)
9535 return loop_insn_hoist (loop, pattern);
9537 return loop_insn_sink (loop, pattern);
9541 loop_ivs_dump (loop, file, verbose)
9542 const struct loop *loop;
9546 struct iv_class *bl;
9549 if (! loop || ! file)
9552 for (bl = LOOP_IVS (loop)->list; bl; bl = bl->next)
9555 fprintf (file, "Loop %d: %d IV classes\n", loop->num, iv_num);
9557 for (bl = LOOP_IVS (loop)->list; bl; bl = bl->next)
9559 loop_iv_class_dump (bl, file, verbose);
9566 loop_iv_class_dump (bl, file, verbose)
9567 const struct iv_class *bl;
9569 int verbose ATTRIBUTE_UNUSED;
9571 struct induction *v;
9578 fprintf (file, "IV class for reg %d, benefit %d\n",
9579 bl->regno, bl->total_benefit);
9581 fprintf (file, " Init insn %d", INSN_UID (bl->init_insn));
9582 if (bl->initial_value)
9584 fprintf (file, ", init val: ");
9585 print_simple_rtl (file, bl->initial_value);
9587 if (bl->initial_test)
9589 fprintf (file, ", init test: ");
9590 print_simple_rtl (file, bl->initial_test);
9594 if (bl->final_value)
9596 fprintf (file, " Final val: ");
9597 print_simple_rtl (file, bl->final_value);
9601 if ((incr = biv_total_increment (bl)))
9603 fprintf (file, " Total increment: ");
9604 print_simple_rtl (file, incr);
9608 /* List the increments. */
9609 for (i = 0, v = bl->biv; v; v = v->next_iv, i++)
9611 fprintf (file, " Inc%d: insn %d, incr: ", i, INSN_UID (v->insn));
9612 print_simple_rtl (file, v->add_val);
9616 /* List the givs. */
9617 for (i = 0, v = bl->giv; v; v = v->next_iv, i++)
9619 fprintf (file, " Giv%d: insn %d, benefit %d, ",
9620 i, INSN_UID (v->insn), v->benefit);
9621 if (v->giv_type == DEST_ADDR)
9622 print_simple_rtl (file, v->mem);
9624 print_simple_rtl (file, single_set (v->insn));
9631 loop_biv_dump (v, file, verbose)
9632 const struct induction *v;
9641 REGNO (v->dest_reg), INSN_UID (v->insn));
9642 fprintf (file, " const ");
9643 print_simple_rtl (file, v->add_val);
9645 if (verbose && v->final_value)
9648 fprintf (file, " final ");
9649 print_simple_rtl (file, v->final_value);
9657 loop_giv_dump (v, file, verbose)
9658 const struct induction *v;
9665 if (v->giv_type == DEST_REG)
9666 fprintf (file, "Giv %d: insn %d",
9667 REGNO (v->dest_reg), INSN_UID (v->insn));
9669 fprintf (file, "Dest address: insn %d",
9670 INSN_UID (v->insn));
9672 fprintf (file, " src reg %d benefit %d",
9673 REGNO (v->src_reg), v->benefit);
9674 fprintf (file, " lifetime %d",
9678 fprintf (file, " replaceable");
9680 if (v->no_const_addval)
9681 fprintf (file, " ncav");
9683 if (v->ext_dependant)
9685 switch (GET_CODE (v->ext_dependant))
9688 fprintf (file, " ext se");
9691 fprintf (file, " ext ze");
9694 fprintf (file, " ext tr");
9702 fprintf (file, " mult ");
9703 print_simple_rtl (file, v->mult_val);
9706 fprintf (file, " add ");
9707 print_simple_rtl (file, v->add_val);
9709 if (verbose && v->final_value)
9712 fprintf (file, " final ");
9713 print_simple_rtl (file, v->final_value);
9722 const struct loop *loop;
9724 loop_ivs_dump (loop, stderr, 1);
9730 const struct iv_class *bl;
9732 loop_iv_class_dump (bl, stderr, 1);
9738 const struct induction *v;
9740 loop_biv_dump (v, stderr, 1);
9746 const struct induction *v;
9748 loop_giv_dump (v, stderr, 1);
9752 #define LOOP_BLOCK_NUM_1(INSN) \
9753 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9755 /* The notes do not have an assigned block, so look at the next insn. */
9756 #define LOOP_BLOCK_NUM(INSN) \
9757 ((INSN) ? (GET_CODE (INSN) == NOTE \
9758 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9759 : LOOP_BLOCK_NUM_1 (INSN)) \
9762 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9765 loop_dump_aux (loop, file, verbose)
9766 const struct loop *loop;
9768 int verbose ATTRIBUTE_UNUSED;
9772 if (! loop || ! file)
9775 /* Print diagnostics to compare our concept of a loop with
9776 what the loop notes say. */
9777 if (! PREV_INSN (loop->first->head)
9778 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9779 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9780 != NOTE_INSN_LOOP_BEG)
9781 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9782 INSN_UID (PREV_INSN (loop->first->head)));
9783 if (! NEXT_INSN (loop->last->end)
9784 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9785 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9786 != NOTE_INSN_LOOP_END)
9787 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9788 INSN_UID (NEXT_INSN (loop->last->end)));
9793 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9794 LOOP_BLOCK_NUM (loop->start),
9795 LOOP_INSN_UID (loop->start),
9796 LOOP_BLOCK_NUM (loop->cont),
9797 LOOP_INSN_UID (loop->cont),
9798 LOOP_BLOCK_NUM (loop->cont),
9799 LOOP_INSN_UID (loop->cont),
9800 LOOP_BLOCK_NUM (loop->vtop),
9801 LOOP_INSN_UID (loop->vtop),
9802 LOOP_BLOCK_NUM (loop->end),
9803 LOOP_INSN_UID (loop->end));
9804 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9805 LOOP_BLOCK_NUM (loop->top),
9806 LOOP_INSN_UID (loop->top),
9807 LOOP_BLOCK_NUM (loop->scan_start),
9808 LOOP_INSN_UID (loop->scan_start));
9809 fprintf (file, ";; exit_count %d", loop->exit_count);
9810 if (loop->exit_count)
9812 fputs (", labels:", file);
9813 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9815 fprintf (file, " %d ",
9816 LOOP_INSN_UID (XEXP (label, 0)));
9821 /* This can happen when a marked loop appears as two nested loops,
9822 say from while (a || b) {}. The inner loop won't match
9823 the loop markers but the outer one will. */
9824 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9825 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9829 /* Call this function from the debugger to dump LOOP. */
9833 const struct loop *loop;
9835 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
9838 /* Call this function from the debugger to dump LOOPS. */
9842 const struct loops *loops;
9844 flow_loops_dump (loops, stderr, loop_dump_aux, 1);