bb-reorder.c revision 102780
111819Sjulian/* Basic block reordering routines for the GNU compiler. 211819Sjulian Copyright (C) 2000, 2002 Free Software Foundation, Inc. 311819Sjulian 411819Sjulian This file is part of GCC. 511819Sjulian 611819Sjulian GCC is free software; you can redistribute it and/or modify it 711819Sjulian under the terms of the GNU General Public License as published by 811819Sjulian the Free Software Foundation; either version 2, or (at your option) 911819Sjulian any later version. 1011819Sjulian 1111819Sjulian GCC is distributed in the hope that it will be useful, but WITHOUT 1211819Sjulian ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1311819Sjulian or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1411819Sjulian License for more details. 1511819Sjulian 1611819Sjulian You should have received a copy of the GNU General Public License 1711819Sjulian along with GCC; see the file COPYING. If not, write to the Free 1811819Sjulian Software Foundation, 59 Temple Place - Suite 330, Boston, MA 1911819Sjulian 02111-1307, USA. */ 2011819Sjulian 2111819Sjulian/* References: 2211819Sjulian 2311819Sjulian "Profile Guided Code Positioning" 2411819Sjulian Pettis and Hanson; PLDI '90. 2511819Sjulian 2611819Sjulian TODO: 2711819Sjulian 2811819Sjulian (1) Consider: 2911819Sjulian 3011819Sjulian if (p) goto A; // predict taken 3111819Sjulian foo (); 3211819Sjulian A: 3311819Sjulian if (q) goto B; // predict taken 3412057Sjulian bar (); 3512057Sjulian B: 3650477Speter baz (); 3711819Sjulian return; 3811819Sjulian 3911819Sjulian We'll currently reorder this as 4011819Sjulian 4129024Sbde if (!p) goto C; 4211819Sjulian A: 4325345Sjhay if (!q) goto D; 4411819Sjulian B: 4511819Sjulian baz (); 4611819Sjulian return; 4711819Sjulian D: 4811819Sjulian bar (); 4911819Sjulian goto B; 5011819Sjulian C: 5111819Sjulian foo (); 5211819Sjulian goto A; 5311819Sjulian 5411819Sjulian A better ordering is 5511819Sjulian 5611819Sjulian if (!p) goto C; 5711819Sjulian if (!q) goto D; 5811819Sjulian B: 5911819Sjulian baz (); 6011819Sjulian return; 6111819Sjulian C: 6233181Seivind foo (); 6333181Seivind if (q) goto B; 6433181Seivind D: 6533181Seivind bar (); 6633181Seivind goto B; 6733181Seivind 6833181Seivind This requires that we be able to duplicate the jump at A, and 6911819Sjulian adjust the graph traversal such that greedy placement doesn't 7025652Sjhay fix D before C is considered. 7125652Sjhay 7225652Sjhay (2) Coordinate with shorten_branches to minimize the number of 7325652Sjhay long branches. 7411819Sjulian 7533181Seivind (3) Invent a method by which sufficiently non-predicted code can 7625652Sjhay be moved to either the end of the section or another section 7711819Sjulian entirely. Some sort of NOTE_INSN note would work fine. 7825652Sjhay 7925652Sjhay This completely scroggs all debugging formats, so the user 8025652Sjhay would have to explicitly ask for it. 8125652Sjhay*/ 8225652Sjhay 8325652Sjhay#include "config.h" 8425652Sjhay#include "system.h" 8525652Sjhay#include "tree.h" 8625652Sjhay#include "rtl.h" 8725652Sjhay#include "hard-reg-set.h" 8824659Sjhay#include "basic-block.h" 8928270Swollman#include "flags.h" 9025345Sjhay#include "output.h" 9128270Swollman#include "cfglayout.h" 9228270Swollman#include "target.h" 9328270Swollman 9424659Sjhay/* Local function prototypes. */ 9524659Sjhaystatic void make_reorder_chain PARAMS ((void)); 9625345Sjhaystatic basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block)); 9724659Sjhay 9824659Sjhay/* Compute an ordering for a subgraph beginning with block BB. Record the 9924659Sjhay ordering in RBI()->index and chained through RBI()->next. */ 10028270Swollman 10128270Swollmanstatic void 10224659Sjhaymake_reorder_chain () 10325345Sjhay{ 10424659Sjhay basic_block prev = NULL; 10524659Sjhay int nbb_m1 = n_basic_blocks - 1; 10624659Sjhay basic_block next; 10724659Sjhay 10824659Sjhay /* Loop until we've placed every block. */ 10924659Sjhay do 11029366Speter { 11124659Sjhay int i; 11224659Sjhay 11324659Sjhay next = NULL; 11424659Sjhay 11524659Sjhay /* Find the next unplaced block. */ 11624659Sjhay /* ??? Get rid of this loop, and track which blocks are not yet 11724659Sjhay placed more directly, so as to avoid the O(N^2) worst case. 11829366Speter Perhaps keep a doubly-linked list of all to-be-placed blocks; 11924659Sjhay remove from the list as we place. The head of that list is 12024659Sjhay what we're looking for here. */ 12111819Sjulian 12211819Sjulian for (i = 0; i <= nbb_m1 && !next; ++i) 12311819Sjulian { 12411819Sjulian basic_block bb = BASIC_BLOCK (i); 12511819Sjulian if (! RBI (bb)->visited) 12611819Sjulian next = bb; 12711819Sjulian } 12811819Sjulian if (next) 12911819Sjulian prev = make_reorder_chain_1 (next, prev); 13011819Sjulian } 13111819Sjulian while (next); 13211819Sjulian RBI (prev)->next = NULL; 13311819Sjulian} 13411819Sjulian 13511819Sjulian/* A helper function for make_reorder_chain. 13611819Sjulian 13711819Sjulian We do not follow EH edges, or non-fallthru edges to noreturn blocks. 13811819Sjulian These are assumed to be the error condition and we wish to cluster 13911819Sjulian all of them at the very end of the function for the benefit of cache 14025652Sjhay locality for the rest of the function. 14111819Sjulian 14211819Sjulian ??? We could do slightly better by noticing earlier that some subgraph 14311819Sjulian has all paths leading to noreturn functions, but for there to be more 14411819Sjulian than one block in such a subgraph is rare. */ 14511819Sjulian 14625652Sjhaystatic basic_block 14725652Sjhaymake_reorder_chain_1 (bb, prev) 14811819Sjulian basic_block bb; 14911819Sjulian basic_block prev; 15025652Sjhay{ 15111819Sjulian edge e; 15211819Sjulian basic_block next; 15311819Sjulian rtx note; 15411819Sjulian 15511819Sjulian /* Mark this block visited. */ 15611819Sjulian if (prev) 15711819Sjulian { 15811819Sjulian restart: 15911819Sjulian RBI (prev)->next = bb; 16011819Sjulian 16111819Sjulian if (rtl_dump_file && prev->index + 1 != bb->index) 16211819Sjulian fprintf (rtl_dump_file, "Reordering block %d after %d\n", 16311819Sjulian bb->index, prev->index); 16411819Sjulian } 16511819Sjulian else 16611819Sjulian { 16711819Sjulian if (bb->index != 0) 16811819Sjulian abort (); 16911819Sjulian } 17025652Sjhay RBI (bb)->visited = 1; 17111819Sjulian prev = bb; 17211819Sjulian 17311819Sjulian if (bb->succ == NULL) 17411819Sjulian return prev; 17511819Sjulian 17611819Sjulian /* Find the most probable block. */ 17711819Sjulian 17811819Sjulian next = NULL; 17911819Sjulian if (any_condjump_p (bb->end) 18011819Sjulian && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL) 18111819Sjulian { 18211819Sjulian int taken, probability; 18311819Sjulian edge e_taken, e_fall; 18411819Sjulian 18511819Sjulian probability = INTVAL (XEXP (note, 0)); 18611819Sjulian taken = probability > REG_BR_PROB_BASE / 2; 18711819Sjulian 18811819Sjulian /* Find the normal taken edge and the normal fallthru edge. 18911819Sjulian 19011819Sjulian Note, conditional jumps with other side effects may not 19111819Sjulian be fully optimized. In this case it is possible for 19211819Sjulian the conditional jump to branch to the same location as 19311819Sjulian the fallthru path. 19411819Sjulian 19511819Sjulian We should probably work to improve optimization of that 19611819Sjulian case; however, it seems silly not to also deal with such 19711819Sjulian problems here if they happen to occur. */ 19811819Sjulian 19911819Sjulian e_taken = e_fall = NULL; 20011819Sjulian for (e = bb->succ; e ; e = e->succ_next) 20111819Sjulian { 20211819Sjulian if (e->flags & EDGE_FALLTHRU) 20311819Sjulian e_fall = e; 20428270Swollman else if (! (e->flags & EDGE_EH)) 20511819Sjulian e_taken = e; 20611819Sjulian } 20711819Sjulian 20811819Sjulian next = (taken ? e_taken : e_fall)->dest; 20911819Sjulian } 21011819Sjulian 21111819Sjulian /* In the absence of a prediction, disturb things as little as possible 21211819Sjulian by selecting the old "next" block from the list of successors. If 21311819Sjulian there had been a fallthru edge, that will be the one. */ 21411819Sjulian /* Note that the fallthru block may not be next any time we eliminate 21511819Sjulian forwarder blocks. */ 21628270Swollman if (! next) 21728270Swollman { 21811819Sjulian for (e = bb->succ; e ; e = e->succ_next) 21911819Sjulian if (e->flags & EDGE_FALLTHRU) 22011819Sjulian { 22111819Sjulian next = e->dest; 22211819Sjulian break; 22311819Sjulian } 22428270Swollman else if (e->dest->index == bb->index + 1) 22511819Sjulian { 22611819Sjulian if (! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))) 22711819Sjulian next = e->dest; 22811819Sjulian } 22911819Sjulian } 23011819Sjulian 23111819Sjulian /* Make sure we didn't select a silly next block. */ 23211819Sjulian if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited) 23311819Sjulian next = NULL; 23411819Sjulian 23511819Sjulian /* Recurse on the successors. Unroll the last call, as the normal 23611819Sjulian case is exactly one or two edges, and we can tail recurse. */ 23711819Sjulian for (e = bb->succ; e; e = e->succ_next) 23811819Sjulian if (e->dest != EXIT_BLOCK_PTR 23911819Sjulian && ! RBI (e->dest)->visited 24011819Sjulian && e->dest->succ 24111819Sjulian && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))) 24211819Sjulian { 24311819Sjulian if (next) 24411819Sjulian { 24511819Sjulian prev = make_reorder_chain_1 (next, prev); 24611819Sjulian next = RBI (e->dest)->visited ? NULL : e->dest; 24711819Sjulian } 24811819Sjulian else 24925652Sjhay next = e->dest; 25011819Sjulian } 25111819Sjulian if (next) 25211819Sjulian { 25311819Sjulian bb = next; 25411819Sjulian goto restart; 25511819Sjulian } 25611819Sjulian 25711819Sjulian return prev; 25811819Sjulian} 25911819Sjulian 26011819Sjulian/* Reorder basic blocks. The main entry point to this file. */ 26111819Sjulian 26211819Sjulianvoid 26311819Sjulianreorder_basic_blocks () 26411819Sjulian{ 26511819Sjulian if (n_basic_blocks <= 1) 26611819Sjulian return; 26711819Sjulian 26811819Sjulian if ((* targetm.cannot_modify_jumps_p) ()) 26911819Sjulian return; 27011819Sjulian 27111819Sjulian cfg_layout_initialize (); 27211819Sjulian 27325652Sjhay make_reorder_chain (); 27411819Sjulian 27511819Sjulian if (rtl_dump_file) 27611819Sjulian dump_flow_info (rtl_dump_file); 27711819Sjulian 27811819Sjulian cfg_layout_finalize (); 27911819Sjulian} 28011819Sjulian