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