gcc/stupid.c

   1 /* Dummy data flow analysis for GNU compiler in nonoptimizing mode.
   2    Copyright (C) 1987, 1991, 1994, 1995 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
 427           && (GET_CODE (SET_DEST (x)) == REG
 428               || (GET_CODE (SET_DEST (x)) == SUBREG
 429                   && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
 430                   && (REGNO (SUBREG_REG (SET_DEST (x)))
 431                       >= FIRST_PSEUDO_REGISTER))))
 432         {
 433           /* Register is being assigned.  */
 434           /* If setting a SUBREG, we treat the entire reg as being set.  */
 435           if (GET_CODE (SET_DEST (x)) == SUBREG)
 436             regno = REGNO (SUBREG_REG (SET_DEST (x)));
 437           else
 438             regno = REGNO (SET_DEST (x));
 439
 440           /* For hard regs, update the where-live info.  */
 441           if (regno < FIRST_PSEUDO_REGISTER)
 442             {
 443               register int j
 444                 = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
 445
 446               while (--j >= 0)
 447                 {
 448                   regs_ever_live[regno+j] = 1;
 449                   regs_live[regno+j] = 0;
 450
 451                   /* The following line is for unused outputs;
 452                      they do get stored even though never used again.  */
 453                   MARK_LIVE_AFTER (insn, regno+j);
 454
 455                   /* When a hard reg is clobbered, mark it in use
 456                      just before this insn, so it is live all through.  */
 457                   if (code == CLOBBER && INSN_SUID (insn) > 0)
 458                     SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1],
 459                                       regno+j);
 460                 }
 461             }
 462           /* For pseudo regs, record where born, where dead, number of
 463              times used, and whether live across a call.  */
 464           else
 465             {
 466               /* Update the life-interval bounds of this pseudo reg.  */
 467
 468               /* When a pseudo-reg is CLOBBERed, it is born just before
 469                  the clobbering insn.  When setting, just after.  */
 470               int where_born = INSN_SUID (insn) - (code == CLOBBER);
 471
 472               reg_where_born[regno] = where_born;
 473
 474               /* The reg must live at least one insn even
 475                  in it is never again used--because it has to go
 476                  in SOME hard reg.  Mark it as dying after the current
 477                  insn so that it will conflict with any other outputs of
 478                  this insn.  */
 479               if (reg_where_dead[regno] < where_born + 2)
 480                 {
 481                   reg_where_dead[regno] = where_born + 2;
 482                   regs_live[regno] = 1;
 483                 }
 484
 485               /* Count the refs of this reg.  */
 486               reg_n_refs[regno]++;
 487
 488               if (last_call_suid < reg_where_dead[regno])
 489                 reg_n_calls_crossed[regno] += 1;
 490             }
 491         }
 492
 493       /* Record references from the value being set,
 494          or from addresses in the place being set if that's not a reg.
 495          If setting a SUBREG, we treat the entire reg as *used*.  */
 496       if (code == SET)
 497         {
 498           stupid_mark_refs (SET_SRC (x), insn);
 499           if (GET_CODE (SET_DEST (x)) != REG)
 500             stupid_mark_refs (SET_DEST (x), insn);
 501         }
 502       return;
 503     }
 504
 505   else if (code == SUBREG
 506            && GET_CODE (SUBREG_REG (x)) == REG
 507            && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
 508            && (GET_MODE_SIZE (GET_MODE (x))
 509                != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
 510            && (INTEGRAL_MODE_P (GET_MODE (x))
 511                || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x)))))
 512     regs_change_size[REGNO (SUBREG_REG (x))] = 1;
 513
 514   /* Register value being used, not set.  */
 515
 516   else if (code == REG)
 517     {
 518       regno = REGNO (x);
 519       if (regno < FIRST_PSEUDO_REGISTER)
 520         {
 521           /* Hard reg: mark it live for continuing scan of previous insns.  */
 522           register int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
 523           while (--j >= 0)
 524             {
 525               regs_ever_live[regno+j] = 1;
 526               regs_live[regno+j] = 1;
 527             }
 528         }
 529       else
 530         {
 531           /* Pseudo reg: record first use, last use and number of uses.  */
 532
 533           reg_where_born[regno] = INSN_SUID (insn);
 534           reg_n_refs[regno]++;
 535           if (regs_live[regno] == 0)
 536             {
 537               regs_live[regno] = 1;
 538               reg_where_dead[regno] = INSN_SUID (insn);
 539             }
 540         }
 541       return;
 542     }
 543
 544   /* Recursive scan of all other rtx's.  */
 545
 546   fmt = GET_RTX_FORMAT (code);
 547   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 548     {
 549       if (fmt[i] == 'e')
 550         stupid_mark_refs (XEXP (x, i), insn);
 551       if (fmt[i] == 'E')
 552         {
 553           register int j;
 554           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 555             stupid_mark_refs (XVECEXP (x, i, j), insn);
 556         }
 557     }
 558 }