Return to stupid.c CVS log

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

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

1.1     ! root        1: /* Dummy data flow analysis for GNU compiler in nonoptimizing mode.
        !             2:    Copyright (C) 1987 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 performs stupid register allocation, which is used
        !            23:    when cc1 gets the -noreg switch (which is when cc does not get -O).
        !            24: 
        !            25:    Stupid register allocation goes in place of the the flow_analysis,
        !            26:    local_alloc and global_alloc passes.  combine_instructions cannot
        !            27:    be done with stupid allocation because the data flow info that it needs
        !            28:    is not computed here.
        !            29: 
        !            30:    In stupid allocation, the only user-defined variables that can
        !            31:    go in registers are those declared "register".  They are assumed
        !            32:    to have a life span equal to their scope.  Other user variables
        !            33:    are given stack slots in the rtl-generation pass and are not
        !            34:    represented as pseudo regs.  A compiler-generated temporary
        !            35:    is assumed to live from its first mention to its last mention.
        !            36: 
        !            37:    Since each pseudo-reg's life span is just an interval, it can be
        !            38:    represented as a pair of numbers, each of which identifies an insn by
        !            39:    its position in the function (number of insns before it).  The first
        !            40:    thing done for stupid allocation is to compute such a number for each
        !            41:    insn.  It is called the suid.  Then the life-interval of each
        !            42:    pseudo reg is computed.  Then the pseudo regs are ordered by priority
        !            43:    and assigned hard regs in priority order.  */
        !            44: 
        !            45: #include <stdio.h>
        !            46: #include "config.h"
        !            47: #include "rtl.h"
        !            48: #include "hard-reg-set.h"
        !            49: #include "regs.h"
        !            50: 
        !            51: /* Vector mapping INSN_UIDs to suids.
        !            52:    The suids are like uids but increase monononically always.
        !            53:    We use them to see whether a subroutine call came
        !            54:    between a variable's birth and its death.  */
        !            55: 
        !            56: static short *uid_suid;
        !            57: 
        !            58: /* Get the suid of an insn.  */
        !            59: 
        !            60: #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)])
        !            61: 
        !            62: /* Record the suid of the last CALL_INSN
        !            63:    so we can tell whether a potential combination crosses any calls.  */
        !            64: 
        !            65: static int last_call_suid;
        !            66: 
        !            67: /* Element N is suid of insn where life span of pseudo reg N ends.
        !            68:    Element is  0 if register N has not been seen yet on backward scan.  */
        !            69: 
        !            70: static short *reg_where_dead;
        !            71: 
        !            72: /* Element N is suid of insn where life span of pseudo reg N begins.  */
        !            73: 
        !            74: static short *reg_where_born;
        !            75: 
        !            76: /* Numbers of pseudo-regs to be allocated, highest priority first.  */
        !            77: 
        !            78: static short *reg_order;
        !            79: 
        !            80: /* Indexed by reg number (hard or pseudo), nonzero if register is live
        !            81:    at the current point in the instruction stream.  */
        !            82: 
        !            83: static char *regs_live;
        !            84: 
        !            85: /* Indexed by insn's suid, the set of hard regs live after that insn.  */
        !            86: 
        !            87: static HARD_REG_SET *after_insn_hard_regs;
        !            88: 
        !            89: /* Record that hard reg REGNO is live after insn INSN.  */
        !            90: 
        !            91: #define MARK_LIVE_AFTER(INSN,REGNO)  \
        !            92:   SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO))
        !            93: 
        !            94: static void stupid_mark_refs ();
        !            95: static int stupid_reg_compare ();
        !            96: 
        !            97: /* Stupid life analysis is for the case where only variables declared
        !            98:    `register' go in registers.  For this case, we mark all
        !            99:    pseudo-registers that belong to register variables as
        !           100:    dying in the last instruction of the function, and all other
        !           101:    pseudo registers as dying in the last place they are referenced.
        !           102:    Hard registers are marked as dying in the last reference before
        !           103:    the end or before each store into them.  */
        !           104: 
        !           105: void
        !           106: stupid_life_analysis (f, nregs, file)
        !           107:      rtx f;
        !           108:      int nregs;
        !           109:      FILE *file;
        !           110: {
        !           111:   register int i;
        !           112:   register rtx last, insn;
        !           113:   int max_uid;
        !           114: 
        !           115:   bzero (regs_ever_live, sizeof regs_ever_live);
        !           116: 
        !           117:   regs_live = (char *) alloca (nregs);
        !           118: 
        !           119:   /* First find the last real insn, and count the number of insns,
        !           120:      and assign insns their suids.  */
        !           121: 
        !           122:   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           123:     if (INSN_UID (insn) > i)
        !           124:       i = INSN_UID (insn);
        !           125: 
        !           126:   max_uid = i + 1;
        !           127:   uid_suid = (short *) alloca ((i + 1) * sizeof (short));
        !           128: 
        !           129:   /* Compute the mapping from uids to suids.
        !           130:      Suids are numbers assigned to insns, like uids,
        !           131:      except that suids increase monotonically through the code.  */
        !           132: 
        !           133:   last = 0;                    /* In case of empty function body */
        !           134:   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
        !           135:     {
        !           136:       if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN
        !           137:          || GET_CODE (insn) == JUMP_INSN)
        !           138:        last = insn;
        !           139:       INSN_SUID (insn) = ++i;
        !           140:     }
        !           141: 
        !           142:   last_call_suid = 0;
        !           143: 
        !           144:   max_regno = nregs;
        !           145: 
        !           146:   /* Allocate tables to record info about regs.  */
        !           147: 
        !           148:   reg_where_dead = (short *) alloca (nregs * sizeof (short));
        !           149:   bzero (reg_where_dead, nregs * sizeof (short));
        !           150: 
        !           151:   reg_where_born = (short *) alloca (nregs * sizeof (short));
        !           152:   bzero (reg_where_born, nregs * sizeof (short));
        !           153: 
        !           154:   reg_order = (short *) alloca (nregs * sizeof (short));
        !           155:   bzero (reg_order, nregs * sizeof (short));
        !           156: 
        !           157:   reg_renumber = (short *) oballoc (nregs * sizeof (short));
        !           158:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           159:     reg_renumber[i] = i;
        !           160: 
        !           161:   after_insn_hard_regs = (HARD_REG_SET *) alloca (max_uid * sizeof (HARD_REG_SET));
        !           162:   bzero (after_insn_hard_regs, max_uid * sizeof (HARD_REG_SET));
        !           163: 
        !           164:   /* Allocate and zero out many data structures
        !           165:      that will record the data from lifetime analysis.  */
        !           166: 
        !           167:   allocate_for_life_analysis ();
        !           168: 
        !           169:   for (i = 0; i < max_regno; i++)
        !           170:     {
        !           171:       reg_n_deaths[i] = 1;
        !           172:     }
        !           173: 
        !           174:   bzero (regs_live, nregs);
        !           175: 
        !           176:   /* Find where each pseudo register is born and dies,
        !           177:      by scanning all insns from the end to the start
        !           178:      and noting all mentions of the registers.
        !           179: 
        !           180:      Also find where each hard register is live
        !           181:      and record that info in after_insn_hard_regs.
        !           182:      regs_live[I] is 1 if hard reg I is live
        !           183:      at the current point in the scan.  */
        !           184: 
        !           185:   for (insn = last; insn; insn = PREV_INSN (insn))
        !           186:     {
        !           187:       register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn);
        !           188: 
        !           189:       /* Copy the info in regs_live
        !           190:         into the element of after_insn_hard_regs
        !           191:         for the current position in the rtl code.  */
        !           192: 
        !           193:       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           194:        if (regs_live[i])
        !           195:          SET_HARD_REG_BIT (*p, i);
        !           196: 
        !           197:       /* Mark all call-clobbered regs as live after each call insn
        !           198:         so that a pseudo whose life span includes this insn
        !           199:         will not go in one of them.
        !           200:         Then mark those regs as all dead for the continuing scan
        !           201:         of the insns before the call.  */
        !           202: 
        !           203:       if (GET_CODE (insn) == CALL_INSN)
        !           204:        {
        !           205:          last_call_suid = INSN_SUID (insn);
        !           206:          IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid],
        !           207:                            call_used_reg_set);
        !           208:          for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           209:            if (call_used_regs[i])
        !           210:              regs_live[i] = 0;
        !           211:        }
        !           212: 
        !           213:       /* Update which hard regs are currently live
        !           214:         and also the birth and death suids of pseudo regs
        !           215:         based on the pattern of this insn.  */
        !           216: 
        !           217:       if (GET_CODE (insn) == INSN
        !           218:          || GET_CODE (insn) == CALL_INSN
        !           219:          || GET_CODE (insn) == JUMP_INSN)
        !           220:        {
        !           221:          stupid_mark_refs (PATTERN (insn), insn);
        !           222:        }
        !           223:     }
        !           224: 
        !           225:   /* Now decide the order in which to allocate the pseudo registers.  */
        !           226: 
        !           227:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           228:     reg_order[i] = i;
        !           229: 
        !           230:   qsort (&reg_order[FIRST_PSEUDO_REGISTER],
        !           231:         max_regno - FIRST_PSEUDO_REGISTER, sizeof (short),
        !           232:         stupid_reg_compare);
        !           233: 
        !           234:   /* Now, in that order, try to find hard registers for those pseudo regs.  */
        !           235: 
        !           236:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           237:     {
        !           238:       register int r = reg_order[i];
        !           239:       enum reg_class class;
        !           240: 
        !           241:       /* Now find the best hard-register class for this pseudo register */
        !           242:       if (N_REG_CLASSES > 1)
        !           243:        class = reg_preferred_class (r);
        !           244: 
        !           245:       reg_renumber[r] = stupid_find_reg (reg_crosses_call[r], class,
        !           246:                                         PSEUDO_REGNO_MODE (r),
        !           247:                                         reg_where_born[r],
        !           248:                                         reg_where_dead[r]);
        !           249: 
        !           250:       /* If no reg available in that class,
        !           251:         try any reg.  */
        !           252:       if (reg_renumber[r] == -1)
        !           253:        reg_renumber[r] = stupid_find_reg (reg_crosses_call[r], GENERAL_REGS,
        !           254:                                           PSEUDO_REGNO_MODE (r),
        !           255:                                           reg_where_born[r],
        !           256:                                           reg_where_dead[r]);
        !           257:     }
        !           258: 
        !           259:   if (file)
        !           260:     dump_flow_info (file);
        !           261: }
        !           262: 
        !           263: /* Comparison function for qsort.
        !           264:    Returns -1 (1) if register *R1P is higher priority than *R2P.  */
        !           265: 
        !           266: static int
        !           267: stupid_reg_compare (r1p, r2p)
        !           268:      short *r1p, *r2p;
        !           269: {
        !           270:   register int r1 = *r1p, r2 = *r2p;
        !           271:   register int len1 = reg_where_dead[r1] - reg_where_born[r1];
        !           272:   register int len2 = reg_where_dead[r2] - reg_where_born[r2];
        !           273: 
        !           274:   if (len1 != len2)
        !           275:     return len2 - len1;
        !           276: 
        !           277:   return reg_n_refs[r1] - reg_n_refs[r2];
        !           278: }
        !           279: 
        !           280: /* Find a block of SIZE words of hard registers in reg_class CLASS
        !           281:    that can hold a value of machine-mode MODE
        !           282:      (but actually we test only the first of the block for holding MODE)
        !           283:    currently free from after insn whose suid is BIRTH
        !           284:    through the insn whose suid is DEATH,
        !           285:    and return the number of the first of them.
        !           286:    Return -1 if such a block cannot be found.
        !           287:    If CALL_PRESERVED is nonzero, insist on registers preserved
        !           288:    over subroutine calls, and return -1 if cannot find such.  */
        !           289: 
        !           290: static int
        !           291: stupid_find_reg (call_preserved, class, mode,
        !           292:                 born_insn, dead_insn)
        !           293:      int call_preserved;
        !           294:      enum reg_class class;
        !           295:      enum machine_mode mode;
        !           296:      int born_insn, dead_insn;
        !           297: {
        !           298:   register int i, ins;
        !           299: #ifdef HARD_REG_SET
        !           300:   register             /* Declare them register if they are scalars.  */
        !           301: #endif
        !           302:     HARD_REG_SET used, this_reg;
        !           303: 
        !           304:   COPY_HARD_REG_SET (used,
        !           305:                     call_preserved ? call_used_reg_set : fixed_reg_set);
        !           306: 
        !           307:   for (ins = born_insn; ins < dead_insn; ins++)
        !           308:     IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]);
        !           309: 
        !           310:   IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
        !           311: 
        !           312:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           313:     if (! TEST_HARD_REG_BIT (used, i)
        !           314:        && HARD_REGNO_MODE_OK (i, mode))
        !           315:       {
        !           316:        register int j;
        !           317:        register int size1 = HARD_REGNO_NREGS (i, mode);
        !           318:        for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, i + j); j++);
        !           319:        if (j == size1)
        !           320:          {
        !           321:            CLEAR_HARD_REG_SET (this_reg);
        !           322:            while (--j >= 0)
        !           323:              SET_HARD_REG_BIT (this_reg, i + j);
        !           324:            for (ins = born_insn; ins < dead_insn; ins++)
        !           325:              {
        !           326:                IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg);
        !           327:              }
        !           328:            return i;
        !           329:          }
        !           330:        i += j;                 /* Skip starting points we know will lose */
        !           331:       }
        !           332:   return -1;
        !           333: }
        !           334: 
        !           335: /* Walk X, noting all assignments and references to registers
        !           336:    and recording what they imply about life spans.
        !           337:    INSN is the current insn, supplied so we can find its suid.  */
        !           338: 
        !           339: static void
        !           340: stupid_mark_refs (x, insn)
        !           341:      rtx x, insn;
        !           342: {
        !           343:   register RTX_CODE code = GET_CODE (x);
        !           344:   register char *fmt;
        !           345:   register int regno, i;
        !           346: 
        !           347:   if (code == SET || code == CLOBBER)
        !           348:     {
        !           349:       if (SET_DEST (x) != 0 && GET_CODE (SET_DEST (x)) == REG)
        !           350:        {
        !           351:          /* Register is being assigned.  */
        !           352:          regno = REGNO (SET_DEST (x));
        !           353: 
        !           354:          /* For hard regs, update the where-live info.  */
        !           355:          if (regno < FIRST_PSEUDO_REGISTER)
        !           356:            {
        !           357:              register int j
        !           358:                = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
        !           359:              while (--j >= 0)
        !           360:                {
        !           361:                  regs_ever_live[regno+j] = 1;
        !           362:                  regs_live[regno+j] = 0;
        !           363:                  /* The following line is for unused outputs;
        !           364:                     they do get stored even though never used again.  */
        !           365:                  MARK_LIVE_AFTER (insn, regno);
        !           366:                }
        !           367:            }
        !           368:          /* For pseudo regs, record where born, where dead, number of
        !           369:             times used, and whether live across a call.  */
        !           370:          else
        !           371:            {
        !           372:              /* Update the life-interval bounds of this reg.  */
        !           373:              reg_where_born[regno] = INSN_SUID (insn);
        !           374: 
        !           375:              /* The reg must live at least one insn even
        !           376:                 if it is never again used--because it has to go
        !           377:                 in SOME hard reg.  */
        !           378:              if (reg_where_dead[regno] < INSN_SUID (insn) + 1)
        !           379:                reg_where_dead[regno] = INSN_SUID (insn) + 1;
        !           380: 
        !           381:              /* Count the refs of this reg.  */
        !           382:              reg_n_refs[regno]++;
        !           383: 
        !           384:              if (last_call_suid < reg_where_dead[regno])
        !           385:                reg_crosses_call[regno] = 1;
        !           386:            }
        !           387:        }
        !           388:       /* Record references from the value being set,
        !           389:         or from addresses in the place being set if that's not a reg.
        !           390:         If setting a SUBREG, we treat the entire reg as *used*.  */
        !           391:       if (code == SET)
        !           392:        {
        !           393:          stupid_mark_refs (SET_SRC (x), insn);
        !           394:          if (GET_CODE (SET_DEST (x)) != REG)
        !           395:            stupid_mark_refs (SET_DEST (x), insn);
        !           396:        }
        !           397:       return;
        !           398:     }
        !           399: 
        !           400:   /* Register value being used, not set.  */
        !           401: 
        !           402:   if (code == REG)
        !           403:     {
        !           404:       regno = REGNO (x);
        !           405:       if (regno < FIRST_PSEUDO_REGISTER)
        !           406:        {
        !           407:          /* Hard reg: mark it live for continuing scan of previous insns.  */
        !           408:          register int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
        !           409:          while (--j >= 0)
        !           410:            {
        !           411:              regs_ever_live[regno+j] = 1;
        !           412:              regs_live[regno+j] = 1;
        !           413:            }
        !           414:        }
        !           415:       else
        !           416:        {
        !           417:          /* Pseudo reg: record first use, last use and number of uses.  */
        !           418: 
        !           419:          reg_where_born[regno] = INSN_SUID (insn);
        !           420:          reg_n_refs[regno]++;
        !           421:          if (regs_live[regno] == 0)
        !           422:            {
        !           423:              regs_live[regno] = 1;
        !           424:              reg_where_dead[regno] = INSN_SUID (insn);
        !           425:            }
        !           426:        }
        !           427:       return;
        !           428:     }
        !           429: 
        !           430:   /* Recursive scan of all other rtx's.  */
        !           431: 
        !           432:   fmt = GET_RTX_FORMAT (code);
        !           433:   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
        !           434:     {
        !           435:       if (fmt[i] == 'e')
        !           436:        stupid_mark_refs (XEXP (x, i), insn);
        !           437:       if (fmt[i] == 'E')
        !           438:        {
        !           439:          register int j;
        !           440:          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
        !           441:            stupid_mark_refs (XVECEXP (x, i, j), insn);
        !           442:        }
        !           443:     }
        !           444: }

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