gcc/tracer.c

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