gcc/regrename.c

   1 /* Register renaming for the GNU compiler.
   2    Copyright (C) 2000 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 #include "config.h"
  22 #include "system.h"
  23 #include "tree.h"
  24 #include "rtl.h"
  25 #include "basic-block.h"
  26 #include "insn-config.h"
  27 #include "regs.h"
  28 #include "hard-reg-set.h"
  29 #include "flags.h"
  30 #include "output.h"
  31 #include "function.h"
  32 #include "recog.h"
  33 #include "resource.h"
  34
  35 static const char *const reg_class_names[] = REG_CLASS_NAMES;
  36
  37 /* ??? Consider a more sparse data structure? */
  38 typedef struct def_uses
  39   {
  40     /* high bound of defs and uses */
  41     int high_bound;
  42
  43     /* 1 if insn y defines a reg whose use crosses a call
  44        y is the ordinal position of the insn within the block */
  45     sbitmap require_call_save_reg;
  46
  47     /* REGNO x INSN y  1 if insn y sets reg x */
  48     sbitmap *defs;
  49
  50     /* REGNO x INSN y  The register class for this def */
  51     enum reg_class *def_class;
  52
  53     /* REGNO x INSN y  1 if insn y uses reg x */
  54     sbitmap *uses;
  55
  56     /* REGNO x INSN y  The register class for this use */
  57     enum reg_class *use_class;
  58   }
  59 def_uses;
  60
  61 #define DU_REG_CLASS(rc,r,high_bound,i) (rc[r * high_bound + i])
  62
  63 typedef struct ext_basic_blocks
  64   {
  65     /* n_basic_blocks x n_basic_blocks y  1 if bb y is in extended bb
  66        having entry x */
  67     sbitmap *basic_block;
  68
  69     /* n_basic_blocks x n_basic_blocks y  1 if bb y is an exit block */
  70     sbitmap *exit;
  71   }
  72 ext_basic_blocks;
  73
  74 #define UID_RUID_HIGH_BOUND 64
  75 #define DESTINATION 1
  76 #define SOURCE 2
  77
  78 static void build_def_use               PARAMS ((int, ext_basic_blocks *,
  79                                                  HARD_REG_SET *, def_uses *,
  80                                                  sbitmap *));
  81 static int replace_reg_in_block         PARAMS ((def_uses *, varray_type *,
  82                                                  int, rtx, unsigned int));
  83 static int consider_def                 PARAMS ((rtx, int, def_uses *, int));
  84 static int consider_available           PARAMS ((rtx, int, HARD_REG_SET *,
  85                                                  int, def_uses *, int));
  86 static rtx rr_replace_reg               PARAMS ((rtx, rtx, rtx, int, rtx,
  87                                                  int *));
  88 static int consider_use                 PARAMS ((rtx, int, int, int));
  89 static int condmove_p                   PARAMS ((rtx));
  90 static void dump_def_use_chain          PARAMS ((HARD_REG_SET *, def_uses *,
  91                                                  varray_type *));
  92 static void dump_ext_bb_info            PARAMS ((int, ext_basic_blocks *));
  93 static void find_ext_basic_blocks       PARAMS ((ext_basic_blocks *));
  94 static void find_one_ext_basic_block    PARAMS ((int, basic_block, sbitmap *,
  95                                                  ext_basic_blocks *));
  96 static enum reg_class get_reg_class     PARAMS ((rtx, rtx, int,
  97                                                  enum reg_class));
  98 static rtx regno_first_use_in           PARAMS ((unsigned int, rtx));
  99 \f
 100 void
 101 regrename_optimize ()
 102 {
 103   int b, eb, i, inum, r, rc, replace_ok;
 104   rtx insn;
 105   def_uses du;
 106   ext_basic_blocks ebb;
 107
 108   /* Registers used in a given class */
 109   HARD_REG_SET class_regs;
 110
 111   /* Registers available for use as renaming registers */
 112   HARD_REG_SET avail_regs;
 113
 114   /* Registers used in the block */
 115   HARD_REG_SET regs_used;
 116
 117   /* Registers which have been used as renaming registers */
 118   HARD_REG_SET renamed_regs;
 119
 120   HARD_REG_SET global_live_at_end, global_live_at_start;
 121
 122   HARD_REG_SET null_bitmap, tmp_bitmap;
 123
 124   /* 1 if insn y sets a register which is live at the end of the block */
 125   sbitmap defs_live_exit;
 126
 127   /* Mapping from insn y (ordinal position in block) to INSN_UID */
 128   varray_type uid_ruid;
 129
 130   /* Mapping from insn y (ordinal position in block) to block id */
 131   varray_type uid_rbid;
 132
 133   /* Ordinal position in block of defining insn */
 134   int *def_idx;
 135
 136   VARRAY_RTX_INIT (uid_ruid, UID_RUID_HIGH_BOUND + 1, "uid_ruid");
 137   VARRAY_LONG_INIT (uid_rbid, UID_RUID_HIGH_BOUND + 1, "uid_rbid");
 138
 139   ebb.basic_block
 140     = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 141   sbitmap_vector_zero (ebb.basic_block, n_basic_blocks);
 142   ebb.exit
 143     = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 144   sbitmap_vector_zero (ebb.exit, n_basic_blocks);
 145
 146   find_ext_basic_blocks (&ebb);
 147
 148   du.def_class = du.use_class = 0;
 149
 150   /* Build uid_ruid and uid_rbid for this extended basic block */
 151   for (b = 0; b < n_basic_blocks; b++)
 152     if (TEST_BIT (ebb.basic_block[b], b))
 153       {
 154         for (eb = du.high_bound = 0; eb < n_basic_blocks; eb++)
 155           if (TEST_BIT (ebb.basic_block[b], eb))
 156             {
 157               basic_block bb = BASIC_BLOCK (eb);
 158
 159               /* Calculate high bound for uid_ruid and allocate if necessary */
 160               for (insn = bb->head;
 161                    insn != NEXT_INSN (bb->end);
 162                    du.high_bound++, insn = NEXT_INSN (insn))
 163                 {
 164                   int uid_ruid_high_bound = VARRAY_SIZE (uid_ruid);
 165
 166                   if (du.high_bound + 4 >= uid_ruid_high_bound)
 167                     {
 168                       VARRAY_GROW (uid_ruid, uid_ruid_high_bound * 2);
 169                       VARRAY_GROW (uid_rbid, uid_ruid_high_bound * 2);
 170                     }
 171
 172                   VARRAY_RTX (uid_ruid, du.high_bound) = insn;
 173                   VARRAY_LONG (uid_rbid, du.high_bound) = eb;
 174                 }
 175             }
 176
 177         CLEAR_HARD_REG_SET (null_bitmap);
 178         CLEAR_HARD_REG_SET (class_regs);
 179         CLEAR_HARD_REG_SET (regs_used);
 180         CLEAR_HARD_REG_SET (avail_regs);
 181         CLEAR_HARD_REG_SET (tmp_bitmap);
 182         CLEAR_HARD_REG_SET (renamed_regs);
 183
 184         du.defs
 185           = sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER, du.high_bound + 1);
 186         sbitmap_vector_zero (du.defs, FIRST_PSEUDO_REGISTER);
 187         du.uses
 188           = sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER, du.high_bound + 1);
 189         sbitmap_vector_zero (du.uses, FIRST_PSEUDO_REGISTER);
 190         du.require_call_save_reg = sbitmap_alloc (du.high_bound + 1);
 191         sbitmap_zero (du.require_call_save_reg);
 192         defs_live_exit = sbitmap_alloc (du.high_bound + 1);
 193         sbitmap_zero (defs_live_exit);
 194
 195         du.def_class
 196           = xrealloc (du.def_class,
 197                       (sizeof (enum reg_class) * FIRST_PSEUDO_REGISTER
 198                        * du.high_bound));
 199
 200         du.use_class
 201           = xrealloc (du.use_class,
 202                       (sizeof (enum reg_class) * FIRST_PSEUDO_REGISTER
 203                        * du.high_bound));
 204
 205         build_def_use (b, &ebb, &regs_used, &du, &defs_live_exit);
 206
 207         if (rtl_dump_file)
 208           {
 209             dump_ext_bb_info (b, &ebb);
 210             dump_def_use_chain (&global_live_at_end, &du, &uid_ruid);
 211           }
 212
 213         /* Available registers are not: used in the block, live at the start,
 214            live at the end, a register we've renamed to. */
 215         /* ??? The current algorithm is pessimistic for extended basic blocks
 216            as it just treats them as a big basic block. */
 217
 218         COPY_HARD_REG_SET (tmp_bitmap, regs_used);
 219         REG_SET_TO_HARD_REG_SET (global_live_at_start,
 220                                  BASIC_BLOCK (b)->global_live_at_start);
 221         IOR_HARD_REG_SET (tmp_bitmap, global_live_at_start);
 222         for (eb = 0; eb < n_basic_blocks; eb++)
 223           if (TEST_BIT (ebb.basic_block[b], eb))
 224             {
 225               basic_block bb = BASIC_BLOCK (eb);
 226
 227               REG_SET_TO_HARD_REG_SET (global_live_at_end,
 228                                        bb->global_live_at_end);
 229               IOR_HARD_REG_SET (tmp_bitmap, global_live_at_end);
 230             }
 231
 232         def_idx = xcalloc (du.high_bound, sizeof (int));
 233
 234         /* Only consider registers in this extended block and in this class
 235            that are defined more than once.  Replace them if permissible. */
 236         for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 237           {
 238             int avail_reg, ar_idx, def, def_cnt = 0, use_idx, call_idx;
 239
 240             if (!TEST_HARD_REG_BIT (regs_used, r)
 241                 || fixed_regs[r]
 242                 || r == FRAME_POINTER_REGNUM)
 243               continue;
 244
 245             /* Find def_idx[N] where hbound of N is the number of
 246                definitions of this register in this block. and def_idx
 247                is the ordinal position of this insn in the block. */
 248             for (i = 0, def_idx[def_cnt] = 0; i < du.high_bound; i++)
 249               if (TEST_BIT (du.defs[r], i)
 250                   && consider_def (VARRAY_RTX (uid_ruid, i), r, &du, i))
 251                 {
 252                   int first_use = 1;
 253                   def_idx[def_cnt] = i;
 254
 255                   /* Only consider definitions that have a use. */
 256                   for (use_idx = i + 1; use_idx < du.high_bound; use_idx++)
 257                     {
 258                       if (TEST_BIT (du.uses[r], use_idx))
 259                         {
 260                           if (consider_use (VARRAY_RTX (uid_ruid, use_idx), r,
 261                                             VARRAY_LONG (uid_rbid, i),
 262                                             VARRAY_LONG (uid_rbid, use_idx)))
 263                             {
 264                               if (first_use)
 265                                 {
 266                                   first_use = 0;
 267                                   def_cnt++;
 268                                 }
 269                             }
 270                           else
 271                             {
 272                               /* Don't consider def if we don't want this
 273                                  use.  */
 274                               if (!first_use)
 275                                 def_cnt--;
 276
 277                               break;
 278                             }
 279                         }
 280
 281                       if (TEST_BIT (du.defs[r], use_idx))
 282                         break;
 283                     }
 284
 285                   /* Scan until the next def to avoid renaming
 286                      parameter registers. */
 287                   /* ??? consider using CALL_INSN_FUNCTION_USAGE */
 288                   for (call_idx = i; call_idx <= use_idx; call_idx++)
 289                     if (VARRAY_RTX (uid_ruid, call_idx)
 290                         && (GET_CODE (VARRAY_RTX (uid_ruid, call_idx))
 291                             == CALL_INSN))
 292                       SET_BIT (du.require_call_save_reg, i);
 293                 }
 294
 295             if (def_cnt < 2)
 296               continue;
 297
 298             /* We have more than one def so rename until we exhaust
 299                renaming registers. */
 300             /* ??? Should we continue renaming round robin when we exhaust
 301                renaming registers? */
 302             for (def = 0; def < def_cnt - 1; def++)
 303               {
 304                 if (!TEST_BIT (defs_live_exit, def_idx[def])
 305                     && (GET_RTX_CLASS
 306                         (GET_CODE (VARRAY_RTX (uid_ruid,
 307                                                def_idx[def]))) == 'i'))
 308                   {
 309                     rtx reg_use
 310                       = regno_first_use_in
 311                         (r, PATTERN (VARRAY_RTX (uid_ruid, def_idx[def])));
 312
 313                     if (!reg_use)
 314                       break;
 315 #ifdef STACK_REGS
 316                     /* Don't bother with stacked float registers */
 317                     if (GET_MODE_CLASS (GET_MODE (reg_use)) == MODE_FLOAT)
 318                       break;
 319 #endif
 320                     rc = (int) DU_REG_CLASS (du.def_class,
 321                                              r, du.high_bound, def_idx[def]);
 322                     COPY_HARD_REG_SET (avail_regs,
 323                                    reg_class_contents[(enum reg_class) rc]);
 324                     AND_COMPL_HARD_REG_SET (avail_regs, tmp_bitmap);
 325                     AND_COMPL_HARD_REG_SET (avail_regs, renamed_regs);
 326
 327                     /* No available registers in this class */
 328                     GO_IF_HARD_REG_EQUAL (avail_regs, null_bitmap,
 329                                           no_available_regs);
 330
 331                     for (ar_idx = 0; ar_idx < FIRST_PSEUDO_REGISTER
 332                          && TEST_HARD_REG_BIT (avail_regs, ar_idx); ar_idx++)
 333                       ;
 334
 335                     if (ar_idx == FIRST_PSEUDO_REGISTER)
 336                       goto no_available_regs;
 337
 338                     /* Only try register renaming if there is an available
 339                        register in this class. */
 340                     for (ar_idx = 0; ar_idx < FIRST_PSEUDO_REGISTER; ar_idx++)
 341                       {
 342 #ifdef REG_ALLOC_ORDER
 343                         avail_reg = reg_alloc_order[ar_idx];
 344 #else
 345                         avail_reg = ar_idx;
 346 #endif
 347                         if (consider_available (reg_use, avail_reg,
 348                                                 &avail_regs, rc, &du,
 349                                                 def_idx[def]))
 350                           break;
 351                       }
 352
 353                     if (ar_idx == FIRST_PSEUDO_REGISTER)
 354                       {
 355                         if (rtl_dump_file)
 356                           {
 357                             fprintf (rtl_dump_file,
 358                                      "Register %s in class %s",
 359                                      reg_names[r], reg_class_names[rc]);
 360                             fprintf (rtl_dump_file,
 361                                      " in insn %d",
 362                                      INSN_UID (VARRAY_RTX (uid_ruid,
 363                                                            def_idx[def])));
 364
 365                             if (TEST_BIT (du.require_call_save_reg,
 366                                           def_idx[def]))
 367                               fprintf (rtl_dump_file, " crosses a call");
 368
 369                             fprintf (rtl_dump_file,
 370                                      ". No available registers\n");
 371                           }
 372
 373                         goto try_next_def;
 374                       }
 375
 376                     SET_HARD_REG_BIT (renamed_regs, avail_reg);
 377                     CLEAR_HARD_REG_BIT (avail_regs, avail_reg);
 378
 379                     /* Replace in destination.  Replace in source for
 380                        remainder of block until new register is defined
 381                        again */
 382                     replace_ok
 383                       = replace_reg_in_block (&du, &uid_ruid, def_idx[def],
 384                                               reg_use, avail_reg);
 385
 386                     /* Replace failed, so restore previous register */
 387                     if (!replace_ok)
 388                       {
 389                         replace_reg_in_block (&du, &uid_ruid, def_idx[def],
 390                                               gen_rtx_REG (GET_MODE (reg_use),
 391                                                            avail_reg),
 392                                               REGNO (reg_use));
 393
 394                         if (rtl_dump_file)
 395                           {
 396                             fprintf (rtl_dump_file,
 397                                      "Register %s in class %s Renaming as %s ",
 398                                      reg_names[r], reg_class_names[rc],
 399                                      reg_names[avail_reg]);
 400                             fprintf (rtl_dump_file,
 401                                      "would not satisfy constraints\n");
 402                           }
 403                       }
 404
 405                     else if (rtl_dump_file)
 406                       {
 407                         fprintf (rtl_dump_file,
 408                                  "Register %s in class %s Renamed as %s ",
 409                                  reg_names[r], reg_class_names[rc],
 410                                  reg_names[avail_reg]);
 411                         fprintf (rtl_dump_file, "at insn %d\n",
 412                                  INSN_UID (VARRAY_RTX (uid_ruid,
 413                                                        def_idx[def])));
 414                       }
 415                   }
 416
 417               try_next_def:
 418                 continue;
 419               }
 420
 421             sbitmap_zero (du.defs[r]);
 422
 423           no_available_regs:
 424             continue;
 425           }
 426
 427         free (def_idx);
 428         sbitmap_vector_free (du.defs);
 429         sbitmap_vector_free (du.uses);
 430         sbitmap_free (du.require_call_save_reg);
 431         sbitmap_free (defs_live_exit);
 432         CLEAR_HARD_REG_SET (regs_used);
 433         CLEAR_HARD_REG_SET (renamed_regs);
 434
 435         for (inum = 0; inum < (int) VARRAY_SIZE (uid_ruid); inum++)
 436           VARRAY_RTX (uid_ruid, inum) = (rtx) 0;
 437       }
 438
 439   sbitmap_vector_free (ebb.basic_block);
 440   sbitmap_vector_free (ebb.exit);
 441 }
 442
 443 /* Build def/use chain DU for extended basic block EBB having root B.
 444    Also determine which regs are used, REGS_USED, and which insns define
 445    a live at exit def, DEFS_LIVE_EXIT */
 446
 447 static void
 448 build_def_use (b, ebb, regs_used, du, defs_live_exit)
 449      int b;
 450      ext_basic_blocks *ebb;
 451      HARD_REG_SET *regs_used;
 452      def_uses *du;
 453      sbitmap *defs_live_exit;
 454 {
 455   rtx insn;
 456   int eb, inum;
 457   unsigned int r;
 458
 459   inum = 0;
 460   for (eb = 0; eb < n_basic_blocks; eb++)
 461     {
 462       basic_block bb = BASIC_BLOCK (eb);
 463
 464       if (!TEST_BIT (ebb->basic_block[b], eb))
 465         continue;
 466
 467       for (insn = bb->head;
 468            insn != NEXT_INSN (bb->end);
 469            inum++, insn = NEXT_INSN (insn))
 470         {
 471           struct resources insn_res;
 472           struct resources insn_sets;
 473
 474           if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
 475             continue;
 476
 477           CLEAR_RESOURCE (&insn_sets);
 478           mark_set_resources (insn, &insn_sets, 0, MARK_DEST);
 479
 480           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 481             {
 482               if (!TEST_HARD_REG_BIT (insn_sets.regs, r))
 483                 continue;
 484
 485               SET_HARD_REG_BIT (*regs_used, r);
 486               if (REGNO_REG_SET_P (bb->global_live_at_end, r))
 487                 SET_BIT (*defs_live_exit, inum);
 488
 489               if (!insn_sets.memory)
 490                 SET_BIT (du->defs[r], inum);
 491
 492               DU_REG_CLASS (du->def_class, r, du->high_bound, inum)
 493                 = get_reg_class (insn, regno_first_use_in (r, PATTERN (insn)),
 494                                  DESTINATION, NO_REGS);
 495             }
 496
 497           CLEAR_RESOURCE (&insn_res);
 498           mark_referenced_resources (insn, &insn_res, 0);
 499
 500           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 501             {
 502               if (!TEST_HARD_REG_BIT (insn_res.regs, r))
 503                 continue;
 504
 505               SET_HARD_REG_BIT (*regs_used, r);
 506               SET_BIT (du->uses[r], inum);
 507               DU_REG_CLASS (du->use_class, r, du->high_bound, inum)
 508                 = get_reg_class (insn, regno_use_in (r, PATTERN (insn)),
 509                                  SOURCE, NO_REGS);
 510             }
 511         }
 512     }
 513
 514   free_resource_info ();
 515 }
 516
 517 /* Return nonzero if regno AVAIL_REG can replace REG_DEF for insns in UID_RUID
 518    starting at insn DEF in def/use chain DU. */
 519
 520 static int
 521 replace_reg_in_block (du, uid_ruid, def, reg_def, avail_reg)
 522      def_uses *du;
 523      varray_type *uid_ruid;
 524      int def;
 525      rtx reg_def;
 526      unsigned int avail_reg;
 527 {
 528   int du_idx, status = 1;
 529   unsigned int r = REGNO (reg_def);
 530   rtx death_note;
 531   rtx new_reg = gen_rtx_REG (GET_MODE (reg_def), avail_reg);
 532
 533   rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, def)), reg_def, new_reg,
 534                   DESTINATION, VARRAY_RTX (*uid_ruid, def), &status);
 535
 536   if (!status)
 537     return status;
 538
 539   death_note = find_reg_note (VARRAY_RTX (*uid_ruid, def), REG_DEAD, reg_def);
 540   if (!death_note)
 541     death_note = find_reg_note (VARRAY_RTX (*uid_ruid, def), REG_UNUSED,
 542                                 reg_def);
 543
 544   if (death_note)
 545     rr_replace_reg (death_note, reg_def, new_reg, 0,
 546                     VARRAY_RTX (*uid_ruid, def), &status);
 547
 548   for (du_idx = def + 1; du_idx < du->high_bound; du_idx++)
 549     {
 550       rtx reg_use;
 551       rtx new_reg;
 552
 553       if (GET_RTX_CLASS (GET_CODE (VARRAY_RTX (*uid_ruid, du_idx))) != 'i')
 554         continue;
 555
 556       reg_use = regno_use_in (r, PATTERN (VARRAY_RTX (*uid_ruid, du_idx)));
 557       if (reg_use && TEST_BIT (du->uses[r], du_idx))
 558         {
 559           new_reg = gen_rtx_REG (GET_MODE (reg_use), avail_reg);
 560           rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, du_idx)), reg_use,
 561                           new_reg, SOURCE, VARRAY_RTX (*uid_ruid, du_idx),
 562                           &status);
 563           death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx),
 564                                       REG_DEAD, reg_use);
 565           if (!death_note)
 566             death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx),
 567                                         REG_UNUSED, reg_use);
 568           if (death_note)
 569             rr_replace_reg (death_note, reg_use, new_reg, 0,
 570                             VARRAY_RTX (*uid_ruid, def), &status);
 571
 572           SET_BIT (du->uses[avail_reg], du_idx);
 573           RESET_BIT (du->uses[r], du_idx);
 574           if (!status)
 575             return status;
 576         }
 577
 578       if (TEST_BIT (du->defs[r], du_idx))
 579         break;
 580     }
 581
 582   return status;
 583 }
 584
 585 /* Try to replace REG_USE in X with REG_SUB if INSN has a REPLACE_TYPE.
 586    STATUS is zero if the resulting pattern is not valid. */
 587
 588 static rtx
 589 rr_replace_reg (x, reg_use, reg_sub, replace_type, insn, status)
 590      rtx x;
 591      rtx reg_use;
 592      rtx reg_sub;
 593      int replace_type;
 594      rtx insn;
 595      int *status;
 596 {
 597   enum rtx_code code;
 598   int i;
 599   const char *fmt;
 600   int n;
 601
 602   if (x == 0)
 603     return x;
 604
 605   code = GET_CODE (x);
 606   switch (code)
 607     {
 608     case REG:
 609       if (REGNO (x) == REGNO (reg_use))
 610         {
 611           if (GET_MODE (x) == GET_MODE (reg_use))
 612             return reg_sub;
 613           else
 614             return gen_rtx_REG (GET_MODE (x), REGNO (reg_use));
 615         }
 616
 617       return x;
 618
 619     case SET:
 620       if (replace_type == DESTINATION)
 621         SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub,
 622                                        replace_type, insn, status);
 623       else if (replace_type == SOURCE)
 624         {
 625           unsigned int dest_subregno;
 626           int had_subreg = GET_CODE (SET_DEST (x)) == SUBREG;
 627
 628           if (had_subreg)
 629             dest_subregno = REGNO (XEXP (SET_DEST (x), 0));
 630
 631           SET_SRC (x) = rr_replace_reg (SET_SRC (x), reg_use, reg_sub,
 632                                         replace_type, insn, status);
 633
 634           /* If the replacement register is not part of the source
 635              then it may be part of a source mem operand. */
 636           if (GET_CODE (SET_DEST (x)) == MEM
 637               || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT
 638               || GET_CODE (SET_DEST (x)) == SIGN_EXTRACT
 639               || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
 640             SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub,
 641                                            replace_type, insn, status);
 642           /* Shared rtl sanity check. */
 643           if (had_subreg && dest_subregno != REGNO (XEXP (SET_DEST (x), 0)))
 644             {
 645               *status = 0;
 646               return x;
 647             }
 648         }
 649
 650       n = recog_memoized (insn);
 651       if (n >= 0)
 652         {
 653           int id;
 654
 655           extract_insn (insn);
 656
 657           /* Any MATCH_DUP's which are REGs must still match */
 658           for (id = insn_data[n].n_dups - 1; id >= 0; id--)
 659             {
 660               int opno = recog_data.dup_num[id];
 661
 662               if (GET_CODE (*recog_data.dup_loc[id]) == REG
 663                   && GET_CODE (*recog_data.operand_loc[opno]) == REG
 664                   && (REGNO (*recog_data.dup_loc[id])
 665                       != REGNO (*recog_data.operand_loc[opno])))
 666                 *status = 0;
 667             }
 668
 669           if (!constrain_operands (1))
 670             {
 671               *status = 0;
 672               validate_replace_rtx (reg_sub, reg_use, insn);
 673             }
 674         }
 675       else
 676         *status = 0;
 677
 678       return x;
 679
 680     default:
 681       break;
 682     }
 683
 684   fmt = GET_RTX_FORMAT (code);
 685   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 686     {
 687       if (fmt[i] == 'e')
 688         XEXP (x, i) = rr_replace_reg (XEXP (x, i), reg_use, reg_sub,
 689                                       replace_type, insn, status);
 690       if (fmt[i] == 'E')
 691         {
 692           register int xv;
 693
 694           for (xv = 0; xv < XVECLEN (x, i); xv++)
 695             {
 696               XVECEXP (x, i, xv) = rr_replace_reg (XVECEXP (x, i, xv), reg_use,
 697                                                 reg_sub, replace_type, insn,
 698                                                    status);
 699               n = recog_memoized (insn);
 700               if (n >= 0)
 701                 {
 702                   extract_insn (insn);
 703                   if (!constrain_operands (1))
 704                     {
 705                       *status = 0;
 706                       validate_replace_rtx (reg_sub, reg_use, insn);
 707                     }
 708                 }
 709               else
 710                 *status = 0;
 711             }
 712         }
 713     }
 714
 715   return x;
 716 }
 717
 718 /* Can REGNO in INSN be considered for renaming, given def INUM in d/u
 719    chain DU? */
 720
 721 static int
 722 consider_def (insn, regno, du, inum)
 723      rtx insn;
 724      int regno;
 725      def_uses *du ATTRIBUTE_UNUSED;
 726      int inum ATTRIBUTE_UNUSED;
 727 {
 728   /* Don't rename windowed registers across a call */
 729 #ifdef INCOMING_REGNO
 730   if (TEST_BIT (du->require_call_save_reg, inum)
 731       && INCOMING_REGNO (regno) != regno)
 732     return 0;
 733 #endif
 734
 735   /* Don't consider conditional moves.  Predicate architectures may
 736      use two complementary conditional moves and the regno shouldn't change */
 737   if (condmove_p (insn))
 738     return 0;
 739
 740   /* Don't rename call used registers across a call */
 741   if (!(GET_CODE (insn) == CALL_INSN
 742         && TEST_HARD_REG_BIT (call_used_reg_set, regno)))
 743     return 1;
 744   else
 745     return 0;
 746 }
 747
 748 /* Can the use of REGNO in INSN of block USE_BLOCK be considered for renaming
 749    for a def in def_block? */
 750
 751 static int
 752 consider_use (insn, regno, def_block, use_block)
 753      rtx insn;
 754      int regno;
 755      int def_block;
 756      int use_block;
 757 {
 758   rtx reg_use;
 759   edge e;
 760   basic_block ub = BASIC_BLOCK (use_block);
 761
 762   if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
 763     return 0;
 764
 765   /* If a use's basic block is different than the def's basic block,
 766      then insure another predecessor does not also define this register */
 767   if (def_block != use_block)
 768     for (e = ub->pred; e; e = e->pred_next)
 769       if (e->src->index != def_block
 770           && e->src->index != -1
 771           && REGNO_REG_SET_P (BASIC_BLOCK (e->src->index)->global_live_at_end,
 772                               regno))
 773         return 0;
 774
 775   /* Don't consider conditional moves.  Predicate architectures may
 776      use two complementary conditional moves and the regno shouldn't change */
 777
 778   if (condmove_p (insn))
 779     return 0;
 780
 781   reg_use = regno_first_use_in (regno, PATTERN (insn));
 782   if (reg_use)
 783     {
 784       /* Don't consider multi-reg values. */
 785       if (HARD_REGNO_NREGS (regno, GET_MODE (reg_use)) != 1
 786           && GET_MODE (reg_use) != CCmode)
 787         return 0;
 788
 789       /* Don't consider register if the only use is in a USE */
 790       return ! reg_mentioned_p (gen_rtx_USE (VOIDmode, reg_use),
 791                                 PATTERN (insn));
 792     }
 793   else
 794     return 0;
 795 }
 796
 797 /* Can REG_USE be replaced by regno AVAIL_REG if it is in AVAIL_REGS
 798    and it is in regclass RC, given insn INUM of def/use chain DU? */
 799
 800 static int
 801 consider_available (reg_use, avail_reg, avail_regs, rc, du, inum)
 802      rtx reg_use;
 803      int avail_reg;
 804      HARD_REG_SET *avail_regs;
 805      int rc;
 806      def_uses *du;
 807      int inum;
 808 {
 809   if (!TEST_HARD_REG_BIT (*avail_regs, avail_reg))
 810     return 0;
 811
 812   if (fixed_regs[avail_reg])
 813     return 0;
 814
 815 #ifdef HARD_REGNO_RENAME_OK
 816   if (!HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg))
 817     return 0;
 818 #endif
 819
 820   /* Don't consider windowed leaf registers which will be renamed by
 821      leaf_renumber_regs */
 822 #ifdef LEAF_REG_REMAP
 823   if (current_function_uses_only_leaf_regs)
 824     if (LEAF_REG_REMAP (avail_reg) < 0)
 825       return 0;
 826 #endif
 827
 828   /* A register is considered available if it is available at the beginning of
 829      the basic block.  We may want to refine this to when a register becomes
 830      available within the block.  We don't consider multi-reg values. */
 831   /* ??? Consider a representation that would allow multi-reg support? */
 832   if (!TEST_HARD_REG_BIT (reg_class_contents[(enum reg_class) rc], avail_reg)
 833       || !HARD_REGNO_MODE_OK (avail_reg, GET_MODE (reg_use))
 834       || (HARD_REGNO_NREGS (avail_reg, GET_MODE (reg_use)) != 1
 835           && GET_MODE (reg_use) != CCmode)
 836       || (call_fixed_regs[avail_reg]
 837 #ifdef HARD_REGNO_RENAME_OK
 838           && !HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg)
 839 #endif
 840       )
 841       || (TEST_BIT (du->require_call_save_reg, inum)
 842           && (call_used_regs[avail_reg] || call_used_regs[REGNO (reg_use)])))
 843     return 0;
 844
 845   /* If register is a callee-saved register it must be saved in the frame.
 846      call saved registers can not be added to regs_ever_live after reload,
 847      as it would invalidate most elimination offsets */
 848   return regs_ever_live[avail_reg] || call_used_regs[avail_reg];
 849 }
 850
 851 /* Return 1 if INSN is a conditional move */
 852
 853 static int
 854 condmove_p (insn)
 855      rtx insn;
 856 {
 857   return (GET_CODE (insn) == INSN
 858           && GET_CODE (PATTERN (insn)) == SET
 859           && GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE);
 860 }
 861
 862 /* Searches X for the first reference to REGNO, returning the rtx of the
 863    reference found if any.  Otherwise, returns NULL_RTX.  */
 864
 865 static rtx
 866 regno_first_use_in (regno, x)
 867      unsigned int regno;
 868      rtx x;
 869 {
 870   register const char *fmt;
 871   int i, j;
 872   rtx tem;
 873
 874   if (GET_CODE (x) == REG && REGNO (x) == regno)
 875     return x;
 876
 877   fmt = GET_RTX_FORMAT (GET_CODE (x));
 878   for (i = 0; i <= GET_RTX_LENGTH (GET_CODE (x)) - 1; i++)
 879     {
 880       if (fmt[i] == 'e')
 881         {
 882           if ((tem = regno_first_use_in (regno, XEXP (x, i))))
 883             return tem;
 884         }
 885
 886       else if (fmt[i] == 'E')
 887         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 888           if ((tem = regno_first_use_in (regno, XVECEXP (x, i, j))))
 889             return tem;
 890     }
 891
 892   return 0;
 893 }
 894
 895 /* Dump def/use chain DU to RTL_DUMP_FILE, given insns in UID_RUID and
 896    which regs are live at end, GLOBAL_LIVE_AT_END */
 897
 898 static void
 899 dump_def_use_chain (global_live_at_end, du, uid_ruid)
 900      HARD_REG_SET *global_live_at_end;
 901      def_uses *du;
 902      varray_type *uid_ruid;
 903 {
 904   unsigned int r;
 905   int inum;
 906
 907   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 908     {
 909       int set = 0;
 910
 911       for (inum = 0; inum <= du->high_bound; inum++)
 912         {
 913           rtx insn = VARRAY_RTX (*uid_ruid, inum);
 914 #if 0
 915           if (!insn
 916               || GET_RTX_CLASS (GET_CODE
 917                                 (insn)) != 'i')
 918             continue;
 919
 920           reg_use = regno_first_use_in (r, PATTERN (insn));
 921           if (!reg_use)
 922             continue;
 923 #endif
 924           if (!set && (TEST_BIT (du->defs[r], inum)
 925                        || TEST_BIT (du->uses[r], inum)))
 926             {
 927               fprintf (rtl_dump_file, "Register %s: ", reg_names[r]);
 928               if (fixed_regs[r])
 929                 fprintf (rtl_dump_file, "Fixed ");
 930               else if (call_fixed_regs[r])
 931                 fprintf (rtl_dump_file, "Call Fixed ");
 932               if (TEST_HARD_REG_BIT (*global_live_at_end, r))
 933                 fprintf (rtl_dump_file, "Live at Exit ");
 934               set = 1;
 935             }
 936
 937           if (TEST_BIT (du->defs[r], inum))
 938             fprintf (rtl_dump_file, "=%d ", INSN_UID (insn));
 939           if (TEST_BIT (du->uses[r], inum))
 940             fprintf (rtl_dump_file, "%d ", INSN_UID (insn));
 941         }
 942
 943       if (set)
 944         fprintf (rtl_dump_file, "\n");
 945     }
 946 }
 947
 948 /* Dump info for extended basic block EBB having root EB */
 949
 950 static void
 951 dump_ext_bb_info (eb, ebb)
 952      int eb;
 953      ext_basic_blocks *ebb;
 954 {
 955   int b;
 956   int have_ebb = 0;
 957
 958   for (b = 0; b < n_basic_blocks; b++)
 959     {
 960       if (TEST_BIT (ebb->basic_block[eb], b))
 961         {
 962           if (!have_ebb)
 963             {
 964 #ifndef RENAME_EXTENDED_BLOCKS
 965               fprintf (rtl_dump_file, "\nBasic block %d: ", b);
 966 #else
 967               fprintf (rtl_dump_file, "\nExtended basic block %d: ", b);
 968 #endif
 969               have_ebb = 1;
 970             }
 971           fprintf (rtl_dump_file, "%d ", b);
 972         }
 973
 974       if (TEST_BIT (ebb->exit[eb], b))
 975         fprintf (rtl_dump_file, "(exit) ");
 976     }
 977
 978   if (have_ebb)
 979     fprintf (rtl_dump_file, "\n");
 980 }
 981
 982 /* Initialize EBB with extended basic block info if RENAME_EXTENDED_BLOCKS is
 983    defined.  Otherwise just use basic blocks */
 984
 985 static void
 986 find_ext_basic_blocks (ebb)
 987      ext_basic_blocks *ebb;
 988 {
 989   sbitmap bb_processed;
 990   int b;
 991
 992   bb_processed = sbitmap_alloc (n_basic_blocks);
 993   sbitmap_zero (bb_processed);
 994
 995 #ifndef RENAME_EXTENDED_BLOCKS
 996   for (b = 0; b < n_basic_blocks; b++)
 997     {
 998       basic_block bb = BASIC_BLOCK (b);
 999       SET_BIT (ebb->basic_block[bb->index], bb->index);
1000     }
1001 #else
1002   for (b = 0; b < n_basic_blocks; b++)
1003     {
1004
1005       basic_block bb = BASIC_BLOCK (b);
1006       if (!TEST_BIT (bb_processed, b))
1007         {
1008           find_one_ext_basic_block (bb->index, bb, &bb_processed, ebb);
1009         }
1010     }
1011 #endif
1012   sbitmap_free (bb_processed);
1013 }
1014
1015 /* Find one extended basic block EBB having root ENTRY containing block
1016    BB */
1017
1018 static void
1019 find_one_ext_basic_block (entry, bb, bb_processed, ebb)
1020      int entry;
1021      basic_block bb;
1022      sbitmap *bb_processed;
1023      ext_basic_blocks *ebb;
1024 {
1025   edge e;
1026
1027   if (!TEST_BIT (*bb_processed, bb->index))
1028     {
1029       SET_BIT (ebb->basic_block[entry], bb->index);
1030       SET_BIT (*bb_processed, bb->index);
1031     }
1032
1033   for (e = bb->succ; e; e = e->succ_next)
1034     if (!TEST_BIT (*bb_processed, e->dest->index))
1035       {
1036         if (!e->dest->pred->pred_next
1037             && (!TEST_BIT (*bb_processed, e->dest->index)))
1038           find_one_ext_basic_block (entry, e->dest, bb_processed, ebb);
1039         else
1040           SET_BIT (ebb->exit[entry], bb->index);
1041       }
1042 }
1043
1044 /* Find the register class for register REG_USE having TYPE (DESTINATION or
1045    SOURCE) in INSN.  Use DEFAULT_CLASS if we cannot determine a class. */
1046
1047 static enum reg_class
1048 get_reg_class (insn, reg_use, type, default_class)
1049      rtx insn;
1050      rtx reg_use;
1051      int type;
1052      enum reg_class default_class;
1053 {
1054   int alt, id = 0;
1055
1056   extract_insn (insn);
1057   constrain_operands (1);
1058   alt = which_alternative;
1059
1060   preprocess_constraints ();
1061
1062   if (type == DESTINATION)
1063     {
1064       for (id = 0; id < recog_data.n_operands; id++)
1065         if (rtx_equal_p (recog_data.operand[id], reg_use))
1066           break;
1067     }
1068
1069   else if (type == SOURCE)
1070     for (id = recog_data.n_operands - 1; id >= 0; id--)
1071       if (rtx_equal_p (recog_data.operand[id], reg_use))
1072         break;
1073
1074   if (id == -1 || id == recog_data.n_operands)
1075     return default_class;
1076
1077   return recog_op_alt[id][alt].class;
1078 }