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 "coretypes.h"
  86 #include "tm.h"
  87 #include "tree.h"
  88 #include "rtl.h"
  89 #include "hard-reg-set.h"
  90 #include "basic-block.h"
  91 #include "flags.h"
  92 #include "output.h"
  93 #include "cfglayout.h"
  94 #include "target.h"
  95
  96 /* Local function prototypes.  */
  97 static void make_reorder_chain          PARAMS ((void));
  98 static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
  99 \f
 100 /* Compute an ordering for a subgraph beginning with block BB.  Record the
 101    ordering in RBI()->index and chained through RBI()->next.  */
 102
 103 static void
 104 make_reorder_chain ()
 105 {
 106   basic_block prev = NULL;
 107   basic_block next, bb;
 108
 109   /* Loop until we've placed every block.  */
 110   do
 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_EACH_BB (bb)
 122         if (! RBI (bb)->visited)
 123           {
 124             next = bb;
 125             break;
 126           }
 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->prev_bb != ENTRY_BLOCK_PTR)
 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   /* Note that the fallthru block may not be next any time we eliminate
 215      forwarder blocks.  */
 216   if (! next)
 217     {
 218       for (e = bb->succ; e ; e = e->succ_next)
 219         if (e->flags & EDGE_FALLTHRU)
 220           {
 221             next = e->dest;
 222             break;
 223           }
 224         else if (e->dest == bb->next_bb)
 225           {
 226             if (! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
 227               next = e->dest;
 228           }
 229     }
 230
 231   /* Make sure we didn't select a silly next block.  */
 232   if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
 233     next = NULL;
 234
 235   /* Recurse on the successors.  Unroll the last call, as the normal
 236      case is exactly one or two edges, and we can tail recurse.  */
 237   for (e = bb->succ; e; e = e->succ_next)
 238     if (e->dest != EXIT_BLOCK_PTR
 239         && ! RBI (e->dest)->visited
 240         && e->dest->succ
 241         && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
 242       {
 243         if (next)
 244           {
 245             prev = make_reorder_chain_1 (next, prev);
 246             next = RBI (e->dest)->visited ? NULL : e->dest;
 247           }
 248         else
 249           next = e->dest;
 250       }
 251   if (next)
 252     {
 253       bb = next;
 254       goto restart;
 255     }
 256
 257   return prev;
 258 }
 259
 260 /* Reorder basic blocks.  The main entry point to this file.  */
 261
 262 void
 263 reorder_basic_blocks ()
 264 {
 265   if (n_basic_blocks <= 1)
 266     return;
 267
 268   if ((* targetm.cannot_modify_jumps_p) ())
 269     return;
 270
 271   cfg_layout_initialize (NULL);
 272
 273   make_reorder_chain ();
 274
 275   if (rtl_dump_file)
 276     dump_flow_info (rtl_dump_file);
 277
 278   cfg_layout_finalize ();
 279 }