gcc/tracer.c

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