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