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 77static int count_insns (basic_block); 78static bool ignore_bb_p (const_basic_block); 79static bool better_p (const_edge, const_edge); 80static edge find_best_successor (basic_block); 81static edge find_best_predecessor (basic_block); 82static int find_trace (basic_block, basic_block *); 83 84/* Minimal outgoing edge probability considered for superblock formation. */ 85static int probability_cutoff; 86static 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. */ 90sbitmap bb_seen; 91 92static inline void 93mark_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 103static inline bool 104bb_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. */ 110static bool 111ignore_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 131static int 132count_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. */ 147static bool 148better_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 165static edge 166find_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 184static edge 185find_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 205static int 206find_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 247static bool 248tail_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 385namespace { 386 387const 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 400class pass_tracer : public gimple_opt_pass 401{ 402public: 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 417unsigned int 418pass_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 445gimple_opt_pass * 446make_pass_tracer (gcc::context *ctxt) 447{ 448 return new pass_tracer (ctxt); 449} 450