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