![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to unroll.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 unroll.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Try to unroll loops, and split induction variables.
1.1.1.8 root 2: Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
1.1 root 3: Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
4:
5: This file is part of GNU CC.
6:
7: GNU CC is free software; you can redistribute it and/or modify
8: it under the terms of the GNU General Public License as published by
9: the Free Software Foundation; either version 2, or (at your option)
10: any later version.
11:
12: GNU CC is distributed in the hope that it will be useful,
13: but WITHOUT ANY WARRANTY; without even the implied warranty of
14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15: GNU General Public License for more details.
16:
17: You should have received a copy of the GNU General Public License
18: along with GNU CC; see the file COPYING. If not, write to
1.1.1.8 root 19: the Free Software Foundation, 59 Temple Place - Suite 330,
20: Boston, MA 02111-1307, USA. */
1.1 root 21:
22: /* Try to unroll a loop, and split induction variables.
23:
24: Loops for which the number of iterations can be calculated exactly are
25: handled specially. If the number of iterations times the insn_count is
26: less than MAX_UNROLLED_INSNS, then the loop is unrolled completely.
27: Otherwise, we try to unroll the loop a number of times modulo the number
28: of iterations, so that only one exit test will be needed. It is unrolled
29: a number of times approximately equal to MAX_UNROLLED_INSNS divided by
30: the insn count.
31:
32: Otherwise, if the number of iterations can be calculated exactly at
33: run time, and the loop is always entered at the top, then we try to
34: precondition the loop. That is, at run time, calculate how many times
35: the loop will execute, and then execute the loop body a few times so
36: that the remaining iterations will be some multiple of 4 (or 2 if the
37: loop is large). Then fall through to a loop unrolled 4 (or 2) times,
38: with only one exit test needed at the end of the loop.
39:
40: Otherwise, if the number of iterations can not be calculated exactly,
41: not even at run time, then we still unroll the loop a number of times
42: approximately equal to MAX_UNROLLED_INSNS divided by the insn count,
43: but there must be an exit test after each copy of the loop body.
44:
45: For each induction variable, which is dead outside the loop (replaceable)
46: or for which we can easily calculate the final value, if we can easily
47: calculate its value at each place where it is set as a function of the
48: current loop unroll count and the variable's value at loop entry, then
49: the induction variable is split into `N' different variables, one for
50: each copy of the loop body. One variable is live across the backward
51: branch, and the others are all calculated as a function of this variable.
52: This helps eliminate data dependencies, and leads to further opportunities
53: for cse. */
54:
55: /* Possible improvements follow: */
56:
57: /* ??? Add an extra pass somewhere to determine whether unrolling will
58: give any benefit. E.g. after generating all unrolled insns, compute the
59: cost of all insns and compare against cost of insns in rolled loop.
60:
61: - On traditional architectures, unrolling a non-constant bound loop
62: is a win if there is a giv whose only use is in memory addresses, the
1.1.1.3 root 63: memory addresses can be split, and hence giv increments can be
1.1 root 64: eliminated.
65: - It is also a win if the loop is executed many times, and preconditioning
66: can be performed for the loop.
67: Add code to check for these and similar cases. */
68:
69: /* ??? Improve control of which loops get unrolled. Could use profiling
70: info to only unroll the most commonly executed loops. Perhaps have
71: a user specifyable option to control the amount of code expansion,
72: or the percent of loops to consider for unrolling. Etc. */
73:
74: /* ??? Look at the register copies inside the loop to see if they form a
75: simple permutation. If so, iterate the permutation until it gets back to
76: the start state. This is how many times we should unroll the loop, for
77: best results, because then all register copies can be eliminated.
78: For example, the lisp nreverse function should be unrolled 3 times
79: while (this)
80: {
81: next = this->cdr;
82: this->cdr = prev;
83: prev = this;
84: this = next;
85: }
86:
87: ??? The number of times to unroll the loop may also be based on data
88: references in the loop. For example, if we have a loop that references
89: x[i-1], x[i], and x[i+1], we should unroll it a multiple of 3 times. */
90:
91: /* ??? Add some simple linear equation solving capability so that we can
92: determine the number of loop iterations for more complex loops.
93: For example, consider this loop from gdb
94: #define SWAP_TARGET_AND_HOST(buffer,len)
95: {
96: char tmp;
97: char *p = (char *) buffer;
98: char *q = ((char *) buffer) + len - 1;
99: int iterations = (len + 1) >> 1;
100: int i;
101: for (p; p < q; p++, q--;)
102: {
103: tmp = *q;
104: *q = *p;
105: *p = tmp;
106: }
107: }
108: Note that:
109: start value = p = &buffer + current_iteration
110: end value = q = &buffer + len - 1 - current_iteration
111: Given the loop exit test of "p < q", then there must be "q - p" iterations,
112: set equal to zero and solve for number of iterations:
113: q - p = len - 1 - 2*current_iteration = 0
114: current_iteration = (len - 1) / 2
115: Hence, there are (len - 1) / 2 (rounded up to the nearest integer)
116: iterations of this loop. */
117:
118: /* ??? Currently, no labels are marked as loop invariant when doing loop
119: unrolling. This is because an insn inside the loop, that loads the address
120: of a label inside the loop into a register, could be moved outside the loop
121: by the invariant code motion pass if labels were invariant. If the loop
122: is subsequently unrolled, the code will be wrong because each unrolled
123: body of the loop will use the same address, whereas each actually needs a
124: different address. A case where this happens is when a loop containing
125: a switch statement is unrolled.
126:
127: It would be better to let labels be considered invariant. When we
128: unroll loops here, check to see if any insns using a label local to the
129: loop were moved before the loop. If so, then correct the problem, by
130: moving the insn back into the loop, or perhaps replicate the insn before
131: the loop, one copy for each time the loop is unrolled. */
132:
133: /* The prime factors looked for when trying to unroll a loop by some
134: number which is modulo the total number of iterations. Just checking
135: for these 4 prime factors will find at least one factor for 75% of
136: all numbers theoretically. Practically speaking, this will succeed
137: almost all of the time since loops are generally a multiple of 2
138: and/or 5. */
139:
140: #define NUM_FACTORS 4
141:
142: struct _factor { int factor, count; } factors[NUM_FACTORS]
143: = { {2, 0}, {3, 0}, {5, 0}, {7, 0}};
144:
145: /* Describes the different types of loop unrolling performed. */
146:
147: enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE };
148:
149: #include "config.h"
150: #include "rtl.h"
151: #include "insn-config.h"
152: #include "integrate.h"
153: #include "regs.h"
154: #include "flags.h"
155: #include "expr.h"
156: #include <stdio.h>
157: #include "loop.h"
158:
159: /* This controls which loops are unrolled, and by how much we unroll
160: them. */
161:
162: #ifndef MAX_UNROLLED_INSNS
163: #define MAX_UNROLLED_INSNS 100
164: #endif
165:
166: /* Indexed by register number, if non-zero, then it contains a pointer
167: to a struct induction for a DEST_REG giv which has been combined with
168: one of more address givs. This is needed because whenever such a DEST_REG
169: giv is modified, we must modify the value of all split address givs
170: that were combined with this DEST_REG giv. */
171:
172: static struct induction **addr_combined_regs;
173:
174: /* Indexed by register number, if this is a splittable induction variable,
175: then this will hold the current value of the register, which depends on the
176: iteration number. */
177:
178: static rtx *splittable_regs;
179:
180: /* Indexed by register number, if this is a splittable induction variable,
181: then this will hold the number of instructions in the loop that modify
182: the induction variable. Used to ensure that only the last insn modifying
183: a split iv will update the original iv of the dest. */
184:
185: static int *splittable_regs_updates;
186:
187: /* Values describing the current loop's iteration variable. These are set up
188: by loop_iterations, and used by precondition_loop_p. */
189:
190: static rtx loop_iteration_var;
191: static rtx loop_initial_value;
192: static rtx loop_increment;
193: static rtx loop_final_value;
194:
195: /* Forward declarations. */
196:
1.1.1.8 root 197: static void init_reg_map PROTO((struct inline_remap *, int));
198: static int precondition_loop_p PROTO((rtx *, rtx *, rtx *, rtx, rtx));
199: static rtx calculate_giv_inc PROTO((rtx, rtx, int));
200: static rtx initial_reg_note_copy PROTO((rtx, struct inline_remap *));
201: static void final_reg_note_copy PROTO((rtx, struct inline_remap *));
202: static void copy_loop_body PROTO((rtx, rtx, struct inline_remap *, rtx, int,
203: enum unroll_types, rtx, rtx, rtx, rtx));
204: static void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
205: static rtx approx_final_value PROTO((enum rtx_code, rtx, int *, int *));
206: static int find_splittable_regs PROTO((enum unroll_types, rtx, rtx, rtx, int));
207: static int find_splittable_givs PROTO((struct iv_class *,enum unroll_types,
208: rtx, rtx, rtx, int));
209: static int reg_dead_after_loop PROTO((rtx, rtx, rtx));
210: static rtx fold_rtx_mult_add PROTO((rtx, rtx, rtx, enum machine_mode));
211: static rtx remap_split_bivs PROTO((rtx));
1.1 root 212:
213: /* Try to unroll one loop and split induction variables in the loop.
214:
215: The loop is described by the arguments LOOP_END, INSN_COUNT, and
1.1.1.3 root 216: LOOP_START. END_INSERT_BEFORE indicates where insns should be added
1.1 root 217: which need to be executed when the loop falls through. STRENGTH_REDUCTION_P
218: indicates whether information generated in the strength reduction pass
219: is available.
220:
221: This function is intended to be called from within `strength_reduce'
222: in loop.c. */
223:
224: void
225: unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
226: strength_reduce_p)
227: rtx loop_end;
228: int insn_count;
229: rtx loop_start;
230: rtx end_insert_before;
231: int strength_reduce_p;
232: {
233: int i, j, temp;
234: int unroll_number = 1;
235: rtx copy_start, copy_end;
236: rtx insn, copy, sequence, pattern, tem;
237: int max_labelno, max_insnno;
238: rtx insert_before;
239: struct inline_remap *map;
240: char *local_label;
1.1.1.8 root 241: char *local_regno;
1.1 root 242: int maxregnum;
243: int new_maxregnum;
244: rtx exit_label = 0;
245: rtx start_label;
246: struct iv_class *bl;
247: int splitting_not_safe = 0;
248: enum unroll_types unroll_type;
249: int loop_preconditioned = 0;
250: rtx safety_label;
251: /* This points to the last real insn in the loop, which should be either
252: a JUMP_INSN (for conditional jumps) or a BARRIER (for unconditional
253: jumps). */
254: rtx last_loop_insn;
255:
256: /* Don't bother unrolling huge loops. Since the minimum factor is
257: two, loops greater than one half of MAX_UNROLLED_INSNS will never
258: be unrolled. */
259: if (insn_count > MAX_UNROLLED_INSNS / 2)
260: {
261: if (loop_dump_stream)
262: fprintf (loop_dump_stream, "Unrolling failure: Loop too big.\n");
263: return;
264: }
265:
266: /* When emitting debugger info, we can't unroll loops with unequal numbers
267: of block_beg and block_end notes, because that would unbalance the block
268: structure of the function. This can happen as a result of the
269: "if (foo) bar; else break;" optimization in jump.c. */
270:
271: if (write_symbols != NO_DEBUG)
272: {
273: int block_begins = 0;
274: int block_ends = 0;
275:
276: for (insn = loop_start; insn != loop_end; insn = NEXT_INSN (insn))
277: {
278: if (GET_CODE (insn) == NOTE)
279: {
280: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG)
281: block_begins++;
282: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
283: block_ends++;
284: }
285: }
286:
287: if (block_begins != block_ends)
288: {
289: if (loop_dump_stream)
290: fprintf (loop_dump_stream,
291: "Unrolling failure: Unbalanced block notes.\n");
292: return;
293: }
294: }
295:
296: /* Determine type of unroll to perform. Depends on the number of iterations
297: and the size of the loop. */
298:
299: /* If there is no strength reduce info, then set loop_n_iterations to zero.
300: This can happen if strength_reduce can't find any bivs in the loop.
301: A value of zero indicates that the number of iterations could not be
302: calculated. */
303:
304: if (! strength_reduce_p)
305: loop_n_iterations = 0;
306:
307: if (loop_dump_stream && loop_n_iterations > 0)
308: fprintf (loop_dump_stream,
309: "Loop unrolling: %d iterations.\n", loop_n_iterations);
310:
311: /* Find and save a pointer to the last nonnote insn in the loop. */
312:
313: last_loop_insn = prev_nonnote_insn (loop_end);
314:
315: /* Calculate how many times to unroll the loop. Indicate whether or
316: not the loop is being completely unrolled. */
317:
318: if (loop_n_iterations == 1)
319: {
320: /* If number of iterations is exactly 1, then eliminate the compare and
321: branch at the end of the loop since they will never be taken.
322: Then return, since no other action is needed here. */
323:
324: /* If the last instruction is not a BARRIER or a JUMP_INSN, then
325: don't do anything. */
326:
327: if (GET_CODE (last_loop_insn) == BARRIER)
328: {
329: /* Delete the jump insn. This will delete the barrier also. */
330: delete_insn (PREV_INSN (last_loop_insn));
331: }
332: else if (GET_CODE (last_loop_insn) == JUMP_INSN)
333: {
334: #ifdef HAVE_cc0
1.1.1.2 root 335: /* The immediately preceding insn is a compare which must be
1.1 root 336: deleted. */
337: delete_insn (last_loop_insn);
338: delete_insn (PREV_INSN (last_loop_insn));
339: #else
1.1.1.2 root 340: /* The immediately preceding insn may not be the compare, so don't
1.1 root 341: delete it. */
342: delete_insn (last_loop_insn);
343: #endif
344: }
345: return;
346: }
347: else if (loop_n_iterations > 0
348: && loop_n_iterations * insn_count < MAX_UNROLLED_INSNS)
349: {
350: unroll_number = loop_n_iterations;
351: unroll_type = UNROLL_COMPLETELY;
352: }
353: else if (loop_n_iterations > 0)
354: {
355: /* Try to factor the number of iterations. Don't bother with the
356: general case, only using 2, 3, 5, and 7 will get 75% of all
357: numbers theoretically, and almost all in practice. */
358:
359: for (i = 0; i < NUM_FACTORS; i++)
360: factors[i].count = 0;
361:
362: temp = loop_n_iterations;
363: for (i = NUM_FACTORS - 1; i >= 0; i--)
364: while (temp % factors[i].factor == 0)
365: {
366: factors[i].count++;
367: temp = temp / factors[i].factor;
368: }
369:
370: /* Start with the larger factors first so that we generally
371: get lots of unrolling. */
372:
373: unroll_number = 1;
374: temp = insn_count;
375: for (i = 3; i >= 0; i--)
376: while (factors[i].count--)
377: {
378: if (temp * factors[i].factor < MAX_UNROLLED_INSNS)
379: {
380: unroll_number *= factors[i].factor;
381: temp *= factors[i].factor;
382: }
383: else
384: break;
385: }
386:
387: /* If we couldn't find any factors, then unroll as in the normal
388: case. */
389: if (unroll_number == 1)
390: {
391: if (loop_dump_stream)
392: fprintf (loop_dump_stream,
393: "Loop unrolling: No factors found.\n");
394: }
395: else
396: unroll_type = UNROLL_MODULO;
397: }
398:
399:
400: /* Default case, calculate number of times to unroll loop based on its
401: size. */
402: if (unroll_number == 1)
403: {
404: if (8 * insn_count < MAX_UNROLLED_INSNS)
405: unroll_number = 8;
406: else if (4 * insn_count < MAX_UNROLLED_INSNS)
407: unroll_number = 4;
408: else
409: unroll_number = 2;
410:
411: unroll_type = UNROLL_NAIVE;
412: }
413:
414: /* Now we know how many times to unroll the loop. */
415:
416: if (loop_dump_stream)
417: fprintf (loop_dump_stream,
418: "Unrolling loop %d times.\n", unroll_number);
419:
420:
421: if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
422: {
423: /* Loops of these types should never start with a jump down to
424: the exit condition test. For now, check for this case just to
425: be sure. UNROLL_NAIVE loops can be of this form, this case is
426: handled below. */
427: insn = loop_start;
428: while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
429: insn = NEXT_INSN (insn);
430: if (GET_CODE (insn) == JUMP_INSN)
431: abort ();
432: }
433:
434: if (unroll_type == UNROLL_COMPLETELY)
435: {
436: /* Completely unrolling the loop: Delete the compare and branch at
437: the end (the last two instructions). This delete must done at the
438: very end of loop unrolling, to avoid problems with calls to
439: back_branch_in_range_p, which is called by find_splittable_regs.
440: All increments of splittable bivs/givs are changed to load constant
441: instructions. */
442:
443: copy_start = loop_start;
444:
445: /* Set insert_before to the instruction immediately after the JUMP_INSN
446: (or BARRIER), so that any NOTEs between the JUMP_INSN and the end of
447: the loop will be correctly handled by copy_loop_body. */
448: insert_before = NEXT_INSN (last_loop_insn);
449:
450: /* Set copy_end to the insn before the jump at the end of the loop. */
451: if (GET_CODE (last_loop_insn) == BARRIER)
452: copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
453: else if (GET_CODE (last_loop_insn) == JUMP_INSN)
454: {
455: #ifdef HAVE_cc0
456: /* The instruction immediately before the JUMP_INSN is a compare
457: instruction which we do not want to copy. */
458: copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
459: #else
460: /* The instruction immediately before the JUMP_INSN may not be the
461: compare, so we must copy it. */
462: copy_end = PREV_INSN (last_loop_insn);
463: #endif
464: }
465: else
466: {
467: /* We currently can't unroll a loop if it doesn't end with a
468: JUMP_INSN. There would need to be a mechanism that recognizes
469: this case, and then inserts a jump after each loop body, which
470: jumps to after the last loop body. */
471: if (loop_dump_stream)
472: fprintf (loop_dump_stream,
473: "Unrolling failure: loop does not end with a JUMP_INSN.\n");
474: return;
475: }
476: }
477: else if (unroll_type == UNROLL_MODULO)
478: {
479: /* Partially unrolling the loop: The compare and branch at the end
480: (the last two instructions) must remain. Don't copy the compare
481: and branch instructions at the end of the loop. Insert the unrolled
482: code immediately before the compare/branch at the end so that the
483: code will fall through to them as before. */
484:
485: copy_start = loop_start;
486:
487: /* Set insert_before to the jump insn at the end of the loop.
488: Set copy_end to before the jump insn at the end of the loop. */
489: if (GET_CODE (last_loop_insn) == BARRIER)
490: {
491: insert_before = PREV_INSN (last_loop_insn);
492: copy_end = PREV_INSN (insert_before);
493: }
494: else if (GET_CODE (last_loop_insn) == JUMP_INSN)
495: {
496: #ifdef HAVE_cc0
497: /* The instruction immediately before the JUMP_INSN is a compare
498: instruction which we do not want to copy or delete. */
499: insert_before = PREV_INSN (last_loop_insn);
500: copy_end = PREV_INSN (insert_before);
501: #else
502: /* The instruction immediately before the JUMP_INSN may not be the
503: compare, so we must copy it. */
504: insert_before = last_loop_insn;
505: copy_end = PREV_INSN (last_loop_insn);
506: #endif
507: }
508: else
509: {
510: /* We currently can't unroll a loop if it doesn't end with a
511: JUMP_INSN. There would need to be a mechanism that recognizes
512: this case, and then inserts a jump after each loop body, which
513: jumps to after the last loop body. */
514: if (loop_dump_stream)
515: fprintf (loop_dump_stream,
516: "Unrolling failure: loop does not end with a JUMP_INSN.\n");
517: return;
518: }
519: }
520: else
521: {
522: /* Normal case: Must copy the compare and branch instructions at the
523: end of the loop. */
524:
525: if (GET_CODE (last_loop_insn) == BARRIER)
526: {
527: /* Loop ends with an unconditional jump and a barrier.
528: Handle this like above, don't copy jump and barrier.
529: This is not strictly necessary, but doing so prevents generating
530: unconditional jumps to an immediately following label.
531:
532: This will be corrected below if the target of this jump is
533: not the start_label. */
534:
535: insert_before = PREV_INSN (last_loop_insn);
536: copy_end = PREV_INSN (insert_before);
537: }
538: else if (GET_CODE (last_loop_insn) == JUMP_INSN)
539: {
540: /* Set insert_before to immediately after the JUMP_INSN, so that
541: NOTEs at the end of the loop will be correctly handled by
542: copy_loop_body. */
543: insert_before = NEXT_INSN (last_loop_insn);
544: copy_end = last_loop_insn;
545: }
546: else
547: {
548: /* We currently can't unroll a loop if it doesn't end with a
549: JUMP_INSN. There would need to be a mechanism that recognizes
550: this case, and then inserts a jump after each loop body, which
551: jumps to after the last loop body. */
552: if (loop_dump_stream)
553: fprintf (loop_dump_stream,
554: "Unrolling failure: loop does not end with a JUMP_INSN.\n");
555: return;
556: }
557:
558: /* If copying exit test branches because they can not be eliminated,
559: then must convert the fall through case of the branch to a jump past
560: the end of the loop. Create a label to emit after the loop and save
561: it for later use. Do not use the label after the loop, if any, since
562: it might be used by insns outside the loop, or there might be insns
563: added before it later by final_[bg]iv_value which must be after
564: the real exit label. */
565: exit_label = gen_label_rtx ();
566:
567: insn = loop_start;
568: while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
569: insn = NEXT_INSN (insn);
570:
571: if (GET_CODE (insn) == JUMP_INSN)
572: {
573: /* The loop starts with a jump down to the exit condition test.
574: Start copying the loop after the barrier following this
575: jump insn. */
576: copy_start = NEXT_INSN (insn);
577:
578: /* Splitting induction variables doesn't work when the loop is
579: entered via a jump to the bottom, because then we end up doing
580: a comparison against a new register for a split variable, but
581: we did not execute the set insn for the new register because
582: it was skipped over. */
583: splitting_not_safe = 1;
584: if (loop_dump_stream)
585: fprintf (loop_dump_stream,
586: "Splitting not safe, because loop not entered at top.\n");
587: }
588: else
589: copy_start = loop_start;
590: }
591:
592: /* This should always be the first label in the loop. */
593: start_label = NEXT_INSN (copy_start);
594: /* There may be a line number note and/or a loop continue note here. */
595: while (GET_CODE (start_label) == NOTE)
596: start_label = NEXT_INSN (start_label);
597: if (GET_CODE (start_label) != CODE_LABEL)
598: {
599: /* This can happen as a result of jump threading. If the first insns in
600: the loop test the same condition as the loop's backward jump, or the
601: opposite condition, then the backward jump will be modified to point
602: to elsewhere, and the loop's start label is deleted.
603:
604: This case currently can not be handled by the loop unrolling code. */
605:
606: if (loop_dump_stream)
607: fprintf (loop_dump_stream,
608: "Unrolling failure: unknown insns between BEG note and loop label.\n");
609: return;
610: }
1.1.1.6 root 611: if (LABEL_NAME (start_label))
612: {
613: /* The jump optimization pass must have combined the original start label
614: with a named label for a goto. We can't unroll this case because
615: jumps which go to the named label must be handled differently than
616: jumps to the loop start, and it is impossible to differentiate them
617: in this case. */
618: if (loop_dump_stream)
619: fprintf (loop_dump_stream,
620: "Unrolling failure: loop start label is gone\n");
621: return;
622: }
1.1 root 623:
624: if (unroll_type == UNROLL_NAIVE
625: && GET_CODE (last_loop_insn) == BARRIER
626: && start_label != JUMP_LABEL (PREV_INSN (last_loop_insn)))
627: {
628: /* In this case, we must copy the jump and barrier, because they will
629: not be converted to jumps to an immediately following label. */
630:
631: insert_before = NEXT_INSN (last_loop_insn);
632: copy_end = last_loop_insn;
633: }
634:
635: /* Allocate a translation table for the labels and insn numbers.
636: They will be filled in as we copy the insns in the loop. */
637:
638: max_labelno = max_label_num ();
639: max_insnno = get_max_uid ();
640:
641: map = (struct inline_remap *) alloca (sizeof (struct inline_remap));
642:
1.1.1.5 root 643: map->integrating = 0;
644:
1.1 root 645: /* Allocate the label map. */
646:
647: if (max_labelno > 0)
648: {
649: map->label_map = (rtx *) alloca (max_labelno * sizeof (rtx));
650:
651: local_label = (char *) alloca (max_labelno);
652: bzero (local_label, max_labelno);
653: }
654: else
655: map->label_map = 0;
656:
657: /* Search the loop and mark all local labels, i.e. the ones which have to
658: be distinct labels when copied. For all labels which might be
659: non-local, set their label_map entries to point to themselves.
660: If they happen to be local their label_map entries will be overwritten
661: before the loop body is copied. The label_map entries for local labels
662: will be set to a different value each time the loop body is copied. */
663:
664: for (insn = copy_start; insn != loop_end; insn = NEXT_INSN (insn))
665: {
666: if (GET_CODE (insn) == CODE_LABEL)
667: local_label[CODE_LABEL_NUMBER (insn)] = 1;
668: else if (GET_CODE (insn) == JUMP_INSN)
669: {
670: if (JUMP_LABEL (insn))
671: map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))]
672: = JUMP_LABEL (insn);
673: else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
674: || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
675: {
676: rtx pat = PATTERN (insn);
677: int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
678: int len = XVECLEN (pat, diff_vec_p);
679: rtx label;
680:
681: for (i = 0; i < len; i++)
682: {
683: label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
684: map->label_map[CODE_LABEL_NUMBER (label)] = label;
685: }
686: }
687: }
688: }
689:
690: /* Allocate space for the insn map. */
691:
692: map->insn_map = (rtx *) alloca (max_insnno * sizeof (rtx));
693:
694: /* Set this to zero, to indicate that we are doing loop unrolling,
695: not function inlining. */
696: map->inline_target = 0;
697:
698: /* The register and constant maps depend on the number of registers
699: present, so the final maps can't be created until after
700: find_splittable_regs is called. However, they are needed for
701: preconditioning, so we create temporary maps when preconditioning
702: is performed. */
703:
704: /* The preconditioning code may allocate two new pseudo registers. */
705: maxregnum = max_reg_num ();
706:
707: /* Allocate and zero out the splittable_regs and addr_combined_regs
708: arrays. These must be zeroed here because they will be used if
709: loop preconditioning is performed, and must be zero for that case.
710:
711: It is safe to do this here, since the extra registers created by the
712: preconditioning code and find_splittable_regs will never be used
1.1.1.3 root 713: to access the splittable_regs[] and addr_combined_regs[] arrays. */
1.1 root 714:
715: splittable_regs = (rtx *) alloca (maxregnum * sizeof (rtx));
1.1.1.7 root 716: bzero ((char *) splittable_regs, maxregnum * sizeof (rtx));
1.1 root 717: splittable_regs_updates = (int *) alloca (maxregnum * sizeof (int));
1.1.1.7 root 718: bzero ((char *) splittable_regs_updates, maxregnum * sizeof (int));
1.1 root 719: addr_combined_regs
720: = (struct induction **) alloca (maxregnum * sizeof (struct induction *));
1.1.1.7 root 721: bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *));
1.1.1.8 root 722: /* We must limit it to max_reg_before_loop, because only these pseudo
723: registers have valid regno_first_uid info. Any register created after
724: that is unlikely to be local to the loop anyways. */
725: local_regno = (char *) alloca (max_reg_before_loop);
726: bzero (local_regno, max_reg_before_loop);
727:
728: /* Mark all local registers, i.e. the ones which are referenced only
729: inside the loop. */
730: if (INSN_UID (copy_end) < max_uid_for_loop)
731: {
732: int copy_start_luid = INSN_LUID (copy_start);
733: int copy_end_luid = INSN_LUID (copy_end);
734:
735: /* If a register is used in the jump insn, we must not duplicate it
736: since it will also be used outside the loop. */
737: if (GET_CODE (copy_end) == JUMP_INSN)
738: copy_end_luid--;
739: /* If copy_start points to the NOTE that starts the loop, then we must
740: use the next luid, because invariant pseudo-regs moved out of the loop
741: have their lifetimes modified to start here, but they are not safe
742: to duplicate. */
743: if (copy_start == loop_start)
744: copy_start_luid++;
745:
746: for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; ++j)
747: if (regno_first_uid[j] > 0 && regno_first_uid[j] <= max_uid_for_loop
748: && uid_luid[regno_first_uid[j]] >= copy_start_luid
749: && regno_last_uid[j] > 0 && regno_last_uid[j] <= max_uid_for_loop
750: && uid_luid[regno_last_uid[j]] <= copy_end_luid)
751: local_regno[j] = 1;
752: }
1.1 root 753:
754: /* If this loop requires exit tests when unrolled, check to see if we
755: can precondition the loop so as to make the exit tests unnecessary.
756: Just like variable splitting, this is not safe if the loop is entered
757: via a jump to the bottom. Also, can not do this if no strength
758: reduce info, because precondition_loop_p uses this info. */
759:
760: /* Must copy the loop body for preconditioning before the following
761: find_splittable_regs call since that will emit insns which need to
762: be after the preconditioned loop copies, but immediately before the
763: unrolled loop copies. */
764:
765: /* Also, it is not safe to split induction variables for the preconditioned
766: copies of the loop body. If we split induction variables, then the code
767: assumes that each induction variable can be represented as a function
768: of its initial value and the loop iteration number. This is not true
769: in this case, because the last preconditioned copy of the loop body
770: could be any iteration from the first up to the `unroll_number-1'th,
771: depending on the initial value of the iteration variable. Therefore
772: we can not split induction variables here, because we can not calculate
773: their value. Hence, this code must occur before find_splittable_regs
774: is called. */
775:
776: if (unroll_type == UNROLL_NAIVE && ! splitting_not_safe && strength_reduce_p)
777: {
778: rtx initial_value, final_value, increment;
779:
780: if (precondition_loop_p (&initial_value, &final_value, &increment,
781: loop_start, loop_end))
782: {
783: register rtx diff, temp;
784: enum machine_mode mode;
785: rtx *labels;
786: int abs_inc, neg_inc;
787:
788: map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx));
789:
790: map->const_equiv_map = (rtx *) alloca (maxregnum * sizeof (rtx));
791: map->const_age_map = (unsigned *) alloca (maxregnum
792: * sizeof (unsigned));
793: map->const_equiv_map_size = maxregnum;
794: global_const_equiv_map = map->const_equiv_map;
1.1.1.6 root 795: global_const_equiv_map_size = maxregnum;
1.1 root 796:
797: init_reg_map (map, maxregnum);
798:
799: /* Limit loop unrolling to 4, since this will make 7 copies of
800: the loop body. */
801: if (unroll_number > 4)
802: unroll_number = 4;
803:
804: /* Save the absolute value of the increment, and also whether or
805: not it is negative. */
806: neg_inc = 0;
807: abs_inc = INTVAL (increment);
808: if (abs_inc < 0)
809: {
810: abs_inc = - abs_inc;
811: neg_inc = 1;
812: }
813:
814: start_sequence ();
815:
816: /* Decide what mode to do these calculations in. Choose the larger
817: of final_value's mode and initial_value's mode, or a full-word if
818: both are constants. */
819: mode = GET_MODE (final_value);
820: if (mode == VOIDmode)
821: {
822: mode = GET_MODE (initial_value);
823: if (mode == VOIDmode)
824: mode = word_mode;
825: }
826: else if (mode != GET_MODE (initial_value)
827: && (GET_MODE_SIZE (mode)
828: < GET_MODE_SIZE (GET_MODE (initial_value))))
829: mode = GET_MODE (initial_value);
830:
831: /* Calculate the difference between the final and initial values.
832: Final value may be a (plus (reg x) (const_int 1)) rtx.
833: Let the following cse pass simplify this if initial value is
834: a constant.
835:
836: We must copy the final and initial values here to avoid
837: improperly shared rtl. */
838:
839: diff = expand_binop (mode, sub_optab, copy_rtx (final_value),
1.1.1.4 root 840: copy_rtx (initial_value), NULL_RTX, 0,
1.1 root 841: OPTAB_LIB_WIDEN);
842:
843: /* Now calculate (diff % (unroll * abs (increment))) by using an
844: and instruction. */
845: diff = expand_binop (GET_MODE (diff), and_optab, diff,
1.1.1.4 root 846: GEN_INT (unroll_number * abs_inc - 1),
847: NULL_RTX, 0, OPTAB_LIB_WIDEN);
1.1 root 848:
849: /* Now emit a sequence of branches to jump to the proper precond
850: loop entry point. */
851:
852: labels = (rtx *) alloca (sizeof (rtx) * unroll_number);
853: for (i = 0; i < unroll_number; i++)
854: labels[i] = gen_label_rtx ();
855:
1.1.1.8 root 856: /* Check for the case where the initial value is greater than or equal
857: to the final value. In that case, we want to execute exactly
858: one loop iteration. The code below will fail for this case. */
859:
860: emit_cmp_insn (initial_value, final_value, neg_inc ? LE : GE,
861: NULL_RTX, mode, 0, 0);
862: if (neg_inc)
863: emit_jump_insn (gen_ble (labels[1]));
864: else
865: emit_jump_insn (gen_bge (labels[1]));
866: JUMP_LABEL (get_last_insn ()) = labels[1];
867: LABEL_NUSES (labels[1])++;
868:
1.1 root 869: /* Assuming the unroll_number is 4, and the increment is 2, then
870: for a negative increment: for a positive increment:
871: diff = 0,1 precond 0 diff = 0,7 precond 0
872: diff = 2,3 precond 3 diff = 1,2 precond 1
873: diff = 4,5 precond 2 diff = 3,4 precond 2
874: diff = 6,7 precond 1 diff = 5,6 precond 3 */
875:
876: /* We only need to emit (unroll_number - 1) branches here, the
877: last case just falls through to the following code. */
878:
879: /* ??? This would give better code if we emitted a tree of branches
880: instead of the current linear list of branches. */
881:
882: for (i = 0; i < unroll_number - 1; i++)
883: {
884: int cmp_const;
1.1.1.8 root 885: enum rtx_code cmp_code;
1.1 root 886:
887: /* For negative increments, must invert the constant compared
888: against, except when comparing against zero. */
889: if (i == 0)
1.1.1.8 root 890: {
891: cmp_const = 0;
892: cmp_code = EQ;
893: }
1.1 root 894: else if (neg_inc)
1.1.1.8 root 895: {
896: cmp_const = unroll_number - i;
897: cmp_code = GE;
898: }
1.1 root 899: else
1.1.1.8 root 900: {
901: cmp_const = i;
902: cmp_code = LE;
903: }
1.1 root 904:
1.1.1.4 root 905: emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
1.1.1.8 root 906: cmp_code, NULL_RTX, mode, 0, 0);
1.1 root 907:
908: if (i == 0)
909: emit_jump_insn (gen_beq (labels[i]));
910: else if (neg_inc)
911: emit_jump_insn (gen_bge (labels[i]));
912: else
913: emit_jump_insn (gen_ble (labels[i]));
914: JUMP_LABEL (get_last_insn ()) = labels[i];
915: LABEL_NUSES (labels[i])++;
916: }
917:
918: /* If the increment is greater than one, then we need another branch,
919: to handle other cases equivalent to 0. */
920:
921: /* ??? This should be merged into the code above somehow to help
922: simplify the code here, and reduce the number of branches emitted.
923: For the negative increment case, the branch here could easily
924: be merged with the `0' case branch above. For the positive
925: increment case, it is not clear how this can be simplified. */
926:
927: if (abs_inc != 1)
928: {
929: int cmp_const;
1.1.1.8 root 930: enum rtx_code cmp_code;
1.1 root 931:
932: if (neg_inc)
1.1.1.8 root 933: {
934: cmp_const = abs_inc - 1;
935: cmp_code = LE;
936: }
1.1 root 937: else
1.1.1.8 root 938: {
939: cmp_const = abs_inc * (unroll_number - 1) + 1;
940: cmp_code = GE;
941: }
1.1 root 942:
1.1.1.8 root 943: emit_cmp_insn (diff, GEN_INT (cmp_const), cmp_code, NULL_RTX,
1.1.1.4 root 944: mode, 0, 0);
1.1 root 945:
946: if (neg_inc)
947: emit_jump_insn (gen_ble (labels[0]));
948: else
949: emit_jump_insn (gen_bge (labels[0]));
950: JUMP_LABEL (get_last_insn ()) = labels[0];
951: LABEL_NUSES (labels[0])++;
952: }
953:
954: sequence = gen_sequence ();
955: end_sequence ();
956: emit_insn_before (sequence, loop_start);
957:
958: /* Only the last copy of the loop body here needs the exit
959: test, so set copy_end to exclude the compare/branch here,
960: and then reset it inside the loop when get to the last
961: copy. */
962:
963: if (GET_CODE (last_loop_insn) == BARRIER)
964: copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
965: else if (GET_CODE (last_loop_insn) == JUMP_INSN)
966: {
967: #ifdef HAVE_cc0
1.1.1.2 root 968: /* The immediately preceding insn is a compare which we do not
1.1 root 969: want to copy. */
970: copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
971: #else
1.1.1.2 root 972: /* The immediately preceding insn may not be a compare, so we
1.1 root 973: must copy it. */
974: copy_end = PREV_INSN (last_loop_insn);
975: #endif
976: }
977: else
978: abort ();
979:
980: for (i = 1; i < unroll_number; i++)
981: {
982: emit_label_after (labels[unroll_number - i],
983: PREV_INSN (loop_start));
984:
1.1.1.7 root 985: bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
986: bzero ((char *) map->const_equiv_map, maxregnum * sizeof (rtx));
987: bzero ((char *) map->const_age_map,
988: maxregnum * sizeof (unsigned));
1.1 root 989: map->const_age = 0;
990:
991: for (j = 0; j < max_labelno; j++)
992: if (local_label[j])
993: map->label_map[j] = gen_label_rtx ();
994:
1.1.1.8 root 995: for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
996: if (local_regno[j])
997: map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
998:
1.1 root 999: /* The last copy needs the compare/branch insns at the end,
1000: so reset copy_end here if the loop ends with a conditional
1001: branch. */
1002:
1003: if (i == unroll_number - 1)
1004: {
1005: if (GET_CODE (last_loop_insn) == BARRIER)
1006: copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
1007: else
1008: copy_end = last_loop_insn;
1009: }
1010:
1011: /* None of the copies are the `last_iteration', so just
1012: pass zero for that parameter. */
1013: copy_loop_body (copy_start, copy_end, map, exit_label, 0,
1014: unroll_type, start_label, loop_end,
1015: loop_start, copy_end);
1016: }
1017: emit_label_after (labels[0], PREV_INSN (loop_start));
1018:
1019: if (GET_CODE (last_loop_insn) == BARRIER)
1020: {
1021: insert_before = PREV_INSN (last_loop_insn);
1022: copy_end = PREV_INSN (insert_before);
1023: }
1024: else
1025: {
1026: #ifdef HAVE_cc0
1.1.1.2 root 1027: /* The immediately preceding insn is a compare which we do not
1.1 root 1028: want to copy. */
1029: insert_before = PREV_INSN (last_loop_insn);
1030: copy_end = PREV_INSN (insert_before);
1031: #else
1.1.1.2 root 1032: /* The immediately preceding insn may not be a compare, so we
1.1 root 1033: must copy it. */
1034: insert_before = last_loop_insn;
1035: copy_end = PREV_INSN (last_loop_insn);
1036: #endif
1037: }
1038:
1039: /* Set unroll type to MODULO now. */
1040: unroll_type = UNROLL_MODULO;
1041: loop_preconditioned = 1;
1042: }
1043: }
1044:
1045: /* If reach here, and the loop type is UNROLL_NAIVE, then don't unroll
1046: the loop unless all loops are being unrolled. */
1047: if (unroll_type == UNROLL_NAIVE && ! flag_unroll_all_loops)
1048: {
1049: if (loop_dump_stream)
1050: fprintf (loop_dump_stream, "Unrolling failure: Naive unrolling not being done.\n");
1051: return;
1052: }
1053:
1054: /* At this point, we are guaranteed to unroll the loop. */
1055:
1056: /* For each biv and giv, determine whether it can be safely split into
1057: a different variable for each unrolled copy of the loop body.
1058: We precalculate and save this info here, since computing it is
1059: expensive.
1060:
1061: Do this before deleting any instructions from the loop, so that
1062: back_branch_in_range_p will work correctly. */
1063:
1064: if (splitting_not_safe)
1065: temp = 0;
1066: else
1067: temp = find_splittable_regs (unroll_type, loop_start, loop_end,
1068: end_insert_before, unroll_number);
1069:
1070: /* find_splittable_regs may have created some new registers, so must
1071: reallocate the reg_map with the new larger size, and must realloc
1072: the constant maps also. */
1073:
1074: maxregnum = max_reg_num ();
1075: map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx));
1076:
1077: init_reg_map (map, maxregnum);
1078:
1079: /* Space is needed in some of the map for new registers, so new_maxregnum
1080: is an (over)estimate of how many registers will exist at the end. */
1081: new_maxregnum = maxregnum + (temp * unroll_number * 2);
1082:
1083: /* Must realloc space for the constant maps, because the number of registers
1084: may have changed. */
1085:
1086: map->const_equiv_map = (rtx *) alloca (new_maxregnum * sizeof (rtx));
1087: map->const_age_map = (unsigned *) alloca (new_maxregnum * sizeof (unsigned));
1088:
1.1.1.6 root 1089: map->const_equiv_map_size = new_maxregnum;
1.1 root 1090: global_const_equiv_map = map->const_equiv_map;
1.1.1.6 root 1091: global_const_equiv_map_size = new_maxregnum;
1.1 root 1092:
1093: /* Search the list of bivs and givs to find ones which need to be remapped
1094: when split, and set their reg_map entry appropriately. */
1095:
1096: for (bl = loop_iv_list; bl; bl = bl->next)
1097: {
1098: if (REGNO (bl->biv->src_reg) != bl->regno)
1099: map->reg_map[bl->regno] = bl->biv->src_reg;
1100: #if 0
1101: /* Currently, non-reduced/final-value givs are never split. */
1102: for (v = bl->giv; v; v = v->next_iv)
1103: if (REGNO (v->src_reg) != bl->regno)
1104: map->reg_map[REGNO (v->dest_reg)] = v->src_reg;
1105: #endif
1106: }
1107:
1108: /* If the loop is being partially unrolled, and the iteration variables
1109: are being split, and are being renamed for the split, then must fix up
1.1.1.7 root 1110: the compare/jump instruction at the end of the loop to refer to the new
1.1 root 1111: registers. This compare isn't copied, so the registers used in it
1112: will never be replaced if it isn't done here. */
1113:
1114: if (unroll_type == UNROLL_MODULO)
1115: {
1116: insn = NEXT_INSN (copy_end);
1.1.1.7 root 1117: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1118: PATTERN (insn) = remap_split_bivs (PATTERN (insn));
1.1 root 1119: }
1120:
1121: /* For unroll_number - 1 times, make a copy of each instruction
1122: between copy_start and copy_end, and insert these new instructions
1123: before the end of the loop. */
1124:
1125: for (i = 0; i < unroll_number; i++)
1126: {
1.1.1.7 root 1127: bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
1128: bzero ((char *) map->const_equiv_map, new_maxregnum * sizeof (rtx));
1129: bzero ((char *) map->const_age_map, new_maxregnum * sizeof (unsigned));
1.1 root 1130: map->const_age = 0;
1131:
1132: for (j = 0; j < max_labelno; j++)
1133: if (local_label[j])
1134: map->label_map[j] = gen_label_rtx ();
1135:
1.1.1.8 root 1136: for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
1137: if (local_regno[j])
1138: map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
1139:
1.1 root 1140: /* If loop starts with a branch to the test, then fix it so that
1141: it points to the test of the first unrolled copy of the loop. */
1142: if (i == 0 && loop_start != copy_start)
1143: {
1144: insn = PREV_INSN (copy_start);
1145: pattern = PATTERN (insn);
1146:
1147: tem = map->label_map[CODE_LABEL_NUMBER
1148: (XEXP (SET_SRC (pattern), 0))];
1149: SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);
1150:
1151: /* Set the jump label so that it can be used by later loop unrolling
1152: passes. */
1153: JUMP_LABEL (insn) = tem;
1154: LABEL_NUSES (tem)++;
1155: }
1156:
1157: copy_loop_body (copy_start, copy_end, map, exit_label,
1158: i == unroll_number - 1, unroll_type, start_label,
1159: loop_end, insert_before, insert_before);
1160: }
1161:
1162: /* Before deleting any insns, emit a CODE_LABEL immediately after the last
1163: insn to be deleted. This prevents any runaway delete_insn call from
1164: more insns that it should, as it always stops at a CODE_LABEL. */
1165:
1166: /* Delete the compare and branch at the end of the loop if completely
1167: unrolling the loop. Deleting the backward branch at the end also
1168: deletes the code label at the start of the loop. This is done at
1169: the very end to avoid problems with back_branch_in_range_p. */
1170:
1171: if (unroll_type == UNROLL_COMPLETELY)
1172: safety_label = emit_label_after (gen_label_rtx (), last_loop_insn);
1173: else
1174: safety_label = emit_label_after (gen_label_rtx (), copy_end);
1175:
1176: /* Delete all of the original loop instructions. Don't delete the
1177: LOOP_BEG note, or the first code label in the loop. */
1178:
1179: insn = NEXT_INSN (copy_start);
1180: while (insn != safety_label)
1181: {
1182: if (insn != start_label)
1183: insn = delete_insn (insn);
1184: else
1185: insn = NEXT_INSN (insn);
1186: }
1187:
1188: /* Can now delete the 'safety' label emitted to protect us from runaway
1189: delete_insn calls. */
1190: if (INSN_DELETED_P (safety_label))
1191: abort ();
1192: delete_insn (safety_label);
1193:
1194: /* If exit_label exists, emit it after the loop. Doing the emit here
1195: forces it to have a higher INSN_UID than any insn in the unrolled loop.
1196: This is needed so that mostly_true_jump in reorg.c will treat jumps
1197: to this loop end label correctly, i.e. predict that they are usually
1198: not taken. */
1199: if (exit_label)
1200: emit_label_after (exit_label, loop_end);
1201: }
1202:
1203: /* Return true if the loop can be safely, and profitably, preconditioned
1204: so that the unrolled copies of the loop body don't need exit tests.
1205:
1206: This only works if final_value, initial_value and increment can be
1207: determined, and if increment is a constant power of 2.
1208: If increment is not a power of 2, then the preconditioning modulo
1209: operation would require a real modulo instead of a boolean AND, and this
1210: is not considered `profitable'. */
1211:
1212: /* ??? If the loop is known to be executed very many times, or the machine
1213: has a very cheap divide instruction, then preconditioning is a win even
1214: when the increment is not a power of 2. Use RTX_COST to compute
1215: whether divide is cheap. */
1216:
1217: static int
1218: precondition_loop_p (initial_value, final_value, increment, loop_start,
1219: loop_end)
1220: rtx *initial_value, *final_value, *increment;
1221: rtx loop_start, loop_end;
1222: {
1223:
1224: if (loop_n_iterations > 0)
1225: {
1226: *initial_value = const0_rtx;
1227: *increment = const1_rtx;
1.1.1.4 root 1228: *final_value = GEN_INT (loop_n_iterations);
1.1 root 1229:
1230: if (loop_dump_stream)
1231: fprintf (loop_dump_stream,
1232: "Preconditioning: Success, number of iterations known, %d.\n",
1233: loop_n_iterations);
1234: return 1;
1235: }
1236:
1237: if (loop_initial_value == 0)
1238: {
1239: if (loop_dump_stream)
1240: fprintf (loop_dump_stream,
1241: "Preconditioning: Could not find initial value.\n");
1242: return 0;
1243: }
1244: else if (loop_increment == 0)
1245: {
1246: if (loop_dump_stream)
1247: fprintf (loop_dump_stream,
1248: "Preconditioning: Could not find increment value.\n");
1249: return 0;
1250: }
1251: else if (GET_CODE (loop_increment) != CONST_INT)
1252: {
1253: if (loop_dump_stream)
1254: fprintf (loop_dump_stream,
1255: "Preconditioning: Increment not a constant.\n");
1256: return 0;
1257: }
1258: else if ((exact_log2 (INTVAL (loop_increment)) < 0)
1259: && (exact_log2 (- INTVAL (loop_increment)) < 0))
1260: {
1261: if (loop_dump_stream)
1262: fprintf (loop_dump_stream,
1263: "Preconditioning: Increment not a constant power of 2.\n");
1264: return 0;
1265: }
1266:
1267: /* Unsigned_compare and compare_dir can be ignored here, since they do
1268: not matter for preconditioning. */
1269:
1270: if (loop_final_value == 0)
1271: {
1272: if (loop_dump_stream)
1273: fprintf (loop_dump_stream,
1274: "Preconditioning: EQ comparison loop.\n");
1275: return 0;
1276: }
1277:
1278: /* Must ensure that final_value is invariant, so call invariant_p to
1279: check. Before doing so, must check regno against max_reg_before_loop
1.1.1.3 root 1280: to make sure that the register is in the range covered by invariant_p.
1.1 root 1281: If it isn't, then it is most likely a biv/giv which by definition are
1282: not invariant. */
1283: if ((GET_CODE (loop_final_value) == REG
1284: && REGNO (loop_final_value) >= max_reg_before_loop)
1285: || (GET_CODE (loop_final_value) == PLUS
1286: && REGNO (XEXP (loop_final_value, 0)) >= max_reg_before_loop)
1287: || ! invariant_p (loop_final_value))
1288: {
1289: if (loop_dump_stream)
1290: fprintf (loop_dump_stream,
1291: "Preconditioning: Final value not invariant.\n");
1292: return 0;
1293: }
1294:
1295: /* Fail for floating point values, since the caller of this function
1296: does not have code to deal with them. */
1297: if (GET_MODE_CLASS (GET_MODE (loop_final_value)) == MODE_FLOAT
1.1.1.2 root 1298: || GET_MODE_CLASS (GET_MODE (loop_initial_value)) == MODE_FLOAT)
1.1 root 1299: {
1300: if (loop_dump_stream)
1301: fprintf (loop_dump_stream,
1302: "Preconditioning: Floating point final or initial value.\n");
1303: return 0;
1304: }
1305:
1306: /* Now set initial_value to be the iteration_var, since that may be a
1307: simpler expression, and is guaranteed to be correct if all of the
1308: above tests succeed.
1309:
1310: We can not use the initial_value as calculated, because it will be
1311: one too small for loops of the form "while (i-- > 0)". We can not
1312: emit code before the loop_skip_over insns to fix this problem as this
1313: will then give a number one too large for loops of the form
1314: "while (--i > 0)".
1315:
1316: Note that all loops that reach here are entered at the top, because
1317: this function is not called if the loop starts with a jump. */
1318:
1319: /* Fail if loop_iteration_var is not live before loop_start, since we need
1320: to test its value in the preconditioning code. */
1321:
1322: if (uid_luid[regno_first_uid[REGNO (loop_iteration_var)]]
1323: > INSN_LUID (loop_start))
1324: {
1325: if (loop_dump_stream)
1326: fprintf (loop_dump_stream,
1327: "Preconditioning: Iteration var not live before loop start.\n");
1328: return 0;
1329: }
1330:
1331: *initial_value = loop_iteration_var;
1332: *increment = loop_increment;
1333: *final_value = loop_final_value;
1334:
1335: /* Success! */
1336: if (loop_dump_stream)
1337: fprintf (loop_dump_stream, "Preconditioning: Successful.\n");
1338: return 1;
1339: }
1340:
1341:
1342: /* All pseudo-registers must be mapped to themselves. Two hard registers
1343: must be mapped, VIRTUAL_STACK_VARS_REGNUM and VIRTUAL_INCOMING_ARGS_
1344: REGNUM, to avoid function-inlining specific conversions of these
1345: registers. All other hard regs can not be mapped because they may be
1346: used with different
1347: modes. */
1348:
1349: static void
1350: init_reg_map (map, maxregnum)
1351: struct inline_remap *map;
1352: int maxregnum;
1353: {
1354: int i;
1355:
1356: for (i = maxregnum - 1; i > LAST_VIRTUAL_REGISTER; i--)
1357: map->reg_map[i] = regno_reg_rtx[i];
1358: /* Just clear the rest of the entries. */
1359: for (i = LAST_VIRTUAL_REGISTER; i >= 0; i--)
1360: map->reg_map[i] = 0;
1361:
1362: map->reg_map[VIRTUAL_STACK_VARS_REGNUM]
1363: = regno_reg_rtx[VIRTUAL_STACK_VARS_REGNUM];
1364: map->reg_map[VIRTUAL_INCOMING_ARGS_REGNUM]
1365: = regno_reg_rtx[VIRTUAL_INCOMING_ARGS_REGNUM];
1366: }
1367:
1368: /* Strength-reduction will often emit code for optimized biv/givs which
1369: calculates their value in a temporary register, and then copies the result
1370: to the iv. This procedure reconstructs the pattern computing the iv;
1371: verifying that all operands are of the proper form.
1372:
1373: The return value is the amount that the giv is incremented by. */
1374:
1375: static rtx
1376: calculate_giv_inc (pattern, src_insn, regno)
1377: rtx pattern, src_insn;
1378: int regno;
1379: {
1380: rtx increment;
1.1.1.5 root 1381: rtx increment_total = 0;
1382: int tries = 0;
1.1 root 1383:
1.1.1.5 root 1384: retry:
1.1 root 1385: /* Verify that we have an increment insn here. First check for a plus
1386: as the set source. */
1387: if (GET_CODE (SET_SRC (pattern)) != PLUS)
1388: {
1389: /* SR sometimes computes the new giv value in a temp, then copies it
1390: to the new_reg. */
1391: src_insn = PREV_INSN (src_insn);
1392: pattern = PATTERN (src_insn);
1393: if (GET_CODE (SET_SRC (pattern)) != PLUS)
1394: abort ();
1395:
1396: /* The last insn emitted is not needed, so delete it to avoid confusing
1397: the second cse pass. This insn sets the giv unnecessarily. */
1398: delete_insn (get_last_insn ());
1399: }
1400:
1401: /* Verify that we have a constant as the second operand of the plus. */
1402: increment = XEXP (SET_SRC (pattern), 1);
1403: if (GET_CODE (increment) != CONST_INT)
1404: {
1405: /* SR sometimes puts the constant in a register, especially if it is
1406: too big to be an add immed operand. */
1.1.1.5 root 1407: src_insn = PREV_INSN (src_insn);
1408: increment = SET_SRC (PATTERN (src_insn));
1.1 root 1409:
1410: /* SR may have used LO_SUM to compute the constant if it is too large
1411: for a load immed operand. In this case, the constant is in operand
1412: one of the LO_SUM rtx. */
1413: if (GET_CODE (increment) == LO_SUM)
1414: increment = XEXP (increment, 1);
1.1.1.8 root 1415: else if (GET_CODE (increment) == IOR
1416: || GET_CODE (increment) == ASHIFT)
1.1.1.7 root 1417: {
1.1.1.8 root 1418: /* The rs6000 port loads some constants with IOR.
1419: The alpha port loads some constants with ASHIFT. */
1.1.1.7 root 1420: rtx second_part = XEXP (increment, 1);
1.1.1.8 root 1421: enum rtx_code code = GET_CODE (increment);
1.1.1.7 root 1422:
1423: src_insn = PREV_INSN (src_insn);
1424: increment = SET_SRC (PATTERN (src_insn));
1425: /* Don't need the last insn anymore. */
1426: delete_insn (get_last_insn ());
1427:
1428: if (GET_CODE (second_part) != CONST_INT
1429: || GET_CODE (increment) != CONST_INT)
1430: abort ();
1431:
1.1.1.8 root 1432: if (code == IOR)
1433: increment = GEN_INT (INTVAL (increment) | INTVAL (second_part));
1434: else
1435: increment = GEN_INT (INTVAL (increment) << INTVAL (second_part));
1.1.1.7 root 1436: }
1.1 root 1437:
1438: if (GET_CODE (increment) != CONST_INT)
1439: abort ();
1440:
1.1.1.7 root 1441: /* The insn loading the constant into a register is no longer needed,
1.1 root 1442: so delete it. */
1443: delete_insn (get_last_insn ());
1444: }
1445:
1.1.1.5 root 1446: if (increment_total)
1447: increment_total = GEN_INT (INTVAL (increment_total) + INTVAL (increment));
1448: else
1449: increment_total = increment;
1450:
1451: /* Check that the source register is the same as the register we expected
1452: to see as the source. If not, something is seriously wrong. */
1.1 root 1453: if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG
1454: || REGNO (XEXP (SET_SRC (pattern), 0)) != regno)
1.1.1.5 root 1455: {
1456: /* Some machines (e.g. the romp), may emit two add instructions for
1457: certain constants, so lets try looking for another add immediately
1458: before this one if we have only seen one add insn so far. */
1459:
1460: if (tries == 0)
1461: {
1462: tries++;
1463:
1464: src_insn = PREV_INSN (src_insn);
1465: pattern = PATTERN (src_insn);
1466:
1467: delete_insn (get_last_insn ());
1468:
1469: goto retry;
1470: }
1471:
1472: abort ();
1473: }
1474:
1475: return increment_total;
1476: }
1477:
1478: /* Copy REG_NOTES, except for insn references, because not all insn_map
1479: entries are valid yet. We do need to copy registers now though, because
1480: the reg_map entries can change during copying. */
1481:
1482: static rtx
1483: initial_reg_note_copy (notes, map)
1484: rtx notes;
1485: struct inline_remap *map;
1486: {
1487: rtx copy;
1488:
1489: if (notes == 0)
1490: return 0;
1491:
1492: copy = rtx_alloc (GET_CODE (notes));
1493: PUT_MODE (copy, GET_MODE (notes));
1494:
1495: if (GET_CODE (notes) == EXPR_LIST)
1496: XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map);
1497: else if (GET_CODE (notes) == INSN_LIST)
1498: /* Don't substitute for these yet. */
1499: XEXP (copy, 0) = XEXP (notes, 0);
1500: else
1.1 root 1501: abort ();
1502:
1.1.1.5 root 1503: XEXP (copy, 1) = initial_reg_note_copy (XEXP (notes, 1), map);
1504:
1505: return copy;
1.1 root 1506: }
1507:
1.1.1.5 root 1508: /* Fixup insn references in copied REG_NOTES. */
1509:
1510: static void
1511: final_reg_note_copy (notes, map)
1512: rtx notes;
1513: struct inline_remap *map;
1514: {
1515: rtx note;
1516:
1517: for (note = notes; note; note = XEXP (note, 1))
1518: if (GET_CODE (note) == INSN_LIST)
1519: XEXP (note, 0) = map->insn_map[INSN_UID (XEXP (note, 0))];
1520: }
1.1 root 1521:
1522: /* Copy each instruction in the loop, substituting from map as appropriate.
1523: This is very similar to a loop in expand_inline_function. */
1524:
1525: static void
1526: copy_loop_body (copy_start, copy_end, map, exit_label, last_iteration,
1527: unroll_type, start_label, loop_end, insert_before,
1528: copy_notes_from)
1529: rtx copy_start, copy_end;
1530: struct inline_remap *map;
1.1.1.4 root 1531: rtx exit_label;
1.1 root 1532: int last_iteration;
1533: enum unroll_types unroll_type;
1534: rtx start_label, loop_end, insert_before, copy_notes_from;
1535: {
1536: rtx insn, pattern;
1537: rtx tem, copy;
1538: int dest_reg_was_split, i;
1539: rtx cc0_insn = 0;
1540: rtx final_label = 0;
1541: rtx giv_inc, giv_dest_reg, giv_src_reg;
1542:
1543: /* If this isn't the last iteration, then map any references to the
1544: start_label to final_label. Final label will then be emitted immediately
1545: after the end of this loop body if it was ever used.
1546:
1547: If this is the last iteration, then map references to the start_label
1548: to itself. */
1549: if (! last_iteration)
1550: {
1551: final_label = gen_label_rtx ();
1552: map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label;
1553: }
1554: else
1555: map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label;
1556:
1557: start_sequence ();
1558:
1559: insn = copy_start;
1560: do
1561: {
1562: insn = NEXT_INSN (insn);
1563:
1564: map->orig_asm_operands_vector = 0;
1565:
1566: switch (GET_CODE (insn))
1567: {
1568: case INSN:
1569: pattern = PATTERN (insn);
1570: copy = 0;
1571: giv_inc = 0;
1572:
1573: /* Check to see if this is a giv that has been combined with
1574: some split address givs. (Combined in the sense that
1575: `combine_givs' in loop.c has put two givs in the same register.)
1576: In this case, we must search all givs based on the same biv to
1577: find the address givs. Then split the address givs.
1578: Do this before splitting the giv, since that may map the
1579: SET_DEST to a new register. */
1580:
1581: if (GET_CODE (pattern) == SET
1582: && GET_CODE (SET_DEST (pattern)) == REG
1583: && addr_combined_regs[REGNO (SET_DEST (pattern))])
1584: {
1585: struct iv_class *bl;
1586: struct induction *v, *tv;
1587: int regno = REGNO (SET_DEST (pattern));
1588:
1589: v = addr_combined_regs[REGNO (SET_DEST (pattern))];
1590: bl = reg_biv_class[REGNO (v->src_reg)];
1591:
1592: /* Although the giv_inc amount is not needed here, we must call
1593: calculate_giv_inc here since it might try to delete the
1594: last insn emitted. If we wait until later to call it,
1595: we might accidentally delete insns generated immediately
1596: below by emit_unrolled_add. */
1597:
1598: giv_inc = calculate_giv_inc (pattern, insn, regno);
1599:
1600: /* Now find all address giv's that were combined with this
1601: giv 'v'. */
1602: for (tv = bl->giv; tv; tv = tv->next_iv)
1603: if (tv->giv_type == DEST_ADDR && tv->same == v)
1604: {
1.1.1.3 root 1605: int this_giv_inc = INTVAL (giv_inc);
1606:
1607: /* Scale this_giv_inc if the multiplicative factors of
1608: the two givs are different. */
1609: if (tv->mult_val != v->mult_val)
1610: this_giv_inc = (this_giv_inc / INTVAL (v->mult_val)
1611: * INTVAL (tv->mult_val));
1612:
1613: tv->dest_reg = plus_constant (tv->dest_reg, this_giv_inc);
1.1 root 1614: *tv->location = tv->dest_reg;
1615:
1616: if (last_iteration && unroll_type != UNROLL_COMPLETELY)
1617: {
1618: /* Must emit an insn to increment the split address
1619: giv. Add in the const_adjust field in case there
1620: was a constant eliminated from the address. */
1621: rtx value, dest_reg;
1622:
1623: /* tv->dest_reg will be either a bare register,
1624: or else a register plus a constant. */
1625: if (GET_CODE (tv->dest_reg) == REG)
1626: dest_reg = tv->dest_reg;
1627: else
1628: dest_reg = XEXP (tv->dest_reg, 0);
1629:
1.1.1.7 root 1630: /* Check for shared address givs, and avoid
1.1.1.8 root 1631: incrementing the shared pseudo reg more than
1.1.1.7 root 1632: once. */
1.1.1.8 root 1633: if (! tv->same_insn)
1.1.1.7 root 1634: {
1635: /* tv->dest_reg may actually be a (PLUS (REG)
1636: (CONST)) here, so we must call plus_constant
1637: to add the const_adjust amount before calling
1638: emit_unrolled_add below. */
1639: value = plus_constant (tv->dest_reg,
1640: tv->const_adjust);
1641:
1642: /* The constant could be too large for an add
1643: immediate, so can't directly emit an insn
1644: here. */
1645: emit_unrolled_add (dest_reg, XEXP (value, 0),
1646: XEXP (value, 1));
1647: }
1.1 root 1648:
1649: /* Reset the giv to be just the register again, in case
1.1.1.2 root 1650: it is used after the set we have just emitted.
1651: We must subtract the const_adjust factor added in
1652: above. */
1653: tv->dest_reg = plus_constant (dest_reg,
1654: - tv->const_adjust);
1.1 root 1655: *tv->location = tv->dest_reg;
1656: }
1657: }
1658: }
1659:
1660: /* If this is a setting of a splittable variable, then determine
1661: how to split the variable, create a new set based on this split,
1662: and set up the reg_map so that later uses of the variable will
1663: use the new split variable. */
1664:
1665: dest_reg_was_split = 0;
1666:
1667: if (GET_CODE (pattern) == SET
1668: && GET_CODE (SET_DEST (pattern)) == REG
1669: && splittable_regs[REGNO (SET_DEST (pattern))])
1670: {
1671: int regno = REGNO (SET_DEST (pattern));
1672:
1673: dest_reg_was_split = 1;
1674:
1675: /* Compute the increment value for the giv, if it wasn't
1676: already computed above. */
1677:
1678: if (giv_inc == 0)
1679: giv_inc = calculate_giv_inc (pattern, insn, regno);
1680: giv_dest_reg = SET_DEST (pattern);
1681: giv_src_reg = SET_DEST (pattern);
1682:
1683: if (unroll_type == UNROLL_COMPLETELY)
1684: {
1685: /* Completely unrolling the loop. Set the induction
1686: variable to a known constant value. */
1687:
1688: /* The value in splittable_regs may be an invariant
1689: value, so we must use plus_constant here. */
1690: splittable_regs[regno]
1691: = plus_constant (splittable_regs[regno], INTVAL (giv_inc));
1692:
1693: if (GET_CODE (splittable_regs[regno]) == PLUS)
1694: {
1695: giv_src_reg = XEXP (splittable_regs[regno], 0);
1696: giv_inc = XEXP (splittable_regs[regno], 1);
1697: }
1698: else
1699: {
1700: /* The splittable_regs value must be a REG or a
1701: CONST_INT, so put the entire value in the giv_src_reg
1702: variable. */
1703: giv_src_reg = splittable_regs[regno];
1704: giv_inc = const0_rtx;
1705: }
1706: }
1707: else
1708: {
1709: /* Partially unrolling loop. Create a new pseudo
1710: register for the iteration variable, and set it to
1711: be a constant plus the original register. Except
1712: on the last iteration, when the result has to
1713: go back into the original iteration var register. */
1714:
1715: /* Handle bivs which must be mapped to a new register
1716: when split. This happens for bivs which need their
1717: final value set before loop entry. The new register
1718: for the biv was stored in the biv's first struct
1719: induction entry by find_splittable_regs. */
1720:
1721: if (regno < max_reg_before_loop
1722: && reg_iv_type[regno] == BASIC_INDUCT)
1723: {
1724: giv_src_reg = reg_biv_class[regno]->biv->src_reg;
1725: giv_dest_reg = giv_src_reg;
1726: }
1727:
1728: #if 0
1729: /* If non-reduced/final-value givs were split, then
1730: this would have to remap those givs also. See
1731: find_splittable_regs. */
1732: #endif
1733:
1734: splittable_regs[regno]
1.1.1.4 root 1735: = GEN_INT (INTVAL (giv_inc)
1.1 root 1736: + INTVAL (splittable_regs[regno]));
1737: giv_inc = splittable_regs[regno];
1738:
1739: /* Now split the induction variable by changing the dest
1740: of this insn to a new register, and setting its
1741: reg_map entry to point to this new register.
1742:
1743: If this is the last iteration, and this is the last insn
1744: that will update the iv, then reuse the original dest,
1745: to ensure that the iv will have the proper value when
1746: the loop exits or repeats.
1747:
1748: Using splittable_regs_updates here like this is safe,
1749: because it can only be greater than one if all
1750: instructions modifying the iv are always executed in
1751: order. */
1752:
1753: if (! last_iteration
1754: || (splittable_regs_updates[regno]-- != 1))
1755: {
1756: tem = gen_reg_rtx (GET_MODE (giv_src_reg));
1757: giv_dest_reg = tem;
1758: map->reg_map[regno] = tem;
1759: }
1760: else
1761: map->reg_map[regno] = giv_src_reg;
1762: }
1763:
1764: /* The constant being added could be too large for an add
1765: immediate, so can't directly emit an insn here. */
1766: emit_unrolled_add (giv_dest_reg, giv_src_reg, giv_inc);
1767: copy = get_last_insn ();
1768: pattern = PATTERN (copy);
1769: }
1770: else
1771: {
1772: pattern = copy_rtx_and_substitute (pattern, map);
1773: copy = emit_insn (pattern);
1774: }
1.1.1.5 root 1775: REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
1.1 root 1776:
1777: #ifdef HAVE_cc0
1778: /* If this insn is setting CC0, it may need to look at
1779: the insn that uses CC0 to see what type of insn it is.
1780: In that case, the call to recog via validate_change will
1781: fail. So don't substitute constants here. Instead,
1782: do it when we emit the following insn.
1783:
1784: For example, see the pyr.md file. That machine has signed and
1785: unsigned compares. The compare patterns must check the
1786: following branch insn to see which what kind of compare to
1787: emit.
1788:
1789: If the previous insn set CC0, substitute constants on it as
1790: well. */
1.1.1.8 root 1791: if (sets_cc0_p (PATTERN (copy)) != 0)
1.1 root 1792: cc0_insn = copy;
1793: else
1794: {
1795: if (cc0_insn)
1796: try_constants (cc0_insn, map);
1797: cc0_insn = 0;
1798: try_constants (copy, map);
1799: }
1800: #else
1801: try_constants (copy, map);
1802: #endif
1803:
1804: /* Make split induction variable constants `permanent' since we
1805: know there are no backward branches across iteration variable
1806: settings which would invalidate this. */
1807: if (dest_reg_was_split)
1808: {
1809: int regno = REGNO (SET_DEST (pattern));
1810:
1.1.1.6 root 1811: if (regno < map->const_equiv_map_size
1812: && map->const_age_map[regno] == map->const_age)
1.1 root 1813: map->const_age_map[regno] = -1;
1814: }
1815: break;
1816:
1817: case JUMP_INSN:
1.1.1.5 root 1818: pattern = copy_rtx_and_substitute (PATTERN (insn), map);
1819: copy = emit_jump_insn (pattern);
1820: REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
1821:
1.1 root 1822: if (JUMP_LABEL (insn) == start_label && insn == copy_end
1823: && ! last_iteration)
1824: {
1825: /* This is a branch to the beginning of the loop; this is the
1826: last insn being copied; and this is not the last iteration.
1827: In this case, we want to change the original fall through
1828: case to be a branch past the end of the loop, and the
1829: original jump label case to fall_through. */
1830:
1.1.1.7 root 1831: if (invert_exp (pattern, copy))
1832: {
1833: if (! redirect_exp (&pattern,
1834: map->label_map[CODE_LABEL_NUMBER
1835: (JUMP_LABEL (insn))],
1836: exit_label, copy))
1837: abort ();
1838: }
1839: else
1840: {
1841: rtx jmp;
1842: rtx lab = gen_label_rtx ();
1.1.1.8 root 1843: /* Can't do it by reversing the jump (probably because we
1844: couldn't reverse the conditions), so emit a new
1.1.1.7 root 1845: jump_insn after COPY, and redirect the jump around
1846: that. */
1847: jmp = emit_jump_insn_after (gen_jump (exit_label), copy);
1848: jmp = emit_barrier_after (jmp);
1849: emit_label_after (lab, jmp);
1850: LABEL_NUSES (lab) = 0;
1851: if (! redirect_exp (&pattern,
1852: map->label_map[CODE_LABEL_NUMBER
1853: (JUMP_LABEL (insn))],
1854: lab, copy))
1855: abort ();
1856: }
1.1 root 1857: }
1858:
1859: #ifdef HAVE_cc0
1860: if (cc0_insn)
1861: try_constants (cc0_insn, map);
1862: cc0_insn = 0;
1863: #endif
1864: try_constants (copy, map);
1865:
1866: /* Set the jump label of COPY correctly to avoid problems with
1867: later passes of unroll_loop, if INSN had jump label set. */
1868: if (JUMP_LABEL (insn))
1869: {
1.1.1.4 root 1870: rtx label = 0;
1871:
1.1 root 1872: /* Can't use the label_map for every insn, since this may be
1873: the backward branch, and hence the label was not mapped. */
1874: if (GET_CODE (pattern) == SET)
1875: {
1876: tem = SET_SRC (pattern);
1877: if (GET_CODE (tem) == LABEL_REF)
1.1.1.4 root 1878: label = XEXP (tem, 0);
1.1 root 1879: else if (GET_CODE (tem) == IF_THEN_ELSE)
1880: {
1881: if (XEXP (tem, 1) != pc_rtx)
1.1.1.4 root 1882: label = XEXP (XEXP (tem, 1), 0);
1.1 root 1883: else
1.1.1.4 root 1884: label = XEXP (XEXP (tem, 2), 0);
1.1 root 1885: }
1886: }
1.1.1.4 root 1887:
1888: if (label && GET_CODE (label) == CODE_LABEL)
1889: JUMP_LABEL (copy) = label;
1.1 root 1890: else
1891: {
1892: /* An unrecognizable jump insn, probably the entry jump
1893: for a switch statement. This label must have been mapped,
1894: so just use the label_map to get the new jump label. */
1.1.1.8 root 1895: JUMP_LABEL (copy)
1896: = map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))];
1.1 root 1897: }
1898:
1899: /* If this is a non-local jump, then must increase the label
1900: use count so that the label will not be deleted when the
1901: original jump is deleted. */
1902: LABEL_NUSES (JUMP_LABEL (copy))++;
1903: }
1904: else if (GET_CODE (PATTERN (copy)) == ADDR_VEC
1905: || GET_CODE (PATTERN (copy)) == ADDR_DIFF_VEC)
1906: {
1907: rtx pat = PATTERN (copy);
1908: int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1909: int len = XVECLEN (pat, diff_vec_p);
1910: int i;
1911:
1912: for (i = 0; i < len; i++)
1913: LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))++;
1914: }
1915:
1916: /* If this used to be a conditional jump insn but whose branch
1917: direction is now known, we must do something special. */
1918: if (condjump_p (insn) && !simplejump_p (insn) && map->last_pc_value)
1919: {
1920: #ifdef HAVE_cc0
1921: /* The previous insn set cc0 for us. So delete it. */
1922: delete_insn (PREV_INSN (copy));
1923: #endif
1924:
1925: /* If this is now a no-op, delete it. */
1926: if (map->last_pc_value == pc_rtx)
1927: {
1.1.1.7 root 1928: /* Don't let delete_insn delete the label referenced here,
1929: because we might possibly need it later for some other
1930: instruction in the loop. */
1931: if (JUMP_LABEL (copy))
1932: LABEL_NUSES (JUMP_LABEL (copy))++;
1.1 root 1933: delete_insn (copy);
1.1.1.7 root 1934: if (JUMP_LABEL (copy))
1935: LABEL_NUSES (JUMP_LABEL (copy))--;
1.1 root 1936: copy = 0;
1937: }
1938: else
1939: /* Otherwise, this is unconditional jump so we must put a
1940: BARRIER after it. We could do some dead code elimination
1941: here, but jump.c will do it just as well. */
1942: emit_barrier ();
1943: }
1944: break;
1945:
1946: case CALL_INSN:
1947: pattern = copy_rtx_and_substitute (PATTERN (insn), map);
1948: copy = emit_call_insn (pattern);
1.1.1.5 root 1949: REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
1.1 root 1950:
1.1.1.7 root 1951: /* Because the USAGE information potentially contains objects other
1952: than hard registers, we need to copy it. */
1953: CALL_INSN_FUNCTION_USAGE (copy) =
1954: copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn), map);
1955:
1.1 root 1956: #ifdef HAVE_cc0
1957: if (cc0_insn)
1958: try_constants (cc0_insn, map);
1959: cc0_insn = 0;
1960: #endif
1961: try_constants (copy, map);
1962:
1963: /* Be lazy and assume CALL_INSNs clobber all hard registers. */
1964: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1965: map->const_equiv_map[i] = 0;
1966: break;
1967:
1968: case CODE_LABEL:
1969: /* If this is the loop start label, then we don't need to emit a
1970: copy of this label since no one will use it. */
1971:
1972: if (insn != start_label)
1973: {
1974: copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
1975: map->const_age++;
1976: }
1977: break;
1978:
1979: case BARRIER:
1980: copy = emit_barrier ();
1981: break;
1982:
1983: case NOTE:
1.1.1.4 root 1984: /* VTOP notes are valid only before the loop exit test. If placed
1985: anywhere else, loop may generate bad code. */
1986:
1987: if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
1988: && (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
1989: || (last_iteration && unroll_type != UNROLL_COMPLETELY)))
1.1 root 1990: copy = emit_note (NOTE_SOURCE_FILE (insn),
1991: NOTE_LINE_NUMBER (insn));
1992: else
1993: copy = 0;
1994: break;
1995:
1996: default:
1997: abort ();
1998: break;
1999: }
2000:
2001: map->insn_map[INSN_UID (insn)] = copy;
2002: }
2003: while (insn != copy_end);
2004:
1.1.1.5 root 2005: /* Now finish coping the REG_NOTES. */
1.1 root 2006: insn = copy_start;
2007: do
2008: {
2009: insn = NEXT_INSN (insn);
2010: if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
2011: || GET_CODE (insn) == CALL_INSN)
2012: && map->insn_map[INSN_UID (insn)])
1.1.1.5 root 2013: final_reg_note_copy (REG_NOTES (map->insn_map[INSN_UID (insn)]), map);
1.1 root 2014: }
2015: while (insn != copy_end);
2016:
2017: /* There may be notes between copy_notes_from and loop_end. Emit a copy of
2018: each of these notes here, since there may be some important ones, such as
2019: NOTE_INSN_BLOCK_END notes, in this group. We don't do this on the last
2020: iteration, because the original notes won't be deleted.
2021:
2022: We can't use insert_before here, because when from preconditioning,
2023: insert_before points before the loop. We can't use copy_end, because
2024: there may be insns already inserted after it (which we don't want to
2025: copy) when not from preconditioning code. */
2026:
2027: if (! last_iteration)
2028: {
2029: for (insn = copy_notes_from; insn != loop_end; insn = NEXT_INSN (insn))
2030: {
2031: if (GET_CODE (insn) == NOTE
2032: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED)
2033: emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
2034: }
2035: }
2036:
2037: if (final_label && LABEL_NUSES (final_label) > 0)
2038: emit_label (final_label);
2039:
2040: tem = gen_sequence ();
2041: end_sequence ();
2042: emit_insn_before (tem, insert_before);
2043: }
2044:
2045: /* Emit an insn, using the expand_binop to ensure that a valid insn is
2046: emitted. This will correctly handle the case where the increment value
2047: won't fit in the immediate field of a PLUS insns. */
2048:
2049: void
2050: emit_unrolled_add (dest_reg, src_reg, increment)
2051: rtx dest_reg, src_reg, increment;
2052: {
2053: rtx result;
2054:
2055: result = expand_binop (GET_MODE (dest_reg), add_optab, src_reg, increment,
2056: dest_reg, 0, OPTAB_LIB_WIDEN);
2057:
2058: if (dest_reg != result)
2059: emit_move_insn (dest_reg, result);
2060: }
2061:
2062: /* Searches the insns between INSN and LOOP_END. Returns 1 if there
2063: is a backward branch in that range that branches to somewhere between
2064: LOOP_START and INSN. Returns 0 otherwise. */
2065:
1.1.1.3 root 2066: /* ??? This is quadratic algorithm. Could be rewritten to be linear.
1.1 root 2067: In practice, this is not a problem, because this function is seldom called,
2068: and uses a negligible amount of CPU time on average. */
2069:
1.1.1.8 root 2070: int
1.1 root 2071: back_branch_in_range_p (insn, loop_start, loop_end)
2072: rtx insn;
2073: rtx loop_start, loop_end;
2074: {
2075: rtx p, q, target_insn;
2076:
2077: /* Stop before we get to the backward branch at the end of the loop. */
2078: loop_end = prev_nonnote_insn (loop_end);
2079: if (GET_CODE (loop_end) == BARRIER)
2080: loop_end = PREV_INSN (loop_end);
2081:
2082: /* Check in case insn has been deleted, search forward for first non
2083: deleted insn following it. */
2084: while (INSN_DELETED_P (insn))
2085: insn = NEXT_INSN (insn);
2086:
2087: /* Check for the case where insn is the last insn in the loop. */
2088: if (insn == loop_end)
2089: return 0;
2090:
2091: for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p))
2092: {
2093: if (GET_CODE (p) == JUMP_INSN)
2094: {
2095: target_insn = JUMP_LABEL (p);
2096:
2097: /* Search from loop_start to insn, to see if one of them is
2098: the target_insn. We can't use INSN_LUID comparisons here,
2099: since insn may not have an LUID entry. */
2100: for (q = loop_start; q != insn; q = NEXT_INSN (q))
2101: if (q == target_insn)
2102: return 1;
2103: }
2104: }
2105:
2106: return 0;
2107: }
2108:
2109: /* Try to generate the simplest rtx for the expression
2110: (PLUS (MULT mult1 mult2) add1). This is used to calculate the initial
2111: value of giv's. */
2112:
2113: static rtx
2114: fold_rtx_mult_add (mult1, mult2, add1, mode)
2115: rtx mult1, mult2, add1;
2116: enum machine_mode mode;
2117: {
2118: rtx temp, mult_res;
2119: rtx result;
2120:
2121: /* The modes must all be the same. This should always be true. For now,
2122: check to make sure. */
2123: if ((GET_MODE (mult1) != mode && GET_MODE (mult1) != VOIDmode)
2124: || (GET_MODE (mult2) != mode && GET_MODE (mult2) != VOIDmode)
2125: || (GET_MODE (add1) != mode && GET_MODE (add1) != VOIDmode))
2126: abort ();
2127:
2128: /* Ensure that if at least one of mult1/mult2 are constant, then mult2
2129: will be a constant. */
2130: if (GET_CODE (mult1) == CONST_INT)
2131: {
2132: temp = mult2;
2133: mult2 = mult1;
2134: mult1 = temp;
2135: }
2136:
2137: mult_res = simplify_binary_operation (MULT, mode, mult1, mult2);
2138: if (! mult_res)
2139: mult_res = gen_rtx (MULT, mode, mult1, mult2);
2140:
2141: /* Again, put the constant second. */
2142: if (GET_CODE (add1) == CONST_INT)
2143: {
2144: temp = add1;
2145: add1 = mult_res;
2146: mult_res = temp;
2147: }
2148:
2149: result = simplify_binary_operation (PLUS, mode, add1, mult_res);
2150: if (! result)
2151: result = gen_rtx (PLUS, mode, add1, mult_res);
2152:
2153: return result;
2154: }
2155:
2156: /* Searches the list of induction struct's for the biv BL, to try to calculate
2157: the total increment value for one iteration of the loop as a constant.
2158:
2159: Returns the increment value as an rtx, simplified as much as possible,
2160: if it can be calculated. Otherwise, returns 0. */
2161:
2162: rtx
2163: biv_total_increment (bl, loop_start, loop_end)
2164: struct iv_class *bl;
2165: rtx loop_start, loop_end;
2166: {
2167: struct induction *v;
2168: rtx result;
2169:
2170: /* For increment, must check every instruction that sets it. Each
2171: instruction must be executed only once each time through the loop.
2172: To verify this, we check that the the insn is always executed, and that
2173: there are no backward branches after the insn that branch to before it.
2174: Also, the insn must have a mult_val of one (to make sure it really is
2175: an increment). */
2176:
2177: result = const0_rtx;
2178: for (v = bl->biv; v; v = v->next_iv)
2179: {
2180: if (v->always_computable && v->mult_val == const1_rtx
2181: && ! back_branch_in_range_p (v->insn, loop_start, loop_end))
2182: result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode);
2183: else
2184: return 0;
2185: }
2186:
2187: return result;
2188: }
2189:
2190: /* Determine the initial value of the iteration variable, and the amount
2191: that it is incremented each loop. Use the tables constructed by
2192: the strength reduction pass to calculate these values.
2193:
2194: Initial_value and/or increment are set to zero if their values could not
2195: be calculated. */
2196:
2197: static void
2198: iteration_info (iteration_var, initial_value, increment, loop_start, loop_end)
2199: rtx iteration_var, *initial_value, *increment;
2200: rtx loop_start, loop_end;
2201: {
2202: struct iv_class *bl;
2203: struct induction *v, *b;
2204:
2205: /* Clear the result values, in case no answer can be found. */
2206: *initial_value = 0;
2207: *increment = 0;
2208:
2209: /* The iteration variable can be either a giv or a biv. Check to see
2210: which it is, and compute the variable's initial value, and increment
2211: value if possible. */
2212:
2213: /* If this is a new register, can't handle it since we don't have any
2214: reg_iv_type entry for it. */
2215: if (REGNO (iteration_var) >= max_reg_before_loop)
2216: {
2217: if (loop_dump_stream)
2218: fprintf (loop_dump_stream,
2219: "Loop unrolling: No reg_iv_type entry for iteration var.\n");
2220: return;
2221: }
2222: /* Reject iteration variables larger than the host long size, since they
2223: could result in a number of iterations greater than the range of our
2224: `unsigned long' variable loop_n_iterations. */
2225: else if (GET_MODE_BITSIZE (GET_MODE (iteration_var)) > HOST_BITS_PER_LONG)
2226: {
2227: if (loop_dump_stream)
2228: fprintf (loop_dump_stream,
2229: "Loop unrolling: Iteration var rejected because mode larger than host long.\n");
2230: return;
2231: }
2232: else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
2233: {
2234: if (loop_dump_stream)
2235: fprintf (loop_dump_stream,
1.1.1.2 root 2236: "Loop unrolling: Iteration var not an integer.\n");
1.1 root 2237: return;
2238: }
2239: else if (reg_iv_type[REGNO (iteration_var)] == BASIC_INDUCT)
2240: {
2241: /* Grab initial value, only useful if it is a constant. */
2242: bl = reg_biv_class[REGNO (iteration_var)];
2243: *initial_value = bl->initial_value;
2244:
2245: *increment = biv_total_increment (bl, loop_start, loop_end);
2246: }
2247: else if (reg_iv_type[REGNO (iteration_var)] == GENERAL_INDUCT)
2248: {
2249: #if 1
2250: /* ??? The code below does not work because the incorrect number of
2251: iterations is calculated when the biv is incremented after the giv
2252: is set (which is the usual case). This can probably be accounted
2253: for by biasing the initial_value by subtracting the amount of the
2254: increment that occurs between the giv set and the giv test. However,
2255: a giv as an iterator is very rare, so it does not seem worthwhile
2256: to handle this. */
2257: /* ??? An example failure is: i = 6; do {;} while (i++ < 9). */
2258: if (loop_dump_stream)
2259: fprintf (loop_dump_stream,
2260: "Loop unrolling: Giv iterators are not handled.\n");
2261: return;
2262: #else
2263: /* Initial value is mult_val times the biv's initial value plus
2264: add_val. Only useful if it is a constant. */
2265: v = reg_iv_info[REGNO (iteration_var)];
2266: bl = reg_biv_class[REGNO (v->src_reg)];
2267: *initial_value = fold_rtx_mult_add (v->mult_val, bl->initial_value,
2268: v->add_val, v->mode);
2269:
2270: /* Increment value is mult_val times the increment value of the biv. */
2271:
2272: *increment = biv_total_increment (bl, loop_start, loop_end);
2273: if (*increment)
2274: *increment = fold_rtx_mult_add (v->mult_val, *increment, const0_rtx,
2275: v->mode);
2276: #endif
2277: }
2278: else
2279: {
2280: if (loop_dump_stream)
2281: fprintf (loop_dump_stream,
2282: "Loop unrolling: Not basic or general induction var.\n");
2283: return;
2284: }
2285: }
2286:
2287: /* Calculate the approximate final value of the iteration variable
2288: which has an loop exit test with code COMPARISON_CODE and comparison value
2289: of COMPARISON_VALUE. Also returns an indication of whether the comparison
2290: was signed or unsigned, and the direction of the comparison. This info is
2291: needed to calculate the number of loop iterations. */
2292:
2293: static rtx
2294: approx_final_value (comparison_code, comparison_value, unsigned_p, compare_dir)
2295: enum rtx_code comparison_code;
2296: rtx comparison_value;
2297: int *unsigned_p;
2298: int *compare_dir;
2299: {
2300: /* Calculate the final value of the induction variable.
2301: The exact final value depends on the branch operator, and increment sign.
2302: This is only an approximate value. It will be wrong if the iteration
2303: variable is not incremented by one each time through the loop, and
2304: approx final value - start value % increment != 0. */
2305:
2306: *unsigned_p = 0;
2307: switch (comparison_code)
2308: {
2309: case LEU:
2310: *unsigned_p = 1;
2311: case LE:
2312: *compare_dir = 1;
2313: return plus_constant (comparison_value, 1);
2314: case GEU:
2315: *unsigned_p = 1;
2316: case GE:
2317: *compare_dir = -1;
2318: return plus_constant (comparison_value, -1);
2319: case EQ:
2320: /* Can not calculate a final value for this case. */
2321: *compare_dir = 0;
2322: return 0;
2323: case LTU:
2324: *unsigned_p = 1;
2325: case LT:
2326: *compare_dir = 1;
2327: return comparison_value;
2328: break;
2329: case GTU:
2330: *unsigned_p = 1;
2331: case GT:
2332: *compare_dir = -1;
2333: return comparison_value;
2334: case NE:
2335: *compare_dir = 0;
2336: return comparison_value;
2337: default:
2338: abort ();
2339: }
2340: }
2341:
2342: /* For each biv and giv, determine whether it can be safely split into
2343: a different variable for each unrolled copy of the loop body. If it
2344: is safe to split, then indicate that by saving some useful info
2345: in the splittable_regs array.
2346:
2347: If the loop is being completely unrolled, then splittable_regs will hold
2348: the current value of the induction variable while the loop is unrolled.
2349: It must be set to the initial value of the induction variable here.
2350: Otherwise, splittable_regs will hold the difference between the current
2351: value of the induction variable and the value the induction variable had
1.1.1.6 root 2352: at the top of the loop. It must be set to the value 0 here.
2353:
2354: Returns the total number of instructions that set registers that are
2355: splittable. */
1.1 root 2356:
2357: /* ?? If the loop is only unrolled twice, then most of the restrictions to
2358: constant values are unnecessary, since we can easily calculate increment
2359: values in this case even if nothing is constant. The increment value
2360: should not involve a multiply however. */
2361:
2362: /* ?? Even if the biv/giv increment values aren't constant, it may still
2363: be beneficial to split the variable if the loop is only unrolled a few
2364: times, since multiplies by small integers (1,2,3,4) are very cheap. */
2365:
2366: static int
2367: find_splittable_regs (unroll_type, loop_start, loop_end, end_insert_before,
2368: unroll_number)
2369: enum unroll_types unroll_type;
2370: rtx loop_start, loop_end;
2371: rtx end_insert_before;
2372: int unroll_number;
2373: {
2374: struct iv_class *bl;
1.1.1.4 root 2375: struct induction *v;
1.1 root 2376: rtx increment, tem;
2377: rtx biv_final_value;
2378: int biv_splittable;
2379: int result = 0;
2380:
2381: for (bl = loop_iv_list; bl; bl = bl->next)
2382: {
2383: /* Biv_total_increment must return a constant value,
2384: otherwise we can not calculate the split values. */
2385:
2386: increment = biv_total_increment (bl, loop_start, loop_end);
2387: if (! increment || GET_CODE (increment) != CONST_INT)
2388: continue;
2389:
2390: /* The loop must be unrolled completely, or else have a known number
2391: of iterations and only one exit, or else the biv must be dead
2392: outside the loop, or else the final value must be known. Otherwise,
2393: it is unsafe to split the biv since it may not have the proper
2394: value on loop exit. */
2395:
1.1.1.8 root 2396: /* loop_number_exit_count is non-zero if the loop has an exit other than
1.1 root 2397: a fall through at the end. */
2398:
2399: biv_splittable = 1;
2400: biv_final_value = 0;
2401: if (unroll_type != UNROLL_COMPLETELY
1.1.1.8 root 2402: && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
1.1 root 2403: || unroll_type == UNROLL_NAIVE)
2404: && (uid_luid[regno_last_uid[bl->regno]] >= INSN_LUID (loop_end)
2405: || ! bl->init_insn
2406: || INSN_UID (bl->init_insn) >= max_uid_for_loop
2407: || (uid_luid[regno_first_uid[bl->regno]]
2408: < INSN_LUID (bl->init_insn))
2409: || reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
2410: && ! (biv_final_value = final_biv_value (bl, loop_start, loop_end)))
2411: biv_splittable = 0;
2412:
1.1.1.4 root 2413: /* If any of the insns setting the BIV don't do so with a simple
2414: PLUS, we don't know how to split it. */
2415: for (v = bl->biv; biv_splittable && v; v = v->next_iv)
2416: if ((tem = single_set (v->insn)) == 0
2417: || GET_CODE (SET_DEST (tem)) != REG
2418: || REGNO (SET_DEST (tem)) != bl->regno
2419: || GET_CODE (SET_SRC (tem)) != PLUS)
2420: biv_splittable = 0;
2421:
1.1 root 2422: /* If final value is non-zero, then must emit an instruction which sets
2423: the value of the biv to the proper value. This is done after
2424: handling all of the givs, since some of them may need to use the
2425: biv's value in their initialization code. */
2426:
2427: /* This biv is splittable. If completely unrolling the loop, save
2428: the biv's initial value. Otherwise, save the constant zero. */
2429:
2430: if (biv_splittable == 1)
2431: {
2432: if (unroll_type == UNROLL_COMPLETELY)
2433: {
2434: /* If the initial value of the biv is itself (i.e. it is too
2435: complicated for strength_reduce to compute), or is a hard
1.1.1.8 root 2436: register, or it isn't invariant, then we must create a new
2437: pseudo reg to hold the initial value of the biv. */
1.1 root 2438:
2439: if (GET_CODE (bl->initial_value) == REG
2440: && (REGNO (bl->initial_value) == bl->regno
1.1.1.8 root 2441: || REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER
2442: || ! invariant_p (bl->initial_value)))
1.1 root 2443: {
2444: rtx tem = gen_reg_rtx (bl->biv->mode);
2445:
2446: emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
2447: loop_start);
2448:
2449: if (loop_dump_stream)
2450: fprintf (loop_dump_stream, "Biv %d initial value remapped to %d.\n",
2451: bl->regno, REGNO (tem));
2452:
2453: splittable_regs[bl->regno] = tem;
2454: }
2455: else
2456: splittable_regs[bl->regno] = bl->initial_value;
2457: }
2458: else
2459: splittable_regs[bl->regno] = const0_rtx;
2460:
2461: /* Save the number of instructions that modify the biv, so that
2462: we can treat the last one specially. */
2463:
2464: splittable_regs_updates[bl->regno] = bl->biv_count;
1.1.1.6 root 2465: result += bl->biv_count;
1.1 root 2466:
2467: if (loop_dump_stream)
2468: fprintf (loop_dump_stream,
2469: "Biv %d safe to split.\n", bl->regno);
2470: }
2471:
2472: /* Check every giv that depends on this biv to see whether it is
2473: splittable also. Even if the biv isn't splittable, givs which
2474: depend on it may be splittable if the biv is live outside the
2475: loop, and the givs aren't. */
2476:
1.1.1.6 root 2477: result += find_splittable_givs (bl, unroll_type, loop_start, loop_end,
2478: increment, unroll_number);
1.1 root 2479:
2480: /* If final value is non-zero, then must emit an instruction which sets
2481: the value of the biv to the proper value. This is done after
2482: handling all of the givs, since some of them may need to use the
2483: biv's value in their initialization code. */
2484: if (biv_final_value)
2485: {
2486: /* If the loop has multiple exits, emit the insns before the
2487: loop to ensure that it will always be executed no matter
2488: how the loop exits. Otherwise emit the insn after the loop,
2489: since this is slightly more efficient. */
1.1.1.8 root 2490: if (! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
1.1 root 2491: emit_insn_before (gen_move_insn (bl->biv->src_reg,
2492: biv_final_value),
2493: end_insert_before);
2494: else
2495: {
2496: /* Create a new register to hold the value of the biv, and then
2497: set the biv to its final value before the loop start. The biv
2498: is set to its final value before loop start to ensure that
2499: this insn will always be executed, no matter how the loop
2500: exits. */
2501: rtx tem = gen_reg_rtx (bl->biv->mode);
2502: emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
2503: loop_start);
2504: emit_insn_before (gen_move_insn (bl->biv->src_reg,
2505: biv_final_value),
2506: loop_start);
2507:
2508: if (loop_dump_stream)
2509: fprintf (loop_dump_stream, "Biv %d mapped to %d for split.\n",
2510: REGNO (bl->biv->src_reg), REGNO (tem));
2511:
2512: /* Set up the mapping from the original biv register to the new
2513: register. */
2514: bl->biv->src_reg = tem;
2515: }
2516: }
2517: }
2518: return result;
2519: }
2520:
1.1.1.8 root 2521: /* Return 1 if the first and last unrolled copy of the address giv V is valid
2522: for the instruction that is using it. Do not make any changes to that
2523: instruction. */
2524:
2525: static int
2526: verify_addresses (v, giv_inc, unroll_number)
2527: struct induction *v;
2528: rtx giv_inc;
2529: int unroll_number;
2530: {
2531: int ret = 1;
2532: rtx orig_addr = *v->location;
2533: rtx last_addr = plus_constant (v->dest_reg,
2534: INTVAL (giv_inc) * (unroll_number - 1));
2535:
2536: /* First check to see if either address would fail. */
2537: if (! validate_change (v->insn, v->location, v->dest_reg, 0)
2538: || ! validate_change (v->insn, v->location, last_addr, 0))
2539: ret = 0;
2540:
2541: /* Now put things back the way they were before. This will always
2542: succeed. */
2543: validate_change (v->insn, v->location, orig_addr, 0);
2544:
2545: return ret;
2546: }
2547:
1.1 root 2548: /* For every giv based on the biv BL, check to determine whether it is
1.1.1.6 root 2549: splittable. This is a subroutine to find_splittable_regs ().
2550:
2551: Return the number of instructions that set splittable registers. */
1.1 root 2552:
2553: static int
2554: find_splittable_givs (bl, unroll_type, loop_start, loop_end, increment,
1.1.1.6 root 2555: unroll_number)
1.1 root 2556: struct iv_class *bl;
2557: enum unroll_types unroll_type;
2558: rtx loop_start, loop_end;
2559: rtx increment;
1.1.1.6 root 2560: int unroll_number;
1.1 root 2561: {
1.1.1.8 root 2562: struct induction *v, *v2;
1.1 root 2563: rtx final_value;
2564: rtx tem;
1.1.1.6 root 2565: int result = 0;
1.1 root 2566:
1.1.1.8 root 2567: /* Scan the list of givs, and set the same_insn field when there are
2568: multiple identical givs in the same insn. */
2569: for (v = bl->giv; v; v = v->next_iv)
2570: for (v2 = v->next_iv; v2; v2 = v2->next_iv)
2571: if (v->insn == v2->insn && rtx_equal_p (v->new_reg, v2->new_reg)
2572: && ! v2->same_insn)
2573: v2->same_insn = v;
2574:
1.1 root 2575: for (v = bl->giv; v; v = v->next_iv)
2576: {
2577: rtx giv_inc, value;
2578:
2579: /* Only split the giv if it has already been reduced, or if the loop is
2580: being completely unrolled. */
2581: if (unroll_type != UNROLL_COMPLETELY && v->ignore)
2582: continue;
2583:
2584: /* The giv can be split if the insn that sets the giv is executed once
2585: and only once on every iteration of the loop. */
2586: /* An address giv can always be split. v->insn is just a use not a set,
2587: and hence it does not matter whether it is always executed. All that
2588: matters is that all the biv increments are always executed, and we
2589: won't reach here if they aren't. */
2590: if (v->giv_type != DEST_ADDR
2591: && (! v->always_computable
2592: || back_branch_in_range_p (v->insn, loop_start, loop_end)))
2593: continue;
2594:
2595: /* The giv increment value must be a constant. */
2596: giv_inc = fold_rtx_mult_add (v->mult_val, increment, const0_rtx,
2597: v->mode);
2598: if (! giv_inc || GET_CODE (giv_inc) != CONST_INT)
2599: continue;
2600:
2601: /* The loop must be unrolled completely, or else have a known number of
2602: iterations and only one exit, or else the giv must be dead outside
2603: the loop, or else the final value of the giv must be known.
2604: Otherwise, it is not safe to split the giv since it may not have the
2605: proper value on loop exit. */
2606:
2607: /* The used outside loop test will fail for DEST_ADDR givs. They are
2608: never used outside the loop anyways, so it is always safe to split a
2609: DEST_ADDR giv. */
2610:
2611: final_value = 0;
2612: if (unroll_type != UNROLL_COMPLETELY
1.1.1.8 root 2613: && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
1.1 root 2614: || unroll_type == UNROLL_NAIVE)
2615: && v->giv_type != DEST_ADDR
2616: && ((regno_first_uid[REGNO (v->dest_reg)] != INSN_UID (v->insn)
2617: /* Check for the case where the pseudo is set by a shift/add
2618: sequence, in which case the first insn setting the pseudo
2619: is the first insn of the shift/add sequence. */
1.1.1.4 root 2620: && (! (tem = find_reg_note (v->insn, REG_RETVAL, NULL_RTX))
1.1 root 2621: || (regno_first_uid[REGNO (v->dest_reg)]
2622: != INSN_UID (XEXP (tem, 0)))))
2623: /* Line above always fails if INSN was moved by loop opt. */
2624: || (uid_luid[regno_last_uid[REGNO (v->dest_reg)]]
2625: >= INSN_LUID (loop_end)))
2626: && ! (final_value = v->final_value))
2627: continue;
2628:
2629: #if 0
2630: /* Currently, non-reduced/final-value givs are never split. */
2631: /* Should emit insns after the loop if possible, as the biv final value
2632: code below does. */
2633:
2634: /* If the final value is non-zero, and the giv has not been reduced,
2635: then must emit an instruction to set the final value. */
2636: if (final_value && !v->new_reg)
2637: {
2638: /* Create a new register to hold the value of the giv, and then set
2639: the giv to its final value before the loop start. The giv is set
2640: to its final value before loop start to ensure that this insn
2641: will always be executed, no matter how we exit. */
2642: tem = gen_reg_rtx (v->mode);
2643: emit_insn_before (gen_move_insn (tem, v->dest_reg), loop_start);
2644: emit_insn_before (gen_move_insn (v->dest_reg, final_value),
2645: loop_start);
2646:
2647: if (loop_dump_stream)
2648: fprintf (loop_dump_stream, "Giv %d mapped to %d for split.\n",
2649: REGNO (v->dest_reg), REGNO (tem));
2650:
2651: v->src_reg = tem;
2652: }
2653: #endif
2654:
2655: /* This giv is splittable. If completely unrolling the loop, save the
2656: giv's initial value. Otherwise, save the constant zero for it. */
2657:
2658: if (unroll_type == UNROLL_COMPLETELY)
1.1.1.4 root 2659: {
2660: /* It is not safe to use bl->initial_value here, because it may not
2661: be invariant. It is safe to use the initial value stored in
2662: the splittable_regs array if it is set. In rare cases, it won't
2663: be set, so then we do exactly the same thing as
2664: find_splittable_regs does to get a safe value. */
2665: rtx biv_initial_value;
2666:
2667: if (splittable_regs[bl->regno])
2668: biv_initial_value = splittable_regs[bl->regno];
2669: else if (GET_CODE (bl->initial_value) != REG
2670: || (REGNO (bl->initial_value) != bl->regno
2671: && REGNO (bl->initial_value) >= FIRST_PSEUDO_REGISTER))
2672: biv_initial_value = bl->initial_value;
2673: else
2674: {
2675: rtx tem = gen_reg_rtx (bl->biv->mode);
2676:
2677: emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
2678: loop_start);
2679: biv_initial_value = tem;
2680: }
2681: value = fold_rtx_mult_add (v->mult_val, biv_initial_value,
2682: v->add_val, v->mode);
2683: }
1.1 root 2684: else
2685: value = const0_rtx;
2686:
2687: if (v->new_reg)
2688: {
1.1.1.3 root 2689: /* If a giv was combined with another giv, then we can only split
2690: this giv if the giv it was combined with was reduced. This
2691: is because the value of v->new_reg is meaningless in this
2692: case. */
2693: if (v->same && ! v->same->new_reg)
1.1 root 2694: {
2695: if (loop_dump_stream)
2696: fprintf (loop_dump_stream,
1.1.1.3 root 2697: "giv combined with unreduced giv not split.\n");
2698: continue;
2699: }
2700: /* If the giv is an address destination, it could be something other
2701: than a simple register, these have to be treated differently. */
2702: else if (v->giv_type == DEST_REG)
2703: {
2704: /* If value is not a constant, register, or register plus
2705: constant, then compute its value into a register before
1.1.1.8 root 2706: loop start. This prevents invalid rtx sharing, and should
1.1.1.3 root 2707: generate better code. We can use bl->initial_value here
2708: instead of splittable_regs[bl->regno] because this code
2709: is going before the loop start. */
2710: if (unroll_type == UNROLL_COMPLETELY
2711: && GET_CODE (value) != CONST_INT
2712: && GET_CODE (value) != REG
2713: && (GET_CODE (value) != PLUS
2714: || GET_CODE (XEXP (value, 0)) != REG
2715: || GET_CODE (XEXP (value, 1)) != CONST_INT))
2716: {
2717: rtx tem = gen_reg_rtx (v->mode);
2718: emit_iv_add_mult (bl->initial_value, v->mult_val,
2719: v->add_val, tem, loop_start);
2720: value = tem;
2721: }
2722:
2723: splittable_regs[REGNO (v->new_reg)] = value;
1.1 root 2724: }
2725: else
2726: {
2727: /* Splitting address givs is useful since it will often allow us
2728: to eliminate some increment insns for the base giv as
2729: unnecessary. */
2730:
2731: /* If the addr giv is combined with a dest_reg giv, then all
2732: references to that dest reg will be remapped, which is NOT
2733: what we want for split addr regs. We always create a new
2734: register for the split addr giv, just to be safe. */
2735:
2736: /* ??? If there are multiple address givs which have been
2737: combined with the same dest_reg giv, then we may only need
2738: one new register for them. Pulling out constants below will
2739: catch some of the common cases of this. Currently, I leave
2740: the work of simplifying multiple address givs to the
2741: following cse pass. */
2742:
1.1.1.7 root 2743: /* As a special case, if we have multiple identical address givs
1.1.1.8 root 2744: within a single instruction, then we do use a single pseudo
1.1.1.7 root 2745: reg for both. This is necessary in case one is a match_dup
2746: of the other. */
2747:
1.1 root 2748: v->const_adjust = 0;
1.1.1.7 root 2749:
1.1.1.8 root 2750: if (v->same_insn)
1.1.1.7 root 2751: {
1.1.1.8 root 2752: v->dest_reg = v->same_insn->dest_reg;
1.1.1.7 root 2753: if (loop_dump_stream)
2754: fprintf (loop_dump_stream,
1.1.1.8 root 2755: "Sharing address givs in insn %d\n",
2756: INSN_UID (v->insn));
1.1.1.7 root 2757: }
2758: else if (unroll_type != UNROLL_COMPLETELY)
1.1 root 2759: {
2760: /* If not completely unrolling the loop, then create a new
2761: register to hold the split value of the DEST_ADDR giv.
2762: Emit insn to initialize its value before loop start. */
2763: tem = gen_reg_rtx (v->mode);
2764:
2765: /* If the address giv has a constant in its new_reg value,
2766: then this constant can be pulled out and put in value,
2767: instead of being part of the initialization code. */
2768:
2769: if (GET_CODE (v->new_reg) == PLUS
2770: && GET_CODE (XEXP (v->new_reg, 1)) == CONST_INT)
2771: {
2772: v->dest_reg
2773: = plus_constant (tem, INTVAL (XEXP (v->new_reg,1)));
2774:
2775: /* Only succeed if this will give valid addresses.
2776: Try to validate both the first and the last
2777: address resulting from loop unrolling, if
2778: one fails, then can't do const elim here. */
1.1.1.8 root 2779: if (! verify_addresses (v, giv_inc, unroll_number))
1.1 root 2780: {
2781: /* Save the negative of the eliminated const, so
2782: that we can calculate the dest_reg's increment
2783: value later. */
2784: v->const_adjust = - INTVAL (XEXP (v->new_reg, 1));
2785:
2786: v->new_reg = XEXP (v->new_reg, 0);
2787: if (loop_dump_stream)
2788: fprintf (loop_dump_stream,
2789: "Eliminating constant from giv %d\n",
2790: REGNO (tem));
2791: }
2792: else
2793: v->dest_reg = tem;
2794: }
2795: else
2796: v->dest_reg = tem;
2797:
2798: /* If the address hasn't been checked for validity yet, do so
2799: now, and fail completely if either the first or the last
1.1.1.8 root 2800: unrolled copy of the address is not a valid address
2801: for the instruction that uses it. */
1.1 root 2802: if (v->dest_reg == tem
1.1.1.8 root 2803: && ! verify_addresses (v, giv_inc, unroll_number))
1.1 root 2804: {
2805: if (loop_dump_stream)
2806: fprintf (loop_dump_stream,
1.1.1.8 root 2807: "Invalid address for giv at insn %d\n",
1.1 root 2808: INSN_UID (v->insn));
2809: continue;
2810: }
2811:
2812: /* To initialize the new register, just move the value of
2813: new_reg into it. This is not guaranteed to give a valid
2814: instruction on machines with complex addressing modes.
2815: If we can't recognize it, then delete it and emit insns
2816: to calculate the value from scratch. */
2817: emit_insn_before (gen_rtx (SET, VOIDmode, tem,
2818: copy_rtx (v->new_reg)),
2819: loop_start);
1.1.1.4 root 2820: if (recog_memoized (PREV_INSN (loop_start)) < 0)
1.1 root 2821: {
1.1.1.7 root 2822: rtx sequence, ret;
2823:
2824: /* We can't use bl->initial_value to compute the initial
2825: value, because the loop may have been preconditioned.
2826: We must calculate it from NEW_REG. Try using
2827: force_operand instead of emit_iv_add_mult. */
1.1 root 2828: delete_insn (PREV_INSN (loop_start));
1.1.1.7 root 2829:
2830: start_sequence ();
2831: ret = force_operand (v->new_reg, tem);
2832: if (ret != tem)
2833: emit_move_insn (tem, ret);
2834: sequence = gen_sequence ();
2835: end_sequence ();
2836: emit_insn_before (sequence, loop_start);
2837:
1.1 root 2838: if (loop_dump_stream)
2839: fprintf (loop_dump_stream,
1.1.1.8 root 2840: "Invalid init insn, rewritten.\n");
1.1 root 2841: }
2842: }
2843: else
2844: {
2845: v->dest_reg = value;
2846:
2847: /* Check the resulting address for validity, and fail
1.1.1.8 root 2848: if the resulting address would be invalid. */
2849: if (! verify_addresses (v, giv_inc, unroll_number))
1.1 root 2850: {
2851: if (loop_dump_stream)
2852: fprintf (loop_dump_stream,
1.1.1.8 root 2853: "Invalid address for giv at insn %d\n",
1.1 root 2854: INSN_UID (v->insn));
2855: continue;
2856: }
2857: }
2858:
2859: /* Store the value of dest_reg into the insn. This sharing
2860: will not be a problem as this insn will always be copied
2861: later. */
2862:
2863: *v->location = v->dest_reg;
2864:
2865: /* If this address giv is combined with a dest reg giv, then
2866: save the base giv's induction pointer so that we will be
2867: able to handle this address giv properly. The base giv
2868: itself does not have to be splittable. */
2869:
2870: if (v->same && v->same->giv_type == DEST_REG)
2871: addr_combined_regs[REGNO (v->same->new_reg)] = v->same;
2872:
2873: if (GET_CODE (v->new_reg) == REG)
2874: {
2875: /* This giv maybe hasn't been combined with any others.
2876: Make sure that it's giv is marked as splittable here. */
2877:
2878: splittable_regs[REGNO (v->new_reg)] = value;
2879:
2880: /* Make it appear to depend upon itself, so that the
2881: giv will be properly split in the main loop above. */
2882: if (! v->same)
2883: {
2884: v->same = v;
2885: addr_combined_regs[REGNO (v->new_reg)] = v;
2886: }
2887: }
1.1.1.2 root 2888:
1.1 root 2889: if (loop_dump_stream)
2890: fprintf (loop_dump_stream, "DEST_ADDR giv being split.\n");
2891: }
2892: }
2893: else
2894: {
2895: #if 0
2896: /* Currently, unreduced giv's can't be split. This is not too much
2897: of a problem since unreduced giv's are not live across loop
2898: iterations anyways. When unrolling a loop completely though,
2899: it makes sense to reduce&split givs when possible, as this will
2900: result in simpler instructions, and will not require that a reg
2901: be live across loop iterations. */
2902:
2903: splittable_regs[REGNO (v->dest_reg)] = value;
2904: fprintf (stderr, "Giv %d at insn %d not reduced\n",
2905: REGNO (v->dest_reg), INSN_UID (v->insn));
2906: #else
2907: continue;
2908: #endif
2909: }
2910:
1.1.1.9 ! root 2911: /* Unreduced givs are only updated once by definition. Reduced givs
! 2912: are updated as many times as their biv is. Mark it so if this is
1.1 root 2913: a splittable register. Don't need to do anything for address givs
2914: where this may not be a register. */
2915:
2916: if (GET_CODE (v->new_reg) == REG)
1.1.1.9 ! root 2917: {
! 2918: int count = 1;
! 2919: if (! v->ignore)
! 2920: count = reg_biv_class[REGNO (v->src_reg)]->biv_count;
! 2921:
! 2922: splittable_regs_updates[REGNO (v->new_reg)] = count;
! 2923: }
1.1 root 2924:
2925: result++;
2926:
2927: if (loop_dump_stream)
2928: {
2929: int regnum;
2930:
2931: if (GET_CODE (v->dest_reg) == CONST_INT)
2932: regnum = -1;
2933: else if (GET_CODE (v->dest_reg) != REG)
2934: regnum = REGNO (XEXP (v->dest_reg, 0));
2935: else
2936: regnum = REGNO (v->dest_reg);
2937: fprintf (loop_dump_stream, "Giv %d at insn %d safe to split.\n",
2938: regnum, INSN_UID (v->insn));
2939: }
2940: }
2941:
2942: return result;
2943: }
2944:
2945: /* Try to prove that the register is dead after the loop exits. Trace every
2946: loop exit looking for an insn that will always be executed, which sets
2947: the register to some value, and appears before the first use of the register
2948: is found. If successful, then return 1, otherwise return 0. */
2949:
2950: /* ?? Could be made more intelligent in the handling of jumps, so that
2951: it can search past if statements and other similar structures. */
2952:
2953: static int
2954: reg_dead_after_loop (reg, loop_start, loop_end)
2955: rtx reg, loop_start, loop_end;
2956: {
2957: rtx insn, label;
2958: enum rtx_code code;
1.1.1.2 root 2959: int jump_count = 0;
1.1.1.8 root 2960: int label_count = 0;
2961: int this_loop_num = uid_loop_num[INSN_UID (loop_start)];
2962:
2963: /* In addition to checking all exits of this loop, we must also check
2964: all exits of inner nested loops that would exit this loop. We don't
2965: have any way to identify those, so we just give up if there are any
2966: such inner loop exits. */
2967:
2968: for (label = loop_number_exit_labels[this_loop_num]; label;
2969: label = LABEL_NEXTREF (label))
2970: label_count++;
2971:
2972: if (label_count != loop_number_exit_count[this_loop_num])
2973: return 0;
1.1 root 2974:
2975: /* HACK: Must also search the loop fall through exit, create a label_ref
2976: here which points to the loop_end, and append the loop_number_exit_labels
2977: list to it. */
2978: label = gen_rtx (LABEL_REF, VOIDmode, loop_end);
1.1.1.8 root 2979: LABEL_NEXTREF (label) = loop_number_exit_labels[this_loop_num];
1.1 root 2980:
2981: for ( ; label; label = LABEL_NEXTREF (label))
2982: {
2983: /* Succeed if find an insn which sets the biv or if reach end of
2984: function. Fail if find an insn that uses the biv, or if come to
2985: a conditional jump. */
2986:
2987: insn = NEXT_INSN (XEXP (label, 0));
1.1.1.2 root 2988: while (insn)
1.1 root 2989: {
1.1.1.2 root 2990: code = GET_CODE (insn);
2991: if (GET_RTX_CLASS (code) == 'i')
1.1 root 2992: {
1.1.1.2 root 2993: rtx set;
2994:
2995: if (reg_referenced_p (reg, PATTERN (insn)))
1.1 root 2996: return 0;
1.1.1.2 root 2997:
2998: set = single_set (insn);
2999: if (set && rtx_equal_p (SET_DEST (set), reg))
3000: break;
1.1 root 3001: }
1.1.1.2 root 3002:
1.1 root 3003: if (code == JUMP_INSN)
3004: {
3005: if (GET_CODE (PATTERN (insn)) == RETURN)
3006: break;
1.1.1.2 root 3007: else if (! simplejump_p (insn)
3008: /* Prevent infinite loop following infinite loops. */
3009: || jump_count++ > 20)
1.1 root 3010: return 0;
3011: else
1.1.1.2 root 3012: insn = JUMP_LABEL (insn);
1.1 root 3013: }
1.1.1.2 root 3014:
1.1 root 3015: insn = NEXT_INSN (insn);
3016: }
3017: }
3018:
3019: /* Success, the register is dead on all loop exits. */
3020: return 1;
3021: }
3022:
3023: /* Try to calculate the final value of the biv, the value it will have at
3024: the end of the loop. If we can do it, return that value. */
3025:
3026: rtx
3027: final_biv_value (bl, loop_start, loop_end)
3028: struct iv_class *bl;
3029: rtx loop_start, loop_end;
3030: {
3031: rtx increment, tem;
3032:
1.1.1.2 root 3033: /* ??? This only works for MODE_INT biv's. Reject all others for now. */
3034:
3035: if (GET_MODE_CLASS (bl->biv->mode) != MODE_INT)
3036: return 0;
3037:
1.1 root 3038: /* The final value for reversed bivs must be calculated differently than
3039: for ordinary bivs. In this case, there is already an insn after the
3040: loop which sets this biv's final value (if necessary), and there are
3041: no other loop exits, so we can return any value. */
3042: if (bl->reversed)
3043: {
3044: if (loop_dump_stream)
3045: fprintf (loop_dump_stream,
3046: "Final biv value for %d, reversed biv.\n", bl->regno);
3047:
3048: return const0_rtx;
3049: }
3050:
3051: /* Try to calculate the final value as initial value + (number of iterations
3052: * increment). For this to work, increment must be invariant, the only
3053: exit from the loop must be the fall through at the bottom (otherwise
3054: it may not have its final value when the loop exits), and the initial
3055: value of the biv must be invariant. */
3056:
3057: if (loop_n_iterations != 0
1.1.1.8 root 3058: && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
1.1 root 3059: && invariant_p (bl->initial_value))
3060: {
3061: increment = biv_total_increment (bl, loop_start, loop_end);
3062:
3063: if (increment && invariant_p (increment))
3064: {
3065: /* Can calculate the loop exit value, emit insns after loop
3066: end to calculate this value into a temporary register in
3067: case it is needed later. */
3068:
3069: tem = gen_reg_rtx (bl->biv->mode);
1.1.1.4 root 3070: /* Make sure loop_end is not the last insn. */
3071: if (NEXT_INSN (loop_end) == 0)
3072: emit_note_after (NOTE_INSN_DELETED, loop_end);
3073: emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
1.1 root 3074: bl->initial_value, tem, NEXT_INSN (loop_end));
3075:
3076: if (loop_dump_stream)
3077: fprintf (loop_dump_stream,
3078: "Final biv value for %d, calculated.\n", bl->regno);
3079:
3080: return tem;
3081: }
3082: }
3083:
3084: /* Check to see if the biv is dead at all loop exits. */
3085: if (reg_dead_after_loop (bl->biv->src_reg, loop_start, loop_end))
3086: {
3087: if (loop_dump_stream)
3088: fprintf (loop_dump_stream,
3089: "Final biv value for %d, biv dead after loop exit.\n",
3090: bl->regno);
3091:
3092: return const0_rtx;
3093: }
3094:
3095: return 0;
3096: }
3097:
3098: /* Try to calculate the final value of the giv, the value it will have at
3099: the end of the loop. If we can do it, return that value. */
3100:
3101: rtx
3102: final_giv_value (v, loop_start, loop_end)
3103: struct induction *v;
3104: rtx loop_start, loop_end;
3105: {
3106: struct iv_class *bl;
1.1.1.4 root 3107: rtx insn;
1.1 root 3108: rtx increment, tem;
1.1.1.3 root 3109: rtx insert_before, seq;
1.1 root 3110:
3111: bl = reg_biv_class[REGNO (v->src_reg)];
3112:
3113: /* The final value for givs which depend on reversed bivs must be calculated
3114: differently than for ordinary givs. In this case, there is already an
3115: insn after the loop which sets this giv's final value (if necessary),
3116: and there are no other loop exits, so we can return any value. */
3117: if (bl->reversed)
3118: {
3119: if (loop_dump_stream)
3120: fprintf (loop_dump_stream,
3121: "Final giv value for %d, depends on reversed biv\n",
3122: REGNO (v->dest_reg));
3123: return const0_rtx;
3124: }
3125:
3126: /* Try to calculate the final value as a function of the biv it depends
3127: upon. The only exit from the loop must be the fall through at the bottom
3128: (otherwise it may not have its final value when the loop exits). */
3129:
3130: /* ??? Can calculate the final giv value by subtracting off the
3131: extra biv increments times the giv's mult_val. The loop must have
3132: only one exit for this to work, but the loop iterations does not need
3133: to be known. */
3134:
3135: if (loop_n_iterations != 0
1.1.1.8 root 3136: && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
1.1 root 3137: {
3138: /* ?? It is tempting to use the biv's value here since these insns will
3139: be put after the loop, and hence the biv will have its final value
3140: then. However, this fails if the biv is subsequently eliminated.
3141: Perhaps determine whether biv's are eliminable before trying to
3142: determine whether giv's are replaceable so that we can use the
3143: biv value here if it is not eliminable. */
3144:
3145: increment = biv_total_increment (bl, loop_start, loop_end);
3146:
3147: if (increment && invariant_p (increment))
3148: {
3149: /* Can calculate the loop exit value of its biv as
3150: (loop_n_iterations * increment) + initial_value */
3151:
3152: /* The loop exit value of the giv is then
3153: (final_biv_value - extra increments) * mult_val + add_val.
3154: The extra increments are any increments to the biv which
3155: occur in the loop after the giv's value is calculated.
3156: We must search from the insn that sets the giv to the end
3157: of the loop to calculate this value. */
3158:
3159: insert_before = NEXT_INSN (loop_end);
3160:
3161: /* Put the final biv value in tem. */
3162: tem = gen_reg_rtx (bl->biv->mode);
1.1.1.4 root 3163: emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
1.1 root 3164: bl->initial_value, tem, insert_before);
3165:
3166: /* Subtract off extra increments as we find them. */
3167: for (insn = NEXT_INSN (v->insn); insn != loop_end;
3168: insn = NEXT_INSN (insn))
3169: {
1.1.1.4 root 3170: struct induction *biv;
3171:
3172: for (biv = bl->biv; biv; biv = biv->next_iv)
3173: if (biv->insn == insn)
3174: {
3175: start_sequence ();
3176: tem = expand_binop (GET_MODE (tem), sub_optab, tem,
3177: biv->add_val, NULL_RTX, 0,
3178: OPTAB_LIB_WIDEN);
3179: seq = gen_sequence ();
3180: end_sequence ();
3181: emit_insn_before (seq, insert_before);
3182: }
1.1 root 3183: }
3184:
3185: /* Now calculate the giv's final value. */
3186: emit_iv_add_mult (tem, v->mult_val, v->add_val, tem,
3187: insert_before);
3188:
3189: if (loop_dump_stream)
3190: fprintf (loop_dump_stream,
3191: "Final giv value for %d, calc from biv's value.\n",
3192: REGNO (v->dest_reg));
3193:
3194: return tem;
3195: }
3196: }
3197:
3198: /* Replaceable giv's should never reach here. */
3199: if (v->replaceable)
3200: abort ();
3201:
3202: /* Check to see if the biv is dead at all loop exits. */
3203: if (reg_dead_after_loop (v->dest_reg, loop_start, loop_end))
3204: {
3205: if (loop_dump_stream)
3206: fprintf (loop_dump_stream,
3207: "Final giv value for %d, giv dead after loop exit.\n",
3208: REGNO (v->dest_reg));
3209:
3210: return const0_rtx;
3211: }
3212:
3213: return 0;
3214: }
3215:
3216:
3217: /* Calculate the number of loop iterations. Returns the exact number of loop
1.1.1.3 root 3218: iterations if it can be calculated, otherwise returns zero. */
1.1 root 3219:
1.1.1.4 root 3220: unsigned HOST_WIDE_INT
1.1 root 3221: loop_iterations (loop_start, loop_end)
3222: rtx loop_start, loop_end;
3223: {
3224: rtx comparison, comparison_value;
3225: rtx iteration_var, initial_value, increment, final_value;
3226: enum rtx_code comparison_code;
1.1.1.4 root 3227: HOST_WIDE_INT i;
3228: int increment_dir;
1.1 root 3229: int unsigned_compare, compare_dir, final_larger;
3230: unsigned long tempu;
3231: rtx last_loop_insn;
3232:
3233: /* First find the iteration variable. If the last insn is a conditional
3234: branch, and the insn before tests a register value, make that the
3235: iteration variable. */
3236:
3237: loop_initial_value = 0;
3238: loop_increment = 0;
3239: loop_final_value = 0;
3240: loop_iteration_var = 0;
3241:
1.1.1.7 root 3242: /* We used to use pren_nonnote_insn here, but that fails because it might
3243: accidentally get the branch for a contained loop if the branch for this
3244: loop was deleted. We can only trust branches immediately before the
3245: loop_end. */
3246: last_loop_insn = PREV_INSN (loop_end);
1.1 root 3247:
3248: comparison = get_condition_for_loop (last_loop_insn);
3249: if (comparison == 0)
3250: {
3251: if (loop_dump_stream)
3252: fprintf (loop_dump_stream,
3253: "Loop unrolling: No final conditional branch found.\n");
3254: return 0;
3255: }
3256:
3257: /* ??? Get_condition may switch position of induction variable and
3258: invariant register when it canonicalizes the comparison. */
3259:
3260: comparison_code = GET_CODE (comparison);
3261: iteration_var = XEXP (comparison, 0);
3262: comparison_value = XEXP (comparison, 1);
3263:
3264: if (GET_CODE (iteration_var) != REG)
3265: {
3266: if (loop_dump_stream)
3267: fprintf (loop_dump_stream,
3268: "Loop unrolling: Comparison not against register.\n");
3269: return 0;
3270: }
3271:
3272: /* Loop iterations is always called before any new registers are created
3273: now, so this should never occur. */
3274:
3275: if (REGNO (iteration_var) >= max_reg_before_loop)
3276: abort ();
3277:
3278: iteration_info (iteration_var, &initial_value, &increment,
3279: loop_start, loop_end);
3280: if (initial_value == 0)
3281: /* iteration_info already printed a message. */
3282: return 0;
3283:
3284: /* If the comparison value is an invariant register, then try to find
3285: its value from the insns before the start of the loop. */
3286:
3287: if (GET_CODE (comparison_value) == REG && invariant_p (comparison_value))
3288: {
3289: rtx insn, set;
3290:
3291: for (insn = PREV_INSN (loop_start); insn ; insn = PREV_INSN (insn))
3292: {
3293: if (GET_CODE (insn) == CODE_LABEL)
3294: break;
3295:
3296: else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
1.1.1.5 root 3297: && reg_set_p (comparison_value, insn))
1.1 root 3298: {
1.1.1.5 root 3299: /* We found the last insn before the loop that sets the register.
3300: If it sets the entire register, and has a REG_EQUAL note,
3301: then use the value of the REG_EQUAL note. */
3302: if ((set = single_set (insn))
3303: && (SET_DEST (set) == comparison_value))
3304: {
3305: rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1.1 root 3306:
1.1.1.7 root 3307: /* Only use the REG_EQUAL note if it is a constant.
3308: Other things, divide in particular, will cause
3309: problems later if we use them. */
3310: if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST
3311: && CONSTANT_P (XEXP (note, 0)))
1.1.1.5 root 3312: comparison_value = XEXP (note, 0);
3313: }
1.1 root 3314: break;
3315: }
3316: }
3317: }
3318:
3319: final_value = approx_final_value (comparison_code, comparison_value,
3320: &unsigned_compare, &compare_dir);
3321:
3322: /* Save the calculated values describing this loop's bounds, in case
3323: precondition_loop_p will need them later. These values can not be
3324: recalculated inside precondition_loop_p because strength reduction
3325: optimizations may obscure the loop's structure. */
3326:
3327: loop_iteration_var = iteration_var;
3328: loop_initial_value = initial_value;
3329: loop_increment = increment;
3330: loop_final_value = final_value;
3331:
1.1.1.7 root 3332: if (increment == 0)
3333: {
3334: if (loop_dump_stream)
3335: fprintf (loop_dump_stream,
3336: "Loop unrolling: Increment value can't be calculated.\n");
3337: return 0;
3338: }
3339: else if (GET_CODE (increment) != CONST_INT)
3340: {
3341: if (loop_dump_stream)
3342: fprintf (loop_dump_stream,
3343: "Loop unrolling: Increment value not constant.\n");
3344: return 0;
3345: }
3346: else if (GET_CODE (initial_value) != CONST_INT)
3347: {
3348: if (loop_dump_stream)
3349: fprintf (loop_dump_stream,
3350: "Loop unrolling: Initial value not constant.\n");
3351: return 0;
3352: }
3353: else if (final_value == 0)
1.1 root 3354: {
3355: if (loop_dump_stream)
3356: fprintf (loop_dump_stream,
3357: "Loop unrolling: EQ comparison loop.\n");
3358: return 0;
3359: }
3360: else if (GET_CODE (final_value) != CONST_INT)
3361: {
3362: if (loop_dump_stream)
3363: fprintf (loop_dump_stream,
3364: "Loop unrolling: Final value not constant.\n");
3365: return 0;
3366: }
3367:
3368: /* ?? Final value and initial value do not have to be constants.
3369: Only their difference has to be constant. When the iteration variable
3370: is an array address, the final value and initial value might both
3371: be addresses with the same base but different constant offsets.
3372: Final value must be invariant for this to work.
3373:
1.1.1.3 root 3374: To do this, need some way to find the values of registers which are
1.1 root 3375: invariant. */
3376:
3377: /* Final_larger is 1 if final larger, 0 if they are equal, otherwise -1. */
3378: if (unsigned_compare)
3379: final_larger
1.1.1.4 root 3380: = ((unsigned HOST_WIDE_INT) INTVAL (final_value)
3381: > (unsigned HOST_WIDE_INT) INTVAL (initial_value))
3382: - ((unsigned HOST_WIDE_INT) INTVAL (final_value)
3383: < (unsigned HOST_WIDE_INT) INTVAL (initial_value));
1.1 root 3384: else
1.1.1.4 root 3385: final_larger = (INTVAL (final_value) > INTVAL (initial_value))
3386: - (INTVAL (final_value) < INTVAL (initial_value));
1.1 root 3387:
3388: if (INTVAL (increment) > 0)
3389: increment_dir = 1;
3390: else if (INTVAL (increment) == 0)
3391: increment_dir = 0;
3392: else
3393: increment_dir = -1;
3394:
3395: /* There are 27 different cases: compare_dir = -1, 0, 1;
3396: final_larger = -1, 0, 1; increment_dir = -1, 0, 1.
3397: There are 4 normal cases, 4 reverse cases (where the iteration variable
3398: will overflow before the loop exits), 4 infinite loop cases, and 15
3399: immediate exit (0 or 1 iteration depending on loop type) cases.
3400: Only try to optimize the normal cases. */
3401:
3402: /* (compare_dir/final_larger/increment_dir)
3403: Normal cases: (0/-1/-1), (0/1/1), (-1/-1/-1), (1/1/1)
3404: Reverse cases: (0/-1/1), (0/1/-1), (-1/-1/1), (1/1/-1)
3405: Infinite loops: (0/-1/0), (0/1/0), (-1/-1/0), (1/1/0)
3406: Immediate exit: (0/0/X), (-1/0/X), (-1/1/X), (1/0/X), (1/-1/X) */
3407:
3408: /* ?? If the meaning of reverse loops (where the iteration variable
3409: will overflow before the loop exits) is undefined, then could
3410: eliminate all of these special checks, and just always assume
3411: the loops are normal/immediate/infinite. Note that this means
3412: the sign of increment_dir does not have to be known. Also,
3413: since it does not really hurt if immediate exit loops or infinite loops
3414: are optimized, then that case could be ignored also, and hence all
3415: loops can be optimized.
3416:
3417: According to ANSI Spec, the reverse loop case result is undefined,
3418: because the action on overflow is undefined.
3419:
3420: See also the special test for NE loops below. */
3421:
3422: if (final_larger == increment_dir && final_larger != 0
3423: && (final_larger == compare_dir || compare_dir == 0))
3424: /* Normal case. */
3425: ;
3426: else
3427: {
3428: if (loop_dump_stream)
3429: fprintf (loop_dump_stream,
3430: "Loop unrolling: Not normal loop.\n");
3431: return 0;
3432: }
3433:
3434: /* Calculate the number of iterations, final_value is only an approximation,
3435: so correct for that. Note that tempu and loop_n_iterations are
3436: unsigned, because they can be as large as 2^n - 1. */
3437:
3438: i = INTVAL (increment);
3439: if (i > 0)
3440: tempu = INTVAL (final_value) - INTVAL (initial_value);
3441: else if (i < 0)
3442: {
3443: tempu = INTVAL (initial_value) - INTVAL (final_value);
3444: i = -i;
3445: }
3446: else
3447: abort ();
3448:
3449: /* For NE tests, make sure that the iteration variable won't miss the
3450: final value. If tempu mod i is not zero, then the iteration variable
3451: will overflow before the loop exits, and we can not calculate the
3452: number of iterations. */
3453: if (compare_dir == 0 && (tempu % i) != 0)
3454: return 0;
3455:
3456: return tempu / i + ((tempu % i) != 0);
3457: }
1.1.1.7 root 3458:
1.1.1.8 root 3459: /* Replace uses of split bivs with their split pseudo register. This is
1.1.1.7 root 3460: for original instructions which remain after loop unrolling without
3461: copying. */
3462:
3463: static rtx
3464: remap_split_bivs (x)
3465: rtx x;
3466: {
3467: register enum rtx_code code;
3468: register int i;
3469: register char *fmt;
3470:
3471: if (x == 0)
3472: return x;
3473:
3474: code = GET_CODE (x);
3475: switch (code)
3476: {
3477: case SCRATCH:
3478: case PC:
3479: case CC0:
3480: case CONST_INT:
3481: case CONST_DOUBLE:
3482: case CONST:
3483: case SYMBOL_REF:
3484: case LABEL_REF:
3485: return x;
3486:
3487: case REG:
3488: #if 0
3489: /* If non-reduced/final-value givs were split, then this would also
3490: have to remap those givs also. */
3491: #endif
3492: if (REGNO (x) < max_reg_before_loop
3493: && reg_iv_type[REGNO (x)] == BASIC_INDUCT)
3494: return reg_biv_class[REGNO (x)]->biv->src_reg;
3495: }
3496:
3497: fmt = GET_RTX_FORMAT (code);
3498: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3499: {
3500: if (fmt[i] == 'e')
3501: XEXP (x, i) = remap_split_bivs (XEXP (x, i));
3502: if (fmt[i] == 'E')
3503: {
3504: register int j;
3505: for (j = 0; j < XVECLEN (x, i); j++)
3506: XVECEXP (x, i, j) = remap_split_bivs (XVECEXP (x, i, j));
3507: }
3508: }
3509: return x;
3510: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.