gcc/compare-elim.c

   1 /* Post-reload compare elimination.
   2    Copyright (C) 2010, 2011
   3    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 under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 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 /* There is a set of targets whose general-purpose move or addition
  22    instructions clobber the flags.  These targets cannot split their
  23    CBRANCH/CSTORE etc patterns before reload is complete, lest reload
  24    itself insert these instructions in between the flags setter and user.
  25    Because these targets cannot split the compare from the use, they
  26    cannot make use of the comparison elimination offered by the combine pass.
  27
  28    This is a small pass intended to provide comparison elimination similar to
  29    what is available via NOTICE_UPDATE_CC for cc0 targets.  This should help
  30    encourage cc0 targets to convert to an explicit post-reload representation
  31    of the flags.
  32
  33    This pass assumes:
  34
  35    (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.
  36
  37    (1) All comparison patterns are represented as
  38
  39         [(set (reg:CC) (compare:CC (reg) (immediate)))]
  40
  41    (2) All insn patterns that modify the flags are represented as
  42
  43         [(set (reg) (operation)
  44          (clobber (reg:CC))]
  45
  46    (3) If an insn of form (2) can usefully set the flags, there is
  47        another pattern of the form
  48
  49         [(set (reg) (operation)
  50          (set (reg:CCM) (compare:CCM (operation) (immediate)))]
  51
  52        The mode CCM will be chosen as if by SELECT_CC_MODE.
  53
  54    Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
  55    This could be handled as a future enhancement.
  56 */
  57
  58 #include "config.h"
  59 #include "system.h"
  60 #include "coretypes.h"
  61 #include "tm.h"
  62 #include "rtl.h"
  63 #include "tm_p.h"
  64 #include "insn-config.h"
  65 #include "recog.h"
  66 #include "flags.h"
  67 #include "basic-block.h"
  68 #include "tree-pass.h"
  69 #include "target.h"
  70 #include "df.h"
  71 #include "domwalk.h"
  72
  73 \f
  74 /* These structures describe a comparison and how it is used.  */
  75
  76 /* The choice of maximum 3 uses comes from wanting to eliminate the two
  77    duplicate compares from a three-way branch on the sign of a value.
  78    This is also sufficient to eliminate the duplicate compare against the
  79    high-part of a double-word comparison.  */
  80 #define MAX_CMP_USE 3
  81
  82 struct comparison_use
  83 {
  84   /* The instruction in which the result of the compare is used.  */
  85   rtx insn;
  86   /* The location of the flags register within the use.  */
  87   rtx *loc;
  88   /* The comparison code applied against the flags register.  */
  89   enum rtx_code code;
  90 };
  91
  92 struct comparison
  93 {
  94   /* The comparison instruction.  */
  95   rtx insn;
  96
  97   /* The insn prior to the comparison insn that clobbers the flags.  */
  98   rtx prev_clobber;
  99
 100   /* The two values being compared.  These will be either REGs or
 101      constants.  */
 102   rtx in_a, in_b;
 103
 104   /* Information about how this comparison is used.  */
 105   struct comparison_use uses[MAX_CMP_USE];
 106
 107   /* The original CC_MODE for this comparison.  */
 108   enum machine_mode orig_mode;
 109
 110   /* The number of uses identified for this comparison.  */
 111   unsigned short n_uses;
 112
 113   /* True if not all uses of this comparison have been identified.
 114      This can happen either for overflowing the array above, or if
 115      the flags register is used in some unusual context.  */
 116   bool missing_uses;
 117
 118   /* True if its inputs are still valid at the end of the block.  */
 119   bool inputs_valid;
 120 };
 121
 122 typedef struct comparison *comparison_struct_p;
 123 DEF_VEC_P(comparison_struct_p);
 124 DEF_VEC_ALLOC_P(comparison_struct_p, heap);
 125
 126 static VEC(comparison_struct_p, heap) *all_compares;
 127
 128 /* Look for a "conforming" comparison, as defined above.  If valid, return
 129    the rtx for the COMPARE itself.  */
 130
 131 static rtx
 132 conforming_compare (rtx insn)
 133 {
 134   rtx set, src, dest;
 135
 136   set = single_set (insn);
 137   if (set == NULL)
 138     return NULL;
 139
 140   src = SET_SRC (set);
 141   if (GET_CODE (src) != COMPARE)
 142     return NULL;
 143
 144   dest = SET_DEST (set);
 145   if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
 146     return NULL;
 147
 148   if (REG_P (XEXP (src, 0))
 149       && REG_P (XEXP (src, 0))
 150       && (REG_P (XEXP (src, 1)) || CONSTANT_P (XEXP (src, 1))))
 151     return src;
 152
 153   return NULL;
 154 }
 155
 156 /* Look for a pattern of the "correct" form for an insn with a flags clobber
 157    for which we may be able to eliminate a compare later.  We're not looking
 158    to validate any inputs at this time, merely see that the basic shape is
 159    correct.  The term "arithmetic" may be somewhat misleading...  */
 160
 161 static bool
 162 arithmetic_flags_clobber_p (rtx insn)
 163 {
 164   rtx pat, x;
 165
 166   if (!NONJUMP_INSN_P (insn))
 167     return false;
 168   pat = PATTERN (insn);
 169   if (extract_asm_operands (pat))
 170     return false;
 171
 172   if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
 173     {
 174       x = XVECEXP (pat, 0, 0);
 175       if (GET_CODE (x) != SET)
 176         return false;
 177       x = SET_DEST (x);
 178       if (!REG_P (x))
 179         return false;
 180
 181       x = XVECEXP (pat, 0, 1);
 182       if (GET_CODE (x) == CLOBBER)
 183         {
 184           x = XEXP (x, 0);
 185           if (REG_P (x) && REGNO (x) == targetm.flags_regnum)
 186             return true;
 187         }
 188     }
 189
 190   return false;
 191 }
 192
 193 /* Look for uses of FLAGS in INSN.  If we find one we can analyze, record
 194    it in CMP; otherwise indicate that we've missed a use.  */
 195
 196 static void
 197 find_flags_uses_in_insn (struct comparison *cmp, rtx insn)
 198 {
 199   df_ref *use_rec, use;
 200
 201   /* If we've already lost track of uses, don't bother collecting more.  */
 202   if (cmp->missing_uses)
 203     return;
 204
 205   /* Find a USE of the flags register.  */
 206   for (use_rec = DF_INSN_USES (insn); (use = *use_rec) != NULL; use_rec++)
 207     if (DF_REF_REGNO (use) == targetm.flags_regnum)
 208       {
 209         rtx x, *loc;
 210
 211         /* If this is an unusual use, quit.  */
 212         if (DF_REF_TYPE (use) != DF_REF_REG_USE)
 213           goto fail;
 214
 215         /* If we've run out of slots to record uses, quit.  */
 216         if (cmp->n_uses == MAX_CMP_USE)
 217           goto fail;
 218
 219         /* Unfortunately the location of the flags register, while present
 220            in the reference structure, doesn't help.  We need to find the
 221            comparison code that is outer to the actual flags use.  */
 222         loc = DF_REF_LOC (use);
 223         x = PATTERN (insn);
 224         if (GET_CODE (x) == PARALLEL)
 225           x = XVECEXP (x, 0, 0);
 226         x = SET_SRC (x);
 227         if (GET_CODE (x) == IF_THEN_ELSE)
 228           x = XEXP (x, 0);
 229         if (COMPARISON_P (x)
 230             && loc == &XEXP (x, 0)
 231             && XEXP (x, 1) == const0_rtx)
 232           {
 233             /* We've found a use of the flags that we understand.  */
 234             struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
 235             cuse->insn = insn;
 236             cuse->loc = loc;
 237             cuse->code = GET_CODE (x);
 238           }
 239         else
 240           goto fail;
 241       }
 242   return;
 243
 244  fail:
 245   /* We failed to recognize this use of the flags register.  */
 246   cmp->missing_uses = true;
 247 }
 248
 249 /* Identify comparison instructions within BB.  If the flags from the last
 250    compare in the BB is live at the end of the block, install the compare
 251    in BB->AUX.  Called via walk_dominators_tree.  */
 252
 253 static void
 254 find_comparisons_in_bb (struct dom_walk_data *data ATTRIBUTE_UNUSED,
 255                         basic_block bb)
 256 {
 257   struct comparison *last_cmp;
 258   rtx insn, next, last_clobber;
 259   bool last_cmp_valid;
 260   bitmap killed;
 261
 262   killed = BITMAP_ALLOC (NULL);
 263
 264   /* The last comparison that was made.  Will be reset to NULL
 265      once the flags are clobbered.  */
 266   last_cmp = NULL;
 267
 268   /* True iff the last comparison has not been clobbered, nor
 269      have its inputs.  Used to eliminate duplicate compares.  */
 270   last_cmp_valid = false;
 271
 272   /* The last insn that clobbered the flags, if that insn is of
 273      a form that may be valid for eliminating a following compare.
 274      To be reset to NULL once the flags are set otherwise.  */
 275   last_clobber = NULL;
 276
 277   /* Propagate the last live comparison throughout the extended basic block. */
 278   if (single_pred_p (bb))
 279     {
 280       last_cmp = (struct comparison *) single_pred (bb)->aux;
 281       if (last_cmp)
 282         last_cmp_valid = last_cmp->inputs_valid;
 283     }
 284
 285   for (insn = BB_HEAD (bb); insn; insn = next)
 286     {
 287       rtx src;
 288
 289       next = (insn == BB_END (bb) ? NULL_RTX : NEXT_INSN (insn));
 290       if (!NONDEBUG_INSN_P (insn))
 291         continue;
 292
 293       /* Compute the set of registers modified by this instruction.  */
 294       bitmap_clear (killed);
 295       df_simulate_find_defs (insn, killed);
 296
 297       src = conforming_compare (insn);
 298       if (src)
 299         {
 300           enum machine_mode src_mode = GET_MODE (src);
 301
 302           /* Eliminate a compare that's redundant with the previous.  */
 303           if (last_cmp_valid
 304               && src_mode == last_cmp->orig_mode
 305               && rtx_equal_p (last_cmp->in_a, XEXP (src, 0))
 306               && rtx_equal_p (last_cmp->in_b, XEXP (src, 1)))
 307             {
 308               delete_insn (insn);
 309               continue;
 310             }
 311
 312           last_cmp = XCNEW (struct comparison);
 313           last_cmp->insn = insn;
 314           last_cmp->prev_clobber = last_clobber;
 315           last_cmp->in_a = XEXP (src, 0);
 316           last_cmp->in_b = XEXP (src, 1);
 317           last_cmp->orig_mode = src_mode;
 318           VEC_safe_push (comparison_struct_p, heap, all_compares, last_cmp);
 319
 320           /* It's unusual, but be prepared for comparison patterns that
 321              also clobber an input, or perhaps a scratch.  */
 322           last_clobber = NULL;
 323           last_cmp_valid = true;
 324         }
 325
 326       /* Notice if this instruction kills the flags register.  */
 327       else if (bitmap_bit_p (killed, targetm.flags_regnum))
 328         {
 329           /* See if this insn could be the "clobber" that eliminates
 330              a future comparison.   */
 331           last_clobber = (arithmetic_flags_clobber_p (insn) ? insn : NULL);
 332
 333           /* In either case, the previous compare is no longer valid.  */
 334           last_cmp = NULL;
 335           last_cmp_valid = false;
 336           continue;
 337         }
 338
 339       /* Notice if this instruction uses the flags register.  */
 340       else if (last_cmp)
 341         find_flags_uses_in_insn (last_cmp, insn);
 342
 343       /* Notice if any of the inputs to the comparison have changed.  */
 344       if (last_cmp_valid
 345           && (bitmap_bit_p (killed, REGNO (last_cmp->in_a))
 346               || (REG_P (last_cmp->in_b)
 347                   && bitmap_bit_p (killed, REGNO (last_cmp->in_b)))))
 348         last_cmp_valid = false;
 349     }
 350
 351   BITMAP_FREE (killed);
 352
 353   /* Remember the live comparison for subsequent members of
 354      the extended basic block.  */
 355   if (last_cmp)
 356     {
 357       bb->aux = last_cmp;
 358       last_cmp->inputs_valid = last_cmp_valid;
 359
 360       /* Look to see if the flags register is live outgoing here, and
 361          incoming to any successor not part of the extended basic block.  */
 362       if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
 363         {
 364           edge e;
 365           edge_iterator ei;
 366
 367           FOR_EACH_EDGE (e, ei, bb->succs)
 368             {
 369               basic_block dest = e->dest;
 370               if (bitmap_bit_p (df_get_live_in (bb),
 371                                 targetm.flags_regnum)
 372                   && !single_pred_p (dest))
 373                 {
 374                   last_cmp->missing_uses = true;
 375                   break;
 376                 }
 377             }
 378         }
 379     }
 380 }
 381
 382 /* Find all comparisons in the function.  */
 383
 384 static void
 385 find_comparisons (void)
 386 {
 387   struct dom_walk_data data;
 388
 389   memset (&data, 0, sizeof(data));
 390   data.dom_direction = CDI_DOMINATORS;
 391   data.before_dom_children = find_comparisons_in_bb;
 392
 393   calculate_dominance_info (CDI_DOMINATORS);
 394
 395   init_walk_dominator_tree (&data);
 396   walk_dominator_tree (&data, ENTRY_BLOCK_PTR);
 397   fini_walk_dominator_tree (&data);
 398
 399   clear_aux_for_blocks ();
 400   free_dominance_info (CDI_DOMINATORS);
 401 }
 402
 403 /* Select an alternate CC_MODE for a comparison insn comparing A and B.
 404    Note that inputs are almost certainly different than the IN_A and IN_B
 405    stored in CMP -- we're called while attempting to eliminate the compare
 406    after all.  Return the new FLAGS rtx if successful, else return NULL.
 407    Note that this function may start a change group.  */
 408
 409 static rtx
 410 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
 411                       rtx b ATTRIBUTE_UNUSED)
 412 {
 413   enum machine_mode sel_mode;
 414   const int n = cmp->n_uses;
 415   rtx flags = NULL;
 416
 417 #ifndef SELECT_CC_MODE
 418   /* Minimize code differences when this target macro is undefined.  */
 419   return NULL;
 420 #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
 421 #endif
 422
 423   /* If we don't have access to all of the uses, we can't validate.  */
 424   if (cmp->missing_uses || n == 0)
 425     return NULL;
 426
 427   /* Find a new mode that works for all of the uses.  Special case the
 428      common case of exactly one use.  */
 429   if (n == 1)
 430     {
 431       sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
 432       if (sel_mode != cmp->orig_mode)
 433         {
 434           flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
 435           validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
 436         }
 437     }
 438   else
 439     {
 440       int i;
 441
 442       sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
 443       for (i = 1; i < n; ++i)
 444         {
 445           enum machine_mode new_mode;
 446           new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
 447           if (new_mode != sel_mode)
 448             {
 449               sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
 450               if (sel_mode == VOIDmode)
 451                 return NULL;
 452             }
 453         }
 454
 455       if (sel_mode != cmp->orig_mode)
 456         {
 457           flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
 458           for (i = 0; i < n; ++i)
 459             validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
 460         }
 461     }
 462
 463   return flags;
 464 }
 465
 466 /* Attempt to replace a comparison with a prior arithmetic insn that can
 467    compute the same flags value as the comparison itself.  Return true if
 468    successful, having made all rtl modifications necessary.  */
 469
 470 static bool
 471 try_eliminate_compare (struct comparison *cmp)
 472 {
 473   rtx x, insn, bb_head, flags, in_a, cmp_src;
 474
 475   /* We must have found an interesting "clobber" preceeding the compare.  */
 476   if (cmp->prev_clobber == NULL)
 477     return false;
 478
 479   /* ??? For the moment we don't handle comparisons for which IN_B
 480      is a register.  We accepted these during initial comparison
 481      recognition in order to eliminate duplicate compares.
 482      An improvement here would be to handle x = a - b; if (a cmp b).  */
 483   if (!CONSTANT_P (cmp->in_b))
 484     return false;
 485
 486   /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
 487      Given that this target requires this pass, we can assume that most
 488      insns do clobber the flags, and so the distance between the compare
 489      and the clobber is likely to be small.  */
 490   /* ??? This is one point at which one could argue that DF_REF_CHAIN would
 491      be useful, but it is thought to be too heavy-weight a solution here.  */
 492
 493   in_a = cmp->in_a;
 494   insn = cmp->insn;
 495   bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
 496   for (insn = PREV_INSN (insn);
 497        insn != cmp->prev_clobber;
 498        insn = PREV_INSN (insn))
 499     {
 500       const int abnormal_flags
 501         = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
 502            | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
 503            | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
 504            | DF_REF_PRE_POST_MODIFY);
 505       df_ref *def_rec, def;
 506
 507       /* Note that the BB_HEAD is always either a note or a label, but in
 508          any case it means that IN_A is defined outside the block.  */
 509       if (insn == bb_head)
 510         return false;
 511       if (NOTE_P (insn) || DEBUG_INSN_P (insn))
 512         continue;
 513
 514       /* Find a possible def of IN_A in INSN.  */
 515       for (def_rec = DF_INSN_DEFS (insn); (def = *def_rec) != NULL; def_rec++)
 516         if (DF_REF_REGNO (def) == REGNO (in_a))
 517           break;
 518
 519       /* No definitions of IN_A; continue searching.  */
 520       if (def == NULL)
 521         continue;
 522
 523       /* Bail if this is not a totally normal set of IN_A.  */
 524       if (DF_REF_IS_ARTIFICIAL (def))
 525         return false;
 526       if (DF_REF_FLAGS (def) & abnormal_flags)
 527         return false;
 528
 529       /* We've found an insn between the compare and the clobber that sets
 530          IN_A.  Given that pass_cprop_hardreg has not yet run, we still find
 531          situations in which we can usefully look through a copy insn.  */
 532       x = single_set (insn);
 533       if (x == NULL)
 534         return false;
 535       in_a = SET_SRC (x);
 536       if (!REG_P (in_a))
 537         return false;
 538     }
 539
 540   /* We've reached PREV_CLOBBER without finding a modification of IN_A.
 541      Validate that PREV_CLOBBER itself does in fact refer to IN_A.  Do
 542      recall that we've already validated the shape of PREV_CLOBBER.  */
 543   x = XVECEXP (PATTERN (insn), 0, 0);
 544   if (!rtx_equal_p (SET_DEST (x), in_a))
 545     return false;
 546   cmp_src = SET_SRC (x);
 547
 548   /* Determine if we ought to use a different CC_MODE here.  */
 549   flags = maybe_select_cc_mode (cmp, cmp_src, cmp->in_b);
 550   if (flags == NULL)
 551     flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
 552
 553   /* Generate a new comparison for installation in the setter.  */
 554   x = copy_rtx (cmp_src);
 555   x = gen_rtx_COMPARE (GET_MODE (flags), x, cmp->in_b);
 556   x = gen_rtx_SET (VOIDmode, flags, x);
 557
 558   /* Succeed if the new instruction is valid.  Note that we may have started
 559      a change group within maybe_select_cc_mode, therefore we must continue. */
 560   validate_change (insn, &XVECEXP (PATTERN (insn), 0, 1), x, true);
 561   if (!apply_change_group ())
 562     return false;
 563
 564   /* Success.  Delete the compare insn...  */
 565   delete_insn (cmp->insn);
 566
 567   /* ... and any notes that are now invalid due to multiple sets.  */
 568   x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
 569   if (x)
 570     remove_note (insn, x);
 571   x = find_reg_note (insn, REG_EQUAL, NULL);
 572   if (x)
 573     remove_note (insn, x);
 574   x = find_reg_note (insn, REG_EQUIV, NULL);
 575   if (x)
 576     remove_note (insn, x);
 577
 578   return true;
 579 }
 580
 581 /* Main entry point to the pass.  */
 582
 583 static unsigned int
 584 execute_compare_elim_after_reload (void)
 585 {
 586   df_analyze ();
 587
 588   gcc_checking_assert (all_compares == NULL);
 589
 590   /* Locate all comparisons and their uses, and eliminate duplicates.  */
 591   find_comparisons ();
 592   if (all_compares)
 593     {
 594       struct comparison *cmp;
 595       size_t i;
 596
 597       /* Eliminate comparisons that are redundant with flags computation.  */
 598       FOR_EACH_VEC_ELT (comparison_struct_p, all_compares, i, cmp)
 599         {
 600           try_eliminate_compare (cmp);
 601           XDELETE (cmp);
 602         }
 603
 604       VEC_free (comparison_struct_p, heap, all_compares);
 605       all_compares = NULL;
 606     }
 607
 608   return 0;
 609 }
 610
 611 static bool
 612 gate_compare_elim_after_reload (void)
 613 {
 614   /* Setting this target hook value is how a backend indicates the need.  */
 615   if (targetm.flags_regnum == INVALID_REGNUM)
 616     return false;
 617   return flag_compare_elim_after_reload;
 618 }
 619
 620 struct rtl_opt_pass pass_compare_elim_after_reload =
 621 {
 622  {
 623   RTL_PASS,
 624   "cmpelim",                            /* name */
 625   gate_compare_elim_after_reload,       /* gate */
 626   execute_compare_elim_after_reload,    /* execute */
 627   NULL,                                 /* sub */
 628   NULL,                                 /* next */
 629   0,                                    /* static_pass_number */
 630   TV_NONE,                              /* tv_id */
 631   0,                                    /* properties_required */
 632   0,                                    /* properties_provided */
 633   0,                                    /* properties_destroyed */
 634   0,                                    /* todo_flags_start */
 635   TODO_df_finish
 636   | TODO_df_verify
 637   | TODO_verify_rtl_sharing
 638   | TODO_ggc_collect                    /* todo_flags_finish */
 639  }
 640 };