Return to loop.c CVS log

Up to [Research Unix] / researchv10dc / cmd / gcc

Annotation of researchv10dc/cmd/gcc/loop.c, revision 1.1

1.1     ! root        1: /* Move constant computations out of loops.
        !             2:    Copyright (C) 1987, 1988 Free Software Foundation, Inc.
        !             3: 
        !             4: This file is part of GNU CC.
        !             5: 
        !             6: GNU CC is distributed in the hope that it will be useful,
        !             7: but WITHOUT ANY WARRANTY.  No author or distributor
        !             8: accepts responsibility to anyone for the consequences of using it
        !             9: or for whether it serves any particular purpose or works at all,
        !            10: unless he says so in writing.  Refer to the GNU CC General Public
        !            11: License for full details.
        !            12: 
        !            13: Everyone is granted permission to copy, modify and redistribute
        !            14: GNU CC, but only under the conditions described in the
        !            15: GNU CC General Public License.   A copy of this license is
        !            16: supposed to have been given to you along with GNU CC so you
        !            17: can know your rights and responsibilities.  It should be in a
        !            18: file named COPYING.  Among other things, the copyright notice
        !            19: and this notice must be preserved on all copies.  */
        !            20: 
        !            21: 
        !            22: /* This is the loop optimization pass of the compiler.
        !            23:    It finds invariant computations within loops and moves them
        !            24:    to the beginning of the loop.
        !            25: 
        !            26:    It also finds cases where
        !            27:    a register is set within the loop by zero-extending a narrower value
        !            28:    and changes these to zero the entire register once before the loop
        !            29:    and merely copy the low part within the loop.
        !            30: 
        !            31:    Most of the complexity is in heuristics to decide when it is worth
        !            32:    while to do these things.  */
        !            33: 
        !            34: /* ??? verify_loop would run faster if we made one table
        !            35:    of the minimum and maximum luids from which each label is reached.
        !            36:    Also, it would be faster if loop_store_addrs were a hash table.  */
        !            37: 
        !            38: #include "config.h"
        !            39: #include "rtl.h"
        !            40: #include "insn-config.h"
        !            41: #include "regs.h"
        !            42: #include "recog.h"
        !            43: #include <stdio.h>
        !            44: 
        !            45: /* Vector mapping INSN_UIDs to luids.
        !            46:    The luids are like uids but increase monononically always.
        !            47:    We use them to see whether a jump comes from outside a given loop.  */
        !            48: 
        !            49: static short *uid_luid;
        !            50: 
        !            51: /* Get the luid of an insn.  */
        !            52: 
        !            53: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)])
        !            54: 
        !            55: /* 1 + largest uid of any insn.  */
        !            56: 
        !            57: static int max_uid;
        !            58: 
        !            59: /* 1 + luid of last insn.  */
        !            60: 
        !            61: static int max_luid;
        !            62: 
        !            63: /* Nonzero if somewhere in the current loop
        !            64:    there is either a subroutine call,
        !            65:    or a store into a memory address that is not fixed,
        !            66:    or a store in a BLKmode memory operand,
        !            67:    or too many different fixed addresses stored in
        !            68:    to record them all in `loop_store_addrs'.
        !            69: 
        !            70:    In any of these cases, no memory location can be regarded
        !            71:    as invariant.  */
        !            72: 
        !            73: static int unknown_address_altered;
        !            74: 
        !            75: /* Nonzero if somewhere in the current loop there is a store
        !            76:    into a memory address that is not fixed but is known to be
        !            77:    part of an aggregate.
        !            78: 
        !            79:    In this case, no memory reference in an aggregate may be
        !            80:    considered invariant.  */
        !            81: 
        !            82: static int unknown_aggregate_altered;
        !            83: 
        !            84: /* Nonzero if somewhere in the current loop there is a store
        !            85:    into a memory address other than a fixed address not in an aggregate.
        !            86: 
        !            87:    In this case, no memory reference in an aggregate at a varying address
        !            88:    may be considered invariant.  */
        !            89: 
        !            90: static int fixed_aggregate_altered;
        !            91: 
        !            92: /* Nonzero if there is a subroutine call in the current loop.
        !            93:    (unknown_address_altered is also nonzero in this case.)  */
        !            94: 
        !            95: static int loop_has_call;
        !            96: 
        !            97: /* Array of fixed memory addresses that are stored in this loop.
        !            98:    If there are too many to fit here,
        !            99:    we just turn on unknown_address_altered.  */
        !           100: 
        !           101: #define NUM_STORES 10
        !           102: static rtx loop_store_addrs[NUM_STORES];
        !           103: static int loop_store_widths[NUM_STORES];
        !           104: 
        !           105: /* Index of first available slot in above array.  */
        !           106: static int loop_store_addrs_idx;
        !           107: 
        !           108: /* During the analysis of a loop, a chain of `struct movable's
        !           109:    is made to record all the movable insns found.
        !           110:    Then the entire chain can be scanned to decide which to move.  */
        !           111: 
        !           112: struct movable
        !           113: {
        !           114:   rtx insn;                    /* A movable insn */
        !           115:   int consec;                  /* Number of consecutive following insns 
        !           116:                                   that must be moved with this one.  */
        !           117:   int regno;                   /* The register it sets */
        !           118:   short lifetime;              /* lifetime of that register;
        !           119:                                   may be adjusted when matching movables
        !           120:                                   that load the same value are found.  */
        !           121:   short times_used;            /* Number of times the register is used,
        !           122:                                   plus uses of related insns that could
        !           123:                                   be moved if this one is.  */
        !           124:   unsigned int cond : 1;       /* 1 if only conditionally movable */
        !           125:   unsigned int force : 1;      /* 1 means MUST move this insn */
        !           126:   unsigned int global : 1;     /* 1 means reg is live outside this loop */
        !           127:   unsigned int done : 1;       /* 1 inhibits further processing of this */
        !           128:   unsigned int partial : 1;    /* Moving this doesn't make it invariant.  */
        !           129:   struct movable *match;       /* First entry for same value */
        !           130:   struct movable *forces;      /* An insn that must be moved if this is */
        !           131:   struct movable *next;
        !           132: };
        !           133: 
        !           134: static FILE *loop_dump_stream;
        !           135: 
        !           136: static rtx verify_loop ();
        !           137: static int invariant_p ();
        !           138: static int can_jump_into_range_p ();
        !           139: static void count_loop_regs_set ();
        !           140: static void note_addr_stored ();
        !           141: static int loop_reg_used_before_p ();
        !           142: static void constant_high_bytes ();
        !           143: static void scan_loop ();
        !           144: static rtx replace_regs ();
        !           145: static void move_movables ();
        !           146: static int may_trap_p ();
        !           147: 
        !           148: /* Entry point of this file.  Perform loop optimization
        !           149:    on the current function.  F is the first insn of the function
        !           150:    and NREGS is the number of register numbers used.  */
        !           151: 
        !           152: void
        !           153: loop_optimize (f, nregs, dumpfile)
        !           154:      /* f is the first instruction of a chain of insns for one function */
        !           155:      rtx f;
        !           156:      /* nregs is the total number of registers used in it */
        !           157:      int nregs;
        !           158:      FILE *dumpfile;
        !           159: {
        !           160:   register rtx insn;
        !           161:   register int i;
        !           162:   rtx end;
        !           163:   rtx last_insn;
        !           164: 
        !           165:   loop_dump_stream = dumpfile;
        !           166: 
        !           167:   init_recog ();
        !           168: 
        !           169:   /* First find the last real insn, and count the number of insns,
        !           170:      and assign insns their suids.  */
        !           171: 
        !           172:   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           173:     if (INSN_UID (insn) > i)
        !           174:       i = INSN_UID (insn);
        !           175: 
        !           176:   max_uid = i + 1;
        !           177:   uid_luid = (short *) alloca ((i + 1) * sizeof (short));
        !           178:   bzero (uid_luid, (i + 1) * sizeof (short));
        !           179: 
        !           180:   /* Compute the mapping from uids to luids.
        !           181:      LUIDs are numbers assigned to insns, like uids,
        !           182:      except that luids increase monotonically through the code.  */
        !           183: 
        !           184:   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           185:     {
        !           186:       last_insn = insn;
        !           187:       INSN_LUID (insn) = ++i;
        !           188:     }
        !           189: 
        !           190:   max_luid = i;
        !           191: 
        !           192:   /* Don't leave gaps in uid_luid for insns that have been
        !           193:      deleted.  It is possible that the first or last insn
        !           194:      using some register has been deleted by cross-jumping.
        !           195:      Make sure that uid_luid for that former insn's uid
        !           196:      points to the general area where that insn used to be.  */
        !           197:   for (i = 0; i < max_uid; i++)
        !           198:     {
        !           199:       uid_luid[0] = uid_luid[i];
        !           200:       if (uid_luid[0] != 0)
        !           201:        break;
        !           202:     }
        !           203:   for (i = 0; i < max_uid; i++)
        !           204:     if (uid_luid[i] == 0)
        !           205:       uid_luid[i] = uid_luid[i - 1];
        !           206: 
        !           207:   /* Find and process each loop.
        !           208:      We scan from the end, and process each loop when its start is seen,
        !           209:      so we process innermost loops first.  */
        !           210: 
        !           211:   for (insn = last_insn; insn; insn = PREV_INSN (insn))
        !           212:     if (GET_CODE (insn) == NOTE
        !           213:        && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
        !           214:        /* Make sure it really is a loop -- no jumps in from outside.  */
        !           215:        && (end = verify_loop (f, insn)))
        !           216:       scan_loop (insn, end, nregs);
        !           217: }
        !           218: 
        !           219: /* Optimize one loop whose start is LOOP_START and end is END.
        !           220:    LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
        !           221:    NOTE_INSN_LOOP_END.  */
        !           222: 
        !           223: static void
        !           224: scan_loop (loop_start, end, nregs)
        !           225:      rtx loop_start, end;
        !           226:      int nregs;
        !           227: {
        !           228:   register int i;
        !           229:   register rtx p = NEXT_INSN (loop_start);
        !           230:   /* 1 if we are scanning insns that could be executed zero times.  */
        !           231:   int maybe_never = 0;
        !           232:   /* 1 if we are scanning insns that might never be executed
        !           233:      due to a subroutine call which might exit before they are reached.  */
        !           234:   int call_passed = 0;
        !           235:   /* For a rotated loop that is entered near the bottom,
        !           236:      this is the label at the top.  Otherwise it is zero.  */
        !           237:   rtx loop_top = 0;
        !           238:   /* This is the insn (whatever kind) before the NOTE that starts the loop.
        !           239:      Any insns moved out of the loop will follow it.  */
        !           240:   rtx before_start = PREV_INSN (loop_start);
        !           241:   /* Jump insn that enters the loop, or 0 if control drops in.  */
        !           242:   rtx loop_entry_jump = 0;
        !           243:   /* Place in the loop where control enters.  */
        !           244:   rtx scan_start;
        !           245:   /* Number of insns in the loop.  */
        !           246:   int insn_count;
        !           247:   int tem;
        !           248:   /* Indexed by register number, contains the number of times the reg
        !           249:      is set during the loop being scanned, or -1 if the insns that set it
        !           250:      have all been scanned as candidates for being moved out of the loop.
        !           251:      0 indicates an invariant register; -1 a conditionally invariant one.  */
        !           252:   short *n_times_set;
        !           253:   /* Indexed by register number, contains the number of times the reg
        !           254:      was used during the loop being scanned, not counting changes due
        !           255:      to moving these insns out of the loop.  */
        !           256:   short *n_times_used;
        !           257:   /* Indexed by register number, contains 1 for a register whose
        !           258:      assignments may not be moved out of the loop.  */
        !           259:   char *may_not_move;
        !           260:   /* Chain describing insns movable in current loop.  */
        !           261:   struct movable *movables = 0;
        !           262:   /* Last element in `movables' -- so we can add elements at the end.  */
        !           263:   struct movable *last_movable = 0;
        !           264:   /* Ratio of extra register life span we can justify
        !           265:      for saving an instruction.  More if loop doesn't call subroutines
        !           266:      since in that case saving an insn makes more difference
        !           267:      and more registers are available.  */
        !           268:   int threshold = loop_has_call ? 17 : 34;
        !           269: 
        !           270:   n_times_set = (short *) alloca (nregs * sizeof (short));
        !           271:   n_times_used = (short *) alloca (nregs * sizeof (short));
        !           272:   may_not_move = (char *) alloca (nregs);
        !           273: 
        !           274:   /* Determine whether this loop starts with a jump down
        !           275:      to a test at the end.  */
        !           276:   while (p != end
        !           277:         && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN)
        !           278:     p = NEXT_INSN (p);
        !           279: 
        !           280:   /* "Loop" contains neither jumps nor labels;
        !           281:      it must have been a dummy.  Think no more about it.  */
        !           282:   if (p == end)
        !           283:     return;
        !           284: 
        !           285:   scan_start = p;
        !           286: 
        !           287:   /* If loop has a jump before the first label,
        !           288:      the true entry is the target of that jump.
        !           289:      Start scan from there.
        !           290:      But record in LOOP_TOP the place where the end-test jumps
        !           291:      back to so we can scan that after the end of the loop.  */
        !           292:   if (GET_CODE (p) == JUMP_INSN)
        !           293:     {
        !           294:       loop_entry_jump = p;
        !           295:       loop_top = NEXT_INSN (p);
        !           296:       /* Loop entry will never be a conditional jump.
        !           297:         If we see one, this must not be a real loop.  */
        !           298:       if (GET_CODE (loop_top) != BARRIER)
        !           299:        return;
        !           300:       p = JUMP_LABEL (p);
        !           301:       /* Check to see whether the jump actually
        !           302:         jumps out of the loop (meaning it's no loop).
        !           303:         This case can happen for things like
        !           304:         do {..} while (0).  */
        !           305:       if (p == 0
        !           306:          || INSN_LUID (p) < INSN_LUID (loop_start)
        !           307:          || INSN_LUID (p) >= INSN_LUID (end))
        !           308:        {
        !           309:          if (loop_dump_stream)
        !           310:            fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
        !           311:                     INSN_UID (loop_start), INSN_UID (end));
        !           312:          return;
        !           313:        }
        !           314: 
        !           315:       /* Find the first label after the entry-jump.  */
        !           316:       while (GET_CODE (loop_top) != CODE_LABEL)
        !           317:        {
        !           318:          loop_top = NEXT_INSN (loop_top);
        !           319:          if (loop_top == 0)
        !           320:            abort ();
        !           321:        }
        !           322: 
        !           323:       /* Maybe rearrange the loop to drop straight in
        !           324:         with a new test to jump around it entirely.
        !           325:         (The latter is considered outside the loop.)
        !           326:         If this is done, we no longer enter with a jump.  */
        !           327:       if (loop_skip_over (loop_start, end, loop_entry_jump))
        !           328:        loop_top = 0;
        !           329:       else
        !           330:        /* We really do enter with a jump;
        !           331:           scan the loop from the place where the jump jumps to.  */
        !           332:        scan_start = p;
        !           333:     }
        !           334: 
        !           335:   /* Count number of times each reg is set during this loop.
        !           336:      Set MAY_NOT_MOVE[I] if it is not safe to move out
        !           337:      the setting of register I.  */
        !           338: 
        !           339:   bzero (n_times_set, nregs * sizeof (short));
        !           340:   bzero (may_not_move, nregs);
        !           341:   count_loop_regs_set (loop_top ? loop_top : loop_start, end,
        !           342:                       n_times_set, may_not_move, 
        !           343:                       &insn_count, nregs);
        !           344:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           345:     may_not_move[i] = 1, n_times_set[i] = 1;
        !           346:   bcopy (n_times_set, n_times_used, nregs * sizeof (short));
        !           347: 
        !           348:   if (loop_dump_stream)
        !           349:     fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns\n\n",
        !           350:             INSN_UID (loop_start), INSN_UID (end), insn_count);
        !           351: 
        !           352:   /* Scan through the loop finding insns that are safe to move.
        !           353:      In each such insn, store QImode as the mode, to mark it.
        !           354:      Then set n_times_set to -1 for the reg being set, so that
        !           355:      this reg will be considered invariant for subsequent insns.
        !           356:      We consider whether subsequent insns use the reg
        !           357:      in deciding whether it is worth actually moving.
        !           358: 
        !           359:      MAYBE_NEVER is nonzero if we have passed a conditional jump insn
        !           360:      and therefore it is possible that the insns we are scanning
        !           361:      would never be executed.  At such times, we must make sure
        !           362:      that it is safe to execute the insn once instead of zero times.
        !           363:      When MAYBE_NEVER is 0, all insns will be executed at least once
        !           364:      so that is not a problem.  */
        !           365: 
        !           366:   p = scan_start;
        !           367:   while (1)
        !           368:     {
        !           369:       p = NEXT_INSN (p);
        !           370:       /* At end of a straight-in loop, we are done.
        !           371:         At end of a loop entered at the bottom, scan the top.  */
        !           372:       if (p == scan_start)
        !           373:        break;
        !           374:       if (p == end)
        !           375:        {
        !           376:          if (loop_top != 0)
        !           377:            p = NEXT_INSN (loop_top);
        !           378:          else
        !           379:            break;
        !           380:          if (p == scan_start)
        !           381:            break;
        !           382:        }
        !           383:       if (GET_CODE (p) == INSN
        !           384:          && GET_CODE (PATTERN (p)) == SET
        !           385:          && GET_CODE (SET_DEST (PATTERN (p))) == REG
        !           386:          && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))])
        !           387:        {
        !           388:          /* If this register is used or set outside the loop,
        !           389:             then we can move it only if we know this insn is
        !           390:             executed exactly once per iteration,
        !           391:             and we can check all the insns executed before it
        !           392:             to make sure none of them used the value that
        !           393:             was lying around at entry to the loop.  */
        !           394:          if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end)
        !           395:               || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start))
        !           396:              && (maybe_never
        !           397:                  || loop_reg_used_before_p (p, loop_start, scan_start, end)))
        !           398:            ;
        !           399:          else if ((tem = invariant_p (SET_SRC (PATTERN (p)), n_times_set))
        !           400:                   && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1
        !           401:                       || consec_sets_invariant_p (SET_DEST (PATTERN (p)),
        !           402:                                                   p, n_times_set))
        !           403:                   /* If the insn can cause a trap (such as divide by zero),
        !           404:                      can't move it unless it's guaranteed to be executed
        !           405:                      once loop is entered.  Even a function call might
        !           406:                      prevent the trap insn from being reached
        !           407:                      (since it might exit!)  */
        !           408:                   && ! ((maybe_never || call_passed)
        !           409:                         && may_trap_p (SET_SRC (PATTERN (p)))))
        !           410:            {
        !           411:              register struct movable *m;
        !           412:              register int regno = REGNO (SET_DEST (PATTERN (p)));
        !           413:              int count;
        !           414:              m = (struct movable *) alloca (sizeof (struct movable));
        !           415:              m->next = 0;
        !           416:              m->insn = p;
        !           417:              m->force = 0;
        !           418:              m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1;
        !           419:              m->done = 0;
        !           420:              m->forces = 0;
        !           421:              m->partial = 0;
        !           422:              m->regno = regno;
        !           423:              m->cond = (tem > 1);
        !           424:              m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
        !           425:                           || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
        !           426:              m->match = 0;
        !           427:              m->lifetime = (uid_luid[regno_last_uid[regno]]
        !           428:                             - uid_luid[regno_first_uid[regno]]);
        !           429:              m->times_used = n_times_used[regno];
        !           430:              n_times_set[regno] = -1;
        !           431:              /* Add M to the end of the chain MOVABLES.  */
        !           432:              if (movables == 0)
        !           433:                movables = m;
        !           434:              else
        !           435:                last_movable->next = m;
        !           436:              last_movable = m;
        !           437:              /* Skip the consecutive insns, if there are any.  */
        !           438:              for (count = m->consec - 1; count >= 0; count--)
        !           439:                {
        !           440:                  do p = NEXT_INSN (p);
        !           441:                  while (GET_CODE (p) == NOTE);
        !           442:                }
        !           443:            }
        !           444:          /* If this register is always set within a STRICT_LOW_PART
        !           445:             or set to zero, then its high bytes are constant.
        !           446:             So clear them outside the loop and within the loop
        !           447:             just load the low bytes.
        !           448:             We must check that the machine has an instruction to do so.
        !           449:             Also, if the value loaded into the register
        !           450:             depends on the same register, this cannot be done.  */
        !           451:          else if (SET_SRC (PATTERN (p)) == const0_rtx
        !           452:                   && GET_CODE (NEXT_INSN (p)) == INSN
        !           453:                   && GET_CODE (PATTERN (NEXT_INSN (p))) == SET
        !           454:                   && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p))))
        !           455:                       == STRICT_LOW_PART)
        !           456:                   && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
        !           457:                       == SUBREG)
        !           458:                   && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
        !           459:                       == SET_DEST (PATTERN (p)))
        !           460:                   && !reg_mentioned_p (SET_DEST (PATTERN (p)),
        !           461:                                        SET_SRC (PATTERN (NEXT_INSN (p)))))
        !           462:            {
        !           463:              register int regno = REGNO (SET_DEST (PATTERN (p)));
        !           464:              if (n_times_set[regno] == 2)
        !           465:                {
        !           466:                  register struct movable *m;
        !           467:                  int count;
        !           468:                  m = (struct movable *) alloca (sizeof (struct movable));
        !           469:                  m->next = 0;
        !           470:                  m->insn = p;
        !           471:                  m->force = 0;
        !           472:                  m->consec = 0;
        !           473:                  m->done = 0;
        !           474:                  m->forces = 0;
        !           475:                  m->partial = 1;
        !           476:                  m->regno = regno;
        !           477:                  m->cond = 0;
        !           478:                  /* Say "global" so this register is not combined
        !           479:                     with any other.  In fact, it is sometimes possible
        !           480:                     to combine two of these registers, but the criteria
        !           481:                     are special and have not been programmed in.  */
        !           482:                  m->global = 1;
        !           483:                  m->match = 0;
        !           484:                  m->lifetime = (uid_luid[regno_last_uid[regno]]
        !           485:                                 - uid_luid[regno_first_uid[regno]]);
        !           486:                  m->times_used = n_times_used[regno];
        !           487:                  n_times_set[regno] = -1;
        !           488:                  /* Add M to the end of the chain MOVABLES.  */
        !           489:                  if (movables == 0)
        !           490:                    movables = m;
        !           491:                  else
        !           492:                    last_movable->next = m;
        !           493:                  last_movable = m;
        !           494:                  /* Skip the consecutive insns, if there are any.  */
        !           495:                  for (count = m->consec - 1; count >= 0; count--)
        !           496:                    {
        !           497:                      do p = NEXT_INSN (p);
        !           498:                      while (GET_CODE (p) == NOTE);
        !           499:                    }
        !           500:                }
        !           501:            }
        !           502:        }
        !           503:       /* Past a call insn, we get to insns which might not be executed
        !           504:         because the call might exit.  This matters for insns that trap.  */
        !           505:       else if (GET_CODE (p) == CALL_INSN)
        !           506:        call_passed = 1;
        !           507:       /* Past a label or a jump, we get to insns for which we
        !           508:         can't count on whether or how many times they will be
        !           509:         executed during each iteration.  Therefore, we can
        !           510:         only move out sets of trivial variables
        !           511:         (those not used after the loop).  */
        !           512:       else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
        !           513:        maybe_never = 1;
        !           514:     }
        !           515: 
        !           516:   /* For each movable insn, see if the reg that it loads
        !           517:      leads when it dies right into another conditionally movable insn.
        !           518:      If so, record that the second insn "forces" the first one,
        !           519:      since the second can be moved only if the first is.  */
        !           520: 
        !           521:   {
        !           522:     register struct movable *m, *m1;
        !           523:     for (m1 = movables; m1; m1 = m1->next)
        !           524:       {
        !           525:        int regno = m1->regno;
        !           526:        for (m = m1->next; m; m = m->next)
        !           527:          if (INSN_UID (m->insn) == regno_last_uid[regno])
        !           528:            break;
        !           529:        if (m != 0 && SET_SRC (PATTERN (m->insn)) == SET_DEST (PATTERN (m1->insn)))
        !           530:          m = 0;
        !           531: 
        !           532:        /* Increase the priority of the moving the first insn
        !           533:           since it permits the second to be moved as well.  */
        !           534:        if (m != 0)
        !           535:          {
        !           536:            m->forces = m1;
        !           537:            m1->lifetime += m->lifetime;
        !           538:            m1->times_used += m1->times_used;
        !           539:          }
        !           540:       }
        !           541:   }
        !           542: 
        !           543:   /* See if there are multiple movable insns that load the same value.
        !           544:      If there are, make all but the first point at the first one
        !           545:      through the `match' field, and add the priorities of them
        !           546:      all together as the priority of the first.  */
        !           547: 
        !           548:   {
        !           549:     register struct movable *m;
        !           550:     char *matched_regs = (char *) alloca (nregs);
        !           551: 
        !           552:     /* Regs that are used more than once are not allowed to match
        !           553:        or be matched.  I'm no longer sure why not.  */
        !           554: 
        !           555:     for (m = movables; m; m = m->next)
        !           556:       if (m->match == 0 && n_times_used[m->regno] == 1)
        !           557:        {
        !           558:          register struct movable *m1;
        !           559:          int regno = m->regno;
        !           560: 
        !           561:          bzero (matched_regs, nregs);
        !           562:          matched_regs[regno] = 1;
        !           563: 
        !           564:          for (m1 = m->next; m1; m1 = m1->next)
        !           565:            if (m1->match == 0 && n_times_used[m1->regno] == 1
        !           566:                /* A reg used outside the loop mustn't be eliminated.  */
        !           567:                && !m1->global
        !           568:                && (matched_regs[m1->regno]
        !           569:                    ||
        !           570:                    (
        !           571:                     /* Can't combine regs with different modes
        !           572:                        even if loaded from the same constant.  */
        !           573:                     (GET_MODE (SET_DEST (PATTERN (m->insn)))
        !           574:                      == GET_MODE (SET_DEST (PATTERN (m1->insn))))
        !           575:                     /* See if the source of M1 says it matches M.  */
        !           576:                     && ((GET_CODE (SET_SRC (PATTERN (m1->insn))) == REG
        !           577:                          && matched_regs[REGNO (SET_SRC (PATTERN (m1->insn)))])
        !           578:                         || rtx_equal_p (SET_SRC (PATTERN (m->insn)),
        !           579:                                         SET_SRC (PATTERN (m1->insn)))
        !           580:                         || (REG_NOTES (m->insn) && REG_NOTES (m1->insn)
        !           581:                             && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV
        !           582:                             && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV
        !           583:                             && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0),
        !           584:                                             XEXP (REG_NOTES (m1->insn), 0)))))))
        !           585:              {
        !           586:                m->lifetime += m1->lifetime;
        !           587:                m->times_used += m1->times_used;
        !           588:                m1->match = m;
        !           589:                matched_regs[m1->regno] = 1;
        !           590:              }
        !           591:        }
        !           592:   }
        !           593:        
        !           594:   /* Now consider each movable insn to decide whether it is worth moving.  */
        !           595: 
        !           596:   move_movables (movables, n_times_set, n_times_used, threshold,
        !           597:                 insn_count, loop_start, end, nregs);
        !           598: }
        !           599: 
        !           600: /* Scan MOVABLES, and move the insns that deserve to be moved.
        !           601:    If two matching movables are combined, replace one reg with the
        !           602:    other throughout.  */
        !           603: 
        !           604: static void
        !           605: move_movables (movables, n_times_set, n_times_used, threshold,
        !           606:               insn_count, loop_start, end, nregs)
        !           607:      struct movable *movables;
        !           608:      short *n_times_set;
        !           609:      short *n_times_used;
        !           610:      int threshold;
        !           611:      int insn_count;
        !           612:      rtx loop_start;
        !           613:      rtx end;
        !           614:      int nregs;
        !           615: {
        !           616:   rtx new_start = 0;
        !           617:   register struct movable *m;
        !           618:   register rtx p;
        !           619:   /* Map of pseudo-register replacements to handle combining
        !           620:      when we move several insns that load the same value
        !           621:      into different pseudo-registers.  */
        !           622:   rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
        !           623:   char *already_moved = (char *) alloca (nregs);
        !           624: 
        !           625:   bzero (already_moved, nregs);
        !           626:   bzero (reg_map, nregs * sizeof (rtx));
        !           627: 
        !           628:   for (m = movables; m; m = m->next)
        !           629:     {
        !           630:       /* Describe this movable insn.  */
        !           631: 
        !           632:       if (loop_dump_stream)
        !           633:        {
        !           634:          fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
        !           635:                   INSN_UID (m->insn), m->regno, m->lifetime);
        !           636:          if (m->consec > 0)
        !           637:            fprintf (loop_dump_stream, "consec %d, ", m->consec);
        !           638:          if (m->cond)
        !           639:            fprintf (loop_dump_stream, "cond ");
        !           640:          if (m->force)
        !           641:            fprintf (loop_dump_stream, "force ");
        !           642:          if (m->global)
        !           643:            fprintf (loop_dump_stream, "global ");
        !           644:          if (m->done)
        !           645:            fprintf (loop_dump_stream, "done ");
        !           646:          if (m->match)
        !           647:            fprintf (loop_dump_stream, "matches %d ",
        !           648:                     INSN_UID (m->match->insn));
        !           649:          if (m->forces)
        !           650:            fprintf (loop_dump_stream, "forces %d ",
        !           651:                     INSN_UID (m->forces->insn));
        !           652:        }
        !           653: 
        !           654:       /* Ignore the insn if it's already done (it matched something else).
        !           655:         Otherwise, see if it is now safe to move.  */
        !           656: 
        !           657:       if (!m->done
        !           658:          && (! m->cond
        !           659:              || 1 == invariant_p (SET_SRC (PATTERN (m->insn)), n_times_set))
        !           660:          && (! m->forces || m->forces->done))
        !           661:        {
        !           662:          register int regno;
        !           663:          register rtx p;
        !           664:          int times_used = m->times_used + m->consec;
        !           665: 
        !           666:          /* We have an insn that is safe to move.
        !           667:             Compute its desirability.  */
        !           668: 
        !           669:          p = m->insn;
        !           670:          regno = m->regno;
        !           671: 
        !           672:          if (loop_dump_stream)
        !           673:            fprintf (loop_dump_stream, "reg uses %d ", times_used);
        !           674: 
        !           675:          /* An insn MUST be moved if we already moved something else
        !           676:             which is safe only if this one is moved too: that is,
        !           677:             if already_moved[REGNO] is nonzero.  */
        !           678: 
        !           679:          /* An insn is desirable to move if the new lifetime of the
        !           680:             register is no more than THRESHOLD times the old lifetime.
        !           681:             If it's not desirable, it means the loop is so big
        !           682:             that moving won't speed things up much,
        !           683:             and it is liable to make register usage worse.  */
        !           684: 
        !           685:          /* It is also desirable to move if it can be moved at no
        !           686:             extra cost because something else was already moved.  */
        !           687: 
        !           688:          if (already_moved[regno]
        !           689:              || (threshold * times_used * m->lifetime) >= insn_count
        !           690:              || (m->forces && m->forces->done
        !           691:                  && n_times_used[m->forces->regno] == 1))
        !           692:            {
        !           693:              int count;
        !           694:              register struct movable *m1;
        !           695: 
        !           696:              for (count = m->consec; count >= 0; count--)
        !           697:                {
        !           698:                  rtx i1 = emit_insn_before (PATTERN (p), loop_start);
        !           699:                  if (new_start == 0)
        !           700:                    new_start = i1;
        !           701: 
        !           702:                  if (loop_dump_stream)
        !           703:                    fprintf (loop_dump_stream, "moved to %d", INSN_UID (i1));
        !           704: 
        !           705:                  /* Mark the moved, invariant reg as being equivalent to
        !           706:                     its constant value.  */
        !           707:                  REG_NOTES (i1) = REG_NOTES (p);
        !           708:                  if (REG_NOTES (i1) == 0
        !           709:                      && ! m->partial /* But not if its a zero-extend clr. */
        !           710:                      && ! m->global /* and not if used outside the loop
        !           711:                                        (since it might get set outside).  */
        !           712:                      && CONSTANT_P (SET_SRC (PATTERN (p))))
        !           713:                    REG_NOTES (i1)
        !           714:                      = gen_rtx (EXPR_LIST, REG_EQUIV,
        !           715:                                 SET_SRC (PATTERN (p)), REG_NOTES (i1));
        !           716:                  delete_insn (p);
        !           717:                  do p = NEXT_INSN (p);
        !           718:                  while (GET_CODE (p) == NOTE);
        !           719: 
        !           720:                  /* The more insns we move, the less we like moving them.  */
        !           721:                  threshold -= 2;
        !           722:                }
        !           723: 
        !           724:              /* Any other movable that loads the same register
        !           725:                 MUST be moved.  */
        !           726:              already_moved[regno] = 1;
        !           727: 
        !           728:              /* The reg set here is now invariant.  */
        !           729:              if (! m->partial)
        !           730:                n_times_set[regno] = 0;
        !           731: 
        !           732:              m->done = 1;
        !           733: 
        !           734:              /* Combine with this moved insn any other matching movables.  */
        !           735: 
        !           736:              for (m1 = m->next; m1; m1 = m1->next)
        !           737:                if (m1->match == m)
        !           738:                  {
        !           739:                    /* Schedule the reg loaded by M1
        !           740:                       for replacement so that shares the reg of M.  */
        !           741:                    reg_map[m1->regno] = SET_DEST (PATTERN (m->insn));
        !           742:                    /* Get rid of the matching insn
        !           743:                       and prevent further processing of it.  */
        !           744:                    m1->done = 1;
        !           745:                    delete_insn (m1->insn);
        !           746: 
        !           747:                    /* Any other movable that loads the same register
        !           748:                       MUST be moved.  */
        !           749:                    already_moved[m1->regno] = 1;
        !           750: 
        !           751:                    /* The reg merged here is now invariant.  */
        !           752:                    if (m->partial)
        !           753:                      n_times_set[m1->regno] = 0;
        !           754:                  }
        !           755:            }
        !           756:          else if (loop_dump_stream)
        !           757:            fprintf (loop_dump_stream, "not desirable");
        !           758:        }
        !           759:       else if (loop_dump_stream && !m->match)
        !           760:        fprintf (loop_dump_stream, "not safe");
        !           761: 
        !           762:       if (loop_dump_stream)
        !           763:        fprintf (loop_dump_stream, "\n");
        !           764:     }
        !           765: 
        !           766:   if (new_start == 0)
        !           767:     new_start = loop_start;
        !           768: 
        !           769:   /* Go through all the instructions in the loop, making
        !           770:      all the register substitutions scheduled in REG_MAP.  */
        !           771:   for (p = new_start; p != end; p = NEXT_INSN (p))
        !           772:     if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
        !           773:        || GET_CODE (p) == CALL_INSN)
        !           774:       replace_regs (PATTERN (p), reg_map);
        !           775: }
        !           776: 
        !           777: /* Optionally change a loop which enters just before the endtest
        !           778:    to one which falls straight in
        !           779:    after skipping around the entire loop if the endtest would drop out.
        !           780:    Returns 1 if the change was made, 0 if the loop was not really suitable.  */
        !           781: 
        !           782: int
        !           783: loop_skip_over (start, end, loop_entry_jump)
        !           784:      rtx start;
        !           785:      rtx end;
        !           786:      rtx loop_entry_jump;
        !           787: {
        !           788:   rtx endtestjump;
        !           789:   register rtx p = JUMP_LABEL (loop_entry_jump);
        !           790: 
        !           791:   while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN
        !           792:         && GET_CODE (p) != CALL_INSN)
        !           793:     p = NEXT_INSN (p);
        !           794:   endtestjump = next_real_insn (p);
        !           795: 
        !           796:   /* Check that we (1) enter at a compare insn and (2)
        !           797:      the insn (presumably a jump) following that compare
        !           798:      is the last in the loop and jumps back to the loop beginning.  */
        !           799: 
        !           800:   if (GET_CODE (PATTERN (p)) == SET
        !           801:       && SET_DEST (PATTERN (p)) == cc0_rtx
        !           802:       && endtestjump == prev_real_insn (end)
        !           803:       && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump)
        !           804:     {
        !           805:       rtx newlab;
        !           806:       /* This is the jump that we insert.  */
        !           807:       rtx new_jump;
        !           808: 
        !           809:       /* Ok, duplicate that test before start of loop.  */
        !           810:       emit_insn_before (copy_rtx (PATTERN (p)), start);
        !           811:       /* Make a new entry-jump (before the original one)
        !           812:         whose condition is opposite to the loop-around endtest
        !           813:         and which jumps around the loop (to just after the endtest).  */
        !           814:       newlab = gen_label_rtx ();
        !           815:       emit_label_after (newlab, endtestjump);
        !           816:       emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start);
        !           817:       new_jump = PREV_INSN (start);
        !           818:       JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump);
        !           819:       LABEL_NUSES (JUMP_LABEL (endtestjump))++;
        !           820:       invert_jump (new_jump, newlab);
        !           821:       /* Delete the original entry-jump.  */
        !           822:       delete_insn (loop_entry_jump);
        !           823: 
        !           824:       return 1;
        !           825:     }
        !           826: 
        !           827:   return 0;
        !           828: }
        !           829: 
        !           830: /* Throughout the rtx X, replace many registers according to REG_MAP.
        !           831:    Return the replacement for X (which may be X with altered contents).
        !           832:    REG_MAP[R] is the replacement for register R, or 0 for don't replace.  */
        !           833: 
        !           834: static rtx
        !           835: replace_regs (x, reg_map)
        !           836:      rtx x;
        !           837:      rtx *reg_map;
        !           838: {
        !           839:   register RTX_CODE code = GET_CODE (x);
        !           840:   register int i;
        !           841:   register char *fmt;
        !           842: 
        !           843:   switch (code)
        !           844:     {
        !           845:     case PC:
        !           846:     case CC0:
        !           847:     case CONST_INT:
        !           848:     case CONST_DOUBLE:
        !           849:     case CONST:
        !           850:     case SYMBOL_REF:
        !           851:     case LABEL_REF:
        !           852:       return x;
        !           853: 
        !           854:     case REG:
        !           855:       if (reg_map[REGNO (x)] != 0)
        !           856:        return reg_map[REGNO (x)];
        !           857:       return x;
        !           858:     }
        !           859: 
        !           860:   fmt = GET_RTX_FORMAT (code);
        !           861:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !           862:     {
        !           863:       if (fmt[i] == 'e')
        !           864:        XEXP (x, i) = replace_regs (XEXP (x, i), reg_map);
        !           865:       if (fmt[i] == 'E')
        !           866:        {
        !           867:          register int j;
        !           868:          for (j = 0; j < XVECLEN (x, i); j++)
        !           869:            XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map);
        !           870:        }
        !           871:     }
        !           872:   return x;
        !           873: }
        !           874: 
        !           875: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
        !           876:    Replace it with an instruction to load just the low bytes
        !           877:    if the machine supports such an instruction,
        !           878:    and insert above LOOP_START an instruction to clear the register.  */
        !           879: 
        !           880: static void
        !           881: constant_high_bytes (p, loop_start)
        !           882:      rtx p, loop_start;
        !           883: {
        !           884:   register rtx new;
        !           885:   register int insn_code_number;
        !           886: 
        !           887:   /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
        !           888:      to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...).  */
        !           889: 
        !           890:   new = gen_rtx (SET, VOIDmode,
        !           891:                 gen_rtx (STRICT_LOW_PART, VOIDmode,
        !           892:                          gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
        !           893:                                   SET_DEST (PATTERN (p)),
        !           894:                                   0)),
        !           895:                 XEXP (SET_SRC (PATTERN (p)), 0));
        !           896:   insn_code_number = recog (new, p);
        !           897: 
        !           898:   if (insn_code_number)
        !           899:     {
        !           900:       register int i;
        !           901: 
        !           902:       /* Clear destination register before the loop.  */
        !           903:       emit_insn_before (gen_rtx (SET, VOIDmode,
        !           904:                                 SET_DEST (PATTERN (p)),
        !           905:                                 const0_rtx),
        !           906:                        loop_start);
        !           907: 
        !           908:       /* Inside the loop, just load the low part.  */
        !           909:       PATTERN (p) = new;
        !           910:     }
        !           911: }
        !           912: 
        !           913: /* Verify that the ostensible loop starting at START
        !           914:    really is a loop: nothing jumps into it from outside.
        !           915:    Return the marker for the end of the loop, or zero if not a real loop.
        !           916: 
        !           917:    Also set the variables `unknown_*_altered' and `loop_has_call',
        !           918:    and fill in the array `loop_store_addrs'.  */
        !           919: 
        !           920: static rtx
        !           921: verify_loop (f, start)
        !           922:      rtx f, start;
        !           923: {
        !           924:   register int level = 1;
        !           925:   register rtx insn, end;
        !           926: 
        !           927:   /* First find the LOOP_END that matches.
        !           928:      Also check each insn for storing in memory and record where.  */
        !           929: 
        !           930:   unknown_address_altered = 0;
        !           931:   unknown_aggregate_altered = 0;
        !           932:   fixed_aggregate_altered = 0;
        !           933:   loop_has_call = 0;
        !           934:   loop_store_addrs_idx = 0;
        !           935: 
        !           936:   for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn))
        !           937:     {
        !           938:       if (insn == 0)
        !           939:        /* Parse errors can cause a loop-beg with no loop-end.  */
        !           940:        return 0;
        !           941:       if (GET_CODE (insn) == NOTE)
        !           942:        {
        !           943:          if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
        !           944:            ++level;
        !           945:          else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
        !           946:            {
        !           947:              --level;
        !           948:              if (level == 0)
        !           949:                {
        !           950:                  end = insn;
        !           951:                  break;
        !           952:                }
        !           953:            }
        !           954:        }
        !           955:       else if (GET_CODE (insn) == CALL_INSN)
        !           956:        {
        !           957:          unknown_address_altered = 1;
        !           958:          loop_has_call = 1;
        !           959:        }
        !           960:       else if (! unknown_address_altered)
        !           961:        {
        !           962:          if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
        !           963:            note_stores (PATTERN (insn), note_addr_stored);
        !           964:        }
        !           965:     }
        !           966: 
        !           967:   /* Now scan all jumps in the function and see if any of them can
        !           968:      reach a label within the range of the loop.  */
        !           969: 
        !           970:   for (insn = f; insn; insn = NEXT_INSN (insn))
        !           971:     if (GET_CODE (insn) == JUMP_INSN
        !           972:        /* Don't get fooled by jumps inserted by loop-optimize.
        !           973:           They don't have valid LUIDs, and they never jump into loops.  */
        !           974:        && INSN_UID (insn) < max_uid
        !           975:        && (INSN_LUID (insn) < INSN_LUID (start)
        !           976:            || INSN_LUID (insn) > INSN_LUID (end))
        !           977:        /* We have a jump that is outside the loop.
        !           978:           Does it jump into the loop?  */
        !           979:        && can_jump_into_range_p (PATTERN (insn),
        !           980:                                  INSN_LUID (start), INSN_LUID (end)))
        !           981:       return 0;
        !           982: 
        !           983: #if 0      
        !           984:   /* Now scan all labels between them and check for any jumps from outside.
        !           985:      This uses the ref-chains set up by find_basic_blocks.
        !           986:      This code is not used because it's more convenient for other reasons
        !           987:      to do the loop optimization before find_basic_blocks.  */
        !           988: 
        !           989:   for (insn = start; insn != end; insn = NEXT_INSN (insn))
        !           990:     if (GET_CODE (insn) == CODE_LABEL)
        !           991:       {
        !           992:        register rtx y;
        !           993:        for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y))
        !           994:          if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start)
        !           995:              || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end))
        !           996:            return 0;
        !           997:       }
        !           998: #endif
        !           999: 
        !          1000:   return end;
        !          1001: }
        !          1002: 
        !          1003: /* Return 1 if somewhere in X is a LABEL_REF to a label
        !          1004:    located between BEG and END.  */
        !          1005: 
        !          1006: static int
        !          1007: can_jump_into_range_p (x, beg, end)
        !          1008:      rtx x;
        !          1009:      int beg, end;
        !          1010: {
        !          1011:   register RTX_CODE code = GET_CODE (x);
        !          1012:   register int i;
        !          1013:   register char *fmt;
        !          1014: 
        !          1015:   if (code == LABEL_REF)
        !          1016:     {
        !          1017:       register int luid = INSN_LUID (XEXP (x, 0));
        !          1018:       return luid > beg && luid < end;
        !          1019:     }
        !          1020: 
        !          1021:   fmt = GET_RTX_FORMAT (code);
        !          1022:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !          1023:     {
        !          1024:       if (fmt[i] == 'e')
        !          1025:        {
        !          1026:          if (can_jump_into_range_p (XEXP (x, i), beg, end))
        !          1027:            return 1;
        !          1028:        }
        !          1029:       else if (fmt[i] == 'E')
        !          1030:        {
        !          1031:          register int j;
        !          1032:          for (j = 0; j < XVECLEN (x, i); j++)
        !          1033:            if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end))
        !          1034:              return 1;
        !          1035:        }
        !          1036:     }
        !          1037: 
        !          1038:   return 0;
        !          1039: }
        !          1040: 
        !          1041: /* Record that a memory reference X is being set.  */
        !          1042: 
        !          1043: static void
        !          1044: note_addr_stored (x)
        !          1045:      rtx x;
        !          1046: {
        !          1047:   rtx addr;
        !          1048:   if (x == 0 || GET_CODE (x) != MEM)
        !          1049:     return;
        !          1050:   if (GET_MODE (x) == BLKmode)
        !          1051:     unknown_address_altered = 1;
        !          1052:   else if (rtx_addr_varies_p (x))
        !          1053:     {
        !          1054:       if (GET_CODE (XEXP (x, 0)) == PLUS)
        !          1055:        unknown_aggregate_altered = 1;
        !          1056:       else
        !          1057:        unknown_address_altered = 1;
        !          1058:     }
        !          1059:   else
        !          1060:     {
        !          1061:       register int i;
        !          1062:       register rtx addr = XEXP (x, 0);
        !          1063: 
        !          1064:       if (x->in_struct)
        !          1065:        fixed_aggregate_altered = 1;
        !          1066:       for (i = 0; i < loop_store_addrs_idx; i++)
        !          1067:        if (rtx_equal_p (loop_store_addrs[i], addr))
        !          1068:          {
        !          1069:            if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x)))
        !          1070:              loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
        !          1071:            break;
        !          1072:          }
        !          1073:       if (i == NUM_STORES)
        !          1074:        unknown_address_altered = 1;
        !          1075:       else if (i == loop_store_addrs_idx)
        !          1076:        {
        !          1077:          loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
        !          1078:          loop_store_addrs[loop_store_addrs_idx++] = addr;
        !          1079:        }
        !          1080:     }
        !          1081: }
        !          1082: 
        !          1083: /* Return nonzero if the rtx X is invariant over the current loop.
        !          1084:    N_TIMES_SET is a vector whose element I is nonzero if register I
        !          1085:    is set during the loop.
        !          1086: 
        !          1087:    The value is 2 if we refer to something only conditionally invariant.
        !          1088: 
        !          1089:    If `unknown_address_altered' is nonzero, no memory ref is invariant.
        !          1090:    Otherwise if `unknown_aggregate_altered' is nonzero,
        !          1091:    a memory ref is invariant if it is not part of an aggregate
        !          1092:    and its address is fixed and not in `loop_store_addrs'.
        !          1093:    Otherwise if `fixed_aggregate_altered' is nonzero,
        !          1094:    a memory ref is invariant
        !          1095:    if its address is fixed and not in `loop_store_addrs'.
        !          1096:    Otherwise, a memory ref is invariant if its address is fixed and not in
        !          1097:    `loop_store_addrs' or if it is not an aggregate.  */
        !          1098: 
        !          1099: static int
        !          1100: invariant_p (x, n_times_set)
        !          1101:      register rtx x;
        !          1102:      short *n_times_set;
        !          1103: {
        !          1104:   register int i;
        !          1105:   register RTX_CODE code = GET_CODE (x);
        !          1106:   register char *fmt;
        !          1107:   int conditional = 0;
        !          1108: 
        !          1109:   switch (code)
        !          1110:     {
        !          1111:     case CONST_INT:
        !          1112:     case CONST_DOUBLE:
        !          1113:     case SYMBOL_REF:
        !          1114:     case LABEL_REF:
        !          1115:     case CONST:
        !          1116:       return 1;
        !          1117: 
        !          1118:     case PC:
        !          1119:     case CC0:
        !          1120:       return 0;
        !          1121: 
        !          1122:     case REG:
        !          1123:       if (x == frame_pointer_rtx || x == arg_pointer_rtx
        !          1124:          || x->unchanging)
        !          1125:        return 1;
        !          1126:       if (n_times_set[REGNO (x)] == -1)
        !          1127:        return 2;
        !          1128:       return n_times_set[REGNO (x)] == 0;
        !          1129: 
        !          1130:     case MEM:
        !          1131:       /* A store in a varying-address scalar (or a subroutine call)
        !          1132:         could clobber anything in memory.  */
        !          1133:       if (unknown_address_altered)
        !          1134:        return 0;
        !          1135:       /* Don't mess with volatile memory references.  */
        !          1136:       if (x->volatil)
        !          1137:        return 0;
        !          1138:       /* If it's declared read-only, it is invariant
        !          1139:         if its address is invariant.  */
        !          1140:       if (x->unchanging)
        !          1141:        return invariant_p (XEXP (x, 0), n_times_set);
        !          1142:       /* A store in a varying-address aggregate component
        !          1143:         could clobber anything except a scalar with a fixed address.  */
        !          1144:       if (unknown_aggregate_altered
        !          1145:          && ((x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
        !          1146:              || rtx_addr_varies_p (x)))
        !          1147:        return 0;
        !          1148:       /* A store in a fixed-address aggregate component
        !          1149:         could clobber anything whose address is not fixed,
        !          1150:         even an aggregate component.  */
        !          1151:       if (fixed_aggregate_altered
        !          1152:          && rtx_addr_varies_p (x))
        !          1153:        return 0;
        !          1154:       /* Any store could clobber a varying-address scalar.  */
        !          1155:       if (loop_store_addrs_idx
        !          1156:          && !(x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
        !          1157:          && rtx_addr_varies_p (x))
        !          1158:        return 0;
        !          1159:       /* A store in a fixed address clobbers overlapping references.  */
        !          1160:       for (i = loop_store_addrs_idx - 1; i >= 0; i--)
        !          1161:        if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i]))
        !          1162:          return 0;
        !          1163:       /* It's not invalidated by a store in memory
        !          1164:         but we must still verify the address is invariant.  */
        !          1165:       break;
        !          1166: 
        !          1167:     case ASM_OPERANDS:
        !          1168:       /* Don't mess with insns declared volatile.  */
        !          1169:       if (x->volatil)
        !          1170:        return 0;
        !          1171:     }
        !          1172: 
        !          1173:   fmt = GET_RTX_FORMAT (code);
        !          1174:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !          1175:     {
        !          1176:       if (fmt[i] == 'e')
        !          1177:        {
        !          1178:          int tem = invariant_p (XEXP (x, i), n_times_set);
        !          1179:          if (tem == 0)
        !          1180:            return 0;
        !          1181:          if (tem == 2)
        !          1182:            conditional = 1;
        !          1183:        }
        !          1184:       else if (fmt[i] == 'E')
        !          1185:        {
        !          1186:          register int j;
        !          1187:          for (j = 0; j < XVECLEN (x, i); j++)
        !          1188:            {
        !          1189:              int tem = invariant_p (XVECEXP (x, i, j), n_times_set);
        !          1190:              if (tem == 0)
        !          1191:                return 0;
        !          1192:              if (tem == 2)
        !          1193:                conditional = 1;
        !          1194:            }
        !          1195: 
        !          1196:        }
        !          1197:     }
        !          1198: 
        !          1199:   return 1 + conditional;
        !          1200: }
        !          1201: 
        !          1202: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
        !          1203:    which is SIZE bytes starting at BASE.  */
        !          1204: 
        !          1205: int
        !          1206: addr_overlap_p (other, base, size)
        !          1207:      rtx other;
        !          1208:      rtx base;
        !          1209:      int size;
        !          1210: {
        !          1211:   int start = 0, end;
        !          1212: 
        !          1213:   if (GET_CODE (base) == CONST)
        !          1214:     base = XEXP (base, 0);
        !          1215:   if (GET_CODE (base) == PLUS
        !          1216:       && GET_CODE (XEXP (base, 1)) == CONST_INT)
        !          1217:     {
        !          1218:       start = INTVAL (XEXP (base, 1));
        !          1219:       base = XEXP (base, 0);
        !          1220:     }
        !          1221: 
        !          1222:   end = start + size;
        !          1223:   return refers_to_mem_p (other, base, start, end);
        !          1224: }
        !          1225: 
        !          1226: /* Return 1 if all the insns in the loop that set REG
        !          1227:    are INSN and the immediately following insns,
        !          1228:    and if each of those insns sets REG in an invariant way
        !          1229:    according to TABLE (not counting uses of REG in them).
        !          1230: 
        !          1231:    We assume that INSN itself is the first set of REG
        !          1232:    and that its source is invariant.  */
        !          1233: 
        !          1234: static int
        !          1235: consec_sets_invariant_p (reg, insn, table)
        !          1236:      rtx reg, insn;
        !          1237:      short *table;
        !          1238: {
        !          1239:   register rtx p = insn;
        !          1240:   register int regno = REGNO (reg);
        !          1241:   /* Number of sets we have to insist on finding after INSN.  */
        !          1242:   int count = table[regno] - 1;
        !          1243:   int old = table[regno];
        !          1244: 
        !          1245:   table[regno] = 0;
        !          1246: 
        !          1247:   while (count > 0)
        !          1248:     {
        !          1249:       register enum rtx_code code;
        !          1250:       p = NEXT_INSN (p);
        !          1251:       code = GET_CODE (p);
        !          1252:       if (code == INSN && GET_CODE (PATTERN (p)) == SET
        !          1253:          && GET_CODE (SET_DEST (PATTERN (p))) == REG
        !          1254:          && REGNO (SET_DEST (PATTERN (p))) == regno
        !          1255:          && invariant_p (SET_SRC (PATTERN (p)), table))
        !          1256:        count--;
        !          1257:       else if (code != NOTE)
        !          1258:        {
        !          1259:          table[regno] = old;
        !          1260:          return 0;
        !          1261:        }
        !          1262:     }
        !          1263: 
        !          1264:   table[regno] = old;
        !          1265:   return 1;
        !          1266: }
        !          1267: 
        !          1268: #if 0
        !          1269: /* I don't think this condition is sufficient to allow INSN
        !          1270:    to be moved, so we no longer test it.  */
        !          1271: 
        !          1272: /* Return 1 if all insns in the basic block of INSN and following INSN
        !          1273:    that set REG are invariant according to TABLE.  */
        !          1274: 
        !          1275: static int
        !          1276: all_sets_invariant_p (reg, insn, table)
        !          1277:      rtx reg, insn;
        !          1278:      short *table;
        !          1279: {
        !          1280:   register rtx p = insn;
        !          1281:   register int regno = REGNO (reg);
        !          1282: 
        !          1283:   while (1)
        !          1284:     {
        !          1285:       register enum rtx_code code;
        !          1286:       p = NEXT_INSN (p);
        !          1287:       code = GET_CODE (p);
        !          1288:       if (code == CODE_LABEL || code == JUMP_INSN)
        !          1289:        return 1;
        !          1290:       if (code == INSN && GET_CODE (PATTERN (p)) == SET
        !          1291:          && GET_CODE (SET_DEST (PATTERN (p))) == REG
        !          1292:          && REGNO (SET_DEST (PATTERN (p))) == regno)
        !          1293:        {
        !          1294:          if (!invariant_p (SET_SRC (PATTERN (p)), table))
        !          1295:            return 0;
        !          1296:        }
        !          1297:     }
        !          1298: }
        !          1299: #endif /* 0 */
        !          1300: 
        !          1301: /* Increment N_TIMES_SET at the index of each register
        !          1302:    that is modified by an insn between FROM and TO.
        !          1303:    If the value of an element of N_TIMES_SET becomes 2 or more,
        !          1304:    do not keep incrementing it; all values >= 2 would be
        !          1305:    equivalent anyway, and this way we avoid danger of overflow.
        !          1306: 
        !          1307:    Store in *COUNT_PTR the number of actual instruction
        !          1308:    in the loop.  We use this to decide what is worth moving out.  */
        !          1309: 
        !          1310: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
        !          1311:    In that case, it is the insn that last set reg n.  */
        !          1312: 
        !          1313: static void
        !          1314: count_loop_regs_set (from, to, n_times_set, may_not_move, count_ptr, nregs)
        !          1315:      register rtx from, to;
        !          1316:      short *n_times_set;
        !          1317:      char *may_not_move;
        !          1318:      int *count_ptr;
        !          1319:      int nregs;
        !          1320: {
        !          1321:   register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
        !          1322:   register rtx insn;
        !          1323:   register int count = 0;
        !          1324:   register rtx dest;
        !          1325: 
        !          1326:   bzero (last_set, nregs * sizeof (rtx));
        !          1327:   for (insn = from; insn != to; insn = NEXT_INSN (insn))
        !          1328:     {
        !          1329:       if (GET_CODE (insn) == CALL_INSN)
        !          1330:        {
        !          1331:          /* If a register is used as a subroutine address,
        !          1332:             don't allow this register's setting to be moved out of the loop.
        !          1333:             This condition is not at all logically correct
        !          1334:             but it averts a very common lossage pattern
        !          1335:             and creates lossage much less often.  */
        !          1336:          if (GET_CODE (PATTERN (insn)) == CALL
        !          1337:              && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM
        !          1338:              && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG)
        !          1339:            {
        !          1340:              register int regno
        !          1341:                = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0));
        !          1342:              may_not_move[regno] = 1;
        !          1343:            }
        !          1344:          else if (GET_CODE (PATTERN (insn)) == SET
        !          1345:              && GET_CODE (SET_SRC (PATTERN (insn))) == CALL
        !          1346:              && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM
        !          1347:              && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG)
        !          1348:            {
        !          1349:              register int regno
        !          1350:                = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0));
        !          1351:              may_not_move[regno] = 1;
        !          1352:              /* The call insn itself sets a reg, which cannot be moved.  */
        !          1353:              may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1;
        !          1354:              n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++;
        !          1355:            }
        !          1356:        }
        !          1357:       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 
        !          1358:        {
        !          1359:          ++count;
        !          1360:          if (GET_CODE (PATTERN (insn)) == CLOBBER
        !          1361:              && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
        !          1362:            /* Don't move a reg that has an explicit clobber.
        !          1363:               We might do so sometimes, but it's not worth the pain.  */
        !          1364:            may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
        !          1365:          else if (GET_CODE (PATTERN (insn)) == SET)
        !          1366:            {
        !          1367:              dest = SET_DEST (PATTERN (insn));
        !          1368:              while (GET_CODE (dest) == SUBREG
        !          1369:                     || GET_CODE (dest) == ZERO_EXTRACT
        !          1370:                     || GET_CODE (dest) == SIGN_EXTRACT
        !          1371:                     || GET_CODE (dest) == STRICT_LOW_PART)
        !          1372:                dest = XEXP (dest, 0);
        !          1373:              if (GET_CODE (dest) == REG)
        !          1374:                {
        !          1375:                  register int regno = REGNO (dest);
        !          1376:                  /* If this is the first setting of this reg
        !          1377:                     in current basic block, and it was set before,
        !          1378:                     it must be set in two basic blocks, so it cannot
        !          1379:                     be moved out of the loop.  */
        !          1380:                  if (n_times_set[regno] > 0 && last_set[regno] == 0)
        !          1381:                    may_not_move[regno] = 1;
        !          1382:                  /* If this is not first setting in current basic block,
        !          1383:                     see if reg was used in between previous one and this.
        !          1384:                     If so, neither one can be moved.  */
        !          1385:                  if (last_set[regno] != 0
        !          1386:                      && reg_used_between_p (dest, last_set[regno], insn))
        !          1387:                    may_not_move[regno] = 1;
        !          1388:                  ++n_times_set[regno];
        !          1389:                  last_set[regno] = insn;
        !          1390:                }
        !          1391:            }
        !          1392:          else if (GET_CODE (PATTERN (insn)) == PARALLEL)
        !          1393:            {
        !          1394:              register int i;
        !          1395:              for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
        !          1396:                {
        !          1397:                  register rtx x = XVECEXP (PATTERN (insn), 0, i);
        !          1398:                  if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
        !          1399:                    /* Don't move a reg that has an explicit clobber.
        !          1400:                       It's not worth the pain to try to do it correctly.  */
        !          1401:                    may_not_move[REGNO (XEXP (x, 0))] = 1;
        !          1402:                  if (GET_CODE (x) == SET)
        !          1403:                    {
        !          1404:                      dest = SET_DEST (x);
        !          1405:                      while (GET_CODE (dest) == SUBREG
        !          1406:                             || GET_CODE (dest) == ZERO_EXTRACT
        !          1407:                             || GET_CODE (dest) == SIGN_EXTRACT
        !          1408:                             || GET_CODE (dest) == STRICT_LOW_PART)
        !          1409:                        dest = XEXP (dest, 0);
        !          1410:                      if (GET_CODE (dest) == REG)
        !          1411:                        {
        !          1412:                          register int regno = REGNO (dest);
        !          1413:                          ++n_times_set[regno];
        !          1414:                          may_not_move[regno] = 1;
        !          1415:                          last_set[regno] = insn;
        !          1416:                        }
        !          1417:                    }
        !          1418:                }
        !          1419:            }
        !          1420:        }
        !          1421:       if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
        !          1422:        bzero (last_set, nregs * sizeof (rtx));
        !          1423:     }
        !          1424:   *count_ptr = count;
        !          1425: }
        !          1426: 
        !          1427: /* Given a loop that is bounded by LOOP_START and LOOP_END
        !          1428:    and that is entered at SCAN_START,
        !          1429:    return 1 if the register set by insn INSN is used by
        !          1430:    any insn that precedes INSN in cyclic order starting
        !          1431:    from the loop entry point.  */
        !          1432: 
        !          1433: static int
        !          1434: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end)
        !          1435:      rtx insn, loop_start, scan_start, loop_end;
        !          1436: {
        !          1437:   rtx reg = SET_DEST (PATTERN (insn));
        !          1438:   if (INSN_LUID (scan_start) > INSN_LUID (insn))
        !          1439:     return (reg_used_between_p (reg, scan_start, loop_end)
        !          1440:            || reg_used_between_p (reg, loop_start, insn));
        !          1441:   else
        !          1442:     return reg_used_between_p (reg, scan_start, insn);
        !          1443: }
        !          1444: 
        !          1445: /* Return nonzero if evaluating rtx X might cause a trap.  */
        !          1446: 
        !          1447: static int
        !          1448: may_trap_p (x)
        !          1449:      rtx x;
        !          1450: {
        !          1451:   int i;
        !          1452:   enum rtx_code code = GET_CODE (x);
        !          1453:   char *fmt;
        !          1454: 
        !          1455:   switch (code)
        !          1456:     {
        !          1457:       /* Handle these cases fast.  */
        !          1458:     case CONST_INT:
        !          1459:     case CONST_DOUBLE:
        !          1460:     case SYMBOL_REF:
        !          1461:     case LABEL_REF:
        !          1462:     case CONST:
        !          1463:     case PC:
        !          1464:     case CC0:
        !          1465:     case REG:
        !          1466:       return 0;
        !          1467: 
        !          1468:       /* Division by a non-constant might trap.  */
        !          1469:     case DIV:
        !          1470:     case MOD:
        !          1471:     case UDIV:
        !          1472:     case UMOD:
        !          1473:       if (! CONSTANT_P (XEXP (x, 1))
        !          1474:          && GET_CODE (XEXP (x, 1)) != CONST_DOUBLE)
        !          1475:        return 1;
        !          1476:       break;
        !          1477: 
        !          1478:       /* Memory ref can trap unless it's a static var or a stack slot.  */
        !          1479:     case MEM:
        !          1480:       return rtx_varies_p (XEXP (x, 0));
        !          1481:     }
        !          1482: 
        !          1483:   fmt = GET_RTX_FORMAT (code);
        !          1484:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !          1485:     {
        !          1486:       if (fmt[i] == 'e')
        !          1487:        {
        !          1488:          if (may_trap_p (XEXP (x, i)))
        !          1489:            return 1;
        !          1490:        }
        !          1491:       else if (fmt[i] == 'E')
        !          1492:        {
        !          1493:          register int j;
        !          1494:          for (j = 0; j < XVECLEN (x, i); j++)
        !          1495:            if (may_trap_p (XVECEXP (x, i, j)))
        !          1496:              return 1;
        !          1497:        }
        !          1498:     }
        !          1499:   return 0;
        !          1500: }

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