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