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