1132718Skan/* Transformations based on profile information for values. 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3132718Skan 4132718SkanThis file is part of GCC. 5132718Skan 6132718SkanGCC is free software; you can redistribute it and/or modify it under 7132718Skanthe terms of the GNU General Public License as published by the Free 8132718SkanSoftware Foundation; either version 2, or (at your option) any later 9132718Skanversion. 10132718Skan 11132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 12132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 13132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14132718Skanfor more details. 15132718Skan 16132718SkanYou should have received a copy of the GNU General Public License 17132718Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20132718Skan 21132718Skan#include "config.h" 22132718Skan#include "system.h" 23132718Skan#include "coretypes.h" 24132718Skan#include "tm.h" 25132718Skan#include "rtl.h" 26132718Skan#include "expr.h" 27132718Skan#include "hard-reg-set.h" 28132718Skan#include "basic-block.h" 29132718Skan#include "value-prof.h" 30132718Skan#include "output.h" 31132718Skan#include "flags.h" 32132718Skan#include "insn-config.h" 33132718Skan#include "recog.h" 34132718Skan#include "optabs.h" 35132718Skan#include "regs.h" 36169689Skan#include "ggc.h" 37169689Skan#include "tree-flow.h" 38169689Skan#include "tree-flow-inline.h" 39169689Skan#include "diagnostic.h" 40169689Skan#include "coverage.h" 41169689Skan#include "tree.h" 42169689Skan#include "gcov-io.h" 43169689Skan#include "timevar.h" 44169689Skan#include "tree-pass.h" 45169689Skan#include "toplev.h" 46132718Skan 47169689Skanstatic struct value_prof_hooks *value_prof_hooks; 48132718Skan 49169689Skan/* In this file value profile based optimizations are placed. Currently the 50169689Skan following optimizations are implemented (for more detailed descriptions 51169689Skan see comments at value_profile_transformations): 52169689Skan 53169689Skan 1) Division/modulo specialization. Provided that we can determine that the 54169689Skan operands of the division have some special properties, we may use it to 55169689Skan produce more effective code. 56169689Skan 2) Speculative prefetching. If we are able to determine that the difference 57169689Skan between addresses accessed by a memory reference is usually constant, we 58169689Skan may add the prefetch instructions. 59169689Skan FIXME: This transformation was removed together with RTL based value 60169689Skan profiling. 61169689Skan 62132718Skan Every such optimization should add its requirements for profiled values to 63132718Skan insn_values_to_profile function. This function is called from branch_prob 64132718Skan in profile.c and the requested values are instrumented by it in the first 65132718Skan compilation with -fprofile-arcs. The optimization may then read the 66132718Skan gathered data in the second compilation with -fbranch-probabilities. 67132718Skan 68169689Skan The measured data is pointed to from the histograms 69169689Skan field of the statement annotation of the instrumented insns. It is 70169689Skan kept as a linked list of struct histogram_value_t's, which contain the 71169689Skan same information as above. */ 72169689Skan 73169689Skan 74169689Skanstatic tree tree_divmod_fixed_value (tree, tree, tree, tree, 75169689Skan tree, int, gcov_type, gcov_type); 76169689Skanstatic tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type); 77169689Skanstatic tree tree_mod_subtract (tree, tree, tree, tree, int, int, int, 78169689Skan gcov_type, gcov_type, gcov_type); 79169689Skanstatic bool tree_divmod_fixed_value_transform (tree); 80169689Skanstatic bool tree_mod_pow2_value_transform (tree); 81169689Skanstatic bool tree_mod_subtract_transform (tree); 82169689Skan 83169689Skan/* The overall number of invocations of the counter should match execution count 84169689Skan of basic block. Report it as error rather than internal error as it might 85169689Skan mean that user has misused the profile somehow. */ 86169689Skanstatic bool 87169689Skancheck_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count) 88132718Skan{ 89169689Skan if (all != bb_count) 90169689Skan { 91169689Skan location_t * locus; 92169689Skan locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt) 93169689Skan ? EXPR_LOCUS (stmt) 94169689Skan : &DECL_SOURCE_LOCATION (current_function_decl)); 95169689Skan error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)", 96169689Skan locus, name, (int)all, (int)bb_count); 97169689Skan return true; 98169689Skan } 99169689Skan return false; 100132718Skan} 101132718Skan 102169689Skan/* Tree based transformations. */ 103169689Skanstatic bool 104169689Skantree_value_profile_transformations (void) 105132718Skan{ 106169689Skan basic_block bb; 107169689Skan block_stmt_iterator bsi; 108169689Skan bool changed = false; 109132718Skan 110169689Skan FOR_EACH_BB (bb) 111132718Skan { 112169689Skan /* Ignore cold areas -- we are enlarging the code. */ 113169689Skan if (!maybe_hot_bb_p (bb)) 114169689Skan continue; 115132718Skan 116169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 117132718Skan { 118169689Skan tree stmt = bsi_stmt (bsi); 119169689Skan stmt_ann_t ann = get_stmt_ann (stmt); 120169689Skan histogram_value th = ann->histograms; 121169689Skan if (!th) 122169689Skan continue; 123132718Skan 124169689Skan if (dump_file) 125169689Skan { 126169689Skan fprintf (dump_file, "Trying transformations on insn "); 127169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 128169689Skan } 129132718Skan 130169689Skan /* Transformations: */ 131169689Skan /* The order of things in this conditional controls which 132169689Skan transformation is used when more than one is applicable. */ 133169689Skan /* It is expected that any code added by the transformations 134169689Skan will be added before the current statement, and that the 135169689Skan current statement remain valid (although possibly 136169689Skan modified) upon return. */ 137169689Skan if (flag_value_profile_transformations 138169689Skan && (tree_mod_subtract_transform (stmt) 139169689Skan || tree_divmod_fixed_value_transform (stmt) 140169689Skan || tree_mod_pow2_value_transform (stmt))) 141169689Skan { 142169689Skan changed = true; 143169689Skan /* Original statement may no longer be in the same block. */ 144169689Skan if (bb != bb_for_stmt (stmt)) 145169689Skan { 146169689Skan bb = bb_for_stmt (stmt); 147169689Skan bsi = bsi_for_stmt (stmt); 148169689Skan } 149169689Skan } 150132718Skan 151169689Skan /* Free extra storage from compute_value_histograms. */ 152169689Skan while (th) 153169689Skan { 154169689Skan free (th->hvalue.counters); 155169689Skan th = th->hvalue.next; 156169689Skan } 157169689Skan ann->histograms = 0; 158169689Skan } 159169689Skan } 160132718Skan 161169689Skan if (changed) 162169689Skan { 163169689Skan counts_to_freqs (); 164132718Skan } 165132718Skan 166169689Skan return changed; 167132718Skan} 168132718Skan 169169689Skan/* Generate code for transformation 1 (with OPERATION, operands OP1 170169689Skan and OP2, whose value is expected to be VALUE, parent modify-expr STMT and 171169689Skan probability of taking the optimal path PROB, which is equivalent to COUNT/ALL 172169689Skan within roundoff error). This generates the result into a temp and returns 173169689Skan the temp; it does not replace or alter the original STMT. */ 174169689Skanstatic tree 175169689Skantree_divmod_fixed_value (tree stmt, tree operation, 176169689Skan tree op1, tree op2, tree value, int prob, gcov_type count, 177169689Skan gcov_type all) 178132718Skan{ 179169689Skan tree stmt1, stmt2, stmt3; 180169689Skan tree tmp1, tmp2, tmpv; 181169689Skan tree label_decl1 = create_artificial_label (); 182169689Skan tree label_decl2 = create_artificial_label (); 183169689Skan tree label_decl3 = create_artificial_label (); 184169689Skan tree label1, label2, label3; 185169689Skan tree bb1end, bb2end, bb3end; 186169689Skan basic_block bb, bb2, bb3, bb4; 187169689Skan tree optype = TREE_TYPE (operation); 188169689Skan edge e12, e13, e23, e24, e34; 189169689Skan block_stmt_iterator bsi; 190132718Skan 191169689Skan bb = bb_for_stmt (stmt); 192169689Skan bsi = bsi_for_stmt (stmt); 193132718Skan 194169689Skan tmpv = create_tmp_var (optype, "PROF"); 195169689Skan tmp1 = create_tmp_var (optype, "PROF"); 196169689Skan stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value)); 197169689Skan stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); 198169689Skan stmt3 = build3 (COND_EXPR, void_type_node, 199169689Skan build2 (NE_EXPR, boolean_type_node, tmp1, tmpv), 200169689Skan build1 (GOTO_EXPR, void_type_node, label_decl2), 201169689Skan build1 (GOTO_EXPR, void_type_node, label_decl1)); 202169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 203169689Skan bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 204169689Skan bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 205169689Skan bb1end = stmt3; 206132718Skan 207169689Skan tmp2 = create_tmp_var (optype, "PROF"); 208169689Skan label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 209169689Skan stmt1 = build2 (MODIFY_EXPR, optype, tmp2, 210169689Skan build2 (TREE_CODE (operation), optype, op1, tmpv)); 211169689Skan bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 212169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 213169689Skan bb2end = stmt1; 214132718Skan 215169689Skan label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 216169689Skan stmt1 = build2 (MODIFY_EXPR, optype, tmp2, 217169689Skan build2 (TREE_CODE (operation), optype, op1, op2)); 218169689Skan bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 219169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 220169689Skan bb3end = stmt1; 221132718Skan 222169689Skan label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 223169689Skan bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 224132718Skan 225169689Skan /* Fix CFG. */ 226169689Skan /* Edge e23 connects bb2 to bb3, etc. */ 227169689Skan e12 = split_block (bb, bb1end); 228169689Skan bb2 = e12->dest; 229169689Skan bb2->count = count; 230169689Skan e23 = split_block (bb2, bb2end); 231169689Skan bb3 = e23->dest; 232169689Skan bb3->count = all - count; 233169689Skan e34 = split_block (bb3, bb3end); 234169689Skan bb4 = e34->dest; 235169689Skan bb4->count = all; 236132718Skan 237169689Skan e12->flags &= ~EDGE_FALLTHRU; 238169689Skan e12->flags |= EDGE_FALSE_VALUE; 239169689Skan e12->probability = prob; 240169689Skan e12->count = count; 241132718Skan 242169689Skan e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 243169689Skan e13->probability = REG_BR_PROB_BASE - prob; 244169689Skan e13->count = all - count; 245132718Skan 246169689Skan remove_edge (e23); 247169689Skan 248169689Skan e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 249169689Skan e24->probability = REG_BR_PROB_BASE; 250169689Skan e24->count = count; 251132718Skan 252169689Skan e34->probability = REG_BR_PROB_BASE; 253169689Skan e34->count = all - count; 254132718Skan 255169689Skan return tmp2; 256169689Skan} 257132718Skan 258169689Skan/* Do transform 1) on INSN if applicable. */ 259169689Skanstatic bool 260169689Skantree_divmod_fixed_value_transform (tree stmt) 261169689Skan{ 262169689Skan stmt_ann_t ann = get_stmt_ann (stmt); 263169689Skan histogram_value histogram; 264169689Skan enum tree_code code; 265169689Skan gcov_type val, count, all; 266169689Skan tree modify, op, op1, op2, result, value, tree_val; 267169689Skan int prob; 268132718Skan 269169689Skan modify = stmt; 270169689Skan if (TREE_CODE (stmt) == RETURN_EXPR 271169689Skan && TREE_OPERAND (stmt, 0) 272169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 273169689Skan modify = TREE_OPERAND (stmt, 0); 274169689Skan if (TREE_CODE (modify) != MODIFY_EXPR) 275169689Skan return false; 276169689Skan op = TREE_OPERAND (modify, 1); 277169689Skan if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 278169689Skan return false; 279169689Skan code = TREE_CODE (op); 280169689Skan 281169689Skan if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) 282169689Skan return false; 283132718Skan 284169689Skan op1 = TREE_OPERAND (op, 0); 285169689Skan op2 = TREE_OPERAND (op, 1); 286169689Skan if (!ann->histograms) 287169689Skan return false; 288132718Skan 289169689Skan for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 290169689Skan if (histogram->type == HIST_TYPE_SINGLE_VALUE) 291169689Skan break; 292132718Skan 293169689Skan if (!histogram) 294169689Skan return false; 295132718Skan 296169689Skan value = histogram->hvalue.value; 297169689Skan val = histogram->hvalue.counters[0]; 298169689Skan count = histogram->hvalue.counters[1]; 299169689Skan all = histogram->hvalue.counters[2]; 300132718Skan 301169689Skan /* We require that count is at least half of all; this means 302169689Skan that for the transformation to fire the value must be constant 303169689Skan at least 50% of time (and 75% gives the guarantee of usage). */ 304169689Skan if (simple_cst_equal (op2, value) != 1 || 2 * count < all) 305169689Skan return false; 306132718Skan 307169689Skan if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count)) 308169689Skan return false; 309132718Skan 310169689Skan /* Compute probability of taking the optimal path. */ 311169689Skan prob = (count * REG_BR_PROB_BASE + all / 2) / all; 312132718Skan 313169689Skan tree_val = build_int_cst_wide (get_gcov_type (), 314169689Skan (unsigned HOST_WIDE_INT) val, 315169689Skan val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); 316169689Skan result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all); 317132718Skan 318169689Skan if (dump_file) 319169689Skan { 320169689Skan fprintf (dump_file, "Div/mod by constant "); 321169689Skan print_generic_expr (dump_file, value, TDF_SLIM); 322169689Skan fprintf (dump_file, "="); 323169689Skan print_generic_expr (dump_file, tree_val, TDF_SLIM); 324169689Skan fprintf (dump_file, " transformation on insn "); 325169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 326169689Skan } 327132718Skan 328169689Skan TREE_OPERAND (modify, 1) = result; 329132718Skan 330169689Skan return true; 331169689Skan} 332132718Skan 333169689Skan/* Generate code for transformation 2 (with OPERATION, operands OP1 334169689Skan and OP2, parent modify-expr STMT and probability of taking the optimal 335169689Skan path PROB, which is equivalent to COUNT/ALL within roundoff error). 336169689Skan This generates the result into a temp and returns 337169689Skan the temp; it does not replace or alter the original STMT. */ 338169689Skanstatic tree 339169689Skantree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, 340169689Skan gcov_type count, gcov_type all) 341132718Skan{ 342169689Skan tree stmt1, stmt2, stmt3, stmt4; 343169689Skan tree tmp2, tmp3; 344169689Skan tree label_decl1 = create_artificial_label (); 345169689Skan tree label_decl2 = create_artificial_label (); 346169689Skan tree label_decl3 = create_artificial_label (); 347169689Skan tree label1, label2, label3; 348169689Skan tree bb1end, bb2end, bb3end; 349169689Skan basic_block bb, bb2, bb3, bb4; 350169689Skan tree optype = TREE_TYPE (operation); 351169689Skan edge e12, e13, e23, e24, e34; 352169689Skan block_stmt_iterator bsi; 353169689Skan tree result = create_tmp_var (optype, "PROF"); 354132718Skan 355169689Skan bb = bb_for_stmt (stmt); 356169689Skan bsi = bsi_for_stmt (stmt); 357132718Skan 358169689Skan tmp2 = create_tmp_var (optype, "PROF"); 359169689Skan tmp3 = create_tmp_var (optype, "PROF"); 360169689Skan stmt2 = build2 (MODIFY_EXPR, optype, tmp2, 361169689Skan build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1))); 362169689Skan stmt3 = build2 (MODIFY_EXPR, optype, tmp3, 363169689Skan build2 (BIT_AND_EXPR, optype, tmp2, op2)); 364169689Skan stmt4 = build3 (COND_EXPR, void_type_node, 365169689Skan build2 (NE_EXPR, boolean_type_node, 366169689Skan tmp3, build_int_cst (optype, 0)), 367169689Skan build1 (GOTO_EXPR, void_type_node, label_decl2), 368169689Skan build1 (GOTO_EXPR, void_type_node, label_decl1)); 369169689Skan bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 370169689Skan bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 371169689Skan bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT); 372169689Skan bb1end = stmt4; 373132718Skan 374169689Skan /* tmp2 == op2-1 inherited from previous block */ 375169689Skan label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 376169689Skan stmt1 = build2 (MODIFY_EXPR, optype, result, 377169689Skan build2 (BIT_AND_EXPR, optype, op1, tmp2)); 378169689Skan bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 379169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 380169689Skan bb2end = stmt1; 381132718Skan 382169689Skan label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 383169689Skan stmt1 = build2 (MODIFY_EXPR, optype, result, 384169689Skan build2 (TREE_CODE (operation), optype, op1, op2)); 385169689Skan bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 386169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 387169689Skan bb3end = stmt1; 388132718Skan 389169689Skan label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 390169689Skan bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 391132718Skan 392169689Skan /* Fix CFG. */ 393169689Skan /* Edge e23 connects bb2 to bb3, etc. */ 394169689Skan e12 = split_block (bb, bb1end); 395169689Skan bb2 = e12->dest; 396169689Skan bb2->count = count; 397169689Skan e23 = split_block (bb2, bb2end); 398169689Skan bb3 = e23->dest; 399169689Skan bb3->count = all - count; 400169689Skan e34 = split_block (bb3, bb3end); 401169689Skan bb4 = e34->dest; 402169689Skan bb4->count = all; 403132718Skan 404169689Skan e12->flags &= ~EDGE_FALLTHRU; 405169689Skan e12->flags |= EDGE_FALSE_VALUE; 406169689Skan e12->probability = prob; 407169689Skan e12->count = count; 408132718Skan 409169689Skan e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 410169689Skan e13->probability = REG_BR_PROB_BASE - prob; 411169689Skan e13->count = all - count; 412132718Skan 413169689Skan remove_edge (e23); 414132718Skan 415169689Skan e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 416169689Skan e24->probability = REG_BR_PROB_BASE; 417169689Skan e24->count = count; 418132718Skan 419169689Skan e34->probability = REG_BR_PROB_BASE; 420169689Skan e34->count = all - count; 421132718Skan 422169689Skan return result; 423132718Skan} 424132718Skan 425169689Skan/* Do transform 2) on INSN if applicable. */ 426132718Skanstatic bool 427169689Skantree_mod_pow2_value_transform (tree stmt) 428132718Skan{ 429169689Skan stmt_ann_t ann = get_stmt_ann (stmt); 430169689Skan histogram_value histogram; 431169689Skan enum tree_code code; 432169689Skan gcov_type count, wrong_values, all; 433169689Skan tree modify, op, op1, op2, result, value; 434169689Skan int prob; 435132718Skan 436169689Skan modify = stmt; 437169689Skan if (TREE_CODE (stmt) == RETURN_EXPR 438169689Skan && TREE_OPERAND (stmt, 0) 439169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 440169689Skan modify = TREE_OPERAND (stmt, 0); 441169689Skan if (TREE_CODE (modify) != MODIFY_EXPR) 442132718Skan return false; 443169689Skan op = TREE_OPERAND (modify, 1); 444169689Skan if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 445169689Skan return false; 446169689Skan code = TREE_CODE (op); 447132718Skan 448169689Skan if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) 449132718Skan return false; 450132718Skan 451169689Skan op1 = TREE_OPERAND (op, 0); 452169689Skan op2 = TREE_OPERAND (op, 1); 453169689Skan if (!ann->histograms) 454169689Skan return false; 455169689Skan 456169689Skan for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 457169689Skan if (histogram->type == HIST_TYPE_POW2) 458132718Skan break; 459132718Skan 460132718Skan if (!histogram) 461132718Skan return false; 462132718Skan 463169689Skan value = histogram->hvalue.value; 464169689Skan wrong_values = histogram->hvalue.counters[0]; 465169689Skan count = histogram->hvalue.counters[1]; 466132718Skan 467169689Skan /* We require that we hit a power of 2 at least half of all evaluations. */ 468169689Skan if (simple_cst_equal (op2, value) != 1 || count < wrong_values) 469132718Skan return false; 470132718Skan 471169689Skan if (dump_file) 472169689Skan { 473169689Skan fprintf (dump_file, "Mod power of 2 transformation on insn "); 474169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 475169689Skan } 476132718Skan 477169689Skan /* Compute probability of taking the optimal path. */ 478169689Skan all = count + wrong_values; 479169689Skan if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count)) 480169689Skan return false; 481132718Skan 482169689Skan prob = (count * REG_BR_PROB_BASE + all / 2) / all; 483169689Skan 484169689Skan result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all); 485169689Skan 486169689Skan TREE_OPERAND (modify, 1) = result; 487169689Skan 488132718Skan return true; 489132718Skan} 490132718Skan 491169689Skan/* Generate code for transformations 3 and 4 (with OPERATION, operands OP1 492169689Skan and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to 493169689Skan support. Currently only NCOUNTS==0 or 1 is supported and this is 494169689Skan built into this interface. The probabilities of taking the optimal 495169689Skan paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and 496169689Skan COUNT2/ALL respectively within roundoff error). This generates the 497169689Skan result into a temp and returns the temp; it does not replace or alter 498169689Skan the original STMT. */ 499169689Skan/* FIXME: Generalize the interface to handle NCOUNTS > 1. */ 500169689Skan 501169689Skanstatic tree 502169689Skantree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, 503169689Skan int prob1, int prob2, int ncounts, 504169689Skan gcov_type count1, gcov_type count2, gcov_type all) 505132718Skan{ 506169689Skan tree stmt1, stmt2, stmt3; 507169689Skan tree tmp1; 508169689Skan tree label_decl1 = create_artificial_label (); 509169689Skan tree label_decl2 = create_artificial_label (); 510169689Skan tree label_decl3 = create_artificial_label (); 511169689Skan tree label1, label2, label3; 512169689Skan tree bb1end, bb2end = NULL_TREE, bb3end; 513169689Skan basic_block bb, bb2, bb3, bb4; 514169689Skan tree optype = TREE_TYPE (operation); 515169689Skan edge e12, e23 = 0, e24, e34, e14; 516169689Skan block_stmt_iterator bsi; 517169689Skan tree result = create_tmp_var (optype, "PROF"); 518132718Skan 519169689Skan bb = bb_for_stmt (stmt); 520169689Skan bsi = bsi_for_stmt (stmt); 521169689Skan 522169689Skan tmp1 = create_tmp_var (optype, "PROF"); 523169689Skan stmt1 = build2 (MODIFY_EXPR, optype, result, op1); 524169689Skan stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); 525169689Skan stmt3 = build3 (COND_EXPR, void_type_node, 526169689Skan build2 (LT_EXPR, boolean_type_node, result, tmp1), 527169689Skan build1 (GOTO_EXPR, void_type_node, label_decl3), 528169689Skan build1 (GOTO_EXPR, void_type_node, 529169689Skan ncounts ? label_decl1 : label_decl2)); 530169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 531169689Skan bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 532169689Skan bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); 533169689Skan bb1end = stmt3; 534169689Skan 535169689Skan if (ncounts) /* Assumed to be 0 or 1 */ 536132718Skan { 537169689Skan label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); 538169689Skan stmt1 = build2 (MODIFY_EXPR, optype, result, 539169689Skan build2 (MINUS_EXPR, optype, result, tmp1)); 540169689Skan stmt2 = build3 (COND_EXPR, void_type_node, 541169689Skan build2 (LT_EXPR, boolean_type_node, result, tmp1), 542169689Skan build1 (GOTO_EXPR, void_type_node, label_decl3), 543169689Skan build1 (GOTO_EXPR, void_type_node, label_decl2)); 544169689Skan bsi_insert_before (&bsi, label1, BSI_SAME_STMT); 545169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 546169689Skan bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); 547169689Skan bb2end = stmt2; 548132718Skan } 549132718Skan 550169689Skan /* Fallback case. */ 551169689Skan label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); 552169689Skan stmt1 = build2 (MODIFY_EXPR, optype, result, 553169689Skan build2 (TREE_CODE (operation), optype, result, tmp1)); 554169689Skan bsi_insert_before (&bsi, label2, BSI_SAME_STMT); 555169689Skan bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); 556169689Skan bb3end = stmt1; 557132718Skan 558169689Skan label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); 559169689Skan bsi_insert_before (&bsi, label3, BSI_SAME_STMT); 560132718Skan 561169689Skan /* Fix CFG. */ 562169689Skan /* Edge e23 connects bb2 to bb3, etc. */ 563169689Skan /* However block 3 is optional; if it is not there, references 564169689Skan to 3 really refer to block 2. */ 565169689Skan e12 = split_block (bb, bb1end); 566169689Skan bb2 = e12->dest; 567169689Skan bb2->count = all - count1; 568169689Skan 569169689Skan if (ncounts) /* Assumed to be 0 or 1. */ 570169689Skan { 571169689Skan e23 = split_block (bb2, bb2end); 572169689Skan bb3 = e23->dest; 573169689Skan bb3->count = all - count1 - count2; 574169689Skan } 575169689Skan 576169689Skan e34 = split_block (ncounts ? bb3 : bb2, bb3end); 577169689Skan bb4 = e34->dest; 578169689Skan bb4->count = all; 579169689Skan 580169689Skan e12->flags &= ~EDGE_FALLTHRU; 581169689Skan e12->flags |= EDGE_FALSE_VALUE; 582169689Skan e12->probability = REG_BR_PROB_BASE - prob1; 583169689Skan e12->count = all - count1; 584169689Skan 585169689Skan e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE); 586169689Skan e14->probability = prob1; 587169689Skan e14->count = count1; 588169689Skan 589169689Skan if (ncounts) /* Assumed to be 0 or 1. */ 590169689Skan { 591169689Skan e23->flags &= ~EDGE_FALLTHRU; 592169689Skan e23->flags |= EDGE_FALSE_VALUE; 593169689Skan e23->count = all - count1 - count2; 594169689Skan e23->probability = REG_BR_PROB_BASE - prob2; 595169689Skan 596169689Skan e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE); 597169689Skan e24->probability = prob2; 598169689Skan e24->count = count2; 599169689Skan } 600169689Skan 601169689Skan e34->probability = REG_BR_PROB_BASE; 602169689Skan e34->count = all - count1 - count2; 603169689Skan 604169689Skan return result; 605132718Skan} 606132718Skan 607169689Skan/* Do transforms 3) and 4) on INSN if applicable. */ 608132718Skanstatic bool 609169689Skantree_mod_subtract_transform (tree stmt) 610132718Skan{ 611169689Skan stmt_ann_t ann = get_stmt_ann (stmt); 612169689Skan histogram_value histogram; 613169689Skan enum tree_code code; 614169689Skan gcov_type count, wrong_values, all; 615169689Skan tree modify, op, op1, op2, result, value; 616169689Skan int prob1, prob2; 617169689Skan unsigned int i; 618132718Skan 619169689Skan modify = stmt; 620169689Skan if (TREE_CODE (stmt) == RETURN_EXPR 621169689Skan && TREE_OPERAND (stmt, 0) 622169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 623169689Skan modify = TREE_OPERAND (stmt, 0); 624169689Skan if (TREE_CODE (modify) != MODIFY_EXPR) 625132718Skan return false; 626169689Skan op = TREE_OPERAND (modify, 1); 627169689Skan if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) 628169689Skan return false; 629169689Skan code = TREE_CODE (op); 630132718Skan 631169689Skan if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) 632132718Skan return false; 633132718Skan 634169689Skan op1 = TREE_OPERAND (op, 0); 635169689Skan op2 = TREE_OPERAND (op, 1); 636169689Skan if (!ann->histograms) 637169689Skan return false; 638169689Skan 639169689Skan for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) 640169689Skan if (histogram->type == HIST_TYPE_INTERVAL) 641132718Skan break; 642132718Skan 643132718Skan if (!histogram) 644132718Skan return false; 645132718Skan 646169689Skan value = histogram->hvalue.value; 647169689Skan all = 0; 648169689Skan wrong_values = 0; 649169689Skan for (i = 0; i < histogram->hdata.intvl.steps; i++) 650169689Skan all += histogram->hvalue.counters[i]; 651132718Skan 652169689Skan wrong_values += histogram->hvalue.counters[i]; 653169689Skan wrong_values += histogram->hvalue.counters[i+1]; 654169689Skan all += wrong_values; 655169689Skan 656169689Skan /* Compute probability of taking the optimal path. */ 657169689Skan if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count)) 658169689Skan return false; 659169689Skan 660169689Skan /* We require that we use just subtractions in at least 50% of all 661169689Skan evaluations. */ 662132718Skan count = 0; 663169689Skan for (i = 0; i < histogram->hdata.intvl.steps; i++) 664132718Skan { 665169689Skan count += histogram->hvalue.counters[i]; 666169689Skan if (count * 2 >= all) 667169689Skan break; 668132718Skan } 669169689Skan if (i == histogram->hdata.intvl.steps) 670132718Skan return false; 671132718Skan 672169689Skan if (dump_file) 673169689Skan { 674169689Skan fprintf (dump_file, "Mod subtract transformation on insn "); 675169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 676169689Skan } 677132718Skan 678169689Skan /* Compute probability of taking the optimal path(s). */ 679169689Skan prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all; 680169689Skan prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all; 681132718Skan 682169689Skan /* In practice, "steps" is always 2. This interface reflects this, 683169689Skan and will need to be changed if "steps" can change. */ 684169689Skan result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i, 685169689Skan histogram->hvalue.counters[0], 686169689Skan histogram->hvalue.counters[1], all); 687132718Skan 688169689Skan TREE_OPERAND (modify, 1) = result; 689169689Skan 690132718Skan return true; 691132718Skan} 692132718Skan 693169689Skanstruct value_prof_hooks { 694169689Skan /* Find list of values for which we want to measure histograms. */ 695169689Skan void (*find_values_to_profile) (histogram_values *); 696169689Skan 697169689Skan /* Identify and exploit properties of values that are hard to analyze 698169689Skan statically. See value-prof.c for more detail. */ 699169689Skan bool (*value_profile_transformations) (void); 700169689Skan}; 701169689Skan 702169689Skan/* Find values inside STMT for that we want to measure histograms for 703169689Skan division/modulo optimization. */ 704169689Skanstatic void 705169689Skantree_divmod_values_to_profile (tree stmt, histogram_values *values) 706132718Skan{ 707169689Skan tree assign, lhs, rhs, divisor, op0, type; 708169689Skan histogram_value hist; 709132718Skan 710169689Skan if (TREE_CODE (stmt) == RETURN_EXPR) 711169689Skan assign = TREE_OPERAND (stmt, 0); 712132718Skan else 713169689Skan assign = stmt; 714132718Skan 715169689Skan if (!assign 716169689Skan || TREE_CODE (assign) != MODIFY_EXPR) 717169689Skan return; 718169689Skan lhs = TREE_OPERAND (assign, 0); 719169689Skan type = TREE_TYPE (lhs); 720169689Skan if (!INTEGRAL_TYPE_P (type)) 721169689Skan return; 722132718Skan 723169689Skan rhs = TREE_OPERAND (assign, 1); 724169689Skan switch (TREE_CODE (rhs)) 725132718Skan { 726169689Skan case TRUNC_DIV_EXPR: 727169689Skan case TRUNC_MOD_EXPR: 728169689Skan divisor = TREE_OPERAND (rhs, 1); 729169689Skan op0 = TREE_OPERAND (rhs, 0); 730169689Skan 731169689Skan VEC_reserve (histogram_value, heap, *values, 3); 732169689Skan 733169689Skan if (is_gimple_reg (divisor)) 734169689Skan { 735169689Skan /* Check for the case where the divisor is the same value most 736169689Skan of the time. */ 737169689Skan hist = ggc_alloc (sizeof (*hist)); 738169689Skan hist->hvalue.value = divisor; 739169689Skan hist->hvalue.stmt = stmt; 740169689Skan hist->type = HIST_TYPE_SINGLE_VALUE; 741169689Skan VEC_quick_push (histogram_value, *values, hist); 742169689Skan } 743169689Skan 744169689Skan /* For mod, check whether it is not often a noop (or replaceable by 745169689Skan a few subtractions). */ 746169689Skan if (TREE_CODE (rhs) == TRUNC_MOD_EXPR 747169689Skan && TYPE_UNSIGNED (type)) 748169689Skan { 749169689Skan /* Check for a special case where the divisor is power of 2. */ 750169689Skan hist = ggc_alloc (sizeof (*hist)); 751169689Skan hist->hvalue.value = divisor; 752169689Skan hist->hvalue.stmt = stmt; 753169689Skan hist->type = HIST_TYPE_POW2; 754169689Skan VEC_quick_push (histogram_value, *values, hist); 755169689Skan 756169689Skan hist = ggc_alloc (sizeof (*hist)); 757169689Skan hist->hvalue.stmt = stmt; 758169689Skan hist->hvalue.value 759169689Skan = build2 (TRUNC_DIV_EXPR, type, op0, divisor); 760169689Skan hist->type = HIST_TYPE_INTERVAL; 761169689Skan hist->hdata.intvl.int_start = 0; 762169689Skan hist->hdata.intvl.steps = 2; 763169689Skan VEC_quick_push (histogram_value, *values, hist); 764169689Skan } 765169689Skan return; 766169689Skan 767169689Skan default: 768169689Skan return; 769132718Skan } 770169689Skan} 771132718Skan 772169689Skan/* Find values inside STMT for that we want to measure histograms and adds 773169689Skan them to list VALUES. */ 774132718Skan 775169689Skanstatic void 776169689Skantree_values_to_profile (tree stmt, histogram_values *values) 777169689Skan{ 778169689Skan if (flag_value_profile_transformations) 779169689Skan tree_divmod_values_to_profile (stmt, values); 780132718Skan} 781132718Skan 782169689Skanstatic void 783169689Skantree_find_values_to_profile (histogram_values *values) 784132718Skan{ 785169689Skan basic_block bb; 786169689Skan block_stmt_iterator bsi; 787169689Skan unsigned i; 788169689Skan histogram_value hist; 789132718Skan 790169689Skan *values = NULL; 791169689Skan FOR_EACH_BB (bb) 792169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 793169689Skan tree_values_to_profile (bsi_stmt (bsi), values); 794132718Skan 795169689Skan for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++) 796169689Skan { 797169689Skan switch (hist->type) 798169689Skan { 799169689Skan case HIST_TYPE_INTERVAL: 800169689Skan if (dump_file) 801169689Skan { 802169689Skan fprintf (dump_file, "Interval counter for tree "); 803169689Skan print_generic_expr (dump_file, hist->hvalue.stmt, 804169689Skan TDF_SLIM); 805169689Skan fprintf (dump_file, ", range %d -- %d.\n", 806169689Skan hist->hdata.intvl.int_start, 807169689Skan (hist->hdata.intvl.int_start 808169689Skan + hist->hdata.intvl.steps - 1)); 809169689Skan } 810169689Skan hist->n_counters = hist->hdata.intvl.steps + 2; 811169689Skan break; 812132718Skan 813169689Skan case HIST_TYPE_POW2: 814169689Skan if (dump_file) 815169689Skan { 816169689Skan fprintf (dump_file, "Pow2 counter for tree "); 817169689Skan print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 818169689Skan fprintf (dump_file, ".\n"); 819169689Skan } 820169689Skan hist->n_counters = 2; 821169689Skan break; 822132718Skan 823169689Skan case HIST_TYPE_SINGLE_VALUE: 824169689Skan if (dump_file) 825169689Skan { 826169689Skan fprintf (dump_file, "Single value counter for tree "); 827169689Skan print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 828169689Skan fprintf (dump_file, ".\n"); 829169689Skan } 830169689Skan hist->n_counters = 3; 831169689Skan break; 832132718Skan 833169689Skan case HIST_TYPE_CONST_DELTA: 834169689Skan if (dump_file) 835169689Skan { 836169689Skan fprintf (dump_file, "Constant delta counter for tree "); 837169689Skan print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); 838169689Skan fprintf (dump_file, ".\n"); 839169689Skan } 840169689Skan hist->n_counters = 4; 841169689Skan break; 842132718Skan 843169689Skan default: 844169689Skan gcc_unreachable (); 845169689Skan } 846132718Skan } 847169689Skan} 848132718Skan 849169689Skanstatic struct value_prof_hooks tree_value_prof_hooks = { 850169689Skan tree_find_values_to_profile, 851169689Skan tree_value_profile_transformations 852169689Skan}; 853132718Skan 854169689Skanvoid 855169689Skantree_register_value_prof_hooks (void) 856169689Skan{ 857169689Skan value_prof_hooks = &tree_value_prof_hooks; 858169689Skan gcc_assert (ir_type ()); 859169689Skan} 860169689Skan 861169689Skan/* IR-independent entry points. */ 862169689Skanvoid 863169689Skanfind_values_to_profile (histogram_values *values) 864169689Skan{ 865169689Skan (value_prof_hooks->find_values_to_profile) (values); 866169689Skan} 867132718Skan 868169689Skanbool 869169689Skanvalue_profile_transformations (void) 870169689Skan{ 871169689Skan return (value_prof_hooks->value_profile_transformations) (); 872169689Skan} 873169689Skan 874132718Skan 875