![[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.
1.1.1.2 ! root 51: The luids are like uids but increase monotonically always.
1.1 root 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:
1.1.1.2 ! root 1461: /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
! 1462: insns in INSNS which use thet reference. */
! 1463:
! 1464: static void
! 1465: add_label_notes (x, insns)
! 1466: rtx x;
! 1467: rtx insns;
! 1468: {
! 1469: enum rtx_code code = GET_CODE (x);
! 1470: int i;
! 1471: char *fmt;
! 1472: rtx insn;
! 1473:
! 1474: if (code == LABEL_REF)
! 1475: {
! 1476: for (insn = insns; insn; insn = NEXT_INSN (insn))
! 1477: if (reg_mentioned_p (XEXP (x, 0), insn))
! 1478: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0),
! 1479: REG_NOTES (insn));
! 1480: return;
! 1481: }
! 1482:
! 1483: fmt = GET_RTX_FORMAT (code);
! 1484: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
! 1485: if (fmt[i] == 'e')
! 1486: add_label_notes (XEXP (x, i), insns);
! 1487: }
! 1488:
1.1 root 1489: /* Scan MOVABLES, and move the insns that deserve to be moved.
1490: If two matching movables are combined, replace one reg with the
1491: other throughout. */
1492:
1493: static void
1494: move_movables (movables, threshold, insn_count, loop_start, end, nregs)
1495: struct movable *movables;
1496: int threshold;
1497: int insn_count;
1498: rtx loop_start;
1499: rtx end;
1500: int nregs;
1501: {
1502: rtx new_start = 0;
1503: register struct movable *m;
1504: register rtx p;
1505: /* Map of pseudo-register replacements to handle combining
1506: when we move several insns that load the same value
1507: into different pseudo-registers. */
1508: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
1509: char *already_moved = (char *) alloca (nregs);
1510:
1511: bzero (already_moved, nregs);
1512: bzero (reg_map, nregs * sizeof (rtx));
1513:
1514: num_movables = 0;
1515:
1516: for (m = movables; m; m = m->next)
1517: {
1518: /* Describe this movable insn. */
1519:
1520: if (loop_dump_stream)
1521: {
1522: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
1523: INSN_UID (m->insn), m->regno, m->lifetime);
1524: if (m->consec > 0)
1525: fprintf (loop_dump_stream, "consec %d, ", m->consec);
1526: if (m->cond)
1527: fprintf (loop_dump_stream, "cond ");
1528: if (m->force)
1529: fprintf (loop_dump_stream, "force ");
1530: if (m->global)
1531: fprintf (loop_dump_stream, "global ");
1532: if (m->done)
1533: fprintf (loop_dump_stream, "done ");
1534: if (m->move_insn)
1535: fprintf (loop_dump_stream, "move-insn ");
1536: if (m->match)
1537: fprintf (loop_dump_stream, "matches %d ",
1538: INSN_UID (m->match->insn));
1539: if (m->forces)
1540: fprintf (loop_dump_stream, "forces %d ",
1541: INSN_UID (m->forces->insn));
1542: }
1543:
1544: /* Count movables. Value used in heuristics in strength_reduce. */
1545: num_movables++;
1546:
1547: /* Ignore the insn if it's already done (it matched something else).
1548: Otherwise, see if it is now safe to move. */
1549:
1550: if (!m->done
1551: && (! m->cond
1552: || (1 == invariant_p (m->set_src)
1553: && (m->dependencies == 0
1554: || 1 == invariant_p (m->dependencies))
1555: && (m->consec == 0
1556: || 1 == consec_sets_invariant_p (m->set_dest,
1557: m->consec + 1,
1558: m->insn))))
1559: && (! m->forces || m->forces->done))
1560: {
1561: register int regno;
1562: register rtx p;
1563: int savings = m->savings;
1564:
1565: /* We have an insn that is safe to move.
1566: Compute its desirability. */
1567:
1568: p = m->insn;
1569: regno = m->regno;
1570:
1571: if (loop_dump_stream)
1572: fprintf (loop_dump_stream, "savings %d ", savings);
1573:
1574: if (moved_once[regno])
1575: {
1576: insn_count *= 2;
1577:
1578: if (loop_dump_stream)
1579: fprintf (loop_dump_stream, "halved since already moved ");
1580: }
1581:
1582: /* An insn MUST be moved if we already moved something else
1583: which is safe only if this one is moved too: that is,
1584: if already_moved[REGNO] is nonzero. */
1585:
1586: /* An insn is desirable to move if the new lifetime of the
1587: register is no more than THRESHOLD times the old lifetime.
1588: If it's not desirable, it means the loop is so big
1589: that moving won't speed things up much,
1590: and it is liable to make register usage worse. */
1591:
1592: /* It is also desirable to move if it can be moved at no
1593: extra cost because something else was already moved. */
1594:
1595: if (already_moved[regno]
1596: || (threshold * savings * m->lifetime) >= insn_count
1597: || (m->forces && m->forces->done
1598: && n_times_used[m->forces->regno] == 1))
1599: {
1600: int count;
1601: register struct movable *m1;
1602: rtx first;
1603:
1604: /* Now move the insns that set the reg. */
1605:
1606: if (m->partial && m->match)
1607: {
1608: rtx newpat, i1;
1609: rtx r1, r2;
1610: /* Find the end of this chain of matching regs.
1611: Thus, we load each reg in the chain from that one reg.
1612: And that reg is loaded with 0 directly,
1613: since it has ->match == 0. */
1614: for (m1 = m; m1->match; m1 = m1->match);
1615: newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
1616: SET_DEST (PATTERN (m1->insn)));
1617: i1 = emit_insn_before (newpat, loop_start);
1618:
1619: /* Mark the moved, invariant reg as being allowed to
1620: share a hard reg with the other matching invariant. */
1621: REG_NOTES (i1) = REG_NOTES (m->insn);
1622: r1 = SET_DEST (PATTERN (m->insn));
1623: r2 = SET_DEST (PATTERN (m1->insn));
1624: regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, r1,
1625: gen_rtx (EXPR_LIST, VOIDmode, r2,
1626: regs_may_share));
1627: delete_insn (m->insn);
1628:
1629: if (new_start == 0)
1630: new_start = i1;
1631:
1632: if (loop_dump_stream)
1633: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1634: }
1635: /* If we are to re-generate the item being moved with a
1636: new move insn, first delete what we have and then emit
1637: the move insn before the loop. */
1638: else if (m->move_insn)
1639: {
1640: rtx i1, temp;
1641:
1642: for (count = m->consec; count >= 0; count--)
1643: {
1644: /* If this is the first insn of a library call sequence,
1645: skip to the end. */
1646: if (GET_CODE (p) != NOTE
1647: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
1648: p = XEXP (temp, 0);
1649:
1650: /* If this is the last insn of a libcall sequence, then
1651: delete every insn in the sequence except the last.
1652: The last insn is handled in the normal manner. */
1653: if (GET_CODE (p) != NOTE
1654: && (temp = find_reg_note (p, REG_RETVAL, 0)))
1655: {
1656: temp = XEXP (temp, 0);
1657: while (temp != p)
1658: temp = delete_insn (temp);
1659: }
1660:
1661: p = delete_insn (p);
1662: }
1663:
1664: start_sequence ();
1665: emit_move_insn (m->set_dest, m->set_src);
1.1.1.2 ! root 1666: temp = get_insns ();
1.1 root 1667: end_sequence ();
1668:
1.1.1.2 ! root 1669: add_label_notes (m->set_src, temp);
! 1670:
! 1671: i1 = emit_insns_before (temp, loop_start);
1.1 root 1672: if (! find_reg_note (i1, REG_EQUAL, 0))
1673: REG_NOTES (i1)
1674: = gen_rtx (EXPR_LIST,
1675: m->is_equiv ? REG_EQUIV : REG_EQUAL,
1676: m->set_src, REG_NOTES (i1));
1677:
1678: if (loop_dump_stream)
1679: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
1680:
1681: /* The more regs we move, the less we like moving them. */
1682: threshold -= 3;
1683: }
1684: else
1685: {
1686: for (count = m->consec; count >= 0; count--)
1687: {
1688: rtx i1, temp;
1689:
1690: /* If first insn of libcall sequence, skip to end. */
1691: /* Do this at start of loop, since p is guaranteed to
1692: be an insn here. */
1693: if (GET_CODE (p) != NOTE
1694: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
1695: p = XEXP (temp, 0);
1696:
1697: /* If last insn of libcall sequence, move all
1698: insns except the last before the loop. The last
1699: insn is handled in the normal manner. */
1700: if (GET_CODE (p) != NOTE
1701: && (temp = find_reg_note (p, REG_RETVAL, 0)))
1702: {
1703: rtx fn_address = 0;
1704: rtx fn_reg = 0;
1705: rtx fn_address_insn = 0;
1706:
1707: first = 0;
1708: for (temp = XEXP (temp, 0); temp != p;
1709: temp = NEXT_INSN (temp))
1710: {
1711: rtx body;
1712: rtx n;
1713: rtx next;
1714:
1715: if (GET_CODE (temp) == NOTE)
1716: continue;
1717:
1718: body = PATTERN (temp);
1719:
1720: /* Find the next insn after TEMP,
1721: not counting USE or NOTE insns. */
1722: for (next = NEXT_INSN (temp); next != p;
1723: next = NEXT_INSN (next))
1724: if (! (GET_CODE (next) == INSN
1725: && GET_CODE (PATTERN (next)) == USE)
1726: && GET_CODE (next) != NOTE)
1727: break;
1728:
1729: /* If that is the call, this may be the insn
1730: that loads the function address.
1731:
1732: Extract the function address from the insn
1733: that loads it into a register.
1734: If this insn was cse'd, we get incorrect code.
1735:
1736: So emit a new move insn that copies the
1737: function address into the register that the
1738: call insn will use. flow.c will delete any
1739: redundant stores that we have created. */
1740: if (GET_CODE (next) == CALL_INSN
1741: && GET_CODE (body) == SET
1742: && GET_CODE (SET_DEST (body)) == REG
1743: && (n = find_reg_note (temp, REG_EQUAL, 0)))
1744: {
1745: fn_reg = SET_SRC (body);
1746: if (GET_CODE (fn_reg) != REG)
1747: fn_reg = SET_DEST (body);
1748: fn_address = XEXP (n, 0);
1749: fn_address_insn = temp;
1750: }
1751: /* We have the call insn.
1752: If it uses the register we suspect it might,
1753: load it with the correct address directly. */
1754: if (GET_CODE (temp) == CALL_INSN
1755: && fn_address != 0
1756: && reg_mentioned_p (fn_reg, body))
1757: emit_insn_after (gen_move_insn (fn_reg,
1758: fn_address),
1759: fn_address_insn);
1760:
1761: if (GET_CODE (temp) == CALL_INSN)
1762: i1 = emit_call_insn_before (body, loop_start);
1763: else
1764: i1 = emit_insn_before (body, loop_start);
1765: if (first == 0)
1766: first = i1;
1767: if (temp == fn_address_insn)
1768: fn_address_insn = i1;
1769: REG_NOTES (i1) = REG_NOTES (temp);
1770: delete_insn (temp);
1771: }
1772: }
1773: if (m->savemode != VOIDmode)
1774: {
1775: /* P sets REG to zero; but we should clear only
1776: the bits that are not covered by the mode
1777: m->savemode. */
1778: rtx reg = m->set_dest;
1779: rtx sequence;
1780: rtx tem;
1781:
1782: start_sequence ();
1783: tem = expand_binop
1784: (GET_MODE (reg), and_optab, reg,
1785: gen_rtx (CONST_INT, VOIDmode,
1786: ((1 << GET_MODE_BITSIZE (m->savemode)))
1787: - 1),
1788: reg, 1, OPTAB_LIB_WIDEN);
1789: if (tem == 0)
1790: abort ();
1791: if (tem != reg)
1792: emit_move_insn (reg, tem);
1793: sequence = gen_sequence ();
1794: end_sequence ();
1795: i1 = emit_insn_before (sequence, loop_start);
1796: }
1797: else if (GET_CODE (p) == CALL_INSN)
1798: i1 = emit_call_insn_before (PATTERN (p), loop_start);
1799: else
1800: i1 = emit_insn_before (PATTERN (p), loop_start);
1801:
1802: REG_NOTES (i1) = REG_NOTES (p);
1803:
1804: if (new_start == 0)
1805: new_start = i1;
1806:
1807: if (loop_dump_stream)
1808: fprintf (loop_dump_stream, " moved to %d",
1809: INSN_UID (i1));
1810:
1811: #if 0
1812: /* This isn't needed because REG_NOTES is copied
1813: below and is wrong since P might be a PARALLEL. */
1814: if (REG_NOTES (i1) == 0
1815: && ! m->partial /* But not if it's a zero-extend clr. */
1816: && ! m->global /* and not if used outside the loop
1817: (since it might get set outside). */
1818: && CONSTANT_P (SET_SRC (PATTERN (p))))
1819: REG_NOTES (i1)
1820: = gen_rtx (EXPR_LIST, REG_EQUAL,
1821: SET_SRC (PATTERN (p)), REG_NOTES (i1));
1822: #endif
1823:
1824: /* If library call, now fix the REG_NOTES that contain
1825: insn pointers, namely REG_LIBCALL on FIRST
1826: and REG_RETVAL on I1. */
1827: if (temp = find_reg_note (i1, REG_RETVAL, 0))
1828: {
1829: XEXP (temp, 0) = first;
1830: temp = find_reg_note (first, REG_LIBCALL, 0);
1831: XEXP (temp, 0) = i1;
1832: }
1833:
1834: delete_insn (p);
1835: do p = NEXT_INSN (p);
1836: while (p && GET_CODE (p) == NOTE);
1837: }
1838:
1839: /* The more regs we move, the less we like moving them. */
1840: threshold -= 3;
1841: }
1842:
1843: /* Any other movable that loads the same register
1844: MUST be moved. */
1845: already_moved[regno] = 1;
1846:
1847: /* This reg has been moved out of one loop. */
1848: moved_once[regno] = 1;
1849:
1850: /* The reg set here is now invariant. */
1851: if (! m->partial)
1852: n_times_set[regno] = 0;
1853:
1854: m->done = 1;
1855:
1856: /* Change the length-of-life info for the register
1857: to say it lives at least the full length of this loop.
1858: This will help guide optimizations in outer loops. */
1859:
1860: if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start))
1861: /* This is the old insn before all the moved insns.
1862: We can't use the moved insn because it is out of range
1863: in uid_luid. Only the old insns have luids. */
1864: regno_first_uid[regno] = INSN_UID (loop_start);
1865: if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end))
1866: regno_last_uid[regno] = INSN_UID (end);
1867:
1868: /* Combine with this moved insn any other matching movables. */
1869:
1870: if (! m->partial)
1871: for (m1 = movables; m1; m1 = m1->next)
1872: if (m1->match == m)
1873: {
1874: rtx temp;
1875:
1876: /* Schedule the reg loaded by M1
1877: for replacement so that shares the reg of M.
1878: If the modes differ (only possible in restricted
1879: circumstances, make a SUBREG. */
1880: if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
1881: reg_map[m1->regno] = m->set_dest;
1882: else
1883: reg_map[m1->regno]
1884: = gen_lowpart_common (GET_MODE (m1->set_dest),
1885: m->set_dest);
1886:
1887: /* Get rid of the matching insn
1888: and prevent further processing of it. */
1889: m1->done = 1;
1890:
1891: /* if library call, delete all insn except last, which
1892: is deleted below */
1893: if (temp = find_reg_note (m1->insn, REG_RETVAL, 0))
1894: {
1895: for (temp = XEXP (temp, 0); temp != m1->insn;
1896: temp = NEXT_INSN (temp))
1897: delete_insn (temp);
1898: }
1899: delete_insn (m1->insn);
1900:
1901: /* Any other movable that loads the same register
1902: MUST be moved. */
1903: already_moved[m1->regno] = 1;
1904:
1905: /* The reg merged here is now invariant,
1906: if the reg it matches is invariant. */
1907: if (! m->partial)
1908: n_times_set[m1->regno] = 0;
1909: }
1910: }
1911: else if (loop_dump_stream)
1912: fprintf (loop_dump_stream, "not desirable");
1913: }
1914: else if (loop_dump_stream && !m->match)
1915: fprintf (loop_dump_stream, "not safe");
1916:
1917: if (loop_dump_stream)
1918: fprintf (loop_dump_stream, "\n");
1919: }
1920:
1921: if (new_start == 0)
1922: new_start = loop_start;
1923:
1924: /* Go through all the instructions in the loop, making
1925: all the register substitutions scheduled in REG_MAP. */
1926: for (p = new_start; p != end; p = NEXT_INSN (p))
1927: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
1928: || GET_CODE (p) == CALL_INSN)
1929: {
1930: replace_regs (PATTERN (p), reg_map, nregs, 0);
1931: replace_regs (REG_NOTES (p), reg_map, nregs, 0);
1932: }
1933: }
1934:
1935: #if 0
1936: /* Scan X and replace the address of any MEM in it with ADDR.
1937: REG is the address that MEM should have before the replacement. */
1938:
1939: static void
1940: replace_call_address (x, reg, addr)
1941: rtx x, reg, addr;
1942: {
1943: register enum rtx_code code;
1944: register int i;
1945: register char *fmt;
1946:
1947: if (x == 0)
1948: return;
1949: code = GET_CODE (x);
1950: switch (code)
1951: {
1952: case PC:
1953: case CC0:
1954: case CONST_INT:
1955: case CONST_DOUBLE:
1956: case CONST:
1957: case SYMBOL_REF:
1958: case LABEL_REF:
1959: case REG:
1960: return;
1961:
1962: case SET:
1963: /* Short cut for very common case. */
1964: replace_call_address (XEXP (x, 1), reg, addr);
1965: return;
1966:
1967: case CALL:
1968: /* Short cut for very common case. */
1969: replace_call_address (XEXP (x, 0), reg, addr);
1970: return;
1971:
1972: case MEM:
1973: /* If this MEM uses a reg other than the one we expected,
1974: something is wrong. */
1975: if (XEXP (x, 0) != reg)
1976: abort ();
1977: XEXP (x, 0) = addr;
1978: return;
1979: }
1980:
1981: fmt = GET_RTX_FORMAT (code);
1982: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1983: {
1984: if (fmt[i] == 'e')
1985: replace_call_address (XEXP (x, i), reg, addr);
1986: if (fmt[i] == 'E')
1987: {
1988: register int j;
1989: for (j = 0; j < XVECLEN (x, i); j++)
1990: replace_call_address (XVECEXP (x, i, j), reg, addr);
1991: }
1992: }
1993: }
1994: #endif
1995:
1996: /* Return the number of memory refs to addresses that vary
1997: in the rtx X. */
1998:
1999: static int
2000: count_nonfixed_reads (x)
2001: rtx x;
2002: {
2003: register enum rtx_code code;
2004: register int i;
2005: register char *fmt;
2006: int value;
2007:
2008: if (x == 0)
2009: return 0;
2010:
2011: code = GET_CODE (x);
2012: switch (code)
2013: {
2014: case PC:
2015: case CC0:
2016: case CONST_INT:
2017: case CONST_DOUBLE:
2018: case CONST:
2019: case SYMBOL_REF:
2020: case LABEL_REF:
2021: case REG:
2022: return 0;
2023:
2024: case MEM:
2025: return ((invariant_p (XEXP (x, 0)) != 1)
2026: + count_nonfixed_reads (XEXP (x, 0)));
2027: }
2028:
2029: value = 0;
2030: fmt = GET_RTX_FORMAT (code);
2031: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2032: {
2033: if (fmt[i] == 'e')
2034: value += count_nonfixed_reads (XEXP (x, i));
2035: if (fmt[i] == 'E')
2036: {
2037: register int j;
2038: for (j = 0; j < XVECLEN (x, i); j++)
2039: value += count_nonfixed_reads (XVECEXP (x, i, j));
2040: }
2041: }
2042: return value;
2043: }
2044:
2045:
2046: #if 0
2047: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
2048: Replace it with an instruction to load just the low bytes
2049: if the machine supports such an instruction,
2050: and insert above LOOP_START an instruction to clear the register. */
2051:
2052: static void
2053: constant_high_bytes (p, loop_start)
2054: rtx p, loop_start;
2055: {
2056: register rtx new;
2057: register int insn_code_number;
2058:
2059: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
2060: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
2061:
2062: new = gen_rtx (SET, VOIDmode,
2063: gen_rtx (STRICT_LOW_PART, VOIDmode,
2064: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
2065: SET_DEST (PATTERN (p)),
2066: 0)),
2067: XEXP (SET_SRC (PATTERN (p)), 0));
2068: insn_code_number = recog (new, p);
2069:
2070: if (insn_code_number)
2071: {
2072: register int i;
2073:
2074: /* Clear destination register before the loop. */
2075: emit_insn_before (gen_rtx (SET, VOIDmode,
2076: SET_DEST (PATTERN (p)),
2077: const0_rtx),
2078: loop_start);
2079:
2080: /* Inside the loop, just load the low part. */
2081: PATTERN (p) = new;
2082: }
2083: }
2084: #endif
2085:
2086: /* Scan a loop setting the variables `unknown_address_altered',
2087: `num_mem_sets', `loop_continue', loops_enclosed' and `loop_has_call'.
2088: Also, fill in the array `loop_store_mems'. */
2089:
2090: static void
2091: prescan_loop (start, end)
2092: rtx start, end;
2093: {
2094: register int level = 1;
2095: register rtx insn;
2096:
2097: unknown_address_altered = 0;
2098: loop_has_call = 0;
2099: loop_store_mems_idx = 0;
2100:
2101: num_mem_sets = 0;
2102: loops_enclosed = 1;
2103: loop_continue = 0;
2104:
2105: for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2106: insn = NEXT_INSN (insn))
2107: {
2108: if (GET_CODE (insn) == NOTE)
2109: {
2110: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2111: {
2112: ++level;
2113: /* Count number of loops contained in this one. */
2114: loops_enclosed++;
2115: }
2116: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2117: {
2118: --level;
2119: if (level == 0)
2120: {
2121: end = insn;
2122: break;
2123: }
2124: }
2125: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
2126: {
2127: if (level == 1)
2128: loop_continue = insn;
2129: }
2130: }
2131: else if (GET_CODE (insn) == CALL_INSN)
2132: {
2133: unknown_address_altered = 1;
2134: loop_has_call = 1;
2135: }
2136: else
2137: {
2138: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2139: note_stores (PATTERN (insn), note_addr_stored);
2140: }
2141: }
2142: }
2143:
2144: /* Scan the function looking for loops. Record the start and end of each loop.
2145: Also mark as invalid loops any loops that contain a setjmp or are branched
2146: to from outside the loop. */
2147:
2148: static void
2149: find_and_verify_loops (f)
2150: rtx f;
2151: {
2152: rtx insn;
2153: int current_loop = -1;
2154: int next_loop = -1;
2155: int loop;
2156:
2157: /* If there are jumps to undefined labels,
2158: treat them as jumps out of any/all loops.
2159: This also avoids writing past end of tables when there are no loops. */
2160: uid_loop_num[0] = -1;
2161:
2162: /* Find boundaries of loops, mark which loops are contained within
2163: loops, and invalidate loops that have setjmp. */
2164:
2165: for (insn = f; insn; insn = NEXT_INSN (insn))
2166: {
2167: if (GET_CODE (insn) == NOTE)
2168: switch (NOTE_LINE_NUMBER (insn))
2169: {
2170: case NOTE_INSN_LOOP_BEG:
2171: loop_number_loop_starts[++next_loop] = insn;
2172: loop_number_loop_ends[next_loop] = 0;
2173: loop_outer_loop[next_loop] = current_loop;
2174: loop_invalid[next_loop] = 0;
2175: loop_number_exit_labels[next_loop] = 0;
2176: current_loop = next_loop;
2177: break;
2178:
2179: case NOTE_INSN_SETJMP:
2180: /* In this case, we must invalidate our current loop and any
2181: enclosing loop. */
2182: for (loop = current_loop; loop != -1; loop = loop_outer_loop[loop])
2183: {
2184: loop_invalid[loop] = 1;
2185: if (loop_dump_stream)
2186: fprintf (loop_dump_stream,
2187: "\nLoop at %d ignored due to setjmp.\n",
2188: INSN_UID (loop_number_loop_starts[loop]));
2189: }
2190: break;
2191:
2192: case NOTE_INSN_LOOP_END:
2193: if (current_loop == -1)
2194: abort ();
2195:
2196: loop_number_loop_ends[current_loop] = insn;
2197: current_loop = loop_outer_loop[current_loop];
2198: break;
2199:
2200: }
2201:
2202: /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
2203: enclosing loop, but this doesn't matter. */
2204: uid_loop_num[INSN_UID (insn)] = current_loop;
2205: }
2206:
2207: /* Now scan all JUMP_INSN's in the function. If any branches into a loop
2208: that it is not contained within, that loop is marked invalid.
2209:
2210: Also look for blocks of code ending in an unconditional branch that
2211: exits the loop. If such a block is surrounded by a conditional
2212: branch around the block, move the block elsewhere (see below) and
2213: invert the jump to point to the code block. This may eliminate a
2214: label in our loop and will simplify processing by both us and a
2215: possible second cse pass. */
2216:
2217: for (insn = f; insn; insn = NEXT_INSN (insn))
2218: if (GET_CODE (insn) == JUMP_INSN)
2219: {
2220: int this_loop_num = uid_loop_num[INSN_UID (insn)];
2221:
2222: mark_loop_jump (PATTERN (insn), this_loop_num);
2223:
2224: /* See if this is an unconditional branch outside the loop. */
2225: if (this_loop_num != -1
2226: && (GET_CODE (PATTERN (insn)) == RETURN
2227: || (simplejump_p (insn)
2228: && (uid_loop_num[INSN_UID (JUMP_LABEL (insn))]
2229: != this_loop_num))))
2230: {
2231: rtx p;
2232: rtx our_next = next_real_insn (insn);
2233:
2234: /* Go backwards until we reach the start of the loop, a label,
2235: or a JUMP_INSN. */
2236: for (p = PREV_INSN (insn);
2237: GET_CODE (p) != CODE_LABEL
2238: && ! (GET_CODE (p) == NOTE
2239: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
2240: && GET_CODE (p) != JUMP_INSN;
2241: p = PREV_INSN (p))
2242: ;
2243:
2244: /* If we stopped on a JUMP_INSN to the next insn after INSN,
2245: we have a block of code to try to move.
2246:
2247: We look backward and then forward from the target of INSN
2248: to find a BARRIER at the same loop depth as the target.
2249: If we find such a BARRIER, we make a new label for the start
2250: of the block, invert the jump in P and point it to that label,
2251: and move the block of code to the spot we found. */
2252:
2253: if (GET_CODE (p) == JUMP_INSN
2254: && JUMP_LABEL (p) != 0
2255: && condjump_p (p)
2256: && ! simplejump_p (p)
2257: && next_real_insn (JUMP_LABEL (p)) == our_next)
2258: {
2259: rtx target
2260: = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
2261: int target_loop_num = uid_loop_num[INSN_UID (target)];
2262: rtx loc;
2263:
2264: for (loc = target; loc; loc = PREV_INSN (loc))
2265: if (GET_CODE (loc) == BARRIER
2266: && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2267: break;
2268:
2269: if (loc == 0)
2270: for (loc = target; loc; loc = NEXT_INSN (loc))
2271: if (GET_CODE (loc) == BARRIER
2272: && uid_loop_num[INSN_UID (loc)] == target_loop_num)
2273: break;
2274:
2275: if (loc)
2276: {
2277: rtx cond_label = JUMP_LABEL (p);
2278: rtx new_label = get_label_after (p);
2279:
2280: /* Ensure our label doesn't go away. */
2281: LABEL_NUSES (cond_label)++;
2282:
2283: /* Verify that uid_loop_num is large enough and that
2284: we can invert P. */
2285: if (INSN_UID (new_label) < max_uid_for_loop
2286: && invert_jump (p, new_label))
2287: {
2288: rtx q, r;
2289:
2290: /* Include the BARRIER after INSN and copy the
2291: block after LOC. */
2292: squeeze_notes (new_label, NEXT_INSN (insn));
2293: reorder_insns (new_label, NEXT_INSN (insn), loc);
2294:
2295: /* All those insns are now in TARGET_LOOP_NUM. */
2296: for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
2297: q = NEXT_INSN (q))
2298: uid_loop_num[INSN_UID (q)] = target_loop_num;
2299:
2300: /* The label jumped to by INSN is no longer a loop exit.
2301: Unless INSN does not have a label (e.g., it is a
2302: RETURN insn), search loop_number_exit_labels to find
2303: its label_ref, and remove it. Also turn off
2304: LABEL_OUTSIDE_LOOP_P bit. */
2305: if (JUMP_LABEL (insn))
2306: {
2307: for (q = 0,
2308: r = loop_number_exit_labels[this_loop_num];
2309: r; q = r, r = LABEL_NEXTREF (r))
2310: if (XEXP (r, 0) == JUMP_LABEL (insn))
2311: {
2312: LABEL_OUTSIDE_LOOP_P (r) = 0;
2313: if (q)
2314: LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
2315: else
2316: loop_number_exit_labels[this_loop_num]
2317: = LABEL_NEXTREF (r);
2318: break;
2319: }
2320:
2321: /* If we didn't find it, then something is wrong. */
2322: if (! r)
2323: abort ();
2324: }
2325:
2326: /* P is now a jump outside the loop, so it must be put
2327: in loop_number_exit_labels, and marked as such.
2328: The easiest way to do this is to just call
2329: mark_loop_jump again for P. */
2330: mark_loop_jump (PATTERN (p), this_loop_num);
2331:
2332: /* If INSN now jumps to the insn after it,
2333: delete INSN. */
2334: if (JUMP_LABEL (insn) != 0
2335: && (next_real_insn (JUMP_LABEL (insn))
2336: == next_real_insn (insn)))
2337: delete_insn (insn);
2338: }
2339:
2340: /* Continue the loop after where the conditional
2341: branch used to jump, since the only branch insn
2342: in the block (if it still remains) is an inter-loop
2343: branch and hence needs no processing. */
2344: insn = NEXT_INSN (cond_label);
2345:
2346: if (--LABEL_NUSES (cond_label) == 0)
2347: delete_insn (cond_label);
2348: }
2349: }
2350: }
2351: }
2352: }
2353:
2354: /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2355: loops it is contained in, mark the target loop invalid.
2356:
2357: For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2358:
2359: static void
2360: mark_loop_jump (x, loop_num)
2361: rtx x;
2362: int loop_num;
2363: {
2364: int dest_loop;
2365: int outer_loop;
2366: int i;
2367:
2368: switch (GET_CODE (x))
2369: {
2370: case PC:
2371: case USE:
2372: case CLOBBER:
2373: case REG:
2374: case MEM:
2375: case CONST_INT:
2376: case CONST_DOUBLE:
2377: case RETURN:
2378: return;
2379:
2380: case CONST:
2381: /* There could be a label reference in here. */
2382: mark_loop_jump (XEXP (x, 0), loop_num);
2383: return;
2384:
2385: case PLUS:
2386: case MINUS:
2387: case MULT:
2388: case LSHIFT:
2389: mark_loop_jump (XEXP (x, 0), loop_num);
2390: mark_loop_jump (XEXP (x, 1), loop_num);
2391: return;
2392:
2393: case SIGN_EXTEND:
2394: case ZERO_EXTEND:
2395: mark_loop_jump (XEXP (x, 0), loop_num);
2396: return;
2397:
2398: case LABEL_REF:
2399: dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))];
2400:
2401: /* Link together all labels that branch outside the loop. This
2402: is used by final_[bg]iv_value and the loop unrolling code. Also
2403: mark this LABEL_REF so we know that this branch should predict
2404: false. */
2405:
2406: if (dest_loop != loop_num && loop_num != -1)
2407: {
2408: LABEL_OUTSIDE_LOOP_P (x) = 1;
2409: LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
2410: loop_number_exit_labels[loop_num] = x;
2411: }
2412:
2413: /* If this is inside a loop, but not in the current loop or one enclosed
2414: by it, it invalidates at least one loop. */
2415:
2416: if (dest_loop == -1)
2417: return;
2418:
2419: /* We must invalidate every nested loop containing the target of this
2420: label, except those that also contain the jump insn. */
2421:
2422: for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
2423: {
2424: /* Stop when we reach a loop that also contains the jump insn. */
2425: for (outer_loop = loop_num; outer_loop != -1;
2426: outer_loop = loop_outer_loop[outer_loop])
2427: if (dest_loop == outer_loop)
2428: return;
2429:
2430: /* If we get here, we know we need to invalidate a loop. */
2431: if (loop_dump_stream && ! loop_invalid[dest_loop])
2432: fprintf (loop_dump_stream,
2433: "\nLoop at %d ignored due to multiple entry points.\n",
2434: INSN_UID (loop_number_loop_starts[dest_loop]));
2435:
2436: loop_invalid[dest_loop] = 1;
2437: }
2438: return;
2439:
2440: case SET:
2441: /* If this is not setting pc, ignore. */
2442: if (SET_DEST (x) == pc_rtx)
2443: mark_loop_jump (SET_SRC (x), loop_num);
2444: return;
2445:
2446: case IF_THEN_ELSE:
2447: mark_loop_jump (XEXP (x, 1), loop_num);
2448: mark_loop_jump (XEXP (x, 2), loop_num);
2449: return;
2450:
2451: case PARALLEL:
2452: case ADDR_VEC:
2453: for (i = 0; i < XVECLEN (x, 0); i++)
2454: mark_loop_jump (XVECEXP (x, 0, i), loop_num);
2455: return;
2456:
2457: case ADDR_DIFF_VEC:
2458: for (i = 0; i < XVECLEN (x, 1); i++)
2459: mark_loop_jump (XVECEXP (x, 1, i), loop_num);
2460: return;
2461:
2462: default:
2463: /* Nothing else should occur in a JUMP_INSN. */
2464: abort ();
2465: }
2466: }
2467:
2468: /* Return nonzero if there is a label in the range from
2469: insn INSN to and including the insn whose luid is END
2470: INSN must have an assigned luid (i.e., it must not have
2471: been previously created by loop.c). */
2472:
2473: static int
2474: labels_in_range_p (insn, end)
2475: rtx insn;
2476: int end;
2477: {
2478: while (insn && INSN_LUID (insn) <= end)
2479: {
2480: if (GET_CODE (insn) == CODE_LABEL)
2481: return 1;
2482: insn = NEXT_INSN (insn);
2483: }
2484:
2485: return 0;
2486: }
2487:
2488: /* Record that a memory reference X is being set. */
2489:
2490: static void
2491: note_addr_stored (x)
2492: rtx x;
2493: {
2494: register int i;
2495:
2496: if (x == 0 || GET_CODE (x) != MEM)
2497: return;
2498:
2499: /* Count number of memory writes.
2500: This affects heuristics in strength_reduce. */
2501: num_mem_sets++;
2502:
2503: if (unknown_address_altered)
2504: return;
2505:
2506: for (i = 0; i < loop_store_mems_idx; i++)
2507: if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0))
2508: && MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
2509: {
2510: /* We are storing at the same address as previously noted. Save the
2511: wider reference, treating BLKmode as wider. */
2512: if (GET_MODE (x) == BLKmode
2513: || (GET_MODE_SIZE (GET_MODE (x))
2514: > GET_MODE_SIZE (GET_MODE (loop_store_mems[i]))))
2515: loop_store_mems[i] = x;
2516: break;
2517: }
2518:
2519: if (i == NUM_STORES)
2520: unknown_address_altered = 1;
2521:
2522: else if (i == loop_store_mems_idx)
2523: loop_store_mems[loop_store_mems_idx++] = x;
2524: }
2525:
2526: /* Return nonzero if the rtx X is invariant over the current loop.
2527:
2528: The value is 2 if we refer to something only conditionally invariant.
2529:
2530: If `unknown_address_altered' is nonzero, no memory ref is invariant.
2531: Otherwise, a memory ref is invariant if it does not conflict with
2532: anything stored in `loop_store_mems'. */
2533:
2534: int
2535: invariant_p (x)
2536: register rtx x;
2537: {
2538: register int i;
2539: register enum rtx_code code;
2540: register char *fmt;
2541: int conditional = 0;
2542:
2543: if (x == 0)
2544: return 1;
2545: code = GET_CODE (x);
2546: switch (code)
2547: {
2548: case CONST_INT:
2549: case CONST_DOUBLE:
2550: case SYMBOL_REF:
2551: case CONST:
2552: return 1;
2553:
2554: case LABEL_REF:
2555: /* A LABEL_REF is normally invariant, however, if we are unrolling
2556: loops, and this label is inside the loop, then it isn't invariant.
2557: This is because each unrolled copy of the loop body will have
2558: a copy of this label. If this was invariant, then an insn loading
2559: the address of this label into a register might get moved outside
2560: the loop, and then each loop body would end up using the same label.
2561:
2562: We don't know the loop bounds here though, so just fail for all
2563: labels. */
2564: if (flag_unroll_loops)
2565: return 0;
2566: else
2567: return 1;
2568:
2569: case PC:
2570: case CC0:
2571: case UNSPEC_VOLATILE:
2572: return 0;
2573:
2574: case REG:
2575: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
2576: since the reg might be set by initialization within the loop. */
2577: if (x == frame_pointer_rtx || x == arg_pointer_rtx)
2578: return 1;
2579: if (loop_has_call
2580: && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
2581: return 0;
2582: if (n_times_set[REGNO (x)] < 0)
2583: return 2;
2584: return n_times_set[REGNO (x)] == 0;
2585:
2586: case MEM:
2587: /* Read-only items (such as constants in a constant pool) are
2588: invariant if their address is. */
2589: if (RTX_UNCHANGING_P (x))
2590: break;
2591:
2592: /* If we filled the table (or had a subroutine call), any location
2593: in memory could have been clobbered. */
2594: if (unknown_address_altered
2595: /* Don't mess with volatile memory references. */
2596: || MEM_VOLATILE_P (x))
2597: return 0;
2598:
2599: /* See if there is any dependence between a store and this load. */
2600: for (i = loop_store_mems_idx - 1; i >= 0; i--)
2601: if (true_dependence (loop_store_mems[i], x))
2602: return 0;
2603:
2604: /* It's not invalidated by a store in memory
2605: but we must still verify the address is invariant. */
2606: break;
2607:
2608: case ASM_OPERANDS:
2609: /* Don't mess with insns declared volatile. */
2610: if (MEM_VOLATILE_P (x))
2611: return 0;
2612: }
2613:
2614: fmt = GET_RTX_FORMAT (code);
2615: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2616: {
2617: if (fmt[i] == 'e')
2618: {
2619: int tem = invariant_p (XEXP (x, i));
2620: if (tem == 0)
2621: return 0;
2622: if (tem == 2)
2623: conditional = 1;
2624: }
2625: else if (fmt[i] == 'E')
2626: {
2627: register int j;
2628: for (j = 0; j < XVECLEN (x, i); j++)
2629: {
2630: int tem = invariant_p (XVECEXP (x, i, j));
2631: if (tem == 0)
2632: return 0;
2633: if (tem == 2)
2634: conditional = 1;
2635: }
2636:
2637: }
2638: }
2639:
2640: return 1 + conditional;
2641: }
2642:
2643: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
2644: which is SIZE bytes starting at BASE. */
2645:
2646: int
2647: addr_overlap_p (other, base, size)
2648: rtx other;
2649: rtx base;
2650: int size;
2651: {
2652: int start = 0, end;
2653:
2654: if (GET_CODE (base) == CONST)
2655: base = XEXP (base, 0);
2656: if (GET_CODE (base) == PLUS
2657: && GET_CODE (XEXP (base, 1)) == CONST_INT)
2658: {
2659: start = INTVAL (XEXP (base, 1));
2660: base = XEXP (base, 0);
2661: }
2662:
2663: end = start + size;
2664: return refers_to_mem_p (other, base, start, end);
2665: }
2666:
2667: /* Return nonzero if all the insns in the loop that set REG
2668: are INSN and the immediately following insns,
2669: and if each of those insns sets REG in an invariant way
2670: (not counting uses of REG in them).
2671:
2672: The value is 2 if some of these insns are only conditionally invariant.
2673:
2674: We assume that INSN itself is the first set of REG
2675: and that its source is invariant. */
2676:
2677: static int
2678: consec_sets_invariant_p (reg, n_sets, insn)
2679: int n_sets;
2680: rtx reg, insn;
2681: {
2682: register rtx p = insn;
2683: register int regno = REGNO (reg);
2684: rtx temp;
2685: /* Number of sets we have to insist on finding after INSN. */
2686: int count = n_sets - 1;
2687: int old = n_times_set[regno];
2688: int value = 0;
2689: int this;
2690:
2691: /* If N_SETS hit the limit, we can't rely on its value. */
2692: if (n_sets == 127)
2693: return 0;
2694:
2695: n_times_set[regno] = 0;
2696:
2697: while (count > 0)
2698: {
2699: register enum rtx_code code;
2700: rtx set;
2701:
2702: p = NEXT_INSN (p);
2703: code = GET_CODE (p);
2704:
2705: /* If library call, skip to end of of it. */
2706: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
2707: p = XEXP (temp, 0);
2708:
2709: this = 0;
2710: if (code == INSN
2711: && (set = single_set (p))
2712: && GET_CODE (SET_DEST (set)) == REG
2713: && REGNO (SET_DEST (set)) == regno)
2714: {
2715: this = invariant_p (SET_SRC (set));
2716: if (this != 0)
2717: value |= this;
2718: else if (temp = find_reg_note (p, REG_EQUAL, 0))
2719: {
2720: this = invariant_p (XEXP (temp, 0));
2721: if (this != 0)
2722: value |= this;
2723: }
2724: }
2725: if (this != 0)
2726: count--;
2727: else if (code != NOTE)
2728: {
2729: n_times_set[regno] = old;
2730: return 0;
2731: }
2732: }
2733:
2734: n_times_set[regno] = old;
2735: /* If invariant_p ever returned 2, we return 2. */
2736: return 1 + (value & 2);
2737: }
2738:
2739: #if 0
2740: /* I don't think this condition is sufficient to allow INSN
2741: to be moved, so we no longer test it. */
2742:
2743: /* Return 1 if all insns in the basic block of INSN and following INSN
2744: that set REG are invariant according to TABLE. */
2745:
2746: static int
2747: all_sets_invariant_p (reg, insn, table)
2748: rtx reg, insn;
2749: short *table;
2750: {
2751: register rtx p = insn;
2752: register int regno = REGNO (reg);
2753:
2754: while (1)
2755: {
2756: register enum rtx_code code;
2757: p = NEXT_INSN (p);
2758: code = GET_CODE (p);
2759: if (code == CODE_LABEL || code == JUMP_INSN)
2760: return 1;
2761: if (code == INSN && GET_CODE (PATTERN (p)) == SET
2762: && GET_CODE (SET_DEST (PATTERN (p))) == REG
2763: && REGNO (SET_DEST (PATTERN (p))) == regno)
2764: {
2765: if (!invariant_p (SET_SRC (PATTERN (p)), table))
2766: return 0;
2767: }
2768: }
2769: }
2770: #endif /* 0 */
2771:
2772: /* Look at all uses (not sets) of registers in X. For each, if it is
2773: the single use, set USAGE[REGNO] to INSN; if there was a previous use in
2774: a different insn, set USAGE[REGNO] to const0_rtx. */
2775:
2776: static void
2777: find_single_use_in_loop (insn, x, usage)
2778: rtx insn;
2779: rtx x;
2780: rtx *usage;
2781: {
2782: enum rtx_code code = GET_CODE (x);
2783: char *fmt = GET_RTX_FORMAT (code);
2784: int i, j;
2785:
2786: if (code == REG)
2787: usage[REGNO (x)]
2788: = (usage[REGNO (x)] != 0 && usage[REGNO (x)] != insn)
2789: ? const0_rtx : insn;
2790:
2791: else if (code == SET)
2792: {
2793: /* Don't count SET_DEST if it is a REG; otherwise count things
2794: in SET_DEST because if a register is partially modified, it won't
2795: show up as a potential movable so we don't care how USAGE is set
2796: for it. */
2797: if (GET_CODE (SET_DEST (x)) != REG)
2798: find_single_use_in_loop (insn, SET_DEST (x), usage);
2799: find_single_use_in_loop (insn, SET_SRC (x), usage);
2800: }
2801: else
2802: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2803: {
2804: if (fmt[i] == 'e' && XEXP (x, i) != 0)
2805: find_single_use_in_loop (insn, XEXP (x, i), usage);
2806: else if (fmt[i] == 'E')
2807: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2808: find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
2809: }
2810: }
2811:
2812: /* Increment N_TIMES_SET at the index of each register
2813: that is modified by an insn between FROM and TO.
2814: If the value of an element of N_TIMES_SET becomes 127 or more,
2815: stop incrementing it, to avoid overflow.
2816:
2817: Store in SINGLE_USAGE[I] the single insn in which register I is
2818: used, if it is only used once. Otherwise, it is set to 0 (for no
2819: uses) or const0_rtx for more than one use. This parameter may be zero,
2820: in which case this processing is not done.
2821:
2822: Store in *COUNT_PTR the number of actual instruction
2823: in the loop. We use this to decide what is worth moving out. */
2824:
2825: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
2826: In that case, it is the insn that last set reg n. */
2827:
2828: static void
2829: count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
2830: register rtx from, to;
2831: char *may_not_move;
2832: rtx *single_usage;
2833: int *count_ptr;
2834: int nregs;
2835: {
2836: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
2837: register rtx insn;
2838: register int count = 0;
2839: register rtx dest;
2840:
2841: bzero (last_set, nregs * sizeof (rtx));
2842: for (insn = from; insn != to; insn = NEXT_INSN (insn))
2843: {
2844: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2845: {
2846: ++count;
2847:
2848: /* If requested, record registers that have exactly one use. */
2849: if (single_usage)
2850: {
2851: find_single_use_in_loop (insn, PATTERN (insn), single_usage);
2852:
2853: /* Include uses in REG_EQUAL notes. */
2854: if (REG_NOTES (insn))
2855: find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
2856: }
2857:
2858: if (GET_CODE (PATTERN (insn)) == CLOBBER
2859: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
2860: /* Don't move a reg that has an explicit clobber.
2861: We might do so sometimes, but it's not worth the pain. */
2862: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
2863:
2864: if (GET_CODE (PATTERN (insn)) == SET
2865: || GET_CODE (PATTERN (insn)) == CLOBBER)
2866: {
2867: dest = SET_DEST (PATTERN (insn));
2868: while (GET_CODE (dest) == SUBREG
2869: || GET_CODE (dest) == ZERO_EXTRACT
2870: || GET_CODE (dest) == SIGN_EXTRACT
2871: || GET_CODE (dest) == STRICT_LOW_PART)
2872: dest = XEXP (dest, 0);
2873: if (GET_CODE (dest) == REG)
2874: {
2875: register int regno = REGNO (dest);
2876: /* If this is the first setting of this reg
2877: in current basic block, and it was set before,
2878: it must be set in two basic blocks, so it cannot
2879: be moved out of the loop. */
2880: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2881: may_not_move[regno] = 1;
2882: /* If this is not first setting in current basic block,
2883: see if reg was used in between previous one and this.
2884: If so, neither one can be moved. */
2885: if (last_set[regno] != 0
2886: && reg_used_between_p (dest, last_set[regno], insn))
2887: may_not_move[regno] = 1;
2888: if (n_times_set[regno] < 127)
2889: ++n_times_set[regno];
2890: last_set[regno] = insn;
2891: }
2892: }
2893: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2894: {
2895: register int i;
2896: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2897: {
2898: register rtx x = XVECEXP (PATTERN (insn), 0, i);
2899: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
2900: /* Don't move a reg that has an explicit clobber.
2901: It's not worth the pain to try to do it correctly. */
2902: may_not_move[REGNO (XEXP (x, 0))] = 1;
2903:
2904: if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
2905: {
2906: dest = SET_DEST (x);
2907: while (GET_CODE (dest) == SUBREG
2908: || GET_CODE (dest) == ZERO_EXTRACT
2909: || GET_CODE (dest) == SIGN_EXTRACT
2910: || GET_CODE (dest) == STRICT_LOW_PART)
2911: dest = XEXP (dest, 0);
2912: if (GET_CODE (dest) == REG)
2913: {
2914: register int regno = REGNO (dest);
2915: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2916: may_not_move[regno] = 1;
2917: if (last_set[regno] != 0
2918: && reg_used_between_p (dest, last_set[regno], insn))
2919: may_not_move[regno] = 1;
2920: if (n_times_set[regno] < 127)
2921: ++n_times_set[regno];
2922: last_set[regno] = insn;
2923: }
2924: }
2925: }
2926: }
2927: }
2928: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
2929: bzero (last_set, nregs * sizeof (rtx));
2930: }
2931: *count_ptr = count;
2932: }
2933:
2934: /* Given a loop that is bounded by LOOP_START and LOOP_END
2935: and that is entered at SCAN_START,
2936: return 1 if the register set in SET contained in insn INSN is used by
2937: any insn that precedes INSN in cyclic order starting
2938: from the loop entry point.
2939:
2940: We don't want to use INSN_LUID here because if we restrict INSN to those
2941: that have a valid INSN_LUID, it means we cannot move an invariant out
2942: from an inner loop past two loops. */
2943:
2944: static int
2945: loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
2946: rtx set, insn, loop_start, scan_start, loop_end;
2947: {
2948: rtx reg = SET_DEST (set);
2949: rtx p;
2950:
2951: /* Scan forward checking for register usage. If we hit INSN, we
2952: are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
2953: for (p = scan_start; p != insn; p = NEXT_INSN (p))
2954: {
2955: if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
2956: && reg_overlap_mentioned_p (reg, PATTERN (p)))
2957: return 1;
2958:
2959: if (p == loop_end)
2960: p = loop_start;
2961: }
2962:
2963: return 0;
2964: }
2965:
2966: /* A "basic induction variable" or biv is a pseudo reg that is set
2967: (within this loop) only by incrementing or decrementing it. */
2968: /* A "general induction variable" or giv is a pseudo reg whose
2969: value is a linear function of a biv. */
2970:
2971: /* Bivs are recognized by `basic_induction_var';
2972: Givs by `general_induct_var'. */
2973:
2974: /* Indexed by register number, indicates whether or not register is an
2975: induction variable, and if so what type. */
2976:
2977: enum iv_mode *reg_iv_type;
2978:
2979: /* Indexed by register number, contains pointer to `struct induction'
2980: if register is an induction variable. This holds general info for
2981: all induction variables. */
2982:
2983: struct induction **reg_iv_info;
2984:
2985: /* Indexed by register number, contains pointer to `struct iv_class'
2986: if register is a basic induction variable. This holds info describing
2987: the class (a related group) of induction variables that the biv belongs
2988: to. */
2989:
2990: struct iv_class **reg_biv_class;
2991:
2992: /* The head of a list which links together (via the next field)
2993: every iv class for the current loop. */
2994:
2995: struct iv_class *loop_iv_list;
2996:
2997: /* Communication with routines called via `note_stores'. */
2998:
2999: static rtx note_insn;
3000:
3001: /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3002:
3003: static rtx addr_placeholder;
3004:
3005: /* ??? Unfinished optimizations, and possible future optimizations,
3006: for the strength reduction code. */
3007:
3008: /* ??? There is one more optimization you might be interested in doing: to
3009: allocate pseudo registers for frequently-accessed memory locations.
3010: If the same memory location is referenced each time around, it might
3011: be possible to copy it into a register before and out after.
3012: This is especially useful when the memory location is a variable which
3013: is in a stack slot because somewhere its address is taken. If the
3014: loop doesn't contain a function call and the variable isn't volatile,
3015: it is safe to keep the value in a register for the duration of the
3016: loop. One tricky thing is that the copying of the value back from the
3017: register has to be done on all exits from the loop. You need to check that
3018: all the exits from the loop go to the same place. */
3019:
3020: /* ??? The interaction of biv elimination, and recognition of 'constant'
3021: bivs, may cause problems. */
3022:
3023: /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3024: performance problems.
3025:
3026: Perhaps don't eliminate things that can be combined with an addressing
3027: mode. Find all givs that have the same biv, mult_val, and add_val;
3028: then for each giv, check to see if its only use dies in a following
3029: memory address. If so, generate a new memory address and check to see
3030: if it is valid. If it is valid, then store the modified memory address,
3031: otherwise, mark the giv as not done so that it will get its own iv. */
3032:
3033: /* ??? Could try to optimize branches when it is known that a biv is always
3034: positive. */
3035:
3036: /* ??? When replace a biv in a compare insn, we should replace with closest
3037: giv so that an optimized branch can still be recognized by the combiner,
3038: e.g. the VAX acb insn. */
3039:
3040: /* ??? Many of the checks involving uid_luid could be simplified if regscan
3041: was rerun in loop_optimize whenever a register was added or moved.
3042: Also, some of the optimizations could be a little less conservative. */
3043:
3044: /* Perform strength reduction and induction variable elimination. */
3045:
3046: /* Pseudo registers created during this function will be beyond the last
3047: valid index in several tables including n_times_set and regno_last_uid.
3048: This does not cause a problem here, because the added registers cannot be
3049: givs outside of their loop, and hence will never be reconsidered.
3050: But scan_loop must check regnos to make sure they are in bounds. */
3051:
3052: static void
3053: strength_reduce (scan_start, end, loop_top, insn_count,
3054: loop_start, loop_end)
3055: rtx scan_start;
3056: rtx end;
3057: rtx loop_top;
3058: int insn_count;
3059: rtx loop_start;
3060: rtx loop_end;
3061: {
3062: rtx p;
3063: rtx set;
3064: rtx inc_val;
3065: rtx mult_val;
3066: rtx dest_reg;
3067: /* This is 1 if current insn is not executed at least once for every loop
3068: iteration. */
3069: int not_every_iteration = 0;
3070: /* Temporary list pointers for traversing loop_iv_list. */
3071: struct iv_class *bl, **backbl;
3072: /* Ratio of extra register life span we can justify
3073: for saving an instruction. More if loop doesn't call subroutines
3074: since in that case saving an insn makes more difference
3075: and more registers are available. */
3076: /* ??? could set this to last value of threshold in move_movables */
3077: int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3078: /* Map of pseudo-register replacements. */
3079: rtx *reg_map;
3080: int call_seen;
3081: rtx test;
3082: rtx end_insert_before;
3083:
3084: reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop
3085: * sizeof (enum iv_mode *));
3086: bzero ((char *) reg_iv_type, max_reg_before_loop * sizeof (enum iv_mode *));
3087: reg_iv_info = (struct induction **)
3088: alloca (max_reg_before_loop * sizeof (struct induction *));
3089: bzero ((char *) reg_iv_info, (max_reg_before_loop
3090: * sizeof (struct induction *)));
3091: reg_biv_class = (struct iv_class **)
3092: alloca (max_reg_before_loop * sizeof (struct iv_class *));
3093: bzero ((char *) reg_biv_class, (max_reg_before_loop
3094: * sizeof (struct iv_class *)));
3095:
3096: loop_iv_list = 0;
3097: addr_placeholder = gen_reg_rtx (Pmode);
3098:
3099: /* Save insn immediately after the loop_end. Insns inserted after loop_end
3100: must be put before this insn, so that they will appear in the right
3101: order (i.e. loop order). */
3102:
3103: end_insert_before = NEXT_INSN (loop_end);
3104:
3105: /* Scan through loop to find all possible bivs. */
3106:
3107: p = scan_start;
3108: while (1)
3109: {
3110: p = NEXT_INSN (p);
3111: /* At end of a straight-in loop, we are done.
3112: At end of a loop entered at the bottom, scan the top. */
3113: if (p == scan_start)
3114: break;
3115: if (p == end)
3116: {
3117: if (loop_top != 0)
3118: p = NEXT_INSN (loop_top);
3119: else
3120: break;
3121: if (p == scan_start)
3122: break;
3123: }
3124:
3125: if (GET_CODE (p) == INSN
3126: && (set = single_set (p))
3127: && GET_CODE (SET_DEST (set)) == REG)
3128: {
3129: dest_reg = SET_DEST (set);
3130: if (REGNO (dest_reg) < max_reg_before_loop
3131: && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
3132: && reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT)
3133: {
3134: if (basic_induction_var (SET_SRC (set), dest_reg,
3135: &inc_val, &mult_val))
3136: {
3137: /* It is a possible basic induction variable.
3138: Create and initialize an induction structure for it. */
3139:
3140: struct induction *v
3141: = (struct induction *) alloca (sizeof (struct induction));
3142:
3143: record_biv (v, p, dest_reg, inc_val, mult_val,
3144: not_every_iteration);
3145: reg_iv_type[REGNO (dest_reg)] = BASIC_INDUCT;
3146: }
3147: else if (REGNO (dest_reg) < max_reg_before_loop)
3148: reg_iv_type[REGNO (dest_reg)] = NOT_BASIC_INDUCT;
3149: }
3150: }
3151:
3152: /* Past a label or a jump, we get to insns for which we can't count
3153: on whether or how many times they will be executed during each
3154: iteration. */
3155: /* This code appears in three places, once in scan_loop, and twice
3156: in strength_reduce. */
3157: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3158: /* If we enter the loop in the middle, and scan around to the
3159: beginning, don't set not_every_iteration for that.
3160: This can be any kind of jump, since we want to know if insns
3161: will be executed if the loop is executed. */
3162: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3163: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3164: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3165: not_every_iteration = 1;
3166:
3167: /* At the virtual top of a converted loop, insns are again known to
3168: be executed each iteration: logically, the loop begins here
3169: even though the exit code has been duplicated. */
3170:
3171: else if (GET_CODE (p) == NOTE
3172: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3173: not_every_iteration = 0;
3174:
3175: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3176: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3177: or not an insn is known to be executed each iteration of the
3178: loop, whether or not any iterations are known to occur.
3179:
3180: Therefore, if we have just passed a label and have no more labels
3181: between here and the test insn of the loop, we know these insns
3182: will be executed each iteration. This can also happen if we
3183: have just passed a jump, for example, when there are nested loops. */
3184:
3185: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3186: && no_labels_between_p (p, loop_end))
3187: not_every_iteration = 0;
3188: }
3189:
3190: /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3191: Make a sanity check against n_times_set. */
3192: for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next)
3193: {
3194: if (reg_iv_type[bl->regno] != BASIC_INDUCT
3195: /* Above happens if register modified by subreg, etc. */
3196: /* Make sure it is not recognized as a basic induction var: */
3197: || n_times_set[bl->regno] != bl->biv_count
3198: /* If never incremented, it is invariant that we decided not to
3199: move. So leave it alone. */
3200: || ! bl->incremented)
3201: {
3202: if (loop_dump_stream)
3203: fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3204: bl->regno,
3205: (reg_iv_type[bl->regno] != BASIC_INDUCT
3206: ? "not induction variable"
3207: : (! bl->incremented ? "never incremented"
3208: : "count error")));
3209:
3210: reg_iv_type[bl->regno] = NOT_BASIC_INDUCT;
3211: *backbl = bl->next;
3212: }
3213: else
3214: {
3215: backbl = &bl->next;
3216:
3217: if (loop_dump_stream)
3218: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3219: }
3220: }
3221:
3222: /* Exit if there are no bivs. */
3223: if (! loop_iv_list)
3224: {
3225: /* Can still unroll the loop anyways, but indicate that there is no
3226: strength reduction info available. */
3227: if (flag_unroll_loops)
3228: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 0);
3229:
3230: return;
3231: }
3232:
3233: /* Find initial value for each biv by searching backwards from loop_start,
3234: halting at first label. Also record any test condition. */
3235:
3236: call_seen = 0;
3237: for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3238: {
3239: note_insn = p;
3240:
3241: if (GET_CODE (p) == CALL_INSN)
3242: call_seen = 1;
3243:
3244: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3245: || GET_CODE (p) == CALL_INSN)
3246: note_stores (PATTERN (p), record_initial);
3247:
3248: /* Record any test of a biv that branches around the loop if no store
3249: between it and the start of loop. We only care about tests with
3250: constants and registers and only certain of those. */
3251: if (GET_CODE (p) == JUMP_INSN
3252: && JUMP_LABEL (p) != 0
3253: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3254: && (test = get_condition_for_loop (p)) != 0
3255: && GET_CODE (XEXP (test, 0)) == REG
3256: && REGNO (XEXP (test, 0)) < max_reg_before_loop
3257: && (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3258: && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3259: && bl->init_insn == 0)
3260: {
3261: /* If an NE test, we have an initial value! */
3262: if (GET_CODE (test) == NE)
3263: {
3264: bl->init_insn = p;
3265: bl->init_set = gen_rtx (SET, VOIDmode,
3266: XEXP (test, 0), XEXP (test, 1));
3267: }
3268: else
3269: bl->initial_test = test;
3270: }
3271: }
3272:
3273: /* Look at the each biv and see if we can say anything better about its
3274: initial value from any initializing insns set up above. (This is done
3275: in two passes to avoid missing SETs in a PARALLEL.) */
3276: for (bl = loop_iv_list; bl; bl = bl->next)
3277: {
3278: rtx src;
3279:
3280: if (! bl->init_insn)
3281: continue;
3282:
3283: src = SET_SRC (bl->init_set);
3284:
3285: if (loop_dump_stream)
3286: fprintf (loop_dump_stream,
3287: "Biv %d initialized at insn %d: initial value ",
3288: bl->regno, INSN_UID (bl->init_insn));
3289:
3290: if (valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3291: {
3292: bl->initial_value = src;
3293:
3294: if (loop_dump_stream)
3295: {
3296: if (GET_CODE (src) == CONST_INT)
3297: fprintf (loop_dump_stream, "%d\n", INTVAL (src));
3298: else
3299: {
3300: print_rtl (loop_dump_stream, src);
3301: fprintf (loop_dump_stream, "\n");
3302: }
3303: }
3304: }
3305: else
3306: {
3307: /* Biv initial value is not simple move,
1.1.1.2 ! root 3308: so let it keep initial value of "itself". */
1.1 root 3309:
3310: if (loop_dump_stream)
3311: fprintf (loop_dump_stream, "is complex\n");
3312: }
3313: }
3314:
3315: /* Search the loop for general induction variables. */
3316:
3317: /* A register is a giv if: it is only set once, it is a function of a
3318: biv and a constant (or invariant), and it is not a biv. */
3319:
3320: not_every_iteration = 0;
3321: p = scan_start;
3322: while (1)
3323: {
3324: p = NEXT_INSN (p);
3325: /* At end of a straight-in loop, we are done.
3326: At end of a loop entered at the bottom, scan the top. */
3327: if (p == scan_start)
3328: break;
3329: if (p == end)
3330: {
3331: if (loop_top != 0)
3332: p = NEXT_INSN (loop_top);
3333: else
3334: break;
3335: if (p == scan_start)
3336: break;
3337: }
3338:
3339: /* Look for a general induction variable in a register. */
3340: if (GET_CODE (p) == INSN
3341: && (set = single_set (p))
3342: && GET_CODE (SET_DEST (set)) == REG
3343: && ! may_not_optimize[REGNO (SET_DEST (set))])
3344: {
3345: rtx src_reg;
3346: rtx add_val;
3347: rtx mult_val;
3348: int benefit;
3349: rtx regnote = 0;
3350:
3351: dest_reg = SET_DEST (set);
3352: if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
3353: continue;
3354:
3355: if (/* SET_SRC is a giv. */
3356: ((benefit = general_induction_var (SET_SRC (set),
3357: &src_reg, &add_val,
3358: &mult_val))
3359: /* Equivalent expression is a giv. */
3360: || ((regnote = find_reg_note (p, REG_EQUAL, 0))
3361: && (benefit = general_induction_var (XEXP (regnote, 0),
3362: &src_reg,
3363: &add_val, &mult_val))))
3364: /* Don't try to handle any regs made by loop optimization.
3365: We have nothing on them in regno_first_uid, etc. */
3366: && REGNO (dest_reg) < max_reg_before_loop
3367: /* Don't recognize a BASIC_INDUCT_VAR here. */
3368: && dest_reg != src_reg
3369: /* This must be the only place where the register is set. */
3370: && (n_times_set[REGNO (dest_reg)] == 1
3371: /* or all sets must be consecutive and make a giv. */
3372: || (benefit = consec_sets_giv (benefit, p,
3373: src_reg, dest_reg,
3374: &add_val, &mult_val))))
3375: {
3376: int count;
3377: struct induction *v
3378: = (struct induction *) alloca (sizeof (struct induction));
3379: rtx temp;
3380:
3381: /* If this is a library call, increase benefit. */
3382: if (find_reg_note (p, REG_RETVAL, 0))
3383: benefit += libcall_benefit (p);
3384:
3385: /* Skip the consecutive insns, if there are any. */
3386: for (count = n_times_set[REGNO (dest_reg)] - 1;
3387: count > 0; count--)
3388: {
3389: /* If first insn of libcall sequence, skip to end.
3390: Do this at start of loop, since INSN is guaranteed to
3391: be an insn here. */
3392: if (GET_CODE (p) != NOTE
3393: && (temp = find_reg_note (p, REG_LIBCALL, 0)))
3394: p = XEXP (temp, 0);
3395:
3396: do p = NEXT_INSN (p);
3397: while (GET_CODE (p) == NOTE);
3398: }
3399:
3400: record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
3401: DEST_REG, not_every_iteration, 0, loop_start,
3402: loop_end);
3403:
3404: }
3405: }
3406:
3407: #ifndef DONT_REDUCE_ADDR
3408: /* Look for givs which are memory addresses. */
3409: /* This resulted in worse code on a VAX 8600. I wonder if it
3410: still does. */
3411: if (GET_CODE (p) == INSN)
3412: find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
3413: loop_end);
3414: #endif
3415:
3416: /* Update the status of whether giv can derive other givs. This can
3417: change when we pass a label or an insn that updates a biv. */
3418: if (GET_CODE (p) == INSN || GET_CODE (p) == CODE_LABEL)
3419: update_giv_derive (p);
3420:
3421: /* Past a label or a jump, we get to insns for which we can't count
3422: on whether or how many times they will be executed during each
3423: iteration. */
3424: /* This code appears in three places, once in scan_loop, and twice
3425: in strength_reduce. */
3426: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3427: /* If we enter the loop in the middle, and scan around
3428: to the beginning, don't set not_every_iteration for that.
3429: This can be any kind of jump, since we want to know if insns
3430: will be executed if the loop is executed. */
3431: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3432: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3433: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3434: not_every_iteration = 1;
3435:
3436: /* At the virtual top of a converted loop, insns are again known to
3437: be executed each iteration: logically, the loop begins here
3438: even though the exit code has been duplicated. */
3439:
3440: else if (GET_CODE (p) == NOTE
3441: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3442: not_every_iteration = 0;
3443:
3444: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3445: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3446: or not an insn is known to be executed each iteration of the
3447: loop, whether or not any iterations are known to occur.
3448:
3449: Therefore, if we have just passed a label and have no more labels
3450: between here and the test insn of the loop, we know these insns
3451: will be executed each iteration. */
3452:
3453: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3454: && no_labels_between_p (p, loop_end))
3455: not_every_iteration = 0;
3456: }
3457:
3458: /* Try to calculate and save the number of loop iterations. This is
3459: set to zero if the actual number can not be calculated. This must
3460: be called after all giv's have been identified, since otherwise it may
3461: fail if the iteration variable is a giv. */
3462:
3463: loop_n_iterations = loop_iterations (loop_start, loop_end);
3464:
3465: /* Now for each giv for which we still don't know whether or not it is
3466: replaceable, check to see if it is replaceable because its final value
3467: can be calculated. This must be done after loop_iterations is called,
3468: so that final_giv_value will work correctly. */
3469:
3470: for (bl = loop_iv_list; bl; bl = bl->next)
3471: {
3472: struct induction *v;
3473:
3474: for (v = bl->giv; v; v = v->next_iv)
3475: if (! v->replaceable && ! v->not_replaceable)
3476: check_final_value (v, loop_start, loop_end);
3477: }
3478:
3479: /* Try to prove that the loop counter variable (if any) is always
3480: nonnegative; if so, record that fact with a REG_NONNEG note
3481: so that "decrement and branch until zero" insn can be used. */
3482: check_dbra_loop (loop_end, insn_count, loop_start);
3483:
3484: /* Create reg_map to hold substitutions for replaceable giv regs. */
3485: reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
3486: bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
3487:
3488: /* Examine each iv class for feasibility of strength reduction/induction
3489: variable elimination. */
3490:
3491: for (bl = loop_iv_list; bl; bl = bl->next)
3492: {
3493: struct induction *v;
3494: int benefit;
3495: int all_reduced;
3496: rtx final_value = 0;
3497:
3498: /* Test whether it will be possible to eliminate this biv
3499: provided all givs are reduced. This is possible if either
3500: the reg is not used outside the loop, or we can compute
3501: what its final value will be.
3502:
3503: For architectures with a decrement_and_branch_until_zero insn,
3504: don't do this if we put a REG_NONNEG note on the endtest for
3505: this biv. */
3506:
3507: /* Compare against bl->init_insn rather than loop_start.
3508: We aren't concerned with any uses of the biv between
3509: init_insn and loop_start since these won't be affected
3510: by the value of the biv elsewhere in the function, so
3511: long as init_insn doesn't use the biv itself.
3512: March 14, 1989 -- [email protected] */
3513:
3514: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
3515: && bl->init_insn
3516: && INSN_UID (bl->init_insn) < max_uid_for_loop
3517: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
3518: #ifdef HAVE_decrement_and_branch_until_zero
3519: && ! bl->nonneg
3520: #endif
3521: && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3522: || ((final_value = final_biv_value (bl, loop_start, loop_end))
3523: #ifdef HAVE_decrement_and_branch_until_zero
3524: && ! bl->nonneg
3525: #endif
3526: ))
3527: bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
3528: threshold, insn_count);
3529: else
3530: {
3531: if (loop_dump_stream)
3532: {
3533: fprintf (loop_dump_stream,
3534: "Cannot eliminate biv %d.\n",
3535: bl->regno);
3536: fprintf (loop_dump_stream,
3537: "First use: insn %d, last use: insn %d.\n",
3538: regno_first_uid[bl->regno],
3539: regno_last_uid[bl->regno]);
3540: }
3541: }
3542:
3543: /* Combine all giv's for this iv_class. */
3544: combine_givs (bl);
3545:
3546: /* This will be true at the end, if all givs which depend on this
3547: biv have been strength reduced.
3548: We can't (currently) eliminate the biv unless this is so. */
3549: all_reduced = 1;
3550:
3551: /* Check each giv in this class to see if we will benefit by reducing
3552: it. Skip giv's combined with others. */
3553: for (v = bl->giv; v; v = v->next_iv)
3554: {
3555: struct induction *tv;
3556:
3557: if (v->ignore || v->same)
3558: continue;
3559:
3560: benefit = v->benefit;
3561:
3562: /* Reduce benefit if not replaceable, since we will insert
3563: a move-insn to replace the insn that calculates this giv.
3564: Don't do this unless the giv is a user variable, since it
3565: will often be marked non-replaceable because of the duplication
3566: of the exit code outside the loop. In such a case, the copies
3567: we insert are dead and will be deleted. So they don't have
3568: a cost. Similar situations exist. */
3569: /* ??? The new final_[bg]iv_value code does a much better job
3570: of finding replaceable giv's, and hence this code may no longer
3571: be necessary. */
3572: if (! v->replaceable && ! bl->eliminable
3573: && REG_USERVAR_P (v->dest_reg))
3574: benefit -= copy_cost;
3575:
3576: /* Decrease the benefit to count the add-insns that we will
3577: insert to increment the reduced reg for the giv. */
3578: benefit -= add_cost * bl->biv_count;
3579:
3580: /* Decide whether to strength-reduce this giv or to leave the code
3581: unchanged (recompute it from the biv each time it is used).
3582: This decision can be made independently for each giv. */
3583:
3584: /* ??? Perhaps attempt to guess whether autoincrement will handle
3585: some of the new add insns; if so, can increase BENEFIT
3586: (undo the subtraction of add_cost that was done above). */
3587:
3588: /* If an insn is not to be strength reduced, then set its ignore
3589: flag, and clear all_reduced. */
3590:
3591: if (v->lifetime * threshold * benefit < insn_count)
3592: {
3593: if (loop_dump_stream)
3594: fprintf (loop_dump_stream,
3595: "giv of insn %d not worth while, %d vs %d.\n",
3596: INSN_UID (v->insn),
3597: v->lifetime * threshold * benefit, insn_count);
3598: v->ignore = 1;
3599: all_reduced = 0;
3600: }
3601: else
3602: {
3603: /* Check that we can increment the reduced giv without a
3604: multiply insn. If not, reject it. */
3605:
3606: for (tv = bl->biv; tv; tv = tv->next_iv)
3607: if (tv->mult_val == const1_rtx
3608: && ! product_cheap_p (tv->add_val, v->mult_val))
3609: {
3610: if (loop_dump_stream)
3611: fprintf (loop_dump_stream,
3612: "giv of insn %d: would need a multiply.\n",
3613: INSN_UID (v->insn));
3614: v->ignore = 1;
3615: all_reduced = 0;
3616: break;
3617: }
3618: }
3619: }
3620:
3621: /* Reduce each giv that we decided to reduce. */
3622:
3623: for (v = bl->giv; v; v = v->next_iv)
3624: {
3625: struct induction *tv;
3626: if (! v->ignore && v->same == 0)
3627: {
3628: v->new_reg = gen_reg_rtx (v->mode);
3629:
3630: /* For each place where the biv is incremented,
3631: add an insn to increment the new, reduced reg for the giv. */
3632: for (tv = bl->biv; tv; tv = tv->next_iv)
3633: {
3634: if (tv->mult_val == const1_rtx)
3635: emit_iv_add_mult (tv->add_val, v->mult_val,
3636: v->new_reg, v->new_reg, tv->insn);
3637: else /* tv->mult_val == const0_rtx */
3638: /* A multiply is acceptable here
3639: since this is presumed to be seldom executed. */
3640: emit_iv_add_mult (tv->add_val, v->mult_val,
3641: v->add_val, v->new_reg, tv->insn);
3642: }
3643:
3644: /* Add code at loop start to initialize giv's reduced reg. */
3645:
3646: emit_iv_add_mult (bl->initial_value, v->mult_val,
3647: v->add_val, v->new_reg, loop_start);
3648: }
3649: }
3650:
3651: /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
3652: as not reduced.
3653:
3654: For each giv register that can be reduced now: if replaceable,
3655: substitute reduced reg wherever the old giv occurs;
3656: else add new move insn "giv_reg = reduced_reg".
3657:
3658: Also check for givs whose first use is their definition and whose
3659: last use is the definition of another giv. If so, it is likely
3660: dead and should not be used to eliminate a biv. */
3661: for (v = bl->giv; v; v = v->next_iv)
3662: {
3663: if (v->same && v->same->ignore)
3664: v->ignore = 1;
3665:
3666: if (v->ignore)
3667: continue;
3668:
3669: if (v->giv_type == DEST_REG
3670: && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn))
3671: {
3672: struct induction *v1;
3673:
3674: for (v1 = bl->giv; v1; v1 = v1->next_iv)
3675: if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn))
3676: v->maybe_dead = 1;
3677: }
3678:
3679: /* Update expression if this was combined, in case other giv was
3680: replaced. */
3681: if (v->same)
3682: v->new_reg = replace_rtx (v->new_reg,
3683: v->same->dest_reg, v->same->new_reg);
3684:
3685: if (v->giv_type == DEST_ADDR)
3686: /* Store reduced reg as the address in the memref where we found
3687: this giv. */
3688: *v->location = v->new_reg;
3689: else if (v->replaceable)
3690: {
3691: reg_map[REGNO (v->dest_reg)] = v->new_reg;
3692:
3693: #if 0
3694: /* I can no longer duplicate the original problem. Perhaps
3695: this is unnecessary now? */
3696:
3697: /* Replaceable; it isn't strictly necessary to delete the old
3698: insn and emit a new one, because v->dest_reg is now dead.
3699:
3700: However, especially when unrolling loops, the special
3701: handling for (set REG0 REG1) in the second cse pass may
3702: make v->dest_reg live again. To avoid this problem, emit
3703: an insn to set the original giv reg from the reduced giv.
3704: We can not delete the original insn, since it may be part
3705: of a LIBCALL, and the code in flow that eliminates dead
3706: libcalls will fail if it is deleted. */
3707: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3708: v->insn);
3709: #endif
3710: }
3711: else
3712: {
3713: /* Not replaceable; emit an insn to set the original giv reg from
3714: the reduced giv, same as above. */
3715: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3716: v->insn);
3717: }
3718:
3719: /* When a loop is reversed, givs which depend on the reversed
3720: biv, and which are live outside the loop, must be set to their
3721: correct final value. This insn is only needed if the giv is
3722: not replaceable. The correct final value is the same as the
3723: value that the giv starts the reversed loop with. */
3724: if (bl->reversed && ! v->replaceable)
3725: emit_iv_add_mult (bl->initial_value, v->mult_val,
3726: v->add_val, v->dest_reg, end_insert_before);
3727: else if (v->final_value)
3728: {
3729: rtx insert_before;
3730:
3731: /* If the loop has multiple exits, emit the insn before the
3732: loop to ensure that it will always be executed no matter
3733: how the loop exits. Otherwise, emit the insn after the loop,
3734: since this is slightly more efficient. */
3735: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3736: insert_before = loop_start;
3737: else
3738: insert_before = end_insert_before;
3739: emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
3740: insert_before);
3741:
3742: #if 0
3743: /* If the insn to set the final value of the giv was emitted
3744: before the loop, then we must delete the insn inside the loop
3745: that sets it. If this is a LIBCALL, then we must delete
3746: every insn in the libcall. Note, however, that
3747: final_giv_value will only succeed when there are multiple
3748: exits if the giv is dead at each exit, hence it does not
3749: matter that the original insn remains because it is dead
3750: anyways. */
3751: /* Delete the insn inside the loop that sets the giv since
3752: the giv is now set before (or after) the loop. */
3753: delete_insn (v->insn);
3754: #endif
3755: }
3756:
3757: if (loop_dump_stream)
3758: {
3759: fprintf (loop_dump_stream, "giv at %d reduced to ",
3760: INSN_UID (v->insn));
3761: print_rtl (loop_dump_stream, v->new_reg);
3762: fprintf (loop_dump_stream, "\n");
3763: }
3764: }
3765:
3766: /* All the givs based on the biv bl have been reduced if they
3767: merit it. */
3768:
3769: /* For each giv not marked as maybe dead that has been combined with a
3770: second giv, clear any "maybe dead" mark on that second giv.
3771: v->new_reg will either be or refer to the register of the giv it
3772: combined with.
3773:
3774: Doing this clearing avoids problems in biv elimination where a
3775: giv's new_reg is a complex value that can't be put in the insn but
3776: the giv combined with (with a reg as new_reg) is marked maybe_dead.
3777: Since the register will be used in either case, we'd prefer it be
3778: used from the simpler giv. */
3779:
3780: for (v = bl->giv; v; v = v->next_iv)
3781: if (! v->maybe_dead && v->same)
3782: v->same->maybe_dead = 0;
3783:
3784: /* Try to eliminate the biv, if it is a candidate.
3785: This won't work if ! all_reduced,
3786: since the givs we planned to use might not have been reduced.
3787:
1.1.1.2 ! root 3788: We have to be careful that we didn't initially think we could eliminate
1.1 root 3789: this biv because of a giv that we now think may be dead and shouldn't
3790: be used as a biv replacement.
3791:
3792: Also, there is the possibility that we may have a giv that looks
3793: like it can be used to eliminate a biv, but the resulting insn
3794: isn't valid. This can happen, for example, on the 88k, where a
3795: JUMP_INSN can compare a register only with zero. Attempts to
3796: replace it with a comapare with a constant will fail.
3797:
3798: Note that in cases where this call fails, we may have replaced some
3799: of the occurrences of the biv with a giv, but no harm was done in
3800: doing so in the rare cases where it can occur. */
3801:
3802: if (all_reduced == 1 && bl->eliminable
3803: && maybe_eliminate_biv (bl, loop_start, end, 1,
3804: threshold, insn_count))
3805:
3806: {
3807: /* ?? If we created a new test to bypass the loop entirely,
3808: or otherwise drop straight in, based on this test, then
3809: we might want to rewrite it also. This way some later
3810: pass has more hope of removing the initialization of this
3811: biv entirely. */
3812:
3813: /* If final_value != 0, then the biv may be used after loop end
3814: and we must emit an insn to set it just in case.
3815:
3816: Reversed bivs already have an insn after the loop setting their
3817: value, so we don't need another one. We can't calculate the
3818: proper final value for such a biv here anyways. */
3819: if (final_value != 0 && ! bl->reversed)
3820: {
3821: rtx insert_before;
3822:
3823: /* If the loop has multiple exits, emit the insn before the
3824: loop to ensure that it will always be executed no matter
3825: how the loop exits. Otherwise, emit the insn after the
3826: loop, since this is slightly more efficient. */
3827: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3828: insert_before = loop_start;
3829: else
3830: insert_before = end_insert_before;
3831:
3832: emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
3833: end_insert_before);
3834: }
3835:
3836: #if 0
3837: /* Delete all of the instructions inside the loop which set
3838: the biv, as they are all dead. If is safe to delete them,
3839: because an insn setting a biv will never be part of a libcall. */
3840: /* However, deleting them will invalidate the regno_last_uid info,
3841: so keeping them around is more convenient. Final_biv_value
3842: will only succeed when there are multiple exits if the biv
3843: is dead at each exit, hence it does not matter that the original
3844: insn remains, because it is dead anyways. */
3845: for (v = bl->biv; v; v = v->next_iv)
3846: delete_insn (v->insn);
3847: #endif
3848:
3849: if (loop_dump_stream)
3850: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
3851: bl->regno);
3852: }
3853: }
3854:
3855: /* Go through all the instructions in the loop, making all the
3856: register substitutions scheduled in REG_MAP. */
3857:
3858: for (p = loop_start; p != end; p = NEXT_INSN (p))
3859: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3860: || GET_CODE (p) == CALL_INSN)
3861: {
3862: replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0);
3863: replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0);
3864: }
3865:
3866: /* Unroll loops from within strength reduction so that we can use the
3867: induction variable information that strength_reduce has already
3868: collected. */
3869:
3870: if (flag_unroll_loops)
3871: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
3872:
3873: if (loop_dump_stream)
3874: fprintf (loop_dump_stream, "\n");
3875: }
3876:
3877: /* Return 1 if X is a valid source for an initial value (or as value being
3878: compared against in an initial test).
3879:
3880: X must be either a register or constant and must not be clobbered between
3881: the current insn and the start of the loop.
3882:
3883: INSN is the insn containing X. */
3884:
3885: static int
3886: valid_initial_value_p (x, insn, call_seen, loop_start)
3887: rtx x;
3888: rtx insn;
3889: int call_seen;
3890: rtx loop_start;
3891: {
3892: if (CONSTANT_P (x))
3893: return 1;
3894:
1.1.1.2 ! root 3895: /* Only consider pseudos we know about initialized in insns whose luids
1.1 root 3896: we know. */
3897: if (GET_CODE (x) != REG
3898: || REGNO (x) >= max_reg_before_loop)
3899: return 0;
3900:
3901: /* Don't use call-clobbered registers across a call which clobbers it. On
3902: some machines, don't use any hard registers at all. */
3903: if (REGNO (x) < FIRST_PSEUDO_REGISTER
3904: #ifndef SMALL_REGISTER_CLASSES
3905: && call_used_regs[REGNO (x)] && call_seen
3906: #endif
3907: )
3908: return 0;
3909:
3910: /* Don't use registers that have been clobbered before the start of the
3911: loop. */
3912: if (reg_set_between_p (x, insn, loop_start))
3913: return 0;
3914:
3915: return 1;
3916: }
3917:
3918: /* Scan X for memory refs and check each memory address
3919: as a possible giv. INSN is the insn whose pattern X comes from.
3920: NOT_EVERY_ITERATION is 1 if the insn might not be executed during
3921: every loop iteration. */
3922:
3923: static void
3924: find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
3925: rtx x;
3926: rtx insn;
3927: int not_every_iteration;
3928: rtx loop_start, loop_end;
3929: {
3930: register int i, j;
3931: register enum rtx_code code;
3932: register char *fmt;
3933:
3934: if (x == 0)
3935: return;
3936:
3937: code = GET_CODE (x);
3938: switch (code)
3939: {
3940: case REG:
3941: case CONST_INT:
3942: case CONST:
3943: case CONST_DOUBLE:
3944: case SYMBOL_REF:
3945: case LABEL_REF:
3946: case PC:
3947: case CC0:
3948: case ADDR_VEC:
3949: case ADDR_DIFF_VEC:
3950: case USE:
3951: case CLOBBER:
3952: return;
3953:
3954: case MEM:
3955: {
3956: rtx src_reg;
3957: rtx add_val;
3958: rtx mult_val;
3959: int benefit;
3960:
3961: benefit = general_induction_var (XEXP (x, 0),
3962: &src_reg, &add_val, &mult_val);
3963:
3964: /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0.
3965: Such a giv isn't useful. */
3966: if (benefit > 0 && (mult_val != const1_rtx || add_val != const0_rtx))
3967: {
3968: /* Found one; record it. */
3969: struct induction *v
3970: = (struct induction *) oballoc (sizeof (struct induction));
3971:
3972: record_giv (v, insn, src_reg, addr_placeholder, mult_val,
3973: add_val, benefit, DEST_ADDR, not_every_iteration,
3974: &XEXP (x, 0), loop_start, loop_end);
3975:
3976: v->mem_mode = GET_MODE (x);
3977: }
3978: return;
3979: }
3980: }
3981:
3982: /* Recursively scan the subexpressions for other mem refs. */
3983:
3984: fmt = GET_RTX_FORMAT (code);
3985: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3986: if (fmt[i] == 'e')
3987: find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
3988: loop_end);
3989: else if (fmt[i] == 'E')
3990: for (j = 0; j < XVECLEN (x, i); j++)
3991: find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
3992: loop_start, loop_end);
3993: }
3994:
3995: /* Fill in the data about one biv update.
3996: V is the `struct induction' in which we record the biv. (It is
3997: allocated by the caller, with alloca.)
3998: INSN is the insn that sets it.
3999: DEST_REG is the biv's reg.
4000:
4001: MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4002: INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
4003: being set to INC_VAL. */
4004:
4005: static void
4006: record_biv (v, insn, dest_reg, inc_val, mult_val, not_every_iteration)
4007: struct induction *v;
4008: rtx insn;
4009: rtx dest_reg;
4010: rtx inc_val;
4011: rtx mult_val;
4012: int not_every_iteration;
4013: {
4014: struct iv_class *bl;
4015:
4016: v->insn = insn;
4017: v->src_reg = dest_reg;
4018: v->dest_reg = dest_reg;
4019: v->mult_val = mult_val;
4020: v->add_val = inc_val;
4021: v->mode = GET_MODE (dest_reg);
4022: v->always_computable = ! not_every_iteration;
4023:
4024: /* Add this to the reg's iv_class, creating a class
4025: if this is the first incrementation of the reg. */
4026:
4027: bl = reg_biv_class[REGNO (dest_reg)];
4028: if (bl == 0)
4029: {
4030: /* Create and initialize new iv_class. */
4031:
4032: bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
4033:
4034: bl->regno = REGNO (dest_reg);
4035: bl->biv = 0;
4036: bl->giv = 0;
4037: bl->biv_count = 0;
4038: bl->giv_count = 0;
4039:
4040: /* Set initial value to the reg itself. */
4041: bl->initial_value = dest_reg;
4042: /* We haven't seen the intializing insn yet */
4043: bl->init_insn = 0;
4044: bl->init_set = 0;
4045: bl->initial_test = 0;
4046: bl->incremented = 0;
4047: bl->eliminable = 0;
4048: bl->nonneg = 0;
4049: bl->reversed = 0;
4050:
4051: /* Add this class to loop_iv_list. */
4052: bl->next = loop_iv_list;
4053: loop_iv_list = bl;
4054:
4055: /* Put it in the array of biv register classes. */
4056: reg_biv_class[REGNO (dest_reg)] = bl;
4057: }
4058:
4059: /* Update IV_CLASS entry for this biv. */
4060: v->next_iv = bl->biv;
4061: bl->biv = v;
4062: bl->biv_count++;
4063: if (mult_val == const1_rtx)
4064: bl->incremented = 1;
4065:
4066: if (loop_dump_stream)
4067: {
4068: fprintf (loop_dump_stream,
4069: "Insn %d: possible biv, reg %d,",
4070: INSN_UID (insn), REGNO (dest_reg));
4071: if (GET_CODE (inc_val) == CONST_INT)
4072: fprintf (loop_dump_stream, " const = %d\n",
4073: INTVAL (inc_val));
4074: else
4075: {
4076: fprintf (loop_dump_stream, " const = ");
4077: print_rtl (loop_dump_stream, inc_val);
4078: fprintf (loop_dump_stream, "\n");
4079: }
4080: }
4081: }
4082:
4083: /* Fill in the data about one giv.
4084: V is the `struct induction' in which we record the giv. (It is
4085: allocated by the caller, with alloca.)
4086: INSN is the insn that sets it.
4087: BENEFIT estimates the savings from deleting this insn.
4088: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4089: into a register or is used as a memory address.
4090:
4091: SRC_REG is the biv reg which the giv is computed from.
4092: DEST_REG is the giv's reg (if the giv is stored in a reg).
4093: MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4094: LOCATION points to the place where this giv's value appears in INSN. */
4095:
4096: static void
4097: record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
4098: type, not_every_iteration, location, loop_start, loop_end)
4099: struct induction *v;
4100: rtx insn;
4101: rtx src_reg;
4102: rtx dest_reg;
4103: rtx mult_val, add_val;
4104: int benefit;
4105: enum g_types type;
4106: int not_every_iteration;
4107: rtx *location;
4108: rtx loop_start, loop_end;
4109: {
4110: struct induction *b;
4111: struct iv_class *bl;
4112: rtx set = single_set (insn);
4113: rtx p;
4114:
4115: v->insn = insn;
4116: v->src_reg = src_reg;
4117: v->giv_type = type;
4118: v->dest_reg = dest_reg;
4119: v->mult_val = mult_val;
4120: v->add_val = add_val;
4121: v->benefit = benefit;
4122: v->location = location;
4123: v->cant_derive = 0;
4124: v->combined_with = 0;
4125: v->maybe_dead = 0;
4126: v->derive_adjustment = 0;
4127: v->same = 0;
4128: v->ignore = 0;
4129: v->new_reg = 0;
4130: v->final_value = 0;
4131:
4132: /* The v->always_computable field is used in update_giv_derive, to
4133: determine whether a giv can be used to derive another giv. For a
4134: DEST_REG giv, INSN computes a new value for the giv, so its value
4135: isn't computable if INSN insn't executed every iteration.
4136: However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4137: it does not compute a new value. Hence the value is always computable
1.1.1.2 ! root 4138: regardless of whether INSN is executed each iteration. */
1.1 root 4139:
4140: if (type == DEST_ADDR)
4141: v->always_computable = 1;
4142: else
4143: v->always_computable = ! not_every_iteration;
4144:
4145: if (type == DEST_ADDR)
4146: {
4147: v->mode = GET_MODE (*location);
4148: v->lifetime = 1;
4149: v->times_used = 1;
4150: }
4151: else /* type == DEST_REG */
4152: {
4153: v->mode = GET_MODE (SET_DEST (set));
4154:
4155: v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]]
4156: - uid_luid[regno_first_uid[REGNO (dest_reg)]]);
4157:
4158: v->times_used = n_times_used[REGNO (dest_reg)];
4159:
4160: /* If the lifetime is zero, it means that this register is
4161: really a dead store. So mark this as a giv that can be
4162: ignored. This will not prevent the biv from being eliminated. */
4163: if (v->lifetime == 0)
4164: v->ignore = 1;
4165:
4166: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
4167: reg_iv_info[REGNO (dest_reg)] = v;
4168: }
4169:
4170: /* Add the giv to the class of givs computed from one biv. */
4171:
4172: bl = reg_biv_class[REGNO (src_reg)];
4173: if (bl)
4174: {
4175: v->next_iv = bl->giv;
4176: bl->giv = v;
4177: /* Don't count DEST_ADDR. This is supposed to count the number of
4178: insns that calculate givs. */
4179: if (type == DEST_REG)
4180: bl->giv_count++;
4181: bl->total_benefit += benefit;
4182: }
4183: else
4184: /* Fatal error, biv missing for this giv? */
4185: abort ();
4186:
4187: if (type == DEST_ADDR)
4188: v->replaceable = 1;
4189: else
4190: {
4191: /* The giv can be replaced outright by the reduced register only if all
4192: of the following conditions are true:
4193: - the insn that sets the giv is always executed on any iteration
4194: on which the giv is used at all
4195: (there are two ways to deduce this:
4196: either the insn is executed on every iteration,
4197: or all uses follow that insn in the same basic block),
4198: - the giv is not used outside the loop
4199: - no assignments to the biv occur during the giv's lifetime. */
4200:
4201: if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn)
4202: /* Previous line always fails if INSN was moved by loop opt. */
4203: && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end)
4204: && (! not_every_iteration
4205: || last_use_this_basic_block (dest_reg, insn)))
4206: {
4207: /* Now check that there are no assignments to the biv within the
4208: giv's lifetime. This requires two separate checks. */
4209:
4210: /* Check each biv update, and fail if any are between the first
4211: and last use of the giv.
4212:
4213: If this loop contains an inner loop that was unrolled, then
4214: the insn modifying the biv may have been emitted by the loop
4215: unrolling code, and hence does not have a valid luid. Just
4216: mark the biv as not replaceable in this case. It is not very
4217: useful as a biv, because it is used in two different loops.
4218: It is very unlikely that we would be able to optimize the giv
4219: using this biv anyways. */
4220:
4221: v->replaceable = 1;
4222: for (b = bl->biv; b; b = b->next_iv)
4223: {
4224: if (INSN_UID (b->insn) >= max_uid_for_loop
4225: || ((uid_luid[INSN_UID (b->insn)]
4226: >= uid_luid[regno_first_uid[REGNO (dest_reg)]])
4227: && (uid_luid[INSN_UID (b->insn)]
4228: <= uid_luid[regno_last_uid[REGNO (dest_reg)]])))
4229: {
4230: v->replaceable = 0;
4231: v->not_replaceable = 1;
4232: break;
4233: }
4234: }
4235:
4236: /* Check each insn between the first and last use of the giv,
4237: and fail if any of them are branches that jump to a named label
4238: outside this range, but still inside the loop. This catches
4239: cases of spaghetti code where the execution order of insns
4240: is not linear, and hence the above test fails. For example,
4241: in the following code, j is not replaceable:
4242: for (i = 0; i < 100; ) {
4243: L0: j = 4*i; goto L1;
4244: L2: k = j; goto L3;
4245: L1: i++; goto L2;
4246: L3: ; }
4247: printf ("k = %d\n", k); }
4248: This test is conservative, but this test succeeds rarely enough
4249: that it isn't a problem. See also check_final_value below. */
4250:
4251: if (v->replaceable)
4252: for (p = insn;
4253: INSN_UID (p) >= max_uid_for_loop
4254: || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]];
4255: p = NEXT_INSN (p))
4256: {
4257: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4258: && LABEL_NAME (JUMP_LABEL (p))
4259: && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)
4260: && (INSN_LUID (JUMP_LABEL (p))
4261: < uid_luid[regno_first_uid[REGNO (dest_reg)]]))
4262: || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)
4263: && (INSN_LUID (JUMP_LABEL (p))
4264: > uid_luid[regno_last_uid[REGNO (dest_reg)]]))))
4265: {
4266: v->replaceable = 0;
4267: v->not_replaceable = 1;
4268:
4269: if (loop_dump_stream)
4270: fprintf (loop_dump_stream,
4271: "Found branch outside giv lifetime.\n");
4272:
4273: break;
4274: }
4275: }
4276: }
4277: else
4278: {
4279: /* May still be replaceable, we don't have enough info here to
4280: decide. */
4281: v->replaceable = 0;
4282: v->not_replaceable = 0;
4283: }
4284: }
4285:
4286: if (loop_dump_stream)
4287: {
4288: if (type == DEST_REG)
4289: fprintf (loop_dump_stream, "Insn %d: giv reg %d",
4290: INSN_UID (insn), REGNO (dest_reg));
4291: else
4292: fprintf (loop_dump_stream, "Insn %d: dest address",
4293: INSN_UID (insn));
4294:
4295: fprintf (loop_dump_stream, " src reg %d benefit %d",
4296: REGNO (src_reg), v->benefit);
4297: fprintf (loop_dump_stream, " used %d lifetime %d",
4298: v->times_used, v->lifetime);
4299:
4300: if (v->replaceable)
4301: fprintf (loop_dump_stream, " replaceable");
4302:
4303: if (GET_CODE (mult_val) == CONST_INT)
4304: fprintf (loop_dump_stream, " mult %d",
4305: INTVAL (mult_val));
4306: else
4307: {
4308: fprintf (loop_dump_stream, " mult ");
4309: print_rtl (loop_dump_stream, mult_val);
4310: }
4311:
4312: if (GET_CODE (add_val) == CONST_INT)
4313: fprintf (loop_dump_stream, " add %d",
4314: INTVAL (add_val));
4315: else
4316: {
4317: fprintf (loop_dump_stream, " add ");
4318: print_rtl (loop_dump_stream, add_val);
4319: }
4320: }
4321:
4322: if (loop_dump_stream)
4323: fprintf (loop_dump_stream, "\n");
4324:
4325: }
4326:
4327:
4328: /* All this does is determine whether a giv can be made replaceable because
4329: its final value can be calculated. This code can not be part of record_giv
4330: above, because final_giv_value requires that the number of loop iterations
4331: be known, and that can not be accurately calculated until after all givs
4332: have been identified. */
4333:
4334: static void
4335: check_final_value (v, loop_start, loop_end)
4336: struct induction *v;
4337: rtx loop_start, loop_end;
4338: {
4339: struct iv_class *bl;
4340: rtx final_value = 0;
4341: rtx tem;
4342:
4343: bl = reg_biv_class[REGNO (v->src_reg)];
4344:
4345: /* DEST_ADDR givs will never reach here, because they are always marked
4346: replaceable above in record_giv. */
4347:
4348: /* The giv can be replaced outright by the reduced register only if all
4349: of the following conditions are true:
4350: - the insn that sets the giv is always executed on any iteration
4351: on which the giv is used at all
4352: (there are two ways to deduce this:
4353: either the insn is executed on every iteration,
4354: or all uses follow that insn in the same basic block),
4355: - its final value can be calculated (this condition is different
4356: than the one above in record_giv)
4357: - no assignments to the biv occur during the giv's lifetime. */
4358:
4359: #if 0
4360: /* This is only called now when replaceable is known to be false. */
4361: /* Clear replaceable, so that it won't confuse final_giv_value. */
4362: v->replaceable = 0;
4363: #endif
4364:
4365: if ((final_value = final_giv_value (v, loop_start, loop_end))
4366: && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
4367: {
4368: int biv_increment_seen = 0;
4369: rtx p = v->insn;
4370: rtx last_giv_use;
4371:
4372: v->replaceable = 1;
4373:
4374: /* When trying to determine whether or not a biv increment occurs
4375: during the lifetime of the giv, we can ignore uses of the variable
4376: outside the loop because final_value is true. Hence we can not
4377: use regno_last_uid and regno_first_uid as above in record_giv. */
4378:
4379: /* Search the loop to determine whether any assignments to the
4380: biv occur during the giv's lifetime. Start with the insn
4381: that sets the giv, and search around the loop until we come
4382: back to that insn again.
4383:
4384: Also fail if there is a jump within the giv's lifetime that jumps
4385: to somewhere outside the lifetime but still within the loop. This
4386: catches spaghetti code where the execution order is not linear, and
4387: hence the above test fails. Here we assume that the giv lifetime
4388: does not extend from one iteration of the loop to the next, so as
4389: to make the test easier. Since the lifetime isn't known yet,
4390: this requires two loops. See also record_giv above. */
4391:
4392: last_giv_use = v->insn;
4393:
4394: while (1)
4395: {
4396: p = NEXT_INSN (p);
4397: if (p == loop_end)
4398: p = NEXT_INSN (loop_start);
4399: if (p == v->insn)
4400: break;
4401:
4402: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4403: || GET_CODE (p) == CALL_INSN)
4404: {
4405: if (biv_increment_seen)
4406: {
4407: if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4408: {
4409: v->replaceable = 0;
4410: v->not_replaceable = 1;
4411: break;
4412: }
4413: }
4414: else if (GET_CODE (PATTERN (p)) == SET
4415: && SET_DEST (PATTERN (p)) == v->src_reg)
4416: biv_increment_seen = 1;
4417: else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4418: last_giv_use = p;
4419: }
4420: }
4421:
4422: /* Now that the lifetime of the giv is known, check for branches
4423: from within the lifetime to outside the lifetime if it is still
4424: replaceable. */
4425:
4426: if (v->replaceable)
4427: {
4428: p = v->insn;
4429: while (1)
4430: {
4431: p = NEXT_INSN (p);
4432: if (p == loop_end)
4433: p = NEXT_INSN (loop_start);
4434: if (p == last_giv_use)
4435: break;
4436:
4437: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4438: && LABEL_NAME (JUMP_LABEL (p))
4439: && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
4440: && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
4441: || (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
4442: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
4443: {
4444: v->replaceable = 0;
4445: v->not_replaceable = 1;
4446:
4447: if (loop_dump_stream)
4448: fprintf (loop_dump_stream,
4449: "Found branch outside giv lifetime.\n");
4450:
4451: break;
4452: }
4453: }
4454: }
4455:
4456: /* If it is replaceable, then save the final value. */
4457: if (v->replaceable)
4458: v->final_value = final_value;
4459: }
4460:
4461: if (loop_dump_stream && v->replaceable)
4462: fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
4463: INSN_UID (v->insn), REGNO (v->dest_reg));
4464: }
4465:
4466: /* Update the status of whether a giv can derive other givs.
4467:
4468: We need to do something special if there is or may be an update to the biv
4469: between the time the giv is defined and the time it is used to derive
4470: another giv.
4471:
4472: In addition, a giv that is only conditionally set is not allowed to
4473: derive another giv once a label has been passed.
4474:
4475: The cases we look at are when a label or an update to a biv is passed. */
4476:
4477: static void
4478: update_giv_derive (p)
4479: rtx p;
4480: {
4481: struct iv_class *bl;
4482: struct induction *biv, *giv;
4483: rtx tem;
4484: int dummy;
4485:
4486: /* Search all IV classes, then all bivs, and finally all givs.
4487:
4488: There are two cases we are concerned with. First we have the situation
4489: of a giv that is only updated conditionally. In that case, it may not
4490: derive any givs after a label is passed.
4491:
4492: The second case is when a biv update occurs, or may occur, after the
4493: definition of a giv. For certain biv updates (see below) that are
4494: known to occur between the giv definition and use, we can adjust the
4495: giv definition. For others, or when the biv update is conditional,
4496: we must prevent the giv from deriving any other givs. There are two
4497: sub-cases within this case.
4498:
4499: If this is a label, we are concerned with any biv update that is done
4500: conditionally, since it may be done after the giv is defined followed by
4501: a branch here (actually, we need to pass both a jump and a label, but
4502: this extra tracking doesn't seem worth it).
4503:
4504: If this is a giv update, we must adjust the giv status to show that a
4505: subsequent biv update was performed. If this adjustment cannot be done,
4506: the giv cannot derive further givs. */
4507:
4508: for (bl = loop_iv_list; bl; bl = bl->next)
4509: for (biv = bl->biv; biv; biv = biv->next_iv)
4510: if (GET_CODE (p) == CODE_LABEL || biv->insn == p)
4511: {
4512: for (giv = bl->giv; giv; giv = giv->next_iv)
4513: {
4514: /* If cant_derive is already true, there is no point in
4515: checking all of these conditions again. */
4516: if (giv->cant_derive)
4517: continue;
4518:
4519: /* If this giv is conditionally set and we have passed a label,
4520: it cannot derive anything. */
4521: if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
4522: giv->cant_derive = 1;
4523:
4524: /* Skip givs that have mult_val == 0, since
4525: they are really invariants. Also skip those that are
4526: replaceable, since we know their lifetime doesn't contain
4527: any biv update. */
4528: else if (giv->mult_val == const0_rtx || giv->replaceable)
4529: continue;
4530:
4531: /* The only way we can allow this giv to derive another
4532: is if this is a biv increment and we can form the product
4533: of biv->add_val and giv->mult_val. In this case, we will
4534: be able to compute a compensation. */
4535: else if (biv->insn == p)
4536: {
1.1.1.2 ! root 4537: tem = 0;
! 4538:
! 4539: if (biv->mult_val == const1_rtx)
! 4540: tem = simplify_giv_expr (gen_rtx (MULT, giv->mode,
! 4541: biv->add_val,
! 4542: giv->mult_val),
! 4543: &dummy);
! 4544:
! 4545: if (tem && giv->derive_adjustment)
! 4546: tem = simplify_giv_expr (gen_rtx (PLUS, giv->mode, tem,
! 4547: giv->derive_adjustment),
! 4548: &dummy);
! 4549: if (tem)
1.1 root 4550: giv->derive_adjustment = tem;
4551: else
4552: giv->cant_derive = 1;
4553: }
4554: else if (GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
4555: giv->cant_derive = 1;
4556: }
4557: }
4558: }
4559:
4560: /* Check whether an insn is an increment legitimate for a basic induction var.
4561: X is the source of the insn.
4562: DEST_REG is the putative biv, also the destination of the insn.
4563: We accept patterns of these forms:
4564: REG = REG + INVARIANT
4565: REG = INVARIANT + REG
4566: REG = REG - CONSTANT
4567:
4568: If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
4569: and store the additive term into *INC_VAL.
4570:
4571: If X is an assignment of an invariant into DEST_REG, we set
4572: *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
4573:
4574: Otherwise we return 0. */
4575:
4576: static int
4577: basic_induction_var (x, dest_reg, inc_val, mult_val)
4578: register rtx x;
4579: rtx dest_reg;
4580: rtx *inc_val;
4581: rtx *mult_val;
4582: {
4583: register enum rtx_code code;
4584: rtx arg;
4585:
4586: code = GET_CODE (x);
4587: switch (code)
4588: {
4589: case PLUS:
4590: if (XEXP (x, 0) == dest_reg)
4591: arg = XEXP (x, 1);
4592: else if (XEXP (x, 1) == dest_reg)
4593: arg = XEXP (x, 0);
4594: else
4595: return 0;
4596:
4597: if (invariant_p (arg) != 1)
4598: return 0;
4599:
4600: *inc_val = arg;
4601: *mult_val = const1_rtx;
4602: return 1;
4603:
4604: case MINUS:
4605: if (XEXP (x, 0) == dest_reg
4606: && GET_CODE (XEXP (x, 1)) == CONST_INT)
4607: *inc_val = gen_rtx (CONST_INT, VOIDmode,
4608: - INTVAL (XEXP (x, 1)));
4609: else
4610: return 0;
4611:
4612: *mult_val = const1_rtx;
4613: return 1;
4614:
4615: /* Can accept constant setting of biv only when inside inner most loop.
4616: Otherwise, a biv of an inner loop may be incorrectly recognized
4617: as a biv of the outer loop,
4618: causing code to be moved INTO the inner loop. */
4619: case MEM:
4620: case REG:
4621: if (invariant_p (x) != 1)
4622: return 0;
4623: case CONST_INT:
4624: case SYMBOL_REF:
4625: case CONST:
4626: if (loops_enclosed == 1)
4627: {
4628: *inc_val = x;
4629: *mult_val = const0_rtx;
4630: return 1;
4631: }
4632: else
4633: return 0;
4634:
4635: default:
4636: return 0;
4637: }
4638: }
4639:
4640: /* A general induction variable (giv) is any quantity that is a linear
4641: function of a basic induction variable,
4642: i.e. giv = biv * mult_val + add_val.
4643: The coefficients can be any loop invariant quantity.
4644: A giv need not be computed directly from the biv;
4645: it can be computed by way of other givs. */
4646:
4647: /* Determine whether X computes a giv.
4648: If it does, return a nonzero value
4649: which is the benefit from eliminating the computation of X;
4650: set *SRC_REG to the register of the biv that it is computed from;
4651: set *ADD_VAL and *MULT_VAL to the coefficients,
4652: such that the value of X is biv * mult + add; */
4653:
4654: static int
4655: general_induction_var (x, src_reg, add_val, mult_val)
4656: rtx x;
4657: rtx *src_reg;
4658: rtx *add_val;
4659: rtx *mult_val;
4660: {
4661: rtx orig_x = x;
4662: int benefit = 0;
4663: char *storage;
4664:
4665: /* If this is an invariant, forget it, it isn't a giv. */
4666: if (invariant_p (x) == 1)
4667: return 0;
4668:
4669: /* See if the expression could be a giv and get its form.
4670: Mark our place on the obstack in case we don't find a giv. */
4671: storage = (char *) oballoc (0);
4672: x = simplify_giv_expr (x, &benefit);
4673: if (x == 0)
4674: {
4675: obfree (storage);
4676: return 0;
4677: }
4678:
4679: switch (GET_CODE (x))
4680: {
4681: case USE:
4682: case CONST_INT:
4683: /* Since this is now an invariant and wasn't before, it must be a giv
4684: with MULT_VAL == 0. It doesn't matter which BIV we associate this
4685: with. */
4686: *src_reg = loop_iv_list->biv->dest_reg;
4687: *mult_val = const0_rtx;
4688: *add_val = x;
4689: break;
4690:
4691: case REG:
4692: /* This is equivalent to a BIV. */
4693: *src_reg = x;
4694: *mult_val = const1_rtx;
4695: *add_val = const0_rtx;
4696: break;
4697:
4698: case PLUS:
4699: /* Either (plus (biv) (invar)) or
4700: (plus (mult (biv) (invar_1)) (invar_2)). */
4701: if (GET_CODE (XEXP (x, 0)) == MULT)
4702: {
4703: *src_reg = XEXP (XEXP (x, 0), 0);
4704: *mult_val = XEXP (XEXP (x, 0), 1);
4705: }
4706: else
4707: {
4708: *src_reg = XEXP (x, 0);
4709: *mult_val = const1_rtx;
4710: }
4711: *add_val = XEXP (x, 1);
4712: break;
4713:
4714: case MULT:
4715: /* ADD_VAL is zero. */
4716: *src_reg = XEXP (x, 0);
4717: *mult_val = XEXP (x, 1);
4718: *add_val = const0_rtx;
4719: break;
4720:
4721: default:
4722: abort ();
4723: }
4724:
4725: /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
4726: unless they are CONST_INT). */
4727: if (GET_CODE (*add_val) == USE)
4728: *add_val = XEXP (*add_val, 0);
4729: if (GET_CODE (*mult_val) == USE)
4730: *mult_val = XEXP (*mult_val, 0);
4731:
4732: benefit += rtx_cost (orig_x);
4733:
4734: /* Always return some benefit if this is a giv so it will be detected
4735: as such. This allows elimination of bivs that might otherwise
4736: not be eliminated. */
4737: return benefit == 0 ? 1 : benefit;
4738: }
4739:
4740: /* Given an expression, X, try to form it as a linear function of a biv.
4741: We will canonicalize it to be of the form
4742: (plus (mult (BIV) (invar_1))
4743: (invar_2))
4744: with possibile degeneracies.
4745:
4746: The invariant expressions must each be of a form that can be used as a
4747: machine operand. We surround then with a USE rtx (a hack, but localized
4748: and certainly unambiguous!) if not a CONST_INT for simplicity in this
4749: routine; it is the caller's responsibility to strip them.
4750:
4751: If no such canonicalization is possible (i.e., two biv's are used or an
4752: expression that is neither invariant nor a biv or giv), this routine
4753: returns 0.
4754:
4755: For a non-zero return, the result will have a code of CONST_INT, USE,
4756: REG (for a BIV), PLUS, or MULT. No other codes will occur.
4757:
4758: *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
4759:
4760: static rtx
4761: simplify_giv_expr (x, benefit)
4762: rtx x;
4763: int *benefit;
4764: {
4765: enum machine_mode mode = GET_MODE (x);
4766: rtx arg0, arg1;
4767: rtx tem;
4768:
4769: /* If this is not an integer mode, or if we cannot do arithmetic in this
4770: mode, this can't be a giv. */
4771: if (mode != VOIDmode
4772: && (GET_MODE_CLASS (mode) != MODE_INT
4773: || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_INT))
4774: return 0;
4775:
4776: switch (GET_CODE (x))
4777: {
4778: case PLUS:
4779: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4780: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4781: if (arg0 == 0 || arg1 == 0)
4782: return 0;
4783:
4784: /* Put constant last, CONST_INT last if both constant. */
4785: if ((GET_CODE (arg0) == USE
4786: || GET_CODE (arg0) == CONST_INT)
4787: && GET_CODE (arg1) != CONST_INT)
4788: tem = arg0, arg0 = arg1, arg1 = tem;
4789:
4790: /* Handle addition of zero, then addition of an invariant. */
4791: if (arg1 == const0_rtx)
4792: return arg0;
4793: else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
4794: switch (GET_CODE (arg0))
4795: {
4796: case CONST_INT:
4797: case USE:
4798: /* Both invariant. Only valid if sum is machine operand.
4799: First strip off possible USE on first operand. */
4800: if (GET_CODE (arg0) == USE)
4801: arg0 = XEXP (arg0, 0);
4802:
4803: tem = 0;
4804: if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
4805: {
4806: tem = plus_constant (arg0, INTVAL (arg1));
4807: if (GET_CODE (tem) != CONST_INT)
4808: tem = gen_rtx (USE, mode, tem);
4809: }
4810:
4811: return tem;
4812:
4813: case REG:
4814: case MULT:
4815: /* biv + invar or mult + invar. Return sum. */
4816: return gen_rtx (PLUS, mode, arg0, arg1);
4817:
4818: case PLUS:
4819: /* (a + invar_1) + invar_2. Associate. */
4820: return simplify_giv_expr (gen_rtx (PLUS, mode,
4821: XEXP (arg0, 0),
4822: gen_rtx (PLUS, mode,
4823: XEXP (arg0, 1), arg1)),
4824: benefit);
4825:
4826: default:
4827: abort ();
4828: }
4829:
4830: /* Each argument must be either REG, PLUS, or MULT. Convert REG to
4831: MULT to reduce cases. */
4832: if (GET_CODE (arg0) == REG)
4833: arg0 = gen_rtx (MULT, mode, arg0, const1_rtx);
4834: if (GET_CODE (arg1) == REG)
4835: arg1 = gen_rtx (MULT, mode, arg1, const1_rtx);
4836:
4837: /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
4838: Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
4839: Recurse to associate the second PLUS. */
4840: if (GET_CODE (arg1) == MULT)
4841: tem = arg0, arg0 = arg1, arg1 = tem;
4842:
4843: if (GET_CODE (arg1) == PLUS)
4844: return simplify_giv_expr (gen_rtx (PLUS, mode,
4845: gen_rtx (PLUS, mode,
4846: arg0, XEXP (arg1, 0)),
4847: XEXP (arg1, 1)),
4848: benefit);
4849:
4850: /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
4851: if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
4852: abort ();
4853:
4854: if (XEXP (arg0, 0) != XEXP (arg1, 0))
4855: return 0;
4856:
4857: return simplify_giv_expr (gen_rtx (MULT, mode,
4858: XEXP (arg0, 0),
4859: gen_rtx (PLUS, mode,
4860: XEXP (arg0, 1),
4861: XEXP (arg1, 1))),
4862: benefit);
4863:
4864: case MINUS:
4865: /* Handle "a - b" as "a + b * (-1)". */
4866: return simplify_giv_expr (gen_rtx (PLUS, mode,
4867: XEXP (x, 0),
4868: gen_rtx (MULT, mode,
4869: XEXP (x, 1),
4870: gen_rtx (CONST_INT,
4871: VOIDmode, -1))),
4872: benefit);
4873:
4874: case MULT:
4875: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4876: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4877: if (arg0 == 0 || arg1 == 0)
4878: return 0;
4879:
4880: /* Put constant last, CONST_INT last if both constant. */
4881: if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
4882: && GET_CODE (arg1) != CONST_INT)
4883: tem = arg0, arg0 = arg1, arg1 = tem;
4884:
4885: /* If second argument is not now constant, not giv. */
4886: if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
4887: return 0;
4888:
4889: /* Handle multiply by 0 or 1. */
4890: if (arg1 == const0_rtx)
4891: return const0_rtx;
4892:
4893: else if (arg1 == const1_rtx)
4894: return arg0;
4895:
4896: switch (GET_CODE (arg0))
4897: {
4898: case REG:
4899: /* biv * invar. Done. */
4900: return gen_rtx (MULT, mode, arg0, arg1);
4901:
4902: case CONST_INT:
4903: /* Product of two constants. */
4904: return gen_rtx (CONST_INT, mode, INTVAL (arg0) * INTVAL (arg1));
4905:
4906: case USE:
4907: /* invar * invar. Not giv. */
4908: return 0;
4909:
4910: case MULT:
4911: /* (a * invar_1) * invar_2. Associate. */
4912: return simplify_giv_expr (gen_rtx (MULT, mode,
4913: XEXP (arg0, 0),
4914: gen_rtx (MULT, mode,
4915: XEXP (arg0, 1), arg1)),
4916: benefit);
4917:
4918: case PLUS:
4919: /* (a + invar_1) * invar_2. Distribute. */
4920: return simplify_giv_expr (gen_rtx (PLUS, mode,
4921: gen_rtx (MULT, mode,
4922: XEXP (arg0, 0), arg1),
4923: gen_rtx (MULT, mode,
4924: XEXP (arg0, 1), arg1)),
4925: benefit);
4926:
4927: default:
4928: abort ();
4929: }
4930:
4931: case ASHIFT:
4932: case LSHIFT:
4933: /* Shift by constant is multiply by power of two. */
4934: if (GET_CODE (XEXP (x, 1)) != CONST_INT)
4935: return 0;
4936:
4937: return simplify_giv_expr (gen_rtx (MULT, mode,
4938: XEXP (x, 0),
4939: gen_rtx (CONST_INT, VOIDmode,
4940: 1 << INTVAL (XEXP (x, 1)))),
4941: benefit);
4942:
4943: case NEG:
4944: /* "-a" is "a * (-1)" */
4945: return simplify_giv_expr (gen_rtx (MULT, mode,
4946: XEXP (x, 0),
4947: gen_rtx (CONST_INT, VOIDmode, -1)),
4948: benefit);
4949:
4950: case NOT:
4951: /* "~a" is "-a - 1". Silly, but easy. */
4952: return simplify_giv_expr (gen_rtx (MINUS, mode,
4953: gen_rtx (NEG, mode, XEXP (x, 0)),
4954: const1_rtx),
4955: benefit);
4956:
4957: case USE:
4958: /* Already in proper form for invariant. */
4959: return x;
4960:
4961: case REG:
4962: /* If this is a new register, we can't deal with it. */
4963: if (REGNO (x) >= max_reg_before_loop)
4964: return 0;
4965:
4966: /* Check for biv or giv. */
4967: switch (reg_iv_type[REGNO (x)])
4968: {
4969: case BASIC_INDUCT:
4970: return x;
4971: case GENERAL_INDUCT:
4972: {
4973: struct induction *v = reg_iv_info[REGNO (x)];
4974:
4975: /* Form expression from giv and add benefit. Ensure this giv
4976: can derive another and subtract any needed adjustment if so. */
4977: *benefit += v->benefit;
4978: if (v->cant_derive)
4979: return 0;
4980:
4981: tem = gen_rtx (PLUS, mode, gen_rtx (MULT, mode,
4982: v->src_reg, v->mult_val),
4983: v->add_val);
4984: if (v->derive_adjustment)
4985: tem = gen_rtx (MINUS, mode, tem, v->derive_adjustment);
4986: return simplify_giv_expr (tem, benefit);
4987: }
4988: }
4989:
4990: /* Fall through to general case. */
4991: default:
4992: /* If invariant, return as USE (unless CONST_INT).
4993: Otherwise, not giv. */
4994: if (GET_CODE (x) == USE)
4995: x = XEXP (x, 0);
4996:
4997: if (invariant_p (x) == 1)
4998: {
4999: if (GET_CODE (x) == CONST_INT)
5000: return x;
5001: else
5002: return gen_rtx (USE, mode, x);
5003: }
5004: else
5005: return 0;
5006: }
5007: }
5008:
5009: /* Help detect a giv that is calculated by several consecutive insns;
5010: for example,
5011: giv = biv * M
5012: giv = giv + A
5013: The caller has already identified the first insn P as having a giv as dest;
5014: we check that all other insns that set the same register follow
5015: immediately after P, that they alter nothing else,
5016: and that the result of the last is still a giv.
5017:
5018: The value is 0 if the reg set in P is not really a giv.
5019: Otherwise, the value is the amount gained by eliminating
5020: all the consecutive insns that compute the value.
5021:
5022: FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
5023: SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
5024:
5025: The coefficients of the ultimate giv value are stored in
5026: *MULT_VAL and *ADD_VAL. */
5027:
5028: static int
5029: consec_sets_giv (first_benefit, p, src_reg, dest_reg,
5030: add_val, mult_val)
5031: int first_benefit;
5032: rtx p;
5033: rtx src_reg;
5034: rtx dest_reg;
5035: rtx *add_val;
5036: rtx *mult_val;
5037: {
5038: int count;
5039: enum rtx_code code;
5040: int benefit;
5041: rtx temp;
5042: rtx set;
5043:
5044: /* Indicate that this is a giv so that we can update the value produced in
5045: each insn of the multi-insn sequence.
5046:
5047: This induction structure will be used only by the call to
5048: general_induction_var below, so we can allocate it on our stack.
5049: If this is a giv, our caller will replace the induct var entry with
5050: a new induction structure. */
5051: struct induction *v
5052: = (struct induction *) alloca (sizeof (struct induction));
5053: v->src_reg = src_reg;
5054: v->mult_val = *mult_val;
5055: v->add_val = *add_val;
5056: v->benefit = first_benefit;
5057: v->cant_derive = 0;
5058: v->derive_adjustment = 0;
5059:
5060: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
5061: reg_iv_info[REGNO (dest_reg)] = v;
5062:
5063: count = n_times_set[REGNO (dest_reg)] - 1;
5064:
5065: while (count > 0)
5066: {
5067: p = NEXT_INSN (p);
5068: code = GET_CODE (p);
5069:
5070: /* If libcall, skip to end of call sequence. */
5071: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
5072: p = XEXP (temp, 0);
5073:
5074: if (code == INSN
5075: && (set = single_set (p))
5076: && GET_CODE (SET_DEST (set)) == REG
5077: && SET_DEST (set) == dest_reg
5078: && ((benefit = general_induction_var (SET_SRC (set), &src_reg,
5079: add_val, mult_val))
5080: /* Giv created by equivalent expression. */
5081: || ((temp = find_reg_note (p, REG_EQUAL, 0))
5082: && (benefit = general_induction_var (XEXP (temp, 0), &src_reg,
5083: add_val, mult_val))))
5084: && src_reg == v->src_reg)
5085: {
5086: if (find_reg_note (p, REG_RETVAL, 0))
5087: benefit += libcall_benefit (p);
5088:
5089: count--;
5090: v->mult_val = *mult_val;
5091: v->add_val = *add_val;
5092: v->benefit = benefit;
5093: }
5094: else if (code != NOTE)
5095: {
5096: /* Allow insns that set something other than this giv to a
5097: constant. Such insns are needed on machines which cannot
5098: include long constants and should not disqualify a giv. */
5099: if (code == INSN
5100: && (set = single_set (p))
5101: && SET_DEST (set) != dest_reg
5102: && CONSTANT_P (SET_SRC (set)))
5103: continue;
5104:
5105: reg_iv_type[REGNO (dest_reg)] = UNKNOWN_INDUCT;
5106: return 0;
5107: }
5108: }
5109:
5110: return v->benefit;
5111: }
5112:
5113: /* Return an rtx, if any, that expresses giv G2 as a function of the register
5114: represented by G1. If no such expression can be found, or it is clear that
5115: it cannot possibly be a valid address, 0 is returned.
5116:
5117: To perform the computation, we note that
5118: G1 = a * v + b and
5119: G2 = c * v + d
5120: where `v' is the biv.
5121:
5122: So G2 = (c/a) * G1 + (d - b*c/a) */
5123:
5124: #ifdef ADDRESS_COST
5125: static rtx
5126: express_from (g1, g2)
5127: struct induction *g1, *g2;
5128: {
5129: rtx mult, add;
5130:
5131: /* The value that G1 will be multiplied by must be a constant integer. Also,
5132: the only chance we have of getting a valid address is if b*c/a (see above
5133: for notation) is also an integer. */
5134: if (GET_CODE (g1->mult_val) != CONST_INT
5135: || GET_CODE (g2->mult_val) != CONST_INT
5136: || GET_CODE (g1->add_val) != CONST_INT
5137: || g1->mult_val == const0_rtx
5138: || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
5139: return 0;
5140:
5141: mult = gen_rtx (CONST_INT, VOIDmode,
5142: INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
5143: add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult));
5144:
5145: /* Form simplified final result. */
5146: if (mult == const0_rtx)
5147: return add;
5148: else if (mult == const1_rtx)
5149: mult = g1->dest_reg;
5150: else
5151: mult = gen_rtx (MULT, g2->mode, g1->dest_reg, mult);
5152:
5153: if (add == const0_rtx)
5154: return mult;
5155: else
5156: return gen_rtx (PLUS, g2->mode, mult, add);
5157: }
5158: #endif
5159:
5160: /* Return 1 if giv G2 can be combined with G1. This means that G2 can use
5161: (either directly or via an address expression) a register used to represent
5162: G1. Set g2->new_reg to a represtation of G1 (normally just
5163: g1->dest_reg). */
5164:
5165: static int
5166: combine_givs_p (g1, g2)
5167: struct induction *g1, *g2;
5168: {
5169: rtx tem;
5170:
5171: /* If these givs are identical, they can be combined. */
5172: if (rtx_equal_p (g1->mult_val, g2->mult_val)
5173: && rtx_equal_p (g1->add_val, g2->add_val))
5174: {
5175: g2->new_reg = g1->dest_reg;
5176: return 1;
5177: }
5178:
5179: #ifdef ADDRESS_COST
5180: /* If G2 can be expressed as a function of G1 and that function is valid
5181: as an address and no more expensive than using a register for G2,
5182: the expression of G2 in terms of G1 can be used. */
5183: if (g2->giv_type == DEST_ADDR
5184: && (tem = express_from (g1, g2)) != 0
5185: && memory_address_p (g2->mem_mode, tem)
5186: && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location))
5187: {
5188: g2->new_reg = tem;
5189: return 1;
5190: }
5191: #endif
5192:
5193: return 0;
5194: }
5195:
5196: /* Check all pairs of givs for iv_class BL and see if any can be combined with
5197: any other. If so, point SAME to the giv combined with and set NEW_REG to
5198: be an expression (in terms of the other giv's DEST_REG) equivalent to the
5199: giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
5200:
5201: static void
5202: combine_givs (bl)
5203: struct iv_class *bl;
5204: {
5205: struct induction *g1, *g2;
5206: int pass;
5207:
5208: for (g1 = bl->giv; g1; g1 = g1->next_iv)
5209: for (pass = 0; pass <= 1; pass++)
5210: for (g2 = bl->giv; g2; g2 = g2->next_iv)
5211: if (g1 != g2
5212: /* First try to combine with replaceable givs, then all givs. */
5213: && (g1->replaceable || pass == 1)
5214: /* If either has already been combined or is to be ignored, can't
5215: combine. */
5216: && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
5217: /* If something has been based on G2, G2 cannot itself be based
5218: on something else. */
5219: && ! g2->combined_with
5220: && combine_givs_p (g1, g2))
5221: {
5222: /* g2->new_reg set by `combine_givs_p' */
5223: g2->same = g1;
5224: g1->combined_with = 1;
5225: g1->benefit += g2->benefit;
5226: /* ??? The new final_[bg]iv_value code does a much better job
5227: of finding replaceable giv's, and hence this code may no
5228: longer be necessary. */
5229: if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
5230: g1->benefit -= copy_cost;
5231: g1->lifetime += g2->lifetime;
5232: g1->times_used += g2->times_used;
5233:
5234: if (loop_dump_stream)
5235: fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
5236: INSN_UID (g2->insn), INSN_UID (g1->insn));
5237: }
5238: }
5239:
5240: /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
5241:
5242: void
5243: emit_iv_add_mult (b, m, a, reg, insert_before)
5244: rtx b; /* initial value of basic induction variable */
5245: rtx m; /* multiplicative constant */
5246: rtx a; /* additive constant */
5247: rtx reg; /* destination register */
5248: rtx insert_before;
5249: {
5250: rtx seq;
5251: rtx result;
5252:
5253: /* Prevent unexpected sharing of these rtx. */
5254: a = copy_rtx (a);
5255: b = copy_rtx (b);
5256:
5257: /* Increase the lifetime of any invariants moved further in code. */
5258: update_reg_last_use (a, insert_before);
5259: update_reg_last_use (b, insert_before);
5260: update_reg_last_use (m, insert_before);
5261:
5262: start_sequence ();
5263: result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
5264: if (reg != result)
5265: emit_move_insn (reg, result);
5266: seq = gen_sequence ();
5267: end_sequence ();
5268:
5269: emit_insn_before (seq, insert_before);
5270: }
5271:
5272: /* Test whether A * B can be computed without
5273: an actual multiply insn. Value is 1 if so. */
5274:
5275: static int
5276: product_cheap_p (a, b)
5277: rtx a;
5278: rtx b;
5279: {
5280: int i;
5281: rtx tmp;
5282: struct obstack *old_rtl_obstack = rtl_obstack;
5283: char *storage = (char *) obstack_alloc (&temp_obstack, 0);
5284: int win = 1;
5285:
5286: /* If only one is constant, make it B. */
5287: if (GET_CODE (a) == CONST_INT)
5288: tmp = a, a = b, b = tmp;
5289:
5290: /* If first constant, both constant, so don't need multiply. */
5291: if (GET_CODE (a) == CONST_INT)
5292: return 1;
5293:
5294: /* If second not constant, neither is constant, so would need multiply. */
5295: if (GET_CODE (b) != CONST_INT)
5296: return 0;
5297:
5298: /* One operand is constant, so might not need multiply insn. Generate the
5299: code for the multiply and see if a call or multiply, or long sequence
5300: of insns is generated. */
5301:
5302: rtl_obstack = &temp_obstack;
5303: start_sequence ();
5304: expand_mult (GET_MODE (a), a, b, 0, 0);
5305: tmp = gen_sequence ();
5306: end_sequence ();
5307:
5308: if (GET_CODE (tmp) == SEQUENCE)
5309: {
5310: if (XVEC (tmp, 0) == 0)
5311: win = 1;
5312: else if (XVECLEN (tmp, 0) > 3)
5313: win = 0;
5314: else
5315: for (i = 0; i < XVECLEN (tmp, 0); i++)
5316: {
5317: rtx insn = XVECEXP (tmp, 0, i);
5318:
5319: if (GET_CODE (insn) != INSN
5320: || (GET_CODE (PATTERN (insn)) == SET
5321: && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
5322: || (GET_CODE (PATTERN (insn)) == PARALLEL
5323: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
5324: && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
5325: {
5326: win = 0;
5327: break;
5328: }
5329: }
5330: }
5331: else if (GET_CODE (tmp) == SET
5332: && GET_CODE (SET_SRC (tmp)) == MULT)
5333: win = 0;
5334: else if (GET_CODE (tmp) == PARALLEL
5335: && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
5336: && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
5337: win = 0;
5338:
5339: /* Free any storage we obtained in generating this multiply and restore rtl
5340: allocation to its normal obstack. */
5341: obstack_free (&temp_obstack, storage);
5342: rtl_obstack = old_rtl_obstack;
5343:
5344: return win;
5345: }
5346:
5347: /* Check to see if loop can be terminated by a "decrement and branch until
5348: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
5349: Also try reversing an increment loop to a decrement loop
5350: to see if the optimization can be performed.
5351: Value is nonzero if optimization was performed. */
5352:
5353: /* This is useful even if the architecture doesn't have such an insn,
5354: because it might change a loops which increments from 0 to n to a loop
5355: which decrements from n to 0. A loop that decrements to zero is usually
5356: faster than one that increments from zero. */
5357:
5358: /* ??? This could be rewritten to use some of the loop unrolling procedures,
5359: such as approx_final_value, biv_total_increment, loop_iterations, and
5360: final_[bg]iv_value. */
5361:
5362: static int
5363: check_dbra_loop (loop_end, insn_count, loop_start)
5364: rtx loop_end;
5365: int insn_count;
5366: rtx loop_start;
5367: {
5368: struct iv_class *bl;
5369: rtx reg;
5370: rtx jump_label;
5371: rtx final_value;
5372: rtx start_value;
5373: enum rtx_code branch_code;
5374: rtx new_add_val;
5375: rtx comparison;
5376: rtx before_comparison;
5377: rtx p;
5378:
5379: /* If last insn is a conditional branch, and the insn before tests a
5380: register value, try to optimize it. Otherwise, we can't do anything. */
5381:
5382: comparison = get_condition_for_loop (PREV_INSN (loop_end));
5383: if (comparison == 0)
5384: return 0;
5385:
5386: /* Check all of the bivs to see if the compare uses one of them.
5387: Skip biv's set more than once because we can't guarantee that
5388: it will be zero on the last iteration. Also skip if the biv is
5389: used between its update and the test insn. */
5390:
5391: for (bl = loop_iv_list; bl; bl = bl->next)
5392: {
5393: if (bl->biv_count == 1
5394: && bl->biv->dest_reg == XEXP (comparison, 0)
5395: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
5396: PREV_INSN (PREV_INSN (loop_end))))
5397: break;
5398: }
5399:
5400: if (! bl)
5401: return 0;
5402:
5403: /* Look for the case where the basic induction variable is always
5404: nonnegative, and equals zero on the last iteration.
5405: In this case, add a reg_note REG_NONNEG, which allows the
5406: m68k DBRA instruction to be used. */
5407:
5408: if (((GET_CODE (comparison) == GT
5409: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5410: && INTVAL (XEXP (comparison, 1)) == -1)
5411: || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
5412: && GET_CODE (bl->biv->add_val) == CONST_INT
5413: && INTVAL (bl->biv->add_val) < 0)
5414: {
5415: /* Initial value must be greater than 0,
5416: init_val % -dec_value == 0 to ensure that it equals zero on
5417: the last iteration */
5418:
5419: if (GET_CODE (bl->initial_value) == CONST_INT
5420: && INTVAL (bl->initial_value) > 0
5421: && (INTVAL (bl->initial_value) %
5422: (-INTVAL (bl->biv->add_val))) == 0)
5423: {
5424: /* register always nonnegative, add REG_NOTE to branch */
5425: REG_NOTES (PREV_INSN (loop_end))
5426: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5427: REG_NOTES (PREV_INSN (loop_end)));
5428: bl->nonneg = 1;
5429:
5430: return 1;
5431: }
5432:
5433: /* If the decrement is 1 and the value was tested as >= 0 before
5434: the loop, then we can safely optimize. */
5435: for (p = loop_start; p; p = PREV_INSN (p))
5436: {
5437: if (GET_CODE (p) == CODE_LABEL)
5438: break;
5439: if (GET_CODE (p) != JUMP_INSN)
5440: continue;
5441:
5442: before_comparison = get_condition_for_loop (p);
5443: if (before_comparison
5444: && XEXP (before_comparison, 0) == bl->biv->dest_reg
5445: && GET_CODE (before_comparison) == LT
5446: && XEXP (before_comparison, 1) == const0_rtx
5447: && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
5448: && INTVAL (bl->biv->add_val) == -1)
5449: {
5450: REG_NOTES (PREV_INSN (loop_end))
5451: = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5452: REG_NOTES (PREV_INSN (loop_end)));
5453: bl->nonneg = 1;
5454:
5455: return 1;
5456: }
5457: }
5458: }
5459: else if (num_mem_sets <= 1)
5460: {
5461: /* Try to change inc to dec, so can apply above optimization. */
5462: /* Can do this if:
5463: all registers modified are induction variables or invariant,
5464: all memory references have non-overlapping addresses
5465: (obviously true if only one write)
5466: allow 2 insns for the compare/jump at the end of the loop. */
5467: int num_nonfixed_reads = 0;
5468: /* 1 if the iteration var is used only to count iterations. */
5469: int no_use_except_counting = 0;
5470:
5471: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5472: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5473: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
5474:
5475: if (bl->giv_count == 0
5476: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
5477: {
5478: rtx bivreg = regno_reg_rtx[bl->regno];
5479:
5480: /* If there are no givs for this biv, and the only exit is the
5481: fall through at the end of the the loop, then
5482: see if perhaps there are no uses except to count. */
5483: no_use_except_counting = 1;
5484: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5485: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5486: {
5487: rtx set = single_set (p);
5488:
5489: if (set && GET_CODE (SET_DEST (set)) == REG
5490: && REGNO (SET_DEST (set)) == bl->regno)
5491: /* An insn that sets the biv is okay. */
5492: ;
5493: else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
5494: || p == prev_nonnote_insn (loop_end))
5495: /* Don't bother about the end test. */
5496: ;
5497: else if (reg_mentioned_p (bivreg, PATTERN (p)))
5498: /* Any other use of the biv is no good. */
5499: {
5500: no_use_except_counting = 0;
5501: break;
5502: }
5503: }
5504: }
5505:
5506: /* This code only acts for innermost loops. Also it simplifies
5507: the memory address check by only reversing loops with
5508: zero or one memory access.
5509: Two memory accesses could involve parts of the same array,
5510: and that can't be reversed. */
5511:
5512: if (num_nonfixed_reads <= 1
5513: && !loop_has_call
5514: && (no_use_except_counting
5515: || (bl->giv_count + bl->biv_count + num_mem_sets
5516: + num_movables + 2 == insn_count)))
5517: {
5518: rtx condition = get_condition_for_loop (PREV_INSN (loop_end));
5519: int win;
5520: rtx tem;
5521:
5522: /* Loop can be reversed. */
5523: if (loop_dump_stream)
5524: fprintf (loop_dump_stream, "Can reverse loop\n");
5525:
5526: /* Now check other conditions:
5527: initial_value must be zero,
5528: final_value % add_val == 0, so that when reversed, the
5529: biv will be zero on the last iteration.
5530:
5531: This test can probably be improved since +/- 1 in the constant
5532: can be obtained by changing LT to LE and vice versa; this is
5533: confusing. */
5534:
5535: if (comparison && bl->initial_value == const0_rtx
5536: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5537: /* LE gets turned into LT */
5538: && GET_CODE (comparison) == LT
5539: && (INTVAL (XEXP (comparison, 1))
5540: % INTVAL (bl->biv->add_val)) == 0)
5541: {
5542: /* Register will always be nonnegative, with value
5543: 0 on last iteration if loop reversed */
5544:
5545: /* Save some info needed to produce the new insns. */
5546: reg = bl->biv->dest_reg;
5547: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
5548: new_add_val = gen_rtx (CONST_INT, VOIDmode,
5549: - INTVAL (bl->biv->add_val));
5550:
5551: final_value = XEXP (comparison, 1);
5552: start_value = gen_rtx (CONST_INT, VOIDmode,
5553: (INTVAL (XEXP (comparison, 1))
5554: - INTVAL (bl->biv->add_val)));
5555:
5556: /* Initialize biv to start_value before loop start.
5557: The old initializing insn will be deleted as a
5558: dead store by flow.c. */
5559: emit_insn_before (gen_move_insn (reg, start_value), loop_start);
5560:
5561: /* Add insn to decrement register, and delete insn
5562: that incremented the register. */
5563: p = emit_insn_before (gen_add2_insn (reg, new_add_val),
5564: bl->biv->insn);
5565: delete_insn (bl->biv->insn);
5566:
5567: /* Update biv info to reflect its new status. */
5568: bl->biv->insn = p;
5569: bl->initial_value = start_value;
5570: bl->biv->add_val = new_add_val;
5571:
5572: /* Inc LABEL_NUSES so that delete_insn will
5573: not delete the label. */
5574: LABEL_NUSES (XEXP (jump_label, 0)) ++;
5575:
5576: /* Emit an insn after the end of the loop to set the biv's
5577: proper exit value if it is used anywhere outside the loop. */
5578: if ((regno_last_uid[bl->regno]
5579: != INSN_UID (PREV_INSN (PREV_INSN (loop_end))))
5580: || ! bl->init_insn
5581: || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn))
5582: emit_insn_after (gen_move_insn (reg, final_value),
5583: loop_end);
5584:
5585: /* Delete compare/branch at end of loop. */
5586: delete_insn (PREV_INSN (loop_end));
5587: delete_insn (PREV_INSN (loop_end));
5588:
5589: /* Add new compare/branch insn at end of loop. */
5590: start_sequence ();
5591: emit_cmp_insn (reg, const0_rtx, GE, 0, GET_MODE (reg), 0, 0);
5592: emit_jump_insn (gen_bge (XEXP (jump_label, 0)));
5593: tem = gen_sequence ();
5594: end_sequence ();
5595: emit_jump_insn_before (tem, loop_end);
5596:
5597: for (tem = PREV_INSN (loop_end);
5598: tem && GET_CODE (tem) != JUMP_INSN; tem = PREV_INSN (tem))
5599: ;
5600: if (tem)
5601: {
5602: JUMP_LABEL (tem) = XEXP (jump_label, 0);
5603:
5604: /* Increment of LABEL_NUSES done above. */
5605: /* Register is now always nonnegative,
5606: so add REG_NONNEG note to the branch. */
5607: REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, 0,
5608: REG_NOTES (tem));
5609: }
5610:
5611: bl->nonneg = 1;
5612:
5613: /* Mark that this biv has been reversed. Each giv which depends
5614: on this biv, and which is also live past the end of the loop
5615: will have to be fixed up. */
5616:
5617: bl->reversed = 1;
5618:
5619: if (loop_dump_stream)
5620: fprintf (loop_dump_stream,
5621: "Reversed loop and added reg_nonneg\n");
5622:
5623: return 1;
5624: }
5625: }
5626: }
5627:
5628: return 0;
5629: }
5630:
5631: /* Verify whether the biv BL appears to be eliminable,
5632: based on the insns in the loop that refer to it.
5633: LOOP_START is the first insn of the loop, and END is the end insn.
5634:
5635: If ELIMINATE_P is non-zero, actually do the elimination.
5636:
5637: THRESHOLD and INSN_COUNT are from loop_optimize and are used to
5638: determine whether invariant insns should be placed inside or at the
5639: start of the loop. */
5640:
5641: static int
5642: maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
5643: struct iv_class *bl;
5644: rtx loop_start;
5645: rtx end;
5646: int eliminate_p;
5647: int threshold, insn_count;
5648: {
5649: rtx reg = bl->biv->dest_reg;
5650: rtx p, set;
5651: struct induction *v;
5652:
5653: /* Scan all insns in the loop, stopping if we find one that uses the
5654: biv in a way that we cannot eliminate. */
5655:
5656: for (p = loop_start; p != end; p = NEXT_INSN (p))
5657: {
5658: enum rtx_code code = GET_CODE (p);
5659: rtx where = threshold >= insn_count ? loop_start : p;
5660:
5661: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
5662: && reg_mentioned_p (reg, PATTERN (p))
5663: && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
5664: {
5665: if (loop_dump_stream)
5666: fprintf (loop_dump_stream,
5667: "Cannot eliminate biv %d: biv used in insn %d.\n",
5668: bl->regno, INSN_UID (p));
5669: break;
5670: }
5671: }
5672:
5673: if (p == end)
5674: {
5675: if (loop_dump_stream)
5676: fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
5677: bl->regno, eliminate_p ? "was" : "can be");
5678: return 1;
5679: }
5680:
5681: return 0;
5682: }
5683:
5684: /* If BL appears in X (part of the pattern of INSN), see if we can
5685: eliminate its use. If so, return 1. If not, return 0.
5686:
5687: If BIV does not appear in X, return 1.
5688:
5689: If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
5690: where extra insns should be added. Depending on how many items have been
5691: moved out of the loop, it will either be before INSN or at the start of
5692: the loop. */
5693:
5694: static int
5695: maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
5696: rtx x, insn;
5697: struct iv_class *bl;
5698: int eliminate_p;
5699: rtx where;
5700: {
5701: enum rtx_code code = GET_CODE (x);
5702: rtx reg = bl->biv->dest_reg;
5703: enum machine_mode mode = GET_MODE (reg);
5704: struct induction *v;
5705: rtx arg, new, tem;
5706: int arg_operand;
5707: char *fmt;
5708: int i, j;
5709:
5710: switch (code)
5711: {
5712: case REG:
5713: /* If we haven't already been able to do something with this BIV,
5714: we can't eliminate it. */
5715: if (x == reg)
5716: return 0;
5717: return 1;
5718:
5719: case SET:
5720: /* If this sets the BIV, it is not a problem. */
5721: if (SET_DEST (x) == reg)
5722: return 1;
5723:
5724: /* If this is an insn that defines a giv, it is also ok because
5725: it will go away when the giv is reduced. */
5726: for (v = bl->giv; v; v = v->next_iv)
5727: if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
5728: return 1;
5729:
5730: #ifdef HAVE_cc0
5731: if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
5732: {
5733: /* Can replace with any giv that was reduced and
5734: that has (MULT_VAL != 0) and (ADD_VAL == 0).
5735: Require a constant for MULT_VAL, so we know it's nonzero. */
5736:
5737: for (v = bl->giv; v; v = v->next_iv)
5738: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5739: && v->add_val == const0_rtx
5740: && ! v->ignore && ! v->maybe_dead
5741: && v->mode == mode)
5742: {
5743: if (! eliminate_p)
5744: return 1;
5745:
5746: /* If the giv has the opposite direction of change,
5747: then reverse the comparison. */
5748: if (INTVAL (v->mult_val) < 0)
5749: new = gen_rtx (COMPARE, GET_MODE (v->new_reg),
5750: const0_rtx, v->new_reg);
5751: else
5752: new = v->new_reg;
5753:
5754: /* We can probably test that giv's reduced reg. */
5755: if (validate_change (insn, &SET_SRC (x), new, 0))
5756: return 1;
5757: }
5758:
5759: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
5760: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
5761: Require a constant for MULT_VAL, so we know it's nonzero. */
5762:
5763: for (v = bl->giv; v; v = v->next_iv)
5764: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5765: && ! v->ignore && ! v->maybe_dead
5766: && v->mode == mode)
5767: {
5768: if (! eliminate_p)
5769: return 1;
5770:
5771: /* If the giv has the opposite direction of change,
5772: then reverse the comparison. */
5773: if (INTVAL (v->mult_val) < 0)
5774: new = gen_rtx (COMPARE, VOIDmode, copy_rtx (v->add_val),
5775: v->new_reg);
5776: else
5777: new = gen_rtx (COMPARE, VOIDmode, v->new_reg,
5778: copy_rtx (v->add_val));
5779:
5780: /* Replace biv with the giv's reduced register. */
5781: update_reg_last_use (v->add_val, insn);
5782: if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
5783: return 1;
5784:
5785: /* Insn doesn't support that constant or invariant. Copy it
5786: into a register (it will be a loop invariant.) */
5787: tem = gen_reg_rtx (GET_MODE (v->new_reg));
5788:
5789: emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
5790: where);
5791:
5792: if (validate_change (insn, &SET_SRC (PATTERN (insn)),
5793: gen_rtx (COMPARE, VOIDmode,
5794: v->new_reg, tem), 0))
5795: return 1;
5796: }
5797: }
5798: #endif
5799: break;
5800:
5801: case COMPARE:
5802: case EQ: case NE:
5803: case GT: case GE: case GTU: case GEU:
5804: case LT: case LE: case LTU: case LEU:
5805: /* See if either argument is the biv. */
5806: if (XEXP (x, 0) == reg)
5807: arg = XEXP (x, 1), arg_operand = 1;
5808: else if (XEXP (x, 1) == reg)
5809: arg = XEXP (x, 0), arg_operand = 0;
5810: else
5811: break;
5812:
5813: if (CONSTANT_P (arg))
5814: {
5815: /* First try to replace with any giv that has constant positive
5816: mult_val and constant add_val. We might be able to support
5817: negative mult_val, but it seems complex to do it in general. */
5818:
5819: for (v = bl->giv; v; v = v->next_iv)
5820: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
5821: && CONSTANT_P (v->add_val)
5822: && ! v->ignore && ! v->maybe_dead
5823: && v->mode == mode)
5824: {
5825: if (! eliminate_p)
5826: return 1;
5827:
5828: /* Replace biv with the giv's reduced reg. */
5829: XEXP (x, 1-arg_operand) = v->new_reg;
5830:
5831: /* If all constants are actually constant integers and
5832: the derived constant can be directly placed in the COMPARE,
5833: do so. */
5834: if (GET_CODE (arg) == CONST_INT
5835: && GET_CODE (v->mult_val) == CONST_INT
5836: && GET_CODE (v->add_val) == CONST_INT
5837: && validate_change (insn, &XEXP (x, arg_operand),
5838: gen_rtx (CONST_INT, VOIDmode,
5839: (INTVAL (arg)
5840: * INTVAL (v->mult_val)
5841: + INTVAL (v->add_val))), 0))
5842: return 1;
5843:
5844: /* Otherwise, load it into a register. */
5845: tem = gen_reg_rtx (mode);
5846: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
5847: if (validate_change (insn, &XEXP (x, arg_operand), tem, 0))
5848: return 1;
5849:
5850: /* If that failed, put back the change we made above. */
5851: XEXP (x, 1-arg_operand) = reg;
5852: }
5853:
5854: /* Look for giv with positive constant mult_val and nonconst add_val.
5855: Insert insns to calculate new compare value. */
5856:
5857: for (v = bl->giv; v; v = v->next_iv)
1.1.1.2 ! root 5858: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
1.1 root 5859: && ! v->ignore && ! v->maybe_dead
5860: && v->mode == mode)
5861: {
5862: rtx tem;
5863:
5864: if (! eliminate_p)
5865: return 1;
5866:
5867: tem = gen_reg_rtx (mode);
5868:
5869: /* Replace biv with giv's reduced register. */
5870: validate_change (insn, &XEXP (x, 1 - arg_operand),
5871: v->new_reg, 1);
5872:
5873: /* Compute value to compare against. */
5874: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
5875: /* Use it in this insn. */
5876: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
5877: if (apply_change_group ())
5878: return 1;
5879: }
5880: }
5881: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
5882: {
5883: if (invariant_p (arg) == 1)
5884: {
5885: /* Look for giv with constant positive mult_val and nonconst
5886: add_val. Insert insns to compute new compare value. */
5887:
5888: for (v = bl->giv; v; v = v->next_iv)
5889: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
5890: && ! v->ignore && ! v->maybe_dead
5891: && v->mode == mode)
5892: {
5893: rtx tem;
5894:
5895: if (! eliminate_p)
5896: return 1;
5897:
5898: tem = gen_reg_rtx (mode);
5899:
5900: /* Replace biv with giv's reduced register. */
5901: validate_change (insn, &XEXP (x, 1 - arg_operand),
5902: v->new_reg, 1);
5903:
5904: /* Compute value to compare against. */
5905: emit_iv_add_mult (arg, v->mult_val, v->add_val,
5906: tem, where);
5907: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
5908: if (apply_change_group ())
5909: return 1;
5910: }
5911: }
5912:
5913: /* This code has problems. Basically, you can't know when
5914: seeing if we will eliminate BL, whether a particular giv
5915: of ARG will be reduced. If it isn't going to be reduced,
5916: we can't eliminate BL. We can try forcing it to be reduced,
5917: but that can generate poor code.
5918:
5919: The problem is that the benefit of reducing TV, below should
5920: be increased if BL can actually be eliminated, but this means
5921: we might have to do a topological sort of the order in which
5922: we try to process biv. It doesn't seem worthwhile to do
5923: this sort of thing now. */
5924:
5925: #if 0
5926: /* Otherwise the reg compared with had better be a biv. */
5927: if (GET_CODE (arg) != REG
5928: || reg_iv_type[REGNO (arg)] != BASIC_INDUCT)
5929: return 0;
5930:
5931: /* Look for a pair of givs, one for each biv,
5932: with identical coefficients. */
5933: for (v = bl->giv; v; v = v->next_iv)
5934: {
5935: struct induction *tv;
5936:
5937: if (v->ignore || v->maybe_dead || v->mode != mode)
5938: continue;
5939:
5940: for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
5941: if (! tv->ignore && ! tv->maybe_dead
5942: && rtx_equal_p (tv->mult_val, v->mult_val)
5943: && rtx_equal_p (tv->add_val, v->add_val)
5944: && tv->mode == mode)
5945: {
5946: if (! eliminate_p)
5947: return 1;
5948:
5949: /* Replace biv with its giv's reduced reg. */
5950: XEXP (x, 1-arg_operand) = v->new_reg;
5951: /* Replace other operand with the other giv's
5952: reduced reg. */
5953: XEXP (x, arg_operand) = tv->new_reg;
5954: return 1;
5955: }
5956: }
5957: #endif
5958: }
5959:
5960: /* If we get here, the biv can't be eliminated. */
5961: return 0;
5962:
5963: case MEM:
5964: /* If this address is a DEST_ADDR giv, it doesn't matter if the
5965: biv is used in it, since it will be replaced. */
5966: for (v = bl->giv; v; v = v->next_iv)
5967: if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
5968: return 1;
5969: break;
5970: }
5971:
5972: /* See if any subexpression fails elimination. */
5973: fmt = GET_RTX_FORMAT (code);
5974: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5975: {
5976: switch (fmt[i])
5977: {
5978: case 'e':
5979: if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl,
5980: eliminate_p, where))
5981: return 0;
5982: break;
5983:
5984: case 'E':
5985: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5986: if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl,
5987: eliminate_p, where))
5988: return 0;
5989: break;
5990: }
5991: }
5992:
5993: return 1;
5994: }
5995:
5996: /* Return nonzero if the last use of REG
5997: is in an insn following INSN in the same basic block. */
5998:
5999: static int
6000: last_use_this_basic_block (reg, insn)
6001: rtx reg;
6002: rtx insn;
6003: {
6004: rtx n;
6005: for (n = insn;
6006: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
6007: n = NEXT_INSN (n))
6008: {
6009: if (regno_last_uid[REGNO (reg)] == INSN_UID (n))
6010: return 1;
6011: }
6012: return 0;
6013: }
6014:
6015: /* Called via `note_stores' to record the initial value of a biv. Here we
6016: just record the location of the set and process it later. */
6017:
6018: static void
6019: record_initial (dest, set)
6020: rtx dest;
6021: rtx set;
6022: {
6023: struct iv_class *bl;
6024:
6025: if (GET_CODE (dest) != REG
6026: || REGNO (dest) >= max_reg_before_loop
6027: || reg_iv_type[REGNO (dest)] != BASIC_INDUCT)
6028: return;
6029:
6030: bl = reg_biv_class[REGNO (dest)];
6031:
6032: /* If this is the first set found, record it. */
6033: if (bl->init_insn == 0)
6034: {
6035: bl->init_insn = note_insn;
6036: bl->init_set = set;
6037: }
6038: }
6039:
6040: /* If any of the registers in X are "old" and currently have a last use earlier
6041: than INSN, update them to have a last use of INSN. Their actual last use
6042: will be the previous insn but it will not have a valid uid_luid so we can't
6043: use it. */
6044:
6045: static void
6046: update_reg_last_use (x, insn)
6047: rtx x;
6048: rtx insn;
6049: {
6050: /* Check for the case where INSN does not have a valid luid. In this case,
6051: there is no need to modify the regno_last_uid, as this can only happen
6052: when code is inserted after the loop_end to set a pseudo's final value,
6053: and hence this insn will never be the last use of x. */
6054: if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
6055: && INSN_UID (insn) < max_uid_for_loop
6056: && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)])
6057: regno_last_uid[REGNO (x)] = INSN_UID (insn);
6058: else
6059: {
6060: register int i, j;
6061: register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
6062: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
6063: {
6064: if (fmt[i] == 'e')
6065: update_reg_last_use (XEXP (x, i), insn);
6066: else if (fmt[i] == 'E')
6067: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6068: update_reg_last_use (XVECEXP (x, i, j), insn);
6069: }
6070: }
6071: }
6072:
6073: /* Given a jump insn JUMP, return the condition that will cause it to branch
6074: to its JUMP_LABEL. If the condition cannot be understood, or is an
6075: inequality floating-point comparison which needs to be reversed, 0 will
6076: be returned.
6077:
6078: If EARLIEST is non-zero, it is a pointer to a place where the earliest
6079: insn used in locating the condition was found. If a replacement test
6080: of the condition is desired, it should be placed in front of that
6081: insn and we will be sure that the inputs are still valid.
6082:
6083: The condition will be returned in a canonical form to simplify testing by
6084: callers. Specifically:
6085:
6086: (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
6087: (2) Both operands will be machine operands; (cc0) will have been replaced.
6088: (3) If an operand is a constant, it will be the second operand.
6089: (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
6090: for GE, GEU, and LEU. */
6091:
6092: rtx
6093: get_condition (jump, earliest)
6094: rtx jump;
6095: rtx *earliest;
6096: {
6097: enum rtx_code code;
6098: rtx prev = jump;
6099: rtx set;
6100: rtx tem;
6101: rtx op0, op1;
6102: int reverse_code = 0;
6103: int did_reverse_condition = 0;
6104:
6105: /* If this is not a standard conditional jump, we can't parse it. */
6106: if (GET_CODE (jump) != JUMP_INSN
6107: || ! condjump_p (jump) || simplejump_p (jump))
6108: return 0;
6109:
6110: code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0));
6111: op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0);
6112: op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1);
6113:
6114: if (earliest)
6115: *earliest = jump;
6116:
6117: /* If this branches to JUMP_LABEL when the condition is false, reverse
6118: the condition. */
6119: if (XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump))
6120: code = reverse_condition (code), did_reverse_condition ^= 1;
6121:
6122: /* If we are comparing a register with zero, see if the register is set
6123: in the previous insn to a COMPARE or a comparison operation. Perform
6124: the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
6125: in cse.c */
6126:
6127: while (GET_RTX_CLASS (code) == '<' && op1 == const0_rtx)
6128: {
6129: /* Set non-zero when we find something of interest. */
6130: rtx x = 0;
6131:
6132: #ifdef HAVE_cc0
6133: /* If comparison with cc0, import actual comparison from compare
6134: insn. */
6135: if (op0 == cc0_rtx)
6136: {
6137: if ((prev = prev_nonnote_insn (prev)) == 0
6138: || GET_CODE (prev) != INSN
6139: || (set = single_set (prev)) == 0
6140: || SET_DEST (set) != cc0_rtx)
6141: return 0;
6142:
6143: op0 = SET_SRC (set);
6144: op1 = CONST0_RTX (GET_MODE (op0));
6145: if (earliest)
6146: *earliest = prev;
6147: }
6148: #endif
6149:
6150: /* If this is a COMPARE, pick up the two things being compared. */
6151: if (GET_CODE (op0) == COMPARE)
6152: {
6153: op1 = XEXP (op0, 1);
6154: op0 = XEXP (op0, 0);
6155: continue;
6156: }
6157: else if (GET_CODE (op0) != REG)
6158: break;
6159:
6160: /* Go back to the previous insn. Stop if it is not an INSN. We also
6161: stop if it isn't a single set or if it has a REG_INC note because
6162: we don't want to bother dealing with it. */
6163:
6164: if ((prev = prev_nonnote_insn (prev)) == 0
6165: || GET_CODE (prev) != INSN
6166: || FIND_REG_INC_NOTE (prev, 0)
6167: || (set = single_set (prev)) == 0)
6168: break;
6169:
6170: /* If this is setting OP0, get what it sets it to if it looks
6171: relevant. */
6172: if (SET_DEST (set) == op0)
6173: {
6174: enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
6175:
6176: if ((GET_CODE (SET_SRC (set)) == COMPARE
6177: || ((code == NE
6178: || (code == LT
6179: && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
6180: && (STORE_FLAG_VALUE
6181: & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
6182: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')))
6183: x = SET_SRC (set);
6184: else if ((code == EQ
6185: || (code == GE
6186: && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
6187: && (STORE_FLAG_VALUE
6188: & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
6189: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')
6190: {
6191: /* We might have reversed a LT to get a GE here. But this wasn't
6192: actually the comparison of data, so we don't flag that we
6193: have had to reverse the condition. */
6194: did_reverse_condition ^= 1;
6195: reverse_code = 1;
6196: x = SET_SRC (set);
6197: }
6198: }
6199:
6200: else if (reg_set_p (op0, prev))
6201: /* If this sets OP0, but not directly, we have to give up. */
6202: break;
6203:
6204: if (x)
6205: {
6206: if (GET_RTX_CLASS (GET_CODE (x)) == '<')
6207: code = GET_CODE (x);
6208: if (reverse_code)
6209: {
6210: code = reverse_condition (code);
6211: did_reverse_condition ^= 1;
6212: reverse_code = 0;
6213: }
6214:
6215: op0 = XEXP (x, 0), op1 = XEXP (x, 1);
6216: if (earliest)
6217: *earliest = prev;
6218: }
6219: }
6220:
6221: /* If constant is first, put it last. */
6222: if (CONSTANT_P (op0))
6223: code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
6224:
6225: /* If OP0 is the result of a comparison, we weren't able to find what
6226: was really being compared, so fail. */
6227: if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
6228: return 0;
6229:
6230: /* Canonicalize any ordered comparison with integers involving equality. */
6231: if (GET_CODE (op1) == CONST_INT)
6232: {
6233: int const_val = INTVAL (op1);
6234: unsigned uconst_val = (unsigned) const_val;
6235:
6236: switch (code)
6237: {
6238: case LE:
6239: code = LT;
6240: op1 = gen_rtx (CONST_INT, VOIDmode, const_val + 1);
6241: break;
6242:
6243: case GE:
6244: code = GT;
6245: op1 = gen_rtx (CONST_INT, VOIDmode, const_val - 1);
6246: break;
6247:
6248: case LEU:
6249: code = LTU;
6250: op1 = gen_rtx (CONST_INT, VOIDmode, uconst_val + 1);
6251: break;
6252:
6253: case GEU:
6254: code = GTU;
6255: op1 = gen_rtx (CONST_INT, VOIDmode, uconst_val - 1);
6256: break;
6257: }
6258: }
6259:
6260: /* If this was floating-point and we reversed anything other than an
6261: EQ or NE, return zero. */
6262: if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
6263: && did_reverse_condition && code != NE && code != EQ
6264: && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
6265: return 0;
6266:
6267: #ifdef HAVE_cc0
6268: /* Never return CC0; return zero instead. */
6269: if (op0 == cc0_rtx)
6270: return 0;
6271: #endif
6272:
6273: return gen_rtx (code, VOIDmode, op0, op1);
6274: }
6275:
6276: /* Similar to above routine, except that we also put an invariant last
6277: unless both operands are invariants. */
6278:
6279: rtx
6280: get_condition_for_loop (x)
6281: rtx x;
6282: {
6283: rtx comparison = get_condition (x, 0);
6284:
6285: if (comparison == 0
6286: || ! invariant_p (XEXP (comparison, 0))
6287: || invariant_p (XEXP (comparison, 1)))
6288: return comparison;
6289:
6290: return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode,
6291: XEXP (comparison, 1), XEXP (comparison, 0));
6292: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.