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 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               edge_iterator ei;
 279               basic_block old = bb2;
 280
 281               FOR_EACH_EDGE (e, ei, bb2->preds)
 282                 if (e->src == bb)
 283                   break;
 284
 285               nduplicated += counts [bb2->index];
 286               bb2 = duplicate_block (bb2, e);
 287
 288               /* Reconsider the original copy of block we've duplicated.
 289                  Removing the most common predecessor may make it to be
 290                  head.  */
 291               blocks[old->index] =
 292                 fibheap_insert (heap, -old->frequency, old);
 293
 294               if (dump_file)
 295                 fprintf (dump_file, "Duplicated %i as %i [%i]\n",
 296                          old->index, bb2->index, bb2->frequency);
 297             }
 298           bb->rbi->next = bb2;
 299           bb2->rbi->visited = 1;
 300           bb = bb2;
 301           /* In case the trace became infrequent, stop duplicating.  */
 302           if (ignore_bb_p (bb))
 303             break;
 304         }
 305       if (dump_file)
 306         fprintf (dump_file, " covered now %.1f\n\n",
 307                  traced_insns * 100.0 / weighted_insns);
 308     }
 309   if (dump_file)
 310     fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
 311              nduplicated * 100 / ninsns);
 312
 313   free (blocks);
 314   free (trace);
 315   free (counts);
 316   fibheap_delete (heap);
 317 }
 318
 319 /* Connect the superblocks into linear sequence.  At the moment we attempt to keep
 320    the original order as much as possible, but the algorithm may be made smarter
 321    later if needed.  BB reordering pass should void most of the benefits of such
 322    change though.  */
 323
 324 static void
 325 layout_superblocks (void)
 326 {
 327   basic_block end = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
 328   basic_block bb = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->next_bb;
 329
 330   while (bb != EXIT_BLOCK_PTR)
 331     {
 332       edge_iterator ei;
 333       edge e, best = NULL;
 334       while (end->rbi->next)
 335         end = end->rbi->next;
 336
 337       FOR_EACH_EDGE (e, ei, end->succs)
 338         if (e->dest != EXIT_BLOCK_PTR
 339             && e->dest != EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest
 340             && !e->dest->rbi->visited
 341             && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
 342           best = e;
 343
 344       if (best)
 345         {
 346           end->rbi->next = best->dest;
 347           best->dest->rbi->visited = 1;
 348         }
 349       else
 350         for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 351           {
 352             if (!bb->rbi->visited)
 353               {
 354                 end->rbi->next = bb;
 355                 bb->rbi->visited = 1;
 356                 break;
 357               }
 358           }
 359     }
 360 }
 361
 362 /* Main entry point to this file.  FLAGS is the set of flags to pass
 363    to cfg_layout_initialize().  */
 364
 365 void
 366 tracer (unsigned int flags)
 367 {
 368   if (n_basic_blocks <= 1)
 369     return;
 370
 371   timevar_push (TV_TRACER);
 372
 373   cfg_layout_initialize (flags);
 374   mark_dfs_back_edges ();
 375   if (dump_file)
 376     dump_flow_info (dump_file);
 377   tail_duplicate ();
 378   layout_superblocks ();
 379   if (dump_file)
 380     dump_flow_info (dump_file);
 381   cfg_layout_finalize ();
 382
 383   /* Merge basic blocks in duplicated traces.  */
 384   cleanup_cfg (CLEANUP_EXPENSIVE);
 385
 386   timevar_pop (TV_TRACER);
 387 }