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