bb-reorder.c revision 96263
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 if (! next) 215 { 216 for (e = bb->succ; e ; e = e->succ_next) 217 if (e->dest->index == bb->index + 1) 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 258void 259reorder_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} 276