gcc/regcprop.c

   1 /* Copy propagation on hard registers for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT
  13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  15    License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GCC; see the file COPYING3.  If not see
  19    <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "tm_p.h"
  27 #include "insn-config.h"
  28 #include "regs.h"
  29 #include "addresses.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "reload.h"
  33 #include "output.h"
  34 #include "function.h"
  35 #include "recog.h"
  36 #include "flags.h"
  37 #include "toplev.h"
  38 #include "obstack.h"
  39 #include "timevar.h"
  40 #include "tree-pass.h"
  41 #include "df.h"
  42
  43 /* The following code does forward propagation of hard register copies.
  44    The object is to eliminate as many dependencies as possible, so that
  45    we have the most scheduling freedom.  As a side effect, we also clean
  46    up some silly register allocation decisions made by reload.  This
  47    code may be obsoleted by a new register allocator.  */
  48
  49 /* For each register, we have a list of registers that contain the same
  50    value.  The OLDEST_REGNO field points to the head of the list, and
  51    the NEXT_REGNO field runs through the list.  The MODE field indicates
  52    what mode the data is known to be in; this field is VOIDmode when the
  53    register is not known to contain valid data.  */
  54
  55 struct value_data_entry
  56 {
  57   enum machine_mode mode;
  58   unsigned int oldest_regno;
  59   unsigned int next_regno;
  60 };
  61
  62 struct value_data
  63 {
  64   struct value_data_entry e[FIRST_PSEUDO_REGISTER];
  65   unsigned int max_value_regs;
  66 };
  67
  68 static void kill_value_one_regno (unsigned, struct value_data *);
  69 static void kill_value_regno (unsigned, unsigned, struct value_data *);
  70 static void kill_value (rtx, struct value_data *);
  71 static void set_value_regno (unsigned, enum machine_mode, struct value_data *);
  72 static void init_value_data (struct value_data *);
  73 static void kill_clobbered_value (rtx, const_rtx, void *);
  74 static void kill_set_value (rtx, const_rtx, void *);
  75 static int kill_autoinc_value (rtx *, void *);
  76 static void copy_value (rtx, rtx, struct value_data *);
  77 static bool mode_change_ok (enum machine_mode, enum machine_mode,
  78                             unsigned int);
  79 static rtx maybe_mode_change (enum machine_mode, enum machine_mode,
  80                               enum machine_mode, unsigned int, unsigned int);
  81 static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
  82 static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx,
  83                                       struct value_data *);
  84 static bool replace_oldest_value_addr (rtx *, enum reg_class,
  85                                        enum machine_mode, rtx,
  86                                        struct value_data *);
  87 static bool replace_oldest_value_mem (rtx, rtx, struct value_data *);
  88 static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
  89 extern void debug_value_data (struct value_data *);
  90 #ifdef ENABLE_CHECKING
  91 static void validate_value_data (struct value_data *);
  92 #endif
  93
  94 /* Kill register REGNO.  This involves removing it from any value
  95    lists, and resetting the value mode to VOIDmode.  This is only a
  96    helper function; it does not handle any hard registers overlapping
  97    with REGNO.  */
  98
  99 static void
 100 kill_value_one_regno (unsigned int regno, struct value_data *vd)
 101 {
 102   unsigned int i, next;
 103
 104   if (vd->e[regno].oldest_regno != regno)
 105     {
 106       for (i = vd->e[regno].oldest_regno;
 107            vd->e[i].next_regno != regno;
 108            i = vd->e[i].next_regno)
 109         continue;
 110       vd->e[i].next_regno = vd->e[regno].next_regno;
 111     }
 112   else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
 113     {
 114       for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
 115         vd->e[i].oldest_regno = next;
 116     }
 117
 118   vd->e[regno].mode = VOIDmode;
 119   vd->e[regno].oldest_regno = regno;
 120   vd->e[regno].next_regno = INVALID_REGNUM;
 121
 122 #ifdef ENABLE_CHECKING
 123   validate_value_data (vd);
 124 #endif
 125 }
 126
 127 /* Kill the value in register REGNO for NREGS, and any other registers
 128    whose values overlap.  */
 129
 130 static void
 131 kill_value_regno (unsigned int regno, unsigned int nregs,
 132                   struct value_data *vd)
 133 {
 134   unsigned int j;
 135
 136   /* Kill the value we're told to kill.  */
 137   for (j = 0; j < nregs; ++j)
 138     kill_value_one_regno (regno + j, vd);
 139
 140   /* Kill everything that overlapped what we're told to kill.  */
 141   if (regno < vd->max_value_regs)
 142     j = 0;
 143   else
 144     j = regno - vd->max_value_regs;
 145   for (; j < regno; ++j)
 146     {
 147       unsigned int i, n;
 148       if (vd->e[j].mode == VOIDmode)
 149         continue;
 150       n = hard_regno_nregs[j][vd->e[j].mode];
 151       if (j + n > regno)
 152         for (i = 0; i < n; ++i)
 153           kill_value_one_regno (j + i, vd);
 154     }
 155 }
 156
 157 /* Kill X.  This is a convenience function wrapping kill_value_regno
 158    so that we mind the mode the register is in.  */
 159
 160 static void
 161 kill_value (rtx x, struct value_data *vd)
 162 {
 163   rtx orig_rtx = x;
 164
 165   if (GET_CODE (x) == SUBREG)
 166     {
 167       x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
 168                            GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
 169       if (x == NULL_RTX)
 170         x = SUBREG_REG (orig_rtx);
 171     }
 172   if (REG_P (x))
 173     {
 174       unsigned int regno = REGNO (x);
 175       unsigned int n = hard_regno_nregs[regno][GET_MODE (x)];
 176
 177       kill_value_regno (regno, n, vd);
 178     }
 179 }
 180
 181 /* Remember that REGNO is valid in MODE.  */
 182
 183 static void
 184 set_value_regno (unsigned int regno, enum machine_mode mode,
 185                  struct value_data *vd)
 186 {
 187   unsigned int nregs;
 188
 189   vd->e[regno].mode = mode;
 190
 191   nregs = hard_regno_nregs[regno][mode];
 192   if (nregs > vd->max_value_regs)
 193     vd->max_value_regs = nregs;
 194 }
 195
 196 /* Initialize VD such that there are no known relationships between regs.  */
 197
 198 static void
 199 init_value_data (struct value_data *vd)
 200 {
 201   int i;
 202   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
 203     {
 204       vd->e[i].mode = VOIDmode;
 205       vd->e[i].oldest_regno = i;
 206       vd->e[i].next_regno = INVALID_REGNUM;
 207     }
 208   vd->max_value_regs = 0;
 209 }
 210
 211 /* Called through note_stores.  If X is clobbered, kill its value.  */
 212
 213 static void
 214 kill_clobbered_value (rtx x, const_rtx set, void *data)
 215 {
 216   struct value_data *const vd = (struct value_data *) data;
 217   if (GET_CODE (set) == CLOBBER)
 218     kill_value (x, vd);
 219 }
 220
 221 /* Called through note_stores.  If X is set, not clobbered, kill its
 222    current value and install it as the root of its own value list.  */
 223
 224 static void
 225 kill_set_value (rtx x, const_rtx set, void *data)
 226 {
 227   struct value_data *const vd = (struct value_data *) data;
 228   if (GET_CODE (set) != CLOBBER)
 229     {
 230       kill_value (x, vd);
 231       if (REG_P (x))
 232         set_value_regno (REGNO (x), GET_MODE (x), vd);
 233     }
 234 }
 235
 236 /* Called through for_each_rtx.  Kill any register used as the base of an
 237    auto-increment expression, and install that register as the root of its
 238    own value list.  */
 239
 240 static int
 241 kill_autoinc_value (rtx *px, void *data)
 242 {
 243   rtx x = *px;
 244   struct value_data *const vd = (struct value_data *) data;
 245
 246   if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
 247     {
 248       x = XEXP (x, 0);
 249       kill_value (x, vd);
 250       set_value_regno (REGNO (x), GET_MODE (x), vd);
 251       return -1;
 252     }
 253
 254   return 0;
 255 }
 256
 257 /* Assert that SRC has been copied to DEST.  Adjust the data structures
 258    to reflect that SRC contains an older copy of the shared value.  */
 259
 260 static void
 261 copy_value (rtx dest, rtx src, struct value_data *vd)
 262 {
 263   unsigned int dr = REGNO (dest);
 264   unsigned int sr = REGNO (src);
 265   unsigned int dn, sn;
 266   unsigned int i;
 267
 268   /* ??? At present, it's possible to see noop sets.  It'd be nice if
 269      this were cleaned up beforehand...  */
 270   if (sr == dr)
 271     return;
 272
 273   /* Do not propagate copies to the stack pointer, as that can leave
 274      memory accesses with no scheduling dependency on the stack update.  */
 275   if (dr == STACK_POINTER_REGNUM)
 276     return;
 277
 278   /* Likewise with the frame pointer, if we're using one.  */
 279   if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
 280     return;
 281
 282   /* Do not propagate copies to fixed or global registers, patterns
 283      can be relying to see particular fixed register or users can
 284      expect the chosen global register in asm.  */
 285   if (fixed_regs[dr] || global_regs[dr])
 286     return;
 287
 288   /* If SRC and DEST overlap, don't record anything.  */
 289   dn = hard_regno_nregs[dr][GET_MODE (dest)];
 290   sn = hard_regno_nregs[sr][GET_MODE (dest)];
 291   if ((dr > sr && dr < sr + sn)
 292       || (sr > dr && sr < dr + dn))
 293     return;
 294
 295   /* If SRC had no assigned mode (i.e. we didn't know it was live)
 296      assign it now and assume the value came from an input argument
 297      or somesuch.  */
 298   if (vd->e[sr].mode == VOIDmode)
 299     set_value_regno (sr, vd->e[dr].mode, vd);
 300
 301   /* If we are narrowing the input to a smaller number of hard regs,
 302      and it is in big endian, we are really extracting a high part.
 303      Since we generally associate a low part of a value with the value itself,
 304      we must not do the same for the high part.
 305      Note we can still get low parts for the same mode combination through
 306      a two-step copy involving differently sized hard regs.
 307      Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
 308      (set (reg:DI r0) (reg:DI fr0))
 309      (set (reg:SI fr2) (reg:SI r0))
 310      loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
 311      (set (reg:SI fr2) (reg:SI fr0))
 312      loads the high part of (reg:DI fr0) into fr2.
 313
 314      We can't properly represent the latter case in our tables, so don't
 315      record anything then.  */
 316   else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]
 317            && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
 318                ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
 319     return;
 320
 321   /* If SRC had been assigned a mode narrower than the copy, we can't
 322      link DEST into the chain, because not all of the pieces of the
 323      copy came from oldest_regno.  */
 324   else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode])
 325     return;
 326
 327   /* Link DR at the end of the value chain used by SR.  */
 328
 329   vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
 330
 331   for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
 332     continue;
 333   vd->e[i].next_regno = dr;
 334
 335 #ifdef ENABLE_CHECKING
 336   validate_value_data (vd);
 337 #endif
 338 }
 339
 340 /* Return true if a mode change from ORIG to NEW is allowed for REGNO.  */
 341
 342 static bool
 343 mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
 344                 unsigned int regno ATTRIBUTE_UNUSED)
 345 {
 346   if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
 347     return false;
 348
 349 #ifdef CANNOT_CHANGE_MODE_CLASS
 350   return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
 351 #endif
 352
 353   return true;
 354 }
 355
 356 /* Register REGNO was originally set in ORIG_MODE.  It - or a copy of it -
 357    was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
 358    in NEW_MODE.
 359    Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX.  */
 360
 361 static rtx
 362 maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode,
 363                    enum machine_mode new_mode, unsigned int regno,
 364                    unsigned int copy_regno ATTRIBUTE_UNUSED)
 365 {
 366   if (GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (orig_mode)
 367       && GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (new_mode))
 368     return NULL_RTX;
 369
 370   if (orig_mode == new_mode)
 371     return gen_rtx_raw_REG (new_mode, regno);
 372   else if (mode_change_ok (orig_mode, new_mode, regno))
 373     {
 374       int copy_nregs = hard_regno_nregs[copy_regno][copy_mode];
 375       int use_nregs = hard_regno_nregs[copy_regno][new_mode];
 376       int copy_offset
 377         = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
 378       int offset
 379         = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
 380       int byteoffset = offset % UNITS_PER_WORD;
 381       int wordoffset = offset - byteoffset;
 382
 383       offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
 384                 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
 385       return gen_rtx_raw_REG (new_mode,
 386                               regno + subreg_regno_offset (regno, orig_mode,
 387                                                            offset,
 388                                                            new_mode));
 389     }
 390   return NULL_RTX;
 391 }
 392
 393 /* Find the oldest copy of the value contained in REGNO that is in
 394    register class CL and has mode MODE.  If found, return an rtx
 395    of that oldest register, otherwise return NULL.  */
 396
 397 static rtx
 398 find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
 399 {
 400   unsigned int regno = REGNO (reg);
 401   enum machine_mode mode = GET_MODE (reg);
 402   unsigned int i;
 403
 404   /* If we are accessing REG in some mode other that what we set it in,
 405      make sure that the replacement is valid.  In particular, consider
 406         (set (reg:DI r11) (...))
 407         (set (reg:SI r9) (reg:SI r11))
 408         (set (reg:SI r10) (...))
 409         (set (...) (reg:DI r9))
 410      Replacing r9 with r11 is invalid.  */
 411   if (mode != vd->e[regno].mode)
 412     {
 413       if (hard_regno_nregs[regno][mode]
 414           > hard_regno_nregs[regno][vd->e[regno].mode])
 415         return NULL_RTX;
 416     }
 417
 418   for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
 419     {
 420       enum machine_mode oldmode = vd->e[i].mode;
 421       rtx new_rtx;
 422
 423       if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
 424         return NULL_RTX;
 425
 426       new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
 427       if (new_rtx)
 428         {
 429           ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (reg);
 430           REG_ATTRS (new_rtx) = REG_ATTRS (reg);
 431           REG_POINTER (new_rtx) = REG_POINTER (reg);
 432           return new_rtx;
 433         }
 434     }
 435
 436   return NULL_RTX;
 437 }
 438
 439 /* If possible, replace the register at *LOC with the oldest register
 440    in register class CL.  Return true if successfully replaced.  */
 441
 442 static bool
 443 replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn,
 444                           struct value_data *vd)
 445 {
 446   rtx new_rtx = find_oldest_value_reg (cl, *loc, vd);
 447   if (new_rtx)
 448     {
 449       if (dump_file)
 450         fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
 451                  INSN_UID (insn), REGNO (*loc), REGNO (new_rtx));
 452
 453       validate_change (insn, loc, new_rtx, 1);
 454       return true;
 455     }
 456   return false;
 457 }
 458
 459 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
 460    Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
 461    BASE_REG_CLASS depending on how the register is being considered.  */
 462
 463 static bool
 464 replace_oldest_value_addr (rtx *loc, enum reg_class cl,
 465                            enum machine_mode mode, rtx insn,
 466                            struct value_data *vd)
 467 {
 468   rtx x = *loc;
 469   RTX_CODE code = GET_CODE (x);
 470   const char *fmt;
 471   int i, j;
 472   bool changed = false;
 473
 474   switch (code)
 475     {
 476     case PLUS:
 477       if (DEBUG_INSN_P (insn))
 478         break;
 479
 480       {
 481         rtx orig_op0 = XEXP (x, 0);
 482         rtx orig_op1 = XEXP (x, 1);
 483         RTX_CODE code0 = GET_CODE (orig_op0);
 484         RTX_CODE code1 = GET_CODE (orig_op1);
 485         rtx op0 = orig_op0;
 486         rtx op1 = orig_op1;
 487         rtx *locI = NULL;
 488         rtx *locB = NULL;
 489         enum rtx_code index_code = SCRATCH;
 490
 491         if (GET_CODE (op0) == SUBREG)
 492           {
 493             op0 = SUBREG_REG (op0);
 494             code0 = GET_CODE (op0);
 495           }
 496
 497         if (GET_CODE (op1) == SUBREG)
 498           {
 499             op1 = SUBREG_REG (op1);
 500             code1 = GET_CODE (op1);
 501           }
 502
 503         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
 504             || code0 == ZERO_EXTEND || code1 == MEM)
 505           {
 506             locI = &XEXP (x, 0);
 507             locB = &XEXP (x, 1);
 508             index_code = GET_CODE (*locI);
 509           }
 510         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
 511                  || code1 == ZERO_EXTEND || code0 == MEM)
 512           {
 513             locI = &XEXP (x, 1);
 514             locB = &XEXP (x, 0);
 515             index_code = GET_CODE (*locI);
 516           }
 517         else if (code0 == CONST_INT || code0 == CONST
 518                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
 519           {
 520             locB = &XEXP (x, 1);
 521             index_code = GET_CODE (XEXP (x, 0));
 522           }
 523         else if (code1 == CONST_INT || code1 == CONST
 524                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
 525           {
 526             locB = &XEXP (x, 0);
 527             index_code = GET_CODE (XEXP (x, 1));
 528           }
 529         else if (code0 == REG && code1 == REG)
 530           {
 531             int index_op;
 532             unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
 533
 534             if (REGNO_OK_FOR_INDEX_P (regno1)
 535                 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
 536               index_op = 1;
 537             else if (REGNO_OK_FOR_INDEX_P (regno0)
 538                      && regno_ok_for_base_p (regno1, mode, PLUS, REG))
 539               index_op = 0;
 540             else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
 541                      || REGNO_OK_FOR_INDEX_P (regno1))
 542               index_op = 1;
 543             else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
 544               index_op = 0;
 545             else
 546               index_op = 1;
 547
 548             locI = &XEXP (x, index_op);
 549             locB = &XEXP (x, !index_op);
 550             index_code = GET_CODE (*locI);
 551           }
 552         else if (code0 == REG)
 553           {
 554             locI = &XEXP (x, 0);
 555             locB = &XEXP (x, 1);
 556             index_code = GET_CODE (*locI);
 557           }
 558         else if (code1 == REG)
 559           {
 560             locI = &XEXP (x, 1);
 561             locB = &XEXP (x, 0);
 562             index_code = GET_CODE (*locI);
 563           }
 564
 565         if (locI)
 566           changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
 567                                                 insn, vd);
 568         if (locB)
 569           changed |= replace_oldest_value_addr (locB,
 570                                                 base_reg_class (mode, PLUS,
 571                                                                 index_code),
 572                                                 mode, insn, vd);
 573         return changed;
 574       }
 575
 576     case POST_INC:
 577     case POST_DEC:
 578     case POST_MODIFY:
 579     case PRE_INC:
 580     case PRE_DEC:
 581     case PRE_MODIFY:
 582       return false;
 583
 584     case MEM:
 585       return replace_oldest_value_mem (x, insn, vd);
 586
 587     case REG:
 588       return replace_oldest_value_reg (loc, cl, insn, vd);
 589
 590     default:
 591       break;
 592     }
 593
 594   fmt = GET_RTX_FORMAT (code);
 595   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 596     {
 597       if (fmt[i] == 'e')
 598         changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode,
 599                                               insn, vd);
 600       else if (fmt[i] == 'E')
 601         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 602           changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
 603                                                 mode, insn, vd);
 604     }
 605
 606   return changed;
 607 }
 608
 609 /* Similar to replace_oldest_value_reg, but X contains a memory.  */
 610
 611 static bool
 612 replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
 613 {
 614   enum reg_class cl;
 615
 616   if (DEBUG_INSN_P (insn))
 617     cl = ALL_REGS;
 618   else
 619     cl = base_reg_class (GET_MODE (x), MEM, SCRATCH);
 620
 621   return replace_oldest_value_addr (&XEXP (x, 0), cl,
 622                                     GET_MODE (x), insn, vd);
 623 }
 624
 625 /* Perform the forward copy propagation on basic block BB.  */
 626
 627 static bool
 628 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
 629 {
 630   bool anything_changed = false;
 631   rtx insn;
 632
 633   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
 634     {
 635       int n_ops, i, alt, predicated;
 636       bool is_asm, any_replacements;
 637       rtx set;
 638       bool replaced[MAX_RECOG_OPERANDS];
 639       bool changed = false;
 640
 641       if (!NONDEBUG_INSN_P (insn))
 642         {
 643           if (DEBUG_INSN_P (insn))
 644             {
 645               rtx loc = INSN_VAR_LOCATION_LOC (insn);
 646               if (!VAR_LOC_UNKNOWN_P (loc)
 647                   && replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn),
 648                                                 ALL_REGS, GET_MODE (loc),
 649                                                 insn, vd))
 650                 {
 651                   changed = apply_change_group ();
 652                   gcc_assert (changed);
 653                   df_insn_rescan (insn);
 654                   anything_changed = true;
 655                 }
 656             }
 657
 658           if (insn == BB_END (bb))
 659             break;
 660           else
 661             continue;
 662         }
 663
 664       set = single_set (insn);
 665       extract_insn (insn);
 666       if (! constrain_operands (1))
 667         fatal_insn_not_found (insn);
 668       preprocess_constraints ();
 669       alt = which_alternative;
 670       n_ops = recog_data.n_operands;
 671       is_asm = asm_noperands (PATTERN (insn)) >= 0;
 672
 673       /* Simplify the code below by rewriting things to reflect
 674          matching constraints.  Also promote OP_OUT to OP_INOUT
 675          in predicated instructions.  */
 676
 677       predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
 678       for (i = 0; i < n_ops; ++i)
 679         {
 680           int matches = recog_op_alt[i][alt].matches;
 681           if (matches >= 0)
 682             recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
 683           if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
 684               || (predicated && recog_data.operand_type[i] == OP_OUT))
 685             recog_data.operand_type[i] = OP_INOUT;
 686         }
 687
 688       /* For each earlyclobber operand, zap the value data.  */
 689       for (i = 0; i < n_ops; i++)
 690         if (recog_op_alt[i][alt].earlyclobber)
 691           kill_value (recog_data.operand[i], vd);
 692
 693       /* Within asms, a clobber cannot overlap inputs or outputs.
 694          I wouldn't think this were true for regular insns, but
 695          scan_rtx treats them like that...  */
 696       note_stores (PATTERN (insn), kill_clobbered_value, vd);
 697
 698       /* Kill all auto-incremented values.  */
 699       /* ??? REG_INC is useless, since stack pushes aren't done that way.  */
 700       for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
 701
 702       /* Kill all early-clobbered operands.  */
 703       for (i = 0; i < n_ops; i++)
 704         if (recog_op_alt[i][alt].earlyclobber)
 705           kill_value (recog_data.operand[i], vd);
 706
 707       /* Special-case plain move instructions, since we may well
 708          be able to do the move from a different register class.  */
 709       if (set && REG_P (SET_SRC (set)))
 710         {
 711           rtx src = SET_SRC (set);
 712           unsigned int regno = REGNO (src);
 713           enum machine_mode mode = GET_MODE (src);
 714           unsigned int i;
 715           rtx new_rtx;
 716
 717           /* If we are accessing SRC in some mode other that what we
 718              set it in, make sure that the replacement is valid.  */
 719           if (mode != vd->e[regno].mode)
 720             {
 721               if (hard_regno_nregs[regno][mode]
 722                   > hard_regno_nregs[regno][vd->e[regno].mode])
 723                 goto no_move_special_case;
 724             }
 725
 726           /* If the destination is also a register, try to find a source
 727              register in the same class.  */
 728           if (REG_P (SET_DEST (set)))
 729             {
 730               new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
 731               if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0))
 732                 {
 733                   if (dump_file)
 734                     fprintf (dump_file,
 735                              "insn %u: replaced reg %u with %u\n",
 736                              INSN_UID (insn), regno, REGNO (new_rtx));
 737                   changed = true;
 738                   goto did_replacement;
 739                 }
 740             }
 741
 742           /* Otherwise, try all valid registers and see if its valid.  */
 743           for (i = vd->e[regno].oldest_regno; i != regno;
 744                i = vd->e[i].next_regno)
 745             {
 746               new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
 747                                        mode, i, regno);
 748               if (new_rtx != NULL_RTX)
 749                 {
 750                   if (validate_change (insn, &SET_SRC (set), new_rtx, 0))
 751                     {
 752                       ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src);
 753                       REG_ATTRS (new_rtx) = REG_ATTRS (src);
 754                       REG_POINTER (new_rtx) = REG_POINTER (src);
 755                       if (dump_file)
 756                         fprintf (dump_file,
 757                                  "insn %u: replaced reg %u with %u\n",
 758                                  INSN_UID (insn), regno, REGNO (new_rtx));
 759                       changed = true;
 760                       goto did_replacement;
 761                     }
 762                 }
 763             }
 764         }
 765       no_move_special_case:
 766
 767       any_replacements = false;
 768
 769       /* For each input operand, replace a hard register with the
 770          eldest live copy that's in an appropriate register class.  */
 771       for (i = 0; i < n_ops; i++)
 772         {
 773           replaced[i] = false;
 774
 775           /* Don't scan match_operand here, since we've no reg class
 776              information to pass down.  Any operands that we could
 777              substitute in will be represented elsewhere.  */
 778           if (recog_data.constraints[i][0] == '\0')
 779             continue;
 780
 781           /* Don't replace in asms intentionally referencing hard regs.  */
 782           if (is_asm && REG_P (recog_data.operand[i])
 783               && (REGNO (recog_data.operand[i])
 784                   == ORIGINAL_REGNO (recog_data.operand[i])))
 785             continue;
 786
 787           if (recog_data.operand_type[i] == OP_IN)
 788             {
 789               if (recog_op_alt[i][alt].is_address)
 790                 replaced[i]
 791                   = replace_oldest_value_addr (recog_data.operand_loc[i],
 792                                                recog_op_alt[i][alt].cl,
 793                                                VOIDmode, insn, vd);
 794               else if (REG_P (recog_data.operand[i]))
 795                 replaced[i]
 796                   = replace_oldest_value_reg (recog_data.operand_loc[i],
 797                                               recog_op_alt[i][alt].cl,
 798                                               insn, vd);
 799               else if (MEM_P (recog_data.operand[i]))
 800                 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
 801                                                         insn, vd);
 802             }
 803           else if (MEM_P (recog_data.operand[i]))
 804             replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
 805                                                     insn, vd);
 806
 807           /* If we performed any replacement, update match_dups.  */
 808           if (replaced[i])
 809             {
 810               int j;
 811               rtx new_rtx;
 812
 813               new_rtx = *recog_data.operand_loc[i];
 814               recog_data.operand[i] = new_rtx;
 815               for (j = 0; j < recog_data.n_dups; j++)
 816                 if (recog_data.dup_num[j] == i)
 817                   validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1);
 818
 819               any_replacements = true;
 820             }
 821         }
 822
 823       if (any_replacements)
 824         {
 825           if (! apply_change_group ())
 826             {
 827               for (i = 0; i < n_ops; i++)
 828                 if (replaced[i])
 829                   {
 830                     rtx old = *recog_data.operand_loc[i];
 831                     recog_data.operand[i] = old;
 832                   }
 833
 834               if (dump_file)
 835                 fprintf (dump_file,
 836                          "insn %u: reg replacements not verified\n",
 837                          INSN_UID (insn));
 838             }
 839           else
 840             changed = true;
 841         }
 842
 843     did_replacement:
 844       if (changed)
 845         {
 846           df_insn_rescan (insn);
 847           anything_changed = true;
 848         }
 849
 850       /* Clobber call-clobbered registers.  */
 851       if (CALL_P (insn))
 852         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 853           if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
 854             kill_value_regno (i, 1, vd);
 855
 856       /* Notice stores.  */
 857       note_stores (PATTERN (insn), kill_set_value, vd);
 858
 859       /* Notice copies.  */
 860       if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
 861         copy_value (SET_DEST (set), SET_SRC (set), vd);
 862
 863       if (insn == BB_END (bb))
 864         break;
 865     }
 866
 867   return anything_changed;
 868 }
 869
 870 /* Main entry point for the forward copy propagation optimization.  */
 871
 872 static unsigned int
 873 copyprop_hardreg_forward (void)
 874 {
 875   struct value_data *all_vd;
 876   basic_block bb;
 877   sbitmap visited;
 878
 879   all_vd = XNEWVEC (struct value_data, last_basic_block);
 880
 881   visited = sbitmap_alloc (last_basic_block);
 882   sbitmap_zero (visited);
 883
 884   FOR_EACH_BB (bb)
 885     {
 886       SET_BIT (visited, bb->index);
 887
 888       /* If a block has a single predecessor, that we've already
 889          processed, begin with the value data that was live at
 890          the end of the predecessor block.  */
 891       /* ??? Ought to use more intelligent queuing of blocks.  */
 892       if (single_pred_p (bb)
 893           && TEST_BIT (visited, single_pred (bb)->index)
 894           && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
 895         all_vd[bb->index] = all_vd[single_pred (bb)->index];
 896       else
 897         init_value_data (all_vd + bb->index);
 898
 899       copyprop_hardreg_forward_1 (bb, all_vd + bb->index);
 900     }
 901
 902   sbitmap_free (visited);
 903   free (all_vd);
 904   return 0;
 905 }
 906
 907 /* Dump the value chain data to stderr.  */
 908
 909 void
 910 debug_value_data (struct value_data *vd)
 911 {
 912   HARD_REG_SET set;
 913   unsigned int i, j;
 914
 915   CLEAR_HARD_REG_SET (set);
 916
 917   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
 918     if (vd->e[i].oldest_regno == i)
 919       {
 920         if (vd->e[i].mode == VOIDmode)
 921           {
 922             if (vd->e[i].next_regno != INVALID_REGNUM)
 923               fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
 924                        i, vd->e[i].next_regno);
 925             continue;
 926           }
 927
 928         SET_HARD_REG_BIT (set, i);
 929         fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
 930
 931         for (j = vd->e[i].next_regno;
 932              j != INVALID_REGNUM;
 933              j = vd->e[j].next_regno)
 934           {
 935             if (TEST_HARD_REG_BIT (set, j))
 936               {
 937                 fprintf (stderr, "[%u] Loop in regno chain\n", j);
 938                 return;
 939               }
 940
 941             if (vd->e[j].oldest_regno != i)
 942               {
 943                 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
 944                          j, vd->e[j].oldest_regno);
 945                 return;
 946               }
 947             SET_HARD_REG_BIT (set, j);
 948             fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
 949           }
 950         fputc ('\n', stderr);
 951       }
 952
 953   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
 954     if (! TEST_HARD_REG_BIT (set, i)
 955         && (vd->e[i].mode != VOIDmode
 956             || vd->e[i].oldest_regno != i
 957             || vd->e[i].next_regno != INVALID_REGNUM))
 958       fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
 959                i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
 960                vd->e[i].next_regno);
 961 }
 962
 963 #ifdef ENABLE_CHECKING
 964 static void
 965 validate_value_data (struct value_data *vd)
 966 {
 967   HARD_REG_SET set;
 968   unsigned int i, j;
 969
 970   CLEAR_HARD_REG_SET (set);
 971
 972   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
 973     if (vd->e[i].oldest_regno == i)
 974       {
 975         if (vd->e[i].mode == VOIDmode)
 976           {
 977             if (vd->e[i].next_regno != INVALID_REGNUM)
 978               internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
 979                               i, vd->e[i].next_regno);
 980             continue;
 981           }
 982
 983         SET_HARD_REG_BIT (set, i);
 984
 985         for (j = vd->e[i].next_regno;
 986              j != INVALID_REGNUM;
 987              j = vd->e[j].next_regno)
 988           {
 989             if (TEST_HARD_REG_BIT (set, j))
 990               internal_error ("validate_value_data: Loop in regno chain (%u)",
 991                               j);
 992             if (vd->e[j].oldest_regno != i)
 993               internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
 994                               j, vd->e[j].oldest_regno);
 995
 996             SET_HARD_REG_BIT (set, j);
 997           }
 998       }
 999
1000   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1001     if (! TEST_HARD_REG_BIT (set, i)
1002         && (vd->e[i].mode != VOIDmode
1003             || vd->e[i].oldest_regno != i
1004             || vd->e[i].next_regno != INVALID_REGNUM))
1005       internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1006                       i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1007                       vd->e[i].next_regno);
1008 }
1009 #endif
1010 \f
1011 static bool
1012 gate_handle_cprop (void)
1013 {
1014   return (optimize > 0 && (flag_cprop_registers));
1015 }
1016
1017
1018 struct rtl_opt_pass pass_cprop_hardreg =
1019 {
1020  {
1021   RTL_PASS,
1022   "cprop_hardreg",                      /* name */
1023   gate_handle_cprop,                    /* gate */
1024   copyprop_hardreg_forward,             /* execute */
1025   NULL,                                 /* sub */
1026   NULL,                                 /* next */
1027   0,                                    /* static_pass_number */
1028   TV_CPROP_REGISTERS,                   /* tv_id */
1029   0,                                    /* properties_required */
1030   0,                                    /* properties_provided */
1031   0,                                    /* properties_destroyed */
1032   0,                                    /* todo_flags_start */
1033   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
1034  }
1035 };