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                         avail_reg = reg_alloc_order[ar_idx];
 339                         if (consider_available (reg_use, avail_reg, &avail_regs,
 340                                                 rc, &du, def_idx[def]))
 341                           break;
 342                       }
 343
 344                     if (ar_idx == FIRST_PSEUDO_REGISTER)
 345                       {
 346                         if (rtl_dump_file)
 347                           {
 348                             fprintf (rtl_dump_file,
 349                                      "Register %s in class %s",
 350                                      reg_names[r], reg_class_names[rc]);
 351                             fprintf (rtl_dump_file,
 352                                      " in insn %d",
 353                                      INSN_UID (VARRAY_RTX (uid_ruid,
 354                                                            def_idx[def])));
 355
 356                             if (TEST_BIT (du.require_call_save_reg,
 357                                           def_idx[def]))
 358                               fprintf (rtl_dump_file, " crosses a call");
 359                             fprintf (rtl_dump_file, ". No available registers\n");
 360                           }
 361                         goto try_next_def;
 362                       }
 363
 364                     SET_HARD_REG_BIT (renamed_regs, avail_reg);
 365                     CLEAR_HARD_REG_BIT (avail_regs, avail_reg);
 366
 367                     /* Replace in destination.  Replace in source for
 368                        remainder of block until new register is defined
 369                        again */
 370                     replace_ok = replace_reg_in_block
 371                       (&du, &uid_ruid, def_idx[def], reg_use, avail_reg);
 372                     /* Replace failed, so restore previous register */
 373                     if (!replace_ok)
 374                       {
 375                         replace_reg_in_block (&du, &uid_ruid, def_idx[def],
 376                                             gen_rtx_REG (GET_MODE (reg_use),
 377                                                          avail_reg),
 378                                               REGNO (reg_use));
 379                         if (rtl_dump_file)
 380                           fprintf (rtl_dump_file,
 381                                    "Register %s in class %s Renaming as %s would not satisfy constraints\n",
 382                                    reg_names[r], reg_class_names[rc],
 383                                    reg_names[avail_reg]);
 384                       }
 385                     else if (rtl_dump_file)
 386                       fprintf (rtl_dump_file,
 387                        "Register %s in class %s Renamed as %s at insn %d\n",
 388                                reg_names[r], reg_class_names[rc],
 389                                reg_names[avail_reg],
 390                             INSN_UID (VARRAY_RTX (uid_ruid, def_idx[def])));
 391                   }
 392               try_next_def:
 393                 continue;
 394               }
 395             sbitmap_zero (du.defs[r]);
 396           no_available_regs:
 397             continue;
 398           }
 399         free (def_idx);
 400         sbitmap_vector_free (du.defs);
 401         sbitmap_vector_free (du.uses);
 402         sbitmap_free (du.require_call_save_reg);
 403         sbitmap_free (defs_live_exit);
 404         CLEAR_HARD_REG_SET (regs_used);
 405         CLEAR_HARD_REG_SET (renamed_regs);
 406
 407         for (inum = 0; inum < (int) VARRAY_SIZE (uid_ruid); inum++)
 408           VARRAY_RTX (uid_ruid, inum) = (rtx) 0;
 409       }
 410
 411   sbitmap_vector_free (ebb.basic_block);
 412   sbitmap_vector_free (ebb.exit);
 413 }
 414
 415 /* Build def/use chain DU for extended basic block EBB having root B.
 416    Also determine which regs are used, REGS_USED, and which insns define
 417    a live at exit def, DEFS_LIVE_EXIT */
 418
 419 static void
 420 build_def_use (b, ebb, regs_used, du, defs_live_exit)
 421      int b;
 422      ext_basic_blocks *ebb;
 423      HARD_REG_SET *regs_used;
 424      def_uses *du;
 425      sbitmap *defs_live_exit;
 426 {
 427   rtx insn;
 428   int eb, inum, r;
 429
 430   inum = 0;
 431   for (eb = 0; eb < n_basic_blocks; eb++)
 432     {
 433       basic_block bb = BASIC_BLOCK (eb);
 434
 435       if (!TEST_BIT (ebb->basic_block[b], eb))
 436         continue;
 437
 438       for (insn = bb->head;
 439            insn != NEXT_INSN (bb->end);
 440            inum++, insn = NEXT_INSN (insn))
 441         {
 442           struct resources insn_res;
 443           struct resources insn_sets;
 444
 445           if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
 446             continue;
 447
 448           CLEAR_RESOURCE (&insn_sets);
 449           mark_set_resources (insn, &insn_sets, 0, MARK_DEST);
 450
 451           for (r = 0;
 452                r < FIRST_PSEUDO_REGISTER;
 453                r++)
 454             {
 455               if (!TEST_HARD_REG_BIT (insn_sets.regs, r))
 456                 continue;
 457
 458               SET_HARD_REG_BIT (*regs_used, r);
 459               if (REGNO_REG_SET_P (bb->global_live_at_end, r))
 460                 SET_BIT (*defs_live_exit, inum);
 461               if (!insn_sets.memory)
 462                 SET_BIT (du->defs[r], inum);
 463               DU_REG_CLASS (du->def_class, r, du->high_bound, inum) = get_reg_class
 464                 (insn, regno_first_use_in (r, PATTERN (insn)),
 465                  DESTINATION, NO_REGS);
 466             }
 467
 468           CLEAR_RESOURCE (&insn_res);
 469           mark_referenced_resources (insn, &insn_res, 0);
 470
 471           for (r = 0;
 472                r < FIRST_PSEUDO_REGISTER;
 473                r++)
 474             {
 475               if (!TEST_HARD_REG_BIT (insn_res.regs, r))
 476                 continue;
 477
 478               SET_HARD_REG_BIT (*regs_used, r);
 479               SET_BIT (du->uses[r], inum);
 480               DU_REG_CLASS (du->use_class, r, du->high_bound, inum) = get_reg_class
 481                 (insn, regno_use_in (r, PATTERN (insn)),
 482                  SOURCE, NO_REGS);
 483             }
 484         }
 485     }
 486   free_resource_info ();
 487 }
 488
 489 /* Return nonzero if regno AVAIL_REG can replace REG_DEF for insns in UID_RUID
 490    starting at insn DEF in def/use chain DU. */
 491
 492 static int
 493 replace_reg_in_block (du, uid_ruid, def, reg_def, avail_reg)
 494      def_uses *du;
 495      varray_type *uid_ruid;
 496      int def;
 497      rtx reg_def;
 498      int avail_reg;
 499 {
 500   int du_idx, status = 1;
 501   int r = REGNO (reg_def);
 502   rtx death_note;
 503   rtx new_reg = gen_rtx_REG (GET_MODE (reg_def), avail_reg);
 504
 505
 506   rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, def)), reg_def,
 507                   new_reg, DESTINATION, VARRAY_RTX (*uid_ruid, def),
 508                   &status);
 509   if (!status)
 510     return status;
 511
 512   death_note = find_reg_note (VARRAY_RTX (*uid_ruid, def), REG_DEAD, reg_def);
 513   if (!death_note)
 514     death_note = find_reg_note (VARRAY_RTX (*uid_ruid, def), REG_UNUSED, reg_def);
 515   if (death_note)
 516     rr_replace_reg (death_note, reg_def, new_reg, 0,
 517                     VARRAY_RTX (*uid_ruid, def), &status);
 518
 519   for (du_idx = def + 1; du_idx < du->high_bound; du_idx++)
 520     {
 521       rtx reg_use;
 522       rtx new_reg;
 523       if (GET_RTX_CLASS (GET_CODE (VARRAY_RTX (*uid_ruid, du_idx))) != 'i')
 524         continue;
 525       reg_use = regno_use_in (r, PATTERN (VARRAY_RTX (*uid_ruid, du_idx)));
 526
 527       if (reg_use && TEST_BIT (du->uses[r], du_idx))
 528         {
 529           new_reg = gen_rtx_REG (GET_MODE (reg_use), avail_reg);
 530           rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, du_idx)), reg_use,
 531                           new_reg, SOURCE, VARRAY_RTX (*uid_ruid, du_idx),
 532                           &status);
 533           death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx),
 534                                       REG_DEAD, reg_use);
 535           if (!death_note)
 536             death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx),
 537                                         REG_UNUSED, reg_use);
 538           if (death_note)
 539             rr_replace_reg (death_note, reg_use, new_reg, 0,
 540                             VARRAY_RTX (*uid_ruid, def), &status);
 541           SET_BIT (du->uses[avail_reg], du_idx);
 542           RESET_BIT (du->uses[r], du_idx);
 543           if (!status)
 544             return status;
 545         }
 546       if (TEST_BIT (du->defs[r], du_idx))
 547         break;
 548     }
 549   return status;
 550 }
 551
 552 /* Try to replace REG_USE in X with REG_SUB if INSN has a REPLACE_TYPE.
 553    STATUS is zero if the resulting pattern is not valid. */
 554
 555 static rtx
 556 rr_replace_reg (x, reg_use, reg_sub, replace_type, insn, status)
 557      rtx x;
 558      rtx reg_use;
 559      rtx reg_sub;
 560      int replace_type;
 561      rtx insn;
 562      int *status;
 563 {
 564   enum rtx_code code;
 565   int i;
 566   const char *fmt;
 567   int n;
 568
 569   if (x == 0)
 570     return x;
 571
 572   code = GET_CODE (x);
 573   switch (code)
 574     {
 575     case REG:
 576       if (REGNO (x) == REGNO (reg_use))
 577         {
 578           if (GET_MODE (x) == GET_MODE (reg_use))
 579             return reg_sub;
 580           else
 581             return gen_rtx_REG (GET_MODE (x), REGNO (reg_use));
 582         }
 583       return x;
 584
 585     case SET:
 586       if (replace_type == DESTINATION)
 587         SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub,
 588                                        replace_type, insn, status);
 589       else if (replace_type == SOURCE)
 590         {
 591           int dest_subregno;
 592
 593           if (GET_CODE (SET_DEST (x)) == SUBREG)
 594             dest_subregno = REGNO (XEXP (SET_DEST (x), 0));
 595           else
 596             dest_subregno = 0;
 597
 598           SET_SRC (x) = rr_replace_reg (SET_SRC (x), reg_use, reg_sub,
 599                                         replace_type, insn, status);
 600           /* If the replacement register is not part of the source
 601              then it may be part of a source mem operand. */
 602           if (GET_CODE (SET_DEST (x)) == MEM
 603               || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT
 604               || GET_CODE (SET_DEST (x)) == SIGN_EXTRACT
 605               || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
 606             SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub,
 607                                            replace_type, insn, status);
 608           /* shared rtl sanity check */
 609           if (dest_subregno
 610               && dest_subregno != REGNO (XEXP (SET_DEST (x), 0)))
 611             {
 612               *status = 0;
 613               return x;
 614             }
 615         }
 616
 617       n = recog_memoized (insn);
 618       if (n >= 0)
 619         {
 620           int id;
 621           extract_insn (insn);
 622
 623           /* Any MATCH_DUP's which are REGs must still match */
 624           for (id = insn_data[n].n_dups - 1; id >= 0; id--)
 625             {
 626               int opno = recog_data.dup_num[id];
 627               if (GET_CODE (*recog_data.dup_loc[id]) == REG
 628                   && GET_CODE (*recog_data.operand_loc[opno]) == REG
 629                   && (REGNO (*recog_data.dup_loc[id]) !=
 630                       REGNO (*recog_data.operand_loc[opno])))
 631                 *status = 0;
 632             }
 633
 634           if (!constrain_operands (1))
 635             {
 636               *status = 0;
 637               validate_replace_rtx (reg_sub, reg_use, insn);
 638             }
 639         }
 640       else
 641         *status = 0;
 642
 643       return x;
 644
 645     default:
 646       break;
 647     }
 648
 649   fmt = GET_RTX_FORMAT (code);
 650   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 651     {
 652       if (fmt[i] == 'e')
 653         XEXP (x, i) = rr_replace_reg (XEXP (x, i), reg_use, reg_sub,
 654                                       replace_type, insn, status);
 655       if (fmt[i] == 'E')
 656         {
 657           register int xv;
 658           for (xv = 0; xv < XVECLEN (x, i); xv++)
 659             {
 660               XVECEXP (x, i, xv) = rr_replace_reg (XVECEXP (x, i, xv), reg_use,
 661                                                 reg_sub, replace_type, insn,
 662                                                    status);
 663               n = recog_memoized (insn);
 664               if (n >= 0)
 665                 {
 666                   extract_insn (insn);
 667                   if (!constrain_operands (1))
 668                     {
 669                       *status = 0;
 670                       validate_replace_rtx (reg_sub, reg_use, insn);
 671                     }
 672                 }
 673               else
 674                 *status = 0;
 675             }
 676         }
 677     }
 678   return x;
 679 }
 680
 681 /* Can REGNO in INSN be considered for renaming, given def INUM in d/u
 682    chain DU? */
 683
 684 static int
 685 consider_def (insn, regno, du, inum)
 686      rtx insn;
 687      int regno;
 688      def_uses *du;
 689      int inum;
 690 {
 691   /* Don't rename windowed registers across a call */
 692 #ifdef INCOMING_REGNO
 693   if (TEST_BIT (du->require_call_save_reg, inum)
 694       && INCOMING_REGNO (regno) != regno)
 695     return 0;
 696 #endif
 697
 698   /* Don't consider conditional moves.  Predicate architectures may
 699      use two complementary conditional moves and the regno shouldn't change */
 700   if (condmove_p (insn))
 701     return 0;
 702
 703   /* Don't rename call used registers across a call */
 704   if (!(GET_CODE (insn) == CALL_INSN
 705         && TEST_HARD_REG_BIT (call_used_reg_set, regno)))
 706     return 1;
 707   else
 708     return 0;
 709 }
 710
 711 /* Can the use of REGNO in INSN of block USE_BLOCK be considered for renaming
 712    for a def in def_block? */
 713
 714 static int
 715 consider_use (insn, regno, def_block, use_block)
 716      rtx insn;
 717      int regno;
 718      int def_block;
 719      int use_block;
 720 {
 721   rtx reg_use;
 722   edge e;
 723   basic_block ub = BASIC_BLOCK (use_block);
 724
 725   if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
 726     return 0;
 727
 728   /* If a use's basic block is different than the def's basic block,
 729      then insure another predecessor does not also define this register */
 730   if (def_block != use_block)
 731     for (e = ub->pred; e; e = e->pred_next)
 732       {
 733         if (e->src->index != def_block
 734             && e->src->index != -1
 735             && REGNO_REG_SET_P (BASIC_BLOCK (e->src->index)->global_live_at_end, regno))
 736           return 0;
 737       }
 738
 739   /* Don't consider conditional moves.  Predicate architectures may
 740      use two complementary conditional moves and the regno shouldn't change */
 741
 742   if (condmove_p (insn))
 743     return 0;
 744
 745   reg_use = regno_first_use_in (regno, PATTERN (insn));
 746   if (reg_use)
 747     {
 748       /* Don't consider multi-reg values. */
 749       if (HARD_REGNO_NREGS (regno, GET_MODE (reg_use)) != 1
 750           && GET_MODE (reg_use) != CCmode)
 751         return 0;
 752
 753       /* Don't consider register if the only use is in a USE */
 754       if (reg_mentioned_p (gen_rtx_USE (VOIDmode, reg_use),
 755                            PATTERN (insn)))
 756         return 0;
 757       else
 758         return 1;
 759     }
 760   else
 761     return 0;
 762 }
 763
 764 /* Can REG_USE be replaced by regno AVAIL_REG if it is in AVAIL_REGS
 765    and it is in regclass RC, given insn INUM of def/use chain DU? */
 766
 767 static int
 768 consider_available (reg_use, avail_reg, avail_regs, rc, du, inum)
 769      rtx reg_use;
 770      int avail_reg;
 771      HARD_REG_SET *avail_regs;
 772      int rc;
 773      def_uses *du;
 774      int inum;
 775 {
 776   if (!TEST_HARD_REG_BIT (*avail_regs, avail_reg))
 777     return 0;
 778
 779   if (fixed_regs[avail_reg])
 780     return 0;
 781
 782 #ifdef HARD_REGNO_RENAME_OK
 783   if (!HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg))
 784     return 0;
 785 #endif
 786
 787   /* Don't consider windowed leaf registers which will be renamed by
 788      leaf_renumber_regs */
 789 #ifdef LEAF_REG_REMAP
 790   if (current_function_uses_only_leaf_regs)
 791     if (LEAF_REG_REMAP (avail_reg) < 0)
 792       return 0;
 793 #endif
 794
 795   /* A register is considered available if it is available at the beginning of
 796      the basic block.  We may want to refine this to when a register becomes
 797      available within the block.  We don't consider multi-reg values. */
 798   /* ??? Consider a representation that would allow multi-reg support? */
 799   if (!TEST_HARD_REG_BIT (reg_class_contents[(enum reg_class) rc], avail_reg)
 800       || !HARD_REGNO_MODE_OK (avail_reg, GET_MODE (reg_use))
 801       || (HARD_REGNO_NREGS (avail_reg, GET_MODE (reg_use)) != 1
 802           && GET_MODE (reg_use) != CCmode)
 803       || (call_fixed_regs[avail_reg]
 804 #ifdef HARD_REGNO_RENAME_OK
 805           && !HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg)
 806 #endif
 807       )
 808       || (TEST_BIT (du->require_call_save_reg, inum)
 809           && (call_used_regs[avail_reg] || call_used_regs[REGNO (reg_use)]
 810           )))
 811     return 0;
 812
 813   /* If register is a callee-saved register it must be saved in the frame.
 814      call saved registers can not be added to regs_ever_live after reload,
 815      as it would invalidate most elimination offsets */
 816   if (regs_ever_live[avail_reg] || call_used_regs[avail_reg])
 817     return 1;
 818
 819   return 0;
 820 }
 821
 822 /* Return 1 if INSN is a conditional move */
 823
 824 static int
 825 condmove_p (insn)
 826      rtx insn;
 827 {
 828   if (GET_CODE (insn) == INSN
 829       && GET_CODE (PATTERN (insn)) == SET
 830       && GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
 831     return 1;
 832   return 0;
 833 }
 834
 835 /* Searches X for the first reference to REGNO, returning the rtx of the
 836    reference found if any.  Otherwise, returns NULL_RTX.  */
 837
 838 static rtx
 839 regno_first_use_in (regno, x)
 840      int regno;
 841      rtx x;
 842 {
 843   register const char *fmt;
 844   int i, j;
 845   rtx tem;
 846
 847   if (GET_CODE (x) == REG && REGNO (x) == regno)
 848     return x;
 849
 850   fmt = GET_RTX_FORMAT (GET_CODE (x));
 851   for (i = 0; i <= GET_RTX_LENGTH (GET_CODE (x)) - 1; i++)
 852     {
 853       if (fmt[i] == 'e')
 854         {
 855           if ((tem = regno_first_use_in (regno, XEXP (x, i))))
 856             return tem;
 857         }
 858       else if (fmt[i] == 'E')
 859         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 860           if ((tem = regno_first_use_in (regno, XVECEXP (x, i, j))))
 861             return tem;
 862     }
 863
 864   return NULL_RTX;
 865 }
 866
 867 /* Dump def/use chain DU to RTL_DUMP_FILE, given insns in UID_RUID and
 868    which regs are live at end, GLOBAL_LIVE_AT_END */
 869
 870 static void
 871 dump_def_use_chain (global_live_at_end, du, uid_ruid)
 872      HARD_REG_SET *global_live_at_end;
 873      def_uses *du;
 874      varray_type *uid_ruid;
 875 {
 876   int r, inum;
 877
 878   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 879     {
 880       int set = 0;
 881       for (inum = 0;
 882            inum <= du->high_bound;
 883            inum++)
 884         {
 885           rtx insn = VARRAY_RTX (*uid_ruid, inum);
 886 #if 0
 887           if (!insn
 888               || GET_RTX_CLASS (GET_CODE
 889                                 (insn)) != 'i')
 890             continue;
 891           reg_use = regno_first_use_in (r, PATTERN (insn));
 892           if (!reg_use)
 893             continue;
 894 #endif
 895           if (!set && (TEST_BIT (du->defs[r], inum)
 896                        || TEST_BIT (du->uses[r], inum)))
 897             {
 898               fprintf (rtl_dump_file, "Register %s: ", reg_names[r]);
 899               if (fixed_regs[r])
 900                 fprintf (rtl_dump_file, "Fixed ");
 901               else if (call_fixed_regs[r])
 902                 fprintf (rtl_dump_file, "Call Fixed ");
 903               if (TEST_HARD_REG_BIT (*global_live_at_end, r))
 904                 fprintf (rtl_dump_file, "Live at Exit ");
 905               set = 1;
 906             }
 907           if (TEST_BIT (du->defs[r], inum))
 908             fprintf (rtl_dump_file, "=%d ", INSN_UID (insn));
 909           if (TEST_BIT (du->uses[r], inum))
 910             fprintf (rtl_dump_file, "%d ", INSN_UID (insn));
 911         }
 912       if (set)
 913         fprintf (rtl_dump_file, "\n");
 914     }
 915 }
 916
 917 /* Dump info for extended basic block EBB having root EB */
 918
 919 static void
 920 dump_ext_bb_info (eb, ebb)
 921      int eb;
 922      ext_basic_blocks *ebb;
 923 {
 924   int b;
 925
 926   {
 927     int have_ebb = 0;
 928     for (b = 0; b < n_basic_blocks; b++)
 929       {
 930         if (TEST_BIT (ebb->basic_block[eb], b))
 931           {
 932             if (!have_ebb)
 933               {
 934 #ifndef RENAME_EXTENDED_BLOCKS
 935                 fprintf (rtl_dump_file, "\nBasic block %d: ", b);
 936 #else
 937                 fprintf (rtl_dump_file, "\nExtended basic block %d: ", b);
 938 #endif
 939                 have_ebb = 1;
 940               }
 941             fprintf (rtl_dump_file, "%d ", b);
 942           }
 943         if (TEST_BIT (ebb->exit[eb], b))
 944           fprintf (rtl_dump_file, "(exit) ");
 945       }
 946     if (have_ebb)
 947       fprintf (rtl_dump_file, "\n");
 948   }
 949 }
 950
 951 /* Initialize EBB with extended basic block info if RENAME_EXTENDED_BLOCKS is
 952    defined.  Otherwise just use basic blocks */
 953
 954 static void
 955 find_ext_basic_blocks (ebb)
 956      ext_basic_blocks *ebb;
 957 {
 958   sbitmap bb_processed;
 959   int b;
 960
 961   bb_processed = sbitmap_alloc (n_basic_blocks);
 962   sbitmap_zero (bb_processed);
 963
 964 #ifndef RENAME_EXTENDED_BLOCKS
 965   for (b = 0; b < n_basic_blocks; b++)
 966     {
 967       basic_block bb = BASIC_BLOCK (b);
 968       SET_BIT (ebb->basic_block[bb->index], bb->index);
 969     }
 970 #else
 971   for (b = 0; b < n_basic_blocks; b++)
 972     {
 973       basic_block bb = BASIC_BLOCK (b);
 974       if (!TEST_BIT (bb_processed, b))
 975         {
 976           find_one_ext_basic_block (bb->index, bb, &bb_processed, ebb);
 977         }
 978     }
 979 #endif
 980   sbitmap_free (bb_processed);
 981 }
 982
 983 /* Find one extended basic block EBB having root ENTRY containing block
 984    BB */
 985
 986 static void
 987 find_one_ext_basic_block (entry, bb, bb_processed, ebb)
 988      int entry;
 989      basic_block bb;
 990      sbitmap *bb_processed;
 991      ext_basic_blocks *ebb;
 992 {
 993   edge e;
 994
 995   if (!TEST_BIT (*bb_processed, bb->index))
 996     {
 997       SET_BIT (ebb->basic_block[entry], bb->index);
 998       SET_BIT (*bb_processed, bb->index);
 999     }
1000
1001   for (e = bb->succ; e; e = e->succ_next)
1002     if (!TEST_BIT (*bb_processed, e->dest->index))
1003       {
1004         if (!e->dest->pred->pred_next
1005             && (!TEST_BIT (*bb_processed, e->dest->index)))
1006           {
1007             find_one_ext_basic_block (entry, e->dest, bb_processed, ebb);
1008           }
1009         else
1010           {
1011             SET_BIT (ebb->exit[entry], bb->index);
1012           }
1013       }
1014 }
1015
1016 /* Find the register class for register REG_USE having TYPE (DESTINATION or
1017    SOURCE) in INSN.  Use DEFAULT_CLASS if we cannot determine a class. */
1018
1019 static enum reg_class
1020 get_reg_class (insn, reg_use, type, default_class)
1021      rtx insn;
1022      rtx reg_use;
1023      int type;
1024      enum reg_class default_class;
1025 {
1026   int alt, id = 0;
1027
1028   extract_insn (insn);
1029   constrain_operands (1);
1030   alt = which_alternative;
1031
1032   preprocess_constraints ();
1033
1034   if (type == DESTINATION)
1035     for (id = 0; id < recog_data.n_operands; id++)
1036       {
1037         if (rtx_equal_p (recog_data.operand[id], reg_use))
1038           break;
1039       }
1040   else if (type == SOURCE)
1041     for (id = recog_data.n_operands - 1; id >= 0; id--)
1042       {
1043         if (rtx_equal_p (recog_data.operand[id], reg_use))
1044           break;
1045       }
1046
1047   if (id == -1 || id == recog_data.n_operands)
1048     return default_class;
1049
1050   return recog_op_alt[id][alt].class;
1051 }