gcc/tracer.c

   1 /* The tracer pass for the GNU compiler.
   2    Contributed by Jan Hubicka, SuSE Labs.
   3    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4    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 2, 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 COPYING.  If not, write to the Free
  20    Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.  */
  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 "output.h"
  46 #include "cfglayout.h"
  47 #include "fibheap.h"
  48 #include "flags.h"
  49 #include "timevar.h"
  50 #include "params.h"
  51 #include "coverage.h"
  52 #include "tree-pass.h"
  53
  54 static int count_insns (basic_block);
  55 static bool ignore_bb_p (basic_block);
  56 static bool better_p (edge, 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 static void tail_duplicate (void);
  61 static void layout_superblocks (void);
  62
  63 /* Minimal outgoing edge probability considered for superblock formation.  */
  64 static int probability_cutoff;
  65 static int branch_ratio_cutoff;
  66
  67 /* Return true if BB has been seen - it is connected to some trace
  68    already.  */
  69
  70 #define seen(bb) (bb->il.rtl->visited || bb->aux)
  71
  72 /* Return true if we should ignore the basic block for purposes of tracing.  */
  73 static bool
  74 ignore_bb_p (basic_block bb)
  75 {
  76   if (bb->index < NUM_FIXED_BLOCKS)
  77     return true;
  78   if (!maybe_hot_bb_p (bb))
  79     return true;
  80   return false;
  81 }
  82
  83 /* Return number of instructions in the block.  */
  84
  85 static int
  86 count_insns (basic_block bb)
  87 {
  88   rtx insn;
  89   int n = 0;
  90
  91   for (insn = BB_HEAD (bb);
  92        insn != NEXT_INSN (BB_END (bb));
  93        insn = NEXT_INSN (insn))
  94     if (active_insn_p (insn))
  95       n++;
  96   return n;
  97 }
  98
  99 /* Return true if E1 is more frequent than E2.  */
 100 static bool
 101 better_p (edge e1, edge e2)
 102 {
 103   if (e1->count != e2->count)
 104     return e1->count > e2->count;
 105   if (e1->src->frequency * e1->probability !=
 106       e2->src->frequency * e2->probability)
 107     return (e1->src->frequency * e1->probability
 108             > e2->src->frequency * e2->probability);
 109   /* This is needed to avoid changes in the decision after
 110      CFG is modified.  */
 111   if (e1->src != e2->src)
 112     return e1->src->index > e2->src->index;
 113   return e1->dest->index > e2->dest->index;
 114 }
 115
 116 /* Return most frequent successor of basic block BB.  */
 117
 118 static edge
 119 find_best_successor (basic_block bb)
 120 {
 121   edge e;
 122   edge best = NULL;
 123   edge_iterator ei;
 124
 125   FOR_EACH_EDGE (e, ei, bb->succs)
 126     if (!best || better_p (e, best))
 127       best = e;
 128   if (!best || ignore_bb_p (best->dest))
 129     return NULL;
 130   if (best->probability <= probability_cutoff)
 131     return NULL;
 132   return best;
 133 }
 134
 135 /* Return most frequent predecessor of basic block BB.  */
 136
 137 static edge
 138 find_best_predecessor (basic_block bb)
 139 {
 140   edge e;
 141   edge best = NULL;
 142   edge_iterator ei;
 143
 144   FOR_EACH_EDGE (e, ei, bb->preds)
 145     if (!best || better_p (e, best))
 146       best = e;
 147   if (!best || ignore_bb_p (best->src))
 148     return NULL;
 149   if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
 150       < bb->frequency * branch_ratio_cutoff)
 151     return NULL;
 152   return best;
 153 }
 154
 155 /* Find the trace using bb and record it in the TRACE array.
 156    Return number of basic blocks recorded.  */
 157
 158 static int
 159 find_trace (basic_block bb, basic_block *trace)
 160 {
 161   int i = 0;
 162   edge e;
 163
 164   if (dump_file)
 165     fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
 166
 167   while ((e = find_best_predecessor (bb)) != NULL)
 168     {
 169       basic_block bb2 = e->src;
 170       if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 171           || find_best_successor (bb2) != e)
 172         break;
 173       if (dump_file)
 174         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
 175       bb = bb2;
 176     }
 177   if (dump_file)
 178     fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
 179   trace[i++] = bb;
 180
 181   /* Follow the trace in forward direction.  */
 182   while ((e = find_best_successor (bb)) != NULL)
 183     {
 184       bb = e->dest;
 185       if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 186           || find_best_predecessor (bb) != e)
 187         break;
 188       if (dump_file)
 189         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
 190       trace[i++] = bb;
 191     }
 192   if (dump_file)
 193     fprintf (dump_file, "\n");
 194   return i;
 195 }
 196
 197 /* Look for basic blocks in frequency order, construct traces and tail duplicate
 198    if profitable.  */
 199
 200 static void
 201 tail_duplicate (void)
 202 {
 203   fibnode_t *blocks = XCNEWVEC (fibnode_t, last_basic_block);
 204   basic_block *trace = XNEWVEC (basic_block, n_basic_blocks);
 205   int *counts = XNEWVEC (int, last_basic_block);
 206   int ninsns = 0, nduplicated = 0;
 207   gcov_type weighted_insns = 0, traced_insns = 0;
 208   fibheap_t heap = fibheap_new ();
 209   gcov_type cover_insns;
 210   int max_dup_insns;
 211   basic_block bb;
 212
 213   if (profile_info && flag_branch_probabilities)
 214     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 215   else
 216     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 217   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 218
 219   branch_ratio_cutoff =
 220     (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
 221
 222   FOR_EACH_BB (bb)
 223     {
 224       int n = count_insns (bb);
 225       if (!ignore_bb_p (bb))
 226         blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
 227                                             bb);
 228
 229       counts [bb->index] = n;
 230       ninsns += n;
 231       weighted_insns += n * bb->frequency;
 232     }
 233
 234   if (profile_info && flag_branch_probabilities)
 235     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
 236   else
 237     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
 238   cover_insns = (weighted_insns * cover_insns + 50) / 100;
 239   max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
 240
 241   while (traced_insns < cover_insns && nduplicated < max_dup_insns
 242          && !fibheap_empty (heap))
 243     {
 244       basic_block bb = fibheap_extract_min (heap);
 245       int n, pos;
 246
 247       if (!bb)
 248         break;
 249
 250       blocks[bb->index] = NULL;
 251
 252       if (ignore_bb_p (bb))
 253         continue;
 254       gcc_assert (!seen (bb));
 255
 256       n = find_trace (bb, trace);
 257
 258       bb = trace[0];
 259       traced_insns += bb->frequency * counts [bb->index];
 260       if (blocks[bb->index])
 261         {
 262           fibheap_delete_node (heap, blocks[bb->index]);
 263           blocks[bb->index] = NULL;
 264         }
 265
 266       for (pos = 1; pos < n; pos++)
 267         {
 268           basic_block bb2 = trace[pos];
 269
 270           if (blocks[bb2->index])
 271             {
 272               fibheap_delete_node (heap, blocks[bb2->index]);
 273               blocks[bb2->index] = NULL;
 274             }
 275           traced_insns += bb2->frequency * counts [bb2->index];
 276           if (EDGE_COUNT (bb2->preds) > 1
 277               && can_duplicate_block_p (bb2))
 278             {
 279               edge e;
 280               basic_block old = bb2;
 281
 282               e = find_edge (bb, bb2);
 283
 284               nduplicated += counts [bb2->index];
 285               bb2 = duplicate_block (bb2, e, bb);
 286
 287               /* Reconsider the original copy of block we've duplicated.
 288                  Removing the most common predecessor may make it to be
 289                  head.  */
 290               blocks[old->index] =
 291                 fibheap_insert (heap, -old->frequency, old);
 292
 293               if (dump_file)
 294                 fprintf (dump_file, "Duplicated %i as %i [%i]\n",
 295                          old->index, bb2->index, bb2->frequency);
 296             }
 297           bb->aux = bb2;
 298           bb2->il.rtl->visited = 1;
 299           bb = bb2;
 300           /* In case the trace became infrequent, stop duplicating.  */
 301           if (ignore_bb_p (bb))
 302             break;
 303         }
 304       if (dump_file)
 305         fprintf (dump_file, " covered now %.1f\n\n",
 306                  traced_insns * 100.0 / weighted_insns);
 307     }
 308   if (dump_file)
 309     fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
 310              nduplicated * 100 / ninsns);
 311
 312   free (blocks);
 313   free (trace);
 314   free (counts);
 315   fibheap_delete (heap);
 316 }
 317
 318 /* Connect the superblocks into linear sequence.  At the moment we attempt to keep
 319    the original order as much as possible, but the algorithm may be made smarter
 320    later if needed.  BB reordering pass should void most of the benefits of such
 321    change though.  */
 322
 323 static void
 324 layout_superblocks (void)
 325 {
 326   basic_block end = single_succ (ENTRY_BLOCK_PTR);
 327   basic_block bb = end->next_bb;
 328
 329   while (bb != EXIT_BLOCK_PTR)
 330     {
 331       edge_iterator ei;
 332       edge e, best = NULL;
 333       while (end->aux)
 334         end = end->aux;
 335
 336       FOR_EACH_EDGE (e, ei, end->succs)
 337         if (e->dest != EXIT_BLOCK_PTR
 338             && e->dest != single_succ (ENTRY_BLOCK_PTR)
 339             && !e->dest->il.rtl->visited
 340             && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
 341           best = e;
 342
 343       if (best)
 344         {
 345           end->aux = best->dest;
 346           best->dest->il.rtl->visited = 1;
 347         }
 348       else
 349         for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 350           {
 351             if (!bb->il.rtl->visited)
 352               {
 353                 end->aux = bb;
 354                 bb->il.rtl->visited = 1;
 355                 break;
 356               }
 357           }
 358     }
 359 }
 360
 361 /* Main entry point to this file.  */
 362
 363 void
 364 tracer (void)
 365 {
 366   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 367
 368   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
 369     return;
 370
 371   mark_dfs_back_edges ();
 372   if (dump_file)
 373     dump_flow_info (dump_file, dump_flags);
 374   tail_duplicate ();
 375   layout_superblocks ();
 376   relink_block_chain (/*stay_in_cfglayout_mode=*/true);
 377
 378   if (dump_file)
 379     dump_flow_info (dump_file, dump_flags);
 380
 381   /* Merge basic blocks in duplicated traces.  */
 382   cleanup_cfg (0);
 383 }
 384 \f
 385 static bool
 386 gate_handle_tracer (void)
 387 {
 388   return (optimize > 0 && flag_tracer);
 389 }
 390
 391 /* Run tracer.  */
 392 static unsigned int
 393 rest_of_handle_tracer (void)
 394 {
 395   if (dump_file)
 396     dump_flow_info (dump_file, dump_flags);
 397   tracer ();
 398   return 0;
 399 }
 400
 401 struct tree_opt_pass pass_tracer =
 402 {
 403   "tracer",                             /* name */
 404   gate_handle_tracer,                   /* gate */
 405   rest_of_handle_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_dump_func,                       /* todo_flags_finish */
 415   'T'                                   /* letter */
 416 };
 417