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