![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to loop.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to loop.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Move constant computations out of loops.
2: Copyright (C) 1987, 1988, 1989, 1991 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
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)
9: any later version.
10:
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.
15:
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, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* This is the loop optimization pass of the compiler.
22: It finds invariant computations within loops and moves them
23: to the beginning of the loop. Then it identifies basic and
24: general induction variables. Strength reduction is applied to the general
25: induction variables, and induction variable elimination is applied to
26: the basic induction variables.
27:
28: It also finds cases where
29: a register is set within the loop by zero-extending a narrower value
30: and changes these to zero the entire register once before the loop
31: and merely copy the low part within the loop.
32:
33: Most of the complexity is in heuristics to decide when it is worth
34: while to do these things. */
35:
36: #include "config.h"
37: #include "rtl.h"
38: #include "obstack.h"
39: #include "expr.h"
40: #include "insn-config.h"
41: #include "insn-flags.h"
42: #include "regs.h"
43: #include "hard-reg-set.h"
44: #include "recog.h"
45: #include "flags.h"
46: #include "real.h"
47: #include <stdio.h>
48: #include "loop.h"
49:
50: /* Vector mapping INSN_UIDs to luids.
1.1.1.2 root 51: The luids are like uids but increase monotonically always.
1.1 root 52: We use them to see whether a jump comes from outside a given loop. */
53:
54: int *uid_luid;
55:
56: /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
57: number the insn is contained in. */
58:
59: int *uid_loop_num;
60:
61: /* 1 + largest uid of any insn. */
62:
63: int max_uid_for_loop;
64:
65: /* 1 + luid of last insn. */
66:
67: static int max_luid;
68:
69: /* Number of loops detected in current function. Used as index to the
70: next few tables. */
71:
72: static int max_loop_num;
73:
74: /* Indexed by loop number, contains the first and last insn of each loop. */
75:
76: static rtx *loop_number_loop_starts, *loop_number_loop_ends;
77:
78: /* For each loop, gives the containing loop number, -1 if none. */
79:
80: int *loop_outer_loop;
81:
82: /* Indexed by loop number, contains a nonzero value if the "loop" isn't
83: really a loop (an insn outside the loop branches into it). */
84:
85: static char *loop_invalid;
86:
87: /* Indexed by loop number, links together all LABEL_REFs which refer to
88: code labels outside the loop. Used by routines that need to know all
89: loop exits, such as final_biv_value and final_giv_value.
90:
91: This does not include loop exits due to return instructions. This is
92: because all bivs and givs are pseudos, and hence must be dead after a
93: return, so the presense of a return does not affect any of the
94: optimizations that use this info. It is simpler to just not include return
95: instructions on this list. */
96:
97: rtx *loop_number_exit_labels;
98:
99: /* Holds the number of loop iterations. It is zero if the number could not be
100: calculated. Must be unsigned long since the number of iterations can
101: be as high as 2^31-1. For loops with a DImode iterator, this number will
102: will be zero if the number of loop iterations is too large for an
103: unsigned long to hold. */
104:
105: unsigned long loop_n_iterations;
106:
107: /* Nonzero if there is a subroutine call in the current loop.
108: (unknown_address_altered is also nonzero in this case.) */
109:
110: static int loop_has_call;
111:
1.1.1.3 ! root 112: /* Nonzero if there is a volatile memory reference in the current
! 113: loop. */
! 114:
! 115: static int loop_has_volatile;
! 116:
1.1 root 117: /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
118: current loop. A continue statement will generate a branch to
119: NEXT_INSN (loop_continue). */
120:
121: static rtx loop_continue;
122:
123: /* Indexed by register number, contains the number of times the reg
124: is set during the loop being scanned.
125: During code motion, a negative value indicates a reg that has been
126: made a candidate; in particular -2 means that it is an candidate that
1.1.1.3 ! root 127: we know is equal to a constant and -1 means that it is an candidate
1.1 root 128: not known equal to a constant.
129: After code motion, regs moved have 0 (which is accurate now)
130: while the failed candidates have the original number of times set.
131:
132: Therefore, at all times, == 0 indicates an invariant register;
133: < 0 a conditionally invariant one. */
134:
135: static short *n_times_set;
136:
137: /* Original value of n_times_set; same except that this value
138: is not set negative for a reg whose sets have been made candidates
139: and not set to 0 for a reg that is moved. */
140:
141: static short *n_times_used;
142:
143: /* Index by register number, 1 indicates that the register
144: cannot be moved or strength reduced. */
145:
146: static char *may_not_optimize;
147:
148: /* Nonzero means reg N has already been moved out of one loop.
149: This reduces the desire to move it out of another. */
150:
151: static char *moved_once;
152:
153: /* Array of MEMs that are stored in this loop. If there are too many to fit
154: here, we just turn on unknown_address_altered. */
155:
156: #define NUM_STORES 20
157: static rtx loop_store_mems[NUM_STORES];
158:
159: /* Index of first available slot in above array. */
160: static int loop_store_mems_idx;
161:
162: /* Nonzero if we don't know what MEMs were changed in the current loop.
1.1.1.3 ! root 163: This happens if the loop contains a call (in which case `loop_has_call'
1.1 root 164: will also be set) or if we store into more than NUM_STORES MEMs. */
165:
166: static int unknown_address_altered;
167:
168: /* Count of movable (i.e. invariant) instructions discovered in the loop. */
169: static int num_movables;
170:
171: /* Count of memory write instructions discovered in the loop. */
172: static int num_mem_sets;
173:
174: /* Number of loops contained within the current one, including itself. */
175: static int loops_enclosed;
176:
177: /* Bound on pseudo register number before loop optimization.
178: A pseudo has valid regscan info if its number is < max_reg_before_loop. */
179: int max_reg_before_loop;
180:
181: /* This obstack is used in product_cheap_p to allocate its rtl. It
182: may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
183: If we used the same obstack that it did, we would be deallocating
184: that array. */
185:
186: static struct obstack temp_obstack;
187:
188: /* This is where the pointer to the obstack being used for RTL is stored. */
189:
190: extern struct obstack *rtl_obstack;
191:
192: #define obstack_chunk_alloc xmalloc
193: #define obstack_chunk_free free
194:
195: extern char *oballoc ();
196: extern int xmalloc ();
197: extern void free ();
198:
199: /* During the analysis of a loop, a chain of `struct movable's
200: is made to record all the movable insns found.
201: Then the entire chain can be scanned to decide which to move. */
202:
203: struct movable
204: {
205: rtx insn; /* A movable insn */
206: rtx set_src; /* The expression this reg is set from. */
207: rtx set_dest; /* The destination of this SET. */
208: rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
209: of any registers used within the LIBCALL. */
210: int consec; /* Number of consecutive following insns
211: that must be moved with this one. */
212: int regno; /* The register it sets */
213: short lifetime; /* lifetime of that register;
214: may be adjusted when matching movables
215: that load the same value are found. */
216: short savings; /* Number of insns we can move for this reg,
217: including other movables that force this
218: or match this one. */
219: unsigned int cond : 1; /* 1 if only conditionally movable */
220: unsigned int force : 1; /* 1 means MUST move this insn */
221: unsigned int global : 1; /* 1 means reg is live outside this loop */
222: /* If PARTIAL is 1, GLOBAL means something different:
223: that the reg is live outside the range from where it is set
224: to the following label. */
225: unsigned int done : 1; /* 1 inhibits further processing of this */
226:
227: unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
228: In particular, moving it does not make it
229: invariant. */
230: unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
231: load SRC, rather than copying INSN. */
232: unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
233: enum machine_mode savemode; /* Nonzero means it is a mode for a low part
234: that we should avoid changing when clearing
235: the rest of the reg. */
236: struct movable *match; /* First entry for same value */
237: struct movable *forces; /* An insn that must be moved if this is */
238: struct movable *next;
239: };
240:
241: FILE *loop_dump_stream;
242:
243: /* Forward declarations. */
244:
245: static void find_and_verify_loops ();
246: static void mark_loop_jump ();
247: static void prescan_loop ();
248: static int reg_in_basic_block_p ();
249: static int consec_sets_invariant_p ();
250: static rtx libcall_other_reg ();
251: static int labels_in_range_p ();
252: static void count_loop_regs_set ();
253: static void note_addr_stored ();
254: static int loop_reg_used_before_p ();
255: static void scan_loop ();
256: static void replace_call_address ();
257: static rtx skip_consec_insns ();
258: static int libcall_benefit ();
259: static void ignore_some_movables ();
260: static void force_movables ();
261: static void combine_movables ();
262: static int rtx_equal_for_loop_p ();
263: static void move_movables ();
264: static void strength_reduce ();
265: static int valid_initial_value_p ();
266: static void find_mem_givs ();
267: static void record_biv ();
268: static void check_final_value ();
269: static void record_giv ();
270: static void update_giv_derive ();
271: static void delete_insn_forces ();
272: static int basic_induction_var ();
273: static rtx simplify_giv_expr ();
274: static int general_induction_var ();
275: static int consec_sets_giv ();
276: static int check_dbra_loop ();
277: static rtx express_from ();
278: static int combine_givs_p ();
279: static void combine_givs ();
280: static int product_cheap_p ();
281: static int maybe_eliminate_biv ();
282: static int maybe_eliminate_biv_1 ();
283: static int last_use_this_basic_block ();
284: static void record_initial ();
285: static void update_reg_last_use ();
286:
287: /* Relative gain of eliminating various kinds of operations. */
288: int add_cost;
289: #if 0
290: int shift_cost;
291: int mult_cost;
292: #endif
293:
294: /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
295: copy the value of the strength reduced giv to its original register. */
296: int copy_cost;
297:
298: void
299: init_loop ()
300: {
301: char *free_point = (char *) oballoc (1);
302: rtx reg = gen_rtx (REG, SImode, 0);
303: rtx pow2 = gen_rtx (CONST_INT, VOIDmode, 32);
304: rtx lea;
305: int i;
306:
1.1.1.3 ! root 307: add_cost = rtx_cost (gen_rtx (PLUS, SImode, reg, reg), SET);
1.1 root 308:
309: /* We multiply by 2 to reconcile the difference in scale between
310: these two ways of computing costs. Otherwise the cost of a copy
311: will be far less than the cost of an add. */
312: #ifdef REGISTER_MOVE_COST
313: copy_cost = REGISTER_MOVE_COST (GENERAL_REGS, GENERAL_REGS) * 2;
314: #else
315: copy_cost = 2 * 2;
316: #endif
317:
318: /* Free the objects we just allocated. */
319: obfree (free_point);
320:
321: /* Initialize the obstack used for rtl in product_cheap_p. */
322: gcc_obstack_init (&temp_obstack);
323: }
324:
325: /* Entry point of this file. Perform loop optimization
326: on the current function. F is the first insn of the function
327: and DUMPFILE is a stream for output of a trace of actions taken
328: (or 0 if none should be output). */
329:
330: void
331: loop_optimize (f, dumpfile)
332: /* f is the first instruction of a chain of insns for one function */
333: rtx f;
334: FILE *dumpfile;
335: {
336: register rtx insn;
337: register int i;
338: rtx end;
339: rtx last_insn;
340:
341: loop_dump_stream = dumpfile;
342:
343: init_recog_no_volatile ();
344: init_alias_analysis ();
345:
346: max_reg_before_loop = max_reg_num ();
347:
348: moved_once = (char *) alloca (max_reg_before_loop);
349: bzero (moved_once, max_reg_before_loop);
350:
351: regs_may_share = 0;
352:
353: /* Count the number of loops. */
354:
355: max_loop_num = 0;
356: for (insn = f; insn; insn = NEXT_INSN (insn))
357: {
358: if (GET_CODE (insn) == NOTE
359: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
360: max_loop_num++;
361: }
362:
363: /* Don't waste time if no loops. */
364: if (max_loop_num == 0)
365: return;
366:
367: /* Get size to use for tables indexed by uids.
368: Leave some space for labels allocated by find_and_verify_loops. */
369: max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 4;
370:
371: uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int));
372: uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int));
373:
374: bzero (uid_luid, max_uid_for_loop * sizeof (int));
375: bzero (uid_loop_num, max_uid_for_loop * sizeof (int));
376:
377: /* Allocate tables for recording each loop. We set each entry, so they need
378: not be zeroed. */
379: loop_number_loop_starts = (rtx *) alloca (max_loop_num * sizeof (rtx));
380: loop_number_loop_ends = (rtx *) alloca (max_loop_num * sizeof (rtx));
381: loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
382: loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
383: loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
384:
385: if (flag_unroll_loops && write_symbols != NO_DEBUG)
386: {
387: loop_number_first_block
388: = (union tree_node **) alloca (max_loop_num
389: * sizeof (union tree_node *));
390: loop_number_last_block
391: = (union tree_node **) alloca (max_loop_num
392: * sizeof (union tree_node *));
393: loop_number_block_level = (int *) alloca (max_loop_num * sizeof (int));
394: }
395:
396: /* Find and process each loop.
397: First, find them, and record them in order of their beginnings. */
398: find_and_verify_loops (f);
399:
400: /* Now find all register lifetimes. This must be done after
401: find_and_verify_loops, because it might reorder the insns in the
402: function. */
403: reg_scan (f, max_reg_num (), 1);
404:
405: /* Compute the mapping from uids to luids.
406: LUIDs are numbers assigned to insns, like uids,
407: except that luids increase monotonically through the code.
408: Don't assign luids to line-number NOTEs, so that the distance in luids
409: between two insns is not affected by -g. */
410:
411: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
412: {
413: last_insn = insn;
414: if (GET_CODE (insn) != NOTE
415: || NOTE_LINE_NUMBER (insn) <= 0)
416: uid_luid[INSN_UID (insn)] = ++i;
417: else
418: /* Give a line number note the same luid as preceding insn. */
419: uid_luid[INSN_UID (insn)] = i;
420: }
421:
422: max_luid = i + 1;
423:
424: /* Don't leave gaps in uid_luid for insns that have been
425: deleted. It is possible that the first or last insn
426: using some register has been deleted by cross-jumping.
427: Make sure that uid_luid for that former insn's uid
428: points to the general area where that insn used to be. */
429: for (i = 0; i < max_uid_for_loop; i++)
430: {
431: uid_luid[0] = uid_luid[i];
432: if (uid_luid[0] != 0)
433: break;
434: }
435: for (i = 0; i < max_uid_for_loop; i++)
436: if (uid_luid[i] == 0)
437: uid_luid[i] = uid_luid[i - 1];
438:
439: /* Create a mapping from loops to BLOCK tree nodes. */
440: if (flag_unroll_loops && write_symbols != NO_DEBUG)
441: find_loop_tree_blocks (f);
442:
443: /* Now scan the loops, last ones first, since this means inner ones are done
444: before outer ones. */
445: for (i = max_loop_num-1; i >= 0; i--)
446: if (! loop_invalid[i] && loop_number_loop_ends[i])
447: scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i],
448: max_reg_num ());
449: }
450:
451: /* Optimize one loop whose start is LOOP_START and end is END.
452: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
453: NOTE_INSN_LOOP_END. */
454:
455: /* ??? Could also move memory writes out of loops if the destination address
456: is invariant, the source is invariant, the memory write is not volatile,
457: and if we can prove that no read inside the loop can read this address
458: before the write occurs. If there is a read of this address after the
459: write, then we can also mark the memory read as invariant. */
460:
461: static void
462: scan_loop (loop_start, end, nregs)
463: rtx loop_start, end;
464: int nregs;
465: {
466: register int i;
467: register rtx p;
468: /* 1 if we are scanning insns that could be executed zero times. */
469: int maybe_never = 0;
470: /* 1 if we are scanning insns that might never be executed
471: due to a subroutine call which might exit before they are reached. */
472: int call_passed = 0;
473: /* For a rotated loop that is entered near the bottom,
474: this is the label at the top. Otherwise it is zero. */
475: rtx loop_top = 0;
476: /* Jump insn that enters the loop, or 0 if control drops in. */
477: rtx loop_entry_jump = 0;
478: /* Place in the loop where control enters. */
479: rtx scan_start;
480: /* Number of insns in the loop. */
481: int insn_count;
482: int in_libcall = 0;
483: int tem;
484: rtx temp;
485: /* The SET from an insn, if it is the only SET in the insn. */
486: rtx set, set1;
487: /* Chain describing insns movable in current loop. */
488: struct movable *movables = 0;
489: /* Last element in `movables' -- so we can add elements at the end. */
490: struct movable *last_movable = 0;
491: /* Ratio of extra register life span we can justify
492: for saving an instruction. More if loop doesn't call subroutines
493: since in that case saving an insn makes more difference
494: and more registers are available. */
495: int threshold;
496: /* If we have calls, contains the insn in which a register was used
497: if it was used exactly once; contains const0_rtx if it was used more
498: than once. */
499: rtx *reg_single_usage = 0;
500:
501: n_times_set = (short *) alloca (nregs * sizeof (short));
502: n_times_used = (short *) alloca (nregs * sizeof (short));
503: may_not_optimize = (char *) alloca (nregs);
504:
505: /* Determine whether this loop starts with a jump down to a test at
506: the end. This will occur for a small number of loops with a test
507: that is too complex to duplicate in front of the loop.
508:
509: We search for the first insn or label in the loop, skipping NOTEs.
510: However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
511: (because we might have a loop executed only once that contains a
512: loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
513: (in case we have a degenerate loop).
514:
515: Note that if we mistakenly think that a loop is entered at the top
516: when, in fact, it is entered at the exit test, the only effect will be
517: slightly poorer optimization. Making the opposite error can generate
518: incorrect code. Since very few loops now start with a jump to the
519: exit test, the code here to detect that case is very conservative. */
520:
521: for (p = NEXT_INSN (loop_start);
522: p != end
523: && GET_CODE (p) != CODE_LABEL && GET_RTX_CLASS (GET_CODE (p)) != 'i'
524: && (GET_CODE (p) != NOTE
525: || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
526: && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
527: p = NEXT_INSN (p))
528: ;
529:
530: scan_start = p;
531:
532: /* Set up variables describing this loop. */
533: prescan_loop (loop_start, end);
534: threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);
535:
536: /* If loop has a jump before the first label,
537: the true entry is the target of that jump.
538: Start scan from there.
539: But record in LOOP_TOP the place where the end-test jumps
540: back to so we can scan that after the end of the loop. */
541: if (GET_CODE (p) == JUMP_INSN)
542: {
543: loop_entry_jump = p;
544:
545: /* Loop entry must be unconditional jump (and not a RETURN) */
546: if (simplejump_p (p)
547: && JUMP_LABEL (p) != 0
548: /* Check to see whether the jump actually
549: jumps out of the loop (meaning it's no loop).
550: This case can happen for things like
551: do {..} while (0). If this label was generated previously
552: by loop, we can't tell anything about it and have to reject
553: the loop. */
554: && INSN_UID (JUMP_LABEL (p)) < max_uid_for_loop
555: && INSN_LUID (JUMP_LABEL (p)) >= INSN_LUID (loop_start)
556: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (end))
557: {
558: loop_top = next_label (scan_start);
559: scan_start = JUMP_LABEL (p);
560: }
561: }
562:
563: /* If SCAN_START was an insn created by loop, we don't know its luid
564: as required by loop_reg_used_before_p. So skip such loops. (This
565: test may never be true, but it's best to play it safe.)
566:
567: Also, skip loops where we do not start scanning at a label. This
568: test also rejects loops starting with a JUMP_INSN that failed the
569: test above. */
570:
571: if (INSN_UID (scan_start) >= max_uid_for_loop
572: || GET_CODE (scan_start) != CODE_LABEL)
573: {
574: if (loop_dump_stream)
575: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
576: INSN_UID (loop_start), INSN_UID (end));
577: return;
578: }
579:
580: /* Count number of times each reg is set during this loop.
581: Set may_not_optimize[I] if it is not safe to move out
582: the setting of register I. If this loop has calls, set
583: reg_single_usage[I]. */
584:
585: bzero (n_times_set, nregs * sizeof (short));
586: bzero (may_not_optimize, nregs);
587:
588: if (loop_has_call)
589: {
590: reg_single_usage = (rtx *) alloca (nregs * sizeof (rtx));
591: bzero (reg_single_usage, nregs * sizeof (rtx));
592: }
593:
594: count_loop_regs_set (loop_top ? loop_top : loop_start, end,
595: may_not_optimize, reg_single_usage, &insn_count, nregs);
596:
597: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
598: may_not_optimize[i] = 1, n_times_set[i] = 1;
599: bcopy (n_times_set, n_times_used, nregs * sizeof (short));
600:
601: if (loop_dump_stream)
602: {
603: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
604: INSN_UID (loop_start), INSN_UID (end), insn_count);
605: if (loop_continue)
606: fprintf (loop_dump_stream, "Continue at insn %d.\n",
607: INSN_UID (loop_continue));
608: }
609:
610: /* Scan through the loop finding insns that are safe to move.
611: Set n_times_set negative for the reg being set, so that
612: this reg will be considered invariant for subsequent insns.
613: We consider whether subsequent insns use the reg
614: in deciding whether it is worth actually moving.
615:
616: MAYBE_NEVER is nonzero if we have passed a conditional jump insn
617: and therefore it is possible that the insns we are scanning
618: would never be executed. At such times, we must make sure
619: that it is safe to execute the insn once instead of zero times.
620: When MAYBE_NEVER is 0, all insns will be executed at least once
621: so that is not a problem. */
622:
623: p = scan_start;
624: while (1)
625: {
626: p = NEXT_INSN (p);
627: /* At end of a straight-in loop, we are done.
628: At end of a loop entered at the bottom, scan the top. */
629: if (p == scan_start)
630: break;
631: if (p == end)
632: {
633: if (loop_top != 0)
634: p = NEXT_INSN (loop_top);
635: else
636: break;
637: if (p == scan_start)
638: break;
639: }
640:
641: if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
642: && find_reg_note (p, REG_LIBCALL, 0))
643: in_libcall = 1;
644: else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
645: && find_reg_note (p, REG_RETVAL, 0))
646: in_libcall = 0;
647:
648: if (GET_CODE (p) == INSN
649: && (set = single_set (p))
650: && GET_CODE (SET_DEST (set)) == REG
651: && ! may_not_optimize[REGNO (SET_DEST (set))])
652: {
653: int tem1 = 0;
654: int tem2 = 0;
655: int move_insn = 0;
656: rtx src = SET_SRC (set);
657: rtx dependencies = 0;
658:
659: /* Figure out what to use as a source of this insn. If a REG_EQUIV
660: note is given or if a REG_EQUAL note with a constant operand is
661: specified, use it as the source and mark that we should move
662: this insn by calling emit_move_insn rather that duplicating the
663: insn.
664:
665: Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
666: is present. */
667: temp = find_reg_note (p, REG_EQUIV, 0);
668: if (temp)
669: src = XEXP (temp, 0), move_insn = 1;
670: else
671: {
672: temp = find_reg_note (p, REG_EQUAL, 0);
673: if (temp && CONSTANT_P (XEXP (temp, 0)))
674: src = XEXP (temp, 0), move_insn = 1;
675: if (temp && find_reg_note (p, REG_RETVAL, 0))
676: {
677: src = XEXP (temp, 0);
678: /* A libcall block can use regs that don't appear in
679: the equivalent expression. To move the libcall,
680: we must move those regs too. */
681: dependencies = libcall_other_reg (p, src);
682: }
683: }
684:
685: /* Don't try to optimize a register that was made
686: by loop-optimization for an inner loop.
687: We don't know its life-span, so we can't compute the benefit. */
688: if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
689: ;
690: /* In order to move a register, we need to have one of three cases:
691: (1) it is used only in the same basic block as the set
692: (2) it is not a user variable.
693: (3) the set is guaranteed to be executed once the loop starts,
694: and the reg is not used until after that. */
695: else if (! ((! maybe_never
696: && ! loop_reg_used_before_p (set, p, loop_start,
697: scan_start, end))
698: || ! REG_USERVAR_P (SET_DEST (PATTERN (p)))
699: || reg_in_basic_block_p (p, SET_DEST (PATTERN (p)))))
700: ;
701: else if ((tem = invariant_p (src))
702: && (dependencies == 0
703: || (tem2 = invariant_p (dependencies)) != 0)
704: && (n_times_set[REGNO (SET_DEST (set))] == 1
705: || (tem1
706: = consec_sets_invariant_p (SET_DEST (set),
707: n_times_set[REGNO (SET_DEST (set))],
708: p)))
709: /* If the insn can cause a trap (such as divide by zero),
710: can't move it unless it's guaranteed to be executed
711: once loop is entered. Even a function call might
712: prevent the trap insn from being reached
713: (since it might exit!) */
714: && ! ((maybe_never || call_passed)
715: && may_trap_p (src)))
716: {
717: register struct movable *m;
718: register int regno = REGNO (SET_DEST (set));
719:
720: /* A potential lossage is where we have a case where two insns
721: can be combined as long as they are both in the loop, but
722: we move one of them outside the loop. For large loops,
723: this can lose. The most common case of this is the address
724: of a function being called.
725:
726: Therefore, if this register is marked as being used exactly
727: once if we are in a loop with calls (a "large loop"), see if
728: we can replace the usage of this register with the source
729: of this SET. If we can, delete this insn.
730:
731: Don't do this if P has a REG_RETVAL note or if we have
732: SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
733:
734: if (reg_single_usage && reg_single_usage[regno] != 0
735: && reg_single_usage[regno] != const0_rtx
736: && regno_first_uid[regno] == INSN_UID (p)
737: && (regno_last_uid[regno]
738: == INSN_UID (reg_single_usage[regno]))
739: && n_times_set[REGNO (SET_DEST (set))] == 1
740: && ! side_effects_p (SET_SRC (set))
741: && ! find_reg_note (p, REG_RETVAL, 0)
742: #ifdef SMALL_REGISTER_CLASSES
743: && ! (GET_CODE (SET_SRC (set)) == REG
744: && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)
745: #endif
746: /* This test is not redundant; SET_SRC (set) might be
747: a call-clobbered register and the life of REGNO
748: might span a call. */
749: && ! modified_between_p (SET_SRC (set), p,
750: reg_single_usage[regno])
751: && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
752: reg_single_usage[regno]))
753: {
754: /* Replace any usage in a REG_EQUAL note. */
755: REG_NOTES (reg_single_usage[regno])
756: = replace_rtx (REG_NOTES (reg_single_usage[regno]),
757: SET_DEST (set), SET_SRC (set));
758:
759: PUT_CODE (p, NOTE);
760: NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
761: NOTE_SOURCE_FILE (p) = 0;
762: n_times_set[regno] = 0;
763: continue;
764: }
765:
766: m = (struct movable *) alloca (sizeof (struct movable));
767: m->next = 0;
768: m->insn = p;
769: m->set_src = src;
770: m->dependencies = dependencies;
771: m->set_dest = SET_DEST (set);
772: m->force = 0;
773: m->consec = n_times_set[REGNO (SET_DEST (set))] - 1;
774: m->done = 0;
775: m->forces = 0;
776: m->partial = 0;
777: m->move_insn = move_insn;
778: m->is_equiv = (find_reg_note (p, REG_EQUIV, 0) != 0);
779: m->savemode = VOIDmode;
780: m->regno = regno;
781: /* Set M->cond if either invariant_p or consec_sets_invariant_p
782: returned 2 (only conditionally invariant). */
783: m->cond = ((tem | tem1 | tem2) > 1);
784: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
785: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
786: m->match = 0;
787: m->lifetime = (uid_luid[regno_last_uid[regno]]
788: - uid_luid[regno_first_uid[regno]]);
789: m->savings = n_times_used[regno];
790: if (find_reg_note (p, REG_RETVAL, 0))
791: m->savings += libcall_benefit (p);
792: n_times_set[regno] = move_insn ? -2 : -1;
793: /* Add M to the end of the chain MOVABLES. */
794: if (movables == 0)
795: movables = m;
796: else
797: last_movable->next = m;
798: last_movable = m;
799:
800: if (m->consec > 0)
801: {
802: /* Skip this insn, not checking REG_LIBCALL notes. */
803: p = NEXT_INSN (p);
804: /* Skip the consecutive insns, if there are any. */
805: p = skip_consec_insns (p, m->consec);
806: /* Back up to the last insn of the consecutive group. */
807: p = prev_nonnote_insn (p);
808:
809: /* We must now reset m->move_insn, m->is_equiv, and possibly
810: m->set_src to correspond to the effects of all the
811: insns. */
812: temp = find_reg_note (p, REG_EQUIV, 0);
813: if (temp)
814: m->set_src = XEXP (temp, 0), m->move_insn = 1;
815: else
816: {
817: temp = find_reg_note (p, REG_EQUAL, 0);
818: if (temp && CONSTANT_P (XEXP (temp, 0)))
819: m->set_src = XEXP (temp, 0), m->move_insn = 1;
820: else
821: m->move_insn = 0;
822:
823: }
824: m->is_equiv = (find_reg_note (p, REG_EQUIV, 0) != 0);
825: }
826: }
827: /* If this register is always set within a STRICT_LOW_PART
828: or set to zero, then its high bytes are constant.
829: So clear them outside the loop and within the loop
830: just load the low bytes.
831: We must check that the machine has an instruction to do so.
832: Also, if the value loaded into the register
833: depends on the same register, this cannot be done. */
834: else if (SET_SRC (set) == const0_rtx
835: && GET_CODE (NEXT_INSN (p)) == INSN
836: && (set1 = single_set (NEXT_INSN (p)))
837: && GET_CODE (set1) == SET
838: && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
839: && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
840: && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
841: == SET_DEST (set))
842: && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
843: {
844: register int regno = REGNO (SET_DEST (set));
845: if (n_times_set[regno] == 2)
846: {
847: register struct movable *m;
848: m = (struct movable *) alloca (sizeof (struct movable));
849: m->next = 0;
850: m->insn = p;
851: m->set_dest = SET_DEST (set);
852: m->dependencies = 0;
853: m->force = 0;
854: m->consec = 0;
855: m->done = 0;
856: m->forces = 0;
857: m->move_insn = 0;
858: m->partial = 1;
859: /* If the insn may not be executed on some cycles,
860: we can't clear the whole reg; clear just high part.
861: Not even if the reg is used only within this loop.
862: Consider this:
863: while (1)
864: while (s != t) {
865: if (foo ()) x = *s;
866: use (x);
867: }
868: Clearing x before the inner loop could clobber a value
869: being saved from the last time around the outer loop.
870: However, if the reg is not used outside this loop
871: and all uses of the register are in the same
872: basic block as the store, there is no problem.
873:
874: If this insn was made by loop, we don't know its
875: INSN_LUID and hence must make a conservative
876: assumption. */
877: m->global = (INSN_UID (p) >= max_uid_for_loop
878: || (uid_luid[regno_last_uid[regno]]
879: > INSN_LUID (end))
880: || (uid_luid[regno_first_uid[regno]]
881: < INSN_LUID (p))
882: || (labels_in_range_p
883: (p, uid_luid[regno_first_uid[regno]])));
884: if (maybe_never && m->global)
885: m->savemode = GET_MODE (SET_SRC (set1));
886: else
887: m->savemode = VOIDmode;
888: m->regno = regno;
889: m->cond = 0;
890: m->match = 0;
891: m->lifetime = (uid_luid[regno_last_uid[regno]]
892: - uid_luid[regno_first_uid[regno]]);
893: m->savings = 1;
894: n_times_set[regno] = -1;
895: /* Add M to the end of the chain MOVABLES. */
896: if (movables == 0)
897: movables = m;
898: else
899: last_movable->next = m;
900: last_movable = m;
901: }
902: }
903: }
904: /* Past a call insn, we get to insns which might not be executed
905: because the call might exit. This matters for insns that trap.
906: Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
907: so they don't count. */
908: else if (GET_CODE (p) == CALL_INSN && ! in_libcall)
909: call_passed = 1;
910: /* Past a label or a jump, we get to insns for which we
911: can't count on whether or how many times they will be
912: executed during each iteration. Therefore, we can
913: only move out sets of trivial variables
914: (those not used after the loop). */
915: /* This code appears in three places, once in scan_loop, and twice
916: in strength_reduce. */
917: else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
918: /* If we enter the loop in the middle, and scan around to the
919: beginning, don't set maybe_never for that. This must be an
920: unconditional jump, otherwise the code at the top of the
921: loop might never be executed. Unconditional jumps are
922: followed a by barrier then loop end. */
923: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
924: && NEXT_INSN (NEXT_INSN (p)) == end
925: && simplejump_p (p)))
926: maybe_never = 1;
927: /* At the virtual top of a converted loop, insns are again known to
928: be executed: logically, the loop begins here even though the exit
929: code has been duplicated. */
930: else if (GET_CODE (p) == NOTE
931: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
932: maybe_never = call_passed = 0;
933: }
934:
935: /* If one movable subsumes another, ignore that other. */
936:
937: ignore_some_movables (movables);
938:
939: /* For each movable insn, see if the reg that it loads
940: leads when it dies right into another conditionally movable insn.
941: If so, record that the second insn "forces" the first one,
942: since the second can be moved only if the first is. */
943:
944: force_movables (movables);
945:
946: /* See if there are multiple movable insns that load the same value.
947: If there are, make all but the first point at the first one
948: through the `match' field, and add the priorities of them
949: all together as the priority of the first. */
950:
951: combine_movables (movables, nregs);
952:
953: /* Now consider each movable insn to decide whether it is worth moving.
954: Store 0 in n_times_set for each reg that is moved. */
955:
956: move_movables (movables, threshold,
957: insn_count, loop_start, end, nregs);
958:
959: /* Now candidates that still are negative are those not moved.
960: Change n_times_set to indicate that those are not actually invariant. */
961: for (i = 0; i < nregs; i++)
962: if (n_times_set[i] < 0)
963: n_times_set[i] = n_times_used[i];
964:
965: if (flag_strength_reduce)
966: strength_reduce (scan_start, end, loop_top,
967: insn_count, loop_start, end);
968: }
969:
970: /* Add elements to *OUTPUT to record all the pseudo-regs
971: mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
972:
973: void
974: record_excess_regs (in_this, not_in_this, output)
975: rtx in_this, not_in_this;
976: rtx *output;
977: {
978: enum rtx_code code;
979: char *fmt;
980: int i;
981:
982: code = GET_CODE (in_this);
983:
984: switch (code)
985: {
986: case PC:
987: case CC0:
988: case CONST_INT:
989: case CONST_DOUBLE:
990: case CONST:
991: case SYMBOL_REF:
992: case LABEL_REF:
993: return;
994:
995: case REG:
996: if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
997: && ! reg_mentioned_p (in_this, not_in_this))
998: *output = gen_rtx (EXPR_LIST, VOIDmode, in_this, *output);
999: return;
1000: }
1001:
1002: fmt = GET_RTX_FORMAT (code);
1003: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1004: {
1005: int j;
1006:
1007: switch (fmt[i])
1008: {
1009: case 'E':
1010: for (j = 0; j < XVECLEN (in_this, i); j++)
1011: record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1012: break;
1013:
1014: case 'e':
1015: record_excess_regs (XEXP (in_this, i), not_in_this, output);
1016: break;
1017: }
1018: }
1019: }
1020:
1021: /* Check what regs are referred to in the libcall block ending with INSN,
1022: aside from those mentioned in the equivalent value.
1023: If there are none, return 0.
1024: If there are one or more, return an EXPR_LIST containing all of them. */
1025:
1026: static rtx
1027: libcall_other_reg (insn, equiv)
1028: rtx insn, equiv;
1029: {
1030: rtx note = find_reg_note (insn, REG_RETVAL, 0);
1031: rtx p = XEXP (note, 0);
1032: rtx output = 0;
1033:
1034: /* First, find all the regs used in the libcall block
1035: that are not mentioned as inputs to the result. */
1036:
1037: while (p != insn)
1038: {
1039: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1040: || GET_CODE (p) == CALL_INSN)
1041: record_excess_regs (PATTERN (p), equiv, &output);
1042: p = NEXT_INSN (p);
1043: }
1044:
1045: return output;
1046: }
1047:
1048: /* Return 1 if all uses of REG
1049: are between INSN and the end of the basic block. */
1050:
1051: static int
1052: reg_in_basic_block_p (insn, reg)
1053: rtx insn, reg;
1054: {
1055: int regno = REGNO (reg);
1056: rtx p;
1057:
1058: if (regno_first_uid[regno] != INSN_UID (insn))
1059: return 0;
1060:
1061: /* Search this basic block for the already recorded last use of the reg. */
1062: for (p = insn; p; p = NEXT_INSN (p))
1063: {
1064: switch (GET_CODE (p))
1065: {
1066: case NOTE:
1067: break;
1068:
1069: case INSN:
1070: case CALL_INSN:
1071: /* Ordinary insn: if this is the last use, we win. */
1072: if (regno_last_uid[regno] == INSN_UID (p))
1073: return 1;
1074: break;
1075:
1076: case JUMP_INSN:
1077: /* Jump insn: if this is the last use, we win. */
1078: if (regno_last_uid[regno] == INSN_UID (p))
1079: return 1;
1080: /* Otherwise, it's the end of the basic block, so we lose. */
1081: return 0;
1082:
1083: case CODE_LABEL:
1084: case BARRIER:
1085: /* It's the end of the basic block, so we lose. */
1086: return 0;
1087: }
1088: }
1089:
1090: /* The "last use" doesn't follow the "first use"?? */
1091: abort ();
1092: }
1093:
1094: /* Compute the benefit of eliminating the insns in the block whose
1095: last insn is LAST. This may be a group of insns used to compute a
1096: value directly or can contain a library call. */
1097:
1098: static int
1099: libcall_benefit (last)
1100: rtx last;
1101: {
1102: rtx insn;
1103: int benefit = 0;
1104:
1105: for (insn = XEXP (find_reg_note (last, REG_RETVAL, 0), 0);
1106: insn != last; insn = NEXT_INSN (insn))
1107: {
1108: if (GET_CODE (insn) == CALL_INSN)
1109: benefit += 10; /* Assume at least this many insns in a library
1110: routine. */
1111: else if (GET_CODE (insn) == INSN
1112: && GET_CODE (PATTERN (insn)) != USE
1113: && GET_CODE (PATTERN (insn)) != CLOBBER)
1114: benefit++;
1115: }
1116:
1117: return benefit;
1118: }
1119:
1120: /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1121:
1122: static rtx
1123: skip_consec_insns (insn, count)
1124: rtx insn;
1125: int count;
1126: {
1127: for (; count > 0; count--)
1128: {
1129: rtx temp;
1130:
1131: /* If first insn of libcall sequence, skip to end. */
1132: /* Do this at start of loop, since INSN is guaranteed to
1133: be an insn here. */
1134: if (GET_CODE (insn) != NOTE
1135: && (temp = find_reg_note (insn, REG_LIBCALL, 0)))
1136: insn = XEXP (temp, 0);
1137:
1138: do insn = NEXT_INSN (insn);
1139: while (GET_CODE (insn) == NOTE);
1140: }
1141:
1142: return insn;
1143: }
1144:
1145: /* Ignore any movable whose insn falls within a libcall
1146: which is part of another movable.
1147: We make use of the fact that the movable for the libcall value
1148: was made later and so appears later on the chain. */
1149:
1150: static void
1151: ignore_some_movables (movables)
1152: struct movable *movables;
1153: {
1154: register struct movable *m, *m1;
1155:
1156: for (m = movables; m; m = m->next)
1157: {
1158: /* Is this a movable for the value of a libcall? */
1159: rtx note = find_reg_note (m->insn, REG_RETVAL, 0);
1160: if (note)
1161: {
1162: rtx insn;
1163: /* Check for earlier movables inside that range,
1164: and mark them invalid. We cannot use LUIDs here because
1165: insns created by loop.c for prior loops don't have LUIDs.
1166: Rather than reject all such insns from movables, we just
1167: explicitly check each insn in the libcall (since invariant
1168: libcalls aren't that common). */
1169: for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1170: for (m1 = movables; m1 != m; m1 = m1->next)
1171: if (m1->insn == insn)
1172: m1->done = 1;
1173: }
1174: }
1175: }
1176:
1177: /* For each movable insn, see if the reg that it loads
1178: leads when it dies right into another conditionally movable insn.
1179: If so, record that the second insn "forces" the first one,
1180: since the second can be moved only if the first is. */
1181:
1182: static void
1183: force_movables (movables)
1184: struct movable *movables;
1185: {
1186: register struct movable *m, *m1;
1187: for (m1 = movables; m1; m1 = m1->next)
1188: /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1189: if (!m1->partial && !m1->done)
1190: {
1191: int regno = m1->regno;
1192: for (m = m1->next; m; m = m->next)
1193: /* ??? Could this be a bug? What if CSE caused the
1194: register of M1 to be used after this insn?
1195: Since CSE does not update regno_last_uid,
1196: this insn M->insn might not be where it dies.
1197: But very likely this doesn't matter; what matters is
1198: that M's reg is computed from M1's reg. */
1199: if (INSN_UID (m->insn) == regno_last_uid[regno]
1200: && !m->done)
1201: break;
1202: if (m != 0 && m->set_src == m1->set_dest
1203: /* If m->consec, m->set_src isn't valid. */
1204: && m->consec == 0)
1205: m = 0;
1206:
1207: /* Increase the priority of the moving the first insn
1208: since it permits the second to be moved as well. */
1209: if (m != 0)
1210: {
1211: m->forces = m1;
1212: m1->lifetime += m->lifetime;
1213: m1->savings += m1->savings;
1214: }
1215: }
1216: }
1217:
1218: /* Find invariant expressions that are equal and can be combined into
1219: one register. */
1220:
1221: static void
1222: combine_movables (movables, nregs)
1223: struct movable *movables;
1224: int nregs;
1225: {
1226: register struct movable *m;
1227: char *matched_regs = (char *) alloca (nregs);
1228: enum machine_mode mode;
1229:
1230: /* Regs that are set more than once are not allowed to match
1231: or be matched. I'm no longer sure why not. */
1232: /* Perhaps testing m->consec_sets would be more appropriate here? */
1233:
1234: for (m = movables; m; m = m->next)
1235: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial)
1236: {
1237: register struct movable *m1;
1238: int regno = m->regno;
1239: rtx reg_note, reg_note1;
1240:
1241: bzero (matched_regs, nregs);
1242: matched_regs[regno] = 1;
1243:
1244: for (m1 = movables; m1; m1 = m1->next)
1245: if (m != m1 && m1->match == 0 && n_times_used[m1->regno] == 1
1246: /* A reg used outside the loop mustn't be eliminated. */
1247: && !m1->global
1248: /* A reg used for zero-extending mustn't be eliminated. */
1249: && !m1->partial
1250: && (matched_regs[m1->regno]
1251: ||
1252: (
1253: /* Can combine regs with different modes loaded from the
1254: same constant only if the modes are the same or
1255: if both are integer modes with M wider or the same
1256: width as M1. The check for integer is redundant, but
1257: safe, since the only case of differing destination
1258: modes with equal sources is when both sources are
1259: VOIDmode, i.e., CONST_INT. */
1260: (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1261: || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1262: && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1263: && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1264: >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1265: /* See if the source of M1 says it matches M. */
1266: && ((GET_CODE (m1->set_src) == REG
1267: && matched_regs[REGNO (m1->set_src)])
1268: || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1269: movables))))
1270: && ((m->dependencies == m1->dependencies)
1271: || rtx_equal_p (m->dependencies, m1->dependencies)))
1272: {
1273: m->lifetime += m1->lifetime;
1274: m->savings += m1->savings;
1275: m1->done = 1;
1276: m1->match = m;
1277: matched_regs[m1->regno] = 1;
1278: }
1279: }
1280:
1281: /* Now combine the regs used for zero-extension.
1282: This can be done for those not marked `global'
1283: provided their lives don't overlap. */
1284:
1285: for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1286: mode = GET_MODE_WIDER_MODE (mode))
1287: {
1288: register struct movable *m0 = 0;
1289:
1290: /* Combine all the registers for extension from mode MODE.
1291: Don't combine any that are used outside this loop. */
1292: for (m = movables; m; m = m->next)
1293: if (m->partial && ! m->global
1294: && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1295: {
1296: register struct movable *m1;
1297: int first = uid_luid[regno_first_uid[m->regno]];
1298: int last = uid_luid[regno_last_uid[m->regno]];
1299:
1300: if (m0 == 0)
1301: {
1302: /* First one: don't check for overlap, just record it. */
1303: m0 = m;
1304: continue;
1305: }
1306:
1307: /* Make sure they extend to the same mode.
1308: (Almost always true.) */
1309: if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1310: continue;
1311:
1312: /* We already have one: check for overlap with those
1313: already combined together. */
1314: for (m1 = movables; m1 != m; m1 = m1->next)
1315: if (m1 == m0 || (m1->partial && m1->match == m0))
1316: if (! (uid_luid[regno_first_uid[m1->regno]] > last
1317: || uid_luid[regno_last_uid[m1->regno]] < first))
1318: goto overlap;
1319:
1320: /* No overlap: we can combine this with the others. */
1321: m0->lifetime += m->lifetime;
1322: m0->savings += m->savings;
1323: m->done = 1;
1324: m->match = m0;
1325:
1326: overlap: ;
1327: }
1328: }
1329: }
1330:
1331: /* Return 1 if regs X and Y will become the same if moved. */
1332:
1333: static int
1334: regs_match_p (x, y, movables)
1335: rtx x, y;
1336: struct movable *movables;
1337: {
1338: int xn = REGNO (x);
1339: int yn = REGNO (y);
1340: struct movable *mx, *my;
1341:
1342: for (mx = movables; mx; mx = mx->next)
1343: if (mx->regno == xn)
1344: break;
1345:
1346: for (my = movables; my; my = my->next)
1347: if (my->regno == yn)
1348: break;
1349:
1350: return (mx && my
1351: && ((mx->match == my->match && mx->match != 0)
1352: || mx->match == my
1353: || mx == my->match));
1354: }
1355:
1356: /* Return 1 if X and Y are identical-looking rtx's.
1357: This is the Lisp function EQUAL for rtx arguments.
1358:
1359: If two registers are matching movables or a movable register and an
1360: equivalent constant, consider them equal. */
1361:
1362: static int
1363: rtx_equal_for_loop_p (x, y, movables)
1364: rtx x, y;
1365: struct movable *movables;
1366: {
1367: register int i;
1368: register int j;
1369: register struct movable *m;
1370: register enum rtx_code code;
1371: register char *fmt;
1372:
1373: if (x == y)
1374: return 1;
1375: if (x == 0 || y == 0)
1376: return 0;
1377:
1378: code = GET_CODE (x);
1379:
1380: /* If we have a register and a constant, they may sometimes be
1381: equal. */
1382: if (GET_CODE (x) == REG && n_times_set[REGNO (x)] == -2
1383: && CONSTANT_P (y))
1384: for (m = movables; m; m = m->next)
1385: if (m->move_insn && m->regno == REGNO (x)
1386: && rtx_equal_p (m->set_src, y))
1387: return 1;
1388:
1389: else if (GET_CODE (y) == REG && n_times_set[REGNO (y)] == -2
1390: && CONSTANT_P (x))
1391: for (m = movables; m; m = m->next)
1392: if (m->move_insn && m->regno == REGNO (y)
1393: && rtx_equal_p (m->set_src, x))
1394: return 1;
1395:
1396: /* Otherwise, rtx's of different codes cannot be equal. */
1397: if (code != GET_CODE (y))
1398: return 0;
1399:
1400: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1401: (REG:SI x) and (REG:HI x) are NOT equivalent. */
1402:
1403: if (GET_MODE (x) != GET_MODE (y))
1404: return 0;
1405:
1406: /* These three types of rtx's can be compared nonrecursively. */
1407: if (code == REG)
1408: return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1409:
1410: if (code == LABEL_REF)
1411: return XEXP (x, 0) == XEXP (y, 0);
1412: if (code == SYMBOL_REF)
1413: return XSTR (x, 0) == XSTR (y, 0);
1414:
1415: /* Compare the elements. If any pair of corresponding elements
1416: fail to match, return 0 for the whole things. */
1417:
1418: fmt = GET_RTX_FORMAT (code);
1419: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1420: {
1421: switch (fmt[i])
1422: {
1423: case 'i':
1424: if (XINT (x, i) != XINT (y, i))
1425: return 0;
1426: break;
1427:
1428: case 'E':
1429: /* Two vectors must have the same length. */
1430: if (XVECLEN (x, i) != XVECLEN (y, i))
1431: return 0;
1432:
1433: /* And the corresponding elements must match. */
1434: for (j = 0; j < XVECLEN (x, i); j++)
1435: if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0)
1436: return 0;
1437: break;
1438:
1439: case 'e':
1440: if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0)
1441: return 0;
1442: break;
1443:
1444: case 's':
1445: if (strcmp (XSTR (x, i), XSTR (y, i)))
1446: return 0;
1447: break;
1448:
1449: case 'u':
1450: /* These are just backpointers, so they don't matter. */
1451: break;
1452:
1453: case '0':
1454: break;
1455:
1456: /* It is believed that rtx's at this level will never
1457: contain anything but integers and other rtx's,
1458: except for within LABEL_REFs and SYMBOL_REFs. */
1459: default:
1460: abort ();
1461: }
1462: }
1463: return 1;
1464: }
1465:
1.1.1.2 root 1466: /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
1467: insns in INSNS which use thet reference. */
1468:
1469: static void
1470: add_label_notes (x, insns)
1471: rtx x;
1472: rtx insns;
1473: {
1474: enum rtx_code code = GET_CODE (x);
1.1.1.3 ! root 1475: int i, j;
1.1.1.2 root 1476: char *fmt;
1477: rtx insn;
1478:
1479: if (code == LABEL_REF)
1480: {
1481: for (insn = insns; insn; insn = NEXT_INSN (insn))
1482: if (reg_mentioned_p (XEXP (x, 0), insn))
1483: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0),
1484: REG_NOTES (insn));
1485: return;
1486: }
1487:
1488: fmt = GET_RTX_FORMAT (code);
1489: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1.1.1.3 ! root 1490: {
! 1491: if (fmt[i] == 'e')
! 1492: add_label_notes (XEXP (x, i), insns);
! 1493: else if (fmt[i] == 'E')
! 1494: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
! 1495: add_label_notes (XVECEXP (x, i, j), insns);
! 1496: }
1.1.1.2 root 1497: }
1498:
1.1 root 1499: /* Scan MOVABLES, and move the insns that deserve to be moved.
1500: If two matching movables are combined, replace one reg with the
1501: other throughout. */
1502:
1503: static void
1504: move_movables (movables, threshold, insn_count, loop_start, end, nregs)
1505: struct movable *movables;
1506: int threshold;
1507: int insn_count;
1508: rtx loop_start;
1509: rtx end;
1510: int nregs;
1511: {
1512: rtx new_start = 0;
1513: register struct movable *m;
1514: register rtx p;
1515: /* Map of pseudo-register replacements to handle combining
1516: when we move several insns that load the same value
1517: into different pseudo-registers. */
1518: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
1519: char *already_moved = (char *) alloca (nregs);
1520:
1521: bzero (already_moved, nregs);
1522: bzero (reg_map, nregs * sizeof (rtx));
1523:
1524: num_movables = 0;
1525:
1526: for (m = movables; m; m = m->next)
1527: {
1528: /* Describe this movable insn. */
1529:
1530: if (loop_dump_stream)
1531: {
1532: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1533: INSN_UID (m->insn), m->regno, m->lifetime);
1534: if (m->consec > 0)
1535: fprintf (loop_dump_stream, "consec %d, ", m->consec);
1536: if (m->cond)
1537: fprintf (loop_dump_stream, "cond ");
1538: if (m->force)
1539: fprintf (loop_dump_stream, "force ");
1540: if (m->global)
1541: fprintf (loop_dump_stream, "global ");
1542: if (m->done)
1543: fprintf (loop_dump_stream, "done ");
1544: if (m->move_insn)
1545: fprintf (loop_dump_stream, "move-insn ");
1546: if (m->match)
1547: fprintf (loop_dump_stream, "matches %d ",
1548: INSN_UID (m->match->insn));
1549: if (m->forces)
1550: fprintf (loop_dump_stream, "forces %d ",
1551: INSN_UID (m->forces->insn));
1552: }
1553:
1554: /* Count movables. Value used in heuristics in strength_reduce. */
1555: num_movables++;
1556:
1557: /* Ignore the insn if it's already done (it matched something else).
1558: Otherwise, see if it is now safe to move. */
1559:
1560: if (!m->done
1561: && (! m->cond
1562: || (1 == invariant_p (m->set_src)
1563: && (m->dependencies == 0
1564: || 1 == invariant_p (m->dependencies))
1565: && (m->consec == 0
1566: || 1 == consec_sets_invariant_p (m->set_dest,
1567: m->consec + 1,
1568: m->insn))))
1569: && (! m->forces || m->forces->done))
1570: {
1571: register int regno;
1572: register rtx p;
1573: int savings = m->savings;
1574:
1575: /* We have an insn that is safe to move.
1576: Compute its desirability. */
1577:
1578: p = m->insn;
1579: regno = m->regno;
1580:
1581: if (loop_dump_stream)
1582: fprintf (loop_dump_stream, "savings %d ", savings);
1583:
1584: if (moved_once[regno])
1585: {
1586: insn_count *= 2;
1587:
1588: if (loop_dump_stream)
1589: fprintf (loop_dump_stream, "halved since already moved ");
1590: }
1591:
1592: /* An insn MUST be moved if we already moved something else
1593: which is safe only if this one is moved too: that is,
1594: if already_moved[REGNO] is nonzero. */
1595:
1596: /* An insn is desirable to move if the new lifetime of the
1597: register is no more than THRESHOLD times the old lifetime.
1598: If it's not desirable, it means the loop is so big
1599: that moving won't speed things up much,
1600: and it is liable to make register usage worse. */
1601:
1602: /* It is also desirable to move if it can be moved at no
1603: extra cost because something else was already moved. */
1604:
1605: if (already_moved[regno]
1606: || (threshold * savings * m->lifetime) >= insn_count
1607: || (m->forces && m->forces->done
1608: && n_times_used[m->forces->regno] == 1))
1609: {
1610: int count;
1611: register struct movable *m1;
1612: rtx first;
1613:
1614: /* Now move the insns that set the reg. */
1615:
1616: if (m->partial && m->match)
1617: {
1618: rtx newpat, i1;
1619: rtx r1, r2;
1620: /* Find the end of this chain of matching regs.
1621: Thus, we load each reg in the chain from that one reg.
1622: And that reg is loaded with 0 directly,
1623: since it has ->match == 0. */
1624: for (m1 = m; m1->match; m1 = m1->match);
1625: newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1626: SET_DEST (PATTERN (m1->insn)));
1627: i1 = emit_insn_before (newpat, loop_start);
1628:
1629: /* Mark the moved, invariant reg as being allowed to
1630: share a hard reg with the other matching invariant. */
1631: REG_NOTES (i1) = REG_NOTES (m->insn);
1632: r1 = SET_DEST (PATTERN (m->insn));
1633: r2 = SET_DEST (PATTERN (m1->insn));
1634: regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, r1,
1635: gen_rtx (EXPR_LIST, VOIDmode, r2,
1636: regs_may_share));
1637: delete_insn (m->insn);
1638:
1639: if (new_start == 0)
1640: new_start = i1;
1641:
1642: if (loop_dump_stream)
1643: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1644: }
1645: /* If we are to re-generate the item being moved with a
1646: new move insn, first delete what we have and then emit
1647: the move insn before the loop. */
1648: else if (m->move_insn)
1649: {
1650: rtx i1, temp;
1651:
1652: for (count = m->consec; count >= 0; count--)
1653: {
1654: /* If this is the first insn of a library call sequence,
1655: skip to the end. */
1656: if (GET_CODE (p) != NOTE
1657: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
1658: p = XEXP (temp, 0);
1659:
1660: /* If this is the last insn of a libcall sequence, then
1661: delete every insn in the sequence except the last.
1662: The last insn is handled in the normal manner. */
1663: if (GET_CODE (p) != NOTE
1664: && (temp = find_reg_note (p, REG_RETVAL, 0)))
1665: {
1666: temp = XEXP (temp, 0);
1667: while (temp != p)
1668: temp = delete_insn (temp);
1669: }
1670:
1671: p = delete_insn (p);
1672: }
1673:
1674: start_sequence ();
1675: emit_move_insn (m->set_dest, m->set_src);
1.1.1.2 root 1676: temp = get_insns ();
1.1 root 1677: end_sequence ();
1678:
1.1.1.2 root 1679: add_label_notes (m->set_src, temp);
1680:
1681: i1 = emit_insns_before (temp, loop_start);
1.1 root 1682: if (! find_reg_note (i1, REG_EQUAL, 0))
1683: REG_NOTES (i1)
1684: = gen_rtx (EXPR_LIST,
1685: m->is_equiv ? REG_EQUIV : REG_EQUAL,
1686: m->set_src, REG_NOTES (i1));
1687:
1688: if (loop_dump_stream)
1689: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1690:
1691: /* The more regs we move, the less we like moving them. */
1692: threshold -= 3;
1693: }
1694: else
1695: {
1696: for (count = m->consec; count >= 0; count--)
1697: {
1698: rtx i1, temp;
1699:
1700: /* If first insn of libcall sequence, skip to end. */
1701: /* Do this at start of loop, since p is guaranteed to
1702: be an insn here. */
1703: if (GET_CODE (p) != NOTE
1704: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
1705: p = XEXP (temp, 0);
1706:
1707: /* If last insn of libcall sequence, move all
1708: insns except the last before the loop. The last
1709: insn is handled in the normal manner. */
1710: if (GET_CODE (p) != NOTE
1711: && (temp = find_reg_note (p, REG_RETVAL, 0)))
1712: {
1713: rtx fn_address = 0;
1714: rtx fn_reg = 0;
1715: rtx fn_address_insn = 0;
1716:
1717: first = 0;
1718: for (temp = XEXP (temp, 0); temp != p;
1719: temp = NEXT_INSN (temp))
1720: {
1721: rtx body;
1722: rtx n;
1723: rtx next;
1724:
1725: if (GET_CODE (temp) == NOTE)
1726: continue;
1727:
1728: body = PATTERN (temp);
1729:
1730: /* Find the next insn after TEMP,
1731: not counting USE or NOTE insns. */
1732: for (next = NEXT_INSN (temp); next != p;
1733: next = NEXT_INSN (next))
1734: if (! (GET_CODE (next) == INSN
1735: && GET_CODE (PATTERN (next)) == USE)
1736: && GET_CODE (next) != NOTE)
1737: break;
1738:
1739: /* If that is the call, this may be the insn
1740: that loads the function address.
1741:
1742: Extract the function address from the insn
1743: that loads it into a register.
1744: If this insn was cse'd, we get incorrect code.
1745:
1746: So emit a new move insn that copies the
1747: function address into the register that the
1748: call insn will use. flow.c will delete any
1749: redundant stores that we have created. */
1750: if (GET_CODE (next) == CALL_INSN
1751: && GET_CODE (body) == SET
1752: && GET_CODE (SET_DEST (body)) == REG
1753: && (n = find_reg_note (temp, REG_EQUAL, 0)))
1754: {
1755: fn_reg = SET_SRC (body);
1756: if (GET_CODE (fn_reg) != REG)
1757: fn_reg = SET_DEST (body);
1758: fn_address = XEXP (n, 0);
1759: fn_address_insn = temp;
1760: }
1761: /* We have the call insn.
1762: If it uses the register we suspect it might,
1763: load it with the correct address directly. */
1764: if (GET_CODE (temp) == CALL_INSN
1765: && fn_address != 0
1766: && reg_mentioned_p (fn_reg, body))
1767: emit_insn_after (gen_move_insn (fn_reg,
1768: fn_address),
1769: fn_address_insn);
1770:
1771: if (GET_CODE (temp) == CALL_INSN)
1772: i1 = emit_call_insn_before (body, loop_start);
1773: else
1774: i1 = emit_insn_before (body, loop_start);
1775: if (first == 0)
1776: first = i1;
1777: if (temp == fn_address_insn)
1778: fn_address_insn = i1;
1779: REG_NOTES (i1) = REG_NOTES (temp);
1780: delete_insn (temp);
1781: }
1782: }
1783: if (m->savemode != VOIDmode)
1784: {
1785: /* P sets REG to zero; but we should clear only
1786: the bits that are not covered by the mode
1787: m->savemode. */
1788: rtx reg = m->set_dest;
1789: rtx sequence;
1790: rtx tem;
1791:
1792: start_sequence ();
1793: tem = expand_binop
1794: (GET_MODE (reg), and_optab, reg,
1795: gen_rtx (CONST_INT, VOIDmode,
1796: ((1 << GET_MODE_BITSIZE (m->savemode)))
1797: - 1),
1798: reg, 1, OPTAB_LIB_WIDEN);
1799: if (tem == 0)
1800: abort ();
1801: if (tem != reg)
1802: emit_move_insn (reg, tem);
1803: sequence = gen_sequence ();
1804: end_sequence ();
1805: i1 = emit_insn_before (sequence, loop_start);
1806: }
1807: else if (GET_CODE (p) == CALL_INSN)
1808: i1 = emit_call_insn_before (PATTERN (p), loop_start);
1809: else
1810: i1 = emit_insn_before (PATTERN (p), loop_start);
1811:
1812: REG_NOTES (i1) = REG_NOTES (p);
1813:
1814: if (new_start == 0)
1815: new_start = i1;
1816:
1817: if (loop_dump_stream)
1818: fprintf (loop_dump_stream, " moved to %d",
1819: INSN_UID (i1));
1820:
1821: #if 0
1822: /* This isn't needed because REG_NOTES is copied
1823: below and is wrong since P might be a PARALLEL. */
1824: if (REG_NOTES (i1) == 0
1825: && ! m->partial /* But not if it's a zero-extend clr. */
1826: && ! m->global /* and not if used outside the loop
1827: (since it might get set outside). */
1828: && CONSTANT_P (SET_SRC (PATTERN (p))))
1829: REG_NOTES (i1)
1830: = gen_rtx (EXPR_LIST, REG_EQUAL,
1831: SET_SRC (PATTERN (p)), REG_NOTES (i1));
1832: #endif
1833:
1834: /* If library call, now fix the REG_NOTES that contain
1835: insn pointers, namely REG_LIBCALL on FIRST
1836: and REG_RETVAL on I1. */
1837: if (temp = find_reg_note (i1, REG_RETVAL, 0))
1838: {
1839: XEXP (temp, 0) = first;
1840: temp = find_reg_note (first, REG_LIBCALL, 0);
1841: XEXP (temp, 0) = i1;
1842: }
1843:
1844: delete_insn (p);
1845: do p = NEXT_INSN (p);
1846: while (p && GET_CODE (p) == NOTE);
1847: }
1848:
1849: /* The more regs we move, the less we like moving them. */
1850: threshold -= 3;
1851: }
1852:
1853: /* Any other movable that loads the same register
1854: MUST be moved. */
1855: already_moved[regno] = 1;
1856:
1857: /* This reg has been moved out of one loop. */
1858: moved_once[regno] = 1;
1859:
1860: /* The reg set here is now invariant. */
1861: if (! m->partial)
1862: n_times_set[regno] = 0;
1863:
1864: m->done = 1;
1865:
1866: /* Change the length-of-life info for the register
1867: to say it lives at least the full length of this loop.
1868: This will help guide optimizations in outer loops. */
1869:
1870: if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start))
1871: /* This is the old insn before all the moved insns.
1872: We can't use the moved insn because it is out of range
1873: in uid_luid. Only the old insns have luids. */
1874: regno_first_uid[regno] = INSN_UID (loop_start);
1875: if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end))
1876: regno_last_uid[regno] = INSN_UID (end);
1877:
1878: /* Combine with this moved insn any other matching movables. */
1879:
1880: if (! m->partial)
1881: for (m1 = movables; m1; m1 = m1->next)
1882: if (m1->match == m)
1883: {
1884: rtx temp;
1885:
1886: /* Schedule the reg loaded by M1
1887: for replacement so that shares the reg of M.
1888: If the modes differ (only possible in restricted
1889: circumstances, make a SUBREG. */
1890: if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
1891: reg_map[m1->regno] = m->set_dest;
1892: else
1893: reg_map[m1->regno]
1894: = gen_lowpart_common (GET_MODE (m1->set_dest),
1895: m->set_dest);
1896:
1897: /* Get rid of the matching insn
1898: and prevent further processing of it. */
1899: m1->done = 1;
1900:
1901: /* if library call, delete all insn except last, which
1902: is deleted below */
1903: if (temp = find_reg_note (m1->insn, REG_RETVAL, 0))
1904: {
1905: for (temp = XEXP (temp, 0); temp != m1->insn;
1906: temp = NEXT_INSN (temp))
1907: delete_insn (temp);
1908: }
1909: delete_insn (m1->insn);
1910:
1911: /* Any other movable that loads the same register
1912: MUST be moved. */
1913: already_moved[m1->regno] = 1;
1914:
1915: /* The reg merged here is now invariant,
1916: if the reg it matches is invariant. */
1917: if (! m->partial)
1918: n_times_set[m1->regno] = 0;
1919: }
1920: }
1921: else if (loop_dump_stream)
1922: fprintf (loop_dump_stream, "not desirable");
1923: }
1924: else if (loop_dump_stream && !m->match)
1925: fprintf (loop_dump_stream, "not safe");
1926:
1927: if (loop_dump_stream)
1928: fprintf (loop_dump_stream, "\n");
1929: }
1930:
1931: if (new_start == 0)
1932: new_start = loop_start;
1933:
1934: /* Go through all the instructions in the loop, making
1935: all the register substitutions scheduled in REG_MAP. */
1936: for (p = new_start; p != end; p = NEXT_INSN (p))
1937: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1938: || GET_CODE (p) == CALL_INSN)
1939: {
1940: replace_regs (PATTERN (p), reg_map, nregs, 0);
1941: replace_regs (REG_NOTES (p), reg_map, nregs, 0);
1942: }
1943: }
1944:
1945: #if 0
1946: /* Scan X and replace the address of any MEM in it with ADDR.
1947: REG is the address that MEM should have before the replacement. */
1948:
1949: static void
1950: replace_call_address (x, reg, addr)
1951: rtx x, reg, addr;
1952: {
1953: register enum rtx_code code;
1954: register int i;
1955: register char *fmt;
1956:
1957: if (x == 0)
1958: return;
1959: code = GET_CODE (x);
1960: switch (code)
1961: {
1962: case PC:
1963: case CC0:
1964: case CONST_INT:
1965: case CONST_DOUBLE:
1966: case CONST:
1967: case SYMBOL_REF:
1968: case LABEL_REF:
1969: case REG:
1970: return;
1971:
1972: case SET:
1973: /* Short cut for very common case. */
1974: replace_call_address (XEXP (x, 1), reg, addr);
1975: return;
1976:
1977: case CALL:
1978: /* Short cut for very common case. */
1979: replace_call_address (XEXP (x, 0), reg, addr);
1980: return;
1981:
1982: case MEM:
1983: /* If this MEM uses a reg other than the one we expected,
1984: something is wrong. */
1985: if (XEXP (x, 0) != reg)
1986: abort ();
1987: XEXP (x, 0) = addr;
1988: return;
1989: }
1990:
1991: fmt = GET_RTX_FORMAT (code);
1992: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1993: {
1994: if (fmt[i] == 'e')
1995: replace_call_address (XEXP (x, i), reg, addr);
1996: if (fmt[i] == 'E')
1997: {
1998: register int j;
1999: for (j = 0; j < XVECLEN (x, i); j++)
2000: replace_call_address (XVECEXP (x, i, j), reg, addr);
2001: }
2002: }
2003: }
2004: #endif
2005:
2006: /* Return the number of memory refs to addresses that vary
2007: in the rtx X. */
2008:
2009: static int
2010: count_nonfixed_reads (x)
2011: rtx x;
2012: {
2013: register enum rtx_code code;
2014: register int i;
2015: register char *fmt;
2016: int value;
2017:
2018: if (x == 0)
2019: return 0;
2020:
2021: code = GET_CODE (x);
2022: switch (code)
2023: {
2024: case PC:
2025: case CC0:
2026: case CONST_INT:
2027: case CONST_DOUBLE:
2028: case CONST:
2029: case SYMBOL_REF:
2030: case LABEL_REF:
2031: case REG:
2032: return 0;
2033:
2034: case MEM:
2035: return ((invariant_p (XEXP (x, 0)) != 1)
2036: + count_nonfixed_reads (XEXP (x, 0)));
2037: }
2038:
2039: value = 0;
2040: fmt = GET_RTX_FORMAT (code);
2041: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2042: {
2043: if (fmt[i] == 'e')
2044: value += count_nonfixed_reads (XEXP (x, i));
2045: if (fmt[i] == 'E')
2046: {
2047: register int j;
2048: for (j = 0; j < XVECLEN (x, i); j++)
2049: value += count_nonfixed_reads (XVECEXP (x, i, j));
2050: }
2051: }
2052: return value;
2053: }
2054:
2055:
2056: #if 0
2057: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
2058: Replace it with an instruction to load just the low bytes
2059: if the machine supports such an instruction,
2060: and insert above LOOP_START an instruction to clear the register. */
2061:
2062: static void
2063: constant_high_bytes (p, loop_start)
2064: rtx p, loop_start;
2065: {
2066: register rtx new;
2067: register int insn_code_number;
2068:
2069: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
2070: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
2071:
2072: new = gen_rtx (SET, VOIDmode,
2073: gen_rtx (STRICT_LOW_PART, VOIDmode,
2074: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
2075: SET_DEST (PATTERN (p)),
2076: 0)),
2077: XEXP (SET_SRC (PATTERN (p)), 0));
2078: insn_code_number = recog (new, p);
2079:
2080: if (insn_code_number)
2081: {
2082: register int i;
2083:
2084: /* Clear destination register before the loop. */
2085: emit_insn_before (gen_rtx (SET, VOIDmode,
2086: SET_DEST (PATTERN (p)),
2087: const0_rtx),
2088: loop_start);
2089:
2090: /* Inside the loop, just load the low part. */
2091: PATTERN (p) = new;
2092: }
2093: }
2094: #endif
2095:
2096: /* Scan a loop setting the variables `unknown_address_altered',
1.1.1.3 ! root 2097: `num_mem_sets', `loop_continue', loops_enclosed', `loop_has_call',
! 2098: and `loop_has_volatile'.
1.1 root 2099: Also, fill in the array `loop_store_mems'. */
2100:
2101: static void
2102: prescan_loop (start, end)
2103: rtx start, end;
2104: {
2105: register int level = 1;
2106: register rtx insn;
2107:
2108: unknown_address_altered = 0;
2109: loop_has_call = 0;
1.1.1.3 ! root 2110: loop_has_volatile = 0;
1.1 root 2111: loop_store_mems_idx = 0;
2112:
2113: num_mem_sets = 0;
2114: loops_enclosed = 1;
2115: loop_continue = 0;
2116:
2117: for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2118: insn = NEXT_INSN (insn))
2119: {
2120: if (GET_CODE (insn) == NOTE)
2121: {
2122: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2123: {
2124: ++level;
2125: /* Count number of loops contained in this one. */
2126: loops_enclosed++;
2127: }
2128: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2129: {
2130: --level;
2131: if (level == 0)
2132: {
2133: end = insn;
2134: break;
2135: }
2136: }
2137: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
2138: {
2139: if (level == 1)
2140: loop_continue = insn;
2141: }
2142: }
2143: else if (GET_CODE (insn) == CALL_INSN)
2144: {
2145: unknown_address_altered = 1;
2146: loop_has_call = 1;
2147: }
2148: else
2149: {
2150: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1.1.1.3 ! root 2151: {
! 2152: if (volatile_refs_p (PATTERN (insn)))
! 2153: loop_has_volatile = 1;
! 2154:
! 2155: note_stores (PATTERN (insn), note_addr_stored);
! 2156: }
1.1 root 2157: }
2158: }
2159: }
2160:
2161: /* Scan the function looking for loops. Record the start and end of each loop.
2162: Also mark as invalid loops any loops that contain a setjmp or are branched
2163: to from outside the loop. */
2164:
2165: static void
2166: find_and_verify_loops (f)
2167: rtx f;
2168: {
2169: rtx insn;
2170: int current_loop = -1;
2171: int next_loop = -1;
2172: int loop;
2173:
2174: /* If there are jumps to undefined labels,
2175: treat them as jumps out of any/all loops.
2176: This also avoids writing past end of tables when there are no loops. */
2177: uid_loop_num[0] = -1;
2178:
2179: /* Find boundaries of loops, mark which loops are contained within
2180: loops, and invalidate loops that have setjmp. */
2181:
2182: for (insn = f; insn; insn = NEXT_INSN (insn))
2183: {
2184: if (GET_CODE (insn) == NOTE)
2185: switch (NOTE_LINE_NUMBER (insn))
2186: {
2187: case NOTE_INSN_LOOP_BEG:
2188: loop_number_loop_starts[++next_loop] = insn;
2189: loop_number_loop_ends[next_loop] = 0;
2190: loop_outer_loop[next_loop] = current_loop;
2191: loop_invalid[next_loop] = 0;
2192: loop_number_exit_labels[next_loop] = 0;
2193: current_loop = next_loop;
2194: break;
2195:
2196: case NOTE_INSN_SETJMP:
2197: /* In this case, we must invalidate our current loop and any
2198: enclosing loop. */
2199: for (loop = current_loop; loop != -1; loop = loop_outer_loop[loop])
2200: {
2201: loop_invalid[loop] = 1;
2202: if (loop_dump_stream)
2203: fprintf (loop_dump_stream,
2204: "\nLoop at %d ignored due to setjmp.\n",
2205: INSN_UID (loop_number_loop_starts[loop]));
2206: }
2207: break;
2208:
2209: case NOTE_INSN_LOOP_END:
2210: if (current_loop == -1)
2211: abort ();
2212:
2213: loop_number_loop_ends[current_loop] = insn;
2214: current_loop = loop_outer_loop[current_loop];
2215: break;
2216:
2217: }
2218:
2219: /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2220: enclosing loop, but this doesn't matter. */
2221: uid_loop_num[INSN_UID (insn)] = current_loop;
2222: }
2223:
2224: /* Now scan all JUMP_INSN's in the function. If any branches into a loop
2225: that it is not contained within, that loop is marked invalid.
2226:
2227: Also look for blocks of code ending in an unconditional branch that
2228: exits the loop. If such a block is surrounded by a conditional
2229: branch around the block, move the block elsewhere (see below) and
2230: invert the jump to point to the code block. This may eliminate a
2231: label in our loop and will simplify processing by both us and a
2232: possible second cse pass. */
2233:
2234: for (insn = f; insn; insn = NEXT_INSN (insn))
2235: if (GET_CODE (insn) == JUMP_INSN)
2236: {
2237: int this_loop_num = uid_loop_num[INSN_UID (insn)];
2238:
2239: mark_loop_jump (PATTERN (insn), this_loop_num);
2240:
2241: /* See if this is an unconditional branch outside the loop. */
2242: if (this_loop_num != -1
2243: && (GET_CODE (PATTERN (insn)) == RETURN
2244: || (simplejump_p (insn)
2245: && (uid_loop_num[INSN_UID (JUMP_LABEL (insn))]
2246: != this_loop_num))))
2247: {
2248: rtx p;
2249: rtx our_next = next_real_insn (insn);
2250:
2251: /* Go backwards until we reach the start of the loop, a label,
2252: or a JUMP_INSN. */
2253: for (p = PREV_INSN (insn);
2254: GET_CODE (p) != CODE_LABEL
2255: && ! (GET_CODE (p) == NOTE
2256: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2257: && GET_CODE (p) != JUMP_INSN;
2258: p = PREV_INSN (p))
2259: ;
2260:
2261: /* If we stopped on a JUMP_INSN to the next insn after INSN,
2262: we have a block of code to try to move.
2263:
2264: We look backward and then forward from the target of INSN
2265: to find a BARRIER at the same loop depth as the target.
2266: If we find such a BARRIER, we make a new label for the start
2267: of the block, invert the jump in P and point it to that label,
2268: and move the block of code to the spot we found. */
2269:
2270: if (GET_CODE (p) == JUMP_INSN
2271: && JUMP_LABEL (p) != 0
2272: && condjump_p (p)
2273: && ! simplejump_p (p)
2274: && next_real_insn (JUMP_LABEL (p)) == our_next)
2275: {
2276: rtx target
2277: = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2278: int target_loop_num = uid_loop_num[INSN_UID (target)];
2279: rtx loc;
2280:
2281: for (loc = target; loc; loc = PREV_INSN (loc))
2282: if (GET_CODE (loc) == BARRIER
2283: && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2284: break;
2285:
2286: if (loc == 0)
2287: for (loc = target; loc; loc = NEXT_INSN (loc))
2288: if (GET_CODE (loc) == BARRIER
2289: && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2290: break;
2291:
2292: if (loc)
2293: {
2294: rtx cond_label = JUMP_LABEL (p);
2295: rtx new_label = get_label_after (p);
2296:
2297: /* Ensure our label doesn't go away. */
2298: LABEL_NUSES (cond_label)++;
2299:
2300: /* Verify that uid_loop_num is large enough and that
2301: we can invert P. */
2302: if (INSN_UID (new_label) < max_uid_for_loop
2303: && invert_jump (p, new_label))
2304: {
2305: rtx q, r;
2306:
2307: /* Include the BARRIER after INSN and copy the
2308: block after LOC. */
1.1.1.3 ! root 2309: new_label = squeeze_notes (new_label, NEXT_INSN (insn));
1.1 root 2310: reorder_insns (new_label, NEXT_INSN (insn), loc);
2311:
2312: /* All those insns are now in TARGET_LOOP_NUM. */
2313: for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
2314: q = NEXT_INSN (q))
2315: uid_loop_num[INSN_UID (q)] = target_loop_num;
2316:
2317: /* The label jumped to by INSN is no longer a loop exit.
2318: Unless INSN does not have a label (e.g., it is a
2319: RETURN insn), search loop_number_exit_labels to find
2320: its label_ref, and remove it. Also turn off
2321: LABEL_OUTSIDE_LOOP_P bit. */
2322: if (JUMP_LABEL (insn))
2323: {
2324: for (q = 0,
2325: r = loop_number_exit_labels[this_loop_num];
2326: r; q = r, r = LABEL_NEXTREF (r))
2327: if (XEXP (r, 0) == JUMP_LABEL (insn))
2328: {
2329: LABEL_OUTSIDE_LOOP_P (r) = 0;
2330: if (q)
2331: LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2332: else
2333: loop_number_exit_labels[this_loop_num]
2334: = LABEL_NEXTREF (r);
2335: break;
2336: }
2337:
2338: /* If we didn't find it, then something is wrong. */
2339: if (! r)
2340: abort ();
2341: }
2342:
2343: /* P is now a jump outside the loop, so it must be put
2344: in loop_number_exit_labels, and marked as such.
2345: The easiest way to do this is to just call
2346: mark_loop_jump again for P. */
2347: mark_loop_jump (PATTERN (p), this_loop_num);
2348:
2349: /* If INSN now jumps to the insn after it,
2350: delete INSN. */
2351: if (JUMP_LABEL (insn) != 0
2352: && (next_real_insn (JUMP_LABEL (insn))
2353: == next_real_insn (insn)))
2354: delete_insn (insn);
2355: }
2356:
2357: /* Continue the loop after where the conditional
2358: branch used to jump, since the only branch insn
2359: in the block (if it still remains) is an inter-loop
2360: branch and hence needs no processing. */
2361: insn = NEXT_INSN (cond_label);
2362:
2363: if (--LABEL_NUSES (cond_label) == 0)
2364: delete_insn (cond_label);
2365: }
2366: }
2367: }
2368: }
2369: }
2370:
2371: /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2372: loops it is contained in, mark the target loop invalid.
2373:
2374: For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2375:
2376: static void
2377: mark_loop_jump (x, loop_num)
2378: rtx x;
2379: int loop_num;
2380: {
2381: int dest_loop;
2382: int outer_loop;
2383: int i;
2384:
2385: switch (GET_CODE (x))
2386: {
2387: case PC:
2388: case USE:
2389: case CLOBBER:
2390: case REG:
2391: case MEM:
2392: case CONST_INT:
2393: case CONST_DOUBLE:
2394: case RETURN:
2395: return;
2396:
2397: case CONST:
2398: /* There could be a label reference in here. */
2399: mark_loop_jump (XEXP (x, 0), loop_num);
2400: return;
2401:
2402: case PLUS:
2403: case MINUS:
2404: case MULT:
2405: case LSHIFT:
2406: mark_loop_jump (XEXP (x, 0), loop_num);
2407: mark_loop_jump (XEXP (x, 1), loop_num);
2408: return;
2409:
2410: case SIGN_EXTEND:
2411: case ZERO_EXTEND:
2412: mark_loop_jump (XEXP (x, 0), loop_num);
2413: return;
2414:
2415: case LABEL_REF:
2416: dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))];
2417:
2418: /* Link together all labels that branch outside the loop. This
2419: is used by final_[bg]iv_value and the loop unrolling code. Also
2420: mark this LABEL_REF so we know that this branch should predict
2421: false. */
2422:
2423: if (dest_loop != loop_num && loop_num != -1)
2424: {
2425: LABEL_OUTSIDE_LOOP_P (x) = 1;
2426: LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
2427: loop_number_exit_labels[loop_num] = x;
2428: }
2429:
2430: /* If this is inside a loop, but not in the current loop or one enclosed
2431: by it, it invalidates at least one loop. */
2432:
2433: if (dest_loop == -1)
2434: return;
2435:
2436: /* We must invalidate every nested loop containing the target of this
2437: label, except those that also contain the jump insn. */
2438:
2439: for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
2440: {
2441: /* Stop when we reach a loop that also contains the jump insn. */
2442: for (outer_loop = loop_num; outer_loop != -1;
2443: outer_loop = loop_outer_loop[outer_loop])
2444: if (dest_loop == outer_loop)
2445: return;
2446:
2447: /* If we get here, we know we need to invalidate a loop. */
2448: if (loop_dump_stream && ! loop_invalid[dest_loop])
2449: fprintf (loop_dump_stream,
2450: "\nLoop at %d ignored due to multiple entry points.\n",
2451: INSN_UID (loop_number_loop_starts[dest_loop]));
2452:
2453: loop_invalid[dest_loop] = 1;
2454: }
2455: return;
2456:
2457: case SET:
2458: /* If this is not setting pc, ignore. */
2459: if (SET_DEST (x) == pc_rtx)
2460: mark_loop_jump (SET_SRC (x), loop_num);
2461: return;
2462:
2463: case IF_THEN_ELSE:
2464: mark_loop_jump (XEXP (x, 1), loop_num);
2465: mark_loop_jump (XEXP (x, 2), loop_num);
2466: return;
2467:
2468: case PARALLEL:
2469: case ADDR_VEC:
2470: for (i = 0; i < XVECLEN (x, 0); i++)
2471: mark_loop_jump (XVECEXP (x, 0, i), loop_num);
2472: return;
2473:
2474: case ADDR_DIFF_VEC:
2475: for (i = 0; i < XVECLEN (x, 1); i++)
2476: mark_loop_jump (XVECEXP (x, 1, i), loop_num);
2477: return;
2478:
2479: default:
2480: /* Nothing else should occur in a JUMP_INSN. */
2481: abort ();
2482: }
2483: }
2484:
2485: /* Return nonzero if there is a label in the range from
2486: insn INSN to and including the insn whose luid is END
2487: INSN must have an assigned luid (i.e., it must not have
2488: been previously created by loop.c). */
2489:
2490: static int
2491: labels_in_range_p (insn, end)
2492: rtx insn;
2493: int end;
2494: {
2495: while (insn && INSN_LUID (insn) <= end)
2496: {
2497: if (GET_CODE (insn) == CODE_LABEL)
2498: return 1;
2499: insn = NEXT_INSN (insn);
2500: }
2501:
2502: return 0;
2503: }
2504:
2505: /* Record that a memory reference X is being set. */
2506:
2507: static void
2508: note_addr_stored (x)
2509: rtx x;
2510: {
2511: register int i;
2512:
2513: if (x == 0 || GET_CODE (x) != MEM)
2514: return;
2515:
2516: /* Count number of memory writes.
2517: This affects heuristics in strength_reduce. */
2518: num_mem_sets++;
2519:
2520: if (unknown_address_altered)
2521: return;
2522:
2523: for (i = 0; i < loop_store_mems_idx; i++)
2524: if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0))
2525: && MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
2526: {
2527: /* We are storing at the same address as previously noted. Save the
2528: wider reference, treating BLKmode as wider. */
2529: if (GET_MODE (x) == BLKmode
2530: || (GET_MODE_SIZE (GET_MODE (x))
2531: > GET_MODE_SIZE (GET_MODE (loop_store_mems[i]))))
2532: loop_store_mems[i] = x;
2533: break;
2534: }
2535:
2536: if (i == NUM_STORES)
2537: unknown_address_altered = 1;
2538:
2539: else if (i == loop_store_mems_idx)
2540: loop_store_mems[loop_store_mems_idx++] = x;
2541: }
2542:
2543: /* Return nonzero if the rtx X is invariant over the current loop.
2544:
2545: The value is 2 if we refer to something only conditionally invariant.
2546:
2547: If `unknown_address_altered' is nonzero, no memory ref is invariant.
2548: Otherwise, a memory ref is invariant if it does not conflict with
2549: anything stored in `loop_store_mems'. */
2550:
2551: int
2552: invariant_p (x)
2553: register rtx x;
2554: {
2555: register int i;
2556: register enum rtx_code code;
2557: register char *fmt;
2558: int conditional = 0;
2559:
2560: if (x == 0)
2561: return 1;
2562: code = GET_CODE (x);
2563: switch (code)
2564: {
2565: case CONST_INT:
2566: case CONST_DOUBLE:
2567: case SYMBOL_REF:
2568: case CONST:
2569: return 1;
2570:
2571: case LABEL_REF:
2572: /* A LABEL_REF is normally invariant, however, if we are unrolling
2573: loops, and this label is inside the loop, then it isn't invariant.
2574: This is because each unrolled copy of the loop body will have
2575: a copy of this label. If this was invariant, then an insn loading
2576: the address of this label into a register might get moved outside
2577: the loop, and then each loop body would end up using the same label.
2578:
2579: We don't know the loop bounds here though, so just fail for all
2580: labels. */
2581: if (flag_unroll_loops)
2582: return 0;
2583: else
2584: return 1;
2585:
2586: case PC:
2587: case CC0:
2588: case UNSPEC_VOLATILE:
2589: return 0;
2590:
2591: case REG:
2592: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
2593: since the reg might be set by initialization within the loop. */
2594: if (x == frame_pointer_rtx || x == arg_pointer_rtx)
2595: return 1;
2596: if (loop_has_call
2597: && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
2598: return 0;
2599: if (n_times_set[REGNO (x)] < 0)
2600: return 2;
2601: return n_times_set[REGNO (x)] == 0;
2602:
2603: case MEM:
2604: /* Read-only items (such as constants in a constant pool) are
2605: invariant if their address is. */
2606: if (RTX_UNCHANGING_P (x))
2607: break;
2608:
2609: /* If we filled the table (or had a subroutine call), any location
2610: in memory could have been clobbered. */
2611: if (unknown_address_altered
2612: /* Don't mess with volatile memory references. */
2613: || MEM_VOLATILE_P (x))
2614: return 0;
2615:
2616: /* See if there is any dependence between a store and this load. */
2617: for (i = loop_store_mems_idx - 1; i >= 0; i--)
2618: if (true_dependence (loop_store_mems[i], x))
2619: return 0;
2620:
2621: /* It's not invalidated by a store in memory
2622: but we must still verify the address is invariant. */
2623: break;
2624:
2625: case ASM_OPERANDS:
2626: /* Don't mess with insns declared volatile. */
2627: if (MEM_VOLATILE_P (x))
2628: return 0;
2629: }
2630:
2631: fmt = GET_RTX_FORMAT (code);
2632: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2633: {
2634: if (fmt[i] == 'e')
2635: {
2636: int tem = invariant_p (XEXP (x, i));
2637: if (tem == 0)
2638: return 0;
2639: if (tem == 2)
2640: conditional = 1;
2641: }
2642: else if (fmt[i] == 'E')
2643: {
2644: register int j;
2645: for (j = 0; j < XVECLEN (x, i); j++)
2646: {
2647: int tem = invariant_p (XVECEXP (x, i, j));
2648: if (tem == 0)
2649: return 0;
2650: if (tem == 2)
2651: conditional = 1;
2652: }
2653:
2654: }
2655: }
2656:
2657: return 1 + conditional;
2658: }
2659:
2660: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
2661: which is SIZE bytes starting at BASE. */
2662:
2663: int
2664: addr_overlap_p (other, base, size)
2665: rtx other;
2666: rtx base;
2667: int size;
2668: {
2669: int start = 0, end;
2670:
2671: if (GET_CODE (base) == CONST)
2672: base = XEXP (base, 0);
2673: if (GET_CODE (base) == PLUS
2674: && GET_CODE (XEXP (base, 1)) == CONST_INT)
2675: {
2676: start = INTVAL (XEXP (base, 1));
2677: base = XEXP (base, 0);
2678: }
2679:
2680: end = start + size;
2681: return refers_to_mem_p (other, base, start, end);
2682: }
2683:
2684: /* Return nonzero if all the insns in the loop that set REG
2685: are INSN and the immediately following insns,
2686: and if each of those insns sets REG in an invariant way
2687: (not counting uses of REG in them).
2688:
2689: The value is 2 if some of these insns are only conditionally invariant.
2690:
2691: We assume that INSN itself is the first set of REG
2692: and that its source is invariant. */
2693:
2694: static int
2695: consec_sets_invariant_p (reg, n_sets, insn)
2696: int n_sets;
2697: rtx reg, insn;
2698: {
2699: register rtx p = insn;
2700: register int regno = REGNO (reg);
2701: rtx temp;
2702: /* Number of sets we have to insist on finding after INSN. */
2703: int count = n_sets - 1;
2704: int old = n_times_set[regno];
2705: int value = 0;
2706: int this;
2707:
2708: /* If N_SETS hit the limit, we can't rely on its value. */
2709: if (n_sets == 127)
2710: return 0;
2711:
2712: n_times_set[regno] = 0;
2713:
2714: while (count > 0)
2715: {
2716: register enum rtx_code code;
2717: rtx set;
2718:
2719: p = NEXT_INSN (p);
2720: code = GET_CODE (p);
2721:
2722: /* If library call, skip to end of of it. */
2723: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
2724: p = XEXP (temp, 0);
2725:
2726: this = 0;
2727: if (code == INSN
2728: && (set = single_set (p))
2729: && GET_CODE (SET_DEST (set)) == REG
2730: && REGNO (SET_DEST (set)) == regno)
2731: {
2732: this = invariant_p (SET_SRC (set));
2733: if (this != 0)
2734: value |= this;
2735: else if (temp = find_reg_note (p, REG_EQUAL, 0))
2736: {
2737: this = invariant_p (XEXP (temp, 0));
2738: if (this != 0)
2739: value |= this;
2740: }
2741: }
2742: if (this != 0)
2743: count--;
2744: else if (code != NOTE)
2745: {
2746: n_times_set[regno] = old;
2747: return 0;
2748: }
2749: }
2750:
2751: n_times_set[regno] = old;
2752: /* If invariant_p ever returned 2, we return 2. */
2753: return 1 + (value & 2);
2754: }
2755:
2756: #if 0
2757: /* I don't think this condition is sufficient to allow INSN
2758: to be moved, so we no longer test it. */
2759:
2760: /* Return 1 if all insns in the basic block of INSN and following INSN
2761: that set REG are invariant according to TABLE. */
2762:
2763: static int
2764: all_sets_invariant_p (reg, insn, table)
2765: rtx reg, insn;
2766: short *table;
2767: {
2768: register rtx p = insn;
2769: register int regno = REGNO (reg);
2770:
2771: while (1)
2772: {
2773: register enum rtx_code code;
2774: p = NEXT_INSN (p);
2775: code = GET_CODE (p);
2776: if (code == CODE_LABEL || code == JUMP_INSN)
2777: return 1;
2778: if (code == INSN && GET_CODE (PATTERN (p)) == SET
2779: && GET_CODE (SET_DEST (PATTERN (p))) == REG
2780: && REGNO (SET_DEST (PATTERN (p))) == regno)
2781: {
2782: if (!invariant_p (SET_SRC (PATTERN (p)), table))
2783: return 0;
2784: }
2785: }
2786: }
2787: #endif /* 0 */
2788:
2789: /* Look at all uses (not sets) of registers in X. For each, if it is
2790: the single use, set USAGE[REGNO] to INSN; if there was a previous use in
2791: a different insn, set USAGE[REGNO] to const0_rtx. */
2792:
2793: static void
2794: find_single_use_in_loop (insn, x, usage)
2795: rtx insn;
2796: rtx x;
2797: rtx *usage;
2798: {
2799: enum rtx_code code = GET_CODE (x);
2800: char *fmt = GET_RTX_FORMAT (code);
2801: int i, j;
2802:
2803: if (code == REG)
2804: usage[REGNO (x)]
2805: = (usage[REGNO (x)] != 0 && usage[REGNO (x)] != insn)
2806: ? const0_rtx : insn;
2807:
2808: else if (code == SET)
2809: {
2810: /* Don't count SET_DEST if it is a REG; otherwise count things
2811: in SET_DEST because if a register is partially modified, it won't
2812: show up as a potential movable so we don't care how USAGE is set
2813: for it. */
2814: if (GET_CODE (SET_DEST (x)) != REG)
2815: find_single_use_in_loop (insn, SET_DEST (x), usage);
2816: find_single_use_in_loop (insn, SET_SRC (x), usage);
2817: }
2818: else
2819: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2820: {
2821: if (fmt[i] == 'e' && XEXP (x, i) != 0)
2822: find_single_use_in_loop (insn, XEXP (x, i), usage);
2823: else if (fmt[i] == 'E')
2824: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2825: find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
2826: }
2827: }
2828:
2829: /* Increment N_TIMES_SET at the index of each register
2830: that is modified by an insn between FROM and TO.
2831: If the value of an element of N_TIMES_SET becomes 127 or more,
2832: stop incrementing it, to avoid overflow.
2833:
2834: Store in SINGLE_USAGE[I] the single insn in which register I is
2835: used, if it is only used once. Otherwise, it is set to 0 (for no
2836: uses) or const0_rtx for more than one use. This parameter may be zero,
2837: in which case this processing is not done.
2838:
2839: Store in *COUNT_PTR the number of actual instruction
2840: in the loop. We use this to decide what is worth moving out. */
2841:
2842: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
2843: In that case, it is the insn that last set reg n. */
2844:
2845: static void
2846: count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
2847: register rtx from, to;
2848: char *may_not_move;
2849: rtx *single_usage;
2850: int *count_ptr;
2851: int nregs;
2852: {
2853: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
2854: register rtx insn;
2855: register int count = 0;
2856: register rtx dest;
2857:
2858: bzero (last_set, nregs * sizeof (rtx));
2859: for (insn = from; insn != to; insn = NEXT_INSN (insn))
2860: {
2861: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2862: {
2863: ++count;
2864:
2865: /* If requested, record registers that have exactly one use. */
2866: if (single_usage)
2867: {
2868: find_single_use_in_loop (insn, PATTERN (insn), single_usage);
2869:
2870: /* Include uses in REG_EQUAL notes. */
2871: if (REG_NOTES (insn))
2872: find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
2873: }
2874:
2875: if (GET_CODE (PATTERN (insn)) == CLOBBER
2876: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
2877: /* Don't move a reg that has an explicit clobber.
2878: We might do so sometimes, but it's not worth the pain. */
2879: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
2880:
2881: if (GET_CODE (PATTERN (insn)) == SET
2882: || GET_CODE (PATTERN (insn)) == CLOBBER)
2883: {
2884: dest = SET_DEST (PATTERN (insn));
2885: while (GET_CODE (dest) == SUBREG
2886: || GET_CODE (dest) == ZERO_EXTRACT
2887: || GET_CODE (dest) == SIGN_EXTRACT
2888: || GET_CODE (dest) == STRICT_LOW_PART)
2889: dest = XEXP (dest, 0);
2890: if (GET_CODE (dest) == REG)
2891: {
2892: register int regno = REGNO (dest);
2893: /* If this is the first setting of this reg
2894: in current basic block, and it was set before,
2895: it must be set in two basic blocks, so it cannot
2896: be moved out of the loop. */
2897: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2898: may_not_move[regno] = 1;
2899: /* If this is not first setting in current basic block,
2900: see if reg was used in between previous one and this.
2901: If so, neither one can be moved. */
2902: if (last_set[regno] != 0
2903: && reg_used_between_p (dest, last_set[regno], insn))
2904: may_not_move[regno] = 1;
2905: if (n_times_set[regno] < 127)
2906: ++n_times_set[regno];
2907: last_set[regno] = insn;
2908: }
2909: }
2910: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2911: {
2912: register int i;
2913: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2914: {
2915: register rtx x = XVECEXP (PATTERN (insn), 0, i);
2916: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
2917: /* Don't move a reg that has an explicit clobber.
2918: It's not worth the pain to try to do it correctly. */
2919: may_not_move[REGNO (XEXP (x, 0))] = 1;
2920:
2921: if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
2922: {
2923: dest = SET_DEST (x);
2924: while (GET_CODE (dest) == SUBREG
2925: || GET_CODE (dest) == ZERO_EXTRACT
2926: || GET_CODE (dest) == SIGN_EXTRACT
2927: || GET_CODE (dest) == STRICT_LOW_PART)
2928: dest = XEXP (dest, 0);
2929: if (GET_CODE (dest) == REG)
2930: {
2931: register int regno = REGNO (dest);
2932: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2933: may_not_move[regno] = 1;
2934: if (last_set[regno] != 0
2935: && reg_used_between_p (dest, last_set[regno], insn))
2936: may_not_move[regno] = 1;
2937: if (n_times_set[regno] < 127)
2938: ++n_times_set[regno];
2939: last_set[regno] = insn;
2940: }
2941: }
2942: }
2943: }
2944: }
2945: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
2946: bzero (last_set, nregs * sizeof (rtx));
2947: }
2948: *count_ptr = count;
2949: }
2950:
2951: /* Given a loop that is bounded by LOOP_START and LOOP_END
2952: and that is entered at SCAN_START,
2953: return 1 if the register set in SET contained in insn INSN is used by
2954: any insn that precedes INSN in cyclic order starting
2955: from the loop entry point.
2956:
2957: We don't want to use INSN_LUID here because if we restrict INSN to those
2958: that have a valid INSN_LUID, it means we cannot move an invariant out
2959: from an inner loop past two loops. */
2960:
2961: static int
2962: loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
2963: rtx set, insn, loop_start, scan_start, loop_end;
2964: {
2965: rtx reg = SET_DEST (set);
2966: rtx p;
2967:
2968: /* Scan forward checking for register usage. If we hit INSN, we
2969: are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
2970: for (p = scan_start; p != insn; p = NEXT_INSN (p))
2971: {
2972: if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
2973: && reg_overlap_mentioned_p (reg, PATTERN (p)))
2974: return 1;
2975:
2976: if (p == loop_end)
2977: p = loop_start;
2978: }
2979:
2980: return 0;
2981: }
2982:
2983: /* A "basic induction variable" or biv is a pseudo reg that is set
2984: (within this loop) only by incrementing or decrementing it. */
2985: /* A "general induction variable" or giv is a pseudo reg whose
2986: value is a linear function of a biv. */
2987:
2988: /* Bivs are recognized by `basic_induction_var';
2989: Givs by `general_induct_var'. */
2990:
2991: /* Indexed by register number, indicates whether or not register is an
2992: induction variable, and if so what type. */
2993:
2994: enum iv_mode *reg_iv_type;
2995:
2996: /* Indexed by register number, contains pointer to `struct induction'
2997: if register is an induction variable. This holds general info for
2998: all induction variables. */
2999:
3000: struct induction **reg_iv_info;
3001:
3002: /* Indexed by register number, contains pointer to `struct iv_class'
3003: if register is a basic induction variable. This holds info describing
3004: the class (a related group) of induction variables that the biv belongs
3005: to. */
3006:
3007: struct iv_class **reg_biv_class;
3008:
3009: /* The head of a list which links together (via the next field)
3010: every iv class for the current loop. */
3011:
3012: struct iv_class *loop_iv_list;
3013:
3014: /* Communication with routines called via `note_stores'. */
3015:
3016: static rtx note_insn;
3017:
3018: /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3019:
3020: static rtx addr_placeholder;
3021:
3022: /* ??? Unfinished optimizations, and possible future optimizations,
3023: for the strength reduction code. */
3024:
3025: /* ??? There is one more optimization you might be interested in doing: to
3026: allocate pseudo registers for frequently-accessed memory locations.
3027: If the same memory location is referenced each time around, it might
3028: be possible to copy it into a register before and out after.
3029: This is especially useful when the memory location is a variable which
3030: is in a stack slot because somewhere its address is taken. If the
3031: loop doesn't contain a function call and the variable isn't volatile,
3032: it is safe to keep the value in a register for the duration of the
3033: loop. One tricky thing is that the copying of the value back from the
3034: register has to be done on all exits from the loop. You need to check that
3035: all the exits from the loop go to the same place. */
3036:
3037: /* ??? The interaction of biv elimination, and recognition of 'constant'
3038: bivs, may cause problems. */
3039:
3040: /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3041: performance problems.
3042:
3043: Perhaps don't eliminate things that can be combined with an addressing
3044: mode. Find all givs that have the same biv, mult_val, and add_val;
3045: then for each giv, check to see if its only use dies in a following
3046: memory address. If so, generate a new memory address and check to see
3047: if it is valid. If it is valid, then store the modified memory address,
3048: otherwise, mark the giv as not done so that it will get its own iv. */
3049:
3050: /* ??? Could try to optimize branches when it is known that a biv is always
3051: positive. */
3052:
3053: /* ??? When replace a biv in a compare insn, we should replace with closest
3054: giv so that an optimized branch can still be recognized by the combiner,
3055: e.g. the VAX acb insn. */
3056:
3057: /* ??? Many of the checks involving uid_luid could be simplified if regscan
3058: was rerun in loop_optimize whenever a register was added or moved.
3059: Also, some of the optimizations could be a little less conservative. */
3060:
3061: /* Perform strength reduction and induction variable elimination. */
3062:
3063: /* Pseudo registers created during this function will be beyond the last
3064: valid index in several tables including n_times_set and regno_last_uid.
3065: This does not cause a problem here, because the added registers cannot be
3066: givs outside of their loop, and hence will never be reconsidered.
3067: But scan_loop must check regnos to make sure they are in bounds. */
3068:
3069: static void
3070: strength_reduce (scan_start, end, loop_top, insn_count,
3071: loop_start, loop_end)
3072: rtx scan_start;
3073: rtx end;
3074: rtx loop_top;
3075: int insn_count;
3076: rtx loop_start;
3077: rtx loop_end;
3078: {
3079: rtx p;
3080: rtx set;
3081: rtx inc_val;
3082: rtx mult_val;
3083: rtx dest_reg;
3084: /* This is 1 if current insn is not executed at least once for every loop
3085: iteration. */
3086: int not_every_iteration = 0;
1.1.1.3 ! root 3087: /* This is 1 if current insn may be executed more than once for every
! 3088: loop iteration. */
! 3089: int maybe_multiple = 0;
1.1 root 3090: /* Temporary list pointers for traversing loop_iv_list. */
3091: struct iv_class *bl, **backbl;
3092: /* Ratio of extra register life span we can justify
3093: for saving an instruction. More if loop doesn't call subroutines
3094: since in that case saving an insn makes more difference
3095: and more registers are available. */
3096: /* ??? could set this to last value of threshold in move_movables */
3097: int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3098: /* Map of pseudo-register replacements. */
3099: rtx *reg_map;
3100: int call_seen;
3101: rtx test;
3102: rtx end_insert_before;
3103:
3104: reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop
3105: * sizeof (enum iv_mode *));
3106: bzero ((char *) reg_iv_type, max_reg_before_loop * sizeof (enum iv_mode *));
3107: reg_iv_info = (struct induction **)
3108: alloca (max_reg_before_loop * sizeof (struct induction *));
3109: bzero ((char *) reg_iv_info, (max_reg_before_loop
3110: * sizeof (struct induction *)));
3111: reg_biv_class = (struct iv_class **)
3112: alloca (max_reg_before_loop * sizeof (struct iv_class *));
3113: bzero ((char *) reg_biv_class, (max_reg_before_loop
3114: * sizeof (struct iv_class *)));
3115:
3116: loop_iv_list = 0;
3117: addr_placeholder = gen_reg_rtx (Pmode);
3118:
3119: /* Save insn immediately after the loop_end. Insns inserted after loop_end
3120: must be put before this insn, so that they will appear in the right
3121: order (i.e. loop order). */
3122:
3123: end_insert_before = NEXT_INSN (loop_end);
3124:
3125: /* Scan through loop to find all possible bivs. */
3126:
3127: p = scan_start;
3128: while (1)
3129: {
3130: p = NEXT_INSN (p);
3131: /* At end of a straight-in loop, we are done.
3132: At end of a loop entered at the bottom, scan the top. */
3133: if (p == scan_start)
3134: break;
3135: if (p == end)
3136: {
3137: if (loop_top != 0)
3138: p = NEXT_INSN (loop_top);
3139: else
3140: break;
3141: if (p == scan_start)
3142: break;
3143: }
3144:
3145: if (GET_CODE (p) == INSN
3146: && (set = single_set (p))
3147: && GET_CODE (SET_DEST (set)) == REG)
3148: {
3149: dest_reg = SET_DEST (set);
3150: if (REGNO (dest_reg) < max_reg_before_loop
3151: && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
3152: && reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT)
3153: {
3154: if (basic_induction_var (SET_SRC (set), dest_reg,
3155: &inc_val, &mult_val))
3156: {
3157: /* It is a possible basic induction variable.
3158: Create and initialize an induction structure for it. */
3159:
3160: struct induction *v
3161: = (struct induction *) alloca (sizeof (struct induction));
3162:
3163: record_biv (v, p, dest_reg, inc_val, mult_val,
1.1.1.3 ! root 3164: not_every_iteration, maybe_multiple);
1.1 root 3165: reg_iv_type[REGNO (dest_reg)] = BASIC_INDUCT;
3166: }
3167: else if (REGNO (dest_reg) < max_reg_before_loop)
3168: reg_iv_type[REGNO (dest_reg)] = NOT_BASIC_INDUCT;
3169: }
3170: }
3171:
1.1.1.3 ! root 3172: /* Past CODE_LABEL, we get to insns that may be executed multiple
! 3173: times. The only way we can be sure that they can't is if every
! 3174: every jump insn between here and the end of the loop either
! 3175: returns, exits the loop, or is a forward jump. */
! 3176:
! 3177: if (GET_CODE (p) == CODE_LABEL)
! 3178: {
! 3179: rtx insn = p;
! 3180:
! 3181: maybe_multiple = 0;
! 3182:
! 3183: while (1)
! 3184: {
! 3185: insn = NEXT_INSN (insn);
! 3186: if (insn == scan_start)
! 3187: break;
! 3188: if (insn == end)
! 3189: {
! 3190: if (loop_top != 0)
! 3191: insn = NEXT_INSN (loop_top);
! 3192: else
! 3193: break;
! 3194: if (insn == scan_start)
! 3195: break;
! 3196: }
! 3197:
! 3198: if (GET_CODE (insn) == JUMP_INSN
! 3199: && GET_CODE (PATTERN (insn)) != RETURN
! 3200: && (! condjump_p (insn)
! 3201: || (JUMP_LABEL (insn) != 0
! 3202: && (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
! 3203: || INSN_UID (insn) >= max_uid_for_loop
! 3204: || (INSN_LUID (JUMP_LABEL (insn))
! 3205: < INSN_LUID (insn))))))
! 3206: {
! 3207: maybe_multiple = 1;
! 3208: break;
! 3209: }
! 3210: }
! 3211: }
! 3212:
1.1 root 3213: /* Past a label or a jump, we get to insns for which we can't count
3214: on whether or how many times they will be executed during each
3215: iteration. */
3216: /* This code appears in three places, once in scan_loop, and twice
3217: in strength_reduce. */
3218: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3219: /* If we enter the loop in the middle, and scan around to the
3220: beginning, don't set not_every_iteration for that.
3221: This can be any kind of jump, since we want to know if insns
3222: will be executed if the loop is executed. */
3223: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3224: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3225: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3226: not_every_iteration = 1;
3227:
3228: /* At the virtual top of a converted loop, insns are again known to
3229: be executed each iteration: logically, the loop begins here
3230: even though the exit code has been duplicated. */
3231:
3232: else if (GET_CODE (p) == NOTE
3233: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3234: not_every_iteration = 0;
3235:
3236: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3237: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3238: or not an insn is known to be executed each iteration of the
3239: loop, whether or not any iterations are known to occur.
3240:
3241: Therefore, if we have just passed a label and have no more labels
3242: between here and the test insn of the loop, we know these insns
3243: will be executed each iteration. This can also happen if we
3244: have just passed a jump, for example, when there are nested loops. */
3245:
3246: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3247: && no_labels_between_p (p, loop_end))
3248: not_every_iteration = 0;
3249: }
3250:
3251: /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3252: Make a sanity check against n_times_set. */
3253: for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next)
3254: {
3255: if (reg_iv_type[bl->regno] != BASIC_INDUCT
3256: /* Above happens if register modified by subreg, etc. */
3257: /* Make sure it is not recognized as a basic induction var: */
3258: || n_times_set[bl->regno] != bl->biv_count
3259: /* If never incremented, it is invariant that we decided not to
3260: move. So leave it alone. */
3261: || ! bl->incremented)
3262: {
3263: if (loop_dump_stream)
3264: fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3265: bl->regno,
3266: (reg_iv_type[bl->regno] != BASIC_INDUCT
3267: ? "not induction variable"
3268: : (! bl->incremented ? "never incremented"
3269: : "count error")));
3270:
3271: reg_iv_type[bl->regno] = NOT_BASIC_INDUCT;
3272: *backbl = bl->next;
3273: }
3274: else
3275: {
3276: backbl = &bl->next;
3277:
3278: if (loop_dump_stream)
3279: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3280: }
3281: }
3282:
3283: /* Exit if there are no bivs. */
3284: if (! loop_iv_list)
3285: {
3286: /* Can still unroll the loop anyways, but indicate that there is no
3287: strength reduction info available. */
3288: if (flag_unroll_loops)
3289: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 0);
3290:
3291: return;
3292: }
3293:
3294: /* Find initial value for each biv by searching backwards from loop_start,
3295: halting at first label. Also record any test condition. */
3296:
3297: call_seen = 0;
3298: for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3299: {
3300: note_insn = p;
3301:
3302: if (GET_CODE (p) == CALL_INSN)
3303: call_seen = 1;
3304:
3305: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3306: || GET_CODE (p) == CALL_INSN)
3307: note_stores (PATTERN (p), record_initial);
3308:
3309: /* Record any test of a biv that branches around the loop if no store
3310: between it and the start of loop. We only care about tests with
3311: constants and registers and only certain of those. */
3312: if (GET_CODE (p) == JUMP_INSN
3313: && JUMP_LABEL (p) != 0
3314: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3315: && (test = get_condition_for_loop (p)) != 0
3316: && GET_CODE (XEXP (test, 0)) == REG
3317: && REGNO (XEXP (test, 0)) < max_reg_before_loop
3318: && (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3319: && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3320: && bl->init_insn == 0)
3321: {
3322: /* If an NE test, we have an initial value! */
3323: if (GET_CODE (test) == NE)
3324: {
3325: bl->init_insn = p;
3326: bl->init_set = gen_rtx (SET, VOIDmode,
3327: XEXP (test, 0), XEXP (test, 1));
3328: }
3329: else
3330: bl->initial_test = test;
3331: }
3332: }
3333:
3334: /* Look at the each biv and see if we can say anything better about its
3335: initial value from any initializing insns set up above. (This is done
3336: in two passes to avoid missing SETs in a PARALLEL.) */
3337: for (bl = loop_iv_list; bl; bl = bl->next)
3338: {
3339: rtx src;
3340:
3341: if (! bl->init_insn)
3342: continue;
3343:
3344: src = SET_SRC (bl->init_set);
3345:
3346: if (loop_dump_stream)
3347: fprintf (loop_dump_stream,
3348: "Biv %d initialized at insn %d: initial value ",
3349: bl->regno, INSN_UID (bl->init_insn));
3350:
3351: if (valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3352: {
3353: bl->initial_value = src;
3354:
3355: if (loop_dump_stream)
3356: {
3357: if (GET_CODE (src) == CONST_INT)
3358: fprintf (loop_dump_stream, "%d\n", INTVAL (src));
3359: else
3360: {
3361: print_rtl (loop_dump_stream, src);
3362: fprintf (loop_dump_stream, "\n");
3363: }
3364: }
3365: }
3366: else
3367: {
3368: /* Biv initial value is not simple move,
1.1.1.2 root 3369: so let it keep initial value of "itself". */
1.1 root 3370:
3371: if (loop_dump_stream)
3372: fprintf (loop_dump_stream, "is complex\n");
3373: }
3374: }
3375:
3376: /* Search the loop for general induction variables. */
3377:
3378: /* A register is a giv if: it is only set once, it is a function of a
3379: biv and a constant (or invariant), and it is not a biv. */
3380:
3381: not_every_iteration = 0;
3382: p = scan_start;
3383: while (1)
3384: {
3385: p = NEXT_INSN (p);
3386: /* At end of a straight-in loop, we are done.
3387: At end of a loop entered at the bottom, scan the top. */
3388: if (p == scan_start)
3389: break;
3390: if (p == end)
3391: {
3392: if (loop_top != 0)
3393: p = NEXT_INSN (loop_top);
3394: else
3395: break;
3396: if (p == scan_start)
3397: break;
3398: }
3399:
3400: /* Look for a general induction variable in a register. */
3401: if (GET_CODE (p) == INSN
3402: && (set = single_set (p))
3403: && GET_CODE (SET_DEST (set)) == REG
3404: && ! may_not_optimize[REGNO (SET_DEST (set))])
3405: {
3406: rtx src_reg;
3407: rtx add_val;
3408: rtx mult_val;
3409: int benefit;
3410: rtx regnote = 0;
3411:
3412: dest_reg = SET_DEST (set);
3413: if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
3414: continue;
3415:
3416: if (/* SET_SRC is a giv. */
3417: ((benefit = general_induction_var (SET_SRC (set),
3418: &src_reg, &add_val,
3419: &mult_val))
3420: /* Equivalent expression is a giv. */
3421: || ((regnote = find_reg_note (p, REG_EQUAL, 0))
3422: && (benefit = general_induction_var (XEXP (regnote, 0),
3423: &src_reg,
3424: &add_val, &mult_val))))
3425: /* Don't try to handle any regs made by loop optimization.
3426: We have nothing on them in regno_first_uid, etc. */
3427: && REGNO (dest_reg) < max_reg_before_loop
3428: /* Don't recognize a BASIC_INDUCT_VAR here. */
3429: && dest_reg != src_reg
3430: /* This must be the only place where the register is set. */
3431: && (n_times_set[REGNO (dest_reg)] == 1
3432: /* or all sets must be consecutive and make a giv. */
3433: || (benefit = consec_sets_giv (benefit, p,
3434: src_reg, dest_reg,
3435: &add_val, &mult_val))))
3436: {
3437: int count;
3438: struct induction *v
3439: = (struct induction *) alloca (sizeof (struct induction));
3440: rtx temp;
3441:
3442: /* If this is a library call, increase benefit. */
3443: if (find_reg_note (p, REG_RETVAL, 0))
3444: benefit += libcall_benefit (p);
3445:
3446: /* Skip the consecutive insns, if there are any. */
3447: for (count = n_times_set[REGNO (dest_reg)] - 1;
3448: count > 0; count--)
3449: {
3450: /* If first insn of libcall sequence, skip to end.
3451: Do this at start of loop, since INSN is guaranteed to
3452: be an insn here. */
3453: if (GET_CODE (p) != NOTE
3454: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
3455: p = XEXP (temp, 0);
3456:
3457: do p = NEXT_INSN (p);
3458: while (GET_CODE (p) == NOTE);
3459: }
3460:
3461: record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
3462: DEST_REG, not_every_iteration, 0, loop_start,
3463: loop_end);
3464:
3465: }
3466: }
3467:
3468: #ifndef DONT_REDUCE_ADDR
3469: /* Look for givs which are memory addresses. */
3470: /* This resulted in worse code on a VAX 8600. I wonder if it
3471: still does. */
3472: if (GET_CODE (p) == INSN)
3473: find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
3474: loop_end);
3475: #endif
3476:
3477: /* Update the status of whether giv can derive other givs. This can
3478: change when we pass a label or an insn that updates a biv. */
1.1.1.3 ! root 3479: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
! 3480: || GET_CODE (p) == CODE_LABEL)
1.1 root 3481: update_giv_derive (p);
3482:
3483: /* Past a label or a jump, we get to insns for which we can't count
3484: on whether or how many times they will be executed during each
3485: iteration. */
3486: /* This code appears in three places, once in scan_loop, and twice
3487: in strength_reduce. */
3488: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3489: /* If we enter the loop in the middle, and scan around
3490: to the beginning, don't set not_every_iteration for that.
3491: This can be any kind of jump, since we want to know if insns
3492: will be executed if the loop is executed. */
3493: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3494: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3495: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3496: not_every_iteration = 1;
3497:
3498: /* At the virtual top of a converted loop, insns are again known to
3499: be executed each iteration: logically, the loop begins here
3500: even though the exit code has been duplicated. */
3501:
3502: else if (GET_CODE (p) == NOTE
3503: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3504: not_every_iteration = 0;
3505:
3506: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3507: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3508: or not an insn is known to be executed each iteration of the
3509: loop, whether or not any iterations are known to occur.
3510:
3511: Therefore, if we have just passed a label and have no more labels
3512: between here and the test insn of the loop, we know these insns
3513: will be executed each iteration. */
3514:
3515: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3516: && no_labels_between_p (p, loop_end))
3517: not_every_iteration = 0;
3518: }
3519:
3520: /* Try to calculate and save the number of loop iterations. This is
3521: set to zero if the actual number can not be calculated. This must
3522: be called after all giv's have been identified, since otherwise it may
3523: fail if the iteration variable is a giv. */
3524:
3525: loop_n_iterations = loop_iterations (loop_start, loop_end);
3526:
3527: /* Now for each giv for which we still don't know whether or not it is
3528: replaceable, check to see if it is replaceable because its final value
3529: can be calculated. This must be done after loop_iterations is called,
3530: so that final_giv_value will work correctly. */
3531:
3532: for (bl = loop_iv_list; bl; bl = bl->next)
3533: {
3534: struct induction *v;
3535:
3536: for (v = bl->giv; v; v = v->next_iv)
3537: if (! v->replaceable && ! v->not_replaceable)
3538: check_final_value (v, loop_start, loop_end);
3539: }
3540:
3541: /* Try to prove that the loop counter variable (if any) is always
3542: nonnegative; if so, record that fact with a REG_NONNEG note
3543: so that "decrement and branch until zero" insn can be used. */
3544: check_dbra_loop (loop_end, insn_count, loop_start);
3545:
3546: /* Create reg_map to hold substitutions for replaceable giv regs. */
3547: reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
3548: bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
3549:
3550: /* Examine each iv class for feasibility of strength reduction/induction
3551: variable elimination. */
3552:
3553: for (bl = loop_iv_list; bl; bl = bl->next)
3554: {
3555: struct induction *v;
3556: int benefit;
3557: int all_reduced;
3558: rtx final_value = 0;
3559:
3560: /* Test whether it will be possible to eliminate this biv
3561: provided all givs are reduced. This is possible if either
3562: the reg is not used outside the loop, or we can compute
3563: what its final value will be.
3564:
3565: For architectures with a decrement_and_branch_until_zero insn,
3566: don't do this if we put a REG_NONNEG note on the endtest for
3567: this biv. */
3568:
3569: /* Compare against bl->init_insn rather than loop_start.
3570: We aren't concerned with any uses of the biv between
3571: init_insn and loop_start since these won't be affected
3572: by the value of the biv elsewhere in the function, so
3573: long as init_insn doesn't use the biv itself.
3574: March 14, 1989 -- [email protected] */
3575:
3576: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
3577: && bl->init_insn
3578: && INSN_UID (bl->init_insn) < max_uid_for_loop
3579: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
3580: #ifdef HAVE_decrement_and_branch_until_zero
3581: && ! bl->nonneg
3582: #endif
3583: && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3584: || ((final_value = final_biv_value (bl, loop_start, loop_end))
3585: #ifdef HAVE_decrement_and_branch_until_zero
3586: && ! bl->nonneg
3587: #endif
3588: ))
3589: bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
3590: threshold, insn_count);
3591: else
3592: {
3593: if (loop_dump_stream)
3594: {
3595: fprintf (loop_dump_stream,
3596: "Cannot eliminate biv %d.\n",
3597: bl->regno);
3598: fprintf (loop_dump_stream,
3599: "First use: insn %d, last use: insn %d.\n",
3600: regno_first_uid[bl->regno],
3601: regno_last_uid[bl->regno]);
3602: }
3603: }
3604:
3605: /* Combine all giv's for this iv_class. */
3606: combine_givs (bl);
3607:
3608: /* This will be true at the end, if all givs which depend on this
3609: biv have been strength reduced.
3610: We can't (currently) eliminate the biv unless this is so. */
3611: all_reduced = 1;
3612:
3613: /* Check each giv in this class to see if we will benefit by reducing
3614: it. Skip giv's combined with others. */
3615: for (v = bl->giv; v; v = v->next_iv)
3616: {
3617: struct induction *tv;
3618:
3619: if (v->ignore || v->same)
3620: continue;
3621:
3622: benefit = v->benefit;
3623:
3624: /* Reduce benefit if not replaceable, since we will insert
3625: a move-insn to replace the insn that calculates this giv.
3626: Don't do this unless the giv is a user variable, since it
3627: will often be marked non-replaceable because of the duplication
3628: of the exit code outside the loop. In such a case, the copies
3629: we insert are dead and will be deleted. So they don't have
3630: a cost. Similar situations exist. */
3631: /* ??? The new final_[bg]iv_value code does a much better job
3632: of finding replaceable giv's, and hence this code may no longer
3633: be necessary. */
3634: if (! v->replaceable && ! bl->eliminable
3635: && REG_USERVAR_P (v->dest_reg))
3636: benefit -= copy_cost;
3637:
3638: /* Decrease the benefit to count the add-insns that we will
3639: insert to increment the reduced reg for the giv. */
3640: benefit -= add_cost * bl->biv_count;
3641:
3642: /* Decide whether to strength-reduce this giv or to leave the code
3643: unchanged (recompute it from the biv each time it is used).
3644: This decision can be made independently for each giv. */
3645:
3646: /* ??? Perhaps attempt to guess whether autoincrement will handle
3647: some of the new add insns; if so, can increase BENEFIT
3648: (undo the subtraction of add_cost that was done above). */
3649:
3650: /* If an insn is not to be strength reduced, then set its ignore
3651: flag, and clear all_reduced. */
3652:
3653: if (v->lifetime * threshold * benefit < insn_count)
3654: {
3655: if (loop_dump_stream)
3656: fprintf (loop_dump_stream,
3657: "giv of insn %d not worth while, %d vs %d.\n",
3658: INSN_UID (v->insn),
3659: v->lifetime * threshold * benefit, insn_count);
3660: v->ignore = 1;
3661: all_reduced = 0;
3662: }
3663: else
3664: {
3665: /* Check that we can increment the reduced giv without a
3666: multiply insn. If not, reject it. */
3667:
3668: for (tv = bl->biv; tv; tv = tv->next_iv)
3669: if (tv->mult_val == const1_rtx
3670: && ! product_cheap_p (tv->add_val, v->mult_val))
3671: {
3672: if (loop_dump_stream)
3673: fprintf (loop_dump_stream,
3674: "giv of insn %d: would need a multiply.\n",
3675: INSN_UID (v->insn));
3676: v->ignore = 1;
3677: all_reduced = 0;
3678: break;
3679: }
3680: }
3681: }
3682:
3683: /* Reduce each giv that we decided to reduce. */
3684:
3685: for (v = bl->giv; v; v = v->next_iv)
3686: {
3687: struct induction *tv;
3688: if (! v->ignore && v->same == 0)
3689: {
3690: v->new_reg = gen_reg_rtx (v->mode);
3691:
3692: /* For each place where the biv is incremented,
3693: add an insn to increment the new, reduced reg for the giv. */
3694: for (tv = bl->biv; tv; tv = tv->next_iv)
3695: {
3696: if (tv->mult_val == const1_rtx)
3697: emit_iv_add_mult (tv->add_val, v->mult_val,
3698: v->new_reg, v->new_reg, tv->insn);
3699: else /* tv->mult_val == const0_rtx */
3700: /* A multiply is acceptable here
3701: since this is presumed to be seldom executed. */
3702: emit_iv_add_mult (tv->add_val, v->mult_val,
3703: v->add_val, v->new_reg, tv->insn);
3704: }
3705:
3706: /* Add code at loop start to initialize giv's reduced reg. */
3707:
3708: emit_iv_add_mult (bl->initial_value, v->mult_val,
3709: v->add_val, v->new_reg, loop_start);
3710: }
3711: }
3712:
3713: /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
3714: as not reduced.
3715:
3716: For each giv register that can be reduced now: if replaceable,
3717: substitute reduced reg wherever the old giv occurs;
3718: else add new move insn "giv_reg = reduced_reg".
3719:
3720: Also check for givs whose first use is their definition and whose
3721: last use is the definition of another giv. If so, it is likely
3722: dead and should not be used to eliminate a biv. */
3723: for (v = bl->giv; v; v = v->next_iv)
3724: {
3725: if (v->same && v->same->ignore)
3726: v->ignore = 1;
3727:
3728: if (v->ignore)
3729: continue;
3730:
3731: if (v->giv_type == DEST_REG
3732: && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn))
3733: {
3734: struct induction *v1;
3735:
3736: for (v1 = bl->giv; v1; v1 = v1->next_iv)
3737: if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn))
3738: v->maybe_dead = 1;
3739: }
3740:
3741: /* Update expression if this was combined, in case other giv was
3742: replaced. */
3743: if (v->same)
3744: v->new_reg = replace_rtx (v->new_reg,
3745: v->same->dest_reg, v->same->new_reg);
3746:
3747: if (v->giv_type == DEST_ADDR)
3748: /* Store reduced reg as the address in the memref where we found
3749: this giv. */
3750: *v->location = v->new_reg;
3751: else if (v->replaceable)
3752: {
3753: reg_map[REGNO (v->dest_reg)] = v->new_reg;
3754:
3755: #if 0
3756: /* I can no longer duplicate the original problem. Perhaps
3757: this is unnecessary now? */
3758:
3759: /* Replaceable; it isn't strictly necessary to delete the old
3760: insn and emit a new one, because v->dest_reg is now dead.
3761:
3762: However, especially when unrolling loops, the special
3763: handling for (set REG0 REG1) in the second cse pass may
3764: make v->dest_reg live again. To avoid this problem, emit
3765: an insn to set the original giv reg from the reduced giv.
3766: We can not delete the original insn, since it may be part
3767: of a LIBCALL, and the code in flow that eliminates dead
3768: libcalls will fail if it is deleted. */
3769: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3770: v->insn);
3771: #endif
3772: }
3773: else
3774: {
3775: /* Not replaceable; emit an insn to set the original giv reg from
3776: the reduced giv, same as above. */
3777: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3778: v->insn);
3779: }
3780:
3781: /* When a loop is reversed, givs which depend on the reversed
3782: biv, and which are live outside the loop, must be set to their
3783: correct final value. This insn is only needed if the giv is
3784: not replaceable. The correct final value is the same as the
3785: value that the giv starts the reversed loop with. */
3786: if (bl->reversed && ! v->replaceable)
3787: emit_iv_add_mult (bl->initial_value, v->mult_val,
3788: v->add_val, v->dest_reg, end_insert_before);
3789: else if (v->final_value)
3790: {
3791: rtx insert_before;
3792:
3793: /* If the loop has multiple exits, emit the insn before the
3794: loop to ensure that it will always be executed no matter
3795: how the loop exits. Otherwise, emit the insn after the loop,
3796: since this is slightly more efficient. */
3797: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3798: insert_before = loop_start;
3799: else
3800: insert_before = end_insert_before;
3801: emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
3802: insert_before);
3803:
3804: #if 0
3805: /* If the insn to set the final value of the giv was emitted
3806: before the loop, then we must delete the insn inside the loop
3807: that sets it. If this is a LIBCALL, then we must delete
3808: every insn in the libcall. Note, however, that
3809: final_giv_value will only succeed when there are multiple
3810: exits if the giv is dead at each exit, hence it does not
3811: matter that the original insn remains because it is dead
3812: anyways. */
3813: /* Delete the insn inside the loop that sets the giv since
3814: the giv is now set before (or after) the loop. */
3815: delete_insn (v->insn);
3816: #endif
3817: }
3818:
3819: if (loop_dump_stream)
3820: {
3821: fprintf (loop_dump_stream, "giv at %d reduced to ",
3822: INSN_UID (v->insn));
3823: print_rtl (loop_dump_stream, v->new_reg);
3824: fprintf (loop_dump_stream, "\n");
3825: }
3826: }
3827:
3828: /* All the givs based on the biv bl have been reduced if they
3829: merit it. */
3830:
3831: /* For each giv not marked as maybe dead that has been combined with a
3832: second giv, clear any "maybe dead" mark on that second giv.
3833: v->new_reg will either be or refer to the register of the giv it
3834: combined with.
3835:
3836: Doing this clearing avoids problems in biv elimination where a
3837: giv's new_reg is a complex value that can't be put in the insn but
3838: the giv combined with (with a reg as new_reg) is marked maybe_dead.
3839: Since the register will be used in either case, we'd prefer it be
3840: used from the simpler giv. */
3841:
3842: for (v = bl->giv; v; v = v->next_iv)
3843: if (! v->maybe_dead && v->same)
3844: v->same->maybe_dead = 0;
3845:
3846: /* Try to eliminate the biv, if it is a candidate.
3847: This won't work if ! all_reduced,
3848: since the givs we planned to use might not have been reduced.
3849:
1.1.1.2 root 3850: We have to be careful that we didn't initially think we could eliminate
1.1 root 3851: this biv because of a giv that we now think may be dead and shouldn't
3852: be used as a biv replacement.
3853:
3854: Also, there is the possibility that we may have a giv that looks
3855: like it can be used to eliminate a biv, but the resulting insn
3856: isn't valid. This can happen, for example, on the 88k, where a
3857: JUMP_INSN can compare a register only with zero. Attempts to
1.1.1.3 ! root 3858: replace it with a compare with a constant will fail.
1.1 root 3859:
3860: Note that in cases where this call fails, we may have replaced some
3861: of the occurrences of the biv with a giv, but no harm was done in
3862: doing so in the rare cases where it can occur. */
3863:
3864: if (all_reduced == 1 && bl->eliminable
3865: && maybe_eliminate_biv (bl, loop_start, end, 1,
3866: threshold, insn_count))
3867:
3868: {
3869: /* ?? If we created a new test to bypass the loop entirely,
3870: or otherwise drop straight in, based on this test, then
3871: we might want to rewrite it also. This way some later
3872: pass has more hope of removing the initialization of this
3873: biv entirely. */
3874:
3875: /* If final_value != 0, then the biv may be used after loop end
3876: and we must emit an insn to set it just in case.
3877:
3878: Reversed bivs already have an insn after the loop setting their
3879: value, so we don't need another one. We can't calculate the
3880: proper final value for such a biv here anyways. */
3881: if (final_value != 0 && ! bl->reversed)
3882: {
3883: rtx insert_before;
3884:
3885: /* If the loop has multiple exits, emit the insn before the
3886: loop to ensure that it will always be executed no matter
3887: how the loop exits. Otherwise, emit the insn after the
3888: loop, since this is slightly more efficient. */
3889: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3890: insert_before = loop_start;
3891: else
3892: insert_before = end_insert_before;
3893:
3894: emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
3895: end_insert_before);
3896: }
3897:
3898: #if 0
3899: /* Delete all of the instructions inside the loop which set
3900: the biv, as they are all dead. If is safe to delete them,
3901: because an insn setting a biv will never be part of a libcall. */
3902: /* However, deleting them will invalidate the regno_last_uid info,
3903: so keeping them around is more convenient. Final_biv_value
3904: will only succeed when there are multiple exits if the biv
3905: is dead at each exit, hence it does not matter that the original
3906: insn remains, because it is dead anyways. */
3907: for (v = bl->biv; v; v = v->next_iv)
3908: delete_insn (v->insn);
3909: #endif
3910:
3911: if (loop_dump_stream)
3912: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
3913: bl->regno);
3914: }
3915: }
3916:
3917: /* Go through all the instructions in the loop, making all the
3918: register substitutions scheduled in REG_MAP. */
3919:
3920: for (p = loop_start; p != end; p = NEXT_INSN (p))
3921: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3922: || GET_CODE (p) == CALL_INSN)
3923: {
3924: replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0);
3925: replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0);
3926: }
3927:
3928: /* Unroll loops from within strength reduction so that we can use the
3929: induction variable information that strength_reduce has already
3930: collected. */
3931:
3932: if (flag_unroll_loops)
3933: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
3934:
3935: if (loop_dump_stream)
3936: fprintf (loop_dump_stream, "\n");
3937: }
3938:
3939: /* Return 1 if X is a valid source for an initial value (or as value being
3940: compared against in an initial test).
3941:
3942: X must be either a register or constant and must not be clobbered between
3943: the current insn and the start of the loop.
3944:
3945: INSN is the insn containing X. */
3946:
3947: static int
3948: valid_initial_value_p (x, insn, call_seen, loop_start)
3949: rtx x;
3950: rtx insn;
3951: int call_seen;
3952: rtx loop_start;
3953: {
3954: if (CONSTANT_P (x))
3955: return 1;
3956:
1.1.1.2 root 3957: /* Only consider pseudos we know about initialized in insns whose luids
1.1 root 3958: we know. */
3959: if (GET_CODE (x) != REG
3960: || REGNO (x) >= max_reg_before_loop)
3961: return 0;
3962:
3963: /* Don't use call-clobbered registers across a call which clobbers it. On
3964: some machines, don't use any hard registers at all. */
3965: if (REGNO (x) < FIRST_PSEUDO_REGISTER
3966: #ifndef SMALL_REGISTER_CLASSES
3967: && call_used_regs[REGNO (x)] && call_seen
3968: #endif
3969: )
3970: return 0;
3971:
3972: /* Don't use registers that have been clobbered before the start of the
3973: loop. */
3974: if (reg_set_between_p (x, insn, loop_start))
3975: return 0;
3976:
3977: return 1;
3978: }
3979:
3980: /* Scan X for memory refs and check each memory address
3981: as a possible giv. INSN is the insn whose pattern X comes from.
3982: NOT_EVERY_ITERATION is 1 if the insn might not be executed during
3983: every loop iteration. */
3984:
3985: static void
3986: find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
3987: rtx x;
3988: rtx insn;
3989: int not_every_iteration;
3990: rtx loop_start, loop_end;
3991: {
3992: register int i, j;
3993: register enum rtx_code code;
3994: register char *fmt;
3995:
3996: if (x == 0)
3997: return;
3998:
3999: code = GET_CODE (x);
4000: switch (code)
4001: {
4002: case REG:
4003: case CONST_INT:
4004: case CONST:
4005: case CONST_DOUBLE:
4006: case SYMBOL_REF:
4007: case LABEL_REF:
4008: case PC:
4009: case CC0:
4010: case ADDR_VEC:
4011: case ADDR_DIFF_VEC:
4012: case USE:
4013: case CLOBBER:
4014: return;
4015:
4016: case MEM:
4017: {
4018: rtx src_reg;
4019: rtx add_val;
4020: rtx mult_val;
4021: int benefit;
4022:
4023: benefit = general_induction_var (XEXP (x, 0),
4024: &src_reg, &add_val, &mult_val);
4025:
4026: /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0.
4027: Such a giv isn't useful. */
4028: if (benefit > 0 && (mult_val != const1_rtx || add_val != const0_rtx))
4029: {
4030: /* Found one; record it. */
4031: struct induction *v
4032: = (struct induction *) oballoc (sizeof (struct induction));
4033:
4034: record_giv (v, insn, src_reg, addr_placeholder, mult_val,
4035: add_val, benefit, DEST_ADDR, not_every_iteration,
4036: &XEXP (x, 0), loop_start, loop_end);
4037:
4038: v->mem_mode = GET_MODE (x);
4039: }
4040: return;
4041: }
4042: }
4043:
4044: /* Recursively scan the subexpressions for other mem refs. */
4045:
4046: fmt = GET_RTX_FORMAT (code);
4047: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4048: if (fmt[i] == 'e')
4049: find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
4050: loop_end);
4051: else if (fmt[i] == 'E')
4052: for (j = 0; j < XVECLEN (x, i); j++)
4053: find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
4054: loop_start, loop_end);
4055: }
4056:
4057: /* Fill in the data about one biv update.
4058: V is the `struct induction' in which we record the biv. (It is
4059: allocated by the caller, with alloca.)
4060: INSN is the insn that sets it.
4061: DEST_REG is the biv's reg.
4062:
4063: MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4064: INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
1.1.1.3 ! root 4065: being set to INC_VAL.
! 4066:
! 4067: NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
! 4068: executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
! 4069: can be executed more than once per iteration. If MAYBE_MULTIPLE
! 4070: and NOT_EVERY_ITERATION are both zero, we know that the biv update is
! 4071: executed exactly once per iteration. */
1.1 root 4072:
4073: static void
1.1.1.3 ! root 4074: record_biv (v, insn, dest_reg, inc_val, mult_val,
! 4075: not_every_iteration, maybe_multiple)
1.1 root 4076: struct induction *v;
4077: rtx insn;
4078: rtx dest_reg;
4079: rtx inc_val;
4080: rtx mult_val;
4081: int not_every_iteration;
1.1.1.3 ! root 4082: int maybe_multiple;
1.1 root 4083: {
4084: struct iv_class *bl;
4085:
4086: v->insn = insn;
4087: v->src_reg = dest_reg;
4088: v->dest_reg = dest_reg;
4089: v->mult_val = mult_val;
4090: v->add_val = inc_val;
4091: v->mode = GET_MODE (dest_reg);
4092: v->always_computable = ! not_every_iteration;
1.1.1.3 ! root 4093: v->maybe_multiple = maybe_multiple;
1.1 root 4094:
4095: /* Add this to the reg's iv_class, creating a class
4096: if this is the first incrementation of the reg. */
4097:
4098: bl = reg_biv_class[REGNO (dest_reg)];
4099: if (bl == 0)
4100: {
4101: /* Create and initialize new iv_class. */
4102:
4103: bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
4104:
4105: bl->regno = REGNO (dest_reg);
4106: bl->biv = 0;
4107: bl->giv = 0;
4108: bl->biv_count = 0;
4109: bl->giv_count = 0;
4110:
4111: /* Set initial value to the reg itself. */
4112: bl->initial_value = dest_reg;
1.1.1.3 ! root 4113: /* We haven't seen the initializing insn yet */
1.1 root 4114: bl->init_insn = 0;
4115: bl->init_set = 0;
4116: bl->initial_test = 0;
4117: bl->incremented = 0;
4118: bl->eliminable = 0;
4119: bl->nonneg = 0;
4120: bl->reversed = 0;
4121:
4122: /* Add this class to loop_iv_list. */
4123: bl->next = loop_iv_list;
4124: loop_iv_list = bl;
4125:
4126: /* Put it in the array of biv register classes. */
4127: reg_biv_class[REGNO (dest_reg)] = bl;
4128: }
4129:
4130: /* Update IV_CLASS entry for this biv. */
4131: v->next_iv = bl->biv;
4132: bl->biv = v;
4133: bl->biv_count++;
4134: if (mult_val == const1_rtx)
4135: bl->incremented = 1;
4136:
4137: if (loop_dump_stream)
4138: {
4139: fprintf (loop_dump_stream,
4140: "Insn %d: possible biv, reg %d,",
4141: INSN_UID (insn), REGNO (dest_reg));
4142: if (GET_CODE (inc_val) == CONST_INT)
4143: fprintf (loop_dump_stream, " const = %d\n",
4144: INTVAL (inc_val));
4145: else
4146: {
4147: fprintf (loop_dump_stream, " const = ");
4148: print_rtl (loop_dump_stream, inc_val);
4149: fprintf (loop_dump_stream, "\n");
4150: }
4151: }
4152: }
4153:
4154: /* Fill in the data about one giv.
4155: V is the `struct induction' in which we record the giv. (It is
4156: allocated by the caller, with alloca.)
4157: INSN is the insn that sets it.
4158: BENEFIT estimates the savings from deleting this insn.
4159: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4160: into a register or is used as a memory address.
4161:
4162: SRC_REG is the biv reg which the giv is computed from.
4163: DEST_REG is the giv's reg (if the giv is stored in a reg).
4164: MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4165: LOCATION points to the place where this giv's value appears in INSN. */
4166:
4167: static void
4168: record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
4169: type, not_every_iteration, location, loop_start, loop_end)
4170: struct induction *v;
4171: rtx insn;
4172: rtx src_reg;
4173: rtx dest_reg;
4174: rtx mult_val, add_val;
4175: int benefit;
4176: enum g_types type;
4177: int not_every_iteration;
4178: rtx *location;
4179: rtx loop_start, loop_end;
4180: {
4181: struct induction *b;
4182: struct iv_class *bl;
4183: rtx set = single_set (insn);
4184: rtx p;
4185:
4186: v->insn = insn;
4187: v->src_reg = src_reg;
4188: v->giv_type = type;
4189: v->dest_reg = dest_reg;
4190: v->mult_val = mult_val;
4191: v->add_val = add_val;
4192: v->benefit = benefit;
4193: v->location = location;
4194: v->cant_derive = 0;
4195: v->combined_with = 0;
1.1.1.3 ! root 4196: v->maybe_multiple = 0;
1.1 root 4197: v->maybe_dead = 0;
4198: v->derive_adjustment = 0;
4199: v->same = 0;
4200: v->ignore = 0;
4201: v->new_reg = 0;
4202: v->final_value = 0;
4203:
4204: /* The v->always_computable field is used in update_giv_derive, to
4205: determine whether a giv can be used to derive another giv. For a
4206: DEST_REG giv, INSN computes a new value for the giv, so its value
4207: isn't computable if INSN insn't executed every iteration.
4208: However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4209: it does not compute a new value. Hence the value is always computable
1.1.1.2 root 4210: regardless of whether INSN is executed each iteration. */
1.1 root 4211:
4212: if (type == DEST_ADDR)
4213: v->always_computable = 1;
4214: else
4215: v->always_computable = ! not_every_iteration;
4216:
4217: if (type == DEST_ADDR)
4218: {
4219: v->mode = GET_MODE (*location);
4220: v->lifetime = 1;
4221: v->times_used = 1;
4222: }
4223: else /* type == DEST_REG */
4224: {
4225: v->mode = GET_MODE (SET_DEST (set));
4226:
4227: v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]]
4228: - uid_luid[regno_first_uid[REGNO (dest_reg)]]);
4229:
4230: v->times_used = n_times_used[REGNO (dest_reg)];
4231:
4232: /* If the lifetime is zero, it means that this register is
4233: really a dead store. So mark this as a giv that can be
4234: ignored. This will not prevent the biv from being eliminated. */
4235: if (v->lifetime == 0)
4236: v->ignore = 1;
4237:
4238: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
4239: reg_iv_info[REGNO (dest_reg)] = v;
4240: }
4241:
4242: /* Add the giv to the class of givs computed from one biv. */
4243:
4244: bl = reg_biv_class[REGNO (src_reg)];
4245: if (bl)
4246: {
4247: v->next_iv = bl->giv;
4248: bl->giv = v;
4249: /* Don't count DEST_ADDR. This is supposed to count the number of
4250: insns that calculate givs. */
4251: if (type == DEST_REG)
4252: bl->giv_count++;
4253: bl->total_benefit += benefit;
4254: }
4255: else
4256: /* Fatal error, biv missing for this giv? */
4257: abort ();
4258:
4259: if (type == DEST_ADDR)
4260: v->replaceable = 1;
4261: else
4262: {
4263: /* The giv can be replaced outright by the reduced register only if all
4264: of the following conditions are true:
4265: - the insn that sets the giv is always executed on any iteration
4266: on which the giv is used at all
4267: (there are two ways to deduce this:
4268: either the insn is executed on every iteration,
4269: or all uses follow that insn in the same basic block),
4270: - the giv is not used outside the loop
4271: - no assignments to the biv occur during the giv's lifetime. */
4272:
4273: if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn)
4274: /* Previous line always fails if INSN was moved by loop opt. */
4275: && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end)
4276: && (! not_every_iteration
4277: || last_use_this_basic_block (dest_reg, insn)))
4278: {
4279: /* Now check that there are no assignments to the biv within the
4280: giv's lifetime. This requires two separate checks. */
4281:
4282: /* Check each biv update, and fail if any are between the first
4283: and last use of the giv.
4284:
4285: If this loop contains an inner loop that was unrolled, then
4286: the insn modifying the biv may have been emitted by the loop
4287: unrolling code, and hence does not have a valid luid. Just
4288: mark the biv as not replaceable in this case. It is not very
4289: useful as a biv, because it is used in two different loops.
4290: It is very unlikely that we would be able to optimize the giv
4291: using this biv anyways. */
4292:
4293: v->replaceable = 1;
4294: for (b = bl->biv; b; b = b->next_iv)
4295: {
4296: if (INSN_UID (b->insn) >= max_uid_for_loop
4297: || ((uid_luid[INSN_UID (b->insn)]
4298: >= uid_luid[regno_first_uid[REGNO (dest_reg)]])
4299: && (uid_luid[INSN_UID (b->insn)]
4300: <= uid_luid[regno_last_uid[REGNO (dest_reg)]])))
4301: {
4302: v->replaceable = 0;
4303: v->not_replaceable = 1;
4304: break;
4305: }
4306: }
4307:
4308: /* Check each insn between the first and last use of the giv,
4309: and fail if any of them are branches that jump to a named label
4310: outside this range, but still inside the loop. This catches
4311: cases of spaghetti code where the execution order of insns
4312: is not linear, and hence the above test fails. For example,
4313: in the following code, j is not replaceable:
4314: for (i = 0; i < 100; ) {
4315: L0: j = 4*i; goto L1;
4316: L2: k = j; goto L3;
4317: L1: i++; goto L2;
4318: L3: ; }
4319: printf ("k = %d\n", k); }
4320: This test is conservative, but this test succeeds rarely enough
4321: that it isn't a problem. See also check_final_value below. */
4322:
4323: if (v->replaceable)
4324: for (p = insn;
4325: INSN_UID (p) >= max_uid_for_loop
4326: || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]];
4327: p = NEXT_INSN (p))
4328: {
4329: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4330: && LABEL_NAME (JUMP_LABEL (p))
4331: && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)
4332: && (INSN_LUID (JUMP_LABEL (p))
4333: < uid_luid[regno_first_uid[REGNO (dest_reg)]]))
4334: || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)
4335: && (INSN_LUID (JUMP_LABEL (p))
4336: > uid_luid[regno_last_uid[REGNO (dest_reg)]]))))
4337: {
4338: v->replaceable = 0;
4339: v->not_replaceable = 1;
4340:
4341: if (loop_dump_stream)
4342: fprintf (loop_dump_stream,
4343: "Found branch outside giv lifetime.\n");
4344:
4345: break;
4346: }
4347: }
4348: }
4349: else
4350: {
4351: /* May still be replaceable, we don't have enough info here to
4352: decide. */
4353: v->replaceable = 0;
4354: v->not_replaceable = 0;
4355: }
4356: }
4357:
4358: if (loop_dump_stream)
4359: {
4360: if (type == DEST_REG)
4361: fprintf (loop_dump_stream, "Insn %d: giv reg %d",
4362: INSN_UID (insn), REGNO (dest_reg));
4363: else
4364: fprintf (loop_dump_stream, "Insn %d: dest address",
4365: INSN_UID (insn));
4366:
4367: fprintf (loop_dump_stream, " src reg %d benefit %d",
4368: REGNO (src_reg), v->benefit);
4369: fprintf (loop_dump_stream, " used %d lifetime %d",
4370: v->times_used, v->lifetime);
4371:
4372: if (v->replaceable)
4373: fprintf (loop_dump_stream, " replaceable");
4374:
4375: if (GET_CODE (mult_val) == CONST_INT)
4376: fprintf (loop_dump_stream, " mult %d",
4377: INTVAL (mult_val));
4378: else
4379: {
4380: fprintf (loop_dump_stream, " mult ");
4381: print_rtl (loop_dump_stream, mult_val);
4382: }
4383:
4384: if (GET_CODE (add_val) == CONST_INT)
4385: fprintf (loop_dump_stream, " add %d",
4386: INTVAL (add_val));
4387: else
4388: {
4389: fprintf (loop_dump_stream, " add ");
4390: print_rtl (loop_dump_stream, add_val);
4391: }
4392: }
4393:
4394: if (loop_dump_stream)
4395: fprintf (loop_dump_stream, "\n");
4396:
4397: }
4398:
4399:
4400: /* All this does is determine whether a giv can be made replaceable because
4401: its final value can be calculated. This code can not be part of record_giv
4402: above, because final_giv_value requires that the number of loop iterations
4403: be known, and that can not be accurately calculated until after all givs
4404: have been identified. */
4405:
4406: static void
4407: check_final_value (v, loop_start, loop_end)
4408: struct induction *v;
4409: rtx loop_start, loop_end;
4410: {
4411: struct iv_class *bl;
4412: rtx final_value = 0;
4413: rtx tem;
4414:
4415: bl = reg_biv_class[REGNO (v->src_reg)];
4416:
4417: /* DEST_ADDR givs will never reach here, because they are always marked
4418: replaceable above in record_giv. */
4419:
4420: /* The giv can be replaced outright by the reduced register only if all
4421: of the following conditions are true:
4422: - the insn that sets the giv is always executed on any iteration
4423: on which the giv is used at all
4424: (there are two ways to deduce this:
4425: either the insn is executed on every iteration,
4426: or all uses follow that insn in the same basic block),
4427: - its final value can be calculated (this condition is different
4428: than the one above in record_giv)
4429: - no assignments to the biv occur during the giv's lifetime. */
4430:
4431: #if 0
4432: /* This is only called now when replaceable is known to be false. */
4433: /* Clear replaceable, so that it won't confuse final_giv_value. */
4434: v->replaceable = 0;
4435: #endif
4436:
4437: if ((final_value = final_giv_value (v, loop_start, loop_end))
4438: && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
4439: {
4440: int biv_increment_seen = 0;
4441: rtx p = v->insn;
4442: rtx last_giv_use;
4443:
4444: v->replaceable = 1;
4445:
4446: /* When trying to determine whether or not a biv increment occurs
4447: during the lifetime of the giv, we can ignore uses of the variable
4448: outside the loop because final_value is true. Hence we can not
4449: use regno_last_uid and regno_first_uid as above in record_giv. */
4450:
4451: /* Search the loop to determine whether any assignments to the
4452: biv occur during the giv's lifetime. Start with the insn
4453: that sets the giv, and search around the loop until we come
4454: back to that insn again.
4455:
4456: Also fail if there is a jump within the giv's lifetime that jumps
4457: to somewhere outside the lifetime but still within the loop. This
4458: catches spaghetti code where the execution order is not linear, and
4459: hence the above test fails. Here we assume that the giv lifetime
4460: does not extend from one iteration of the loop to the next, so as
4461: to make the test easier. Since the lifetime isn't known yet,
4462: this requires two loops. See also record_giv above. */
4463:
4464: last_giv_use = v->insn;
4465:
4466: while (1)
4467: {
4468: p = NEXT_INSN (p);
4469: if (p == loop_end)
4470: p = NEXT_INSN (loop_start);
4471: if (p == v->insn)
4472: break;
4473:
4474: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4475: || GET_CODE (p) == CALL_INSN)
4476: {
4477: if (biv_increment_seen)
4478: {
4479: if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4480: {
4481: v->replaceable = 0;
4482: v->not_replaceable = 1;
4483: break;
4484: }
4485: }
4486: else if (GET_CODE (PATTERN (p)) == SET
4487: && SET_DEST (PATTERN (p)) == v->src_reg)
4488: biv_increment_seen = 1;
4489: else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4490: last_giv_use = p;
4491: }
4492: }
4493:
4494: /* Now that the lifetime of the giv is known, check for branches
4495: from within the lifetime to outside the lifetime if it is still
4496: replaceable. */
4497:
4498: if (v->replaceable)
4499: {
4500: p = v->insn;
4501: while (1)
4502: {
4503: p = NEXT_INSN (p);
4504: if (p == loop_end)
4505: p = NEXT_INSN (loop_start);
4506: if (p == last_giv_use)
4507: break;
4508:
4509: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4510: && LABEL_NAME (JUMP_LABEL (p))
4511: && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
4512: && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
4513: || (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
4514: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
4515: {
4516: v->replaceable = 0;
4517: v->not_replaceable = 1;
4518:
4519: if (loop_dump_stream)
4520: fprintf (loop_dump_stream,
4521: "Found branch outside giv lifetime.\n");
4522:
4523: break;
4524: }
4525: }
4526: }
4527:
4528: /* If it is replaceable, then save the final value. */
4529: if (v->replaceable)
4530: v->final_value = final_value;
4531: }
4532:
4533: if (loop_dump_stream && v->replaceable)
4534: fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
4535: INSN_UID (v->insn), REGNO (v->dest_reg));
4536: }
4537:
4538: /* Update the status of whether a giv can derive other givs.
4539:
4540: We need to do something special if there is or may be an update to the biv
4541: between the time the giv is defined and the time it is used to derive
4542: another giv.
4543:
4544: In addition, a giv that is only conditionally set is not allowed to
4545: derive another giv once a label has been passed.
4546:
4547: The cases we look at are when a label or an update to a biv is passed. */
4548:
4549: static void
4550: update_giv_derive (p)
4551: rtx p;
4552: {
4553: struct iv_class *bl;
4554: struct induction *biv, *giv;
4555: rtx tem;
4556: int dummy;
4557:
4558: /* Search all IV classes, then all bivs, and finally all givs.
4559:
1.1.1.3 ! root 4560: There are three cases we are concerned with. First we have the situation
1.1 root 4561: of a giv that is only updated conditionally. In that case, it may not
4562: derive any givs after a label is passed.
4563:
4564: The second case is when a biv update occurs, or may occur, after the
4565: definition of a giv. For certain biv updates (see below) that are
4566: known to occur between the giv definition and use, we can adjust the
4567: giv definition. For others, or when the biv update is conditional,
4568: we must prevent the giv from deriving any other givs. There are two
4569: sub-cases within this case.
4570:
4571: If this is a label, we are concerned with any biv update that is done
4572: conditionally, since it may be done after the giv is defined followed by
4573: a branch here (actually, we need to pass both a jump and a label, but
4574: this extra tracking doesn't seem worth it).
4575:
1.1.1.3 ! root 4576: If this is a jump, we are concerned about any biv update that may be
! 4577: executed multiple times. We are actually only concerned about
! 4578: backward jumps, but it is probably not worth performing the test
! 4579: on the jump again here.
! 4580:
! 4581: If this is a biv update, we must adjust the giv status to show that a
1.1 root 4582: subsequent biv update was performed. If this adjustment cannot be done,
4583: the giv cannot derive further givs. */
4584:
4585: for (bl = loop_iv_list; bl; bl = bl->next)
4586: for (biv = bl->biv; biv; biv = biv->next_iv)
1.1.1.3 ! root 4587: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
! 4588: || biv->insn == p)
1.1 root 4589: {
4590: for (giv = bl->giv; giv; giv = giv->next_iv)
4591: {
4592: /* If cant_derive is already true, there is no point in
4593: checking all of these conditions again. */
4594: if (giv->cant_derive)
4595: continue;
4596:
4597: /* If this giv is conditionally set and we have passed a label,
4598: it cannot derive anything. */
4599: if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
4600: giv->cant_derive = 1;
4601:
4602: /* Skip givs that have mult_val == 0, since
4603: they are really invariants. Also skip those that are
4604: replaceable, since we know their lifetime doesn't contain
4605: any biv update. */
4606: else if (giv->mult_val == const0_rtx || giv->replaceable)
4607: continue;
4608:
4609: /* The only way we can allow this giv to derive another
4610: is if this is a biv increment and we can form the product
4611: of biv->add_val and giv->mult_val. In this case, we will
4612: be able to compute a compensation. */
4613: else if (biv->insn == p)
4614: {
1.1.1.2 root 4615: tem = 0;
4616:
4617: if (biv->mult_val == const1_rtx)
4618: tem = simplify_giv_expr (gen_rtx (MULT, giv->mode,
4619: biv->add_val,
4620: giv->mult_val),
4621: &dummy);
4622:
4623: if (tem && giv->derive_adjustment)
4624: tem = simplify_giv_expr (gen_rtx (PLUS, giv->mode, tem,
4625: giv->derive_adjustment),
4626: &dummy);
4627: if (tem)
1.1 root 4628: giv->derive_adjustment = tem;
4629: else
4630: giv->cant_derive = 1;
4631: }
1.1.1.3 ! root 4632: else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
! 4633: || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
1.1 root 4634: giv->cant_derive = 1;
4635: }
4636: }
4637: }
4638:
4639: /* Check whether an insn is an increment legitimate for a basic induction var.
4640: X is the source of the insn.
4641: DEST_REG is the putative biv, also the destination of the insn.
4642: We accept patterns of these forms:
4643: REG = REG + INVARIANT
4644: REG = INVARIANT + REG
4645: REG = REG - CONSTANT
4646:
4647: If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
4648: and store the additive term into *INC_VAL.
4649:
4650: If X is an assignment of an invariant into DEST_REG, we set
4651: *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
4652:
4653: Otherwise we return 0. */
4654:
4655: static int
4656: basic_induction_var (x, dest_reg, inc_val, mult_val)
4657: register rtx x;
4658: rtx dest_reg;
4659: rtx *inc_val;
4660: rtx *mult_val;
4661: {
4662: register enum rtx_code code;
4663: rtx arg;
4664:
4665: code = GET_CODE (x);
4666: switch (code)
4667: {
4668: case PLUS:
4669: if (XEXP (x, 0) == dest_reg)
4670: arg = XEXP (x, 1);
4671: else if (XEXP (x, 1) == dest_reg)
4672: arg = XEXP (x, 0);
4673: else
4674: return 0;
4675:
4676: if (invariant_p (arg) != 1)
4677: return 0;
4678:
4679: *inc_val = arg;
4680: *mult_val = const1_rtx;
4681: return 1;
4682:
4683: case MINUS:
4684: if (XEXP (x, 0) == dest_reg
4685: && GET_CODE (XEXP (x, 1)) == CONST_INT)
4686: *inc_val = gen_rtx (CONST_INT, VOIDmode,
4687: - INTVAL (XEXP (x, 1)));
4688: else
4689: return 0;
4690:
4691: *mult_val = const1_rtx;
4692: return 1;
4693:
4694: /* Can accept constant setting of biv only when inside inner most loop.
4695: Otherwise, a biv of an inner loop may be incorrectly recognized
4696: as a biv of the outer loop,
4697: causing code to be moved INTO the inner loop. */
4698: case MEM:
4699: case REG:
4700: if (invariant_p (x) != 1)
4701: return 0;
4702: case CONST_INT:
4703: case SYMBOL_REF:
4704: case CONST:
4705: if (loops_enclosed == 1)
4706: {
4707: *inc_val = x;
4708: *mult_val = const0_rtx;
4709: return 1;
4710: }
4711: else
4712: return 0;
4713:
4714: default:
4715: return 0;
4716: }
4717: }
4718:
4719: /* A general induction variable (giv) is any quantity that is a linear
4720: function of a basic induction variable,
4721: i.e. giv = biv * mult_val + add_val.
4722: The coefficients can be any loop invariant quantity.
4723: A giv need not be computed directly from the biv;
4724: it can be computed by way of other givs. */
4725:
4726: /* Determine whether X computes a giv.
4727: If it does, return a nonzero value
4728: which is the benefit from eliminating the computation of X;
4729: set *SRC_REG to the register of the biv that it is computed from;
4730: set *ADD_VAL and *MULT_VAL to the coefficients,
4731: such that the value of X is biv * mult + add; */
4732:
4733: static int
4734: general_induction_var (x, src_reg, add_val, mult_val)
4735: rtx x;
4736: rtx *src_reg;
4737: rtx *add_val;
4738: rtx *mult_val;
4739: {
4740: rtx orig_x = x;
4741: int benefit = 0;
4742: char *storage;
4743:
4744: /* If this is an invariant, forget it, it isn't a giv. */
4745: if (invariant_p (x) == 1)
4746: return 0;
4747:
4748: /* See if the expression could be a giv and get its form.
4749: Mark our place on the obstack in case we don't find a giv. */
4750: storage = (char *) oballoc (0);
4751: x = simplify_giv_expr (x, &benefit);
4752: if (x == 0)
4753: {
4754: obfree (storage);
4755: return 0;
4756: }
4757:
4758: switch (GET_CODE (x))
4759: {
4760: case USE:
4761: case CONST_INT:
4762: /* Since this is now an invariant and wasn't before, it must be a giv
4763: with MULT_VAL == 0. It doesn't matter which BIV we associate this
4764: with. */
4765: *src_reg = loop_iv_list->biv->dest_reg;
4766: *mult_val = const0_rtx;
4767: *add_val = x;
4768: break;
4769:
4770: case REG:
4771: /* This is equivalent to a BIV. */
4772: *src_reg = x;
4773: *mult_val = const1_rtx;
4774: *add_val = const0_rtx;
4775: break;
4776:
4777: case PLUS:
4778: /* Either (plus (biv) (invar)) or
4779: (plus (mult (biv) (invar_1)) (invar_2)). */
4780: if (GET_CODE (XEXP (x, 0)) == MULT)
4781: {
4782: *src_reg = XEXP (XEXP (x, 0), 0);
4783: *mult_val = XEXP (XEXP (x, 0), 1);
4784: }
4785: else
4786: {
4787: *src_reg = XEXP (x, 0);
4788: *mult_val = const1_rtx;
4789: }
4790: *add_val = XEXP (x, 1);
4791: break;
4792:
4793: case MULT:
4794: /* ADD_VAL is zero. */
4795: *src_reg = XEXP (x, 0);
4796: *mult_val = XEXP (x, 1);
4797: *add_val = const0_rtx;
4798: break;
4799:
4800: default:
4801: abort ();
4802: }
4803:
4804: /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
4805: unless they are CONST_INT). */
4806: if (GET_CODE (*add_val) == USE)
4807: *add_val = XEXP (*add_val, 0);
4808: if (GET_CODE (*mult_val) == USE)
4809: *mult_val = XEXP (*mult_val, 0);
4810:
1.1.1.3 ! root 4811: benefit += rtx_cost (orig_x, SET);
1.1 root 4812:
4813: /* Always return some benefit if this is a giv so it will be detected
4814: as such. This allows elimination of bivs that might otherwise
4815: not be eliminated. */
4816: return benefit == 0 ? 1 : benefit;
4817: }
4818:
4819: /* Given an expression, X, try to form it as a linear function of a biv.
4820: We will canonicalize it to be of the form
4821: (plus (mult (BIV) (invar_1))
4822: (invar_2))
1.1.1.3 ! root 4823: with possible degeneracies.
1.1 root 4824:
4825: The invariant expressions must each be of a form that can be used as a
4826: machine operand. We surround then with a USE rtx (a hack, but localized
4827: and certainly unambiguous!) if not a CONST_INT for simplicity in this
4828: routine; it is the caller's responsibility to strip them.
4829:
4830: If no such canonicalization is possible (i.e., two biv's are used or an
4831: expression that is neither invariant nor a biv or giv), this routine
4832: returns 0.
4833:
4834: For a non-zero return, the result will have a code of CONST_INT, USE,
4835: REG (for a BIV), PLUS, or MULT. No other codes will occur.
4836:
4837: *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
4838:
4839: static rtx
4840: simplify_giv_expr (x, benefit)
4841: rtx x;
4842: int *benefit;
4843: {
4844: enum machine_mode mode = GET_MODE (x);
4845: rtx arg0, arg1;
4846: rtx tem;
4847:
4848: /* If this is not an integer mode, or if we cannot do arithmetic in this
4849: mode, this can't be a giv. */
4850: if (mode != VOIDmode
4851: && (GET_MODE_CLASS (mode) != MODE_INT
4852: || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_INT))
4853: return 0;
4854:
4855: switch (GET_CODE (x))
4856: {
4857: case PLUS:
4858: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4859: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4860: if (arg0 == 0 || arg1 == 0)
4861: return 0;
4862:
4863: /* Put constant last, CONST_INT last if both constant. */
4864: if ((GET_CODE (arg0) == USE
4865: || GET_CODE (arg0) == CONST_INT)
4866: && GET_CODE (arg1) != CONST_INT)
4867: tem = arg0, arg0 = arg1, arg1 = tem;
4868:
4869: /* Handle addition of zero, then addition of an invariant. */
4870: if (arg1 == const0_rtx)
4871: return arg0;
4872: else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
4873: switch (GET_CODE (arg0))
4874: {
4875: case CONST_INT:
4876: case USE:
4877: /* Both invariant. Only valid if sum is machine operand.
4878: First strip off possible USE on first operand. */
4879: if (GET_CODE (arg0) == USE)
4880: arg0 = XEXP (arg0, 0);
4881:
4882: tem = 0;
4883: if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
4884: {
4885: tem = plus_constant (arg0, INTVAL (arg1));
4886: if (GET_CODE (tem) != CONST_INT)
4887: tem = gen_rtx (USE, mode, tem);
4888: }
4889:
4890: return tem;
4891:
4892: case REG:
4893: case MULT:
4894: /* biv + invar or mult + invar. Return sum. */
4895: return gen_rtx (PLUS, mode, arg0, arg1);
4896:
4897: case PLUS:
4898: /* (a + invar_1) + invar_2. Associate. */
4899: return simplify_giv_expr (gen_rtx (PLUS, mode,
4900: XEXP (arg0, 0),
4901: gen_rtx (PLUS, mode,
4902: XEXP (arg0, 1), arg1)),
4903: benefit);
4904:
4905: default:
4906: abort ();
4907: }
4908:
4909: /* Each argument must be either REG, PLUS, or MULT. Convert REG to
4910: MULT to reduce cases. */
4911: if (GET_CODE (arg0) == REG)
4912: arg0 = gen_rtx (MULT, mode, arg0, const1_rtx);
4913: if (GET_CODE (arg1) == REG)
4914: arg1 = gen_rtx (MULT, mode, arg1, const1_rtx);
4915:
4916: /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
4917: Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
4918: Recurse to associate the second PLUS. */
4919: if (GET_CODE (arg1) == MULT)
4920: tem = arg0, arg0 = arg1, arg1 = tem;
4921:
4922: if (GET_CODE (arg1) == PLUS)
4923: return simplify_giv_expr (gen_rtx (PLUS, mode,
4924: gen_rtx (PLUS, mode,
4925: arg0, XEXP (arg1, 0)),
4926: XEXP (arg1, 1)),
4927: benefit);
4928:
4929: /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
4930: if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
4931: abort ();
4932:
4933: if (XEXP (arg0, 0) != XEXP (arg1, 0))
4934: return 0;
4935:
4936: return simplify_giv_expr (gen_rtx (MULT, mode,
4937: XEXP (arg0, 0),
4938: gen_rtx (PLUS, mode,
4939: XEXP (arg0, 1),
4940: XEXP (arg1, 1))),
4941: benefit);
4942:
4943: case MINUS:
4944: /* Handle "a - b" as "a + b * (-1)". */
4945: return simplify_giv_expr (gen_rtx (PLUS, mode,
4946: XEXP (x, 0),
4947: gen_rtx (MULT, mode,
4948: XEXP (x, 1),
4949: gen_rtx (CONST_INT,
4950: VOIDmode, -1))),
4951: benefit);
4952:
4953: case MULT:
4954: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4955: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4956: if (arg0 == 0 || arg1 == 0)
4957: return 0;
4958:
4959: /* Put constant last, CONST_INT last if both constant. */
4960: if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
4961: && GET_CODE (arg1) != CONST_INT)
4962: tem = arg0, arg0 = arg1, arg1 = tem;
4963:
4964: /* If second argument is not now constant, not giv. */
4965: if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
4966: return 0;
4967:
4968: /* Handle multiply by 0 or 1. */
4969: if (arg1 == const0_rtx)
4970: return const0_rtx;
4971:
4972: else if (arg1 == const1_rtx)
4973: return arg0;
4974:
4975: switch (GET_CODE (arg0))
4976: {
4977: case REG:
4978: /* biv * invar. Done. */
4979: return gen_rtx (MULT, mode, arg0, arg1);
4980:
4981: case CONST_INT:
4982: /* Product of two constants. */
4983: return gen_rtx (CONST_INT, mode, INTVAL (arg0) * INTVAL (arg1));
4984:
4985: case USE:
4986: /* invar * invar. Not giv. */
4987: return 0;
4988:
4989: case MULT:
4990: /* (a * invar_1) * invar_2. Associate. */
4991: return simplify_giv_expr (gen_rtx (MULT, mode,
4992: XEXP (arg0, 0),
4993: gen_rtx (MULT, mode,
4994: XEXP (arg0, 1), arg1)),
4995: benefit);
4996:
4997: case PLUS:
4998: /* (a + invar_1) * invar_2. Distribute. */
4999: return simplify_giv_expr (gen_rtx (PLUS, mode,
5000: gen_rtx (MULT, mode,
5001: XEXP (arg0, 0), arg1),
5002: gen_rtx (MULT, mode,
5003: XEXP (arg0, 1), arg1)),
5004: benefit);
5005:
5006: default:
5007: abort ();
5008: }
5009:
5010: case ASHIFT:
5011: case LSHIFT:
5012: /* Shift by constant is multiply by power of two. */
5013: if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5014: return 0;
5015:
5016: return simplify_giv_expr (gen_rtx (MULT, mode,
5017: XEXP (x, 0),
5018: gen_rtx (CONST_INT, VOIDmode,
5019: 1 << INTVAL (XEXP (x, 1)))),
5020: benefit);
5021:
5022: case NEG:
5023: /* "-a" is "a * (-1)" */
5024: return simplify_giv_expr (gen_rtx (MULT, mode,
5025: XEXP (x, 0),
5026: gen_rtx (CONST_INT, VOIDmode, -1)),
5027: benefit);
5028:
5029: case NOT:
5030: /* "~a" is "-a - 1". Silly, but easy. */
5031: return simplify_giv_expr (gen_rtx (MINUS, mode,
5032: gen_rtx (NEG, mode, XEXP (x, 0)),
5033: const1_rtx),
5034: benefit);
5035:
5036: case USE:
5037: /* Already in proper form for invariant. */
5038: return x;
5039:
5040: case REG:
5041: /* If this is a new register, we can't deal with it. */
5042: if (REGNO (x) >= max_reg_before_loop)
5043: return 0;
5044:
5045: /* Check for biv or giv. */
5046: switch (reg_iv_type[REGNO (x)])
5047: {
5048: case BASIC_INDUCT:
5049: return x;
5050: case GENERAL_INDUCT:
5051: {
5052: struct induction *v = reg_iv_info[REGNO (x)];
5053:
5054: /* Form expression from giv and add benefit. Ensure this giv
5055: can derive another and subtract any needed adjustment if so. */
5056: *benefit += v->benefit;
5057: if (v->cant_derive)
5058: return 0;
5059:
5060: tem = gen_rtx (PLUS, mode, gen_rtx (MULT, mode,
5061: v->src_reg, v->mult_val),
5062: v->add_val);
5063: if (v->derive_adjustment)
5064: tem = gen_rtx (MINUS, mode, tem, v->derive_adjustment);
5065: return simplify_giv_expr (tem, benefit);
5066: }
5067: }
5068:
5069: /* Fall through to general case. */
5070: default:
5071: /* If invariant, return as USE (unless CONST_INT).
5072: Otherwise, not giv. */
5073: if (GET_CODE (x) == USE)
5074: x = XEXP (x, 0);
5075:
5076: if (invariant_p (x) == 1)
5077: {
5078: if (GET_CODE (x) == CONST_INT)
5079: return x;
5080: else
5081: return gen_rtx (USE, mode, x);
5082: }
5083: else
5084: return 0;
5085: }
5086: }
5087:
5088: /* Help detect a giv that is calculated by several consecutive insns;
5089: for example,
5090: giv = biv * M
5091: giv = giv + A
5092: The caller has already identified the first insn P as having a giv as dest;
5093: we check that all other insns that set the same register follow
5094: immediately after P, that they alter nothing else,
5095: and that the result of the last is still a giv.
5096:
5097: The value is 0 if the reg set in P is not really a giv.
5098: Otherwise, the value is the amount gained by eliminating
5099: all the consecutive insns that compute the value.
5100:
5101: FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
5102: SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
5103:
5104: The coefficients of the ultimate giv value are stored in
5105: *MULT_VAL and *ADD_VAL. */
5106:
5107: static int
5108: consec_sets_giv (first_benefit, p, src_reg, dest_reg,
5109: add_val, mult_val)
5110: int first_benefit;
5111: rtx p;
5112: rtx src_reg;
5113: rtx dest_reg;
5114: rtx *add_val;
5115: rtx *mult_val;
5116: {
5117: int count;
5118: enum rtx_code code;
5119: int benefit;
5120: rtx temp;
5121: rtx set;
5122:
5123: /* Indicate that this is a giv so that we can update the value produced in
5124: each insn of the multi-insn sequence.
5125:
5126: This induction structure will be used only by the call to
5127: general_induction_var below, so we can allocate it on our stack.
5128: If this is a giv, our caller will replace the induct var entry with
5129: a new induction structure. */
5130: struct induction *v
5131: = (struct induction *) alloca (sizeof (struct induction));
5132: v->src_reg = src_reg;
5133: v->mult_val = *mult_val;
5134: v->add_val = *add_val;
5135: v->benefit = first_benefit;
5136: v->cant_derive = 0;
5137: v->derive_adjustment = 0;
5138:
5139: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
5140: reg_iv_info[REGNO (dest_reg)] = v;
5141:
5142: count = n_times_set[REGNO (dest_reg)] - 1;
5143:
5144: while (count > 0)
5145: {
5146: p = NEXT_INSN (p);
5147: code = GET_CODE (p);
5148:
5149: /* If libcall, skip to end of call sequence. */
5150: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
5151: p = XEXP (temp, 0);
5152:
5153: if (code == INSN
5154: && (set = single_set (p))
5155: && GET_CODE (SET_DEST (set)) == REG
5156: && SET_DEST (set) == dest_reg
5157: && ((benefit = general_induction_var (SET_SRC (set), &src_reg,
5158: add_val, mult_val))
5159: /* Giv created by equivalent expression. */
5160: || ((temp = find_reg_note (p, REG_EQUAL, 0))
5161: && (benefit = general_induction_var (XEXP (temp, 0), &src_reg,
5162: add_val, mult_val))))
5163: && src_reg == v->src_reg)
5164: {
5165: if (find_reg_note (p, REG_RETVAL, 0))
5166: benefit += libcall_benefit (p);
5167:
5168: count--;
5169: v->mult_val = *mult_val;
5170: v->add_val = *add_val;
5171: v->benefit = benefit;
5172: }
5173: else if (code != NOTE)
5174: {
5175: /* Allow insns that set something other than this giv to a
5176: constant. Such insns are needed on machines which cannot
5177: include long constants and should not disqualify a giv. */
5178: if (code == INSN
5179: && (set = single_set (p))
5180: && SET_DEST (set) != dest_reg
5181: && CONSTANT_P (SET_SRC (set)))
5182: continue;
5183:
5184: reg_iv_type[REGNO (dest_reg)] = UNKNOWN_INDUCT;
5185: return 0;
5186: }
5187: }
5188:
5189: return v->benefit;
5190: }
5191:
5192: /* Return an rtx, if any, that expresses giv G2 as a function of the register
5193: represented by G1. If no such expression can be found, or it is clear that
5194: it cannot possibly be a valid address, 0 is returned.
5195:
5196: To perform the computation, we note that
5197: G1 = a * v + b and
5198: G2 = c * v + d
5199: where `v' is the biv.
5200:
5201: So G2 = (c/a) * G1 + (d - b*c/a) */
5202:
5203: #ifdef ADDRESS_COST
5204: static rtx
5205: express_from (g1, g2)
5206: struct induction *g1, *g2;
5207: {
5208: rtx mult, add;
5209:
5210: /* The value that G1 will be multiplied by must be a constant integer. Also,
5211: the only chance we have of getting a valid address is if b*c/a (see above
5212: for notation) is also an integer. */
5213: if (GET_CODE (g1->mult_val) != CONST_INT
5214: || GET_CODE (g2->mult_val) != CONST_INT
5215: || GET_CODE (g1->add_val) != CONST_INT
5216: || g1->mult_val == const0_rtx
5217: || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
5218: return 0;
5219:
5220: mult = gen_rtx (CONST_INT, VOIDmode,
5221: INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
5222: add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult));
5223:
5224: /* Form simplified final result. */
5225: if (mult == const0_rtx)
5226: return add;
5227: else if (mult == const1_rtx)
5228: mult = g1->dest_reg;
5229: else
5230: mult = gen_rtx (MULT, g2->mode, g1->dest_reg, mult);
5231:
5232: if (add == const0_rtx)
5233: return mult;
5234: else
5235: return gen_rtx (PLUS, g2->mode, mult, add);
5236: }
5237: #endif
5238:
5239: /* Return 1 if giv G2 can be combined with G1. This means that G2 can use
5240: (either directly or via an address expression) a register used to represent
5241: G1. Set g2->new_reg to a represtation of G1 (normally just
5242: g1->dest_reg). */
5243:
5244: static int
5245: combine_givs_p (g1, g2)
5246: struct induction *g1, *g2;
5247: {
5248: rtx tem;
5249:
5250: /* If these givs are identical, they can be combined. */
5251: if (rtx_equal_p (g1->mult_val, g2->mult_val)
5252: && rtx_equal_p (g1->add_val, g2->add_val))
5253: {
5254: g2->new_reg = g1->dest_reg;
5255: return 1;
5256: }
5257:
5258: #ifdef ADDRESS_COST
5259: /* If G2 can be expressed as a function of G1 and that function is valid
5260: as an address and no more expensive than using a register for G2,
5261: the expression of G2 in terms of G1 can be used. */
5262: if (g2->giv_type == DEST_ADDR
5263: && (tem = express_from (g1, g2)) != 0
5264: && memory_address_p (g2->mem_mode, tem)
5265: && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location))
5266: {
5267: g2->new_reg = tem;
5268: return 1;
5269: }
5270: #endif
5271:
5272: return 0;
5273: }
5274:
5275: /* Check all pairs of givs for iv_class BL and see if any can be combined with
5276: any other. If so, point SAME to the giv combined with and set NEW_REG to
5277: be an expression (in terms of the other giv's DEST_REG) equivalent to the
5278: giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
5279:
5280: static void
5281: combine_givs (bl)
5282: struct iv_class *bl;
5283: {
5284: struct induction *g1, *g2;
5285: int pass;
5286:
5287: for (g1 = bl->giv; g1; g1 = g1->next_iv)
5288: for (pass = 0; pass <= 1; pass++)
5289: for (g2 = bl->giv; g2; g2 = g2->next_iv)
5290: if (g1 != g2
5291: /* First try to combine with replaceable givs, then all givs. */
5292: && (g1->replaceable || pass == 1)
5293: /* If either has already been combined or is to be ignored, can't
5294: combine. */
5295: && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
5296: /* If something has been based on G2, G2 cannot itself be based
5297: on something else. */
5298: && ! g2->combined_with
5299: && combine_givs_p (g1, g2))
5300: {
5301: /* g2->new_reg set by `combine_givs_p' */
5302: g2->same = g1;
5303: g1->combined_with = 1;
5304: g1->benefit += g2->benefit;
5305: /* ??? The new final_[bg]iv_value code does a much better job
5306: of finding replaceable giv's, and hence this code may no
5307: longer be necessary. */
5308: if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
5309: g1->benefit -= copy_cost;
5310: g1->lifetime += g2->lifetime;
5311: g1->times_used += g2->times_used;
5312:
5313: if (loop_dump_stream)
5314: fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
5315: INSN_UID (g2->insn), INSN_UID (g1->insn));
5316: }
5317: }
5318:
5319: /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
5320:
5321: void
5322: emit_iv_add_mult (b, m, a, reg, insert_before)
5323: rtx b; /* initial value of basic induction variable */
5324: rtx m; /* multiplicative constant */
5325: rtx a; /* additive constant */
5326: rtx reg; /* destination register */
5327: rtx insert_before;
5328: {
5329: rtx seq;
5330: rtx result;
5331:
5332: /* Prevent unexpected sharing of these rtx. */
5333: a = copy_rtx (a);
5334: b = copy_rtx (b);
5335:
5336: /* Increase the lifetime of any invariants moved further in code. */
5337: update_reg_last_use (a, insert_before);
5338: update_reg_last_use (b, insert_before);
5339: update_reg_last_use (m, insert_before);
5340:
5341: start_sequence ();
5342: result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
5343: if (reg != result)
5344: emit_move_insn (reg, result);
5345: seq = gen_sequence ();
5346: end_sequence ();
5347:
5348: emit_insn_before (seq, insert_before);
5349: }
5350:
5351: /* Test whether A * B can be computed without
5352: an actual multiply insn. Value is 1 if so. */
5353:
5354: static int
5355: product_cheap_p (a, b)
5356: rtx a;
5357: rtx b;
5358: {
5359: int i;
5360: rtx tmp;
5361: struct obstack *old_rtl_obstack = rtl_obstack;
5362: char *storage = (char *) obstack_alloc (&temp_obstack, 0);
5363: int win = 1;
5364:
5365: /* If only one is constant, make it B. */
5366: if (GET_CODE (a) == CONST_INT)
5367: tmp = a, a = b, b = tmp;
5368:
5369: /* If first constant, both constant, so don't need multiply. */
5370: if (GET_CODE (a) == CONST_INT)
5371: return 1;
5372:
5373: /* If second not constant, neither is constant, so would need multiply. */
5374: if (GET_CODE (b) != CONST_INT)
5375: return 0;
5376:
5377: /* One operand is constant, so might not need multiply insn. Generate the
5378: code for the multiply and see if a call or multiply, or long sequence
5379: of insns is generated. */
5380:
5381: rtl_obstack = &temp_obstack;
5382: start_sequence ();
5383: expand_mult (GET_MODE (a), a, b, 0, 0);
5384: tmp = gen_sequence ();
5385: end_sequence ();
5386:
5387: if (GET_CODE (tmp) == SEQUENCE)
5388: {
5389: if (XVEC (tmp, 0) == 0)
5390: win = 1;
5391: else if (XVECLEN (tmp, 0) > 3)
5392: win = 0;
5393: else
5394: for (i = 0; i < XVECLEN (tmp, 0); i++)
5395: {
5396: rtx insn = XVECEXP (tmp, 0, i);
5397:
5398: if (GET_CODE (insn) != INSN
5399: || (GET_CODE (PATTERN (insn)) == SET
5400: && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
5401: || (GET_CODE (PATTERN (insn)) == PARALLEL
5402: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
5403: && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
5404: {
5405: win = 0;
5406: break;
5407: }
5408: }
5409: }
5410: else if (GET_CODE (tmp) == SET
5411: && GET_CODE (SET_SRC (tmp)) == MULT)
5412: win = 0;
5413: else if (GET_CODE (tmp) == PARALLEL
5414: && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
5415: && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
5416: win = 0;
5417:
5418: /* Free any storage we obtained in generating this multiply and restore rtl
5419: allocation to its normal obstack. */
5420: obstack_free (&temp_obstack, storage);
5421: rtl_obstack = old_rtl_obstack;
5422:
5423: return win;
5424: }
5425:
5426: /* Check to see if loop can be terminated by a "decrement and branch until
5427: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
5428: Also try reversing an increment loop to a decrement loop
5429: to see if the optimization can be performed.
5430: Value is nonzero if optimization was performed. */
5431:
5432: /* This is useful even if the architecture doesn't have such an insn,
5433: because it might change a loops which increments from 0 to n to a loop
5434: which decrements from n to 0. A loop that decrements to zero is usually
5435: faster than one that increments from zero. */
5436:
5437: /* ??? This could be rewritten to use some of the loop unrolling procedures,
5438: such as approx_final_value, biv_total_increment, loop_iterations, and
5439: final_[bg]iv_value. */
5440:
5441: static int
5442: check_dbra_loop (loop_end, insn_count, loop_start)
5443: rtx loop_end;
5444: int insn_count;
5445: rtx loop_start;
5446: {
5447: struct iv_class *bl;
5448: rtx reg;
5449: rtx jump_label;
5450: rtx final_value;
5451: rtx start_value;
5452: enum rtx_code branch_code;
5453: rtx new_add_val;
5454: rtx comparison;
5455: rtx before_comparison;
5456: rtx p;
5457:
5458: /* If last insn is a conditional branch, and the insn before tests a
5459: register value, try to optimize it. Otherwise, we can't do anything. */
5460:
5461: comparison = get_condition_for_loop (PREV_INSN (loop_end));
5462: if (comparison == 0)
5463: return 0;
5464:
5465: /* Check all of the bivs to see if the compare uses one of them.
5466: Skip biv's set more than once because we can't guarantee that
5467: it will be zero on the last iteration. Also skip if the biv is
5468: used between its update and the test insn. */
5469:
5470: for (bl = loop_iv_list; bl; bl = bl->next)
5471: {
5472: if (bl->biv_count == 1
5473: && bl->biv->dest_reg == XEXP (comparison, 0)
5474: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
5475: PREV_INSN (PREV_INSN (loop_end))))
5476: break;
5477: }
5478:
5479: if (! bl)
5480: return 0;
5481:
5482: /* Look for the case where the basic induction variable is always
5483: nonnegative, and equals zero on the last iteration.
5484: In this case, add a reg_note REG_NONNEG, which allows the
5485: m68k DBRA instruction to be used. */
5486:
5487: if (((GET_CODE (comparison) == GT
5488: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5489: && INTVAL (XEXP (comparison, 1)) == -1)
5490: || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
5491: && GET_CODE (bl->biv->add_val) == CONST_INT
5492: && INTVAL (bl->biv->add_val) < 0)
5493: {
5494: /* Initial value must be greater than 0,
5495: init_val % -dec_value == 0 to ensure that it equals zero on
5496: the last iteration */
5497:
5498: if (GET_CODE (bl->initial_value) == CONST_INT
5499: && INTVAL (bl->initial_value) > 0
5500: && (INTVAL (bl->initial_value) %
5501: (-INTVAL (bl->biv->add_val))) == 0)
5502: {
5503: /* register always nonnegative, add REG_NOTE to branch */
5504: REG_NOTES (PREV_INSN (loop_end))
5505: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5506: REG_NOTES (PREV_INSN (loop_end)));
5507: bl->nonneg = 1;
5508:
5509: return 1;
5510: }
5511:
5512: /* If the decrement is 1 and the value was tested as >= 0 before
5513: the loop, then we can safely optimize. */
5514: for (p = loop_start; p; p = PREV_INSN (p))
5515: {
5516: if (GET_CODE (p) == CODE_LABEL)
5517: break;
5518: if (GET_CODE (p) != JUMP_INSN)
5519: continue;
5520:
5521: before_comparison = get_condition_for_loop (p);
5522: if (before_comparison
5523: && XEXP (before_comparison, 0) == bl->biv->dest_reg
5524: && GET_CODE (before_comparison) == LT
5525: && XEXP (before_comparison, 1) == const0_rtx
5526: && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
5527: && INTVAL (bl->biv->add_val) == -1)
5528: {
5529: REG_NOTES (PREV_INSN (loop_end))
5530: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5531: REG_NOTES (PREV_INSN (loop_end)));
5532: bl->nonneg = 1;
5533:
5534: return 1;
5535: }
5536: }
5537: }
5538: else if (num_mem_sets <= 1)
5539: {
5540: /* Try to change inc to dec, so can apply above optimization. */
5541: /* Can do this if:
5542: all registers modified are induction variables or invariant,
5543: all memory references have non-overlapping addresses
5544: (obviously true if only one write)
5545: allow 2 insns for the compare/jump at the end of the loop. */
5546: int num_nonfixed_reads = 0;
5547: /* 1 if the iteration var is used only to count iterations. */
5548: int no_use_except_counting = 0;
5549:
5550: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5551: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5552: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
5553:
5554: if (bl->giv_count == 0
5555: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
5556: {
5557: rtx bivreg = regno_reg_rtx[bl->regno];
5558:
5559: /* If there are no givs for this biv, and the only exit is the
5560: fall through at the end of the the loop, then
5561: see if perhaps there are no uses except to count. */
5562: no_use_except_counting = 1;
5563: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5564: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5565: {
5566: rtx set = single_set (p);
5567:
5568: if (set && GET_CODE (SET_DEST (set)) == REG
5569: && REGNO (SET_DEST (set)) == bl->regno)
5570: /* An insn that sets the biv is okay. */
5571: ;
5572: else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
5573: || p == prev_nonnote_insn (loop_end))
5574: /* Don't bother about the end test. */
5575: ;
5576: else if (reg_mentioned_p (bivreg, PATTERN (p)))
5577: /* Any other use of the biv is no good. */
5578: {
5579: no_use_except_counting = 0;
5580: break;
5581: }
5582: }
5583: }
5584:
5585: /* This code only acts for innermost loops. Also it simplifies
5586: the memory address check by only reversing loops with
5587: zero or one memory access.
5588: Two memory accesses could involve parts of the same array,
5589: and that can't be reversed. */
5590:
5591: if (num_nonfixed_reads <= 1
5592: && !loop_has_call
1.1.1.3 ! root 5593: && !loop_has_volatile
1.1 root 5594: && (no_use_except_counting
5595: || (bl->giv_count + bl->biv_count + num_mem_sets
5596: + num_movables + 2 == insn_count)))
5597: {
5598: rtx condition = get_condition_for_loop (PREV_INSN (loop_end));
5599: int win;
5600: rtx tem;
5601:
5602: /* Loop can be reversed. */
5603: if (loop_dump_stream)
5604: fprintf (loop_dump_stream, "Can reverse loop\n");
5605:
5606: /* Now check other conditions:
5607: initial_value must be zero,
5608: final_value % add_val == 0, so that when reversed, the
5609: biv will be zero on the last iteration.
5610:
5611: This test can probably be improved since +/- 1 in the constant
5612: can be obtained by changing LT to LE and vice versa; this is
5613: confusing. */
5614:
5615: if (comparison && bl->initial_value == const0_rtx
5616: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5617: /* LE gets turned into LT */
5618: && GET_CODE (comparison) == LT
5619: && (INTVAL (XEXP (comparison, 1))
5620: % INTVAL (bl->biv->add_val)) == 0)
5621: {
5622: /* Register will always be nonnegative, with value
5623: 0 on last iteration if loop reversed */
5624:
5625: /* Save some info needed to produce the new insns. */
5626: reg = bl->biv->dest_reg;
5627: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
5628: new_add_val = gen_rtx (CONST_INT, VOIDmode,
5629: - INTVAL (bl->biv->add_val));
5630:
5631: final_value = XEXP (comparison, 1);
5632: start_value = gen_rtx (CONST_INT, VOIDmode,
5633: (INTVAL (XEXP (comparison, 1))
5634: - INTVAL (bl->biv->add_val)));
5635:
5636: /* Initialize biv to start_value before loop start.
5637: The old initializing insn will be deleted as a
5638: dead store by flow.c. */
5639: emit_insn_before (gen_move_insn (reg, start_value), loop_start);
5640:
5641: /* Add insn to decrement register, and delete insn
5642: that incremented the register. */
5643: p = emit_insn_before (gen_add2_insn (reg, new_add_val),
5644: bl->biv->insn);
5645: delete_insn (bl->biv->insn);
5646:
5647: /* Update biv info to reflect its new status. */
5648: bl->biv->insn = p;
5649: bl->initial_value = start_value;
5650: bl->biv->add_val = new_add_val;
5651:
5652: /* Inc LABEL_NUSES so that delete_insn will
5653: not delete the label. */
5654: LABEL_NUSES (XEXP (jump_label, 0)) ++;
5655:
5656: /* Emit an insn after the end of the loop to set the biv's
5657: proper exit value if it is used anywhere outside the loop. */
5658: if ((regno_last_uid[bl->regno]
5659: != INSN_UID (PREV_INSN (PREV_INSN (loop_end))))
5660: || ! bl->init_insn
5661: || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn))
5662: emit_insn_after (gen_move_insn (reg, final_value),
5663: loop_end);
5664:
5665: /* Delete compare/branch at end of loop. */
5666: delete_insn (PREV_INSN (loop_end));
5667: delete_insn (PREV_INSN (loop_end));
5668:
5669: /* Add new compare/branch insn at end of loop. */
5670: start_sequence ();
5671: emit_cmp_insn (reg, const0_rtx, GE, 0, GET_MODE (reg), 0, 0);
5672: emit_jump_insn (gen_bge (XEXP (jump_label, 0)));
5673: tem = gen_sequence ();
5674: end_sequence ();
5675: emit_jump_insn_before (tem, loop_end);
5676:
5677: for (tem = PREV_INSN (loop_end);
5678: tem && GET_CODE (tem) != JUMP_INSN; tem = PREV_INSN (tem))
5679: ;
5680: if (tem)
5681: {
5682: JUMP_LABEL (tem) = XEXP (jump_label, 0);
5683:
5684: /* Increment of LABEL_NUSES done above. */
5685: /* Register is now always nonnegative,
5686: so add REG_NONNEG note to the branch. */
5687: REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5688: REG_NOTES (tem));
5689: }
5690:
5691: bl->nonneg = 1;
5692:
5693: /* Mark that this biv has been reversed. Each giv which depends
5694: on this biv, and which is also live past the end of the loop
5695: will have to be fixed up. */
5696:
5697: bl->reversed = 1;
5698:
5699: if (loop_dump_stream)
5700: fprintf (loop_dump_stream,
5701: "Reversed loop and added reg_nonneg\n");
5702:
5703: return 1;
5704: }
5705: }
5706: }
5707:
5708: return 0;
5709: }
5710:
5711: /* Verify whether the biv BL appears to be eliminable,
5712: based on the insns in the loop that refer to it.
5713: LOOP_START is the first insn of the loop, and END is the end insn.
5714:
5715: If ELIMINATE_P is non-zero, actually do the elimination.
5716:
5717: THRESHOLD and INSN_COUNT are from loop_optimize and are used to
5718: determine whether invariant insns should be placed inside or at the
5719: start of the loop. */
5720:
5721: static int
5722: maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
5723: struct iv_class *bl;
5724: rtx loop_start;
5725: rtx end;
5726: int eliminate_p;
5727: int threshold, insn_count;
5728: {
5729: rtx reg = bl->biv->dest_reg;
5730: rtx p, set;
5731: struct induction *v;
5732:
5733: /* Scan all insns in the loop, stopping if we find one that uses the
5734: biv in a way that we cannot eliminate. */
5735:
5736: for (p = loop_start; p != end; p = NEXT_INSN (p))
5737: {
5738: enum rtx_code code = GET_CODE (p);
5739: rtx where = threshold >= insn_count ? loop_start : p;
5740:
5741: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
5742: && reg_mentioned_p (reg, PATTERN (p))
5743: && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
5744: {
5745: if (loop_dump_stream)
5746: fprintf (loop_dump_stream,
5747: "Cannot eliminate biv %d: biv used in insn %d.\n",
5748: bl->regno, INSN_UID (p));
5749: break;
5750: }
5751: }
5752:
5753: if (p == end)
5754: {
5755: if (loop_dump_stream)
5756: fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
5757: bl->regno, eliminate_p ? "was" : "can be");
5758: return 1;
5759: }
5760:
5761: return 0;
5762: }
5763:
5764: /* If BL appears in X (part of the pattern of INSN), see if we can
5765: eliminate its use. If so, return 1. If not, return 0.
5766:
5767: If BIV does not appear in X, return 1.
5768:
5769: If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
5770: where extra insns should be added. Depending on how many items have been
5771: moved out of the loop, it will either be before INSN or at the start of
5772: the loop. */
5773:
5774: static int
5775: maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
5776: rtx x, insn;
5777: struct iv_class *bl;
5778: int eliminate_p;
5779: rtx where;
5780: {
5781: enum rtx_code code = GET_CODE (x);
5782: rtx reg = bl->biv->dest_reg;
5783: enum machine_mode mode = GET_MODE (reg);
5784: struct induction *v;
5785: rtx arg, new, tem;
5786: int arg_operand;
5787: char *fmt;
5788: int i, j;
5789:
5790: switch (code)
5791: {
5792: case REG:
5793: /* If we haven't already been able to do something with this BIV,
5794: we can't eliminate it. */
5795: if (x == reg)
5796: return 0;
5797: return 1;
5798:
5799: case SET:
5800: /* If this sets the BIV, it is not a problem. */
5801: if (SET_DEST (x) == reg)
5802: return 1;
5803:
5804: /* If this is an insn that defines a giv, it is also ok because
5805: it will go away when the giv is reduced. */
5806: for (v = bl->giv; v; v = v->next_iv)
5807: if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
5808: return 1;
5809:
5810: #ifdef HAVE_cc0
5811: if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
5812: {
5813: /* Can replace with any giv that was reduced and
5814: that has (MULT_VAL != 0) and (ADD_VAL == 0).
5815: Require a constant for MULT_VAL, so we know it's nonzero. */
5816:
5817: for (v = bl->giv; v; v = v->next_iv)
5818: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5819: && v->add_val == const0_rtx
5820: && ! v->ignore && ! v->maybe_dead
5821: && v->mode == mode)
5822: {
5823: if (! eliminate_p)
5824: return 1;
5825:
5826: /* If the giv has the opposite direction of change,
5827: then reverse the comparison. */
5828: if (INTVAL (v->mult_val) < 0)
5829: new = gen_rtx (COMPARE, GET_MODE (v->new_reg),
5830: const0_rtx, v->new_reg);
5831: else
5832: new = v->new_reg;
5833:
5834: /* We can probably test that giv's reduced reg. */
5835: if (validate_change (insn, &SET_SRC (x), new, 0))
5836: return 1;
5837: }
5838:
5839: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
5840: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
5841: Require a constant for MULT_VAL, so we know it's nonzero. */
5842:
5843: for (v = bl->giv; v; v = v->next_iv)
5844: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5845: && ! v->ignore && ! v->maybe_dead
5846: && v->mode == mode)
5847: {
5848: if (! eliminate_p)
5849: return 1;
5850:
5851: /* If the giv has the opposite direction of change,
5852: then reverse the comparison. */
5853: if (INTVAL (v->mult_val) < 0)
5854: new = gen_rtx (COMPARE, VOIDmode, copy_rtx (v->add_val),
5855: v->new_reg);
5856: else
5857: new = gen_rtx (COMPARE, VOIDmode, v->new_reg,
5858: copy_rtx (v->add_val));
5859:
5860: /* Replace biv with the giv's reduced register. */
5861: update_reg_last_use (v->add_val, insn);
5862: if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
5863: return 1;
5864:
5865: /* Insn doesn't support that constant or invariant. Copy it
5866: into a register (it will be a loop invariant.) */
5867: tem = gen_reg_rtx (GET_MODE (v->new_reg));
5868:
5869: emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
5870: where);
5871:
5872: if (validate_change (insn, &SET_SRC (PATTERN (insn)),
5873: gen_rtx (COMPARE, VOIDmode,
5874: v->new_reg, tem), 0))
5875: return 1;
5876: }
5877: }
5878: #endif
5879: break;
5880:
5881: case COMPARE:
5882: case EQ: case NE:
5883: case GT: case GE: case GTU: case GEU:
5884: case LT: case LE: case LTU: case LEU:
5885: /* See if either argument is the biv. */
5886: if (XEXP (x, 0) == reg)
5887: arg = XEXP (x, 1), arg_operand = 1;
5888: else if (XEXP (x, 1) == reg)
5889: arg = XEXP (x, 0), arg_operand = 0;
5890: else
5891: break;
5892:
5893: if (CONSTANT_P (arg))
5894: {
5895: /* First try to replace with any giv that has constant positive
5896: mult_val and constant add_val. We might be able to support
5897: negative mult_val, but it seems complex to do it in general. */
5898:
5899: for (v = bl->giv; v; v = v->next_iv)
5900: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
5901: && CONSTANT_P (v->add_val)
5902: && ! v->ignore && ! v->maybe_dead
5903: && v->mode == mode)
5904: {
5905: if (! eliminate_p)
5906: return 1;
5907:
5908: /* Replace biv with the giv's reduced reg. */
5909: XEXP (x, 1-arg_operand) = v->new_reg;
5910:
5911: /* If all constants are actually constant integers and
5912: the derived constant can be directly placed in the COMPARE,
5913: do so. */
5914: if (GET_CODE (arg) == CONST_INT
5915: && GET_CODE (v->mult_val) == CONST_INT
5916: && GET_CODE (v->add_val) == CONST_INT
5917: && validate_change (insn, &XEXP (x, arg_operand),
5918: gen_rtx (CONST_INT, VOIDmode,
5919: (INTVAL (arg)
5920: * INTVAL (v->mult_val)
5921: + INTVAL (v->add_val))), 0))
5922: return 1;
5923:
5924: /* Otherwise, load it into a register. */
5925: tem = gen_reg_rtx (mode);
5926: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
5927: if (validate_change (insn, &XEXP (x, arg_operand), tem, 0))
5928: return 1;
5929:
5930: /* If that failed, put back the change we made above. */
5931: XEXP (x, 1-arg_operand) = reg;
5932: }
5933:
5934: /* Look for giv with positive constant mult_val and nonconst add_val.
5935: Insert insns to calculate new compare value. */
5936:
5937: for (v = bl->giv; v; v = v->next_iv)
1.1.1.2 root 5938: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
1.1 root 5939: && ! v->ignore && ! v->maybe_dead
5940: && v->mode == mode)
5941: {
5942: rtx tem;
5943:
5944: if (! eliminate_p)
5945: return 1;
5946:
5947: tem = gen_reg_rtx (mode);
5948:
5949: /* Replace biv with giv's reduced register. */
5950: validate_change (insn, &XEXP (x, 1 - arg_operand),
5951: v->new_reg, 1);
5952:
5953: /* Compute value to compare against. */
5954: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
5955: /* Use it in this insn. */
5956: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
5957: if (apply_change_group ())
5958: return 1;
5959: }
5960: }
5961: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
5962: {
5963: if (invariant_p (arg) == 1)
5964: {
5965: /* Look for giv with constant positive mult_val and nonconst
5966: add_val. Insert insns to compute new compare value. */
5967:
5968: for (v = bl->giv; v; v = v->next_iv)
5969: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
5970: && ! v->ignore && ! v->maybe_dead
5971: && v->mode == mode)
5972: {
5973: rtx tem;
5974:
5975: if (! eliminate_p)
5976: return 1;
5977:
5978: tem = gen_reg_rtx (mode);
5979:
5980: /* Replace biv with giv's reduced register. */
5981: validate_change (insn, &XEXP (x, 1 - arg_operand),
5982: v->new_reg, 1);
5983:
5984: /* Compute value to compare against. */
5985: emit_iv_add_mult (arg, v->mult_val, v->add_val,
5986: tem, where);
5987: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
5988: if (apply_change_group ())
5989: return 1;
5990: }
5991: }
5992:
5993: /* This code has problems. Basically, you can't know when
5994: seeing if we will eliminate BL, whether a particular giv
5995: of ARG will be reduced. If it isn't going to be reduced,
5996: we can't eliminate BL. We can try forcing it to be reduced,
5997: but that can generate poor code.
5998:
5999: The problem is that the benefit of reducing TV, below should
6000: be increased if BL can actually be eliminated, but this means
6001: we might have to do a topological sort of the order in which
6002: we try to process biv. It doesn't seem worthwhile to do
6003: this sort of thing now. */
6004:
6005: #if 0
6006: /* Otherwise the reg compared with had better be a biv. */
6007: if (GET_CODE (arg) != REG
6008: || reg_iv_type[REGNO (arg)] != BASIC_INDUCT)
6009: return 0;
6010:
6011: /* Look for a pair of givs, one for each biv,
6012: with identical coefficients. */
6013: for (v = bl->giv; v; v = v->next_iv)
6014: {
6015: struct induction *tv;
6016:
6017: if (v->ignore || v->maybe_dead || v->mode != mode)
6018: continue;
6019:
6020: for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
6021: if (! tv->ignore && ! tv->maybe_dead
6022: && rtx_equal_p (tv->mult_val, v->mult_val)
6023: && rtx_equal_p (tv->add_val, v->add_val)
6024: && tv->mode == mode)
6025: {
6026: if (! eliminate_p)
6027: return 1;
6028:
6029: /* Replace biv with its giv's reduced reg. */
6030: XEXP (x, 1-arg_operand) = v->new_reg;
6031: /* Replace other operand with the other giv's
6032: reduced reg. */
6033: XEXP (x, arg_operand) = tv->new_reg;
6034: return 1;
6035: }
6036: }
6037: #endif
6038: }
6039:
6040: /* If we get here, the biv can't be eliminated. */
6041: return 0;
6042:
6043: case MEM:
6044: /* If this address is a DEST_ADDR giv, it doesn't matter if the
6045: biv is used in it, since it will be replaced. */
6046: for (v = bl->giv; v; v = v->next_iv)
6047: if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
6048: return 1;
6049: break;
6050: }
6051:
6052: /* See if any subexpression fails elimination. */
6053: fmt = GET_RTX_FORMAT (code);
6054: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
6055: {
6056: switch (fmt[i])
6057: {
6058: case 'e':
6059: if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl,
6060: eliminate_p, where))
6061: return 0;
6062: break;
6063:
6064: case 'E':
6065: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6066: if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl,
6067: eliminate_p, where))
6068: return 0;
6069: break;
6070: }
6071: }
6072:
6073: return 1;
6074: }
6075:
6076: /* Return nonzero if the last use of REG
6077: is in an insn following INSN in the same basic block. */
6078:
6079: static int
6080: last_use_this_basic_block (reg, insn)
6081: rtx reg;
6082: rtx insn;
6083: {
6084: rtx n;
6085: for (n = insn;
6086: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
6087: n = NEXT_INSN (n))
6088: {
6089: if (regno_last_uid[REGNO (reg)] == INSN_UID (n))
6090: return 1;
6091: }
6092: return 0;
6093: }
6094:
6095: /* Called via `note_stores' to record the initial value of a biv. Here we
6096: just record the location of the set and process it later. */
6097:
6098: static void
6099: record_initial (dest, set)
6100: rtx dest;
6101: rtx set;
6102: {
6103: struct iv_class *bl;
6104:
6105: if (GET_CODE (dest) != REG
6106: || REGNO (dest) >= max_reg_before_loop
6107: || reg_iv_type[REGNO (dest)] != BASIC_INDUCT)
6108: return;
6109:
6110: bl = reg_biv_class[REGNO (dest)];
6111:
6112: /* If this is the first set found, record it. */
6113: if (bl->init_insn == 0)
6114: {
6115: bl->init_insn = note_insn;
6116: bl->init_set = set;
6117: }
6118: }
6119:
6120: /* If any of the registers in X are "old" and currently have a last use earlier
6121: than INSN, update them to have a last use of INSN. Their actual last use
6122: will be the previous insn but it will not have a valid uid_luid so we can't
6123: use it. */
6124:
6125: static void
6126: update_reg_last_use (x, insn)
6127: rtx x;
6128: rtx insn;
6129: {
6130: /* Check for the case where INSN does not have a valid luid. In this case,
6131: there is no need to modify the regno_last_uid, as this can only happen
6132: when code is inserted after the loop_end to set a pseudo's final value,
6133: and hence this insn will never be the last use of x. */
6134: if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
6135: && INSN_UID (insn) < max_uid_for_loop
6136: && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)])
6137: regno_last_uid[REGNO (x)] = INSN_UID (insn);
6138: else
6139: {
6140: register int i, j;
6141: register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
6142: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
6143: {
6144: if (fmt[i] == 'e')
6145: update_reg_last_use (XEXP (x, i), insn);
6146: else if (fmt[i] == 'E')
6147: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6148: update_reg_last_use (XVECEXP (x, i, j), insn);
6149: }
6150: }
6151: }
6152:
6153: /* Given a jump insn JUMP, return the condition that will cause it to branch
6154: to its JUMP_LABEL. If the condition cannot be understood, or is an
6155: inequality floating-point comparison which needs to be reversed, 0 will
6156: be returned.
6157:
6158: If EARLIEST is non-zero, it is a pointer to a place where the earliest
6159: insn used in locating the condition was found. If a replacement test
6160: of the condition is desired, it should be placed in front of that
6161: insn and we will be sure that the inputs are still valid.
6162:
6163: The condition will be returned in a canonical form to simplify testing by
6164: callers. Specifically:
6165:
6166: (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
6167: (2) Both operands will be machine operands; (cc0) will have been replaced.
6168: (3) If an operand is a constant, it will be the second operand.
6169: (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
6170: for GE, GEU, and LEU. */
6171:
6172: rtx
6173: get_condition (jump, earliest)
6174: rtx jump;
6175: rtx *earliest;
6176: {
6177: enum rtx_code code;
6178: rtx prev = jump;
6179: rtx set;
6180: rtx tem;
6181: rtx op0, op1;
6182: int reverse_code = 0;
6183: int did_reverse_condition = 0;
6184:
6185: /* If this is not a standard conditional jump, we can't parse it. */
6186: if (GET_CODE (jump) != JUMP_INSN
6187: || ! condjump_p (jump) || simplejump_p (jump))
6188: return 0;
6189:
6190: code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0));
6191: op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0);
6192: op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1);
6193:
6194: if (earliest)
6195: *earliest = jump;
6196:
6197: /* If this branches to JUMP_LABEL when the condition is false, reverse
6198: the condition. */
6199: if (XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump))
6200: code = reverse_condition (code), did_reverse_condition ^= 1;
6201:
6202: /* If we are comparing a register with zero, see if the register is set
6203: in the previous insn to a COMPARE or a comparison operation. Perform
6204: the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
6205: in cse.c */
6206:
6207: while (GET_RTX_CLASS (code) == '<' && op1 == const0_rtx)
6208: {
6209: /* Set non-zero when we find something of interest. */
6210: rtx x = 0;
6211:
6212: #ifdef HAVE_cc0
6213: /* If comparison with cc0, import actual comparison from compare
6214: insn. */
6215: if (op0 == cc0_rtx)
6216: {
6217: if ((prev = prev_nonnote_insn (prev)) == 0
6218: || GET_CODE (prev) != INSN
6219: || (set = single_set (prev)) == 0
6220: || SET_DEST (set) != cc0_rtx)
6221: return 0;
6222:
6223: op0 = SET_SRC (set);
6224: op1 = CONST0_RTX (GET_MODE (op0));
6225: if (earliest)
6226: *earliest = prev;
6227: }
6228: #endif
6229:
6230: /* If this is a COMPARE, pick up the two things being compared. */
6231: if (GET_CODE (op0) == COMPARE)
6232: {
6233: op1 = XEXP (op0, 1);
6234: op0 = XEXP (op0, 0);
6235: continue;
6236: }
6237: else if (GET_CODE (op0) != REG)
6238: break;
6239:
6240: /* Go back to the previous insn. Stop if it is not an INSN. We also
6241: stop if it isn't a single set or if it has a REG_INC note because
6242: we don't want to bother dealing with it. */
6243:
6244: if ((prev = prev_nonnote_insn (prev)) == 0
6245: || GET_CODE (prev) != INSN
6246: || FIND_REG_INC_NOTE (prev, 0)
6247: || (set = single_set (prev)) == 0)
6248: break;
6249:
6250: /* If this is setting OP0, get what it sets it to if it looks
6251: relevant. */
6252: if (SET_DEST (set) == op0)
6253: {
6254: enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
6255:
6256: if ((GET_CODE (SET_SRC (set)) == COMPARE
6257: || ((code == NE
6258: || (code == LT
6259: && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
6260: && (STORE_FLAG_VALUE
6261: & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
6262: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')))
6263: x = SET_SRC (set);
6264: else if ((code == EQ
6265: || (code == GE
6266: && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
6267: && (STORE_FLAG_VALUE
6268: & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
6269: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')
6270: {
6271: /* We might have reversed a LT to get a GE here. But this wasn't
6272: actually the comparison of data, so we don't flag that we
6273: have had to reverse the condition. */
6274: did_reverse_condition ^= 1;
6275: reverse_code = 1;
6276: x = SET_SRC (set);
6277: }
6278: }
6279:
6280: else if (reg_set_p (op0, prev))
6281: /* If this sets OP0, but not directly, we have to give up. */
6282: break;
6283:
6284: if (x)
6285: {
6286: if (GET_RTX_CLASS (GET_CODE (x)) == '<')
6287: code = GET_CODE (x);
6288: if (reverse_code)
6289: {
6290: code = reverse_condition (code);
6291: did_reverse_condition ^= 1;
6292: reverse_code = 0;
6293: }
6294:
6295: op0 = XEXP (x, 0), op1 = XEXP (x, 1);
6296: if (earliest)
6297: *earliest = prev;
6298: }
6299: }
6300:
6301: /* If constant is first, put it last. */
6302: if (CONSTANT_P (op0))
6303: code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
6304:
6305: /* If OP0 is the result of a comparison, we weren't able to find what
6306: was really being compared, so fail. */
6307: if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
6308: return 0;
6309:
6310: /* Canonicalize any ordered comparison with integers involving equality. */
6311: if (GET_CODE (op1) == CONST_INT)
6312: {
6313: int const_val = INTVAL (op1);
6314: unsigned uconst_val = (unsigned) const_val;
6315:
6316: switch (code)
6317: {
6318: case LE:
6319: code = LT;
6320: op1 = gen_rtx (CONST_INT, VOIDmode, const_val + 1);
6321: break;
6322:
6323: case GE:
6324: code = GT;
6325: op1 = gen_rtx (CONST_INT, VOIDmode, const_val - 1);
6326: break;
6327:
6328: case LEU:
6329: code = LTU;
6330: op1 = gen_rtx (CONST_INT, VOIDmode, uconst_val + 1);
6331: break;
6332:
6333: case GEU:
6334: code = GTU;
6335: op1 = gen_rtx (CONST_INT, VOIDmode, uconst_val - 1);
6336: break;
6337: }
6338: }
6339:
6340: /* If this was floating-point and we reversed anything other than an
6341: EQ or NE, return zero. */
6342: if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
6343: && did_reverse_condition && code != NE && code != EQ
6344: && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
6345: return 0;
6346:
6347: #ifdef HAVE_cc0
6348: /* Never return CC0; return zero instead. */
6349: if (op0 == cc0_rtx)
6350: return 0;
6351: #endif
6352:
6353: return gen_rtx (code, VOIDmode, op0, op1);
6354: }
6355:
6356: /* Similar to above routine, except that we also put an invariant last
6357: unless both operands are invariants. */
6358:
6359: rtx
6360: get_condition_for_loop (x)
6361: rtx x;
6362: {
6363: rtx comparison = get_condition (x, 0);
6364:
6365: if (comparison == 0
6366: || ! invariant_p (XEXP (comparison, 0))
6367: || invariant_p (XEXP (comparison, 1)))
6368: return comparison;
6369:
6370: return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode,
6371: XEXP (comparison, 1), XEXP (comparison, 0));
6372: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.