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