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