gcc/stupid.c

   1 /* Dummy data flow analysis for GNU compiler in nonoptimizing mode.
   2    Copyright (C) 1987, 1991, 1994 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  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 #include "flags.h"
  51 \f
  52 /* Vector mapping INSN_UIDs to suids.
  53    The suids are like uids but increase monotonically always.
  54    We use them to see whether a subroutine call came
  55    between a variable's birth and its death.  */
  56
  57 static int *uid_suid;
  58
  59 /* Get the suid of an insn.  */
  60
  61 #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)])
  62
  63 /* Record the suid of the last CALL_INSN
  64    so we can tell whether a pseudo reg crosses any calls.  */
  65
  66 static int last_call_suid;
  67
  68 /* Element N is suid of insn where life span of pseudo reg N ends.
  69    Element is  0 if register N has not been seen yet on backward scan.  */
  70
  71 static int *reg_where_dead;
  72
  73 /* Element N is suid of insn where life span of pseudo reg N begins.  */
  74
  75 static int *reg_where_born;
  76
  77 /* Numbers of pseudo-regs to be allocated, highest priority first.  */
  78
  79 static int *reg_order;
  80
  81 /* Indexed by reg number (hard or pseudo), nonzero if register is live
  82    at the current point in the instruction stream.  */
  83
  84 static char *regs_live;
  85
  86 /* Indexed by reg number, nonzero if reg was used in a SUBREG that changes
  87    its size.  */
  88
  89 static char *regs_change_size;
  90
  91 /* Indexed by insn's suid, the set of hard regs live after that insn.  */
  92
  93 static HARD_REG_SET *after_insn_hard_regs;
  94
  95 /* Record that hard reg REGNO is live after insn INSN.  */
  96
  97 #define MARK_LIVE_AFTER(INSN,REGNO)  \
  98   SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO))
  99
 100 static int stupid_reg_compare   PROTO((int *, int *));
 101 static int stupid_find_reg      PROTO((int, enum reg_class, enum machine_mode,
 102                                        int, int, int));
 103 static void stupid_mark_refs    PROTO((rtx, rtx));
 104 \f
 105 /* Stupid life analysis is for the case where only variables declared
 106    `register' go in registers.  For this case, we mark all
 107    pseudo-registers that belong to register variables as
 108    dying in the last instruction of the function, and all other
 109    pseudo registers as dying in the last place they are referenced.
 110    Hard registers are marked as dying in the last reference before
 111    the end or before each store into them.  */
 112
 113 void
 114 stupid_life_analysis (f, nregs, file)
 115      rtx f;
 116      int nregs;
 117      FILE *file;
 118 {
 119   register int i;
 120   register rtx last, insn;
 121   int max_uid, max_suid;
 122
 123   bzero (regs_ever_live, sizeof regs_ever_live);
 124
 125   regs_live = (char *) alloca (nregs);
 126
 127   /* First find the last real insn, and count the number of insns,
 128      and assign insns their suids.  */
 129
 130   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
 131     if (INSN_UID (insn) > i)
 132       i = INSN_UID (insn);
 133
 134   max_uid = i + 1;
 135   uid_suid = (int *) alloca ((i + 1) * sizeof (int));
 136
 137   /* Compute the mapping from uids to suids.
 138      Suids are numbers assigned to insns, like uids,
 139      except that suids increase monotonically through the code.  */
 140
 141   last = 0;                     /* In case of empty function body */
 142   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
 143     {
 144       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 145         last = insn;
 146
 147       INSN_SUID (insn) = ++i;
 148     }
 149
 150   last_call_suid = i + 1;
 151   max_suid = i + 1;
 152
 153   max_regno = nregs;
 154
 155   /* Allocate tables to record info about regs.  */
 156
 157   reg_where_dead = (int *) alloca (nregs * sizeof (int));
 158   bzero ((char *) reg_where_dead, nregs * sizeof (int));
 159
 160   reg_where_born = (int *) alloca (nregs * sizeof (int));
 161   bzero ((char *) reg_where_born, nregs * sizeof (int));
 162
 163   reg_order = (int *) alloca (nregs * sizeof (int));
 164   bzero ((char *) reg_order, nregs * sizeof (int));
 165
 166   regs_change_size = (char *) alloca (nregs * sizeof (char));
 167   bzero ((char *) regs_change_size, nregs * sizeof (char));
 168
 169   reg_renumber = (short *) oballoc (nregs * sizeof (short));
 170   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 171     reg_renumber[i] = i;
 172
 173   for (i = FIRST_VIRTUAL_REGISTER; i < max_regno; i++)
 174     reg_renumber[i] = -1;
 175
 176   after_insn_hard_regs
 177     = (HARD_REG_SET *) alloca (max_suid * sizeof (HARD_REG_SET));
 178
 179   bzero ((char *) after_insn_hard_regs, max_suid * sizeof (HARD_REG_SET));
 180
 181   /* Allocate and zero out many data structures
 182      that will record the data from lifetime analysis.  */
 183
 184   allocate_for_life_analysis ();
 185
 186   for (i = 0; i < max_regno; i++)
 187     reg_n_deaths[i] = 1;
 188
 189   bzero (regs_live, nregs);
 190
 191   /* Find where each pseudo register is born and dies,
 192      by scanning all insns from the end to the start
 193      and noting all mentions of the registers.
 194
 195      Also find where each hard register is live
 196      and record that info in after_insn_hard_regs.
 197      regs_live[I] is 1 if hard reg I is live
 198      at the current point in the scan.  */
 199
 200   for (insn = last; insn; insn = PREV_INSN (insn))
 201     {
 202       register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn);
 203
 204       /* Copy the info in regs_live into the element of after_insn_hard_regs
 205          for the current position in the rtl code.  */
 206
 207       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 208         if (regs_live[i])
 209           SET_HARD_REG_BIT (*p, i);
 210
 211       /* Update which hard regs are currently live
 212          and also the birth and death suids of pseudo regs
 213          based on the pattern of this insn.  */
 214
 215       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 216         stupid_mark_refs (PATTERN (insn), insn);
 217
 218       /* Mark all call-clobbered regs as live after each call insn
 219          so that a pseudo whose life span includes this insn
 220          will not go in one of them.
 221          Then mark those regs as all dead for the continuing scan
 222          of the insns before the call.  */
 223
 224       if (GET_CODE (insn) == CALL_INSN)
 225         {
 226           last_call_suid = INSN_SUID (insn);
 227           IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid],
 228                             call_used_reg_set);
 229
 230           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 231             if (call_used_regs[i])
 232               regs_live[i] = 0;
 233
 234           /* It is important that this be done after processing the insn's
 235              pattern because we want the function result register to still
 236              be live if it's also used to pass arguments.  */
 237           stupid_mark_refs (CALL_INSN_FUNCTION_USAGE (insn), insn);
 238         }
 239     }
 240
 241   /* Now decide the order in which to allocate the pseudo registers.  */
 242
 243   for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
 244     reg_order[i] = i;
 245
 246   qsort (&reg_order[LAST_VIRTUAL_REGISTER + 1],
 247          max_regno - LAST_VIRTUAL_REGISTER - 1, sizeof (int),
 248          stupid_reg_compare);
 249
 250   /* Now, in that order, try to find hard registers for those pseudo regs.  */
 251
 252   for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
 253     {
 254       register int r = reg_order[i];
 255
 256       /* Some regnos disappear from the rtl.  Ignore them to avoid crash.  */
 257       if (regno_reg_rtx[r] == 0)
 258         continue;
 259
 260       /* Now find the best hard-register class for this pseudo register */
 261       if (N_REG_CLASSES > 1)
 262         reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r],
 263                                            reg_preferred_class (r),
 264                                            PSEUDO_REGNO_MODE (r),
 265                                            reg_where_born[r],
 266                                            reg_where_dead[r],
 267                                            regs_change_size[r]);
 268
 269       /* If no reg available in that class, try alternate class.  */
 270       if (reg_renumber[r] == -1 && reg_alternate_class (r) != NO_REGS)
 271         reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r],
 272                                            reg_alternate_class (r),
 273                                            PSEUDO_REGNO_MODE (r),
 274                                            reg_where_born[r],
 275                                            reg_where_dead[r],
 276                                            regs_change_size[r]);
 277     }
 278
 279   if (file)
 280     dump_flow_info (file);
 281 }
 282
 283 /* Comparison function for qsort.
 284    Returns -1 (1) if register *R1P is higher priority than *R2P.  */
 285
 286 static int
 287 stupid_reg_compare (r1p, r2p)
 288      int *r1p, *r2p;
 289 {
 290   register int r1 = *r1p, r2 = *r2p;
 291   register int len1 = reg_where_dead[r1] - reg_where_born[r1];
 292   register int len2 = reg_where_dead[r2] - reg_where_born[r2];
 293   int tem;
 294
 295   tem = len2 - len1;
 296   if (tem != 0)
 297     return tem;
 298
 299   tem = reg_n_refs[r1] - reg_n_refs[r2];
 300   if (tem != 0)
 301     return tem;
 302
 303   /* If regs are equally good, sort by regno,
 304      so that the results of qsort leave nothing to chance.  */
 305   return r1 - r2;
 306 }
 307 \f
 308 /* Find a block of SIZE words of hard registers in reg_class CLASS
 309    that can hold a value of machine-mode MODE
 310      (but actually we test only the first of the block for holding MODE)
 311    currently free from after insn whose suid is BIRTH
 312    through the insn whose suid is DEATH,
 313    and return the number of the first of them.
 314    Return -1 if such a block cannot be found.
 315
 316    If CALL_PRESERVED is nonzero, insist on registers preserved
 317    over subroutine calls, and return -1 if cannot find such.
 318
 319    If CHANGES_SIZE is nonzero, it means this register was used as the
 320    operand of a SUBREG that changes its size.  */
 321
 322 static int
 323 stupid_find_reg (call_preserved, class, mode,
 324                  born_insn, dead_insn, changes_size)
 325      int call_preserved;
 326      enum reg_class class;
 327      enum machine_mode mode;
 328      int born_insn, dead_insn;
 329      int changes_size;
 330 {
 331   register int i, ins;
 332 #ifdef HARD_REG_SET
 333   register              /* Declare them register if they are scalars.  */
 334 #endif
 335     HARD_REG_SET used, this_reg;
 336 #ifdef ELIMINABLE_REGS
 337   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
 338 #endif
 339
 340   COPY_HARD_REG_SET (used,
 341                      call_preserved ? call_used_reg_set : fixed_reg_set);
 342
 343 #ifdef ELIMINABLE_REGS
 344   for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
 345     SET_HARD_REG_BIT (used, eliminables[i].from);
 346 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
 347   SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
 348 #endif
 349 #else
 350   SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
 351 #endif
 352
 353   for (ins = born_insn; ins < dead_insn; ins++)
 354     IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]);
 355
 356   IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
 357
 358 #ifdef CLASS_CANNOT_CHANGE_SIZE
 359   if (changes_size)
 360     IOR_HARD_REG_SET (used,
 361                       reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
 362 #endif
 363
 364   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 365     {
 366 #ifdef REG_ALLOC_ORDER
 367       int regno = reg_alloc_order[i];
 368 #else
 369       int regno = i;
 370 #endif
 371
 372       /* If a register has screwy overlap problems,
 373          don't use it at all if not optimizing.
 374          Actually this is only for the 387 stack register,
 375          and it's because subsequent code won't work.  */
 376 #ifdef OVERLAPPING_REGNO_P
 377       if (OVERLAPPING_REGNO_P (regno))
 378         continue;
 379 #endif
 380
 381       if (! TEST_HARD_REG_BIT (used, regno)
 382           && HARD_REGNO_MODE_OK (regno, mode))
 383         {
 384           register int j;
 385           register int size1 = HARD_REGNO_NREGS (regno, mode);
 386           for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
 387           if (j == size1)
 388             {
 389               CLEAR_HARD_REG_SET (this_reg);
 390               while (--j >= 0)
 391                 SET_HARD_REG_BIT (this_reg, regno + j);
 392               for (ins = born_insn; ins < dead_insn; ins++)
 393                 {
 394                   IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg);
 395                 }
 396               return regno;
 397             }
 398 #ifndef REG_ALLOC_ORDER
 399           i += j;               /* Skip starting points we know will lose */
 400 #endif
 401         }
 402     }
 403
 404   return -1;
 405 }
 406 \f
 407 /* Walk X, noting all assignments and references to registers
 408    and recording what they imply about life spans.
 409    INSN is the current insn, supplied so we can find its suid.  */
 410
 411 static void
 412 stupid_mark_refs (x, insn)
 413      rtx x, insn;
 414 {
 415   register RTX_CODE code;
 416   register char *fmt;
 417   register int regno, i;
 418
 419   if (x == 0)
 420     return;
 421
 422   code = GET_CODE (x);
 423
 424   if (code == SET || code == CLOBBER)
 425     {
 426       if (SET_DEST (x) != 0 && GET_CODE (SET_DEST (x)) == REG)
 427         {
 428           /* Register is being assigned.  */
 429           regno = REGNO (SET_DEST (x));
 430
 431           /* For hard regs, update the where-live info.  */
 432           if (regno < FIRST_PSEUDO_REGISTER)
 433             {
 434               register int j
 435                 = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
 436
 437               while (--j >= 0)
 438                 {
 439                   regs_ever_live[regno+j] = 1;
 440                   regs_live[regno+j] = 0;
 441
 442                   /* The following line is for unused outputs;
 443                      they do get stored even though never used again.  */
 444                   MARK_LIVE_AFTER (insn, regno);
 445
 446                   /* When a hard reg is clobbered, mark it in use
 447                      just before this insn, so it is live all through.  */
 448                   if (code == CLOBBER && INSN_SUID (insn) > 0)
 449                     SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1],
 450                                       regno);
 451                 }
 452             }
 453           /* For pseudo regs, record where born, where dead, number of
 454              times used, and whether live across a call.  */
 455           else
 456             {
 457               /* Update the life-interval bounds of this pseudo reg.  */
 458
 459               /* When a pseudo-reg is CLOBBERed, it is born just before
 460                  the clobbering insn.  When setting, just after.  */
 461               int where_born = INSN_SUID (insn) - (code == CLOBBER);
 462
 463               reg_where_born[regno] = where_born;
 464
 465               /* The reg must live at least one insn even
 466                  in it is never again used--because it has to go
 467                  in SOME hard reg.  Mark it as dying after the current
 468                  insn so that it will conflict with any other outputs of
 469                  this insn.  */
 470               if (reg_where_dead[regno] < where_born + 2)
 471                 {
 472                   reg_where_dead[regno] = where_born + 2;
 473                   regs_live[regno] = 1;
 474                 }
 475
 476               /* Count the refs of this reg.  */
 477               reg_n_refs[regno]++;
 478
 479               if (last_call_suid < reg_where_dead[regno])
 480                 reg_n_calls_crossed[regno] += 1;
 481             }
 482         }
 483
 484       /* Record references from the value being set,
 485          or from addresses in the place being set if that's not a reg.
 486          If setting a SUBREG, we treat the entire reg as *used*.  */
 487       if (code == SET)
 488         {
 489           stupid_mark_refs (SET_SRC (x), insn);
 490           if (GET_CODE (SET_DEST (x)) != REG)
 491             stupid_mark_refs (SET_DEST (x), insn);
 492         }
 493       return;
 494     }
 495
 496   else if (code == SUBREG
 497            && GET_CODE (SUBREG_REG (x)) == REG
 498            && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
 499            && (GET_MODE_SIZE (GET_MODE (x))
 500                != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
 501            && (INTEGRAL_MODE_P (GET_MODE (x))
 502                || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x)))))
 503     regs_change_size[REGNO (SUBREG_REG (x))] = 1;
 504
 505   /* Register value being used, not set.  */
 506
 507   else if (code == REG)
 508     {
 509       regno = REGNO (x);
 510       if (regno < FIRST_PSEUDO_REGISTER)
 511         {
 512           /* Hard reg: mark it live for continuing scan of previous insns.  */
 513           register int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
 514           while (--j >= 0)
 515             {
 516               regs_ever_live[regno+j] = 1;
 517               regs_live[regno+j] = 1;
 518             }
 519         }
 520       else
 521         {
 522           /* Pseudo reg: record first use, last use and number of uses.  */
 523
 524           reg_where_born[regno] = INSN_SUID (insn);
 525           reg_n_refs[regno]++;
 526           if (regs_live[regno] == 0)
 527             {
 528               regs_live[regno] = 1;
 529               reg_where_dead[regno] = INSN_SUID (insn);
 530             }
 531         }
 532       return;
 533     }
 534
 535   /* Recursive scan of all other rtx's.  */
 536
 537   fmt = GET_RTX_FORMAT (code);
 538   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 539     {
 540       if (fmt[i] == 'e')
 541         stupid_mark_refs (XEXP (x, i), insn);
 542       if (fmt[i] == 'E')
 543         {
 544           register int j;
 545           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 546             stupid_mark_refs (XVECEXP (x, i, j), insn);
 547         }
 548     }
 549 }