1 /* Perform various loop optimizations, including strength reduction.
2 Copyright (C) 1987, 88, 89, 91-98, 1999 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. */
85 #ifdef HAVE_decrement_and_branch_on_count
86 /* Records whether resource in use by inner loop. */
88 int *loop_used_count_register
;
89 #endif /* HAVE_decrement_and_branch_on_count */
91 /* Indexed by loop number, contains a nonzero value if the "loop" isn't
92 really a loop (an insn outside the loop branches into it). */
94 static char *loop_invalid
;
96 /* Indexed by loop number, links together all LABEL_REFs which refer to
97 code labels outside the loop. Used by routines that need to know all
98 loop exits, such as final_biv_value and final_giv_value.
100 This does not include loop exits due to return instructions. This is
101 because all bivs and givs are pseudos, and hence must be dead after a
102 return, so the presense of a return does not affect any of the
103 optimizations that use this info. It is simpler to just not include return
104 instructions on this list. */
106 rtx
*loop_number_exit_labels
;
108 /* Indexed by loop number, counts the number of LABEL_REFs on
109 loop_number_exit_labels for this loop and all loops nested inside it. */
111 int *loop_number_exit_count
;
113 /* Nonzero if there is a subroutine call in the current loop. */
115 static int loop_has_call
;
117 /* Nonzero if there is a volatile memory reference in the current
120 static int loop_has_volatile
;
122 /* Nonzero if there is a tablejump in the current loop. */
124 static int loop_has_tablejump
;
126 /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
127 current loop. A continue statement will generate a branch to
128 NEXT_INSN (loop_continue). */
130 static rtx loop_continue
;
132 /* Indexed by register number, contains the number of times the reg
133 is set during the loop being scanned.
134 During code motion, a negative value indicates a reg that has been
135 made a candidate; in particular -2 means that it is an candidate that
136 we know is equal to a constant and -1 means that it is an candidate
137 not known equal to a constant.
138 After code motion, regs moved have 0 (which is accurate now)
139 while the failed candidates have the original number of times set.
141 Therefore, at all times, == 0 indicates an invariant register;
142 < 0 a conditionally invariant one. */
144 static varray_type set_in_loop
;
146 /* Original value of set_in_loop; same except that this value
147 is not set negative for a reg whose sets have been made candidates
148 and not set to 0 for a reg that is moved. */
150 static varray_type n_times_set
;
152 /* Index by register number, 1 indicates that the register
153 cannot be moved or strength reduced. */
155 static varray_type may_not_optimize
;
157 /* Nonzero means reg N has already been moved out of one loop.
158 This reduces the desire to move it out of another. */
160 static char *moved_once
;
162 /* List of MEMs that are stored in this loop. */
164 static rtx loop_store_mems
;
166 typedef struct loop_mem_info
{
167 rtx mem
; /* The MEM itself. */
168 rtx reg
; /* Corresponding pseudo, if any. */
169 int optimize
; /* Nonzero if we can optimize access to this MEM. */
172 /* Array of MEMs that are used (read or written) in this loop, but
173 cannot be aliased by anything in this loop, except perhaps
174 themselves. In other words, if loop_mems[i] is altered during the
175 loop, it is altered by an expression that is rtx_equal_p to it. */
177 static loop_mem_info
*loop_mems
;
179 /* The index of the next available slot in LOOP_MEMS. */
181 static int loop_mems_idx
;
183 /* The number of elements allocated in LOOP_MEMs. */
185 static int loop_mems_allocated
;
187 /* Nonzero if we don't know what MEMs were changed in the current loop.
188 This happens if the loop contains a call (in which case `loop_has_call'
189 will also be set) or if we store into more than NUM_STORES MEMs. */
191 static int unknown_address_altered
;
193 /* Count of movable (i.e. invariant) instructions discovered in the loop. */
194 static int num_movables
;
196 /* Count of memory write instructions discovered in the loop. */
197 static int num_mem_sets
;
199 /* Number of loops contained within the current one, including itself. */
200 static int loops_enclosed
;
202 /* Bound on pseudo register number before loop optimization.
203 A pseudo has valid regscan info if its number is < max_reg_before_loop. */
204 int max_reg_before_loop
;
206 /* This obstack is used in product_cheap_p to allocate its rtl. It
207 may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
208 If we used the same obstack that it did, we would be deallocating
211 static struct obstack temp_obstack
;
213 /* This is where the pointer to the obstack being used for RTL is stored. */
215 extern struct obstack
*rtl_obstack
;
217 #define obstack_chunk_alloc xmalloc
218 #define obstack_chunk_free free
220 /* During the analysis of a loop, a chain of `struct movable's
221 is made to record all the movable insns found.
222 Then the entire chain can be scanned to decide which to move. */
226 rtx insn
; /* A movable insn */
227 rtx set_src
; /* The expression this reg is set from. */
228 rtx set_dest
; /* The destination of this SET. */
229 rtx dependencies
; /* When INSN is libcall, this is an EXPR_LIST
230 of any registers used within the LIBCALL. */
231 int consec
; /* Number of consecutive following insns
232 that must be moved with this one. */
233 int regno
; /* The register it sets */
234 short lifetime
; /* lifetime of that register;
235 may be adjusted when matching movables
236 that load the same value are found. */
237 short savings
; /* Number of insns we can move for this reg,
238 including other movables that force this
239 or match this one. */
240 unsigned int cond
: 1; /* 1 if only conditionally movable */
241 unsigned int force
: 1; /* 1 means MUST move this insn */
242 unsigned int global
: 1; /* 1 means reg is live outside this loop */
243 /* If PARTIAL is 1, GLOBAL means something different:
244 that the reg is live outside the range from where it is set
245 to the following label. */
246 unsigned int done
: 1; /* 1 inhibits further processing of this */
248 unsigned int partial
: 1; /* 1 means this reg is used for zero-extending.
249 In particular, moving it does not make it
251 unsigned int move_insn
: 1; /* 1 means that we call emit_move_insn to
252 load SRC, rather than copying INSN. */
253 unsigned int move_insn_first
:1;/* Same as above, if this is necessary for the
254 first insn of a consecutive sets group. */
255 unsigned int is_equiv
: 1; /* 1 means a REG_EQUIV is present on INSN. */
256 enum machine_mode savemode
; /* Nonzero means it is a mode for a low part
257 that we should avoid changing when clearing
258 the rest of the reg. */
259 struct movable
*match
; /* First entry for same value */
260 struct movable
*forces
; /* An insn that must be moved if this is */
261 struct movable
*next
;
264 static struct movable
*the_movables
;
266 FILE *loop_dump_stream
;
268 /* Forward declarations. */
270 static void find_and_verify_loops
PROTO((rtx
));
271 static void mark_loop_jump
PROTO((rtx
, int));
272 static void prescan_loop
PROTO((rtx
, rtx
));
273 static int reg_in_basic_block_p
PROTO((rtx
, rtx
));
274 static int consec_sets_invariant_p
PROTO((rtx
, int, rtx
));
275 static rtx libcall_other_reg
PROTO((rtx
, rtx
));
276 static int labels_in_range_p
PROTO((rtx
, int));
277 static void count_one_set
PROTO((rtx
, rtx
, varray_type
, rtx
*));
279 static void count_loop_regs_set
PROTO((rtx
, rtx
, varray_type
, varray_type
,
281 static void note_addr_stored
PROTO((rtx
, rtx
));
282 static int loop_reg_used_before_p
PROTO((rtx
, rtx
, rtx
, rtx
, rtx
));
283 static void scan_loop
PROTO((rtx
, rtx
, int, int));
285 static void replace_call_address
PROTO((rtx
, rtx
, rtx
));
287 static rtx skip_consec_insns
PROTO((rtx
, int));
288 static int libcall_benefit
PROTO((rtx
));
289 static void ignore_some_movables
PROTO((struct movable
*));
290 static void force_movables
PROTO((struct movable
*));
291 static void combine_movables
PROTO((struct movable
*, int));
292 static int regs_match_p
PROTO((rtx
, rtx
, struct movable
*));
293 static int rtx_equal_for_loop_p
PROTO((rtx
, rtx
, struct movable
*));
294 static void add_label_notes
PROTO((rtx
, rtx
));
295 static void move_movables
PROTO((struct movable
*, int, int, rtx
, rtx
, int));
296 static int count_nonfixed_reads
PROTO((rtx
));
297 static void strength_reduce
PROTO((rtx
, rtx
, rtx
, int, rtx
, rtx
, int, int));
298 static void find_single_use_in_loop
PROTO((rtx
, rtx
, varray_type
));
299 static int valid_initial_value_p
PROTO((rtx
, rtx
, int, rtx
));
300 static void find_mem_givs
PROTO((rtx
, rtx
, int, rtx
, rtx
));
301 static void record_biv
PROTO((struct induction
*, rtx
, rtx
, rtx
, rtx
, int, int));
302 static void check_final_value
PROTO((struct induction
*, rtx
, rtx
,
303 unsigned HOST_WIDE_INT
));
304 static void record_giv
PROTO((struct induction
*, rtx
, rtx
, rtx
, rtx
, rtx
, int, enum g_types
, int, rtx
*, rtx
, rtx
));
305 static void update_giv_derive
PROTO((rtx
));
306 static int basic_induction_var
PROTO((rtx
, enum machine_mode
, rtx
, rtx
, rtx
*, rtx
*));
307 static rtx simplify_giv_expr
PROTO((rtx
, int *));
308 static int general_induction_var
PROTO((rtx
, rtx
*, rtx
*, rtx
*, int, int *));
309 static int consec_sets_giv
PROTO((int, rtx
, rtx
, rtx
, rtx
*, rtx
*, rtx
*));
310 static int check_dbra_loop
PROTO((rtx
, int, rtx
, struct loop_info
*));
311 static rtx express_from_1
PROTO((rtx
, rtx
, rtx
));
312 static rtx express_from
PROTO((struct induction
*, struct induction
*));
313 static rtx combine_givs_p
PROTO((struct induction
*, struct induction
*));
314 static void combine_givs
PROTO((struct iv_class
*));
315 static int product_cheap_p
PROTO((rtx
, rtx
));
316 static int maybe_eliminate_biv
PROTO((struct iv_class
*, rtx
, rtx
, int, int, int));
317 static int maybe_eliminate_biv_1
PROTO((rtx
, rtx
, struct iv_class
*, int, rtx
));
318 static int last_use_this_basic_block
PROTO((rtx
, rtx
));
319 static void record_initial
PROTO((rtx
, rtx
));
320 static void update_reg_last_use
PROTO((rtx
, rtx
));
321 static rtx next_insn_in_loop
PROTO((rtx
, rtx
, rtx
, rtx
));
322 static void load_mems_and_recount_loop_regs_set
PROTO((rtx
, rtx
, rtx
,
325 static void load_mems
PROTO((rtx
, rtx
, rtx
, rtx
));
326 static int insert_loop_mem
PROTO((rtx
*, void *));
327 static int replace_loop_mem
PROTO((rtx
*, void *));
328 static int replace_label
PROTO((rtx
*, void *));
330 typedef struct rtx_and_int
{
335 typedef struct rtx_pair
{
340 /* Nonzero iff INSN is between START and END, inclusive. */
341 #define INSN_IN_RANGE_P(INSN, START, END) \
342 (INSN_UID (INSN) < max_uid_for_loop \
343 && INSN_LUID (INSN) >= INSN_LUID (START) \
344 && INSN_LUID (INSN) <= INSN_LUID (END))
346 #ifdef HAVE_decrement_and_branch_on_count
347 /* Test whether BCT applicable and safe. */
348 static void insert_bct
PROTO((rtx
, rtx
, struct loop_info
*));
350 /* Auxiliary function that inserts the BCT pattern into the loop. */
351 static void instrument_loop_bct
PROTO((rtx
, rtx
, rtx
));
352 #endif /* HAVE_decrement_and_branch_on_count */
354 /* Indirect_jump_in_function is computed once per function. */
355 int indirect_jump_in_function
= 0;
356 static int indirect_jump_in_function_p
PROTO((rtx
));
359 /* Relative gain of eliminating various kinds of operations. */
362 static int shift_cost
;
363 static int mult_cost
;
366 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
367 copy the value of the strength reduced giv to its original register. */
368 static int copy_cost
;
370 /* Cost of using a register, to normalize the benefits of a giv. */
371 static int reg_address_cost
;
377 char *free_point
= (char *) oballoc (1);
378 rtx reg
= gen_rtx_REG (word_mode
, LAST_VIRTUAL_REGISTER
+ 1);
380 add_cost
= rtx_cost (gen_rtx_PLUS (word_mode
, reg
, reg
), SET
);
383 reg_address_cost
= ADDRESS_COST (reg
);
385 reg_address_cost
= rtx_cost (reg
, MEM
);
388 /* We multiply by 2 to reconcile the difference in scale between
389 these two ways of computing costs. Otherwise the cost of a copy
390 will be far less than the cost of an add. */
394 /* Free the objects we just allocated. */
397 /* Initialize the obstack used for rtl in product_cheap_p. */
398 gcc_obstack_init (&temp_obstack
);
401 /* Entry point of this file. Perform loop optimization
402 on the current function. F is the first insn of the function
403 and DUMPFILE is a stream for output of a trace of actions taken
404 (or 0 if none should be output). */
407 loop_optimize (f
, dumpfile
, unroll_p
, bct_p
)
408 /* f is the first instruction of a chain of insns for one function */
417 loop_dump_stream
= dumpfile
;
419 init_recog_no_volatile ();
421 max_reg_before_loop
= max_reg_num ();
423 moved_once
= (char *) alloca (max_reg_before_loop
);
424 bzero (moved_once
, max_reg_before_loop
);
428 /* Count the number of loops. */
431 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
433 if (GET_CODE (insn
) == NOTE
434 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
438 /* Don't waste time if no loops. */
439 if (max_loop_num
== 0)
442 /* Get size to use for tables indexed by uids.
443 Leave some space for labels allocated by find_and_verify_loops. */
444 max_uid_for_loop
= get_max_uid () + 1 + max_loop_num
* 32;
446 uid_luid
= (int *) alloca (max_uid_for_loop
* sizeof (int));
447 uid_loop_num
= (int *) alloca (max_uid_for_loop
* sizeof (int));
449 bzero ((char *) uid_luid
, max_uid_for_loop
* sizeof (int));
450 bzero ((char *) uid_loop_num
, max_uid_for_loop
* sizeof (int));
452 /* Allocate tables for recording each loop. We set each entry, so they need
454 loop_number_loop_starts
= (rtx
*) alloca (max_loop_num
* sizeof (rtx
));
455 loop_number_loop_ends
= (rtx
*) alloca (max_loop_num
* sizeof (rtx
));
456 loop_outer_loop
= (int *) alloca (max_loop_num
* sizeof (int));
457 loop_invalid
= (char *) alloca (max_loop_num
* sizeof (char));
458 loop_number_exit_labels
= (rtx
*) alloca (max_loop_num
* sizeof (rtx
));
459 loop_number_exit_count
= (int *) alloca (max_loop_num
* sizeof (int));
461 #ifdef HAVE_decrement_and_branch_on_count
462 /* Allocate for BCT optimization */
463 loop_used_count_register
= (int *) alloca (max_loop_num
* sizeof (int));
464 bzero ((char *) loop_used_count_register
, max_loop_num
* sizeof (int));
465 #endif /* HAVE_decrement_and_branch_on_count */
467 /* Find and process each loop.
468 First, find them, and record them in order of their beginnings. */
469 find_and_verify_loops (f
);
471 /* Now find all register lifetimes. This must be done after
472 find_and_verify_loops, because it might reorder the insns in the
474 reg_scan (f
, max_reg_num (), 1);
476 /* This must occur after reg_scan so that registers created by gcse
477 will have entries in the register tables.
479 We could have added a call to reg_scan after gcse_main in toplev.c,
480 but moving this call to init_alias_analysis is more efficient. */
481 init_alias_analysis ();
483 /* See if we went too far. */
484 if (get_max_uid () > max_uid_for_loop
)
486 /* Now reset it to the actual size we need. See above. */
487 max_uid_for_loop
= get_max_uid () + 1;
489 /* Compute the mapping from uids to luids.
490 LUIDs are numbers assigned to insns, like uids,
491 except that luids increase monotonically through the code.
492 Don't assign luids to line-number NOTEs, so that the distance in luids
493 between two insns is not affected by -g. */
495 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
498 if (GET_CODE (insn
) != NOTE
499 || NOTE_LINE_NUMBER (insn
) <= 0)
500 uid_luid
[INSN_UID (insn
)] = ++i
;
502 /* Give a line number note the same luid as preceding insn. */
503 uid_luid
[INSN_UID (insn
)] = i
;
508 /* Don't leave gaps in uid_luid for insns that have been
509 deleted. It is possible that the first or last insn
510 using some register has been deleted by cross-jumping.
511 Make sure that uid_luid for that former insn's uid
512 points to the general area where that insn used to be. */
513 for (i
= 0; i
< max_uid_for_loop
; i
++)
515 uid_luid
[0] = uid_luid
[i
];
516 if (uid_luid
[0] != 0)
519 for (i
= 0; i
< max_uid_for_loop
; i
++)
520 if (uid_luid
[i
] == 0)
521 uid_luid
[i
] = uid_luid
[i
- 1];
523 /* Create a mapping from loops to BLOCK tree nodes. */
524 if (unroll_p
&& write_symbols
!= NO_DEBUG
)
525 find_loop_tree_blocks ();
527 /* Determine if the function has indirect jump. On some systems
528 this prevents low overhead loop instructions from being used. */
529 indirect_jump_in_function
= indirect_jump_in_function_p (f
);
531 /* Now scan the loops, last ones first, since this means inner ones are done
532 before outer ones. */
533 for (i
= max_loop_num
-1; i
>= 0; i
--)
534 if (! loop_invalid
[i
] && loop_number_loop_ends
[i
])
535 scan_loop (loop_number_loop_starts
[i
], loop_number_loop_ends
[i
],
538 /* If debugging and unrolling loops, we must replicate the tree nodes
539 corresponding to the blocks inside the loop, so that the original one
540 to one mapping will remain. */
541 if (unroll_p
&& write_symbols
!= NO_DEBUG
)
542 unroll_block_trees ();
544 end_alias_analysis ();
547 /* Returns the next insn, in execution order, after INSN. START and
548 END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
549 respectively. LOOP_TOP, if non-NULL, is the top of the loop in the
550 insn-stream; it is used with loops that are entered near the
554 next_insn_in_loop (insn
, start
, end
, loop_top
)
560 insn
= NEXT_INSN (insn
);
565 /* Go to the top of the loop, and continue there. */
579 /* Optimize one loop whose start is LOOP_START and end is END.
580 LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
581 NOTE_INSN_LOOP_END. */
583 /* ??? Could also move memory writes out of loops if the destination address
584 is invariant, the source is invariant, the memory write is not volatile,
585 and if we can prove that no read inside the loop can read this address
586 before the write occurs. If there is a read of this address after the
587 write, then we can also mark the memory read as invariant. */
590 scan_loop (loop_start
, end
, unroll_p
, bct_p
)
596 /* 1 if we are scanning insns that could be executed zero times. */
598 /* 1 if we are scanning insns that might never be executed
599 due to a subroutine call which might exit before they are reached. */
601 /* For a rotated loop that is entered near the bottom,
602 this is the label at the top. Otherwise it is zero. */
604 /* Jump insn that enters the loop, or 0 if control drops in. */
605 rtx loop_entry_jump
= 0;
606 /* Place in the loop where control enters. */
608 /* Number of insns in the loop. */
613 /* The SET from an insn, if it is the only SET in the insn. */
615 /* Chain describing insns movable in current loop. */
616 struct movable
*movables
= 0;
617 /* Last element in `movables' -- so we can add elements at the end. */
618 struct movable
*last_movable
= 0;
619 /* Ratio of extra register life span we can justify
620 for saving an instruction. More if loop doesn't call subroutines
621 since in that case saving an insn makes more difference
622 and more registers are available. */
624 /* If we have calls, contains the insn in which a register was used
625 if it was used exactly once; contains const0_rtx if it was used more
627 varray_type reg_single_usage
= 0;
628 /* Nonzero if we are scanning instructions in a sub-loop. */
632 /* Determine whether this loop starts with a jump down to a test at
633 the end. This will occur for a small number of loops with a test
634 that is too complex to duplicate in front of the loop.
636 We search for the first insn or label in the loop, skipping NOTEs.
637 However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
638 (because we might have a loop executed only once that contains a
639 loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
640 (in case we have a degenerate loop).
642 Note that if we mistakenly think that a loop is entered at the top
643 when, in fact, it is entered at the exit test, the only effect will be
644 slightly poorer optimization. Making the opposite error can generate
645 incorrect code. Since very few loops now start with a jump to the
646 exit test, the code here to detect that case is very conservative. */
648 for (p
= NEXT_INSN (loop_start
);
650 && GET_CODE (p
) != CODE_LABEL
&& GET_RTX_CLASS (GET_CODE (p
)) != 'i'
651 && (GET_CODE (p
) != NOTE
652 || (NOTE_LINE_NUMBER (p
) != NOTE_INSN_LOOP_BEG
653 && NOTE_LINE_NUMBER (p
) != NOTE_INSN_LOOP_END
));
659 /* Set up variables describing this loop. */
660 prescan_loop (loop_start
, end
);
661 threshold
= (loop_has_call
? 1 : 2) * (1 + n_non_fixed_regs
);
663 /* If loop has a jump before the first label,
664 the true entry is the target of that jump.
665 Start scan from there.
666 But record in LOOP_TOP the place where the end-test jumps
667 back to so we can scan that after the end of the loop. */
668 if (GET_CODE (p
) == JUMP_INSN
)
672 /* Loop entry must be unconditional jump (and not a RETURN) */
674 && JUMP_LABEL (p
) != 0
675 /* Check to see whether the jump actually
676 jumps out of the loop (meaning it's no loop).
677 This case can happen for things like
678 do {..} while (0). If this label was generated previously
679 by loop, we can't tell anything about it and have to reject
681 && INSN_IN_RANGE_P (JUMP_LABEL (p
), loop_start
, end
))
683 loop_top
= next_label (scan_start
);
684 scan_start
= JUMP_LABEL (p
);
688 /* If SCAN_START was an insn created by loop, we don't know its luid
689 as required by loop_reg_used_before_p. So skip such loops. (This
690 test may never be true, but it's best to play it safe.)
692 Also, skip loops where we do not start scanning at a label. This
693 test also rejects loops starting with a JUMP_INSN that failed the
696 if (INSN_UID (scan_start
) >= max_uid_for_loop
697 || GET_CODE (scan_start
) != CODE_LABEL
)
699 if (loop_dump_stream
)
700 fprintf (loop_dump_stream
, "\nLoop from %d to %d is phony.\n\n",
701 INSN_UID (loop_start
), INSN_UID (end
));
705 /* Count number of times each reg is set during this loop.
706 Set VARRAY_CHAR (may_not_optimize, I) if it is not safe to move out
707 the setting of register I. If this loop has calls, set
708 VARRAY_RTX (reg_single_usage, I). */
710 /* Allocate extra space for REGS that might be created by
711 load_mems. We allocate a little extra slop as well, in the hopes
712 that even after the moving of movables creates some new registers
713 we won't have to reallocate these arrays. However, we do grow
714 the arrays, if necessary, in load_mems_recount_loop_regs_set. */
715 nregs
= max_reg_num () + loop_mems_idx
+ 16;
716 VARRAY_INT_INIT (set_in_loop
, nregs
, "set_in_loop");
717 VARRAY_INT_INIT (n_times_set
, nregs
, "n_times_set");
718 VARRAY_CHAR_INIT (may_not_optimize
, nregs
, "may_not_optimize");
721 VARRAY_RTX_INIT (reg_single_usage
, nregs
, "reg_single_usage");
723 count_loop_regs_set (loop_top
? loop_top
: loop_start
, end
,
724 may_not_optimize
, reg_single_usage
, &insn_count
, nregs
);
726 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
728 VARRAY_CHAR (may_not_optimize
, i
) = 1;
729 VARRAY_INT (set_in_loop
, i
) = 1;
732 #ifdef AVOID_CCMODE_COPIES
733 /* Don't try to move insns which set CC registers if we should not
734 create CCmode register copies. */
735 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
736 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx
[i
])) == MODE_CC
)
737 VARRAY_CHAR (may_not_optimize
, i
) = 1;
740 bcopy ((char *) &set_in_loop
->data
,
741 (char *) &n_times_set
->data
, nregs
* sizeof (int));
743 if (loop_dump_stream
)
745 fprintf (loop_dump_stream
, "\nLoop from %d to %d: %d real insns.\n",
746 INSN_UID (loop_start
), INSN_UID (end
), insn_count
);
748 fprintf (loop_dump_stream
, "Continue at insn %d.\n",
749 INSN_UID (loop_continue
));
752 /* Scan through the loop finding insns that are safe to move.
753 Set set_in_loop negative for the reg being set, so that
754 this reg will be considered invariant for subsequent insns.
755 We consider whether subsequent insns use the reg
756 in deciding whether it is worth actually moving.
758 MAYBE_NEVER is nonzero if we have passed a conditional jump insn
759 and therefore it is possible that the insns we are scanning
760 would never be executed. At such times, we must make sure
761 that it is safe to execute the insn once instead of zero times.
762 When MAYBE_NEVER is 0, all insns will be executed at least once
763 so that is not a problem. */
765 for (p
= next_insn_in_loop (scan_start
, scan_start
, end
, loop_top
);
767 p
= next_insn_in_loop (p
, scan_start
, end
, loop_top
))
769 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i'
770 && find_reg_note (p
, REG_LIBCALL
, NULL_RTX
))
772 else if (GET_RTX_CLASS (GET_CODE (p
)) == 'i'
773 && find_reg_note (p
, REG_RETVAL
, NULL_RTX
))
776 if (GET_CODE (p
) == INSN
777 && (set
= single_set (p
))
778 && GET_CODE (SET_DEST (set
)) == REG
779 && ! VARRAY_CHAR (may_not_optimize
, REGNO (SET_DEST (set
))))
784 rtx src
= SET_SRC (set
);
785 rtx dependencies
= 0;
787 /* Figure out what to use as a source of this insn. If a REG_EQUIV
788 note is given or if a REG_EQUAL note with a constant operand is
789 specified, use it as the source and mark that we should move
790 this insn by calling emit_move_insn rather that duplicating the
793 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
795 temp
= find_reg_note (p
, REG_EQUIV
, NULL_RTX
);
797 src
= XEXP (temp
, 0), move_insn
= 1;
800 temp
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
);
801 if (temp
&& CONSTANT_P (XEXP (temp
, 0)))
802 src
= XEXP (temp
, 0), move_insn
= 1;
803 if (temp
&& find_reg_note (p
, REG_RETVAL
, NULL_RTX
))
805 src
= XEXP (temp
, 0);
806 /* A libcall block can use regs that don't appear in
807 the equivalent expression. To move the libcall,
808 we must move those regs too. */
809 dependencies
= libcall_other_reg (p
, src
);
813 /* Don't try to optimize a register that was made
814 by loop-optimization for an inner loop.
815 We don't know its life-span, so we can't compute the benefit. */
816 if (REGNO (SET_DEST (set
)) >= max_reg_before_loop
)
818 else if (/* The set is not guaranteed to be executed one
819 the loop starts, or the value before the set is
820 needed before the set occurs... */
822 || loop_reg_used_before_p (set
, p
, loop_start
,
824 /* And the register is used in basic blocks other
825 than the one where it is set (meaning that
826 something after this point in the loop might
827 depend on its value before the set). */
828 && !reg_in_basic_block_p (p
, SET_DEST (set
)))
829 /* It is unsafe to move the set.
831 This code used to consider it OK to move a set of a variable
832 which was not created by the user and not used in an exit test.
833 That behavior is incorrect and was removed. */
835 else if ((tem
= invariant_p (src
))
836 && (dependencies
== 0
837 || (tem2
= invariant_p (dependencies
)) != 0)
838 && (VARRAY_INT (set_in_loop
,
839 REGNO (SET_DEST (set
))) == 1
841 = consec_sets_invariant_p
843 VARRAY_INT (set_in_loop
, REGNO (SET_DEST (set
))),
845 /* If the insn can cause a trap (such as divide by zero),
846 can't move it unless it's guaranteed to be executed
847 once loop is entered. Even a function call might
848 prevent the trap insn from being reached
849 (since it might exit!) */
850 && ! ((maybe_never
|| call_passed
)
851 && may_trap_p (src
)))
853 register struct movable
*m
;
854 register int regno
= REGNO (SET_DEST (set
));
856 /* A potential lossage is where we have a case where two insns
857 can be combined as long as they are both in the loop, but
858 we move one of them outside the loop. For large loops,
859 this can lose. The most common case of this is the address
860 of a function being called.
862 Therefore, if this register is marked as being used exactly
863 once if we are in a loop with calls (a "large loop"), see if
864 we can replace the usage of this register with the source
865 of this SET. If we can, delete this insn.
867 Don't do this if P has a REG_RETVAL note or if we have
868 SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
870 if (reg_single_usage
&& VARRAY_RTX (reg_single_usage
, regno
) != 0
871 && VARRAY_RTX (reg_single_usage
, regno
) != const0_rtx
872 && REGNO_FIRST_UID (regno
) == INSN_UID (p
)
873 && (REGNO_LAST_UID (regno
)
874 == INSN_UID (VARRAY_RTX (reg_single_usage
, regno
)))
875 && VARRAY_INT (set_in_loop
, regno
) == 1
876 && ! side_effects_p (SET_SRC (set
))
877 && ! find_reg_note (p
, REG_RETVAL
, NULL_RTX
)
878 && (! SMALL_REGISTER_CLASSES
879 || (! (GET_CODE (SET_SRC (set
)) == REG
880 && REGNO (SET_SRC (set
)) < FIRST_PSEUDO_REGISTER
)))
881 /* This test is not redundant; SET_SRC (set) might be
882 a call-clobbered register and the life of REGNO
883 might span a call. */
884 && ! modified_between_p (SET_SRC (set
), p
,
886 (reg_single_usage
, regno
))
887 && no_labels_between_p (p
, VARRAY_RTX (reg_single_usage
, regno
))
888 && validate_replace_rtx (SET_DEST (set
), SET_SRC (set
),
890 (reg_single_usage
, regno
)))
892 /* Replace any usage in a REG_EQUAL note. Must copy the
893 new source, so that we don't get rtx sharing between the
894 SET_SOURCE and REG_NOTES of insn p. */
895 REG_NOTES (VARRAY_RTX (reg_single_usage
, regno
))
896 = replace_rtx (REG_NOTES (VARRAY_RTX
897 (reg_single_usage
, regno
)),
898 SET_DEST (set
), copy_rtx (SET_SRC (set
)));
901 NOTE_LINE_NUMBER (p
) = NOTE_INSN_DELETED
;
902 NOTE_SOURCE_FILE (p
) = 0;
903 VARRAY_INT (set_in_loop
, regno
) = 0;
907 m
= (struct movable
*) alloca (sizeof (struct movable
));
911 m
->dependencies
= dependencies
;
912 m
->set_dest
= SET_DEST (set
);
914 m
->consec
= VARRAY_INT (set_in_loop
,
915 REGNO (SET_DEST (set
))) - 1;
919 m
->move_insn
= move_insn
;
920 m
->move_insn_first
= 0;
921 m
->is_equiv
= (find_reg_note (p
, REG_EQUIV
, NULL_RTX
) != 0);
922 m
->savemode
= VOIDmode
;
924 /* Set M->cond if either invariant_p or consec_sets_invariant_p
925 returned 2 (only conditionally invariant). */
926 m
->cond
= ((tem
| tem1
| tem2
) > 1);
927 m
->global
= (uid_luid
[REGNO_LAST_UID (regno
)] > INSN_LUID (end
)
928 || uid_luid
[REGNO_FIRST_UID (regno
)] < INSN_LUID (loop_start
));
930 m
->lifetime
= (uid_luid
[REGNO_LAST_UID (regno
)]
931 - uid_luid
[REGNO_FIRST_UID (regno
)]);
932 m
->savings
= VARRAY_INT (n_times_set
, regno
);
933 if (find_reg_note (p
, REG_RETVAL
, NULL_RTX
))
934 m
->savings
+= libcall_benefit (p
);
935 VARRAY_INT (set_in_loop
, regno
) = move_insn
? -2 : -1;
936 /* Add M to the end of the chain MOVABLES. */
940 last_movable
->next
= m
;
945 /* It is possible for the first instruction to have a
946 REG_EQUAL note but a non-invariant SET_SRC, so we must
947 remember the status of the first instruction in case
948 the last instruction doesn't have a REG_EQUAL note. */
949 m
->move_insn_first
= m
->move_insn
;
951 /* Skip this insn, not checking REG_LIBCALL notes. */
952 p
= next_nonnote_insn (p
);
953 /* Skip the consecutive insns, if there are any. */
954 p
= skip_consec_insns (p
, m
->consec
);
955 /* Back up to the last insn of the consecutive group. */
956 p
= prev_nonnote_insn (p
);
958 /* We must now reset m->move_insn, m->is_equiv, and possibly
959 m->set_src to correspond to the effects of all the
961 temp
= find_reg_note (p
, REG_EQUIV
, NULL_RTX
);
963 m
->set_src
= XEXP (temp
, 0), m
->move_insn
= 1;
966 temp
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
);
967 if (temp
&& CONSTANT_P (XEXP (temp
, 0)))
968 m
->set_src
= XEXP (temp
, 0), m
->move_insn
= 1;
973 m
->is_equiv
= (find_reg_note (p
, REG_EQUIV
, NULL_RTX
) != 0);
976 /* If this register is always set within a STRICT_LOW_PART
977 or set to zero, then its high bytes are constant.
978 So clear them outside the loop and within the loop
979 just load the low bytes.
980 We must check that the machine has an instruction to do so.
981 Also, if the value loaded into the register
982 depends on the same register, this cannot be done. */
983 else if (SET_SRC (set
) == const0_rtx
984 && GET_CODE (NEXT_INSN (p
)) == INSN
985 && (set1
= single_set (NEXT_INSN (p
)))
986 && GET_CODE (set1
) == SET
987 && (GET_CODE (SET_DEST (set1
)) == STRICT_LOW_PART
)
988 && (GET_CODE (XEXP (SET_DEST (set1
), 0)) == SUBREG
)
989 && (SUBREG_REG (XEXP (SET_DEST (set1
), 0))
991 && !reg_mentioned_p (SET_DEST (set
), SET_SRC (set1
)))
993 register int regno
= REGNO (SET_DEST (set
));
994 if (VARRAY_INT (set_in_loop
, regno
) == 2)
996 register struct movable
*m
;
997 m
= (struct movable
*) alloca (sizeof (struct movable
));
1000 m
->set_dest
= SET_DEST (set
);
1001 m
->dependencies
= 0;
1007 m
->move_insn_first
= 0;
1009 /* If the insn may not be executed on some cycles,
1010 we can't clear the whole reg; clear just high part.
1011 Not even if the reg is used only within this loop.
1018 Clearing x before the inner loop could clobber a value
1019 being saved from the last time around the outer loop.
1020 However, if the reg is not used outside this loop
1021 and all uses of the register are in the same
1022 basic block as the store, there is no problem.
1024 If this insn was made by loop, we don't know its
1025 INSN_LUID and hence must make a conservative
1027 m
->global
= (INSN_UID (p
) >= max_uid_for_loop
1028 || (uid_luid
[REGNO_LAST_UID (regno
)]
1030 || (uid_luid
[REGNO_FIRST_UID (regno
)]
1032 || (labels_in_range_p
1033 (p
, uid_luid
[REGNO_FIRST_UID (regno
)])));
1034 if (maybe_never
&& m
->global
)
1035 m
->savemode
= GET_MODE (SET_SRC (set1
));
1037 m
->savemode
= VOIDmode
;
1041 m
->lifetime
= (uid_luid
[REGNO_LAST_UID (regno
)]
1042 - uid_luid
[REGNO_FIRST_UID (regno
)]);
1044 VARRAY_INT (set_in_loop
, regno
) = -1;
1045 /* Add M to the end of the chain MOVABLES. */
1049 last_movable
->next
= m
;
1054 /* Past a call insn, we get to insns which might not be executed
1055 because the call might exit. This matters for insns that trap.
1056 Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
1057 so they don't count. */
1058 else if (GET_CODE (p
) == CALL_INSN
&& ! in_libcall
)
1060 /* Past a label or a jump, we get to insns for which we
1061 can't count on whether or how many times they will be
1062 executed during each iteration. Therefore, we can
1063 only move out sets of trivial variables
1064 (those not used after the loop). */
1065 /* Similar code appears twice in strength_reduce. */
1066 else if ((GET_CODE (p
) == CODE_LABEL
|| GET_CODE (p
) == JUMP_INSN
)
1067 /* If we enter the loop in the middle, and scan around to the
1068 beginning, don't set maybe_never for that. This must be an
1069 unconditional jump, otherwise the code at the top of the
1070 loop might never be executed. Unconditional jumps are
1071 followed a by barrier then loop end. */
1072 && ! (GET_CODE (p
) == JUMP_INSN
&& JUMP_LABEL (p
) == loop_top
1073 && NEXT_INSN (NEXT_INSN (p
)) == end
1074 && simplejump_p (p
)))
1076 else if (GET_CODE (p
) == NOTE
)
1078 /* At the virtual top of a converted loop, insns are again known to
1079 be executed: logically, the loop begins here even though the exit
1080 code has been duplicated. */
1081 if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_VTOP
&& loop_depth
== 0)
1082 maybe_never
= call_passed
= 0;
1083 else if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_BEG
)
1085 else if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_END
)
1090 /* If one movable subsumes another, ignore that other. */
1092 ignore_some_movables (movables
);
1094 /* For each movable insn, see if the reg that it loads
1095 leads when it dies right into another conditionally movable insn.
1096 If so, record that the second insn "forces" the first one,
1097 since the second can be moved only if the first is. */
1099 force_movables (movables
);
1101 /* See if there are multiple movable insns that load the same value.
1102 If there are, make all but the first point at the first one
1103 through the `match' field, and add the priorities of them
1104 all together as the priority of the first. */
1106 combine_movables (movables
, nregs
);
1108 /* Now consider each movable insn to decide whether it is worth moving.
1109 Store 0 in set_in_loop for each reg that is moved.
1111 Generally this increases code size, so do not move moveables when
1112 optimizing for code size. */
1114 if (! optimize_size
)
1115 move_movables (movables
, threshold
,
1116 insn_count
, loop_start
, end
, nregs
);
1118 /* Now candidates that still are negative are those not moved.
1119 Change set_in_loop to indicate that those are not actually invariant. */
1120 for (i
= 0; i
< nregs
; i
++)
1121 if (VARRAY_INT (set_in_loop
, i
) < 0)
1122 VARRAY_INT (set_in_loop
, i
) = VARRAY_INT (n_times_set
, i
);
1124 /* Now that we've moved some things out of the loop, we able to
1125 hoist even more memory references. There's no need to pass
1126 reg_single_usage this time, since we're done with it. */
1127 load_mems_and_recount_loop_regs_set (scan_start
, end
, loop_top
,
1131 /* set_in_loop is still used by invariant_p, so we can't free it now. */
1132 VARRAY_FREE (reg_single_usage
);
1134 if (flag_strength_reduce
)
1136 the_movables
= movables
;
1137 strength_reduce (scan_start
, end
, loop_top
,
1138 insn_count
, loop_start
, end
, unroll_p
, bct_p
);
1141 VARRAY_FREE (set_in_loop
);
1142 VARRAY_FREE (n_times_set
);
1143 VARRAY_FREE (may_not_optimize
);
1146 /* Add elements to *OUTPUT to record all the pseudo-regs
1147 mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
1150 record_excess_regs (in_this
, not_in_this
, output
)
1151 rtx in_this
, not_in_this
;
1158 code
= GET_CODE (in_this
);
1172 if (REGNO (in_this
) >= FIRST_PSEUDO_REGISTER
1173 && ! reg_mentioned_p (in_this
, not_in_this
))
1174 *output
= gen_rtx_EXPR_LIST (VOIDmode
, in_this
, *output
);
1181 fmt
= GET_RTX_FORMAT (code
);
1182 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1189 for (j
= 0; j
< XVECLEN (in_this
, i
); j
++)
1190 record_excess_regs (XVECEXP (in_this
, i
, j
), not_in_this
, output
);
1194 record_excess_regs (XEXP (in_this
, i
), not_in_this
, output
);
1200 /* Check what regs are referred to in the libcall block ending with INSN,
1201 aside from those mentioned in the equivalent value.
1202 If there are none, return 0.
1203 If there are one or more, return an EXPR_LIST containing all of them. */
1206 libcall_other_reg (insn
, equiv
)
1209 rtx note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
1210 rtx p
= XEXP (note
, 0);
1213 /* First, find all the regs used in the libcall block
1214 that are not mentioned as inputs to the result. */
1218 if (GET_CODE (p
) == INSN
|| GET_CODE (p
) == JUMP_INSN
1219 || GET_CODE (p
) == CALL_INSN
)
1220 record_excess_regs (PATTERN (p
), equiv
, &output
);
1227 /* Return 1 if all uses of REG
1228 are between INSN and the end of the basic block. */
1231 reg_in_basic_block_p (insn
, reg
)
1234 int regno
= REGNO (reg
);
1237 if (REGNO_FIRST_UID (regno
) != INSN_UID (insn
))
1240 /* Search this basic block for the already recorded last use of the reg. */
1241 for (p
= insn
; p
; p
= NEXT_INSN (p
))
1243 switch (GET_CODE (p
))
1250 /* Ordinary insn: if this is the last use, we win. */
1251 if (REGNO_LAST_UID (regno
) == INSN_UID (p
))
1256 /* Jump insn: if this is the last use, we win. */
1257 if (REGNO_LAST_UID (regno
) == INSN_UID (p
))
1259 /* Otherwise, it's the end of the basic block, so we lose. */
1264 /* It's the end of the basic block, so we lose. */
1272 /* The "last use" doesn't follow the "first use"?? */
1276 /* Compute the benefit of eliminating the insns in the block whose
1277 last insn is LAST. This may be a group of insns used to compute a
1278 value directly or can contain a library call. */
1281 libcall_benefit (last
)
1287 for (insn
= XEXP (find_reg_note (last
, REG_RETVAL
, NULL_RTX
), 0);
1288 insn
!= last
; insn
= NEXT_INSN (insn
))
1290 if (GET_CODE (insn
) == CALL_INSN
)
1291 benefit
+= 10; /* Assume at least this many insns in a library
1293 else if (GET_CODE (insn
) == INSN
1294 && GET_CODE (PATTERN (insn
)) != USE
1295 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
1302 /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1305 skip_consec_insns (insn
, count
)
1309 for (; count
> 0; count
--)
1313 /* If first insn of libcall sequence, skip to end. */
1314 /* Do this at start of loop, since INSN is guaranteed to
1316 if (GET_CODE (insn
) != NOTE
1317 && (temp
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)))
1318 insn
= XEXP (temp
, 0);
1320 do insn
= NEXT_INSN (insn
);
1321 while (GET_CODE (insn
) == NOTE
);
1327 /* Ignore any movable whose insn falls within a libcall
1328 which is part of another movable.
1329 We make use of the fact that the movable for the libcall value
1330 was made later and so appears later on the chain. */
1333 ignore_some_movables (movables
)
1334 struct movable
*movables
;
1336 register struct movable
*m
, *m1
;
1338 for (m
= movables
; m
; m
= m
->next
)
1340 /* Is this a movable for the value of a libcall? */
1341 rtx note
= find_reg_note (m
->insn
, REG_RETVAL
, NULL_RTX
);
1345 /* Check for earlier movables inside that range,
1346 and mark them invalid. We cannot use LUIDs here because
1347 insns created by loop.c for prior loops don't have LUIDs.
1348 Rather than reject all such insns from movables, we just
1349 explicitly check each insn in the libcall (since invariant
1350 libcalls aren't that common). */
1351 for (insn
= XEXP (note
, 0); insn
!= m
->insn
; insn
= NEXT_INSN (insn
))
1352 for (m1
= movables
; m1
!= m
; m1
= m1
->next
)
1353 if (m1
->insn
== insn
)
1359 /* For each movable insn, see if the reg that it loads
1360 leads when it dies right into another conditionally movable insn.
1361 If so, record that the second insn "forces" the first one,
1362 since the second can be moved only if the first is. */
1365 force_movables (movables
)
1366 struct movable
*movables
;
1368 register struct movable
*m
, *m1
;
1369 for (m1
= movables
; m1
; m1
= m1
->next
)
1370 /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1371 if (!m1
->partial
&& !m1
->done
)
1373 int regno
= m1
->regno
;
1374 for (m
= m1
->next
; m
; m
= m
->next
)
1375 /* ??? Could this be a bug? What if CSE caused the
1376 register of M1 to be used after this insn?
1377 Since CSE does not update regno_last_uid,
1378 this insn M->insn might not be where it dies.
1379 But very likely this doesn't matter; what matters is
1380 that M's reg is computed from M1's reg. */
1381 if (INSN_UID (m
->insn
) == REGNO_LAST_UID (regno
)
1384 if (m
!= 0 && m
->set_src
== m1
->set_dest
1385 /* If m->consec, m->set_src isn't valid. */
1389 /* Increase the priority of the moving the first insn
1390 since it permits the second to be moved as well. */
1394 m1
->lifetime
+= m
->lifetime
;
1395 m1
->savings
+= m
->savings
;
1400 /* Find invariant expressions that are equal and can be combined into
1404 combine_movables (movables
, nregs
)
1405 struct movable
*movables
;
1408 register struct movable
*m
;
1409 char *matched_regs
= (char *) alloca (nregs
);
1410 enum machine_mode mode
;
1412 /* Regs that are set more than once are not allowed to match
1413 or be matched. I'm no longer sure why not. */
1414 /* Perhaps testing m->consec_sets would be more appropriate here? */
1416 for (m
= movables
; m
; m
= m
->next
)
1417 if (m
->match
== 0 && VARRAY_INT (n_times_set
, m
->regno
) == 1 && !m
->partial
)
1419 register struct movable
*m1
;
1420 int regno
= m
->regno
;
1422 bzero (matched_regs
, nregs
);
1423 matched_regs
[regno
] = 1;
1425 /* We want later insns to match the first one. Don't make the first
1426 one match any later ones. So start this loop at m->next. */
1427 for (m1
= m
->next
; m1
; m1
= m1
->next
)
1428 if (m
!= m1
&& m1
->match
== 0 && VARRAY_INT (n_times_set
, m1
->regno
) == 1
1429 /* A reg used outside the loop mustn't be eliminated. */
1431 /* A reg used for zero-extending mustn't be eliminated. */
1433 && (matched_regs
[m1
->regno
]
1436 /* Can combine regs with different modes loaded from the
1437 same constant only if the modes are the same or
1438 if both are integer modes with M wider or the same
1439 width as M1. The check for integer is redundant, but
1440 safe, since the only case of differing destination
1441 modes with equal sources is when both sources are
1442 VOIDmode, i.e., CONST_INT. */
1443 (GET_MODE (m
->set_dest
) == GET_MODE (m1
->set_dest
)
1444 || (GET_MODE_CLASS (GET_MODE (m
->set_dest
)) == MODE_INT
1445 && GET_MODE_CLASS (GET_MODE (m1
->set_dest
)) == MODE_INT
1446 && (GET_MODE_BITSIZE (GET_MODE (m
->set_dest
))
1447 >= GET_MODE_BITSIZE (GET_MODE (m1
->set_dest
)))))
1448 /* See if the source of M1 says it matches M. */
1449 && ((GET_CODE (m1
->set_src
) == REG
1450 && matched_regs
[REGNO (m1
->set_src
)])
1451 || rtx_equal_for_loop_p (m
->set_src
, m1
->set_src
,
1453 && ((m
->dependencies
== m1
->dependencies
)
1454 || rtx_equal_p (m
->dependencies
, m1
->dependencies
)))
1456 m
->lifetime
+= m1
->lifetime
;
1457 m
->savings
+= m1
->savings
;
1460 matched_regs
[m1
->regno
] = 1;
1464 /* Now combine the regs used for zero-extension.
1465 This can be done for those not marked `global'
1466 provided their lives don't overlap. */
1468 for (mode
= GET_CLASS_NARROWEST_MODE (MODE_INT
); mode
!= VOIDmode
;
1469 mode
= GET_MODE_WIDER_MODE (mode
))
1471 register struct movable
*m0
= 0;
1473 /* Combine all the registers for extension from mode MODE.
1474 Don't combine any that are used outside this loop. */
1475 for (m
= movables
; m
; m
= m
->next
)
1476 if (m
->partial
&& ! m
->global
1477 && mode
== GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m
->insn
)))))
1479 register struct movable
*m1
;
1480 int first
= uid_luid
[REGNO_FIRST_UID (m
->regno
)];
1481 int last
= uid_luid
[REGNO_LAST_UID (m
->regno
)];
1485 /* First one: don't check for overlap, just record it. */
1490 /* Make sure they extend to the same mode.
1491 (Almost always true.) */
1492 if (GET_MODE (m
->set_dest
) != GET_MODE (m0
->set_dest
))
1495 /* We already have one: check for overlap with those
1496 already combined together. */
1497 for (m1
= movables
; m1
!= m
; m1
= m1
->next
)
1498 if (m1
== m0
|| (m1
->partial
&& m1
->match
== m0
))
1499 if (! (uid_luid
[REGNO_FIRST_UID (m1
->regno
)] > last
1500 || uid_luid
[REGNO_LAST_UID (m1
->regno
)] < first
))
1503 /* No overlap: we can combine this with the others. */
1504 m0
->lifetime
+= m
->lifetime
;
1505 m0
->savings
+= m
->savings
;
1514 /* Return 1 if regs X and Y will become the same if moved. */
1517 regs_match_p (x
, y
, movables
)
1519 struct movable
*movables
;
1523 struct movable
*mx
, *my
;
1525 for (mx
= movables
; mx
; mx
= mx
->next
)
1526 if (mx
->regno
== xn
)
1529 for (my
= movables
; my
; my
= my
->next
)
1530 if (my
->regno
== yn
)
1534 && ((mx
->match
== my
->match
&& mx
->match
!= 0)
1536 || mx
== my
->match
));
1539 /* Return 1 if X and Y are identical-looking rtx's.
1540 This is the Lisp function EQUAL for rtx arguments.
1542 If two registers are matching movables or a movable register and an
1543 equivalent constant, consider them equal. */
1546 rtx_equal_for_loop_p (x
, y
, movables
)
1548 struct movable
*movables
;
1552 register struct movable
*m
;
1553 register enum rtx_code code
;
1558 if (x
== 0 || y
== 0)
1561 code
= GET_CODE (x
);
1563 /* If we have a register and a constant, they may sometimes be
1565 if (GET_CODE (x
) == REG
&& VARRAY_INT (set_in_loop
, REGNO (x
)) == -2
1568 for (m
= movables
; m
; m
= m
->next
)
1569 if (m
->move_insn
&& m
->regno
== REGNO (x
)
1570 && rtx_equal_p (m
->set_src
, y
))
1573 else if (GET_CODE (y
) == REG
&& VARRAY_INT (set_in_loop
, REGNO (y
)) == -2
1576 for (m
= movables
; m
; m
= m
->next
)
1577 if (m
->move_insn
&& m
->regno
== REGNO (y
)
1578 && rtx_equal_p (m
->set_src
, x
))
1582 /* Otherwise, rtx's of different codes cannot be equal. */
1583 if (code
!= GET_CODE (y
))
1586 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1587 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1589 if (GET_MODE (x
) != GET_MODE (y
))
1592 /* These three types of rtx's can be compared nonrecursively. */
1594 return (REGNO (x
) == REGNO (y
) || regs_match_p (x
, y
, movables
));
1596 if (code
== LABEL_REF
)
1597 return XEXP (x
, 0) == XEXP (y
, 0);
1598 if (code
== SYMBOL_REF
)
1599 return XSTR (x
, 0) == XSTR (y
, 0);
1601 /* Compare the elements. If any pair of corresponding elements
1602 fail to match, return 0 for the whole things. */
1604 fmt
= GET_RTX_FORMAT (code
);
1605 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1610 if (XWINT (x
, i
) != XWINT (y
, i
))
1615 if (XINT (x
, i
) != XINT (y
, i
))
1620 /* Two vectors must have the same length. */
1621 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1624 /* And the corresponding elements must match. */
1625 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1626 if (rtx_equal_for_loop_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
), movables
) == 0)
1631 if (rtx_equal_for_loop_p (XEXP (x
, i
), XEXP (y
, i
), movables
) == 0)
1636 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1641 /* These are just backpointers, so they don't matter. */
1647 /* It is believed that rtx's at this level will never
1648 contain anything but integers and other rtx's,
1649 except for within LABEL_REFs and SYMBOL_REFs. */
1657 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1658 insns in INSNS which use thet reference. */
1661 add_label_notes (x
, insns
)
1665 enum rtx_code code
= GET_CODE (x
);
1670 if (code
== LABEL_REF
&& !LABEL_REF_NONLOCAL_P (x
))
1672 /* This code used to ignore labels that referred to dispatch tables to
1673 avoid flow generating (slighly) worse code.
1675 We no longer ignore such label references (see LABEL_REF handling in
1676 mark_jump_label for additional information). */
1677 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
1678 if (reg_mentioned_p (XEXP (x
, 0), insn
))
1679 REG_NOTES (insn
) = gen_rtx_EXPR_LIST (REG_LABEL
, XEXP (x
, 0),
1683 fmt
= GET_RTX_FORMAT (code
);
1684 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1687 add_label_notes (XEXP (x
, i
), insns
);
1688 else if (fmt
[i
] == 'E')
1689 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1690 add_label_notes (XVECEXP (x
, i
, j
), insns
);
1694 /* Scan MOVABLES, and move the insns that deserve to be moved.
1695 If two matching movables are combined, replace one reg with the
1696 other throughout. */
1699 move_movables (movables
, threshold
, insn_count
, loop_start
, end
, nregs
)
1700 struct movable
*movables
;
1708 register struct movable
*m
;
1710 /* Map of pseudo-register replacements to handle combining
1711 when we move several insns that load the same value
1712 into different pseudo-registers. */
1713 rtx
*reg_map
= (rtx
*) alloca (nregs
* sizeof (rtx
));
1714 char *already_moved
= (char *) alloca (nregs
);
1716 bzero (already_moved
, nregs
);
1717 bzero ((char *) reg_map
, nregs
* sizeof (rtx
));
1721 for (m
= movables
; m
; m
= m
->next
)
1723 /* Describe this movable insn. */
1725 if (loop_dump_stream
)
1727 fprintf (loop_dump_stream
, "Insn %d: regno %d (life %d), ",
1728 INSN_UID (m
->insn
), m
->regno
, m
->lifetime
);
1730 fprintf (loop_dump_stream
, "consec %d, ", m
->consec
);
1732 fprintf (loop_dump_stream
, "cond ");
1734 fprintf (loop_dump_stream
, "force ");
1736 fprintf (loop_dump_stream
, "global ");
1738 fprintf (loop_dump_stream
, "done ");
1740 fprintf (loop_dump_stream
, "move-insn ");
1742 fprintf (loop_dump_stream
, "matches %d ",
1743 INSN_UID (m
->match
->insn
));
1745 fprintf (loop_dump_stream
, "forces %d ",
1746 INSN_UID (m
->forces
->insn
));
1749 /* Count movables. Value used in heuristics in strength_reduce. */
1752 /* Ignore the insn if it's already done (it matched something else).
1753 Otherwise, see if it is now safe to move. */
1757 || (1 == invariant_p (m
->set_src
)
1758 && (m
->dependencies
== 0
1759 || 1 == invariant_p (m
->dependencies
))
1761 || 1 == consec_sets_invariant_p (m
->set_dest
,
1764 && (! m
->forces
|| m
->forces
->done
))
1768 int savings
= m
->savings
;
1770 /* We have an insn that is safe to move.
1771 Compute its desirability. */
1776 if (loop_dump_stream
)
1777 fprintf (loop_dump_stream
, "savings %d ", savings
);
1779 if (moved_once
[regno
] && loop_dump_stream
)
1780 fprintf (loop_dump_stream
, "halved since already moved ");
1782 /* An insn MUST be moved if we already moved something else
1783 which is safe only if this one is moved too: that is,
1784 if already_moved[REGNO] is nonzero. */
1786 /* An insn is desirable to move if the new lifetime of the
1787 register is no more than THRESHOLD times the old lifetime.
1788 If it's not desirable, it means the loop is so big
1789 that moving won't speed things up much,
1790 and it is liable to make register usage worse. */
1792 /* It is also desirable to move if it can be moved at no
1793 extra cost because something else was already moved. */
1795 if (already_moved
[regno
]
1796 || flag_move_all_movables
1797 || (threshold
* savings
* m
->lifetime
) >=
1798 (moved_once
[regno
] ? insn_count
* 2 : insn_count
)
1799 || (m
->forces
&& m
->forces
->done
1800 && VARRAY_INT (n_times_set
, m
->forces
->regno
) == 1))
1803 register struct movable
*m1
;
1806 /* Now move the insns that set the reg. */
1808 if (m
->partial
&& m
->match
)
1812 /* Find the end of this chain of matching regs.
1813 Thus, we load each reg in the chain from that one reg.
1814 And that reg is loaded with 0 directly,
1815 since it has ->match == 0. */
1816 for (m1
= m
; m1
->match
; m1
= m1
->match
);
1817 newpat
= gen_move_insn (SET_DEST (PATTERN (m
->insn
)),
1818 SET_DEST (PATTERN (m1
->insn
)));
1819 i1
= emit_insn_before (newpat
, loop_start
);
1821 /* Mark the moved, invariant reg as being allowed to
1822 share a hard reg with the other matching invariant. */
1823 REG_NOTES (i1
) = REG_NOTES (m
->insn
);
1824 r1
= SET_DEST (PATTERN (m
->insn
));
1825 r2
= SET_DEST (PATTERN (m1
->insn
));
1827 = gen_rtx_EXPR_LIST (VOIDmode
, r1
,
1828 gen_rtx_EXPR_LIST (VOIDmode
, r2
,
1830 delete_insn (m
->insn
);
1835 if (loop_dump_stream
)
1836 fprintf (loop_dump_stream
, " moved to %d", INSN_UID (i1
));
1838 /* If we are to re-generate the item being moved with a
1839 new move insn, first delete what we have and then emit
1840 the move insn before the loop. */
1841 else if (m
->move_insn
)
1845 for (count
= m
->consec
; count
>= 0; count
--)
1847 /* If this is the first insn of a library call sequence,
1849 if (GET_CODE (p
) != NOTE
1850 && (temp
= find_reg_note (p
, REG_LIBCALL
, NULL_RTX
)))
1853 /* If this is the last insn of a libcall sequence, then
1854 delete every insn in the sequence except the last.
1855 The last insn is handled in the normal manner. */
1856 if (GET_CODE (p
) != NOTE
1857 && (temp
= find_reg_note (p
, REG_RETVAL
, NULL_RTX
)))
1859 temp
= XEXP (temp
, 0);
1861 temp
= delete_insn (temp
);
1865 p
= delete_insn (p
);
1867 /* simplify_giv_expr expects that it can walk the insns
1868 at m->insn forwards and see this old sequence we are
1869 tossing here. delete_insn does preserve the next
1870 pointers, but when we skip over a NOTE we must fix
1871 it up. Otherwise that code walks into the non-deleted
1873 while (p
&& GET_CODE (p
) == NOTE
)
1874 p
= NEXT_INSN (temp
) = NEXT_INSN (p
);
1878 emit_move_insn (m
->set_dest
, m
->set_src
);
1879 temp
= get_insns ();
1882 add_label_notes (m
->set_src
, temp
);
1884 i1
= emit_insns_before (temp
, loop_start
);
1885 if (! find_reg_note (i1
, REG_EQUAL
, NULL_RTX
))
1887 = gen_rtx_EXPR_LIST (m
->is_equiv
? REG_EQUIV
: REG_EQUAL
,
1888 m
->set_src
, REG_NOTES (i1
));
1890 if (loop_dump_stream
)
1891 fprintf (loop_dump_stream
, " moved to %d", INSN_UID (i1
));
1893 /* The more regs we move, the less we like moving them. */
1898 for (count
= m
->consec
; count
>= 0; count
--)
1902 /* If first insn of libcall sequence, skip to end. */
1903 /* Do this at start of loop, since p is guaranteed to
1905 if (GET_CODE (p
) != NOTE
1906 && (temp
= find_reg_note (p
, REG_LIBCALL
, NULL_RTX
)))
1909 /* If last insn of libcall sequence, move all
1910 insns except the last before the loop. The last
1911 insn is handled in the normal manner. */
1912 if (GET_CODE (p
) != NOTE
1913 && (temp
= find_reg_note (p
, REG_RETVAL
, NULL_RTX
)))
1917 rtx fn_address_insn
= 0;
1920 for (temp
= XEXP (temp
, 0); temp
!= p
;
1921 temp
= NEXT_INSN (temp
))
1927 if (GET_CODE (temp
) == NOTE
)
1930 body
= PATTERN (temp
);
1932 /* Find the next insn after TEMP,
1933 not counting USE or NOTE insns. */
1934 for (next
= NEXT_INSN (temp
); next
!= p
;
1935 next
= NEXT_INSN (next
))
1936 if (! (GET_CODE (next
) == INSN
1937 && GET_CODE (PATTERN (next
)) == USE
)
1938 && GET_CODE (next
) != NOTE
)
1941 /* If that is the call, this may be the insn
1942 that loads the function address.
1944 Extract the function address from the insn
1945 that loads it into a register.
1946 If this insn was cse'd, we get incorrect code.
1948 So emit a new move insn that copies the
1949 function address into the register that the
1950 call insn will use. flow.c will delete any
1951 redundant stores that we have created. */
1952 if (GET_CODE (next
) == CALL_INSN
1953 && GET_CODE (body
) == SET
1954 && GET_CODE (SET_DEST (body
)) == REG
1955 && (n
= find_reg_note (temp
, REG_EQUAL
,
1958 fn_reg
= SET_SRC (body
);
1959 if (GET_CODE (fn_reg
) != REG
)
1960 fn_reg
= SET_DEST (body
);
1961 fn_address
= XEXP (n
, 0);
1962 fn_address_insn
= temp
;
1964 /* We have the call insn.
1965 If it uses the register we suspect it might,
1966 load it with the correct address directly. */
1967 if (GET_CODE (temp
) == CALL_INSN
1969 && reg_referenced_p (fn_reg
, body
))
1970 emit_insn_after (gen_move_insn (fn_reg
,
1974 if (GET_CODE (temp
) == CALL_INSN
)
1976 i1
= emit_call_insn_before (body
, loop_start
);
1977 /* Because the USAGE information potentially
1978 contains objects other than hard registers
1979 we need to copy it. */
1980 if (CALL_INSN_FUNCTION_USAGE (temp
))
1981 CALL_INSN_FUNCTION_USAGE (i1
)
1982 = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp
));
1985 i1
= emit_insn_before (body
, loop_start
);
1988 if (temp
== fn_address_insn
)
1989 fn_address_insn
= i1
;
1990 REG_NOTES (i1
) = REG_NOTES (temp
);
1996 if (m
->savemode
!= VOIDmode
)
1998 /* P sets REG to zero; but we should clear only
1999 the bits that are not covered by the mode
2001 rtx reg
= m
->set_dest
;
2007 (GET_MODE (reg
), and_optab
, reg
,
2008 GEN_INT ((((HOST_WIDE_INT
) 1
2009 << GET_MODE_BITSIZE (m
->savemode
)))
2011 reg
, 1, OPTAB_LIB_WIDEN
);
2015 emit_move_insn (reg
, tem
);
2016 sequence
= gen_sequence ();
2018 i1
= emit_insn_before (sequence
, loop_start
);
2020 else if (GET_CODE (p
) == CALL_INSN
)
2022 i1
= emit_call_insn_before (PATTERN (p
), loop_start
);
2023 /* Because the USAGE information potentially
2024 contains objects other than hard registers
2025 we need to copy it. */
2026 if (CALL_INSN_FUNCTION_USAGE (p
))
2027 CALL_INSN_FUNCTION_USAGE (i1
)
2028 = copy_rtx (CALL_INSN_FUNCTION_USAGE (p
));
2030 else if (count
== m
->consec
&& m
->move_insn_first
)
2032 /* The SET_SRC might not be invariant, so we must
2033 use the REG_EQUAL note. */
2035 emit_move_insn (m
->set_dest
, m
->set_src
);
2036 temp
= get_insns ();
2039 add_label_notes (m
->set_src
, temp
);
2041 i1
= emit_insns_before (temp
, loop_start
);
2042 if (! find_reg_note (i1
, REG_EQUAL
, NULL_RTX
))
2044 = gen_rtx_EXPR_LIST ((m
->is_equiv
? REG_EQUIV
2046 m
->set_src
, REG_NOTES (i1
));
2049 i1
= emit_insn_before (PATTERN (p
), loop_start
);
2051 if (REG_NOTES (i1
) == 0)
2053 REG_NOTES (i1
) = REG_NOTES (p
);
2055 /* If there is a REG_EQUAL note present whose value
2056 is not loop invariant, then delete it, since it
2057 may cause problems with later optimization passes.
2058 It is possible for cse to create such notes
2059 like this as a result of record_jump_cond. */
2061 if ((temp
= find_reg_note (i1
, REG_EQUAL
, NULL_RTX
))
2062 && ! invariant_p (XEXP (temp
, 0)))
2063 remove_note (i1
, temp
);
2069 if (loop_dump_stream
)
2070 fprintf (loop_dump_stream
, " moved to %d",
2073 /* If library call, now fix the REG_NOTES that contain
2074 insn pointers, namely REG_LIBCALL on FIRST
2075 and REG_RETVAL on I1. */
2076 if ((temp
= find_reg_note (i1
, REG_RETVAL
, NULL_RTX
)))
2078 XEXP (temp
, 0) = first
;
2079 temp
= find_reg_note (first
, REG_LIBCALL
, NULL_RTX
);
2080 XEXP (temp
, 0) = i1
;
2087 /* simplify_giv_expr expects that it can walk the insns
2088 at m->insn forwards and see this old sequence we are
2089 tossing here. delete_insn does preserve the next
2090 pointers, but when we skip over a NOTE we must fix
2091 it up. Otherwise that code walks into the non-deleted
2093 while (p
&& GET_CODE (p
) == NOTE
)
2094 p
= NEXT_INSN (temp
) = NEXT_INSN (p
);
2097 /* The more regs we move, the less we like moving them. */
2101 /* Any other movable that loads the same register
2103 already_moved
[regno
] = 1;
2105 /* This reg has been moved out of one loop. */
2106 moved_once
[regno
] = 1;
2108 /* The reg set here is now invariant. */
2110 VARRAY_INT (set_in_loop
, regno
) = 0;
2114 /* Change the length-of-life info for the register
2115 to say it lives at least the full length of this loop.
2116 This will help guide optimizations in outer loops. */
2118 if (uid_luid
[REGNO_FIRST_UID (regno
)] > INSN_LUID (loop_start
))
2119 /* This is the old insn before all the moved insns.
2120 We can't use the moved insn because it is out of range
2121 in uid_luid. Only the old insns have luids. */
2122 REGNO_FIRST_UID (regno
) = INSN_UID (loop_start
);
2123 if (uid_luid
[REGNO_LAST_UID (regno
)] < INSN_LUID (end
))
2124 REGNO_LAST_UID (regno
) = INSN_UID (end
);
2126 /* Combine with this moved insn any other matching movables. */
2129 for (m1
= movables
; m1
; m1
= m1
->next
)
2134 /* Schedule the reg loaded by M1
2135 for replacement so that shares the reg of M.
2136 If the modes differ (only possible in restricted
2137 circumstances, make a SUBREG. */
2138 if (GET_MODE (m
->set_dest
) == GET_MODE (m1
->set_dest
))
2139 reg_map
[m1
->regno
] = m
->set_dest
;
2142 = gen_lowpart_common (GET_MODE (m1
->set_dest
),
2145 /* Get rid of the matching insn
2146 and prevent further processing of it. */
2149 /* if library call, delete all insn except last, which
2151 if ((temp
= find_reg_note (m1
->insn
, REG_RETVAL
,
2154 for (temp
= XEXP (temp
, 0); temp
!= m1
->insn
;
2155 temp
= NEXT_INSN (temp
))
2158 delete_insn (m1
->insn
);
2160 /* Any other movable that loads the same register
2162 already_moved
[m1
->regno
] = 1;
2164 /* The reg merged here is now invariant,
2165 if the reg it matches is invariant. */
2167 VARRAY_INT (set_in_loop
, m1
->regno
) = 0;
2170 else if (loop_dump_stream
)
2171 fprintf (loop_dump_stream
, "not desirable");
2173 else if (loop_dump_stream
&& !m
->match
)
2174 fprintf (loop_dump_stream
, "not safe");
2176 if (loop_dump_stream
)
2177 fprintf (loop_dump_stream
, "\n");
2181 new_start
= loop_start
;
2183 /* Go through all the instructions in the loop, making
2184 all the register substitutions scheduled in REG_MAP. */
2185 for (p
= new_start
; p
!= end
; p
= NEXT_INSN (p
))
2186 if (GET_CODE (p
) == INSN
|| GET_CODE (p
) == JUMP_INSN
2187 || GET_CODE (p
) == CALL_INSN
)
2189 replace_regs (PATTERN (p
), reg_map
, nregs
, 0);
2190 replace_regs (REG_NOTES (p
), reg_map
, nregs
, 0);
2196 /* Scan X and replace the address of any MEM in it with ADDR.
2197 REG is the address that MEM should have before the replacement. */
2200 replace_call_address (x
, reg
, addr
)
2203 register enum rtx_code code
;
2209 code
= GET_CODE (x
);
2223 /* Short cut for very common case. */
2224 replace_call_address (XEXP (x
, 1), reg
, addr
);
2228 /* Short cut for very common case. */
2229 replace_call_address (XEXP (x
, 0), reg
, addr
);
2233 /* If this MEM uses a reg other than the one we expected,
2234 something is wrong. */
2235 if (XEXP (x
, 0) != reg
)
2244 fmt
= GET_RTX_FORMAT (code
);
2245 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2248 replace_call_address (XEXP (x
, i
), reg
, addr
);
2252 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2253 replace_call_address (XVECEXP (x
, i
, j
), reg
, addr
);
2259 /* Return the number of memory refs to addresses that vary
2263 count_nonfixed_reads (x
)
2266 register enum rtx_code code
;
2274 code
= GET_CODE (x
);
2288 return ((invariant_p (XEXP (x
, 0)) != 1)
2289 + count_nonfixed_reads (XEXP (x
, 0)));
2296 fmt
= GET_RTX_FORMAT (code
);
2297 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2300 value
+= count_nonfixed_reads (XEXP (x
, i
));
2304 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2305 value
+= count_nonfixed_reads (XVECEXP (x
, i
, j
));
2313 /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
2314 Replace it with an instruction to load just the low bytes
2315 if the machine supports such an instruction,
2316 and insert above LOOP_START an instruction to clear the register. */
2319 constant_high_bytes (p
, loop_start
)
2323 register int insn_code_number
;
2325 /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
2326 to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
2328 new = gen_rtx_SET (VOIDmode
,
2329 gen_rtx_STRICT_LOW_PART (VOIDmode
,
2330 gen_rtx_SUBREG (GET_MODE (XEXP (SET_SRC (PATTERN (p
)), 0)),
2331 SET_DEST (PATTERN (p
)),
2333 XEXP (SET_SRC (PATTERN (p
)), 0));
2334 insn_code_number
= recog (new, p
);
2336 if (insn_code_number
)
2340 /* Clear destination register before the loop. */
2341 emit_insn_before (gen_rtx_SET (VOIDmode
, SET_DEST (PATTERN (p
)),
2345 /* Inside the loop, just load the low part. */
2351 /* Scan a loop setting the variables `unknown_address_altered',
2352 `num_mem_sets', `loop_continue', `loops_enclosed', `loop_has_call',
2353 `loop_has_volatile', and `loop_has_tablejump'.
2354 Also, fill in the array `loop_mems' and the list `loop_store_mems'. */
2357 prescan_loop (start
, end
)
2360 register int level
= 1;
2362 int loop_has_multiple_exit_targets
= 0;
2363 /* The label after END. Jumping here is just like falling off the
2364 end of the loop. We use next_nonnote_insn instead of next_label
2365 as a hedge against the (pathological) case where some actual insn
2366 might end up between the two. */
2367 rtx exit_target
= next_nonnote_insn (end
);
2368 if (exit_target
== NULL_RTX
|| GET_CODE (exit_target
) != CODE_LABEL
)
2369 loop_has_multiple_exit_targets
= 1;
2371 unknown_address_altered
= 0;
2373 loop_has_volatile
= 0;
2374 loop_has_tablejump
= 0;
2375 loop_store_mems
= NULL_RTX
;
2382 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
2383 insn
= NEXT_INSN (insn
))
2385 if (GET_CODE (insn
) == NOTE
)
2387 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
2390 /* Count number of loops contained in this one. */
2393 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
2402 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_CONT
)
2405 loop_continue
= insn
;
2408 else if (GET_CODE (insn
) == CALL_INSN
)
2410 if (! CONST_CALL_P (insn
))
2411 unknown_address_altered
= 1;
2414 else if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
2416 rtx label1
= NULL_RTX
;
2417 rtx label2
= NULL_RTX
;
2419 if (volatile_refs_p (PATTERN (insn
)))
2420 loop_has_volatile
= 1;
2422 if (GET_CODE (insn
) == JUMP_INSN
2423 && (GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
2424 || GET_CODE (PATTERN (insn
)) == ADDR_VEC
))
2425 loop_has_tablejump
= 1;
2427 note_stores (PATTERN (insn
), note_addr_stored
);
2429 if (! loop_has_multiple_exit_targets
2430 && GET_CODE (insn
) == JUMP_INSN
2431 && GET_CODE (PATTERN (insn
)) == SET
2432 && SET_DEST (PATTERN (insn
)) == pc_rtx
)
2434 if (GET_CODE (SET_SRC (PATTERN (insn
))) == IF_THEN_ELSE
)
2436 label1
= XEXP (SET_SRC (PATTERN (insn
)), 1);
2437 label2
= XEXP (SET_SRC (PATTERN (insn
)), 2);
2441 label1
= SET_SRC (PATTERN (insn
));
2445 if (label1
&& label1
!= pc_rtx
)
2447 if (GET_CODE (label1
) != LABEL_REF
)
2449 /* Something tricky. */
2450 loop_has_multiple_exit_targets
= 1;
2453 else if (XEXP (label1
, 0) != exit_target
2454 && LABEL_OUTSIDE_LOOP_P (label1
))
2456 /* A jump outside the current loop. */
2457 loop_has_multiple_exit_targets
= 1;
2467 else if (GET_CODE (insn
) == RETURN
)
2468 loop_has_multiple_exit_targets
= 1;
2471 /* Now, rescan the loop, setting up the LOOP_MEMS array. */
2472 if (/* We can't tell what MEMs are aliased by what. */
2473 !unknown_address_altered
2474 /* An exception thrown by a called function might land us
2477 /* We don't want loads for MEMs moved to a location before the
2478 one at which their stack memory becomes allocated. (Note
2479 that this is not a problem for malloc, etc., since those
2480 require actual function calls. */
2481 && !current_function_calls_alloca
2482 /* There are ways to leave the loop other than falling off the
2484 && !loop_has_multiple_exit_targets
)
2485 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
2486 insn
= NEXT_INSN (insn
))
2487 for_each_rtx (&insn
, insert_loop_mem
, 0);
2490 /* Scan the function looking for loops. Record the start and end of each loop.
2491 Also mark as invalid loops any loops that contain a setjmp or are branched
2492 to from outside the loop. */
2495 find_and_verify_loops (f
)
2499 int current_loop
= -1;
2503 /* If there are jumps to undefined labels,
2504 treat them as jumps out of any/all loops.
2505 This also avoids writing past end of tables when there are no loops. */
2506 uid_loop_num
[0] = -1;
2508 /* Find boundaries of loops, mark which loops are contained within
2509 loops, and invalidate loops that have setjmp. */
2511 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
2513 if (GET_CODE (insn
) == NOTE
)
2514 switch (NOTE_LINE_NUMBER (insn
))
2516 case NOTE_INSN_LOOP_BEG
:
2517 loop_number_loop_starts
[++next_loop
] = insn
;
2518 loop_number_loop_ends
[next_loop
] = 0;
2519 loop_outer_loop
[next_loop
] = current_loop
;
2520 loop_invalid
[next_loop
] = 0;
2521 loop_number_exit_labels
[next_loop
] = 0;
2522 loop_number_exit_count
[next_loop
] = 0;
2523 current_loop
= next_loop
;
2526 case NOTE_INSN_SETJMP
:
2527 /* In this case, we must invalidate our current loop and any
2529 for (loop
= current_loop
; loop
!= -1; loop
= loop_outer_loop
[loop
])
2531 loop_invalid
[loop
] = 1;
2532 if (loop_dump_stream
)
2533 fprintf (loop_dump_stream
,
2534 "\nLoop at %d ignored due to setjmp.\n",
2535 INSN_UID (loop_number_loop_starts
[loop
]));
2539 case NOTE_INSN_LOOP_END
:
2540 if (current_loop
== -1)
2543 loop_number_loop_ends
[current_loop
] = insn
;
2544 current_loop
= loop_outer_loop
[current_loop
];
2551 /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2552 enclosing loop, but this doesn't matter. */
2553 uid_loop_num
[INSN_UID (insn
)] = current_loop
;
2556 /* Any loop containing a label used in an initializer must be invalidated,
2557 because it can be jumped into from anywhere. */
2559 for (label
= forced_labels
; label
; label
= XEXP (label
, 1))
2563 for (loop_num
= uid_loop_num
[INSN_UID (XEXP (label
, 0))];
2565 loop_num
= loop_outer_loop
[loop_num
])
2566 loop_invalid
[loop_num
] = 1;
2569 /* Any loop containing a label used for an exception handler must be
2570 invalidated, because it can be jumped into from anywhere. */
2572 for (label
= exception_handler_labels
; label
; label
= XEXP (label
, 1))
2576 for (loop_num
= uid_loop_num
[INSN_UID (XEXP (label
, 0))];
2578 loop_num
= loop_outer_loop
[loop_num
])
2579 loop_invalid
[loop_num
] = 1;
2582 /* Now scan all insn's in the function. If any JUMP_INSN branches into a
2583 loop that it is not contained within, that loop is marked invalid.
2584 If any INSN or CALL_INSN uses a label's address, then the loop containing
2585 that label is marked invalid, because it could be jumped into from
2588 Also look for blocks of code ending in an unconditional branch that
2589 exits the loop. If such a block is surrounded by a conditional
2590 branch around the block, move the block elsewhere (see below) and
2591 invert the jump to point to the code block. This may eliminate a
2592 label in our loop and will simplify processing by both us and a
2593 possible second cse pass. */
2595 for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
2596 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
2598 int this_loop_num
= uid_loop_num
[INSN_UID (insn
)];
2600 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == CALL_INSN
)
2602 rtx note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
);
2607 for (loop_num
= uid_loop_num
[INSN_UID (XEXP (note
, 0))];
2609 loop_num
= loop_outer_loop
[loop_num
])
2610 loop_invalid
[loop_num
] = 1;
2614 if (GET_CODE (insn
) != JUMP_INSN
)
2617 mark_loop_jump (PATTERN (insn
), this_loop_num
);
2619 /* See if this is an unconditional branch outside the loop. */
2620 if (this_loop_num
!= -1
2621 && (GET_CODE (PATTERN (insn
)) == RETURN
2622 || (simplejump_p (insn
)
2623 && (uid_loop_num
[INSN_UID (JUMP_LABEL (insn
))]
2625 && get_max_uid () < max_uid_for_loop
)
2628 rtx our_next
= next_real_insn (insn
);
2630 int outer_loop
= -1;
2632 /* Go backwards until we reach the start of the loop, a label,
2634 for (p
= PREV_INSN (insn
);
2635 GET_CODE (p
) != CODE_LABEL
2636 && ! (GET_CODE (p
) == NOTE
2637 && NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_BEG
)
2638 && GET_CODE (p
) != JUMP_INSN
;
2642 /* Check for the case where we have a jump to an inner nested
2643 loop, and do not perform the optimization in that case. */
2645 if (JUMP_LABEL (insn
))
2647 dest_loop
= uid_loop_num
[INSN_UID (JUMP_LABEL (insn
))];
2648 if (dest_loop
!= -1)
2650 for (outer_loop
= dest_loop
; outer_loop
!= -1;
2651 outer_loop
= loop_outer_loop
[outer_loop
])
2652 if (outer_loop
== this_loop_num
)
2657 /* Make sure that the target of P is within the current loop. */
2659 if (GET_CODE (p
) == JUMP_INSN
&& JUMP_LABEL (p
)
2660 && uid_loop_num
[INSN_UID (JUMP_LABEL (p
))] != this_loop_num
)
2661 outer_loop
= this_loop_num
;
2663 /* If we stopped on a JUMP_INSN to the next insn after INSN,
2664 we have a block of code to try to move.
2666 We look backward and then forward from the target of INSN
2667 to find a BARRIER at the same loop depth as the target.
2668 If we find such a BARRIER, we make a new label for the start
2669 of the block, invert the jump in P and point it to that label,
2670 and move the block of code to the spot we found. */
2672 if (outer_loop
== -1
2673 && GET_CODE (p
) == JUMP_INSN
2674 && JUMP_LABEL (p
) != 0
2675 /* Just ignore jumps to labels that were never emitted.
2676 These always indicate compilation errors. */
2677 && INSN_UID (JUMP_LABEL (p
)) != 0
2679 && ! simplejump_p (p
)
2680 && next_real_insn (JUMP_LABEL (p
)) == our_next
)
2683 = JUMP_LABEL (insn
) ? JUMP_LABEL (insn
) : get_last_insn ();
2684 int target_loop_num
= uid_loop_num
[INSN_UID (target
)];
2687 for (loc
= target
; loc
; loc
= PREV_INSN (loc
))
2688 if (GET_CODE (loc
) == BARRIER
2689 && uid_loop_num
[INSN_UID (loc
)] == target_loop_num
)
2693 for (loc
= target
; loc
; loc
= NEXT_INSN (loc
))
2694 if (GET_CODE (loc
) == BARRIER
2695 && uid_loop_num
[INSN_UID (loc
)] == target_loop_num
)
2700 rtx cond_label
= JUMP_LABEL (p
);
2701 rtx new_label
= get_label_after (p
);
2703 /* Ensure our label doesn't go away. */
2704 LABEL_NUSES (cond_label
)++;
2706 /* Verify that uid_loop_num is large enough and that
2708 if (invert_jump (p
, new_label
))
2712 /* If no suitable BARRIER was found, create a suitable
2713 one before TARGET. Since TARGET is a fall through
2714 path, we'll need to insert an jump around our block
2715 and a add a BARRIER before TARGET.
2717 This creates an extra unconditional jump outside
2718 the loop. However, the benefits of removing rarely
2719 executed instructions from inside the loop usually
2720 outweighs the cost of the extra unconditional jump
2721 outside the loop. */
2726 temp
= gen_jump (JUMP_LABEL (insn
));
2727 temp
= emit_jump_insn_before (temp
, target
);
2728 JUMP_LABEL (temp
) = JUMP_LABEL (insn
);
2729 LABEL_NUSES (JUMP_LABEL (insn
))++;
2730 loc
= emit_barrier_before (target
);
2733 /* Include the BARRIER after INSN and copy the
2735 new_label
= squeeze_notes (new_label
, NEXT_INSN (insn
));
2736 reorder_insns (new_label
, NEXT_INSN (insn
), loc
);
2738 /* All those insns are now in TARGET_LOOP_NUM. */
2739 for (q
= new_label
; q
!= NEXT_INSN (NEXT_INSN (insn
));
2741 uid_loop_num
[INSN_UID (q
)] = target_loop_num
;
2743 /* The label jumped to by INSN is no longer a loop exit.
2744 Unless INSN does not have a label (e.g., it is a
2745 RETURN insn), search loop_number_exit_labels to find
2746 its label_ref, and remove it. Also turn off
2747 LABEL_OUTSIDE_LOOP_P bit. */
2748 if (JUMP_LABEL (insn
))
2753 r
= loop_number_exit_labels
[this_loop_num
];
2754 r
; q
= r
, r
= LABEL_NEXTREF (r
))
2755 if (XEXP (r
, 0) == JUMP_LABEL (insn
))
2757 LABEL_OUTSIDE_LOOP_P (r
) = 0;
2759 LABEL_NEXTREF (q
) = LABEL_NEXTREF (r
);
2761 loop_number_exit_labels
[this_loop_num
]
2762 = LABEL_NEXTREF (r
);
2766 for (loop_num
= this_loop_num
;
2767 loop_num
!= -1 && loop_num
!= target_loop_num
;
2768 loop_num
= loop_outer_loop
[loop_num
])
2769 loop_number_exit_count
[loop_num
]--;
2771 /* If we didn't find it, then something is wrong. */
2776 /* P is now a jump outside the loop, so it must be put
2777 in loop_number_exit_labels, and marked as such.
2778 The easiest way to do this is to just call
2779 mark_loop_jump again for P. */
2780 mark_loop_jump (PATTERN (p
), this_loop_num
);
2782 /* If INSN now jumps to the insn after it,
2784 if (JUMP_LABEL (insn
) != 0
2785 && (next_real_insn (JUMP_LABEL (insn
))
2786 == next_real_insn (insn
)))
2790 /* Continue the loop after where the conditional
2791 branch used to jump, since the only branch insn
2792 in the block (if it still remains) is an inter-loop
2793 branch and hence needs no processing. */
2794 insn
= NEXT_INSN (cond_label
);
2796 if (--LABEL_NUSES (cond_label
) == 0)
2797 delete_insn (cond_label
);
2799 /* This loop will be continued with NEXT_INSN (insn). */
2800 insn
= PREV_INSN (insn
);
2807 /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2808 loops it is contained in, mark the target loop invalid.
2810 For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2813 mark_loop_jump (x
, loop_num
)
2821 switch (GET_CODE (x
))
2834 /* There could be a label reference in here. */
2835 mark_loop_jump (XEXP (x
, 0), loop_num
);
2841 mark_loop_jump (XEXP (x
, 0), loop_num
);
2842 mark_loop_jump (XEXP (x
, 1), loop_num
);
2847 mark_loop_jump (XEXP (x
, 0), loop_num
);
2851 dest_loop
= uid_loop_num
[INSN_UID (XEXP (x
, 0))];
2853 /* Link together all labels that branch outside the loop. This
2854 is used by final_[bg]iv_value and the loop unrolling code. Also
2855 mark this LABEL_REF so we know that this branch should predict
2858 /* A check to make sure the label is not in an inner nested loop,
2859 since this does not count as a loop exit. */
2860 if (dest_loop
!= -1)
2862 for (outer_loop
= dest_loop
; outer_loop
!= -1;
2863 outer_loop
= loop_outer_loop
[outer_loop
])
2864 if (outer_loop
== loop_num
)
2870 if (loop_num
!= -1 && outer_loop
== -1)
2872 LABEL_OUTSIDE_LOOP_P (x
) = 1;
2873 LABEL_NEXTREF (x
) = loop_number_exit_labels
[loop_num
];
2874 loop_number_exit_labels
[loop_num
] = x
;
2876 for (outer_loop
= loop_num
;
2877 outer_loop
!= -1 && outer_loop
!= dest_loop
;
2878 outer_loop
= loop_outer_loop
[outer_loop
])
2879 loop_number_exit_count
[outer_loop
]++;
2882 /* If this is inside a loop, but not in the current loop or one enclosed
2883 by it, it invalidates at least one loop. */
2885 if (dest_loop
== -1)
2888 /* We must invalidate every nested loop containing the target of this
2889 label, except those that also contain the jump insn. */
2891 for (; dest_loop
!= -1; dest_loop
= loop_outer_loop
[dest_loop
])
2893 /* Stop when we reach a loop that also contains the jump insn. */
2894 for (outer_loop
= loop_num
; outer_loop
!= -1;
2895 outer_loop
= loop_outer_loop
[outer_loop
])
2896 if (dest_loop
== outer_loop
)
2899 /* If we get here, we know we need to invalidate a loop. */
2900 if (loop_dump_stream
&& ! loop_invalid
[dest_loop
])
2901 fprintf (loop_dump_stream
,
2902 "\nLoop at %d ignored due to multiple entry points.\n",
2903 INSN_UID (loop_number_loop_starts
[dest_loop
]));
2905 loop_invalid
[dest_loop
] = 1;
2910 /* If this is not setting pc, ignore. */
2911 if (SET_DEST (x
) == pc_rtx
)
2912 mark_loop_jump (SET_SRC (x
), loop_num
);
2916 mark_loop_jump (XEXP (x
, 1), loop_num
);
2917 mark_loop_jump (XEXP (x
, 2), loop_num
);
2922 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
2923 mark_loop_jump (XVECEXP (x
, 0, i
), loop_num
);
2927 for (i
= 0; i
< XVECLEN (x
, 1); i
++)
2928 mark_loop_jump (XVECEXP (x
, 1, i
), loop_num
);
2932 /* Treat anything else (such as a symbol_ref)
2933 as a branch out of this loop, but not into any loop. */
2937 #ifdef HAVE_decrement_and_branch_on_count
2938 LABEL_OUTSIDE_LOOP_P (x
) = 1;
2939 LABEL_NEXTREF (x
) = loop_number_exit_labels
[loop_num
];
2940 #endif /* HAVE_decrement_and_branch_on_count */
2942 loop_number_exit_labels
[loop_num
] = x
;
2944 for (outer_loop
= loop_num
; outer_loop
!= -1;
2945 outer_loop
= loop_outer_loop
[outer_loop
])
2946 loop_number_exit_count
[outer_loop
]++;
2952 /* Return nonzero if there is a label in the range from
2953 insn INSN to and including the insn whose luid is END
2954 INSN must have an assigned luid (i.e., it must not have
2955 been previously created by loop.c). */
2958 labels_in_range_p (insn
, end
)
2962 while (insn
&& INSN_LUID (insn
) <= end
)
2964 if (GET_CODE (insn
) == CODE_LABEL
)
2966 insn
= NEXT_INSN (insn
);
2972 /* Record that a memory reference X is being set. */
2975 note_addr_stored (x
, y
)
2977 rtx y ATTRIBUTE_UNUSED
;
2979 if (x
== 0 || GET_CODE (x
) != MEM
)
2982 /* Count number of memory writes.
2983 This affects heuristics in strength_reduce. */
2986 /* BLKmode MEM means all memory is clobbered. */
2987 if (GET_MODE (x
) == BLKmode
)
2988 unknown_address_altered
= 1;
2990 if (unknown_address_altered
)
2993 loop_store_mems
= gen_rtx_EXPR_LIST (VOIDmode
, x
, loop_store_mems
);
2996 /* Return nonzero if the rtx X is invariant over the current loop.
2998 The value is 2 if we refer to something only conditionally invariant.
3000 If `unknown_address_altered' is nonzero, no memory ref is invariant.
3001 Otherwise, a memory ref is invariant if it does not conflict with
3002 anything stored in `loop_store_mems'. */
3009 register enum rtx_code code
;
3011 int conditional
= 0;
3016 code
= GET_CODE (x
);
3026 /* A LABEL_REF is normally invariant, however, if we are unrolling
3027 loops, and this label is inside the loop, then it isn't invariant.
3028 This is because each unrolled copy of the loop body will have
3029 a copy of this label. If this was invariant, then an insn loading
3030 the address of this label into a register might get moved outside
3031 the loop, and then each loop body would end up using the same label.
3033 We don't know the loop bounds here though, so just fail for all
3035 if (flag_unroll_loops
)
3042 case UNSPEC_VOLATILE
:
3046 /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
3047 since the reg might be set by initialization within the loop. */
3049 if ((x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
3050 || x
== arg_pointer_rtx
)
3051 && ! current_function_has_nonlocal_goto
)
3055 && REGNO (x
) < FIRST_PSEUDO_REGISTER
&& call_used_regs
[REGNO (x
)])
3058 if (VARRAY_INT (set_in_loop
, REGNO (x
)) < 0)
3061 return VARRAY_INT (set_in_loop
, REGNO (x
)) == 0;
3064 /* Volatile memory references must be rejected. Do this before
3065 checking for read-only items, so that volatile read-only items
3066 will be rejected also. */
3067 if (MEM_VOLATILE_P (x
))
3070 /* Read-only items (such as constants in a constant pool) are
3071 invariant if their address is. */
3072 if (RTX_UNCHANGING_P (x
))
3075 /* If we had a subroutine call, any location in memory could have been
3077 if (unknown_address_altered
)
3080 /* See if there is any dependence between a store and this load. */
3081 mem_list_entry
= loop_store_mems
;
3082 while (mem_list_entry
)
3084 if (true_dependence (XEXP (mem_list_entry
, 0), VOIDmode
,
3087 mem_list_entry
= XEXP (mem_list_entry
, 1);
3090 /* It's not invalidated by a store in memory
3091 but we must still verify the address is invariant. */
3095 /* Don't mess with insns declared volatile. */
3096 if (MEM_VOLATILE_P (x
))
3104 fmt
= GET_RTX_FORMAT (code
);
3105 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3109 int tem
= invariant_p (XEXP (x
, i
));
3115 else if (fmt
[i
] == 'E')
3118 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3120 int tem
= invariant_p (XVECEXP (x
, i
, j
));
3130 return 1 + conditional
;
3134 /* Return nonzero if all the insns in the loop that set REG
3135 are INSN and the immediately following insns,
3136 and if each of those insns sets REG in an invariant way
3137 (not counting uses of REG in them).
3139 The value is 2 if some of these insns are only conditionally invariant.
3141 We assume that INSN itself is the first set of REG
3142 and that its source is invariant. */
3145 consec_sets_invariant_p (reg
, n_sets
, insn
)
3149 register rtx p
= insn
;
3150 register int regno
= REGNO (reg
);
3152 /* Number of sets we have to insist on finding after INSN. */
3153 int count
= n_sets
- 1;
3154 int old
= VARRAY_INT (set_in_loop
, regno
);
3158 /* If N_SETS hit the limit, we can't rely on its value. */
3162 VARRAY_INT (set_in_loop
, regno
) = 0;
3166 register enum rtx_code code
;
3170 code
= GET_CODE (p
);
3172 /* If library call, skip to end of it. */
3173 if (code
== INSN
&& (temp
= find_reg_note (p
, REG_LIBCALL
, NULL_RTX
)))
3178 && (set
= single_set (p
))
3179 && GET_CODE (SET_DEST (set
)) == REG
3180 && REGNO (SET_DEST (set
)) == regno
)
3182 this = invariant_p (SET_SRC (set
));
3185 else if ((temp
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
)))
3187 /* If this is a libcall, then any invariant REG_EQUAL note is OK.
3188 If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
3190 this = (CONSTANT_P (XEXP (temp
, 0))
3191 || (find_reg_note (p
, REG_RETVAL
, NULL_RTX
)
3192 && invariant_p (XEXP (temp
, 0))));
3199 else if (code
!= NOTE
)
3201 VARRAY_INT (set_in_loop
, regno
) = old
;
3206 VARRAY_INT (set_in_loop
, regno
) = old
;
3207 /* If invariant_p ever returned 2, we return 2. */
3208 return 1 + (value
& 2);
3212 /* I don't think this condition is sufficient to allow INSN
3213 to be moved, so we no longer test it. */
3215 /* Return 1 if all insns in the basic block of INSN and following INSN
3216 that set REG are invariant according to TABLE. */
3219 all_sets_invariant_p (reg
, insn
, table
)
3223 register rtx p
= insn
;
3224 register int regno
= REGNO (reg
);
3228 register enum rtx_code code
;
3230 code
= GET_CODE (p
);
3231 if (code
== CODE_LABEL
|| code
== JUMP_INSN
)
3233 if (code
== INSN
&& GET_CODE (PATTERN (p
)) == SET
3234 && GET_CODE (SET_DEST (PATTERN (p
))) == REG
3235 && REGNO (SET_DEST (PATTERN (p
))) == regno
)
3237 if (!invariant_p (SET_SRC (PATTERN (p
)), table
))
3244 /* Look at all uses (not sets) of registers in X. For each, if it is
3245 the single use, set USAGE[REGNO] to INSN; if there was a previous use in
3246 a different insn, set USAGE[REGNO] to const0_rtx. */
3249 find_single_use_in_loop (insn
, x
, usage
)
3254 enum rtx_code code
= GET_CODE (x
);
3255 char *fmt
= GET_RTX_FORMAT (code
);
3259 VARRAY_RTX (usage
, REGNO (x
))
3260 = (VARRAY_RTX (usage
, REGNO (x
)) != 0
3261 && VARRAY_RTX (usage
, REGNO (x
)) != insn
)
3262 ? const0_rtx
: insn
;
3264 else if (code
== SET
)
3266 /* Don't count SET_DEST if it is a REG; otherwise count things
3267 in SET_DEST because if a register is partially modified, it won't
3268 show up as a potential movable so we don't care how USAGE is set
3270 if (GET_CODE (SET_DEST (x
)) != REG
)
3271 find_single_use_in_loop (insn
, SET_DEST (x
), usage
);
3272 find_single_use_in_loop (insn
, SET_SRC (x
), usage
);
3275 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3277 if (fmt
[i
] == 'e' && XEXP (x
, i
) != 0)
3278 find_single_use_in_loop (insn
, XEXP (x
, i
), usage
);
3279 else if (fmt
[i
] == 'E')
3280 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3281 find_single_use_in_loop (insn
, XVECEXP (x
, i
, j
), usage
);
3285 /* Count and record any set in X which is contained in INSN. Update
3286 MAY_NOT_MOVE and LAST_SET for any register set in X. */
3289 count_one_set (insn
, x
, may_not_move
, last_set
)
3291 varray_type may_not_move
;
3294 if (GET_CODE (x
) == CLOBBER
&& GET_CODE (XEXP (x
, 0)) == REG
)
3295 /* Don't move a reg that has an explicit clobber.
3296 It's not worth the pain to try to do it correctly. */
3297 VARRAY_CHAR (may_not_move
, REGNO (XEXP (x
, 0))) = 1;
3299 if (GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
3301 rtx dest
= SET_DEST (x
);
3302 while (GET_CODE (dest
) == SUBREG
3303 || GET_CODE (dest
) == ZERO_EXTRACT
3304 || GET_CODE (dest
) == SIGN_EXTRACT
3305 || GET_CODE (dest
) == STRICT_LOW_PART
)
3306 dest
= XEXP (dest
, 0);
3307 if (GET_CODE (dest
) == REG
)
3309 register int regno
= REGNO (dest
);
3310 /* If this is the first setting of this reg
3311 in current basic block, and it was set before,
3312 it must be set in two basic blocks, so it cannot
3313 be moved out of the loop. */
3314 if (VARRAY_INT (set_in_loop
, regno
) > 0
3315 && last_set
[regno
] == 0)
3316 VARRAY_CHAR (may_not_move
, regno
) = 1;
3317 /* If this is not first setting in current basic block,
3318 see if reg was used in between previous one and this.
3319 If so, neither one can be moved. */
3320 if (last_set
[regno
] != 0
3321 && reg_used_between_p (dest
, last_set
[regno
], insn
))
3322 VARRAY_CHAR (may_not_move
, regno
) = 1;
3323 if (VARRAY_INT (set_in_loop
, regno
) < 127)
3324 ++VARRAY_INT (set_in_loop
, regno
);
3325 last_set
[regno
] = insn
;
3330 /* Increment SET_IN_LOOP at the index of each register
3331 that is modified by an insn between FROM and TO.
3332 If the value of an element of SET_IN_LOOP becomes 127 or more,
3333 stop incrementing it, to avoid overflow.
3335 Store in SINGLE_USAGE[I] the single insn in which register I is
3336 used, if it is only used once. Otherwise, it is set to 0 (for no
3337 uses) or const0_rtx for more than one use. This parameter may be zero,
3338 in which case this processing is not done.
3340 Store in *COUNT_PTR the number of actual instruction
3341 in the loop. We use this to decide what is worth moving out. */
3343 /* last_set[n] is nonzero iff reg n has been set in the current basic block.
3344 In that case, it is the insn that last set reg n. */
3347 count_loop_regs_set (from
, to
, may_not_move
, single_usage
, count_ptr
, nregs
)
3348 register rtx from
, to
;
3349 varray_type may_not_move
;
3350 varray_type single_usage
;
3354 register rtx
*last_set
= (rtx
*) alloca (nregs
* sizeof (rtx
));
3356 register int count
= 0;
3358 bzero ((char *) last_set
, nregs
* sizeof (rtx
));
3359 for (insn
= from
; insn
!= to
; insn
= NEXT_INSN (insn
))
3361 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
3365 /* If requested, record registers that have exactly one use. */
3368 find_single_use_in_loop (insn
, PATTERN (insn
), single_usage
);
3370 /* Include uses in REG_EQUAL notes. */
3371 if (REG_NOTES (insn
))
3372 find_single_use_in_loop (insn
, REG_NOTES (insn
), single_usage
);
3375 if (GET_CODE (PATTERN (insn
)) == SET
3376 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
3377 count_one_set (insn
, PATTERN (insn
), may_not_move
, last_set
);
3378 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
3381 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
3382 count_one_set (insn
, XVECEXP (PATTERN (insn
), 0, i
),
3383 may_not_move
, last_set
);
3387 if (GET_CODE (insn
) == CODE_LABEL
|| GET_CODE (insn
) == JUMP_INSN
)
3388 bzero ((char *) last_set
, nregs
* sizeof (rtx
));
3393 /* Given a loop that is bounded by LOOP_START and LOOP_END
3394 and that is entered at SCAN_START,
3395 return 1 if the register set in SET contained in insn INSN is used by
3396 any insn that precedes INSN in cyclic order starting
3397 from the loop entry point.
3399 We don't want to use INSN_LUID here because if we restrict INSN to those
3400 that have a valid INSN_LUID, it means we cannot move an invariant out
3401 from an inner loop past two loops. */
3404 loop_reg_used_before_p (set
, insn
, loop_start
, scan_start
, loop_end
)
3405 rtx set
, insn
, loop_start
, scan_start
, loop_end
;
3407 rtx reg
= SET_DEST (set
);
3410 /* Scan forward checking for register usage. If we hit INSN, we
3411 are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
3412 for (p
= scan_start
; p
!= insn
; p
= NEXT_INSN (p
))
3414 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i'
3415 && reg_overlap_mentioned_p (reg
, PATTERN (p
)))
3425 /* A "basic induction variable" or biv is a pseudo reg that is set
3426 (within this loop) only by incrementing or decrementing it. */
3427 /* A "general induction variable" or giv is a pseudo reg whose
3428 value is a linear function of a biv. */
3430 /* Bivs are recognized by `basic_induction_var';
3431 Givs by `general_induction_var'. */
3433 /* Indexed by register number, indicates whether or not register is an
3434 induction variable, and if so what type. */
3436 enum iv_mode
*reg_iv_type
;
3438 /* Indexed by register number, contains pointer to `struct induction'
3439 if register is an induction variable. This holds general info for
3440 all induction variables. */
3442 struct induction
**reg_iv_info
;
3444 /* Indexed by register number, contains pointer to `struct iv_class'
3445 if register is a basic induction variable. This holds info describing
3446 the class (a related group) of induction variables that the biv belongs
3449 struct iv_class
**reg_biv_class
;
3451 /* The head of a list which links together (via the next field)
3452 every iv class for the current loop. */
3454 struct iv_class
*loop_iv_list
;
3456 /* Communication with routines called via `note_stores'. */
3458 static rtx note_insn
;
3460 /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3462 static rtx addr_placeholder
;
3464 /* ??? Unfinished optimizations, and possible future optimizations,
3465 for the strength reduction code. */
3467 /* ??? The interaction of biv elimination, and recognition of 'constant'
3468 bivs, may cause problems. */
3470 /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3471 performance problems.
3473 Perhaps don't eliminate things that can be combined with an addressing
3474 mode. Find all givs that have the same biv, mult_val, and add_val;
3475 then for each giv, check to see if its only use dies in a following
3476 memory address. If so, generate a new memory address and check to see
3477 if it is valid. If it is valid, then store the modified memory address,
3478 otherwise, mark the giv as not done so that it will get its own iv. */
3480 /* ??? Could try to optimize branches when it is known that a biv is always
3483 /* ??? When replace a biv in a compare insn, we should replace with closest
3484 giv so that an optimized branch can still be recognized by the combiner,
3485 e.g. the VAX acb insn. */
3487 /* ??? Many of the checks involving uid_luid could be simplified if regscan
3488 was rerun in loop_optimize whenever a register was added or moved.
3489 Also, some of the optimizations could be a little less conservative. */
3491 /* Perform strength reduction and induction variable elimination.
3493 Pseudo registers created during this function will be beyond the last
3494 valid index in several tables including n_times_set and regno_last_uid.
3495 This does not cause a problem here, because the added registers cannot be
3496 givs outside of their loop, and hence will never be reconsidered.
3497 But scan_loop must check regnos to make sure they are in bounds.
3499 SCAN_START is the first instruction in the loop, as the loop would
3500 actually be executed. END is the NOTE_INSN_LOOP_END. LOOP_TOP is
3501 the first instruction in the loop, as it is layed out in the
3502 instruction stream. LOOP_START is the NOTE_INSN_LOOP_BEG. */
3505 strength_reduce (scan_start
, end
, loop_top
, insn_count
,
3506 loop_start
, loop_end
, unroll_p
, bct_p
)
3513 int unroll_p
, bct_p ATTRIBUTE_UNUSED
;
3520 /* This is 1 if current insn is not executed at least once for every loop
3522 int not_every_iteration
= 0;
3523 /* This is 1 if current insn may be executed more than once for every
3525 int maybe_multiple
= 0;
3526 /* Temporary list pointers for traversing loop_iv_list. */
3527 struct iv_class
*bl
, **backbl
;
3528 /* Ratio of extra register life span we can justify
3529 for saving an instruction. More if loop doesn't call subroutines
3530 since in that case saving an insn makes more difference
3531 and more registers are available. */
3532 /* ??? could set this to last value of threshold in move_movables */
3533 int threshold
= (loop_has_call
? 1 : 2) * (3 + n_non_fixed_regs
);
3534 /* Map of pseudo-register replacements. */
3538 rtx end_insert_before
;
3540 struct loop_info loop_iteration_info
;
3541 struct loop_info
*loop_info
= &loop_iteration_info
;
3543 /* If scan_start points to the loop exit test, we have to be wary of
3544 subversive use of gotos inside expression statements. */
3545 if (prev_nonnote_insn (scan_start
) != prev_nonnote_insn (loop_start
))
3546 maybe_multiple
= back_branch_in_range_p (scan_start
, loop_start
, loop_end
);
3548 reg_iv_type
= (enum iv_mode
*) alloca (max_reg_before_loop
3549 * sizeof (enum iv_mode
));
3550 bzero ((char *) reg_iv_type
, max_reg_before_loop
* sizeof (enum iv_mode
));
3551 reg_iv_info
= (struct induction
**)
3552 alloca (max_reg_before_loop
* sizeof (struct induction
*));
3553 bzero ((char *) reg_iv_info
, (max_reg_before_loop
3554 * sizeof (struct induction
*)));
3555 reg_biv_class
= (struct iv_class
**)
3556 alloca (max_reg_before_loop
* sizeof (struct iv_class
*));
3557 bzero ((char *) reg_biv_class
, (max_reg_before_loop
3558 * sizeof (struct iv_class
*)));
3561 addr_placeholder
= gen_reg_rtx (Pmode
);
3563 /* Save insn immediately after the loop_end. Insns inserted after loop_end
3564 must be put before this insn, so that they will appear in the right
3565 order (i.e. loop order).
3567 If loop_end is the end of the current function, then emit a
3568 NOTE_INSN_DELETED after loop_end and set end_insert_before to the
3570 if (NEXT_INSN (loop_end
) != 0)
3571 end_insert_before
= NEXT_INSN (loop_end
);
3573 end_insert_before
= emit_note_after (NOTE_INSN_DELETED
, loop_end
);
3575 /* Scan through loop to find all possible bivs. */
3577 for (p
= next_insn_in_loop (scan_start
, scan_start
, end
, loop_top
);
3579 p
= next_insn_in_loop (p
, scan_start
, end
, loop_top
))
3581 if (GET_CODE (p
) == INSN
3582 && (set
= single_set (p
))
3583 && GET_CODE (SET_DEST (set
)) == REG
)
3585 dest_reg
= SET_DEST (set
);
3586 if (REGNO (dest_reg
) < max_reg_before_loop
3587 && REGNO (dest_reg
) >= FIRST_PSEUDO_REGISTER
3588 && reg_iv_type
[REGNO (dest_reg
)] != NOT_BASIC_INDUCT
)
3590 if (basic_induction_var (SET_SRC (set
), GET_MODE (SET_SRC (set
)),
3591 dest_reg
, p
, &inc_val
, &mult_val
))
3593 /* It is a possible basic induction variable.
3594 Create and initialize an induction structure for it. */
3597 = (struct induction
*) alloca (sizeof (struct induction
));
3599 record_biv (v
, p
, dest_reg
, inc_val
, mult_val
,
3600 not_every_iteration
, maybe_multiple
);
3601 reg_iv_type
[REGNO (dest_reg
)] = BASIC_INDUCT
;
3603 else if (REGNO (dest_reg
) < max_reg_before_loop
)
3604 reg_iv_type
[REGNO (dest_reg
)] = NOT_BASIC_INDUCT
;
3608 /* Past CODE_LABEL, we get to insns that may be executed multiple
3609 times. The only way we can be sure that they can't is if every
3610 jump insn between here and the end of the loop either
3611 returns, exits the loop, is a jump to a location that is still
3612 behind the label, or is a jump to the loop start. */
3614 if (GET_CODE (p
) == CODE_LABEL
)
3622 insn
= NEXT_INSN (insn
);
3623 if (insn
== scan_start
)
3631 if (insn
== scan_start
)
3635 if (GET_CODE (insn
) == JUMP_INSN
3636 && GET_CODE (PATTERN (insn
)) != RETURN
3637 && (! condjump_p (insn
)
3638 || (JUMP_LABEL (insn
) != 0
3639 && JUMP_LABEL (insn
) != scan_start
3640 && (INSN_UID (JUMP_LABEL (insn
)) >= max_uid_for_loop
3641 || (INSN_UID (p
) < max_uid_for_loop
3642 ? (INSN_LUID (JUMP_LABEL (insn
))
3644 : (INSN_UID (insn
) >= max_uid_for_loop
3645 || (INSN_LUID (JUMP_LABEL (insn
))
3646 < INSN_LUID (insn
))))))))
3654 /* Past a jump, we get to insns for which we can't count
3655 on whether they will be executed during each iteration. */
3656 /* This code appears twice in strength_reduce. There is also similar
3657 code in scan_loop. */
3658 if (GET_CODE (p
) == JUMP_INSN
3659 /* If we enter the loop in the middle, and scan around to the
3660 beginning, don't set not_every_iteration for that.
3661 This can be any kind of jump, since we want to know if insns
3662 will be executed if the loop is executed. */
3663 && ! (JUMP_LABEL (p
) == loop_top
3664 && ((NEXT_INSN (NEXT_INSN (p
)) == loop_end
&& simplejump_p (p
))
3665 || (NEXT_INSN (p
) == loop_end
&& condjump_p (p
)))))
3669 /* If this is a jump outside the loop, then it also doesn't
3670 matter. Check to see if the target of this branch is on the
3671 loop_number_exits_labels list. */
3673 for (label
= loop_number_exit_labels
[uid_loop_num
[INSN_UID (loop_start
)]];
3675 label
= LABEL_NEXTREF (label
))
3676 if (XEXP (label
, 0) == JUMP_LABEL (p
))
3680 not_every_iteration
= 1;
3683 else if (GET_CODE (p
) == NOTE
)
3685 /* At the virtual top of a converted loop, insns are again known to
3686 be executed each iteration: logically, the loop begins here
3687 even though the exit code has been duplicated. */
3688 if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_VTOP
&& loop_depth
== 0)
3689 not_every_iteration
= 0;
3690 else if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_BEG
)
3692 else if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_END
)
3696 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3697 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3698 or not an insn is known to be executed each iteration of the
3699 loop, whether or not any iterations are known to occur.
3701 Therefore, if we have just passed a label and have no more labels
3702 between here and the test insn of the loop, we know these insns
3703 will be executed each iteration. */
3705 if (not_every_iteration
&& GET_CODE (p
) == CODE_LABEL
3706 && no_labels_between_p (p
, loop_end
))
3707 not_every_iteration
= 0;
3710 /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3711 Make a sanity check against n_times_set. */
3712 for (backbl
= &loop_iv_list
, bl
= *backbl
; bl
; bl
= bl
->next
)
3714 if (reg_iv_type
[bl
->regno
] != BASIC_INDUCT
3715 /* Above happens if register modified by subreg, etc. */
3716 /* Make sure it is not recognized as a basic induction var: */
3717 || VARRAY_INT (n_times_set
, bl
->regno
) != bl
->biv_count
3718 /* If never incremented, it is invariant that we decided not to
3719 move. So leave it alone. */
3720 || ! bl
->incremented
)
3722 if (loop_dump_stream
)
3723 fprintf (loop_dump_stream
, "Reg %d: biv discarded, %s\n",
3725 (reg_iv_type
[bl
->regno
] != BASIC_INDUCT
3726 ? "not induction variable"
3727 : (! bl
->incremented
? "never incremented"
3730 reg_iv_type
[bl
->regno
] = NOT_BASIC_INDUCT
;
3737 if (loop_dump_stream
)
3738 fprintf (loop_dump_stream
, "Reg %d: biv verified\n", bl
->regno
);
3742 /* Exit if there are no bivs. */
3745 /* Can still unroll the loop anyways, but indicate that there is no
3746 strength reduction info available. */
3748 unroll_loop (loop_end
, insn_count
, loop_start
, end_insert_before
,
3754 /* Find initial value for each biv by searching backwards from loop_start,
3755 halting at first label. Also record any test condition. */
3758 for (p
= loop_start
; p
&& GET_CODE (p
) != CODE_LABEL
; p
= PREV_INSN (p
))
3762 if (GET_CODE (p
) == CALL_INSN
)
3765 if (GET_CODE (p
) == INSN
|| GET_CODE (p
) == JUMP_INSN
3766 || GET_CODE (p
) == CALL_INSN
)
3767 note_stores (PATTERN (p
), record_initial
);
3769 /* Record any test of a biv that branches around the loop if no store
3770 between it and the start of loop. We only care about tests with
3771 constants and registers and only certain of those. */
3772 if (GET_CODE (p
) == JUMP_INSN
3773 && JUMP_LABEL (p
) != 0
3774 && next_real_insn (JUMP_LABEL (p
)) == next_real_insn (loop_end
)
3775 && (test
= get_condition_for_loop (p
)) != 0
3776 && GET_CODE (XEXP (test
, 0)) == REG
3777 && REGNO (XEXP (test
, 0)) < max_reg_before_loop
3778 && (bl
= reg_biv_class
[REGNO (XEXP (test
, 0))]) != 0
3779 && valid_initial_value_p (XEXP (test
, 1), p
, call_seen
, loop_start
)
3780 && bl
->init_insn
== 0)
3782 /* If an NE test, we have an initial value! */
3783 if (GET_CODE (test
) == NE
)
3786 bl
->init_set
= gen_rtx_SET (VOIDmode
,
3787 XEXP (test
, 0), XEXP (test
, 1));
3790 bl
->initial_test
= test
;
3794 /* Look at the each biv and see if we can say anything better about its
3795 initial value from any initializing insns set up above. (This is done
3796 in two passes to avoid missing SETs in a PARALLEL.) */
3797 for (bl
= loop_iv_list
; bl
; bl
= bl
->next
)
3802 if (! bl
->init_insn
)
3805 /* IF INIT_INSN has a REG_EQUAL or REG_EQUIV note and the value
3806 is a constant, use the value of that. */
3807 if (((note
= find_reg_note (bl
->init_insn
, REG_EQUAL
, 0)) != NULL
3808 && CONSTANT_P (XEXP (note
, 0)))
3809 || ((note
= find_reg_note (bl
->init_insn
, REG_EQUIV
, 0)) != NULL
3810 && CONSTANT_P (XEXP (note
, 0))))
3811 src
= XEXP (note
, 0);
3813 src
= SET_SRC (bl
->init_set
);
3815 if (loop_dump_stream
)
3816 fprintf (loop_dump_stream
,
3817 "Biv %d initialized at insn %d: initial value ",
3818 bl
->regno
, INSN_UID (bl
->init_insn
));
3820 if ((GET_MODE (src
) == GET_MODE (regno_reg_rtx
[bl
->regno
])
3821 || GET_MODE (src
) == VOIDmode
)
3822 && valid_initial_value_p (src
, bl
->init_insn
, call_seen
, loop_start
))
3824 bl
->initial_value
= src
;
3826 if (loop_dump_stream
)
3828 if (GET_CODE (src
) == CONST_INT
)
3830 fprintf (loop_dump_stream
, HOST_WIDE_INT_PRINT_DEC
, INTVAL (src
));
3831 fputc ('\n', loop_dump_stream
);
3835 print_rtl (loop_dump_stream
, src
);
3836 fprintf (loop_dump_stream
, "\n");
3842 /* Biv initial value is not simple move,
3843 so let it keep initial value of "itself". */
3845 if (loop_dump_stream
)
3846 fprintf (loop_dump_stream
, "is complex\n");
3850 /* Search the loop for general induction variables. */
3852 /* A register is a giv if: it is only set once, it is a function of a
3853 biv and a constant (or invariant), and it is not a biv. */
3855 not_every_iteration
= 0;
3861 /* At end of a straight-in loop, we are done.
3862 At end of a loop entered at the bottom, scan the top. */
3863 if (p
== scan_start
)
3871 if (p
== scan_start
)
3875 /* Look for a general induction variable in a register. */
3876 if (GET_CODE (p
) == INSN
3877 && (set
= single_set (p
))
3878 && GET_CODE (SET_DEST (set
)) == REG
3879 && ! VARRAY_CHAR (may_not_optimize
, REGNO (SET_DEST (set
))))
3886 rtx last_consec_insn
;
3888 dest_reg
= SET_DEST (set
);
3889 if (REGNO (dest_reg
) < FIRST_PSEUDO_REGISTER
)
3892 if (/* SET_SRC is a giv. */
3893 (general_induction_var (SET_SRC (set
), &src_reg
, &add_val
,
3894 &mult_val
, 0, &benefit
)
3895 /* Equivalent expression is a giv. */
3896 || ((regnote
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
))
3897 && general_induction_var (XEXP (regnote
, 0), &src_reg
,
3898 &add_val
, &mult_val
, 0,
3900 /* Don't try to handle any regs made by loop optimization.
3901 We have nothing on them in regno_first_uid, etc. */
3902 && REGNO (dest_reg
) < max_reg_before_loop
3903 /* Don't recognize a BASIC_INDUCT_VAR here. */
3904 && dest_reg
!= src_reg
3905 /* This must be the only place where the register is set. */
3906 && (VARRAY_INT (n_times_set
, REGNO (dest_reg
)) == 1
3907 /* or all sets must be consecutive and make a giv. */
3908 || (benefit
= consec_sets_giv (benefit
, p
,
3910 &add_val
, &mult_val
,
3911 &last_consec_insn
))))
3914 = (struct induction
*) alloca (sizeof (struct induction
));
3916 /* If this is a library call, increase benefit. */
3917 if (find_reg_note (p
, REG_RETVAL
, NULL_RTX
))
3918 benefit
+= libcall_benefit (p
);
3920 /* Skip the consecutive insns, if there are any. */
3921 if (VARRAY_INT (n_times_set
, REGNO (dest_reg
)) != 1)
3922 p
= last_consec_insn
;
3924 record_giv (v
, p
, src_reg
, dest_reg
, mult_val
, add_val
, benefit
,
3925 DEST_REG
, not_every_iteration
, NULL_PTR
, loop_start
,
3931 #ifndef DONT_REDUCE_ADDR
3932 /* Look for givs which are memory addresses. */
3933 /* This resulted in worse code on a VAX 8600. I wonder if it
3935 if (GET_CODE (p
) == INSN
)
3936 find_mem_givs (PATTERN (p
), p
, not_every_iteration
, loop_start
,
3940 /* Update the status of whether giv can derive other givs. This can
3941 change when we pass a label or an insn that updates a biv. */
3942 if (GET_CODE (p
) == INSN
|| GET_CODE (p
) == JUMP_INSN
3943 || GET_CODE (p
) == CODE_LABEL
)
3944 update_giv_derive (p
);
3946 /* Past a jump, we get to insns for which we can't count
3947 on whether they will be executed during each iteration. */
3948 /* This code appears twice in strength_reduce. There is also similar
3949 code in scan_loop. */
3950 if (GET_CODE (p
) == JUMP_INSN
3951 /* If we enter the loop in the middle, and scan around to the
3952 beginning, don't set not_every_iteration for that.
3953 This can be any kind of jump, since we want to know if insns
3954 will be executed if the loop is executed. */
3955 && ! (JUMP_LABEL (p
) == loop_top
3956 && ((NEXT_INSN (NEXT_INSN (p
)) == loop_end
&& simplejump_p (p
))
3957 || (NEXT_INSN (p
) == loop_end
&& condjump_p (p
)))))
3961 /* If this is a jump outside the loop, then it also doesn't
3962 matter. Check to see if the target of this branch is on the
3963 loop_number_exits_labels list. */
3965 for (label
= loop_number_exit_labels
[uid_loop_num
[INSN_UID (loop_start
)]];
3967 label
= LABEL_NEXTREF (label
))
3968 if (XEXP (label
, 0) == JUMP_LABEL (p
))
3972 not_every_iteration
= 1;
3975 else if (GET_CODE (p
) == NOTE
)
3977 /* At the virtual top of a converted loop, insns are again known to
3978 be executed each iteration: logically, the loop begins here
3979 even though the exit code has been duplicated. */
3980 if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_VTOP
&& loop_depth
== 0)
3981 not_every_iteration
= 0;
3982 else if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_BEG
)
3984 else if (NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_END
)
3988 /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3989 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3990 or not an insn is known to be executed each iteration of the
3991 loop, whether or not any iterations are known to occur.
3993 Therefore, if we have just passed a label and have no more labels
3994 between here and the test insn of the loop, we know these insns
3995 will be executed each iteration. */
3997 if (not_every_iteration
&& GET_CODE (p
) == CODE_LABEL
3998 && no_labels_between_p (p
, loop_end
))
3999 not_every_iteration
= 0;
4002 /* Try to calculate and save the number of loop iterations. This is
4003 set to zero if the actual number can not be calculated. This must
4004 be called after all giv's have been identified, since otherwise it may
4005 fail if the iteration variable is a giv. */
4007 loop_iterations (loop_start
, loop_end
, loop_info
);
4009 /* Now for each giv for which we still don't know whether or not it is
4010 replaceable, check to see if it is replaceable because its final value
4011 can be calculated. This must be done after loop_iterations is called,
4012 so that final_giv_value will work correctly. */
4014 for (bl
= loop_iv_list
; bl
; bl
= bl
->next
)
4016 struct induction
*v
;
4018 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
4019 if (! v
->replaceable
&& ! v
->not_replaceable
)
4020 check_final_value (v
, loop_start
, loop_end
, loop_info
->n_iterations
);
4023 /* Try to prove that the loop counter variable (if any) is always
4024 nonnegative; if so, record that fact with a REG_NONNEG note
4025 so that "decrement and branch until zero" insn can be used. */
4026 check_dbra_loop (loop_end
, insn_count
, loop_start
, loop_info
);
4028 /* Create reg_map to hold substitutions for replaceable giv regs. */
4029 reg_map
= (rtx
*) alloca (max_reg_before_loop
* sizeof (rtx
));
4030 bzero ((char *) reg_map
, max_reg_before_loop
* sizeof (rtx
));
4032 /* Examine each iv class for feasibility of strength reduction/induction
4033 variable elimination. */
4035 for (bl
= loop_iv_list
; bl
; bl
= bl
->next
)
4037 struct induction
*v
;
4040 rtx final_value
= 0;
4042 /* Test whether it will be possible to eliminate this biv
4043 provided all givs are reduced. This is possible if either
4044 the reg is not used outside the loop, or we can compute
4045 what its final value will be.
4047 For architectures with a decrement_and_branch_until_zero insn,
4048 don't do this if we put a REG_NONNEG note on the endtest for
4051 /* Compare against bl->init_insn rather than loop_start.
4052 We aren't concerned with any uses of the biv between
4053 init_insn and loop_start since these won't be affected
4054 by the value of the biv elsewhere in the function, so
4055 long as init_insn doesn't use the biv itself.
4056 March 14, 1989 -- self@bayes.arc.nasa.gov */
4058 if ((uid_luid
[REGNO_LAST_UID (bl
->regno
)] < INSN_LUID (loop_end
)
4060 && INSN_UID (bl
->init_insn
) < max_uid_for_loop
4061 && uid_luid
[REGNO_FIRST_UID (bl
->regno
)] >= INSN_LUID (bl
->init_insn
)
4062 #ifdef HAVE_decrement_and_branch_until_zero
4065 && ! reg_mentioned_p (bl
->biv
->dest_reg
, SET_SRC (bl
->init_set
)))
4066 || ((final_value
= final_biv_value (bl
, loop_start
, loop_end
,
4067 loop_info
->n_iterations
))
4068 #ifdef HAVE_decrement_and_branch_until_zero
4072 bl
->eliminable
= maybe_eliminate_biv (bl
, loop_start
, end
, 0,
4073 threshold
, insn_count
);
4076 if (loop_dump_stream
)
4078 fprintf (loop_dump_stream
,
4079 "Cannot eliminate biv %d.\n",
4081 fprintf (loop_dump_stream
,
4082 "First use: insn %d, last use: insn %d.\n",
4083 REGNO_FIRST_UID (bl
->regno
),
4084 REGNO_LAST_UID (bl
->regno
));
4088 /* Combine all giv's for this iv_class. */
4091 /* This will be true at the end, if all givs which depend on this
4092 biv have been strength reduced.
4093 We can't (currently) eliminate the biv unless this is so. */
4096 /* Check each giv in this class to see if we will benefit by reducing
4097 it. Skip giv's combined with others. */
4098 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
4100 struct induction
*tv
;
4102 if (v
->ignore
|| v
->same
)
4105 benefit
= v
->benefit
;
4107 /* Reduce benefit if not replaceable, since we will insert
4108 a move-insn to replace the insn that calculates this giv.
4109 Don't do this unless the giv is a user variable, since it
4110 will often be marked non-replaceable because of the duplication
4111 of the exit code outside the loop. In such a case, the copies
4112 we insert are dead and will be deleted. So they don't have
4113 a cost. Similar situations exist. */
4114 /* ??? The new final_[bg]iv_value code does a much better job
4115 of finding replaceable giv's, and hence this code may no longer
4117 if (! v
->replaceable
&& ! bl
->eliminable
4118 && REG_USERVAR_P (v
->dest_reg
))
4119 benefit
-= copy_cost
;
4121 /* Decrease the benefit to count the add-insns that we will
4122 insert to increment the reduced reg for the giv. */
4123 benefit
-= add_cost
* bl
->biv_count
;
4125 /* Decide whether to strength-reduce this giv or to leave the code
4126 unchanged (recompute it from the biv each time it is used).
4127 This decision can be made independently for each giv. */
4130 /* Attempt to guess whether autoincrement will handle some of the
4131 new add insns; if so, increase BENEFIT (undo the subtraction of
4132 add_cost that was done above). */
4133 if (v
->giv_type
== DEST_ADDR
4134 && GET_CODE (v
->mult_val
) == CONST_INT
)
4136 if (HAVE_POST_INCREMENT
4137 && INTVAL (v
->mult_val
) == GET_MODE_SIZE (v
->mem_mode
))
4138 benefit
+= add_cost
* bl
->biv_count
;
4139 else if (HAVE_PRE_INCREMENT
4140 && INTVAL (v
->mult_val
) == GET_MODE_SIZE (v
->mem_mode
))
4141 benefit
+= add_cost
* bl
->biv_count
;
4142 else if (HAVE_POST_DECREMENT
4143 && -INTVAL (v
->mult_val
) == GET_MODE_SIZE (v
->mem_mode
))
4144 benefit
+= add_cost
* bl
->biv_count
;
4145 else if (HAVE_PRE_DECREMENT
4146 && -INTVAL (v
->mult_val
) == GET_MODE_SIZE (v
->mem_mode
))
4147 benefit
+= add_cost
* bl
->biv_count
;
4151 /* If an insn is not to be strength reduced, then set its ignore
4152 flag, and clear all_reduced. */
4154 /* A giv that depends on a reversed biv must be reduced if it is
4155 used after the loop exit, otherwise, it would have the wrong
4156 value after the loop exit. To make it simple, just reduce all
4157 of such giv's whether or not we know they are used after the loop
4160 if ( ! flag_reduce_all_givs
&& v
->lifetime
* threshold
* benefit
< insn_count
4163 if (loop_dump_stream
)
4164 fprintf (loop_dump_stream
,
4165 "giv of insn %d not worth while, %d vs %d.\n",
4167 v
->lifetime
* threshold
* benefit
, insn_count
);
4173 /* Check that we can increment the reduced giv without a
4174 multiply insn. If not, reject it. */
4176 for (tv
= bl
->biv
; tv
; tv
= tv
->next_iv
)
4177 if (tv
->mult_val
== const1_rtx
4178 && ! product_cheap_p (tv
->add_val
, v
->mult_val
))
4180 if (loop_dump_stream
)
4181 fprintf (loop_dump_stream
,
4182 "giv of insn %d: would need a multiply.\n",
4183 INSN_UID (v
->insn
));
4191 /* Reduce each giv that we decided to reduce. */
4193 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
4195 struct induction
*tv
;
4196 if (! v
->ignore
&& v
->same
== 0)
4198 int auto_inc_opt
= 0;
4200 v
->new_reg
= gen_reg_rtx (v
->mode
);
4203 /* If the target has auto-increment addressing modes, and
4204 this is an address giv, then try to put the increment
4205 immediately after its use, so that flow can create an
4206 auto-increment addressing mode. */
4207 if (v
->giv_type
== DEST_ADDR
&& bl
->biv_count
== 1
4208 && bl
->biv
->always_executed
&& ! bl
->biv
->maybe_multiple
4209 /* We don't handle reversed biv's because bl->biv->insn
4210 does not have a valid INSN_LUID. */
4212 && v
->always_executed
&& ! v
->maybe_multiple
4213 && INSN_UID (v
->insn
) < max_uid_for_loop
)
4215 /* If other giv's have been combined with this one, then
4216 this will work only if all uses of the other giv's occur
4217 before this giv's insn. This is difficult to check.
4219 We simplify this by looking for the common case where
4220 there is one DEST_REG giv, and this giv's insn is the
4221 last use of the dest_reg of that DEST_REG giv. If the
4222 increment occurs after the address giv, then we can
4223 perform the optimization. (Otherwise, the increment
4224 would have to go before other_giv, and we would not be
4225 able to combine it with the address giv to get an
4226 auto-inc address.) */
4227 if (v
->combined_with
)
4229 struct induction
*other_giv
= 0;
4231 for (tv
= bl
->giv
; tv
; tv
= tv
->next_iv
)
4239 if (! tv
&& other_giv
4240 && REGNO (other_giv
->dest_reg
) < max_reg_before_loop
4241 && (REGNO_LAST_UID (REGNO (other_giv
->dest_reg
))
4242 == INSN_UID (v
->insn
))
4243 && INSN_LUID (v
->insn
) < INSN_LUID (bl
->biv
->insn
))
4246 /* Check for case where increment is before the address
4247 giv. Do this test in "loop order". */
4248 else if ((INSN_LUID (v
->insn
) > INSN_LUID (bl
->biv
->insn
)
4249 && (INSN_LUID (v
->insn
) < INSN_LUID (scan_start
)
4250 || (INSN_LUID (bl
->biv
->insn
)
4251 > INSN_LUID (scan_start
))))
4252 || (INSN_LUID (v
->insn
) < INSN_LUID (scan_start
)
4253 && (INSN_LUID (scan_start
)
4254 < INSN_LUID (bl
->biv
->insn
))))
4263 /* We can't put an insn immediately after one setting
4264 cc0, or immediately before one using cc0. */
4265 if ((auto_inc_opt
== 1 && sets_cc0_p (PATTERN (v
->insn
)))
4266 || (auto_inc_opt
== -1
4267 && (prev
= prev_nonnote_insn (v
->insn
)) != 0
4268 && GET_RTX_CLASS (GET_CODE (prev
)) == 'i'
4269 && sets_cc0_p (PATTERN (prev
))))
4275 v
->auto_inc_opt
= 1;
4279 /* For each place where the biv is incremented, add an insn
4280 to increment the new, reduced reg for the giv. */
4281 for (tv
= bl
->biv
; tv
; tv
= tv
->next_iv
)
4286 insert_before
= tv
->insn
;
4287 else if (auto_inc_opt
== 1)
4288 insert_before
= NEXT_INSN (v
->insn
);
4290 insert_before
= v
->insn
;
4292 if (tv
->mult_val
== const1_rtx
)
4293 emit_iv_add_mult (tv
->add_val
, v
->mult_val
,
4294 v
->new_reg
, v
->new_reg
, insert_before
);
4295 else /* tv->mult_val == const0_rtx */
4296 /* A multiply is acceptable here
4297 since this is presumed to be seldom executed. */
4298 emit_iv_add_mult (tv
->add_val
, v
->mult_val
,
4299 v
->add_val
, v
->new_reg
, insert_before
);
4302 /* Add code at loop start to initialize giv's reduced reg. */
4304 emit_iv_add_mult (bl
->initial_value
, v
->mult_val
,
4305 v
->add_val
, v
->new_reg
, loop_start
);
4309 /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
4312 For each giv register that can be reduced now: if replaceable,
4313 substitute reduced reg wherever the old giv occurs;
4314 else add new move insn "giv_reg = reduced_reg".
4316 Also check for givs whose first use is their definition and whose
4317 last use is the definition of another giv. If so, it is likely
4318 dead and should not be used to eliminate a biv. */
4319 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
4321 if (v
->same
&& v
->same
->ignore
)
4327 if (v
->giv_type
== DEST_REG
4328 && REGNO_FIRST_UID (REGNO (v
->dest_reg
)) == INSN_UID (v
->insn
))
4330 struct induction
*v1
;
4332 for (v1
= bl
->giv
; v1
; v1
= v1
->next_iv
)
4333 if (REGNO_LAST_UID (REGNO (v
->dest_reg
)) == INSN_UID (v1
->insn
))
4337 /* Update expression if this was combined, in case other giv was
4340 v
->new_reg
= replace_rtx (v
->new_reg
,
4341 v
->same
->dest_reg
, v
->same
->new_reg
);
4343 if (v
->giv_type
== DEST_ADDR
)
4344 /* Store reduced reg as the address in the memref where we found
4346 validate_change (v
->insn
, v
->location
, v
->new_reg
, 0);
4347 else if (v
->replaceable
)
4349 reg_map
[REGNO (v
->dest_reg
)] = v
->new_reg
;
4352 /* I can no longer duplicate the original problem. Perhaps
4353 this is unnecessary now? */
4355 /* Replaceable; it isn't strictly necessary to delete the old
4356 insn and emit a new one, because v->dest_reg is now dead.
4358 However, especially when unrolling loops, the special
4359 handling for (set REG0 REG1) in the second cse pass may
4360 make v->dest_reg live again. To avoid this problem, emit
4361 an insn to set the original giv reg from the reduced giv.
4362 We can not delete the original insn, since it may be part
4363 of a LIBCALL, and the code in flow that eliminates dead
4364 libcalls will fail if it is deleted. */
4365 emit_insn_after (gen_move_insn (v
->dest_reg
, v
->new_reg
),
4371 /* Not replaceable; emit an insn to set the original giv reg from
4372 the reduced giv, same as above. */
4373 emit_insn_after (gen_move_insn (v
->dest_reg
, v
->new_reg
),
4377 /* When a loop is reversed, givs which depend on the reversed
4378 biv, and which are live outside the loop, must be set to their
4379 correct final value. This insn is only needed if the giv is
4380 not replaceable. The correct final value is the same as the
4381 value that the giv starts the reversed loop with. */
4382 if (bl
->reversed
&& ! v
->replaceable
)
4383 emit_iv_add_mult (bl
->initial_value
, v
->mult_val
,
4384 v
->add_val
, v
->dest_reg
, end_insert_before
);
4385 else if (v
->final_value
)
4389 /* If the loop has multiple exits, emit the insn before the
4390 loop to ensure that it will always be executed no matter
4391 how the loop exits. Otherwise, emit the insn after the loop,
4392 since this is slightly more efficient. */
4393 if (loop_number_exit_count
[uid_loop_num
[INSN_UID (loop_start
)]])
4394 insert_before
= loop_start
;
4396 insert_before
= end_insert_before
;
4397 emit_insn_before (gen_move_insn (v
->dest_reg
, v
->final_value
),
4401 /* If the insn to set the final value of the giv was emitted
4402 before the loop, then we must delete the insn inside the loop
4403 that sets it. If this is a LIBCALL, then we must delete
4404 every insn in the libcall. Note, however, that
4405 final_giv_value will only succeed when there are multiple
4406 exits if the giv is dead at each exit, hence it does not
4407 matter that the original insn remains because it is dead
4409 /* Delete the insn inside the loop that sets the giv since
4410 the giv is now set before (or after) the loop. */
4411 delete_insn (v
->insn
);
4415 if (loop_dump_stream
)
4417 fprintf (loop_dump_stream
, "giv at %d reduced to ",
4418 INSN_UID (v
->insn
));
4419 print_rtl (loop_dump_stream
, v
->new_reg
);
4420 fprintf (loop_dump_stream
, "\n");
4424 /* All the givs based on the biv bl have been reduced if they
4427 /* For each giv not marked as maybe dead that has been combined with a
4428 second giv, clear any "maybe dead" mark on that second giv.
4429 v->new_reg will either be or refer to the register of the giv it
4432 Doing this clearing avoids problems in biv elimination where a
4433 giv's new_reg is a complex value that can't be put in the insn but
4434 the giv combined with (with a reg as new_reg) is marked maybe_dead.
4435 Since the register will be used in either case, we'd prefer it be
4436 used from the simpler giv. */
4438 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
4439 if (! v
->maybe_dead
&& v
->same
)
4440 v
->same
->maybe_dead
= 0;
4442 /* Try to eliminate the biv, if it is a candidate.
4443 This won't work if ! all_reduced,
4444 since the givs we planned to use might not have been reduced.
4446 We have to be careful that we didn't initially think we could eliminate
4447 this biv because of a giv that we now think may be dead and shouldn't
4448 be used as a biv replacement.
4450 Also, there is the possibility that we may have a giv that looks
4451 like it can be used to eliminate a biv, but the resulting insn
4452 isn't valid. This can happen, for example, on the 88k, where a
4453 JUMP_INSN can compare a register only with zero. Attempts to
4454 replace it with a compare with a constant will fail.
4456 Note that in cases where this call fails, we may have replaced some
4457 of the occurrences of the biv with a giv, but no harm was done in
4458 doing so in the rare cases where it can occur. */
4460 if (all_reduced
== 1 && bl
->eliminable
4461 && maybe_eliminate_biv (bl
, loop_start
, end
, 1,
4462 threshold
, insn_count
))
4465 /* ?? If we created a new test to bypass the loop entirely,
4466 or otherwise drop straight in, based on this test, then
4467 we might want to rewrite it also. This way some later
4468 pass has more hope of removing the initialization of this
4471 /* If final_value != 0, then the biv may be used after loop end
4472 and we must emit an insn to set it just in case.
4474 Reversed bivs already have an insn after the loop setting their
4475 value, so we don't need another one. We can't calculate the
4476 proper final value for such a biv here anyways. */
4477 if (final_value
!= 0 && ! bl
->reversed
)
4481 /* If the loop has multiple exits, emit the insn before the
4482 loop to ensure that it will always be executed no matter
4483 how the loop exits. Otherwise, emit the insn after the
4484 loop, since this is slightly more efficient. */
4485 if (loop_number_exit_count
[uid_loop_num
[INSN_UID (loop_start
)]])
4486 insert_before
= loop_start
;
4488 insert_before
= end_insert_before
;
4490 emit_insn_before (gen_move_insn (bl
->biv
->dest_reg
, final_value
),
4495 /* Delete all of the instructions inside the loop which set
4496 the biv, as they are all dead. If is safe to delete them,
4497 because an insn setting a biv will never be part of a libcall. */
4498 /* However, deleting them will invalidate the regno_last_uid info,
4499 so keeping them around is more convenient. Final_biv_value
4500 will only succeed when there are multiple exits if the biv
4501 is dead at each exit, hence it does not matter that the original
4502 insn remains, because it is dead anyways. */
4503 for (v
= bl
->biv
; v
; v
= v
->next_iv
)
4504 delete_insn (v
->insn
);
4507 if (loop_dump_stream
)
4508 fprintf (loop_dump_stream
, "Reg %d: biv eliminated\n",
4513 /* Go through all the instructions in the loop, making all the
4514 register substitutions scheduled in REG_MAP. */
4516 for (p
= loop_start
; p
!= end
; p
= NEXT_INSN (p
))
4517 if (GET_CODE (p
) == INSN
|| GET_CODE (p
) == JUMP_INSN
4518 || GET_CODE (p
) == CALL_INSN
)
4520 replace_regs (PATTERN (p
), reg_map
, max_reg_before_loop
, 0);
4521 replace_regs (REG_NOTES (p
), reg_map
, max_reg_before_loop
, 0);
4525 /* Unroll loops from within strength reduction so that we can use the
4526 induction variable information that strength_reduce has already
4530 unroll_loop (loop_end
, insn_count
, loop_start
, end_insert_before
,
4533 #ifdef HAVE_decrement_and_branch_on_count
4534 /* Instrument the loop with BCT insn. */
4535 if (HAVE_decrement_and_branch_on_count
&& bct_p
4536 && flag_branch_on_count_reg
)
4537 insert_bct (loop_start
, loop_end
, loop_info
);
4538 #endif /* HAVE_decrement_and_branch_on_count */
4540 if (loop_dump_stream
)
4541 fprintf (loop_dump_stream
, "\n");
4544 /* Return 1 if X is a valid source for an initial value (or as value being
4545 compared against in an initial test).
4547 X must be either a register or constant and must not be clobbered between
4548 the current insn and the start of the loop.
4550 INSN is the insn containing X. */
4553 valid_initial_value_p (x
, insn
, call_seen
, loop_start
)
4562 /* Only consider pseudos we know about initialized in insns whose luids
4564 if (GET_CODE (x
) != REG
4565 || REGNO (x
) >= max_reg_before_loop
)
4568 /* Don't use call-clobbered registers across a call which clobbers it. On
4569 some machines, don't use any hard registers at all. */
4570 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
4571 && (SMALL_REGISTER_CLASSES
4572 || (call_used_regs
[REGNO (x
)] && call_seen
)))
4575 /* Don't use registers that have been clobbered before the start of the
4577 if (reg_set_between_p (x
, insn
, loop_start
))
4583 /* Scan X for memory refs and check each memory address
4584 as a possible giv. INSN is the insn whose pattern X comes from.
4585 NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4586 every loop iteration. */
4589 find_mem_givs (x
, insn
, not_every_iteration
, loop_start
, loop_end
)
4592 int not_every_iteration
;
4593 rtx loop_start
, loop_end
;
4596 register enum rtx_code code
;
4602 code
= GET_CODE (x
);
4626 /* This code used to disable creating GIVs with mult_val == 1 and
4627 add_val == 0. However, this leads to lost optimizations when
4628 it comes time to combine a set of related DEST_ADDR GIVs, since
4629 this one would not be seen. */
4631 if (general_induction_var (XEXP (x
, 0), &src_reg
, &add_val
,
4632 &mult_val
, 1, &benefit
))
4634 /* Found one; record it. */
4636 = (struct induction
*) oballoc (sizeof (struct induction
));
4638 record_giv (v
, insn
, src_reg
, addr_placeholder
, mult_val
,
4639 add_val
, benefit
, DEST_ADDR
, not_every_iteration
,
4640 &XEXP (x
, 0), loop_start
, loop_end
);
4642 v
->mem_mode
= GET_MODE (x
);
4651 /* Recursively scan the subexpressions for other mem refs. */
4653 fmt
= GET_RTX_FORMAT (code
);
4654 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4656 find_mem_givs (XEXP (x
, i
), insn
, not_every_iteration
, loop_start
,
4658 else if (fmt
[i
] == 'E')
4659 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4660 find_mem_givs (XVECEXP (x
, i
, j
), insn
, not_every_iteration
,
4661 loop_start
, loop_end
);
4664 /* Fill in the data about one biv update.
4665 V is the `struct induction' in which we record the biv. (It is
4666 allocated by the caller, with alloca.)
4667 INSN is the insn that sets it.
4668 DEST_REG is the biv's reg.
4670 MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4671 INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4672 being set to INC_VAL.
4674 NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4675 executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4676 can be executed more than once per iteration. If MAYBE_MULTIPLE
4677 and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4678 executed exactly once per iteration. */
4681 record_biv (v
, insn
, dest_reg
, inc_val
, mult_val
,
4682 not_every_iteration
, maybe_multiple
)
4683 struct induction
*v
;
4688 int not_every_iteration
;
4691 struct iv_class
*bl
;
4694 v
->src_reg
= dest_reg
;
4695 v
->dest_reg
= dest_reg
;
4696 v
->mult_val
= mult_val
;
4697 v
->add_val
= inc_val
;
4698 v
->mode
= GET_MODE (dest_reg
);
4699 v
->always_computable
= ! not_every_iteration
;
4700 v
->always_executed
= ! not_every_iteration
;
4701 v
->maybe_multiple
= maybe_multiple
;
4703 /* Add this to the reg's iv_class, creating a class
4704 if this is the first incrementation of the reg. */
4706 bl
= reg_biv_class
[REGNO (dest_reg
)];
4709 /* Create and initialize new iv_class. */
4711 bl
= (struct iv_class
*) oballoc (sizeof (struct iv_class
));
4713 bl
->regno
= REGNO (dest_reg
);
4719 /* Set initial value to the reg itself. */
4720 bl
->initial_value
= dest_reg
;
4721 /* We haven't seen the initializing insn yet */
4724 bl
->initial_test
= 0;
4725 bl
->incremented
= 0;
4729 bl
->total_benefit
= 0;
4731 /* Add this class to loop_iv_list. */
4732 bl
->next
= loop_iv_list
;
4735 /* Put it in the array of biv register classes. */
4736 reg_biv_class
[REGNO (dest_reg
)] = bl
;
4739 /* Update IV_CLASS entry for this biv. */
4740 v
->next_iv
= bl
->biv
;
4743 if (mult_val
== const1_rtx
)
4744 bl
->incremented
= 1;
4746 if (loop_dump_stream
)
4748 fprintf (loop_dump_stream
,
4749 "Insn %d: possible biv, reg %d,",
4750 INSN_UID (insn
), REGNO (dest_reg
));
4751 if (GET_CODE (inc_val
) == CONST_INT
)
4753 fprintf (loop_dump_stream
, " const =");
4754 fprintf (loop_dump_stream
, HOST_WIDE_INT_PRINT_DEC
, INTVAL (inc_val
));
4755 fputc ('\n', loop_dump_stream
);
4759 fprintf (loop_dump_stream
, " const = ");
4760 print_rtl (loop_dump_stream
, inc_val
);
4761 fprintf (loop_dump_stream
, "\n");
4766 /* Fill in the data about one giv.
4767 V is the `struct induction' in which we record the giv. (It is
4768 allocated by the caller, with alloca.)
4769 INSN is the insn that sets it.
4770 BENEFIT estimates the savings from deleting this insn.
4771 TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4772 into a register or is used as a memory address.
4774 SRC_REG is the biv reg which the giv is computed from.
4775 DEST_REG is the giv's reg (if the giv is stored in a reg).
4776 MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4777 LOCATION points to the place where this giv's value appears in INSN. */
4780 record_giv (v
, insn
, src_reg
, dest_reg
, mult_val
, add_val
, benefit
,
4781 type
, not_every_iteration
, location
, loop_start
, loop_end
)
4782 struct induction
*v
;
4786 rtx mult_val
, add_val
;
4789 int not_every_iteration
;
4791 rtx loop_start
, loop_end
;
4793 struct induction
*b
;
4794 struct iv_class
*bl
;
4795 rtx set
= single_set (insn
);
4798 v
->src_reg
= src_reg
;
4800 v
->dest_reg
= dest_reg
;
4801 v
->mult_val
= mult_val
;
4802 v
->add_val
= add_val
;
4803 v
->benefit
= benefit
;
4804 v
->location
= location
;
4806 v
->combined_with
= 0;
4807 v
->maybe_multiple
= 0;
4809 v
->derive_adjustment
= 0;
4815 v
->auto_inc_opt
= 0;
4819 /* The v->always_computable field is used in update_giv_derive, to
4820 determine whether a giv can be used to derive another giv. For a
4821 DEST_REG giv, INSN computes a new value for the giv, so its value
4822 isn't computable if INSN insn't executed every iteration.
4823 However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4824 it does not compute a new value. Hence the value is always computable
4825 regardless of whether INSN is executed each iteration. */
4827 if (type
== DEST_ADDR
)
4828 v
->always_computable
= 1;
4830 v
->always_computable
= ! not_every_iteration
;
4832 v
->always_executed
= ! not_every_iteration
;
4834 if (type
== DEST_ADDR
)
4836 v
->mode
= GET_MODE (*location
);
4839 else /* type == DEST_REG */
4841 v
->mode
= GET_MODE (SET_DEST (set
));
4843 v
->lifetime
= (uid_luid
[REGNO_LAST_UID (REGNO (dest_reg
))]
4844 - uid_luid
[REGNO_FIRST_UID (REGNO (dest_reg
))]);
4846 /* If the lifetime is zero, it means that this register is
4847 really a dead store. So mark this as a giv that can be
4848 ignored. This will not prevent the biv from being eliminated. */
4849 if (v
->lifetime
== 0)
4852 reg_iv_type
[REGNO (dest_reg
)] = GENERAL_INDUCT
;
4853 reg_iv_info
[REGNO (dest_reg
)] = v
;
4856 /* Add the giv to the class of givs computed from one biv. */
4858 bl
= reg_biv_class
[REGNO (src_reg
)];
4861 v
->next_iv
= bl
->giv
;
4863 /* Don't count DEST_ADDR. This is supposed to count the number of
4864 insns that calculate givs. */
4865 if (type
== DEST_REG
)
4867 bl
->total_benefit
+= benefit
;
4870 /* Fatal error, biv missing for this giv? */
4873 if (type
== DEST_ADDR
)
4877 /* The giv can be replaced outright by the reduced register only if all
4878 of the following conditions are true:
4879 - the insn that sets the giv is always executed on any iteration
4880 on which the giv is used at all
4881 (there are two ways to deduce this:
4882 either the insn is executed on every iteration,
4883 or all uses follow that insn in the same basic block),
4884 - the giv is not used outside the loop
4885 - no assignments to the biv occur during the giv's lifetime. */
4887 if (REGNO_FIRST_UID (REGNO (dest_reg
)) == INSN_UID (insn
)
4888 /* Previous line always fails if INSN was moved by loop opt. */
4889 && uid_luid
[REGNO_LAST_UID (REGNO (dest_reg
))] < INSN_LUID (loop_end
)
4890 && (! not_every_iteration
4891 || last_use_this_basic_block (dest_reg
, insn
)))
4893 /* Now check that there are no assignments to the biv within the
4894 giv's lifetime. This requires two separate checks. */
4896 /* Check each biv update, and fail if any are between the first
4897 and last use of the giv.
4899 If this loop contains an inner loop that was unrolled, then
4900 the insn modifying the biv may have been emitted by the loop
4901 unrolling code, and hence does not have a valid luid. Just
4902 mark the biv as not replaceable in this case. It is not very
4903 useful as a biv, because it is used in two different loops.
4904 It is very unlikely that we would be able to optimize the giv
4905 using this biv anyways. */
4908 for (b
= bl
->biv
; b
; b
= b
->next_iv
)
4910 if (INSN_UID (b
->insn
) >= max_uid_for_loop
4911 || ((uid_luid
[INSN_UID (b
->insn
)]
4912 >= uid_luid
[REGNO_FIRST_UID (REGNO (dest_reg
))])
4913 && (uid_luid
[INSN_UID (b
->insn
)]
4914 <= uid_luid
[REGNO_LAST_UID (REGNO (dest_reg
))])))
4917 v
->not_replaceable
= 1;
4922 /* If there are any backwards branches that go from after the
4923 biv update to before it, then this giv is not replaceable. */
4925 for (b
= bl
->biv
; b
; b
= b
->next_iv
)
4926 if (back_branch_in_range_p (b
->insn
, loop_start
, loop_end
))
4929 v
->not_replaceable
= 1;
4935 /* May still be replaceable, we don't have enough info here to
4938 v
->not_replaceable
= 0;
4942 /* Record whether the add_val contains a const_int, for later use by
4947 v
->no_const_addval
= 1;
4948 if (tem
== const0_rtx
)
4950 else if (GET_CODE (tem
) == CONST_INT
)
4951 v
->no_const_addval
= 0;
4952 else if (GET_CODE (tem
) == PLUS
)
4956 if (GET_CODE (XEXP (tem
, 0)) == PLUS
)
4957 tem
= XEXP (tem
, 0);
4958 else if (GET_CODE (XEXP (tem
, 1)) == PLUS
)
4959 tem
= XEXP (tem
, 1);
4963 if (GET_CODE (XEXP (tem
, 1)) == CONST_INT
)
4964 v
->no_const_addval
= 0;
4968 if (loop_dump_stream
)
4970 if (type
== DEST_REG
)
4971 fprintf (loop_dump_stream
, "Insn %d: giv reg %d",
4972 INSN_UID (insn
), REGNO (dest_reg
));
4974 fprintf (loop_dump_stream
, "Insn %d: dest address",
4977 fprintf (loop_dump_stream
, " src reg %d benefit %d",
4978 REGNO (src_reg
), v
->benefit
);
4979 fprintf (loop_dump_stream
, " lifetime %d",
4983 fprintf (loop_dump_stream
, " replaceable");
4985 if (v
->no_const_addval
)
4986 fprintf (loop_dump_stream
, " ncav");
4988 if (GET_CODE (mult_val
) == CONST_INT
)
4990 fprintf (loop_dump_stream
, " mult ");
4991 fprintf (loop_dump_stream
, HOST_WIDE_INT_PRINT_DEC
, INTVAL (mult_val
));
4995 fprintf (loop_dump_stream
, " mult ");
4996 print_rtl (loop_dump_stream
, mult_val
);
4999 if (GET_CODE (add_val
) == CONST_INT
)
5001 fprintf (loop_dump_stream
, " add ");
5002 fprintf (loop_dump_stream
, HOST_WIDE_INT_PRINT_DEC
, INTVAL (add_val
));
5006 fprintf (loop_dump_stream
, " add ");
5007 print_rtl (loop_dump_stream
, add_val
);
5011 if (loop_dump_stream
)
5012 fprintf (loop_dump_stream
, "\n");
5017 /* All this does is determine whether a giv can be made replaceable because
5018 its final value can be calculated. This code can not be part of record_giv
5019 above, because final_giv_value requires that the number of loop iterations
5020 be known, and that can not be accurately calculated until after all givs
5021 have been identified. */
5024 check_final_value (v
, loop_start
, loop_end
, n_iterations
)
5025 struct induction
*v
;
5026 rtx loop_start
, loop_end
;
5027 unsigned HOST_WIDE_INT n_iterations
;
5029 struct iv_class
*bl
;
5030 rtx final_value
= 0;
5032 bl
= reg_biv_class
[REGNO (v
->src_reg
)];
5034 /* DEST_ADDR givs will never reach here, because they are always marked
5035 replaceable above in record_giv. */
5037 /* The giv can be replaced outright by the reduced register only if all
5038 of the following conditions are true:
5039 - the insn that sets the giv is always executed on any iteration
5040 on which the giv is used at all
5041 (there are two ways to deduce this:
5042 either the insn is executed on every iteration,
5043 or all uses follow that insn in the same basic block),
5044 - its final value can be calculated (this condition is different
5045 than the one above in record_giv)
5046 - no assignments to the biv occur during the giv's lifetime. */
5049 /* This is only called now when replaceable is known to be false. */
5050 /* Clear replaceable, so that it won't confuse final_giv_value. */
5054 if ((final_value
= final_giv_value (v
, loop_start
, loop_end
, n_iterations
))
5055 && (v
->always_computable
|| last_use_this_basic_block (v
->dest_reg
, v
->insn
)))
5057 int biv_increment_seen
= 0;
5063 /* When trying to determine whether or not a biv increment occurs
5064 during the lifetime of the giv, we can ignore uses of the variable
5065 outside the loop because final_value is true. Hence we can not
5066 use regno_last_uid and regno_first_uid as above in record_giv. */
5068 /* Search the loop to determine whether any assignments to the
5069 biv occur during the giv's lifetime. Start with the insn
5070 that sets the giv, and search around the loop until we come
5071 back to that insn again.
5073 Also fail if there is a jump within the giv's lifetime that jumps
5074 to somewhere outside the lifetime but still within the loop. This
5075 catches spaghetti code where the execution order is not linear, and
5076 hence the above test fails. Here we assume that the giv lifetime
5077 does not extend from one iteration of the loop to the next, so as
5078 to make the test easier. Since the lifetime isn't known yet,
5079 this requires two loops. See also record_giv above. */
5081 last_giv_use
= v
->insn
;
5087 p
= NEXT_INSN (loop_start
);
5091 if (GET_CODE (p
) == INSN
|| GET_CODE (p
) == JUMP_INSN
5092 || GET_CODE (p
) == CALL_INSN
)
5094 if (biv_increment_seen
)
5096 if (reg_mentioned_p (v
->dest_reg
, PATTERN (p
)))
5099 v
->not_replaceable
= 1;
5103 else if (reg_set_p (v
->src_reg
, PATTERN (p
)))
5104 biv_increment_seen
= 1;
5105 else if (reg_mentioned_p (v
->dest_reg
, PATTERN (p
)))
5110 /* Now that the lifetime of the giv is known, check for branches
5111 from within the lifetime to outside the lifetime if it is still
5121 p
= NEXT_INSN (loop_start
);
5122 if (p
== last_giv_use
)
5125 if (GET_CODE (p
) == JUMP_INSN
&& JUMP_LABEL (p
)
5126 && LABEL_NAME (JUMP_LABEL (p
))
5127 && ((INSN_UID (JUMP_LABEL (p
)) >= max_uid_for_loop
)
5128 || (INSN_UID (v
->insn
) >= max_uid_for_loop
)
5129 || (INSN_UID (last_giv_use
) >= max_uid_for_loop
)
5130 || (INSN_LUID (JUMP_LABEL (p
)) < INSN_LUID (v
->insn
)
5131 && INSN_LUID (JUMP_LABEL (p
)) > INSN_LUID (loop_start
))
5132 || (INSN_LUID (JUMP_LABEL (p
)) > INSN_LUID (last_giv_use
)
5133 && INSN_LUID (JUMP_LABEL (p
)) < INSN_LUID (loop_end
))))
5136 v
->not_replaceable
= 1;
5138 if (loop_dump_stream
)
5139 fprintf (loop_dump_stream
,
5140 "Found branch outside giv lifetime.\n");
5147 /* If it is replaceable, then save the final value. */
5149 v
->final_value
= final_value
;
5152 if (loop_dump_stream
&& v
->replaceable
)
5153 fprintf (loop_dump_stream
, "Insn %d: giv reg %d final_value replaceable\n",
5154 INSN_UID (v
->insn
), REGNO (v
->dest_reg
));
5157 /* Update the status of whether a giv can derive other givs.
5159 We need to do something special if there is or may be an update to the biv
5160 between the time the giv is defined and the time it is used to derive
5163 In addition, a giv that is only conditionally set is not allowed to
5164 derive another giv once a label has been passed.
5166 The cases we look at are when a label or an update to a biv is passed. */
5169 update_giv_derive (p
)
5172 struct iv_class
*bl
;
5173 struct induction
*biv
, *giv
;
5177 /* Search all IV classes, then all bivs, and finally all givs.
5179 There are three cases we are concerned with. First we have the situation
5180 of a giv that is only updated conditionally. In that case, it may not
5181 derive any givs after a label is passed.
5183 The second case is when a biv update occurs, or may occur, after the
5184 definition of a giv. For certain biv updates (see below) that are
5185 known to occur between the giv definition and use, we can adjust the
5186 giv definition. For others, or when the biv update is conditional,
5187 we must prevent the giv from deriving any other givs. There are two
5188 sub-cases within this case.
5190 If this is a label, we are concerned with any biv update that is done
5191 conditionally, since it may be done after the giv is defined followed by
5192 a branch here (actually, we need to pass both a jump and a label, but
5193 this extra tracking doesn't seem worth it).
5195 If this is a jump, we are concerned about any biv update that may be
5196 executed multiple times. We are actually only concerned about
5197 backward jumps, but it is probably not worth performing the test
5198 on the jump again here.
5200 If this is a biv update, we must adjust the giv status to show that a
5201 subsequent biv update was performed. If this adjustment cannot be done,
5202 the giv cannot derive further givs. */
5204 for (bl
= loop_iv_list
; bl
; bl
= bl
->next
)
5205 for (biv
= bl
->biv
; biv
; biv
= biv
->next_iv
)
5206 if (GET_CODE (p
) == CODE_LABEL
|| GET_CODE (p
) == JUMP_INSN
5209 for (giv
= bl
->giv
; giv
; giv
= giv
->next_iv
)
5211 /* If cant_derive is already true, there is no point in
5212 checking all of these conditions again. */
5213 if (giv
->cant_derive
)
5216 /* If this giv is conditionally set and we have passed a label,
5217 it cannot derive anything. */
5218 if (GET_CODE (p
) == CODE_LABEL
&& ! giv
->always_computable
)
5219 giv
->cant_derive
= 1;
5221 /* Skip givs that have mult_val == 0, since
5222 they are really invariants. Also skip those that are
5223 replaceable, since we know their lifetime doesn't contain
5225 else if (giv
->mult_val
== const0_rtx
|| giv
->replaceable
)
5228 /* The only way we can allow this giv to derive another
5229 is if this is a biv increment and we can form the product
5230 of biv->add_val and giv->mult_val. In this case, we will
5231 be able to compute a compensation. */
5232 else if (biv
->insn
== p
)
5236 if (biv
->mult_val
== const1_rtx
)
5237 tem
= simplify_giv_expr (gen_rtx_MULT (giv
->mode
,
5242 if (tem
&& giv
->derive_adjustment
)
5243 tem
= simplify_giv_expr (gen_rtx_PLUS (giv
->mode
, tem
,
5244 giv
->derive_adjustment
),
5247 giv
->derive_adjustment
= tem
;
5249 giv
->cant_derive
= 1;
5251 else if ((GET_CODE (p
) == CODE_LABEL
&& ! biv
->always_computable
)
5252 || (GET_CODE (p
) == JUMP_INSN
&& biv
->maybe_multiple
))
5253 giv
->cant_derive
= 1;
5258 /* Check whether an insn is an increment legitimate for a basic induction var.
5259 X is the source of insn P, or a part of it.
5260 MODE is the mode in which X should be interpreted.
5262 DEST_REG is the putative biv, also the destination of the insn.
5263 We accept patterns of these forms:
5264 REG = REG + INVARIANT (includes REG = REG - CONSTANT)
5265 REG = INVARIANT + REG
5267 If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
5268 and store the additive term into *INC_VAL.
5270 If X is an assignment of an invariant into DEST_REG, we set
5271 *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
5273 We also want to detect a BIV when it corresponds to a variable
5274 whose mode was promoted via PROMOTED_MODE. In that case, an increment
5275 of the variable may be a PLUS that adds a SUBREG of that variable to
5276 an invariant and then sign- or zero-extends the result of the PLUS
5279 Most GIVs in such cases will be in the promoted mode, since that is the
5280 probably the natural computation mode (and almost certainly the mode
5281 used for addresses) on the machine. So we view the pseudo-reg containing
5282 the variable as the BIV, as if it were simply incremented.
5284 Note that treating the entire pseudo as a BIV will result in making
5285 simple increments to any GIVs based on it. However, if the variable
5286 overflows in its declared mode but not its promoted mode, the result will
5287 be incorrect. This is acceptable if the variable is signed, since
5288 overflows in such cases are undefined, but not if it is unsigned, since
5289 those overflows are defined. So we only check for SIGN_EXTEND and
5292 If we cannot find a biv, we return 0. */
5295 basic_induction_var (x
, mode
, dest_reg
, p
, inc_val
, mult_val
)
5297 enum machine_mode mode
;
5303 register enum rtx_code code
;
5307 code
= GET_CODE (x
);
5311 if (rtx_equal_p (XEXP (x
, 0), dest_reg
)
5312 || (GET_CODE (XEXP (x
, 0)) == SUBREG
5313 && SUBREG_PROMOTED_VAR_P (XEXP (x
, 0))
5314 && SUBREG_REG (XEXP (x
, 0)) == dest_reg
))
5316 else if (rtx_equal_p (XEXP (x
, 1), dest_reg
)
5317 || (GET_CODE (XEXP (x
, 1)) == SUBREG
5318 && SUBREG_PROMOTED_VAR_P (XEXP (x
, 1))
5319 && SUBREG_REG (XEXP (x
, 1)) == dest_reg
))
5324 if (invariant_p (arg
) != 1)
5327 *inc_val
= convert_modes (GET_MODE (dest_reg
), GET_MODE (x
), arg
, 0);
5328 *mult_val
= const1_rtx
;
5332 /* If this is a SUBREG for a promoted variable, check the inner
5334 if (SUBREG_PROMOTED_VAR_P (x
))
5335 return basic_induction_var (SUBREG_REG (x
), GET_MODE (SUBREG_REG (x
)),
5336 dest_reg
, p
, inc_val
, mult_val
);
5340 /* If this register is assigned in a previous insn, look at its
5341 source, but don't go outside the loop or past a label. */
5347 insn
= PREV_INSN (insn
);
5348 } while (insn
&& GET_CODE (insn
) == NOTE
5349 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
);
5353 set
= single_set (insn
);
5357 if ((SET_DEST (set
) == x
5358 || (GET_CODE (SET_DEST (set
)) == SUBREG
5359 && (GET_MODE_SIZE (GET_MODE (SET_DEST (set
)))
5361 && SUBREG_REG (SET_DEST (set
)) == x
))
5362 && basic_induction_var (SET_SRC (set
),
5363 (GET_MODE (SET_SRC (set
)) == VOIDmode
5365 : GET_MODE (SET_SRC (set
))),
5370 /* ... fall through ... */
5372 /* Can accept constant setting of biv only when inside inner most loop.
5373 Otherwise, a biv of an inner loop may be incorrectly recognized
5374 as a biv of the outer loop,
5375 causing code to be moved INTO the inner loop. */
5377 if (invariant_p (x
) != 1)
5382 /* convert_modes aborts if we try to convert to or from CCmode, so just
5383 exclude that case. It is very unlikely that a condition code value
5384 would be a useful iterator anyways. */
5385 if (loops_enclosed
== 1
5386 && GET_MODE_CLASS (mode
) != MODE_CC
5387 && GET_MODE_CLASS (GET_MODE (dest_reg
)) != MODE_CC
)
5389 /* Possible bug here? Perhaps we don't know the mode of X. */
5390 *inc_val
= convert_modes (GET_MODE (dest_reg
), mode
, x
, 0);
5391 *mult_val
= const0_rtx
;
5398 return basic_induction_var (XEXP (x
, 0), GET_MODE (XEXP (x
, 0)),
5399 dest_reg
, p
, inc_val
, mult_val
);
5402 /* Similar, since this can be a sign extension. */
5403 for (insn
= PREV_INSN (p
);
5404 (insn
&& GET_CODE (insn
) == NOTE
5405 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
);
5406 insn
= PREV_INSN (insn
))
5410 set
= single_set (insn
);
5412 if (set
&& SET_DEST (set
) == XEXP (x
, 0)
5413 && GET_CODE (XEXP (x
, 1)) == CONST_INT
5414 && INTVAL (XEXP (x
, 1)) >= 0
5415 && GET_CODE (SET_SRC (set
)) == ASHIFT
5416 && XEXP (x
, 1) == XEXP (SET_SRC (set
), 1))
5417 return basic_induction_var (XEXP (SET_SRC (set
), 0),
5418 GET_MODE (XEXP (x
, 0)),
5419 dest_reg
, insn
, inc_val
, mult_val
);
5427 /* A general induction variable (giv) is any quantity that is a linear
5428 function of a basic induction variable,
5429 i.e. giv = biv * mult_val + add_val.
5430 The coefficients can be any loop invariant quantity.
5431 A giv need not be computed directly from the biv;
5432 it can be computed by way of other givs. */
5434 /* Determine whether X computes a giv.
5435 If it does, return a nonzero value
5436 which is the benefit from eliminating the computation of X;
5437 set *SRC_REG to the register of the biv that it is computed from;
5438 set *ADD_VAL and *MULT_VAL to the coefficients,
5439 such that the value of X is biv * mult + add; */
5442 general_induction_var (x
, src_reg
, add_val
, mult_val
, is_addr
, pbenefit
)
5453 /* If this is an invariant, forget it, it isn't a giv. */
5454 if (invariant_p (x
) == 1)
5457 /* See if the expression could be a giv and get its form.
5458 Mark our place on the obstack in case we don't find a giv. */
5459 storage
= (char *) oballoc (0);
5461 x
= simplify_giv_expr (x
, pbenefit
);
5468 switch (GET_CODE (x
))
5472 /* Since this is now an invariant and wasn't before, it must be a giv
5473 with MULT_VAL == 0. It doesn't matter which BIV we associate this
5475 *src_reg
= loop_iv_list
->biv
->dest_reg
;
5476 *mult_val
= const0_rtx
;
5481 /* This is equivalent to a BIV. */
5483 *mult_val
= const1_rtx
;
5484 *add_val
= const0_rtx
;
5488 /* Either (plus (biv) (invar)) or
5489 (plus (mult (biv) (invar_1)) (invar_2)). */
5490 if (GET_CODE (XEXP (x
, 0)) == MULT
)
5492 *src_reg
= XEXP (XEXP (x
, 0), 0);
5493 *mult_val
= XEXP (XEXP (x
, 0), 1);
5497 *src_reg
= XEXP (x
, 0);
5498 *mult_val
= const1_rtx
;
5500 *add_val
= XEXP (x
, 1);
5504 /* ADD_VAL is zero. */
5505 *src_reg
= XEXP (x
, 0);
5506 *mult_val
= XEXP (x
, 1);
5507 *add_val
= const0_rtx
;
5514 /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
5515 unless they are CONST_INT). */
5516 if (GET_CODE (*add_val
) == USE
)
5517 *add_val
= XEXP (*add_val
, 0);
5518 if (GET_CODE (*mult_val
) == USE
)
5519 *mult_val
= XEXP (*mult_val
, 0);
5524 *pbenefit
+= ADDRESS_COST (orig_x
) - reg_address_cost
;
5526 *pbenefit
+= rtx_cost (orig_x
, MEM
) - reg_address_cost
;
5530 *pbenefit
+= rtx_cost (orig_x
, SET
);
5532 /* Always return true if this is a giv so it will be detected as such,
5533 even if the benefit is zero or negative. This allows elimination
5534 of bivs that might otherwise not be eliminated. */
5538 /* Given an expression, X, try to form it as a linear function of a biv.
5539 We will canonicalize it to be of the form
5540 (plus (mult (BIV) (invar_1))
5542 with possible degeneracies.
5544 The invariant expressions must each be of a form that can be used as a
5545 machine operand. We surround then with a USE rtx (a hack, but localized
5546 and certainly unambiguous!) if not a CONST_INT for simplicity in this
5547 routine; it is the caller's responsibility to strip them.
5549 If no such canonicalization is possible (i.e., two biv's are used or an
5550 expression that is neither invariant nor a biv or giv), this routine
5553 For a non-zero return, the result will have a code of CONST_INT, USE,
5554 REG (for a BIV), PLUS, or MULT. No other codes will occur.
5556 *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
5558 static rtx sge_plus
PROTO ((enum machine_mode
, rtx
, rtx
));
5559 static rtx sge_plus_constant
PROTO ((rtx
, rtx
));
5562 simplify_giv_expr (x
, benefit
)
5566 enum machine_mode mode
= GET_MODE (x
);
5570 /* If this is not an integer mode, or if we cannot do arithmetic in this
5571 mode, this can't be a giv. */
5572 if (mode
!= VOIDmode
5573 && (GET_MODE_CLASS (mode
) != MODE_INT
5574 || GET_MODE_BITSIZE (mode
) > HOST_BITS_PER_WIDE_INT
))
5577 switch (GET_CODE (x
))
5580 arg0
= simplify_giv_expr (XEXP (x
, 0), benefit
);
5581 arg1
= simplify_giv_expr (XEXP (x
, 1), benefit
);
5582 if (arg0
== 0 || arg1
== 0)
5585 /* Put constant last, CONST_INT last if both constant. */
5586 if ((GET_CODE (arg0
) == USE
5587 || GET_CODE (arg0
) == CONST_INT
)
5588 && ! ((GET_CODE (arg0
) == USE
5589 && GET_CODE (arg1
) == USE
)
5590 || GET_CODE (arg1
) == CONST_INT
))
5591 tem
= arg0
, arg0
= arg1
, arg1
= tem
;
5593 /* Handle addition of zero, then addition of an invariant. */
5594 if (arg1
== const0_rtx
)
5596 else if (GET_CODE (arg1
) == CONST_INT
|| GET_CODE (arg1
) == USE
)
5597 switch (GET_CODE (arg0
))
5601 /* Adding two invariants must result in an invariant, so enclose
5602 addition operation inside a USE and return it. */
5603 if (GET_CODE (arg0
) == USE
)
5604 arg0
= XEXP (arg0
, 0);
5605 if (GET_CODE (arg1
) == USE
)
5606 arg1
= XEXP (arg1
, 0);
5608 if (GET_CODE (arg0
) == CONST_INT
)
5609 tem
= arg0
, arg0
= arg1
, arg1
= tem
;
5610 if (GET_CODE (arg1
) == CONST_INT
)
5611 tem
= sge_plus_constant (arg0
, arg1
);
5613 tem
= sge_plus (mode
, arg0
, arg1
);
5615 if (GET_CODE (tem
) != CONST_INT
)
5616 tem
= gen_rtx_USE (mode
, tem
);
5621 /* biv + invar or mult + invar. Return sum. */
5622 return gen_rtx_PLUS (mode
, arg0
, arg1
);
5625 /* (a + invar_1) + invar_2. Associate. */
5626 return simplify_giv_expr (
5627 gen_rtx_PLUS (mode
, XEXP (arg0
, 0),
5628 gen_rtx_PLUS (mode
, XEXP (arg0
, 1), arg1
)),
5635 /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5636 MULT to reduce cases. */
5637 if (GET_CODE (arg0
) == REG
)
5638 arg0
= gen_rtx_MULT (mode
, arg0
, const1_rtx
);
5639 if (GET_CODE (arg1
) == REG
)
5640 arg1
= gen_rtx_MULT (mode
, arg1
, const1_rtx
);
5642 /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5643 Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5644 Recurse to associate the second PLUS. */
5645 if (GET_CODE (arg1
) == MULT
)
5646 tem
= arg0
, arg0
= arg1
, arg1
= tem
;
5648 if (GET_CODE (arg1
) == PLUS
)
5649 return simplify_giv_expr (gen_rtx_PLUS (mode
,
5650 gen_rtx_PLUS (mode
, arg0
,
5655 /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5656 if (GET_CODE (arg0
) != MULT
|| GET_CODE (arg1
) != MULT
)
5659 if (!rtx_equal_p (arg0
, arg1
))
5662 return simplify_giv_expr (gen_rtx_MULT (mode
,
5670 /* Handle "a - b" as "a + b * (-1)". */
5671 return simplify_giv_expr (gen_rtx_PLUS (mode
,
5673 gen_rtx_MULT (mode
, XEXP (x
, 1),
5678 arg0
= simplify_giv_expr (XEXP (x
, 0), benefit
);
5679 arg1
= simplify_giv_expr (XEXP (x
, 1), benefit
);
5680 if (arg0
== 0 || arg1
== 0)
5683 /* Put constant last, CONST_INT last if both constant. */
5684 if ((GET_CODE (arg0
) == USE
|| GET_CODE (arg0
) == CONST_INT
)
5685 && GET_CODE (arg1
) != CONST_INT
)
5686 tem
= arg0
, arg0
= arg1
, arg1
= tem
;
5688 /* If second argument is not now constant, not giv. */
5689 if (GET_CODE (arg1
) != USE
&& GET_CODE (arg1
) != CONST_INT
)
5692 /* Handle multiply by 0 or 1. */
5693 if (arg1
== const0_rtx
)
5696 else if (arg1
== const1_rtx
)
5699 switch (GET_CODE (arg0
))
5702 /* biv * invar. Done. */
5703 return gen_rtx_MULT (mode
, arg0
, arg1
);
5706 /* Product of two constants. */
5707 return GEN_INT (INTVAL (arg0
) * INTVAL (arg1
));
5710 /* invar * invar. It is a giv, but very few of these will
5711 actually pay off, so limit to simple registers. */
5712 if (GET_CODE (arg1
) != CONST_INT
)
5715 arg0
= XEXP (arg0
, 0);
5716 if (GET_CODE (arg0
) == REG
)
5717 tem
= gen_rtx_MULT (mode
, arg0
, arg1
);
5718 else if (GET_CODE (arg0
) == MULT
5719 && GET_CODE (XEXP (arg0
, 0)) == REG
5720 && GET_CODE (XEXP (arg0
, 1)) == CONST_INT
)
5722 tem
= gen_rtx_MULT (mode
, XEXP (arg0
, 0),
5723 GEN_INT (INTVAL (XEXP (arg0
, 1))
5728 return gen_rtx_USE (mode
, tem
);
5731 /* (a * invar_1) * invar_2. Associate. */
5732 return simplify_giv_expr (gen_rtx_MULT (mode
, XEXP (arg0
, 0),
5739 /* (a + invar_1) * invar_2. Distribute. */
5740 return simplify_giv_expr (gen_rtx_PLUS (mode
,
5754 /* Shift by constant is multiply by power of two. */
5755 if (GET_CODE (XEXP (x
, 1)) != CONST_INT
)
5758 return simplify_giv_expr (gen_rtx_MULT (mode
,
5760 GEN_INT ((HOST_WIDE_INT
) 1
5761 << INTVAL (XEXP (x
, 1)))),
5765 /* "-a" is "a * (-1)" */
5766 return simplify_giv_expr (gen_rtx_MULT (mode
, XEXP (x
, 0), constm1_rtx
),
5770 /* "~a" is "-a - 1". Silly, but easy. */
5771 return simplify_giv_expr (gen_rtx_MINUS (mode
,
5772 gen_rtx_NEG (mode
, XEXP (x
, 0)),
5777 /* Already in proper form for invariant. */
5781 /* If this is a new register, we can't deal with it. */
5782 if (REGNO (x
) >= max_reg_before_loop
)
5785 /* Check for biv or giv. */
5786 switch (reg_iv_type
[REGNO (x
)])
5790 case GENERAL_INDUCT
:
5792 struct induction
*v
= reg_iv_info
[REGNO (x
)];
5794 /* Form expression from giv and add benefit. Ensure this giv
5795 can derive another and subtract any needed adjustment if so. */
5796 *benefit
+= v
->benefit
;
5800 tem
= gen_rtx_PLUS (mode
, gen_rtx_MULT (mode
, v
->src_reg
,
5803 if (v
->derive_adjustment
)
5804 tem
= gen_rtx_MINUS (mode
, tem
, v
->derive_adjustment
);
5805 return simplify_giv_expr (tem
, benefit
);
5809 /* If it isn't an induction variable, and it is invariant, we
5810 may be able to simplify things further by looking through
5811 the bits we just moved outside the loop. */
5812 if (invariant_p (x
) == 1)
5816 for (m
= the_movables
; m
; m
= m
->next
)
5817 if (rtx_equal_p (x
, m
->set_dest
))
5819 /* Ok, we found a match. Substitute and simplify. */
5821 /* If we match another movable, we must use that, as
5822 this one is going away. */
5824 return simplify_giv_expr (m
->match
->set_dest
, benefit
);
5826 /* If consec is non-zero, this is a member of a group of
5827 instructions that were moved together. We handle this
5828 case only to the point of seeking to the last insn and
5829 looking for a REG_EQUAL. Fail if we don't find one. */
5834 do { tem
= NEXT_INSN (tem
); } while (--i
> 0);
5836 tem
= find_reg_note (tem
, REG_EQUAL
, NULL_RTX
);
5838 tem
= XEXP (tem
, 0);
5842 tem
= single_set (m
->insn
);
5844 tem
= SET_SRC (tem
);
5849 /* What we are most interested in is pointer
5850 arithmetic on invariants -- only take
5851 patterns we may be able to do something with. */
5852 if (GET_CODE (tem
) == PLUS
5853 || GET_CODE (tem
) == MULT
5854 || GET_CODE (tem
) == ASHIFT
5855 || GET_CODE (tem
) == CONST_INT
5856 || GET_CODE (tem
) == SYMBOL_REF
)
5858 tem
= simplify_giv_expr (tem
, benefit
);
5862 else if (GET_CODE (tem
) == CONST
5863 && GET_CODE (XEXP (tem
, 0)) == PLUS
5864 && GET_CODE (XEXP (XEXP (tem
, 0), 0)) == SYMBOL_REF
5865 && GET_CODE (XEXP (XEXP (tem
, 0), 1)) == CONST_INT
)
5867 tem
= simplify_giv_expr (XEXP (tem
, 0), benefit
);
5878 /* Fall through to general case. */
5880 /* If invariant, return as USE (unless CONST_INT).
5881 Otherwise, not giv. */
5882 if (GET_CODE (x
) == USE
)
5885 if (invariant_p (x
) == 1)
5887 if (GET_CODE (x
) == CONST_INT
)
5889 if (GET_CODE (x
) == CONST
5890 && GET_CODE (XEXP (x
, 0)) == PLUS
5891 && GET_CODE (XEXP (XEXP (x
, 0), 0)) == SYMBOL_REF
5892 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
)
5894 return gen_rtx_USE (mode
, x
);
5901 /* This routine folds invariants such that there is only ever one
5902 CONST_INT in the summation. It is only used by simplify_giv_expr. */
5905 sge_plus_constant (x
, c
)
5908 if (GET_CODE (x
) == CONST_INT
)
5909 return GEN_INT (INTVAL (x
) + INTVAL (c
));
5910 else if (GET_CODE (x
) != PLUS
)
5911 return gen_rtx_PLUS (GET_MODE (x
), x
, c
);
5912 else if (GET_CODE (XEXP (x
, 1)) == CONST_INT
)
5914 return gen_rtx_PLUS (GET_MODE (x
), XEXP (x
, 0),
5915 GEN_INT (INTVAL (XEXP (x
, 1)) + INTVAL (c
)));
5917 else if (GET_CODE (XEXP (x
, 0)) == PLUS
5918 || GET_CODE (XEXP (x
, 1)) != PLUS
)
5920 return gen_rtx_PLUS (GET_MODE (x
),
5921 sge_plus_constant (XEXP (x
, 0), c
), XEXP (x
, 1));
5925 return gen_rtx_PLUS (GET_MODE (x
),
5926 sge_plus_constant (XEXP (x
, 1), c
), XEXP (x
, 0));
5931 sge_plus (mode
, x
, y
)
5932 enum machine_mode mode
;
5935 while (GET_CODE (y
) == PLUS
)
5937 rtx a
= XEXP (y
, 0);
5938 if (GET_CODE (a
) == CONST_INT
)
5939 x
= sge_plus_constant (x
, a
);
5941 x
= gen_rtx_PLUS (mode
, x
, a
);
5944 if (GET_CODE (y
) == CONST_INT
)
5945 x
= sge_plus_constant (x
, y
);
5947 x
= gen_rtx_PLUS (mode
, x
, y
);
5951 /* Help detect a giv that is calculated by several consecutive insns;
5955 The caller has already identified the first insn P as having a giv as dest;
5956 we check that all other insns that set the same register follow
5957 immediately after P, that they alter nothing else,
5958 and that the result of the last is still a giv.
5960 The value is 0 if the reg set in P is not really a giv.
5961 Otherwise, the value is the amount gained by eliminating
5962 all the consecutive insns that compute the value.
5964 FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
5965 SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
5967 The coefficients of the ultimate giv value are stored in
5968 *MULT_VAL and *ADD_VAL. */
5971 consec_sets_giv (first_benefit
, p
, src_reg
, dest_reg
,
5972 add_val
, mult_val
, last_consec_insn
)
5979 rtx
*last_consec_insn
;
5987 /* Indicate that this is a giv so that we can update the value produced in
5988 each insn of the multi-insn sequence.
5990 This induction structure will be used only by the call to
5991 general_induction_var below, so we can allocate it on our stack.
5992 If this is a giv, our caller will replace the induct var entry with
5993 a new induction structure. */
5995 = (struct induction
*) alloca (sizeof (struct induction
));
5996 v
->src_reg
= src_reg
;
5997 v
->mult_val
= *mult_val
;
5998 v
->add_val
= *add_val
;
5999 v
->benefit
= first_benefit
;
6001 v
->derive_adjustment
= 0;
6003 reg_iv_type
[REGNO (dest_reg
)] = GENERAL_INDUCT
;
6004 reg_iv_info
[REGNO (dest_reg
)] = v
;
6006 count
= VARRAY_INT (n_times_set
, REGNO (dest_reg
)) - 1;
6011 code
= GET_CODE (p
);
6013 /* If libcall, skip to end of call sequence. */
6014 if (code
== INSN
&& (temp
= find_reg_note (p
, REG_LIBCALL
, NULL_RTX
)))
6018 && (set
= single_set (p
))
6019 && GET_CODE (SET_DEST (set
)) == REG
6020 && SET_DEST (set
) == dest_reg
6021 && (general_induction_var (SET_SRC (set
), &src_reg
,
6022 add_val
, mult_val
, 0, &benefit
)
6023 /* Giv created by equivalent expression. */
6024 || ((temp
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
))
6025 && general_induction_var (XEXP (temp
, 0), &src_reg
,
6026 add_val
, mult_val
, 0, &benefit
)))
6027 && src_reg
== v
->src_reg
)
6029 if (find_reg_note (p
, REG_RETVAL
, NULL_RTX
))
6030 benefit
+= libcall_benefit (p
);
6033 v
->mult_val
= *mult_val
;
6034 v
->add_val
= *add_val
;
6035 v
->benefit
= benefit
;
6037 else if (code
!= NOTE
)
6039 /* Allow insns that set something other than this giv to a
6040 constant. Such insns are needed on machines which cannot
6041 include long constants and should not disqualify a giv. */
6043 && (set
= single_set (p
))
6044 && SET_DEST (set
) != dest_reg
6045 && CONSTANT_P (SET_SRC (set
)))
6048 reg_iv_type
[REGNO (dest_reg
)] = UNKNOWN_INDUCT
;
6053 *last_consec_insn
= p
;
6057 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6058 represented by G1. If no such expression can be found, or it is clear that
6059 it cannot possibly be a valid address, 0 is returned.
6061 To perform the computation, we note that
6064 where `v' is the biv.
6066 So G2 = (y/b) * G1 + (b - a*y/x).
6068 Note that MULT = y/x.
6070 Update: A and B are now allowed to be additive expressions such that
6071 B contains all variables in A. That is, computing B-A will not require
6072 subtracting variables. */
6075 express_from_1 (a
, b
, mult
)
6078 /* If MULT is zero, then A*MULT is zero, and our expression is B. */
6080 if (mult
== const0_rtx
)
6083 /* If MULT is not 1, we cannot handle A with non-constants, since we
6084 would then be required to subtract multiples of the registers in A.
6085 This is theoretically possible, and may even apply to some Fortran
6086 constructs, but it is a lot of work and we do not attempt it here. */
6088 if (mult
!= const1_rtx
&& GET_CODE (a
) != CONST_INT
)
6091 /* In general these structures are sorted top to bottom (down the PLUS
6092 chain), but not left to right across the PLUS. If B is a higher
6093 order giv than A, we can strip one level and recurse. If A is higher
6094 order, we'll eventually bail out, but won't know that until the end.
6095 If they are the same, we'll strip one level around this loop. */
6097 while (GET_CODE (a
) == PLUS
&& GET_CODE (b
) == PLUS
)
6099 rtx ra
, rb
, oa
, ob
, tmp
;
6101 ra
= XEXP (a
, 0), oa
= XEXP (a
, 1);
6102 if (GET_CODE (ra
) == PLUS
)
6103 tmp
= ra
, ra
= oa
, oa
= tmp
;
6105 rb
= XEXP (b
, 0), ob
= XEXP (b
, 1);
6106 if (GET_CODE (rb
) == PLUS
)
6107 tmp
= rb
, rb
= ob
, ob
= tmp
;
6109 if (rtx_equal_p (ra
, rb
))
6110 /* We matched: remove one reg completely. */
6112 else if (GET_CODE (ob
) != PLUS
&& rtx_equal_p (ra
, ob
))
6113 /* An alternate match. */
6115 else if (GET_CODE (oa
) != PLUS
&& rtx_equal_p (oa
, rb
))
6116 /* An alternate match. */
6120 /* Indicates an extra register in B. Strip one level from B and
6121 recurse, hoping B was the higher order expression. */
6122 ob
= express_from_1 (a
, ob
, mult
);
6125 return gen_rtx_PLUS (GET_MODE (b
), rb
, ob
);
6129 /* Here we are at the last level of A, go through the cases hoping to
6130 get rid of everything but a constant. */
6132 if (GET_CODE (a
) == PLUS
)
6136 ra
= XEXP (a
, 0), oa
= XEXP (a
, 1);
6137 if (rtx_equal_p (oa
, b
))
6139 else if (!rtx_equal_p (ra
, b
))
6142 if (GET_CODE (oa
) != CONST_INT
)
6145 return GEN_INT (-INTVAL (oa
) * INTVAL (mult
));
6147 else if (GET_CODE (a
) == CONST_INT
)
6149 return plus_constant (b
, -INTVAL (a
) * INTVAL (mult
));
6151 else if (GET_CODE (b
) == PLUS
)
6153 if (rtx_equal_p (a
, XEXP (b
, 0)))
6155 else if (rtx_equal_p (a
, XEXP (b
, 1)))
6160 else if (rtx_equal_p (a
, b
))
6167 express_from (g1
, g2
)
6168 struct induction
*g1
, *g2
;
6172 /* The value that G1 will be multiplied by must be a constant integer. Also,
6173 the only chance we have of getting a valid address is if b*c/a (see above
6174 for notation) is also an integer. */
6175 if (GET_CODE (g1
->mult_val
) == CONST_INT
6176 && GET_CODE (g2
->mult_val
) == CONST_INT
)
6178 if (g1
->mult_val
== const0_rtx
6179 || INTVAL (g2
->mult_val
) % INTVAL (g1
->mult_val
) != 0)
6181 mult
= GEN_INT (INTVAL (g2
->mult_val
) / INTVAL (g1
->mult_val
));
6183 else if (rtx_equal_p (g1
->mult_val
, g2
->mult_val
))
6187 /* ??? Find out if the one is a multiple of the other? */
6191 add
= express_from_1 (g1
->add_val
, g2
->add_val
, mult
);
6192 if (add
== NULL_RTX
)
6195 /* Form simplified final result. */
6196 if (mult
== const0_rtx
)
6198 else if (mult
== const1_rtx
)
6199 mult
= g1
->dest_reg
;
6201 mult
= gen_rtx_MULT (g2
->mode
, g1
->dest_reg
, mult
);
6203 if (add
== const0_rtx
)
6207 if (GET_CODE (add
) == PLUS
6208 && CONSTANT_P (XEXP (add
, 1)))
6210 rtx tem
= XEXP (add
, 1);
6211 mult
= gen_rtx_PLUS (g2
->mode
, mult
, XEXP (add
, 0));
6215 return gen_rtx_PLUS (g2
->mode
, mult
, add
);
6220 /* Return an rtx, if any, that expresses giv G2 as a function of the register
6221 represented by G1. This indicates that G2 should be combined with G1 and
6222 that G2 can use (either directly or via an address expression) a register
6223 used to represent G1. */
6226 combine_givs_p (g1
, g2
)
6227 struct induction
*g1
, *g2
;
6229 rtx tem
= express_from (g1
, g2
);
6231 /* If these givs are identical, they can be combined. We use the results
6232 of express_from because the addends are not in a canonical form, so
6233 rtx_equal_p is a weaker test. */
6234 if (tem
== g1
->dest_reg
)
6236 return g1
->dest_reg
;
6239 /* If G2 can be expressed as a function of G1 and that function is valid
6240 as an address and no more expensive than using a register for G2,
6241 the expression of G2 in terms of G1 can be used. */
6243 && g2
->giv_type
== DEST_ADDR
6244 && memory_address_p (g2
->mem_mode
, tem
)
6245 /* ??? Looses, especially with -fforce-addr, where *g2->location
6246 will always be a register, and so anything more complicated
6250 && ADDRESS_COST (tem
) <= ADDRESS_COST (*g2
->location
)
6252 && rtx_cost (tem
, MEM
) <= rtx_cost (*g2
->location
, MEM
)
6263 struct combine_givs_stats
6270 cmp_combine_givs_stats (x
, y
)
6271 struct combine_givs_stats
*x
, *y
;
6274 d
= y
->total_benefit
- x
->total_benefit
;
6275 /* Stabilize the sort. */
6277 d
= x
->giv_number
- y
->giv_number
;
6281 /* If one of these givs is a DEST_REG that was used by the other giv,
6282 this is actually a single use. Return 0 if this is not
6283 the case, -1 if g1 is the DEST_REG involved, and 1 if it was g2. */
6286 combine_givs_used_by_other (g1
, g2
)
6287 struct induction
*g1
, *g2
;
6289 if (g1
->giv_type
== DEST_REG
6290 && reg_mentioned_p (g1
->dest_reg
, PATTERN (g2
->insn
)))
6293 if (g2
->giv_type
== DEST_REG
6294 && reg_mentioned_p (g2
->dest_reg
, PATTERN (g1
->insn
)))
6301 combine_givs_benefit_from (g1
, g2
)
6302 struct induction
*g1
, *g2
;
6304 int tmp
= combine_givs_used_by_other (g1
, g2
);
6308 return g2
->benefit
- g1
->benefit
;
6313 /* Check all pairs of givs for iv_class BL and see if any can be combined with
6314 any other. If so, point SAME to the giv combined with and set NEW_REG to
6315 be an expression (in terms of the other giv's DEST_REG) equivalent to the
6316 giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
6320 struct iv_class
*bl
;
6322 struct induction
*g1
, *g2
, **giv_array
;
6323 int i
, j
, k
, giv_count
;
6324 struct combine_givs_stats
*stats
;
6327 /* Count givs, because bl->giv_count is incorrect here. */
6329 for (g1
= bl
->giv
; g1
; g1
= g1
->next_iv
)
6334 = (struct induction
**) alloca (giv_count
* sizeof (struct induction
*));
6336 for (g1
= bl
->giv
; g1
; g1
= g1
->next_iv
)
6338 giv_array
[i
++] = g1
;
6340 stats
= (struct combine_givs_stats
*) alloca (giv_count
* sizeof (*stats
));
6341 bzero ((char *) stats
, giv_count
* sizeof (*stats
));
6343 can_combine
= (rtx
*) alloca (giv_count
* giv_count
* sizeof(rtx
));
6344 bzero ((char *) can_combine
, giv_count
* giv_count
* sizeof(rtx
));
6346 for (i
= 0; i
< giv_count
; i
++)
6352 this_benefit
= g1
->benefit
;
6353 /* Add an additional weight for zero addends. */
6354 if (g1
->no_const_addval
)
6356 for (j
= 0; j
< giv_count
; j
++)
6362 && (this_combine
= combine_givs_p (g1
, g2
)) != NULL_RTX
)
6364 can_combine
[i
*giv_count
+ j
] = this_combine
;
6365 this_benefit
+= combine_givs_benefit_from (g1
, g2
);
6366 /* Add an additional weight for being reused more times. */
6370 stats
[i
].giv_number
= i
;
6371 stats
[i
].total_benefit
= this_benefit
;
6374 /* Iterate, combining until we can't. */
6376 qsort (stats
, giv_count
, sizeof(*stats
), cmp_combine_givs_stats
);
6378 if (loop_dump_stream
)
6380 fprintf (loop_dump_stream
, "Sorted combine statistics:\n");
6381 for (k
= 0; k
< giv_count
; k
++)
6383 g1
= giv_array
[stats
[k
].giv_number
];
6384 if (!g1
->combined_with
&& !g1
->same
)
6385 fprintf (loop_dump_stream
, " {%d, %d}",
6386 INSN_UID (giv_array
[stats
[k
].giv_number
]->insn
),
6387 stats
[k
].total_benefit
);
6389 putc ('\n', loop_dump_stream
);
6392 for (k
= 0; k
< giv_count
; k
++)
6394 int g1_add_benefit
= 0;
6396 i
= stats
[k
].giv_number
;
6399 /* If it has already been combined, skip. */
6400 if (g1
->combined_with
|| g1
->same
)
6403 for (j
= 0; j
< giv_count
; j
++)
6406 if (g1
!= g2
&& can_combine
[i
*giv_count
+ j
]
6407 /* If it has already been combined, skip. */
6408 && ! g2
->same
&& ! g2
->combined_with
)
6412 g2
->new_reg
= can_combine
[i
*giv_count
+ j
];
6414 g1
->combined_with
= 1;
6415 g1
->lifetime
+= g2
->lifetime
;
6417 g1_add_benefit
+= combine_givs_benefit_from (g1
, g2
);
6419 /* ??? The new final_[bg]iv_value code does a much better job
6420 of finding replaceable giv's, and hence this code may no
6421 longer be necessary. */
6422 if (! g2
->replaceable
&& REG_USERVAR_P (g2
->dest_reg
))
6423 g1_add_benefit
-= copy_cost
;
6425 /* To help optimize the next set of combinations, remove
6426 this giv from the benefits of other potential mates. */
6427 for (l
= 0; l
< giv_count
; ++l
)
6429 int m
= stats
[l
].giv_number
;
6430 if (can_combine
[m
*giv_count
+ j
])
6432 /* Remove additional weight for being reused. */
6433 stats
[l
].total_benefit
-= 3 +
6434 combine_givs_benefit_from (giv_array
[m
], g2
);
6438 if (loop_dump_stream
)
6439 fprintf (loop_dump_stream
,
6440 "giv at %d combined with giv at %d\n",
6441 INSN_UID (g2
->insn
), INSN_UID (g1
->insn
));
6445 /* To help optimize the next set of combinations, remove
6446 this giv from the benefits of other potential mates. */
6447 if (g1
->combined_with
)
6449 for (j
= 0; j
< giv_count
; ++j
)
6451 int m
= stats
[j
].giv_number
;
6452 if (can_combine
[m
*giv_count
+ j
])
6454 /* Remove additional weight for being reused. */
6455 stats
[j
].total_benefit
-= 3 +
6456 combine_givs_benefit_from (giv_array
[m
], g1
);
6460 g1
->benefit
+= g1_add_benefit
;
6462 /* We've finished with this giv, and everything it touched.
6463 Restart the combination so that proper weights for the
6464 rest of the givs are properly taken into account. */
6465 /* ??? Ideally we would compact the arrays at this point, so
6466 as to not cover old ground. But sanely compacting
6467 can_combine is tricky. */
6473 /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
6476 emit_iv_add_mult (b
, m
, a
, reg
, insert_before
)
6477 rtx b
; /* initial value of basic induction variable */
6478 rtx m
; /* multiplicative constant */
6479 rtx a
; /* additive constant */
6480 rtx reg
; /* destination register */
6486 /* Prevent unexpected sharing of these rtx. */
6490 /* Increase the lifetime of any invariants moved further in code. */
6491 update_reg_last_use (a
, insert_before
);
6492 update_reg_last_use (b
, insert_before
);
6493 update_reg_last_use (m
, insert_before
);
6496 result
= expand_mult_add (b
, reg
, m
, a
, GET_MODE (reg
), 0);
6498 emit_move_insn (reg
, result
);
6499 seq
= gen_sequence ();
6502 emit_insn_before (seq
, insert_before
);
6504 /* It is entirely possible that the expansion created lots of new
6505 registers. Iterate over the sequence we just created and
6508 if (GET_CODE (seq
) == SEQUENCE
)
6511 for (i
= 0; i
< XVECLEN (seq
, 0); ++i
)
6513 rtx set
= single_set (XVECEXP (seq
, 0, i
));
6514 if (set
&& GET_CODE (SET_DEST (set
)) == REG
)
6515 record_base_value (REGNO (SET_DEST (set
)), SET_SRC (set
), 0);
6518 else if (GET_CODE (seq
) == SET
6519 && GET_CODE (SET_DEST (seq
)) == REG
)
6520 record_base_value (REGNO (SET_DEST (seq
)), SET_SRC (seq
), 0);
6523 /* Test whether A * B can be computed without
6524 an actual multiply insn. Value is 1 if so. */
6527 product_cheap_p (a
, b
)
6533 struct obstack
*old_rtl_obstack
= rtl_obstack
;
6534 char *storage
= (char *) obstack_alloc (&temp_obstack
, 0);
6537 /* If only one is constant, make it B. */
6538 if (GET_CODE (a
) == CONST_INT
)
6539 tmp
= a
, a
= b
, b
= tmp
;
6541 /* If first constant, both constant, so don't need multiply. */
6542 if (GET_CODE (a
) == CONST_INT
)
6545 /* If second not constant, neither is constant, so would need multiply. */
6546 if (GET_CODE (b
) != CONST_INT
)
6549 /* One operand is constant, so might not need multiply insn. Generate the
6550 code for the multiply and see if a call or multiply, or long sequence
6551 of insns is generated. */
6553 rtl_obstack
= &temp_obstack
;
6555 expand_mult (GET_MODE (a
), a
, b
, NULL_RTX
, 0);
6556 tmp
= gen_sequence ();
6559 if (GET_CODE (tmp
) == SEQUENCE
)
6561 if (XVEC (tmp
, 0) == 0)
6563 else if (XVECLEN (tmp
, 0) > 3)
6566 for (i
= 0; i
< XVECLEN (tmp
, 0); i
++)
6568 rtx insn
= XVECEXP (tmp
, 0, i
);
6570 if (GET_CODE (insn
) != INSN
6571 || (GET_CODE (PATTERN (insn
)) == SET
6572 && GET_CODE (SET_SRC (PATTERN (insn
))) == MULT
)
6573 || (GET_CODE (PATTERN (insn
)) == PARALLEL
6574 && GET_CODE (XVECEXP (PATTERN (insn
), 0, 0)) == SET
6575 && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn
), 0, 0))) == MULT
))
6582 else if (GET_CODE (tmp
) == SET
6583 && GET_CODE (SET_SRC (tmp
)) == MULT
)
6585 else if (GET_CODE (tmp
) == PARALLEL
6586 && GET_CODE (XVECEXP (tmp
, 0, 0)) == SET
6587 && GET_CODE (SET_SRC (XVECEXP (tmp
, 0, 0))) == MULT
)
6590 /* Free any storage we obtained in generating this multiply and restore rtl
6591 allocation to its normal obstack. */
6592 obstack_free (&temp_obstack
, storage
);
6593 rtl_obstack
= old_rtl_obstack
;
6598 /* Check to see if loop can be terminated by a "decrement and branch until
6599 zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
6600 Also try reversing an increment loop to a decrement loop
6601 to see if the optimization can be performed.
6602 Value is nonzero if optimization was performed. */
6604 /* This is useful even if the architecture doesn't have such an insn,
6605 because it might change a loops which increments from 0 to n to a loop
6606 which decrements from n to 0. A loop that decrements to zero is usually
6607 faster than one that increments from zero. */
6609 /* ??? This could be rewritten to use some of the loop unrolling procedures,
6610 such as approx_final_value, biv_total_increment, loop_iterations, and
6611 final_[bg]iv_value. */
6614 check_dbra_loop (loop_end
, insn_count
, loop_start
, loop_info
)
6618 struct loop_info
*loop_info
;
6620 struct iv_class
*bl
;
6627 rtx before_comparison
;
6631 int compare_and_branch
;
6633 /* If last insn is a conditional branch, and the insn before tests a
6634 register value, try to optimize it. Otherwise, we can't do anything. */
6636 jump
= PREV_INSN (loop_end
);
6637 comparison
= get_condition_for_loop (jump
);
6638 if (comparison
== 0)
6641 /* Try to compute whether the compare/branch at the loop end is one or
6642 two instructions. */
6643 get_condition (jump
, &first_compare
);
6644 if (first_compare
== jump
)
6645 compare_and_branch
= 1;
6646 else if (first_compare
== prev_nonnote_insn (jump
))
6647 compare_and_branch
= 2;
6651 /* Check all of the bivs to see if the compare uses one of them.
6652 Skip biv's set more than once because we can't guarantee that
6653 it will be zero on the last iteration. Also skip if the biv is
6654 used between its update and the test insn. */
6656 for (bl
= loop_iv_list
; bl
; bl
= bl
->next
)
6658 if (bl
->biv_count
== 1
6659 && bl
->biv
->dest_reg
== XEXP (comparison
, 0)
6660 && ! reg_used_between_p (regno_reg_rtx
[bl
->regno
], bl
->biv
->insn
,
6668 /* Look for the case where the basic induction variable is always
6669 nonnegative, and equals zero on the last iteration.
6670 In this case, add a reg_note REG_NONNEG, which allows the
6671 m68k DBRA instruction to be used. */
6673 if (((GET_CODE (comparison
) == GT
6674 && GET_CODE (XEXP (comparison
, 1)) == CONST_INT
6675 && INTVAL (XEXP (comparison
, 1)) == -1)
6676 || (GET_CODE (comparison
) == NE
&& XEXP (comparison
, 1) == const0_rtx
))
6677 && GET_CODE (bl
->biv
->add_val
) == CONST_INT
6678 && INTVAL (bl
->biv
->add_val
) < 0)
6680 /* Initial value must be greater than 0,
6681 init_val % -dec_value == 0 to ensure that it equals zero on
6682 the last iteration */
6684 if (GET_CODE (bl
->initial_value
) == CONST_INT
6685 && INTVAL (bl
->initial_value
) > 0
6686 && (INTVAL (bl
->initial_value
)
6687 % (-INTVAL (bl
->biv
->add_val
))) == 0)
6689 /* register always nonnegative, add REG_NOTE to branch */
6690 REG_NOTES (PREV_INSN (loop_end
))
6691 = gen_rtx_EXPR_LIST (REG_NONNEG
, NULL_RTX
,
6692 REG_NOTES (PREV_INSN (loop_end
)));
6698 /* If the decrement is 1 and the value was tested as >= 0 before
6699 the loop, then we can safely optimize. */
6700 for (p
= loop_start
; p
; p
= PREV_INSN (p
))
6702 if (GET_CODE (p
) == CODE_LABEL
)
6704 if (GET_CODE (p
) != JUMP_INSN
)
6707 before_comparison
= get_condition_for_loop (p
);
6708 if (before_comparison
6709 && XEXP (before_comparison
, 0) == bl
->biv
->dest_reg
6710 && GET_CODE (before_comparison
) == LT
6711 && XEXP (before_comparison
, 1) == const0_rtx
6712 && ! reg_set_between_p (bl
->biv
->dest_reg
, p
, loop_start
)
6713 && INTVAL (bl
->biv
->add_val
) == -1)
6715 REG_NOTES (PREV_INSN (loop_end
))
6716 = gen_rtx_EXPR_LIST (REG_NONNEG
, NULL_RTX
,
6717 REG_NOTES (PREV_INSN (loop_end
)));
6724 else if (INTVAL (bl
->biv
->add_val
) > 0)
6726 /* Try to change inc to dec, so can apply above optimization. */
6728 all registers modified are induction variables or invariant,
6729 all memory references have non-overlapping addresses
6730 (obviously true if only one write)
6731 allow 2 insns for the compare/jump at the end of the loop. */
6732 /* Also, we must avoid any instructions which use both the reversed
6733 biv and another biv. Such instructions will fail if the loop is
6734 reversed. We meet this condition by requiring that either
6735 no_use_except_counting is true, or else that there is only
6737 int num_nonfixed_reads
= 0;
6738 /* 1 if the iteration var is used only to count iterations. */
6739 int no_use_except_counting
= 0;
6740 /* 1 if the loop has no memory store, or it has a single memory store
6741 which is reversible. */
6742 int reversible_mem_store
= 1;
6744 if (bl
->giv_count
== 0
6745 && ! loop_number_exit_count
[uid_loop_num
[INSN_UID (loop_start
)]])
6747 rtx bivreg
= regno_reg_rtx
[bl
->regno
];
6749 /* If there are no givs for this biv, and the only exit is the
6750 fall through at the end of the loop, then
6751 see if perhaps there are no uses except to count. */
6752 no_use_except_counting
= 1;
6753 for (p
= loop_start
; p
!= loop_end
; p
= NEXT_INSN (p
))
6754 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i')
6756 rtx set
= single_set (p
);
6758 if (set
&& GET_CODE (SET_DEST (set
)) == REG
6759 && REGNO (SET_DEST (set
)) == bl
->regno
)
6760 /* An insn that sets the biv is okay. */
6762 else if (p
== prev_nonnote_insn (prev_nonnote_insn (loop_end
))
6763 || p
== prev_nonnote_insn (loop_end
))
6764 /* Don't bother about the end test. */
6766 else if (reg_mentioned_p (bivreg
, PATTERN (p
)))
6768 no_use_except_counting
= 0;
6774 if (no_use_except_counting
)
6775 ; /* no need to worry about MEMs. */
6776 else if (num_mem_sets
<= 1)
6778 for (p
= loop_start
; p
!= loop_end
; p
= NEXT_INSN (p
))
6779 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i')
6780 num_nonfixed_reads
+= count_nonfixed_reads (PATTERN (p
));
6782 /* If the loop has a single store, and the destination address is
6783 invariant, then we can't reverse the loop, because this address
6784 might then have the wrong value at loop exit.
6785 This would work if the source was invariant also, however, in that
6786 case, the insn should have been moved out of the loop. */
6788 if (num_mem_sets
== 1)
6789 reversible_mem_store
6790 = (! unknown_address_altered
6791 && ! invariant_p (XEXP (loop_store_mems
, 0)));
6796 /* This code only acts for innermost loops. Also it simplifies
6797 the memory address check by only reversing loops with
6798 zero or one memory access.
6799 Two memory accesses could involve parts of the same array,
6800 and that can't be reversed.
6801 If the biv is used only for counting, than we don't need to worry
6802 about all these things. */
6804 if ((num_nonfixed_reads
<= 1
6806 && !loop_has_volatile
6807 && reversible_mem_store
6808 && (bl
->giv_count
+ bl
->biv_count
+ num_mem_sets
6809 + num_movables
+ compare_and_branch
== insn_count
)
6810 && (bl
== loop_iv_list
&& bl
->next
== 0))
6811 || no_use_except_counting
)
6815 /* Loop can be reversed. */
6816 if (loop_dump_stream
)
6817 fprintf (loop_dump_stream
, "Can reverse loop\n");
6819 /* Now check other conditions:
6821 The increment must be a constant, as must the initial value,
6822 and the comparison code must be LT.
6824 This test can probably be improved since +/- 1 in the constant
6825 can be obtained by changing LT to LE and vice versa; this is
6829 /* for constants, LE gets turned into LT */
6830 && (GET_CODE (comparison
) == LT
6831 || (GET_CODE (comparison
) == LE
6832 && no_use_except_counting
)))
6834 HOST_WIDE_INT add_val
, add_adjust
, comparison_val
;
6835 rtx initial_value
, comparison_value
;
6837 enum rtx_code cmp_code
;
6838 int comparison_const_width
;
6839 unsigned HOST_WIDE_INT comparison_sign_mask
;
6841 add_val
= INTVAL (bl
->biv
->add_val
);
6842 comparison_value
= XEXP (comparison
, 1);
6843 if (GET_MODE (comparison_value
) == VOIDmode
)
6844 comparison_const_width
6845 = GET_MODE_BITSIZE (GET_MODE (XEXP (comparison
, 0)));
6847 comparison_const_width
6848 = GET_MODE_BITSIZE (GET_MODE (comparison_value
));
6849 if (comparison_const_width
> HOST_BITS_PER_WIDE_INT
)
6850 comparison_const_width
= HOST_BITS_PER_WIDE_INT
;
6851 comparison_sign_mask
6852 = (unsigned HOST_WIDE_INT
)1 << (comparison_const_width
- 1);
6854 /* If the comparison value is not a loop invariant, then we
6855 can not reverse this loop.
6857 ??? If the insns which initialize the comparison value as
6858 a whole compute an invariant result, then we could move
6859 them out of the loop and proceed with loop reversal. */
6860 if (!invariant_p (comparison_value
))
6863 if (GET_CODE (comparison_value
) == CONST_INT
)
6864 comparison_val
= INTVAL (comparison_value
);
6865 initial_value
= bl
->initial_value
;
6867 /* Normalize the initial value if it is an integer and
6868 has no other use except as a counter. This will allow
6869 a few more loops to be reversed. */
6870 if (no_use_except_counting
6871 && GET_CODE (comparison_value
) == CONST_INT
6872 && GET_CODE (initial_value
) == CONST_INT
)
6874 comparison_val
= comparison_val
- INTVAL (bl
->initial_value
);
6875 /* The code below requires comparison_val to be a multiple
6876 of add_val in order to do the loop reversal, so
6877 round up comparison_val to a multiple of add_val.
6878 Since comparison_value is constant, we know that the
6879 current comparison code is LT. */
6880 comparison_val
= comparison_val
+ add_val
- 1;
6882 -= (unsigned HOST_WIDE_INT
) comparison_val
% add_val
;
6883 /* We postpone overflow checks for COMPARISON_VAL here;
6884 even if there is an overflow, we might still be able to
6885 reverse the loop, if converting the loop exit test to
6887 initial_value
= const0_rtx
;
6890 /* First check if we can do a vanilla loop reversal. */
6891 if (initial_value
== const0_rtx
6892 /* If we have a decrement_and_branch_on_count, prefer
6893 the NE test, since this will allow that instruction to
6894 be generated. Note that we must use a vanilla loop
6895 reversal if the biv is used to calculate a giv or has
6896 a non-counting use. */
6897 #if ! defined (HAVE_decrement_and_branch_until_zero) && defined (HAVE_decrement_and_branch_on_count)
6898 && (! (add_val
== 1 && loop_info
->vtop
6899 && (bl
->biv_count
== 0
6900 || no_use_except_counting
)))
6902 && GET_CODE (comparison_value
) == CONST_INT
6903 /* Now do postponed overflow checks on COMPARISON_VAL. */
6904 && ! (((comparison_val
- add_val
) ^ INTVAL (comparison_value
))
6905 & comparison_sign_mask
))
6907 /* Register will always be nonnegative, with value
6908 0 on last iteration */
6909 add_adjust
= add_val
;
6913 else if (add_val
== 1 && loop_info
->vtop
6914 && (bl
->biv_count
== 0
6915 || no_use_except_counting
))
6923 if (GET_CODE (comparison
) == LE
)
6924 add_adjust
-= add_val
;
6926 /* If the initial value is not zero, or if the comparison
6927 value is not an exact multiple of the increment, then we
6928 can not reverse this loop. */
6929 if (initial_value
== const0_rtx
6930 && GET_CODE (comparison_value
) == CONST_INT
)
6932 if (((unsigned HOST_WIDE_INT
) comparison_val
% add_val
) != 0)
6937 if (! no_use_except_counting
|| add_val
!= 1)
6941 final_value
= comparison_value
;
6943 /* Reset these in case we normalized the initial value
6944 and comparison value above. */
6945 if (GET_CODE (comparison_value
) == CONST_INT
6946 && GET_CODE (initial_value
) == CONST_INT
)
6948 comparison_value
= GEN_INT (comparison_val
);
6950 = GEN_INT (comparison_val
+ INTVAL (bl
->initial_value
));
6952 bl
->initial_value
= initial_value
;
6954 /* Save some info needed to produce the new insns. */
6955 reg
= bl
->biv
->dest_reg
;
6956 jump_label
= XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end
))), 1);
6957 if (jump_label
== pc_rtx
)
6958 jump_label
= XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end
))), 2);
6959 new_add_val
= GEN_INT (- INTVAL (bl
->biv
->add_val
));
6961 /* Set start_value; if this is not a CONST_INT, we need
6963 Initialize biv to start_value before loop start.
6964 The old initializing insn will be deleted as a
6965 dead store by flow.c. */
6966 if (initial_value
== const0_rtx
6967 && GET_CODE (comparison_value
) == CONST_INT
)
6969 start_value
= GEN_INT (comparison_val
- add_adjust
);
6970 emit_insn_before (gen_move_insn (reg
, start_value
),
6973 else if (GET_CODE (initial_value
) == CONST_INT
)
6975 rtx offset
= GEN_INT (-INTVAL (initial_value
) - add_adjust
);
6976 enum machine_mode mode
= GET_MODE (reg
);
6977 enum insn_code icode
6978 = add_optab
->handlers
[(int) mode
].insn_code
;
6979 if (! (*insn_operand_predicate
[icode
][0]) (reg
, mode
)
6980 || ! ((*insn_operand_predicate
[icode
][1])
6981 (comparison_value
, mode
))
6982 || ! (*insn_operand_predicate
[icode
][2]) (offset
, mode
))
6985 = gen_rtx_PLUS (mode
, comparison_value
, offset
);
6986 emit_insn_before ((GEN_FCN (icode
)
6987 (reg
, comparison_value
, offset
)),
6989 if (GET_CODE (comparison
) == LE
)
6990 final_value
= gen_rtx_PLUS (mode
, comparison_value
,
6993 else if (! add_adjust
)
6995 enum machine_mode mode
= GET_MODE (reg
);
6996 enum insn_code icode
6997 = sub_optab
->handlers
[(int) mode
].insn_code
;
6998 if (! (*insn_operand_predicate
[icode
][0]) (reg
, mode
)
6999 || ! ((*insn_operand_predicate
[icode
][1])
7000 (comparison_value
, mode
))
7001 || ! ((*insn_operand_predicate
[icode
][2])
7002 (initial_value
, mode
)))
7005 = gen_rtx_MINUS (mode
, comparison_value
, initial_value
);
7006 emit_insn_before ((GEN_FCN (icode
)
7007 (reg
, comparison_value
, initial_value
)),
7011 /* We could handle the other cases too, but it'll be
7012 better to have a testcase first. */
7015 /* We may not have a single insn which can increment a reg, so
7016 create a sequence to hold all the insns from expand_inc. */
7018 expand_inc (reg
, new_add_val
);
7019 tem
= gen_sequence ();
7022 p
= emit_insn_before (tem
, bl
->biv
->insn
);
7023 delete_insn (bl
->biv
->insn
);
7025 /* Update biv info to reflect its new status. */
7027 bl
->initial_value
= start_value
;
7028 bl
->biv
->add_val
= new_add_val
;
7030 /* Update loop info. */
7031 loop_info
->initial_value
= reg
;
7032 loop_info
->initial_equiv_value
= reg
;
7033 loop_info
->final_value
= const0_rtx
;
7034 loop_info
->final_equiv_value
= const0_rtx
;
7035 loop_info
->comparison_value
= const0_rtx
;
7036 loop_info
->comparison_code
= cmp_code
;
7037 loop_info
->increment
= new_add_val
;
7039 /* Inc LABEL_NUSES so that delete_insn will
7040 not delete the label. */
7041 LABEL_NUSES (XEXP (jump_label
, 0)) ++;
7043 /* Emit an insn after the end of the loop to set the biv's
7044 proper exit value if it is used anywhere outside the loop. */
7045 if ((REGNO_LAST_UID (bl
->regno
) != INSN_UID (first_compare
))
7047 || REGNO_FIRST_UID (bl
->regno
) != INSN_UID (bl
->init_insn
))
7048 emit_insn_after (gen_move_insn (reg
, final_value
),
7051 /* Delete compare/branch at end of loop. */
7052 delete_insn (PREV_INSN (loop_end
));
7053 if (compare_and_branch
== 2)
7054 delete_insn (first_compare
);
7056 /* Add new compare/branch insn at end of loop. */
7058 emit_cmp_and_jump_insns (reg
, const0_rtx
, cmp_code
, NULL_RTX
,
7059 GET_MODE (reg
), 0, 0,
7060 XEXP (jump_label
, 0));
7061 tem
= gen_sequence ();
7063 emit_jump_insn_before (tem
, loop_end
);
7065 for (tem
= PREV_INSN (loop_end
);
7066 tem
&& GET_CODE (tem
) != JUMP_INSN
;
7067 tem
= PREV_INSN (tem
))
7071 JUMP_LABEL (tem
) = XEXP (jump_label
, 0);
7077 /* Increment of LABEL_NUSES done above. */
7078 /* Register is now always nonnegative,
7079 so add REG_NONNEG note to the branch. */
7080 REG_NOTES (tem
) = gen_rtx_EXPR_LIST (REG_NONNEG
, NULL_RTX
,
7086 /* Mark that this biv has been reversed. Each giv which depends
7087 on this biv, and which is also live past the end of the loop
7088 will have to be fixed up. */
7092 if (loop_dump_stream
)
7093 fprintf (loop_dump_stream
,
7094 "Reversed loop and added reg_nonneg\n");
7104 /* Verify whether the biv BL appears to be eliminable,
7105 based on the insns in the loop that refer to it.
7106 LOOP_START is the first insn of the loop, and END is the end insn.
7108 If ELIMINATE_P is non-zero, actually do the elimination.
7110 THRESHOLD and INSN_COUNT are from loop_optimize and are used to
7111 determine whether invariant insns should be placed inside or at the
7112 start of the loop. */
7115 maybe_eliminate_biv (bl
, loop_start
, end
, eliminate_p
, threshold
, insn_count
)
7116 struct iv_class
*bl
;
7120 int threshold
, insn_count
;
7122 rtx reg
= bl
->biv
->dest_reg
;
7125 /* Scan all insns in the loop, stopping if we find one that uses the
7126 biv in a way that we cannot eliminate. */
7128 for (p
= loop_start
; p
!= end
; p
= NEXT_INSN (p
))
7130 enum rtx_code code
= GET_CODE (p
);
7131 rtx where
= threshold
>= insn_count
? loop_start
: p
;
7133 if ((code
== INSN
|| code
== JUMP_INSN
|| code
== CALL_INSN
)
7134 && reg_mentioned_p (reg
, PATTERN (p
))
7135 && ! maybe_eliminate_biv_1 (PATTERN (p
), p
, bl
, eliminate_p
, where
))
7137 if (loop_dump_stream
)
7138 fprintf (loop_dump_stream
,
7139 "Cannot eliminate biv %d: biv used in insn %d.\n",
7140 bl
->regno
, INSN_UID (p
));
7147 if (loop_dump_stream
)
7148 fprintf (loop_dump_stream
, "biv %d %s eliminated.\n",
7149 bl
->regno
, eliminate_p
? "was" : "can be");
7156 /* If BL appears in X (part of the pattern of INSN), see if we can
7157 eliminate its use. If so, return 1. If not, return 0.
7159 If BIV does not appear in X, return 1.
7161 If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
7162 where extra insns should be added. Depending on how many items have been
7163 moved out of the loop, it will either be before INSN or at the start of
7167 maybe_eliminate_biv_1 (x
, insn
, bl
, eliminate_p
, where
)
7169 struct iv_class
*bl
;
7173 enum rtx_code code
= GET_CODE (x
);
7174 rtx reg
= bl
->biv
->dest_reg
;
7175 enum machine_mode mode
= GET_MODE (reg
);
7176 struct induction
*v
;
7188 /* If we haven't already been able to do something with this BIV,
7189 we can't eliminate it. */
7195 /* If this sets the BIV, it is not a problem. */
7196 if (SET_DEST (x
) == reg
)
7199 /* If this is an insn that defines a giv, it is also ok because
7200 it will go away when the giv is reduced. */
7201 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7202 if (v
->giv_type
== DEST_REG
&& SET_DEST (x
) == v
->dest_reg
)
7206 if (SET_DEST (x
) == cc0_rtx
&& SET_SRC (x
) == reg
)
7208 /* Can replace with any giv that was reduced and
7209 that has (MULT_VAL != 0) and (ADD_VAL == 0).
7210 Require a constant for MULT_VAL, so we know it's nonzero.
7211 ??? We disable this optimization to avoid potential
7214 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7215 if (CONSTANT_P (v
->mult_val
) && v
->mult_val
!= const0_rtx
7216 && v
->add_val
== const0_rtx
7217 && ! v
->ignore
&& ! v
->maybe_dead
&& v
->always_computable
7221 /* If the giv V had the auto-inc address optimization applied
7222 to it, and INSN occurs between the giv insn and the biv
7223 insn, then we must adjust the value used here.
7224 This is rare, so we don't bother to do so. */
7226 && ((INSN_LUID (v
->insn
) < INSN_LUID (insn
)
7227 && INSN_LUID (insn
) < INSN_LUID (bl
->biv
->insn
))
7228 || (INSN_LUID (v
->insn
) > INSN_LUID (insn
)
7229 && INSN_LUID (insn
) > INSN_LUID (bl
->biv
->insn
))))
7235 /* If the giv has the opposite direction of change,
7236 then reverse the comparison. */
7237 if (INTVAL (v
->mult_val
) < 0)
7238 new = gen_rtx_COMPARE (GET_MODE (v
->new_reg
),
7239 const0_rtx
, v
->new_reg
);
7243 /* We can probably test that giv's reduced reg. */
7244 if (validate_change (insn
, &SET_SRC (x
), new, 0))
7248 /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
7249 replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
7250 Require a constant for MULT_VAL, so we know it's nonzero.
7251 ??? Do this only if ADD_VAL is a pointer to avoid a potential
7252 overflow problem. */
7254 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7255 if (CONSTANT_P (v
->mult_val
) && v
->mult_val
!= const0_rtx
7256 && ! v
->ignore
&& ! v
->maybe_dead
&& v
->always_computable
7258 && (GET_CODE (v
->add_val
) == SYMBOL_REF
7259 || GET_CODE (v
->add_val
) == LABEL_REF
7260 || GET_CODE (v
->add_val
) == CONST
7261 || (GET_CODE (v
->add_val
) == REG
7262 && REGNO_POINTER_FLAG (REGNO (v
->add_val
)))))
7264 /* If the giv V had the auto-inc address optimization applied
7265 to it, and INSN occurs between the giv insn and the biv
7266 insn, then we must adjust the value used here.
7267 This is rare, so we don't bother to do so. */
7269 && ((INSN_LUID (v
->insn
) < INSN_LUID (insn
)
7270 && INSN_LUID (insn
) < INSN_LUID (bl
->biv
->insn
))
7271 || (INSN_LUID (v
->insn
) > INSN_LUID (insn
)
7272 && INSN_LUID (insn
) > INSN_LUID (bl
->biv
->insn
))))
7278 /* If the giv has the opposite direction of change,
7279 then reverse the comparison. */
7280 if (INTVAL (v
->mult_val
) < 0)
7281 new = gen_rtx_COMPARE (VOIDmode
, copy_rtx (v
->add_val
),
7284 new = gen_rtx_COMPARE (VOIDmode
, v
->new_reg
,
7285 copy_rtx (v
->add_val
));
7287 /* Replace biv with the giv's reduced register. */
7288 update_reg_last_use (v
->add_val
, insn
);
7289 if (validate_change (insn
, &SET_SRC (PATTERN (insn
)), new, 0))
7292 /* Insn doesn't support that constant or invariant. Copy it
7293 into a register (it will be a loop invariant.) */
7294 tem
= gen_reg_rtx (GET_MODE (v
->new_reg
));
7296 emit_insn_before (gen_move_insn (tem
, copy_rtx (v
->add_val
)),
7299 /* Substitute the new register for its invariant value in
7300 the compare expression. */
7301 XEXP (new, (INTVAL (v
->mult_val
) < 0) ? 0 : 1) = tem
;
7302 if (validate_change (insn
, &SET_SRC (PATTERN (insn
)), new, 0))
7311 case GT
: case GE
: case GTU
: case GEU
:
7312 case LT
: case LE
: case LTU
: case LEU
:
7313 /* See if either argument is the biv. */
7314 if (XEXP (x
, 0) == reg
)
7315 arg
= XEXP (x
, 1), arg_operand
= 1;
7316 else if (XEXP (x
, 1) == reg
)
7317 arg
= XEXP (x
, 0), arg_operand
= 0;
7321 if (CONSTANT_P (arg
))
7323 /* First try to replace with any giv that has constant positive
7324 mult_val and constant add_val. We might be able to support
7325 negative mult_val, but it seems complex to do it in general. */
7327 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7328 if (CONSTANT_P (v
->mult_val
) && INTVAL (v
->mult_val
) > 0
7329 && (GET_CODE (v
->add_val
) == SYMBOL_REF
7330 || GET_CODE (v
->add_val
) == LABEL_REF
7331 || GET_CODE (v
->add_val
) == CONST
7332 || (GET_CODE (v
->add_val
) == REG
7333 && REGNO_POINTER_FLAG (REGNO (v
->add_val
))))
7334 && ! v
->ignore
&& ! v
->maybe_dead
&& v
->always_computable
7337 /* If the giv V had the auto-inc address optimization applied
7338 to it, and INSN occurs between the giv insn and the biv
7339 insn, then we must adjust the value used here.
7340 This is rare, so we don't bother to do so. */
7342 && ((INSN_LUID (v
->insn
) < INSN_LUID (insn
)
7343 && INSN_LUID (insn
) < INSN_LUID (bl
->biv
->insn
))
7344 || (INSN_LUID (v
->insn
) > INSN_LUID (insn
)
7345 && INSN_LUID (insn
) > INSN_LUID (bl
->biv
->insn
))))
7351 /* Replace biv with the giv's reduced reg. */
7352 XEXP (x
, 1-arg_operand
) = v
->new_reg
;
7354 /* If all constants are actually constant integers and
7355 the derived constant can be directly placed in the COMPARE,
7357 if (GET_CODE (arg
) == CONST_INT
7358 && GET_CODE (v
->mult_val
) == CONST_INT
7359 && GET_CODE (v
->add_val
) == CONST_INT
7360 && validate_change (insn
, &XEXP (x
, arg_operand
),
7361 GEN_INT (INTVAL (arg
)
7362 * INTVAL (v
->mult_val
)
7363 + INTVAL (v
->add_val
)), 0))
7366 /* Otherwise, load it into a register. */
7367 tem
= gen_reg_rtx (mode
);
7368 emit_iv_add_mult (arg
, v
->mult_val
, v
->add_val
, tem
, where
);
7369 if (validate_change (insn
, &XEXP (x
, arg_operand
), tem
, 0))
7372 /* If that failed, put back the change we made above. */
7373 XEXP (x
, 1-arg_operand
) = reg
;
7376 /* Look for giv with positive constant mult_val and nonconst add_val.
7377 Insert insns to calculate new compare value.
7378 ??? Turn this off due to possible overflow. */
7380 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7381 if (CONSTANT_P (v
->mult_val
) && INTVAL (v
->mult_val
) > 0
7382 && ! v
->ignore
&& ! v
->maybe_dead
&& v
->always_computable
7388 /* If the giv V had the auto-inc address optimization applied
7389 to it, and INSN occurs between the giv insn and the biv
7390 insn, then we must adjust the value used here.
7391 This is rare, so we don't bother to do so. */
7393 && ((INSN_LUID (v
->insn
) < INSN_LUID (insn
)
7394 && INSN_LUID (insn
) < INSN_LUID (bl
->biv
->insn
))
7395 || (INSN_LUID (v
->insn
) > INSN_LUID (insn
)
7396 && INSN_LUID (insn
) > INSN_LUID (bl
->biv
->insn
))))
7402 tem
= gen_reg_rtx (mode
);
7404 /* Replace biv with giv's reduced register. */
7405 validate_change (insn
, &XEXP (x
, 1 - arg_operand
),
7408 /* Compute value to compare against. */
7409 emit_iv_add_mult (arg
, v
->mult_val
, v
->add_val
, tem
, where
);
7410 /* Use it in this insn. */
7411 validate_change (insn
, &XEXP (x
, arg_operand
), tem
, 1);
7412 if (apply_change_group ())
7416 else if (GET_CODE (arg
) == REG
|| GET_CODE (arg
) == MEM
)
7418 if (invariant_p (arg
) == 1)
7420 /* Look for giv with constant positive mult_val and nonconst
7421 add_val. Insert insns to compute new compare value.
7422 ??? Turn this off due to possible overflow. */
7424 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7425 if (CONSTANT_P (v
->mult_val
) && INTVAL (v
->mult_val
) > 0
7426 && ! v
->ignore
&& ! v
->maybe_dead
&& v
->always_computable
7432 /* If the giv V had the auto-inc address optimization applied
7433 to it, and INSN occurs between the giv insn and the biv
7434 insn, then we must adjust the value used here.
7435 This is rare, so we don't bother to do so. */
7437 && ((INSN_LUID (v
->insn
) < INSN_LUID (insn
)
7438 && INSN_LUID (insn
) < INSN_LUID (bl
->biv
->insn
))
7439 || (INSN_LUID (v
->insn
) > INSN_LUID (insn
)
7440 && INSN_LUID (insn
) > INSN_LUID (bl
->biv
->insn
))))
7446 tem
= gen_reg_rtx (mode
);
7448 /* Replace biv with giv's reduced register. */
7449 validate_change (insn
, &XEXP (x
, 1 - arg_operand
),
7452 /* Compute value to compare against. */
7453 emit_iv_add_mult (arg
, v
->mult_val
, v
->add_val
,
7455 validate_change (insn
, &XEXP (x
, arg_operand
), tem
, 1);
7456 if (apply_change_group ())
7461 /* This code has problems. Basically, you can't know when
7462 seeing if we will eliminate BL, whether a particular giv
7463 of ARG will be reduced. If it isn't going to be reduced,
7464 we can't eliminate BL. We can try forcing it to be reduced,
7465 but that can generate poor code.
7467 The problem is that the benefit of reducing TV, below should
7468 be increased if BL can actually be eliminated, but this means
7469 we might have to do a topological sort of the order in which
7470 we try to process biv. It doesn't seem worthwhile to do
7471 this sort of thing now. */
7474 /* Otherwise the reg compared with had better be a biv. */
7475 if (GET_CODE (arg
) != REG
7476 || reg_iv_type
[REGNO (arg
)] != BASIC_INDUCT
)
7479 /* Look for a pair of givs, one for each biv,
7480 with identical coefficients. */
7481 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7483 struct induction
*tv
;
7485 if (v
->ignore
|| v
->maybe_dead
|| v
->mode
!= mode
)
7488 for (tv
= reg_biv_class
[REGNO (arg
)]->giv
; tv
; tv
= tv
->next_iv
)
7489 if (! tv
->ignore
&& ! tv
->maybe_dead
7490 && rtx_equal_p (tv
->mult_val
, v
->mult_val
)
7491 && rtx_equal_p (tv
->add_val
, v
->add_val
)
7492 && tv
->mode
== mode
)
7494 /* If the giv V had the auto-inc address optimization applied
7495 to it, and INSN occurs between the giv insn and the biv
7496 insn, then we must adjust the value used here.
7497 This is rare, so we don't bother to do so. */
7499 && ((INSN_LUID (v
->insn
) < INSN_LUID (insn
)
7500 && INSN_LUID (insn
) < INSN_LUID (bl
->biv
->insn
))
7501 || (INSN_LUID (v
->insn
) > INSN_LUID (insn
)
7502 && INSN_LUID (insn
) > INSN_LUID (bl
->biv
->insn
))))
7508 /* Replace biv with its giv's reduced reg. */
7509 XEXP (x
, 1-arg_operand
) = v
->new_reg
;
7510 /* Replace other operand with the other giv's
7512 XEXP (x
, arg_operand
) = tv
->new_reg
;
7519 /* If we get here, the biv can't be eliminated. */
7523 /* If this address is a DEST_ADDR giv, it doesn't matter if the
7524 biv is used in it, since it will be replaced. */
7525 for (v
= bl
->giv
; v
; v
= v
->next_iv
)
7526 if (v
->giv_type
== DEST_ADDR
&& v
->location
== &XEXP (x
, 0))
7534 /* See if any subexpression fails elimination. */
7535 fmt
= GET_RTX_FORMAT (code
);
7536 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
7541 if (! maybe_eliminate_biv_1 (XEXP (x
, i
), insn
, bl
,
7542 eliminate_p
, where
))
7547 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7548 if (! maybe_eliminate_biv_1 (XVECEXP (x
, i
, j
), insn
, bl
,
7549 eliminate_p
, where
))
7558 /* Return nonzero if the last use of REG
7559 is in an insn following INSN in the same basic block. */
7562 last_use_this_basic_block (reg
, insn
)
7568 n
&& GET_CODE (n
) != CODE_LABEL
&& GET_CODE (n
) != JUMP_INSN
;
7571 if (REGNO_LAST_UID (REGNO (reg
)) == INSN_UID (n
))
7577 /* Called via `note_stores' to record the initial value of a biv. Here we
7578 just record the location of the set and process it later. */
7581 record_initial (dest
, set
)
7585 struct iv_class
*bl
;
7587 if (GET_CODE (dest
) != REG
7588 || REGNO (dest
) >= max_reg_before_loop
7589 || reg_iv_type
[REGNO (dest
)] != BASIC_INDUCT
)
7592 bl
= reg_biv_class
[REGNO (dest
)];
7594 /* If this is the first set found, record it. */
7595 if (bl
->init_insn
== 0)
7597 bl
->init_insn
= note_insn
;
7602 /* If any of the registers in X are "old" and currently have a last use earlier
7603 than INSN, update them to have a last use of INSN. Their actual last use
7604 will be the previous insn but it will not have a valid uid_luid so we can't
7608 update_reg_last_use (x
, insn
)
7612 /* Check for the case where INSN does not have a valid luid. In this case,
7613 there is no need to modify the regno_last_uid, as this can only happen
7614 when code is inserted after the loop_end to set a pseudo's final value,
7615 and hence this insn will never be the last use of x. */
7616 if (GET_CODE (x
) == REG
&& REGNO (x
) < max_reg_before_loop
7617 && INSN_UID (insn
) < max_uid_for_loop
7618 && uid_luid
[REGNO_LAST_UID (REGNO (x
))] < uid_luid
[INSN_UID (insn
)])
7619 REGNO_LAST_UID (REGNO (x
)) = INSN_UID (insn
);
7623 register char *fmt
= GET_RTX_FORMAT (GET_CODE (x
));
7624 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
7627 update_reg_last_use (XEXP (x
, i
), insn
);
7628 else if (fmt
[i
] == 'E')
7629 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7630 update_reg_last_use (XVECEXP (x
, i
, j
), insn
);
7635 /* Given a jump insn JUMP, return the condition that will cause it to branch
7636 to its JUMP_LABEL. If the condition cannot be understood, or is an
7637 inequality floating-point comparison which needs to be reversed, 0 will
7640 If EARLIEST is non-zero, it is a pointer to a place where the earliest
7641 insn used in locating the condition was found. If a replacement test
7642 of the condition is desired, it should be placed in front of that
7643 insn and we will be sure that the inputs are still valid.
7645 The condition will be returned in a canonical form to simplify testing by
7646 callers. Specifically:
7648 (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
7649 (2) Both operands will be machine operands; (cc0) will have been replaced.
7650 (3) If an operand is a constant, it will be the second operand.
7651 (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
7652 for GE, GEU, and LEU. */
7655 get_condition (jump
, earliest
)
7664 int reverse_code
= 0;
7665 int did_reverse_condition
= 0;
7666 enum machine_mode mode
;
7668 /* If this is not a standard conditional jump, we can't parse it. */
7669 if (GET_CODE (jump
) != JUMP_INSN
7670 || ! condjump_p (jump
) || simplejump_p (jump
))
7673 code
= GET_CODE (XEXP (SET_SRC (PATTERN (jump
)), 0));
7674 mode
= GET_MODE (XEXP (SET_SRC (PATTERN (jump
)), 0));
7675 op0
= XEXP (XEXP (SET_SRC (PATTERN (jump
)), 0), 0);
7676 op1
= XEXP (XEXP (SET_SRC (PATTERN (jump
)), 0), 1);
7681 /* If this branches to JUMP_LABEL when the condition is false, reverse
7683 if (GET_CODE (XEXP (SET_SRC (PATTERN (jump
)), 2)) == LABEL_REF
7684 && XEXP (XEXP (SET_SRC (PATTERN (jump
)), 2), 0) == JUMP_LABEL (jump
))
7685 code
= reverse_condition (code
), did_reverse_condition
^= 1;
7687 /* If we are comparing a register with zero, see if the register is set
7688 in the previous insn to a COMPARE or a comparison operation. Perform
7689 the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
7692 while (GET_RTX_CLASS (code
) == '<' && op1
== CONST0_RTX (GET_MODE (op0
)))
7694 /* Set non-zero when we find something of interest. */
7698 /* If comparison with cc0, import actual comparison from compare
7702 if ((prev
= prev_nonnote_insn (prev
)) == 0
7703 || GET_CODE (prev
) != INSN
7704 || (set
= single_set (prev
)) == 0
7705 || SET_DEST (set
) != cc0_rtx
)
7708 op0
= SET_SRC (set
);
7709 op1
= CONST0_RTX (GET_MODE (op0
));
7715 /* If this is a COMPARE, pick up the two things being compared. */
7716 if (GET_CODE (op0
) == COMPARE
)
7718 op1
= XEXP (op0
, 1);
7719 op0
= XEXP (op0
, 0);
7722 else if (GET_CODE (op0
) != REG
)
7725 /* Go back to the previous insn. Stop if it is not an INSN. We also
7726 stop if it isn't a single set or if it has a REG_INC note because
7727 we don't want to bother dealing with it. */
7729 if ((prev
= prev_nonnote_insn (prev
)) == 0
7730 || GET_CODE (prev
) != INSN
7731 || FIND_REG_INC_NOTE (prev
, 0)
7732 || (set
= single_set (prev
)) == 0)
7735 /* If this is setting OP0, get what it sets it to if it looks
7737 if (rtx_equal_p (SET_DEST (set
), op0
))
7739 enum machine_mode inner_mode
= GET_MODE (SET_SRC (set
));
7741 /* ??? We may not combine comparisons done in a CCmode with
7742 comparisons not done in a CCmode. This is to aid targets
7743 like Alpha that have an IEEE compliant EQ instruction, and
7744 a non-IEEE compliant BEQ instruction. The use of CCmode is
7745 actually artificial, simply to prevent the combination, but
7746 should not affect other platforms.
7748 However, we must allow VOIDmode comparisons to match either
7749 CCmode or non-CCmode comparison, because some ports have
7750 modeless comparisons inside branch patterns.
7752 ??? This mode check should perhaps look more like the mode check
7753 in simplify_comparison in combine. */
7755 if ((GET_CODE (SET_SRC (set
)) == COMPARE
7758 && GET_MODE_CLASS (inner_mode
) == MODE_INT
7759 && (GET_MODE_BITSIZE (inner_mode
)
7760 <= HOST_BITS_PER_WIDE_INT
)
7761 && (STORE_FLAG_VALUE
7762 & ((HOST_WIDE_INT
) 1
7763 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
7764 #ifdef FLOAT_STORE_FLAG_VALUE
7766 && GET_MODE_CLASS (inner_mode
) == MODE_FLOAT
7767 && FLOAT_STORE_FLAG_VALUE
< 0)
7770 && GET_RTX_CLASS (GET_CODE (SET_SRC (set
))) == '<'))
7771 && (((GET_MODE_CLASS (mode
) == MODE_CC
)
7772 == (GET_MODE_CLASS (inner_mode
) == MODE_CC
))
7773 || mode
== VOIDmode
|| inner_mode
== VOIDmode
))
7775 else if (((code
== EQ
7777 && (GET_MODE_BITSIZE (inner_mode
)
7778 <= HOST_BITS_PER_WIDE_INT
)
7779 && GET_MODE_CLASS (inner_mode
) == MODE_INT
7780 && (STORE_FLAG_VALUE
7781 & ((HOST_WIDE_INT
) 1
7782 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
7783 #ifdef FLOAT_STORE_FLAG_VALUE
7785 && GET_MODE_CLASS (inner_mode
) == MODE_FLOAT
7786 && FLOAT_STORE_FLAG_VALUE
< 0)
7789 && GET_RTX_CLASS (GET_CODE (SET_SRC (set
))) == '<'
7790 && (((GET_MODE_CLASS (mode
) == MODE_CC
)
7791 == (GET_MODE_CLASS (inner_mode
) == MODE_CC
))
7792 || mode
== VOIDmode
|| inner_mode
== VOIDmode
))
7795 /* We might have reversed a LT to get a GE here. But this wasn't
7796 actually the comparison of data, so we don't flag that we
7797 have had to reverse the condition. */
7798 did_reverse_condition
^= 1;
7806 else if (reg_set_p (op0
, prev
))
7807 /* If this sets OP0, but not directly, we have to give up. */
7812 if (GET_RTX_CLASS (GET_CODE (x
)) == '<')
7813 code
= GET_CODE (x
);
7816 code
= reverse_condition (code
);
7817 did_reverse_condition
^= 1;
7821 op0
= XEXP (x
, 0), op1
= XEXP (x
, 1);
7827 /* If constant is first, put it last. */
7828 if (CONSTANT_P (op0
))
7829 code
= swap_condition (code
), tem
= op0
, op0
= op1
, op1
= tem
;
7831 /* If OP0 is the result of a comparison, we weren't able to find what
7832 was really being compared, so fail. */
7833 if (GET_MODE_CLASS (GET_MODE (op0
)) == MODE_CC
)
7836 /* Canonicalize any ordered comparison with integers involving equality
7837 if we can do computations in the relevant mode and we do not
7840 if (GET_CODE (op1
) == CONST_INT
7841 && GET_MODE (op0
) != VOIDmode
7842 && GET_MODE_BITSIZE (GET_MODE (op0
)) <= HOST_BITS_PER_WIDE_INT
)
7844 HOST_WIDE_INT const_val
= INTVAL (op1
);
7845 unsigned HOST_WIDE_INT uconst_val
= const_val
;
7846 unsigned HOST_WIDE_INT max_val
7847 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (GET_MODE (op0
));
7852 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
7853 code
= LT
, op1
= GEN_INT (const_val
+ 1);
7856 /* When cross-compiling, const_val might be sign-extended from
7857 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
7859 if ((HOST_WIDE_INT
) (const_val
& max_val
)
7860 != (((HOST_WIDE_INT
) 1
7861 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
7862 code
= GT
, op1
= GEN_INT (const_val
- 1);
7866 if (uconst_val
< max_val
)
7867 code
= LTU
, op1
= GEN_INT (uconst_val
+ 1);
7871 if (uconst_val
!= 0)
7872 code
= GTU
, op1
= GEN_INT (uconst_val
- 1);
7880 /* If this was floating-point and we reversed anything other than an
7881 EQ or NE, return zero. */
7882 if (TARGET_FLOAT_FORMAT
== IEEE_FLOAT_FORMAT
7883 && did_reverse_condition
&& code
!= NE
&& code
!= EQ
7885 && GET_MODE_CLASS (GET_MODE (op0
)) == MODE_FLOAT
)
7889 /* Never return CC0; return zero instead. */
7894 return gen_rtx_fmt_ee (code
, VOIDmode
, op0
, op1
);
7897 /* Similar to above routine, except that we also put an invariant last
7898 unless both operands are invariants. */
7901 get_condition_for_loop (x
)
7904 rtx comparison
= get_condition (x
, NULL_PTR
);
7907 || ! invariant_p (XEXP (comparison
, 0))
7908 || invariant_p (XEXP (comparison
, 1)))
7911 return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison
)), VOIDmode
,
7912 XEXP (comparison
, 1), XEXP (comparison
, 0));
7915 #ifdef HAVE_decrement_and_branch_on_count
7916 /* Instrument loop for insertion of bct instruction. We distinguish between
7917 loops with compile-time bounds and those with run-time bounds.
7918 Information from loop_iterations() is used to compute compile-time bounds.
7919 Run-time bounds should use loop preconditioning, but currently ignored.
7923 insert_bct (loop_start
, loop_end
, loop_info
)
7924 rtx loop_start
, loop_end
;
7925 struct loop_info
*loop_info
;
7928 unsigned HOST_WIDE_INT n_iterations
;
7931 int increment_direction
, compare_direction
;
7933 /* If the loop condition is <= or >=, the number of iteration
7934 is 1 more than the range of the bounds of the loop. */
7935 int add_iteration
= 0;
7937 enum machine_mode loop_var_mode
= word_mode
;
7940 int loop_num
= uid_loop_num
[INSN_UID (loop_start
)];
7942 /* It's impossible to instrument a competely unrolled loop. */
7943 if (loop_info
->unroll_number
== -1)
7946 /* Make sure that the count register is not in use. */
7947 if (loop_used_count_register
[loop_num
])
7949 if (loop_dump_stream
)
7950 fprintf (loop_dump_stream
,
7951 "insert_bct %d: BCT instrumentation failed: count register already in use\n",
7956 /* Make sure that the function has no indirect jumps. */
7957 if (indirect_jump_in_function
)
7959 if (loop_dump_stream
)
7960 fprintf (loop_dump_stream
,
7961 "insert_bct %d: BCT instrumentation failed: indirect jump in function\n",
7966 /* Make sure that the last loop insn is a conditional jump. */
7967 if (GET_CODE (PREV_INSN (loop_end
)) != JUMP_INSN
7968 || ! condjump_p (PREV_INSN (loop_end
))
7969 || simplejump_p (PREV_INSN (loop_end
)))
7971 if (loop_dump_stream
)
7972 fprintf (loop_dump_stream
,
7973 "insert_bct %d: BCT instrumentation failed: invalid jump at loop end\n",
7978 /* Make sure that the loop does not contain a function call
7979 (the count register might be altered by the called function). */
7982 if (loop_dump_stream
)
7983 fprintf (loop_dump_stream
,
7984 "insert_bct %d: BCT instrumentation failed: function call in loop\n",
7989 /* Make sure that the loop does not jump via a table.
7990 (the count register might be used to perform the branch on table). */
7991 if (loop_has_tablejump
)
7993 if (loop_dump_stream
)
7994 fprintf (loop_dump_stream
,
7995 "insert_bct %d: BCT instrumentation failed: computed branch in the loop\n",
8000 /* Account for loop unrolling in instrumented iteration count. */
8001 if (loop_info
->unroll_number
> 1)
8002 n_iterations
= loop_info
->n_iterations
/ loop_info
->unroll_number
;
8004 n_iterations
= loop_info
->n_iterations
;
8006 if (n_iterations
!= 0 && n_iterations
< 3)
8008 /* Allow an enclosing outer loop to benefit if possible. */
8009 if (loop_dump_stream
)
8010 fprintf (loop_dump_stream
,
8011 "insert_bct %d: Too few iterations to benefit from BCT optimization\n",
8016 /* Try to instrument the loop. */
8018 /* Handle the simpler case, where the bounds are known at compile time. */
8019 if (n_iterations
> 0)
8021 /* Mark all enclosing loops that they cannot use count register. */
8022 for (i
= loop_num
; i
!= -1; i
= loop_outer_loop
[i
])
8023 loop_used_count_register
[i
] = 1;
8024 instrument_loop_bct (loop_start
, loop_end
, GEN_INT (n_iterations
));
8028 /* Handle the more complex case, that the bounds are NOT known
8029 at compile time. In this case we generate run_time calculation
8030 of the number of iterations. */
8032 if (loop_info
->iteration_var
== 0)
8034 if (loop_dump_stream
)
8035 fprintf (loop_dump_stream
,
8036 "insert_bct %d: BCT Runtime Instrumentation failed: no loop iteration variable found\n",
8041 if (GET_MODE_CLASS (GET_MODE (loop_info
->iteration_var
)) != MODE_INT
8042 || GET_MODE_SIZE (GET_MODE (loop_info
->iteration_var
)) != UNITS_PER_WORD
)
8044 if (loop_dump_stream
)
8045 fprintf (loop_dump_stream
,
8046 "insert_bct %d: BCT Runtime Instrumentation failed: loop variable not integer\n",
8051 /* With runtime bounds, if the compare is of the form '!=' we give up */
8052 if (loop_info
->comparison_code
== NE
)
8054 if (loop_dump_stream
)
8055 fprintf (loop_dump_stream
,
8056 "insert_bct %d: BCT Runtime Instrumentation failed: runtime bounds with != comparison\n",
8060 /* Use common loop preconditioning code instead. */
8064 /* We rely on the existence of run-time guard to ensure that the
8065 loop executes at least once. */
8067 rtx iterations_num_reg
;
8069 unsigned HOST_WIDE_INT increment_value_abs
8070 = INTVAL (increment
) * increment_direction
;
8072 /* make sure that the increment is a power of two, otherwise (an
8073 expensive) divide is needed. */
8074 if (exact_log2 (increment_value_abs
) == -1)
8076 if (loop_dump_stream
)
8077 fprintf (loop_dump_stream
,
8078 "insert_bct: not instrumenting BCT because the increment is not power of 2\n");
8082 /* compute the number of iterations */
8087 /* Again, the number of iterations is calculated by:
8089 ; compare-val - initial-val + (increment -1) + additional-iteration
8090 ; num_iterations = -----------------------------------------------------------------
8093 /* ??? Do we have to call copy_rtx here before passing rtx to
8095 if (compare_direction
> 0)
8097 /* <, <= :the loop variable is increasing */
8098 temp_reg
= expand_binop (loop_var_mode
, sub_optab
,
8099 comparison_value
, initial_value
,
8100 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
8104 temp_reg
= expand_binop (loop_var_mode
, sub_optab
,
8105 initial_value
, comparison_value
,
8106 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
8109 if (increment_value_abs
- 1 + add_iteration
!= 0)
8110 temp_reg
= expand_binop (loop_var_mode
, add_optab
, temp_reg
,
8111 GEN_INT (increment_value_abs
- 1
8113 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
8115 if (increment_value_abs
!= 1)
8117 /* ??? This will generate an expensive divide instruction for
8118 most targets. The original authors apparently expected this
8119 to be a shift, since they test for power-of-2 divisors above,
8120 but just naively generating a divide instruction will not give
8121 a shift. It happens to work for the PowerPC target because
8122 the rs6000.md file has a divide pattern that emits shifts.
8123 It will probably not work for any other target. */
8124 iterations_num_reg
= expand_binop (loop_var_mode
, sdiv_optab
,
8126 GEN_INT (increment_value_abs
),
8127 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
8130 iterations_num_reg
= temp_reg
;
8132 sequence
= gen_sequence ();
8134 emit_insn_before (sequence
, loop_start
);
8135 instrument_loop_bct (loop_start
, loop_end
, iterations_num_reg
);
8139 #endif /* Complex case */
8142 /* Instrument loop by inserting a bct in it as follows:
8143 1. A new counter register is created.
8144 2. In the head of the loop the new variable is initialized to the value
8145 passed in the loop_num_iterations parameter.
8146 3. At the end of the loop, comparison of the register with 0 is generated.
8147 The created comparison follows the pattern defined for the
8148 decrement_and_branch_on_count insn, so this insn will be generated.
8149 4. The branch on the old variable are deleted. The compare must remain
8150 because it might be used elsewhere. If the loop-variable or condition
8151 register are used elsewhere, they will be eliminated by flow. */
8154 instrument_loop_bct (loop_start
, loop_end
, loop_num_iterations
)
8155 rtx loop_start
, loop_end
;
8156 rtx loop_num_iterations
;
8162 if (HAVE_decrement_and_branch_on_count
)
8164 if (loop_dump_stream
)
8166 fputs ("instrument_bct: Inserting BCT (", loop_dump_stream
);
8167 if (GET_CODE (loop_num_iterations
) == CONST_INT
)
8168 fprintf (loop_dump_stream
, HOST_WIDE_INT_PRINT_DEC
,
8169 INTVAL (loop_num_iterations
));
8171 fputs ("runtime", loop_dump_stream
);
8172 fputs (" iterations)", loop_dump_stream
);
8175 /* Discard original jump to continue loop. Original compare result
8176 may still be live, so it cannot be discarded explicitly. */
8177 delete_insn (PREV_INSN (loop_end
));
8179 /* Insert the label which will delimit the start of the loop. */
8180 start_label
= gen_label_rtx ();
8181 emit_label_after (start_label
, loop_start
);
8183 /* Insert initialization of the count register into the loop header. */
8185 counter_reg
= gen_reg_rtx (word_mode
);
8186 emit_insn (gen_move_insn (counter_reg
, loop_num_iterations
));
8187 sequence
= gen_sequence ();
8189 emit_insn_before (sequence
, loop_start
);
8191 /* Insert new comparison on the count register instead of the
8192 old one, generating the needed BCT pattern (that will be
8193 later recognized by assembly generation phase). */
8194 emit_jump_insn_before (gen_decrement_and_branch_on_count (counter_reg
,
8197 LABEL_NUSES (start_label
)++;
8201 #endif /* HAVE_decrement_and_branch_on_count */
8203 /* Scan the function and determine whether it has indirect (computed) jumps.
8205 This is taken mostly from flow.c; similar code exists elsewhere
8206 in the compiler. It may be useful to put this into rtlanal.c. */
8208 indirect_jump_in_function_p (start
)
8213 for (insn
= start
; insn
; insn
= NEXT_INSN (insn
))
8214 if (computed_jump_p (insn
))
8220 /* Add MEM to the LOOP_MEMS array, if appropriate. See the
8221 documentation for LOOP_MEMS for the definition of `appropriate'.
8222 This function is called from prescan_loop via for_each_rtx. */
8225 insert_loop_mem (mem
, data
)
8227 void *data ATTRIBUTE_UNUSED
;
8235 switch (GET_CODE (m
))
8241 /* We're not interested in the MEM associated with a
8242 CONST_DOUBLE, so there's no need to traverse into this. */
8246 /* This is not a MEM. */
8250 /* See if we've already seen this MEM. */
8251 for (i
= 0; i
< loop_mems_idx
; ++i
)
8252 if (rtx_equal_p (m
, loop_mems
[i
].mem
))
8254 if (GET_MODE (m
) != GET_MODE (loop_mems
[i
].mem
))
8255 /* The modes of the two memory accesses are different. If
8256 this happens, something tricky is going on, and we just
8257 don't optimize accesses to this MEM. */
8258 loop_mems
[i
].optimize
= 0;
8263 /* Resize the array, if necessary. */
8264 if (loop_mems_idx
== loop_mems_allocated
)
8266 if (loop_mems_allocated
!= 0)
8267 loop_mems_allocated
*= 2;
8269 loop_mems_allocated
= 32;
8271 loop_mems
= (loop_mem_info
*)
8272 xrealloc (loop_mems
,
8273 loop_mems_allocated
* sizeof (loop_mem_info
));
8276 /* Actually insert the MEM. */
8277 loop_mems
[loop_mems_idx
].mem
= m
;
8278 /* We can't hoist this MEM out of the loop if it's a BLKmode MEM
8279 because we can't put it in a register. We still store it in the
8280 table, though, so that if we see the same address later, but in a
8281 non-BLK mode, we'll not think we can optimize it at that point. */
8282 loop_mems
[loop_mems_idx
].optimize
= (GET_MODE (m
) != BLKmode
);
8283 loop_mems
[loop_mems_idx
].reg
= NULL_RTX
;
8289 /* Like load_mems, but also ensures that SET_IN_LOOP,
8290 MAY_NOT_OPTIMIZE, REG_SINGLE_USAGE, and INSN_COUNT have the correct
8291 values after load_mems. */
8294 load_mems_and_recount_loop_regs_set (scan_start
, end
, loop_top
, start
,
8295 reg_single_usage
, insn_count
)
8300 varray_type reg_single_usage
;
8303 int nregs
= max_reg_num ();
8305 load_mems (scan_start
, end
, loop_top
, start
);
8307 /* Recalculate set_in_loop and friends since load_mems may have
8308 created new registers. */
8309 if (max_reg_num () > nregs
)
8315 nregs
= max_reg_num ();
8317 if ((unsigned) nregs
> set_in_loop
->num_elements
)
8319 /* Grow all the arrays. */
8320 VARRAY_GROW (set_in_loop
, nregs
);
8321 VARRAY_GROW (n_times_set
, nregs
);
8322 VARRAY_GROW (may_not_optimize
, nregs
);
8323 if (reg_single_usage
)
8324 VARRAY_GROW (reg_single_usage
, nregs
);
8326 /* Clear the arrays */
8327 bzero ((char *) &set_in_loop
->data
, nregs
* sizeof (int));
8328 bzero ((char *) &may_not_optimize
->data
, nregs
* sizeof (char));
8329 if (reg_single_usage
)
8330 bzero ((char *) ®_single_usage
->data
, nregs
* sizeof (rtx
));
8332 count_loop_regs_set (loop_top
? loop_top
: start
, end
,
8333 may_not_optimize
, reg_single_usage
,
8336 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
8338 VARRAY_CHAR (may_not_optimize
, i
) = 1;
8339 VARRAY_INT (set_in_loop
, i
) = 1;
8342 #ifdef AVOID_CCMODE_COPIES
8343 /* Don't try to move insns which set CC registers if we should not
8344 create CCmode register copies. */
8345 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
8346 if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx
[i
])) == MODE_CC
)
8347 VARRAY_CHAR (may_not_optimize
, i
) = 1;
8350 /* Set n_times_set for the new registers. */
8351 bcopy ((char *) (&set_in_loop
->data
.i
[0] + old_nregs
),
8352 (char *) (&n_times_set
->data
.i
[0] + old_nregs
),
8353 (nregs
- old_nregs
) * sizeof (int));
8357 /* Move MEMs into registers for the duration of the loop. SCAN_START
8358 is the first instruction in the loop (as it is executed). The
8359 other parameters are as for next_insn_in_loop. */
8362 load_mems (scan_start
, end
, loop_top
, start
)
8368 int maybe_never
= 0;
8371 rtx label
= NULL_RTX
;
8374 if (loop_mems_idx
> 0)
8376 /* Nonzero if the next instruction may never be executed. */
8377 int next_maybe_never
= 0;
8379 /* Check to see if it's possible that some instructions in the
8380 loop are never executed. */
8381 for (p
= next_insn_in_loop (scan_start
, scan_start
, end
, loop_top
);
8382 p
!= NULL_RTX
&& !maybe_never
;
8383 p
= next_insn_in_loop (p
, scan_start
, end
, loop_top
))
8385 if (GET_CODE (p
) == CODE_LABEL
)
8387 else if (GET_CODE (p
) == JUMP_INSN
8388 /* If we enter the loop in the middle, and scan
8389 around to the beginning, don't set maybe_never
8390 for that. This must be an unconditional jump,
8391 otherwise the code at the top of the loop might
8392 never be executed. Unconditional jumps are
8393 followed a by barrier then loop end. */
8394 && ! (GET_CODE (p
) == JUMP_INSN
8395 && JUMP_LABEL (p
) == loop_top
8396 && NEXT_INSN (NEXT_INSN (p
)) == end
8397 && simplejump_p (p
)))
8399 if (!condjump_p (p
))
8400 /* Something complicated. */
8403 /* If there are any more instructions in the loop, they
8404 might not be reached. */
8405 next_maybe_never
= 1;
8407 else if (next_maybe_never
)
8411 /* Actually move the MEMs. */
8412 for (i
= 0; i
< loop_mems_idx
; ++i
)
8416 rtx mem
= loop_mems
[i
].mem
;
8419 if (MEM_VOLATILE_P (mem
)
8420 || invariant_p (XEXP (mem
, 0)) != 1)
8421 /* There's no telling whether or not MEM is modified. */
8422 loop_mems
[i
].optimize
= 0;
8424 /* Go through the MEMs written to in the loop to see if this
8425 one is aliased by one of them. */
8426 mem_list_entry
= loop_store_mems
;
8427 while (mem_list_entry
)
8429 if (rtx_equal_p (mem
, XEXP (mem_list_entry
, 0)))
8431 else if (true_dependence (XEXP (mem_list_entry
, 0), VOIDmode
,
8434 /* MEM is indeed aliased by this store. */
8435 loop_mems
[i
].optimize
= 0;
8438 mem_list_entry
= XEXP (mem_list_entry
, 1);
8441 /* If this MEM is written to, we must be sure that there
8442 are no reads from another MEM that aliases this one. */
8443 if (loop_mems
[i
].optimize
&& written
)
8447 for (j
= 0; j
< loop_mems_idx
; ++j
)
8451 else if (true_dependence (mem
,
8456 /* It's not safe to hoist loop_mems[i] out of
8457 the loop because writes to it might not be
8458 seen by reads from loop_mems[j]. */
8459 loop_mems
[i
].optimize
= 0;
8465 if (maybe_never
&& may_trap_p (mem
))
8466 /* We can't access the MEM outside the loop; it might
8467 cause a trap that wouldn't have happened otherwise. */
8468 loop_mems
[i
].optimize
= 0;
8470 if (!loop_mems
[i
].optimize
)
8471 /* We thought we were going to lift this MEM out of the
8472 loop, but later discovered that we could not. */
8475 /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
8476 order to keep scan_loop from moving stores to this MEM
8477 out of the loop just because this REG is neither a
8478 user-variable nor used in the loop test. */
8479 reg
= gen_reg_rtx (GET_MODE (mem
));
8480 REG_USERVAR_P (reg
) = 1;
8481 loop_mems
[i
].reg
= reg
;
8483 /* Now, replace all references to the MEM with the
8484 corresponding pesudos. */
8485 for (p
= next_insn_in_loop (scan_start
, scan_start
, end
, loop_top
);
8487 p
= next_insn_in_loop (p
, scan_start
, end
, loop_top
))
8492 for_each_rtx (&p
, replace_loop_mem
, &ri
);
8495 if (!apply_change_group ())
8496 /* We couldn't replace all occurrences of the MEM. */
8497 loop_mems
[i
].optimize
= 0;
8502 /* Load the memory immediately before START, which is
8503 the NOTE_LOOP_BEG. */
8504 set
= gen_rtx_SET (GET_MODE (reg
), reg
, mem
);
8505 emit_insn_before (set
, start
);
8509 if (label
== NULL_RTX
)
8511 /* We must compute the former
8512 right-after-the-end label before we insert
8514 end_label
= next_label (end
);
8515 label
= gen_label_rtx ();
8516 emit_label_after (label
, end
);
8519 /* Store the memory immediately after END, which is
8520 the NOTE_LOOP_END. */
8521 set
= gen_rtx_SET (GET_MODE (reg
), copy_rtx (mem
), reg
);
8522 emit_insn_after (set
, label
);
8525 if (loop_dump_stream
)
8527 fprintf (loop_dump_stream
, "Hoisted regno %d %s from ",
8528 REGNO (reg
), (written
? "r/w" : "r/o"));
8529 print_rtl (loop_dump_stream
, mem
);
8530 fputc ('\n', loop_dump_stream
);
8536 if (label
!= NULL_RTX
)
8538 /* Now, we need to replace all references to the previous exit
8539 label with the new one. */
8544 for (p
= start
; p
!= end
; p
= NEXT_INSN (p
))
8546 for_each_rtx (&p
, replace_label
, &rr
);
8548 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
8549 field. This is not handled by for_each_rtx because it doesn't
8550 handle unprinted ('0') fields. We need to update JUMP_LABEL
8551 because the immediately following unroll pass will use it.
8552 replace_label would not work anyways, because that only handles
8554 if (GET_CODE (p
) == JUMP_INSN
&& JUMP_LABEL (p
) == end_label
)
8555 JUMP_LABEL (p
) = label
;
8560 /* Replace MEM with its associated pseudo register. This function is
8561 called from load_mems via for_each_rtx. DATA is actually an
8562 rtx_and_int * describing the instruction currently being scanned
8563 and the MEM we are currently replacing. */
8566 replace_loop_mem (mem
, data
)
8578 switch (GET_CODE (m
))
8584 /* We're not interested in the MEM associated with a
8585 CONST_DOUBLE, so there's no need to traverse into one. */
8589 /* This is not a MEM. */
8593 ri
= (rtx_and_int
*) data
;
8596 if (!rtx_equal_p (loop_mems
[i
].mem
, m
))
8597 /* This is not the MEM we are currently replacing. */
8602 /* Actually replace the MEM. */
8603 validate_change (insn
, mem
, loop_mems
[i
].reg
, 1);
8608 /* Replace occurrences of the old exit label for the loop with the new
8609 one. DATA is an rtx_pair containing the old and new labels,
8613 replace_label (x
, data
)
8618 rtx old_label
= ((rtx_pair
*) data
)->r1
;
8619 rtx new_label
= ((rtx_pair
*) data
)->r2
;
8624 if (GET_CODE (l
) != LABEL_REF
)
8627 if (XEXP (l
, 0) != old_label
)
8630 XEXP (l
, 0) = new_label
;
8631 ++LABEL_NUSES (new_label
);
8632 --LABEL_NUSES (old_label
);