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