gcc/ext-dce.cc

   1 /* RTL dead zero/sign extension (code) elimination.
   2    Copyright (C) 2000-2022 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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 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 "backend.h"
  24 #include "rtl.h"
  25 #include "tree.h"
  26 #include "memmodel.h"
  27 #include "insn-config.h"
  28 #include "emit-rtl.h"
  29 #include "recog.h"
  30 #include "cfganal.h"
  31 #include "tree-pass.h"
  32 #include "cfgrtl.h"
  33 #include "rtl-iter.h"
  34 #include "df.h"
  35 #include "print-rtl.h"
  36 #include "dbgcnt.h"
  37
  38 /* These should probably move into a C++ class.  */
  39 static vec<bitmap_head> livein;
  40 static bitmap all_blocks;
  41 static bitmap livenow;
  42 static bitmap changed_pseudos;
  43 static bool modify;
  44
  45 /* We consider four bit groups for liveness:
  46    bit 0..7   (least significant byte)
  47    bit 8..15  (second least significant byte)
  48    bit 16..31
  49    bit 32..BITS_PER_WORD-1  */
  50
  51 /* For the given REG, return the number of bit groups implied by the
  52    size of the REG's mode, up to a maximum of 4 (number of bit groups
  53    tracked by this pass).
  54
  55    For partial integer and variable sized modes also return 4.  This
  56    could possibly be refined for something like PSI mode, but it
  57    does not seem worth the effort.  */
  58
  59 static int
  60 group_limit (const_rtx reg)
  61 {
  62   machine_mode mode = GET_MODE (reg);
  63
  64   if (!GET_MODE_BITSIZE (mode).is_constant ())
  65     return 4;
  66
  67   int size = GET_MODE_SIZE (mode).to_constant ();
  68
  69   size = exact_log2 (size);
  70
  71   if (size < 0)
  72     return 4;
  73
  74   size++;
  75   return (size > 4 ? 4 : size);
  76 }
  77
  78 /* Make all bit groups live for REGNO in bitmap BMAP.  For hard regs,
  79    we assume all groups are live.  For a pseudo we consider the size
  80    of the pseudo to avoid creating unnecessarily live chunks of data.  */
  81
  82 static void
  83 make_reg_live (bitmap bmap, int regno)
  84 {
  85   int limit;
  86
  87   /* For pseudos we can use the mode to limit how many bit groups
  88      are marked as live since a pseudo only has one mode.  Hard
  89      registers have to be handled more conservatively.  */
  90   if (regno > FIRST_PSEUDO_REGISTER)
  91     {
  92       rtx reg = regno_reg_rtx[regno];
  93       limit = group_limit (reg);
  94     }
  95   else
  96     limit = 4;
  97
  98   for (int i = 0; i < limit; i++)
  99     bitmap_set_bit (bmap, regno * 4 + i);
 100 }
 101
 102 /* Note this pass could be used to narrow memory loads too.  It's
 103    not clear if that's profitable or not in general.  */
 104
 105 #define UNSPEC_P(X) (GET_CODE (X) == UNSPEC || GET_CODE (X) == UNSPEC_VOLATILE)
 106
 107 /* If we know the destination of CODE only uses some low bits
 108    (say just the QI bits of an SI operation), then return true
 109    if we can propagate the need for just the subset of bits
 110    from the destination to the sources.
 111
 112    FIXME: This is safe for operands 1 and 2 of an IF_THEN_ELSE, but not
 113    operand 0.  Thus is likely would need some special casing to handle.  */
 114
 115 static bool
 116 safe_for_live_propagation (rtx_code code)
 117 {
 118   /* First handle rtx classes which as a whole are known to
 119      be either safe or unsafe.  */
 120   switch (GET_RTX_CLASS (code))
 121     {
 122       case RTX_OBJ:
 123       case RTX_CONST_OBJ:
 124         return true;
 125
 126       case RTX_COMPARE:
 127       case RTX_COMM_COMPARE:
 128       case RTX_TERNARY:
 129         return false;
 130
 131       default:
 132         break;
 133     }
 134
 135   /* What's left are specific codes.  We only need to identify those
 136      which are safe.   */
 137   switch (code)
 138     {
 139     /* These are trivially safe.  */
 140     case SUBREG:
 141     case NOT:
 142     case ZERO_EXTEND:
 143     case SIGN_EXTEND:
 144     case TRUNCATE:
 145     case PLUS:
 146     case MINUS:
 147     case MULT:
 148     case SMUL_HIGHPART:
 149     case UMUL_HIGHPART:
 150     case AND:
 151     case IOR:
 152     case XOR:
 153       return true;
 154
 155     /* We can propagate for the shifted operand, but not the shift
 156        count.  The count is handled specially.  */
 157     case ASHIFT:
 158     case LSHIFTRT:
 159     case ASHIFTRT:
 160     case SS_ASHIFT:
 161     case US_ASHIFT:
 162       return true;
 163
 164     /* There may be other safe codes.  If so they can be added
 165        individually when discovered.  */
 166     default:
 167       return false;
 168     }
 169 }
 170
 171 /* Clear bits in LIVENOW and set bits in LIVE_TMP for objects
 172    set/clobbered by OBJ contained in INSN.
 173
 174    Conceptually it is always safe to ignore a particular destination
 175    here as that will result in more chunks of data being considered
 176    live.  That's what happens when we "continue" the main loop when
 177    we see something we don't know how to handle such as a vector
 178    mode destination.
 179
 180    The more accurate we are in identifying what objects (and chunks
 181    within an object) are set by INSN, the more aggressive the
 182    optimization phase during use handling will be.  */
 183
 184 static bool
 185 ext_dce_process_sets (rtx_insn *insn, rtx obj, bitmap live_tmp)
 186 {
 187   bool skipped_dest = false;
 188
 189   subrtx_iterator::array_type array;
 190   FOR_EACH_SUBRTX (iter, array, obj, NONCONST)
 191     {
 192       const_rtx x = *iter;
 193
 194       /* An EXPR_LIST (from call fusage) ends in NULL_RTX.  */
 195       if (x == NULL_RTX)
 196         continue;
 197
 198       if (UNSPEC_P (x))
 199         continue;
 200
 201       if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
 202         {
 203           unsigned bit = 0;
 204           x = SET_DEST (x);
 205
 206           /* We don't support vector destinations or destinations
 207              wider than DImode.  */
 208           scalar_int_mode outer_mode;
 209           if (!is_a <scalar_int_mode> (GET_MODE (x), &outer_mode)
 210               || GET_MODE_BITSIZE (outer_mode) > HOST_BITS_PER_WIDE_INT)
 211             {
 212               /* Skip the subrtxs of this destination.  There is
 213                  little value in iterating into the subobjects, so
 214                  just skip them for a bit of efficiency.  */
 215               skipped_dest = true;
 216               iter.skip_subrtxes ();
 217               continue;
 218             }
 219
 220           /* We could have (strict_low_part (subreg ...)).  We can not just
 221              strip the STRICT_LOW_PART as that would result in clearing
 222              some bits in LIVENOW that are still live.  So process the
 223              STRICT_LOW_PART specially.  */
 224           if (GET_CODE (x) == STRICT_LOW_PART)
 225             {
 226               x = XEXP (x, 0);
 227
 228               /* The only valid operand of a STRICT_LOW_PART is a non
 229                  paradoxical SUBREG.  */
 230               gcc_assert (SUBREG_P (x)
 231                           && !paradoxical_subreg_p (x)
 232                           && SUBREG_BYTE (x).is_constant ());
 233
 234               /* I think we should always see a REG here.  But let's
 235                  be sure.  */
 236               gcc_assert (REG_P (SUBREG_REG (x)));
 237
 238               /* The inner mode might be larger, just punt for
 239                  that case.  Remember, we can not just continue to process
 240                  the inner RTXs due to the STRICT_LOW_PART.  */
 241               if (!is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (x)), &outer_mode)
 242                   || GET_MODE_BITSIZE (outer_mode) > HOST_BITS_PER_WIDE_INT)
 243                 {
 244                   /* Skip the subrtxs of the STRICT_LOW_PART.  We can't
 245                      process them because it'll set objects as no longer
 246                      live when they are in fact still live.  */
 247                   skipped_dest = true;
 248                   iter.skip_subrtxes ();
 249                   continue;
 250                 }
 251
 252               /* LIVE_TMP contains the set groups that are live-out and set in
 253                  this insn.  It is used to narrow the groups live-in for the
 254                  inputs of this insn.
 255
 256                  The simple thing to do is mark all the groups as live, but
 257                  that will significantly inhibit optimization.
 258
 259                  We also need to be careful in the case where we have an in-out
 260                  operand.  If we're not careful we'd clear LIVE_TMP
 261                  incorrectly.  */
 262               HOST_WIDE_INT rn = REGNO (SUBREG_REG (x));
 263               int limit = group_limit (SUBREG_REG (x));
 264               for (HOST_WIDE_INT i = 4 * rn; i < 4 * rn + limit; i++)
 265                 if (bitmap_bit_p (livenow, i))
 266                   bitmap_set_bit (live_tmp, i);
 267
 268               if (bitmap_empty_p (live_tmp))
 269                 make_reg_live (live_tmp, rn);
 270
 271               /* The mode of the SUBREG tells us how many bits we can
 272                  clear.  */
 273               machine_mode mode = GET_MODE (x);
 274               HOST_WIDE_INT size
 275                 = exact_log2 (GET_MODE_SIZE (mode).to_constant ()) + 1;
 276               bitmap_clear_range (livenow, 4 * rn, size);
 277
 278               /* We have fully processed this destination.  */
 279               iter.skip_subrtxes ();
 280               continue;
 281             }
 282
 283           /* Phase one of destination handling.  First remove any wrapper
 284              such as SUBREG or ZERO_EXTRACT.  */
 285           unsigned HOST_WIDE_INT mask
 286             = GET_MODE_MASK (GET_MODE_INNER (GET_MODE (x)));
 287           if (SUBREG_P (x))
 288             {
 289               /* If we have a SUBREG destination that is too wide, just
 290                  skip the destination rather than continuing this iterator.
 291                  While continuing would be better, we'd need to strip the
 292                  subreg and restart within the SET processing rather than
 293                  the top of the loop which just complicates the flow even
 294                  more.  */
 295               if (!is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (x)), &outer_mode)
 296                   || GET_MODE_BITSIZE (outer_mode) > HOST_BITS_PER_WIDE_INT)
 297                 {
 298                   skipped_dest = true;
 299                   iter.skip_subrtxes ();
 300                   continue;
 301                 }
 302
 303               /* We can safely strip a paradoxical subreg.  The inner mode will
 304                  be narrower than the outer mode.  We'll clear fewer bits in
 305                  LIVENOW than we'd like, but that's always safe.  */
 306               if (paradoxical_subreg_p (x))
 307                 x = XEXP (x, 0);
 308               else if (SUBREG_BYTE (x).is_constant ())
 309                 {
 310                   bit = subreg_lsb (x).to_constant ();
 311                   mask = GET_MODE_MASK (GET_MODE (SUBREG_REG (x))) << bit;
 312                   gcc_assert (mask);
 313                   x = SUBREG_REG (x);
 314                 }
 315               else
 316                 gcc_unreachable ();
 317             }
 318
 319           if (GET_CODE (x) == ZERO_EXTRACT)
 320             {
 321               /* Unlike a SUBREG destination, a set of a ZERO_EXTRACT only
 322                  modifies the bits referenced in the ZERO_EXTRACT, the rest
 323                  remain the same.  Thus we can not continue here, we must
 324                  either figure out what part of the destination is modified
 325                  or skip the sub-rtxs.  */
 326               skipped_dest = true;
 327               iter.skip_subrtxes ();
 328               continue;
 329             }
 330
 331           /* BIT >= 64 indicates something went horribly wrong.  */
 332           gcc_assert (bit <= HOST_BITS_PER_WIDE_INT - 1);
 333
 334           /* Now handle the actual object that was changed.  */
 335           if (REG_P (x))
 336             {
 337               /* LIVE_TMP contains the set groups that are live-out and set in
 338                  this insn.  It is used to narrow the groups live-in for the
 339                  inputs of this insn.
 340
 341                  The simple thing to do is mark all the groups as live, but
 342                  that will significantly inhibit optimization.
 343
 344                  We also need to be careful in the case where we have an in-out
 345                  operand.  If we're not careful we'd clear LIVE_TMP
 346                  incorrectly.  */
 347               HOST_WIDE_INT rn = REGNO (x);
 348               int limit = group_limit (x);
 349               for (HOST_WIDE_INT i = 4 * rn; i < 4 * rn + limit; i++)
 350                 if (bitmap_bit_p (livenow, i))
 351                   bitmap_set_bit (live_tmp, i);
 352
 353               if (bitmap_empty_p (live_tmp))
 354                 make_reg_live (live_tmp, rn);
 355
 356               /* Now clear the bits known written by this instruction.
 357                  Note that BIT need not be a power of two, consider a
 358                  ZERO_EXTRACT destination.  */
 359               int start = (bit < 8 ? 0 : bit < 16 ? 1 : bit < 32 ? 2 : 3);
 360               int end = ((mask & ~0xffffffffULL) ? 4
 361                          : (mask & 0xffff0000ULL) ? 3
 362                          : (mask & 0xff00) ? 2 : 1);
 363               bitmap_clear_range (livenow, 4 * rn + start, end - start);
 364             }
 365           /* Some ports generate (clobber (const_int)).  */
 366           else if (CONST_INT_P (x))
 367             continue;
 368           else
 369             gcc_assert (CALL_P (insn)
 370                         || MEM_P (x)
 371                         || x == pc_rtx
 372                         || GET_CODE (x) == SCRATCH);
 373
 374           iter.skip_subrtxes ();
 375         }
 376       else if (GET_CODE (x) == COND_EXEC)
 377         {
 378           /* This isn't ideal, but may not be so bad in practice.  */
 379           skipped_dest = true;
 380           iter.skip_subrtxes ();
 381         }
 382     }
 383   return skipped_dest;
 384 }
 385
 386 /* INSN has a sign/zero extended source inside SET that we will
 387    try to turn into a SUBREG.  */
 388 static void
 389 ext_dce_try_optimize_insn (rtx_insn *insn, rtx set)
 390 {
 391   rtx src = SET_SRC (set);
 392   rtx inner = XEXP (src, 0);
 393
 394   /* Avoid (subreg (mem)) and other constructs which may be valid RTL, but
 395      not useful for this optimization.  */
 396   if (!(REG_P (inner) || (SUBREG_P (inner) && REG_P (SUBREG_REG (inner)))))
 397     return;
 398
 399   rtx new_pattern;
 400   if (dump_file)
 401     {
 402       fprintf (dump_file, "Processing insn:\n");
 403       dump_insn_slim (dump_file, insn);
 404       fprintf (dump_file, "Trying to simplify pattern:\n");
 405       print_rtl_single (dump_file, SET_SRC (set));
 406     }
 407
 408   /* We decided to turn do the optimization but allow it to be rejected for
 409      bisection purposes.  */
 410   if (!dbg_cnt (::ext_dce))
 411     {
 412       if (dump_file)
 413         fprintf (dump_file, "Rejected due to debug counter.\n");
 414       return;
 415     }
 416
 417   new_pattern = simplify_gen_subreg (GET_MODE (src), inner,
 418                                      GET_MODE (inner), 0);
 419   /* simplify_gen_subreg may fail in which case NEW_PATTERN will be NULL.
 420      We must not pass that as a replacement pattern to validate_change.  */
 421   if (new_pattern)
 422     {
 423       int ok = validate_change (insn, &SET_SRC (set), new_pattern, false);
 424
 425       rtx x = SET_DEST (set);
 426       while (SUBREG_P (x) || GET_CODE (x) == ZERO_EXTRACT)
 427         x = XEXP (x, 0);
 428
 429       gcc_assert (REG_P (x));
 430       if (ok)
 431         bitmap_set_bit (changed_pseudos, REGNO (x));
 432
 433       if (dump_file)
 434         {
 435           if (ok)
 436             fprintf (dump_file, "Successfully transformed to:\n");
 437           else
 438             fprintf (dump_file, "Failed transformation to:\n");
 439
 440           print_rtl_single (dump_file, new_pattern);
 441           fprintf (dump_file, "\n");
 442         }
 443     }
 444   else
 445     {
 446       if (dump_file)
 447         fprintf (dump_file, "Unable to generate valid SUBREG expression.\n");
 448     }
 449 }
 450
 451 /* Some operators imply that their second operand is fully live,
 452    regardless of how many bits in the output are live.  An example
 453    would be the shift count on a target without SHIFT_COUNT_TRUNCATED
 454    defined.
 455
 456    Return TRUE if CODE is such an operator.  FALSE otherwise.  */
 457
 458 static bool
 459 binop_implies_op2_fully_live (rtx_code code)
 460 {
 461   switch (code)
 462     {
 463     case ASHIFT:
 464     case LSHIFTRT:
 465     case ASHIFTRT:
 466     case ROTATE:
 467     case ROTATERT:
 468     case SS_ASHIFT:
 469     case US_ASHIFT:
 470       return !SHIFT_COUNT_TRUNCATED;
 471
 472     default:
 473       return false;
 474     }
 475 }
 476
 477 /* X, with code CODE, is an operation for which safe_for_live_propagation
 478    holds true, and bits set in MASK are live in the result.  Compute a
 479    mask of (potentially) live bits in the non-constant inputs.  In case of
 480    binop_implies_op2_fully_live (e.g. shifts), the computed mask may
 481    exclusively pertain to the first operand.  */
 482
 483 unsigned HOST_WIDE_INT
 484 carry_backpropagate (unsigned HOST_WIDE_INT mask, enum rtx_code code, rtx x)
 485 {
 486   if (mask == 0)
 487     return 0;
 488
 489   enum machine_mode mode = GET_MODE_INNER (GET_MODE (x));
 490   unsigned HOST_WIDE_INT mmask = GET_MODE_MASK (mode);
 491
 492   /* While we don't try to optimize operations on types larger
 493      than 64 bits, we do want to make sure not to invoke undefined
 494      behavior when presented with such operations during use
 495      processing.  The safe thing to do is to just return mmask
 496      for that scenario indicating every possible chunk is life.  */
 497   scalar_int_mode smode;
 498   if (!is_a <scalar_int_mode> (mode, &smode)
 499       || GET_MODE_BITSIZE (smode) > HOST_BITS_PER_WIDE_INT)
 500     return mmask;
 501
 502   switch (code)
 503     {
 504     case PLUS:
 505     case MINUS:
 506     case MULT:
 507       return (2ULL << floor_log2 (mask)) - 1;
 508
 509     /* We propagate for the shifted operand, but not the shift
 510        count.  The count is handled specially.  */
 511     case ASHIFT:
 512       if (CONST_INT_P (XEXP (x, 1))
 513           && known_lt (UINTVAL (XEXP (x, 1)), GET_MODE_BITSIZE (mode)))
 514         return (HOST_WIDE_INT)mask >> INTVAL (XEXP (x, 1));
 515       return (2ULL << floor_log2 (mask)) - 1;
 516
 517     /* We propagate for the shifted operand, but not the shift
 518        count.  The count is handled specially.  */
 519     case LSHIFTRT:
 520       if (CONST_INT_P (XEXP (x, 1))
 521           && known_lt (UINTVAL (XEXP (x, 1)), GET_MODE_BITSIZE (mode)))
 522         return mmask & (mask << INTVAL (XEXP (x, 1)));
 523       return mmask;
 524
 525     /* We propagate for the shifted operand, but not the shift
 526        count.  The count is handled specially.  */
 527     case ASHIFTRT:
 528       if (CONST_INT_P (XEXP (x, 1))
 529           && known_lt (UINTVAL (XEXP (x, 1)), GET_MODE_BITSIZE (mode)))
 530         {
 531           HOST_WIDE_INT sign = 0;
 532           if (HOST_BITS_PER_WIDE_INT - clz_hwi (mask) + INTVAL (XEXP (x, 1))
 533               > GET_MODE_BITSIZE (mode).to_constant ())
 534             sign = 1ULL << (GET_MODE_BITSIZE (mode).to_constant () - 1);
 535           return sign | (mmask & (mask << INTVAL (XEXP (x, 1))));
 536         }
 537       return mmask;
 538
 539     case SMUL_HIGHPART:
 540     case UMUL_HIGHPART:
 541       if (XEXP (x, 1) == const0_rtx)
 542         return 0;
 543       if (XEXP (x, 1) == const1_rtx)
 544         return mmask;
 545       if (CONST_INT_P (XEXP (x, 1)))
 546         {
 547           if (pow2p_hwi (INTVAL (XEXP (x, 1))))
 548             return mmask & (mask << (GET_MODE_BITSIZE (mode).to_constant ()
 549                                      - exact_log2 (INTVAL (XEXP (x, 1)))));
 550
 551           int bits = (HOST_BITS_PER_WIDE_INT
 552                       + GET_MODE_BITSIZE (mode).to_constant ()
 553                       - clz_hwi (mask) - ctz_hwi (INTVAL (XEXP (x, 1))));
 554           if (bits < GET_MODE_BITSIZE (mode).to_constant ())
 555             return (1ULL << bits) - 1;
 556         }
 557       return mmask;
 558
 559     case SIGN_EXTEND:
 560       if (mask & ~GET_MODE_MASK (GET_MODE_INNER (GET_MODE (XEXP (x, 0)))))
 561         mask |= 1ULL << (GET_MODE_BITSIZE (mode).to_constant () - 1);
 562       return mask;
 563
 564     /* We propagate for the shifted operand, but not the shift
 565        count.  The count is handled specially.  */
 566     case SS_ASHIFT:
 567     case US_ASHIFT:
 568       if (CONST_INT_P (XEXP (x, 1))
 569           && UINTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (mode).to_constant ())
 570         {
 571           return ((mmask & ~((unsigned HOST_WIDE_INT)mmask
 572                              >> (INTVAL (XEXP (x, 1))
 573                                  + (XEXP (x, 1) != const0_rtx
 574                                     && code == SS_ASHIFT))))
 575                   | ((HOST_WIDE_INT)mask >> INTVAL (XEXP (x, 1))));
 576         }
 577       return mmask;
 578
 579     default:
 580       return mask;
 581     }
 582 }
 583
 584 /* Process uses in INSN contained in OBJ.  Set appropriate bits in LIVENOW
 585    for any chunks of pseudos that become live, potentially filtering using
 586    bits from LIVE_TMP.
 587
 588    If MODIFY is true, then optimize sign/zero extensions to SUBREGs when
 589    the extended bits are never read and mark pseudos which had extensions
 590    eliminated in CHANGED_PSEUDOS.  */
 591
 592 static void
 593 ext_dce_process_uses (rtx_insn *insn, rtx obj,
 594                       bitmap live_tmp, bool skipped_dest)
 595 {
 596   subrtx_var_iterator::array_type array_var;
 597   FOR_EACH_SUBRTX_VAR (iter, array_var, obj, NONCONST)
 598     {
 599       /* An EXPR_LIST (from call fusage) ends in NULL_RTX.  */
 600       rtx x = *iter;
 601       if (x == NULL_RTX)
 602         continue;
 603
 604       /* So the basic idea in this FOR_EACH_SUBRTX_VAR loop is to
 605          handle SETs explicitly, possibly propagating live information
 606          into the uses.
 607
 608          We may continue the loop at various points which will cause
 609          iteration into the next level of RTL.  Breaking from the loop
 610          is never safe as it can lead us to fail to process some of the
 611          RTL and thus not make objects live when necessary.  */
 612       enum rtx_code xcode = GET_CODE (x);
 613       if (xcode == SET)
 614         {
 615           const_rtx dst = SET_DEST (x);
 616           rtx src = SET_SRC (x);
 617           const_rtx y;
 618           unsigned HOST_WIDE_INT bit = 0;
 619
 620           /* The code of the RHS of a SET.  */
 621           enum rtx_code code = GET_CODE (src);
 622
 623           /* ?!? How much of this should mirror SET handling, potentially
 624              being shared?   */
 625           if (SUBREG_P (dst) && SUBREG_BYTE (dst).is_constant ())
 626             {
 627               bit = subreg_lsb (dst).to_constant ();
 628               if (bit >= HOST_BITS_PER_WIDE_INT)
 629                 bit = HOST_BITS_PER_WIDE_INT - 1;
 630               dst = SUBREG_REG (dst);
 631             }
 632           else if (GET_CODE (dst) == STRICT_LOW_PART)
 633             dst = XEXP (dst, 0);
 634
 635           /* Main processing of the uses.  Two major goals here.
 636
 637              First, we want to try and propagate liveness (or the lack
 638              thereof) from the destination register to the source
 639              register(s).
 640
 641              Second, if the source is an extension, try to optimize
 642              it into a SUBREG.  The SUBREG form indicates we don't
 643              care about the upper bits and will usually be copy
 644              propagated away.
 645
 646              If we fail to handle something in here, the expectation
 647              is the iterator will dive into the sub-components and
 648              mark all the chunks in any found REGs as live.  */
 649           if (REG_P (dst) && safe_for_live_propagation (code))
 650             {
 651               /* Create a mask representing the bits of this output
 652                  operand that are live after this insn.  We can use
 653                  this information to refine the live in state of
 654                  inputs to this insn in many cases.
 655
 656                  We have to do this on a per SET basis, we might have
 657                  an INSN with multiple SETS, some of which can narrow
 658                  the source operand liveness, some of which may not.  */
 659               unsigned HOST_WIDE_INT dst_mask = 0;
 660               HOST_WIDE_INT rn = REGNO (dst);
 661               unsigned HOST_WIDE_INT mask_array[]
 662                 = { 0xff, 0xff00, 0xffff0000ULL, -0x100000000ULL };
 663               for (int i = 0; i < 4; i++)
 664                 if (bitmap_bit_p (live_tmp, 4 * rn + i))
 665                   dst_mask |= mask_array[i];
 666               dst_mask >>= bit;
 667
 668               /* If we ignored a destination during set processing, then
 669                  consider all the bits live.  */
 670               if (skipped_dest)
 671                 dst_mask = -1;
 672
 673               /* ??? Could also handle ZERO_EXTRACT / SIGN_EXTRACT
 674                  of the source specially to improve optimization.  */
 675               if (code == SIGN_EXTEND || code == ZERO_EXTEND)
 676                 {
 677                   rtx inner = XEXP (src, 0);
 678                   unsigned HOST_WIDE_INT src_mask
 679                     = GET_MODE_MASK (GET_MODE_INNER (GET_MODE (inner)));
 680
 681                   /* DST_MASK could be zero if we had something in the SET
 682                      that we couldn't handle.  */
 683                   if (modify && !skipped_dest && (dst_mask & ~src_mask) == 0)
 684                     ext_dce_try_optimize_insn (insn, x);
 685
 686                   /* Stripping the extension here just seems wrong on multiple
 687                      levels.  It's source side handling, so it seems like it
 688                      belongs in the loop below.  Stripping here also makes it
 689                      harder than necessary to properly handle live bit groups
 690                      for (ANY_EXTEND (SUBREG)) where the SUBREG has
 691                      SUBREG_PROMOTED state.  */
 692                   dst_mask &= src_mask;
 693                   src = XEXP (src, 0);
 694                   code = GET_CODE (src);
 695                 }
 696
 697               /* Optimization is done at this point.  We just want to make
 698                  sure everything that should get marked as live is marked
 699                  from here onward.  Shouldn't the backpropagate step happen
 700                  before optimization?  */
 701               dst_mask = carry_backpropagate (dst_mask, code, src);
 702
 703               /* We will handle the other operand of a binary operator
 704                  at the bottom of the loop by resetting Y.  */
 705               if (BINARY_P (src))
 706                 y = XEXP (src, 0);
 707               else
 708                 y = src;
 709
 710               /* We're inside a SET and want to process the source operands
 711                  making things live.  Breaking from this loop will cause
 712                  the iterator to work on sub-rtxs, so it is safe to break
 713                  if we see something we don't know how to handle.
 714
 715                  This code is just hokey as it really just handles trivial
 716                  unary and binary cases.  Otherwise the loop exits and we
 717                  continue iterating on sub-rtxs, but outside the set context.  */
 718               unsigned HOST_WIDE_INT save_mask = dst_mask;
 719               for (;;)
 720                 {
 721                   /* In general we want to restore DST_MASK before each loop
 722                      iteration.  The exception is when the opcode implies that
 723                      the other operand is fully live.  That's handled by
 724                      changing SAVE_MASK below.  */
 725                   dst_mask = save_mask;
 726                   /* Strip an outer paradoxical subreg.  The bits outside
 727                      the inner mode are don't cares.  So we can just strip
 728                      and process the inner object.  */
 729                   if (paradoxical_subreg_p (y))
 730                     y = XEXP (y, 0);
 731                   else if (SUBREG_P (y) && SUBREG_BYTE (y).is_constant ())
 732                     {
 733                       /* We really want to know the outer code here, ie do we
 734                          have (ANY_EXTEND (SUBREG ...)) as we need to know if
 735                          the extension matches the SUBREG_PROMOTED state.  In
 736                          that case optimizers can turn the extension into a
 737                          simple copy.  Which means that bits outside the
 738                          SUBREG's mode are actually live.
 739
 740                          We don't want to mark those bits live unnecessarily
 741                          as that inhibits extension elimination in important
 742                          cases such as those in Coremark.  So we need that
 743                          outer code.  */
 744                       if (!REG_P (SUBREG_REG (y))
 745                           || (SUBREG_PROMOTED_VAR_P (y)
 746                               && ((GET_CODE (SET_SRC (x)) == SIGN_EXTEND
 747                                    && SUBREG_PROMOTED_SIGNED_P (y))
 748                                   || (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
 749                                       && SUBREG_PROMOTED_UNSIGNED_P (y)))))
 750                         break;
 751
 752                       bit = subreg_lsb (y).to_constant ();
 753
 754                       /* If this is a wide object (more bits than we can fit
 755                          in a HOST_WIDE_INT), then just break from the SET
 756                          context.   That will cause the iterator to walk down
 757                          into the subrtx and if we land on a REG we'll mark
 758                          the whole think live.  */
 759                       if (bit >= HOST_BITS_PER_WIDE_INT)
 760                         break;
 761
 762                       /* The SUBREG's mode determines the live width.  */
 763                       if (dst_mask)
 764                         {
 765                           dst_mask <<= bit;
 766                           if (!dst_mask)
 767                             dst_mask = -0x100000000ULL;
 768                         }
 769                       y = SUBREG_REG (y);
 770                     }
 771
 772                   if (REG_P (y))
 773                     {
 774                       /* We have found the use of a register.  We need to mark
 775                          the appropriate chunks of the register live.  The mode
 776                          of the REG is a starting point.  We may refine that
 777                          based on what chunks in the output were live.  */
 778                       rn = 4 * REGNO (y);
 779                       unsigned HOST_WIDE_INT tmp_mask = dst_mask;
 780
 781                       /* If the RTX code for the SET_SRC is not one we can
 782                          propagate destination liveness through, then just
 783                          set the mask to the mode's mask.  */
 784                       if (!safe_for_live_propagation (code))
 785                         tmp_mask
 786                           = GET_MODE_MASK (GET_MODE_INNER (GET_MODE (y)));
 787
 788                       if (tmp_mask & 0xff)
 789                         bitmap_set_bit (livenow, rn);
 790                       if (tmp_mask & 0xff00)
 791                         bitmap_set_bit (livenow, rn + 1);
 792                       if (tmp_mask & 0xffff0000ULL)
 793                         bitmap_set_bit (livenow, rn + 2);
 794                       if (tmp_mask & -0x100000000ULL)
 795                         bitmap_set_bit (livenow, rn + 3);
 796                     }
 797                   else if (!CONSTANT_P (y))
 798                     break;
 799
 800                   /* We might have (ashift (const_int 1) (reg...))
 801                      By setting dst_mask we can continue iterating on the
 802                      the next operand and it will be considered fully live.
 803
 804                      Note that since we restore DST_MASK from SAVE_MASK at the
 805                      top of the loop, we have to change SAVE_MASK to get the
 806                      semantics we want.  */
 807                   if (binop_implies_op2_fully_live (GET_CODE (src)))
 808                     save_mask = -1;
 809
 810                   /* If this was anything but a binary operand, break the inner
 811                      loop.  This is conservatively correct as it will cause the
 812                      iterator to look at the sub-rtxs outside the SET context.  */
 813                   if (!BINARY_P (src))
 814                     break;
 815
 816                   /* We processed the first operand of a binary operator.  Now
 817                      handle the second.  */
 818                   y = XEXP (src, 1), src = pc_rtx;
 819                 }
 820
 821               /* These are leaf nodes, no need to iterate down into them.  */
 822               if (REG_P (y) || CONSTANT_P (y))
 823                 iter.skip_subrtxes ();
 824             }
 825         }
 826       /* If we are reading the low part of a SUBREG, then we can
 827          refine liveness of the input register, otherwise let the
 828          iterator continue into SUBREG_REG.  */
 829       else if (SUBREG_P (x)
 830                && REG_P (SUBREG_REG (x))
 831                && !paradoxical_subreg_p (x)
 832                && subreg_lowpart_p (x)
 833                && GET_MODE_BITSIZE (GET_MODE (x)).is_constant ()
 834                && GET_MODE_BITSIZE (GET_MODE (x)).to_constant () <= 32)
 835         {
 836           HOST_WIDE_INT size = GET_MODE_BITSIZE (GET_MODE (x)).to_constant ();
 837           HOST_WIDE_INT rn = 4 * REGNO (SUBREG_REG (x));
 838
 839           /* If this is a promoted subreg, then more of it may be live than
 840              is otherwise obvious.  */
 841           if (SUBREG_PROMOTED_VAR_P (x))
 842             size = GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))).to_constant ();
 843
 844           bitmap_set_bit (livenow, rn);
 845           if (size > 8)
 846             bitmap_set_bit (livenow, rn + 1);
 847           if (size > 16)
 848             bitmap_set_bit (livenow, rn + 2);
 849           if (size >= 32)
 850             bitmap_set_bit (livenow, rn + 3);
 851           iter.skip_subrtxes ();
 852         }
 853       /* If we have a register reference that is not otherwise handled,
 854          just assume all the chunks are live.  */
 855       else if (REG_P (x))
 856         bitmap_set_range (livenow, REGNO (x) * 4, group_limit (x));
 857     }
 858 }
 859
 860 /* Process a single basic block BB with current liveness information
 861    in LIVENOW, returning updated liveness information.
 862
 863    If MODIFY is true, then this is the last pass and unnecessary
 864    extensions should be eliminated when possible.  If an extension
 865    is removed, the source pseudo is marked in CHANGED_PSEUDOS.  */
 866
 867 static void
 868 ext_dce_process_bb (basic_block bb)
 869 {
 870   rtx_insn *insn;
 871
 872   FOR_BB_INSNS_REVERSE (bb, insn)
 873     {
 874       if (!NONDEBUG_INSN_P (insn))
 875         continue;
 876
 877       /* Live-out state of the destination of this insn.  We can
 878          use this to refine the live-in state of the sources of
 879          this insn in many cases.  */
 880       bitmap live_tmp = BITMAP_ALLOC (NULL);
 881
 882       /* First process any sets/clobbers in INSN.  */
 883       bool skipped_dest = ext_dce_process_sets (insn, PATTERN (insn), live_tmp);
 884
 885       /* CALL_INSNs need processing their fusage data.  */
 886       if (CALL_P (insn))
 887         skipped_dest |= ext_dce_process_sets (insn,
 888                                               CALL_INSN_FUNCTION_USAGE (insn),
 889                                               live_tmp);
 890
 891       /* And now uses, optimizing away SIGN/ZERO extensions as we go.  */
 892       ext_dce_process_uses (insn, PATTERN (insn), live_tmp, skipped_dest);
 893
 894       /* A nonlocal goto implicitly uses the frame pointer.  */
 895       if (JUMP_P (insn) && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
 896         {
 897           bitmap_set_range (livenow, FRAME_POINTER_REGNUM * 4, 4);
 898           if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
 899             bitmap_set_range (livenow, HARD_FRAME_POINTER_REGNUM * 4, 4);
 900         }
 901
 902       /* And process fusage data for the use as well.  */
 903       if (CALL_P (insn))
 904         {
 905           if (!FAKE_CALL_P (insn))
 906             bitmap_set_range (livenow, STACK_POINTER_REGNUM * 4, 4);
 907
 908           /* If this is not a call to a const fucntion, then assume it
 909              can read any global register.  */
 910           if (!RTL_CONST_CALL_P (insn))
 911             for (unsigned i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 912               if (global_regs[i])
 913                 bitmap_set_range (livenow, i * 4, 4);
 914
 915           ext_dce_process_uses (insn, CALL_INSN_FUNCTION_USAGE (insn), live_tmp, false);
 916         }
 917
 918       BITMAP_FREE (live_tmp);
 919     }
 920 }
 921
 922 /* We optimize away sign/zero extensions in this pass and replace
 923    them with SUBREGs indicating certain bits are don't cares.
 924
 925    This changes the SUBREG_PROMOTED_VAR_P state of the object.
 926    It is fairly painful to fix this on the fly, so we have
 927    recorded which pseudos are affected and we look for SUBREGs
 928    of those pseudos and fix them up.  */
 929
 930 static void
 931 reset_subreg_promoted_p (void)
 932 {
 933   /* If we removed an extension, that changed the promoted state
 934      of the destination of that extension.  Thus we need to go
 935      find any SUBREGs that reference that pseudo and adjust their
 936      SUBREG_PROMOTED_P state.  */
 937   for (rtx_insn *insn = get_insns(); insn; insn = NEXT_INSN (insn))
 938     {
 939       if (!NONDEBUG_INSN_P (insn))
 940         continue;
 941
 942       rtx pat = PATTERN (insn);
 943       subrtx_var_iterator::array_type array;
 944       FOR_EACH_SUBRTX_VAR (iter, array, pat, NONCONST)
 945         {
 946           rtx sub = *iter;
 947
 948           /* We only care about SUBREGs.  */
 949           if (GET_CODE (sub) != SUBREG)
 950             continue;
 951
 952           const_rtx x = SUBREG_REG (sub);
 953
 954           /* We only care if the inner object is a REG.  */
 955           if (!REG_P (x))
 956             continue;
 957
 958           /* And only if the SUBREG is a promoted var.  */
 959           if (!SUBREG_PROMOTED_VAR_P (sub))
 960             continue;
 961
 962           if (bitmap_bit_p (changed_pseudos, REGNO (x)))
 963             SUBREG_PROMOTED_VAR_P (sub) = 0;
 964         }
 965     }
 966 }
 967
 968 /* Initialization of the ext-dce pass.  Primarily this means
 969    setting up the various bitmaps we utilize.  */
 970
 971 static void
 972 ext_dce_init (void)
 973 {
 974   livein.create (last_basic_block_for_fn (cfun));
 975   livein.quick_grow_cleared (last_basic_block_for_fn (cfun));
 976   for (int i = 0; i < last_basic_block_for_fn (cfun); i++)
 977     bitmap_initialize (&livein[i], &bitmap_default_obstack);
 978
 979   auto_bitmap refs (&bitmap_default_obstack);
 980   df_get_exit_block_use_set (refs);
 981
 982   unsigned i;
 983   bitmap_iterator bi;
 984   EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
 985     make_reg_live (&livein[EXIT_BLOCK], i);
 986
 987   livenow = BITMAP_ALLOC (NULL);
 988   all_blocks = BITMAP_ALLOC (NULL);
 989   changed_pseudos = BITMAP_ALLOC (NULL);
 990
 991   for (int i = 0; i < last_basic_block_for_fn (cfun); i++)
 992     if (i != ENTRY_BLOCK && i != EXIT_BLOCK)
 993       bitmap_set_bit (all_blocks, i);
 994
 995   modify = false;
 996 }
 997
 998 /* Finalization of the ext-dce pass.  Primarily this means
 999    releasing up the various bitmaps we utilize.  */
1000
1001 static void
1002 ext_dce_finish (void)
1003 {
1004   for (unsigned i = 0; i < livein.length (); i++)
1005     bitmap_clear (&livein[i]);
1006   livein.release ();
1007
1008   BITMAP_FREE (livenow);
1009   BITMAP_FREE (changed_pseudos);
1010   BITMAP_FREE (all_blocks);
1011 }
1012
1013 /* Process block number BB_INDEX as part of the backward
1014    simple dataflow analysis.  Return TRUE if something in
1015    this block changed or FALSE otherwise.  */
1016
1017 static bool
1018 ext_dce_rd_transfer_n (int bb_index)
1019 {
1020   /* The ENTRY/EXIT blocks never change.  */
1021   if (bb_index == ENTRY_BLOCK || bb_index == EXIT_BLOCK)
1022     return false;
1023
1024   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1025
1026   /* Make everything live that's live in the successors.  */
1027   bitmap_clear (livenow);
1028   edge_iterator ei;
1029   edge e;
1030
1031   FOR_EACH_EDGE (e, ei, bb->succs)
1032     bitmap_ior_into (livenow, &livein[e->dest->index]);
1033
1034   ext_dce_process_bb (bb);
1035
1036   /* We may have narrowed the set of live objects at the start
1037      of this block.  If so, update the bitmaps and indicate to
1038      the generic dataflow code that something changed.  */
1039   if (!bitmap_equal_p (&livein[bb_index], livenow))
1040     {
1041       bitmap_copy (&livein[bb_index], livenow);
1042       return true;
1043     }
1044
1045   return false;
1046 }
1047
1048 /* Dummy function for the df_simple_dataflow API.  */
1049 static bool ext_dce_rd_confluence_n (edge) { return true; }
1050
1051 /* Use lifetime analyis to identify extensions that set bits that
1052    are never read.  Turn such extensions into SUBREGs instead which
1053    can often be propagated away.  */
1054
1055 void
1056 ext_dce_execute (void)
1057 {
1058   df_analyze ();
1059   ext_dce_init ();
1060
1061   do
1062     {
1063       df_simple_dataflow (DF_BACKWARD, NULL, NULL,
1064                           ext_dce_rd_confluence_n, ext_dce_rd_transfer_n,
1065                           all_blocks, df_get_postorder (DF_BACKWARD),
1066                           df_get_n_blocks (DF_BACKWARD));
1067       modify = !modify;
1068     }
1069   while (modify);
1070
1071   reset_subreg_promoted_p ();
1072
1073   ext_dce_finish ();
1074 }
1075
1076
1077 namespace {
1078
1079 const pass_data pass_data_ext_dce =
1080 {
1081   RTL_PASS, /* type */
1082   "ext_dce", /* name */
1083   OPTGROUP_NONE, /* optinfo_flags */
1084   TV_NONE, /* tv_id */
1085   PROP_cfglayout, /* properties_required */
1086   0, /* properties_provided */
1087   0, /* properties_destroyed */
1088   0, /* todo_flags_start */
1089   TODO_df_finish, /* todo_flags_finish */
1090 };
1091
1092 class pass_ext_dce : public rtl_opt_pass
1093 {
1094 public:
1095   pass_ext_dce (gcc::context *ctxt)
1096     : rtl_opt_pass (pass_data_ext_dce, ctxt)
1097   {}
1098
1099   /* opt_pass methods: */
1100   virtual bool gate (function *) { return flag_ext_dce && optimize > 0; }
1101   virtual unsigned int execute (function *)
1102     {
1103       ext_dce_execute ();
1104       return 0;
1105     }
1106
1107 }; // class pass_combine
1108
1109 } // anon namespace
1110
1111 rtl_opt_pass *
1112 make_pass_ext_dce (gcc::context *ctxt)
1113 {
1114   return new pass_ext_dce (ctxt);
1115 }