1 /* Perform various loop optimizations, including strength reduction.
2 Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
22 /* This is the loop optimization pass of the compiler.
23 It finds invariant computations within loops and moves them
24 to the beginning of the loop. Then it identifies basic and
25 general induction variables. Strength reduction is applied to the general
26 induction variables, and induction variable elimination is applied to
27 the basic induction variables.
29 It also finds cases where
30 a register is set within the loop by zero-extending a narrower value
31 and changes these to zero the entire register once before the loop
32 and merely copy the low part within the loop.
34 Most of the complexity is in heuristics to decide when it is worth
35 while to do these things. */
44 #include "hard-reg-set.h"
45 #include "basic-block.h"
46 #include "insn-config.h"
47 #include "insn-flags.h"
57 /* Vector mapping INSN_UIDs to luids.
58 The luids are like uids but increase monotonically always.
59 We use them to see whether a jump comes from outside a given loop. */
63 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
64 number the insn is contained in. */
66 struct loop **uid_loop;
68 /* 1 + largest uid of any insn. */
72 /* 1 + luid of last insn. */
76 /* Number of loops detected in current function. Used as index to the
79 static int max_loop_num;
81 /* Bound on pseudo register number before loop optimization.
82 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
83 unsigned int max_reg_before_loop;
85 /* The value to pass to the next call of reg_scan_update. */
86 static int loop_max_reg;
88 /* This obstack is used in product_cheap_p to allocate its rtl. It
89 may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
90 If we used the same obstack that it did, we would be deallocating
93 static struct obstack temp_obstack;
95 /* This is where the pointer to the obstack being used for RTL is stored. */
97 extern struct obstack *rtl_obstack;
99 #define obstack_chunk_alloc xmalloc
100 #define obstack_chunk_free free
102 /* During the analysis of a loop, a chain of `struct movable's
103 is made to record all the movable insns found.
104 Then the entire chain can be scanned to decide which to move. */
108 rtx insn; /* A movable insn */
109 rtx set_src; /* The expression this reg is set from. */
110 rtx set_dest; /* The destination of this SET. */
111 rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
112 of any registers used within the LIBCALL. */
113 int consec; /* Number of consecutive following insns
114 that must be moved with this one. */
115 unsigned int regno; /* The register it sets */
116 short lifetime; /* lifetime of that register;
117 may be adjusted when matching movables
118 that load the same value are found. */
119 short savings; /* Number of insns we can move for this reg,
120 including other movables that force this
121 or match this one. */
122 unsigned int cond : 1; /* 1 if only conditionally movable */
123 unsigned int force : 1; /* 1 means MUST move this insn */
124 unsigned int global : 1; /* 1 means reg is live outside this loop */
125 /* If PARTIAL is 1, GLOBAL means something different:
126 that the reg is live outside the range from where it is set
127 to the following label. */
128 unsigned int done : 1; /* 1 inhibits further processing of this */
130 unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
131 In particular, moving it does not make it
133 unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
134 load SRC, rather than copying INSN. */
135 unsigned int move_insn_first:1;/* Same as above, if this is necessary for the
136 first insn of a consecutive sets group. */
137 unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
138 enum machine_mode savemode; /* Nonzero means it is a mode for a low part
139 that we should avoid changing when clearing
140 the rest of the reg. */
141 struct movable *match; /* First entry for same value */
142 struct movable *forces; /* An insn that must be moved if this is */
143 struct movable *next;
148 /* Head of movable chain. */
149 struct movable *head;
150 /* Last movable in chain. */
151 struct movable *last;
152 /* Number of movables in the loop. */
156 static struct movables the_movables;
158 FILE *loop_dump_stream;
160 /* Forward declarations. */
162 static void find_and_verify_loops PARAMS ((rtx, struct loops *));
163 static void mark_loop_jump PARAMS ((rtx, struct loop *));
164 static void prescan_loop PARAMS ((struct loop *));
165 static int reg_in_basic_block_p PARAMS ((rtx, rtx));
166 static int consec_sets_invariant_p PARAMS ((const struct loop *,
168 static int labels_in_range_p PARAMS ((rtx, int));
169 static void count_one_set PARAMS ((struct loop_regs *, rtx, rtx,
170 varray_type, rtx *));
172 static void count_loop_regs_set PARAMS ((const struct loop*,
173 varray_type, varray_type,
175 static void note_addr_stored PARAMS ((rtx, rtx, void *));
176 static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
177 static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
178 static void scan_loop PARAMS ((struct loop*, int));
180 static void replace_call_address PARAMS ((rtx, rtx, rtx));
182 static rtx skip_consec_insns PARAMS ((rtx, int));
183 static int libcall_benefit PARAMS ((rtx));
184 static void ignore_some_movables PARAMS ((struct movables *));
185 static void force_movables PARAMS ((struct movables *));
186 static void combine_movables PARAMS ((struct movables *, struct loop_regs *));
187 static int regs_match_p PARAMS ((rtx, rtx, struct movables *));
188 static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct movables *,
189 struct loop_regs *));
190 static void add_label_notes PARAMS ((rtx, rtx));
191 static void move_movables PARAMS ((struct loop *loop, struct movables *,
193 static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
194 static void strength_reduce PARAMS ((struct loop *, int, int));
195 static void find_single_use_in_loop PARAMS ((rtx, rtx, varray_type));
196 static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
197 static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
198 static void record_biv PARAMS ((struct loop *, struct induction *,
199 rtx, rtx, rtx, rtx, rtx *,
201 static void check_final_value PARAMS ((const struct loop *,
202 struct induction *));
203 static void record_giv PARAMS ((const struct loop *, struct induction *,
204 rtx, rtx, rtx, rtx, rtx, rtx, int,
205 enum g_types, int, int, rtx *));
206 static void update_giv_derive PARAMS ((const struct loop *, rtx));
207 static void check_ext_dependant_givs PARAMS ((struct iv_class *,
208 struct loop_info *));
209 static int basic_induction_var PARAMS ((const struct loop *, rtx,
210 enum machine_mode, rtx, rtx,
211 rtx *, rtx *, rtx **));
212 static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
213 static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
214 rtx *, rtx *, rtx *, int, int *,
216 static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
217 rtx, rtx, rtx *, rtx *, rtx *, rtx *));
218 static int check_dbra_loop PARAMS ((struct loop *, int));
219 static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
220 static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
221 static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
222 static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
223 static int product_cheap_p PARAMS ((rtx, rtx));
224 static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
226 static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
227 struct iv_class *, int, rtx));
228 static int last_use_this_basic_block PARAMS ((rtx, rtx));
229 static void record_initial PARAMS ((rtx, rtx, void *));
230 static void update_reg_last_use PARAMS ((rtx, rtx));
231 static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
232 static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
234 static void load_mems PARAMS ((const struct loop *));
235 static int insert_loop_mem PARAMS ((rtx *, void *));
236 static int replace_loop_mem PARAMS ((rtx *, void *));
237 static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
238 static int replace_loop_reg PARAMS ((rtx *, void *));
239 static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
240 static void note_reg_stored PARAMS ((rtx, rtx, void *));
241 static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
242 static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
244 static int replace_label PARAMS ((rtx *, void *));
245 static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
246 static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
247 static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
249 static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
250 void debug_loop PARAMS ((const struct loop *));
252 typedef struct rtx_pair
258 typedef struct loop_replace_args
265 /* Nonzero iff INSN is between START and END, inclusive. */
266 #define INSN_IN_RANGE_P(INSN, START, END) \
267 (INSN_UID (INSN) < max_uid_for_loop \
268 && INSN_LUID (INSN) >= INSN_LUID (START) \
269 && INSN_LUID (INSN) <= INSN_LUID (END))
271 /* Indirect_jump_in_function is computed once per function. */
272 static int indirect_jump_in_function;
273 static int indirect_jump_in_function_p PARAMS ((rtx));
275 static int compute_luids PARAMS ((rtx, rtx, int));
277 static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
281 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
282 copy the value of the strength reduced giv to its original register. */
283 static int copy_cost;
285 /* Cost of using a register, to normalize the benefits of a giv. */
286 static int reg_address_cost;
291 char *free_point = (char *) oballoc (1);
292 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
294 reg_address_cost = address_cost (reg, SImode);
296 copy_cost = COSTS_N_INSNS (1);
298 /* Free the objects we just allocated. */
301 /* Initialize the obstack used for rtl in product_cheap_p. */
302 gcc_obstack_init (&temp_obstack);
305 /* Compute the mapping from uids to luids.
306 LUIDs are numbers assigned to insns, like uids,
307 except that luids increase monotonically through the code.
308 Start at insn START and stop just before END. Assign LUIDs
309 starting with PREV_LUID + 1. Return the last assigned LUID + 1. */
311 compute_luids (start, end, prev_luid)
318 for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
320 if (INSN_UID (insn) >= max_uid_for_loop)
322 /* Don't assign luids to line-number NOTEs, so that the distance in
323 luids between two insns is not affected by -g. */
324 if (GET_CODE (insn) != NOTE
325 || NOTE_LINE_NUMBER (insn) <= 0)
326 uid_luid[INSN_UID (insn)] = ++i;
328 /* Give a line number note the same luid as preceding insn. */
329 uid_luid[INSN_UID (insn)] = i;
334 /* Entry point of this file. Perform loop optimization
335 on the current function. F is the first insn of the function
336 and DUMPFILE is a stream for output of a trace of actions taken
337 (or 0 if none should be output). */
340 loop_optimize (f, dumpfile, flags)
341 /* f is the first instruction of a chain of insns for one function */
348 struct loops loops_data;
349 struct loops *loops = &loops_data;
350 struct loop_info *loops_info;
351 static char *moved_once;
353 loop_dump_stream = dumpfile;
355 init_recog_no_volatile ();
357 max_reg_before_loop = max_reg_num ();
358 loop_max_reg = max_reg_before_loop;
362 /* Count the number of loops. */
365 for (insn = f; insn; insn = NEXT_INSN (insn))
367 if (GET_CODE (insn) == NOTE
368 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
372 /* Don't waste time if no loops. */
373 if (max_loop_num == 0)
376 loops->num = max_loop_num;
378 moved_once = (char *) xcalloc (max_reg_before_loop, sizeof (char));
380 /* Get size to use for tables indexed by uids.
381 Leave some space for labels allocated by find_and_verify_loops. */
382 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
384 uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
385 uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
386 sizeof (struct loop *));
388 /* Allocate storage for array of loops. */
389 loops->array = (struct loop *)
390 xcalloc (loops->num, sizeof (struct loop));
392 /* Find and process each loop.
393 First, find them, and record them in order of their beginnings. */
394 find_and_verify_loops (f, loops);
396 /* Allocate and initialize auxiliary loop information. */
397 loops_info = xcalloc (loops->num, sizeof (struct loop_info));
398 for (i = 0; i < loops->num; i++)
399 loops->array[i].aux = loops_info + i;
401 /* Now find all register lifetimes. This must be done after
402 find_and_verify_loops, because it might reorder the insns in the
404 reg_scan (f, max_reg_before_loop, 1);
406 /* This must occur after reg_scan so that registers created by gcse
407 will have entries in the register tables.
409 We could have added a call to reg_scan after gcse_main in toplev.c,
410 but moving this call to init_alias_analysis is more efficient. */
411 init_alias_analysis ();
413 /* See if we went too far. Note that get_max_uid already returns
414 one more that the maximum uid of all insn. */
415 if (get_max_uid () > max_uid_for_loop)
417 /* Now reset it to the actual size we need. See above. */
418 max_uid_for_loop = get_max_uid ();
420 /* find_and_verify_loops has already called compute_luids, but it
421 might have rearranged code afterwards, so we need to recompute
423 max_luid = compute_luids (f, NULL_RTX, 0);
425 /* Don't leave gaps in uid_luid for insns that have been
426 deleted. It is possible that the first or last insn
427 using some register has been deleted by cross-jumping.
428 Make sure that uid_luid for that former insn's uid
429 points to the general area where that insn used to be. */
430 for (i = 0; i < max_uid_for_loop; i++)
432 uid_luid[0] = uid_luid[i];
433 if (uid_luid[0] != 0)
436 for (i = 0; i < max_uid_for_loop; i++)
437 if (uid_luid[i] == 0)
438 uid_luid[i] = uid_luid[i - 1];
440 /* Determine if the function has indirect jump. On some systems
441 this prevents low overhead loop instructions from being used. */
442 indirect_jump_in_function = indirect_jump_in_function_p (f);
444 /* Now scan the loops, last ones first, since this means inner ones are done
445 before outer ones. */
446 for (i = max_loop_num - 1; i >= 0; i--)
448 struct loop *loop = &loops->array[i];
449 struct loop_regs *regs = LOOP_REGS (loop);
451 regs->moved_once = moved_once;
453 if (! loop->invalid && loop->end)
454 scan_loop (loop, flags);
457 /* If there were lexical blocks inside the loop, they have been
458 replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
459 and NOTE_INSN_BLOCK_END for each such block. We must duplicate
460 the BLOCKs as well. */
461 if (write_symbols != NO_DEBUG)
464 end_alias_analysis ();
474 /* Returns the next insn, in execution order, after INSN. START and
475 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
476 respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
477 insn-stream; it is used with loops that are entered near the
481 next_insn_in_loop (loop, insn)
482 const struct loop *loop;
485 insn = NEXT_INSN (insn);
487 if (insn == loop->end)
490 /* Go to the top of the loop, and continue there. */
497 if (insn == loop->scan_start)
504 /* Optimize one loop described by LOOP. */
506 /* ??? Could also move memory writes out of loops if the destination address
507 is invariant, the source is invariant, the memory write is not volatile,
508 and if we can prove that no read inside the loop can read this address
509 before the write occurs. If there is a read of this address after the
510 write, then we can also mark the memory read as invariant. */
513 scan_loop (loop, flags)
517 struct loop_info *loop_info = LOOP_INFO (loop);
518 struct loop_regs *regs = LOOP_REGS (loop);
520 rtx loop_start = loop->start;
521 rtx loop_end = loop->end;
523 /* 1 if we are scanning insns that could be executed zero times. */
525 /* 1 if we are scanning insns that might never be executed
526 due to a subroutine call which might exit before they are reached. */
528 /* Jump insn that enters the loop, or 0 if control drops in. */
529 rtx loop_entry_jump = 0;
530 /* Number of insns in the loop. */
533 rtx temp, update_start, update_end;
534 /* The SET from an insn, if it is the only SET in the insn. */
536 /* Chain describing insns movable in current loop. */
537 struct movables *movables = &the_movables;
538 /* Ratio of extra register life span we can justify
539 for saving an instruction. More if loop doesn't call subroutines
540 since in that case saving an insn makes more difference
541 and more registers are available. */
543 /* Nonzero if we are scanning instructions in a sub-loop. */
553 /* Determine whether this loop starts with a jump down to a test at
554 the end. This will occur for a small number of loops with a test
555 that is too complex to duplicate in front of the loop.
557 We search for the first insn or label in the loop, skipping NOTEs.
558 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
559 (because we might have a loop executed only once that contains a
560 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
561 (in case we have a degenerate loop).
563 Note that if we mistakenly think that a loop is entered at the top
564 when, in fact, it is entered at the exit test, the only effect will be
565 slightly poorer optimization. Making the opposite error can generate
566 incorrect code. Since very few loops now start with a jump to the
567 exit test, the code here to detect that case is very conservative. */
569 for (p = NEXT_INSN (loop_start);
571 && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
572 && (GET_CODE (p) != NOTE
573 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
574 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
578 loop->scan_start = p;
580 /* Set up variables describing this loop. */
582 threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
584 /* If loop has a jump before the first label,
585 the true entry is the target of that jump.
586 Start scan from there.
587 But record in LOOP->TOP the place where the end-test jumps
588 back to so we can scan that after the end of the loop. */
589 if (GET_CODE (p) == JUMP_INSN)
593 /* Loop entry must be unconditional jump (and not a RETURN) */
594 if (any_uncondjump_p (p)
595 && JUMP_LABEL (p) != 0
596 /* Check to see whether the jump actually
597 jumps out of the loop (meaning it's no loop).
598 This case can happen for things like
599 do {..} while (0). If this label was generated previously
600 by loop, we can't tell anything about it and have to reject
602 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
604 loop->top = next_label (loop->scan_start);
605 loop->scan_start = JUMP_LABEL (p);
609 /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
610 as required by loop_reg_used_before_p. So skip such loops. (This
611 test may never be true, but it's best to play it safe.)
613 Also, skip loops where we do not start scanning at a label. This
614 test also rejects loops starting with a JUMP_INSN that failed the
617 if (INSN_UID (loop->scan_start) >= max_uid_for_loop
618 || GET_CODE (loop->scan_start) != CODE_LABEL)
620 if (loop_dump_stream)
621 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
622 INSN_UID (loop_start), INSN_UID (loop_end));
626 /* Count number of times each reg is set during this loop. Set
627 VARRAY_CHAR (regs->may_not_optimize, I) if it is not safe to move
628 out the setting of register I. Set VARRAY_RTX
629 (regs->single_usage, I). */
631 /* Allocate extra space for REGS that might be created by
632 load_mems. We allocate a little extra slop as well, in the hopes
633 that even after the moving of movables creates some new registers
634 we won't have to reallocate these arrays. However, we do grow
635 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
636 nregs = max_reg_num () + loop_info->mems_idx + 16;
637 VARRAY_INT_INIT (regs->set_in_loop, nregs, "set_in_loop");
638 VARRAY_INT_INIT (regs->n_times_set, nregs, "n_times_set");
639 VARRAY_CHAR_INIT (regs->may_not_optimize, nregs, "may_not_optimize");
640 VARRAY_RTX_INIT (regs->single_usage, nregs, "single_usage");
644 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
647 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
649 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
650 VARRAY_INT (regs->set_in_loop, i) = 1;
653 #ifdef AVOID_CCMODE_COPIES
654 /* Don't try to move insns which set CC registers if we should not
655 create CCmode register copies. */
656 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
657 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
658 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
661 bcopy ((char *) ®s->set_in_loop->data,
662 (char *) ®s->n_times_set->data, nregs * sizeof (int));
664 if (loop_dump_stream)
666 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
667 INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
669 fprintf (loop_dump_stream, "Continue at insn %d.\n",
670 INSN_UID (loop->cont));
673 /* Scan through the loop finding insns that are safe to move.
674 Set regs->set_in_loop negative for the reg being set, so that
675 this reg will be considered invariant for subsequent insns.
676 We consider whether subsequent insns use the reg
677 in deciding whether it is worth actually moving.
679 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
680 and therefore it is possible that the insns we are scanning
681 would never be executed. At such times, we must make sure
682 that it is safe to execute the insn once instead of zero times.
683 When MAYBE_NEVER is 0, all insns will be executed at least once
684 so that is not a problem. */
686 for (p = next_insn_in_loop (loop, loop->scan_start);
688 p = next_insn_in_loop (loop, p))
690 if (GET_CODE (p) == INSN
691 && (set = single_set (p))
692 && GET_CODE (SET_DEST (set)) == REG
693 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
698 rtx src = SET_SRC (set);
699 rtx dependencies = 0;
701 /* Figure out what to use as a source of this insn. If a REG_EQUIV
702 note is given or if a REG_EQUAL note with a constant operand is
703 specified, use it as the source and mark that we should move
704 this insn by calling emit_move_insn rather that duplicating the
707 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
709 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
711 src = XEXP (temp, 0), move_insn = 1;
714 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
715 if (temp && CONSTANT_P (XEXP (temp, 0)))
716 src = XEXP (temp, 0), move_insn = 1;
717 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
719 src = XEXP (temp, 0);
720 /* A libcall block can use regs that don't appear in
721 the equivalent expression. To move the libcall,
722 we must move those regs too. */
723 dependencies = libcall_other_reg (p, src);
727 /* Don't try to optimize a register that was made
728 by loop-optimization for an inner loop.
729 We don't know its life-span, so we can't compute the benefit. */
730 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
732 else if (/* The register is used in basic blocks other
733 than the one where it is set (meaning that
734 something after this point in the loop might
735 depend on its value before the set). */
736 ! reg_in_basic_block_p (p, SET_DEST (set))
737 /* And the set is not guaranteed to be executed one
738 the loop starts, or the value before the set is
739 needed before the set occurs...
741 ??? Note we have quadratic behaviour here, mitigated
742 by the fact that the previous test will often fail for
743 large loops. Rather than re-scanning the entire loop
744 each time for register usage, we should build tables
745 of the register usage and use them here instead. */
747 || loop_reg_used_before_p (loop, set, p)))
748 /* It is unsafe to move the set.
750 This code used to consider it OK to move a set of a variable
751 which was not created by the user and not used in an exit test.
752 That behavior is incorrect and was removed. */
754 else if ((tem = loop_invariant_p (loop, src))
755 && (dependencies == 0
756 || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
757 && (VARRAY_INT (regs->set_in_loop,
758 REGNO (SET_DEST (set))) == 1
760 = consec_sets_invariant_p
761 (loop, SET_DEST (set),
762 VARRAY_INT (regs->set_in_loop,
763 REGNO (SET_DEST (set))),
765 /* If the insn can cause a trap (such as divide by zero),
766 can't move it unless it's guaranteed to be executed
767 once loop is entered. Even a function call might
768 prevent the trap insn from being reached
769 (since it might exit!) */
770 && ! ((maybe_never || call_passed)
771 && may_trap_p (src)))
773 register struct movable *m;
774 register int regno = REGNO (SET_DEST (set));
776 /* A potential lossage is where we have a case where two insns
777 can be combined as long as they are both in the loop, but
778 we move one of them outside the loop. For large loops,
779 this can lose. The most common case of this is the address
780 of a function being called.
782 Therefore, if this register is marked as being used exactly
783 once if we are in a loop with calls (a "large loop"), see if
784 we can replace the usage of this register with the source
785 of this SET. If we can, delete this insn.
787 Don't do this if P has a REG_RETVAL note or if we have
788 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
790 if (loop_info->has_call
791 && VARRAY_RTX (regs->single_usage, regno) != 0
792 && VARRAY_RTX (regs->single_usage, regno) != const0_rtx
793 && REGNO_FIRST_UID (regno) == INSN_UID (p)
794 && (REGNO_LAST_UID (regno)
795 == INSN_UID (VARRAY_RTX (regs->single_usage, regno)))
796 && VARRAY_INT (regs->set_in_loop, regno) == 1
797 && ! side_effects_p (SET_SRC (set))
798 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
799 && (! SMALL_REGISTER_CLASSES
800 || (! (GET_CODE (SET_SRC (set)) == REG
801 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
802 /* This test is not redundant; SET_SRC (set) might be
803 a call-clobbered register and the life of REGNO
804 might span a call. */
805 && ! modified_between_p (SET_SRC (set), p,
807 (regs->single_usage, regno))
808 && no_labels_between_p (p, VARRAY_RTX (regs->single_usage,
810 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
812 (regs->single_usage, regno)))
814 /* Replace any usage in a REG_EQUAL note. Must copy the
815 new source, so that we don't get rtx sharing between the
816 SET_SOURCE and REG_NOTES of insn p. */
817 REG_NOTES (VARRAY_RTX (regs->single_usage, regno))
818 = replace_rtx (REG_NOTES (VARRAY_RTX
819 (regs->single_usage, regno)),
820 SET_DEST (set), copy_rtx (SET_SRC (set)));
823 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
824 NOTE_SOURCE_FILE (p) = 0;
825 VARRAY_INT (regs->set_in_loop, regno) = 0;
829 m = (struct movable *) alloca (sizeof (struct movable));
833 m->dependencies = dependencies;
834 m->set_dest = SET_DEST (set);
836 m->consec = VARRAY_INT (regs->set_in_loop,
837 REGNO (SET_DEST (set))) - 1;
841 m->move_insn = move_insn;
842 m->move_insn_first = 0;
843 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
844 m->savemode = VOIDmode;
846 /* Set M->cond if either loop_invariant_p
847 or consec_sets_invariant_p returned 2
848 (only conditionally invariant). */
849 m->cond = ((tem | tem1 | tem2) > 1);
850 m->global = (uid_luid[REGNO_LAST_UID (regno)]
851 > INSN_LUID (loop_end)
852 || uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
854 m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
855 - uid_luid[REGNO_FIRST_UID (regno)]);
856 m->savings = VARRAY_INT (regs->n_times_set, regno);
857 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
858 m->savings += libcall_benefit (p);
859 VARRAY_INT (regs->set_in_loop, regno) = move_insn ? -2 : -1;
860 /* Add M to the end of the chain MOVABLES. */
861 if (movables->head == 0)
864 movables->last->next = m;
869 /* It is possible for the first instruction to have a
870 REG_EQUAL note but a non-invariant SET_SRC, so we must
871 remember the status of the first instruction in case
872 the last instruction doesn't have a REG_EQUAL note. */
873 m->move_insn_first = m->move_insn;
875 /* Skip this insn, not checking REG_LIBCALL notes. */
876 p = next_nonnote_insn (p);
877 /* Skip the consecutive insns, if there are any. */
878 p = skip_consec_insns (p, m->consec);
879 /* Back up to the last insn of the consecutive group. */
880 p = prev_nonnote_insn (p);
882 /* We must now reset m->move_insn, m->is_equiv, and possibly
883 m->set_src to correspond to the effects of all the
885 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
887 m->set_src = XEXP (temp, 0), m->move_insn = 1;
890 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
891 if (temp && CONSTANT_P (XEXP (temp, 0)))
892 m->set_src = XEXP (temp, 0), m->move_insn = 1;
897 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
900 /* If this register is always set within a STRICT_LOW_PART
901 or set to zero, then its high bytes are constant.
902 So clear them outside the loop and within the loop
903 just load the low bytes.
904 We must check that the machine has an instruction to do so.
905 Also, if the value loaded into the register
906 depends on the same register, this cannot be done. */
907 else if (SET_SRC (set) == const0_rtx
908 && GET_CODE (NEXT_INSN (p)) == INSN
909 && (set1 = single_set (NEXT_INSN (p)))
910 && GET_CODE (set1) == SET
911 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
912 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
913 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
915 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
917 register int regno = REGNO (SET_DEST (set));
918 if (VARRAY_INT (regs->set_in_loop, regno) == 2)
920 register struct movable *m;
921 m = (struct movable *) alloca (sizeof (struct movable));
924 m->set_dest = SET_DEST (set);
931 m->move_insn_first = 0;
933 /* If the insn may not be executed on some cycles,
934 we can't clear the whole reg; clear just high part.
935 Not even if the reg is used only within this loop.
942 Clearing x before the inner loop could clobber a value
943 being saved from the last time around the outer loop.
944 However, if the reg is not used outside this loop
945 and all uses of the register are in the same
946 basic block as the store, there is no problem.
948 If this insn was made by loop, we don't know its
949 INSN_LUID and hence must make a conservative
951 m->global = (INSN_UID (p) >= max_uid_for_loop
952 || (uid_luid[REGNO_LAST_UID (regno)]
953 > INSN_LUID (loop_end))
954 || (uid_luid[REGNO_FIRST_UID (regno)]
956 || (labels_in_range_p
957 (p, uid_luid[REGNO_FIRST_UID (regno)])));
958 if (maybe_never && m->global)
959 m->savemode = GET_MODE (SET_SRC (set1));
961 m->savemode = VOIDmode;
965 m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
966 - uid_luid[REGNO_FIRST_UID (regno)]);
968 VARRAY_INT (regs->set_in_loop, regno) = -1;
969 /* Add M to the end of the chain MOVABLES. */
970 if (movables->head == 0)
973 movables->last->next = m;
978 /* Past a call insn, we get to insns which might not be executed
979 because the call might exit. This matters for insns that trap.
980 Constant and pure call insns always return, so they don't count. */
981 else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
983 /* Past a label or a jump, we get to insns for which we
984 can't count on whether or how many times they will be
985 executed during each iteration. Therefore, we can
986 only move out sets of trivial variables
987 (those not used after the loop). */
988 /* Similar code appears twice in strength_reduce. */
989 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
990 /* If we enter the loop in the middle, and scan around to the
991 beginning, don't set maybe_never for that. This must be an
992 unconditional jump, otherwise the code at the top of the
993 loop might never be executed. Unconditional jumps are
994 followed a by barrier then loop end. */
995 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
996 && NEXT_INSN (NEXT_INSN (p)) == loop_end
997 && any_uncondjump_p (p)))
999 else if (GET_CODE (p) == NOTE)
1001 /* At the virtual top of a converted loop, insns are again known to
1002 be executed: logically, the loop begins here even though the exit
1003 code has been duplicated. */
1004 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
1005 maybe_never = call_passed = 0;
1006 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
1008 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
1013 /* If one movable subsumes another, ignore that other. */
1015 ignore_some_movables (movables);
1017 /* For each movable insn, see if the reg that it loads
1018 leads when it dies right into another conditionally movable insn.
1019 If so, record that the second insn "forces" the first one,
1020 since the second can be moved only if the first is. */
1022 force_movables (movables);
1024 /* See if there are multiple movable insns that load the same value.
1025 If there are, make all but the first point at the first one
1026 through the `match' field, and add the priorities of them
1027 all together as the priority of the first. */
1029 combine_movables (movables, regs);
1031 /* Now consider each movable insn to decide whether it is worth moving.
1032 Store 0 in regs->set_in_loop for each reg that is moved.
1034 Generally this increases code size, so do not move moveables when
1035 optimizing for code size. */
1037 if (! optimize_size)
1038 move_movables (loop, movables, threshold, insn_count);
1040 /* Now candidates that still are negative are those not moved.
1041 Change regs->set_in_loop to indicate that those are not actually
1043 for (i = 0; i < nregs; i++)
1044 if (VARRAY_INT (regs->set_in_loop, i) < 0)
1045 VARRAY_INT (regs->set_in_loop, i) = VARRAY_INT (regs->n_times_set, i);
1047 /* Now that we've moved some things out of the loop, we might be able to
1048 hoist even more memory references. */
1049 load_mems_and_recount_loop_regs_set (loop, &insn_count);
1051 for (update_start = loop_start;
1052 PREV_INSN (update_start)
1053 && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
1054 update_start = PREV_INSN (update_start))
1056 update_end = NEXT_INSN (loop_end);
1058 reg_scan_update (update_start, update_end, loop_max_reg);
1059 loop_max_reg = max_reg_num ();
1061 if (flag_strength_reduce)
1063 if (update_end && GET_CODE (update_end) == CODE_LABEL)
1064 /* Ensure our label doesn't go away. */
1065 LABEL_NUSES (update_end)++;
1067 strength_reduce (loop, insn_count, flags);
1069 reg_scan_update (update_start, update_end, loop_max_reg);
1070 loop_max_reg = max_reg_num ();
1072 if (update_end && GET_CODE (update_end) == CODE_LABEL
1073 && --LABEL_NUSES (update_end) == 0)
1074 delete_insn (update_end);
1077 VARRAY_FREE (regs->single_usage);
1078 VARRAY_FREE (regs->set_in_loop);
1079 VARRAY_FREE (regs->n_times_set);
1080 VARRAY_FREE (regs->may_not_optimize);
1083 /* Add elements to *OUTPUT to record all the pseudo-regs
1084 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1087 record_excess_regs (in_this, not_in_this, output)
1088 rtx in_this, not_in_this;
1095 code = GET_CODE (in_this);
1109 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1110 && ! reg_mentioned_p (in_this, not_in_this))
1111 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1118 fmt = GET_RTX_FORMAT (code);
1119 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1126 for (j = 0; j < XVECLEN (in_this, i); j++)
1127 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1131 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1137 /* Check what regs are referred to in the libcall block ending with INSN,
1138 aside from those mentioned in the equivalent value.
1139 If there are none, return 0.
1140 If there are one or more, return an EXPR_LIST containing all of them. */
1143 libcall_other_reg (insn, equiv)
1146 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1147 rtx p = XEXP (note, 0);
1150 /* First, find all the regs used in the libcall block
1151 that are not mentioned as inputs to the result. */
1155 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1156 || GET_CODE (p) == CALL_INSN)
1157 record_excess_regs (PATTERN (p), equiv, &output);
1164 /* Return 1 if all uses of REG
1165 are between INSN and the end of the basic block. */
1168 reg_in_basic_block_p (insn, reg)
1171 int regno = REGNO (reg);
1174 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1177 /* Search this basic block for the already recorded last use of the reg. */
1178 for (p = insn; p; p = NEXT_INSN (p))
1180 switch (GET_CODE (p))
1187 /* Ordinary insn: if this is the last use, we win. */
1188 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1193 /* Jump insn: if this is the last use, we win. */
1194 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1196 /* Otherwise, it's the end of the basic block, so we lose. */
1201 /* It's the end of the basic block, so we lose. */
1209 /* The "last use" that was recorded can't be found after the first
1210 use. This can happen when the last use was deleted while
1211 processing an inner loop, this inner loop was then completely
1212 unrolled, and the outer loop is always exited after the inner loop,
1213 so that everything after the first use becomes a single basic block. */
1217 /* Compute the benefit of eliminating the insns in the block whose
1218 last insn is LAST. This may be a group of insns used to compute a
1219 value directly or can contain a library call. */
1222 libcall_benefit (last)
1228 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1229 insn != last; insn = NEXT_INSN (insn))
1231 if (GET_CODE (insn) == CALL_INSN)
1232 benefit += 10; /* Assume at least this many insns in a library
1234 else if (GET_CODE (insn) == INSN
1235 && GET_CODE (PATTERN (insn)) != USE
1236 && GET_CODE (PATTERN (insn)) != CLOBBER)
1243 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1246 skip_consec_insns (insn, count)
1250 for (; count > 0; count--)
1254 /* If first insn of libcall sequence, skip to end. */
1255 /* Do this at start of loop, since INSN is guaranteed to
1257 if (GET_CODE (insn) != NOTE
1258 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1259 insn = XEXP (temp, 0);
1262 insn = NEXT_INSN (insn);
1263 while (GET_CODE (insn) == NOTE);
1269 /* Ignore any movable whose insn falls within a libcall
1270 which is part of another movable.
1271 We make use of the fact that the movable for the libcall value
1272 was made later and so appears later on the chain. */
1275 ignore_some_movables (movables)
1276 struct movables *movables;
1278 register struct movable *m, *m1;
1280 for (m = movables->head; m; m = m->next)
1282 /* Is this a movable for the value of a libcall? */
1283 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1287 /* Check for earlier movables inside that range,
1288 and mark them invalid. We cannot use LUIDs here because
1289 insns created by loop.c for prior loops don't have LUIDs.
1290 Rather than reject all such insns from movables, we just
1291 explicitly check each insn in the libcall (since invariant
1292 libcalls aren't that common). */
1293 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1294 for (m1 = movables->head; m1 != m; m1 = m1->next)
1295 if (m1->insn == insn)
1301 /* For each movable insn, see if the reg that it loads
1302 leads when it dies right into another conditionally movable insn.
1303 If so, record that the second insn "forces" the first one,
1304 since the second can be moved only if the first is. */
1307 force_movables (movables)
1308 struct movables *movables;
1310 register struct movable *m, *m1;
1311 for (m1 = movables->head; m1; m1 = m1->next)
1312 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1313 if (!m1->partial && !m1->done)
1315 int regno = m1->regno;
1316 for (m = m1->next; m; m = m->next)
1317 /* ??? Could this be a bug? What if CSE caused the
1318 register of M1 to be used after this insn?
1319 Since CSE does not update regno_last_uid,
1320 this insn M->insn might not be where it dies.
1321 But very likely this doesn't matter; what matters is
1322 that M's reg is computed from M1's reg. */
1323 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1326 if (m != 0 && m->set_src == m1->set_dest
1327 /* If m->consec, m->set_src isn't valid. */
1331 /* Increase the priority of the moving the first insn
1332 since it permits the second to be moved as well. */
1336 m1->lifetime += m->lifetime;
1337 m1->savings += m->savings;
1342 /* Find invariant expressions that are equal and can be combined into
1346 combine_movables (movables, regs)
1347 struct movables *movables;
1348 struct loop_regs *regs;
1350 register struct movable *m;
1351 char *matched_regs = (char *) xmalloc (regs->num);
1352 enum machine_mode mode;
1354 /* Regs that are set more than once are not allowed to match
1355 or be matched. I'm no longer sure why not. */
1356 /* Perhaps testing m->consec_sets would be more appropriate here? */
1358 for (m = movables->head; m; m = m->next)
1359 if (m->match == 0 && VARRAY_INT (regs->n_times_set, m->regno) == 1
1362 register struct movable *m1;
1363 int regno = m->regno;
1365 bzero (matched_regs, regs->num);
1366 matched_regs[regno] = 1;
1368 /* We want later insns to match the first one. Don't make the first
1369 one match any later ones. So start this loop at m->next. */
1370 for (m1 = m->next; m1; m1 = m1->next)
1371 if (m != m1 && m1->match == 0 && VARRAY_INT (regs->n_times_set,
1373 /* A reg used outside the loop mustn't be eliminated. */
1375 /* A reg used for zero-extending mustn't be eliminated. */
1377 && (matched_regs[m1->regno]
1380 /* Can combine regs with different modes loaded from the
1381 same constant only if the modes are the same or
1382 if both are integer modes with M wider or the same
1383 width as M1. The check for integer is redundant, but
1384 safe, since the only case of differing destination
1385 modes with equal sources is when both sources are
1386 VOIDmode, i.e., CONST_INT. */
1387 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1388 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1389 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1390 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1391 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1392 /* See if the source of M1 says it matches M. */
1393 && ((GET_CODE (m1->set_src) == REG
1394 && matched_regs[REGNO (m1->set_src)])
1395 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1397 && ((m->dependencies == m1->dependencies)
1398 || rtx_equal_p (m->dependencies, m1->dependencies)))
1400 m->lifetime += m1->lifetime;
1401 m->savings += m1->savings;
1404 matched_regs[m1->regno] = 1;
1408 /* Now combine the regs used for zero-extension.
1409 This can be done for those not marked `global'
1410 provided their lives don't overlap. */
1412 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1413 mode = GET_MODE_WIDER_MODE (mode))
1415 register struct movable *m0 = 0;
1417 /* Combine all the registers for extension from mode MODE.
1418 Don't combine any that are used outside this loop. */
1419 for (m = movables->head; m; m = m->next)
1420 if (m->partial && ! m->global
1421 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1423 register struct movable *m1;
1424 int first = uid_luid[REGNO_FIRST_UID (m->regno)];
1425 int last = uid_luid[REGNO_LAST_UID (m->regno)];
1429 /* First one: don't check for overlap, just record it. */
1434 /* Make sure they extend to the same mode.
1435 (Almost always true.) */
1436 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1439 /* We already have one: check for overlap with those
1440 already combined together. */
1441 for (m1 = movables->head; m1 != m; m1 = m1->next)
1442 if (m1 == m0 || (m1->partial && m1->match == m0))
1443 if (! (uid_luid[REGNO_FIRST_UID (m1->regno)] > last
1444 || uid_luid[REGNO_LAST_UID (m1->regno)] < first))
1447 /* No overlap: we can combine this with the others. */
1448 m0->lifetime += m->lifetime;
1449 m0->savings += m->savings;
1459 free (matched_regs);
1462 /* Return 1 if regs X and Y will become the same if moved. */
1465 regs_match_p (x, y, movables)
1467 struct movables *movables;
1469 unsigned int xn = REGNO (x);
1470 unsigned int yn = REGNO (y);
1471 struct movable *mx, *my;
1473 for (mx = movables->head; mx; mx = mx->next)
1474 if (mx->regno == xn)
1477 for (my = movables->head; my; my = my->next)
1478 if (my->regno == yn)
1482 && ((mx->match == my->match && mx->match != 0)
1484 || mx == my->match));
1487 /* Return 1 if X and Y are identical-looking rtx's.
1488 This is the Lisp function EQUAL for rtx arguments.
1490 If two registers are matching movables or a movable register and an
1491 equivalent constant, consider them equal. */
1494 rtx_equal_for_loop_p (x, y, movables, regs)
1496 struct movables *movables;
1497 struct loop_regs *regs;
1501 register struct movable *m;
1502 register enum rtx_code code;
1503 register const char *fmt;
1507 if (x == 0 || y == 0)
1510 code = GET_CODE (x);
1512 /* If we have a register and a constant, they may sometimes be
1514 if (GET_CODE (x) == REG && VARRAY_INT (regs->set_in_loop, REGNO (x)) == -2
1517 for (m = movables->head; m; m = m->next)
1518 if (m->move_insn && m->regno == REGNO (x)
1519 && rtx_equal_p (m->set_src, y))
1522 else if (GET_CODE (y) == REG && VARRAY_INT (regs->set_in_loop,
1526 for (m = movables->head; m; m = m->next)
1527 if (m->move_insn && m->regno == REGNO (y)
1528 && rtx_equal_p (m->set_src, x))
1532 /* Otherwise, rtx's of different codes cannot be equal. */
1533 if (code != GET_CODE (y))
1536 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1537 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1539 if (GET_MODE (x) != GET_MODE (y))
1542 /* These three types of rtx's can be compared nonrecursively. */
1544 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1546 if (code == LABEL_REF)
1547 return XEXP (x, 0) == XEXP (y, 0);
1548 if (code == SYMBOL_REF)
1549 return XSTR (x, 0) == XSTR (y, 0);
1551 /* Compare the elements. If any pair of corresponding elements
1552 fail to match, return 0 for the whole things. */
1554 fmt = GET_RTX_FORMAT (code);
1555 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1560 if (XWINT (x, i) != XWINT (y, i))
1565 if (XINT (x, i) != XINT (y, i))
1570 /* Two vectors must have the same length. */
1571 if (XVECLEN (x, i) != XVECLEN (y, i))
1574 /* And the corresponding elements must match. */
1575 for (j = 0; j < XVECLEN (x, i); j++)
1576 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
1577 movables, regs) == 0)
1582 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
1588 if (strcmp (XSTR (x, i), XSTR (y, i)))
1593 /* These are just backpointers, so they don't matter. */
1599 /* It is believed that rtx's at this level will never
1600 contain anything but integers and other rtx's,
1601 except for within LABEL_REFs and SYMBOL_REFs. */
1609 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1610 insns in INSNS which use the reference. */
1613 add_label_notes (x, insns)
1617 enum rtx_code code = GET_CODE (x);
1622 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1624 /* This code used to ignore labels that referred to dispatch tables to
1625 avoid flow generating (slighly) worse code.
1627 We no longer ignore such label references (see LABEL_REF handling in
1628 mark_jump_label for additional information). */
1629 for (insn = insns; insn; insn = NEXT_INSN (insn))
1630 if (reg_mentioned_p (XEXP (x, 0), insn))
1631 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1635 fmt = GET_RTX_FORMAT (code);
1636 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1639 add_label_notes (XEXP (x, i), insns);
1640 else if (fmt[i] == 'E')
1641 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1642 add_label_notes (XVECEXP (x, i, j), insns);
1646 /* Scan MOVABLES, and move the insns that deserve to be moved.
1647 If two matching movables are combined, replace one reg with the
1648 other throughout. */
1651 move_movables (loop, movables, threshold, insn_count)
1653 struct movables *movables;
1657 struct loop_regs *regs = LOOP_REGS (loop);
1658 int nregs = regs->num;
1660 register struct movable *m;
1662 rtx loop_start = loop->start;
1663 rtx loop_end = loop->end;
1664 /* Map of pseudo-register replacements to handle combining
1665 when we move several insns that load the same value
1666 into different pseudo-registers. */
1667 rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
1668 char *already_moved = (char *) xcalloc (nregs, sizeof (char));
1672 for (m = movables->head; m; m = m->next)
1674 /* Describe this movable insn. */
1676 if (loop_dump_stream)
1678 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1679 INSN_UID (m->insn), m->regno, m->lifetime);
1681 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1683 fprintf (loop_dump_stream, "cond ");
1685 fprintf (loop_dump_stream, "force ");
1687 fprintf (loop_dump_stream, "global ");
1689 fprintf (loop_dump_stream, "done ");
1691 fprintf (loop_dump_stream, "move-insn ");
1693 fprintf (loop_dump_stream, "matches %d ",
1694 INSN_UID (m->match->insn));
1696 fprintf (loop_dump_stream, "forces %d ",
1697 INSN_UID (m->forces->insn));
1700 /* Count movables. Value used in heuristics in strength_reduce. */
1703 /* Ignore the insn if it's already done (it matched something else).
1704 Otherwise, see if it is now safe to move. */
1708 || (1 == loop_invariant_p (loop, m->set_src)
1709 && (m->dependencies == 0
1710 || 1 == loop_invariant_p (loop, m->dependencies))
1712 || 1 == consec_sets_invariant_p (loop, m->set_dest,
1715 && (! m->forces || m->forces->done))
1719 int savings = m->savings;
1721 /* We have an insn that is safe to move.
1722 Compute its desirability. */
1727 if (loop_dump_stream)
1728 fprintf (loop_dump_stream, "savings %d ", savings);
1730 if (regs->moved_once[regno] && loop_dump_stream)
1731 fprintf (loop_dump_stream, "halved since already moved ");
1733 /* An insn MUST be moved if we already moved something else
1734 which is safe only if this one is moved too: that is,
1735 if already_moved[REGNO] is nonzero. */
1737 /* An insn is desirable to move if the new lifetime of the
1738 register is no more than THRESHOLD times the old lifetime.
1739 If it's not desirable, it means the loop is so big
1740 that moving won't speed things up much,
1741 and it is liable to make register usage worse. */
1743 /* It is also desirable to move if it can be moved at no
1744 extra cost because something else was already moved. */
1746 if (already_moved[regno]
1747 || flag_move_all_movables
1748 || (threshold * savings * m->lifetime) >=
1749 (regs->moved_once[regno] ? insn_count * 2 : insn_count)
1750 || (m->forces && m->forces->done
1751 && VARRAY_INT (regs->n_times_set, m->forces->regno) == 1))
1754 register struct movable *m1;
1755 rtx first = NULL_RTX;
1757 /* Now move the insns that set the reg. */
1759 if (m->partial && m->match)
1763 /* Find the end of this chain of matching regs.
1764 Thus, we load each reg in the chain from that one reg.
1765 And that reg is loaded with 0 directly,
1766 since it has ->match == 0. */
1767 for (m1 = m; m1->match; m1 = m1->match);
1768 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1769 SET_DEST (PATTERN (m1->insn)));
1770 i1 = emit_insn_before (newpat, loop_start);
1772 /* Mark the moved, invariant reg as being allowed to
1773 share a hard reg with the other matching invariant. */
1774 REG_NOTES (i1) = REG_NOTES (m->insn);
1775 r1 = SET_DEST (PATTERN (m->insn));
1776 r2 = SET_DEST (PATTERN (m1->insn));
1778 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1779 gen_rtx_EXPR_LIST (VOIDmode, r2,
1781 delete_insn (m->insn);
1786 if (loop_dump_stream)
1787 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1789 /* If we are to re-generate the item being moved with a
1790 new move insn, first delete what we have and then emit
1791 the move insn before the loop. */
1792 else if (m->move_insn)
1796 for (count = m->consec; count >= 0; count--)
1798 /* If this is the first insn of a library call sequence,
1800 if (GET_CODE (p) != NOTE
1801 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1804 /* If this is the last insn of a libcall sequence, then
1805 delete every insn in the sequence except the last.
1806 The last insn is handled in the normal manner. */
1807 if (GET_CODE (p) != NOTE
1808 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1810 temp = XEXP (temp, 0);
1812 temp = delete_insn (temp);
1816 p = delete_insn (p);
1818 /* simplify_giv_expr expects that it can walk the insns
1819 at m->insn forwards and see this old sequence we are
1820 tossing here. delete_insn does preserve the next
1821 pointers, but when we skip over a NOTE we must fix
1822 it up. Otherwise that code walks into the non-deleted
1824 while (p && GET_CODE (p) == NOTE)
1825 p = NEXT_INSN (temp) = NEXT_INSN (p);
1829 emit_move_insn (m->set_dest, m->set_src);
1830 temp = get_insns ();
1833 add_label_notes (m->set_src, temp);
1835 i1 = emit_insns_before (temp, loop_start);
1836 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1838 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1839 m->set_src, REG_NOTES (i1));
1841 if (loop_dump_stream)
1842 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1844 /* The more regs we move, the less we like moving them. */
1849 for (count = m->consec; count >= 0; count--)
1853 /* If first insn of libcall sequence, skip to end. */
1854 /* Do this at start of loop, since p is guaranteed to
1856 if (GET_CODE (p) != NOTE
1857 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1860 /* If last insn of libcall sequence, move all
1861 insns except the last before the loop. The last
1862 insn is handled in the normal manner. */
1863 if (GET_CODE (p) != NOTE
1864 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1868 rtx fn_address_insn = 0;
1871 for (temp = XEXP (temp, 0); temp != p;
1872 temp = NEXT_INSN (temp))
1878 if (GET_CODE (temp) == NOTE)
1881 body = PATTERN (temp);
1883 /* Find the next insn after TEMP,
1884 not counting USE or NOTE insns. */
1885 for (next = NEXT_INSN (temp); next != p;
1886 next = NEXT_INSN (next))
1887 if (! (GET_CODE (next) == INSN
1888 && GET_CODE (PATTERN (next)) == USE)
1889 && GET_CODE (next) != NOTE)
1892 /* If that is the call, this may be the insn
1893 that loads the function address.
1895 Extract the function address from the insn
1896 that loads it into a register.
1897 If this insn was cse'd, we get incorrect code.
1899 So emit a new move insn that copies the
1900 function address into the register that the
1901 call insn will use. flow.c will delete any
1902 redundant stores that we have created. */
1903 if (GET_CODE (next) == CALL_INSN
1904 && GET_CODE (body) == SET
1905 && GET_CODE (SET_DEST (body)) == REG
1906 && (n = find_reg_note (temp, REG_EQUAL,
1909 fn_reg = SET_SRC (body);
1910 if (GET_CODE (fn_reg) != REG)
1911 fn_reg = SET_DEST (body);
1912 fn_address = XEXP (n, 0);
1913 fn_address_insn = temp;
1915 /* We have the call insn.
1916 If it uses the register we suspect it might,
1917 load it with the correct address directly. */
1918 if (GET_CODE (temp) == CALL_INSN
1920 && reg_referenced_p (fn_reg, body))
1921 emit_insn_after (gen_move_insn (fn_reg,
1925 if (GET_CODE (temp) == CALL_INSN)
1927 i1 = emit_call_insn_before (body, loop_start);
1928 /* Because the USAGE information potentially
1929 contains objects other than hard registers
1930 we need to copy it. */
1931 if (CALL_INSN_FUNCTION_USAGE (temp))
1932 CALL_INSN_FUNCTION_USAGE (i1)
1933 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
1936 i1 = emit_insn_before (body, loop_start);
1939 if (temp == fn_address_insn)
1940 fn_address_insn = i1;
1941 REG_NOTES (i1) = REG_NOTES (temp);
1947 if (m->savemode != VOIDmode)
1949 /* P sets REG to zero; but we should clear only
1950 the bits that are not covered by the mode
1952 rtx reg = m->set_dest;
1958 (GET_MODE (reg), and_optab, reg,
1959 GEN_INT ((((HOST_WIDE_INT) 1
1960 << GET_MODE_BITSIZE (m->savemode)))
1962 reg, 1, OPTAB_LIB_WIDEN);
1966 emit_move_insn (reg, tem);
1967 sequence = gen_sequence ();
1969 i1 = emit_insn_before (sequence, loop_start);
1971 else if (GET_CODE (p) == CALL_INSN)
1973 i1 = emit_call_insn_before (PATTERN (p), loop_start);
1974 /* Because the USAGE information potentially
1975 contains objects other than hard registers
1976 we need to copy it. */
1977 if (CALL_INSN_FUNCTION_USAGE (p))
1978 CALL_INSN_FUNCTION_USAGE (i1)
1979 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
1981 else if (count == m->consec && m->move_insn_first)
1983 /* The SET_SRC might not be invariant, so we must
1984 use the REG_EQUAL note. */
1986 emit_move_insn (m->set_dest, m->set_src);
1987 temp = get_insns ();
1990 add_label_notes (m->set_src, temp);
1992 i1 = emit_insns_before (temp, loop_start);
1993 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1995 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
1997 m->set_src, REG_NOTES (i1));
2000 i1 = emit_insn_before (PATTERN (p), loop_start);
2002 if (REG_NOTES (i1) == 0)
2004 REG_NOTES (i1) = REG_NOTES (p);
2006 /* If there is a REG_EQUAL note present whose value
2007 is not loop invariant, then delete it, since it
2008 may cause problems with later optimization passes.
2009 It is possible for cse to create such notes
2010 like this as a result of record_jump_cond. */
2012 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
2013 && ! loop_invariant_p (loop, XEXP (temp, 0)))
2014 remove_note (i1, temp);
2020 if (loop_dump_stream)
2021 fprintf (loop_dump_stream, " moved to %d",
2024 /* If library call, now fix the REG_NOTES that contain
2025 insn pointers, namely REG_LIBCALL on FIRST
2026 and REG_RETVAL on I1. */
2027 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2029 XEXP (temp, 0) = first;
2030 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2031 XEXP (temp, 0) = i1;
2038 /* simplify_giv_expr expects that it can walk the insns
2039 at m->insn forwards and see this old sequence we are
2040 tossing here. delete_insn does preserve the next
2041 pointers, but when we skip over a NOTE we must fix
2042 it up. Otherwise that code walks into the non-deleted
2044 while (p && GET_CODE (p) == NOTE)
2045 p = NEXT_INSN (temp) = NEXT_INSN (p);
2048 /* The more regs we move, the less we like moving them. */
2052 /* Any other movable that loads the same register
2054 already_moved[regno] = 1;
2056 /* This reg has been moved out of one loop. */
2057 regs->moved_once[regno] = 1;
2059 /* The reg set here is now invariant. */
2061 VARRAY_INT (regs->set_in_loop, regno) = 0;
2065 /* Change the length-of-life info for the register
2066 to say it lives at least the full length of this loop.
2067 This will help guide optimizations in outer loops. */
2069 if (uid_luid[REGNO_FIRST_UID (regno)] > INSN_LUID (loop_start))
2070 /* This is the old insn before all the moved insns.
2071 We can't use the moved insn because it is out of range
2072 in uid_luid. Only the old insns have luids. */
2073 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2074 if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (loop_end))
2075 REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2077 /* Combine with this moved insn any other matching movables. */
2080 for (m1 = movables->head; m1; m1 = m1->next)
2085 /* Schedule the reg loaded by M1
2086 for replacement so that shares the reg of M.
2087 If the modes differ (only possible in restricted
2088 circumstances, make a SUBREG.
2090 Note this assumes that the target dependent files
2091 treat REG and SUBREG equally, including within
2092 GO_IF_LEGITIMATE_ADDRESS and in all the
2093 predicates since we never verify that replacing the
2094 original register with a SUBREG results in a
2095 recognizable insn. */
2096 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2097 reg_map[m1->regno] = m->set_dest;
2100 = gen_lowpart_common (GET_MODE (m1->set_dest),
2103 /* Get rid of the matching insn
2104 and prevent further processing of it. */
2107 /* if library call, delete all insn except last, which
2109 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2112 for (temp = XEXP (temp, 0); temp != m1->insn;
2113 temp = NEXT_INSN (temp))
2116 delete_insn (m1->insn);
2118 /* Any other movable that loads the same register
2120 already_moved[m1->regno] = 1;
2122 /* The reg merged here is now invariant,
2123 if the reg it matches is invariant. */
2125 VARRAY_INT (regs->set_in_loop, m1->regno) = 0;
2128 else if (loop_dump_stream)
2129 fprintf (loop_dump_stream, "not desirable");
2131 else if (loop_dump_stream && !m->match)
2132 fprintf (loop_dump_stream, "not safe");
2134 if (loop_dump_stream)
2135 fprintf (loop_dump_stream, "\n");
2139 new_start = loop_start;
2141 /* Go through all the instructions in the loop, making
2142 all the register substitutions scheduled in REG_MAP. */
2143 for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2144 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2145 || GET_CODE (p) == CALL_INSN)
2147 replace_regs (PATTERN (p), reg_map, nregs, 0);
2148 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2154 free (already_moved);
2158 /* Scan X and replace the address of any MEM in it with ADDR.
2159 REG is the address that MEM should have before the replacement. */
2162 replace_call_address (x, reg, addr)
2165 register enum rtx_code code;
2167 register const char *fmt;
2171 code = GET_CODE (x);
2185 /* Short cut for very common case. */
2186 replace_call_address (XEXP (x, 1), reg, addr);
2190 /* Short cut for very common case. */
2191 replace_call_address (XEXP (x, 0), reg, addr);
2195 /* If this MEM uses a reg other than the one we expected,
2196 something is wrong. */
2197 if (XEXP (x, 0) != reg)
2206 fmt = GET_RTX_FORMAT (code);
2207 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2210 replace_call_address (XEXP (x, i), reg, addr);
2211 else if (fmt[i] == 'E')
2214 for (j = 0; j < XVECLEN (x, i); j++)
2215 replace_call_address (XVECEXP (x, i, j), reg, addr);
2221 /* Return the number of memory refs to addresses that vary
2225 count_nonfixed_reads (loop, x)
2226 const struct loop *loop;
2229 register enum rtx_code code;
2231 register const char *fmt;
2237 code = GET_CODE (x);
2251 return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2252 + count_nonfixed_reads (loop, XEXP (x, 0)));
2259 fmt = GET_RTX_FORMAT (code);
2260 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2263 value += count_nonfixed_reads (loop, XEXP (x, i));
2267 for (j = 0; j < XVECLEN (x, i); j++)
2268 value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2274 /* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
2275 `has_call', `has_volatile', `has_tablejump',
2276 `unknown_address_altered', `unknown_constant_address_altered', and
2277 `num_mem_sets' in LOOP. Also, fill in the array `mems' and the
2278 list `store_mems' in LOOP. */
2284 register int level = 1;
2286 struct loop_info *loop_info = LOOP_INFO (loop);
2287 rtx start = loop->start;
2288 rtx end = loop->end;
2289 /* The label after END. Jumping here is just like falling off the
2290 end of the loop. We use next_nonnote_insn instead of next_label
2291 as a hedge against the (pathological) case where some actual insn
2292 might end up between the two. */
2293 rtx exit_target = next_nonnote_insn (end);
2295 loop_info->has_indirect_jump = indirect_jump_in_function;
2296 loop_info->has_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;
2309 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2310 insn = NEXT_INSN (insn))
2312 if (GET_CODE (insn) == NOTE)
2314 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2317 /* Count number of loops contained in this one. */
2320 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2325 else if (GET_CODE (insn) == CALL_INSN)
2327 if (! CONST_CALL_P (insn))
2328 loop_info->unknown_address_altered = 1;
2329 loop_info->has_call = 1;
2331 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2333 rtx label1 = NULL_RTX;
2334 rtx label2 = NULL_RTX;
2336 if (volatile_refs_p (PATTERN (insn)))
2337 loop_info->has_volatile = 1;
2339 if (GET_CODE (insn) == JUMP_INSN
2340 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2341 || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2342 loop_info->has_tablejump = 1;
2344 note_stores (PATTERN (insn), note_addr_stored, loop_info);
2345 if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2346 loop_info->first_loop_store_insn = insn;
2348 if (! loop_info->has_multiple_exit_targets
2349 && GET_CODE (insn) == JUMP_INSN
2350 && GET_CODE (PATTERN (insn)) == SET
2351 && SET_DEST (PATTERN (insn)) == pc_rtx)
2353 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2355 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2356 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2360 label1 = SET_SRC (PATTERN (insn));
2365 if (label1 && label1 != pc_rtx)
2367 if (GET_CODE (label1) != LABEL_REF)
2369 /* Something tricky. */
2370 loop_info->has_multiple_exit_targets = 1;
2373 else if (XEXP (label1, 0) != exit_target
2374 && LABEL_OUTSIDE_LOOP_P (label1))
2376 /* A jump outside the current loop. */
2377 loop_info->has_multiple_exit_targets = 1;
2388 else if (GET_CODE (insn) == RETURN)
2389 loop_info->has_multiple_exit_targets = 1;
2392 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2393 if (/* An exception thrown by a called function might land us
2395 ! loop_info->has_call
2396 /* We don't want loads for MEMs moved to a location before the
2397 one at which their stack memory becomes allocated. (Note
2398 that this is not a problem for malloc, etc., since those
2399 require actual function calls. */
2400 && ! current_function_calls_alloca
2401 /* There are ways to leave the loop other than falling off the
2403 && ! loop_info->has_multiple_exit_targets)
2404 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2405 insn = NEXT_INSN (insn))
2406 for_each_rtx (&insn, insert_loop_mem, loop_info);
2408 /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
2409 that loop_invariant_p and load_mems can use true_dependence
2410 to determine what is really clobbered. */
2411 if (loop_info->unknown_address_altered)
2413 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2415 loop_info->store_mems
2416 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2418 if (loop_info->unknown_constant_address_altered)
2420 rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
2422 RTX_UNCHANGING_P (mem) = 1;
2423 loop_info->store_mems
2424 = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
2428 /* Scan the function looking for loops. Record the start and end of each loop.
2429 Also mark as invalid loops any loops that contain a setjmp or are branched
2430 to from outside the loop. */
2433 find_and_verify_loops (f, loops)
2435 struct loops *loops;
2440 struct loop *current_loop;
2441 struct loop *next_loop;
2444 num_loops = loops->num;
2446 compute_luids (f, NULL_RTX, 0);
2448 /* If there are jumps to undefined labels,
2449 treat them as jumps out of any/all loops.
2450 This also avoids writing past end of tables when there are no loops. */
2453 /* Find boundaries of loops, mark which loops are contained within
2454 loops, and invalidate loops that have setjmp. */
2457 current_loop = NULL;
2458 for (insn = f; insn; insn = NEXT_INSN (insn))
2460 if (GET_CODE (insn) == NOTE)
2461 switch (NOTE_LINE_NUMBER (insn))
2463 case NOTE_INSN_LOOP_BEG:
2464 next_loop = loops->array + num_loops;
2465 next_loop->num = num_loops;
2467 next_loop->start = insn;
2468 next_loop->outer = current_loop;
2469 current_loop = next_loop;
2472 case NOTE_INSN_SETJMP:
2473 /* In this case, we must invalidate our current loop and any
2475 for (loop = current_loop; loop; loop = loop->outer)
2478 if (loop_dump_stream)
2479 fprintf (loop_dump_stream,
2480 "\nLoop at %d ignored due to setjmp.\n",
2481 INSN_UID (loop->start));
2485 case NOTE_INSN_LOOP_CONT:
2486 current_loop->cont = insn;
2489 case NOTE_INSN_LOOP_VTOP:
2490 current_loop->vtop = insn;
2493 case NOTE_INSN_LOOP_END:
2497 current_loop->end = insn;
2498 current_loop = current_loop->outer;
2505 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2506 enclosing loop, but this doesn't matter. */
2507 uid_loop[INSN_UID (insn)] = current_loop;
2510 /* Any loop containing a label used in an initializer must be invalidated,
2511 because it can be jumped into from anywhere. */
2513 for (label = forced_labels; label; label = XEXP (label, 1))
2515 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2516 loop; loop = loop->outer)
2520 /* Any loop containing a label used for an exception handler must be
2521 invalidated, because it can be jumped into from anywhere. */
2523 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2525 for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
2526 loop; loop = loop->outer)
2530 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2531 loop that it is not contained within, that loop is marked invalid.
2532 If any INSN or CALL_INSN uses a label's address, then the loop containing
2533 that label is marked invalid, because it could be jumped into from
2536 Also look for blocks of code ending in an unconditional branch that
2537 exits the loop. If such a block is surrounded by a conditional
2538 branch around the block, move the block elsewhere (see below) and
2539 invert the jump to point to the code block. This may eliminate a
2540 label in our loop and will simplify processing by both us and a
2541 possible second cse pass. */
2543 for (insn = f; insn; insn = NEXT_INSN (insn))
2546 struct loop *this_loop = uid_loop[INSN_UID (insn)];
2548 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2550 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2553 for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
2554 loop; loop = loop->outer)
2559 if (GET_CODE (insn) != JUMP_INSN)
2562 mark_loop_jump (PATTERN (insn), this_loop);
2564 /* See if this is an unconditional branch outside the loop. */
2566 && (GET_CODE (PATTERN (insn)) == RETURN
2567 || (any_uncondjump_p (insn)
2568 && onlyjump_p (insn)
2569 && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
2571 && get_max_uid () < max_uid_for_loop)
2574 rtx our_next = next_real_insn (insn);
2575 rtx last_insn_to_move = NEXT_INSN (insn);
2576 struct loop *dest_loop;
2577 struct loop *outer_loop = NULL;
2579 /* Go backwards until we reach the start of the loop, a label,
2581 for (p = PREV_INSN (insn);
2582 GET_CODE (p) != CODE_LABEL
2583 && ! (GET_CODE (p) == NOTE
2584 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2585 && GET_CODE (p) != JUMP_INSN;
2589 /* Check for the case where we have a jump to an inner nested
2590 loop, and do not perform the optimization in that case. */
2592 if (JUMP_LABEL (insn))
2594 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
2597 for (outer_loop = dest_loop; outer_loop;
2598 outer_loop = outer_loop->outer)
2599 if (outer_loop == this_loop)
2604 /* Make sure that the target of P is within the current loop. */
2606 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2607 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
2608 outer_loop = this_loop;
2610 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2611 we have a block of code to try to move.
2613 We look backward and then forward from the target of INSN
2614 to find a BARRIER at the same loop depth as the target.
2615 If we find such a BARRIER, we make a new label for the start
2616 of the block, invert the jump in P and point it to that label,
2617 and move the block of code to the spot we found. */
2620 && GET_CODE (p) == JUMP_INSN
2621 && JUMP_LABEL (p) != 0
2622 /* Just ignore jumps to labels that were never emitted.
2623 These always indicate compilation errors. */
2624 && INSN_UID (JUMP_LABEL (p)) != 0
2625 && any_condjump_p (p) && onlyjump_p (p)
2626 && next_real_insn (JUMP_LABEL (p)) == our_next
2627 /* If it's not safe to move the sequence, then we
2629 && insns_safe_to_move_p (p, NEXT_INSN (insn),
2630 &last_insn_to_move))
2633 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2634 struct loop *target_loop = uid_loop[INSN_UID (target)];
2637 for (loc = target; loc; loc = PREV_INSN (loc))
2638 if (GET_CODE (loc) == BARRIER
2639 /* Don't move things inside a tablejump. */
2640 && ((loc2 = next_nonnote_insn (loc)) == 0
2641 || GET_CODE (loc2) != CODE_LABEL
2642 || (loc2 = next_nonnote_insn (loc2)) == 0
2643 || GET_CODE (loc2) != JUMP_INSN
2644 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2645 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2646 && uid_loop[INSN_UID (loc)] == target_loop)
2650 for (loc = target; loc; loc = NEXT_INSN (loc))
2651 if (GET_CODE (loc) == BARRIER
2652 /* Don't move things inside a tablejump. */
2653 && ((loc2 = next_nonnote_insn (loc)) == 0
2654 || GET_CODE (loc2) != CODE_LABEL
2655 || (loc2 = next_nonnote_insn (loc2)) == 0
2656 || GET_CODE (loc2) != JUMP_INSN
2657 || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
2658 && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
2659 && uid_loop[INSN_UID (loc)] == target_loop)
2664 rtx cond_label = JUMP_LABEL (p);
2665 rtx new_label = get_label_after (p);
2667 /* Ensure our label doesn't go away. */
2668 LABEL_NUSES (cond_label)++;
2670 /* Verify that uid_loop is large enough and that
2672 if (invert_jump (p, new_label, 1))
2676 /* If no suitable BARRIER was found, create a suitable
2677 one before TARGET. Since TARGET is a fall through
2678 path, we'll need to insert an jump around our block
2679 and a add a BARRIER before TARGET.
2681 This creates an extra unconditional jump outside
2682 the loop. However, the benefits of removing rarely
2683 executed instructions from inside the loop usually
2684 outweighs the cost of the extra unconditional jump
2685 outside the loop. */
2690 temp = gen_jump (JUMP_LABEL (insn));
2691 temp = emit_jump_insn_before (temp, target);
2692 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2693 LABEL_NUSES (JUMP_LABEL (insn))++;
2694 loc = emit_barrier_before (target);
2697 /* Include the BARRIER after INSN and copy the
2699 new_label = squeeze_notes (new_label,
2701 reorder_insns (new_label, last_insn_to_move, loc);
2703 /* All those insns are now in TARGET_LOOP. */
2705 q != NEXT_INSN (last_insn_to_move);
2707 uid_loop[INSN_UID (q)] = target_loop;
2709 /* The label jumped to by INSN is no longer a loop
2710 exit. Unless INSN does not have a label (e.g.,
2711 it is a RETURN insn), search loop->exit_labels
2712 to find its label_ref, and remove it. Also turn
2713 off LABEL_OUTSIDE_LOOP_P bit. */
2714 if (JUMP_LABEL (insn))
2716 for (q = 0, r = this_loop->exit_labels;
2718 q = r, r = LABEL_NEXTREF (r))
2719 if (XEXP (r, 0) == JUMP_LABEL (insn))
2721 LABEL_OUTSIDE_LOOP_P (r) = 0;
2723 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2725 this_loop->exit_labels = LABEL_NEXTREF (r);
2729 for (loop = this_loop; loop && loop != target_loop;
2733 /* If we didn't find it, then something is
2739 /* P is now a jump outside the loop, so it must be put
2740 in loop->exit_labels, and marked as such.
2741 The easiest way to do this is to just call
2742 mark_loop_jump again for P. */
2743 mark_loop_jump (PATTERN (p), this_loop);
2745 /* If INSN now jumps to the insn after it,
2747 if (JUMP_LABEL (insn) != 0
2748 && (next_real_insn (JUMP_LABEL (insn))
2749 == next_real_insn (insn)))
2753 /* Continue the loop after where the conditional
2754 branch used to jump, since the only branch insn
2755 in the block (if it still remains) is an inter-loop
2756 branch and hence needs no processing. */
2757 insn = NEXT_INSN (cond_label);
2759 if (--LABEL_NUSES (cond_label) == 0)
2760 delete_insn (cond_label);
2762 /* This loop will be continued with NEXT_INSN (insn). */
2763 insn = PREV_INSN (insn);
2770 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2771 loops it is contained in, mark the target loop invalid.
2773 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2776 mark_loop_jump (x, loop)
2780 struct loop *dest_loop;
2781 struct loop *outer_loop;
2784 switch (GET_CODE (x))
2797 /* There could be a label reference in here. */
2798 mark_loop_jump (XEXP (x, 0), loop);
2804 mark_loop_jump (XEXP (x, 0), loop);
2805 mark_loop_jump (XEXP (x, 1), loop);
2809 /* This may refer to a LABEL_REF or SYMBOL_REF. */
2810 mark_loop_jump (XEXP (x, 1), loop);
2815 mark_loop_jump (XEXP (x, 0), loop);
2819 dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
2821 /* Link together all labels that branch outside the loop. This
2822 is used by final_[bg]iv_value and the loop unrolling code. Also
2823 mark this LABEL_REF so we know that this branch should predict
2826 /* A check to make sure the label is not in an inner nested loop,
2827 since this does not count as a loop exit. */
2830 for (outer_loop = dest_loop; outer_loop;
2831 outer_loop = outer_loop->outer)
2832 if (outer_loop == loop)
2838 if (loop && ! outer_loop)
2840 LABEL_OUTSIDE_LOOP_P (x) = 1;
2841 LABEL_NEXTREF (x) = loop->exit_labels;
2842 loop->exit_labels = x;
2844 for (outer_loop = loop;
2845 outer_loop && outer_loop != dest_loop;
2846 outer_loop = outer_loop->outer)
2847 outer_loop->exit_count++;
2850 /* If this is inside a loop, but not in the current loop or one enclosed
2851 by it, it invalidates at least one loop. */
2856 /* We must invalidate every nested loop containing the target of this
2857 label, except those that also contain the jump insn. */
2859 for (; dest_loop; dest_loop = dest_loop->outer)
2861 /* Stop when we reach a loop that also contains the jump insn. */
2862 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2863 if (dest_loop == outer_loop)
2866 /* If we get here, we know we need to invalidate a loop. */
2867 if (loop_dump_stream && ! dest_loop->invalid)
2868 fprintf (loop_dump_stream,
2869 "\nLoop at %d ignored due to multiple entry points.\n",
2870 INSN_UID (dest_loop->start));
2872 dest_loop->invalid = 1;
2877 /* If this is not setting pc, ignore. */
2878 if (SET_DEST (x) == pc_rtx)
2879 mark_loop_jump (SET_SRC (x), loop);
2883 mark_loop_jump (XEXP (x, 1), loop);
2884 mark_loop_jump (XEXP (x, 2), loop);
2889 for (i = 0; i < XVECLEN (x, 0); i++)
2890 mark_loop_jump (XVECEXP (x, 0, i), loop);
2894 for (i = 0; i < XVECLEN (x, 1); i++)
2895 mark_loop_jump (XVECEXP (x, 1, i), loop);
2899 /* Strictly speaking this is not a jump into the loop, only a possible
2900 jump out of the loop. However, we have no way to link the destination
2901 of this jump onto the list of exit labels. To be safe we mark this
2902 loop and any containing loops as invalid. */
2905 for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
2907 if (loop_dump_stream && ! outer_loop->invalid)
2908 fprintf (loop_dump_stream,
2909 "\nLoop at %d ignored due to unknown exit jump.\n",
2910 INSN_UID (outer_loop->start));
2911 outer_loop->invalid = 1;
2918 /* Return nonzero if there is a label in the range from
2919 insn INSN to and including the insn whose luid is END
2920 INSN must have an assigned luid (i.e., it must not have
2921 been previously created by loop.c). */
2924 labels_in_range_p (insn, end)
2928 while (insn && INSN_LUID (insn) <= end)
2930 if (GET_CODE (insn) == CODE_LABEL)
2932 insn = NEXT_INSN (insn);
2938 /* Record that a memory reference X is being set. */
2941 note_addr_stored (x, y, data)
2943 rtx y ATTRIBUTE_UNUSED;
2944 void *data ATTRIBUTE_UNUSED;
2946 struct loop_info *loop_info = data;
2948 if (x == 0 || GET_CODE (x) != MEM)
2951 /* Count number of memory writes.
2952 This affects heuristics in strength_reduce. */
2953 loop_info->num_mem_sets++;
2955 /* BLKmode MEM means all memory is clobbered. */
2956 if (GET_MODE (x) == BLKmode)
2958 if (RTX_UNCHANGING_P (x))
2959 loop_info->unknown_constant_address_altered = 1;
2961 loop_info->unknown_address_altered = 1;
2966 loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
2967 loop_info->store_mems);
2970 /* X is a value modified by an INSN that references a biv inside a loop
2971 exit test (ie, X is somehow related to the value of the biv). If X
2972 is a pseudo that is used more than once, then the biv is (effectively)
2973 used more than once. DATA is a pointer to a loop_regs structure. */
2976 note_set_pseudo_multiple_uses (x, y, data)
2978 rtx y ATTRIBUTE_UNUSED;
2981 struct loop_regs *regs = (struct loop_regs *) data;
2986 while (GET_CODE (x) == STRICT_LOW_PART
2987 || GET_CODE (x) == SIGN_EXTRACT
2988 || GET_CODE (x) == ZERO_EXTRACT
2989 || GET_CODE (x) == SUBREG)
2992 if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
2995 /* If we do not have usage information, or if we know the register
2996 is used more than once, note that fact for check_dbra_loop. */
2997 if (REGNO (x) >= max_reg_before_loop
2998 || ! VARRAY_RTX (regs->single_usage, REGNO (x))
2999 || VARRAY_RTX (regs->single_usage, REGNO (x)) == const0_rtx)
3000 regs->multiple_uses = 1;
3003 /* Return nonzero if the rtx X is invariant over the current loop.
3005 The value is 2 if we refer to something only conditionally invariant.
3007 A memory ref is invariant if it is not volatile and does not conflict
3008 with anything stored in `loop_info->store_mems'. */
3011 loop_invariant_p (loop, x)
3012 const struct loop *loop;
3015 struct loop_info *loop_info = LOOP_INFO (loop);
3016 struct loop_regs *regs = LOOP_REGS (loop);
3018 register enum rtx_code code;
3019 register const char *fmt;
3020 int conditional = 0;
3025 code = GET_CODE (x);
3035 /* A LABEL_REF is normally invariant, however, if we are unrolling
3036 loops, and this label is inside the loop, then it isn't invariant.
3037 This is because each unrolled copy of the loop body will have
3038 a copy of this label. If this was invariant, then an insn loading
3039 the address of this label into a register might get moved outside
3040 the loop, and then each loop body would end up using the same label.
3042 We don't know the loop bounds here though, so just fail for all
3044 if (flag_unroll_loops)
3051 case UNSPEC_VOLATILE:
3055 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3056 since the reg might be set by initialization within the loop. */
3058 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3059 || x == arg_pointer_rtx)
3060 && ! current_function_has_nonlocal_goto)
3063 if (LOOP_INFO (loop)->has_call
3064 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3067 if (VARRAY_INT (regs->set_in_loop, REGNO (x)) < 0)
3070 return VARRAY_INT (regs->set_in_loop, REGNO (x)) == 0;
3073 /* Volatile memory references must be rejected. Do this before
3074 checking for read-only items, so that volatile read-only items
3075 will be rejected also. */
3076 if (MEM_VOLATILE_P (x))
3079 /* See if there is any dependence between a store and this load. */
3080 mem_list_entry = loop_info->store_mems;
3081 while (mem_list_entry)
3083 if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
3087 mem_list_entry = XEXP (mem_list_entry, 1);
3090 /* It's not invalidated by a store in memory
3091 but we must still verify the address is invariant. */
3095 /* Don't mess with insns declared volatile. */
3096 if (MEM_VOLATILE_P (x))
3104 fmt = GET_RTX_FORMAT (code);
3105 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3109 int tem = loop_invariant_p (loop, XEXP (x, i));
3115 else if (fmt[i] == 'E')
3118 for (j = 0; j < XVECLEN (x, i); j++)
3120 int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
3130 return 1 + conditional;
3133 /* Return nonzero if all the insns in the loop that set REG
3134 are INSN and the immediately following insns,
3135 and if each of those insns sets REG in an invariant way
3136 (not counting uses of REG in them).
3138 The value is 2 if some of these insns are only conditionally invariant.
3140 We assume that INSN itself is the first set of REG
3141 and that its source is invariant. */
3144 consec_sets_invariant_p (loop, reg, n_sets, insn)
3145 const struct loop *loop;
3149 struct loop_regs *regs = LOOP_REGS (loop);
3151 unsigned int regno = REGNO (reg);
3153 /* Number of sets we have to insist on finding after INSN. */
3154 int count = n_sets - 1;
3155 int old = VARRAY_INT (regs->set_in_loop, regno);
3159 /* If N_SETS hit the limit, we can't rely on its value. */
3163 VARRAY_INT (regs->set_in_loop, regno) = 0;
3167 register enum rtx_code code;
3171 code = GET_CODE (p);
3173 /* If library call, skip to end of it. */
3174 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3179 && (set = single_set (p))
3180 && GET_CODE (SET_DEST (set)) == REG
3181 && REGNO (SET_DEST (set)) == regno)
3183 this = loop_invariant_p (loop, SET_SRC (set));
3186 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3188 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3189 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3191 this = (CONSTANT_P (XEXP (temp, 0))
3192 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3193 && loop_invariant_p (loop, XEXP (temp, 0))));
3200 else if (code != NOTE)
3202 VARRAY_INT (regs->set_in_loop, regno) = old;
3207 VARRAY_INT (regs->set_in_loop, regno) = old;
3208 /* If loop_invariant_p ever returned 2, we return 2. */
3209 return 1 + (value & 2);
3213 /* I don't think this condition is sufficient to allow INSN
3214 to be moved, so we no longer test it. */
3216 /* Return 1 if all insns in the basic block of INSN and following INSN
3217 that set REG are invariant according to TABLE. */
3220 all_sets_invariant_p (reg, insn, table)
3224 register rtx p = insn;
3225 register int regno = REGNO (reg);
3229 register enum rtx_code code;
3231 code = GET_CODE (p);
3232 if (code == CODE_LABEL || code == JUMP_INSN)
3234 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3235 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3236 && REGNO (SET_DEST (PATTERN (p))) == regno)
3238 if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
3245 /* Look at all uses (not sets) of registers in X. For each, if it is
3246 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3247 a different insn, set USAGE[REGNO] to const0_rtx. */
3250 find_single_use_in_loop (insn, x, usage)
3255 enum rtx_code code = GET_CODE (x);
3256 const char *fmt = GET_RTX_FORMAT (code);
3260 VARRAY_RTX (usage, REGNO (x))
3261 = (VARRAY_RTX (usage, REGNO (x)) != 0
3262 && VARRAY_RTX (usage, REGNO (x)) != insn)
3263 ? const0_rtx : insn;
3265 else if (code == SET)
3267 /* Don't count SET_DEST if it is a REG; otherwise count things
3268 in SET_DEST because if a register is partially modified, it won't
3269 show up as a potential movable so we don't care how USAGE is set
3271 if (GET_CODE (SET_DEST (x)) != REG)
3272 find_single_use_in_loop (insn, SET_DEST (x), usage);
3273 find_single_use_in_loop (insn, SET_SRC (x), usage);
3276 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3278 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3279 find_single_use_in_loop (insn, XEXP (x, i), usage);
3280 else if (fmt[i] == 'E')
3281 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3282 find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
3286 /* Count and record any set in X which is contained in INSN. Update
3287 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3290 count_one_set (regs, insn, x, may_not_move, last_set)
3291 struct loop_regs *regs;
3293 varray_type may_not_move;
3296 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3297 /* Don't move a reg that has an explicit clobber.
3298 It's not worth the pain to try to do it correctly. */
3299 VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
3301 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3303 rtx dest = SET_DEST (x);
3304 while (GET_CODE (dest) == SUBREG
3305 || GET_CODE (dest) == ZERO_EXTRACT
3306 || GET_CODE (dest) == SIGN_EXTRACT
3307 || GET_CODE (dest) == STRICT_LOW_PART)
3308 dest = XEXP (dest, 0);
3309 if (GET_CODE (dest) == REG)
3311 register int regno = REGNO (dest);
3312 /* If this is the first setting of this reg
3313 in current basic block, and it was set before,
3314 it must be set in two basic blocks, so it cannot
3315 be moved out of the loop. */
3316 if (VARRAY_INT (regs->set_in_loop, regno) > 0
3317 && last_set[regno] == 0)
3318 VARRAY_CHAR (may_not_move, regno) = 1;
3319 /* If this is not first setting in current basic block,
3320 see if reg was used in between previous one and this.
3321 If so, neither one can be moved. */
3322 if (last_set[regno] != 0
3323 && reg_used_between_p (dest, last_set[regno], insn))
3324 VARRAY_CHAR (may_not_move, regno) = 1;
3325 if (VARRAY_INT (regs->set_in_loop, regno) < 127)
3326 ++VARRAY_INT (regs->set_in_loop, regno);
3327 last_set[regno] = insn;
3332 /* Increment REGS->SET_IN_LOOP at the index of each register
3333 that is modified by an insn between FROM and TO.
3334 If the value of an element of REGS->SET_IN_LOOP becomes 127 or more,
3335 stop incrementing it, to avoid overflow.
3337 Store in SINGLE_USAGE[I] the single insn in which register I is
3338 used, if it is only used once. Otherwise, it is set to 0 (for no
3339 uses) or const0_rtx for more than one use. This parameter may be zero,
3340 in which case this processing is not done.
3342 Store in *COUNT_PTR the number of actual instruction
3343 in the loop. We use this to decide what is worth moving out. */
3345 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3346 In that case, it is the insn that last set reg n. */
3349 count_loop_regs_set (loop, may_not_move, single_usage, count_ptr, nregs)
3350 const struct loop *loop;
3351 varray_type may_not_move;
3352 varray_type single_usage;
3356 struct loop_regs *regs = LOOP_REGS (loop);
3357 register rtx *last_set = (rtx *) xcalloc (nregs, sizeof (rtx));
3359 register int count = 0;
3361 for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
3362 insn = NEXT_INSN (insn))
3368 /* Record registers that have exactly one use. */
3369 find_single_use_in_loop (insn, PATTERN (insn), single_usage);
3371 /* Include uses in REG_EQUAL notes. */
3372 if (REG_NOTES (insn))
3373 find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
3375 if (GET_CODE (PATTERN (insn)) == SET
3376 || GET_CODE (PATTERN (insn)) == CLOBBER)
3377 count_one_set (regs, insn, PATTERN (insn), may_not_move, last_set);
3378 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3381 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3382 count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
3383 may_not_move, last_set);
3387 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
3388 bzero ((char *) last_set, nregs * sizeof (rtx));
3396 /* Given a loop that is bounded by LOOP->START and LOOP->END and that
3397 is entered at LOOP->SCAN_START, return 1 if the register set in SET
3398 contained in insn INSN is used by any insn that precedes INSN in
3399 cyclic order starting from the loop entry point.
3401 We don't want to use INSN_LUID here because if we restrict INSN to those
3402 that have a valid INSN_LUID, it means we cannot move an invariant out
3403 from an inner loop past two loops. */
3406 loop_reg_used_before_p (loop, set, insn)
3407 const struct loop *loop;
3410 rtx reg = SET_DEST (set);
3413 /* Scan forward checking for register usage. If we hit INSN, we
3414 are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
3415 for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
3417 if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
3427 /* A "basic induction variable" or biv is a pseudo reg that is set
3428 (within this loop) only by incrementing or decrementing it. */
3429 /* A "general induction variable" or giv is a pseudo reg whose
3430 value is a linear function of a biv. */
3432 /* Bivs are recognized by `basic_induction_var';
3433 Givs by `general_induction_var'. */
3435 /* Communication with routines called via `note_stores'. */
3437 static rtx note_insn;
3439 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3441 static rtx addr_placeholder;
3443 /* ??? Unfinished optimizations, and possible future optimizations,
3444 for the strength reduction code. */
3446 /* ??? The interaction of biv elimination, and recognition of 'constant'
3447 bivs, may cause problems. */
3449 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3450 performance problems.
3452 Perhaps don't eliminate things that can be combined with an addressing
3453 mode. Find all givs that have the same biv, mult_val, and add_val;
3454 then for each giv, check to see if its only use dies in a following
3455 memory address. If so, generate a new memory address and check to see
3456 if it is valid. If it is valid, then store the modified memory address,
3457 otherwise, mark the giv as not done so that it will get its own iv. */
3459 /* ??? Could try to optimize branches when it is known that a biv is always
3462 /* ??? When replace a biv in a compare insn, we should replace with closest
3463 giv so that an optimized branch can still be recognized by the combiner,
3464 e.g. the VAX acb insn. */
3466 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3467 was rerun in loop_optimize whenever a register was added or moved.
3468 Also, some of the optimizations could be a little less conservative. */
3470 /* Scan the loop body and call FNCALL for each insn. In the addition to the
3471 LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
3474 NOT_EVERY_ITERATION if current insn is not executed at least once for every
3475 loop iteration except for the last one.
3477 MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
3481 for_each_insn_in_loop (loop, fncall)
3483 loop_insn_callback fncall;
3485 /* This is 1 if current insn is not executed at least once for every loop
3487 int not_every_iteration = 0;
3488 int maybe_multiple = 0;
3489 int past_loop_latch = 0;
3493 /* If loop_scan_start points to the loop exit test, we have to be wary of
3494 subversive use of gotos inside expression statements. */
3495 if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
3496 maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
3498 /* Scan through loop to find all possible bivs. */
3500 for (p = next_insn_in_loop (loop, loop->scan_start);
3502 p = next_insn_in_loop (loop, p))
3504 p = fncall (loop, p, not_every_iteration, maybe_multiple);
3506 /* Past CODE_LABEL, we get to insns that may be executed multiple
3507 times. The only way we can be sure that they can't is if every
3508 jump insn between here and the end of the loop either
3509 returns, exits the loop, is a jump to a location that is still
3510 behind the label, or is a jump to the loop start. */
3512 if (GET_CODE (p) == CODE_LABEL)
3520 insn = NEXT_INSN (insn);
3521 if (insn == loop->scan_start)
3523 if (insn == loop->end)
3529 if (insn == loop->scan_start)
3533 if (GET_CODE (insn) == JUMP_INSN
3534 && GET_CODE (PATTERN (insn)) != RETURN
3535 && (!any_condjump_p (insn)
3536 || (JUMP_LABEL (insn) != 0
3537 && JUMP_LABEL (insn) != loop->scan_start
3538 && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
3546 /* Past a jump, we get to insns for which we can't count
3547 on whether they will be executed during each iteration. */
3548 /* This code appears twice in strength_reduce. There is also similar
3549 code in scan_loop. */
3550 if (GET_CODE (p) == JUMP_INSN
3551 /* If we enter the loop in the middle, and scan around to the
3552 beginning, don't set not_every_iteration for that.
3553 This can be any kind of jump, since we want to know if insns
3554 will be executed if the loop is executed. */
3555 && !(JUMP_LABEL (p) == loop->top
3556 && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
3557 && any_uncondjump_p (p))
3558 || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
3562 /* If this is a jump outside the loop, then it also doesn't
3563 matter. Check to see if the target of this branch is on the
3564 loop->exits_labels list. */
3566 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
3567 if (XEXP (label, 0) == JUMP_LABEL (p))
3571 not_every_iteration = 1;
3574 else if (GET_CODE (p) == NOTE)
3576 /* At the virtual top of a converted loop, insns are again known to
3577 be executed each iteration: logically, the loop begins here
3578 even though the exit code has been duplicated.
3580 Insns are also again known to be executed each iteration at
3581 the LOOP_CONT note. */
3582 if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
3583 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
3585 not_every_iteration = 0;
3586 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3588 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3592 /* Note if we pass a loop latch. If we do, then we can not clear
3593 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
3594 a loop since a jump before the last CODE_LABEL may have started
3595 a new loop iteration.
3597 Note that LOOP_TOP is only set for rotated loops and we need
3598 this check for all loops, so compare against the CODE_LABEL
3599 which immediately follows LOOP_START. */
3600 if (GET_CODE (p) == JUMP_INSN
3601 && JUMP_LABEL (p) == NEXT_INSN (loop->start))
3602 past_loop_latch = 1;
3604 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3605 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3606 or not an insn is known to be executed each iteration of the
3607 loop, whether or not any iterations are known to occur.
3609 Therefore, if we have just passed a label and have no more labels
3610 between here and the test insn of the loop, and we have not passed
3611 a jump to the top of the loop, then we know these insns will be
3612 executed each iteration. */
3614 if (not_every_iteration
3616 && GET_CODE (p) == CODE_LABEL
3617 && no_labels_between_p (p, loop->end)
3618 && loop_insn_first_p (p, loop->cont))
3619 not_every_iteration = 0;
3623 /* Perform strength reduction and induction variable elimination.
3625 Pseudo registers created during this function will be beyond the
3626 last valid index in several tables including regs->n_times_set and
3627 regno_last_uid. This does not cause a problem here, because the
3628 added registers cannot be givs outside of their loop, and hence
3629 will never be reconsidered. But scan_loop must check regnos to
3630 make sure they are in bounds. */
3633 strength_reduce (loop, insn_count, flags)
3638 struct loop_info *loop_info = LOOP_INFO (loop);
3639 struct loop_regs *regs = LOOP_REGS (loop);
3640 struct loop_ivs *ivs = LOOP_IVS (loop);
3642 /* Temporary list pointers for traversing ivs->loop_iv_list. */
3643 struct iv_class *bl, **backbl;
3644 /* Ratio of extra register life span we can justify
3645 for saving an instruction. More if loop doesn't call subroutines
3646 since in that case saving an insn makes more difference
3647 and more registers are available. */
3648 /* ??? could set this to last value of threshold in move_movables */
3649 int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3650 /* Map of pseudo-register replacements. */
3651 rtx *reg_map = NULL;
3655 rtx end_insert_before;
3656 int unrolled_insn_copies = 0;
3657 rtx loop_start = loop->start;
3658 rtx loop_end = loop->end;
3659 rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
3661 VARRAY_INT_INIT (ivs->reg_iv_type, max_reg_before_loop, "reg_iv_type");
3662 VARRAY_GENERIC_PTR_INIT (ivs->reg_iv_info, max_reg_before_loop, "reg_iv_info");
3663 ivs->reg_biv_class = (struct iv_class **)
3664 xcalloc (max_reg_before_loop, sizeof (struct iv_class *));
3666 ivs->loop_iv_list = 0;
3667 addr_placeholder = gen_reg_rtx (Pmode);
3669 /* Save insn immediately after the loop_end. Insns inserted after loop_end
3670 must be put before this insn, so that they will appear in the right
3671 order (i.e. loop order).
3673 If loop_end is the end of the current function, then emit a
3674 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
3676 if (NEXT_INSN (loop_end) != 0)
3677 end_insert_before = NEXT_INSN (loop_end);
3679 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
3681 for_each_insn_in_loop (loop, check_insn_for_bivs);
3683 /* Scan ivs->loop_iv_list to remove all regs that proved not to be bivs.
3684 Make a sanity check against regs->n_times_set. */
3685 for (backbl = &ivs->loop_iv_list, bl = *backbl; bl; bl = bl->next)
3687 if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3688 /* Above happens if register modified by subreg, etc. */
3689 /* Make sure it is not recognized as a basic induction var: */
3690 || VARRAY_INT (regs->n_times_set, bl->regno) != bl->biv_count
3691 /* If never incremented, it is invariant that we decided not to
3692 move. So leave it alone. */
3693 || ! bl->incremented)
3695 if (loop_dump_stream)
3696 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3698 (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
3699 ? "not induction variable"
3700 : (! bl->incremented ? "never incremented"
3703 REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
3710 if (loop_dump_stream)
3711 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3715 /* Exit if there are no bivs. */
3716 if (! ivs->loop_iv_list)
3718 /* Can still unroll the loop anyways, but indicate that there is no
3719 strength reduction info available. */
3720 if (flags & LOOP_UNROLL)
3721 unroll_loop (loop, insn_count, end_insert_before, 0);
3726 /* Find initial value for each biv by searching backwards from loop_start,
3727 halting at first label. Also record any test condition. */
3730 for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3734 if (GET_CODE (p) == CALL_INSN)
3738 note_stores (PATTERN (p), record_initial, ivs);
3740 /* Record any test of a biv that branches around the loop if no store
3741 between it and the start of loop. We only care about tests with
3742 constants and registers and only certain of those. */
3743 if (GET_CODE (p) == JUMP_INSN
3744 && JUMP_LABEL (p) != 0
3745 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3746 && (test = get_condition_for_loop (loop, p)) != 0
3747 && GET_CODE (XEXP (test, 0)) == REG
3748 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3749 && (bl = ivs->reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3750 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3751 && bl->init_insn == 0)
3753 /* If an NE test, we have an initial value! */
3754 if (GET_CODE (test) == NE)
3757 bl->init_set = gen_rtx_SET (VOIDmode,
3758 XEXP (test, 0), XEXP (test, 1));
3761 bl->initial_test = test;
3765 /* Look at the each biv and see if we can say anything better about its
3766 initial value from any initializing insns set up above. (This is done
3767 in two passes to avoid missing SETs in a PARALLEL.) */
3768 for (backbl = &ivs->loop_iv_list; (bl = *backbl); backbl = &bl->next)
3773 if (! bl->init_insn)
3776 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3777 is a constant, use the value of that. */
3778 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3779 && CONSTANT_P (XEXP (note, 0)))
3780 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3781 && CONSTANT_P (XEXP (note, 0))))
3782 src = XEXP (note, 0);
3784 src = SET_SRC (bl->init_set);
3786 if (loop_dump_stream)
3787 fprintf (loop_dump_stream,
3788 "Biv %d initialized at insn %d: initial value ",
3789 bl->regno, INSN_UID (bl->init_insn));
3791 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3792 || GET_MODE (src) == VOIDmode)
3793 && valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3795 bl->initial_value = src;
3797 if (loop_dump_stream)
3799 if (GET_CODE (src) == CONST_INT)
3801 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (src));
3802 fputc ('\n', loop_dump_stream);
3806 print_rtl (loop_dump_stream, src);
3807 fprintf (loop_dump_stream, "\n");
3811 /* If we can't make it a giv,
3812 let biv keep initial value of "itself". */
3813 else if (loop_dump_stream)
3814 fprintf (loop_dump_stream, "is complex\n");
3817 /* Search the loop for general induction variables. */
3819 for_each_insn_in_loop (loop, check_insn_for_givs);
3821 /* Try to calculate and save the number of loop iterations. This is
3822 set to zero if the actual number can not be calculated. This must
3823 be called after all giv's have been identified, since otherwise it may
3824 fail if the iteration variable is a giv. */
3826 loop_iterations (loop);
3828 /* Now for each giv for which we still don't know whether or not it is
3829 replaceable, check to see if it is replaceable because its final value
3830 can be calculated. This must be done after loop_iterations is called,
3831 so that final_giv_value will work correctly. */
3833 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3835 struct induction *v;
3837 for (v = bl->giv; v; v = v->next_iv)
3838 if (! v->replaceable && ! v->not_replaceable)
3839 check_final_value (loop, v);
3842 /* Try to prove that the loop counter variable (if any) is always
3843 nonnegative; if so, record that fact with a REG_NONNEG note
3844 so that "decrement and branch until zero" insn can be used. */
3845 check_dbra_loop (loop, insn_count);
3847 /* Create reg_map to hold substitutions for replaceable giv regs.
3848 Some givs might have been made from biv increments, so look at
3849 ivs->reg_iv_type for a suitable size. */
3850 reg_map_size = ivs->reg_iv_type->num_elements;
3851 reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
3853 /* Examine each iv class for feasibility of strength reduction/induction
3854 variable elimination. */
3856 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
3858 struct induction *v;
3861 rtx final_value = 0;
3863 /* Test whether it will be possible to eliminate this biv
3864 provided all givs are reduced. This is possible if either
3865 the reg is not used outside the loop, or we can compute
3866 what its final value will be.
3868 For architectures with a decrement_and_branch_until_zero insn,
3869 don't do this if we put a REG_NONNEG note on the endtest for
3872 /* Compare against bl->init_insn rather than loop_start.
3873 We aren't concerned with any uses of the biv between
3874 init_insn and loop_start since these won't be affected
3875 by the value of the biv elsewhere in the function, so
3876 long as init_insn doesn't use the biv itself.
3877 March 14, 1989 -- self@bayes.arc.nasa.gov */
3879 if ((uid_luid[REGNO_LAST_UID (bl->regno)] < INSN_LUID (loop_end)
3881 && INSN_UID (bl->init_insn) < max_uid_for_loop
3882 && uid_luid[REGNO_FIRST_UID (bl->regno)] >= INSN_LUID (bl->init_insn)
3883 #ifdef HAVE_decrement_and_branch_until_zero
3886 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3887 || ((final_value = final_biv_value (loop, bl))
3888 #ifdef HAVE_decrement_and_branch_until_zero
3892 bl->eliminable = maybe_eliminate_biv (loop, bl, 0, threshold,
3896 if (loop_dump_stream)
3898 fprintf (loop_dump_stream,
3899 "Cannot eliminate biv %d.\n",
3901 fprintf (loop_dump_stream,
3902 "First use: insn %d, last use: insn %d.\n",
3903 REGNO_FIRST_UID (bl->regno),
3904 REGNO_LAST_UID (bl->regno));
3908 /* Check each extension dependant giv in this class to see if its
3909 root biv is safe from wrapping in the interior mode. */
3910 check_ext_dependant_givs (bl, loop_info);
3912 /* Combine all giv's for this iv_class. */
3913 combine_givs (regs, bl);
3915 /* This will be true at the end, if all givs which depend on this
3916 biv have been strength reduced.
3917 We can't (currently) eliminate the biv unless this is so. */
3920 /* Check each giv in this class to see if we will benefit by reducing
3921 it. Skip giv's combined with others. */
3922 for (v = bl->giv; v; v = v->next_iv)
3924 struct induction *tv;
3927 if (v->ignore || v->same)
3930 benefit = v->benefit;
3931 PUT_MODE (test_reg, v->mode);
3932 add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
3933 test_reg, test_reg);
3935 /* Reduce benefit if not replaceable, since we will insert
3936 a move-insn to replace the insn that calculates this giv.
3937 Don't do this unless the giv is a user variable, since it
3938 will often be marked non-replaceable because of the duplication
3939 of the exit code outside the loop. In such a case, the copies
3940 we insert are dead and will be deleted. So they don't have
3941 a cost. Similar situations exist. */
3942 /* ??? The new final_[bg]iv_value code does a much better job
3943 of finding replaceable giv's, and hence this code may no longer
3945 if (! v->replaceable && ! bl->eliminable
3946 && REG_USERVAR_P (v->dest_reg))
3947 benefit -= copy_cost;
3949 /* Decrease the benefit to count the add-insns that we will
3950 insert to increment the reduced reg for the giv.
3951 ??? This can overestimate the run-time cost of the additional
3952 insns, e.g. if there are multiple basic blocks that increment
3953 the biv, but only one of these blocks is executed during each
3954 iteration. There is no good way to detect cases like this with
3955 the current structure of the loop optimizer.
3956 This code is more accurate for determining code size than
3957 run-time benefits. */
3958 benefit -= add_cost * bl->biv_count;
3960 /* Decide whether to strength-reduce this giv or to leave the code
3961 unchanged (recompute it from the biv each time it is used).
3962 This decision can be made independently for each giv. */
3965 /* Attempt to guess whether autoincrement will handle some of the
3966 new add insns; if so, increase BENEFIT (undo the subtraction of
3967 add_cost that was done above). */
3968 if (v->giv_type == DEST_ADDR
3969 /* Increasing the benefit is risky, since this is only a guess.
3970 Avoid increasing register pressure in cases where there would
3971 be no other benefit from reducing this giv. */
3973 && GET_CODE (v->mult_val) == CONST_INT)
3975 if (HAVE_POST_INCREMENT
3976 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3977 benefit += add_cost * bl->biv_count;
3978 else if (HAVE_PRE_INCREMENT
3979 && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3980 benefit += add_cost * bl->biv_count;
3981 else if (HAVE_POST_DECREMENT
3982 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3983 benefit += add_cost * bl->biv_count;
3984 else if (HAVE_PRE_DECREMENT
3985 && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
3986 benefit += add_cost * bl->biv_count;
3990 /* If an insn is not to be strength reduced, then set its ignore
3991 flag, and clear all_reduced. */
3993 /* A giv that depends on a reversed biv must be reduced if it is
3994 used after the loop exit, otherwise, it would have the wrong
3995 value after the loop exit. To make it simple, just reduce all
3996 of such giv's whether or not we know they are used after the loop
3999 if ( ! flag_reduce_all_givs && v->lifetime * threshold * benefit < insn_count
4002 if (loop_dump_stream)
4003 fprintf (loop_dump_stream,
4004 "giv of insn %d not worth while, %d vs %d.\n",
4006 v->lifetime * threshold * benefit, insn_count);
4012 /* Check that we can increment the reduced giv without a
4013 multiply insn. If not, reject it. */
4015 for (tv = bl->biv; tv; tv = tv->next_iv)
4016 if (tv->mult_val == const1_rtx
4017 && ! product_cheap_p (tv->add_val, v->mult_val))
4019 if (loop_dump_stream)
4020 fprintf (loop_dump_stream,
4021 "giv of insn %d: would need a multiply.\n",
4022 INSN_UID (v->insn));
4030 /* Check for givs whose first use is their definition and whose
4031 last use is the definition of another giv. If so, it is likely
4032 dead and should not be used to derive another giv nor to
4034 for (v = bl->giv; v; v = v->next_iv)
4037 || (v->same && v->same->ignore))
4040 if (v->giv_type == DEST_REG
4041 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4043 struct induction *v1;
4045 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4046 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4051 /* Reduce each giv that we decided to reduce. */
4053 for (v = bl->giv; v; v = v->next_iv)
4055 struct induction *tv;
4056 if (! v->ignore && v->same == 0)
4058 int auto_inc_opt = 0;
4060 /* If the code for derived givs immediately below has already
4061 allocated a new_reg, we must keep it. */
4063 v->new_reg = gen_reg_rtx (v->mode);
4066 /* If the target has auto-increment addressing modes, and
4067 this is an address giv, then try to put the increment
4068 immediately after its use, so that flow can create an
4069 auto-increment addressing mode. */
4070 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
4071 && bl->biv->always_executed && ! bl->biv->maybe_multiple
4072 /* We don't handle reversed biv's because bl->biv->insn
4073 does not have a valid INSN_LUID. */
4075 && v->always_executed && ! v->maybe_multiple
4076 && INSN_UID (v->insn) < max_uid_for_loop)
4078 /* If other giv's have been combined with this one, then
4079 this will work only if all uses of the other giv's occur
4080 before this giv's insn. This is difficult to check.
4082 We simplify this by looking for the common case where
4083 there is one DEST_REG giv, and this giv's insn is the
4084 last use of the dest_reg of that DEST_REG giv. If the
4085 increment occurs after the address giv, then we can
4086 perform the optimization. (Otherwise, the increment
4087 would have to go before other_giv, and we would not be
4088 able to combine it with the address giv to get an
4089 auto-inc address.) */
4090 if (v->combined_with)
4092 struct induction *other_giv = 0;
4094 for (tv = bl->giv; tv; tv = tv->next_iv)
4102 if (! tv && other_giv
4103 && REGNO (other_giv->dest_reg) < max_reg_before_loop
4104 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
4105 == INSN_UID (v->insn))
4106 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
4109 /* Check for case where increment is before the address
4110 giv. Do this test in "loop order". */
4111 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
4112 && (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
4113 || (INSN_LUID (bl->biv->insn)
4114 > INSN_LUID (loop->scan_start))))
4115 || (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
4116 && (INSN_LUID (loop->scan_start)
4117 < INSN_LUID (bl->biv->insn))))
4126 /* We can't put an insn immediately after one setting
4127 cc0, or immediately before one using cc0. */
4128 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
4129 || (auto_inc_opt == -1
4130 && (prev = prev_nonnote_insn (v->insn)) != 0
4132 && sets_cc0_p (PATTERN (prev))))
4138 v->auto_inc_opt = 1;
4142 /* For each place where the biv is incremented, add an insn
4143 to increment the new, reduced reg for the giv. */
4144 for (tv = bl->biv; tv; tv = tv->next_iv)
4149 insert_before = tv->insn;
4150 else if (auto_inc_opt == 1)
4151 insert_before = NEXT_INSN (v->insn);
4153 insert_before = v->insn;
4155 if (tv->mult_val == const1_rtx)
4156 emit_iv_add_mult (tv->add_val, v->mult_val,
4157 v->new_reg, v->new_reg, insert_before);
4158 else /* tv->mult_val == const0_rtx */
4159 /* A multiply is acceptable here
4160 since this is presumed to be seldom executed. */
4161 emit_iv_add_mult (tv->add_val, v->mult_val,
4162 v->add_val, v->new_reg, insert_before);
4165 /* Add code at loop start to initialize giv's reduced reg. */
4167 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4168 v->mult_val, v->add_val, v->new_reg,
4173 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4176 For each giv register that can be reduced now: if replaceable,
4177 substitute reduced reg wherever the old giv occurs;
4178 else add new move insn "giv_reg = reduced_reg". */
4180 for (v = bl->giv; v; v = v->next_iv)
4182 if (v->same && v->same->ignore)
4188 /* Update expression if this was combined, in case other giv was
4191 v->new_reg = replace_rtx (v->new_reg,
4192 v->same->dest_reg, v->same->new_reg);
4194 if (v->giv_type == DEST_ADDR)
4195 /* Store reduced reg as the address in the memref where we found
4197 validate_change (v->insn, v->location, v->new_reg, 0);
4198 else if (v->replaceable)
4200 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4203 /* I can no longer duplicate the original problem. Perhaps
4204 this is unnecessary now? */
4206 /* Replaceable; it isn't strictly necessary to delete the old
4207 insn and emit a new one, because v->dest_reg is now dead.
4209 However, especially when unrolling loops, the special
4210 handling for (set REG0 REG1) in the second cse pass may
4211 make v->dest_reg live again. To avoid this problem, emit
4212 an insn to set the original giv reg from the reduced giv.
4213 We can not delete the original insn, since it may be part
4214 of a LIBCALL, and the code in flow that eliminates dead
4215 libcalls will fail if it is deleted. */
4216 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4222 /* Not replaceable; emit an insn to set the original giv reg from
4223 the reduced giv, same as above. */
4224 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4228 /* When a loop is reversed, givs which depend on the reversed
4229 biv, and which are live outside the loop, must be set to their
4230 correct final value. This insn is only needed if the giv is
4231 not replaceable. The correct final value is the same as the
4232 value that the giv starts the reversed loop with. */
4233 if (bl->reversed && ! v->replaceable)
4234 emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
4235 v->mult_val, v->add_val, v->dest_reg,
4237 else if (v->final_value)
4241 /* If the loop has multiple exits, emit the insn before the
4242 loop to ensure that it will always be executed no matter
4243 how the loop exits. Otherwise, emit the insn after the loop,
4244 since this is slightly more efficient. */
4245 if (loop->exit_count)
4246 insert_before = loop_start;
4248 insert_before = end_insert_before;
4249 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4253 /* If the insn to set the final value of the giv was emitted
4254 before the loop, then we must delete the insn inside the loop
4255 that sets it. If this is a LIBCALL, then we must delete
4256 every insn in the libcall. Note, however, that
4257 final_giv_value will only succeed when there are multiple
4258 exits if the giv is dead at each exit, hence it does not
4259 matter that the original insn remains because it is dead
4261 /* Delete the insn inside the loop that sets the giv since
4262 the giv is now set before (or after) the loop. */
4263 delete_insn (v->insn);
4267 if (loop_dump_stream)
4269 fprintf (loop_dump_stream, "giv at %d reduced to ",
4270 INSN_UID (v->insn));
4271 print_rtl (loop_dump_stream, v->new_reg);
4272 fprintf (loop_dump_stream, "\n");
4276 /* All the givs based on the biv bl have been reduced if they
4279 /* For each giv not marked as maybe dead that has been combined with a
4280 second giv, clear any "maybe dead" mark on that second giv.
4281 v->new_reg will either be or refer to the register of the giv it
4284 Doing this clearing avoids problems in biv elimination where a
4285 giv's new_reg is a complex value that can't be put in the insn but
4286 the giv combined with (with a reg as new_reg) is marked maybe_dead.
4287 Since the register will be used in either case, we'd prefer it be
4288 used from the simpler giv. */
4290 for (v = bl->giv; v; v = v->next_iv)
4291 if (! v->maybe_dead && v->same)
4292 v->same->maybe_dead = 0;
4294 /* Try to eliminate the biv, if it is a candidate.
4295 This won't work if ! all_reduced,
4296 since the givs we planned to use might not have been reduced.
4298 We have to be careful that we didn't initially think we could eliminate
4299 this biv because of a giv that we now think may be dead and shouldn't
4300 be used as a biv replacement.
4302 Also, there is the possibility that we may have a giv that looks
4303 like it can be used to eliminate a biv, but the resulting insn
4304 isn't valid. This can happen, for example, on the 88k, where a
4305 JUMP_INSN can compare a register only with zero. Attempts to
4306 replace it with a compare with a constant will fail.
4308 Note that in cases where this call fails, we may have replaced some
4309 of the occurrences of the biv with a giv, but no harm was done in
4310 doing so in the rare cases where it can occur. */
4312 if (all_reduced == 1 && bl->eliminable
4313 && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
4315 /* ?? If we created a new test to bypass the loop entirely,
4316 or otherwise drop straight in, based on this test, then
4317 we might want to rewrite it also. This way some later
4318 pass has more hope of removing the initialization of this
4321 /* If final_value != 0, then the biv may be used after loop end
4322 and we must emit an insn to set it just in case.
4324 Reversed bivs already have an insn after the loop setting their
4325 value, so we don't need another one. We can't calculate the
4326 proper final value for such a biv here anyways. */
4327 if (final_value != 0 && ! bl->reversed)
4331 /* If the loop has multiple exits, emit the insn before the
4332 loop to ensure that it will always be executed no matter
4333 how the loop exits. Otherwise, emit the insn after the
4334 loop, since this is slightly more efficient. */
4335 if (loop->exit_count)
4336 insert_before = loop_start;
4338 insert_before = end_insert_before;
4340 emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
4345 /* Delete all of the instructions inside the loop which set
4346 the biv, as they are all dead. If is safe to delete them,
4347 because an insn setting a biv will never be part of a libcall. */
4348 /* However, deleting them will invalidate the regno_last_uid info,
4349 so keeping them around is more convenient. Final_biv_value
4350 will only succeed when there are multiple exits if the biv
4351 is dead at each exit, hence it does not matter that the original
4352 insn remains, because it is dead anyways. */
4353 for (v = bl->biv; v; v = v->next_iv)
4354 delete_insn (v->insn);
4357 if (loop_dump_stream)
4358 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4363 /* Go through all the instructions in the loop, making all the
4364 register substitutions scheduled in REG_MAP. */
4366 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
4367 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4368 || GET_CODE (p) == CALL_INSN)
4370 replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
4371 replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
4375 if (loop_info->n_iterations > 0)
4377 /* When we completely unroll a loop we will likely not need the increment
4378 of the loop BIV and we will not need the conditional branch at the
4380 unrolled_insn_copies = insn_count - 2;
4383 /* When we completely unroll a loop on a HAVE_cc0 machine we will not
4384 need the comparison before the conditional branch at the end of the
4386 unrolled_insn_copies -= 1;
4389 /* We'll need one copy for each loop iteration. */
4390 unrolled_insn_copies *= loop_info->n_iterations;
4392 /* A little slop to account for the ability to remove initialization
4393 code, better CSE, and other secondary benefits of completely
4394 unrolling some loops. */
4395 unrolled_insn_copies -= 1;
4397 /* Clamp the value. */
4398 if (unrolled_insn_copies < 0)
4399 unrolled_insn_copies = 0;
4402 /* Unroll loops from within strength reduction so that we can use the
4403 induction variable information that strength_reduce has already
4404 collected. Always unroll loops that would be as small or smaller
4405 unrolled than when rolled. */
4406 if ((flags & LOOP_UNROLL)
4407 || (loop_info->n_iterations > 0
4408 && unrolled_insn_copies <= insn_count))
4409 unroll_loop (loop, insn_count, end_insert_before, 1);
4411 #ifdef HAVE_doloop_end
4412 if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
4413 doloop_optimize (loop);
4414 #endif /* HAVE_doloop_end */
4416 if (loop_dump_stream)
4417 fprintf (loop_dump_stream, "\n");
4420 VARRAY_FREE (ivs->reg_iv_type);
4421 VARRAY_FREE (ivs->reg_iv_info);
4422 free (ivs->reg_biv_class);
4427 /*Record all basic induction variables calculated in the insn. */
4429 check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
4432 int not_every_iteration;
4435 struct loop_ivs *ivs = LOOP_IVS (loop);
4442 if (GET_CODE (p) == INSN
4443 && (set = single_set (p))
4444 && GET_CODE (SET_DEST (set)) == REG)
4446 dest_reg = SET_DEST (set);
4447 if (REGNO (dest_reg) < max_reg_before_loop
4448 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
4449 && REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
4451 if (basic_induction_var (loop, SET_SRC (set),
4452 GET_MODE (SET_SRC (set)),
4453 dest_reg, p, &inc_val, &mult_val,
4456 /* It is a possible basic induction variable.
4457 Create and initialize an induction structure for it. */
4460 = (struct induction *) oballoc (sizeof (struct induction));
4462 record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
4463 not_every_iteration, maybe_multiple);
4464 REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
4466 else if (REGNO (dest_reg) < max_reg_before_loop)
4467 REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
4473 /* Record all givs calculated in the insn.
4474 A register is a giv if: it is only set once, it is a function of a
4475 biv and a constant (or invariant), and it is not a biv. */
4477 check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
4480 int not_every_iteration;
4483 struct loop_regs *regs = LOOP_REGS (loop);
4486 /* Look for a general induction variable in a register. */
4487 if (GET_CODE (p) == INSN
4488 && (set = single_set (p))
4489 && GET_CODE (SET_DEST (set)) == REG
4490 && ! VARRAY_CHAR (regs->may_not_optimize, REGNO (SET_DEST (set))))
4499 rtx last_consec_insn;
4501 dest_reg = SET_DEST (set);
4502 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
4505 if (/* SET_SRC is a giv. */
4506 (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
4507 &mult_val, &ext_val, 0, &benefit, VOIDmode)
4508 /* Equivalent expression is a giv. */
4509 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
4510 && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
4511 &add_val, &mult_val, &ext_val, 0,
4512 &benefit, VOIDmode)))
4513 /* Don't try to handle any regs made by loop optimization.
4514 We have nothing on them in regno_first_uid, etc. */
4515 && REGNO (dest_reg) < max_reg_before_loop
4516 /* Don't recognize a BASIC_INDUCT_VAR here. */
4517 && dest_reg != src_reg
4518 /* This must be the only place where the register is set. */
4519 && (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) == 1
4520 /* or all sets must be consecutive and make a giv. */
4521 || (benefit = consec_sets_giv (loop, benefit, p,
4523 &add_val, &mult_val, &ext_val,
4524 &last_consec_insn))))
4527 = (struct induction *) oballoc (sizeof (struct induction));
4529 /* If this is a library call, increase benefit. */
4530 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
4531 benefit += libcall_benefit (p);
4533 /* Skip the consecutive insns, if there are any. */
4534 if (VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) != 1)
4535 p = last_consec_insn;
4537 record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
4538 ext_val, benefit, DEST_REG, not_every_iteration,
4539 maybe_multiple, NULL_PTR);
4544 #ifndef DONT_REDUCE_ADDR
4545 /* Look for givs which are memory addresses. */
4546 /* This resulted in worse code on a VAX 8600. I wonder if it
4548 if (GET_CODE (p) == INSN)
4549 find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
4553 /* Update the status of whether giv can derive other givs. This can
4554 change when we pass a label or an insn that updates a biv. */
4555 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4556 || GET_CODE (p) == CODE_LABEL)
4557 update_giv_derive (loop, p);
4561 /* Return 1 if X is a valid source for an initial value (or as value being
4562 compared against in an initial test).
4564 X must be either a register or constant and must not be clobbered between
4565 the current insn and the start of the loop.
4567 INSN is the insn containing X. */
4570 valid_initial_value_p (x, insn, call_seen, loop_start)
4579 /* Only consider pseudos we know about initialized in insns whose luids
4581 if (GET_CODE (x) != REG
4582 || REGNO (x) >= max_reg_before_loop)
4585 /* Don't use call-clobbered registers across a call which clobbers it. On
4586 some machines, don't use any hard registers at all. */
4587 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4588 && (SMALL_REGISTER_CLASSES
4589 || (call_used_regs[REGNO (x)] && call_seen)))
4592 /* Don't use registers that have been clobbered before the start of the
4594 if (reg_set_between_p (x, insn, loop_start))
4600 /* Scan X for memory refs and check each memory address
4601 as a possible giv. INSN is the insn whose pattern X comes from.
4602 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4603 every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
4604 more thanonce in each loop iteration. */
4607 find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
4608 const struct loop *loop;
4611 int not_every_iteration, maybe_multiple;
4614 register enum rtx_code code;
4615 register const char *fmt;
4620 code = GET_CODE (x);
4645 /* This code used to disable creating GIVs with mult_val == 1 and
4646 add_val == 0. However, this leads to lost optimizations when
4647 it comes time to combine a set of related DEST_ADDR GIVs, since
4648 this one would not be seen. */
4650 if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
4651 &mult_val, &ext_val, 1, &benefit,
4654 /* Found one; record it. */
4656 = (struct induction *) oballoc (sizeof (struct induction));
4658 record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
4659 add_val, ext_val, benefit, DEST_ADDR,
4660 not_every_iteration, maybe_multiple, &XEXP (x, 0));
4662 v->mem_mode = GET_MODE (x);
4671 /* Recursively scan the subexpressions for other mem refs. */
4673 fmt = GET_RTX_FORMAT (code);
4674 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4676 find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
4678 else if (fmt[i] == 'E')
4679 for (j = 0; j < XVECLEN (x, i); j++)
4680 find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
4684 /* Fill in the data about one biv update.
4685 V is the `struct induction' in which we record the biv. (It is
4686 allocated by the caller, with alloca.)
4687 INSN is the insn that sets it.
4688 DEST_REG is the biv's reg.
4690 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4691 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4692 being set to INC_VAL.
4694 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4695 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4696 can be executed more than once per iteration. If MAYBE_MULTIPLE
4697 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4698 executed exactly once per iteration. */
4701 record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
4702 not_every_iteration, maybe_multiple)
4704 struct induction *v;
4710 int not_every_iteration;
4713 struct loop_ivs *ivs = LOOP_IVS (loop);
4714 struct iv_class *bl;
4717 v->src_reg = dest_reg;
4718 v->dest_reg = dest_reg;
4719 v->mult_val = mult_val;
4720 v->add_val = inc_val;
4721 v->ext_dependant = NULL_RTX;
4722 v->location = location;
4723 v->mode = GET_MODE (dest_reg);
4724 v->always_computable = ! not_every_iteration;
4725 v->always_executed = ! not_every_iteration;
4726 v->maybe_multiple = maybe_multiple;
4728 /* Add this to the reg's iv_class, creating a class
4729 if this is the first incrementation of the reg. */
4731 bl = ivs->reg_biv_class[REGNO (dest_reg)];
4734 /* Create and initialize new iv_class. */
4736 bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
4738 bl->regno = REGNO (dest_reg);
4744 /* Set initial value to the reg itself. */
4745 bl->initial_value = dest_reg;
4746 /* We haven't seen the initializing insn yet */
4749 bl->initial_test = 0;
4750 bl->incremented = 0;
4754 bl->total_benefit = 0;
4756 /* Add this class to ivs->loop_iv_list. */
4757 bl->next = ivs->loop_iv_list;
4758 ivs->loop_iv_list = bl;
4760 /* Put it in the array of biv register classes. */
4761 ivs->reg_biv_class[REGNO (dest_reg)] = bl;
4764 /* Update IV_CLASS entry for this biv. */
4765 v->next_iv = bl->biv;
4768 if (mult_val == const1_rtx)
4769 bl->incremented = 1;
4771 if (loop_dump_stream)
4773 fprintf (loop_dump_stream,
4774 "Insn %d: possible biv, reg %d,",
4775 INSN_UID (insn), REGNO (dest_reg));
4776 if (GET_CODE (inc_val) == CONST_INT)
4778 fprintf (loop_dump_stream, " const =");
4779 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4780 fputc ('\n', loop_dump_stream);
4784 fprintf (loop_dump_stream, " const = ");
4785 print_rtl (loop_dump_stream, inc_val);
4786 fprintf (loop_dump_stream, "\n");
4791 /* Fill in the data about one giv.
4792 V is the `struct induction' in which we record the giv. (It is
4793 allocated by the caller, with alloca.)
4794 INSN is the insn that sets it.
4795 BENEFIT estimates the savings from deleting this insn.
4796 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4797 into a register or is used as a memory address.
4799 SRC_REG is the biv reg which the giv is computed from.
4800 DEST_REG is the giv's reg (if the giv is stored in a reg).
4801 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4802 LOCATION points to the place where this giv's value appears in INSN. */
4805 record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
4806 benefit, type, not_every_iteration, maybe_multiple, location)
4807 const struct loop *loop;
4808 struct induction *v;
4812 rtx mult_val, add_val, ext_val;
4815 int not_every_iteration, maybe_multiple;
4818 struct loop_ivs *ivs = LOOP_IVS (loop);
4819 struct induction *b;
4820 struct iv_class *bl;
4821 rtx set = single_set (insn);
4824 /* Attempt to prove constantness of the values. */
4825 temp = simplify_rtx (add_val);
4830 v->src_reg = src_reg;
4832 v->dest_reg = dest_reg;
4833 v->mult_val = mult_val;
4834 v->add_val = add_val;
4835 v->ext_dependant = ext_val;
4836 v->benefit = benefit;
4837 v->location = location;
4839 v->combined_with = 0;
4840 v->maybe_multiple = maybe_multiple;
4842 v->derive_adjustment = 0;
4848 v->auto_inc_opt = 0;
4852 /* The v->always_computable field is used in update_giv_derive, to
4853 determine whether a giv can be used to derive another giv. For a
4854 DEST_REG giv, INSN computes a new value for the giv, so its value
4855 isn't computable if INSN insn't executed every iteration.
4856 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4857 it does not compute a new value. Hence the value is always computable
4858 regardless of whether INSN is executed each iteration. */
4860 if (type == DEST_ADDR)
4861 v->always_computable = 1;
4863 v->always_computable = ! not_every_iteration;
4865 v->always_executed = ! not_every_iteration;
4867 if (type == DEST_ADDR)
4869 v->mode = GET_MODE (*location);
4872 else /* type == DEST_REG */
4874 v->mode = GET_MODE (SET_DEST (set));
4876 v->lifetime = (uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
4877 - uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))]);
4879 /* If the lifetime is zero, it means that this register is
4880 really a dead store. So mark this as a giv that can be
4881 ignored. This will not prevent the biv from being eliminated. */
4882 if (v->lifetime == 0)
4885 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
4886 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
4889 /* Add the giv to the class of givs computed from one biv. */
4891 bl = ivs->reg_biv_class[REGNO (src_reg)];
4894 v->next_iv = bl->giv;
4896 /* Don't count DEST_ADDR. This is supposed to count the number of
4897 insns that calculate givs. */
4898 if (type == DEST_REG)
4900 bl->total_benefit += benefit;
4903 /* Fatal error, biv missing for this giv? */
4906 if (type == DEST_ADDR)
4910 /* The giv can be replaced outright by the reduced register only if all
4911 of the following conditions are true:
4912 - the insn that sets the giv is always executed on any iteration
4913 on which the giv is used at all
4914 (there are two ways to deduce this:
4915 either the insn is executed on every iteration,
4916 or all uses follow that insn in the same basic block),
4917 - the giv is not used outside the loop
4918 - no assignments to the biv occur during the giv's lifetime. */
4920 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
4921 /* Previous line always fails if INSN was moved by loop opt. */
4922 && uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
4923 < INSN_LUID (loop->end)
4924 && (! not_every_iteration
4925 || last_use_this_basic_block (dest_reg, insn)))
4927 /* Now check that there are no assignments to the biv within the
4928 giv's lifetime. This requires two separate checks. */
4930 /* Check each biv update, and fail if any are between the first
4931 and last use of the giv.
4933 If this loop contains an inner loop that was unrolled, then
4934 the insn modifying the biv may have been emitted by the loop
4935 unrolling code, and hence does not have a valid luid. Just
4936 mark the biv as not replaceable in this case. It is not very
4937 useful as a biv, because it is used in two different loops.
4938 It is very unlikely that we would be able to optimize the giv
4939 using this biv anyways. */
4942 for (b = bl->biv; b; b = b->next_iv)
4944 if (INSN_UID (b->insn) >= max_uid_for_loop
4945 || ((uid_luid[INSN_UID (b->insn)]
4946 >= uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))])
4947 && (uid_luid[INSN_UID (b->insn)]
4948 <= uid_luid[REGNO_LAST_UID (REGNO (dest_reg))])))
4951 v->not_replaceable = 1;
4956 /* If there are any backwards branches that go from after the
4957 biv update to before it, then this giv is not replaceable. */
4959 for (b = bl->biv; b; b = b->next_iv)
4960 if (back_branch_in_range_p (loop, b->insn))
4963 v->not_replaceable = 1;
4969 /* May still be replaceable, we don't have enough info here to
4972 v->not_replaceable = 0;
4976 /* Record whether the add_val contains a const_int, for later use by
4981 v->no_const_addval = 1;
4982 if (tem == const0_rtx)
4984 else if (CONSTANT_P (add_val))
4985 v->no_const_addval = 0;
4986 if (GET_CODE (tem) == PLUS)
4990 if (GET_CODE (XEXP (tem, 0)) == PLUS)
4991 tem = XEXP (tem, 0);
4992 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
4993 tem = XEXP (tem, 1);
4997 if (CONSTANT_P (XEXP (tem, 1)))
4998 v->no_const_addval = 0;
5002 if (loop_dump_stream)
5004 if (type == DEST_REG)
5005 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5006 INSN_UID (insn), REGNO (dest_reg));
5008 fprintf (loop_dump_stream, "Insn %d: dest address",
5011 fprintf (loop_dump_stream, " src reg %d benefit %d",
5012 REGNO (src_reg), v->benefit);
5013 fprintf (loop_dump_stream, " lifetime %d",
5017 fprintf (loop_dump_stream, " replaceable");
5019 if (v->no_const_addval)
5020 fprintf (loop_dump_stream, " ncav");
5022 if (v->ext_dependant)
5024 switch (GET_CODE (v->ext_dependant))
5027 fprintf (loop_dump_stream, " ext se");
5030 fprintf (loop_dump_stream, " ext ze");
5033 fprintf (loop_dump_stream, " ext tr");
5040 if (GET_CODE (mult_val) == CONST_INT)
5042 fprintf (loop_dump_stream, " mult ");
5043 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5047 fprintf (loop_dump_stream, " mult ");
5048 print_rtl (loop_dump_stream, mult_val);
5051 if (GET_CODE (add_val) == CONST_INT)
5053 fprintf (loop_dump_stream, " add ");
5054 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5058 fprintf (loop_dump_stream, " add ");
5059 print_rtl (loop_dump_stream, add_val);
5063 if (loop_dump_stream)
5064 fprintf (loop_dump_stream, "\n");
5068 /* All this does is determine whether a giv can be made replaceable because
5069 its final value can be calculated. This code can not be part of record_giv
5070 above, because final_giv_value requires that the number of loop iterations
5071 be known, and that can not be accurately calculated until after all givs
5072 have been identified. */
5075 check_final_value (loop, v)
5076 const struct loop *loop;
5077 struct induction *v;
5079 struct loop_ivs *ivs = LOOP_IVS (loop);
5080 struct iv_class *bl;
5081 rtx final_value = 0;
5083 bl = ivs->reg_biv_class[REGNO (v->src_reg)];
5085 /* DEST_ADDR givs will never reach here, because they are always marked
5086 replaceable above in record_giv. */
5088 /* The giv can be replaced outright by the reduced register only if all
5089 of the following conditions are true:
5090 - the insn that sets the giv is always executed on any iteration
5091 on which the giv is used at all
5092 (there are two ways to deduce this:
5093 either the insn is executed on every iteration,
5094 or all uses follow that insn in the same basic block),
5095 - its final value can be calculated (this condition is different
5096 than the one above in record_giv)
5097 - no assignments to the biv occur during the giv's lifetime. */
5100 /* This is only called now when replaceable is known to be false. */
5101 /* Clear replaceable, so that it won't confuse final_giv_value. */
5105 if ((final_value = final_giv_value (loop, v))
5106 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5108 int biv_increment_seen = 0;
5114 /* When trying to determine whether or not a biv increment occurs
5115 during the lifetime of the giv, we can ignore uses of the variable
5116 outside the loop because final_value is true. Hence we can not
5117 use regno_last_uid and regno_first_uid as above in record_giv. */
5119 /* Search the loop to determine whether any assignments to the
5120 biv occur during the giv's lifetime. Start with the insn
5121 that sets the giv, and search around the loop until we come
5122 back to that insn again.
5124 Also fail if there is a jump within the giv's lifetime that jumps
5125 to somewhere outside the lifetime but still within the loop. This
5126 catches spaghetti code where the execution order is not linear, and
5127 hence the above test fails. Here we assume that the giv lifetime
5128 does not extend from one iteration of the loop to the next, so as
5129 to make the test easier. Since the lifetime isn't known yet,
5130 this requires two loops. See also record_giv above. */
5132 last_giv_use = v->insn;
5138 p = NEXT_INSN (loop->start);
5142 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5143 || GET_CODE (p) == CALL_INSN)
5145 /* It is possible for the BIV increment to use the GIV if we
5146 have a cycle. Thus we must be sure to check each insn for
5147 both BIV and GIV uses, and we must check for BIV uses
5150 if (! biv_increment_seen
5151 && reg_set_p (v->src_reg, PATTERN (p)))
5152 biv_increment_seen = 1;
5154 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5156 if (biv_increment_seen)
5159 v->not_replaceable = 1;
5167 /* Now that the lifetime of the giv is known, check for branches
5168 from within the lifetime to outside the lifetime if it is still
5178 p = NEXT_INSN (loop->start);
5179 if (p == last_giv_use)
5182 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5183 && LABEL_NAME (JUMP_LABEL (p))
5184 && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
5185 && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
5186 || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
5187 && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
5190 v->not_replaceable = 1;
5192 if (loop_dump_stream)
5193 fprintf (loop_dump_stream,
5194 "Found branch outside giv lifetime.\n");
5201 /* If it is replaceable, then save the final value. */
5203 v->final_value = final_value;
5206 if (loop_dump_stream && v->replaceable)
5207 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5208 INSN_UID (v->insn), REGNO (v->dest_reg));
5211 /* Update the status of whether a giv can derive other givs.
5213 We need to do something special if there is or may be an update to the biv
5214 between the time the giv is defined and the time it is used to derive
5217 In addition, a giv that is only conditionally set is not allowed to
5218 derive another giv once a label has been passed.
5220 The cases we look at are when a label or an update to a biv is passed. */
5223 update_giv_derive (loop, p)
5224 const struct loop *loop;
5227 struct loop_ivs *ivs = LOOP_IVS (loop);
5228 struct iv_class *bl;
5229 struct induction *biv, *giv;
5233 /* Search all IV classes, then all bivs, and finally all givs.
5235 There are three cases we are concerned with. First we have the situation
5236 of a giv that is only updated conditionally. In that case, it may not
5237 derive any givs after a label is passed.
5239 The second case is when a biv update occurs, or may occur, after the
5240 definition of a giv. For certain biv updates (see below) that are
5241 known to occur between the giv definition and use, we can adjust the
5242 giv definition. For others, or when the biv update is conditional,
5243 we must prevent the giv from deriving any other givs. There are two
5244 sub-cases within this case.
5246 If this is a label, we are concerned with any biv update that is done
5247 conditionally, since it may be done after the giv is defined followed by
5248 a branch here (actually, we need to pass both a jump and a label, but
5249 this extra tracking doesn't seem worth it).
5251 If this is a jump, we are concerned about any biv update that may be
5252 executed multiple times. We are actually only concerned about
5253 backward jumps, but it is probably not worth performing the test
5254 on the jump again here.
5256 If this is a biv update, we must adjust the giv status to show that a
5257 subsequent biv update was performed. If this adjustment cannot be done,
5258 the giv cannot derive further givs. */
5260 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
5261 for (biv = bl->biv; biv; biv = biv->next_iv)
5262 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5265 for (giv = bl->giv; giv; giv = giv->next_iv)
5267 /* If cant_derive is already true, there is no point in
5268 checking all of these conditions again. */
5269 if (giv->cant_derive)
5272 /* If this giv is conditionally set and we have passed a label,
5273 it cannot derive anything. */
5274 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5275 giv->cant_derive = 1;
5277 /* Skip givs that have mult_val == 0, since
5278 they are really invariants. Also skip those that are
5279 replaceable, since we know their lifetime doesn't contain
5281 else if (giv->mult_val == const0_rtx || giv->replaceable)
5284 /* The only way we can allow this giv to derive another
5285 is if this is a biv increment and we can form the product
5286 of biv->add_val and giv->mult_val. In this case, we will
5287 be able to compute a compensation. */
5288 else if (biv->insn == p)
5293 if (biv->mult_val == const1_rtx)
5294 tem = simplify_giv_expr (loop,
5295 gen_rtx_MULT (giv->mode,
5298 &ext_val_dummy, &dummy);
5300 if (tem && giv->derive_adjustment)
5301 tem = simplify_giv_expr
5303 gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
5304 &ext_val_dummy, &dummy);
5307 giv->derive_adjustment = tem;
5309 giv->cant_derive = 1;
5311 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5312 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5313 giv->cant_derive = 1;
5318 /* Check whether an insn is an increment legitimate for a basic induction var.
5319 X is the source of insn P, or a part of it.
5320 MODE is the mode in which X should be interpreted.
5322 DEST_REG is the putative biv, also the destination of the insn.
5323 We accept patterns of these forms:
5324 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5325 REG = INVARIANT + REG
5327 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5328 store the additive term into *INC_VAL, and store the place where
5329 we found the additive term into *LOCATION.
5331 If X is an assignment of an invariant into DEST_REG, we set
5332 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5334 We also want to detect a BIV when it corresponds to a variable
5335 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5336 of the variable may be a PLUS that adds a SUBREG of that variable to
5337 an invariant and then sign- or zero-extends the result of the PLUS
5340 Most GIVs in such cases will be in the promoted mode, since that is the
5341 probably the natural computation mode (and almost certainly the mode
5342 used for addresses) on the machine. So we view the pseudo-reg containing
5343 the variable as the BIV, as if it were simply incremented.
5345 Note that treating the entire pseudo as a BIV will result in making
5346 simple increments to any GIVs based on it. However, if the variable
5347 overflows in its declared mode but not its promoted mode, the result will
5348 be incorrect. This is acceptable if the variable is signed, since
5349 overflows in such cases are undefined, but not if it is unsigned, since
5350 those overflows are defined. So we only check for SIGN_EXTEND and
5353 If we cannot find a biv, we return 0. */
5356 basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
5357 const struct loop *loop;
5359 enum machine_mode mode;
5366 register enum rtx_code code;
5370 code = GET_CODE (x);
5375 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5376 || (GET_CODE (XEXP (x, 0)) == SUBREG
5377 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5378 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5380 argp = &XEXP (x, 1);
5382 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5383 || (GET_CODE (XEXP (x, 1)) == SUBREG
5384 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5385 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5387 argp = &XEXP (x, 0);
5393 if (loop_invariant_p (loop, arg) != 1)
5396 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5397 *mult_val = const1_rtx;
5402 /* If this is a SUBREG for a promoted variable, check the inner
5404 if (SUBREG_PROMOTED_VAR_P (x))
5405 return basic_induction_var (loop, SUBREG_REG (x),
5406 GET_MODE (SUBREG_REG (x)),
5407 dest_reg, p, inc_val, mult_val, location);
5411 /* If this register is assigned in a previous insn, look at its
5412 source, but don't go outside the loop or past a label. */
5414 /* If this sets a register to itself, we would repeat any previous
5415 biv increment if we applied this strategy blindly. */
5416 if (rtx_equal_p (dest_reg, x))
5424 insn = PREV_INSN (insn);
5426 while (insn && GET_CODE (insn) == NOTE
5427 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5431 set = single_set (insn);
5435 if ((SET_DEST (set) == x
5436 || (GET_CODE (SET_DEST (set)) == SUBREG
5437 && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
5439 && (GET_MODE_CLASS (GET_MODE (SET_DEST (set)))
5441 && SUBREG_REG (SET_DEST (set)) == x))
5442 && basic_induction_var (loop, SET_SRC (set),
5443 (GET_MODE (SET_SRC (set)) == VOIDmode
5445 : GET_MODE (SET_SRC (set))),
5447 inc_val, mult_val, location))
5452 /* Can accept constant setting of biv only when inside inner most loop.
5453 Otherwise, a biv of an inner loop may be incorrectly recognized
5454 as a biv of the outer loop,
5455 causing code to be moved INTO the inner loop. */
5457 if (loop_invariant_p (loop, x) != 1)
5462 /* convert_modes aborts if we try to convert to or from CCmode, so just
5463 exclude that case. It is very unlikely that a condition code value
5464 would be a useful iterator anyways. */
5465 if (loop->level == 1
5466 && GET_MODE_CLASS (mode) != MODE_CC
5467 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5469 /* Possible bug here? Perhaps we don't know the mode of X. */
5470 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5471 *mult_val = const0_rtx;
5478 return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5479 dest_reg, p, inc_val, mult_val, location);
5482 /* Similar, since this can be a sign extension. */
5483 for (insn = PREV_INSN (p);
5484 (insn && GET_CODE (insn) == NOTE
5485 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5486 insn = PREV_INSN (insn))
5490 set = single_set (insn);
5492 if (! rtx_equal_p (dest_reg, XEXP (x, 0))
5493 && set && SET_DEST (set) == XEXP (x, 0)
5494 && GET_CODE (XEXP (x, 1)) == CONST_INT
5495 && INTVAL (XEXP (x, 1)) >= 0
5496 && GET_CODE (SET_SRC (set)) == ASHIFT
5497 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5498 return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
5499 GET_MODE (XEXP (x, 0)),
5500 dest_reg, insn, inc_val, mult_val,
5509 /* A general induction variable (giv) is any quantity that is a linear
5510 function of a basic induction variable,
5511 i.e. giv = biv * mult_val + add_val.
5512 The coefficients can be any loop invariant quantity.
5513 A giv need not be computed directly from the biv;
5514 it can be computed by way of other givs. */
5516 /* Determine whether X computes a giv.
5517 If it does, return a nonzero value
5518 which is the benefit from eliminating the computation of X;
5519 set *SRC_REG to the register of the biv that it is computed from;
5520 set *ADD_VAL and *MULT_VAL to the coefficients,
5521 such that the value of X is biv * mult + add; */
5524 general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
5525 is_addr, pbenefit, addr_mode)
5526 const struct loop *loop;
5534 enum machine_mode addr_mode;
5536 struct loop_ivs *ivs = LOOP_IVS (loop);
5540 /* If this is an invariant, forget it, it isn't a giv. */
5541 if (loop_invariant_p (loop, x) == 1)
5544 /* See if the expression could be a giv and get its form.
5545 Mark our place on the obstack in case we don't find a giv. */
5546 storage = (char *) oballoc (0);
5548 *ext_val = NULL_RTX;
5549 x = simplify_giv_expr (loop, x, ext_val, pbenefit);
5556 switch (GET_CODE (x))
5560 /* Since this is now an invariant and wasn't before, it must be a giv
5561 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5563 *src_reg = ivs->loop_iv_list->biv->dest_reg;
5564 *mult_val = const0_rtx;
5569 /* This is equivalent to a BIV. */
5571 *mult_val = const1_rtx;
5572 *add_val = const0_rtx;
5576 /* Either (plus (biv) (invar)) or
5577 (plus (mult (biv) (invar_1)) (invar_2)). */
5578 if (GET_CODE (XEXP (x, 0)) == MULT)
5580 *src_reg = XEXP (XEXP (x, 0), 0);
5581 *mult_val = XEXP (XEXP (x, 0), 1);
5585 *src_reg = XEXP (x, 0);
5586 *mult_val = const1_rtx;
5588 *add_val = XEXP (x, 1);
5592 /* ADD_VAL is zero. */
5593 *src_reg = XEXP (x, 0);
5594 *mult_val = XEXP (x, 1);
5595 *add_val = const0_rtx;
5602 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5603 unless they are CONST_INT). */
5604 if (GET_CODE (*add_val) == USE)
5605 *add_val = XEXP (*add_val, 0);
5606 if (GET_CODE (*mult_val) == USE)
5607 *mult_val = XEXP (*mult_val, 0);
5610 *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
5612 *pbenefit += rtx_cost (orig_x, SET);
5614 /* Always return true if this is a giv so it will be detected as such,
5615 even if the benefit is zero or negative. This allows elimination
5616 of bivs that might otherwise not be eliminated. */
5620 /* Given an expression, X, try to form it as a linear function of a biv.
5621 We will canonicalize it to be of the form
5622 (plus (mult (BIV) (invar_1))
5624 with possible degeneracies.
5626 The invariant expressions must each be of a form that can be used as a
5627 machine operand. We surround then with a USE rtx (a hack, but localized
5628 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5629 routine; it is the caller's responsibility to strip them.
5631 If no such canonicalization is possible (i.e., two biv's are used or an
5632 expression that is neither invariant nor a biv or giv), this routine
5635 For a non-zero return, the result will have a code of CONST_INT, USE,
5636 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5638 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5640 static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
5641 static rtx sge_plus_constant PARAMS ((rtx, rtx));
5644 simplify_giv_expr (loop, x, ext_val, benefit)
5645 const struct loop *loop;
5650 struct loop_ivs *ivs = LOOP_IVS (loop);
5651 struct loop_regs *regs = LOOP_REGS (loop);
5652 enum machine_mode mode = GET_MODE (x);
5656 /* If this is not an integer mode, or if we cannot do arithmetic in this
5657 mode, this can't be a giv. */
5658 if (mode != VOIDmode
5659 && (GET_MODE_CLASS (mode) != MODE_INT
5660 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5663 switch (GET_CODE (x))
5666 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5667 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5668 if (arg0 == 0 || arg1 == 0)
5671 /* Put constant last, CONST_INT last if both constant. */
5672 if ((GET_CODE (arg0) == USE
5673 || GET_CODE (arg0) == CONST_INT)
5674 && ! ((GET_CODE (arg0) == USE
5675 && GET_CODE (arg1) == USE)
5676 || GET_CODE (arg1) == CONST_INT))
5677 tem = arg0, arg0 = arg1, arg1 = tem;
5679 /* Handle addition of zero, then addition of an invariant. */
5680 if (arg1 == const0_rtx)
5682 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5683 switch (GET_CODE (arg0))
5687 /* Adding two invariants must result in an invariant, so enclose
5688 addition operation inside a USE and return it. */
5689 if (GET_CODE (arg0) == USE)
5690 arg0 = XEXP (arg0, 0);
5691 if (GET_CODE (arg1) == USE)
5692 arg1 = XEXP (arg1, 0);
5694 if (GET_CODE (arg0) == CONST_INT)
5695 tem = arg0, arg0 = arg1, arg1 = tem;
5696 if (GET_CODE (arg1) == CONST_INT)
5697 tem = sge_plus_constant (arg0, arg1);
5699 tem = sge_plus (mode, arg0, arg1);
5701 if (GET_CODE (tem) != CONST_INT)
5702 tem = gen_rtx_USE (mode, tem);
5707 /* biv + invar or mult + invar. Return sum. */
5708 return gen_rtx_PLUS (mode, arg0, arg1);
5711 /* (a + invar_1) + invar_2. Associate. */
5713 simplify_giv_expr (loop,
5725 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5726 MULT to reduce cases. */
5727 if (GET_CODE (arg0) == REG)
5728 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5729 if (GET_CODE (arg1) == REG)
5730 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5732 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5733 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5734 Recurse to associate the second PLUS. */
5735 if (GET_CODE (arg1) == MULT)
5736 tem = arg0, arg0 = arg1, arg1 = tem;
5738 if (GET_CODE (arg1) == PLUS)
5740 simplify_giv_expr (loop,
5742 gen_rtx_PLUS (mode, arg0,
5747 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5748 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5751 if (!rtx_equal_p (arg0, arg1))
5754 return simplify_giv_expr (loop,
5763 /* Handle "a - b" as "a + b * (-1)". */
5764 return simplify_giv_expr (loop,
5773 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5774 arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
5775 if (arg0 == 0 || arg1 == 0)
5778 /* Put constant last, CONST_INT last if both constant. */
5779 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5780 && GET_CODE (arg1) != CONST_INT)
5781 tem = arg0, arg0 = arg1, arg1 = tem;
5783 /* If second argument is not now constant, not giv. */
5784 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5787 /* Handle multiply by 0 or 1. */
5788 if (arg1 == const0_rtx)
5791 else if (arg1 == const1_rtx)
5794 switch (GET_CODE (arg0))
5797 /* biv * invar. Done. */
5798 return gen_rtx_MULT (mode, arg0, arg1);
5801 /* Product of two constants. */
5802 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5805 /* invar * invar is a giv, but attempt to simplify it somehow. */
5806 if (GET_CODE (arg1) != CONST_INT)
5809 arg0 = XEXP (arg0, 0);
5810 if (GET_CODE (arg0) == MULT)
5812 /* (invar_0 * invar_1) * invar_2. Associate. */
5813 return simplify_giv_expr (loop,
5822 /* Porpagate the MULT expressions to the intermost nodes. */
5823 else if (GET_CODE (arg0) == PLUS)
5825 /* (invar_0 + invar_1) * invar_2. Distribute. */
5826 return simplify_giv_expr (loop,
5838 return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
5841 /* (a * invar_1) * invar_2. Associate. */
5842 return simplify_giv_expr (loop,
5851 /* (a + invar_1) * invar_2. Distribute. */
5852 return simplify_giv_expr (loop,
5867 /* Shift by constant is multiply by power of two. */
5868 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5872 simplify_giv_expr (loop,
5875 GEN_INT ((HOST_WIDE_INT) 1
5876 << INTVAL (XEXP (x, 1)))),
5880 /* "-a" is "a * (-1)" */
5881 return simplify_giv_expr (loop,
5882 gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
5886 /* "~a" is "-a - 1". Silly, but easy. */
5887 return simplify_giv_expr (loop,
5888 gen_rtx_MINUS (mode,
5889 gen_rtx_NEG (mode, XEXP (x, 0)),
5894 /* Already in proper form for invariant. */
5900 /* Conditionally recognize extensions of simple IVs. After we've
5901 computed loop traversal counts and verified the range of the
5902 source IV, we'll reevaluate this as a GIV. */
5903 if (*ext_val == NULL_RTX)
5905 arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
5906 if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
5908 *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
5915 /* If this is a new register, we can't deal with it. */
5916 if (REGNO (x) >= max_reg_before_loop)
5919 /* Check for biv or giv. */
5920 switch (REG_IV_TYPE (ivs, REGNO (x)))
5924 case GENERAL_INDUCT:
5926 struct induction *v = REG_IV_INFO (ivs, REGNO (x));
5928 /* Form expression from giv and add benefit. Ensure this giv
5929 can derive another and subtract any needed adjustment if so. */
5931 /* Increasing the benefit here is risky. The only case in which it
5932 is arguably correct is if this is the only use of V. In other
5933 cases, this will artificially inflate the benefit of the current
5934 giv, and lead to suboptimal code. Thus, it is disabled, since
5935 potentially not reducing an only marginally beneficial giv is
5936 less harmful than reducing many givs that are not really
5939 rtx single_use = VARRAY_RTX (regs->single_usage, REGNO (x));
5940 if (single_use && single_use != const0_rtx)
5941 *benefit += v->benefit;
5947 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
5948 v->src_reg, v->mult_val),
5951 if (v->derive_adjustment)
5952 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
5953 arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
5956 if (!v->ext_dependant)
5961 *ext_val = v->ext_dependant;
5969 /* If it isn't an induction variable, and it is invariant, we
5970 may be able to simplify things further by looking through
5971 the bits we just moved outside the loop. */
5972 if (loop_invariant_p (loop, x) == 1)
5976 for (m = the_movables.head; m; m = m->next)
5977 if (rtx_equal_p (x, m->set_dest))
5979 /* Ok, we found a match. Substitute and simplify. */
5981 /* If we match another movable, we must use that, as
5982 this one is going away. */
5984 return simplify_giv_expr (loop, m->match->set_dest,
5987 /* If consec is non-zero, this is a member of a group of
5988 instructions that were moved together. We handle this
5989 case only to the point of seeking to the last insn and
5990 looking for a REG_EQUAL. Fail if we don't find one. */
5997 tem = NEXT_INSN (tem);
6001 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
6003 tem = XEXP (tem, 0);
6007 tem = single_set (m->insn);
6009 tem = SET_SRC (tem);
6014 /* What we are most interested in is pointer
6015 arithmetic on invariants -- only take
6016 patterns we may be able to do something with. */
6017 if (GET_CODE (tem) == PLUS
6018 || GET_CODE (tem) == MULT
6019 || GET_CODE (tem) == ASHIFT
6020 || GET_CODE (tem) == CONST_INT
6021 || GET_CODE (tem) == SYMBOL_REF)
6023 tem = simplify_giv_expr (loop, tem, ext_val,
6028 else if (GET_CODE (tem) == CONST
6029 && GET_CODE (XEXP (tem, 0)) == PLUS
6030 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
6031 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
6033 tem = simplify_giv_expr (loop, XEXP (tem, 0),
6045 /* Fall through to general case. */
6047 /* If invariant, return as USE (unless CONST_INT).
6048 Otherwise, not giv. */
6049 if (GET_CODE (x) == USE)
6052 if (loop_invariant_p (loop, x) == 1)
6054 if (GET_CODE (x) == CONST_INT)
6056 if (GET_CODE (x) == CONST
6057 && GET_CODE (XEXP (x, 0)) == PLUS
6058 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
6059 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
6061 return gen_rtx_USE (mode, x);
6068 /* This routine folds invariants such that there is only ever one
6069 CONST_INT in the summation. It is only used by simplify_giv_expr. */
6072 sge_plus_constant (x, c)
6075 if (GET_CODE (x) == CONST_INT)
6076 return GEN_INT (INTVAL (x) + INTVAL (c));
6077 else if (GET_CODE (x) != PLUS)
6078 return gen_rtx_PLUS (GET_MODE (x), x, c);
6079 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6081 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6082 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6084 else if (GET_CODE (XEXP (x, 0)) == PLUS
6085 || GET_CODE (XEXP (x, 1)) != PLUS)
6087 return gen_rtx_PLUS (GET_MODE (x),
6088 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6092 return gen_rtx_PLUS (GET_MODE (x),
6093 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6098 sge_plus (mode, x, y)
6099 enum machine_mode mode;
6102 while (GET_CODE (y) == PLUS)
6104 rtx a = XEXP (y, 0);
6105 if (GET_CODE (a) == CONST_INT)
6106 x = sge_plus_constant (x, a);
6108 x = gen_rtx_PLUS (mode, x, a);
6111 if (GET_CODE (y) == CONST_INT)
6112 x = sge_plus_constant (x, y);
6114 x = gen_rtx_PLUS (mode, x, y);
6118 /* Help detect a giv that is calculated by several consecutive insns;
6122 The caller has already identified the first insn P as having a giv as dest;
6123 we check that all other insns that set the same register follow
6124 immediately after P, that they alter nothing else,
6125 and that the result of the last is still a giv.
6127 The value is 0 if the reg set in P is not really a giv.
6128 Otherwise, the value is the amount gained by eliminating
6129 all the consecutive insns that compute the value.
6131 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6132 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6134 The coefficients of the ultimate giv value are stored in
6135 *MULT_VAL and *ADD_VAL. */
6138 consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
6139 add_val, mult_val, ext_val, last_consec_insn)
6140 const struct loop *loop;
6148 rtx *last_consec_insn;
6150 struct loop_ivs *ivs = LOOP_IVS (loop);
6151 struct loop_regs *regs = LOOP_REGS (loop);
6158 /* Indicate that this is a giv so that we can update the value produced in
6159 each insn of the multi-insn sequence.
6161 This induction structure will be used only by the call to
6162 general_induction_var below, so we can allocate it on our stack.
6163 If this is a giv, our caller will replace the induct var entry with
6164 a new induction structure. */
6166 = (struct induction *) alloca (sizeof (struct induction));
6167 v->src_reg = src_reg;
6168 v->mult_val = *mult_val;
6169 v->add_val = *add_val;
6170 v->benefit = first_benefit;
6172 v->derive_adjustment = 0;
6173 v->ext_dependant = NULL_RTX;
6175 REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
6176 REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
6178 count = VARRAY_INT (regs->n_times_set, REGNO (dest_reg)) - 1;
6183 code = GET_CODE (p);
6185 /* If libcall, skip to end of call sequence. */
6186 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6190 && (set = single_set (p))
6191 && GET_CODE (SET_DEST (set)) == REG
6192 && SET_DEST (set) == dest_reg
6193 && (general_induction_var (loop, SET_SRC (set), &src_reg,
6194 add_val, mult_val, ext_val, 0,
6196 /* Giv created by equivalent expression. */
6197 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6198 && general_induction_var (loop, XEXP (temp, 0), &src_reg,
6199 add_val, mult_val, ext_val, 0,
6200 &benefit, VOIDmode)))
6201 && src_reg == v->src_reg)
6203 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6204 benefit += libcall_benefit (p);
6207 v->mult_val = *mult_val;
6208 v->add_val = *add_val;
6209 v->benefit += benefit;
6211 else if (code != NOTE)
6213 /* Allow insns that set something other than this giv to a
6214 constant. Such insns are needed on machines which cannot
6215 include long constants and should not disqualify a giv. */
6217 && (set = single_set (p))
6218 && SET_DEST (set) != dest_reg
6219 && CONSTANT_P (SET_SRC (set)))
6222 REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
6227 *last_consec_insn = p;
6231 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6232 represented by G1. If no such expression can be found, or it is clear that
6233 it cannot possibly be a valid address, 0 is returned.
6235 To perform the computation, we note that
6238 where `v' is the biv.
6240 So G2 = (y/b) * G1 + (b - a*y/x).
6242 Note that MULT = y/x.
6244 Update: A and B are now allowed to be additive expressions such that
6245 B contains all variables in A. That is, computing B-A will not require
6246 subtracting variables. */
6249 express_from_1 (a, b, mult)
6252 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6254 if (mult == const0_rtx)
6257 /* If MULT is not 1, we cannot handle A with non-constants, since we
6258 would then be required to subtract multiples of the registers in A.
6259 This is theoretically possible, and may even apply to some Fortran
6260 constructs, but it is a lot of work and we do not attempt it here. */
6262 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6265 /* In general these structures are sorted top to bottom (down the PLUS
6266 chain), but not left to right across the PLUS. If B is a higher
6267 order giv than A, we can strip one level and recurse. If A is higher
6268 order, we'll eventually bail out, but won't know that until the end.
6269 If they are the same, we'll strip one level around this loop. */
6271 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6273 rtx ra, rb, oa, ob, tmp;
6275 ra = XEXP (a, 0), oa = XEXP (a, 1);
6276 if (GET_CODE (ra) == PLUS)
6277 tmp = ra, ra = oa, oa = tmp;
6279 rb = XEXP (b, 0), ob = XEXP (b, 1);
6280 if (GET_CODE (rb) == PLUS)
6281 tmp = rb, rb = ob, ob = tmp;
6283 if (rtx_equal_p (ra, rb))
6284 /* We matched: remove one reg completely. */
6286 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6287 /* An alternate match. */
6289 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6290 /* An alternate match. */
6294 /* Indicates an extra register in B. Strip one level from B and
6295 recurse, hoping B was the higher order expression. */
6296 ob = express_from_1 (a, ob, mult);
6299 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6303 /* Here we are at the last level of A, go through the cases hoping to
6304 get rid of everything but a constant. */
6306 if (GET_CODE (a) == PLUS)
6310 ra = XEXP (a, 0), oa = XEXP (a, 1);
6311 if (rtx_equal_p (oa, b))
6313 else if (!rtx_equal_p (ra, b))
6316 if (GET_CODE (oa) != CONST_INT)
6319 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6321 else if (GET_CODE (a) == CONST_INT)
6323 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6325 else if (CONSTANT_P (a))
6327 return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
6329 else if (GET_CODE (b) == PLUS)
6331 if (rtx_equal_p (a, XEXP (b, 0)))
6333 else if (rtx_equal_p (a, XEXP (b, 1)))
6338 else if (rtx_equal_p (a, b))
6345 express_from (g1, g2)
6346 struct induction *g1, *g2;
6350 /* The value that G1 will be multiplied by must be a constant integer. Also,
6351 the only chance we have of getting a valid address is if b*c/a (see above
6352 for notation) is also an integer. */
6353 if (GET_CODE (g1->mult_val) == CONST_INT
6354 && GET_CODE (g2->mult_val) == CONST_INT)
6356 if (g1->mult_val == const0_rtx
6357 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6359 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6361 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6365 /* ??? Find out if the one is a multiple of the other? */
6369 add = express_from_1 (g1->add_val, g2->add_val, mult);
6370 if (add == NULL_RTX)
6372 /* Failed. If we've got a multiplication factor between G1 and G2,
6373 scale G1's addend and try again. */
6374 if (INTVAL (mult) > 1)
6376 rtx g1_add_val = g1->add_val;
6377 if (GET_CODE (g1_add_val) == MULT
6378 && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
6381 m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
6382 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
6383 XEXP (g1_add_val, 0), GEN_INT (m));
6387 g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
6391 add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
6394 if (add == NULL_RTX)
6397 /* Form simplified final result. */
6398 if (mult == const0_rtx)
6400 else if (mult == const1_rtx)
6401 mult = g1->dest_reg;
6403 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6405 if (add == const0_rtx)
6409 if (GET_CODE (add) == PLUS
6410 && CONSTANT_P (XEXP (add, 1)))
6412 rtx tem = XEXP (add, 1);
6413 mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
6417 return gen_rtx_PLUS (g2->mode, mult, add);
6421 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6422 represented by G1. This indicates that G2 should be combined with G1 and
6423 that G2 can use (either directly or via an address expression) a register
6424 used to represent G1. */
6427 combine_givs_p (g1, g2)
6428 struct induction *g1, *g2;
6432 /* With the introduction of ext dependant givs, we must care for modes.
6433 G2 must not use a wider mode than G1. */
6434 if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
6437 ret = comb = express_from (g1, g2);
6438 if (comb == NULL_RTX)
6440 if (g1->mode != g2->mode)
6441 ret = gen_lowpart (g2->mode, comb);
6443 /* If these givs are identical, they can be combined. We use the results
6444 of express_from because the addends are not in a canonical form, so
6445 rtx_equal_p is a weaker test. */
6446 /* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
6447 combination to be the other way round. */
6448 if (comb == g1->dest_reg
6449 && (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
6454 /* If G2 can be expressed as a function of G1 and that function is valid
6455 as an address and no more expensive than using a register for G2,
6456 the expression of G2 in terms of G1 can be used. */
6458 && g2->giv_type == DEST_ADDR
6459 && memory_address_p (g2->mem_mode, ret)
6460 /* ??? Looses, especially with -fforce-addr, where *g2->location
6461 will always be a register, and so anything more complicated
6465 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6467 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6478 /* Check each extension dependant giv in this class to see if its
6479 root biv is safe from wrapping in the interior mode, which would
6480 make the giv illegal. */
6483 check_ext_dependant_givs (bl, loop_info)
6484 struct iv_class *bl;
6485 struct loop_info *loop_info;
6487 int ze_ok = 0, se_ok = 0, info_ok = 0;
6488 enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
6489 HOST_WIDE_INT start_val;
6490 unsigned HOST_WIDE_INT u_end_val, u_start_val;
6492 struct induction *v;
6494 /* Make sure the iteration data is available. We must have
6495 constants in order to be certain of no overflow. */
6496 /* ??? An unknown iteration count with an increment of +-1
6497 combined with friendly exit tests of against an invariant
6498 value is also ameanable to optimization. Not implemented. */
6499 if (loop_info->n_iterations > 0
6500 && bl->initial_value
6501 && GET_CODE (bl->initial_value) == CONST_INT
6502 && (incr = biv_total_increment (bl))
6503 && GET_CODE (incr) == CONST_INT
6504 /* Make sure the host can represent the arithmetic. */
6505 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
6507 unsigned HOST_WIDE_INT abs_incr, total_incr;
6508 HOST_WIDE_INT s_end_val;
6512 start_val = INTVAL (bl->initial_value);
6513 u_start_val = start_val;
6515 neg_incr = 0, abs_incr = INTVAL (incr);
6516 if (INTVAL (incr) < 0)
6517 neg_incr = 1, abs_incr = -abs_incr;
6518 total_incr = abs_incr * loop_info->n_iterations;
6520 /* Check for host arithmatic overflow. */
6521 if (total_incr / loop_info->n_iterations == abs_incr)
6523 unsigned HOST_WIDE_INT u_max;
6524 HOST_WIDE_INT s_max;
6526 u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
6527 s_end_val = u_end_val;
6528 u_max = GET_MODE_MASK (biv_mode);
6531 /* Check zero extension of biv ok. */
6533 /* Check for host arithmatic overflow. */
6535 ? u_end_val < u_start_val
6536 : u_end_val > u_start_val)
6537 /* Check for target arithmetic overflow. */
6539 ? 1 /* taken care of with host overflow */
6540 : u_end_val <= u_max))
6545 /* Check sign extension of biv ok. */
6546 /* ??? While it is true that overflow with signed and pointer
6547 arithmetic is undefined, I fear too many programmers don't
6548 keep this fact in mind -- myself included on occasion.
6549 So leave alone with the signed overflow optimizations. */
6550 if (start_val >= -s_max - 1
6551 /* Check for host arithmatic overflow. */
6553 ? s_end_val < start_val
6554 : s_end_val > start_val)
6555 /* Check for target arithmetic overflow. */
6557 ? s_end_val >= -s_max - 1
6558 : s_end_val <= s_max))
6565 /* Invalidate givs that fail the tests. */
6566 for (v = bl->giv; v; v = v->next_iv)
6567 if (v->ext_dependant)
6569 enum rtx_code code = GET_CODE (v->ext_dependant);
6582 /* We don't know whether this value is being used as either
6583 signed or unsigned, so to safely truncate we must satisfy
6584 both. The initial check here verifies the BIV itself;
6585 once that is successful we may check its range wrt the
6589 enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
6590 unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
6592 /* We know from the above that both endpoints are nonnegative,
6593 and that there is no wrapping. Verify that both endpoints
6594 are within the (signed) range of the outer mode. */
6595 if (u_start_val <= max && u_end_val <= max)
6606 if (loop_dump_stream)
6608 fprintf (loop_dump_stream,
6609 "Verified ext dependant giv at %d of reg %d\n",
6610 INSN_UID (v->insn), bl->regno);
6615 if (loop_dump_stream)
6620 why = "biv iteration values overflowed";
6624 incr = biv_total_increment (bl);
6625 if (incr == const1_rtx)
6626 why = "biv iteration info incomplete; incr by 1";
6628 why = "biv iteration info incomplete";
6631 fprintf (loop_dump_stream,
6632 "Failed ext dependant giv at %d, %s\n",
6633 INSN_UID (v->insn), why);
6640 /* Generate a version of VALUE in a mode appropriate for initializing V. */
6643 extend_value_for_giv (v, value)
6644 struct induction *v;
6647 rtx ext_dep = v->ext_dependant;
6652 /* Recall that check_ext_dependant_givs verified that the known bounds
6653 of a biv did not overflow or wrap with respect to the extension for
6654 the giv. Therefore, constants need no additional adjustment. */
6655 if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
6658 /* Otherwise, we must adjust the value to compensate for the
6659 differing modes of the biv and the giv. */
6660 return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
6663 struct combine_givs_stats
6670 cmp_combine_givs_stats (xp, yp)
6674 const struct combine_givs_stats * const x =
6675 (const struct combine_givs_stats *) xp;
6676 const struct combine_givs_stats * const y =
6677 (const struct combine_givs_stats *) yp;
6679 d = y->total_benefit - x->total_benefit;
6680 /* Stabilize the sort. */
6682 d = x->giv_number - y->giv_number;
6686 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6687 any other. If so, point SAME to the giv combined with and set NEW_REG to
6688 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6689 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6692 combine_givs (regs, bl)
6693 struct loop_regs *regs;
6694 struct iv_class *bl;
6696 /* Additional benefit to add for being combined multiple times. */
6697 const int extra_benefit = 3;
6699 struct induction *g1, *g2, **giv_array;
6700 int i, j, k, giv_count;
6701 struct combine_givs_stats *stats;
6704 /* Count givs, because bl->giv_count is incorrect here. */
6706 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6711 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6713 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6715 giv_array[i++] = g1;
6717 stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
6718 can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
6720 for (i = 0; i < giv_count; i++)
6726 stats[i].giv_number = i;
6728 /* If a DEST_REG GIV is used only once, do not allow it to combine
6729 with anything, for in doing so we will gain nothing that cannot
6730 be had by simply letting the GIV with which we would have combined
6731 to be reduced on its own. The losage shows up in particular with
6732 DEST_ADDR targets on hosts with reg+reg addressing, though it can
6733 be seen elsewhere as well. */
6734 if (g1->giv_type == DEST_REG
6735 && (single_use = VARRAY_RTX (regs->single_usage,
6736 REGNO (g1->dest_reg)))
6737 && single_use != const0_rtx)
6740 this_benefit = g1->benefit;
6741 /* Add an additional weight for zero addends. */
6742 if (g1->no_const_addval)
6745 for (j = 0; j < giv_count; j++)
6751 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6753 can_combine[i * giv_count + j] = this_combine;
6754 this_benefit += g2->benefit + extra_benefit;
6757 stats[i].total_benefit = this_benefit;
6760 /* Iterate, combining until we can't. */
6762 qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
6764 if (loop_dump_stream)
6766 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6767 for (k = 0; k < giv_count; k++)
6769 g1 = giv_array[stats[k].giv_number];
6770 if (!g1->combined_with && !g1->same)
6771 fprintf (loop_dump_stream, " {%d, %d}",
6772 INSN_UID (giv_array[stats[k].giv_number]->insn),
6773 stats[k].total_benefit);
6775 putc ('\n', loop_dump_stream);
6778 for (k = 0; k < giv_count; k++)
6780 int g1_add_benefit = 0;
6782 i = stats[k].giv_number;
6785 /* If it has already been combined, skip. */
6786 if (g1->combined_with || g1->same)
6789 for (j = 0; j < giv_count; j++)
6792 if (g1 != g2 && can_combine[i * giv_count + j]
6793 /* If it has already been combined, skip. */
6794 && ! g2->same && ! g2->combined_with)
6798 g2->new_reg = can_combine[i * giv_count + j];
6800 g1->combined_with++;
6801 g1->lifetime += g2->lifetime;
6803 g1_add_benefit += g2->benefit;
6805 /* ??? The new final_[bg]iv_value code does a much better job
6806 of finding replaceable giv's, and hence this code may no
6807 longer be necessary. */
6808 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6809 g1_add_benefit -= copy_cost;
6811 /* To help optimize the next set of combinations, remove
6812 this giv from the benefits of other potential mates. */
6813 for (l = 0; l < giv_count; ++l)
6815 int m = stats[l].giv_number;
6816 if (can_combine[m * giv_count + j])
6817 stats[l].total_benefit -= g2->benefit + extra_benefit;
6820 if (loop_dump_stream)
6821 fprintf (loop_dump_stream,
6822 "giv at %d combined with giv at %d; new benefit %d + %d, lifetime %d\n",
6823 INSN_UID (g2->insn), INSN_UID (g1->insn),
6824 g1->benefit, g1_add_benefit, g1->lifetime);
6828 /* To help optimize the next set of combinations, remove
6829 this giv from the benefits of other potential mates. */
6830 if (g1->combined_with)
6832 for (j = 0; j < giv_count; ++j)
6834 int m = stats[j].giv_number;
6835 if (can_combine[m * giv_count + i])
6836 stats[j].total_benefit -= g1->benefit + extra_benefit;
6839 g1->benefit += g1_add_benefit;
6841 /* We've finished with this giv, and everything it touched.
6842 Restart the combination so that proper weights for the
6843 rest of the givs are properly taken into account. */
6844 /* ??? Ideally we would compact the arrays at this point, so
6845 as to not cover old ground. But sanely compacting
6846 can_combine is tricky. */
6856 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
6859 emit_iv_add_mult (b, m, a, reg, insert_before)
6860 rtx b; /* initial value of basic induction variable */
6861 rtx m; /* multiplicative constant */
6862 rtx a; /* additive constant */
6863 rtx reg; /* destination register */
6869 /* Prevent unexpected sharing of these rtx. */
6873 /* Increase the lifetime of any invariants moved further in code. */
6874 update_reg_last_use (a, insert_before);
6875 update_reg_last_use (b, insert_before);
6876 update_reg_last_use (m, insert_before);
6879 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
6881 emit_move_insn (reg, result);
6882 seq = gen_sequence ();
6885 emit_insn_before (seq, insert_before);
6887 /* It is entirely possible that the expansion created lots of new
6888 registers. Iterate over the sequence we just created and
6891 if (GET_CODE (seq) == SEQUENCE)
6894 for (i = 0; i < XVECLEN (seq, 0); ++i)
6896 rtx set = single_set (XVECEXP (seq, 0, i));
6897 if (set && GET_CODE (SET_DEST (set)) == REG)
6898 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6901 else if (GET_CODE (seq) == SET
6902 && GET_CODE (SET_DEST (seq)) == REG)
6903 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
6906 /* Similar to emit_iv_add_mult, but compute cost rather than emitting
6909 iv_add_mult_cost (b, m, a, reg)
6910 rtx b; /* initial value of basic induction variable */
6911 rtx m; /* multiplicative constant */
6912 rtx a; /* additive constant */
6913 rtx reg; /* destination register */
6919 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
6921 emit_move_insn (reg, result);
6922 last = get_last_insn ();
6925 rtx t = single_set (last);
6927 cost += rtx_cost (SET_SRC (t), SET);
6928 last = PREV_INSN (last);
6934 /* Test whether A * B can be computed without
6935 an actual multiply insn. Value is 1 if so. */
6938 product_cheap_p (a, b)
6944 struct obstack *old_rtl_obstack = rtl_obstack;
6945 char *storage = (char *) obstack_alloc (&temp_obstack, 0);
6948 /* If only one is constant, make it B. */
6949 if (GET_CODE (a) == CONST_INT)
6950 tmp = a, a = b, b = tmp;
6952 /* If first constant, both constant, so don't need multiply. */
6953 if (GET_CODE (a) == CONST_INT)
6956 /* If second not constant, neither is constant, so would need multiply. */
6957 if (GET_CODE (b) != CONST_INT)
6960 /* One operand is constant, so might not need multiply insn. Generate the
6961 code for the multiply and see if a call or multiply, or long sequence
6962 of insns is generated. */
6964 rtl_obstack = &temp_obstack;
6966 expand_mult (GET_MODE (a), a, b, NULL_RTX, 0);
6967 tmp = gen_sequence ();
6970 if (GET_CODE (tmp) == SEQUENCE)
6972 if (XVEC (tmp, 0) == 0)
6974 else if (XVECLEN (tmp, 0) > 3)
6977 for (i = 0; i < XVECLEN (tmp, 0); i++)
6979 rtx insn = XVECEXP (tmp, 0, i);
6981 if (GET_CODE (insn) != INSN
6982 || (GET_CODE (PATTERN (insn)) == SET
6983 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
6984 || (GET_CODE (PATTERN (insn)) == PARALLEL
6985 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
6986 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
6993 else if (GET_CODE (tmp) == SET
6994 && GET_CODE (SET_SRC (tmp)) == MULT)
6996 else if (GET_CODE (tmp) == PARALLEL
6997 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
6998 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
7001 /* Free any storage we obtained in generating this multiply and restore rtl
7002 allocation to its normal obstack. */
7003 obstack_free (&temp_obstack, storage);
7004 rtl_obstack = old_rtl_obstack;
7009 /* Check to see if loop can be terminated by a "decrement and branch until
7010 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
7011 Also try reversing an increment loop to a decrement loop
7012 to see if the optimization can be performed.
7013 Value is nonzero if optimization was performed. */
7015 /* This is useful even if the architecture doesn't have such an insn,
7016 because it might change a loops which increments from 0 to n to a loop
7017 which decrements from n to 0. A loop that decrements to zero is usually
7018 faster than one that increments from zero. */
7020 /* ??? This could be rewritten to use some of the loop unrolling procedures,
7021 such as approx_final_value, biv_total_increment, loop_iterations, and
7022 final_[bg]iv_value. */
7025 check_dbra_loop (loop, insn_count)
7029 struct loop_info *loop_info = LOOP_INFO (loop);
7030 struct loop_regs *regs = LOOP_REGS (loop);
7031 struct loop_ivs *ivs = LOOP_IVS (loop);
7032 struct iv_class *bl;
7039 rtx before_comparison;
7043 int compare_and_branch;
7044 rtx loop_start = loop->start;
7045 rtx loop_end = loop->end;
7047 /* If last insn is a conditional branch, and the insn before tests a
7048 register value, try to optimize it. Otherwise, we can't do anything. */
7050 jump = PREV_INSN (loop_end);
7051 comparison = get_condition_for_loop (loop, jump);
7052 if (comparison == 0)
7054 if (!onlyjump_p (jump))
7057 /* Try to compute whether the compare/branch at the loop end is one or
7058 two instructions. */
7059 get_condition (jump, &first_compare);
7060 if (first_compare == jump)
7061 compare_and_branch = 1;
7062 else if (first_compare == prev_nonnote_insn (jump))
7063 compare_and_branch = 2;
7068 /* If more than one condition is present to control the loop, then
7069 do not proceed, as this function does not know how to rewrite
7070 loop tests with more than one condition.
7072 Look backwards from the first insn in the last comparison
7073 sequence and see if we've got another comparison sequence. */
7076 if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
7077 if (GET_CODE (jump1) == JUMP_INSN)
7081 /* Check all of the bivs to see if the compare uses one of them.
7082 Skip biv's set more than once because we can't guarantee that
7083 it will be zero on the last iteration. Also skip if the biv is
7084 used between its update and the test insn. */
7086 for (bl = ivs->loop_iv_list; bl; bl = bl->next)
7088 if (bl->biv_count == 1
7089 && ! bl->biv->maybe_multiple
7090 && bl->biv->dest_reg == XEXP (comparison, 0)
7091 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
7099 /* Look for the case where the basic induction variable is always
7100 nonnegative, and equals zero on the last iteration.
7101 In this case, add a reg_note REG_NONNEG, which allows the
7102 m68k DBRA instruction to be used. */
7104 if (((GET_CODE (comparison) == GT
7105 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
7106 && INTVAL (XEXP (comparison, 1)) == -1)
7107 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
7108 && GET_CODE (bl->biv->add_val) == CONST_INT
7109 && INTVAL (bl->biv->add_val) < 0)
7111 /* Initial value must be greater than 0,
7112 init_val % -dec_value == 0 to ensure that it equals zero on
7113 the last iteration */
7115 if (GET_CODE (bl->initial_value) == CONST_INT
7116 && INTVAL (bl->initial_value) > 0
7117 && (INTVAL (bl->initial_value)
7118 % (-INTVAL (bl->biv->add_val))) == 0)
7120 /* register always nonnegative, add REG_NOTE to branch */
7121 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7123 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7130 /* If the decrement is 1 and the value was tested as >= 0 before
7131 the loop, then we can safely optimize. */
7132 for (p = loop_start; p; p = PREV_INSN (p))
7134 if (GET_CODE (p) == CODE_LABEL)
7136 if (GET_CODE (p) != JUMP_INSN)
7139 before_comparison = get_condition_for_loop (loop, p);
7140 if (before_comparison
7141 && XEXP (before_comparison, 0) == bl->biv->dest_reg
7142 && GET_CODE (before_comparison) == LT
7143 && XEXP (before_comparison, 1) == const0_rtx
7144 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
7145 && INTVAL (bl->biv->add_val) == -1)
7147 if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
7149 = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
7157 else if (GET_CODE (bl->biv->add_val) == CONST_INT
7158 && INTVAL (bl->biv->add_val) > 0)
7160 /* Try to change inc to dec, so can apply above optimization. */
7162 all registers modified are induction variables or invariant,
7163 all memory references have non-overlapping addresses
7164 (obviously true if only one write)
7165 allow 2 insns for the compare/jump at the end of the loop. */
7166 /* Also, we must avoid any instructions which use both the reversed
7167 biv and another biv. Such instructions will fail if the loop is
7168 reversed. We meet this condition by requiring that either
7169 no_use_except_counting is true, or else that there is only
7171 int num_nonfixed_reads = 0;
7172 /* 1 if the iteration var is used only to count iterations. */
7173 int no_use_except_counting = 0;
7174 /* 1 if the loop has no memory store, or it has a single memory store
7175 which is reversible. */
7176 int reversible_mem_store = 1;
7178 if (bl->giv_count == 0 && ! loop->exit_count)
7180 rtx bivreg = regno_reg_rtx[bl->regno];
7182 /* If there are no givs for this biv, and the only exit is the
7183 fall through at the end of the loop, then
7184 see if perhaps there are no uses except to count. */
7185 no_use_except_counting = 1;
7186 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7189 rtx set = single_set (p);
7191 if (set && GET_CODE (SET_DEST (set)) == REG
7192 && REGNO (SET_DEST (set)) == bl->regno)
7193 /* An insn that sets the biv is okay. */
7195 else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
7196 || p == prev_nonnote_insn (loop_end))
7197 && reg_mentioned_p (bivreg, PATTERN (p)))
7199 /* If either of these insns uses the biv and sets a pseudo
7200 that has more than one usage, then the biv has uses
7201 other than counting since it's used to derive a value
7202 that is used more than one time. */
7203 note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
7205 if (regs->multiple_uses)
7207 no_use_except_counting = 0;
7211 else if (reg_mentioned_p (bivreg, PATTERN (p)))
7213 no_use_except_counting = 0;
7219 if (no_use_except_counting)
7220 /* No need to worry about MEMs. */
7222 else if (loop_info->num_mem_sets <= 1)
7224 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7226 num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
7228 /* If the loop has a single store, and the destination address is
7229 invariant, then we can't reverse the loop, because this address
7230 might then have the wrong value at loop exit.
7231 This would work if the source was invariant also, however, in that
7232 case, the insn should have been moved out of the loop. */
7234 if (loop_info->num_mem_sets == 1)
7236 struct induction *v;
7238 reversible_mem_store
7239 = (! loop_info->unknown_address_altered
7240 && ! loop_info->unknown_constant_address_altered
7241 && ! loop_invariant_p (loop,
7242 XEXP (XEXP (loop_info->store_mems, 0),
7245 /* If the store depends on a register that is set after the
7246 store, it depends on the initial value, and is thus not
7248 for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
7250 if (v->giv_type == DEST_REG
7251 && reg_mentioned_p (v->dest_reg,
7252 PATTERN (loop_info->first_loop_store_insn))
7253 && loop_insn_first_p (loop_info->first_loop_store_insn,
7255 reversible_mem_store = 0;
7262 /* This code only acts for innermost loops. Also it simplifies
7263 the memory address check by only reversing loops with
7264 zero or one memory access.
7265 Two memory accesses could involve parts of the same array,
7266 and that can't be reversed.
7267 If the biv is used only for counting, than we don't need to worry
7268 about all these things. */
7270 if ((num_nonfixed_reads <= 1
7271 && ! loop_info->has_call
7272 && ! loop_info->has_volatile
7273 && reversible_mem_store
7274 && (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
7275 + the_movables.num + compare_and_branch == insn_count)
7276 && (bl == ivs->loop_iv_list && bl->next == 0))
7277 || no_use_except_counting)
7281 /* Loop can be reversed. */
7282 if (loop_dump_stream)
7283 fprintf (loop_dump_stream, "Can reverse loop\n");
7285 /* Now check other conditions:
7287 The increment must be a constant, as must the initial value,
7288 and the comparison code must be LT.
7290 This test can probably be improved since +/- 1 in the constant
7291 can be obtained by changing LT to LE and vice versa; this is
7295 /* for constants, LE gets turned into LT */
7296 && (GET_CODE (comparison) == LT
7297 || (GET_CODE (comparison) == LE
7298 && no_use_except_counting)))
7300 HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
7301 rtx initial_value, comparison_value;
7303 enum rtx_code cmp_code;
7304 int comparison_const_width;
7305 unsigned HOST_WIDE_INT comparison_sign_mask;
7307 add_val = INTVAL (bl->biv->add_val);
7308 comparison_value = XEXP (comparison, 1);
7309 if (GET_MODE (comparison_value) == VOIDmode)
7310 comparison_const_width
7311 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
7313 comparison_const_width
7314 = GET_MODE_BITSIZE (GET_MODE (comparison_value));
7315 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
7316 comparison_const_width = HOST_BITS_PER_WIDE_INT;
7317 comparison_sign_mask
7318 = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
7320 /* If the comparison value is not a loop invariant, then we
7321 can not reverse this loop.
7323 ??? If the insns which initialize the comparison value as
7324 a whole compute an invariant result, then we could move
7325 them out of the loop and proceed with loop reversal. */
7326 if (! loop_invariant_p (loop, comparison_value))
7329 if (GET_CODE (comparison_value) == CONST_INT)
7330 comparison_val = INTVAL (comparison_value);
7331 initial_value = bl->initial_value;
7333 /* Normalize the initial value if it is an integer and
7334 has no other use except as a counter. This will allow
7335 a few more loops to be reversed. */
7336 if (no_use_except_counting
7337 && GET_CODE (comparison_value) == CONST_INT
7338 && GET_CODE (initial_value) == CONST_INT)
7340 comparison_val = comparison_val - INTVAL (bl->initial_value);
7341 /* The code below requires comparison_val to be a multiple
7342 of add_val in order to do the loop reversal, so
7343 round up comparison_val to a multiple of add_val.
7344 Since comparison_value is constant, we know that the
7345 current comparison code is LT. */
7346 comparison_val = comparison_val + add_val - 1;
7348 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
7349 /* We postpone overflow checks for COMPARISON_VAL here;
7350 even if there is an overflow, we might still be able to
7351 reverse the loop, if converting the loop exit test to
7353 initial_value = const0_rtx;
7356 /* First check if we can do a vanilla loop reversal. */
7357 if (initial_value == const0_rtx
7358 /* If we have a decrement_and_branch_on_count,
7359 prefer the NE test, since this will allow that
7360 instruction to be generated. Note that we must
7361 use a vanilla loop reversal if the biv is used to
7362 calculate a giv or has a non-counting use. */
7363 #if ! defined (HAVE_decrement_and_branch_until_zero) \
7364 && defined (HAVE_decrement_and_branch_on_count)
7365 && (! (add_val == 1 && loop->vtop
7366 && (bl->biv_count == 0
7367 || no_use_except_counting)))
7369 && GET_CODE (comparison_value) == CONST_INT
7370 /* Now do postponed overflow checks on COMPARISON_VAL. */
7371 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7372 & comparison_sign_mask))
7374 /* Register will always be nonnegative, with value
7375 0 on last iteration */
7376 add_adjust = add_val;
7380 else if (add_val == 1 && loop->vtop
7381 && (bl->biv_count == 0
7382 || no_use_except_counting))
7390 if (GET_CODE (comparison) == LE)
7391 add_adjust -= add_val;
7393 /* If the initial value is not zero, or if the comparison
7394 value is not an exact multiple of the increment, then we
7395 can not reverse this loop. */
7396 if (initial_value == const0_rtx
7397 && GET_CODE (comparison_value) == CONST_INT)
7399 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7404 if (! no_use_except_counting || add_val != 1)
7408 final_value = comparison_value;
7410 /* Reset these in case we normalized the initial value
7411 and comparison value above. */
7412 if (GET_CODE (comparison_value) == CONST_INT
7413 && GET_CODE (initial_value) == CONST_INT)
7415 comparison_value = GEN_INT (comparison_val);
7417 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7419 bl->initial_value = initial_value;
7421 /* Save some info needed to produce the new insns. */
7422 reg = bl->biv->dest_reg;
7423 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7424 if (jump_label == pc_rtx)
7425 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7426 new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
7428 /* Set start_value; if this is not a CONST_INT, we need
7430 Initialize biv to start_value before loop start.
7431 The old initializing insn will be deleted as a
7432 dead store by flow.c. */
7433 if (initial_value == const0_rtx
7434 && GET_CODE (comparison_value) == CONST_INT)
7436 start_value = GEN_INT (comparison_val - add_adjust);
7437 emit_insn_before (gen_move_insn (reg, start_value),
7440 else if (GET_CODE (initial_value) == CONST_INT)
7442 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7443 enum machine_mode mode = GET_MODE (reg);
7444 enum insn_code icode
7445 = add_optab->handlers[(int) mode].insn_code;
7447 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7448 || ! ((*insn_data[icode].operand[1].predicate)
7449 (comparison_value, mode))
7450 || ! ((*insn_data[icode].operand[2].predicate)
7454 = gen_rtx_PLUS (mode, comparison_value, offset);
7455 emit_insn_before ((GEN_FCN (icode)
7456 (reg, comparison_value, offset)),
7458 if (GET_CODE (comparison) == LE)
7459 final_value = gen_rtx_PLUS (mode, comparison_value,
7462 else if (! add_adjust)
7464 enum machine_mode mode = GET_MODE (reg);
7465 enum insn_code icode
7466 = sub_optab->handlers[(int) mode].insn_code;
7467 if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
7468 || ! ((*insn_data[icode].operand[1].predicate)
7469 (comparison_value, mode))
7470 || ! ((*insn_data[icode].operand[2].predicate)
7471 (initial_value, mode)))
7474 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7475 emit_insn_before ((GEN_FCN (icode)
7476 (reg, comparison_value, initial_value)),
7480 /* We could handle the other cases too, but it'll be
7481 better to have a testcase first. */
7484 /* We may not have a single insn which can increment a reg, so
7485 create a sequence to hold all the insns from expand_inc. */
7487 expand_inc (reg, new_add_val);
7488 tem = gen_sequence ();
7491 p = emit_insn_before (tem, bl->biv->insn);
7492 delete_insn (bl->biv->insn);
7494 /* Update biv info to reflect its new status. */
7496 bl->initial_value = start_value;
7497 bl->biv->add_val = new_add_val;
7499 /* Update loop info. */
7500 loop_info->initial_value = reg;
7501 loop_info->initial_equiv_value = reg;
7502 loop_info->final_value = const0_rtx;
7503 loop_info->final_equiv_value = const0_rtx;
7504 loop_info->comparison_value = const0_rtx;
7505 loop_info->comparison_code = cmp_code;
7506 loop_info->increment = new_add_val;
7508 /* Inc LABEL_NUSES so that delete_insn will
7509 not delete the label. */
7510 LABEL_NUSES (XEXP (jump_label, 0))++;
7512 /* Emit an insn after the end of the loop to set the biv's
7513 proper exit value if it is used anywhere outside the loop. */
7514 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7516 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7517 emit_insn_after (gen_move_insn (reg, final_value),
7520 /* Delete compare/branch at end of loop. */
7521 delete_insn (PREV_INSN (loop_end));
7522 if (compare_and_branch == 2)
7523 delete_insn (first_compare);
7525 /* Add new compare/branch insn at end of loop. */
7527 emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
7528 GET_MODE (reg), 0, 0,
7529 XEXP (jump_label, 0));
7530 tem = gen_sequence ();
7532 emit_jump_insn_before (tem, loop_end);
7534 for (tem = PREV_INSN (loop_end);
7535 tem && GET_CODE (tem) != JUMP_INSN;
7536 tem = PREV_INSN (tem))
7540 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7546 /* Increment of LABEL_NUSES done above. */
7547 /* Register is now always nonnegative,
7548 so add REG_NONNEG note to the branch. */
7549 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
7555 /* No insn may reference both the reversed and another biv or it
7556 will fail (see comment near the top of the loop reversal
7558 Earlier on, we have verified that the biv has no use except
7559 counting, or it is the only biv in this function.
7560 However, the code that computes no_use_except_counting does
7561 not verify reg notes. It's possible to have an insn that
7562 references another biv, and has a REG_EQUAL note with an
7563 expression based on the reversed biv. To avoid this case,
7564 remove all REG_EQUAL notes based on the reversed biv
7566 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7570 rtx set = single_set (p);
7571 /* If this is a set of a GIV based on the reversed biv, any
7572 REG_EQUAL notes should still be correct. */
7574 || GET_CODE (SET_DEST (set)) != REG
7575 || (size_t) REGNO (SET_DEST (set)) >= ivs->reg_iv_type->num_elements
7576 || REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
7577 || REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
7578 for (pnote = ®_NOTES (p); *pnote;)
7580 if (REG_NOTE_KIND (*pnote) == REG_EQUAL
7581 && reg_mentioned_p (regno_reg_rtx[bl->regno],
7583 *pnote = XEXP (*pnote, 1);
7585 pnote = &XEXP (*pnote, 1);
7589 /* Mark that this biv has been reversed. Each giv which depends
7590 on this biv, and which is also live past the end of the loop
7591 will have to be fixed up. */
7595 if (loop_dump_stream)
7597 fprintf (loop_dump_stream, "Reversed loop");
7599 fprintf (loop_dump_stream, " and added reg_nonneg\n");
7601 fprintf (loop_dump_stream, "\n");
7612 /* Verify whether the biv BL appears to be eliminable,
7613 based on the insns in the loop that refer to it.
7615 If ELIMINATE_P is non-zero, actually do the elimination.
7617 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7618 determine whether invariant insns should be placed inside or at the
7619 start of the loop. */
7622 maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
7623 const struct loop *loop;
7624 struct iv_class *bl;
7626 int threshold, insn_count;
7628 struct loop_ivs *ivs = LOOP_IVS (loop);
7629 rtx reg = bl->biv->dest_reg;
7630 rtx loop_start = loop->start;
7631 rtx loop_end = loop->end;
7634 /* Scan all insns in the loop, stopping if we find one that uses the
7635 biv in a way that we cannot eliminate. */
7637 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
7639 enum rtx_code code = GET_CODE (p);
7640 rtx where = threshold >= insn_count ? loop_start : p;
7642 /* If this is a libcall that sets a giv, skip ahead to its end. */
7643 if (GET_RTX_CLASS (code) == 'i')
7645 rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
7649 rtx last = XEXP (note, 0);
7650 rtx set = single_set (last);
7652 if (set && GET_CODE (SET_DEST (set)) == REG)
7654 unsigned int regno = REGNO (SET_DEST (set));
7656 if (regno < max_reg_before_loop
7657 && REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
7658 && REG_IV_INFO (ivs, regno)->src_reg == bl->biv->src_reg)
7663 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7664 && reg_mentioned_p (reg, PATTERN (p))
7665 && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
7666 eliminate_p, where))
7668 if (loop_dump_stream)
7669 fprintf (loop_dump_stream,
7670 "Cannot eliminate biv %d: biv used in insn %d.\n",
7671 bl->regno, INSN_UID (p));
7678 if (loop_dump_stream)
7679 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7680 bl->regno, eliminate_p ? "was" : "can be");
7687 /* INSN and REFERENCE are instructions in the same insn chain.
7688 Return non-zero if INSN is first. */
7691 loop_insn_first_p (insn, reference)
7692 rtx insn, reference;
7696 for (p = insn, q = reference;;)
7698 /* Start with test for not first so that INSN == REFERENCE yields not
7700 if (q == insn || ! p)
7702 if (p == reference || ! q)
7705 /* Either of P or Q might be a NOTE. Notes have the same LUID as the
7706 previous insn, hence the <= comparison below does not work if
7708 if (INSN_UID (p) < max_uid_for_loop
7709 && INSN_UID (q) < max_uid_for_loop
7710 && GET_CODE (p) != NOTE)
7711 return INSN_LUID (p) <= INSN_LUID (q);
7713 if (INSN_UID (p) >= max_uid_for_loop
7714 || GET_CODE (p) == NOTE)
7716 if (INSN_UID (q) >= max_uid_for_loop)
7721 /* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
7722 the offset that we have to take into account due to auto-increment /
7723 div derivation is zero. */
7725 biv_elimination_giv_has_0_offset (biv, giv, insn)
7726 struct induction *biv, *giv;
7729 /* If the giv V had the auto-inc address optimization applied
7730 to it, and INSN occurs between the giv insn and the biv
7731 insn, then we'd have to adjust the value used here.
7732 This is rare, so we don't bother to make this possible. */
7733 if (giv->auto_inc_opt
7734 && ((loop_insn_first_p (giv->insn, insn)
7735 && loop_insn_first_p (insn, biv->insn))
7736 || (loop_insn_first_p (biv->insn, insn)
7737 && loop_insn_first_p (insn, giv->insn))))
7743 /* If BL appears in X (part of the pattern of INSN), see if we can
7744 eliminate its use. If so, return 1. If not, return 0.
7746 If BIV does not appear in X, return 1.
7748 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7749 where extra insns should be added. Depending on how many items have been
7750 moved out of the loop, it will either be before INSN or at the start of
7754 maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
7755 const struct loop *loop;
7757 struct iv_class *bl;
7761 enum rtx_code code = GET_CODE (x);
7762 rtx reg = bl->biv->dest_reg;
7763 enum machine_mode mode = GET_MODE (reg);
7764 struct induction *v;
7776 /* If we haven't already been able to do something with this BIV,
7777 we can't eliminate it. */
7783 /* If this sets the BIV, it is not a problem. */
7784 if (SET_DEST (x) == reg)
7787 /* If this is an insn that defines a giv, it is also ok because
7788 it will go away when the giv is reduced. */
7789 for (v = bl->giv; v; v = v->next_iv)
7790 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7794 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7796 /* Can replace with any giv that was reduced and
7797 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7798 Require a constant for MULT_VAL, so we know it's nonzero.
7799 ??? We disable this optimization to avoid potential
7802 for (v = bl->giv; v; v = v->next_iv)
7803 if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
7804 && v->add_val == const0_rtx
7805 && ! v->ignore && ! v->maybe_dead && v->always_computable
7809 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7815 /* If the giv has the opposite direction of change,
7816 then reverse the comparison. */
7817 if (INTVAL (v->mult_val) < 0)
7818 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7819 const0_rtx, v->new_reg);
7823 /* We can probably test that giv's reduced reg. */
7824 if (validate_change (insn, &SET_SRC (x), new, 0))
7828 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7829 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7830 Require a constant for MULT_VAL, so we know it's nonzero.
7831 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7832 overflow problem. */
7834 for (v = bl->giv; v; v = v->next_iv)
7835 if (GET_CODE (v->mult_val) == CONST_INT
7836 && v->mult_val != const0_rtx
7837 && ! v->ignore && ! v->maybe_dead && v->always_computable
7839 && (GET_CODE (v->add_val) == SYMBOL_REF
7840 || GET_CODE (v->add_val) == LABEL_REF
7841 || GET_CODE (v->add_val) == CONST
7842 || (GET_CODE (v->add_val) == REG
7843 && REGNO_POINTER_FLAG (REGNO (v->add_val)))))
7845 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7851 /* If the giv has the opposite direction of change,
7852 then reverse the comparison. */
7853 if (INTVAL (v->mult_val) < 0)
7854 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
7857 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
7858 copy_rtx (v->add_val));
7860 /* Replace biv with the giv's reduced register. */
7861 update_reg_last_use (v->add_val, insn);
7862 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7865 /* Insn doesn't support that constant or invariant. Copy it
7866 into a register (it will be a loop invariant.) */
7867 tem = gen_reg_rtx (GET_MODE (v->new_reg));
7869 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
7872 /* Substitute the new register for its invariant value in
7873 the compare expression. */
7874 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
7875 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7884 case GT: case GE: case GTU: case GEU:
7885 case LT: case LE: case LTU: case LEU:
7886 /* See if either argument is the biv. */
7887 if (XEXP (x, 0) == reg)
7888 arg = XEXP (x, 1), arg_operand = 1;
7889 else if (XEXP (x, 1) == reg)
7890 arg = XEXP (x, 0), arg_operand = 0;
7894 if (CONSTANT_P (arg))
7896 /* First try to replace with any giv that has constant positive
7897 mult_val and constant add_val. We might be able to support
7898 negative mult_val, but it seems complex to do it in general. */
7900 for (v = bl->giv; v; v = v->next_iv)
7901 if (GET_CODE (v->mult_val) == CONST_INT
7902 && INTVAL (v->mult_val) > 0
7903 && (GET_CODE (v->add_val) == SYMBOL_REF
7904 || GET_CODE (v->add_val) == LABEL_REF
7905 || GET_CODE (v->add_val) == CONST
7906 || (GET_CODE (v->add_val) == REG
7907 && REGNO_POINTER_FLAG (REGNO (v->add_val))))
7908 && ! v->ignore && ! v->maybe_dead && v->always_computable
7911 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7917 /* Replace biv with the giv's reduced reg. */
7918 validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
7920 /* If all constants are actually constant integers and
7921 the derived constant can be directly placed in the COMPARE,
7923 if (GET_CODE (arg) == CONST_INT
7924 && GET_CODE (v->mult_val) == CONST_INT
7925 && GET_CODE (v->add_val) == CONST_INT)
7927 validate_change (insn, &XEXP (x, arg_operand),
7928 GEN_INT (INTVAL (arg)
7929 * INTVAL (v->mult_val)
7930 + INTVAL (v->add_val)), 1);
7934 /* Otherwise, load it into a register. */
7935 tem = gen_reg_rtx (mode);
7936 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7937 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7939 if (apply_change_group ())
7943 /* Look for giv with positive constant mult_val and nonconst add_val.
7944 Insert insns to calculate new compare value.
7945 ??? Turn this off due to possible overflow. */
7947 for (v = bl->giv; v; v = v->next_iv)
7948 if (GET_CODE (v->mult_val) == CONST_INT
7949 && INTVAL (v->mult_val) > 0
7950 && ! v->ignore && ! v->maybe_dead && v->always_computable
7956 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7962 tem = gen_reg_rtx (mode);
7964 /* Replace biv with giv's reduced register. */
7965 validate_change (insn, &XEXP (x, 1 - arg_operand),
7968 /* Compute value to compare against. */
7969 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7970 /* Use it in this insn. */
7971 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7972 if (apply_change_group ())
7976 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
7978 if (loop_invariant_p (loop, arg) == 1)
7980 /* Look for giv with constant positive mult_val and nonconst
7981 add_val. Insert insns to compute new compare value.
7982 ??? Turn this off due to possible overflow. */
7984 for (v = bl->giv; v; v = v->next_iv)
7985 if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
7986 && ! v->ignore && ! v->maybe_dead && v->always_computable
7992 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
7998 tem = gen_reg_rtx (mode);
8000 /* Replace biv with giv's reduced register. */
8001 validate_change (insn, &XEXP (x, 1 - arg_operand),
8004 /* Compute value to compare against. */
8005 emit_iv_add_mult (arg, v->mult_val, v->add_val,
8007 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
8008 if (apply_change_group ())
8013 /* This code has problems. Basically, you can't know when
8014 seeing if we will eliminate BL, whether a particular giv
8015 of ARG will be reduced. If it isn't going to be reduced,
8016 we can't eliminate BL. We can try forcing it to be reduced,
8017 but that can generate poor code.
8019 The problem is that the benefit of reducing TV, below should
8020 be increased if BL can actually be eliminated, but this means
8021 we might have to do a topological sort of the order in which
8022 we try to process biv. It doesn't seem worthwhile to do
8023 this sort of thing now. */
8026 /* Otherwise the reg compared with had better be a biv. */
8027 if (GET_CODE (arg) != REG
8028 || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
8031 /* Look for a pair of givs, one for each biv,
8032 with identical coefficients. */
8033 for (v = bl->giv; v; v = v->next_iv)
8035 struct induction *tv;
8037 if (v->ignore || v->maybe_dead || v->mode != mode)
8040 for (tv = ivs->reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
8041 if (! tv->ignore && ! tv->maybe_dead
8042 && rtx_equal_p (tv->mult_val, v->mult_val)
8043 && rtx_equal_p (tv->add_val, v->add_val)
8044 && tv->mode == mode)
8046 if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
8052 /* Replace biv with its giv's reduced reg. */
8053 XEXP (x, 1 - arg_operand) = v->new_reg;
8054 /* Replace other operand with the other giv's
8056 XEXP (x, arg_operand) = tv->new_reg;
8063 /* If we get here, the biv can't be eliminated. */
8067 /* If this address is a DEST_ADDR giv, it doesn't matter if the
8068 biv is used in it, since it will be replaced. */
8069 for (v = bl->giv; v; v = v->next_iv)
8070 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
8078 /* See if any subexpression fails elimination. */
8079 fmt = GET_RTX_FORMAT (code);
8080 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8085 if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
8086 eliminate_p, where))
8091 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8092 if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
8093 eliminate_p, where))
8102 /* Return nonzero if the last use of REG
8103 is in an insn following INSN in the same basic block. */
8106 last_use_this_basic_block (reg, insn)
8112 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
8115 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
8121 /* Called via `note_stores' to record the initial value of a biv. Here we
8122 just record the location of the set and process it later. */
8125 record_initial (dest, set, data)
8128 void *data ATTRIBUTE_UNUSED;
8130 struct loop_ivs *ivs = (struct loop_ivs *) data;
8131 struct iv_class *bl;
8133 if (GET_CODE (dest) != REG
8134 || REGNO (dest) >= max_reg_before_loop
8135 || REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
8138 bl = ivs->reg_biv_class[REGNO (dest)];
8140 /* If this is the first set found, record it. */
8141 if (bl->init_insn == 0)
8143 bl->init_insn = note_insn;
8148 /* If any of the registers in X are "old" and currently have a last use earlier
8149 than INSN, update them to have a last use of INSN. Their actual last use
8150 will be the previous insn but it will not have a valid uid_luid so we can't
8154 update_reg_last_use (x, insn)
8158 /* Check for the case where INSN does not have a valid luid. In this case,
8159 there is no need to modify the regno_last_uid, as this can only happen
8160 when code is inserted after the loop_end to set a pseudo's final value,
8161 and hence this insn will never be the last use of x. */
8162 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
8163 && INSN_UID (insn) < max_uid_for_loop
8164 && uid_luid[REGNO_LAST_UID (REGNO (x))] < uid_luid[INSN_UID (insn)])
8165 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
8169 register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
8170 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
8173 update_reg_last_use (XEXP (x, i), insn);
8174 else if (fmt[i] == 'E')
8175 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8176 update_reg_last_use (XVECEXP (x, i, j), insn);
8181 /* Given an insn INSN and condition COND, return the condition in a
8182 canonical form to simplify testing by callers. Specifically:
8184 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
8185 (2) Both operands will be machine operands; (cc0) will have been replaced.
8186 (3) If an operand is a constant, it will be the second operand.
8187 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
8188 for GE, GEU, and LEU.
8190 If the condition cannot be understood, or is an inequality floating-point
8191 comparison which needs to be reversed, 0 will be returned.
8193 If REVERSE is non-zero, then reverse the condition prior to canonizing it.
8195 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8196 insn used in locating the condition was found. If a replacement test
8197 of the condition is desired, it should be placed in front of that
8198 insn and we will be sure that the inputs are still valid.
8200 If WANT_REG is non-zero, we wish the condition to be relative to that
8201 register, if possible. Therefore, do not canonicalize the condition
8205 canonicalize_condition (insn, cond, reverse, earliest, want_reg)
8217 int reverse_code = 0;
8218 int did_reverse_condition = 0;
8219 enum machine_mode mode;
8221 code = GET_CODE (cond);
8222 mode = GET_MODE (cond);
8223 op0 = XEXP (cond, 0);
8224 op1 = XEXP (cond, 1);
8228 code = reverse_condition (code);
8229 did_reverse_condition ^= 1;
8235 /* If we are comparing a register with zero, see if the register is set
8236 in the previous insn to a COMPARE or a comparison operation. Perform
8237 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
8240 while (GET_RTX_CLASS (code) == '<'
8241 && op1 == CONST0_RTX (GET_MODE (op0))
8244 /* Set non-zero when we find something of interest. */
8248 /* If comparison with cc0, import actual comparison from compare
8252 if ((prev = prev_nonnote_insn (prev)) == 0
8253 || GET_CODE (prev) != INSN
8254 || (set = single_set (prev)) == 0
8255 || SET_DEST (set) != cc0_rtx)
8258 op0 = SET_SRC (set);
8259 op1 = CONST0_RTX (GET_MODE (op0));
8265 /* If this is a COMPARE, pick up the two things being compared. */
8266 if (GET_CODE (op0) == COMPARE)
8268 op1 = XEXP (op0, 1);
8269 op0 = XEXP (op0, 0);
8272 else if (GET_CODE (op0) != REG)
8275 /* Go back to the previous insn. Stop if it is not an INSN. We also
8276 stop if it isn't a single set or if it has a REG_INC note because
8277 we don't want to bother dealing with it. */
8279 if ((prev = prev_nonnote_insn (prev)) == 0
8280 || GET_CODE (prev) != INSN
8281 || FIND_REG_INC_NOTE (prev, 0)
8282 || (set = single_set (prev)) == 0)
8285 /* If this is setting OP0, get what it sets it to if it looks
8287 if (rtx_equal_p (SET_DEST (set), op0))
8289 enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
8291 /* ??? We may not combine comparisons done in a CCmode with
8292 comparisons not done in a CCmode. This is to aid targets
8293 like Alpha that have an IEEE compliant EQ instruction, and
8294 a non-IEEE compliant BEQ instruction. The use of CCmode is
8295 actually artificial, simply to prevent the combination, but
8296 should not affect other platforms.
8298 However, we must allow VOIDmode comparisons to match either
8299 CCmode or non-CCmode comparison, because some ports have
8300 modeless comparisons inside branch patterns.
8302 ??? This mode check should perhaps look more like the mode check
8303 in simplify_comparison in combine. */
8305 if ((GET_CODE (SET_SRC (set)) == COMPARE
8308 && GET_MODE_CLASS (inner_mode) == MODE_INT
8309 && (GET_MODE_BITSIZE (inner_mode)
8310 <= HOST_BITS_PER_WIDE_INT)
8311 && (STORE_FLAG_VALUE
8312 & ((HOST_WIDE_INT) 1
8313 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8314 #ifdef FLOAT_STORE_FLAG_VALUE
8316 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8317 && (REAL_VALUE_NEGATIVE
8318 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8321 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
8322 && (((GET_MODE_CLASS (mode) == MODE_CC)
8323 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8324 || mode == VOIDmode || inner_mode == VOIDmode))
8326 else if (((code == EQ
8328 && (GET_MODE_BITSIZE (inner_mode)
8329 <= HOST_BITS_PER_WIDE_INT)
8330 && GET_MODE_CLASS (inner_mode) == MODE_INT
8331 && (STORE_FLAG_VALUE
8332 & ((HOST_WIDE_INT) 1
8333 << (GET_MODE_BITSIZE (inner_mode) - 1))))
8334 #ifdef FLOAT_STORE_FLAG_VALUE
8336 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
8337 && (REAL_VALUE_NEGATIVE
8338 (FLOAT_STORE_FLAG_VALUE (inner_mode))))
8341 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
8342 && (((GET_MODE_CLASS (mode) == MODE_CC)
8343 == (GET_MODE_CLASS (inner_mode) == MODE_CC))
8344 || mode == VOIDmode || inner_mode == VOIDmode))
8347 /* We might have reversed a LT to get a GE here. But this wasn't
8348 actually the comparison of data, so we don't flag that we
8349 have had to reverse the condition. */
8350 did_reverse_condition ^= 1;
8358 else if (reg_set_p (op0, prev))
8359 /* If this sets OP0, but not directly, we have to give up. */
8364 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
8365 code = GET_CODE (x);
8368 code = reverse_condition (code);
8369 if (code == UNKNOWN)
8371 did_reverse_condition ^= 1;
8375 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
8381 /* If constant is first, put it last. */
8382 if (CONSTANT_P (op0))
8383 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
8385 /* If OP0 is the result of a comparison, we weren't able to find what
8386 was really being compared, so fail. */
8387 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
8390 /* Canonicalize any ordered comparison with integers involving equality
8391 if we can do computations in the relevant mode and we do not
8394 if (GET_CODE (op1) == CONST_INT
8395 && GET_MODE (op0) != VOIDmode
8396 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
8398 HOST_WIDE_INT const_val = INTVAL (op1);
8399 unsigned HOST_WIDE_INT uconst_val = const_val;
8400 unsigned HOST_WIDE_INT max_val
8401 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
8406 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
8407 code = LT, op1 = GEN_INT (const_val + 1);
8410 /* When cross-compiling, const_val might be sign-extended from
8411 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
8413 if ((HOST_WIDE_INT) (const_val & max_val)
8414 != (((HOST_WIDE_INT) 1
8415 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
8416 code = GT, op1 = GEN_INT (const_val - 1);
8420 if (uconst_val < max_val)
8421 code = LTU, op1 = GEN_INT (uconst_val + 1);
8425 if (uconst_val != 0)
8426 code = GTU, op1 = GEN_INT (uconst_val - 1);
8434 /* If this was floating-point and we reversed anything other than an
8435 EQ or NE or (UN)ORDERED, return zero. */
8436 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
8437 && did_reverse_condition
8438 && code != NE && code != EQ && code != UNORDERED && code != ORDERED
8440 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
8444 /* Never return CC0; return zero instead. */
8449 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
8452 /* Given a jump insn JUMP, return the condition that will cause it to branch
8453 to its JUMP_LABEL. If the condition cannot be understood, or is an
8454 inequality floating-point comparison which needs to be reversed, 0 will
8457 If EARLIEST is non-zero, it is a pointer to a place where the earliest
8458 insn used in locating the condition was found. If a replacement test
8459 of the condition is desired, it should be placed in front of that
8460 insn and we will be sure that the inputs are still valid. */
8463 get_condition (jump, earliest)
8471 /* If this is not a standard conditional jump, we can't parse it. */
8472 if (GET_CODE (jump) != JUMP_INSN
8473 || ! any_condjump_p (jump))
8475 set = pc_set (jump);
8477 cond = XEXP (SET_SRC (set), 0);
8479 /* If this branches to JUMP_LABEL when the condition is false, reverse
8482 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
8483 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
8485 return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
8488 /* Similar to above routine, except that we also put an invariant last
8489 unless both operands are invariants. */
8492 get_condition_for_loop (loop, x)
8493 const struct loop *loop;
8496 rtx comparison = get_condition (x, NULL_PTR);
8499 || ! loop_invariant_p (loop, XEXP (comparison, 0))
8500 || loop_invariant_p (loop, XEXP (comparison, 1)))
8503 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
8504 XEXP (comparison, 1), XEXP (comparison, 0));
8507 /* Scan the function and determine whether it has indirect (computed) jumps.
8509 This is taken mostly from flow.c; similar code exists elsewhere
8510 in the compiler. It may be useful to put this into rtlanal.c. */
8512 indirect_jump_in_function_p (start)
8517 for (insn = start; insn; insn = NEXT_INSN (insn))
8518 if (computed_jump_p (insn))
8524 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8525 documentation for LOOP_MEMS for the definition of `appropriate'.
8526 This function is called from prescan_loop via for_each_rtx. */
8529 insert_loop_mem (mem, data)
8531 void *data ATTRIBUTE_UNUSED;
8533 struct loop_info *loop_info = data;
8540 switch (GET_CODE (m))
8546 /* We're not interested in MEMs that are only clobbered. */
8550 /* We're not interested in the MEM associated with a
8551 CONST_DOUBLE, so there's no need to traverse into this. */
8555 /* We're not interested in any MEMs that only appear in notes. */
8559 /* This is not a MEM. */
8563 /* See if we've already seen this MEM. */
8564 for (i = 0; i < loop_info->mems_idx; ++i)
8565 if (rtx_equal_p (m, loop_info->mems[i].mem))
8567 if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
8568 /* The modes of the two memory accesses are different. If
8569 this happens, something tricky is going on, and we just
8570 don't optimize accesses to this MEM. */
8571 loop_info->mems[i].optimize = 0;
8576 /* Resize the array, if necessary. */
8577 if (loop_info->mems_idx == loop_info->mems_allocated)
8579 if (loop_info->mems_allocated != 0)
8580 loop_info->mems_allocated *= 2;
8582 loop_info->mems_allocated = 32;
8584 loop_info->mems = (loop_mem_info *)
8585 xrealloc (loop_info->mems,
8586 loop_info->mems_allocated * sizeof (loop_mem_info));
8589 /* Actually insert the MEM. */
8590 loop_info->mems[loop_info->mems_idx].mem = m;
8591 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8592 because we can't put it in a register. We still store it in the
8593 table, though, so that if we see the same address later, but in a
8594 non-BLK mode, we'll not think we can optimize it at that point. */
8595 loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
8596 loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
8597 ++loop_info->mems_idx;
8602 /* Like load_mems, but also ensures that REGS->SET_IN_LOOP,
8603 REGS->MAY_NOT_OPTIMIZE, REGS->SINGLE_USAGE, and INSN_COUNT have the correct
8604 values after load_mems. */
8607 load_mems_and_recount_loop_regs_set (loop, insn_count)
8608 const struct loop *loop;
8611 struct loop_regs *regs = LOOP_REGS (loop);
8612 int nregs = max_reg_num ();
8616 /* Recalculate regs->set_in_loop and friends since load_mems may have
8617 created new registers. */
8618 if (max_reg_num () > nregs)
8624 nregs = max_reg_num ();
8626 if ((unsigned) nregs > regs->set_in_loop->num_elements)
8628 /* Grow all the arrays. */
8629 VARRAY_GROW (regs->set_in_loop, nregs);
8630 VARRAY_GROW (regs->n_times_set, nregs);
8631 VARRAY_GROW (regs->may_not_optimize, nregs);
8632 VARRAY_GROW (regs->single_usage, nregs);
8634 /* Clear the arrays */
8635 bzero ((char *) ®s->set_in_loop->data, nregs * sizeof (int));
8636 bzero ((char *) ®s->may_not_optimize->data, nregs * sizeof (char));
8637 bzero ((char *) ®s->single_usage->data, nregs * sizeof (rtx));
8639 count_loop_regs_set (loop, regs->may_not_optimize, regs->single_usage,
8642 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8644 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8645 VARRAY_INT (regs->set_in_loop, i) = 1;
8648 #ifdef AVOID_CCMODE_COPIES
8649 /* Don't try to move insns which set CC registers if we should not
8650 create CCmode register copies. */
8651 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8652 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8653 VARRAY_CHAR (regs->may_not_optimize, i) = 1;
8656 /* Set regs->n_times_set for the new registers. */
8657 bcopy ((char *) (®s->set_in_loop->data.i[0] + old_nregs),
8658 (char *) (®s->n_times_set->data.i[0] + old_nregs),
8659 (nregs - old_nregs) * sizeof (int));
8663 /* Move MEMs into registers for the duration of the loop. */
8667 const struct loop *loop;
8669 struct loop_info *loop_info = LOOP_INFO (loop);
8670 struct loop_regs *regs = LOOP_REGS (loop);
8671 int maybe_never = 0;
8674 rtx label = NULL_RTX;
8675 rtx end_label = NULL_RTX;
8676 /* Nonzero if the next instruction may never be executed. */
8677 int next_maybe_never = 0;
8678 int last_max_reg = max_reg_num ();
8680 if (loop_info->mems_idx == 0)
8683 /* Find start of the extended basic block that enters the loop. */
8684 for (p = loop->start;
8685 PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
8691 /* Build table of mems that get set to constant values before the
8693 for (; p != loop->start; p = NEXT_INSN (p))
8694 cselib_process_insn (p);
8696 /* Check to see if it's possible that some instructions in the
8697 loop are never executed. */
8698 for (p = next_insn_in_loop (loop, loop->scan_start);
8699 p != NULL_RTX && ! maybe_never;
8700 p = next_insn_in_loop (loop, p))
8702 if (GET_CODE (p) == CODE_LABEL)
8704 else if (GET_CODE (p) == JUMP_INSN
8705 /* If we enter the loop in the middle, and scan
8706 around to the beginning, don't set maybe_never
8707 for that. This must be an unconditional jump,
8708 otherwise the code at the top of the loop might
8709 never be executed. Unconditional jumps are
8710 followed a by barrier then loop end. */
8711 && ! (GET_CODE (p) == JUMP_INSN
8712 && JUMP_LABEL (p) == loop->top
8713 && NEXT_INSN (NEXT_INSN (p)) == loop->end
8714 && any_uncondjump_p (p)))
8716 if (!any_condjump_p (p))
8717 /* Something complicated. */
8720 /* If there are any more instructions in the loop, they
8721 might not be reached. */
8722 next_maybe_never = 1;
8724 else if (next_maybe_never)
8728 /* Actually move the MEMs. */
8729 for (i = 0; i < loop_info->mems_idx; ++i)
8731 regset_head load_copies;
8732 regset_head store_copies;
8735 rtx mem = loop_info->mems[i].mem;
8738 if (MEM_VOLATILE_P (mem)
8739 || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
8740 /* There's no telling whether or not MEM is modified. */
8741 loop_info->mems[i].optimize = 0;
8743 /* Go through the MEMs written to in the loop to see if this
8744 one is aliased by one of them. */
8745 mem_list_entry = loop_info->store_mems;
8746 while (mem_list_entry)
8748 if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
8750 else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
8753 /* MEM is indeed aliased by this store. */
8754 loop_info->mems[i].optimize = 0;
8757 mem_list_entry = XEXP (mem_list_entry, 1);
8760 if (flag_float_store && written
8761 && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
8762 loop_info->mems[i].optimize = 0;
8764 /* If this MEM is written to, we must be sure that there
8765 are no reads from another MEM that aliases this one. */
8766 if (loop_info->mems[i].optimize && written)
8770 for (j = 0; j < loop_info->mems_idx; ++j)
8774 else if (true_dependence (mem,
8776 loop_info->mems[j].mem,
8779 /* It's not safe to hoist loop_info->mems[i] out of
8780 the loop because writes to it might not be
8781 seen by reads from loop_info->mems[j]. */
8782 loop_info->mems[i].optimize = 0;
8788 if (maybe_never && may_trap_p (mem))
8789 /* We can't access the MEM outside the loop; it might
8790 cause a trap that wouldn't have happened otherwise. */
8791 loop_info->mems[i].optimize = 0;
8793 if (!loop_info->mems[i].optimize)
8794 /* We thought we were going to lift this MEM out of the
8795 loop, but later discovered that we could not. */
8798 INIT_REG_SET (&load_copies);
8799 INIT_REG_SET (&store_copies);
8801 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8802 order to keep scan_loop from moving stores to this MEM
8803 out of the loop just because this REG is neither a
8804 user-variable nor used in the loop test. */
8805 reg = gen_reg_rtx (GET_MODE (mem));
8806 REG_USERVAR_P (reg) = 1;
8807 loop_info->mems[i].reg = reg;
8809 /* Now, replace all references to the MEM with the
8810 corresponding pesudos. */
8812 for (p = next_insn_in_loop (loop, loop->scan_start);
8814 p = next_insn_in_loop (loop, p))
8820 set = single_set (p);
8822 /* See if this copies the mem into a register that isn't
8823 modified afterwards. We'll try to do copy propagation
8824 a little further on. */
8826 /* @@@ This test is _way_ too conservative. */
8828 && GET_CODE (SET_DEST (set)) == REG
8829 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
8830 && REGNO (SET_DEST (set)) < last_max_reg
8831 && VARRAY_INT (regs->n_times_set,
8832 REGNO (SET_DEST (set))) == 1
8833 && rtx_equal_p (SET_SRC (set), mem))
8834 SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
8836 /* See if this copies the mem from a register that isn't
8837 modified afterwards. We'll try to remove the
8838 redundant copy later on by doing a little register
8839 renaming and copy propagation. This will help
8840 to untangle things for the BIV detection code. */
8843 && GET_CODE (SET_SRC (set)) == REG
8844 && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
8845 && REGNO (SET_SRC (set)) < last_max_reg
8846 && VARRAY_INT (regs->n_times_set, REGNO (SET_SRC (set))) == 1
8847 && rtx_equal_p (SET_DEST (set), mem))
8848 SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
8850 /* Replace the memory reference with the shadow register. */
8851 replace_loop_mems (p, loop_info->mems[i].mem,
8852 loop_info->mems[i].reg);
8855 if (GET_CODE (p) == CODE_LABEL
8856 || GET_CODE (p) == JUMP_INSN)
8860 if (! apply_change_group ())
8861 /* We couldn't replace all occurrences of the MEM. */
8862 loop_info->mems[i].optimize = 0;
8865 /* Load the memory immediately before LOOP->START, which is
8866 the NOTE_LOOP_BEG. */
8867 cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
8871 struct elt_loc_list *const_equiv = 0;
8875 struct elt_loc_list *equiv;
8876 struct elt_loc_list *best_equiv = 0;
8877 for (equiv = e->locs; equiv; equiv = equiv->next)
8879 if (CONSTANT_P (equiv->loc))
8880 const_equiv = equiv;
8881 else if (GET_CODE (equiv->loc) == REG
8882 /* Extending hard register lifetimes cuases crash
8883 on SRC targets. Doing so on non-SRC is
8884 probably also not good idea, since we most
8885 probably have pseudoregister equivalence as
8887 && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
8890 /* Use the constant equivalence if that is cheap enough. */
8892 best_equiv = const_equiv;
8893 else if (const_equiv
8894 && (rtx_cost (const_equiv->loc, SET)
8895 <= rtx_cost (best_equiv->loc, SET)))
8897 best_equiv = const_equiv;
8901 /* If best_equiv is nonzero, we know that MEM is set to a
8902 constant or register before the loop. We will use this
8903 knowledge to initialize the shadow register with that
8904 constant or reg rather than by loading from MEM. */
8906 best = copy_rtx (best_equiv->loc);
8908 set = gen_move_insn (reg, best);
8909 set = emit_insn_before (set, loop->start);
8911 REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
8912 copy_rtx (const_equiv->loc),
8917 if (label == NULL_RTX)
8919 /* We must compute the former
8920 right-after-the-end label before we insert
8922 end_label = next_label (loop->end);
8923 label = gen_label_rtx ();
8924 emit_label_after (label, loop->end);
8927 /* Store the memory immediately after END, which is
8928 the NOTE_LOOP_END. */
8929 set = gen_move_insn (copy_rtx (mem), reg);
8930 emit_insn_after (set, label);
8933 if (loop_dump_stream)
8935 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
8936 REGNO (reg), (written ? "r/w" : "r/o"));
8937 print_rtl (loop_dump_stream, mem);
8938 fputc ('\n', loop_dump_stream);
8941 /* Attempt a bit of copy propagation. This helps untangle the
8942 data flow, and enables {basic,general}_induction_var to find
8944 EXECUTE_IF_SET_IN_REG_SET
8945 (&load_copies, FIRST_PSEUDO_REGISTER, j,
8947 try_copy_prop (loop, reg, j);
8949 CLEAR_REG_SET (&load_copies);
8951 EXECUTE_IF_SET_IN_REG_SET
8952 (&store_copies, FIRST_PSEUDO_REGISTER, j,
8954 try_swap_copy_prop (loop, reg, j);
8956 CLEAR_REG_SET (&store_copies);
8960 if (label != NULL_RTX)
8962 /* Now, we need to replace all references to the previous exit
8963 label with the new one. */
8968 for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
8970 for_each_rtx (&p, replace_label, &rr);
8972 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
8973 field. This is not handled by for_each_rtx because it doesn't
8974 handle unprinted ('0') fields. We need to update JUMP_LABEL
8975 because the immediately following unroll pass will use it.
8976 replace_label would not work anyways, because that only handles
8978 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
8979 JUMP_LABEL (p) = label;
8986 /* For communication between note_reg_stored and its caller. */
8987 struct note_reg_stored_arg
8993 /* Called via note_stores, record in SET_SEEN whether X, which is written,
8996 note_reg_stored (x, setter, arg)
8997 rtx x, setter ATTRIBUTE_UNUSED;
9000 struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
9005 /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
9006 There must be exactly one insn that sets this pseudo; it will be
9007 deleted if all replacements succeed and we can prove that the register
9008 is not used after the loop. */
9011 try_copy_prop (loop, replacement, regno)
9012 const struct loop *loop;
9016 /* This is the reg that we are copying from. */
9017 rtx reg_rtx = regno_reg_rtx[regno];
9020 /* These help keep track of whether we replaced all uses of the reg. */
9021 int replaced_last = 0;
9022 int store_is_first = 0;
9024 for (insn = next_insn_in_loop (loop, loop->scan_start);
9026 insn = next_insn_in_loop (loop, insn))
9030 /* Only substitute within one extended basic block from the initializing
9032 if (GET_CODE (insn) == CODE_LABEL && init_insn)
9035 if (! INSN_P (insn))
9038 /* Is this the initializing insn? */
9039 set = single_set (insn);
9041 && GET_CODE (SET_DEST (set)) == REG
9042 && REGNO (SET_DEST (set)) == regno)
9048 if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
9052 /* Only substitute after seeing the initializing insn. */
9053 if (init_insn && insn != init_insn)
9055 struct note_reg_stored_arg arg;
9057 replace_loop_regs (insn, reg_rtx, replacement);
9058 if (REGNO_LAST_UID (regno) == INSN_UID (insn))
9061 /* Stop replacing when REPLACEMENT is modified. */
9062 arg.reg = replacement;
9064 note_stores (PATTERN (insn), note_reg_stored, &arg);
9071 if (apply_change_group ())
9073 if (loop_dump_stream)
9074 fprintf (loop_dump_stream, " Replaced reg %d", regno);
9075 if (store_is_first && replaced_last)
9077 PUT_CODE (init_insn, NOTE);
9078 NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
9079 if (loop_dump_stream)
9080 fprintf (loop_dump_stream, ", deleting init_insn (%d)",
9081 INSN_UID (init_insn));
9083 if (loop_dump_stream)
9084 fprintf (loop_dump_stream, ".\n");
9088 /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
9089 loop LOOP if the order of the sets of these registers can be
9090 swapped. There must be exactly one insn within the loop that sets
9091 this pseudo followed immediately by a move insn that sets
9092 REPLACEMENT with REGNO. */
9094 try_swap_copy_prop (loop, replacement, regno)
9095 const struct loop *loop;
9101 unsigned int new_regno;
9103 new_regno = REGNO (replacement);
9105 for (insn = next_insn_in_loop (loop, loop->scan_start);
9107 insn = next_insn_in_loop (loop, insn))
9109 /* Search for the insn that copies REGNO to NEW_REGNO? */
9110 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9111 && (set = single_set (insn))
9112 && GET_CODE (SET_DEST (set)) == REG
9113 && REGNO (SET_DEST (set)) == new_regno
9114 && GET_CODE (SET_SRC (set)) == REG
9115 && REGNO (SET_SRC (set)) == regno)
9119 if (insn != NULL_RTX)
9124 /* Some DEF-USE info would come in handy here to make this
9125 function more general. For now, just check the previous insn
9126 which is the most likely candidate for setting REGNO. */
9128 prev_insn = PREV_INSN (insn);
9130 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
9131 && (prev_set = single_set (prev_insn))
9132 && GET_CODE (SET_DEST (prev_set)) == REG
9133 && REGNO (SET_DEST (prev_set)) == regno)
9136 (set (reg regno) (expr))
9137 (set (reg new_regno) (reg regno))
9139 so try converting this to:
9140 (set (reg new_regno) (expr))
9141 (set (reg regno) (reg new_regno))
9143 The former construct is often generated when a global
9144 variable used for an induction variable is shadowed by a
9145 register (NEW_REGNO). The latter construct improves the
9146 chances of GIV replacement and BIV elimination. */
9148 validate_change (prev_insn, &SET_DEST (prev_set),
9150 validate_change (insn, &SET_DEST (set),
9152 validate_change (insn, &SET_SRC (set),
9155 if (apply_change_group ())
9157 if (loop_dump_stream)
9158 fprintf (loop_dump_stream,
9159 " Swapped set of reg %d at %d with reg %d at %d.\n",
9160 regno, INSN_UID (insn),
9161 new_regno, INSN_UID (prev_insn));
9163 /* Update first use of REGNO. */
9164 if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
9165 REGNO_FIRST_UID (regno) = INSN_UID (insn);
9167 /* Now perform copy propagation to hopefully
9168 remove all uses of REGNO within the loop. */
9169 try_copy_prop (loop, replacement, regno);
9175 /* Replace MEM with its associated pseudo register. This function is
9176 called from load_mems via for_each_rtx. DATA is actually a pointer
9177 to a structure describing the instruction currently being scanned
9178 and the MEM we are currently replacing. */
9181 replace_loop_mem (mem, data)
9185 loop_replace_args *args = (loop_replace_args *) data;
9191 switch (GET_CODE (m))
9197 /* We're not interested in the MEM associated with a
9198 CONST_DOUBLE, so there's no need to traverse into one. */
9202 /* This is not a MEM. */
9206 if (!rtx_equal_p (args->match, m))
9207 /* This is not the MEM we are currently replacing. */
9210 /* Actually replace the MEM. */
9211 validate_change (args->insn, mem, args->replacement, 1);
9217 replace_loop_mems (insn, mem, reg)
9222 loop_replace_args args;
9226 args.replacement = reg;
9228 for_each_rtx (&insn, replace_loop_mem, &args);
9231 /* Replace one register with another. Called through for_each_rtx; PX points
9232 to the rtx being scanned. DATA is actually a pointer to
9233 a structure of arguments. */
9236 replace_loop_reg (px, data)
9241 loop_replace_args *args = (loop_replace_args *) data;
9246 if (x == args->match)
9247 validate_change (args->insn, px, args->replacement, 1);
9253 replace_loop_regs (insn, reg, replacement)
9258 loop_replace_args args;
9262 args.replacement = replacement;
9264 for_each_rtx (&insn, replace_loop_reg, &args);
9267 /* Replace occurrences of the old exit label for the loop with the new
9268 one. DATA is an rtx_pair containing the old and new labels,
9272 replace_label (x, data)
9277 rtx old_label = ((rtx_pair *) data)->r1;
9278 rtx new_label = ((rtx_pair *) data)->r2;
9283 if (GET_CODE (l) != LABEL_REF)
9286 if (XEXP (l, 0) != old_label)
9289 XEXP (l, 0) = new_label;
9290 ++LABEL_NUSES (new_label);
9291 --LABEL_NUSES (old_label);
9296 #define LOOP_BLOCK_NUM_1(INSN) \
9297 ((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
9299 /* The notes do not have an assigned block, so look at the next insn. */
9300 #define LOOP_BLOCK_NUM(INSN) \
9301 ((INSN) ? (GET_CODE (INSN) == NOTE \
9302 ? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
9303 : LOOP_BLOCK_NUM_1 (INSN)) \
9306 #define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
9309 loop_dump_aux (loop, file, verbose)
9310 const struct loop *loop;
9316 if (! loop || ! file)
9319 /* Print diagnostics to compare our concept of a loop with
9320 what the loop notes say. */
9321 if (! PREV_INSN (loop->first->head)
9322 || GET_CODE (PREV_INSN (loop->first->head)) != NOTE
9323 || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
9324 != NOTE_INSN_LOOP_BEG)
9325 fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
9326 INSN_UID (PREV_INSN (loop->first->head)));
9327 if (! NEXT_INSN (loop->last->end)
9328 || GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
9329 || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
9330 != NOTE_INSN_LOOP_END)
9331 fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
9332 INSN_UID (NEXT_INSN (loop->last->end)));
9337 ";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
9338 LOOP_BLOCK_NUM (loop->start),
9339 LOOP_INSN_UID (loop->start),
9340 LOOP_BLOCK_NUM (loop->cont),
9341 LOOP_INSN_UID (loop->cont),
9342 LOOP_BLOCK_NUM (loop->cont),
9343 LOOP_INSN_UID (loop->cont),
9344 LOOP_BLOCK_NUM (loop->vtop),
9345 LOOP_INSN_UID (loop->vtop),
9346 LOOP_BLOCK_NUM (loop->end),
9347 LOOP_INSN_UID (loop->end));
9348 fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
9349 LOOP_BLOCK_NUM (loop->top),
9350 LOOP_INSN_UID (loop->top),
9351 LOOP_BLOCK_NUM (loop->scan_start),
9352 LOOP_INSN_UID (loop->scan_start));
9353 fprintf (file, ";; exit_count %d", loop->exit_count);
9354 if (loop->exit_count)
9356 fputs (", labels:", file);
9357 for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
9359 fprintf (file, " %d ",
9360 LOOP_INSN_UID (XEXP (label, 0)));
9365 /* This can happen when a marked loop appears as two nested loops,
9366 say from while (a || b) {}. The inner loop won't match
9367 the loop markers but the outer one will. */
9368 if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
9369 fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
9373 /* Call this function from the debugger to dump LOOP. */
9377 const struct loop *loop;
9379 flow_loop_dump (loop, stderr, loop_dump_aux, 1);
OSDN Git Service
