gcc/compare-elim.cc

   1 /* Post-reload compare elimination.
   2    Copyright (C) 2010-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 /* There is a set of targets whose general-purpose move or addition
  21    instructions clobber the flags.  These targets cannot split their
  22    CBRANCH/CSTORE etc patterns before reload is complete, lest reload
  23    itself insert these instructions in between the flags setter and user.
  24    Because these targets cannot split the compare from the use, they
  25    cannot make use of the comparison elimination offered by the combine pass.
  26
  27    This is a small pass intended to provide comparison elimination similar to
  28    what was available via NOTICE_UPDATE_CC for cc0 targets.
  29
  30    This pass assumes:
  31
  32    (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.
  33
  34    (1) All comparison patterns are represented as
  35
  36         [(set (reg:CC) (compare:CC (reg) (reg_or_immediate)))]
  37
  38    (2) All insn patterns that modify the flags are represented as
  39
  40         [(set (reg) (operation)
  41          (clobber (reg:CC))]
  42
  43    (3) If an insn of form (2) can usefully set the flags, there is
  44        another pattern of the form
  45
  46         [(set (reg:CCM) (compare:CCM (operation) (immediate)))
  47          (set (reg) (operation)]
  48
  49        The mode CCM will be chosen as if by SELECT_CC_MODE.
  50
  51    Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
  52    This could be handled as a future enhancement.
  53 */
  54
  55 #include "config.h"
  56 #include "system.h"
  57 #include "coretypes.h"
  58 #include "backend.h"
  59 #include "target.h"
  60 #include "rtl.h"
  61 #include "df.h"
  62 #include "memmodel.h"
  63 #include "tm_p.h"
  64 #include "insn-config.h"
  65 #include "recog.h"
  66 #include "emit-rtl.h"
  67 #include "cfgrtl.h"
  68 #include "tree-pass.h"
  69 #include "domwalk.h"
  70
  71 \f
  72 /* These structures describe a comparison and how it is used.  */
  73
  74 /* The choice of maximum 3 uses comes from wanting to eliminate the two
  75    duplicate compares from a three-way branch on the sign of a value.
  76    This is also sufficient to eliminate the duplicate compare against the
  77    high-part of a double-word comparison.  */
  78 #define MAX_CMP_USE 3
  79
  80 struct comparison_use
  81 {
  82   /* The instruction in which the result of the compare is used.  */
  83   rtx_insn *insn;
  84   /* The location of the flags register within the use.  */
  85   rtx *loc;
  86   /* The comparison code applied against the flags register.  */
  87   enum rtx_code code;
  88 };
  89
  90 struct comparison
  91 {
  92   /* The comparison instruction.  */
  93   rtx_insn *insn;
  94
  95   /* The insn prior to the comparison insn that clobbers the flags.  */
  96   rtx_insn *prev_clobber;
  97
  98   /* The insn prior to the comparison insn that sets in_a REG.  */
  99   rtx_insn *in_a_setter;
 100
 101   /* The two values being compared.  These will be either REGs or
 102      constants.  */
 103   rtx in_a, in_b;
 104
 105   /* The REG_EH_REGION of the comparison.  */
 106   rtx eh_note;
 107
 108   /* Information about how this comparison is used.  */
 109   struct comparison_use uses[MAX_CMP_USE];
 110
 111   /* The original CC_MODE for this comparison.  */
 112   machine_mode orig_mode;
 113
 114   /* The number of uses identified for this comparison.  */
 115   unsigned short n_uses;
 116
 117   /* True if not all uses of this comparison have been identified.
 118      This can happen either for overflowing the array above, or if
 119      the flags register is used in some unusual context.  */
 120   bool missing_uses;
 121
 122   /* True if its inputs are still valid at the end of the block.  */
 123   bool inputs_valid;
 124
 125   /* Whether IN_A is wrapped in a NOT before being compared.  */
 126   bool not_in_a;
 127 };
 128
 129 static vec<comparison *> all_compares;
 130
 131 /* Return whether X is a NOT unary expression.  */
 132
 133 static bool
 134 is_not (rtx x)
 135 {
 136   return GET_CODE (x) == NOT;
 137 }
 138
 139 /* Strip a NOT unary expression around X, if any.  */
 140
 141 static rtx
 142 strip_not (rtx x)
 143 {
 144   if (is_not (x))
 145     return XEXP (x, 0);
 146
 147   return x;
 148 }
 149
 150 /* Look for a "conforming" comparison, as defined above.  If valid, return
 151    the rtx for the COMPARE itself.  */
 152
 153 static rtx
 154 conforming_compare (rtx_insn *insn)
 155 {
 156   rtx set, src, dest;
 157
 158   set = single_set (insn);
 159   if (set == NULL)
 160     return NULL;
 161
 162   src = SET_SRC (set);
 163   if (GET_CODE (src) != COMPARE)
 164     return NULL;
 165
 166   dest = SET_DEST (set);
 167   if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
 168     return NULL;
 169
 170   if (!REG_P (strip_not (XEXP (src, 0))))
 171     return NULL;
 172
 173   if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
 174     return src;
 175
 176   if (GET_CODE (XEXP (src, 1)) == UNSPEC)
 177     {
 178       for (int i = 0; i < XVECLEN (XEXP (src, 1), 0); i++)
 179         if (!REG_P (XVECEXP (XEXP (src, 1), 0, i)))
 180           return NULL;
 181       return src;
 182     }
 183
 184   return NULL;
 185 }
 186
 187 /* Look for a pattern of the "correct" form for an insn with a flags clobber
 188    for which we may be able to eliminate a compare later.  We're not looking
 189    to validate any inputs at this time, merely see that the basic shape is
 190    correct.  The term "arithmetic" may be somewhat misleading...  */
 191
 192 static bool
 193 arithmetic_flags_clobber_p (rtx_insn *insn)
 194 {
 195   rtx pat, x;
 196
 197   if (!NONJUMP_INSN_P (insn))
 198     return false;
 199   pat = PATTERN (insn);
 200   if (asm_noperands (pat) >= 0)
 201     return false;
 202
 203   if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
 204     {
 205       x = XVECEXP (pat, 0, 0);
 206       if (GET_CODE (x) != SET)
 207         return false;
 208       x = SET_DEST (x);
 209       if (!REG_P (x))
 210         return false;
 211
 212       x = XVECEXP (pat, 0, 1);
 213       if (GET_CODE (x) == CLOBBER)
 214         {
 215           x = XEXP (x, 0);
 216           if (REG_P (x) && REGNO (x) == targetm.flags_regnum)
 217             return true;
 218         }
 219     }
 220
 221   return false;
 222 }
 223
 224 /* Look for uses of FLAGS in INSN.  If we find one we can analyze, record
 225    it in CMP; otherwise indicate that we've missed a use.  */
 226
 227 static void
 228 find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
 229 {
 230   df_ref use;
 231
 232   /* If we've already lost track of uses, don't bother collecting more.  */
 233   if (cmp->missing_uses)
 234     return;
 235
 236   /* Find a USE of the flags register.  */
 237   FOR_EACH_INSN_USE (use, insn)
 238     if (DF_REF_REGNO (use) == targetm.flags_regnum)
 239       {
 240         rtx x, *loc;
 241
 242         /* If this is an unusual use, quit.  */
 243         if (DF_REF_TYPE (use) != DF_REF_REG_USE)
 244           goto fail;
 245
 246         /* If we've run out of slots to record uses, quit.  */
 247         if (cmp->n_uses == MAX_CMP_USE)
 248           goto fail;
 249
 250         /* Unfortunately the location of the flags register, while present
 251            in the reference structure, doesn't help.  We need to find the
 252            comparison code that is outer to the actual flags use.  */
 253         loc = DF_REF_LOC (use);
 254         x = PATTERN (insn);
 255         if (GET_CODE (x) == PARALLEL)
 256           x = XVECEXP (x, 0, 0);
 257         x = SET_SRC (x);
 258         if (GET_CODE (x) == IF_THEN_ELSE)
 259           x = XEXP (x, 0);
 260         if (COMPARISON_P (x)
 261             && loc == &XEXP (x, 0)
 262             && XEXP (x, 1) == const0_rtx)
 263           {
 264             /* We've found a use of the flags that we understand.  */
 265             struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
 266             cuse->insn = insn;
 267             cuse->loc = loc;
 268             cuse->code = GET_CODE (x);
 269           }
 270         else
 271           goto fail;
 272       }
 273   return;
 274
 275  fail:
 276   /* We failed to recognize this use of the flags register.  */
 277   cmp->missing_uses = true;
 278 }
 279
 280 class find_comparison_dom_walker : public dom_walker
 281 {
 282 public:
 283   find_comparison_dom_walker (cdi_direction direction)
 284     : dom_walker (direction) {}
 285
 286   edge before_dom_children (basic_block) final override;
 287 };
 288
 289 /* Return true if conforming COMPARE with EH_NOTE is redundant with comparison
 290    CMP and can thus be eliminated.  */
 291
 292 static bool
 293 can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
 294 {
 295   /* Take care that it's in the same EH region.  */
 296   if (cfun->can_throw_non_call_exceptions
 297       && !rtx_equal_p (eh_note, cmp->eh_note))
 298     return false;
 299
 300   /* Make sure the compare is redundant with the previous.  */
 301   if (!rtx_equal_p (strip_not (XEXP (compare, 0)), cmp->in_a)
 302       || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
 303     return false;
 304
 305   if (is_not (XEXP (compare, 0)) != cmp->not_in_a)
 306     return false;
 307
 308   /* New mode must be compatible with the previous compare mode.  */
 309   machine_mode new_mode
 310     = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
 311
 312   if (new_mode == VOIDmode)
 313     return false;
 314
 315   if (cmp->orig_mode != new_mode)
 316     {
 317       /* Generate new comparison for substitution.  */
 318       rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
 319       rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
 320       x = gen_rtx_SET (flags, x);
 321
 322       if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
 323         return false;
 324
 325       cmp->orig_mode = new_mode;
 326     }
 327
 328   return true;
 329 }
 330
 331 /* Identify comparison instructions within BB.  If the flags from the last
 332    compare in the BB is live at the end of the block, install the compare
 333    in BB->AUX.  Called via dom_walker.walk ().  */
 334
 335 edge
 336 find_comparison_dom_walker::before_dom_children (basic_block bb)
 337 {
 338   rtx_insn *insn, *next;
 339   bool need_purge = false;
 340   rtx_insn *last_setter[FIRST_PSEUDO_REGISTER];
 341
 342   /* The last comparison that was made.  Will be reset to NULL
 343      once the flags are clobbered.  */
 344   struct comparison *last_cmp = NULL;
 345
 346   /* True iff the last comparison has not been clobbered, nor
 347      have its inputs.  Used to eliminate duplicate compares.  */
 348   bool last_cmp_valid = false;
 349
 350   /* The last insn that clobbered the flags, if that insn is of
 351      a form that may be valid for eliminating a following compare.
 352      To be reset to NULL once the flags are set otherwise.  */
 353   rtx_insn *last_clobber = NULL;
 354
 355   /* Propagate the last live comparison throughout the extended basic block. */
 356   if (single_pred_p (bb))
 357     {
 358       last_cmp = (struct comparison *) single_pred (bb)->aux;
 359       if (last_cmp)
 360         last_cmp_valid = last_cmp->inputs_valid;
 361     }
 362
 363   memset (last_setter, 0, sizeof (last_setter));
 364   for (insn = BB_HEAD (bb); insn; insn = next)
 365     {
 366       rtx src;
 367
 368       next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
 369       if (!NONDEBUG_INSN_P (insn))
 370         continue;
 371
 372       src = conforming_compare (insn);
 373       if (src)
 374         {
 375           rtx eh_note = NULL;
 376
 377           if (cfun->can_throw_non_call_exceptions)
 378             eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
 379
 380           if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
 381             {
 382               if (eh_note)
 383                 need_purge = true;
 384               delete_insn (insn);
 385               continue;
 386             }
 387
 388           last_cmp = XCNEW (struct comparison);
 389           last_cmp->insn = insn;
 390           last_cmp->prev_clobber = last_clobber;
 391           last_cmp->in_a = strip_not (XEXP (src, 0));
 392           last_cmp->in_b = XEXP (src, 1);
 393           last_cmp->not_in_a = is_not (XEXP (src, 0));
 394           last_cmp->eh_note = eh_note;
 395           last_cmp->orig_mode = GET_MODE (src);
 396           if (last_cmp->in_b == const0_rtx
 397               && last_setter[REGNO (last_cmp->in_a)])
 398             {
 399               rtx set = single_set (last_setter[REGNO (last_cmp->in_a)]);
 400               if (set && rtx_equal_p (SET_DEST (set), last_cmp->in_a))
 401                 last_cmp->in_a_setter = last_setter[REGNO (last_cmp->in_a)];
 402             }
 403           all_compares.safe_push (last_cmp);
 404
 405           /* It's unusual, but be prepared for comparison patterns that
 406              also clobber an input, or perhaps a scratch.  */
 407           last_clobber = NULL;
 408           last_cmp_valid = true;
 409         }
 410
 411       else
 412         {
 413           /* Notice if this instruction uses the flags register.  */
 414           if (last_cmp)
 415             find_flags_uses_in_insn (last_cmp, insn);
 416
 417           /* Notice if this instruction kills the flags register.  */
 418           df_ref def;
 419           FOR_EACH_INSN_DEF (def, insn)
 420             if (DF_REF_REGNO (def) == targetm.flags_regnum)
 421               {
 422                 /* See if this insn could be the "clobber" that eliminates
 423                    a future comparison.   */
 424                 last_clobber = (arithmetic_flags_clobber_p (insn)
 425                                 ? insn : NULL);
 426
 427                 /* In either case, the previous compare is no longer valid.  */
 428                 last_cmp = NULL;
 429                 last_cmp_valid = false;
 430                 break;
 431               }
 432         }
 433
 434       /* Notice if any of the inputs to the comparison have changed
 435          and remember last insn that sets each register.  */
 436       df_ref def;
 437       FOR_EACH_INSN_DEF (def, insn)
 438         {
 439           if (last_cmp_valid
 440               && (DF_REF_REGNO (def) == REGNO (last_cmp->in_a)
 441                   || (REG_P (last_cmp->in_b)
 442                       && DF_REF_REGNO (def) == REGNO (last_cmp->in_b))))
 443             last_cmp_valid = false;
 444           last_setter[DF_REF_REGNO (def)] = insn;
 445         }
 446     }
 447
 448   /* Remember the live comparison for subsequent members of
 449      the extended basic block.  */
 450   if (last_cmp)
 451     {
 452       bb->aux = last_cmp;
 453       last_cmp->inputs_valid = last_cmp_valid;
 454
 455       /* Look to see if the flags register is live outgoing here, and
 456          incoming to any successor not part of the extended basic block.  */
 457       if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
 458         {
 459           edge e;
 460           edge_iterator ei;
 461
 462           FOR_EACH_EDGE (e, ei, bb->succs)
 463             {
 464               basic_block dest = e->dest;
 465               if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
 466                   && !single_pred_p (dest))
 467                 {
 468                   last_cmp->missing_uses = true;
 469                   break;
 470                 }
 471             }
 472         }
 473     }
 474
 475   /* If we deleted a compare with a REG_EH_REGION note, we may need to
 476      remove EH edges.  */
 477   if (need_purge)
 478     purge_dead_edges (bb);
 479
 480   return NULL;
 481 }
 482
 483 /* Find all comparisons in the function.  */
 484
 485 static void
 486 find_comparisons (void)
 487 {
 488   calculate_dominance_info (CDI_DOMINATORS);
 489
 490   find_comparison_dom_walker (CDI_DOMINATORS)
 491     .walk (cfun->cfg->x_entry_block_ptr);
 492
 493   clear_aux_for_blocks ();
 494   free_dominance_info (CDI_DOMINATORS);
 495 }
 496
 497 /* Select an alternate CC_MODE for a comparison insn comparing A and B.
 498    Note that inputs are almost certainly different than the IN_A and IN_B
 499    stored in CMP -- we're called while attempting to eliminate the compare
 500    after all.  Return the new FLAGS rtx if successful, else return NULL.
 501    Note that this function may start a change group.  */
 502
 503 static rtx
 504 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
 505                       rtx b ATTRIBUTE_UNUSED)
 506 {
 507   machine_mode sel_mode;
 508   const int n = cmp->n_uses;
 509   rtx flags = NULL;
 510
 511 #ifndef SELECT_CC_MODE
 512   /* Minimize code differences when this target macro is undefined.  */
 513   return NULL;
 514 #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
 515 #endif
 516
 517   /* If we don't have access to all of the uses, we can't validate.  */
 518   if (cmp->missing_uses || n == 0)
 519     return NULL;
 520
 521   /* Find a new mode that works for all of the uses.  Special case the
 522      common case of exactly one use.  */
 523   if (n == 1)
 524     {
 525       sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
 526       if (sel_mode != cmp->orig_mode)
 527         {
 528           flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
 529           validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
 530         }
 531     }
 532   else
 533     {
 534       int i;
 535
 536       sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
 537       for (i = 1; i < n; ++i)
 538         {
 539           machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
 540           if (new_mode != sel_mode)
 541             {
 542               sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
 543               if (sel_mode == VOIDmode)
 544                 return NULL;
 545             }
 546         }
 547
 548       if (sel_mode != cmp->orig_mode)
 549         {
 550           flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
 551           for (i = 0; i < n; ++i)
 552             validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
 553         }
 554     }
 555
 556   return flags;
 557 }
 558
 559 /* Return a register RTX holding the same value at START as REG at END, or
 560    NULL_RTX if there is none.  */
 561
 562 static rtx
 563 equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
 564 {
 565   machine_mode orig_mode = GET_MODE (reg);
 566   rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
 567
 568   for (rtx_insn *insn = PREV_INSN (end);
 569        insn != start;
 570        insn = PREV_INSN (insn))
 571     {
 572       const int abnormal_flags
 573         = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
 574            | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
 575            | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
 576            | DF_REF_PRE_POST_MODIFY);
 577       df_ref def;
 578
 579       /* Note that the BB_HEAD is always either a note or a label, but in
 580          any case it means that REG is defined outside the block.  */
 581       if (insn == bb_head)
 582         return NULL_RTX;
 583       if (NOTE_P (insn) || DEBUG_INSN_P (insn))
 584         continue;
 585
 586       /* Find a possible def of REG in INSN.  */
 587       FOR_EACH_INSN_DEF (def, insn)
 588         if (DF_REF_REGNO (def) == REGNO (reg))
 589           break;
 590
 591       /* No definitions of REG; continue searching.  */
 592       if (def == NULL)
 593         continue;
 594
 595       /* Bail if this is not a totally normal set of REG.  */
 596       if (DF_REF_IS_ARTIFICIAL (def))
 597         return NULL_RTX;
 598       if (DF_REF_FLAGS (def) & abnormal_flags)
 599         return NULL_RTX;
 600
 601       /* We've found an insn between the compare and the clobber that sets
 602          REG.  Given that pass_cprop_hardreg has not yet run, we still find
 603          situations in which we can usefully look through a copy insn.  */
 604       rtx x = single_set (insn);
 605       if (x == NULL_RTX)
 606         return NULL_RTX;
 607       reg = SET_SRC (x);
 608       if (!REG_P (reg))
 609         return NULL_RTX;
 610     }
 611
 612   if (GET_MODE (reg) != orig_mode)
 613     return NULL_RTX;
 614
 615   return reg;
 616 }
 617
 618 /* Return true if it is okay to merge the comparison CMP_INSN with
 619    the instruction ARITH_INSN.  Both instructions are assumed to be in the
 620    same basic block with ARITH_INSN appearing before CMP_INSN.  This checks
 621    that there are no uses or defs of the condition flags or control flow
 622    changes between the two instructions.  */
 623
 624 static bool
 625 can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
 626 {
 627   for (rtx_insn *insn = PREV_INSN (cmp_insn);
 628        insn && insn != arith_insn;
 629        insn = PREV_INSN (insn))
 630     {
 631       if (!NONDEBUG_INSN_P (insn))
 632         continue;
 633       /* Bail if there are jumps or calls in between.  */
 634       if (!NONJUMP_INSN_P (insn))
 635         return false;
 636
 637       /* Bail on old-style asm statements because they lack
 638          data flow information.  */
 639       if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
 640         return false;
 641
 642       df_ref ref;
 643       /* Find a USE of the flags register.  */
 644       FOR_EACH_INSN_USE (ref, insn)
 645         if (DF_REF_REGNO (ref) == targetm.flags_regnum)
 646           return false;
 647
 648       /* Find a DEF of the flags register.  */
 649       FOR_EACH_INSN_DEF (ref, insn)
 650         if (DF_REF_REGNO (ref) == targetm.flags_regnum)
 651           return false;
 652     }
 653   return true;
 654 }
 655
 656 /* Given two SET expressions, SET_A and SET_B determine whether they form
 657    a recognizable pattern when emitted in parallel.  Return that parallel
 658    if so.  Otherwise return NULL.  */
 659
 660 static rtx
 661 try_validate_parallel (rtx set_a, rtx set_b)
 662 {
 663   rtx par = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
 664   rtx_insn *insn = make_insn_raw (par);
 665
 666   if (insn_invalid_p (insn, false))
 667     {
 668       crtl->emit.x_cur_insn_uid--;
 669       return NULL_RTX;
 670     }
 671
 672   SET_PREV_INSN (insn) = NULL_RTX;
 673   SET_NEXT_INSN (insn) = NULL_RTX;
 674   INSN_LOCATION (insn) = 0;
 675   return insn;
 676 }
 677
 678 /* For a comparison instruction described by CMP check if it compares a
 679    register with zero i.e. it is of the form CC := CMP R1, 0.
 680    If it is, find the instruction defining R1 (say I1) and try to create a
 681    PARALLEL consisting of I1 and the comparison, representing a flag-setting
 682    arithmetic instruction.  Example:
 683    I1: R1 := R2 + R3
 684    <instructions that don't read the condition register>
 685    I2: CC := CMP R1 0
 686    I2 can be merged with I1 into:
 687    I1: { CC := CMP (R2 + R3) 0 ; R1 := R2 + R3 }
 688    This catches cases where R1 is used between I1 and I2 and therefore
 689    combine and other RTL optimisations will not try to propagate it into
 690    I2.  Return true if we succeeded in merging CMP.  */
 691
 692 static bool
 693 try_merge_compare (struct comparison *cmp)
 694 {
 695   rtx_insn *cmp_insn = cmp->insn;
 696
 697   if (cmp->in_b != const0_rtx || cmp->in_a_setter == NULL)
 698     return false;
 699   rtx in_a = cmp->in_a;
 700   df_ref use;
 701
 702   FOR_EACH_INSN_USE (use, cmp_insn)
 703     if (DF_REF_REGNO (use) == REGNO (in_a))
 704       break;
 705   if (!use)
 706     return false;
 707
 708   rtx_insn *def_insn = cmp->in_a_setter;
 709   rtx set = single_set (def_insn);
 710   if (!set)
 711     return false;
 712
 713   if (!can_merge_compare_into_arith (cmp_insn, def_insn))
 714     return false;
 715
 716   rtx src = SET_SRC (set);
 717
 718   /* If the source uses addressing modes with side effects, we can't
 719      do the merge because we'd end up with a PARALLEL that has two
 720      instances of that side effect in it.  */
 721   if (side_effects_p (src))
 722     return false;
 723
 724   rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
 725   if (!flags)
 726     {
 727     /* We may already have a change group going through maybe_select_cc_mode.
 728        Discard it properly.  */
 729       cancel_changes (0);
 730       return false;
 731     }
 732
 733   rtx flag_set
 734     = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
 735                                            copy_rtx (src),
 736                                            CONST0_RTX (GET_MODE (src))));
 737   rtx arith_set = copy_rtx (PATTERN (def_insn));
 738   rtx par = try_validate_parallel (flag_set, arith_set);
 739   if (!par)
 740     {
 741       /* We may already have a change group going through maybe_select_cc_mode.
 742          Discard it properly.  */
 743       cancel_changes (0);
 744       return false;
 745     }
 746   if (!apply_change_group ())
 747     return false;
 748   emit_insn_after (par, def_insn);
 749   delete_insn (def_insn);
 750   delete_insn (cmp->insn);
 751   return true;
 752 }
 753
 754 /* Attempt to replace a comparison with a prior arithmetic insn that can
 755    compute the same flags value as the comparison itself.  Return true if
 756    successful, having made all rtl modifications necessary.  */
 757
 758 static bool
 759 try_eliminate_compare (struct comparison *cmp)
 760 {
 761   rtx flags, in_a, in_b, cmp_a, cmp_b;
 762
 763   if (try_merge_compare (cmp))
 764     return true;
 765
 766   /* We must have found an interesting "clobber" preceding the compare.  */
 767   if (cmp->prev_clobber == NULL)
 768     return false;
 769
 770   /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
 771      Given that this target requires this pass, we can assume that most
 772      insns do clobber the flags, and so the distance between the compare
 773      and the clobber is likely to be small.  */
 774   /* ??? This is one point at which one could argue that DF_REF_CHAIN would
 775      be useful, but it is thought to be too heavy-weight a solution here.  */
 776   in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
 777   if (!in_a)
 778     return false;
 779
 780   /* Likewise for IN_B if need be.  */
 781   if (CONSTANT_P (cmp->in_b))
 782     in_b = cmp->in_b;
 783   else if (REG_P (cmp->in_b))
 784     {
 785       in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
 786       if (!in_b)
 787         return false;
 788     }
 789   else if (GET_CODE (cmp->in_b) == UNSPEC)
 790     {
 791       const int len = XVECLEN (cmp->in_b, 0);
 792       rtvec v = rtvec_alloc (len);
 793       for (int i = 0; i < len; i++)
 794         {
 795           rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
 796                                            cmp->insn, cmp->prev_clobber);
 797           if (!r)
 798             return false;
 799           RTVEC_ELT (v, i) = r;
 800         }
 801       in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
 802     }
 803   else
 804     gcc_unreachable ();
 805
 806   /* We've reached PREV_CLOBBER without finding a modification of IN_A.
 807      Validate that PREV_CLOBBER itself does in fact refer to IN_A.  Do
 808      recall that we've already validated the shape of PREV_CLOBBER.  */
 809   rtx_insn *insn = cmp->prev_clobber;
 810
 811   rtx x = XVECEXP (PATTERN (insn), 0, 0);
 812   if (rtx_equal_p (SET_DEST (x), in_a))
 813     cmp_a = SET_SRC (x);
 814
 815   /* Also check operations with implicit extensions, e.g.:
 816      [(set (reg:DI)
 817            (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
 818       (set (reg:CCZ flags)
 819            (compare:CCZ (plus:SI (reg:SI) (reg:SI))
 820                         (const_int 0)))] */
 821   else if (REG_P (SET_DEST (x))
 822            && REG_P (in_a)
 823            && REGNO (SET_DEST (x)) == REGNO (in_a)
 824            && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
 825                || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
 826            && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
 827     cmp_a = XEXP (SET_SRC (x), 0);
 828
 829   /* Also check fully redundant comparisons, e.g.:
 830      [(set (reg:SI)
 831            (minus:SI (reg:SI) (reg:SI))))
 832       (set (reg:CC flags)
 833            (compare:CC (reg:SI) (reg:SI)))] */
 834   else if (REG_P (in_b)
 835            && GET_CODE (SET_SRC (x)) == MINUS
 836            && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
 837            && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
 838     cmp_a = in_a;
 839
 840   else
 841     return false;
 842
 843   /* If the source uses addressing modes with side effects, we can't
 844      do the merge because we'd end up with a PARALLEL that has two
 845      instances of that side effect in it.  */
 846   if (side_effects_p (cmp_a))
 847     return false;
 848
 849   if (in_a == in_b)
 850     cmp_b = cmp_a;
 851   else if (rtx_equal_p (SET_DEST (x), in_b))
 852     cmp_b = SET_SRC (x);
 853   else
 854     cmp_b = in_b;
 855   if (side_effects_p (cmp_b))
 856     return false;
 857
 858   /* Determine if we ought to use a different CC_MODE here.  */
 859   flags = maybe_select_cc_mode (cmp, cmp_a, cmp_b);
 860   if (flags == NULL)
 861     flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
 862
 863   /* Generate a new comparison for installation in the setter.  */
 864   rtx y = cmp->not_in_a
 865           ? gen_rtx_NOT (GET_MODE (cmp_a), copy_rtx (cmp_a))
 866           : copy_rtx (cmp_a);
 867   y = gen_rtx_COMPARE (GET_MODE (flags), y, copy_rtx (cmp_b));
 868   y = gen_rtx_SET (flags, y);
 869
 870   /* Canonicalize instruction to:
 871      [(set (reg:CCM) (compare:CCM (operation) (immediate)))
 872       (set (reg) (operation)]  */
 873
 874   rtvec v = rtvec_alloc (2);
 875   RTVEC_ELT (v, 0) = y;
 876   RTVEC_ELT (v, 1) = x;
 877
 878   rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
 879
 880   /* Succeed if the new instruction is valid.  Note that we may have started
 881      a change group within maybe_select_cc_mode, therefore we must continue. */
 882   validate_change (insn, &PATTERN (insn), pat, true);
 883
 884   if (!apply_change_group ())
 885     return false;
 886
 887   /* Success.  Delete the compare insn...  */
 888   delete_insn (cmp->insn);
 889
 890   /* ... and any notes that are now invalid due to multiple sets.  */
 891   x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
 892   if (x)
 893     remove_note (insn, x);
 894   x = find_reg_note (insn, REG_EQUAL, NULL);
 895   if (x)
 896     remove_note (insn, x);
 897   x = find_reg_note (insn, REG_EQUIV, NULL);
 898   if (x)
 899     remove_note (insn, x);
 900
 901   return true;
 902 }
 903
 904 /* Main entry point to the pass.  */
 905
 906 static unsigned int
 907 execute_compare_elim_after_reload (void)
 908 {
 909   df_set_flags (DF_LR_RUN_DCE);
 910   df_analyze ();
 911
 912   gcc_checking_assert (!all_compares.exists ());
 913
 914   /* Locate all comparisons and their uses, and eliminate duplicates.  */
 915   find_comparisons ();
 916   if (all_compares.exists ())
 917     {
 918       struct comparison *cmp;
 919       size_t i;
 920
 921       /* Eliminate comparisons that are redundant with flags computation.  */
 922       FOR_EACH_VEC_ELT (all_compares, i, cmp)
 923         {
 924           try_eliminate_compare (cmp);
 925           XDELETE (cmp);
 926         }
 927
 928       all_compares.release ();
 929     }
 930
 931   return 0;
 932 }
 933
 934 namespace {
 935
 936 const pass_data pass_data_compare_elim_after_reload =
 937 {
 938   RTL_PASS, /* type */
 939   "cmpelim", /* name */
 940   OPTGROUP_NONE, /* optinfo_flags */
 941   TV_NONE, /* tv_id */
 942   0, /* properties_required */
 943   0, /* properties_provided */
 944   0, /* properties_destroyed */
 945   0, /* todo_flags_start */
 946   ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
 947 };
 948
 949 class pass_compare_elim_after_reload : public rtl_opt_pass
 950 {
 951 public:
 952   pass_compare_elim_after_reload (gcc::context *ctxt)
 953     : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
 954   {}
 955
 956   /* opt_pass methods: */
 957   bool gate (function *) final override
 958     {
 959       /* Setting this target hook value is how a backend indicates the need.  */
 960       if (targetm.flags_regnum == INVALID_REGNUM)
 961         return false;
 962       return flag_compare_elim_after_reload;
 963     }
 964
 965   unsigned int execute (function *) final override
 966     {
 967       return execute_compare_elim_after_reload ();
 968     }
 969
 970 }; // class pass_compare_elim_after_reload
 971
 972 } // anon namespace
 973
 974 rtl_opt_pass *
 975 make_pass_compare_elim_after_reload (gcc::context *ctxt)
 976 {
 977   return new pass_compare_elim_after_reload (ctxt);
 978 }