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 bb = bb_for_stmt (stmt); 145 } 146 147 /* Free extra storage from compute_value_histograms. */ 148 while (th) 149 { 150 free (th->hvalue.counters); 151 th = th->hvalue.next; 152 } 153 ann->histograms = 0; 154 } 155 } 156 157 if (changed) 158 { 159 counts_to_freqs (); 160 } 161 162 return changed; 163} 164 165/* Generate code for transformation 1 (with OPERATION, operands OP1 166 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and 167 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL 168 within roundoff error). This generates the result into a temp and returns 169 the temp; it does not replace or alter the original STMT. */ 170static tree 171tree_divmod_fixed_value (tree stmt, tree operation, 172 tree op1, tree op2, tree value, int prob, gcov_type count, 173 gcov_type all) 174{ 175 tree stmt1, stmt2, stmt3; 176 tree tmp1, tmp2, tmpv; 177 tree label_decl1 = create_artificial_label (); 178 tree label_decl2 = create_artificial_label (); 179 tree label_decl3 = create_artificial_label (); 180 tree label1, label2, label3; 181 tree bb1end, bb2end, bb3end; 182 basic_block bb, bb2, bb3, bb4; 183 tree optype = TREE_TYPE (operation); 184 edge e12, e13, e23, e24, e34; 185 block_stmt_iterator bsi; 186 187 bb = bb_for_stmt (stmt); 188 bsi = bsi_for_stmt (stmt); 189 190 tmpv = create_tmp_var (optype, "PROF"); 191 tmp1 = create_tmp_var (optype, "PROF"); 192 stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value)); 193 stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); 194 stmt3 = build3 (COND_EXPR, void_type_node, 195 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv), 196 build1 (GOTO_EXPR, void_type_node, label_decl2), 197 build1 (GOTO_EXPR, void_type_node, label_decl1)); 198 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 199 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 200 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 201 bb1end = stmt3; 202 203 tmp2 = create_tmp_var (optype, "PROF"); 204 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 205 stmt1 = build2 (MODIFY_EXPR, optype, tmp2, 206 build2 (TREE_CODE (operation), optype, op1, tmpv)); 207 bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 208 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 209 bb2end = stmt1; 210 211 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 212 stmt1 = build2 (MODIFY_EXPR, optype, tmp2, 213 build2 (TREE_CODE (operation), optype, op1, op2)); 214 bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 215 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 216 bb3end = stmt1; 217 218 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 219 bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 220 221 /* Fix CFG. */ 222 /* Edge e23 connects bb2 to bb3, etc. */ 223 e12 = split_block (bb, bb1end); 224 bb2 = e12->dest; 225 bb2->count = count; 226 e23 = split_block (bb2, bb2end); 227 bb3 = e23->dest; 228 bb3->count = all - count; 229 e34 = split_block (bb3, bb3end); 230 bb4 = e34->dest; 231 bb4->count = all; 232 233 e12->flags &= ~EDGE_FALLTHRU; 234 e12->flags |= EDGE_FALSE_VALUE; 235 e12->probability = prob; 236 e12->count = count; 237 238 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 239 e13->probability = REG_BR_PROB_BASE - prob; 240 e13->count = all - count; 241 242 remove_edge (e23); 243 244 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 245 e24->probability = REG_BR_PROB_BASE; 246 e24->count = count; 247 248 e34->probability = REG_BR_PROB_BASE; 249 e34->count = all - count; 250 251 return tmp2; 252} 253 254/* Do transform 1) on INSN if applicable. */ 255static bool 256tree_divmod_fixed_value_transform (tree stmt) 257{ 258 stmt_ann_t ann = get_stmt_ann (stmt); 259 histogram_value histogram; 260 enum tree_code code; 261 gcov_type val, count, all; 262 tree modify, op, op1, op2, result, value, tree_val; 263 int prob; 264 265 modify = stmt; 266 if (TREE_CODE (stmt) == RETURN_EXPR 267 && TREE_OPERAND (stmt, 0) 268 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 269 modify = TREE_OPERAND (stmt, 0); 270 if (TREE_CODE (modify) != MODIFY_EXPR) 271 return false; 272 op = TREE_OPERAND (modify, 1); 273 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 274 return false; 275 code = TREE_CODE (op); 276 277 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) 278 return false; 279 280 op1 = TREE_OPERAND (op, 0); 281 op2 = TREE_OPERAND (op, 1); 282 if (!ann->histograms) 283 return false; 284 285 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 286 if (histogram->type == HIST_TYPE_SINGLE_VALUE) 287 break; 288 289 if (!histogram) 290 return false; 291 292 value = histogram->hvalue.value; 293 val = histogram->hvalue.counters[0]; 294 count = histogram->hvalue.counters[1]; 295 all = histogram->hvalue.counters[2]; 296 297 /* We require that count is at least half of all; this means 298 that for the transformation to fire the value must be constant 299 at least 50% of time (and 75% gives the guarantee of usage). */ 300 if (simple_cst_equal (op2, value) != 1 || 2 * count < all) 301 return false; 302 303 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count)) 304 return false; 305 306 /* Compute probability of taking the optimal path. */ 307 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 308 309 tree_val = build_int_cst_wide (get_gcov_type (), 310 (unsigned HOST_WIDE_INT) val, 311 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); 312 result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all); 313 314 if (dump_file) 315 { 316 fprintf (dump_file, "Div/mod by constant "); 317 print_generic_expr (dump_file, value, TDF_SLIM); 318 fprintf (dump_file, "="); 319 print_generic_expr (dump_file, tree_val, TDF_SLIM); 320 fprintf (dump_file, " transformation on insn "); 321 print_generic_stmt (dump_file, stmt, TDF_SLIM); 322 } 323 324 TREE_OPERAND (modify, 1) = result; 325 326 return true; 327} 328 329/* Generate code for transformation 2 (with OPERATION, operands OP1 330 and OP2, parent modify-expr STMT and probability of taking the optimal 331 path PROB, which is equivalent to COUNT/ALL within roundoff error). 332 This generates the result into a temp and returns 333 the temp; it does not replace or alter the original STMT. */ 334static tree 335tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, 336 gcov_type count, gcov_type all) 337{ 338 tree stmt1, stmt2, stmt3, stmt4; 339 tree tmp1, tmp2, tmp3; 340 tree label_decl1 = create_artificial_label (); 341 tree label_decl2 = create_artificial_label (); 342 tree label_decl3 = create_artificial_label (); 343 tree label1, label2, label3; 344 tree bb1end, bb2end, bb3end; 345 basic_block bb, bb2, bb3, bb4; 346 tree optype = TREE_TYPE (operation); 347 edge e12, e13, e23, e24, e34; 348 block_stmt_iterator bsi; 349 tree result = create_tmp_var (optype, "PROF"); 350 351 bb = bb_for_stmt (stmt); 352 bsi = bsi_for_stmt (stmt); 353 354 tmp1 = create_tmp_var (optype, "PROF"); 355 tmp2 = create_tmp_var (optype, "PROF"); 356 tmp3 = create_tmp_var (optype, "PROF"); 357 stmt1 = build2 (MODIFY_EXPR, optype, tmp1, fold_convert (optype, op2)); 358 stmt2 = build2 (MODIFY_EXPR, optype, tmp2, 359 build2 (PLUS_EXPR, optype, op2, integer_minus_one_node)); 360 stmt3 = build2 (MODIFY_EXPR, optype, tmp3, 361 build2 (BIT_AND_EXPR, optype, tmp2, tmp1)); 362 stmt4 = build3 (COND_EXPR, void_type_node, 363 build2 (NE_EXPR, boolean_type_node, tmp3, integer_zero_node), 364 build1 (GOTO_EXPR, void_type_node, label_decl2), 365 build1 (GOTO_EXPR, void_type_node, label_decl1)); 366 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 367 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 368 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 369 bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT); 370 bb1end = stmt4; 371 372 /* tmp2 == op2-1 inherited from previous block */ 373 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 374 stmt1 = build2 (MODIFY_EXPR, optype, result, 375 build2 (BIT_AND_EXPR, optype, op1, tmp2)); 376 bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 377 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 378 bb2end = stmt1; 379 380 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 381 stmt1 = build2 (MODIFY_EXPR, optype, result, 382 build2 (TREE_CODE (operation), optype, op1, op2)); 383 bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 384 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 385 bb3end = stmt1; 386 387 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 388 bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 389 390 /* Fix CFG. */ 391 /* Edge e23 connects bb2 to bb3, etc. */ 392 e12 = split_block (bb, bb1end); 393 bb2 = e12->dest; 394 bb2->count = count; 395 e23 = split_block (bb2, bb2end); 396 bb3 = e23->dest; 397 bb3->count = all - count; 398 e34 = split_block (bb3, bb3end); 399 bb4 = e34->dest; 400 bb4->count = all; 401 402 e12->flags &= ~EDGE_FALLTHRU; 403 e12->flags |= EDGE_FALSE_VALUE; 404 e12->probability = prob; 405 e12->count = count; 406 407 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 408 e13->probability = REG_BR_PROB_BASE - prob; 409 e13->count = all - count; 410 411 remove_edge (e23); 412 413 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 414 e24->probability = REG_BR_PROB_BASE; 415 e24->count = count; 416 417 e34->probability = REG_BR_PROB_BASE; 418 e34->count = all - count; 419 420 return result; 421} 422 423/* Do transform 2) on INSN if applicable. */ 424static bool 425tree_mod_pow2_value_transform (tree stmt) 426{ 427 stmt_ann_t ann = get_stmt_ann (stmt); 428 histogram_value histogram; 429 enum tree_code code; 430 gcov_type count, wrong_values, all; 431 tree modify, op, op1, op2, result, value; 432 int prob; 433 434 modify = stmt; 435 if (TREE_CODE (stmt) == RETURN_EXPR 436 && TREE_OPERAND (stmt, 0) 437 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 438 modify = TREE_OPERAND (stmt, 0); 439 if (TREE_CODE (modify) != MODIFY_EXPR) 440 return false; 441 op = TREE_OPERAND (modify, 1); 442 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 443 return false; 444 code = TREE_CODE (op); 445 446 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) 447 return false; 448 449 op1 = TREE_OPERAND (op, 0); 450 op2 = TREE_OPERAND (op, 1); 451 if (!ann->histograms) 452 return false; 453 454 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 455 if (histogram->type == HIST_TYPE_POW2) 456 break; 457 458 if (!histogram) 459 return false; 460 461 value = histogram->hvalue.value; 462 wrong_values = histogram->hvalue.counters[0]; 463 count = histogram->hvalue.counters[1]; 464 465 /* We require that we hit a power of 2 at least half of all evaluations. */ 466 if (simple_cst_equal (op2, value) != 1 || count < wrong_values) 467 return false; 468 469 if (dump_file) 470 { 471 fprintf (dump_file, "Mod power of 2 transformation on insn "); 472 print_generic_stmt (dump_file, stmt, TDF_SLIM); 473 } 474 475 /* Compute probability of taking the optimal path. */ 476 all = count + wrong_values; 477 if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count)) 478 return false; 479 480 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 481 482 result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all); 483 484 TREE_OPERAND (modify, 1) = result; 485 486 return true; 487} 488 489/* Generate code for transformations 3 and 4 (with OPERATION, operands OP1 490 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to 491 support. Currently only NCOUNTS==0 or 1 is supported and this is 492 built into this interface. The probabilities of taking the optimal 493 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and 494 COUNT2/ALL respectively within roundoff error). This generates the 495 result into a temp and returns the temp; it does not replace or alter 496 the original STMT. */ 497/* FIXME: Generalize the interface to handle NCOUNTS > 1. */ 498 499static tree 500tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, 501 int prob1, int prob2, int ncounts, 502 gcov_type count1, gcov_type count2, gcov_type all) 503{ 504 tree stmt1, stmt2, stmt3; 505 tree tmp1; 506 tree label_decl1 = create_artificial_label (); 507 tree label_decl2 = create_artificial_label (); 508 tree label_decl3 = create_artificial_label (); 509 tree label1, label2, label3; 510 tree bb1end, bb2end = NULL_TREE, bb3end; 511 basic_block bb, bb2, bb3, bb4; 512 tree optype = TREE_TYPE (operation); 513 edge e12, e23 = 0, e24, e34, e14; 514 block_stmt_iterator bsi; 515 tree result = create_tmp_var (optype, "PROF"); 516 517 bb = bb_for_stmt (stmt); 518 bsi = bsi_for_stmt (stmt); 519 520 tmp1 = create_tmp_var (optype, "PROF"); 521 stmt1 = build2 (MODIFY_EXPR, optype, result, op1); 522 stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); 523 stmt3 = build3 (COND_EXPR, void_type_node, 524 build2 (LT_EXPR, boolean_type_node, result, tmp1), 525 build1 (GOTO_EXPR, void_type_node, label_decl3), 526 build1 (GOTO_EXPR, void_type_node, 527 ncounts ? label_decl1 : label_decl2)); 528 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 529 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 530 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 531 bb1end = stmt3; 532 533 if (ncounts) /* Assumed to be 0 or 1 */ 534 { 535 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 536 stmt1 = build2 (MODIFY_EXPR, optype, result, 537 build2 (MINUS_EXPR, optype, result, tmp1)); 538 stmt2 = build3 (COND_EXPR, void_type_node, 539 build2 (LT_EXPR, boolean_type_node, result, tmp1), 540 build1 (GOTO_EXPR, void_type_node, label_decl3), 541 build1 (GOTO_EXPR, void_type_node, label_decl2)); 542 bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 543 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 544 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 545 bb2end = stmt2; 546 } 547 548 /* Fallback case. */ 549 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 550 stmt1 = build2 (MODIFY_EXPR, optype, result, 551 build2 (TREE_CODE (operation), optype, result, tmp1)); 552 bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 553 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 554 bb3end = stmt1; 555 556 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 557 bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 558 559 /* Fix CFG. */ 560 /* Edge e23 connects bb2 to bb3, etc. */ 561 /* However block 3 is optional; if it is not there, references 562 to 3 really refer to block 2. */ 563 e12 = split_block (bb, bb1end); 564 bb2 = e12->dest; 565 bb2->count = all - count1; 566 567 if (ncounts) /* Assumed to be 0 or 1. */ 568 { 569 e23 = split_block (bb2, bb2end); 570 bb3 = e23->dest; 571 bb3->count = all - count1 - count2; 572 } 573 574 e34 = split_block (ncounts ? bb3 : bb2, bb3end); 575 bb4 = e34->dest; 576 bb4->count = all; 577 578 e12->flags &= ~EDGE_FALLTHRU; 579 e12->flags |= EDGE_FALSE_VALUE; 580 e12->probability = REG_BR_PROB_BASE - prob1; 581 e12->count = all - count1; 582 583 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE); 584 e14->probability = prob1; 585 e14->count = count1; 586 587 if (ncounts) /* Assumed to be 0 or 1. */ 588 { 589 e23->flags &= ~EDGE_FALLTHRU; 590 e23->flags |= EDGE_FALSE_VALUE; 591 e23->count = all - count1 - count2; 592 e23->probability = REG_BR_PROB_BASE - prob2; 593 594 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE); 595 e24->probability = prob2; 596 e24->count = count2; 597 } 598 599 e34->probability = REG_BR_PROB_BASE; 600 e34->count = all - count1 - count2; 601 602 return result; 603} 604 605/* Do transforms 3) and 4) on INSN if applicable. */ 606static bool 607tree_mod_subtract_transform (tree stmt) 608{ 609 stmt_ann_t ann = get_stmt_ann (stmt); 610 histogram_value histogram; 611 enum tree_code code; 612 gcov_type count, wrong_values, all; 613 tree modify, op, op1, op2, result, value; 614 int prob1, prob2; 615 unsigned int i; 616 617 modify = stmt; 618 if (TREE_CODE (stmt) == RETURN_EXPR 619 && TREE_OPERAND (stmt, 0) 620 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 621 modify = TREE_OPERAND (stmt, 0); 622 if (TREE_CODE (modify) != MODIFY_EXPR) 623 return false; 624 op = TREE_OPERAND (modify, 1); 625 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 626 return false; 627 code = TREE_CODE (op); 628 629 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) 630 return false; 631 632 op1 = TREE_OPERAND (op, 0); 633 op2 = TREE_OPERAND (op, 1); 634 if (!ann->histograms) 635 return false; 636 637 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 638 if (histogram->type == HIST_TYPE_INTERVAL) 639 break; 640 641 if (!histogram) 642 return false; 643 644 value = histogram->hvalue.value; 645 all = 0; 646 wrong_values = 0; 647 for (i = 0; i < histogram->hdata.intvl.steps; i++) 648 all += histogram->hvalue.counters[i]; 649 650 wrong_values += histogram->hvalue.counters[i]; 651 wrong_values += histogram->hvalue.counters[i+1]; 652 all += wrong_values; 653 654 /* Compute probability of taking the optimal path. */ 655 if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count)) 656 return false; 657 658 /* We require that we use just subtractions in at least 50% of all 659 evaluations. */ 660 count = 0; 661 for (i = 0; i < histogram->hdata.intvl.steps; i++) 662 { 663 count += histogram->hvalue.counters[i]; 664 if (count * 2 >= all) 665 break; 666 } 667 if (i == histogram->hdata.intvl.steps) 668 return false; 669 670 if (dump_file) 671 { 672 fprintf (dump_file, "Mod subtract transformation on insn "); 673 print_generic_stmt (dump_file, stmt, TDF_SLIM); 674 } 675 676 /* Compute probability of taking the optimal path(s). */ 677 prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all; 678 prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all; 679 680 /* In practice, "steps" is always 2. This interface reflects this, 681 and will need to be changed if "steps" can change. */ 682 result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i, 683 histogram->hvalue.counters[0], 684 histogram->hvalue.counters[1], all); 685 686 TREE_OPERAND (modify, 1) = result; 687 688 return true; 689} 690 691struct value_prof_hooks { 692 /* Find list of values for which we want to measure histograms. */ 693 void (*find_values_to_profile) (histogram_values *); 694 695 /* Identify and exploit properties of values that are hard to analyze 696 statically. See value-prof.c for more detail. */ 697 bool (*value_profile_transformations) (void); 698}; 699 700/* Find values inside STMT for that we want to measure histograms for 701 division/modulo optimization. */ 702static void 703tree_divmod_values_to_profile (tree stmt, histogram_values *values) 704{ 705 tree assign, lhs, rhs, divisor, op0, type; 706 histogram_value hist; 707 708 if (TREE_CODE (stmt) == RETURN_EXPR) 709 assign = TREE_OPERAND (stmt, 0); 710 else 711 assign = stmt; 712 713 if (!assign 714 || TREE_CODE (assign) != MODIFY_EXPR) 715 return; 716 lhs = TREE_OPERAND (assign, 0); 717 type = TREE_TYPE (lhs); 718 if (!INTEGRAL_TYPE_P (type)) 719 return; 720 721 rhs = TREE_OPERAND (assign, 1); 722 switch (TREE_CODE (rhs)) 723 { 724 case TRUNC_DIV_EXPR: 725 case TRUNC_MOD_EXPR: 726 divisor = TREE_OPERAND (rhs, 1); 727 op0 = TREE_OPERAND (rhs, 0); 728 729 VEC_reserve (histogram_value, heap, *values, 3); 730 731 if (is_gimple_reg (divisor)) 732 { 733 /* Check for the case where the divisor is the same value most 734 of the time. */ 735 hist = ggc_alloc (sizeof (*hist)); 736 hist->hvalue.value = divisor; 737 hist->hvalue.stmt = stmt; 738 hist->type = HIST_TYPE_SINGLE_VALUE; 739 VEC_quick_push (histogram_value, *values, hist); 740 } 741 742 /* For mod, check whether it is not often a noop (or replaceable by 743 a few subtractions). */ 744 if (TREE_CODE (rhs) == TRUNC_MOD_EXPR 745 && TYPE_UNSIGNED (type)) 746 { 747 /* Check for a special case where the divisor is power of 2. */ 748 hist = ggc_alloc (sizeof (*hist)); 749 hist->hvalue.value = divisor; 750 hist->hvalue.stmt = stmt; 751 hist->type = HIST_TYPE_POW2; 752 VEC_quick_push (histogram_value, *values, hist); 753 754 hist = ggc_alloc (sizeof (*hist)); 755 hist->hvalue.stmt = stmt; 756 hist->hvalue.value 757 = build2 (TRUNC_DIV_EXPR, type, op0, divisor); 758 hist->type = HIST_TYPE_INTERVAL; 759 hist->hdata.intvl.int_start = 0; 760 hist->hdata.intvl.steps = 2; 761 VEC_quick_push (histogram_value, *values, hist); 762 } 763 return; 764 765 default: 766 return; 767 } 768} 769 770/* Find values inside STMT for that we want to measure histograms and adds 771 them to list VALUES. */ 772 773static void 774tree_values_to_profile (tree stmt, histogram_values *values) 775{ 776 if (flag_value_profile_transformations) 777 tree_divmod_values_to_profile (stmt, values); 778} 779 780static void 781tree_find_values_to_profile (histogram_values *values) 782{ 783 basic_block bb; 784 block_stmt_iterator bsi; 785 unsigned i; 786 histogram_value hist; 787 788 *values = NULL; 789 FOR_EACH_BB (bb) 790 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 791 tree_values_to_profile (bsi_stmt (bsi), values); 792 793 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++) 794 { 795 switch (hist->type) 796 { 797 case HIST_TYPE_INTERVAL: 798 if (dump_file) 799 { 800 fprintf (dump_file, "Interval counter for tree "); 801 print_generic_expr (dump_file, hist->hvalue.stmt, 802 TDF_SLIM); 803 fprintf (dump_file, ", range %d -- %d.\n", 804 hist->hdata.intvl.int_start, 805 (hist->hdata.intvl.int_start 806 + hist->hdata.intvl.steps - 1)); 807 } 808 hist->n_counters = hist->hdata.intvl.steps + 2; 809 break; 810 811 case HIST_TYPE_POW2: 812 if (dump_file) 813 { 814 fprintf (dump_file, "Pow2 counter for tree "); 815 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 816 fprintf (dump_file, ".\n"); 817 } 818 hist->n_counters = 2; 819 break; 820 821 case HIST_TYPE_SINGLE_VALUE: 822 if (dump_file) 823 { 824 fprintf (dump_file, "Single value counter for tree "); 825 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 826 fprintf (dump_file, ".\n"); 827 } 828 hist->n_counters = 3; 829 break; 830 831 case HIST_TYPE_CONST_DELTA: 832 if (dump_file) 833 { 834 fprintf (dump_file, "Constant delta counter for tree "); 835 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 836 fprintf (dump_file, ".\n"); 837 } 838 hist->n_counters = 4; 839 break; 840 841 default: 842 gcc_unreachable (); 843 } 844 } 845} 846 847static struct value_prof_hooks tree_value_prof_hooks = { 848 tree_find_values_to_profile, 849 tree_value_profile_transformations 850}; 851 852void 853tree_register_value_prof_hooks (void) 854{ 855 value_prof_hooks = &tree_value_prof_hooks; 856 gcc_assert (ir_type ()); 857} 858 859/* IR-independent entry points. */ 860void 861find_values_to_profile (histogram_values *values) 862{ 863 (value_prof_hooks->find_values_to_profile) (values); 864} 865 866bool 867value_profile_transformations (void) 868{ 869 return (value_prof_hooks->value_profile_transformations) (); 870} 871 872 873