bb-reorder.c revision 102780
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. */ 95static void make_reorder_chain PARAMS ((void)); 96static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block)); 97 98/* Compute an ordering for a subgraph beginning with block BB. Record the 99 ordering in RBI()->index and chained through RBI()->next. */ 100 101static void 102make_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 146static basic_block 147make_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->index + 1 != bb->index) 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_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->index == bb->index + 1) 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 262void 263reorder_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 (); 272 273 make_reorder_chain (); 274 275 if (rtl_dump_file) 276 dump_flow_info (rtl_dump_file); 277 278 cfg_layout_finalize (); 279} 280