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