1 /* The tracer pass for the GNU compiler. 2 Contributed by Jan Hubicka, SuSE Labs. 3 Adapted to work on GIMPLE instead of RTL by Robert Kidd, UIUC. 4 Copyright (C) 2001-2015 Free Software Foundation, Inc. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it 9 under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 16 License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* This pass performs the tail duplication needed for superblock formation. 23 For more information see: 24 25 Design and Analysis of Profile-Based Optimization in Compaq's 26 Compilation Tools for Alpha; Journal of Instruction-Level 27 Parallelism 3 (2000) 1-25 28 29 Unlike Compaq's implementation we don't do the loop peeling as most 30 probably a better job can be done by a special pass and we don't 31 need to worry too much about the code size implications as the tail 32 duplicates are crossjumped again if optimizations are not 33 performed. */ 34 35 36 #include "config.h" 37 #include "system.h" 38 #include "coretypes.h" 39 #include "tm.h" 40 #include "hash-set.h" 41 #include "machmode.h" 42 #include "vec.h" 43 #include "double-int.h" 44 #include "input.h" 45 #include "alias.h" 46 #include "symtab.h" 47 #include "wide-int.h" 48 #include "inchash.h" 49 #include "tree.h" 50 #include "fold-const.h" 51 #include "rtl.h" 52 #include "hard-reg-set.h" 53 #include "profile.h" 54 #include "predict.h" 55 #include "input.h" 56 #include "function.h" 57 #include "dominance.h" 58 #include "cfg.h" 59 #include "cfganal.h" 60 #include "basic-block.h" 61 #include "flags.h" 62 #include "params.h" 63 #include "coverage.h" 64 #include "tree-pass.h" 65 #include "tree-ssa-alias.h" 66 #include "internal-fn.h" 67 #include "gimple-expr.h" 68 #include "is-a.h" 69 #include "gimple.h" 70 #include "gimple-iterator.h" 71 #include "tree-cfg.h" 72 #include "tree-ssa.h" 73 #include "tree-inline.h" 74 #include "cfgloop.h" 75 #include "fibonacci_heap.h" 76 77 static int count_insns (basic_block); 78 static bool ignore_bb_p (const_basic_block); 79 static bool better_p (const_edge, const_edge); 80 static edge find_best_successor (basic_block); 81 static edge find_best_predecessor (basic_block); 82 static int find_trace (basic_block, basic_block *); 83 84 /* Minimal outgoing edge probability considered for superblock formation. */ 85 static int probability_cutoff; 86 static int branch_ratio_cutoff; 87 88 /* A bit BB->index is set if BB has already been seen, i.e. it is 89 connected to some trace already. */ 90 sbitmap bb_seen; 91 92 static inline void 93 mark_bb_seen (basic_block bb) 94 { 95 unsigned int size = SBITMAP_SIZE (bb_seen); 96 97 if ((unsigned int)bb->index >= size) 98 bb_seen = sbitmap_resize (bb_seen, size * 2, 0); 99 100 bitmap_set_bit (bb_seen, bb->index); 101 } 102 103 static inline bool 104 bb_seen_p (basic_block bb) 105 { 106 return bitmap_bit_p (bb_seen, bb->index); 107 } 108 109 /* Return true if we should ignore the basic block for purposes of tracing. */ 110 static bool 111 ignore_bb_p (const_basic_block bb) 112 { 113 gimple g; 114 115 if (bb->index < NUM_FIXED_BLOCKS) 116 return true; 117 if (optimize_bb_for_size_p (bb)) 118 return true; 119 120 /* A transaction is a single entry multiple exit region. It must be 121 duplicated in its entirety or not at all. */ 122 g = last_stmt (CONST_CAST_BB (bb)); 123 if (g && gimple_code (g) == GIMPLE_TRANSACTION) 124 return true; 125 126 return false; 127 } 128 129 /* Return number of instructions in the block. */ 130 131 static int 132 count_insns (basic_block bb) 133 { 134 gimple_stmt_iterator gsi; 135 gimple stmt; 136 int n = 0; 137 138 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 139 { 140 stmt = gsi_stmt (gsi); 141 n += estimate_num_insns (stmt, &eni_size_weights); 142 } 143 return n; 144 } 145 146 /* Return true if E1 is more frequent than E2. */ 147 static bool 148 better_p (const_edge e1, const_edge e2) 149 { 150 if (e1->count != e2->count) 151 return e1->count > e2->count; 152 if (e1->src->frequency * e1->probability != 153 e2->src->frequency * e2->probability) 154 return (e1->src->frequency * e1->probability 155 > e2->src->frequency * e2->probability); 156 /* This is needed to avoid changes in the decision after 157 CFG is modified. */ 158 if (e1->src != e2->src) 159 return e1->src->index > e2->src->index; 160 return e1->dest->index > e2->dest->index; 161 } 162 163 /* Return most frequent successor of basic block BB. */ 164 165 static edge 166 find_best_successor (basic_block bb) 167 { 168 edge e; 169 edge best = NULL; 170 edge_iterator ei; 171 172 FOR_EACH_EDGE (e, ei, bb->succs) 173 if (!best || better_p (e, best)) 174 best = e; 175 if (!best || ignore_bb_p (best->dest)) 176 return NULL; 177 if (best->probability <= probability_cutoff) 178 return NULL; 179 return best; 180 } 181 182 /* Return most frequent predecessor of basic block BB. */ 183 184 static edge 185 find_best_predecessor (basic_block bb) 186 { 187 edge e; 188 edge best = NULL; 189 edge_iterator ei; 190 191 FOR_EACH_EDGE (e, ei, bb->preds) 192 if (!best || better_p (e, best)) 193 best = e; 194 if (!best || ignore_bb_p (best->src)) 195 return NULL; 196 if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE 197 < bb->frequency * branch_ratio_cutoff) 198 return NULL; 199 return best; 200 } 201 202 /* Find the trace using bb and record it in the TRACE array. 203 Return number of basic blocks recorded. */ 204 205 static int 206 find_trace (basic_block bb, basic_block *trace) 207 { 208 int i = 0; 209 edge e; 210 211 if (dump_file) 212 fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency); 213 214 while ((e = find_best_predecessor (bb)) != NULL) 215 { 216 basic_block bb2 = e->src; 217 if (bb_seen_p (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 218 || find_best_successor (bb2) != e) 219 break; 220 if (dump_file) 221 fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency); 222 bb = bb2; 223 } 224 if (dump_file) 225 fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency); 226 trace[i++] = bb; 227 228 /* Follow the trace in forward direction. */ 229 while ((e = find_best_successor (bb)) != NULL) 230 { 231 bb = e->dest; 232 if (bb_seen_p (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 233 || find_best_predecessor (bb) != e) 234 break; 235 if (dump_file) 236 fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency); 237 trace[i++] = bb; 238 } 239 if (dump_file) 240 fprintf (dump_file, "\n"); 241 return i; 242 } 243 244 /* Look for basic blocks in frequency order, construct traces and tail duplicate 245 if profitable. */ 246 247 static bool 248 tail_duplicate (void) 249 { 250 auto_vec<fibonacci_node<long, basic_block_def>*> blocks; 251 blocks.safe_grow_cleared (last_basic_block_for_fn (cfun)); 252 253 basic_block *trace = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); 254 int *counts = XNEWVEC (int, last_basic_block_for_fn (cfun)); 255 int ninsns = 0, nduplicated = 0; 256 gcov_type weighted_insns = 0, traced_insns = 0; 257 fibonacci_heap<long, basic_block_def> heap (LONG_MIN); 258 gcov_type cover_insns; 259 int max_dup_insns; 260 basic_block bb; 261 bool changed = false; 262 263 /* Create an oversized sbitmap to reduce the chance that we need to 264 resize it. */ 265 bb_seen = sbitmap_alloc (last_basic_block_for_fn (cfun) * 2); 266 bitmap_clear (bb_seen); 267 initialize_original_copy_tables (); 268 269 if (profile_info && flag_branch_probabilities) 270 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK); 271 else 272 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY); 273 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff; 274 275 branch_ratio_cutoff = 276 (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO)); 277 278 FOR_EACH_BB_FN (bb, cfun) 279 { 280 int n = count_insns (bb); 281 if (!ignore_bb_p (bb)) 282 blocks[bb->index] = heap.insert (-bb->frequency, bb); 283 284 counts [bb->index] = n; 285 ninsns += n; 286 weighted_insns += n * bb->frequency; 287 } 288 289 if (profile_info && flag_branch_probabilities) 290 cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK); 291 else 292 cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE); 293 cover_insns = (weighted_insns * cover_insns + 50) / 100; 294 max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100; 295 296 while (traced_insns < cover_insns && nduplicated < max_dup_insns 297 && !heap.empty ()) 298 { 299 basic_block bb = heap.extract_min (); 300 int n, pos; 301 302 if (!bb) 303 break; 304 305 blocks[bb->index] = NULL; 306 307 if (ignore_bb_p (bb)) 308 continue; 309 gcc_assert (!bb_seen_p (bb)); 310 311 n = find_trace (bb, trace); 312 313 bb = trace[0]; 314 traced_insns += bb->frequency * counts [bb->index]; 315 if (blocks[bb->index]) 316 { 317 heap.delete_node (blocks[bb->index]); 318 blocks[bb->index] = NULL; 319 } 320 321 for (pos = 1; pos < n; pos++) 322 { 323 basic_block bb2 = trace[pos]; 324 325 if (blocks[bb2->index]) 326 { 327 heap.delete_node (blocks[bb2->index]); 328 blocks[bb2->index] = NULL; 329 } 330 traced_insns += bb2->frequency * counts [bb2->index]; 331 if (EDGE_COUNT (bb2->preds) > 1 332 && can_duplicate_block_p (bb2) 333 /* We have the tendency to duplicate the loop header 334 of all do { } while loops. Do not do that - it is 335 not profitable and it might create a loop with multiple 336 entries or at least rotate the loop. */ 337 && bb2->loop_father->header != bb2) 338 { 339 edge e; 340 basic_block copy; 341 342 nduplicated += counts [bb2->index]; 343 344 e = find_edge (bb, bb2); 345 346 copy = duplicate_block (bb2, e, bb); 347 flush_pending_stmts (e); 348 349 add_phi_args_after_copy (©, 1, NULL); 350 351 /* Reconsider the original copy of block we've duplicated. 352 Removing the most common predecessor may make it to be 353 head. */ 354 blocks[bb2->index] = heap.insert (-bb2->frequency, bb2); 355 356 if (dump_file) 357 fprintf (dump_file, "Duplicated %i as %i [%i]\n", 358 bb2->index, copy->index, copy->frequency); 359 360 bb2 = copy; 361 changed = true; 362 } 363 mark_bb_seen (bb2); 364 bb = bb2; 365 /* In case the trace became infrequent, stop duplicating. */ 366 if (ignore_bb_p (bb)) 367 break; 368 } 369 if (dump_file) 370 fprintf (dump_file, " covered now %.1f\n\n", 371 traced_insns * 100.0 / weighted_insns); 372 } 373 if (dump_file) 374 fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated, 375 nduplicated * 100 / ninsns); 376 377 free_original_copy_tables (); 378 sbitmap_free (bb_seen); 379 free (trace); 380 free (counts); 381 382 return changed; 383 } 384 385 namespace { 386 387 const pass_data pass_data_tracer = 388 { 389 GIMPLE_PASS, /* type */ 390 "tracer", /* name */ 391 OPTGROUP_NONE, /* optinfo_flags */ 392 TV_TRACER, /* tv_id */ 393 0, /* properties_required */ 394 0, /* properties_provided */ 395 0, /* properties_destroyed */ 396 0, /* todo_flags_start */ 397 TODO_update_ssa, /* todo_flags_finish */ 398 }; 399 400 class pass_tracer : public gimple_opt_pass 401 { 402 public: 403 pass_tracer (gcc::context *ctxt) 404 : gimple_opt_pass (pass_data_tracer, ctxt) 405 {} 406 407 /* opt_pass methods: */ 408 virtual bool gate (function *) 409 { 410 return (optimize > 0 && flag_tracer && flag_reorder_blocks); 411 } 412 413 virtual unsigned int execute (function *); 414 415 }; // class pass_tracer 416 417 unsigned int 418 pass_tracer::execute (function *fun) 419 { 420 bool changed; 421 422 if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1) 423 return 0; 424 425 mark_dfs_back_edges (); 426 if (dump_file) 427 brief_dump_cfg (dump_file, dump_flags); 428 429 /* Trace formation is done on the fly inside tail_duplicate */ 430 changed = tail_duplicate (); 431 if (changed) 432 { 433 free_dominance_info (CDI_DOMINATORS); 434 /* If we changed the CFG schedule loops for fixup by cleanup_cfg. */ 435 loops_state_set (LOOPS_NEED_FIXUP); 436 } 437 438 if (dump_file) 439 brief_dump_cfg (dump_file, dump_flags); 440 441 return changed ? TODO_cleanup_cfg : 0; 442 } 443 } // anon namespace 444 445 gimple_opt_pass * 446 make_pass_tracer (gcc::context *ctxt) 447 { 448 return new pass_tracer (ctxt); 449 } 450