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