Subversion Repositories openrisc

/* Instruction scheduling pass.

   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,

   2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010

   Free Software Foundation, Inc.

   Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,

   and currently maintained by, Jim Wilson (wilson@cygnus.com)

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

/* This pass implements list scheduling within basic blocks.  It is

   run twice: (1) after flow analysis, but before register allocation,

   and (2) after register allocation.

   The first run performs interblock scheduling, moving insns between

   different blocks in the same "region", and the second runs only

   basic block scheduling.

   Interblock motions performed are useful motions and speculative

   motions, including speculative loads.  Motions requiring code

   duplication are not supported.  The identification of motion type

   and the check for validity of speculative motions requires

   construction and analysis of the function's control flow graph.

   The main entry point for this pass is schedule_insns(), called for

   each function.  The work of the scheduler is organized in three

   levels: (1) function level: insns are subject to splitting,

   control-flow-graph is constructed, regions are computed (after

   reload, each region is of one block), (2) region level: control

   flow graph attributes required for interblock scheduling are

   computed (dominators, reachability, etc.), data dependences and

   priorities are computed, and (3) block level: insns in the block

   are actually scheduled.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "toplev.h"

#include "rtl.h"

#include "tm_p.h"

#include "hard-reg-set.h"

#include "regs.h"

#include "function.h"

#include "flags.h"

#include "insn-config.h"

#include "insn-attr.h"

#include "except.h"

#include "toplev.h"

#include "recog.h"

#include "cfglayout.h"

#include "params.h"

#include "sched-int.h"

#include "sel-sched.h"

#include "target.h"

#include "timevar.h"

#include "tree-pass.h"

#include "dbgcnt.h"

#ifdef INSN_SCHEDULING

/* Some accessor macros for h_i_d members only used within this file.  */

#define FED_BY_SPEC_LOAD(INSN) (HID (INSN)->fed_by_spec_load)

#define IS_LOAD_INSN(INSN) (HID (insn)->is_load_insn)

/* nr_inter/spec counts interblock/speculative motion for the function.  */

static int nr_inter, nr_spec;

static int is_cfg_nonregular (void);

/* Number of regions in the procedure.  */

int nr_regions = 0;

/* Table of region descriptions.  */

region *rgn_table = NULL;

/* Array of lists of regions' blocks.  */

int *rgn_bb_table = NULL;

/* Topological order of blocks in the region (if b2 is reachable from

   b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is

   always referred to by either block or b, while its topological

   order name (in the region) is referred to by bb.  */

int *block_to_bb = NULL;

/* The number of the region containing a block.  */

int *containing_rgn = NULL;

/* ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.

   Currently we can get a ebb only through splitting of currently

   scheduling block, therefore, we don't need ebb_head array for every region,

   hence, its sufficient to hold it for current one only.  */

int *ebb_head = NULL;

/* The minimum probability of reaching a source block so that it will be

   considered for speculative scheduling.  */

static int min_spec_prob;

static void find_single_block_region (bool);

static void find_rgns (void);

static bool too_large (int, int *, int *);

/* Blocks of the current region being scheduled.  */

int current_nr_blocks;

int current_blocks;

/* A speculative motion requires checking live information on the path

   from 'source' to 'target'.  The split blocks are those to be checked.

   After a speculative motion, live information should be modified in

   the 'update' blocks.

   Lists of split and update blocks for each candidate of the current

   target are in array bblst_table.  */

static basic_block *bblst_table;

static int bblst_size, bblst_last;

/* Target info declarations.

   The block currently being scheduled is referred to as the "target" block,

   while other blocks in the region from which insns can be moved to the

   target are called "source" blocks.  The candidate structure holds info

   about such sources: are they valid?  Speculative?  Etc.  */

typedef struct

{

  basic_block *first_member;

  int nr_members;

}

bblst;

typedef struct

{

  char is_valid;

  char is_speculative;

  int src_prob;

  bblst split_bbs;

  bblst update_bbs;

}

candidate;

static candidate *candidate_table;

#define IS_VALID(src) (candidate_table[src].is_valid)

#define IS_SPECULATIVE(src) (candidate_table[src].is_speculative)

#define IS_SPECULATIVE_INSN(INSN)                       \

  (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))

#define SRC_PROB(src) ( candidate_table[src].src_prob )

/* The bb being currently scheduled.  */

int target_bb;

/* List of edges.  */

typedef struct

{

  edge *first_member;

  int nr_members;

}

edgelst;

static edge *edgelst_table;

static int edgelst_last;

static void extract_edgelst (sbitmap, edgelst *);

/* Target info functions.  */

static void split_edges (int, int, edgelst *);

static void compute_trg_info (int);

void debug_candidate (int);

void debug_candidates (int);

/* Dominators array: dom[i] contains the sbitmap of dominators of

   bb i in the region.  */

static sbitmap *dom;

/* bb 0 is the only region entry.  */

#define IS_RGN_ENTRY(bb) (!bb)

/* Is bb_src dominated by bb_trg.  */

#define IS_DOMINATED(bb_src, bb_trg)                                 \

( TEST_BIT (dom[bb_src], bb_trg) )

/* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is

   the probability of bb i relative to the region entry.  */

static int *prob;

/* Bit-set of edges, where bit i stands for edge i.  */

typedef sbitmap edgeset;

/* Number of edges in the region.  */

static int rgn_nr_edges;

/* Array of size rgn_nr_edges.  */

static edge *rgn_edges;

/* Mapping from each edge in the graph to its number in the rgn.  */

#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)

#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))

/* The split edges of a source bb is different for each target

   bb.  In order to compute this efficiently, the 'potential-split edges'

   are computed for each bb prior to scheduling a region.  This is actually

   the split edges of each bb relative to the region entry.

   pot_split[bb] is the set of potential split edges of bb.  */

static edgeset *pot_split;

/* For every bb, a set of its ancestor edges.  */

static edgeset *ancestor_edges;

#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))

/* Speculative scheduling functions.  */

static int check_live_1 (int, rtx);

static void update_live_1 (int, rtx);

static int is_pfree (rtx, int, int);

static int find_conditional_protection (rtx, int);

static int is_conditionally_protected (rtx, int, int);

static int is_prisky (rtx, int, int);

static int is_exception_free (rtx, int, int);

static bool sets_likely_spilled (rtx);

static void sets_likely_spilled_1 (rtx, const_rtx, void *);

static void add_branch_dependences (rtx, rtx);

static void compute_block_dependences (int);

static void schedule_region (int);

static rtx concat_INSN_LIST (rtx, rtx);

static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);

static void propagate_deps (int, struct deps_desc *);

static void free_pending_lists (void);

/* Functions for construction of the control flow graph.  */

/* Return 1 if control flow graph should not be constructed, 0 otherwise.

   We decide not to build the control flow graph if there is possibly more

   than one entry to the function, if computed branches exist, if we

   have nonlocal gotos, or if we have an unreachable loop.  */

static int

is_cfg_nonregular (void)

{

  basic_block b;

  rtx insn;

  /* If we have a label that could be the target of a nonlocal goto, then

     the cfg is not well structured.  */

  if (nonlocal_goto_handler_labels)

    return 1;

  /* If we have any forced labels, then the cfg is not well structured.  */

  if (forced_labels)

    return 1;

  /* If we have exception handlers, then we consider the cfg not well

     structured.  ?!?  We should be able to handle this now that we

     compute an accurate cfg for EH.  */

  if (current_function_has_exception_handlers ())

    return 1;

  /* If we have insns which refer to labels as non-jumped-to operands,

     then we consider the cfg not well structured.  */

  FOR_EACH_BB (b)

    FOR_BB_INSNS (b, insn)

      {

        rtx note, next, set, dest;

        /* If this function has a computed jump, then we consider the cfg

           not well structured.  */

        if (JUMP_P (insn) && computed_jump_p (insn))

          return 1;

        if (!INSN_P (insn))

          continue;

        note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX);

        if (note == NULL_RTX)

          continue;

        /* For that label not to be seen as a referred-to label, this

           must be a single-set which is feeding a jump *only*.  This

           could be a conditional jump with the label split off for

           machine-specific reasons or a casesi/tablejump.  */

        next = next_nonnote_insn (insn);

        if (next == NULL_RTX

            || !JUMP_P (next)

            || (JUMP_LABEL (next) != XEXP (note, 0)

                && find_reg_note (next, REG_LABEL_TARGET,

                                  XEXP (note, 0)) == NULL_RTX)

            || BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (next))

          return 1;

        set = single_set (insn);

        if (set == NULL_RTX)

          return 1;

        dest = SET_DEST (set);

        if (!REG_P (dest) || !dead_or_set_p (next, dest))

          return 1;

      }

  /* Unreachable loops with more than one basic block are detected

     during the DFS traversal in find_rgns.

     Unreachable loops with a single block are detected here.  This

     test is redundant with the one in find_rgns, but it's much

     cheaper to go ahead and catch the trivial case here.  */

  FOR_EACH_BB (b)

    {

      if (EDGE_COUNT (b->preds) == 0

          || (single_pred_p (b)

              && single_pred (b) == b))

        return 1;

    }

  /* All the tests passed.  Consider the cfg well structured.  */

  return 0;

}

/* Extract list of edges from a bitmap containing EDGE_TO_BIT bits.  */

static void

extract_edgelst (sbitmap set, edgelst *el)

{

  unsigned int i = 0;

  sbitmap_iterator sbi;

  /* edgelst table space is reused in each call to extract_edgelst.  */

  edgelst_last = 0;

  el->first_member = &edgelst_table[edgelst_last];

  el->nr_members = 0;

  /* Iterate over each word in the bitset.  */

  EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)

    {

      edgelst_table[edgelst_last++] = rgn_edges[i];

      el->nr_members++;

    }

}

/* Functions for the construction of regions.  */

/* Print the regions, for debugging purposes.  Callable from debugger.  */

void

debug_regions (void)

{

  int rgn, bb;

  fprintf (sched_dump, "\n;;   ------------ REGIONS ----------\n\n");

  for (rgn = 0; rgn < nr_regions; rgn++)

    {

      fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,

               rgn_table[rgn].rgn_nr_blocks);

      fprintf (sched_dump, ";;\tbb/block: ");

      /* We don't have ebb_head initialized yet, so we can't use

         BB_TO_BLOCK ().  */

      current_blocks = RGN_BLOCKS (rgn);

      for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)

        fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);

      fprintf (sched_dump, "\n\n");

    }

}

/* Print the region's basic blocks.  */

void

debug_region (int rgn)

{

  int bb;

  fprintf (stderr, "\n;;   ------------ REGION %d ----------\n\n", rgn);

  fprintf (stderr, ";;\trgn %d nr_blocks %d:\n", rgn,

           rgn_table[rgn].rgn_nr_blocks);

  fprintf (stderr, ";;\tbb/block: ");

  /* We don't have ebb_head initialized yet, so we can't use

     BB_TO_BLOCK ().  */

  current_blocks = RGN_BLOCKS (rgn);

  for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)

    fprintf (stderr, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);

  fprintf (stderr, "\n\n");

  for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)

    {

      debug_bb_n_slim (rgn_bb_table[current_blocks + bb]);

      fprintf (stderr, "\n");

    }

  fprintf (stderr, "\n");

}

/* True when a bb with index BB_INDEX contained in region RGN.  */

static bool

bb_in_region_p (int bb_index, int rgn)

{

  int i;

  for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)

    if (rgn_bb_table[current_blocks + i] == bb_index)

      return true;

  return false;

}

/* Dump region RGN to file F using dot syntax.  */

void

dump_region_dot (FILE *f, int rgn)

{

  int i;

  fprintf (f, "digraph Region_%d {\n", rgn);

  /* We don't have ebb_head initialized yet, so we can't use

     BB_TO_BLOCK ().  */

  current_blocks = RGN_BLOCKS (rgn);

  for (i = 0; i < rgn_table[rgn].rgn_nr_blocks; i++)

    {

      edge e;

      edge_iterator ei;

      int src_bb_num = rgn_bb_table[current_blocks + i];

      struct basic_block_def *bb = BASIC_BLOCK (src_bb_num);

      FOR_EACH_EDGE (e, ei, bb->succs)

        if (bb_in_region_p (e->dest->index, rgn))

          fprintf (f, "\t%d -> %d\n", src_bb_num, e->dest->index);

    }

  fprintf (f, "}\n");

}

/* The same, but first open a file specified by FNAME.  */

void

dump_region_dot_file (const char *fname, int rgn)

{

  FILE *f = fopen (fname, "wt");

  dump_region_dot (f, rgn);

  fclose (f);

}

/* Build a single block region for each basic block in the function.

   This allows for using the same code for interblock and basic block

   scheduling.  */

static void

find_single_block_region (bool ebbs_p)

{

  basic_block bb, ebb_start;

  int i = 0;

  nr_regions = 0;

  if (ebbs_p) {

    int probability_cutoff;

    if (profile_info && flag_branch_probabilities)

      probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);

    else

      probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);

    probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;

    FOR_EACH_BB (ebb_start)

      {

        RGN_NR_BLOCKS (nr_regions) = 0;

        RGN_BLOCKS (nr_regions) = i;

        RGN_DONT_CALC_DEPS (nr_regions) = 0;

        RGN_HAS_REAL_EBB (nr_regions) = 0;

        for (bb = ebb_start; ; bb = bb->next_bb)

          {

            edge e;

            edge_iterator ei;

            rgn_bb_table[i] = bb->index;

            RGN_NR_BLOCKS (nr_regions)++;

            CONTAINING_RGN (bb->index) = nr_regions;

            BLOCK_TO_BB (bb->index) = i - RGN_BLOCKS (nr_regions);

            i++;

            if (bb->next_bb == EXIT_BLOCK_PTR

                || LABEL_P (BB_HEAD (bb->next_bb)))

              break;

            FOR_EACH_EDGE (e, ei, bb->succs)

             if ((e->flags & EDGE_FALLTHRU) != 0)

               break;

            if (! e)

              break;

            if (e->probability <= probability_cutoff)

              break;

          }

        ebb_start = bb;

        nr_regions++;

      }

  }

  else

    FOR_EACH_BB (bb)

      {

        rgn_bb_table[nr_regions] = bb->index;

        RGN_NR_BLOCKS (nr_regions) = 1;

        RGN_BLOCKS (nr_regions) = nr_regions;

        RGN_DONT_CALC_DEPS (nr_regions) = 0;

        RGN_HAS_REAL_EBB (nr_regions) = 0;

        CONTAINING_RGN (bb->index) = nr_regions;

        BLOCK_TO_BB (bb->index) = 0;

        nr_regions++;

      }

}

/* Estimate number of the insns in the BB.  */

static int

rgn_estimate_number_of_insns (basic_block bb)

{

  int count;

  count = INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));

  if (MAY_HAVE_DEBUG_INSNS)

    {

      rtx insn;

      FOR_BB_INSNS (bb, insn)

        if (DEBUG_INSN_P (insn))

          count--;

    }

  return count;

}

/* Update number of blocks and the estimate for number of insns

   in the region.  Return true if the region is "too large" for interblock

   scheduling (compile time considerations).  */

static bool

too_large (int block, int *num_bbs, int *num_insns)

{

  (*num_bbs)++;

  (*num_insns) += (common_sched_info->estimate_number_of_insns

                   (BASIC_BLOCK (block)));

  return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))

          || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));

}

/* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]

   is still an inner loop.  Put in max_hdr[blk] the header of the most inner

   loop containing blk.  */

#define UPDATE_LOOP_RELATIONS(blk, hdr)         \

{                                               \

  if (max_hdr[blk] == -1)                       \

    max_hdr[blk] = hdr;                         \

  else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])  \

    RESET_BIT (inner, hdr);                     \

  else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])  \

    {                                           \

      RESET_BIT (inner,max_hdr[blk]);           \

      max_hdr[blk] = hdr;                       \

    }                                           \

}

/* Find regions for interblock scheduling.

   A region for scheduling can be:

     * A loop-free procedure, or

     * A reducible inner loop, or

     * A basic block not contained in any other region.

   ?!? In theory we could build other regions based on extended basic

   blocks or reverse extended basic blocks.  Is it worth the trouble?

   Loop blocks that form a region are put into the region's block list

   in topological order.

   This procedure stores its results into the following global (ick) variables

     * rgn_nr

     * rgn_table

     * rgn_bb_table

     * block_to_bb

     * containing region

   We use dominator relationships to avoid making regions out of non-reducible

   loops.

   This procedure needs to be converted to work on pred/succ lists instead

   of edge tables.  That would simplify it somewhat.  */

static void

haifa_find_rgns (void)

{

  int *max_hdr, *dfs_nr, *degree;

  char no_loops = 1;

  int node, child, loop_head, i, head, tail;

  int count = 0, sp, idx = 0;

  edge_iterator current_edge;

  edge_iterator *stack;

  int num_bbs, num_insns, unreachable;

  int too_large_failure;

  basic_block bb;

  /* Note if a block is a natural loop header.  */

  sbitmap header;

  /* Note if a block is a natural inner loop header.  */

  sbitmap inner;

  /* Note if a block is in the block queue.  */

  sbitmap in_queue;

  /* Note if a block is in the block queue.  */

  sbitmap in_stack;

  /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops

     and a mapping from block to its loop header (if the block is contained

     in a loop, else -1).

     Store results in HEADER, INNER, and MAX_HDR respectively, these will

     be used as inputs to the second traversal.

     STACK, SP and DFS_NR are only used during the first traversal.  */

  /* Allocate and initialize variables for the first traversal.  */

  max_hdr = XNEWVEC (int, last_basic_block);

  dfs_nr = XCNEWVEC (int, last_basic_block);

  stack = XNEWVEC (edge_iterator, n_edges);

  inner = sbitmap_alloc (last_basic_block);

  sbitmap_ones (inner);

  header = sbitmap_alloc (last_basic_block);

  sbitmap_zero (header);

  in_queue = sbitmap_alloc (last_basic_block);

  sbitmap_zero (in_queue);

  in_stack = sbitmap_alloc (last_basic_block);

  sbitmap_zero (in_stack);

  for (i = 0; i < last_basic_block; i++)

    max_hdr[i] = -1;

  #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)

  #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))

  /* DFS traversal to find inner loops in the cfg.  */

  current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);

  sp = -1;

  while (1)

    {

      if (EDGE_PASSED (current_edge))

        {

          /* We have reached a leaf node or a node that was already

             processed.  Pop edges off the stack until we find

             an edge that has not yet been processed.  */

          while (sp >= 0 && EDGE_PASSED (current_edge))

            {

              /* Pop entry off the stack.  */

              current_edge = stack[sp--];

              node = ei_edge (current_edge)->src->index;

              gcc_assert (node != ENTRY_BLOCK);

              child = ei_edge (current_edge)->dest->index;

              gcc_assert (child != EXIT_BLOCK);

              RESET_BIT (in_stack, child);

              if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))

                UPDATE_LOOP_RELATIONS (node, max_hdr[child]);

              ei_next (&current_edge);

            }

          /* See if have finished the DFS tree traversal.  */

          if (sp < 0 && EDGE_PASSED (current_edge))

            break;

          /* Nope, continue the traversal with the popped node.  */

          continue;

        }

      /* Process a node.  */

      node = ei_edge (current_edge)->src->index;

      gcc_assert (node != ENTRY_BLOCK);

      SET_BIT (in_stack, node);

      dfs_nr[node] = ++count;

      /* We don't traverse to the exit block.  */

      child = ei_edge (current_edge)->dest->index;

      if (child == EXIT_BLOCK)

        {

          SET_EDGE_PASSED (current_edge);

          ei_next (&current_edge);

          continue;

        }

      /* If the successor is in the stack, then we've found a loop.

         Mark the loop, if it is not a natural loop, then it will

         be rejected during the second traversal.  */

      if (TEST_BIT (in_stack, child))

        {

          no_loops = 0;

          SET_BIT (header, child);

          UPDATE_LOOP_RELATIONS (node, child);