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