1 /* Perform various loop optimizations, including strength reduction.
2 Copyright (C) 1987, 88, 89, 91-97, 1998 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 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. */
42 #include "insn-config.h"
43 #include "insn-flags.h"
45 #include "hard-reg-set.h"
53 /* Vector mapping INSN_UIDs to luids.
54 The luids are like uids but increase monotonically always.
55 We use them to see whether a jump comes from outside a given loop. */
59 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
60 number the insn is contained in. */
64 /* 1 + largest uid of any insn. */
68 /* 1 + luid of last insn. */
72 /* Number of loops detected in current function. Used as index to the
75 static int max_loop_num;
77 /* Indexed by loop number, contains the first and last insn of each loop. */
79 static rtx *loop_number_loop_starts, *loop_number_loop_ends;
81 /* For each loop, gives the containing loop number, -1 if none. */
86 /* The main output of analyze_loop_iterations is placed here */
88 int *loop_can_insert_bct;
90 /* For each loop, determines whether some of its inner loops has used
93 int *loop_used_count_register;
95 /* loop parameters for arithmetic loops. These loops have a loop variable
96 which is initialized to loop_start_value, incremented in each iteration
97 by "loop_increment". At the end of the iteration the loop variable is
98 compared to the loop_comparison_value (using loop_comparison_code). */
101 rtx *loop_comparison_value;
102 rtx *loop_start_value;
103 enum rtx_code *loop_comparison_code;
106 /* For each loop, keep track of its unrolling factor.
110 -1: completely unrolled
111 >0: holds the unroll exact factor. */
112 int *loop_unroll_factor;
114 /* Indexed by loop number, contains a nonzero value if the "loop" isn't
115 really a loop (an insn outside the loop branches into it). */
117 static char *loop_invalid;
119 /* Indexed by loop number, links together all LABEL_REFs which refer to
120 code labels outside the loop. Used by routines that need to know all
121 loop exits, such as final_biv_value and final_giv_value.
123 This does not include loop exits due to return instructions. This is
124 because all bivs and givs are pseudos, and hence must be dead after a
125 return, so the presense of a return does not affect any of the
126 optimizations that use this info. It is simpler to just not include return
127 instructions on this list. */
129 rtx *loop_number_exit_labels;
131 /* Indexed by loop number, counts the number of LABEL_REFs on
132 loop_number_exit_labels for this loop and all loops nested inside it. */
134 int *loop_number_exit_count;
136 /* Holds the number of loop iterations. It is zero if the number could not be
137 calculated. Must be unsigned since the number of iterations can
138 be as high as 2^wordsize-1. For loops with a wider iterator, this number
139 will be zero if the number of loop iterations is too large for an
140 unsigned integer to hold. */
142 unsigned HOST_WIDE_INT loop_n_iterations;
144 /* Nonzero if there is a subroutine call in the current loop. */
146 static int loop_has_call;
148 /* Nonzero if there is a volatile memory reference in the current
151 static int loop_has_volatile;
153 /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
154 current loop. A continue statement will generate a branch to
155 NEXT_INSN (loop_continue). */
157 static rtx loop_continue;
159 /* Indexed by register number, contains the number of times the reg
160 is set during the loop being scanned.
161 During code motion, a negative value indicates a reg that has been
162 made a candidate; in particular -2 means that it is an candidate that
163 we know is equal to a constant and -1 means that it is an candidate
164 not known equal to a constant.
165 After code motion, regs moved have 0 (which is accurate now)
166 while the failed candidates have the original number of times set.
168 Therefore, at all times, == 0 indicates an invariant register;
169 < 0 a conditionally invariant one. */
171 static varray_type n_times_set;
173 /* Original value of n_times_set; same except that this value
174 is not set negative for a reg whose sets have been made candidates
175 and not set to 0 for a reg that is moved. */
177 static varray_type n_times_used;
179 /* Index by register number, 1 indicates that the register
180 cannot be moved or strength reduced. */
182 static varray_type may_not_optimize;
184 /* Nonzero means reg N has already been moved out of one loop.
185 This reduces the desire to move it out of another. */
187 static char *moved_once;
189 /* Array of MEMs that are stored in this loop. If there are too many to fit
190 here, we just turn on unknown_address_altered. */
192 #define NUM_STORES 30
193 static rtx loop_store_mems[NUM_STORES];
195 /* Index of first available slot in above array. */
196 static int loop_store_mems_idx;
198 typedef struct loop_mem_info {
199 rtx mem; /* The MEM itself. */
200 rtx reg; /* Corresponding pseudo, if any. */
201 int optimize; /* Nonzero if we can optimize access to this MEM. */
204 /* Array of MEMs that are used (read or written) in this loop, but
205 cannot be aliased by anything in this loop, except perhaps
206 themselves. In other words, if loop_mems[i] is altered during the
207 loop, it is altered by an expression that is rtx_equal_p to it. */
209 static loop_mem_info *loop_mems;
211 /* The index of the next available slot in LOOP_MEMS. */
213 static int loop_mems_idx;
215 /* The number of elements allocated in LOOP_MEMs. */
217 static int loop_mems_allocated;
219 /* Nonzero if we don't know what MEMs were changed in the current loop.
220 This happens if the loop contains a call (in which case `loop_has_call'
221 will also be set) or if we store into more than NUM_STORES MEMs. */
223 static int unknown_address_altered;
225 /* Count of movable (i.e. invariant) instructions discovered in the loop. */
226 static int num_movables;
228 /* Count of memory write instructions discovered in the loop. */
229 static int num_mem_sets;
231 /* Number of loops contained within the current one, including itself. */
232 static int loops_enclosed;
234 /* Bound on pseudo register number before loop optimization.
235 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
236 int max_reg_before_loop;
238 /* This obstack is used in product_cheap_p to allocate its rtl. It
239 may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
240 If we used the same obstack that it did, we would be deallocating
243 static struct obstack temp_obstack;
245 /* This is where the pointer to the obstack being used for RTL is stored. */
247 extern struct obstack *rtl_obstack;
249 #define obstack_chunk_alloc xmalloc
250 #define obstack_chunk_free free
252 /* During the analysis of a loop, a chain of `struct movable's
253 is made to record all the movable insns found.
254 Then the entire chain can be scanned to decide which to move. */
258 rtx insn; /* A movable insn */
259 rtx set_src; /* The expression this reg is set from. */
260 rtx set_dest; /* The destination of this SET. */
261 rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
262 of any registers used within the LIBCALL. */
263 int consec; /* Number of consecutive following insns
264 that must be moved with this one. */
265 int regno; /* The register it sets */
266 short lifetime; /* lifetime of that register;
267 may be adjusted when matching movables
268 that load the same value are found. */
269 short savings; /* Number of insns we can move for this reg,
270 including other movables that force this
271 or match this one. */
272 unsigned int cond : 1; /* 1 if only conditionally movable */
273 unsigned int force : 1; /* 1 means MUST move this insn */
274 unsigned int global : 1; /* 1 means reg is live outside this loop */
275 /* If PARTIAL is 1, GLOBAL means something different:
276 that the reg is live outside the range from where it is set
277 to the following label. */
278 unsigned int done : 1; /* 1 inhibits further processing of this */
280 unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
281 In particular, moving it does not make it
283 unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
284 load SRC, rather than copying INSN. */
285 unsigned int move_insn_first:1;/* Same as above, if this is necessary for the
286 first insn of a consecutive sets group. */
287 unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
288 enum machine_mode savemode; /* Nonzero means it is a mode for a low part
289 that we should avoid changing when clearing
290 the rest of the reg. */
291 struct movable *match; /* First entry for same value */
292 struct movable *forces; /* An insn that must be moved if this is */
293 struct movable *next;
296 static struct movable *the_movables;
298 FILE *loop_dump_stream;
300 /* Forward declarations. */
302 static void find_and_verify_loops PROTO((rtx));
303 static void mark_loop_jump PROTO((rtx, int));
304 static void prescan_loop PROTO((rtx, rtx));
305 static int reg_in_basic_block_p PROTO((rtx, rtx));
306 static int consec_sets_invariant_p PROTO((rtx, int, rtx));
307 static rtx libcall_other_reg PROTO((rtx, rtx));
308 static int labels_in_range_p PROTO((rtx, int));
309 static void count_loop_regs_set PROTO((rtx, rtx, varray_type, varray_type,
311 static void note_addr_stored PROTO((rtx, rtx));
312 static int loop_reg_used_before_p PROTO((rtx, rtx, rtx, rtx, rtx));
313 static void scan_loop PROTO((rtx, rtx, int, int));
315 static void replace_call_address PROTO((rtx, rtx, rtx));
317 static rtx skip_consec_insns PROTO((rtx, int));
318 static int libcall_benefit PROTO((rtx));
319 static void ignore_some_movables PROTO((struct movable *));
320 static void force_movables PROTO((struct movable *));
321 static void combine_movables PROTO((struct movable *, int));
322 static int regs_match_p PROTO((rtx, rtx, struct movable *));
323 static int rtx_equal_for_loop_p PROTO((rtx, rtx, struct movable *));
324 static void add_label_notes PROTO((rtx, rtx));
325 static void move_movables PROTO((struct movable *, int, int, rtx, rtx, int));
326 static int count_nonfixed_reads PROTO((rtx));
327 static void strength_reduce PROTO((rtx, rtx, rtx, int, rtx, rtx, int, int));
328 static void find_single_use_in_loop PROTO((rtx, rtx, varray_type));
329 static int valid_initial_value_p PROTO((rtx, rtx, int, rtx));
330 static void find_mem_givs PROTO((rtx, rtx, int, rtx, rtx));
331 static void record_biv PROTO((struct induction *, rtx, rtx, rtx, rtx, int, int));
332 static void check_final_value PROTO((struct induction *, rtx, rtx));
333 static void record_giv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx, int, enum g_types, int, rtx *, rtx, rtx));
334 static void update_giv_derive PROTO((rtx));
335 static int basic_induction_var PROTO((rtx, enum machine_mode, rtx, rtx, rtx *, rtx *));
336 static rtx simplify_giv_expr PROTO((rtx, int *));
337 static int general_induction_var PROTO((rtx, rtx *, rtx *, rtx *, int, int *));
338 static int consec_sets_giv PROTO((int, rtx, rtx, rtx, rtx *, rtx *));
339 static int check_dbra_loop PROTO((rtx, int, rtx));
340 static rtx express_from_1 PROTO((rtx, rtx, rtx));
341 static rtx express_from PROTO((struct induction *, struct induction *));
342 static rtx combine_givs_p PROTO((struct induction *, struct induction *));
343 static void combine_givs PROTO((struct iv_class *));
344 static int product_cheap_p PROTO((rtx, rtx));
345 static int maybe_eliminate_biv PROTO((struct iv_class *, rtx, rtx, int, int, int));
346 static int maybe_eliminate_biv_1 PROTO((rtx, rtx, struct iv_class *, int, rtx));
347 static int last_use_this_basic_block PROTO((rtx, rtx));
348 static void record_initial PROTO((rtx, rtx));
349 static void update_reg_last_use PROTO((rtx, rtx));
350 static rtx next_insn_in_loop PROTO((rtx, rtx, rtx, rtx));
351 static void load_mems_and_recount_loop_regs_set PROTO((rtx, rtx, rtx,
354 static void load_mems PROTO((rtx, rtx, rtx, rtx));
355 static int insert_loop_mem PROTO((rtx *, void *));
356 static int replace_loop_mem PROTO((rtx *, void *));
357 static int replace_label PROTO((rtx *, void *));
359 typedef struct rtx_and_int {
364 typedef struct rtx_pair {
369 /* Nonzero iff INSN is between START and END, inclusive. */
370 #define INSN_IN_RANGE_P(INSN, START, END) \
371 (INSN_UID (INSN) < max_uid_for_loop \
372 && INSN_LUID (INSN) >= INSN_LUID (START) \
373 && INSN_LUID (INSN) <= INSN_LUID (END))
376 /* This is extern from unroll.c */
377 extern void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
379 /* Two main functions for implementing bct:
380 first - to be called before loop unrolling, and the second - after */
381 #ifdef HAVE_decrement_and_branch_on_count
382 static void analyze_loop_iterations PROTO((rtx, rtx));
383 static void insert_bct PROTO((rtx, rtx));
385 /* Auxiliary function that inserts the bct pattern into the loop */
386 static void instrument_loop_bct PROTO((rtx, rtx, rtx));
387 #endif /* HAVE_decrement_and_branch_on_count */
390 /* Indirect_jump_in_function is computed once per function. */
391 int indirect_jump_in_function = 0;
392 static int indirect_jump_in_function_p PROTO((rtx));
395 /* Relative gain of eliminating various kinds of operations. */
398 static int shift_cost;
399 static int mult_cost;
402 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
403 copy the value of the strength reduced giv to its original register. */
404 static int copy_cost;
406 /* Cost of using a register, to normalize the benefits of a giv. */
407 static int reg_address_cost;
413 char *free_point = (char *) oballoc (1);
414 rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
416 add_cost = rtx_cost (gen_rtx_PLUS (word_mode, reg, reg), SET);
419 reg_address_cost = ADDRESS_COST (reg);
421 reg_address_cost = rtx_cost (reg, MEM);
424 /* We multiply by 2 to reconcile the difference in scale between
425 these two ways of computing costs. Otherwise the cost of a copy
426 will be far less than the cost of an add. */
430 /* Free the objects we just allocated. */
433 /* Initialize the obstack used for rtl in product_cheap_p. */
434 gcc_obstack_init (&temp_obstack);
437 /* Entry point of this file. Perform loop optimization
438 on the current function. F is the first insn of the function
439 and DUMPFILE is a stream for output of a trace of actions taken
440 (or 0 if none should be output). */
443 loop_optimize (f, dumpfile, unroll_p, bct_p)
444 /* f is the first instruction of a chain of insns for one function */
453 loop_dump_stream = dumpfile;
455 init_recog_no_volatile ();
457 max_reg_before_loop = max_reg_num ();
459 moved_once = (char *) alloca (max_reg_before_loop);
460 bzero (moved_once, max_reg_before_loop);
464 /* Count the number of loops. */
467 for (insn = f; insn; insn = NEXT_INSN (insn))
469 if (GET_CODE (insn) == NOTE
470 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
474 /* Don't waste time if no loops. */
475 if (max_loop_num == 0)
478 /* Get size to use for tables indexed by uids.
479 Leave some space for labels allocated by find_and_verify_loops. */
480 max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
482 uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int));
483 uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int));
485 bzero ((char *) uid_luid, max_uid_for_loop * sizeof (int));
486 bzero ((char *) uid_loop_num, max_uid_for_loop * sizeof (int));
488 /* Allocate tables for recording each loop. We set each entry, so they need
490 loop_number_loop_starts = (rtx *) alloca (max_loop_num * sizeof (rtx));
491 loop_number_loop_ends = (rtx *) alloca (max_loop_num * sizeof (rtx));
492 loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
493 loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
494 loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
495 loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));
497 /* This is initialized by the unrolling code, so we go ahead
498 and clear them just in case we are not performing loop
500 loop_unroll_factor = (int *) alloca (max_loop_num *sizeof (int));
501 bzero ((char *) loop_unroll_factor, max_loop_num * sizeof (int));
504 /* Allocate for BCT optimization */
505 loop_can_insert_bct = (int *) alloca (max_loop_num * sizeof (int));
506 bzero ((char *) loop_can_insert_bct, max_loop_num * sizeof (int));
508 loop_used_count_register = (int *) alloca (max_loop_num * sizeof (int));
509 bzero ((char *) loop_used_count_register, max_loop_num * sizeof (int));
511 loop_increment = (rtx *) alloca (max_loop_num * sizeof (rtx));
512 loop_comparison_value = (rtx *) alloca (max_loop_num * sizeof (rtx));
513 loop_start_value = (rtx *) alloca (max_loop_num * sizeof (rtx));
514 bzero ((char *) loop_increment, max_loop_num * sizeof (rtx));
515 bzero ((char *) loop_comparison_value, max_loop_num * sizeof (rtx));
516 bzero ((char *) loop_start_value, max_loop_num * sizeof (rtx));
519 = (enum rtx_code *) alloca (max_loop_num * sizeof (enum rtx_code));
520 bzero ((char *) loop_comparison_code, max_loop_num * sizeof (enum rtx_code));
523 /* Find and process each loop.
524 First, find them, and record them in order of their beginnings. */
525 find_and_verify_loops (f);
527 /* Now find all register lifetimes. This must be done after
528 find_and_verify_loops, because it might reorder the insns in the
530 reg_scan (f, max_reg_num (), 1);
532 /* This must occur after reg_scan so that registers created by gcse
533 will have entries in the register tables.
535 We could have added a call to reg_scan after gcse_main in toplev.c,
536 but moving this call to init_alias_analysis is more efficient. */
537 init_alias_analysis ();
539 /* See if we went too far. */
540 if (get_max_uid () > max_uid_for_loop)
542 /* Now reset it to the actual size we need. See above. */
543 max_uid_for_loop = get_max_uid () + 1;
545 /* Compute the mapping from uids to luids.
546 LUIDs are numbers assigned to insns, like uids,
547 except that luids increase monotonically through the code.
548 Don't assign luids to line-number NOTEs, so that the distance in luids
549 between two insns is not affected by -g. */
551 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
554 if (GET_CODE (insn) != NOTE
555 || NOTE_LINE_NUMBER (insn) <= 0)
556 uid_luid[INSN_UID (insn)] = ++i;
558 /* Give a line number note the same luid as preceding insn. */
559 uid_luid[INSN_UID (insn)] = i;
564 /* Don't leave gaps in uid_luid for insns that have been
565 deleted. It is possible that the first or last insn
566 using some register has been deleted by cross-jumping.
567 Make sure that uid_luid for that former insn's uid
568 points to the general area where that insn used to be. */
569 for (i = 0; i < max_uid_for_loop; i++)
571 uid_luid[0] = uid_luid[i];
572 if (uid_luid[0] != 0)
575 for (i = 0; i < max_uid_for_loop; i++)
576 if (uid_luid[i] == 0)
577 uid_luid[i] = uid_luid[i - 1];
579 /* Create a mapping from loops to BLOCK tree nodes. */
580 if (unroll_p && write_symbols != NO_DEBUG)
581 find_loop_tree_blocks ();
583 /* Determine if the function has indirect jump. On some systems
584 this prevents low overhead loop instructions from being used. */
585 indirect_jump_in_function = indirect_jump_in_function_p (f);
587 /* Now scan the loops, last ones first, since this means inner ones are done
588 before outer ones. */
589 for (i = max_loop_num-1; i >= 0; i--)
590 if (! loop_invalid[i] && loop_number_loop_ends[i])
591 scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i],
594 /* If debugging and unrolling loops, we must replicate the tree nodes
595 corresponding to the blocks inside the loop, so that the original one
596 to one mapping will remain. */
597 if (unroll_p && write_symbols != NO_DEBUG)
598 unroll_block_trees ();
600 end_alias_analysis ();
603 /* Returns the next insn, in execution order, after INSN. START and
604 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
605 respectively. LOOP_TOP, if non-NULL, is the top of the loop in the
606 insn-stream; it is used with loops that are entered near the
610 next_insn_in_loop (insn, start, end, loop_top)
616 insn = NEXT_INSN (insn);
621 /* Go to the top of the loop, and continue there. */
635 /* Optimize one loop whose start is LOOP_START and end is END.
636 LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
637 NOTE_INSN_LOOP_END. */
639 /* ??? Could also move memory writes out of loops if the destination address
640 is invariant, the source is invariant, the memory write is not volatile,
641 and if we can prove that no read inside the loop can read this address
642 before the write occurs. If there is a read of this address after the
643 write, then we can also mark the memory read as invariant. */
646 scan_loop (loop_start, end, unroll_p, bct_p)
652 /* 1 if we are scanning insns that could be executed zero times. */
654 /* 1 if we are scanning insns that might never be executed
655 due to a subroutine call which might exit before they are reached. */
657 /* For a rotated loop that is entered near the bottom,
658 this is the label at the top. Otherwise it is zero. */
660 /* Jump insn that enters the loop, or 0 if control drops in. */
661 rtx loop_entry_jump = 0;
662 /* Place in the loop where control enters. */
664 /* Number of insns in the loop. */
669 /* The SET from an insn, if it is the only SET in the insn. */
671 /* Chain describing insns movable in current loop. */
672 struct movable *movables = 0;
673 /* Last element in `movables' -- so we can add elements at the end. */
674 struct movable *last_movable = 0;
675 /* Ratio of extra register life span we can justify
676 for saving an instruction. More if loop doesn't call subroutines
677 since in that case saving an insn makes more difference
678 and more registers are available. */
680 /* If we have calls, contains the insn in which a register was used
681 if it was used exactly once; contains const0_rtx if it was used more
683 varray_type reg_single_usage = 0;
684 /* Nonzero if we are scanning instructions in a sub-loop. */
688 /* Determine whether this loop starts with a jump down to a test at
689 the end. This will occur for a small number of loops with a test
690 that is too complex to duplicate in front of the loop.
692 We search for the first insn or label in the loop, skipping NOTEs.
693 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
694 (because we might have a loop executed only once that contains a
695 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
696 (in case we have a degenerate loop).
698 Note that if we mistakenly think that a loop is entered at the top
699 when, in fact, it is entered at the exit test, the only effect will be
700 slightly poorer optimization. Making the opposite error can generate
701 incorrect code. Since very few loops now start with a jump to the
702 exit test, the code here to detect that case is very conservative. */
704 for (p = NEXT_INSN (loop_start);
706 && GET_CODE (p) != CODE_LABEL && GET_RTX_CLASS (GET_CODE (p)) != 'i'
707 && (GET_CODE (p) != NOTE
708 || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
709 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
715 /* Set up variables describing this loop. */
716 prescan_loop (loop_start, end);
717 threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);
719 /* If loop has a jump before the first label,
720 the true entry is the target of that jump.
721 Start scan from there.
722 But record in LOOP_TOP the place where the end-test jumps
723 back to so we can scan that after the end of the loop. */
724 if (GET_CODE (p) == JUMP_INSN)
728 /* Loop entry must be unconditional jump (and not a RETURN) */
730 && JUMP_LABEL (p) != 0
731 /* Check to see whether the jump actually
732 jumps out of the loop (meaning it's no loop).
733 This case can happen for things like
734 do {..} while (0). If this label was generated previously
735 by loop, we can't tell anything about it and have to reject
737 && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, end))
739 loop_top = next_label (scan_start);
740 scan_start = JUMP_LABEL (p);
744 /* If SCAN_START was an insn created by loop, we don't know its luid
745 as required by loop_reg_used_before_p. So skip such loops. (This
746 test may never be true, but it's best to play it safe.)
748 Also, skip loops where we do not start scanning at a label. This
749 test also rejects loops starting with a JUMP_INSN that failed the
752 if (INSN_UID (scan_start) >= max_uid_for_loop
753 || GET_CODE (scan_start) != CODE_LABEL)
755 if (loop_dump_stream)
756 fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
757 INSN_UID (loop_start), INSN_UID (end));
761 /* Count number of times each reg is set during this loop.
762 Set VARRAY_CHAR (may_not_optimize, I) if it is not safe to move out
763 the setting of register I. If this loop has calls, set
764 VARRAY_RTX (reg_single_usage, I). */
766 /* Allocate extra space for REGS that might be created by
767 load_mems. We allocate a little extra slop as well, in the hopes
768 that even after the moving of movables creates some new registers
769 we won't have to reallocate these arrays. However, we do grow
770 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
771 nregs = max_reg_num () + loop_mems_idx + 16;
772 VARRAY_INT_INIT (n_times_set, nregs, "n_times_set");
773 VARRAY_INT_INIT (n_times_used, nregs, "n_times_used");
774 VARRAY_CHAR_INIT (may_not_optimize, nregs, "may_not_optimize");
777 VARRAY_RTX_INIT (reg_single_usage, nregs, "reg_single_usage");
779 count_loop_regs_set (loop_top ? loop_top : loop_start, end,
780 may_not_optimize, reg_single_usage, &insn_count, nregs);
782 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
784 VARRAY_CHAR (may_not_optimize, i) = 1;
785 VARRAY_INT (n_times_set, i) = 1;
788 #ifdef AVOID_CCMODE_COPIES
789 /* Don't try to move insns which set CC registers if we should not
790 create CCmode register copies. */
791 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
792 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
793 VARRAY_CHAR (may_not_optimize, i) = 1;
796 bcopy ((char *) &n_times_set->data,
797 (char *) &n_times_used->data, nregs * sizeof (int));
799 if (loop_dump_stream)
801 fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
802 INSN_UID (loop_start), INSN_UID (end), insn_count);
804 fprintf (loop_dump_stream, "Continue at insn %d.\n",
805 INSN_UID (loop_continue));
808 /* Scan through the loop finding insns that are safe to move.
809 Set n_times_set negative for the reg being set, so that
810 this reg will be considered invariant for subsequent insns.
811 We consider whether subsequent insns use the reg
812 in deciding whether it is worth actually moving.
814 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
815 and therefore it is possible that the insns we are scanning
816 would never be executed. At such times, we must make sure
817 that it is safe to execute the insn once instead of zero times.
818 When MAYBE_NEVER is 0, all insns will be executed at least once
819 so that is not a problem. */
821 for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
823 p = next_insn_in_loop (p, scan_start, end, loop_top))
825 if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
826 && find_reg_note (p, REG_LIBCALL, NULL_RTX))
828 else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
829 && find_reg_note (p, REG_RETVAL, NULL_RTX))
832 if (GET_CODE (p) == INSN
833 && (set = single_set (p))
834 && GET_CODE (SET_DEST (set)) == REG
835 && ! VARRAY_CHAR (may_not_optimize, REGNO (SET_DEST (set))))
840 rtx src = SET_SRC (set);
841 rtx dependencies = 0;
843 /* Figure out what to use as a source of this insn. If a REG_EQUIV
844 note is given or if a REG_EQUAL note with a constant operand is
845 specified, use it as the source and mark that we should move
846 this insn by calling emit_move_insn rather that duplicating the
849 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
851 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
853 src = XEXP (temp, 0), move_insn = 1;
856 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
857 if (temp && CONSTANT_P (XEXP (temp, 0)))
858 src = XEXP (temp, 0), move_insn = 1;
859 if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
861 src = XEXP (temp, 0);
862 /* A libcall block can use regs that don't appear in
863 the equivalent expression. To move the libcall,
864 we must move those regs too. */
865 dependencies = libcall_other_reg (p, src);
869 /* Don't try to optimize a register that was made
870 by loop-optimization for an inner loop.
871 We don't know its life-span, so we can't compute the benefit. */
872 if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
874 else if (/* The set is a user-variable or it is used in
875 the exit test (this can cause the variable to be
876 used before it is set just like a
878 (REG_USERVAR_P (SET_DEST (set))
879 || REG_LOOP_TEST_P (SET_DEST (set)))
880 /* And the set is not guaranteed to be executed one
881 the loop starts, or the value before the set is
882 needed before the set occurs... */
884 || loop_reg_used_before_p (set, p, loop_start,
886 /* And the register is used in basic blocks other
887 than the one where it is set (meaning that
888 something after this point in the loop might
889 depend on its value before the set). */
890 && !reg_in_basic_block_p (p, SET_DEST (set)))
891 /* It is unsafe to move the set. The fact that these
892 three conditions are considered in conjunction means
893 that we are assuming various conditions, such as:
895 o It's OK to move a set of a variable which was not
896 created by the user and is not used in an exit test
897 even if that point in the set would not be reached
898 during execution of the loop. */
900 else if ((tem = invariant_p (src))
901 && (dependencies == 0
902 || (tem2 = invariant_p (dependencies)) != 0)
903 && (VARRAY_INT (n_times_set,
904 REGNO (SET_DEST (set))) == 1
906 = consec_sets_invariant_p
908 VARRAY_INT (n_times_set, REGNO (SET_DEST (set))),
910 /* If the insn can cause a trap (such as divide by zero),
911 can't move it unless it's guaranteed to be executed
912 once loop is entered. Even a function call might
913 prevent the trap insn from being reached
914 (since it might exit!) */
915 && ! ((maybe_never || call_passed)
916 && may_trap_p (src)))
918 register struct movable *m;
919 register int regno = REGNO (SET_DEST (set));
921 /* A potential lossage is where we have a case where two insns
922 can be combined as long as they are both in the loop, but
923 we move one of them outside the loop. For large loops,
924 this can lose. The most common case of this is the address
925 of a function being called.
927 Therefore, if this register is marked as being used exactly
928 once if we are in a loop with calls (a "large loop"), see if
929 we can replace the usage of this register with the source
930 of this SET. If we can, delete this insn.
932 Don't do this if P has a REG_RETVAL note or if we have
933 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
935 if (reg_single_usage && VARRAY_RTX (reg_single_usage, regno) != 0
936 && VARRAY_RTX (reg_single_usage, regno) != const0_rtx
937 && REGNO_FIRST_UID (regno) == INSN_UID (p)
938 && (REGNO_LAST_UID (regno)
939 == INSN_UID (VARRAY_RTX (reg_single_usage, regno)))
940 && VARRAY_INT (n_times_set, regno) == 1
941 && ! side_effects_p (SET_SRC (set))
942 && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
943 && (! SMALL_REGISTER_CLASSES
944 || (! (GET_CODE (SET_SRC (set)) == REG
945 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
946 /* This test is not redundant; SET_SRC (set) might be
947 a call-clobbered register and the life of REGNO
948 might span a call. */
949 && ! modified_between_p (SET_SRC (set), p,
951 (reg_single_usage, regno))
952 && no_labels_between_p (p, VARRAY_RTX (reg_single_usage, regno))
953 && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
955 (reg_single_usage, regno)))
957 /* Replace any usage in a REG_EQUAL note. Must copy the
958 new source, so that we don't get rtx sharing between the
959 SET_SOURCE and REG_NOTES of insn p. */
960 REG_NOTES (VARRAY_RTX (reg_single_usage, regno))
961 = replace_rtx (REG_NOTES (VARRAY_RTX
962 (reg_single_usage, regno)),
963 SET_DEST (set), copy_rtx (SET_SRC (set)));
966 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
967 NOTE_SOURCE_FILE (p) = 0;
968 VARRAY_INT (n_times_set, regno) = 0;
972 m = (struct movable *) alloca (sizeof (struct movable));
976 m->dependencies = dependencies;
977 m->set_dest = SET_DEST (set);
979 m->consec = VARRAY_INT (n_times_set,
980 REGNO (SET_DEST (set))) - 1;
984 m->move_insn = move_insn;
985 m->move_insn_first = 0;
986 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
987 m->savemode = VOIDmode;
989 /* Set M->cond if either invariant_p or consec_sets_invariant_p
990 returned 2 (only conditionally invariant). */
991 m->cond = ((tem | tem1 | tem2) > 1);
992 m->global = (uid_luid[REGNO_LAST_UID (regno)] > INSN_LUID (end)
993 || uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
995 m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
996 - uid_luid[REGNO_FIRST_UID (regno)]);
997 m->savings = VARRAY_INT (n_times_used, regno);
998 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
999 m->savings += libcall_benefit (p);
1000 VARRAY_INT (n_times_set, regno) = move_insn ? -2 : -1;
1001 /* Add M to the end of the chain MOVABLES. */
1005 last_movable->next = m;
1010 /* It is possible for the first instruction to have a
1011 REG_EQUAL note but a non-invariant SET_SRC, so we must
1012 remember the status of the first instruction in case
1013 the last instruction doesn't have a REG_EQUAL note. */
1014 m->move_insn_first = m->move_insn;
1016 /* Skip this insn, not checking REG_LIBCALL notes. */
1017 p = next_nonnote_insn (p);
1018 /* Skip the consecutive insns, if there are any. */
1019 p = skip_consec_insns (p, m->consec);
1020 /* Back up to the last insn of the consecutive group. */
1021 p = prev_nonnote_insn (p);
1023 /* We must now reset m->move_insn, m->is_equiv, and possibly
1024 m->set_src to correspond to the effects of all the
1026 temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
1028 m->set_src = XEXP (temp, 0), m->move_insn = 1;
1031 temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
1032 if (temp && CONSTANT_P (XEXP (temp, 0)))
1033 m->set_src = XEXP (temp, 0), m->move_insn = 1;
1038 m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
1041 /* If this register is always set within a STRICT_LOW_PART
1042 or set to zero, then its high bytes are constant.
1043 So clear them outside the loop and within the loop
1044 just load the low bytes.
1045 We must check that the machine has an instruction to do so.
1046 Also, if the value loaded into the register
1047 depends on the same register, this cannot be done. */
1048 else if (SET_SRC (set) == const0_rtx
1049 && GET_CODE (NEXT_INSN (p)) == INSN
1050 && (set1 = single_set (NEXT_INSN (p)))
1051 && GET_CODE (set1) == SET
1052 && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
1053 && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
1054 && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
1056 && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
1058 register int regno = REGNO (SET_DEST (set));
1059 if (VARRAY_INT (n_times_set, regno) == 2)
1061 register struct movable *m;
1062 m = (struct movable *) alloca (sizeof (struct movable));
1065 m->set_dest = SET_DEST (set);
1066 m->dependencies = 0;
1072 m->move_insn_first = 0;
1074 /* If the insn may not be executed on some cycles,
1075 we can't clear the whole reg; clear just high part.
1076 Not even if the reg is used only within this loop.
1083 Clearing x before the inner loop could clobber a value
1084 being saved from the last time around the outer loop.
1085 However, if the reg is not used outside this loop
1086 and all uses of the register are in the same
1087 basic block as the store, there is no problem.
1089 If this insn was made by loop, we don't know its
1090 INSN_LUID and hence must make a conservative
1092 m->global = (INSN_UID (p) >= max_uid_for_loop
1093 || (uid_luid[REGNO_LAST_UID (regno)]
1095 || (uid_luid[REGNO_FIRST_UID (regno)]
1097 || (labels_in_range_p
1098 (p, uid_luid[REGNO_FIRST_UID (regno)])));
1099 if (maybe_never && m->global)
1100 m->savemode = GET_MODE (SET_SRC (set1));
1102 m->savemode = VOIDmode;
1106 m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
1107 - uid_luid[REGNO_FIRST_UID (regno)]);
1109 VARRAY_INT (n_times_set, regno) = -1;
1110 /* Add M to the end of the chain MOVABLES. */
1114 last_movable->next = m;
1119 /* Past a call insn, we get to insns which might not be executed
1120 because the call might exit. This matters for insns that trap.
1121 Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
1122 so they don't count. */
1123 else if (GET_CODE (p) == CALL_INSN && ! in_libcall)
1125 /* Past a label or a jump, we get to insns for which we
1126 can't count on whether or how many times they will be
1127 executed during each iteration. Therefore, we can
1128 only move out sets of trivial variables
1129 (those not used after the loop). */
1130 /* Similar code appears twice in strength_reduce. */
1131 else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
1132 /* If we enter the loop in the middle, and scan around to the
1133 beginning, don't set maybe_never for that. This must be an
1134 unconditional jump, otherwise the code at the top of the
1135 loop might never be executed. Unconditional jumps are
1136 followed a by barrier then loop end. */
1137 && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
1138 && NEXT_INSN (NEXT_INSN (p)) == end
1139 && simplejump_p (p)))
1141 else if (GET_CODE (p) == NOTE)
1143 /* At the virtual top of a converted loop, insns are again known to
1144 be executed: logically, the loop begins here even though the exit
1145 code has been duplicated. */
1146 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
1147 maybe_never = call_passed = 0;
1148 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
1150 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
1155 /* If one movable subsumes another, ignore that other. */
1157 ignore_some_movables (movables);
1159 /* For each movable insn, see if the reg that it loads
1160 leads when it dies right into another conditionally movable insn.
1161 If so, record that the second insn "forces" the first one,
1162 since the second can be moved only if the first is. */
1164 force_movables (movables);
1166 /* See if there are multiple movable insns that load the same value.
1167 If there are, make all but the first point at the first one
1168 through the `match' field, and add the priorities of them
1169 all together as the priority of the first. */
1171 combine_movables (movables, nregs);
1173 /* Now consider each movable insn to decide whether it is worth moving.
1174 Store 0 in n_times_set for each reg that is moved.
1176 Generally this increases code size, so do not move moveables when
1177 optimizing for code size. */
1179 if (! optimize_size)
1180 move_movables (movables, threshold,
1181 insn_count, loop_start, end, nregs);
1183 /* Now candidates that still are negative are those not moved.
1184 Change n_times_set to indicate that those are not actually invariant. */
1185 for (i = 0; i < nregs; i++)
1186 if (VARRAY_INT (n_times_set, i) < 0)
1187 VARRAY_INT (n_times_set, i) = VARRAY_INT (n_times_used, i);
1189 /* Now that we've moved some things out of the loop, we able to
1190 hoist even more memory references. There's no need to pass
1191 reg_single_usage this time, since we're done with it. */
1192 load_mems_and_recount_loop_regs_set (scan_start, end, loop_top,
1196 if (flag_strength_reduce)
1198 the_movables = movables;
1199 strength_reduce (scan_start, end, loop_top,
1200 insn_count, loop_start, end, unroll_p, bct_p);
1203 VARRAY_FREE (n_times_set);
1204 VARRAY_FREE (n_times_used);
1205 VARRAY_FREE (may_not_optimize);
1206 VARRAY_FREE (reg_single_usage);
1209 /* Add elements to *OUTPUT to record all the pseudo-regs
1210 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1213 record_excess_regs (in_this, not_in_this, output)
1214 rtx in_this, not_in_this;
1221 code = GET_CODE (in_this);
1235 if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1236 && ! reg_mentioned_p (in_this, not_in_this))
1237 *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1244 fmt = GET_RTX_FORMAT (code);
1245 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1252 for (j = 0; j < XVECLEN (in_this, i); j++)
1253 record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1257 record_excess_regs (XEXP (in_this, i), not_in_this, output);
1263 /* Check what regs are referred to in the libcall block ending with INSN,
1264 aside from those mentioned in the equivalent value.
1265 If there are none, return 0.
1266 If there are one or more, return an EXPR_LIST containing all of them. */
1269 libcall_other_reg (insn, equiv)
1272 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1273 rtx p = XEXP (note, 0);
1276 /* First, find all the regs used in the libcall block
1277 that are not mentioned as inputs to the result. */
1281 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1282 || GET_CODE (p) == CALL_INSN)
1283 record_excess_regs (PATTERN (p), equiv, &output);
1290 /* Return 1 if all uses of REG
1291 are between INSN and the end of the basic block. */
1294 reg_in_basic_block_p (insn, reg)
1297 int regno = REGNO (reg);
1300 if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1303 /* Search this basic block for the already recorded last use of the reg. */
1304 for (p = insn; p; p = NEXT_INSN (p))
1306 switch (GET_CODE (p))
1313 /* Ordinary insn: if this is the last use, we win. */
1314 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1319 /* Jump insn: if this is the last use, we win. */
1320 if (REGNO_LAST_UID (regno) == INSN_UID (p))
1322 /* Otherwise, it's the end of the basic block, so we lose. */
1327 /* It's the end of the basic block, so we lose. */
1335 /* The "last use" doesn't follow the "first use"?? */
1339 /* Compute the benefit of eliminating the insns in the block whose
1340 last insn is LAST. This may be a group of insns used to compute a
1341 value directly or can contain a library call. */
1344 libcall_benefit (last)
1350 for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1351 insn != last; insn = NEXT_INSN (insn))
1353 if (GET_CODE (insn) == CALL_INSN)
1354 benefit += 10; /* Assume at least this many insns in a library
1356 else if (GET_CODE (insn) == INSN
1357 && GET_CODE (PATTERN (insn)) != USE
1358 && GET_CODE (PATTERN (insn)) != CLOBBER)
1365 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1368 skip_consec_insns (insn, count)
1372 for (; count > 0; count--)
1376 /* If first insn of libcall sequence, skip to end. */
1377 /* Do this at start of loop, since INSN is guaranteed to
1379 if (GET_CODE (insn) != NOTE
1380 && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1381 insn = XEXP (temp, 0);
1383 do insn = NEXT_INSN (insn);
1384 while (GET_CODE (insn) == NOTE);
1390 /* Ignore any movable whose insn falls within a libcall
1391 which is part of another movable.
1392 We make use of the fact that the movable for the libcall value
1393 was made later and so appears later on the chain. */
1396 ignore_some_movables (movables)
1397 struct movable *movables;
1399 register struct movable *m, *m1;
1401 for (m = movables; m; m = m->next)
1403 /* Is this a movable for the value of a libcall? */
1404 rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1408 /* Check for earlier movables inside that range,
1409 and mark them invalid. We cannot use LUIDs here because
1410 insns created by loop.c for prior loops don't have LUIDs.
1411 Rather than reject all such insns from movables, we just
1412 explicitly check each insn in the libcall (since invariant
1413 libcalls aren't that common). */
1414 for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1415 for (m1 = movables; m1 != m; m1 = m1->next)
1416 if (m1->insn == insn)
1422 /* For each movable insn, see if the reg that it loads
1423 leads when it dies right into another conditionally movable insn.
1424 If so, record that the second insn "forces" the first one,
1425 since the second can be moved only if the first is. */
1428 force_movables (movables)
1429 struct movable *movables;
1431 register struct movable *m, *m1;
1432 for (m1 = movables; m1; m1 = m1->next)
1433 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1434 if (!m1->partial && !m1->done)
1436 int regno = m1->regno;
1437 for (m = m1->next; m; m = m->next)
1438 /* ??? Could this be a bug? What if CSE caused the
1439 register of M1 to be used after this insn?
1440 Since CSE does not update regno_last_uid,
1441 this insn M->insn might not be where it dies.
1442 But very likely this doesn't matter; what matters is
1443 that M's reg is computed from M1's reg. */
1444 if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1447 if (m != 0 && m->set_src == m1->set_dest
1448 /* If m->consec, m->set_src isn't valid. */
1452 /* Increase the priority of the moving the first insn
1453 since it permits the second to be moved as well. */
1457 m1->lifetime += m->lifetime;
1458 m1->savings += m->savings;
1463 /* Find invariant expressions that are equal and can be combined into
1467 combine_movables (movables, nregs)
1468 struct movable *movables;
1471 register struct movable *m;
1472 char *matched_regs = (char *) alloca (nregs);
1473 enum machine_mode mode;
1475 /* Regs that are set more than once are not allowed to match
1476 or be matched. I'm no longer sure why not. */
1477 /* Perhaps testing m->consec_sets would be more appropriate here? */
1479 for (m = movables; m; m = m->next)
1480 if (m->match == 0 && VARRAY_INT (n_times_used, m->regno) == 1 && !m->partial)
1482 register struct movable *m1;
1483 int regno = m->regno;
1485 bzero (matched_regs, nregs);
1486 matched_regs[regno] = 1;
1488 /* We want later insns to match the first one. Don't make the first
1489 one match any later ones. So start this loop at m->next. */
1490 for (m1 = m->next; m1; m1 = m1->next)
1491 if (m != m1 && m1->match == 0 && VARRAY_INT (n_times_used, m1->regno) == 1
1492 /* A reg used outside the loop mustn't be eliminated. */
1494 /* A reg used for zero-extending mustn't be eliminated. */
1496 && (matched_regs[m1->regno]
1499 /* Can combine regs with different modes loaded from the
1500 same constant only if the modes are the same or
1501 if both are integer modes with M wider or the same
1502 width as M1. The check for integer is redundant, but
1503 safe, since the only case of differing destination
1504 modes with equal sources is when both sources are
1505 VOIDmode, i.e., CONST_INT. */
1506 (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1507 || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1508 && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1509 && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1510 >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1511 /* See if the source of M1 says it matches M. */
1512 && ((GET_CODE (m1->set_src) == REG
1513 && matched_regs[REGNO (m1->set_src)])
1514 || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1516 && ((m->dependencies == m1->dependencies)
1517 || rtx_equal_p (m->dependencies, m1->dependencies)))
1519 m->lifetime += m1->lifetime;
1520 m->savings += m1->savings;
1523 matched_regs[m1->regno] = 1;
1527 /* Now combine the regs used for zero-extension.
1528 This can be done for those not marked `global'
1529 provided their lives don't overlap. */
1531 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1532 mode = GET_MODE_WIDER_MODE (mode))
1534 register struct movable *m0 = 0;
1536 /* Combine all the registers for extension from mode MODE.
1537 Don't combine any that are used outside this loop. */
1538 for (m = movables; m; m = m->next)
1539 if (m->partial && ! m->global
1540 && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1542 register struct movable *m1;
1543 int first = uid_luid[REGNO_FIRST_UID (m->regno)];
1544 int last = uid_luid[REGNO_LAST_UID (m->regno)];
1548 /* First one: don't check for overlap, just record it. */
1553 /* Make sure they extend to the same mode.
1554 (Almost always true.) */
1555 if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1558 /* We already have one: check for overlap with those
1559 already combined together. */
1560 for (m1 = movables; m1 != m; m1 = m1->next)
1561 if (m1 == m0 || (m1->partial && m1->match == m0))
1562 if (! (uid_luid[REGNO_FIRST_UID (m1->regno)] > last
1563 || uid_luid[REGNO_LAST_UID (m1->regno)] < first))
1566 /* No overlap: we can combine this with the others. */
1567 m0->lifetime += m->lifetime;
1568 m0->savings += m->savings;
1577 /* Return 1 if regs X and Y will become the same if moved. */
1580 regs_match_p (x, y, movables)
1582 struct movable *movables;
1586 struct movable *mx, *my;
1588 for (mx = movables; mx; mx = mx->next)
1589 if (mx->regno == xn)
1592 for (my = movables; my; my = my->next)
1593 if (my->regno == yn)
1597 && ((mx->match == my->match && mx->match != 0)
1599 || mx == my->match));
1602 /* Return 1 if X and Y are identical-looking rtx's.
1603 This is the Lisp function EQUAL for rtx arguments.
1605 If two registers are matching movables or a movable register and an
1606 equivalent constant, consider them equal. */
1609 rtx_equal_for_loop_p (x, y, movables)
1611 struct movable *movables;
1615 register struct movable *m;
1616 register enum rtx_code code;
1621 if (x == 0 || y == 0)
1624 code = GET_CODE (x);
1626 /* If we have a register and a constant, they may sometimes be
1628 if (GET_CODE (x) == REG && VARRAY_INT (n_times_set, REGNO (x)) == -2
1631 for (m = movables; m; m = m->next)
1632 if (m->move_insn && m->regno == REGNO (x)
1633 && rtx_equal_p (m->set_src, y))
1636 else if (GET_CODE (y) == REG && VARRAY_INT (n_times_set, REGNO (y)) == -2
1639 for (m = movables; m; m = m->next)
1640 if (m->move_insn && m->regno == REGNO (y)
1641 && rtx_equal_p (m->set_src, x))
1645 /* Otherwise, rtx's of different codes cannot be equal. */
1646 if (code != GET_CODE (y))
1649 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1650 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1652 if (GET_MODE (x) != GET_MODE (y))
1655 /* These three types of rtx's can be compared nonrecursively. */
1657 return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1659 if (code == LABEL_REF)
1660 return XEXP (x, 0) == XEXP (y, 0);
1661 if (code == SYMBOL_REF)
1662 return XSTR (x, 0) == XSTR (y, 0);
1664 /* Compare the elements. If any pair of corresponding elements
1665 fail to match, return 0 for the whole things. */
1667 fmt = GET_RTX_FORMAT (code);
1668 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1673 if (XWINT (x, i) != XWINT (y, i))
1678 if (XINT (x, i) != XINT (y, i))
1683 /* Two vectors must have the same length. */
1684 if (XVECLEN (x, i) != XVECLEN (y, i))
1687 /* And the corresponding elements must match. */
1688 for (j = 0; j < XVECLEN (x, i); j++)
1689 if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0)
1694 if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0)
1699 if (strcmp (XSTR (x, i), XSTR (y, i)))
1704 /* These are just backpointers, so they don't matter. */
1710 /* It is believed that rtx's at this level will never
1711 contain anything but integers and other rtx's,
1712 except for within LABEL_REFs and SYMBOL_REFs. */
1720 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1721 insns in INSNS which use thet reference. */
1724 add_label_notes (x, insns)
1728 enum rtx_code code = GET_CODE (x);
1733 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1735 /* This code used to ignore labels that referred to dispatch tables to
1736 avoid flow generating (slighly) worse code.
1738 We no longer ignore such label references (see LABEL_REF handling in
1739 mark_jump_label for additional information). */
1740 for (insn = insns; insn; insn = NEXT_INSN (insn))
1741 if (reg_mentioned_p (XEXP (x, 0), insn))
1742 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
1746 fmt = GET_RTX_FORMAT (code);
1747 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1750 add_label_notes (XEXP (x, i), insns);
1751 else if (fmt[i] == 'E')
1752 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1753 add_label_notes (XVECEXP (x, i, j), insns);
1757 /* Scan MOVABLES, and move the insns that deserve to be moved.
1758 If two matching movables are combined, replace one reg with the
1759 other throughout. */
1762 move_movables (movables, threshold, insn_count, loop_start, end, nregs)
1763 struct movable *movables;
1771 register struct movable *m;
1773 /* Map of pseudo-register replacements to handle combining
1774 when we move several insns that load the same value
1775 into different pseudo-registers. */
1776 rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
1777 char *already_moved = (char *) alloca (nregs);
1779 bzero (already_moved, nregs);
1780 bzero ((char *) reg_map, nregs * sizeof (rtx));
1784 for (m = movables; m; m = m->next)
1786 /* Describe this movable insn. */
1788 if (loop_dump_stream)
1790 fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1791 INSN_UID (m->insn), m->regno, m->lifetime);
1793 fprintf (loop_dump_stream, "consec %d, ", m->consec);
1795 fprintf (loop_dump_stream, "cond ");
1797 fprintf (loop_dump_stream, "force ");
1799 fprintf (loop_dump_stream, "global ");
1801 fprintf (loop_dump_stream, "done ");
1803 fprintf (loop_dump_stream, "move-insn ");
1805 fprintf (loop_dump_stream, "matches %d ",
1806 INSN_UID (m->match->insn));
1808 fprintf (loop_dump_stream, "forces %d ",
1809 INSN_UID (m->forces->insn));
1812 /* Count movables. Value used in heuristics in strength_reduce. */
1815 /* Ignore the insn if it's already done (it matched something else).
1816 Otherwise, see if it is now safe to move. */
1820 || (1 == invariant_p (m->set_src)
1821 && (m->dependencies == 0
1822 || 1 == invariant_p (m->dependencies))
1824 || 1 == consec_sets_invariant_p (m->set_dest,
1827 && (! m->forces || m->forces->done))
1831 int savings = m->savings;
1833 /* We have an insn that is safe to move.
1834 Compute its desirability. */
1839 if (loop_dump_stream)
1840 fprintf (loop_dump_stream, "savings %d ", savings);
1842 if (moved_once[regno] && loop_dump_stream)
1843 fprintf (loop_dump_stream, "halved since already moved ");
1845 /* An insn MUST be moved if we already moved something else
1846 which is safe only if this one is moved too: that is,
1847 if already_moved[REGNO] is nonzero. */
1849 /* An insn is desirable to move if the new lifetime of the
1850 register is no more than THRESHOLD times the old lifetime.
1851 If it's not desirable, it means the loop is so big
1852 that moving won't speed things up much,
1853 and it is liable to make register usage worse. */
1855 /* It is also desirable to move if it can be moved at no
1856 extra cost because something else was already moved. */
1858 if (already_moved[regno]
1859 || flag_move_all_movables
1860 || (threshold * savings * m->lifetime) >=
1861 (moved_once[regno] ? insn_count * 2 : insn_count)
1862 || (m->forces && m->forces->done
1863 && VARRAY_INT (n_times_used, m->forces->regno) == 1))
1866 register struct movable *m1;
1869 /* Now move the insns that set the reg. */
1871 if (m->partial && m->match)
1875 /* Find the end of this chain of matching regs.
1876 Thus, we load each reg in the chain from that one reg.
1877 And that reg is loaded with 0 directly,
1878 since it has ->match == 0. */
1879 for (m1 = m; m1->match; m1 = m1->match);
1880 newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1881 SET_DEST (PATTERN (m1->insn)));
1882 i1 = emit_insn_before (newpat, loop_start);
1884 /* Mark the moved, invariant reg as being allowed to
1885 share a hard reg with the other matching invariant. */
1886 REG_NOTES (i1) = REG_NOTES (m->insn);
1887 r1 = SET_DEST (PATTERN (m->insn));
1888 r2 = SET_DEST (PATTERN (m1->insn));
1890 = gen_rtx_EXPR_LIST (VOIDmode, r1,
1891 gen_rtx_EXPR_LIST (VOIDmode, r2,
1893 delete_insn (m->insn);
1898 if (loop_dump_stream)
1899 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1901 /* If we are to re-generate the item being moved with a
1902 new move insn, first delete what we have and then emit
1903 the move insn before the loop. */
1904 else if (m->move_insn)
1908 for (count = m->consec; count >= 0; count--)
1910 /* If this is the first insn of a library call sequence,
1912 if (GET_CODE (p) != NOTE
1913 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1916 /* If this is the last insn of a libcall sequence, then
1917 delete every insn in the sequence except the last.
1918 The last insn is handled in the normal manner. */
1919 if (GET_CODE (p) != NOTE
1920 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1922 temp = XEXP (temp, 0);
1924 temp = delete_insn (temp);
1928 p = delete_insn (p);
1930 /* simplify_giv_expr expects that it can walk the insns
1931 at m->insn forwards and see this old sequence we are
1932 tossing here. delete_insn does preserve the next
1933 pointers, but when we skip over a NOTE we must fix
1934 it up. Otherwise that code walks into the non-deleted
1936 while (p && GET_CODE (p) == NOTE)
1937 p = NEXT_INSN (temp) = NEXT_INSN (p);
1941 emit_move_insn (m->set_dest, m->set_src);
1942 temp = get_insns ();
1945 add_label_notes (m->set_src, temp);
1947 i1 = emit_insns_before (temp, loop_start);
1948 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1950 = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
1951 m->set_src, REG_NOTES (i1));
1953 if (loop_dump_stream)
1954 fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1956 /* The more regs we move, the less we like moving them. */
1961 for (count = m->consec; count >= 0; count--)
1965 /* If first insn of libcall sequence, skip to end. */
1966 /* Do this at start of loop, since p is guaranteed to
1968 if (GET_CODE (p) != NOTE
1969 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1972 /* If last insn of libcall sequence, move all
1973 insns except the last before the loop. The last
1974 insn is handled in the normal manner. */
1975 if (GET_CODE (p) != NOTE
1976 && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1980 rtx fn_address_insn = 0;
1983 for (temp = XEXP (temp, 0); temp != p;
1984 temp = NEXT_INSN (temp))
1990 if (GET_CODE (temp) == NOTE)
1993 body = PATTERN (temp);
1995 /* Find the next insn after TEMP,
1996 not counting USE or NOTE insns. */
1997 for (next = NEXT_INSN (temp); next != p;
1998 next = NEXT_INSN (next))
1999 if (! (GET_CODE (next) == INSN
2000 && GET_CODE (PATTERN (next)) == USE)
2001 && GET_CODE (next) != NOTE)
2004 /* If that is the call, this may be the insn
2005 that loads the function address.
2007 Extract the function address from the insn
2008 that loads it into a register.
2009 If this insn was cse'd, we get incorrect code.
2011 So emit a new move insn that copies the
2012 function address into the register that the
2013 call insn will use. flow.c will delete any
2014 redundant stores that we have created. */
2015 if (GET_CODE (next) == CALL_INSN
2016 && GET_CODE (body) == SET
2017 && GET_CODE (SET_DEST (body)) == REG
2018 && (n = find_reg_note (temp, REG_EQUAL,
2021 fn_reg = SET_SRC (body);
2022 if (GET_CODE (fn_reg) != REG)
2023 fn_reg = SET_DEST (body);
2024 fn_address = XEXP (n, 0);
2025 fn_address_insn = temp;
2027 /* We have the call insn.
2028 If it uses the register we suspect it might,
2029 load it with the correct address directly. */
2030 if (GET_CODE (temp) == CALL_INSN
2032 && reg_referenced_p (fn_reg, body))
2033 emit_insn_after (gen_move_insn (fn_reg,
2037 if (GET_CODE (temp) == CALL_INSN)
2039 i1 = emit_call_insn_before (body, loop_start);
2040 /* Because the USAGE information potentially
2041 contains objects other than hard registers
2042 we need to copy it. */
2043 if (CALL_INSN_FUNCTION_USAGE (temp))
2044 CALL_INSN_FUNCTION_USAGE (i1)
2045 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
2048 i1 = emit_insn_before (body, loop_start);
2051 if (temp == fn_address_insn)
2052 fn_address_insn = i1;
2053 REG_NOTES (i1) = REG_NOTES (temp);
2057 if (m->savemode != VOIDmode)
2059 /* P sets REG to zero; but we should clear only
2060 the bits that are not covered by the mode
2062 rtx reg = m->set_dest;
2068 (GET_MODE (reg), and_optab, reg,
2069 GEN_INT ((((HOST_WIDE_INT) 1
2070 << GET_MODE_BITSIZE (m->savemode)))
2072 reg, 1, OPTAB_LIB_WIDEN);
2076 emit_move_insn (reg, tem);
2077 sequence = gen_sequence ();
2079 i1 = emit_insn_before (sequence, loop_start);
2081 else if (GET_CODE (p) == CALL_INSN)
2083 i1 = emit_call_insn_before (PATTERN (p), loop_start);
2084 /* Because the USAGE information potentially
2085 contains objects other than hard registers
2086 we need to copy it. */
2087 if (CALL_INSN_FUNCTION_USAGE (p))
2088 CALL_INSN_FUNCTION_USAGE (i1)
2089 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
2091 else if (count == m->consec && m->move_insn_first)
2093 /* The SET_SRC might not be invariant, so we must
2094 use the REG_EQUAL note. */
2096 emit_move_insn (m->set_dest, m->set_src);
2097 temp = get_insns ();
2100 add_label_notes (m->set_src, temp);
2102 i1 = emit_insns_before (temp, loop_start);
2103 if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
2105 = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
2107 m->set_src, REG_NOTES (i1));
2110 i1 = emit_insn_before (PATTERN (p), loop_start);
2112 if (REG_NOTES (i1) == 0)
2114 REG_NOTES (i1) = REG_NOTES (p);
2116 /* If there is a REG_EQUAL note present whose value
2117 is not loop invariant, then delete it, since it
2118 may cause problems with later optimization passes.
2119 It is possible for cse to create such notes
2120 like this as a result of record_jump_cond. */
2122 if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
2123 && ! invariant_p (XEXP (temp, 0)))
2124 remove_note (i1, temp);
2130 if (loop_dump_stream)
2131 fprintf (loop_dump_stream, " moved to %d",
2134 /* If library call, now fix the REG_NOTES that contain
2135 insn pointers, namely REG_LIBCALL on FIRST
2136 and REG_RETVAL on I1. */
2137 if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2139 XEXP (temp, 0) = first;
2140 temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2141 XEXP (temp, 0) = i1;
2148 /* simplify_giv_expr expects that it can walk the insns
2149 at m->insn forwards and see this old sequence we are
2150 tossing here. delete_insn does preserve the next
2151 pointers, but when we skip over a NOTE we must fix
2152 it up. Otherwise that code walks into the non-deleted
2154 while (p && GET_CODE (p) == NOTE)
2155 p = NEXT_INSN (temp) = NEXT_INSN (p);
2158 /* The more regs we move, the less we like moving them. */
2162 /* Any other movable that loads the same register
2164 already_moved[regno] = 1;
2166 /* This reg has been moved out of one loop. */
2167 moved_once[regno] = 1;
2169 /* The reg set here is now invariant. */
2171 VARRAY_INT (n_times_set, regno) = 0;
2175 /* Change the length-of-life info for the register
2176 to say it lives at least the full length of this loop.
2177 This will help guide optimizations in outer loops. */
2179 if (uid_luid[REGNO_FIRST_UID (regno)] > INSN_LUID (loop_start))
2180 /* This is the old insn before all the moved insns.
2181 We can't use the moved insn because it is out of range
2182 in uid_luid. Only the old insns have luids. */
2183 REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2184 if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
2185 REGNO_LAST_UID (regno) = INSN_UID (end);
2187 /* Combine with this moved insn any other matching movables. */
2190 for (m1 = movables; m1; m1 = m1->next)
2195 /* Schedule the reg loaded by M1
2196 for replacement so that shares the reg of M.
2197 If the modes differ (only possible in restricted
2198 circumstances, make a SUBREG. */
2199 if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2200 reg_map[m1->regno] = m->set_dest;
2203 = gen_lowpart_common (GET_MODE (m1->set_dest),
2206 /* Get rid of the matching insn
2207 and prevent further processing of it. */
2210 /* if library call, delete all insn except last, which
2212 if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2215 for (temp = XEXP (temp, 0); temp != m1->insn;
2216 temp = NEXT_INSN (temp))
2219 delete_insn (m1->insn);
2221 /* Any other movable that loads the same register
2223 already_moved[m1->regno] = 1;
2225 /* The reg merged here is now invariant,
2226 if the reg it matches is invariant. */
2228 VARRAY_INT (n_times_set, m1->regno) = 0;
2231 else if (loop_dump_stream)
2232 fprintf (loop_dump_stream, "not desirable");
2234 else if (loop_dump_stream && !m->match)
2235 fprintf (loop_dump_stream, "not safe");
2237 if (loop_dump_stream)
2238 fprintf (loop_dump_stream, "\n");
2242 new_start = loop_start;
2244 /* Go through all the instructions in the loop, making
2245 all the register substitutions scheduled in REG_MAP. */
2246 for (p = new_start; p != end; p = NEXT_INSN (p))
2247 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
2248 || GET_CODE (p) == CALL_INSN)
2250 replace_regs (PATTERN (p), reg_map, nregs, 0);
2251 replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2257 /* Scan X and replace the address of any MEM in it with ADDR.
2258 REG is the address that MEM should have before the replacement. */
2261 replace_call_address (x, reg, addr)
2264 register enum rtx_code code;
2270 code = GET_CODE (x);
2284 /* Short cut for very common case. */
2285 replace_call_address (XEXP (x, 1), reg, addr);
2289 /* Short cut for very common case. */
2290 replace_call_address (XEXP (x, 0), reg, addr);
2294 /* If this MEM uses a reg other than the one we expected,
2295 something is wrong. */
2296 if (XEXP (x, 0) != reg)
2305 fmt = GET_RTX_FORMAT (code);
2306 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2309 replace_call_address (XEXP (x, i), reg, addr);
2313 for (j = 0; j < XVECLEN (x, i); j++)
2314 replace_call_address (XVECEXP (x, i, j), reg, addr);
2320 /* Return the number of memory refs to addresses that vary
2324 count_nonfixed_reads (x)
2327 register enum rtx_code code;
2335 code = GET_CODE (x);
2349 return ((invariant_p (XEXP (x, 0)) != 1)
2350 + count_nonfixed_reads (XEXP (x, 0)));
2357 fmt = GET_RTX_FORMAT (code);
2358 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2361 value += count_nonfixed_reads (XEXP (x, i));
2365 for (j = 0; j < XVECLEN (x, i); j++)
2366 value += count_nonfixed_reads (XVECEXP (x, i, j));
2374 /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
2375 Replace it with an instruction to load just the low bytes
2376 if the machine supports such an instruction,
2377 and insert above LOOP_START an instruction to clear the register. */
2380 constant_high_bytes (p, loop_start)
2384 register int insn_code_number;
2386 /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
2387 to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
2389 new = gen_rtx_SET (VOIDmode,
2390 gen_rtx_STRICT_LOW_PART (VOIDmode,
2391 gen_rtx_SUBREG (GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
2392 SET_DEST (PATTERN (p)),
2394 XEXP (SET_SRC (PATTERN (p)), 0));
2395 insn_code_number = recog (new, p);
2397 if (insn_code_number)
2401 /* Clear destination register before the loop. */
2402 emit_insn_before (gen_rtx_SET (VOIDmode, SET_DEST (PATTERN (p)),
2406 /* Inside the loop, just load the low part. */
2412 /* Scan a loop setting the variables `unknown_address_altered',
2413 `num_mem_sets', `loop_continue', loops_enclosed', `loop_has_call',
2414 and `loop_has_volatile'. Also, fill in the arrays `loop_mems' and
2415 `loop_store_mems'. */
2418 prescan_loop (start, end)
2421 register int level = 1;
2423 int loop_has_multiple_exit_targets = 0;
2424 /* The label after END. Jumping here is just like falling off the
2425 end of the loop. We use next_nonnote_insn instead of next_label
2426 as a hedge against the (pathological) case where some actual insn
2427 might end up between the two. */
2428 rtx exit_target = next_nonnote_insn (end);
2429 if (exit_target == NULL_RTX || GET_CODE (exit_target) != CODE_LABEL)
2430 loop_has_multiple_exit_targets = 1;
2432 unknown_address_altered = 0;
2434 loop_has_volatile = 0;
2435 loop_store_mems_idx = 0;
2442 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2443 insn = NEXT_INSN (insn))
2445 if (GET_CODE (insn) == NOTE)
2447 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2450 /* Count number of loops contained in this one. */
2453 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2462 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
2465 loop_continue = insn;
2468 else if (GET_CODE (insn) == CALL_INSN)
2470 if (! CONST_CALL_P (insn))
2471 unknown_address_altered = 1;
2474 else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2476 rtx label1 = NULL_RTX;
2477 rtx label2 = NULL_RTX;
2479 if (volatile_refs_p (PATTERN (insn)))
2480 loop_has_volatile = 1;
2482 note_stores (PATTERN (insn), note_addr_stored);
2484 if (!loop_has_multiple_exit_targets
2485 && GET_CODE (insn) == JUMP_INSN
2486 && GET_CODE (PATTERN (insn)) == SET
2487 && SET_DEST (PATTERN (insn)) == pc_rtx)
2489 if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
2491 label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
2492 label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
2496 label1 = SET_SRC (PATTERN (insn));
2500 if (label1 && label1 != pc_rtx)
2502 if (GET_CODE (label1) != LABEL_REF)
2504 /* Something tricky. */
2505 loop_has_multiple_exit_targets = 1;
2508 else if (XEXP (label1, 0) != exit_target
2509 && LABEL_OUTSIDE_LOOP_P (label1))
2511 /* A jump outside the current loop. */
2512 loop_has_multiple_exit_targets = 1;
2522 else if (GET_CODE (insn) == RETURN)
2523 loop_has_multiple_exit_targets = 1;
2526 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2527 if (/* We can't tell what MEMs are aliased by what. */
2528 !unknown_address_altered
2529 /* An exception thrown by a called function might land us
2532 /* We don't want loads for MEMs moved to a location before the
2533 one at which their stack memory becomes allocated. (Note
2534 that this is not a problem for malloc, etc., since those
2535 require actual function calls. */
2536 && !current_function_calls_alloca
2537 /* There are ways to leave the loop other than falling off the
2539 && !loop_has_multiple_exit_targets)
2540 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2541 insn = NEXT_INSN (insn))
2542 for_each_rtx (&insn, insert_loop_mem, 0);
2545 /* Scan the function looking for loops. Record the start and end of each loop.
2546 Also mark as invalid loops any loops that contain a setjmp or are branched
2547 to from outside the loop. */
2550 find_and_verify_loops (f)
2554 int current_loop = -1;
2558 /* If there are jumps to undefined labels,
2559 treat them as jumps out of any/all loops.
2560 This also avoids writing past end of tables when there are no loops. */
2561 uid_loop_num[0] = -1;
2563 /* Find boundaries of loops, mark which loops are contained within
2564 loops, and invalidate loops that have setjmp. */
2566 for (insn = f; insn; insn = NEXT_INSN (insn))
2568 if (GET_CODE (insn) == NOTE)
2569 switch (NOTE_LINE_NUMBER (insn))
2571 case NOTE_INSN_LOOP_BEG:
2572 loop_number_loop_starts[++next_loop] = insn;
2573 loop_number_loop_ends[next_loop] = 0;
2574 loop_outer_loop[next_loop] = current_loop;
2575 loop_invalid[next_loop] = 0;
2576 loop_number_exit_labels[next_loop] = 0;
2577 loop_number_exit_count[next_loop] = 0;
2578 current_loop = next_loop;
2581 case NOTE_INSN_SETJMP:
2582 /* In this case, we must invalidate our current loop and any
2584 for (loop = current_loop; loop != -1; loop = loop_outer_loop[loop])
2586 loop_invalid[loop] = 1;
2587 if (loop_dump_stream)
2588 fprintf (loop_dump_stream,
2589 "\nLoop at %d ignored due to setjmp.\n",
2590 INSN_UID (loop_number_loop_starts[loop]));
2594 case NOTE_INSN_LOOP_END:
2595 if (current_loop == -1)
2598 loop_number_loop_ends[current_loop] = insn;
2599 current_loop = loop_outer_loop[current_loop];
2606 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2607 enclosing loop, but this doesn't matter. */
2608 uid_loop_num[INSN_UID (insn)] = current_loop;
2611 /* Any loop containing a label used in an initializer must be invalidated,
2612 because it can be jumped into from anywhere. */
2614 for (label = forced_labels; label; label = XEXP (label, 1))
2618 for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
2620 loop_num = loop_outer_loop[loop_num])
2621 loop_invalid[loop_num] = 1;
2624 /* Any loop containing a label used for an exception handler must be
2625 invalidated, because it can be jumped into from anywhere. */
2627 for (label = exception_handler_labels; label; label = XEXP (label, 1))
2631 for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
2633 loop_num = loop_outer_loop[loop_num])
2634 loop_invalid[loop_num] = 1;
2637 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2638 loop that it is not contained within, that loop is marked invalid.
2639 If any INSN or CALL_INSN uses a label's address, then the loop containing
2640 that label is marked invalid, because it could be jumped into from
2643 Also look for blocks of code ending in an unconditional branch that
2644 exits the loop. If such a block is surrounded by a conditional
2645 branch around the block, move the block elsewhere (see below) and
2646 invert the jump to point to the code block. This may eliminate a
2647 label in our loop and will simplify processing by both us and a
2648 possible second cse pass. */
2650 for (insn = f; insn; insn = NEXT_INSN (insn))
2651 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2653 int this_loop_num = uid_loop_num[INSN_UID (insn)];
2655 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2657 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
2662 for (loop_num = uid_loop_num[INSN_UID (XEXP (note, 0))];
2664 loop_num = loop_outer_loop[loop_num])
2665 loop_invalid[loop_num] = 1;
2669 if (GET_CODE (insn) != JUMP_INSN)
2672 mark_loop_jump (PATTERN (insn), this_loop_num);
2674 /* See if this is an unconditional branch outside the loop. */
2675 if (this_loop_num != -1
2676 && (GET_CODE (PATTERN (insn)) == RETURN
2677 || (simplejump_p (insn)
2678 && (uid_loop_num[INSN_UID (JUMP_LABEL (insn))]
2680 && get_max_uid () < max_uid_for_loop)
2683 rtx our_next = next_real_insn (insn);
2685 int outer_loop = -1;
2687 /* Go backwards until we reach the start of the loop, a label,
2689 for (p = PREV_INSN (insn);
2690 GET_CODE (p) != CODE_LABEL
2691 && ! (GET_CODE (p) == NOTE
2692 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2693 && GET_CODE (p) != JUMP_INSN;
2697 /* Check for the case where we have a jump to an inner nested
2698 loop, and do not perform the optimization in that case. */
2700 if (JUMP_LABEL (insn))
2702 dest_loop = uid_loop_num[INSN_UID (JUMP_LABEL (insn))];
2703 if (dest_loop != -1)
2705 for (outer_loop = dest_loop; outer_loop != -1;
2706 outer_loop = loop_outer_loop[outer_loop])
2707 if (outer_loop == this_loop_num)
2712 /* Make sure that the target of P is within the current loop. */
2714 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
2715 && uid_loop_num[INSN_UID (JUMP_LABEL (p))] != this_loop_num)
2716 outer_loop = this_loop_num;
2718 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2719 we have a block of code to try to move.
2721 We look backward and then forward from the target of INSN
2722 to find a BARRIER at the same loop depth as the target.
2723 If we find such a BARRIER, we make a new label for the start
2724 of the block, invert the jump in P and point it to that label,
2725 and move the block of code to the spot we found. */
2727 if (outer_loop == -1
2728 && GET_CODE (p) == JUMP_INSN
2729 && JUMP_LABEL (p) != 0
2730 /* Just ignore jumps to labels that were never emitted.
2731 These always indicate compilation errors. */
2732 && INSN_UID (JUMP_LABEL (p)) != 0
2734 && ! simplejump_p (p)
2735 && next_real_insn (JUMP_LABEL (p)) == our_next)
2738 = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2739 int target_loop_num = uid_loop_num[INSN_UID (target)];
2742 for (loc = target; loc; loc = PREV_INSN (loc))
2743 if (GET_CODE (loc) == BARRIER
2744 && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2748 for (loc = target; loc; loc = NEXT_INSN (loc))
2749 if (GET_CODE (loc) == BARRIER
2750 && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2755 rtx cond_label = JUMP_LABEL (p);
2756 rtx new_label = get_label_after (p);
2758 /* Ensure our label doesn't go away. */
2759 LABEL_NUSES (cond_label)++;
2761 /* Verify that uid_loop_num is large enough and that
2763 if (invert_jump (p, new_label))
2767 /* If no suitable BARRIER was found, create a suitable
2768 one before TARGET. Since TARGET is a fall through
2769 path, we'll need to insert an jump around our block
2770 and a add a BARRIER before TARGET.
2772 This creates an extra unconditional jump outside
2773 the loop. However, the benefits of removing rarely
2774 executed instructions from inside the loop usually
2775 outweighs the cost of the extra unconditional jump
2776 outside the loop. */
2781 temp = gen_jump (JUMP_LABEL (insn));
2782 temp = emit_jump_insn_before (temp, target);
2783 JUMP_LABEL (temp) = JUMP_LABEL (insn);
2784 LABEL_NUSES (JUMP_LABEL (insn))++;
2785 loc = emit_barrier_before (target);
2788 /* Include the BARRIER after INSN and copy the
2790 new_label = squeeze_notes (new_label, NEXT_INSN (insn));
2791 reorder_insns (new_label, NEXT_INSN (insn), loc);
2793 /* All those insns are now in TARGET_LOOP_NUM. */
2794 for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
2796 uid_loop_num[INSN_UID (q)] = target_loop_num;
2798 /* The label jumped to by INSN is no longer a loop exit.
2799 Unless INSN does not have a label (e.g., it is a
2800 RETURN insn), search loop_number_exit_labels to find
2801 its label_ref, and remove it. Also turn off
2802 LABEL_OUTSIDE_LOOP_P bit. */
2803 if (JUMP_LABEL (insn))
2808 r = loop_number_exit_labels[this_loop_num];
2809 r; q = r, r = LABEL_NEXTREF (r))
2810 if (XEXP (r, 0) == JUMP_LABEL (insn))
2812 LABEL_OUTSIDE_LOOP_P (r) = 0;
2814 LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2816 loop_number_exit_labels[this_loop_num]
2817 = LABEL_NEXTREF (r);
2821 for (loop_num = this_loop_num;
2822 loop_num != -1 && loop_num != target_loop_num;
2823 loop_num = loop_outer_loop[loop_num])
2824 loop_number_exit_count[loop_num]--;
2826 /* If we didn't find it, then something is wrong. */
2831 /* P is now a jump outside the loop, so it must be put
2832 in loop_number_exit_labels, and marked as such.
2833 The easiest way to do this is to just call
2834 mark_loop_jump again for P. */
2835 mark_loop_jump (PATTERN (p), this_loop_num);
2837 /* If INSN now jumps to the insn after it,
2839 if (JUMP_LABEL (insn) != 0
2840 && (next_real_insn (JUMP_LABEL (insn))
2841 == next_real_insn (insn)))
2845 /* Continue the loop after where the conditional
2846 branch used to jump, since the only branch insn
2847 in the block (if it still remains) is an inter-loop
2848 branch and hence needs no processing. */
2849 insn = NEXT_INSN (cond_label);
2851 if (--LABEL_NUSES (cond_label) == 0)
2852 delete_insn (cond_label);
2854 /* This loop will be continued with NEXT_INSN (insn). */
2855 insn = PREV_INSN (insn);
2862 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2863 loops it is contained in, mark the target loop invalid.
2865 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2868 mark_loop_jump (x, loop_num)
2876 switch (GET_CODE (x))
2889 /* There could be a label reference in here. */
2890 mark_loop_jump (XEXP (x, 0), loop_num);
2896 mark_loop_jump (XEXP (x, 0), loop_num);
2897 mark_loop_jump (XEXP (x, 1), loop_num);
2902 mark_loop_jump (XEXP (x, 0), loop_num);
2906 dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))];
2908 /* Link together all labels that branch outside the loop. This
2909 is used by final_[bg]iv_value and the loop unrolling code. Also
2910 mark this LABEL_REF so we know that this branch should predict
2913 /* A check to make sure the label is not in an inner nested loop,
2914 since this does not count as a loop exit. */
2915 if (dest_loop != -1)
2917 for (outer_loop = dest_loop; outer_loop != -1;
2918 outer_loop = loop_outer_loop[outer_loop])
2919 if (outer_loop == loop_num)
2925 if (loop_num != -1 && outer_loop == -1)
2927 LABEL_OUTSIDE_LOOP_P (x) = 1;
2928 LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
2929 loop_number_exit_labels[loop_num] = x;
2931 for (outer_loop = loop_num;
2932 outer_loop != -1 && outer_loop != dest_loop;
2933 outer_loop = loop_outer_loop[outer_loop])
2934 loop_number_exit_count[outer_loop]++;
2937 /* If this is inside a loop, but not in the current loop or one enclosed
2938 by it, it invalidates at least one loop. */
2940 if (dest_loop == -1)
2943 /* We must invalidate every nested loop containing the target of this
2944 label, except those that also contain the jump insn. */
2946 for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
2948 /* Stop when we reach a loop that also contains the jump insn. */
2949 for (outer_loop = loop_num; outer_loop != -1;
2950 outer_loop = loop_outer_loop[outer_loop])
2951 if (dest_loop == outer_loop)
2954 /* If we get here, we know we need to invalidate a loop. */
2955 if (loop_dump_stream && ! loop_invalid[dest_loop])
2956 fprintf (loop_dump_stream,
2957 "\nLoop at %d ignored due to multiple entry points.\n",
2958 INSN_UID (loop_number_loop_starts[dest_loop]));
2960 loop_invalid[dest_loop] = 1;
2965 /* If this is not setting pc, ignore. */
2966 if (SET_DEST (x) == pc_rtx)
2967 mark_loop_jump (SET_SRC (x), loop_num);
2971 mark_loop_jump (XEXP (x, 1), loop_num);
2972 mark_loop_jump (XEXP (x, 2), loop_num);
2977 for (i = 0; i < XVECLEN (x, 0); i++)
2978 mark_loop_jump (XVECEXP (x, 0, i), loop_num);
2982 for (i = 0; i < XVECLEN (x, 1); i++)
2983 mark_loop_jump (XVECEXP (x, 1, i), loop_num);
2987 /* Treat anything else (such as a symbol_ref)
2988 as a branch out of this loop, but not into any loop. */
2993 LABEL_OUTSIDE_LOOP_P (x) = 1;
2994 LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
2997 loop_number_exit_labels[loop_num] = x;
2999 for (outer_loop = loop_num; outer_loop != -1;
3000 outer_loop = loop_outer_loop[outer_loop])
3001 loop_number_exit_count[outer_loop]++;
3007 /* Return nonzero if there is a label in the range from
3008 insn INSN to and including the insn whose luid is END
3009 INSN must have an assigned luid (i.e., it must not have
3010 been previously created by loop.c). */
3013 labels_in_range_p (insn, end)
3017 while (insn && INSN_LUID (insn) <= end)
3019 if (GET_CODE (insn) == CODE_LABEL)
3021 insn = NEXT_INSN (insn);
3027 /* Record that a memory reference X is being set. */
3030 note_addr_stored (x, y)
3032 rtx y ATTRIBUTE_UNUSED;
3036 if (x == 0 || GET_CODE (x) != MEM)
3039 /* Count number of memory writes.
3040 This affects heuristics in strength_reduce. */
3043 /* BLKmode MEM means all memory is clobbered. */
3044 if (GET_MODE (x) == BLKmode)
3045 unknown_address_altered = 1;
3047 if (unknown_address_altered)
3050 for (i = 0; i < loop_store_mems_idx; i++)
3051 if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0))
3052 && MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
3054 /* We are storing at the same address as previously noted. Save the
3056 if (GET_MODE_SIZE (GET_MODE (x))
3057 > GET_MODE_SIZE (GET_MODE (loop_store_mems[i])))
3058 loop_store_mems[i] = x;
3062 if (i == NUM_STORES)
3063 unknown_address_altered = 1;
3065 else if (i == loop_store_mems_idx)
3066 loop_store_mems[loop_store_mems_idx++] = x;
3069 /* Return nonzero if the rtx X is invariant over the current loop.
3071 The value is 2 if we refer to something only conditionally invariant.
3073 If `unknown_address_altered' is nonzero, no memory ref is invariant.
3074 Otherwise, a memory ref is invariant if it does not conflict with
3075 anything stored in `loop_store_mems'. */
3082 register enum rtx_code code;
3084 int conditional = 0;
3088 code = GET_CODE (x);
3098 /* A LABEL_REF is normally invariant, however, if we are unrolling
3099 loops, and this label is inside the loop, then it isn't invariant.
3100 This is because each unrolled copy of the loop body will have
3101 a copy of this label. If this was invariant, then an insn loading
3102 the address of this label into a register might get moved outside
3103 the loop, and then each loop body would end up using the same label.
3105 We don't know the loop bounds here though, so just fail for all
3107 if (flag_unroll_loops)
3114 case UNSPEC_VOLATILE:
3118 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3119 since the reg might be set by initialization within the loop. */
3121 if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
3122 || x == arg_pointer_rtx)
3123 && ! current_function_has_nonlocal_goto)
3127 && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
3130 if (VARRAY_INT (n_times_set, REGNO (x)) < 0)
3133 return VARRAY_INT (n_times_set, REGNO (x)) == 0;
3136 /* Volatile memory references must be rejected. Do this before
3137 checking for read-only items, so that volatile read-only items
3138 will be rejected also. */
3139 if (MEM_VOLATILE_P (x))
3142 /* Read-only items (such as constants in a constant pool) are
3143 invariant if their address is. */
3144 if (RTX_UNCHANGING_P (x))
3147 /* If we filled the table (or had a subroutine call), any location
3148 in memory could have been clobbered. */
3149 if (unknown_address_altered)
3152 /* See if there is any dependence between a store and this load. */
3153 for (i = loop_store_mems_idx - 1; i >= 0; i--)
3154 if (true_dependence (loop_store_mems[i], VOIDmode, x, rtx_varies_p))
3157 /* It's not invalidated by a store in memory
3158 but we must still verify the address is invariant. */
3162 /* Don't mess with insns declared volatile. */
3163 if (MEM_VOLATILE_P (x))
3171 fmt = GET_RTX_FORMAT (code);
3172 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3176 int tem = invariant_p (XEXP (x, i));
3182 else if (fmt[i] == 'E')
3185 for (j = 0; j < XVECLEN (x, i); j++)
3187 int tem = invariant_p (XVECEXP (x, i, j));
3197 return 1 + conditional;
3201 /* Return nonzero if all the insns in the loop that set REG
3202 are INSN and the immediately following insns,
3203 and if each of those insns sets REG in an invariant way
3204 (not counting uses of REG in them).
3206 The value is 2 if some of these insns are only conditionally invariant.
3208 We assume that INSN itself is the first set of REG
3209 and that its source is invariant. */
3212 consec_sets_invariant_p (reg, n_sets, insn)
3216 register rtx p = insn;
3217 register int regno = REGNO (reg);
3219 /* Number of sets we have to insist on finding after INSN. */
3220 int count = n_sets - 1;
3221 int old = VARRAY_INT (n_times_set, regno);
3225 /* If N_SETS hit the limit, we can't rely on its value. */
3229 VARRAY_INT (n_times_set, regno) = 0;
3233 register enum rtx_code code;
3237 code = GET_CODE (p);
3239 /* If library call, skip to end of it. */
3240 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
3245 && (set = single_set (p))
3246 && GET_CODE (SET_DEST (set)) == REG
3247 && REGNO (SET_DEST (set)) == regno)
3249 this = invariant_p (SET_SRC (set));
3252 else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
3254 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3255 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3257 this = (CONSTANT_P (XEXP (temp, 0))
3258 || (find_reg_note (p, REG_RETVAL, NULL_RTX)
3259 && invariant_p (XEXP (temp, 0))));
3266 else if (code != NOTE)
3268 VARRAY_INT (n_times_set, regno) = old;
3273 VARRAY_INT (n_times_set, regno) = old;
3274 /* If invariant_p ever returned 2, we return 2. */
3275 return 1 + (value & 2);
3279 /* I don't think this condition is sufficient to allow INSN
3280 to be moved, so we no longer test it. */
3282 /* Return 1 if all insns in the basic block of INSN and following INSN
3283 that set REG are invariant according to TABLE. */
3286 all_sets_invariant_p (reg, insn, table)
3290 register rtx p = insn;
3291 register int regno = REGNO (reg);
3295 register enum rtx_code code;
3297 code = GET_CODE (p);
3298 if (code == CODE_LABEL || code == JUMP_INSN)
3300 if (code == INSN && GET_CODE (PATTERN (p)) == SET
3301 && GET_CODE (SET_DEST (PATTERN (p))) == REG
3302 && REGNO (SET_DEST (PATTERN (p))) == regno)
3304 if (!invariant_p (SET_SRC (PATTERN (p)), table))
3311 /* Look at all uses (not sets) of registers in X. For each, if it is
3312 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3313 a different insn, set USAGE[REGNO] to const0_rtx. */
3316 find_single_use_in_loop (insn, x, usage)
3321 enum rtx_code code = GET_CODE (x);
3322 char *fmt = GET_RTX_FORMAT (code);
3326 VARRAY_RTX (usage, REGNO (x))
3327 = (VARRAY_RTX (usage, REGNO (x)) != 0
3328 && VARRAY_RTX (usage, REGNO (x)) != insn)
3329 ? const0_rtx : insn;
3331 else if (code == SET)
3333 /* Don't count SET_DEST if it is a REG; otherwise count things
3334 in SET_DEST because if a register is partially modified, it won't
3335 show up as a potential movable so we don't care how USAGE is set
3337 if (GET_CODE (SET_DEST (x)) != REG)
3338 find_single_use_in_loop (insn, SET_DEST (x), usage);
3339 find_single_use_in_loop (insn, SET_SRC (x), usage);
3342 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3344 if (fmt[i] == 'e' && XEXP (x, i) != 0)
3345 find_single_use_in_loop (insn, XEXP (x, i), usage);
3346 else if (fmt[i] == 'E')
3347 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3348 find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
3352 /* Increment N_TIMES_SET at the index of each register
3353 that is modified by an insn between FROM and TO.
3354 If the value of an element of N_TIMES_SET becomes 127 or more,
3355 stop incrementing it, to avoid overflow.
3357 Store in SINGLE_USAGE[I] the single insn in which register I is
3358 used, if it is only used once. Otherwise, it is set to 0 (for no
3359 uses) or const0_rtx for more than one use. This parameter may be zero,
3360 in which case this processing is not done.
3362 Store in *COUNT_PTR the number of actual instruction
3363 in the loop. We use this to decide what is worth moving out. */
3365 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3366 In that case, it is the insn that last set reg n. */
3369 count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
3370 register rtx from, to;
3371 varray_type may_not_move;
3372 varray_type single_usage;
3376 register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
3378 register int count = 0;
3381 bzero ((char *) last_set, nregs * sizeof (rtx));
3382 for (insn = from; insn != to; insn = NEXT_INSN (insn))
3384 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3388 /* If requested, record registers that have exactly one use. */
3391 find_single_use_in_loop (insn, PATTERN (insn), single_usage);
3393 /* Include uses in REG_EQUAL notes. */
3394 if (REG_NOTES (insn))
3395 find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
3398 if (GET_CODE (PATTERN (insn)) == CLOBBER
3399 && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
3400 /* Don't move a reg that has an explicit clobber.
3401 We might do so sometimes, but it's not worth the pain. */
3402 VARRAY_CHAR (may_not_move, REGNO (XEXP (PATTERN (insn), 0))) = 1;
3404 if (GET_CODE (PATTERN (insn)) == SET
3405 || GET_CODE (PATTERN (insn)) == CLOBBER)
3407 dest = SET_DEST (PATTERN (insn));
3408 while (GET_CODE (dest) == SUBREG
3409 || GET_CODE (dest) == ZERO_EXTRACT
3410 || GET_CODE (dest) == SIGN_EXTRACT
3411 || GET_CODE (dest) == STRICT_LOW_PART)
3412 dest = XEXP (dest, 0);
3413 if (GET_CODE (dest) == REG)
3415 register int regno = REGNO (dest);
3416 /* If this is the first setting of this reg
3417 in current basic block, and it was set before,
3418 it must be set in two basic blocks, so it cannot
3419 be moved out of the loop. */
3420 if (VARRAY_INT (n_times_set, regno) > 0
3421 && last_set[regno] == 0)
3422 VARRAY_CHAR (may_not_move, regno) = 1;
3423 /* If this is not first setting in current basic block,
3424 see if reg was used in between previous one and this.
3425 If so, neither one can be moved. */
3426 if (last_set[regno] != 0
3427 && reg_used_between_p (dest, last_set[regno], insn))
3428 VARRAY_CHAR (may_not_move, regno) = 1;
3429 if (VARRAY_INT (n_times_set, regno) < 127)
3430 ++VARRAY_INT (n_times_set, regno);
3431 last_set[regno] = insn;
3434 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3437 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3439 register rtx x = XVECEXP (PATTERN (insn), 0, i);
3440 if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
3441 /* Don't move a reg that has an explicit clobber.
3442 It's not worth the pain to try to do it correctly. */
3443 VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
3445 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
3447 dest = SET_DEST (x);
3448 while (GET_CODE (dest) == SUBREG
3449 || GET_CODE (dest) == ZERO_EXTRACT
3450 || GET_CODE (dest) == SIGN_EXTRACT
3451 || GET_CODE (dest) == STRICT_LOW_PART)
3452 dest = XEXP (dest, 0);
3453 if (GET_CODE (dest) == REG)
3455 register int regno = REGNO (dest);
3456 if (VARRAY_INT (n_times_set, regno) > 0
3457 && last_set[regno] == 0)
3458 VARRAY_CHAR (may_not_move, regno) = 1;
3459 if (last_set[regno] != 0
3460 && reg_used_between_p (dest, last_set[regno], insn))
3461 VARRAY_CHAR (may_not_move, regno) = 1;
3462 if (VARRAY_INT (n_times_set, regno) < 127)
3463 ++VARRAY_INT (n_times_set, regno);
3464 last_set[regno] = insn;
3471 if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
3472 bzero ((char *) last_set, nregs * sizeof (rtx));
3477 /* Given a loop that is bounded by LOOP_START and LOOP_END
3478 and that is entered at SCAN_START,
3479 return 1 if the register set in SET contained in insn INSN is used by
3480 any insn that precedes INSN in cyclic order starting
3481 from the loop entry point.
3483 We don't want to use INSN_LUID here because if we restrict INSN to those
3484 that have a valid INSN_LUID, it means we cannot move an invariant out
3485 from an inner loop past two loops. */
3488 loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
3489 rtx set, insn, loop_start, scan_start, loop_end;
3491 rtx reg = SET_DEST (set);
3494 /* Scan forward checking for register usage. If we hit INSN, we
3495 are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
3496 for (p = scan_start; p != insn; p = NEXT_INSN (p))
3498 if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
3499 && reg_overlap_mentioned_p (reg, PATTERN (p)))
3509 /* A "basic induction variable" or biv is a pseudo reg that is set
3510 (within this loop) only by incrementing or decrementing it. */
3511 /* A "general induction variable" or giv is a pseudo reg whose
3512 value is a linear function of a biv. */
3514 /* Bivs are recognized by `basic_induction_var';
3515 Givs by `general_induction_var'. */
3517 /* Indexed by register number, indicates whether or not register is an
3518 induction variable, and if so what type. */
3520 enum iv_mode *reg_iv_type;
3522 /* Indexed by register number, contains pointer to `struct induction'
3523 if register is an induction variable. This holds general info for
3524 all induction variables. */
3526 struct induction **reg_iv_info;
3528 /* Indexed by register number, contains pointer to `struct iv_class'
3529 if register is a basic induction variable. This holds info describing
3530 the class (a related group) of induction variables that the biv belongs
3533 struct iv_class **reg_biv_class;
3535 /* The head of a list which links together (via the next field)
3536 every iv class for the current loop. */
3538 struct iv_class *loop_iv_list;
3540 /* Communication with routines called via `note_stores'. */
3542 static rtx note_insn;
3544 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3546 static rtx addr_placeholder;
3548 /* ??? Unfinished optimizations, and possible future optimizations,
3549 for the strength reduction code. */
3551 /* ??? The interaction of biv elimination, and recognition of 'constant'
3552 bivs, may cause problems. */
3554 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3555 performance problems.
3557 Perhaps don't eliminate things that can be combined with an addressing
3558 mode. Find all givs that have the same biv, mult_val, and add_val;
3559 then for each giv, check to see if its only use dies in a following
3560 memory address. If so, generate a new memory address and check to see
3561 if it is valid. If it is valid, then store the modified memory address,
3562 otherwise, mark the giv as not done so that it will get its own iv. */
3564 /* ??? Could try to optimize branches when it is known that a biv is always
3567 /* ??? When replace a biv in a compare insn, we should replace with closest
3568 giv so that an optimized branch can still be recognized by the combiner,
3569 e.g. the VAX acb insn. */
3571 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3572 was rerun in loop_optimize whenever a register was added or moved.
3573 Also, some of the optimizations could be a little less conservative. */
3575 /* Perform strength reduction and induction variable elimination.
3577 Pseudo registers created during this function will be beyond the last
3578 valid index in several tables including n_times_set and regno_last_uid.
3579 This does not cause a problem here, because the added registers cannot be
3580 givs outside of their loop, and hence will never be reconsidered.
3581 But scan_loop must check regnos to make sure they are in bounds.
3583 SCAN_START is the first instruction in the loop, as the loop would
3584 actually be executed. END is the NOTE_INSN_LOOP_END. LOOP_TOP is
3585 the first instruction in the loop, as it is layed out in the
3586 instruction stream. LOOP_START is the NOTE_INSN_LOOP_BEG. */
3589 strength_reduce (scan_start, end, loop_top, insn_count,
3590 loop_start, loop_end, unroll_p, bct_p)
3597 int unroll_p, bct_p;
3604 /* This is 1 if current insn is not executed at least once for every loop
3606 int not_every_iteration = 0;
3607 /* This is 1 if current insn may be executed more than once for every
3609 int maybe_multiple = 0;
3610 /* Temporary list pointers for traversing loop_iv_list. */
3611 struct iv_class *bl, **backbl;
3612 /* Ratio of extra register life span we can justify
3613 for saving an instruction. More if loop doesn't call subroutines
3614 since in that case saving an insn makes more difference
3615 and more registers are available. */
3616 /* ??? could set this to last value of threshold in move_movables */
3617 int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3618 /* Map of pseudo-register replacements. */
3622 rtx end_insert_before;
3625 reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop
3626 * sizeof (enum iv_mode *));
3627 bzero ((char *) reg_iv_type, max_reg_before_loop * sizeof (enum iv_mode *));
3628 reg_iv_info = (struct induction **)
3629 alloca (max_reg_before_loop * sizeof (struct induction *));
3630 bzero ((char *) reg_iv_info, (max_reg_before_loop
3631 * sizeof (struct induction *)));
3632 reg_biv_class = (struct iv_class **)
3633 alloca (max_reg_before_loop * sizeof (struct iv_class *));
3634 bzero ((char *) reg_biv_class, (max_reg_before_loop
3635 * sizeof (struct iv_class *)));
3638 addr_placeholder = gen_reg_rtx (Pmode);
3640 /* Save insn immediately after the loop_end. Insns inserted after loop_end
3641 must be put before this insn, so that they will appear in the right
3642 order (i.e. loop order).
3644 If loop_end is the end of the current function, then emit a
3645 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
3647 if (NEXT_INSN (loop_end) != 0)
3648 end_insert_before = NEXT_INSN (loop_end);
3650 end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
3652 /* Scan through loop to find all possible bivs. */
3654 for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
3656 p = next_insn_in_loop (p, scan_start, end, loop_top))
3658 if (GET_CODE (p) == INSN
3659 && (set = single_set (p))
3660 && GET_CODE (SET_DEST (set)) == REG)
3662 dest_reg = SET_DEST (set);
3663 if (REGNO (dest_reg) < max_reg_before_loop
3664 && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
3665 && reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT)
3667 if (basic_induction_var (SET_SRC (set), GET_MODE (SET_SRC (set)),
3668 dest_reg, p, &inc_val, &mult_val))
3670 /* It is a possible basic induction variable.
3671 Create and initialize an induction structure for it. */
3674 = (struct induction *) alloca (sizeof (struct induction));
3676 record_biv (v, p, dest_reg, inc_val, mult_val,
3677 not_every_iteration, maybe_multiple);
3678 reg_iv_type[REGNO (dest_reg)] = BASIC_INDUCT;
3680 else if (REGNO (dest_reg) < max_reg_before_loop)
3681 reg_iv_type[REGNO (dest_reg)] = NOT_BASIC_INDUCT;
3685 /* Past CODE_LABEL, we get to insns that may be executed multiple
3686 times. The only way we can be sure that they can't is if every
3687 jump insn between here and the end of the loop either
3688 returns, exits the loop, is a forward jump, or is a jump
3689 to the loop start. */
3691 if (GET_CODE (p) == CODE_LABEL)
3699 insn = NEXT_INSN (insn);
3700 if (insn == scan_start)
3708 if (insn == scan_start)
3712 if (GET_CODE (insn) == JUMP_INSN
3713 && GET_CODE (PATTERN (insn)) != RETURN
3714 && (! condjump_p (insn)
3715 || (JUMP_LABEL (insn) != 0
3716 && JUMP_LABEL (insn) != scan_start
3717 && (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
3718 || INSN_UID (insn) >= max_uid_for_loop
3719 || (INSN_LUID (JUMP_LABEL (insn))
3720 < INSN_LUID (insn))))))
3728 /* Past a jump, we get to insns for which we can't count
3729 on whether they will be executed during each iteration. */
3730 /* This code appears twice in strength_reduce. There is also similar
3731 code in scan_loop. */
3732 if (GET_CODE (p) == JUMP_INSN
3733 /* If we enter the loop in the middle, and scan around to the
3734 beginning, don't set not_every_iteration for that.
3735 This can be any kind of jump, since we want to know if insns
3736 will be executed if the loop is executed. */
3737 && ! (JUMP_LABEL (p) == loop_top
3738 && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3739 || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3743 /* If this is a jump outside the loop, then it also doesn't
3744 matter. Check to see if the target of this branch is on the
3745 loop_number_exits_labels list. */
3747 for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
3749 label = LABEL_NEXTREF (label))
3750 if (XEXP (label, 0) == JUMP_LABEL (p))
3754 not_every_iteration = 1;
3757 else if (GET_CODE (p) == NOTE)
3759 /* At the virtual top of a converted loop, insns are again known to
3760 be executed each iteration: logically, the loop begins here
3761 even though the exit code has been duplicated. */
3762 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
3763 not_every_iteration = 0;
3764 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3766 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
3770 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3771 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3772 or not an insn is known to be executed each iteration of the
3773 loop, whether or not any iterations are known to occur.
3775 Therefore, if we have just passed a label and have no more labels
3776 between here and the test insn of the loop, we know these insns
3777 will be executed each iteration. */
3779 if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3780 && no_labels_between_p (p, loop_end))
3781 not_every_iteration = 0;
3784 /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3785 Make a sanity check against n_times_set. */
3786 for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next)
3788 if (reg_iv_type[bl->regno] != BASIC_INDUCT
3789 /* Above happens if register modified by subreg, etc. */
3790 /* Make sure it is not recognized as a basic induction var: */
3791 || VARRAY_INT (n_times_set, bl->regno) != bl->biv_count
3792 /* If never incremented, it is invariant that we decided not to
3793 move. So leave it alone. */
3794 || ! bl->incremented)
3796 if (loop_dump_stream)
3797 fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3799 (reg_iv_type[bl->regno] != BASIC_INDUCT
3800 ? "not induction variable"
3801 : (! bl->incremented ? "never incremented"
3804 reg_iv_type[bl->regno] = NOT_BASIC_INDUCT;
3811 if (loop_dump_stream)
3812 fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3816 /* Exit if there are no bivs. */
3819 /* Can still unroll the loop anyways, but indicate that there is no
3820 strength reduction info available. */
3822 unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 0);
3827 /* Find initial value for each biv by searching backwards from loop_start,
3828 halting at first label. Also record any test condition. */
3831 for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3835 if (GET_CODE (p) == CALL_INSN)
3838 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3839 || GET_CODE (p) == CALL_INSN)
3840 note_stores (PATTERN (p), record_initial);
3842 /* Record any test of a biv that branches around the loop if no store
3843 between it and the start of loop. We only care about tests with
3844 constants and registers and only certain of those. */
3845 if (GET_CODE (p) == JUMP_INSN
3846 && JUMP_LABEL (p) != 0
3847 && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3848 && (test = get_condition_for_loop (p)) != 0
3849 && GET_CODE (XEXP (test, 0)) == REG
3850 && REGNO (XEXP (test, 0)) < max_reg_before_loop
3851 && (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3852 && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3853 && bl->init_insn == 0)
3855 /* If an NE test, we have an initial value! */
3856 if (GET_CODE (test) == NE)
3859 bl->init_set = gen_rtx_SET (VOIDmode,
3860 XEXP (test, 0), XEXP (test, 1));
3863 bl->initial_test = test;
3867 /* Look at the each biv and see if we can say anything better about its
3868 initial value from any initializing insns set up above. (This is done
3869 in two passes to avoid missing SETs in a PARALLEL.) */
3870 for (bl = loop_iv_list; bl; bl = bl->next)
3875 if (! bl->init_insn)
3878 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3879 is a constant, use the value of that. */
3880 if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
3881 && CONSTANT_P (XEXP (note, 0)))
3882 || ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
3883 && CONSTANT_P (XEXP (note, 0))))
3884 src = XEXP (note, 0);
3886 src = SET_SRC (bl->init_set);
3888 if (loop_dump_stream)
3889 fprintf (loop_dump_stream,
3890 "Biv %d initialized at insn %d: initial value ",
3891 bl->regno, INSN_UID (bl->init_insn));
3893 if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
3894 || GET_MODE (src) == VOIDmode)
3895 && valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3897 bl->initial_value = src;
3899 if (loop_dump_stream)
3901 if (GET_CODE (src) == CONST_INT)
3903 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (src));
3904 fputc ('\n', loop_dump_stream);
3908 print_rtl (loop_dump_stream, src);
3909 fprintf (loop_dump_stream, "\n");
3915 /* Biv initial value is not simple move,
3916 so let it keep initial value of "itself". */
3918 if (loop_dump_stream)
3919 fprintf (loop_dump_stream, "is complex\n");
3923 /* Search the loop for general induction variables. */
3925 /* A register is a giv if: it is only set once, it is a function of a
3926 biv and a constant (or invariant), and it is not a biv. */
3928 not_every_iteration = 0;
3934 /* At end of a straight-in loop, we are done.
3935 At end of a loop entered at the bottom, scan the top. */
3936 if (p == scan_start)
3944 if (p == scan_start)
3948 /* Look for a general induction variable in a register. */
3949 if (GET_CODE (p) == INSN
3950 && (set = single_set (p))
3951 && GET_CODE (SET_DEST (set)) == REG
3952 && ! VARRAY_CHAR (may_not_optimize, REGNO (SET_DEST (set))))
3960 dest_reg = SET_DEST (set);
3961 if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
3964 if (/* SET_SRC is a giv. */
3965 (general_induction_var (SET_SRC (set), &src_reg, &add_val,
3966 &mult_val, 0, &benefit)
3967 /* Equivalent expression is a giv. */
3968 || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
3969 && general_induction_var (XEXP (regnote, 0), &src_reg,
3970 &add_val, &mult_val, 0,
3972 /* Don't try to handle any regs made by loop optimization.
3973 We have nothing on them in regno_first_uid, etc. */
3974 && REGNO (dest_reg) < max_reg_before_loop
3975 /* Don't recognize a BASIC_INDUCT_VAR here. */
3976 && dest_reg != src_reg
3977 /* This must be the only place where the register is set. */
3978 && (VARRAY_INT (n_times_set, REGNO (dest_reg)) == 1
3979 /* or all sets must be consecutive and make a giv. */
3980 || (benefit = consec_sets_giv (benefit, p,
3982 &add_val, &mult_val))))
3986 = (struct induction *) alloca (sizeof (struct induction));
3989 /* If this is a library call, increase benefit. */
3990 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
3991 benefit += libcall_benefit (p);
3993 /* Skip the consecutive insns, if there are any. */
3994 for (count = VARRAY_INT (n_times_set, REGNO (dest_reg)) - 1;
3997 /* If first insn of libcall sequence, skip to end.
3998 Do this at start of loop, since INSN is guaranteed to
4000 if (GET_CODE (p) != NOTE
4001 && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
4004 do p = NEXT_INSN (p);
4005 while (GET_CODE (p) == NOTE);
4008 record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
4009 DEST_REG, not_every_iteration, NULL_PTR, loop_start,
4015 #ifndef DONT_REDUCE_ADDR
4016 /* Look for givs which are memory addresses. */
4017 /* This resulted in worse code on a VAX 8600. I wonder if it
4019 if (GET_CODE (p) == INSN)
4020 find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
4024 /* Update the status of whether giv can derive other givs. This can
4025 change when we pass a label or an insn that updates a biv. */
4026 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4027 || GET_CODE (p) == CODE_LABEL)
4028 update_giv_derive (p);
4030 /* Past a jump, we get to insns for which we can't count
4031 on whether they will be executed during each iteration. */
4032 /* This code appears twice in strength_reduce. There is also similar
4033 code in scan_loop. */
4034 if (GET_CODE (p) == JUMP_INSN
4035 /* If we enter the loop in the middle, and scan around to the
4036 beginning, don't set not_every_iteration for that.
4037 This can be any kind of jump, since we want to know if insns
4038 will be executed if the loop is executed. */
4039 && ! (JUMP_LABEL (p) == loop_top
4040 && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
4041 || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
4045 /* If this is a jump outside the loop, then it also doesn't
4046 matter. Check to see if the target of this branch is on the
4047 loop_number_exits_labels list. */
4049 for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
4051 label = LABEL_NEXTREF (label))
4052 if (XEXP (label, 0) == JUMP_LABEL (p))
4056 not_every_iteration = 1;
4059 else if (GET_CODE (p) == NOTE)
4061 /* At the virtual top of a converted loop, insns are again known to
4062 be executed each iteration: logically, the loop begins here
4063 even though the exit code has been duplicated. */
4064 if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
4065 not_every_iteration = 0;
4066 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
4068 else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
4072 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
4073 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
4074 or not an insn is known to be executed each iteration of the
4075 loop, whether or not any iterations are known to occur.
4077 Therefore, if we have just passed a label and have no more labels
4078 between here and the test insn of the loop, we know these insns
4079 will be executed each iteration. */
4081 if (not_every_iteration && GET_CODE (p) == CODE_LABEL
4082 && no_labels_between_p (p, loop_end))
4083 not_every_iteration = 0;
4086 /* Try to calculate and save the number of loop iterations. This is
4087 set to zero if the actual number can not be calculated. This must
4088 be called after all giv's have been identified, since otherwise it may
4089 fail if the iteration variable is a giv. */
4091 loop_n_iterations = loop_iterations (loop_start, loop_end);
4093 /* Now for each giv for which we still don't know whether or not it is
4094 replaceable, check to see if it is replaceable because its final value
4095 can be calculated. This must be done after loop_iterations is called,
4096 so that final_giv_value will work correctly. */
4098 for (bl = loop_iv_list; bl; bl = bl->next)
4100 struct induction *v;
4102 for (v = bl->giv; v; v = v->next_iv)
4103 if (! v->replaceable && ! v->not_replaceable)
4104 check_final_value (v, loop_start, loop_end);
4107 /* Try to prove that the loop counter variable (if any) is always
4108 nonnegative; if so, record that fact with a REG_NONNEG note
4109 so that "decrement and branch until zero" insn can be used. */
4110 check_dbra_loop (loop_end, insn_count, loop_start);
4113 /* record loop-variables relevant for BCT optimization before unrolling
4114 the loop. Unrolling may update part of this information, and the
4115 correct data will be used for generating the BCT. */
4116 #ifdef HAVE_decrement_and_branch_on_count
4117 if (HAVE_decrement_and_branch_on_count && bct_p)
4118 analyze_loop_iterations (loop_start, loop_end);
4122 /* Create reg_map to hold substitutions for replaceable giv regs. */
4123 reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
4124 bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
4126 /* Examine each iv class for feasibility of strength reduction/induction
4127 variable elimination. */
4129 for (bl = loop_iv_list; bl; bl = bl->next)
4131 struct induction *v;
4134 rtx final_value = 0;
4136 /* Test whether it will be possible to eliminate this biv
4137 provided all givs are reduced. This is possible if either
4138 the reg is not used outside the loop, or we can compute
4139 what its final value will be.
4141 For architectures with a decrement_and_branch_until_zero insn,
4142 don't do this if we put a REG_NONNEG note on the endtest for
4145 /* Compare against bl->init_insn rather than loop_start.
4146 We aren't concerned with any uses of the biv between
4147 init_insn and loop_start since these won't be affected
4148 by the value of the biv elsewhere in the function, so
4149 long as init_insn doesn't use the biv itself.
4150 March 14, 1989 -- self@bayes.arc.nasa.gov */
4152 if ((uid_luid[REGNO_LAST_UID (bl->regno)] < INSN_LUID (loop_end)
4154 && INSN_UID (bl->init_insn) < max_uid_for_loop
4155 && uid_luid[REGNO_FIRST_UID (bl->regno)] >= INSN_LUID (bl->init_insn)
4156 #ifdef HAVE_decrement_and_branch_until_zero
4159 && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
4160 || ((final_value = final_biv_value (bl, loop_start, loop_end))
4161 #ifdef HAVE_decrement_and_branch_until_zero
4165 bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
4166 threshold, insn_count);
4169 if (loop_dump_stream)
4171 fprintf (loop_dump_stream,
4172 "Cannot eliminate biv %d.\n",
4174 fprintf (loop_dump_stream,
4175 "First use: insn %d, last use: insn %d.\n",
4176 REGNO_FIRST_UID (bl->regno),
4177 REGNO_LAST_UID (bl->regno));
4181 /* Combine all giv's for this iv_class. */
4184 /* This will be true at the end, if all givs which depend on this
4185 biv have been strength reduced.
4186 We can't (currently) eliminate the biv unless this is so. */
4189 /* Check each giv in this class to see if we will benefit by reducing
4190 it. Skip giv's combined with others. */
4191 for (v = bl->giv; v; v = v->next_iv)
4193 struct induction *tv;
4195 if (v->ignore || v->same)
4198 benefit = v->benefit;
4200 /* Reduce benefit if not replaceable, since we will insert
4201 a move-insn to replace the insn that calculates this giv.
4202 Don't do this unless the giv is a user variable, since it
4203 will often be marked non-replaceable because of the duplication
4204 of the exit code outside the loop. In such a case, the copies
4205 we insert are dead and will be deleted. So they don't have
4206 a cost. Similar situations exist. */
4207 /* ??? The new final_[bg]iv_value code does a much better job
4208 of finding replaceable giv's, and hence this code may no longer
4210 if (! v->replaceable && ! bl->eliminable
4211 && REG_USERVAR_P (v->dest_reg))
4212 benefit -= copy_cost;
4214 /* Decrease the benefit to count the add-insns that we will
4215 insert to increment the reduced reg for the giv. */
4216 benefit -= add_cost * bl->biv_count;
4218 /* Decide whether to strength-reduce this giv or to leave the code
4219 unchanged (recompute it from the biv each time it is used).
4220 This decision can be made independently for each giv. */
4223 /* Attempt to guess whether autoincrement will handle some of the
4224 new add insns; if so, increase BENEFIT (undo the subtraction of
4225 add_cost that was done above). */
4226 if (v->giv_type == DEST_ADDR
4227 && GET_CODE (v->mult_val) == CONST_INT)
4229 #if defined (HAVE_POST_INCREMENT) || defined (HAVE_PRE_INCREMENT)
4230 if (INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4231 benefit += add_cost * bl->biv_count;
4233 #if defined (HAVE_POST_DECREMENT) || defined (HAVE_PRE_DECREMENT)
4234 if (-INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
4235 benefit += add_cost * bl->biv_count;
4240 /* If an insn is not to be strength reduced, then set its ignore
4241 flag, and clear all_reduced. */
4243 /* A giv that depends on a reversed biv must be reduced if it is
4244 used after the loop exit, otherwise, it would have the wrong
4245 value after the loop exit. To make it simple, just reduce all
4246 of such giv's whether or not we know they are used after the loop
4249 if ( ! flag_reduce_all_givs && v->lifetime * threshold * benefit < insn_count
4252 if (loop_dump_stream)
4253 fprintf (loop_dump_stream,
4254 "giv of insn %d not worth while, %d vs %d.\n",
4256 v->lifetime * threshold * benefit, insn_count);
4262 /* Check that we can increment the reduced giv without a
4263 multiply insn. If not, reject it. */
4265 for (tv = bl->biv; tv; tv = tv->next_iv)
4266 if (tv->mult_val == const1_rtx
4267 && ! product_cheap_p (tv->add_val, v->mult_val))
4269 if (loop_dump_stream)
4270 fprintf (loop_dump_stream,
4271 "giv of insn %d: would need a multiply.\n",
4272 INSN_UID (v->insn));
4280 /* Reduce each giv that we decided to reduce. */
4282 for (v = bl->giv; v; v = v->next_iv)
4284 struct induction *tv;
4285 if (! v->ignore && v->same == 0)
4287 int auto_inc_opt = 0;
4289 v->new_reg = gen_reg_rtx (v->mode);
4292 /* If the target has auto-increment addressing modes, and
4293 this is an address giv, then try to put the increment
4294 immediately after its use, so that flow can create an
4295 auto-increment addressing mode. */
4296 if (v->giv_type == DEST_ADDR && bl->biv_count == 1
4297 && bl->biv->always_executed && ! bl->biv->maybe_multiple
4298 /* We don't handle reversed biv's because bl->biv->insn
4299 does not have a valid INSN_LUID. */
4301 && v->always_executed && ! v->maybe_multiple
4302 && INSN_UID (v->insn) < max_uid_for_loop)
4304 /* If other giv's have been combined with this one, then
4305 this will work only if all uses of the other giv's occur
4306 before this giv's insn. This is difficult to check.
4308 We simplify this by looking for the common case where
4309 there is one DEST_REG giv, and this giv's insn is the
4310 last use of the dest_reg of that DEST_REG giv. If the
4311 increment occurs after the address giv, then we can
4312 perform the optimization. (Otherwise, the increment
4313 would have to go before other_giv, and we would not be
4314 able to combine it with the address giv to get an
4315 auto-inc address.) */
4316 if (v->combined_with)
4318 struct induction *other_giv = 0;
4320 for (tv = bl->giv; tv; tv = tv->next_iv)
4328 if (! tv && other_giv
4329 && REGNO (other_giv->dest_reg) < max_reg_before_loop
4330 && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
4331 == INSN_UID (v->insn))
4332 && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
4335 /* Check for case where increment is before the address
4336 giv. Do this test in "loop order". */
4337 else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
4338 && (INSN_LUID (v->insn) < INSN_LUID (scan_start)
4339 || (INSN_LUID (bl->biv->insn)
4340 > INSN_LUID (scan_start))))
4341 || (INSN_LUID (v->insn) < INSN_LUID (scan_start)
4342 && (INSN_LUID (scan_start)
4343 < INSN_LUID (bl->biv->insn))))
4352 /* We can't put an insn immediately after one setting
4353 cc0, or immediately before one using cc0. */
4354 if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
4355 || (auto_inc_opt == -1
4356 && (prev = prev_nonnote_insn (v->insn)) != 0
4357 && GET_RTX_CLASS (GET_CODE (prev)) == 'i'
4358 && sets_cc0_p (PATTERN (prev))))
4364 v->auto_inc_opt = 1;
4368 /* For each place where the biv is incremented, add an insn
4369 to increment the new, reduced reg for the giv. */
4370 for (tv = bl->biv; tv; tv = tv->next_iv)
4375 insert_before = tv->insn;
4376 else if (auto_inc_opt == 1)
4377 insert_before = NEXT_INSN (v->insn);
4379 insert_before = v->insn;
4381 if (tv->mult_val == const1_rtx)
4382 emit_iv_add_mult (tv->add_val, v->mult_val,
4383 v->new_reg, v->new_reg, insert_before);
4384 else /* tv->mult_val == const0_rtx */
4385 /* A multiply is acceptable here
4386 since this is presumed to be seldom executed. */
4387 emit_iv_add_mult (tv->add_val, v->mult_val,
4388 v->add_val, v->new_reg, insert_before);
4391 /* Add code at loop start to initialize giv's reduced reg. */
4393 emit_iv_add_mult (bl->initial_value, v->mult_val,
4394 v->add_val, v->new_reg, loop_start);
4398 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4401 For each giv register that can be reduced now: if replaceable,
4402 substitute reduced reg wherever the old giv occurs;
4403 else add new move insn "giv_reg = reduced_reg".
4405 Also check for givs whose first use is their definition and whose
4406 last use is the definition of another giv. If so, it is likely
4407 dead and should not be used to eliminate a biv. */
4408 for (v = bl->giv; v; v = v->next_iv)
4410 if (v->same && v->same->ignore)
4416 if (v->giv_type == DEST_REG
4417 && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
4419 struct induction *v1;
4421 for (v1 = bl->giv; v1; v1 = v1->next_iv)
4422 if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
4426 /* Update expression if this was combined, in case other giv was
4429 v->new_reg = replace_rtx (v->new_reg,
4430 v->same->dest_reg, v->same->new_reg);
4432 if (v->giv_type == DEST_ADDR)
4433 /* Store reduced reg as the address in the memref where we found
4435 validate_change (v->insn, v->location, v->new_reg, 0);
4436 else if (v->replaceable)
4438 reg_map[REGNO (v->dest_reg)] = v->new_reg;
4441 /* I can no longer duplicate the original problem. Perhaps
4442 this is unnecessary now? */
4444 /* Replaceable; it isn't strictly necessary to delete the old
4445 insn and emit a new one, because v->dest_reg is now dead.
4447 However, especially when unrolling loops, the special
4448 handling for (set REG0 REG1) in the second cse pass may
4449 make v->dest_reg live again. To avoid this problem, emit
4450 an insn to set the original giv reg from the reduced giv.
4451 We can not delete the original insn, since it may be part
4452 of a LIBCALL, and the code in flow that eliminates dead
4453 libcalls will fail if it is deleted. */
4454 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4460 /* Not replaceable; emit an insn to set the original giv reg from
4461 the reduced giv, same as above. */
4462 emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
4466 /* When a loop is reversed, givs which depend on the reversed
4467 biv, and which are live outside the loop, must be set to their
4468 correct final value. This insn is only needed if the giv is
4469 not replaceable. The correct final value is the same as the
4470 value that the giv starts the reversed loop with. */
4471 if (bl->reversed && ! v->replaceable)
4472 emit_iv_add_mult (bl->initial_value, v->mult_val,
4473 v->add_val, v->dest_reg, end_insert_before);
4474 else if (v->final_value)
4478 /* If the loop has multiple exits, emit the insn before the
4479 loop to ensure that it will always be executed no matter
4480 how the loop exits. Otherwise, emit the insn after the loop,
4481 since this is slightly more efficient. */
4482 if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
4483 insert_before = loop_start;
4485 insert_before = end_insert_before;
4486 emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
4490 /* If the insn to set the final value of the giv was emitted
4491 before the loop, then we must delete the insn inside the loop
4492 that sets it. If this is a LIBCALL, then we must delete
4493 every insn in the libcall. Note, however, that
4494 final_giv_value will only succeed when there are multiple
4495 exits if the giv is dead at each exit, hence it does not
4496 matter that the original insn remains because it is dead
4498 /* Delete the insn inside the loop that sets the giv since
4499 the giv is now set before (or after) the loop. */
4500 delete_insn (v->insn);
4504 if (loop_dump_stream)
4506 fprintf (loop_dump_stream, "giv at %d reduced to ",
4507 INSN_UID (v->insn));
4508 print_rtl (loop_dump_stream, v->new_reg);
4509 fprintf (loop_dump_stream, "\n");
4513 /* All the givs based on the biv bl have been reduced if they
4516 /* For each giv not marked as maybe dead that has been combined with a
4517 second giv, clear any "maybe dead" mark on that second giv.
4518 v->new_reg will either be or refer to the register of the giv it
4521 Doing this clearing avoids problems in biv elimination where a
4522 giv's new_reg is a complex value that can't be put in the insn but
4523 the giv combined with (with a reg as new_reg) is marked maybe_dead.
4524 Since the register will be used in either case, we'd prefer it be
4525 used from the simpler giv. */
4527 for (v = bl->giv; v; v = v->next_iv)
4528 if (! v->maybe_dead && v->same)
4529 v->same->maybe_dead = 0;
4531 /* Try to eliminate the biv, if it is a candidate.
4532 This won't work if ! all_reduced,
4533 since the givs we planned to use might not have been reduced.
4535 We have to be careful that we didn't initially think we could eliminate
4536 this biv because of a giv that we now think may be dead and shouldn't
4537 be used as a biv replacement.
4539 Also, there is the possibility that we may have a giv that looks
4540 like it can be used to eliminate a biv, but the resulting insn
4541 isn't valid. This can happen, for example, on the 88k, where a
4542 JUMP_INSN can compare a register only with zero. Attempts to
4543 replace it with a compare with a constant will fail.
4545 Note that in cases where this call fails, we may have replaced some
4546 of the occurrences of the biv with a giv, but no harm was done in
4547 doing so in the rare cases where it can occur. */
4549 if (all_reduced == 1 && bl->eliminable
4550 && maybe_eliminate_biv (bl, loop_start, end, 1,
4551 threshold, insn_count))
4554 /* ?? If we created a new test to bypass the loop entirely,
4555 or otherwise drop straight in, based on this test, then
4556 we might want to rewrite it also. This way some later
4557 pass has more hope of removing the initialization of this
4560 /* If final_value != 0, then the biv may be used after loop end
4561 and we must emit an insn to set it just in case.
4563 Reversed bivs already have an insn after the loop setting their
4564 value, so we don't need another one. We can't calculate the
4565 proper final value for such a biv here anyways. */
4566 if (final_value != 0 && ! bl->reversed)
4570 /* If the loop has multiple exits, emit the insn before the
4571 loop to ensure that it will always be executed no matter
4572 how the loop exits. Otherwise, emit the insn after the
4573 loop, since this is slightly more efficient. */
4574 if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
4575 insert_before = loop_start;
4577 insert_before = end_insert_before;
4579 emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
4584 /* Delete all of the instructions inside the loop which set
4585 the biv, as they are all dead. If is safe to delete them,
4586 because an insn setting a biv will never be part of a libcall. */
4587 /* However, deleting them will invalidate the regno_last_uid info,
4588 so keeping them around is more convenient. Final_biv_value
4589 will only succeed when there are multiple exits if the biv
4590 is dead at each exit, hence it does not matter that the original
4591 insn remains, because it is dead anyways. */
4592 for (v = bl->biv; v; v = v->next_iv)
4593 delete_insn (v->insn);
4596 if (loop_dump_stream)
4597 fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
4602 /* Go through all the instructions in the loop, making all the
4603 register substitutions scheduled in REG_MAP. */
4605 for (p = loop_start; p != end; p = NEXT_INSN (p))
4606 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4607 || GET_CODE (p) == CALL_INSN)
4609 replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0);
4610 replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0);
4614 /* Unroll loops from within strength reduction so that we can use the
4615 induction variable information that strength_reduce has already
4619 unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
4622 /* instrument the loop with bct insn */
4623 #ifdef HAVE_decrement_and_branch_on_count
4624 if (HAVE_decrement_and_branch_on_count && bct_p)
4625 insert_bct (loop_start, loop_end);
4629 if (loop_dump_stream)
4630 fprintf (loop_dump_stream, "\n");
4633 /* Return 1 if X is a valid source for an initial value (or as value being
4634 compared against in an initial test).
4636 X must be either a register or constant and must not be clobbered between
4637 the current insn and the start of the loop.
4639 INSN is the insn containing X. */
4642 valid_initial_value_p (x, insn, call_seen, loop_start)
4651 /* Only consider pseudos we know about initialized in insns whose luids
4653 if (GET_CODE (x) != REG
4654 || REGNO (x) >= max_reg_before_loop)
4657 /* Don't use call-clobbered registers across a call which clobbers it. On
4658 some machines, don't use any hard registers at all. */
4659 if (REGNO (x) < FIRST_PSEUDO_REGISTER
4660 && (SMALL_REGISTER_CLASSES
4661 || (call_used_regs[REGNO (x)] && call_seen)))
4664 /* Don't use registers that have been clobbered before the start of the
4666 if (reg_set_between_p (x, insn, loop_start))
4672 /* Scan X for memory refs and check each memory address
4673 as a possible giv. INSN is the insn whose pattern X comes from.
4674 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4675 every loop iteration. */
4678 find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
4681 int not_every_iteration;
4682 rtx loop_start, loop_end;
4685 register enum rtx_code code;
4691 code = GET_CODE (x);
4715 /* This code used to disable creating GIVs with mult_val == 1 and
4716 add_val == 0. However, this leads to lost optimizations when
4717 it comes time to combine a set of related DEST_ADDR GIVs, since
4718 this one would not be seen. */
4720 if (general_induction_var (XEXP (x, 0), &src_reg, &add_val,
4721 &mult_val, 1, &benefit))
4723 /* Found one; record it. */
4725 = (struct induction *) oballoc (sizeof (struct induction));
4727 record_giv (v, insn, src_reg, addr_placeholder, mult_val,
4728 add_val, benefit, DEST_ADDR, not_every_iteration,
4729 &XEXP (x, 0), loop_start, loop_end);
4731 v->mem_mode = GET_MODE (x);
4740 /* Recursively scan the subexpressions for other mem refs. */
4742 fmt = GET_RTX_FORMAT (code);
4743 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4745 find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
4747 else if (fmt[i] == 'E')
4748 for (j = 0; j < XVECLEN (x, i); j++)
4749 find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
4750 loop_start, loop_end);
4753 /* Fill in the data about one biv update.
4754 V is the `struct induction' in which we record the biv. (It is
4755 allocated by the caller, with alloca.)
4756 INSN is the insn that sets it.
4757 DEST_REG is the biv's reg.
4759 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4760 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4761 being set to INC_VAL.
4763 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4764 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4765 can be executed more than once per iteration. If MAYBE_MULTIPLE
4766 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4767 executed exactly once per iteration. */
4770 record_biv (v, insn, dest_reg, inc_val, mult_val,
4771 not_every_iteration, maybe_multiple)
4772 struct induction *v;
4777 int not_every_iteration;
4780 struct iv_class *bl;
4783 v->src_reg = dest_reg;
4784 v->dest_reg = dest_reg;
4785 v->mult_val = mult_val;
4786 v->add_val = inc_val;
4787 v->mode = GET_MODE (dest_reg);
4788 v->always_computable = ! not_every_iteration;
4789 v->always_executed = ! not_every_iteration;
4790 v->maybe_multiple = maybe_multiple;
4792 /* Add this to the reg's iv_class, creating a class
4793 if this is the first incrementation of the reg. */
4795 bl = reg_biv_class[REGNO (dest_reg)];
4798 /* Create and initialize new iv_class. */
4800 bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
4802 bl->regno = REGNO (dest_reg);
4808 /* Set initial value to the reg itself. */
4809 bl->initial_value = dest_reg;
4810 /* We haven't seen the initializing insn yet */
4813 bl->initial_test = 0;
4814 bl->incremented = 0;
4818 bl->total_benefit = 0;
4820 /* Add this class to loop_iv_list. */
4821 bl->next = loop_iv_list;
4824 /* Put it in the array of biv register classes. */
4825 reg_biv_class[REGNO (dest_reg)] = bl;
4828 /* Update IV_CLASS entry for this biv. */
4829 v->next_iv = bl->biv;
4832 if (mult_val == const1_rtx)
4833 bl->incremented = 1;
4835 if (loop_dump_stream)
4837 fprintf (loop_dump_stream,
4838 "Insn %d: possible biv, reg %d,",
4839 INSN_UID (insn), REGNO (dest_reg));
4840 if (GET_CODE (inc_val) == CONST_INT)
4842 fprintf (loop_dump_stream, " const =");
4843 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
4844 fputc ('\n', loop_dump_stream);
4848 fprintf (loop_dump_stream, " const = ");
4849 print_rtl (loop_dump_stream, inc_val);
4850 fprintf (loop_dump_stream, "\n");
4855 /* Fill in the data about one giv.
4856 V is the `struct induction' in which we record the giv. (It is
4857 allocated by the caller, with alloca.)
4858 INSN is the insn that sets it.
4859 BENEFIT estimates the savings from deleting this insn.
4860 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4861 into a register or is used as a memory address.
4863 SRC_REG is the biv reg which the giv is computed from.
4864 DEST_REG is the giv's reg (if the giv is stored in a reg).
4865 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4866 LOCATION points to the place where this giv's value appears in INSN. */
4869 record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
4870 type, not_every_iteration, location, loop_start, loop_end)
4871 struct induction *v;
4875 rtx mult_val, add_val;
4878 int not_every_iteration;
4880 rtx loop_start, loop_end;
4882 struct induction *b;
4883 struct iv_class *bl;
4884 rtx set = single_set (insn);
4887 v->src_reg = src_reg;
4889 v->dest_reg = dest_reg;
4890 v->mult_val = mult_val;
4891 v->add_val = add_val;
4892 v->benefit = benefit;
4893 v->location = location;
4895 v->combined_with = 0;
4896 v->maybe_multiple = 0;
4898 v->derive_adjustment = 0;
4904 v->auto_inc_opt = 0;
4908 /* The v->always_computable field is used in update_giv_derive, to
4909 determine whether a giv can be used to derive another giv. For a
4910 DEST_REG giv, INSN computes a new value for the giv, so its value
4911 isn't computable if INSN insn't executed every iteration.
4912 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4913 it does not compute a new value. Hence the value is always computable
4914 regardless of whether INSN is executed each iteration. */
4916 if (type == DEST_ADDR)
4917 v->always_computable = 1;
4919 v->always_computable = ! not_every_iteration;
4921 v->always_executed = ! not_every_iteration;
4923 if (type == DEST_ADDR)
4925 v->mode = GET_MODE (*location);
4929 else /* type == DEST_REG */
4931 v->mode = GET_MODE (SET_DEST (set));
4933 v->lifetime = (uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
4934 - uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))]);
4936 v->times_used = VARRAY_INT (n_times_used, REGNO (dest_reg));
4938 /* If the lifetime is zero, it means that this register is
4939 really a dead store. So mark this as a giv that can be
4940 ignored. This will not prevent the biv from being eliminated. */
4941 if (v->lifetime == 0)
4944 reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
4945 reg_iv_info[REGNO (dest_reg)] = v;
4948 /* Add the giv to the class of givs computed from one biv. */
4950 bl = reg_biv_class[REGNO (src_reg)];
4953 v->next_iv = bl->giv;
4955 /* Don't count DEST_ADDR. This is supposed to count the number of
4956 insns that calculate givs. */
4957 if (type == DEST_REG)
4959 bl->total_benefit += benefit;
4962 /* Fatal error, biv missing for this giv? */
4965 if (type == DEST_ADDR)
4969 /* The giv can be replaced outright by the reduced register only if all
4970 of the following conditions are true:
4971 - the insn that sets the giv is always executed on any iteration
4972 on which the giv is used at all
4973 (there are two ways to deduce this:
4974 either the insn is executed on every iteration,
4975 or all uses follow that insn in the same basic block),
4976 - the giv is not used outside the loop
4977 - no assignments to the biv occur during the giv's lifetime. */
4979 if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
4980 /* Previous line always fails if INSN was moved by loop opt. */
4981 && uid_luid[REGNO_LAST_UID (REGNO (dest_reg))] < INSN_LUID (loop_end)
4982 && (! not_every_iteration
4983 || last_use_this_basic_block (dest_reg, insn)))
4985 /* Now check that there are no assignments to the biv within the
4986 giv's lifetime. This requires two separate checks. */
4988 /* Check each biv update, and fail if any are between the first
4989 and last use of the giv.
4991 If this loop contains an inner loop that was unrolled, then
4992 the insn modifying the biv may have been emitted by the loop
4993 unrolling code, and hence does not have a valid luid. Just
4994 mark the biv as not replaceable in this case. It is not very
4995 useful as a biv, because it is used in two different loops.
4996 It is very unlikely that we would be able to optimize the giv
4997 using this biv anyways. */
5000 for (b = bl->biv; b; b = b->next_iv)
5002 if (INSN_UID (b->insn) >= max_uid_for_loop
5003 || ((uid_luid[INSN_UID (b->insn)]
5004 >= uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))])
5005 && (uid_luid[INSN_UID (b->insn)]
5006 <= uid_luid[REGNO_LAST_UID (REGNO (dest_reg))])))
5009 v->not_replaceable = 1;
5014 /* If there are any backwards branches that go from after the
5015 biv update to before it, then this giv is not replaceable. */
5017 for (b = bl->biv; b; b = b->next_iv)
5018 if (back_branch_in_range_p (b->insn, loop_start, loop_end))
5021 v->not_replaceable = 1;
5027 /* May still be replaceable, we don't have enough info here to
5030 v->not_replaceable = 0;
5034 /* Record whether the add_val contains a const_int, for later use by
5039 v->no_const_addval = 1;
5040 if (tem == const0_rtx)
5042 else if (GET_CODE (tem) == CONST_INT)
5043 v->no_const_addval = 0;
5044 else if (GET_CODE (tem) == PLUS)
5048 if (GET_CODE (XEXP (tem, 0)) == PLUS)
5049 tem = XEXP (tem, 0);
5050 else if (GET_CODE (XEXP (tem, 1)) == PLUS)
5051 tem = XEXP (tem, 1);
5055 if (GET_CODE (XEXP (tem, 1)) == CONST_INT)
5056 v->no_const_addval = 0;
5060 if (loop_dump_stream)
5062 if (type == DEST_REG)
5063 fprintf (loop_dump_stream, "Insn %d: giv reg %d",
5064 INSN_UID (insn), REGNO (dest_reg));
5066 fprintf (loop_dump_stream, "Insn %d: dest address",
5069 fprintf (loop_dump_stream, " src reg %d benefit %d",
5070 REGNO (src_reg), v->benefit);
5071 fprintf (loop_dump_stream, " used %d lifetime %d",
5072 v->times_used, v->lifetime);
5075 fprintf (loop_dump_stream, " replaceable");
5077 if (v->no_const_addval)
5078 fprintf (loop_dump_stream, " ncav");
5080 if (GET_CODE (mult_val) == CONST_INT)
5082 fprintf (loop_dump_stream, " mult ");
5083 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
5087 fprintf (loop_dump_stream, " mult ");
5088 print_rtl (loop_dump_stream, mult_val);
5091 if (GET_CODE (add_val) == CONST_INT)
5093 fprintf (loop_dump_stream, " add ");
5094 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
5098 fprintf (loop_dump_stream, " add ");
5099 print_rtl (loop_dump_stream, add_val);
5103 if (loop_dump_stream)
5104 fprintf (loop_dump_stream, "\n");
5109 /* All this does is determine whether a giv can be made replaceable because
5110 its final value can be calculated. This code can not be part of record_giv
5111 above, because final_giv_value requires that the number of loop iterations
5112 be known, and that can not be accurately calculated until after all givs
5113 have been identified. */
5116 check_final_value (v, loop_start, loop_end)
5117 struct induction *v;
5118 rtx loop_start, loop_end;
5120 struct iv_class *bl;
5121 rtx final_value = 0;
5123 bl = reg_biv_class[REGNO (v->src_reg)];
5125 /* DEST_ADDR givs will never reach here, because they are always marked
5126 replaceable above in record_giv. */
5128 /* The giv can be replaced outright by the reduced register only if all
5129 of the following conditions are true:
5130 - the insn that sets the giv is always executed on any iteration
5131 on which the giv is used at all
5132 (there are two ways to deduce this:
5133 either the insn is executed on every iteration,
5134 or all uses follow that insn in the same basic block),
5135 - its final value can be calculated (this condition is different
5136 than the one above in record_giv)
5137 - no assignments to the biv occur during the giv's lifetime. */
5140 /* This is only called now when replaceable is known to be false. */
5141 /* Clear replaceable, so that it won't confuse final_giv_value. */
5145 if ((final_value = final_giv_value (v, loop_start, loop_end))
5146 && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
5148 int biv_increment_seen = 0;
5154 /* When trying to determine whether or not a biv increment occurs
5155 during the lifetime of the giv, we can ignore uses of the variable
5156 outside the loop because final_value is true. Hence we can not
5157 use regno_last_uid and regno_first_uid as above in record_giv. */
5159 /* Search the loop to determine whether any assignments to the
5160 biv occur during the giv's lifetime. Start with the insn
5161 that sets the giv, and search around the loop until we come
5162 back to that insn again.
5164 Also fail if there is a jump within the giv's lifetime that jumps
5165 to somewhere outside the lifetime but still within the loop. This
5166 catches spaghetti code where the execution order is not linear, and
5167 hence the above test fails. Here we assume that the giv lifetime
5168 does not extend from one iteration of the loop to the next, so as
5169 to make the test easier. Since the lifetime isn't known yet,
5170 this requires two loops. See also record_giv above. */
5172 last_giv_use = v->insn;
5178 p = NEXT_INSN (loop_start);
5182 if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
5183 || GET_CODE (p) == CALL_INSN)
5185 if (biv_increment_seen)
5187 if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5190 v->not_replaceable = 1;
5194 else if (reg_set_p (v->src_reg, PATTERN (p)))
5195 biv_increment_seen = 1;
5196 else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
5201 /* Now that the lifetime of the giv is known, check for branches
5202 from within the lifetime to outside the lifetime if it is still
5212 p = NEXT_INSN (loop_start);
5213 if (p == last_giv_use)
5216 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
5217 && LABEL_NAME (JUMP_LABEL (p))
5218 && ((INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop)
5219 || (INSN_UID (v->insn) >= max_uid_for_loop)
5220 || (INSN_UID (last_giv_use) >= max_uid_for_loop)
5221 || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
5222 && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
5223 || (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
5224 && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
5227 v->not_replaceable = 1;
5229 if (loop_dump_stream)
5230 fprintf (loop_dump_stream,
5231 "Found branch outside giv lifetime.\n");
5238 /* If it is replaceable, then save the final value. */
5240 v->final_value = final_value;
5243 if (loop_dump_stream && v->replaceable)
5244 fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
5245 INSN_UID (v->insn), REGNO (v->dest_reg));
5248 /* Update the status of whether a giv can derive other givs.
5250 We need to do something special if there is or may be an update to the biv
5251 between the time the giv is defined and the time it is used to derive
5254 In addition, a giv that is only conditionally set is not allowed to
5255 derive another giv once a label has been passed.
5257 The cases we look at are when a label or an update to a biv is passed. */
5260 update_giv_derive (p)
5263 struct iv_class *bl;
5264 struct induction *biv, *giv;
5268 /* Search all IV classes, then all bivs, and finally all givs.
5270 There are three cases we are concerned with. First we have the situation
5271 of a giv that is only updated conditionally. In that case, it may not
5272 derive any givs after a label is passed.
5274 The second case is when a biv update occurs, or may occur, after the
5275 definition of a giv. For certain biv updates (see below) that are
5276 known to occur between the giv definition and use, we can adjust the
5277 giv definition. For others, or when the biv update is conditional,
5278 we must prevent the giv from deriving any other givs. There are two
5279 sub-cases within this case.
5281 If this is a label, we are concerned with any biv update that is done
5282 conditionally, since it may be done after the giv is defined followed by
5283 a branch here (actually, we need to pass both a jump and a label, but
5284 this extra tracking doesn't seem worth it).
5286 If this is a jump, we are concerned about any biv update that may be
5287 executed multiple times. We are actually only concerned about
5288 backward jumps, but it is probably not worth performing the test
5289 on the jump again here.
5291 If this is a biv update, we must adjust the giv status to show that a
5292 subsequent biv update was performed. If this adjustment cannot be done,
5293 the giv cannot derive further givs. */
5295 for (bl = loop_iv_list; bl; bl = bl->next)
5296 for (biv = bl->biv; biv; biv = biv->next_iv)
5297 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
5300 for (giv = bl->giv; giv; giv = giv->next_iv)
5302 /* If cant_derive is already true, there is no point in
5303 checking all of these conditions again. */
5304 if (giv->cant_derive)
5307 /* If this giv is conditionally set and we have passed a label,
5308 it cannot derive anything. */
5309 if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
5310 giv->cant_derive = 1;
5312 /* Skip givs that have mult_val == 0, since
5313 they are really invariants. Also skip those that are
5314 replaceable, since we know their lifetime doesn't contain
5316 else if (giv->mult_val == const0_rtx || giv->replaceable)
5319 /* The only way we can allow this giv to derive another
5320 is if this is a biv increment and we can form the product
5321 of biv->add_val and giv->mult_val. In this case, we will
5322 be able to compute a compensation. */
5323 else if (biv->insn == p)
5327 if (biv->mult_val == const1_rtx)
5328 tem = simplify_giv_expr (gen_rtx_MULT (giv->mode,
5333 if (tem && giv->derive_adjustment)
5334 tem = simplify_giv_expr (gen_rtx_PLUS (giv->mode, tem,
5335 giv->derive_adjustment),
5338 giv->derive_adjustment = tem;
5340 giv->cant_derive = 1;
5342 else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
5343 || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
5344 giv->cant_derive = 1;
5349 /* Check whether an insn is an increment legitimate for a basic induction var.
5350 X is the source of insn P, or a part of it.
5351 MODE is the mode in which X should be interpreted.
5353 DEST_REG is the putative biv, also the destination of the insn.
5354 We accept patterns of these forms:
5355 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5356 REG = INVARIANT + REG
5358 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5359 and store the additive term into *INC_VAL.
5361 If X is an assignment of an invariant into DEST_REG, we set
5362 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5364 We also want to detect a BIV when it corresponds to a variable
5365 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5366 of the variable may be a PLUS that adds a SUBREG of that variable to
5367 an invariant and then sign- or zero-extends the result of the PLUS
5370 Most GIVs in such cases will be in the promoted mode, since that is the
5371 probably the natural computation mode (and almost certainly the mode
5372 used for addresses) on the machine. So we view the pseudo-reg containing
5373 the variable as the BIV, as if it were simply incremented.
5375 Note that treating the entire pseudo as a BIV will result in making
5376 simple increments to any GIVs based on it. However, if the variable
5377 overflows in its declared mode but not its promoted mode, the result will
5378 be incorrect. This is acceptable if the variable is signed, since
5379 overflows in such cases are undefined, but not if it is unsigned, since
5380 those overflows are defined. So we only check for SIGN_EXTEND and
5383 If we cannot find a biv, we return 0. */
5386 basic_induction_var (x, mode, dest_reg, p, inc_val, mult_val)
5388 enum machine_mode mode;
5394 register enum rtx_code code;
5398 code = GET_CODE (x);
5402 if (rtx_equal_p (XEXP (x, 0), dest_reg)
5403 || (GET_CODE (XEXP (x, 0)) == SUBREG
5404 && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
5405 && SUBREG_REG (XEXP (x, 0)) == dest_reg))
5407 else if (rtx_equal_p (XEXP (x, 1), dest_reg)
5408 || (GET_CODE (XEXP (x, 1)) == SUBREG
5409 && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
5410 && SUBREG_REG (XEXP (x, 1)) == dest_reg))
5415 if (invariant_p (arg) != 1)
5418 *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
5419 *mult_val = const1_rtx;
5423 /* If this is a SUBREG for a promoted variable, check the inner
5425 if (SUBREG_PROMOTED_VAR_P (x))
5426 return basic_induction_var (SUBREG_REG (x), GET_MODE (SUBREG_REG (x)),
5427 dest_reg, p, inc_val, mult_val);
5431 /* If this register is assigned in a previous insn, look at its
5432 source, but don't go outside the loop or past a label. */
5438 insn = PREV_INSN (insn);
5439 } while (insn && GET_CODE (insn) == NOTE
5440 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5444 set = single_set (insn);
5448 if ((SET_DEST (set) == x
5449 || (GET_CODE (SET_DEST (set)) == SUBREG
5450 && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
5452 && SUBREG_REG (SET_DEST (set)) == x))
5453 && basic_induction_var (SET_SRC (set),
5454 (GET_MODE (SET_SRC (set)) == VOIDmode
5456 : GET_MODE (SET_SRC (set))),
5461 /* ... fall through ... */
5463 /* Can accept constant setting of biv only when inside inner most loop.
5464 Otherwise, a biv of an inner loop may be incorrectly recognized
5465 as a biv of the outer loop,
5466 causing code to be moved INTO the inner loop. */
5468 if (invariant_p (x) != 1)
5473 /* convert_modes aborts if we try to convert to or from CCmode, so just
5474 exclude that case. It is very unlikely that a condition code value
5475 would be a useful iterator anyways. */
5476 if (loops_enclosed == 1
5477 && GET_MODE_CLASS (mode) != MODE_CC
5478 && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
5480 /* Possible bug here? Perhaps we don't know the mode of X. */
5481 *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
5482 *mult_val = const0_rtx;
5489 return basic_induction_var (XEXP (x, 0), GET_MODE (XEXP (x, 0)),
5490 dest_reg, p, inc_val, mult_val);
5493 /* Similar, since this can be a sign extension. */
5494 for (insn = PREV_INSN (p);
5495 (insn && GET_CODE (insn) == NOTE
5496 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
5497 insn = PREV_INSN (insn))
5501 set = single_set (insn);
5503 if (set && SET_DEST (set) == XEXP (x, 0)
5504 && GET_CODE (XEXP (x, 1)) == CONST_INT
5505 && INTVAL (XEXP (x, 1)) >= 0
5506 && GET_CODE (SET_SRC (set)) == ASHIFT
5507 && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
5508 return basic_induction_var (XEXP (SET_SRC (set), 0),
5509 GET_MODE (XEXP (x, 0)),
5510 dest_reg, insn, inc_val, mult_val);
5518 /* A general induction variable (giv) is any quantity that is a linear
5519 function of a basic induction variable,
5520 i.e. giv = biv * mult_val + add_val.
5521 The coefficients can be any loop invariant quantity.
5522 A giv need not be computed directly from the biv;
5523 it can be computed by way of other givs. */
5525 /* Determine whether X computes a giv.
5526 If it does, return a nonzero value
5527 which is the benefit from eliminating the computation of X;
5528 set *SRC_REG to the register of the biv that it is computed from;
5529 set *ADD_VAL and *MULT_VAL to the coefficients,
5530 such that the value of X is biv * mult + add; */
5533 general_induction_var (x, src_reg, add_val, mult_val, is_addr, pbenefit)
5544 /* If this is an invariant, forget it, it isn't a giv. */
5545 if (invariant_p (x) == 1)
5548 /* See if the expression could be a giv and get its form.
5549 Mark our place on the obstack in case we don't find a giv. */
5550 storage = (char *) oballoc (0);
5552 x = simplify_giv_expr (x, pbenefit);
5559 switch (GET_CODE (x))
5563 /* Since this is now an invariant and wasn't before, it must be a giv
5564 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5566 *src_reg = loop_iv_list->biv->dest_reg;
5567 *mult_val = const0_rtx;
5572 /* This is equivalent to a BIV. */
5574 *mult_val = const1_rtx;
5575 *add_val = const0_rtx;
5579 /* Either (plus (biv) (invar)) or
5580 (plus (mult (biv) (invar_1)) (invar_2)). */
5581 if (GET_CODE (XEXP (x, 0)) == MULT)
5583 *src_reg = XEXP (XEXP (x, 0), 0);
5584 *mult_val = XEXP (XEXP (x, 0), 1);
5588 *src_reg = XEXP (x, 0);
5589 *mult_val = const1_rtx;
5591 *add_val = XEXP (x, 1);
5595 /* ADD_VAL is zero. */
5596 *src_reg = XEXP (x, 0);
5597 *mult_val = XEXP (x, 1);
5598 *add_val = const0_rtx;
5605 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5606 unless they are CONST_INT). */
5607 if (GET_CODE (*add_val) == USE)
5608 *add_val = XEXP (*add_val, 0);
5609 if (GET_CODE (*mult_val) == USE)
5610 *mult_val = XEXP (*mult_val, 0);
5615 *pbenefit += ADDRESS_COST (orig_x) - reg_address_cost;
5617 *pbenefit += rtx_cost (orig_x, MEM) - reg_address_cost;
5621 *pbenefit += rtx_cost (orig_x, SET);
5623 /* Always return true if this is a giv so it will be detected as such,
5624 even if the benefit is zero or negative. This allows elimination
5625 of bivs that might otherwise not be eliminated. */
5629 /* Given an expression, X, try to form it as a linear function of a biv.
5630 We will canonicalize it to be of the form
5631 (plus (mult (BIV) (invar_1))
5633 with possible degeneracies.
5635 The invariant expressions must each be of a form that can be used as a
5636 machine operand. We surround then with a USE rtx (a hack, but localized
5637 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5638 routine; it is the caller's responsibility to strip them.
5640 If no such canonicalization is possible (i.e., two biv's are used or an
5641 expression that is neither invariant nor a biv or giv), this routine
5644 For a non-zero return, the result will have a code of CONST_INT, USE,
5645 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5647 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5649 static rtx sge_plus PROTO ((enum machine_mode, rtx, rtx));
5650 static rtx sge_plus_constant PROTO ((rtx, rtx));
5653 simplify_giv_expr (x, benefit)
5657 enum machine_mode mode = GET_MODE (x);
5661 /* If this is not an integer mode, or if we cannot do arithmetic in this
5662 mode, this can't be a giv. */
5663 if (mode != VOIDmode
5664 && (GET_MODE_CLASS (mode) != MODE_INT
5665 || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
5668 switch (GET_CODE (x))
5671 arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
5672 arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
5673 if (arg0 == 0 || arg1 == 0)
5676 /* Put constant last, CONST_INT last if both constant. */
5677 if ((GET_CODE (arg0) == USE
5678 || GET_CODE (arg0) == CONST_INT)
5679 && ! ((GET_CODE (arg0) == USE
5680 && GET_CODE (arg1) == USE)
5681 || GET_CODE (arg1) == CONST_INT))
5682 tem = arg0, arg0 = arg1, arg1 = tem;
5684 /* Handle addition of zero, then addition of an invariant. */
5685 if (arg1 == const0_rtx)
5687 else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
5688 switch (GET_CODE (arg0))
5692 /* Adding two invariants must result in an invariant, so enclose
5693 addition operation inside a USE and return it. */
5694 if (GET_CODE (arg0) == USE)
5695 arg0 = XEXP (arg0, 0);
5696 if (GET_CODE (arg1) == USE)
5697 arg1 = XEXP (arg1, 0);
5699 if (GET_CODE (arg0) == CONST_INT)
5700 tem = arg0, arg0 = arg1, arg1 = tem;
5701 if (GET_CODE (arg1) == CONST_INT)
5702 tem = sge_plus_constant (arg0, arg1);
5704 tem = sge_plus (mode, arg0, arg1);
5706 if (GET_CODE (tem) != CONST_INT)
5707 tem = gen_rtx_USE (mode, tem);
5712 /* biv + invar or mult + invar. Return sum. */
5713 return gen_rtx_PLUS (mode, arg0, arg1);
5716 /* (a + invar_1) + invar_2. Associate. */
5717 return simplify_giv_expr (
5718 gen_rtx_PLUS (mode, XEXP (arg0, 0),
5719 gen_rtx_PLUS (mode, XEXP (arg0, 1), arg1)),
5726 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5727 MULT to reduce cases. */
5728 if (GET_CODE (arg0) == REG)
5729 arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
5730 if (GET_CODE (arg1) == REG)
5731 arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
5733 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5734 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5735 Recurse to associate the second PLUS. */
5736 if (GET_CODE (arg1) == MULT)
5737 tem = arg0, arg0 = arg1, arg1 = tem;
5739 if (GET_CODE (arg1) == PLUS)
5740 return simplify_giv_expr (gen_rtx_PLUS (mode,
5741 gen_rtx_PLUS (mode, arg0,
5746 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5747 if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5750 if (!rtx_equal_p (arg0, arg1))
5753 return simplify_giv_expr (gen_rtx_MULT (mode,
5761 /* Handle "a - b" as "a + b * (-1)". */
5762 return simplify_giv_expr (gen_rtx_PLUS (mode,
5764 gen_rtx_MULT (mode, XEXP (x, 1),
5769 arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
5770 arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
5771 if (arg0 == 0 || arg1 == 0)
5774 /* Put constant last, CONST_INT last if both constant. */
5775 if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5776 && GET_CODE (arg1) != CONST_INT)
5777 tem = arg0, arg0 = arg1, arg1 = tem;
5779 /* If second argument is not now constant, not giv. */
5780 if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5783 /* Handle multiply by 0 or 1. */
5784 if (arg1 == const0_rtx)
5787 else if (arg1 == const1_rtx)
5790 switch (GET_CODE (arg0))
5793 /* biv * invar. Done. */
5794 return gen_rtx_MULT (mode, arg0, arg1);
5797 /* Product of two constants. */
5798 return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
5801 /* invar * invar. It is a giv, but very few of these will
5802 actually pay off, so limit to simple registers. */
5803 if (GET_CODE (arg1) != CONST_INT)
5806 arg0 = XEXP (arg0, 0);
5807 if (GET_CODE (arg0) == REG)
5808 tem = gen_rtx_MULT (mode, arg0, arg1);
5809 else if (GET_CODE (arg0) == MULT
5810 && GET_CODE (XEXP (arg0, 0)) == REG
5811 && GET_CODE (XEXP (arg0, 1)) == CONST_INT)
5813 tem = gen_rtx_MULT (mode, XEXP (arg0, 0),
5814 GEN_INT (INTVAL (XEXP (arg0, 1))
5819 return gen_rtx_USE (mode, tem);
5822 /* (a * invar_1) * invar_2. Associate. */
5823 return simplify_giv_expr (gen_rtx_MULT (mode, XEXP (arg0, 0),
5830 /* (a + invar_1) * invar_2. Distribute. */
5831 return simplify_giv_expr (gen_rtx_PLUS (mode,
5845 /* Shift by constant is multiply by power of two. */
5846 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5849 return simplify_giv_expr (gen_rtx_MULT (mode,
5851 GEN_INT ((HOST_WIDE_INT) 1
5852 << INTVAL (XEXP (x, 1)))),
5856 /* "-a" is "a * (-1)" */
5857 return simplify_giv_expr (gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
5861 /* "~a" is "-a - 1". Silly, but easy. */
5862 return simplify_giv_expr (gen_rtx_MINUS (mode,
5863 gen_rtx_NEG (mode, XEXP (x, 0)),
5868 /* Already in proper form for invariant. */
5872 /* If this is a new register, we can't deal with it. */
5873 if (REGNO (x) >= max_reg_before_loop)
5876 /* Check for biv or giv. */
5877 switch (reg_iv_type[REGNO (x)])
5881 case GENERAL_INDUCT:
5883 struct induction *v = reg_iv_info[REGNO (x)];
5885 /* Form expression from giv and add benefit. Ensure this giv
5886 can derive another and subtract any needed adjustment if so. */
5887 *benefit += v->benefit;
5891 tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode, v->src_reg,
5894 if (v->derive_adjustment)
5895 tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
5896 return simplify_giv_expr (tem, benefit);
5900 /* If it isn't an induction variable, and it is invariant, we
5901 may be able to simplify things further by looking through
5902 the bits we just moved outside the loop. */
5903 if (invariant_p (x) == 1)
5907 for (m = the_movables; m ; m = m->next)
5908 if (rtx_equal_p (x, m->set_dest))
5910 /* Ok, we found a match. Substitute and simplify. */
5912 /* If we match another movable, we must use that, as
5913 this one is going away. */
5915 return simplify_giv_expr (m->match->set_dest, benefit);
5917 /* If consec is non-zero, this is a member of a group of
5918 instructions that were moved together. We handle this
5919 case only to the point of seeking to the last insn and
5920 looking for a REG_EQUAL. Fail if we don't find one. */
5925 do { tem = NEXT_INSN (tem); } while (--i > 0);
5927 tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
5929 tem = XEXP (tem, 0);
5933 tem = single_set (m->insn);
5935 tem = SET_SRC (tem);
5940 /* What we are most interested in is pointer
5941 arithmetic on invariants -- only take
5942 patterns we may be able to do something with. */
5943 if (GET_CODE (tem) == PLUS
5944 || GET_CODE (tem) == MULT
5945 || GET_CODE (tem) == ASHIFT
5946 || GET_CODE (tem) == CONST_INT
5947 || GET_CODE (tem) == SYMBOL_REF)
5949 tem = simplify_giv_expr (tem, benefit);
5953 else if (GET_CODE (tem) == CONST
5954 && GET_CODE (XEXP (tem, 0)) == PLUS
5955 && GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
5956 && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
5958 tem = simplify_giv_expr (XEXP (tem, 0), benefit);
5969 /* Fall through to general case. */
5971 /* If invariant, return as USE (unless CONST_INT).
5972 Otherwise, not giv. */
5973 if (GET_CODE (x) == USE)
5976 if (invariant_p (x) == 1)
5978 if (GET_CODE (x) == CONST_INT)
5980 if (GET_CODE (x) == CONST
5981 && GET_CODE (XEXP (x, 0)) == PLUS
5982 && GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
5983 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
5985 return gen_rtx_USE (mode, x);
5992 /* This routine folds invariants such that there is only ever one
5993 CONST_INT in the summation. It is only used by simplify_giv_expr. */
5996 sge_plus_constant (x, c)
5999 if (GET_CODE (x) == CONST_INT)
6000 return GEN_INT (INTVAL (x) + INTVAL (c));
6001 else if (GET_CODE (x) != PLUS)
6002 return gen_rtx_PLUS (GET_MODE (x), x, c);
6003 else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
6005 return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
6006 GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
6008 else if (GET_CODE (XEXP (x, 0)) == PLUS
6009 || GET_CODE (XEXP (x, 1)) != PLUS)
6011 return gen_rtx_PLUS (GET_MODE (x),
6012 sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
6016 return gen_rtx_PLUS (GET_MODE (x),
6017 sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
6022 sge_plus (mode, x, y)
6023 enum machine_mode mode;
6026 while (GET_CODE (y) == PLUS)
6028 rtx a = XEXP (y, 0);
6029 if (GET_CODE (a) == CONST_INT)
6030 x = sge_plus_constant (x, a);
6032 x = gen_rtx_PLUS (mode, x, a);
6035 if (GET_CODE (y) == CONST_INT)
6036 x = sge_plus_constant (x, y);
6038 x = gen_rtx_PLUS (mode, x, y);
6042 /* Help detect a giv that is calculated by several consecutive insns;
6046 The caller has already identified the first insn P as having a giv as dest;
6047 we check that all other insns that set the same register follow
6048 immediately after P, that they alter nothing else,
6049 and that the result of the last is still a giv.
6051 The value is 0 if the reg set in P is not really a giv.
6052 Otherwise, the value is the amount gained by eliminating
6053 all the consecutive insns that compute the value.
6055 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
6056 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
6058 The coefficients of the ultimate giv value are stored in
6059 *MULT_VAL and *ADD_VAL. */
6062 consec_sets_giv (first_benefit, p, src_reg, dest_reg,
6077 /* Indicate that this is a giv so that we can update the value produced in
6078 each insn of the multi-insn sequence.
6080 This induction structure will be used only by the call to
6081 general_induction_var below, so we can allocate it on our stack.
6082 If this is a giv, our caller will replace the induct var entry with
6083 a new induction structure. */
6085 = (struct induction *) alloca (sizeof (struct induction));
6086 v->src_reg = src_reg;
6087 v->mult_val = *mult_val;
6088 v->add_val = *add_val;
6089 v->benefit = first_benefit;
6091 v->derive_adjustment = 0;
6093 reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
6094 reg_iv_info[REGNO (dest_reg)] = v;
6096 count = VARRAY_INT (n_times_set, REGNO (dest_reg)) - 1;
6101 code = GET_CODE (p);
6103 /* If libcall, skip to end of call sequence. */
6104 if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
6108 && (set = single_set (p))
6109 && GET_CODE (SET_DEST (set)) == REG
6110 && SET_DEST (set) == dest_reg
6111 && (general_induction_var (SET_SRC (set), &src_reg,
6112 add_val, mult_val, 0, &benefit)
6113 /* Giv created by equivalent expression. */
6114 || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
6115 && general_induction_var (XEXP (temp, 0), &src_reg,
6116 add_val, mult_val, 0, &benefit)))
6117 && src_reg == v->src_reg)
6119 if (find_reg_note (p, REG_RETVAL, NULL_RTX))
6120 benefit += libcall_benefit (p);
6123 v->mult_val = *mult_val;
6124 v->add_val = *add_val;
6125 v->benefit = benefit;
6127 else if (code != NOTE)
6129 /* Allow insns that set something other than this giv to a
6130 constant. Such insns are needed on machines which cannot
6131 include long constants and should not disqualify a giv. */
6133 && (set = single_set (p))
6134 && SET_DEST (set) != dest_reg
6135 && CONSTANT_P (SET_SRC (set)))
6138 reg_iv_type[REGNO (dest_reg)] = UNKNOWN_INDUCT;
6146 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6147 represented by G1. If no such expression can be found, or it is clear that
6148 it cannot possibly be a valid address, 0 is returned.
6150 To perform the computation, we note that
6153 where `v' is the biv.
6155 So G2 = (y/b) * G1 + (b - a*y/x).
6157 Note that MULT = y/x.
6159 Update: A and B are now allowed to be additive expressions such that
6160 B contains all variables in A. That is, computing B-A will not require
6161 subtracting variables. */
6164 express_from_1 (a, b, mult)
6167 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6169 if (mult == const0_rtx)
6172 /* If MULT is not 1, we cannot handle A with non-constants, since we
6173 would then be required to subtract multiples of the registers in A.
6174 This is theoretically possible, and may even apply to some Fortran
6175 constructs, but it is a lot of work and we do not attempt it here. */
6177 if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
6180 /* In general these structures are sorted top to bottom (down the PLUS
6181 chain), but not left to right across the PLUS. If B is a higher
6182 order giv than A, we can strip one level and recurse. If A is higher
6183 order, we'll eventually bail out, but won't know that until the end.
6184 If they are the same, we'll strip one level around this loop. */
6186 while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
6188 rtx ra, rb, oa, ob, tmp;
6190 ra = XEXP (a, 0), oa = XEXP (a, 1);
6191 if (GET_CODE (ra) == PLUS)
6192 tmp = ra, ra = oa, oa = tmp;
6194 rb = XEXP (b, 0), ob = XEXP (b, 1);
6195 if (GET_CODE (rb) == PLUS)
6196 tmp = rb, rb = ob, ob = tmp;
6198 if (rtx_equal_p (ra, rb))
6199 /* We matched: remove one reg completely. */
6201 else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
6202 /* An alternate match. */
6204 else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
6205 /* An alternate match. */
6209 /* Indicates an extra register in B. Strip one level from B and
6210 recurse, hoping B was the higher order expression. */
6211 ob = express_from_1 (a, ob, mult);
6214 return gen_rtx_PLUS (GET_MODE (b), rb, ob);
6218 /* Here we are at the last level of A, go through the cases hoping to
6219 get rid of everything but a constant. */
6221 if (GET_CODE (a) == PLUS)
6225 ra = XEXP (a, 0), oa = XEXP (a, 1);
6226 if (rtx_equal_p (oa, b))
6228 else if (!rtx_equal_p (ra, b))
6231 if (GET_CODE (oa) != CONST_INT)
6234 return GEN_INT (-INTVAL (oa) * INTVAL (mult));
6236 else if (GET_CODE (a) == CONST_INT)
6238 return plus_constant (b, -INTVAL (a) * INTVAL (mult));
6240 else if (GET_CODE (b) == PLUS)
6242 if (rtx_equal_p (a, XEXP (b, 0)))
6244 else if (rtx_equal_p (a, XEXP (b, 1)))
6249 else if (rtx_equal_p (a, b))
6256 express_from (g1, g2)
6257 struct induction *g1, *g2;
6261 /* The value that G1 will be multiplied by must be a constant integer. Also,
6262 the only chance we have of getting a valid address is if b*c/a (see above
6263 for notation) is also an integer. */
6264 if (GET_CODE (g1->mult_val) == CONST_INT
6265 && GET_CODE (g2->mult_val) == CONST_INT)
6267 if (g1->mult_val == const0_rtx
6268 || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
6270 mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
6272 else if (rtx_equal_p (g1->mult_val, g2->mult_val))
6276 /* ??? Find out if the one is a multiple of the other? */
6280 add = express_from_1 (g1->add_val, g2->add_val, mult);
6281 if (add == NULL_RTX)
6284 /* Form simplified final result. */
6285 if (mult == const0_rtx)
6287 else if (mult == const1_rtx)
6288 mult = g1->dest_reg;
6290 mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
6292 if (add == const0_rtx)
6295 return gen_rtx_PLUS (g2->mode, mult, add);
6298 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6299 represented by G1. This indicates that G2 should be combined with G1 and
6300 that G2 can use (either directly or via an address expression) a register
6301 used to represent G1. */
6304 combine_givs_p (g1, g2)
6305 struct induction *g1, *g2;
6307 rtx tem = express_from (g1, g2);
6309 /* If these givs are identical, they can be combined. We use the results
6310 of express_from because the addends are not in a canonical form, so
6311 rtx_equal_p is a weaker test. */
6312 if (tem == g1->dest_reg)
6314 return g1->dest_reg;
6317 /* If G2 can be expressed as a function of G1 and that function is valid
6318 as an address and no more expensive than using a register for G2,
6319 the expression of G2 in terms of G1 can be used. */
6321 && g2->giv_type == DEST_ADDR
6322 && memory_address_p (g2->mem_mode, tem)
6323 /* ??? Looses, especially with -fforce-addr, where *g2->location
6324 will always be a register, and so anything more complicated
6328 && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
6330 && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
6341 struct combine_givs_stats
6348 cmp_combine_givs_stats (x, y)
6349 struct combine_givs_stats *x, *y;
6352 d = y->total_benefit - x->total_benefit;
6353 /* Stabilize the sort. */
6355 d = x->giv_number - y->giv_number;
6359 /* If one of these givs is a DEST_REG that was only used once, by the
6360 other giv, this is actually a single use. Return 0 if this is not
6361 the case, -1 if g1 is the DEST_REG involved, and 1 if it was g2. */
6364 combine_givs_used_once (g1, g2)
6365 struct induction *g1, *g2;
6367 if (g1->giv_type == DEST_REG
6368 && VARRAY_INT (n_times_used, REGNO (g1->dest_reg)) == 1
6369 && reg_mentioned_p (g1->dest_reg, PATTERN (g2->insn)))
6372 if (g2->giv_type == DEST_REG
6373 && VARRAY_INT (n_times_used, REGNO (g2->dest_reg)) == 1
6374 && reg_mentioned_p (g2->dest_reg, PATTERN (g1->insn)))
6381 combine_givs_benefit_from (g1, g2)
6382 struct induction *g1, *g2;
6384 int tmp = combine_givs_used_once (g1, g2);
6388 return g2->benefit - g1->benefit;
6393 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6394 any other. If so, point SAME to the giv combined with and set NEW_REG to
6395 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6396 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6400 struct iv_class *bl;
6402 struct induction *g1, *g2, **giv_array;
6403 int i, j, k, giv_count;
6404 struct combine_givs_stats *stats;
6407 /* Count givs, because bl->giv_count is incorrect here. */
6409 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6414 = (struct induction **) alloca (giv_count * sizeof (struct induction *));
6416 for (g1 = bl->giv; g1; g1 = g1->next_iv)
6418 giv_array[i++] = g1;
6420 stats = (struct combine_givs_stats *) alloca (giv_count * sizeof (*stats));
6421 bzero ((char *) stats, giv_count * sizeof (*stats));
6423 can_combine = (rtx *) alloca (giv_count * giv_count * sizeof(rtx));
6424 bzero ((char *) can_combine, giv_count * giv_count * sizeof(rtx));
6426 for (i = 0; i < giv_count; i++)
6432 this_benefit = g1->benefit;
6433 /* Add an additional weight for zero addends. */
6434 if (g1->no_const_addval)
6436 for (j = 0; j < giv_count; j++)
6442 && (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
6444 can_combine[i*giv_count + j] = this_combine;
6445 this_benefit += combine_givs_benefit_from (g1, g2);
6446 /* Add an additional weight for being reused more times. */
6450 stats[i].giv_number = i;
6451 stats[i].total_benefit = this_benefit;
6454 /* Iterate, combining until we can't. */
6456 qsort (stats, giv_count, sizeof(*stats), cmp_combine_givs_stats);
6458 if (loop_dump_stream)
6460 fprintf (loop_dump_stream, "Sorted combine statistics:\n");
6461 for (k = 0; k < giv_count; k++)
6463 g1 = giv_array[stats[k].giv_number];
6464 if (!g1->combined_with && !g1->same)
6465 fprintf (loop_dump_stream, " {%d, %d}",
6466 INSN_UID (giv_array[stats[k].giv_number]->insn),
6467 stats[k].total_benefit);
6469 putc ('\n', loop_dump_stream);
6472 for (k = 0; k < giv_count; k++)
6474 int g1_add_benefit = 0;
6476 i = stats[k].giv_number;
6479 /* If it has already been combined, skip. */
6480 if (g1->combined_with || g1->same)
6483 for (j = 0; j < giv_count; j++)
6486 if (g1 != g2 && can_combine[i*giv_count + j]
6487 /* If it has already been combined, skip. */
6488 && ! g2->same && ! g2->combined_with)
6492 g2->new_reg = can_combine[i*giv_count + j];
6494 g1->combined_with = 1;
6495 if (!combine_givs_used_once (g1, g2))
6496 g1->times_used += 1;
6497 g1->lifetime += g2->lifetime;
6499 g1_add_benefit += combine_givs_benefit_from (g1, g2);
6501 /* ??? The new final_[bg]iv_value code does a much better job
6502 of finding replaceable giv's, and hence this code may no
6503 longer be necessary. */
6504 if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
6505 g1_add_benefit -= copy_cost;
6507 /* To help optimize the next set of combinations, remove
6508 this giv from the benefits of other potential mates. */
6509 for (l = 0; l < giv_count; ++l)
6511 int m = stats[l].giv_number;
6512 if (can_combine[m*giv_count + j])
6514 /* Remove additional weight for being reused. */
6515 stats[l].total_benefit -= 3 +
6516 combine_givs_benefit_from (giv_array[m], g2);
6520 if (loop_dump_stream)
6521 fprintf (loop_dump_stream,
6522 "giv at %d combined with giv at %d\n",
6523 INSN_UID (g2->insn), INSN_UID (g1->insn));
6527 /* To help optimize the next set of combinations, remove
6528 this giv from the benefits of other potential mates. */
6529 if (g1->combined_with)
6531 for (j = 0; j < giv_count; ++j)
6533 int m = stats[j].giv_number;
6534 if (can_combine[m*giv_count + j])
6536 /* Remove additional weight for being reused. */
6537 stats[j].total_benefit -= 3 +
6538 combine_givs_benefit_from (giv_array[m], g1);
6542 g1->benefit += g1_add_benefit;
6544 /* We've finished with this giv, and everything it touched.
6545 Restart the combination so that proper weights for the
6546 rest of the givs are properly taken into account. */
6547 /* ??? Ideally we would compact the arrays at this point, so
6548 as to not cover old ground. But sanely compacting
6549 can_combine is tricky. */
6555 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
6558 emit_iv_add_mult (b, m, a, reg, insert_before)
6559 rtx b; /* initial value of basic induction variable */
6560 rtx m; /* multiplicative constant */
6561 rtx a; /* additive constant */
6562 rtx reg; /* destination register */
6568 /* Prevent unexpected sharing of these rtx. */
6572 /* Increase the lifetime of any invariants moved further in code. */
6573 update_reg_last_use (a, insert_before);
6574 update_reg_last_use (b, insert_before);
6575 update_reg_last_use (m, insert_before);
6578 result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
6580 emit_move_insn (reg, result);
6581 seq = gen_sequence ();
6584 emit_insn_before (seq, insert_before);
6586 /* It is entirely possible that the expansion created lots of new
6587 registers. Iterate over the sequence we just created and
6590 if (GET_CODE (seq) == SEQUENCE)
6593 for (i = 0; i < XVECLEN (seq, 0); ++i)
6595 rtx set = single_set (XVECEXP (seq, 0, i));
6596 if (set && GET_CODE (SET_DEST (set)) == REG)
6597 record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
6600 else if (GET_CODE (seq) == SET
6601 && GET_CODE (SET_DEST (seq)) == REG)
6602 record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
6605 /* Test whether A * B can be computed without
6606 an actual multiply insn. Value is 1 if so. */
6609 product_cheap_p (a, b)
6615 struct obstack *old_rtl_obstack = rtl_obstack;
6616 char *storage = (char *) obstack_alloc (&temp_obstack, 0);
6619 /* If only one is constant, make it B. */
6620 if (GET_CODE (a) == CONST_INT)
6621 tmp = a, a = b, b = tmp;
6623 /* If first constant, both constant, so don't need multiply. */
6624 if (GET_CODE (a) == CONST_INT)
6627 /* If second not constant, neither is constant, so would need multiply. */
6628 if (GET_CODE (b) != CONST_INT)
6631 /* One operand is constant, so might not need multiply insn. Generate the
6632 code for the multiply and see if a call or multiply, or long sequence
6633 of insns is generated. */
6635 rtl_obstack = &temp_obstack;
6637 expand_mult (GET_MODE (a), a, b, NULL_RTX, 0);
6638 tmp = gen_sequence ();
6641 if (GET_CODE (tmp) == SEQUENCE)
6643 if (XVEC (tmp, 0) == 0)
6645 else if (XVECLEN (tmp, 0) > 3)
6648 for (i = 0; i < XVECLEN (tmp, 0); i++)
6650 rtx insn = XVECEXP (tmp, 0, i);
6652 if (GET_CODE (insn) != INSN
6653 || (GET_CODE (PATTERN (insn)) == SET
6654 && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
6655 || (GET_CODE (PATTERN (insn)) == PARALLEL
6656 && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
6657 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
6664 else if (GET_CODE (tmp) == SET
6665 && GET_CODE (SET_SRC (tmp)) == MULT)
6667 else if (GET_CODE (tmp) == PARALLEL
6668 && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
6669 && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
6672 /* Free any storage we obtained in generating this multiply and restore rtl
6673 allocation to its normal obstack. */
6674 obstack_free (&temp_obstack, storage);
6675 rtl_obstack = old_rtl_obstack;
6680 /* Check to see if loop can be terminated by a "decrement and branch until
6681 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
6682 Also try reversing an increment loop to a decrement loop
6683 to see if the optimization can be performed.
6684 Value is nonzero if optimization was performed. */
6686 /* This is useful even if the architecture doesn't have such an insn,
6687 because it might change a loops which increments from 0 to n to a loop
6688 which decrements from n to 0. A loop that decrements to zero is usually
6689 faster than one that increments from zero. */
6691 /* ??? This could be rewritten to use some of the loop unrolling procedures,
6692 such as approx_final_value, biv_total_increment, loop_iterations, and
6693 final_[bg]iv_value. */
6696 check_dbra_loop (loop_end, insn_count, loop_start)
6701 struct iv_class *bl;
6708 rtx before_comparison;
6712 int compare_and_branch;
6714 /* If last insn is a conditional branch, and the insn before tests a
6715 register value, try to optimize it. Otherwise, we can't do anything. */
6717 jump = PREV_INSN (loop_end);
6718 comparison = get_condition_for_loop (jump);
6719 if (comparison == 0)
6722 /* Try to compute whether the compare/branch at the loop end is one or
6723 two instructions. */
6724 get_condition (jump, &first_compare);
6725 if (first_compare == jump)
6726 compare_and_branch = 1;
6727 else if (first_compare == prev_nonnote_insn (jump))
6728 compare_and_branch = 2;
6732 /* Check all of the bivs to see if the compare uses one of them.
6733 Skip biv's set more than once because we can't guarantee that
6734 it will be zero on the last iteration. Also skip if the biv is
6735 used between its update and the test insn. */
6737 for (bl = loop_iv_list; bl; bl = bl->next)
6739 if (bl->biv_count == 1
6740 && bl->biv->dest_reg == XEXP (comparison, 0)
6741 && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
6749 /* Look for the case where the basic induction variable is always
6750 nonnegative, and equals zero on the last iteration.
6751 In this case, add a reg_note REG_NONNEG, which allows the
6752 m68k DBRA instruction to be used. */
6754 if (((GET_CODE (comparison) == GT
6755 && GET_CODE (XEXP (comparison, 1)) == CONST_INT
6756 && INTVAL (XEXP (comparison, 1)) == -1)
6757 || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
6758 && GET_CODE (bl->biv->add_val) == CONST_INT
6759 && INTVAL (bl->biv->add_val) < 0)
6761 /* Initial value must be greater than 0,
6762 init_val % -dec_value == 0 to ensure that it equals zero on
6763 the last iteration */
6765 if (GET_CODE (bl->initial_value) == CONST_INT
6766 && INTVAL (bl->initial_value) > 0
6767 && (INTVAL (bl->initial_value)
6768 % (-INTVAL (bl->biv->add_val))) == 0)
6770 /* register always nonnegative, add REG_NOTE to branch */
6771 REG_NOTES (PREV_INSN (loop_end))
6772 = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
6773 REG_NOTES (PREV_INSN (loop_end)));
6779 /* If the decrement is 1 and the value was tested as >= 0 before
6780 the loop, then we can safely optimize. */
6781 for (p = loop_start; p; p = PREV_INSN (p))
6783 if (GET_CODE (p) == CODE_LABEL)
6785 if (GET_CODE (p) != JUMP_INSN)
6788 before_comparison = get_condition_for_loop (p);
6789 if (before_comparison
6790 && XEXP (before_comparison, 0) == bl->biv->dest_reg
6791 && GET_CODE (before_comparison) == LT
6792 && XEXP (before_comparison, 1) == const0_rtx
6793 && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
6794 && INTVAL (bl->biv->add_val) == -1)
6796 REG_NOTES (PREV_INSN (loop_end))
6797 = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
6798 REG_NOTES (PREV_INSN (loop_end)));
6805 else if (INTVAL (bl->biv->add_val) > 0)
6807 /* Try to change inc to dec, so can apply above optimization. */
6809 all registers modified are induction variables or invariant,
6810 all memory references have non-overlapping addresses
6811 (obviously true if only one write)
6812 allow 2 insns for the compare/jump at the end of the loop. */
6813 /* Also, we must avoid any instructions which use both the reversed
6814 biv and another biv. Such instructions will fail if the loop is
6815 reversed. We meet this condition by requiring that either
6816 no_use_except_counting is true, or else that there is only
6818 int num_nonfixed_reads = 0;
6819 /* 1 if the iteration var is used only to count iterations. */
6820 int no_use_except_counting = 0;
6821 /* 1 if the loop has no memory store, or it has a single memory store
6822 which is reversible. */
6823 int reversible_mem_store = 1;
6825 if (bl->giv_count == 0
6826 && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
6828 rtx bivreg = regno_reg_rtx[bl->regno];
6830 /* If there are no givs for this biv, and the only exit is the
6831 fall through at the end of the loop, then
6832 see if perhaps there are no uses except to count. */
6833 no_use_except_counting = 1;
6834 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
6835 if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
6837 rtx set = single_set (p);
6839 if (set && GET_CODE (SET_DEST (set)) == REG
6840 && REGNO (SET_DEST (set)) == bl->regno)
6841 /* An insn that sets the biv is okay. */
6843 else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
6844 || p == prev_nonnote_insn (loop_end))
6845 /* Don't bother about the end test. */
6847 else if (reg_mentioned_p (bivreg, PATTERN (p)))
6849 no_use_except_counting = 0;
6855 if (no_use_except_counting)
6856 ; /* no need to worry about MEMs. */
6857 else if (num_mem_sets <= 1)
6859 for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
6860 if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
6861 num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
6863 /* If the loop has a single store, and the destination address is
6864 invariant, then we can't reverse the loop, because this address
6865 might then have the wrong value at loop exit.
6866 This would work if the source was invariant also, however, in that
6867 case, the insn should have been moved out of the loop. */
6869 if (num_mem_sets == 1)
6870 reversible_mem_store
6871 = (! unknown_address_altered
6872 && ! invariant_p (XEXP (loop_store_mems[0], 0)));
6877 /* This code only acts for innermost loops. Also it simplifies
6878 the memory address check by only reversing loops with
6879 zero or one memory access.
6880 Two memory accesses could involve parts of the same array,
6881 and that can't be reversed.
6882 If the biv is used only for counting, than we don't need to worry
6883 about all these things. */
6885 if ((num_nonfixed_reads <= 1
6887 && !loop_has_volatile
6888 && reversible_mem_store
6889 && (bl->giv_count + bl->biv_count + num_mem_sets
6890 + num_movables + compare_and_branch == insn_count)
6891 && (bl == loop_iv_list && bl->next == 0))
6892 || no_use_except_counting)
6896 /* Loop can be reversed. */
6897 if (loop_dump_stream)
6898 fprintf (loop_dump_stream, "Can reverse loop\n");
6900 /* Now check other conditions:
6902 The increment must be a constant, as must the initial value,
6903 and the comparison code must be LT.
6905 This test can probably be improved since +/- 1 in the constant
6906 can be obtained by changing LT to LE and vice versa; this is
6910 /* for constants, LE gets turned into LT */
6911 && (GET_CODE (comparison) == LT
6912 || (GET_CODE (comparison) == LE
6913 && no_use_except_counting)))
6915 HOST_WIDE_INT add_val, add_adjust, comparison_val;
6916 rtx initial_value, comparison_value;
6918 enum rtx_code cmp_code;
6919 int comparison_const_width;
6920 unsigned HOST_WIDE_INT comparison_sign_mask;
6923 add_val = INTVAL (bl->biv->add_val);
6924 comparison_value = XEXP (comparison, 1);
6925 comparison_const_width
6926 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 1)));
6927 if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
6928 comparison_const_width = HOST_BITS_PER_WIDE_INT;
6929 comparison_sign_mask
6930 = (unsigned HOST_WIDE_INT)1 << (comparison_const_width - 1);
6932 /* If the comparison value is not a loop invariant, then we
6933 can not reverse this loop.
6935 ??? If the insns which initialize the comparison value as
6936 a whole compute an invariant result, then we could move
6937 them out of the loop and proceed with loop reversal. */
6938 if (!invariant_p (comparison_value))
6941 if (GET_CODE (comparison_value) == CONST_INT)
6942 comparison_val = INTVAL (comparison_value);
6943 initial_value = bl->initial_value;
6945 /* Normalize the initial value if it is an integer and
6946 has no other use except as a counter. This will allow
6947 a few more loops to be reversed. */
6948 if (no_use_except_counting
6949 && GET_CODE (comparison_value) == CONST_INT
6950 && GET_CODE (initial_value) == CONST_INT)
6952 comparison_val = comparison_val - INTVAL (bl->initial_value);
6953 /* The code below requires comparison_val to be a multiple
6954 of add_val in order to do the loop reversal, so
6955 round up comparison_val to a multiple of add_val.
6956 Since comparison_value is constant, we know that the
6957 current comparison code is LT. */
6958 comparison_val = comparison_val + add_val - 1;
6960 -= (unsigned HOST_WIDE_INT) comparison_val % add_val;
6961 /* We postpone overflow checks for COMPARISON_VAL here;
6962 even if there is an overflow, we might still be able to
6963 reverse the loop, if converting the loop exit test to
6965 initial_value = const0_rtx;
6968 /* Check if there is a NOTE_INSN_LOOP_VTOP note. If there is,
6969 that means that this is a for or while style loop, with
6970 a loop exit test at the start. Thus, we can assume that
6971 the loop condition was true when the loop was entered.
6972 This allows us to change the loop exit condition to an
6974 We start at the end and search backwards for the previous
6975 NOTE. If there is no NOTE_INSN_LOOP_VTOP for this loop,
6976 the search will stop at the NOTE_INSN_LOOP_CONT. */
6979 vtop = PREV_INSN (vtop);
6980 while (GET_CODE (vtop) != NOTE
6981 || NOTE_LINE_NUMBER (vtop) > 0
6982 || NOTE_LINE_NUMBER (vtop) == NOTE_REPEATED_LINE_NUMBER
6983 || NOTE_LINE_NUMBER (vtop) == NOTE_INSN_DELETED);
6984 if (NOTE_LINE_NUMBER (vtop) != NOTE_INSN_LOOP_VTOP)
6987 /* First check if we can do a vanilla loop reversal. */
6988 if (initial_value == const0_rtx
6989 /* If we have a decrement_and_branch_on_count, prefer
6990 the NE test, since this will allow that instruction to
6991 be generated. Note that we must use a vanilla loop
6992 reversal if the biv is used to calculate a giv or has
6993 a non-counting use. */
6994 #if ! defined (HAVE_decrement_and_branch_until_zero) && defined (HAVE_decrement_and_branch_on_count)
6995 && (! (add_val == 1 && vtop
6996 && (bl->biv_count == 0
6997 || no_use_except_counting)))
6999 && GET_CODE (comparison_value) == CONST_INT
7000 /* Now do postponed overflow checks on COMPARISON_VAL. */
7001 && ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
7002 & comparison_sign_mask))
7004 /* Register will always be nonnegative, with value
7005 0 on last iteration */
7006 add_adjust = add_val;
7010 else if (add_val == 1 && vtop
7011 && (bl->biv_count == 0
7012 || no_use_except_counting))
7020 if (GET_CODE (comparison) == LE)
7021 add_adjust -= add_val;
7023 /* If the initial value is not zero, or if the comparison
7024 value is not an exact multiple of the increment, then we
7025 can not reverse this loop. */
7026 if (initial_value == const0_rtx
7027 && GET_CODE (comparison_value) == CONST_INT)
7029 if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
7034 if (! no_use_except_counting || add_val != 1)
7038 final_value = comparison_value;
7040 /* Reset these in case we normalized the initial value
7041 and comparison value above. */
7042 if (GET_CODE (comparison_value) == CONST_INT
7043 && GET_CODE (initial_value) == CONST_INT)
7045 comparison_value = GEN_INT (comparison_val);
7047 = GEN_INT (comparison_val + INTVAL (bl->initial_value));
7049 bl->initial_value = initial_value;
7051 /* Save some info needed to produce the new insns. */
7052 reg = bl->biv->dest_reg;
7053 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
7054 if (jump_label == pc_rtx)
7055 jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
7056 new_add_val = GEN_INT (- INTVAL (bl->biv->add_val));
7058 /* Set start_value; if this is not a CONST_INT, we need
7060 Initialize biv to start_value before loop start.
7061 The old initializing insn will be deleted as a
7062 dead store by flow.c. */
7063 if (initial_value == const0_rtx
7064 && GET_CODE (comparison_value) == CONST_INT)
7066 start_value = GEN_INT (comparison_val - add_adjust);
7067 emit_insn_before (gen_move_insn (reg, start_value),
7070 else if (GET_CODE (initial_value) == CONST_INT)
7072 rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
7073 enum machine_mode mode = GET_MODE (reg);
7074 enum insn_code icode
7075 = add_optab->handlers[(int) mode].insn_code;
7076 if (! (*insn_operand_predicate[icode][0]) (reg, mode)
7077 || ! ((*insn_operand_predicate[icode][1])
7078 (comparison_value, mode))
7079 || ! (*insn_operand_predicate[icode][2]) (offset, mode))
7082 = gen_rtx_PLUS (mode, comparison_value, offset);
7083 emit_insn_before ((GEN_FCN (icode)
7084 (reg, comparison_value, offset)),
7086 if (GET_CODE (comparison) == LE)
7087 final_value = gen_rtx_PLUS (mode, comparison_value,
7090 else if (! add_adjust)
7092 enum machine_mode mode = GET_MODE (reg);
7093 enum insn_code icode
7094 = sub_optab->handlers[(int) mode].insn_code;
7095 if (! (*insn_operand_predicate[icode][0]) (reg, mode)
7096 || ! ((*insn_operand_predicate[icode][1])
7097 (comparison_value, mode))
7098 || ! ((*insn_operand_predicate[icode][2])
7099 (initial_value, mode)))
7102 = gen_rtx_MINUS (mode, comparison_value, initial_value);
7103 emit_insn_before ((GEN_FCN (icode)
7104 (reg, comparison_value, initial_value)),
7108 /* We could handle the other cases too, but it'll be
7109 better to have a testcase first. */
7112 /* Add insn to decrement register, and delete insn
7113 that incremented the register. */
7114 p = emit_insn_before (gen_add2_insn (reg, new_add_val),
7116 delete_insn (bl->biv->insn);
7118 /* Update biv info to reflect its new status. */
7120 bl->initial_value = start_value;
7121 bl->biv->add_val = new_add_val;
7123 /* Inc LABEL_NUSES so that delete_insn will
7124 not delete the label. */
7125 LABEL_NUSES (XEXP (jump_label, 0)) ++;
7127 /* Emit an insn after the end of the loop to set the biv's
7128 proper exit value if it is used anywhere outside the loop. */
7129 if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
7131 || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
7132 emit_insn_after (gen_move_insn (reg, final_value),
7135 /* Delete compare/branch at end of loop. */
7136 delete_insn (PREV_INSN (loop_end));
7137 if (compare_and_branch == 2)
7138 delete_insn (first_compare);
7140 /* Add new compare/branch insn at end of loop. */
7142 emit_cmp_insn (reg, const0_rtx, cmp_code, NULL_RTX,
7143 GET_MODE (reg), 0, 0);
7144 emit_jump_insn ((*bcc_gen_fctn[(int) cmp_code])
7145 (XEXP (jump_label, 0)));
7146 tem = gen_sequence ();
7148 emit_jump_insn_before (tem, loop_end);
7152 for (tem = PREV_INSN (loop_end);
7153 tem && GET_CODE (tem) != JUMP_INSN;
7154 tem = PREV_INSN (tem))
7158 JUMP_LABEL (tem) = XEXP (jump_label, 0);
7160 /* Increment of LABEL_NUSES done above. */
7161 /* Register is now always nonnegative,
7162 so add REG_NONNEG note to the branch. */
7163 REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
7169 /* Mark that this biv has been reversed. Each giv which depends
7170 on this biv, and which is also live past the end of the loop
7171 will have to be fixed up. */
7175 if (loop_dump_stream)
7176 fprintf (loop_dump_stream,
7177 "Reversed loop and added reg_nonneg\n");
7187 /* Verify whether the biv BL appears to be eliminable,
7188 based on the insns in the loop that refer to it.
7189 LOOP_START is the first insn of the loop, and END is the end insn.
7191 If ELIMINATE_P is non-zero, actually do the elimination.
7193 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7194 determine whether invariant insns should be placed inside or at the
7195 start of the loop. */
7198 maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
7199 struct iv_class *bl;
7203 int threshold, insn_count;
7205 rtx reg = bl->biv->dest_reg;
7208 /* Scan all insns in the loop, stopping if we find one that uses the
7209 biv in a way that we cannot eliminate. */
7211 for (p = loop_start; p != end; p = NEXT_INSN (p))
7213 enum rtx_code code = GET_CODE (p);
7214 rtx where = threshold >= insn_count ? loop_start : p;
7216 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
7217 && reg_mentioned_p (reg, PATTERN (p))
7218 && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
7220 if (loop_dump_stream)
7221 fprintf (loop_dump_stream,
7222 "Cannot eliminate biv %d: biv used in insn %d.\n",
7223 bl->regno, INSN_UID (p));
7230 if (loop_dump_stream)
7231 fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
7232 bl->regno, eliminate_p ? "was" : "can be");
7239 /* If BL appears in X (part of the pattern of INSN), see if we can
7240 eliminate its use. If so, return 1. If not, return 0.
7242 If BIV does not appear in X, return 1.
7244 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7245 where extra insns should be added. Depending on how many items have been
7246 moved out of the loop, it will either be before INSN or at the start of
7250 maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
7252 struct iv_class *bl;
7256 enum rtx_code code = GET_CODE (x);
7257 rtx reg = bl->biv->dest_reg;
7258 enum machine_mode mode = GET_MODE (reg);
7259 struct induction *v;
7271 /* If we haven't already been able to do something with this BIV,
7272 we can't eliminate it. */
7278 /* If this sets the BIV, it is not a problem. */
7279 if (SET_DEST (x) == reg)
7282 /* If this is an insn that defines a giv, it is also ok because
7283 it will go away when the giv is reduced. */
7284 for (v = bl->giv; v; v = v->next_iv)
7285 if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
7289 if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
7291 /* Can replace with any giv that was reduced and
7292 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7293 Require a constant for MULT_VAL, so we know it's nonzero.
7294 ??? We disable this optimization to avoid potential
7297 for (v = bl->giv; v; v = v->next_iv)
7298 if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
7299 && v->add_val == const0_rtx
7300 && ! v->ignore && ! v->maybe_dead && v->always_computable
7304 /* If the giv V had the auto-inc address optimization applied
7305 to it, and INSN occurs between the giv insn and the biv
7306 insn, then we must adjust the value used here.
7307 This is rare, so we don't bother to do so. */
7309 && ((INSN_LUID (v->insn) < INSN_LUID (insn)
7310 && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
7311 || (INSN_LUID (v->insn) > INSN_LUID (insn)
7312 && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
7318 /* If the giv has the opposite direction of change,
7319 then reverse the comparison. */
7320 if (INTVAL (v->mult_val) < 0)
7321 new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
7322 const0_rtx, v->new_reg);
7326 /* We can probably test that giv's reduced reg. */
7327 if (validate_change (insn, &SET_SRC (x), new, 0))
7331 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7332 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7333 Require a constant for MULT_VAL, so we know it's nonzero.
7334 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7335 overflow problem. */
7337 for (v = bl->giv; v; v = v->next_iv)
7338 if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
7339 && ! v->ignore && ! v->maybe_dead && v->always_computable
7341 && (GET_CODE (v->add_val) == SYMBOL_REF
7342 || GET_CODE (v->add_val) == LABEL_REF
7343 || GET_CODE (v->add_val) == CONST
7344 || (GET_CODE (v->add_val) == REG
7345 && REGNO_POINTER_FLAG (REGNO (v->add_val)))))
7347 /* If the giv V had the auto-inc address optimization applied
7348 to it, and INSN occurs between the giv insn and the biv
7349 insn, then we must adjust the value used here.
7350 This is rare, so we don't bother to do so. */
7352 && ((INSN_LUID (v->insn) < INSN_LUID (insn)
7353 && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
7354 || (INSN_LUID (v->insn) > INSN_LUID (insn)
7355 && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
7361 /* If the giv has the opposite direction of change,
7362 then reverse the comparison. */
7363 if (INTVAL (v->mult_val) < 0)
7364 new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
7367 new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
7368 copy_rtx (v->add_val));
7370 /* Replace biv with the giv's reduced register. */
7371 update_reg_last_use (v->add_val, insn);
7372 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7375 /* Insn doesn't support that constant or invariant. Copy it
7376 into a register (it will be a loop invariant.) */
7377 tem = gen_reg_rtx (GET_MODE (v->new_reg));
7379 emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
7382 /* Substitute the new register for its invariant value in
7383 the compare expression. */
7384 XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
7385 if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
7394 case GT: case GE: case GTU: case GEU:
7395 case LT: case LE: case LTU: case LEU:
7396 /* See if either argument is the biv. */
7397 if (XEXP (x, 0) == reg)
7398 arg = XEXP (x, 1), arg_operand = 1;
7399 else if (XEXP (x, 1) == reg)
7400 arg = XEXP (x, 0), arg_operand = 0;
7404 if (CONSTANT_P (arg))
7406 /* First try to replace with any giv that has constant positive
7407 mult_val and constant add_val. We might be able to support
7408 negative mult_val, but it seems complex to do it in general. */
7410 for (v = bl->giv; v; v = v->next_iv)
7411 if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
7412 && (GET_CODE (v->add_val) == SYMBOL_REF
7413 || GET_CODE (v->add_val) == LABEL_REF
7414 || GET_CODE (v->add_val) == CONST
7415 || (GET_CODE (v->add_val) == REG
7416 && REGNO_POINTER_FLAG (REGNO (v->add_val))))
7417 && ! v->ignore && ! v->maybe_dead && v->always_computable
7420 /* If the giv V had the auto-inc address optimization applied
7421 to it, and INSN occurs between the giv insn and the biv
7422 insn, then we must adjust the value used here.
7423 This is rare, so we don't bother to do so. */
7425 && ((INSN_LUID (v->insn) < INSN_LUID (insn)
7426 && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
7427 || (INSN_LUID (v->insn) > INSN_LUID (insn)
7428 && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
7434 /* Replace biv with the giv's reduced reg. */
7435 XEXP (x, 1-arg_operand) = v->new_reg;
7437 /* If all constants are actually constant integers and
7438 the derived constant can be directly placed in the COMPARE,
7440 if (GET_CODE (arg) == CONST_INT
7441 && GET_CODE (v->mult_val) == CONST_INT
7442 && GET_CODE (v->add_val) == CONST_INT
7443 && validate_change (insn, &XEXP (x, arg_operand),
7444 GEN_INT (INTVAL (arg)
7445 * INTVAL (v->mult_val)
7446 + INTVAL (v->add_val)), 0))
7449 /* Otherwise, load it into a register. */
7450 tem = gen_reg_rtx (mode);
7451 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7452 if (validate_change (insn, &XEXP (x, arg_operand), tem, 0))
7455 /* If that failed, put back the change we made above. */
7456 XEXP (x, 1-arg_operand) = reg;
7459 /* Look for giv with positive constant mult_val and nonconst add_val.
7460 Insert insns to calculate new compare value.
7461 ??? Turn this off due to possible overflow. */
7463 for (v = bl->giv; v; v = v->next_iv)
7464 if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
7465 && ! v->ignore && ! v->maybe_dead && v->always_computable
7471 /* If the giv V had the auto-inc address optimization applied
7472 to it, and INSN occurs between the giv insn and the biv
7473 insn, then we must adjust the value used here.
7474 This is rare, so we don't bother to do so. */
7476 && ((INSN_LUID (v->insn) < INSN_LUID (insn)
7477 && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
7478 || (INSN_LUID (v->insn) > INSN_LUID (insn)
7479 && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
7485 tem = gen_reg_rtx (mode);
7487 /* Replace biv with giv's reduced register. */
7488 validate_change (insn, &XEXP (x, 1 - arg_operand),
7491 /* Compute value to compare against. */
7492 emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
7493 /* Use it in this insn. */
7494 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7495 if (apply_change_group ())
7499 else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
7501 if (invariant_p (arg) == 1)
7503 /* Look for giv with constant positive mult_val and nonconst
7504 add_val. Insert insns to compute new compare value.
7505 ??? Turn this off due to possible overflow. */
7507 for (v = bl->giv; v; v = v->next_iv)
7508 if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
7509 && ! v->ignore && ! v->maybe_dead && v->always_computable
7515 /* If the giv V had the auto-inc address optimization applied
7516 to it, and INSN occurs between the giv insn and the biv
7517 insn, then we must adjust the value used here.
7518 This is rare, so we don't bother to do so. */
7520 && ((INSN_LUID (v->insn) < INSN_LUID (insn)
7521 && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
7522 || (INSN_LUID (v->insn) > INSN_LUID (insn)
7523 && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
7529 tem = gen_reg_rtx (mode);
7531 /* Replace biv with giv's reduced register. */
7532 validate_change (insn, &XEXP (x, 1 - arg_operand),
7535 /* Compute value to compare against. */
7536 emit_iv_add_mult (arg, v->mult_val, v->add_val,
7538 validate_change (insn, &XEXP (x, arg_operand), tem, 1);
7539 if (apply_change_group ())
7544 /* This code has problems. Basically, you can't know when
7545 seeing if we will eliminate BL, whether a particular giv
7546 of ARG will be reduced. If it isn't going to be reduced,
7547 we can't eliminate BL. We can try forcing it to be reduced,
7548 but that can generate poor code.
7550 The problem is that the benefit of reducing TV, below should
7551 be increased if BL can actually be eliminated, but this means
7552 we might have to do a topological sort of the order in which
7553 we try to process biv. It doesn't seem worthwhile to do
7554 this sort of thing now. */
7557 /* Otherwise the reg compared with had better be a biv. */
7558 if (GET_CODE (arg) != REG
7559 || reg_iv_type[REGNO (arg)] != BASIC_INDUCT)
7562 /* Look for a pair of givs, one for each biv,
7563 with identical coefficients. */
7564 for (v = bl->giv; v; v = v->next_iv)
7566 struct induction *tv;
7568 if (v->ignore || v->maybe_dead || v->mode != mode)
7571 for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
7572 if (! tv->ignore && ! tv->maybe_dead
7573 && rtx_equal_p (tv->mult_val, v->mult_val)
7574 && rtx_equal_p (tv->add_val, v->add_val)
7575 && tv->mode == mode)
7577 /* If the giv V had the auto-inc address optimization applied
7578 to it, and INSN occurs between the giv insn and the biv
7579 insn, then we must adjust the value used here.
7580 This is rare, so we don't bother to do so. */
7582 && ((INSN_LUID (v->insn) < INSN_LUID (insn)
7583 && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
7584 || (INSN_LUID (v->insn) > INSN_LUID (insn)
7585 && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
7591 /* Replace biv with its giv's reduced reg. */
7592 XEXP (x, 1-arg_operand) = v->new_reg;
7593 /* Replace other operand with the other giv's
7595 XEXP (x, arg_operand) = tv->new_reg;
7602 /* If we get here, the biv can't be eliminated. */
7606 /* If this address is a DEST_ADDR giv, it doesn't matter if the
7607 biv is used in it, since it will be replaced. */
7608 for (v = bl->giv; v; v = v->next_iv)
7609 if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
7617 /* See if any subexpression fails elimination. */
7618 fmt = GET_RTX_FORMAT (code);
7619 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
7624 if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl,
7625 eliminate_p, where))
7630 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7631 if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl,
7632 eliminate_p, where))
7641 /* Return nonzero if the last use of REG
7642 is in an insn following INSN in the same basic block. */
7645 last_use_this_basic_block (reg, insn)
7651 n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
7654 if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
7660 /* Called via `note_stores' to record the initial value of a biv. Here we
7661 just record the location of the set and process it later. */
7664 record_initial (dest, set)
7668 struct iv_class *bl;
7670 if (GET_CODE (dest) != REG
7671 || REGNO (dest) >= max_reg_before_loop
7672 || reg_iv_type[REGNO (dest)] != BASIC_INDUCT)
7675 bl = reg_biv_class[REGNO (dest)];
7677 /* If this is the first set found, record it. */
7678 if (bl->init_insn == 0)
7680 bl->init_insn = note_insn;
7685 /* If any of the registers in X are "old" and currently have a last use earlier
7686 than INSN, update them to have a last use of INSN. Their actual last use
7687 will be the previous insn but it will not have a valid uid_luid so we can't
7691 update_reg_last_use (x, insn)
7695 /* Check for the case where INSN does not have a valid luid. In this case,
7696 there is no need to modify the regno_last_uid, as this can only happen
7697 when code is inserted after the loop_end to set a pseudo's final value,
7698 and hence this insn will never be the last use of x. */
7699 if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
7700 && INSN_UID (insn) < max_uid_for_loop
7701 && uid_luid[REGNO_LAST_UID (REGNO (x))] < uid_luid[INSN_UID (insn)])
7702 REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
7706 register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
7707 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
7710 update_reg_last_use (XEXP (x, i), insn);
7711 else if (fmt[i] == 'E')
7712 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7713 update_reg_last_use (XVECEXP (x, i, j), insn);
7718 /* Given a jump insn JUMP, return the condition that will cause it to branch
7719 to its JUMP_LABEL. If the condition cannot be understood, or is an
7720 inequality floating-point comparison which needs to be reversed, 0 will
7723 If EARLIEST is non-zero, it is a pointer to a place where the earliest
7724 insn used in locating the condition was found. If a replacement test
7725 of the condition is desired, it should be placed in front of that
7726 insn and we will be sure that the inputs are still valid.
7728 The condition will be returned in a canonical form to simplify testing by
7729 callers. Specifically:
7731 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
7732 (2) Both operands will be machine operands; (cc0) will have been replaced.
7733 (3) If an operand is a constant, it will be the second operand.
7734 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
7735 for GE, GEU, and LEU. */
7738 get_condition (jump, earliest)
7747 int reverse_code = 0;
7748 int did_reverse_condition = 0;
7749 enum machine_mode mode;
7751 /* If this is not a standard conditional jump, we can't parse it. */
7752 if (GET_CODE (jump) != JUMP_INSN
7753 || ! condjump_p (jump) || simplejump_p (jump))
7756 code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0));
7757 mode = GET_MODE (XEXP (SET_SRC (PATTERN (jump)), 0));
7758 op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0);
7759 op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1);
7764 /* If this branches to JUMP_LABEL when the condition is false, reverse
7766 if (GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 2)) == LABEL_REF
7767 && XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump))
7768 code = reverse_condition (code), did_reverse_condition ^= 1;
7770 /* If we are comparing a register with zero, see if the register is set
7771 in the previous insn to a COMPARE or a comparison operation. Perform
7772 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
7775 while (GET_RTX_CLASS (code) == '<' && op1 == CONST0_RTX (GET_MODE (op0)))
7777 /* Set non-zero when we find something of interest. */
7781 /* If comparison with cc0, import actual comparison from compare
7785 if ((prev = prev_nonnote_insn (prev)) == 0
7786 || GET_CODE (prev) != INSN
7787 || (set = single_set (prev)) == 0
7788 || SET_DEST (set) != cc0_rtx)
7791 op0 = SET_SRC (set);
7792 op1 = CONST0_RTX (GET_MODE (op0));
7798 /* If this is a COMPARE, pick up the two things being compared. */
7799 if (GET_CODE (op0) == COMPARE)
7801 op1 = XEXP (op0, 1);
7802 op0 = XEXP (op0, 0);
7805 else if (GET_CODE (op0) != REG)
7808 /* Go back to the previous insn. Stop if it is not an INSN. We also
7809 stop if it isn't a single set or if it has a REG_INC note because
7810 we don't want to bother dealing with it. */
7812 if ((prev = prev_nonnote_insn (prev)) == 0
7813 || GET_CODE (prev) != INSN
7814 || FIND_REG_INC_NOTE (prev, 0)
7815 || (set = single_set (prev)) == 0)
7818 /* If this is setting OP0, get what it sets it to if it looks
7820 if (rtx_equal_p (SET_DEST (set), op0))
7822 enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
7824 /* ??? We may not combine comparisons done in a CCmode with
7825 comparisons not done in a CCmode. This is to aid targets
7826 like Alpha that have an IEEE compliant EQ instruction, and
7827 a non-IEEE compliant BEQ instruction. The use of CCmode is
7828 actually artificial, simply to prevent the combination, but
7829 should not affect other platforms. */
7831 if ((GET_CODE (SET_SRC (set)) == COMPARE
7834 && GET_MODE_CLASS (inner_mode) == MODE_INT
7835 && (GET_MODE_BITSIZE (inner_mode)
7836 <= HOST_BITS_PER_WIDE_INT)
7837 && (STORE_FLAG_VALUE
7838 & ((HOST_WIDE_INT) 1
7839 << (GET_MODE_BITSIZE (inner_mode) - 1))))
7840 #ifdef FLOAT_STORE_FLAG_VALUE
7842 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
7843 && FLOAT_STORE_FLAG_VALUE < 0)
7846 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
7847 && ((GET_MODE_CLASS (mode) == MODE_CC)
7848 == (GET_MODE_CLASS (inner_mode) == MODE_CC)))
7850 else if (((code == EQ
7852 && (GET_MODE_BITSIZE (inner_mode)
7853 <= HOST_BITS_PER_WIDE_INT)
7854 && GET_MODE_CLASS (inner_mode) == MODE_INT
7855 && (STORE_FLAG_VALUE
7856 & ((HOST_WIDE_INT) 1
7857 << (GET_MODE_BITSIZE (inner_mode) - 1))))
7858 #ifdef FLOAT_STORE_FLAG_VALUE
7860 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
7861 && FLOAT_STORE_FLAG_VALUE < 0)
7864 && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
7865 && ((GET_MODE_CLASS (mode) == MODE_CC)
7866 == (GET_MODE_CLASS (inner_mode) == MODE_CC)))
7868 /* We might have reversed a LT to get a GE here. But this wasn't
7869 actually the comparison of data, so we don't flag that we
7870 have had to reverse the condition. */
7871 did_reverse_condition ^= 1;
7879 else if (reg_set_p (op0, prev))
7880 /* If this sets OP0, but not directly, we have to give up. */
7885 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
7886 code = GET_CODE (x);
7889 code = reverse_condition (code);
7890 did_reverse_condition ^= 1;
7894 op0 = XEXP (x, 0), op1 = XEXP (x, 1);
7900 /* If constant is first, put it last. */
7901 if (CONSTANT_P (op0))
7902 code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
7904 /* If OP0 is the result of a comparison, we weren't able to find what
7905 was really being compared, so fail. */
7906 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
7909 /* Canonicalize any ordered comparison with integers involving equality
7910 if we can do computations in the relevant mode and we do not
7913 if (GET_CODE (op1) == CONST_INT
7914 && GET_MODE (op0) != VOIDmode
7915 && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
7917 HOST_WIDE_INT const_val = INTVAL (op1);
7918 unsigned HOST_WIDE_INT uconst_val = const_val;
7919 unsigned HOST_WIDE_INT max_val
7920 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
7925 if (const_val != max_val >> 1)
7926 code = LT, op1 = GEN_INT (const_val + 1);
7929 /* When cross-compiling, const_val might be sign-extended from
7930 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
7932 if ((const_val & max_val)
7933 != (((HOST_WIDE_INT) 1
7934 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
7935 code = GT, op1 = GEN_INT (const_val - 1);
7939 if (uconst_val < max_val)
7940 code = LTU, op1 = GEN_INT (uconst_val + 1);
7944 if (uconst_val != 0)
7945 code = GTU, op1 = GEN_INT (uconst_val - 1);
7953 /* If this was floating-point and we reversed anything other than an
7954 EQ or NE, return zero. */
7955 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
7956 && did_reverse_condition && code != NE && code != EQ
7958 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
7962 /* Never return CC0; return zero instead. */
7967 return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
7970 /* Similar to above routine, except that we also put an invariant last
7971 unless both operands are invariants. */
7974 get_condition_for_loop (x)
7977 rtx comparison = get_condition (x, NULL_PTR);
7980 || ! invariant_p (XEXP (comparison, 0))
7981 || invariant_p (XEXP (comparison, 1)))
7984 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
7985 XEXP (comparison, 1), XEXP (comparison, 0));
7989 /* Analyze a loop in order to instrument it with the use of count register.
7990 loop_start and loop_end are the first and last insns of the loop.
7991 This function works in cooperation with insert_bct ().
7992 loop_can_insert_bct[loop_num] is set according to whether the optimization
7993 is applicable to the loop. When it is applicable, the following variables
7995 loop_start_value[loop_num]
7996 loop_comparison_value[loop_num]
7997 loop_increment[loop_num]
7998 loop_comparison_code[loop_num] */
8000 #ifdef HAVE_decrement_and_branch_on_count
8002 analyze_loop_iterations (loop_start, loop_end)
8003 rtx loop_start, loop_end;
8005 rtx comparison, comparison_value;
8006 rtx iteration_var, initial_value, increment;
8007 enum rtx_code comparison_code;
8013 /* loop_variable mode */
8014 enum machine_mode original_mode;
8016 /* find the number of the loop */
8017 int loop_num = uid_loop_num [INSN_UID (loop_start)];
8019 /* we change our mind only when we are sure that loop will be instrumented */
8020 loop_can_insert_bct[loop_num] = 0;
8022 /* is the optimization suppressed. */
8023 if ( !flag_branch_on_count_reg )
8026 /* make sure that count-reg is not in use */
8027 if (loop_used_count_register[loop_num]){
8028 if (loop_dump_stream)
8029 fprintf (loop_dump_stream,
8030 "analyze_loop_iterations %d: BCT instrumentation failed: count register already in use\n",
8035 /* make sure that the function has no indirect jumps. */
8036 if (indirect_jump_in_function){
8037 if (loop_dump_stream)
8038 fprintf (loop_dump_stream,
8039 "analyze_loop_iterations %d: BCT instrumentation failed: indirect jump in function\n",
8044 /* make sure that the last loop insn is a conditional jump */
8045 last_loop_insn = PREV_INSN (loop_end);
8046 if (GET_CODE (last_loop_insn) != JUMP_INSN || !condjump_p (last_loop_insn)) {
8047 if (loop_dump_stream)
8048 fprintf (loop_dump_stream,
8049 "analyze_loop_iterations %d: BCT instrumentation failed: invalid jump at loop end\n",
8054 /* First find the iteration variable. If the last insn is a conditional
8055 branch, and the insn preceding it tests a register value, make that
8056 register the iteration variable. */
8058 /* We used to use prev_nonnote_insn here, but that fails because it might
8059 accidentally get the branch for a contained loop if the branch for this
8060 loop was deleted. We can only trust branches immediately before the
8063 comparison = get_condition_for_loop (last_loop_insn);
8064 /* ??? Get_condition may switch position of induction variable and
8065 invariant register when it canonicalizes the comparison. */
8067 if (comparison == 0) {
8068 if (loop_dump_stream)
8069 fprintf (loop_dump_stream,
8070 "analyze_loop_iterations %d: BCT instrumentation failed: comparison not found\n",
8075 comparison_code = GET_CODE (comparison);
8076 iteration_var = XEXP (comparison, 0);
8077 comparison_value = XEXP (comparison, 1);
8079 original_mode = GET_MODE (iteration_var);
8080 if (GET_MODE_CLASS (original_mode) != MODE_INT
8081 || GET_MODE_SIZE (original_mode) != UNITS_PER_WORD) {
8082 if (loop_dump_stream)
8083 fprintf (loop_dump_stream,
8084 "analyze_loop_iterations %d: BCT Instrumentation failed: loop variable not integer\n",
8089 /* get info about loop bounds and increment */
8090 iteration_info (iteration_var, &initial_value, &increment,
8091 loop_start, loop_end);
8093 /* make sure that all required loop data were found */
8094 if (!(initial_value && increment && comparison_value
8095 && invariant_p (comparison_value) && invariant_p (increment)
8096 && ! indirect_jump_in_function))
8098 if (loop_dump_stream) {
8099 fprintf (loop_dump_stream,
8100 "analyze_loop_iterations %d: BCT instrumentation failed because of wrong loop: ", loop_num);
8101 if (!(initial_value && increment && comparison_value)) {
8102 fprintf (loop_dump_stream, "\tbounds not available: ");
8103 if ( ! initial_value )
8104 fprintf (loop_dump_stream, "initial ");
8106 fprintf (loop_dump_stream, "increment ");
8107 if ( ! comparison_value )
8108 fprintf (loop_dump_stream, "comparison ");
8109 fprintf (loop_dump_stream, "\n");
8111 if (!invariant_p (comparison_value) || !invariant_p (increment))
8112 fprintf (loop_dump_stream, "\tloop bounds not invariant\n");
8117 /* make sure that the increment is constant */
8118 if (GET_CODE (increment) != CONST_INT) {
8119 if (loop_dump_stream)
8120 fprintf (loop_dump_stream,
8121 "analyze_loop_iterations %d: instrumentation failed: not arithmetic loop\n",
8126 /* make sure that the loop contains neither function call, nor jump on table.
8127 (the count register might be altered by the called function, and might
8128 be used for a branch on table). */
8129 for (insn = loop_start; insn && insn != loop_end; insn = NEXT_INSN (insn)) {
8130 if (GET_CODE (insn) == CALL_INSN){
8131 if (loop_dump_stream)
8132 fprintf (loop_dump_stream,
8133 "analyze_loop_iterations %d: BCT instrumentation failed: function call in the loop\n",
8138 if (GET_CODE (insn) == JUMP_INSN
8139 && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
8140 || GET_CODE (PATTERN (insn)) == ADDR_VEC)){
8141 if (loop_dump_stream)
8142 fprintf (loop_dump_stream,
8143 "analyze_loop_iterations %d: BCT instrumentation failed: computed branch in the loop\n",
8149 /* At this point, we are sure that the loop can be instrumented with BCT.
8150 Some of the loops, however, will not be instrumented - the final decision
8151 is taken by insert_bct () */
8152 if (loop_dump_stream)
8153 fprintf (loop_dump_stream,
8154 "analyze_loop_iterations: loop (luid =%d) can be BCT instrumented.\n",
8157 /* mark all enclosing loops that they cannot use count register */
8158 /* ???: In fact, since insert_bct may decide not to instrument this loop,
8159 marking here may prevent instrumenting an enclosing loop that could
8160 actually be instrumented. But since this is rare, it is safer to mark
8161 here in case the order of calling (analyze/insert)_bct would be changed. */
8162 for (i=loop_num; i != -1; i = loop_outer_loop[i])
8163 loop_used_count_register[i] = 1;
8165 /* Set data structures which will be used by the instrumentation phase */
8166 loop_start_value[loop_num] = initial_value;
8167 loop_comparison_value[loop_num] = comparison_value;
8168 loop_increment[loop_num] = increment;
8169 loop_comparison_code[loop_num] = comparison_code;
8170 loop_can_insert_bct[loop_num] = 1;
8174 /* instrument loop for insertion of bct instruction. We distinguish between
8175 loops with compile-time bounds, to those with run-time bounds. The loop
8176 behaviour is analized according to the following characteristics/variables:
8178 ; comparison-value: the value to which the iteration counter is compared.
8179 ; initial-value: iteration-counter initial value.
8180 ; increment: iteration-counter increment.
8181 ; Computed variables:
8182 ; increment-direction: the sign of the increment.
8183 ; compare-direction: '1' for GT, GTE, '-1' for LT, LTE, '0' for NE.
8184 ; range-direction: sign (comparison-value - initial-value)
8185 We give up on the following cases:
8186 ; loop variable overflow.
8187 ; run-time loop bounds with comparison code NE.
8191 insert_bct (loop_start, loop_end)
8192 rtx loop_start, loop_end;
8194 rtx initial_value, comparison_value, increment;
8195 enum rtx_code comparison_code;
8197 int increment_direction, compare_direction;
8200 /* if the loop condition is <= or >=, the number of iteration
8201 is 1 more than the range of the bounds of the loop */
8202 int add_iteration = 0;
8204 /* the only machine mode we work with - is the integer of the size that the
8206 enum machine_mode loop_var_mode = word_mode;
8208 int loop_num = uid_loop_num [INSN_UID (loop_start)];
8210 /* get loop-variables. No need to check that these are valid - already
8211 checked in analyze_loop_iterations (). */
8212 comparison_code = loop_comparison_code[loop_num];
8213 initial_value = loop_start_value[loop_num];
8214 comparison_value = loop_comparison_value[loop_num];
8215 increment = loop_increment[loop_num];
8217 /* check analyze_loop_iterations decision for this loop. */
8218 if (! loop_can_insert_bct[loop_num]){
8219 if (loop_dump_stream)
8220 fprintf (loop_dump_stream,
8221 "insert_bct: [%d] - was decided not to instrument by analyze_loop_iterations ()\n",
8226 /* It's impossible to instrument a competely unrolled loop. */
8227 if (loop_unroll_factor [loop_num] == -1)
8230 /* make sure that the last loop insn is a conditional jump .
8231 This check is repeated from analyze_loop_iterations (),
8232 because unrolling might have changed that. */
8233 if (GET_CODE (PREV_INSN (loop_end)) != JUMP_INSN
8234 || !condjump_p (PREV_INSN (loop_end))) {
8235 if (loop_dump_stream)
8236 fprintf (loop_dump_stream,
8237 "insert_bct: not instrumenting BCT because of invalid branch\n");
8241 /* fix increment in case loop was unrolled. */
8242 if (loop_unroll_factor [loop_num] > 1)
8243 increment = GEN_INT ( INTVAL (increment) * loop_unroll_factor [loop_num] );
8245 /* determine properties and directions of the loop */
8246 increment_direction = (INTVAL (increment) > 0) ? 1:-1;
8247 switch ( comparison_code ) {
8252 compare_direction = 1;
8259 compare_direction = -1;
8263 /* in this case we cannot know the number of iterations */
8264 if (loop_dump_stream)
8265 fprintf (loop_dump_stream,
8266 "insert_bct: %d: loop cannot be instrumented: == in condition\n",
8273 compare_direction = 1;
8279 compare_direction = -1;
8282 compare_direction = 0;
8289 /* make sure that the loop does not end by an overflow */
8290 if (compare_direction != increment_direction) {
8291 if (loop_dump_stream)
8292 fprintf (loop_dump_stream,
8293 "insert_bct: %d: loop cannot be instrumented: terminated by overflow\n",
8298 /* try to instrument the loop. */
8300 /* Handle the simpler case, where the bounds are known at compile time. */
8301 if (GET_CODE (initial_value) == CONST_INT
8302 && GET_CODE (comparison_value) == CONST_INT)
8305 int increment_value_abs = INTVAL (increment) * increment_direction;
8307 /* check the relation between compare-val and initial-val */
8308 int difference = INTVAL (comparison_value) - INTVAL (initial_value);
8309 int range_direction = (difference > 0) ? 1 : -1;
8311 /* make sure the loop executes enough iterations to gain from BCT */
8312 if (difference > -3 && difference < 3) {
8313 if (loop_dump_stream)
8314 fprintf (loop_dump_stream,
8315 "insert_bct: loop %d not BCT instrumented: too small iteration count.\n",
8320 /* make sure that the loop executes at least once */
8321 if ((range_direction == 1 && compare_direction == -1)
8322 || (range_direction == -1 && compare_direction == 1))
8324 if (loop_dump_stream)
8325 fprintf (loop_dump_stream,
8326 "insert_bct: loop %d: does not iterate even once. Not instrumenting.\n",
8331 /* make sure that the loop does not end by an overflow (in compile time
8332 bounds we must have an additional check for overflow, because here
8333 we also support the compare code of 'NE'. */
8334 if (comparison_code == NE
8335 && increment_direction != range_direction) {
8336 if (loop_dump_stream)
8337 fprintf (loop_dump_stream,
8338 "insert_bct (compile time bounds): %d: loop not instrumented: terminated by overflow\n",
8343 /* Determine the number of iterations by:
8345 ; compare-val - initial-val + (increment -1) + additional-iteration
8346 ; num_iterations = -----------------------------------------------------------------
8349 difference = (range_direction > 0) ? difference : -difference;
8351 fprintf (stderr, "difference is: %d\n", difference); /* @*/
8352 fprintf (stderr, "increment_value_abs is: %d\n", increment_value_abs); /* @*/
8353 fprintf (stderr, "add_iteration is: %d\n", add_iteration); /* @*/
8354 fprintf (stderr, "INTVAL (comparison_value) is: %d\n", INTVAL (comparison_value)); /* @*/
8355 fprintf (stderr, "INTVAL (initial_value) is: %d\n", INTVAL (initial_value)); /* @*/
8358 if (increment_value_abs == 0) {
8359 fprintf (stderr, "insert_bct: error: increment == 0 !!!\n");
8362 n_iterations = (difference + increment_value_abs - 1 + add_iteration)
8363 / increment_value_abs;
8366 fprintf (stderr, "number of iterations is: %d\n", n_iterations); /* @*/
8368 instrument_loop_bct (loop_start, loop_end, GEN_INT (n_iterations));
8370 /* Done with this loop. */
8374 /* Handle the more complex case, that the bounds are NOT known at compile time. */
8375 /* In this case we generate run_time calculation of the number of iterations */
8377 /* With runtime bounds, if the compare is of the form '!=' we give up */
8378 if (comparison_code == NE) {
8379 if (loop_dump_stream)
8380 fprintf (loop_dump_stream,
8381 "insert_bct: fail for loop %d: runtime bounds with != comparison\n",
8387 /* We rely on the existence of run-time guard to ensure that the
8388 loop executes at least once. */
8390 rtx iterations_num_reg;
8392 int increment_value_abs = INTVAL (increment) * increment_direction;
8394 /* make sure that the increment is a power of two, otherwise (an
8395 expensive) divide is needed. */
8396 if (exact_log2 (increment_value_abs) == -1)
8398 if (loop_dump_stream)
8399 fprintf (loop_dump_stream,
8400 "insert_bct: not instrumenting BCT because the increment is not power of 2\n");
8404 /* compute the number of iterations */
8409 /* Again, the number of iterations is calculated by:
8411 ; compare-val - initial-val + (increment -1) + additional-iteration
8412 ; num_iterations = -----------------------------------------------------------------
8415 /* ??? Do we have to call copy_rtx here before passing rtx to
8417 if (compare_direction > 0) {
8418 /* <, <= :the loop variable is increasing */
8419 temp_reg = expand_binop (loop_var_mode, sub_optab, comparison_value,
8420 initial_value, NULL_RTX, 0, OPTAB_LIB_WIDEN);
8423 temp_reg = expand_binop (loop_var_mode, sub_optab, initial_value,
8424 comparison_value, NULL_RTX, 0, OPTAB_LIB_WIDEN);
8427 if (increment_value_abs - 1 + add_iteration != 0)
8428 temp_reg = expand_binop (loop_var_mode, add_optab, temp_reg,
8429 GEN_INT (increment_value_abs - 1 + add_iteration),
8430 NULL_RTX, 0, OPTAB_LIB_WIDEN);
8432 if (increment_value_abs != 1)
8434 /* ??? This will generate an expensive divide instruction for
8435 most targets. The original authors apparently expected this
8436 to be a shift, since they test for power-of-2 divisors above,
8437 but just naively generating a divide instruction will not give
8438 a shift. It happens to work for the PowerPC target because
8439 the rs6000.md file has a divide pattern that emits shifts.
8440 It will probably not work for any other target. */
8441 iterations_num_reg = expand_binop (loop_var_mode, sdiv_optab,
8443 GEN_INT (increment_value_abs),
8444 NULL_RTX, 0, OPTAB_LIB_WIDEN);
8447 iterations_num_reg = temp_reg;
8449 sequence = gen_sequence ();
8451 emit_insn_before (sequence, loop_start);
8452 instrument_loop_bct (loop_start, loop_end, iterations_num_reg);
8456 /* instrument loop by inserting a bct in it. This is done in the following way:
8457 1. A new register is created and assigned the hard register number of the count
8459 2. In the head of the loop the new variable is initialized by the value passed in the
8460 loop_num_iterations parameter.
8461 3. At the end of the loop, comparison of the register with 0 is generated.
8462 The created comparison follows the pattern defined for the
8463 decrement_and_branch_on_count insn, so this insn will be generated in assembly
8465 4. The compare&branch on the old variable is deleted. So, if the loop-variable was
8466 not used elsewhere, it will be eliminated by data-flow analisys. */
8469 instrument_loop_bct (loop_start, loop_end, loop_num_iterations)
8470 rtx loop_start, loop_end;
8471 rtx loop_num_iterations;
8473 rtx temp_reg1, temp_reg2;
8477 enum machine_mode loop_var_mode = word_mode;
8479 if (HAVE_decrement_and_branch_on_count)
8481 if (loop_dump_stream)
8482 fprintf (loop_dump_stream, "Loop: Inserting BCT\n");
8484 /* Discard original jump to continue loop. Original compare result
8485 may still be live, so it cannot be discarded explicitly. */
8486 delete_insn (PREV_INSN (loop_end));
8488 /* insert the label which will delimit the start of the loop */
8489 start_label = gen_label_rtx ();
8490 emit_label_after (start_label, loop_start);
8492 /* insert initialization of the count register into the loop header */
8494 temp_reg1 = gen_reg_rtx (loop_var_mode);
8495 emit_insn (gen_move_insn (temp_reg1, loop_num_iterations));
8497 /* this will be count register */
8498 temp_reg2 = gen_rtx_REG (loop_var_mode, COUNT_REGISTER_REGNUM);
8499 /* we have to move the value to the count register from an GPR
8500 because rtx pointed to by loop_num_iterations could contain
8501 expression which cannot be moved into count register */
8502 emit_insn (gen_move_insn (temp_reg2, temp_reg1));
8504 sequence = gen_sequence ();
8506 emit_insn_before (sequence, loop_start);
8508 /* insert new comparison on the count register instead of the
8509 old one, generating the needed BCT pattern (that will be
8510 later recognized by assembly generation phase). */
8511 emit_jump_insn_before (gen_decrement_and_branch_on_count (temp_reg2,
8514 LABEL_NUSES (start_label)++;
8518 #endif /* HAVE_decrement_and_branch_on_count */
8522 /* Scan the function and determine whether it has indirect (computed) jumps.
8524 This is taken mostly from flow.c; similar code exists elsewhere
8525 in the compiler. It may be useful to put this into rtlanal.c. */
8527 indirect_jump_in_function_p (start)
8532 for (insn = start; insn; insn = NEXT_INSN (insn))
8533 if (computed_jump_p (insn))
8539 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8540 documentation for LOOP_MEMS for the definition of `appropriate'.
8541 This function is called from prescan_loop via for_each_rtx. */
8544 insert_loop_mem (mem, data)
8554 switch (GET_CODE (m))
8560 /* We're not interested in the MEM associated with a
8561 CONST_DOUBLE, so there's no need to traverse into this. */
8565 /* This is not a MEM. */
8569 /* See if we've already seen this MEM. */
8570 for (i = 0; i < loop_mems_idx; ++i)
8571 if (rtx_equal_p (m, loop_mems[i].mem))
8573 if (GET_MODE (m) != GET_MODE (loop_mems[i].mem))
8574 /* The modes of the two memory accesses are different. If
8575 this happens, something tricky is going on, and we just
8576 don't optimize accesses to this MEM. */
8577 loop_mems[i].optimize = 0;
8582 /* Resize the array, if necessary. */
8583 if (loop_mems_idx == loop_mems_allocated)
8585 if (loop_mems_allocated != 0)
8586 loop_mems_allocated *= 2;
8588 loop_mems_allocated = 32;
8590 loop_mems = (loop_mem_info*)
8591 xrealloc (loop_mems,
8592 loop_mems_allocated * sizeof (loop_mem_info));
8595 /* Actually insert the MEM. */
8596 loop_mems[loop_mems_idx].mem = m;
8597 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8598 because we can't put it in a register. We still store it in the
8599 table, though, so that if we see the same address later, but in a
8600 non-BLK mode, we'll not think we can optimize it at that point. */
8601 loop_mems[loop_mems_idx].optimize = (GET_MODE (m) != BLKmode);
8602 loop_mems[loop_mems_idx].reg = NULL_RTX;
8608 /* Like load_mems, but also ensures that N_TIMES_SET,
8609 MAY_NOT_OPTIMIZE, REG_SINGLE_USAGE, and INSN_COUNT have the correct
8610 values after load_mems. */
8613 load_mems_and_recount_loop_regs_set (scan_start, end, loop_top, start,
8614 reg_single_usage, insn_count)
8619 varray_type reg_single_usage;
8622 int nregs = max_reg_num ();
8624 load_mems (scan_start, end, loop_top, start);
8626 /* Recalculate n_times_set and friends since load_mems may have
8627 created new registers. */
8628 if (max_reg_num () > nregs)
8634 nregs = max_reg_num ();
8636 if (nregs > n_times_set->num_elements)
8638 /* Grow all the arrays. */
8639 VARRAY_GROW (n_times_set, nregs);
8640 VARRAY_GROW (n_times_used, nregs);
8641 VARRAY_GROW (may_not_optimize, nregs);
8642 if (reg_single_usage)
8643 VARRAY_GROW (reg_single_usage, nregs);
8645 /* Clear the arrays */
8646 bzero ((char *) &n_times_set->data, nregs * sizeof (int));
8647 bzero ((char *) &may_not_optimize->data, nregs * sizeof (char));
8648 if (reg_single_usage)
8649 bzero ((char *) ®_single_usage->data, nregs * sizeof (rtx));
8651 count_loop_regs_set (loop_top ? loop_top : start, end,
8652 may_not_optimize, reg_single_usage,
8655 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8657 VARRAY_CHAR (may_not_optimize, i) = 1;
8658 VARRAY_INT (n_times_set, i) = 1;
8661 #ifdef AVOID_CCMODE_COPIES
8662 /* Don't try to move insns which set CC registers if we should not
8663 create CCmode register copies. */
8664 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
8665 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
8666 VARRAY_CHAR (may_not_optimize, i) = 1;
8669 /* Set n_times_used for the new registers. */
8670 bcopy ((char *) (&n_times_set->data.i[0] + old_nregs),
8671 (char *) (&n_times_used->data.i[0] + old_nregs),
8672 (nregs - old_nregs) * sizeof (int));
8676 /* Move MEMs into registers for the duration of the loop. SCAN_START
8677 is the first instruction in the loop (as it is executed). The
8678 other parameters are as for next_insn_in_loop. */
8681 load_mems (scan_start, end, loop_top, start)
8687 int maybe_never = 0;
8690 rtx label = NULL_RTX;
8693 if (loop_mems_idx > 0)
8695 /* Nonzero if the next instruction may never be executed. */
8696 int next_maybe_never = 0;
8698 /* Check to see if it's possible that some instructions in the
8699 loop are never executed. */
8700 for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
8701 p != NULL_RTX && !maybe_never;
8702 p = next_insn_in_loop (p, scan_start, end, loop_top))
8704 if (GET_CODE (p) == CODE_LABEL)
8706 else if (GET_CODE (p) == JUMP_INSN
8707 /* If we enter the loop in the middle, and scan
8708 around to the beginning, don't set maybe_never
8709 for that. This must be an unconditional jump,
8710 otherwise the code at the top of the loop might
8711 never be executed. Unconditional jumps are
8712 followed a by barrier then loop end. */
8713 && ! (GET_CODE (p) == JUMP_INSN
8714 && JUMP_LABEL (p) == loop_top
8715 && NEXT_INSN (NEXT_INSN (p)) == end
8716 && simplejump_p (p)))
8718 if (!condjump_p (p))
8719 /* Something complicated. */
8722 /* If there are any more instructions in the loop, they
8723 might not be reached. */
8724 next_maybe_never = 1;
8726 else if (next_maybe_never)
8730 /* Actually move the MEMs. */
8731 for (i = 0; i < loop_mems_idx; ++i)
8736 rtx mem = loop_mems[i].mem;
8738 if (MEM_VOLATILE_P (mem)
8739 || invariant_p (XEXP (mem, 0)) != 1)
8740 /* There's no telling whether or not MEM is modified. */
8741 loop_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 for (j = 0; j < loop_store_mems_idx; ++j)
8747 if (rtx_equal_p (mem, loop_store_mems[j]))
8749 else if (true_dependence (loop_store_mems[j], VOIDmode,
8752 /* MEM is indeed aliased by this store. */
8753 loop_mems[i].optimize = 0;
8758 /* If this MEM is written to, we must be sure that there
8759 are no reads from another MEM that aliases this one. */
8760 if (loop_mems[i].optimize && written)
8764 for (j = 0; j < loop_mems_idx; ++j)
8768 else if (true_dependence (mem,
8773 /* It's not safe to hoist loop_mems[i] out of
8774 the loop because writes to it might not be
8775 seen by reads from loop_mems[j]. */
8776 loop_mems[i].optimize = 0;
8782 if (maybe_never && may_trap_p (mem))
8783 /* We can't access the MEM outside the loop; it might
8784 cause a trap that wouldn't have happened otherwise. */
8785 loop_mems[i].optimize = 0;
8787 if (!loop_mems[i].optimize)
8788 /* We thought we were going to lift this MEM out of the
8789 loop, but later discovered that we could not. */
8792 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8793 order to keep scan_loop from moving stores to this MEM
8794 out of the loop just because this REG is neither a
8795 user-variable nor used in the loop test. */
8796 reg = gen_reg_rtx (GET_MODE (mem));
8797 REG_USERVAR_P (reg) = 1;
8798 loop_mems[i].reg = reg;
8800 /* Now, replace all references to the MEM with the
8801 corresponding pesudos. */
8802 for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
8804 p = next_insn_in_loop (p, scan_start, end, loop_top))
8809 for_each_rtx (&p, replace_loop_mem, &ri);
8812 if (!apply_change_group ())
8813 /* We couldn't replace all occurrences of the MEM. */
8814 loop_mems[i].optimize = 0;
8819 /* Load the memory immediately before START, which is
8820 the NOTE_LOOP_BEG. */
8821 set = gen_rtx_SET (GET_MODE (reg), reg, mem);
8822 emit_insn_before (set, start);
8826 if (label == NULL_RTX)
8828 /* We must compute the former
8829 right-after-the-end label before we insert
8831 end_label = next_label (end);
8832 label = gen_label_rtx ();
8833 emit_label_after (label, end);
8836 /* Store the memory immediately after END, which is
8837 the NOTE_LOOP_END. */
8838 set = gen_rtx_SET (GET_MODE (reg), copy_rtx (mem), reg);
8839 emit_insn_after (set, label);
8842 if (loop_dump_stream)
8844 fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
8845 REGNO (reg), (written ? "r/w" : "r/o"));
8846 print_rtl (loop_dump_stream, mem);
8847 fputc ('\n', loop_dump_stream);
8853 if (label != NULL_RTX)
8855 /* Now, we need to replace all references to the previous exit
8856 label with the new one. */
8861 for (p = start; p != end; p = NEXT_INSN (p))
8863 for_each_rtx (&p, replace_label, &rr);
8865 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
8866 field. This is not handled by for_each_rtx because it doesn't
8867 handle unprinted ('0') fields. We need to update JUMP_LABEL
8868 because the immediately following unroll pass will use it.
8869 replace_label would not work anyways, because that only handles
8871 if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
8872 JUMP_LABEL (p) = label;
8877 /* Replace MEM with its associated pseudo register. This function is
8878 called from load_mems via for_each_rtx. DATA is actually an
8879 rtx_and_int * describing the instruction currently being scanned
8880 and the MEM we are currently replacing. */
8883 replace_loop_mem (mem, data)
8895 switch (GET_CODE (m))
8901 /* We're not interested in the MEM associated with a
8902 CONST_DOUBLE, so there's no need to traverse into one. */
8906 /* This is not a MEM. */
8910 ri = (rtx_and_int*) data;
8913 if (!rtx_equal_p (loop_mems[i].mem, m))
8914 /* This is not the MEM we are currently replacing. */
8919 /* Actually replace the MEM. */
8920 validate_change (insn, mem, loop_mems[i].reg, 1);
8925 /* Replace occurrences of the old exit label for the loop with the new
8926 one. DATA is an rtx_pair containing the old and new labels,
8930 replace_label (x, data)
8935 rtx old_label = ((rtx_pair*) data)->r1;
8936 rtx new_label = ((rtx_pair*) data)->r2;
8941 if (GET_CODE (l) != LABEL_REF)
8944 if (XEXP (l, 0) != old_label)
8947 XEXP (l, 0) = new_label;
8948 ++LABEL_NUSES (new_label);
8949 --LABEL_NUSES (old_label);