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