![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to loop.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to loop.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Move constant computations out of loops.
1.1.1.4 root 2: Copyright (C) 1987, 1988, 1989, 1991, 1992 Free Software Foundation, Inc.
1.1 root 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:
1.1.1.4 root 36: #include <stdio.h>
1.1 root 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.
1.1.1.2 root 51: The luids are like uids but increase monotonically always.
1.1 root 52: We use them to see whether a jump comes from outside a given loop. */
53:
54: int *uid_luid;
55:
56: /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
57: number the insn is contained in. */
58:
59: int *uid_loop_num;
60:
61: /* 1 + largest uid of any insn. */
62:
63: int max_uid_for_loop;
64:
65: /* 1 + luid of last insn. */
66:
67: static int max_luid;
68:
69: /* Number of loops detected in current function. Used as index to the
70: next few tables. */
71:
72: static int max_loop_num;
73:
74: /* Indexed by loop number, contains the first and last insn of each loop. */
75:
76: static rtx *loop_number_loop_starts, *loop_number_loop_ends;
77:
78: /* For each loop, gives the containing loop number, -1 if none. */
79:
80: int *loop_outer_loop;
81:
82: /* Indexed by loop number, contains a nonzero value if the "loop" isn't
83: really a loop (an insn outside the loop branches into it). */
84:
85: static char *loop_invalid;
86:
87: /* Indexed by loop number, links together all LABEL_REFs which refer to
88: code labels outside the loop. Used by routines that need to know all
89: loop exits, such as final_biv_value and final_giv_value.
90:
91: This does not include loop exits due to return instructions. This is
92: because all bivs and givs are pseudos, and hence must be dead after a
93: return, so the presense of a return does not affect any of the
94: optimizations that use this info. It is simpler to just not include return
95: instructions on this list. */
96:
97: rtx *loop_number_exit_labels;
98:
99: /* Holds the number of loop iterations. It is zero if the number could not be
1.1.1.4 root 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. */
1.1 root 104:
1.1.1.4 root 105: unsigned HOST_WIDE_INT loop_n_iterations;
1.1 root 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:
1.1.1.3 root 112: /* Nonzero if there is a volatile memory reference in the current
113: loop. */
114:
115: static int loop_has_volatile;
116:
1.1 root 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
1.1.1.3 root 127: we know is equal to a constant and -1 means that it is an candidate
1.1 root 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.
1.1.1.3 root 163: This happens if the loop contains a call (in which case `loop_has_call'
1.1 root 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);
1.1.1.4 root 299: rtx reg = gen_rtx (REG, word_mode, 0);
300: rtx pow2 = GEN_INT (32);
1.1 root 301: rtx lea;
302: int i;
303:
1.1.1.4 root 304: add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);
1.1 root 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. */
1.1.1.4 root 309:
1.1 root 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. */
1.1.1.4 root 363: max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
1.1 root 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:
1.1.1.4 root 388: /* See if we went too far. */
389: if (get_max_uid () > max_uid_for_loop)
390: abort ();
391:
1.1 root 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)
1.1.1.4 root 428: find_loop_tree_blocks ();
1.1 root 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 ());
1.1.1.4 root 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 ();
1.1 root 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'
1.1.1.4 root 635: && find_reg_note (p, REG_LIBCALL, NULL_RTX))
1.1 root 636: in_libcall = 1;
637: else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
1.1.1.4 root 638: && find_reg_note (p, REG_RETVAL, NULL_RTX))
1.1 root 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. */
1.1.1.4 root 660: temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
1.1 root 661: if (temp)
662: src = XEXP (temp, 0), move_insn = 1;
663: else
664: {
1.1.1.4 root 665: temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
1.1 root 666: if (temp && CONSTANT_P (XEXP (temp, 0)))
667: src = XEXP (temp, 0), move_insn = 1;
1.1.1.4 root 668: if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
1.1 root 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
1.1.1.5 ! root 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).
1.1 root 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))
1.1.1.5 ! root 693: || (! REG_USERVAR_P (SET_DEST (PATTERN (p)))
! 694: && ! REG_LOOP_TEST_P (SET_DEST (PATTERN (p))))
1.1 root 695: || reg_in_basic_block_p (p, SET_DEST (PATTERN (p)))))
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))
1.1.1.4 root 737: && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
1.1 root 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;
1.1.1.4 root 774: m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
1.1 root 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];
1.1.1.4 root 786: if (find_reg_note (p, REG_RETVAL, NULL_RTX))
1.1 root 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_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. */
1.1.1.4 root 808: temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
1.1 root 809: if (temp)
810: m->set_src = XEXP (temp, 0), m->move_insn = 1;
811: else
812: {
1.1.1.4 root 813: temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
1.1 root 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: }
1.1.1.4 root 820: m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
1.1 root 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: {
1.1.1.4 root 1026: rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1.1 root 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:
1.1.1.4 root 1101: for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1.1 root 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
1.1.1.4 root 1131: && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1.1 root 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? */
1.1.1.4 root 1155: rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1.1 root 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: {
1.1.1.4 root 1419: case 'w':
1420: if (XWINT (x, i) != XWINT (y, i))
1421: return 0;
1422: break;
1423:
1.1 root 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:
1.1.1.2 root 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);
1.1.1.3 root 1476: int i, j;
1.1.1.2 root 1477: char *fmt;
1478: rtx insn;
1479:
1.1.1.4 root 1480: if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
1.1.1.2 root 1481: {
1.1.1.5 ! root 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: }
1.1.1.2 root 1497: return;
1498: }
1499:
1500: fmt = GET_RTX_FORMAT (code);
1501: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1.1.1.3 root 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: }
1.1.1.2 root 1509: }
1510:
1.1 root 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
1.1.1.4 root 1669: && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1.1 root 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
1.1.1.4 root 1676: && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1.1 root 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);
1.1.1.2 root 1688: temp = get_insns ();
1.1 root 1689: end_sequence ();
1690:
1.1.1.2 root 1691: add_label_notes (m->set_src, temp);
1692:
1693: i1 = emit_insns_before (temp, loop_start);
1.1.1.4 root 1694: if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
1.1 root 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
1.1.1.4 root 1716: && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1.1 root 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
1.1.1.4 root 1723: && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
1.1 root 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
1.1.1.4 root 1765: && (n = find_reg_note (temp, REG_EQUAL,
1766: NULL_RTX)))
1.1 root 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
1.1.1.4 root 1779: && reg_referenced_p (fn_reg, body))
1.1 root 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,
1.1.1.4 root 1808: GEN_INT ((((HOST_WIDE_INT) 1
1809: << GET_MODE_BITSIZE (m->savemode)))
1.1 root 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:
1.1.1.5 ! root 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:
1.1 root 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. */
1.1.1.4 root 1860: if (temp = find_reg_note (i1, REG_RETVAL, NULL_RTX))
1.1 root 1861: {
1862: XEXP (temp, 0) = first;
1.1.1.4 root 1863: temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
1.1 root 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 */
1.1.1.4 root 1926: if (temp = find_reg_note (m1->insn, REG_RETVAL,
1927: NULL_RTX))
1.1 root 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);
1.1.1.5 ! root 1966: INSN_CODE (p) = -1;
1.1 root 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',
1.1.1.3 root 2122: `num_mem_sets', `loop_continue', loops_enclosed', `loop_has_call',
2123: and `loop_has_volatile'.
1.1 root 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;
1.1.1.3 root 2135: loop_has_volatile = 0;
1.1 root 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)
1.1.1.3 root 2176: {
2177: if (volatile_refs_p (PATTERN (insn)))
2178: loop_has_volatile = 1;
2179:
2180: note_stores (PATTERN (insn), note_addr_stored);
2181: }
1.1 root 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: {
1.1.1.5 ! root 2194: rtx insn, label;
1.1 root 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:
1.1.1.5 ! root 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.
1.1 root 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))
1.1.1.5 ! root 2276: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1.1 root 2277: {
2278: int this_loop_num = uid_loop_num[INSN_UID (insn)];
2279:
1.1.1.5 ! root 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:
1.1 root 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))]
1.1.1.4 root 2304: != this_loop_num)))
2305: && get_max_uid () < max_uid_for_loop)
1.1 root 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
1.1.1.4 root 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)
1.1 root 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. */
1.1.1.4 root 2364: if (invert_jump (p, new_label))
1.1 root 2365: {
2366: rtx q, r;
2367:
2368: /* Include the BARRIER after INSN and copy the
2369: block after LOC. */
1.1.1.3 root 2370: new_label = squeeze_notes (new_label, NEXT_INSN (insn));
1.1 root 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: }
2428: }
2429: }
2430: }
2431:
2432: /* If any label in X jumps to a loop different from LOOP_NUM and any of the
2433: loops it is contained in, mark the target loop invalid.
2434:
2435: For speed, we assume that X is part of a pattern of a JUMP_INSN. */
2436:
2437: static void
2438: mark_loop_jump (x, loop_num)
2439: rtx x;
2440: int loop_num;
2441: {
2442: int dest_loop;
2443: int outer_loop;
2444: int i;
2445:
2446: switch (GET_CODE (x))
2447: {
2448: case PC:
2449: case USE:
2450: case CLOBBER:
2451: case REG:
2452: case MEM:
2453: case CONST_INT:
2454: case CONST_DOUBLE:
2455: case RETURN:
2456: return;
2457:
2458: case CONST:
2459: /* There could be a label reference in here. */
2460: mark_loop_jump (XEXP (x, 0), loop_num);
2461: return;
2462:
2463: case PLUS:
2464: case MINUS:
2465: case MULT:
2466: case LSHIFT:
2467: mark_loop_jump (XEXP (x, 0), loop_num);
2468: mark_loop_jump (XEXP (x, 1), loop_num);
2469: return;
2470:
2471: case SIGN_EXTEND:
2472: case ZERO_EXTEND:
2473: mark_loop_jump (XEXP (x, 0), loop_num);
2474: return;
2475:
2476: case LABEL_REF:
2477: dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))];
2478:
2479: /* Link together all labels that branch outside the loop. This
2480: is used by final_[bg]iv_value and the loop unrolling code. Also
2481: mark this LABEL_REF so we know that this branch should predict
2482: false. */
2483:
2484: if (dest_loop != loop_num && loop_num != -1)
2485: {
2486: LABEL_OUTSIDE_LOOP_P (x) = 1;
2487: LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
2488: loop_number_exit_labels[loop_num] = x;
2489: }
2490:
2491: /* If this is inside a loop, but not in the current loop or one enclosed
2492: by it, it invalidates at least one loop. */
2493:
2494: if (dest_loop == -1)
2495: return;
2496:
2497: /* We must invalidate every nested loop containing the target of this
2498: label, except those that also contain the jump insn. */
2499:
2500: for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
2501: {
2502: /* Stop when we reach a loop that also contains the jump insn. */
2503: for (outer_loop = loop_num; outer_loop != -1;
2504: outer_loop = loop_outer_loop[outer_loop])
2505: if (dest_loop == outer_loop)
2506: return;
2507:
2508: /* If we get here, we know we need to invalidate a loop. */
2509: if (loop_dump_stream && ! loop_invalid[dest_loop])
2510: fprintf (loop_dump_stream,
2511: "\nLoop at %d ignored due to multiple entry points.\n",
2512: INSN_UID (loop_number_loop_starts[dest_loop]));
2513:
2514: loop_invalid[dest_loop] = 1;
2515: }
2516: return;
2517:
2518: case SET:
2519: /* If this is not setting pc, ignore. */
2520: if (SET_DEST (x) == pc_rtx)
2521: mark_loop_jump (SET_SRC (x), loop_num);
2522: return;
2523:
2524: case IF_THEN_ELSE:
2525: mark_loop_jump (XEXP (x, 1), loop_num);
2526: mark_loop_jump (XEXP (x, 2), loop_num);
2527: return;
2528:
2529: case PARALLEL:
2530: case ADDR_VEC:
2531: for (i = 0; i < XVECLEN (x, 0); i++)
2532: mark_loop_jump (XVECEXP (x, 0, i), loop_num);
2533: return;
2534:
2535: case ADDR_DIFF_VEC:
2536: for (i = 0; i < XVECLEN (x, 1); i++)
2537: mark_loop_jump (XVECEXP (x, 1, i), loop_num);
2538: return;
2539:
2540: default:
2541: /* Nothing else should occur in a JUMP_INSN. */
2542: abort ();
2543: }
2544: }
2545:
2546: /* Return nonzero if there is a label in the range from
2547: insn INSN to and including the insn whose luid is END
2548: INSN must have an assigned luid (i.e., it must not have
2549: been previously created by loop.c). */
2550:
2551: static int
2552: labels_in_range_p (insn, end)
2553: rtx insn;
2554: int end;
2555: {
2556: while (insn && INSN_LUID (insn) <= end)
2557: {
2558: if (GET_CODE (insn) == CODE_LABEL)
2559: return 1;
2560: insn = NEXT_INSN (insn);
2561: }
2562:
2563: return 0;
2564: }
2565:
2566: /* Record that a memory reference X is being set. */
2567:
2568: static void
2569: note_addr_stored (x)
2570: rtx x;
2571: {
2572: register int i;
2573:
2574: if (x == 0 || GET_CODE (x) != MEM)
2575: return;
2576:
2577: /* Count number of memory writes.
2578: This affects heuristics in strength_reduce. */
2579: num_mem_sets++;
2580:
2581: if (unknown_address_altered)
2582: return;
2583:
2584: for (i = 0; i < loop_store_mems_idx; i++)
2585: if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0))
2586: && MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
2587: {
2588: /* We are storing at the same address as previously noted. Save the
2589: wider reference, treating BLKmode as wider. */
2590: if (GET_MODE (x) == BLKmode
2591: || (GET_MODE_SIZE (GET_MODE (x))
2592: > GET_MODE_SIZE (GET_MODE (loop_store_mems[i]))))
2593: loop_store_mems[i] = x;
2594: break;
2595: }
2596:
2597: if (i == NUM_STORES)
2598: unknown_address_altered = 1;
2599:
2600: else if (i == loop_store_mems_idx)
2601: loop_store_mems[loop_store_mems_idx++] = x;
2602: }
2603:
2604: /* Return nonzero if the rtx X is invariant over the current loop.
2605:
2606: The value is 2 if we refer to something only conditionally invariant.
2607:
2608: If `unknown_address_altered' is nonzero, no memory ref is invariant.
2609: Otherwise, a memory ref is invariant if it does not conflict with
2610: anything stored in `loop_store_mems'. */
2611:
2612: int
2613: invariant_p (x)
2614: register rtx x;
2615: {
2616: register int i;
2617: register enum rtx_code code;
2618: register char *fmt;
2619: int conditional = 0;
2620:
2621: if (x == 0)
2622: return 1;
2623: code = GET_CODE (x);
2624: switch (code)
2625: {
2626: case CONST_INT:
2627: case CONST_DOUBLE:
2628: case SYMBOL_REF:
2629: case CONST:
2630: return 1;
2631:
2632: case LABEL_REF:
2633: /* A LABEL_REF is normally invariant, however, if we are unrolling
2634: loops, and this label is inside the loop, then it isn't invariant.
2635: This is because each unrolled copy of the loop body will have
2636: a copy of this label. If this was invariant, then an insn loading
2637: the address of this label into a register might get moved outside
2638: the loop, and then each loop body would end up using the same label.
2639:
2640: We don't know the loop bounds here though, so just fail for all
2641: labels. */
2642: if (flag_unroll_loops)
2643: return 0;
2644: else
2645: return 1;
2646:
2647: case PC:
2648: case CC0:
2649: case UNSPEC_VOLATILE:
2650: return 0;
2651:
2652: case REG:
2653: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
2654: since the reg might be set by initialization within the loop. */
2655: if (x == frame_pointer_rtx || x == arg_pointer_rtx)
2656: return 1;
2657: if (loop_has_call
2658: && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
2659: return 0;
2660: if (n_times_set[REGNO (x)] < 0)
2661: return 2;
2662: return n_times_set[REGNO (x)] == 0;
2663:
2664: case MEM:
2665: /* Read-only items (such as constants in a constant pool) are
2666: invariant if their address is. */
2667: if (RTX_UNCHANGING_P (x))
2668: break;
2669:
2670: /* If we filled the table (or had a subroutine call), any location
2671: in memory could have been clobbered. */
2672: if (unknown_address_altered
2673: /* Don't mess with volatile memory references. */
2674: || MEM_VOLATILE_P (x))
2675: return 0;
2676:
2677: /* See if there is any dependence between a store and this load. */
2678: for (i = loop_store_mems_idx - 1; i >= 0; i--)
2679: if (true_dependence (loop_store_mems[i], x))
2680: return 0;
2681:
2682: /* It's not invalidated by a store in memory
2683: but we must still verify the address is invariant. */
2684: break;
2685:
2686: case ASM_OPERANDS:
2687: /* Don't mess with insns declared volatile. */
2688: if (MEM_VOLATILE_P (x))
2689: return 0;
2690: }
2691:
2692: fmt = GET_RTX_FORMAT (code);
2693: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2694: {
2695: if (fmt[i] == 'e')
2696: {
2697: int tem = invariant_p (XEXP (x, i));
2698: if (tem == 0)
2699: return 0;
2700: if (tem == 2)
2701: conditional = 1;
2702: }
2703: else if (fmt[i] == 'E')
2704: {
2705: register int j;
2706: for (j = 0; j < XVECLEN (x, i); j++)
2707: {
2708: int tem = invariant_p (XVECEXP (x, i, j));
2709: if (tem == 0)
2710: return 0;
2711: if (tem == 2)
2712: conditional = 1;
2713: }
2714:
2715: }
2716: }
2717:
2718: return 1 + conditional;
2719: }
2720:
2721:
2722: /* Return nonzero if all the insns in the loop that set REG
2723: are INSN and the immediately following insns,
2724: and if each of those insns sets REG in an invariant way
2725: (not counting uses of REG in them).
2726:
2727: The value is 2 if some of these insns are only conditionally invariant.
2728:
2729: We assume that INSN itself is the first set of REG
2730: and that its source is invariant. */
2731:
2732: static int
2733: consec_sets_invariant_p (reg, n_sets, insn)
2734: int n_sets;
2735: rtx reg, insn;
2736: {
2737: register rtx p = insn;
2738: register int regno = REGNO (reg);
2739: rtx temp;
2740: /* Number of sets we have to insist on finding after INSN. */
2741: int count = n_sets - 1;
2742: int old = n_times_set[regno];
2743: int value = 0;
2744: int this;
2745:
2746: /* If N_SETS hit the limit, we can't rely on its value. */
2747: if (n_sets == 127)
2748: return 0;
2749:
2750: n_times_set[regno] = 0;
2751:
2752: while (count > 0)
2753: {
2754: register enum rtx_code code;
2755: rtx set;
2756:
2757: p = NEXT_INSN (p);
2758: code = GET_CODE (p);
2759:
2760: /* If library call, skip to end of of it. */
1.1.1.4 root 2761: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1.1 root 2762: p = XEXP (temp, 0);
2763:
2764: this = 0;
2765: if (code == INSN
2766: && (set = single_set (p))
2767: && GET_CODE (SET_DEST (set)) == REG
2768: && REGNO (SET_DEST (set)) == regno)
2769: {
2770: this = invariant_p (SET_SRC (set));
2771: if (this != 0)
2772: value |= this;
1.1.1.4 root 2773: else if (temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
1.1 root 2774: {
1.1.1.5 ! root 2775: /* If this is a libcall, then any invariant REG_EQUAL note is OK.
! 2776: If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
! 2777: notes are OK. */
! 2778: this = (CONSTANT_P (XEXP (temp, 0))
! 2779: || (find_reg_note (p, REG_RETVAL, NULL_RTX)
! 2780: && invariant_p (XEXP (temp, 0))));
1.1 root 2781: if (this != 0)
2782: value |= this;
2783: }
2784: }
2785: if (this != 0)
2786: count--;
2787: else if (code != NOTE)
2788: {
2789: n_times_set[regno] = old;
2790: return 0;
2791: }
2792: }
2793:
2794: n_times_set[regno] = old;
2795: /* If invariant_p ever returned 2, we return 2. */
2796: return 1 + (value & 2);
2797: }
2798:
2799: #if 0
2800: /* I don't think this condition is sufficient to allow INSN
2801: to be moved, so we no longer test it. */
2802:
2803: /* Return 1 if all insns in the basic block of INSN and following INSN
2804: that set REG are invariant according to TABLE. */
2805:
2806: static int
2807: all_sets_invariant_p (reg, insn, table)
2808: rtx reg, insn;
2809: short *table;
2810: {
2811: register rtx p = insn;
2812: register int regno = REGNO (reg);
2813:
2814: while (1)
2815: {
2816: register enum rtx_code code;
2817: p = NEXT_INSN (p);
2818: code = GET_CODE (p);
2819: if (code == CODE_LABEL || code == JUMP_INSN)
2820: return 1;
2821: if (code == INSN && GET_CODE (PATTERN (p)) == SET
2822: && GET_CODE (SET_DEST (PATTERN (p))) == REG
2823: && REGNO (SET_DEST (PATTERN (p))) == regno)
2824: {
2825: if (!invariant_p (SET_SRC (PATTERN (p)), table))
2826: return 0;
2827: }
2828: }
2829: }
2830: #endif /* 0 */
2831:
2832: /* Look at all uses (not sets) of registers in X. For each, if it is
2833: the single use, set USAGE[REGNO] to INSN; if there was a previous use in
2834: a different insn, set USAGE[REGNO] to const0_rtx. */
2835:
2836: static void
2837: find_single_use_in_loop (insn, x, usage)
2838: rtx insn;
2839: rtx x;
2840: rtx *usage;
2841: {
2842: enum rtx_code code = GET_CODE (x);
2843: char *fmt = GET_RTX_FORMAT (code);
2844: int i, j;
2845:
2846: if (code == REG)
2847: usage[REGNO (x)]
2848: = (usage[REGNO (x)] != 0 && usage[REGNO (x)] != insn)
2849: ? const0_rtx : insn;
2850:
2851: else if (code == SET)
2852: {
2853: /* Don't count SET_DEST if it is a REG; otherwise count things
2854: in SET_DEST because if a register is partially modified, it won't
2855: show up as a potential movable so we don't care how USAGE is set
2856: for it. */
2857: if (GET_CODE (SET_DEST (x)) != REG)
2858: find_single_use_in_loop (insn, SET_DEST (x), usage);
2859: find_single_use_in_loop (insn, SET_SRC (x), usage);
2860: }
2861: else
2862: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2863: {
2864: if (fmt[i] == 'e' && XEXP (x, i) != 0)
2865: find_single_use_in_loop (insn, XEXP (x, i), usage);
2866: else if (fmt[i] == 'E')
2867: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2868: find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
2869: }
2870: }
2871:
2872: /* Increment N_TIMES_SET at the index of each register
2873: that is modified by an insn between FROM and TO.
2874: If the value of an element of N_TIMES_SET becomes 127 or more,
2875: stop incrementing it, to avoid overflow.
2876:
2877: Store in SINGLE_USAGE[I] the single insn in which register I is
2878: used, if it is only used once. Otherwise, it is set to 0 (for no
2879: uses) or const0_rtx for more than one use. This parameter may be zero,
2880: in which case this processing is not done.
2881:
2882: Store in *COUNT_PTR the number of actual instruction
2883: in the loop. We use this to decide what is worth moving out. */
2884:
2885: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
2886: In that case, it is the insn that last set reg n. */
2887:
2888: static void
2889: count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
2890: register rtx from, to;
2891: char *may_not_move;
2892: rtx *single_usage;
2893: int *count_ptr;
2894: int nregs;
2895: {
2896: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
2897: register rtx insn;
2898: register int count = 0;
2899: register rtx dest;
2900:
2901: bzero (last_set, nregs * sizeof (rtx));
2902: for (insn = from; insn != to; insn = NEXT_INSN (insn))
2903: {
2904: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2905: {
2906: ++count;
2907:
2908: /* If requested, record registers that have exactly one use. */
2909: if (single_usage)
2910: {
2911: find_single_use_in_loop (insn, PATTERN (insn), single_usage);
2912:
2913: /* Include uses in REG_EQUAL notes. */
2914: if (REG_NOTES (insn))
2915: find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
2916: }
2917:
2918: if (GET_CODE (PATTERN (insn)) == CLOBBER
2919: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
2920: /* Don't move a reg that has an explicit clobber.
2921: We might do so sometimes, but it's not worth the pain. */
2922: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
2923:
2924: if (GET_CODE (PATTERN (insn)) == SET
2925: || GET_CODE (PATTERN (insn)) == CLOBBER)
2926: {
2927: dest = SET_DEST (PATTERN (insn));
2928: while (GET_CODE (dest) == SUBREG
2929: || GET_CODE (dest) == ZERO_EXTRACT
2930: || GET_CODE (dest) == SIGN_EXTRACT
2931: || GET_CODE (dest) == STRICT_LOW_PART)
2932: dest = XEXP (dest, 0);
2933: if (GET_CODE (dest) == REG)
2934: {
2935: register int regno = REGNO (dest);
2936: /* If this is the first setting of this reg
2937: in current basic block, and it was set before,
2938: it must be set in two basic blocks, so it cannot
2939: be moved out of the loop. */
2940: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2941: may_not_move[regno] = 1;
2942: /* If this is not first setting in current basic block,
2943: see if reg was used in between previous one and this.
2944: If so, neither one can be moved. */
2945: if (last_set[regno] != 0
2946: && reg_used_between_p (dest, last_set[regno], insn))
2947: may_not_move[regno] = 1;
2948: if (n_times_set[regno] < 127)
2949: ++n_times_set[regno];
2950: last_set[regno] = insn;
2951: }
2952: }
2953: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2954: {
2955: register int i;
2956: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2957: {
2958: register rtx x = XVECEXP (PATTERN (insn), 0, i);
2959: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
2960: /* Don't move a reg that has an explicit clobber.
2961: It's not worth the pain to try to do it correctly. */
2962: may_not_move[REGNO (XEXP (x, 0))] = 1;
2963:
2964: if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
2965: {
2966: dest = SET_DEST (x);
2967: while (GET_CODE (dest) == SUBREG
2968: || GET_CODE (dest) == ZERO_EXTRACT
2969: || GET_CODE (dest) == SIGN_EXTRACT
2970: || GET_CODE (dest) == STRICT_LOW_PART)
2971: dest = XEXP (dest, 0);
2972: if (GET_CODE (dest) == REG)
2973: {
2974: register int regno = REGNO (dest);
2975: if (n_times_set[regno] > 0 && last_set[regno] == 0)
2976: may_not_move[regno] = 1;
2977: if (last_set[regno] != 0
2978: && reg_used_between_p (dest, last_set[regno], insn))
2979: may_not_move[regno] = 1;
2980: if (n_times_set[regno] < 127)
2981: ++n_times_set[regno];
2982: last_set[regno] = insn;
2983: }
2984: }
2985: }
2986: }
2987: }
2988: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
2989: bzero (last_set, nregs * sizeof (rtx));
2990: }
2991: *count_ptr = count;
2992: }
2993:
2994: /* Given a loop that is bounded by LOOP_START and LOOP_END
2995: and that is entered at SCAN_START,
2996: return 1 if the register set in SET contained in insn INSN is used by
2997: any insn that precedes INSN in cyclic order starting
2998: from the loop entry point.
2999:
3000: We don't want to use INSN_LUID here because if we restrict INSN to those
3001: that have a valid INSN_LUID, it means we cannot move an invariant out
3002: from an inner loop past two loops. */
3003:
3004: static int
3005: loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
3006: rtx set, insn, loop_start, scan_start, loop_end;
3007: {
3008: rtx reg = SET_DEST (set);
3009: rtx p;
3010:
3011: /* Scan forward checking for register usage. If we hit INSN, we
3012: are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
3013: for (p = scan_start; p != insn; p = NEXT_INSN (p))
3014: {
3015: if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
3016: && reg_overlap_mentioned_p (reg, PATTERN (p)))
3017: return 1;
3018:
3019: if (p == loop_end)
3020: p = loop_start;
3021: }
3022:
3023: return 0;
3024: }
3025:
3026: /* A "basic induction variable" or biv is a pseudo reg that is set
3027: (within this loop) only by incrementing or decrementing it. */
3028: /* A "general induction variable" or giv is a pseudo reg whose
3029: value is a linear function of a biv. */
3030:
3031: /* Bivs are recognized by `basic_induction_var';
3032: Givs by `general_induct_var'. */
3033:
3034: /* Indexed by register number, indicates whether or not register is an
3035: induction variable, and if so what type. */
3036:
3037: enum iv_mode *reg_iv_type;
3038:
3039: /* Indexed by register number, contains pointer to `struct induction'
3040: if register is an induction variable. This holds general info for
3041: all induction variables. */
3042:
3043: struct induction **reg_iv_info;
3044:
3045: /* Indexed by register number, contains pointer to `struct iv_class'
3046: if register is a basic induction variable. This holds info describing
3047: the class (a related group) of induction variables that the biv belongs
3048: to. */
3049:
3050: struct iv_class **reg_biv_class;
3051:
3052: /* The head of a list which links together (via the next field)
3053: every iv class for the current loop. */
3054:
3055: struct iv_class *loop_iv_list;
3056:
3057: /* Communication with routines called via `note_stores'. */
3058:
3059: static rtx note_insn;
3060:
3061: /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */
3062:
3063: static rtx addr_placeholder;
3064:
3065: /* ??? Unfinished optimizations, and possible future optimizations,
3066: for the strength reduction code. */
3067:
3068: /* ??? There is one more optimization you might be interested in doing: to
3069: allocate pseudo registers for frequently-accessed memory locations.
3070: If the same memory location is referenced each time around, it might
3071: be possible to copy it into a register before and out after.
3072: This is especially useful when the memory location is a variable which
3073: is in a stack slot because somewhere its address is taken. If the
3074: loop doesn't contain a function call and the variable isn't volatile,
3075: it is safe to keep the value in a register for the duration of the
3076: loop. One tricky thing is that the copying of the value back from the
3077: register has to be done on all exits from the loop. You need to check that
3078: all the exits from the loop go to the same place. */
3079:
3080: /* ??? The interaction of biv elimination, and recognition of 'constant'
3081: bivs, may cause problems. */
3082:
3083: /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
3084: performance problems.
3085:
3086: Perhaps don't eliminate things that can be combined with an addressing
3087: mode. Find all givs that have the same biv, mult_val, and add_val;
3088: then for each giv, check to see if its only use dies in a following
3089: memory address. If so, generate a new memory address and check to see
3090: if it is valid. If it is valid, then store the modified memory address,
3091: otherwise, mark the giv as not done so that it will get its own iv. */
3092:
3093: /* ??? Could try to optimize branches when it is known that a biv is always
3094: positive. */
3095:
3096: /* ??? When replace a biv in a compare insn, we should replace with closest
3097: giv so that an optimized branch can still be recognized by the combiner,
3098: e.g. the VAX acb insn. */
3099:
3100: /* ??? Many of the checks involving uid_luid could be simplified if regscan
3101: was rerun in loop_optimize whenever a register was added or moved.
3102: Also, some of the optimizations could be a little less conservative. */
3103:
3104: /* Perform strength reduction and induction variable elimination. */
3105:
3106: /* Pseudo registers created during this function will be beyond the last
3107: valid index in several tables including n_times_set and regno_last_uid.
3108: This does not cause a problem here, because the added registers cannot be
3109: givs outside of their loop, and hence will never be reconsidered.
3110: But scan_loop must check regnos to make sure they are in bounds. */
3111:
3112: static void
3113: strength_reduce (scan_start, end, loop_top, insn_count,
3114: loop_start, loop_end)
3115: rtx scan_start;
3116: rtx end;
3117: rtx loop_top;
3118: int insn_count;
3119: rtx loop_start;
3120: rtx loop_end;
3121: {
3122: rtx p;
3123: rtx set;
3124: rtx inc_val;
3125: rtx mult_val;
3126: rtx dest_reg;
3127: /* This is 1 if current insn is not executed at least once for every loop
3128: iteration. */
3129: int not_every_iteration = 0;
1.1.1.3 root 3130: /* This is 1 if current insn may be executed more than once for every
3131: loop iteration. */
3132: int maybe_multiple = 0;
1.1 root 3133: /* Temporary list pointers for traversing loop_iv_list. */
3134: struct iv_class *bl, **backbl;
3135: /* Ratio of extra register life span we can justify
3136: for saving an instruction. More if loop doesn't call subroutines
3137: since in that case saving an insn makes more difference
3138: and more registers are available. */
3139: /* ??? could set this to last value of threshold in move_movables */
3140: int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
3141: /* Map of pseudo-register replacements. */
3142: rtx *reg_map;
3143: int call_seen;
3144: rtx test;
3145: rtx end_insert_before;
3146:
3147: reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop
3148: * sizeof (enum iv_mode *));
3149: bzero ((char *) reg_iv_type, max_reg_before_loop * sizeof (enum iv_mode *));
3150: reg_iv_info = (struct induction **)
3151: alloca (max_reg_before_loop * sizeof (struct induction *));
3152: bzero ((char *) reg_iv_info, (max_reg_before_loop
3153: * sizeof (struct induction *)));
3154: reg_biv_class = (struct iv_class **)
3155: alloca (max_reg_before_loop * sizeof (struct iv_class *));
3156: bzero ((char *) reg_biv_class, (max_reg_before_loop
3157: * sizeof (struct iv_class *)));
3158:
3159: loop_iv_list = 0;
3160: addr_placeholder = gen_reg_rtx (Pmode);
3161:
3162: /* Save insn immediately after the loop_end. Insns inserted after loop_end
3163: must be put before this insn, so that they will appear in the right
1.1.1.5 ! root 3164: order (i.e. loop order).
1.1 root 3165:
1.1.1.5 ! root 3166: If loop_end is the end of the current function, then emit a
! 3167: NOTE_INSN_DELETED after loop_end and set end_insert_before to the
! 3168: dummy note insn. */
! 3169: if (NEXT_INSN (loop_end) != 0)
! 3170: end_insert_before = NEXT_INSN (loop_end);
! 3171: else
! 3172: end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
1.1 root 3173:
3174: /* Scan through loop to find all possible bivs. */
3175:
3176: p = scan_start;
3177: while (1)
3178: {
3179: p = NEXT_INSN (p);
3180: /* At end of a straight-in loop, we are done.
3181: At end of a loop entered at the bottom, scan the top. */
3182: if (p == scan_start)
3183: break;
3184: if (p == end)
3185: {
3186: if (loop_top != 0)
3187: p = NEXT_INSN (loop_top);
3188: else
3189: break;
3190: if (p == scan_start)
3191: break;
3192: }
3193:
3194: if (GET_CODE (p) == INSN
3195: && (set = single_set (p))
3196: && GET_CODE (SET_DEST (set)) == REG)
3197: {
3198: dest_reg = SET_DEST (set);
3199: if (REGNO (dest_reg) < max_reg_before_loop
3200: && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
3201: && reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT)
3202: {
1.1.1.4 root 3203: if (basic_induction_var (SET_SRC (set), dest_reg, p,
1.1 root 3204: &inc_val, &mult_val))
3205: {
3206: /* It is a possible basic induction variable.
3207: Create and initialize an induction structure for it. */
3208:
3209: struct induction *v
3210: = (struct induction *) alloca (sizeof (struct induction));
3211:
3212: record_biv (v, p, dest_reg, inc_val, mult_val,
1.1.1.3 root 3213: not_every_iteration, maybe_multiple);
1.1 root 3214: reg_iv_type[REGNO (dest_reg)] = BASIC_INDUCT;
3215: }
3216: else if (REGNO (dest_reg) < max_reg_before_loop)
3217: reg_iv_type[REGNO (dest_reg)] = NOT_BASIC_INDUCT;
3218: }
3219: }
3220:
1.1.1.3 root 3221: /* Past CODE_LABEL, we get to insns that may be executed multiple
3222: times. The only way we can be sure that they can't is if every
3223: every jump insn between here and the end of the loop either
3224: returns, exits the loop, or is a forward jump. */
3225:
3226: if (GET_CODE (p) == CODE_LABEL)
3227: {
3228: rtx insn = p;
3229:
3230: maybe_multiple = 0;
3231:
3232: while (1)
3233: {
3234: insn = NEXT_INSN (insn);
3235: if (insn == scan_start)
3236: break;
3237: if (insn == end)
3238: {
3239: if (loop_top != 0)
3240: insn = NEXT_INSN (loop_top);
3241: else
3242: break;
3243: if (insn == scan_start)
3244: break;
3245: }
3246:
3247: if (GET_CODE (insn) == JUMP_INSN
3248: && GET_CODE (PATTERN (insn)) != RETURN
3249: && (! condjump_p (insn)
3250: || (JUMP_LABEL (insn) != 0
3251: && (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
3252: || INSN_UID (insn) >= max_uid_for_loop
3253: || (INSN_LUID (JUMP_LABEL (insn))
3254: < INSN_LUID (insn))))))
3255: {
3256: maybe_multiple = 1;
3257: break;
3258: }
3259: }
3260: }
3261:
1.1 root 3262: /* Past a label or a jump, we get to insns for which we can't count
3263: on whether or how many times they will be executed during each
3264: iteration. */
3265: /* This code appears in three places, once in scan_loop, and twice
3266: in strength_reduce. */
3267: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3268: /* If we enter the loop in the middle, and scan around to the
3269: beginning, don't set not_every_iteration for that.
3270: This can be any kind of jump, since we want to know if insns
3271: will be executed if the loop is executed. */
3272: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3273: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3274: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3275: not_every_iteration = 1;
3276:
3277: /* At the virtual top of a converted loop, insns are again known to
3278: be executed each iteration: logically, the loop begins here
3279: even though the exit code has been duplicated. */
3280:
3281: else if (GET_CODE (p) == NOTE
3282: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3283: not_every_iteration = 0;
3284:
3285: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3286: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3287: or not an insn is known to be executed each iteration of the
3288: loop, whether or not any iterations are known to occur.
3289:
3290: Therefore, if we have just passed a label and have no more labels
3291: between here and the test insn of the loop, we know these insns
3292: will be executed each iteration. This can also happen if we
3293: have just passed a jump, for example, when there are nested loops. */
3294:
3295: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3296: && no_labels_between_p (p, loop_end))
3297: not_every_iteration = 0;
3298: }
3299:
3300: /* Scan loop_iv_list to remove all regs that proved not to be bivs.
3301: Make a sanity check against n_times_set. */
3302: for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next)
3303: {
3304: if (reg_iv_type[bl->regno] != BASIC_INDUCT
3305: /* Above happens if register modified by subreg, etc. */
3306: /* Make sure it is not recognized as a basic induction var: */
3307: || n_times_set[bl->regno] != bl->biv_count
3308: /* If never incremented, it is invariant that we decided not to
3309: move. So leave it alone. */
3310: || ! bl->incremented)
3311: {
3312: if (loop_dump_stream)
3313: fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
3314: bl->regno,
3315: (reg_iv_type[bl->regno] != BASIC_INDUCT
3316: ? "not induction variable"
3317: : (! bl->incremented ? "never incremented"
3318: : "count error")));
3319:
3320: reg_iv_type[bl->regno] = NOT_BASIC_INDUCT;
3321: *backbl = bl->next;
3322: }
3323: else
3324: {
3325: backbl = &bl->next;
3326:
3327: if (loop_dump_stream)
3328: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
3329: }
3330: }
3331:
3332: /* Exit if there are no bivs. */
3333: if (! loop_iv_list)
3334: {
3335: /* Can still unroll the loop anyways, but indicate that there is no
3336: strength reduction info available. */
3337: if (flag_unroll_loops)
3338: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 0);
3339:
3340: return;
3341: }
3342:
3343: /* Find initial value for each biv by searching backwards from loop_start,
3344: halting at first label. Also record any test condition. */
3345:
3346: call_seen = 0;
3347: for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
3348: {
3349: note_insn = p;
3350:
3351: if (GET_CODE (p) == CALL_INSN)
3352: call_seen = 1;
3353:
3354: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3355: || GET_CODE (p) == CALL_INSN)
3356: note_stores (PATTERN (p), record_initial);
3357:
3358: /* Record any test of a biv that branches around the loop if no store
3359: between it and the start of loop. We only care about tests with
3360: constants and registers and only certain of those. */
3361: if (GET_CODE (p) == JUMP_INSN
3362: && JUMP_LABEL (p) != 0
3363: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
3364: && (test = get_condition_for_loop (p)) != 0
3365: && GET_CODE (XEXP (test, 0)) == REG
3366: && REGNO (XEXP (test, 0)) < max_reg_before_loop
3367: && (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
3368: && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
3369: && bl->init_insn == 0)
3370: {
3371: /* If an NE test, we have an initial value! */
3372: if (GET_CODE (test) == NE)
3373: {
3374: bl->init_insn = p;
3375: bl->init_set = gen_rtx (SET, VOIDmode,
3376: XEXP (test, 0), XEXP (test, 1));
3377: }
3378: else
3379: bl->initial_test = test;
3380: }
3381: }
3382:
3383: /* Look at the each biv and see if we can say anything better about its
3384: initial value from any initializing insns set up above. (This is done
3385: in two passes to avoid missing SETs in a PARALLEL.) */
3386: for (bl = loop_iv_list; bl; bl = bl->next)
3387: {
3388: rtx src;
3389:
3390: if (! bl->init_insn)
3391: continue;
3392:
3393: src = SET_SRC (bl->init_set);
3394:
3395: if (loop_dump_stream)
3396: fprintf (loop_dump_stream,
3397: "Biv %d initialized at insn %d: initial value ",
3398: bl->regno, INSN_UID (bl->init_insn));
3399:
3400: if (valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
3401: {
3402: bl->initial_value = src;
3403:
3404: if (loop_dump_stream)
3405: {
3406: if (GET_CODE (src) == CONST_INT)
3407: fprintf (loop_dump_stream, "%d\n", INTVAL (src));
3408: else
3409: {
3410: print_rtl (loop_dump_stream, src);
3411: fprintf (loop_dump_stream, "\n");
3412: }
3413: }
3414: }
3415: else
3416: {
3417: /* Biv initial value is not simple move,
1.1.1.2 root 3418: so let it keep initial value of "itself". */
1.1 root 3419:
3420: if (loop_dump_stream)
3421: fprintf (loop_dump_stream, "is complex\n");
3422: }
3423: }
3424:
3425: /* Search the loop for general induction variables. */
3426:
3427: /* A register is a giv if: it is only set once, it is a function of a
3428: biv and a constant (or invariant), and it is not a biv. */
3429:
3430: not_every_iteration = 0;
3431: p = scan_start;
3432: while (1)
3433: {
3434: p = NEXT_INSN (p);
3435: /* At end of a straight-in loop, we are done.
3436: At end of a loop entered at the bottom, scan the top. */
3437: if (p == scan_start)
3438: break;
3439: if (p == end)
3440: {
3441: if (loop_top != 0)
3442: p = NEXT_INSN (loop_top);
3443: else
3444: break;
3445: if (p == scan_start)
3446: break;
3447: }
3448:
3449: /* Look for a general induction variable in a register. */
3450: if (GET_CODE (p) == INSN
3451: && (set = single_set (p))
3452: && GET_CODE (SET_DEST (set)) == REG
3453: && ! may_not_optimize[REGNO (SET_DEST (set))])
3454: {
3455: rtx src_reg;
3456: rtx add_val;
3457: rtx mult_val;
3458: int benefit;
3459: rtx regnote = 0;
3460:
3461: dest_reg = SET_DEST (set);
3462: if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
3463: continue;
3464:
3465: if (/* SET_SRC is a giv. */
3466: ((benefit = general_induction_var (SET_SRC (set),
3467: &src_reg, &add_val,
3468: &mult_val))
3469: /* Equivalent expression is a giv. */
1.1.1.4 root 3470: || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
1.1 root 3471: && (benefit = general_induction_var (XEXP (regnote, 0),
3472: &src_reg,
3473: &add_val, &mult_val))))
3474: /* Don't try to handle any regs made by loop optimization.
3475: We have nothing on them in regno_first_uid, etc. */
3476: && REGNO (dest_reg) < max_reg_before_loop
3477: /* Don't recognize a BASIC_INDUCT_VAR here. */
3478: && dest_reg != src_reg
3479: /* This must be the only place where the register is set. */
3480: && (n_times_set[REGNO (dest_reg)] == 1
3481: /* or all sets must be consecutive and make a giv. */
3482: || (benefit = consec_sets_giv (benefit, p,
3483: src_reg, dest_reg,
3484: &add_val, &mult_val))))
3485: {
3486: int count;
3487: struct induction *v
3488: = (struct induction *) alloca (sizeof (struct induction));
3489: rtx temp;
3490:
3491: /* If this is a library call, increase benefit. */
1.1.1.4 root 3492: if (find_reg_note (p, REG_RETVAL, NULL_RTX))
1.1 root 3493: benefit += libcall_benefit (p);
3494:
3495: /* Skip the consecutive insns, if there are any. */
3496: for (count = n_times_set[REGNO (dest_reg)] - 1;
3497: count > 0; count--)
3498: {
3499: /* If first insn of libcall sequence, skip to end.
3500: Do this at start of loop, since INSN is guaranteed to
3501: be an insn here. */
3502: if (GET_CODE (p) != NOTE
1.1.1.4 root 3503: && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1.1 root 3504: p = XEXP (temp, 0);
3505:
3506: do p = NEXT_INSN (p);
3507: while (GET_CODE (p) == NOTE);
3508: }
3509:
3510: record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
1.1.1.4 root 3511: DEST_REG, not_every_iteration, NULL_PTR, loop_start,
1.1 root 3512: loop_end);
3513:
3514: }
3515: }
3516:
3517: #ifndef DONT_REDUCE_ADDR
3518: /* Look for givs which are memory addresses. */
3519: /* This resulted in worse code on a VAX 8600. I wonder if it
3520: still does. */
3521: if (GET_CODE (p) == INSN)
3522: find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
3523: loop_end);
3524: #endif
3525:
3526: /* Update the status of whether giv can derive other givs. This can
3527: change when we pass a label or an insn that updates a biv. */
1.1.1.3 root 3528: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3529: || GET_CODE (p) == CODE_LABEL)
1.1 root 3530: update_giv_derive (p);
3531:
3532: /* Past a label or a jump, we get to insns for which we can't count
3533: on whether or how many times they will be executed during each
3534: iteration. */
3535: /* This code appears in three places, once in scan_loop, and twice
3536: in strength_reduce. */
3537: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
3538: /* If we enter the loop in the middle, and scan around
3539: to the beginning, don't set not_every_iteration for that.
3540: This can be any kind of jump, since we want to know if insns
3541: will be executed if the loop is executed. */
3542: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
3543: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
3544: || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
3545: not_every_iteration = 1;
3546:
3547: /* At the virtual top of a converted loop, insns are again known to
3548: be executed each iteration: logically, the loop begins here
3549: even though the exit code has been duplicated. */
3550:
3551: else if (GET_CODE (p) == NOTE
3552: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
3553: not_every_iteration = 0;
3554:
3555: /* Unlike in the code motion pass where MAYBE_NEVER indicates that
3556: an insn may never be executed, NOT_EVERY_ITERATION indicates whether
3557: or not an insn is known to be executed each iteration of the
3558: loop, whether or not any iterations are known to occur.
3559:
3560: Therefore, if we have just passed a label and have no more labels
3561: between here and the test insn of the loop, we know these insns
3562: will be executed each iteration. */
3563:
3564: if (not_every_iteration && GET_CODE (p) == CODE_LABEL
3565: && no_labels_between_p (p, loop_end))
3566: not_every_iteration = 0;
3567: }
3568:
3569: /* Try to calculate and save the number of loop iterations. This is
3570: set to zero if the actual number can not be calculated. This must
3571: be called after all giv's have been identified, since otherwise it may
3572: fail if the iteration variable is a giv. */
3573:
3574: loop_n_iterations = loop_iterations (loop_start, loop_end);
3575:
3576: /* Now for each giv for which we still don't know whether or not it is
3577: replaceable, check to see if it is replaceable because its final value
3578: can be calculated. This must be done after loop_iterations is called,
3579: so that final_giv_value will work correctly. */
3580:
3581: for (bl = loop_iv_list; bl; bl = bl->next)
3582: {
3583: struct induction *v;
3584:
3585: for (v = bl->giv; v; v = v->next_iv)
3586: if (! v->replaceable && ! v->not_replaceable)
3587: check_final_value (v, loop_start, loop_end);
3588: }
3589:
3590: /* Try to prove that the loop counter variable (if any) is always
3591: nonnegative; if so, record that fact with a REG_NONNEG note
3592: so that "decrement and branch until zero" insn can be used. */
3593: check_dbra_loop (loop_end, insn_count, loop_start);
3594:
3595: /* Create reg_map to hold substitutions for replaceable giv regs. */
3596: reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
3597: bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
3598:
3599: /* Examine each iv class for feasibility of strength reduction/induction
3600: variable elimination. */
3601:
3602: for (bl = loop_iv_list; bl; bl = bl->next)
3603: {
3604: struct induction *v;
3605: int benefit;
3606: int all_reduced;
3607: rtx final_value = 0;
3608:
3609: /* Test whether it will be possible to eliminate this biv
3610: provided all givs are reduced. This is possible if either
3611: the reg is not used outside the loop, or we can compute
3612: what its final value will be.
3613:
3614: For architectures with a decrement_and_branch_until_zero insn,
3615: don't do this if we put a REG_NONNEG note on the endtest for
3616: this biv. */
3617:
3618: /* Compare against bl->init_insn rather than loop_start.
3619: We aren't concerned with any uses of the biv between
3620: init_insn and loop_start since these won't be affected
3621: by the value of the biv elsewhere in the function, so
3622: long as init_insn doesn't use the biv itself.
3623: March 14, 1989 -- [email protected] */
3624:
3625: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
3626: && bl->init_insn
3627: && INSN_UID (bl->init_insn) < max_uid_for_loop
3628: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
3629: #ifdef HAVE_decrement_and_branch_until_zero
3630: && ! bl->nonneg
3631: #endif
3632: && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
3633: || ((final_value = final_biv_value (bl, loop_start, loop_end))
3634: #ifdef HAVE_decrement_and_branch_until_zero
3635: && ! bl->nonneg
3636: #endif
3637: ))
3638: bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
3639: threshold, insn_count);
3640: else
3641: {
3642: if (loop_dump_stream)
3643: {
3644: fprintf (loop_dump_stream,
3645: "Cannot eliminate biv %d.\n",
3646: bl->regno);
3647: fprintf (loop_dump_stream,
3648: "First use: insn %d, last use: insn %d.\n",
3649: regno_first_uid[bl->regno],
3650: regno_last_uid[bl->regno]);
3651: }
3652: }
3653:
3654: /* Combine all giv's for this iv_class. */
3655: combine_givs (bl);
3656:
3657: /* This will be true at the end, if all givs which depend on this
3658: biv have been strength reduced.
3659: We can't (currently) eliminate the biv unless this is so. */
3660: all_reduced = 1;
3661:
3662: /* Check each giv in this class to see if we will benefit by reducing
3663: it. Skip giv's combined with others. */
3664: for (v = bl->giv; v; v = v->next_iv)
3665: {
3666: struct induction *tv;
3667:
3668: if (v->ignore || v->same)
3669: continue;
3670:
3671: benefit = v->benefit;
3672:
3673: /* Reduce benefit if not replaceable, since we will insert
3674: a move-insn to replace the insn that calculates this giv.
3675: Don't do this unless the giv is a user variable, since it
3676: will often be marked non-replaceable because of the duplication
3677: of the exit code outside the loop. In such a case, the copies
3678: we insert are dead and will be deleted. So they don't have
3679: a cost. Similar situations exist. */
3680: /* ??? The new final_[bg]iv_value code does a much better job
3681: of finding replaceable giv's, and hence this code may no longer
3682: be necessary. */
3683: if (! v->replaceable && ! bl->eliminable
3684: && REG_USERVAR_P (v->dest_reg))
3685: benefit -= copy_cost;
3686:
3687: /* Decrease the benefit to count the add-insns that we will
3688: insert to increment the reduced reg for the giv. */
3689: benefit -= add_cost * bl->biv_count;
3690:
3691: /* Decide whether to strength-reduce this giv or to leave the code
3692: unchanged (recompute it from the biv each time it is used).
3693: This decision can be made independently for each giv. */
3694:
3695: /* ??? Perhaps attempt to guess whether autoincrement will handle
3696: some of the new add insns; if so, can increase BENEFIT
3697: (undo the subtraction of add_cost that was done above). */
3698:
3699: /* If an insn is not to be strength reduced, then set its ignore
3700: flag, and clear all_reduced. */
3701:
3702: if (v->lifetime * threshold * benefit < insn_count)
3703: {
3704: if (loop_dump_stream)
3705: fprintf (loop_dump_stream,
3706: "giv of insn %d not worth while, %d vs %d.\n",
3707: INSN_UID (v->insn),
3708: v->lifetime * threshold * benefit, insn_count);
3709: v->ignore = 1;
3710: all_reduced = 0;
3711: }
3712: else
3713: {
3714: /* Check that we can increment the reduced giv without a
3715: multiply insn. If not, reject it. */
3716:
3717: for (tv = bl->biv; tv; tv = tv->next_iv)
3718: if (tv->mult_val == const1_rtx
3719: && ! product_cheap_p (tv->add_val, v->mult_val))
3720: {
3721: if (loop_dump_stream)
3722: fprintf (loop_dump_stream,
3723: "giv of insn %d: would need a multiply.\n",
3724: INSN_UID (v->insn));
3725: v->ignore = 1;
3726: all_reduced = 0;
3727: break;
3728: }
3729: }
3730: }
3731:
3732: /* Reduce each giv that we decided to reduce. */
3733:
3734: for (v = bl->giv; v; v = v->next_iv)
3735: {
3736: struct induction *tv;
3737: if (! v->ignore && v->same == 0)
3738: {
3739: v->new_reg = gen_reg_rtx (v->mode);
3740:
3741: /* For each place where the biv is incremented,
3742: add an insn to increment the new, reduced reg for the giv. */
3743: for (tv = bl->biv; tv; tv = tv->next_iv)
3744: {
3745: if (tv->mult_val == const1_rtx)
3746: emit_iv_add_mult (tv->add_val, v->mult_val,
3747: v->new_reg, v->new_reg, tv->insn);
3748: else /* tv->mult_val == const0_rtx */
3749: /* A multiply is acceptable here
3750: since this is presumed to be seldom executed. */
3751: emit_iv_add_mult (tv->add_val, v->mult_val,
3752: v->add_val, v->new_reg, tv->insn);
3753: }
3754:
3755: /* Add code at loop start to initialize giv's reduced reg. */
3756:
3757: emit_iv_add_mult (bl->initial_value, v->mult_val,
3758: v->add_val, v->new_reg, loop_start);
3759: }
3760: }
3761:
3762: /* Rescan all givs. If a giv is the same as a giv not reduced, mark it
3763: as not reduced.
3764:
3765: For each giv register that can be reduced now: if replaceable,
3766: substitute reduced reg wherever the old giv occurs;
3767: else add new move insn "giv_reg = reduced_reg".
3768:
3769: Also check for givs whose first use is their definition and whose
3770: last use is the definition of another giv. If so, it is likely
3771: dead and should not be used to eliminate a biv. */
3772: for (v = bl->giv; v; v = v->next_iv)
3773: {
3774: if (v->same && v->same->ignore)
3775: v->ignore = 1;
3776:
3777: if (v->ignore)
3778: continue;
3779:
3780: if (v->giv_type == DEST_REG
3781: && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn))
3782: {
3783: struct induction *v1;
3784:
3785: for (v1 = bl->giv; v1; v1 = v1->next_iv)
3786: if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn))
3787: v->maybe_dead = 1;
3788: }
3789:
3790: /* Update expression if this was combined, in case other giv was
3791: replaced. */
3792: if (v->same)
3793: v->new_reg = replace_rtx (v->new_reg,
3794: v->same->dest_reg, v->same->new_reg);
3795:
3796: if (v->giv_type == DEST_ADDR)
3797: /* Store reduced reg as the address in the memref where we found
3798: this giv. */
3799: *v->location = v->new_reg;
3800: else if (v->replaceable)
3801: {
3802: reg_map[REGNO (v->dest_reg)] = v->new_reg;
3803:
3804: #if 0
3805: /* I can no longer duplicate the original problem. Perhaps
3806: this is unnecessary now? */
3807:
3808: /* Replaceable; it isn't strictly necessary to delete the old
3809: insn and emit a new one, because v->dest_reg is now dead.
3810:
3811: However, especially when unrolling loops, the special
3812: handling for (set REG0 REG1) in the second cse pass may
3813: make v->dest_reg live again. To avoid this problem, emit
3814: an insn to set the original giv reg from the reduced giv.
3815: We can not delete the original insn, since it may be part
3816: of a LIBCALL, and the code in flow that eliminates dead
3817: libcalls will fail if it is deleted. */
3818: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3819: v->insn);
3820: #endif
3821: }
3822: else
3823: {
3824: /* Not replaceable; emit an insn to set the original giv reg from
3825: the reduced giv, same as above. */
3826: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
3827: v->insn);
3828: }
3829:
3830: /* When a loop is reversed, givs which depend on the reversed
3831: biv, and which are live outside the loop, must be set to their
3832: correct final value. This insn is only needed if the giv is
3833: not replaceable. The correct final value is the same as the
3834: value that the giv starts the reversed loop with. */
3835: if (bl->reversed && ! v->replaceable)
3836: emit_iv_add_mult (bl->initial_value, v->mult_val,
3837: v->add_val, v->dest_reg, end_insert_before);
3838: else if (v->final_value)
3839: {
3840: rtx insert_before;
3841:
3842: /* If the loop has multiple exits, emit the insn before the
3843: loop to ensure that it will always be executed no matter
3844: how the loop exits. Otherwise, emit the insn after the loop,
3845: since this is slightly more efficient. */
3846: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3847: insert_before = loop_start;
3848: else
3849: insert_before = end_insert_before;
3850: emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
3851: insert_before);
3852:
3853: #if 0
3854: /* If the insn to set the final value of the giv was emitted
3855: before the loop, then we must delete the insn inside the loop
3856: that sets it. If this is a LIBCALL, then we must delete
3857: every insn in the libcall. Note, however, that
3858: final_giv_value will only succeed when there are multiple
3859: exits if the giv is dead at each exit, hence it does not
3860: matter that the original insn remains because it is dead
3861: anyways. */
3862: /* Delete the insn inside the loop that sets the giv since
3863: the giv is now set before (or after) the loop. */
3864: delete_insn (v->insn);
3865: #endif
3866: }
3867:
3868: if (loop_dump_stream)
3869: {
3870: fprintf (loop_dump_stream, "giv at %d reduced to ",
3871: INSN_UID (v->insn));
3872: print_rtl (loop_dump_stream, v->new_reg);
3873: fprintf (loop_dump_stream, "\n");
3874: }
3875: }
3876:
3877: /* All the givs based on the biv bl have been reduced if they
3878: merit it. */
3879:
3880: /* For each giv not marked as maybe dead that has been combined with a
3881: second giv, clear any "maybe dead" mark on that second giv.
3882: v->new_reg will either be or refer to the register of the giv it
3883: combined with.
3884:
3885: Doing this clearing avoids problems in biv elimination where a
3886: giv's new_reg is a complex value that can't be put in the insn but
3887: the giv combined with (with a reg as new_reg) is marked maybe_dead.
3888: Since the register will be used in either case, we'd prefer it be
3889: used from the simpler giv. */
3890:
3891: for (v = bl->giv; v; v = v->next_iv)
3892: if (! v->maybe_dead && v->same)
3893: v->same->maybe_dead = 0;
3894:
3895: /* Try to eliminate the biv, if it is a candidate.
3896: This won't work if ! all_reduced,
3897: since the givs we planned to use might not have been reduced.
3898:
1.1.1.2 root 3899: We have to be careful that we didn't initially think we could eliminate
1.1 root 3900: this biv because of a giv that we now think may be dead and shouldn't
3901: be used as a biv replacement.
3902:
3903: Also, there is the possibility that we may have a giv that looks
3904: like it can be used to eliminate a biv, but the resulting insn
3905: isn't valid. This can happen, for example, on the 88k, where a
3906: JUMP_INSN can compare a register only with zero. Attempts to
1.1.1.3 root 3907: replace it with a compare with a constant will fail.
1.1 root 3908:
3909: Note that in cases where this call fails, we may have replaced some
3910: of the occurrences of the biv with a giv, but no harm was done in
3911: doing so in the rare cases where it can occur. */
3912:
3913: if (all_reduced == 1 && bl->eliminable
3914: && maybe_eliminate_biv (bl, loop_start, end, 1,
3915: threshold, insn_count))
3916:
3917: {
3918: /* ?? If we created a new test to bypass the loop entirely,
3919: or otherwise drop straight in, based on this test, then
3920: we might want to rewrite it also. This way some later
3921: pass has more hope of removing the initialization of this
3922: biv entirely. */
3923:
3924: /* If final_value != 0, then the biv may be used after loop end
3925: and we must emit an insn to set it just in case.
3926:
3927: Reversed bivs already have an insn after the loop setting their
3928: value, so we don't need another one. We can't calculate the
3929: proper final value for such a biv here anyways. */
3930: if (final_value != 0 && ! bl->reversed)
3931: {
3932: rtx insert_before;
3933:
3934: /* If the loop has multiple exits, emit the insn before the
3935: loop to ensure that it will always be executed no matter
3936: how the loop exits. Otherwise, emit the insn after the
3937: loop, since this is slightly more efficient. */
3938: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
3939: insert_before = loop_start;
3940: else
3941: insert_before = end_insert_before;
3942:
3943: emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
3944: end_insert_before);
3945: }
3946:
3947: #if 0
3948: /* Delete all of the instructions inside the loop which set
3949: the biv, as they are all dead. If is safe to delete them,
3950: because an insn setting a biv will never be part of a libcall. */
3951: /* However, deleting them will invalidate the regno_last_uid info,
3952: so keeping them around is more convenient. Final_biv_value
3953: will only succeed when there are multiple exits if the biv
3954: is dead at each exit, hence it does not matter that the original
3955: insn remains, because it is dead anyways. */
3956: for (v = bl->biv; v; v = v->next_iv)
3957: delete_insn (v->insn);
3958: #endif
3959:
3960: if (loop_dump_stream)
3961: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
3962: bl->regno);
3963: }
3964: }
3965:
3966: /* Go through all the instructions in the loop, making all the
3967: register substitutions scheduled in REG_MAP. */
3968:
3969: for (p = loop_start; p != end; p = NEXT_INSN (p))
3970: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
3971: || GET_CODE (p) == CALL_INSN)
3972: {
3973: replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0);
3974: replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0);
1.1.1.5 ! root 3975: INSN_CODE (p) = -1;
1.1 root 3976: }
3977:
3978: /* Unroll loops from within strength reduction so that we can use the
3979: induction variable information that strength_reduce has already
3980: collected. */
3981:
3982: if (flag_unroll_loops)
3983: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
3984:
3985: if (loop_dump_stream)
3986: fprintf (loop_dump_stream, "\n");
3987: }
3988:
3989: /* Return 1 if X is a valid source for an initial value (or as value being
3990: compared against in an initial test).
3991:
3992: X must be either a register or constant and must not be clobbered between
3993: the current insn and the start of the loop.
3994:
3995: INSN is the insn containing X. */
3996:
3997: static int
3998: valid_initial_value_p (x, insn, call_seen, loop_start)
3999: rtx x;
4000: rtx insn;
4001: int call_seen;
4002: rtx loop_start;
4003: {
4004: if (CONSTANT_P (x))
4005: return 1;
4006:
1.1.1.2 root 4007: /* Only consider pseudos we know about initialized in insns whose luids
1.1 root 4008: we know. */
4009: if (GET_CODE (x) != REG
4010: || REGNO (x) >= max_reg_before_loop)
4011: return 0;
4012:
4013: /* Don't use call-clobbered registers across a call which clobbers it. On
4014: some machines, don't use any hard registers at all. */
4015: if (REGNO (x) < FIRST_PSEUDO_REGISTER
4016: #ifndef SMALL_REGISTER_CLASSES
4017: && call_used_regs[REGNO (x)] && call_seen
4018: #endif
4019: )
4020: return 0;
4021:
4022: /* Don't use registers that have been clobbered before the start of the
4023: loop. */
4024: if (reg_set_between_p (x, insn, loop_start))
4025: return 0;
4026:
4027: return 1;
4028: }
4029:
4030: /* Scan X for memory refs and check each memory address
4031: as a possible giv. INSN is the insn whose pattern X comes from.
4032: NOT_EVERY_ITERATION is 1 if the insn might not be executed during
4033: every loop iteration. */
4034:
4035: static void
4036: find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
4037: rtx x;
4038: rtx insn;
4039: int not_every_iteration;
4040: rtx loop_start, loop_end;
4041: {
4042: register int i, j;
4043: register enum rtx_code code;
4044: register char *fmt;
4045:
4046: if (x == 0)
4047: return;
4048:
4049: code = GET_CODE (x);
4050: switch (code)
4051: {
4052: case REG:
4053: case CONST_INT:
4054: case CONST:
4055: case CONST_DOUBLE:
4056: case SYMBOL_REF:
4057: case LABEL_REF:
4058: case PC:
4059: case CC0:
4060: case ADDR_VEC:
4061: case ADDR_DIFF_VEC:
4062: case USE:
4063: case CLOBBER:
4064: return;
4065:
4066: case MEM:
4067: {
4068: rtx src_reg;
4069: rtx add_val;
4070: rtx mult_val;
4071: int benefit;
4072:
4073: benefit = general_induction_var (XEXP (x, 0),
4074: &src_reg, &add_val, &mult_val);
4075:
4076: /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0.
4077: Such a giv isn't useful. */
4078: if (benefit > 0 && (mult_val != const1_rtx || add_val != const0_rtx))
4079: {
4080: /* Found one; record it. */
4081: struct induction *v
4082: = (struct induction *) oballoc (sizeof (struct induction));
4083:
4084: record_giv (v, insn, src_reg, addr_placeholder, mult_val,
4085: add_val, benefit, DEST_ADDR, not_every_iteration,
4086: &XEXP (x, 0), loop_start, loop_end);
4087:
4088: v->mem_mode = GET_MODE (x);
4089: }
4090: return;
4091: }
4092: }
4093:
4094: /* Recursively scan the subexpressions for other mem refs. */
4095:
4096: fmt = GET_RTX_FORMAT (code);
4097: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4098: if (fmt[i] == 'e')
4099: find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
4100: loop_end);
4101: else if (fmt[i] == 'E')
4102: for (j = 0; j < XVECLEN (x, i); j++)
4103: find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
4104: loop_start, loop_end);
4105: }
4106:
4107: /* Fill in the data about one biv update.
4108: V is the `struct induction' in which we record the biv. (It is
4109: allocated by the caller, with alloca.)
4110: INSN is the insn that sets it.
4111: DEST_REG is the biv's reg.
4112:
4113: MULT_VAL is const1_rtx if the biv is being incremented here, in which case
4114: INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is
1.1.1.3 root 4115: being set to INC_VAL.
4116:
4117: NOT_EVERY_ITERATION is nonzero if this biv update is not know to be
4118: executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update
4119: can be executed more than once per iteration. If MAYBE_MULTIPLE
4120: and NOT_EVERY_ITERATION are both zero, we know that the biv update is
4121: executed exactly once per iteration. */
1.1 root 4122:
4123: static void
1.1.1.3 root 4124: record_biv (v, insn, dest_reg, inc_val, mult_val,
4125: not_every_iteration, maybe_multiple)
1.1 root 4126: struct induction *v;
4127: rtx insn;
4128: rtx dest_reg;
4129: rtx inc_val;
4130: rtx mult_val;
4131: int not_every_iteration;
1.1.1.3 root 4132: int maybe_multiple;
1.1 root 4133: {
4134: struct iv_class *bl;
4135:
4136: v->insn = insn;
4137: v->src_reg = dest_reg;
4138: v->dest_reg = dest_reg;
4139: v->mult_val = mult_val;
4140: v->add_val = inc_val;
4141: v->mode = GET_MODE (dest_reg);
4142: v->always_computable = ! not_every_iteration;
1.1.1.3 root 4143: v->maybe_multiple = maybe_multiple;
1.1 root 4144:
4145: /* Add this to the reg's iv_class, creating a class
4146: if this is the first incrementation of the reg. */
4147:
4148: bl = reg_biv_class[REGNO (dest_reg)];
4149: if (bl == 0)
4150: {
4151: /* Create and initialize new iv_class. */
4152:
4153: bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
4154:
4155: bl->regno = REGNO (dest_reg);
4156: bl->biv = 0;
4157: bl->giv = 0;
4158: bl->biv_count = 0;
4159: bl->giv_count = 0;
4160:
4161: /* Set initial value to the reg itself. */
4162: bl->initial_value = dest_reg;
1.1.1.3 root 4163: /* We haven't seen the initializing insn yet */
1.1 root 4164: bl->init_insn = 0;
4165: bl->init_set = 0;
4166: bl->initial_test = 0;
4167: bl->incremented = 0;
4168: bl->eliminable = 0;
4169: bl->nonneg = 0;
4170: bl->reversed = 0;
1.1.1.4 root 4171: bl->total_benefit = 0;
1.1 root 4172:
4173: /* Add this class to loop_iv_list. */
4174: bl->next = loop_iv_list;
4175: loop_iv_list = bl;
4176:
4177: /* Put it in the array of biv register classes. */
4178: reg_biv_class[REGNO (dest_reg)] = bl;
4179: }
4180:
4181: /* Update IV_CLASS entry for this biv. */
4182: v->next_iv = bl->biv;
4183: bl->biv = v;
4184: bl->biv_count++;
4185: if (mult_val == const1_rtx)
4186: bl->incremented = 1;
4187:
4188: if (loop_dump_stream)
4189: {
4190: fprintf (loop_dump_stream,
4191: "Insn %d: possible biv, reg %d,",
4192: INSN_UID (insn), REGNO (dest_reg));
4193: if (GET_CODE (inc_val) == CONST_INT)
4194: fprintf (loop_dump_stream, " const = %d\n",
4195: INTVAL (inc_val));
4196: else
4197: {
4198: fprintf (loop_dump_stream, " const = ");
4199: print_rtl (loop_dump_stream, inc_val);
4200: fprintf (loop_dump_stream, "\n");
4201: }
4202: }
4203: }
4204:
4205: /* Fill in the data about one giv.
4206: V is the `struct induction' in which we record the giv. (It is
4207: allocated by the caller, with alloca.)
4208: INSN is the insn that sets it.
4209: BENEFIT estimates the savings from deleting this insn.
4210: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed
4211: into a register or is used as a memory address.
4212:
4213: SRC_REG is the biv reg which the giv is computed from.
4214: DEST_REG is the giv's reg (if the giv is stored in a reg).
4215: MULT_VAL and ADD_VAL are the coefficients used to compute the giv.
4216: LOCATION points to the place where this giv's value appears in INSN. */
4217:
4218: static void
4219: record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
4220: type, not_every_iteration, location, loop_start, loop_end)
4221: struct induction *v;
4222: rtx insn;
4223: rtx src_reg;
4224: rtx dest_reg;
4225: rtx mult_val, add_val;
4226: int benefit;
4227: enum g_types type;
4228: int not_every_iteration;
4229: rtx *location;
4230: rtx loop_start, loop_end;
4231: {
4232: struct induction *b;
4233: struct iv_class *bl;
4234: rtx set = single_set (insn);
4235: rtx p;
4236:
4237: v->insn = insn;
4238: v->src_reg = src_reg;
4239: v->giv_type = type;
4240: v->dest_reg = dest_reg;
4241: v->mult_val = mult_val;
4242: v->add_val = add_val;
4243: v->benefit = benefit;
4244: v->location = location;
4245: v->cant_derive = 0;
4246: v->combined_with = 0;
1.1.1.3 root 4247: v->maybe_multiple = 0;
1.1 root 4248: v->maybe_dead = 0;
4249: v->derive_adjustment = 0;
4250: v->same = 0;
4251: v->ignore = 0;
4252: v->new_reg = 0;
4253: v->final_value = 0;
4254:
4255: /* The v->always_computable field is used in update_giv_derive, to
4256: determine whether a giv can be used to derive another giv. For a
4257: DEST_REG giv, INSN computes a new value for the giv, so its value
4258: isn't computable if INSN insn't executed every iteration.
4259: However, for a DEST_ADDR giv, INSN merely uses the value of the giv;
4260: it does not compute a new value. Hence the value is always computable
1.1.1.2 root 4261: regardless of whether INSN is executed each iteration. */
1.1 root 4262:
4263: if (type == DEST_ADDR)
4264: v->always_computable = 1;
4265: else
4266: v->always_computable = ! not_every_iteration;
4267:
4268: if (type == DEST_ADDR)
4269: {
4270: v->mode = GET_MODE (*location);
4271: v->lifetime = 1;
4272: v->times_used = 1;
4273: }
4274: else /* type == DEST_REG */
4275: {
4276: v->mode = GET_MODE (SET_DEST (set));
4277:
4278: v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]]
4279: - uid_luid[regno_first_uid[REGNO (dest_reg)]]);
4280:
4281: v->times_used = n_times_used[REGNO (dest_reg)];
4282:
4283: /* If the lifetime is zero, it means that this register is
4284: really a dead store. So mark this as a giv that can be
4285: ignored. This will not prevent the biv from being eliminated. */
4286: if (v->lifetime == 0)
4287: v->ignore = 1;
4288:
4289: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
4290: reg_iv_info[REGNO (dest_reg)] = v;
4291: }
4292:
4293: /* Add the giv to the class of givs computed from one biv. */
4294:
4295: bl = reg_biv_class[REGNO (src_reg)];
4296: if (bl)
4297: {
4298: v->next_iv = bl->giv;
4299: bl->giv = v;
4300: /* Don't count DEST_ADDR. This is supposed to count the number of
4301: insns that calculate givs. */
4302: if (type == DEST_REG)
4303: bl->giv_count++;
4304: bl->total_benefit += benefit;
4305: }
4306: else
4307: /* Fatal error, biv missing for this giv? */
4308: abort ();
4309:
4310: if (type == DEST_ADDR)
4311: v->replaceable = 1;
4312: else
4313: {
4314: /* The giv can be replaced outright by the reduced register only if all
4315: of the following conditions are true:
4316: - the insn that sets the giv is always executed on any iteration
4317: on which the giv is used at all
4318: (there are two ways to deduce this:
4319: either the insn is executed on every iteration,
4320: or all uses follow that insn in the same basic block),
4321: - the giv is not used outside the loop
4322: - no assignments to the biv occur during the giv's lifetime. */
4323:
4324: if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn)
4325: /* Previous line always fails if INSN was moved by loop opt. */
4326: && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end)
4327: && (! not_every_iteration
4328: || last_use_this_basic_block (dest_reg, insn)))
4329: {
4330: /* Now check that there are no assignments to the biv within the
4331: giv's lifetime. This requires two separate checks. */
4332:
4333: /* Check each biv update, and fail if any are between the first
4334: and last use of the giv.
4335:
4336: If this loop contains an inner loop that was unrolled, then
4337: the insn modifying the biv may have been emitted by the loop
4338: unrolling code, and hence does not have a valid luid. Just
4339: mark the biv as not replaceable in this case. It is not very
4340: useful as a biv, because it is used in two different loops.
4341: It is very unlikely that we would be able to optimize the giv
4342: using this biv anyways. */
4343:
4344: v->replaceable = 1;
4345: for (b = bl->biv; b; b = b->next_iv)
4346: {
4347: if (INSN_UID (b->insn) >= max_uid_for_loop
4348: || ((uid_luid[INSN_UID (b->insn)]
4349: >= uid_luid[regno_first_uid[REGNO (dest_reg)]])
4350: && (uid_luid[INSN_UID (b->insn)]
4351: <= uid_luid[regno_last_uid[REGNO (dest_reg)]])))
4352: {
4353: v->replaceable = 0;
4354: v->not_replaceable = 1;
4355: break;
4356: }
4357: }
4358:
4359: /* Check each insn between the first and last use of the giv,
4360: and fail if any of them are branches that jump to a named label
4361: outside this range, but still inside the loop. This catches
4362: cases of spaghetti code where the execution order of insns
4363: is not linear, and hence the above test fails. For example,
4364: in the following code, j is not replaceable:
4365: for (i = 0; i < 100; ) {
4366: L0: j = 4*i; goto L1;
4367: L2: k = j; goto L3;
4368: L1: i++; goto L2;
4369: L3: ; }
4370: printf ("k = %d\n", k); }
4371: This test is conservative, but this test succeeds rarely enough
4372: that it isn't a problem. See also check_final_value below. */
4373:
4374: if (v->replaceable)
4375: for (p = insn;
4376: INSN_UID (p) >= max_uid_for_loop
4377: || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]];
4378: p = NEXT_INSN (p))
4379: {
4380: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4381: && LABEL_NAME (JUMP_LABEL (p))
4382: && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)
4383: && (INSN_LUID (JUMP_LABEL (p))
4384: < uid_luid[regno_first_uid[REGNO (dest_reg)]]))
4385: || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)
4386: && (INSN_LUID (JUMP_LABEL (p))
4387: > uid_luid[regno_last_uid[REGNO (dest_reg)]]))))
4388: {
4389: v->replaceable = 0;
4390: v->not_replaceable = 1;
4391:
4392: if (loop_dump_stream)
4393: fprintf (loop_dump_stream,
4394: "Found branch outside giv lifetime.\n");
4395:
4396: break;
4397: }
4398: }
4399: }
4400: else
4401: {
4402: /* May still be replaceable, we don't have enough info here to
4403: decide. */
4404: v->replaceable = 0;
4405: v->not_replaceable = 0;
4406: }
4407: }
4408:
4409: if (loop_dump_stream)
4410: {
4411: if (type == DEST_REG)
4412: fprintf (loop_dump_stream, "Insn %d: giv reg %d",
4413: INSN_UID (insn), REGNO (dest_reg));
4414: else
4415: fprintf (loop_dump_stream, "Insn %d: dest address",
4416: INSN_UID (insn));
4417:
4418: fprintf (loop_dump_stream, " src reg %d benefit %d",
4419: REGNO (src_reg), v->benefit);
4420: fprintf (loop_dump_stream, " used %d lifetime %d",
4421: v->times_used, v->lifetime);
4422:
4423: if (v->replaceable)
4424: fprintf (loop_dump_stream, " replaceable");
4425:
4426: if (GET_CODE (mult_val) == CONST_INT)
4427: fprintf (loop_dump_stream, " mult %d",
4428: INTVAL (mult_val));
4429: else
4430: {
4431: fprintf (loop_dump_stream, " mult ");
4432: print_rtl (loop_dump_stream, mult_val);
4433: }
4434:
4435: if (GET_CODE (add_val) == CONST_INT)
4436: fprintf (loop_dump_stream, " add %d",
4437: INTVAL (add_val));
4438: else
4439: {
4440: fprintf (loop_dump_stream, " add ");
4441: print_rtl (loop_dump_stream, add_val);
4442: }
4443: }
4444:
4445: if (loop_dump_stream)
4446: fprintf (loop_dump_stream, "\n");
4447:
4448: }
4449:
4450:
4451: /* All this does is determine whether a giv can be made replaceable because
4452: its final value can be calculated. This code can not be part of record_giv
4453: above, because final_giv_value requires that the number of loop iterations
4454: be known, and that can not be accurately calculated until after all givs
4455: have been identified. */
4456:
4457: static void
4458: check_final_value (v, loop_start, loop_end)
4459: struct induction *v;
4460: rtx loop_start, loop_end;
4461: {
4462: struct iv_class *bl;
4463: rtx final_value = 0;
4464: rtx tem;
4465:
4466: bl = reg_biv_class[REGNO (v->src_reg)];
4467:
4468: /* DEST_ADDR givs will never reach here, because they are always marked
4469: replaceable above in record_giv. */
4470:
4471: /* The giv can be replaced outright by the reduced register only if all
4472: of the following conditions are true:
4473: - the insn that sets the giv is always executed on any iteration
4474: on which the giv is used at all
4475: (there are two ways to deduce this:
4476: either the insn is executed on every iteration,
4477: or all uses follow that insn in the same basic block),
4478: - its final value can be calculated (this condition is different
4479: than the one above in record_giv)
4480: - no assignments to the biv occur during the giv's lifetime. */
4481:
4482: #if 0
4483: /* This is only called now when replaceable is known to be false. */
4484: /* Clear replaceable, so that it won't confuse final_giv_value. */
4485: v->replaceable = 0;
4486: #endif
4487:
4488: if ((final_value = final_giv_value (v, loop_start, loop_end))
4489: && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
4490: {
4491: int biv_increment_seen = 0;
4492: rtx p = v->insn;
4493: rtx last_giv_use;
4494:
4495: v->replaceable = 1;
4496:
4497: /* When trying to determine whether or not a biv increment occurs
4498: during the lifetime of the giv, we can ignore uses of the variable
4499: outside the loop because final_value is true. Hence we can not
4500: use regno_last_uid and regno_first_uid as above in record_giv. */
4501:
4502: /* Search the loop to determine whether any assignments to the
4503: biv occur during the giv's lifetime. Start with the insn
4504: that sets the giv, and search around the loop until we come
4505: back to that insn again.
4506:
4507: Also fail if there is a jump within the giv's lifetime that jumps
4508: to somewhere outside the lifetime but still within the loop. This
4509: catches spaghetti code where the execution order is not linear, and
4510: hence the above test fails. Here we assume that the giv lifetime
4511: does not extend from one iteration of the loop to the next, so as
4512: to make the test easier. Since the lifetime isn't known yet,
4513: this requires two loops. See also record_giv above. */
4514:
4515: last_giv_use = v->insn;
4516:
4517: while (1)
4518: {
4519: p = NEXT_INSN (p);
4520: if (p == loop_end)
4521: p = NEXT_INSN (loop_start);
4522: if (p == v->insn)
4523: break;
4524:
4525: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
4526: || GET_CODE (p) == CALL_INSN)
4527: {
4528: if (biv_increment_seen)
4529: {
4530: if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4531: {
4532: v->replaceable = 0;
4533: v->not_replaceable = 1;
4534: break;
4535: }
4536: }
4537: else if (GET_CODE (PATTERN (p)) == SET
4538: && SET_DEST (PATTERN (p)) == v->src_reg)
4539: biv_increment_seen = 1;
4540: else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
4541: last_giv_use = p;
4542: }
4543: }
4544:
4545: /* Now that the lifetime of the giv is known, check for branches
4546: from within the lifetime to outside the lifetime if it is still
4547: replaceable. */
4548:
4549: if (v->replaceable)
4550: {
4551: p = v->insn;
4552: while (1)
4553: {
4554: p = NEXT_INSN (p);
4555: if (p == loop_end)
4556: p = NEXT_INSN (loop_start);
4557: if (p == last_giv_use)
4558: break;
4559:
4560: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
4561: && LABEL_NAME (JUMP_LABEL (p))
4562: && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
4563: && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
4564: || (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
4565: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
4566: {
4567: v->replaceable = 0;
4568: v->not_replaceable = 1;
4569:
4570: if (loop_dump_stream)
4571: fprintf (loop_dump_stream,
4572: "Found branch outside giv lifetime.\n");
4573:
4574: break;
4575: }
4576: }
4577: }
4578:
4579: /* If it is replaceable, then save the final value. */
4580: if (v->replaceable)
4581: v->final_value = final_value;
4582: }
4583:
4584: if (loop_dump_stream && v->replaceable)
4585: fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
4586: INSN_UID (v->insn), REGNO (v->dest_reg));
4587: }
4588:
4589: /* Update the status of whether a giv can derive other givs.
4590:
4591: We need to do something special if there is or may be an update to the biv
4592: between the time the giv is defined and the time it is used to derive
4593: another giv.
4594:
4595: In addition, a giv that is only conditionally set is not allowed to
4596: derive another giv once a label has been passed.
4597:
4598: The cases we look at are when a label or an update to a biv is passed. */
4599:
4600: static void
4601: update_giv_derive (p)
4602: rtx p;
4603: {
4604: struct iv_class *bl;
4605: struct induction *biv, *giv;
4606: rtx tem;
4607: int dummy;
4608:
4609: /* Search all IV classes, then all bivs, and finally all givs.
4610:
1.1.1.3 root 4611: There are three cases we are concerned with. First we have the situation
1.1 root 4612: of a giv that is only updated conditionally. In that case, it may not
4613: derive any givs after a label is passed.
4614:
4615: The second case is when a biv update occurs, or may occur, after the
4616: definition of a giv. For certain biv updates (see below) that are
4617: known to occur between the giv definition and use, we can adjust the
4618: giv definition. For others, or when the biv update is conditional,
4619: we must prevent the giv from deriving any other givs. There are two
4620: sub-cases within this case.
4621:
4622: If this is a label, we are concerned with any biv update that is done
4623: conditionally, since it may be done after the giv is defined followed by
4624: a branch here (actually, we need to pass both a jump and a label, but
4625: this extra tracking doesn't seem worth it).
4626:
1.1.1.3 root 4627: If this is a jump, we are concerned about any biv update that may be
4628: executed multiple times. We are actually only concerned about
4629: backward jumps, but it is probably not worth performing the test
4630: on the jump again here.
4631:
4632: If this is a biv update, we must adjust the giv status to show that a
1.1 root 4633: subsequent biv update was performed. If this adjustment cannot be done,
4634: the giv cannot derive further givs. */
4635:
4636: for (bl = loop_iv_list; bl; bl = bl->next)
4637: for (biv = bl->biv; biv; biv = biv->next_iv)
1.1.1.3 root 4638: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
4639: || biv->insn == p)
1.1 root 4640: {
4641: for (giv = bl->giv; giv; giv = giv->next_iv)
4642: {
4643: /* If cant_derive is already true, there is no point in
4644: checking all of these conditions again. */
4645: if (giv->cant_derive)
4646: continue;
4647:
4648: /* If this giv is conditionally set and we have passed a label,
4649: it cannot derive anything. */
4650: if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
4651: giv->cant_derive = 1;
4652:
4653: /* Skip givs that have mult_val == 0, since
4654: they are really invariants. Also skip those that are
4655: replaceable, since we know their lifetime doesn't contain
4656: any biv update. */
4657: else if (giv->mult_val == const0_rtx || giv->replaceable)
4658: continue;
4659:
4660: /* The only way we can allow this giv to derive another
4661: is if this is a biv increment and we can form the product
4662: of biv->add_val and giv->mult_val. In this case, we will
4663: be able to compute a compensation. */
4664: else if (biv->insn == p)
4665: {
1.1.1.2 root 4666: tem = 0;
4667:
4668: if (biv->mult_val == const1_rtx)
4669: tem = simplify_giv_expr (gen_rtx (MULT, giv->mode,
4670: biv->add_val,
4671: giv->mult_val),
4672: &dummy);
4673:
4674: if (tem && giv->derive_adjustment)
4675: tem = simplify_giv_expr (gen_rtx (PLUS, giv->mode, tem,
4676: giv->derive_adjustment),
4677: &dummy);
4678: if (tem)
1.1 root 4679: giv->derive_adjustment = tem;
4680: else
4681: giv->cant_derive = 1;
4682: }
1.1.1.3 root 4683: else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
4684: || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
1.1 root 4685: giv->cant_derive = 1;
4686: }
4687: }
4688: }
4689:
4690: /* Check whether an insn is an increment legitimate for a basic induction var.
1.1.1.4 root 4691: X is the source of insn P.
1.1 root 4692: DEST_REG is the putative biv, also the destination of the insn.
4693: We accept patterns of these forms:
1.1.1.4 root 4694: REG = REG + INVARIANT (includes REG = REG - CONSTANT)
1.1 root 4695: REG = INVARIANT + REG
4696:
4697: If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX,
4698: and store the additive term into *INC_VAL.
4699:
4700: If X is an assignment of an invariant into DEST_REG, we set
4701: *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL.
4702:
1.1.1.4 root 4703: We also want to detect a BIV when it corresponds to a variable
4704: whose mode was promoted via PROMOTED_MODE. In that case, an increment
4705: of the variable may be a PLUS that adds a SUBREG of that variable to
4706: an invariant and then sign- or zero-extends the result of the PLUS
4707: into the variable.
4708:
4709: Most GIVs in such cases will be in the promoted mode, since that is the
4710: probably the natural computation mode (and almost certainly the mode
4711: used for addresses) on the machine. So we view the pseudo-reg containing
4712: the variable as the BIV, as if it were simply incremented.
4713:
4714: Note that treating the entire pseudo as a BIV will result in making
4715: simple increments to any GIVs based on it. However, if the variable
4716: overflows in its declared mode but not its promoted mode, the result will
4717: be incorrect. This is acceptable if the variable is signed, since
4718: overflows in such cases are undefined, but not if it is unsigned, since
4719: those overflows are defined. So we only check for SIGN_EXTEND and
4720: not ZERO_EXTEND.
4721:
4722: If we cannot find a biv, we return 0. */
1.1 root 4723:
4724: static int
1.1.1.4 root 4725: basic_induction_var (x, dest_reg, p, inc_val, mult_val)
1.1 root 4726: register rtx x;
1.1.1.4 root 4727: rtx p;
1.1 root 4728: rtx dest_reg;
4729: rtx *inc_val;
4730: rtx *mult_val;
4731: {
4732: register enum rtx_code code;
4733: rtx arg;
1.1.1.4 root 4734: rtx insn, set = 0;
1.1 root 4735:
4736: code = GET_CODE (x);
4737: switch (code)
4738: {
4739: case PLUS:
1.1.1.4 root 4740: if (XEXP (x, 0) == dest_reg
4741: || (GET_CODE (XEXP (x, 0)) == SUBREG
4742: && SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
4743: && SUBREG_REG (XEXP (x, 0)) == dest_reg))
1.1 root 4744: arg = XEXP (x, 1);
1.1.1.4 root 4745: else if (XEXP (x, 1) == dest_reg
4746: || (GET_CODE (XEXP (x, 1)) == SUBREG
4747: && SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
4748: && SUBREG_REG (XEXP (x, 1)) == dest_reg))
1.1 root 4749: arg = XEXP (x, 0);
4750: else
4751: return 0;
4752:
4753: if (invariant_p (arg) != 1)
4754: return 0;
4755:
1.1.1.4 root 4756: *inc_val = convert_to_mode (GET_MODE (dest_reg), arg, 0);;
1.1 root 4757: *mult_val = const1_rtx;
4758: return 1;
4759:
1.1.1.4 root 4760: case SUBREG:
4761: /* If this is a SUBREG for a promoted variable, check the inner
4762: value. */
4763: if (SUBREG_PROMOTED_VAR_P (x))
4764: return basic_induction_var (SUBREG_REG (x), dest_reg, p,
4765: inc_val, mult_val);
1.1 root 4766:
1.1.1.4 root 4767: case REG:
4768: /* If this register is assigned in the previous insn, look at its
4769: source, but don't go outside the loop or past a label. */
4770:
4771: for (insn = PREV_INSN (p);
4772: (insn && GET_CODE (insn) == NOTE
4773: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
4774: insn = PREV_INSN (insn))
4775: ;
4776:
4777: if (insn)
4778: set = single_set (insn);
4779:
4780: if (set != 0 && SET_DEST (set) == x)
4781: return basic_induction_var (SET_SRC (set), dest_reg, insn,
4782: inc_val, mult_val);
4783: /* ... fall through ... */
1.1 root 4784:
4785: /* Can accept constant setting of biv only when inside inner most loop.
4786: Otherwise, a biv of an inner loop may be incorrectly recognized
4787: as a biv of the outer loop,
4788: causing code to be moved INTO the inner loop. */
4789: case MEM:
4790: if (invariant_p (x) != 1)
4791: return 0;
4792: case CONST_INT:
4793: case SYMBOL_REF:
4794: case CONST:
4795: if (loops_enclosed == 1)
4796: {
1.1.1.4 root 4797: *inc_val = convert_to_mode (GET_MODE (dest_reg), x, 0);;
1.1 root 4798: *mult_val = const0_rtx;
4799: return 1;
4800: }
4801: else
4802: return 0;
4803:
1.1.1.4 root 4804: case SIGN_EXTEND:
4805: return basic_induction_var (XEXP (x, 0), dest_reg, p,
4806: inc_val, mult_val);
4807: case ASHIFTRT:
4808: /* Similar, since this can be a sign extension. */
4809: for (insn = PREV_INSN (p);
4810: (insn && GET_CODE (insn) == NOTE
4811: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
4812: insn = PREV_INSN (insn))
4813: ;
4814:
4815: if (insn)
4816: set = single_set (insn);
4817:
4818: if (set && SET_DEST (set) == XEXP (x, 0)
4819: && GET_CODE (XEXP (x, 1)) == CONST_INT
4820: && INTVAL (XEXP (x, 1)) >= 0
4821: && GET_CODE (SET_SRC (set)) == ASHIFT
4822: && XEXP (x, 1) == XEXP (SET_SRC (set), 1))
4823: return basic_induction_var (XEXP (SET_SRC (set), 0), dest_reg, insn,
4824: inc_val, mult_val);
4825: return 0;
4826:
1.1 root 4827: default:
4828: return 0;
4829: }
4830: }
4831:
4832: /* A general induction variable (giv) is any quantity that is a linear
4833: function of a basic induction variable,
4834: i.e. giv = biv * mult_val + add_val.
4835: The coefficients can be any loop invariant quantity.
4836: A giv need not be computed directly from the biv;
4837: it can be computed by way of other givs. */
4838:
4839: /* Determine whether X computes a giv.
4840: If it does, return a nonzero value
4841: which is the benefit from eliminating the computation of X;
4842: set *SRC_REG to the register of the biv that it is computed from;
4843: set *ADD_VAL and *MULT_VAL to the coefficients,
4844: such that the value of X is biv * mult + add; */
4845:
4846: static int
4847: general_induction_var (x, src_reg, add_val, mult_val)
4848: rtx x;
4849: rtx *src_reg;
4850: rtx *add_val;
4851: rtx *mult_val;
4852: {
4853: rtx orig_x = x;
4854: int benefit = 0;
4855: char *storage;
4856:
4857: /* If this is an invariant, forget it, it isn't a giv. */
4858: if (invariant_p (x) == 1)
4859: return 0;
4860:
4861: /* See if the expression could be a giv and get its form.
4862: Mark our place on the obstack in case we don't find a giv. */
4863: storage = (char *) oballoc (0);
4864: x = simplify_giv_expr (x, &benefit);
4865: if (x == 0)
4866: {
4867: obfree (storage);
4868: return 0;
4869: }
4870:
4871: switch (GET_CODE (x))
4872: {
4873: case USE:
4874: case CONST_INT:
4875: /* Since this is now an invariant and wasn't before, it must be a giv
4876: with MULT_VAL == 0. It doesn't matter which BIV we associate this
4877: with. */
4878: *src_reg = loop_iv_list->biv->dest_reg;
4879: *mult_val = const0_rtx;
4880: *add_val = x;
4881: break;
4882:
4883: case REG:
4884: /* This is equivalent to a BIV. */
4885: *src_reg = x;
4886: *mult_val = const1_rtx;
4887: *add_val = const0_rtx;
4888: break;
4889:
4890: case PLUS:
4891: /* Either (plus (biv) (invar)) or
4892: (plus (mult (biv) (invar_1)) (invar_2)). */
4893: if (GET_CODE (XEXP (x, 0)) == MULT)
4894: {
4895: *src_reg = XEXP (XEXP (x, 0), 0);
4896: *mult_val = XEXP (XEXP (x, 0), 1);
4897: }
4898: else
4899: {
4900: *src_reg = XEXP (x, 0);
4901: *mult_val = const1_rtx;
4902: }
4903: *add_val = XEXP (x, 1);
4904: break;
4905:
4906: case MULT:
4907: /* ADD_VAL is zero. */
4908: *src_reg = XEXP (x, 0);
4909: *mult_val = XEXP (x, 1);
4910: *add_val = const0_rtx;
4911: break;
4912:
4913: default:
4914: abort ();
4915: }
4916:
4917: /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be
4918: unless they are CONST_INT). */
4919: if (GET_CODE (*add_val) == USE)
4920: *add_val = XEXP (*add_val, 0);
4921: if (GET_CODE (*mult_val) == USE)
4922: *mult_val = XEXP (*mult_val, 0);
4923:
1.1.1.3 root 4924: benefit += rtx_cost (orig_x, SET);
1.1 root 4925:
4926: /* Always return some benefit if this is a giv so it will be detected
4927: as such. This allows elimination of bivs that might otherwise
4928: not be eliminated. */
4929: return benefit == 0 ? 1 : benefit;
4930: }
4931:
4932: /* Given an expression, X, try to form it as a linear function of a biv.
4933: We will canonicalize it to be of the form
4934: (plus (mult (BIV) (invar_1))
4935: (invar_2))
1.1.1.3 root 4936: with possible degeneracies.
1.1 root 4937:
4938: The invariant expressions must each be of a form that can be used as a
4939: machine operand. We surround then with a USE rtx (a hack, but localized
4940: and certainly unambiguous!) if not a CONST_INT for simplicity in this
4941: routine; it is the caller's responsibility to strip them.
4942:
4943: If no such canonicalization is possible (i.e., two biv's are used or an
4944: expression that is neither invariant nor a biv or giv), this routine
4945: returns 0.
4946:
4947: For a non-zero return, the result will have a code of CONST_INT, USE,
4948: REG (for a BIV), PLUS, or MULT. No other codes will occur.
4949:
4950: *BENEFIT will be incremented by the benefit of any sub-giv encountered. */
4951:
4952: static rtx
4953: simplify_giv_expr (x, benefit)
4954: rtx x;
4955: int *benefit;
4956: {
4957: enum machine_mode mode = GET_MODE (x);
4958: rtx arg0, arg1;
4959: rtx tem;
4960:
4961: /* If this is not an integer mode, or if we cannot do arithmetic in this
4962: mode, this can't be a giv. */
4963: if (mode != VOIDmode
4964: && (GET_MODE_CLASS (mode) != MODE_INT
1.1.1.4 root 4965: || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
1.1 root 4966: return 0;
4967:
4968: switch (GET_CODE (x))
4969: {
4970: case PLUS:
4971: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
4972: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
4973: if (arg0 == 0 || arg1 == 0)
4974: return 0;
4975:
4976: /* Put constant last, CONST_INT last if both constant. */
4977: if ((GET_CODE (arg0) == USE
4978: || GET_CODE (arg0) == CONST_INT)
4979: && GET_CODE (arg1) != CONST_INT)
4980: tem = arg0, arg0 = arg1, arg1 = tem;
4981:
4982: /* Handle addition of zero, then addition of an invariant. */
4983: if (arg1 == const0_rtx)
4984: return arg0;
4985: else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
4986: switch (GET_CODE (arg0))
4987: {
4988: case CONST_INT:
4989: case USE:
4990: /* Both invariant. Only valid if sum is machine operand.
4991: First strip off possible USE on first operand. */
4992: if (GET_CODE (arg0) == USE)
4993: arg0 = XEXP (arg0, 0);
4994:
4995: tem = 0;
4996: if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
4997: {
4998: tem = plus_constant (arg0, INTVAL (arg1));
4999: if (GET_CODE (tem) != CONST_INT)
5000: tem = gen_rtx (USE, mode, tem);
5001: }
5002:
5003: return tem;
5004:
5005: case REG:
5006: case MULT:
5007: /* biv + invar or mult + invar. Return sum. */
5008: return gen_rtx (PLUS, mode, arg0, arg1);
5009:
5010: case PLUS:
5011: /* (a + invar_1) + invar_2. Associate. */
5012: return simplify_giv_expr (gen_rtx (PLUS, mode,
5013: XEXP (arg0, 0),
5014: gen_rtx (PLUS, mode,
5015: XEXP (arg0, 1), arg1)),
5016: benefit);
5017:
5018: default:
5019: abort ();
5020: }
5021:
5022: /* Each argument must be either REG, PLUS, or MULT. Convert REG to
5023: MULT to reduce cases. */
5024: if (GET_CODE (arg0) == REG)
5025: arg0 = gen_rtx (MULT, mode, arg0, const1_rtx);
5026: if (GET_CODE (arg1) == REG)
5027: arg1 = gen_rtx (MULT, mode, arg1, const1_rtx);
5028:
5029: /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT.
5030: Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT.
5031: Recurse to associate the second PLUS. */
5032: if (GET_CODE (arg1) == MULT)
5033: tem = arg0, arg0 = arg1, arg1 = tem;
5034:
5035: if (GET_CODE (arg1) == PLUS)
5036: return simplify_giv_expr (gen_rtx (PLUS, mode,
5037: gen_rtx (PLUS, mode,
5038: arg0, XEXP (arg1, 0)),
5039: XEXP (arg1, 1)),
5040: benefit);
5041:
5042: /* Now must have MULT + MULT. Distribute if same biv, else not giv. */
5043: if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
5044: abort ();
5045:
5046: if (XEXP (arg0, 0) != XEXP (arg1, 0))
5047: return 0;
5048:
5049: return simplify_giv_expr (gen_rtx (MULT, mode,
5050: XEXP (arg0, 0),
5051: gen_rtx (PLUS, mode,
5052: XEXP (arg0, 1),
5053: XEXP (arg1, 1))),
5054: benefit);
5055:
5056: case MINUS:
5057: /* Handle "a - b" as "a + b * (-1)". */
5058: return simplify_giv_expr (gen_rtx (PLUS, mode,
5059: XEXP (x, 0),
5060: gen_rtx (MULT, mode,
1.1.1.4 root 5061: XEXP (x, 1), constm1_rtx)),
1.1 root 5062: benefit);
5063:
5064: case MULT:
5065: arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
5066: arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
5067: if (arg0 == 0 || arg1 == 0)
5068: return 0;
5069:
5070: /* Put constant last, CONST_INT last if both constant. */
5071: if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
5072: && GET_CODE (arg1) != CONST_INT)
5073: tem = arg0, arg0 = arg1, arg1 = tem;
5074:
5075: /* If second argument is not now constant, not giv. */
5076: if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
5077: return 0;
5078:
5079: /* Handle multiply by 0 or 1. */
5080: if (arg1 == const0_rtx)
5081: return const0_rtx;
5082:
5083: else if (arg1 == const1_rtx)
5084: return arg0;
5085:
5086: switch (GET_CODE (arg0))
5087: {
5088: case REG:
5089: /* biv * invar. Done. */
5090: return gen_rtx (MULT, mode, arg0, arg1);
5091:
5092: case CONST_INT:
5093: /* Product of two constants. */
1.1.1.4 root 5094: return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
1.1 root 5095:
5096: case USE:
5097: /* invar * invar. Not giv. */
5098: return 0;
5099:
5100: case MULT:
5101: /* (a * invar_1) * invar_2. Associate. */
5102: return simplify_giv_expr (gen_rtx (MULT, mode,
5103: XEXP (arg0, 0),
5104: gen_rtx (MULT, mode,
5105: XEXP (arg0, 1), arg1)),
5106: benefit);
5107:
5108: case PLUS:
5109: /* (a + invar_1) * invar_2. Distribute. */
5110: return simplify_giv_expr (gen_rtx (PLUS, mode,
5111: gen_rtx (MULT, mode,
5112: XEXP (arg0, 0), arg1),
5113: gen_rtx (MULT, mode,
5114: XEXP (arg0, 1), arg1)),
5115: benefit);
5116:
5117: default:
5118: abort ();
5119: }
5120:
5121: case ASHIFT:
5122: case LSHIFT:
5123: /* Shift by constant is multiply by power of two. */
5124: if (GET_CODE (XEXP (x, 1)) != CONST_INT)
5125: return 0;
5126:
5127: return simplify_giv_expr (gen_rtx (MULT, mode,
5128: XEXP (x, 0),
1.1.1.4 root 5129: GEN_INT ((HOST_WIDE_INT) 1
5130: << INTVAL (XEXP (x, 1)))),
1.1 root 5131: benefit);
5132:
5133: case NEG:
5134: /* "-a" is "a * (-1)" */
1.1.1.4 root 5135: return simplify_giv_expr (gen_rtx (MULT, mode, XEXP (x, 0), constm1_rtx),
1.1 root 5136: benefit);
5137:
5138: case NOT:
5139: /* "~a" is "-a - 1". Silly, but easy. */
5140: return simplify_giv_expr (gen_rtx (MINUS, mode,
5141: gen_rtx (NEG, mode, XEXP (x, 0)),
5142: const1_rtx),
5143: benefit);
5144:
5145: case USE:
5146: /* Already in proper form for invariant. */
5147: return x;
5148:
5149: case REG:
5150: /* If this is a new register, we can't deal with it. */
5151: if (REGNO (x) >= max_reg_before_loop)
5152: return 0;
5153:
5154: /* Check for biv or giv. */
5155: switch (reg_iv_type[REGNO (x)])
5156: {
5157: case BASIC_INDUCT:
5158: return x;
5159: case GENERAL_INDUCT:
5160: {
5161: struct induction *v = reg_iv_info[REGNO (x)];
5162:
5163: /* Form expression from giv and add benefit. Ensure this giv
5164: can derive another and subtract any needed adjustment if so. */
5165: *benefit += v->benefit;
5166: if (v->cant_derive)
5167: return 0;
5168:
5169: tem = gen_rtx (PLUS, mode, gen_rtx (MULT, mode,
5170: v->src_reg, v->mult_val),
5171: v->add_val);
5172: if (v->derive_adjustment)
5173: tem = gen_rtx (MINUS, mode, tem, v->derive_adjustment);
5174: return simplify_giv_expr (tem, benefit);
5175: }
5176: }
5177:
5178: /* Fall through to general case. */
5179: default:
5180: /* If invariant, return as USE (unless CONST_INT).
5181: Otherwise, not giv. */
5182: if (GET_CODE (x) == USE)
5183: x = XEXP (x, 0);
5184:
5185: if (invariant_p (x) == 1)
5186: {
5187: if (GET_CODE (x) == CONST_INT)
5188: return x;
5189: else
5190: return gen_rtx (USE, mode, x);
5191: }
5192: else
5193: return 0;
5194: }
5195: }
5196:
5197: /* Help detect a giv that is calculated by several consecutive insns;
5198: for example,
5199: giv = biv * M
5200: giv = giv + A
5201: The caller has already identified the first insn P as having a giv as dest;
5202: we check that all other insns that set the same register follow
5203: immediately after P, that they alter nothing else,
5204: and that the result of the last is still a giv.
5205:
5206: The value is 0 if the reg set in P is not really a giv.
5207: Otherwise, the value is the amount gained by eliminating
5208: all the consecutive insns that compute the value.
5209:
5210: FIRST_BENEFIT is the amount gained by eliminating the first insn, P.
5211: SRC_REG is the reg of the biv; DEST_REG is the reg of the giv.
5212:
5213: The coefficients of the ultimate giv value are stored in
5214: *MULT_VAL and *ADD_VAL. */
5215:
5216: static int
5217: consec_sets_giv (first_benefit, p, src_reg, dest_reg,
5218: add_val, mult_val)
5219: int first_benefit;
5220: rtx p;
5221: rtx src_reg;
5222: rtx dest_reg;
5223: rtx *add_val;
5224: rtx *mult_val;
5225: {
5226: int count;
5227: enum rtx_code code;
5228: int benefit;
5229: rtx temp;
5230: rtx set;
5231:
5232: /* Indicate that this is a giv so that we can update the value produced in
5233: each insn of the multi-insn sequence.
5234:
5235: This induction structure will be used only by the call to
5236: general_induction_var below, so we can allocate it on our stack.
5237: If this is a giv, our caller will replace the induct var entry with
5238: a new induction structure. */
5239: struct induction *v
5240: = (struct induction *) alloca (sizeof (struct induction));
5241: v->src_reg = src_reg;
5242: v->mult_val = *mult_val;
5243: v->add_val = *add_val;
5244: v->benefit = first_benefit;
5245: v->cant_derive = 0;
5246: v->derive_adjustment = 0;
5247:
5248: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT;
5249: reg_iv_info[REGNO (dest_reg)] = v;
5250:
5251: count = n_times_set[REGNO (dest_reg)] - 1;
5252:
5253: while (count > 0)
5254: {
5255: p = NEXT_INSN (p);
5256: code = GET_CODE (p);
5257:
5258: /* If libcall, skip to end of call sequence. */
1.1.1.4 root 5259: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
1.1 root 5260: p = XEXP (temp, 0);
5261:
5262: if (code == INSN
5263: && (set = single_set (p))
5264: && GET_CODE (SET_DEST (set)) == REG
5265: && SET_DEST (set) == dest_reg
5266: && ((benefit = general_induction_var (SET_SRC (set), &src_reg,
5267: add_val, mult_val))
5268: /* Giv created by equivalent expression. */
1.1.1.4 root 5269: || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
1.1 root 5270: && (benefit = general_induction_var (XEXP (temp, 0), &src_reg,
5271: add_val, mult_val))))
5272: && src_reg == v->src_reg)
5273: {
1.1.1.4 root 5274: if (find_reg_note (p, REG_RETVAL, NULL_RTX))
1.1 root 5275: benefit += libcall_benefit (p);
5276:
5277: count--;
5278: v->mult_val = *mult_val;
5279: v->add_val = *add_val;
5280: v->benefit = benefit;
5281: }
5282: else if (code != NOTE)
5283: {
5284: /* Allow insns that set something other than this giv to a
5285: constant. Such insns are needed on machines which cannot
5286: include long constants and should not disqualify a giv. */
5287: if (code == INSN
5288: && (set = single_set (p))
5289: && SET_DEST (set) != dest_reg
5290: && CONSTANT_P (SET_SRC (set)))
5291: continue;
5292:
5293: reg_iv_type[REGNO (dest_reg)] = UNKNOWN_INDUCT;
5294: return 0;
5295: }
5296: }
5297:
5298: return v->benefit;
5299: }
5300:
5301: /* Return an rtx, if any, that expresses giv G2 as a function of the register
5302: represented by G1. If no such expression can be found, or it is clear that
5303: it cannot possibly be a valid address, 0 is returned.
5304:
5305: To perform the computation, we note that
5306: G1 = a * v + b and
5307: G2 = c * v + d
5308: where `v' is the biv.
5309:
5310: So G2 = (c/a) * G1 + (d - b*c/a) */
5311:
5312: #ifdef ADDRESS_COST
5313: static rtx
5314: express_from (g1, g2)
5315: struct induction *g1, *g2;
5316: {
5317: rtx mult, add;
5318:
5319: /* The value that G1 will be multiplied by must be a constant integer. Also,
5320: the only chance we have of getting a valid address is if b*c/a (see above
5321: for notation) is also an integer. */
5322: if (GET_CODE (g1->mult_val) != CONST_INT
5323: || GET_CODE (g2->mult_val) != CONST_INT
5324: || GET_CODE (g1->add_val) != CONST_INT
5325: || g1->mult_val == const0_rtx
5326: || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
5327: return 0;
5328:
1.1.1.4 root 5329: mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
1.1 root 5330: add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult));
5331:
5332: /* Form simplified final result. */
5333: if (mult == const0_rtx)
5334: return add;
5335: else if (mult == const1_rtx)
5336: mult = g1->dest_reg;
5337: else
5338: mult = gen_rtx (MULT, g2->mode, g1->dest_reg, mult);
5339:
5340: if (add == const0_rtx)
5341: return mult;
5342: else
5343: return gen_rtx (PLUS, g2->mode, mult, add);
5344: }
5345: #endif
5346:
5347: /* Return 1 if giv G2 can be combined with G1. This means that G2 can use
5348: (either directly or via an address expression) a register used to represent
5349: G1. Set g2->new_reg to a represtation of G1 (normally just
5350: g1->dest_reg). */
5351:
5352: static int
5353: combine_givs_p (g1, g2)
5354: struct induction *g1, *g2;
5355: {
5356: rtx tem;
5357:
5358: /* If these givs are identical, they can be combined. */
5359: if (rtx_equal_p (g1->mult_val, g2->mult_val)
5360: && rtx_equal_p (g1->add_val, g2->add_val))
5361: {
5362: g2->new_reg = g1->dest_reg;
5363: return 1;
5364: }
5365:
5366: #ifdef ADDRESS_COST
5367: /* If G2 can be expressed as a function of G1 and that function is valid
5368: as an address and no more expensive than using a register for G2,
5369: the expression of G2 in terms of G1 can be used. */
5370: if (g2->giv_type == DEST_ADDR
5371: && (tem = express_from (g1, g2)) != 0
5372: && memory_address_p (g2->mem_mode, tem)
5373: && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location))
5374: {
5375: g2->new_reg = tem;
5376: return 1;
5377: }
5378: #endif
5379:
5380: return 0;
5381: }
5382:
5383: /* Check all pairs of givs for iv_class BL and see if any can be combined with
5384: any other. If so, point SAME to the giv combined with and set NEW_REG to
5385: be an expression (in terms of the other giv's DEST_REG) equivalent to the
5386: giv. Also, update BENEFIT and related fields for cost/benefit analysis. */
5387:
5388: static void
5389: combine_givs (bl)
5390: struct iv_class *bl;
5391: {
5392: struct induction *g1, *g2;
5393: int pass;
5394:
5395: for (g1 = bl->giv; g1; g1 = g1->next_iv)
5396: for (pass = 0; pass <= 1; pass++)
5397: for (g2 = bl->giv; g2; g2 = g2->next_iv)
5398: if (g1 != g2
5399: /* First try to combine with replaceable givs, then all givs. */
5400: && (g1->replaceable || pass == 1)
5401: /* If either has already been combined or is to be ignored, can't
5402: combine. */
5403: && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
5404: /* If something has been based on G2, G2 cannot itself be based
5405: on something else. */
5406: && ! g2->combined_with
5407: && combine_givs_p (g1, g2))
5408: {
5409: /* g2->new_reg set by `combine_givs_p' */
5410: g2->same = g1;
5411: g1->combined_with = 1;
5412: g1->benefit += g2->benefit;
5413: /* ??? The new final_[bg]iv_value code does a much better job
5414: of finding replaceable giv's, and hence this code may no
5415: longer be necessary. */
5416: if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
5417: g1->benefit -= copy_cost;
5418: g1->lifetime += g2->lifetime;
5419: g1->times_used += g2->times_used;
5420:
5421: if (loop_dump_stream)
5422: fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
5423: INSN_UID (g2->insn), INSN_UID (g1->insn));
5424: }
5425: }
5426:
5427: /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
5428:
5429: void
5430: emit_iv_add_mult (b, m, a, reg, insert_before)
5431: rtx b; /* initial value of basic induction variable */
5432: rtx m; /* multiplicative constant */
5433: rtx a; /* additive constant */
5434: rtx reg; /* destination register */
5435: rtx insert_before;
5436: {
5437: rtx seq;
5438: rtx result;
5439:
5440: /* Prevent unexpected sharing of these rtx. */
5441: a = copy_rtx (a);
5442: b = copy_rtx (b);
5443:
5444: /* Increase the lifetime of any invariants moved further in code. */
5445: update_reg_last_use (a, insert_before);
5446: update_reg_last_use (b, insert_before);
5447: update_reg_last_use (m, insert_before);
5448:
5449: start_sequence ();
5450: result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
5451: if (reg != result)
5452: emit_move_insn (reg, result);
5453: seq = gen_sequence ();
5454: end_sequence ();
5455:
5456: emit_insn_before (seq, insert_before);
5457: }
5458:
5459: /* Test whether A * B can be computed without
5460: an actual multiply insn. Value is 1 if so. */
5461:
5462: static int
5463: product_cheap_p (a, b)
5464: rtx a;
5465: rtx b;
5466: {
5467: int i;
5468: rtx tmp;
5469: struct obstack *old_rtl_obstack = rtl_obstack;
5470: char *storage = (char *) obstack_alloc (&temp_obstack, 0);
5471: int win = 1;
5472:
5473: /* If only one is constant, make it B. */
5474: if (GET_CODE (a) == CONST_INT)
5475: tmp = a, a = b, b = tmp;
5476:
5477: /* If first constant, both constant, so don't need multiply. */
5478: if (GET_CODE (a) == CONST_INT)
5479: return 1;
5480:
5481: /* If second not constant, neither is constant, so would need multiply. */
5482: if (GET_CODE (b) != CONST_INT)
5483: return 0;
5484:
5485: /* One operand is constant, so might not need multiply insn. Generate the
5486: code for the multiply and see if a call or multiply, or long sequence
5487: of insns is generated. */
5488:
5489: rtl_obstack = &temp_obstack;
5490: start_sequence ();
1.1.1.4 root 5491: expand_mult (GET_MODE (a), a, b, NULL_RTX, 0);
1.1 root 5492: tmp = gen_sequence ();
5493: end_sequence ();
5494:
5495: if (GET_CODE (tmp) == SEQUENCE)
5496: {
5497: if (XVEC (tmp, 0) == 0)
5498: win = 1;
5499: else if (XVECLEN (tmp, 0) > 3)
5500: win = 0;
5501: else
5502: for (i = 0; i < XVECLEN (tmp, 0); i++)
5503: {
5504: rtx insn = XVECEXP (tmp, 0, i);
5505:
5506: if (GET_CODE (insn) != INSN
5507: || (GET_CODE (PATTERN (insn)) == SET
5508: && GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
5509: || (GET_CODE (PATTERN (insn)) == PARALLEL
5510: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
5511: && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
5512: {
5513: win = 0;
5514: break;
5515: }
5516: }
5517: }
5518: else if (GET_CODE (tmp) == SET
5519: && GET_CODE (SET_SRC (tmp)) == MULT)
5520: win = 0;
5521: else if (GET_CODE (tmp) == PARALLEL
5522: && GET_CODE (XVECEXP (tmp, 0, 0)) == SET
5523: && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
5524: win = 0;
5525:
5526: /* Free any storage we obtained in generating this multiply and restore rtl
5527: allocation to its normal obstack. */
5528: obstack_free (&temp_obstack, storage);
5529: rtl_obstack = old_rtl_obstack;
5530:
5531: return win;
5532: }
5533:
5534: /* Check to see if loop can be terminated by a "decrement and branch until
5535: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so.
5536: Also try reversing an increment loop to a decrement loop
5537: to see if the optimization can be performed.
5538: Value is nonzero if optimization was performed. */
5539:
5540: /* This is useful even if the architecture doesn't have such an insn,
5541: because it might change a loops which increments from 0 to n to a loop
5542: which decrements from n to 0. A loop that decrements to zero is usually
5543: faster than one that increments from zero. */
5544:
5545: /* ??? This could be rewritten to use some of the loop unrolling procedures,
5546: such as approx_final_value, biv_total_increment, loop_iterations, and
5547: final_[bg]iv_value. */
5548:
5549: static int
5550: check_dbra_loop (loop_end, insn_count, loop_start)
5551: rtx loop_end;
5552: int insn_count;
5553: rtx loop_start;
5554: {
5555: struct iv_class *bl;
5556: rtx reg;
5557: rtx jump_label;
5558: rtx final_value;
5559: rtx start_value;
5560: enum rtx_code branch_code;
5561: rtx new_add_val;
5562: rtx comparison;
5563: rtx before_comparison;
5564: rtx p;
5565:
5566: /* If last insn is a conditional branch, and the insn before tests a
5567: register value, try to optimize it. Otherwise, we can't do anything. */
5568:
5569: comparison = get_condition_for_loop (PREV_INSN (loop_end));
5570: if (comparison == 0)
5571: return 0;
5572:
5573: /* Check all of the bivs to see if the compare uses one of them.
5574: Skip biv's set more than once because we can't guarantee that
5575: it will be zero on the last iteration. Also skip if the biv is
5576: used between its update and the test insn. */
5577:
5578: for (bl = loop_iv_list; bl; bl = bl->next)
5579: {
5580: if (bl->biv_count == 1
5581: && bl->biv->dest_reg == XEXP (comparison, 0)
5582: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
5583: PREV_INSN (PREV_INSN (loop_end))))
5584: break;
5585: }
5586:
5587: if (! bl)
5588: return 0;
5589:
5590: /* Look for the case where the basic induction variable is always
5591: nonnegative, and equals zero on the last iteration.
5592: In this case, add a reg_note REG_NONNEG, which allows the
5593: m68k DBRA instruction to be used. */
5594:
5595: if (((GET_CODE (comparison) == GT
5596: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5597: && INTVAL (XEXP (comparison, 1)) == -1)
5598: || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
5599: && GET_CODE (bl->biv->add_val) == CONST_INT
5600: && INTVAL (bl->biv->add_val) < 0)
5601: {
5602: /* Initial value must be greater than 0,
5603: init_val % -dec_value == 0 to ensure that it equals zero on
5604: the last iteration */
5605:
5606: if (GET_CODE (bl->initial_value) == CONST_INT
5607: && INTVAL (bl->initial_value) > 0
5608: && (INTVAL (bl->initial_value) %
5609: (-INTVAL (bl->biv->add_val))) == 0)
5610: {
5611: /* register always nonnegative, add REG_NOTE to branch */
5612: REG_NOTES (PREV_INSN (loop_end))
1.1.1.4 root 5613: = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX,
1.1 root 5614: REG_NOTES (PREV_INSN (loop_end)));
5615: bl->nonneg = 1;
5616:
5617: return 1;
5618: }
5619:
5620: /* If the decrement is 1 and the value was tested as >= 0 before
5621: the loop, then we can safely optimize. */
5622: for (p = loop_start; p; p = PREV_INSN (p))
5623: {
5624: if (GET_CODE (p) == CODE_LABEL)
5625: break;
5626: if (GET_CODE (p) != JUMP_INSN)
5627: continue;
5628:
5629: before_comparison = get_condition_for_loop (p);
5630: if (before_comparison
5631: && XEXP (before_comparison, 0) == bl->biv->dest_reg
5632: && GET_CODE (before_comparison) == LT
5633: && XEXP (before_comparison, 1) == const0_rtx
5634: && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
5635: && INTVAL (bl->biv->add_val) == -1)
5636: {
5637: REG_NOTES (PREV_INSN (loop_end))
1.1.1.4 root 5638: = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX,
1.1 root 5639: REG_NOTES (PREV_INSN (loop_end)));
5640: bl->nonneg = 1;
5641:
5642: return 1;
5643: }
5644: }
5645: }
5646: else if (num_mem_sets <= 1)
5647: {
5648: /* Try to change inc to dec, so can apply above optimization. */
5649: /* Can do this if:
5650: all registers modified are induction variables or invariant,
5651: all memory references have non-overlapping addresses
5652: (obviously true if only one write)
5653: allow 2 insns for the compare/jump at the end of the loop. */
5654: int num_nonfixed_reads = 0;
5655: /* 1 if the iteration var is used only to count iterations. */
5656: int no_use_except_counting = 0;
5657:
5658: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5659: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5660: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
5661:
5662: if (bl->giv_count == 0
5663: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
5664: {
5665: rtx bivreg = regno_reg_rtx[bl->regno];
5666:
5667: /* If there are no givs for this biv, and the only exit is the
5668: fall through at the end of the the loop, then
5669: see if perhaps there are no uses except to count. */
5670: no_use_except_counting = 1;
5671: for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
5672: if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
5673: {
5674: rtx set = single_set (p);
5675:
5676: if (set && GET_CODE (SET_DEST (set)) == REG
5677: && REGNO (SET_DEST (set)) == bl->regno)
5678: /* An insn that sets the biv is okay. */
5679: ;
5680: else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
5681: || p == prev_nonnote_insn (loop_end))
5682: /* Don't bother about the end test. */
5683: ;
5684: else if (reg_mentioned_p (bivreg, PATTERN (p)))
5685: /* Any other use of the biv is no good. */
5686: {
5687: no_use_except_counting = 0;
5688: break;
5689: }
5690: }
5691: }
5692:
5693: /* This code only acts for innermost loops. Also it simplifies
5694: the memory address check by only reversing loops with
5695: zero or one memory access.
5696: Two memory accesses could involve parts of the same array,
5697: and that can't be reversed. */
5698:
5699: if (num_nonfixed_reads <= 1
5700: && !loop_has_call
1.1.1.3 root 5701: && !loop_has_volatile
1.1 root 5702: && (no_use_except_counting
5703: || (bl->giv_count + bl->biv_count + num_mem_sets
5704: + num_movables + 2 == insn_count)))
5705: {
5706: rtx condition = get_condition_for_loop (PREV_INSN (loop_end));
5707: int win;
5708: rtx tem;
5709:
5710: /* Loop can be reversed. */
5711: if (loop_dump_stream)
5712: fprintf (loop_dump_stream, "Can reverse loop\n");
5713:
5714: /* Now check other conditions:
5715: initial_value must be zero,
5716: final_value % add_val == 0, so that when reversed, the
5717: biv will be zero on the last iteration.
5718:
5719: This test can probably be improved since +/- 1 in the constant
5720: can be obtained by changing LT to LE and vice versa; this is
5721: confusing. */
5722:
5723: if (comparison && bl->initial_value == const0_rtx
5724: && GET_CODE (XEXP (comparison, 1)) == CONST_INT
5725: /* LE gets turned into LT */
5726: && GET_CODE (comparison) == LT
5727: && (INTVAL (XEXP (comparison, 1))
5728: % INTVAL (bl->biv->add_val)) == 0)
5729: {
5730: /* Register will always be nonnegative, with value
5731: 0 on last iteration if loop reversed */
5732:
5733: /* Save some info needed to produce the new insns. */
5734: reg = bl->biv->dest_reg;
5735: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
1.1.1.4 root 5736: new_add_val = GEN_INT (- INTVAL (bl->biv->add_val));
1.1 root 5737:
5738: final_value = XEXP (comparison, 1);
1.1.1.4 root 5739: start_value = GEN_INT (INTVAL (XEXP (comparison, 1))
5740: - INTVAL (bl->biv->add_val));
1.1 root 5741:
5742: /* Initialize biv to start_value before loop start.
5743: The old initializing insn will be deleted as a
5744: dead store by flow.c. */
5745: emit_insn_before (gen_move_insn (reg, start_value), loop_start);
5746:
5747: /* Add insn to decrement register, and delete insn
5748: that incremented the register. */
5749: p = emit_insn_before (gen_add2_insn (reg, new_add_val),
5750: bl->biv->insn);
5751: delete_insn (bl->biv->insn);
5752:
5753: /* Update biv info to reflect its new status. */
5754: bl->biv->insn = p;
5755: bl->initial_value = start_value;
5756: bl->biv->add_val = new_add_val;
5757:
5758: /* Inc LABEL_NUSES so that delete_insn will
5759: not delete the label. */
5760: LABEL_NUSES (XEXP (jump_label, 0)) ++;
5761:
5762: /* Emit an insn after the end of the loop to set the biv's
5763: proper exit value if it is used anywhere outside the loop. */
5764: if ((regno_last_uid[bl->regno]
5765: != INSN_UID (PREV_INSN (PREV_INSN (loop_end))))
5766: || ! bl->init_insn
5767: || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn))
5768: emit_insn_after (gen_move_insn (reg, final_value),
5769: loop_end);
5770:
5771: /* Delete compare/branch at end of loop. */
5772: delete_insn (PREV_INSN (loop_end));
5773: delete_insn (PREV_INSN (loop_end));
5774:
5775: /* Add new compare/branch insn at end of loop. */
5776: start_sequence ();
1.1.1.4 root 5777: emit_cmp_insn (reg, const0_rtx, GE, NULL_RTX,
5778: GET_MODE (reg), 0, 0);
1.1 root 5779: emit_jump_insn (gen_bge (XEXP (jump_label, 0)));
5780: tem = gen_sequence ();
5781: end_sequence ();
5782: emit_jump_insn_before (tem, loop_end);
5783:
5784: for (tem = PREV_INSN (loop_end);
5785: tem && GET_CODE (tem) != JUMP_INSN; tem = PREV_INSN (tem))
5786: ;
5787: if (tem)
5788: {
5789: JUMP_LABEL (tem) = XEXP (jump_label, 0);
5790:
5791: /* Increment of LABEL_NUSES done above. */
5792: /* Register is now always nonnegative,
5793: so add REG_NONNEG note to the branch. */
1.1.1.4 root 5794: REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX,
1.1 root 5795: REG_NOTES (tem));
5796: }
5797:
5798: bl->nonneg = 1;
5799:
5800: /* Mark that this biv has been reversed. Each giv which depends
5801: on this biv, and which is also live past the end of the loop
5802: will have to be fixed up. */
5803:
5804: bl->reversed = 1;
5805:
5806: if (loop_dump_stream)
5807: fprintf (loop_dump_stream,
5808: "Reversed loop and added reg_nonneg\n");
5809:
5810: return 1;
5811: }
5812: }
5813: }
5814:
5815: return 0;
5816: }
5817:
5818: /* Verify whether the biv BL appears to be eliminable,
5819: based on the insns in the loop that refer to it.
5820: LOOP_START is the first insn of the loop, and END is the end insn.
5821:
5822: If ELIMINATE_P is non-zero, actually do the elimination.
5823:
5824: THRESHOLD and INSN_COUNT are from loop_optimize and are used to
5825: determine whether invariant insns should be placed inside or at the
5826: start of the loop. */
5827:
5828: static int
5829: maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
5830: struct iv_class *bl;
5831: rtx loop_start;
5832: rtx end;
5833: int eliminate_p;
5834: int threshold, insn_count;
5835: {
5836: rtx reg = bl->biv->dest_reg;
5837: rtx p, set;
5838: struct induction *v;
5839:
5840: /* Scan all insns in the loop, stopping if we find one that uses the
5841: biv in a way that we cannot eliminate. */
5842:
5843: for (p = loop_start; p != end; p = NEXT_INSN (p))
5844: {
5845: enum rtx_code code = GET_CODE (p);
5846: rtx where = threshold >= insn_count ? loop_start : p;
5847:
5848: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
5849: && reg_mentioned_p (reg, PATTERN (p))
5850: && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
5851: {
5852: if (loop_dump_stream)
5853: fprintf (loop_dump_stream,
5854: "Cannot eliminate biv %d: biv used in insn %d.\n",
5855: bl->regno, INSN_UID (p));
5856: break;
5857: }
5858: }
5859:
5860: if (p == end)
5861: {
5862: if (loop_dump_stream)
5863: fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
5864: bl->regno, eliminate_p ? "was" : "can be");
5865: return 1;
5866: }
5867:
5868: return 0;
5869: }
5870:
5871: /* If BL appears in X (part of the pattern of INSN), see if we can
5872: eliminate its use. If so, return 1. If not, return 0.
5873:
5874: If BIV does not appear in X, return 1.
5875:
5876: If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
5877: where extra insns should be added. Depending on how many items have been
5878: moved out of the loop, it will either be before INSN or at the start of
5879: the loop. */
5880:
5881: static int
5882: maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
5883: rtx x, insn;
5884: struct iv_class *bl;
5885: int eliminate_p;
5886: rtx where;
5887: {
5888: enum rtx_code code = GET_CODE (x);
5889: rtx reg = bl->biv->dest_reg;
5890: enum machine_mode mode = GET_MODE (reg);
5891: struct induction *v;
5892: rtx arg, new, tem;
5893: int arg_operand;
5894: char *fmt;
5895: int i, j;
5896:
5897: switch (code)
5898: {
5899: case REG:
5900: /* If we haven't already been able to do something with this BIV,
5901: we can't eliminate it. */
5902: if (x == reg)
5903: return 0;
5904: return 1;
5905:
5906: case SET:
5907: /* If this sets the BIV, it is not a problem. */
5908: if (SET_DEST (x) == reg)
5909: return 1;
5910:
5911: /* If this is an insn that defines a giv, it is also ok because
5912: it will go away when the giv is reduced. */
5913: for (v = bl->giv; v; v = v->next_iv)
5914: if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
5915: return 1;
5916:
5917: #ifdef HAVE_cc0
5918: if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
5919: {
5920: /* Can replace with any giv that was reduced and
5921: that has (MULT_VAL != 0) and (ADD_VAL == 0).
5922: Require a constant for MULT_VAL, so we know it's nonzero. */
5923:
5924: for (v = bl->giv; v; v = v->next_iv)
5925: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5926: && v->add_val == const0_rtx
5927: && ! v->ignore && ! v->maybe_dead
5928: && v->mode == mode)
5929: {
5930: if (! eliminate_p)
5931: return 1;
5932:
5933: /* If the giv has the opposite direction of change,
5934: then reverse the comparison. */
5935: if (INTVAL (v->mult_val) < 0)
5936: new = gen_rtx (COMPARE, GET_MODE (v->new_reg),
5937: const0_rtx, v->new_reg);
5938: else
5939: new = v->new_reg;
5940:
5941: /* We can probably test that giv's reduced reg. */
5942: if (validate_change (insn, &SET_SRC (x), new, 0))
5943: return 1;
5944: }
5945:
5946: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
5947: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
5948: Require a constant for MULT_VAL, so we know it's nonzero. */
5949:
5950: for (v = bl->giv; v; v = v->next_iv)
5951: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
5952: && ! v->ignore && ! v->maybe_dead
5953: && v->mode == mode)
5954: {
5955: if (! eliminate_p)
5956: return 1;
5957:
5958: /* If the giv has the opposite direction of change,
5959: then reverse the comparison. */
5960: if (INTVAL (v->mult_val) < 0)
5961: new = gen_rtx (COMPARE, VOIDmode, copy_rtx (v->add_val),
5962: v->new_reg);
5963: else
5964: new = gen_rtx (COMPARE, VOIDmode, v->new_reg,
5965: copy_rtx (v->add_val));
5966:
5967: /* Replace biv with the giv's reduced register. */
5968: update_reg_last_use (v->add_val, insn);
5969: if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
5970: return 1;
5971:
5972: /* Insn doesn't support that constant or invariant. Copy it
5973: into a register (it will be a loop invariant.) */
5974: tem = gen_reg_rtx (GET_MODE (v->new_reg));
5975:
5976: emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
5977: where);
5978:
5979: if (validate_change (insn, &SET_SRC (PATTERN (insn)),
5980: gen_rtx (COMPARE, VOIDmode,
5981: v->new_reg, tem), 0))
5982: return 1;
5983: }
5984: }
5985: #endif
5986: break;
5987:
5988: case COMPARE:
5989: case EQ: case NE:
5990: case GT: case GE: case GTU: case GEU:
5991: case LT: case LE: case LTU: case LEU:
5992: /* See if either argument is the biv. */
5993: if (XEXP (x, 0) == reg)
5994: arg = XEXP (x, 1), arg_operand = 1;
5995: else if (XEXP (x, 1) == reg)
5996: arg = XEXP (x, 0), arg_operand = 0;
5997: else
5998: break;
5999:
6000: if (CONSTANT_P (arg))
6001: {
6002: /* First try to replace with any giv that has constant positive
6003: mult_val and constant add_val. We might be able to support
6004: negative mult_val, but it seems complex to do it in general. */
6005:
6006: for (v = bl->giv; v; v = v->next_iv)
6007: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
6008: && CONSTANT_P (v->add_val)
6009: && ! v->ignore && ! v->maybe_dead
6010: && v->mode == mode)
6011: {
6012: if (! eliminate_p)
6013: return 1;
6014:
6015: /* Replace biv with the giv's reduced reg. */
6016: XEXP (x, 1-arg_operand) = v->new_reg;
6017:
6018: /* If all constants are actually constant integers and
6019: the derived constant can be directly placed in the COMPARE,
6020: do so. */
6021: if (GET_CODE (arg) == CONST_INT
6022: && GET_CODE (v->mult_val) == CONST_INT
6023: && GET_CODE (v->add_val) == CONST_INT
6024: && validate_change (insn, &XEXP (x, arg_operand),
1.1.1.4 root 6025: GEN_INT (INTVAL (arg)
6026: * INTVAL (v->mult_val)
6027: + INTVAL (v->add_val)), 0))
1.1 root 6028: return 1;
6029:
6030: /* Otherwise, load it into a register. */
6031: tem = gen_reg_rtx (mode);
6032: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
6033: if (validate_change (insn, &XEXP (x, arg_operand), tem, 0))
6034: return 1;
6035:
6036: /* If that failed, put back the change we made above. */
6037: XEXP (x, 1-arg_operand) = reg;
6038: }
6039:
6040: /* Look for giv with positive constant mult_val and nonconst add_val.
6041: Insert insns to calculate new compare value. */
6042:
6043: for (v = bl->giv; v; v = v->next_iv)
1.1.1.2 root 6044: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
1.1 root 6045: && ! v->ignore && ! v->maybe_dead
6046: && v->mode == mode)
6047: {
6048: rtx tem;
6049:
6050: if (! eliminate_p)
6051: return 1;
6052:
6053: tem = gen_reg_rtx (mode);
6054:
6055: /* Replace biv with giv's reduced register. */
6056: validate_change (insn, &XEXP (x, 1 - arg_operand),
6057: v->new_reg, 1);
6058:
6059: /* Compute value to compare against. */
6060: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
6061: /* Use it in this insn. */
6062: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
6063: if (apply_change_group ())
6064: return 1;
6065: }
6066: }
6067: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
6068: {
6069: if (invariant_p (arg) == 1)
6070: {
6071: /* Look for giv with constant positive mult_val and nonconst
6072: add_val. Insert insns to compute 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,
6092: tem, where);
6093: validate_change (insn, &XEXP (x, arg_operand), tem, 1);
6094: if (apply_change_group ())
6095: return 1;
6096: }
6097: }
6098:
6099: /* This code has problems. Basically, you can't know when
6100: seeing if we will eliminate BL, whether a particular giv
6101: of ARG will be reduced. If it isn't going to be reduced,
6102: we can't eliminate BL. We can try forcing it to be reduced,
6103: but that can generate poor code.
6104:
6105: The problem is that the benefit of reducing TV, below should
6106: be increased if BL can actually be eliminated, but this means
6107: we might have to do a topological sort of the order in which
6108: we try to process biv. It doesn't seem worthwhile to do
6109: this sort of thing now. */
6110:
6111: #if 0
6112: /* Otherwise the reg compared with had better be a biv. */
6113: if (GET_CODE (arg) != REG
6114: || reg_iv_type[REGNO (arg)] != BASIC_INDUCT)
6115: return 0;
6116:
6117: /* Look for a pair of givs, one for each biv,
6118: with identical coefficients. */
6119: for (v = bl->giv; v; v = v->next_iv)
6120: {
6121: struct induction *tv;
6122:
6123: if (v->ignore || v->maybe_dead || v->mode != mode)
6124: continue;
6125:
6126: for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
6127: if (! tv->ignore && ! tv->maybe_dead
6128: && rtx_equal_p (tv->mult_val, v->mult_val)
6129: && rtx_equal_p (tv->add_val, v->add_val)
6130: && tv->mode == mode)
6131: {
6132: if (! eliminate_p)
6133: return 1;
6134:
6135: /* Replace biv with its giv's reduced reg. */
6136: XEXP (x, 1-arg_operand) = v->new_reg;
6137: /* Replace other operand with the other giv's
6138: reduced reg. */
6139: XEXP (x, arg_operand) = tv->new_reg;
6140: return 1;
6141: }
6142: }
6143: #endif
6144: }
6145:
6146: /* If we get here, the biv can't be eliminated. */
6147: return 0;
6148:
6149: case MEM:
6150: /* If this address is a DEST_ADDR giv, it doesn't matter if the
6151: biv is used in it, since it will be replaced. */
6152: for (v = bl->giv; v; v = v->next_iv)
6153: if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
6154: return 1;
6155: break;
6156: }
6157:
6158: /* See if any subexpression fails elimination. */
6159: fmt = GET_RTX_FORMAT (code);
6160: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
6161: {
6162: switch (fmt[i])
6163: {
6164: case 'e':
6165: if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl,
6166: eliminate_p, where))
6167: return 0;
6168: break;
6169:
6170: case 'E':
6171: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6172: if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl,
6173: eliminate_p, where))
6174: return 0;
6175: break;
6176: }
6177: }
6178:
6179: return 1;
6180: }
6181:
6182: /* Return nonzero if the last use of REG
6183: is in an insn following INSN in the same basic block. */
6184:
6185: static int
6186: last_use_this_basic_block (reg, insn)
6187: rtx reg;
6188: rtx insn;
6189: {
6190: rtx n;
6191: for (n = insn;
6192: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
6193: n = NEXT_INSN (n))
6194: {
6195: if (regno_last_uid[REGNO (reg)] == INSN_UID (n))
6196: return 1;
6197: }
6198: return 0;
6199: }
6200:
6201: /* Called via `note_stores' to record the initial value of a biv. Here we
6202: just record the location of the set and process it later. */
6203:
6204: static void
6205: record_initial (dest, set)
6206: rtx dest;
6207: rtx set;
6208: {
6209: struct iv_class *bl;
6210:
6211: if (GET_CODE (dest) != REG
6212: || REGNO (dest) >= max_reg_before_loop
1.1.1.5 ! root 6213: || reg_iv_type[REGNO (dest)] != BASIC_INDUCT
! 6214: /* Reject this insn if the source isn't valid for the mode of DEST. */
! 6215: || GET_MODE (dest) != GET_MODE (SET_DEST (set)))
1.1 root 6216: return;
6217:
6218: bl = reg_biv_class[REGNO (dest)];
6219:
6220: /* If this is the first set found, record it. */
6221: if (bl->init_insn == 0)
6222: {
6223: bl->init_insn = note_insn;
6224: bl->init_set = set;
6225: }
6226: }
6227:
6228: /* If any of the registers in X are "old" and currently have a last use earlier
6229: than INSN, update them to have a last use of INSN. Their actual last use
6230: will be the previous insn but it will not have a valid uid_luid so we can't
6231: use it. */
6232:
6233: static void
6234: update_reg_last_use (x, insn)
6235: rtx x;
6236: rtx insn;
6237: {
6238: /* Check for the case where INSN does not have a valid luid. In this case,
6239: there is no need to modify the regno_last_uid, as this can only happen
6240: when code is inserted after the loop_end to set a pseudo's final value,
6241: and hence this insn will never be the last use of x. */
6242: if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
6243: && INSN_UID (insn) < max_uid_for_loop
6244: && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)])
6245: regno_last_uid[REGNO (x)] = INSN_UID (insn);
6246: else
6247: {
6248: register int i, j;
6249: register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
6250: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
6251: {
6252: if (fmt[i] == 'e')
6253: update_reg_last_use (XEXP (x, i), insn);
6254: else if (fmt[i] == 'E')
6255: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6256: update_reg_last_use (XVECEXP (x, i, j), insn);
6257: }
6258: }
6259: }
6260:
6261: /* Given a jump insn JUMP, return the condition that will cause it to branch
6262: to its JUMP_LABEL. If the condition cannot be understood, or is an
6263: inequality floating-point comparison which needs to be reversed, 0 will
6264: be returned.
6265:
6266: If EARLIEST is non-zero, it is a pointer to a place where the earliest
6267: insn used in locating the condition was found. If a replacement test
6268: of the condition is desired, it should be placed in front of that
6269: insn and we will be sure that the inputs are still valid.
6270:
6271: The condition will be returned in a canonical form to simplify testing by
6272: callers. Specifically:
6273:
6274: (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
6275: (2) Both operands will be machine operands; (cc0) will have been replaced.
6276: (3) If an operand is a constant, it will be the second operand.
6277: (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
6278: for GE, GEU, and LEU. */
6279:
6280: rtx
6281: get_condition (jump, earliest)
6282: rtx jump;
6283: rtx *earliest;
6284: {
6285: enum rtx_code code;
6286: rtx prev = jump;
6287: rtx set;
6288: rtx tem;
6289: rtx op0, op1;
6290: int reverse_code = 0;
6291: int did_reverse_condition = 0;
6292:
6293: /* If this is not a standard conditional jump, we can't parse it. */
6294: if (GET_CODE (jump) != JUMP_INSN
6295: || ! condjump_p (jump) || simplejump_p (jump))
6296: return 0;
6297:
6298: code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0));
6299: op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0);
6300: op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1);
6301:
6302: if (earliest)
6303: *earliest = jump;
6304:
6305: /* If this branches to JUMP_LABEL when the condition is false, reverse
6306: the condition. */
1.1.1.4 root 6307: if (GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 2)) == LABEL_REF
6308: && XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump))
1.1 root 6309: code = reverse_condition (code), did_reverse_condition ^= 1;
6310:
6311: /* If we are comparing a register with zero, see if the register is set
6312: in the previous insn to a COMPARE or a comparison operation. Perform
6313: the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
6314: in cse.c */
6315:
6316: while (GET_RTX_CLASS (code) == '<' && op1 == const0_rtx)
6317: {
6318: /* Set non-zero when we find something of interest. */
6319: rtx x = 0;
6320:
6321: #ifdef HAVE_cc0
6322: /* If comparison with cc0, import actual comparison from compare
6323: insn. */
6324: if (op0 == cc0_rtx)
6325: {
6326: if ((prev = prev_nonnote_insn (prev)) == 0
6327: || GET_CODE (prev) != INSN
6328: || (set = single_set (prev)) == 0
6329: || SET_DEST (set) != cc0_rtx)
6330: return 0;
6331:
6332: op0 = SET_SRC (set);
6333: op1 = CONST0_RTX (GET_MODE (op0));
6334: if (earliest)
6335: *earliest = prev;
6336: }
6337: #endif
6338:
6339: /* If this is a COMPARE, pick up the two things being compared. */
6340: if (GET_CODE (op0) == COMPARE)
6341: {
6342: op1 = XEXP (op0, 1);
6343: op0 = XEXP (op0, 0);
6344: continue;
6345: }
6346: else if (GET_CODE (op0) != REG)
6347: break;
6348:
6349: /* Go back to the previous insn. Stop if it is not an INSN. We also
6350: stop if it isn't a single set or if it has a REG_INC note because
6351: we don't want to bother dealing with it. */
6352:
6353: if ((prev = prev_nonnote_insn (prev)) == 0
6354: || GET_CODE (prev) != INSN
6355: || FIND_REG_INC_NOTE (prev, 0)
6356: || (set = single_set (prev)) == 0)
6357: break;
6358:
6359: /* If this is setting OP0, get what it sets it to if it looks
6360: relevant. */
6361: if (SET_DEST (set) == op0)
6362: {
6363: enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
6364:
6365: if ((GET_CODE (SET_SRC (set)) == COMPARE
1.1.1.4 root 6366: || (((code == NE
6367: || (code == LT
6368: && GET_MODE_CLASS (inner_mode) == MODE_INT
6369: && (GET_MODE_BITSIZE (inner_mode)
6370: <= HOST_BITS_PER_WIDE_INT)
6371: && (STORE_FLAG_VALUE
6372: & ((HOST_WIDE_INT) 1
6373: << (GET_MODE_BITSIZE (inner_mode) - 1))))
6374: #ifdef FLOAT_STORE_FLAG_VALUE
6375: || (code == LT
6376: && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
6377: && FLOAT_STORE_FLAG_VALUE < 0)
6378: #endif
6379: ))
1.1 root 6380: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')))
6381: x = SET_SRC (set);
1.1.1.4 root 6382: else if (((code == EQ
6383: || (code == GE
6384: && (GET_MODE_BITSIZE (inner_mode)
6385: <= HOST_BITS_PER_WIDE_INT)
6386: && GET_MODE_CLASS (inner_mode) == MODE_INT
6387: && (STORE_FLAG_VALUE
6388: & ((HOST_WIDE_INT) 1
6389: << (GET_MODE_BITSIZE (inner_mode) - 1))))
6390: #ifdef FLOAT_STORE_FLAG_VALUE
6391: || (code == GE
6392: && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
6393: && FLOAT_STORE_FLAG_VALUE < 0)
6394: #endif
6395: ))
1.1 root 6396: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<')
6397: {
6398: /* We might have reversed a LT to get a GE here. But this wasn't
6399: actually the comparison of data, so we don't flag that we
6400: have had to reverse the condition. */
6401: did_reverse_condition ^= 1;
6402: reverse_code = 1;
6403: x = SET_SRC (set);
6404: }
6405: }
6406:
6407: else if (reg_set_p (op0, prev))
6408: /* If this sets OP0, but not directly, we have to give up. */
6409: break;
6410:
6411: if (x)
6412: {
6413: if (GET_RTX_CLASS (GET_CODE (x)) == '<')
6414: code = GET_CODE (x);
6415: if (reverse_code)
6416: {
6417: code = reverse_condition (code);
6418: did_reverse_condition ^= 1;
6419: reverse_code = 0;
6420: }
6421:
6422: op0 = XEXP (x, 0), op1 = XEXP (x, 1);
6423: if (earliest)
6424: *earliest = prev;
6425: }
6426: }
6427:
6428: /* If constant is first, put it last. */
6429: if (CONSTANT_P (op0))
6430: code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
6431:
6432: /* If OP0 is the result of a comparison, we weren't able to find what
6433: was really being compared, so fail. */
6434: if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
6435: return 0;
6436:
1.1.1.4 root 6437: /* Canonicalize any ordered comparison with integers involving equality
6438: if we can do computations in the relevant mode and we do not
6439: overflow. */
6440:
6441: if (GET_CODE (op1) == CONST_INT
6442: && GET_MODE (op0) != VOIDmode
6443: && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
6444: {
6445: HOST_WIDE_INT const_val = INTVAL (op1);
6446: unsigned HOST_WIDE_INT uconst_val = const_val;
6447: unsigned HOST_WIDE_INT max_val
6448: = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
1.1 root 6449:
6450: switch (code)
1.1.1.4 root 6451: {
6452: case LE:
6453: if (const_val != max_val >> 1)
6454: code = LT, op1 = GEN_INT (const_val + 1);
6455: break;
1.1 root 6456:
1.1.1.4 root 6457: case GE:
6458: if (const_val
6459: != (((HOST_WIDE_INT) 1
6460: << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
6461: code = GT, op1 = GEN_INT (const_val - 1);
6462: break;
1.1 root 6463:
1.1.1.4 root 6464: case LEU:
6465: if (uconst_val != max_val)
6466: code = LTU, op1 = GEN_INT (uconst_val + 1);
6467: break;
1.1 root 6468:
1.1.1.4 root 6469: case GEU:
6470: if (uconst_val != 0)
6471: code = GTU, op1 = GEN_INT (uconst_val - 1);
6472: break;
6473: }
1.1 root 6474: }
6475:
6476: /* If this was floating-point and we reversed anything other than an
6477: EQ or NE, return zero. */
6478: if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
6479: && did_reverse_condition && code != NE && code != EQ
6480: && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
6481: return 0;
6482:
6483: #ifdef HAVE_cc0
6484: /* Never return CC0; return zero instead. */
6485: if (op0 == cc0_rtx)
6486: return 0;
6487: #endif
6488:
6489: return gen_rtx (code, VOIDmode, op0, op1);
6490: }
6491:
6492: /* Similar to above routine, except that we also put an invariant last
6493: unless both operands are invariants. */
6494:
6495: rtx
6496: get_condition_for_loop (x)
6497: rtx x;
6498: {
1.1.1.4 root 6499: rtx comparison = get_condition (x, NULL_PTR);
1.1 root 6500:
6501: if (comparison == 0
6502: || ! invariant_p (XEXP (comparison, 0))
6503: || invariant_p (XEXP (comparison, 1)))
6504: return comparison;
6505:
6506: return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode,
6507: XEXP (comparison, 1), XEXP (comparison, 0));
6508: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.