LCOV - code coverage report
Current view: top level - gcc - sched-rgn.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 69.7 % 1500 1045
Test Date: 2026-11-14 16:39:50 Functions: 73.4 % 94 69
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Instruction scheduling pass.
       2              :    Copyright (C) 1992-2026 Free Software Foundation, Inc.
       3              :    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
       4              :    and currently maintained by, Jim Wilson (wilson@cygnus.com)
       5              : 
       6              : This file is part of GCC.
       7              : 
       8              : GCC is free software; you can redistribute it and/or modify it under
       9              : the terms of the GNU General Public License as published by the Free
      10              : Software Foundation; either version 3, or (at your option) any later
      11              : version.
      12              : 
      13              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      14              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      15              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      16              : for more details.
      17              : 
      18              : You should have received a copy of the GNU General Public License
      19              : along with GCC; see the file COPYING3.  If not see
      20              : <http://www.gnu.org/licenses/>.  */
      21              : 
      22              : /* This pass implements list scheduling within basic blocks.  It is
      23              :    run twice: (1) after flow analysis, but before register allocation,
      24              :    and (2) after register allocation.
      25              : 
      26              :    The first run performs interblock scheduling, moving insns between
      27              :    different blocks in the same "region", and the second runs only
      28              :    basic block scheduling.
      29              : 
      30              :    Interblock motions performed are useful motions and speculative
      31              :    motions, including speculative loads.  Motions requiring code
      32              :    duplication are not supported.  The identification of motion type
      33              :    and the check for validity of speculative motions requires
      34              :    construction and analysis of the function's control flow graph.
      35              : 
      36              :    The main entry point for this pass is schedule_insns(), called for
      37              :    each function.  The work of the scheduler is organized in three
      38              :    levels: (1) function level: insns are subject to splitting,
      39              :    control-flow-graph is constructed, regions are computed (after
      40              :    reload, each region is of one block), (2) region level: control
      41              :    flow graph attributes required for interblock scheduling are
      42              :    computed (dominators, reachability, etc.), data dependences and
      43              :    priorities are computed, and (3) block level: insns in the block
      44              :    are actually scheduled.  */
      45              : 
      46              : #include "config.h"
      47              : #include "system.h"
      48              : #include "coretypes.h"
      49              : #include "backend.h"
      50              : #include "target.h"
      51              : #include "rtl.h"
      52              : #include "df.h"
      53              : #include "memmodel.h"
      54              : #include "tm_p.h"
      55              : #include "insn-config.h"
      56              : #include "emit-rtl.h"
      57              : #include "recog.h"
      58              : #include "profile.h"
      59              : #include "insn-attr.h"
      60              : #include "except.h"
      61              : #include "cfganal.h"
      62              : #include "sched-int.h"
      63              : #include "sel-sched.h"
      64              : #include "tree-pass.h"
      65              : #include "dbgcnt.h"
      66              : #include "pretty-print.h"
      67              : #include "print-rtl.h"
      68              : 
      69              : /* Disable warnings about quoting issues in the pp_xxx calls below
      70              :    that (intentionally) don't follow GCC diagnostic conventions.  */
      71              : #if __GNUC__ >= 10
      72              : #  pragma GCC diagnostic push
      73              : #  pragma GCC diagnostic ignored "-Wformat-diag"
      74              : #endif
      75              : 
      76              : #ifdef INSN_SCHEDULING
      77              : 
      78              : /* Some accessor macros for h_i_d members only used within this file.  */
      79              : #define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)
      80              : #define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)
      81              : 
      82              : /* nr_inter/spec counts interblock/speculative motion for the function.  */
      83              : static int nr_inter, nr_spec;
      84              : 
      85              : static bool is_cfg_nonregular (void);
      86              : 
      87              : /* Number of regions in the procedure.  */
      88              : int nr_regions = 0;
      89              : 
      90              : /* Same as above before adding any new regions.  */
      91              : static int nr_regions_initial = 0;
      92              : 
      93              : /* Table of region descriptions.  */
      94              : region *rgn_table = NULL;
      95              : 
      96              : /* Array of lists of regions' blocks.  */
      97              : int *rgn_bb_table = NULL;
      98              : 
      99              : /* Topological order of blocks in the region (if b2 is reachable from
     100              :    b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is
     101              :    always referred to by either block or b, while its topological
     102              :    order name (in the region) is referred to by bb.  */
     103              : int *block_to_bb = NULL;
     104              : 
     105              : /* The number of the region containing a block.  */
     106              : int *containing_rgn = NULL;
     107              : 
     108              : /* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
     109              :    Currently we can get a ebb only through splitting of currently
     110              :    scheduling block, therefore, we don't need ebb_head array for every region,
     111              :    hence, its sufficient to hold it for current one only.  */
     112              : int *ebb_head = NULL;
     113              : 
     114              : /* The minimum probability of reaching a source block so that it will be
     115              :    considered for speculative scheduling.  */
     116              : static int min_spec_prob;
     117              : 
     118              : static void find_single_block_region (bool);
     119              : static void find_rgns (void);
     120              : static bool too_large (int, int *, int *);
     121              : 
     122              : /* Blocks of the current region being scheduled.  */
     123              : int current_nr_blocks;
     124              : int current_blocks;
     125              : 
     126              : /* A speculative motion requires checking live information on the path
     127              :    from 'source' to 'target'.  The split blocks are those to be checked.
     128              :    After a speculative motion, live information should be modified in
     129              :    the 'update' blocks.
     130              : 
     131              :    Lists of split and update blocks for each candidate of the current
     132              :    target are in array bblst_table.  */
     133              : static basic_block *bblst_table;
     134              : static int bblst_size, bblst_last;
     135              : 
     136              : /* Arrays that hold the DFA state at the end of a basic block, to re-use
     137              :    as the initial state at the start of successor blocks.  The BB_STATE
     138              :    array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
     139              :    into BB_STATE for basic block I.  FIXME: This should be a vec.  */
     140              : static char *bb_state_array = NULL;
     141              : static state_t *bb_state = NULL;
     142              : 
     143              : /* Target info declarations.
     144              : 
     145              :    The block currently being scheduled is referred to as the "target" block,
     146              :    while other blocks in the region from which insns can be moved to the
     147              :    target are called "source" blocks.  The candidate structure holds info
     148              :    about such sources: are they valid?  Speculative?  Etc.  */
     149              : struct bblst
     150              : {
     151              :   basic_block *first_member;
     152              :   int nr_members;
     153              : };
     154              : 
     155              : struct candidate
     156              : {
     157              :   char is_valid;
     158              :   char is_speculative;
     159              :   int src_prob;
     160              :   bblst split_bbs;
     161              :   bblst update_bbs;
     162              : };
     163              : 
     164              : static candidate *candidate_table;
     165              : #define IS_VALID(src) (candidate_table[src].is_valid)
     166              : #define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)
     167              : #define IS_SPECULATIVE_INSN(INSN)                       \
     168              :   (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
     169              : #define SRC_PROB(src) ( candidate_table[src].src_prob )
     170              : 
     171              : /* The bb being currently scheduled.  */
     172              : int target_bb;
     173              : 
     174              : /* List of edges.  */
     175              : struct edgelst
     176              : {
     177              :   edge *first_member;
     178              :   int nr_members;
     179              : };
     180              : 
     181              : static edge *edgelst_table;
     182              : static int edgelst_last;
     183              : 
     184              : static void extract_edgelst (sbitmap, edgelst *);
     185              : 
     186              : /* Target info functions.  */
     187              : static void split_edges (int, int, edgelst *);
     188              : static void compute_trg_info (int);
     189              : void debug_candidate (int);
     190              : void debug_candidates (int);
     191              : 
     192              : /* Dominators array: dom[i] contains the sbitmap of dominators of
     193              :    bb i in the region.  */
     194              : static sbitmap *dom;
     195              : 
     196              : /* bb 0 is the only region entry.  */
     197              : #define IS_RGN_ENTRY(bb) (!bb)
     198              : 
     199              : /* Is bb_src dominated by bb_trg.  */
     200              : #define IS_DOMINATED(bb_src, bb_trg)                                 \
     201              : ( bitmap_bit_p (dom[bb_src], bb_trg) )
     202              : 
     203              : /* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
     204              :    the probability of bb i relative to the region entry.  */
     205              : static int *prob;
     206              : 
     207              : /* Bit-set of edges, where bit i stands for edge i.  */
     208              : typedef sbitmap edgeset;
     209              : 
     210              : /* Number of edges in the region.  */
     211              : static int rgn_nr_edges;
     212              : 
     213              : /* Array of size rgn_nr_edges.  */
     214              : static edge *rgn_edges;
     215              : 
     216              : /* Mapping from each edge in the graph to its number in the rgn.  */
     217              : #define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)
     218              : #define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))
     219              : 
     220              : /* The split edges of a source bb is different for each target
     221              :    bb.  In order to compute this efficiently, the 'potential-split edges'
     222              :    are computed for each bb prior to scheduling a region.  This is actually
     223              :    the split edges of each bb relative to the region entry.
     224              : 
     225              :    pot_split[bb] is the set of potential split edges of bb.  */
     226              : static edgeset *pot_split;
     227              : 
     228              : /* For every bb, a set of its ancestor edges.  */
     229              : static edgeset *ancestor_edges;
     230              : 
     231              : #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
     232              : 
     233              : /* Speculative scheduling functions.  */
     234              : static bool check_live_1 (int, rtx);
     235              : static void update_live_1 (int, rtx);
     236              : static bool is_pfree (rtx_insn *, int, int);
     237              : static bool find_conditional_protection (rtx_insn *, int);
     238              : static bool is_conditionally_protected (rtx_insn *, int, int);
     239              : static bool is_prisky (rtx_insn *, int, int);
     240              : static bool is_exception_free (rtx_insn *, int, int);
     241              : 
     242              : static bool sets_likely_spilled (rtx);
     243              : static void sets_likely_spilled_1 (rtx, const_rtx, void *);
     244              : static void add_branch_dependences (rtx_insn *, rtx_insn *);
     245              : static void compute_block_dependences (int);
     246              : 
     247              : static void schedule_region (int);
     248              : static void concat_insn_mem_list (rtx_insn_list *, rtx_expr_list *,
     249              :                                   rtx_insn_list **, rtx_expr_list **);
     250              : static void propagate_deps (int, class deps_desc *);
     251              : static void free_pending_lists (void);
     252              : 
     253              : /* Functions for construction of the control flow graph.  */
     254              : 
     255              : /* Return true if control flow graph should not be constructed,
     256              :    false otherwise.
     257              : 
     258              :    We decide not to build the control flow graph if there is possibly more
     259              :    than one entry to the function, if computed branches exist, if we
     260              :    have nonlocal gotos, or if we have an unreachable loop.  */
     261              : 
     262              : static bool
     263          186 : is_cfg_nonregular (void)
     264              : {
     265          186 :   basic_block b;
     266          186 :   rtx_insn *insn;
     267              : 
     268              :   /* If we have a label that could be the target of a nonlocal goto, then
     269              :      the cfg is not well structured.  */
     270          186 :   if (nonlocal_goto_handler_labels)
     271              :     return true;
     272              : 
     273              :   /* If we have any forced labels, then the cfg is not well structured.  */
     274          186 :   if (forced_labels)
     275              :     return true;
     276              : 
     277              :   /* If we have exception handlers, then we consider the cfg not well
     278              :      structured.  ?!?  We should be able to handle this now that we
     279              :      compute an accurate cfg for EH.  */
     280          186 :   if (current_function_has_exception_handlers ())
     281              :     return true;
     282              : 
     283              :   /* If we have insns which refer to labels as non-jumped-to operands,
     284              :      then we consider the cfg not well structured.  */
     285         1927 :   FOR_EACH_BB_FN (b, cfun)
     286        14995 :     FOR_BB_INSNS (b, insn)
     287              :       {
     288        13248 :         rtx note, set, dest;
     289        13248 :         rtx_insn *next;
     290              : 
     291              :         /* If this function has a computed jump, then we consider the cfg
     292              :            not well structured.  */
     293        13248 :         if (JUMP_P (insn) && computed_jump_p (insn))
     294              :           return true;
     295              : 
     296              :         /* A shared table's successors cannot be redirected independently
     297              :            to create loop preheaders or scheduling bookkeeping blocks.  */
     298        13248 :         if (shared_tablejump_p (insn, NULL, NULL))
     299              :           return true;
     300              : 
     301        13248 :         if (!INSN_P (insn))
     302         3780 :           continue;
     303              : 
     304         9468 :         note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);
     305         9468 :         if (note == NULL_RTX)
     306         9458 :           continue;
     307              : 
     308              :         /* For that label not to be seen as a referred-to label, this
     309              :            must be a single-set which is feeding a jump *only*.  This
     310              :            could be a conditional jump with the label split off for
     311              :            machine-specific reasons or a casesi/tablejump.  */
     312           10 :         next = next_nonnote_insn (insn);
     313           10 :         if (next == NULL_RTX
     314           10 :             || !JUMP_P (next)
     315            0 :             || (JUMP_LABEL (next) != XEXP (note, 0)
     316            0 :                 && find_reg_note (next, REG_LABEL_TARGET,
     317              :                                   XEXP (note, 0)) == NULL_RTX)
     318           10 :             || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))
     319              :           return true;
     320              : 
     321            0 :         set = single_set (insn);
     322            0 :         if (set == NULL_RTX)
     323              :           return true;
     324              : 
     325            0 :         dest = SET_DEST (set);
     326            0 :         if (!REG_P (dest) || !dead_or_set_p (next, dest))
     327              :           return true;
     328              :       }
     329              : 
     330              :   /* Unreachable loops with more than one basic block are detected
     331              :      during the DFS traversal in find_rgns.
     332              : 
     333              :      Unreachable loops with a single block are detected here.  This
     334              :      test is redundant with the one in find_rgns, but it's much
     335              :      cheaper to go ahead and catch the trivial case here.  */
     336         1894 :   FOR_EACH_BB_FN (b, cfun)
     337              :     {
     338         1724 :       if (EDGE_COUNT (b->preds) == 0
     339         2886 :           || (single_pred_p (b)
     340         1162 :               && single_pred (b) == b))
     341              :         return true;
     342              :     }
     343              : 
     344              :   /* All the tests passed.  Consider the cfg well structured.  */
     345              :   return false;
     346              : }
     347              : 
     348              : /* Extract list of edges from a bitmap containing EDGE_TO_BIT bits.  */
     349              : 
     350              : static void
     351           51 : extract_edgelst (sbitmap set, edgelst *el)
     352              : {
     353           51 :   unsigned int i = 0;
     354           51 :   sbitmap_iterator sbi;
     355              : 
     356              :   /* edgelst table space is reused in each call to extract_edgelst.  */
     357           51 :   edgelst_last = 0;
     358              : 
     359           51 :   el->first_member = &edgelst_table[edgelst_last];
     360           51 :   el->nr_members = 0;
     361              : 
     362              :   /* Iterate over each word in the bitset.  */
     363          174 :   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, sbi)
     364              :     {
     365           72 :       edgelst_table[edgelst_last++] = rgn_edges[i];
     366           72 :       el->nr_members++;
     367              :     }
     368           51 : }
     369              : 
     370              : /* Functions for the construction of regions.  */
     371              : 
     372              : /* Print the regions, for debugging purposes.  Callable from debugger.  */
     373              : 
     374              : DEBUG_FUNCTION void
     375            0 : debug_regions (void)
     376              : {
     377            0 :   int rgn, bb;
     378              : 
     379            0 :   fprintf (sched_dump, "\n;;   ------------ REGIONS ----------\n\n");
     380            0 :   for (rgn = 0; rgn < nr_regions; rgn++)
     381              :     {
     382            0 :       fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
     383            0 :                rgn_table[rgn].rgn_nr_blocks);
     384            0 :       fprintf (sched_dump, ";;\tbb/block: ");
     385              : 
     386              :       /* We don't have ebb_head initialized yet, so we can't use
     387              :          BB_TO_BLOCK ().  */
     388            0 :       current_blocks = RGN_BLOCKS (rgn);
     389              : 
     390            0 :       for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
     391            0 :         fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
     392              : 
     393            0 :       fprintf (sched_dump, "\n\n");
     394              :     }
     395            0 : }
     396              : 
     397              : /* Print the region's basic blocks.  */
     398              : 
     399              : DEBUG_FUNCTION void
     400            0 : debug_region (int rgn)
     401              : {
     402            0 :   int bb;
     403              : 
     404            0 :   fprintf (stderr, "\n;;   ------------ REGION %d ----------\n\n", rgn);
     405            0 :   fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,
     406            0 :            rgn_table[rgn].rgn_nr_blocks);
     407            0 :   fprintf (stderr, ";;\tbb/block: ");
     408              : 
     409              :   /* We don't have ebb_head initialized yet, so we can't use
     410              :      BB_TO_BLOCK ().  */
     411            0 :   current_blocks = RGN_BLOCKS (rgn);
     412              : 
     413            0 :   for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
     414            0 :     fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
     415              : 
     416            0 :   fprintf (stderr, "\n\n");
     417              : 
     418            0 :   for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
     419              :     {
     420            0 :       dump_bb (stderr,
     421            0 :                BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[current_blocks + bb]),
     422              :                0, TDF_SLIM | TDF_BLOCKS);
     423            0 :       fprintf (stderr, "\n");
     424              :     }
     425              : 
     426            0 :   fprintf (stderr, "\n");
     427              : 
     428            0 : }
     429              : 
     430              : /* True when a bb with index BB_INDEX contained in region RGN.  */
     431              : static bool
     432            0 : bb_in_region_p (int bb_index, int rgn)
     433              : {
     434            0 :   int i;
     435              : 
     436            0 :   for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
     437            0 :     if (rgn_bb_table[current_blocks + i] == bb_index)
     438              :       return true;
     439              : 
     440              :   return false;
     441              : }
     442              : 
     443              : /* Dump region RGN to file F using dot syntax.  */
     444              : void
     445            0 : dump_region_dot (FILE *f, int rgn)
     446              : {
     447            0 :   int i;
     448              : 
     449            0 :   fprintf (f, "digraph Region_%d {\n", rgn);
     450              : 
     451              :   /* We don't have ebb_head initialized yet, so we can't use
     452              :      BB_TO_BLOCK ().  */
     453            0 :   current_blocks = RGN_BLOCKS (rgn);
     454              : 
     455            0 :   for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)
     456              :     {
     457            0 :       edge e;
     458            0 :       edge_iterator ei;
     459            0 :       int src_bb_num = rgn_bb_table[current_blocks + i];
     460            0 :       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, src_bb_num);
     461              : 
     462            0 :       FOR_EACH_EDGE (e, ei, bb->succs)
     463            0 :         if (bb_in_region_p (e->dest->index, rgn))
     464            0 :           fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);
     465              :     }
     466            0 :   fprintf (f, "}\n");
     467            0 : }
     468              : 
     469              : /* The same, but first open a file specified by FNAME.  */
     470              : void
     471            0 : dump_region_dot_file (const char *fname, int rgn)
     472              : {
     473            0 :   FILE *f = fopen (fname, "wt");
     474            0 :   dump_region_dot (f, rgn);
     475            0 :   fclose (f);
     476            0 : }
     477              : 
     478              : /* Build a single block region for each basic block in the function.
     479              :    This allows for using the same code for interblock and basic block
     480              :    scheduling.  */
     481              : 
     482              : static void
     483       982738 : find_single_block_region (bool ebbs_p)
     484              : {
     485       982738 :   basic_block bb, ebb_start;
     486       982738 :   int i = 0;
     487              : 
     488       982738 :   nr_regions = 0;
     489              : 
     490       982738 :   if (ebbs_p) {
     491           52 :     int probability_cutoff;
     492           52 :     if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
     493            5 :       probability_cutoff = param_tracer_min_branch_probability_feedback;
     494              :     else
     495           47 :       probability_cutoff = param_tracer_min_branch_probability;
     496           52 :     probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
     497              : 
     498          177 :     FOR_EACH_BB_FN (ebb_start, cfun)
     499              :       {
     500          125 :         RGN_NR_BLOCKS (nr_regions) = 0;
     501          125 :         RGN_BLOCKS (nr_regions) = i;
     502          125 :         RGN_DONT_CALC_DEPS (nr_regions) = 0;
     503          125 :         RGN_HAS_REAL_EBB (nr_regions) = 0;
     504              : 
     505          125 :         for (bb = ebb_start; ; bb = bb->next_bb)
     506              :           {
     507          135 :             edge e;
     508              : 
     509          135 :             rgn_bb_table[i] = bb->index;
     510          135 :             RGN_NR_BLOCKS (nr_regions)++;
     511          135 :             CONTAINING_RGN (bb->index) = nr_regions;
     512          135 :             BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);
     513          135 :             i++;
     514              : 
     515          135 :             if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
     516           83 :                 || LABEL_P (BB_HEAD (bb->next_bb)))
     517              :               break;
     518              : 
     519           15 :             e = find_fallthru_edge (bb->succs);
     520           15 :             if (! e)
     521              :               break;
     522           15 :             if (e->probability.initialized_p ()
     523           15 :                 && e->probability.to_reg_br_prob_base () <= probability_cutoff)
     524              :               break;
     525           10 :           }
     526              : 
     527          125 :         ebb_start = bb;
     528          125 :         nr_regions++;
     529              :       }
     530              :   }
     531              :   else
     532     11498607 :     FOR_EACH_BB_FN (bb, cfun)
     533              :       {
     534     10515921 :         rgn_bb_table[nr_regions] = bb->index;
     535     10515921 :         RGN_NR_BLOCKS (nr_regions) = 1;
     536     10515921 :         RGN_BLOCKS (nr_regions) = nr_regions;
     537     10515921 :         RGN_DONT_CALC_DEPS (nr_regions) = 0;
     538     10515921 :         RGN_HAS_REAL_EBB (nr_regions) = 0;
     539              : 
     540     10515921 :         CONTAINING_RGN (bb->index) = nr_regions;
     541     10515921 :         BLOCK_TO_BB (bb->index) = 0;
     542     10515921 :         nr_regions++;
     543              :       }
     544       982738 : }
     545              : 
     546              : /* Estimate number of the insns in the BB.  */
     547              : static int
     548          108 : rgn_estimate_number_of_insns (basic_block bb)
     549              : {
     550          108 :   int count;
     551              : 
     552          108 :   count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
     553              : 
     554          108 :   if (MAY_HAVE_DEBUG_INSNS)
     555              :     {
     556              :       rtx_insn *insn;
     557              : 
     558          955 :       FOR_BB_INSNS (bb, insn)
     559          931 :         if (DEBUG_INSN_P (insn))
     560          539 :           count--;
     561              :     }
     562              : 
     563          108 :   return count;
     564              : }
     565              : 
     566              : /* Update number of blocks and the estimate for number of insns
     567              :    in the region.  Return true if the region is "too large" for interblock
     568              :    scheduling (compile time considerations).  */
     569              : 
     570              : static bool
     571          117 : too_large (int block, int *num_bbs, int *num_insns)
     572              : {
     573          117 :   (*num_bbs)++;
     574          234 :   (*num_insns) += (common_sched_info->estimate_number_of_insns
     575          117 :                    (BASIC_BLOCK_FOR_FN (cfun, block)));
     576              : 
     577          117 :   return ((*num_bbs > param_max_sched_region_blocks)
     578          117 :           || (*num_insns > param_max_sched_region_insns));
     579              : }
     580              : 
     581              : /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
     582              :    is still an inner loop.  Put in max_hdr[blk] the header of the most inner
     583              :    loop containing blk.  */
     584              : #define UPDATE_LOOP_RELATIONS(blk, hdr)         \
     585              : {                                               \
     586              :   if (max_hdr[blk] == -1)                       \
     587              :     max_hdr[blk] = hdr;                         \
     588              :   else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])       \
     589              :     bitmap_clear_bit (inner, hdr);                      \
     590              :   else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])       \
     591              :     {                                           \
     592              :       bitmap_clear_bit (inner,max_hdr[blk]);            \
     593              :       max_hdr[blk] = hdr;                       \
     594              :     }                                           \
     595              : }
     596              : 
     597              : /* Find regions for interblock scheduling.
     598              : 
     599              :    A region for scheduling can be:
     600              : 
     601              :      * A loop-free procedure, or
     602              : 
     603              :      * A reducible inner loop, or
     604              : 
     605              :      * A basic block not contained in any other region.
     606              : 
     607              :    ?!? In theory we could build other regions based on extended basic
     608              :    blocks or reverse extended basic blocks.  Is it worth the trouble?
     609              : 
     610              :    Loop blocks that form a region are put into the region's block list
     611              :    in topological order.
     612              : 
     613              :    This procedure stores its results into the following global (ick) variables
     614              : 
     615              :      * rgn_nr
     616              :      * rgn_table
     617              :      * rgn_bb_table
     618              :      * block_to_bb
     619              :      * containing region
     620              : 
     621              :    We use dominator relationships to avoid making regions out of non-reducible
     622              :    loops.
     623              : 
     624              :    This procedure needs to be converted to work on pred/succ lists instead
     625              :    of edge tables.  That would simplify it somewhat.  */
     626              : 
     627              : static void
     628          127 : haifa_find_rgns (void)
     629              : {
     630          127 :   int *max_hdr, *dfs_nr, *degree;
     631          127 :   char no_loops = 1;
     632          127 :   int node, child, loop_head, i, head, tail;
     633          127 :   int count = 0, sp, idx = 0;
     634          127 :   edge_iterator current_edge;
     635          127 :   edge_iterator *stack;
     636          127 :   int num_bbs, num_insns;
     637          127 :   bool unreachable;
     638          127 :   bool too_large_failure;
     639          127 :   basic_block bb;
     640              : 
     641              :   /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops
     642              :      and a mapping from block to its loop header (if the block is contained
     643              :      in a loop, else -1).
     644              : 
     645              :      Store results in HEADER, INNER, and MAX_HDR respectively, these will
     646              :      be used as inputs to the second traversal.
     647              : 
     648              :      STACK, SP and DFS_NR are only used during the first traversal.  */
     649              : 
     650              :   /* Allocate and initialize variables for the first traversal.  */
     651          127 :   max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
     652          127 :   dfs_nr = XCNEWVEC (int, last_basic_block_for_fn (cfun));
     653          127 :   stack = XNEWVEC (edge_iterator, n_edges_for_fn (cfun));
     654              : 
     655              :   /* Note if a block is a natural inner loop header.  */
     656          127 :   auto_sbitmap inner (last_basic_block_for_fn (cfun));
     657          127 :   bitmap_ones (inner);
     658              : 
     659              :   /* Note if a block is a natural loop header.  */
     660          127 :   auto_sbitmap header (last_basic_block_for_fn (cfun));
     661          127 :   bitmap_clear (header);
     662              : 
     663              :   /* Note if a block is in the block queue.  */
     664          127 :   auto_sbitmap in_queue (last_basic_block_for_fn (cfun));
     665          127 :   bitmap_clear (in_queue);
     666              : 
     667              :   /* Note if a block is in the block queue.  */
     668          127 :   auto_sbitmap in_stack (last_basic_block_for_fn (cfun));
     669          127 :   bitmap_clear (in_stack);
     670              : 
     671         1764 :   for (i = 0; i < last_basic_block_for_fn (cfun); i++)
     672         1510 :     max_hdr[i] = -1;
     673              : 
     674              :   #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)
     675              :   #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))
     676              : 
     677              :   /* DFS traversal to find inner loops in the cfg.  */
     678              : 
     679          127 :   current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->succs);
     680          127 :   sp = -1;
     681              : 
     682         2416 :   while (1)
     683              :     {
     684         2416 :       if (EDGE_PASSED (current_edge))
     685              :         {
     686              :           /* We have reached a leaf node or a node that was already
     687              :              processed.  Pop edges off the stack until we find
     688              :              an edge that has not yet been processed.  */
     689         1710 :           while (sp >= 0 && EDGE_PASSED (current_edge))
     690              :             {
     691              :               /* Pop entry off the stack.  */
     692         1147 :               current_edge = stack[sp--];
     693         1147 :               node = ei_edge (current_edge)->src->index;
     694         1147 :               gcc_assert (node != ENTRY_BLOCK);
     695         1147 :               child = ei_edge (current_edge)->dest->index;
     696         1147 :               gcc_assert (child != EXIT_BLOCK);
     697         1147 :               bitmap_clear_bit (in_stack, child);
     698         1147 :               if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
     699          208 :                 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
     700         1147 :               ei_next (&current_edge);
     701              :             }
     702              : 
     703              :           /* See if have finished the DFS tree traversal.  */
     704          563 :           if (sp < 0 && EDGE_PASSED (current_edge))
     705              :             break;
     706              : 
     707              :           /* Nope, continue the traversal with the popped node.  */
     708          436 :           continue;
     709              :         }
     710              : 
     711              :       /* Process a node.  */
     712         1853 :       node = ei_edge (current_edge)->src->index;
     713         1853 :       gcc_assert (node != ENTRY_BLOCK);
     714         1853 :       bitmap_set_bit (in_stack, node);
     715         1853 :       dfs_nr[node] = ++count;
     716              : 
     717              :       /* We don't traverse to the exit block.  */
     718         1853 :       child = ei_edge (current_edge)->dest->index;
     719         1853 :       if (child == EXIT_BLOCK)
     720              :         {
     721          125 :           SET_EDGE_PASSED (current_edge);
     722          125 :           ei_next (&current_edge);
     723          125 :           continue;
     724              :         }
     725              : 
     726              :       /* If the successor is in the stack, then we've found a loop.
     727              :          Mark the loop, if it is not a natural loop, then it will
     728              :          be rejected during the second traversal.  */
     729         1728 :       if (bitmap_bit_p (in_stack, child))
     730              :         {
     731          140 :           no_loops = 0;
     732          140 :           bitmap_set_bit (header, child);
     733          140 :           UPDATE_LOOP_RELATIONS (node, child);
     734          140 :           SET_EDGE_PASSED (current_edge);
     735          140 :           ei_next (&current_edge);
     736          140 :           continue;
     737              :         }
     738              : 
     739              :       /* If the child was already visited, then there is no need to visit
     740              :          it again.  Just update the loop relationships and restart
     741              :          with a new edge.  */
     742         1588 :       if (dfs_nr[child])
     743              :         {
     744          441 :           if (max_hdr[child] >= 0 && bitmap_bit_p (in_stack, max_hdr[child]))
     745           42 :             UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
     746          441 :           SET_EDGE_PASSED (current_edge);
     747          441 :           ei_next (&current_edge);
     748          441 :           continue;
     749              :         }
     750              : 
     751              :       /* Push an entry on the stack and continue DFS traversal.  */
     752         1147 :       stack[++sp] = current_edge;
     753         1147 :       SET_EDGE_PASSED (current_edge);
     754         1147 :       current_edge = ei_start (ei_edge (current_edge)->dest->succs);
     755              :     }
     756              : 
     757              :   /* Reset ->aux field used by EDGE_PASSED.  */
     758         1636 :   FOR_ALL_BB_FN (bb, cfun)
     759              :     {
     760         1509 :       edge_iterator ei;
     761         1509 :       edge e;
     762         3489 :       FOR_EACH_EDGE (e, ei, bb->succs)
     763         1980 :         e->aux = NULL;
     764              :     }
     765              : 
     766              : 
     767              :   /* Another check for unreachable blocks.  The earlier test in
     768              :      is_cfg_nonregular only finds unreachable blocks that do not
     769              :      form a loop.
     770              : 
     771              :      The DFS traversal will mark every block that is reachable from
     772              :      the entry node by placing a nonzero value in dfs_nr.  Thus if
     773              :      dfs_nr is zero for any block, then it must be unreachable.  */
     774          127 :   unreachable = false;
     775         1309 :   FOR_EACH_BB_FN (bb, cfun)
     776         1216 :     if (dfs_nr[bb->index] == 0)
     777              :       {
     778              :         unreachable = true;
     779              :         break;
     780              :       }
     781              : 
     782              :   /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
     783              :      to hold degree counts.  */
     784          127 :   degree = dfs_nr;
     785              : 
     786         1382 :   FOR_EACH_BB_FN (bb, cfun)
     787         2510 :     degree[bb->index] = EDGE_COUNT (bb->preds);
     788              : 
     789              :   /* Do not perform region scheduling if there are any unreachable
     790              :      blocks.  */
     791          127 :   if (!unreachable)
     792              :     {
     793           93 :       int *queue, *degree1 = NULL;
     794              :       /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
     795              :          there basic blocks, which are forced to be region heads.
     796              :          This is done to try to assemble few smaller regions
     797              :          from a too_large region.  */
     798           93 :       sbitmap extended_rgn_header = NULL;
     799           93 :       bool extend_regions_p;
     800              : 
     801           93 :       if (no_loops)
     802           22 :         bitmap_set_bit (header, 0);
     803              : 
     804              :       /* Second traversal:find reducible inner loops and topologically sort
     805              :          block of each region.  */
     806              : 
     807           93 :       queue = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
     808              : 
     809           93 :       extend_regions_p = param_max_sched_extend_regions_iters > 0;
     810           93 :       if (extend_regions_p)
     811              :         {
     812            2 :           degree1 = XNEWVEC (int, last_basic_block_for_fn (cfun));
     813            2 :           extended_rgn_header =
     814            2 :             sbitmap_alloc (last_basic_block_for_fn (cfun));
     815            2 :           bitmap_clear (extended_rgn_header);
     816              :         }
     817              : 
     818              :       /* Find blocks which are inner loop headers.  We still have non-reducible
     819              :          loops to consider at this point.  */
     820         1193 :       FOR_EACH_BB_FN (bb, cfun)
     821              :         {
     822         1100 :           if (bitmap_bit_p (header, bb->index) && bitmap_bit_p (inner, bb->index))
     823              :             {
     824           95 :               edge e;
     825           95 :               edge_iterator ei;
     826           95 :               basic_block jbb;
     827              : 
     828              :               /* Now check that the loop is reducible.  We do this separate
     829              :                  from finding inner loops so that we do not find a reducible
     830              :                  loop which contains an inner non-reducible loop.
     831              : 
     832              :                  A simple way to find reducible/natural loops is to verify
     833              :                  that each block in the loop is dominated by the loop
     834              :                  header.
     835              : 
     836              :                  If there exists a block that is not dominated by the loop
     837              :                  header, then the block is reachable from outside the loop
     838              :                  and thus the loop is not a natural loop.  */
     839         1650 :               FOR_EACH_BB_FN (jbb, cfun)
     840              :                 {
     841              :                   /* First identify blocks in the loop, except for the loop
     842              :                      entry block.  */
     843         1562 :                   if (bb->index == max_hdr[jbb->index] && bb != jbb)
     844              :                     {
     845              :                       /* Now verify that the block is dominated by the loop
     846              :                          header.  */
     847          104 :                       if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
     848              :                         break;
     849              :                     }
     850              :                 }
     851              : 
     852              :               /* If we exited the loop early, then I is the header of
     853              :                  a non-reducible loop and we should quit processing it
     854              :                  now.  */
     855           95 :               if (jbb != EXIT_BLOCK_PTR_FOR_FN (cfun))
     856            7 :                 continue;
     857              : 
     858              :               /* I is a header of an inner loop, or block 0 in a subroutine
     859              :                  with no loops at all.  */
     860           88 :               head = tail = -1;
     861           88 :               too_large_failure = false;
     862           88 :               loop_head = max_hdr[bb->index];
     863              : 
     864           88 :               if (extend_regions_p)
     865              :                 /* We save degree in case when we meet a too_large region
     866              :                    and cancel it.  We need a correct degree later when
     867              :                    calling extend_rgns.  */
     868            1 :                 memcpy (degree1, degree,
     869            1 :                         last_basic_block_for_fn (cfun) * sizeof (int));
     870              : 
     871              :               /* Decrease degree of all I's successors for topological
     872              :                  ordering.  */
     873          244 :               FOR_EACH_EDGE (e, ei, bb->succs)
     874          156 :                 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
     875          155 :                   --degree[e->dest->index];
     876              : 
     877              :               /* Estimate # insns, and count # blocks in the region.  */
     878           88 :               num_bbs = 1;
     879           88 :               num_insns = common_sched_info->estimate_number_of_insns (bb);
     880              : 
     881              :               /* Find all loop latches (blocks with back edges to the loop
     882              :                  header) or all the leaf blocks in the cfg has no loops.
     883              : 
     884              :                  Place those blocks into the queue.  */
     885           88 :               if (no_loops)
     886              :                 {
     887            0 :                   FOR_EACH_BB_FN (jbb, cfun)
     888              :                     /* Leaf nodes have only a single successor which must
     889              :                        be EXIT_BLOCK.  */
     890            0 :                     if (single_succ_p (jbb)
     891            0 :                         && single_succ (jbb) == EXIT_BLOCK_PTR_FOR_FN (cfun))
     892              :                       {
     893            0 :                         queue[++tail] = jbb->index;
     894            0 :                         bitmap_set_bit (in_queue, jbb->index);
     895              : 
     896            0 :                         if (too_large (jbb->index, &num_bbs, &num_insns))
     897              :                           {
     898           88 :                             too_large_failure = true;
     899              :                             break;
     900              :                           }
     901              :                       }
     902              :                 }
     903              :               else
     904              :                 {
     905           88 :                   edge e;
     906              : 
     907          290 :                   FOR_EACH_EDGE (e, ei, bb->preds)
     908              :                     {
     909          203 :                       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     910            0 :                         continue;
     911              : 
     912          203 :                       node = e->src->index;
     913              : 
     914          203 :                       if (max_hdr[node] == loop_head && node != bb->index)
     915              :                         {
     916              :                           /* This is a loop latch.  */
     917           43 :                           queue[++tail] = node;
     918           43 :                           bitmap_set_bit (in_queue, node);
     919              : 
     920           43 :                           if (too_large (node, &num_bbs, &num_insns))
     921              :                             {
     922              :                               too_large_failure = true;
     923              :                               break;
     924              :                             }
     925              :                         }
     926              :                     }
     927              :                 }
     928              : 
     929              :               /* Now add all the blocks in the loop to the queue.
     930              : 
     931              :              We know the loop is a natural loop; however the algorithm
     932              :              above will not always mark certain blocks as being in the
     933              :              loop.  Consider:
     934              :                 node   children
     935              :                  a        b,c
     936              :                  b        c
     937              :                  c        a,d
     938              :                  d        b
     939              : 
     940              :              The algorithm in the DFS traversal may not mark B & D as part
     941              :              of the loop (i.e. they will not have max_hdr set to A).
     942              : 
     943              :              We know they cannot be loop latches (else they would have
     944              :              had max_hdr set since they'd have a backedge to a dominator
     945              :              block).  So we don't need them on the initial queue.
     946              : 
     947              :              We know they are part of the loop because they are dominated
     948              :              by the loop header and can be reached by a backwards walk of
     949              :              the edges starting with nodes on the initial queue.
     950              : 
     951              :              It is safe and desirable to include those nodes in the
     952              :              loop/scheduling region.  To do so we would need to decrease
     953              :              the degree of a node if it is the target of a backedge
     954              :              within the loop itself as the node is placed in the queue.
     955              : 
     956              :              We do not do this because I'm not sure that the actual
     957              :              scheduling code will properly handle this case. ?!? */
     958              : 
     959          182 :               while (head < tail && !too_large_failure)
     960              :                 {
     961           94 :                   edge e;
     962           94 :                   child = queue[++head];
     963              : 
     964          207 :                   FOR_EACH_EDGE (e, ei,
     965              :                                  BASIC_BLOCK_FOR_FN (cfun, child)->preds)
     966              :                     {
     967          113 :                       node = e->src->index;
     968              : 
     969              :                       /* See discussion above about nodes not marked as in
     970              :                          this loop during the initial DFS traversal.  */
     971          113 :                       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
     972          113 :                           || max_hdr[node] != loop_head)
     973              :                         {
     974              :                           tail = -1;
     975              :                           break;
     976              :                         }
     977          113 :                       else if (!bitmap_bit_p (in_queue, node) && node != bb->index)
     978              :                         {
     979           52 :                           queue[++tail] = node;
     980           52 :                           bitmap_set_bit (in_queue, node);
     981              : 
     982           52 :                           if (too_large (node, &num_bbs, &num_insns))
     983              :                             {
     984              :                               too_large_failure = true;
     985              :                               break;
     986              :                             }
     987              :                         }
     988              :                     }
     989              :                 }
     990              : 
     991           88 :               if (tail >= 0 && !too_large_failure)
     992              :                 {
     993              :                   /* Place the loop header into list of region blocks.  */
     994           41 :                   degree[bb->index] = -1;
     995           41 :                   rgn_bb_table[idx] = bb->index;
     996           41 :                   RGN_NR_BLOCKS (nr_regions) = num_bbs;
     997           41 :                   RGN_BLOCKS (nr_regions) = idx++;
     998           41 :                   RGN_DONT_CALC_DEPS (nr_regions) = 0;
     999           41 :                   RGN_HAS_REAL_EBB (nr_regions) = 0;
    1000           41 :                   CONTAINING_RGN (bb->index) = nr_regions;
    1001           41 :                   BLOCK_TO_BB (bb->index) = count = 0;
    1002              : 
    1003              :                   /* Remove blocks from queue[] when their in degree
    1004              :                      becomes zero.  Repeat until no blocks are left on the
    1005              :                      list.  This produces a topological list of blocks in
    1006              :                      the region.  */
    1007          188 :                   while (tail >= 0)
    1008              :                     {
    1009          147 :                       if (head < 0)
    1010            0 :                         head = tail;
    1011          147 :                       child = queue[head];
    1012          147 :                       if (degree[child] == 0)
    1013              :                         {
    1014           94 :                           edge e;
    1015              : 
    1016           94 :                           degree[child] = -1;
    1017           94 :                           rgn_bb_table[idx++] = child;
    1018           94 :                           BLOCK_TO_BB (child) = ++count;
    1019           94 :                           CONTAINING_RGN (child) = nr_regions;
    1020           94 :                           queue[head] = queue[tail--];
    1021              : 
    1022          252 :                           FOR_EACH_EDGE (e, ei,
    1023              :                                          BASIC_BLOCK_FOR_FN (cfun,
    1024              :                                                              child)->succs)
    1025          158 :                             if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1026          158 :                               --degree[e->dest->index];
    1027              :                         }
    1028              :                       else
    1029           53 :                         --head;
    1030              :                     }
    1031           41 :                   ++nr_regions;
    1032              :                 }
    1033           47 :               else if (extend_regions_p)
    1034              :                 {
    1035              :                   /* Restore DEGREE.  */
    1036            0 :                   int *t = degree;
    1037              : 
    1038            0 :                   degree = degree1;
    1039            0 :                   degree1 = t;
    1040              : 
    1041              :                   /* And force successors of BB to be region heads.
    1042              :                      This may provide several smaller regions instead
    1043              :                      of one too_large region.  */
    1044            0 :                   FOR_EACH_EDGE (e, ei, bb->succs)
    1045            0 :                     if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1046            0 :                       bitmap_set_bit (extended_rgn_header, e->dest->index);
    1047              :                 }
    1048              :             }
    1049              :         }
    1050           93 :       free (queue);
    1051              : 
    1052           93 :       if (extend_regions_p)
    1053              :         {
    1054            2 :           free (degree1);
    1055              : 
    1056            2 :           bitmap_ior (header, header, extended_rgn_header);
    1057            2 :           sbitmap_free (extended_rgn_header);
    1058              : 
    1059            2 :           extend_rgns (degree, &idx, header, max_hdr);
    1060              :         }
    1061              :     }
    1062              : 
    1063              :   /* Any block that did not end up in a region is placed into a region
    1064              :      by itself.  */
    1065         1382 :   FOR_EACH_BB_FN (bb, cfun)
    1066         1255 :     if (degree[bb->index] >= 0)
    1067              :       {
    1068         1098 :         rgn_bb_table[idx] = bb->index;
    1069         1098 :         RGN_NR_BLOCKS (nr_regions) = 1;
    1070         1098 :         RGN_BLOCKS (nr_regions) = idx++;
    1071         1098 :         RGN_DONT_CALC_DEPS (nr_regions) = 0;
    1072         1098 :         RGN_HAS_REAL_EBB (nr_regions) = 0;
    1073         1098 :         CONTAINING_RGN (bb->index) = nr_regions++;
    1074         1098 :         BLOCK_TO_BB (bb->index) = 0;
    1075              :       }
    1076              : 
    1077          127 :   free (max_hdr);
    1078          127 :   free (degree);
    1079          127 :   free (stack);
    1080          127 : }
    1081              : 
    1082              : 
    1083              : /* Wrapper function.
    1084              :    If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
    1085              :    regions.  Otherwise just call find_rgns_haifa.  */
    1086              : static void
    1087          170 : find_rgns (void)
    1088              : {
    1089          170 :   if (sel_sched_p () && flag_sel_sched_pipelining)
    1090           43 :     sel_find_rgns ();
    1091              :   else
    1092          127 :     haifa_find_rgns ();
    1093          170 : }
    1094              : 
    1095              : static int gather_region_statistics (int **);
    1096              : static void print_region_statistics (int *, int, int *, int);
    1097              : 
    1098              : /* Calculate the histogram that shows the number of regions having the
    1099              :    given number of basic blocks, and store it in the RSP array.  Return
    1100              :    the size of this array.  */
    1101              : static int
    1102            0 : gather_region_statistics (int **rsp)
    1103              : {
    1104            0 :   int i, *a = 0, a_sz = 0;
    1105              : 
    1106              :   /* a[i] is the number of regions that have (i + 1) basic blocks.  */
    1107            0 :   for (i = 0; i < nr_regions; i++)
    1108              :     {
    1109            0 :       int nr_blocks = RGN_NR_BLOCKS (i);
    1110              : 
    1111            0 :       gcc_assert (nr_blocks >= 1);
    1112              : 
    1113            0 :       if (nr_blocks > a_sz)
    1114              :         {
    1115            0 :           a = XRESIZEVEC (int, a, nr_blocks);
    1116            0 :           do
    1117            0 :             a[a_sz++] = 0;
    1118            0 :           while (a_sz != nr_blocks);
    1119              :         }
    1120              : 
    1121            0 :       a[nr_blocks - 1]++;
    1122              :     }
    1123              : 
    1124            0 :   *rsp = a;
    1125            0 :   return a_sz;
    1126              : }
    1127              : 
    1128              : /* Print regions statistics.  S1 and S2 denote the data before and after
    1129              :    calling extend_rgns, respectively.  */
    1130              : static void
    1131            0 : print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
    1132              : {
    1133            0 :   int i;
    1134              : 
    1135              :   /* We iterate until s2_sz because extend_rgns does not decrease
    1136              :      the maximal region size.  */
    1137            0 :   for (i = 1; i < s2_sz; i++)
    1138              :     {
    1139            0 :       int n1, n2;
    1140              : 
    1141            0 :       n2 = s2[i];
    1142              : 
    1143            0 :       if (n2 == 0)
    1144            0 :         continue;
    1145              : 
    1146            0 :       if (i >= s1_sz)
    1147              :         n1 = 0;
    1148              :       else
    1149            0 :         n1 = s1[i];
    1150              : 
    1151            0 :       fprintf (sched_dump, ";; Region extension statistics: size %d: " \
    1152              :                "was %d + %d more\n", i + 1, n1, n2 - n1);
    1153              :     }
    1154            0 : }
    1155              : 
    1156              : /* Extend regions.
    1157              :    DEGREE - Array of incoming edge count, considering only
    1158              :    the edges, that don't have their sources in formed regions yet.
    1159              :    IDXP - pointer to the next available index in rgn_bb_table.
    1160              :    HEADER - set of all region heads.
    1161              :    LOOP_HDR - mapping from block to the containing loop
    1162              :    (two blocks can reside within one region if they have
    1163              :    the same loop header).  */
    1164              : void
    1165           45 : extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
    1166              : {
    1167           45 :   int *order, i, idx = *idxp, iter = 0, max_iter, *max_hdr;
    1168           45 :   int nblocks = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
    1169           45 :   bool rescan = false;
    1170              : 
    1171           45 :   max_iter = param_max_sched_extend_regions_iters;
    1172              : 
    1173           45 :   max_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1174              : 
    1175           45 :   order = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1176           45 :   post_order_compute (order, false, false);
    1177              : 
    1178          578 :   for (i = nblocks - 1; i >= 0; i--)
    1179              :     {
    1180          533 :       int bbn = order[i];
    1181          533 :       if (degree[bbn] >= 0)
    1182              :         {
    1183          254 :           max_hdr[bbn] = bbn;
    1184          254 :           rescan = true;
    1185              :         }
    1186              :       else
    1187              :         /* This block already was processed in find_rgns.  */
    1188          279 :         max_hdr[bbn] = -1;
    1189              :     }
    1190              : 
    1191              :   /* The idea is to topologically walk through CFG in top-down order.
    1192              :      During the traversal, if all the predecessors of a node are
    1193              :      marked to be in the same region (they all have the same max_hdr),
    1194              :      then current node is also marked to be a part of that region.
    1195              :      Otherwise the node starts its own region.
    1196              :      CFG should be traversed until no further changes are made.  On each
    1197              :      iteration the set of the region heads is extended (the set of those
    1198              :      blocks that have max_hdr[bbi] == bbi).  This set is upper bounded by the
    1199              :      set of all basic blocks, thus the algorithm is guaranteed to
    1200              :      terminate.  */
    1201              : 
    1202           49 :   while (rescan && iter < max_iter)
    1203              :     {
    1204              :       rescan = false;
    1205              : 
    1206           52 :       for (i = nblocks - 1; i >= 0; i--)
    1207              :         {
    1208           48 :           edge e;
    1209           48 :           edge_iterator ei;
    1210           48 :           int bbn = order[i];
    1211              : 
    1212           48 :           if (max_hdr[bbn] != -1 && !bitmap_bit_p (header, bbn))
    1213              :             {
    1214           41 :               int hdr = -1;
    1215              : 
    1216           91 :               FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->preds)
    1217              :                 {
    1218           53 :                   int predn = e->src->index;
    1219              : 
    1220           53 :                   if (predn != ENTRY_BLOCK
    1221              :                       /* If pred wasn't processed in find_rgns.  */
    1222           51 :                       && max_hdr[predn] != -1
    1223              :                       /* And pred and bb reside in the same loop.
    1224              :                          (Or out of any loop).  */
    1225           50 :                       && loop_hdr[bbn] == loop_hdr[predn])
    1226              :                     {
    1227           50 :                       if (hdr == -1)
    1228              :                         /* Then bb extends the containing region of pred.  */
    1229              :                         hdr = max_hdr[predn];
    1230           12 :                       else if (hdr != max_hdr[predn])
    1231              :                         /* Too bad, there are at least two predecessors
    1232              :                            that reside in different regions.  Thus, BB should
    1233              :                            begin its own region.  */
    1234              :                         {
    1235              :                           hdr = bbn;
    1236              :                           break;
    1237              :                         }
    1238              :                     }
    1239              :                   else
    1240              :                     /* BB starts its own region.  */
    1241              :                     {
    1242              :                       hdr = bbn;
    1243              :                       break;
    1244              :                     }
    1245              :                 }
    1246              : 
    1247           41 :               if (hdr == bbn)
    1248              :                 {
    1249              :                   /* If BB start its own region,
    1250              :                      update set of headers with BB.  */
    1251            3 :                   bitmap_set_bit (header, bbn);
    1252            3 :                   rescan = true;
    1253              :                 }
    1254              :               else
    1255           38 :                 gcc_assert (hdr != -1);
    1256              : 
    1257           41 :               max_hdr[bbn] = hdr;
    1258              :             }
    1259              :         }
    1260              : 
    1261            4 :       iter++;
    1262              :     }
    1263              : 
    1264              :   /* Statistics were gathered on the SPEC2000 package of tests with
    1265              :      mainline weekly snapshot gcc-4.1-20051015 on ia64.
    1266              : 
    1267              :      Statistics for SPECint:
    1268              :      1 iteration : 1751 cases (38.7%)
    1269              :      2 iterations: 2770 cases (61.3%)
    1270              :      Blocks wrapped in regions by find_rgns without extension: 18295 blocks
    1271              :      Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
    1272              :      (We don't count single block regions here).
    1273              : 
    1274              :      Statistics for SPECfp:
    1275              :      1 iteration : 621 cases (35.9%)
    1276              :      2 iterations: 1110 cases (64.1%)
    1277              :      Blocks wrapped in regions by find_rgns without extension: 6476 blocks
    1278              :      Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
    1279              :      (We don't count single block regions here).
    1280              : 
    1281              :      By default we do at most 2 iterations.
    1282              :      This can be overridden with max-sched-extend-regions-iters parameter:
    1283              :      0 - disable region extension,
    1284              :      N > 0 - do at most N iterations.  */
    1285              : 
    1286           45 :   if (sched_verbose && iter != 0)
    1287            0 :     fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
    1288              :              rescan ? "... failed" : "");
    1289              : 
    1290           45 :   if (!rescan && iter != 0)
    1291              :     {
    1292            2 :       int *s1 = NULL, s1_sz = 0;
    1293              : 
    1294              :       /* Save the old statistics for later printout.  */
    1295            2 :       if (sched_verbose >= 6)
    1296            0 :         s1_sz = gather_region_statistics (&s1);
    1297              : 
    1298              :       /* We have succeeded.  Now assemble the regions.  */
    1299           26 :       for (i = nblocks - 1; i >= 0; i--)
    1300              :         {
    1301           24 :           int bbn = order[i];
    1302              : 
    1303           24 :           if (max_hdr[bbn] == bbn)
    1304              :             /* BBN is a region head.  */
    1305              :             {
    1306            3 :               edge e;
    1307            3 :               edge_iterator ei;
    1308            3 :               int num_bbs = 0, j, num_insns = 0, large;
    1309              : 
    1310            3 :               large = too_large (bbn, &num_bbs, &num_insns);
    1311              : 
    1312            3 :               degree[bbn] = -1;
    1313            3 :               rgn_bb_table[idx] = bbn;
    1314            3 :               RGN_BLOCKS (nr_regions) = idx++;
    1315            3 :               RGN_DONT_CALC_DEPS (nr_regions) = 0;
    1316            3 :               RGN_HAS_REAL_EBB (nr_regions) = 0;
    1317            3 :               CONTAINING_RGN (bbn) = nr_regions;
    1318            3 :               BLOCK_TO_BB (bbn) = 0;
    1319              : 
    1320            8 :               FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, bbn)->succs)
    1321            5 :                 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1322            4 :                   degree[e->dest->index]--;
    1323              : 
    1324            3 :               if (!large)
    1325              :                 /* Here we check whether the region is too_large.  */
    1326           22 :                 for (j = i - 1; j >= 0; j--)
    1327              :                   {
    1328           20 :                     int succn = order[j];
    1329           20 :                     if (max_hdr[succn] == bbn)
    1330              :                       {
    1331           19 :                         if ((large = too_large (succn, &num_bbs, &num_insns)))
    1332              :                           break;
    1333              :                       }
    1334              :                   }
    1335              : 
    1336            3 :               if (large)
    1337              :                 /* If the region is too_large, then wrap every block of
    1338              :                    the region into single block region.
    1339              :                    Here we wrap region head only.  Other blocks are
    1340              :                    processed in the below cycle.  */
    1341              :                 {
    1342            1 :                   RGN_NR_BLOCKS (nr_regions) = 1;
    1343            1 :                   nr_regions++;
    1344              :                 }
    1345              : 
    1346            3 :               num_bbs = 1;
    1347              : 
    1348           26 :               for (j = i - 1; j >= 0; j--)
    1349              :                 {
    1350           23 :                   int succn = order[j];
    1351              : 
    1352           23 :                   if (max_hdr[succn] == bbn)
    1353              :                     /* This cycle iterates over all basic blocks, that
    1354              :                        are supposed to be in the region with head BBN,
    1355              :                        and wraps them into that region (or in single
    1356              :                        block region).  */
    1357              :                     {
    1358           19 :                       gcc_assert (degree[succn] == 0);
    1359              : 
    1360           19 :                       degree[succn] = -1;
    1361           19 :                       rgn_bb_table[idx] = succn;
    1362           19 :                       BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
    1363           19 :                       CONTAINING_RGN (succn) = nr_regions;
    1364              : 
    1365           19 :                       if (large)
    1366              :                         /* Wrap SUCCN into single block region.  */
    1367              :                         {
    1368           15 :                           RGN_BLOCKS (nr_regions) = idx;
    1369           15 :                           RGN_NR_BLOCKS (nr_regions) = 1;
    1370           15 :                           RGN_DONT_CALC_DEPS (nr_regions) = 0;
    1371           15 :                           RGN_HAS_REAL_EBB (nr_regions) = 0;
    1372           15 :                           nr_regions++;
    1373              :                         }
    1374              : 
    1375           19 :                       idx++;
    1376              : 
    1377           45 :                       FOR_EACH_EDGE (e, ei,
    1378              :                                      BASIC_BLOCK_FOR_FN (cfun, succn)->succs)
    1379           26 :                         if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1380           25 :                           degree[e->dest->index]--;
    1381              :                     }
    1382              :                 }
    1383              : 
    1384            3 :               if (!large)
    1385              :                 {
    1386            2 :                   RGN_NR_BLOCKS (nr_regions) = num_bbs;
    1387            2 :                   nr_regions++;
    1388              :                 }
    1389              :             }
    1390              :         }
    1391              : 
    1392            2 :       if (sched_verbose >= 6)
    1393              :         {
    1394            0 :           int *s2, s2_sz;
    1395              : 
    1396              :           /* Get the new statistics and print the comparison with the
    1397              :              one before calling this function.  */
    1398            0 :           s2_sz = gather_region_statistics (&s2);
    1399            0 :           print_region_statistics (s1, s1_sz, s2, s2_sz);
    1400            0 :           free (s1);
    1401            0 :           free (s2);
    1402              :         }
    1403              :     }
    1404              : 
    1405           45 :   free (order);
    1406           45 :   free (max_hdr);
    1407              : 
    1408           45 :   *idxp = idx;
    1409           45 : }
    1410              : 
    1411              : /* Functions for regions scheduling information.  */
    1412              : 
    1413              : /* Compute dominators, probability, and potential-split-edges of bb.
    1414              :    Assume that these values were already computed for bb's predecessors.  */
    1415              : 
    1416              : static void
    1417           72 : compute_dom_prob_ps (int bb)
    1418              : {
    1419           72 :   edge_iterator in_ei;
    1420           72 :   edge in_edge;
    1421              : 
    1422              :   /* We shouldn't have any real ebbs yet.  */
    1423           72 :   gcc_assert (ebb_head [bb] == bb + current_blocks);
    1424              : 
    1425           72 :   if (IS_RGN_ENTRY (bb))
    1426              :     {
    1427           26 :       bitmap_set_bit (dom[bb], 0);
    1428           26 :       prob[bb] = REG_BR_PROB_BASE;
    1429           26 :       return;
    1430              :     }
    1431              : 
    1432           46 :   prob[bb] = 0;
    1433              : 
    1434              :   /* Initialize dom[bb] to '111..1'.  */
    1435           46 :   bitmap_ones (dom[bb]);
    1436              : 
    1437           93 :   FOR_EACH_EDGE (in_edge, in_ei,
    1438              :                  BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb))->preds)
    1439              :     {
    1440           47 :       int pred_bb;
    1441           47 :       edge out_edge;
    1442           47 :       edge_iterator out_ei;
    1443              : 
    1444           47 :       if (in_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1445            0 :         continue;
    1446              : 
    1447           47 :       pred_bb = BLOCK_TO_BB (in_edge->src->index);
    1448           47 :       bitmap_and (dom[bb], dom[bb], dom[pred_bb]);
    1449           47 :       bitmap_ior (ancestor_edges[bb],
    1450           47 :                       ancestor_edges[bb], ancestor_edges[pred_bb]);
    1451              : 
    1452           47 :       bitmap_set_bit (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
    1453              : 
    1454           47 :       bitmap_ior (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
    1455              : 
    1456          139 :       FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
    1457           92 :         bitmap_set_bit (pot_split[bb], EDGE_TO_BIT (out_edge));
    1458              : 
    1459           94 :       prob[bb] += combine_probabilities
    1460           94 :                  (prob[pred_bb],
    1461           47 :                   in_edge->probability.initialized_p ()
    1462           47 :                   ? in_edge->probability.to_reg_br_prob_base ()
    1463              :                   : 0);
    1464              :       // The rounding divide in combine_probabilities can result in an extra
    1465              :       // probability increment propagating along 50-50 edges. Eventually when
    1466              :       // the edges re-merge, the accumulated probability can go slightly above
    1467              :       // REG_BR_PROB_BASE.
    1468           47 :       if (prob[bb] > REG_BR_PROB_BASE)
    1469            0 :         prob[bb] = REG_BR_PROB_BASE;
    1470              :     }
    1471              : 
    1472           46 :   bitmap_set_bit (dom[bb], bb);
    1473           46 :   bitmap_and_compl (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
    1474              : 
    1475           46 :   if (sched_verbose >= 2)
    1476            0 :     fprintf (sched_dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
    1477            0 :              (100 * prob[bb]) / REG_BR_PROB_BASE);
    1478              : }
    1479              : 
    1480              : /* Functions for target info.  */
    1481              : 
    1482              : /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
    1483              :    Note that bb_trg dominates bb_src.  */
    1484              : 
    1485              : static void
    1486           51 : split_edges (int bb_src, int bb_trg, edgelst *bl)
    1487              : {
    1488           51 :   auto_sbitmap src (SBITMAP_SIZE (pot_split[bb_src]));
    1489           51 :   bitmap_copy (src, pot_split[bb_src]);
    1490              : 
    1491           51 :   bitmap_and_compl (src, src, pot_split[bb_trg]);
    1492           51 :   extract_edgelst (src, bl);
    1493           51 : }
    1494              : 
    1495              : /* Find the valid candidate-source-blocks for the target block TRG, compute
    1496              :    their probability, and check if they are speculative or not.
    1497              :    For speculative sources, compute their update-blocks and split-blocks.  */
    1498              : 
    1499              : static void
    1500           72 : compute_trg_info (int trg)
    1501              : {
    1502           72 :   candidate *sp;
    1503           72 :   edgelst el = { NULL, 0 };
    1504           72 :   int i, j, k, update_idx;
    1505           72 :   basic_block block;
    1506           72 :   edge_iterator ei;
    1507           72 :   edge e;
    1508              : 
    1509           72 :   candidate_table = XNEWVEC (candidate, current_nr_blocks);
    1510              : 
    1511           72 :   bblst_last = 0;
    1512              :   /* bblst_table holds split blocks and update blocks for each block after
    1513              :      the current one in the region.  split blocks and update blocks are
    1514              :      the TO blocks of region edges, so there can be at most rgn_nr_edges
    1515              :      of them.  */
    1516           72 :   bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
    1517           72 :   bblst_table = XNEWVEC (basic_block, bblst_size);
    1518              : 
    1519           72 :   edgelst_last = 0;
    1520           72 :   edgelst_table = XNEWVEC (edge, rgn_nr_edges);
    1521              : 
    1522              :   /* Define some of the fields for the target bb as well.  */
    1523           72 :   sp = candidate_table + trg;
    1524           72 :   sp->is_valid = 1;
    1525           72 :   sp->is_speculative = 0;
    1526           72 :   sp->src_prob = REG_BR_PROB_BASE;
    1527              : 
    1528           72 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
    1529              : 
    1530          154 :   for (i = trg + 1; i < current_nr_blocks; i++)
    1531              :     {
    1532           82 :       sp = candidate_table + i;
    1533              : 
    1534           82 :       sp->is_valid = IS_DOMINATED (i, trg);
    1535           82 :       if (sp->is_valid)
    1536              :         {
    1537           74 :           int tf = prob[trg], cf = prob[i];
    1538              : 
    1539              :           /* In CFGs with low probability edges TF can possibly be zero.  */
    1540           74 :           sp->src_prob = (tf ?
    1541           74 :                           profile_count::from_gcov_type (cf)
    1542              :                             .probability_in
    1543           74 :                               (profile_count::from_gcov_type (tf))
    1544           74 :                                 .to_reg_br_prob_base ()
    1545              :                           : 0);
    1546           74 :           sp->is_valid = (sp->src_prob >= min_spec_prob);
    1547              :         }
    1548              : 
    1549           82 :       if (sp->is_valid)
    1550              :         {
    1551           51 :           split_edges (i, trg, &el);
    1552           51 :           sp->is_speculative = (el.nr_members) ? 1 : 0;
    1553           51 :           if (sp->is_speculative && !flag_schedule_speculative)
    1554            0 :             sp->is_valid = 0;
    1555              :         }
    1556              : 
    1557           82 :       if (sp->is_valid)
    1558              :         {
    1559              :           /* Compute split blocks and store them in bblst_table.
    1560              :              The TO block of every split edge is a split block.  */
    1561           51 :           sp->split_bbs.first_member = &bblst_table[bblst_last];
    1562           51 :           sp->split_bbs.nr_members = el.nr_members;
    1563          123 :           for (j = 0; j < el.nr_members; bblst_last++, j++)
    1564           72 :             bblst_table[bblst_last] = el.first_member[j]->dest;
    1565           51 :           sp->update_bbs.first_member = &bblst_table[bblst_last];
    1566              : 
    1567              :           /* Compute update blocks and store them in bblst_table.
    1568              :              For every split edge, look at the FROM block, and check
    1569              :              all out edges.  For each out edge that is not a split edge,
    1570              :              add the TO block to the update block list.  This list can end
    1571              :              up with a lot of duplicates.  We need to weed them out to avoid
    1572              :              overrunning the end of the bblst_table.  */
    1573              : 
    1574           51 :           update_idx = 0;
    1575           51 :           bitmap_clear (visited);
    1576          174 :           for (j = 0; j < el.nr_members; j++)
    1577              :             {
    1578           72 :               block = el.first_member[j]->src;
    1579          216 :               FOR_EACH_EDGE (e, ei, block->succs)
    1580              :                 {
    1581          144 :                   if (!bitmap_bit_p (visited, e->dest->index))
    1582              :                     {
    1583          285 :                       for (k = 0; k < el.nr_members; k++)
    1584          213 :                         if (e == el.first_member[k])
    1585              :                           break;
    1586              : 
    1587          144 :                       if (k >= el.nr_members)
    1588              :                         {
    1589           72 :                           bblst_table[bblst_last++] = e->dest;
    1590           72 :                           bitmap_set_bit (visited, e->dest->index);
    1591           72 :                           update_idx++;
    1592              :                         }
    1593              :                     }
    1594              :                 }
    1595              :             }
    1596           51 :           sp->update_bbs.nr_members = update_idx;
    1597              : 
    1598              :           /* Make sure we didn't overrun the end of bblst_table.  */
    1599           51 :           gcc_assert (bblst_last <= bblst_size);
    1600              :         }
    1601              :       else
    1602              :         {
    1603           31 :           sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
    1604              : 
    1605           31 :           sp->is_speculative = 0;
    1606           31 :           sp->src_prob = 0;
    1607              :         }
    1608              :     }
    1609           72 : }
    1610              : 
    1611              : /* Free the computed target info.  */
    1612              : static void
    1613           72 : free_trg_info (void)
    1614              : {
    1615           72 :   free (candidate_table);
    1616           72 :   free (bblst_table);
    1617           72 :   free (edgelst_table);
    1618           72 : }
    1619              : 
    1620              : /* Print candidates info, for debugging purposes.  Callable from debugger.  */
    1621              : 
    1622              : DEBUG_FUNCTION void
    1623            0 : debug_candidate (int i)
    1624              : {
    1625            0 :   if (!candidate_table[i].is_valid)
    1626              :     return;
    1627              : 
    1628            0 :   if (candidate_table[i].is_speculative)
    1629              :     {
    1630            0 :       int j;
    1631            0 :       fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
    1632              : 
    1633            0 :       fprintf (sched_dump, "split path: ");
    1634            0 :       for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
    1635              :         {
    1636            0 :           int b = candidate_table[i].split_bbs.first_member[j]->index;
    1637              : 
    1638            0 :           fprintf (sched_dump, " %d ", b);
    1639              :         }
    1640            0 :       fprintf (sched_dump, "\n");
    1641              : 
    1642            0 :       fprintf (sched_dump, "update path: ");
    1643            0 :       for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
    1644              :         {
    1645            0 :           int b = candidate_table[i].update_bbs.first_member[j]->index;
    1646              : 
    1647            0 :           fprintf (sched_dump, " %d ", b);
    1648              :         }
    1649            0 :       fprintf (sched_dump, "\n");
    1650              :     }
    1651              :   else
    1652              :     {
    1653            0 :       fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
    1654              :     }
    1655              : }
    1656              : 
    1657              : /* Print candidates info, for debugging purposes.  Callable from debugger.  */
    1658              : 
    1659              : DEBUG_FUNCTION void
    1660            0 : debug_candidates (int trg)
    1661              : {
    1662            0 :   int i;
    1663              : 
    1664            0 :   fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
    1665            0 :            BB_TO_BLOCK (trg), trg);
    1666            0 :   for (i = trg + 1; i < current_nr_blocks; i++)
    1667            0 :     debug_candidate (i);
    1668            0 : }
    1669              : 
    1670              : /* Functions for speculative scheduling.  */
    1671              : 
    1672              : static bitmap_head not_in_df;
    1673              : 
    1674              : /* Return false if x is a set of a register alive in the beginning of one
    1675              :    of the split-blocks of src, otherwise return true.  */
    1676              : 
    1677              : static bool
    1678           19 : check_live_1 (int src, rtx x)
    1679              : {
    1680           19 :   int i;
    1681           19 :   int regno;
    1682           19 :   rtx reg = SET_DEST (x);
    1683              : 
    1684           19 :   if (reg == 0)
    1685              :     return true;
    1686              : 
    1687           19 :   while (GET_CODE (reg) == SUBREG
    1688           19 :          || GET_CODE (reg) == ZERO_EXTRACT
    1689           38 :          || GET_CODE (reg) == STRICT_LOW_PART)
    1690            0 :     reg = XEXP (reg, 0);
    1691              : 
    1692           19 :   if (GET_CODE (reg) == PARALLEL)
    1693              :     {
    1694            0 :       int i;
    1695              : 
    1696            0 :       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
    1697            0 :         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
    1698            0 :           if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
    1699              :             return true;
    1700              : 
    1701              :       return false;
    1702              :     }
    1703              : 
    1704           19 :   if (!REG_P (reg))
    1705              :     return true;
    1706              : 
    1707           16 :   regno = REGNO (reg);
    1708              : 
    1709           16 :   if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
    1710              :     {
    1711              :       /* Global registers are assumed live.  */
    1712              :       return false;
    1713              :     }
    1714              :   else
    1715              :     {
    1716           16 :       if (regno < FIRST_PSEUDO_REGISTER)
    1717              :         {
    1718              :           /* Check for hard registers.  */
    1719           12 :           int j = REG_NREGS (reg);
    1720           24 :           while (--j >= 0)
    1721              :             {
    1722           24 :               for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
    1723              :                 {
    1724           12 :                   basic_block b = candidate_table[src].split_bbs.first_member[i];
    1725           12 :                   int t = bitmap_bit_p (&not_in_df, b->index);
    1726              : 
    1727              :                   /* We can have split blocks, that were recently generated.
    1728              :                      Such blocks are always outside current region.  */
    1729           12 :                   gcc_assert (!t || (CONTAINING_RGN (b->index)
    1730              :                                      != CONTAINING_RGN (BB_TO_BLOCK (src))));
    1731              : 
    1732           12 :                   if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
    1733              :                     return false;
    1734              :                 }
    1735              :             }
    1736              :         }
    1737              :       else
    1738              :         {
    1739              :           /* Check for pseudo registers.  */
    1740            8 :           for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
    1741              :             {
    1742            5 :               basic_block b = candidate_table[src].split_bbs.first_member[i];
    1743            5 :               int t = bitmap_bit_p (&not_in_df, b->index);
    1744              : 
    1745            5 :               gcc_assert (!t || (CONTAINING_RGN (b->index)
    1746              :                                  != CONTAINING_RGN (BB_TO_BLOCK (src))));
    1747              : 
    1748            5 :               if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
    1749              :                 return false;
    1750              :             }
    1751              :         }
    1752              :     }
    1753              : 
    1754              :   return true;
    1755              : }
    1756              : 
    1757              : /* If x is a set of a register R, mark that R is alive in the beginning
    1758              :    of every update-block of src.  */
    1759              : 
    1760              : static void
    1761            0 : update_live_1 (int src, rtx x)
    1762              : {
    1763            0 :   int i;
    1764            0 :   int regno;
    1765            0 :   rtx reg = SET_DEST (x);
    1766              : 
    1767            0 :   if (reg == 0)
    1768              :     return;
    1769              : 
    1770            0 :   while (GET_CODE (reg) == SUBREG
    1771            0 :          || GET_CODE (reg) == ZERO_EXTRACT
    1772            0 :          || GET_CODE (reg) == STRICT_LOW_PART)
    1773            0 :     reg = XEXP (reg, 0);
    1774              : 
    1775            0 :   if (GET_CODE (reg) == PARALLEL)
    1776              :     {
    1777            0 :       int i;
    1778              : 
    1779            0 :       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
    1780            0 :         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
    1781            0 :           update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
    1782              : 
    1783              :       return;
    1784              :     }
    1785              : 
    1786            0 :   if (!REG_P (reg))
    1787              :     return;
    1788              : 
    1789              :   /* Global registers are always live, so the code below does not apply
    1790              :      to them.  */
    1791              : 
    1792            0 :   regno = REGNO (reg);
    1793              : 
    1794            0 :   if (! HARD_REGISTER_NUM_P (regno)
    1795            0 :       || !global_regs[regno])
    1796              :     {
    1797            0 :       for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
    1798              :         {
    1799            0 :           basic_block b = candidate_table[src].update_bbs.first_member[i];
    1800            0 :           bitmap_set_range (df_get_live_in (b), regno, REG_NREGS (reg));
    1801              :         }
    1802              :     }
    1803              : }
    1804              : 
    1805              : /* Return true if insn can be speculatively moved from block src to trg,
    1806              :    otherwise return false.  Called before first insertion of insn to
    1807              :    ready-list or before the scheduling.  */
    1808              : 
    1809              : static bool
    1810           35 : check_live (rtx_insn *insn, int src)
    1811              : {
    1812              :   /* Find the registers set by instruction.  */
    1813           35 :   if (GET_CODE (PATTERN (insn)) == SET
    1814           35 :       || GET_CODE (PATTERN (insn)) == CLOBBER)
    1815           19 :     return check_live_1 (src, PATTERN (insn));
    1816           16 :   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
    1817              :     {
    1818            0 :       int j;
    1819            0 :       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
    1820            0 :         if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
    1821            0 :              || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
    1822            0 :             && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
    1823              :           return false;
    1824              : 
    1825              :       return true;
    1826              :     }
    1827              : 
    1828              :   return true;
    1829              : }
    1830              : 
    1831              : /* Update the live registers info after insn was moved speculatively from
    1832              :    block src to trg.  */
    1833              : 
    1834              : static void
    1835            8 : update_live (rtx_insn *insn, int src)
    1836              : {
    1837              :   /* Find the registers set by instruction.  */
    1838            8 :   if (GET_CODE (PATTERN (insn)) == SET
    1839            8 :       || GET_CODE (PATTERN (insn)) == CLOBBER)
    1840            0 :     update_live_1 (src, PATTERN (insn));
    1841            8 :   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
    1842              :     {
    1843            0 :       int j;
    1844            0 :       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
    1845            0 :         if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
    1846            0 :             || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
    1847            0 :           update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
    1848              :     }
    1849            8 : }
    1850              : 
    1851              : /* True if block bb_to is equal to, or reachable from block bb_from.  */
    1852              : #define IS_REACHABLE(bb_from, bb_to)                                    \
    1853              :   (bb_from == bb_to                                                     \
    1854              :    || IS_RGN_ENTRY (bb_from)                                            \
    1855              :    || (bitmap_bit_p                                                     \
    1856              :        (ancestor_edges[bb_to],                                          \
    1857              :         EDGE_TO_BIT (single_pred_edge                                   \
    1858              :                      (BASIC_BLOCK_FOR_FN (cfun,                         \
    1859              :                                           BB_TO_BLOCK (bb_from)))))))
    1860              : 
    1861              : /* Turns on the fed_by_spec_load flag for insns fed by load_insn.  */
    1862              : 
    1863              : static void
    1864            0 : set_spec_fed (rtx_insn *load_insn)
    1865              : {
    1866            0 :   sd_iterator_def sd_it;
    1867            0 :   dep_t dep;
    1868              : 
    1869            0 :   FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
    1870            0 :     if (DEP_TYPE (dep) == REG_DEP_TRUE)
    1871            0 :       FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
    1872            0 : }
    1873              : 
    1874              : /* On the path from the insn to load_insn_bb, find a conditional
    1875              :    branch depending on insn, that guards the speculative load.  */
    1876              : 
    1877              : static bool
    1878            0 : find_conditional_protection (rtx_insn *insn, int load_insn_bb)
    1879              : {
    1880            0 :   sd_iterator_def sd_it;
    1881            0 :   dep_t dep;
    1882              : 
    1883              :   /* Iterate through DEF-USE forward dependences.  */
    1884            0 :   FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
    1885              :     {
    1886            0 :       rtx_insn *next = DEP_CON (dep);
    1887              : 
    1888            0 :       if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
    1889            0 :            CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
    1890            0 :           && IS_REACHABLE (INSN_BB (next), load_insn_bb)
    1891            0 :           && load_insn_bb != INSN_BB (next)
    1892            0 :           && DEP_TYPE (dep) == REG_DEP_TRUE
    1893            0 :           && (JUMP_P (next)
    1894            0 :               || find_conditional_protection (next, load_insn_bb)))
    1895              :         return true;
    1896              :     }
    1897              :   return false;
    1898              : }                               /* find_conditional_protection */
    1899              : 
    1900              : /* Returns true if the same insn1 that participates in the computation
    1901              :    of load_insn's address is feeding a conditional branch that is
    1902              :    guarding on load_insn. This is true if we find two DEF-USE
    1903              :    chains:
    1904              :    insn1 -> ... -> conditional-branch
    1905              :    insn1 -> ... -> load_insn,
    1906              :    and if a flow path exists:
    1907              :    insn1 -> ... -> conditional-branch -> ... -> load_insn,
    1908              :    and if insn1 is on the path
    1909              :    region-entry -> ... -> bb_trg -> ... load_insn.
    1910              : 
    1911              :    Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
    1912              :    Locate the branch by following INSN_FORW_DEPS from insn1.  */
    1913              : 
    1914              : static bool
    1915            0 : is_conditionally_protected (rtx_insn *load_insn, int bb_src, int bb_trg)
    1916              : {
    1917            0 :   sd_iterator_def sd_it;
    1918            0 :   dep_t dep;
    1919              : 
    1920            0 :   FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
    1921              :     {
    1922            0 :       rtx_insn *insn1 = DEP_PRO (dep);
    1923              : 
    1924              :       /* Must be a DEF-USE dependence upon non-branch.  */
    1925            0 :       if (DEP_TYPE (dep) != REG_DEP_TRUE
    1926            0 :           || JUMP_P (insn1))
    1927            0 :         continue;
    1928              : 
    1929              :       /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  */
    1930            0 :       if (INSN_BB (insn1) == bb_src
    1931            0 :           || (CONTAINING_RGN (BLOCK_NUM (insn1))
    1932            0 :               != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
    1933            0 :           || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
    1934            0 :               && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
    1935            0 :         continue;
    1936              : 
    1937              :       /* Now search for the conditional-branch.  */
    1938            0 :       if (find_conditional_protection (insn1, bb_src))
    1939              :         return true;
    1940              : 
    1941              :       /* Recursive step: search another insn1, "above" current insn1.  */
    1942            0 :       return is_conditionally_protected (insn1, bb_src, bb_trg);
    1943              :     }
    1944              : 
    1945              :   /* The chain does not exist.  */
    1946              :   return false;
    1947              : }                               /* is_conditionally_protected */
    1948              : 
    1949              : /* Returns true if a clue for "similar load" 'insn2' is found, and hence
    1950              :    load_insn can move speculatively from bb_src to bb_trg.  All the
    1951              :    following must hold:
    1952              : 
    1953              :    (1) both loads have 1 base register (PFREE_CANDIDATEs).
    1954              :    (2) load_insn and load1 have a def-use dependence upon
    1955              :    the same insn 'insn1'.
    1956              :    (3) either load2 is in bb_trg, or:
    1957              :    - there's only one split-block, and
    1958              :    - load1 is on the escape path, and
    1959              : 
    1960              :    From all these we can conclude that the two loads access memory
    1961              :    addresses that differ at most by a constant, and hence if moving
    1962              :    load_insn would cause an exception, it would have been caused by
    1963              :    load2 anyhow.  */
    1964              : 
    1965              : static bool
    1966            0 : is_pfree (rtx_insn *load_insn, int bb_src, int bb_trg)
    1967              : {
    1968            0 :   sd_iterator_def back_sd_it;
    1969            0 :   dep_t back_dep;
    1970            0 :   candidate *candp = candidate_table + bb_src;
    1971              : 
    1972            0 :   if (candp->split_bbs.nr_members != 1)
    1973              :     /* Must have exactly one escape block.  */
    1974              :     return false;
    1975              : 
    1976            0 :   FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
    1977              :     {
    1978            0 :       rtx_insn *insn1 = DEP_PRO (back_dep);
    1979              : 
    1980            0 :       if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
    1981              :         /* Found a DEF-USE dependence (insn1, load_insn).  */
    1982              :         {
    1983            0 :           sd_iterator_def fore_sd_it;
    1984            0 :           dep_t fore_dep;
    1985              : 
    1986            0 :           FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
    1987              :             {
    1988            0 :               rtx_insn *insn2 = DEP_CON (fore_dep);
    1989              : 
    1990            0 :               if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
    1991              :                 {
    1992              :                   /* Found a DEF-USE dependence (insn1, insn2).  */
    1993            0 :                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
    1994              :                     /* insn2 not guaranteed to be a 1 base reg load.  */
    1995            0 :                     continue;
    1996              : 
    1997            0 :                   if (INSN_BB (insn2) == bb_trg)
    1998              :                     /* insn2 is the similar load, in the target block.  */
    1999            0 :                     return true;
    2000              : 
    2001            0 :                   if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
    2002              :                     /* insn2 is a similar load, in a split-block.  */
    2003              :                     return true;
    2004              :                 }
    2005              :             }
    2006              :         }
    2007              :     }
    2008              : 
    2009              :   /* Couldn't find a similar load.  */
    2010              :   return false;
    2011              : }                               /* is_pfree */
    2012              : 
    2013              : /* Return true if load_insn is prisky (i.e. if load_insn is fed by
    2014              :    a load moved speculatively, or if load_insn is protected by
    2015              :    a compare on load_insn's address).  */
    2016              : 
    2017              : static bool
    2018            0 : is_prisky (rtx_insn *load_insn, int bb_src, int bb_trg)
    2019              : {
    2020            0 :   if (FED_BY_SPEC_LOAD (load_insn))
    2021              :     return true;
    2022              : 
    2023            0 :   if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
    2024              :     /* Dependence may 'hide' out of the region.  */
    2025              :     return true;
    2026              : 
    2027            0 :   if (is_conditionally_protected (load_insn, bb_src, bb_trg))
    2028              :     return true;
    2029              : 
    2030              :   return false;
    2031              : }
    2032              : 
    2033              : /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
    2034              :    Return true if insn is exception-free (and the motion is valid)
    2035              :    and false otherwise.  */
    2036              : 
    2037              : static bool
    2038           26 : is_exception_free (rtx_insn *insn, int bb_src, int bb_trg)
    2039              : {
    2040           26 :   int insn_class = haifa_classify_insn (insn);
    2041              : 
    2042              :   /* Handle non-load insns.  */
    2043           26 :   switch (insn_class)
    2044              :     {
    2045              :     case TRAP_FREE:
    2046              :       return true;
    2047              :     case TRAP_RISKY:
    2048              :       return false;
    2049            3 :     default:;
    2050              :     }
    2051              : 
    2052              :   /* Handle loads.  */
    2053            3 :   if (!flag_schedule_speculative_load)
    2054              :     return false;
    2055            0 :   IS_LOAD_INSN (insn) = 1;
    2056            0 :   switch (insn_class)
    2057              :     {
    2058              :     case IFREE:
    2059              :       return true;
    2060              :     case IRISKY:
    2061              :       return false;
    2062            0 :     case PFREE_CANDIDATE:
    2063            0 :       if (is_pfree (insn, bb_src, bb_trg))
    2064              :         return true;
    2065              :       /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  */
    2066              :       /* FALLTHRU */
    2067            0 :     case PRISKY_CANDIDATE:
    2068            0 :       if (!flag_schedule_speculative_load_dangerous
    2069            0 :           || is_prisky (insn, bb_src, bb_trg))
    2070              :         return false;
    2071              :       break;
    2072            0 :     default:;
    2073              :     }
    2074              : 
    2075            0 :   return flag_schedule_speculative_load_dangerous;
    2076              : }
    2077              : 
    2078              : /* The number of insns from the current block scheduled so far.  */
    2079              : static int sched_target_n_insns;
    2080              : /* The number of insns from the current block to be scheduled in total.  */
    2081              : static int target_n_insns;
    2082              : /* The number of insns from the entire region scheduled so far.  */
    2083              : static int sched_n_insns;
    2084              : 
    2085              : /* Implementations of the sched_info functions for region scheduling.  */
    2086              : static void init_ready_list (void);
    2087              : static bool can_schedule_ready_p (rtx_insn *);
    2088              : static void begin_schedule_ready (rtx_insn *);
    2089              : static ds_t new_ready (rtx_insn *, ds_t);
    2090              : static bool schedule_more_p (void);
    2091              : static const char *rgn_print_insn (const rtx_insn *, int);
    2092              : static int rgn_rank (rtx_insn *, rtx_insn *);
    2093              : static void compute_jump_reg_dependencies (rtx_insn *, regset);
    2094              : 
    2095              : /* Functions for speculative scheduling.  */
    2096              : static void rgn_add_remove_insn (rtx_insn *, int);
    2097              : static void rgn_add_block (basic_block, basic_block);
    2098              : static void rgn_fix_recovery_cfg (int, int, int);
    2099              : static basic_block advance_target_bb (basic_block, rtx_insn *);
    2100              : 
    2101              : /* Return true if there are more insns that should be scheduled.  */
    2102              : 
    2103              : static bool
    2104    114575395 : schedule_more_p (void)
    2105              : {
    2106    114575395 :   return sched_target_n_insns < target_n_insns;
    2107              : }
    2108              : 
    2109              : /* Add all insns that are initially ready to the ready list READY.  Called
    2110              :    once before scheduling a set of insns.  */
    2111              : 
    2112              : static void
    2113     10497928 : init_ready_list (void)
    2114              : {
    2115     10497928 :   rtx_insn *prev_head = current_sched_info->prev_head;
    2116     10497928 :   rtx_insn *next_tail = current_sched_info->next_tail;
    2117     10497928 :   int bb_src;
    2118     10497928 :   rtx_insn *insn;
    2119              : 
    2120     10497928 :   target_n_insns = 0;
    2121     10497928 :   sched_target_n_insns = 0;
    2122     10497928 :   sched_n_insns = 0;
    2123              : 
    2124              :   /* Print debugging information.  */
    2125     10497928 :   if (sched_verbose >= 5)
    2126            0 :     debug_rgn_dependencies (target_bb);
    2127              : 
    2128              :   /* Prepare current target block info.  */
    2129     10497928 :   if (current_nr_blocks > 1)
    2130           72 :     compute_trg_info (target_bb);
    2131              : 
    2132              :   /* Initialize ready list with all 'ready' insns in target block.
    2133              :      Count number of insns in the target block being scheduled.  */
    2134    134620577 :   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
    2135              :     {
    2136    113624721 :       gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
    2137    113624721 :       TODO_SPEC (insn) = HARD_DEP;
    2138    113624721 :       try_ready (insn);
    2139    113624721 :       target_n_insns++;
    2140              : 
    2141    113624721 :       gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
    2142              :     }
    2143              : 
    2144              :   /* Add to ready list all 'ready' insns in valid source blocks.
    2145              :      For speculative insns, check-live, exception-free, and
    2146              :      issue-delay.  */
    2147     10498010 :   for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
    2148           82 :     if (IS_VALID (bb_src))
    2149              :       {
    2150           51 :         rtx_insn *src_head;
    2151           51 :         rtx_insn *src_next_tail;
    2152           51 :         rtx_insn *tail, *head;
    2153              : 
    2154           51 :         get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
    2155              :                            &head, &tail);
    2156           51 :         src_next_tail = NEXT_INSN (tail);
    2157           51 :         src_head = head;
    2158              : 
    2159          712 :         for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
    2160          661 :           if (INSN_P (insn))
    2161              :             {
    2162          637 :               gcc_assert (TODO_SPEC (insn) == HARD_DEP || TODO_SPEC (insn) == DEP_POSTPONED);
    2163          637 :               TODO_SPEC (insn) = HARD_DEP;
    2164          637 :               try_ready (insn);
    2165              :             }
    2166              :       }
    2167     10497928 : }
    2168              : 
    2169              : /* Called after taking INSN from the ready list.  Returns true if this
    2170              :    insn can be scheduled, nonzero if we should silently discard it.  */
    2171              : 
    2172              : static bool
    2173     61628620 : can_schedule_ready_p (rtx_insn *insn)
    2174              : {
    2175              :   /* An interblock motion?  */
    2176     61628620 :   if (INSN_BB (insn) != target_bb && IS_SPECULATIVE_INSN (insn))
    2177              :     {
    2178              :       /* Cannot schedule this insn unless all operands are live.  */
    2179            0 :       if (!check_live (insn, INSN_BB (insn)))
    2180              :         return false;
    2181              : 
    2182              :       /* Should not move expensive instructions speculatively.  */
    2183            0 :       if (GET_CODE (PATTERN (insn)) != CLOBBER
    2184            0 :           && !targetm.sched.can_speculate_insn (insn))
    2185              :         return false;
    2186              :     }
    2187              : 
    2188              :   return true;
    2189              : }
    2190              : 
    2191              : /* Updates counter and other information.  Split from can_schedule_ready_p ()
    2192              :    because when we schedule insn speculatively then insn passed to
    2193              :    can_schedule_ready_p () differs from the one passed to
    2194              :    begin_schedule_ready ().  */
    2195              : static void
    2196    113624729 : begin_schedule_ready (rtx_insn *insn)
    2197              : {
    2198              :   /* An interblock motion?  */
    2199    113624729 :   if (INSN_BB (insn) != target_bb)
    2200              :     {
    2201            8 :       if (IS_SPECULATIVE_INSN (insn))
    2202              :         {
    2203            8 :           gcc_assert (check_live (insn, INSN_BB (insn)));
    2204              : 
    2205            8 :           update_live (insn, INSN_BB (insn));
    2206              : 
    2207              :           /* For speculative load, mark insns fed by it.  */
    2208            8 :           if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
    2209            0 :             set_spec_fed (insn);
    2210              : 
    2211            8 :           nr_spec++;
    2212              :         }
    2213            8 :       nr_inter++;
    2214              :     }
    2215              :   else
    2216              :     {
    2217              :       /* In block motion.  */
    2218    113624721 :       sched_target_n_insns++;
    2219              :     }
    2220    113624729 :   sched_n_insns++;
    2221    113624729 : }
    2222              : 
    2223              : /* Called after INSN has all its hard dependencies resolved and the speculation
    2224              :    of type TS is enough to overcome them all.
    2225              :    Return nonzero if it should be moved to the ready list or the queue, or zero
    2226              :    if we should silently discard it.  */
    2227              : static ds_t
    2228    113624777 : new_ready (rtx_insn *next, ds_t ts)
    2229              : {
    2230    113624777 :   if (INSN_BB (next) != target_bb)
    2231              :     {
    2232           56 :       int not_ex_free = 0;
    2233              : 
    2234              :       /* For speculative insns, before inserting to ready/queue,
    2235              :          check live, exception-free, and issue-delay.  */
    2236           56 :       if (!IS_VALID (INSN_BB (next))
    2237           40 :           || CANT_MOVE (next)
    2238          110 :           || (IS_SPECULATIVE_INSN (next)
    2239           27 :               && ((recog_memoized (next) >= 0
    2240           19 :                    && min_insn_conflict_delay (curr_state, next, next)
    2241           19 :                    > param_max_sched_insn_conflict_delay)
    2242           27 :                   || IS_SPECULATION_CHECK_P (next)
    2243           27 :                   || !check_live (next, INSN_BB (next))
    2244           26 :                   || (not_ex_free = !is_exception_free (next, INSN_BB (next),
    2245              :                                                         target_bb)))))
    2246              :         {
    2247           36 :           if (not_ex_free
    2248              :               /* We are here because is_exception_free () == false.
    2249              :                  But we possibly can handle that with control speculation.  */
    2250            6 :               && sched_deps_info->generate_spec_deps
    2251            0 :               && spec_info->mask & BEGIN_CONTROL)
    2252              :             {
    2253            0 :               ds_t new_ds;
    2254              : 
    2255              :               /* Add control speculation to NEXT's dependency type.  */
    2256            0 :               new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
    2257              : 
    2258              :               /* Check if NEXT can be speculated with new dependency type.  */
    2259            0 :               if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
    2260              :                 /* Here we got new control-speculative instruction.  */
    2261              :                 ts = new_ds;
    2262              :               else
    2263              :                 /* NEXT isn't ready yet.  */
    2264           36 :                 ts = DEP_POSTPONED;
    2265              :             }
    2266              :           else
    2267              :             /* NEXT isn't ready yet.  */
    2268              :             ts = DEP_POSTPONED;
    2269              :         }
    2270              :     }
    2271              : 
    2272    113624777 :   return ts;
    2273              : }
    2274              : 
    2275              : /* Return a string that contains the insn uid and optionally anything else
    2276              :    necessary to identify this insn in an output.  It's valid to use a
    2277              :    static buffer for this.  The ALIGNED parameter should cause the string
    2278              :    to be formatted so that multiple output lines will line up nicely.  */
    2279              : 
    2280              : static const char *
    2281          987 : rgn_print_insn (const rtx_insn *insn, int aligned)
    2282              : {
    2283          987 :   static char tmp[80];
    2284              : 
    2285          987 :   if (aligned)
    2286          987 :     sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
    2287              :   else
    2288              :     {
    2289            0 :       if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
    2290            0 :         sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
    2291              :       else
    2292            0 :         sprintf (tmp, "%d", INSN_UID (insn));
    2293              :     }
    2294          987 :   return tmp;
    2295              : }
    2296              : 
    2297              : /* Compare priority of two insns.  Return a positive number if the second
    2298              :    insn is to be preferred for scheduling, and a negative one if the first
    2299              :    is to be preferred.  Zero if they are equally good.  */
    2300              : 
    2301              : static int
    2302    252224813 : rgn_rank (rtx_insn *insn1, rtx_insn *insn2)
    2303              : {
    2304              :   /* Some comparison make sense in interblock scheduling only.  */
    2305    252224813 :   if (INSN_BB (insn1) != INSN_BB (insn2))
    2306              :     {
    2307            0 :       int spec_val, prob_val;
    2308              : 
    2309              :       /* Prefer an inblock motion on an interblock motion.  */
    2310            0 :       if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
    2311              :         return 1;
    2312            0 :       if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
    2313              :         return -1;
    2314              : 
    2315              :       /* Prefer a useful motion on a speculative one.  */
    2316            0 :       spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
    2317            0 :       if (spec_val)
    2318              :         return spec_val;
    2319              : 
    2320              :       /* Prefer a more probable (speculative) insn.  */
    2321            0 :       prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
    2322            0 :       if (prob_val)
    2323              :         return prob_val;
    2324              :     }
    2325              :   return 0;
    2326              : }
    2327              : 
    2328              : /* NEXT is an instruction that depends on INSN (a backward dependence);
    2329              :    return true if we should include this dependence in priority
    2330              :    calculations.  */
    2331              : 
    2332              : bool
    2333    147146164 : contributes_to_priority (rtx_insn *next, rtx_insn *insn)
    2334              : {
    2335              :   /* NEXT and INSN reside in one ebb.  */
    2336    147146164 :   return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
    2337              : }
    2338              : 
    2339              : /* INSN is a JUMP_INSN.  Store the set of registers that must be
    2340              :    considered as used by this jump in USED.  */
    2341              : 
    2342              : static void
    2343      4891438 : compute_jump_reg_dependencies (rtx_insn *insn ATTRIBUTE_UNUSED,
    2344              :                                regset used ATTRIBUTE_UNUSED)
    2345              : {
    2346              :   /* Nothing to do here, since we postprocess jumps in
    2347              :      add_branch_dependences.  */
    2348      4891438 : }
    2349              : 
    2350              : /* This variable holds common_sched_info hooks and data relevant to
    2351              :    the interblock scheduler.  */
    2352              : static struct common_sched_info_def rgn_common_sched_info;
    2353              : 
    2354              : 
    2355              : /* This holds data for the dependence analysis relevant to
    2356              :    the interblock scheduler.  */
    2357              : static struct sched_deps_info_def rgn_sched_deps_info;
    2358              : 
    2359              : /* This holds constant data used for initializing the above structure
    2360              :    for the Haifa scheduler.  */
    2361              : static const struct sched_deps_info_def rgn_const_sched_deps_info =
    2362              :   {
    2363              :     compute_jump_reg_dependencies,
    2364              :     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    2365              :     0, 0, 0
    2366              :   };
    2367              : 
    2368              : /* Same as above, but for the selective scheduler.  */
    2369              : static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
    2370              :   {
    2371              :     compute_jump_reg_dependencies,
    2372              :     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    2373              :     0, 0, 0
    2374              :   };
    2375              : 
    2376              : /* Return true if scheduling INSN will trigger finish of scheduling
    2377              :    current block.  */
    2378              : static bool
    2379    115386557 : rgn_insn_finishes_block_p (rtx_insn *insn)
    2380              : {
    2381    115386557 :   if (INSN_BB (insn) == target_bb
    2382    115386557 :       && sched_target_n_insns + 1 == target_n_insns)
    2383              :     /* INSN is the last not-scheduled instruction in the current block.  */
    2384      5975716 :     return true;
    2385              : 
    2386              :   return false;
    2387              : }
    2388              : 
    2389              : /* Used in schedule_insns to initialize current_sched_info for scheduling
    2390              :    regions (or single basic blocks).  */
    2391              : 
    2392              : static const struct haifa_sched_info rgn_const_sched_info =
    2393              : {
    2394              :   init_ready_list,
    2395              :   can_schedule_ready_p,
    2396              :   schedule_more_p,
    2397              :   new_ready,
    2398              :   rgn_rank,
    2399              :   rgn_print_insn,
    2400              :   contributes_to_priority,
    2401              :   rgn_insn_finishes_block_p,
    2402              : 
    2403              :   NULL, NULL,
    2404              :   NULL, NULL,
    2405              :   0, 0,
    2406              : 
    2407              :   rgn_add_remove_insn,
    2408              :   begin_schedule_ready,
    2409              :   NULL,
    2410              :   advance_target_bb,
    2411              :   NULL, NULL,
    2412              :   SCHED_RGN
    2413              : };
    2414              : 
    2415              : /* This variable holds the data and hooks needed to the Haifa scheduler backend
    2416              :    for the interblock scheduler frontend.  */
    2417              : static struct haifa_sched_info rgn_sched_info;
    2418              : 
    2419              : /* Returns maximum priority that an insn was assigned to.  */
    2420              : 
    2421              : int
    2422          849 : get_rgn_sched_max_insns_priority (void)
    2423              : {
    2424          849 :   return rgn_sched_info.sched_max_insns_priority;
    2425              : }
    2426              : 
    2427              : /* Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register.  */
    2428              : 
    2429              : static bool
    2430         1757 : sets_likely_spilled (rtx pat)
    2431              : {
    2432         1757 :   bool ret = false;
    2433            0 :   note_pattern_stores (pat, sets_likely_spilled_1, &ret);
    2434         1757 :   return ret;
    2435              : }
    2436              : 
    2437              : static void
    2438         2090 : sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
    2439              : {
    2440         2090 :   bool *ret = (bool *) data;
    2441              : 
    2442         2090 :   if (GET_CODE (pat) == SET
    2443         1862 :       && REG_P (x)
    2444         1711 :       && HARD_REGISTER_P (x)
    2445         3114 :       && targetm.class_likely_spilled_p (REGNO_REG_CLASS (REGNO (x))))
    2446          342 :     *ret = true;
    2447         2090 : }
    2448              : 
    2449              : /* A bitmap to note insns that participate in any dependency.  Used in
    2450              :    add_branch_dependences.  */
    2451              : static sbitmap insn_referenced;
    2452              : 
    2453              : /* Add dependences so that branches are scheduled to run last in their
    2454              :    block.  */
    2455              : static void
    2456     10517854 : add_branch_dependences (rtx_insn *head, rtx_insn *tail)
    2457              : {
    2458     10517854 :   rtx_insn *insn, *last;
    2459              : 
    2460              :   /* For all branches, calls, uses, clobbers, and instructions
    2461              :      that can throw exceptions, force them to remain in order at the end of
    2462              :      the block by adding dependencies and giving the last a high priority.
    2463              :      There may be notes present, and prev_head may also be a note.
    2464              : 
    2465              :      Branches must obviously remain at the end.  Calls should remain at the
    2466              :      end since moving them results in worse register allocation.  Uses remain
    2467              :      at the end to ensure proper register allocation.
    2468              : 
    2469              :      Predecessors of SCHED_GROUP_P instructions at the end remain at the end.
    2470              : 
    2471              :      COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
    2472              : 
    2473              :      Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
    2474              :      values) are not moved before reload because we can wind up with register
    2475              :      allocation failures.  */
    2476              : 
    2477     12186989 :   while (tail != head && DEBUG_INSN_P (tail))
    2478      1669135 :     tail = PREV_INSN (tail);
    2479              : 
    2480              :   insn = tail;
    2481              :   last = 0;
    2482     24472688 :   while (CALL_P (insn)
    2483     24472688 :          || JUMP_P (insn) || JUMP_TABLE_DATA_P (insn)
    2484     14785679 :          || (NONJUMP_INSN_P (insn)
    2485     13129824 :              && (GET_CODE (PATTERN (insn)) == USE
    2486     12838235 :                  || GET_CODE (PATTERN (insn)) == CLOBBER
    2487     12835927 :                  || can_throw_internal (insn)
    2488     12728548 :                  || (!reload_completed
    2489         1757 :                      && sets_likely_spilled (PATTERN (insn)))))
    2490     14384061 :          || NOTE_P (insn)
    2491     37639488 :          || (last != 0 && SCHED_GROUP_P (last)))
    2492              :     {
    2493     15515838 :       if (!NOTE_P (insn))
    2494              :         {
    2495     14298577 :           if (last != 0
    2496     14298577 :               && sd_find_dep_between (insn, last, false) == NULL)
    2497              :             {
    2498        20085 :               if (! sched_insns_conditions_mutex_p (last, insn))
    2499        20085 :                 add_dependence (last, insn, REG_DEP_ANTI);
    2500        20085 :               bitmap_set_bit (insn_referenced, INSN_LUID (insn));
    2501              :             }
    2502              : 
    2503     14298577 :           CANT_MOVE (insn) = 1;
    2504              : 
    2505     14298577 :           last = insn;
    2506              :         }
    2507              : 
    2508              :       /* Don't overrun the bounds of the basic block.  */
    2509     15515838 :       if (insn == head)
    2510              :         break;
    2511              : 
    2512     22685899 :       do
    2513     22685899 :         insn = PREV_INSN (insn);
    2514     22685899 :       while (insn != head && DEBUG_INSN_P (insn));
    2515              :     }
    2516              : 
    2517              :   /* Selective scheduling handles control dependencies by itself, and
    2518              :      CANT_MOVE flags ensure that other insns will be kept in place.  */
    2519     10517854 :   if (sel_sched_p ())
    2520              :     return;
    2521              : 
    2522              :   /* Make sure these insns are scheduled last in their block.  */
    2523     10516849 :   insn = last;
    2524     10516849 :   if (insn != 0)
    2525     95490245 :     while (insn != head)
    2526              :       {
    2527     86320873 :         insn = prev_nonnote_insn (insn);
    2528              : 
    2529     86320873 :         if (bitmap_bit_p (insn_referenced, INSN_LUID (insn))
    2530     86320873 :             || DEBUG_INSN_P (insn))
    2531     45256277 :           continue;
    2532              : 
    2533     41064596 :         if (! sched_insns_conditions_mutex_p (last, insn))
    2534     41064596 :           add_dependence (last, insn, REG_DEP_ANTI);
    2535              :       }
    2536              : 
    2537     10516849 :   if (!targetm.have_conditional_execution ())
    2538              :     return;
    2539              : 
    2540              :   /* Finally, if the block ends in a jump, and we are doing intra-block
    2541              :      scheduling, make sure that the branch depends on any COND_EXEC insns
    2542              :      inside the block to avoid moving the COND_EXECs past the branch insn.
    2543              : 
    2544              :      We only have to do this after reload, because (1) before reload there
    2545              :      are no COND_EXEC insns, and (2) the region scheduler is an intra-block
    2546              :      scheduler after reload.
    2547              : 
    2548              :      FIXME: We could in some cases move COND_EXEC insns past the branch if
    2549              :      this scheduler would be a little smarter.  Consider this code:
    2550              : 
    2551              :                 T = [addr]
    2552              :         C  ?    addr += 4
    2553              :         !C ?    X += 12
    2554              :         C  ?    T += 1
    2555              :         C  ?    jump foo
    2556              : 
    2557              :      On a target with a one cycle stall on a memory access the optimal
    2558              :      sequence would be:
    2559              : 
    2560              :                 T = [addr]
    2561              :         C  ?    addr += 4
    2562              :         C  ?    T += 1
    2563              :         C  ?    jump foo
    2564              :         !C ?    X += 12
    2565              : 
    2566              :      We don't want to put the 'X += 12' before the branch because it just
    2567              :      wastes a cycle of execution time when the branch is taken.
    2568              : 
    2569              :      Note that in the example "!C" will always be true.  That is another
    2570              :      possible improvement for handling COND_EXECs in this scheduler: it
    2571              :      could remove always-true predicates.  */
    2572              : 
    2573            0 :   if (!reload_completed || ! (JUMP_P (tail) || JUMP_TABLE_DATA_P (tail)))
    2574              :     return;
    2575              : 
    2576              :   insn = tail;
    2577            0 :   while (insn != head)
    2578              :     {
    2579            0 :       insn = PREV_INSN (insn);
    2580              : 
    2581              :       /* Note that we want to add this dependency even when
    2582              :          sched_insns_conditions_mutex_p returns true.  The whole point
    2583              :          is that we _want_ this dependency, even if these insns really
    2584              :          are independent.  */
    2585            0 :       if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
    2586            0 :         add_dependence (tail, insn, REG_DEP_ANTI);
    2587              :     }
    2588              : }
    2589              : 
    2590              : /* Data structures for the computation of data dependences in a regions.  We
    2591              :    keep one `deps' structure for every basic block.  Before analyzing the
    2592              :    data dependences for a bb, its variables are initialized as a function of
    2593              :    the variables of its predecessors.  When the analysis for a bb completes,
    2594              :    we save the contents to the corresponding bb_deps[bb] variable.  */
    2595              : 
    2596              : static class deps_desc *bb_deps;
    2597              : 
    2598              : static void
    2599         1142 : concat_insn_mem_list (rtx_insn_list *copy_insns,
    2600              :                       rtx_expr_list *copy_mems,
    2601              :                       rtx_insn_list **old_insns_p,
    2602              :                       rtx_expr_list **old_mems_p)
    2603              : {
    2604         1142 :   rtx_insn_list *new_insns = *old_insns_p;
    2605         1142 :   rtx_expr_list *new_mems = *old_mems_p;
    2606              : 
    2607         2116 :   while (copy_insns)
    2608              :     {
    2609          974 :       new_insns = alloc_INSN_LIST (copy_insns->insn (), new_insns);
    2610          974 :       new_mems = alloc_EXPR_LIST (VOIDmode, copy_mems->element (), new_mems);
    2611          974 :       copy_insns = copy_insns->next ();
    2612          974 :       copy_mems = copy_mems->next ();
    2613              :     }
    2614              : 
    2615         1142 :   *old_insns_p = new_insns;
    2616         1142 :   *old_mems_p = new_mems;
    2617         1142 : }
    2618              : 
    2619              : /* Join PRED_DEPS to the SUCC_DEPS.  */
    2620              : void
    2621          571 : deps_join (class deps_desc *succ_deps, class deps_desc *pred_deps)
    2622              : {
    2623          571 :   unsigned reg;
    2624          571 :   reg_set_iterator rsi;
    2625              : 
    2626              :   /* Registers that PRED has not materialised carry PRED's pending barriers as
    2627              :      their sets list, so fold those into the ones SUCC has materialised before
    2628              :      the main loop, and into SUCC's own pending list afterwards.  */
    2629          571 :   if (pred_deps->pending_barriers)
    2630           43 :     EXECUTE_IF_AND_COMPL_IN_REG_SET (&succ_deps->reg_last_in_use,
    2631              :                                      &pred_deps->reg_last_in_use,
    2632              :                                      0, reg, rsi)
    2633              :       {
    2634            4 :         struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
    2635            4 :         succ_rl->sets = concat_INSN_LIST (pred_deps->pending_barriers,
    2636              :                                           succ_rl->sets);
    2637              :       }
    2638              : 
    2639              :   /* The reg_last lists are inherited by successor.  */
    2640        20730 :   EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
    2641              :     {
    2642        20159 :       struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
    2643        20159 :       struct deps_reg *succ_rl = deps_reg_last (succ_deps, reg);
    2644              : 
    2645        20159 :       succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
    2646        20159 :       succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
    2647        20159 :       succ_rl->implicit_sets
    2648        20159 :         = concat_INSN_LIST (pred_rl->implicit_sets, succ_rl->implicit_sets);
    2649        20159 :       succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
    2650              :                                             succ_rl->clobbers);
    2651        20159 :       succ_rl->uses_length += pred_rl->uses_length;
    2652        20159 :       succ_rl->clobbers_length += pred_rl->clobbers_length;
    2653              :     }
    2654          571 :   IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
    2655              : 
    2656              :   /* Registers neither side has materialised keep both pending lists.  */
    2657          571 :   succ_deps->pending_barriers
    2658          571 :     = concat_INSN_LIST (pred_deps->pending_barriers,
    2659              :                         succ_deps->pending_barriers);
    2660              : 
    2661              :   /* Mem read/write lists are inherited by successor.  */
    2662          571 :   concat_insn_mem_list (pred_deps->pending_read_insns,
    2663              :                         pred_deps->pending_read_mems,
    2664              :                         &succ_deps->pending_read_insns,
    2665              :                         &succ_deps->pending_read_mems);
    2666          571 :   concat_insn_mem_list (pred_deps->pending_write_insns,
    2667              :                         pred_deps->pending_write_mems,
    2668              :                         &succ_deps->pending_write_insns,
    2669              :                         &succ_deps->pending_write_mems);
    2670              : 
    2671          571 :   succ_deps->pending_jump_insns
    2672          571 :     = concat_INSN_LIST (pred_deps->pending_jump_insns,
    2673              :                         succ_deps->pending_jump_insns);
    2674          571 :   succ_deps->last_pending_memory_flush
    2675          571 :     = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
    2676              :                         succ_deps->last_pending_memory_flush);
    2677              : 
    2678          571 :   succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
    2679          571 :   succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
    2680          571 :   succ_deps->pending_flush_length += pred_deps->pending_flush_length;
    2681              : 
    2682              :   /* last_function_call is inherited by successor.  */
    2683          571 :   succ_deps->last_function_call
    2684          571 :     = concat_INSN_LIST (pred_deps->last_function_call,
    2685              :                         succ_deps->last_function_call);
    2686              : 
    2687              :   /* last_function_call_may_noreturn is inherited by successor.  */
    2688          571 :   succ_deps->last_function_call_may_noreturn
    2689          571 :     = concat_INSN_LIST (pred_deps->last_function_call_may_noreturn,
    2690              :                         succ_deps->last_function_call_may_noreturn);
    2691              : 
    2692              :   /* sched_before_next_call is inherited by successor.  */
    2693          571 :   succ_deps->sched_before_next_call
    2694          571 :     = concat_INSN_LIST (pred_deps->sched_before_next_call,
    2695              :                         succ_deps->sched_before_next_call);
    2696          571 : }
    2697              : 
    2698              : /* After computing the dependencies for block BB, propagate the dependencies
    2699              :    found in TMP_DEPS to the successors of the block.  */
    2700              : static void
    2701          444 : propagate_deps (int bb, class deps_desc *pred_deps)
    2702              : {
    2703          444 :   basic_block block = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (bb));
    2704          444 :   edge_iterator ei;
    2705          444 :   edge e;
    2706              : 
    2707              :   /* bb's structures are inherited by its successors.  */
    2708         1200 :   FOR_EACH_EDGE (e, ei, block->succs)
    2709              :     {
    2710              :       /* Only bbs "below" bb, in the same region, are interesting.  */
    2711          756 :       if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
    2712          754 :           || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
    2713          499 :           || BLOCK_TO_BB (e->dest->index) <= bb)
    2714          355 :         continue;
    2715              : 
    2716          401 :       deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
    2717              :     }
    2718              : 
    2719              :   /* These lists should point to the right place, for correct
    2720              :      freeing later.  */
    2721          444 :   bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
    2722          444 :   bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
    2723          444 :   bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
    2724          444 :   bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
    2725          444 :   bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
    2726              : 
    2727              :   /* Can't allow these to be freed twice.  */
    2728          444 :   pred_deps->pending_read_insns = 0;
    2729          444 :   pred_deps->pending_read_mems = 0;
    2730          444 :   pred_deps->pending_write_insns = 0;
    2731          444 :   pred_deps->pending_write_mems = 0;
    2732          444 :   pred_deps->pending_jump_insns = 0;
    2733          444 : }
    2734              : 
    2735              : /* Compute dependences inside bb.  In a multiple blocks region:
    2736              :    (1) a bb is analyzed after its predecessors, and (2) the lists in
    2737              :    effect at the end of bb (after analyzing for bb) are inherited by
    2738              :    bb's successors.
    2739              : 
    2740              :    Specifically for reg-reg data dependences, the block insns are
    2741              :    scanned by sched_analyze () top-to-bottom.  Three lists are
    2742              :    maintained by sched_analyze (): reg_last[].sets for register DEFs,
    2743              :    reg_last[].implicit_sets for implicit hard register DEFs, and
    2744              :    reg_last[].uses for register USEs.
    2745              : 
    2746              :    When analysis is completed for bb, we update for its successors:
    2747              :    ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
    2748              :    ;  - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
    2749              :    ;  - USES[succ] = Union (USES [succ], DEFS [bb])
    2750              : 
    2751              :    The mechanism for computing mem-mem data dependence is very
    2752              :    similar, and the result is interblock dependences in the region.  */
    2753              : 
    2754              : static void
    2755     10517854 : compute_block_dependences (int bb)
    2756              : {
    2757     10517854 :   rtx_insn *head, *tail;
    2758     10517854 :   class deps_desc tmp_deps;
    2759              : 
    2760     10517854 :   tmp_deps = bb_deps[bb];
    2761              : 
    2762              :   /* Do the analysis for this block.  */
    2763     10517854 :   gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
    2764     10517854 :   get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
    2765              : 
    2766     10517854 :   sched_analyze (&tmp_deps, head, tail);
    2767              : 
    2768     10517854 :   add_branch_dependences (head, tail);
    2769              : 
    2770     10517854 :   if (current_nr_blocks > 1)
    2771          444 :     propagate_deps (bb, &tmp_deps);
    2772              : 
    2773              :   /* Free up the INSN_LISTs.  */
    2774     10517854 :   free_deps (&tmp_deps);
    2775              : 
    2776     10517854 :   if (targetm.sched.dependencies_evaluation_hook)
    2777     10517854 :     targetm.sched.dependencies_evaluation_hook (head, tail);
    2778     10517854 : }
    2779              : 
    2780              : /* Free dependencies of instructions inside BB.  */
    2781              : static void
    2782     10516849 : free_block_dependencies (int bb)
    2783              : {
    2784     10516849 :   rtx_insn *head;
    2785     10516849 :   rtx_insn *tail;
    2786              : 
    2787     10516849 :   get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
    2788              : 
    2789     10516849 :   if (no_real_insns_p (head, tail))
    2790              :     return;
    2791              : 
    2792     10497928 :   sched_free_deps (head, tail, true);
    2793              : }
    2794              : 
    2795              : /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
    2796              :    them to the unused_*_list variables, so that they can be reused.  */
    2797              : 
    2798              : static void
    2799     10517518 : free_pending_lists (void)
    2800              : {
    2801     10517518 :   int bb;
    2802              : 
    2803     21035372 :   for (bb = 0; bb < current_nr_blocks; bb++)
    2804              :     {
    2805     10517854 :       free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
    2806     10517854 :       free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
    2807     10517854 :       free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
    2808     10517854 :       free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
    2809     10517854 :       free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
    2810              :     }
    2811     10517518 : }
    2812              : 
    2813              : /* Print dependences for debugging starting from FROM_BB.
    2814              :    Callable from debugger.  */
    2815              : /* Print dependences for debugging starting from FROM_BB.
    2816              :    Callable from debugger.  */
    2817              : DEBUG_FUNCTION void
    2818            0 : debug_rgn_dependencies (int from_bb)
    2819              : {
    2820            0 :   int bb;
    2821              : 
    2822            0 :   fprintf (sched_dump,
    2823              :            ";;   --------------- forward dependences: ------------ \n");
    2824              : 
    2825            0 :   for (bb = from_bb; bb < current_nr_blocks; bb++)
    2826              :     {
    2827            0 :       rtx_insn *head, *tail;
    2828              : 
    2829            0 :       get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
    2830            0 :       fprintf (sched_dump, "\n;;   --- Region Dependences --- b %d bb %d \n",
    2831            0 :                BB_TO_BLOCK (bb), bb);
    2832              : 
    2833            0 :       debug_dependencies (head, tail);
    2834              :     }
    2835            0 : }
    2836              : 
    2837              : /* Print dependencies information for instructions between HEAD and TAIL.
    2838              :    ??? This function would probably fit best in haifa-sched.cc.  */
    2839            0 : void debug_dependencies (rtx_insn *head, rtx_insn *tail)
    2840              : {
    2841            0 :   rtx_insn *insn;
    2842            0 :   rtx_insn *next_tail = NEXT_INSN (tail);
    2843              : 
    2844            0 :   fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
    2845              :            "insn", "code", "bb", "dep", "prio", "cost",
    2846              :            "reservation");
    2847            0 :   fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
    2848              :            "----", "----", "--", "---", "----", "----",
    2849              :            "-----------");
    2850              : 
    2851            0 :   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
    2852              :     {
    2853            0 :       if (! INSN_P (insn))
    2854              :         {
    2855            0 :           int n;
    2856            0 :           fprintf (sched_dump, ";;   %6d ", INSN_UID (insn));
    2857            0 :           if (NOTE_P (insn))
    2858              :             {
    2859            0 :               n = NOTE_KIND (insn);
    2860            0 :               fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
    2861              :             }
    2862              :           else
    2863            0 :             fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
    2864            0 :           continue;
    2865            0 :         }
    2866              : 
    2867            0 :       fprintf (sched_dump,
    2868              :                ";;   %s%5d%6d%6d%6d%6d%6d   ",
    2869            0 :                (SCHED_GROUP_P (insn) ? "+" : " "),
    2870            0 :                INSN_UID (insn),
    2871              :                INSN_CODE (insn),
    2872            0 :                BLOCK_NUM (insn),
    2873            0 :                sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
    2874            0 :                (sel_sched_p () ? (sched_emulate_haifa_p ? -1
    2875            0 :                                : INSN_PRIORITY (insn))
    2876            0 :                 : INSN_PRIORITY (insn)),
    2877            0 :                (sel_sched_p () ? (sched_emulate_haifa_p ? -1
    2878            0 :                                : insn_sched_cost (insn))
    2879            0 :                 : insn_sched_cost (insn)));
    2880              : 
    2881            0 :       if (recog_memoized (insn) < 0)
    2882            0 :         fprintf (sched_dump, "nothing");
    2883              :       else
    2884            0 :         print_reservation (sched_dump, insn);
    2885              : 
    2886            0 :       fprintf (sched_dump, "\t: FW:");
    2887            0 :       {
    2888            0 :         sd_iterator_def sd_it;
    2889            0 :         dep_t dep;
    2890              : 
    2891            0 :         FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
    2892            0 :           fprintf (sched_dump, " %d%s%s%s", INSN_UID (DEP_CON (dep)),
    2893            0 :                    DEP_TYPE (dep) == REG_DEP_TRUE ? "t" : "",
    2894            0 :                    DEP_NONREG (dep) ? "n" : "",
    2895            0 :                    DEP_MULTIPLE (dep) ? "m" : "");
    2896            0 :         if (sched_verbose >= 5)
    2897              :           {
    2898            0 :             fprintf (sched_dump, "\n;;\t\t\t\t\t\t: BK:");
    2899            0 :             FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
    2900            0 :               fprintf (sched_dump, " %d%s%s%s", INSN_UID (DEP_PRO (dep)),
    2901            0 :                        DEP_TYPE (dep) == REG_DEP_TRUE ? "t" : "",
    2902            0 :                        DEP_NONREG (dep) ? "n" : "",
    2903            0 :                        DEP_MULTIPLE (dep) ? "m" : "");
    2904              :           }
    2905              :       }
    2906            0 :       fprintf (sched_dump, "\n");
    2907              :     }
    2908              : 
    2909            0 :   fprintf (sched_dump, "\n");
    2910            0 : }
    2911              : 
    2912              : /* Dump dependency graph for the current region to a file using dot syntax.  */
    2913              : 
    2914              : void
    2915            0 : dump_rgn_dependencies_dot (FILE *file)
    2916              : {
    2917            0 :   rtx_insn *head, *tail, *con, *pro;
    2918            0 :   sd_iterator_def sd_it;
    2919            0 :   dep_t dep;
    2920            0 :   int bb;
    2921            0 :   pretty_printer pp;
    2922              : 
    2923            0 :   pp.set_output_stream (file);
    2924            0 :   pp_printf (&pp, "digraph SchedDG {\n");
    2925              : 
    2926            0 :   for (bb = 0; bb < current_nr_blocks; ++bb)
    2927              :     {
    2928              :       /* Begin subgraph (basic block).  */
    2929            0 :       pp_printf (&pp, "subgraph cluster_block_%d {\n", bb);
    2930            0 :       pp_printf (&pp, "\t" "color=blue;" "\n");
    2931            0 :       pp_printf (&pp, "\t" "style=bold;" "\n");
    2932            0 :       pp_printf (&pp, "\t" "label=\"BB #%d\";\n", BB_TO_BLOCK (bb));
    2933              : 
    2934              :       /* Setup head and tail (no support for EBBs).  */
    2935            0 :       gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
    2936            0 :       get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
    2937            0 :       tail = NEXT_INSN (tail);
    2938              : 
    2939              :       /* Dump all insns.  */
    2940            0 :       for (con = head; con != tail; con = NEXT_INSN (con))
    2941              :         {
    2942            0 :           if (!INSN_P (con))
    2943            0 :             continue;
    2944              : 
    2945              :           /* Pretty print the insn.  */
    2946            0 :           pp_printf (&pp, "\t%d [label=\"{", INSN_UID (con));
    2947            0 :           pp_write_text_to_stream (&pp);
    2948            0 :           print_insn (&pp, con, /*verbose=*/false);
    2949            0 :           pp_write_text_as_dot_label_to_stream (&pp, /*for_record=*/true);
    2950            0 :           pp_write_text_to_stream (&pp);
    2951              : 
    2952              :           /* Dump instruction attributes.  */
    2953            0 :           pp_printf (&pp, "|{ uid:%d | luid:%d | prio:%d }}\",shape=record]\n",
    2954            0 :                      INSN_UID (con), INSN_LUID (con), INSN_PRIORITY (con));
    2955              : 
    2956              :           /* Dump all deps.  */
    2957            0 :           FOR_EACH_DEP (con, SD_LIST_BACK, sd_it, dep)
    2958              :             {
    2959            0 :               int weight = 0;
    2960            0 :               const char *color;
    2961            0 :               pro = DEP_PRO (dep);
    2962              : 
    2963            0 :               switch (DEP_TYPE (dep))
    2964              :                 {
    2965              :                 case REG_DEP_TRUE:
    2966              :                   color = "black";
    2967              :                   weight = 1;
    2968              :                   break;
    2969            0 :                 case REG_DEP_OUTPUT:
    2970            0 :                 case REG_DEP_ANTI:
    2971            0 :                   color = "orange";
    2972            0 :                   break;
    2973            0 :                 case REG_DEP_CONTROL:
    2974            0 :                   color = "blue";
    2975            0 :                   break;
    2976            0 :                 default:
    2977            0 :                   gcc_unreachable ();
    2978              :                 }
    2979              : 
    2980            0 :               pp_printf (&pp, "\t%d -> %d [color=%s",
    2981            0 :                          INSN_UID (pro), INSN_UID (con), color);
    2982            0 :               if (int cost = dep_cost (dep))
    2983            0 :                 pp_printf (&pp, ",label=%d", cost);
    2984            0 :               pp_printf (&pp, ",weight=%d", weight);
    2985            0 :               pp_printf (&pp, "];\n");
    2986              :             }
    2987              :         }
    2988            0 :       pp_printf (&pp, "}\n");
    2989              :     }
    2990              : 
    2991            0 :   pp_printf (&pp, "}\n");
    2992            0 :   pp_flush (&pp);
    2993            0 : }
    2994              : 
    2995              : /* Dump dependency graph for the current region to a file using dot syntax.  */
    2996              : 
    2997              : DEBUG_FUNCTION void
    2998            0 : dump_rgn_dependencies_dot (const char *fname)
    2999              : {
    3000            0 :   FILE *fp;
    3001              : 
    3002            0 :   fp = fopen (fname, "w");
    3003            0 :   if (!fp)
    3004              :     {
    3005            0 :       perror ("fopen");
    3006            0 :       return;
    3007              :     }
    3008              : 
    3009            0 :   dump_rgn_dependencies_dot (fp);
    3010            0 :   fclose (fp);
    3011              : }
    3012              : 
    3013              : 
    3014              : /* Returns true if all the basic blocks of the current region have
    3015              :    NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region.  */
    3016              : bool
    3017     10517518 : sched_is_disabled_for_current_region_p (void)
    3018              : {
    3019     10517518 :   int bb;
    3020              : 
    3021     10517518 :   for (bb = 0; bb < current_nr_blocks; bb++)
    3022     10517518 :     if (!(BASIC_BLOCK_FOR_FN (cfun,
    3023     10517518 :                               BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
    3024              :       return false;
    3025              : 
    3026              :   return true;
    3027              : }
    3028              : 
    3029              : /* Free all region dependencies saved in INSN_BACK_DEPS and
    3030              :    INSN_RESOLVED_BACK_DEPS.  The Haifa scheduler does this on the fly
    3031              :    when scheduling, so this function is supposed to be called from
    3032              :    the selective scheduling only.  */
    3033              : void
    3034          715 : free_rgn_deps (void)
    3035              : {
    3036          715 :   int bb;
    3037              : 
    3038         1720 :   for (bb = 0; bb < current_nr_blocks; bb++)
    3039              :     {
    3040         1005 :       rtx_insn *head, *tail;
    3041              : 
    3042         1005 :       gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
    3043         1005 :       get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
    3044              : 
    3045         1005 :       sched_free_deps (head, tail, false);
    3046              :     }
    3047          715 : }
    3048              : 
    3049              : static int rgn_n_insns;
    3050              : 
    3051              : /* Compute insn priority for a current region.  */
    3052              : void
    3053     10517518 : compute_priorities (void)
    3054              : {
    3055     10517518 :   int bb;
    3056              : 
    3057     10517518 :   current_sched_info->sched_max_insns_priority = 0;
    3058     21035372 :   for (bb = 0; bb < current_nr_blocks; bb++)
    3059              :     {
    3060     10517854 :       rtx_insn *head, *tail;
    3061              : 
    3062     10517854 :       gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
    3063     10517854 :       get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
    3064              : 
    3065     10517854 :       if (no_real_insns_p (head, tail))
    3066        18953 :         continue;
    3067              : 
    3068     10498901 :       rgn_n_insns += set_priorities (head, tail);
    3069              :     }
    3070     10517518 :   current_sched_info->sched_max_insns_priority++;
    3071     10517518 : }
    3072              : 
    3073              : /* (Re-)initialize the arrays of DFA states at the end of each basic block.
    3074              : 
    3075              :    SAVED_LAST_BASIC_BLOCK is the previous length of the arrays.  It must be
    3076              :    zero for the first call to this function, to allocate the arrays for the
    3077              :    first time.
    3078              : 
    3079              :    This function is called once during initialization of the scheduler, and
    3080              :    called again to resize the arrays if new basic blocks have been created,
    3081              :    for example for speculation recovery code.  */
    3082              : 
    3083              : static void
    3084     11480836 : realloc_bb_state_array (int saved_last_basic_block)
    3085              : {
    3086     11480836 :   char *old_bb_state_array = bb_state_array;
    3087     11480836 :   size_t lbb = (size_t) last_basic_block_for_fn (cfun);
    3088     11480836 :   size_t slbb = (size_t) saved_last_basic_block;
    3089              : 
    3090              :   /* Nothing to do if nothing changed since the last time this was called.  */
    3091     11480836 :   if (saved_last_basic_block == last_basic_block_for_fn (cfun))
    3092              :     return;
    3093              : 
    3094              :   /* The selective scheduler doesn't use the state arrays.  */
    3095       982908 :   if (sel_sched_p ())
    3096              :     {
    3097          134 :       gcc_assert (bb_state_array == NULL && bb_state == NULL);
    3098              :       return;
    3099              :     }
    3100              : 
    3101       982774 :   gcc_checking_assert (saved_last_basic_block == 0
    3102              :                        || (bb_state_array != NULL && bb_state != NULL));
    3103              : 
    3104       982774 :   bb_state_array = XRESIZEVEC (char, bb_state_array, lbb * dfa_state_size);
    3105       982774 :   bb_state = XRESIZEVEC (state_t, bb_state, lbb);
    3106              : 
    3107              :   /* If BB_STATE_ARRAY has moved, fixup all the state pointers array.
    3108              :      Otherwise only fixup the newly allocated ones.  For the state
    3109              :      array itself, only initialize the new entries.  */
    3110       982774 :   bool bb_state_array_moved = (bb_state_array != old_bb_state_array);
    3111     13465214 :   for (size_t i = bb_state_array_moved ? 0 : slbb; i < lbb; i++)
    3112     12482440 :     bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
    3113     13465214 :   for (size_t i = slbb; i < lbb; i++)
    3114     12482440 :     state_reset (bb_state[i]);
    3115              : }
    3116              : 
    3117              : /* Free the arrays of DFA states at the end of each basic block.  */
    3118              : 
    3119              : static void
    3120       982908 : free_bb_state_array (void)
    3121              : {
    3122       982908 :   free (bb_state_array);
    3123       982908 :   free (bb_state);
    3124       982908 :   bb_state_array = NULL;
    3125       982908 :   bb_state = NULL;
    3126       982908 : }
    3127              : 
    3128              : /* If LAST_BB falls through to another block B, record that B should
    3129              :    start with DFA start STATE.  */
    3130              : 
    3131              : static void
    3132     10516849 : save_state_for_fallthru_edge (basic_block last_bb, state_t state)
    3133              : {
    3134     10516849 :   edge f = find_fallthru_edge (last_bb->succs);
    3135     10516849 :   if (f
    3136     10516849 :       && (!f->probability.initialized_p ()
    3137      6976612 :           || (f->probability.to_reg_br_prob_base () * 100
    3138              :               / REG_BR_PROB_BASE
    3139      6976612 :               >= param_sched_state_edge_prob_cutoff)))
    3140              :   {
    3141      6590556 :     memcpy (bb_state[f->dest->index], state,
    3142              :             dfa_state_size);
    3143      6590556 :     if (sched_verbose >= 5)
    3144            0 :       fprintf (sched_dump, "saving state for edge %d->%d\n",
    3145            0 :                f->src->index, f->dest->index);
    3146              :   }
    3147     10516849 : }
    3148              : 
    3149              : /* Schedule a region.  A region is either an inner loop, a loop-free
    3150              :    subroutine, or a single basic block.  Each bb in the region is
    3151              :    scheduled after its flow predecessors.  */
    3152              : 
    3153              : static void
    3154     10516803 : schedule_region (int rgn)
    3155              : {
    3156     10516803 :   int bb;
    3157     10516803 :   int sched_rgn_n_insns = 0;
    3158              : 
    3159     10516803 :   rgn_n_insns = 0;
    3160              : 
    3161              :   /* Do not support register pressure sensitive scheduling for the new regions
    3162              :      as we don't update the liveness info for them.  */
    3163     10516803 :   if (sched_pressure != SCHED_PRESSURE_NONE
    3164          679 :       && rgn >= nr_regions_initial)
    3165              :     {
    3166            0 :       free_global_sched_pressure_data ();
    3167            0 :       sched_pressure = SCHED_PRESSURE_NONE;
    3168              :     }
    3169              : 
    3170     10516803 :   rgn_setup_region (rgn);
    3171              : 
    3172              :   /* Don't schedule region that is marked by
    3173              :      NOTE_DISABLE_SCHED_OF_BLOCK.  */
    3174     10516803 :   if (sched_is_disabled_for_current_region_p ())
    3175              :     return;
    3176              : 
    3177     10516803 :   sched_rgn_compute_dependencies (rgn);
    3178              : 
    3179     10516803 :   sched_rgn_local_init (rgn);
    3180              : 
    3181              :   /* Set priorities.  */
    3182     10516803 :   compute_priorities ();
    3183              : 
    3184     10516803 :   sched_extend_ready_list (rgn_n_insns);
    3185              : 
    3186     10516803 :   if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
    3187              :     {
    3188          679 :       sched_init_region_reg_pressure_info ();
    3189         2073 :       for (bb = 0; bb < current_nr_blocks; bb++)
    3190              :         {
    3191          715 :           basic_block first_bb, last_bb;
    3192          715 :           rtx_insn *head, *tail;
    3193              : 
    3194          715 :           first_bb = EBB_FIRST_BB (bb);
    3195          715 :           last_bb = EBB_LAST_BB (bb);
    3196              : 
    3197          715 :           get_ebb_head_tail (first_bb, last_bb, &head, &tail);
    3198              : 
    3199          715 :           if (no_real_insns_p (head, tail))
    3200              :             {
    3201            9 :               gcc_assert (first_bb == last_bb);
    3202            9 :               continue;
    3203              :             }
    3204          706 :           sched_setup_bb_reg_pressure_info (first_bb, PREV_INSN (head));
    3205              :         }
    3206              :     }
    3207              : 
    3208              :   /* Now we can schedule all blocks.  */
    3209     21033652 :   for (bb = 0; bb < current_nr_blocks; bb++)
    3210              :     {
    3211     10516849 :       basic_block first_bb, last_bb, curr_bb;
    3212     10516849 :       rtx_insn *head, *tail;
    3213              : 
    3214     10516849 :       first_bb = EBB_FIRST_BB (bb);
    3215     10516849 :       last_bb = EBB_LAST_BB (bb);
    3216              : 
    3217     10516849 :       get_ebb_head_tail (first_bb, last_bb, &head, &tail);
    3218              : 
    3219     10516849 :       if (no_real_insns_p (head, tail))
    3220              :         {
    3221        18921 :           gcc_assert (first_bb == last_bb);
    3222        18921 :           save_state_for_fallthru_edge (last_bb, bb_state[first_bb->index]);
    3223        18921 :           continue;
    3224              :         }
    3225              : 
    3226     10497928 :       current_sched_info->prev_head = PREV_INSN (head);
    3227     10497928 :       current_sched_info->next_tail = NEXT_INSN (tail);
    3228              : 
    3229     10497928 :       remove_notes (head, tail);
    3230              : 
    3231     10497928 :       unlink_bb_notes (first_bb, last_bb);
    3232              : 
    3233     10497928 :       target_bb = bb;
    3234              : 
    3235     10497928 :       gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
    3236     10497928 :       current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
    3237              : 
    3238     10497928 :       curr_bb = first_bb;
    3239     10497928 :       int saved_last_basic_block = last_basic_block_for_fn (cfun);
    3240              : 
    3241     10497928 :       schedule_block (&curr_bb, bb_state[first_bb->index]);
    3242     10497928 :       gcc_assert (EBB_FIRST_BB (bb) == first_bb);
    3243     10497928 :       sched_rgn_n_insns += sched_n_insns;
    3244     10497928 :       realloc_bb_state_array (saved_last_basic_block);
    3245     10497928 :       save_state_for_fallthru_edge (last_bb, curr_state);
    3246              : 
    3247              :       /* Clean up.  */
    3248     10497928 :       if (current_nr_blocks > 1)
    3249           72 :         free_trg_info ();
    3250              :     }
    3251              : 
    3252              :   /* Sanity check: verify that all region insns were scheduled.  */
    3253     10516803 :   gcc_assert (sched_rgn_n_insns == rgn_n_insns);
    3254              : 
    3255     10516803 :   sched_finish_ready_list ();
    3256              : 
    3257              :   /* Done with this region.  */
    3258     10516803 :   sched_rgn_local_finish ();
    3259              : 
    3260              :   /* Free dependencies.  */
    3261     31550455 :   for (bb = 0; bb < current_nr_blocks; ++bb)
    3262     10516849 :     free_block_dependencies (bb);
    3263              : 
    3264     10516803 :   gcc_assert (haifa_recovery_bb_ever_added_p
    3265              :               || deps_pools_are_empty_p ());
    3266              : }
    3267              : 
    3268              : /* Initialize data structures for region scheduling.  */
    3269              : 
    3270              : void
    3271       982908 : sched_rgn_init (bool single_blocks_p)
    3272              : {
    3273       982908 :   min_spec_prob = ((param_min_spec_prob * REG_BR_PROB_BASE)
    3274              :                     / 100);
    3275              : 
    3276       982908 :   nr_inter = 0;
    3277       982908 :   nr_spec = 0;
    3278              : 
    3279       982908 :   extend_regions ();
    3280              : 
    3281       982908 :   CONTAINING_RGN (ENTRY_BLOCK) = -1;
    3282       982908 :   CONTAINING_RGN (EXIT_BLOCK) = -1;
    3283              : 
    3284       982908 :   realloc_bb_state_array (0);
    3285              : 
    3286              :   /* Compute regions for scheduling.  */
    3287       982908 :   if (single_blocks_p
    3288          321 :       || n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS + 1
    3289          199 :       || !flag_schedule_interblock
    3290       983094 :       || is_cfg_nonregular ())
    3291              :     {
    3292       982738 :       find_single_block_region (sel_sched_p ());
    3293              :     }
    3294              :   else
    3295              :     {
    3296              :       /* Compute the dominators and post dominators.  */
    3297          170 :       if (!sel_sched_p ())
    3298           88 :         calculate_dominance_info (CDI_DOMINATORS);
    3299              : 
    3300              :       /* Find regions.  */
    3301          170 :       find_rgns ();
    3302              : 
    3303          170 :       if (sched_verbose >= 3)
    3304            0 :         debug_regions ();
    3305              : 
    3306              :       /* For now.  This will move as more and more of haifa is converted
    3307              :          to using the cfg code.  */
    3308          170 :       if (!sel_sched_p ())
    3309           88 :         free_dominance_info (CDI_DOMINATORS);
    3310              :     }
    3311              : 
    3312       982908 :   gcc_assert (nr_regions > 0 && nr_regions <= n_basic_blocks_for_fn (cfun));
    3313              : 
    3314       982908 :   RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1)
    3315       982908 :                              + RGN_NR_BLOCKS (nr_regions - 1));
    3316       982908 :   nr_regions_initial = nr_regions;
    3317       982908 : }
    3318              : 
    3319              : /* Free data structures for region scheduling.  */
    3320              : void
    3321       982908 : sched_rgn_finish (void)
    3322              : {
    3323       982908 :   free_bb_state_array ();
    3324              : 
    3325              :   /* Reposition the prologue and epilogue notes in case we moved the
    3326              :      prologue/epilogue insns.  */
    3327       982908 :   if (reload_completed)
    3328       982674 :     reposition_prologue_and_epilogue_notes ();
    3329              : 
    3330       982908 :   if (sched_verbose)
    3331              :     {
    3332           24 :       if (reload_completed == 0
    3333            0 :           && flag_schedule_interblock)
    3334              :         {
    3335            0 :           fprintf (sched_dump,
    3336              :                    "\n;; Procedure interblock/speculative motions == %d/%d \n",
    3337              :                    nr_inter, nr_spec);
    3338              :         }
    3339              :       else
    3340           24 :         gcc_assert (nr_inter <= 0);
    3341           24 :       fprintf (sched_dump, "\n\n");
    3342              :     }
    3343              : 
    3344       982908 :   nr_regions = 0;
    3345              : 
    3346       982908 :   free (rgn_table);
    3347       982908 :   rgn_table = NULL;
    3348              : 
    3349       982908 :   free (rgn_bb_table);
    3350       982908 :   rgn_bb_table = NULL;
    3351              : 
    3352       982908 :   free (block_to_bb);
    3353       982908 :   block_to_bb = NULL;
    3354              : 
    3355       982908 :   free (containing_rgn);
    3356       982908 :   containing_rgn = NULL;
    3357              : 
    3358       982908 :   free (ebb_head);
    3359       982908 :   ebb_head = NULL;
    3360       982908 : }
    3361              : 
    3362              : /* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
    3363              :    point to the region RGN.  */
    3364              : void
    3365     10517723 : rgn_setup_region (int rgn)
    3366              : {
    3367     10517723 :   int bb;
    3368              : 
    3369              :   /* Set variables for the current region.  */
    3370     10517723 :   current_nr_blocks = RGN_NR_BLOCKS (rgn);
    3371     10517723 :   current_blocks = RGN_BLOCKS (rgn);
    3372              : 
    3373              :   /* EBB_HEAD is a region-scope structure.  But we realloc it for
    3374              :      each region to save time/memory/something else.
    3375              :      See comments in add_block1, for what reasons we allocate +1 element.  */
    3376     10517723 :   ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
    3377     31555327 :   for (bb = 0; bb <= current_nr_blocks; bb++)
    3378     21037604 :     ebb_head[bb] = current_blocks + bb;
    3379     10517723 : }
    3380              : 
    3381              : /* Compute instruction dependencies in region RGN.  */
    3382              : void
    3383     10517518 : sched_rgn_compute_dependencies (int rgn)
    3384              : {
    3385     10517518 :   if (!RGN_DONT_CALC_DEPS (rgn))
    3386              :     {
    3387     10517518 :       int bb;
    3388              : 
    3389     10517518 :       if (sel_sched_p ())
    3390          715 :         sched_emulate_haifa_p = 1;
    3391              : 
    3392     10517518 :       init_deps_global ();
    3393              : 
    3394              :       /* Initializations for region data dependence analysis.  */
    3395     10517518 :       bb_deps = XNEWVEC (class deps_desc, current_nr_blocks);
    3396     21035372 :       for (bb = 0; bb < current_nr_blocks; bb++)
    3397     10517854 :         init_deps (bb_deps + bb, false);
    3398              : 
    3399              :       /* Initialize bitmap used in add_branch_dependences.  */
    3400     10517518 :       insn_referenced = sbitmap_alloc (sched_max_luid);
    3401     10517518 :       bitmap_clear (insn_referenced);
    3402              : 
    3403              :       /* Compute backward dependencies.  */
    3404     31552890 :       for (bb = 0; bb < current_nr_blocks; bb++)
    3405     10517854 :         compute_block_dependences (bb);
    3406              : 
    3407     10517518 :       sbitmap_free (insn_referenced);
    3408     10517518 :       free_pending_lists ();
    3409     10517518 :       finish_deps_global ();
    3410     10517518 :       free (bb_deps);
    3411              : 
    3412              :       /* We don't want to recalculate this twice.  */
    3413     10517518 :       RGN_DONT_CALC_DEPS (rgn) = 1;
    3414              : 
    3415     10517518 :       if (sel_sched_p ())
    3416          715 :         sched_emulate_haifa_p = 0;
    3417              :     }
    3418              :   else
    3419              :     /* (This is a recovery block.  It is always a single block region.)
    3420              :        OR (We use selective scheduling.)  */
    3421            0 :     gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
    3422     10517518 : }
    3423              : 
    3424              : /* Init region data structures.  Returns true if this region should
    3425              :    not be scheduled.  */
    3426              : void
    3427     10516803 : sched_rgn_local_init (int rgn)
    3428              : {
    3429     10516803 :   int bb;
    3430              : 
    3431              :   /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
    3432     10516803 :   if (current_nr_blocks > 1)
    3433              :     {
    3434           26 :       basic_block block;
    3435           26 :       edge e;
    3436           26 :       edge_iterator ei;
    3437              : 
    3438           26 :       prob = XNEWVEC (int, current_nr_blocks);
    3439              : 
    3440           26 :       dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
    3441           26 :       bitmap_vector_clear (dom, current_nr_blocks);
    3442              : 
    3443              :       /* Use ->aux to implement EDGE_TO_BIT mapping.  */
    3444           26 :       rgn_nr_edges = 0;
    3445         1029 :       FOR_EACH_BB_FN (block, cfun)
    3446              :         {
    3447         1003 :           if (CONTAINING_RGN (block->index) != rgn)
    3448          931 :             continue;
    3449          213 :           FOR_EACH_EDGE (e, ei, block->succs)
    3450          141 :             SET_EDGE_TO_BIT (e, rgn_nr_edges++);
    3451              :         }
    3452              : 
    3453           26 :       rgn_edges = XNEWVEC (edge, rgn_nr_edges);
    3454           26 :       rgn_nr_edges = 0;
    3455         1029 :       FOR_EACH_BB_FN (block, cfun)
    3456              :         {
    3457         1003 :           if (CONTAINING_RGN (block->index) != rgn)
    3458          931 :             continue;
    3459          213 :           FOR_EACH_EDGE (e, ei, block->succs)
    3460          141 :             rgn_edges[rgn_nr_edges++] = e;
    3461              :         }
    3462              : 
    3463              :       /* Split edges.  */
    3464           26 :       pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
    3465           26 :       bitmap_vector_clear (pot_split, current_nr_blocks);
    3466           26 :       ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
    3467           26 :       bitmap_vector_clear (ancestor_edges, current_nr_blocks);
    3468              : 
    3469              :       /* Compute probabilities, dominators, split_edges.  */
    3470          124 :       for (bb = 0; bb < current_nr_blocks; bb++)
    3471           72 :         compute_dom_prob_ps (bb);
    3472              : 
    3473              :       /* Cleanup ->aux used for EDGE_TO_BIT mapping.  */
    3474              :       /* We don't need them anymore.  But we want to avoid duplication of
    3475              :          aux fields in the newly created edges.  */
    3476         1029 :       FOR_EACH_BB_FN (block, cfun)
    3477              :         {
    3478         1003 :           if (CONTAINING_RGN (block->index) != rgn)
    3479          931 :             continue;
    3480          213 :           FOR_EACH_EDGE (e, ei, block->succs)
    3481          141 :             e->aux = NULL;
    3482              :         }
    3483              :     }
    3484     10516803 : }
    3485              : 
    3486              : /* Free data computed for the finished region.  */
    3487              : void
    3488           26 : sched_rgn_local_free (void)
    3489              : {
    3490           26 :   free (prob);
    3491           26 :   sbitmap_vector_free (dom);
    3492           26 :   sbitmap_vector_free (pot_split);
    3493           26 :   sbitmap_vector_free (ancestor_edges);
    3494           26 :   free (rgn_edges);
    3495           26 : }
    3496              : 
    3497              : /* Free data computed for the finished region.  */
    3498              : void
    3499     10516803 : sched_rgn_local_finish (void)
    3500              : {
    3501     10516803 :   if (current_nr_blocks > 1 && !sel_sched_p ())
    3502              :     {
    3503           26 :       sched_rgn_local_free ();
    3504              :     }
    3505     10516803 : }
    3506              : 
    3507              : /* Setup scheduler infos.  */
    3508              : void
    3509       983623 : rgn_setup_common_sched_info (void)
    3510              : {
    3511       983623 :   memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
    3512              :           sizeof (rgn_common_sched_info));
    3513              : 
    3514       983623 :   rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
    3515       983623 :   rgn_common_sched_info.add_block = rgn_add_block;
    3516       983623 :   rgn_common_sched_info.estimate_number_of_insns
    3517       983623 :     = rgn_estimate_number_of_insns;
    3518       983623 :   rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
    3519              : 
    3520       983623 :   common_sched_info = &rgn_common_sched_info;
    3521       983623 : }
    3522              : 
    3523              : /* Setup all *_sched_info structures (for the Haifa frontend
    3524              :    and for the dependence analysis) in the interblock scheduler.  */
    3525              : void
    3526       983489 : rgn_setup_sched_infos (void)
    3527              : {
    3528       983489 :   if (!sel_sched_p ())
    3529       982774 :     memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
    3530              :             sizeof (rgn_sched_deps_info));
    3531              :   else
    3532          715 :     memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
    3533              :             sizeof (rgn_sched_deps_info));
    3534              : 
    3535       983489 :   sched_deps_info = &rgn_sched_deps_info;
    3536              : 
    3537       983489 :   memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
    3538       983489 :   current_sched_info = &rgn_sched_info;
    3539       983489 : }
    3540              : 
    3541              : /* The one entry point in this file.  */
    3542              : void
    3543       982774 : schedule_insns (void)
    3544              : {
    3545       982774 :   int rgn;
    3546              : 
    3547              :   /* Taking care of this degenerate case makes the rest of
    3548              :      this code simpler.  */
    3549       982774 :   if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
    3550              :     return;
    3551              : 
    3552       982774 :   rgn_setup_common_sched_info ();
    3553       982774 :   rgn_setup_sched_infos ();
    3554              : 
    3555       982774 :   haifa_sched_init ();
    3556       982774 :   sched_rgn_init (reload_completed);
    3557              : 
    3558       982774 :   bitmap_initialize (&not_in_df, &bitmap_default_obstack);
    3559              : 
    3560              :   /* Schedule every region in the subroutine.  */
    3561     11499577 :   for (rgn = 0; rgn < nr_regions; rgn++)
    3562     10516803 :     if (dbg_cnt (sched_region))
    3563     10516803 :       schedule_region (rgn);
    3564              : 
    3565              :   /* Clean up.  */
    3566       982774 :   sched_rgn_finish ();
    3567       982774 :   bitmap_release (&not_in_df);
    3568              : 
    3569       982774 :   haifa_sched_finish ();
    3570              : }
    3571              : 
    3572              : /* INSN has been added to/removed from current region.  */
    3573              : static void
    3574            0 : rgn_add_remove_insn (rtx_insn *insn, int remove_p)
    3575              : {
    3576            0 :   if (!remove_p)
    3577            0 :     rgn_n_insns++;
    3578              :   else
    3579            0 :     rgn_n_insns--;
    3580              : 
    3581            0 :   if (INSN_BB (insn) == target_bb)
    3582              :     {
    3583            0 :       if (!remove_p)
    3584            0 :         target_n_insns++;
    3585              :       else
    3586            0 :         target_n_insns--;
    3587              :     }
    3588            0 : }
    3589              : 
    3590              : /* Extend internal data structures.  */
    3591              : void
    3592       983026 : extend_regions (void)
    3593              : {
    3594       983026 :   rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks_for_fn (cfun));
    3595       983026 :   rgn_bb_table = XRESIZEVEC (int, rgn_bb_table,
    3596              :                              n_basic_blocks_for_fn (cfun));
    3597       983026 :   block_to_bb = XRESIZEVEC (int, block_to_bb,
    3598              :                             last_basic_block_for_fn (cfun));
    3599       983026 :   containing_rgn = XRESIZEVEC (int, containing_rgn,
    3600              :                                last_basic_block_for_fn (cfun));
    3601       983026 : }
    3602              : 
    3603              : void
    3604            0 : rgn_make_new_region_out_of_new_block (basic_block bb)
    3605              : {
    3606            0 :   int i;
    3607              : 
    3608            0 :   i = RGN_BLOCKS (nr_regions);
    3609              :   /* I - first free position in rgn_bb_table.  */
    3610              : 
    3611            0 :   rgn_bb_table[i] = bb->index;
    3612            0 :   RGN_NR_BLOCKS (nr_regions) = 1;
    3613            0 :   RGN_HAS_REAL_EBB (nr_regions) = 0;
    3614            0 :   RGN_DONT_CALC_DEPS (nr_regions) = 0;
    3615            0 :   CONTAINING_RGN (bb->index) = nr_regions;
    3616            0 :   BLOCK_TO_BB (bb->index) = 0;
    3617              : 
    3618            0 :   nr_regions++;
    3619              : 
    3620            0 :   RGN_BLOCKS (nr_regions) = i + 1;
    3621            0 : }
    3622              : 
    3623              : /* BB was added to ebb after AFTER.  */
    3624              : static void
    3625            0 : rgn_add_block (basic_block bb, basic_block after)
    3626              : {
    3627            0 :   extend_regions ();
    3628            0 :   bitmap_set_bit (&not_in_df, bb->index);
    3629              : 
    3630            0 :   if (after == 0 || after == EXIT_BLOCK_PTR_FOR_FN (cfun))
    3631              :     {
    3632            0 :       rgn_make_new_region_out_of_new_block (bb);
    3633            0 :       RGN_DONT_CALC_DEPS (nr_regions - 1) = (after
    3634            0 :                                              == EXIT_BLOCK_PTR_FOR_FN (cfun));
    3635              :     }
    3636              :   else
    3637              :     {
    3638            0 :       int i, pos;
    3639              : 
    3640              :       /* We need to fix rgn_table, block_to_bb, containing_rgn
    3641              :          and ebb_head.  */
    3642              : 
    3643            0 :       BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
    3644              : 
    3645              :       /* We extend ebb_head to one more position to
    3646              :          easily find the last position of the last ebb in
    3647              :          the current region.  Thus, ebb_head[BLOCK_TO_BB (after) + 1]
    3648              :          is _always_ valid for access.  */
    3649              : 
    3650            0 :       i = BLOCK_TO_BB (after->index) + 1;
    3651            0 :       pos = ebb_head[i] - 1;
    3652              :       /* Now POS is the index of the last block in the region.  */
    3653              : 
    3654              :       /* Find index of basic block AFTER.  */
    3655            0 :       for (; rgn_bb_table[pos] != after->index; pos--)
    3656              :         ;
    3657              : 
    3658            0 :       pos++;
    3659            0 :       gcc_assert (pos > ebb_head[i - 1]);
    3660              : 
    3661              :       /* i - ebb right after "AFTER".  */
    3662              :       /* ebb_head[i] - VALID.  */
    3663              : 
    3664              :       /* Source position: ebb_head[i]
    3665              :          Destination position: ebb_head[i] + 1
    3666              :          Last position:
    3667              :            RGN_BLOCKS (nr_regions) - 1
    3668              :          Number of elements to copy: (last_position) - (source_position) + 1
    3669              :        */
    3670              : 
    3671            0 :       memmove (rgn_bb_table + pos + 1,
    3672            0 :                rgn_bb_table + pos,
    3673            0 :                ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
    3674              :                * sizeof (*rgn_bb_table));
    3675              : 
    3676            0 :       rgn_bb_table[pos] = bb->index;
    3677              : 
    3678            0 :       for (; i <= current_nr_blocks; i++)
    3679            0 :         ebb_head [i]++;
    3680              : 
    3681            0 :       i = CONTAINING_RGN (after->index);
    3682            0 :       CONTAINING_RGN (bb->index) = i;
    3683              : 
    3684            0 :       RGN_HAS_REAL_EBB (i) = 1;
    3685              : 
    3686            0 :       for (++i; i <= nr_regions; i++)
    3687            0 :         RGN_BLOCKS (i)++;
    3688              :     }
    3689            0 : }
    3690              : 
    3691              : /* Fix internal data after interblock movement of jump instruction.
    3692              :    For parameter meaning please refer to
    3693              :    sched-int.h: struct sched_info: fix_recovery_cfg.  */
    3694              : static void
    3695            0 : rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
    3696              : {
    3697            0 :   int old_pos, new_pos, i;
    3698              : 
    3699            0 :   BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
    3700              : 
    3701            0 :   for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
    3702            0 :        rgn_bb_table[old_pos] != check_bb_nexti;
    3703              :        old_pos--)
    3704              :     ;
    3705            0 :   gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
    3706              : 
    3707            0 :   for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
    3708            0 :        rgn_bb_table[new_pos] != bbi;
    3709              :        new_pos--)
    3710              :     ;
    3711            0 :   new_pos++;
    3712            0 :   gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
    3713              : 
    3714            0 :   gcc_assert (new_pos < old_pos);
    3715              : 
    3716            0 :   memmove (rgn_bb_table + new_pos + 1,
    3717            0 :            rgn_bb_table + new_pos,
    3718            0 :            (old_pos - new_pos) * sizeof (*rgn_bb_table));
    3719              : 
    3720            0 :   rgn_bb_table[new_pos] = check_bb_nexti;
    3721              : 
    3722            0 :   for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
    3723            0 :     ebb_head[i]++;
    3724            0 : }
    3725              : 
    3726              : /* Return next block in ebb chain.  For parameter meaning please refer to
    3727              :    sched-int.h: struct sched_info: advance_target_bb.  */
    3728              : static basic_block
    3729    113624729 : advance_target_bb (basic_block bb, rtx_insn *insn)
    3730              : {
    3731    113624729 :   if (insn)
    3732              :     return 0;
    3733              : 
    3734            0 :   gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
    3735              :               && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
    3736              :   return bb->next_bb;
    3737              : }
    3738              : 
    3739              : #endif
    3740              : 
    3741              : /* Run instruction scheduler.  */
    3742              : static unsigned int
    3743           35 : rest_of_handle_live_range_shrinkage (void)
    3744              : {
    3745              : #ifdef INSN_SCHEDULING
    3746           35 :   int saved;
    3747              : 
    3748           35 :   initialize_live_range_shrinkage ();
    3749           35 :   saved = flag_schedule_interblock;
    3750           35 :   flag_schedule_interblock = false;
    3751           35 :   schedule_insns ();
    3752           35 :   flag_schedule_interblock = saved;
    3753           35 :   finish_live_range_shrinkage ();
    3754              : #endif
    3755           35 :   return 0;
    3756              : }
    3757              : 
    3758              : /* Run instruction scheduler.  */
    3759              : static unsigned int
    3760          199 : rest_of_handle_sched (void)
    3761              : {
    3762              : #ifdef INSN_SCHEDULING
    3763          199 :   if (flag_selective_scheduling
    3764          199 :       && ! maybe_skip_selective_scheduling ())
    3765           47 :     run_selective_scheduling ();
    3766              :   else
    3767          152 :     schedule_insns ();
    3768              : #endif
    3769          199 :   return 0;
    3770              : }
    3771              : 
    3772              : /* Run second scheduling pass after reload.  */
    3773              : static unsigned int
    3774       982732 : rest_of_handle_sched2 (void)
    3775              : {
    3776              : #ifdef INSN_SCHEDULING
    3777       982732 :   if (flag_selective_scheduling2
    3778       982732 :       && ! maybe_skip_selective_scheduling ())
    3779           87 :     run_selective_scheduling ();
    3780              :   else
    3781              :     {
    3782              :       /* Do control and data sched analysis again,
    3783              :          and write some more of the results to dump file.  */
    3784       982645 :       if (flag_sched2_use_superblocks)
    3785           58 :         schedule_ebbs ();
    3786              :       else
    3787       982587 :         schedule_insns ();
    3788              :     }
    3789              : #endif
    3790       982732 :   return 0;
    3791              : }
    3792              : 
    3793              : static unsigned int
    3794            0 : rest_of_handle_sched_fusion (void)
    3795              : {
    3796              : #ifdef INSN_SCHEDULING
    3797            0 :   sched_fusion = true;
    3798            0 :   schedule_insns ();
    3799            0 :   sched_fusion = false;
    3800              : #endif
    3801            0 :   return 0;
    3802              : }
    3803              : 
    3804              : namespace {
    3805              : 
    3806              : const pass_data pass_data_live_range_shrinkage =
    3807              : {
    3808              :   RTL_PASS, /* type */
    3809              :   "lr_shrinkage", /* name */
    3810              :   OPTGROUP_NONE, /* optinfo_flags */
    3811              :   TV_LIVE_RANGE_SHRINKAGE, /* tv_id */
    3812              :   0, /* properties_required */
    3813              :   0, /* properties_provided */
    3814              :   0, /* properties_destroyed */
    3815              :   0, /* todo_flags_start */
    3816              :   TODO_df_finish, /* todo_flags_finish */
    3817              : };
    3818              : 
    3819              : class pass_live_range_shrinkage : public rtl_opt_pass
    3820              : {
    3821              : public:
    3822       297180 :   pass_live_range_shrinkage(gcc::context *ctxt)
    3823       594360 :     : rtl_opt_pass(pass_data_live_range_shrinkage, ctxt)
    3824              :   {}
    3825              : 
    3826              :   /* opt_pass methods: */
    3827      1517135 :   bool gate (function *) final override
    3828              :     {
    3829              : #ifdef INSN_SCHEDULING
    3830      1517135 :       return flag_live_range_shrinkage;
    3831              : #else
    3832              :       return 0;
    3833              : #endif
    3834              :     }
    3835              : 
    3836           35 :   unsigned int execute (function *) final override
    3837              :     {
    3838           35 :       return rest_of_handle_live_range_shrinkage ();
    3839              :     }
    3840              : 
    3841              : }; // class pass_live_range_shrinkage
    3842              : 
    3843              : } // anon namespace
    3844              : 
    3845              : rtl_opt_pass *
    3846       297180 : make_pass_live_range_shrinkage (gcc::context *ctxt)
    3847              : {
    3848       297180 :   return new pass_live_range_shrinkage (ctxt);
    3849              : }
    3850              : 
    3851              : namespace {
    3852              : 
    3853              : const pass_data pass_data_sched =
    3854              : {
    3855              :   RTL_PASS, /* type */
    3856              :   "sched1", /* name */
    3857              :   OPTGROUP_NONE, /* optinfo_flags */
    3858              :   TV_SCHED, /* tv_id */
    3859              :   0, /* properties_required */
    3860              :   0, /* properties_provided */
    3861              :   0, /* properties_destroyed */
    3862              :   0, /* todo_flags_start */
    3863              :   TODO_df_finish, /* todo_flags_finish */
    3864              : };
    3865              : 
    3866              : class pass_sched : public rtl_opt_pass
    3867              : {
    3868              : public:
    3869       297180 :   pass_sched (gcc::context *ctxt)
    3870       594360 :     : rtl_opt_pass (pass_data_sched, ctxt)
    3871              :   {}
    3872              : 
    3873              :   /* opt_pass methods: */
    3874              :   bool gate (function *) final override;
    3875          199 :   unsigned int execute (function *) final override
    3876              :   {
    3877          199 :     return rest_of_handle_sched ();
    3878              :   }
    3879              : 
    3880              : }; // class pass_sched
    3881              : 
    3882              : bool
    3883      1517135 : pass_sched::gate (function *)
    3884              : {
    3885              : #ifdef INSN_SCHEDULING
    3886      1517135 :   return optimize > 0 && flag_schedule_insns && dbg_cnt (sched_func);
    3887              : #else
    3888              :   return 0;
    3889              : #endif
    3890              : }
    3891              : 
    3892              : } // anon namespace
    3893              : 
    3894              : rtl_opt_pass *
    3895       297180 : make_pass_sched (gcc::context *ctxt)
    3896              : {
    3897       297180 :   return new pass_sched (ctxt);
    3898              : }
    3899              : 
    3900              : namespace {
    3901              : 
    3902              : const pass_data pass_data_sched2 =
    3903              : {
    3904              :   RTL_PASS, /* type */
    3905              :   "sched2", /* name */
    3906              :   OPTGROUP_NONE, /* optinfo_flags */
    3907              :   TV_SCHED2, /* tv_id */
    3908              :   0, /* properties_required */
    3909              :   0, /* properties_provided */
    3910              :   0, /* properties_destroyed */
    3911              :   0, /* todo_flags_start */
    3912              :   TODO_df_finish, /* todo_flags_finish */
    3913              : };
    3914              : 
    3915              : class pass_sched2 : public rtl_opt_pass
    3916              : {
    3917              : public:
    3918       297180 :   pass_sched2 (gcc::context *ctxt)
    3919       594360 :     : rtl_opt_pass (pass_data_sched2, ctxt)
    3920              :   {}
    3921              : 
    3922              :   /* opt_pass methods: */
    3923              :   bool gate (function *) final override;
    3924       982732 :   unsigned int execute (function *) final override
    3925              :     {
    3926       982732 :       return rest_of_handle_sched2 ();
    3927              :     }
    3928              : 
    3929              : }; // class pass_sched2
    3930              : 
    3931              : bool
    3932      1517135 : pass_sched2::gate (function *)
    3933              : {
    3934              : #ifdef INSN_SCHEDULING
    3935      1064964 :   return optimize > 0 && flag_schedule_insns_after_reload
    3936      2499868 :     && !targetm.delay_sched2 && dbg_cnt (sched2_func);
    3937              : #else
    3938              :   return 0;
    3939              : #endif
    3940              : }
    3941              : 
    3942              : } // anon namespace
    3943              : 
    3944              : rtl_opt_pass *
    3945       297180 : make_pass_sched2 (gcc::context *ctxt)
    3946              : {
    3947       297180 :   return new pass_sched2 (ctxt);
    3948              : }
    3949              : 
    3950              : namespace {
    3951              : 
    3952              : const pass_data pass_data_sched_fusion =
    3953              : {
    3954              :   RTL_PASS, /* type */
    3955              :   "sched_fusion", /* name */
    3956              :   OPTGROUP_NONE, /* optinfo_flags */
    3957              :   TV_SCHED_FUSION, /* tv_id */
    3958              :   0, /* properties_required */
    3959              :   0, /* properties_provided */
    3960              :   0, /* properties_destroyed */
    3961              :   0, /* todo_flags_start */
    3962              :   TODO_df_finish, /* todo_flags_finish */
    3963              : };
    3964              : 
    3965              : class pass_sched_fusion : public rtl_opt_pass
    3966              : {
    3967              : public:
    3968       297180 :   pass_sched_fusion (gcc::context *ctxt)
    3969       594360 :     : rtl_opt_pass (pass_data_sched_fusion, ctxt)
    3970              :   {}
    3971              : 
    3972              :   /* opt_pass methods: */
    3973              :   bool gate (function *) final override;
    3974            0 :   unsigned int execute (function *) final override
    3975              :     {
    3976            0 :       return rest_of_handle_sched_fusion ();
    3977              :     }
    3978              : 
    3979              : }; // class pass_sched2
    3980              : 
    3981              : bool
    3982      1517135 : pass_sched_fusion::gate (function *)
    3983              : {
    3984              : #ifdef INSN_SCHEDULING
    3985              :   /* Scheduling fusion relies on peephole2 to do real fusion work,
    3986              :      so only enable it if peephole2 is in effect.  */
    3987      1064964 :   return (optimize > 0 && flag_peephole2
    3988      2499875 :     && flag_schedule_fusion && targetm.sched.fusion_priority != NULL);
    3989              : #else
    3990              :   return 0;
    3991              : #endif
    3992              : }
    3993              : 
    3994              : } // anon namespace
    3995              : 
    3996              : rtl_opt_pass *
    3997       297180 : make_pass_sched_fusion (gcc::context *ctxt)
    3998              : {
    3999       297180 :   return new pass_sched_fusion (ctxt);
    4000              : }
    4001              : 
    4002              : #if __GNUC__ >= 10
    4003              : #  pragma GCC diagnostic pop
    4004              : #endif
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.