gcc/tracer.c

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