Return to flow.c CVS log

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

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

1.1     ! root        1: /* Data flow analysis 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 file contains the data flow analysis pass of the compiler.
        !            23:    It computes data flow information
        !            24:    which tells combine_instructions which insns to consider combining
        !            25:    and controls register allocation.
        !            26: 
        !            27:    Additional data flow information that is too bulky to record
        !            28:    is generated during the analysis, and is used at that time to
        !            29:    create autoincrement and autodecrement addressing.
        !            30: 
        !            31:    The first step is dividing the function into basic blocks.
        !            32:    find_basic_blocks does this.  Then life_analysis determines
        !            33:    where each register is live and where it is dead.
        !            34: 
        !            35:    ** find_basic_blocks **
        !            36: 
        !            37:    find_basic_blocks divides the current function's rtl
        !            38:    into basic blocks.  It records the beginnings and ends of the
        !            39:    basic blocks in the vectors basic_block_head and basic_block_end,
        !            40:    and the number of blocks in n_basic_blocks.
        !            41: 
        !            42:    find_basic_blocks also finds any unreachable loops
        !            43:    and deletes them.
        !            44: 
        !            45:    ** life_analysis **
        !            46: 
        !            47:    life_analysis is called immediately after find_basic_blocks.
        !            48:    It uses the basic block information to determine where each
        !            49:    hard or pseudo register is live.
        !            50: 
        !            51:    ** live-register info **
        !            52: 
        !            53:    The information about where each register is live is in two parts:
        !            54:    the REG_NOTES of insns, and the vector basic_block_live_at_start.
        !            55: 
        !            56:    basic_block_live_at_start has an element for each basic block,
        !            57:    and the element is a bit-vector with a bit for each hard or pseudo
        !            58:    register.  The bit is 1 if the register is live at the beginning
        !            59:    of the basic block.
        !            60: 
        !            61:    To each insn's REG_NOTES is added an element for each register
        !            62:    that is live before the insn or set by the insn, but is dead
        !            63:    after the insn.
        !            64: 
        !            65:    To determine which registers are live after any insn, one can
        !            66:    start from the beginning of the basic block and scan insns, noting
        !            67:    which registers are set by each insn and which die there.
        !            68: 
        !            69:    ** Other actions of life_analysis **
        !            70: 
        !            71:    life_analysis sets up the LOG_LINKS fields of insns because the
        !            72:    information needed to do so is readily available.
        !            73: 
        !            74:    life_analysis deletes insns whose only effect is to store a value
        !            75:    that is never used.
        !            76: 
        !            77:    life_analysis notices cases where a reference to a register as
        !            78:    a memory address can be combined with a preceding or following
        !            79:    incrementation or decrementation of the register.  The separate
        !            80:    instruction to increment or decrement is deleted and the address
        !            81:    is changed to a POST_INC or similar rtx.
        !            82: 
        !            83:    Each time an incrementing or decrementing address is created,
        !            84:    a REG_INC element is added to the insn's REG_NOTES list.
        !            85: 
        !            86:    life_analysis fills in certain vectors containing information about
        !            87:    register usage: reg_n_refs, reg_n_deaths, reg_n_sets,
        !            88:    reg_live_length, reg_crosses_call and reg_basic_block.  */
        !            89: 
        !            90: #include <stdio.h>
        !            91: #include "config.h"
        !            92: #include "rtl.h"
        !            93: #include "basic-block.h"
        !            94: #include "regs.h"
        !            95: #include "hard-reg-set.h"
        !            96: #include "flags.h"
        !            97: 
        !            98: /* Get the basic block number of an insn.
        !            99:    This info should not be expected to remain available
        !           100:    after the end of life_analysis.  */
        !           101: 
        !           102: #define BLOCK_NUM(INSN)  uid_block_number[INSN_UID (INSN)]
        !           103: 
        !           104: /* This is where the BLOCK_NUM values are really stored.
        !           105:    This is set up by find_basic_blocks and used there and in life_analysis,
        !           106:    and then freed.  */
        !           107: 
        !           108: static short *uid_block_number;
        !           109: 
        !           110: /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile.  */
        !           111: 
        !           112: #define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)]
        !           113: static char *uid_volatile;
        !           114: 
        !           115: /* Number of basic blocks in the current function.  */
        !           116: 
        !           117: int n_basic_blocks;
        !           118: 
        !           119: /* Maximum register number used in this function, plus one.  */
        !           120: 
        !           121: int max_regno;
        !           122: 
        !           123: /* Indexed by n, gives number of basic block that  (REG n) is used in.
        !           124:    Or gives -2 if (REG n) is used in more than one basic block.
        !           125:    Or -1 if it has not yet been seen so no basic block is known.
        !           126:    This information remains valid for the rest of the compilation
        !           127:    of the current function; it is used to control register allocation.  */
        !           128: 
        !           129: short *reg_basic_block;
        !           130: 
        !           131: /* Indexed by n, gives number of times (REG n) is used or set, each
        !           132:    weighted by its loop-depth.
        !           133:    This information remains valid for the rest of the compilation
        !           134:    of the current function; it is used to control register allocation.  */
        !           135: 
        !           136: short *reg_n_refs;
        !           137: 
        !           138: /* Indexed by n, gives number of times (REG n) is set.
        !           139:    This information remains valid for the rest of the compilation
        !           140:    of the current function; it is used to control register allocation.  */
        !           141: 
        !           142: short *reg_n_sets;
        !           143: 
        !           144: /* Indexed by N, gives number of places register N dies.
        !           145:    This information remains valid for the rest of the compilation
        !           146:    of the current function; it is used to control register allocation.  */
        !           147: 
        !           148: short *reg_n_deaths;
        !           149: 
        !           150: /* Indexed by N, gives 1 if that reg is live across any CALL_INSNs.
        !           151:    This information remains valid for the rest of the compilation
        !           152:    of the current function; it is used to control register allocation.  */
        !           153: 
        !           154: char *reg_crosses_call;
        !           155: 
        !           156: /* Total number of instructions at which (REG n) is live.
        !           157:    The larger this is, the less priority (REG n) gets for
        !           158:    allocation in a real register.
        !           159:    This information remains valid for the rest of the compilation
        !           160:    of the current function; it is used to control register allocation.
        !           161: 
        !           162:    local-alloc.c may alter this number to change the priority.
        !           163: 
        !           164:    Negative values are special.
        !           165:    -1 is used to mark a pseudo reg which has a constant or memory equivalent
        !           166:    and is used infrequently enough that it should not get a hard register.
        !           167:    -2 is used to mark a pseudo reg for a parameter, when a frame pointer
        !           168:    is not required.  global-alloc.c makes an allocno for this but does
        !           169:    not try to assign a hard register to it.  */
        !           170: 
        !           171: int *reg_live_length;
        !           172: 
        !           173: /* Element N is the next insn that uses (hard or pseudo) register number N
        !           174:    within the current basic block; or zero, if there is no such insn.
        !           175:    This is valid only during the final backward scan in propagate_block.  */
        !           176: 
        !           177: static rtx *reg_next_use;
        !           178: 
        !           179: /* Size of a regset for the current function,
        !           180:    in (1) bytes and (2) elements.  */
        !           181: 
        !           182: int regset_bytes;
        !           183: int regset_size;
        !           184: 
        !           185: /* Element N is first insn in basic block N.
        !           186:    This info lasts until we finish compiling the function.  */
        !           187: 
        !           188: rtx *basic_block_head;
        !           189: 
        !           190: /* Element N is last insn in basic block N.
        !           191:    This info lasts until we finish compiling the function.  */
        !           192: 
        !           193: rtx *basic_block_end;
        !           194: 
        !           195: /* Element N is a regset describing the registers live
        !           196:    at the start of basic block N.
        !           197:    This info lasts until we finish compiling the function.  */
        !           198: 
        !           199: regset *basic_block_live_at_start;
        !           200: 
        !           201: /* Regset of regs live when calls to `setjmp'-like functions happen.  */
        !           202: 
        !           203: regset regs_live_at_setjmp;
        !           204: 
        !           205: /* Element N is nonzero if control can drop into basic block N
        !           206:    from the preceding basic block.  Freed after life_analysis.  */
        !           207: 
        !           208: static char *basic_block_drops_in;
        !           209: 
        !           210: /* Element N is depth within loops of basic block number N.
        !           211:    Freed after life_analysis.  */
        !           212: 
        !           213: static short *basic_block_loop_depth;
        !           214: 
        !           215: /* Element N nonzero if basic block N can actually be reached.
        !           216:    Vector exists only during find_basic_blocks.  */
        !           217: 
        !           218: static char *block_live_static;
        !           219: 
        !           220: /* Depth within loops of basic block being scanned for lifetime analysis,
        !           221:    plus one.  This is the weight attached to references to registers.  */
        !           222: 
        !           223: static int loop_depth;
        !           224: 
        !           225: /* Define AUTO_INC_DEC if machine has any kind of incrementing
        !           226:    or decrementing addressing.  */
        !           227: 
        !           228: #ifdef HAVE_PRE_DECREMENT
        !           229: #define AUTO_INC_DEC
        !           230: #endif
        !           231: 
        !           232: #ifdef HAVE_PRE_INCREMENT
        !           233: #define AUTO_INC_DEC
        !           234: #endif
        !           235: 
        !           236: #ifdef HAVE_POST_DECREMENT
        !           237: #define AUTO_INC_DEC
        !           238: #endif
        !           239: 
        !           240: #ifdef HAVE_POST_INCREMENT
        !           241: #define AUTO_INC_DEC
        !           242: #endif
        !           243: 
        !           244: /* Forward declarations */
        !           245: static void find_basic_blocks ();
        !           246: static void life_analysis ();
        !           247: static void mark_label_ref ();
        !           248: void allocate_for_life_analysis (); /* Used also in stupid_life_analysis */
        !           249: static void init_regset_vector ();
        !           250: static void propagate_block ();
        !           251: static void mark_set_regs ();
        !           252: static void mark_used_regs ();
        !           253: static int insn_dead_p ();
        !           254: static int try_pre_increment ();
        !           255: static int try_pre_increment_1 ();
        !           256: static rtx find_use_as_address ();
        !           257: static int volatile_refs_p ();
        !           258: void dump_flow_info ();
        !           259: 
        !           260: /* Find basic blocks of the current function and perform data flow analysis.
        !           261:    F is the first insn of the function and NREGS the number of register numbers
        !           262:    in use.  */
        !           263: 
        !           264: void
        !           265: flow_analysis (f, nregs, file)
        !           266:      rtx f;
        !           267:      int nregs;
        !           268:      FILE *file;
        !           269: {
        !           270:   register rtx insn;
        !           271:   register int i;
        !           272:   register int max_uid = 0;
        !           273: 
        !           274:   /* Count the basic blocks.  Also find maximum insn uid value used.  */
        !           275: 
        !           276:   {
        !           277:     register RTX_CODE prev_code = JUMP_INSN;
        !           278:     register RTX_CODE code;
        !           279: 
        !           280:     for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           281:       {
        !           282:        code = GET_CODE (insn);
        !           283:        if (INSN_UID (insn) > max_uid)
        !           284:          max_uid = INSN_UID (insn);
        !           285:        if (code == CODE_LABEL
        !           286:            || (prev_code != INSN && prev_code != CALL_INSN
        !           287:                && prev_code != CODE_LABEL
        !           288:                && (code == INSN || code == CALL_INSN || code == JUMP_INSN)))
        !           289:          i++;
        !           290:        if (code != NOTE)
        !           291:          prev_code = code;
        !           292:       }
        !           293:   }
        !           294: 
        !           295:   /* Allocate some tables that last till end of compiling this function
        !           296:      and some needed only in find_basic_blocks and life_analysis.  */
        !           297: 
        !           298:   n_basic_blocks = i;
        !           299:   basic_block_head = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
        !           300:   basic_block_end = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
        !           301:   basic_block_drops_in = (char *) alloca (n_basic_blocks);
        !           302:   basic_block_loop_depth = (short *) alloca (n_basic_blocks * sizeof (short));
        !           303:   uid_block_number = (short *) alloca ((max_uid + 1) * sizeof (short));
        !           304:   uid_volatile = (char *) alloca (max_uid + 1);
        !           305:   bzero (uid_volatile, max_uid + 1);
        !           306: 
        !           307:   find_basic_blocks (f);
        !           308:   life_analysis (f, nregs);
        !           309:   if (file)
        !           310:     dump_flow_info (file);
        !           311: 
        !           312:   basic_block_drops_in = 0;
        !           313:   uid_block_number = 0;
        !           314:   basic_block_loop_depth = 0;
        !           315: }
        !           316: 
        !           317: /* Find all basic blocks of the function whose first insn is F.
        !           318:    Store the correct data in the tables that describe the basic blocks,
        !           319:    set up the chains of references for each CODE_LABEL, and
        !           320:    delete any entire basic blocks that cannot be reached.  */
        !           321: 
        !           322: static void
        !           323: find_basic_blocks (f)
        !           324:      rtx f;
        !           325: {
        !           326:   register rtx insn;
        !           327:   register int i;
        !           328: 
        !           329:   /* Initialize the ref chain of each label to 0.  */
        !           330:   /* Record where all the blocks start and end and their depth in loops.  */
        !           331:   /* For each insn, record the block it is in.  */
        !           332: 
        !           333:   {
        !           334:     register RTX_CODE prev_code = JUMP_INSN;
        !           335:     register RTX_CODE code;
        !           336:     int depth = 1;
        !           337: 
        !           338:     for (insn = f, i = -1; insn; insn = NEXT_INSN (insn))
        !           339:       {
        !           340:        code = GET_CODE (insn);
        !           341:        if (code == NOTE)
        !           342:          {
        !           343:            if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
        !           344:              depth++;
        !           345:            else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
        !           346:              depth--;
        !           347:          }
        !           348:        else if (code == CODE_LABEL
        !           349:                 || (prev_code != INSN && prev_code != CALL_INSN
        !           350:                     && prev_code != CODE_LABEL
        !           351:                     && (code == INSN || code == CALL_INSN || code == JUMP_INSN)))
        !           352:          {
        !           353:            basic_block_head[++i] = insn;
        !           354:            basic_block_end[i] = insn;
        !           355:            basic_block_loop_depth[i] = depth;
        !           356:            if (code == CODE_LABEL)
        !           357:              LABEL_REFS (insn) = insn;
        !           358:          }
        !           359:        else if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
        !           360:          basic_block_end[i] = insn;
        !           361:        BLOCK_NUM (insn) = i;
        !           362:        if (code != NOTE)
        !           363:          prev_code = code;
        !           364:       }
        !           365:   }
        !           366: 
        !           367:   /* Record which basic blocks control can drop in to.  */
        !           368: 
        !           369:   {
        !           370:     register int i;
        !           371:     for (i = 0; i < n_basic_blocks; i++)
        !           372:       {
        !           373:        register rtx insn = PREV_INSN (basic_block_head[i]);
        !           374:        /* TEMP1 is used to avoid a bug in Sequent's compiler.  */
        !           375:        register int temp1;
        !           376:        while (insn && GET_CODE (insn) == NOTE)
        !           377:          insn = PREV_INSN (insn);
        !           378:        temp1 = insn && GET_CODE (insn) != BARRIER;
        !           379:        basic_block_drops_in[i] = temp1;
        !           380:       }
        !           381:   }
        !           382: 
        !           383:   /* Now find which basic blocks can actually be reached
        !           384:      and put all jump insns' LABEL_REFS onto the ref-chains
        !           385:      of their target labels.  */
        !           386: 
        !           387:   if (n_basic_blocks > 0)
        !           388:     {
        !           389:       register char *block_live = (char *) alloca (n_basic_blocks);
        !           390:       register char *block_marked = (char *) alloca (n_basic_blocks);
        !           391:       int something_marked = 1;
        !           392: 
        !           393:       /* Initialize with just block 0 reachable and no blocks marked.  */
        !           394: 
        !           395:       bzero (block_live, n_basic_blocks);
        !           396:       bzero (block_marked, n_basic_blocks);
        !           397:       block_live[0] = 1;
        !           398:       block_live_static = block_live;
        !           399: 
        !           400:       /* Pass over all blocks, marking each block that is reachable
        !           401:         and has not yet been marked.
        !           402:         Keep doing this until, in one pass, no blocks have been marked.
        !           403:         Then blocks_live and blocks_marked are identical and correct.
        !           404:         In addition, all jumps actually reachable have been marked.  */
        !           405: 
        !           406:       while (something_marked)
        !           407:        {
        !           408:          something_marked = 0;
        !           409:          for (i = 0; i < n_basic_blocks; i++)
        !           410:            if (block_live[i] && !block_marked[i])
        !           411:              {
        !           412:                block_marked[i] = 1;
        !           413:                something_marked = 1;
        !           414:                if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
        !           415:                  block_live[i + 1] = 1;
        !           416:                insn = basic_block_end[i];
        !           417:                if (GET_CODE (insn) == JUMP_INSN)
        !           418:                  mark_label_ref (PATTERN (insn), insn, 0);
        !           419:              }
        !           420:        }
        !           421: 
        !           422:       /* Now delete the code for any basic blocks that can't be reached.
        !           423:         They can occur because jump_optimize does not recognize
        !           424:         unreachable loops as unreachable.  */
        !           425: 
        !           426:       for (i = 0; i < n_basic_blocks; i++)
        !           427:        if (!block_live[i])
        !           428:          {
        !           429:            insn = basic_block_head[i];
        !           430:            while (1)
        !           431:              {
        !           432:                if (GET_CODE (insn) == BARRIER)
        !           433:                  abort ();
        !           434:                if (GET_CODE (insn) != NOTE)
        !           435:                  {
        !           436:                    PUT_CODE (insn, NOTE);
        !           437:                    NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
        !           438:                    NOTE_SOURCE_FILE (insn) = 0;
        !           439:                  }
        !           440:                if (insn == basic_block_end[i])
        !           441:                  {
        !           442:                    /* BARRIERs are between basic blocks, not part of one.
        !           443:                       Delete a BARRIER if the preceding jump is deleted.
        !           444:                       We cannot alter a BARRIER into a NOTE
        !           445:                       because it is too short; but we can really delete
        !           446:                       it because it is not part of a basic block.  */
        !           447:                    if (NEXT_INSN (insn) != 0
        !           448:                        && GET_CODE (NEXT_INSN (insn)) == BARRIER)
        !           449:                      delete_insn (NEXT_INSN (insn));
        !           450:                    break;
        !           451:                  }
        !           452:                insn = NEXT_INSN (insn);
        !           453:              }
        !           454:            /* Each time we delete some basic blocks,
        !           455:               see if there is a jump around them that is
        !           456:               being turned into a no-op.  If so, delete it.  */
        !           457: 
        !           458:            if (block_live[i - 1])
        !           459:              {
        !           460:                register int j;
        !           461:                for (j = i; j < n_basic_blocks; j++)
        !           462:                  if (block_live[j])
        !           463:                    {
        !           464:                      insn = basic_block_end[i - 1];
        !           465:                      if (GET_CODE (insn) == JUMP_INSN
        !           466:                          && JUMP_LABEL (insn) != 0
        !           467:                          && INSN_UID (JUMP_LABEL (insn)) != 0
        !           468:                          && BLOCK_NUM (JUMP_LABEL (insn)) == j)
        !           469:                        {
        !           470:                          PUT_CODE (insn, NOTE);
        !           471:                          NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
        !           472:                          NOTE_SOURCE_FILE (insn) = 0;
        !           473:                          if (GET_CODE (NEXT_INSN (insn)) != BARRIER)
        !           474:                            abort ();
        !           475:                          delete_insn (NEXT_INSN (insn));
        !           476:                        }
        !           477:                      break;
        !           478:                    }
        !           479:              }
        !           480:          }
        !           481:     }
        !           482: }
        !           483: 
        !           484: /* Check expression X for label references;
        !           485:    if one is found, add INSN to the label's chain of references.
        !           486: 
        !           487:    CHECKDUP means check for and avoid creating duplicate references
        !           488:    from the same insn.  Such duplicates do no serious harm but
        !           489:    can slow life analysis.  CHECKDUP is set only when duplicates
        !           490:    are likely.  */
        !           491: 
        !           492: static void
        !           493: mark_label_ref (x, insn, checkdup)
        !           494:      rtx x, insn;
        !           495:      int checkdup;
        !           496: {
        !           497:   register RTX_CODE code = GET_CODE (x);
        !           498:   register int i;
        !           499:   register char *fmt;
        !           500: 
        !           501:   if (code == LABEL_REF)
        !           502:     {
        !           503:       register rtx label = XEXP (x, 0);
        !           504:       register rtx y;
        !           505:       if (GET_CODE (label) != CODE_LABEL)
        !           506:        return;
        !           507:       /* If the label was never emitted, this insn is junk,
        !           508:         but avoid a crash trying to refer to BLOCK_NUM (label).
        !           509:         This can happen as a result of a syntax error
        !           510:         and a diagnostic has already been printed.  */
        !           511:       if (INSN_UID (label) == 0)
        !           512:        return;
        !           513:       CONTAINING_INSN (x) = insn;
        !           514:       /* if CHECKDUP is set, check for duplicate ref from same insn
        !           515:         and don't insert.  */
        !           516:       if (checkdup)
        !           517:        for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
        !           518:          if (CONTAINING_INSN (y) == insn)
        !           519:            return;
        !           520:       LABEL_NEXTREF (x) = LABEL_REFS (label);
        !           521:       LABEL_REFS (label) = x;
        !           522:       block_live_static[BLOCK_NUM (label)] = 1;
        !           523:       return;
        !           524:     }
        !           525: 
        !           526:   fmt = GET_RTX_FORMAT (code);
        !           527:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !           528:     {
        !           529:       if (fmt[i] == 'e')
        !           530:        mark_label_ref (XEXP (x, i), insn, 0);
        !           531:       if (fmt[i] == 'E')
        !           532:        {
        !           533:          register int j;
        !           534:          for (j = 0; j < XVECLEN (x, i); j++)
        !           535:            mark_label_ref (XVECEXP (x, i, j), insn, 1);
        !           536:        }
        !           537:     }
        !           538: }
        !           539: 
        !           540: /* Determine the which registers are live at the start of each
        !           541:    basic block of the function whose first insn is F.
        !           542:    NREGS is the number of registers used in F.
        !           543:    We allocate the vector basic_block_live_at_start
        !           544:    and the regsets that it points to, and fill them with the data.
        !           545:    regset_size and regset_bytes are also set here.  */
        !           546: 
        !           547: static void
        !           548: life_analysis (f, nregs)
        !           549:      rtx f;
        !           550:      int nregs;
        !           551: {
        !           552:   register regset tem;
        !           553:   int first_pass;
        !           554:   int changed;
        !           555:   /* For each basic block, a bitmask of regs
        !           556:      live on exit from the block.  */
        !           557:   regset *basic_block_live_at_end;
        !           558:   /* For each basic block, a bitmask of regs
        !           559:      live on entry to a successor-block of this block.
        !           560:      If this does not match basic_block_live_at_end,
        !           561:      that must be updated, and the block must be rescanned.  */
        !           562:   regset *basic_block_new_live_at_end;
        !           563:   /* For each basic block, a bitmask of regs
        !           564:      whose liveness at the end of the basic block
        !           565:      can make a difference in which regs are live on entry to the block.
        !           566:      These are the regs that are set within the basic block,
        !           567:      possibly excluding those that are used after they are set.  */
        !           568:   regset *basic_block_significant;
        !           569:   register int i;
        !           570:   rtx insn;
        !           571: 
        !           572:   max_regno = nregs;
        !           573: 
        !           574:   bzero (regs_ever_live, sizeof regs_ever_live);
        !           575: 
        !           576:   /* Allocate and zero out many data structures
        !           577:      that will record the data from lifetime analysis.  */
        !           578: 
        !           579:   allocate_for_life_analysis ();
        !           580: 
        !           581:   reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
        !           582:   bzero (reg_next_use, nregs * sizeof (rtx));
        !           583: 
        !           584:   /* Set up several regset-vectors used internally within this function.
        !           585:      Their meanings are documented above, with their declarations.  */
        !           586: 
        !           587:   basic_block_live_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
        !           588:   tem = (regset) alloca (n_basic_blocks * regset_bytes);
        !           589:   bzero (tem, n_basic_blocks * regset_bytes);
        !           590:   init_regset_vector (basic_block_live_at_end, tem, n_basic_blocks, regset_bytes);
        !           591: 
        !           592:   basic_block_new_live_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
        !           593:   tem = (regset) alloca (n_basic_blocks * regset_bytes);
        !           594:   bzero (tem, n_basic_blocks * regset_bytes);
        !           595:   init_regset_vector (basic_block_new_live_at_end, tem, n_basic_blocks, regset_bytes);
        !           596: 
        !           597:   basic_block_significant = (regset *) alloca (n_basic_blocks * sizeof (regset));
        !           598:   tem = (regset) alloca (n_basic_blocks * regset_bytes);
        !           599:   bzero (tem, n_basic_blocks * regset_bytes);
        !           600:   init_regset_vector (basic_block_significant, tem, n_basic_blocks, regset_bytes);
        !           601: 
        !           602:   /* Record which insns refer to any volatile memory.  */
        !           603: 
        !           604:   for (insn = f; insn; insn = NEXT_INSN (insn))
        !           605:     if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
        !           606:        || GET_CODE (insn) == CALL_INSN)
        !           607:       INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
        !           608: 
        !           609:   if (n_basic_blocks > 0)
        !           610: #ifdef EXIT_IGNORE_STACK
        !           611:     if (! (EXIT_IGNORE_STACK) || ! frame_pointer_needed)
        !           612: #endif
        !           613:       {
        !           614:        /* If exiting needs the right stack value,
        !           615:           consider the stack pointer live at the end of the function.  */
        !           616:        basic_block_live_at_end[n_basic_blocks - 1]
        !           617:          [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
        !           618:            |= 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
        !           619:        basic_block_new_live_at_end[n_basic_blocks - 1]
        !           620:          [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
        !           621:            |= 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
        !           622:       }
        !           623: 
        !           624:   /* Propagate life info through the basic blocks
        !           625:      around the graph of basic blocks.
        !           626: 
        !           627:      This is a relaxation process: each time a new register
        !           628:      is live at the end of the basic block, we must scan the block
        !           629:      to determine which registers are, as a consequence, live at the beginning
        !           630:      of that block.  These registers must then be marked live at the ends
        !           631:      of all the blocks that can transfer control to that block.
        !           632:      The process continues until it reaches a fixed point.  */
        !           633: 
        !           634:   first_pass = 1;
        !           635:   changed = 1;
        !           636:   while (changed)
        !           637:     {
        !           638:       changed = 0;
        !           639:       for (i = n_basic_blocks - 1; i >= 0; i--)
        !           640:        {
        !           641:          int consider = first_pass;
        !           642:          int must_rescan = first_pass;
        !           643:          register int j;
        !           644: 
        !           645:          /* Set CONSIDER if this block needs thinking about at all
        !           646:             (that is, if the regs live now at the end of it
        !           647:             are not the same as were live at the end of it when
        !           648:             we last thought about it).
        !           649:             Set must_rescan if it needs to be thought about
        !           650:             instruction by instruction (that is, if any additional
        !           651:             reg that is live at the end now but was not live there before
        !           652:             is one of the significant regs of this basic block).  */
        !           653: 
        !           654:          for (j = 0; j < regset_size; j++)
        !           655:            {
        !           656:              register int x = basic_block_new_live_at_end[i][j]
        !           657:                      & ~basic_block_live_at_end[i][j];
        !           658:              if (x)
        !           659:                consider = 1;
        !           660:              if (x & basic_block_significant[i][j])
        !           661:                {
        !           662:                  must_rescan = 1;
        !           663:                  consider = 1;
        !           664:                  break;
        !           665:                }
        !           666:            }
        !           667: 
        !           668:          if (! consider)
        !           669:            continue;
        !           670: 
        !           671:          /* The live_at_start of this block may be changing,
        !           672:             so another pass will be required after this one.  */
        !           673:          changed = 1;
        !           674: 
        !           675:          if (! must_rescan)
        !           676:            {
        !           677:              /* No complete rescan needed;
        !           678:                 just record those variables newly known live at end
        !           679:                 as live at start as well.  */
        !           680:              for (j = 0; j < regset_size; j++)
        !           681:                {
        !           682:                  register int x = basic_block_new_live_at_end[i][j]
        !           683:                        & ~basic_block_live_at_end[i][j];
        !           684:                  basic_block_live_at_start[i][j] |= x;
        !           685:                  basic_block_live_at_end[i][j] |= x;
        !           686:                }
        !           687:            }
        !           688:          else
        !           689:            {
        !           690:              /* Update the basic_block_live_at_start
        !           691:                 by propagation backwards through the block.  */
        !           692:              bcopy (basic_block_new_live_at_end[i],
        !           693:                     basic_block_live_at_end[i], regset_bytes);
        !           694:              bcopy (basic_block_live_at_end[i],
        !           695:                     basic_block_live_at_start[i], regset_bytes);
        !           696:              propagate_block (basic_block_live_at_start[i],
        !           697:                               basic_block_head[i], basic_block_end[i], 0,
        !           698:                               first_pass ? basic_block_significant[i] : 0,
        !           699:                               i);
        !           700:            }
        !           701: 
        !           702:          {
        !           703:            register rtx jump, head;
        !           704:            /* Update the basic_block_new_live_at_end's of the block
        !           705:               that falls through into this one (if any).  */
        !           706:            head = basic_block_head[i];
        !           707:            jump = PREV_INSN (head);
        !           708:            if (basic_block_drops_in[i])
        !           709:              {
        !           710:                register from_block = BLOCK_NUM (jump);
        !           711:                register int j;
        !           712:                for (j = 0; j < regset_size; j++)
        !           713:                  basic_block_new_live_at_end[from_block][j]
        !           714:                    |= basic_block_live_at_start[i][j];
        !           715:              }
        !           716:            /* Update the basic_block_new_live_at_end's of
        !           717:               all the blocks that jump to this one.  */
        !           718:            if (GET_CODE (head) == CODE_LABEL)
        !           719:              for (jump = LABEL_REFS (head);
        !           720:                   jump != head;
        !           721:                   jump = LABEL_NEXTREF (jump))
        !           722:                {
        !           723:                  register from_block = BLOCK_NUM (CONTAINING_INSN (jump));
        !           724:                  register int j;
        !           725:                  for (j = 0; j < regset_size; j++)
        !           726:                    basic_block_new_live_at_end[from_block][j]
        !           727:                      |= basic_block_live_at_start[i][j];
        !           728:                }
        !           729:          }
        !           730:        }
        !           731:       first_pass = 0;
        !           732:     }
        !           733: 
        !           734:   /* Process the regs live at the beginning of the function.
        !           735:      Mark them as not local to any one basic block.  */
        !           736: 
        !           737:   if (n_basic_blocks > 0)
        !           738:     for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           739:       if (basic_block_live_at_start[0][i / REGSET_ELT_BITS]
        !           740:          & (1 << (i % REGSET_ELT_BITS)))
        !           741:        reg_basic_block[i] = -2;
        !           742: 
        !           743:   /* Now the life information is accurate.
        !           744:      Make one more pass over each basic block
        !           745:      to delete dead stores, create autoincrement addressing
        !           746:      and record how many times each register is used, is set, or dies.
        !           747: 
        !           748:      To save time, we operate directly in basic_block_live_at_end[i],
        !           749:      thus destroying it (in fact, converting it into a copy of
        !           750:      basic_block_live_at_start[i]).  This is ok now because
        !           751:      basic_block_live_at_end[i] is no longer used past this point.  */
        !           752: 
        !           753:   for (i = 0; i < n_basic_blocks; i++)
        !           754:     {
        !           755:       propagate_block (basic_block_live_at_end[i],
        !           756:                       basic_block_head[i], basic_block_end[i], 1, 0, i);
        !           757:     }
        !           758: }
        !           759: 
        !           760: /* Subroutines of life analysis.  */
        !           761: 
        !           762: /* Allocate the permanent data structures that represent the results
        !           763:    of life analysis.  Not static since used also for stupid life analysis.  */
        !           764: 
        !           765: void
        !           766: allocate_for_life_analysis ()
        !           767: {
        !           768:   register int i;
        !           769:   register regset tem;
        !           770: 
        !           771:   regset_size = ((max_regno + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS);
        !           772:   regset_bytes = regset_size * sizeof (*(regset)0);
        !           773: 
        !           774:   reg_n_refs = (short *) oballoc (max_regno * sizeof (short));
        !           775:   bzero (reg_n_refs, max_regno * sizeof (short));
        !           776: 
        !           777:   reg_n_sets = (short *) oballoc (max_regno * sizeof (short));
        !           778:   bzero (reg_n_sets, max_regno * sizeof (short));
        !           779: 
        !           780:   reg_n_deaths = (short *) oballoc (max_regno * sizeof (short));
        !           781:   bzero (reg_n_deaths, max_regno * sizeof (short));
        !           782: 
        !           783:   reg_live_length = (int *) oballoc (max_regno * sizeof (int));
        !           784:   bzero (reg_live_length, max_regno * sizeof (int));
        !           785: 
        !           786:   reg_crosses_call = (char *) oballoc (max_regno);
        !           787:   bzero (reg_crosses_call, max_regno);
        !           788: 
        !           789:   reg_basic_block = (short *) oballoc (max_regno * sizeof (short));
        !           790:   for (i = 0; i < max_regno; i++)
        !           791:     reg_basic_block[i] = -1;
        !           792: 
        !           793:   basic_block_live_at_start = (regset *) oballoc (n_basic_blocks * sizeof (regset));
        !           794:   tem = (regset) oballoc (n_basic_blocks * regset_bytes);
        !           795:   bzero (tem, n_basic_blocks * regset_bytes);
        !           796:   init_regset_vector (basic_block_live_at_start, tem, n_basic_blocks, regset_bytes);
        !           797: 
        !           798:   regs_live_at_setjmp = (regset) oballoc (regset_bytes);
        !           799:   bzero (regs_live_at_setjmp, regset_bytes);
        !           800: }
        !           801: 
        !           802: /* Make each element of VECTOR point at a regset,
        !           803:    taking the space for all those regsets from SPACE.
        !           804:    SPACE is of type regset, but it is really as long as NELTS regsets.
        !           805:    BYTES_PER_ELT is the number of bytes in one regset.  */
        !           806: 
        !           807: static void
        !           808: init_regset_vector (vector, space, nelts, bytes_per_elt)
        !           809:      regset *vector;
        !           810:      regset space;
        !           811:      int nelts;
        !           812:      int bytes_per_elt;
        !           813: {
        !           814:   register int i;
        !           815:   register regset p = space;
        !           816: 
        !           817:   for (i = 0; i < nelts; i++)
        !           818:     {
        !           819:       vector[i] = p;
        !           820:       p += bytes_per_elt / sizeof (*p);
        !           821:     }
        !           822: }
        !           823: 
        !           824: /* Compute the registers live at the beginning of a basic block
        !           825:    from those live at the end.
        !           826: 
        !           827:    When called, OLD contains those live at the end.
        !           828:    On return, it contains those live at the beginning.
        !           829:    FIRST and LAST are the first and last insns of the basic block.
        !           830: 
        !           831:    FINAL is nonzero if we are doing the final pass which is not
        !           832:    for computing the life info (since that has already been done)
        !           833:    but for acting on it.  On this pass, we delete dead stores,
        !           834:    set up the logical links and dead-variables lists of instructions,
        !           835:    and merge instructions for autoincrement and autodecrement addresses.
        !           836: 
        !           837:    SIGNIFICANT is nonzero only the first time for each basic block.
        !           838:    If it is nonzero, it points to a regset in which we store
        !           839:    a 1 for each register that is set within the block.
        !           840: 
        !           841:    BNUM is the number of the basic block.  */
        !           842: 
        !           843: static void
        !           844: propagate_block (old, first, last, final, significant, bnum)
        !           845:      register regset old;
        !           846:      rtx first;
        !           847:      rtx last;
        !           848:      int final;
        !           849:      regset significant;
        !           850:      int bnum;
        !           851: {
        !           852:   register rtx insn;
        !           853:   rtx prev;
        !           854:   regset live;
        !           855:   regset dead;
        !           856: 
        !           857:   /* The following variables are used only if FINAL is nonzero.  */
        !           858:   /* This vector gets one element for each reg that has been live
        !           859:      at any point in the basic block that has been scanned so far.
        !           860:      SOMETIMES_MAX says how many elements are in use so far.
        !           861:      In each element, OFFSET is the byte-number within a regset
        !           862:      for the register described by the element, and BIT is a mask
        !           863:      for that register's bit within the byte.  */
        !           864:   register struct foo { short offset; short bit; } *regs_sometimes_live;
        !           865:   int sometimes_max = 0;
        !           866:   /* This regset has 1 for each reg that we have seen live so far.
        !           867:      It and REGS_SOMETIMES_LIVE are updated together.  */
        !           868:   regset maxlive;
        !           869: 
        !           870:   loop_depth = basic_block_loop_depth[bnum];
        !           871: 
        !           872:   dead = (regset) alloca (regset_bytes);
        !           873:   live = (regset) alloca (regset_bytes);
        !           874: 
        !           875:   if (final)
        !           876:     {
        !           877:       register int i, offset, bit;
        !           878: 
        !           879:       maxlive = (regset) alloca (regset_bytes);
        !           880:       bcopy (old, maxlive, regset_bytes);
        !           881:       regs_sometimes_live
        !           882:        = (struct foo *) alloca (max_regno * sizeof (struct foo));
        !           883: 
        !           884:       /* Process the regs live at the end of the block.
        !           885:         Enter them in MAXLIVE and REGS_SOMETIMES_LIVE.
        !           886:         Also mark them as not local to any one basic block.  */
        !           887: 
        !           888:       for (offset = 0, i = 0; offset < regset_size; offset++)
        !           889:        for (bit = 1; bit; bit <<= 1, i++)
        !           890:          {
        !           891:            if (i == max_regno)
        !           892:              break;
        !           893:            if (old[offset] & bit)
        !           894:              {
        !           895:                reg_basic_block[i] = -2;
        !           896:                regs_sometimes_live[sometimes_max].offset = offset;
        !           897:                regs_sometimes_live[sometimes_max].bit = i % REGSET_ELT_BITS;
        !           898:                sometimes_max++;
        !           899:              }
        !           900:          }
        !           901:     }
        !           902: 
        !           903:   /* Scan the block an insn at a time from end to beginning.  */
        !           904: 
        !           905:   for (insn = last; ; insn = prev)
        !           906:     {
        !           907:       prev = PREV_INSN (insn);
        !           908: 
        !           909:       /* If this is a call to `setjmp' et al,
        !           910:         warn if any non-volatile datum is live.  */
        !           911: 
        !           912:       if (final && GET_CODE (insn) == NOTE
        !           913:          && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
        !           914:        {
        !           915:          int i;
        !           916:          for (i = 0; i < regset_size; i++)
        !           917:            regs_live_at_setjmp[i] |= old[i];
        !           918:        }
        !           919: 
        !           920:       /* Update the life-status of regs for this insn.
        !           921:         First DEAD gets which regs are set in this insn
        !           922:         then LIVE gets which regs are used in this insn.
        !           923:         Then the regs live before the insn
        !           924:         are those live after, with DEAD regs turned off,
        !           925:         and then LIVE regs turned on.  */
        !           926: 
        !           927:       if (GET_CODE (insn) == INSN
        !           928:          || GET_CODE (insn) == JUMP_INSN
        !           929:          || GET_CODE (insn) == CALL_INSN)
        !           930:        {
        !           931:          register int i;
        !           932:          rtx note = find_reg_note (insn, REG_RETVAL, 0);
        !           933: 
        !           934:          /* If an instruction consists of just dead store(s) on final pass,
        !           935:             "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
        !           936:             We could really delete it with delete_insn, but that
        !           937:             can cause trouble for first or last insn in a basic block.  */
        !           938:          if (final && insn_dead_p (PATTERN (insn), old, 1)
        !           939:              /* Don't delete something that refers to volatile storage!  */
        !           940:              && ! INSN_VOLATILE (insn))
        !           941:            {
        !           942:              PUT_CODE (insn, NOTE);
        !           943:              NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
        !           944:              NOTE_SOURCE_FILE (insn) = 0;
        !           945:              /* If this insn is copying the return value from a library call,
        !           946:                 delete the entire library call.  */
        !           947:              if (note)
        !           948:                {
        !           949:                  rtx first = XEXP (note, 0);
        !           950:                  rtx prev = insn;
        !           951:                  while (first->volatil)
        !           952:                    first = NEXT_INSN (first);
        !           953:                  while (prev != first)
        !           954:                    {
        !           955:                      prev = PREV_INSN (prev);
        !           956:                      PUT_CODE (prev, NOTE);
        !           957:                      NOTE_LINE_NUMBER (prev) = NOTE_INSN_DELETED;
        !           958:                      NOTE_SOURCE_FILE (prev) = 0;
        !           959:                    }
        !           960:                }
        !           961:              goto flushed;
        !           962:            }
        !           963: 
        !           964:          for (i = 0; i < regset_size; i++)
        !           965:            {
        !           966:              dead[i] = 0;      /* Faster than bzero here */
        !           967:              live[i] = 0;      /* since regset_size is usually small */
        !           968:            }
        !           969: 
        !           970:          /* See if this is an increment or decrement that can be
        !           971:             merged into a following memory address.  */
        !           972: #ifdef AUTO_INC_DEC
        !           973:          {
        !           974:            register rtx x = PATTERN (insn);
        !           975:            /* Does this instruction increment or decrement a register?  */
        !           976:            if (final && GET_CODE (x) == SET
        !           977:                && GET_CODE (SET_DEST (x)) == REG
        !           978:                && (GET_CODE (SET_SRC (x)) == PLUS
        !           979:                    || GET_CODE (SET_SRC (x)) == MINUS)
        !           980:                && XEXP (SET_SRC (x), 0) == SET_DEST (x)
        !           981:                && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
        !           982:                /* Ok, look for a following memory ref we can combine with.
        !           983:                   If one is found, change the memory ref to a PRE_INC
        !           984:                   or PRE_DEC, cancel this insn, and return 1.
        !           985:                   Return 0 if nothing has been done.  */
        !           986:                && try_pre_increment_1 (insn))
        !           987:              goto flushed;
        !           988:          }
        !           989: #endif /* AUTO_INC_DEC */
        !           990: 
        !           991:          /* If this is not the final pass, and this insn is copying the
        !           992:             value of a library call and it's dead, don't scan the
        !           993:             insns that perform the library call, so that the call's
        !           994:             arguments are not marked live.  */
        !           995:          if (note && insn_dead_p (PATTERN (insn), old, 1))
        !           996:            {
        !           997:              insn = XEXP (note, 0);
        !           998:              prev = PREV_INSN (insn);
        !           999:            }
        !          1000:          else
        !          1001:            {
        !          1002:              /* LIVE gets the regs used in INSN; DEAD gets those set by it.  */
        !          1003:              mark_set_regs (old, dead, PATTERN (insn), final ? insn : 0,
        !          1004:                             significant);
        !          1005:              mark_used_regs (old, live, PATTERN (insn), final, insn);
        !          1006: 
        !          1007:              /* Update OLD for the registers used or set.  */
        !          1008:              for (i = 0; i < regset_size; i++)
        !          1009:                {
        !          1010:                  old[i] &= ~dead[i];
        !          1011:                  old[i] |= live[i];
        !          1012:                }
        !          1013: 
        !          1014:              if (GET_CODE (insn) == CALL_INSN)
        !          1015:                {
        !          1016:                  register int i;
        !          1017: 
        !          1018:                  /* Each call clobbers all call-clobbered regs.
        !          1019:                     Note that the function-value reg is one of these, and
        !          1020:                     mark_set_regs has already had a chance to handle it.  */
        !          1021:                  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !          1022:                    if (call_used_regs[i])
        !          1023:                      old[i / REGSET_ELT_BITS]
        !          1024:                        &= ~(1 << (i % REGSET_ELT_BITS));
        !          1025: 
        !          1026:                  /* The stack ptr is used (honorarily) by a CALL insn.  */
        !          1027:                  old[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
        !          1028:                    |= (1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS));
        !          1029: 
        !          1030:                  if (final)
        !          1031:                    {
        !          1032:                      /* Any regs live at the time of a call instruction
        !          1033:                         must not go in a register clobbered by calls.
        !          1034:                         Find all regs now live and record this for them.  */
        !          1035: 
        !          1036:                      register struct foo *p = regs_sometimes_live;
        !          1037: 
        !          1038:                      for (i = 0; i < sometimes_max; i++, p++)
        !          1039:                        {
        !          1040:                          if (old[p->offset]
        !          1041:                              & (1 << p->bit))
        !          1042:                            reg_crosses_call[p->offset * REGSET_ELT_BITS + p->bit] = 1;
        !          1043:                        }
        !          1044:                    }
        !          1045:                }
        !          1046:            }
        !          1047: 
        !          1048:          /* On final pass, add any additional sometimes-live regs
        !          1049:             into MAXLIVE and REGS_SOMETIMES_LIVE.
        !          1050:             Also update counts of how many insns each reg is live at.  */
        !          1051: 
        !          1052:          if (final)
        !          1053:            {
        !          1054:              for (i = 0; i < regset_size; i++)
        !          1055:                {
        !          1056:                  register int diff = live[i] & ~maxlive[i];
        !          1057: 
        !          1058:                  if (diff)
        !          1059:                    {
        !          1060:                      register int regno;
        !          1061:                      maxlive[i] |= diff;
        !          1062:                      for (regno = 0; diff && regno < REGSET_ELT_BITS; regno++)
        !          1063:                        if (diff & (1 << regno))
        !          1064:                          {
        !          1065:                            regs_sometimes_live[sometimes_max].offset = i;
        !          1066:                            regs_sometimes_live[sometimes_max].bit = regno;
        !          1067:                            diff &= ~ (1 << regno);
        !          1068:                            sometimes_max++;
        !          1069:                          }
        !          1070:                    }
        !          1071:                }
        !          1072: 
        !          1073:              {
        !          1074:                register struct foo *p = regs_sometimes_live;
        !          1075:                for (i = 0; i < sometimes_max; i++, p++)
        !          1076:                  {
        !          1077:                    if (old[p->offset] & (1 << p->bit))
        !          1078:                      reg_live_length[p->offset * REGSET_ELT_BITS + p->bit]++;
        !          1079:                  }
        !          1080:              }
        !          1081:            }
        !          1082:        }
        !          1083:     flushed: ;
        !          1084:       if (insn == first)
        !          1085:        break;
        !          1086:     }
        !          1087: }
        !          1088: 
        !          1089: /* Return 1 if X (the body of an insn, or part of it) is just dead stores
        !          1090:    (SET expressions whose destinations are registers dead after the insn).
        !          1091:    NEEDED is the regset that says which regs are alive after the insn.  */
        !          1092: 
        !          1093: static int
        !          1094: insn_dead_p (x, needed, strict_low_ok)
        !          1095:      rtx x;
        !          1096:      regset needed;
        !          1097:      int strict_low_ok;
        !          1098: {
        !          1099:   register RTX_CODE code = GET_CODE (x);
        !          1100: #if 0
        !          1101:   /* Make sure insns to set the stack pointer are never deleted.  */
        !          1102:   needed[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
        !          1103:     |= 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
        !          1104: #endif
        !          1105: 
        !          1106:   /* If setting something that's a reg or part of one,
        !          1107:      see if that register's altered value will be live.  */
        !          1108: 
        !          1109:   if (code == SET)
        !          1110:     {
        !          1111:       register rtx r = SET_DEST (x);
        !          1112:       /* A SET that is a subroutine call cannot be dead.  */
        !          1113:       if (GET_CODE (SET_SRC (x)) == CALL)
        !          1114:        return 0;
        !          1115:       while (GET_CODE (r) == SUBREG
        !          1116:             || (strict_low_ok && GET_CODE (r) == STRICT_LOW_PART)
        !          1117:             || GET_CODE (r) == ZERO_EXTRACT
        !          1118:             || GET_CODE (r) == SIGN_EXTRACT)
        !          1119:        r = SUBREG_REG (r);
        !          1120:       if (GET_CODE (r) == REG)
        !          1121:        {
        !          1122:          register int regno = REGNO (r);
        !          1123:          register int offset = regno / REGSET_ELT_BITS;
        !          1124:          register int bit = 1 << (regno % REGSET_ELT_BITS);
        !          1125:          return (needed[offset] & bit) == 0;
        !          1126:        }
        !          1127:     }
        !          1128:   /* If performing several activities,
        !          1129:      insn is dead if each activity is individually dead.
        !          1130:      Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
        !          1131:      that's inside a PARALLEL doesn't make the insn worth keeping.  */
        !          1132:   else if (code == PARALLEL)
        !          1133:     {
        !          1134:       register int i = XVECLEN (x, 0);
        !          1135:       for (i--; i >= 0; i--)
        !          1136:        {
        !          1137:          rtx elt = XVECEXP (x, 0, i);
        !          1138:          if (!insn_dead_p (elt, needed, strict_low_ok)
        !          1139:              && GET_CODE (elt) != CLOBBER
        !          1140:              && GET_CODE (elt) != USE)
        !          1141:            return 0;
        !          1142:        }
        !          1143:       return 1;
        !          1144:     }
        !          1145:   /* We do not check CLOBBER or USE here.
        !          1146:      An insn consisting of just a CLOBBER or just a USE
        !          1147:      should not be deleted.  */
        !          1148:   return 0;
        !          1149: }
        !          1150: 
        !          1151: /* Return 1 if register REGNO was used before it was set.
        !          1152:    In other words, if it is live at function entry.  */
        !          1153: 
        !          1154: int
        !          1155: regno_uninitialized (regno)
        !          1156:      int regno;
        !          1157: {
        !          1158:   return (basic_block_live_at_start[0][regno / REGSET_ELT_BITS]
        !          1159:          & (1 << (regno % REGSET_ELT_BITS)));
        !          1160: }
        !          1161: 
        !          1162: /* 1 if register REGNO was alive at a place where `setjmp' was called
        !          1163:    and was set more than once.  Such regs may be clobbered by `longjmp'.  */
        !          1164: 
        !          1165: int
        !          1166: regno_clobbered_at_setjmp (regno)
        !          1167:      int regno;
        !          1168: {
        !          1169:   return (reg_n_sets[regno] > 1
        !          1170:          && (regs_live_at_setjmp[regno / REGSET_ELT_BITS]
        !          1171:              & (1 << (regno % REGSET_ELT_BITS))));
        !          1172: }
        !          1173: 
        !          1174: /* Process the registers that are set within X.
        !          1175:    Their bits are set to 1 in the regset DEAD,
        !          1176:    because they are dead prior to this insn.
        !          1177: 
        !          1178:    If INSN is nonzero, it is the insn being processed
        !          1179:    and the fact that it is nonzero implies this is the FINAL pass
        !          1180:    in propagate_block.  In this case, various info about register
        !          1181:    usage is stored, LOG_LINKS fields of insns are set up.  */
        !          1182: 
        !          1183: static void mark_set_1 ();
        !          1184: 
        !          1185: static void
        !          1186: mark_set_regs (needed, dead, x, insn, significant)
        !          1187:      regset needed;
        !          1188:      regset dead;
        !          1189:      rtx x;
        !          1190:      rtx insn;
        !          1191:      regset significant;
        !          1192: {
        !          1193:   register RTX_CODE code = GET_CODE (x);
        !          1194: 
        !          1195:   if (code == SET || code == CLOBBER)
        !          1196:     mark_set_1 (needed, dead, x, insn, significant);
        !          1197:   else if (code == PARALLEL)
        !          1198:     {
        !          1199:       register int i;
        !          1200:       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
        !          1201:        {
        !          1202:          code = GET_CODE (XVECEXP (x, 0, i));
        !          1203:          if (code == SET || code == CLOBBER)
        !          1204:            mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn, significant);
        !          1205:        }
        !          1206:     }
        !          1207: }
        !          1208: 
        !          1209: /* Process a single SET rtx, X.  */
        !          1210: 
        !          1211: static void
        !          1212: mark_set_1 (needed, dead, x, insn, significant)
        !          1213:      regset needed;
        !          1214:      regset dead;
        !          1215:      rtx x;
        !          1216:      rtx insn;
        !          1217:      regset significant;
        !          1218: {
        !          1219:   register int regno;
        !          1220:   register rtx reg = SET_DEST (x);
        !          1221: 
        !          1222:   if (reg == 0)
        !          1223:     return;
        !          1224: 
        !          1225:   if (GET_CODE (reg) == SUBREG)
        !          1226:     {
        !          1227:       /* Modifying just one hardware register
        !          1228:         of a multi-register value does not count as "setting"
        !          1229:         for live-dead analysis.  Parts of the previous value
        !          1230:         might still be significant below this insn.  */
        !          1231:       if (REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
        !          1232:        return;
        !          1233: 
        !          1234:       reg = SUBREG_REG (reg);
        !          1235:     }
        !          1236: 
        !          1237:   if (GET_CODE (reg) == REG
        !          1238:       && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM)
        !          1239:       && regno != ARG_POINTER_REGNUM)
        !          1240:     /* && regno != STACK_POINTER_REGNUM) -- let's try without this.  */
        !          1241:     {
        !          1242:       register int offset = regno / REGSET_ELT_BITS;
        !          1243:       register int bit = 1 << (regno % REGSET_ELT_BITS);
        !          1244:       int is_needed = 0;
        !          1245: 
        !          1246:       /* Mark the reg being set as dead before this insn.  */
        !          1247:       dead[offset] |= bit;
        !          1248:       /* Mark it as a significant register for this basic block.  */
        !          1249:       if (significant)
        !          1250:        significant[offset] |= bit;
        !          1251:       /* A hard reg in a wide mode may really be multiple registers.
        !          1252:         If so, mark all of them just like the first.  */
        !          1253:       if (regno < FIRST_PSEUDO_REGISTER)
        !          1254:        {
        !          1255:          int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
        !          1256:          while (--n > 0)
        !          1257:            {
        !          1258:              dead[(regno + n) / REGSET_ELT_BITS]
        !          1259:                |= 1 << ((regno + n) % REGSET_ELT_BITS);
        !          1260:              if (significant)
        !          1261:                significant[(regno + n) / REGSET_ELT_BITS]
        !          1262:                  |= 1 << ((regno + n) % REGSET_ELT_BITS);
        !          1263:              is_needed |= (needed[(regno + n) / REGSET_ELT_BITS]
        !          1264:                            & 1 << ((regno + n) % REGSET_ELT_BITS));
        !          1265:            }
        !          1266:        }
        !          1267:       /* Additional data to record if this is the final pass.  */
        !          1268:       if (insn)
        !          1269:        {
        !          1270:          register rtx y = reg_next_use[regno];
        !          1271:          register int blocknum = BLOCK_NUM (insn);
        !          1272: 
        !          1273:          /* If this is a hard reg, record this function uses the reg.  */
        !          1274: 
        !          1275:          if (regno < FIRST_PSEUDO_REGISTER)
        !          1276:            {
        !          1277:              register int i;
        !          1278:              i = HARD_REGNO_NREGS (regno, GET_MODE (reg));
        !          1279:              do
        !          1280:                regs_ever_live[regno + --i] = 1;
        !          1281:              while (i > 0);
        !          1282:            }
        !          1283: 
        !          1284:          /* Keep track of which basic blocks each reg appears in.  */
        !          1285: 
        !          1286:          if (reg_basic_block[regno] == -1)
        !          1287:            reg_basic_block[regno] = blocknum;
        !          1288:          else if (reg_basic_block[regno] != blocknum)
        !          1289:            reg_basic_block[regno] = -2;
        !          1290: 
        !          1291:          /* Count (weighted) references, stores, etc.  */
        !          1292:          reg_n_refs[regno] += loop_depth;
        !          1293:          reg_n_sets[regno]++;
        !          1294:          /* The next use is no longer "next", since a store intervenes.  */
        !          1295:          reg_next_use[regno] = 0;
        !          1296:          /* The insns where a reg is live are normally counted elsewhere,
        !          1297:             but we want the count to include the insn where the reg is set,
        !          1298:             and the normal counting mechanism would not count it.  */
        !          1299:          reg_live_length[regno]++;
        !          1300:          if ((needed[offset] & bit) || is_needed)
        !          1301:            {
        !          1302:              /* Make a logical link from the next following insn
        !          1303:                 that uses this register, back to this insn.
        !          1304:                 The following insns have already been processed.  */
        !          1305:              if (y && (BLOCK_NUM (y) == blocknum))
        !          1306:                LOG_LINKS (y)
        !          1307:                  = gen_rtx (INSN_LIST, VOIDmode, insn, LOG_LINKS (y));
        !          1308:            }
        !          1309:          else
        !          1310:            {
        !          1311:              /* Note that dead stores have already been deleted when possible
        !          1312:                 If we get here, we have found a dead store that cannot
        !          1313:                 be eliminated (because the same insn does something useful).
        !          1314:                 Indicate this by marking the reg being set as dying here.  */
        !          1315:              REG_NOTES (insn)
        !          1316:                = gen_rtx (EXPR_LIST, REG_DEAD,
        !          1317:                           reg, REG_NOTES (insn));
        !          1318:              reg_n_deaths[REGNO (reg)]++;
        !          1319:            }
        !          1320:        }
        !          1321:     }
        !          1322: }
        !          1323: 
        !          1324: /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
        !          1325:    This is done assuming the registers needed from X
        !          1326:    are those that have 1-bits in NEEDED.
        !          1327: 
        !          1328:    On the final pass, FINAL is 1.  This means try for autoincrement
        !          1329:    and count the uses and deaths of each pseudo-reg.
        !          1330: 
        !          1331:    INSN is the containing instruction.  */
        !          1332: 
        !          1333: static void
        !          1334: mark_used_regs (needed, live, x, final, insn)
        !          1335:      regset needed;
        !          1336:      regset live;
        !          1337:      rtx x;
        !          1338:      rtx insn;
        !          1339:      int final;
        !          1340: {
        !          1341:   register RTX_CODE code;
        !          1342:   register int regno;
        !          1343: 
        !          1344:  retry:
        !          1345:   code = GET_CODE (x);
        !          1346:   switch (code)
        !          1347:     {
        !          1348:     case LABEL_REF:
        !          1349:     case SYMBOL_REF:
        !          1350:     case CONST_INT:
        !          1351:     case CONST:
        !          1352:     case CC0:
        !          1353:     case PC:
        !          1354:     case CLOBBER:
        !          1355:       return;
        !          1356: 
        !          1357: #if defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT)
        !          1358:     case MEM:
        !          1359:       /* Here we detect use of an index register which might
        !          1360:         be good for postincrement or postdecrement.  */
        !          1361:       if (final)
        !          1362:        {
        !          1363:          rtx addr = XEXP (x, 0);
        !          1364:          register int size = GET_MODE_SIZE (GET_MODE (x));
        !          1365: 
        !          1366:          if (GET_CODE (addr) == REG)
        !          1367:            {
        !          1368:              register rtx y;
        !          1369:              regno = REGNO (addr);
        !          1370:              /* Is the next use an increment that might make auto-increment? */
        !          1371:              y = reg_next_use[regno];
        !          1372:              if (y && GET_CODE (PATTERN (y)) == SET
        !          1373:                  && BLOCK_NUM (y) == BLOCK_NUM (insn)
        !          1374:                  /* Can't add side effects to jumps; if reg is spilled and
        !          1375:                     reloaded, there's no way to store back the altered value.  */
        !          1376:                  && GET_CODE (insn) != JUMP_INSN
        !          1377:                  && (y = SET_SRC (PATTERN (y)),
        !          1378:                      (0
        !          1379: #ifdef HAVE_POST_INCREMENT
        !          1380:                       || GET_CODE (y) == PLUS
        !          1381: #endif
        !          1382: #ifdef HAVE_POST_DECREMENT
        !          1383:                       || GET_CODE (y) == MINUS
        !          1384: #endif
        !          1385:                       )
        !          1386:                      && XEXP (y, 0) == addr
        !          1387:                      && GET_CODE (XEXP (y, 1)) == CONST_INT
        !          1388:                      && INTVAL (XEXP (y, 1)) == size)
        !          1389:                  && dead_or_set_p (reg_next_use[regno], addr))
        !          1390:                {
        !          1391:                  rtx use = find_use_as_address (PATTERN (insn), addr, 0);
        !          1392: 
        !          1393:                  /* Make sure this register appears only once in this insn.  */
        !          1394:                  if (use != 0 && use != (rtx) 1)
        !          1395:                    {
        !          1396:                      /* We have found a suitable auto-increment:
        !          1397:                         do POST_INC around the register here,
        !          1398:                         and patch out the increment instruction that follows. */
        !          1399:                      XEXP (x, 0)
        !          1400:                        = gen_rtx (GET_CODE (y) == PLUS ? POST_INC : POST_DEC,
        !          1401:                                   Pmode, addr);
        !          1402:                      /* Record that this insn has an implicit side effect.  */
        !          1403:                      REG_NOTES (insn)
        !          1404:                        = gen_rtx (EXPR_LIST, REG_INC, addr, REG_NOTES (insn));
        !          1405: 
        !          1406:                      /* Modify the old increment-insn to simply copy
        !          1407:                         the already-incremented value of our register.  */
        !          1408:                      y = reg_next_use[regno];
        !          1409:                      SET_SRC (PATTERN (y)) = addr;
        !          1410: 
        !          1411:                      /* If that makes it a no-op (copying the register
        !          1412:                         into itself) then change it to a simpler no-op
        !          1413:                         so it won't appear to be a "use" and a "set"
        !          1414:                         of this register.  */
        !          1415:                      if (SET_DEST (PATTERN (y)) == addr)
        !          1416:                        PATTERN (y) = gen_rtx (USE, VOIDmode, const0_rtx);
        !          1417: 
        !          1418:                      /* Count an extra reference to the reg for the increment.
        !          1419:                         When a reg is incremented.
        !          1420:                         spilling it is worse, so we want to make that
        !          1421:                         less likely.  */
        !          1422:                      reg_n_refs[regno] += loop_depth;
        !          1423:                      /* Count the increment as a setting of the register,
        !          1424:                         even though it isn't a SET in rtl.  */
        !          1425:                      reg_n_sets[regno]++;
        !          1426:                    }
        !          1427:                }
        !          1428:            }
        !          1429:        }
        !          1430:       break;
        !          1431: #endif /* HAVE_POST_INCREMENT or HAVE_POST_DECREMENT */
        !          1432: 
        !          1433:     case REG:
        !          1434:       /* See a register other than being set
        !          1435:         => mark it as needed.  */
        !          1436: 
        !          1437:       regno = REGNO (x);
        !          1438:       if (regno != FRAME_POINTER_REGNUM
        !          1439:          && regno != ARG_POINTER_REGNUM)
        !          1440:        /* && regno != STACK_POINTER_REGNUM) -- let's try without this.  */
        !          1441:        {
        !          1442:          register int offset = regno / REGSET_ELT_BITS;
        !          1443:          register int bit = 1 << (regno % REGSET_ELT_BITS);
        !          1444:          int is_needed = 0;
        !          1445: 
        !          1446:          live[offset] |= bit;
        !          1447:          /* A hard reg in a wide mode may really be multiple registers.
        !          1448:             If so, mark all of them just like the first.  */
        !          1449:          if (regno < FIRST_PSEUDO_REGISTER)
        !          1450:            {
        !          1451:              int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
        !          1452:              while (--n > 0)
        !          1453:                {
        !          1454:                  live[(regno + n) / REGSET_ELT_BITS]
        !          1455:                    |= 1 << ((regno + n) % REGSET_ELT_BITS);
        !          1456:                  is_needed |= (needed[(regno + n) / REGSET_ELT_BITS]
        !          1457:                                & 1 << ((regno + n) % REGSET_ELT_BITS));
        !          1458:                }
        !          1459:            }
        !          1460:          if (final)
        !          1461:            {
        !          1462:              register int blocknum = BLOCK_NUM (insn);
        !          1463: 
        !          1464:              /* If a hard reg is being used,
        !          1465:                 record that this function does use it.  */
        !          1466: 
        !          1467:              if (regno < FIRST_PSEUDO_REGISTER)
        !          1468:                {
        !          1469:                  register int i;
        !          1470:                  i = HARD_REGNO_NREGS (regno, GET_MODE (x));
        !          1471:                  do
        !          1472:                    regs_ever_live[regno + --i] = 1;
        !          1473:                  while (i > 0);
        !          1474:                }
        !          1475: 
        !          1476:              /* Keep track of which basic block each reg appears in.  */
        !          1477: 
        !          1478:              if (reg_basic_block[regno] == -1)
        !          1479:                reg_basic_block[regno] = blocknum;
        !          1480:              else if (reg_basic_block[regno] != blocknum)
        !          1481:                reg_basic_block[regno] = -2;
        !          1482: 
        !          1483:              /* Record where each reg is used
        !          1484:                 so when the reg is set we know the next insn that uses it.  */
        !          1485: 
        !          1486:              reg_next_use[regno] = insn;
        !          1487: 
        !          1488:              /* Count (weighted) number of uses of each reg.  */
        !          1489: 
        !          1490:              reg_n_refs[regno] += loop_depth;
        !          1491: 
        !          1492:              /* Record and count the insns in which a reg dies.
        !          1493:                 If it is used in this insn and was dead below the insn
        !          1494:                 then it dies in this insn.  */
        !          1495: 
        !          1496:              if (!(needed[offset] & bit) && !is_needed
        !          1497:                  && ! find_regno_note (insn, REG_DEAD, regno))
        !          1498:                {
        !          1499:                  REG_NOTES (insn)
        !          1500:                    = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (insn));
        !          1501:                  reg_n_deaths[regno]++;
        !          1502:                }
        !          1503:            }
        !          1504:        }
        !          1505:       return;
        !          1506: 
        !          1507:     case SET:
        !          1508:       {
        !          1509:        register rtx testreg = SET_DEST (x);
        !          1510:        int mark_dest = 0;
        !          1511: 
        !          1512:        /* Storing in STRICT_LOW_PART is like storing in a reg
        !          1513:           in that this SET might be dead, so ignore it in TESTREG.
        !          1514:           but in some other ways it is like using the reg.  */
        !          1515:        /* Storing in a SUBREG or a bit field is like storing the entire
        !          1516:           register in that if the register's value is not used
        !          1517:           then this SET is not needed.  */
        !          1518:        while (GET_CODE (testreg) == STRICT_LOW_PART
        !          1519:               || GET_CODE (testreg) == ZERO_EXTRACT
        !          1520:               || GET_CODE (testreg) == SIGN_EXTRACT
        !          1521:               || GET_CODE (testreg) == SUBREG)
        !          1522:          {
        !          1523:            /* Modifying a single register in an alternate mode
        !          1524:               does not use any of the old value.  But these other
        !          1525:               ways of storing in a register do use the old value.  */
        !          1526:            if (GET_CODE (testreg) == SUBREG
        !          1527:                && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
        !          1528:              ;
        !          1529:            else
        !          1530:              mark_dest = 1;
        !          1531: 
        !          1532:            testreg = XEXP (testreg, 0);
        !          1533:          }
        !          1534: 
        !          1535:        /* If this is a store into a register,
        !          1536:           recursively scan the only value being stored,
        !          1537:           and only if the register's value is live after this insn.
        !          1538:           If the value being computed here would never be used
        !          1539:           then the values it uses don't need to be computed either.  */
        !          1540: 
        !          1541:        if (GET_CODE (testreg) == REG
        !          1542:            && (regno = REGNO (testreg), regno != FRAME_POINTER_REGNUM)
        !          1543:            && regno != ARG_POINTER_REGNUM)
        !          1544:          /*  && regno != STACK_POINTER_REGNUM) -- let's try without this.  */
        !          1545:          {
        !          1546:            register int offset = regno / REGSET_ELT_BITS;
        !          1547:            register int bit = 1 << (regno % REGSET_ELT_BITS);
        !          1548:            if ((needed[offset] & bit)
        !          1549:                /* If insn refers to volatile, we mustn't delete it,
        !          1550:                   so its inputs are all needed.  */
        !          1551:                || INSN_VOLATILE (insn))
        !          1552:              {
        !          1553:                mark_used_regs (needed, live, SET_SRC (x), final, insn);
        !          1554:                if (mark_dest)
        !          1555:                  mark_used_regs (needed, live, SET_DEST (x), final, insn);
        !          1556:              }
        !          1557:            return;
        !          1558:          }
        !          1559:       }
        !          1560:       break;
        !          1561:     }
        !          1562: 
        !          1563:   /* Recursively scan the operands of this expression.  */
        !          1564: 
        !          1565:   {
        !          1566:     register char *fmt = GET_RTX_FORMAT (code);
        !          1567:     register int i;
        !          1568:     
        !          1569:     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !          1570:       {
        !          1571:        if (fmt[i] == 'e')
        !          1572:          {
        !          1573:            /* Tail recursive case: save a function call level.  */
        !          1574:            if (i == 0)
        !          1575:              {
        !          1576:                x = XEXP (x, 0);
        !          1577:                goto retry;
        !          1578:              }
        !          1579:            mark_used_regs (needed, live, XEXP (x, i), final, insn);
        !          1580:          }
        !          1581:        if (fmt[i] == 'E')
        !          1582:          {
        !          1583:            register int j;
        !          1584:            for (j = 0; j < XVECLEN (x, i); j++)
        !          1585:              mark_used_regs (needed, live, XVECEXP (x, i, j), final, insn);
        !          1586:          }
        !          1587:       }
        !          1588:   }
        !          1589: }
        !          1590: 
        !          1591: /* Nonzero if X contains any volatile memory references
        !          1592:    or volatile ASM_OPERANDS expressions.  */
        !          1593: 
        !          1594: static int
        !          1595: volatile_refs_p (x)
        !          1596:      rtx x;
        !          1597: {
        !          1598:   register RTX_CODE code;
        !          1599: 
        !          1600:   code = GET_CODE (x);
        !          1601:   switch (code)
        !          1602:     {
        !          1603:     case LABEL_REF:
        !          1604:     case SYMBOL_REF:
        !          1605:     case CONST_INT:
        !          1606:     case CONST:
        !          1607:     case CC0:
        !          1608:     case PC:
        !          1609:     case CLOBBER:
        !          1610:     case REG:
        !          1611:       return 0;
        !          1612: 
        !          1613:     case CALL:
        !          1614:       return 1;
        !          1615: 
        !          1616:     case MEM:
        !          1617:     case ASM_OPERANDS:
        !          1618:       if (x->volatil)
        !          1619:        return 1;
        !          1620:     }
        !          1621: 
        !          1622:   /* Recursively scan the operands of this expression.  */
        !          1623: 
        !          1624:   {
        !          1625:     register char *fmt = GET_RTX_FORMAT (code);
        !          1626:     register int i;
        !          1627:     
        !          1628:     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !          1629:       {
        !          1630:        if (fmt[i] == 'e')
        !          1631:          {
        !          1632:            if (volatile_refs_p (XEXP (x, i)))
        !          1633:              return 1;
        !          1634:          }
        !          1635:        if (fmt[i] == 'E')
        !          1636:          {
        !          1637:            register int j;
        !          1638:            for (j = 0; j < XVECLEN (x, i); j++)
        !          1639:              if (volatile_refs_p (XVECEXP (x, i, j)))
        !          1640:                return 1;
        !          1641:          }
        !          1642:       }
        !          1643:   }
        !          1644:   return 0;
        !          1645: }
        !          1646: 
        !          1647: #ifdef AUTO_INC_DEC
        !          1648: 
        !          1649: static int
        !          1650: try_pre_increment_1 (insn)
        !          1651:      rtx insn;
        !          1652: {
        !          1653:   /* Find the next use of this reg.  If in same basic block,
        !          1654:      make it do pre-increment or pre-decrement if appropriate.  */
        !          1655:   rtx x = PATTERN (insn);
        !          1656:   int amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
        !          1657:                * INTVAL (XEXP (SET_SRC (x), 1)));
        !          1658:   int regno = REGNO (SET_DEST (x));
        !          1659:   rtx y = reg_next_use[regno];
        !          1660:   if (y != 0
        !          1661:       && BLOCK_NUM (y) == BLOCK_NUM (insn)
        !          1662:       && try_pre_increment (y, SET_DEST (PATTERN (insn)),
        !          1663:                            amount))
        !          1664:     {
        !          1665:       /* We have found a suitable auto-increment
        !          1666:         and already changed insn Y to do it.
        !          1667:         So flush this increment-instruction.  */
        !          1668:       PUT_CODE (insn, NOTE);
        !          1669:       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
        !          1670:       NOTE_SOURCE_FILE (insn) = 0;
        !          1671:       /* Count a reference to this reg for the increment
        !          1672:         insn we are deleting.  When a reg is incremented.
        !          1673:         spilling it is worse, so we want to make that
        !          1674:         less likely.  */
        !          1675:       reg_n_refs[regno] += loop_depth;
        !          1676:       reg_n_sets[regno]++;
        !          1677:       return 1;
        !          1678:     }
        !          1679:   return 0;
        !          1680: }
        !          1681: 
        !          1682: /* Try to change INSN so that it does pre-increment or pre-decrement
        !          1683:    addressing on register REG in order to add AMOUNT to REG.
        !          1684:    AMOUNT is negative for pre-decrement.
        !          1685:    Returns 1 if the change could be made.
        !          1686:    This checks all about the validity of the result of modifying INSN.  */
        !          1687: 
        !          1688: static int
        !          1689: try_pre_increment (insn, reg, amount)
        !          1690:      rtx insn, reg;
        !          1691:      int amount;
        !          1692: {
        !          1693:   register rtx use;
        !          1694: 
        !          1695:   /* Nonzero if we can try to make a pre-increment or pre-decrement.
        !          1696:      For example, addl $4,r1; movl (r1),... can become movl +(r1),...  */
        !          1697:   int pre_ok = 0;
        !          1698:   /* Nonzero if we can try to make a post-increment or post-decrement.
        !          1699:      For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
        !          1700:      It is possible for both PRE_OK and POST_OK to be nonzero if the machine
        !          1701:      supports both pre-inc and post-inc, or both pre-dec and post-dec.  */
        !          1702:   int post_ok = 0;
        !          1703: 
        !          1704:   /* Nonzero if the opportunity actually requires post-inc or post-dec.  */
        !          1705:   int do_post = 0;
        !          1706: 
        !          1707:   /* From the sign of increment, see which possibilities are conceivable
        !          1708:      on this target machine.  */
        !          1709: #ifdef HAVE_PRE_INCREMENT
        !          1710:   if (amount > 0)
        !          1711:     pre_ok = 1;
        !          1712: #endif
        !          1713: #ifdef HAVE_POST_INCREMENT
        !          1714:   if (amount > 0)
        !          1715:     post_ok = 1;
        !          1716: #endif
        !          1717: 
        !          1718: #ifdef HAVE_PRE_DECREMENT
        !          1719:   if (amount < 0)
        !          1720:     pre_ok = 1;
        !          1721: #endif
        !          1722: #ifdef HAVE_POST_DECREMENT
        !          1723:   if (amount < 0)
        !          1724:     post_ok = 1;
        !          1725: #endif
        !          1726: 
        !          1727:   if (! (pre_ok || post_ok))
        !          1728:     return 0;
        !          1729: 
        !          1730:   /* It is not safe to add a side effect to a jump insn
        !          1731:      because if the incremented register is spilled and must be reloaded
        !          1732:      there would be no way to store the incremented value back in memory.  */
        !          1733: 
        !          1734:   if (GET_CODE (insn) == JUMP_INSN)
        !          1735:     return 0;
        !          1736: 
        !          1737:   use = 0;
        !          1738:   if (pre_ok)
        !          1739:     use = find_use_as_address (PATTERN (insn), reg, 0);
        !          1740:   if (post_ok && (use == 0 || use == (rtx) 1))
        !          1741:     {
        !          1742:       use = find_use_as_address (PATTERN (insn), reg, -amount);
        !          1743:       do_post = 1;
        !          1744:     }
        !          1745: 
        !          1746:   if (use == 0 || use == (rtx) 1)
        !          1747:     return 0;
        !          1748: 
        !          1749:   if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
        !          1750:     return 0;
        !          1751: 
        !          1752:   XEXP (use, 0) = gen_rtx (amount > 0
        !          1753:                           ? (do_post ? POST_INC : PRE_INC)
        !          1754:                           : (do_post ? POST_DEC : PRE_DEC),
        !          1755:                           Pmode, reg);
        !          1756: 
        !          1757:   /* Record that this insn now has an implicit side effect on X.  */
        !          1758:   REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_INC, reg, REG_NOTES (insn));
        !          1759:   return 1;
        !          1760: }
        !          1761: 
        !          1762: #endif /* AUTO_INC_DEC */
        !          1763: 
        !          1764: /* Find the place in the rtx X where REG is used as a memory address.
        !          1765:    Return the MEM rtx that so uses it.
        !          1766:    If PLUSCONST is nonzero, search instead for a memory address equivalent to
        !          1767:    (plus REG (const_int PLUSCONST)).
        !          1768: 
        !          1769:    If such an address does not appear, return 0.
        !          1770:    If REG appears more than once, or is used other than in such an address,
        !          1771:    return (rtx)1.  */
        !          1772: 
        !          1773: static rtx
        !          1774: find_use_as_address (x, reg, plusconst)
        !          1775:      register rtx x;
        !          1776:      rtx reg;
        !          1777:      int plusconst;
        !          1778: {
        !          1779:   enum rtx_code code = GET_CODE (x);
        !          1780:   char *fmt = GET_RTX_FORMAT (code);
        !          1781:   register int i;
        !          1782:   register rtx value = 0;
        !          1783:   register rtx tem;
        !          1784: 
        !          1785:   if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
        !          1786:     return x;
        !          1787: 
        !          1788:   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
        !          1789:       && XEXP (XEXP (x, 0), 0) == reg
        !          1790:       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
        !          1791:       && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
        !          1792:     return x;
        !          1793: 
        !          1794:   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
        !          1795:     {
        !          1796:       /* If REG occurs inside a MEM used in a bit-field reference,
        !          1797:         that is unacceptable.  */
        !          1798:       if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
        !          1799:        return (rtx) 1;
        !          1800:     }
        !          1801: 
        !          1802:   if (x == reg)
        !          1803:     return (rtx) 1;
        !          1804: 
        !          1805:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !          1806:     {
        !          1807:       if (fmt[i] == 'e')
        !          1808:        {
        !          1809:          tem = find_use_as_address (XEXP (x, i), reg, plusconst);
        !          1810:          if (value == 0)
        !          1811:            value = tem;
        !          1812:          else if (tem != 0)
        !          1813:            return (rtx) 1;
        !          1814:        }
        !          1815:       if (fmt[i] == 'E')
        !          1816:        {
        !          1817:          register int j;
        !          1818:          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
        !          1819:            {
        !          1820:              tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
        !          1821:              if (value == 0)
        !          1822:                value = tem;
        !          1823:              else if (tem != 0)
        !          1824:                return (rtx) 1;
        !          1825:            }
        !          1826:        }
        !          1827:     }
        !          1828: 
        !          1829:   return value;
        !          1830: }
        !          1831: 
        !          1832: /* Write information about registers and basic blocks into FILE.
        !          1833:    This is part of making a debugging dump.  */
        !          1834: 
        !          1835: void
        !          1836: dump_flow_info (file)
        !          1837:      FILE *file;
        !          1838: {
        !          1839:   register int i;
        !          1840:   static char *reg_class_names[] = REG_CLASS_NAMES;
        !          1841: 
        !          1842:   fprintf (file, "%d registers.\n", max_regno);
        !          1843: 
        !          1844:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !          1845:     if (reg_n_refs[i])
        !          1846:       {
        !          1847:        enum reg_class class;
        !          1848:        fprintf (file, "\nRegister %d used %d times across %d insns",
        !          1849:                 i, reg_n_refs[i], reg_live_length[i]);
        !          1850:        if (reg_basic_block[i] >= 0)
        !          1851:          fprintf (file, " in block %d", reg_basic_block[i]);
        !          1852:        if (reg_n_deaths[i] != 1)
        !          1853:          fprintf (file, "; dies in %d places", reg_n_deaths[i]);
        !          1854:        if (reg_crosses_call[i])
        !          1855:          fprintf (file, "; crosses calls");
        !          1856:        if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
        !          1857:          fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
        !          1858:        class = reg_preferred_class (i);
        !          1859:        if (class != GENERAL_REGS)
        !          1860:          {
        !          1861:            if (reg_preferred_or_nothing (i))
        !          1862:              fprintf (file, "; %s or none", reg_class_names[(int) class]);
        !          1863:            else
        !          1864:              fprintf (file, "; pref %s", reg_class_names[(int) class]);
        !          1865:          }
        !          1866:        if (REGNO_POINTER_FLAG (i))
        !          1867:          fprintf (file, "; pointer");
        !          1868:        fprintf (file, ".\n");
        !          1869:       }
        !          1870:   fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
        !          1871:   for (i = 0; i < n_basic_blocks; i++)
        !          1872:     {
        !          1873:       register rtx head, jump;
        !          1874:       register int regno;
        !          1875:       fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
        !          1876:               i,
        !          1877:               INSN_UID (basic_block_head[i]),
        !          1878:               INSN_UID (basic_block_end[i]));
        !          1879:       /* The control flow graph's storage is freed
        !          1880:         now when flow_analysis returns.
        !          1881:         Don't try to print it if it is gone.  */
        !          1882:       if (basic_block_drops_in)
        !          1883:        {
        !          1884:          fprintf (file, "Reached from blocks: ");
        !          1885:          head = basic_block_head[i];
        !          1886:          if (GET_CODE (head) == CODE_LABEL)
        !          1887:            for (jump = LABEL_REFS (head);
        !          1888:                 jump != head;
        !          1889:                 jump = LABEL_NEXTREF (jump))
        !          1890:              {
        !          1891:                register from_block = BLOCK_NUM (CONTAINING_INSN (jump));
        !          1892:                fprintf (file, " %d", from_block);
        !          1893:              }
        !          1894:          if (basic_block_drops_in[i])
        !          1895:            fprintf (file, " previous");
        !          1896:        }
        !          1897:       fprintf (file, "\nRegisters live at start:");
        !          1898:       for (regno = 0; regno < max_regno; regno++)
        !          1899:        {
        !          1900:          register int offset = regno / REGSET_ELT_BITS;
        !          1901:          register int bit = 1 << (regno % REGSET_ELT_BITS);
        !          1902:          if (basic_block_live_at_start[i][offset] & bit)
        !          1903:              fprintf (file, " %d", regno);
        !          1904:        }
        !          1905:       fprintf (file, "\n");
        !          1906:     }
        !          1907:   fprintf (file, "\n");
        !          1908: }

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