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