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