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