Return to combine.c CVS log

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

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

1.1     ! root        1: /* Optimize by combining instructions for GNU compiler.
        !             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 module is essentially the "combiner" phase of the U. of Arizona
        !            23:    Portable Optimizer, but redone to work on our list-structured
        !            24:    representation for RTL instead of their string representation.
        !            25: 
        !            26:    The LOG_LINKS of each insn identify the most recent assignment
        !            27:    to each REG used in the insn.  It is a list of previous insns,
        !            28:    each of which contains a SET for a REG that is used in this insn
        !            29:    and not used or set in between.  LOG_LINKs never cross basic blocks.
        !            30:    They were set up by the preceding pass (lifetime analysis).
        !            31: 
        !            32:    We try to combine each pair of insns joined by a logical link.
        !            33:    We also try to combine triples of insns A, B and C when
        !            34:    C has a link back to B and B has a link back to A.
        !            35: 
        !            36:    LOG_LINKS does not have links for use of the CC0.  They don't
        !            37:    need to, because the insn that sets the CC0 is always immediately
        !            38:    before the insn that tests it.  So we always regard a branch
        !            39:    insn as having a logical link to the preceding insn.
        !            40: 
        !            41:    We check (with use_crosses_set_p) to avoid combining in such a way
        !            42:    as to move a computation to a place where its value would be different.
        !            43: 
        !            44:    Combination is done by mathematically substituting the previous
        !            45:    insn(s) values for the regs they set into the expressions in
        !            46:    the later insns that refer to these regs.  If the result is a valid insn
        !            47:    for our target machine, according to the machine description,
        !            48:    we install it, delete the earlier insns, and update the data flow
        !            49:    information (LOG_LINKS and REG_NOTES) for what we did.
        !            50: 
        !            51:    To simplify substitution, we combine only when the earlier insn(s)
        !            52:    consist of only a single assignment.  To simplify updating afterward,
        !            53:    we never combine when a subroutine call appears in the middle.
        !            54: 
        !            55:    Since we do not represent assignments to CC0 explicitly except when that
        !            56:    is all an insn does, there is no LOG_LINKS entry in an insn that uses
        !            57:    the condition code for the insn that set the condition code.
        !            58:    Fortunately, these two insns must be consecutive.
        !            59:    Therefore, every JUMP_INSN is taken to have an implicit logical link
        !            60:    to the preceding insn.  This is not quite right, since non-jumps can
        !            61:    also use the condition code; but in practice such insns would not
        !            62:    combine anyway.  */
        !            63: 
        !            64: #include "config.h"
        !            65: #include "rtl.h"
        !            66: #include "flags.h"
        !            67: #include "regs.h"
        !            68: #include "basic-block.h"
        !            69: #include "insn-config.h"
        !            70: #include "recog.h"
        !            71: 
        !            72: #define max(A,B) ((A) > (B) ? (A) : (B))
        !            73: #define min(A,B) ((A) < (B) ? (A) : (B))
        !            74: 
        !            75: /* It is not safe to use ordinary gen_lowpart in combine.
        !            76:    Use gen_lowpart_for_combine instead.  See comments there.  */
        !            77: #define gen_lowpart dont_use_gen_lowpart_you_dummy
        !            78: 
        !            79: /* Number of attempts to combine instructions in this function.  */
        !            80: 
        !            81: static int combine_attempts;
        !            82: 
        !            83: /* Number of attempts that got as far as substitution in this function.  */
        !            84: 
        !            85: static int combine_merges;
        !            86: 
        !            87: /* Number of instructions combined with added SETs in this function.  */
        !            88: 
        !            89: static int combine_extras;
        !            90: 
        !            91: /* Number of instructions combined in this function.  */
        !            92: 
        !            93: static int combine_successes;
        !            94: 
        !            95: /* Totals over entire compilation.  */
        !            96: 
        !            97: static int total_attempts, total_merges, total_extras, total_successes;
        !            98: 
        !            99: 
        !           100: /* Vector mapping INSN_UIDs to cuids.
        !           101:    The cuids are like uids but increase monononically always.
        !           102:    Combine always uses cuids so that it can compare them.
        !           103:    But actually renumbering the uids, which we used to do,
        !           104:    proves to be a bad idea because it makes it hard to compare
        !           105:    the dumps produced by earlier passes with those from later passes.  */
        !           106: 
        !           107: static short *uid_cuid;
        !           108: 
        !           109: /* Get the cuid of an insn.  */
        !           110: 
        !           111: #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
        !           112: 
        !           113: 
        !           114: /* Record last point of death of (hard or pseudo) register n.  */
        !           115: 
        !           116: static rtx *reg_last_death;
        !           117: 
        !           118: /* Record last point of modification of (hard or pseudo) register n.  */
        !           119: 
        !           120: static rtx *reg_last_set;
        !           121: 
        !           122: /* Record the cuid of the last insn that invalidated memory
        !           123:    (anything that writes memory, and subroutine calls).  */
        !           124: 
        !           125: static int mem_last_set;
        !           126: 
        !           127: /* Record the cuid of the last CALL_INSN
        !           128:    so we can tell whether a potential combination crosses any calls.  */
        !           129: 
        !           130: static int last_call_cuid;
        !           131: 
        !           132: /* When `subst' is called, this is the insn that is being modified
        !           133:    (by combining in a previous insn).  The PATTERN of this insn
        !           134:    is still the old pattern partially modified and it should not be
        !           135:    looked at, but this may be used to examine the successors of the insn
        !           136:    to judge whether a simplification is valid.  */
        !           137: 
        !           138: static rtx subst_insn;
        !           139: 
        !           140: /* Record one modification to rtl structure
        !           141:    to be undone by storing old_contents into *where.  */
        !           142: 
        !           143: struct undo
        !           144: {
        !           145:   rtx *where;
        !           146:   rtx old_contents;
        !           147: };
        !           148: 
        !           149: /* Record a bunch of changes to be undone, up to MAX_UNDO of them.
        !           150:    num_undo says how many are currently recorded.
        !           151:    storage is nonzero if we must undo the allocation of new storage.
        !           152:    The value of storage is what to pass to obfree.  */
        !           153: 
        !           154: #define MAX_UNDO 10
        !           155: 
        !           156: struct undobuf
        !           157: {
        !           158:   int num_undo;
        !           159:   char *storage;
        !           160:   struct undo undo[MAX_UNDO];
        !           161: };
        !           162: 
        !           163: static struct undobuf undobuf;
        !           164: 
        !           165: /* Number of times the pseudo being substituted for
        !           166:    was found and replaced.  */
        !           167: 
        !           168: static int n_occurrences;
        !           169: 
        !           170: static void move_deaths ();
        !           171: static void remove_death ();
        !           172: static void record_dead_and_set_regs ();
        !           173: int regno_dead_p ();
        !           174: static int use_crosses_set_p ();
        !           175: static rtx subst ();
        !           176: static void undo_all ();
        !           177: static void copy_substitutions ();
        !           178: static void add_links ();
        !           179: static void add_incs ();
        !           180: static int insn_has_inc_p ();
        !           181: static int adjacent_insns_p ();
        !           182: static rtx simplify_and_const_int ();
        !           183: static rtx gen_lowpart_for_combine ();
        !           184: static void simplify_set_cc0_and ();
        !           185: 
        !           186: /* Main entry point for combiner.  F is the first insn of the function.
        !           187:    NREGS is the first unused pseudo-reg number.  */
        !           188: 
        !           189: void
        !           190: combine_instructions (f, nregs)
        !           191:      rtx f;
        !           192:      int nregs;
        !           193: {
        !           194:   register rtx insn;
        !           195:   register int i;
        !           196:   register rtx links, nextlinks;
        !           197:   rtx prev;
        !           198: 
        !           199:   combine_attempts = 0;
        !           200:   combine_merges = 0;
        !           201:   combine_extras = 0;
        !           202:   combine_successes = 0;
        !           203: 
        !           204:   reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));
        !           205:   reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));
        !           206:   bzero (reg_last_death, nregs * sizeof (rtx));
        !           207:   bzero (reg_last_set, nregs * sizeof (rtx));
        !           208: 
        !           209:   init_recog ();
        !           210: 
        !           211:   /* Compute maximum uid value so uid_cuid can be allocated.  */
        !           212: 
        !           213:   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           214:     if (INSN_UID (insn) > i)
        !           215:       i = INSN_UID (insn);
        !           216: 
        !           217:   uid_cuid = (short *) alloca ((i + 1) * sizeof (short));
        !           218: 
        !           219:   /* Compute the mapping from uids to cuids.
        !           220:      Cuids are numbers assigned to insns, like uids,
        !           221:      except that cuids increase monotonically through the code.  */
        !           222: 
        !           223:   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           224:     INSN_CUID (insn) = ++i;
        !           225: 
        !           226:   /* Now scan all the insns in forward order.  */
        !           227: 
        !           228:   last_call_cuid = 0;
        !           229:   mem_last_set = 0;
        !           230:   prev = 0;
        !           231: 
        !           232:   for (insn = f; insn; insn = NEXT_INSN (insn))
        !           233:     {
        !           234:       if (GET_CODE (insn) == INSN
        !           235:          || GET_CODE (insn) == CALL_INSN
        !           236:          || GET_CODE (insn) == JUMP_INSN)
        !           237:        {
        !           238:        retry:
        !           239:          /* Try this insn with each insn it links back to.  */
        !           240: 
        !           241:          for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
        !           242:            if (try_combine (insn, XEXP (links, 0), 0))
        !           243:              goto retry;
        !           244: 
        !           245:          /* Try each sequence of three linked insns ending with this one.  */
        !           246: 
        !           247:          for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
        !           248:            if (GET_CODE (XEXP (links, 0)) != NOTE)
        !           249:              for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
        !           250:                   nextlinks = XEXP (nextlinks, 1))
        !           251:                if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
        !           252:                  goto retry;
        !           253: 
        !           254:          /* Try to combine a jump insn that uses CC0
        !           255:             with a preceding insn that sets CC0, and maybe with its
        !           256:             logical predecessor as well.
        !           257:             This is how we make decrement-and-branch insns.
        !           258:             We need this special code because data flow connections
        !           259:             via CC0 do not get entered in LOG_LINKS.  */
        !           260: 
        !           261:          if (GET_CODE (insn) == JUMP_INSN
        !           262:              && prev != 0
        !           263:              && GET_CODE (prev) == INSN
        !           264:              && GET_CODE (PATTERN (prev)) == SET
        !           265:              && GET_CODE (SET_DEST (PATTERN (prev))) == CC0)
        !           266:            {
        !           267:              if (try_combine (insn, prev, 0))
        !           268:                  goto retry;
        !           269: 
        !           270:              if (GET_CODE (prev) != NOTE)
        !           271:                for (nextlinks = LOG_LINKS (prev); nextlinks;
        !           272:                     nextlinks = XEXP (nextlinks, 1))
        !           273:                  if (try_combine (insn, prev, XEXP (nextlinks, 0)))
        !           274:                    goto retry;
        !           275:            }
        !           276: #if 0
        !           277: /* Turned off because on 68020 it takes four insns to make
        !           278:    something like (a[b / 32] & (1 << (31 - (b % 32)))) != 0
        !           279:    that could actually be optimized, and that's an unlikely piece of code.  */
        !           280:          /* If an insn gets or sets a bit field, try combining it
        !           281:             with two different insns whose results it uses.  */
        !           282:          if (GET_CODE (insn) == INSN
        !           283:              && GET_CODE (PATTERN (insn)) == SET
        !           284:              && (GET_CODE (SET_DEST (PATTERN (insn))) == ZERO_EXTRACT
        !           285:                  || GET_CODE (SET_DEST (PATTERN (insn))) == SIGN_EXTRACT
        !           286:                  || GET_CODE (SET_SRC (PATTERN (insn))) == ZERO_EXTRACT
        !           287:                  || GET_CODE (SET_SRC (PATTERN (insn))) == SIGN_EXTRACT))
        !           288:            {
        !           289:              for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
        !           290:                if (GET_CODE (XEXP (links, 0)) != NOTE)
        !           291:                  for (nextlinks = XEXP (links, 1); nextlinks;
        !           292:                       nextlinks = XEXP (nextlinks, 1))
        !           293:                    if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
        !           294:                      goto retry;
        !           295:            }
        !           296: #endif
        !           297:          record_dead_and_set_regs (insn);
        !           298:          prev = insn;
        !           299:        }
        !           300:       else if (GET_CODE (insn) != NOTE)
        !           301:        prev = 0;
        !           302:     }
        !           303:   total_attempts += combine_attempts;
        !           304:   total_merges += combine_merges;
        !           305:   total_extras += combine_extras;
        !           306:   total_successes += combine_successes;
        !           307: }
        !           308: 
        !           309: /* Try to combine the insns I1 and I2 into I3.
        !           310:    Here I1 appears earlier than I2, which is earlier than I3.
        !           311:    I1 can be zero; then we combine just I2 into I3.
        !           312:  
        !           313:    Return 1 if successful; if that happens, I1 and I2 are pseudo-deleted
        !           314:    by turning them into NOTEs, and I3 is modified.
        !           315:    Return 0 if the combination does not work.  Then nothing is changed.  */
        !           316: 
        !           317: static int
        !           318: try_combine (i3, i2, i1)
        !           319:      register rtx i3, i2, i1;
        !           320: {
        !           321:   register rtx newpat;
        !           322:   int added_sets_1 = 0;
        !           323:   int added_sets_2 = 0;
        !           324:   int total_sets;
        !           325:   int i2_is_used;
        !           326:   register rtx link;
        !           327:   int insn_code_number;
        !           328:   int recog_flags = 0;
        !           329:   rtx i2dest, i2src;
        !           330:   rtx i1dest, i1src;
        !           331:   int maxreg;
        !           332: 
        !           333:   combine_attempts++;
        !           334: 
        !           335:   /* Don't combine with something already used up by combination.  */
        !           336: 
        !           337:   if (GET_CODE (i2) == NOTE
        !           338:       || (i1 && GET_CODE (i1) == NOTE))
        !           339:     return 0;
        !           340: 
        !           341:   /* Don't combine across a CALL_INSN, because that would possibly
        !           342:      change whether the life span of some REGs crosses calls or not,
        !           343:      and it is a pain to update that information.  */
        !           344: 
        !           345:   if (INSN_CUID (i2) < last_call_cuid
        !           346:       || (i1 && INSN_CUID (i1) < last_call_cuid))
        !           347:     return 0;
        !           348: 
        !           349:   /* Can combine only if previous insn is a SET of a REG, a SUBREG or CC0.
        !           350:      That REG must be either set or dead by the final instruction
        !           351:      (so that we can safely forget about setting it).
        !           352:      Also test use_crosses_set_p to make sure that the value
        !           353:      that is to be substituted for the register
        !           354:      does not use any registers whose values alter in between.
        !           355:      Do not try combining with moves from one register to another
        !           356:      since it is better to let them be tied by register allocation.
        !           357:      (There is a switch to permit such combination; except the insns
        !           358:      that copy a function value into another register are never combined
        !           359:      because moving that too far away from the function call could cause
        !           360:      something else to be stored in that register in the interim.)
        !           361: 
        !           362:      A set of a SUBREG is considered as if it were a set from
        !           363:      SUBREG.  Thus, (SET (SUBREG:X (REG:Y...)) (something:X...))
        !           364:      is handled by substituting (SUBREG:Y (something:X...)) for (REG:Y...).  */
        !           365: 
        !           366:   if (GET_CODE (PATTERN (i2)) != SET)
        !           367:     return 0;
        !           368:   i2dest = SET_DEST (PATTERN (i2));
        !           369:   i2src = SET_SRC (PATTERN (i2));
        !           370:   if (GET_CODE (i2dest) == SUBREG)
        !           371:     {
        !           372:       i2dest = SUBREG_REG (i2dest);
        !           373:       i2src = gen_rtx (SUBREG, GET_MODE (i2dest), i2src, 0);
        !           374:     }
        !           375:   if (GET_CODE (i2dest) != CC0
        !           376:       && (GET_CODE (i2dest) != REG
        !           377:          || (GET_CODE (i2src) == REG
        !           378:              && (!flag_combine_regs
        !           379:                  || FUNCTION_VALUE_REGNO_P (REGNO (i2src))))
        !           380:          || GET_CODE (i2src) == CALL
        !           381:          || use_crosses_set_p (i2src, INSN_CUID (i2))))
        !           382:     return 0;
        !           383: 
        !           384:   if (i1 != 0)
        !           385:     {
        !           386:       if (GET_CODE (PATTERN (i1)) != SET)
        !           387:        return 0;
        !           388:       i1dest = SET_DEST (PATTERN (i1));
        !           389:       i1src = SET_SRC (PATTERN (i1));
        !           390:       if (GET_CODE (i1dest) == SUBREG)
        !           391:        {
        !           392:          i1dest = SUBREG_REG (i1dest);
        !           393:          i1src = gen_rtx (SUBREG, GET_MODE (i1dest), i1src, 0);
        !           394:        }
        !           395:       if (GET_CODE (i1dest) != CC0
        !           396:          && (GET_CODE (i1dest) != REG
        !           397:              || (GET_CODE (i1src) == REG
        !           398:                  && (!flag_combine_regs
        !           399:                      || FUNCTION_VALUE_REGNO_P (REGNO (i1src))))
        !           400:              || GET_CODE (i1src) == CALL
        !           401:              || use_crosses_set_p (i1src, INSN_CUID (i1))))
        !           402:        return 0;
        !           403:     }
        !           404: 
        !           405:   /* If I1 or I2 contains an autoincrement or autodecrement,
        !           406:      make sure that register is not used between there and I3.
        !           407:      Also insist that I3 not be a jump; if it were one
        !           408:      and the incremented register were spilled, we would lose.  */
        !           409:   if ((link = find_reg_note (i2, REG_INC, 0)) != 0
        !           410:       && (GET_CODE (i3) == JUMP_INSN
        !           411:          || reg_used_between_p (XEXP (link, 0), i2, i3)
        !           412:          || reg_mentioned_p (XEXP (link, 0), i3)))
        !           413:     return 0;
        !           414: 
        !           415:   if (i1 && (link = find_reg_note (i1, REG_INC, 0)) != 0
        !           416:       && (GET_CODE (i3) == JUMP_INSN
        !           417:          || reg_used_between_p (XEXP (link, 0), i1, i3)
        !           418:          || reg_mentioned_p (XEXP (link, 0), i3)))
        !           419:     return 0;
        !           420: 
        !           421:   /* See if the SETs in i1 or i2 need to be kept around in the merged
        !           422:      instruction: whenever the value set there is still needed past i3.  */
        !           423:   added_sets_2 = (GET_CODE (i2dest) != CC0
        !           424:                  && ! dead_or_set_p (i3, i2dest));
        !           425:   if (i1)
        !           426:     added_sets_1 = ! (dead_or_set_p (i3, i1dest)
        !           427:                      || dead_or_set_p (i2, i1dest));
        !           428: 
        !           429:   combine_merges++;
        !           430: 
        !           431:   undobuf.num_undo = 0;
        !           432:   undobuf.storage = 0;
        !           433: 
        !           434:   /* Substitute in the latest insn for the regs set by the earlier ones.  */
        !           435: 
        !           436:   maxreg = max_reg_num ();
        !           437: 
        !           438:   subst_insn = i3;
        !           439:   n_occurrences = 0;           /* `subst' counts here */
        !           440: 
        !           441:   newpat = subst (PATTERN (i3), i2dest, i2src);
        !           442:   /* Record whether i2's body now appears within i3's body.  */
        !           443:   i2_is_used = n_occurrences;
        !           444: 
        !           445:   if (i1)
        !           446:     {
        !           447:       n_occurrences = 0;
        !           448:       newpat = subst (newpat, i1dest, i1src);
        !           449:     }
        !           450: 
        !           451:   if (GET_CODE (PATTERN (i3)) == SET
        !           452:       && SET_DEST (PATTERN (i3)) == cc0_rtx
        !           453:       && (GET_CODE (SET_SRC (PATTERN (i3))) == AND
        !           454:          || GET_CODE (SET_SRC (PATTERN (i3))) == LSHIFTRT)
        !           455:       && next_insn_tests_no_inequality (i3))
        !           456:     simplify_set_cc0_and (i3);
        !           457: 
        !           458:   if (max_reg_num () != maxreg)
        !           459:     abort ();
        !           460: 
        !           461:   /* If the actions of the earler insns must be kept
        !           462:      in addition to substituting them into the latest one,
        !           463:      we must make a new PARALLEL for the latest insn
        !           464:      to hold additional the SETs.  */
        !           465: 
        !           466:   if (added_sets_1 || added_sets_2)
        !           467:     {
        !           468:       combine_extras++;
        !           469: 
        !           470:       /* Arrange to free later what we allocate now
        !           471:         if we don't accept this combination.  */
        !           472:       if (!undobuf.storage)
        !           473:        undobuf.storage = (char *) oballoc (0);
        !           474: 
        !           475:       if (GET_CODE (newpat) == PARALLEL)
        !           476:        {
        !           477:          rtvec old = XVEC (newpat, 0);
        !           478:          total_sets = XVECLEN (newpat, 0) + added_sets_1 + added_sets_2;
        !           479:          newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
        !           480:          bcopy (&old->elem[0], &XVECEXP (newpat, 0, 0),
        !           481:                 sizeof (old->elem[0]) * old->num_elem);
        !           482:        }
        !           483:       else
        !           484:        {
        !           485:          rtx old = newpat;
        !           486:          total_sets = 1 + added_sets_1 + added_sets_2;
        !           487:          newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
        !           488:          XVECEXP (newpat, 0, 0) = old;
        !           489:        }
        !           490:      if (added_sets_1)
        !           491:        {
        !           492:          XVECEXP (newpat, 0, --total_sets) = PATTERN (i1);
        !           493:        }
        !           494:      if (added_sets_2)
        !           495:        {
        !           496:          /* If there is no I1, use I2's body as is.  */
        !           497:          if (i1 == 0
        !           498:          /* If I2 was stuck into I3, then anything within it has
        !           499:             already had I1 substituted into it when that was done to I3.  */
        !           500:              || i2_is_used)
        !           501:            {
        !           502:              XVECEXP (newpat, 0, --total_sets) = PATTERN (i2);
        !           503:            }
        !           504:          else
        !           505:            XVECEXP (newpat, 0, --total_sets)
        !           506:              = subst (PATTERN (i2), i1dest, i1src);
        !           507:        }
        !           508:     }
        !           509: 
        !           510:   /* Fail if an autoincrement side-effect has been duplicated.  */
        !           511:   if ((i2_is_used > 1 && find_reg_note (i2, REG_INC, 0) != 0)
        !           512:       || (i1 != 0 && n_occurrences > 1 && find_reg_note (i1, REG_INC, 0) != 0))
        !           513:     {
        !           514:       undo_all ();
        !           515:       return 0;
        !           516:     }
        !           517: 
        !           518:   /* Is the result of combination a valid instruction?  */
        !           519:   insn_code_number = recog (newpat, i3);
        !           520: 
        !           521:   if (insn_code_number >= 0)
        !           522:     {
        !           523:       /* Yes.  Install it.  */
        !           524:       register int regno;
        !           525:       INSN_CODE (i3) = insn_code_number;
        !           526:       PATTERN (i3) = newpat;
        !           527:       /* If anything was substituted more than once,
        !           528:         copy it to avoid invalid shared rtl structure.  */
        !           529:       copy_substitutions ();
        !           530:       /* The data flowing into I2 now flows into I3.
        !           531:         But we cannot always move all of I2's LOG_LINKS into I3,
        !           532:         since they must go to a setting of a REG from the
        !           533:         first use following.  If I2 was the first use following a set,
        !           534:         I3 is now a use, but it is not the first use
        !           535:         if some instruction between I2 and I3 is also a use.
        !           536:         Here, for simplicity, we move all the links only if
        !           537:         there are no real insns between I2 and I3.
        !           538:         Otherwise, we move only links that correspond to regs
        !           539:         that used to die in I2.  They are always safe to move.  */
        !           540:       add_links (i3, i2, adjacent_insns_p (i2, i3));
        !           541:       /* Most REGs that previously died in I2 now die in I3.  */ 
        !           542:       move_deaths (i2src, INSN_CUID (i2), i3);
        !           543:       if (GET_CODE (i2dest) == REG)
        !           544:        {
        !           545:          /* If the reg formerly set in I2 died only once and that was in I3,
        !           546:             zero its use count so it won't make `reload' do any work.  */
        !           547:          regno = REGNO (i2dest);
        !           548:          if (! added_sets_2)
        !           549:            {
        !           550:              reg_n_sets[regno]--;
        !           551:              /* Used to check  && regno_dead_p (regno, i3)  also here.  */
        !           552:              if (reg_n_sets[regno] == 0
        !           553:                  && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
        !           554:                        & (1 << (regno % HOST_BITS_PER_INT))))
        !           555:                reg_n_refs[regno] = 0;
        !           556:            }
        !           557:          /* If a ref to REGNO was substituted into I3 from I2,
        !           558:             then it still dies there if it previously did.
        !           559:             Otherwise either REGNO never did die in I3 so remove_death is safe
        !           560:             or this entire life of REGNO is gone so remove its death.  */
        !           561:          if (!added_sets_2
        !           562:              && ! reg_mentioned_p (i2dest, PATTERN (i3)))
        !           563:            remove_death (regno, i3);
        !           564:        }
        !           565:       /* Any registers previously autoincremented in I2
        !           566:         are now incremented in I3.  */
        !           567:       add_incs (i3, REG_NOTES (i2));
        !           568:       if (i1)
        !           569:        {
        !           570:          /* Likewise, merge the info from I1 and get rid of it.  */
        !           571:          add_links (i3, i1,
        !           572:                     adjacent_insns_p (i1, i2) && adjacent_insns_p (i2, i3));
        !           573:          move_deaths (i1src, INSN_CUID (i1), i3);
        !           574:          if (GET_CODE (i1dest) == REG)
        !           575:            {
        !           576:              regno = REGNO (i1dest);
        !           577:              if (! added_sets_1)
        !           578:                {
        !           579:                  reg_n_sets[regno]--;
        !           580:                  /* Used to also check  && regno_dead_p (regno, i3) here.  */
        !           581: 
        !           582:                  if (reg_n_sets[regno] == 0
        !           583:                      && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
        !           584:                            & (1 << (regno % HOST_BITS_PER_INT))))
        !           585: 
        !           586:                    reg_n_refs[regno] = 0;
        !           587:                }
        !           588:              /* If a ref to REGNO was substituted into I3 from I1,
        !           589:                 then it still dies there if it previously did.
        !           590:                 Else either REGNO never did die in I3 so remove_death is safe
        !           591:                 or this entire life of REGNO is gone so remove its death.  */
        !           592:              if (! added_sets_1
        !           593:                  && ! reg_mentioned_p (i1dest, PATTERN (i3)))
        !           594:                remove_death (regno, i3);
        !           595:            }
        !           596:          add_incs (i3, REG_NOTES (i1));
        !           597:          LOG_LINKS (i1) = 0;
        !           598:          PUT_CODE (i1, NOTE);
        !           599:          NOTE_LINE_NUMBER (i1) = NOTE_INSN_DELETED;
        !           600:          NOTE_SOURCE_FILE (i1) = 0;
        !           601:        }
        !           602:       /* Get rid of I2.  */
        !           603:       LOG_LINKS (i2) = 0;
        !           604:       PUT_CODE (i2, NOTE);
        !           605:       NOTE_LINE_NUMBER (i2) = NOTE_INSN_DELETED;
        !           606:       NOTE_SOURCE_FILE (i2) = 0;
        !           607: 
        !           608:       combine_successes++;
        !           609:       return 1;
        !           610:     }
        !           611: 
        !           612:   /* Failure: change I3 back the way it was.  */
        !           613:   undo_all ();
        !           614: 
        !           615:   return 0;
        !           616: }
        !           617: 
        !           618: /* Undo all the modifications recorded in undobuf.  */
        !           619: 
        !           620: static void
        !           621: undo_all ()
        !           622: {
        !           623:   register int i;
        !           624:   if (undobuf.num_undo > MAX_UNDO)
        !           625:     undobuf.num_undo = MAX_UNDO;
        !           626:   for (i = undobuf.num_undo - 1; i >= 0; i--)
        !           627:     *undobuf.undo[i].where = undobuf.undo[i].old_contents;
        !           628:   if (undobuf.storage)
        !           629:     obfree (undobuf.storage);
        !           630:   undobuf.num_undo = 0;
        !           631:   undobuf.storage = 0;
        !           632: }
        !           633: 
        !           634: /* If this insn had more than one substitution,
        !           635:    copy all but one, so that no invalid shared substructure is introduced.  */
        !           636: 
        !           637: static void
        !           638: copy_substitutions ()
        !           639: {
        !           640:   register int i;
        !           641:   if (undobuf.num_undo > 1)
        !           642:     {
        !           643:       for (i = undobuf.num_undo - 1; i >= 1; i--)
        !           644:        *undobuf.undo[i].where = copy_rtx (*undobuf.undo[i].where);
        !           645:     }
        !           646: }
        !           647: 
        !           648: /* Throughout X, replace FROM with TO, and return the result.
        !           649:    The result is TO if X is FROM;
        !           650:    otherwise the result is X, but its contents may have been modified.
        !           651:    If they were modified, a record was made in undobuf so that
        !           652:    undo_all will (among other things) return X to its original state.
        !           653: 
        !           654:    If the number of changes necessary is too much to record to undo,
        !           655:    the excess changes are not made, so the result is invalid.
        !           656:    The changes already made can still be undone.
        !           657:    undobuf.num_undo is incremented for such changes, so by testing that
        !           658:    the caller can tell whether the result is valid.
        !           659: 
        !           660:    `n_occurrences' is incremented each time FROM is replaced.  */
        !           661: 
        !           662: static rtx
        !           663: subst (x, from, to)
        !           664:      register rtx x, from, to;
        !           665: {
        !           666:   register char *fmt;
        !           667:   register int len, i;
        !           668:   register enum rtx_code code;
        !           669:   char was_replaced[2];
        !           670: 
        !           671: #define SUBST(INTO, NEWVAL)  \
        !           672:  do { if (undobuf.num_undo < MAX_UNDO)                                 \
        !           673:        {                                                               \
        !           674:          undobuf.undo[undobuf.num_undo].where = &INTO;                 \
        !           675:          undobuf.undo[undobuf.num_undo].old_contents = INTO;           \
        !           676:          INTO = NEWVAL;                                                \
        !           677:        }                                                               \
        !           678:       undobuf.num_undo++; } while (0)
        !           679: 
        !           680: /* FAKE_EXTEND_SAFE_P (MODE, FROM) is 1 if (subreg:MODE FROM 0) is a safe
        !           681:    replacement for (zero_extend:MODE FROM) or (sign_extend:MODE FROM).
        !           682:    If it is 0, that cannot be done because it might cause a badly aligned
        !           683:    memory reference.  */
        !           684: 
        !           685: /* Now we never do this for memory refs, because of the danger of
        !           686:    turning a reference to the last byte on a page into a page-crossing
        !           687:    reference that could get a spurious fault.  It could be done safely
        !           688:    for certain cases but it's hard to check for them.  */
        !           689: #if 0
        !           690: #define FAKE_EXTEND_SAFE_P(MODE, FROM)  \
        !           691:    (GET_CODE (FROM) == REG ||                          \
        !           692:     (GET_CODE (FROM) == MEM                            \
        !           693:      && offsetable_address_p ((MODE), XEXP ((FROM), 0))        \
        !           694:      && ! mode_dependent_address_p ((XEXP ((FROM), 0)))))
        !           695: #else
        !           696: #define FAKE_EXTEND_SAFE_P(MODE, FROM) (GET_CODE (FROM) == REG)
        !           697: #endif
        !           698: 
        !           699:   if (x == from)
        !           700:     return to;
        !           701: 
        !           702:   /* It is possible to have a subexpression appear twice in the insn.
        !           703:      Suppose that FROM is a register that appears within TO.
        !           704:      Then, after that subexpression has been scanned once by `subst',
        !           705:      the second time it is scanned, TO may be found.  If we were
        !           706:      to scan TO here, we would find FROM within it and create a
        !           707:      self-referent rtl structure which is completely wrong.  */
        !           708:   if (x == to)
        !           709:     return to;
        !           710: 
        !           711:   code = GET_CODE (x);
        !           712: 
        !           713:   /* A little bit of algebraic simplification here.  */
        !           714:   switch (code)
        !           715:     {
        !           716:       /* This case has no effect except to speed things up.  */
        !           717:     case REG:
        !           718:     case CONST_INT:
        !           719:     case CONST:
        !           720:     case SYMBOL_REF:
        !           721:     case LABEL_REF:
        !           722:     case PC:
        !           723:     case CC0:
        !           724:       return x;
        !           725:     }
        !           726: 
        !           727:   was_replaced[0] = 0;
        !           728:   was_replaced[1] = 0;
        !           729: 
        !           730:   len = GET_RTX_LENGTH (code);
        !           731:   fmt = GET_RTX_FORMAT (code);
        !           732: 
        !           733:   /* Don't replace FROM where it is being stored in rather than used.  */
        !           734:   if (code == SET && SET_DEST (x) == from)
        !           735:     fmt = "ie";
        !           736:   if (code == SET && GET_CODE (SET_DEST (x)) == SUBREG
        !           737:       && SUBREG_REG (SET_DEST (x)) == from)
        !           738:     fmt = "ie";
        !           739: 
        !           740:   for (i = 0; i < len; i++)
        !           741:     {
        !           742:       if (fmt[i] == 'E')
        !           743:        {
        !           744:          register int j;
        !           745:          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
        !           746:            {
        !           747:              register rtx new;
        !           748:              if (XVECEXP (x, i, j) == from)
        !           749:                new = to, n_occurrences++;
        !           750:              else
        !           751:                new = subst (XVECEXP (x, i, j), from, to);
        !           752:              if (new != XVECEXP (x, i, j))
        !           753:                SUBST (XVECEXP (x, i, j), new);
        !           754:            }
        !           755:        }
        !           756:       else if (fmt[i] == 'e')
        !           757:        {
        !           758:          register rtx new;
        !           759: 
        !           760:          if (XEXP (x, i) == from)
        !           761:            {
        !           762:              new = to;
        !           763:              n_occurrences++;
        !           764:              if (i < 2)
        !           765:                was_replaced[i] = 1;
        !           766:            }
        !           767:          else
        !           768:            new = subst (XEXP (x, i), from, to);
        !           769: 
        !           770:          if (new != XEXP (x, i))
        !           771:            SUBST (XEXP (x, i), new);
        !           772:        }
        !           773:     }
        !           774: 
        !           775:   /* A little bit of algebraic simplification here.  */
        !           776:   switch (code)
        !           777:     {
        !           778:     case SUBREG:
        !           779:       /* Changing mode twice with SUBREG => just change it once,
        !           780:         or not at all if changing back to starting mode.  */
        !           781:       if (SUBREG_REG (x) == to
        !           782:          && GET_CODE (to) == SUBREG
        !           783:          && SUBREG_WORD (x) == 0
        !           784:          && SUBREG_WORD (to) == 0)
        !           785:        {
        !           786:          if (GET_MODE (x) == GET_MODE (SUBREG_REG (to)))
        !           787:            return SUBREG_REG (to);
        !           788:          SUBST (SUBREG_REG (x), SUBREG_REG (to));
        !           789:        }
        !           790:       break;
        !           791: 
        !           792:     case NOT:
        !           793:     case NEG:
        !           794:       /* Don't let substitution introduce double-negatives.  */
        !           795:       if (was_replaced[0]
        !           796:          && GET_CODE (to) == code)
        !           797:        return XEXP (to, 0);
        !           798:       break;
        !           799: 
        !           800:     case FLOAT_TRUNCATE:
        !           801:       /* (float_truncate:SF (float_extend:DF foo:SF)) = foo:SF.  */
        !           802:       if (was_replaced[0]
        !           803:          && GET_CODE (to) == FLOAT_EXTEND
        !           804:          && GET_MODE (XEXP (to, 0)) == GET_MODE (x))
        !           805:        return XEXP (to, 0);
        !           806:       break;
        !           807: 
        !           808:     case PLUS:
        !           809:       /* In (plus <foo> (ashift <bar> <n>))
        !           810:         change the shift to a multiply so we can recognize
        !           811:         scaled indexed addresses.  */
        !           812:       if ((was_replaced[0]
        !           813:           || was_replaced[1])
        !           814:          && GET_CODE (to) == ASHIFT
        !           815:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !           816:          && INTVAL (XEXP (to, 1)) < HOST_BITS_PER_INT)
        !           817:        {
        !           818:          rtx temp;
        !           819:          if (!undobuf.storage)
        !           820:            undobuf.storage = (char *) oballoc (0);
        !           821:          temp = gen_rtx (MULT, GET_MODE (to),
        !           822:                          XEXP (to, 0),
        !           823:                          gen_rtx (CONST_INT, VOIDmode,
        !           824:                                   1 << INTVAL (XEXP (to, 1))));
        !           825:          if (was_replaced[0])
        !           826:            SUBST (XEXP (x, 0), temp);
        !           827:          else
        !           828:            SUBST (XEXP (x, 1), temp);
        !           829:        }
        !           830:       /* (plus X (neg Y)) becomes (minus X Y).  */
        !           831:       if (GET_CODE (XEXP (x, 1)) == NEG)
        !           832:        {
        !           833:          if (!undobuf.storage)
        !           834:            undobuf.storage = (char *) oballoc (0);
        !           835:          return gen_rtx (MINUS, GET_MODE (x),
        !           836:                          XEXP (x, 0), XEXP (XEXP (x, 1), 0));
        !           837:        }
        !           838:       /* (plus (neg X) Y) becomes (minus Y X).  */
        !           839:       if (GET_CODE (XEXP (x, 0)) == NEG)
        !           840:        {
        !           841:          if (!undobuf.storage)
        !           842:            undobuf.storage = (char *) oballoc (0);
        !           843:          return gen_rtx (MINUS, GET_MODE (x),
        !           844:                          XEXP (x, 1), XEXP (XEXP (x, 0), 0));
        !           845:        }
        !           846:       /* (plus (plus x c1) c2) => (plus x c1+c2) */
        !           847:       if (GET_CODE (XEXP (x, 1)) == CONST_INT
        !           848:          && GET_CODE (XEXP (x, 0)) == PLUS
        !           849:          && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
        !           850:        {
        !           851:          int sum = (INTVAL (XEXP (x, 1))
        !           852:                     + INTVAL (XEXP (XEXP (x, 0), 1)));
        !           853:          if (sum == 0)
        !           854:            return XEXP (XEXP (x, 0), 0);
        !           855:          if (!undobuf.storage)
        !           856:            undobuf.storage = (char *) oballoc (0);
        !           857:          SUBST (XEXP (x, 1), gen_rtx (CONST_INT, VOIDmode, sum));
        !           858:          SUBST (XEXP (x, 0), XEXP (XEXP (x, 0), 0));
        !           859:          break;
        !           860:        }
        !           861:       /* If we have something (putative index) being added to a sum,
        !           862:         associate it so that any constant term is outermost.
        !           863:         That's because that's the way indexed addresses are
        !           864:         now supposed to appear.  */
        !           865:       if (((was_replaced[0] && GET_CODE (XEXP (x, 1)) == PLUS)
        !           866:           || (was_replaced[1] && GET_CODE (XEXP (x, 0)) == PLUS))
        !           867:          ||
        !           868:          ((was_replaced[0] || was_replaced[1])
        !           869:           && GET_CODE (to) == PLUS))
        !           870:        {
        !           871:          rtx offset = 0, base, index;
        !           872:          if (GET_CODE (to) != PLUS)
        !           873:            {
        !           874:              index = to;
        !           875:              base = was_replaced[0] ? XEXP (x, 1) : XEXP (x, 0);
        !           876:            }
        !           877:          else
        !           878:            {
        !           879:              index = was_replaced[0] ? XEXP (x, 1) : XEXP (x, 0);
        !           880:              base = to;
        !           881:            }
        !           882:          if (CONSTANT_ADDRESS_P (XEXP (base, 0)))
        !           883:            {
        !           884:              offset = XEXP (base, 0);
        !           885:              base = XEXP (base, 1);
        !           886:            }
        !           887:          else if (CONSTANT_ADDRESS_P (XEXP (base, 1)))
        !           888:            {
        !           889:              offset = XEXP (base, 1);
        !           890:              base = XEXP (base, 0);
        !           891:            }
        !           892:          if (offset != 0)
        !           893:            {
        !           894:              if (!undobuf.storage)
        !           895:                undobuf.storage = (char *) oballoc (0);
        !           896:              if (GET_CODE (offset) == CONST_INT)
        !           897:                return plus_constant (gen_rtx (PLUS, GET_MODE (index),
        !           898:                                               base, index),
        !           899:                                      INTVAL (offset));
        !           900:              if (GET_CODE (index) == CONST_INT)
        !           901:                return plus_constant (gen_rtx (PLUS, GET_MODE (offset),
        !           902:                                               base, offset),
        !           903:                                      INTVAL (index));
        !           904:              return gen_rtx (PLUS, GET_MODE (index),
        !           905:                              gen_rtx (PLUS, GET_MODE (index),
        !           906:                                       base, index),
        !           907:                              offset);
        !           908:            }
        !           909:        }
        !           910:       break;
        !           911: 
        !           912:     case MINUS:
        !           913:       /* Can simplify (minus:VOIDmode (zero/sign_extend FOO) CONST)
        !           914:         (which is a compare instruction, not a subtract instruction)
        !           915:         to (minus FOO CONST) if CONST fits in FOO's mode
        !           916:         and we are only testing equality.
        !           917:         In fact, this is valid for zero_extend if what follows is an
        !           918:         unsigned comparison, and for sign_extend with a signed comparison.  */
        !           919:       if (GET_MODE (x) == VOIDmode
        !           920:          && was_replaced[0]
        !           921:          && (GET_CODE (to) == ZERO_EXTEND || GET_CODE (to) == SIGN_EXTEND)
        !           922:          && next_insn_tests_no_inequality (subst_insn)
        !           923:          && GET_CODE (XEXP (x, 1)) == CONST_INT
        !           924:          /* This is overly cautious by one bit, but saves worrying about
        !           925:             whether it is zero-extension or sign extension.  */
        !           926:          && ((unsigned) INTVAL (XEXP (x, 1))
        !           927:              < (1 << (GET_MODE_BITSIZE (GET_MODE (XEXP (to, 0))) - 1))))
        !           928:        SUBST (XEXP (x, 0), XEXP (to, 0));
        !           929:       break;
        !           930: 
        !           931:     case EQ:
        !           932:     case NE:
        !           933:       /* If comparing a subreg against zero, discard the subreg.  */
        !           934:       if (was_replaced[0]
        !           935:          && GET_CODE (to) == SUBREG
        !           936:          && SUBREG_WORD (to) == 0
        !           937:          && XEXP (x, 1) == const0_rtx)
        !           938:        SUBST (XEXP (x, 0), SUBREG_REG (to));
        !           939: 
        !           940:       /* If comparing a ZERO_EXTRACT against zero,
        !           941:         canonicalize to a SIGN_EXTRACT,
        !           942:         since the two are equivalent here.  */
        !           943:       if (was_replaced[0]
        !           944:          && GET_CODE (to) == ZERO_EXTRACT
        !           945:          && XEXP (x, 1) == const0_rtx)
        !           946:        {
        !           947:          if (!undobuf.storage)
        !           948:            undobuf.storage = (char *) oballoc (0);
        !           949:          SUBST (XEXP (x, 0),
        !           950:                 gen_rtx (SIGN_EXTRACT, GET_MODE (to),
        !           951:                          XEXP (to, 0), XEXP (to, 1),
        !           952:                          XEXP (to, 2)));
        !           953:        }
        !           954:       /* If we are putting (ASHIFT 1 x) into (EQ (AND ... y) 0),
        !           955:         arrange to return (EQ (SIGN_EXTRACT y 1 x) 0),
        !           956:         which is what jump-on-bit instructions are written with.  */
        !           957:       else if (XEXP (x, 1) == const0_rtx
        !           958:               && GET_CODE (XEXP (x, 0)) == AND
        !           959:               && (XEXP (XEXP (x, 0), 0) == to
        !           960:                   || XEXP (XEXP (x, 0), 1) == to)
        !           961:               && GET_CODE (to) == ASHIFT
        !           962:               && XEXP (to, 0) == const1_rtx)
        !           963:        {
        !           964:          register rtx y = XEXP (XEXP (x, 0),
        !           965:                                 XEXP (XEXP (x, 0), 0) == to);
        !           966:          if (!undobuf.storage)
        !           967:            undobuf.storage = (char *) oballoc (0);
        !           968:          SUBST (XEXP (x, 0),
        !           969:                 gen_rtx (SIGN_EXTRACT, GET_MODE (to),
        !           970:                          y,
        !           971:                          const1_rtx, XEXP (to, 1)));
        !           972:        }
        !           973: 
        !           974:       break;
        !           975: 
        !           976:     case ZERO_EXTEND:
        !           977:       if (was_replaced[0]
        !           978:          && GET_CODE (to) == ZERO_EXTEND)
        !           979:        SUBST (XEXP (x, 0), XEXP (to, 0));
        !           980:       /* Zero-extending the result of an and with a constant can be done
        !           981:         with a wider and.  */
        !           982:       if (was_replaced[0]
        !           983:          && GET_CODE (to) == AND
        !           984:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !           985:          && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
        !           986:          /* Avoid getting wrong result if the constant has high bits set
        !           987:             that are irrelevant in the narrow mode where it is being used.  */
        !           988:          && 0 == (INTVAL (XEXP (to, 1))
        !           989:                   & ~ GET_MODE_MASK (GET_MODE (to))))
        !           990:        {
        !           991:          if (!undobuf.storage)
        !           992:            undobuf.storage = (char *) oballoc (0);
        !           993:          return gen_rtx (AND, GET_MODE (x),
        !           994:                          gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
        !           995:                          XEXP (to, 1));
        !           996:        } 
        !           997:       /* Change (zero_extend:M (subreg:N (zero_extract:M ...) 0))
        !           998:         to (zero_extract:M ...) if the field extracted fits in mode N.  */
        !           999:       if (GET_CODE (XEXP (x, 0)) == SUBREG
        !          1000:          && GET_CODE (XEXP (XEXP (x, 0), 0)) == ZERO_EXTRACT
        !          1001:          && GET_CODE (XEXP (XEXP (XEXP (x, 0), 0), 1)) == CONST_INT
        !          1002:          && (INTVAL (XEXP (XEXP (XEXP (x, 0), 0), 1))
        !          1003:              <= GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))))
        !          1004:        {
        !          1005:          return XEXP (XEXP (x, 0), 0);
        !          1006:        }
        !          1007:       break;
        !          1008: 
        !          1009:     case SIGN_EXTEND:
        !          1010:       if (was_replaced[0]
        !          1011:          && GET_CODE (to) == SIGN_EXTEND)
        !          1012:        SUBST (XEXP (x, 0), XEXP (to, 0));
        !          1013:       /* Sign-extending the result of an and with a constant can be done
        !          1014:         with a wider and, provided the high bit of the constant is 0.  */
        !          1015:       if (was_replaced[0]
        !          1016:          && GET_CODE (to) == AND
        !          1017:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1018:          && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
        !          1019:          && ((INTVAL (XEXP (to, 1))
        !          1020:               & (-1 << (GET_MODE_BITSIZE (GET_MODE (to)) - 1)))
        !          1021:              == 0))
        !          1022:        {
        !          1023:          if (!undobuf.storage)
        !          1024:            undobuf.storage = (char *) oballoc (0);
        !          1025:          return gen_rtx (AND, GET_MODE (x),
        !          1026:                          gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
        !          1027:                          XEXP (to, 1));
        !          1028:         } 
        !          1029:       break;
        !          1030: 
        !          1031:     case SET:
        !          1032:       /* In (set (zero-extract <x> <n> <y>) (and <foo> <(2**n-1) | anything>))
        !          1033:         the `and' can be deleted.  This can happen when storing a bit
        !          1034:         that came from a set-flag insn followed by masking to one bit.  */
        !          1035:       if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
        !          1036:          && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
        !          1037:          && was_replaced[1]
        !          1038:          && GET_CODE (to) == AND
        !          1039:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1040:          && 0 == (((1 << INTVAL (XEXP (XEXP (x, 0), 1))) - 1)
        !          1041:                   & ~ INTVAL (XEXP (to, 1))))
        !          1042:        {
        !          1043:          SUBST (XEXP (x, 1), XEXP (to, 0));
        !          1044:        } 
        !          1045:       /* In (set (zero-extract <x> <n> <y>)
        !          1046:                 (subreg (and <foo> <(2**n-1) | anything>)))
        !          1047:         the `and' can be deleted.  */
        !          1048:       if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
        !          1049:          && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
        !          1050:          && GET_CODE (XEXP (x, 1)) == SUBREG
        !          1051:          && SUBREG_WORD (XEXP (x, 1)) == 0
        !          1052:          && GET_CODE (SUBREG_REG (XEXP (x, 1))) == AND
        !          1053:          && GET_CODE (XEXP (SUBREG_REG (XEXP (x, 1)), 1)) == CONST_INT
        !          1054:          && 0 == (((1 << INTVAL (XEXP (XEXP (x, 0), 1))) - 1)
        !          1055:                   & ~ INTVAL (XEXP (SUBREG_REG (XEXP (x, 1)), 1))))
        !          1056:        {
        !          1057:          SUBST (SUBREG_REG (XEXP (x, 1)), XEXP (SUBREG_REG (XEXP (x, 1)), 0));
        !          1058:        } 
        !          1059:       /* (set (zero_extract ...) (and/or/xor (zero_extract ...) const)),
        !          1060:         if both zero_extracts have the byte size and position,
        !          1061:         can be changed to avoid the byte extracts.  */
        !          1062:       if ((GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
        !          1063:           || GET_CODE (XEXP (x, 0)) == SIGN_EXTRACT)
        !          1064:          && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
        !          1065:          && (GET_CODE (XEXP (x, 1)) == AND
        !          1066:              || GET_CODE (XEXP (x, 1)) == IOR
        !          1067:              || GET_CODE (XEXP (x, 1)) == XOR)
        !          1068:          && (GET_CODE (XEXP (XEXP (x, 1), 0)) == ZERO_EXTRACT
        !          1069:              || GET_CODE (XEXP (XEXP (x, 1), 0)) == SIGN_EXTRACT)
        !          1070:          && rtx_equal_p (XEXP (XEXP (XEXP (x, 1), 0), 1),
        !          1071:                          XEXP (XEXP (x, 0), 1))
        !          1072:          && rtx_equal_p (XEXP (XEXP (XEXP (x, 1), 0), 2),
        !          1073:                          XEXP (XEXP (x, 0), 2))
        !          1074:          && GET_CODE (XEXP (XEXP (x, 1), 0)) == GET_CODE (XEXP (x, 0))
        !          1075:          && GET_CODE (XEXP (XEXP (x, 1), 1)) == CONST_INT)
        !          1076:        {
        !          1077: #ifdef BITS_BIG_ENDIAN
        !          1078:          int shiftcount
        !          1079:            = GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (x, 0), 0)))
        !          1080:              - INTVAL (XEXP (XEXP (x, 0), 1)) - INTVAL (XEXP (XEXP (x, 0), 2));
        !          1081: #else
        !          1082:          int shiftcount
        !          1083:            = INTVAL (XEXP (XEXP (x, 0), 2));
        !          1084: #endif
        !          1085:          if (!undobuf.storage)
        !          1086:            undobuf.storage = (char *) oballoc (0);
        !          1087:          return
        !          1088:            gen_rtx (SET, VOIDmode,
        !          1089:                     XEXP (XEXP (x, 0), 0),
        !          1090:                     gen_rtx (GET_CODE (XEXP (x, 1)),
        !          1091:                              GET_MODE (XEXP (XEXP (x, 0), 0)),
        !          1092:                              XEXP (XEXP (XEXP (x, 1), 0), 0),
        !          1093:                              gen_rtx (CONST_INT, VOIDmode,
        !          1094:                                       (INTVAL (XEXP (XEXP (x, 1), 1))
        !          1095:                                        << shiftcount)
        !          1096:                                       + (GET_CODE (XEXP (x, 1)) == AND
        !          1097:                                          ? (1 << shiftcount) - 1
        !          1098:                                          : 0))));
        !          1099:        }
        !          1100:       break;
        !          1101: 
        !          1102:     case AND:
        !          1103:       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
        !          1104:        {
        !          1105:          rtx tem = simplify_and_const_int (x, to);
        !          1106:          if (tem)
        !          1107:            return tem;
        !          1108:        }
        !          1109:       break;
        !          1110: 
        !          1111:     case FLOAT:
        !          1112:       /* (float (sign_extend <X>)) = (float <X>).  */
        !          1113:       if (was_replaced[0]
        !          1114:          && GET_CODE (to) == SIGN_EXTEND)
        !          1115:        SUBST (XEXP (x, 0), XEXP (to, 0));
        !          1116:       break;
        !          1117: 
        !          1118:     case ZERO_EXTRACT:
        !          1119:       /* (ZERO_EXTRACT (TRUNCATE x)...)
        !          1120:         can become (ZERO_EXTRACT x ...).  */
        !          1121:       if (was_replaced[0]
        !          1122:          && GET_CODE (to) == TRUNCATE)
        !          1123:        {
        !          1124: #ifdef BITS_BIG_ENDIAN
        !          1125:          if (GET_CODE (XEXP (x, 2)) == CONST_INT)
        !          1126:            {
        !          1127:              if (!undobuf.storage)
        !          1128:                undobuf.storage = (char *) oballoc (0);
        !          1129:              /* On a big-endian machine, must increment the bit-number
        !          1130:                 since sign bit is farther away in the pre-truncated value.  */
        !          1131:              return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
        !          1132:                              XEXP (to, 0),
        !          1133:                              XEXP (x, 1),
        !          1134:                              gen_rtx (CONST_INT, VOIDmode,
        !          1135:                                       (INTVAL (XEXP (x, 2))
        !          1136:                                        + GET_MODE_BITSIZE (GET_MODE (XEXP (to, 0)))
        !          1137:                                        - GET_MODE_BITSIZE (GET_MODE (to)))));
        !          1138:            }
        !          1139: #else
        !          1140:          SUBST (XEXP (x, 0), XEXP (to, 0));
        !          1141: #endif
        !          1142:        }
        !          1143:       /* Extracting a single bit from the result of a shift:
        !          1144:         see which bit it was before the shift and extract that directly.  */
        !          1145:       if (was_replaced[0]
        !          1146:          && (GET_CODE (to) == ASHIFTRT || GET_CODE (to) == LSHIFTRT
        !          1147:              || GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
        !          1148:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1149:          && XEXP (x, 1) == const1_rtx
        !          1150:          && GET_CODE (XEXP (x, 2)) == CONST_INT)
        !          1151:        {
        !          1152:          int shift = INTVAL (XEXP (to, 1));
        !          1153:          int newpos;
        !          1154:          if (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
        !          1155:            shift = - shift;
        !          1156: #ifdef BITS_BIG_ENDIAN
        !          1157:          shift = - shift;
        !          1158: #endif
        !          1159:          newpos = INTVAL (XEXP (x, 2)) + shift;
        !          1160:          if (newpos >= 0 &&
        !          1161:              newpos < GET_MODE_BITSIZE (GET_MODE (to)))
        !          1162:            {
        !          1163:              if (!undobuf.storage)
        !          1164:                undobuf.storage = (char *) oballoc (0);
        !          1165:              return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
        !          1166:                              XEXP (to, 0), const1_rtx,
        !          1167:                              gen_rtx (CONST_INT, VOIDmode, newpos));
        !          1168:            }
        !          1169:        }
        !          1170:       break;
        !          1171: 
        !          1172:     case LSHIFTRT:
        !          1173:     case ASHIFTRT:
        !          1174:     case ROTATE:
        !          1175:     case ROTATERT:
        !          1176: #ifdef SHIFT_COUNT_TRUNCATED
        !          1177:       /* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
        !          1178:         True for all kinds of shifts and also for zero_extend.  */
        !          1179:       if (was_replaced[1]
        !          1180:          && (GET_CODE (to) == SIGN_EXTEND
        !          1181:              || GET_CODE (to) == ZERO_EXTEND)
        !          1182:          && FAKE_EXTEND_SAFE_P (GET_MODE (to), XEXP (to, 0)))
        !          1183:        {
        !          1184:          if (!undobuf.storage)
        !          1185:            undobuf.storage = (char *) oballoc (0);
        !          1186:          SUBST (XEXP (x, 1),
        !          1187:                 /* This is a perverse SUBREG, wider than its base.  */
        !          1188:                 gen_lowpart_for_combine (GET_MODE (to), XEXP (to, 0)));
        !          1189:        }
        !          1190: #endif
        !          1191:       /* Two shifts in a row of same kind
        !          1192:         in same direction with constant counts
        !          1193:         may be combined.  */
        !          1194:       if (was_replaced[0]
        !          1195:          && GET_CODE (to) == GET_CODE (x)
        !          1196:          && GET_CODE (XEXP (x, 1)) == CONST_INT
        !          1197:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1198:          && INTVAL (XEXP (to, 1)) > 0
        !          1199:          && INTVAL (XEXP (x, 1)) > 0
        !          1200:          && (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
        !          1201:              < GET_MODE_BITSIZE (GET_MODE (x))))
        !          1202:        {
        !          1203:          if (!undobuf.storage)
        !          1204:            undobuf.storage = (char *) oballoc (0);
        !          1205:          return gen_rtx (GET_CODE (x), GET_MODE (x),
        !          1206:                          XEXP (to, 0),
        !          1207:                          gen_rtx (CONST_INT, VOIDmode,
        !          1208:                                   INTVAL (XEXP (x, 1))
        !          1209:                                   + INTVAL (XEXP (to, 1))));
        !          1210:        }
        !          1211:       break;
        !          1212: 
        !          1213:     case LSHIFT:
        !          1214:     case ASHIFT:
        !          1215: #ifdef SHIFT_COUNT_TRUNCATED
        !          1216:       /* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
        !          1217:         True for all kinds of shifts and also for zero_extend.  */
        !          1218:       if (was_replaced[1]
        !          1219:          && (GET_CODE (to) == SIGN_EXTEND
        !          1220:              || GET_CODE (to) == ZERO_EXTEND))
        !          1221:        {
        !          1222:          if (!undobuf.storage)
        !          1223:            undobuf.storage = (char *) oballoc (0);
        !          1224:          SUBST (XEXP (x, 1), gen_rtx (SUBREG, GET_MODE (to), XEXP (to, 0), 0));
        !          1225:        }
        !          1226: #endif
        !          1227:       /* (lshift (and (lshiftrt <foo> <X>) <Y>) <X>)
        !          1228:         happens copying between bit fields in similar structures.
        !          1229:         It can be replaced by one and instruction.
        !          1230:         It does not matter whether the shifts are logical or arithmetic.  */
        !          1231:       if (GET_CODE (XEXP (x, 0)) == AND
        !          1232:          && GET_CODE (XEXP (x, 1)) == CONST_INT
        !          1233:          && INTVAL (XEXP (x, 1)) > 0
        !          1234:          && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
        !          1235:          && XEXP (XEXP (x, 0), 0) == to
        !          1236:          && (GET_CODE (to) == LSHIFTRT
        !          1237:              || GET_CODE (to) == ASHIFTRT)
        !          1238: #if 0
        !          1239: /* I now believe this restriction is unnecessary.
        !          1240:    The outer shift will discard those bits in any case, right?  */
        !          1241: 
        !          1242:              /* If inner shift is arithmetic, either it shifts left or
        !          1243:                 the bits it shifts the sign into are zeroed by the and.  */
        !          1244:                  && (INTVAL (XEXP (x, 1)) < 0
        !          1245:                      || ((unsigned) INTVAL (XEXP (XEXP (x, 0), 1))
        !          1246:                          < 1 << (GET_MODE_BITSIZE (GET_MODE (x))
        !          1247:                                  - INTVAL (XEXP (x, 0)))))
        !          1248: #endif
        !          1249:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1250:          && INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
        !          1251:        {
        !          1252:          if (!undobuf.storage)
        !          1253:            undobuf.storage = (char *) oballoc (0);
        !          1254:          /* The constant in the new `and' is <Y> << <X>
        !          1255:             but clear out all bits that don't belong in our mode.  */
        !          1256:          return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
        !          1257:                          gen_rtx (CONST_INT, VOIDmode,
        !          1258:                                   (GET_MODE_MASK (GET_MODE (x))
        !          1259:                                    & ((GET_MODE_MASK (GET_MODE (x))
        !          1260:                                        & INTVAL (XEXP (XEXP (x, 0), 1)))
        !          1261:                                       << INTVAL (XEXP (x, 1))))));
        !          1262:        } 
        !          1263:       /* Two shifts in a row in same direction with constant counts
        !          1264:         may be combined.  */
        !          1265:       if (was_replaced[0]
        !          1266:          && (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
        !          1267:          && GET_CODE (XEXP (x, 1)) == CONST_INT
        !          1268:          && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1269:          && INTVAL (XEXP (to, 1)) > 0
        !          1270:          && INTVAL (XEXP (x, 1)) > 0
        !          1271:          && (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
        !          1272:              < GET_MODE_BITSIZE (GET_MODE (x))))
        !          1273:        {
        !          1274:          if (!undobuf.storage)
        !          1275:            undobuf.storage = (char *) oballoc (0);
        !          1276:          return gen_rtx (GET_CODE (x), GET_MODE (x),
        !          1277:                          XEXP (to, 0),
        !          1278:                          gen_rtx (CONST_INT, VOIDmode,
        !          1279:                                   INTVAL (XEXP (x, 1))
        !          1280:                                   + INTVAL (XEXP (to, 1))));
        !          1281:        }
        !          1282:       /* (ashift (ashiftrt <foo> <X>) <X>)
        !          1283:         (or, on some machines, (ashift (ashift <foo> <-X>) <X>) instead)
        !          1284:         happens if you divide by 2**N and then multiply by 2**N.
        !          1285:         It can be replaced by one `and' instruction.
        !          1286:         It does not matter whether the shifts are logical or arithmetic.  */
        !          1287:       if (GET_CODE (XEXP (x, 1)) == CONST_INT
        !          1288:          && INTVAL (XEXP (x, 1)) > 0
        !          1289:          && was_replaced[0]
        !          1290:          && (((GET_CODE (to) == LSHIFTRT || GET_CODE (to) == ASHIFTRT)
        !          1291:               && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1292:               && INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
        !          1293:              ||
        !          1294:              ((GET_CODE (to) == LSHIFT || GET_CODE (to) == ASHIFT)
        !          1295:               && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1296:               && INTVAL (XEXP (x, 1)) == - INTVAL (XEXP (to, 1)))))
        !          1297:        {
        !          1298:          if (!undobuf.storage)
        !          1299:            undobuf.storage = (char *) oballoc (0);
        !          1300:          /* The constant in the new `and' is -1 << <X>
        !          1301:             but clear out all bits that don't belong in our mode.  */
        !          1302:          return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
        !          1303:                          gen_rtx (CONST_INT, VOIDmode,
        !          1304:                                   (GET_MODE_MASK (GET_MODE (x))
        !          1305:                                    & (GET_MODE_MASK (GET_MODE (x))
        !          1306:                                       << INTVAL (XEXP (x, 1))))));
        !          1307:        } 
        !          1308: 
        !          1309:     }
        !          1310: 
        !          1311:   return x;
        !          1312: }
        !          1313: 
        !          1314: /* This is the AND case of the function subst.  */
        !          1315: 
        !          1316: static rtx
        !          1317: simplify_and_const_int (x, to)
        !          1318:      rtx x, to;
        !          1319: {
        !          1320:   register rtx varop = XEXP (x, 0);
        !          1321:   register int constop = INTVAL (XEXP (x, 1));
        !          1322: 
        !          1323:   /* (and (subreg (and <foo> <constant>) 0) <constant>)
        !          1324:      results from an andsi followed by an andqi,
        !          1325:      which happens frequently when storing bit-fields
        !          1326:      on something whose result comes from an andsi.  */
        !          1327:   if (GET_CODE (varop) == SUBREG
        !          1328:       && XEXP (varop, 0) == to
        !          1329:       && subreg_lowpart_p (varop)
        !          1330:       && GET_CODE (to) == AND
        !          1331:       && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1332:       /* Verify that the result of the outer `and'
        !          1333:         is not affected by any bits not defined in the inner `and'.
        !          1334:         True if the outer mode is narrower, or if the outer constant
        !          1335:         masks to zero all the bits that the inner mode doesn't have.  */
        !          1336:       && (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (to))
        !          1337:          || (constop & ~ GET_MODE_MASK (GET_MODE (to))) == 0))
        !          1338:     {
        !          1339:       if (!undobuf.storage)
        !          1340:        undobuf.storage = (char *) oballoc (0);
        !          1341:       return gen_rtx (AND, GET_MODE (x),
        !          1342:                      gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
        !          1343:                      gen_rtx (CONST_INT, VOIDmode,
        !          1344:                               constop
        !          1345:                               /* Remember that the bits outside that mode
        !          1346:                                  are not being changed, so the effect
        !          1347:                                  is as if they were all 1.  */
        !          1348:                               & INTVAL (XEXP (to, 1))));
        !          1349:     } 
        !          1350:   /* (and:SI (zero_extract:SI ...) <constant>)
        !          1351:      results from an andsi following a byte-fetch on risc machines.
        !          1352:      When the constant includes all bits extracted, eliminate the `and'.  */
        !          1353:   if (GET_CODE (varop) == ZERO_EXTRACT
        !          1354:       && GET_CODE (XEXP (varop, 1)) == CONST_INT
        !          1355:       /* The `and' must not clear any bits that the extract can give.  */
        !          1356:       && (~ constop & ((1 << INTVAL (XEXP (varop, 1))) - 1)) == 0)
        !          1357:     return varop;
        !          1358:   /* (and (zero_extend <foo>) <constant>)
        !          1359:      often results from storing in a bit-field something
        !          1360:      that was calculated as a short.  Replace with a single `and'
        !          1361:      in whose constant all bits not in <foo>'s mode are zero.  */
        !          1362:   if (varop == to
        !          1363:       && GET_CODE (to) == ZERO_EXTEND
        !          1364:       && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
        !          1365:     {
        !          1366:       if (!undobuf.storage)
        !          1367:        undobuf.storage = (char *) oballoc (0);
        !          1368:       return gen_rtx (AND, GET_MODE (x),
        !          1369:                      /* This is a perverse SUBREG, wider than its base.  */
        !          1370:                      gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
        !          1371:                      gen_rtx (CONST_INT, VOIDmode,
        !          1372:                               constop & GET_MODE_MASK (GET_MODE (XEXP (to, 0)))));
        !          1373:     }
        !          1374:   /* (and (sign_extend <foo>) <constant>)
        !          1375:      can be replaced with (and (subreg <foo>) <constant>)
        !          1376:      if <constant> is narrower than <foo>'s mode,
        !          1377:      or with (zero_extend <foo>) if <constant> is a mask for that mode.  */
        !          1378:   if (varop == to
        !          1379:       && GET_CODE (to) == SIGN_EXTEND
        !          1380:       && ((unsigned) constop <= GET_MODE_MASK (GET_MODE (XEXP (to, 0))))
        !          1381:       && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
        !          1382:     {
        !          1383:       if (!undobuf.storage)
        !          1384:        undobuf.storage = (char *) oballoc (0);
        !          1385:       if (constop == GET_MODE_MASK (GET_MODE (XEXP (to, 0))))
        !          1386:        return gen_rtx (ZERO_EXTEND, GET_MODE (x), XEXP (to, 0));
        !          1387:       return gen_rtx (AND, GET_MODE (x),
        !          1388:                      /* This is a perverse SUBREG, wider than its base.  */
        !          1389:                      gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
        !          1390:                      XEXP (x, 1));
        !          1391:     }
        !          1392:   /* (and (and <foo> <constant>) <constant>)
        !          1393:      comes from two and instructions in a row.  */
        !          1394:   if (varop == to
        !          1395:       && GET_CODE (to) == AND
        !          1396:       && GET_CODE (XEXP (to, 1)) == CONST_INT)
        !          1397:     {
        !          1398:       if (!undobuf.storage)
        !          1399:        undobuf.storage = (char *) oballoc (0);
        !          1400:       return gen_rtx (AND, GET_MODE (x),
        !          1401:                      XEXP (to, 0),
        !          1402:                      gen_rtx (CONST_INT, VOIDmode,
        !          1403:                               constop
        !          1404:                               & INTVAL (XEXP (to, 1))));
        !          1405:     }
        !          1406:   /* (and (ashiftrt (ashift FOO N) N) CONST)
        !          1407:      may be simplified to (and FOO CONST) if CONST masks off the bits
        !          1408:      changed by the two shifts.  */
        !          1409:   if (GET_CODE (varop) == ASHIFTRT
        !          1410:       && GET_CODE (XEXP (varop, 1)) == CONST_INT
        !          1411:       && XEXP (varop, 0) == to
        !          1412:       && GET_CODE (to) == ASHIFT
        !          1413:       && GET_CODE (XEXP (to, 1)) == CONST_INT
        !          1414:       && INTVAL (XEXP (varop, 1)) == INTVAL (XEXP (to, 1))
        !          1415:       && ((unsigned) constop >> INTVAL (XEXP (varop, 1))) == 0)
        !          1416:     {
        !          1417:       if (!undobuf.storage)
        !          1418:        undobuf.storage = (char *) oballoc (0);
        !          1419:       /* If CONST is a mask for the low byte,
        !          1420:         change this into a zero-extend instruction
        !          1421:         from just the low byte of FOO.  */
        !          1422:       if (constop == GET_MODE_MASK (QImode))
        !          1423:        {
        !          1424:          rtx temp = gen_lowpart_for_combine (QImode, XEXP (to, 0));
        !          1425:          if (GET_CODE (temp) != CLOBBER)
        !          1426:            return gen_rtx (ZERO_EXTEND, GET_MODE (x), temp);
        !          1427:        }
        !          1428:       return gen_rtx (AND, GET_MODE (x),
        !          1429:                      XEXP (to, 0), XEXP (x, 1));
        !          1430:     }
        !          1431:   /* (and x const) may be converted to (zero_extend (subreg x 0)).  */
        !          1432:   if (constop == GET_MODE_MASK (QImode))
        !          1433:     {
        !          1434:       if (!undobuf.storage)
        !          1435:        undobuf.storage = (char *) oballoc (0);
        !          1436:       return gen_rtx (ZERO_EXTEND, GET_MODE (x),
        !          1437:                      gen_rtx (SUBREG, QImode, varop, 0));
        !          1438:     }
        !          1439:   if (constop == GET_MODE_MASK (HImode))
        !          1440:     {
        !          1441:       if (!undobuf.storage)
        !          1442:        undobuf.storage = (char *) oballoc (0);
        !          1443:       return gen_rtx (ZERO_EXTEND, GET_MODE (x),
        !          1444:                      gen_rtx (SUBREG, HImode, varop, 0));
        !          1445:     }
        !          1446:   /* No simplification applies.  */
        !          1447:   return 0;
        !          1448: }
        !          1449: 
        !          1450: /* Like gen_lowpart but for use by combine.  In combine it is not possible
        !          1451:    to create any new pseudoregs.  However, it is safe to create
        !          1452:    invalid memory addresses, because combine will try to recognize
        !          1453:    them and all they will do is make the combine attempt fail.
        !          1454: 
        !          1455:    If for some reason this cannot do its job, an rtx
        !          1456:    (clobber (const_int 0)) is returned.
        !          1457:    An insn containing that will not be recognized.  */
        !          1458: 
        !          1459: #undef gen_lowpart
        !          1460: 
        !          1461: static rtx
        !          1462: gen_lowpart_for_combine (mode, x)
        !          1463:      enum machine_mode mode;
        !          1464:      register rtx x;
        !          1465: {
        !          1466:   if (GET_CODE (x) == SUBREG || GET_CODE (x) == REG)
        !          1467:     return gen_lowpart (mode, x);
        !          1468:   if (GET_MODE (x) == mode || x->volatil)
        !          1469:     return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
        !          1470:   if (GET_CODE (x) == MEM)
        !          1471:     {
        !          1472:       register int offset = 0;
        !          1473: #ifdef WORDS_BIG_ENDIAN
        !          1474:       offset = (max (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
        !          1475:                - max (GET_MODE_SIZE (mode), UNITS_PER_WORD));
        !          1476: #endif
        !          1477: #ifdef BYTES_BIG_ENDIAN
        !          1478:       /* Adjust the address so that the address-after-the-data
        !          1479:         is unchanged.  */
        !          1480:       offset -= (min (UNITS_PER_WORD, GET_MODE_SIZE (mode))
        !          1481:                 - min (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
        !          1482: #endif
        !          1483:       return gen_rtx (MEM, mode, plus_constant (XEXP (x, 0),
        !          1484:                                                offset));
        !          1485:     }
        !          1486:   else
        !          1487:     return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
        !          1488: }
        !          1489: 
        !          1490: /* After substitution, if the resulting pattern looks like
        !          1491:    (set (cc0) (and ...)) or (set (cc0) (lshiftrt ...)),
        !          1492:    this function is called to simplify the
        !          1493:    pattern into a bit-field operation if possible.  */
        !          1494: 
        !          1495: static void
        !          1496: simplify_set_cc0_and (insn)
        !          1497:      rtx insn;
        !          1498: {
        !          1499:   register rtx value = XEXP (PATTERN (insn), 1);
        !          1500:   register rtx op0 = XEXP (value, 0);
        !          1501:   register rtx op1 = XEXP (value, 1);
        !          1502:   int offset = 0;
        !          1503:   rtx var = 0;
        !          1504:   rtx bitnum = 0;
        !          1505:   int temp;
        !          1506:   int unit;
        !          1507:   rtx newpat;
        !          1508: 
        !          1509:   if (GET_CODE (value) == AND)
        !          1510:     {
        !          1511:       op0 = XEXP (value, 0);
        !          1512:       op1 = XEXP (value, 1);
        !          1513:     }
        !          1514:   else if (GET_CODE (value) == LSHIFTRT)
        !          1515:     {
        !          1516:       /* If there is no AND, but there is a shift that discards
        !          1517:         all but the sign bit, we can pretend that the shift result
        !          1518:         is ANDed with 1.  Otherwise we cannot handle just a shift.  */
        !          1519:       if (GET_CODE (XEXP (value, 1)) == CONST_INT
        !          1520:          && (INTVAL (XEXP (value, 1))
        !          1521:              == GET_MODE_BITSIZE (GET_MODE (value)) - 1))
        !          1522:        {
        !          1523:          op0 = value;
        !          1524:          op1 = const1_rtx;
        !          1525:        }
        !          1526:       else
        !          1527:        return;
        !          1528:     }
        !          1529:   else
        !          1530:     abort ();
        !          1531: 
        !          1532:   /* Look for a constant power of 2 or a shifted 1
        !          1533:      on either side of the AND.  Set VAR to the other side.
        !          1534:      Set BITNUM to the shift count of the 1 (as an rtx).
        !          1535:      Or, if bit number is constant, set OFFSET to the bit number.  */
        !          1536: 
        !          1537:   switch (GET_CODE (op0))
        !          1538:     {
        !          1539:     case CONST_INT:
        !          1540:       temp = exact_log2 (INTVAL (op0));
        !          1541:       if (temp < 0)
        !          1542:        return;
        !          1543:       offset = temp;
        !          1544:       var = op1;
        !          1545:       break;
        !          1546: 
        !          1547:     case ASHIFT:
        !          1548:     case LSHIFT:
        !          1549:       if (XEXP (op0, 0) == const1_rtx)
        !          1550:        {
        !          1551:          bitnum = XEXP (op0, 1);
        !          1552:          var = op1;
        !          1553:        }
        !          1554:     }
        !          1555:   if (var == 0)
        !          1556:     switch (GET_CODE (op1))
        !          1557:       {
        !          1558:       case CONST_INT:
        !          1559:        temp = exact_log2 (INTVAL (op1));
        !          1560:        if (temp < 0)
        !          1561:          return;
        !          1562:        offset = temp;
        !          1563:        var = op0;
        !          1564:        break;
        !          1565: 
        !          1566:       case ASHIFT:
        !          1567:       case LSHIFT:
        !          1568:        if (XEXP (op1, 0) == const1_rtx)
        !          1569:          {
        !          1570:            bitnum = XEXP (op1, 1);
        !          1571:            var = op0;
        !          1572:          }
        !          1573:       }
        !          1574: 
        !          1575:   /* If VAR is 0, we didn't find something recognizable.  */
        !          1576:   if (var == 0)
        !          1577:     return;
        !          1578: 
        !          1579:   if (!undobuf.storage)
        !          1580:     undobuf.storage = (char *) oballoc (0);
        !          1581: 
        !          1582:   /* If the bit position is currently exactly 0,
        !          1583:      extract a right-shift from the variable portion.  */
        !          1584:   if (offset == 0
        !          1585:       && (GET_CODE (var) == ASHIFTRT || GET_CODE (var) == LSHIFTRT))
        !          1586:     {
        !          1587:       bitnum = XEXP (var, 1);
        !          1588:       var = XEXP (var, 0);
        !          1589:     }
        !          1590: 
        !          1591:   if (GET_CODE (var) == SUBREG && SUBREG_WORD (var) == 0)
        !          1592:     var = SUBREG_REG (var);
        !          1593: 
        !          1594:   /* Note that BITNUM and OFFSET are always little-endian thru here
        !          1595:      even on a big-endian machine.  */
        !          1596: 
        !          1597: #ifdef BITS_BIG_ENDIAN
        !          1598:   unit = GET_MODE_BITSIZE (GET_MODE (var)) - 1;
        !          1599: 
        !          1600:   if (bitnum != 0)
        !          1601:     bitnum = gen_rtx (MINUS, SImode,
        !          1602:                      gen_rtx (CONST_INT, VOIDmode, unit), bitnum);
        !          1603:   else
        !          1604:     offset = unit - offset;
        !          1605: #endif
        !          1606: 
        !          1607:   if (bitnum == 0)
        !          1608:     bitnum = gen_rtx (CONST_INT, VOIDmode, offset);
        !          1609: 
        !          1610:   newpat = gen_rtx (SET, VOIDmode, cc0_rtx,
        !          1611:                    gen_rtx (ZERO_EXTRACT, VOIDmode, var, const1_rtx, bitnum));
        !          1612:   if (recog (newpat, insn) >= 0)
        !          1613:     {
        !          1614:       if (undobuf.num_undo < MAX_UNDO)
        !          1615:        {
        !          1616:          undobuf.undo[undobuf.num_undo].where = &XEXP (PATTERN (insn), 1);
        !          1617:          undobuf.undo[undobuf.num_undo].old_contents = value;
        !          1618:          XEXP (PATTERN (insn), 1) = XEXP (newpat, 1);
        !          1619:        }
        !          1620:       undobuf.num_undo++;
        !          1621:     }
        !          1622: }
        !          1623: 
        !          1624: /* Update the records of when each REG was most recently set or killed
        !          1625:    for the things done by INSN.  This is the last thing done in processing
        !          1626:    INSN in the combiner loop.
        !          1627: 
        !          1628:    We update reg_last_set, reg_last_death, and also the similar information
        !          1629:    mem_last_set (which insn most recently modified memory)
        !          1630:    and last_call_cuid (which insn was the most recent subroutine call).  */
        !          1631: 
        !          1632: static void
        !          1633: record_dead_and_set_regs (insn)
        !          1634:      rtx insn;
        !          1635: {
        !          1636:   register rtx link;
        !          1637:   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
        !          1638:     {
        !          1639:       if (REG_NOTE_KIND (link) == REG_DEAD)
        !          1640:        reg_last_death[REGNO (XEXP (link, 0))] = insn;
        !          1641:       else if (REG_NOTE_KIND (link) == REG_INC)
        !          1642:        reg_last_set[REGNO (XEXP (link, 0))] = insn;
        !          1643:     }
        !          1644: 
        !          1645:   if (GET_CODE (insn) == CALL_INSN)
        !          1646:     last_call_cuid = mem_last_set = INSN_CUID (insn);
        !          1647: 
        !          1648:   if (GET_CODE (PATTERN (insn)) == PARALLEL)
        !          1649:     {
        !          1650:       register int i;
        !          1651:       for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
        !          1652:        {
        !          1653:          register rtx elt = XVECEXP (PATTERN (insn), 0, i);
        !          1654:          register enum rtx_code code = GET_CODE (elt);
        !          1655:          if (code == SET || code == CLOBBER)
        !          1656:            {
        !          1657:              if (GET_CODE (XEXP (elt, 0)) == REG)
        !          1658:                reg_last_set[REGNO (XEXP (elt, 0))] = insn;
        !          1659:              if (GET_CODE (XEXP (elt, 0)) == SUBREG
        !          1660:                  && GET_CODE (SUBREG_REG (XEXP (elt, 0))) == REG)
        !          1661:                reg_last_set[REGNO (SUBREG_REG (XEXP (elt, 0)))] = insn;
        !          1662:              else if (GET_CODE (XEXP (elt, 0)) == MEM)
        !          1663:                mem_last_set = INSN_CUID (insn);
        !          1664:            }
        !          1665:        }
        !          1666:     }
        !          1667:   else if (GET_CODE (PATTERN (insn)) == SET
        !          1668:           || GET_CODE (PATTERN (insn)) == CLOBBER)
        !          1669:     {
        !          1670:       register rtx x = XEXP (PATTERN (insn), 0);
        !          1671:       if (GET_CODE (x) == REG)
        !          1672:        reg_last_set[REGNO (x)] = insn;
        !          1673:       if (GET_CODE (x) == SUBREG
        !          1674:          && GET_CODE (SUBREG_REG (x)) == REG)
        !          1675:        reg_last_set[REGNO (SUBREG_REG (x))] = insn;
        !          1676:       else if (GET_CODE (x) == MEM)
        !          1677:        mem_last_set = INSN_CUID (insn);
        !          1678:     }
        !          1679: }
        !          1680: 
        !          1681: /* Return nonzero if expression X refers to a REG or to memory
        !          1682:    that is set in an instruction more recent than FROM_CUID.  */
        !          1683: 
        !          1684: static int
        !          1685: use_crosses_set_p (x, from_cuid)
        !          1686:      register rtx x;
        !          1687:      int from_cuid;
        !          1688: {
        !          1689:   register char *fmt;
        !          1690:   register int i;
        !          1691:   register enum rtx_code code = GET_CODE (x);
        !          1692: 
        !          1693:   if (code == REG)
        !          1694:     {
        !          1695:       register int regno = REGNO (x);
        !          1696:       return (reg_last_set[regno]
        !          1697:              && INSN_CUID (reg_last_set[regno]) > from_cuid);
        !          1698:     }
        !          1699: 
        !          1700:   if (code == MEM && mem_last_set > from_cuid)
        !          1701:     return 1;
        !          1702: 
        !          1703:   fmt = GET_RTX_FORMAT (code);
        !          1704: 
        !          1705:   for (i = GET_RTX_LENGTH (code); i >= 0; i--)
        !          1706:     {
        !          1707:       if (fmt[i] == 'E')
        !          1708:        {
        !          1709:          register int j;
        !          1710:          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
        !          1711:            if (use_crosses_set_p (XVECEXP (x, i, j), from_cuid))
        !          1712:              return 1;
        !          1713:        }
        !          1714:       else if (fmt[i] == 'e'
        !          1715:               && use_crosses_set_p (XEXP (x, i), from_cuid))
        !          1716:        return 1;
        !          1717:     }
        !          1718:   return 0;
        !          1719: }
        !          1720: 
        !          1721: /* Return nonzero if reg REGNO is marked as dying in INSN.  */
        !          1722: 
        !          1723: int
        !          1724: regno_dead_p (regno, insn)
        !          1725:      int regno;
        !          1726:      rtx insn;
        !          1727: {
        !          1728:   register rtx link;
        !          1729: 
        !          1730:   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
        !          1731:     if ((REG_NOTE_KIND (link) == REG_DEAD
        !          1732:         || REG_NOTE_KIND (link) == REG_INC)
        !          1733:        && REGNO (XEXP (link, 0)) == regno)
        !          1734:       return 1;
        !          1735: 
        !          1736:   return 0;
        !          1737: }
        !          1738: 
        !          1739: /* Remove register number REGNO from the dead registers list of INSN.  */
        !          1740: 
        !          1741: static void
        !          1742: remove_death (regno, insn)
        !          1743:      int regno;
        !          1744:      rtx insn;
        !          1745: {
        !          1746:   register rtx link, next;
        !          1747:   while ((link = REG_NOTES (insn))
        !          1748:         && REG_NOTE_KIND (link) == REG_DEAD
        !          1749:         && REGNO (XEXP (link, 0)) == regno)
        !          1750:     REG_NOTES (insn) = XEXP (link, 1);
        !          1751: 
        !          1752:   if (link)
        !          1753:     while (next = XEXP (link, 1))
        !          1754:       {
        !          1755:        if (REG_NOTE_KIND (next) == REG_DEAD
        !          1756:            && REGNO (XEXP (next, 0)) == regno)
        !          1757:          XEXP (link, 1) = XEXP (next, 1);
        !          1758:        else
        !          1759:          link = next;
        !          1760:       }
        !          1761: }
        !          1762: 
        !          1763: /* Return nonzero if J is the first insn following I,
        !          1764:    not counting labels, line numbers, etc.
        !          1765:    We assume that J follows I.  */
        !          1766: 
        !          1767: static int
        !          1768: adjacent_insns_p (i, j)
        !          1769:      rtx i, j;
        !          1770: {
        !          1771:   register rtx insn;
        !          1772:   for (insn = NEXT_INSN (i); insn != j; insn = NEXT_INSN (insn))
        !          1773:     if (GET_CODE (insn) == INSN
        !          1774:        || GET_CODE (insn) == CALL_INSN
        !          1775:        || GET_CODE (insn) == JUMP_INSN)
        !          1776:       return 0;
        !          1777:   return 1;
        !          1778: }
        !          1779: 
        !          1780: /* Concatenate the list of logical links of OINSN
        !          1781:    into INSN's list of logical links.
        !          1782:    Modifies OINSN destructively.
        !          1783: 
        !          1784:    If ALL_LINKS is nonzero, move all the links that OINSN has.
        !          1785:    Otherwise, move only those that point to insns that set regs
        !          1786:    that die in the insn OINSN.
        !          1787:    Other links are clobbered so that they are no longer effective.  */
        !          1788: 
        !          1789: static void
        !          1790: add_links (insn, oinsn, all_links)
        !          1791:      rtx insn, oinsn;
        !          1792:      int all_links;
        !          1793: {
        !          1794:   register rtx links = LOG_LINKS (oinsn);
        !          1795:   if (! all_links)
        !          1796:     {
        !          1797:       rtx tail;
        !          1798:       for (tail = links; tail; tail = XEXP (tail, 1))
        !          1799:        {
        !          1800:          rtx target = XEXP (tail, 0);
        !          1801:          if (GET_CODE (target) != INSN
        !          1802:              || GET_CODE (PATTERN (target)) != SET
        !          1803:              || GET_CODE (SET_DEST (PATTERN (target))) != REG
        !          1804:              || ! dead_or_set_p (oinsn, SET_DEST (PATTERN (target))))
        !          1805:            /* OINSN is going to become a NOTE 
        !          1806:               so a link pointing there will have no effect.  */
        !          1807:            XEXP (tail, 0) = oinsn;
        !          1808:        }
        !          1809:     }
        !          1810:   if (LOG_LINKS (insn) == 0)
        !          1811:     LOG_LINKS (insn) = links;
        !          1812:   else
        !          1813:     {
        !          1814:       register rtx next, prev = LOG_LINKS (insn);
        !          1815:       while (next = XEXP (prev, 1))
        !          1816:        prev = next;
        !          1817:       XEXP (prev, 1) = links;
        !          1818:     }
        !          1819: }
        !          1820: 
        !          1821: /* Concatenate the any elements of the list of reg-notes INCS
        !          1822:    which are of type REG_INC
        !          1823:    into INSN's list of reg-notes.  */
        !          1824: 
        !          1825: static void
        !          1826: add_incs (insn, incs)
        !          1827:      rtx insn, incs;
        !          1828: {
        !          1829:   register rtx tail;
        !          1830: 
        !          1831:   for (tail = incs; tail; tail = XEXP (tail, 1))
        !          1832:     if (REG_NOTE_KIND (tail) == REG_INC)
        !          1833:       REG_NOTES (insn)
        !          1834:        = gen_rtx (EXPR_LIST, REG_INC, XEXP (tail, 0), REG_NOTES (insn));
        !          1835: }
        !          1836: 
        !          1837: /* For each register (hardware or pseudo) used within expression X,
        !          1838:    if its death is in an instruction with cuid
        !          1839:    between FROM_CUID (inclusive) and TO_INSN (exclusive),
        !          1840:    mark it as dead in TO_INSN instead.
        !          1841: 
        !          1842:    This is done when X is being merged by combination into TO_INSN.  */
        !          1843: 
        !          1844: static void
        !          1845: move_deaths (x, from_cuid, to_insn)
        !          1846:      rtx x;
        !          1847:      int from_cuid;
        !          1848:      rtx to_insn;
        !          1849: {
        !          1850:   register char *fmt;
        !          1851:   register int len, i;
        !          1852:   register enum rtx_code code = GET_CODE (x);
        !          1853: 
        !          1854:   if (code == REG)
        !          1855:     {
        !          1856:       register rtx where_dead = reg_last_death[REGNO (x)];
        !          1857: 
        !          1858:       if (where_dead && INSN_CUID (where_dead) >= from_cuid
        !          1859:          && INSN_CUID (where_dead) < INSN_CUID (to_insn))
        !          1860:        {
        !          1861:          remove_death (REGNO (x), reg_last_death[REGNO (x)]);
        !          1862:          if (! dead_or_set_p (to_insn, x))
        !          1863:            REG_NOTES (to_insn)
        !          1864:              = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (to_insn));
        !          1865:        }
        !          1866:       return;
        !          1867:     }
        !          1868: 
        !          1869:   len = GET_RTX_LENGTH (code);
        !          1870:   fmt = GET_RTX_FORMAT (code);
        !          1871: 
        !          1872:   for (i = 0; i < len; i++)
        !          1873:     {
        !          1874:       if (fmt[i] == 'E')
        !          1875:        {
        !          1876:          register int j;
        !          1877:          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
        !          1878:            move_deaths (XVECEXP (x, i, j), from_cuid, to_insn);
        !          1879:        }
        !          1880:       else if (fmt[i] == 'e')
        !          1881:        move_deaths (XEXP (x, i), from_cuid, to_insn);
        !          1882:     }
        !          1883: }
        !          1884: 
        !          1885: void
        !          1886: dump_combine_stats (file)
        !          1887:      char *file;
        !          1888: {
        !          1889:   fprintf
        !          1890:     (file,
        !          1891:      ";; Combiner statistics: %d attempts, %d substitutions (%d requiring new space),\n;; %d successes.\n\n"
        !          1892:      , combine_attempts, combine_merges, combine_extras, combine_successes);
        !          1893: }
        !          1894: 
        !          1895: void
        !          1896: dump_combine_total_stats (file)
        !          1897:      char *file;
        !          1898: {
        !          1899:   fprintf
        !          1900:     (file,
        !          1901:      "\n;; Combiner totals: %d attempts, %d substitutions (%d requiring new space),\n;; %d successes.\n",
        !          1902:      total_attempts, total_merges, total_extras, total_successes);
        !          1903: }

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