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