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-2018 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 "backend.h" 40 #include "rtl.h" 41 #include "tree.h" 42 #include "gimple.h" 43 #include "cfghooks.h" 44 #include "tree-pass.h" 45 #include "profile.h" 46 #include "cfganal.h" 47 #include "params.h" 48 #include "gimple-iterator.h" 49 #include "tree-cfg.h" 50 #include "tree-ssa.h" 51 #include "tree-inline.h" 52 #include "cfgloop.h" 53 #include "fibonacci_heap.h" 54 #include "tracer.h" 55 56 static int count_insns (basic_block); 57 static bool better_p (const_edge, const_edge); 58 static edge find_best_successor (basic_block); 59 static edge find_best_predecessor (basic_block); 60 static int find_trace (basic_block, basic_block *); 61 62 /* Minimal outgoing edge probability considered for superblock formation. */ 63 static int probability_cutoff; 64 static int branch_ratio_cutoff; 65 66 /* A bit BB->index is set if BB has already been seen, i.e. it is 67 connected to some trace already. */ 68 static sbitmap bb_seen; 69 70 static inline void 71 mark_bb_seen (basic_block bb) 72 { 73 unsigned int size = SBITMAP_SIZE (bb_seen); 74 75 if ((unsigned int)bb->index >= size) 76 bb_seen = sbitmap_resize (bb_seen, size * 2, 0); 77 78 bitmap_set_bit (bb_seen, bb->index); 79 } 80 81 static inline bool 82 bb_seen_p (basic_block bb) 83 { 84 return bitmap_bit_p (bb_seen, bb->index); 85 } 86 87 /* Return true if we should ignore the basic block for purposes of tracing. */ 88 bool 89 ignore_bb_p (const_basic_block bb) 90 { 91 if (bb->index < NUM_FIXED_BLOCKS) 92 return true; 93 if (optimize_bb_for_size_p (bb)) 94 return true; 95 96 if (gimple *g = last_stmt (CONST_CAST_BB (bb))) 97 { 98 /* A transaction is a single entry multiple exit region. It 99 must be duplicated in its entirety or not at all. */ 100 if (gimple_code (g) == GIMPLE_TRANSACTION) 101 return true; 102 103 /* An IFN_UNIQUE call must be duplicated as part of its group, 104 or not at all. */ 105 if (is_gimple_call (g) 106 && gimple_call_internal_p (g) 107 && gimple_call_internal_unique_p (g)) 108 return true; 109 } 110 111 return false; 112 } 113 114 /* Return number of instructions in the block. */ 115 116 static int 117 count_insns (basic_block bb) 118 { 119 gimple_stmt_iterator gsi; 120 gimple *stmt; 121 int n = 0; 122 123 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 124 { 125 stmt = gsi_stmt (gsi); 126 n += estimate_num_insns (stmt, &eni_size_weights); 127 } 128 return n; 129 } 130 131 /* Return true if E1 is more frequent than E2. */ 132 static bool 133 better_p (const_edge e1, const_edge e2) 134 { 135 if (e1->count ().initialized_p () && e2->count ().initialized_p () 136 && ((e1->count () > e2->count ()) || (e1->count () < e2->count ()))) 137 return e1->count () > e2->count (); 138 /* This is needed to avoid changes in the decision after 139 CFG is modified. */ 140 if (e1->src != e2->src) 141 return e1->src->index > e2->src->index; 142 return e1->dest->index > e2->dest->index; 143 } 144 145 /* Return most frequent successor of basic block BB. */ 146 147 static edge 148 find_best_successor (basic_block bb) 149 { 150 edge e; 151 edge best = NULL; 152 edge_iterator ei; 153 154 FOR_EACH_EDGE (e, ei, bb->succs) 155 if (!best || better_p (e, best)) 156 best = e; 157 if (!best || ignore_bb_p (best->dest)) 158 return NULL; 159 if (best->probability.initialized_p () 160 && best->probability.to_reg_br_prob_base () <= probability_cutoff) 161 return NULL; 162 return best; 163 } 164 165 /* Return most frequent predecessor of basic block BB. */ 166 167 static edge 168 find_best_predecessor (basic_block bb) 169 { 170 edge e; 171 edge best = NULL; 172 edge_iterator ei; 173 174 FOR_EACH_EDGE (e, ei, bb->preds) 175 if (!best || better_p (e, best)) 176 best = e; 177 if (!best || ignore_bb_p (best->src)) 178 return NULL; 179 if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE 180 < bb->count.to_frequency (cfun) * branch_ratio_cutoff) 181 return NULL; 182 return best; 183 } 184 185 /* Find the trace using bb and record it in the TRACE array. 186 Return number of basic blocks recorded. */ 187 188 static int 189 find_trace (basic_block bb, basic_block *trace) 190 { 191 int i = 0; 192 edge e; 193 194 if (dump_file) 195 fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->count.to_frequency (cfun)); 196 197 while ((e = find_best_predecessor (bb)) != NULL) 198 { 199 basic_block bb2 = e->src; 200 if (bb_seen_p (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 201 || find_best_successor (bb2) != e) 202 break; 203 if (dump_file) 204 fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun)); 205 bb = bb2; 206 } 207 if (dump_file) 208 fprintf (dump_file, " forward %i [%i]", bb->index, bb->count.to_frequency (cfun)); 209 trace[i++] = bb; 210 211 /* Follow the trace in forward direction. */ 212 while ((e = find_best_successor (bb)) != NULL) 213 { 214 bb = e->dest; 215 if (bb_seen_p (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 216 || find_best_predecessor (bb) != e) 217 break; 218 if (dump_file) 219 fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun)); 220 trace[i++] = bb; 221 } 222 if (dump_file) 223 fprintf (dump_file, "\n"); 224 return i; 225 } 226 227 /* Duplicate block BB2, placing it after BB in the CFG. Return the 228 newly created block. */ 229 basic_block 230 transform_duplicate (basic_block bb, basic_block bb2) 231 { 232 edge e; 233 basic_block copy; 234 235 e = find_edge (bb, bb2); 236 237 copy = duplicate_block (bb2, e, bb); 238 flush_pending_stmts (e); 239 240 add_phi_args_after_copy (©, 1, NULL); 241 242 return (copy); 243 } 244 245 /* Look for basic blocks in frequency order, construct traces and tail duplicate 246 if profitable. */ 247 248 static bool 249 tail_duplicate (void) 250 { 251 auto_vec<fibonacci_node<long, basic_block_def>*> blocks; 252 blocks.safe_grow_cleared (last_basic_block_for_fn (cfun)); 253 254 basic_block *trace = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); 255 int *counts = XNEWVEC (int, last_basic_block_for_fn (cfun)); 256 int ninsns = 0, nduplicated = 0; 257 gcov_type weighted_insns = 0, traced_insns = 0; 258 fibonacci_heap<long, basic_block_def> heap (LONG_MIN); 259 gcov_type cover_insns; 260 int max_dup_insns; 261 basic_block bb; 262 bool changed = false; 263 264 /* Create an oversized sbitmap to reduce the chance that we need to 265 resize it. */ 266 bb_seen = sbitmap_alloc (last_basic_block_for_fn (cfun) * 2); 267 bitmap_clear (bb_seen); 268 initialize_original_copy_tables (); 269 270 if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ) 271 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK); 272 else 273 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY); 274 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff; 275 276 branch_ratio_cutoff = 277 (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO)); 278 279 FOR_EACH_BB_FN (bb, cfun) 280 { 281 int n = count_insns (bb); 282 if (!ignore_bb_p (bb)) 283 blocks[bb->index] = heap.insert (-bb->count.to_frequency (cfun), bb); 284 285 counts [bb->index] = n; 286 ninsns += n; 287 weighted_insns += n * bb->count.to_frequency (cfun); 288 } 289 290 if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ) 291 cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK); 292 else 293 cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE); 294 cover_insns = (weighted_insns * cover_insns + 50) / 100; 295 max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100; 296 297 while (traced_insns < cover_insns && nduplicated < max_dup_insns 298 && !heap.empty ()) 299 { 300 basic_block bb = heap.extract_min (); 301 int n, pos; 302 303 if (!bb) 304 break; 305 306 blocks[bb->index] = NULL; 307 308 if (ignore_bb_p (bb)) 309 continue; 310 gcc_assert (!bb_seen_p (bb)); 311 312 n = find_trace (bb, trace); 313 314 bb = trace[0]; 315 traced_insns += bb->count.to_frequency (cfun) * counts [bb->index]; 316 if (blocks[bb->index]) 317 { 318 heap.delete_node (blocks[bb->index]); 319 blocks[bb->index] = NULL; 320 } 321 322 for (pos = 1; pos < n; pos++) 323 { 324 basic_block bb2 = trace[pos]; 325 326 if (blocks[bb2->index]) 327 { 328 heap.delete_node (blocks[bb2->index]); 329 blocks[bb2->index] = NULL; 330 } 331 traced_insns += bb2->count.to_frequency (cfun) * counts [bb2->index]; 332 if (EDGE_COUNT (bb2->preds) > 1 333 && can_duplicate_block_p (bb2) 334 /* We have the tendency to duplicate the loop header 335 of all do { } while loops. Do not do that - it is 336 not profitable and it might create a loop with multiple 337 entries or at least rotate the loop. */ 338 && bb2->loop_father->header != bb2) 339 { 340 nduplicated += counts [bb2->index]; 341 basic_block copy = transform_duplicate (bb, bb2); 342 343 /* Reconsider the original copy of block we've duplicated. 344 Removing the most common predecessor may make it to be 345 head. */ 346 blocks[bb2->index] = heap.insert (-bb2->count.to_frequency (cfun), bb2); 347 348 if (dump_file) 349 fprintf (dump_file, "Duplicated %i as %i [%i]\n", 350 bb2->index, copy->index, copy->count.to_frequency (cfun)); 351 352 bb2 = copy; 353 changed = true; 354 } 355 mark_bb_seen (bb2); 356 bb = bb2; 357 /* In case the trace became infrequent, stop duplicating. */ 358 if (ignore_bb_p (bb)) 359 break; 360 } 361 if (dump_file) 362 fprintf (dump_file, " covered now %.1f\n\n", 363 traced_insns * 100.0 / weighted_insns); 364 } 365 if (dump_file) 366 fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated, 367 nduplicated * 100 / ninsns); 368 369 free_original_copy_tables (); 370 sbitmap_free (bb_seen); 371 free (trace); 372 free (counts); 373 374 return changed; 375 } 376 377 namespace { 378 379 const pass_data pass_data_tracer = 380 { 381 GIMPLE_PASS, /* type */ 382 "tracer", /* name */ 383 OPTGROUP_NONE, /* optinfo_flags */ 384 TV_TRACER, /* tv_id */ 385 0, /* properties_required */ 386 0, /* properties_provided */ 387 0, /* properties_destroyed */ 388 0, /* todo_flags_start */ 389 TODO_update_ssa, /* todo_flags_finish */ 390 }; 391 392 class pass_tracer : public gimple_opt_pass 393 { 394 public: 395 pass_tracer (gcc::context *ctxt) 396 : gimple_opt_pass (pass_data_tracer, ctxt) 397 {} 398 399 /* opt_pass methods: */ 400 virtual bool gate (function *) 401 { 402 return (optimize > 0 && flag_tracer && flag_reorder_blocks); 403 } 404 405 virtual unsigned int execute (function *); 406 407 }; // class pass_tracer 408 409 unsigned int 410 pass_tracer::execute (function *fun) 411 { 412 bool changed; 413 414 if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1) 415 return 0; 416 417 mark_dfs_back_edges (); 418 if (dump_file) 419 brief_dump_cfg (dump_file, dump_flags); 420 421 /* Trace formation is done on the fly inside tail_duplicate */ 422 changed = tail_duplicate (); 423 if (changed) 424 { 425 free_dominance_info (CDI_DOMINATORS); 426 /* If we changed the CFG schedule loops for fixup by cleanup_cfg. */ 427 loops_state_set (LOOPS_NEED_FIXUP); 428 } 429 430 if (dump_file) 431 brief_dump_cfg (dump_file, dump_flags); 432 433 return changed ? TODO_cleanup_cfg : 0; 434 } 435 } // anon namespace 436 437 gimple_opt_pass * 438 make_pass_tracer (gcc::context *ctxt) 439 { 440 return new pass_tracer (ctxt); 441 } 442