Return to unroll.c CVS log

Up to [GCC 2.x] / gcc

Annotation of gcc/unroll.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.