190075Sobrien/* Instruction scheduling pass. 290075Sobrien Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 490075Sobrien Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, 590075Sobrien and currently maintained by, Jim Wilson (wilson@cygnus.com) 690075Sobrien 790075SobrienThis file is part of GCC. 890075Sobrien 990075SobrienGCC is free software; you can redistribute it and/or modify it under 1090075Sobrienthe terms of the GNU General Public License as published by the Free 1190075SobrienSoftware Foundation; either version 2, or (at your option) any later 1290075Sobrienversion. 1390075Sobrien 1490075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1590075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1690075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1790075Sobrienfor more details. 1890075Sobrien 1990075SobrienYou should have received a copy of the GNU General Public License 2090075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 22169689Skan02110-1301, USA. */ 2390075Sobrien 2490075Sobrien/* This pass implements list scheduling within basic blocks. It is 2590075Sobrien run twice: (1) after flow analysis, but before register allocation, 2690075Sobrien and (2) after register allocation. 2790075Sobrien 2890075Sobrien The first run performs interblock scheduling, moving insns between 2990075Sobrien different blocks in the same "region", and the second runs only 3090075Sobrien basic block scheduling. 3190075Sobrien 3290075Sobrien Interblock motions performed are useful motions and speculative 3390075Sobrien motions, including speculative loads. Motions requiring code 3490075Sobrien duplication are not supported. The identification of motion type 3590075Sobrien and the check for validity of speculative motions requires 3690075Sobrien construction and analysis of the function's control flow graph. 3790075Sobrien 3890075Sobrien The main entry point for this pass is schedule_insns(), called for 3990075Sobrien each function. The work of the scheduler is organized in three 4090075Sobrien levels: (1) function level: insns are subject to splitting, 4190075Sobrien control-flow-graph is constructed, regions are computed (after 4290075Sobrien reload, each region is of one block), (2) region level: control 4390075Sobrien flow graph attributes required for interblock scheduling are 4490075Sobrien computed (dominators, reachability, etc.), data dependences and 4590075Sobrien priorities are computed, and (3) block level: insns in the block 4690075Sobrien are actually scheduled. */ 4790075Sobrien 4890075Sobrien#include "config.h" 4990075Sobrien#include "system.h" 50132718Skan#include "coretypes.h" 51132718Skan#include "tm.h" 5290075Sobrien#include "toplev.h" 5390075Sobrien#include "rtl.h" 5490075Sobrien#include "tm_p.h" 5590075Sobrien#include "hard-reg-set.h" 5690075Sobrien#include "regs.h" 5790075Sobrien#include "function.h" 5890075Sobrien#include "flags.h" 5990075Sobrien#include "insn-config.h" 6090075Sobrien#include "insn-attr.h" 6190075Sobrien#include "except.h" 6290075Sobrien#include "toplev.h" 6390075Sobrien#include "recog.h" 6490075Sobrien#include "cfglayout.h" 65169689Skan#include "params.h" 6690075Sobrien#include "sched-int.h" 67117395Skan#include "target.h" 68169689Skan#include "timevar.h" 69169689Skan#include "tree-pass.h" 7090075Sobrien 7190075Sobrien/* Define when we want to do count REG_DEAD notes before and after scheduling 7290075Sobrien for sanity checking. We can't do that when conditional execution is used, 7390075Sobrien as REG_DEAD exist only for unconditional deaths. */ 7490075Sobrien 7590075Sobrien#if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING) 7690075Sobrien#define CHECK_DEAD_NOTES 1 7790075Sobrien#else 7890075Sobrien#define CHECK_DEAD_NOTES 0 7990075Sobrien#endif 8090075Sobrien 8190075Sobrien 8290075Sobrien#ifdef INSN_SCHEDULING 8390075Sobrien/* Some accessor macros for h_i_d members only used within this file. */ 8490075Sobrien#define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count) 8590075Sobrien#define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load) 8690075Sobrien#define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn) 8790075Sobrien 8890075Sobrien/* nr_inter/spec counts interblock/speculative motion for the function. */ 8990075Sobrienstatic int nr_inter, nr_spec; 9090075Sobrien 91132718Skanstatic int is_cfg_nonregular (void); 92169689Skanstatic bool sched_is_disabled_for_current_region_p (void); 9390075Sobrien 9490075Sobrien/* A region is the main entity for interblock scheduling: insns 9590075Sobrien are allowed to move between blocks in the same region, along 9690075Sobrien control flow graph edges, in the 'up' direction. */ 9790075Sobrientypedef struct 9890075Sobrien{ 99169689Skan /* Number of extended basic blocks in region. */ 100169689Skan int rgn_nr_blocks; 101169689Skan /* cblocks in the region (actually index in rgn_bb_table). */ 102169689Skan int rgn_blocks; 103169689Skan /* Dependencies for this region are already computed. Basically, indicates, 104169689Skan that this is a recovery block. */ 105169689Skan unsigned int dont_calc_deps : 1; 106169689Skan /* This region has at least one non-trivial ebb. */ 107169689Skan unsigned int has_real_ebb : 1; 10890075Sobrien} 10990075Sobrienregion; 11090075Sobrien 11190075Sobrien/* Number of regions in the procedure. */ 11290075Sobrienstatic int nr_regions; 11390075Sobrien 11490075Sobrien/* Table of region descriptions. */ 11590075Sobrienstatic region *rgn_table; 11690075Sobrien 11790075Sobrien/* Array of lists of regions' blocks. */ 11890075Sobrienstatic int *rgn_bb_table; 11990075Sobrien 12090075Sobrien/* Topological order of blocks in the region (if b2 is reachable from 12190075Sobrien b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is 12290075Sobrien always referred to by either block or b, while its topological 123132718Skan order name (in the region) is referred to by bb. */ 12490075Sobrienstatic int *block_to_bb; 12590075Sobrien 12690075Sobrien/* The number of the region containing a block. */ 12790075Sobrienstatic int *containing_rgn; 12890075Sobrien 129169689Skan/* The minimum probability of reaching a source block so that it will be 130169689Skan considered for speculative scheduling. */ 131169689Skanstatic int min_spec_prob; 132169689Skan 13390075Sobrien#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks) 13490075Sobrien#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks) 135169689Skan#define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps) 136169689Skan#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb) 13790075Sobrien#define BLOCK_TO_BB(block) (block_to_bb[block]) 13890075Sobrien#define CONTAINING_RGN(block) (containing_rgn[block]) 13990075Sobrien 140132718Skanvoid debug_regions (void); 141132718Skanstatic void find_single_block_region (void); 142169689Skanstatic void find_rgns (void); 143169689Skanstatic void extend_rgns (int *, int *, sbitmap, int *); 144169689Skanstatic bool too_large (int, int *, int *); 14590075Sobrien 146132718Skanextern void debug_live (int, int); 14790075Sobrien 14890075Sobrien/* Blocks of the current region being scheduled. */ 14990075Sobrienstatic int current_nr_blocks; 15090075Sobrienstatic int current_blocks; 15190075Sobrien 152169689Skanstatic int rgn_n_insns; 15390075Sobrien 154169689Skan/* The mapping from ebb to block. */ 155169689Skan/* ebb_head [i] - is index in rgn_bb_table, while 156169689Skan EBB_HEAD (i) - is basic block index. 157169689Skan BASIC_BLOCK (EBB_HEAD (i)) - head of ebb. */ 158169689Skan#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]]) 159169689Skan#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb)) 160169689Skan#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1]) 16190075Sobrien 16290075Sobrien/* Target info declarations. 16390075Sobrien 16490075Sobrien The block currently being scheduled is referred to as the "target" block, 16590075Sobrien while other blocks in the region from which insns can be moved to the 16690075Sobrien target are called "source" blocks. The candidate structure holds info 16790075Sobrien about such sources: are they valid? Speculative? Etc. */ 16890075Sobrientypedef struct 16990075Sobrien{ 170169689Skan basic_block *first_member; 171169689Skan int nr_members; 172169689Skan} 173169689Skanbblst; 174169689Skan 175169689Skantypedef struct 176169689Skan{ 17790075Sobrien char is_valid; 17890075Sobrien char is_speculative; 17990075Sobrien int src_prob; 18090075Sobrien bblst split_bbs; 18190075Sobrien bblst update_bbs; 18290075Sobrien} 18390075Sobriencandidate; 18490075Sobrien 18590075Sobrienstatic candidate *candidate_table; 18690075Sobrien 18790075Sobrien/* A speculative motion requires checking live information on the path 18890075Sobrien from 'source' to 'target'. The split blocks are those to be checked. 18990075Sobrien After a speculative motion, live information should be modified in 19090075Sobrien the 'update' blocks. 19190075Sobrien 19290075Sobrien Lists of split and update blocks for each candidate of the current 19390075Sobrien target are in array bblst_table. */ 194169689Skanstatic basic_block *bblst_table; 195169689Skanstatic int bblst_size, bblst_last; 19690075Sobrien 19790075Sobrien#define IS_VALID(src) ( candidate_table[src].is_valid ) 19890075Sobrien#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative ) 19990075Sobrien#define SRC_PROB(src) ( candidate_table[src].src_prob ) 20090075Sobrien 20190075Sobrien/* The bb being currently scheduled. */ 20290075Sobrienstatic int target_bb; 20390075Sobrien 20490075Sobrien/* List of edges. */ 205169689Skantypedef struct 206169689Skan{ 207169689Skan edge *first_member; 208169689Skan int nr_members; 209169689Skan} 210169689Skanedgelst; 21190075Sobrien 212169689Skanstatic edge *edgelst_table; 213169689Skanstatic int edgelst_last; 214169689Skan 215169689Skanstatic void extract_edgelst (sbitmap, edgelst *); 216169689Skan 217169689Skan 21890075Sobrien/* Target info functions. */ 219132718Skanstatic void split_edges (int, int, edgelst *); 220132718Skanstatic void compute_trg_info (int); 221132718Skanvoid debug_candidate (int); 222132718Skanvoid debug_candidates (int); 22390075Sobrien 22490075Sobrien/* Dominators array: dom[i] contains the sbitmap of dominators of 22590075Sobrien bb i in the region. */ 22690075Sobrienstatic sbitmap *dom; 22790075Sobrien 22890075Sobrien/* bb 0 is the only region entry. */ 22990075Sobrien#define IS_RGN_ENTRY(bb) (!bb) 23090075Sobrien 23190075Sobrien/* Is bb_src dominated by bb_trg. */ 23290075Sobrien#define IS_DOMINATED(bb_src, bb_trg) \ 23390075Sobrien( TEST_BIT (dom[bb_src], bb_trg) ) 23490075Sobrien 235169689Skan/* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is 236169689Skan the probability of bb i relative to the region entry. */ 237169689Skanstatic int *prob; 23890075Sobrien 23990075Sobrien/* Bit-set of edges, where bit i stands for edge i. */ 24090075Sobrientypedef sbitmap edgeset; 24190075Sobrien 24290075Sobrien/* Number of edges in the region. */ 24390075Sobrienstatic int rgn_nr_edges; 24490075Sobrien 24590075Sobrien/* Array of size rgn_nr_edges. */ 246169689Skanstatic edge *rgn_edges; 24790075Sobrien 24890075Sobrien/* Mapping from each edge in the graph to its number in the rgn. */ 249169689Skan#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux) 250169689Skan#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr)) 25190075Sobrien 25290075Sobrien/* The split edges of a source bb is different for each target 25390075Sobrien bb. In order to compute this efficiently, the 'potential-split edges' 25490075Sobrien are computed for each bb prior to scheduling a region. This is actually 25590075Sobrien the split edges of each bb relative to the region entry. 25690075Sobrien 25790075Sobrien pot_split[bb] is the set of potential split edges of bb. */ 25890075Sobrienstatic edgeset *pot_split; 25990075Sobrien 26090075Sobrien/* For every bb, a set of its ancestor edges. */ 26190075Sobrienstatic edgeset *ancestor_edges; 26290075Sobrien 263169689Skan/* Array of EBBs sizes. Currently we can get a ebb only through 264169689Skan splitting of currently scheduling block, therefore, we don't need 265169689Skan ebb_head array for every region, its sufficient to hold it only 266169689Skan for current one. */ 267169689Skanstatic int *ebb_head; 268169689Skan 269132718Skanstatic void compute_dom_prob_ps (int); 27090075Sobrien 27190075Sobrien#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN)))) 27290075Sobrien#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN)))) 27390075Sobrien#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN))) 27490075Sobrien 27590075Sobrien/* Speculative scheduling functions. */ 276132718Skanstatic int check_live_1 (int, rtx); 277132718Skanstatic void update_live_1 (int, rtx); 278132718Skanstatic int check_live (rtx, int); 279132718Skanstatic void update_live (rtx, int); 280132718Skanstatic void set_spec_fed (rtx); 281132718Skanstatic int is_pfree (rtx, int, int); 282132718Skanstatic int find_conditional_protection (rtx, int); 283132718Skanstatic int is_conditionally_protected (rtx, int, int); 284132718Skanstatic int is_prisky (rtx, int, int); 285132718Skanstatic int is_exception_free (rtx, int, int); 28690075Sobrien 287132718Skanstatic bool sets_likely_spilled (rtx); 288132718Skanstatic void sets_likely_spilled_1 (rtx, rtx, void *); 289132718Skanstatic void add_branch_dependences (rtx, rtx); 290132718Skanstatic void compute_block_backward_dependences (int); 291132718Skanvoid debug_dependencies (void); 29290075Sobrien 293132718Skanstatic void init_regions (void); 294132718Skanstatic void schedule_region (int); 295132718Skanstatic rtx concat_INSN_LIST (rtx, rtx); 296132718Skanstatic void concat_insn_mem_list (rtx, rtx, rtx *, rtx *); 297132718Skanstatic void propagate_deps (int, struct deps *); 298132718Skanstatic void free_pending_lists (void); 29990075Sobrien 30090075Sobrien/* Functions for construction of the control flow graph. */ 30190075Sobrien 30290075Sobrien/* Return 1 if control flow graph should not be constructed, 0 otherwise. 30390075Sobrien 30490075Sobrien We decide not to build the control flow graph if there is possibly more 305169689Skan than one entry to the function, if computed branches exist, if we 306169689Skan have nonlocal gotos, or if we have an unreachable loop. */ 30790075Sobrien 30890075Sobrienstatic int 309132718Skanis_cfg_nonregular (void) 31090075Sobrien{ 311117395Skan basic_block b; 31290075Sobrien rtx insn; 31390075Sobrien 31490075Sobrien /* If we have a label that could be the target of a nonlocal goto, then 31590075Sobrien the cfg is not well structured. */ 31690075Sobrien if (nonlocal_goto_handler_labels) 31790075Sobrien return 1; 31890075Sobrien 31990075Sobrien /* If we have any forced labels, then the cfg is not well structured. */ 32090075Sobrien if (forced_labels) 32190075Sobrien return 1; 32290075Sobrien 32390075Sobrien /* If we have exception handlers, then we consider the cfg not well 32490075Sobrien structured. ?!? We should be able to handle this now that flow.c 32590075Sobrien computes an accurate cfg for EH. */ 32696263Sobrien if (current_function_has_exception_handlers ()) 32790075Sobrien return 1; 32890075Sobrien 32990075Sobrien /* If we have non-jumping insns which refer to labels, then we consider 33090075Sobrien the cfg not well structured. */ 331117395Skan FOR_EACH_BB (b) 332169689Skan FOR_BB_INSNS (b, insn) 33390075Sobrien { 334169689Skan /* Check for labels referred by non-jump insns. */ 335169689Skan if (NONJUMP_INSN_P (insn) || CALL_P (insn)) 33690075Sobrien { 33790075Sobrien rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX); 33890075Sobrien if (note 339169689Skan && ! (JUMP_P (NEXT_INSN (insn)) 34090075Sobrien && find_reg_note (NEXT_INSN (insn), REG_LABEL, 34190075Sobrien XEXP (note, 0)))) 34290075Sobrien return 1; 34390075Sobrien } 344169689Skan /* If this function has a computed jump, then we consider the cfg 345169689Skan not well structured. */ 346169689Skan else if (JUMP_P (insn) && computed_jump_p (insn)) 347169689Skan return 1; 34890075Sobrien } 34990075Sobrien 35090075Sobrien /* Unreachable loops with more than one basic block are detected 35190075Sobrien during the DFS traversal in find_rgns. 35290075Sobrien 35390075Sobrien Unreachable loops with a single block are detected here. This 35490075Sobrien test is redundant with the one in find_rgns, but it's much 355169689Skan cheaper to go ahead and catch the trivial case here. */ 356117395Skan FOR_EACH_BB (b) 35790075Sobrien { 358169689Skan if (EDGE_COUNT (b->preds) == 0 359169689Skan || (single_pred_p (b) 360169689Skan && single_pred (b) == b)) 361169689Skan return 1; 36290075Sobrien } 36390075Sobrien 364169689Skan /* All the tests passed. Consider the cfg well structured. */ 365169689Skan return 0; 36690075Sobrien} 36790075Sobrien 368169689Skan/* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */ 36990075Sobrien 37090075Sobrienstatic void 371169689Skanextract_edgelst (sbitmap set, edgelst *el) 37290075Sobrien{ 373169689Skan unsigned int i = 0; 374169689Skan sbitmap_iterator sbi; 37590075Sobrien 376169689Skan /* edgelst table space is reused in each call to extract_edgelst. */ 377169689Skan edgelst_last = 0; 37890075Sobrien 379169689Skan el->first_member = &edgelst_table[edgelst_last]; 380169689Skan el->nr_members = 0; 38190075Sobrien 382169689Skan /* Iterate over each word in the bitset. */ 383169689Skan EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi) 38490075Sobrien { 385169689Skan edgelst_table[edgelst_last++] = rgn_edges[i]; 386169689Skan el->nr_members++; 38790075Sobrien } 38890075Sobrien} 38990075Sobrien 39090075Sobrien/* Functions for the construction of regions. */ 39190075Sobrien 39290075Sobrien/* Print the regions, for debugging purposes. Callable from debugger. */ 39390075Sobrien 39490075Sobrienvoid 395132718Skandebug_regions (void) 39690075Sobrien{ 39790075Sobrien int rgn, bb; 39890075Sobrien 39990075Sobrien fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n"); 40090075Sobrien for (rgn = 0; rgn < nr_regions; rgn++) 40190075Sobrien { 40290075Sobrien fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn, 40390075Sobrien rgn_table[rgn].rgn_nr_blocks); 40490075Sobrien fprintf (sched_dump, ";;\tbb/block: "); 40590075Sobrien 406169689Skan /* We don't have ebb_head initialized yet, so we can't use 407169689Skan BB_TO_BLOCK (). */ 408169689Skan current_blocks = RGN_BLOCKS (rgn); 409169689Skan 41090075Sobrien for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++) 411169689Skan fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]); 41290075Sobrien 41390075Sobrien fprintf (sched_dump, "\n\n"); 41490075Sobrien } 41590075Sobrien} 41690075Sobrien 41790075Sobrien/* Build a single block region for each basic block in the function. 41890075Sobrien This allows for using the same code for interblock and basic block 41990075Sobrien scheduling. */ 42090075Sobrien 42190075Sobrienstatic void 422132718Skanfind_single_block_region (void) 42390075Sobrien{ 424117395Skan basic_block bb; 42590075Sobrien 426117395Skan nr_regions = 0; 427117395Skan 428117395Skan FOR_EACH_BB (bb) 42990075Sobrien { 430117395Skan rgn_bb_table[nr_regions] = bb->index; 431117395Skan RGN_NR_BLOCKS (nr_regions) = 1; 432117395Skan RGN_BLOCKS (nr_regions) = nr_regions; 433169689Skan RGN_DONT_CALC_DEPS (nr_regions) = 0; 434169689Skan RGN_HAS_REAL_EBB (nr_regions) = 0; 435117395Skan CONTAINING_RGN (bb->index) = nr_regions; 436117395Skan BLOCK_TO_BB (bb->index) = 0; 437117395Skan nr_regions++; 43890075Sobrien } 43990075Sobrien} 44090075Sobrien 44190075Sobrien/* Update number of blocks and the estimate for number of insns 442169689Skan in the region. Return true if the region is "too large" for interblock 443169689Skan scheduling (compile time considerations). */ 44490075Sobrien 445169689Skanstatic bool 446132718Skantoo_large (int block, int *num_bbs, int *num_insns) 44790075Sobrien{ 44890075Sobrien (*num_bbs)++; 449169689Skan (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block))) 450169689Skan - INSN_LUID (BB_HEAD (BASIC_BLOCK (block)))); 451169689Skan 452169689Skan return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS)) 453169689Skan || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS))); 45490075Sobrien} 45590075Sobrien 45690075Sobrien/* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk] 45790075Sobrien is still an inner loop. Put in max_hdr[blk] the header of the most inner 45890075Sobrien loop containing blk. */ 459117395Skan#define UPDATE_LOOP_RELATIONS(blk, hdr) \ 460117395Skan{ \ 461117395Skan if (max_hdr[blk] == -1) \ 462117395Skan max_hdr[blk] = hdr; \ 463117395Skan else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \ 464117395Skan RESET_BIT (inner, hdr); \ 465117395Skan else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \ 466117395Skan { \ 467117395Skan RESET_BIT (inner,max_hdr[blk]); \ 468117395Skan max_hdr[blk] = hdr; \ 469117395Skan } \ 47090075Sobrien} 47190075Sobrien 47290075Sobrien/* Find regions for interblock scheduling. 47390075Sobrien 47490075Sobrien A region for scheduling can be: 47590075Sobrien 47690075Sobrien * A loop-free procedure, or 47790075Sobrien 47890075Sobrien * A reducible inner loop, or 47990075Sobrien 48090075Sobrien * A basic block not contained in any other region. 48190075Sobrien 48290075Sobrien ?!? In theory we could build other regions based on extended basic 48390075Sobrien blocks or reverse extended basic blocks. Is it worth the trouble? 48490075Sobrien 48590075Sobrien Loop blocks that form a region are put into the region's block list 48690075Sobrien in topological order. 48790075Sobrien 48890075Sobrien This procedure stores its results into the following global (ick) variables 48990075Sobrien 49090075Sobrien * rgn_nr 49190075Sobrien * rgn_table 49290075Sobrien * rgn_bb_table 49390075Sobrien * block_to_bb 49490075Sobrien * containing region 49590075Sobrien 49690075Sobrien We use dominator relationships to avoid making regions out of non-reducible 49790075Sobrien loops. 49890075Sobrien 49990075Sobrien This procedure needs to be converted to work on pred/succ lists instead 50090075Sobrien of edge tables. That would simplify it somewhat. */ 50190075Sobrien 50290075Sobrienstatic void 503169689Skanfind_rgns (void) 50490075Sobrien{ 505169689Skan int *max_hdr, *dfs_nr, *degree; 50690075Sobrien char no_loops = 1; 50790075Sobrien int node, child, loop_head, i, head, tail; 508132718Skan int count = 0, sp, idx = 0; 509169689Skan edge_iterator current_edge; 510169689Skan edge_iterator *stack; 51190075Sobrien int num_bbs, num_insns, unreachable; 51290075Sobrien int too_large_failure; 513117395Skan basic_block bb; 51490075Sobrien 51590075Sobrien /* Note if a block is a natural loop header. */ 51690075Sobrien sbitmap header; 51790075Sobrien 518117395Skan /* Note if a block is a natural inner loop header. */ 51990075Sobrien sbitmap inner; 52090075Sobrien 52190075Sobrien /* Note if a block is in the block queue. */ 52290075Sobrien sbitmap in_queue; 52390075Sobrien 52490075Sobrien /* Note if a block is in the block queue. */ 52590075Sobrien sbitmap in_stack; 52690075Sobrien 52790075Sobrien /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops 52890075Sobrien and a mapping from block to its loop header (if the block is contained 52990075Sobrien in a loop, else -1). 53090075Sobrien 53190075Sobrien Store results in HEADER, INNER, and MAX_HDR respectively, these will 53290075Sobrien be used as inputs to the second traversal. 53390075Sobrien 53490075Sobrien STACK, SP and DFS_NR are only used during the first traversal. */ 53590075Sobrien 53690075Sobrien /* Allocate and initialize variables for the first traversal. */ 537169689Skan max_hdr = XNEWVEC (int, last_basic_block); 538169689Skan dfs_nr = XCNEWVEC (int, last_basic_block); 539169689Skan stack = XNEWVEC (edge_iterator, n_edges); 54090075Sobrien 541117395Skan inner = sbitmap_alloc (last_basic_block); 54290075Sobrien sbitmap_ones (inner); 54390075Sobrien 544117395Skan header = sbitmap_alloc (last_basic_block); 54590075Sobrien sbitmap_zero (header); 54690075Sobrien 547117395Skan in_queue = sbitmap_alloc (last_basic_block); 54890075Sobrien sbitmap_zero (in_queue); 54990075Sobrien 550117395Skan in_stack = sbitmap_alloc (last_basic_block); 55190075Sobrien sbitmap_zero (in_stack); 55290075Sobrien 553117395Skan for (i = 0; i < last_basic_block; i++) 55490075Sobrien max_hdr[i] = -1; 55590075Sobrien 556169689Skan #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux) 557169689Skan #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E))) 558169689Skan 55990075Sobrien /* DFS traversal to find inner loops in the cfg. */ 56090075Sobrien 561169689Skan current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs); 56290075Sobrien sp = -1; 563169689Skan 56490075Sobrien while (1) 56590075Sobrien { 566169689Skan if (EDGE_PASSED (current_edge)) 56790075Sobrien { 56890075Sobrien /* We have reached a leaf node or a node that was already 56990075Sobrien processed. Pop edges off the stack until we find 57090075Sobrien an edge that has not yet been processed. */ 571169689Skan while (sp >= 0 && EDGE_PASSED (current_edge)) 57290075Sobrien { 57390075Sobrien /* Pop entry off the stack. */ 57490075Sobrien current_edge = stack[sp--]; 575169689Skan node = ei_edge (current_edge)->src->index; 576169689Skan gcc_assert (node != ENTRY_BLOCK); 577169689Skan child = ei_edge (current_edge)->dest->index; 578169689Skan gcc_assert (child != EXIT_BLOCK); 57990075Sobrien RESET_BIT (in_stack, child); 58090075Sobrien if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child])) 58190075Sobrien UPDATE_LOOP_RELATIONS (node, max_hdr[child]); 582169689Skan ei_next (¤t_edge); 58390075Sobrien } 58490075Sobrien 58590075Sobrien /* See if have finished the DFS tree traversal. */ 586169689Skan if (sp < 0 && EDGE_PASSED (current_edge)) 58790075Sobrien break; 58890075Sobrien 58990075Sobrien /* Nope, continue the traversal with the popped node. */ 59090075Sobrien continue; 59190075Sobrien } 59290075Sobrien 59390075Sobrien /* Process a node. */ 594169689Skan node = ei_edge (current_edge)->src->index; 595169689Skan gcc_assert (node != ENTRY_BLOCK); 59690075Sobrien SET_BIT (in_stack, node); 59790075Sobrien dfs_nr[node] = ++count; 59890075Sobrien 599169689Skan /* We don't traverse to the exit block. */ 600169689Skan child = ei_edge (current_edge)->dest->index; 601169689Skan if (child == EXIT_BLOCK) 602169689Skan { 603169689Skan SET_EDGE_PASSED (current_edge); 604169689Skan ei_next (¤t_edge); 605169689Skan continue; 606169689Skan } 607169689Skan 60890075Sobrien /* If the successor is in the stack, then we've found a loop. 60990075Sobrien Mark the loop, if it is not a natural loop, then it will 61090075Sobrien be rejected during the second traversal. */ 61190075Sobrien if (TEST_BIT (in_stack, child)) 61290075Sobrien { 61390075Sobrien no_loops = 0; 61490075Sobrien SET_BIT (header, child); 61590075Sobrien UPDATE_LOOP_RELATIONS (node, child); 616169689Skan SET_EDGE_PASSED (current_edge); 617169689Skan ei_next (¤t_edge); 61890075Sobrien continue; 61990075Sobrien } 62090075Sobrien 62190075Sobrien /* If the child was already visited, then there is no need to visit 62290075Sobrien it again. Just update the loop relationships and restart 62390075Sobrien with a new edge. */ 62490075Sobrien if (dfs_nr[child]) 62590075Sobrien { 62690075Sobrien if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child])) 62790075Sobrien UPDATE_LOOP_RELATIONS (node, max_hdr[child]); 628169689Skan SET_EDGE_PASSED (current_edge); 629169689Skan ei_next (¤t_edge); 63090075Sobrien continue; 63190075Sobrien } 63290075Sobrien 63390075Sobrien /* Push an entry on the stack and continue DFS traversal. */ 63490075Sobrien stack[++sp] = current_edge; 635169689Skan SET_EDGE_PASSED (current_edge); 636169689Skan current_edge = ei_start (ei_edge (current_edge)->dest->succs); 637169689Skan } 63890075Sobrien 639169689Skan /* Reset ->aux field used by EDGE_PASSED. */ 640169689Skan FOR_ALL_BB (bb) 641169689Skan { 642169689Skan edge_iterator ei; 643169689Skan edge e; 644169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 645169689Skan e->aux = NULL; 646169689Skan } 64790075Sobrien 64890075Sobrien 64990075Sobrien /* Another check for unreachable blocks. The earlier test in 65090075Sobrien is_cfg_nonregular only finds unreachable blocks that do not 65190075Sobrien form a loop. 65290075Sobrien 65390075Sobrien The DFS traversal will mark every block that is reachable from 65490075Sobrien the entry node by placing a nonzero value in dfs_nr. Thus if 65590075Sobrien dfs_nr is zero for any block, then it must be unreachable. */ 65690075Sobrien unreachable = 0; 657117395Skan FOR_EACH_BB (bb) 658117395Skan if (dfs_nr[bb->index] == 0) 65990075Sobrien { 66090075Sobrien unreachable = 1; 66190075Sobrien break; 66290075Sobrien } 66390075Sobrien 66490075Sobrien /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array 66590075Sobrien to hold degree counts. */ 66690075Sobrien degree = dfs_nr; 66790075Sobrien 668117395Skan FOR_EACH_BB (bb) 669169689Skan degree[bb->index] = EDGE_COUNT (bb->preds); 67090075Sobrien 67190075Sobrien /* Do not perform region scheduling if there are any unreachable 67290075Sobrien blocks. */ 67390075Sobrien if (!unreachable) 67490075Sobrien { 675169689Skan int *queue, *degree1 = NULL; 676169689Skan /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put 677169689Skan there basic blocks, which are forced to be region heads. 678169689Skan This is done to try to assemble few smaller regions 679169689Skan from a too_large region. */ 680169689Skan sbitmap extended_rgn_header = NULL; 681169689Skan bool extend_regions_p; 68290075Sobrien 68390075Sobrien if (no_loops) 68490075Sobrien SET_BIT (header, 0); 68590075Sobrien 686132718Skan /* Second traversal:find reducible inner loops and topologically sort 68790075Sobrien block of each region. */ 68890075Sobrien 689169689Skan queue = XNEWVEC (int, n_basic_blocks); 690169689Skan 691169689Skan extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0; 692169689Skan if (extend_regions_p) 693169689Skan { 694169689Skan degree1 = xmalloc (last_basic_block * sizeof (int)); 695169689Skan extended_rgn_header = sbitmap_alloc (last_basic_block); 696169689Skan sbitmap_zero (extended_rgn_header); 697169689Skan } 69890075Sobrien 69990075Sobrien /* Find blocks which are inner loop headers. We still have non-reducible 70090075Sobrien loops to consider at this point. */ 701117395Skan FOR_EACH_BB (bb) 70290075Sobrien { 703117395Skan if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index)) 70490075Sobrien { 70590075Sobrien edge e; 706169689Skan edge_iterator ei; 707117395Skan basic_block jbb; 70890075Sobrien 70990075Sobrien /* Now check that the loop is reducible. We do this separate 71090075Sobrien from finding inner loops so that we do not find a reducible 71190075Sobrien loop which contains an inner non-reducible loop. 71290075Sobrien 71390075Sobrien A simple way to find reducible/natural loops is to verify 71490075Sobrien that each block in the loop is dominated by the loop 71590075Sobrien header. 71690075Sobrien 71790075Sobrien If there exists a block that is not dominated by the loop 71890075Sobrien header, then the block is reachable from outside the loop 71990075Sobrien and thus the loop is not a natural loop. */ 720117395Skan FOR_EACH_BB (jbb) 72190075Sobrien { 72290075Sobrien /* First identify blocks in the loop, except for the loop 72390075Sobrien entry block. */ 724117395Skan if (bb->index == max_hdr[jbb->index] && bb != jbb) 72590075Sobrien { 72690075Sobrien /* Now verify that the block is dominated by the loop 72790075Sobrien header. */ 728132718Skan if (!dominated_by_p (CDI_DOMINATORS, jbb, bb)) 72990075Sobrien break; 73090075Sobrien } 73190075Sobrien } 73290075Sobrien 73390075Sobrien /* If we exited the loop early, then I is the header of 73490075Sobrien a non-reducible loop and we should quit processing it 73590075Sobrien now. */ 736117395Skan if (jbb != EXIT_BLOCK_PTR) 73790075Sobrien continue; 73890075Sobrien 73990075Sobrien /* I is a header of an inner loop, or block 0 in a subroutine 74090075Sobrien with no loops at all. */ 74190075Sobrien head = tail = -1; 74290075Sobrien too_large_failure = 0; 743117395Skan loop_head = max_hdr[bb->index]; 74490075Sobrien 745169689Skan if (extend_regions_p) 746169689Skan /* We save degree in case when we meet a too_large region 747169689Skan and cancel it. We need a correct degree later when 748169689Skan calling extend_rgns. */ 749169689Skan memcpy (degree1, degree, last_basic_block * sizeof (int)); 750169689Skan 75190075Sobrien /* Decrease degree of all I's successors for topological 75290075Sobrien ordering. */ 753169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 75490075Sobrien if (e->dest != EXIT_BLOCK_PTR) 75590075Sobrien --degree[e->dest->index]; 75690075Sobrien 75790075Sobrien /* Estimate # insns, and count # blocks in the region. */ 75890075Sobrien num_bbs = 1; 759132718Skan num_insns = (INSN_LUID (BB_END (bb)) 760132718Skan - INSN_LUID (BB_HEAD (bb))); 76190075Sobrien 76290075Sobrien /* Find all loop latches (blocks with back edges to the loop 76390075Sobrien header) or all the leaf blocks in the cfg has no loops. 76490075Sobrien 76590075Sobrien Place those blocks into the queue. */ 76690075Sobrien if (no_loops) 76790075Sobrien { 768117395Skan FOR_EACH_BB (jbb) 76990075Sobrien /* Leaf nodes have only a single successor which must 77090075Sobrien be EXIT_BLOCK. */ 771169689Skan if (single_succ_p (jbb) 772169689Skan && single_succ (jbb) == EXIT_BLOCK_PTR) 77390075Sobrien { 774117395Skan queue[++tail] = jbb->index; 775117395Skan SET_BIT (in_queue, jbb->index); 77690075Sobrien 777117395Skan if (too_large (jbb->index, &num_bbs, &num_insns)) 77890075Sobrien { 77990075Sobrien too_large_failure = 1; 78090075Sobrien break; 78190075Sobrien } 78290075Sobrien } 78390075Sobrien } 78490075Sobrien else 78590075Sobrien { 78690075Sobrien edge e; 78790075Sobrien 788169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 78990075Sobrien { 79090075Sobrien if (e->src == ENTRY_BLOCK_PTR) 79190075Sobrien continue; 79290075Sobrien 79390075Sobrien node = e->src->index; 79490075Sobrien 795117395Skan if (max_hdr[node] == loop_head && node != bb->index) 79690075Sobrien { 79790075Sobrien /* This is a loop latch. */ 79890075Sobrien queue[++tail] = node; 79990075Sobrien SET_BIT (in_queue, node); 80090075Sobrien 80190075Sobrien if (too_large (node, &num_bbs, &num_insns)) 80290075Sobrien { 80390075Sobrien too_large_failure = 1; 80490075Sobrien break; 80590075Sobrien } 80690075Sobrien } 80790075Sobrien } 80890075Sobrien } 80990075Sobrien 81090075Sobrien /* Now add all the blocks in the loop to the queue. 81190075Sobrien 81290075Sobrien We know the loop is a natural loop; however the algorithm 81390075Sobrien above will not always mark certain blocks as being in the 81490075Sobrien loop. Consider: 81590075Sobrien node children 81690075Sobrien a b,c 81790075Sobrien b c 81890075Sobrien c a,d 81990075Sobrien d b 82090075Sobrien 82190075Sobrien The algorithm in the DFS traversal may not mark B & D as part 822169689Skan of the loop (i.e. they will not have max_hdr set to A). 82390075Sobrien 82490075Sobrien We know they can not be loop latches (else they would have 82590075Sobrien had max_hdr set since they'd have a backedge to a dominator 82690075Sobrien block). So we don't need them on the initial queue. 82790075Sobrien 82890075Sobrien We know they are part of the loop because they are dominated 82990075Sobrien by the loop header and can be reached by a backwards walk of 83090075Sobrien the edges starting with nodes on the initial queue. 83190075Sobrien 83290075Sobrien It is safe and desirable to include those nodes in the 83390075Sobrien loop/scheduling region. To do so we would need to decrease 83490075Sobrien the degree of a node if it is the target of a backedge 83590075Sobrien within the loop itself as the node is placed in the queue. 83690075Sobrien 83790075Sobrien We do not do this because I'm not sure that the actual 83890075Sobrien scheduling code will properly handle this case. ?!? */ 83990075Sobrien 84090075Sobrien while (head < tail && !too_large_failure) 84190075Sobrien { 84290075Sobrien edge e; 84390075Sobrien child = queue[++head]; 84490075Sobrien 845169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds) 84690075Sobrien { 84790075Sobrien node = e->src->index; 84890075Sobrien 84990075Sobrien /* See discussion above about nodes not marked as in 85090075Sobrien this loop during the initial DFS traversal. */ 85190075Sobrien if (e->src == ENTRY_BLOCK_PTR 85290075Sobrien || max_hdr[node] != loop_head) 85390075Sobrien { 85490075Sobrien tail = -1; 85590075Sobrien break; 85690075Sobrien } 857117395Skan else if (!TEST_BIT (in_queue, node) && node != bb->index) 85890075Sobrien { 85990075Sobrien queue[++tail] = node; 86090075Sobrien SET_BIT (in_queue, node); 86190075Sobrien 86290075Sobrien if (too_large (node, &num_bbs, &num_insns)) 86390075Sobrien { 86490075Sobrien too_large_failure = 1; 86590075Sobrien break; 86690075Sobrien } 86790075Sobrien } 86890075Sobrien } 86990075Sobrien } 87090075Sobrien 87190075Sobrien if (tail >= 0 && !too_large_failure) 87290075Sobrien { 87390075Sobrien /* Place the loop header into list of region blocks. */ 874117395Skan degree[bb->index] = -1; 875117395Skan rgn_bb_table[idx] = bb->index; 87690075Sobrien RGN_NR_BLOCKS (nr_regions) = num_bbs; 87790075Sobrien RGN_BLOCKS (nr_regions) = idx++; 878169689Skan RGN_DONT_CALC_DEPS (nr_regions) = 0; 879169689Skan RGN_HAS_REAL_EBB (nr_regions) = 0; 880117395Skan CONTAINING_RGN (bb->index) = nr_regions; 881117395Skan BLOCK_TO_BB (bb->index) = count = 0; 88290075Sobrien 88390075Sobrien /* Remove blocks from queue[] when their in degree 88490075Sobrien becomes zero. Repeat until no blocks are left on the 88590075Sobrien list. This produces a topological list of blocks in 88690075Sobrien the region. */ 88790075Sobrien while (tail >= 0) 88890075Sobrien { 88990075Sobrien if (head < 0) 89090075Sobrien head = tail; 89190075Sobrien child = queue[head]; 89290075Sobrien if (degree[child] == 0) 89390075Sobrien { 89490075Sobrien edge e; 89590075Sobrien 89690075Sobrien degree[child] = -1; 89790075Sobrien rgn_bb_table[idx++] = child; 89890075Sobrien BLOCK_TO_BB (child) = ++count; 89990075Sobrien CONTAINING_RGN (child) = nr_regions; 90090075Sobrien queue[head] = queue[tail--]; 90190075Sobrien 902169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs) 90390075Sobrien if (e->dest != EXIT_BLOCK_PTR) 90490075Sobrien --degree[e->dest->index]; 90590075Sobrien } 90690075Sobrien else 90790075Sobrien --head; 90890075Sobrien } 90990075Sobrien ++nr_regions; 91090075Sobrien } 911169689Skan else if (extend_regions_p) 912169689Skan { 913169689Skan /* Restore DEGREE. */ 914169689Skan int *t = degree; 915169689Skan 916169689Skan degree = degree1; 917169689Skan degree1 = t; 918169689Skan 919169689Skan /* And force successors of BB to be region heads. 920169689Skan This may provide several smaller regions instead 921169689Skan of one too_large region. */ 922169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 923169689Skan if (e->dest != EXIT_BLOCK_PTR) 924169689Skan SET_BIT (extended_rgn_header, e->dest->index); 925169689Skan } 92690075Sobrien } 92790075Sobrien } 92890075Sobrien free (queue); 929169689Skan 930169689Skan if (extend_regions_p) 931169689Skan { 932169689Skan free (degree1); 933169689Skan 934169689Skan sbitmap_a_or_b (header, header, extended_rgn_header); 935169689Skan sbitmap_free (extended_rgn_header); 936169689Skan 937169689Skan extend_rgns (degree, &idx, header, max_hdr); 938169689Skan } 93990075Sobrien } 94090075Sobrien 94190075Sobrien /* Any block that did not end up in a region is placed into a region 94290075Sobrien by itself. */ 943117395Skan FOR_EACH_BB (bb) 944117395Skan if (degree[bb->index] >= 0) 94590075Sobrien { 946117395Skan rgn_bb_table[idx] = bb->index; 94790075Sobrien RGN_NR_BLOCKS (nr_regions) = 1; 94890075Sobrien RGN_BLOCKS (nr_regions) = idx++; 949169689Skan RGN_DONT_CALC_DEPS (nr_regions) = 0; 950169689Skan RGN_HAS_REAL_EBB (nr_regions) = 0; 951117395Skan CONTAINING_RGN (bb->index) = nr_regions++; 952117395Skan BLOCK_TO_BB (bb->index) = 0; 95390075Sobrien } 95490075Sobrien 95590075Sobrien free (max_hdr); 956169689Skan free (degree); 95790075Sobrien free (stack); 95890075Sobrien sbitmap_free (header); 95990075Sobrien sbitmap_free (inner); 96090075Sobrien sbitmap_free (in_queue); 96190075Sobrien sbitmap_free (in_stack); 96290075Sobrien} 96390075Sobrien 964169689Skanstatic int gather_region_statistics (int **); 965169689Skanstatic void print_region_statistics (int *, int, int *, int); 966169689Skan 967169689Skan/* Calculate the histogram that shows the number of regions having the 968169689Skan given number of basic blocks, and store it in the RSP array. Return 969169689Skan the size of this array. */ 970169689Skanstatic int 971169689Skangather_region_statistics (int **rsp) 972169689Skan{ 973169689Skan int i, *a = 0, a_sz = 0; 974169689Skan 975169689Skan /* a[i] is the number of regions that have (i + 1) basic blocks. */ 976169689Skan for (i = 0; i < nr_regions; i++) 977169689Skan { 978169689Skan int nr_blocks = RGN_NR_BLOCKS (i); 979169689Skan 980169689Skan gcc_assert (nr_blocks >= 1); 981169689Skan 982169689Skan if (nr_blocks > a_sz) 983169689Skan { 984169689Skan a = xrealloc (a, nr_blocks * sizeof (*a)); 985169689Skan do 986169689Skan a[a_sz++] = 0; 987169689Skan while (a_sz != nr_blocks); 988169689Skan } 989169689Skan 990169689Skan a[nr_blocks - 1]++; 991169689Skan } 992169689Skan 993169689Skan *rsp = a; 994169689Skan return a_sz; 995169689Skan} 996169689Skan 997169689Skan/* Print regions statistics. S1 and S2 denote the data before and after 998169689Skan calling extend_rgns, respectively. */ 999169689Skanstatic void 1000169689Skanprint_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz) 1001169689Skan{ 1002169689Skan int i; 1003169689Skan 1004169689Skan /* We iterate until s2_sz because extend_rgns does not decrease 1005169689Skan the maximal region size. */ 1006169689Skan for (i = 1; i < s2_sz; i++) 1007169689Skan { 1008169689Skan int n1, n2; 1009169689Skan 1010169689Skan n2 = s2[i]; 1011169689Skan 1012169689Skan if (n2 == 0) 1013169689Skan continue; 1014169689Skan 1015169689Skan if (i >= s1_sz) 1016169689Skan n1 = 0; 1017169689Skan else 1018169689Skan n1 = s1[i]; 1019169689Skan 1020169689Skan fprintf (sched_dump, ";; Region extension statistics: size %d: " \ 1021169689Skan "was %d + %d more\n", i + 1, n1, n2 - n1); 1022169689Skan } 1023169689Skan} 1024169689Skan 1025169689Skan/* Extend regions. 1026169689Skan DEGREE - Array of incoming edge count, considering only 1027169689Skan the edges, that don't have their sources in formed regions yet. 1028169689Skan IDXP - pointer to the next available index in rgn_bb_table. 1029169689Skan HEADER - set of all region heads. 1030169689Skan LOOP_HDR - mapping from block to the containing loop 1031169689Skan (two blocks can reside within one region if they have 1032169689Skan the same loop header). */ 1033169689Skanstatic void 1034169689Skanextend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr) 1035169689Skan{ 1036169689Skan int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr; 1037169689Skan int nblocks = n_basic_blocks - NUM_FIXED_BLOCKS; 1038169689Skan 1039169689Skan max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS); 1040169689Skan 1041169689Skan max_hdr = xmalloc (last_basic_block * sizeof (*max_hdr)); 1042169689Skan 1043169689Skan order = xmalloc (last_basic_block * sizeof (*order)); 1044169689Skan post_order_compute (order, false); 1045169689Skan 1046169689Skan for (i = nblocks - 1; i >= 0; i--) 1047169689Skan { 1048169689Skan int bbn = order[i]; 1049169689Skan if (degree[bbn] >= 0) 1050169689Skan { 1051169689Skan max_hdr[bbn] = bbn; 1052169689Skan rescan = 1; 1053169689Skan } 1054169689Skan else 1055169689Skan /* This block already was processed in find_rgns. */ 1056169689Skan max_hdr[bbn] = -1; 1057169689Skan } 1058169689Skan 1059169689Skan /* The idea is to topologically walk through CFG in top-down order. 1060169689Skan During the traversal, if all the predecessors of a node are 1061169689Skan marked to be in the same region (they all have the same max_hdr), 1062169689Skan then current node is also marked to be a part of that region. 1063169689Skan Otherwise the node starts its own region. 1064169689Skan CFG should be traversed until no further changes are made. On each 1065169689Skan iteration the set of the region heads is extended (the set of those 1066169689Skan blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the 1067169689Skan set of all basic blocks, thus the algorithm is guaranteed to terminate. */ 1068169689Skan 1069169689Skan while (rescan && iter < max_iter) 1070169689Skan { 1071169689Skan rescan = 0; 1072169689Skan 1073169689Skan for (i = nblocks - 1; i >= 0; i--) 1074169689Skan { 1075169689Skan edge e; 1076169689Skan edge_iterator ei; 1077169689Skan int bbn = order[i]; 1078169689Skan 1079169689Skan if (max_hdr[bbn] != -1 && !TEST_BIT (header, bbn)) 1080169689Skan { 1081169689Skan int hdr = -1; 1082169689Skan 1083169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->preds) 1084169689Skan { 1085169689Skan int predn = e->src->index; 1086169689Skan 1087169689Skan if (predn != ENTRY_BLOCK 1088169689Skan /* If pred wasn't processed in find_rgns. */ 1089169689Skan && max_hdr[predn] != -1 1090169689Skan /* And pred and bb reside in the same loop. 1091169689Skan (Or out of any loop). */ 1092169689Skan && loop_hdr[bbn] == loop_hdr[predn]) 1093169689Skan { 1094169689Skan if (hdr == -1) 1095169689Skan /* Then bb extends the containing region of pred. */ 1096169689Skan hdr = max_hdr[predn]; 1097169689Skan else if (hdr != max_hdr[predn]) 1098169689Skan /* Too bad, there are at least two predecessors 1099169689Skan that reside in different regions. Thus, BB should 1100169689Skan begin its own region. */ 1101169689Skan { 1102169689Skan hdr = bbn; 1103169689Skan break; 1104169689Skan } 1105169689Skan } 1106169689Skan else 1107169689Skan /* BB starts its own region. */ 1108169689Skan { 1109169689Skan hdr = bbn; 1110169689Skan break; 1111169689Skan } 1112169689Skan } 1113169689Skan 1114169689Skan if (hdr == bbn) 1115169689Skan { 1116169689Skan /* If BB start its own region, 1117169689Skan update set of headers with BB. */ 1118169689Skan SET_BIT (header, bbn); 1119169689Skan rescan = 1; 1120169689Skan } 1121169689Skan else 1122169689Skan gcc_assert (hdr != -1); 1123169689Skan 1124169689Skan max_hdr[bbn] = hdr; 1125169689Skan } 1126169689Skan } 1127169689Skan 1128169689Skan iter++; 1129169689Skan } 1130169689Skan 1131169689Skan /* Statistics were gathered on the SPEC2000 package of tests with 1132169689Skan mainline weekly snapshot gcc-4.1-20051015 on ia64. 1133169689Skan 1134169689Skan Statistics for SPECint: 1135169689Skan 1 iteration : 1751 cases (38.7%) 1136169689Skan 2 iterations: 2770 cases (61.3%) 1137169689Skan Blocks wrapped in regions by find_rgns without extension: 18295 blocks 1138169689Skan Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks 1139169689Skan (We don't count single block regions here). 1140169689Skan 1141169689Skan Statistics for SPECfp: 1142169689Skan 1 iteration : 621 cases (35.9%) 1143169689Skan 2 iterations: 1110 cases (64.1%) 1144169689Skan Blocks wrapped in regions by find_rgns without extension: 6476 blocks 1145169689Skan Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks 1146169689Skan (We don't count single block regions here). 1147169689Skan 1148169689Skan By default we do at most 2 iterations. 1149169689Skan This can be overridden with max-sched-extend-regions-iters parameter: 1150169689Skan 0 - disable region extension, 1151169689Skan N > 0 - do at most N iterations. */ 1152169689Skan 1153169689Skan if (sched_verbose && iter != 0) 1154169689Skan fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter, 1155169689Skan rescan ? "... failed" : ""); 1156169689Skan 1157169689Skan if (!rescan && iter != 0) 1158169689Skan { 1159169689Skan int *s1 = NULL, s1_sz = 0; 1160169689Skan 1161169689Skan /* Save the old statistics for later printout. */ 1162169689Skan if (sched_verbose >= 6) 1163169689Skan s1_sz = gather_region_statistics (&s1); 1164169689Skan 1165169689Skan /* We have succeeded. Now assemble the regions. */ 1166169689Skan for (i = nblocks - 1; i >= 0; i--) 1167169689Skan { 1168169689Skan int bbn = order[i]; 1169169689Skan 1170169689Skan if (max_hdr[bbn] == bbn) 1171169689Skan /* BBN is a region head. */ 1172169689Skan { 1173169689Skan edge e; 1174169689Skan edge_iterator ei; 1175169689Skan int num_bbs = 0, j, num_insns = 0, large; 1176169689Skan 1177169689Skan large = too_large (bbn, &num_bbs, &num_insns); 1178169689Skan 1179169689Skan degree[bbn] = -1; 1180169689Skan rgn_bb_table[idx] = bbn; 1181169689Skan RGN_BLOCKS (nr_regions) = idx++; 1182169689Skan RGN_DONT_CALC_DEPS (nr_regions) = 0; 1183169689Skan RGN_HAS_REAL_EBB (nr_regions) = 0; 1184169689Skan CONTAINING_RGN (bbn) = nr_regions; 1185169689Skan BLOCK_TO_BB (bbn) = 0; 1186169689Skan 1187169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->succs) 1188169689Skan if (e->dest != EXIT_BLOCK_PTR) 1189169689Skan degree[e->dest->index]--; 1190169689Skan 1191169689Skan if (!large) 1192169689Skan /* Here we check whether the region is too_large. */ 1193169689Skan for (j = i - 1; j >= 0; j--) 1194169689Skan { 1195169689Skan int succn = order[j]; 1196169689Skan if (max_hdr[succn] == bbn) 1197169689Skan { 1198169689Skan if ((large = too_large (succn, &num_bbs, &num_insns))) 1199169689Skan break; 1200169689Skan } 1201169689Skan } 1202169689Skan 1203169689Skan if (large) 1204169689Skan /* If the region is too_large, then wrap every block of 1205169689Skan the region into single block region. 1206169689Skan Here we wrap region head only. Other blocks are 1207169689Skan processed in the below cycle. */ 1208169689Skan { 1209169689Skan RGN_NR_BLOCKS (nr_regions) = 1; 1210169689Skan nr_regions++; 1211169689Skan } 1212169689Skan 1213169689Skan num_bbs = 1; 1214169689Skan 1215169689Skan for (j = i - 1; j >= 0; j--) 1216169689Skan { 1217169689Skan int succn = order[j]; 1218169689Skan 1219169689Skan if (max_hdr[succn] == bbn) 1220169689Skan /* This cycle iterates over all basic blocks, that 1221169689Skan are supposed to be in the region with head BBN, 1222169689Skan and wraps them into that region (or in single 1223169689Skan block region). */ 1224169689Skan { 1225169689Skan gcc_assert (degree[succn] == 0); 1226169689Skan 1227169689Skan degree[succn] = -1; 1228169689Skan rgn_bb_table[idx] = succn; 1229169689Skan BLOCK_TO_BB (succn) = large ? 0 : num_bbs++; 1230169689Skan CONTAINING_RGN (succn) = nr_regions; 1231169689Skan 1232169689Skan if (large) 1233169689Skan /* Wrap SUCCN into single block region. */ 1234169689Skan { 1235169689Skan RGN_BLOCKS (nr_regions) = idx; 1236169689Skan RGN_NR_BLOCKS (nr_regions) = 1; 1237169689Skan RGN_DONT_CALC_DEPS (nr_regions) = 0; 1238169689Skan RGN_HAS_REAL_EBB (nr_regions) = 0; 1239169689Skan nr_regions++; 1240169689Skan } 1241169689Skan 1242169689Skan idx++; 1243169689Skan 1244169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (succn)->succs) 1245169689Skan if (e->dest != EXIT_BLOCK_PTR) 1246169689Skan degree[e->dest->index]--; 1247169689Skan } 1248169689Skan } 1249169689Skan 1250169689Skan if (!large) 1251169689Skan { 1252169689Skan RGN_NR_BLOCKS (nr_regions) = num_bbs; 1253169689Skan nr_regions++; 1254169689Skan } 1255169689Skan } 1256169689Skan } 1257169689Skan 1258169689Skan if (sched_verbose >= 6) 1259169689Skan { 1260169689Skan int *s2, s2_sz; 1261169689Skan 1262169689Skan /* Get the new statistics and print the comparison with the 1263169689Skan one before calling this function. */ 1264169689Skan s2_sz = gather_region_statistics (&s2); 1265169689Skan print_region_statistics (s1, s1_sz, s2, s2_sz); 1266169689Skan free (s1); 1267169689Skan free (s2); 1268169689Skan } 1269169689Skan } 1270169689Skan 1271169689Skan free (order); 1272169689Skan free (max_hdr); 1273169689Skan 1274169689Skan *idxp = idx; 1275169689Skan} 1276169689Skan 127790075Sobrien/* Functions for regions scheduling information. */ 127890075Sobrien 127990075Sobrien/* Compute dominators, probability, and potential-split-edges of bb. 128090075Sobrien Assume that these values were already computed for bb's predecessors. */ 128190075Sobrien 128290075Sobrienstatic void 1283132718Skancompute_dom_prob_ps (int bb) 128490075Sobrien{ 1285169689Skan edge_iterator in_ei; 1286169689Skan edge in_edge; 128790075Sobrien 1288169689Skan /* We shouldn't have any real ebbs yet. */ 1289169689Skan gcc_assert (ebb_head [bb] == bb + current_blocks); 1290169689Skan 129190075Sobrien if (IS_RGN_ENTRY (bb)) 129290075Sobrien { 129390075Sobrien SET_BIT (dom[bb], 0); 1294169689Skan prob[bb] = REG_BR_PROB_BASE; 129590075Sobrien return; 129690075Sobrien } 129790075Sobrien 1298169689Skan prob[bb] = 0; 129990075Sobrien 130090075Sobrien /* Initialize dom[bb] to '111..1'. */ 130190075Sobrien sbitmap_ones (dom[bb]); 130290075Sobrien 1303169689Skan FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds) 130490075Sobrien { 1305169689Skan int pred_bb; 1306169689Skan edge out_edge; 1307169689Skan edge_iterator out_ei; 130890075Sobrien 1309169689Skan if (in_edge->src == ENTRY_BLOCK_PTR) 1310169689Skan continue; 131190075Sobrien 1312169689Skan pred_bb = BLOCK_TO_BB (in_edge->src->index); 1313169689Skan sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]); 1314169689Skan sbitmap_a_or_b (ancestor_edges[bb], 1315169689Skan ancestor_edges[bb], ancestor_edges[pred_bb]); 131690075Sobrien 1317169689Skan SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge)); 131890075Sobrien 1319169689Skan sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]); 132090075Sobrien 1321169689Skan FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs) 1322169689Skan SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge)); 132390075Sobrien 1324169689Skan prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE); 132590075Sobrien } 132690075Sobrien 132790075Sobrien SET_BIT (dom[bb], bb); 132890075Sobrien sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]); 132990075Sobrien 133090075Sobrien if (sched_verbose >= 2) 133190075Sobrien fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), 1332169689Skan (100 * prob[bb]) / REG_BR_PROB_BASE); 133390075Sobrien} 133490075Sobrien 133590075Sobrien/* Functions for target info. */ 133690075Sobrien 133790075Sobrien/* Compute in BL the list of split-edges of bb_src relatively to bb_trg. 133890075Sobrien Note that bb_trg dominates bb_src. */ 133990075Sobrien 134090075Sobrienstatic void 1341132718Skansplit_edges (int bb_src, int bb_trg, edgelst *bl) 134290075Sobrien{ 1343132718Skan sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits); 134490075Sobrien sbitmap_copy (src, pot_split[bb_src]); 134590075Sobrien 134690075Sobrien sbitmap_difference (src, src, pot_split[bb_trg]); 1347169689Skan extract_edgelst (src, bl); 134890075Sobrien sbitmap_free (src); 134990075Sobrien} 135090075Sobrien 135190075Sobrien/* Find the valid candidate-source-blocks for the target block TRG, compute 135290075Sobrien their probability, and check if they are speculative or not. 135390075Sobrien For speculative sources, compute their update-blocks and split-blocks. */ 135490075Sobrien 135590075Sobrienstatic void 1356132718Skancompute_trg_info (int trg) 135790075Sobrien{ 135890075Sobrien candidate *sp; 135990075Sobrien edgelst el; 1360169689Skan int i, j, k, update_idx; 1361169689Skan basic_block block; 1362169689Skan sbitmap visited; 1363169689Skan edge_iterator ei; 1364169689Skan edge e; 136590075Sobrien 136690075Sobrien /* Define some of the fields for the target bb as well. */ 136790075Sobrien sp = candidate_table + trg; 136890075Sobrien sp->is_valid = 1; 136990075Sobrien sp->is_speculative = 0; 1370169689Skan sp->src_prob = REG_BR_PROB_BASE; 137190075Sobrien 1372169689Skan visited = sbitmap_alloc (last_basic_block); 1373169689Skan 137490075Sobrien for (i = trg + 1; i < current_nr_blocks; i++) 137590075Sobrien { 137690075Sobrien sp = candidate_table + i; 137790075Sobrien 137890075Sobrien sp->is_valid = IS_DOMINATED (i, trg); 137990075Sobrien if (sp->is_valid) 138090075Sobrien { 1381169689Skan int tf = prob[trg], cf = prob[i]; 1382169689Skan 1383169689Skan /* In CFGs with low probability edges TF can possibly be zero. */ 1384169689Skan sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0); 1385169689Skan sp->is_valid = (sp->src_prob >= min_spec_prob); 138690075Sobrien } 138790075Sobrien 138890075Sobrien if (sp->is_valid) 138990075Sobrien { 139090075Sobrien split_edges (i, trg, &el); 139190075Sobrien sp->is_speculative = (el.nr_members) ? 1 : 0; 139290075Sobrien if (sp->is_speculative && !flag_schedule_speculative) 139390075Sobrien sp->is_valid = 0; 139490075Sobrien } 139590075Sobrien 139690075Sobrien if (sp->is_valid) 139790075Sobrien { 139890075Sobrien /* Compute split blocks and store them in bblst_table. 139990075Sobrien The TO block of every split edge is a split block. */ 140090075Sobrien sp->split_bbs.first_member = &bblst_table[bblst_last]; 140190075Sobrien sp->split_bbs.nr_members = el.nr_members; 140290075Sobrien for (j = 0; j < el.nr_members; bblst_last++, j++) 1403169689Skan bblst_table[bblst_last] = el.first_member[j]->dest; 140490075Sobrien sp->update_bbs.first_member = &bblst_table[bblst_last]; 140590075Sobrien 140690075Sobrien /* Compute update blocks and store them in bblst_table. 140790075Sobrien For every split edge, look at the FROM block, and check 140890075Sobrien all out edges. For each out edge that is not a split edge, 140990075Sobrien add the TO block to the update block list. This list can end 141090075Sobrien up with a lot of duplicates. We need to weed them out to avoid 141190075Sobrien overrunning the end of the bblst_table. */ 141290075Sobrien 141390075Sobrien update_idx = 0; 1414169689Skan sbitmap_zero (visited); 141590075Sobrien for (j = 0; j < el.nr_members; j++) 141690075Sobrien { 1417169689Skan block = el.first_member[j]->src; 1418169689Skan FOR_EACH_EDGE (e, ei, block->succs) 141990075Sobrien { 1420169689Skan if (!TEST_BIT (visited, e->dest->index)) 142190075Sobrien { 142290075Sobrien for (k = 0; k < el.nr_members; k++) 1423169689Skan if (e == el.first_member[k]) 142490075Sobrien break; 142590075Sobrien 142690075Sobrien if (k >= el.nr_members) 142790075Sobrien { 1428169689Skan bblst_table[bblst_last++] = e->dest; 1429169689Skan SET_BIT (visited, e->dest->index); 143090075Sobrien update_idx++; 143190075Sobrien } 143290075Sobrien } 143390075Sobrien } 143490075Sobrien } 143590075Sobrien sp->update_bbs.nr_members = update_idx; 143690075Sobrien 143790075Sobrien /* Make sure we didn't overrun the end of bblst_table. */ 1438169689Skan gcc_assert (bblst_last <= bblst_size); 143990075Sobrien } 144090075Sobrien else 144190075Sobrien { 144290075Sobrien sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0; 144390075Sobrien 144490075Sobrien sp->is_speculative = 0; 144590075Sobrien sp->src_prob = 0; 144690075Sobrien } 144790075Sobrien } 1448169689Skan 1449169689Skan sbitmap_free (visited); 145090075Sobrien} 145190075Sobrien 145290075Sobrien/* Print candidates info, for debugging purposes. Callable from debugger. */ 145390075Sobrien 145490075Sobrienvoid 1455132718Skandebug_candidate (int i) 145690075Sobrien{ 145790075Sobrien if (!candidate_table[i].is_valid) 145890075Sobrien return; 145990075Sobrien 146090075Sobrien if (candidate_table[i].is_speculative) 146190075Sobrien { 146290075Sobrien int j; 146390075Sobrien fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i); 146490075Sobrien 146590075Sobrien fprintf (sched_dump, "split path: "); 146690075Sobrien for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++) 146790075Sobrien { 1468169689Skan int b = candidate_table[i].split_bbs.first_member[j]->index; 146990075Sobrien 147090075Sobrien fprintf (sched_dump, " %d ", b); 147190075Sobrien } 147290075Sobrien fprintf (sched_dump, "\n"); 147390075Sobrien 147490075Sobrien fprintf (sched_dump, "update path: "); 147590075Sobrien for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++) 147690075Sobrien { 1477169689Skan int b = candidate_table[i].update_bbs.first_member[j]->index; 147890075Sobrien 147990075Sobrien fprintf (sched_dump, " %d ", b); 148090075Sobrien } 148190075Sobrien fprintf (sched_dump, "\n"); 148290075Sobrien } 148390075Sobrien else 148490075Sobrien { 148590075Sobrien fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i)); 148690075Sobrien } 148790075Sobrien} 148890075Sobrien 148990075Sobrien/* Print candidates info, for debugging purposes. Callable from debugger. */ 149090075Sobrien 149190075Sobrienvoid 1492132718Skandebug_candidates (int trg) 149390075Sobrien{ 149490075Sobrien int i; 149590075Sobrien 149690075Sobrien fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n", 149790075Sobrien BB_TO_BLOCK (trg), trg); 149890075Sobrien for (i = trg + 1; i < current_nr_blocks; i++) 149990075Sobrien debug_candidate (i); 150090075Sobrien} 150190075Sobrien 1502132718Skan/* Functions for speculative scheduling. */ 150390075Sobrien 150490075Sobrien/* Return 0 if x is a set of a register alive in the beginning of one 150590075Sobrien of the split-blocks of src, otherwise return 1. */ 150690075Sobrien 150790075Sobrienstatic int 1508132718Skancheck_live_1 (int src, rtx x) 150990075Sobrien{ 151090075Sobrien int i; 151190075Sobrien int regno; 151290075Sobrien rtx reg = SET_DEST (x); 151390075Sobrien 151490075Sobrien if (reg == 0) 151590075Sobrien return 1; 151690075Sobrien 1517169689Skan while (GET_CODE (reg) == SUBREG 1518169689Skan || GET_CODE (reg) == ZERO_EXTRACT 151990075Sobrien || GET_CODE (reg) == STRICT_LOW_PART) 152090075Sobrien reg = XEXP (reg, 0); 152190075Sobrien 152290075Sobrien if (GET_CODE (reg) == PARALLEL) 152390075Sobrien { 152490075Sobrien int i; 152590075Sobrien 152690075Sobrien for (i = XVECLEN (reg, 0) - 1; i >= 0; i--) 152790075Sobrien if (XEXP (XVECEXP (reg, 0, i), 0) != 0) 152890075Sobrien if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0))) 152990075Sobrien return 1; 153090075Sobrien 153190075Sobrien return 0; 153290075Sobrien } 153390075Sobrien 1534169689Skan if (!REG_P (reg)) 153590075Sobrien return 1; 153690075Sobrien 153790075Sobrien regno = REGNO (reg); 153890075Sobrien 153990075Sobrien if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 154090075Sobrien { 154190075Sobrien /* Global registers are assumed live. */ 154290075Sobrien return 0; 154390075Sobrien } 154490075Sobrien else 154590075Sobrien { 154690075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 154790075Sobrien { 154890075Sobrien /* Check for hard registers. */ 1549169689Skan int j = hard_regno_nregs[regno][GET_MODE (reg)]; 155090075Sobrien while (--j >= 0) 155190075Sobrien { 155290075Sobrien for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++) 155390075Sobrien { 1554169689Skan basic_block b = candidate_table[src].split_bbs.first_member[i]; 155590075Sobrien 1556169689Skan /* We can have split blocks, that were recently generated. 1557169689Skan such blocks are always outside current region. */ 1558169689Skan gcc_assert (glat_start[b->index] 1559169689Skan || CONTAINING_RGN (b->index) 1560169689Skan != CONTAINING_RGN (BB_TO_BLOCK (src))); 1561169689Skan if (!glat_start[b->index] 1562169689Skan || REGNO_REG_SET_P (glat_start[b->index], 1563169689Skan regno + j)) 156490075Sobrien { 156590075Sobrien return 0; 156690075Sobrien } 156790075Sobrien } 156890075Sobrien } 156990075Sobrien } 157090075Sobrien else 157190075Sobrien { 1572132718Skan /* Check for pseudo registers. */ 157390075Sobrien for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++) 157490075Sobrien { 1575169689Skan basic_block b = candidate_table[src].split_bbs.first_member[i]; 157690075Sobrien 1577169689Skan gcc_assert (glat_start[b->index] 1578169689Skan || CONTAINING_RGN (b->index) 1579169689Skan != CONTAINING_RGN (BB_TO_BLOCK (src))); 1580169689Skan if (!glat_start[b->index] 1581169689Skan || REGNO_REG_SET_P (glat_start[b->index], regno)) 158290075Sobrien { 158390075Sobrien return 0; 158490075Sobrien } 158590075Sobrien } 158690075Sobrien } 158790075Sobrien } 158890075Sobrien 158990075Sobrien return 1; 159090075Sobrien} 159190075Sobrien 159290075Sobrien/* If x is a set of a register R, mark that R is alive in the beginning 159390075Sobrien of every update-block of src. */ 159490075Sobrien 159590075Sobrienstatic void 1596132718Skanupdate_live_1 (int src, rtx x) 159790075Sobrien{ 159890075Sobrien int i; 159990075Sobrien int regno; 160090075Sobrien rtx reg = SET_DEST (x); 160190075Sobrien 160290075Sobrien if (reg == 0) 160390075Sobrien return; 160490075Sobrien 1605169689Skan while (GET_CODE (reg) == SUBREG 1606169689Skan || GET_CODE (reg) == ZERO_EXTRACT 160790075Sobrien || GET_CODE (reg) == STRICT_LOW_PART) 160890075Sobrien reg = XEXP (reg, 0); 160990075Sobrien 161090075Sobrien if (GET_CODE (reg) == PARALLEL) 161190075Sobrien { 161290075Sobrien int i; 161390075Sobrien 161490075Sobrien for (i = XVECLEN (reg, 0) - 1; i >= 0; i--) 161590075Sobrien if (XEXP (XVECEXP (reg, 0, i), 0) != 0) 161690075Sobrien update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)); 161790075Sobrien 161890075Sobrien return; 161990075Sobrien } 162090075Sobrien 1621169689Skan if (!REG_P (reg)) 162290075Sobrien return; 162390075Sobrien 162490075Sobrien /* Global registers are always live, so the code below does not apply 162590075Sobrien to them. */ 162690075Sobrien 162790075Sobrien regno = REGNO (reg); 162890075Sobrien 162990075Sobrien if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno]) 163090075Sobrien { 163190075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 163290075Sobrien { 1633169689Skan int j = hard_regno_nregs[regno][GET_MODE (reg)]; 163490075Sobrien while (--j >= 0) 163590075Sobrien { 163690075Sobrien for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++) 163790075Sobrien { 1638169689Skan basic_block b = candidate_table[src].update_bbs.first_member[i]; 163990075Sobrien 1640169689Skan SET_REGNO_REG_SET (glat_start[b->index], regno + j); 164190075Sobrien } 164290075Sobrien } 164390075Sobrien } 164490075Sobrien else 164590075Sobrien { 164690075Sobrien for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++) 164790075Sobrien { 1648169689Skan basic_block b = candidate_table[src].update_bbs.first_member[i]; 164990075Sobrien 1650169689Skan SET_REGNO_REG_SET (glat_start[b->index], regno); 165190075Sobrien } 165290075Sobrien } 165390075Sobrien } 165490075Sobrien} 165590075Sobrien 165690075Sobrien/* Return 1 if insn can be speculatively moved from block src to trg, 165790075Sobrien otherwise return 0. Called before first insertion of insn to 165890075Sobrien ready-list or before the scheduling. */ 165990075Sobrien 166090075Sobrienstatic int 1661132718Skancheck_live (rtx insn, int src) 166290075Sobrien{ 166390075Sobrien /* Find the registers set by instruction. */ 166490075Sobrien if (GET_CODE (PATTERN (insn)) == SET 166590075Sobrien || GET_CODE (PATTERN (insn)) == CLOBBER) 166690075Sobrien return check_live_1 (src, PATTERN (insn)); 166790075Sobrien else if (GET_CODE (PATTERN (insn)) == PARALLEL) 166890075Sobrien { 166990075Sobrien int j; 167090075Sobrien for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) 167190075Sobrien if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET 167290075Sobrien || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) 167390075Sobrien && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j))) 167490075Sobrien return 0; 167590075Sobrien 167690075Sobrien return 1; 167790075Sobrien } 167890075Sobrien 167990075Sobrien return 1; 168090075Sobrien} 168190075Sobrien 168290075Sobrien/* Update the live registers info after insn was moved speculatively from 168390075Sobrien block src to trg. */ 168490075Sobrien 168590075Sobrienstatic void 1686132718Skanupdate_live (rtx insn, int src) 168790075Sobrien{ 168890075Sobrien /* Find the registers set by instruction. */ 168990075Sobrien if (GET_CODE (PATTERN (insn)) == SET 169090075Sobrien || GET_CODE (PATTERN (insn)) == CLOBBER) 169190075Sobrien update_live_1 (src, PATTERN (insn)); 169290075Sobrien else if (GET_CODE (PATTERN (insn)) == PARALLEL) 169390075Sobrien { 169490075Sobrien int j; 169590075Sobrien for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) 169690075Sobrien if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET 169790075Sobrien || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) 169890075Sobrien update_live_1 (src, XVECEXP (PATTERN (insn), 0, j)); 169990075Sobrien } 170090075Sobrien} 170190075Sobrien 1702132718Skan/* Nonzero if block bb_to is equal to, or reachable from block bb_from. */ 170390075Sobrien#define IS_REACHABLE(bb_from, bb_to) \ 1704117395Skan (bb_from == bb_to \ 170590075Sobrien || IS_RGN_ENTRY (bb_from) \ 1706117395Skan || (TEST_BIT (ancestor_edges[bb_to], \ 1707169689Skan EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from))))))) 170890075Sobrien 170990075Sobrien/* Turns on the fed_by_spec_load flag for insns fed by load_insn. */ 171090075Sobrien 171190075Sobrienstatic void 1712132718Skanset_spec_fed (rtx load_insn) 171390075Sobrien{ 171490075Sobrien rtx link; 171590075Sobrien 171690075Sobrien for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1)) 171790075Sobrien if (GET_MODE (link) == VOIDmode) 171890075Sobrien FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1; 171990075Sobrien} /* set_spec_fed */ 172090075Sobrien 172190075Sobrien/* On the path from the insn to load_insn_bb, find a conditional 172290075Sobrienbranch depending on insn, that guards the speculative load. */ 172390075Sobrien 172490075Sobrienstatic int 1725132718Skanfind_conditional_protection (rtx insn, int load_insn_bb) 172690075Sobrien{ 172790075Sobrien rtx link; 172890075Sobrien 172990075Sobrien /* Iterate through DEF-USE forward dependences. */ 173090075Sobrien for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) 173190075Sobrien { 173290075Sobrien rtx next = XEXP (link, 0); 173390075Sobrien if ((CONTAINING_RGN (BLOCK_NUM (next)) == 173490075Sobrien CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb))) 173590075Sobrien && IS_REACHABLE (INSN_BB (next), load_insn_bb) 173690075Sobrien && load_insn_bb != INSN_BB (next) 173790075Sobrien && GET_MODE (link) == VOIDmode 1738169689Skan && (JUMP_P (next) 173990075Sobrien || find_conditional_protection (next, load_insn_bb))) 174090075Sobrien return 1; 174190075Sobrien } 174290075Sobrien return 0; 174390075Sobrien} /* find_conditional_protection */ 174490075Sobrien 174590075Sobrien/* Returns 1 if the same insn1 that participates in the computation 174690075Sobrien of load_insn's address is feeding a conditional branch that is 174790075Sobrien guarding on load_insn. This is true if we find a the two DEF-USE 174890075Sobrien chains: 174990075Sobrien insn1 -> ... -> conditional-branch 175090075Sobrien insn1 -> ... -> load_insn, 175190075Sobrien and if a flow path exist: 175290075Sobrien insn1 -> ... -> conditional-branch -> ... -> load_insn, 175390075Sobrien and if insn1 is on the path 175490075Sobrien region-entry -> ... -> bb_trg -> ... load_insn. 175590075Sobrien 175690075Sobrien Locate insn1 by climbing on LOG_LINKS from load_insn. 175790075Sobrien Locate the branch by following INSN_DEPEND from insn1. */ 175890075Sobrien 175990075Sobrienstatic int 1760132718Skanis_conditionally_protected (rtx load_insn, int bb_src, int bb_trg) 176190075Sobrien{ 176290075Sobrien rtx link; 176390075Sobrien 176490075Sobrien for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1)) 176590075Sobrien { 176690075Sobrien rtx insn1 = XEXP (link, 0); 176790075Sobrien 176890075Sobrien /* Must be a DEF-USE dependence upon non-branch. */ 176990075Sobrien if (GET_MODE (link) != VOIDmode 1770169689Skan || JUMP_P (insn1)) 177190075Sobrien continue; 177290075Sobrien 177390075Sobrien /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */ 177490075Sobrien if (INSN_BB (insn1) == bb_src 177590075Sobrien || (CONTAINING_RGN (BLOCK_NUM (insn1)) 177690075Sobrien != CONTAINING_RGN (BB_TO_BLOCK (bb_src))) 177790075Sobrien || (!IS_REACHABLE (bb_trg, INSN_BB (insn1)) 177890075Sobrien && !IS_REACHABLE (INSN_BB (insn1), bb_trg))) 177990075Sobrien continue; 178090075Sobrien 178190075Sobrien /* Now search for the conditional-branch. */ 178290075Sobrien if (find_conditional_protection (insn1, bb_src)) 178390075Sobrien return 1; 178490075Sobrien 178590075Sobrien /* Recursive step: search another insn1, "above" current insn1. */ 178690075Sobrien return is_conditionally_protected (insn1, bb_src, bb_trg); 178790075Sobrien } 178890075Sobrien 178990075Sobrien /* The chain does not exist. */ 179090075Sobrien return 0; 179190075Sobrien} /* is_conditionally_protected */ 179290075Sobrien 179390075Sobrien/* Returns 1 if a clue for "similar load" 'insn2' is found, and hence 179490075Sobrien load_insn can move speculatively from bb_src to bb_trg. All the 179590075Sobrien following must hold: 179690075Sobrien 179790075Sobrien (1) both loads have 1 base register (PFREE_CANDIDATEs). 179890075Sobrien (2) load_insn and load1 have a def-use dependence upon 179990075Sobrien the same insn 'insn1'. 180090075Sobrien (3) either load2 is in bb_trg, or: 180190075Sobrien - there's only one split-block, and 180290075Sobrien - load1 is on the escape path, and 180390075Sobrien 180490075Sobrien From all these we can conclude that the two loads access memory 180590075Sobrien addresses that differ at most by a constant, and hence if moving 180690075Sobrien load_insn would cause an exception, it would have been caused by 180790075Sobrien load2 anyhow. */ 180890075Sobrien 180990075Sobrienstatic int 1810132718Skanis_pfree (rtx load_insn, int bb_src, int bb_trg) 181190075Sobrien{ 181290075Sobrien rtx back_link; 181390075Sobrien candidate *candp = candidate_table + bb_src; 181490075Sobrien 181590075Sobrien if (candp->split_bbs.nr_members != 1) 181690075Sobrien /* Must have exactly one escape block. */ 181790075Sobrien return 0; 181890075Sobrien 181990075Sobrien for (back_link = LOG_LINKS (load_insn); 182090075Sobrien back_link; back_link = XEXP (back_link, 1)) 182190075Sobrien { 182290075Sobrien rtx insn1 = XEXP (back_link, 0); 182390075Sobrien 182490075Sobrien if (GET_MODE (back_link) == VOIDmode) 182590075Sobrien { 182690075Sobrien /* Found a DEF-USE dependence (insn1, load_insn). */ 182790075Sobrien rtx fore_link; 182890075Sobrien 182990075Sobrien for (fore_link = INSN_DEPEND (insn1); 183090075Sobrien fore_link; fore_link = XEXP (fore_link, 1)) 183190075Sobrien { 183290075Sobrien rtx insn2 = XEXP (fore_link, 0); 183390075Sobrien if (GET_MODE (fore_link) == VOIDmode) 183490075Sobrien { 183590075Sobrien /* Found a DEF-USE dependence (insn1, insn2). */ 183690075Sobrien if (haifa_classify_insn (insn2) != PFREE_CANDIDATE) 183790075Sobrien /* insn2 not guaranteed to be a 1 base reg load. */ 183890075Sobrien continue; 183990075Sobrien 184090075Sobrien if (INSN_BB (insn2) == bb_trg) 184190075Sobrien /* insn2 is the similar load, in the target block. */ 184290075Sobrien return 1; 184390075Sobrien 1844169689Skan if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2)) 184590075Sobrien /* insn2 is a similar load, in a split-block. */ 184690075Sobrien return 1; 184790075Sobrien } 184890075Sobrien } 184990075Sobrien } 185090075Sobrien } 185190075Sobrien 185290075Sobrien /* Couldn't find a similar load. */ 185390075Sobrien return 0; 185490075Sobrien} /* is_pfree */ 185590075Sobrien 185690075Sobrien/* Return 1 if load_insn is prisky (i.e. if load_insn is fed by 185790075Sobrien a load moved speculatively, or if load_insn is protected by 185890075Sobrien a compare on load_insn's address). */ 185990075Sobrien 186090075Sobrienstatic int 1861132718Skanis_prisky (rtx load_insn, int bb_src, int bb_trg) 186290075Sobrien{ 186390075Sobrien if (FED_BY_SPEC_LOAD (load_insn)) 186490075Sobrien return 1; 186590075Sobrien 186690075Sobrien if (LOG_LINKS (load_insn) == NULL) 186790075Sobrien /* Dependence may 'hide' out of the region. */ 186890075Sobrien return 1; 186990075Sobrien 187090075Sobrien if (is_conditionally_protected (load_insn, bb_src, bb_trg)) 187190075Sobrien return 1; 187290075Sobrien 187390075Sobrien return 0; 187490075Sobrien} 187590075Sobrien 187690075Sobrien/* Insn is a candidate to be moved speculatively from bb_src to bb_trg. 187790075Sobrien Return 1 if insn is exception-free (and the motion is valid) 187890075Sobrien and 0 otherwise. */ 187990075Sobrien 188090075Sobrienstatic int 1881132718Skanis_exception_free (rtx insn, int bb_src, int bb_trg) 188290075Sobrien{ 188390075Sobrien int insn_class = haifa_classify_insn (insn); 188490075Sobrien 188590075Sobrien /* Handle non-load insns. */ 188690075Sobrien switch (insn_class) 188790075Sobrien { 188890075Sobrien case TRAP_FREE: 188990075Sobrien return 1; 189090075Sobrien case TRAP_RISKY: 189190075Sobrien return 0; 189290075Sobrien default:; 189390075Sobrien } 189490075Sobrien 189590075Sobrien /* Handle loads. */ 189690075Sobrien if (!flag_schedule_speculative_load) 189790075Sobrien return 0; 189890075Sobrien IS_LOAD_INSN (insn) = 1; 189990075Sobrien switch (insn_class) 190090075Sobrien { 190190075Sobrien case IFREE: 190290075Sobrien return (1); 190390075Sobrien case IRISKY: 190490075Sobrien return 0; 190590075Sobrien case PFREE_CANDIDATE: 190690075Sobrien if (is_pfree (insn, bb_src, bb_trg)) 190790075Sobrien return 1; 190890075Sobrien /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */ 190990075Sobrien case PRISKY_CANDIDATE: 191090075Sobrien if (!flag_schedule_speculative_load_dangerous 191190075Sobrien || is_prisky (insn, bb_src, bb_trg)) 191290075Sobrien return 0; 191390075Sobrien break; 191490075Sobrien default:; 191590075Sobrien } 191690075Sobrien 191790075Sobrien return flag_schedule_speculative_load_dangerous; 191890075Sobrien} 191990075Sobrien 192090075Sobrien/* The number of insns from the current block scheduled so far. */ 192190075Sobrienstatic int sched_target_n_insns; 192290075Sobrien/* The number of insns from the current block to be scheduled in total. */ 192390075Sobrienstatic int target_n_insns; 192490075Sobrien/* The number of insns from the entire region scheduled so far. */ 192590075Sobrienstatic int sched_n_insns; 192690075Sobrien 192790075Sobrien/* Implementations of the sched_info functions for region scheduling. */ 1928169689Skanstatic void init_ready_list (void); 1929132718Skanstatic int can_schedule_ready_p (rtx); 1930169689Skanstatic void begin_schedule_ready (rtx, rtx); 1931169689Skanstatic ds_t new_ready (rtx, ds_t); 1932132718Skanstatic int schedule_more_p (void); 1933132718Skanstatic const char *rgn_print_insn (rtx, int); 1934132718Skanstatic int rgn_rank (rtx, rtx); 1935132718Skanstatic int contributes_to_priority (rtx, rtx); 1936132718Skanstatic void compute_jump_reg_dependencies (rtx, regset, regset, regset); 193790075Sobrien 1938169689Skan/* Functions for speculative scheduling. */ 1939169689Skanstatic void add_remove_insn (rtx, int); 1940169689Skanstatic void extend_regions (void); 1941169689Skanstatic void add_block1 (basic_block, basic_block); 1942169689Skanstatic void fix_recovery_cfg (int, int, int); 1943169689Skanstatic basic_block advance_target_bb (basic_block, rtx); 1944169689Skanstatic void check_dead_notes1 (int, sbitmap); 1945169689Skan#ifdef ENABLE_CHECKING 1946169689Skanstatic int region_head_or_leaf_p (basic_block, int); 1947169689Skan#endif 1948169689Skan 194990075Sobrien/* Return nonzero if there are more insns that should be scheduled. */ 195090075Sobrien 195190075Sobrienstatic int 1952132718Skanschedule_more_p (void) 195390075Sobrien{ 1954169689Skan return sched_target_n_insns < target_n_insns; 195590075Sobrien} 195690075Sobrien 195790075Sobrien/* Add all insns that are initially ready to the ready list READY. Called 195890075Sobrien once before scheduling a set of insns. */ 195990075Sobrien 196090075Sobrienstatic void 1961169689Skaninit_ready_list (void) 196290075Sobrien{ 196390075Sobrien rtx prev_head = current_sched_info->prev_head; 196490075Sobrien rtx next_tail = current_sched_info->next_tail; 196590075Sobrien int bb_src; 196690075Sobrien rtx insn; 196790075Sobrien 196890075Sobrien target_n_insns = 0; 196990075Sobrien sched_target_n_insns = 0; 197090075Sobrien sched_n_insns = 0; 197190075Sobrien 197290075Sobrien /* Print debugging information. */ 197390075Sobrien if (sched_verbose >= 5) 197490075Sobrien debug_dependencies (); 197590075Sobrien 197690075Sobrien /* Prepare current target block info. */ 197790075Sobrien if (current_nr_blocks > 1) 197890075Sobrien { 1979169689Skan candidate_table = XNEWVEC (candidate, current_nr_blocks); 198090075Sobrien 198190075Sobrien bblst_last = 0; 198290075Sobrien /* bblst_table holds split blocks and update blocks for each block after 198390075Sobrien the current one in the region. split blocks and update blocks are 198490075Sobrien the TO blocks of region edges, so there can be at most rgn_nr_edges 198590075Sobrien of them. */ 198690075Sobrien bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges; 1987169689Skan bblst_table = XNEWVEC (basic_block, bblst_size); 198890075Sobrien 1989169689Skan edgelst_last = 0; 1990169689Skan edgelst_table = XNEWVEC (edge, rgn_nr_edges); 199190075Sobrien 199290075Sobrien compute_trg_info (target_bb); 199390075Sobrien } 199490075Sobrien 199590075Sobrien /* Initialize ready list with all 'ready' insns in target block. 199690075Sobrien Count number of insns in the target block being scheduled. */ 199790075Sobrien for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn)) 1998169689Skan { 1999169689Skan try_ready (insn); 2000169689Skan target_n_insns++; 200190075Sobrien 2002169689Skan gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL)); 200390075Sobrien } 200490075Sobrien 200590075Sobrien /* Add to ready list all 'ready' insns in valid source blocks. 200690075Sobrien For speculative insns, check-live, exception-free, and 200790075Sobrien issue-delay. */ 200890075Sobrien for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++) 200990075Sobrien if (IS_VALID (bb_src)) 201090075Sobrien { 201190075Sobrien rtx src_head; 201290075Sobrien rtx src_next_tail; 201390075Sobrien rtx tail, head; 201490075Sobrien 2015169689Skan get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src), 2016169689Skan &head, &tail); 201790075Sobrien src_next_tail = NEXT_INSN (tail); 201890075Sobrien src_head = head; 201990075Sobrien 202090075Sobrien for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn)) 2021169689Skan if (INSN_P (insn)) 2022169689Skan try_ready (insn); 202390075Sobrien } 202490075Sobrien} 202590075Sobrien 202690075Sobrien/* Called after taking INSN from the ready list. Returns nonzero if this 202790075Sobrien insn can be scheduled, nonzero if we should silently discard it. */ 202890075Sobrien 202990075Sobrienstatic int 2030132718Skancan_schedule_ready_p (rtx insn) 203190075Sobrien{ 2032169689Skan /* An interblock motion? */ 2033169689Skan if (INSN_BB (insn) != target_bb 2034169689Skan && IS_SPECULATIVE_INSN (insn) 2035169689Skan && !check_live (insn, INSN_BB (insn))) 2036169689Skan return 0; 2037169689Skan else 2038169689Skan return 1; 2039169689Skan} 204090075Sobrien 2041169689Skan/* Updates counter and other information. Split from can_schedule_ready_p () 2042169689Skan because when we schedule insn speculatively then insn passed to 2043169689Skan can_schedule_ready_p () differs from the one passed to 2044169689Skan begin_schedule_ready (). */ 2045169689Skanstatic void 2046169689Skanbegin_schedule_ready (rtx insn, rtx last ATTRIBUTE_UNUSED) 2047169689Skan{ 204890075Sobrien /* An interblock motion? */ 204990075Sobrien if (INSN_BB (insn) != target_bb) 205090075Sobrien { 205190075Sobrien if (IS_SPECULATIVE_INSN (insn)) 205290075Sobrien { 2053169689Skan gcc_assert (check_live (insn, INSN_BB (insn))); 2054169689Skan 205590075Sobrien update_live (insn, INSN_BB (insn)); 205690075Sobrien 205790075Sobrien /* For speculative load, mark insns fed by it. */ 205890075Sobrien if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn)) 205990075Sobrien set_spec_fed (insn); 206090075Sobrien 206190075Sobrien nr_spec++; 206290075Sobrien } 206390075Sobrien nr_inter++; 206490075Sobrien } 206590075Sobrien else 206690075Sobrien { 206790075Sobrien /* In block motion. */ 206890075Sobrien sched_target_n_insns++; 206990075Sobrien } 207090075Sobrien sched_n_insns++; 207190075Sobrien} 207290075Sobrien 2073169689Skan/* Called after INSN has all its hard dependencies resolved and the speculation 2074169689Skan of type TS is enough to overcome them all. 2075169689Skan Return nonzero if it should be moved to the ready list or the queue, or zero 2076169689Skan if we should silently discard it. */ 2077169689Skanstatic ds_t 2078169689Skannew_ready (rtx next, ds_t ts) 207990075Sobrien{ 2080169689Skan if (INSN_BB (next) != target_bb) 2081169689Skan { 2082169689Skan int not_ex_free = 0; 2083169689Skan 2084169689Skan /* For speculative insns, before inserting to ready/queue, 2085169689Skan check live, exception-free, and issue-delay. */ 2086169689Skan if (!IS_VALID (INSN_BB (next)) 208790075Sobrien || CANT_MOVE (next) 208890075Sobrien || (IS_SPECULATIVE_INSN (next) 2089169689Skan && ((recog_memoized (next) >= 0 2090169689Skan && min_insn_conflict_delay (curr_state, next, next) 2091169689Skan > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY)) 2092169689Skan || IS_SPECULATION_CHECK_P (next) 209390075Sobrien || !check_live (next, INSN_BB (next)) 2094169689Skan || (not_ex_free = !is_exception_free (next, INSN_BB (next), 2095169689Skan target_bb))))) 2096169689Skan { 2097169689Skan if (not_ex_free 2098169689Skan /* We are here because is_exception_free () == false. 2099169689Skan But we possibly can handle that with control speculation. */ 2100169689Skan && current_sched_info->flags & DO_SPECULATION) 2101169689Skan /* Here we got new control-speculative instruction. */ 2102169689Skan ts = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK); 2103169689Skan else 2104169689Skan ts = (ts & ~SPECULATIVE) | HARD_DEP; 2105169689Skan } 2106169689Skan } 2107169689Skan 2108169689Skan return ts; 210990075Sobrien} 211090075Sobrien 211190075Sobrien/* Return a string that contains the insn uid and optionally anything else 211290075Sobrien necessary to identify this insn in an output. It's valid to use a 211390075Sobrien static buffer for this. The ALIGNED parameter should cause the string 211490075Sobrien to be formatted so that multiple output lines will line up nicely. */ 211590075Sobrien 211690075Sobrienstatic const char * 2117132718Skanrgn_print_insn (rtx insn, int aligned) 211890075Sobrien{ 211990075Sobrien static char tmp[80]; 212090075Sobrien 212190075Sobrien if (aligned) 212290075Sobrien sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn)); 212390075Sobrien else 212490075Sobrien { 212590075Sobrien if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb) 212690075Sobrien sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn)); 212790075Sobrien else 212890075Sobrien sprintf (tmp, "%d", INSN_UID (insn)); 212990075Sobrien } 213090075Sobrien return tmp; 213190075Sobrien} 213290075Sobrien 213390075Sobrien/* Compare priority of two insns. Return a positive number if the second 213490075Sobrien insn is to be preferred for scheduling, and a negative one if the first 213590075Sobrien is to be preferred. Zero if they are equally good. */ 213690075Sobrien 213790075Sobrienstatic int 2138132718Skanrgn_rank (rtx insn1, rtx insn2) 213990075Sobrien{ 214090075Sobrien /* Some comparison make sense in interblock scheduling only. */ 214190075Sobrien if (INSN_BB (insn1) != INSN_BB (insn2)) 214290075Sobrien { 214390075Sobrien int spec_val, prob_val; 214490075Sobrien 214590075Sobrien /* Prefer an inblock motion on an interblock motion. */ 214690075Sobrien if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb)) 214790075Sobrien return 1; 214890075Sobrien if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb)) 214990075Sobrien return -1; 215090075Sobrien 215190075Sobrien /* Prefer a useful motion on a speculative one. */ 215290075Sobrien spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2); 215390075Sobrien if (spec_val) 215490075Sobrien return spec_val; 215590075Sobrien 215690075Sobrien /* Prefer a more probable (speculative) insn. */ 215790075Sobrien prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1); 215890075Sobrien if (prob_val) 215990075Sobrien return prob_val; 216090075Sobrien } 216190075Sobrien return 0; 216290075Sobrien} 216390075Sobrien 216490075Sobrien/* NEXT is an instruction that depends on INSN (a backward dependence); 216590075Sobrien return nonzero if we should include this dependence in priority 216690075Sobrien calculations. */ 216790075Sobrien 216890075Sobrienstatic int 2169132718Skancontributes_to_priority (rtx next, rtx insn) 217090075Sobrien{ 2171169689Skan /* NEXT and INSN reside in one ebb. */ 2172169689Skan return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn)); 217390075Sobrien} 217490075Sobrien 2175119256Skan/* INSN is a JUMP_INSN, COND_SET is the set of registers that are 2176119256Skan conditionally set before INSN. Store the set of registers that 2177119256Skan must be considered as used by this jump in USED and that of 2178119256Skan registers that must be considered as set in SET. */ 217990075Sobrien 218090075Sobrienstatic void 2181132718Skancompute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED, 2182132718Skan regset cond_exec ATTRIBUTE_UNUSED, 2183132718Skan regset used ATTRIBUTE_UNUSED, 2184132718Skan regset set ATTRIBUTE_UNUSED) 218590075Sobrien{ 218690075Sobrien /* Nothing to do here, since we postprocess jumps in 218790075Sobrien add_branch_dependences. */ 218890075Sobrien} 218990075Sobrien 219090075Sobrien/* Used in schedule_insns to initialize current_sched_info for scheduling 219190075Sobrien regions (or single basic blocks). */ 219290075Sobrien 219390075Sobrienstatic struct sched_info region_sched_info = 219490075Sobrien{ 219590075Sobrien init_ready_list, 219690075Sobrien can_schedule_ready_p, 219790075Sobrien schedule_more_p, 219890075Sobrien new_ready, 219990075Sobrien rgn_rank, 220090075Sobrien rgn_print_insn, 220190075Sobrien contributes_to_priority, 220290075Sobrien compute_jump_reg_dependencies, 220390075Sobrien 220490075Sobrien NULL, NULL, 220590075Sobrien NULL, NULL, 2206169689Skan 0, 0, 0, 2207169689Skan 2208169689Skan add_remove_insn, 2209169689Skan begin_schedule_ready, 2210169689Skan add_block1, 2211169689Skan advance_target_bb, 2212169689Skan fix_recovery_cfg, 2213169689Skan#ifdef ENABLE_CHECKING 2214169689Skan region_head_or_leaf_p, 2215169689Skan#endif 2216169689Skan SCHED_RGN | USE_GLAT 2217169689Skan#ifdef ENABLE_CHECKING 2218169689Skan | DETACH_LIFE_INFO 2219169689Skan#endif 222090075Sobrien}; 222190075Sobrien 222296263Sobrien/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */ 222396263Sobrien 222496263Sobrienstatic bool 2225132718Skansets_likely_spilled (rtx pat) 222696263Sobrien{ 222796263Sobrien bool ret = false; 222896263Sobrien note_stores (pat, sets_likely_spilled_1, &ret); 222996263Sobrien return ret; 223096263Sobrien} 223196263Sobrien 223296263Sobrienstatic void 2233132718Skansets_likely_spilled_1 (rtx x, rtx pat, void *data) 223496263Sobrien{ 223596263Sobrien bool *ret = (bool *) data; 223696263Sobrien 223796263Sobrien if (GET_CODE (pat) == SET 223896263Sobrien && REG_P (x) 223996263Sobrien && REGNO (x) < FIRST_PSEUDO_REGISTER 224096263Sobrien && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x)))) 224196263Sobrien *ret = true; 224296263Sobrien} 224396263Sobrien 224490075Sobrien/* Add dependences so that branches are scheduled to run last in their 224590075Sobrien block. */ 224690075Sobrien 224790075Sobrienstatic void 2248132718Skanadd_branch_dependences (rtx head, rtx tail) 224990075Sobrien{ 225090075Sobrien rtx insn, last; 225190075Sobrien 225296263Sobrien /* For all branches, calls, uses, clobbers, cc0 setters, and instructions 225396263Sobrien that can throw exceptions, force them to remain in order at the end of 225496263Sobrien the block by adding dependencies and giving the last a high priority. 225596263Sobrien There may be notes present, and prev_head may also be a note. 225690075Sobrien 225790075Sobrien Branches must obviously remain at the end. Calls should remain at the 225890075Sobrien end since moving them results in worse register allocation. Uses remain 225996263Sobrien at the end to ensure proper register allocation. 226096263Sobrien 2261132718Skan cc0 setters remain at the end because they can't be moved away from 226296263Sobrien their cc0 user. 226396263Sobrien 2264169689Skan COND_EXEC insns cannot be moved past a branch (see e.g. PR17808). 2265169689Skan 226696263Sobrien Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values) 226796263Sobrien are not moved before reload because we can wind up with register 226896263Sobrien allocation failures. */ 226996263Sobrien 227090075Sobrien insn = tail; 227190075Sobrien last = 0; 2272169689Skan while (CALL_P (insn) 2273169689Skan || JUMP_P (insn) 2274169689Skan || (NONJUMP_INSN_P (insn) 227590075Sobrien && (GET_CODE (PATTERN (insn)) == USE 227690075Sobrien || GET_CODE (PATTERN (insn)) == CLOBBER 227796263Sobrien || can_throw_internal (insn) 227890075Sobrien#ifdef HAVE_cc0 227990075Sobrien || sets_cc0_p (PATTERN (insn)) 228090075Sobrien#endif 228196263Sobrien || (!reload_completed 228296263Sobrien && sets_likely_spilled (PATTERN (insn))))) 2283169689Skan || NOTE_P (insn)) 228490075Sobrien { 2285169689Skan if (!NOTE_P (insn)) 228690075Sobrien { 228790075Sobrien if (last != 0 && !find_insn_list (insn, LOG_LINKS (last))) 228890075Sobrien { 2289169689Skan if (! sched_insns_conditions_mutex_p (last, insn)) 2290169689Skan add_dependence (last, insn, REG_DEP_ANTI); 229190075Sobrien INSN_REF_COUNT (insn)++; 229290075Sobrien } 229390075Sobrien 229490075Sobrien CANT_MOVE (insn) = 1; 229590075Sobrien 229690075Sobrien last = insn; 229790075Sobrien } 229890075Sobrien 229990075Sobrien /* Don't overrun the bounds of the basic block. */ 230090075Sobrien if (insn == head) 230190075Sobrien break; 230290075Sobrien 230390075Sobrien insn = PREV_INSN (insn); 230490075Sobrien } 230590075Sobrien 230690075Sobrien /* Make sure these insns are scheduled last in their block. */ 230790075Sobrien insn = last; 230890075Sobrien if (insn != 0) 230990075Sobrien while (insn != head) 231090075Sobrien { 231190075Sobrien insn = prev_nonnote_insn (insn); 231290075Sobrien 231390075Sobrien if (INSN_REF_COUNT (insn) != 0) 231490075Sobrien continue; 231590075Sobrien 2316169689Skan if (! sched_insns_conditions_mutex_p (last, insn)) 2317169689Skan add_dependence (last, insn, REG_DEP_ANTI); 231890075Sobrien INSN_REF_COUNT (insn) = 1; 231990075Sobrien } 2320169689Skan 2321169689Skan#ifdef HAVE_conditional_execution 2322169689Skan /* Finally, if the block ends in a jump, and we are doing intra-block 2323169689Skan scheduling, make sure that the branch depends on any COND_EXEC insns 2324169689Skan inside the block to avoid moving the COND_EXECs past the branch insn. 2325169689Skan 2326169689Skan We only have to do this after reload, because (1) before reload there 2327169689Skan are no COND_EXEC insns, and (2) the region scheduler is an intra-block 2328169689Skan scheduler after reload. 2329169689Skan 2330169689Skan FIXME: We could in some cases move COND_EXEC insns past the branch if 2331169689Skan this scheduler would be a little smarter. Consider this code: 2332169689Skan 2333169689Skan T = [addr] 2334169689Skan C ? addr += 4 2335169689Skan !C ? X += 12 2336169689Skan C ? T += 1 2337169689Skan C ? jump foo 2338169689Skan 2339169689Skan On a target with a one cycle stall on a memory access the optimal 2340169689Skan sequence would be: 2341169689Skan 2342169689Skan T = [addr] 2343169689Skan C ? addr += 4 2344169689Skan C ? T += 1 2345169689Skan C ? jump foo 2346169689Skan !C ? X += 12 2347169689Skan 2348169689Skan We don't want to put the 'X += 12' before the branch because it just 2349169689Skan wastes a cycle of execution time when the branch is taken. 2350169689Skan 2351169689Skan Note that in the example "!C" will always be true. That is another 2352169689Skan possible improvement for handling COND_EXECs in this scheduler: it 2353169689Skan could remove always-true predicates. */ 2354169689Skan 2355169689Skan if (!reload_completed || ! JUMP_P (tail)) 2356169689Skan return; 2357169689Skan 2358169689Skan insn = tail; 2359169689Skan while (insn != head) 2360169689Skan { 2361169689Skan insn = PREV_INSN (insn); 2362169689Skan 2363169689Skan /* Note that we want to add this dependency even when 2364169689Skan sched_insns_conditions_mutex_p returns true. The whole point 2365169689Skan is that we _want_ this dependency, even if these insns really 2366169689Skan are independent. */ 2367169689Skan if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC) 2368169689Skan add_dependence (tail, insn, REG_DEP_ANTI); 2369169689Skan } 2370169689Skan#endif 237190075Sobrien} 237290075Sobrien 237390075Sobrien/* Data structures for the computation of data dependences in a regions. We 237490075Sobrien keep one `deps' structure for every basic block. Before analyzing the 237590075Sobrien data dependences for a bb, its variables are initialized as a function of 237690075Sobrien the variables of its predecessors. When the analysis for a bb completes, 237790075Sobrien we save the contents to the corresponding bb_deps[bb] variable. */ 237890075Sobrien 237990075Sobrienstatic struct deps *bb_deps; 238090075Sobrien 238190075Sobrien/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */ 238290075Sobrien 238390075Sobrienstatic rtx 2384132718Skanconcat_INSN_LIST (rtx copy, rtx old) 238590075Sobrien{ 238690075Sobrien rtx new = old; 238790075Sobrien for (; copy ; copy = XEXP (copy, 1)) 238890075Sobrien new = alloc_INSN_LIST (XEXP (copy, 0), new); 238990075Sobrien return new; 239090075Sobrien} 239190075Sobrien 239290075Sobrienstatic void 2393132718Skanconcat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p, 2394132718Skan rtx *old_mems_p) 239590075Sobrien{ 239690075Sobrien rtx new_insns = *old_insns_p; 239790075Sobrien rtx new_mems = *old_mems_p; 239890075Sobrien 239990075Sobrien while (copy_insns) 240090075Sobrien { 240190075Sobrien new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns); 240290075Sobrien new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems); 240390075Sobrien copy_insns = XEXP (copy_insns, 1); 240490075Sobrien copy_mems = XEXP (copy_mems, 1); 240590075Sobrien } 240690075Sobrien 240790075Sobrien *old_insns_p = new_insns; 240890075Sobrien *old_mems_p = new_mems; 240990075Sobrien} 241090075Sobrien 241190075Sobrien/* After computing the dependencies for block BB, propagate the dependencies 241290075Sobrien found in TMP_DEPS to the successors of the block. */ 241390075Sobrienstatic void 2414132718Skanpropagate_deps (int bb, struct deps *pred_deps) 241590075Sobrien{ 2416169689Skan basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb)); 2417169689Skan edge_iterator ei; 2418169689Skan edge e; 241990075Sobrien 242090075Sobrien /* bb's structures are inherited by its successors. */ 2421169689Skan FOR_EACH_EDGE (e, ei, block->succs) 2422169689Skan { 2423169689Skan struct deps *succ_deps; 2424169689Skan unsigned reg; 2425169689Skan reg_set_iterator rsi; 242690075Sobrien 2427169689Skan /* Only bbs "below" bb, in the same region, are interesting. */ 2428169689Skan if (e->dest == EXIT_BLOCK_PTR 2429169689Skan || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index) 2430169689Skan || BLOCK_TO_BB (e->dest->index) <= bb) 2431169689Skan continue; 243290075Sobrien 2433169689Skan succ_deps = bb_deps + BLOCK_TO_BB (e->dest->index); 243490075Sobrien 2435169689Skan /* The reg_last lists are inherited by successor. */ 2436169689Skan EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi) 2437169689Skan { 2438169689Skan struct deps_reg *pred_rl = &pred_deps->reg_last[reg]; 2439169689Skan struct deps_reg *succ_rl = &succ_deps->reg_last[reg]; 244090075Sobrien 2441169689Skan succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses); 2442169689Skan succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets); 2443169689Skan succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers, 2444169689Skan succ_rl->clobbers); 2445169689Skan succ_rl->uses_length += pred_rl->uses_length; 2446169689Skan succ_rl->clobbers_length += pred_rl->clobbers_length; 2447169689Skan } 2448169689Skan IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use); 244990075Sobrien 2450169689Skan /* Mem read/write lists are inherited by successor. */ 2451169689Skan concat_insn_mem_list (pred_deps->pending_read_insns, 2452169689Skan pred_deps->pending_read_mems, 2453169689Skan &succ_deps->pending_read_insns, 2454169689Skan &succ_deps->pending_read_mems); 2455169689Skan concat_insn_mem_list (pred_deps->pending_write_insns, 2456169689Skan pred_deps->pending_write_mems, 2457169689Skan &succ_deps->pending_write_insns, 2458169689Skan &succ_deps->pending_write_mems); 2459117395Skan 2460169689Skan succ_deps->last_pending_memory_flush 2461169689Skan = concat_INSN_LIST (pred_deps->last_pending_memory_flush, 2462169689Skan succ_deps->last_pending_memory_flush); 246390075Sobrien 2464169689Skan succ_deps->pending_lists_length += pred_deps->pending_lists_length; 2465169689Skan succ_deps->pending_flush_length += pred_deps->pending_flush_length; 2466169689Skan 2467169689Skan /* last_function_call is inherited by successor. */ 2468169689Skan succ_deps->last_function_call 2469169689Skan = concat_INSN_LIST (pred_deps->last_function_call, 247090075Sobrien succ_deps->last_function_call); 247190075Sobrien 2472169689Skan /* sched_before_next_call is inherited by successor. */ 2473169689Skan succ_deps->sched_before_next_call 2474169689Skan = concat_INSN_LIST (pred_deps->sched_before_next_call, 2475169689Skan succ_deps->sched_before_next_call); 2476169689Skan } 247790075Sobrien 247890075Sobrien /* These lists should point to the right place, for correct 247990075Sobrien freeing later. */ 248090075Sobrien bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns; 248190075Sobrien bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems; 248290075Sobrien bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns; 248390075Sobrien bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems; 248490075Sobrien 248590075Sobrien /* Can't allow these to be freed twice. */ 248690075Sobrien pred_deps->pending_read_insns = 0; 248790075Sobrien pred_deps->pending_read_mems = 0; 248890075Sobrien pred_deps->pending_write_insns = 0; 248990075Sobrien pred_deps->pending_write_mems = 0; 249090075Sobrien} 249190075Sobrien 249290075Sobrien/* Compute backward dependences inside bb. In a multiple blocks region: 249390075Sobrien (1) a bb is analyzed after its predecessors, and (2) the lists in 249490075Sobrien effect at the end of bb (after analyzing for bb) are inherited by 2495132718Skan bb's successors. 249690075Sobrien 249790075Sobrien Specifically for reg-reg data dependences, the block insns are 249890075Sobrien scanned by sched_analyze () top-to-bottom. Two lists are 249990075Sobrien maintained by sched_analyze (): reg_last[].sets for register DEFs, 250090075Sobrien and reg_last[].uses for register USEs. 250190075Sobrien 250290075Sobrien When analysis is completed for bb, we update for its successors: 250390075Sobrien ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb]) 250490075Sobrien ; - USES[succ] = Union (USES [succ], DEFS [bb]) 250590075Sobrien 250690075Sobrien The mechanism for computing mem-mem data dependence is very 250790075Sobrien similar, and the result is interblock dependences in the region. */ 250890075Sobrien 250990075Sobrienstatic void 2510132718Skancompute_block_backward_dependences (int bb) 251190075Sobrien{ 251290075Sobrien rtx head, tail; 251390075Sobrien struct deps tmp_deps; 251490075Sobrien 251590075Sobrien tmp_deps = bb_deps[bb]; 251690075Sobrien 251790075Sobrien /* Do the analysis for this block. */ 2518169689Skan gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb)); 2519169689Skan get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail); 252090075Sobrien sched_analyze (&tmp_deps, head, tail); 252190075Sobrien add_branch_dependences (head, tail); 252290075Sobrien 252390075Sobrien if (current_nr_blocks > 1) 252490075Sobrien propagate_deps (bb, &tmp_deps); 252590075Sobrien 252690075Sobrien /* Free up the INSN_LISTs. */ 252790075Sobrien free_deps (&tmp_deps); 252890075Sobrien} 252990075Sobrien 253090075Sobrien/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add 253190075Sobrien them to the unused_*_list variables, so that they can be reused. */ 253290075Sobrien 253390075Sobrienstatic void 2534132718Skanfree_pending_lists (void) 253590075Sobrien{ 253690075Sobrien int bb; 253790075Sobrien 253890075Sobrien for (bb = 0; bb < current_nr_blocks; bb++) 253990075Sobrien { 254090075Sobrien free_INSN_LIST_list (&bb_deps[bb].pending_read_insns); 254190075Sobrien free_INSN_LIST_list (&bb_deps[bb].pending_write_insns); 254290075Sobrien free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems); 254390075Sobrien free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems); 254490075Sobrien } 254590075Sobrien} 254690075Sobrien 254790075Sobrien/* Print dependences for debugging, callable from debugger. */ 254890075Sobrien 254990075Sobrienvoid 2550132718Skandebug_dependencies (void) 255190075Sobrien{ 255290075Sobrien int bb; 255390075Sobrien 255490075Sobrien fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n"); 255590075Sobrien for (bb = 0; bb < current_nr_blocks; bb++) 255690075Sobrien { 2557169689Skan rtx head, tail; 2558169689Skan rtx next_tail; 2559169689Skan rtx insn; 256090075Sobrien 2561169689Skan gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb)); 2562169689Skan get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail); 2563169689Skan next_tail = NEXT_INSN (tail); 2564169689Skan fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n", 2565169689Skan BB_TO_BLOCK (bb), bb); 256690075Sobrien 2567169689Skan fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n", 2568169689Skan "insn", "code", "bb", "dep", "prio", "cost", 2569169689Skan "reservation"); 2570169689Skan fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n", 2571169689Skan "----", "----", "--", "---", "----", "----", 2572169689Skan "-----------"); 2573117395Skan 2574169689Skan for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 2575169689Skan { 2576169689Skan rtx link; 2577169689Skan 2578169689Skan if (! INSN_P (insn)) 257990075Sobrien { 2580169689Skan int n; 2581169689Skan fprintf (sched_dump, ";; %6d ", INSN_UID (insn)); 2582169689Skan if (NOTE_P (insn)) 258390075Sobrien { 2584169689Skan n = NOTE_LINE_NUMBER (insn); 2585169689Skan if (n < 0) 2586169689Skan fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n)); 2587169689Skan else 258890075Sobrien { 2589169689Skan expanded_location xloc; 2590169689Skan NOTE_EXPANDED_LOCATION (xloc, insn); 2591169689Skan fprintf (sched_dump, "line %d, file %s\n", 2592169689Skan xloc.line, xloc.file); 259390075Sobrien } 259490075Sobrien } 2595169689Skan else 2596169689Skan fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn))); 2597169689Skan continue; 2598169689Skan } 259990075Sobrien 2600169689Skan fprintf (sched_dump, 2601169689Skan ";; %s%5d%6d%6d%6d%6d%6d ", 2602169689Skan (SCHED_GROUP_P (insn) ? "+" : " "), 2603169689Skan INSN_UID (insn), 2604169689Skan INSN_CODE (insn), 2605169689Skan INSN_BB (insn), 2606169689Skan INSN_DEP_COUNT (insn), 2607169689Skan INSN_PRIORITY (insn), 2608169689Skan insn_cost (insn, 0, 0)); 2609117395Skan 2610169689Skan if (recog_memoized (insn) < 0) 2611169689Skan fprintf (sched_dump, "nothing"); 2612169689Skan else 2613169689Skan print_reservation (sched_dump, insn); 2614117395Skan 2615169689Skan fprintf (sched_dump, "\t: "); 2616169689Skan for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) 2617169689Skan fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0))); 2618169689Skan fprintf (sched_dump, "\n"); 261990075Sobrien } 262090075Sobrien } 262190075Sobrien fprintf (sched_dump, "\n"); 262290075Sobrien} 262390075Sobrien 2624169689Skan/* Returns true if all the basic blocks of the current region have 2625169689Skan NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */ 2626169689Skanstatic bool 2627169689Skansched_is_disabled_for_current_region_p (void) 2628169689Skan{ 2629169689Skan int bb; 2630169689Skan 2631169689Skan for (bb = 0; bb < current_nr_blocks; bb++) 2632169689Skan if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE)) 2633169689Skan return false; 2634169689Skan 2635169689Skan return true; 2636169689Skan} 2637169689Skan 263890075Sobrien/* Schedule a region. A region is either an inner loop, a loop-free 263990075Sobrien subroutine, or a single basic block. Each bb in the region is 264090075Sobrien scheduled after its flow predecessors. */ 264190075Sobrien 264290075Sobrienstatic void 2643132718Skanschedule_region (int rgn) 264490075Sobrien{ 2645169689Skan basic_block block; 2646169689Skan edge_iterator ei; 2647169689Skan edge e; 264890075Sobrien int bb; 264990075Sobrien int sched_rgn_n_insns = 0; 265090075Sobrien 2651169689Skan rgn_n_insns = 0; 265290075Sobrien /* Set variables for the current region. */ 265390075Sobrien current_nr_blocks = RGN_NR_BLOCKS (rgn); 265490075Sobrien current_blocks = RGN_BLOCKS (rgn); 2655169689Skan 2656169689Skan /* See comments in add_block1, for what reasons we allocate +1 element. */ 2657169689Skan ebb_head = xrealloc (ebb_head, (current_nr_blocks + 1) * sizeof (*ebb_head)); 2658169689Skan for (bb = 0; bb <= current_nr_blocks; bb++) 2659169689Skan ebb_head[bb] = current_blocks + bb; 266090075Sobrien 2661169689Skan /* Don't schedule region that is marked by 2662169689Skan NOTE_DISABLE_SCHED_OF_BLOCK. */ 2663169689Skan if (sched_is_disabled_for_current_region_p ()) 2664169689Skan return; 266590075Sobrien 2666169689Skan if (!RGN_DONT_CALC_DEPS (rgn)) 2667169689Skan { 2668169689Skan init_deps_global (); 266990075Sobrien 2670169689Skan /* Initializations for region data dependence analysis. */ 2671169689Skan bb_deps = XNEWVEC (struct deps, current_nr_blocks); 2672169689Skan for (bb = 0; bb < current_nr_blocks; bb++) 2673169689Skan init_deps (bb_deps + bb); 267490075Sobrien 2675169689Skan /* Compute LOG_LINKS. */ 2676169689Skan for (bb = 0; bb < current_nr_blocks; bb++) 2677169689Skan compute_block_backward_dependences (bb); 267890075Sobrien 2679169689Skan /* Compute INSN_DEPEND. */ 2680169689Skan for (bb = current_nr_blocks - 1; bb >= 0; bb--) 2681169689Skan { 2682169689Skan rtx head, tail; 2683132718Skan 2684169689Skan gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb)); 2685169689Skan get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail); 2686132718Skan 2687169689Skan compute_forward_dependences (head, tail); 2688169689Skan 2689169689Skan if (targetm.sched.dependencies_evaluation_hook) 2690169689Skan targetm.sched.dependencies_evaluation_hook (head, tail); 2691169689Skan } 2692169689Skan 2693169689Skan free_pending_lists (); 2694169689Skan 2695169689Skan finish_deps_global (); 2696169689Skan 2697169689Skan free (bb_deps); 269890075Sobrien } 2699169689Skan else 2700169689Skan /* This is a recovery block. It is always a single block region. */ 2701169689Skan gcc_assert (current_nr_blocks == 1); 2702169689Skan 270390075Sobrien /* Set priorities. */ 2704169689Skan current_sched_info->sched_max_insns_priority = 0; 270590075Sobrien for (bb = 0; bb < current_nr_blocks; bb++) 270690075Sobrien { 270790075Sobrien rtx head, tail; 2708169689Skan 2709169689Skan gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb)); 2710169689Skan get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail); 271190075Sobrien 271290075Sobrien rgn_n_insns += set_priorities (head, tail); 271390075Sobrien } 2714169689Skan current_sched_info->sched_max_insns_priority++; 271590075Sobrien 271690075Sobrien /* Compute interblock info: probabilities, split-edges, dominators, etc. */ 271790075Sobrien if (current_nr_blocks > 1) 271890075Sobrien { 2719169689Skan prob = XNEWVEC (int, current_nr_blocks); 272090075Sobrien 272190075Sobrien dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks); 272290075Sobrien sbitmap_vector_zero (dom, current_nr_blocks); 2723169689Skan 2724169689Skan /* Use ->aux to implement EDGE_TO_BIT mapping. */ 272590075Sobrien rgn_nr_edges = 0; 2726169689Skan FOR_EACH_BB (block) 2727169689Skan { 2728169689Skan if (CONTAINING_RGN (block->index) != rgn) 2729169689Skan continue; 2730169689Skan FOR_EACH_EDGE (e, ei, block->succs) 2731169689Skan SET_EDGE_TO_BIT (e, rgn_nr_edges++); 2732169689Skan } 273390075Sobrien 2734169689Skan rgn_edges = XNEWVEC (edge, rgn_nr_edges); 273590075Sobrien rgn_nr_edges = 0; 2736169689Skan FOR_EACH_BB (block) 2737169689Skan { 2738169689Skan if (CONTAINING_RGN (block->index) != rgn) 2739169689Skan continue; 2740169689Skan FOR_EACH_EDGE (e, ei, block->succs) 2741169689Skan rgn_edges[rgn_nr_edges++] = e; 2742169689Skan } 274390075Sobrien 274490075Sobrien /* Split edges. */ 274590075Sobrien pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges); 274690075Sobrien sbitmap_vector_zero (pot_split, current_nr_blocks); 274790075Sobrien ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges); 274890075Sobrien sbitmap_vector_zero (ancestor_edges, current_nr_blocks); 274990075Sobrien 275090075Sobrien /* Compute probabilities, dominators, split_edges. */ 275190075Sobrien for (bb = 0; bb < current_nr_blocks; bb++) 275290075Sobrien compute_dom_prob_ps (bb); 2753169689Skan 2754169689Skan /* Cleanup ->aux used for EDGE_TO_BIT mapping. */ 2755169689Skan /* We don't need them anymore. But we want to avoid duplication of 2756169689Skan aux fields in the newly created edges. */ 2757169689Skan FOR_EACH_BB (block) 2758169689Skan { 2759169689Skan if (CONTAINING_RGN (block->index) != rgn) 2760169689Skan continue; 2761169689Skan FOR_EACH_EDGE (e, ei, block->succs) 2762169689Skan e->aux = NULL; 2763169689Skan } 276490075Sobrien } 276590075Sobrien 276690075Sobrien /* Now we can schedule all blocks. */ 276790075Sobrien for (bb = 0; bb < current_nr_blocks; bb++) 276890075Sobrien { 2769169689Skan basic_block first_bb, last_bb, curr_bb; 277090075Sobrien rtx head, tail; 277190075Sobrien int b = BB_TO_BLOCK (bb); 277290075Sobrien 2773169689Skan first_bb = EBB_FIRST_BB (bb); 2774169689Skan last_bb = EBB_LAST_BB (bb); 277590075Sobrien 2776169689Skan get_ebb_head_tail (first_bb, last_bb, &head, &tail); 2777169689Skan 277890075Sobrien if (no_real_insns_p (head, tail)) 2779169689Skan { 2780169689Skan gcc_assert (first_bb == last_bb); 2781169689Skan continue; 2782169689Skan } 278390075Sobrien 278490075Sobrien current_sched_info->prev_head = PREV_INSN (head); 278590075Sobrien current_sched_info->next_tail = NEXT_INSN (tail); 278690075Sobrien 278790075Sobrien if (write_symbols != NO_DEBUG) 278890075Sobrien { 278990075Sobrien save_line_notes (b, head, tail); 279090075Sobrien rm_line_notes (head, tail); 279190075Sobrien } 279290075Sobrien 279390075Sobrien /* rm_other_notes only removes notes which are _inside_ the 279490075Sobrien block---that is, it won't remove notes before the first real insn 2795132718Skan or after the last real insn of the block. So if the first insn 279690075Sobrien has a REG_SAVE_NOTE which would otherwise be emitted before the 279790075Sobrien insn, it is redundant with the note before the start of the 279890075Sobrien block, and so we have to take it out. */ 279990075Sobrien if (INSN_P (head)) 280090075Sobrien { 280190075Sobrien rtx note; 280290075Sobrien 280390075Sobrien for (note = REG_NOTES (head); note; note = XEXP (note, 1)) 280490075Sobrien if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 2805169689Skan remove_note (head, note); 280690075Sobrien } 2807169689Skan else 2808169689Skan /* This means that first block in ebb is empty. 2809169689Skan It looks to me as an impossible thing. There at least should be 2810169689Skan a recovery check, that caused the splitting. */ 2811169689Skan gcc_unreachable (); 281290075Sobrien 281390075Sobrien /* Remove remaining note insns from the block, save them in 281490075Sobrien note_list. These notes are restored at the end of 281590075Sobrien schedule_block (). */ 281690075Sobrien rm_other_notes (head, tail); 281790075Sobrien 2818169689Skan unlink_bb_notes (first_bb, last_bb); 2819169689Skan 282090075Sobrien target_bb = bb; 282190075Sobrien 2822169689Skan gcc_assert (flag_schedule_interblock || current_nr_blocks == 1); 2823169689Skan current_sched_info->queue_must_finish_empty = current_nr_blocks == 1; 282490075Sobrien 2825169689Skan curr_bb = first_bb; 2826169689Skan schedule_block (&curr_bb, rgn_n_insns); 2827169689Skan gcc_assert (EBB_FIRST_BB (bb) == first_bb); 282890075Sobrien sched_rgn_n_insns += sched_n_insns; 282990075Sobrien 283090075Sobrien /* Clean up. */ 283190075Sobrien if (current_nr_blocks > 1) 283290075Sobrien { 283390075Sobrien free (candidate_table); 283490075Sobrien free (bblst_table); 2835169689Skan free (edgelst_table); 283690075Sobrien } 283790075Sobrien } 283890075Sobrien 283990075Sobrien /* Sanity check: verify that all region insns were scheduled. */ 2840169689Skan gcc_assert (sched_rgn_n_insns == rgn_n_insns); 284190075Sobrien 284290075Sobrien /* Restore line notes. */ 284390075Sobrien if (write_symbols != NO_DEBUG) 284490075Sobrien { 284590075Sobrien for (bb = 0; bb < current_nr_blocks; bb++) 284690075Sobrien { 284790075Sobrien rtx head, tail; 2848169689Skan 2849169689Skan get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail); 285090075Sobrien restore_line_notes (head, tail); 285190075Sobrien } 285290075Sobrien } 285390075Sobrien 285490075Sobrien /* Done with this region. */ 285590075Sobrien 285690075Sobrien if (current_nr_blocks > 1) 285790075Sobrien { 285890075Sobrien free (prob); 285990075Sobrien sbitmap_vector_free (dom); 286090075Sobrien sbitmap_vector_free (pot_split); 286190075Sobrien sbitmap_vector_free (ancestor_edges); 286290075Sobrien free (rgn_edges); 286390075Sobrien } 286490075Sobrien} 286590075Sobrien 286690075Sobrien/* Indexed by region, holds the number of death notes found in that region. 286790075Sobrien Used for consistency checks. */ 286890075Sobrienstatic int *deaths_in_region; 286990075Sobrien 287090075Sobrien/* Initialize data structures for region scheduling. */ 287190075Sobrien 287290075Sobrienstatic void 2873132718Skaninit_regions (void) 287490075Sobrien{ 287590075Sobrien sbitmap blocks; 287690075Sobrien int rgn; 287790075Sobrien 287890075Sobrien nr_regions = 0; 2879169689Skan rgn_table = 0; 2880169689Skan rgn_bb_table = 0; 2881169689Skan block_to_bb = 0; 2882169689Skan containing_rgn = 0; 2883169689Skan extend_regions (); 288490075Sobrien 288590075Sobrien /* Compute regions for scheduling. */ 288690075Sobrien if (reload_completed 2887169689Skan || n_basic_blocks == NUM_FIXED_BLOCKS + 1 2888169689Skan || !flag_schedule_interblock 2889169689Skan || is_cfg_nonregular ()) 289090075Sobrien { 289190075Sobrien find_single_block_region (); 289290075Sobrien } 289390075Sobrien else 289490075Sobrien { 2895169689Skan /* Compute the dominators and post dominators. */ 2896169689Skan calculate_dominance_info (CDI_DOMINATORS); 289790075Sobrien 2898169689Skan /* Find regions. */ 2899169689Skan find_rgns (); 290090075Sobrien 2901169689Skan if (sched_verbose >= 3) 2902169689Skan debug_regions (); 290390075Sobrien 2904169689Skan /* For now. This will move as more and more of haifa is converted 2905169689Skan to using the cfg code in flow.c. */ 2906169689Skan free_dominance_info (CDI_DOMINATORS); 290790075Sobrien } 2908169689Skan RGN_BLOCKS (nr_regions) = RGN_BLOCKS (nr_regions - 1) + 2909169689Skan RGN_NR_BLOCKS (nr_regions - 1); 291090075Sobrien 291190075Sobrien 291290075Sobrien if (CHECK_DEAD_NOTES) 291390075Sobrien { 2914117395Skan blocks = sbitmap_alloc (last_basic_block); 2915169689Skan deaths_in_region = XNEWVEC (int, nr_regions); 291690075Sobrien /* Remove all death notes from the subroutine. */ 291790075Sobrien for (rgn = 0; rgn < nr_regions; rgn++) 2918169689Skan check_dead_notes1 (rgn, blocks); 291990075Sobrien 292090075Sobrien sbitmap_free (blocks); 292190075Sobrien } 292290075Sobrien else 292390075Sobrien count_or_remove_death_notes (NULL, 1); 292490075Sobrien} 292590075Sobrien 2926169689Skan/* The one entry point in this file. */ 292790075Sobrien 292890075Sobrienvoid 2929169689Skanschedule_insns (void) 293090075Sobrien{ 293190075Sobrien sbitmap large_region_blocks, blocks; 293290075Sobrien int rgn; 293390075Sobrien int any_large_regions; 2934117395Skan basic_block bb; 293590075Sobrien 293690075Sobrien /* Taking care of this degenerate case makes the rest of 293790075Sobrien this code simpler. */ 2938169689Skan if (n_basic_blocks == NUM_FIXED_BLOCKS) 293990075Sobrien return; 294090075Sobrien 294190075Sobrien nr_inter = 0; 294290075Sobrien nr_spec = 0; 294390075Sobrien 2944169689Skan /* We need current_sched_info in init_dependency_caches, which is 2945169689Skan invoked via sched_init. */ 2946169689Skan current_sched_info = ®ion_sched_info; 294790075Sobrien 2948169689Skan sched_init (); 2949169689Skan 2950169689Skan min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE) 2951169689Skan / 100); 2952169689Skan 295390075Sobrien init_regions (); 295490075Sobrien 2955169689Skan /* EBB_HEAD is a region-scope structure. But we realloc it for 2956169689Skan each region to save time/memory/something else. */ 2957169689Skan ebb_head = 0; 2958169689Skan 295990075Sobrien /* Schedule every region in the subroutine. */ 296090075Sobrien for (rgn = 0; rgn < nr_regions; rgn++) 296190075Sobrien schedule_region (rgn); 2962169689Skan 2963169689Skan free(ebb_head); 296490075Sobrien 296590075Sobrien /* Update life analysis for the subroutine. Do single block regions 296690075Sobrien first so that we can verify that live_at_start didn't change. Then 296790075Sobrien do all other blocks. */ 296890075Sobrien /* ??? There is an outside possibility that update_life_info, or more 2969117395Skan to the point propagate_block, could get called with nonzero flags 297090075Sobrien more than once for one basic block. This would be kinda bad if it 297190075Sobrien were to happen, since REG_INFO would be accumulated twice for the 297290075Sobrien block, and we'd have twice the REG_DEAD notes. 297390075Sobrien 297490075Sobrien I'm fairly certain that this _shouldn't_ happen, since I don't think 297590075Sobrien that live_at_start should change at region heads. Not sure what the 297690075Sobrien best way to test for this kind of thing... */ 297790075Sobrien 2978169689Skan if (current_sched_info->flags & DETACH_LIFE_INFO) 2979169689Skan /* this flag can be set either by the target or by ENABLE_CHECKING. */ 2980169689Skan attach_life_info (); 2981169689Skan 298290075Sobrien allocate_reg_life_data (); 298390075Sobrien 298490075Sobrien any_large_regions = 0; 2985117395Skan large_region_blocks = sbitmap_alloc (last_basic_block); 2986117395Skan sbitmap_zero (large_region_blocks); 2987117395Skan FOR_EACH_BB (bb) 2988117395Skan SET_BIT (large_region_blocks, bb->index); 298990075Sobrien 2990117395Skan blocks = sbitmap_alloc (last_basic_block); 299190075Sobrien sbitmap_zero (blocks); 299290075Sobrien 299390075Sobrien /* Update life information. For regions consisting of multiple blocks 299490075Sobrien we've possibly done interblock scheduling that affects global liveness. 299590075Sobrien For regions consisting of single blocks we need to do only local 299690075Sobrien liveness. */ 2997169689Skan for (rgn = 0; rgn < nr_regions; rgn++) 2998169689Skan if (RGN_NR_BLOCKS (rgn) > 1 2999169689Skan /* Or the only block of this region has been split. */ 3000169689Skan || RGN_HAS_REAL_EBB (rgn) 3001169689Skan /* New blocks (e.g. recovery blocks) should be processed 3002169689Skan as parts of large regions. */ 3003169689Skan || !glat_start[rgn_bb_table[RGN_BLOCKS (rgn)]]) 300490075Sobrien any_large_regions = 1; 300590075Sobrien else 300690075Sobrien { 300790075Sobrien SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]); 300890075Sobrien RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]); 300990075Sobrien } 301090075Sobrien 301190075Sobrien /* Don't update reg info after reload, since that affects 301290075Sobrien regs_ever_live, which should not change after reload. */ 301390075Sobrien update_life_info (blocks, UPDATE_LIFE_LOCAL, 301490075Sobrien (reload_completed ? PROP_DEATH_NOTES 3015169689Skan : (PROP_DEATH_NOTES | PROP_REG_INFO))); 301690075Sobrien if (any_large_regions) 301790075Sobrien { 301890075Sobrien update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL, 3019169689Skan (reload_completed ? PROP_DEATH_NOTES 3020169689Skan : (PROP_DEATH_NOTES | PROP_REG_INFO))); 3021169689Skan 3022169689Skan#ifdef ENABLE_CHECKING 3023169689Skan check_reg_live (true); 3024169689Skan#endif 302590075Sobrien } 302690075Sobrien 302790075Sobrien if (CHECK_DEAD_NOTES) 302890075Sobrien { 3029169689Skan /* Verify the counts of basic block notes in single basic block 303090075Sobrien regions. */ 303190075Sobrien for (rgn = 0; rgn < nr_regions; rgn++) 303290075Sobrien if (RGN_NR_BLOCKS (rgn) == 1) 303390075Sobrien { 303490075Sobrien sbitmap_zero (blocks); 303590075Sobrien SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]); 303690075Sobrien 3037169689Skan gcc_assert (deaths_in_region[rgn] 3038169689Skan == count_or_remove_death_notes (blocks, 0)); 303990075Sobrien } 304090075Sobrien free (deaths_in_region); 304190075Sobrien } 304290075Sobrien 304390075Sobrien /* Reposition the prologue and epilogue notes in case we moved the 304490075Sobrien prologue/epilogue insns. */ 304590075Sobrien if (reload_completed) 304690075Sobrien reposition_prologue_and_epilogue_notes (get_insns ()); 304790075Sobrien 304890075Sobrien /* Delete redundant line notes. */ 304990075Sobrien if (write_symbols != NO_DEBUG) 305090075Sobrien rm_redundant_line_notes (); 305190075Sobrien 305290075Sobrien if (sched_verbose) 305390075Sobrien { 305490075Sobrien if (reload_completed == 0 && flag_schedule_interblock) 305590075Sobrien { 305690075Sobrien fprintf (sched_dump, 305790075Sobrien "\n;; Procedure interblock/speculative motions == %d/%d \n", 305890075Sobrien nr_inter, nr_spec); 305990075Sobrien } 306090075Sobrien else 3061169689Skan gcc_assert (nr_inter <= 0); 306290075Sobrien fprintf (sched_dump, "\n\n"); 306390075Sobrien } 306490075Sobrien 306590075Sobrien /* Clean up. */ 306690075Sobrien free (rgn_table); 306790075Sobrien free (rgn_bb_table); 306890075Sobrien free (block_to_bb); 306990075Sobrien free (containing_rgn); 307090075Sobrien 307190075Sobrien sched_finish (); 307290075Sobrien 3073169689Skan sbitmap_free (blocks); 3074169689Skan sbitmap_free (large_region_blocks); 3075169689Skan} 3076169689Skan 3077169689Skan/* INSN has been added to/removed from current region. */ 3078169689Skanstatic void 3079169689Skanadd_remove_insn (rtx insn, int remove_p) 3080169689Skan{ 3081169689Skan if (!remove_p) 3082169689Skan rgn_n_insns++; 3083169689Skan else 3084169689Skan rgn_n_insns--; 3085169689Skan 3086169689Skan if (INSN_BB (insn) == target_bb) 308790075Sobrien { 3088169689Skan if (!remove_p) 3089169689Skan target_n_insns++; 3090169689Skan else 3091169689Skan target_n_insns--; 309290075Sobrien } 3093169689Skan} 309490075Sobrien 3095169689Skan/* Extend internal data structures. */ 3096169689Skanstatic void 3097169689Skanextend_regions (void) 3098169689Skan{ 3099169689Skan rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks); 3100169689Skan rgn_bb_table = XRESIZEVEC (int, rgn_bb_table, n_basic_blocks); 3101169689Skan block_to_bb = XRESIZEVEC (int, block_to_bb, last_basic_block); 3102169689Skan containing_rgn = XRESIZEVEC (int, containing_rgn, last_basic_block); 3103169689Skan} 3104169689Skan 3105169689Skan/* BB was added to ebb after AFTER. */ 3106169689Skanstatic void 3107169689Skanadd_block1 (basic_block bb, basic_block after) 3108169689Skan{ 3109169689Skan extend_regions (); 3110169689Skan 3111169689Skan if (after == 0 || after == EXIT_BLOCK_PTR) 311290075Sobrien { 3113169689Skan int i; 3114169689Skan 3115169689Skan i = RGN_BLOCKS (nr_regions); 3116169689Skan /* I - first free position in rgn_bb_table. */ 3117169689Skan 3118169689Skan rgn_bb_table[i] = bb->index; 3119169689Skan RGN_NR_BLOCKS (nr_regions) = 1; 3120169689Skan RGN_DONT_CALC_DEPS (nr_regions) = after == EXIT_BLOCK_PTR; 3121169689Skan RGN_HAS_REAL_EBB (nr_regions) = 0; 3122169689Skan CONTAINING_RGN (bb->index) = nr_regions; 3123169689Skan BLOCK_TO_BB (bb->index) = 0; 3124169689Skan 3125169689Skan nr_regions++; 3126169689Skan 3127169689Skan RGN_BLOCKS (nr_regions) = i + 1; 3128169689Skan 3129169689Skan if (CHECK_DEAD_NOTES) 3130169689Skan { 3131169689Skan sbitmap blocks = sbitmap_alloc (last_basic_block); 3132169689Skan deaths_in_region = xrealloc (deaths_in_region, nr_regions * 3133169689Skan sizeof (*deaths_in_region)); 3134169689Skan 3135169689Skan check_dead_notes1 (nr_regions - 1, blocks); 3136169689Skan 3137169689Skan sbitmap_free (blocks); 3138169689Skan } 313990075Sobrien } 3140169689Skan else 3141169689Skan { 3142169689Skan int i, pos; 3143169689Skan 3144169689Skan /* We need to fix rgn_table, block_to_bb, containing_rgn 3145169689Skan and ebb_head. */ 3146169689Skan 3147169689Skan BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index); 3148169689Skan 3149169689Skan /* We extend ebb_head to one more position to 3150169689Skan easily find the last position of the last ebb in 3151169689Skan the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1] 3152169689Skan is _always_ valid for access. */ 3153169689Skan 3154169689Skan i = BLOCK_TO_BB (after->index) + 1; 3155169689Skan pos = ebb_head[i] - 1; 3156169689Skan /* Now POS is the index of the last block in the region. */ 3157169689Skan 3158169689Skan /* Find index of basic block AFTER. */ 3159169689Skan for (; rgn_bb_table[pos] != after->index; pos--); 3160169689Skan 3161169689Skan pos++; 3162169689Skan gcc_assert (pos > ebb_head[i - 1]); 3163169689Skan 3164169689Skan /* i - ebb right after "AFTER". */ 3165169689Skan /* ebb_head[i] - VALID. */ 3166169689Skan 3167169689Skan /* Source position: ebb_head[i] 3168169689Skan Destination position: ebb_head[i] + 1 3169169689Skan Last position: 3170169689Skan RGN_BLOCKS (nr_regions) - 1 3171169689Skan Number of elements to copy: (last_position) - (source_position) + 1 3172169689Skan */ 3173169689Skan 3174169689Skan memmove (rgn_bb_table + pos + 1, 3175169689Skan rgn_bb_table + pos, 3176169689Skan ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1) 3177169689Skan * sizeof (*rgn_bb_table)); 3178169689Skan 3179169689Skan rgn_bb_table[pos] = bb->index; 3180169689Skan 3181169689Skan for (; i <= current_nr_blocks; i++) 3182169689Skan ebb_head [i]++; 3183169689Skan 3184169689Skan i = CONTAINING_RGN (after->index); 3185169689Skan CONTAINING_RGN (bb->index) = i; 3186169689Skan 3187169689Skan RGN_HAS_REAL_EBB (i) = 1; 3188169689Skan 3189169689Skan for (++i; i <= nr_regions; i++) 3190169689Skan RGN_BLOCKS (i)++; 3191169689Skan 3192169689Skan /* We don't need to call check_dead_notes1 () because this new block 3193169689Skan is just a split of the old. We don't want to count anything twice. */ 3194169689Skan } 3195169689Skan} 3196169689Skan 3197169689Skan/* Fix internal data after interblock movement of jump instruction. 3198169689Skan For parameter meaning please refer to 3199169689Skan sched-int.h: struct sched_info: fix_recovery_cfg. */ 3200169689Skanstatic void 3201169689Skanfix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti) 3202169689Skan{ 3203169689Skan int old_pos, new_pos, i; 3204169689Skan 3205169689Skan BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi); 3206169689Skan 3207169689Skan for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1; 3208169689Skan rgn_bb_table[old_pos] != check_bb_nexti; 3209169689Skan old_pos--); 3210169689Skan gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]); 3211169689Skan 3212169689Skan for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1; 3213169689Skan rgn_bb_table[new_pos] != bbi; 3214169689Skan new_pos--); 3215169689Skan new_pos++; 3216169689Skan gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]); 3217169689Skan 3218169689Skan gcc_assert (new_pos < old_pos); 3219169689Skan 3220169689Skan memmove (rgn_bb_table + new_pos + 1, 3221169689Skan rgn_bb_table + new_pos, 3222169689Skan (old_pos - new_pos) * sizeof (*rgn_bb_table)); 3223169689Skan 3224169689Skan rgn_bb_table[new_pos] = check_bb_nexti; 3225169689Skan 3226169689Skan for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++) 3227169689Skan ebb_head[i]++; 3228169689Skan} 3229169689Skan 3230169689Skan/* Return next block in ebb chain. For parameter meaning please refer to 3231169689Skan sched-int.h: struct sched_info: advance_target_bb. */ 3232169689Skanstatic basic_block 3233169689Skanadvance_target_bb (basic_block bb, rtx insn) 3234169689Skan{ 3235169689Skan if (insn) 3236169689Skan return 0; 3237169689Skan 3238169689Skan gcc_assert (BLOCK_TO_BB (bb->index) == target_bb 3239169689Skan && BLOCK_TO_BB (bb->next_bb->index) == target_bb); 3240169689Skan return bb->next_bb; 3241169689Skan} 3242169689Skan 3243169689Skan/* Count and remove death notes in region RGN, which consists of blocks 3244169689Skan with indecies in BLOCKS. */ 3245169689Skanstatic void 3246169689Skancheck_dead_notes1 (int rgn, sbitmap blocks) 3247169689Skan{ 3248169689Skan int b; 3249169689Skan 3250169689Skan sbitmap_zero (blocks); 3251169689Skan for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b) 3252169689Skan SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]); 3253169689Skan 3254169689Skan deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1); 3255169689Skan} 3256169689Skan 3257169689Skan#ifdef ENABLE_CHECKING 3258169689Skan/* Return non zero, if BB is head or leaf (depending of LEAF_P) block in 3259169689Skan current region. For more information please refer to 3260169689Skan sched-int.h: struct sched_info: region_head_or_leaf_p. */ 3261169689Skanstatic int 3262169689Skanregion_head_or_leaf_p (basic_block bb, int leaf_p) 3263169689Skan{ 3264169689Skan if (!leaf_p) 3265169689Skan return bb->index == rgn_bb_table[RGN_BLOCKS (CONTAINING_RGN (bb->index))]; 3266169689Skan else 326790075Sobrien { 3268169689Skan int i; 3269169689Skan edge e; 3270169689Skan edge_iterator ei; 3271169689Skan 3272169689Skan i = CONTAINING_RGN (bb->index); 3273169689Skan 3274169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 3275169689Skan if (e->dest != EXIT_BLOCK_PTR 3276169689Skan && CONTAINING_RGN (e->dest->index) == i 3277169689Skan /* except self-loop. */ 3278169689Skan && e->dest != bb) 3279169689Skan return 0; 3280169689Skan 3281169689Skan return 1; 328290075Sobrien } 3283169689Skan} 3284169689Skan#endif /* ENABLE_CHECKING */ 328590075Sobrien 3286169689Skan#endif 3287169689Skan 3288169689Skanstatic bool 3289169689Skangate_handle_sched (void) 3290169689Skan{ 3291169689Skan#ifdef INSN_SCHEDULING 3292169689Skan return flag_schedule_insns; 3293169689Skan#else 3294169689Skan return 0; 3295169689Skan#endif 329690075Sobrien} 3297169689Skan 3298169689Skan/* Run instruction scheduler. */ 3299169689Skanstatic unsigned int 3300169689Skanrest_of_handle_sched (void) 3301169689Skan{ 3302169689Skan#ifdef INSN_SCHEDULING 3303169689Skan /* Do control and data sched analysis, 3304169689Skan and write some of the results to dump file. */ 3305169689Skan 3306169689Skan schedule_insns (); 330790075Sobrien#endif 3308169689Skan return 0; 3309169689Skan} 3310169689Skan 3311169689Skanstatic bool 3312169689Skangate_handle_sched2 (void) 3313169689Skan{ 3314169689Skan#ifdef INSN_SCHEDULING 3315169689Skan return optimize > 0 && flag_schedule_insns_after_reload; 3316169689Skan#else 3317169689Skan return 0; 3318169689Skan#endif 3319169689Skan} 3320169689Skan 3321169689Skan/* Run second scheduling pass after reload. */ 3322169689Skanstatic unsigned int 3323169689Skanrest_of_handle_sched2 (void) 3324169689Skan{ 3325169689Skan#ifdef INSN_SCHEDULING 3326169689Skan /* Do control and data sched analysis again, 3327169689Skan and write some more of the results to dump file. */ 3328169689Skan 3329169689Skan split_all_insns (1); 3330169689Skan 3331169689Skan if (flag_sched2_use_superblocks || flag_sched2_use_traces) 3332169689Skan { 3333169689Skan schedule_ebbs (); 3334169689Skan /* No liveness updating code yet, but it should be easy to do. 3335169689Skan reg-stack recomputes the liveness when needed for now. */ 3336169689Skan count_or_remove_death_notes (NULL, 1); 3337169689Skan cleanup_cfg (CLEANUP_EXPENSIVE); 3338169689Skan } 3339169689Skan else 3340169689Skan schedule_insns (); 3341169689Skan#endif 3342169689Skan return 0; 3343169689Skan} 3344169689Skan 3345169689Skanstruct tree_opt_pass pass_sched = 3346169689Skan{ 3347169689Skan "sched1", /* name */ 3348169689Skan gate_handle_sched, /* gate */ 3349169689Skan rest_of_handle_sched, /* execute */ 3350169689Skan NULL, /* sub */ 3351169689Skan NULL, /* next */ 3352169689Skan 0, /* static_pass_number */ 3353169689Skan TV_SCHED, /* tv_id */ 3354169689Skan 0, /* properties_required */ 3355169689Skan 0, /* properties_provided */ 3356169689Skan 0, /* properties_destroyed */ 3357169689Skan 0, /* todo_flags_start */ 3358169689Skan TODO_dump_func | 3359169689Skan TODO_ggc_collect, /* todo_flags_finish */ 3360169689Skan 'S' /* letter */ 3361169689Skan}; 3362169689Skan 3363169689Skanstruct tree_opt_pass pass_sched2 = 3364169689Skan{ 3365169689Skan "sched2", /* name */ 3366169689Skan gate_handle_sched2, /* gate */ 3367169689Skan rest_of_handle_sched2, /* execute */ 3368169689Skan NULL, /* sub */ 3369169689Skan NULL, /* next */ 3370169689Skan 0, /* static_pass_number */ 3371169689Skan TV_SCHED2, /* tv_id */ 3372169689Skan 0, /* properties_required */ 3373169689Skan 0, /* properties_provided */ 3374169689Skan 0, /* properties_destroyed */ 3375169689Skan 0, /* todo_flags_start */ 3376169689Skan TODO_dump_func | 3377169689Skan TODO_ggc_collect, /* todo_flags_finish */ 3378169689Skan 'R' /* letter */ 3379169689Skan}; 3380169689Skan 3381