gcc/stupid.c

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