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 Free Software Foundation, Inc.
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT
  13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  15    License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GCC; see the file COPYING.  If not, write to the Free
  19    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, USA.  */
  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 "tree.h"
  41 #include "rtl.h"
  42 #include "hard-reg-set.h"
  43 #include "basic-block.h"
  44 #include "output.h"
  45 #include "cfglayout.h"
  46 #include "fibheap.h"
  47 #include "flags.h"
  48 #include "timevar.h"
  49 #include "params.h"
  50 #include "coverage.h"
  51
  52 static int count_insns (basic_block);
  53 static bool ignore_bb_p (basic_block);
  54 static bool better_p (edge, edge);
  55 static edge find_best_successor (basic_block);
  56 static edge find_best_predecessor (basic_block);
  57 static int find_trace (basic_block, basic_block *);
  58 static void tail_duplicate (void);
  59 static void layout_superblocks (void);
  60
  61 /* Minimal outgoing edge probability considered for superblock formation.  */
  62 static int probability_cutoff;
  63 static int branch_ratio_cutoff;
  64
  65 /* Return true if BB has been seen - it is connected to some trace
  66    already.  */
  67
  68 #define seen(bb) (bb->rbi->visited || bb->rbi->next)
  69
  70 /* Return true if we should ignore the basic block for purposes of tracing.  */
  71 static bool
  72 ignore_bb_p (basic_block bb)
  73 {
  74   if (bb->index < 0)
  75     return true;
  76   if (!maybe_hot_bb_p (bb))
  77     return true;
  78   return false;
  79 }
  80
  81 /* Return number of instructions in the block.  */
  82
  83 static int
  84 count_insns (basic_block bb)
  85 {
  86   rtx insn;
  87   int n = 0;
  88
  89   for (insn = BB_HEAD (bb);
  90        insn != NEXT_INSN (BB_END (bb));
  91        insn = NEXT_INSN (insn))
  92     if (active_insn_p (insn))
  93       n++;
  94   return n;
  95 }
  96
  97 /* Return true if E1 is more frequent than E2.  */
  98 static bool
  99 better_p (edge e1, edge e2)
 100 {
 101   if (e1->count != e2->count)
 102     return e1->count > e2->count;
 103   if (e1->src->frequency * e1->probability !=
 104       e2->src->frequency * e2->probability)
 105     return (e1->src->frequency * e1->probability
 106             > e2->src->frequency * e2->probability);
 107   /* This is needed to avoid changes in the decision after
 108      CFG is modified.  */
 109   if (e1->src != e2->src)
 110     return e1->src->index > e2->src->index;
 111   return e1->dest->index > e2->dest->index;
 112 }
 113
 114 /* Return most frequent successor of basic block BB.  */
 115
 116 static edge
 117 find_best_successor (basic_block bb)
 118 {
 119   edge e;
 120   edge best = NULL;
 121   edge_iterator ei;
 122
 123   FOR_EACH_EDGE (e, ei, bb->succs)
 124     if (!best || better_p (e, best))
 125       best = e;
 126   if (!best || ignore_bb_p (best->dest))
 127     return NULL;
 128   if (best->probability <= probability_cutoff)
 129     return NULL;
 130   return best;
 131 }
 132
 133 /* Return most frequent predecessor of basic block BB.  */
 134
 135 static edge
 136 find_best_predecessor (basic_block bb)
 137 {
 138   edge e;
 139   edge best = NULL;
 140   edge_iterator ei;
 141
 142   FOR_EACH_EDGE (e, ei, bb->preds)
 143     if (!best || better_p (e, best))
 144       best = e;
 145   if (!best || ignore_bb_p (best->src))
 146     return NULL;
 147   if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
 148       < bb->frequency * branch_ratio_cutoff)
 149     return NULL;
 150   return best;
 151 }
 152
 153 /* Find the trace using bb and record it in the TRACE array.
 154    Return number of basic blocks recorded.  */
 155
 156 static int
 157 find_trace (basic_block bb, basic_block *trace)
 158 {
 159   int i = 0;
 160   edge e;
 161
 162   if (dump_file)
 163     fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
 164
 165   while ((e = find_best_predecessor (bb)) != NULL)
 166     {
 167       basic_block bb2 = e->src;
 168       if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 169           || find_best_successor (bb2) != e)
 170         break;
 171       if (dump_file)
 172         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
 173       bb = bb2;
 174     }
 175   if (dump_file)
 176     fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
 177   trace[i++] = bb;
 178
 179   /* Follow the trace in forward direction.  */
 180   while ((e = find_best_successor (bb)) != NULL)
 181     {
 182       bb = e->dest;
 183       if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 184           || find_best_predecessor (bb) != e)
 185         break;
 186       if (dump_file)
 187         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
 188       trace[i++] = bb;
 189     }
 190   if (dump_file)
 191     fprintf (dump_file, "\n");
 192   return i;
 193 }
 194
 195 /* Look for basic blocks in frequency order, construct traces and tail duplicate
 196    if profitable.  */
 197
 198 static void
 199 tail_duplicate (void)
 200 {
 201   fibnode_t *blocks = xcalloc (last_basic_block, sizeof (fibnode_t));
 202   basic_block *trace = xmalloc (sizeof (basic_block) * n_basic_blocks);
 203   int *counts = xmalloc (sizeof (int) * last_basic_block);
 204   int ninsns = 0, nduplicated = 0;
 205   gcov_type weighted_insns = 0, traced_insns = 0;
 206   fibheap_t heap = fibheap_new ();
 207   gcov_type cover_insns;
 208   int max_dup_insns;
 209   basic_block bb;
 210
 211   if (profile_info && flag_branch_probabilities)
 212     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 213   else
 214     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 215   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 216
 217   branch_ratio_cutoff =
 218     (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
 219
 220   FOR_EACH_BB (bb)
 221     {
 222       int n = count_insns (bb);
 223       if (!ignore_bb_p (bb))
 224         blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
 225                                             bb);
 226
 227       counts [bb->index] = n;
 228       ninsns += n;
 229       weighted_insns += n * bb->frequency;
 230     }
 231
 232   if (profile_info && flag_branch_probabilities)
 233     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
 234   else
 235     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
 236   cover_insns = (weighted_insns * cover_insns + 50) / 100;
 237   max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
 238
 239   while (traced_insns < cover_insns && nduplicated < max_dup_insns
 240          && !fibheap_empty (heap))
 241     {
 242       basic_block bb = fibheap_extract_min (heap);
 243       int n, pos;
 244
 245       if (!bb)
 246         break;
 247
 248       blocks[bb->index] = NULL;
 249
 250       if (ignore_bb_p (bb))
 251         continue;
 252       gcc_assert (!seen (bb));
 253
 254       n = find_trace (bb, trace);
 255
 256       bb = trace[0];
 257       traced_insns += bb->frequency * counts [bb->index];
 258       if (blocks[bb->index])
 259         {
 260           fibheap_delete_node (heap, blocks[bb->index]);
 261           blocks[bb->index] = NULL;
 262         }
 263
 264       for (pos = 1; pos < n; pos++)
 265         {
 266           basic_block bb2 = trace[pos];
 267
 268           if (blocks[bb2->index])
 269             {
 270               fibheap_delete_node (heap, blocks[bb2->index]);
 271               blocks[bb2->index] = NULL;
 272             }
 273           traced_insns += bb2->frequency * counts [bb2->index];
 274           if (EDGE_COUNT (bb2->preds) > 1
 275               && can_duplicate_block_p (bb2))
 276             {
 277               edge e;
 278               basic_block old = bb2;
 279
 280               e = find_edge (bb, bb2);
 281
 282               nduplicated += counts [bb2->index];
 283               bb2 = duplicate_block (bb2, e);
 284
 285               /* Reconsider the original copy of block we've duplicated.
 286                  Removing the most common predecessor may make it to be
 287                  head.  */
 288               blocks[old->index] =
 289                 fibheap_insert (heap, -old->frequency, old);
 290
 291               if (dump_file)
 292                 fprintf (dump_file, "Duplicated %i as %i [%i]\n",
 293                          old->index, bb2->index, bb2->frequency);
 294             }
 295           bb->rbi->next = bb2;
 296           bb2->rbi->visited = 1;
 297           bb = bb2;
 298           /* In case the trace became infrequent, stop duplicating.  */
 299           if (ignore_bb_p (bb))
 300             break;
 301         }
 302       if (dump_file)
 303         fprintf (dump_file, " covered now %.1f\n\n",
 304                  traced_insns * 100.0 / weighted_insns);
 305     }
 306   if (dump_file)
 307     fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
 308              nduplicated * 100 / ninsns);
 309
 310   free (blocks);
 311   free (trace);
 312   free (counts);
 313   fibheap_delete (heap);
 314 }
 315
 316 /* Connect the superblocks into linear sequence.  At the moment we attempt to keep
 317    the original order as much as possible, but the algorithm may be made smarter
 318    later if needed.  BB reordering pass should void most of the benefits of such
 319    change though.  */
 320
 321 static void
 322 layout_superblocks (void)
 323 {
 324   basic_block end = single_succ (ENTRY_BLOCK_PTR);
 325   basic_block bb = end->next_bb;
 326
 327   while (bb != EXIT_BLOCK_PTR)
 328     {
 329       edge_iterator ei;
 330       edge e, best = NULL;
 331       while (end->rbi->next)
 332         end = end->rbi->next;
 333
 334       FOR_EACH_EDGE (e, ei, end->succs)
 335         if (e->dest != EXIT_BLOCK_PTR
 336             && e->dest != single_succ (ENTRY_BLOCK_PTR)
 337             && !e->dest->rbi->visited
 338             && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
 339           best = e;
 340
 341       if (best)
 342         {
 343           end->rbi->next = best->dest;
 344           best->dest->rbi->visited = 1;
 345         }
 346       else
 347         for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 348           {
 349             if (!bb->rbi->visited)
 350               {
 351                 end->rbi->next = bb;
 352                 bb->rbi->visited = 1;
 353                 break;
 354               }
 355           }
 356     }
 357 }
 358
 359 /* Main entry point to this file.  FLAGS is the set of flags to pass
 360    to cfg_layout_initialize().  */
 361
 362 void
 363 tracer (unsigned int flags)
 364 {
 365   if (n_basic_blocks <= 1)
 366     return;
 367
 368   timevar_push (TV_TRACER);
 369
 370   cfg_layout_initialize (flags);
 371   mark_dfs_back_edges ();
 372   if (dump_file)
 373     dump_flow_info (dump_file);
 374   tail_duplicate ();
 375   layout_superblocks ();
 376   if (dump_file)
 377     dump_flow_info (dump_file);
 378   cfg_layout_finalize ();
 379
 380   /* Merge basic blocks in duplicated traces.  */
 381   cleanup_cfg (CLEANUP_EXPENSIVE);
 382
 383   timevar_pop (TV_TRACER);
 384 }