![[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 2.x] / gcc|
Return to loop.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Move constant computations out of loops.
2: Copyright (C) 1987, 1988, 1989, 1991 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
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 2, or (at your option)
9: any later version.
10:
11: GNU CC is distributed in the hope that it will be useful,
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. */
19:
20:
21: /* This is the loop optimization pass of the compiler.
22: It finds invariant computations within loops and moves them
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.
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: #include "config.h"
37: #include "rtl.h"
38: #include "obstack.h"
39: #include "expr.h"
40: #include "insn-config.h"
41: #include "insn-flags.h"
42: #include "regs.h"
43: #include "hard-reg-set.h"
44: #include "recog.h"
45: #include "flags.h"
46: #include "real.h"
47: #include <stdio.h>
48: #include "loop.h"
49:
50: /* Vector mapping INSN_UIDs to luids.
51: The luids are like uids but increase monononically always.
52: We use them to see whether a jump comes from outside a given loop. */
53:
54: int *uid_luid;
55:
56: /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
57: number the insn is contained in. */
58:
59: int *uid_loop_num;
60:
61: /* 1 + largest uid of any insn. */
62:
63: int max_uid_for_loop;
64:
65: /* 1 + luid of last insn. */
66:
67: static int max_luid;
68:
69: /* Number of loops detected in current function. Used as index to the
70: next few tables. */
71:
72: static int max_loop_num;
73:
74: /* Indexed by loop number, contains the first and last insn of each loop. */
75:
76: static rtx *loop_number_loop_starts, *loop_number_loop_ends;
77:
78: /* For each loop, gives the containing loop number, -1 if none. */
79:
80: int *loop_outer_loop;
81:
82: /* Indexed by loop number, contains a nonzero value if the "loop" isn't
83: really a loop (an insn outside the loop branches into it). */
84:
85: static char *loop_invalid;
86:
87: /* Indexed by loop number, links together all LABEL_REFs which refer to
88: code labels outside the loop. Used by routines that need to know all
89: loop exits, such as final_biv_value and final_giv_value.
90:
91: This does not include loop exits due to return instructions. This is
92: because all bivs and givs are pseudos, and hence must be dead after a
93: return, so the presense of a return does not affect any of the
94: optimizations that use this info. It is simpler to just not include return
95: instructions on this list. */
96:
97: rtx *loop_number_exit_labels;
98:
99: /* Holds the number of loop iterations. It is zero if the number could not be
100: calculated. Must be unsigned long since the number of iterations can
101: be as high as 2^31-1. For loops with a DImode iterator, this number will
102: will be zero if the number of loop iterations is too large for an
103: unsigned long to hold. */
104:
105: unsigned long loop_n_iterations;
106:
107: /* Nonzero if there is a subroutine call in the current loop.
108: (unknown_address_altered is also nonzero in this case.) */
109:
110: static int loop_has_call;
111:
112: /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
113: current loop. A continue statement will generate a branch to
114: NEXT_INSN (loop_continue). */
115:
116: static rtx loop_continue;
117:
118: /* Indexed by register number, contains the number of times the reg
119: is set during the loop being scanned.
120: During code motion, a negative value indicates a reg that has been
121: made a candidate; in particular -2 means that it is an candidate that
122: we know is equal to a constant and -1 means that it is an condidate
123: not known equal to a constant.
124: After code motion, regs moved have 0 (which is accurate now)
125: while the failed candidates have the original number of times set.
126:
127: Therefore, at all times, == 0 indicates an invariant register;
128: < 0 a conditionally invariant one. */
129:
130: static short *n_times_set;
131:
132: /* Original value of n_times_set; same except that this value
133: is not set negative for a reg whose sets have been made candidates
134: and not set to 0 for a reg that is moved. */
135:
136: static short *n_times_used;
137:
138: /* Index by register number, 1 indicates that the register
139: cannot be moved or strength reduced. */
140:
141: static char *may_not_optimize;
142:
143: /* Nonzero means reg N has already been moved out of one loop.
144: This reduces the desire to move it out of another. */
145:
146: static char *moved_once;
147:
148: /* Array of MEMs that are stored in this loop. If there are too many to fit
149: here, we just turn on unknown_address_altered. */
150:
151: #define NUM_STORES 20
152: static rtx loop_store_mems[NUM_STORES];
153:
154: /* Index of first available slot in above array. */
155: static int loop_store_mems_idx;
156:
157: /* Nonzero if we don't know what MEMs were changed in the current loop.
158: This happens if the loop contains a call (in which call `loop_has_call'
159: will also be set) or if we store into more than NUM_STORES MEMs. */
160:
161: static int unknown_address_altered;
162:
163: /* Count of movable (i.e. invariant) instructions discovered in the loop. */
164: static int num_movables;
165:
166: /* Count of memory write instructions discovered in the loop. */
167: static int num_mem_sets;
168:
169: /* Number of loops contained within the current one, including itself. */
170: static int loops_enclosed;
171:
172: /* Bound on pseudo register number before loop optimization.
173: A pseudo has valid regscan info if its number is < max_reg_before_loop. */
174: int max_reg_before_loop;
175:
176: /* This obstack is used in product_cheap_p to allocate its rtl. It
177: may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
178: If we used the same obstack that it did, we would be deallocating
179: that array. */
180:
181: static struct obstack temp_obstack;
182:
183: /* This is where the pointer to the obstack being used for RTL is stored. */
184:
185: extern struct obstack *rtl_obstack;
186:
187: #define obstack_chunk_alloc xmalloc
188: #define obstack_chunk_free free
189:
190: extern char *oballoc ();
191: extern int xmalloc ();
192: extern void free ();
193:
194: /* During the analysis of a loop, a chain of `struct movable's
195: is made to record all the movable insns found.
196: Then the entire chain can be scanned to decide which to move. */
197:
198: struct movable
199: {
200: rtx insn; /* A movable insn */
201: rtx set_src; /* The expression this reg is set from. */
202: rtx set_dest; /* The destination of this SET. */
203: rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
204: of any registers used within the LIBCALL. */
205: int consec; /* Number of consecutive following insns
206: that must be moved with this one. */
207: int regno; /* The register it sets */
208: short lifetime; /* lifetime of that register;
209: may be adjusted when matching movables
210: that load the same value are found. */
211: short savings; /* Number of insns we can move for this reg,
212: including other movables that force this
213: or match this one. */
214: unsigned int cond : 1; /* 1 if only conditionally movable */
215: unsigned int force : 1; /* 1 means MUST move this insn */
216: unsigned int global : 1; /* 1 means reg is live outside this loop */
217: /* If PARTIAL is 1, GLOBAL means something different:
218: that the reg is live outside the range from where it is set
219: to the following label. */
220: unsigned int done : 1; /* 1 inhibits further processing of this */
221:
222: unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
223: In particular, moving it does not make it
224: invariant. */
225: unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
226: load SRC, rather than copying INSN. */
227: unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
228: enum machine_mode savemode; /* Nonzero means it is a mode for a low part
229: that we should avoid changing when clearing
230: the rest of the reg. */
231: struct movable *match; /* First entry for same value */
232: struct movable *forces; /* An insn that must be moved if this is */
233: struct movable *next;
234: };
235:
236: FILE *loop_dump_stream;
237:
238: /* Forward declarations. */
239:
240: static void find_and_verify_loops ();
241: static void mark_loop_jump ();
242: static void prescan_loop ();
243: static int reg_in_basic_block_p ();
244: static int consec_sets_invariant_p ();
245: static rtx libcall_other_reg ();
246: static int labels_in_range_p ();
247: static void count_loop_regs_set ();
248: static void note_addr_stored ();
249: static int loop_reg_used_before_p ();
250: static void scan_loop ();
251: static void replace_call_address ();
252: static rtx skip_consec_insns ();
253: static int libcall_benefit ();
254: static void ignore_some_movables ();
255: static void force_movables ();
256: static void combine_movables ();
257: static int rtx_equal_for_loop_p ();
258: static void move_movables ();
259: static void strength_reduce ();
260: static int valid_initial_value_p ();
261: static void find_mem_givs ();
262: static void record_biv ();
263: static void check_final_value ();
264: static void record_giv ();
265: static void update_giv_derive ();
266: static void delete_insn_forces ();
267: static int basic_induction_var ();
268: static rtx simplify_giv_expr ();
269: static int general_induction_var ();
270: static int consec_sets_giv ();
271: static int check_dbra_loop ();
272: static rtx express_from ();
273: static int combine_givs_p ();
274: static void combine_givs ();
275: static int product_cheap_p ();
276: static int maybe_eliminate_biv ();
277: static int maybe_eliminate_biv_1 ();
278: static int last_use_this_basic_block ();
279: static void record_initial ();
280: static void update_reg_last_use ();
281:
282: /* Relative gain of eliminating various kinds of operations. */
283: int add_cost;
284: #if 0
285: int shift_cost;
286: int mult_cost;
287: #endif
288:
289: /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
290: copy the value of the strength reduced giv to its original register. */
291: int copy_cost;
292:
293: void
294: init_loop ()
295: {
296: char *free_point = (char *) oballoc (1);
297: rtx reg = gen_rtx (REG, SImode, 0);
298: rtx pow2 = gen_rtx (CONST_INT, VOIDmode, 32);
299: rtx lea;
300: int i;
301:
302: add_cost = rtx_cost (gen_rtx (PLUS, SImode, reg, reg));
303:
304: /* We multiply by 2 to reconcile the difference in scale between
305: these two ways of computing costs. Otherwise the cost of a copy
306: will be far less than the cost of an add. */
307: #ifdef REGISTER_MOVE_COST
308: copy_cost = REGISTER_MOVE_COST (GENERAL_REGS, GENERAL_REGS) * 2;
309: #else
310: copy_cost = 2 * 2;
311: #endif
312:
313: /* Free the objects we just allocated. */
314: obfree (free_point);
315:
316: /* Initialize the obstack used for rtl in product_cheap_p. */
317: gcc_obstack_init (&temp_obstack);
318: }
319:
320: /* Entry point of this file. Perform loop optimization
321: on the current function. F is the first insn of the function
322: and DUMPFILE is a stream for output of a trace of actions taken
323: (or 0 if none should be output). */
324:
325: void
326: loop_optimize (f, dumpfile)
327: /* f is the first instruction of a chain of insns for one function */
328: rtx f;
329: FILE *dumpfile;
330: {
331: register rtx insn;
332: register int i;
333: rtx end;
334: rtx last_insn;
335:
336: loop_dump_stream = dumpfile;
337:
338: init_recog_no_volatile ();
339: init_alias_analysis ();
340:
341: max_reg_before_loop = max_reg_num ();
342:
343: moved_once = (char *) alloca (max_reg_before_loop);
344: bzero (moved_once, max_reg_before_loop);
345:
346: regs_may_share = 0;
347:
348: /* Count the number of loops. */
349:
350: max_loop_num = 0;
351: for (insn = f; insn; insn = NEXT_INSN (insn))
352: {
353: if (GET_CODE (insn) == NOTE
354: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
355: max_loop_num++;
356: }
357:
358: /* Don't waste time if no loops. */
359: if (max_loop_num == 0)
360: return;
361:
362: /* Get size to use for tables indexed by uids.
363: Leave some space for labels allocated by find_and_verify_loops. */
364: max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 4;
365:
366: uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int));
367: uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int));
368:
369: bzero (uid_luid, max_uid_for_loop * sizeof (int));
370: bzero (uid_loop_num, max_uid_for_loop * sizeof (int));
371:
372: /* Allocate tables for recording each loop. We set each entry, so they need
373: not be zeroed. */
374: loop_number_loop_starts = (rtx *) alloca (max_loop_num * sizeof (rtx));
375: loop_number_loop_ends = (rtx *) alloca (max_loop_num * sizeof (rtx));
376: loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
377: loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
378: loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
379:
380: if (flag_unroll_loops && write_symbols != NO_DEBUG)
381: {
382: loop_number_first_block
383: = (union tree_node **) alloca (max_loop_num
384: * sizeof (union tree_node *));
385: loop_number_last_block
386: = (union tree_node **) alloca (max_loop_num
387: * sizeof (union tree_node *));
388: loop_number_block_level = (int *) alloca (max_loop_num * sizeof (int));
389: }
390:
391: /* Find and process each loop.
392: First, find them, and record them in order of their beginnings. */
393: find_and_verify_loops (f);
394:
395: /* Now find all register lifetimes. This must be done after
396: find_and_verify_loops, because it might reorder the insns in the
397: function. */
398: reg_scan (f, max_reg_num (), 1);
399:
400: /* Compute the mapping from uids to luids.
401: LUIDs are numbers assigned to insns, like uids,
402: except that luids increase monotonically through the code.
403: Don't assign luids to line-number NOTEs, so that the distance in luids
404: between two insns is not affected by -g. */
405:
406: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
407: {
408: last_insn = insn;
409: if (GET_CODE (insn) != NOTE
410: || NOTE_LINE_NUMBER (insn) <= 0)
411: uid_luid[INSN_UID (insn)] = ++i;
412: else
413: /* Give a line number note the same luid as preceding insn. */
414: uid_luid[INSN_UID (insn)] = i;
415: }
416:
417: max_luid = i + 1;
418:
419: /* Don't leave gaps in uid_luid for insns that have been
420: deleted. It is possible that the first or last insn
421: using some register has been deleted by cross-jumping.
422: Make sure that uid_luid for that former insn's uid
423: points to the general area where that insn used to be. */
424: for (i = 0; i < max_uid_for_loop; i++)
425: {
426: uid_luid[0] = uid_luid[i];
427: if (uid_luid[0] != 0)
428: break;
429: }
430: for (i = 0; i < max_uid_for_loop; i++)
431: if (uid_luid[i] == 0)
432: uid_luid[i] = uid_luid[i - 1];
433:
434: /* Create a mapping from loops to BLOCK tree nodes. */
435: if (flag_unroll_loops && write_symbols != NO_DEBUG)
436: find_loop_tree_blocks (f);
437:
438: /* Now scan the loops, last ones first, since this means inner ones are done
439: before outer ones. */
440: for (i = max_loop_num-1; i >= 0; i--)
441: if (! loop_invalid[i] && loop_number_loop_ends[i])
442: scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i],
443: max_reg_num ());
444: }
445:
446: /* Optimize one loop whose start is LOOP_START and end is END.
447: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
448: NOTE_INSN_LOOP_END. */
449:
450: /* ??? Could also move memory writes out of loops if the destination address
451: is invariant, the source is invariant, the memory write is not volatile,
452: and if we can prove that no read inside the loop can read this address
453: before the write occurs. If there is a read of this address after the
454: write, then we can also mark the memory read as invariant. */
455:
456: static void
457: scan_loop (loop_start, end, nregs)
458: rtx loop_start, end;
459: int nregs;
460: {
461: register int i;
462: register rtx p;
463: /* 1 if we are scanning insns that could be executed zero times. */
464: int maybe_never = 0;
465: /* 1 if we are scanning insns that might never be executed
466: due to a subroutine call which might exit before they are reached. */
467: int call_passed = 0;
468: /* For a rotated loop that is entered near the bottom,
469: this is the label at the top. Otherwise it is zero. */
470: rtx loop_top = 0;
471: /* Jump insn that enters the loop, or 0 if control drops in. */
472: rtx loop_entry_jump = 0;
473: /* Place in the loop where control enters. */
474: rtx scan_start;
475: /* Number of insns in the loop. */
476: int insn_count;
477: int in_libcall = 0;
478: int tem;
479: rtx temp;
480: /* The SET from an insn, if it is the only SET in the insn. */
481: rtx set, set1;
482: /* Chain describing insns movable in current loop. */
483: struct movable *movables = 0;
484: /* Last element in `movables' -- so we can add elements at the end. */
485: struct movable *last_movable = 0;
486: /* Ratio of extra register life span we can justify
487: for saving an instruction. More if loop doesn't call subroutines
488: since in that case saving an insn makes more difference
489: and more registers are available. */
490: int threshold;
491: /* If we have calls, contains the insn in which a register was used
492: if it was used exactly once; contains const0_rtx if it was used more
493: than once. */
494: rtx *reg_single_usage = 0;
495:
496: n_times_set = (short *) alloca (nregs * sizeof (short));
497: n_times_used = (short *) alloca (nregs * sizeof (short));
498: may_not_optimize = (char *) alloca (nregs);
499:
500: /* Determine whether this loop starts with a jump down to a test at
501: the end. This will occur for a small number of loops with a test
502: that is too complex to duplicate in front of the loop.
503:
504: We search for the first insn or label in the loop, skipping NOTEs.
505: However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
506: (because we might have a loop executed only once that contains a
507: loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
508: (in case we have a degenerate loop).
509:
510: Note that if we mistakenly think that a loop is entered at the top
511: when, in fact, it is entered at the exit test, the only effect will be
512: slightly poorer optimization. Making the opposite error can generate
513: incorrect code. Since very few loops now start with a jump to the
514: exit test, the code here to detect that case is very conservative. */
515:
516: for (p = NEXT_INSN (loop_start);
517: p != end
518: && GET_CODE (p) != CODE_LABEL && GET_RTX_CLASS (GET_CODE (p)) != 'i'
519: && (GET_CODE (p) != NOTE
520: || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
521: && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
522: p = NEXT_INSN (p))
523: ;
524:
525: scan_start = p;
526:
527: /* Set up variables describing this loop. */
528: prescan_loop (loop_start, end);
529: threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);
530:
531: /* If loop has a jump before the first label,
532: the true entry is the target of that jump.
533: Start scan from there.
534: But record in LOOP_TOP the place where the end-test jumps
535: back to so we can scan that after the end of the loop. */
536: if (GET_CODE (p) == JUMP_INSN)
537: {
538: loop_entry_jump = p;
539:
540: /* Loop entry must be unconditional jump (and not a RETURN) */
541: if (simplejump_p (p)
542: && JUMP_LABEL (p) != 0
543: /* Check to see whether the jump actually
544: jumps out of the loop (meaning it's no loop).
545: This case can happen for things like
546: do {..} while (0). If this label was generated previously
547: by loop, we can't tell anything about it and have to reject
548: the loop. */
549: && INSN_UID (JUMP_LABEL (p)) < max_uid_for_loop
550: && INSN_LUID (JUMP_LABEL (p)) >= INSN_LUID (loop_start)
551: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (end))
552: {
553: loop_top = next_label (scan_start);
554: scan_start = JUMP_LABEL (p);
555: }
556: }
557:
558: /* If SCAN_START was an insn created by loop, we don't know its luid
559: as required by loop_reg_used_before_p. So skip such loops. (This
560: test may never be true, but it's best to play it safe.)
561:
562: Also, skip loops where we do not start scanning at a label. This
563: test also rejects loops starting with a JUMP_INSN that failed the
564: test above. */
565:
566: if (INSN_UID (scan_start) >= max_uid_for_loop
567: || GET_CODE (scan_start) != CODE_LABEL)
568: {
569: if (loop_dump_stream)
570: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
571: INSN_UID (loop_start), INSN_UID (end));
572: return;
573: }
574:
575: /* Count number of times each reg is set during this loop.
576: Set may_not_optimize[I] if it is not safe to move out
577: the setting of register I. If this loop has calls, set
578: reg_single_usage[I]. */
579:
580: bzero (n_times_set, nregs * sizeof (short));
581: bzero (may_not_optimize, nregs);
582:
583: if (loop_has_call)
584: {
585: reg_single_usage = (rtx *) alloca (nregs * sizeof (rtx));
586: bzero (reg_single_usage, nregs * sizeof (rtx));
587: }
588:
589: count_loop_regs_set (loop_top ? loop_top : loop_start, end,
590: may_not_optimize, reg_single_usage, &insn_count, nregs);
591:
592: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
593: may_not_optimize[i] = 1, n_times_set[i] = 1;
594: bcopy (n_times_set, n_times_used, nregs * sizeof (short));
595:
596: if (loop_dump_stream)
597: {
598: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
599: INSN_UID (loop_start), INSN_UID (end), insn_count);
600: if (loop_continue)
601: fprintf (loop_dump_stream, "Continue at insn %d.\n",
602: INSN_UID (loop_continue));
603: }
604:
605: /* Scan through the loop finding insns that are safe to move.
606: Set n_times_set negative for the reg being set, so that
607: this reg will be considered invariant for subsequent insns.
608: We consider whether subsequent insns use the reg
609: in deciding whether it is worth actually moving.
610:
611: MAYBE_NEVER is nonzero if we have passed a conditional jump insn
612: and therefore it is possible that the insns we are scanning
613: would never be executed. At such times, we must make sure
614: that it is safe to execute the insn once instead of zero times.
615: When MAYBE_NEVER is 0, all insns will be executed at least once
616: so that is not a problem. */
617:
618: p = scan_start;
619: while (1)
620: {
621: p = NEXT_INSN (p);
622: /* At end of a straight-in loop, we are done.
623: At end of a loop entered at the bottom, scan the top. */
624: if (p == scan_start)
625: break;
626: if (p == end)
627: {
628: if (loop_top != 0)
629: p = NEXT_INSN (loop_top);
630: else
631: break;
632: if (p == scan_start)
633: break;
634: }
635:
636: if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
637: && find_reg_note (p, REG_LIBCALL, 0))
638: in_libcall = 1;
639: else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
640: && find_reg_note (p, REG_RETVAL, 0))
641: in_libcall = 0;
642:
643: if (GET_CODE (p) == INSN
644: && (set = single_set (p))
645: && GET_CODE (SET_DEST (set)) == REG
646: && ! may_not_optimize[REGNO (SET_DEST (set))])
647: {
648: int tem1 = 0;
649: int tem2 = 0;
650: int move_insn = 0;
651: rtx src = SET_SRC (set);
652: rtx dependencies = 0;
653:
654: /* Figure out what to use as a source of this insn. If a REG_EQUIV
655: note is given or if a REG_EQUAL note with a constant operand is
656: specified, use it as the source and mark that we should move
657: this insn by calling emit_move_insn rather that duplicating the
658: insn.
659:
660: Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
661: is present. */
662: temp = find_reg_note (p, REG_EQUIV, 0);
663: if (temp)
664: src = XEXP (temp, 0), move_insn = 1;
665: else
666: {
667: temp = find_reg_note (p, REG_EQUAL, 0);
668: if (temp && CONSTANT_P (XEXP (temp, 0)))
669: src = XEXP (temp, 0), move_insn = 1;
670: if (temp && find_reg_note (p, REG_RETVAL, 0))
671: {
672: src = XEXP (temp, 0);
673: /* A libcall block can use regs that don't appear in
674: the equivalent expression. To move the libcall,
675: we must move those regs too. */
676: dependencies = libcall_other_reg (p, src);
677: }
678: }
679:
680: /* Don't try to optimize a register that was made
681: by loop-optimization for an inner loop.
682: We don't know its life-span, so we can't compute the benefit. */
683: if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
684: ;
685: /* In order to move a register, we need to have one of three cases:
686: (1) it is used only in the same basic block as the set
687: (2) it is not a user variable.
688: (3) the set is guaranteed to be executed once the loop starts,
689: and the reg is not used until after that. */
690: else if (! ((! maybe_never
691: && ! loop_reg_used_before_p (set, p, loop_start,
692: scan_start, end))
693: || ! REG_USERVAR_P (SET_DEST (PATTERN (p)))
694: || reg_in_basic_block_p (p, SET_DEST (PATTERN (p)))))
695: ;
696: else if ((tem = invariant_p (src))
697: && (dependencies == 0
698: || (tem2 = invariant_p (dependencies)) != 0)
699: && (n_times_set[REGNO (SET_DEST (set))] == 1
700: || (tem1
701: = consec_sets_invariant_p (SET_DEST (set),
702: n_times_set[REGNO (SET_DEST (set))],
703: p)))
704: /* If the insn can cause a trap (such as divide by zero),
705: can't move it unless it's guaranteed to be executed
706: once loop is entered. Even a function call might
707: prevent the trap insn from being reached
708: (since it might exit!) */
709: && ! ((maybe_never || call_passed)
710: && may_trap_p (src)))
711: {
712: register struct movable *m;
713: register int regno = REGNO (SET_DEST (set));
714:
715: /* A potential lossage is where we have a case where two insns
716: can be combined as long as they are both in the loop, but
717: we move one of them outside the loop. For large loops,
718: this can lose. The most common case of this is the address
719: of a function being called.
720:
721: Therefore, if this register is marked as being used exactly
722: once if we are in a loop with calls (a "large loop"), see if
723: we can replace the usage of this register with the source
724: of this SET. If we can, delete this insn.
725:
726: Don't do this if P has a REG_RETVAL note or if we have
727: SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
728:
729: if (reg_single_usage && reg_single_usage[regno] != 0
730: && reg_single_usage[regno] != const0_rtx
731: && regno_first_uid[regno] == INSN_UID (p)
732: && (regno_last_uid[regno]
733: == INSN_UID (reg_single_usage[regno]))
734: && n_times_set[REGNO (SET_DEST (set))] == 1
735: && ! side_effects_p (SET_SRC (set))
736: && ! find_reg_note (p, REG_RETVAL, 0)
737: #ifdef SMALL_REGISTER_CLASSES
738: && ! (GET_CODE (SET_SRC (set)) == REG
739: && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)
740: #endif
741: /* This test is not redundant; SET_SRC (set) might be
742: a call-clobbered register and the life of REGNO
743: might span a call. */
744: && ! modified_between_p (SET_SRC (set), p,
745: reg_single_usage[regno])
746: && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
747: reg_single_usage[regno]))
748: {
749: /* Replace any usage in a REG_EQUAL note. */
750: REG_NOTES (reg_single_usage[regno])
751: = replace_rtx (REG_NOTES (reg_single_usage[regno]),
752: SET_DEST (set), SET_SRC (set));
753:
754: PUT_CODE (p, NOTE);
755: NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
756: NOTE_SOURCE_FILE (p) = 0;
757: n_times_set[regno] = 0;
758: continue;
759: }
760:
761: m = (struct movable *) alloca (sizeof (struct movable));
762: m->next = 0;
763: m->insn = p;
764: m->set_src = src;
765: m->dependencies = dependencies;
766: m->set_dest = SET_DEST (set);
767: m->force = 0;
768: m->consec = n_times_set[REGNO (SET_DEST (set))] - 1;
769: m->done = 0;
770: m->forces = 0;
771: m->partial = 0;
772: m->move_insn = move_insn;
773: m->is_equiv = (find_reg_note (p, REG_EQUIV, 0) != 0);
774: m->savemode = VOIDmode;
775: m->regno = regno;
776: /* Set M->cond if either invariant_p or consec_sets_invariant_p
777: returned 2 (only conditionally invariant). */
778: m->cond = ((tem | tem1 | tem2) > 1);
779: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
780: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
781: m->match = 0;
782: m->lifetime = (uid_luid[regno_last_uid[regno]]
783: - uid_luid[regno_first_uid[regno]]);
784: m->savings = n_times_used[regno];
785: if (find_reg_note (p, REG_RETVAL, 0))
786: m->savings += libcall_benefit (p);
787: n_times_set[regno] = move_insn ? -2 : -1;
788: /* Add M to the end of the chain MOVABLES. */
789: if (movables == 0)
790: movables = m;
791: else
792: last_movable->next = m;
793: last_movable = m;
794:
795: if (m->consec > 0)
796: {
797: /* Skip this insn, not checking REG_LIBCALL notes. */
798: p = NEXT_INSN (p);
799: /* Skip the consecutive insns, if there are any. */
800: p = skip_consec_insns (p, m->consec);
801: /* Back up to the last insn of the consecutive group. */
802: p = prev_nonnote_insn (p);
803:
804: /* We must now reset m->move_insn, m->is_equiv, and possibly
805: m->set_src to correspond to the effects of all the
806: insns. */
807: temp = find_reg_note (p, REG_EQUIV, 0);
808: if (temp)
809: m->set_src = XEXP (temp, 0), m->move_insn = 1;
810: else
811: {
812: temp = find_reg_note (p, REG_EQUAL, 0);
813: if (temp && CONSTANT_P (XEXP (temp, 0)))
814: m->set_src = XEXP (temp, 0), m->move_insn = 1;
815: else
816: m->move_insn = 0;
817:
818: }
819: m->is_equiv = (find_reg_note (p, REG_EQUIV, 0) != 0);
820: }
821: }
822: /* If this register is always set within a STRICT_LOW_PART
823: or set to zero, then its high bytes are constant.
824: So clear them outside the loop and within the loop
825: just load the low bytes.
826: We must check that the machine has an instruction to do so.
827: Also, if the value loaded into the register
828: depends on the same register, this cannot be done. */
829: else if (SET_SRC (set) == const0_rtx
830: && GET_CODE (NEXT_INSN (p)) == INSN
831: && (set1 = single_set (NEXT_INSN (p)))
832: && GET_CODE (set1) == SET
833: && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
834: && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
835: && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
836: == SET_DEST (set))
837: && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
838: {
839: register int regno = REGNO (SET_DEST (set));
840: if (n_times_set[regno] == 2)
841: {
842: register struct movable *m;
843: m = (struct movable *) alloca (sizeof (struct movable));
844: m->next = 0;
845: m->insn = p;
846: m->set_dest = SET_DEST (set);
847: m->dependencies = 0;
848: m->force = 0;
849: m->consec = 0;
850: m->done = 0;
851: m->forces = 0;
852: m->move_insn = 0;
853: m->partial = 1;
854: /* If the insn may not be executed on some cycles,
855: we can't clear the whole reg; clear just high part.
856: Not even if the reg is used only within this loop.
857: Consider this:
858: while (1)
859: while (s != t) {
860: if (foo ()) x = *s;
861: use (x);
862: }
863: Clearing x before the inner loop could clobber a value
864: being saved from the last time around the outer loop.
865: However, if the reg is not used outside this loop
866: and all uses of the register are in the same
867: basic block as the store, there is no problem.
868:
869: If this insn was made by loop, we don't know its
870: INSN_LUID and hence must make a conservative
871: assumption. */
872: m->global = (INSN_UID (p) >= max_uid_for_loop
873: || (uid_luid[regno_last_uid[regno]]
874: > INSN_LUID (end))
875: || (uid_luid[regno_first_uid[regno]]
876: < INSN_LUID (p))
877: || (labels_in_range_p
878: (p, uid_luid[regno_first_uid[regno]])));
879: if (maybe_never && m->global)
880: m->savemode = GET_MODE (SET_SRC (set1));
881: else
882: m->savemode = VOIDmode;
883: m->regno = regno;
884: m->cond = 0;
885: m->match = 0;
886: m->lifetime = (uid_luid[regno_last_uid[regno]]
887: - uid_luid[regno_first_uid[regno]]);
888: m->savings = 1;
889: n_times_set[regno] = -1;
890: /* Add M to the end of the chain MOVABLES. */
891: if (movables == 0)
892: movables = m;
893: else
894: last_movable->next = m;
895: last_movable = m;
896: }
897: }
898: }
899: /* Past a call insn, we get to insns which might not be executed
900: because the call might exit. This matters for insns that trap.
901: Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
902: so they don't count. */
903: else if (GET_CODE (p) == CALL_INSN && ! in_libcall)
904: call_passed = 1;
905: /* Past a label or a jump, we get to insns for which we
906: can't count on whether or how many times they will be
907: executed during each iteration. Therefore, we can
908: only move out sets of trivial variables
909: (those not used after the loop). */
910: /* This code appears in three places, once in scan_loop, and twice
911: in strength_reduce. */
912: else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
913: /* If we enter the loop in the middle, and scan around to the
914: beginning, don't set maybe_never for that. This must be an
915: unconditional jump, otherwise the code at the top of the
916: loop might never be executed. Unconditional jumps are
917: followed a by barrier then loop end. */
918: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
919: && NEXT_INSN (NEXT_INSN (p)) == end
920: && simplejump_p (p)))
921: maybe_never = 1;
922: /* At the virtual top of a converted loop, insns are again known to
923: be executed: logically, the loop begins here even though the exit
924: code has been duplicated. */
925: else if (GET_CODE (p) == NOTE
926: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
927: maybe_never = call_passed = 0;
928: }
929:
930: /* If one movable subsumes another, ignore that other. */
931:
932: ignore_some_movables (movables);
933:
934: /* For each movable insn, see if the reg that it loads
935: leads when it dies right into another conditionally movable insn.
936: If so, record that the second insn "forces" the first one,
937: since the second can be moved only if the first is. */
938:
939: force_movables (movables);
940:
941: /* See if there are multiple movable insns that load the same value.
942: If there are, make all but the first point at the first one
943: through the `match' field, and add the priorities of them
944: all together as the priority of the first. */
945:
946: combine_movables (movables, nregs);
947:
948: /* Now consider each movable insn to decide whether it is worth moving.
949: Store 0 in n_times_set for each reg that is moved. */
950:
951: move_movables (movables, threshold,
952: insn_count, loop_start, end, nregs);
953:
954: /* Now candidates that still are negative are those not moved.
955: Change n_times_set to indicate that those are not actually invariant. */
956: for (i = 0; i < nregs; i++)
957: if (n_times_set[i] < 0)
958: n_times_set[i] = n_times_used[i];
959:
960: if (flag_strength_reduce)
961: strength_reduce (scan_start, end, loop_top,
962: insn_count, loop_start, end);
963: }
964:
965: /* Add elements to *OUTPUT to record all the pseudo-regs
966: mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
967:
968: void
969: record_excess_regs (in_this, not_in_this, output)
970: rtx in_this, not_in_this;
971: rtx *output;
972: {
973: enum rtx_code code;
974: char *fmt;
975: int i;
976:
977: code = GET_CODE (in_this);
978:
979: switch (code)
980: {
981: case PC:
982: case CC0:
983: case CONST_INT:
984: case CONST_DOUBLE:
985: case CONST:
986: case SYMBOL_REF:
987: case LABEL_REF:
988: return;
989:
990: case REG:
991: if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
992: && ! reg_mentioned_p (in_this, not_in_this))
993: *output = gen_rtx (EXPR_LIST, VOIDmode, in_this, *output);
994: return;
995: }
996:
997: fmt = GET_RTX_FORMAT (code);
998: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
999: {
1000: int j;
1001:
1002: switch (fmt[i])
1003: {
1004: case 'E':
1005: for (j = 0; j < XVECLEN (in_this, i); j++)
1006: record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1007: break;
1008:
1009: case 'e':
1010: record_excess_regs (XEXP (in_this, i), not_in_this, output);
1011: break;
1012: }
1013: }
1014: }
1015:
1016: /* Check what regs are referred to in the libcall block ending with INSN,
1017: aside from those mentioned in the equivalent value.
1018: If there are none, return 0.
1019: If there are one or more, return an EXPR_LIST containing all of them. */
1020:
1021: static rtx
1022: libcall_other_reg (insn, equiv)
1023: rtx insn, equiv;
1024: {
1025: rtx note = find_reg_note (insn, REG_RETVAL, 0);
1026: rtx p = XEXP (note, 0);
1027: rtx output = 0;
1028:
1029: /* First, find all the regs used in the libcall block
1030: that are not mentioned as inputs to the result. */
1031:
1032: while (p != insn)
1033: {
1034: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1035: || GET_CODE (p) == CALL_INSN)
1036: record_excess_regs (PATTERN (p), equiv, &output);
1037: p = NEXT_INSN (p);
1038: }
1039:
1040: return output;
1041: }
1042:
1043: /* Return 1 if all uses of REG
1044: are between INSN and the end of the basic block. */
1045:
1046: static int
1047: reg_in_basic_block_p (insn, reg)
1048: rtx insn, reg;
1049: {
1050: int regno = REGNO (reg);
1051: rtx p;
1052:
1053: if (regno_first_uid[regno] != INSN_UID (insn))
1054: return 0;
1055:
1056: /* Search this basic block for the already recorded last use of the reg. */
1057: for (p = insn; p; p = NEXT_INSN (p))
1058: {
1059: switch (GET_CODE (p))
1060: {
1061: case NOTE:
1062: break;
1063:
1064: case INSN:
1065: case CALL_INSN:
1066: /* Ordinary insn: if this is the last use, we win. */
1067: if (regno_last_uid[regno] == INSN_UID (p))
1068: return 1;
1069: break;
1070:
1071: case JUMP_INSN:
1072: /* Jump insn: if this is the last use, we win. */
1073: if (regno_last_uid[regno] == INSN_UID (p))
1074: return 1;
1075: /* Otherwise, it's the end of the basic block, so we lose. */
1076: return 0;
1077:
1078: case CODE_LABEL:
1079: case BARRIER:
1080: /* It's the end of the basic block, so we lose. */
1081: return 0;
1082: }
1083: }
1084:
1085: /* The "last use" doesn't follow the "first use"?? */
1086: abort ();
1087: }
1088:
1089: /* Compute the benefit of eliminating the insns in the block whose
1090: last insn is LAST. This may be a group of insns used to compute a
1091: value directly or can contain a library call. */
1092:
1093: static int
1094: libcall_benefit (last)
1095: rtx last;
1096: {
1097: rtx insn;
1098: int benefit = 0;
1099:
1100: for (insn = XEXP (find_reg_note (last, REG_RETVAL, 0), 0);
1101: insn != last; insn = NEXT_INSN (insn))
1102: {
1103: if (GET_CODE (insn) == CALL_INSN)
1104: benefit += 10; /* Assume at least this many insns in a library
1105: routine. */
1106: else if (GET_CODE (insn) == INSN
1107: && GET_CODE (PATTERN (insn)) != USE
1108: && GET_CODE (PATTERN (insn)) != CLOBBER)
1109: benefit++;
1110: }
1111:
1112: return benefit;
1113: }
1114:
1115: /* Skip COUNT insns from INSN, counting library calls as 1 insn. */
1116:
1117: static rtx
1118: skip_consec_insns (insn, count)
1119: rtx insn;
1120: int count;
1121: {
1122: for (; count > 0; count--)
1123: {
1124: rtx temp;
1125:
1126: /* If first insn of libcall sequence, skip to end. */
1127: /* Do this at start of loop, since INSN is guaranteed to
1128: be an insn here. */
1129: if (GET_CODE (insn) != NOTE
1130: && (temp = find_reg_note (insn, REG_LIBCALL, 0)))
1131: insn = XEXP (temp, 0);
1132:
1133: do insn = NEXT_INSN (insn);
1134: while (GET_CODE (insn) == NOTE);
1135: }
1136:
1137: return insn;
1138: }
1139:
1140: /* Ignore any movable whose insn falls within a libcall
1141: which is part of another movable.
1142: We make use of the fact that the movable for the libcall value
1143: was made later and so appears later on the chain. */
1144:
1145: static void
1146: ignore_some_movables (movables)
1147: struct movable *movables;
1148: {
1149: register struct movable *m, *m1;
1150:
1151: for (m = movables; m; m = m->next)
1152: {
1153: /* Is this a movable for the value of a libcall? */
1154: rtx note = find_reg_note (m->insn, REG_RETVAL, 0);
1155: if (note)
1156: {
1157: rtx insn;
1158: /* Check for earlier movables inside that range,
1159: and mark them invalid. We cannot use LUIDs here because
1160: insns created by loop.c for prior loops don't have LUIDs.
1161: Rather than reject all such insns from movables, we just
1162: explicitly check each insn in the libcall (since invariant
1163: libcalls aren't that common). */
1164: for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1165: for (m1 = movables; m1 != m; m1 = m1->next)
1166: if (m1->insn == insn)
1167: m1->done = 1;
1168: }
1169: }
1170: }
1171:
1172: /* For each movable insn, see if the reg that it loads
1173: leads when it dies right into another conditionally movable insn.
1174: If so, record that the second insn "forces" the first one,
1175: since the second can be moved only if the first is. */
1176:
1177: static void
1178: force_movables (movables)
1179: struct movable *movables;
1180: {
1181: register struct movable *m, *m1;
1182: for (m1 = movables; m1; m1 = m1->next)
1183: /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
1184: if (!m1->partial && !m1->done)
1185: {
1186: int regno = m1->regno;
1187: for (m = m1->next; m; m = m->next)
1188: /* ??? Could this be a bug? What if CSE caused the
1189: register of M1 to be used after this insn?
1190: Since CSE does not update regno_last_uid,
1191: this insn M->insn might not be where it dies.
1192: But very likely this doesn't matter; what matters is
1193: that M's reg is computed from M1's reg. */
1194: if (INSN_UID (m->insn) == regno_last_uid[regno]
1195: && !m->done)
1196: break;
1197: if (m != 0 && m->set_src == m1->set_dest
1198: /* If m->consec, m->set_src isn't valid. */
1199: && m->consec == 0)
1200: m = 0;
1201:
1202: /* Increase the priority of the moving the first insn
1203: since it permits the second to be moved as well. */
1204: if (m != 0)
1205: {
1206: m->forces = m1;
1207: m1->lifetime += m->lifetime;
1208: m1->savings += m1->savings;
1209: }
1210: }
1211: }
1212:
1213: /* Find invariant expressions that are equal and can be combined into
1214: one register. */
1215:
1216: static void
1217: combine_movables (movables, nregs)
1218: struct movable *movables;
1219: int nregs;
1220: {
1221: register struct movable *m;
1222: char *matched_regs = (char *) alloca (nregs);
1223: enum machine_mode mode;
1224:
1225: /* Regs that are set more than once are not allowed to match
1226: or be matched. I'm no longer sure why not. */
1227: /* Perhaps testing m->consec_sets would be more appropriate here? */
1228:
1229: for (m = movables; m; m = m->next)
1230: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial)
1231: {
1232: register struct movable *m1;
1233: int regno = m->regno;
1234: rtx reg_note, reg_note1;
1235:
1236: bzero (matched_regs, nregs);
1237: matched_regs[regno] = 1;
1238:
1239: for (m1 = movables; m1; m1 = m1->next)
1240: if (m != m1 && m1->match == 0 && n_times_used[m1->regno] == 1
1241: /* A reg used outside the loop mustn't be eliminated. */
1242: && !m1->global
1243: /* A reg used for zero-extending mustn't be eliminated. */
1244: && !m1->partial
1245: && (matched_regs[m1->regno]
1246: ||
1247: (
1248: /* Can combine regs with different modes loaded from the
1249: same constant only if the modes are the same or
1250: if both are integer modes with M wider or the same
1251: width as M1. The check for integer is redundant, but
1252: safe, since the only case of differing destination
1253: modes with equal sources is when both sources are
1254: VOIDmode, i.e., CONST_INT. */
1255: (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1256: || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1257: && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1258: && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1259: >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1260: /* See if the source of M1 says it matches M. */
1261: && ((GET_CODE (m1->set_src) == REG
1262: && matched_regs[REGNO (m1->set_src)])
1263: || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1264: movables))))
1265: && ((m->dependencies == m1->dependencies)
1266: || rtx_equal_p (m->dependencies, m1->dependencies)))
1267: {
1268: m->lifetime += m1->lifetime;
1269: m->savings += m1->savings;
1270: m1->done = 1;
1271: m1->match = m;
1272: matched_regs[m1->regno] = 1;
1273: }
1274: }
1275:
1276: /* Now combine the regs used for zero-extension.
1277: This can be done for those not marked `global'
1278: provided their lives don't overlap. */
1279:
1280: for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1281: mode = GET_MODE_WIDER_MODE (mode))
1282: {
1283: register struct movable *m0 = 0;
1284:
1285: /* Combine all the registers for extension from mode MODE.
1286: Don't combine any that are used outside this loop. */
1287: for (m = movables; m; m = m->next)
1288: if (m->partial && ! m->global
1289: && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1290: {
1291: register struct movable *m1;
1292: int first = uid_luid[regno_first_uid[m->regno]];
1293: int last = uid_luid[regno_last_uid[m->regno]];
1294:
1295: if (m0 == 0)
1296: {
1297: /* First one: don't check for overlap, just record it. */
1298: m0 = m;
1299: continue;
1300: }
1301:
1302: /* Make sure they extend to the same mode.
1303: (Almost always true.) */
1304: if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1305: continue;
1306:
1307: /* We already have one: check for overlap with those
1308: already combined together. */
1309: for (m1 = movables; m1 != m; m1 = m1->next)
1310: if (m1 == m0 || (m1->partial && m1->match == m0))
1311: if (! (uid_luid[regno_first_uid[m1->regno]] > last
1312: || uid_luid[regno_last_uid[m1->regno]] < first))
1313: goto overlap;
1314:
1315: /* No overlap: we can combine this with the others. */
1316: m0->lifetime += m->lifetime;
1317: m0->savings += m->savings;
1318: m->done = 1;
1319: m->match = m0;
1320:
1321: overlap: ;
1322: }
1323: }
1324: }
1325:
1326: /* Return 1 if regs X and Y will become the same if moved. */
1327:
1328: static int
1329: regs_match_p (x, y, movables)
1330: rtx x, y;
1331: struct movable *movables;
1332: {
1333: int xn = REGNO (x);
1334: int yn = REGNO (y);
1335: struct movable *mx, *my;
1336:
1337: for (mx = movables; mx; mx = mx->next)
1338: if (mx->regno == xn)
1339: break;
1340:
1341: for (my = movables; my; my = my->next)
1342: if (my->regno == yn)
1343: break;
1344:
1345: return (mx && my
1346: && ((mx->match == my->match && mx->match != 0)
1347: || mx->match == my
1348: || mx == my->match));
1349: }
1350:
1351: /* Return 1 if X and Y are identical-looking rtx's.
1352: This is the Lisp function EQUAL for rtx arguments.
1353:
1354: If two registers are matching movables or a movable register and an
1355: equivalent constant, consider them equal. */
1356:
1357: static int
1358: rtx_equal_for_loop_p (x, y, movables)
1359: rtx x, y;
1360: struct movable *movables;
1361: {
1362: register int i;
1363: register int j;
1364: register struct movable *m;
1365: register enum rtx_code code;
1366: register char *fmt;
1367:
1368: if (x == y)
1369: return 1;
1370: if (x == 0 || y == 0)
1371: return 0;
1372:
1373: code = GET_CODE (x);
1374:
1375: /* If we have a register and a constant, they may sometimes be
1376: equal. */
1377: if (GET_CODE (x) == REG && n_times_set[REGNO (x)] == -2
1378: && CONSTANT_P (y))
1379: for (m = movables; m; m = m->next)
1380: if (m->move_insn && m->regno == REGNO (x)
1381: && rtx_equal_p (m->set_src, y))
1382: return 1;
1383:
1384: else if (GET_CODE (y) == REG && n_times_set[REGNO (y)] == -2
1385: && CONSTANT_P (x))
1386: for (m = movables; m; m = m->next)
1387: if (m->move_insn && m->regno == REGNO (y)
1388: && rtx_equal_p (m->set_src, x))
1389: return 1;
1390:
1391: /* Otherwise, rtx's of different codes cannot be equal. */
1392: if (code != GET_CODE (y))
1393: return 0;
1394:
1395: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1396: (REG:SI x) and (REG:HI x) are NOT equivalent. */
1397:
1398: if (GET_MODE (x) != GET_MODE (y))
1399: return 0;
1400:
1401: /* These three types of rtx's can be compared nonrecursively. */
1402: if (code == REG)
1403: return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
1404:
1405: if (code == LABEL_REF)
1406: return XEXP (x, 0) == XEXP (y, 0);
1407: if (code == SYMBOL_REF)
1408: return XSTR (x, 0) == XSTR (y, 0);
1409:
1410: /* Compare the elements. If any pair of corresponding elements
1411: fail to match, return 0 for the whole things. */
1412:
1413: fmt = GET_RTX_FORMAT (code);
1414: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1415: {
1416: switch (fmt[i])
1417: {
1418: case 'i':
1419: if (XINT (x, i) != XINT (y, i))
1420: return 0;
1421: break;
1422:
1423: case 'E':
1424: /* Two vectors must have the same length. */
1425: if (XVECLEN (x, i) != XVECLEN (y, i))
1426: return 0;
1427:
1428: /* And the corresponding elements must match. */
1429: for (j = 0; j < XVECLEN (x, i); j++)
1430: if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0)
1431: return 0;
1432: break;
1433:
1434: case 'e':
1435: if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0)
1436: return 0;
1437: break;
1438:
1439: case 's':
1440: if (strcmp (XSTR (x, i), XSTR (y, i)))
1441: return 0;
1442: break;
1443:
1444: case 'u':
1445: /* These are just backpointers, so they don't matter. */
1446: break;
1447:
1448: case '0':
1449: break;
1450:
1451: /* It is believed that rtx's at this level will never
1452: contain anything but integers and other rtx's,
1453: except for within LABEL_REFs and SYMBOL_REFs. */
1454: default:
1455: abort ();
1456: }
1457: }
1458: return 1;
1459: }
1460:
1461: /* Scan MOVABLES, and move the insns that deserve to be moved.
1462: If two matching movables are combined, replace one reg with the
1463: other throughout. */
1464:
1465: static void
1466: move_movables (movables, threshold, insn_count, loop_start, end, nregs)
1467: struct movable *movables;
1468: int threshold;
1469: int insn_count;
1470: rtx loop_start;
1471: rtx end;
1472: int nregs;
1473: {
1474: rtx new_start = 0;
1475: register struct movable *m;
1476: register rtx p;
1477: /* Map of pseudo-register replacements to handle combining
1478: when we move several insns that load the same value
1479: into different pseudo-registers. */
1480: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
1481: char *already_moved = (char *) alloca (nregs);
1482:
1483: bzero (already_moved, nregs);
1484: bzero (reg_map, nregs * sizeof (rtx));
1485:
1486: num_movables = 0;
1487:
1488: for (m = movables; m; m = m->next)
1489: {
1490: /* Describe this movable insn. */
1491:
1492: if (loop_dump_stream)
1493: {
1494: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1495: INSN_UID (m->insn), m->regno, m->lifetime);
1496: if (m->consec > 0)
1497: fprintf (loop_dump_stream, "consec %d, ", m->consec);
1498: if (m->cond)
1499: fprintf (loop_dump_stream, "cond ");
1500: if (m->force)
1501: fprintf (loop_dump_stream, "force ");
1502: if (m->global)
1503: fprintf (loop_dump_stream, "global ");
1504: if (m->done)
1505: fprintf (loop_dump_stream, "done ");
1506: if (m->move_insn)
1507: fprintf (loop_dump_stream, "move-insn ");
1508: if (m->match)
1509: fprintf (loop_dump_stream, "matches %d ",
1510: INSN_UID (m->match->insn));
1511: if (m->forces)
1512: fprintf (loop_dump_stream, "forces %d ",
1513: INSN_UID (m->forces->insn));
1514: }
1515:
1516: /* Count movables. Value used in heuristics in strength_reduce. */
1517: num_movables++;
1518:
1519: /* Ignore the insn if it's already done (it matched something else).
1520: Otherwise, see if it is now safe to move. */
1521:
1522: if (!m->done
1523: && (! m->cond
1524: || (1 == invariant_p (m->set_src)
1525: && (m->dependencies == 0
1526: || 1 == invariant_p (m->dependencies))
1527: && (m->consec == 0
1528: || 1 == consec_sets_invariant_p (m->set_dest,
1529: m->consec + 1,
1530: m->insn))))
1531: && (! m->forces || m->forces->done))
1532: {
1533: register int regno;
1534: register rtx p;
1535: int savings = m->savings;
1536:
1537: /* We have an insn that is safe to move.
1538: Compute its desirability. */
1539:
1540: p = m->insn;
1541: regno = m->regno;
1542:
1543: if (loop_dump_stream)
1544: fprintf (loop_dump_stream, "savings %d ", savings);
1545:
1546: if (moved_once[regno])
1547: {
1548: insn_count *= 2;
1549:
1550: if (loop_dump_stream)
1551: fprintf (loop_dump_stream, "halved since already moved ");
1552: }
1553:
1554: /* An insn MUST be moved if we already moved something else
1555: which is safe only if this one is moved too: that is,
1556: if already_moved[REGNO] is nonzero. */
1557:
1558: /* An insn is desirable to move if the new lifetime of the
1559: register is no more than THRESHOLD times the old lifetime.
1560: If it's not desirable, it means the loop is so big
1561: that moving won't speed things up much,
1562: and it is liable to make register usage worse. */
1563:
1564: /* It is also desirable to move if it can be moved at no
1565: extra cost because something else was already moved. */
1566:
1567: if (already_moved[regno]
1568: || (threshold * savings * m->lifetime) >= insn_count
1569: || (m->forces && m->forces->done
1570: && n_times_used[m->forces->regno] == 1))
1571: {
1572: int count;
1573: register struct movable *m1;
1574: rtx first;
1575:
1576: /* Now move the insns that set the reg. */
1577:
1578: if (m->partial && m->match)
1579: {
1580: rtx newpat, i1;
1581: rtx r1, r2;
1582: /* Find the end of this chain of matching regs.
1583: Thus, we load each reg in the chain from that one reg.
1584: And that reg is loaded with 0 directly,
1585: since it has ->match == 0. */
1586: for (m1 = m; m1->match; m1 = m1->match);
1587: newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1588: SET_DEST (PATTERN (m1->insn)));
1589: i1 = emit_insn_before (newpat, loop_start);
1590:
1591: /* Mark the moved, invariant reg as being allowed to
1592: share a hard reg with the other matching invariant. */
1593: REG_NOTES (i1) = REG_NOTES (m->insn);
1594: r1 = SET_DEST (PATTERN (m->insn));
1595: r2 = SET_DEST (PATTERN (m1->insn));
1596: regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, r1,
1597: gen_rtx (EXPR_LIST, VOIDmode, r2,
1598: regs_may_share));
1599: delete_insn (m->insn);
1600:
1601: if (new_start == 0)
1602: new_start = i1;
1603:
1604: if (loop_dump_stream)
1605: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1606: }
1607: /* If we are to re-generate the item being moved with a
1608: new move insn, first delete what we have and then emit
1609: the move insn before the loop. */
1610: else if (m->move_insn)
1611: {
1612: rtx i1, temp;
1613:
1614: for (count = m->consec; count >= 0; count--)
1615: {
1616: /* If this is the first insn of a library call sequence,
1617: skip to the end. */
1618: if (GET_CODE (p) != NOTE
1619: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
1620: p = XEXP (temp, 0);
1621:
1622: /* If this is the last insn of a libcall sequence, then
1623: delete every insn in the sequence except the last.
1624: The last insn is handled in the normal manner. */
1625: if (GET_CODE (p) != NOTE
1626: && (temp = find_reg_note (p, REG_RETVAL, 0)))
1627: {
1628: temp = XEXP (temp, 0);
1629: while (temp != p)
1630: temp = delete_insn (temp);
1631: }
1632:
1633: p = delete_insn (p);
1634: }
1635:
1636: start_sequence ();
1637: emit_move_insn (m->set_dest, m->set_src);
1638: temp = gen_sequence ();
1639: end_sequence ();
1640:
1641: i1 = emit_insn_before (temp, loop_start);
1642: if (! find_reg_note (i1, REG_EQUAL, 0))
1643: REG_NOTES (i1)
1644: = gen_rtx (EXPR_LIST,
1645: m->is_equiv ? REG_EQUIV : REG_EQUAL,
1646: m->set_src, REG_NOTES (i1));
1647:
1648: if (loop_dump_stream)
1649: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1650:
1651: /* The more regs we move, the less we like moving them. */
1652: threshold -= 3;
1653: }
1654: else
1655: {
1656: for (count = m->consec; count >= 0; count--)
1657: {
1658: rtx i1, temp;
1659:
1660: /* If first insn of libcall sequence, skip to end. */
1661: /* Do this at start of loop, since p is guaranteed to
1662: be an insn here. */
1663: if (GET_CODE (p) != NOTE
1664: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
1665: p = XEXP (temp, 0);
1666:
1667: /* If last insn of libcall sequence, move all
1668: insns except the last before the loop. The last
1669: insn is handled in the normal manner. */
1670: if (GET_CODE (p) != NOTE
1671: && (temp = find_reg_note (p, REG_RETVAL, 0)))
1672: {
1673: rtx fn_address = 0;
1674: rtx fn_reg = 0;
1675: rtx fn_address_insn = 0;
1676:
1677: first = 0;
1678: for (temp = XEXP (temp, 0); temp != p;
1679: temp = NEXT_INSN (temp))
1680: {
1681: rtx body;
1682: rtx n;
1683: rtx next;
1684:
1685: if (GET_CODE (temp) == NOTE)
1686: continue;
1687:
1688: body = PATTERN (temp);
1689:
1690: /* Find the next insn after TEMP,
1691: not counting USE or NOTE insns. */
1692: for (next = NEXT_INSN (temp); next != p;
1693: next = NEXT_INSN (next))
1694: if (! (GET_CODE (next) == INSN
1695: && GET_CODE (PATTERN (next)) == USE)
1696: && GET_CODE (next) != NOTE)
1697: break;
1698:
1699: /* If that is the call, this may be the insn
1700: that loads the function address.
1701:
1702: Extract the function address from the insn
1703: that loads it into a register.
1704: If this insn was cse'd, we get incorrect code.
1705:
1706: So emit a new move insn that copies the
1707: function address into the register that the
1708: call insn will use. flow.c will delete any
1709: redundant stores that we have created. */
1710: if (GET_CODE (next) == CALL_INSN
1711: && GET_CODE (body) == SET
1712: && GET_CODE (SET_DEST (body)) == REG
1713: && (n = find_reg_note (temp, REG_EQUAL, 0)))
1714: {
1715: fn_reg = SET_SRC (body);
1716: if (GET_CODE (fn_reg) != REG)
1717: fn_reg = SET_DEST (body);
1718: fn_address = XEXP (n, 0);
1719: fn_address_insn = temp;
1720: }
1721: /* We have the call insn.
1722: If it uses the register we suspect it might,
1723: load it with the correct address directly. */
1724: if (GET_CODE (temp) == CALL_INSN
1725: && fn_address != 0
1726: && reg_mentioned_p (fn_reg, body))
1727: emit_insn_after (gen_move_insn (fn_reg,
1728: fn_address),
1729: fn_address_insn);
1730:
1731: if (GET_CODE (temp) == CALL_INSN)
1732: i1 = emit_call_insn_before (body, loop_start);
1733: else
1734: i1 = emit_insn_before (body, loop_start);
1735: if (first == 0)
1736: first = i1;
1737: if (temp == fn_address_insn)
1738: fn_address_insn = i1;
1739: REG_NOTES (i1) = REG_NOTES (temp);
1740: delete_insn (temp);
1741: }
1742: }
1743: if (m->savemode != VOIDmode)
1744: {
1745: /* P sets REG to zero; but we should clear only
1746: the bits that are not covered by the mode
1747: m->savemode. */
1748: rtx reg = m->set_dest;
1749: rtx sequence;
1750: rtx tem;
1751:
1752: start_sequence ();
1753: tem = expand_binop
1754: (GET_MODE (reg), and_optab, reg,
1755: gen_rtx (CONST_INT, VOIDmode,
1756: ((1 << GET_MODE_BITSIZE (m->savemode)))
1757: - 1),
1758: reg, 1, OPTAB_LIB_WIDEN);
1759: if (tem == 0)
1760: abort ();
1761: if (tem != reg)
1762: emit_move_insn (reg, tem);
1763: sequence = gen_sequence ();
1764: end_sequence ();
1765: i1 = emit_insn_before (sequence, loop_start);
1766: }
1767: else if (GET_CODE (p) == CALL_INSN)
1768: i1 = emit_call_insn_before (PATTERN (p), loop_start);
1769: else
1770: i1 = emit_insn_before (PATTERN (p), loop_start);
1771:
1772: REG_NOTES (i1) = REG_NOTES (p);
1773:
1774: if (new_start == 0)
1775: new_start = i1;
1776:
1777: if (loop_dump_stream)
1778: fprintf (loop_dump_stream, " moved to %d",
1779: INSN_UID (i1));
1780:
1781: #if 0
1782: /* This isn't needed because REG_NOTES is copied
1783: below and is wrong since P might be a PARALLEL. */
1784: if (REG_NOTES (i1) == 0
1785: && ! m->partial /* But not if it's a zero-extend clr. */
1786: && ! m->global /* and not if used outside the loop
1787: (since it might get set outside). */
1788: && CONSTANT_P (SET_SRC (PATTERN (p))))
1789: REG_NOTES (i1)
1790: = gen_rtx (EXPR_LIST, REG_EQUAL,
1791: SET_SRC (PATTERN (p)), REG_NOTES (i1));
1792: #endif
1793:
1794: /* If library call, now fix the REG_NOTES that contain
1795: insn pointers, namely REG_LIBCALL on FIRST
1796: and REG_RETVAL on I1. */
1797: if (temp = find_reg_note (i1, REG_RETVAL, 0))
1798: {
1799: XEXP (temp, 0) = first;
1800: temp = find_reg_note (first, REG_LIBCALL, 0);
1801: XEXP (temp, 0) = i1;
1802: }
1803:
1804: delete_insn (p);
1805: do p = NEXT_INSN (p);
1806: while (p && GET_CODE (p) == NOTE);
1807: }
1808:
1809: /* The more regs we move, the less we like moving them. */
1810: threshold -= 3;
1811: }
1812:
1813: /* Any other movable that loads the same register
1814: MUST be moved. */
1815: already_moved[regno] = 1;
1816:
1817: /* This reg has been moved out of one loop. */
1818: moved_once[regno] = 1;
1819:
1820: /* The reg set here is now invariant. */
1821: if (! m->partial)
1822: n_times_set[regno] = 0;
1823:
1824: m->done = 1;
1825:
1826: /* Change the length-of-life info for the register
1827: to say it lives at least the full length of this loop.
1828: This will help guide optimizations in outer loops. */
1829:
1830: if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start))
1831: /* This is the old insn before all the moved insns.
1832: We can't use the moved insn because it is out of range
1833: in uid_luid. Only the old insns have luids. */
1834: regno_first_uid[regno] = INSN_UID (loop_start);
1835: if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end))
1836: regno_last_uid[regno] = INSN_UID (end);
1837:
1838: /* Combine with this moved insn any other matching movables. */
1839:
1840: if (! m->partial)
1841: for (m1 = movables; m1; m1 = m1->next)
1842: if (m1->match == m)
1843: {
1844: rtx temp;
1845:
1846: /* Schedule the reg loaded by M1
1847: for replacement so that shares the reg of M.
1848: If the modes differ (only possible in restricted
1849: circumstances, make a SUBREG. */
1850: if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
1851: reg_map[m1->regno] = m->set_dest;
1852: else
1853: reg_map[m1->regno]
1854: = gen_lowpart_common (GET_MODE (m1->set_dest),
1855: m->set_dest);
1856:
1857: /* Get rid of the matching insn
1858: and prevent further processing of it. */
1859: m1->done = 1;
1860:
1861: /* if library call, delete all insn except last, which
1862: is deleted below */
1863: if (temp = find_reg_note (m1->insn, REG_RETVAL, 0))
1864: {
1865: for (temp = XEXP (temp, 0); temp != m1->insn;
1866: temp = NEXT_INSN (temp))
1867: delete_insn (temp);
1868: }
1869: delete_insn (m1->insn);
1870:
1871: /* Any other movable that loads the same register
1872: MUST be moved. */
1873: already_moved[m1->regno] = 1;
1874:
1875: /* The reg merged here is now invariant,
1876: if the reg it matches is invariant. */
1877: if (! m->partial)
1878: n_times_set[m1->regno] = 0;
1879: }
1880: }
1881: else if (loop_dump_stream)
1882: fprintf (loop_dump_stream, "not desirable");
1883: }
1884: else if (loop_dump_stream && !m->match)
1885: fprintf (loop_dump_stream, "not safe");
1886:
1887: if (loop_dump_stream)
1888: fprintf (loop_dump_stream, "\n");
1889: }
1890:
1891: if (new_start == 0)
1892: new_start = loop_start;
1893:
1894: /* Go through all the instructions in the loop, making
1895: all the register substitutions scheduled in REG_MAP. */
1896: for (p = new_start; p != end; p = NEXT_INSN (p))
1897: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1898: || GET_CODE (p) == CALL_INSN)
1899: {
1900: replace_regs (PATTERN (p), reg_map, nregs, 0);
1901: replace_regs (REG_NOTES (p), reg_map, nregs, 0);
1902: }
1903: }
1904:
1905: #if 0
1906: /* Scan X and replace the address of any MEM in it with ADDR.
1907: REG is the address that MEM should have before the replacement. */
1908:
1909: static void
1910: replace_call_address (x, reg, addr)
1911: rtx x, reg, addr;
1912: {
1913: register enum rtx_code code;
1914: register int i;
1915: register char *fmt;
1916:
1917: if (x == 0)
1918: return;
1919: code = GET_CODE (x);
1920: switch (code)
1921: {
1922: case PC:
1923: case CC0:
1924: case CONST_INT:
1925: case CONST_DOUBLE:
1926: case CONST:
1927: case SYMBOL_REF:
1928: case LABEL_REF:
1929: case REG:
1930: return;
1931:
1932: case SET:
1933: /* Short cut for very common case. */
1934: replace_call_address (XEXP (x, 1), reg, addr);
1935: return;
1936:
1937: case CALL:
1938: /* Short cut for very common case. */
1939: replace_call_address (XEXP (x, 0), reg, addr);
1940: return;
1941:
1942: case MEM:
1943: /* If this MEM uses a reg other than the one we expected,
1944: something is wrong. */
1945: if (XEXP (x, 0) != reg)
1946: abort ();
1947: XEXP (x, 0) = addr;
1948: return;
1949: }
1950:
1951: fmt = GET_RTX_FORMAT (code);
1952: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1953: {
1954: if (fmt[i] == 'e')
1955: replace_call_address (XEXP (x, i), reg, addr);
1956: if (fmt[i] == 'E')
1957: {
1958: register int j;
1959: for (j = 0; j < XVECLEN (x, i); j++)
1960: replace_call_address (XVECEXP (x, i, j), reg, addr);
1961: }
1962: }
1963: }
1964: #endif
1965:
1966: /* Return the number of memory refs to addresses that vary
1967: in the rtx X. */
1968:
1969: static int
1970: count_nonfixed_reads (x)
1971: rtx x;
1972: {
1973: register enum rtx_code code;
1974: register int i;
1975: register char *fmt;
1976: int value;
1977:
1978: if (x == 0)
1979: return 0;
1980:
1981: code = GET_CODE (x);
1982: switch (code)
1983: {
1984: case PC:
1985: case CC0:
1986: case CONST_INT:
1987: case CONST_DOUBLE:
1988: case CONST:
1989: case SYMBOL_REF:
1990: case LABEL_REF:
1991: case REG:
1992: return 0;
1993:
1994: case MEM:
1995: return ((invariant_p (XEXP (x, 0)) != 1)
1996: + count_nonfixed_reads (XEXP (x, 0)));
1997: }
1998:
1999: value = 0;
2000: fmt = GET_RTX_FORMAT (code);
2001: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2002: {
2003: if (fmt[i] == 'e')
2004: value += count_nonfixed_reads (XEXP (x, i));
2005: if (fmt[i] == 'E')
2006: {
2007: register int j;
2008: for (j = 0; j < XVECLEN (x, i); j++)
2009: value += count_nonfixed_reads (XVECEXP (x, i, j));
2010: }
2011: }
2012: return value;
2013: }
2014:
2015:
2016: #if 0
2017: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
2018: Replace it with an instruction to load just the low bytes
2019: if the machine supports such an instruction,
2020: and insert above LOOP_START an instruction to clear the register. */
2021:
2022: static void
2023: constant_high_bytes (p, loop_start)
2024: rtx p, loop_start;
2025: {
2026: register rtx new;
2027: register int insn_code_number;
2028:
2029: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
2030: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
2031:
2032: new = gen_rtx (SET, VOIDmode,
2033: gen_rtx (STRICT_LOW_PART, VOIDmode,
2034: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
2035: SET_DEST (PATTERN (p)),
2036: 0)),
2037: XEXP (SET_SRC (PATTERN (p)), 0));
2038: insn_code_number = recog (new, p);
2039:
2040: if (insn_code_number)
2041: {
2042: register int i;
2043:
2044: /* Clear destination register before the loop. */
2045: emit_insn_before (gen_rtx (SET, VOIDmode,
2046: SET_DEST (PATTERN (p)),
2047: const0_rtx),
2048: loop_start);
2049:
2050: /* Inside the loop, just load the low part. */
2051: PATTERN (p) = new;
2052: }
2053: }
2054: #endif
2055:
2056: /* Scan a loop setting the variables `unknown_address_altered',
2057: `num_mem_sets', `loop_continue', loops_enclosed' and `loop_has_call'.
2058: Also, fill in the array `loop_store_mems'. */
2059:
2060: static void
2061: prescan_loop (start, end)
2062: rtx start, end;
2063: {
2064: register int level = 1;
2065: register rtx insn;
2066:
2067: unknown_address_altered = 0;
2068: loop_has_call = 0;
2069: loop_store_mems_idx = 0;
2070:
2071: num_mem_sets = 0;
2072: loops_enclosed = 1;
2073: loop_continue = 0;
2074:
2075: for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2076: insn = NEXT_INSN (insn))
2077: {
2078: if (GET_CODE (insn) == NOTE)
2079: {
2080: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2081: {
2082: ++level;
2083: /* Count number of loops contained in this one. */
2084: loops_enclosed++;
2085: }
2086: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2087: {
2088: --level;
2089: if (level == 0)
2090: {
2091: end = insn;
2092: break;
2093: }
2094: }
2095: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
2096: {
2097: if (level == 1)
2098: loop_continue = insn;
2099: }
2100: }
2101: else if (GET_CODE (insn) == CALL_INSN)
2102: {
2103: unknown_address_altered = 1;
2104: loop_has_call = 1;
2105: }
2106: else
2107: {
2108: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2109: note_stores (PATTERN (insn), note_addr_stored);
2110: }
2111: }
2112: }
2113:
2114: /* Scan the function looking for loops. Record the start and end of each loop.
2115: Also mark as invalid loops any loops that contain a setjmp or are branched
2116: to from outside the loop. */
2117:
2118: static void
2119: find_and_verify_loops (f)
2120: rtx f;
2121: {
2122: rtx insn;
2123: int current_loop = -1;
2124: int next_loop = -1;
2125: int loop;
2126:
2127: /* If there are jumps to undefined labels,
2128: treat them as jumps out of any/all loops.
2129: This also avoids writing past end of tables when there are no loops. */
2130: uid_loop_num[0] = -1;
2131:
2132: /* Find boundaries of loops, mark which loops are contained within
2133: loops, and invalidate loops that have setjmp. */
2134:
2135: for (insn = f; insn; insn = NEXT_INSN (insn))
2136: {
2137: if (GET_CODE (insn) == NOTE)
2138: switch (NOTE_LINE_NUMBER (insn))
2139: {
2140: case NOTE_INSN_LOOP_BEG:
2141: loop_number_loop_starts[++next_loop] = insn;
2142: loop_number_loop_ends[next_loop] = 0;
2143: loop_outer_loop[next_loop] = current_loop;
2144: loop_invalid[next_loop] = 0;
2145: loop_number_exit_labels[next_loop] = 0;
2146: current_loop = next_loop;
2147: break;
2148:
2149: case NOTE_INSN_SETJMP:
2150: /* In this case, we must invalidate our current loop and any
2151: enclosing loop. */
2152: for (loop = current_loop; loop != -1; loop = loop_outer_loop[loop])
2153: {
2154: loop_invalid[loop] = 1;
2155: if (loop_dump_stream)
2156: fprintf (loop_dump_stream,
2157: "\nLoop at %d ignored due to setjmp.\n",
2158: INSN_UID (loop_number_loop_starts[loop]));
2159: }
2160: break;
2161:
2162: case NOTE_INSN_LOOP_END:
2163: if (current_loop == -1)
2164: abort ();
2165:
2166: loop_number_loop_ends[current_loop] = insn;
2167: current_loop = loop_outer_loop[current_loop];
2168: break;
2169:
2170: }
2171:
2172: /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2173: enclosing loop, but this doesn't matter. */
2174: uid_loop_num[INSN_UID (insn)] = current_loop;
2175: }
2176:
2177: /* Now scan all JUMP_INSN's in the function. If any branches into a loop
2178: that it is not contained within, that loop is marked invalid.
2179:
2180: Also look for blocks of code ending in an unconditional branch that
2181: exits the loop. If such a block is surrounded by a conditional
2182: branch around the block, move the block elsewhere (see below) and
2183: invert the jump to point to the code block. This may eliminate a
2184: label in our loop and will simplify processing by both us and a
2185: possible second cse pass. */
2186:
2187: for (insn = f; insn; insn = NEXT_INSN (insn))
2188: if (GET_CODE (insn) == JUMP_INSN)
2189: {
2190: int this_loop_num = uid_loop_num[INSN_UID (insn)];
2191:
2192: mark_loop_jump (PATTERN (insn), this_loop_num);
2193:
2194: /* See if this is an unconditional branch outside the loop. */
2195: if (this_loop_num != -1
2196: && (GET_CODE (PATTERN (insn)) == RETURN
2197: || (simplejump_p (insn)
2198: && (uid_loop_num[INSN_UID (JUMP_LABEL (insn))]
2199: != this_loop_num))))
2200: {
2201: rtx p;
2202: rtx our_next = next_real_insn (insn);
2203:
2204: /* Go backwards until we reach the start of the loop, a label,
2205: or a JUMP_INSN. */
2206: for (p = PREV_INSN (insn);
2207: GET_CODE (p) != CODE_LABEL
2208: && ! (GET_CODE (p) == NOTE
2209: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2210: && GET_CODE (p) != JUMP_INSN;
2211: p = PREV_INSN (p))
2212: ;
2213:
2214: /* If we stopped on a JUMP_INSN to the next insn after INSN,
2215: we have a block of code to try to move.
2216:
2217: We look backward and then forward from the target of INSN
2218: to find a BARRIER at the same loop depth as the target.
2219: If we find such a BARRIER, we make a new label for the start
2220: of the block, invert the jump in P and point it to that label,
2221: and move the block of code to the spot we found. */
2222:
2223: if (GET_CODE (p) == JUMP_INSN
2224: && JUMP_LABEL (p) != 0
2225: && condjump_p (p)
2226: && ! simplejump_p (p)
2227: && next_real_insn (JUMP_LABEL (p)) == our_next)
2228: {
2229: rtx target
2230: = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2231: int target_loop_num = uid_loop_num[INSN_UID (target)];
2232: rtx loc;
2233:
2234: for (loc = target; loc; loc = PREV_INSN (loc))
2235: if (GET_CODE (loc) == BARRIER
2236: && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2237: break;
2238:
2239: if (loc == 0)
2240: for (loc = target; loc; loc = NEXT_INSN (loc))
2241: if (GET_CODE (loc) == BARRIER
2242: && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2243: break;
2244:
2245: if (loc)
2246: {
2247: rtx cond_label = JUMP_LABEL (p);
2248: rtx new_label = get_label_after (p);
2249:
2250: /* Ensure our label doesn't go away. */
2251: LABEL_NUSES (cond_label)++;
2252:
2253: /* Verify that uid_loop_num is large enough and that
2254: we can invert P. */
2255: if (INSN_UID (new_label) < max_uid_for_loop
2256: && invert_jump (p, new_label))
2257: {
2258: rtx q, r;
2259:
2260: /* Include the BARRIER after INSN and copy the
2261: block after LOC. */
2262: squeeze_notes (new_label, NEXT_INSN (insn));
2263: reorder_insns (new_label, NEXT_INSN (insn), loc);
2264:
2265: /* All those insns are now in TARGET_LOOP_NUM. */
2266: for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
2267: q = NEXT_INSN (q))
2268: uid_loop_num[INSN_UID (q)] = target_loop_num;
2269:
2270: /* The label jumped to by INSN is no longer a loop exit.
2271: Unless INSN does not have a label (e.g., it is a
2272: RETURN insn), search loop_number_exit_labels to find
2273: its label_ref, and remove it. Also turn off
2274: LABEL_OUTSIDE_LOOP_P bit. */
2275: if (JUMP_LABEL (insn))
2276: {
2277: for (q = 0,
2278: r = loop_number_exit_labels[this_loop_num];
2279: r; q = r, r = LABEL_NEXTREF (r))
2280: if (XEXP (r, 0) == JUMP_LABEL (insn))
2281: {
2282: LABEL_OUTSIDE_LOOP_P (r) = 0;
2283: if (q)
2284: LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2285: else
2286: loop_number_exit_labels[this_loop_num]
2287: = LABEL_NEXTREF (r);
2288: break;
2289: }
2290:
2291: /* If we didn't find it, then something is wrong. */
2292: if (! r)
2293: abort ();
2294: }
2295:
2296: /* P is now a jump outside the loop, so it must be put
2297: in loop_number_exit_labels, and marked as such.
2298: The easiest way to do this is to just call
2299: mark_loop_jump again for P. */
2300: mark_loop_jump (PATTERN (p), this_loop_num);
2301:
2302: /* If INSN now jumps to the insn after it,
2303: delete INSN. */
2304: if (JUMP_LABEL (insn) != 0
2305: && (next_real_insn (JUMP_LABEL (insn))
2306: == next_real_insn (insn)))
2307: delete_insn (insn);
2308: }
2309:
2310: /* Continue the loop after where the conditional
2311: branch used to jump, since the only branch insn
2312: in the block (if it still remains) is an inter-loop
2313: branch and hence needs no processing. */
2314: insn = NEXT_INSN (cond_label);
2315:
2316: if (--LABEL_NUSES (cond_label) == 0)
2317: delete_insn (cond_label);
2318: }
2319: }
2320: }
2321: }
2322: }
2323:
2324: /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2325: loops it is contained in, mark the target loop invalid.
2326:
2327: For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2328:
2329: static void
2330: mark_loop_jump (x, loop_num)
2331: rtx x;
2332: int loop_num;
2333: {
2334: int dest_loop;
2335: int outer_loop;
2336: int i;
2337:
2338: switch (GET_CODE (x))
2339: {
2340: case PC:
2341: case USE:
2342: case CLOBBER:
2343: case REG:
2344: case MEM:
2345: case CONST_INT:
2346: case CONST_DOUBLE:
2347: case RETURN:
2348: return;
2349:
2350: case CONST:
2351: /* There could be a label reference in here. */
2352: mark_loop_jump (XEXP (x, 0), loop_num);
2353: return;
2354:
2355: case PLUS:
2356: case MINUS:
2357: case MULT:
2358: case LSHIFT:
2359: mark_loop_jump (XEXP (x, 0), loop_num);
2360: mark_loop_jump (XEXP (x, 1), loop_num);
2361: return;
2362:
2363: case SIGN_EXTEND:
2364: case ZERO_EXTEND:
2365: mark_loop_jump (XEXP (x, 0), loop_num);
2366: return;
2367:
2368: case LABEL_REF:
2369: dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))];
2370:
2371: /* Link together all labels that branch outside the loop. This
2372: is used by final_[bg]iv_value and the loop unrolling code. Also
2373: mark this LABEL_REF so we know that this branch should predict
2374: false. */
2375:
2376: if (dest_loop != loop_num && loop_num != -1)
2377: {
2378: LABEL_OUTSIDE_LOOP_P (x) = 1;
2379: LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
2380: loop_number_exit_labels[loop_num] = x;
2381: }
2382:
2383: /* If this is inside a loop, but not in the current loop or one enclosed
2384: by it, it invalidates at least one loop. */
2385:
2386: if (dest_loop == -1)
2387: return;
2388:
2389: /* We must invalidate every nested loop containing the target of this
2390: label, except those that also contain the jump insn. */
2391:
2392: for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
2393: {
2394: /* Stop when we reach a loop that also contains the jump insn. */
2395: for (outer_loop = loop_num; outer_loop != -1;
2396: outer_loop = loop_outer_loop[outer_loop])
2397: if (dest_loop == outer_loop)
2398: return;
2399:
2400: /* If we get here, we know we need to invalidate a loop. */
2401: if (loop_dump_stream && ! loop_invalid[dest_loop])
2402: fprintf (loop_dump_stream,
2403: "\nLoop at %d ignored due to multiple entry points.\n",
2404: INSN_UID (loop_number_loop_starts[dest_loop]));
2405:
2406: loop_invalid[dest_loop] = 1;
2407: }
2408: return;
2409:
2410: case SET:
2411: /* If this is not setting pc, ignore. */
2412: if (SET_DEST (x) == pc_rtx)
2413: mark_loop_jump (SET_SRC (x), loop_num);
2414: return;
2415:
2416: case IF_THEN_ELSE:
2417: mark_loop_jump (XEXP (x, 1), loop_num);
2418: mark_loop_jump (XEXP (x, 2), loop_num);
2419: return;
2420:
2421: case PARALLEL:
2422: case ADDR_VEC:
2423: for (i = 0; i < XVECLEN (x, 0); i++)
2424: mark_loop_jump (XVECEXP (x, 0, i), loop_num);
2425: return;
2426:
2427: case ADDR_DIFF_VEC:
2428: for (i = 0; i < XVECLEN (x, 1); i++)
2429: mark_loop_jump (XVECEXP (x, 1, i), loop_num);
2430: return;
2431:
2432: default:
2433: /* Nothing else should occur in a JUMP_INSN. */
2434: abort ();
2435: }
2436: }
2437:
2438: /* Return nonzero if there is a label in the range from
2439: insn INSN to and including the insn whose luid is END
2440: INSN must have an assigned luid (i.e., it must not have
2441: been previously created by loop.c). */
2442:
2443: static int
2444: labels_in_range_p (insn, end)
2445: rtx insn;
2446: int end;
2447: {
2448: while (insn && INSN_LUID (insn) <= end)
2449: {
2450: if (GET_CODE (insn) == CODE_LABEL)
2451: return 1;
2452: insn = NEXT_INSN (insn);
2453: }
2454:
2455: return 0;
2456: }
2457:
2458: /* Record that a memory reference X is being set. */
2459:
2460: static void
2461: note_addr_stored (x)
2462: rtx x;
2463: {
2464: register int i;
2465:
2466: if (x == 0 || GET_CODE (x) != MEM)
2467: return;
2468:
2469: /* Count number of memory writes.
2470: This affects heuristics in strength_reduce. */
2471: num_mem_sets++;
2472:
2473: if (unknown_address_altered)
2474: return;
2475:
2476: for (i = 0; i < loop_store_mems_idx; i++)
2477: if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0))
2478: && MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
2479: {
2480: /* We are storing at the same address as previously noted. Save the
2481: wider reference, treating BLKmode as wider. */
2482: if (GET_MODE (x) == BLKmode
2483: || (GET_MODE_SIZE (GET_MODE (x))
2484: > GET_MODE_SIZE (GET_MODE (loop_store_mems[i]))))
2485: loop_store_mems[i] = x;
2486: break;
2487: }
2488:
2489: if (i == NUM_STORES)
2490: unknown_address_altered = 1;
2491:
2492: else if (i == loop_store_mems_idx)
2493: loop_store_mems[loop_store_mems_idx++] = x;
2494: }
2495:
2496: /* Return nonzero if the rtx X is invariant over the current loop.
2497:
2498: The value is 2 if we refer to something only conditionally invariant.
2499:
2500: If `unknown_address_altered' is nonzero, no memory ref is invariant.
2501: Otherwise, a memory ref is invariant if it does not conflict with
2502: anything stored in `loop_store_mems'. */
2503:
2504: int
2505: invariant_p (x)
2506: register rtx x;
2507: {
2508: register int i;
2509: register enum rtx_code code;
2510: register char *fmt;
2511: int conditional = 0;
2512:
2513: if (x == 0)
2514: return 1;
2515: code = GET_CODE (x);
2516: switch (code)
2517: {
2518: case CONST_INT:
2519: case CONST_DOUBLE:
2520: case SYMBOL_REF:
2521: case CONST:
2522: return 1;
2523:
2524: case LABEL_REF:
2525: /* A LABEL_REF is normally invariant, however, if we are unrolling
2526: loops, and this label is inside the loop, then it isn't invariant.
2527: This is because each unrolled copy of the loop body will have
2528: a copy of this label. If this was invariant, then an insn loading
2529: the address of this label into a register might get moved outside
2530: the loop, and then each loop body would end up using the same label.
2531:
2532: We don't know the loop bounds here though, so just fail for all
2533: labels. */
2534: if (flag_unroll_loops)
2535: return 0;
2536: else
2537: return 1;
2538:
2539: case PC:
2540: case CC0:
2541: case UNSPEC_VOLATILE:
2542: return 0;
2543:
2544: case REG:
2545: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
2546: since the reg might be set by initialization within the loop. */
2547: if (x == frame_pointer_rtx || x == arg_pointer_rtx)
2548: return 1;
2549: if (loop_has_call
2550: && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
2551: return 0;
2552: if (n_times_set[REGNO (x)] < 0)
2553: return 2;
2554: return n_times_set[REGNO (x)] == 0;
2555:
2556: case MEM:
2557: /* Read-only items (such as constants in a constant pool) are
2558: invariant if their address is. */
2559: if (RTX_UNCHANGING_P (x))
2560: break;
2561:
2562: /* If we filled the table (or had a subroutine call), any location
2563: in memory could have been clobbered. */
2564: if (unknown_address_altered
2565: /* Don't mess with volatile memory references. */
2566: || MEM_VOLATILE_P (x))
2567: return 0;
2568:
2569: /* See if there is any dependence between a store and this load. */
2570: for (i = loop_store_mems_idx - 1; i >= 0; i--)
2571: if (true_dependence (loop_store_mems[i], x))
2572: return 0;
2573:
2574: /* It's not invalidated by a store in memory
2575: but we must still verify the address is invariant. */
2576: break;
2577:
2578: case ASM_OPERANDS:
2579: /* Don't mess with insns declared volatile. */
2580: if (MEM_VOLATILE_P (x))
2581: return 0;
2582: }
2583:
2584: fmt = GET_RTX_FORMAT (code);
2585: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2586: {
2587: if (fmt[i] == 'e')
2588: {
2589: int tem = invariant_p (XEXP (x, i));
2590: if (tem == 0)
2591: return 0;
2592: if (tem == 2)
2593: conditional = 1;
2594: }
2595: else if (fmt[i] == 'E')
2596: {
2597: register int j;
2598: for (j = 0; j < XVECLEN (x, i); j++)
2599: {
2600: int tem = invariant_p (XVECEXP (x, i, j));
2601: if (tem == 0)
2602: return 0;
2603: if (tem == 2)
2604: conditional = 1;
2605: }
2606:
2607: }
2608: }
2609:
2610: return 1 + conditional;
2611: }
2612:
2613: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
2614: which is SIZE bytes starting at BASE. */
2615:
2616: int
2617: addr_overlap_p (other, base, size)
2618: rtx other;
2619: rtx base;
2620: int size;
2621: {
2622: int start = 0, end;
2623:
2624: if (GET_CODE (base) == CONST)
2625: base = XEXP (base, 0);
2626: if (GET_CODE (base) == PLUS
2627: && GET_CODE (XEXP (base, 1)) == CONST_INT)
2628: {
2629: start = INTVAL (XEXP (base, 1));
2630: base = XEXP (base, 0);
2631: }
2632:
2633: end = start + size;
2634: return refers_to_mem_p (other, base, start, end);
2635: }
2636:
2637: /* Return nonzero if all the insns in the loop that set REG
2638: are INSN and the immediately following insns,
2639: and if each of those insns sets REG in an invariant way
2640: (not counting uses of REG in them).
2641:
2642: The value is 2 if some of these insns are only conditionally invariant.
2643:
2644: We assume that INSN itself is the first set of REG
2645: and that its source is invariant. */
2646:
2647: static int
2648: consec_sets_invariant_p (reg, n_sets, insn)
2649: int n_sets;
2650: rtx reg, insn;
2651: {
2652: register rtx p = insn;
2653: register int regno = REGNO (reg);
2654: rtx temp;
2655: /* Number of sets we have to insist on finding after INSN. */
2656: int count = n_sets - 1;
2657: int old = n_times_set[regno];
2658: int value = 0;
2659: int this;
2660:
2661: /* If N_SETS hit the limit, we can't rely on its value. */
2662: if (n_sets == 127)
2663: return 0;
2664:
2665: n_times_set[regno] = 0;
2666:
2667: while (count > 0)
2668: {
2669: register enum rtx_code code;
2670: rtx set;
2671:
2672: p = NEXT_INSN (p);
2673: code = GET_CODE (p);
2674:
2675: /* If library call, skip to end of of it. */
2676: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
2677: p = XEXP (temp, 0);
2678:
2679: this = 0;
2680: if (code == INSN
2681: && (set = single_set (p))
2682: && GET_CODE (SET_DEST (set)) == REG
2683: && REGNO (SET_DEST (set)) == regno)
2684: {
2685: this = invariant_p (SET_SRC (set));
2686: if (this != 0)
2687: value |= this;
2688: else if (temp = find_reg_note (p, REG_EQUAL, 0))
2689: {
2690: this = invariant_p (XEXP (temp, 0));
2691: if (this != 0)
2692: value |= this;
2693: }
2694: }
2695: if (this != 0)
2696: count--;
2697: else if (code != NOTE)
2698: {
2699: n_times_set[regno] = old;
2700: return 0;
2701: }
2702: }
2703:
2704: n_times_set[regno] = old;
2705: /* If invariant_p ever returned 2, we return 2. */
2706: return 1 + (value & 2);
2707: }
2708:
2709: #if 0
2710: /* I don't think this condition is sufficient to allow INSN
2711: to be moved, so we no longer test it. */
2712:
2713: /* Return 1 if all insns in the basic block of INSN and following INSN
2714: that set REG are invariant according to TABLE. */
2715:
2716: static int
2717: all_sets_invariant_p (reg, insn, table)
2718: rtx reg, insn;
2719: short *table;
2720: {
2721: register rtx p = insn;
2722: register int regno = REGNO (reg);
2723:
2724: while (1)
2725: {
2726: register enum rtx_code code;
2727: p = NEXT_INSN (p);
2728: code = GET_CODE (p);
2729: if (code == CODE_LABEL || code == JUMP_INSN)
2730: return 1;
2731: if (code == INSN && GET_CODE (PATTERN (p)) == SET
2732: && GET_CODE (SET_DEST (PATTERN (p))) == REG
2733: && REGNO (SET_DEST (PATTERN (p))) == regno)
2734: {
2735: if (!invariant_p (SET_SRC (PATTERN (p)), table))
2736: return 0;
2737: }
2738: }
2739: }
2740: #endif /* 0 */
2741:
2742: /* Look at all uses (not sets) of registers in X. For each, if it is
2743: the single use, set USAGE[REGNO] to INSN; if there was a previous use in
2744: a different insn, set USAGE[REGNO] to const0_rtx. */
2745:
2746: static void
2747: find_single_use_in_loop (insn, x, usage)
2748: rtx insn;
2749: rtx x;
2750: rtx *usage;
2751: {
2752: enum rtx_code code = GET_CODE (x);
2753: char *fmt = GET_RTX_FORMAT (code);
2754: int i, j;
2755:
2756: if (code == REG)
2757: usage[REGNO (x)]
2758: = (usage[REGNO (x)] != 0 && usage[REGNO (x)] != insn)
2759: ? const0_rtx : insn;
2760:
2761: else if (code == SET)
2762: {
2763: /* Don't count SET_DEST if it is a REG; otherwise count things
2764: in SET_DEST because if a register is partially modified, it won't
2765: show up as a potential movable so we don't care how USAGE is set
2766: for it. */
2767: if (GET_CODE (SET_DEST (x)) != REG)
2768: find_single_use_in_loop (insn, SET_DEST (x), usage);
2769: find_single_use_in_loop (insn, SET_SRC (x), usage);
2770: }
2771: else
2772: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2773: {
2774: if (fmt[i] == 'e' && XEXP (x, i) != 0)
2775: find_single_use_in_loop (insn, XEXP (x, i), usage);
2776: else if (fmt[i] == 'E')
2777: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2778: find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
2779: }
2780: }
2781:
2782: /* Increment N_TIMES_SET at the index of each register
2783: that is modified by an insn between FROM and TO.
2784: If the value of an element of N_TIMES_SET becomes 127 or more,
2785: stop incrementing it, to avoid overflow.
2786:
2787: Store in SINGLE_USAGE[I] the single insn in which register I is
2788: used, if it is only used once. Otherwise, it is set to 0 (for no
2789: uses) or const0_rtx for more than one use. This parameter may be zero,
2790: in which case this processing is not done.
2791:
2792: Store in *COUNT_PTR the number of actual instruction
2793: in the loop. We use this to decide what is worth moving out. */
2794:
2795: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
2796: In that case, it is the insn that last set reg n. */
2797:
2798: static void
2799: count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
2800: register rtx from, to;
2801: char *may_not_move;
2802: rtx *single_usage;
2803: int *count_ptr;
2804: int nregs;
2805: {
2806: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
2807: register rtx insn;
2808: register int count = 0;
2809: register rtx dest;
2810:
2811: bzero (last_set, nregs * sizeof (rtx));
2812: for (insn = from; insn != to; insn = NEXT_INSN (insn))
2813: {
2814: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2815: {
2816: ++count;
2817:
2818: /* If requested, record registers that have exactly one use. */
2819: if (single_usage)
2820: {
2821: find_single_use_in_loop (insn, PATTERN (insn), single_usage);
2822:
2823: /* Include uses in REG_EQUAL notes. */
2824: if (REG_NOTES (insn))
2825: find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
2826: }
2827:
2828: if (GET_CODE (PATTERN (insn)) == CLOBBER
2829: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
2830: /* Don't move a reg that has an explicit clobber.
2831: We might do so sometimes, but it's not worth the pain. */
2832: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
2833:
2834: if (GET_CODE (PATTERN (insn)) == SET
2835: || GET_CODE (PATTERN (insn)) == CLOBBER)
2836: {
2837: dest = SET_DEST (PATTERN (insn));
2838: while (GET_CODE (dest) == SUBREG
2839: || GET_CODE (dest) == ZERO_EXTRACT
2840: || GET_CODE (dest) == SIGN_EXTRACT
2841: || GET_CODE (dest) == STRICT_LOW_PART)
2842: dest = XEXP (dest, 0);
2843: if (GET_CODE (dest) == REG)
2844: {
2845: register int regno = REGNO (dest);
2846: /* If this is the first setting of this reg
2847: in current basic block, and it was set before,
2848: it must be set in two basic blocks, so it cannot
2849: be moved out of the loop. */
2850: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2851: may_not_move[regno] = 1;
2852: /* If this is not first setting in current basic block,
2853: see if reg was used in between previous one and this.
2854: If so, neither one can be moved. */
2855: if (last_set[regno] != 0
2856: && reg_used_between_p (dest, last_set[regno], insn))
2857: may_not_move[regno] = 1;
2858: if (n_times_set[regno] < 127)
2859: ++n_times_set[regno];
2860: last_set[regno] = insn;
2861: }
2862: }
2863: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2864: {
2865: register int i;
2866: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2867: {
2868: register rtx x = XVECEXP (PATTERN (insn), 0, i);
2869: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
2870: /* Don't move a reg that has an explicit clobber.
2871: It's not worth the pain to try to do it correctly. */
2872: may_not_move[REGNO (XEXP (x, 0))] = 1;
2873:
2874: if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
2875: {
2876: dest = SET_DEST (x);
2877: while (GET_CODE (dest) == SUBREG
2878: || GET_CODE (dest) == ZERO_EXTRACT
2879: || GET_CODE (dest) == SIGN_EXTRACT
2880: || GET_CODE (dest) == STRICT_LOW_PART)
2881: dest = XEXP (dest, 0);
2882: if (GET_CODE (dest) == REG)
2883: {
2884: register int regno = REGNO (dest);
2885: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2886: may_not_move[regno] = 1;
2887: if (last_set[regno] != 0
2888: && reg_used_between_p (dest, last_set[regno], insn))
2889: may_not_move[regno] = 1;
2890: if (n_times_set[regno] < 127)
2891: ++n_times_set[regno];
2892: last_set[regno] = insn;
2893: }
2894: }
2895: }
2896: }
2897: }
2898: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
2899: bzero (last_set, nregs * sizeof (rtx));
2900: }
2901: *count_ptr = count;
2902: }
2903:
2904: /* Given a loop that is bounded by LOOP_START and LOOP_END
2905: and that is entered at SCAN_START,
2906: return 1 if the register set in SET contained in insn INSN is used by
2907: any insn that precedes INSN in cyclic order starting
2908: from the loop entry point.
2909:
2910: We don't want to use INSN_LUID here because if we restrict INSN to those
2911: that have a valid INSN_LUID, it means we cannot move an invariant out
2912: from an inner loop past two loops. */
2913:
2914: static int
2915: loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
2916: rtx set, insn, loop_start, scan_start, loop_end;
2917: {
2918: rtx reg = SET_DEST (set);
2919: rtx p;
2920:
2921: /* Scan forward checking for register usage. If we hit INSN, we
2922: are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
2923: for (p = scan_start; p != insn; p = NEXT_INSN (p))
2924: {
2925: if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
2926: && reg_overlap_mentioned_p (reg, PATTERN (p)))
2927: return 1;
2928:
2929: if (p == loop_end)
2930: p = loop_start;
2931: }
2932:
2933: return 0;
2934: }
2935:
2936: /* A "basic induction variable" or biv is a pseudo reg that is set
2937: (within this loop) only by incrementing or decrementing it. */
2938: /* A "general induction variable" or giv is a pseudo reg whose
2939: value is a linear function of a biv. */
2940:
2941: /* Bivs are recognized by `basic_induction_var';
2942: Givs by `general_induct_var'. */
2943:
2944: /* Indexed by register number, indicates whether or not register is an
2945: induction variable, and if so what type. */
2946:
2947: enum iv_mode *reg_iv_type;
2948:
2949: /* Indexed by register number, contains pointer to `struct induction'
2950: if register is an induction variable. This holds general info for
2951: all induction variables. */
2952:
2953: struct induction **reg_iv_info;
2954:
2955: /* Indexed by register number, contains pointer to `struct iv_class'
2956: if register is a basic induction variable. This holds info describing
2957: the class (a related group) of induction variables that the biv belongs
2958: to. */
2959:
2960: struct iv_class **reg_biv_class;
2961:
2962: /* The head of a list which links together (via the next field)
2963: every iv class for the current loop. */
2964:
2965: struct iv_class *loop_iv_list;
2966:
2967: /* Communication with routines called via `note_stores'. */
2968:
2969: static rtx note_insn;
2970:
2971: /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
2972:
2973: static rtx addr_placeholder;
2974:
2975: /* ??? Unfinished optimizations, and possible future optimizations,
2976: for the strength reduction code. */
2977:
2978: /* ??? There is one more optimization you might be interested in doing: to
2979: allocate pseudo registers for frequently-accessed memory locations.
2980: If the same memory location is referenced each time around, it might
2981: be possible to copy it into a register before and out after.
2982: This is especially useful when the memory location is a variable which
2983: is in a stack slot because somewhere its address is taken. If the
2984: loop doesn't contain a function call and the variable isn't volatile,
2985: it is safe to keep the value in a register for the duration of the
2986: loop. One tricky thing is that the copying of the value back from the
2987: register has to be done on all exits from the loop. You need to check that
2988: all the exits from the loop go to the same place. */
2989:
2990: /* ??? The interaction of biv elimination, and recognition of 'constant'
2991: bivs, may cause problems. */
2992:
2993: /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
2994: performance problems.
2995:
2996: Perhaps don't eliminate things that can be combined with an addressing
2997: mode. Find all givs that have the same biv, mult_val, and add_val;
2998: then for each giv, check to see if its only use dies in a following
2999: memory address. If so, generate a new memory address and check to see
3000: if it is valid. If it is valid, then store the modified memory address,
3001: otherwise, mark the giv as not done so that it will get its own iv. */
3002:
3003: /* ??? Could try to optimize branches when it is known that a biv is always
3004: positive. */
3005:
3006: /* ??? When replace a biv in a compare insn, we should replace with closest
3007: giv so that an optimized branch can still be recognized by the combiner,
3008: e.g. the VAX acb insn. */
3009:
3010: /* ??? Many of the checks involving uid_luid could be simplified if regscan
3011: was rerun in loop_optimize whenever a register was added or moved.
3012: Also, some of the optimizations could be a little less conservative. */
3013:
3014: /* Perform strength reduction and induction variable elimination. */
3015:
3016: /* Pseudo registers created during this function will be beyond the last
3017: valid index in several tables including n_times_set and regno_last_uid.
3018: This does not cause a problem here, because the added registers cannot be
3019: givs outside of their loop, and hence will never be reconsidered.
3020: But scan_loop must check regnos to make sure they are in bounds. */
3021:
3022: static void
3023: strength_reduce (scan_start, end, loop_top, insn_count,
3024: loop_start, loop_end)
3025: rtx scan_start;
3026: rtx end;
3027: rtx loop_top;
3028: int insn_count;
3029: rtx loop_start;
3030: rtx loop_end;
3031: {
3032: rtx p;
3033: rtx set;
3034: rtx inc_val;
3035: rtx mult_val;
3036: rtx dest_reg;
3037: /* This is 1 if current insn is not executed at least once for every loop
3038: iteration. */
3039: int not_every_iteration = 0;
3040: /* Temporary list pointers for traversing loop_iv_list. */
3041: struct iv_class *bl, **backbl;
3042: /* Ratio of extra register life span we can justify
3043: for saving an instruction. More if loop doesn't call subroutines
3044: since in that case saving an insn makes more difference
3045: and more registers are available. */
3046: /* ??? could set this to last value of threshold in move_movables */
3047: int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3048: /* Map of pseudo-register replacements. */
3049: rtx *reg_map;
3050: int call_seen;
3051: rtx test;
3052: rtx end_insert_before;
3053:
3054: reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop
3055: * sizeof (enum iv_mode *));
3056: bzero ((char *) reg_iv_type, max_reg_before_loop * sizeof (enum iv_mode *));
3057: reg_iv_info = (struct induction **)
3058: alloca (max_reg_before_loop * sizeof (struct induction *));
3059: bzero ((char *) reg_iv_info, (max_reg_before_loop
3060: * sizeof (struct induction *)));
3061: reg_biv_class = (struct iv_class **)
3062: alloca (max_reg_before_loop * sizeof (struct iv_class *));
3063: bzero ((char *) reg_biv_class, (max_reg_before_loop
3064: * sizeof (struct iv_class *)));
3065:
3066: loop_iv_list = 0;
3067: addr_placeholder = gen_reg_rtx (Pmode);
3068:
3069: /* Save insn immediately after the loop_end. Insns inserted after loop_end
3070: must be put before this insn, so that they will appear in the right
3071: order (i.e. loop order). */
3072:
3073: end_insert_before = NEXT_INSN (loop_end);
3074:
3075: /* Scan through loop to find all possible bivs. */
3076:
3077: p = scan_start;
3078: while (1)
3079: {
3080: p = NEXT_INSN (p);
3081: /* At end of a straight-in loop, we are done.
3082: At end of a loop entered at the bottom, scan the top. */
3083: if (p == scan_start)
3084: break;
3085: if (p == end)
3086: {
3087: if (loop_top != 0)
3088: p = NEXT_INSN (loop_top);
3089: else
3090: break;
3091: if (p == scan_start)
3092: break;
3093: }
3094:
3095: if (GET_CODE (p) == INSN
3096: && (set = single_set (p))
3097: && GET_CODE (SET_DEST (set)) == REG)
3098: {
3099: dest_reg = SET_DEST (set);
3100: if (REGNO (dest_reg) < max_reg_before_loop
3101: && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
3102: && reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT)
3103: {
3104: if (basic_induction_var (SET_SRC (set), dest_reg,
3105: &inc_val, &mult_val))
3106: {
3107: /* It is a possible basic induction variable.
3108: Create and initialize an induction structure for it. */
3109:
3110: struct induction *v
3111: = (struct induction *) alloca (sizeof (struct induction));
3112:
3113: record_biv (v, p, dest_reg, inc_val, mult_val,
3114: not_every_iteration);
3115: reg_iv_type[REGNO (dest_reg)] = BASIC_INDUCT;
3116: }
3117: else if (REGNO (dest_reg) < max_reg_before_loop)
3118: reg_iv_type[REGNO (dest_reg)] = NOT_BASIC_INDUCT;
3119: }
3120: }
3121:
3122: /* Past a label or a jump, we get to insns for which we can't count
3123: on whether or how many times they will be executed during each
3124: iteration. */
3125: /* This code appears in three places, once in scan_loop, and twice
3126: in strength_reduce. */
3127: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3128: /* If we enter the loop in the middle, and scan around to the
3129: beginning, don't set not_every_iteration for that.
3130: This can be any kind of jump, since we want to know if insns
3131: will be executed if the loop is executed. */
3132: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3133: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3134: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3135: not_every_iteration = 1;
3136:
3137: /* At the virtual top of a converted loop, insns are again known to
3138: be executed each iteration: logically, the loop begins here
3139: even though the exit code has been duplicated. */
3140:
3141: else if (GET_CODE (p) == NOTE
3142: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3143: not_every_iteration = 0;
3144:
3145: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3146: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3147: or not an insn is known to be executed each iteration of the
3148: loop, whether or not any iterations are known to occur.
3149:
3150: Therefore, if we have just passed a label and have no more labels
3151: between here and the test insn of the loop, we know these insns
3152: will be executed each iteration. This can also happen if we
3153: have just passed a jump, for example, when there are nested loops. */
3154:
3155: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3156: && no_labels_between_p (p, loop_end))
3157: not_every_iteration = 0;
3158: }
3159:
3160: /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3161: Make a sanity check against n_times_set. */
3162: for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next)
3163: {
3164: if (reg_iv_type[bl->regno] != BASIC_INDUCT
3165: /* Above happens if register modified by subreg, etc. */
3166: /* Make sure it is not recognized as a basic induction var: */
3167: || n_times_set[bl->regno] != bl->biv_count
3168: /* If never incremented, it is invariant that we decided not to
3169: move. So leave it alone. */
3170: || ! bl->incremented)
3171: {
3172: if (loop_dump_stream)
3173: fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3174: bl->regno,
3175: (reg_iv_type[bl->regno] != BASIC_INDUCT
3176: ? "not induction variable"
3177: : (! bl->incremented ? "never incremented"
3178: : "count error")));
3179:
3180: reg_iv_type[bl->regno] = NOT_BASIC_INDUCT;
3181: *backbl = bl->next;
3182: }
3183: else
3184: {
3185: backbl = &bl->next;
3186:
3187: if (loop_dump_stream)
3188: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3189: }
3190: }
3191:
3192: /* Exit if there are no bivs. */
3193: if (! loop_iv_list)
3194: {
3195: /* Can still unroll the loop anyways, but indicate that there is no
3196: strength reduction info available. */
3197: if (flag_unroll_loops)
3198: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 0);
3199:
3200: return;
3201: }
3202:
3203: /* Find initial value for each biv by searching backwards from loop_start,
3204: halting at first label. Also record any test condition. */
3205:
3206: call_seen = 0;
3207: for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3208: {
3209: note_insn = p;
3210:
3211: if (GET_CODE (p) == CALL_INSN)
3212: call_seen = 1;
3213:
3214: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3215: || GET_CODE (p) == CALL_INSN)
3216: note_stores (PATTERN (p), record_initial);
3217:
3218: /* Record any test of a biv that branches around the loop if no store
3219: between it and the start of loop. We only care about tests with
3220: constants and registers and only certain of those. */
3221: if (GET_CODE (p) == JUMP_INSN
3222: && JUMP_LABEL (p) != 0
3223: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3224: && (test = get_condition_for_loop (p)) != 0
3225: && GET_CODE (XEXP (test, 0)) == REG
3226: && REGNO (XEXP (test, 0)) < max_reg_before_loop
3227: && (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3228: && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3229: && bl->init_insn == 0)
3230: {
3231: /* If an NE test, we have an initial value! */
3232: if (GET_CODE (test) == NE)
3233: {
3234: bl->init_insn = p;
3235: bl->init_set = gen_rtx (SET, VOIDmode,
3236: XEXP (test, 0), XEXP (test, 1));
3237: }
3238: else
3239: bl->initial_test = test;
3240: }
3241: }
3242:
3243: /* Look at the each biv and see if we can say anything better about its
3244: initial value from any initializing insns set up above. (This is done
3245: in two passes to avoid missing SETs in a PARALLEL.) */
3246: for (bl = loop_iv_list; bl; bl = bl->next)
3247: {
3248: rtx src;
3249:
3250: if (! bl->init_insn)
3251: continue;
3252:
3253: src = SET_SRC (bl->init_set);
3254:
3255: if (loop_dump_stream)
3256: fprintf (loop_dump_stream,
3257: "Biv %d initialized at insn %d: initial value ",
3258: bl->regno, INSN_UID (bl->init_insn));
3259:
3260: if (valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3261: {
3262: bl->initial_value = src;
3263:
3264: if (loop_dump_stream)
3265: {
3266: if (GET_CODE (src) == CONST_INT)
3267: fprintf (loop_dump_stream, "%d\n", INTVAL (src));
3268: else
3269: {
3270: print_rtl (loop_dump_stream, src);
3271: fprintf (loop_dump_stream, "\n");
3272: }
3273: }
3274: }
3275: else
3276: {
3277: /* Biv initial value is not simple move,
3278: so let it keep intial value of "itself". */
3279:
3280: if (loop_dump_stream)
3281: fprintf (loop_dump_stream, "is complex\n");
3282: }
3283: }
3284:
3285: /* Search the loop for general induction variables. */
3286:
3287: /* A register is a giv if: it is only set once, it is a function of a
3288: biv and a constant (or invariant), and it is not a biv. */
3289:
3290: not_every_iteration = 0;
3291: p = scan_start;
3292: while (1)
3293: {
3294: p = NEXT_INSN (p);
3295: /* At end of a straight-in loop, we are done.
3296: At end of a loop entered at the bottom, scan the top. */
3297: if (p == scan_start)
3298: break;
3299: if (p == end)
3300: {
3301: if (loop_top != 0)
3302: p = NEXT_INSN (loop_top);
3303: else
3304: break;
3305: if (p == scan_start)
3306: break;
3307: }
3308:
3309: /* Look for a general induction variable in a register. */
3310: if (GET_CODE (p) == INSN
3311: && (set = single_set (p))
3312: && GET_CODE (SET_DEST (set)) == REG
3313: && ! may_not_optimize[REGNO (SET_DEST (set))])
3314: {
3315: rtx src_reg;
3316: rtx add_val;
3317: rtx mult_val;
3318: int benefit;
3319: rtx regnote = 0;
3320:
3321: dest_reg = SET_DEST (set);
3322: if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
3323: continue;
3324:
3325: if (/* SET_SRC is a giv. */
3326: ((benefit = general_induction_var (SET_SRC (set),
3327: &src_reg, &add_val,
3328: &mult_val))
3329: /* Equivalent expression is a giv. */
3330: || ((regnote = find_reg_note (p, REG_EQUAL, 0))
3331: && (benefit = general_induction_var (XEXP (regnote, 0),
3332: &src_reg,
3333: &add_val, &mult_val))))
3334: /* Don't try to handle any regs made by loop optimization.
3335: We have nothing on them in regno_first_uid, etc. */
3336: && REGNO (dest_reg) < max_reg_before_loop
3337: /* Don't recognize a BASIC_INDUCT_VAR here. */
3338: && dest_reg != src_reg
3339: /* This must be the only place where the register is set. */
3340: && (n_times_set[REGNO (dest_reg)] == 1
3341: /* or all sets must be consecutive and make a giv. */
3342: || (benefit = consec_sets_giv (benefit, p,
3343: src_reg, dest_reg,
3344: &add_val, &mult_val))))
3345: {
3346: int count;
3347: struct induction *v
3348: = (struct induction *) alloca (sizeof (struct induction));
3349: rtx temp;
3350:
3351: /* If this is a library call, increase benefit. */
3352: if (find_reg_note (p, REG_RETVAL, 0))
3353: benefit += libcall_benefit (p);
3354:
3355: /* Skip the consecutive insns, if there are any. */
3356: for (count = n_times_set[REGNO (dest_reg)] - 1;
3357: count > 0; count--)
3358: {
3359: /* If first insn of libcall sequence, skip to end.
3360: Do this at start of loop, since INSN is guaranteed to
3361: be an insn here. */
3362: if (GET_CODE (p) != NOTE
3363: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
3364: p = XEXP (temp, 0);
3365:
3366: do p = NEXT_INSN (p);
3367: while (GET_CODE (p) == NOTE);
3368: }
3369:
3370: record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
3371: DEST_REG, not_every_iteration, 0, loop_start,
3372: loop_end);
3373:
3374: }
3375: }
3376:
3377: #ifndef DONT_REDUCE_ADDR
3378: /* Look for givs which are memory addresses. */
3379: /* This resulted in worse code on a VAX 8600. I wonder if it
3380: still does. */
3381: if (GET_CODE (p) == INSN)
3382: find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
3383: loop_end);
3384: #endif
3385:
3386: /* Update the status of whether giv can derive other givs. This can
3387: change when we pass a label or an insn that updates a biv. */
3388: if (GET_CODE (p) == INSN || GET_CODE (p) == CODE_LABEL)
3389: update_giv_derive (p);
3390:
3391: /* Past a label or a jump, we get to insns for which we can't count
3392: on whether or how many times they will be executed during each
3393: iteration. */
3394: /* This code appears in three places, once in scan_loop, and twice
3395: in strength_reduce. */
3396: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3397: /* If we enter the loop in the middle, and scan around
3398: to the beginning, don't set not_every_iteration for that.
3399: This can be any kind of jump, since we want to know if insns
3400: will be executed if the loop is executed. */
3401: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3402: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3403: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3404: not_every_iteration = 1;
3405:
3406: /* At the virtual top of a converted loop, insns are again known to
3407: be executed each iteration: logically, the loop begins here
3408: even though the exit code has been duplicated. */
3409:
3410: else if (GET_CODE (p) == NOTE
3411: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3412: not_every_iteration = 0;
3413:
3414: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3415: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3416: or not an insn is known to be executed each iteration of the
3417: loop, whether or not any iterations are known to occur.
3418:
3419: Therefore, if we have just passed a label and have no more labels
3420: between here and the test insn of the loop, we know these insns
3421: will be executed each iteration. */
3422:
3423: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3424: && no_labels_between_p (p, loop_end))
3425: not_every_iteration = 0;
3426: }
3427:
3428: /* Try to calculate and save the number of loop iterations. This is
3429: set to zero if the actual number can not be calculated. This must
3430: be called after all giv's have been identified, since otherwise it may
3431: fail if the iteration variable is a giv. */
3432:
3433: loop_n_iterations = loop_iterations (loop_start, loop_end);
3434:
3435: /* Now for each giv for which we still don't know whether or not it is
3436: replaceable, check to see if it is replaceable because its final value
3437: can be calculated. This must be done after loop_iterations is called,
3438: so that final_giv_value will work correctly. */
3439:
3440: for (bl = loop_iv_list; bl; bl = bl->next)
3441: {
3442: struct induction *v;
3443:
3444: for (v = bl->giv; v; v = v->next_iv)
3445: if (! v->replaceable && ! v->not_replaceable)
3446: check_final_value (v, loop_start, loop_end);
3447: }
3448:
3449: /* Try to prove that the loop counter variable (if any) is always
3450: nonnegative; if so, record that fact with a REG_NONNEG note
3451: so that "decrement and branch until zero" insn can be used. */
3452: check_dbra_loop (loop_end, insn_count, loop_start);
3453:
3454: /* Create reg_map to hold substitutions for replaceable giv regs. */
3455: reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
3456: bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
3457:
3458: /* Examine each iv class for feasibility of strength reduction/induction
3459: variable elimination. */
3460:
3461: for (bl = loop_iv_list; bl; bl = bl->next)
3462: {
3463: struct induction *v;
3464: int benefit;
3465: int all_reduced;
3466: rtx final_value = 0;
3467:
3468: /* Test whether it will be possible to eliminate this biv
3469: provided all givs are reduced. This is possible if either
3470: the reg is not used outside the loop, or we can compute
3471: what its final value will be.
3472:
3473: For architectures with a decrement_and_branch_until_zero insn,
3474: don't do this if we put a REG_NONNEG note on the endtest for
3475: this biv. */
3476:
3477: /* Compare against bl->init_insn rather than loop_start.
3478: We aren't concerned with any uses of the biv between
3479: init_insn and loop_start since these won't be affected
3480: by the value of the biv elsewhere in the function, so
3481: long as init_insn doesn't use the biv itself.
3482: March 14, 1989 -- [email protected] */
3483:
3484: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
3485: && bl->init_insn
3486: && INSN_UID (bl->init_insn) < max_uid_for_loop
3487: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
3488: #ifdef HAVE_decrement_and_branch_until_zero
3489: && ! bl->nonneg
3490: #endif
3491: && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3492: || ((final_value = final_biv_value (bl, loop_start, loop_end))
3493: #ifdef HAVE_decrement_and_branch_until_zero
3494: && ! bl->nonneg
3495: #endif
3496: ))
3497: bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
3498: threshold, insn_count);
3499: else
3500: {
3501: if (loop_dump_stream)
3502: {
3503: fprintf (loop_dump_stream,
3504: "Cannot eliminate biv %d.\n",
3505: bl->regno);
3506: fprintf (loop_dump_stream,
3507: "First use: insn %d, last use: insn %d.\n",
3508: regno_first_uid[bl->regno],
3509: regno_last_uid[bl->regno]);
3510: }
3511: }
3512:
3513: /* Combine all giv's for this iv_class. */
3514: combine_givs (bl);
3515:
3516: /* This will be true at the end, if all givs which depend on this
3517: biv have been strength reduced.
3518: We can't (currently) eliminate the biv unless this is so. */
3519: all_reduced = 1;
3520:
3521: /* Check each giv in this class to see if we will benefit by reducing
3522: it. Skip giv's combined with others. */
3523: for (v = bl->giv; v; v = v->next_iv)
3524: {
3525: struct induction *tv;
3526:
3527: if (v->ignore || v->same)
3528: continue;
3529:
3530: benefit = v->benefit;
3531:
3532: /* Reduce benefit if not replaceable, since we will insert
3533: a move-insn to replace the insn that calculates this giv.
3534: Don't do this unless the giv is a user variable, since it
3535: will often be marked non-replaceable because of the duplication
3536: of the exit code outside the loop. In such a case, the copies
3537: we insert are dead and will be deleted. So they don't have
3538: a cost. Similar situations exist. */
3539: /* ??? The new final_[bg]iv_value code does a much better job
3540: of finding replaceable giv's, and hence this code may no longer
3541: be necessary. */
3542: if (! v->replaceable && ! bl->eliminable
3543: && REG_USERVAR_P (v->dest_reg))
3544: benefit -= copy_cost;
3545:
3546: /* Decrease the benefit to count the add-insns that we will
3547: insert to increment the reduced reg for the giv. */
3548: benefit -= add_cost * bl->biv_count;
3549:
3550: /* Decide whether to strength-reduce this giv or to leave the code
3551: unchanged (recompute it from the biv each time it is used).
3552: This decision can be made independently for each giv. */
3553:
3554: /* ??? Perhaps attempt to guess whether autoincrement will handle
3555: some of the new add insns; if so, can increase BENEFIT
3556: (undo the subtraction of add_cost that was done above). */
3557:
3558: /* If an insn is not to be strength reduced, then set its ignore
3559: flag, and clear all_reduced. */
3560:
3561: if (v->lifetime * threshold * benefit < insn_count)
3562: {
3563: if (loop_dump_stream)
3564: fprintf (loop_dump_stream,
3565: "giv of insn %d not worth while, %d vs %d.\n",
3566: INSN_UID (v->insn),
3567: v->lifetime * threshold * benefit, insn_count);
3568: v->ignore = 1;
3569: all_reduced = 0;
3570: }
3571: else
3572: {
3573: /* Check that we can increment the reduced giv without a
3574: multiply insn. If not, reject it. */
3575:
3576: for (tv = bl->biv; tv; tv = tv->next_iv)
3577: if (tv->mult_val == const1_rtx
3578: && ! product_cheap_p (tv->add_val, v->mult_val))
3579: {
3580: if (loop_dump_stream)
3581: fprintf (loop_dump_stream,
3582: "giv of insn %d: would need a multiply.\n",
3583: INSN_UID (v->insn));
3584: v->ignore = 1;
3585: all_reduced = 0;
3586: break;
3587: }
3588: }
3589: }
3590:
3591: /* Reduce each giv that we decided to reduce. */
3592:
3593: for (v = bl->giv; v; v = v->next_iv)
3594: {
3595: struct induction *tv;
3596: if (! v->ignore && v->same == 0)
3597: {
3598: v->new_reg = gen_reg_rtx (v->mode);
3599:
3600: /* For each place where the biv is incremented,
3601: add an insn to increment the new, reduced reg for the giv. */
3602: for (tv = bl->biv; tv; tv = tv->next_iv)
3603: {
3604: if (tv->mult_val == const1_rtx)
3605: emit_iv_add_mult (tv->add_val, v->mult_val,
3606: v->new_reg, v->new_reg, tv->insn);
3607: else /* tv->mult_val == const0_rtx */
3608: /* A multiply is acceptable here
3609: since this is presumed to be seldom executed. */
3610: emit_iv_add_mult (tv->add_val, v->mult_val,
3611: v->add_val, v->new_reg, tv->insn);
3612: }
3613:
3614: /* Add code at loop start to initialize giv's reduced reg. */
3615:
3616: emit_iv_add_mult (bl->initial_value, v->mult_val,
3617: v->add_val, v->new_reg, loop_start);
3618: }
3619: }
3620:
3621: /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
3622: as not reduced.
3623:
3624: For each giv register that can be reduced now: if replaceable,
3625: substitute reduced reg wherever the old giv occurs;
3626: else add new move insn "giv_reg = reduced_reg".
3627:
3628: Also check for givs whose first use is their definition and whose
3629: last use is the definition of another giv. If so, it is likely
3630: dead and should not be used to eliminate a biv. */
3631: for (v = bl->giv; v; v = v->next_iv)
3632: {
3633: if (v->same && v->same->ignore)
3634: v->ignore = 1;
3635:
3636: if (v->ignore)
3637: continue;
3638:
3639: if (v->giv_type == DEST_REG
3640: && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn))
3641: {
3642: struct induction *v1;
3643:
3644: for (v1 = bl->giv; v1; v1 = v1->next_iv)
3645: if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn))
3646: v->maybe_dead = 1;
3647: }
3648:
3649: /* Update expression if this was combined, in case other giv was
3650: replaced. */
3651: if (v->same)
3652: v->new_reg = replace_rtx (v->new_reg,
3653: v->same->dest_reg, v->same->new_reg);
3654:
3655: if (v->giv_type == DEST_ADDR)
3656: /* Store reduced reg as the address in the memref where we found
3657: this giv. */
3658: *v->location = v->new_reg;
3659: else if (v->replaceable)
3660: {
3661: reg_map[REGNO (v->dest_reg)] = v->new_reg;
3662:
3663: #if 0
3664: /* I can no longer duplicate the original problem. Perhaps
3665: this is unnecessary now? */
3666:
3667: /* Replaceable; it isn't strictly necessary to delete the old
3668: insn and emit a new one, because v->dest_reg is now dead.
3669:
3670: However, especially when unrolling loops, the special
3671: handling for (set REG0 REG1) in the second cse pass may
3672: make v->dest_reg live again. To avoid this problem, emit
3673: an insn to set the original giv reg from the reduced giv.
3674: We can not delete the original insn, since it may be part
3675: of a LIBCALL, and the code in flow that eliminates dead
3676: libcalls will fail if it is deleted. */
3677: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3678: v->insn);
3679: #endif
3680: }
3681: else
3682: {
3683: /* Not replaceable; emit an insn to set the original giv reg from
3684: the reduced giv, same as above. */
3685: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3686: v->insn);
3687: }
3688:
3689: /* When a loop is reversed, givs which depend on the reversed
3690: biv, and which are live outside the loop, must be set to their
3691: correct final value. This insn is only needed if the giv is
3692: not replaceable. The correct final value is the same as the
3693: value that the giv starts the reversed loop with. */
3694: if (bl->reversed && ! v->replaceable)
3695: emit_iv_add_mult (bl->initial_value, v->mult_val,
3696: v->add_val, v->dest_reg, end_insert_before);
3697: else if (v->final_value)
3698: {
3699: rtx insert_before;
3700:
3701: /* If the loop has multiple exits, emit the insn before the
3702: loop to ensure that it will always be executed no matter
3703: how the loop exits. Otherwise, emit the insn after the loop,
3704: since this is slightly more efficient. */
3705: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3706: insert_before = loop_start;
3707: else
3708: insert_before = end_insert_before;
3709: emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
3710: insert_before);
3711:
3712: #if 0
3713: /* If the insn to set the final value of the giv was emitted
3714: before the loop, then we must delete the insn inside the loop
3715: that sets it. If this is a LIBCALL, then we must delete
3716: every insn in the libcall. Note, however, that
3717: final_giv_value will only succeed when there are multiple
3718: exits if the giv is dead at each exit, hence it does not
3719: matter that the original insn remains because it is dead
3720: anyways. */
3721: /* Delete the insn inside the loop that sets the giv since
3722: the giv is now set before (or after) the loop. */
3723: delete_insn (v->insn);
3724: #endif
3725: }
3726:
3727: if (loop_dump_stream)
3728: {
3729: fprintf (loop_dump_stream, "giv at %d reduced to ",
3730: INSN_UID (v->insn));
3731: print_rtl (loop_dump_stream, v->new_reg);
3732: fprintf (loop_dump_stream, "\n");
3733: }
3734: }
3735:
3736: /* All the givs based on the biv bl have been reduced if they
3737: merit it. */
3738:
3739: /* For each giv not marked as maybe dead that has been combined with a
3740: second giv, clear any "maybe dead" mark on that second giv.
3741: v->new_reg will either be or refer to the register of the giv it
3742: combined with.
3743:
3744: Doing this clearing avoids problems in biv elimination where a
3745: giv's new_reg is a complex value that can't be put in the insn but
3746: the giv combined with (with a reg as new_reg) is marked maybe_dead.
3747: Since the register will be used in either case, we'd prefer it be
3748: used from the simpler giv. */
3749:
3750: for (v = bl->giv; v; v = v->next_iv)
3751: if (! v->maybe_dead && v->same)
3752: v->same->maybe_dead = 0;
3753:
3754: /* Try to eliminate the biv, if it is a candidate.
3755: This won't work if ! all_reduced,
3756: since the givs we planned to use might not have been reduced.
3757:
3758: We have to be careful that we didn't initially think we could elminate
3759: this biv because of a giv that we now think may be dead and shouldn't
3760: be used as a biv replacement.
3761:
3762: Also, there is the possibility that we may have a giv that looks
3763: like it can be used to eliminate a biv, but the resulting insn
3764: isn't valid. This can happen, for example, on the 88k, where a
3765: JUMP_INSN can compare a register only with zero. Attempts to
3766: replace it with a comapare with a constant will fail.
3767:
3768: Note that in cases where this call fails, we may have replaced some
3769: of the occurrences of the biv with a giv, but no harm was done in
3770: doing so in the rare cases where it can occur. */
3771:
3772: if (all_reduced == 1 && bl->eliminable
3773: && maybe_eliminate_biv (bl, loop_start, end, 1,
3774: threshold, insn_count))
3775:
3776: {
3777: /* ?? If we created a new test to bypass the loop entirely,
3778: or otherwise drop straight in, based on this test, then
3779: we might want to rewrite it also. This way some later
3780: pass has more hope of removing the initialization of this
3781: biv entirely. */
3782:
3783: /* If final_value != 0, then the biv may be used after loop end
3784: and we must emit an insn to set it just in case.
3785:
3786: Reversed bivs already have an insn after the loop setting their
3787: value, so we don't need another one. We can't calculate the
3788: proper final value for such a biv here anyways. */
3789: if (final_value != 0 && ! bl->reversed)
3790: {
3791: rtx insert_before;
3792:
3793: /* If the loop has multiple exits, emit the insn before the
3794: loop to ensure that it will always be executed no matter
3795: how the loop exits. Otherwise, emit the insn after the
3796: loop, since this is slightly more efficient. */
3797: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3798: insert_before = loop_start;
3799: else
3800: insert_before = end_insert_before;
3801:
3802: emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
3803: end_insert_before);
3804: }
3805:
3806: #if 0
3807: /* Delete all of the instructions inside the loop which set
3808: the biv, as they are all dead. If is safe to delete them,
3809: because an insn setting a biv will never be part of a libcall. */
3810: /* However, deleting them will invalidate the regno_last_uid info,
3811: so keeping them around is more convenient. Final_biv_value
3812: will only succeed when there are multiple exits if the biv
3813: is dead at each exit, hence it does not matter that the original
3814: insn remains, because it is dead anyways. */
3815: for (v = bl->biv; v; v = v->next_iv)
3816: delete_insn (v->insn);
3817: #endif
3818:
3819: if (loop_dump_stream)
3820: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
3821: bl->regno);
3822: }
3823: }
3824:
3825: /* Go through all the instructions in the loop, making all the
3826: register substitutions scheduled in REG_MAP. */
3827:
3828: for (p = loop_start; p != end; p = NEXT_INSN (p))
3829: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3830: || GET_CODE (p) == CALL_INSN)
3831: {
3832: replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0);
3833: replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0);
3834: }
3835:
3836: /* Unroll loops from within strength reduction so that we can use the
3837: induction variable information that strength_reduce has already
3838: collected. */
3839:
3840: if (flag_unroll_loops)
3841: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
3842:
3843: if (loop_dump_stream)
3844: fprintf (loop_dump_stream, "\n");
3845: }
3846:
3847: /* Return 1 if X is a valid source for an initial value (or as value being
3848: compared against in an initial test).
3849:
3850: X must be either a register or constant and must not be clobbered between
3851: the current insn and the start of the loop.
3852:
3853: INSN is the insn containing X. */
3854:
3855: static int
3856: valid_initial_value_p (x, insn, call_seen, loop_start)
3857: rtx x;
3858: rtx insn;
3859: int call_seen;
3860: rtx loop_start;
3861: {
3862: if (CONSTANT_P (x))
3863: return 1;
3864:
3865: /* Only consider psuedos we know about initialized in insns whose luids
3866: we know. */
3867: if (GET_CODE (x) != REG
3868: || REGNO (x) >= max_reg_before_loop)
3869: return 0;
3870:
3871: /* Don't use call-clobbered registers across a call which clobbers it. On
3872: some machines, don't use any hard registers at all. */
3873: if (REGNO (x) < FIRST_PSEUDO_REGISTER
3874: #ifndef SMALL_REGISTER_CLASSES
3875: && call_used_regs[REGNO (x)] && call_seen
3876: #endif
3877: )
3878: return 0;
3879:
3880: /* Don't use registers that have been clobbered before the start of the
3881: loop. */
3882: if (reg_set_between_p (x, insn, loop_start))
3883: return 0;
3884:
3885: return 1;
3886: }
3887:
3888: /* Scan X for memory refs and check each memory address
3889: as a possible giv. INSN is the insn whose pattern X comes from.
3890: NOT_EVERY_ITERATION is 1 if the insn might not be executed during
3891: every loop iteration. */
3892:
3893: static void
3894: find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
3895: rtx x;
3896: rtx insn;
3897: int not_every_iteration;
3898: rtx loop_start, loop_end;
3899: {
3900: register int i, j;
3901: register enum rtx_code code;
3902: register char *fmt;
3903:
3904: if (x == 0)
3905: return;
3906:
3907: code = GET_CODE (x);
3908: switch (code)
3909: {
3910: case REG:
3911: case CONST_INT:
3912: case CONST:
3913: case CONST_DOUBLE:
3914: case SYMBOL_REF:
3915: case LABEL_REF:
3916: case PC:
3917: case CC0:
3918: case ADDR_VEC:
3919: case ADDR_DIFF_VEC:
3920: case USE:
3921: case CLOBBER:
3922: return;
3923:
3924: case MEM:
3925: {
3926: rtx src_reg;
3927: rtx add_val;
3928: rtx mult_val;
3929: int benefit;
3930:
3931: benefit = general_induction_var (XEXP (x, 0),
3932: &src_reg, &add_val, &mult_val);
3933:
3934: /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0.
3935: Such a giv isn't useful. */
3936: if (benefit > 0 && (mult_val != const1_rtx || add_val != const0_rtx))
3937: {
3938: /* Found one; record it. */
3939: struct induction *v
3940: = (struct induction *) oballoc (sizeof (struct induction));
3941:
3942: record_giv (v, insn, src_reg, addr_placeholder, mult_val,
3943: add_val, benefit, DEST_ADDR, not_every_iteration,
3944: &XEXP (x, 0), loop_start, loop_end);
3945:
3946: v->mem_mode = GET_MODE (x);
3947: }
3948: return;
3949: }
3950: }
3951:
3952: /* Recursively scan the subexpressions for other mem refs. */
3953:
3954: fmt = GET_RTX_FORMAT (code);
3955: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3956: if (fmt[i] == 'e')
3957: find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
3958: loop_end);
3959: else if (fmt[i] == 'E')
3960: for (j = 0; j < XVECLEN (x, i); j++)
3961: find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
3962: loop_start, loop_end);
3963: }
3964:
3965: /* Fill in the data about one biv update.
3966: V is the `struct induction' in which we record the biv. (It is
3967: allocated by the caller, with alloca.)
3968: INSN is the insn that sets it.
3969: DEST_REG is the biv's reg.
3970:
3971: MULT_VAL is const1_rtx if the biv is being incremented here, in which case
3972: INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
3973: being set to INC_VAL. */
3974:
3975: static void
3976: record_biv (v, insn, dest_reg, inc_val, mult_val, not_every_iteration)
3977: struct induction *v;
3978: rtx insn;
3979: rtx dest_reg;
3980: rtx inc_val;
3981: rtx mult_val;
3982: int not_every_iteration;
3983: {
3984: struct iv_class *bl;
3985:
3986: v->insn = insn;
3987: v->src_reg = dest_reg;
3988: v->dest_reg = dest_reg;
3989: v->mult_val = mult_val;
3990: v->add_val = inc_val;
3991: v->mode = GET_MODE (dest_reg);
3992: v->always_computable = ! not_every_iteration;
3993:
3994: /* Add this to the reg's iv_class, creating a class
3995: if this is the first incrementation of the reg. */
3996:
3997: bl = reg_biv_class[REGNO (dest_reg)];
3998: if (bl == 0)
3999: {
4000: /* Create and initialize new iv_class. */
4001:
4002: bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
4003:
4004: bl->regno = REGNO (dest_reg);
4005: bl->biv = 0;
4006: bl->giv = 0;
4007: bl->biv_count = 0;
4008: bl->giv_count = 0;
4009:
4010: /* Set initial value to the reg itself. */
4011: bl->initial_value = dest_reg;
4012: /* We haven't seen the intializing insn yet */
4013: bl->init_insn = 0;
4014: bl->init_set = 0;
4015: bl->initial_test = 0;
4016: bl->incremented = 0;
4017: bl->eliminable = 0;
4018: bl->nonneg = 0;
4019: bl->reversed = 0;
4020:
4021: /* Add this class to loop_iv_list. */
4022: bl->next = loop_iv_list;
4023: loop_iv_list = bl;
4024:
4025: /* Put it in the array of biv register classes. */
4026: reg_biv_class[REGNO (dest_reg)] = bl;
4027: }
4028:
4029: /* Update IV_CLASS entry for this biv. */
4030: v->next_iv = bl->biv;
4031: bl->biv = v;
4032: bl->biv_count++;
4033: if (mult_val == const1_rtx)
4034: bl->incremented = 1;
4035:
4036: if (loop_dump_stream)
4037: {
4038: fprintf (loop_dump_stream,
4039: "Insn %d: possible biv, reg %d,",
4040: INSN_UID (insn), REGNO (dest_reg));
4041: if (GET_CODE (inc_val) == CONST_INT)
4042: fprintf (loop_dump_stream, " const = %d\n",
4043: INTVAL (inc_val));
4044: else
4045: {
4046: fprintf (loop_dump_stream, " const = ");
4047: print_rtl (loop_dump_stream, inc_val);
4048: fprintf (loop_dump_stream, "\n");
4049: }
4050: }
4051: }
4052:
4053: /* Fill in the data about one giv.
4054: V is the `struct induction' in which we record the giv. (It is
4055: allocated by the caller, with alloca.)
4056: INSN is the insn that sets it.
4057: BENEFIT estimates the savings from deleting this insn.
4058: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4059: into a register or is used as a memory address.
4060:
4061: SRC_REG is the biv reg which the giv is computed from.
4062: DEST_REG is the giv's reg (if the giv is stored in a reg).
4063: MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4064: LOCATION points to the place where this giv's value appears in INSN. */
4065:
4066: static void
4067: record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
4068: type, not_every_iteration, location, loop_start, loop_end)
4069: struct induction *v;
4070: rtx insn;
4071: rtx src_reg;
4072: rtx dest_reg;
4073: rtx mult_val, add_val;
4074: int benefit;
4075: enum g_types type;
4076: int not_every_iteration;
4077: rtx *location;
4078: rtx loop_start, loop_end;
4079: {
4080: struct induction *b;
4081: struct iv_class *bl;
4082: rtx set = single_set (insn);
4083: rtx p;
4084:
4085: v->insn = insn;
4086: v->src_reg = src_reg;
4087: v->giv_type = type;
4088: v->dest_reg = dest_reg;
4089: v->mult_val = mult_val;
4090: v->add_val = add_val;
4091: v->benefit = benefit;
4092: v->location = location;
4093: v->cant_derive = 0;
4094: v->combined_with = 0;
4095: v->maybe_dead = 0;
4096: v->derive_adjustment = 0;
4097: v->same = 0;
4098: v->ignore = 0;
4099: v->new_reg = 0;
4100: v->final_value = 0;
4101:
4102: /* The v->always_computable field is used in update_giv_derive, to
4103: determine whether a giv can be used to derive another giv. For a
4104: DEST_REG giv, INSN computes a new value for the giv, so its value
4105: isn't computable if INSN insn't executed every iteration.
4106: However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4107: it does not compute a new value. Hence the value is always computable
4108: irregardless of whether INSN is executed each iteration. */
4109:
4110: if (type == DEST_ADDR)
4111: v->always_computable = 1;
4112: else
4113: v->always_computable = ! not_every_iteration;
4114:
4115: if (type == DEST_ADDR)
4116: {
4117: v->mode = GET_MODE (*location);
4118: v->lifetime = 1;
4119: v->times_used = 1;
4120: }
4121: else /* type == DEST_REG */
4122: {
4123: v->mode = GET_MODE (SET_DEST (set));
4124:
4125: v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]]
4126: - uid_luid[regno_first_uid[REGNO (dest_reg)]]);
4127:
4128: v->times_used = n_times_used[REGNO (dest_reg)];
4129:
4130: /* If the lifetime is zero, it means that this register is
4131: really a dead store. So mark this as a giv that can be
4132: ignored. This will not prevent the biv from being eliminated. */
4133: if (v->lifetime == 0)
4134: v->ignore = 1;
4135:
4136: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
4137: reg_iv_info[REGNO (dest_reg)] = v;
4138: }
4139:
4140: /* Add the giv to the class of givs computed from one biv. */
4141:
4142: bl = reg_biv_class[REGNO (src_reg)];
4143: if (bl)
4144: {
4145: v->next_iv = bl->giv;
4146: bl->giv = v;
4147: /* Don't count DEST_ADDR. This is supposed to count the number of
4148: insns that calculate givs. */
4149: if (type == DEST_REG)
4150: bl->giv_count++;
4151: bl->total_benefit += benefit;
4152: }
4153: else
4154: /* Fatal error, biv missing for this giv? */
4155: abort ();
4156:
4157: if (type == DEST_ADDR)
4158: v->replaceable = 1;
4159: else
4160: {
4161: /* The giv can be replaced outright by the reduced register only if all
4162: of the following conditions are true:
4163: - the insn that sets the giv is always executed on any iteration
4164: on which the giv is used at all
4165: (there are two ways to deduce this:
4166: either the insn is executed on every iteration,
4167: or all uses follow that insn in the same basic block),
4168: - the giv is not used outside the loop
4169: - no assignments to the biv occur during the giv's lifetime. */
4170:
4171: if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn)
4172: /* Previous line always fails if INSN was moved by loop opt. */
4173: && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end)
4174: && (! not_every_iteration
4175: || last_use_this_basic_block (dest_reg, insn)))
4176: {
4177: /* Now check that there are no assignments to the biv within the
4178: giv's lifetime. This requires two separate checks. */
4179:
4180: /* Check each biv update, and fail if any are between the first
4181: and last use of the giv.
4182:
4183: If this loop contains an inner loop that was unrolled, then
4184: the insn modifying the biv may have been emitted by the loop
4185: unrolling code, and hence does not have a valid luid. Just
4186: mark the biv as not replaceable in this case. It is not very
4187: useful as a biv, because it is used in two different loops.
4188: It is very unlikely that we would be able to optimize the giv
4189: using this biv anyways. */
4190:
4191: v->replaceable = 1;
4192: for (b = bl->biv; b; b = b->next_iv)
4193: {
4194: if (INSN_UID (b->insn) >= max_uid_for_loop
4195: || ((uid_luid[INSN_UID (b->insn)]
4196: >= uid_luid[regno_first_uid[REGNO (dest_reg)]])
4197: && (uid_luid[INSN_UID (b->insn)]
4198: <= uid_luid[regno_last_uid[REGNO (dest_reg)]])))
4199: {
4200: v->replaceable = 0;
4201: v->not_replaceable = 1;
4202: break;
4203: }
4204: }
4205:
4206: /* Check each insn between the first and last use of the giv,
4207: and fail if any of them are branches that jump to a named label
4208: outside this range, but still inside the loop. This catches
4209: cases of spaghetti code where the execution order of insns
4210: is not linear, and hence the above test fails. For example,
4211: in the following code, j is not replaceable:
4212: for (i = 0; i < 100; ) {
4213: L0: j = 4*i; goto L1;
4214: L2: k = j; goto L3;
4215: L1: i++; goto L2;
4216: L3: ; }
4217: printf ("k = %d\n", k); }
4218: This test is conservative, but this test succeeds rarely enough
4219: that it isn't a problem. See also check_final_value below. */
4220:
4221: if (v->replaceable)
4222: for (p = insn;
4223: INSN_UID (p) >= max_uid_for_loop
4224: || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]];
4225: p = NEXT_INSN (p))
4226: {
4227: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4228: && LABEL_NAME (JUMP_LABEL (p))
4229: && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)
4230: && (INSN_LUID (JUMP_LABEL (p))
4231: < uid_luid[regno_first_uid[REGNO (dest_reg)]]))
4232: || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)
4233: && (INSN_LUID (JUMP_LABEL (p))
4234: > uid_luid[regno_last_uid[REGNO (dest_reg)]]))))
4235: {
4236: v->replaceable = 0;
4237: v->not_replaceable = 1;
4238:
4239: if (loop_dump_stream)
4240: fprintf (loop_dump_stream,
4241: "Found branch outside giv lifetime.\n");
4242:
4243: break;
4244: }
4245: }
4246: }
4247: else
4248: {
4249: /* May still be replaceable, we don't have enough info here to
4250: decide. */
4251: v->replaceable = 0;
4252: v->not_replaceable = 0;
4253: }
4254: }
4255:
4256: if (loop_dump_stream)
4257: {
4258: if (type == DEST_REG)
4259: fprintf (loop_dump_stream, "Insn %d: giv reg %d",
4260: INSN_UID (insn), REGNO (dest_reg));
4261: else
4262: fprintf (loop_dump_stream, "Insn %d: dest address",
4263: INSN_UID (insn));
4264:
4265: fprintf (loop_dump_stream, " src reg %d benefit %d",
4266: REGNO (src_reg), v->benefit);
4267: fprintf (loop_dump_stream, " used %d lifetime %d",
4268: v->times_used, v->lifetime);
4269:
4270: if (v->replaceable)
4271: fprintf (loop_dump_stream, " replaceable");
4272:
4273: if (GET_CODE (mult_val) == CONST_INT)
4274: fprintf (loop_dump_stream, " mult %d",
4275: INTVAL (mult_val));
4276: else
4277: {
4278: fprintf (loop_dump_stream, " mult ");
4279: print_rtl (loop_dump_stream, mult_val);
4280: }
4281:
4282: if (GET_CODE (add_val) == CONST_INT)
4283: fprintf (loop_dump_stream, " add %d",
4284: INTVAL (add_val));
4285: else
4286: {
4287: fprintf (loop_dump_stream, " add ");
4288: print_rtl (loop_dump_stream, add_val);
4289: }
4290: }
4291:
4292: if (loop_dump_stream)
4293: fprintf (loop_dump_stream, "\n");
4294:
4295: }
4296:
4297:
4298: /* All this does is determine whether a giv can be made replaceable because
4299: its final value can be calculated. This code can not be part of record_giv
4300: above, because final_giv_value requires that the number of loop iterations
4301: be known, and that can not be accurately calculated until after all givs
4302: have been identified. */
4303:
4304: static void
4305: check_final_value (v, loop_start, loop_end)
4306: struct induction *v;
4307: rtx loop_start, loop_end;
4308: {
4309: struct iv_class *bl;
4310: rtx final_value = 0;
4311: rtx tem;
4312:
4313: bl = reg_biv_class[REGNO (v->src_reg)];
4314:
4315: /* DEST_ADDR givs will never reach here, because they are always marked
4316: replaceable above in record_giv. */
4317:
4318: /* The giv can be replaced outright by the reduced register only if all
4319: of the following conditions are true:
4320: - the insn that sets the giv is always executed on any iteration
4321: on which the giv is used at all
4322: (there are two ways to deduce this:
4323: either the insn is executed on every iteration,
4324: or all uses follow that insn in the same basic block),
4325: - its final value can be calculated (this condition is different
4326: than the one above in record_giv)
4327: - no assignments to the biv occur during the giv's lifetime. */
4328:
4329: #if 0
4330: /* This is only called now when replaceable is known to be false. */
4331: /* Clear replaceable, so that it won't confuse final_giv_value. */
4332: v->replaceable = 0;
4333: #endif
4334:
4335: if ((final_value = final_giv_value (v, loop_start, loop_end))
4336: && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
4337: {
4338: int biv_increment_seen = 0;
4339: rtx p = v->insn;
4340: rtx last_giv_use;
4341:
4342: v->replaceable = 1;
4343:
4344: /* When trying to determine whether or not a biv increment occurs
4345: during the lifetime of the giv, we can ignore uses of the variable
4346: outside the loop because final_value is true. Hence we can not
4347: use regno_last_uid and regno_first_uid as above in record_giv. */
4348:
4349: /* Search the loop to determine whether any assignments to the
4350: biv occur during the giv's lifetime. Start with the insn
4351: that sets the giv, and search around the loop until we come
4352: back to that insn again.
4353:
4354: Also fail if there is a jump within the giv's lifetime that jumps
4355: to somewhere outside the lifetime but still within the loop. This
4356: catches spaghetti code where the execution order is not linear, and
4357: hence the above test fails. Here we assume that the giv lifetime
4358: does not extend from one iteration of the loop to the next, so as
4359: to make the test easier. Since the lifetime isn't known yet,
4360: this requires two loops. See also record_giv above. */
4361:
4362: last_giv_use = v->insn;
4363:
4364: while (1)
4365: {
4366: p = NEXT_INSN (p);
4367: if (p == loop_end)
4368: p = NEXT_INSN (loop_start);
4369: if (p == v->insn)
4370: break;
4371:
4372: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4373: || GET_CODE (p) == CALL_INSN)
4374: {
4375: if (biv_increment_seen)
4376: {
4377: if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4378: {
4379: v->replaceable = 0;
4380: v->not_replaceable = 1;
4381: break;
4382: }
4383: }
4384: else if (GET_CODE (PATTERN (p)) == SET
4385: && SET_DEST (PATTERN (p)) == v->src_reg)
4386: biv_increment_seen = 1;
4387: else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4388: last_giv_use = p;
4389: }
4390: }
4391:
4392: /* Now that the lifetime of the giv is known, check for branches
4393: from within the lifetime to outside the lifetime if it is still
4394: replaceable. */
4395:
4396: if (v->replaceable)
4397: {
4398: p = v->insn;
4399: while (1)
4400: {
4401: p = NEXT_INSN (p);
4402: if (p == loop_end)
4403: p = NEXT_INSN (loop_start);
4404: if (p == last_giv_use)
4405: break;
4406:
4407: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4408: && LABEL_NAME (JUMP_LABEL (p))
4409: && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
4410: && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
4411: || (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
4412: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
4413: {
4414: v->replaceable = 0;
4415: v->not_replaceable = 1;
4416:
4417: if (loop_dump_stream)
4418: fprintf (loop_dump_stream,
4419: "Found branch outside giv lifetime.\n");
4420:
4421: break;
4422: }
4423: }
4424: }
4425:
4426: /* If it is replaceable, then save the final value. */
4427: if (v->replaceable)
4428: v->final_value = final_value;
4429: }
4430:
4431: if (loop_dump_stream && v->replaceable)
4432: fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
4433: INSN_UID (v->insn), REGNO (v->dest_reg));
4434: }
4435:
4436: /* Update the status of whether a giv can derive other givs.
4437:
4438: We need to do something special if there is or may be an update to the biv
4439: between the time the giv is defined and the time it is used to derive
4440: another giv.
4441:
4442: In addition, a giv that is only conditionally set is not allowed to
4443: derive another giv once a label has been passed.
4444:
4445: The cases we look at are when a label or an update to a biv is passed. */
4446:
4447: static void
4448: update_giv_derive (p)
4449: rtx p;
4450: {
4451: struct iv_class *bl;
4452: struct induction *biv, *giv;
4453: rtx tem;
4454: int dummy;
4455:
4456: /* Search all IV classes, then all bivs, and finally all givs.
4457:
4458: There are two cases we are concerned with. First we have the situation
4459: of a giv that is only updated conditionally. In that case, it may not
4460: derive any givs after a label is passed.
4461:
4462: The second case is when a biv update occurs, or may occur, after the
4463: definition of a giv. For certain biv updates (see below) that are
4464: known to occur between the giv definition and use, we can adjust the
4465: giv definition. For others, or when the biv update is conditional,
4466: we must prevent the giv from deriving any other givs. There are two
4467: sub-cases within this case.
4468:
4469: If this is a label, we are concerned with any biv update that is done
4470: conditionally, since it may be done after the giv is defined followed by
4471: a branch here (actually, we need to pass both a jump and a label, but
4472: this extra tracking doesn't seem worth it).
4473:
4474: If this is a giv update, we must adjust the giv status to show that a
4475: subsequent biv update was performed. If this adjustment cannot be done,
4476: the giv cannot derive further givs. */
4477:
4478: for (bl = loop_iv_list; bl; bl = bl->next)
4479: for (biv = bl->biv; biv; biv = biv->next_iv)
4480: if (GET_CODE (p) == CODE_LABEL || biv->insn == p)
4481: {
4482: for (giv = bl->giv; giv; giv = giv->next_iv)
4483: {
4484: /* If cant_derive is already true, there is no point in
4485: checking all of these conditions again. */
4486: if (giv->cant_derive)
4487: continue;
4488:
4489: /* If this giv is conditionally set and we have passed a label,
4490: it cannot derive anything. */
4491: if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
4492: giv->cant_derive = 1;
4493:
4494: /* Skip givs that have mult_val == 0, since
4495: they are really invariants. Also skip those that are
4496: replaceable, since we know their lifetime doesn't contain
4497: any biv update. */
4498: else if (giv->mult_val == const0_rtx || giv->replaceable)
4499: continue;
4500:
4501: /* The only way we can allow this giv to derive another
4502: is if this is a biv increment and we can form the product
4503: of biv->add_val and giv->mult_val. In this case, we will
4504: be able to compute a compensation. */
4505: else if (biv->insn == p)
4506: {
4507: if (biv->mult_val == const1_rtx
4508: && (tem = simplify_giv_expr (gen_rtx (MULT, giv->mode,
4509: biv->add_val,
4510: giv->mult_val),
4511: &dummy)))
4512: giv->derive_adjustment = tem;
4513: else
4514: giv->cant_derive = 1;
4515: }
4516: else if (GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
4517: giv->cant_derive = 1;
4518: }
4519: }
4520: }
4521:
4522: /* Check whether an insn is an increment legitimate for a basic induction var.
4523: X is the source of the insn.
4524: DEST_REG is the putative biv, also the destination of the insn.
4525: We accept patterns of these forms:
4526: REG = REG + INVARIANT
4527: REG = INVARIANT + REG
4528: REG = REG - CONSTANT
4529:
4530: If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
4531: and store the additive term into *INC_VAL.
4532:
4533: If X is an assignment of an invariant into DEST_REG, we set
4534: *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
4535:
4536: Otherwise we return 0. */
4537:
4538: static int
4539: basic_induction_var (x, dest_reg, inc_val, mult_val)
4540: register rtx x;
4541: rtx dest_reg;
4542: rtx *inc_val;
4543: rtx *mult_val;
4544: {
4545: register enum rtx_code code;
4546: rtx arg;
4547:
4548: code = GET_CODE (x);
4549: switch (code)
4550: {
4551: case PLUS:
4552: if (XEXP (x, 0) == dest_reg)
4553: arg = XEXP (x, 1);
4554: else if (XEXP (x, 1) == dest_reg)
4555: arg = XEXP (x, 0);
4556: else
4557: return 0;
4558:
4559: if (invariant_p (arg) != 1)
4560: return 0;
4561:
4562: *inc_val = arg;
4563: *mult_val = const1_rtx;
4564: return 1;
4565:
4566: case MINUS:
4567: if (XEXP (x, 0) == dest_reg
4568: && GET_CODE (XEXP (x, 1)) == CONST_INT)
4569: *inc_val = gen_rtx (CONST_INT, VOIDmode,
4570: - INTVAL (XEXP (x, 1)));
4571: else
4572: return 0;
4573:
4574: *mult_val = const1_rtx;
4575: return 1;
4576:
4577: /* Can accept constant setting of biv only when inside inner most loop.
4578: Otherwise, a biv of an inner loop may be incorrectly recognized
4579: as a biv of the outer loop,
4580: causing code to be moved INTO the inner loop. */
4581: case MEM:
4582: case REG:
4583: if (invariant_p (x) != 1)
4584: return 0;
4585: case CONST_INT:
4586: case SYMBOL_REF:
4587: case CONST:
4588: if (loops_enclosed == 1)
4589: {
4590: *inc_val = x;
4591: *mult_val = const0_rtx;
4592: return 1;
4593: }
4594: else
4595: return 0;
4596:
4597: default:
4598: return 0;
4599: }
4600: }
4601:
4602: /* A general induction variable (giv) is any quantity that is a linear
4603: function of a basic induction variable,
4604: i.e. giv = biv * mult_val + add_val.
4605: The coefficients can be any loop invariant quantity.
4606: A giv need not be computed directly from the biv;
4607: it can be computed by way of other givs. */
4608:
4609: /* Determine whether X computes a giv.
4610: If it does, return a nonzero value
4611: which is the benefit from eliminating the computation of X;
4612: set *SRC_REG to the register of the biv that it is computed from;
4613: set *ADD_VAL and *MULT_VAL to the coefficients,
4614: such that the value of X is biv * mult + add; */
4615:
4616: static int
4617: general_induction_var (x, src_reg, add_val, mult_val)
4618: rtx x;
4619: rtx *src_reg;
4620: rtx *add_val;
4621: rtx *mult_val;
4622: {
4623: rtx orig_x = x;
4624: int benefit = 0;
4625: char *storage;
4626:
4627: /* If this is an invariant, forget it, it isn't a giv. */
4628: if (invariant_p (x) == 1)
4629: return 0;
4630:
4631: /* See if the expression could be a giv and get its form.
4632: Mark our place on the obstack in case we don't find a giv. */
4633: storage = (char *) oballoc (0);
4634: x = simplify_giv_expr (x, &benefit);
4635: if (x == 0)
4636: {
4637: obfree (storage);
4638: return 0;
4639: }
4640:
4641: switch (GET_CODE (x))
4642: {
4643: case USE:
4644: case CONST_INT:
4645: /* Since this is now an invariant and wasn't before, it must be a giv
4646: with MULT_VAL == 0. It doesn't matter which BIV we associate this
4647: with. */
4648: *src_reg = loop_iv_list->biv->dest_reg;
4649: *mult_val = const0_rtx;
4650: *add_val = x;
4651: break;
4652:
4653: case REG:
4654: /* This is equivalent to a BIV. */
4655: *src_reg = x;
4656: *mult_val = const1_rtx;
4657: *add_val = const0_rtx;
4658: break;
4659:
4660: case PLUS:
4661: /* Either (plus (biv) (invar)) or
4662: (plus (mult (biv) (invar_1)) (invar_2)). */
4663: if (GET_CODE (XEXP (x, 0)) == MULT)
4664: {
4665: *src_reg = XEXP (XEXP (x, 0), 0);
4666: *mult_val = XEXP (XEXP (x, 0), 1);
4667: }
4668: else
4669: {
4670: *src_reg = XEXP (x, 0);
4671: *mult_val = const1_rtx;
4672: }
4673: *add_val = XEXP (x, 1);
4674: break;
4675:
4676: case MULT:
4677: /* ADD_VAL is zero. */
4678: *src_reg = XEXP (x, 0);
4679: *mult_val = XEXP (x, 1);
4680: *add_val = const0_rtx;
4681: break;
4682:
4683: default:
4684: abort ();
4685: }
4686:
4687: /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
4688: unless they are CONST_INT). */
4689: if (GET_CODE (*add_val) == USE)
4690: *add_val = XEXP (*add_val, 0);
4691: if (GET_CODE (*mult_val) == USE)
4692: *mult_val = XEXP (*mult_val, 0);
4693:
4694: benefit += rtx_cost (orig_x);
4695:
4696: /* Always return some benefit if this is a giv so it will be detected
4697: as such. This allows elimination of bivs that might otherwise
4698: not be eliminated. */
4699: return benefit == 0 ? 1 : benefit;
4700: }
4701:
4702: /* Given an expression, X, try to form it as a linear function of a biv.
4703: We will canonicalize it to be of the form
4704: (plus (mult (BIV) (invar_1))
4705: (invar_2))
4706: with possibile degeneracies.
4707:
4708: The invariant expressions must each be of a form that can be used as a
4709: machine operand. We surround then with a USE rtx (a hack, but localized
4710: and certainly unambiguous!) if not a CONST_INT for simplicity in this
4711: routine; it is the caller's responsibility to strip them.
4712:
4713: If no such canonicalization is possible (i.e., two biv's are used or an
4714: expression that is neither invariant nor a biv or giv), this routine
4715: returns 0.
4716:
4717: For a non-zero return, the result will have a code of CONST_INT, USE,
4718: REG (for a BIV), PLUS, or MULT. No other codes will occur.
4719:
4720: *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
4721:
4722: static rtx
4723: simplify_giv_expr (x, benefit)
4724: rtx x;
4725: int *benefit;
4726: {
4727: enum machine_mode mode = GET_MODE (x);
4728: rtx arg0, arg1;
4729: rtx tem;
4730:
4731: /* If this is not an integer mode, or if we cannot do arithmetic in this
4732: mode, this can't be a giv. */
4733: if (mode != VOIDmode
4734: && (GET_MODE_CLASS (mode) != MODE_INT
4735: || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_INT))
4736: return 0;
4737:
4738: switch (GET_CODE (x))
4739: {
4740: case PLUS:
4741: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4742: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4743: if (arg0 == 0 || arg1 == 0)
4744: return 0;
4745:
4746: /* Put constant last, CONST_INT last if both constant. */
4747: if ((GET_CODE (arg0) == USE
4748: || GET_CODE (arg0) == CONST_INT)
4749: && GET_CODE (arg1) != CONST_INT)
4750: tem = arg0, arg0 = arg1, arg1 = tem;
4751:
4752: /* Handle addition of zero, then addition of an invariant. */
4753: if (arg1 == const0_rtx)
4754: return arg0;
4755: else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
4756: switch (GET_CODE (arg0))
4757: {
4758: case CONST_INT:
4759: case USE:
4760: /* Both invariant. Only valid if sum is machine operand.
4761: First strip off possible USE on first operand. */
4762: if (GET_CODE (arg0) == USE)
4763: arg0 = XEXP (arg0, 0);
4764:
4765: tem = 0;
4766: if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
4767: {
4768: tem = plus_constant (arg0, INTVAL (arg1));
4769: if (GET_CODE (tem) != CONST_INT)
4770: tem = gen_rtx (USE, mode, tem);
4771: }
4772:
4773: return tem;
4774:
4775: case REG:
4776: case MULT:
4777: /* biv + invar or mult + invar. Return sum. */
4778: return gen_rtx (PLUS, mode, arg0, arg1);
4779:
4780: case PLUS:
4781: /* (a + invar_1) + invar_2. Associate. */
4782: return simplify_giv_expr (gen_rtx (PLUS, mode,
4783: XEXP (arg0, 0),
4784: gen_rtx (PLUS, mode,
4785: XEXP (arg0, 1), arg1)),
4786: benefit);
4787:
4788: default:
4789: abort ();
4790: }
4791:
4792: /* Each argument must be either REG, PLUS, or MULT. Convert REG to
4793: MULT to reduce cases. */
4794: if (GET_CODE (arg0) == REG)
4795: arg0 = gen_rtx (MULT, mode, arg0, const1_rtx);
4796: if (GET_CODE (arg1) == REG)
4797: arg1 = gen_rtx (MULT, mode, arg1, const1_rtx);
4798:
4799: /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
4800: Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
4801: Recurse to associate the second PLUS. */
4802: if (GET_CODE (arg1) == MULT)
4803: tem = arg0, arg0 = arg1, arg1 = tem;
4804:
4805: if (GET_CODE (arg1) == PLUS)
4806: return simplify_giv_expr (gen_rtx (PLUS, mode,
4807: gen_rtx (PLUS, mode,
4808: arg0, XEXP (arg1, 0)),
4809: XEXP (arg1, 1)),
4810: benefit);
4811:
4812: /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
4813: if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
4814: abort ();
4815:
4816: if (XEXP (arg0, 0) != XEXP (arg1, 0))
4817: return 0;
4818:
4819: return simplify_giv_expr (gen_rtx (MULT, mode,
4820: XEXP (arg0, 0),
4821: gen_rtx (PLUS, mode,
4822: XEXP (arg0, 1),
4823: XEXP (arg1, 1))),
4824: benefit);
4825:
4826: case MINUS:
4827: /* Handle "a - b" as "a + b * (-1)". */
4828: return simplify_giv_expr (gen_rtx (PLUS, mode,
4829: XEXP (x, 0),
4830: gen_rtx (MULT, mode,
4831: XEXP (x, 1),
4832: gen_rtx (CONST_INT,
4833: VOIDmode, -1))),
4834: benefit);
4835:
4836: case MULT:
4837: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4838: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4839: if (arg0 == 0 || arg1 == 0)
4840: return 0;
4841:
4842: /* Put constant last, CONST_INT last if both constant. */
4843: if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
4844: && GET_CODE (arg1) != CONST_INT)
4845: tem = arg0, arg0 = arg1, arg1 = tem;
4846:
4847: /* If second argument is not now constant, not giv. */
4848: if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
4849: return 0;
4850:
4851: /* Handle multiply by 0 or 1. */
4852: if (arg1 == const0_rtx)
4853: return const0_rtx;
4854:
4855: else if (arg1 == const1_rtx)
4856: return arg0;
4857:
4858: switch (GET_CODE (arg0))
4859: {
4860: case REG:
4861: /* biv * invar. Done. */
4862: return gen_rtx (MULT, mode, arg0, arg1);
4863:
4864: case CONST_INT:
4865: /* Product of two constants. */
4866: return gen_rtx (CONST_INT, mode, INTVAL (arg0) * INTVAL (arg1));
4867:
4868: case USE:
4869: /* invar * invar. Not giv. */
4870: return 0;
4871:
4872: case MULT:
4873: /* (a * invar_1) * invar_2. Associate. */
4874: return simplify_giv_expr (gen_rtx (MULT, mode,
4875: XEXP (arg0, 0),
4876: gen_rtx (MULT, mode,
4877: XEXP (arg0, 1), arg1)),
4878: benefit);
4879:
4880: case PLUS:
4881: /* (a + invar_1) * invar_2. Distribute. */
4882: return simplify_giv_expr (gen_rtx (PLUS, mode,
4883: gen_rtx (MULT, mode,
4884: XEXP (arg0, 0), arg1),
4885: gen_rtx (MULT, mode,
4886: XEXP (arg0, 1), arg1)),
4887: benefit);
4888:
4889: default:
4890: abort ();
4891: }
4892:
4893: case ASHIFT:
4894: case LSHIFT:
4895: /* Shift by constant is multiply by power of two. */
4896: if (GET_CODE (XEXP (x, 1)) != CONST_INT)
4897: return 0;
4898:
4899: return simplify_giv_expr (gen_rtx (MULT, mode,
4900: XEXP (x, 0),
4901: gen_rtx (CONST_INT, VOIDmode,
4902: 1 << INTVAL (XEXP (x, 1)))),
4903: benefit);
4904:
4905: case NEG:
4906: /* "-a" is "a * (-1)" */
4907: return simplify_giv_expr (gen_rtx (MULT, mode,
4908: XEXP (x, 0),
4909: gen_rtx (CONST_INT, VOIDmode, -1)),
4910: benefit);
4911:
4912: case NOT:
4913: /* "~a" is "-a - 1". Silly, but easy. */
4914: return simplify_giv_expr (gen_rtx (MINUS, mode,
4915: gen_rtx (NEG, mode, XEXP (x, 0)),
4916: const1_rtx),
4917: benefit);
4918:
4919: case USE:
4920: /* Already in proper form for invariant. */
4921: return x;
4922:
4923: case REG:
4924: /* If this is a new register, we can't deal with it. */
4925: if (REGNO (x) >= max_reg_before_loop)
4926: return 0;
4927:
4928: /* Check for biv or giv. */
4929: switch (reg_iv_type[REGNO (x)])
4930: {
4931: case BASIC_INDUCT:
4932: return x;
4933: case GENERAL_INDUCT:
4934: {
4935: struct induction *v = reg_iv_info[REGNO (x)];
4936:
4937: /* Form expression from giv and add benefit. Ensure this giv
4938: can derive another and subtract any needed adjustment if so. */
4939: *benefit += v->benefit;
4940: if (v->cant_derive)
4941: return 0;
4942:
4943: tem = gen_rtx (PLUS, mode, gen_rtx (MULT, mode,
4944: v->src_reg, v->mult_val),
4945: v->add_val);
4946: if (v->derive_adjustment)
4947: tem = gen_rtx (MINUS, mode, tem, v->derive_adjustment);
4948: return simplify_giv_expr (tem, benefit);
4949: }
4950: }
4951:
4952: /* Fall through to general case. */
4953: default:
4954: /* If invariant, return as USE (unless CONST_INT).
4955: Otherwise, not giv. */
4956: if (GET_CODE (x) == USE)
4957: x = XEXP (x, 0);
4958:
4959: if (invariant_p (x) == 1)
4960: {
4961: if (GET_CODE (x) == CONST_INT)
4962: return x;
4963: else
4964: return gen_rtx (USE, mode, x);
4965: }
4966: else
4967: return 0;
4968: }
4969: }
4970:
4971: /* Help detect a giv that is calculated by several consecutive insns;
4972: for example,
4973: giv = biv * M
4974: giv = giv + A
4975: The caller has already identified the first insn P as having a giv as dest;
4976: we check that all other insns that set the same register follow
4977: immediately after P, that they alter nothing else,
4978: and that the result of the last is still a giv.
4979:
4980: The value is 0 if the reg set in P is not really a giv.
4981: Otherwise, the value is the amount gained by eliminating
4982: all the consecutive insns that compute the value.
4983:
4984: FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
4985: SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
4986:
4987: The coefficients of the ultimate giv value are stored in
4988: *MULT_VAL and *ADD_VAL. */
4989:
4990: static int
4991: consec_sets_giv (first_benefit, p, src_reg, dest_reg,
4992: add_val, mult_val)
4993: int first_benefit;
4994: rtx p;
4995: rtx src_reg;
4996: rtx dest_reg;
4997: rtx *add_val;
4998: rtx *mult_val;
4999: {
5000: int count;
5001: enum rtx_code code;
5002: int benefit;
5003: rtx temp;
5004: rtx set;
5005:
5006: /* Indicate that this is a giv so that we can update the value produced in
5007: each insn of the multi-insn sequence.
5008:
5009: This induction structure will be used only by the call to
5010: general_induction_var below, so we can allocate it on our stack.
5011: If this is a giv, our caller will replace the induct var entry with
5012: a new induction structure. */
5013: struct induction *v
5014: = (struct induction *) alloca (sizeof (struct induction));
5015: v->src_reg = src_reg;
5016: v->mult_val = *mult_val;
5017: v->add_val = *add_val;
5018: v->benefit = first_benefit;
5019: v->cant_derive = 0;
5020: v->derive_adjustment = 0;
5021:
5022: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
5023: reg_iv_info[REGNO (dest_reg)] = v;
5024:
5025: count = n_times_set[REGNO (dest_reg)] - 1;
5026:
5027: while (count > 0)
5028: {
5029: p = NEXT_INSN (p);
5030: code = GET_CODE (p);
5031:
5032: /* If libcall, skip to end of call sequence. */
5033: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
5034: p = XEXP (temp, 0);
5035:
5036: if (code == INSN
5037: && (set = single_set (p))
5038: && GET_CODE (SET_DEST (set)) == REG
5039: && SET_DEST (set) == dest_reg
5040: && ((benefit = general_induction_var (SET_SRC (set), &src_reg,
5041: add_val, mult_val))
5042: /* Giv created by equivalent expression. */
5043: || ((temp = find_reg_note (p, REG_EQUAL, 0))
5044: && (benefit = general_induction_var (XEXP (temp, 0), &src_reg,
5045: add_val, mult_val))))
5046: && src_reg == v->src_reg)
5047: {
5048: if (find_reg_note (p, REG_RETVAL, 0))
5049: benefit += libcall_benefit (p);
5050:
5051: count--;
5052: v->mult_val = *mult_val;
5053: v->add_val = *add_val;
5054: v->benefit = benefit;
5055: }
5056: else if (code != NOTE)
5057: {
5058: /* Allow insns that set something other than this giv to a
5059: constant. Such insns are needed on machines which cannot
5060: include long constants and should not disqualify a giv. */
5061: if (code == INSN
5062: && (set = single_set (p))
5063: && SET_DEST (set) != dest_reg
5064: && CONSTANT_P (SET_SRC (set)))
5065: continue;
5066:
5067: reg_iv_type[REGNO (dest_reg)] = UNKNOWN_INDUCT;
5068: return 0;
5069: }
5070: }
5071:
5072: return v->benefit;
5073: }
5074:
5075: /* Return an rtx, if any, that expresses giv G2 as a function of the register
5076: represented by G1. If no such expression can be found, or it is clear that
5077: it cannot possibly be a valid address, 0 is returned.
5078:
5079: To perform the computation, we note that
5080: G1 = a * v + b and
5081: G2 = c * v + d
5082: where `v' is the biv.
5083:
5084: So G2 = (c/a) * G1 + (d - b*c/a) */
5085:
5086: #ifdef ADDRESS_COST
5087: static rtx
5088: express_from (g1, g2)
5089: struct induction *g1, *g2;
5090: {
5091: rtx mult, add;
5092:
5093: /* The value that G1 will be multiplied by must be a constant integer. Also,
5094: the only chance we have of getting a valid address is if b*c/a (see above
5095: for notation) is also an integer. */
5096: if (GET_CODE (g1->mult_val) != CONST_INT
5097: || GET_CODE (g2->mult_val) != CONST_INT
5098: || GET_CODE (g1->add_val) != CONST_INT
5099: || g1->mult_val == const0_rtx
5100: || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
5101: return 0;
5102:
5103: mult = gen_rtx (CONST_INT, VOIDmode,
5104: INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
5105: add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult));
5106:
5107: /* Form simplified final result. */
5108: if (mult == const0_rtx)
5109: return add;
5110: else if (mult == const1_rtx)
5111: mult = g1->dest_reg;
5112: else
5113: mult = gen_rtx (MULT, g2->mode, g1->dest_reg, mult);
5114:
5115: if (add == const0_rtx)
5116: return mult;
5117: else
5118: return gen_rtx (PLUS, g2->mode, mult, add);
5119: }
5120: #endif
5121:
5122: /* Return 1 if giv G2 can be combined with G1. This means that G2 can use
5123: (either directly or via an address expression) a register used to represent
5124: G1. Set g2->new_reg to a represtation of G1 (normally just
5125: g1->dest_reg). */
5126:
5127: static int
5128: combine_givs_p (g1, g2)
5129: struct induction *g1, *g2;
5130: {
5131: rtx tem;
5132:
5133: /* If these givs are identical, they can be combined. */
5134: if (rtx_equal_p (g1->mult_val, g2->mult_val)
5135: && rtx_equal_p (g1->add_val, g2->add_val))
5136: {
5137: g2->new_reg = g1->dest_reg;
5138: return 1;
5139: }
5140:
5141: #ifdef ADDRESS_COST
5142: /* If G2 can be expressed as a function of G1 and that function is valid
5143: as an address and no more expensive than using a register for G2,
5144: the expression of G2 in terms of G1 can be used. */
5145: if (g2->giv_type == DEST_ADDR
5146: && (tem = express_from (g1, g2)) != 0
5147: && memory_address_p (g2->mem_mode, tem)
5148: && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location))
5149: {
5150: g2->new_reg = tem;
5151: return 1;
5152: }
5153: #endif
5154:
5155: return 0;
5156: }
5157:
5158: /* Check all pairs of givs for iv_class BL and see if any can be combined with
5159: any other. If so, point SAME to the giv combined with and set NEW_REG to
5160: be an expression (in terms of the other giv's DEST_REG) equivalent to the
5161: giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
5162:
5163: static void
5164: combine_givs (bl)
5165: struct iv_class *bl;
5166: {
5167: struct induction *g1, *g2;
5168: int pass;
5169:
5170: for (g1 = bl->giv; g1; g1 = g1->next_iv)
5171: for (pass = 0; pass <= 1; pass++)
5172: for (g2 = bl->giv; g2; g2 = g2->next_iv)
5173: if (g1 != g2
5174: /* First try to combine with replaceable givs, then all givs. */
5175: && (g1->replaceable || pass == 1)
5176: /* If either has already been combined or is to be ignored, can't
5177: combine. */
5178: && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
5179: /* If something has been based on G2, G2 cannot itself be based
5180: on something else. */
5181: && ! g2->combined_with
5182: && combine_givs_p (g1, g2))
5183: {
5184: /* g2->new_reg set by `combine_givs_p' */
5185: g2->same = g1;
5186: g1->combined_with = 1;
5187: g1->benefit += g2->benefit;
5188: /* ??? The new final_[bg]iv_value code does a much better job
5189: of finding replaceable giv's, and hence this code may no
5190: longer be necessary. */
5191: if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
5192: g1->benefit -= copy_cost;
5193: g1->lifetime += g2->lifetime;
5194: g1->times_used += g2->times_used;
5195:
5196: if (loop_dump_stream)
5197: fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
5198: INSN_UID (g2->insn), INSN_UID (g1->insn));
5199: }
5200: }
5201:
5202: /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
5203:
5204: void
5205: emit_iv_add_mult (b, m, a, reg, insert_before)
5206: rtx b; /* initial value of basic induction variable */
5207: rtx m; /* multiplicative constant */
5208: rtx a; /* additive constant */
5209: rtx reg; /* destination register */
5210: rtx insert_before;
5211: {
5212: rtx seq;
5213: rtx result;
5214:
5215: /* Prevent unexpected sharing of these rtx. */
5216: a = copy_rtx (a);
5217: b = copy_rtx (b);
5218:
5219: /* Increase the lifetime of any invariants moved further in code. */
5220: update_reg_last_use (a, insert_before);
5221: update_reg_last_use (b, insert_before);
5222: update_reg_last_use (m, insert_before);
5223:
5224: start_sequence ();
5225: result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
5226: if (reg != result)
5227: emit_move_insn (reg, result);
5228: seq = gen_sequence ();
5229: end_sequence ();
5230:
5231: emit_insn_before (seq, insert_before);
5232: }
5233:
5234: /* Test whether A * B can be computed without
5235: an actual multiply insn. Value is 1 if so. */
5236:
5237: static int
5238: product_cheap_p (a, b)
5239: rtx a;
5240: rtx b;
5241: {
5242: int i;
5243: rtx tmp;
5244: struct obstack *old_rtl_obstack = rtl_obstack;
5245: char *storage = (char *) obstack_alloc (&temp_obstack, 0);
5246: int win = 1;
5247:
5248: /* If only one is constant, make it B. */
5249: if (GET_CODE (a) == CONST_INT)
5250: tmp = a, a = b, b = tmp;
5251:
5252: /* If first constant, both constant, so don't need multiply. */
5253: if (GET_CODE (a) == CONST_INT)
5254: return 1;
5255:
5256: /* If second not constant, neither is constant, so would need multiply. */
5257: if (GET_CODE (b) != CONST_INT)
5258: return 0;
5259:
5260: /* One operand is constant, so might not need multiply insn. Generate the
5261: code for the multiply and see if a call or multiply, or long sequence
5262: of insns is generated. */
5263:
5264: rtl_obstack = &temp_obstack;
5265: start_sequence ();
5266: expand_mult (GET_MODE (a), a, b, 0, 0);
5267: tmp = gen_sequence ();
5268: end_sequence ();
5269:
5270: if (GET_CODE (tmp) == SEQUENCE)
5271: {
5272: if (XVEC (tmp, 0) == 0)
5273: win = 1;
5274: else if (XVECLEN (tmp, 0) > 3)
5275: win = 0;
5276: else
5277: for (i = 0; i < XVECLEN (tmp, 0); i++)
5278: {
5279: rtx insn = XVECEXP (tmp, 0, i);
5280:
5281: if (GET_CODE (insn) != INSN
5282: || (GET_CODE (PATTERN (insn)) == SET
5283: && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
5284: || (GET_CODE (PATTERN (insn)) == PARALLEL
5285: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
5286: && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
5287: {
5288: win = 0;
5289: break;
5290: }
5291: }
5292: }
5293: else if (GET_CODE (tmp) == SET
5294: && GET_CODE (SET_SRC (tmp)) == MULT)
5295: win = 0;
5296: else if (GET_CODE (tmp) == PARALLEL
5297: && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
5298: && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
5299: win = 0;
5300:
5301: /* Free any storage we obtained in generating this multiply and restore rtl
5302: allocation to its normal obstack. */
5303: obstack_free (&temp_obstack, storage);
5304: rtl_obstack = old_rtl_obstack;
5305:
5306: return win;
5307: }
5308:
5309: /* Check to see if loop can be terminated by a "decrement and branch until
5310: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
5311: Also try reversing an increment loop to a decrement loop
5312: to see if the optimization can be performed.
5313: Value is nonzero if optimization was performed. */
5314:
5315: /* This is useful even if the architecture doesn't have such an insn,
5316: because it might change a loops which increments from 0 to n to a loop
5317: which decrements from n to 0. A loop that decrements to zero is usually
5318: faster than one that increments from zero. */
5319:
5320: /* ??? This could be rewritten to use some of the loop unrolling procedures,
5321: such as approx_final_value, biv_total_increment, loop_iterations, and
5322: final_[bg]iv_value. */
5323:
5324: static int
5325: check_dbra_loop (loop_end, insn_count, loop_start)
5326: rtx loop_end;
5327: int insn_count;
5328: rtx loop_start;
5329: {
5330: struct iv_class *bl;
5331: rtx reg;
5332: rtx jump_label;
5333: rtx final_value;
5334: rtx start_value;
5335: enum rtx_code branch_code;
5336: rtx new_add_val;
5337: rtx comparison;
5338: rtx before_comparison;
5339: rtx p;
5340:
5341: /* If last insn is a conditional branch, and the insn before tests a
5342: register value, try to optimize it. Otherwise, we can't do anything. */
5343:
5344: comparison = get_condition_for_loop (PREV_INSN (loop_end));
5345: if (comparison == 0)
5346: return 0;
5347:
5348: /* Check all of the bivs to see if the compare uses one of them.
5349: Skip biv's set more than once because we can't guarantee that
5350: it will be zero on the last iteration. Also skip if the biv is
5351: used between its update and the test insn. */
5352:
5353: for (bl = loop_iv_list; bl; bl = bl->next)
5354: {
5355: if (bl->biv_count == 1
5356: && bl->biv->dest_reg == XEXP (comparison, 0)
5357: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
5358: PREV_INSN (PREV_INSN (loop_end))))
5359: break;
5360: }
5361:
5362: if (! bl)
5363: return 0;
5364:
5365: /* Look for the case where the basic induction variable is always
5366: nonnegative, and equals zero on the last iteration.
5367: In this case, add a reg_note REG_NONNEG, which allows the
5368: m68k DBRA instruction to be used. */
5369:
5370: if (((GET_CODE (comparison) == GT
5371: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5372: && INTVAL (XEXP (comparison, 1)) == -1)
5373: || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
5374: && GET_CODE (bl->biv->add_val) == CONST_INT
5375: && INTVAL (bl->biv->add_val) < 0)
5376: {
5377: /* Initial value must be greater than 0,
5378: init_val % -dec_value == 0 to ensure that it equals zero on
5379: the last iteration */
5380:
5381: if (GET_CODE (bl->initial_value) == CONST_INT
5382: && INTVAL (bl->initial_value) > 0
5383: && (INTVAL (bl->initial_value) %
5384: (-INTVAL (bl->biv->add_val))) == 0)
5385: {
5386: /* register always nonnegative, add REG_NOTE to branch */
5387: REG_NOTES (PREV_INSN (loop_end))
5388: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5389: REG_NOTES (PREV_INSN (loop_end)));
5390: bl->nonneg = 1;
5391:
5392: return 1;
5393: }
5394:
5395: /* If the decrement is 1 and the value was tested as >= 0 before
5396: the loop, then we can safely optimize. */
5397: for (p = loop_start; p; p = PREV_INSN (p))
5398: {
5399: if (GET_CODE (p) == CODE_LABEL)
5400: break;
5401: if (GET_CODE (p) != JUMP_INSN)
5402: continue;
5403:
5404: before_comparison = get_condition_for_loop (p);
5405: if (before_comparison
5406: && XEXP (before_comparison, 0) == bl->biv->dest_reg
5407: && GET_CODE (before_comparison) == LT
5408: && XEXP (before_comparison, 1) == const0_rtx
5409: && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
5410: && INTVAL (bl->biv->add_val) == -1)
5411: {
5412: REG_NOTES (PREV_INSN (loop_end))
5413: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5414: REG_NOTES (PREV_INSN (loop_end)));
5415: bl->nonneg = 1;
5416:
5417: return 1;
5418: }
5419: }
5420: }
5421: else if (num_mem_sets <= 1)
5422: {
5423: /* Try to change inc to dec, so can apply above optimization. */
5424: /* Can do this if:
5425: all registers modified are induction variables or invariant,
5426: all memory references have non-overlapping addresses
5427: (obviously true if only one write)
5428: allow 2 insns for the compare/jump at the end of the loop. */
5429: int num_nonfixed_reads = 0;
5430: /* 1 if the iteration var is used only to count iterations. */
5431: int no_use_except_counting = 0;
5432:
5433: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5434: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5435: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
5436:
5437: if (bl->giv_count == 0
5438: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
5439: {
5440: rtx bivreg = regno_reg_rtx[bl->regno];
5441:
5442: /* If there are no givs for this biv, and the only exit is the
5443: fall through at the end of the the loop, then
5444: see if perhaps there are no uses except to count. */
5445: no_use_except_counting = 1;
5446: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5447: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5448: {
5449: rtx set = single_set (p);
5450:
5451: if (set && GET_CODE (SET_DEST (set)) == REG
5452: && REGNO (SET_DEST (set)) == bl->regno)
5453: /* An insn that sets the biv is okay. */
5454: ;
5455: else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
5456: || p == prev_nonnote_insn (loop_end))
5457: /* Don't bother about the end test. */
5458: ;
5459: else if (reg_mentioned_p (bivreg, PATTERN (p)))
5460: /* Any other use of the biv is no good. */
5461: {
5462: no_use_except_counting = 0;
5463: break;
5464: }
5465: }
5466: }
5467:
5468: /* This code only acts for innermost loops. Also it simplifies
5469: the memory address check by only reversing loops with
5470: zero or one memory access.
5471: Two memory accesses could involve parts of the same array,
5472: and that can't be reversed. */
5473:
5474: if (num_nonfixed_reads <= 1
5475: && !loop_has_call
5476: && (no_use_except_counting
5477: || (bl->giv_count + bl->biv_count + num_mem_sets
5478: + num_movables + 2 == insn_count)))
5479: {
5480: rtx condition = get_condition_for_loop (PREV_INSN (loop_end));
5481: int win;
5482: rtx tem;
5483:
5484: /* Loop can be reversed. */
5485: if (loop_dump_stream)
5486: fprintf (loop_dump_stream, "Can reverse loop\n");
5487:
5488: /* Now check other conditions:
5489: initial_value must be zero,
5490: final_value % add_val == 0, so that when reversed, the
5491: biv will be zero on the last iteration.
5492:
5493: This test can probably be improved since +/- 1 in the constant
5494: can be obtained by changing LT to LE and vice versa; this is
5495: confusing. */
5496:
5497: if (comparison && bl->initial_value == const0_rtx
5498: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5499: /* LE gets turned into LT */
5500: && GET_CODE (comparison) == LT
5501: && (INTVAL (XEXP (comparison, 1))
5502: % INTVAL (bl->biv->add_val)) == 0)
5503: {
5504: /* Register will always be nonnegative, with value
5505: 0 on last iteration if loop reversed */
5506:
5507: /* Save some info needed to produce the new insns. */
5508: reg = bl->biv->dest_reg;
5509: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
5510: new_add_val = gen_rtx (CONST_INT, VOIDmode,
5511: - INTVAL (bl->biv->add_val));
5512:
5513: final_value = XEXP (comparison, 1);
5514: start_value = gen_rtx (CONST_INT, VOIDmode,
5515: (INTVAL (XEXP (comparison, 1))
5516: - INTVAL (bl->biv->add_val)));
5517:
5518: /* Initialize biv to start_value before loop start.
5519: The old initializing insn will be deleted as a
5520: dead store by flow.c. */
5521: emit_insn_before (gen_move_insn (reg, start_value), loop_start);
5522:
5523: /* Add insn to decrement register, and delete insn
5524: that incremented the register. */
5525: p = emit_insn_before (gen_add2_insn (reg, new_add_val),
5526: bl->biv->insn);
5527: delete_insn (bl->biv->insn);
5528:
5529: /* Update biv info to reflect its new status. */
5530: bl->biv->insn = p;
5531: bl->initial_value = start_value;
5532: bl->biv->add_val = new_add_val;
5533:
5534: /* Inc LABEL_NUSES so that delete_insn will
5535: not delete the label. */
5536: LABEL_NUSES (XEXP (jump_label, 0)) ++;
5537:
5538: /* Emit an insn after the end of the loop to set the biv's
5539: proper exit value if it is used anywhere outside the loop. */
5540: if ((regno_last_uid[bl->regno]
5541: != INSN_UID (PREV_INSN (PREV_INSN (loop_end))))
5542: || ! bl->init_insn
5543: || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn))
5544: emit_insn_after (gen_move_insn (reg, final_value),
5545: loop_end);
5546:
5547: /* Delete compare/branch at end of loop. */
5548: delete_insn (PREV_INSN (loop_end));
5549: delete_insn (PREV_INSN (loop_end));
5550:
5551: /* Add new compare/branch insn at end of loop. */
5552: start_sequence ();
5553: emit_cmp_insn (reg, const0_rtx, GE, 0, GET_MODE (reg), 0, 0);
5554: emit_jump_insn (gen_bge (XEXP (jump_label, 0)));
5555: tem = gen_sequence ();
5556: end_sequence ();
5557: emit_jump_insn_before (tem, loop_end);
5558:
5559: for (tem = PREV_INSN (loop_end);
5560: tem && GET_CODE (tem) != JUMP_INSN; tem = PREV_INSN (tem))
5561: ;
5562: if (tem)
5563: {
5564: JUMP_LABEL (tem) = XEXP (jump_label, 0);
5565:
5566: /* Increment of LABEL_NUSES done above. */
5567: /* Register is now always nonnegative,
5568: so add REG_NONNEG note to the branch. */
5569: REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5570: REG_NOTES (tem));
5571: }
5572:
5573: bl->nonneg = 1;
5574:
5575: /* Mark that this biv has been reversed. Each giv which depends
5576: on this biv, and which is also live past the end of the loop
5577: will have to be fixed up. */
5578:
5579: bl->reversed = 1;
5580:
5581: if (loop_dump_stream)
5582: fprintf (loop_dump_stream,
5583: "Reversed loop and added reg_nonneg\n");
5584:
5585: return 1;
5586: }
5587: }
5588: }
5589:
5590: return 0;
5591: }
5592:
5593: /* Verify whether the biv BL appears to be eliminable,
5594: based on the insns in the loop that refer to it.
5595: LOOP_START is the first insn of the loop, and END is the end insn.
5596:
5597: If ELIMINATE_P is non-zero, actually do the elimination.
5598:
5599: THRESHOLD and INSN_COUNT are from loop_optimize and are used to
5600: determine whether invariant insns should be placed inside or at the
5601: start of the loop. */
5602:
5603: static int
5604: maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
5605: struct iv_class *bl;
5606: rtx loop_start;
5607: rtx end;
5608: int eliminate_p;
5609: int threshold, insn_count;
5610: {
5611: rtx reg = bl->biv->dest_reg;
5612: rtx p, set;
5613: struct induction *v;
5614:
5615: /* Scan all insns in the loop, stopping if we find one that uses the
5616: biv in a way that we cannot eliminate. */
5617:
5618: for (p = loop_start; p != end; p = NEXT_INSN (p))
5619: {
5620: enum rtx_code code = GET_CODE (p);
5621: rtx where = threshold >= insn_count ? loop_start : p;
5622:
5623: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
5624: && reg_mentioned_p (reg, PATTERN (p))
5625: && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
5626: {
5627: if (loop_dump_stream)
5628: fprintf (loop_dump_stream,
5629: "Cannot eliminate biv %d: biv used in insn %d.\n",
5630: bl->regno, INSN_UID (p));
5631: break;
5632: }
5633: }
5634:
5635: if (p == end)
5636: {
5637: if (loop_dump_stream)
5638: fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
5639: bl->regno, eliminate_p ? "was" : "can be");
5640: return 1;
5641: }
5642:
5643: return 0;
5644: }
5645:
5646: /* If BL appears in X (part of the pattern of INSN), see if we can
5647: eliminate its use. If so, return 1. If not, return 0.
5648:
5649: If BIV does not appear in X, return 1.
5650:
5651: If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
5652: where extra insns should be added. Depending on how many items have been
5653: moved out of the loop, it will either be before INSN or at the start of
5654: the loop. */
5655:
5656: static int
5657: maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
5658: rtx x, insn;
5659: struct iv_class *bl;
5660: int eliminate_p;
5661: rtx where;
5662: {
5663: enum rtx_code code = GET_CODE (x);
5664: rtx reg = bl->biv->dest_reg;
5665: enum machine_mode mode = GET_MODE (reg);
5666: struct induction *v;
5667: rtx arg, new, tem;
5668: int arg_operand;
5669: char *fmt;
5670: int i, j;
5671:
5672: switch (code)
5673: {
5674: case REG:
5675: /* If we haven't already been able to do something with this BIV,
5676: we can't eliminate it. */
5677: if (x == reg)
5678: return 0;
5679: return 1;
5680:
5681: case SET:
5682: /* If this sets the BIV, it is not a problem. */
5683: if (SET_DEST (x) == reg)
5684: return 1;
5685:
5686: /* If this is an insn that defines a giv, it is also ok because
5687: it will go away when the giv is reduced. */
5688: for (v = bl->giv; v; v = v->next_iv)
5689: if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
5690: return 1;
5691:
5692: #ifdef HAVE_cc0
5693: if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
5694: {
5695: /* Can replace with any giv that was reduced and
5696: that has (MULT_VAL != 0) and (ADD_VAL == 0).
5697: Require a constant for MULT_VAL, so we know it's nonzero. */
5698:
5699: for (v = bl->giv; v; v = v->next_iv)
5700: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5701: && v->add_val == const0_rtx
5702: && ! v->ignore && ! v->maybe_dead
5703: && v->mode == mode)
5704: {
5705: if (! eliminate_p)
5706: return 1;
5707:
5708: /* If the giv has the opposite direction of change,
5709: then reverse the comparison. */
5710: if (INTVAL (v->mult_val) < 0)
5711: new = gen_rtx (COMPARE, GET_MODE (v->new_reg),
5712: const0_rtx, v->new_reg);
5713: else
5714: new = v->new_reg;
5715:
5716: /* We can probably test that giv's reduced reg. */
5717: if (validate_change (insn, &SET_SRC (x), new, 0))
5718: return 1;
5719: }
5720:
5721: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
5722: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
5723: Require a constant for MULT_VAL, so we know it's nonzero. */
5724:
5725: for (v = bl->giv; v; v = v->next_iv)
5726: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5727: && ! v->ignore && ! v->maybe_dead
5728: && v->mode == mode)
5729: {
5730: if (! eliminate_p)
5731: return 1;
5732:
5733: /* If the giv has the opposite direction of change,
5734: then reverse the comparison. */
5735: if (INTVAL (v->mult_val) < 0)
5736: new = gen_rtx (COMPARE, VOIDmode, copy_rtx (v->add_val),
5737: v->new_reg);
5738: else
5739: new = gen_rtx (COMPARE, VOIDmode, v->new_reg,
5740: copy_rtx (v->add_val));
5741:
5742: /* Replace biv with the giv's reduced register. */
5743: update_reg_last_use (v->add_val, insn);
5744: if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
5745: return 1;
5746:
5747: /* Insn doesn't support that constant or invariant. Copy it
5748: into a register (it will be a loop invariant.) */
5749: tem = gen_reg_rtx (GET_MODE (v->new_reg));
5750:
5751: emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
5752: where);
5753:
5754: if (validate_change (insn, &SET_SRC (PATTERN (insn)),
5755: gen_rtx (COMPARE, VOIDmode,
5756: v->new_reg, tem), 0))
5757: return 1;
5758: }
5759: }
5760: #endif
5761: break;
5762:
5763: case COMPARE:
5764: case EQ: case NE:
5765: case GT: case GE: case GTU: case GEU:
5766: case LT: case LE: case LTU: case LEU:
5767: /* See if either argument is the biv. */
5768: if (XEXP (x, 0) == reg)
5769: arg = XEXP (x, 1), arg_operand = 1;
5770: else if (XEXP (x, 1) == reg)
5771: arg = XEXP (x, 0), arg_operand = 0;
5772: else
5773: break;
5774:
5775: if (CONSTANT_P (arg))
5776: {
5777: /* First try to replace with any giv that has constant positive
5778: mult_val and constant add_val. We might be able to support
5779: negative mult_val, but it seems complex to do it in general. */
5780:
5781: for (v = bl->giv; v; v = v->next_iv)
5782: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
5783: && CONSTANT_P (v->add_val)
5784: && ! v->ignore && ! v->maybe_dead
5785: && v->mode == mode)
5786: {
5787: if (! eliminate_p)
5788: return 1;
5789:
5790: /* Replace biv with the giv's reduced reg. */
5791: XEXP (x, 1-arg_operand) = v->new_reg;
5792:
5793: /* If all constants are actually constant integers and
5794: the derived constant can be directly placed in the COMPARE,
5795: do so. */
5796: if (GET_CODE (arg) == CONST_INT
5797: && GET_CODE (v->mult_val) == CONST_INT
5798: && GET_CODE (v->add_val) == CONST_INT
5799: && validate_change (insn, &XEXP (x, arg_operand),
5800: gen_rtx (CONST_INT, VOIDmode,
5801: (INTVAL (arg)
5802: * INTVAL (v->mult_val)
5803: + INTVAL (v->add_val))), 0))
5804: return 1;
5805:
5806: /* Otherwise, load it into a register. */
5807: tem = gen_reg_rtx (mode);
5808: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
5809: if (validate_change (insn, &XEXP (x, arg_operand), tem, 0))
5810: return 1;
5811:
5812: /* If that failed, put back the change we made above. */
5813: XEXP (x, 1-arg_operand) = reg;
5814: }
5815:
5816: /* Look for giv with positive constant mult_val and nonconst add_val.
5817: Insert insns to calculate new compare value. */
5818:
5819: for (v = bl->giv; v; v = v->next_iv)
5820: if (CONSTANT_P (v->mult_val)
5821: && ! v->ignore && ! v->maybe_dead
5822: && v->mode == mode)
5823: {
5824: rtx tem;
5825:
5826: if (! eliminate_p)
5827: return 1;
5828:
5829: tem = gen_reg_rtx (mode);
5830:
5831: /* Replace biv with giv's reduced register. */
5832: validate_change (insn, &XEXP (x, 1 - arg_operand),
5833: v->new_reg, 1);
5834:
5835: /* Compute value to compare against. */
5836: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
5837: /* Use it in this insn. */
5838: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
5839: if (apply_change_group ())
5840: return 1;
5841: }
5842: }
5843: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
5844: {
5845: if (invariant_p (arg) == 1)
5846: {
5847: /* Look for giv with constant positive mult_val and nonconst
5848: add_val. Insert insns to compute new compare value. */
5849:
5850: for (v = bl->giv; v; v = v->next_iv)
5851: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
5852: && ! v->ignore && ! v->maybe_dead
5853: && v->mode == mode)
5854: {
5855: rtx tem;
5856:
5857: if (! eliminate_p)
5858: return 1;
5859:
5860: tem = gen_reg_rtx (mode);
5861:
5862: /* Replace biv with giv's reduced register. */
5863: validate_change (insn, &XEXP (x, 1 - arg_operand),
5864: v->new_reg, 1);
5865:
5866: /* Compute value to compare against. */
5867: emit_iv_add_mult (arg, v->mult_val, v->add_val,
5868: tem, where);
5869: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
5870: if (apply_change_group ())
5871: return 1;
5872: }
5873: }
5874:
5875: /* This code has problems. Basically, you can't know when
5876: seeing if we will eliminate BL, whether a particular giv
5877: of ARG will be reduced. If it isn't going to be reduced,
5878: we can't eliminate BL. We can try forcing it to be reduced,
5879: but that can generate poor code.
5880:
5881: The problem is that the benefit of reducing TV, below should
5882: be increased if BL can actually be eliminated, but this means
5883: we might have to do a topological sort of the order in which
5884: we try to process biv. It doesn't seem worthwhile to do
5885: this sort of thing now. */
5886:
5887: #if 0
5888: /* Otherwise the reg compared with had better be a biv. */
5889: if (GET_CODE (arg) != REG
5890: || reg_iv_type[REGNO (arg)] != BASIC_INDUCT)
5891: return 0;
5892:
5893: /* Look for a pair of givs, one for each biv,
5894: with identical coefficients. */
5895: for (v = bl->giv; v; v = v->next_iv)
5896: {
5897: struct induction *tv;
5898:
5899: if (v->ignore || v->maybe_dead || v->mode != mode)
5900: continue;
5901:
5902: for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
5903: if (! tv->ignore && ! tv->maybe_dead
5904: && rtx_equal_p (tv->mult_val, v->mult_val)
5905: && rtx_equal_p (tv->add_val, v->add_val)
5906: && tv->mode == mode)
5907: {
5908: if (! eliminate_p)
5909: return 1;
5910:
5911: /* Replace biv with its giv's reduced reg. */
5912: XEXP (x, 1-arg_operand) = v->new_reg;
5913: /* Replace other operand with the other giv's
5914: reduced reg. */
5915: XEXP (x, arg_operand) = tv->new_reg;
5916: return 1;
5917: }
5918: }
5919: #endif
5920: }
5921:
5922: /* If we get here, the biv can't be eliminated. */
5923: return 0;
5924:
5925: case MEM:
5926: /* If this address is a DEST_ADDR giv, it doesn't matter if the
5927: biv is used in it, since it will be replaced. */
5928: for (v = bl->giv; v; v = v->next_iv)
5929: if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
5930: return 1;
5931: break;
5932: }
5933:
5934: /* See if any subexpression fails elimination. */
5935: fmt = GET_RTX_FORMAT (code);
5936: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5937: {
5938: switch (fmt[i])
5939: {
5940: case 'e':
5941: if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl,
5942: eliminate_p, where))
5943: return 0;
5944: break;
5945:
5946: case 'E':
5947: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5948: if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl,
5949: eliminate_p, where))
5950: return 0;
5951: break;
5952: }
5953: }
5954:
5955: return 1;
5956: }
5957:
5958: /* Return nonzero if the last use of REG
5959: is in an insn following INSN in the same basic block. */
5960:
5961: static int
5962: last_use_this_basic_block (reg, insn)
5963: rtx reg;
5964: rtx insn;
5965: {
5966: rtx n;
5967: for (n = insn;
5968: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
5969: n = NEXT_INSN (n))
5970: {
5971: if (regno_last_uid[REGNO (reg)] == INSN_UID (n))
5972: return 1;
5973: }
5974: return 0;
5975: }
5976:
5977: /* Called via `note_stores' to record the initial value of a biv. Here we
5978: just record the location of the set and process it later. */
5979:
5980: static void
5981: record_initial (dest, set)
5982: rtx dest;
5983: rtx set;
5984: {
5985: struct iv_class *bl;
5986:
5987: if (GET_CODE (dest) != REG
5988: || REGNO (dest) >= max_reg_before_loop
5989: || reg_iv_type[REGNO (dest)] != BASIC_INDUCT)
5990: return;
5991:
5992: bl = reg_biv_class[REGNO (dest)];
5993:
5994: /* If this is the first set found, record it. */
5995: if (bl->init_insn == 0)
5996: {
5997: bl->init_insn = note_insn;
5998: bl->init_set = set;
5999: }
6000: }
6001:
6002: /* If any of the registers in X are "old" and currently have a last use earlier
6003: than INSN, update them to have a last use of INSN. Their actual last use
6004: will be the previous insn but it will not have a valid uid_luid so we can't
6005: use it. */
6006:
6007: static void
6008: update_reg_last_use (x, insn)
6009: rtx x;
6010: rtx insn;
6011: {
6012: /* Check for the case where INSN does not have a valid luid. In this case,
6013: there is no need to modify the regno_last_uid, as this can only happen
6014: when code is inserted after the loop_end to set a pseudo's final value,
6015: and hence this insn will never be the last use of x. */
6016: if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
6017: && INSN_UID (insn) < max_uid_for_loop
6018: && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)])
6019: regno_last_uid[REGNO (x)] = INSN_UID (insn);
6020: else
6021: {
6022: register int i, j;
6023: register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
6024: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
6025: {
6026: if (fmt[i] == 'e')
6027: update_reg_last_use (XEXP (x, i), insn);
6028: else if (fmt[i] == 'E')
6029: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6030: update_reg_last_use (XVECEXP (x, i, j), insn);
6031: }
6032: }
6033: }
6034:
6035: /* Given a jump insn JUMP, return the condition that will cause it to branch
6036: to its JUMP_LABEL. If the condition cannot be understood, or is an
6037: inequality floating-point comparison which needs to be reversed, 0 will
6038: be returned.
6039:
6040: If EARLIEST is non-zero, it is a pointer to a place where the earliest
6041: insn used in locating the condition was found. If a replacement test
6042: of the condition is desired, it should be placed in front of that
6043: insn and we will be sure that the inputs are still valid.
6044:
6045: The condition will be returned in a canonical form to simplify testing by
6046: callers. Specifically:
6047:
6048: (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
6049: (2) Both operands will be machine operands; (cc0) will have been replaced.
6050: (3) If an operand is a constant, it will be the second operand.
6051: (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
6052: for GE, GEU, and LEU. */
6053:
6054: rtx
6055: get_condition (jump, earliest)
6056: rtx jump;
6057: rtx *earliest;
6058: {
6059: enum rtx_code code;
6060: rtx prev = jump;
6061: rtx set;
6062: rtx tem;
6063: rtx op0, op1;
6064: int reverse_code = 0;
6065: int did_reverse_condition = 0;
6066:
6067: /* If this is not a standard conditional jump, we can't parse it. */
6068: if (GET_CODE (jump) != JUMP_INSN
6069: || ! condjump_p (jump) || simplejump_p (jump))
6070: return 0;
6071:
6072: code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0));
6073: op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0);
6074: op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1);
6075:
6076: if (earliest)
6077: *earliest = jump;
6078:
6079: /* If this branches to JUMP_LABEL when the condition is false, reverse
6080: the condition. */
6081: if (XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump))
6082: code = reverse_condition (code), did_reverse_condition ^= 1;
6083:
6084: /* If we are comparing a register with zero, see if the register is set
6085: in the previous insn to a COMPARE or a comparison operation. Perform
6086: the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
6087: in cse.c */
6088:
6089: while (GET_RTX_CLASS (code) == '<' && op1 == const0_rtx)
6090: {
6091: /* Set non-zero when we find something of interest. */
6092: rtx x = 0;
6093:
6094: #ifdef HAVE_cc0
6095: /* If comparison with cc0, import actual comparison from compare
6096: insn. */
6097: if (op0 == cc0_rtx)
6098: {
6099: if ((prev = prev_nonnote_insn (prev)) == 0
6100: || GET_CODE (prev) != INSN
6101: || (set = single_set (prev)) == 0
6102: || SET_DEST (set) != cc0_rtx)
6103: return 0;
6104:
6105: op0 = SET_SRC (set);
6106: op1 = CONST0_RTX (GET_MODE (op0));
6107: if (earliest)
6108: *earliest = prev;
6109: }
6110: #endif
6111:
6112: /* If this is a COMPARE, pick up the two things being compared. */
6113: if (GET_CODE (op0) == COMPARE)
6114: {
6115: op1 = XEXP (op0, 1);
6116: op0 = XEXP (op0, 0);
6117: continue;
6118: }
6119: else if (GET_CODE (op0) != REG)
6120: break;
6121:
6122: /* Go back to the previous insn. Stop if it is not an INSN. We also
6123: stop if it isn't a single set or if it has a REG_INC note because
6124: we don't want to bother dealing with it. */
6125:
6126: if ((prev = prev_nonnote_insn (prev)) == 0
6127: || GET_CODE (prev) != INSN
6128: || FIND_REG_INC_NOTE (prev, 0)
6129: || (set = single_set (prev)) == 0)
6130: break;
6131:
6132: /* If this is setting OP0, get what it sets it to if it looks
6133: relevant. */
6134: if (SET_DEST (set) == op0)
6135: {
6136: enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
6137:
6138: if ((GET_CODE (SET_SRC (set)) == COMPARE
6139: || ((code == NE
6140: || (code == LT
6141: && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
6142: && (STORE_FLAG_VALUE
6143: & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
6144: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')))
6145: x = SET_SRC (set);
6146: else if ((code == EQ
6147: || (code == GE
6148: && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
6149: && (STORE_FLAG_VALUE
6150: & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
6151: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')
6152: {
6153: /* We might have reversed a LT to get a GE here. But this wasn't
6154: actually the comparison of data, so we don't flag that we
6155: have had to reverse the condition. */
6156: did_reverse_condition ^= 1;
6157: reverse_code = 1;
6158: x = SET_SRC (set);
6159: }
6160: }
6161:
6162: else if (reg_set_p (op0, prev))
6163: /* If this sets OP0, but not directly, we have to give up. */
6164: break;
6165:
6166: if (x)
6167: {
6168: if (GET_RTX_CLASS (GET_CODE (x)) == '<')
6169: code = GET_CODE (x);
6170: if (reverse_code)
6171: {
6172: code = reverse_condition (code);
6173: did_reverse_condition ^= 1;
6174: reverse_code = 0;
6175: }
6176:
6177: op0 = XEXP (x, 0), op1 = XEXP (x, 1);
6178: if (earliest)
6179: *earliest = prev;
6180: }
6181: }
6182:
6183: /* If constant is first, put it last. */
6184: if (CONSTANT_P (op0))
6185: code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
6186:
6187: /* If OP0 is the result of a comparison, we weren't able to find what
6188: was really being compared, so fail. */
6189: if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
6190: return 0;
6191:
6192: /* Canonicalize any ordered comparison with integers involving equality. */
6193: if (GET_CODE (op1) == CONST_INT)
6194: {
6195: int const_val = INTVAL (op1);
6196: unsigned uconst_val = (unsigned) const_val;
6197:
6198: switch (code)
6199: {
6200: case LE:
6201: code = LT;
6202: op1 = gen_rtx (CONST_INT, VOIDmode, const_val + 1);
6203: break;
6204:
6205: case GE:
6206: code = GT;
6207: op1 = gen_rtx (CONST_INT, VOIDmode, const_val - 1);
6208: break;
6209:
6210: case LEU:
6211: code = LTU;
6212: op1 = gen_rtx (CONST_INT, VOIDmode, uconst_val + 1);
6213: break;
6214:
6215: case GEU:
6216: code = GTU;
6217: op1 = gen_rtx (CONST_INT, VOIDmode, uconst_val - 1);
6218: break;
6219: }
6220: }
6221:
6222: /* If this was floating-point and we reversed anything other than an
6223: EQ or NE, return zero. */
6224: if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
6225: && did_reverse_condition && code != NE && code != EQ
6226: && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
6227: return 0;
6228:
6229: #ifdef HAVE_cc0
6230: /* Never return CC0; return zero instead. */
6231: if (op0 == cc0_rtx)
6232: return 0;
6233: #endif
6234:
6235: return gen_rtx (code, VOIDmode, op0, op1);
6236: }
6237:
6238: /* Similar to above routine, except that we also put an invariant last
6239: unless both operands are invariants. */
6240:
6241: rtx
6242: get_condition_for_loop (x)
6243: rtx x;
6244: {
6245: rtx comparison = get_condition (x, 0);
6246:
6247: if (comparison == 0
6248: || ! invariant_p (XEXP (comparison, 0))
6249: || invariant_p (XEXP (comparison, 1)))
6250: return comparison;
6251:
6252: return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode,
6253: XEXP (comparison, 1), XEXP (comparison, 0));
6254: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.