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