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
 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 (basic_block bb)
 136 {
 137   edge e;
 138   edge best = NULL;
 139
 140   for (e = bb->pred; e; e = e->pred_next)
 141     if (!best || better_p (e, best))
 142       best = e;
 143   if (!best || ignore_bb_p (best->src))
 144     return NULL;
 145   if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
 146       < bb->frequency * branch_ratio_cutoff)
 147     return NULL;
 148   return best;
 149 }
 150
 151 /* Find the trace using bb and record it in the TRACE array.
 152    Return number of basic blocks recorded.  */
 153
 154 static int
 155 find_trace (basic_block bb, basic_block *trace)
 156 {
 157   int i = 0;
 158   edge e;
 159
 160   if (dump_file)
 161     fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
 162
 163   while ((e = find_best_predecessor (bb)) != NULL)
 164     {
 165       basic_block bb2 = e->src;
 166       if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 167           || find_best_successor (bb2) != e)
 168         break;
 169       if (dump_file)
 170         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
 171       bb = bb2;
 172     }
 173   if (dump_file)
 174     fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
 175   trace[i++] = bb;
 176
 177   /* Follow the trace in forward direction.  */
 178   while ((e = find_best_successor (bb)) != NULL)
 179     {
 180       bb = e->dest;
 181       if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 182           || find_best_predecessor (bb) != e)
 183         break;
 184       if (dump_file)
 185         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
 186       trace[i++] = bb;
 187     }
 188   if (dump_file)
 189     fprintf (dump_file, "\n");
 190   return i;
 191 }
 192
 193 /* Look for basic blocks in frequency order, construct traces and tail duplicate
 194    if profitable.  */
 195
 196 static void
 197 tail_duplicate (void)
 198 {
 199   fibnode_t *blocks = xcalloc (last_basic_block, sizeof (fibnode_t));
 200   basic_block *trace = xmalloc (sizeof (basic_block) * n_basic_blocks);
 201   int *counts = xmalloc (sizeof (int) * last_basic_block);
 202   int ninsns = 0, nduplicated = 0;
 203   gcov_type weighted_insns = 0, traced_insns = 0;
 204   fibheap_t heap = fibheap_new ();
 205   gcov_type cover_insns;
 206   int max_dup_insns;
 207   basic_block bb;
 208
 209   if (profile_info && flag_branch_probabilities)
 210     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 211   else
 212     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 213   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 214
 215   branch_ratio_cutoff =
 216     (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
 217
 218   FOR_EACH_BB (bb)
 219     {
 220       int n = count_insns (bb);
 221       if (!ignore_bb_p (bb))
 222         blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
 223                                             bb);
 224
 225       counts [bb->index] = n;
 226       ninsns += n;
 227       weighted_insns += n * bb->frequency;
 228     }
 229
 230   if (profile_info && flag_branch_probabilities)
 231     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
 232   else
 233     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
 234   cover_insns = (weighted_insns * cover_insns + 50) / 100;
 235   max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
 236
 237   while (traced_insns < cover_insns && nduplicated < max_dup_insns
 238          && !fibheap_empty (heap))
 239     {
 240       basic_block bb = fibheap_extract_min (heap);
 241       int n, pos;
 242
 243       if (!bb)
 244         break;
 245
 246       blocks[bb->index] = NULL;
 247
 248       if (ignore_bb_p (bb))
 249         continue;
 250       gcc_assert (!seen (bb));
 251
 252       n = find_trace (bb, trace);
 253
 254       bb = trace[0];
 255       traced_insns += bb->frequency * counts [bb->index];
 256       if (blocks[bb->index])
 257         {
 258           fibheap_delete_node (heap, blocks[bb->index]);
 259           blocks[bb->index] = NULL;
 260         }
 261
 262       for (pos = 1; pos < n; pos++)
 263         {
 264           basic_block bb2 = trace[pos];
 265
 266           if (blocks[bb2->index])
 267             {
 268               fibheap_delete_node (heap, blocks[bb2->index]);
 269               blocks[bb2->index] = NULL;
 270             }
 271           traced_insns += bb2->frequency * counts [bb2->index];
 272           if (bb2->pred && bb2->pred->pred_next
 273               && can_duplicate_block_p (bb2))
 274             {
 275               edge e = bb2->pred;
 276               basic_block old = bb2;
 277
 278               while (e->src != bb)
 279                 e = e->pred_next;
 280               nduplicated += counts [bb2->index];
 281               bb2 = duplicate_block (bb2, e);
 282
 283               /* Reconsider the original copy of block we've duplicated.
 284                  Removing the most common predecessor may make it to be
 285                  head.  */
 286               blocks[old->index] =
 287                 fibheap_insert (heap, -old->frequency, old);
 288
 289               if (dump_file)
 290                 fprintf (dump_file, "Duplicated %i as %i [%i]\n",
 291                          old->index, bb2->index, bb2->frequency);
 292             }
 293           bb->rbi->next = bb2;
 294           bb2->rbi->visited = 1;
 295           bb = bb2;
 296           /* In case the trace became infrequent, stop duplicating.  */
 297           if (ignore_bb_p (bb))
 298             break;
 299         }
 300       if (dump_file)
 301         fprintf (dump_file, " covered now %.1f\n\n",
 302                  traced_insns * 100.0 / weighted_insns);
 303     }
 304   if (dump_file)
 305     fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
 306              nduplicated * 100 / ninsns);
 307
 308   free (blocks);
 309   free (trace);
 310   free (counts);
 311   fibheap_delete (heap);
 312 }
 313
 314 /* Connect the superblocks into linear sequence.  At the moment we attempt to keep
 315    the original order as much as possible, but the algorithm may be made smarter
 316    later if needed.  BB reordering pass should void most of the benefits of such
 317    change though.  */
 318
 319 static void
 320 layout_superblocks (void)
 321 {
 322   basic_block end = ENTRY_BLOCK_PTR->succ->dest;
 323   basic_block bb = ENTRY_BLOCK_PTR->succ->dest->next_bb;
 324
 325   while (bb != EXIT_BLOCK_PTR)
 326     {
 327       edge e, best = NULL;
 328       while (end->rbi->next)
 329         end = end->rbi->next;
 330
 331       for (e = end->succ; e; e = e->succ_next)
 332         if (e->dest != EXIT_BLOCK_PTR
 333             && e->dest != ENTRY_BLOCK_PTR->succ->dest
 334             && !e->dest->rbi->visited
 335             && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
 336           best = e;
 337
 338       if (best)
 339         {
 340           end->rbi->next = best->dest;
 341           best->dest->rbi->visited = 1;
 342         }
 343       else
 344         for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 345           {
 346             if (!bb->rbi->visited)
 347               {
 348                 end->rbi->next = bb;
 349                 bb->rbi->visited = 1;
 350                 break;
 351               }
 352           }
 353     }
 354 }
 355
 356 /* Main entry point to this file.  FLAGS is the set of flags to pass
 357    to cfg_layout_initialize().  */
 358
 359 void
 360 tracer (unsigned int flags)
 361 {
 362   if (n_basic_blocks <= 1)
 363     return;
 364
 365   timevar_push (TV_TRACER);
 366
 367   cfg_layout_initialize (flags);
 368   mark_dfs_back_edges ();
 369   if (dump_file)
 370     dump_flow_info (dump_file);
 371   tail_duplicate ();
 372   layout_superblocks ();
 373   if (dump_file)
 374     dump_flow_info (dump_file);
 375   cfg_layout_finalize ();
 376
 377   /* Merge basic blocks in duplicated traces.  */
 378   cleanup_cfg (CLEANUP_EXPENSIVE);
 379
 380   timevar_pop (TV_TRACER);
 381 }