gcc/regcprop.c

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