![[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));
1.1.1.19! root 2284: rtx p;
! 2285:
! 2286: /* Scan forward checking for register usage. If we hit INSN, we
! 2287: are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
! 2288: for (p = scan_start; p != insn; p = NEXT_INSN (p))
! 2289: {
! 2290: if ((GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN
! 2291: || GET_CODE (p) == JUMP_INSN)
! 2292: && reg_overlap_mentioned_p (reg, PATTERN (p)))
! 2293: return 1;
! 2294:
! 2295: if (p == loop_end)
! 2296: p = loop_start;
! 2297: }
! 2298:
! 2299: return 0;
1.1 root 2300: }
1.1.1.8 root 2301:
2302: /* A "basic induction variable" or biv is a pseudo reg that is set
2303: (within this loop) only by incrementing or decrementing it. */
2304: /* A "general induction variable" or giv is a pseudo reg whose
2305: value is a linear function of a biv. */
2306:
2307: /* Bivs are recognized by `basic_induction_var';
2308: Givs by `general_induct_var'. */
2309:
2310: /* An enum for the two different types of givs, those that are used
2311: as memory addresses and those that are calculated into registers. */
2312: enum g_types { DEST_ADDR, DEST_REG };
2313:
2314: /* A `struct induction' is created for every instruction that sets
2315: an induction variable (either a biv or a giv). */
2316:
2317: struct induction
2318: {
2319: rtx insn; /* The insn that sets a biv or giv */
2320: rtx new_reg; /* New register, containing strength reduced
2321: version of this giv. */
2322: int src_regno; /* Biv from which this giv is computed.
2323: (If this is a biv, then this is the biv.) */
2324: enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG giv */
2325: int dest_regno; /* Destination register for insn: this is the
2326: register which was the biv or giv.
2327: For a biv, this equals src_reg.
2328: For a DEST_ADDR type giv, this is 0. */
2329: rtx *location; /* Place in the insn where this giv occurs.
2330: If GIV_TYPE is DEST_REG, this is 0. */
1.1.1.14 root 2331: enum machine_mode mode; /* The mode of this biv or giv */
1.1.1.8 root 2332: rtx mult_val; /* Multiplicative factor for src_reg. */
2333: rtx add_val; /* Additive constant for that product. */
2334: int benefit; /* Gain from eliminating this insn. */
2335: int consec; /* The number of consecutive insn that set this
2336: register; they are all eliminated if this
2337: one is. */
2338: char replaceable; /* 1 if we can substitute the strength-reduced
2339: variable for the original variable.
2340: 0 means they must be kept separate and the
2341: new one must be copied into the old pseudo
2342: reg each time the old one is set. */
2343: char ignore; /* 1 prohibits further processing of this giv */
2344: int lifetime; /* Length of life of this giv */
2345: int times_used; /* # times this giv is used. */
2346: struct induction *family; /* Links together all induction variables that
2347: have the same src register. */
2348: struct induction *forces; /* Points to an induction variable insn which
2349: is used only once, to compute this giv,
2350: and hence can be deleted if this insn is
2351: strength reduced. */
2352: struct induction *forces2; /* Likewise. */
2353: struct induction *same; /* Links together all induction variables that
2354: have the same tuple (src, mult, add). */
2355: };
2356:
2357: /* A `struct iv_class' is created for each biv. */
2358:
2359: struct iv_class {
2360: int regno; /* Pseudo reg which is the biv. */
2361: int biv_count; /* Number of insns setting this reg. */
2362: struct induction *biv; /* List of all insns that set this reg. */
1.1.1.14 root 2363: int giv_count; /* Number of DEST_REG givs computed from this
2364: biv. The resulting count is only used in
2365: check_dbra_loop. */
1.1.1.8 root 2366: struct induction *giv; /* List of all insns that compute a giv
2367: from this reg. */
2368: int total_benefit; /* Sum of BENEFITs of all those givs */
2369: rtx initial_value; /* Value of reg at loop start */
2370: struct iv_class *next; /* Links all class structures together */
1.1.1.14 root 2371: rtx init_insn; /* insn which intializes biv, 0 if none seen. */
1.1.1.8 root 2372: char eliminable; /* 1 if plausible candidate for elimination. */
2373: char nonneg; /* 1 if we added a REG_NONNEG note for this. */
2374: };
2375:
2376: /* Definitions used by the basic induction variable discovery code. */
2377: enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT,
2378: GENERAL_INDUCT };
2379:
2380: /* Relative gain of eliminating various kinds of operations. */
2381: #define NO_BENEFIT 0
2382: #define ADD_BENEFIT 1
2383: #define SHIFT_BENEFIT 2
2384: #define MULT_BENEFIT 4
2385: #define LIBCALL_BENEFIT 15
2386: /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
2387: copy the value of the strength reduced giv to its original register. */
2388: #define COPY_PENALTY 2
2389:
2390: /* Indexed by register number, indicates whether or not register is an
2391: induction variable, and if so what type. */
2392:
2393: static enum iv_mode *induct_var;
2394:
2395: /* Indexed by register number, contains pointer to `struct induction'
2396: if register is a general induction variable. */
2397:
2398: static struct induction **induct_struct;
2399:
2400: /* Indexed by register number, contains pointer to `struct iv_class'
2401: if register is a basic induction variable. */
2402:
2403: static struct iv_class **class_struct;
2404:
2405: /*********************************/
2406:
2407: /* ??? Unfinished optimizations, [email protected] */
2408:
2409: /* strength reduce addresses found in sources (set () (mem ())*/
2410:
2411: /* There is one more optimization you might be interested in doing: to
2412: allocate pseudo registers for frequently-accessed memory locations.
2413: If the same memory location is referenced each time around, it might
2414: be possible to copy it into a register before and out after.
2415: This is especially useful when the memory location is a variable which
2416: is in a stack slot because somewhere its address is taken. If the
2417: loop doesn't contain a function call and the variable isn't volatile,
2418: it is safe to keep the value in a register for the duration of the
2419: loop. One tricky thing is that the copying of the value back from the
2420: register has to be done on all exits from the loop. You need to check that
2421: all the exits from the loop go to the same place. */
2422:
2423: /* WARNING: the interaction of biv elimination, and recognizing 'constant'
2424: bivs may cause problems */
2425:
2426: /* add heuristic so that DEST_ADDR strength reduction does not cause
2427: performance problems */
2428:
2429: /* don't eliminate things that can be combined with an addressing mode?
2430: find all giv that have same biv and mult_val (now must also have
2431: same add_val), then for each giv, check to see if its only use
2432: dies in a following memory address, generate a new memory address
2433: and check to see if valid, if valid then store modified mem addr,
2434: else if not valid addr mark giv as not done so that it will get its
2435: own iv */
2436:
2437: /* consec_sets_giv does not calculate replaceable and forces correctly,
2438: forces should be a more general linked list instead of two entries */
2439:
2440: /* try to optimize branches when it is known that a biv is always positive */
2441:
2442: /* when replace biv in compare insn, should replace with closest giv so that
2443: an optimized branch can still be recognized by combiner, i.e. VAXen acb */
2444:
2445: /* should merge final_value calculation in check_dbra_loop with the
2446: new final_biv_value function */
2447:
2448: /* many of the checks involving uid_luid could be simplified if regscan
2449: was rerun in loop_optimize() whenever a register was added or moved,
2450: also some of the optimizations could be a little less conservative */
2451:
2452: /* Perform strength reduction and induction variable elimination. */
2453:
2454: /* Pseudo registers created during this function will be beyond the last
2455: valid index in several tables including n_times_set and regno_last_uid.
2456: This does not cause a problem here, because the added registers cannot be
2457: givs outside of their loop, and hence will never be reconsidered.
2458: But scan_loop must check regnos to make sure they are in bounds. */
2459:
2460: static void
2461: strength_reduce (scan_start, end, loop_top, insn_count,
2462: loop_start, loop_end, nregs)
2463: rtx scan_start;
2464: rtx end;
2465: rtx loop_top;
2466: int insn_count;
2467: rtx loop_start;
2468: rtx loop_end;
2469: int nregs;
2470: {
2471: rtx p;
2472: rtx inc_val;
2473: rtx mult_val;
2474: int dest_regno;
2475: int biv_found;
2476: /* This is 1 if current insn could be executed zero times in the loop. */
2477: int maybe_never = 0;
2478: /* List of all possible basic induction variables. */
2479: struct iv_class *iv_list = 0;
2480: /* Temporary list pointers for traversing iv_list. */
2481: struct iv_class *bl, *backbl;
2482: /* Ratio of extra register life span we can justify
2483: for saving an instruction. More if loop doesn't call subroutines
2484: since in that case saving an insn makes more difference
2485: and more registers are available. */
2486: /* ??? could set this to last value of threshold in move_movables */
2487: int threshold = loop_has_call ? 17 : 34;
2488: /* Map of pseudo-register replacements. */
2489: rtx *reg_map;
1.1.1.15 root 2490: int call_seen;
1.1.1.8 root 2491:
2492: induct_var = (enum iv_mode *) alloca (nregs * sizeof (induct_var[0]));
2493: bzero ((char *)induct_var, nregs * sizeof (induct_var[0]));
2494: induct_struct = (struct induction **)
2495: alloca (nregs * sizeof (struct induction *));
2496: bzero ((char *)induct_struct, nregs * sizeof (struct induction *));
2497: class_struct = (struct iv_class **)
2498: alloca (nregs * sizeof (struct iv_class *));
2499: bzero ((char *)class_struct, nregs * sizeof (struct iv_class *));
2500:
2501: /* Scan through loop to find all possible bivs. */
2502:
2503: for (p = NEXT_INSN (loop_start); p != end; p = NEXT_INSN (p))
2504: {
2505: if (GET_CODE (p) == INSN
2506: && GET_CODE (PATTERN (p)) == SET
2507: && GET_CODE (SET_DEST (PATTERN (p))) == REG)
2508: {
2509: dest_regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.15 root 2510: if (induct_var[dest_regno] != NOT_BASIC_INDUCT
2511: && dest_regno >= FIRST_PSEUDO_REGISTER)
1.1.1.8 root 2512: {
2513: if (basic_induction_var (SET_SRC (PATTERN (p)), dest_regno,
2514: &inc_val, &mult_val))
2515: {
2516: /* It is a possible basic induction variable.
2517: Create and initialize an induction structure for it. */
2518:
2519: struct induction *v =
2520: (struct induction *) alloca (sizeof (struct induction));
2521:
2522: v->insn = p;
2523: v->src_regno = dest_regno;
2524: v->dest_regno = dest_regno;
2525: v->mult_val = mult_val;
2526: v->add_val = inc_val;
1.1.1.14 root 2527: v->mode = GET_MODE (SET_DEST (PATTERN (p)));
1.1.1.8 root 2528:
2529: /* Add this to the reg's iv_class, creating a class
2530: if this is the first incrementation of the reg. */
2531:
2532: bl = class_struct[dest_regno];
2533: if (bl)
2534: {
2535: v->family = bl->biv;
2536: bl->biv = v;
2537: bl->biv_count++;
2538: }
2539: else
2540: {
2541: /* Create and initialize new iv_class. */
2542:
2543: bl = (struct iv_class *) alloca (sizeof (struct iv_class));
2544:
2545: bl->regno = dest_regno;
2546: bl->biv = v;
2547: v->family = 0;
2548: bl->giv = 0;
2549: bl->biv_count = 1;
2550: bl->giv_count = 0;
2551:
2552: /* Set initial value to the reg itself. */
2553: bl->initial_value = SET_DEST (PATTERN (p));
1.1.1.14 root 2554: /* We haven't seen the intializing insn yet */
2555: bl->init_insn = 0;
1.1.1.8 root 2556: bl->eliminable = 0;
2557: bl->nonneg = 0;
2558:
2559: /* Add this insn to iv_list. */
2560: bl->next = iv_list;
2561: iv_list = bl;
2562:
2563: /* Put it in the array of iv_lists. */
2564: class_struct[dest_regno] = bl;
2565: }
2566:
2567: induct_var[dest_regno] = BASIC_INDUCT;
2568:
2569: if (loop_dump_stream)
2570: {
2571: fprintf (loop_dump_stream,
2572: "Insn %d: possible biv, reg %d,",
2573: INSN_UID (p), dest_regno);
2574: if (GET_CODE (inc_val) == CONST_INT)
2575: fprintf (loop_dump_stream, " const = %d\n",
2576: INTVAL (inc_val));
2577: else
2578: {
2579: fprintf (loop_dump_stream, " const = ");
2580: print_rtl (loop_dump_stream, inc_val);
2581: fprintf (loop_dump_stream, "\n");
2582: }
2583: }
2584: }
2585: else
2586: induct_var[dest_regno] = NOT_BASIC_INDUCT;
2587: }
2588: }
2589: }
2590:
2591: /* Scan iv_list to remove all regs that proved not to be bivs.
2592: Make a sanity check against n_times_set. */
2593:
2594: biv_found = 0;
2595:
2596: for (backbl = bl = iv_list; bl; backbl = bl, bl = bl->next)
2597: {
2598: if (induct_var[bl->regno] != BASIC_INDUCT)
2599: {
2600: /* Not a basic induction variable, remove this iv_class. */
2601:
2602: if (backbl == bl)
2603: iv_list = bl->next;
2604: else
2605: backbl->next = bl->next;
2606:
2607: if (loop_dump_stream)
2608: fprintf (loop_dump_stream, "Reg %d: biv discarded, not induct\n",
2609: bl->regno);
2610: }
2611: else if (n_times_set[bl->regno] != bl->biv_count)
2612: {
2613: /* This happens if register modified by subreg, etc. */
2614: /* Make sure it is not recognized as a basic induction var: */
2615: /* remove this iv_class from iv_list. */
2616:
2617: induct_var[bl->regno] = NOT_BASIC_INDUCT;
2618:
2619: if (backbl == bl)
2620: iv_list = bl->next;
2621: else
2622: backbl->next = bl->next;
2623:
2624: if (loop_dump_stream)
2625: fprintf (loop_dump_stream, "Reg %d: biv discarded, count error\n",
2626: bl->regno);
2627: }
2628: else
2629: {
2630: /* This is a valid basic induction variable. */
2631:
2632: biv_found++;
2633:
2634: if (loop_dump_stream)
2635: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
2636: }
2637: }
2638:
2639: /* Exit if there are no bivs. */
2640: if (!iv_list)
2641: return;
2642:
2643: /* Find initial value for each biv. */
2644: /* Search backwards from loop_start, halting at first label
2645: or when all bivs have been seen. */
2646:
1.1.1.15 root 2647: call_seen = 0;
1.1.1.8 root 2648: p = loop_start;
2649: while (biv_found)
2650: {
2651: p = PREV_INSN (p);
2652: if (p == 0)
2653: break;
2654:
1.1.1.15 root 2655: if (GET_CODE (p) == CALL_INSN)
2656: call_seen = 1;
2657:
1.1.1.8 root 2658: if (GET_CODE (p) == INSN
1.1.1.16 root 2659: && GET_CODE (PATTERN (p)) == SET)
1.1.1.8 root 2660: {
1.1.1.16 root 2661: rtx dest = SET_DEST (PATTERN (p));
1.1.1.8 root 2662:
1.1.1.16 root 2663: while (GET_CODE (dest) == SUBREG
2664: || GET_CODE (dest) == ZERO_EXTRACT
2665: || GET_CODE (dest) == SIGN_EXTRACT
2666: || GET_CODE (dest) == STRICT_LOW_PART)
2667: dest = XEXP (dest, 0);
1.1.1.8 root 2668:
1.1.1.16 root 2669: if (GET_CODE (dest) == REG)
2670: {
2671: int dest_regno = REGNO (dest);
2672: if (induct_var[dest_regno] == BASIC_INDUCT
2673: && class_struct[dest_regno]->init_insn == 0)
2674: {
2675: /* This is the first modification found for this reg. */
1.1.1.15 root 2676:
1.1.1.16 root 2677: rtx src = SET_SRC (PATTERN (p));
1.1.1.14 root 2678:
1.1.1.16 root 2679: /* Record the intializing INSN */
1.1.1.14 root 2680:
1.1.1.16 root 2681: class_struct[dest_regno]->init_insn = p;
1.1.1.14 root 2682:
1.1.1.8 root 2683: if (loop_dump_stream)
1.1.1.16 root 2684: fprintf (loop_dump_stream, "Biv %d initialized at insn %d: ",
2685: dest_regno, INSN_UID (p));
2686:
2687: /* Save value if it is a constant or register. */
2688: if (CONSTANT_P (src)
2689: || (GET_CODE (src) == REG
2690: /* Don't try to use a value in a hard reg
2691: across a call which clobbers it. */
2692: && ! (REGNO (src) < FIRST_PSEUDO_REGISTER
2693: && call_used_regs[REGNO (src)]
2694: && call_seen)
2695: && ! reg_set_between_p (src, p, loop_start)))
1.1.1.8 root 2696: {
1.1.1.16 root 2697: class_struct[dest_regno]->initial_value = src;
2698:
2699: if (loop_dump_stream)
2700: fprintf (loop_dump_stream, "initial value ");
2701: if (loop_dump_stream)
1.1.1.14 root 2702: {
1.1.1.16 root 2703: if (GET_CODE (src) == CONST_INT)
2704: fprintf (loop_dump_stream, "%d\n", INTVAL (src));
2705: else
2706: {
2707: print_rtl (loop_dump_stream, src);
2708: fprintf (loop_dump_stream, "\n");
2709: }
1.1.1.14 root 2710: }
1.1.1.8 root 2711: }
1.1.1.16 root 2712: else
2713: {
2714: /* Biv initial value is not simple move,
2715: so let it keep intial value of "itself". */
1.1.1.8 root 2716:
1.1.1.16 root 2717: if (loop_dump_stream)
2718: fprintf (loop_dump_stream, "complex initial value\n");
2719: }
1.1.1.8 root 2720:
1.1.1.16 root 2721: biv_found--;
2722: }
1.1.1.8 root 2723: }
2724: }
2725: else if (GET_CODE (p) == CODE_LABEL)
2726: break;
2727: }
2728:
2729: /* Search the loop for general induction variables. */
2730:
2731: /* A register is a giv if: it is only set once, it is a function of a
2732: biv and a constant (or invariant), and it is not a biv. */
2733:
2734: p = scan_start;
2735: while (1)
2736: {
2737: p = NEXT_INSN (p);
2738: /* At end of a straight-in loop, we are done.
2739: At end of a loop entered at the bottom, scan the top. */
2740: if (p == scan_start)
2741: break;
2742: if (p == end)
2743: {
2744: if (loop_top != 0)
2745: p = NEXT_INSN (loop_top);
2746: else
2747: break;
2748: if (p == scan_start)
2749: break;
2750: }
2751:
2752: /* Look for a general induction variable in a register. */
2753: if (GET_CODE (p) == INSN
2754: && GET_CODE (PATTERN (p)) == SET
1.1.1.17 root 2755: && GET_CODE (SET_DEST (PATTERN (p))) == REG
2756: && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))])
1.1.1.8 root 2757: {
2758: int src_regno;
2759: rtx add_val;
2760: rtx mult_val;
2761: int benefit;
2762: rtx regnote = 0;
2763: struct induction *forces = 0;
2764: struct induction *forces2 = 0;
2765:
2766: dest_regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.15 root 2767: if (dest_regno < FIRST_PSEUDO_REGISTER)
2768: continue;
1.1.1.8 root 2769:
2770: if (/* Normal giv. */
2771: ((benefit = general_induction_var (SET_SRC (PATTERN (p)),
2772: &src_regno, &add_val,
2773: &mult_val,
2774: &forces, &forces2))
2775: /* Giv set with call to a library routine. */
1.1.1.17 root 2776: || ((regnote = loop_find_reg_equal (p))
1.1.1.8 root 2777: &&
2778: (benefit = general_induction_var (XEXP (regnote, 0),
2779: &src_regno,
2780: &add_val, &mult_val,
2781: &forces, &forces2))))
1.1.1.11 root 2782: /* Don't try to handle any regs made by loop optimization.
2783: We have nothing on them in regno_first_uid, etc. */
2784: && dest_regno < old_max_reg
1.1.1.8 root 2785: /* Don't recognize a BASIC_INDUCT_VAR here. */
2786: && dest_regno != src_regno
2787: /* This must be the only place where the register is set. */
2788: && (n_times_set[dest_regno] == 1
2789: || (benefit = consec_sets_giv (benefit, p,
2790: src_regno, dest_regno,
2791: &add_val, &mult_val))))
2792: {
2793: int count;
2794: struct induction *v =
2795: (struct induction *) alloca (sizeof (struct induction));
2796: rtx temp;
2797:
2798: record_giv (v, p, src_regno, dest_regno, mult_val, add_val, benefit,
1.1.1.14 root 2799: forces, forces2, DEST_REG, maybe_never, 0, loop_end);
1.1.1.8 root 2800:
2801: /* Skip the consecutive insns, if there are any. */
2802: for (count = v->consec - 1; count >= 0; count--)
2803: {
2804: /* If first insn of libcall sequence, skip to end. */
2805: /* Do this at start of loop, since INSN is guaranteed to
2806: be an insn here. */
2807: if (temp = find_reg_note (p, REG_LIBCALL, 0))
2808: {
2809: /* Eliminating a libcall does more good than
2810: eliminating a single insn to do the same job. */
2811: benefit += LIBCALL_BENEFIT;
2812: p = XEXP (temp, 0);
2813: }
2814:
2815: do p = NEXT_INSN (p);
2816: while (GET_CODE (p) == NOTE);
2817: }
2818: }
2819: }
2820:
2821: #ifndef DONT_REDUCE_ADDR
2822: /* Look for givs which are memory addresses. */
2823: /* This resulted in worse code on a VAX 8600. I wonder if it
2824: still does. */
2825: if (GET_CODE (p) == INSN)
1.1.1.14 root 2826: find_mem_givs (PATTERN (p), p, maybe_never, loop_end);
1.1.1.8 root 2827: #endif
2828:
2829: /* Past a label or a jump, we get to insns for which we can't count
2830: on whether or how many times they will be executed during each
2831: iteration. Givs found afterwards cannot be marked replaceable. */
2832: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
2833: maybe_never = 1;
2834: }
2835:
2836: /* Try to prove that the loop counter variable (if any) is always
2837: nonnegative; if so, record that fact with a REG_NONNEG note
2838: so that "decrement and branch until zero" insn can be used. */
2839: check_dbra_loop (loop_end, iv_list, insn_count, loop_start);
2840:
2841: /* Create reg_map to hold substitutions for replaceable giv regs. */
2842: reg_map = (rtx *) alloca (nregs * sizeof (rtx));
2843: bzero ((char *)reg_map, nregs * sizeof (rtx));
2844:
2845: /* Examine each iv class for feasibility of strength reduction/induction
2846: variable elimination. */
2847:
2848: for (bl = iv_list; bl; bl = bl->next)
2849: {
2850: struct induction *v;
2851: int benefit;
2852: int replaceable;
2853: int all_reduced;
2854: rtx final_value = 0;
2855:
2856: /* Test whether it will be possible to eliminate this biv
1.1.1.10 root 2857: provided all givs are reduced. This is possible if either
2858: the reg is not used outside the loop, or we can compute
2859: what its final value will be.
1.1.1.8 root 2860:
2861: Don't try if we put a REG_NONNEG note on the endtest for this biv.
2862: ??? That should be only on machines that have dbra insns. */
2863:
1.1.1.14 root 2864: /* Compare against bl->init_insn rather than loop_start.
2865: We aren't concerned with any uses of the biv between
2866: init_insn and loop_start since these won't be affected
2867: by the value of the biv elsewhere in the function, so
2868: long as init_insn doesn't use the biv itself.
2869: March 14, 1989 -- [email protected] */
2870:
1.1.1.8 root 2871: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
1.1.1.14 root 2872: && bl->init_insn
1.1.1.16 root 2873: && INSN_UID (bl->init_insn) < max_uid
1.1.1.14 root 2874: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
2875: && ! reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)),
2876: SET_SRC (PATTERN (bl->init_insn)))
2877: && ! bl->nonneg)
1.1.1.8 root 2878: || (final_value = final_biv_value (bl, loop_end)))
1.1.1.15 root 2879: check_eliminate_biv (bl, loop_start, end);
1.1.1.8 root 2880: else
2881: {
2882: if (loop_dump_stream)
1.1.1.14 root 2883: {
2884: fprintf (loop_dump_stream,
2885: "Cannot eliminate biv %d.\n",
2886: bl->regno);
2887: fprintf (loop_dump_stream,
2888: "First use: insn %d, last use: insn %d.\n",
2889: regno_first_uid[bl->regno],
2890: regno_last_uid[bl->regno]);
2891: }
1.1.1.8 root 2892: }
2893:
2894: /* This will be true at the end, if all givs which depend on this
2895: biv have been strength reduced.
2896: We can't (currently) eliminate the biv unless this is so. */
2897: all_reduced = 1;
2898:
2899: /* Check each giv in this class. */
2900:
2901: for (v = bl->giv; v; v = v->family)
2902: {
2903: struct induction *tv;
2904:
2905: if (v->ignore)
2906: continue;
2907:
2908: benefit = v->benefit;
2909: replaceable = v->replaceable;
2910:
2911: /* Reduce benefit if not replaceable, since we will insert
2912: a move-insn to replace the insn that calculates this giv. */
2913: if (!replaceable && ! bl->eliminable)
2914: benefit -= COPY_PENALTY;
2915:
2916: /* Decrease the benefit to count the add-insns that we will
2917: insert to increment the reduced reg for the giv. */
2918: benefit -= ADD_BENEFIT * bl->biv_count;
2919:
2920: /* Find all equivalent givs (that bear same relation to the biv).
2921: Link them via the `same' field and add their benefits together.
2922: They can be replaced with a single register. */
2923:
2924: for (tv = v->family; tv; tv = tv->family)
2925: {
2926: if (tv->ignore == 0
2927: && tv->src_regno == v->src_regno
2928: && rtx_equal_p (tv->mult_val, v->mult_val)
2929: && rtx_equal_p (tv->add_val, v->add_val))
2930: {
2931: benefit += tv->benefit;
2932: if (! tv->replaceable)
2933: benefit -= COPY_PENALTY;
2934: v->lifetime += tv->lifetime;
2935: v->times_used += tv->times_used;
2936: tv->ignore = 1;
2937:
2938: /* Link them together via `same' field. */
2939: tv->same = v->same;
2940: v->same = tv;
2941:
2942: if (loop_dump_stream)
2943: fprintf (loop_dump_stream,
2944: "giv of insn %d combined with that of %d.\n",
2945: INSN_UID (v->insn), INSN_UID (tv->insn));
2946: }
2947: }
2948:
2949: /* Decide whether to strength-reduce this giv
2950: or to leave the code unchanged
2951: (recompute it from the biv each time it is used).
2952: This decision can be made independently for each giv. */
2953:
2954: /* ??? Perhaps attempt to guess whether autoincrement will handle
2955: some of the new add insns; if so, can increase BENEFIT
2956: (undo the subtraction of ADD_BENEFIT that was done above). */
2957:
1.1.1.14 root 2958: /* If an insn is not to be strength reduced, then set its ignore
2959: flag, and clear all_reduced. */
2960:
1.1.1.8 root 2961: /* Is it right to consider times_used? */
2962:
1.1.1.14 root 2963: /* ??? What about the insns that are 'forced' by this one?
2964: Although this insn is not worthwhile to reduce, it may be
2965: worthwhile to reduce the simpler givs used to compute this
2966: complex giv. */
2967:
2968: /* ??? Hey! If a giv has its forces field set, then that means
2969: it is not computed directly from the biv, it is instead computed
2970: from a simpler giv. If we define UNFORCE_INSNS, then the simpler
2971: giv will be considered for strength reduction, and this giv should
2972: not cause all_reduced to be cleared because it DOESN'T use the
2973: biv!!! If the simpler giv can not be reduced, then that simpler
2974: biv will still cause all_reduced to be cleared. */
2975:
1.1.1.8 root 2976: if (benefit <= 0)
2977: {
2978: if (loop_dump_stream)
2979: fprintf (loop_dump_stream, "giv of insn %d, no benefit\n",
2980: INSN_UID (v->insn));
2981: v->ignore = 1;
1.1.1.14 root 2982: all_reduced = 0;
1.1.1.8 root 2983: }
2984:
2985: if (v->lifetime * threshold * benefit < insn_count)
2986: {
2987: if (loop_dump_stream)
2988: fprintf (loop_dump_stream,
2989: "giv of insn %d not worth while, %d vs %d.\n",
2990: INSN_UID (v->insn),
2991: v->lifetime * threshold * benefit, insn_count);
2992: v->ignore = 1;
1.1.1.14 root 2993: all_reduced = 0;
1.1.1.8 root 2994: }
2995:
2996: /* Now check that we can increment the reduced giv
2997: without needing a multiply insn. If not, reject it. */
2998:
2999: if (! v->ignore)
3000: {
3001: int success = 1;
3002:
3003: for (tv = bl->biv; tv; tv = tv->family)
3004: if (tv->mult_val == const1_rtx)
3005: success &= product_cheap_p (tv->add_val, v->mult_val);
3006:
3007: if (! success)
3008: {
3009: if (loop_dump_stream)
3010: fprintf (loop_dump_stream,
3011: "giv of insn %d: would need a multiply.\n",
3012: INSN_UID (v->insn));
3013: v->ignore = 1;
1.1.1.14 root 3014: all_reduced = 0;
1.1.1.8 root 3015: }
3016: }
3017: }
3018:
3019: /* Reduce each giv that we decided to reduce. */
3020:
3021: for (v = bl->giv; v; v = v->family)
3022: {
3023: struct induction *tv;
3024: if (! v->ignore)
3025: {
1.1.1.11 root 3026: rtx new_reg;
3027:
3028: /* Note Iris compiler dies if ?: is used inside gen_reg_rtx. */
3029: if (v->giv_type == DEST_ADDR)
3030: new_reg = gen_reg_rtx (Pmode);
3031: else
3032: new_reg = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (v->insn))));
1.1.1.8 root 3033:
3034: /* For each place where the biv is incremented,
3035: add an insn to increment the new, reduced reg for the giv.
3036: Insert it before the insn that sets the biv,
3037: so that the biv increment remains last before the endtest,
3038: so that dbra will still be recognized. */
3039:
3040: for (tv = bl->biv; tv; tv = tv->family)
3041: {
1.1.1.14 root 3042: struct induction *iv;
3043: rtx before_insn = tv->insn;
3044:
3045: /* If this increment is between the setting of the giv and
3046: its use, don't increment until after the use. */
3047: for (iv = v; iv; iv = iv->same)
3048: {
3049: if (INSN_LUID (tv->insn) <= INSN_LUID (iv->insn)
3050: && ((iv->forces
3051: && (INSN_LUID (tv->insn)
3052: >= INSN_LUID (iv->forces->insn))
3053: || (iv->forces2
3054: && (INSN_LUID (tv->insn)
3055: >= INSN_LUID (iv->forces2->insn))))))
3056: {
3057: before_insn = NEXT_INSN (iv->insn);
3058: break;
3059: }
3060: }
3061:
1.1.1.8 root 3062: if (tv->mult_val == const1_rtx)
3063: emit_iv_inc (tv->add_val, v->mult_val,
1.1.1.14 root 3064: new_reg, before_insn);
1.1.1.8 root 3065: else /* tv->mult_val == const0_rtx */
3066: /* A multiply is acceptable here
3067: since this is presumed to be seldom executed. */
3068: emit_iv_init_code (tv->add_val, v->mult_val,
1.1.1.14 root 3069: v->add_val, new_reg, before_insn);
1.1.1.8 root 3070: }
3071:
3072: /* Add code at loop start to initialize giv's reduced reg. */
3073:
3074: emit_iv_init_code (bl->initial_value, v->mult_val,
3075: v->add_val, new_reg, loop_start);
1.1.1.16 root 3076: /* If the initial value uses a register,
3077: then we may have just extended its range of appearance.
3078: Update this conservatively for the sake of outer loops. */
3079: if (GET_CODE (bl->initial_value) == REG
3080: && (uid_luid[regno_last_uid[REGNO (bl->initial_value)]]
3081: < INSN_LUID (loop_start)))
3082: uid_luid[regno_last_uid[REGNO (bl->initial_value)]]
3083: = INSN_LUID (loop_start);
1.1.1.8 root 3084:
3085: /* For each giv register that can be reduced now:
3086: delete old insn that modifies the giv,
3087: if replaceable, substitute reduced reg
3088: wherever the old giv occurs;
3089: else add new move insn "giv_reg = reduced_reg". */
3090:
3091: for (tv = v; tv; tv = tv->same)
3092: {
3093: /* Record the identity of the reduced reg. */
3094: tv->new_reg = new_reg;
3095:
3096: if (tv->giv_type == DEST_ADDR)
3097: {
3098: /* Store reduced reg as the address in the memref
3099: where we found this giv. */
3100: * tv->location = new_reg;
3101: }
3102: else if (tv->replaceable)
3103: {
3104: reg_map[tv->dest_regno] = new_reg;
3105: /* If giv lives after end of loop,
3106: emit insn to copy reduced reg into old reg,
1.1.1.14 root 3107: at the end of the loop.
3108: ?? insufficient; used before loop could
3109: mean live after loop, due to surrounding loop. */
3110: /* Currently a giv used outside
3111: the loop will not be marked replaceable,
3112: so these deficiencies don't really hurt. */
1.1.1.8 root 3113: if (uid_luid[regno_last_uid[tv->dest_regno]]
3114: > uid_luid[INSN_UID (loop_end)])
1.1.1.14 root 3115: {
3116: /* ?? This won't work. We need to do this at
3117: ALL exits. */
3118: emit_insn_after (gen_rtx (SET, VOIDmode,
3119: SET_DEST (PATTERN (tv->insn)),
3120: new_reg),
3121: loop_end);
3122: abort ();
3123: }
1.1.1.8 root 3124: }
3125: else
3126: {
1.1.1.14 root 3127: /* Not replaceable; emit an insn to set the
3128: original giv reg from the reduced giv. */
3129:
3130: int count;
3131: rtx after_insn = tv->insn;
3132:
3133: for (count = tv->consec; count > 0; count--)
3134: after_insn = next_real_insn (after_insn);
3135:
1.1.1.11 root 3136: /* Put new insn after, not before, in case
1.1.1.14 root 3137: after_insn is the end of a libcall. */
1.1.1.11 root 3138: emit_insn_after (gen_rtx (SET, VOIDmode,
1.1.1.8 root 3139: SET_DEST (PATTERN (tv->insn)),
3140: new_reg),
1.1.1.14 root 3141: after_insn);
1.1.1.8 root 3142: }
3143:
3144: /* Delete the insn that used to set the old giv reg,
3145: unless we modified an address in it.
3146: In any case, delete the other insns used for this one. */
3147: delete_insn_forces (tv, tv->giv_type != DEST_ADDR);
3148:
3149: if (loop_dump_stream)
3150: fprintf (loop_dump_stream, "giv at %d reduced to reg %d\n",
3151: INSN_UID (tv->insn), REGNO (new_reg));
3152: }
3153: /* One set of equivalent givs has been strength-reduced. */
3154: }
1.1.1.14 root 3155: #if 0
1.1.1.8 root 3156: else if (v->new_reg == 0)
3157: {
3158: /* This giv wasn't reduced and is not worth reducing. */
3159:
3160: for (tv = v; tv; tv = tv->same)
3161: if (loop_dump_stream)
3162: fprintf (loop_dump_stream, "giv at %d not reduced\n",
3163: INSN_UID (tv->insn));
3164:
3165: all_reduced = 0;
3166: }
1.1.1.14 root 3167: #endif
1.1.1.8 root 3168: }
3169:
3170: /* All the givs in this family have been reduced if they merit it. */
3171:
3172: /* Try to eliminate the biv, if it is a candidate.
3173: This won't work if ! all_reduced,
3174: since the givs we planned to use might not have been reduced. */
3175:
3176: if (all_reduced == 1 && bl->eliminable)
3177: {
3178: /* Get the REG rtx for the biv. */
3179: rtx reg = SET_DEST (PATTERN (bl->biv->insn));
3180:
3181: for (p = loop_start; p != end; p = NEXT_INSN (p))
3182: {
3183: enum rtx_code code = GET_CODE (p);
3184: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
3185: && reg_mentioned_p (reg, PATTERN (p))
3186: && SET_DEST (PATTERN (p)) == cc0_rtx)
3187: /* Found a compare instruction using this biv;
3188: rewrite it to use a related giv. */
1.1.1.16 root 3189: {
3190: struct induction *v1;
3191: /* If this is an insn which uses the biv ONLY in the
3192: calculation of a giv which is in the family of this
3193: biv, it's ok becuase it will go away when the giv is
3194: reduced. */
3195: for (v1 = bl->giv; v1; v1 = v1->family)
3196: if (v1->insn == p)
3197: {
3198: if (v1->giv_type == DEST_REG
3199: || (v1->giv_type == DEST_ADDR
1.1.1.17 root 3200: /* I thought the test was backwards,
3201: but then I found the real problem
3202: was in the subroutine. */
3203: && ! other_reg_use_p (reg, *(v1->location),
3204: PATTERN (p))))
1.1.1.16 root 3205: break;
3206: }
3207: if (!v1)
3208: eliminate_biv (p, bl, loop_start);
3209: }
1.1.1.8 root 3210: }
3211:
3212: /* Biv is no longer really needed inside the loop,
3213: so delete all insns that set the biv. */
3214:
3215: for (v = bl->biv; v; v = v->family)
3216: delete_insn (v->insn);
3217:
1.1.1.14 root 3218: /* ?? If we created a new test to bypass the loop entirely,
3219: or otherwise drop straight in, based on this test, then
3220: we might want to rewrite it also. This way some later
3221: pass has more hope of removing the intialization of this
3222: biv entirely. */
3223:
1.1.1.8 root 3224: /* If final_value != 0, then biv may be used after loop end
3225: and we must emit an insn to set it just in case. */
3226: if (final_value != 0)
3227: emit_insn_after (gen_rtx (SET, VOIDmode, reg, final_value),
3228: loop_end);
3229:
3230: if (loop_dump_stream)
3231: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
3232: bl->regno);
3233: }
3234: }
3235:
3236: /* Go through all the instructions in the loop, making all the
3237: register substitutions scheduled in REG_MAP. */
3238:
3239: for (p = loop_start; p != end; p = NEXT_INSN (p))
3240: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3241: || GET_CODE (p) == CALL_INSN)
1.1.1.19! root 3242: {
! 3243: rtx tail;
! 3244:
! 3245: replace_regs (PATTERN (p), reg_map, nregs);
! 3246: /* Subsitute registers in the equivalent expression also. */
! 3247: for (tail = REG_NOTES (p); tail; tail = XEXP (tail, 1))
! 3248: if (REG_NOTE_KIND (tail) == REG_EQUAL
! 3249: || REG_NOTE_KIND (tail) == REG_EQUIV)
! 3250: replace_regs (XEXP (tail, 0), reg_map, nregs);
! 3251: }
1.1.1.14 root 3252:
3253: if (loop_dump_stream)
3254: fprintf (loop_dump_stream, "\n");
3255: }
3256:
1.1.1.17 root 3257: /* Nonzero if register REG appears somewhere within IN, other than in
1.1.1.14 root 3258: subexpressions EQ to EXPR. This is a modification of reg_mentioned_p. */
3259:
3260: int
1.1.1.17 root 3261: other_reg_use_p (reg, expr, in)
1.1.1.14 root 3262: register rtx reg, expr, in;
3263: {
3264: register char *fmt;
3265: register int i;
3266: register enum rtx_code code;
3267:
1.1.1.17 root 3268: if (in == 0 || in == expr)
1.1.1.14 root 3269: return 0;
3270:
3271: if (reg == in)
3272: return 1;
3273:
3274: code = GET_CODE (in);
3275:
3276: switch (code)
3277: {
3278: /* Compare registers by number. */
3279: case REG:
3280: return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
3281:
3282: /* These codes have no constituent expressions
3283: and are unique. */
3284: case CC0:
3285: case PC:
3286: case CONST_INT:
3287: case CONST_DOUBLE:
3288: case SYMBOL_REF:
3289: case CODE_LABEL:
3290: return 0;
3291: }
3292:
3293: fmt = GET_RTX_FORMAT (code);
3294:
3295: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3296: {
3297: if (fmt[i] == 'E')
3298: {
3299: register int j;
3300: for (j = XVECLEN (in, i) - 1; j >= 0; j--)
1.1.1.17 root 3301: if (other_reg_use_p (reg, expr, XVECEXP (in, i, j)))
1.1.1.14 root 3302: return 1;
3303: }
3304: else if (fmt[i] == 'e'
1.1.1.17 root 3305: && other_reg_use_p (reg, expr, XEXP (in, i)))
1.1.1.14 root 3306: return 1;
3307: }
3308: return 0;
1.1.1.8 root 3309: }
3310:
3311: /* Scan X for memory refs and check each memory address
3312: as a possible giv. INSN is the insn whose pattern X comes from.
3313: MAYBE_NEVER is 1 if the loop might execute INSN zero times. */
3314:
3315: static void
1.1.1.14 root 3316: find_mem_givs (x, insn, maybe_never, loop_end)
1.1.1.8 root 3317: rtx x;
3318: rtx insn;
3319: int maybe_never;
1.1.1.14 root 3320: rtx loop_end;
1.1.1.8 root 3321: {
3322: register int i, j;
3323: register enum rtx_code code;
3324: register char *fmt;
3325:
3326: if (x == 0)
3327: return;
3328:
3329: code = GET_CODE (x);
3330: switch (code)
3331: {
3332: case REG:
3333: case CONST_INT:
3334: case CONST:
3335: case CONST_DOUBLE:
3336: case SYMBOL_REF:
3337: case LABEL_REF:
3338: case PC:
3339: case CC0:
3340: case ADDR_VEC:
3341: case ADDR_DIFF_VEC:
3342: case USE:
3343: case CLOBBER:
3344: return;
3345:
3346: case MEM:
3347: {
3348: int src_regno;
3349: rtx add_val;
3350: rtx mult_val;
3351: int benefit;
3352: struct induction *forces = 0;
3353: struct induction *forces2 = 0;
3354:
3355: benefit = general_induction_var (XEXP (x, 0),
3356: &src_regno, &add_val, &mult_val,
3357: &forces, &forces2);
3358: if (benefit > 0)
3359: {
3360: /* Found one; record it. */
3361: struct induction *v =
3362: (struct induction *) oballoc (sizeof (struct induction));
3363:
3364: record_giv (v, insn, src_regno, 0, mult_val, add_val, benefit,
1.1.1.14 root 3365: forces, forces2, DEST_ADDR, maybe_never, &XEXP (x, 0),
3366: loop_end);
1.1.1.8 root 3367: }
3368: return;
3369: }
3370: }
3371:
3372: /* Recursively scan the subexpressions for other mem refs. */
3373:
3374: fmt = GET_RTX_FORMAT (code);
3375: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3376: if (fmt[i] == 'e')
1.1.1.14 root 3377: find_mem_givs (XEXP (x, i), insn, maybe_never, loop_end);
1.1.1.8 root 3378: else if (fmt[i] == 'E')
3379: for (j = 0; j < XVECLEN (x, i); j++)
1.1.1.14 root 3380: find_mem_givs (XVECEXP (x, i, j), insn, maybe_never, loop_end);
1.1.1.8 root 3381: }
3382:
3383: /* Fill in the data about one giv.
3384: V is the `struct induction' in which we record the giv. (It is
3385: allocated by the caller, with alloca.)
3386: INSN is the insn that sets it.
3387: BENEFIT estimates the savings from deleting this insn.
3388: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
3389: into a register or is used as a memory address.
3390:
3391: SRC_REGNO is the biv reg number which the giv is computed from.
3392: DEST_REGNO is the giv's reg number (if the giv is stored in a reg).
3393: MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
3394: FORCES and FORCES2, if nonzero, are other `struct induction's for
3395: other givs which are used to compute this giv indirectly.
3396: LOCATION points to the place where this giv's value appears in INSN. */
3397:
3398: static void
3399: record_giv (v, insn, src_regno, dest_regno, mult_val, add_val, benefit,
1.1.1.14 root 3400: forces, forces2, type, maybe_never, location, loop_end)
1.1.1.8 root 3401: struct induction *v;
3402: rtx insn;
3403: int src_regno, dest_regno;
3404: rtx mult_val, add_val;
3405: int benefit;
3406: struct induction *forces, *forces2;
3407: enum g_types type;
3408: int maybe_never;
3409: rtx *location;
1.1.1.14 root 3410: rtx loop_end;
1.1.1.8 root 3411: {
3412: struct induction *b;
3413: struct iv_class *bl;
3414:
3415: v->insn = insn;
3416: v->src_regno = src_regno;
3417: v->giv_type = type;
3418: v->dest_regno = dest_regno;
3419: v->mult_val = mult_val;
3420: v->add_val = add_val;
3421: v->benefit = benefit;
3422: v->location = location;
3423:
3424: if (type == DEST_ADDR)
3425: {
1.1.1.14 root 3426: v->mode = GET_MODE (*location);
1.1.1.8 root 3427: v->consec = 0;
3428: v->lifetime = 1;
3429: v->times_used = 1;
3430: }
1.1.1.14 root 3431: else /* type == DEST_REG */
1.1.1.8 root 3432: {
1.1.1.14 root 3433: v->mode = GET_MODE (SET_DEST (PATTERN (insn)));
1.1.1.8 root 3434: v->consec = n_times_set[dest_regno] - 1;
3435: v->lifetime = (uid_luid[regno_last_uid[dest_regno]]
3436: - uid_luid[regno_first_uid[dest_regno]]);
3437: v->times_used = n_times_used[dest_regno];
3438: }
3439:
3440: v->same = 0;
3441: v->forces = 0;
3442: v->forces2 = 0;
3443: v->ignore = 0;
3444: v->new_reg = 0;
3445:
3446: /* Mark giv as forced if it is only used to compute another giv. */
3447:
3448: /* This check is not sufficient as INSN may have been moved giving
3449: it a new uid, so make another check by calculating lifetimes.
3450: This is overconservative but seems to be correct. */
3451:
3452: if (forces)
3453: {
3454: v->benefit += forces->benefit;
3455: if ((regno_last_uid[forces->dest_regno] == INSN_UID (insn)
3456: ||
3457: ((uid_luid[regno_last_uid[forces->dest_regno]]
3458: - uid_luid[regno_first_uid[forces->dest_regno]])
1.1.1.15 root 3459: == (INSN_LUID (insn) - INSN_LUID (forces->insn))))
1.1.1.8 root 3460: && !reg_used_between_p (SET_DEST (PATTERN (forces->insn)),
3461: forces->insn, insn))
3462: {
3463: v->forces = forces;
3464: forces->ignore = 1;
3465: }
3466: }
3467:
3468: if (forces2)
3469: {
3470: v->benefit += forces2->benefit;
3471: if ((regno_last_uid[forces2->dest_regno] == INSN_UID (insn)
3472: ||
3473: ((uid_luid[regno_last_uid[forces2->dest_regno]]
3474: - uid_luid[regno_first_uid[forces2->dest_regno]])
1.1.1.15 root 3475: == (INSN_LUID (insn) - INSN_LUID (forces2->insn))))
1.1.1.8 root 3476: && !reg_used_between_p (SET_DEST (PATTERN (forces2->insn)),
3477: forces2->insn, insn))
3478: {
3479: if (v->forces)
3480: v->forces2 = forces2;
3481: else
3482: v->forces = forces2;
3483: forces2->ignore = 1;
3484: }
3485: }
3486:
3487: if (type == DEST_REG)
3488: {
3489: induct_var[dest_regno] = GENERAL_INDUCT;
3490: induct_struct[dest_regno] = v;
3491: }
3492:
3493: /* Add the giv to the class of givs computed from one biv. */
3494:
3495: bl = class_struct[src_regno];
3496: if (bl)
3497: {
3498: v->family = bl->giv;
3499: bl->giv = v;
1.1.1.14 root 3500: /* Don't count DEST_ADDR. This is supposed to count the number of
3501: insns that calculate givs. */
3502: if (type == DEST_REG)
3503: bl->giv_count++;
1.1.1.8 root 3504: bl->total_benefit += benefit;
3505: }
3506: else
1.1.1.15 root 3507: /* Fatal error, biv missing for this giv? */
3508: abort ();
1.1.1.8 root 3509:
3510: if (type == DEST_ADDR)
3511: v->replaceable = 1;
3512: else
3513: {
3514: /* The giv can be replaced outright by the reduced register if
1.1.1.11 root 3515: - the insn that sets the giv is always executed on any iteration
3516: on which the giv is used at all
3517: (there are two ways to deduce this:
3518: either the insn is executed on every iteration,
3519: or all uses follow that insn in the same basic block),
1.1.1.8 root 3520: - the giv is not used before the insn that sets it,
3521: i.e. no definition outside loop reaches into loop
3522: - no assignments to the biv occur during the giv's lifetime. */
3523:
1.1.1.14 root 3524: /* Is this right? Don't we need to make sure the giv is not used
3525: outside the loop. Someday we will know where all the loop exits
3526: are so we can do better, but until then....
3527: March 18, 1989 -- [email protected] */
3528:
1.1.1.11 root 3529: if (regno_first_uid[dest_regno] == INSN_UID (insn)
3530: /* Previous line always fails if INSN was moved by loop opt. */
1.1.1.14 root 3531: && uid_luid[regno_last_uid[dest_regno]] < INSN_LUID (loop_end)
1.1.1.11 root 3532: && (!maybe_never || last_use_this_basic_block (dest_regno, insn)))
1.1.1.8 root 3533: {
3534: v->replaceable = 1;
3535: for (b = bl->biv; b; b = b->family)
3536: {
3537: if ((uid_luid[INSN_UID (b->insn)] >= uid_luid[regno_first_uid[dest_regno]])
3538: &&
3539: (uid_luid[INSN_UID (b->insn)]
3540: <= uid_luid[regno_last_uid[dest_regno]]))
3541: {
3542: v->replaceable = 0;
3543: break;
3544: }
3545: }
3546: }
3547: else
3548: v->replaceable = 0;
3549: }
3550:
3551: if (loop_dump_stream)
3552: {
3553: if (type == DEST_REG)
3554: fprintf (loop_dump_stream, "Insn %d: giv reg %d",
3555: INSN_UID (insn), dest_regno);
3556: else
3557: fprintf (loop_dump_stream, "Insn %d: dest address",
3558: INSN_UID (insn));
3559:
3560: fprintf (loop_dump_stream, " src reg %d benefit %d",
3561: src_regno, v->benefit);
3562: fprintf (loop_dump_stream, " used %d lifetime %d",
3563: v->times_used, v->lifetime);
3564:
3565: if (v->replaceable)
3566: fprintf (loop_dump_stream, " replaceable");
3567:
3568: if (GET_CODE (mult_val) == CONST_INT)
3569: fprintf (loop_dump_stream, " mult %d",
3570: INTVAL (mult_val));
3571: else
3572: {
3573: fprintf (loop_dump_stream, " mult ");
3574: print_rtl (loop_dump_stream, mult_val);
3575: }
3576:
3577: if (GET_CODE (add_val) == CONST_INT)
3578: fprintf (loop_dump_stream, " add %d",
3579: INTVAL (add_val));
3580: else
3581: {
3582: fprintf (loop_dump_stream, " add ");
3583: print_rtl (loop_dump_stream, add_val);
3584: }
3585: }
3586:
3587: if (loop_dump_stream && v->forces)
3588: fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces->insn));
3589: if (loop_dump_stream && v->forces2)
3590: fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces2->insn));
3591: if (loop_dump_stream && v->consec)
3592: fprintf (loop_dump_stream, " consec %d", v->consec);
3593: if (loop_dump_stream)
3594: fprintf (loop_dump_stream, "\n");
3595: }
3596:
3597: /* Delete the insns forced by the insn described by V.
3598: If THIS_TOO is nonzero, delete that insn itself as well. */
3599:
3600: static void
3601: delete_insn_forces (v, this_too)
3602: struct induction *v;
3603: int this_too;
3604: {
3605: rtx x, p;
3606: int count;
3607: rtx insn;
3608:
3609: if (this_too)
3610: {
3611: insn = v->insn;
3612: for (count = v->consec; count >= 0; count--)
3613: {
3614: /* If first insn of libcall sequence, skip to end. */
3615: /* Do this at start of loop, since p is guaranteed to
3616: be an insn here. */
3617: if (x = find_reg_note (insn, REG_LIBCALL, 0))
3618: insn = XEXP (x, 0);
3619:
1.1.1.13 root 3620: if (x = find_reg_note (insn, REG_RETVAL, 0))
1.1.1.8 root 3621: {
3622: /* This is a library call; delete all insns backward until get to
3623: first insn in this group. */
1.1.1.13 root 3624: rtx first = XEXP (x, 0);
1.1.1.8 root 3625: for (p = insn; p != first; p = PREV_INSN (p))
3626: delete_insn (p);
3627: /* Delete first insn also. */
3628: delete_insn (p);
3629: }
3630: else
3631: delete_insn (insn);
3632:
3633: do insn = NEXT_INSN (insn);
3634: while (GET_CODE (insn) == NOTE);
3635: }
3636: }
3637:
3638: if (v->forces)
3639: delete_insn_forces (v->forces, 1);
3640: if (v->forces2)
3641: delete_insn_forces (v->forces2, 1);
3642: }
3643:
3644: /* Check whether an insn is an increment legitimate for a basic induction var.
3645: X is the source of the insn.
3646: DEST_REG is the putative biv, also the destination of the insn.
3647: We accept patterns of these forms:
3648: REG = REG + INVARIANT
3649: REG = INVARIANT + REG
3650: REG = REG - CONSTANT
3651:
3652: If X is suitable, we return 1,
3653: and store the factor multiplying REF in X into *MULT_VAL
3654: and the additive term into *INC_VAL.
3655: Otherwise we return 0. */
3656:
3657: static int
3658: basic_induction_var (x, dest_regno, inc_val, mult_val)
3659: register rtx x;
3660: int dest_regno;
3661: rtx *inc_val;
3662: rtx *mult_val;
3663: {
1.1.1.12 root 3664: register enum rtx_code code;
1.1.1.8 root 3665: rtx arg;
3666:
1.1.1.12 root 3667: if (x == 0)
3668: return 0;
3669: code = GET_CODE (x);
1.1.1.8 root 3670: switch (code)
3671: {
3672: case PLUS:
3673: if (GET_CODE (XEXP (x, 0)) == REG
3674: && REGNO (XEXP (x, 0)) == dest_regno)
3675: arg = XEXP (x, 1);
3676: else if (GET_CODE (XEXP (x, 1)) == REG
3677: && REGNO (XEXP (x, 1)) == dest_regno)
3678: arg = XEXP (x, 0);
3679: else
3680: return 0;
3681:
3682: if (invariant_p (arg) == 1)
3683: *inc_val = arg;
3684: else
3685: return 0;
3686:
3687: *mult_val = const1_rtx;
3688: return 1;
3689:
3690: case MINUS:
3691: if (GET_CODE (XEXP (x, 0)) == REG
3692: && REGNO (XEXP (x, 0)) == dest_regno
3693: && GET_CODE (XEXP (x, 1)) == CONST_INT)
3694: *inc_val = gen_rtx (CONST_INT, VOIDmode,
3695: - INTVAL (XEXP (x, 1)));
3696: else
3697: return 0;
3698: *mult_val = const1_rtx;
3699: return 1;
3700:
3701: /* Can accept constant setting of biv only when inside inner most loop.
3702: Otherwise, a biv of an inner loop may be incorrectly recognized
3703: as a biv of the outer loop,
3704: causing code to be moved INTO the inner loop. */
3705: case REG:
3706: if (!invariant_p (x))
3707: return 0;
3708: case CONST_INT:
3709: case SYMBOL_REF:
3710: case CONST:
3711: if (loops_enclosed == 1)
3712: {
3713: *inc_val = x;
3714: *mult_val = const0_rtx;
3715: return 1;
3716: }
3717: else
3718: return 0;
3719:
3720: default:
3721: return 0;
3722: }
3723: }
3724:
3725: /* A general induction variable (giv) is any quantity that is a linear function
3726: of a basic induction variable, i.e. giv = biv * mult_val + add_val.
3727: The coefficients can be any loop invariant quantity.
3728: A giv need not be computed directly from the biv;
3729: it can be computed by way of other givs. */
3730:
3731: /* Determine whether X computes a giv.
3732: If it does, return a nonzero value
3733: which is the benefit from eliminating the computation of X;
3734: set *SRC_REGNO to the register number of the biv that it is computed from;
3735: set *ADD_VAL and *MULT_VAL to the coefficients,
3736: such that the value of X is biv * mult + add;
3737: set forces (and forces2) to identify any other givs that are used
3738: solely to compute this one. */
3739:
3740: /* This routine recognizes four types of patterns that generate givs:
3741: - giv = biv op invariant v = 0, g = 0
3742: - giv1 = giv2 op invariant v = 0, g = giv2
3743: where giv1 and giv2 are functions of the same biv
3744: - giv1 = biv op giv2 v = giv2, g = 0
3745: where giv2 is a function of biv
3746: - giv1 = giv2 op giv3 v = giv3, g = giv2
3747: where giv2 and giv3 are functions of the save biv */
3748:
3749: static int
3750: general_induction_var (x, src_regno, add_val, mult_val, forces, forces2)
3751: rtx x;
3752: int *src_regno;
3753: rtx *add_val;
3754: rtx *mult_val;
3755: struct induction **forces;
3756: struct induction **forces2;
3757: {
1.1.1.12 root 3758: register enum rtx_code code;
1.1.1.8 root 3759: rtx arg;
3760: struct induction *g = 0;
3761: struct induction *v = 0;
3762: int subexp = 0;
3763: int tem;
3764:
1.1.1.12 root 3765: if (x == 0)
3766: return 0;
3767:
3768: code = GET_CODE (x);
1.1.1.8 root 3769: switch (code)
3770: {
3771: case NEG:
3772: /* This can generate givs also, but it is not handled. */
3773: return 0;
3774:
3775: case MULT:
3776: case UMULT:
1.1.1.16 root 3777: /* Reject widening multiply in version 1.
3778: That is safer than trying to handle it. */
3779: {
3780: enum machine_mode m0 = GET_MODE (XEXP (x, 0));
3781: enum machine_mode m1 = GET_MODE (XEXP (x, 1));
3782: if (m0 != VOIDmode && m0 != GET_MODE (x))
3783: return 0;
3784: if (m1 != VOIDmode && m1 != GET_MODE (x))
3785: return 0;
3786: }
3787: case PLUS:
3788: case MINUS:
1.1.1.8 root 3789: /* Result is linear in both operands. */
3790: /* Determine which operand is the biv, and put the other in ARG. */
3791: if (GET_CODE (XEXP (x, 0)) == REG
3792: && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT)
3793: {
3794: *src_regno = REGNO (XEXP (x, 0));
3795: arg = XEXP (x, 1);
3796:
3797: }
3798: else if (GET_CODE (XEXP (x, 1)) == REG
3799: && induct_var[REGNO (XEXP (x, 1))] == BASIC_INDUCT)
3800: {
3801: *src_regno = REGNO (XEXP (x, 1));
3802: arg = XEXP (x, 0);
3803:
3804: }
3805: /* Check for an rtl subexpression that is a giv. Memory address
3806: givs often look like (plus (reg) (mult (biv) (const))). */
3807: /* Do this before checking for a giv operand, as this function will
3808: fail if this special operand is not recognized. */
3809: #ifndef DONT_REDUCE_ADDR
3810: else if (tem = general_induction_var (XEXP (x, 1), src_regno,
3811: add_val, mult_val,
1.1.1.15 root 3812: forces, forces2)
3813: && code != MINUS)
1.1.1.8 root 3814: {
3815: /* Set subexp true so that this can be handled a little
3816: differently from the normal case of g set. */
3817: /* Note that SRC_REGNO is already set. */
3818: subexp = TRUE;
3819: g = (struct induction *) alloca (sizeof (struct induction));
3820: g->mult_val = *mult_val;
3821: g->add_val = *add_val;
1.1.1.15 root 3822: /* Fake out the test below. */
3823: g->replaceable = 1;
1.1.1.8 root 3824: /* Count this multiply as a shift, since that's what it
3825: really will do. */
3826: if (tem == MULT_BENEFIT)
3827: g->benefit = SHIFT_BENEFIT;
3828: else
3829: g->benefit = tem;
3830: arg = XEXP (x, 0);
3831: }
1.1.1.16 root 3832: else if (tem = general_induction_var (XEXP (x, 0), src_regno,
3833: add_val, mult_val,
3834: forces, forces2))
3835: {
3836: /* Set subexp true so that this can be handled a little
3837: differently from the normal case of g set. */
3838: /* Note that SRC_REGNO is already set. */
3839: subexp = TRUE;
3840: g = (struct induction *) alloca (sizeof (struct induction));
3841: g->mult_val = *mult_val;
3842: g->add_val = *add_val;
3843: /* Fake out the test below. */
3844: g->replaceable = 1;
3845: /* Count this multiply as a shift, since that's what it
3846: really will do. */
3847: if (tem == MULT_BENEFIT)
3848: g->benefit = SHIFT_BENEFIT;
3849: else
3850: g->benefit = tem;
3851: arg = XEXP (x, 1);
3852: }
1.1.1.8 root 3853: #endif
3854: /* Also allow general induction variables.
3855: Could have a mult followed by an add (i.e. an address calculation),
3856: thereby generating two related general induction variables
3857: of which only the second is actually used. */
3858: /* Do this after checking both args for basic induction variables. */
3859: else if (GET_CODE (XEXP (x, 0)) == REG
3860: && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT)
3861: {
3862: g = induct_struct[REGNO (XEXP (x, 0))];
3863: *src_regno = g->src_regno;
3864: arg = XEXP (x, 1);
3865: }
3866: else if (GET_CODE (XEXP (x, 1)) == REG
1.1.1.15 root 3867: && induct_var[REGNO (XEXP (x, 1))] == GENERAL_INDUCT
3868: && code != MINUS)
1.1.1.8 root 3869: {
3870: g = induct_struct[REGNO (XEXP (x, 1))];
3871: *src_regno = g->src_regno;
3872: arg = XEXP (x, 0);
3873: }
3874: else
3875: return 0;
3876:
3877: /* Overall form of expression looks good. */
3878: break;
3879:
3880: /* Could handle these also. */
3881: case DIV:
3882: case UDIV:
3883: /* For a 68020 could handle these? */
3884: case LSHIFT:
3885: case ASHIFT:
3886: case ASHIFTRT:
3887: case LSHIFTRT:
3888: /* These operations are linear only in first operand.
3889: Check for a biv or giv there; if found, put other operand in ARG. */
3890: if (GET_CODE (XEXP (x, 0)) == REG
3891: && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT)
3892: {
3893: *src_regno = REGNO (XEXP (x, 0));
3894: arg = XEXP (x, 1);
3895: }
3896: /* Also allow general induction variable. */
3897: else if (GET_CODE (XEXP (x, 0)) == REG
3898: && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT)
3899: {
3900: g = induct_struct[REGNO (XEXP (x, 0))];
3901: *src_regno = g->src_regno;
3902: arg = XEXP (x, 1);
3903: }
3904: else
3905: return 0;
3906:
3907: /* Overall form of expression looks good. */
3908: break;
3909:
3910: default:
3911: return 0;
3912: }
3913:
3914: /* ARG is the operand that is NOT a biv or giv.
3915: Test it for superficial validity. */
3916:
3917: /* This is just a special case of invariant values,
3918: it is not really needed, but it's a shortcut. */
3919: if (GET_CODE (arg) == CONST_INT)
3920: ;
3921:
3922: /* Depends on previous general induction variable, which has
3923: the same basic induction variable */
3924: /* This code detects mults that have been generated as shift and add. */
3925: else if (GET_CODE (arg) == REG
3926: && induct_var[REGNO (arg)] == GENERAL_INDUCT
3927: && induct_struct[REGNO (arg)]->src_regno == *src_regno)
3928: {
3929: v = induct_struct[REGNO (arg)];
3930: /* Dependence indicated by forces, sort of kludgey. */
3931: }
3932:
3933: /* Invariant expression, could be a constant-valued register. */
3934: else if (invariant_p (arg) == 1)
3935: ;
3936:
3937: /* Failure */
3938: else
3939: return 0;
1.1.1.15 root 3940:
3941: /* Until we can do the correct thing, suppress use of nonreplaceable givs
3942: as sources for other givs. */
3943: if ((g && ! g->replaceable)
3944: || (v && ! v->replaceable))
3945: return 0;
1.1.1.8 root 3946:
3947: /* Now we know looks like a giv; extract the coefficients.
3948: We can still fail if the coefficients are not what we can handle. */
3949:
3950: /* Only succeed if result mult_val and add_val are only one level of rtl,
3951: for example, (NEG:SI (REG:SI 34)) is not accepted.
3952: This mainly causes problems with the MINUS code. */
3953:
3954: switch (code)
3955: {
3956: case PLUS:
3957: if (v && g)
3958: {
3959: if (GET_CODE (g->mult_val) == CONST_INT)
3960: {
3961: if (g->mult_val == const0_rtx)
3962: *mult_val = v->mult_val;
3963: else if (GET_CODE (v->mult_val) == CONST_INT)
3964: *mult_val = gen_rtx (CONST_INT, VOIDmode,
3965: INTVAL (g->mult_val)
3966: + INTVAL (v->mult_val));
3967: else
3968: return 0;
3969: }
3970: else if (v->mult_val == const0_rtx)
3971: *mult_val = g->mult_val;
3972: else
3973: return 0;
3974:
3975: if (GET_CODE (g->add_val) == CONST_INT)
3976: {
3977: if (g->add_val == const0_rtx)
3978: *add_val = v->add_val;
3979: else if (GET_CODE (v->add_val) == CONST_INT)
3980: *add_val = gen_rtx (CONST_INT, VOIDmode,
3981: INTVAL (g->add_val)
3982: + INTVAL (v->add_val));
3983: else
3984: return 0;
3985: }
3986: else if (v->add_val == const0_rtx)
3987: *add_val = g->add_val;
3988: else
3989: return 0;
3990:
3991: if (subexp)
3992: {
3993: /* g deleted when return, can't return pointer to it */
3994: if (*forces2 == 0)
3995: *forces2 = v;
3996: return ADD_BENEFIT + g->benefit;
3997: }
3998: else
3999: {
4000: *forces = g;
4001: *forces2 = v;
4002: return ADD_BENEFIT;
4003: }
4004: }
4005: else if (v)
4006: {
4007: if (GET_CODE (v->mult_val) == CONST_INT)
4008: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4009: INTVAL (v->mult_val) + 1);
4010: else
4011: return 0;
4012: *add_val = v->add_val;
4013: *forces = v;
4014: return ADD_BENEFIT;
4015: }
4016: else if (g)
4017: {
4018: *mult_val = g->mult_val;
1.1.1.17 root 4019: if (GET_CODE (g->add_val) == CONST_INT
4020: && nonmemory_operand (arg, GET_MODE (arg)))
1.1.1.16 root 4021: *add_val = plus_constant (arg, INTVAL (g->add_val));
1.1.1.17 root 4022: else if (GET_CODE (arg) == CONST_INT
4023: && nonmemory_operand (g->add_val, GET_MODE (g->add_val)))
1.1.1.16 root 4024: *add_val = plus_constant (g->add_val, INTVAL (arg));
1.1.1.8 root 4025: else
4026: /* Could succeed if arg == 0, but that will never occur. */
4027: return 0;
4028:
4029: if (subexp)
4030: /* g deleted when return, can't return pointer to it */
4031: return ADD_BENEFIT + g->benefit;
4032: else
4033: {
4034: *forces = g;
4035: return ADD_BENEFIT;
4036: }
4037: }
4038: else
4039: {
4040: *mult_val = const1_rtx;
4041: *add_val = arg;
4042: return ADD_BENEFIT;
4043: }
4044:
4045: /* Takes a lot of code and will rarely succeed. */
4046: case MINUS:
4047: if (v && g)
4048: {
4049: /* G is the first argument of MINUS. */
4050:
4051: if (GET_CODE (g->mult_val) == CONST_INT)
4052: {
4053: if (g->mult_val == const0_rtx)
4054: #if 0 /* Should not have to fail here */
4055: *mult_val = gen_rtx (NEG, SImode, v->mult_val);
4056: #endif
4057: return 0;
4058: else if (GET_CODE (v->mult_val) == CONST_INT)
4059: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4060: INTVAL (g->mult_val)
4061: - INTVAL (v->mult_val));
4062: else
4063: return 0;
4064: }
4065: else if (v->mult_val == const0_rtx)
4066: *mult_val = g->mult_val;
4067: else
4068: return 0;
4069:
4070: if (GET_CODE (g->add_val) == CONST_INT)
4071: {
4072: if (g->add_val == const0_rtx)
4073: #if 0 /* should not have to fail here */
4074: *add_val = v->add_val;
4075: #endif
4076: return 0;
4077: else if (GET_CODE (v->add_val) == CONST_INT)
4078: *add_val = gen_rtx (CONST_INT, VOIDmode,
4079: INTVAL (g->add_val)
4080: - INTVAL (v->add_val));
4081: else
4082: return 0;
4083: }
4084: else if (v->add_val == const0_rtx)
4085: *add_val = g->add_val;
4086: else
4087: return 0;
4088:
4089: if (subexp)
4090: {
4091: /* G deleted when return, can't return pointer to it */
4092: if (*forces2 == 0)
4093: *forces2 = v;
4094: return ADD_BENEFIT + g->benefit;
4095: }
4096: else
4097: {
4098: *forces = g;
4099: *forces2 = v;
4100: return ADD_BENEFIT;
4101: }
4102: }
4103: else if (v)
4104: {
4105: if (GET_CODE (v->mult_val) != CONST_INT)
4106: return 0;
4107: if (arg == XEXP (x, 0)) /* giv1 = giv2 - biv */
4108: {
4109: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4110: INTVAL (v->mult_val) - 1);
4111: *add_val = v->add_val;
4112: }
4113: else /* giv1 = biv - giv2 */
4114: {
4115: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4116: 1 - INTVAL (v->mult_val));
4117: if (GET_CODE (v->add_val) == CONST_INT)
4118: *add_val = gen_rtx (CONST_INT, VOIDmode,
4119: - INTVAL (v->add_val));
4120: else
4121: return 0;
4122: }
4123: *forces = v;
4124: return ADD_BENEFIT;
4125: }
4126: else if (g)
4127: {
4128: if (arg == XEXP (x, 1))
4129: *mult_val = g->mult_val;
4130: else
4131: {
4132: if (GET_CODE (g->mult_val) == CONST_INT)
4133: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4134: - INTVAL (g->mult_val));
4135: else
4136: return 0;
4137: }
4138: if (GET_CODE (g->add_val) == CONST_INT)
4139: {
4140: if (g->add_val == const0_rtx)
4141: {
4142: if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */
4143: {
4144: /* Fail unless arg is a constant. */
4145: if (GET_CODE (arg) == CONST_INT)
4146: *add_val = gen_rtx (CONST_INT, VOIDmode,
4147: -INTVAL (arg));
4148: else
4149: return 0;
4150: }
4151: else /* giv1 = arg - giv2 */
4152: *add_val = arg;
4153: }
4154: else if (GET_CODE (arg) == CONST_INT)
4155: {
4156: if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */
4157: *add_val = gen_rtx (CONST_INT, VOIDmode,
4158: INTVAL (g->add_val)
4159: - INTVAL (arg));
4160: else /* giv1 = arg - giv2 */
4161: *add_val = gen_rtx (CONST_INT, VOIDmode,
4162: INTVAL (arg),
4163: - INTVAL (g->add_val));
4164: }
4165: else
4166: return 0;
4167: }
4168: else
4169: /* Could succeed if arg == 0, but that will never occur. */
4170: return 0;
4171:
4172: if (subexp)
4173: /* G deleted when return, can't return pointer to it. */
4174: return ADD_BENEFIT + g->benefit;
4175: else
4176: {
4177: *forces = g;
4178: return ADD_BENEFIT;
4179: }
4180: }
4181: else if (GET_CODE (arg) == CONST_INT)
4182: {
4183: if (arg == XEXP (x, 1))
4184: {
4185: *add_val = gen_rtx (CONST_INT, VOIDmode, - INTVAL (arg));
4186: *mult_val = const1_rtx;
4187: }
4188: else
4189: {
4190: *add_val = arg;
4191: *mult_val = gen_rtx (CONST_INT, VOIDmode, -1);
4192: }
4193: return ADD_BENEFIT;
4194: }
4195: else
4196: return 0;
4197:
4198: /* UMULT can be handled like MULT since C ignores overflows. */
4199: case MULT:
4200: case UMULT:
4201: if (v && g)
4202: {
4203: /* Quadratic term, just fail. */
4204: return 0;
4205: }
4206: else if (v)
4207: {
4208: /* Quadratic term, just fail. */
4209: return 0;
4210: }
4211: else if (g)
4212: {
4213: /* Takes a lot of code and will rarely succeed. */
4214: /* dest = m * arg * b + a * arg */
4215: if (GET_CODE (g->mult_val) == CONST_INT)
4216: {
4217: if (g->mult_val == const0_rtx)
4218: *mult_val = const0_rtx;
4219: else if (g->mult_val == const1_rtx)
4220: *mult_val = arg;
4221: else if (GET_CODE (arg) == CONST_INT)
4222: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4223: INTVAL (g->mult_val) * INTVAL (arg));
4224: else
4225: return 0;
4226: }
4227: else
4228: /* Could suceed if arg == 1 or 0, but this will never occur. */
4229: return 0;
4230:
4231: if (GET_CODE (g->add_val) == CONST_INT)
4232: {
4233: if (g->add_val == const0_rtx)
4234: *add_val = const0_rtx;
4235: else if (g->add_val == const1_rtx)
4236: *add_val = arg;
4237: else if (GET_CODE (arg) == CONST_INT)
4238: *add_val = gen_rtx (CONST_INT, VOIDmode,
4239: INTVAL (g->add_val) * INTVAL (arg));
4240: else
4241: return 0;
4242: }
4243: else
4244: /* Could suceed if arg == 1 or 0, but this will never occur. */
4245: return 0;
4246:
4247: if (subexp)
4248: /* G deleted when return, can't return pointer to it. */
4249: return MULT_BENEFIT + g->benefit;
4250: else
4251: {
4252: *forces = g;
4253: return MULT_BENEFIT;
4254: }
4255: }
4256: else
4257: {
4258: *mult_val = arg;
4259: *add_val = const0_rtx;
4260: return MULT_BENEFIT;
4261: }
4262:
4263: /* These are not worth the trouble. */
4264: case DIV:
4265: case UDIV:
4266: return 0;
4267:
4268: /* Handle these, but only for left shift. */
4269: case LSHIFT:
4270: case ASHIFT:
4271: if (v && g)
4272: {
4273: /* Quadratic term, just fail. */
4274: return 0;
4275: }
4276: else if (v)
4277: {
4278: /* Quadratic term, just fail. */
4279: return 0;
4280: }
4281: else if (g)
4282: {
4283: /* Takes a lot of code and will rarely succeed. */
4284: /* dest = ((m * b) << arg) + (a << arg) */
4285: if (GET_CODE (g->mult_val) == CONST_INT)
4286: {
4287: if (g->mult_val == const0_rtx)
4288: *mult_val = const0_rtx;
4289: else if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0)
4290: *mult_val = gen_rtx (CONST_INT, VOIDmode,
4291: INTVAL (g->mult_val)
4292: * (1 << INTVAL (arg)));
4293: else
4294: return 0;
4295: }
4296: else
4297: /* Could suceed if arg == 0, but this will never occur. */
4298: return 0;
4299:
4300: if (GET_CODE (g->add_val) == CONST_INT)
4301: {
4302: if (g->add_val == const0_rtx)
4303: *add_val = const0_rtx;
4304: else if (GET_CODE (arg) == CONST_INT)
4305: *add_val = gen_rtx (CONST_INT, VOIDmode,
4306: INTVAL (g->add_val)
4307: * (1 << INTVAL (arg)));
4308: else
4309: return 0;
4310: }
4311: else
4312: /* Could suceed if arg == 0, but this will never occur. */
4313: return 0;
4314:
4315: if (subexp)
4316: /* G deleted when return, can't return pointer to it. */
4317: return SHIFT_BENEFIT + g->benefit;
4318: else
4319: {
4320: *forces = g;
4321: return SHIFT_BENEFIT;
4322: }
4323: }
4324:
4325: if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0)
4326: *mult_val = gen_rtx (CONST_INT, VOIDmode, 1 << INTVAL (arg));
4327: else
4328: return 0;
4329: *add_val = const0_rtx;
4330: return SHIFT_BENEFIT;
4331:
4332: /* These are not worth the trouble. */
4333: case ASHIFTRT:
4334: case LSHIFTRT:
4335: return 0;
4336:
4337: /* should never reach here */
4338: default:
4339: abort ();
4340: return 0;
4341: }
4342: }
4343:
4344: /* Help detect a giv that is calculated by several consecutive insns;
4345: for example,
4346: giv = biv * M
4347: giv = giv + A
4348: The caller has already identified the first insn P as having a giv as dest;
4349: we check that all other insns that set the same register follow
4350: immediately after P, that they alter nothing else,
4351: and that the result of the last is still a giv.
4352:
4353: The value is 0 if the reg set in P is not really a giv.
4354: Otherwise, the value is the amount gained by eliminating
4355: all the consecutive insns that compute the value.
4356:
4357: FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
4358: SRC_REGNO is the regno of the biv; DEST_REGNO is that of the giv.
4359:
4360: The coefficients of the ultimate giv value are stored in
4361: *MULT_VAL and *ADD_VAL. */
4362:
4363: static int
4364: consec_sets_giv (first_benefit, p, src_regno, dest_regno,
4365: add_val, mult_val)
4366: int first_benefit;
4367: rtx p;
4368: int src_regno;
4369: int dest_regno;
4370: rtx *add_val;
4371: rtx *mult_val;
4372: {
4373: int count;
4374: int benefit = first_benefit;
4375: enum rtx_code code;
1.1.1.17 root 4376: struct induction *forces, *forces2;
1.1.1.8 root 4377: rtx temp;
4378: int tem;
4379:
4380: /* Initialize info used by general_induction_var. */
4381: struct induction *v =
4382: (struct induction *) oballoc (sizeof (struct induction));
4383: v->src_regno = src_regno;
4384: v->mult_val = *mult_val;
4385: v->add_val = *add_val;
4386:
4387: induct_var[dest_regno] = GENERAL_INDUCT;
4388: induct_struct[dest_regno] = v;
4389:
4390: count = n_times_set[dest_regno] - 1;
4391:
4392: while (count > 0)
4393: {
4394: p = NEXT_INSN (p);
4395: code = GET_CODE (p);
4396:
4397: /* If libcall, skip to end of call sequence. */
4398: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
4399: p = XEXP (temp, 0);
4400:
4401: if (code == INSN && GET_CODE (PATTERN (p)) == SET
4402: && GET_CODE (SET_DEST (PATTERN (p))) == REG
4403: && REGNO (SET_DEST (PATTERN (p))) == dest_regno
4404: && ((tem = general_induction_var (SET_SRC (PATTERN (p)), &src_regno,
4405: add_val, mult_val,
4406: &forces, &forces2))
4407: /* Giv created by call to library routine. */
1.1.1.17 root 4408: || ((temp = loop_find_reg_equal (p))
4409: && (tem = general_induction_var (XEXP (temp, 0), &src_regno,
4410: add_val, mult_val,
4411: &forces, &forces2))))
1.1.1.8 root 4412: && src_regno == v->src_regno)
4413: {
4414: count--;
4415: benefit += tem;
4416: v->mult_val = *mult_val;
4417: v->add_val = *add_val;
4418: }
4419: else if (code != NOTE)
4420: {
4421: induct_var[dest_regno] = UNKNOWN_INDUCT;
4422: return 0;
4423: }
4424: }
4425:
4426: return benefit;
4427: }
4428:
4429: /* Generate a SEQUENCE to multiply OP0 and OP1 with result in TARGET.
4430: Use expand_mult to "optimally" do the multiply.
1.1.1.10 root 4431: This also works for machines that do not have multiply insns.
4432: If one of the operands is a constant, it must be the second. */
1.1.1.8 root 4433:
4434: static rtx
4435: gen_iv_mult (mode, op0, op1, target)
4436: enum machine_mode mode;
4437: register rtx op0, op1, target;
4438: {
4439: extern rtx gen_sequence ();
4440: extern rtx start_sequence ();
1.1.1.10 root 4441: rtx saved, result, temp;
1.1.1.8 root 4442:
4443: saved = start_sequence ();
4444:
1.1.1.10 root 4445: /* ??? It is very unmodular to use expand_mult here!
4446: This should be redesigned. */
4447:
1.1.1.8 root 4448: /* UNSIGNEDP arg can be zero since operands/target always same width. */
1.1.1.10 root 4449: temp = expand_mult (mode, op0, op1, target, 0);
4450:
4451: /* Move to target register, if expand_mult did not put it there. */
4452: if (target != 0 && temp != target)
4453: emit_move_insn (target, temp);
1.1.1.8 root 4454:
4455: result = gen_sequence ();
4456: end_sequence (saved);
4457:
4458: return result;
4459: }
4460:
4461: /* Emit code to initialize an induction variable created by strength
1.1.1.15 root 4462: reduction.
4463: More precisely, emit code before INSERT_BEFORE
4464: to set REG = B * M + A. */
1.1.1.14 root 4465:
1.1.1.8 root 4466: static void
1.1.1.15 root 4467: emit_iv_init_code (b, m, a, reg, insert_before)
1.1.1.8 root 4468: rtx b; /* initial value of basic induction variable */
4469: rtx m; /* multiplicative constant */
4470: rtx a; /* additive constant */
4471: rtx reg; /* destination register */
1.1.1.15 root 4472: rtx insert_before;
1.1.1.8 root 4473: {
1.1.1.15 root 4474: rtx seq;
4475: rtx result;
1.1.1.8 root 4476:
1.1.1.15 root 4477: /* Prevent unexpected sharing of these rtx. */
4478: a = copy_rtx (a);
4479: b = copy_rtx (b);
4480:
4481: start_sequence ();
4482: result = expand_mult_add (b, m, a, GET_MODE (reg), 0);
4483: if (reg != result)
4484: emit_move_insn (reg, result);
4485: seq = gen_sequence ();
4486: end_sequence ();
1.1.1.8 root 4487:
1.1.1.15 root 4488: emit_insn_before (seq, insert_before);
4489: }
1.1.1.8 root 4490:
1.1.1.15 root 4491: /* Emit code to increment the induction variable inside the loop.
4492: Try to emit optimal code for the expression
4493: REG = REG + BIV_ADD * GIV_MULT. */
1.1.1.8 root 4494:
1.1.1.15 root 4495: static void
4496: emit_iv_inc (biv_add, giv_mult, reg, insn)
4497: rtx biv_add; /* increment value for biv */
4498: rtx giv_mult; /* multiply value of giv */
4499: rtx reg; /* create insn to set this reg */
4500: rtx insn; /* where to insert the new insn */
4501: {
4502: emit_iv_init_code (biv_add, giv_mult, reg, reg, insn);
1.1.1.8 root 4503: }
4504:
4505: /* Test whethen BIV_ADD * GIV_MULT can be computed without
4506: an actual multiply insn. Value is 1 if so. */
4507:
4508: static int
4509: product_cheap_p (biv_add, giv_mult)
4510: rtx biv_add;
4511: rtx giv_mult;
4512: {
4513: /* Indicates which of MULT/ADD are constants. */
4514: int status = 0;
4515: int const_val;
4516: rtx tmp;
4517:
4518: if (GET_CODE (biv_add) == CONST_INT)
4519: status |= 0x1;
4520: if (GET_CODE (giv_mult) == CONST_INT)
4521: status |= 0x2;
4522:
4523: switch (status)
4524: {
4525: case 0:
4526: /* Neither is constant: would need a multiply insn, so fail. */
4527: return 0;
4528:
4529: case 1:
4530: /* BIV_ADD value is constant */
4531: /* Equivalent to state 2, just switch values of BIV_ADD and GIV_MULT
4532: and fall through. */
4533: tmp = biv_add;
4534: biv_add = giv_mult;
4535: giv_mult = tmp;
4536:
4537: case 2:
4538: /* GIV_MULT value is constant.
4539: If it is 1, 0 or -1 then we win. */
4540: const_val = INTVAL (giv_mult);
4541: if (const_val < -1 || const_val > 1)
4542: {
4543: tmp = gen_iv_mult (GET_MODE (biv_add), biv_add, giv_mult, 0);
4544: /* Don't emit a multiply insn, just fail instead. */
4545: if ((GET_CODE (tmp) == SET && GET_CODE (SET_SRC (tmp)) == MULT)
4546: /* Also fail if library call (which generates more
4547: then two insn) is needed. */
4548: || (GET_CODE (tmp) == SEQUENCE && XVECLEN (tmp, 0) > 2))
4549: return 0;
4550: }
4551: return 1;
4552:
4553: case 3:
4554: /* Both BIV_ADD and GIV_MULT are constant;
4555: can compute the product at compile time. */
4556: return 1;
4557:
4558: default:
4559: abort ();
4560: }
4561: }
4562:
4563:
4564: /* Check to see if loop can be terminated by a "decrement and branch until
4565: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
4566: Also try reversing an increment loop to a decrement loop
4567: to see if the optimization can be performed.
4568: Value is nonzero if optimization was performed. */
4569:
4570: static int
4571: check_dbra_loop (loop_end, iv_list, insn_count, loop_start)
4572: rtx loop_end;
4573: struct iv_class *iv_list;
4574: int insn_count;
4575: rtx loop_start;
4576: {
4577: struct iv_class *bl;
4578: rtx reg;
4579: rtx jump_label;
4580: rtx final_value;
4581: rtx start_value;
4582: enum rtx_code branch_code;
4583: rtx new_add_val;
4584: rtx tested_before_loop = 0;
4585: rtx p;
4586:
4587: /* See if the loop is contained in `if (X >= 0)' for some reg X.
4588: If so, then we know X is initially nonnegative even though
4589: we don't know its initial value.
4590: Record X in TESTED_BEFORE_LOOP. */
4591:
4592: for (p = loop_start; p != 0; p = PREV_INSN (p))
4593: if (GET_CODE (p) != NOTE)
4594: break;
4595:
4596: /* See if a conditional branch preceeds the loop.
4597: There may be no other insns or labels between it and
4598: the beginning of the loop. */
4599: if (p != 0 && GET_CODE (p) == JUMP_INSN && condjump_p (p)
4600: && SET_SRC (PATTERN (p)) != pc_rtx
4601: && ((GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == LT
4602: && XEXP (SET_SRC (PATTERN (p)), 2) == pc_rtx)
4603: ||
4604: (GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == GE
4605: && XEXP (SET_SRC (PATTERN (p)), 1) == pc_rtx))
4606: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end))
4607: {
4608: /* Before the branch should be a test or compare.
4609: See if we are comparing something against zero. */
4610: p = PREV_INSN (p);
4611: if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET
4612: && SET_DEST (PATTERN (p)) == cc0_rtx)
4613: {
4614: if (GET_CODE (SET_SRC (PATTERN (p))) == REG)
4615: tested_before_loop = SET_SRC (PATTERN (p));
1.1.1.14 root 4616: else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE
4617: && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == REG
1.1.1.8 root 4618: && XEXP (SET_SRC (PATTERN (p)), 1) == const0_rtx)
4619: tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 0);
1.1.1.14 root 4620: else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE
4621: && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 1)) == REG
4622: && XEXP (SET_SRC (PATTERN (p)), 0) == const0_rtx)
4623: tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 1);
1.1.1.8 root 4624: }
4625: }
4626:
4627: /* If last insn is a conditional branch, and the insn before tests a register
4628: value, then try to optimize it. */
4629:
4630: if (GET_CODE (PREV_INSN (loop_end)) == JUMP_INSN
4631: && GET_CODE (PATTERN (PREV_INSN (loop_end))) == SET
4632: && GET_CODE (SET_SRC (PATTERN (PREV_INSN (loop_end)))) == IF_THEN_ELSE
4633: && GET_CODE (PREV_INSN (PREV_INSN (loop_end))) == INSN
4634: && GET_CODE (PATTERN (PREV_INSN (PREV_INSN (loop_end)))) == SET
4635: && (GET_CODE (SET_DEST (PATTERN (PREV_INSN (PREV_INSN (loop_end))))) ==
4636: CC0))
4637: {
4638: /* Check all of the bivs to see if the compare uses one of them. */
4639:
4640: for (bl = iv_list; bl; bl = bl->next)
4641: {
4642: if (reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)),
4643: PREV_INSN (PREV_INSN (loop_end))))
4644: break;
4645: }
4646:
4647: /* If biv set more than once, then give up.
1.1.1.15 root 4648: We can't guarantee that it will be zero on the last iteration.
4649: Also give up if the biv is used between its update and the test
4650: insn. */
4651: if (bl && bl->biv_count == 1
4652: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
4653: PREV_INSN (PREV_INSN (loop_end))))
1.1.1.8 root 4654: {
4655: /* Look for the case where the basic induction variable is always
4656: nonnegative, and equals zero on the last iteration.
4657: In this case, add a reg_note REG_NONNEG, which allows the
4658: m68k DBRA instruction to be used. */
4659:
4660: /* the decrement case */
4661:
4662: if (GET_CODE (bl->biv->add_val) == CONST_INT
4663: && INTVAL (bl->biv->add_val) < 0)
4664: {
4665: /* Initial value must be greater than 0,
4666: init_val % -dec_value == 0 to ensure that it equals zero on
4667: the last iteration */
4668:
4669: if (GET_CODE (bl->initial_value) == CONST_INT
4670: && INTVAL (bl->initial_value) > 0
4671: && (INTVAL (bl->initial_value) %
4672: (-INTVAL (bl->biv->add_val))) == 0)
4673: {
4674: /* register always nonnegative, add REG_NOTE to branch */
4675: REG_NOTES (PREV_INSN (loop_end))
4676: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
4677: REG_NOTES (PREV_INSN (loop_end)));
4678: bl->nonneg = 1;
4679:
4680: return 1;
4681: }
4682:
4683: /* If the decrement is 1 and the value was tested as >= 0 before
4684: the loop, then we can safely optimize. */
4685: if (SET_DEST (PATTERN (bl->biv->insn)) == tested_before_loop
4686: && INTVAL (bl->biv->add_val) == -1)
4687: {
4688: REG_NOTES (PREV_INSN (loop_end))
4689: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
4690: REG_NOTES (PREV_INSN (loop_end)));
4691: bl->nonneg = 1;
4692:
4693: return 1;
4694: }
4695: }
1.1.1.15 root 4696: else if (num_mem_sets <= 1)
1.1.1.8 root 4697: {
4698: /* Try to change inc to dec, so can apply above optimization. */
4699: /* Can do this if:
4700: all registers modified are induction variables or invariant,
4701: all memory references have non-overlapping addresses
4702: (obviously true if only one write)
4703: allow 2 insns for the compare/jump at the end of the loop. */
1.1.1.15 root 4704: int num_nonfixed_reads = 0;
4705: rtx p;
1.1.1.19! root 4706: /* 1 if the iteration var is used only to count iterations. */
! 4707: int no_use_except_counting = 0;
1.1.1.15 root 4708:
4709: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
4710: if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN
4711: || GET_CODE (p) == JUMP_INSN)
4712: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
1.1.1.8 root 4713:
1.1.1.19! root 4714: if (bl->giv_count == 0)
! 4715: {
! 4716: rtx bivreg = regno_reg_rtx[bl->regno];
! 4717:
! 4718: /* If there are no givs for this biv,
! 4719: see if perhaps there are no uses except to count. */
! 4720: no_use_except_counting = 1;
! 4721: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
! 4722: if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN
! 4723: || GET_CODE (p) == JUMP_INSN)
! 4724: {
! 4725: if (GET_CODE (PATTERN (p)) == SET
! 4726: && GET_CODE (SET_DEST (PATTERN (p))) == REG
! 4727: && REGNO (SET_DEST (PATTERN (p))) == bl->regno)
! 4728: /* An insn that sets the biv is okay. */
! 4729: ;
! 4730: else if (p == PREV_INSN (PREV_INSN (loop_end))
! 4731: || p == PREV_INSN (loop_end))
! 4732: /* Don't bother about the end test. */
! 4733: ;
! 4734: else if (reg_mentioned_p (bivreg, PATTERN (p)))
! 4735: /* Any other use of the biv is no good. */
! 4736: {
! 4737: no_use_except_counting = 0;
! 4738: break;
! 4739: }
! 4740: }
! 4741: }
! 4742:
1.1.1.8 root 4743: /* This code only acts for innermost loops. Also it simplifies
4744: the memory address check by only reversing loops with
1.1.1.15 root 4745: zero or one memory access.
4746: Two memory accesses could involve parts of the same array,
4747: and that can't be reversed. */
1.1.1.8 root 4748:
1.1.1.15 root 4749: if (num_nonfixed_reads <= 1
1.1.1.8 root 4750: && !loop_has_call
1.1.1.19! root 4751: && (no_use_except_counting
! 4752: || (bl->giv_count + bl->biv_count + num_mem_sets
! 4753: + num_movables + 2 == insn_count)))
1.1.1.8 root 4754: {
4755: rtx src_two_before_end;
1.1.1.15 root 4756: int constant;
4757: int win;
1.1.1.8 root 4758:
4759: /* Loop can be reversed. */
4760: if (loop_dump_stream)
4761: fprintf (loop_dump_stream, "Can reverse loop\n");
4762:
4763: /* Now check other conditions:
4764: initial_value must be zero,
4765: final_value % add_val == 0, so that when reversed, the
4766: biv will be zero on the last iteration. */
4767:
4768: /* Calculating the final value non trivial.
4769: If branch is (LT (CC0) (CONST 0),
4770: then value in compare is final value.
4771: If branch is (LE (CC0) (CONST 0),
4772: then value in compare is final_value - add_val */
4773:
4774: branch_code
4775: = GET_CODE (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0));
4776: src_two_before_end
1.1.1.14 root 4777: = SET_SRC (PATTERN (PREV_INSN (PREV_INSN (loop_end))));
1.1.1.8 root 4778:
1.1.1.15 root 4779: win = 1;
4780: if (GET_CODE (src_two_before_end) == REG)
4781: constant = 0;
4782: else if (GET_CODE (src_two_before_end) == COMPARE
4783: && GET_CODE (XEXP (src_two_before_end, 1)) == CONST_INT)
4784: constant = INTVAL (XEXP (src_two_before_end, 1));
4785: else
4786: win = 0;
4787:
4788: if (win && bl->initial_value == const0_rtx
1.1.1.8 root 4789: && (branch_code == LT || branch_code == LE)
4790: && XEXP (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0), 1) == const0_rtx
1.1.1.15 root 4791: && (constant % INTVAL (bl->biv->add_val)) == 0)
1.1.1.8 root 4792: {
4793: /* Register will always be nonnegative, with value
4794: 0 on last iteration if loop reversed */
4795:
4796: /* Save some info needed to produce the new insns. */
4797: reg = SET_DEST (PATTERN (bl->biv->insn));
4798: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
4799: new_add_val = gen_rtx (CONST_INT, VOIDmode,
4800: - INTVAL (bl->biv->add_val));
4801:
4802:
4803: if (branch_code == LT)
4804: {
1.1.1.15 root 4805: final_value
4806: = gen_rtx (CONST_INT, VOIDmode, constant);
1.1.1.8 root 4807: start_value
4808: = gen_rtx (CONST_INT, VOIDmode,
1.1.1.15 root 4809: (constant - INTVAL (bl->biv->add_val)));
1.1.1.8 root 4810: }
4811: else /* branch_code == LE */
4812: {
1.1.1.15 root 4813: start_value
4814: = gen_rtx (CONST_INT, VOIDmode, constant);
1.1.1.8 root 4815: final_value
4816: = gen_rtx (CONST_INT, VOIDmode,
1.1.1.15 root 4817: (constant + INTVAL (bl->biv->add_val)));
1.1.1.8 root 4818: }
4819:
4820: /* Initialize biv to start_value before loop start.
4821: The old initializing insn will be deleted as a
4822: dead store by flow.c. */
4823: emit_insn_before (gen_rtx (SET, VOIDmode, reg,
4824: start_value),
4825: loop_start);
4826:
4827: /* Add insn to decrement register, and delete insn
4828: that incremented the register. */
4829: emit_insn_before (gen_rtx (SET, VOIDmode, reg,
4830: gen_rtx (PLUS, GET_MODE (reg), reg,
4831: new_add_val)),
4832: bl->biv->insn);
4833: /* Update biv info to reflect its new status. */
4834: bl->biv->insn = PREV_INSN (bl->biv->insn);
4835: delete_insn (NEXT_INSN (bl->biv->insn));
4836:
1.1.1.15 root 4837: /* Inc LABEL_NUSES so that delete_insn will
1.1.1.8 root 4838: not delete the label. */
1.1.1.15 root 4839: LABEL_NUSES (XEXP (jump_label, 0)) ++;
1.1.1.8 root 4840:
4841: if (regno_last_uid[bl->regno] != INSN_UID (PREV_INSN (loop_end)))
4842: emit_insn_after (gen_rtx (SET, VOIDmode, reg,
4843: final_value),
4844: loop_end);
4845:
4846: /* Delete compare/branch at end of loop. */
4847: delete_insn (PREV_INSN (loop_end));
4848: delete_insn (PREV_INSN (loop_end));
4849:
4850: /* Add new compare/branch insn at end of loop. */
4851: emit_insn_before (gen_rtx (SET, VOIDmode, cc0_rtx, reg),
4852: loop_end);
4853: emit_jump_insn_before (gen_rtx (SET, VOIDmode, pc_rtx,
4854: gen_rtx (IF_THEN_ELSE, VOIDmode,
4855: gen_rtx (GE, VOIDmode, cc0_rtx,
4856: const0_rtx),
4857: jump_label,
4858: pc_rtx)),
4859: loop_end);
4860:
1.1.1.15 root 4861: JUMP_LABEL (PREV_INSN (loop_end)) = XEXP (jump_label, 0);
4862: /* Increment of LABEL_NUSES done above. */
4863:
1.1.1.8 root 4864: /* Register is now always nonnegative,
4865: so add REG_NONNEG note to the branch. */
4866: REG_NOTES (PREV_INSN (loop_end))
4867: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
4868: REG_NOTES (PREV_INSN (loop_end)));
4869: bl->nonneg = 1;
4870:
4871: /* Update rest of biv info. */
4872: bl->initial_value = start_value;
4873: bl->biv->add_val = new_add_val;
4874:
4875: if (loop_dump_stream)
4876: fprintf (loop_dump_stream, "Reversed loop and added reg_nonneg\n");
4877:
4878: return 1;
4879: }
4880: }
4881: }
4882: }
4883: }
4884: return 0;
4885: }
4886:
1.1.1.14 root 4887: /* Verify whether the biv BL appears to be eliminable,
4888: based on the insns in the loop that refer to it.
4889: LOOP_START is the first insn of the loop, and END is the end insn. */
4890:
4891: static void
4892: check_eliminate_biv (bl, loop_start, end)
4893: struct iv_class *bl;
4894: rtx loop_start;
4895: rtx end;
4896: {
4897: /* Get the REG rtx for the biv. */
4898: rtx reg = SET_DEST (PATTERN (bl->biv->insn));
4899: rtx p;
4900: struct induction *v;
4901:
4902: bl->eliminable = 0;
4903:
4904: for (p = loop_start; p != end; p = NEXT_INSN (p))
4905: {
4906: enum rtx_code code = GET_CODE (p);
4907: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
4908: && reg_mentioned_p (reg, PATTERN (p)))
4909: {
4910: /* This insn uses the biv. If we can't understand it,
4911: then we can't eliminate the biv. */
4912: if (GET_CODE (PATTERN (p)) != SET)
4913: {
4914: if (loop_dump_stream)
4915: fprintf (loop_dump_stream,
4916: "Cannot eliminate biv %d: cannot understand insn %d.\n",
4917: bl->regno, INSN_UID (p));
4918: break;
4919: }
4920:
4921: /* The insns that increment the biv are no problem. */
4922: if (SET_DEST (PATTERN (p)) == reg)
4923: continue;
4924:
4925: /* If this is an insn which uses the biv ONLY in the
4926: calculation of a giv which is in the family of this
4927: biv, it's ok becuase it will go away when the giv is
4928: reduced. March 14, 1989 -- [email protected] */
4929: for (v = bl->giv; v; v = v->family)
4930: if (v->insn == p)
4931: {
4932: if (v->giv_type == DEST_REG
4933: || (v->giv_type == DEST_ADDR
1.1.1.17 root 4934: && ! other_reg_use_p (reg, *(v->location),
4935: PATTERN (p))))
1.1.1.14 root 4936: break;
4937: }
4938: if (v)
4939: continue;
4940:
4941: /* If can rewrite this insn not to use the biv, it's ok. */
4942: if (can_eliminate_biv_p (p, bl))
4943: continue;
4944:
4945: /* Biv is used in a way we cannot eliminate. */
4946: if (loop_dump_stream)
4947: fprintf (loop_dump_stream,
4948: "Cannot eliminate biv %d: biv used in insn %d.\n",
4949: bl->regno, INSN_UID (p));
4950: break;
4951: }
4952: }
4953:
4954: if (p == end)
4955: {
4956: bl->eliminable = 1;
4957: if (loop_dump_stream)
4958: fprintf (loop_dump_stream, "Can eliminate biv %d.\n",
4959: bl->regno);
4960: }
4961: }
4962:
1.1.1.8 root 4963: /* Return 1 if INSN, a compare insn which tests the biv described by BL,
4964: can be rewritten to use instead some reduced giv related to that biv.
4965: Does not change the rtl.
4966:
4967: We make the assumption that all the givs depending on this biv
4968: will be reduced, since only in that case will an attempt to eliminate
4969: the biv actually be made.
4970:
4971: The following function is very parallel to this one. */
4972:
4973: static int
4974: can_eliminate_biv_p (insn, bl)
4975: rtx insn;
4976: struct iv_class *bl;
4977: {
4978: rtx src;
4979: enum rtx_code code;
4980: struct induction *v, *tv;
4981: rtx arg;
4982: int arg_operand;
4983: /* Mode of this biv. */
1.1.1.14 root 4984: enum machine_mode mode = bl->biv->mode;
1.1.1.8 root 4985:
4986: if (SET_DEST (PATTERN (insn)) != cc0_rtx)
4987: return 0;
4988:
4989: src = SET_SRC (PATTERN (insn));
4990: code = GET_CODE (src);
4991:
4992: switch (code)
4993: {
4994: /* a test insn */
4995: case REG:
4996: /* Can replace with any giv that has (MULT_VAL != 0) and (ADD_VAL == 0)
1.1.1.14 root 4997: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 4998:
4999: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 5000: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
5001: && v->add_val == const0_rtx
5002: && ! v->ignore
5003: && v->mode == mode)
1.1.1.8 root 5004: return 1;
5005:
1.1.1.16 root 5006: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0)
5007: where ADD_VAL is a constant or a register;
5008: can replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
1.1.1.14 root 5009: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 5010:
1.1.1.19! root 5011: if (next_insn_tests_no_inequality (insn))
! 5012: for (v = bl->giv; v; v = v->family)
! 5013: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
! 5014: && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT)
! 5015: && ! v->ignore
! 5016: && v->mode == mode)
! 5017: return 1;
1.1.1.14 root 5018:
5019: if (loop_dump_stream)
5020: fprintf (loop_dump_stream, "Cannot eliminate biv %d in test insn %d: no appropriate giv.\n",
5021: bl->regno, INSN_UID (insn));
5022:
1.1.1.8 root 5023: return 0;
5024:
5025: /* a compare insn */
1.1.1.13 root 5026: case COMPARE:
1.1.1.8 root 5027: /* Figure out which operand is the biv. */
5028: if ((GET_CODE (XEXP (src, 0)) == REG)
5029: && (REGNO (XEXP (src, 0)) == bl->regno))
5030: {
5031: arg = XEXP (src, 1);
5032: arg_operand = 1;
5033: }
1.1.1.16 root 5034: else if ((GET_CODE (XEXP (src, 1)) == REG)
5035: && (REGNO (XEXP (src, 1)) == bl->regno))
1.1.1.8 root 5036: {
5037: arg = XEXP (src, 0);
5038: arg_operand = 0;
5039: }
1.1.1.16 root 5040: else
5041: return 0;
1.1.1.8 root 5042:
5043: if (GET_CODE (arg) == CONST_INT)
5044: {
5045: /* Can replace with any giv that has constant coefficients. */
5046:
5047: for (v = bl->giv; v; v = v->family)
5048: if (GET_CODE (v->mult_val) == CONST_INT
5049: && GET_CODE (v->add_val) == CONST_INT
1.1.1.14 root 5050: && ! v->ignore
5051: && v->mode == mode)
1.1.1.19! root 5052: {
! 5053: /* Make sure there's no overflow in the range for the giv. */
! 5054: if (INTVAL (v->mult_val) == 0
! 5055: ||
! 5056: (INTVAL (arg) * INTVAL (v->mult_val) / INTVAL (v->mult_val)
! 5057: != INTVAL (arg))
! 5058: ||
! 5059: ((0 < (INTVAL (arg) * INTVAL (v->mult_val)
! 5060: + INTVAL (v->add_val)))
! 5061: != (0 < INTVAL (arg))))
! 5062: return 0;
1.1.1.8 root 5063:
1.1.1.19! root 5064: return 1;
! 5065: }
1.1.1.8 root 5066:
1.1.1.19! root 5067: if (next_insn_tests_no_inequality (insn))
! 5068: {
! 5069: /* Look for giv with constant mult_val and nonconst add_val,
! 5070: since we can insert add insn before loop
! 5071: to calculate new compare value. */
! 5072:
! 5073: /* This is not safe if the end-test is not == or !=,
! 5074: since we can't tell whether the giv will overflow. */
! 5075: for (v = bl->giv; v; v = v->family)
! 5076: if (GET_CODE (v->mult_val) == CONST_INT
! 5077: && ! v->ignore
! 5078: && v->mode == mode)
! 5079: return 1;
! 5080: }
1.1.1.8 root 5081: }
1.1.1.19! root 5082: else if ((GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
! 5083: && next_insn_tests_no_inequality (insn))
1.1.1.8 root 5084: {
5085: /* Comparing against invariant register or memref can be handled. */
5086:
5087: if (invariant_p (arg))
5088: {
5089: /* Look for giv with constant mult_val and nonconst add_val.
5090: Insert add-insn before loop to compute new compare value. */
5091:
5092: for (v = bl->giv; v; v = v->family)
5093: if ((GET_CODE (v->mult_val) == CONST_INT)
1.1.1.14 root 5094: && ! v->ignore
5095: && v->mode == mode)
1.1.1.8 root 5096: return 1;
5097: }
5098:
5099: /* Otherwise, only comparing against a biv can be handled. */
5100: if (GET_CODE (arg) != REG
5101: || induct_var[REGNO (arg)] != BASIC_INDUCT)
5102: return 0;
5103:
5104: /* Look for a giv for each biv that have identical
5105: values for mult_val and add_val. */
5106: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 5107: if (v->mode == mode
5108: && ! v->ignore)
1.1.1.8 root 5109: {
5110: for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
5111: if ((tv->new_reg != 0)
5112: && rtx_equal_p (tv->mult_val, v->mult_val)
5113: && rtx_equal_p (tv->mult_val, v->mult_val)
1.1.1.14 root 5114: && ! tv->ignore
5115: && tv->mode == mode)
1.1.1.8 root 5116: return 1;
5117: }
5118: }
5119: return 0;
5120:
5121: default:
5122: return 0;
5123: }
5124: }
5125:
5126: /* Rewrite a compare insn INSN which uses the biv described by BL
5127: so that it doesn't use that biv any more.
5128: Instead it will use some reduced giv related to that biv.
5129:
5130: The preceding function is very parallel to this one. */
5131:
5132: static void
5133: eliminate_biv (insn, bl, loop_start)
5134: rtx insn;
5135: struct iv_class *bl;
5136: rtx loop_start;
5137: {
5138: rtx src = SET_SRC (PATTERN (insn));
5139: enum rtx_code code = GET_CODE (src);
5140: struct induction *v, *tv;
1.1.1.17 root 5141: rtx arg, temp;
1.1.1.8 root 5142: int arg_operand;
5143: /* Mode of this biv. */
1.1.1.14 root 5144: enum machine_mode mode = bl->biv->mode;
1.1.1.8 root 5145:
5146: switch (code)
5147: {
5148: /* a test insn */
5149: case REG:
1.1.1.14 root 5150: /* Can replace with any giv that was reduced and
5151: that has (MULT_VAL != 0) and (ADD_VAL == 0).
5152: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 5153:
5154: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 5155: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
5156: && v->add_val == const0_rtx
1.1.1.8 root 5157: && v->new_reg != 0
1.1.1.14 root 5158: && v->mode == mode)
1.1.1.8 root 5159: break;
5160: if (v)
5161: {
5162: /* We can test the sign of that giv's reduced reg. */
5163: SET_SRC (PATTERN (insn)) = v->new_reg;
1.1.1.17 root 5164: /* If the giv has the opposite direction of change,
5165: then reverse the comparison. */
5166: if (INTVAL (v->mult_val) < 0)
5167: SET_SRC (PATTERN (insn))
5168: = gen_rtx (COMPARE, GET_MODE (v->new_reg),
5169: const0_rtx, v->new_reg);
1.1.1.8 root 5170: return;
5171: }
5172:
1.1.1.16 root 5173: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0)
5174: where ADD_VAL is a constant or a register;
1.1.1.14 root 5175: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
5176: Require a constant integer for MULT_VAL, so we know it's nonzero. */
1.1.1.8 root 5177:
5178: for (v = bl->giv; v; v = v->family)
1.1.1.14 root 5179: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
1.1.1.16 root 5180: && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT)
1.1.1.14 root 5181: && v->new_reg != 0
5182: && v->mode == mode)
1.1.1.8 root 5183: break;
5184: if (v)
5185: {
5186: /* Replace biv with the giv's reduced register. */
1.1.1.14 root 5187: SET_SRC (PATTERN (insn)) = gen_rtx (COMPARE, GET_MODE (v->new_reg),
1.1.1.15 root 5188: v->new_reg,
5189: copy_rtx (v->add_val));
1.1.1.8 root 5190:
1.1.1.17 root 5191: /* If the giv has the opposite direction of change,
5192: then reverse the comparison. */
5193: if (INTVAL (v->mult_val) < 0)
5194: {
5195: XEXP (SET_SRC (PATTERN (insn)), 0)
5196: = XEXP (SET_SRC (PATTERN (insn)), 1);
5197: XEXP (SET_SRC (PATTERN (insn)), 1) = v->new_reg;
5198: }
1.1.1.8 root 5199: #if 0
5200: /* add_val must be invariant, so don't bother storing in a register */
5201: /* calculate the appropriate constant to compare against */
5202: emit_insn_before (gen_rtx (SET, VOIDmode, compare_value,
1.1.1.15 root 5203: copy_rtx (v->add_val)),
1.1.1.8 root 5204: loop_start);
5205: #endif
5206: return;
5207: }
5208: abort ();
5209: break;
5210:
5211: /* a compare insn */
1.1.1.13 root 5212: case COMPARE:
1.1.1.8 root 5213: /* Figure out which operand is the biv. */
1.1.1.13 root 5214: if (GET_CODE (XEXP (src, 0)) == REG
5215: && REGNO (XEXP (src, 0)) == bl->regno)
1.1.1.8 root 5216: {
5217: arg = XEXP (src, 1);
5218: arg_operand = 1;
5219: }
1.1.1.16 root 5220: else if (GET_CODE (XEXP (src, 1)) == REG
5221: && REGNO (XEXP (src, 1)) == bl->regno)
1.1.1.8 root 5222: {
5223: arg = XEXP (src, 0);
5224: arg_operand = 0;
5225: }
1.1.1.16 root 5226: else
5227: abort ();
1.1.1.8 root 5228:
5229: if (GET_CODE (arg) == CONST_INT)
5230: {
5231: /* Can replace with any giv that has constant mult_val and add_val.
5232: Make sure it was strength reduced by checking new_reg != 0. */
5233:
5234: for (v = bl->giv; v; v = v->family)
5235: if (GET_CODE (v->mult_val) == CONST_INT
5236: && GET_CODE (v->add_val) == CONST_INT
5237: && v->new_reg
1.1.1.14 root 5238: && v->mode == mode)
1.1.1.19! root 5239: {
! 5240: /* Make sure there's no overflow in the range for the giv. */
! 5241: if (! (INTVAL (v->mult_val) == 0
! 5242: ||
! 5243: (INTVAL (arg) * INTVAL (v->mult_val) / INTVAL (v->mult_val)
! 5244: != INTVAL (arg))
! 5245: ||
! 5246: ((0 < (INTVAL (arg) * INTVAL (v->mult_val)
! 5247: + INTVAL (v->add_val)))
! 5248: != (0 < INTVAL (arg)))))
! 5249: break;
! 5250: }
1.1.1.8 root 5251: if (v)
5252: {
1.1.1.15 root 5253: rtx newval;
1.1.1.8 root 5254: /* Replace biv with the giv's reduced reg. */
5255: XEXP (src, 1-arg_operand) = v->new_reg;
5256: /* Calculate the appropriate constant to compare against. */
1.1.1.15 root 5257: newval = gen_rtx (CONST_INT, VOIDmode,
5258: (INTVAL (arg) * INTVAL (v->mult_val)
5259: + INTVAL (v->add_val)));
5260: XEXP (src, arg_operand) = newval;
5261: /* If that constant is no good in a compare,
5262: put it in a register. */
5263: if (recog (PATTERN (insn), insn) < 0)
5264: {
1.1.1.17 root 5265: temp = gen_reg_rtx (mode);
1.1.1.15 root 5266: emit_iv_init_code (arg, v->mult_val, v->add_val,
5267: temp, loop_start);
5268: XEXP (src, arg_operand) = temp;
5269: }
1.1.1.17 root 5270:
5271: /* If the giv has the opposite direction of change,
5272: then reverse the comparison. */
5273: if (INTVAL (v->mult_val) < 0)
5274: {
5275: temp = XEXP (src, 0);
5276: XEXP (src, 0) = XEXP (src, 1);
5277: XEXP (src, 1) = temp;
5278: }
1.1.1.8 root 5279: return;
5280: }
5281:
5282: /* Look for giv with constant mult_val and nonconst add_val.
5283: Insert add insn before loop to calculate new compare value. */
5284:
5285: for (v = bl->giv; v; v = v->family)
5286: if (GET_CODE (v->mult_val) == CONST_INT
5287: && v->new_reg
1.1.1.14 root 5288: && v->mode == mode)
1.1.1.8 root 5289: break;
5290: if (v)
5291: {
5292: rtx compare_value = gen_reg_rtx (mode);
5293:
5294: /* Replace biv with giv's reduced register. */
5295: XEXP (src, 1-arg_operand) = v->new_reg;
5296:
5297: /* At start of loop, compute value to compare against. */
1.1.1.15 root 5298: emit_iv_init_code (arg, v->mult_val, v->add_val,
5299: compare_value, loop_start);
5300: /* Use it in this insn. */
1.1.1.8 root 5301: XEXP (src, arg_operand) = compare_value;
1.1.1.17 root 5302:
5303: /* If the giv has the opposite direction of change,
5304: then reverse the comparison. */
5305: if (INTVAL (v->mult_val) < 0)
5306: {
5307: temp = XEXP (src, 0);
5308: XEXP (src, 0) = XEXP (src, 1);
5309: XEXP (src, 1) = temp;
5310: }
1.1.1.8 root 5311: return;
5312: }
5313: abort ();
5314: }
5315: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
5316: {
5317: if (invariant_p (arg))
5318: {
5319: /* Look for giv with constant mult_val and nonconst add_val.
5320: Insert add-insn before loop to compute new compare value. */
5321:
5322: for (v = bl->giv; v; v = v->family)
5323: if (GET_CODE (v->mult_val) == CONST_INT
5324: && v->new_reg
1.1.1.14 root 5325: && v->mode == mode)
1.1.1.8 root 5326: break;
5327: if (v)
5328: {
5329: rtx compare_value = gen_reg_rtx (mode);
5330:
5331: /* Replace biv with giv's reduced register. */
5332: XEXP (src, 1-arg_operand) = v->new_reg;
5333:
1.1.1.15 root 5334: /* At start of loop, compute value to compare against. */
5335: emit_iv_init_code (arg, v->mult_val, v->add_val,
5336: compare_value, loop_start);
1.1.1.8 root 5337: XEXP (src, arg_operand) = compare_value;
1.1.1.17 root 5338:
5339: /* If the giv has the opposite direction of change,
5340: then reverse the comparison. */
5341: if (INTVAL (v->mult_val) < 0)
5342: {
5343: temp = XEXP (src, 0);
5344: XEXP (src, 0) = XEXP (src, 1);
5345: XEXP (src, 1) = temp;
5346: }
1.1.1.8 root 5347: return;
5348: }
5349: }
5350:
5351: /* Otherwise the reg compared with had better be a biv. */
5352: if (GET_CODE (arg) != REG
5353: || induct_var[REGNO (arg)] != BASIC_INDUCT)
5354: abort ();
5355:
5356: /* Look for a pair of givs, one for each biv,
5357: with identical coefficients. */
5358: for (v = bl->giv; v; v = v->family)
5359: {
1.1.1.14 root 5360: if (!v->new_reg && v->mode == mode)
1.1.1.8 root 5361: continue;
5362: for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
5363: if ((tv->new_reg != 0)
5364: && rtx_equal_p (tv->mult_val, v->mult_val)
1.1.1.16 root 5365: && rtx_equal_p (tv->add_val, v->add_val)
1.1.1.14 root 5366: && tv->mode == mode)
1.1.1.8 root 5367: break;
5368: if (tv)
5369: break;
5370: }
5371: if (v)
5372: {
5373: /* Replace biv with its giv's reduced reg. */
5374: XEXP (src, 1-arg_operand) = v->new_reg;
5375: /* Replace other operand with the other giv's reduced reg. */
5376: XEXP (src, arg_operand) = tv->new_reg;
1.1.1.17 root 5377:
5378: /* If the giv has the opposite direction of change,
5379: then reverse the comparison. */
5380: if (INTVAL (v->mult_val) < 0)
5381: {
5382: temp = XEXP (src, 0);
5383: XEXP (src, 0) = XEXP (src, 1);
5384: XEXP (src, 1) = temp;
5385: }
1.1.1.8 root 5386: return;
5387: }
5388: }
5389: abort ();
5390:
5391: default:
5392: abort ();
5393: }
5394: }
5395:
5396: /* Try to calculate the final value of the biv,
5397: the value it will have at the end of the loop.
5398: If we can do it, return that value. */
5399:
1.1.1.10 root 5400: /* ??? One case that should be simple to handle
5401: is when the biv is incremented by an invariant
5402: exactly once each time around the loop,
5403: and when the number of iterations can be determined
5404: (as the value of some invariant).
5405: Then the final value would be BIV + (INCREMENT * NUM_ITERATIONS).
5406:
5407: Once that case is handled, it would become desirable to detect empty
5408: loops and delete them, since this optimization could make empty loops. */
5409:
1.1.1.8 root 5410: static rtx
5411: final_biv_value (bl, loop_end)
5412: struct iv_class *bl;
5413: rtx loop_end;
5414: {
5415: /* wimpy, but guaranteed to work */
5416: return 0;
5417: }
1.1.1.11 root 5418:
5419: /* Return nonzero if the last use of reg REGNO
5420: is in an insn following INSN in the same basic block. */
5421:
5422: static int
5423: last_use_this_basic_block (regno, insn)
5424: int regno;
5425: rtx insn;
5426: {
5427: rtx n;
5428: for (n = insn;
5429: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
5430: n = NEXT_INSN (n))
5431: {
5432: if (regno_last_uid[regno] == INSN_UID (n))
5433: return 1;
5434: }
5435: return 0;
5436: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.