1/* Transformations based on profile information for values. 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, 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#include "ggc.h" 37#include "tree-flow.h" 38#include "tree-flow-inline.h" 39#include "diagnostic.h" 40#include "coverage.h" 41#include "tree.h" 42#include "gcov-io.h" 43#include "timevar.h" 44#include "tree-pass.h" 45#include "toplev.h" 46 47static struct value_prof_hooks *value_prof_hooks; 48 49/* In this file value profile based optimizations are placed. Currently the 50 following optimizations are implemented (for more detailed descriptions 51 see comments at value_profile_transformations): 52 53 1) Division/modulo specialization. Provided that we can determine that the 54 operands of the division have some special properties, we may use it to 55 produce more effective code. 56 2) Speculative prefetching. If we are able to determine that the difference 57 between addresses accessed by a memory reference is usually constant, we 58 may add the prefetch instructions. 59 FIXME: This transformation was removed together with RTL based value 60 profiling. 61 62 Every such optimization should add its requirements for profiled values to 63 insn_values_to_profile function. This function is called from branch_prob 64 in profile.c and the requested values are instrumented by it in the first 65 compilation with -fprofile-arcs. The optimization may then read the 66 gathered data in the second compilation with -fbranch-probabilities. 67 68 The measured data is pointed to from the histograms 69 field of the statement annotation of the instrumented insns. It is 70 kept as a linked list of struct histogram_value_t's, which contain the 71 same information as above. */ 72 73 74static tree tree_divmod_fixed_value (tree, tree, tree, tree, 75 tree, int, gcov_type, gcov_type); 76static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type); 77static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int, 78 gcov_type, gcov_type, gcov_type); 79static bool tree_divmod_fixed_value_transform (tree); 80static bool tree_mod_pow2_value_transform (tree); 81static bool tree_mod_subtract_transform (tree); 82 83/* The overall number of invocations of the counter should match execution count 84 of basic block. Report it as error rather than internal error as it might 85 mean that user has misused the profile somehow. */ 86static bool 87check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count) 88{ 89 if (all != bb_count) 90 { 91 location_t * locus; 92 locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt) 93 ? EXPR_LOCUS (stmt) 94 : &DECL_SOURCE_LOCATION (current_function_decl)); 95 error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)", 96 locus, name, (int)all, (int)bb_count); 97 return true; 98 } 99 return false; 100} 101 102/* Tree based transformations. */ 103static bool 104tree_value_profile_transformations (void) 105{ 106 basic_block bb; 107 block_stmt_iterator bsi; 108 bool changed = false; 109 110 FOR_EACH_BB (bb) 111 { 112 /* Ignore cold areas -- we are enlarging the code. */ 113 if (!maybe_hot_bb_p (bb)) 114 continue; 115 116 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 117 { 118 tree stmt = bsi_stmt (bsi); 119 stmt_ann_t ann = get_stmt_ann (stmt); 120 histogram_value th = ann->histograms; 121 if (!th) 122 continue; 123 124 if (dump_file) 125 { 126 fprintf (dump_file, "Trying transformations on insn "); 127 print_generic_stmt (dump_file, stmt, TDF_SLIM); 128 } 129 130 /* Transformations: */ 131 /* The order of things in this conditional controls which 132 transformation is used when more than one is applicable. */ 133 /* It is expected that any code added by the transformations 134 will be added before the current statement, and that the 135 current statement remain valid (although possibly 136 modified) upon return. */ 137 if (flag_value_profile_transformations 138 && (tree_mod_subtract_transform (stmt) 139 || tree_divmod_fixed_value_transform (stmt) 140 || tree_mod_pow2_value_transform (stmt))) 141 { 142 changed = true; 143 /* Original statement may no longer be in the same block. */ 144 if (bb != bb_for_stmt (stmt)) 145 { 146 bb = bb_for_stmt (stmt); 147 bsi = bsi_for_stmt (stmt); 148 } 149 } 150 151 /* Free extra storage from compute_value_histograms. */ 152 while (th) 153 { 154 free (th->hvalue.counters); 155 th = th->hvalue.next; 156 } 157 ann->histograms = 0; 158 } 159 } 160 161 if (changed) 162 { 163 counts_to_freqs (); 164 } 165 166 return changed; 167} 168 169/* Generate code for transformation 1 (with OPERATION, operands OP1 170 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and 171 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL 172 within roundoff error). This generates the result into a temp and returns 173 the temp; it does not replace or alter the original STMT. */ 174static tree 175tree_divmod_fixed_value (tree stmt, tree operation, 176 tree op1, tree op2, tree value, int prob, gcov_type count, 177 gcov_type all) 178{ 179 tree stmt1, stmt2, stmt3; 180 tree tmp1, tmp2, tmpv; 181 tree label_decl1 = create_artificial_label (); 182 tree label_decl2 = create_artificial_label (); 183 tree label_decl3 = create_artificial_label (); 184 tree label1, label2, label3; 185 tree bb1end, bb2end, bb3end; 186 basic_block bb, bb2, bb3, bb4; 187 tree optype = TREE_TYPE (operation); 188 edge e12, e13, e23, e24, e34; 189 block_stmt_iterator bsi; 190 191 bb = bb_for_stmt (stmt); 192 bsi = bsi_for_stmt (stmt); 193 194 tmpv = create_tmp_var (optype, "PROF"); 195 tmp1 = create_tmp_var (optype, "PROF"); 196 stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value)); 197 stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); 198 stmt3 = build3 (COND_EXPR, void_type_node, 199 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv), 200 build1 (GOTO_EXPR, void_type_node, label_decl2), 201 build1 (GOTO_EXPR, void_type_node, label_decl1)); 202 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 203 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 204 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 205 bb1end = stmt3; 206 207 tmp2 = create_tmp_var (optype, "PROF"); 208 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 209 stmt1 = build2 (MODIFY_EXPR, optype, tmp2, 210 build2 (TREE_CODE (operation), optype, op1, tmpv)); 211 bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 212 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 213 bb2end = stmt1; 214 215 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 216 stmt1 = build2 (MODIFY_EXPR, optype, tmp2, 217 build2 (TREE_CODE (operation), optype, op1, op2)); 218 bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 219 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 220 bb3end = stmt1; 221 222 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 223 bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 224 225 /* Fix CFG. */ 226 /* Edge e23 connects bb2 to bb3, etc. */ 227 e12 = split_block (bb, bb1end); 228 bb2 = e12->dest; 229 bb2->count = count; 230 e23 = split_block (bb2, bb2end); 231 bb3 = e23->dest; 232 bb3->count = all - count; 233 e34 = split_block (bb3, bb3end); 234 bb4 = e34->dest; 235 bb4->count = all; 236 237 e12->flags &= ~EDGE_FALLTHRU; 238 e12->flags |= EDGE_FALSE_VALUE; 239 e12->probability = prob; 240 e12->count = count; 241 242 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 243 e13->probability = REG_BR_PROB_BASE - prob; 244 e13->count = all - count; 245 246 remove_edge (e23); 247 248 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 249 e24->probability = REG_BR_PROB_BASE; 250 e24->count = count; 251 252 e34->probability = REG_BR_PROB_BASE; 253 e34->count = all - count; 254 255 return tmp2; 256} 257 258/* Do transform 1) on INSN if applicable. */ 259static bool 260tree_divmod_fixed_value_transform (tree stmt) 261{ 262 stmt_ann_t ann = get_stmt_ann (stmt); 263 histogram_value histogram; 264 enum tree_code code; 265 gcov_type val, count, all; 266 tree modify, op, op1, op2, result, value, tree_val; 267 int prob; 268 269 modify = stmt; 270 if (TREE_CODE (stmt) == RETURN_EXPR 271 && TREE_OPERAND (stmt, 0) 272 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 273 modify = TREE_OPERAND (stmt, 0); 274 if (TREE_CODE (modify) != MODIFY_EXPR) 275 return false; 276 op = TREE_OPERAND (modify, 1); 277 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 278 return false; 279 code = TREE_CODE (op); 280 281 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) 282 return false; 283 284 op1 = TREE_OPERAND (op, 0); 285 op2 = TREE_OPERAND (op, 1); 286 if (!ann->histograms) 287 return false; 288 289 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 290 if (histogram->type == HIST_TYPE_SINGLE_VALUE) 291 break; 292 293 if (!histogram) 294 return false; 295 296 value = histogram->hvalue.value; 297 val = histogram->hvalue.counters[0]; 298 count = histogram->hvalue.counters[1]; 299 all = histogram->hvalue.counters[2]; 300 301 /* We require that count is at least half of all; this means 302 that for the transformation to fire the value must be constant 303 at least 50% of time (and 75% gives the guarantee of usage). */ 304 if (simple_cst_equal (op2, value) != 1 || 2 * count < all) 305 return false; 306 307 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count)) 308 return false; 309 310 /* Compute probability of taking the optimal path. */ 311 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 312 313 tree_val = build_int_cst_wide (get_gcov_type (), 314 (unsigned HOST_WIDE_INT) val, 315 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); 316 result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all); 317 318 if (dump_file) 319 { 320 fprintf (dump_file, "Div/mod by constant "); 321 print_generic_expr (dump_file, value, TDF_SLIM); 322 fprintf (dump_file, "="); 323 print_generic_expr (dump_file, tree_val, TDF_SLIM); 324 fprintf (dump_file, " transformation on insn "); 325 print_generic_stmt (dump_file, stmt, TDF_SLIM); 326 } 327 328 TREE_OPERAND (modify, 1) = result; 329 330 return true; 331} 332 333/* Generate code for transformation 2 (with OPERATION, operands OP1 334 and OP2, parent modify-expr STMT and probability of taking the optimal 335 path PROB, which is equivalent to COUNT/ALL within roundoff error). 336 This generates the result into a temp and returns 337 the temp; it does not replace or alter the original STMT. */ 338static tree 339tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, 340 gcov_type count, gcov_type all) 341{ 342 tree stmt1, stmt2, stmt3, stmt4; 343 tree tmp2, tmp3; 344 tree label_decl1 = create_artificial_label (); 345 tree label_decl2 = create_artificial_label (); 346 tree label_decl3 = create_artificial_label (); 347 tree label1, label2, label3; 348 tree bb1end, bb2end, bb3end; 349 basic_block bb, bb2, bb3, bb4; 350 tree optype = TREE_TYPE (operation); 351 edge e12, e13, e23, e24, e34; 352 block_stmt_iterator bsi; 353 tree result = create_tmp_var (optype, "PROF"); 354 355 bb = bb_for_stmt (stmt); 356 bsi = bsi_for_stmt (stmt); 357 358 tmp2 = create_tmp_var (optype, "PROF"); 359 tmp3 = create_tmp_var (optype, "PROF"); 360 stmt2 = build2 (MODIFY_EXPR, optype, tmp2, 361 build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1))); 362 stmt3 = build2 (MODIFY_EXPR, optype, tmp3, 363 build2 (BIT_AND_EXPR, optype, tmp2, op2)); 364 stmt4 = build3 (COND_EXPR, void_type_node, 365 build2 (NE_EXPR, boolean_type_node, 366 tmp3, build_int_cst (optype, 0)), 367 build1 (GOTO_EXPR, void_type_node, label_decl2), 368 build1 (GOTO_EXPR, void_type_node, label_decl1)); 369 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 370 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 371 bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT); 372 bb1end = stmt4; 373 374 /* tmp2 == op2-1 inherited from previous block */ 375 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 376 stmt1 = build2 (MODIFY_EXPR, optype, result, 377 build2 (BIT_AND_EXPR, optype, op1, tmp2)); 378 bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 379 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 380 bb2end = stmt1; 381 382 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 383 stmt1 = build2 (MODIFY_EXPR, optype, result, 384 build2 (TREE_CODE (operation), optype, op1, op2)); 385 bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 386 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 387 bb3end = stmt1; 388 389 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 390 bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 391 392 /* Fix CFG. */ 393 /* Edge e23 connects bb2 to bb3, etc. */ 394 e12 = split_block (bb, bb1end); 395 bb2 = e12->dest; 396 bb2->count = count; 397 e23 = split_block (bb2, bb2end); 398 bb3 = e23->dest; 399 bb3->count = all - count; 400 e34 = split_block (bb3, bb3end); 401 bb4 = e34->dest; 402 bb4->count = all; 403 404 e12->flags &= ~EDGE_FALLTHRU; 405 e12->flags |= EDGE_FALSE_VALUE; 406 e12->probability = prob; 407 e12->count = count; 408 409 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 410 e13->probability = REG_BR_PROB_BASE - prob; 411 e13->count = all - count; 412 413 remove_edge (e23); 414 415 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 416 e24->probability = REG_BR_PROB_BASE; 417 e24->count = count; 418 419 e34->probability = REG_BR_PROB_BASE; 420 e34->count = all - count; 421 422 return result; 423} 424 425/* Do transform 2) on INSN if applicable. */ 426static bool 427tree_mod_pow2_value_transform (tree stmt) 428{ 429 stmt_ann_t ann = get_stmt_ann (stmt); 430 histogram_value histogram; 431 enum tree_code code; 432 gcov_type count, wrong_values, all; 433 tree modify, op, op1, op2, result, value; 434 int prob; 435 436 modify = stmt; 437 if (TREE_CODE (stmt) == RETURN_EXPR 438 && TREE_OPERAND (stmt, 0) 439 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 440 modify = TREE_OPERAND (stmt, 0); 441 if (TREE_CODE (modify) != MODIFY_EXPR) 442 return false; 443 op = TREE_OPERAND (modify, 1); 444 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 445 return false; 446 code = TREE_CODE (op); 447 448 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) 449 return false; 450 451 op1 = TREE_OPERAND (op, 0); 452 op2 = TREE_OPERAND (op, 1); 453 if (!ann->histograms) 454 return false; 455 456 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 457 if (histogram->type == HIST_TYPE_POW2) 458 break; 459 460 if (!histogram) 461 return false; 462 463 value = histogram->hvalue.value; 464 wrong_values = histogram->hvalue.counters[0]; 465 count = histogram->hvalue.counters[1]; 466 467 /* We require that we hit a power of 2 at least half of all evaluations. */ 468 if (simple_cst_equal (op2, value) != 1 || count < wrong_values) 469 return false; 470 471 if (dump_file) 472 { 473 fprintf (dump_file, "Mod power of 2 transformation on insn "); 474 print_generic_stmt (dump_file, stmt, TDF_SLIM); 475 } 476 477 /* Compute probability of taking the optimal path. */ 478 all = count + wrong_values; 479 if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count)) 480 return false; 481 482 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 483 484 result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all); 485 486 TREE_OPERAND (modify, 1) = result; 487 488 return true; 489} 490 491/* Generate code for transformations 3 and 4 (with OPERATION, operands OP1 492 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to 493 support. Currently only NCOUNTS==0 or 1 is supported and this is 494 built into this interface. The probabilities of taking the optimal 495 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and 496 COUNT2/ALL respectively within roundoff error). This generates the 497 result into a temp and returns the temp; it does not replace or alter 498 the original STMT. */ 499/* FIXME: Generalize the interface to handle NCOUNTS > 1. */ 500 501static tree 502tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, 503 int prob1, int prob2, int ncounts, 504 gcov_type count1, gcov_type count2, gcov_type all) 505{ 506 tree stmt1, stmt2, stmt3; 507 tree tmp1; 508 tree label_decl1 = create_artificial_label (); 509 tree label_decl2 = create_artificial_label (); 510 tree label_decl3 = create_artificial_label (); 511 tree label1, label2, label3; 512 tree bb1end, bb2end = NULL_TREE, bb3end; 513 basic_block bb, bb2, bb3, bb4; 514 tree optype = TREE_TYPE (operation); 515 edge e12, e23 = 0, e24, e34, e14; 516 block_stmt_iterator bsi; 517 tree result = create_tmp_var (optype, "PROF"); 518 519 bb = bb_for_stmt (stmt); 520 bsi = bsi_for_stmt (stmt); 521 522 tmp1 = create_tmp_var (optype, "PROF"); 523 stmt1 = build2 (MODIFY_EXPR, optype, result, op1); 524 stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); 525 stmt3 = build3 (COND_EXPR, void_type_node, 526 build2 (LT_EXPR, boolean_type_node, result, tmp1), 527 build1 (GOTO_EXPR, void_type_node, label_decl3), 528 build1 (GOTO_EXPR, void_type_node, 529 ncounts ? label_decl1 : label_decl2)); 530 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 531 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 532 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 533 bb1end = stmt3; 534 535 if (ncounts) /* Assumed to be 0 or 1 */ 536 { 537 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 538 stmt1 = build2 (MODIFY_EXPR, optype, result, 539 build2 (MINUS_EXPR, optype, result, tmp1)); 540 stmt2 = build3 (COND_EXPR, void_type_node, 541 build2 (LT_EXPR, boolean_type_node, result, tmp1), 542 build1 (GOTO_EXPR, void_type_node, label_decl3), 543 build1 (GOTO_EXPR, void_type_node, label_decl2)); 544 bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 545 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 546 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 547 bb2end = stmt2; 548 } 549 550 /* Fallback case. */ 551 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 552 stmt1 = build2 (MODIFY_EXPR, optype, result, 553 build2 (TREE_CODE (operation), optype, result, tmp1)); 554 bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 555 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 556 bb3end = stmt1; 557 558 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 559 bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 560 561 /* Fix CFG. */ 562 /* Edge e23 connects bb2 to bb3, etc. */ 563 /* However block 3 is optional; if it is not there, references 564 to 3 really refer to block 2. */ 565 e12 = split_block (bb, bb1end); 566 bb2 = e12->dest; 567 bb2->count = all - count1; 568 569 if (ncounts) /* Assumed to be 0 or 1. */ 570 { 571 e23 = split_block (bb2, bb2end); 572 bb3 = e23->dest; 573 bb3->count = all - count1 - count2; 574 } 575 576 e34 = split_block (ncounts ? bb3 : bb2, bb3end); 577 bb4 = e34->dest; 578 bb4->count = all; 579 580 e12->flags &= ~EDGE_FALLTHRU; 581 e12->flags |= EDGE_FALSE_VALUE; 582 e12->probability = REG_BR_PROB_BASE - prob1; 583 e12->count = all - count1; 584 585 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE); 586 e14->probability = prob1; 587 e14->count = count1; 588 589 if (ncounts) /* Assumed to be 0 or 1. */ 590 { 591 e23->flags &= ~EDGE_FALLTHRU; 592 e23->flags |= EDGE_FALSE_VALUE; 593 e23->count = all - count1 - count2; 594 e23->probability = REG_BR_PROB_BASE - prob2; 595 596 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE); 597 e24->probability = prob2; 598 e24->count = count2; 599 } 600 601 e34->probability = REG_BR_PROB_BASE; 602 e34->count = all - count1 - count2; 603 604 return result; 605} 606 607/* Do transforms 3) and 4) on INSN if applicable. */ 608static bool 609tree_mod_subtract_transform (tree stmt) 610{ 611 stmt_ann_t ann = get_stmt_ann (stmt); 612 histogram_value histogram; 613 enum tree_code code; 614 gcov_type count, wrong_values, all; 615 tree modify, op, op1, op2, result, value; 616 int prob1, prob2; 617 unsigned int i; 618 619 modify = stmt; 620 if (TREE_CODE (stmt) == RETURN_EXPR 621 && TREE_OPERAND (stmt, 0) 622 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 623 modify = TREE_OPERAND (stmt, 0); 624 if (TREE_CODE (modify) != MODIFY_EXPR) 625 return false; 626 op = TREE_OPERAND (modify, 1); 627 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 628 return false; 629 code = TREE_CODE (op); 630 631 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) 632 return false; 633 634 op1 = TREE_OPERAND (op, 0); 635 op2 = TREE_OPERAND (op, 1); 636 if (!ann->histograms) 637 return false; 638 639 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 640 if (histogram->type == HIST_TYPE_INTERVAL) 641 break; 642 643 if (!histogram) 644 return false; 645 646 value = histogram->hvalue.value; 647 all = 0; 648 wrong_values = 0; 649 for (i = 0; i < histogram->hdata.intvl.steps; i++) 650 all += histogram->hvalue.counters[i]; 651 652 wrong_values += histogram->hvalue.counters[i]; 653 wrong_values += histogram->hvalue.counters[i+1]; 654 all += wrong_values; 655 656 /* Compute probability of taking the optimal path. */ 657 if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count)) 658 return false; 659 660 /* We require that we use just subtractions in at least 50% of all 661 evaluations. */ 662 count = 0; 663 for (i = 0; i < histogram->hdata.intvl.steps; i++) 664 { 665 count += histogram->hvalue.counters[i]; 666 if (count * 2 >= all) 667 break; 668 } 669 if (i == histogram->hdata.intvl.steps) 670 return false; 671 672 if (dump_file) 673 { 674 fprintf (dump_file, "Mod subtract transformation on insn "); 675 print_generic_stmt (dump_file, stmt, TDF_SLIM); 676 } 677 678 /* Compute probability of taking the optimal path(s). */ 679 prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all; 680 prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all; 681 682 /* In practice, "steps" is always 2. This interface reflects this, 683 and will need to be changed if "steps" can change. */ 684 result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i, 685 histogram->hvalue.counters[0], 686 histogram->hvalue.counters[1], all); 687 688 TREE_OPERAND (modify, 1) = result; 689 690 return true; 691} 692 693struct value_prof_hooks { 694 /* Find list of values for which we want to measure histograms. */ 695 void (*find_values_to_profile) (histogram_values *); 696 697 /* Identify and exploit properties of values that are hard to analyze 698 statically. See value-prof.c for more detail. */ 699 bool (*value_profile_transformations) (void); 700}; 701 702/* Find values inside STMT for that we want to measure histograms for 703 division/modulo optimization. */ 704static void 705tree_divmod_values_to_profile (tree stmt, histogram_values *values) 706{ 707 tree assign, lhs, rhs, divisor, op0, type; 708 histogram_value hist; 709 710 if (TREE_CODE (stmt) == RETURN_EXPR) 711 assign = TREE_OPERAND (stmt, 0); 712 else 713 assign = stmt; 714 715 if (!assign 716 || TREE_CODE (assign) != MODIFY_EXPR) 717 return; 718 lhs = TREE_OPERAND (assign, 0); 719 type = TREE_TYPE (lhs); 720 if (!INTEGRAL_TYPE_P (type)) 721 return; 722 723 rhs = TREE_OPERAND (assign, 1); 724 switch (TREE_CODE (rhs)) 725 { 726 case TRUNC_DIV_EXPR: 727 case TRUNC_MOD_EXPR: 728 divisor = TREE_OPERAND (rhs, 1); 729 op0 = TREE_OPERAND (rhs, 0); 730 731 VEC_reserve (histogram_value, heap, *values, 3); 732 733 if (is_gimple_reg (divisor)) 734 { 735 /* Check for the case where the divisor is the same value most 736 of the time. */ 737 hist = ggc_alloc (sizeof (*hist)); 738 hist->hvalue.value = divisor; 739 hist->hvalue.stmt = stmt; 740 hist->type = HIST_TYPE_SINGLE_VALUE; 741 VEC_quick_push (histogram_value, *values, hist); 742 } 743 744 /* For mod, check whether it is not often a noop (or replaceable by 745 a few subtractions). */ 746 if (TREE_CODE (rhs) == TRUNC_MOD_EXPR 747 && TYPE_UNSIGNED (type)) 748 { 749 /* Check for a special case where the divisor is power of 2. */ 750 hist = ggc_alloc (sizeof (*hist)); 751 hist->hvalue.value = divisor; 752 hist->hvalue.stmt = stmt; 753 hist->type = HIST_TYPE_POW2; 754 VEC_quick_push (histogram_value, *values, hist); 755 756 hist = ggc_alloc (sizeof (*hist)); 757 hist->hvalue.stmt = stmt; 758 hist->hvalue.value 759 = build2 (TRUNC_DIV_EXPR, type, op0, divisor); 760 hist->type = HIST_TYPE_INTERVAL; 761 hist->hdata.intvl.int_start = 0; 762 hist->hdata.intvl.steps = 2; 763 VEC_quick_push (histogram_value, *values, hist); 764 } 765 return; 766 767 default: 768 return; 769 } 770} 771 772/* Find values inside STMT for that we want to measure histograms and adds 773 them to list VALUES. */ 774 775static void 776tree_values_to_profile (tree stmt, histogram_values *values) 777{ 778 if (flag_value_profile_transformations) 779 tree_divmod_values_to_profile (stmt, values); 780} 781 782static void 783tree_find_values_to_profile (histogram_values *values) 784{ 785 basic_block bb; 786 block_stmt_iterator bsi; 787 unsigned i; 788 histogram_value hist; 789 790 *values = NULL; 791 FOR_EACH_BB (bb) 792 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 793 tree_values_to_profile (bsi_stmt (bsi), values); 794 795 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++) 796 { 797 switch (hist->type) 798 { 799 case HIST_TYPE_INTERVAL: 800 if (dump_file) 801 { 802 fprintf (dump_file, "Interval counter for tree "); 803 print_generic_expr (dump_file, hist->hvalue.stmt, 804 TDF_SLIM); 805 fprintf (dump_file, ", range %d -- %d.\n", 806 hist->hdata.intvl.int_start, 807 (hist->hdata.intvl.int_start 808 + hist->hdata.intvl.steps - 1)); 809 } 810 hist->n_counters = hist->hdata.intvl.steps + 2; 811 break; 812 813 case HIST_TYPE_POW2: 814 if (dump_file) 815 { 816 fprintf (dump_file, "Pow2 counter for tree "); 817 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 818 fprintf (dump_file, ".\n"); 819 } 820 hist->n_counters = 2; 821 break; 822 823 case HIST_TYPE_SINGLE_VALUE: 824 if (dump_file) 825 { 826 fprintf (dump_file, "Single value counter for tree "); 827 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 828 fprintf (dump_file, ".\n"); 829 } 830 hist->n_counters = 3; 831 break; 832 833 case HIST_TYPE_CONST_DELTA: 834 if (dump_file) 835 { 836 fprintf (dump_file, "Constant delta counter for tree "); 837 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 838 fprintf (dump_file, ".\n"); 839 } 840 hist->n_counters = 4; 841 break; 842 843 default: 844 gcc_unreachable (); 845 } 846 } 847} 848 849static struct value_prof_hooks tree_value_prof_hooks = { 850 tree_find_values_to_profile, 851 tree_value_profile_transformations 852}; 853 854void 855tree_register_value_prof_hooks (void) 856{ 857 value_prof_hooks = &tree_value_prof_hooks; 858 gcc_assert (ir_type ()); 859} 860 861/* IR-independent entry points. */ 862void 863find_values_to_profile (histogram_values *values) 864{ 865 (value_prof_hooks->find_values_to_profile) (values); 866} 867 868bool 869value_profile_transformations (void) 870{ 871 return (value_prof_hooks->value_profile_transformations) (); 872} 873 874 875