gcc/value-prof.c

   1 /* Transformations based on profile information for values.
   2    Copyright (C) 2003, 2004 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "expr.h"
  27 #include "hard-reg-set.h"
  28 #include "basic-block.h"
  29 #include "value-prof.h"
  30 #include "output.h"
  31 #include "flags.h"
  32 #include "insn-config.h"
  33 #include "recog.h"
  34 #include "optabs.h"
  35 #include "regs.h"
  36
  37 static struct value_prof_hooks *value_prof_hooks;
  38
  39 /* In this file value profile based optimizations will be placed (none are
  40    here just now, but they are hopefully coming soon).
  41
  42    Every such optimization should add its requirements for profiled values to
  43    insn_values_to_profile function.  This function is called from branch_prob
  44    in profile.c and the requested values are instrumented by it in the first
  45    compilation with -fprofile-arcs.  The optimization may then read the
  46    gathered data in the second compilation with -fbranch-probabilities.
  47    The measured data is appended as REG_VALUE_PROFILE note to the instrumented
  48    insn.  The argument to the note consists of an EXPR_LIST where its
  49    members have the following meaning (from the first to the last):
  50
  51    -- type of information gathered (HIST_TYPE*)
  52    -- the expression that is profiled
  53    -- list of counters starting from the first one.  */
  54
  55 static void insn_divmod_values_to_profile (rtx, unsigned *,
  56                                            struct histogram_value **);
  57 static void insn_values_to_profile (rtx, unsigned *, struct histogram_value **);
  58 static rtx gen_divmod_fixed_value (enum machine_mode, enum rtx_code, rtx, rtx,
  59                                    rtx, gcov_type, int);
  60 static rtx gen_mod_pow2 (enum machine_mode, enum rtx_code, rtx, rtx, rtx, int);
  61 static rtx gen_mod_subtract (enum machine_mode, enum rtx_code, rtx, rtx, rtx,
  62                              int, int, int);
  63 static bool divmod_fixed_value_transform (rtx insn);
  64 static bool mod_pow2_value_transform (rtx);
  65 static bool mod_subtract_transform (rtx);
  66 \f
  67 /* Release the list of VALUES of length N_VALUES for that we want to measure
  68    histograms.  */
  69 void
  70 free_profiled_values (unsigned n_values ATTRIBUTE_UNUSED,
  71                       struct histogram_value *values)
  72 {
  73   free (values);
  74 }
  75
  76 /* Find values inside INSN for that we want to measure histograms for
  77    division/modulo optimization.  */
  78 static void
  79 insn_divmod_values_to_profile (rtx insn, unsigned *n_values,
  80                                struct histogram_value **values)
  81 {
  82   rtx set, set_src, op1, op2;
  83   enum machine_mode mode;
  84
  85   if (!INSN_P (insn))
  86     return;
  87
  88   set = single_set (insn);
  89   if (!set)
  90     return;
  91
  92   mode = GET_MODE (SET_DEST (set));
  93   if (!INTEGRAL_MODE_P (mode))
  94     return;
  95
  96   set_src = SET_SRC (set);
  97   switch (GET_CODE (set_src))
  98     {
  99     case DIV:
 100     case MOD:
 101     case UDIV:
 102     case UMOD:
 103       op1 = XEXP (set_src, 0);
 104       op2 = XEXP (set_src, 1);
 105       if (side_effects_p (op2))
 106         return;
 107
 108       /* Check for a special case where the divisor is power of 2.  */
 109       if ((GET_CODE (set_src) == UMOD) && !CONSTANT_P (op2))
 110         {
 111           *values = xrealloc (*values,
 112                               (*n_values + 1)
 113                                 * sizeof (struct histogram_value));
 114           (*values)[*n_values].value = op2;
 115           (*values)[*n_values].seq = NULL_RTX;
 116           (*values)[*n_values].mode = mode;
 117           (*values)[*n_values].insn = insn;
 118           (*values)[*n_values].type = HIST_TYPE_POW2;
 119           (*values)[*n_values].hdata.pow2.may_be_other = 1;
 120           (*n_values)++;
 121         }
 122
 123       /* Check whether the divisor is not in fact a constant.  */
 124       if (!CONSTANT_P (op2))
 125         {
 126           *values = xrealloc (*values,
 127                               (*n_values + 1)
 128                                 * sizeof (struct histogram_value));
 129           (*values)[*n_values].value = op2;
 130           (*values)[*n_values].mode = mode;
 131           (*values)[*n_values].seq = NULL_RTX;
 132           (*values)[*n_values].insn = insn;
 133           (*values)[*n_values].type = HIST_TYPE_SINGLE_VALUE;
 134           (*n_values)++;
 135         }
 136
 137       /* For mod, check whether it is not often a noop (or replaceable by
 138          a few subtractions).  */
 139       if (GET_CODE (set_src) == UMOD && !side_effects_p (op1))
 140         {
 141           rtx tmp;
 142
 143           *values = xrealloc (*values,
 144                               (*n_values + 1)
 145                                 * sizeof (struct histogram_value));
 146           start_sequence ();
 147           tmp = simplify_gen_binary (DIV, mode, copy_rtx (op1), copy_rtx (op2));
 148           (*values)[*n_values].value = force_operand (tmp, NULL_RTX);
 149           (*values)[*n_values].seq = get_insns ();
 150           end_sequence ();
 151           (*values)[*n_values].mode = mode;
 152           (*values)[*n_values].insn = insn;
 153           (*values)[*n_values].type = HIST_TYPE_INTERVAL;
 154           (*values)[*n_values].hdata.intvl.int_start = 0;
 155           (*values)[*n_values].hdata.intvl.steps = 2;
 156           (*values)[*n_values].hdata.intvl.may_be_less = 1;
 157           (*values)[*n_values].hdata.intvl.may_be_more = 1;
 158           (*n_values)++;
 159         }
 160       return;
 161
 162     default:
 163       return;
 164     }
 165 }
 166
 167 /* Find values inside INSN for that we want to measure histograms and adds
 168    them to list VALUES (increasing the record of its length in N_VALUES).  */
 169 static void
 170 insn_values_to_profile (rtx insn,
 171                         unsigned *n_values,
 172                         struct histogram_value **values)
 173 {
 174   if (flag_value_profile_transformations)
 175     insn_divmod_values_to_profile (insn, n_values, values);
 176 }
 177
 178 /* Find list of values for that we want to measure histograms.  */
 179 static void
 180 rtl_find_values_to_profile (unsigned *n_values, struct histogram_value **values)
 181 {
 182   rtx insn;
 183   unsigned i;
 184
 185   life_analysis (NULL, PROP_DEATH_NOTES);
 186
 187   *n_values = 0;
 188   *values = NULL;
 189   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 190     insn_values_to_profile (insn, n_values, values);
 191
 192   for (i = 0; i < *n_values; i++)
 193     {
 194       switch ((*values)[i].type)
 195         {
 196         case HIST_TYPE_INTERVAL:
 197           if (dump_file)
 198             fprintf (dump_file,
 199                      "Interval counter for insn %d, range %d -- %d.\n",
 200                      INSN_UID ((rtx)(*values)[i].insn),
 201                      (*values)[i].hdata.intvl.int_start,
 202                      ((*values)[i].hdata.intvl.int_start
 203                       + (*values)[i].hdata.intvl.steps - 1));
 204           (*values)[i].n_counters = (*values)[i].hdata.intvl.steps +
 205                   ((*values)[i].hdata.intvl.may_be_less ? 1 : 0) +
 206                   ((*values)[i].hdata.intvl.may_be_more ? 1 : 0);
 207           break;
 208
 209         case HIST_TYPE_POW2:
 210           if (dump_file)
 211             fprintf (dump_file,
 212                      "Pow2 counter for insn %d.\n",
 213                      INSN_UID ((rtx)(*values)[i].insn));
 214           (*values)[i].n_counters
 215                 = GET_MODE_BITSIZE ((*values)[i].mode)
 216                   +  ((*values)[i].hdata.pow2.may_be_other ? 1 : 0);
 217           break;
 218
 219         case HIST_TYPE_SINGLE_VALUE:
 220           if (dump_file)
 221             fprintf (dump_file,
 222                      "Single value counter for insn %d.\n",
 223                      INSN_UID ((rtx)(*values)[i].insn));
 224           (*values)[i].n_counters = 3;
 225           break;
 226
 227         case HIST_TYPE_CONST_DELTA:
 228           if (dump_file)
 229             fprintf (dump_file,
 230                      "Constant delta counter for insn %d.\n",
 231                      INSN_UID ((rtx)(*values)[i].insn));
 232           (*values)[i].n_counters = 4;
 233           break;
 234
 235         default:
 236           abort ();
 237         }
 238     }
 239   allocate_reg_info (max_reg_num (), FALSE, FALSE);
 240 }
 241
 242 /* Main entry point.  Finds REG_VALUE_PROFILE notes from profiler and uses
 243    them to identify and exploit properties of values that are hard to analyze
 244    statically.
 245
 246    We do following transformations:
 247
 248    1)
 249
 250    x = a / b;
 251
 252    where b is almost always a constant N is transformed to
 253
 254    if (b == N)
 255      x = a / N;
 256    else
 257      x = a / b;
 258
 259    Analogically with %
 260
 261    2)
 262
 263    x = a % b
 264
 265    where b is almost always a power of 2 and the division is unsigned
 266    TODO -- handle signed case as well
 267
 268    if ((b & (b - 1)) == 0)
 269      x = a & (b - 1);
 270    else
 271      x = x % b;
 272
 273    Note that when b = 0, no error will occur and x = a; this is correct,
 274    as result of such operation is undefined.
 275
 276    3)
 277
 278    x = a % b
 279
 280    where a is almost always less then b and the division is unsigned
 281    TODO -- handle signed case as well
 282
 283    x = a;
 284    if (x >= b)
 285      x %= b;
 286
 287    4)
 288
 289    x = a % b
 290
 291    where a is almost always less then 2 * b and the division is unsigned
 292    TODO -- handle signed case as well
 293
 294    x = a;
 295    if (x >= b)
 296      x -= b;
 297    if (x >= b)
 298      x %= b;
 299
 300    It would be possible to continue analogically for K * b for other small
 301    K's, but it is probably not useful.
 302
 303    TODO:
 304
 305    There are other useful cases that could be handled by a similar mechanism,
 306    for example:
 307
 308    for (i = 0; i < n; i++)
 309      ...
 310
 311    transform to (for constant N):
 312
 313    if (n == N)
 314      for (i = 0; i < N; i++)
 315        ...
 316    else
 317      for (i = 0; i < n; i++)
 318        ...
 319    making unroller happy.  Since this may grow the code significantly,
 320    we would have to be very careful here.  */
 321
 322 static bool
 323 rtl_value_profile_transformations (void)
 324 {
 325   rtx insn, next;
 326   int changed = false;
 327
 328   for (insn = get_insns (); insn; insn = next)
 329     {
 330       next = NEXT_INSN (insn);
 331
 332       if (!INSN_P (insn))
 333         continue;
 334
 335       /* Scan for insn carrying a histogram.  */
 336       if (!find_reg_note (insn, REG_VALUE_PROFILE, 0))
 337         continue;
 338
 339       /* Ignore cold areas -- we are growing a code.  */
 340       if (!maybe_hot_bb_p (BLOCK_FOR_INSN (insn)))
 341         continue;
 342
 343       if (dump_file)
 344         {
 345           fprintf (dump_file, "Trying transformations on insn %d\n",
 346                    INSN_UID (insn));
 347           print_rtl_single (dump_file, insn);
 348         }
 349
 350       /* Transformations:  */
 351       if (flag_value_profile_transformations
 352           && (mod_subtract_transform (insn)
 353               || divmod_fixed_value_transform (insn)
 354               || mod_pow2_value_transform (insn)))
 355         changed = true;
 356     }
 357
 358   if (changed)
 359     {
 360       commit_edge_insertions ();
 361       allocate_reg_info (max_reg_num (), FALSE, FALSE);
 362     }
 363
 364   return changed;
 365 }
 366
 367 /* Generate code for transformation 1 (with MODE and OPERATION, operands OP1
 368    and OP2, whose value is expected to be VALUE, result TARGET and
 369    probability of taking the optimal path PROB).  */
 370 static rtx
 371 gen_divmod_fixed_value (enum machine_mode mode, enum rtx_code operation,
 372                         rtx target, rtx op1, rtx op2, gcov_type value,
 373                         int prob)
 374 {
 375   rtx tmp, tmp1, jump;
 376   rtx neq_label = gen_label_rtx ();
 377   rtx end_label = gen_label_rtx ();
 378   rtx sequence;
 379
 380   start_sequence ();
 381
 382   if (!REG_P (op2))
 383     {
 384       tmp = gen_reg_rtx (mode);
 385       emit_move_insn (tmp, copy_rtx (op2));
 386     }
 387   else
 388     tmp = op2;
 389
 390   do_compare_rtx_and_jump (tmp, GEN_INT (value), NE, 0, mode, NULL_RTX,
 391                            NULL_RTX, neq_label);
 392
 393   /* Add branch probability to jump we just created.  */
 394   jump = get_last_insn ();
 395   REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB,
 396                                         GEN_INT (REG_BR_PROB_BASE - prob),
 397                                         REG_NOTES (jump));
 398
 399   tmp1 = simplify_gen_binary (operation, mode,
 400                               copy_rtx (op1), GEN_INT (value));
 401   tmp1 = force_operand (tmp1, target);
 402   if (tmp1 != target)
 403     emit_move_insn (copy_rtx (target), copy_rtx (tmp1));
 404
 405   emit_jump_insn (gen_jump (end_label));
 406   emit_barrier ();
 407
 408   emit_label (neq_label);
 409   tmp1 = simplify_gen_binary (operation, mode,
 410                               copy_rtx (op1), copy_rtx (tmp));
 411   tmp1 = force_operand (tmp1, target);
 412   if (tmp1 != target)
 413     emit_move_insn (copy_rtx (target), copy_rtx (tmp1));
 414
 415   emit_label (end_label);
 416
 417   sequence = get_insns ();
 418   end_sequence ();
 419   rebuild_jump_labels (sequence);
 420   return sequence;
 421 }
 422
 423 /* Do transform 1) on INSN if applicable.  */
 424 static bool
 425 divmod_fixed_value_transform (rtx insn)
 426 {
 427   rtx set, set_src, set_dest, op1, op2, value, histogram;
 428   enum rtx_code code;
 429   enum machine_mode mode;
 430   gcov_type val, count, all;
 431   edge e;
 432   int prob;
 433
 434   set = single_set (insn);
 435   if (!set)
 436     return false;
 437
 438   set_src = SET_SRC (set);
 439   set_dest = SET_DEST (set);
 440   code = GET_CODE (set_src);
 441   mode = GET_MODE (set_dest);
 442
 443   if (code != DIV && code != MOD && code != UDIV && code != UMOD)
 444     return false;
 445   op1 = XEXP (set_src, false);
 446   op2 = XEXP (set_src, 1);
 447
 448   for (histogram = REG_NOTES (insn);
 449        histogram;
 450        histogram = XEXP (histogram, 1))
 451     if (REG_NOTE_KIND (histogram) == REG_VALUE_PROFILE
 452         && XEXP (XEXP (histogram, 0), 0) == GEN_INT (HIST_TYPE_SINGLE_VALUE))
 453       break;
 454
 455   if (!histogram)
 456     return false;
 457
 458   histogram = XEXP (XEXP (histogram, 0), 1);
 459   value = XEXP (histogram, 0);
 460   histogram = XEXP (histogram, 1);
 461   val = INTVAL (XEXP (histogram, 0));
 462   histogram = XEXP (histogram, 1);
 463   count = INTVAL (XEXP (histogram, 0));
 464   histogram = XEXP (histogram, 1);
 465   all = INTVAL (XEXP (histogram, 0));
 466
 467   /* We require that count is at least half of all; this means
 468      that for the transformation to fire the value must be constant
 469      at least 50% of time (and 75% gives the guarantee of usage).  */
 470   if (!rtx_equal_p (op2, value) || 2 * count < all)
 471     return false;
 472
 473   if (dump_file)
 474     fprintf (dump_file, "Div/mod by constant transformation on insn %d\n",
 475              INSN_UID (insn));
 476
 477   /* Compute probability of taking the optimal path.  */
 478   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 479
 480   e = split_block (BLOCK_FOR_INSN (insn), PREV_INSN (insn));
 481   delete_insn (insn);
 482
 483   insert_insn_on_edge (
 484         gen_divmod_fixed_value (mode, code, set_dest,
 485                                 op1, op2, val, prob), e);
 486
 487   return true;
 488 }
 489
 490 /* Generate code for transformation 2 (with MODE and OPERATION, operands OP1
 491    and OP2, result TARGET and probability of taking the optimal path PROB).  */
 492 static rtx
 493 gen_mod_pow2 (enum machine_mode mode, enum rtx_code operation, rtx target,
 494               rtx op1, rtx op2, int prob)
 495 {
 496   rtx tmp, tmp1, tmp2, tmp3, jump;
 497   rtx neq_label = gen_label_rtx ();
 498   rtx end_label = gen_label_rtx ();
 499   rtx sequence;
 500
 501   start_sequence ();
 502
 503   if (!REG_P (op2))
 504     {
 505       tmp = gen_reg_rtx (mode);
 506       emit_move_insn (tmp, copy_rtx (op2));
 507     }
 508   else
 509     tmp = op2;
 510
 511   tmp1 = expand_simple_binop (mode, PLUS, tmp, constm1_rtx, NULL_RTX,
 512                               0, OPTAB_WIDEN);
 513   tmp2 = expand_simple_binop (mode, AND, tmp, tmp1, NULL_RTX,
 514                               0, OPTAB_WIDEN);
 515   do_compare_rtx_and_jump (tmp2, const0_rtx, NE, 0, mode, NULL_RTX,
 516                            NULL_RTX, neq_label);
 517
 518   /* Add branch probability to jump we just created.  */
 519   jump = get_last_insn ();
 520   REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB,
 521                                         GEN_INT (REG_BR_PROB_BASE - prob),
 522                                         REG_NOTES (jump));
 523
 524   tmp3 = expand_simple_binop (mode, AND, op1, tmp1, target,
 525                               0, OPTAB_WIDEN);
 526   if (tmp3 != target)
 527     emit_move_insn (copy_rtx (target), tmp3);
 528   emit_jump_insn (gen_jump (end_label));
 529   emit_barrier ();
 530
 531   emit_label (neq_label);
 532   tmp1 = simplify_gen_binary (operation, mode, copy_rtx (op1), copy_rtx (tmp));
 533   tmp1 = force_operand (tmp1, target);
 534   if (tmp1 != target)
 535     emit_move_insn (target, tmp1);
 536
 537   emit_label (end_label);
 538
 539   sequence = get_insns ();
 540   end_sequence ();
 541   rebuild_jump_labels (sequence);
 542   return sequence;
 543 }
 544
 545 /* Do transform 2) on INSN if applicable.  */
 546 static bool
 547 mod_pow2_value_transform (rtx insn)
 548 {
 549   rtx set, set_src, set_dest, op1, op2, value, histogram;
 550   enum rtx_code code;
 551   enum machine_mode mode;
 552   gcov_type wrong_values, count;
 553   edge e;
 554   int i, all, prob;
 555
 556   set = single_set (insn);
 557   if (!set)
 558     return false;
 559
 560   set_src = SET_SRC (set);
 561   set_dest = SET_DEST (set);
 562   code = GET_CODE (set_src);
 563   mode = GET_MODE (set_dest);
 564
 565   if (code != UMOD)
 566     return false;
 567   op1 = XEXP (set_src, 0);
 568   op2 = XEXP (set_src, 1);
 569
 570   for (histogram = REG_NOTES (insn);
 571        histogram;
 572        histogram = XEXP (histogram, 1))
 573     if (REG_NOTE_KIND (histogram) == REG_VALUE_PROFILE
 574         && XEXP (XEXP (histogram, 0), 0) == GEN_INT (HIST_TYPE_POW2))
 575       break;
 576
 577   if (!histogram)
 578     return false;
 579
 580   histogram = XEXP (XEXP (histogram, 0), 1);
 581   value = XEXP (histogram, 0);
 582   histogram = XEXP (histogram, 1);
 583   wrong_values =INTVAL (XEXP (histogram, 0));
 584   histogram = XEXP (histogram, 1);
 585
 586   count = 0;
 587   for (i = 0; i < GET_MODE_BITSIZE (mode); i++)
 588     {
 589       count += INTVAL (XEXP (histogram, 0));
 590       histogram = XEXP (histogram, 1);
 591     }
 592
 593   if (!rtx_equal_p (op2, value))
 594     return false;
 595
 596   /* We require that we hit a power of two at least half of all evaluations.  */
 597   if (count < wrong_values)
 598     return false;
 599
 600   if (dump_file)
 601     fprintf (dump_file, "Mod power of 2 transformation on insn %d\n",
 602              INSN_UID (insn));
 603
 604   /* Compute probability of taking the optimal path.  */
 605   all = count + wrong_values;
 606   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 607
 608   e = split_block (BLOCK_FOR_INSN (insn), PREV_INSN (insn));
 609   delete_insn (insn);
 610
 611   insert_insn_on_edge (
 612         gen_mod_pow2 (mode, code, set_dest, op1, op2, prob), e);
 613
 614   return true;
 615 }
 616
 617 /* Generate code for transformations 3 and 4 (with MODE and OPERATION,
 618    operands OP1 and OP2, result TARGET, at most SUB subtractions, and
 619    probability of taking the optimal path(s) PROB1 and PROB2).  */
 620 static rtx
 621 gen_mod_subtract (enum machine_mode mode, enum rtx_code operation,
 622                   rtx target, rtx op1, rtx op2, int sub, int prob1, int prob2)
 623 {
 624   rtx tmp, tmp1, jump;
 625   rtx end_label = gen_label_rtx ();
 626   rtx sequence;
 627   int i;
 628
 629   start_sequence ();
 630
 631   if (!REG_P (op2))
 632     {
 633       tmp = gen_reg_rtx (mode);
 634       emit_move_insn (tmp, copy_rtx (op2));
 635     }
 636   else
 637     tmp = op2;
 638
 639   emit_move_insn (target, copy_rtx (op1));
 640   do_compare_rtx_and_jump (target, tmp, LTU, 0, mode, NULL_RTX,
 641                            NULL_RTX, end_label);
 642
 643   /* Add branch probability to jump we just created.  */
 644   jump = get_last_insn ();
 645   REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB,
 646                                         GEN_INT (prob1), REG_NOTES (jump));
 647
 648   for (i = 0; i < sub; i++)
 649     {
 650       tmp1 = expand_simple_binop (mode, MINUS, target, tmp, target,
 651                                   0, OPTAB_WIDEN);
 652       if (tmp1 != target)
 653         emit_move_insn (target, tmp1);
 654       do_compare_rtx_and_jump (target, tmp, LTU, 0, mode, NULL_RTX,
 655                                NULL_RTX, end_label);
 656
 657       /* Add branch probability to jump we just created.  */
 658       jump = get_last_insn ();
 659       REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB,
 660                                             GEN_INT (prob2), REG_NOTES (jump));
 661     }
 662
 663   tmp1 = simplify_gen_binary (operation, mode, copy_rtx (target), copy_rtx (tmp));
 664   tmp1 = force_operand (tmp1, target);
 665   if (tmp1 != target)
 666     emit_move_insn (target, tmp1);
 667
 668   emit_label (end_label);
 669
 670   sequence = get_insns ();
 671   end_sequence ();
 672   rebuild_jump_labels (sequence);
 673   return sequence;
 674 }
 675
 676 /* Do transforms 3) and 4) on INSN if applicable.  */
 677 static bool
 678 mod_subtract_transform (rtx insn)
 679 {
 680   rtx set, set_src, set_dest, op1, op2, value, histogram;
 681   enum rtx_code code;
 682   enum machine_mode mode;
 683   gcov_type wrong_values, counts[2], count, all;
 684   edge e;
 685   int i, prob1, prob2;
 686
 687   set = single_set (insn);
 688   if (!set)
 689     return false;
 690
 691   set_src = SET_SRC (set);
 692   set_dest = SET_DEST (set);
 693   code = GET_CODE (set_src);
 694   mode = GET_MODE (set_dest);
 695
 696   if (code != UMOD)
 697     return false;
 698   op1 = XEXP (set_src, 0);
 699   op2 = XEXP (set_src, 1);
 700
 701   for (histogram = REG_NOTES (insn);
 702        histogram;
 703        histogram = XEXP (histogram, 1))
 704     if (REG_NOTE_KIND (histogram) == REG_VALUE_PROFILE
 705         && XEXP (XEXP (histogram, 0), 0) == GEN_INT (HIST_TYPE_INTERVAL))
 706       break;
 707
 708   if (!histogram)
 709     return false;
 710
 711   histogram = XEXP (XEXP (histogram, 0), 1);
 712   value = XEXP (histogram, 0);
 713   histogram = XEXP (histogram, 1);
 714
 715   all = 0;
 716   for (i = 0; i < 2; i++)
 717     {
 718       counts[i] = INTVAL (XEXP (histogram, 0));
 719       all += counts[i];
 720       histogram = XEXP (histogram, 1);
 721     }
 722   wrong_values = INTVAL (XEXP (histogram, 0));
 723   histogram = XEXP (histogram, 1);
 724   wrong_values += INTVAL (XEXP (histogram, 0));
 725   all += wrong_values;
 726
 727   /* We require that we use just subtractions in at least 50% of all
 728      evaluations.  */
 729   count = 0;
 730   for (i = 0; i < 2; i++)
 731     {
 732       count += counts[i];
 733       if (count * 2 >= all)
 734         break;
 735     }
 736
 737   if (i == 2)
 738     return false;
 739
 740   if (dump_file)
 741     fprintf (dump_file, "Mod subtract transformation on insn %d\n",
 742              INSN_UID (insn));
 743
 744   /* Compute probability of taking the optimal path(s).  */
 745   prob1 = (counts[0] * REG_BR_PROB_BASE + all / 2) / all;
 746   prob2 = (counts[1] * REG_BR_PROB_BASE + all / 2) / all;
 747
 748   e = split_block (BLOCK_FOR_INSN (insn), PREV_INSN (insn));
 749   delete_insn (insn);
 750
 751   insert_insn_on_edge (
 752         gen_mod_subtract (mode, code, set_dest,
 753                           op1, op2, i, prob1, prob2), e);
 754
 755   return true;
 756 }
 757 \f
 758 /* Connection to the outside world.  */
 759 /* Struct for IR-dependent hooks.  */
 760 struct value_prof_hooks {
 761   /* Find list of values for which we want to measure histograms.  */
 762   void (*find_values_to_profile) (unsigned *, struct histogram_value **);
 763
 764   /* Identify and exploit properties of values that are hard to analyze
 765      statically.  See value-prof.c for more detail.  */
 766   bool (*value_profile_transformations) (void);
 767 };
 768
 769 /* Hooks for RTL-based versions (the only ones that currently work).  */
 770 static struct value_prof_hooks rtl_value_prof_hooks =
 771 {
 772   rtl_find_values_to_profile,
 773   rtl_value_profile_transformations
 774 };
 775
 776 void
 777 rtl_register_value_prof_hooks (void)
 778 {
 779   value_prof_hooks = &rtl_value_prof_hooks;
 780   if (ir_type ())
 781     abort ();
 782 }
 783 \f
 784 /* Tree-based versions are stubs for now.  */
 785 static void
 786 tree_find_values_to_profile (unsigned *n_values, struct histogram_value **values)
 787 {
 788   (void)n_values;
 789   (void)values;
 790   abort ();
 791 }
 792
 793 static bool
 794 tree_value_profile_transformations (void)
 795 {
 796   abort ();
 797 }
 798
 799 static struct value_prof_hooks tree_value_prof_hooks = {
 800   tree_find_values_to_profile,
 801   tree_value_profile_transformations
 802 };
 803
 804 void
 805 tree_register_value_prof_hooks (void)
 806 {
 807   value_prof_hooks = &tree_value_prof_hooks;
 808   if (!ir_type ())
 809     abort ();
 810 }
 811 \f
 812 /* IR-independent entry points.  */
 813 void
 814 find_values_to_profile (unsigned *n_values, struct histogram_value **values)
 815 {
 816   (value_prof_hooks->find_values_to_profile) (n_values, values);
 817 }
 818
 819 bool
 820 value_profile_transformations (void)
 821 {
 822   return (value_prof_hooks->value_profile_transformations) ();
 823 }
 824