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