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