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