gcc/bb-reorder.c

   1 /* Basic block reordering routines for the GNU compiler.
   2    Copyright (C) 2000, 2002 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 #include "target.h"
  93
  94 /* Local function prototypes.  */
  95 static void make_reorder_chain          PARAMS ((void));
  96 static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
  97 \f
  98 /* Compute an ordering for a subgraph beginning with block BB.  Record the
  99    ordering in RBI()->index and chained through RBI()->next.  */
 100
 101 static void
 102 make_reorder_chain ()
 103 {
 104   basic_block prev = NULL;
 105   int nbb_m1 = n_basic_blocks - 1;
 106   basic_block next;
 107
 108   /* Loop until we've placed every block.  */
 109   do
 110     {
 111       int i;
 112
 113       next = NULL;
 114
 115       /* Find the next unplaced block.  */
 116       /* ??? Get rid of this loop, and track which blocks are not yet
 117          placed more directly, so as to avoid the O(N^2) worst case.
 118          Perhaps keep a doubly-linked list of all to-be-placed blocks;
 119          remove from the list as we place.  The head of that list is
 120          what we're looking for here.  */
 121
 122       for (i = 0; i <= nbb_m1 && !next; ++i)
 123         {
 124           basic_block bb = BASIC_BLOCK (i);
 125           if (! RBI (bb)->visited)
 126             next = bb;
 127         }
 128       if (next)
 129         prev = make_reorder_chain_1 (next, prev);
 130     }
 131   while (next);
 132   RBI (prev)->next = NULL;
 133 }
 134
 135 /* A helper function for make_reorder_chain.
 136
 137    We do not follow EH edges, or non-fallthru edges to noreturn blocks.
 138    These are assumed to be the error condition and we wish to cluster
 139    all of them at the very end of the function for the benefit of cache
 140    locality for the rest of the function.
 141
 142    ??? We could do slightly better by noticing earlier that some subgraph
 143    has all paths leading to noreturn functions, but for there to be more
 144    than one block in such a subgraph is rare.  */
 145
 146 static basic_block
 147 make_reorder_chain_1 (bb, prev)
 148      basic_block bb;
 149      basic_block prev;
 150 {
 151   edge e;
 152   basic_block next;
 153   rtx note;
 154
 155   /* Mark this block visited.  */
 156   if (prev)
 157     {
 158  restart:
 159       RBI (prev)->next = bb;
 160
 161       if (rtl_dump_file && prev->next_bb != bb)
 162         fprintf (rtl_dump_file, "Reordering block %d after %d\n",
 163                  bb->index, prev->index);
 164     }
 165   else
 166     {
 167       if (bb->index != 0)
 168         abort ();
 169     }
 170   RBI (bb)->visited = 1;
 171   prev = bb;
 172
 173   if (bb->succ == NULL)
 174     return prev;
 175
 176   /* Find the most probable block.  */
 177
 178   next = NULL;
 179   if (any_condjump_p (bb->end)
 180       && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
 181     {
 182       int taken, probability;
 183       edge e_taken, e_fall;
 184
 185       probability = INTVAL (XEXP (note, 0));
 186       taken = probability > REG_BR_PROB_BASE / 2;
 187
 188       /* Find the normal taken edge and the normal fallthru edge.
 189
 190          Note, conditional jumps with other side effects may not
 191          be fully optimized.  In this case it is possible for
 192          the conditional jump to branch to the same location as
 193          the fallthru path.
 194
 195          We should probably work to improve optimization of that
 196          case; however, it seems silly not to also deal with such
 197          problems here if they happen to occur.  */
 198
 199       e_taken = e_fall = NULL;
 200       for (e = bb->succ; e ; e = e->succ_next)
 201         {
 202           if (e->flags & EDGE_FALLTHRU)
 203             e_fall = e;
 204           else if (! (e->flags & EDGE_EH))
 205             e_taken = e;
 206         }
 207
 208       next = ((taken && e_taken) ? e_taken : e_fall)->dest;
 209     }
 210
 211   /* In the absence of a prediction, disturb things as little as possible
 212      by selecting the old "next" block from the list of successors.  If
 213      there had been a fallthru edge, that will be the one.  */
 214   if (! next)
 215     {
 216       for (e = bb->succ; e ; e = e->succ_next)
 217         if (e->dest == bb->next_bb)
 218           {
 219             if ((e->flags & EDGE_FALLTHRU)
 220                 || (e->dest->succ
 221                     && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))))
 222               next = e->dest;
 223             break;
 224           }
 225     }
 226
 227   /* Make sure we didn't select a silly next block.  */
 228   if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
 229     next = NULL;
 230
 231   /* Recurse on the successors.  Unroll the last call, as the normal
 232      case is exactly one or two edges, and we can tail recurse.  */
 233   for (e = bb->succ; e; e = e->succ_next)
 234     if (e->dest != EXIT_BLOCK_PTR
 235         && ! RBI (e->dest)->visited
 236         && e->dest->succ
 237         && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
 238       {
 239         if (next)
 240           {
 241             prev = make_reorder_chain_1 (next, prev);
 242             next = RBI (e->dest)->visited ? NULL : e->dest;
 243           }
 244         else
 245           next = e->dest;
 246       }
 247   if (next)
 248     {
 249       bb = next;
 250       goto restart;
 251     }
 252
 253   return prev;
 254 }
 255
 256 /* Reorder basic blocks.  The main entry point to this file.  */
 257
 258 void
 259 reorder_basic_blocks ()
 260 {
 261   if (n_basic_blocks <= 1)
 262     return;
 263
 264   if ((* targetm.cannot_modify_jumps_p) ())
 265     return;
 266
 267   cfg_layout_initialize ();
 268
 269   make_reorder_chain ();
 270
 271   if (rtl_dump_file)
 272     dump_flow_info (rtl_dump_file);
 273
 274   cfg_layout_finalize ();
 275 }