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