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           /* Eliminate a compare that's redundant with the previous.  */
 301           if (last_cmp_valid
 302               && rtx_equal_p (last_cmp->in_a, XEXP (src, 0))
 303               && rtx_equal_p (last_cmp->in_b, XEXP (src, 1)))
 304             {
 305               delete_insn (insn);
 306               continue;
 307             }
 308
 309           last_cmp = XCNEW (struct comparison);
 310           last_cmp->insn = insn;
 311           last_cmp->prev_clobber = last_clobber;
 312           last_cmp->in_a = XEXP (src, 0);
 313           last_cmp->in_b = XEXP (src, 1);
 314           last_cmp->orig_mode = GET_MODE (SET_DEST (single_set (insn)));
 315           VEC_safe_push (comparison_struct_p, heap, all_compares, last_cmp);
 316
 317           /* It's unusual, but be prepared for comparison patterns that
 318              also clobber an input, or perhaps a scratch.  */
 319           last_clobber = NULL;
 320           last_cmp_valid = true;
 321         }
 322
 323       /* Notice if this instruction kills the flags register.  */
 324       else if (bitmap_bit_p (killed, targetm.flags_regnum))
 325         {
 326           /* See if this insn could be the "clobber" that eliminates
 327              a future comparison.   */
 328           last_clobber = (arithmetic_flags_clobber_p (insn) ? insn : NULL);
 329
 330           /* In either case, the previous compare is no longer valid.  */
 331           last_cmp = NULL;
 332           last_cmp_valid = false;
 333           continue;
 334         }
 335
 336       /* Notice if this instruction uses the flags register.  */
 337       else if (last_cmp)
 338         find_flags_uses_in_insn (last_cmp, insn);
 339
 340       /* Notice if any of the inputs to the comparison have changed.  */
 341       if (last_cmp_valid
 342           && (bitmap_bit_p (killed, REGNO (last_cmp->in_a))
 343               || (REG_P (last_cmp->in_b)
 344                   && bitmap_bit_p (killed, REGNO (last_cmp->in_b)))))
 345         last_cmp_valid = false;
 346     }
 347
 348   BITMAP_FREE (killed);
 349
 350   /* Remember the live comparison for subsequent members of
 351      the extended basic block.  */
 352   if (last_cmp)
 353     {
 354       bb->aux = last_cmp;
 355       last_cmp->inputs_valid = last_cmp_valid;
 356
 357       /* Look to see if the flags register is live outgoing here, and
 358          incoming to any successor not part of the extended basic block.  */
 359       if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
 360         {
 361           edge e;
 362           edge_iterator ei;
 363
 364           FOR_EACH_EDGE (e, ei, bb->succs)
 365             {
 366               basic_block dest = e->dest;
 367               if (bitmap_bit_p (df_get_live_in (bb),
 368                                 targetm.flags_regnum)
 369                   && !single_pred_p (dest))
 370                 {
 371                   last_cmp->missing_uses = true;
 372                   break;
 373                 }
 374             }
 375         }
 376     }
 377 }
 378
 379 /* Find all comparisons in the function.  */
 380
 381 static void
 382 find_comparisons (void)
 383 {
 384   struct dom_walk_data data;
 385
 386   memset (&data, 0, sizeof(data));
 387   data.dom_direction = CDI_DOMINATORS;
 388   data.before_dom_children = find_comparisons_in_bb;
 389
 390   calculate_dominance_info (CDI_DOMINATORS);
 391
 392   init_walk_dominator_tree (&data);
 393   walk_dominator_tree (&data, ENTRY_BLOCK_PTR);
 394   fini_walk_dominator_tree (&data);
 395
 396   clear_aux_for_blocks ();
 397   free_dominance_info (CDI_DOMINATORS);
 398 }
 399
 400 /* Select an alternate CC_MODE for a comparison insn comparing A and B.
 401    Note that inputs are almost certainly different than the IN_A and IN_B
 402    stored in CMP -- we're called while attempting to eliminate the compare
 403    after all.  Return the new FLAGS rtx if successful, else return NULL.
 404    Note that this function may start a change group.  */
 405
 406 static rtx
 407 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
 408                       rtx b ATTRIBUTE_UNUSED)
 409 {
 410   enum machine_mode sel_mode;
 411   const int n = cmp->n_uses;
 412   rtx flags = NULL;
 413
 414 #ifndef SELECT_CC_MODE
 415   /* Minimize code differences when this target macro is undefined.  */
 416   return NULL;
 417 #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
 418 #endif
 419
 420   /* If we don't have access to all of the uses, we can't validate.  */
 421   if (cmp->missing_uses || n == 0)
 422     return NULL;
 423
 424   /* Find a new mode that works for all of the uses.  Special case the
 425      common case of exactly one use.  */
 426   if (n == 1)
 427     {
 428       sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
 429       if (sel_mode != cmp->orig_mode)
 430         {
 431           flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
 432           validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
 433         }
 434     }
 435   else
 436     {
 437       int i;
 438
 439       sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
 440       for (i = 1; i < n; ++i)
 441         {
 442           enum machine_mode new_mode;
 443           new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
 444           if (new_mode != sel_mode)
 445             {
 446               sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
 447               if (sel_mode == VOIDmode)
 448                 return NULL;
 449             }
 450         }
 451
 452       if (sel_mode != cmp->orig_mode)
 453         {
 454           flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
 455           for (i = 0; i < n; ++i)
 456             validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
 457         }
 458     }
 459
 460   return flags;
 461 }
 462
 463 /* Attempt to replace a comparison with a prior arithmetic insn that can
 464    compute the same flags value as the comparison itself.  Return true if
 465    successful, having made all rtl modifications necessary.  */
 466
 467 static bool
 468 try_eliminate_compare (struct comparison *cmp)
 469 {
 470   rtx x, insn, bb_head, flags, in_a, cmp_src;
 471
 472   /* We must have found an interesting "clobber" preceeding the compare.  */
 473   if (cmp->prev_clobber == NULL)
 474     return false;
 475
 476   /* ??? For the moment we don't handle comparisons for which IN_B
 477      is a register.  We accepted these during initial comparison
 478      recognition in order to eliminate duplicate compares.
 479      An improvement here would be to handle x = a - b; if (a cmp b).  */
 480   if (!CONSTANT_P (cmp->in_b))
 481     return false;
 482
 483   /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
 484      Given that this target requires this pass, we can assume that most
 485      insns do clobber the flags, and so the distance between the compare
 486      and the clobber is likely to be small.  */
 487   /* ??? This is one point at which one could argue that DF_REF_CHAIN would
 488      be useful, but it is thought to be too heavy-weight a solution here.  */
 489
 490   in_a = cmp->in_a;
 491   insn = cmp->insn;
 492   bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
 493   for (insn = PREV_INSN (insn);
 494        insn != cmp->prev_clobber;
 495        insn = PREV_INSN (insn))
 496     {
 497       const int abnormal_flags
 498         = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
 499            | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
 500            | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
 501            | DF_REF_PRE_POST_MODIFY);
 502       df_ref *def_rec, def;
 503
 504       /* Note that the BB_HEAD is always either a note or a label, but in
 505          any case it means that IN_A is defined outside the block.  */
 506       if (insn == bb_head)
 507         return false;
 508       if (NOTE_P (insn) || DEBUG_INSN_P (insn))
 509         continue;
 510
 511       /* Find a possible def of IN_A in INSN.  */
 512       for (def_rec = DF_INSN_DEFS (insn); (def = *def_rec) != NULL; def_rec++)
 513         if (DF_REF_REGNO (def) == REGNO (in_a))
 514           break;
 515
 516       /* No definitions of IN_A; continue searching.  */
 517       if (def == NULL)
 518         continue;
 519
 520       /* Bail if this is not a totally normal set of IN_A.  */
 521       if (DF_REF_IS_ARTIFICIAL (def))
 522         return false;
 523       if (DF_REF_FLAGS (def) & abnormal_flags)
 524         return false;
 525
 526       /* We've found an insn between the compare and the clobber that sets
 527          IN_A.  Given that pass_cprop_hardreg has not yet run, we still find
 528          situations in which we can usefully look through a copy insn.  */
 529       x = single_set (insn);
 530       if (x == NULL)
 531         return false;
 532       in_a = SET_SRC (x);
 533       if (!REG_P (in_a))
 534         return false;
 535     }
 536
 537   /* We've reached PREV_CLOBBER without finding a modification of IN_A.
 538      Validate that PREV_CLOBBER itself does in fact refer to IN_A.  Do
 539      recall that we've already validated the shape of PREV_CLOBBER.  */
 540   x = XVECEXP (PATTERN (insn), 0, 0);
 541   if (!rtx_equal_p (SET_DEST (x), in_a))
 542     return false;
 543   cmp_src = SET_SRC (x);
 544
 545   /* Determine if we ought to use a different CC_MODE here.  */
 546   flags = maybe_select_cc_mode (cmp, cmp_src, cmp->in_b);
 547   if (flags == NULL)
 548     flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
 549
 550   /* Generate a new comparison for installation in the setter.  */
 551   x = copy_rtx (cmp_src);
 552   x = gen_rtx_COMPARE (GET_MODE (flags), x, cmp->in_b);
 553   x = gen_rtx_SET (VOIDmode, flags, x);
 554
 555   /* Succeed if the new instruction is valid.  Note that we may have started
 556      a change group within maybe_select_cc_mode, therefore we must continue. */
 557   validate_change (insn, &XVECEXP (PATTERN (insn), 0, 1), x, true);
 558   if (!apply_change_group ())
 559     return false;
 560
 561   /* Success.  Delete the compare insn...  */
 562   delete_insn (cmp->insn);
 563
 564   /* ... and any notes that are now invalid due to multiple sets.  */
 565   x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
 566   if (x)
 567     remove_note (insn, x);
 568   x = find_reg_note (insn, REG_EQUAL, NULL);
 569   if (x)
 570     remove_note (insn, x);
 571   x = find_reg_note (insn, REG_EQUIV, NULL);
 572   if (x)
 573     remove_note (insn, x);
 574
 575   return true;
 576 }
 577
 578 /* Main entry point to the pass.  */
 579
 580 static unsigned int
 581 execute_compare_elim_after_reload (void)
 582 {
 583   df_analyze ();
 584
 585   gcc_checking_assert (all_compares == NULL);
 586
 587   /* Locate all comparisons and their uses, and eliminate duplicates.  */
 588   find_comparisons ();
 589   if (all_compares)
 590     {
 591       struct comparison *cmp;
 592       size_t i;
 593
 594       /* Eliminate comparisons that are redundant with flags computation.  */
 595       FOR_EACH_VEC_ELT (comparison_struct_p, all_compares, i, cmp)
 596         {
 597           try_eliminate_compare (cmp);
 598           XDELETE (cmp);
 599         }
 600
 601       VEC_free (comparison_struct_p, heap, all_compares);
 602       all_compares = NULL;
 603     }
 604
 605   return 0;
 606 }
 607
 608 static bool
 609 gate_compare_elim_after_reload (void)
 610 {
 611   /* Setting this target hook value is how a backend indicates the need.  */
 612   if (targetm.flags_regnum == INVALID_REGNUM)
 613     return false;
 614   return flag_compare_elim_after_reload;
 615 }
 616
 617 struct rtl_opt_pass pass_compare_elim_after_reload =
 618 {
 619  {
 620   RTL_PASS,
 621   "cmpelim",                            /* name */
 622   gate_compare_elim_after_reload,       /* gate */
 623   execute_compare_elim_after_reload,    /* execute */
 624   NULL,                                 /* sub */
 625   NULL,                                 /* next */
 626   0,                                    /* static_pass_number */
 627   TV_NONE,                              /* tv_id */
 628   0,                                    /* properties_required */
 629   0,                                    /* properties_provided */
 630   0,                                    /* properties_destroyed */
 631   0,                                    /* todo_flags_start */
 632   TODO_df_finish
 633   | TODO_df_verify
 634   | TODO_verify_rtl_sharing
 635   | TODO_ggc_collect                    /* todo_flags_finish */
 636  }
 637 };