![[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 1.x] / gcc|
Return to loop.c CVS log | Up to [GCC 1.x] / gcc |
1.1 root 1: /* Move constant computations out of loops.
1.1.1.15 root 2: Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc.
1.1 root 3:
4: This file is part of GNU CC.
5:
1.1.1.13 root 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 1, or (at your option)
9: any later version.
10:
1.1 root 11: GNU CC is distributed in the hope that it will be useful,
1.1.1.13 root 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. */
1.1 root 19:
20:
21: /* This is the loop optimization pass of the compiler.
22: It finds invariant computations within loops and moves them
1.1.1.8 root 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.
1.1 root 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: /* ??? verify_loop would run faster if we made one table
37: of the minimum and maximum luids from which each label is reached.
38: Also, it would be faster if loop_store_addrs were a hash table. */
39:
40: #include "config.h"
41: #include "rtl.h"
1.1.1.10 root 42: #include "expr.h"
1.1 root 43: #include "insn-config.h"
44: #include "regs.h"
1.1.1.15 root 45: #include "hard-reg-set.h"
1.1 root 46: #include "recog.h"
1.1.1.8 root 47: #include "flags.h"
1.1.1.2 root 48: #include <stdio.h>
1.1 root 49:
50: /* Vector mapping INSN_UIDs to luids.
51: The luids are like uids but increase monononically always.
52: We use them to see whether a jump comes from outside a given loop. */
53:
1.1.1.16 root 54: static int *uid_luid;
1.1 root 55:
56: /* Get the luid of an insn. */
57:
58: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)])
59:
60: /* 1 + largest uid of any insn. */
61:
62: static int max_uid;
63:
64: /* 1 + luid of last insn. */
65:
66: static int max_luid;
67:
68: /* Nonzero if somewhere in the current loop
69: there is either a subroutine call,
70: or a store into a memory address that is not fixed,
71: or a store in a BLKmode memory operand,
72: or too many different fixed addresses stored in
73: to record them all in `loop_store_addrs'.
74:
75: In any of these cases, no memory location can be regarded
76: as invariant. */
77:
78: static int unknown_address_altered;
79:
80: /* Nonzero if somewhere in the current loop there is a store
81: into a memory address that is not fixed but is known to be
82: part of an aggregate.
83:
84: In this case, no memory reference in an aggregate may be
85: considered invariant. */
86:
87: static int unknown_aggregate_altered;
88:
89: /* Nonzero if somewhere in the current loop there is a store
90: into a memory address other than a fixed address not in an aggregate.
91:
92: In this case, no memory reference in an aggregate at a varying address
93: may be considered invariant. */
94:
95: static int fixed_aggregate_altered;
96:
97: /* Nonzero if there is a subroutine call in the current loop.
98: (unknown_address_altered is also nonzero in this case.) */
99:
100: static int loop_has_call;
101:
1.1.1.14 root 102: /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
103: current loop. A continue statement will generate a branch to
104: NEXT_INSN (loop_continue). */
105:
106: static rtx loop_continue;
107:
1.1.1.8 root 108: /* Indexed by register number, contains the number of times the reg
1.1.1.10 root 109: is set during the loop being scanned.
110: During code motion, -1 indicates a reg that has been made a candidate.
111: After code motion, regs moved have 0 (which is accurate now)
112: while the failed candidates have the original number of times set.
113:
114: Therefore, at all times, 0 indicates an invariant register;
115: -1 a conditionally invariant one. */
1.1.1.8 root 116:
117: static short *n_times_set;
118:
1.1.1.10 root 119: /* Original value of n_times_set; same except that this value
120: is not set to -1 for a reg whose sets have been made candidates
121: and not set to 0 for a reg that is moved. */
1.1.1.8 root 122:
123: static short *n_times_used;
124:
1.1.1.17! root 125: /* Index by register number, 1 indicates that the register
! 126: cannot be moved or strength reduced. */
! 127:
! 128: static char *may_not_optimize;
! 129:
1.1.1.12 root 130: /* Nonzero means reg N has already been moved out of one loop.
131: This reduces the desire to move it out of another. */
132:
133: static char *moved_once;
134:
1.1 root 135: /* Array of fixed memory addresses that are stored in this loop.
136: If there are too many to fit here,
137: we just turn on unknown_address_altered. */
138:
139: #define NUM_STORES 10
140: static rtx loop_store_addrs[NUM_STORES];
141: static int loop_store_widths[NUM_STORES];
142:
143: /* Index of first available slot in above array. */
144: static int loop_store_addrs_idx;
145:
1.1.1.8 root 146: /* Count of movable (i.e. invariant) instructions discovered in the loop. */
147: static int num_movables;
148:
149: /* Count of memory write instructions discovered in the loop. */
150: static int num_mem_sets;
151:
152: /* Number of loops contained within the current one, including itself. */
153: static int loops_enclosed;
154:
155: /* Bound on pseudo register number before loop optimization.
156: A pseudo has valid regscan info if its number is < old_max_reg. */
157: static int old_max_reg;
158:
1.1 root 159: /* During the analysis of a loop, a chain of `struct movable's
160: is made to record all the movable insns found.
161: Then the entire chain can be scanned to decide which to move. */
162:
163: struct movable
164: {
165: rtx insn; /* A movable insn */
1.1.1.8 root 166: rtx set_src; /* The expression this reg is set from.
167: Either SET_SRC (body) or a REG_EQUAL. */
1.1.1.2 root 168: int consec; /* Number of consecutive following insns
169: that must be moved with this one. */
1.1 root 170: int regno; /* The register it sets */
171: short lifetime; /* lifetime of that register;
172: may be adjusted when matching movables
173: that load the same value are found. */
1.1.1.10 root 174: short savings; /* Number of insns we can move for this reg,
175: including other movables that force this
176: or match this one. */
1.1 root 177: unsigned int cond : 1; /* 1 if only conditionally movable */
178: unsigned int force : 1; /* 1 means MUST move this insn */
179: unsigned int global : 1; /* 1 means reg is live outside this loop */
1.1.1.15 root 180: /* If PARTIAL is 1, GLOBAL means something different:
181: that the reg is live outside the range from where it is set
182: to the following label. */
1.1.1.2 root 183: unsigned int done : 1; /* 1 inhibits further processing of this */
1.1.1.15 root 184: /* 1 in PARTIAL means this reg is used for zero-extending.
185: In particular, moving it does not make it invariant. */
186: unsigned int partial : 1;
1.1.1.14 root 187: enum machine_mode savemode; /* Nonzero means it is a mode for a low part
188: that we should avoid changing when clearing
189: the rest of the reg. */
1.1 root 190: struct movable *match; /* First entry for same value */
191: struct movable *forces; /* An insn that must be moved if this is */
192: struct movable *next;
193: };
194:
1.1.1.2 root 195: static FILE *loop_dump_stream;
196:
1.1.1.15 root 197: /* Forward declarations. */
198:
199: struct induction;
200: struct iv_class;
201:
1.1.1.17! root 202: static rtx loop_find_reg_equal ();
1.1 root 203: static rtx verify_loop ();
204: static int invariant_p ();
1.1.1.4 root 205: static int consec_sets_invariant_p ();
1.1 root 206: static int can_jump_into_range_p ();
1.1.1.15 root 207: static int labels_in_range_p ();
1.1 root 208: static void count_loop_regs_set ();
209: static void note_addr_stored ();
210: static int loop_reg_used_before_p ();
211: static void constant_high_bytes ();
212: static void scan_loop ();
213: static rtx replace_regs ();
1.1.1.9 root 214: static void replace_call_address ();
1.1.1.15 root 215: static rtx skip_consec_insns ();
216: static void ignore_some_movables ();
217: static void force_movables ();
218: static void combine_movables ();
219: static int rtx_equal_for_loop_p ();
1.1.1.2 root 220: static void move_movables ();
1.1.1.8 root 221: static void strength_reduce ();
222: static void find_mem_givs ();
223: static void record_giv ();
224: static void delete_insn_forces ();
225: static int basic_induction_var ();
226: static int general_induction_var ();
227: static int consec_sets_giv ();
228: static int check_dbra_loop ();
229: static void emit_iv_init_code ();
230: static int product_cheap_p ();
231: static void emit_iv_inc ();
1.1.1.14 root 232: static void check_eliminate_biv ();
1.1.1.8 root 233: static int can_eliminate_biv_p ();
234: static void eliminate_biv ();
235: static rtx final_biv_value ();
1.1.1.11 root 236: static int last_use_this_basic_block ();
1.1 root 237:
238: /* Entry point of this file. Perform loop optimization
239: on the current function. F is the first insn of the function
1.1.1.13 root 240: and DUMPFILE is a stream for output of a trace of actions taken
241: (or 0 if none should be output). */
1.1 root 242:
1.1.1.2 root 243: void
1.1.1.8 root 244: loop_optimize (f, dumpfile)
1.1 root 245: /* f is the first instruction of a chain of insns for one function */
246: rtx f;
1.1.1.2 root 247: FILE *dumpfile;
1.1 root 248: {
249: register rtx insn;
250: register int i;
251: rtx end;
252: rtx last_insn;
253:
1.1.1.2 root 254: loop_dump_stream = dumpfile;
255:
1.1 root 256: init_recog ();
257:
1.1.1.10 root 258: old_max_reg = max_reg_num ();
1.1.1.8 root 259:
1.1.1.12 root 260: moved_once = (char *) alloca (old_max_reg);
261: bzero (moved_once, old_max_reg);
262:
1.1 root 263: /* First find the last real insn, and count the number of insns,
1.1.1.15 root 264: and assign insns their luids. */
1.1 root 265:
266: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
267: if (INSN_UID (insn) > i)
268: i = INSN_UID (insn);
269:
270: max_uid = i + 1;
1.1.1.16 root 271: uid_luid = (int *) alloca ((i + 1) * sizeof (int));
272: bzero (uid_luid, (i + 1) * sizeof (int));
1.1 root 273:
274: /* Compute the mapping from uids to luids.
275: LUIDs are numbers assigned to insns, like uids,
1.1.1.15 root 276: except that luids increase monotonically through the code.
277: Don't assign luids to line-number NOTEs, so that the distance in luids
278: between two insns is not affected by -g. */
1.1 root 279:
280: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
281: {
282: last_insn = insn;
1.1.1.15 root 283: if (GET_CODE (insn) != NOTE
284: || NOTE_LINE_NUMBER (insn) < 0)
285: INSN_LUID (insn) = ++i;
286: else
287: /* Give a line number note the same luid as preceding insn. */
288: INSN_LUID (insn) = i;
1.1 root 289: }
290:
291: max_luid = i;
292:
293: /* Don't leave gaps in uid_luid for insns that have been
294: deleted. It is possible that the first or last insn
295: using some register has been deleted by cross-jumping.
296: Make sure that uid_luid for that former insn's uid
297: points to the general area where that insn used to be. */
298: for (i = 0; i < max_uid; i++)
1.1.1.2 root 299: {
300: uid_luid[0] = uid_luid[i];
301: if (uid_luid[0] != 0)
302: break;
303: }
304: for (i = 0; i < max_uid; i++)
1.1 root 305: if (uid_luid[i] == 0)
306: uid_luid[i] = uid_luid[i - 1];
307:
308: /* Find and process each loop.
309: We scan from the end, and process each loop when its start is seen,
310: so we process innermost loops first. */
311:
312: for (insn = last_insn; insn; insn = PREV_INSN (insn))
313: if (GET_CODE (insn) == NOTE
1.1.1.4 root 314: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
315: {
1.1 root 316: /* Make sure it really is a loop -- no jumps in from outside. */
1.1.1.4 root 317: end = verify_loop (f, insn);
318: if (end != 0)
319: /* If so, optimize this loop. */
1.1.1.8 root 320: scan_loop (insn, end, max_reg_num ());
1.1.1.4 root 321: else if (loop_dump_stream)
322: fprintf (loop_dump_stream,
323: "\nLoop at %d ignored due to multiple entry points.\n",
324: INSN_UID (insn));
325: }
1.1 root 326: }
327:
328: /* Optimize one loop whose start is LOOP_START and end is END.
329: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
330: NOTE_INSN_LOOP_END. */
331:
1.1.1.8 root 332: /* ??? can also move memory writes out of loop if destination
333: address is invariant? */
334:
1.1 root 335: static void
336: scan_loop (loop_start, end, nregs)
337: rtx loop_start, end;
338: int nregs;
339: {
340: register int i;
341: register rtx p = NEXT_INSN (loop_start);
342: /* 1 if we are scanning insns that could be executed zero times. */
343: int maybe_never = 0;
1.1.1.3 root 344: /* 1 if we are scanning insns that might never be executed
345: due to a subroutine call which might exit before they are reached. */
346: int call_passed = 0;
1.1 root 347: /* For a rotated loop that is entered near the bottom,
348: this is the label at the top. Otherwise it is zero. */
349: rtx loop_top = 0;
350: /* Jump insn that enters the loop, or 0 if control drops in. */
351: rtx loop_entry_jump = 0;
352: /* Place in the loop where control enters. */
353: rtx scan_start;
354: /* Number of insns in the loop. */
355: int insn_count;
356: int tem;
1.1.1.8 root 357: rtx temp;
1.1 root 358: /* Chain describing insns movable in current loop. */
359: struct movable *movables = 0;
360: /* Last element in `movables' -- so we can add elements at the end. */
361: struct movable *last_movable = 0;
362: /* Ratio of extra register life span we can justify
363: for saving an instruction. More if loop doesn't call subroutines
364: since in that case saving an insn makes more difference
365: and more registers are available. */
1.1.1.10 root 366: int threshold = loop_has_call ? 15 : 30;
1.1.1.7 root 367: /* Nonzero if the insn that jumps into the real loop
368: is not the very first thing after the loop-beginning note. */
369: int something_before_entry_jump = 0;
1.1 root 370:
371: n_times_set = (short *) alloca (nregs * sizeof (short));
372: n_times_used = (short *) alloca (nregs * sizeof (short));
1.1.1.17! root 373: may_not_optimize = (char *) alloca (nregs);
1.1 root 374:
375: /* Determine whether this loop starts with a jump down
376: to a test at the end. */
377: while (p != end
378: && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN)
1.1.1.7 root 379: {
380: if (GET_CODE (p) == CALL_INSN || GET_CODE (p) == INSN)
381: something_before_entry_jump = 1;
382: p = NEXT_INSN (p);
383: }
1.1 root 384:
385: /* "Loop" contains neither jumps nor labels;
386: it must have been a dummy. Think no more about it. */
387: if (p == end)
388: return;
389:
1.1.1.2 root 390: scan_start = p;
391:
1.1 root 392: /* If loop has a jump before the first label,
393: the true entry is the target of that jump.
394: Start scan from there.
395: But record in LOOP_TOP the place where the end-test jumps
396: back to so we can scan that after the end of the loop. */
397: if (GET_CODE (p) == JUMP_INSN)
398: {
399: loop_entry_jump = p;
400: loop_top = NEXT_INSN (p);
401: /* Loop entry will never be a conditional jump.
1.1.1.8 root 402: If we see one, this must not be a real loop.
403: Also, a return-insn isn't a jump to enter the loop. */
404: if (GET_CODE (loop_top) != BARRIER
405: || GET_CODE (PATTERN (p)) != SET)
1.1 root 406: return;
1.1.1.5 root 407: /* Get the label at which the loop is entered. */
408: p = XEXP (SET_SRC (PATTERN (p)), 0);
1.1 root 409: /* Check to see whether the jump actually
410: jumps out of the loop (meaning it's no loop).
411: This case can happen for things like
412: do {..} while (0). */
1.1.1.2 root 413: if (p == 0
414: || INSN_LUID (p) < INSN_LUID (loop_start)
1.1 root 415: || INSN_LUID (p) >= INSN_LUID (end))
1.1.1.2 root 416: {
417: if (loop_dump_stream)
418: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
419: INSN_UID (loop_start), INSN_UID (end));
420: return;
421: }
422:
423: /* Find the first label after the entry-jump. */
424: while (GET_CODE (loop_top) != CODE_LABEL)
425: {
426: loop_top = NEXT_INSN (loop_top);
427: if (loop_top == 0)
428: abort ();
429: }
430:
431: /* Maybe rearrange the loop to drop straight in
432: with a new test to jump around it entirely.
433: (The latter is considered outside the loop.)
434: If this is done, we no longer enter with a jump. */
1.1.1.7 root 435: if (! something_before_entry_jump
436: && loop_skip_over (loop_start, end, loop_entry_jump))
1.1.1.8 root 437: {
438: scan_start = loop_top;
439: loop_top = 0;
440: }
1.1.1.2 root 441: else
442: /* We really do enter with a jump;
443: scan the loop from the place where the jump jumps to. */
444: scan_start = p;
1.1 root 445: }
446:
447: /* Count number of times each reg is set during this loop.
1.1.1.17! root 448: Set may_not_optimize[I] if it is not safe to move out
1.1 root 449: the setting of register I. */
450:
451: bzero (n_times_set, nregs * sizeof (short));
1.1.1.17! root 452: bzero (may_not_optimize, nregs);
1.1.1.2 root 453: count_loop_regs_set (loop_top ? loop_top : loop_start, end,
1.1.1.17! root 454: may_not_optimize, &insn_count, nregs);
1.1 root 455: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1.1.1.17! root 456: may_not_optimize[i] = 1, n_times_set[i] = 1;
1.1 root 457: bcopy (n_times_set, n_times_used, nregs * sizeof (short));
458:
1.1.1.2 root 459: if (loop_dump_stream)
1.1.1.14 root 460: {
461: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
462: INSN_UID (loop_start), INSN_UID (end), insn_count);
463: if (loop_continue)
464: fprintf (loop_dump_stream, "Continue at insn %d.\n",
465: INSN_UID (loop_continue));
466: }
1.1.1.2 root 467:
1.1 root 468: /* Scan through the loop finding insns that are safe to move.
469: In each such insn, store QImode as the mode, to mark it.
470: Then set n_times_set to -1 for the reg being set, so that
471: this reg will be considered invariant for subsequent insns.
472: We consider whether subsequent insns use the reg
473: in deciding whether it is worth actually moving.
474:
475: MAYBE_NEVER is nonzero if we have passed a conditional jump insn
476: and therefore it is possible that the insns we are scanning
477: would never be executed. At such times, we must make sure
478: that it is safe to execute the insn once instead of zero times.
479: When MAYBE_NEVER is 0, all insns will be executed at least once
480: so that is not a problem. */
481:
1.1.1.2 root 482: p = scan_start;
1.1 root 483: while (1)
484: {
485: p = NEXT_INSN (p);
486: /* At end of a straight-in loop, we are done.
487: At end of a loop entered at the bottom, scan the top. */
488: if (p == scan_start)
489: break;
490: if (p == end)
491: {
492: if (loop_top != 0)
493: p = NEXT_INSN (loop_top);
494: else
495: break;
496: if (p == scan_start)
497: break;
498: }
499: if (GET_CODE (p) == INSN
500: && GET_CODE (PATTERN (p)) == SET
501: && GET_CODE (SET_DEST (PATTERN (p))) == REG
1.1.1.17! root 502: && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))])
1.1 root 503: {
1.1.1.4 root 504: int tem1 = 0;
1.1.1.11 root 505: /* Don't try to optimize a register that was made
506: by loop-optimization for an inner loop.
507: We don't know its life-span, so we can't compute the benefit. */
508: if (REGNO (SET_DEST (PATTERN (p))) >= old_max_reg)
509: ;
1.1 root 510: /* If this register is used or set outside the loop,
511: then we can move it only if we know this insn is
512: executed exactly once per iteration,
513: and we can check all the insns executed before it
514: to make sure none of them used the value that
515: was lying around at entry to the loop. */
1.1.1.11 root 516: else if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end)
517: || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start))
518: && (maybe_never
519: || loop_reg_used_before_p (p, loop_start, scan_start, end)))
1.1 root 520: ;
1.1.1.8 root 521: else if (((tem = invariant_p (SET_SRC (PATTERN (p))))
1.1.1.17! root 522: || ((temp = loop_find_reg_equal (p))
1.1.1.8 root 523: && (tem = invariant_p (XEXP (temp, 0)))))
1.1 root 524: && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1
1.1.1.4 root 525: || (tem1
526: = consec_sets_invariant_p (SET_DEST (PATTERN (p)),
527: n_times_set[REGNO (SET_DEST (PATTERN (p)))],
1.1.1.8 root 528: p)))
1.1.1.3 root 529: /* If the insn can cause a trap (such as divide by zero),
530: can't move it unless it's guaranteed to be executed
531: once loop is entered. Even a function call might
532: prevent the trap insn from being reached
533: (since it might exit!) */
534: && ! ((maybe_never || call_passed)
1.1.1.8 root 535: && (may_trap_p (SET_SRC (PATTERN (p)))
1.1.1.17! root 536: || ((temp = loop_find_reg_equal (p))
1.1.1.8 root 537: && may_trap_p (XEXP (temp, 0))))))
1.1 root 538: {
539: register struct movable *m;
540: register int regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.2 root 541: int count;
1.1 root 542: m = (struct movable *) alloca (sizeof (struct movable));
543: m->next = 0;
544: m->insn = p;
1.1.1.17! root 545: temp = loop_find_reg_equal (p);
1.1.1.8 root 546: if (temp)
547: m->set_src = XEXP (temp, 0);
548: else
549: m->set_src = SET_SRC (PATTERN (p));
1.1 root 550: m->force = 0;
1.1.1.2 root 551: m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1;
552: m->done = 0;
1.1 root 553: m->forces = 0;
1.1.1.2 root 554: m->partial = 0;
1.1.1.14 root 555: m->savemode = VOIDmode;
1.1 root 556: m->regno = regno;
1.1.1.4 root 557: /* Set M->cond if either invariant_p or consec_sets_invariant_p
558: returned 2 (only conditionally invariant). */
559: m->cond = ((tem | tem1) > 1);
1.1 root 560: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
561: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
562: m->match = 0;
563: m->lifetime = (uid_luid[regno_last_uid[regno]]
564: - uid_luid[regno_first_uid[regno]]);
1.1.1.10 root 565: m->savings = n_times_used[regno];
1.1 root 566: n_times_set[regno] = -1;
567: /* Add M to the end of the chain MOVABLES. */
568: if (movables == 0)
569: movables = m;
570: else
571: last_movable->next = m;
572: last_movable = m;
1.1.1.15 root 573: if (m->consec > 0)
1.1.1.2 root 574: {
1.1.1.15 root 575: /* Skip this insn, not checking REG_LIBCALL notes. */
576: p = NEXT_INSN (p);
577: /* Skip the consecutive insns, if there are any. */
578: p = skip_consec_insns (p, m->consec);
579: /* Back up, so the main loop will advance to the right place. */
580: p = PREV_INSN (p);
1.1.1.2 root 581: }
1.1 root 582: }
1.1.1.2 root 583: /* If this register is always set within a STRICT_LOW_PART
584: or set to zero, then its high bytes are constant.
1.1 root 585: So clear them outside the loop and within the loop
586: just load the low bytes.
587: We must check that the machine has an instruction to do so.
588: Also, if the value loaded into the register
589: depends on the same register, this cannot be done. */
1.1.1.2 root 590: else if (SET_SRC (PATTERN (p)) == const0_rtx
591: && GET_CODE (NEXT_INSN (p)) == INSN
592: && GET_CODE (PATTERN (NEXT_INSN (p))) == SET
593: && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p))))
594: == STRICT_LOW_PART)
595: && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
596: == SUBREG)
597: && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
598: == SET_DEST (PATTERN (p)))
1.1 root 599: && !reg_mentioned_p (SET_DEST (PATTERN (p)),
1.1.1.2 root 600: SET_SRC (PATTERN (NEXT_INSN (p)))))
1.1 root 601: {
602: register int regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.2 root 603: if (n_times_set[regno] == 2)
604: {
605: register struct movable *m;
606: int count;
607: m = (struct movable *) alloca (sizeof (struct movable));
608: m->next = 0;
609: m->insn = p;
610: m->force = 0;
611: m->consec = 0;
612: m->done = 0;
613: m->forces = 0;
614: m->partial = 1;
1.1.1.14 root 615: /* If the insn may not be executed on some cycles,
616: we can't clear the whole reg; clear just high part.
1.1.1.15 root 617: Not even if the reg is used only within this loop.
1.1.1.14 root 618: Consider this:
619: while (1)
1.1.1.15 root 620: while (s != t) {
1.1.1.14 root 621: if (foo ()) x = *s;
622: use (x);
623: }
624: Clearing x before the inner loop could clobber a value
1.1.1.15 root 625: being saved from the last time around the outer loop.
626: However, if the reg is not used outside this loop
627: and all uses of the register are in the same
628: basic block as the store, there is no problem. */
629: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
630: || uid_luid[regno_first_uid[regno]] < INSN_LUID (p)
631: || (labels_in_range_p
632: (p, uid_luid[regno_first_uid[regno]])));
633: if (maybe_never && m->global)
1.1.1.14 root 634: m->savemode = GET_MODE (SET_SRC (PATTERN (NEXT_INSN (p))));
635: else
636: m->savemode = VOIDmode;
1.1.1.2 root 637: m->regno = regno;
638: m->cond = 0;
639: m->match = 0;
640: m->lifetime = (uid_luid[regno_last_uid[regno]]
641: - uid_luid[regno_first_uid[regno]]);
1.1.1.10 root 642: m->savings = 1;
1.1.1.2 root 643: n_times_set[regno] = -1;
644: /* Add M to the end of the chain MOVABLES. */
645: if (movables == 0)
646: movables = m;
647: else
648: last_movable->next = m;
649: last_movable = m;
650: }
1.1 root 651: }
652: }
1.1.1.3 root 653: /* Past a call insn, we get to insns which might not be executed
654: because the call might exit. This matters for insns that trap. */
655: else if (GET_CODE (p) == CALL_INSN)
656: call_passed = 1;
1.1 root 657: /* Past a label or a jump, we get to insns for which we
658: can't count on whether or how many times they will be
659: executed during each iteration. Therefore, we can
660: only move out sets of trivial variables
661: (those not used after the loop). */
1.1.1.15 root 662: else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
663: /* If we enter the loop in the middle, and scan around
664: to the beginning, don't set maybe_never for that. */
665: && ! (NEXT_INSN (p) == end && GET_CODE (p) == JUMP_INSN
666: && simplejump_p (p)))
1.1 root 667: maybe_never = 1;
668: }
669:
1.1.1.15 root 670: /* If one movable subsumes another, ignore that other. */
671:
672: ignore_some_movables (movables);
673:
1.1 root 674: /* For each movable insn, see if the reg that it loads
1.1.1.2 root 675: leads when it dies right into another conditionally movable insn.
676: If so, record that the second insn "forces" the first one,
677: since the second can be moved only if the first is. */
678:
1.1.1.15 root 679: force_movables (movables);
1.1 root 680:
681: /* See if there are multiple movable insns that load the same value.
682: If there are, make all but the first point at the first one
683: through the `match' field, and add the priorities of them
684: all together as the priority of the first. */
1.1.1.2 root 685:
1.1.1.15 root 686: combine_movables (movables, nregs);
1.1.1.2 root 687:
1.1.1.10 root 688: /* Now consider each movable insn to decide whether it is worth moving.
689: Store 0 in n_times_set for each reg that is moved. */
1.1.1.2 root 690:
1.1.1.8 root 691: move_movables (movables, threshold,
1.1.1.2 root 692: insn_count, loop_start, end, nregs);
1.1.1.8 root 693:
1.1.1.10 root 694: /* Now candidates that still have -1 are those not moved.
695: Change n_times_set to indicate that those are not actually invariant. */
696: for (i = 0; i < nregs; i++)
697: if (n_times_set[i] < 0)
698: n_times_set[i] = n_times_used[i];
699:
1.1.1.8 root 700: if (flag_strength_reduce)
701: strength_reduce (scan_start, end, loop_top,
702: insn_count, loop_start, end, nregs);
1.1.1.2 root 703: }
704:
1.1.1.15 root 705: /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
706:
707: static rtx
708: skip_consec_insns (insn, count)
709: rtx insn;
710: int count;
711: {
712: for (; count > 0; count--)
713: {
714: if (GET_CODE (insn) == NOTE)
715: insn = NEXT_INSN (insn);
716: else if (GET_CODE (insn) == BARRIER || GET_CODE (insn) == CODE_LABEL)
717: abort ();
718: else
719: {
720: rtx i1, temp;
721:
722: /* If first insn of gnulib call sequence, skip to end. */
723: /* Do this at start of loop, since INSN is guaranteed to
724: be an insn here. */
725: if (temp = find_reg_note (insn, REG_LIBCALL, 0))
726: insn = XEXP (temp, 0);
727:
728: do insn = NEXT_INSN (insn);
729: while (GET_CODE (insn) == NOTE);
730: }
731: }
732:
733: return insn;
734: }
735:
1.1.1.17! root 736: /* Find a REG_EQUAL note in INSN but only if it is safe to use for our
! 737: purposes. Those put in by CSE are not safe since they may fail to
! 738: use the registers that appear in the actual insn source. */
! 739:
! 740: static rtx
! 741: loop_find_reg_equal (insn)
! 742: rtx insn;
! 743: {
! 744: return (find_reg_note (insn, REG_RETVAL, 0)
! 745: ? find_reg_note (insn, REG_EQUAL, 0)
! 746: : 0);
! 747: }
! 748:
1.1.1.15 root 749: /* Ignore any movable whose insn falls within a libcall
750: which is part of another movable.
751: We make use of the fact that the movable for the libcall value
752: was made later and so appears later on the chain. */
753:
754: static void
755: ignore_some_movables (movables)
756: struct movable *movables;
757: {
758: register struct movable *m, *m1;
759:
760: for (m = movables; m; m = m->next)
761: {
762: /* Is this a movable for the value of a libcall? */
763: rtx note = find_reg_note (m->insn, REG_RETVAL, 0);
764: if (note)
765: {
766: /* Find the beginning of that libcall. */
767: rtx first_insn = XEXP (note, 0);
768: /* Check for earlier movables inside that range,
769: and mark them invalid. */
770: for (m1 = movables; m1 != m; m1 = m1->next)
771: if (INSN_LUID (m1->insn) >= INSN_LUID (first_insn)
772: && INSN_LUID (m1->insn) < INSN_LUID (m->insn))
773: m1->done = 1;
774: }
775: }
776: }
777:
778: /* For each movable insn, see if the reg that it loads
779: leads when it dies right into another conditionally movable insn.
780: If so, record that the second insn "forces" the first one,
781: since the second can be moved only if the first is. */
782:
783: static void
784: force_movables (movables)
785: struct movable *movables;
786: {
787: register struct movable *m, *m1;
788: for (m1 = movables; m1; m1 = m1->next)
789: /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
790: if (!m1->partial && !m1->done)
791: {
792: int regno = m1->regno;
793: for (m = m1->next; m; m = m->next)
794: /* ??? Could this be a bug? What if CSE caused the
795: register of M1 to be used after this insn?
796: Since CSE does not update regno_last_uid,
797: this insn M->insn might not be where it dies.
798: But very likely this doesn't matter; what matters is
799: that M's reg is computed from M1's reg. */
800: if (INSN_UID (m->insn) == regno_last_uid[regno]
801: && !m->done)
802: break;
803: if (m != 0 && m->set_src == SET_DEST (PATTERN (m1->insn)))
804: m = 0;
805:
806: /* Increase the priority of the moving the first insn
807: since it permits the second to be moved as well. */
808: if (m != 0)
809: {
810: m->forces = m1;
811: m1->lifetime += m->lifetime;
812: m1->savings += m1->savings;
813: }
814: }
815: }
816:
817: /* Find invariant expressions that are equal and can be combined into
818: one register. */
819:
820: static void
821: combine_movables (movables, nregs)
822: struct movable *movables;
823: int nregs;
824: {
825: register struct movable *m;
826: char *matched_regs = (char *) alloca (nregs);
827: enum machine_mode mode;
828:
829: /* Regs that are set more than once are not allowed to match
830: or be matched. I'm no longer sure why not. */
831: /* Perhaps testing m->consec_sets would be more appropriate here? */
832:
833: for (m = movables; m; m = m->next)
834: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial)
835: {
836: register struct movable *m1;
837: int regno = m->regno;
838:
839: bzero (matched_regs, nregs);
840: matched_regs[regno] = 1;
841:
842: for (m1 = m->next; m1; m1 = m1->next)
843: if (m1->match == 0 && n_times_used[m1->regno] == 1
844: /* A reg used outside the loop mustn't be eliminated. */
845: && !m1->global
846: /* A reg used for zero-extending mustn't be eliminated. */
847: && !m1->partial
848: && (matched_regs[m1->regno]
849: ||
850: (
851: /* Can't combine regs with different modes
852: even if loaded from the same constant. */
853: (GET_MODE (SET_DEST (PATTERN (m->insn)))
854: == GET_MODE (SET_DEST (PATTERN (m1->insn))))
855: /* See if the source of M1 says it matches M. */
856: && ((GET_CODE (m1->set_src) == REG
857: && matched_regs[REGNO (m1->set_src)])
858: || rtx_equal_for_loop_p (m->set_src, m1->set_src,
859: movables)
860: || (REG_NOTES (m->insn) && REG_NOTES (m1->insn)
861: && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV
862: && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV
863: && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0),
864: XEXP (REG_NOTES (m1->insn), 0)))))))
865: {
866: m->lifetime += m1->lifetime;
867: m->savings += m1->savings;
868: m1->match = m;
869: matched_regs[m1->regno] = 1;
870: }
871: }
872:
873: /* Now combine the regs used for zero-extension.
874: This can be done for those not marked `global'
875: provided their lives don't overlap. */
876:
877: for (mode = VOIDmode; (int) mode < (int) MAX_MACHINE_MODE;
878: mode = (enum machine_mode) ((int) mode + 1))
879: if (GET_MODE_CLASS (mode) == MODE_INT)
880: {
881: register struct movable *m0 = 0;
882:
883: /* Combine all the registers for extension from mode MODE.
884: Don't combine any that are used outside this loop. */
885: for (m = movables; m; m = m->next)
886: if (m->partial && ! m->global
887: && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
888: {
889: register struct movable *m1;
890: int first = uid_luid[regno_first_uid[m->regno]];
891: int last = uid_luid[regno_last_uid[m->regno]];
892:
893: if (m0 == 0)
894: {
895: /* First one: don't check for overlap, just record it. */
896: m0 = m;
897: continue;
898: }
899:
900: /* Make sure they extend to the same mode.
901: (Almost always true.) */
902: if (GET_MODE (SET_DEST (PATTERN (m->insn)))
903: != GET_MODE (SET_DEST (PATTERN (m0->insn))))
904: continue;
905:
906: /* We already have one: check for overlap with those
907: already combined together. */
908: for (m1 = movables; m1 != m; m1 = m1->next)
909: if (m1 == m0 || (m1->partial && m1->match == m0))
910: if (! (uid_luid[regno_first_uid[m1->regno]] > last
911: || uid_luid[regno_last_uid[m1->regno]] < first))
912: goto overlap;
913:
914: /* No overlap: we can combine this with the others. */
915: m0->lifetime += m->lifetime;
916: m0->savings += m->savings;
917: m->match = m0;
918:
919: overlap: ;
920: }
921: }
922: }
923:
924: /* Return 1 if regs X and Y will become the same if moved. */
925:
926: static int
927: regs_match_p (x, y, movables)
928: rtx x, y;
929: struct movable *movables;
930: {
931: int xn = REGNO (x);
932: int yn = REGNO (y);
933: struct movable *mx, *my;
934:
935: for (mx = movables; mx; mx = mx->next)
936: if (mx->regno == xn)
937: break;
938:
939: for (my = movables; my; my = my->next)
940: if (my->regno == yn)
941: break;
942:
943: return (mx && my
944: && ((mx->match == my->match && mx->match != 0)
945: || mx->match == my
946: || mx == my->match));
947: }
948:
949: /* Return 1 if X and Y are identical-looking rtx's.
950: This is the Lisp function EQUAL for rtx arguments. */
951:
952: static int
953: rtx_equal_for_loop_p (x, y, movables)
954: rtx x, y;
955: struct movable *movables;
956: {
957: register int i;
958: register int j;
959: register enum rtx_code code;
960: register char *fmt;
961:
962: if (x == y)
963: return 1;
964: if (x == 0 || y == 0)
965: return 0;
966:
967: code = GET_CODE (x);
968: /* Rtx's of different codes cannot be equal. */
969: if (code != GET_CODE (y))
970: return 0;
971:
972: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
973: (REG:SI x) and (REG:HI x) are NOT equivalent. */
974:
975: if (GET_MODE (x) != GET_MODE (y))
976: return 0;
977:
978: /* These three types of rtx's can be compared nonrecursively. */
979: /* Until the end of reload,
980: don't consider the a reference to the return register of the current
981: function the same as the return from a called function. This eases
982: the job of function integration. Once the distinction no longer
983: matters, the insn will be deleted. */
984: if (code == REG)
985: return ((REGNO (x) == REGNO (y)
986: && REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y))
987: || regs_match_p (x, y, movables));
988:
989: if (code == LABEL_REF)
990: return XEXP (x, 0) == XEXP (y, 0);
991: if (code == SYMBOL_REF)
992: return XSTR (x, 0) == XSTR (y, 0);
993:
994: /* Compare the elements. If any pair of corresponding elements
995: fail to match, return 0 for the whole things. */
996:
997: fmt = GET_RTX_FORMAT (code);
998: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
999: {
1000: switch (fmt[i])
1001: {
1002: case 'i':
1003: if (XINT (x, i) != XINT (y, i))
1004: return 0;
1005: break;
1006:
1007: case 'E':
1008: /* Two vectors must have the same length. */
1009: if (XVECLEN (x, i) != XVECLEN (y, i))
1010: return 0;
1011:
1012: /* And the corresponding elements must match. */
1013: for (j = 0; j < XVECLEN (x, i); j++)
1014: if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0)
1015: return 0;
1016: break;
1017:
1018: case 'e':
1019: if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0)
1020: return 0;
1021: break;
1022:
1023: case 's':
1024: if (strcmp (XSTR (x, i), XSTR (y, i)))
1025: return 0;
1026: break;
1027:
1028: case 'u':
1029: /* These are just backpointers, so they don't matter. */
1030: break;
1031:
1032: case '0':
1033: break;
1034:
1035: /* It is believed that rtx's at this level will never
1036: contain anything but integers and other rtx's,
1037: except for within LABEL_REFs and SYMBOL_REFs. */
1038: default:
1039: abort ();
1040: }
1041: }
1042: return 1;
1043: }
1044:
1.1.1.2 root 1045: /* Scan MOVABLES, and move the insns that deserve to be moved.
1046: If two matching movables are combined, replace one reg with the
1047: other throughout. */
1048:
1049: static void
1.1.1.8 root 1050: move_movables (movables, threshold, insn_count, loop_start, end, nregs)
1.1.1.2 root 1051: struct movable *movables;
1052: int threshold;
1053: int insn_count;
1054: rtx loop_start;
1055: rtx end;
1056: int nregs;
1057: {
1058: rtx new_start = 0;
1059: register struct movable *m;
1060: register rtx p;
1061: /* Map of pseudo-register replacements to handle combining
1062: when we move several insns that load the same value
1063: into different pseudo-registers. */
1064: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
1065: char *already_moved = (char *) alloca (nregs);
1066:
1067: bzero (already_moved, nregs);
1068: bzero (reg_map, nregs * sizeof (rtx));
1069:
1.1.1.8 root 1070: num_movables = 0;
1071:
1.1.1.2 root 1072: for (m = movables; m; m = m->next)
1073: {
1074: /* Describe this movable insn. */
1075:
1076: if (loop_dump_stream)
1077: {
1078: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1079: INSN_UID (m->insn), m->regno, m->lifetime);
1080: if (m->consec > 0)
1081: fprintf (loop_dump_stream, "consec %d, ", m->consec);
1082: if (m->cond)
1083: fprintf (loop_dump_stream, "cond ");
1084: if (m->force)
1085: fprintf (loop_dump_stream, "force ");
1086: if (m->global)
1087: fprintf (loop_dump_stream, "global ");
1088: if (m->done)
1089: fprintf (loop_dump_stream, "done ");
1090: if (m->match)
1091: fprintf (loop_dump_stream, "matches %d ",
1092: INSN_UID (m->match->insn));
1093: if (m->forces)
1094: fprintf (loop_dump_stream, "forces %d ",
1095: INSN_UID (m->forces->insn));
1096: }
1097:
1.1.1.8 root 1098: /* Count movables. Value used in heuristics in strength_reduce. */
1099: num_movables++;
1100:
1.1.1.2 root 1101: /* Ignore the insn if it's already done (it matched something else).
1102: Otherwise, see if it is now safe to move. */
1103:
1104: if (!m->done
1105: && (! m->cond
1.1.1.8 root 1106: || (1 == invariant_p (m->set_src)
1.1.1.4 root 1107: && (m->consec == 0
1108: || 1 == consec_sets_invariant_p (SET_DEST (PATTERN (m->insn)),
1109: m->consec + 1,
1.1.1.8 root 1110: m->insn))))
1.1.1.2 root 1111: && (! m->forces || m->forces->done))
1112: {
1113: register int regno;
1114: register rtx p;
1.1.1.10 root 1115: int savings = m->savings;
1.1.1.2 root 1116:
1117: /* We have an insn that is safe to move.
1118: Compute its desirability. */
1119:
1120: p = m->insn;
1121: regno = m->regno;
1122:
1123: if (loop_dump_stream)
1.1.1.10 root 1124: fprintf (loop_dump_stream, "savings %d ", savings);
1.1.1.2 root 1125:
1.1.1.12 root 1126: if (moved_once[regno])
1127: {
1128: insn_count *= 2;
1129:
1130: if (loop_dump_stream)
1131: fprintf (loop_dump_stream, "halved since already moved ");
1132: }
1133:
1.1.1.2 root 1134: /* An insn MUST be moved if we already moved something else
1135: which is safe only if this one is moved too: that is,
1136: if already_moved[REGNO] is nonzero. */
1137:
1138: /* An insn is desirable to move if the new lifetime of the
1139: register is no more than THRESHOLD times the old lifetime.
1140: If it's not desirable, it means the loop is so big
1141: that moving won't speed things up much,
1142: and it is liable to make register usage worse. */
1143:
1144: /* It is also desirable to move if it can be moved at no
1145: extra cost because something else was already moved. */
1146:
1147: if (already_moved[regno]
1.1.1.10 root 1148: || (threshold * savings * m->lifetime) >= insn_count
1.1.1.2 root 1149: || (m->forces && m->forces->done
1150: && n_times_used[m->forces->regno] == 1))
1.1 root 1151: {
1.1.1.2 root 1152: int count;
1153: register struct movable *m1;
1.1.1.8 root 1154: rtx first;
1.1.1.2 root 1155:
1.1.1.14 root 1156: /* Now move the insns that set the reg. */
1157:
1.1.1.2 root 1158: for (count = m->consec; count >= 0; count--)
1.1 root 1159: {
1.1.1.8 root 1160: rtx i1, temp;
1161:
1162: /* If first insn of gnulib call sequence, skip to end. */
1163: /* Do this at start of loop, since p is guaranteed to
1164: be an insn here. */
1165: if (temp = find_reg_note (p, REG_LIBCALL, 0))
1166: p = XEXP (temp, 0);
1167:
1168: /* If last insn of gnulib call sequence, move all
1169: insns except the last before the loop. The last insn is
1170: handled in the normal manner. */
1.1.1.15 root 1171: if (temp = find_reg_note (p, REG_RETVAL
1172: , 0))
1.1.1.8 root 1173: {
1.1.1.9 root 1174: rtx fn_address = 0;
1175: rtx fn_reg = 0;
1.1.1.8 root 1176: first = 0;
1177: for (temp = XEXP (temp, 0); temp != p;
1178: temp = NEXT_INSN (temp))
1179: {
1.1.1.9 root 1180: rtx body = PATTERN (temp);
1181: rtx n;
1182: /* Extract the function address from the insn
1183: that loads it into a register.
1184: If this insn was cse'd, we get incorrect code.
1185: So delete it and stick the fn address right
1186: into the call insn. Since the moved insns
1187: won't be cse'd, that does no harm. */
1188: if (GET_CODE (NEXT_INSN (temp)) == CALL_INSN
1189: && GET_CODE (body) == SET
1190: && GET_CODE (SET_DEST (body)) == REG
1191: && (n = find_reg_note (temp, REG_EQUIV, 0)))
1192: {
1193: fn_reg = SET_SRC (body);
1194: if (GET_CODE (fn_reg) != REG)
1195: fn_reg = SET_DEST (body);
1196: fn_address = XEXP (n, 0);
1197: continue;
1198: }
1199: /* We have the call insn.
1200: Substitute the fn address for the reg
1201: that we believe this insn will use. */
1202: if (GET_CODE (temp) == CALL_INSN
1203: && fn_address != 0)
1204: replace_call_address (body, fn_reg, fn_address);
1.1.1.10 root 1205: if (GET_CODE (temp) == CALL_INSN)
1206: i1 = emit_call_insn_before (body, loop_start);
1207: else
1208: i1 = emit_insn_before (body, loop_start);
1.1.1.8 root 1209: if (first == 0)
1210: first = i1;
1211: REG_NOTES (i1) = REG_NOTES (temp);
1212: delete_insn (temp);
1213: }
1214: }
1.1.1.14 root 1215: if (m->savemode != VOIDmode)
1216: {
1217: /* P sets REG to zero; but we should clear only the bits
1218: that are not covered by the mode m->savemode. */
1219: rtx reg = SET_DEST (PATTERN (p));
1220: i1 = emit_insn_before
1221: (gen_rtx (SET, VOIDmode, reg,
1222: gen_rtx (AND, GET_MODE (reg),
1223: reg,
1224: gen_rtx (CONST_INT, VOIDmode,
1225: (1 << GET_MODE_BITSIZE (m->savemode)) - 1))),
1226: loop_start);
1227: }
1228: else if (GET_CODE (PATTERN (p)) == CALL_INSN)
1.1.1.10 root 1229: i1 = emit_call_insn_before (PATTERN (p), loop_start);
1230: else
1231: i1 = emit_insn_before (PATTERN (p), loop_start);
1.1.1.8 root 1232:
1.1.1.2 root 1233: if (new_start == 0)
1234: new_start = i1;
1235:
1236: if (loop_dump_stream)
1.1.1.15 root 1237: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1.1.1.2 root 1238:
1239: /* Mark the moved, invariant reg as being equivalent to
1240: its constant value. */
1241: REG_NOTES (i1) = REG_NOTES (p);
1242: if (REG_NOTES (i1) == 0
1.1.1.8 root 1243: && ! m->partial /* But not if it's a zero-extend clr. */
1.1.1.2 root 1244: && ! m->global /* and not if used outside the loop
1245: (since it might get set outside). */
1246: && CONSTANT_P (SET_SRC (PATTERN (p))))
1247: REG_NOTES (i1)
1248: = gen_rtx (EXPR_LIST, REG_EQUIV,
1249: SET_SRC (PATTERN (p)), REG_NOTES (i1));
1.1.1.8 root 1250:
1251: /* If library call, now fix the REG_NOTES that contain
1252: insn pointers, namely REG_LIBCALL on FIRST
1253: and REG_RETVAL on I1. */
1254: if (temp = find_reg_note (i1, REG_RETVAL, 0))
1255: {
1256: XEXP (temp, 0) = first;
1257: temp = find_reg_note (first, REG_LIBCALL, 0);
1258: XEXP (temp, 0) = i1;
1259: }
1260:
1.1.1.2 root 1261: delete_insn (p);
1262: do p = NEXT_INSN (p);
1.1.1.17! root 1263: while (p != 0 && GET_CODE (p) == NOTE);
1.1 root 1264: }
1.1.1.2 root 1265:
1.1.1.10 root 1266: /* The more regs we move, the less we like moving them. */
1267: threshold -= 3;
1268:
1.1.1.2 root 1269: /* Any other movable that loads the same register
1270: MUST be moved. */
1271: already_moved[regno] = 1;
1272:
1.1.1.12 root 1273: /* This reg has been moved out of one loop. */
1274: moved_once[regno] = 1;
1275:
1.1.1.2 root 1276: /* The reg set here is now invariant. */
1277: if (! m->partial)
1278: n_times_set[regno] = 0;
1279:
1280: m->done = 1;
1281:
1.1.1.10 root 1282: /* Change the length-of-life info for the register
1283: to say it lives at least the full length of this loop.
1284: This will help guide optimizations in outer loops. */
1285:
1286: if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start))
1287: /* This is the old insn before all the moved insns.
1288: We can't use the moved insn because it is out of range
1289: in uid_luid. Only the old insns have luids. */
1290: regno_first_uid[regno] = INSN_UID (loop_start);
1291: if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end))
1292: regno_last_uid[regno] = INSN_UID (end);
1293:
1.1.1.2 root 1294: /* Combine with this moved insn any other matching movables. */
1.1 root 1295:
1296: for (m1 = m->next; m1; m1 = m1->next)
1297: if (m1->match == m)
1298: {
1.1.1.8 root 1299: rtx temp;
1300:
1.1 root 1301: /* Schedule the reg loaded by M1
1302: for replacement so that shares the reg of M. */
1303: reg_map[m1->regno] = SET_DEST (PATTERN (m->insn));
1.1.1.2 root 1304: /* Get rid of the matching insn
1.1 root 1305: and prevent further processing of it. */
1.1.1.2 root 1306: m1->done = 1;
1.1.1.8 root 1307:
1308: /* if library call, delete all insn except last, which
1309: is deleted below */
1310: if (temp = find_reg_note (m1->insn, REG_RETVAL, 0))
1311: {
1312: for (temp = XEXP (temp, 0); temp != m1->insn;
1313: temp = NEXT_INSN (temp))
1314: delete_insn (temp);
1315: }
1.1 root 1316: delete_insn (m1->insn);
1.1.1.2 root 1317:
1318: /* Any other movable that loads the same register
1319: MUST be moved. */
1320: already_moved[m1->regno] = 1;
1321:
1.1.1.13 root 1322: /* The reg merged here is now invariant,
1323: if the reg it matches is invariant. */
1324: if (! m->partial)
1.1.1.2 root 1325: n_times_set[m1->regno] = 0;
1.1 root 1326: }
1327: }
1.1.1.2 root 1328: else if (loop_dump_stream)
1329: fprintf (loop_dump_stream, "not desirable");
1.1 root 1330: }
1.1.1.2 root 1331: else if (loop_dump_stream && !m->match)
1332: fprintf (loop_dump_stream, "not safe");
1.1 root 1333:
1.1.1.2 root 1334: if (loop_dump_stream)
1335: fprintf (loop_dump_stream, "\n");
1336: }
1.1 root 1337:
1.1.1.2 root 1338: if (new_start == 0)
1339: new_start = loop_start;
1.1 root 1340:
1.1.1.2 root 1341: /* Go through all the instructions in the loop, making
1342: all the register substitutions scheduled in REG_MAP. */
1343: for (p = new_start; p != end; p = NEXT_INSN (p))
1344: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1345: || GET_CODE (p) == CALL_INSN)
1.1.1.8 root 1346: replace_regs (PATTERN (p), reg_map, nregs);
1.1.1.2 root 1347: }
1348:
1349: /* Optionally change a loop which enters just before the endtest
1350: to one which falls straight in
1351: after skipping around the entire loop if the endtest would drop out.
1352: Returns 1 if the change was made, 0 if the loop was not really suitable. */
1353:
1354: int
1355: loop_skip_over (start, end, loop_entry_jump)
1356: rtx start;
1357: rtx end;
1358: rtx loop_entry_jump;
1359: {
1.1.1.16 root 1360: rtx entry_insn;
1361: rtx endtest;
1.1.1.2 root 1362: rtx endtestjump;
1363: register rtx p = JUMP_LABEL (loop_entry_jump);
1.1 root 1364:
1.1.1.2 root 1365: while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN
1366: && GET_CODE (p) != CALL_INSN)
1367: p = NEXT_INSN (p);
1.1.1.16 root 1368: entry_insn = p;
1369:
1370: /* Skip any ordinary arithmetic insns to find the compare. */
1371: for (; p != 0; p = NEXT_INSN (p))
1372: if (GET_CODE (p) != NOTE)
1373: if (GET_CODE (p) != INSN || sets_cc0_p (PATTERN (p)))
1374: break;
1375: if (p == 0 || GET_CODE (p) != INSN)
1376: return 0;
1377: endtest = p;
1.1.1.2 root 1378: endtestjump = next_real_insn (p);
1379:
1.1.1.16 root 1380: /* Check that (1) we have reached a compare insn and (2)
1.1.1.2 root 1381: the insn (presumably a jump) following that compare
1382: is the last in the loop and jumps back to the loop beginning. */
1383:
1.1.1.16 root 1384: if (sets_cc0_p (PATTERN (endtest)) > 0
1.1.1.2 root 1385: && endtestjump == prev_real_insn (end)
1386: && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump)
1.1 root 1387: {
1.1.1.2 root 1388: rtx newlab;
1389: /* This is the jump that we insert. */
1390: rtx new_jump;
1391:
1.1.1.16 root 1392: /* Duplicate the ordinary arith insns before the compare. */
1393: for (p = entry_insn; p != endtest; p = NEXT_INSN (p))
1394: if (GET_CODE (p) == INSN)
1395: {
1396: rtx new = emit_insn_before (copy_rtx (PATTERN (p)), start);
1397: if (REG_NOTES (p))
1398: REG_NOTES (new) = copy_rtx (REG_NOTES (p));
1399: }
1400:
1.1.1.2 root 1401: /* Ok, duplicate that test before start of loop. */
1.1.1.16 root 1402: emit_insn_before (copy_rtx (PATTERN (endtest)), start);
1.1.1.2 root 1403: /* Make a new entry-jump (before the original one)
1404: whose condition is opposite to the loop-around endtest
1.1.1.8 root 1405: and which jumps around the loop (to just after the ending NOTE). */
1.1.1.2 root 1406: newlab = gen_label_rtx ();
1.1.1.8 root 1407: emit_label_after (newlab, end);
1.1.1.2 root 1408: emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start);
1409: new_jump = PREV_INSN (start);
1410: JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump);
1411: LABEL_NUSES (JUMP_LABEL (endtestjump))++;
1412: invert_jump (new_jump, newlab);
1413: /* Delete the original entry-jump. */
1414: delete_insn (loop_entry_jump);
1.1 root 1415:
1.1.1.2 root 1416: return 1;
1.1 root 1417: }
1.1.1.2 root 1418:
1419: return 0;
1.1 root 1420: }
1421:
1422: /* Throughout the rtx X, replace many registers according to REG_MAP.
1423: Return the replacement for X (which may be X with altered contents).
1.1.1.8 root 1424: REG_MAP[R] is the replacement for register R, or 0 for don't replace.
1425: NREGS is the length of REG_MAP; regs >= NREGS are not mapped. */
1.1 root 1426:
1427: static rtx
1.1.1.8 root 1428: replace_regs (x, reg_map, nregs)
1.1 root 1429: rtx x;
1430: rtx *reg_map;
1.1.1.8 root 1431: int nregs;
1.1 root 1432: {
1.1.1.12 root 1433: register enum rtx_code code;
1.1 root 1434: register int i;
1435: register char *fmt;
1436:
1.1.1.12 root 1437: if (x == 0)
1438: return x;
1439:
1440: code = GET_CODE (x);
1.1 root 1441: switch (code)
1442: {
1443: case PC:
1444: case CC0:
1445: case CONST_INT:
1446: case CONST_DOUBLE:
1447: case CONST:
1448: case SYMBOL_REF:
1449: case LABEL_REF:
1450: return x;
1451:
1452: case REG:
1.1.1.8 root 1453: /* Verify that the register has an entry before trying to access it. */
1454: if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
1.1 root 1455: return reg_map[REGNO (x)];
1456: return x;
1457: }
1458:
1459: fmt = GET_RTX_FORMAT (code);
1460: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1461: {
1462: if (fmt[i] == 'e')
1.1.1.8 root 1463: XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs);
1.1 root 1464: if (fmt[i] == 'E')
1465: {
1466: register int j;
1467: for (j = 0; j < XVECLEN (x, i); j++)
1.1.1.8 root 1468: XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map, nregs);
1.1 root 1469: }
1470: }
1471: return x;
1472: }
1473:
1.1.1.9 root 1474: /* Scan X and replace the address of any MEM in it with ADDR.
1475: REG is the address that MEM should have before the replacement. */
1476:
1477: static void
1478: replace_call_address (x, reg, addr)
1479: rtx x, reg, addr;
1480: {
1.1.1.12 root 1481: register enum rtx_code code;
1.1.1.9 root 1482: register int i;
1483: register char *fmt;
1484:
1.1.1.12 root 1485: if (x == 0)
1486: return;
1487: code = GET_CODE (x);
1.1.1.9 root 1488: switch (code)
1489: {
1490: case PC:
1491: case CC0:
1492: case CONST_INT:
1493: case CONST_DOUBLE:
1494: case CONST:
1495: case SYMBOL_REF:
1496: case LABEL_REF:
1497: case REG:
1498: return;
1499:
1500: case SET:
1501: /* Short cut for very common case. */
1502: replace_call_address (XEXP (x, 1), reg, addr);
1503: return;
1504:
1505: case CALL:
1506: /* Short cut for very common case. */
1507: replace_call_address (XEXP (x, 0), reg, addr);
1508: return;
1509:
1510: case MEM:
1511: /* If this MEM uses a reg other than the one we expected,
1512: something is wrong. */
1513: if (XEXP (x, 0) != reg)
1514: abort ();
1515: XEXP (x, 0) = addr;
1516: return;
1517: }
1518:
1519: fmt = GET_RTX_FORMAT (code);
1520: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1521: {
1522: if (fmt[i] == 'e')
1523: replace_call_address (XEXP (x, i), reg, addr);
1524: if (fmt[i] == 'E')
1525: {
1526: register int j;
1527: for (j = 0; j < XVECLEN (x, i); j++)
1528: replace_call_address (XVECEXP (x, i, j), reg, addr);
1529: }
1530: }
1531: }
1532:
1.1.1.15 root 1533: /* Return the number of memory refs to addresses that vary
1534: in the rtx X. */
1535:
1536: static int
1537: count_nonfixed_reads (x)
1538: rtx x;
1539: {
1540: register enum rtx_code code;
1541: register int i;
1542: register char *fmt;
1543: int value;
1544:
1545: if (x == 0)
1546: return 0;
1547:
1548: code = GET_CODE (x);
1549: switch (code)
1550: {
1551: case PC:
1552: case CC0:
1553: case CONST_INT:
1554: case CONST_DOUBLE:
1555: case CONST:
1556: case SYMBOL_REF:
1557: case LABEL_REF:
1558: case REG:
1559: return 0;
1560:
1561: case MEM:
1562: return rtx_varies_p (XEXP (x, 0)) + count_nonfixed_reads (XEXP (x, 0));
1563: }
1564:
1565: value = 0;
1566: fmt = GET_RTX_FORMAT (code);
1567: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1568: {
1569: if (fmt[i] == 'e')
1570: value += count_nonfixed_reads (XEXP (x, i));
1571: if (fmt[i] == 'E')
1572: {
1573: register int j;
1574: for (j = 0; j < XVECLEN (x, i); j++)
1575: value += count_nonfixed_reads (XVECEXP (x, i, j));
1576: }
1577: }
1578: return value;
1579: }
1580:
1581:
1.1.1.4 root 1582: #if 0
1.1 root 1583: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
1584: Replace it with an instruction to load just the low bytes
1585: if the machine supports such an instruction,
1586: and insert above LOOP_START an instruction to clear the register. */
1587:
1588: static void
1589: constant_high_bytes (p, loop_start)
1590: rtx p, loop_start;
1591: {
1592: register rtx new;
1593: register int insn_code_number;
1594:
1595: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
1596: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
1597:
1598: new = gen_rtx (SET, VOIDmode,
1599: gen_rtx (STRICT_LOW_PART, VOIDmode,
1600: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
1601: SET_DEST (PATTERN (p)),
1602: 0)),
1603: XEXP (SET_SRC (PATTERN (p)), 0));
1604: insn_code_number = recog (new, p);
1605:
1606: if (insn_code_number)
1607: {
1608: register int i;
1609:
1610: /* Clear destination register before the loop. */
1611: emit_insn_before (gen_rtx (SET, VOIDmode,
1612: SET_DEST (PATTERN (p)),
1613: const0_rtx),
1614: loop_start);
1615:
1616: /* Inside the loop, just load the low part. */
1617: PATTERN (p) = new;
1618: }
1619: }
1.1.1.4 root 1620: #endif
1.1 root 1621:
1622: /* Verify that the ostensible loop starting at START
1623: really is a loop: nothing jumps into it from outside.
1624: Return the marker for the end of the loop, or zero if not a real loop.
1625:
1626: Also set the variables `unknown_*_altered' and `loop_has_call',
1627: and fill in the array `loop_store_addrs'. */
1628:
1629: static rtx
1630: verify_loop (f, start)
1631: rtx f, start;
1632: {
1633: register int level = 1;
1634: register rtx insn, end;
1635:
1636: /* First find the LOOP_END that matches.
1637: Also check each insn for storing in memory and record where. */
1638:
1639: unknown_address_altered = 0;
1640: unknown_aggregate_altered = 0;
1641: fixed_aggregate_altered = 0;
1642: loop_has_call = 0;
1643: loop_store_addrs_idx = 0;
1644:
1.1.1.8 root 1645: num_mem_sets = 0;
1646: loops_enclosed = 1;
1.1.1.14 root 1647: loop_continue = 0;
1.1.1.8 root 1648:
1.1 root 1649: for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn))
1650: {
1651: if (insn == 0)
1.1.1.2 root 1652: /* Parse errors can cause a loop-beg with no loop-end. */
1653: return 0;
1.1 root 1654: if (GET_CODE (insn) == NOTE)
1655: {
1656: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1.1.1.8 root 1657: {
1658: ++level;
1659: /* Count number of loops contained in this one. */
1660: loops_enclosed++;
1661: }
1.1 root 1662: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1.1.1.2 root 1663: {
1664: --level;
1665: if (level == 0)
1666: {
1667: end = insn;
1668: break;
1669: }
1670: }
1.1.1.14 root 1671: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
1672: {
1673: if (level == 1)
1674: loop_continue = insn;
1675: }
1676:
1.1.1.11 root 1677: /* Don't optimize loops containing setjmps.
1678: On some machines, longjmp does not restore the reg
1679: values as of the time of the setjmp. */
1680: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1681: return 0;
1.1 root 1682: }
1683: else if (GET_CODE (insn) == CALL_INSN)
1684: {
1685: unknown_address_altered = 1;
1686: loop_has_call = 1;
1687: }
1.1.1.8 root 1688: /* ???
1689: else if (! unknown_address_altered) */
1690: else
1.1 root 1691: {
1692: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1693: note_stores (PATTERN (insn), note_addr_stored);
1694: }
1695: }
1696:
1697: /* Now scan all jumps in the function and see if any of them can
1698: reach a label within the range of the loop. */
1699:
1700: for (insn = f; insn; insn = NEXT_INSN (insn))
1701: if (GET_CODE (insn) == JUMP_INSN
1702: /* Don't get fooled by jumps inserted by loop-optimize.
1703: They don't have valid LUIDs, and they never jump into loops. */
1704: && INSN_UID (insn) < max_uid
1705: && (INSN_LUID (insn) < INSN_LUID (start)
1706: || INSN_LUID (insn) > INSN_LUID (end))
1707: /* We have a jump that is outside the loop.
1708: Does it jump into the loop? */
1709: && can_jump_into_range_p (PATTERN (insn),
1710: INSN_LUID (start), INSN_LUID (end)))
1711: return 0;
1712:
1713: #if 0
1714: /* Now scan all labels between them and check for any jumps from outside.
1715: This uses the ref-chains set up by find_basic_blocks.
1716: This code is not used because it's more convenient for other reasons
1717: to do the loop optimization before find_basic_blocks. */
1718:
1719: for (insn = start; insn != end; insn = NEXT_INSN (insn))
1720: if (GET_CODE (insn) == CODE_LABEL)
1721: {
1722: register rtx y;
1723: for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y))
1724: if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start)
1725: || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end))
1726: return 0;
1727: }
1728: #endif
1729:
1730: return end;
1731: }
1732:
1733: /* Return 1 if somewhere in X is a LABEL_REF to a label
1734: located between BEG and END. */
1735:
1736: static int
1737: can_jump_into_range_p (x, beg, end)
1738: rtx x;
1739: int beg, end;
1740: {
1.1.1.12 root 1741: register enum rtx_code code = GET_CODE (x);
1.1 root 1742: register int i;
1743: register char *fmt;
1744:
1745: if (code == LABEL_REF)
1746: {
1747: register int luid = INSN_LUID (XEXP (x, 0));
1748: return luid > beg && luid < end;
1749: }
1750:
1751: fmt = GET_RTX_FORMAT (code);
1752: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1753: {
1754: if (fmt[i] == 'e')
1755: {
1756: if (can_jump_into_range_p (XEXP (x, i), beg, end))
1757: return 1;
1758: }
1759: else if (fmt[i] == 'E')
1760: {
1761: register int j;
1762: for (j = 0; j < XVECLEN (x, i); j++)
1763: if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end))
1764: return 1;
1765: }
1766: }
1767:
1768: return 0;
1769: }
1770:
1.1.1.15 root 1771: /* Return nonzero if there is a label in the range from
1772: insn INSN to the insn whose luid is END. */
1773:
1774: static int
1775: labels_in_range_p (insn, end)
1776: rtx insn;
1777: int end;
1778: {
1779: while (insn && INSN_LUID (insn) <= end)
1780: {
1781: if (GET_CODE (insn) == CODE_LABEL)
1782: return 0;
1783: insn = NEXT_INSN (insn);
1784: }
1785:
1786: return 0;
1787: }
1788:
1.1 root 1789: /* Record that a memory reference X is being set. */
1790:
1791: static void
1792: note_addr_stored (x)
1793: rtx x;
1794: {
1795: if (x == 0 || GET_CODE (x) != MEM)
1796: return;
1.1.1.8 root 1797:
1798: /* Count number of memory writes.
1799: This affects heuristics in strength_reduce. */
1800: num_mem_sets++;
1801: if (unknown_address_altered)
1802: return;
1803:
1.1.1.2 root 1804: if (GET_MODE (x) == BLKmode)
1805: unknown_address_altered = 1;
1806: else if (rtx_addr_varies_p (x))
1.1 root 1807: {
1808: if (GET_CODE (XEXP (x, 0)) == PLUS)
1809: unknown_aggregate_altered = 1;
1810: else
1811: unknown_address_altered = 1;
1812: }
1813: else
1814: {
1815: register int i;
1816: register rtx addr = XEXP (x, 0);
1817:
1.1.1.8 root 1818: if (MEM_IN_STRUCT_P (x))
1.1 root 1819: fixed_aggregate_altered = 1;
1820: for (i = 0; i < loop_store_addrs_idx; i++)
1821: if (rtx_equal_p (loop_store_addrs[i], addr))
1822: {
1823: if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x)))
1824: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
1825: break;
1826: }
1827: if (i == NUM_STORES)
1828: unknown_address_altered = 1;
1829: else if (i == loop_store_addrs_idx)
1830: {
1.1.1.2 root 1831: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
1.1 root 1832: loop_store_addrs[loop_store_addrs_idx++] = addr;
1833: }
1834: }
1835: }
1836:
1837: /* Return nonzero if the rtx X is invariant over the current loop.
1838:
1839: The value is 2 if we refer to something only conditionally invariant.
1840:
1841: If `unknown_address_altered' is nonzero, no memory ref is invariant.
1842: Otherwise if `unknown_aggregate_altered' is nonzero,
1843: a memory ref is invariant if it is not part of an aggregate
1844: and its address is fixed and not in `loop_store_addrs'.
1845: Otherwise if `fixed_aggregate_altered' is nonzero,
1846: a memory ref is invariant
1847: if its address is fixed and not in `loop_store_addrs'.
1848: Otherwise, a memory ref is invariant if its address is fixed and not in
1849: `loop_store_addrs' or if it is not an aggregate. */
1850:
1851: static int
1.1.1.8 root 1852: invariant_p (x)
1.1 root 1853: register rtx x;
1854: {
1855: register int i;
1.1.1.12 root 1856: register enum rtx_code code;
1.1 root 1857: register char *fmt;
1858: int conditional = 0;
1859:
1.1.1.12 root 1860: if (x == 0)
1861: return 1;
1862: code = GET_CODE (x);
1.1 root 1863: switch (code)
1864: {
1865: case CONST_INT:
1866: case CONST_DOUBLE:
1867: case SYMBOL_REF:
1868: case LABEL_REF:
1869: case CONST:
1870: return 1;
1871:
1872: case PC:
1873: case CC0:
1874: return 0;
1875:
1876: case REG:
1.1.1.8 root 1877: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
1.1.1.6 root 1878: since the reg might be set by initialization within the loop. */
1879: if (x == frame_pointer_rtx || x == arg_pointer_rtx)
1.1.1.2 root 1880: return 1;
1.1 root 1881: if (n_times_set[REGNO (x)] == -1)
1882: return 2;
1883: return n_times_set[REGNO (x)] == 0;
1884:
1885: case MEM:
1.1.1.14 root 1886: /* Constants in the constant pool are invariant.
1887: ?? Really we should detect any constant address in the
1888: text section. */
1889: if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
1890: && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
1891: return 1;
1.1 root 1892: /* A store in a varying-address scalar (or a subroutine call)
1893: could clobber anything in memory. */
1894: if (unknown_address_altered)
1895: return 0;
1.1.1.2 root 1896: /* Don't mess with volatile memory references. */
1.1.1.8 root 1897: if (MEM_VOLATILE_P (x))
1.1.1.2 root 1898: return 0;
1.1.1.6 root 1899: #if 0
1.1.1.2 root 1900: /* If it's declared read-only, it is invariant
1901: if its address is invariant. */
1.1.1.8 root 1902: if (RTX_UNCHANGING_P (x))
1903: return invariant_p (XEXP (x, 0));
1.1.1.6 root 1904: #endif
1.1 root 1905: /* A store in a varying-address aggregate component
1906: could clobber anything except a scalar with a fixed address. */
1907: if (unknown_aggregate_altered
1.1.1.8 root 1908: && ((MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS)
1.1 root 1909: || rtx_addr_varies_p (x)))
1910: return 0;
1911: /* A store in a fixed-address aggregate component
1912: could clobber anything whose address is not fixed,
1913: even an aggregate component. */
1914: if (fixed_aggregate_altered
1915: && rtx_addr_varies_p (x))
1916: return 0;
1917: /* Any store could clobber a varying-address scalar. */
1918: if (loop_store_addrs_idx
1.1.1.8 root 1919: && !(MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS)
1.1 root 1920: && rtx_addr_varies_p (x))
1921: return 0;
1922: /* A store in a fixed address clobbers overlapping references. */
1923: for (i = loop_store_addrs_idx - 1; i >= 0; i--)
1.1.1.2 root 1924: if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i]))
1.1 root 1925: return 0;
1926: /* It's not invalidated by a store in memory
1927: but we must still verify the address is invariant. */
1.1.1.2 root 1928: break;
1929:
1930: case ASM_OPERANDS:
1931: /* Don't mess with insns declared volatile. */
1.1.1.8 root 1932: if (MEM_VOLATILE_P (x))
1.1.1.2 root 1933: return 0;
1.1 root 1934: }
1935:
1936: fmt = GET_RTX_FORMAT (code);
1937: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1938: {
1939: if (fmt[i] == 'e')
1940: {
1.1.1.8 root 1941: int tem = invariant_p (XEXP (x, i));
1.1 root 1942: if (tem == 0)
1943: return 0;
1944: if (tem == 2)
1945: conditional = 1;
1946: }
1.1.1.2 root 1947: else if (fmt[i] == 'E')
1948: {
1949: register int j;
1950: for (j = 0; j < XVECLEN (x, i); j++)
1951: {
1.1.1.8 root 1952: int tem = invariant_p (XVECEXP (x, i, j));
1.1.1.2 root 1953: if (tem == 0)
1954: return 0;
1955: if (tem == 2)
1956: conditional = 1;
1957: }
1958:
1959: }
1.1 root 1960: }
1961:
1962: return 1 + conditional;
1963: }
1964:
1965: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
1966: which is SIZE bytes starting at BASE. */
1967:
1968: int
1969: addr_overlap_p (other, base, size)
1970: rtx other;
1971: rtx base;
1972: int size;
1973: {
1974: int start = 0, end;
1975:
1976: if (GET_CODE (base) == CONST)
1977: base = XEXP (base, 0);
1978: if (GET_CODE (base) == PLUS
1979: && GET_CODE (XEXP (base, 1)) == CONST_INT)
1980: {
1981: start = INTVAL (XEXP (base, 1));
1982: base = XEXP (base, 0);
1983: }
1984:
1985: end = start + size;
1986: return refers_to_mem_p (other, base, start, end);
1987: }
1.1.1.2 root 1988:
1.1.1.4 root 1989: /* Return nonzero if all the insns in the loop that set REG
1.1.1.2 root 1990: are INSN and the immediately following insns,
1991: and if each of those insns sets REG in an invariant way
1.1.1.8 root 1992: (not counting uses of REG in them).
1.1.1.2 root 1993:
1.1.1.4 root 1994: The value is 2 if some of these insns are only conditionally invariant.
1995:
1.1.1.2 root 1996: We assume that INSN itself is the first set of REG
1997: and that its source is invariant. */
1998:
1999: static int
1.1.1.8 root 2000: consec_sets_invariant_p (reg, n_sets, insn)
1.1.1.4 root 2001: int n_sets;
1.1.1.2 root 2002: rtx reg, insn;
2003: {
2004: register rtx p = insn;
2005: register int regno = REGNO (reg);
1.1.1.8 root 2006: rtx temp;
1.1.1.2 root 2007: /* Number of sets we have to insist on finding after INSN. */
1.1.1.4 root 2008: int count = n_sets - 1;
1.1.1.8 root 2009: int old = n_times_set[regno];
1.1.1.15 root 2010: int value = 0;
2011: int this;
1.1.1.2 root 2012:
1.1.1.8 root 2013: /* If N_SETS hit the limit, we can't rely on its value. */
2014: if (n_sets == 127)
2015: return 0;
2016:
2017: n_times_set[regno] = 0;
1.1.1.2 root 2018:
2019: while (count > 0)
2020: {
2021: register enum rtx_code code;
2022: p = NEXT_INSN (p);
2023: code = GET_CODE (p);
1.1.1.8 root 2024:
2025: /* If library call, skip to end of of it. */
2026: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
2027: p = XEXP (temp, 0);
2028:
1.1.1.15 root 2029: this = 0;
1.1.1.2 root 2030: if (code == INSN && GET_CODE (PATTERN (p)) == SET
2031: && GET_CODE (SET_DEST (PATTERN (p))) == REG
1.1.1.15 root 2032: && REGNO (SET_DEST (PATTERN (p))) == regno)
2033: {
2034: this = invariant_p (SET_SRC (PATTERN (p)));
2035: if (this != 0)
2036: value |= this;
1.1.1.17! root 2037: else if (temp = loop_find_reg_equal (p))
1.1.1.15 root 2038: {
2039: this = invariant_p (XEXP (temp, 0));
2040: if (this != 0)
2041: value |= this;
2042: }
2043: }
2044: if (this != 0)
1.1.1.2 root 2045: count--;
2046: else if (code != NOTE)
2047: {
1.1.1.8 root 2048: n_times_set[regno] = old;
1.1.1.2 root 2049: return 0;
2050: }
2051: }
2052:
1.1.1.8 root 2053: n_times_set[regno] = old;
1.1.1.4 root 2054: /* If invariant_p ever returned 2, we return 2. */
1.1.1.15 root 2055: return 1 + (value & 2);
1.1.1.2 root 2056: }
2057:
2058: #if 0
2059: /* I don't think this condition is sufficient to allow INSN
2060: to be moved, so we no longer test it. */
1.1 root 2061:
2062: /* Return 1 if all insns in the basic block of INSN and following INSN
2063: that set REG are invariant according to TABLE. */
2064:
2065: static int
2066: all_sets_invariant_p (reg, insn, table)
2067: rtx reg, insn;
1.1.1.2 root 2068: short *table;
1.1 root 2069: {
2070: register rtx p = insn;
2071: register int regno = REGNO (reg);
2072:
2073: while (1)
2074: {
2075: register enum rtx_code code;
2076: p = NEXT_INSN (p);
2077: code = GET_CODE (p);
2078: if (code == CODE_LABEL || code == JUMP_INSN)
2079: return 1;
2080: if (code == INSN && GET_CODE (PATTERN (p)) == SET
2081: && GET_CODE (SET_DEST (PATTERN (p))) == REG
2082: && REGNO (SET_DEST (PATTERN (p))) == regno)
2083: {
2084: if (!invariant_p (SET_SRC (PATTERN (p)), table))
2085: return 0;
2086: }
2087: }
2088: }
1.1.1.2 root 2089: #endif /* 0 */
1.1 root 2090:
2091: /* Increment N_TIMES_SET at the index of each register
2092: that is modified by an insn between FROM and TO.
1.1.1.8 root 2093: If the value of an element of N_TIMES_SET becomes 127 or more,
2094: stop incrementing it, to avoid overflow.
1.1 root 2095:
2096: Store in *COUNT_PTR the number of actual instruction
2097: in the loop. We use this to decide what is worth moving out. */
2098:
2099: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
2100: In that case, it is the insn that last set reg n. */
2101:
2102: static void
1.1.1.8 root 2103: count_loop_regs_set (from, to, may_not_move, count_ptr, nregs)
1.1 root 2104: register rtx from, to;
2105: char *may_not_move;
2106: int *count_ptr;
2107: int nregs;
2108: {
2109: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
2110: register rtx insn;
2111: register int count = 0;
2112: register rtx dest;
2113:
2114: bzero (last_set, nregs * sizeof (rtx));
2115: for (insn = from; insn != to; insn = NEXT_INSN (insn))
2116: {
1.1.1.2 root 2117: if (GET_CODE (insn) == CALL_INSN)
2118: {
2119: /* If a register is used as a subroutine address,
2120: don't allow this register's setting to be moved out of the loop.
2121: This condition is not at all logically correct
2122: but it averts a very common lossage pattern
2123: and creates lossage much less often. */
2124: if (GET_CODE (PATTERN (insn)) == CALL
2125: && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM
2126: && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG)
2127: {
2128: register int regno
2129: = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0));
2130: may_not_move[regno] = 1;
2131: }
2132: else if (GET_CODE (PATTERN (insn)) == SET
2133: && GET_CODE (SET_SRC (PATTERN (insn))) == CALL
2134: && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM
2135: && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG)
2136: {
2137: register int regno
2138: = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0));
2139: may_not_move[regno] = 1;
2140: /* The call insn itself sets a reg, which cannot be moved. */
2141: may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1;
1.1.1.8 root 2142: if (n_times_set[REGNO (SET_DEST (PATTERN (insn)))] < 127)
2143: n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++;
1.1.1.2 root 2144: }
2145: }
2146: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1.1 root 2147: {
2148: ++count;
1.1.1.2 root 2149: if (GET_CODE (PATTERN (insn)) == CLOBBER
2150: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
2151: /* Don't move a reg that has an explicit clobber.
2152: We might do so sometimes, but it's not worth the pain. */
2153: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
2154: else if (GET_CODE (PATTERN (insn)) == SET)
1.1 root 2155: {
2156: dest = SET_DEST (PATTERN (insn));
2157: while (GET_CODE (dest) == SUBREG
2158: || GET_CODE (dest) == ZERO_EXTRACT
2159: || GET_CODE (dest) == SIGN_EXTRACT
2160: || GET_CODE (dest) == STRICT_LOW_PART)
2161: dest = XEXP (dest, 0);
2162: if (GET_CODE (dest) == REG)
2163: {
2164: register int regno = REGNO (dest);
2165: /* If this is the first setting of this reg
2166: in current basic block, and it was set before,
2167: it must be set in two basic blocks, so it cannot
2168: be moved out of the loop. */
2169: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2170: may_not_move[regno] = 1;
2171: /* If this is not first setting in current basic block,
2172: see if reg was used in between previous one and this.
2173: If so, neither one can be moved. */
2174: if (last_set[regno] != 0
2175: && reg_used_between_p (dest, last_set[regno], insn))
2176: may_not_move[regno] = 1;
1.1.1.8 root 2177: if (n_times_set[regno] < 127)
2178: ++n_times_set[regno];
1.1 root 2179: last_set[regno] = insn;
2180: }
2181: }
2182: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2183: {
2184: register int i;
2185: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2186: {
2187: register rtx x = XVECEXP (PATTERN (insn), 0, i);
1.1.1.2 root 2188: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
2189: /* Don't move a reg that has an explicit clobber.
2190: It's not worth the pain to try to do it correctly. */
2191: may_not_move[REGNO (XEXP (x, 0))] = 1;
1.1 root 2192: if (GET_CODE (x) == SET)
2193: {
2194: dest = SET_DEST (x);
2195: while (GET_CODE (dest) == SUBREG
2196: || GET_CODE (dest) == ZERO_EXTRACT
2197: || GET_CODE (dest) == SIGN_EXTRACT
2198: || GET_CODE (dest) == STRICT_LOW_PART)
2199: dest = XEXP (dest, 0);
2200: if (GET_CODE (dest) == REG)
2201: {
2202: register int regno = REGNO (dest);
1.1.1.8 root 2203: if (n_times_set[regno] < 127)
2204: ++n_times_set[regno];
1.1 root 2205: may_not_move[regno] = 1;
2206: last_set[regno] = insn;
2207: }
2208: }
2209: }
2210: }
2211: }
2212: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
2213: bzero (last_set, nregs * sizeof (rtx));
2214: }
2215: *count_ptr = count;
2216: }
2217:
2218: /* Given a loop that is bounded by LOOP_START and LOOP_END
2219: and that is entered at SCAN_START,
2220: return 1 if the register set by insn INSN is used by
2221: any insn that precedes INSN in cyclic order starting
2222: from the loop entry point. */
2223:
2224: static int
2225: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end)
2226: rtx insn, loop_start, scan_start, loop_end;
2227: {
2228: rtx reg = SET_DEST (PATTERN (insn));
2229: if (INSN_LUID (scan_start) > INSN_LUID (insn))
2230: return (reg_used_between_p (reg, scan_start, loop_end)
2231: || reg_used_between_p (reg, loop_start, insn));
2232: else
2233: return reg_used_between_p (reg, scan_start, insn);
2234: }
1.1.1.8 root 2235:
2236: /* A "basic induction variable" or biv is a pseudo reg that is set
2237: (within this loop) only by incrementing or decrementing it. */
2238: /* A "general induction variable" or giv is a pseudo reg whose
2239: value is a linear function of a biv. */
2240:
2241: /* Bivs are recognized by `basic_induction_var';
2242: Givs by `general_induct_var'. */
2243:
2244: /* An enum for the two different types of givs, those that are used
2245: as memory addresses and those that are calculated into registers. */
2246: enum g_types { DEST_ADDR, DEST_REG };
2247:
2248: /* A `struct induction' is created for every instruction that sets
2249: an induction variable (either a biv or a giv). */
2250:
2251: struct induction
2252: {
2253: rtx insn; /* The insn that sets a biv or giv */
2254: rtx new_reg; /* New register, containing strength reduced
2255: version of this giv. */
2256: int src_regno; /* Biv from which this giv is computed.
2257: (If this is a biv, then this is the biv.) */
2258: enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG giv */
2259: int dest_regno; /* Destination register for insn: this is the
2260: register which was the biv or giv.
2261: For a biv, this equals src_reg.
2262: For a DEST_ADDR type giv, this is 0. */
2263: rtx *location; /* Place in the insn where this giv occurs.
2264: If GIV_TYPE is DEST_REG, this is 0. */
1.1.1.14 root 2265: enum machine_mode mode; /* The mode of this biv or giv */
1.1.1.8 root 2266: rtx mult_val; /* Multiplicative factor for src_reg. */
2267: rtx add_val; /* Additive constant for that product. */
2268: int benefit; /* Gain from eliminating this insn. */
2269: int consec; /* The number of consecutive insn that set this
2270: register; they are all eliminated if this
2271: one is. */
2272: char replaceable; /* 1 if we can substitute the strength-reduced
2273: variable for the original variable.
2274: 0 means they must be kept separate and the
2275: new one must be copied into the old pseudo
2276: reg each time the old one is set. */
2277: char ignore; /* 1 prohibits further processing of this giv */
2278: int lifetime; /* Length of life of this giv */
2279: int times_used; /* # times this giv is used. */
2280: struct induction *family; /* Links together all induction variables that
2281: have the same src register. */
2282: struct induction *forces; /* Points to an induction variable insn which
2283: is used only once, to compute this giv,
2284: and hence can be deleted if this insn is
2285: strength reduced. */
2286: struct induction *forces2; /* Likewise. */
2287: struct induction *same; /* Links together all induction variables that
2288: have the same tuple (src, mult, add). */
2289: };
2290:
2291: /* A `struct iv_class' is created for each biv. */
2292:
2293: struct iv_class {
2294: int regno; /* Pseudo reg which is the biv. */
2295: int biv_count; /* Number of insns setting this reg. */
2296: struct induction *biv; /* List of all insns that set this reg. */
1.1.1.14 root 2297: int giv_count; /* Number of DEST_REG givs computed from this
2298: biv. The resulting count is only used in
2299: check_dbra_loop. */
1.1.1.8 root 2300: struct induction *giv; /* List of all insns that compute a giv
2301: from this reg. */
2302: int total_benefit; /* Sum of BENEFITs of all those givs */
2303: rtx initial_value; /* Value of reg at loop start */
2304: struct iv_class *next; /* Links all class structures together */
1.1.1.14 root 2305: rtx init_insn; /* insn which intializes biv, 0 if none seen. */
1.1.1.8 root 2306: char eliminable; /* 1 if plausible candidate for elimination. */
2307: char nonneg; /* 1 if we added a REG_NONNEG note for this. */
2308: };
2309:
2310: /* Definitions used by the basic induction variable discovery code. */
2311: enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT,
2312: GENERAL_INDUCT };
2313:
2314: /* Relative gain of eliminating various kinds of operations. */
2315: #define NO_BENEFIT 0
2316: #define ADD_BENEFIT 1
2317: #define SHIFT_BENEFIT 2
2318: #define MULT_BENEFIT 4
2319: #define LIBCALL_BENEFIT 15
2320: /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
2321: copy the value of the strength reduced giv to its original register. */
2322: #define COPY_PENALTY 2
2323:
2324: /* Indexed by register number, indicates whether or not register is an
2325: induction variable, and if so what type. */
2326:
2327: static enum iv_mode *induct_var;
2328:
2329: /* Indexed by register number, contains pointer to `struct induction'
2330: if register is a general induction variable. */
2331:
2332: static struct induction **induct_struct;
2333:
2334: /* Indexed by register number, contains pointer to `struct iv_class'
2335: if register is a basic induction variable. */
2336:
2337: static struct iv_class **class_struct;
2338:
2339: /*********************************/
2340:
2341: /* ??? Unfinished optimizations, [email protected] */
2342:
2343: /* strength reduce addresses found in sources (set () (mem ())*/
2344:
2345: /* There is one more optimization you might be interested in doing: to
2346: allocate pseudo registers for frequently-accessed memory locations.
2347: If the same memory location is referenced each time around, it might
2348: be possible to copy it into a register before and out after.
2349: This is especially useful when the memory location is a variable which
2350: is in a stack slot because somewhere its address is taken. If the
2351: loop doesn't contain a function call and the variable isn't volatile,
2352: it is safe to keep the value in a register for the duration of the
2353: loop. One tricky thing is that the copying of the value back from the
2354: register has to be done on all exits from the loop. You need to check that
2355: all the exits from the loop go to the same place. */
2356:
2357: /* WARNING: the interaction of biv elimination, and recognizing 'constant'
2358: bivs may cause problems */
2359:
2360: /* add heuristic so that DEST_ADDR strength reduction does not cause
2361: performance problems */
2362:
2363: /* don't eliminate things that can be combined with an addressing mode?
2364: find all giv that have same biv and mult_val (now must also have
2365: same add_val), then for each giv, check to see if its only use
2366: dies in a following memory address, generate a new memory address
2367: and check to see if valid, if valid then store modified mem addr,
2368: else if not valid addr mark giv as not done so that it will get its
2369: own iv */
2370:
2371: /* consec_sets_giv does not calculate replaceable and forces correctly,
2372: forces should be a more general linked list instead of two entries */
2373:
2374: /* try to optimize branches when it is known that a biv is always positive */
2375:
2376: /* when replace biv in compare insn, should replace with closest giv so that
2377: an optimized branch can still be recognized by combiner, i.e. VAXen acb */
2378:
2379: /* should merge final_value calculation in check_dbra_loop with the
2380: new final_biv_value function */
2381:
2382: /* many of the checks involving uid_luid could be simplified if regscan
2383: was rerun in loop_optimize() whenever a register was added or moved,
2384: also some of the optimizations could be a little less conservative */
2385:
2386: /* Perform strength reduction and induction variable elimination. */
2387:
2388: /* Pseudo registers created during this function will be beyond the last
2389: valid index in several tables including n_times_set and regno_last_uid.
2390: This does not cause a problem here, because the added registers cannot be
2391: givs outside of their loop, and hence will never be reconsidered.
2392: But scan_loop must check regnos to make sure they are in bounds. */
2393:
2394: static void
2395: strength_reduce (scan_start, end, loop_top, insn_count,
2396: loop_start, loop_end, nregs)
2397: rtx scan_start;
2398: rtx end;
2399: rtx loop_top;
2400: int insn_count;
2401: rtx loop_start;
2402: rtx loop_end;
2403: int nregs;
2404: {
2405: rtx p;
2406: rtx inc_val;
2407: rtx mult_val;
2408: int dest_regno;
2409: int biv_found;
2410: /* This is 1 if current insn could be executed zero times in the loop. */
2411: int maybe_never = 0;
2412: /* List of all possible basic induction variables. */
2413: struct iv_class *iv_list = 0;
2414: /* Temporary list pointers for traversing iv_list. */
2415: struct iv_class *bl, *backbl;
2416: /* Ratio of extra register life span we can justify
2417: for saving an instruction. More if loop doesn't call subroutines
2418: since in that case saving an insn makes more difference
2419: and more registers are available. */
2420: /* ??? could set this to last value of threshold in move_movables */
2421: int threshold = loop_has_call ? 17 : 34;
2422: /* Map of pseudo-register replacements. */
2423: rtx *reg_map;
1.1.1.15 root 2424: int call_seen;
1.1.1.8 root 2425:
2426: induct_var = (enum iv_mode *) alloca (nregs * sizeof (induct_var[0]));
2427: bzero ((char *)induct_var, nregs * sizeof (induct_var[0]));
2428: induct_struct = (struct induction **)
2429: alloca (nregs * sizeof (struct induction *));
2430: bzero ((char *)induct_struct, nregs * sizeof (struct induction *));
2431: class_struct = (struct iv_class **)
2432: alloca (nregs * sizeof (struct iv_class *));
2433: bzero ((char *)class_struct, nregs * sizeof (struct iv_class *));
2434:
2435: /* Scan through loop to find all possible bivs. */
2436:
2437: for (p = NEXT_INSN (loop_start); p != end; p = NEXT_INSN (p))
2438: {
2439: if (GET_CODE (p) == INSN
2440: && GET_CODE (PATTERN (p)) == SET
2441: && GET_CODE (SET_DEST (PATTERN (p))) == REG)
2442: {
2443: dest_regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.15 root 2444: if (induct_var[dest_regno] != NOT_BASIC_INDUCT
2445: && dest_regno >= FIRST_PSEUDO_REGISTER)
1.1.1.8 root 2446: {
2447: if (basic_induction_var (SET_SRC (PATTERN (p)), dest_regno,
2448: &inc_val, &mult_val))
2449: {
2450: /* It is a possible basic induction variable.
2451: Create and initialize an induction structure for it. */
2452:
2453: struct induction *v =
2454: (struct induction *) alloca (sizeof (struct induction));
2455:
2456: v->insn = p;
2457: v->src_regno = dest_regno;
2458: v->dest_regno = dest_regno;
2459: v->mult_val = mult_val;
2460: v->add_val = inc_val;
1.1.1.14 root 2461: v->mode = GET_MODE (SET_DEST (PATTERN (p)));
1.1.1.8 root 2462:
2463: /* Add this to the reg's iv_class, creating a class
2464: if this is the first incrementation of the reg. */
2465:
2466: bl = class_struct[dest_regno];
2467: if (bl)
2468: {
2469: v->family = bl->biv;
2470: bl->biv = v;
2471: bl->biv_count++;
2472: }
2473: else
2474: {
2475: /* Create and initialize new iv_class. */
2476:
2477: bl = (struct iv_class *) alloca (sizeof (struct iv_class));
2478:
2479: bl->regno = dest_regno;
2480: bl->biv = v;
2481: v->family = 0;
2482: bl->giv = 0;
2483: bl->biv_count = 1;
2484: bl->giv_count = 0;
2485:
2486: /* Set initial value to the reg itself. */
2487: bl->initial_value = SET_DEST (PATTERN (p));
1.1.1.14 root 2488: /* We haven't seen the intializing insn yet */
2489: bl->init_insn = 0;
1.1.1.8 root 2490: bl->eliminable = 0;
2491: bl->nonneg = 0;
2492:
2493: /* Add this insn to iv_list. */
2494: bl->next = iv_list;
2495: iv_list = bl;
2496:
2497: /* Put it in the array of iv_lists. */
2498: class_struct[dest_regno] = bl;
2499: }
2500:
2501: induct_var[dest_regno] = BASIC_INDUCT;
2502:
2503: if (loop_dump_stream)
2504: {
2505: fprintf (loop_dump_stream,
2506: "Insn %d: possible biv, reg %d,",
2507: INSN_UID (p), dest_regno);
2508: if (GET_CODE (inc_val) == CONST_INT)
2509: fprintf (loop_dump_stream, " const = %d\n",
2510: INTVAL (inc_val));
2511: else
2512: {
2513: fprintf (loop_dump_stream, " const = ");
2514: print_rtl (loop_dump_stream, inc_val);
2515: fprintf (loop_dump_stream, "\n");
2516: }
2517: }
2518: }
2519: else
2520: induct_var[dest_regno] = NOT_BASIC_INDUCT;
2521: }
2522: }
2523: }
2524:
2525: /* Scan iv_list to remove all regs that proved not to be bivs.
2526: Make a sanity check against n_times_set. */
2527:
2528: biv_found = 0;
2529:
2530: for (backbl = bl = iv_list; bl; backbl = bl, bl = bl->next)
2531: {
2532: if (induct_var[bl->regno] != BASIC_INDUCT)
2533: {
2534: /* Not a basic induction variable, remove this iv_class. */
2535:
2536: if (backbl == bl)
2537: iv_list = bl->next;
2538: else
2539: backbl->next = bl->next;
2540:
2541: if (loop_dump_stream)
2542: fprintf (loop_dump_stream, "Reg %d: biv discarded, not induct\n",
2543: bl->regno);
2544: }
2545: else if (n_times_set[bl->regno] != bl->biv_count)
2546: {
2547: /* This happens if register modified by subreg, etc. */
2548: /* Make sure it is not recognized as a basic induction var: */
2549: /* remove this iv_class from iv_list. */
2550:
2551: induct_var[bl->regno] = NOT_BASIC_INDUCT;
2552:
2553: if (backbl == bl)
2554: iv_list = bl->next;
2555: else
2556: backbl->next = bl->next;
2557:
2558: if (loop_dump_stream)
2559: fprintf (loop_dump_stream, "Reg %d: biv discarded, count error\n",
2560: bl->regno);
2561: }
2562: else
2563: {
2564: /* This is a valid basic induction variable. */
2565:
2566: biv_found++;
2567:
2568: if (loop_dump_stream)
2569: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
2570: }
2571: }
2572:
2573: /* Exit if there are no bivs. */
2574: if (!iv_list)
2575: return;
2576:
2577: /* Find initial value for each biv. */
2578: /* Search backwards from loop_start, halting at first label
2579: or when all bivs have been seen. */
2580:
1.1.1.15 root 2581: call_seen = 0;
1.1.1.8 root 2582: p = loop_start;
2583: while (biv_found)
2584: {
2585: p = PREV_INSN (p);
2586: if (p == 0)
2587: break;
2588:
1.1.1.15 root 2589: if (GET_CODE (p) == CALL_INSN)
2590: call_seen = 1;
2591:
1.1.1.8 root 2592: if (GET_CODE (p) == INSN
1.1.1.16 root 2593: && GET_CODE (PATTERN (p)) == SET)
1.1.1.8 root 2594: {
1.1.1.16 root 2595: rtx dest = SET_DEST (PATTERN (p));
1.1.1.8 root 2596:
1.1.1.16 root 2597: while (GET_CODE (dest) == SUBREG
2598: || GET_CODE (dest) == ZERO_EXTRACT
2599: || GET_CODE (dest) == SIGN_EXTRACT
2600: || GET_CODE (dest) == STRICT_LOW_PART)
2601: dest = XEXP (dest, 0);
1.1.1.8 root 2602:
1.1.1.16 root 2603: if (GET_CODE (dest) == REG)
2604: {
2605: int dest_regno = REGNO (dest);
2606: if (induct_var[dest_regno] == BASIC_INDUCT
2607: && class_struct[dest_regno]->init_insn == 0)
2608: {
2609: /* This is the first modification found for this reg. */
1.1.1.15 root 2610:
1.1.1.16 root 2611: rtx src = SET_SRC (PATTERN (p));
1.1.1.14 root 2612:
1.1.1.16 root 2613: /* Record the intializing INSN */
1.1.1.14 root 2614:
1.1.1.16 root 2615: class_struct[dest_regno]->init_insn = p;
1.1.1.14 root 2616:
1.1.1.8 root 2617: if (loop_dump_stream)
1.1.1.16 root 2618: fprintf (loop_dump_stream, "Biv %d initialized at insn %d: ",
2619: dest_regno, INSN_UID (p));
2620:
2621: /* Save value if it is a constant or register. */
2622: if (CONSTANT_P (src)
2623: || (GET_CODE (src) == REG
2624: /* Don't try to use a value in a hard reg
2625: across a call which clobbers it. */
2626: && ! (REGNO (src) < FIRST_PSEUDO_REGISTER
2627: && call_used_regs[REGNO (src)]
2628: && call_seen)
2629: && ! reg_set_between_p (src, p, loop_start)))
1.1.1.8 root 2630: {
1.1.1.16 root 2631: class_struct[dest_regno]->initial_value = src;
2632:
2633: if (loop_dump_stream)
2634: fprintf (loop_dump_stream, "initial value ");
2635: if (loop_dump_stream)
1.1.1.14 root 2636: {
1.1.1.16 root 2637: if (GET_CODE (src) == CONST_INT)
2638: fprintf (loop_dump_stream, "%d\n", INTVAL (src));
2639: else
2640: {
2641: print_rtl (loop_dump_stream, src);
2642: fprintf (loop_dump_stream, "\n");
2643: }
1.1.1.14 root 2644: }
1.1.1.8 root 2645: }
1.1.1.16 root 2646: else
2647: {
2648: /* Biv initial value is not simple move,
2649: so let it keep intial value of "itself". */
1.1.1.8 root 2650:
1.1.1.16 root 2651: if (loop_dump_stream)
2652: fprintf (loop_dump_stream, "complex initial value\n");
2653: }
1.1.1.8 root 2654:
1.1.1.16 root 2655: biv_found--;
2656: }
1.1.1.8 root 2657: }
2658: }
2659: else if (GET_CODE (p) == CODE_LABEL)
2660: break;
2661: }
2662:
2663: /* Search the loop for general induction variables. */
2664:
2665: /* A register is a giv if: it is only set once, it is a function of a
2666: biv and a constant (or invariant), and it is not a biv. */
2667:
2668: p = scan_start;
2669: while (1)
2670: {
2671: p = NEXT_INSN (p);
2672: /* At end of a straight-in loop, we are done.
2673: At end of a loop entered at the bottom, scan the top. */
2674: if (p == scan_start)
2675: break;
2676: if (p == end)
2677: {
2678: if (loop_top != 0)
2679: p = NEXT_INSN (loop_top);
2680: else
2681: break;
2682: if (p == scan_start)
2683: break;
2684: }
2685:
2686: /* Look for a general induction variable in a register. */
2687: if (GET_CODE (p) == INSN
2688: && GET_CODE (PATTERN (p)) == SET
1.1.1.17! root 2689: && GET_CODE (SET_DEST (PATTERN (p))) == REG
! 2690: && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))])
1.1.1.8 root 2691: {
2692: int src_regno;
2693: rtx add_val;
2694: rtx mult_val;
2695: int benefit;
2696: rtx regnote = 0;
2697: struct induction *forces = 0;
2698: struct induction *forces2 = 0;
2699:
2700: dest_regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.15 root 2701: if (dest_regno < FIRST_PSEUDO_REGISTER)
2702: continue;
1.1.1.8 root 2703:
2704: if (/* Normal giv. */
2705: ((benefit = general_induction_var (SET_SRC (PATTERN (p)),
2706: &src_regno, &add_val,
2707: &mult_val,
2708: &forces, &forces2))
2709: /* Giv set with call to a library routine. */
1.1.1.17! root 2710: || ((regnote = loop_find_reg_equal (p))
1.1.1.8 root 2711: &&
2712: (benefit = general_induction_var (XEXP (regnote, 0),
2713: &src_regno,
2714: &add_val, &mult_val,
2715: &forces, &forces2))))
1.1.1.11 root 2716: /* Don't try to handle any regs made by loop optimization.
2717: We have nothing on them in regno_first_uid, etc. */
2718: && dest_regno < old_max_reg
1.1.1.8 root 2719: /* Don't recognize a BASIC_INDUCT_VAR here. */
2720: && dest_regno != src_regno
2721: /* This must be the only place where the register is set. */
2722: && (n_times_set[dest_regno] == 1
2723: || (benefit = consec_sets_giv (benefit, p,
2724: src_regno, dest_regno,
2725: &add_val, &mult_val))))
2726: {
2727: int count;
2728: struct induction *v =
2729: (struct induction *) alloca (sizeof (struct induction));
2730: rtx temp;
2731:
2732: record_giv (v, p, src_regno, dest_regno, mult_val, add_val, benefit,
1.1.1.14 root 2733: forces, forces2, DEST_REG, maybe_never, 0, loop_end);
1.1.1.8 root 2734:
2735: /* Skip the consecutive insns, if there are any. */
2736: for (count = v->consec - 1; count >= 0; count--)
2737: {
2738: /* If first insn of libcall sequence, skip to end. */
2739: /* Do this at start of loop, since INSN is guaranteed to
2740: be an insn here. */
2741: if (temp = find_reg_note (p, REG_LIBCALL, 0))
2742: {
2743: /* Eliminating a libcall does more good than
2744: eliminating a single insn to do the same job. */
2745: benefit += LIBCALL_BENEFIT;
2746: p = XEXP (temp, 0);
2747: }
2748:
2749: do p = NEXT_INSN (p);
2750: while (GET_CODE (p) == NOTE);
2751: }
2752: }
2753: }
2754:
2755: #ifndef DONT_REDUCE_ADDR
2756: /* Look for givs which are memory addresses. */
2757: /* This resulted in worse code on a VAX 8600. I wonder if it
2758: still does. */
2759: if (GET_CODE (p) == INSN)
1.1.1.14 root 2760: find_mem_givs (PATTERN (p), p, maybe_never, loop_end);
1.1.1.8 root 2761: #endif
2762:
2763: /* Past a label or a jump, we get to insns for which we can't count
2764: on whether or how many times they will be executed during each
2765: iteration. Givs found afterwards cannot be marked replaceable. */
2766: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
2767: maybe_never = 1;
2768: }
2769:
2770: /* Try to prove that the loop counter variable (if any) is always
2771: nonnegative; if so, record that fact with a REG_NONNEG note
2772: so that "decrement and branch until zero" insn can be used. */
2773: check_dbra_loop (loop_end, iv_list, insn_count, loop_start);
2774:
2775: /* Create reg_map to hold substitutions for replaceable giv regs. */
2776: reg_map = (rtx *) alloca (nregs * sizeof (rtx));
2777: bzero ((char *)reg_map, nregs * sizeof (rtx));
2778:
2779: /* Examine each iv class for feasibility of strength reduction/induction
2780: variable elimination. */
2781:
2782: for (bl = iv_list; bl; bl = bl->next)
2783: {
2784: struct induction *v;
2785: int benefit;
2786: int replaceable;
2787: int all_reduced;
2788: rtx final_value = 0;
2789:
2790: /* Test whether it will be possible to eliminate this biv
1.1.1.10 root 2791: provided all givs are reduced. This is possible if either
2792: the reg is not used outside the loop, or we can compute
2793: what its final value will be.
1.1.1.8 root 2794:
2795: Don't try if we put a REG_NONNEG note on the endtest for this biv.
2796: ??? That should be only on machines that have dbra insns. */
2797:
1.1.1.14 root 2798: /* Compare against bl->init_insn rather than loop_start.
2799: We aren't concerned with any uses of the biv between
2800: init_insn and loop_start since these won't be affected
2801: by the value of the biv elsewhere in the function, so
2802: long as init_insn doesn't use the biv itself.
2803: March 14, 1989 -- [email protected] */
2804:
1.1.1.8 root 2805: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
1.1.1.14 root 2806: && bl->init_insn
1.1.1.16 root 2807: && INSN_UID (bl->init_insn) < max_uid
1.1.1.14 root 2808: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
2809: && ! reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)),
2810: SET_SRC (PATTERN (bl->init_insn)))
2811: && ! bl->nonneg)
1.1.1.8 root 2812: || (final_value = final_biv_value (bl, loop_end)))
1.1.1.15 root 2813: check_eliminate_biv (bl, loop_start, end);
1.1.1.8 root 2814: else
2815: {
2816: if (loop_dump_stream)
1.1.1.14 root 2817: {
2818: fprintf (loop_dump_stream,
2819: "Cannot eliminate biv %d.\n",
2820: bl->regno);
2821: fprintf (loop_dump_stream,
2822: "First use: insn %d, last use: insn %d.\n",
2823: regno_first_uid[bl->regno],
2824: regno_last_uid[bl->regno]);
2825: }
1.1.1.8 root 2826: }
2827:
2828: /* This will be true at the end, if all givs which depend on this
2829: biv have been strength reduced.
2830: We can't (currently) eliminate the biv unless this is so. */
2831: all_reduced = 1;
2832:
2833: /* Check each giv in this class. */
2834:
2835: for (v = bl->giv; v; v = v->family)
2836: {
2837: struct induction *tv;
2838:
2839: if (v->ignore)
2840: continue;
2841:
2842: benefit = v->benefit;
2843: replaceable = v->replaceable;
2844:
2845: /* Reduce benefit if not replaceable, since we will insert
2846: a move-insn to replace the insn that calculates this giv. */
2847: if (!replaceable && ! bl->eliminable)
2848: benefit -= COPY_PENALTY;
2849:
2850: /* Decrease the benefit to count the add-insns that we will
2851: insert to increment the reduced reg for the giv. */
2852: benefit -= ADD_BENEFIT * bl->biv_count;
2853:
2854: /* Find all equivalent givs (that bear same relation to the biv).
2855: Link them via the `same' field and add their benefits together.
2856: They can be replaced with a single register. */
2857:
2858: for (tv = v->family; tv; tv = tv->family)
2859: {
2860: if (tv->ignore == 0
2861: && tv->src_regno == v->src_regno
2862: && rtx_equal_p (tv->mult_val, v->mult_val)
2863: && rtx_equal_p (tv->add_val, v->add_val))
2864: {
2865: benefit += tv->benefit;
2866: if (! tv->replaceable)
2867: benefit -= COPY_PENALTY;
2868: v->lifetime += tv->lifetime;
2869: v->times_used += tv->times_used;
2870: tv->ignore = 1;
2871:
2872: /* Link them together via `same' field. */
2873: tv->same = v->same;
2874: v->same = tv;
2875:
2876: if (loop_dump_stream)
2877: fprintf (loop_dump_stream,
2878: "giv of insn %d combined with that of %d.\n",
2879: INSN_UID (v->insn), INSN_UID (tv->insn));
2880: }
2881: }
2882:
2883: /* Decide whether to strength-reduce this giv
2884: or to leave the code unchanged
2885: (recompute it from the biv each time it is used).
2886: This decision can be made independently for each giv. */
2887:
2888: /* ??? Perhaps attempt to guess whether autoincrement will handle
2889: some of the new add insns; if so, can increase BENEFIT
2890: (undo the subtraction of ADD_BENEFIT that was done above). */
2891:
1.1.1.14 root 2892: /* If an insn is not to be strength reduced, then set its ignore
2893: flag, and clear all_reduced. */
2894:
1.1.1.8 root 2895: /* Is it right to consider times_used? */
2896:
1.1.1.14 root 2897: /* ??? What about the insns that are 'forced' by this one?
2898: Although this insn is not worthwhile to reduce, it may be
2899: worthwhile to reduce the simpler givs used to compute this
2900: complex giv. */
2901:
2902: /* ??? Hey! If a giv has its forces field set, then that means
2903: it is not computed directly from the biv, it is instead computed
2904: from a simpler giv. If we define UNFORCE_INSNS, then the simpler
2905: giv will be considered for strength reduction, and this giv should
2906: not cause all_reduced to be cleared because it DOESN'T use the
2907: biv!!! If the simpler giv can not be reduced, then that simpler
2908: biv will still cause all_reduced to be cleared. */
2909:
1.1.1.8 root 2910: if (benefit <= 0)
2911: {
2912: if (loop_dump_stream)
2913: fprintf (loop_dump_stream, "giv of insn %d, no benefit\n",
2914: INSN_UID (v->insn));
2915: v->ignore = 1;
1.1.1.14 root 2916: all_reduced = 0;
1.1.1.8 root 2917: }
2918:
2919: if (v->lifetime * threshold * benefit < insn_count)
2920: {
2921: if (loop_dump_stream)
2922: fprintf (loop_dump_stream,
2923: "giv of insn %d not worth while, %d vs %d.\n",
2924: INSN_UID (v->insn),
2925: v->lifetime * threshold * benefit, insn_count);
2926: v->ignore = 1;
1.1.1.14 root 2927: all_reduced = 0;
1.1.1.8 root 2928: }
2929:
2930: /* Now check that we can increment the reduced giv
2931: without needing a multiply insn. If not, reject it. */
2932:
2933: if (! v->ignore)
2934: {
2935: int success = 1;
2936:
2937: for (tv = bl->biv; tv; tv = tv->family)
2938: if (tv->mult_val == const1_rtx)
2939: success &= product_cheap_p (tv->add_val, v->mult_val);
2940:
2941: if (! success)
2942: {
2943: if (loop_dump_stream)
2944: fprintf (loop_dump_stream,
2945: "giv of insn %d: would need a multiply.\n",
2946: INSN_UID (v->insn));
2947: v->ignore = 1;
1.1.1.14 root 2948: all_reduced = 0;
1.1.1.8 root 2949: }
2950: }
2951: }
2952:
2953: /* Reduce each giv that we decided to reduce. */
2954:
2955: for (v = bl->giv; v; v = v->family)
2956: {
2957: struct induction *tv;
2958: if (! v->ignore)
2959: {
1.1.1.11 root 2960: rtx new_reg;
2961:
2962: /* Note Iris compiler dies if ?: is used inside gen_reg_rtx. */
2963: if (v->giv_type == DEST_ADDR)
2964: new_reg = gen_reg_rtx (Pmode);
2965: else
2966: new_reg = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (v->insn))));
1.1.1.8 root 2967:
2968: /* For each place where the biv is incremented,
2969: add an insn to increment the new, reduced reg for the giv.
2970: Insert it before the insn that sets the biv,
2971: so that the biv increment remains last before the endtest,
2972: so that dbra will still be recognized. */
2973:
2974: for (tv = bl->biv; tv; tv = tv->family)
2975: {
1.1.1.14 root 2976: struct induction *iv;
2977: rtx before_insn = tv->insn;
2978:
2979: /* If this increment is between the setting of the giv and
2980: its use, don't increment until after the use. */
2981: for (iv = v; iv; iv = iv->same)
2982: {
2983: if (INSN_LUID (tv->insn) <= INSN_LUID (iv->insn)
2984: && ((iv->forces
2985: && (INSN_LUID (tv->insn)
2986: >= INSN_LUID (iv->forces->insn))
2987: || (iv->forces2
2988: && (INSN_LUID (tv->insn)
2989: >= INSN_LUID (iv->forces2->insn))))))
2990: {
2991: before_insn = NEXT_INSN (iv->insn);
2992: break;
2993: }
2994: }
2995:
1.1.1.8 root 2996: if (tv->mult_val == const1_rtx)
2997: emit_iv_inc (tv->add_val, v->mult_val,
1.1.1.14 root 2998: new_reg, before_insn);
1.1.1.8 root 2999: else /* tv->mult_val == const0_rtx */
3000: /* A multiply is acceptable here
3001: since this is presumed to be seldom executed. */
3002: emit_iv_init_code (tv->add_val, v->mult_val,
1.1.1.14 root 3003: v->add_val, new_reg, before_insn);
1.1.1.8 root 3004: }
3005:
3006: /* Add code at loop start to initialize giv's reduced reg. */
3007:
3008: emit_iv_init_code (bl->initial_value, v->mult_val,
3009: v->add_val, new_reg, loop_start);
1.1.1.16 root 3010: /* If the initial value uses a register,
3011: then we may have just extended its range of appearance.
3012: Update this conservatively for the sake of outer loops. */
3013: if (GET_CODE (bl->initial_value) == REG
3014: && (uid_luid[regno_last_uid[REGNO (bl->initial_value)]]
3015: < INSN_LUID (loop_start)))
3016: uid_luid[regno_last_uid[REGNO (bl->initial_value)]]
3017: = INSN_LUID (loop_start);
1.1.1.8 root 3018:
3019: /* For each giv register that can be reduced now:
3020: delete old insn that modifies the giv,
3021: if replaceable, substitute reduced reg
3022: wherever the old giv occurs;
3023: else add new move insn "giv_reg = reduced_reg". */
3024:
3025: for (tv = v; tv; tv = tv->same)
3026: {
3027: /* Record the identity of the reduced reg. */
3028: tv->new_reg = new_reg;
3029:
3030: if (tv->giv_type == DEST_ADDR)
3031: {
3032: /* Store reduced reg as the address in the memref
3033: where we found this giv. */
3034: * tv->location = new_reg;
3035: }
3036: else if (tv->replaceable)
3037: {
3038: reg_map[tv->dest_regno] = new_reg;
3039: /* If giv lives after end of loop,
3040: emit insn to copy reduced reg into old reg,
1.1.1.14 root 3041: at the end of the loop.
3042: ?? insufficient; used before loop could
3043: mean live after loop, due to surrounding loop. */
3044: /* Currently a giv used outside
3045: the loop will not be marked replaceable,
3046: so these deficiencies don't really hurt. */
1.1.1.8 root 3047: if (uid_luid[regno_last_uid[tv->dest_regno]]
3048: > uid_luid[INSN_UID (loop_end)])
1.1.1.14 root 3049: {
3050: /* ?? This won't work. We need to do this at
3051: ALL exits. */
3052: emit_insn_after (gen_rtx (SET, VOIDmode,
3053: SET_DEST (PATTERN (tv->insn)),
3054: new_reg),
3055: loop_end);
3056: abort ();
3057: }
1.1.1.8 root 3058: }
3059: else
3060: {
1.1.1.14 root 3061: /* Not replaceable; emit an insn to set the
3062: original giv reg from the reduced giv. */
3063:
3064: int count;
3065: rtx after_insn = tv->insn;
3066:
3067: for (count = tv->consec; count > 0; count--)
3068: after_insn = next_real_insn (after_insn);
3069:
1.1.1.11 root 3070: /* Put new insn after, not before, in case
1.1.1.14 root 3071: after_insn is the end of a libcall. */
1.1.1.11 root 3072: emit_insn_after (gen_rtx (SET, VOIDmode,
1.1.1.8 root 3073: SET_DEST (PATTERN (tv->insn)),
3074: new_reg),
1.1.1.14 root 3075: after_insn);
1.1.1.8 root 3076: }
3077:
3078: /* Delete the insn that used to set the old giv reg,
3079: unless we modified an address in it.
3080: In any case, delete the other insns used for this one. */
3081: delete_insn_forces (tv, tv->giv_type != DEST_ADDR);
3082:
3083: if (loop_dump_stream)
3084: fprintf (loop_dump_stream, "giv at %d reduced to reg %d\n",
3085: INSN_UID (tv->insn), REGNO (new_reg));
3086: }
3087: /* One set of equivalent givs has been strength-reduced. */
3088: }
1.1.1.14 root 3089: #if 0
1.1.1.8 root 3090: else if (v->new_reg == 0)
3091: {
3092: /* This giv wasn't reduced and is not worth reducing. */
3093:
3094: for (tv = v; tv; tv = tv->same)
3095: if (loop_dump_stream)
3096: fprintf (loop_dump_stream, "giv at %d not reduced\n",
3097: INSN_UID (tv->insn));
3098:
3099: all_reduced = 0;
3100: }
1.1.1.14 root 3101: #endif
1.1.1.8 root 3102: }
3103:
3104: /* All the givs in this family have been reduced if they merit it. */
3105:
3106: /* Try to eliminate the biv, if it is a candidate.
3107: This won't work if ! all_reduced,
3108: since the givs we planned to use might not have been reduced. */
3109:
3110: if (all_reduced == 1 && bl->eliminable)
3111: {
3112: /* Get the REG rtx for the biv. */
3113: rtx reg = SET_DEST (PATTERN (bl->biv->insn));
3114:
3115: for (p = loop_start; p != end; p = NEXT_INSN (p))
3116: {
3117: enum rtx_code code = GET_CODE (p);
3118: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
3119: && reg_mentioned_p (reg, PATTERN (p))
3120: && SET_DEST (PATTERN (p)) == cc0_rtx)
3121: /* Found a compare instruction using this biv;
3122: rewrite it to use a related giv. */
1.1.1.16 root 3123: {
3124: struct induction *v1;
3125: /* If this is an insn which uses the biv ONLY in the
3126: calculation of a giv which is in the family of this
3127: biv, it's ok becuase it will go away when the giv is
3128: reduced. */
3129: for (v1 = bl->giv; v1; v1 = v1->family)
3130: if (v1->insn == p)
3131: {
3132: if (v1->giv_type == DEST_REG
3133: || (v1->giv_type == DEST_ADDR
1.1.1.17! root 3134: /* I thought the test was backwards,
! 3135: but then I found the real problem
! 3136: was in the subroutine. */
! 3137: && ! other_reg_use_p (reg, *(v1->location),
! 3138: PATTERN (p))))
1.1.1.16 root 3139: break;
3140: }
3141: if (!v1)
3142: eliminate_biv (p, bl, loop_start);
3143: }
1.1.1.8 root 3144: }
3145:
3146: /* Biv is no longer really needed inside the loop,
3147: so delete all insns that set the biv. */
3148:
3149: for (v = bl->biv; v; v = v->family)
3150: delete_insn (v->insn);
3151:
1.1.1.14 root 3152: /* ?? If we created a new test to bypass the loop entirely,
3153: or otherwise drop straight in, based on this test, then
3154: we might want to rewrite it also. This way some later
3155: pass has more hope of removing the intialization of this
3156: biv entirely. */
3157:
1.1.1.8 root 3158: /* If final_value != 0, then biv may be used after loop end
3159: and we must emit an insn to set it just in case. */
3160: if (final_value != 0)
3161: emit_insn_after (gen_rtx (SET, VOIDmode, reg, final_value),
3162: loop_end);
3163:
3164: if (loop_dump_stream)
3165: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
3166: bl->regno);
3167: }
3168: }
3169:
3170: /* Go through all the instructions in the loop, making all the
3171: register substitutions scheduled in REG_MAP. */
3172:
3173: for (p = loop_start; p != end; p = NEXT_INSN (p))
3174: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3175: || GET_CODE (p) == CALL_INSN)
3176: replace_regs (PATTERN (p), reg_map, nregs);
1.1.1.14 root 3177:
3178: if (loop_dump_stream)
3179: fprintf (loop_dump_stream, "\n");
3180: }
3181:
1.1.1.17! root 3182: /* Nonzero if register REG appears somewhere within IN, other than in
1.1.1.14 root 3183: subexpressions EQ to EXPR. This is a modification of reg_mentioned_p. */
3184:
3185: int
1.1.1.17! root 3186: other_reg_use_p (reg, expr, in)
1.1.1.14 root 3187: register rtx reg, expr, in;
3188: {
3189: register char *fmt;
3190: register int i;
3191: register enum rtx_code code;
3192:
1.1.1.17! root 3193: if (in == 0 || in == expr)
1.1.1.14 root 3194: return 0;
3195:
3196: if (reg == in)
3197: return 1;
3198:
3199: code = GET_CODE (in);
3200:
3201: switch (code)
3202: {
3203: /* Compare registers by number. */
3204: case REG:
3205: return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
3206:
3207: /* These codes have no constituent expressions
3208: and are unique. */
3209: case CC0:
3210: case PC:
3211: case CONST_INT:
3212: case CONST_DOUBLE:
3213: case SYMBOL_REF:
3214: case CODE_LABEL:
3215: return 0;
3216: }
3217:
3218: fmt = GET_RTX_FORMAT (code);
3219:
3220: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3221: {
3222: if (fmt[i] == 'E')
3223: {
3224: register int j;
3225: for (j = XVECLEN (in, i) - 1; j >= 0; j--)
1.1.1.17! root 3226: if (other_reg_use_p (reg, expr, XVECEXP (in, i, j)))
1.1.1.14 root 3227: return 1;
3228: }
3229: else if (fmt[i] == 'e'
1.1.1.17! root 3230: && other_reg_use_p (reg, expr, XEXP (in, i)))
1.1.1.14 root 3231: return 1;
3232: }
3233: return 0;
1.1.1.8 root 3234: }
3235:
3236: /* Scan X for memory refs and check each memory address
3237: as a possible giv. INSN is the insn whose pattern X comes from.
3238: MAYBE_NEVER is 1 if the loop might execute INSN zero times. */
3239:
3240: static void
1.1.1.14 root 3241: find_mem_givs (x, insn, maybe_never, loop_end)
1.1.1.8 root 3242: rtx x;
3243: rtx insn;
3244: int maybe_never;
1.1.1.14 root 3245: rtx loop_end;
1.1.1.8 root 3246: {
3247: register int i, j;
3248: register enum rtx_code code;
3249: register char *fmt;
3250:
3251: if (x == 0)
3252: return;
3253:
3254: code = GET_CODE (x);
3255: switch (code)
3256: {
3257: case REG:
3258: case CONST_INT:
3259: case CONST:
3260: case CONST_DOUBLE:
3261: case SYMBOL_REF:
3262: case LABEL_REF:
3263: case PC:
3264: case CC0:
3265: case ADDR_VEC:
3266: case ADDR_DIFF_VEC:
3267: case USE:
3268: case CLOBBER:
3269: return;
3270:
3271: case MEM:
3272: {
3273: int src_regno;
3274: rtx add_val;
3275: rtx mult_val;
3276: int benefit;
3277: struct induction *forces = 0;
3278: struct induction *forces2 = 0;
3279:
3280: benefit = general_induction_var (XEXP (x, 0),
3281: &src_regno, &add_val, &mult_val,
3282: &forces, &forces2);
3283: if (benefit > 0)
3284: {
3285: /* Found one; record it. */
3286: struct induction *v =
3287: (struct induction *) oballoc (sizeof (struct induction));
3288:
3289: record_giv (v, insn, src_regno, 0, mult_val, add_val, benefit,
1.1.1.14 root 3290: forces, forces2, DEST_ADDR, maybe_never, &XEXP (x, 0),
3291: loop_end);
1.1.1.8 root 3292: }
3293: return;
3294: }
3295: }
3296:
3297: /* Recursively scan the subexpressions for other mem refs. */
3298:
3299: fmt = GET_RTX_FORMAT (code);
3300: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3301: if (fmt[i] == 'e')
1.1.1.14 root 3302: find_mem_givs (XEXP (x, i), insn, maybe_never, loop_end);
1.1.1.8 root 3303: else if (fmt[i] == 'E')
3304: for (j = 0; j < XVECLEN (x, i); j++)
1.1.1.14 root 3305: find_mem_givs (XVECEXP (x, i, j), insn, maybe_never, loop_end);
1.1.1.8 root 3306: }
3307:
3308: /* Fill in the data about one giv.
3309: V is the `struct induction' in which we record the giv. (It is
3310: allocated by the caller, with alloca.)
3311: INSN is the insn that sets it.
3312: BENEFIT estimates the savings from deleting this insn.
3313: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
3314: into a register or is used as a memory address.
3315:
3316: SRC_REGNO is the biv reg number which the giv is computed from.
3317: DEST_REGNO is the giv's reg number (if the giv is stored in a reg).
3318: MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
3319: FORCES and FORCES2, if nonzero, are other `struct induction's for
3320: other givs which are used to compute this giv indirectly.
3321: LOCATION points to the place where this giv's value appears in INSN. */
3322:
3323: static void
3324: record_giv (v, insn, src_regno, dest_regno, mult_val, add_val, benefit,
1.1.1.14 root 3325: forces, forces2, type, maybe_never, location, loop_end)
1.1.1.8 root 3326: struct induction *v;
3327: rtx insn;
3328: int src_regno, dest_regno;
3329: rtx mult_val, add_val;
3330: int benefit;
3331: struct induction *forces, *forces2;
3332: enum g_types type;
3333: int maybe_never;
3334: rtx *location;
1.1.1.14 root 3335: rtx loop_end;
1.1.1.8 root 3336: {
3337: struct induction *b;
3338: struct iv_class *bl;
3339:
3340: v->insn = insn;
3341: v->src_regno = src_regno;
3342: v->giv_type = type;
3343: v->dest_regno = dest_regno;
3344: v->mult_val = mult_val;
3345: v->add_val = add_val;
3346: v->benefit = benefit;
3347: v->location = location;
3348:
3349: if (type == DEST_ADDR)
3350: {
1.1.1.14 root 3351: v->mode = GET_MODE (*location);
1.1.1.8 root 3352: v->consec = 0;
3353: v->lifetime = 1;
3354: v->times_used = 1;
3355: }
1.1.1.14 root 3356: else /* type == DEST_REG */
1.1.1.8 root 3357: {
1.1.1.14 root 3358: v->mode = GET_MODE (SET_DEST (PATTERN (insn)));
1.1.1.8 root 3359: v->consec = n_times_set[dest_regno] - 1;
3360: v->lifetime = (uid_luid[regno_last_uid[dest_regno]]
3361: - uid_luid[regno_first_uid[dest_regno]]);
3362: v->times_used = n_times_used[dest_regno];
3363: }
3364:
3365: v->same = 0;
3366: v->forces = 0;
3367: v->forces2 = 0;
3368: v->ignore = 0;
3369: v->new_reg = 0;
3370:
3371: /* Mark giv as forced if it is only used to compute another giv. */
3372:
3373: /* This check is not sufficient as INSN may have been moved giving
3374: it a new uid, so make another check by calculating lifetimes.
3375: This is overconservative but seems to be correct. */
3376:
3377: if (forces)
3378: {
3379: v->benefit += forces->benefit;
3380: if ((regno_last_uid[forces->dest_regno] == INSN_UID (insn)
3381: ||
3382: ((uid_luid[regno_last_uid[forces->dest_regno]]
3383: - uid_luid[regno_first_uid[forces->dest_regno]])
1.1.1.15 root 3384: == (INSN_LUID (insn) - INSN_LUID (forces->insn))))
1.1.1.8 root 3385: && !reg_used_between_p (SET_DEST (PATTERN (forces->insn)),
3386: forces->insn, insn))
3387: {
3388: v->forces = forces;
3389: forces->ignore = 1;
3390: }
3391: }
3392:
3393: if (forces2)
3394: {
3395: v->benefit += forces2->benefit;
3396: if ((regno_last_uid[forces2->dest_regno] == INSN_UID (insn)
3397: ||
3398: ((uid_luid[regno_last_uid[forces2->dest_regno]]
3399: - uid_luid[regno_first_uid[forces2->dest_regno]])
1.1.1.15 root 3400: == (INSN_LUID (insn) - INSN_LUID (forces2->insn))))
1.1.1.8 root 3401: && !reg_used_between_p (SET_DEST (PATTERN (forces2->insn)),
3402: forces2->insn, insn))
3403: {
3404: if (v->forces)
3405: v->forces2 = forces2;
3406: else
3407: v->forces = forces2;
3408: forces2->ignore = 1;
3409: }
3410: }
3411:
3412: if (type == DEST_REG)
3413: {
3414: induct_var[dest_regno] = GENERAL_INDUCT;
3415: induct_struct[dest_regno] = v;
3416: }
3417:
3418: /* Add the giv to the class of givs computed from one biv. */
3419:
3420: bl = class_struct[src_regno];
3421: if (bl)
3422: {
3423: v->family = bl->giv;
3424: bl->giv = v;
1.1.1.14 root 3425: /* Don't count DEST_ADDR. This is supposed to count the number of
3426: insns that calculate givs. */
3427: if (type == DEST_REG)
3428: bl->giv_count++;
1.1.1.8 root 3429: bl->total_benefit += benefit;
3430: }
3431: else
1.1.1.15 root 3432: /* Fatal error, biv missing for this giv? */
3433: abort ();
1.1.1.8 root 3434:
3435: if (type == DEST_ADDR)
3436: v->replaceable = 1;
3437: else
3438: {
3439: /* The giv can be replaced outright by the reduced register if
1.1.1.11 root 3440: - the insn that sets the giv is always executed on any iteration
3441: on which the giv is used at all
3442: (there are two ways to deduce this:
3443: either the insn is executed on every iteration,
3444: or all uses follow that insn in the same basic block),
1.1.1.8 root 3445: - the giv is not used before the insn that sets it,
3446: i.e. no definition outside loop reaches into loop
3447: - no assignments to the biv occur during the giv's lifetime. */
3448:
1.1.1.14 root 3449: /* Is this right? Don't we need to make sure the giv is not used
3450: outside the loop. Someday we will know where all the loop exits
3451: are so we can do better, but until then....
3452: March 18, 1989 -- [email protected] */
3453:
1.1.1.11 root 3454: if (regno_first_uid[dest_regno] == INSN_UID (insn)
3455: /* Previous line always fails if INSN was moved by loop opt. */
1.1.1.14 root 3456: && uid_luid[regno_last_uid[dest_regno]] < INSN_LUID (loop_end)
1.1.1.11 root 3457: && (!maybe_never || last_use_this_basic_block (dest_regno, insn)))
1.1.1.8 root 3458: {
3459: v->replaceable = 1;
3460: for (b = bl->biv; b; b = b->family)
3461: {
3462: if ((uid_luid[INSN_UID (b->insn)] >= uid_luid[regno_first_uid[dest_regno]])
3463: &&
3464: (uid_luid[INSN_UID (b->insn)]
3465: <= uid_luid[regno_last_uid[dest_regno]]))
3466: {
3467: v->replaceable = 0;
3468: break;
3469: }
3470: }
3471: }
3472: else
3473: v->replaceable = 0;
3474: }
3475:
3476: if (loop_dump_stream)
3477: {
3478: if (type == DEST_REG)
3479: fprintf (loop_dump_stream, "Insn %d: giv reg %d",
3480: INSN_UID (insn), dest_regno);
3481: else
3482: fprintf (loop_dump_stream, "Insn %d: dest address",
3483: INSN_UID (insn));
3484:
3485: fprintf (loop_dump_stream, " src reg %d benefit %d",
3486: src_regno, v->benefit);
3487: fprintf (loop_dump_stream, " used %d lifetime %d",
3488: v->times_used, v->lifetime);
3489:
3490: if (v->replaceable)
3491: fprintf (loop_dump_stream, " replaceable");
3492:
3493: if (GET_CODE (mult_val) == CONST_INT)
3494: fprintf (loop_dump_stream, " mult %d",
3495: INTVAL (mult_val));
3496: else
3497: {
3498: fprintf (loop_dump_stream, " mult ");
3499: print_rtl (loop_dump_stream, mult_val);
3500: }
3501:
3502: if (GET_CODE (add_val) == CONST_INT)
3503: fprintf (loop_dump_stream, " add %d",
3504: INTVAL (add_val));
3505: else
3506: {
3507: fprintf (loop_dump_stream, " add ");
3508: print_rtl (loop_dump_stream, add_val);
3509: }
3510: }
3511:
3512: if (loop_dump_stream && v->forces)
3513: fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces->insn));
3514: if (loop_dump_stream && v->forces2)
3515: fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces2->insn));
3516: if (loop_dump_stream && v->consec)
3517: fprintf (loop_dump_stream, " consec %d", v->consec);
3518: if (loop_dump_stream)
3519: fprintf (loop_dump_stream, "\n");
3520: }
3521:
3522: /* Delete the insns forced by the insn described by V.
3523: If THIS_TOO is nonzero, delete that insn itself as well. */
3524:
3525: static void
3526: delete_insn_forces (v, this_too)
3527: struct induction *v;
3528: int this_too;
3529: {
3530: rtx x, p;
3531: int count;
3532: rtx insn;
3533:
3534: if (this_too)
3535: {
3536: insn = v->insn;
3537: for (count = v->consec; count >= 0; count--)
3538: {
3539: /* If first insn of libcall sequence, skip to end. */
3540: /* Do this at start of loop, since p is guaranteed to
3541: be an insn here. */
3542: if (x = find_reg_note (insn, REG_LIBCALL, 0))
3543: insn = XEXP (x, 0);
3544:
1.1.1.13 root 3545: if (x = find_reg_note (insn, REG_RETVAL, 0))
1.1.1.8 root 3546: {
3547: /* This is a library call; delete all insns backward until get to
3548: first insn in this group. */
1.1.1.13 root 3549: rtx first = XEXP (x, 0);
1.1.1.8 root 3550: for (p = insn; p != first; p = PREV_INSN (p))
3551: delete_insn (p);
3552: /* Delete first insn also. */
3553: delete_insn (p);
3554: }
3555: else
3556: delete_insn (insn);
3557:
3558: do insn = NEXT_INSN (insn);
3559: while (GET_CODE (insn) == NOTE);
3560: }
3561: }
3562:
3563: if (v->forces)
3564: delete_insn_forces (v->forces, 1);
3565: if (v->forces2)
3566: delete_insn_forces (v->forces2, 1);
3567: }
3568:
3569: /* Check whether an insn is an increment legitimate for a basic induction var.
3570: X is the source of the insn.
3571: DEST_REG is the putative biv, also the destination of the insn.
3572: We accept patterns of these forms:
3573: REG = REG + INVARIANT
3574: REG = INVARIANT + REG
3575: REG = REG - CONSTANT
3576:
3577: If X is suitable, we return 1,
3578: and store the factor multiplying REF in X into *MULT_VAL
3579: and the additive term into *INC_VAL.
3580: Otherwise we return 0. */
3581:
3582: static int
3583: basic_induction_var (x, dest_regno, inc_val, mult_val)
3584: register rtx x;
3585: int dest_regno;
3586: rtx *inc_val;
3587: rtx *mult_val;
3588: {
1.1.1.12 root 3589: register enum rtx_code code;
1.1.1.8 root 3590: rtx arg;
3591:
1.1.1.12 root 3592: if (x == 0)
3593: return 0;
3594: code = GET_CODE (x);
1.1.1.8 root 3595: switch (code)
3596: {
3597: case PLUS:
3598: if (GET_CODE (XEXP (x, 0)) == REG
3599: && REGNO (XEXP (x, 0)) == dest_regno)
3600: arg = XEXP (x, 1);
3601: else if (GET_CODE (XEXP (x, 1)) == REG
3602: && REGNO (XEXP (x, 1)) == dest_regno)
3603: arg = XEXP (x, 0);
3604: else
3605: return 0;
3606:
3607: if (invariant_p (arg) == 1)
3608: *inc_val = arg;
3609: else
3610: return 0;
3611:
3612: *mult_val = const1_rtx;
3613: return 1;
3614:
3615: case MINUS:
3616: if (GET_CODE (XEXP (x, 0)) == REG
3617: && REGNO (XEXP (x, 0)) == dest_regno
3618: && GET_CODE (XEXP (x, 1)) == CONST_INT)
3619: *inc_val = gen_rtx (CONST_INT, VOIDmode,
3620: - INTVAL (XEXP (x, 1)));
3621: else
3622: return 0;
3623: *mult_val = const1_rtx;
3624: return 1;
3625:
3626: /* Can accept constant setting of biv only when inside inner most loop.
3627: Otherwise, a biv of an inner loop may be incorrectly recognized
3628: as a biv of the outer loop,
3629: causing code to be moved INTO the inner loop. */
3630: case REG:
3631: if (!invariant_p (x))
3632: return 0;
3633: case CONST_INT:
3634: case SYMBOL_REF:
3635: case CONST:
3636: if (loops_enclosed == 1)
3637: {
3638: *inc_val = x;
3639: *mult_val = const0_rtx;
3640: return 1;
3641: }
3642: else
3643: return 0;
3644:
3645: default:
3646: return 0;
3647: }
3648: }
3649:
3650: /* A general induction variable (giv) is any quantity that is a linear function
3651: of a basic induction variable, i.e. giv = biv * mult_val + add_val.
3652: The coefficients can be any loop invariant quantity.
3653: A giv need not be computed directly from the biv;
3654: it can be computed by way of other givs. */
3655:
3656: /* Determine whether X computes a giv.
3657: If it does, return a nonzero value
3658: which is the benefit from eliminating the computation of X;
3659: set *SRC_REGNO to the register number of the biv that it is computed from;
3660: set *ADD_VAL and *MULT_VAL to the coefficients,
3661: such that the value of X is biv * mult + add;
3662: set forces (and forces2) to identify any other givs that are used
3663: solely to compute this one. */
3664:
3665: /* This routine recognizes four types of patterns that generate givs:
3666: - giv = biv op invariant v = 0, g = 0
3667: - giv1 = giv2 op invariant v = 0, g = giv2
3668: where giv1 and giv2 are functions of the same biv
3669: - giv1 = biv op giv2 v = giv2, g = 0
3670: where giv2 is a function of biv
3671: - giv1 = giv2 op giv3 v = giv3, g = giv2
3672: where giv2 and giv3 are functions of the save biv */
3673:
3674: static int
3675: general_induction_var (x, src_regno, add_val, mult_val, forces, forces2)
3676: rtx x;
3677: int *src_regno;
3678: rtx *add_val;
3679: rtx *mult_val;
3680: struct induction **forces;
3681: struct induction **forces2;
3682: {
1.1.1.12 root 3683: register enum rtx_code code;
1.1.1.8 root 3684: rtx arg;
3685: struct induction *g = 0;
3686: struct induction *v = 0;
3687: int subexp = 0;
3688: int tem;
3689:
1.1.1.12 root 3690: if (x == 0)
3691: return 0;
3692:
3693: code = GET_CODE (x);
1.1.1.8 root 3694: switch (code)
3695: {
3696: case NEG:
3697: /* This can generate givs also, but it is not handled. */
3698: return 0;
3699:
3700: case MULT:
3701: case UMULT:
1.1.1.16 root 3702: /* Reject widening multiply in version 1.
3703: That is safer than trying to handle it. */
3704: {
3705: enum machine_mode m0 = GET_MODE (XEXP (x, 0));
3706: enum machine_mode m1 = GET_MODE (XEXP (x, 1));
3707: if (m0 != VOIDmode && m0 != GET_MODE (x))
3708: return 0;
3709: if (m1 != VOIDmode && m1 != GET_MODE (x))
3710: return 0;
3711: }
3712: case PLUS:
3713: case MINUS:
1.1.1.8 root 3714: /* Result is linear in both operands. */
3715: /* Determine which operand is the biv, and put the other in ARG. */
3716: if (GET_CODE (XEXP (x, 0)) == REG
3717: && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT)
3718: {
3719: *src_regno = REGNO (XEXP (x, 0));
3720: arg = XEXP (x, 1);
3721:
3722: }
3723: else if (GET_CODE (XEXP (x, 1)) == REG
3724: && induct_var[REGNO (XEXP (x, 1))] == BASIC_INDUCT)
3725: {
3726: *src_regno = REGNO (XEXP (x, 1));
3727: arg = XEXP (x, 0);
3728:
3729: }
3730: /* Check for an rtl subexpression that is a giv. Memory address
3731: givs often look like (plus (reg) (mult (biv) (const))). */
3732: /* Do this before checking for a giv operand, as this function will
3733: fail if this special operand is not recognized. */
3734: #ifndef DONT_REDUCE_ADDR
3735: else if (tem = general_induction_var (XEXP (x, 1), src_regno,
3736: add_val, mult_val,
1.1.1.15 root 3737: forces, forces2)
3738: && code != MINUS)
1.1.1.8 root 3739: {
3740: /* Set subexp true so that this can be handled a little
3741: differently from the normal case of g set. */
3742: /* Note that SRC_REGNO is already set. */
3743: subexp = TRUE;
3744: g = (struct induction *) alloca (sizeof (struct induction));
3745: g->mult_val = *mult_val;
3746: g->add_val = *add_val;
1.1.1.15 root 3747: /* Fake out the test below. */
3748: g->replaceable = 1;
1.1.1.8 root 3749: /* Count this multiply as a shift, since that's what it
3750: really will do. */
3751: if (tem == MULT_BENEFIT)
3752: g->benefit = SHIFT_BENEFIT;
3753: else
3754: g->benefit = tem;
3755: arg = XEXP (x, 0);
3756: }
1.1.1.16 root 3757: else if (tem = general_induction_var (XEXP (x, 0), src_regno,
3758: add_val, mult_val,
3759: forces, forces2))
3760: {
3761: /* Set subexp true so that this can be handled a little
3762: differently from the normal case of g set. */
3763: /* Note that SRC_REGNO is already set. */
3764: subexp = TRUE;
3765: g = (struct induction *) alloca (sizeof (struct induction));
3766: g->mult_val = *mult_val;
3767: g->add_val = *add_val;
3768: /* Fake out the test below. */
3769: g->replaceable = 1;
3770: /* Count this multiply as a shift, since that's what it
3771: really will do. */
3772: if (tem == MULT_BENEFIT)
3773: g->benefit = SHIFT_BENEFIT;
3774: else
3775: g->benefit = tem;
3776: arg = XEXP (x, 1);
3777: }
1.1.1.8 root 3778: #endif
3779: /* Also allow general induction variables.
3780: Could have a mult followed by an add (i.e. an address calculation),
3781: thereby generating two related general induction variables
3782: of which only the second is actually used. */
3783: /* Do this after checking both args for basic induction variables. */
3784: else if (GET_CODE (XEXP (x, 0)) == REG
3785: && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT)
3786: {
3787: g = induct_struct[REGNO (XEXP (x, 0))];
3788: *src_regno = g->src_regno;
3789: arg = XEXP (x, 1);
3790: }
3791: else if (GET_CODE (XEXP (x, 1)) == REG
1.1.1.15 root 3792: && induct_var[REGNO (XEXP (x, 1))] == GENERAL_INDUCT
3793: && code != MINUS)
1.1.1.8 root 3794: {
3795: g = induct_struct[REGNO (XEXP (x, 1))];
3796: *src_regno = g->src_regno;
3797: arg = XEXP (x, 0);
3798: }
3799: else
3800: return 0;
3801:
3802: /* Overall form of expression looks good. */
3803: break;
3804:
3805: /* Could handle these also. */
3806: case DIV:
3807: case UDIV:
3808: /* For a 68020 could handle these? */
3809: case LSHIFT:
3810: case ASHIFT:
3811: case ASHIFTRT:
3812: case LSHIFTRT:
3813: /* These operations are linear only in first operand.
3814: Check for a biv or giv there; if found, put other operand in ARG. */
3815: if (GET_CODE (XEXP (x, 0)) == REG
3816: && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT)
3817: {
3818: *src_regno = REGNO (XEXP (x, 0));
3819: arg = XEXP (x, 1);
3820: }
3821: /* Also allow general induction variable. */
3822: else if (GET_CODE (XEXP (x, 0)) == REG
3823: && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT)
3824: {
3825: g = induct_struct[REGNO (XEXP (x, 0))];
3826: *src_regno = g->src_regno;
3827: arg = XEXP (x, 1);
3828: }
3829: else
3830: return 0;
3831:
3832: /* Overall form of expression looks good. */
3833: break;
3834:
3835: default:
3836: return 0;
3837: }
3838:
3839: /* ARG is the operand that is NOT a biv or giv.
3840: Test it for superficial validity. */
3841:
3842: /* This is just a special case of invariant values,
3843: it is not really needed, but it's a shortcut. */
3844: if (GET_CODE (arg) == CONST_INT)
3845: ;
3846:
3847: /* Depends on previous general induction variable, which has
3848: the same basic induction variable */
3849: /* This code detects mults that have been generated as shift and add. */
3850: else if (GET_CODE (arg) == REG
3851: && induct_var[REGNO (arg)] == GENERAL_INDUCT
3852: && induct_struct[REGNO (arg)]->src_regno == *src_regno)
3853: {
3854: v = induct_struct[REGNO (arg)];
3855: /* Dependence indicated by forces, sort of kludgey. */
3856: }
3857:
3858: /* Invariant expression, could be a constant-valued register. */
3859: else if (invariant_p (arg) == 1)
3860: ;
3861:
3862: /* Failure */
3863: else
3864: return 0;
1.1.1.15 root 3865:
3866: /* Until we can do the correct thing, suppress use of nonreplaceable givs
3867: as sources for other givs. */
3868: if ((g && ! g->replaceable)
3869: || (v && ! v->replaceable))
3870: return 0;
1.1.1.8 root 3871:
3872: /* Now we know looks like a giv; extract the coefficients.
3873: We can still fail if the coefficients are not what we can handle. */
3874:
3875: /* Only succeed if result mult_val and add_val are only one level of rtl,
3876: for example, (NEG:SI (REG:SI 34)) is not accepted.
3877: This mainly causes problems with the MINUS code. */
3878:
3879: switch (code)
3880: {
3881: case PLUS:
3882: if (v && g)
3883: {
3884: if (GET_CODE (g->mult_val) == CONST_INT)
3885: {
3886: if (g->mult_val == const0_rtx)
3887: *mult_val = v->mult_val;
3888: else if (GET_CODE (v->mult_val) == CONST_INT)
3889: *mult_val = gen_rtx (CONST_INT, VOIDmode,
3890: INTVAL (g->mult_val)
3891: + INTVAL (v->mult_val));
3892: else
3893: return 0;
3894: }
3895: else if (v->mult_val == const0_rtx)
3896: *mult_val = g->mult_val;
3897: else
3898: return 0;
3899:
3900: if (GET_CODE (g->add_val) == CONST_INT)
3901: {
3902: if (g->add_val == const0_rtx)
3903: *add_val = v->add_val;
3904: else if (GET_CODE (v->add_val) == CONST_INT)
3905: *add_val = gen_rtx (CONST_INT, VOIDmode,
3906: INTVAL (g->add_val)
3907: + INTVAL (v->add_val));
3908: else
3909: return 0;
3910: }
3911: else if (v->add_val == const0_rtx)
3912: *add_val = g->add_val;
3913: else
3914: return 0;
3915:
3916: if (subexp)
3917: {
3918: /* g deleted when return, can't return pointer to it */
3919: if (*forces2 == 0)
3920: *forces2 = v;
3921: return ADD_BENEFIT + g->benefit;
3922: }
3923: else
3924: {
3925: *forces = g;
3926: *forces2 = v;
3927: return ADD_BENEFIT;
3928: }
3929: }
3930: else if (v)
3931: {
3932: if (GET_CODE (v->mult_val) == CONST_INT)
3933: *mult_val = gen_rtx (CONST_INT, VOIDmode,
3934: INTVAL (v->mult_val) + 1);
3935: else
3936: return 0;
3937: *add_val = v->add_val;
3938: *forces = v;
3939: return ADD_BENEFIT;
3940: }
3941: else if (g)
3942: {
3943: *mult_val = g->mult_val;
1.1.1.17! root 3944: if (GET_CODE (g->add_val) == CONST_INT
! 3945: && nonmemory_operand (arg, GET_MODE (arg)))
1.1.1.16 root 3946: *add_val = plus_constant (arg, INTVAL (g->add_val));
1.1.1.17! root 3947: else if (GET_CODE (arg) == CONST_INT
! 3948: && nonmemory_operand (g->add_val, GET_MODE (g->add_val)))
1.1.1.16 root 3949: *add_val = plus_constant (g->add_val, INTVAL (arg));
1.1.1.8 root 3950: else
3951: /* Could succeed if arg == 0, but that will never occur. */
3952: return 0;
3953:
3954: if (subexp)
3955: /* g deleted when return, can't return pointer to it */
3956: return ADD_BENEFIT + g->benefit;
3957: else
3958: {
3959: *forces = g;
3960: return ADD_BENEFIT;
3961: }
3962: }
3963: else
3964: {
3965: *mult_val = const1_rtx;
3966: *add_val = arg;
3967: return ADD_BENEFIT;
3968: }
3969:
3970: /* Takes a lot of code and will rarely succeed. */
3971: case MINUS:
3972: if (v && g)
3973: {
3974: /* G is the first argument of MINUS. */
3975:
3976: if (GET_CODE (g->mult_val) == CONST_INT)
3977: {
3978: if (g->mult_val == const0_rtx)
3979: #if 0 /* Should not have to fail here */
3980: *mult_val = gen_rtx (NEG, SImode, v->mult_val);
3981: #endif
3982: return 0;
3983: else if (GET_CODE (v->mult_val) == CONST_INT)
3984: *mult_val = gen_rtx (CONST_INT, VOIDmode,
3985: INTVAL (g->mult_val)
3986: - INTVAL (v->mult_val));
3987: else
3988: return 0;
3989: }
3990: else if (v->mult_val == const0_rtx)
3991: *mult_val = g->mult_val;
3992: else
3993: return 0;
3994:
3995: if (GET_CODE (g->add_val) == CONST_INT)
3996: {
3997: if (g->add_val == const0_rtx)
3998: #if 0 /* should not have to fail here */
3999: *add_val = v->add_val;
4000: #endif
4001: return 0;
4002: else if (GET_CODE (v->add_val) == CONST_INT)
4003: *add_val = gen_rtx (CONST_INT, VOIDmode,
4004: INTVAL (g->add_val)
4005: - INTVAL (v->add_val));
4006: else
4007: return 0;
4008: }
4009: else if (v->add_val == const0_rtx)
4010: *add_val = g->add_val;
4011: else
4012: return 0;
4013:
4014: if (subexp)
4015: {
4016: /* G deleted when return, can't return pointer to it */
4017: if (*forces2 == 0)
4018: *forces2 = v;
4019: return ADD_BENEFIT + g->benefit;
4020: }
4021: else
4022: {
4023: *forces = g;
4024: *forces2 = v;
4025: return ADD_BENEFIT;
4026: }
4027: }
4028: else if (v)
4029: {
4030: if (GET_CODE (v->mult_val) != CONST_INT)
4031: return 0;
4032: if (arg == XEXP (x, 0)) /* giv1 = giv2 - biv */
4033: {
4034: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4035: INTVAL (v->mult_val) - 1);
4036: *add_val = v->add_val;
4037: }
4038: else /* giv1 = biv - giv2 */
4039: {
4040: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4041: 1 - INTVAL (v->mult_val));
4042: if (GET_CODE (v->add_val) == CONST_INT)
4043: *add_val = gen_rtx (CONST_INT, VOIDmode,
4044: - INTVAL (v->add_val));
4045: else
4046: return 0;
4047: }
4048: *forces = v;
4049: return ADD_BENEFIT;
4050: }
4051: else if (g)
4052: {
4053: if (arg == XEXP (x, 1))
4054: *mult_val = g->mult_val;
4055: else
4056: {
4057: if (GET_CODE (g->mult_val) == CONST_INT)
4058: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4059: - INTVAL (g->mult_val));
4060: else
4061: return 0;
4062: }
4063: if (GET_CODE (g->add_val) == CONST_INT)
4064: {
4065: if (g->add_val == const0_rtx)
4066: {
4067: if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */
4068: {
4069: /* Fail unless arg is a constant. */
4070: if (GET_CODE (arg) == CONST_INT)
4071: *add_val = gen_rtx (CONST_INT, VOIDmode,
4072: -INTVAL (arg));
4073: else
4074: return 0;
4075: }
4076: else /* giv1 = arg - giv2 */
4077: *add_val = arg;
4078: }
4079: else if (GET_CODE (arg) == CONST_INT)
4080: {
4081: if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */
4082: *add_val = gen_rtx (CONST_INT, VOIDmode,
4083: INTVAL (g->add_val)
4084: - INTVAL (arg));
4085: else /* giv1 = arg - giv2 */
4086: *add_val = gen_rtx (CONST_INT, VOIDmode,
4087: INTVAL (arg),
4088: - INTVAL (g->add_val));
4089: }
4090: else
4091: return 0;
4092: }
4093: else
4094: /* Could succeed if arg == 0, but that will never occur. */
4095: return 0;
4096:
4097: if (subexp)
4098: /* G deleted when return, can't return pointer to it. */
4099: return ADD_BENEFIT + g->benefit;
4100: else
4101: {
4102: *forces = g;
4103: return ADD_BENEFIT;
4104: }
4105: }
4106: else if (GET_CODE (arg) == CONST_INT)
4107: {
4108: if (arg == XEXP (x, 1))
4109: {
4110: *add_val = gen_rtx (CONST_INT, VOIDmode, - INTVAL (arg));
4111: *mult_val = const1_rtx;
4112: }
4113: else
4114: {
4115: *add_val = arg;
4116: *mult_val = gen_rtx (CONST_INT, VOIDmode, -1);
4117: }
4118: return ADD_BENEFIT;
4119: }
4120: else
4121: return 0;
4122:
4123: /* UMULT can be handled like MULT since C ignores overflows. */
4124: case MULT:
4125: case UMULT:
4126: if (v && g)
4127: {
4128: /* Quadratic term, just fail. */
4129: return 0;
4130: }
4131: else if (v)
4132: {
4133: /* Quadratic term, just fail. */
4134: return 0;
4135: }
4136: else if (g)
4137: {
4138: /* Takes a lot of code and will rarely succeed. */
4139: /* dest = m * arg * b + a * arg */
4140: if (GET_CODE (g->mult_val) == CONST_INT)
4141: {
4142: if (g->mult_val == const0_rtx)
4143: *mult_val = const0_rtx;
4144: else if (g->mult_val == const1_rtx)
4145: *mult_val = arg;
4146: else if (GET_CODE (arg) == CONST_INT)
4147: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4148: INTVAL (g->mult_val) * INTVAL (arg));
4149: else
4150: return 0;
4151: }
4152: else
4153: /* Could suceed if arg == 1 or 0, but this will never occur. */
4154: return 0;
4155:
4156: if (GET_CODE (g->add_val) == CONST_INT)
4157: {
4158: if (g->add_val == const0_rtx)
4159: *add_val = const0_rtx;
4160: else if (g->add_val == const1_rtx)
4161: *add_val = arg;
4162: else if (GET_CODE (arg) == CONST_INT)
4163: *add_val = gen_rtx (CONST_INT, VOIDmode,
4164: INTVAL (g->add_val) * INTVAL (arg));
4165: else
4166: return 0;
4167: }
4168: else
4169: /* Could suceed if arg == 1 or 0, but this will never occur. */
4170: return 0;
4171:
4172: if (subexp)
4173: /* G deleted when return, can't return pointer to it. */
4174: return MULT_BENEFIT + g->benefit;
4175: else
4176: {
4177: *forces = g;
4178: return MULT_BENEFIT;
4179: }
4180: }
4181: else
4182: {
4183: *mult_val = arg;
4184: *add_val = const0_rtx;
4185: return MULT_BENEFIT;
4186: }
4187:
4188: /* These are not worth the trouble. */
4189: case DIV:
4190: case UDIV:
4191: return 0;
4192:
4193: /* Handle these, but only for left shift. */
4194: case LSHIFT:
4195: case ASHIFT:
4196: if (v && g)
4197: {
4198: /* Quadratic term, just fail. */
4199: return 0;
4200: }
4201: else if (v)
4202: {
4203: /* Quadratic term, just fail. */
4204: return 0;
4205: }
4206: else if (g)
4207: {
4208: /* Takes a lot of code and will rarely succeed. */
4209: /* dest = ((m * b) << arg) + (a << arg) */
4210: if (GET_CODE (g->mult_val) == CONST_INT)
4211: {
4212: if (g->mult_val == const0_rtx)
4213: *mult_val = const0_rtx;
4214: else if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0)
4215: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4216: INTVAL (g->mult_val)
4217: * (1 << INTVAL (arg)));
4218: else
4219: return 0;
4220: }
4221: else
4222: /* Could suceed if arg == 0, but this will never occur. */
4223: return 0;
4224:
4225: if (GET_CODE (g->add_val) == CONST_INT)
4226: {
4227: if (g->add_val == const0_rtx)
4228: *add_val = const0_rtx;
4229: else if (GET_CODE (arg) == CONST_INT)
4230: *add_val = gen_rtx (CONST_INT, VOIDmode,
4231: INTVAL (g->add_val)
4232: * (1 << INTVAL (arg)));
4233: else
4234: return 0;
4235: }
4236: else
4237: /* Could suceed if arg == 0, but this will never occur. */
4238: return 0;
4239:
4240: if (subexp)
4241: /* G deleted when return, can't return pointer to it. */
4242: return SHIFT_BENEFIT + g->benefit;
4243: else
4244: {
4245: *forces = g;
4246: return SHIFT_BENEFIT;
4247: }
4248: }
4249:
4250: if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0)
4251: *mult_val = gen_rtx (CONST_INT, VOIDmode, 1 << INTVAL (arg));
4252: else
4253: return 0;
4254: *add_val = const0_rtx;
4255: return SHIFT_BENEFIT;
4256:
4257: /* These are not worth the trouble. */
4258: case ASHIFTRT:
4259: case LSHIFTRT:
4260: return 0;
4261:
4262: /* should never reach here */
4263: default:
4264: abort ();
4265: return 0;
4266: }
4267: }
4268:
4269: /* Help detect a giv that is calculated by several consecutive insns;
4270: for example,
4271: giv = biv * M
4272: giv = giv + A
4273: The caller has already identified the first insn P as having a giv as dest;
4274: we check that all other insns that set the same register follow
4275: immediately after P, that they alter nothing else,
4276: and that the result of the last is still a giv.
4277:
4278: The value is 0 if the reg set in P is not really a giv.
4279: Otherwise, the value is the amount gained by eliminating
4280: all the consecutive insns that compute the value.
4281:
4282: FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
4283: SRC_REGNO is the regno of the biv; DEST_REGNO is that of the giv.
4284:
4285: The coefficients of the ultimate giv value are stored in
4286: *MULT_VAL and *ADD_VAL. */
4287:
4288: static int
4289: consec_sets_giv (first_benefit, p, src_regno, dest_regno,
4290: add_val, mult_val)
4291: int first_benefit;
4292: rtx p;
4293: int src_regno;
4294: int dest_regno;
4295: rtx *add_val;
4296: rtx *mult_val;
4297: {
4298: int count;
4299: int benefit = first_benefit;
4300: enum rtx_code code;
1.1.1.17! root 4301: struct induction *forces, *forces2;
1.1.1.8 root 4302: rtx temp;
4303: int tem;
4304:
4305: /* Initialize info used by general_induction_var. */
4306: struct induction *v =
4307: (struct induction *) oballoc (sizeof (struct induction));
4308: v->src_regno = src_regno;
4309: v->mult_val = *mult_val;
4310: v->add_val = *add_val;
4311:
4312: induct_var[dest_regno] = GENERAL_INDUCT;
4313: induct_struct[dest_regno] = v;
4314:
4315: count = n_times_set[dest_regno] - 1;
4316:
4317: while (count > 0)
4318: {
4319: p = NEXT_INSN (p);
4320: code = GET_CODE (p);
4321:
4322: /* If libcall, skip to end of call sequence. */
4323: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
4324: p = XEXP (temp, 0);
4325:
4326: if (code == INSN && GET_CODE (PATTERN (p)) == SET
4327: && GET_CODE (SET_DEST (PATTERN (p))) == REG
4328: && REGNO (SET_DEST (PATTERN (p))) == dest_regno
4329: && ((tem = general_induction_var (SET_SRC (PATTERN (p)), &src_regno,
4330: add_val, mult_val,
4331: &forces, &forces2))
4332: /* Giv created by call to library routine. */
1.1.1.17! root 4333: || ((temp = loop_find_reg_equal (p))
! 4334: && (tem = general_induction_var (XEXP (temp, 0), &src_regno,
! 4335: add_val, mult_val,
! 4336: &forces, &forces2))))
1.1.1.8 root 4337: && src_regno == v->src_regno)
4338: {
4339: count--;
4340: benefit += tem;
4341: v->mult_val = *mult_val;
4342: v->add_val = *add_val;
4343: }
4344: else if (code != NOTE)
4345: {
4346: induct_var[dest_regno] = UNKNOWN_INDUCT;
4347: return 0;
4348: }
4349: }
4350:
4351: return benefit;
4352: }
4353:
4354: /* Generate a SEQUENCE to multiply OP0 and OP1 with result in TARGET.
4355: Use expand_mult to "optimally" do the multiply.
1.1.1.10 root 4356: This also works for machines that do not have multiply insns.
4357: If one of the operands is a constant, it must be the second. */
1.1.1.8 root 4358:
4359: static rtx
4360: gen_iv_mult (mode, op0, op1, target)
4361: enum machine_mode mode;
4362: register rtx op0, op1, target;
4363: {
4364: extern rtx gen_sequence ();
4365: extern rtx start_sequence ();
1.1.1.10 root 4366: rtx saved, result, temp;
1.1.1.8 root 4367:
4368: saved = start_sequence ();
4369:
1.1.1.10 root 4370: /* ??? It is very unmodular to use expand_mult here!
4371: This should be redesigned. */
4372:
1.1.1.8 root 4373: /* UNSIGNEDP arg can be zero since operands/target always same width. */
1.1.1.10 root 4374: temp = expand_mult (mode, op0, op1, target, 0);
4375:
4376: /* Move to target register, if expand_mult did not put it there. */
4377: if (target != 0 && temp != target)
4378: emit_move_insn (target, temp);
1.1.1.8 root 4379:
4380: result = gen_sequence ();
4381: end_sequence (saved);
4382:
4383: return result;
4384: }
4385:
4386: /* Emit code to initialize an induction variable created by strength
1.1.1.15 root 4387: reduction.
4388: More precisely, emit code before INSERT_BEFORE
4389: to set REG = B * M + A. */
1.1.1.14 root 4390:
1.1.1.8 root 4391: static void
1.1.1.15 root 4392: emit_iv_init_code (b, m, a, reg, insert_before)
1.1.1.8 root 4393: rtx b; /* initial value of basic induction variable */
4394: rtx m; /* multiplicative constant */
4395: rtx a; /* additive constant */
4396: rtx reg; /* destination register */
1.1.1.15 root 4397: rtx insert_before;
1.1.1.8 root 4398: {
1.1.1.15 root 4399: rtx seq;
4400: rtx result;
1.1.1.8 root 4401:
1.1.1.15 root 4402: /* Prevent unexpected sharing of these rtx. */
4403: a = copy_rtx (a);
4404: b = copy_rtx (b);
4405:
4406: start_sequence ();
4407: result = expand_mult_add (b, m, a, GET_MODE (reg), 0);
4408: if (reg != result)
4409: emit_move_insn (reg, result);
4410: seq = gen_sequence ();
4411: end_sequence ();
1.1.1.8 root 4412:
1.1.1.15 root 4413: emit_insn_before (seq, insert_before);
4414: }
1.1.1.8 root 4415:
1.1.1.15 root 4416: /* Emit code to increment the induction variable inside the loop.
4417: Try to emit optimal code for the expression
4418: REG = REG + BIV_ADD * GIV_MULT. */
1.1.1.8 root 4419:
1.1.1.15 root 4420: static void
4421: emit_iv_inc (biv_add, giv_mult, reg, insn)
4422: rtx biv_add; /* increment value for biv */
4423: rtx giv_mult; /* multiply value of giv */
4424: rtx reg; /* create insn to set this reg */
4425: rtx insn; /* where to insert the new insn */
4426: {
4427: emit_iv_init_code (biv_add, giv_mult, reg, reg, insn);
1.1.1.8 root 4428: }
4429:
4430: /* Test whethen BIV_ADD * GIV_MULT can be computed without
4431: an actual multiply insn. Value is 1 if so. */
4432:
4433: static int
4434: product_cheap_p (biv_add, giv_mult)
4435: rtx biv_add;
4436: rtx giv_mult;
4437: {
4438: /* Indicates which of MULT/ADD are constants. */
4439: int status = 0;
4440: int const_val;
4441: rtx tmp;
4442:
4443: if (GET_CODE (biv_add) == CONST_INT)
4444: status |= 0x1;
4445: if (GET_CODE (giv_mult) == CONST_INT)
4446: status |= 0x2;
4447:
4448: switch (status)
4449: {
4450: case 0:
4451: /* Neither is constant: would need a multiply insn, so fail. */
4452: return 0;
4453:
4454: case 1:
4455: /* BIV_ADD value is constant */
4456: /* Equivalent to state 2, just switch values of BIV_ADD and GIV_MULT
4457: and fall through. */
4458: tmp = biv_add;
4459: biv_add = giv_mult;
4460: giv_mult = tmp;
4461:
4462: case 2:
4463: /* GIV_MULT value is constant.
4464: If it is 1, 0 or -1 then we win. */
4465: const_val = INTVAL (giv_mult);
4466: if (const_val < -1 || const_val > 1)
4467: {
4468: tmp = gen_iv_mult (GET_MODE (biv_add), biv_add, giv_mult, 0);
4469: /* Don't emit a multiply insn, just fail instead. */
4470: if ((GET_CODE (tmp) == SET && GET_CODE (SET_SRC (tmp)) == MULT)
4471: /* Also fail if library call (which generates more
4472: then two insn) is needed. */
4473: || (GET_CODE (tmp) == SEQUENCE && XVECLEN (tmp, 0) > 2))
4474: return 0;
4475: }
4476: return 1;
4477:
4478: case 3:
4479: /* Both BIV_ADD and GIV_MULT are constant;
4480: can compute the product at compile time. */
4481: return 1;
4482:
4483: default:
4484: abort ();
4485: }
4486: }
4487:
4488:
4489: /* Check to see if loop can be terminated by a "decrement and branch until
4490: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
4491: Also try reversing an increment loop to a decrement loop
4492: to see if the optimization can be performed.
4493: Value is nonzero if optimization was performed. */
4494:
4495: static int
4496: check_dbra_loop (loop_end, iv_list, insn_count, loop_start)
4497: rtx loop_end;
4498: struct iv_class *iv_list;
4499: int insn_count;
4500: rtx loop_start;
4501: {
4502: struct iv_class *bl;
4503: rtx reg;
4504: rtx jump_label;
4505: rtx final_value;
4506: rtx start_value;
4507: enum rtx_code branch_code;
4508: rtx new_add_val;
4509: rtx tested_before_loop = 0;
4510: rtx p;
4511:
4512: /* See if the loop is contained in `if (X >= 0)' for some reg X.
4513: If so, then we know X is initially nonnegative even though
4514: we don't know its initial value.
4515: Record X in TESTED_BEFORE_LOOP. */
4516:
4517: for (p = loop_start; p != 0; p = PREV_INSN (p))
4518: if (GET_CODE (p) != NOTE)
4519: break;
4520:
4521: /* See if a conditional branch preceeds the loop.
4522: There may be no other insns or labels between it and
4523: the beginning of the loop. */
4524: if (p != 0 && GET_CODE (p) == JUMP_INSN && condjump_p (p)
4525: && SET_SRC (PATTERN (p)) != pc_rtx
4526: && ((GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == LT
4527: && XEXP (SET_SRC (PATTERN (p)), 2) == pc_rtx)
4528: ||
4529: (GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == GE
4530: && XEXP (SET_SRC (PATTERN (p)), 1) == pc_rtx))
4531: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end))
4532: {
4533: /* Before the branch should be a test or compare.
4534: See if we are comparing something against zero. */
4535: p = PREV_INSN (p);
4536: if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET
4537: && SET_DEST (PATTERN (p)) == cc0_rtx)
4538: {
4539: if (GET_CODE (SET_SRC (PATTERN (p))) == REG)
4540: tested_before_loop = SET_SRC (PATTERN (p));
1.1.1.14 root 4541: else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE
4542: && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == REG
1.1.1.8 root 4543: && XEXP (SET_SRC (PATTERN (p)), 1) == const0_rtx)
4544: tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 0);
1.1.1.14 root 4545: else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE
4546: && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 1)) == REG
4547: && XEXP (SET_SRC (PATTERN (p)), 0) == const0_rtx)
4548: tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 1);
1.1.1.8 root 4549: }
4550: }
4551:
4552: /* If last insn is a conditional branch, and the insn before tests a register
4553: value, then try to optimize it. */
4554:
4555: if (GET_CODE (PREV_INSN (loop_end)) == JUMP_INSN
4556: && GET_CODE (PATTERN (PREV_INSN (loop_end))) == SET
4557: && GET_CODE (SET_SRC (PATTERN (PREV_INSN (loop_end)))) == IF_THEN_ELSE
4558: && GET_CODE (PREV_INSN (PREV_INSN (loop_end))) == INSN
4559: && GET_CODE (PATTERN (PREV_INSN (PREV_INSN (loop_end)))) == SET
4560: && (GET_CODE (SET_DEST (PATTERN (PREV_INSN (PREV_INSN (loop_end))))) ==
4561: CC0))
4562: {
4563: /* Check all of the bivs to see if the compare uses one of them. */
4564:
4565: for (bl = iv_list; bl; bl = bl->next)
4566: {
4567: if (reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)),
4568: PREV_INSN (PREV_INSN (loop_end))))
4569: break;
4570: }
4571:
4572: /* If biv set more than once, then give up.
1.1.1.15 root 4573: We can't guarantee that it will be zero on the last iteration.
4574: Also give up if the biv is used between its update and the test
4575: insn. */
4576: if (bl && bl->biv_count == 1
4577: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
4578: PREV_INSN (PREV_INSN (loop_end))))
1.1.1.8 root 4579: {
4580: /* Look for the case where the basic induction variable is always
4581: nonnegative, and equals zero on the last iteration.
4582: In this case, add a reg_note REG_NONNEG, which allows the
4583: m68k DBRA instruction to be used. */
4584:
4585: /* the decrement case */
4586:
4587: if (GET_CODE (bl->biv->add_val) == CONST_INT
4588: && INTVAL (bl->biv->add_val) < 0)
4589: {
4590: /* Initial value must be greater than 0,
4591: init_val % -dec_value == 0 to ensure that it equals zero on
4592: the last iteration */
4593:
4594: if (GET_CODE (bl->initial_value) == CONST_INT
4595: && INTVAL (bl->initial_value) > 0
4596: && (INTVAL (bl->initial_value) %
4597: (-INTVAL (bl->biv->add_val))) == 0)
4598: {
4599: /* register always nonnegative, add REG_NOTE to branch */
4600: REG_NOTES (PREV_INSN (loop_end))
4601: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
4602: REG_NOTES (PREV_INSN (loop_end)));
4603: bl->nonneg = 1;
4604:
4605: return 1;
4606: }
4607:
4608: /* If the decrement is 1 and the value was tested as >= 0 before
4609: the loop, then we can safely optimize. */
4610: if (SET_DEST (PATTERN (bl->biv->insn)) == tested_before_loop
4611: && INTVAL (bl->biv->add_val) == -1)
4612: {
4613: REG_NOTES (PREV_INSN (loop_end))
4614: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
4615: REG_NOTES (PREV_INSN (loop_end)));
4616: bl->nonneg = 1;
4617:
4618: return 1;
4619: }
4620: }
1.1.1.15 root 4621: else if (num_mem_sets <= 1)
1.1.1.8 root 4622: {
4623: /* Try to change inc to dec, so can apply above optimization. */
4624: /* Can do this if:
4625: all registers modified are induction variables or invariant,
4626: all memory references have non-overlapping addresses
4627: (obviously true if only one write)
4628: allow 2 insns for the compare/jump at the end of the loop. */
1.1.1.15 root 4629: int num_nonfixed_reads = 0;
4630: rtx p;
4631:
4632: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
4633: if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN
4634: || GET_CODE (p) == JUMP_INSN)
4635: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
1.1.1.8 root 4636:
4637: /* This code only acts for innermost loops. Also it simplifies
4638: the memory address check by only reversing loops with
1.1.1.15 root 4639: zero or one memory access.
4640: Two memory accesses could involve parts of the same array,
4641: and that can't be reversed. */
1.1.1.8 root 4642:
1.1.1.15 root 4643: if (num_nonfixed_reads <= 1
1.1.1.8 root 4644: && !loop_has_call
4645: && (bl->giv_count + bl->biv_count + num_mem_sets
4646: + num_movables + 2 == insn_count))
4647: {
4648: rtx src_two_before_end;
1.1.1.15 root 4649: int constant;
4650: int win;
1.1.1.8 root 4651:
4652: /* Loop can be reversed. */
4653: if (loop_dump_stream)
4654: fprintf (loop_dump_stream, "Can reverse loop\n");
4655:
4656: /* Now check other conditions:
4657: initial_value must be zero,
4658: final_value % add_val == 0, so that when reversed, the
4659: biv will be zero on the last iteration. */
4660:
4661: /* Calculating the final value non trivial.
4662: If branch is (LT (CC0) (CONST 0),
4663: then value in compare is final value.
4664: If branch is (LE (CC0) (CONST 0),
4665: then value in compare is final_value - add_val */
4666:
4667: branch_code
4668: = GET_CODE (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0));
4669: src_two_before_end
1.1.1.14 root 4670: = SET_SRC (PATTERN (PREV_INSN (PREV_INSN (loop_end))));
1.1.1.8 root 4671:
1.1.1.15 root 4672: win = 1;
4673: if (GET_CODE (src_two_before_end) == REG)
4674: constant = 0;
4675: else if (GET_CODE (src_two_before_end) == COMPARE
4676: && GET_CODE (XEXP (src_two_before_end, 1)) == CONST_INT)
4677: constant = INTVAL (XEXP (src_two_before_end, 1));
4678: else
4679: win = 0;
4680:
4681: if (win && bl->initial_value == const0_rtx
1.1.1.8 root 4682: && (branch_code == LT || branch_code == LE)
4683: && XEXP (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0), 1) == const0_rtx
1.1.1.15 root 4684: && (constant % INTVAL (bl->biv->add_val)) == 0)
1.1.1.8 root 4685: {
4686: /* Register will always be nonnegative, with value
4687: 0 on last iteration if loop reversed */
4688:
4689: /* Save some info needed to produce the new insns. */
4690: reg = SET_DEST (PATTERN (bl->biv->insn));
4691: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
4692: new_add_val = gen_rtx (CONST_INT, VOIDmode,
4693: - INTVAL (bl->biv->add_val));
4694:
4695:
4696: if (branch_code == LT)
4697: {
1.1.1.15 root 4698: final_value
4699: = gen_rtx (CONST_INT, VOIDmode, constant);
1.1.1.8 root 4700: start_value
4701: = gen_rtx (CONST_INT, VOIDmode,
1.1.1.15 root 4702: (constant - INTVAL (bl->biv->add_val)));
1.1.1.8 root 4703: }
4704: else /* branch_code == LE */
4705: {
1.1.1.15 root 4706: start_value
4707: = gen_rtx (CONST_INT, VOIDmode, constant);
1.1.1.8 root 4708: final_value
4709: = gen_rtx (CONST_INT, VOIDmode,
1.1.1.15 root 4710: (constant + INTVAL (bl->biv->add_val)));
1.1.1.8 root 4711: }
4712:
4713: /* Initialize biv to start_value before loop start.
4714: The old initializing insn will be deleted as a
4715: dead store by flow.c. */
4716: emit_insn_before (gen_rtx (SET, VOIDmode, reg,
4717: start_value),
4718: loop_start);
4719:
4720: /* Add insn to decrement register, and delete insn
4721: that incremented the register. */
4722: emit_insn_before (gen_rtx (SET, VOIDmode, reg,
4723: gen_rtx (PLUS, GET_MODE (reg), reg,
4724: new_add_val)),
4725: bl->biv->insn);
4726: /* Update biv info to reflect its new status. */
4727: bl->biv->insn = PREV_INSN (bl->biv->insn);
4728: delete_insn (NEXT_INSN (bl->biv->insn));
4729:
1.1.1.15 root 4730: /* Inc LABEL_NUSES so that delete_insn will
1.1.1.8 root 4731: not delete the label. */
1.1.1.15 root 4732: LABEL_NUSES (XEXP (jump_label, 0)) ++;
1.1.1.8 root 4733:
4734: if (regno_last_uid[bl->regno] != INSN_UID (PREV_INSN (loop_end)))
4735: emit_insn_after (gen_rtx (SET, VOIDmode, reg,
4736: final_value),
4737: loop_end);
4738:
4739: /* Delete compare/branch at end of loop. */
4740: delete_insn (PREV_INSN (loop_end));
4741: delete_insn (PREV_INSN (loop_end));
4742:
4743: /* Add new compare/branch insn at end of loop. */
4744: emit_insn_before (gen_rtx (SET, VOIDmode, cc0_rtx, reg),
4745: loop_end);
4746: emit_jump_insn_before (gen_rtx (SET, VOIDmode, pc_rtx,
4747: gen_rtx (IF_THEN_ELSE, VOIDmode,
4748: gen_rtx (GE, VOIDmode, cc0_rtx,
4749: const0_rtx),
4750: jump_label,
4751: pc_rtx)),
4752: loop_end);
4753:
1.1.1.15 root 4754: JUMP_LABEL (PREV_INSN (loop_end)) = XEXP (jump_label, 0);
4755: /* Increment of LABEL_NUSES done above. */
4756:
1.1.1.8 root 4757: /* Register is now always nonnegative,
4758: so add REG_NONNEG note to the branch. */
4759: REG_NOTES (PREV_INSN (loop_end))
4760: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
4761: REG_NOTES (PREV_INSN (loop_end)));
4762: bl->nonneg = 1;
4763:
4764: /* Update rest of biv info. */
4765: bl->initial_value = start_value;
4766: bl->biv->add_val = new_add_val;
4767:
4768: if (loop_dump_stream)
4769: fprintf (loop_dump_stream, "Reversed loop and added reg_nonneg\n");
4770:
4771: return 1;
4772: }
4773: }
4774: }
4775: }
4776: }
4777: return 0;
4778: }
4779:
1.1.1.14 root 4780: /* Verify whether the biv BL appears to be eliminable,
4781: based on the insns in the loop that refer to it.
4782: LOOP_START is the first insn of the loop, and END is the end insn. */
4783:
4784: static void
4785: check_eliminate_biv (bl, loop_start, end)
4786: struct iv_class *bl;
4787: rtx loop_start;
4788: rtx end;
4789: {
4790: /* Get the REG rtx for the biv. */
4791: rtx reg = SET_DEST (PATTERN (bl->biv->insn));
4792: rtx p;
4793: struct induction *v;
4794:
4795: bl->eliminable = 0;
4796:
4797: for (p = loop_start; p != end; p = NEXT_INSN (p))
4798: {
4799: enum rtx_code code = GET_CODE (p);
4800: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
4801: && reg_mentioned_p (reg, PATTERN (p)))
4802: {
4803: /* This insn uses the biv. If we can't understand it,
4804: then we can't eliminate the biv. */
4805: if (GET_CODE (PATTERN (p)) != SET)
4806: {
4807: if (loop_dump_stream)
4808: fprintf (loop_dump_stream,
4809: "Cannot eliminate biv %d: cannot understand insn %d.\n",
4810: bl->regno, INSN_UID (p));
4811: break;
4812: }
4813:
4814: /* The insns that increment the biv are no problem. */
4815: if (SET_DEST (PATTERN (p)) == reg)
4816: continue;
4817:
4818: /* If this is an insn which uses the biv ONLY in the
4819: calculation of a giv which is in the family of this
4820: biv, it's ok becuase it will go away when the giv is
4821: reduced. March 14, 1989 -- [email protected] */
4822: for (v = bl->giv; v; v = v->family)
4823: if (v->insn == p)
4824: {
4825: if (v->giv_type == DEST_REG
4826: || (v->giv_type == DEST_ADDR
1.1.1.17! root 4827: && ! other_reg_use_p (reg, *(v->location),
! 4828: PATTERN (p))))
1.1.1.14 root 4829: break;
4830: }
4831: if (v)
4832: continue;
4833:
4834: /* If can rewrite this insn not to use the biv, it's ok. */
4835: if (can_eliminate_biv_p (p, bl))
4836: continue;
4837:
4838: /* Biv is used in a way we cannot eliminate. */
4839: if (loop_dump_stream)
4840: fprintf (loop_dump_stream,
4841: "Cannot eliminate biv %d: biv used in insn %d.\n",
4842: bl->regno, INSN_UID (p));
4843: break;
4844: }
4845: }
4846:
4847: if (p == end)
4848: {
4849: bl->eliminable = 1;
4850: if (loop_dump_stream)
4851: fprintf (loop_dump_stream, "Can eliminate biv %d.\n",
4852: bl->regno);
4853: }
4854: }
4855:
1.1.1.8 root 4856: /* Return 1 if INSN, a compare insn which tests the biv described by BL,
4857: can be rewritten to use instead some reduced giv related to that biv.
4858: Does not change the rtl.
4859:
4860: We make the assumption that all the givs depending on this biv
4861: will be reduced, since only in that case will an attempt to eliminate
4862: the biv actually be made.
4863:
4864: The following function is very parallel to this one. */
4865:
4866: static int
4867: can_eliminate_biv_p (insn, bl)
4868: rtx insn;
4869: struct iv_class *bl;
4870: {
4871: rtx src;
4872: enum rtx_code code;
4873: struct induction *v, *tv;
4874: rtx arg;
4875: int arg_operand;
4876: /* Mode of this biv. */
1.1.1.14 root 4877: enum machine_mode mode = bl->biv->mode;
1.1.1.8 root 4878:
4879: if (SET_DEST (PATTERN (insn)) != cc0_rtx)
4880: return 0;
4881:
4882: src = SET_SRC (PATTERN (insn));
4883: code = GET_CODE (src);
4884:
4885: switch (code)
4886: {
4887: /* a test insn */
4888: case REG:
4889: /* Can replace with any giv that has (MULT_VAL != 0) and (ADD_VAL == 0)
1.1.1.14 root 4890: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 4891:
4892: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 4893: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
4894: && v->add_val == const0_rtx
4895: && ! v->ignore
4896: && v->mode == mode)
1.1.1.8 root 4897: return 1;
4898:
1.1.1.16 root 4899: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0)
4900: where ADD_VAL is a constant or a register;
4901: can replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
1.1.1.14 root 4902: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 4903:
4904: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 4905: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
1.1.1.16 root 4906: && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT)
1.1.1.14 root 4907: && ! v->ignore
4908: && v->mode == mode)
1.1.1.8 root 4909: return 1;
1.1.1.14 root 4910:
4911: if (loop_dump_stream)
4912: fprintf (loop_dump_stream, "Cannot eliminate biv %d in test insn %d: no appropriate giv.\n",
4913: bl->regno, INSN_UID (insn));
4914:
1.1.1.8 root 4915: return 0;
4916:
4917: /* a compare insn */
1.1.1.13 root 4918: case COMPARE:
1.1.1.8 root 4919: /* Figure out which operand is the biv. */
4920: if ((GET_CODE (XEXP (src, 0)) == REG)
4921: && (REGNO (XEXP (src, 0)) == bl->regno))
4922: {
4923: arg = XEXP (src, 1);
4924: arg_operand = 1;
4925: }
1.1.1.16 root 4926: else if ((GET_CODE (XEXP (src, 1)) == REG)
4927: && (REGNO (XEXP (src, 1)) == bl->regno))
1.1.1.8 root 4928: {
4929: arg = XEXP (src, 0);
4930: arg_operand = 0;
4931: }
1.1.1.16 root 4932: else
4933: return 0;
1.1.1.8 root 4934:
4935: if (GET_CODE (arg) == CONST_INT)
4936: {
4937: /* Can replace with any giv that has constant coefficients. */
4938:
4939: for (v = bl->giv; v; v = v->family)
4940: if (GET_CODE (v->mult_val) == CONST_INT
4941: && GET_CODE (v->add_val) == CONST_INT
1.1.1.14 root 4942: && ! v->ignore
4943: && v->mode == mode)
1.1.1.8 root 4944: return 1;
4945:
4946: /* Look for giv with constant mult_val and nonconst add_val,
4947: since we can insert add insn before loop
4948: to calculate new compare value. */
4949:
4950: for (v = bl->giv; v; v = v->family)
4951: if (GET_CODE (v->mult_val) == CONST_INT
1.1.1.14 root 4952: && ! v->ignore
4953: && v->mode == mode)
1.1.1.8 root 4954: return 1;
4955: }
4956: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
4957: {
4958: /* Comparing against invariant register or memref can be handled. */
4959:
4960: if (invariant_p (arg))
4961: {
4962: /* Look for giv with constant mult_val and nonconst add_val.
4963: Insert add-insn before loop to compute new compare value. */
4964:
4965: for (v = bl->giv; v; v = v->family)
4966: if ((GET_CODE (v->mult_val) == CONST_INT)
1.1.1.14 root 4967: && ! v->ignore
4968: && v->mode == mode)
1.1.1.8 root 4969: return 1;
4970: }
4971:
4972: /* Otherwise, only comparing against a biv can be handled. */
4973: if (GET_CODE (arg) != REG
4974: || induct_var[REGNO (arg)] != BASIC_INDUCT)
4975: return 0;
4976:
4977: /* Look for a giv for each biv that have identical
4978: values for mult_val and add_val. */
4979: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 4980: if (v->mode == mode
4981: && ! v->ignore)
1.1.1.8 root 4982: {
4983: for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
4984: if ((tv->new_reg != 0)
4985: && rtx_equal_p (tv->mult_val, v->mult_val)
4986: && rtx_equal_p (tv->mult_val, v->mult_val)
1.1.1.14 root 4987: && ! tv->ignore
4988: && tv->mode == mode)
1.1.1.8 root 4989: return 1;
4990: }
4991: }
4992: return 0;
4993:
4994: default:
4995: return 0;
4996: }
4997: }
4998:
4999: /* Rewrite a compare insn INSN which uses the biv described by BL
5000: so that it doesn't use that biv any more.
5001: Instead it will use some reduced giv related to that biv.
5002:
5003: The preceding function is very parallel to this one. */
5004:
5005: static void
5006: eliminate_biv (insn, bl, loop_start)
5007: rtx insn;
5008: struct iv_class *bl;
5009: rtx loop_start;
5010: {
5011: rtx src = SET_SRC (PATTERN (insn));
5012: enum rtx_code code = GET_CODE (src);
5013: struct induction *v, *tv;
1.1.1.17! root 5014: rtx arg, temp;
1.1.1.8 root 5015: int arg_operand;
5016: /* Mode of this biv. */
1.1.1.14 root 5017: enum machine_mode mode = bl->biv->mode;
1.1.1.8 root 5018:
5019: switch (code)
5020: {
5021: /* a test insn */
5022: case REG:
1.1.1.14 root 5023: /* Can replace with any giv that was reduced and
5024: that has (MULT_VAL != 0) and (ADD_VAL == 0).
5025: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 5026:
5027: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 5028: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
5029: && v->add_val == const0_rtx
1.1.1.8 root 5030: && v->new_reg != 0
1.1.1.14 root 5031: && v->mode == mode)
1.1.1.8 root 5032: break;
5033: if (v)
5034: {
5035: /* We can test the sign of that giv's reduced reg. */
5036: SET_SRC (PATTERN (insn)) = v->new_reg;
1.1.1.17! root 5037: /* If the giv has the opposite direction of change,
! 5038: then reverse the comparison. */
! 5039: if (INTVAL (v->mult_val) < 0)
! 5040: SET_SRC (PATTERN (insn))
! 5041: = gen_rtx (COMPARE, GET_MODE (v->new_reg),
! 5042: const0_rtx, v->new_reg);
1.1.1.8 root 5043: return;
5044: }
5045:
1.1.1.16 root 5046: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0)
5047: where ADD_VAL is a constant or a register;
1.1.1.14 root 5048: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
5049: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 5050:
5051: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 5052: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
1.1.1.16 root 5053: && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT)
1.1.1.14 root 5054: && v->new_reg != 0
5055: && v->mode == mode)
1.1.1.8 root 5056: break;
5057: if (v)
5058: {
5059: /* Replace biv with the giv's reduced register. */
1.1.1.14 root 5060: SET_SRC (PATTERN (insn)) = gen_rtx (COMPARE, GET_MODE (v->new_reg),
1.1.1.15 root 5061: v->new_reg,
5062: copy_rtx (v->add_val));
1.1.1.8 root 5063:
1.1.1.17! root 5064: /* If the giv has the opposite direction of change,
! 5065: then reverse the comparison. */
! 5066: if (INTVAL (v->mult_val) < 0)
! 5067: {
! 5068: XEXP (SET_SRC (PATTERN (insn)), 0)
! 5069: = XEXP (SET_SRC (PATTERN (insn)), 1);
! 5070: XEXP (SET_SRC (PATTERN (insn)), 1) = v->new_reg;
! 5071: }
1.1.1.8 root 5072: #if 0
5073: /* add_val must be invariant, so don't bother storing in a register */
5074: /* calculate the appropriate constant to compare against */
5075: emit_insn_before (gen_rtx (SET, VOIDmode, compare_value,
1.1.1.15 root 5076: copy_rtx (v->add_val)),
1.1.1.8 root 5077: loop_start);
5078: #endif
5079: return;
5080: }
5081: abort ();
5082: break;
5083:
5084: /* a compare insn */
1.1.1.13 root 5085: case COMPARE:
1.1.1.8 root 5086: /* Figure out which operand is the biv. */
1.1.1.13 root 5087: if (GET_CODE (XEXP (src, 0)) == REG
5088: && REGNO (XEXP (src, 0)) == bl->regno)
1.1.1.8 root 5089: {
5090: arg = XEXP (src, 1);
5091: arg_operand = 1;
5092: }
1.1.1.16 root 5093: else if (GET_CODE (XEXP (src, 1)) == REG
5094: && REGNO (XEXP (src, 1)) == bl->regno)
1.1.1.8 root 5095: {
5096: arg = XEXP (src, 0);
5097: arg_operand = 0;
5098: }
1.1.1.16 root 5099: else
5100: abort ();
1.1.1.8 root 5101:
5102: if (GET_CODE (arg) == CONST_INT)
5103: {
5104: /* Can replace with any giv that has constant mult_val and add_val.
5105: Make sure it was strength reduced by checking new_reg != 0. */
5106:
5107: for (v = bl->giv; v; v = v->family)
5108: if (GET_CODE (v->mult_val) == CONST_INT
5109: && GET_CODE (v->add_val) == CONST_INT
5110: && v->new_reg
1.1.1.14 root 5111: && v->mode == mode)
1.1.1.8 root 5112: break;
5113: if (v)
5114: {
1.1.1.15 root 5115: rtx newval;
1.1.1.8 root 5116: /* Replace biv with the giv's reduced reg. */
5117: XEXP (src, 1-arg_operand) = v->new_reg;
5118: /* Calculate the appropriate constant to compare against. */
1.1.1.15 root 5119: newval = gen_rtx (CONST_INT, VOIDmode,
5120: (INTVAL (arg) * INTVAL (v->mult_val)
5121: + INTVAL (v->add_val)));
5122: XEXP (src, arg_operand) = newval;
5123: /* If that constant is no good in a compare,
5124: put it in a register. */
5125: if (recog (PATTERN (insn), insn) < 0)
5126: {
1.1.1.17! root 5127: temp = gen_reg_rtx (mode);
1.1.1.15 root 5128: emit_iv_init_code (arg, v->mult_val, v->add_val,
5129: temp, loop_start);
5130: XEXP (src, arg_operand) = temp;
5131: }
1.1.1.17! root 5132:
! 5133: /* If the giv has the opposite direction of change,
! 5134: then reverse the comparison. */
! 5135: if (INTVAL (v->mult_val) < 0)
! 5136: {
! 5137: temp = XEXP (src, 0);
! 5138: XEXP (src, 0) = XEXP (src, 1);
! 5139: XEXP (src, 1) = temp;
! 5140: }
1.1.1.8 root 5141: return;
5142: }
5143:
5144: /* Look for giv with constant mult_val and nonconst add_val.
5145: Insert add insn before loop to calculate new compare value. */
5146:
5147: for (v = bl->giv; v; v = v->family)
5148: if (GET_CODE (v->mult_val) == CONST_INT
5149: && v->new_reg
1.1.1.14 root 5150: && v->mode == mode)
1.1.1.8 root 5151: break;
5152: if (v)
5153: {
5154: rtx compare_value = gen_reg_rtx (mode);
5155:
5156: /* Replace biv with giv's reduced register. */
5157: XEXP (src, 1-arg_operand) = v->new_reg;
5158:
5159: /* At start of loop, compute value to compare against. */
1.1.1.15 root 5160: emit_iv_init_code (arg, v->mult_val, v->add_val,
5161: compare_value, loop_start);
5162: /* Use it in this insn. */
1.1.1.8 root 5163: XEXP (src, arg_operand) = compare_value;
1.1.1.17! root 5164:
! 5165: /* If the giv has the opposite direction of change,
! 5166: then reverse the comparison. */
! 5167: if (INTVAL (v->mult_val) < 0)
! 5168: {
! 5169: temp = XEXP (src, 0);
! 5170: XEXP (src, 0) = XEXP (src, 1);
! 5171: XEXP (src, 1) = temp;
! 5172: }
1.1.1.8 root 5173: return;
5174: }
5175: abort ();
5176: }
5177: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
5178: {
5179: if (invariant_p (arg))
5180: {
5181: /* Look for giv with constant mult_val and nonconst add_val.
5182: Insert add-insn before loop to compute new compare value. */
5183:
5184: for (v = bl->giv; v; v = v->family)
5185: if (GET_CODE (v->mult_val) == CONST_INT
5186: && v->new_reg
1.1.1.14 root 5187: && v->mode == mode)
1.1.1.8 root 5188: break;
5189: if (v)
5190: {
5191: rtx compare_value = gen_reg_rtx (mode);
5192:
5193: /* Replace biv with giv's reduced register. */
5194: XEXP (src, 1-arg_operand) = v->new_reg;
5195:
1.1.1.15 root 5196: /* At start of loop, compute value to compare against. */
5197: emit_iv_init_code (arg, v->mult_val, v->add_val,
5198: compare_value, loop_start);
1.1.1.8 root 5199: XEXP (src, arg_operand) = compare_value;
1.1.1.17! root 5200:
! 5201: /* If the giv has the opposite direction of change,
! 5202: then reverse the comparison. */
! 5203: if (INTVAL (v->mult_val) < 0)
! 5204: {
! 5205: temp = XEXP (src, 0);
! 5206: XEXP (src, 0) = XEXP (src, 1);
! 5207: XEXP (src, 1) = temp;
! 5208: }
1.1.1.8 root 5209: return;
5210: }
5211: }
5212:
5213: /* Otherwise the reg compared with had better be a biv. */
5214: if (GET_CODE (arg) != REG
5215: || induct_var[REGNO (arg)] != BASIC_INDUCT)
5216: abort ();
5217:
5218: /* Look for a pair of givs, one for each biv,
5219: with identical coefficients. */
5220: for (v = bl->giv; v; v = v->family)
5221: {
1.1.1.14 root 5222: if (!v->new_reg && v->mode == mode)
1.1.1.8 root 5223: continue;
5224: for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
5225: if ((tv->new_reg != 0)
5226: && rtx_equal_p (tv->mult_val, v->mult_val)
1.1.1.16 root 5227: && rtx_equal_p (tv->add_val, v->add_val)
1.1.1.14 root 5228: && tv->mode == mode)
1.1.1.8 root 5229: break;
5230: if (tv)
5231: break;
5232: }
5233: if (v)
5234: {
5235: /* Replace biv with its giv's reduced reg. */
5236: XEXP (src, 1-arg_operand) = v->new_reg;
5237: /* Replace other operand with the other giv's reduced reg. */
5238: XEXP (src, arg_operand) = tv->new_reg;
1.1.1.17! root 5239:
! 5240: /* If the giv has the opposite direction of change,
! 5241: then reverse the comparison. */
! 5242: if (INTVAL (v->mult_val) < 0)
! 5243: {
! 5244: temp = XEXP (src, 0);
! 5245: XEXP (src, 0) = XEXP (src, 1);
! 5246: XEXP (src, 1) = temp;
! 5247: }
1.1.1.8 root 5248: return;
5249: }
5250: }
5251: abort ();
5252:
5253: default:
5254: abort ();
5255: }
5256: }
5257:
5258: /* Try to calculate the final value of the biv,
5259: the value it will have at the end of the loop.
5260: If we can do it, return that value. */
5261:
1.1.1.10 root 5262: /* ??? One case that should be simple to handle
5263: is when the biv is incremented by an invariant
5264: exactly once each time around the loop,
5265: and when the number of iterations can be determined
5266: (as the value of some invariant).
5267: Then the final value would be BIV + (INCREMENT * NUM_ITERATIONS).
5268:
5269: Once that case is handled, it would become desirable to detect empty
5270: loops and delete them, since this optimization could make empty loops. */
5271:
1.1.1.8 root 5272: static rtx
5273: final_biv_value (bl, loop_end)
5274: struct iv_class *bl;
5275: rtx loop_end;
5276: {
5277: /* wimpy, but guaranteed to work */
5278: return 0;
5279: }
1.1.1.11 root 5280:
5281: /* Return nonzero if the last use of reg REGNO
5282: is in an insn following INSN in the same basic block. */
5283:
5284: static int
5285: last_use_this_basic_block (regno, insn)
5286: int regno;
5287: rtx insn;
5288: {
5289: rtx n;
5290: for (n = insn;
5291: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
5292: n = NEXT_INSN (n))
5293: {
5294: if (regno_last_uid[regno] == INSN_UID (n))
5295: return 1;
5296: }
5297: return 0;
5298: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.