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