gcc/regcprop.c

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