gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING.  If not, write to the Free
  18    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19    02111-1307, USA.  */
  20
  21 /* References:
  22
  23    "Profile Guided Code Positioning"
  24    Pettis and Hanson; PLDI '90.
  25
  26    TODO:
  27
  28    (1) Consider:
  29
  30                 if (p) goto A;          // predict taken
  31                 foo ();
  32               A:
  33                 if (q) goto B;          // predict taken
  34                 bar ();
  35               B:
  36                 baz ();
  37                 return;
  38
  39        We'll currently reorder this as
  40
  41                 if (!p) goto C;
  42               A:
  43                 if (!q) goto D;
  44               B:
  45                 baz ();
  46                 return;
  47               D:
  48                 bar ();
  49                 goto B;
  50               C:
  51                 foo ();
  52                 goto A;
  53
  54        A better ordering is
  55
  56                 if (!p) goto C;
  57                 if (!q) goto D;
  58               B:
  59                 baz ();
  60                 return;
  61               C:
  62                 foo ();
  63                 if (q) goto B;
  64               D:
  65                 bar ();
  66                 goto B;
  67
  68        This requires that we be able to duplicate the jump at A, and
  69        adjust the graph traversal such that greedy placement doesn't
  70        fix D before C is considered.
  71
  72    (2) Coordinate with shorten_branches to minimize the number of
  73        long branches.
  74
  75    (3) Invent a method by which sufficiently non-predicted code can
  76        be moved to either the end of the section or another section
  77        entirely.  Some sort of NOTE_INSN note would work fine.
  78
  79        This completely scroggs all debugging formats, so the user
  80        would have to explicitly ask for it.
  81 */
  82
  83 #include "config.h"
  84 #include "system.h"
  85 #include "tree.h"
  86 #include "rtl.h"
  87 #include "hard-reg-set.h"
  88 #include "basic-block.h"
  89 #include "flags.h"
  90 #include "output.h"
  91 #include "cfglayout.h"
  92
  93 /* Local function prototypes.  */
  94 static void make_reorder_chain          PARAMS ((void));
  95 static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
  96 \f
  97 /* Compute an ordering for a subgraph beginning with block BB.  Record the
  98    ordering in RBI()->index and chained through RBI()->next.  */
  99
 100 static void
 101 make_reorder_chain ()
 102 {
 103   basic_block prev = NULL;
 104   int nbb_m1 = n_basic_blocks - 1;
 105   basic_block next;
 106
 107   /* Loop until we've placed every block.  */
 108   do
 109     {
 110       int i;
 111
 112       next = NULL;
 113
 114       /* Find the next unplaced block.  */
 115       /* ??? Get rid of this loop, and track which blocks are not yet
 116          placed more directly, so as to avoid the O(N^2) worst case.
 117          Perhaps keep a doubly-linked list of all to-be-placed blocks;
 118          remove from the list as we place.  The head of that list is
 119          what we're looking for here.  */
 120
 121       for (i = 0; i <= nbb_m1 && !next; ++i)
 122         {
 123           basic_block bb = BASIC_BLOCK (i);
 124           if (! RBI (bb)->visited)
 125             next = bb;
 126         }
 127       if (next)
 128         prev = make_reorder_chain_1 (next, prev);
 129     }
 130   while (next);
 131   RBI (prev)->next = NULL;
 132 }
 133
 134 /* A helper function for make_reorder_chain.
 135
 136    We do not follow EH edges, or non-fallthru edges to noreturn blocks.
 137    These are assumed to be the error condition and we wish to cluster
 138    all of them at the very end of the function for the benefit of cache
 139    locality for the rest of the function.
 140
 141    ??? We could do slightly better by noticing earlier that some subgraph
 142    has all paths leading to noreturn functions, but for there to be more
 143    than one block in such a subgraph is rare.  */
 144
 145 static basic_block
 146 make_reorder_chain_1 (bb, prev)
 147      basic_block bb;
 148      basic_block prev;
 149 {
 150   edge e;
 151   basic_block next;
 152   rtx note;
 153
 154   /* Mark this block visited.  */
 155   if (prev)
 156     {
 157  restart:
 158       RBI (prev)->next = bb;
 159
 160       if (rtl_dump_file && prev->index + 1 != bb->index)
 161         fprintf (rtl_dump_file, "Reordering block %d after %d\n",
 162                  bb->index, prev->index);
 163     }
 164   else
 165     {
 166       if (bb->index != 0)
 167         abort ();
 168     }
 169   RBI (bb)->visited = 1;
 170   prev = bb;
 171
 172   if (bb->succ == NULL)
 173     return prev;
 174
 175   /* Find the most probable block.  */
 176
 177   next = NULL;
 178   if (any_condjump_p (bb->end)
 179       && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
 180     {
 181       int taken, probability;
 182       edge e_taken, e_fall;
 183
 184       probability = INTVAL (XEXP (note, 0));
 185       taken = probability > REG_BR_PROB_BASE / 2;
 186
 187       /* Find the normal taken edge and the normal fallthru edge.
 188
 189          Note, conditional jumps with other side effects may not
 190          be fully optimized.  In this case it is possible for
 191          the conditional jump to branch to the same location as
 192          the fallthru path.
 193
 194          We should probably work to improve optimization of that
 195          case; however, it seems silly not to also deal with such
 196          problems here if they happen to occur.  */
 197
 198       e_taken = e_fall = NULL;
 199       for (e = bb->succ; e ; e = e->succ_next)
 200         {
 201           if (e->flags & EDGE_FALLTHRU)
 202             e_fall = e;
 203           else if (! (e->flags & EDGE_EH))
 204             e_taken = e;
 205         }
 206
 207       next = (taken ? e_taken : e_fall)->dest;
 208     }
 209
 210   /* In the absence of a prediction, disturb things as little as possible
 211      by selecting the old "next" block from the list of successors.  If
 212      there had been a fallthru edge, that will be the one.  */
 213   if (! next)
 214     {
 215       for (e = bb->succ; e ; e = e->succ_next)
 216         if (e->dest->index == bb->index + 1)
 217           {
 218             if ((e->flags & EDGE_FALLTHRU)
 219                 || (e->dest->succ
 220                     && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))))
 221               next = e->dest;
 222             break;
 223           }
 224     }
 225
 226   /* Make sure we didn't select a silly next block.  */
 227   if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
 228     next = NULL;
 229
 230   /* Recurse on the successors.  Unroll the last call, as the normal
 231      case is exactly one or two edges, and we can tail recurse.  */
 232   for (e = bb->succ; e; e = e->succ_next)
 233     if (e->dest != EXIT_BLOCK_PTR
 234         && ! RBI (e->dest)->visited
 235         && e->dest->succ
 236         && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
 237       {
 238         if (next)
 239           {
 240             prev = make_reorder_chain_1 (next, prev);
 241             next = RBI (e->dest)->visited ? NULL : e->dest;
 242           }
 243         else
 244           next = e->dest;
 245       }
 246   if (next)
 247     {
 248       bb = next;
 249       goto restart;
 250     }
 251
 252   return prev;
 253 }
 254
 255 /* Reorder basic blocks.  The main entry point to this file.  */
 256
 257 void
 258 reorder_basic_blocks ()
 259 {
 260   if (n_basic_blocks <= 1)
 261     return;
 262
 263   cfg_layout_initialize ();
 264
 265   make_reorder_chain ();
 266
 267   if (rtl_dump_file)
 268     dump_flow_info (rtl_dump_file);
 269
 270   cfg_layout_finalize ();
 271 }