--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/sched-rgn.c	Fri Jul 17 14:47:48 2009 +0900
@@ -0,0 +1,3521 @@
+/* Instruction scheduling pass.
+   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
+   2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
+   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 *);
+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)
+{
+  return INSN_LUID (BB_END (bb)) - INSN_LUID (BB_HEAD (bb));
+}
+
+/* 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);
+	  SET_EDGE_PASSED (current_edge);
+	  ei_next (&current_edge);
+	  continue;
+	}
+
+      /* If the child was already visited, then there is no need to visit
+	 it again.  Just update the loop relationships and restart
+	 with a new edge.  */
+      if (dfs_nr[child])
+	{
+	  if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
+	    UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
+	  SET_EDGE_PASSED (current_edge);
+	  ei_next (&current_edge);
+	  continue;
+	}
+
+      /* Push an entry on the stack and continue DFS traversal.  */
+      stack[++sp] = current_edge;
+      SET_EDGE_PASSED (current_edge);
+      current_edge = ei_start (ei_edge (current_edge)->dest->succs);
+    }
+
+  /* Reset ->aux field used by EDGE_PASSED.  */
+  FOR_ALL_BB (bb)
+    {
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	e->aux = NULL;
+    }
+
+
+  /* Another check for unreachable blocks.  The earlier test in
+     is_cfg_nonregular only finds unreachable blocks that do not
+     form a loop.
+
+     The DFS traversal will mark every block that is reachable from
+     the entry node by placing a nonzero value in dfs_nr.  Thus if
+     dfs_nr is zero for any block, then it must be unreachable.  */
+  unreachable = 0;
+  FOR_EACH_BB (bb)
+    if (dfs_nr[bb->index] == 0)
+      {
+	unreachable = 1;
+	break;
+      }
+
+  /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
+     to hold degree counts.  */
+  degree = dfs_nr;
+
+  FOR_EACH_BB (bb)
+    degree[bb->index] = EDGE_COUNT (bb->preds);
+
+  /* Do not perform region scheduling if there are any unreachable
+     blocks.  */
+  if (!unreachable)
+    {
+      int *queue, *degree1 = NULL;
+      /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put
+	 there basic blocks, which are forced to be region heads.
+	 This is done to try to assemble few smaller regions 
+	 from a too_large region.  */
+      sbitmap extended_rgn_header = NULL;
+      bool extend_regions_p;
+
+      if (no_loops)
+	SET_BIT (header, 0);
+
+      /* Second traversal:find reducible inner loops and topologically sort
+	 block of each region.  */
+
+      queue = XNEWVEC (int, n_basic_blocks);
+      
+      extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;
+      if (extend_regions_p)
+        {
+          degree1 = XNEWVEC (int, last_basic_block);
+          extended_rgn_header = sbitmap_alloc (last_basic_block);
+          sbitmap_zero (extended_rgn_header);
+	}
+
+      /* Find blocks which are inner loop headers.  We still have non-reducible
+	 loops to consider at this point.  */
+      FOR_EACH_BB (bb)
+	{
+	  if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
+	    {
+	      edge e;
+	      edge_iterator ei;
+	      basic_block jbb;
+
+	      /* Now check that the loop is reducible.  We do this separate
+		 from finding inner loops so that we do not find a reducible
+		 loop which contains an inner non-reducible loop.
+
+		 A simple way to find reducible/natural loops is to verify
+		 that each block in the loop is dominated by the loop
+		 header.
+
+		 If there exists a block that is not dominated by the loop
+		 header, then the block is reachable from outside the loop
+		 and thus the loop is not a natural loop.  */
+	      FOR_EACH_BB (jbb)
+		{
+		  /* First identify blocks in the loop, except for the loop
+		     entry block.  */
+		  if (bb->index == max_hdr[jbb->index] && bb != jbb)
+		    {
+		      /* Now verify that the block is dominated by the loop
+			 header.  */
+		      if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
+			break;
+		    }
+		}
+
+	      /* If we exited the loop early, then I is the header of
+		 a non-reducible loop and we should quit processing it
+		 now.  */
+	      if (jbb != EXIT_BLOCK_PTR)
+		continue;
+
+	      /* I is a header of an inner loop, or block 0 in a subroutine
+		 with no loops at all.  */
+	      head = tail = -1;
+	      too_large_failure = 0;
+	      loop_head = max_hdr[bb->index];
+
+              if (extend_regions_p)
+                /* We save degree in case when we meet a too_large region 
+		   and cancel it.  We need a correct degree later when 
+                   calling extend_rgns.  */
+                memcpy (degree1, degree, last_basic_block * sizeof (int));
+	      
+	      /* Decrease degree of all I's successors for topological
+		 ordering.  */
+	      FOR_EACH_EDGE (e, ei, bb->succs)
+		if (e->dest != EXIT_BLOCK_PTR)
+		  --degree[e->dest->index];
+
+	      /* Estimate # insns, and count # blocks in the region.  */
+	      num_bbs = 1;
+	      num_insns = common_sched_info->estimate_number_of_insns (bb);
+
+	      /* Find all loop latches (blocks with back edges to the loop
+		 header) or all the leaf blocks in the cfg has no loops.
+
+		 Place those blocks into the queue.  */
+	      if (no_loops)
+		{
+		  FOR_EACH_BB (jbb)
+		    /* Leaf nodes have only a single successor which must
+		       be EXIT_BLOCK.  */
+		    if (single_succ_p (jbb)
+			&& single_succ (jbb) == EXIT_BLOCK_PTR)
+		      {
+			queue[++tail] = jbb->index;
+			SET_BIT (in_queue, jbb->index);
+
+			if (too_large (jbb->index, &num_bbs, &num_insns))
+			  {
+			    too_large_failure = 1;
+			    break;
+			  }
+		      }
+		}
+	      else
+		{
+		  edge e;
+
+		  FOR_EACH_EDGE (e, ei, bb->preds)
+		    {
+		      if (e->src == ENTRY_BLOCK_PTR)
+			continue;
+
+		      node = e->src->index;
+
+		      if (max_hdr[node] == loop_head && node != bb->index)
+			{
+			  /* This is a loop latch.  */
+			  queue[++tail] = node;
+			  SET_BIT (in_queue, node);
+
+			  if (too_large (node, &num_bbs, &num_insns))
+			    {
+			      too_large_failure = 1;
+			      break;
+			    }
+			}
+		    }
+		}
+
+	      /* Now add all the blocks in the loop to the queue.
+
+	     We know the loop is a natural loop; however the algorithm
+	     above will not always mark certain blocks as being in the
+	     loop.  Consider:
+		node   children
+		 a	  b,c
+		 b	  c
+		 c	  a,d
+		 d	  b
+
+	     The algorithm in the DFS traversal may not mark B & D as part
+	     of the loop (i.e. they will not have max_hdr set to A).
+
+	     We know they can not be loop latches (else they would have
+	     had max_hdr set since they'd have a backedge to a dominator
+	     block).  So we don't need them on the initial queue.
+
+	     We know they are part of the loop because they are dominated
+	     by the loop header and can be reached by a backwards walk of
+	     the edges starting with nodes on the initial queue.
+
+	     It is safe and desirable to include those nodes in the
+	     loop/scheduling region.  To do so we would need to decrease
+	     the degree of a node if it is the target of a backedge
+	     within the loop itself as the node is placed in the queue.
+
+	     We do not do this because I'm not sure that the actual
+	     scheduling code will properly handle this case. ?!? */
+
+	      while (head < tail && !too_large_failure)
+		{
+		  edge e;
+		  child = queue[++head];
+
+		  FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds)
+		    {
+		      node = e->src->index;
+
+		      /* See discussion above about nodes not marked as in
+			 this loop during the initial DFS traversal.  */
+		      if (e->src == ENTRY_BLOCK_PTR
+			  || max_hdr[node] != loop_head)
+			{
+			  tail = -1;
+			  break;
+			}
+		      else if (!TEST_BIT (in_queue, node) && node != bb->index)
+			{
+			  queue[++tail] = node;
+			  SET_BIT (in_queue, node);
+
+			  if (too_large (node, &num_bbs, &num_insns))
+			    {
+			      too_large_failure = 1;
+			      break;
+			    }
+			}
+		    }
+		}
+
+	      if (tail >= 0 && !too_large_failure)
+		{
+		  /* Place the loop header into list of region blocks.  */
+		  degree[bb->index] = -1;
+		  rgn_bb_table[idx] = bb->index;
+		  RGN_NR_BLOCKS (nr_regions) = num_bbs;
+		  RGN_BLOCKS (nr_regions) = idx++;
+                  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) = count = 0;
+
+		  /* Remove blocks from queue[] when their in degree
+		     becomes zero.  Repeat until no blocks are left on the
+		     list.  This produces a topological list of blocks in
+		     the region.  */
+		  while (tail >= 0)
+		    {
+		      if (head < 0)
+			head = tail;
+		      child = queue[head];
+		      if (degree[child] == 0)
+			{
+			  edge e;
+
+			  degree[child] = -1;
+			  rgn_bb_table[idx++] = child;
+			  BLOCK_TO_BB (child) = ++count;
+			  CONTAINING_RGN (child) = nr_regions;
+			  queue[head] = queue[tail--];
+
+			  FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs)
+			    if (e->dest != EXIT_BLOCK_PTR)
+			      --degree[e->dest->index];
+			}
+		      else
+			--head;
+		    }
+		  ++nr_regions;
+		}
+              else if (extend_regions_p)
+                {
+                  /* Restore DEGREE.  */
+                  int *t = degree;
+
+                  degree = degree1;
+                  degree1 = t;
+                  
+                  /* And force successors of BB to be region heads.
+		     This may provide several smaller regions instead
+		     of one too_large region.  */
+                  FOR_EACH_EDGE (e, ei, bb->succs)
+                    if (e->dest != EXIT_BLOCK_PTR)
+                      SET_BIT (extended_rgn_header, e->dest->index);
+                }
+	    }
+	}
+      free (queue);
+
+      if (extend_regions_p)
+        {
+          free (degree1);
+          
+          sbitmap_a_or_b (header, header, extended_rgn_header);
+          sbitmap_free (extended_rgn_header);
+ 
+          extend_rgns (degree, &idx, header, max_hdr);
+        }
+    }
+
+  /* Any block that did not end up in a region is placed into a region
+     by itself.  */
+  FOR_EACH_BB (bb)
+    if (degree[bb->index] >= 0)
+      {
+	rgn_bb_table[idx] = bb->index;
+	RGN_NR_BLOCKS (nr_regions) = 1;
+	RGN_BLOCKS (nr_regions) = idx++;
+        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;
+      }
+
+  free (max_hdr);
+  free (degree);
+  free (stack);
+  sbitmap_free (header);
+  sbitmap_free (inner);
+  sbitmap_free (in_queue);
+  sbitmap_free (in_stack);
+}
+
+
+/* Wrapper function.
+   If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
+   regions.  Otherwise just call find_rgns_haifa.  */
+static void
+find_rgns (void)
+{
+  if (sel_sched_p () && flag_sel_sched_pipelining)
+    sel_find_rgns ();
+  else
+    haifa_find_rgns ();
+}
+
+static int gather_region_statistics (int **);
+static void print_region_statistics (int *, int, int *, int);
+
+/* Calculate the histogram that shows the number of regions having the 
+   given number of basic blocks, and store it in the RSP array.  Return 
+   the size of this array.  */
+static int
+gather_region_statistics (int **rsp)
+{
+  int i, *a = 0, a_sz = 0;
+
+  /* a[i] is the number of regions that have (i + 1) basic blocks.  */
+  for (i = 0; i < nr_regions; i++)
+    {
+      int nr_blocks = RGN_NR_BLOCKS (i);
+
+      gcc_assert (nr_blocks >= 1);
+
+      if (nr_blocks > a_sz)
+	{	 
+	  a = XRESIZEVEC (int, a, nr_blocks);
+	  do
+	    a[a_sz++] = 0;
+	  while (a_sz != nr_blocks);
+	}
+
+      a[nr_blocks - 1]++;
+    }
+
+  *rsp = a;
+  return a_sz;
+}
+
+/* Print regions statistics.  S1 and S2 denote the data before and after 
+   calling extend_rgns, respectively.  */
+static void
+print_region_statistics (int *s1, int s1_sz, int *s2, int s2_sz)
+{
+  int i;
+  
+  /* We iterate until s2_sz because extend_rgns does not decrease 
+     the maximal region size.  */
+  for (i = 1; i < s2_sz; i++)
+    {
+      int n1, n2;
+
+      n2 = s2[i];
+
+      if (n2 == 0)
+	continue;
+
+      if (i >= s1_sz)
+	n1 = 0;
+      else
+	n1 = s1[i];
+
+      fprintf (sched_dump, ";; Region extension statistics: size %d: " \
+	       "was %d + %d more\n", i + 1, n1, n2 - n1);
+    }
+}
+
+/* Extend regions.
+   DEGREE - Array of incoming edge count, considering only
+   the edges, that don't have their sources in formed regions yet.
+   IDXP - pointer to the next available index in rgn_bb_table.
+   HEADER - set of all region heads.
+   LOOP_HDR - mapping from block to the containing loop
+   (two blocks can reside within one region if they have
+   the same loop header).  */
+void
+extend_rgns (int *degree, int *idxp, sbitmap header, int *loop_hdr)
+{
+  int *order, i, rescan = 0, idx = *idxp, iter = 0, max_iter, *max_hdr;
+  int nblocks = n_basic_blocks - NUM_FIXED_BLOCKS;
+
+  max_iter = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS);
+
+  max_hdr = XNEWVEC (int, last_basic_block);
+
+  order = XNEWVEC (int, last_basic_block);
+  post_order_compute (order, false, false);
+
+  for (i = nblocks - 1; i >= 0; i--)
+    {
+      int bbn = order[i];
+      if (degree[bbn] >= 0)
+	{
+	  max_hdr[bbn] = bbn;
+	  rescan = 1;
+	}
+      else
+        /* This block already was processed in find_rgns.  */
+        max_hdr[bbn] = -1;
+    }
+  
+  /* The idea is to topologically walk through CFG in top-down order.
+     During the traversal, if all the predecessors of a node are
+     marked to be in the same region (they all have the same max_hdr),
+     then current node is also marked to be a part of that region. 
+     Otherwise the node starts its own region.
+     CFG should be traversed until no further changes are made.  On each 
+     iteration the set of the region heads is extended (the set of those 
+     blocks that have max_hdr[bbi] == bbi).  This set is upper bounded by the 
+     set of all basic blocks, thus the algorithm is guaranteed to
+     terminate.  */
+
+  while (rescan && iter < max_iter)
+    {
+      rescan = 0;
+      
+      for (i = nblocks - 1; i >= 0; i--)
+	{
+	  edge e;
+	  edge_iterator ei;
+	  int bbn = order[i];
+	
+	  if (max_hdr[bbn] != -1 && !TEST_BIT (header, bbn))
+	    {
+	      int hdr = -1;
+
+	      FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->preds)
+		{
+		  int predn = e->src->index;
+
+		  if (predn != ENTRY_BLOCK
+		      /* If pred wasn't processed in find_rgns.  */
+		      && max_hdr[predn] != -1
+		      /* And pred and bb reside in the same loop.
+			 (Or out of any loop).  */
+		      && loop_hdr[bbn] == loop_hdr[predn])
+		    {
+		      if (hdr == -1)
+			/* Then bb extends the containing region of pred.  */
+			hdr = max_hdr[predn];
+		      else if (hdr != max_hdr[predn])
+			/* Too bad, there are at least two predecessors
+			   that reside in different regions.  Thus, BB should
+			   begin its own region.  */
+			{
+			  hdr = bbn;
+			  break;
+			}		    
+		    }
+		  else
+		    /* BB starts its own region.  */
+		    {
+		      hdr = bbn;
+		      break;
+		    }		
+		}
+	    
+	      if (hdr == bbn)
+		{
+		  /* If BB start its own region,
+		     update set of headers with BB.  */
+		  SET_BIT (header, bbn);
+		  rescan = 1;
+		}
+	      else
+		gcc_assert (hdr != -1);	    
+
+	      max_hdr[bbn] = hdr;
+	    }
+	}
+
+      iter++;
+    }
+  
+  /* Statistics were gathered on the SPEC2000 package of tests with
+     mainline weekly snapshot gcc-4.1-20051015 on ia64.
+     
+     Statistics for SPECint:
+     1 iteration : 1751 cases (38.7%)
+     2 iterations: 2770 cases (61.3%)
+     Blocks wrapped in regions by find_rgns without extension: 18295 blocks
+     Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
+     (We don't count single block regions here).
+     
+     Statistics for SPECfp:
+     1 iteration : 621 cases (35.9%)
+     2 iterations: 1110 cases (64.1%)
+     Blocks wrapped in regions by find_rgns without extension: 6476 blocks
+     Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
+     (We don't count single block regions here).
+
+     By default we do at most 2 iterations.
+     This can be overridden with max-sched-extend-regions-iters parameter:
+     0 - disable region extension,
+     N > 0 - do at most N iterations.  */
+  
+  if (sched_verbose && iter != 0)
+    fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
+	     rescan ? "... failed" : "");
+    
+  if (!rescan && iter != 0)
+    {
+      int *s1 = NULL, s1_sz = 0;
+
+      /* Save the old statistics for later printout.  */
+      if (sched_verbose >= 6)
+	s1_sz = gather_region_statistics (&s1);
+
+      /* We have succeeded.  Now assemble the regions.  */
+      for (i = nblocks - 1; i >= 0; i--)
+	{
+	  int bbn = order[i];
+
+	  if (max_hdr[bbn] == bbn)
+	    /* BBN is a region head.  */
+	    {
+	      edge e;
+	      edge_iterator ei;
+	      int num_bbs = 0, j, num_insns = 0, large;
+	
+	      large = too_large (bbn, &num_bbs, &num_insns);
+
+	      degree[bbn] = -1;
+	      rgn_bb_table[idx] = bbn;
+	      RGN_BLOCKS (nr_regions) = idx++;
+	      RGN_DONT_CALC_DEPS (nr_regions) = 0;
+	      RGN_HAS_REAL_EBB (nr_regions) = 0;
+	      CONTAINING_RGN (bbn) = nr_regions;
+	      BLOCK_TO_BB (bbn) = 0;
+
+	      FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->succs)
+		if (e->dest != EXIT_BLOCK_PTR)
+		  degree[e->dest->index]--;
+
+	      if (!large)
+		/* Here we check whether the region is too_large.  */
+		for (j = i - 1; j >= 0; j--)
+		  {
+		    int succn = order[j];
+		    if (max_hdr[succn] == bbn)
+		      {
+			if ((large = too_large (succn, &num_bbs, &num_insns)))
+			  break;
+		      }
+		  }
+
+	      if (large)
+		/* If the region is too_large, then wrap every block of
+		   the region into single block region.
+		   Here we wrap region head only.  Other blocks are
+		   processed in the below cycle.  */
+		{
+		  RGN_NR_BLOCKS (nr_regions) = 1;
+		  nr_regions++;
+		}          
+
+	      num_bbs = 1;
+
+	      for (j = i - 1; j >= 0; j--)
+		{
+		  int succn = order[j];
+
+		  if (max_hdr[succn] == bbn)
+		    /* This cycle iterates over all basic blocks, that 
+		       are supposed to be in the region with head BBN,
+		       and wraps them into that region (or in single
+		       block region).  */
+		    {
+		      gcc_assert (degree[succn] == 0);
+
+		      degree[succn] = -1;
+		      rgn_bb_table[idx] = succn;		 
+		      BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
+		      CONTAINING_RGN (succn) = nr_regions;
+
+		      if (large)
+			/* Wrap SUCCN into single block region.  */
+			{
+			  RGN_BLOCKS (nr_regions) = idx;
+			  RGN_NR_BLOCKS (nr_regions) = 1;
+			  RGN_DONT_CALC_DEPS (nr_regions) = 0;
+			  RGN_HAS_REAL_EBB (nr_regions) = 0;
+			  nr_regions++;
+			}
+
+		      idx++;
+				
+		      FOR_EACH_EDGE (e, ei, BASIC_BLOCK (succn)->succs)
+			if (e->dest != EXIT_BLOCK_PTR)
+			  degree[e->dest->index]--;
+		    }
+		}
+
+	      if (!large)
+		{
+		  RGN_NR_BLOCKS (nr_regions) = num_bbs;
+		  nr_regions++;
+		}
+	    }
+	}
+
+      if (sched_verbose >= 6)
+	{
+	  int *s2, s2_sz;
+
+          /* Get the new statistics and print the comparison with the 
+             one before calling this function.  */
+	  s2_sz = gather_region_statistics (&s2);
+	  print_region_statistics (s1, s1_sz, s2, s2_sz);
+	  free (s1);
+	  free (s2);
+	}
+    }
+  
+  free (order);
+  free (max_hdr);
+
+  *idxp = idx; 
+}
+
+/* Functions for regions scheduling information.  */
+
+/* Compute dominators, probability, and potential-split-edges of bb.
+   Assume that these values were already computed for bb's predecessors.  */
+
+static void
+compute_dom_prob_ps (int bb)
+{
+  edge_iterator in_ei;
+  edge in_edge;
+
+  /* We shouldn't have any real ebbs yet.  */
+  gcc_assert (ebb_head [bb] == bb + current_blocks);
+  
+  if (IS_RGN_ENTRY (bb))
+    {
+      SET_BIT (dom[bb], 0);
+      prob[bb] = REG_BR_PROB_BASE;
+      return;
+    }
+
+  prob[bb] = 0;
+
+  /* Initialize dom[bb] to '111..1'.  */
+  sbitmap_ones (dom[bb]);
+
+  FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
+    {
+      int pred_bb;
+      edge out_edge;
+      edge_iterator out_ei;
+
+      if (in_edge->src == ENTRY_BLOCK_PTR)
+	continue;
+
+      pred_bb = BLOCK_TO_BB (in_edge->src->index);
+      sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]);
+      sbitmap_a_or_b (ancestor_edges[bb],
+		      ancestor_edges[bb], ancestor_edges[pred_bb]);
+
+      SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
+
+      sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
+
+      FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
+	SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
+
+      prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
+    }
+
+  SET_BIT (dom[bb], bb);
+  sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
+
+  if (sched_verbose >= 2)
+    fprintf (sched_dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
+	     (100 * prob[bb]) / REG_BR_PROB_BASE);
+}
+
+/* Functions for target info.  */
+
+/* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
+   Note that bb_trg dominates bb_src.  */
+
+static void
+split_edges (int bb_src, int bb_trg, edgelst *bl)
+{
+  sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
+  sbitmap_copy (src, pot_split[bb_src]);
+
+  sbitmap_difference (src, src, pot_split[bb_trg]);
+  extract_edgelst (src, bl);
+  sbitmap_free (src);
+}
+
+/* Find the valid candidate-source-blocks for the target block TRG, compute
+   their probability, and check if they are speculative or not.
+   For speculative sources, compute their update-blocks and split-blocks.  */
+
+static void
+compute_trg_info (int trg)
+{
+  candidate *sp;
+  edgelst el = { NULL, 0 };
+  int i, j, k, update_idx;
+  basic_block block;
+  sbitmap visited;
+  edge_iterator ei;
+  edge e;
+
+  candidate_table = XNEWVEC (candidate, current_nr_blocks);
+
+  bblst_last = 0;
+  /* bblst_table holds split blocks and update blocks for each block after
+     the current one in the region.  split blocks and update blocks are
+     the TO blocks of region edges, so there can be at most rgn_nr_edges
+     of them.  */
+  bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
+  bblst_table = XNEWVEC (basic_block, bblst_size);
+
+  edgelst_last = 0;
+  edgelst_table = XNEWVEC (edge, rgn_nr_edges);
+
+  /* Define some of the fields for the target bb as well.  */
+  sp = candidate_table + trg;
+  sp->is_valid = 1;
+  sp->is_speculative = 0;
+  sp->src_prob = REG_BR_PROB_BASE;
+
+  visited = sbitmap_alloc (last_basic_block);
+
+  for (i = trg + 1; i < current_nr_blocks; i++)
+    {
+      sp = candidate_table + i;
+
+      sp->is_valid = IS_DOMINATED (i, trg);
+      if (sp->is_valid)
+	{
+	  int tf = prob[trg], cf = prob[i];
+
+	  /* In CFGs with low probability edges TF can possibly be zero.  */
+	  sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
+	  sp->is_valid = (sp->src_prob >= min_spec_prob);
+	}
+
+      if (sp->is_valid)
+	{
+	  split_edges (i, trg, &el);
+	  sp->is_speculative = (el.nr_members) ? 1 : 0;
+	  if (sp->is_speculative && !flag_schedule_speculative)
+	    sp->is_valid = 0;
+	}
+
+      if (sp->is_valid)
+	{
+	  /* Compute split blocks and store them in bblst_table.
+	     The TO block of every split edge is a split block.  */
+	  sp->split_bbs.first_member = &bblst_table[bblst_last];
+	  sp->split_bbs.nr_members = el.nr_members;
+	  for (j = 0; j < el.nr_members; bblst_last++, j++)
+	    bblst_table[bblst_last] = el.first_member[j]->dest;
+	  sp->update_bbs.first_member = &bblst_table[bblst_last];
+
+	  /* Compute update blocks and store them in bblst_table.
+	     For every split edge, look at the FROM block, and check
+	     all out edges.  For each out edge that is not a split edge,
+	     add the TO block to the update block list.  This list can end
+	     up with a lot of duplicates.  We need to weed them out to avoid
+	     overrunning the end of the bblst_table.  */
+
+	  update_idx = 0;
+	  sbitmap_zero (visited);
+	  for (j = 0; j < el.nr_members; j++)
+	    {
+	      block = el.first_member[j]->src;
+	      FOR_EACH_EDGE (e, ei, block->succs)
+		{
+		  if (!TEST_BIT (visited, e->dest->index))
+		    {
+		      for (k = 0; k < el.nr_members; k++)
+			if (e == el.first_member[k])
+			  break;
+
+		      if (k >= el.nr_members)
+			{
+			  bblst_table[bblst_last++] = e->dest;
+			  SET_BIT (visited, e->dest->index);
+			  update_idx++;
+			}
+		    }
+		}
+	    }
+	  sp->update_bbs.nr_members = update_idx;
+
+	  /* Make sure we didn't overrun the end of bblst_table.  */
+	  gcc_assert (bblst_last <= bblst_size);
+	}
+      else
+	{
+	  sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
+
+	  sp->is_speculative = 0;
+	  sp->src_prob = 0;
+	}
+    }
+
+  sbitmap_free (visited);
+}
+
+/* Free the computed target info.  */
+static void
+free_trg_info (void)
+{
+  free (candidate_table);
+  free (bblst_table);
+  free (edgelst_table);
+}
+
+/* Print candidates info, for debugging purposes.  Callable from debugger.  */
+
+void
+debug_candidate (int i)
+{
+  if (!candidate_table[i].is_valid)
+    return;
+
+  if (candidate_table[i].is_speculative)
+    {
+      int j;
+      fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
+
+      fprintf (sched_dump, "split path: ");
+      for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
+	{
+	  int b = candidate_table[i].split_bbs.first_member[j]->index;
+
+	  fprintf (sched_dump, " %d ", b);
+	}
+      fprintf (sched_dump, "\n");
+
+      fprintf (sched_dump, "update path: ");
+      for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
+	{
+	  int b = candidate_table[i].update_bbs.first_member[j]->index;
+
+	  fprintf (sched_dump, " %d ", b);
+	}
+      fprintf (sched_dump, "\n");
+    }
+  else
+    {
+      fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
+    }
+}
+
+/* Print candidates info, for debugging purposes.  Callable from debugger.  */
+
+void
+debug_candidates (int trg)
+{
+  int i;
+
+  fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
+	   BB_TO_BLOCK (trg), trg);
+  for (i = trg + 1; i < current_nr_blocks; i++)
+    debug_candidate (i);
+}
+
+/* Functions for speculative scheduling.  */
+
+static bitmap_head not_in_df;
+
+/* Return 0 if x is a set of a register alive in the beginning of one
+   of the split-blocks of src, otherwise return 1.  */
+
+static int
+check_live_1 (int src, rtx x)
+{
+  int i;
+  int regno;
+  rtx reg = SET_DEST (x);
+
+  if (reg == 0)
+    return 1;
+
+  while (GET_CODE (reg) == SUBREG
+	 || GET_CODE (reg) == ZERO_EXTRACT
+	 || GET_CODE (reg) == STRICT_LOW_PART)
+    reg = XEXP (reg, 0);
+
+  if (GET_CODE (reg) == PARALLEL)
+    {
+      int i;
+
+      for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
+	if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
+	  if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
+	    return 1;
+
+      return 0;
+    }
+
+  if (!REG_P (reg))
+    return 1;
+
+  regno = REGNO (reg);
+
+  if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
+    {
+      /* Global registers are assumed live.  */
+      return 0;
+    }
+  else
+    {
+      if (regno < FIRST_PSEUDO_REGISTER)
+	{
+	  /* Check for hard registers.  */
+	  int j = hard_regno_nregs[regno][GET_MODE (reg)];
+	  while (--j >= 0)
+	    {
+	      for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
+		{
+		  basic_block b = candidate_table[src].split_bbs.first_member[i];
+		  int t = bitmap_bit_p (&not_in_df, b->index);
+
+		  /* We can have split blocks, that were recently generated.
+		     Such blocks are always outside current region.  */
+		  gcc_assert (!t || (CONTAINING_RGN (b->index)
+				     != CONTAINING_RGN (BB_TO_BLOCK (src))));
+
+		  if (t || REGNO_REG_SET_P (df_get_live_in (b), regno + j))
+		    return 0;
+		}
+	    }
+	}
+      else
+	{
+	  /* Check for pseudo registers.  */
+	  for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
+	    {
+	      basic_block b = candidate_table[src].split_bbs.first_member[i];
+	      int t = bitmap_bit_p (&not_in_df, b->index);
+
+	      gcc_assert (!t || (CONTAINING_RGN (b->index)
+				 != CONTAINING_RGN (BB_TO_BLOCK (src))));
+
+	      if (t || REGNO_REG_SET_P (df_get_live_in (b), regno))
+		return 0;
+	    }
+	}
+    }
+
+  return 1;
+}
+
+/* If x is a set of a register R, mark that R is alive in the beginning
+   of every update-block of src.  */
+
+static void
+update_live_1 (int src, rtx x)
+{
+  int i;
+  int regno;
+  rtx reg = SET_DEST (x);
+
+  if (reg == 0)
+    return;
+
+  while (GET_CODE (reg) == SUBREG
+	 || GET_CODE (reg) == ZERO_EXTRACT
+	 || GET_CODE (reg) == STRICT_LOW_PART)
+    reg = XEXP (reg, 0);
+
+  if (GET_CODE (reg) == PARALLEL)
+    {
+      int i;
+
+      for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
+	if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
+	  update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
+
+      return;
+    }
+
+  if (!REG_P (reg))
+    return;
+
+  /* Global registers are always live, so the code below does not apply
+     to them.  */
+
+  regno = REGNO (reg);
+
+  if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
+    {
+      if (regno < FIRST_PSEUDO_REGISTER)
+	{
+	  int j = hard_regno_nregs[regno][GET_MODE (reg)];
+	  while (--j >= 0)
+	    {
+	      for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
+		{
+		  basic_block b = candidate_table[src].update_bbs.first_member[i];
+
+		  SET_REGNO_REG_SET (df_get_live_in (b), regno + j);
+		}
+	    }
+	}
+      else
+	{
+	  for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
+	    {
+	      basic_block b = candidate_table[src].update_bbs.first_member[i];
+
+	      SET_REGNO_REG_SET (df_get_live_in (b), regno);
+	    }
+	}
+    }
+}
+
+/* Return 1 if insn can be speculatively moved from block src to trg,
+   otherwise return 0.  Called before first insertion of insn to
+   ready-list or before the scheduling.  */
+
+static int
+check_live (rtx insn, int src)
+{
+  /* Find the registers set by instruction.  */
+  if (GET_CODE (PATTERN (insn)) == SET
+      || GET_CODE (PATTERN (insn)) == CLOBBER)
+    return check_live_1 (src, PATTERN (insn));
+  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+    {
+      int j;
+      for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
+	if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
+	     || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
+	    && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
+	  return 0;
+
+      return 1;
+    }
+
+  return 1;
+}
+
+/* Update the live registers info after insn was moved speculatively from
+   block src to trg.  */
+
+static void
+update_live (rtx insn, int src)
+{
+  /* Find the registers set by instruction.  */
+  if (GET_CODE (PATTERN (insn)) == SET
+      || GET_CODE (PATTERN (insn)) == CLOBBER)
+    update_live_1 (src, PATTERN (insn));
+  else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+    {
+      int j;
+      for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
+	if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
+	    || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
+	  update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
+    }
+}
+
+/* Nonzero if block bb_to is equal to, or reachable from block bb_from.  */
+#define IS_REACHABLE(bb_from, bb_to)					\
+  (bb_from == bb_to							\
+   || IS_RGN_ENTRY (bb_from)						\
+   || (TEST_BIT (ancestor_edges[bb_to],					\
+	 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from)))))))
+
+/* Turns on the fed_by_spec_load flag for insns fed by load_insn.  */
+
+static void
+set_spec_fed (rtx load_insn)
+{
+  sd_iterator_def sd_it;
+  dep_t dep;
+
+  FOR_EACH_DEP (load_insn, SD_LIST_FORW, sd_it, dep)
+    if (DEP_TYPE (dep) == REG_DEP_TRUE)
+      FED_BY_SPEC_LOAD (DEP_CON (dep)) = 1;
+}
+
+/* On the path from the insn to load_insn_bb, find a conditional
+branch depending on insn, that guards the speculative load.  */
+
+static int
+find_conditional_protection (rtx insn, int load_insn_bb)
+{
+  sd_iterator_def sd_it;
+  dep_t dep;
+
+  /* Iterate through DEF-USE forward dependences.  */
+  FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+    {
+      rtx next = DEP_CON (dep);
+
+      if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
+	   CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
+	  && IS_REACHABLE (INSN_BB (next), load_insn_bb)
+	  && load_insn_bb != INSN_BB (next)
+	  && DEP_TYPE (dep) == REG_DEP_TRUE
+	  && (JUMP_P (next)
+	      || find_conditional_protection (next, load_insn_bb)))
+	return 1;
+    }
+  return 0;
+}				/* find_conditional_protection */
+
+/* Returns 1 if the same insn1 that participates in the computation
+   of load_insn's address is feeding a conditional branch that is
+   guarding on load_insn. This is true if we find two DEF-USE
+   chains:
+   insn1 -> ... -> conditional-branch
+   insn1 -> ... -> load_insn,
+   and if a flow path exists:
+   insn1 -> ... -> conditional-branch -> ... -> load_insn,
+   and if insn1 is on the path
+   region-entry -> ... -> bb_trg -> ... load_insn.
+
+   Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
+   Locate the branch by following INSN_FORW_DEPS from insn1.  */
+
+static int
+is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg)
+{
+  sd_iterator_def sd_it;
+  dep_t dep;
+
+  FOR_EACH_DEP (load_insn, SD_LIST_BACK, sd_it, dep)
+    {
+      rtx insn1 = DEP_PRO (dep);
+
+      /* Must be a DEF-USE dependence upon non-branch.  */
+      if (DEP_TYPE (dep) != REG_DEP_TRUE
+	  || JUMP_P (insn1))
+	continue;
+
+      /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  */
+      if (INSN_BB (insn1) == bb_src
+	  || (CONTAINING_RGN (BLOCK_NUM (insn1))
+	      != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
+	  || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
+	      && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
+	continue;
+
+      /* Now search for the conditional-branch.  */
+      if (find_conditional_protection (insn1, bb_src))
+	return 1;
+
+      /* Recursive step: search another insn1, "above" current insn1.  */
+      return is_conditionally_protected (insn1, bb_src, bb_trg);
+    }
+
+  /* The chain does not exist.  */
+  return 0;
+}				/* is_conditionally_protected */
+
+/* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
+   load_insn can move speculatively from bb_src to bb_trg.  All the
+   following must hold:
+
+   (1) both loads have 1 base register (PFREE_CANDIDATEs).
+   (2) load_insn and load1 have a def-use dependence upon
+   the same insn 'insn1'.
+   (3) either load2 is in bb_trg, or:
+   - there's only one split-block, and
+   - load1 is on the escape path, and
+
+   From all these we can conclude that the two loads access memory
+   addresses that differ at most by a constant, and hence if moving
+   load_insn would cause an exception, it would have been caused by
+   load2 anyhow.  */
+
+static int
+is_pfree (rtx load_insn, int bb_src, int bb_trg)
+{
+  sd_iterator_def back_sd_it;
+  dep_t back_dep;
+  candidate *candp = candidate_table + bb_src;
+
+  if (candp->split_bbs.nr_members != 1)
+    /* Must have exactly one escape block.  */
+    return 0;
+
+  FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
+    {
+      rtx insn1 = DEP_PRO (back_dep);
+
+      if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
+	/* Found a DEF-USE dependence (insn1, load_insn).  */
+	{
+	  sd_iterator_def fore_sd_it;
+	  dep_t fore_dep;
+
+	  FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
+	    {
+	      rtx insn2 = DEP_CON (fore_dep);
+
+	      if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
+		{
+		  /* Found a DEF-USE dependence (insn1, insn2).  */
+		  if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
+		    /* insn2 not guaranteed to be a 1 base reg load.  */
+		    continue;
+
+		  if (INSN_BB (insn2) == bb_trg)
+		    /* insn2 is the similar load, in the target block.  */
+		    return 1;
+
+		  if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2))
+		    /* insn2 is a similar load, in a split-block.  */
+		    return 1;
+		}
+	    }
+	}
+    }
+
+  /* Couldn't find a similar load.  */
+  return 0;
+}				/* is_pfree */
+
+/* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
+   a load moved speculatively, or if load_insn is protected by
+   a compare on load_insn's address).  */
+
+static int
+is_prisky (rtx load_insn, int bb_src, int bb_trg)
+{
+  if (FED_BY_SPEC_LOAD (load_insn))
+    return 1;
+
+  if (sd_lists_empty_p (load_insn, SD_LIST_BACK))
+    /* Dependence may 'hide' out of the region.  */
+    return 1;
+
+  if (is_conditionally_protected (load_insn, bb_src, bb_trg))
+    return 1;
+
+  return 0;
+}
+
+/* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
+   Return 1 if insn is exception-free (and the motion is valid)
+   and 0 otherwise.  */
+
+static int
+is_exception_free (rtx insn, int bb_src, int bb_trg)
+{
+  int insn_class = haifa_classify_insn (insn);
+
+  /* Handle non-load insns.  */
+  switch (insn_class)
+    {
+    case TRAP_FREE:
+      return 1;
+    case TRAP_RISKY:
+      return 0;
+    default:;
+    }
+
+  /* Handle loads.  */
+  if (!flag_schedule_speculative_load)
+    return 0;
+  IS_LOAD_INSN (insn) = 1;
+  switch (insn_class)
+    {
+    case IFREE:
+      return (1);
+    case IRISKY:
+      return 0;
+    case PFREE_CANDIDATE:
+      if (is_pfree (insn, bb_src, bb_trg))
+	return 1;
+      /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  */
+    case PRISKY_CANDIDATE:
+      if (!flag_schedule_speculative_load_dangerous
+	  || is_prisky (insn, bb_src, bb_trg))
+	return 0;
+      break;
+    default:;
+    }
+
+  return flag_schedule_speculative_load_dangerous;
+}
+
+/* The number of insns from the current block scheduled so far.  */
+static int sched_target_n_insns;
+/* The number of insns from the current block to be scheduled in total.  */
+static int target_n_insns;
+/* The number of insns from the entire region scheduled so far.  */
+static int sched_n_insns;
+
+/* Implementations of the sched_info functions for region scheduling.  */
+static void init_ready_list (void);
+static int can_schedule_ready_p (rtx);
+static void begin_schedule_ready (rtx, rtx);
+static ds_t new_ready (rtx, ds_t);
+static int schedule_more_p (void);
+static const char *rgn_print_insn (const_rtx, int);
+static int rgn_rank (rtx, rtx);
+static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
+
+/* Functions for speculative scheduling.  */
+static void rgn_add_remove_insn (rtx, int);
+static void rgn_add_block (basic_block, basic_block);
+static void rgn_fix_recovery_cfg (int, int, int);
+static basic_block advance_target_bb (basic_block, rtx);
+
+/* Return nonzero if there are more insns that should be scheduled.  */
+
+static int
+schedule_more_p (void)
+{
+  return sched_target_n_insns < target_n_insns;
+}
+
+/* Add all insns that are initially ready to the ready list READY.  Called
+   once before scheduling a set of insns.  */
+
+static void
+init_ready_list (void)
+{
+  rtx prev_head = current_sched_info->prev_head;
+  rtx next_tail = current_sched_info->next_tail;
+  int bb_src;
+  rtx insn;
+
+  target_n_insns = 0;
+  sched_target_n_insns = 0;
+  sched_n_insns = 0;
+
+  /* Print debugging information.  */
+  if (sched_verbose >= 5)
+    debug_rgn_dependencies (target_bb);
+
+  /* Prepare current target block info.  */
+  if (current_nr_blocks > 1)
+    compute_trg_info (target_bb);
+
+  /* Initialize ready list with all 'ready' insns in target block.
+     Count number of insns in the target block being scheduled.  */
+  for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
+    {      
+      try_ready (insn);
+      target_n_insns++;
+
+      gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
+    }
+
+  /* Add to ready list all 'ready' insns in valid source blocks.
+     For speculative insns, check-live, exception-free, and
+     issue-delay.  */
+  for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
+    if (IS_VALID (bb_src))
+      {
+	rtx src_head;
+	rtx src_next_tail;
+	rtx tail, head;
+
+	get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
+			   &head, &tail);
+	src_next_tail = NEXT_INSN (tail);
+	src_head = head;
+
+	for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
+	  if (INSN_P (insn))
+	    try_ready (insn);
+      }
+}
+
+/* Called after taking INSN from the ready list.  Returns nonzero if this
+   insn can be scheduled, nonzero if we should silently discard it.  */
+
+static int
+can_schedule_ready_p (rtx insn)
+{
+  /* An interblock motion?  */
+  if (INSN_BB (insn) != target_bb
+      && IS_SPECULATIVE_INSN (insn)
+      && !check_live (insn, INSN_BB (insn)))
+    return 0;          
+  else
+    return 1;
+}
+
+/* Updates counter and other information.  Split from can_schedule_ready_p ()
+   because when we schedule insn speculatively then insn passed to
+   can_schedule_ready_p () differs from the one passed to
+   begin_schedule_ready ().  */
+static void
+begin_schedule_ready (rtx insn, rtx last ATTRIBUTE_UNUSED)
+{
+  /* An interblock motion?  */
+  if (INSN_BB (insn) != target_bb)
+    {
+      if (IS_SPECULATIVE_INSN (insn))
+	{
+	  gcc_assert (check_live (insn, INSN_BB (insn)));
+
+	  update_live (insn, INSN_BB (insn));
+
+	  /* For speculative load, mark insns fed by it.  */
+	  if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
+	    set_spec_fed (insn);
+
+	  nr_spec++;
+	}
+      nr_inter++;
+    }
+  else
+    {
+      /* In block motion.  */
+      sched_target_n_insns++;
+    }
+  sched_n_insns++;
+}
+
+/* Called after INSN has all its hard dependencies resolved and the speculation
+   of type TS is enough to overcome them all.
+   Return nonzero if it should be moved to the ready list or the queue, or zero
+   if we should silently discard it.  */
+static ds_t
+new_ready (rtx next, ds_t ts)
+{
+  if (INSN_BB (next) != target_bb)
+    {
+      int not_ex_free = 0;
+
+      /* For speculative insns, before inserting to ready/queue,
+	 check live, exception-free, and issue-delay.  */	
+      if (!IS_VALID (INSN_BB (next))
+	  || CANT_MOVE (next)
+	  || (IS_SPECULATIVE_INSN (next)
+	      && ((recog_memoized (next) >= 0
+		   && min_insn_conflict_delay (curr_state, next, next) 
+                   > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
+                  || IS_SPECULATION_CHECK_P (next)
+		  || !check_live (next, INSN_BB (next))
+		  || (not_ex_free = !is_exception_free (next, INSN_BB (next),
+							target_bb)))))
+	{
+	  if (not_ex_free
+	      /* We are here because is_exception_free () == false.
+		 But we possibly can handle that with control speculation.  */
+	      && sched_deps_info->generate_spec_deps
+	      && spec_info->mask & BEGIN_CONTROL)
+	    {
+	      ds_t new_ds;
+
+	      /* Add control speculation to NEXT's dependency type.  */
+	      new_ds = set_dep_weak (ts, BEGIN_CONTROL, MAX_DEP_WEAK);
+
+	      /* Check if NEXT can be speculated with new dependency type.  */
+	      if (sched_insn_is_legitimate_for_speculation_p (next, new_ds))
+		/* Here we got new control-speculative instruction.  */
+		ts = new_ds;
+	      else
+		/* NEXT isn't ready yet.  */
+		ts = (ts & ~SPECULATIVE) | HARD_DEP;
+	    }
+	  else
+	    /* NEXT isn't ready yet.  */
+            ts = (ts & ~SPECULATIVE) | HARD_DEP;
+	}
+    }
+  
+  return ts;
+}
+
+/* Return a string that contains the insn uid and optionally anything else
+   necessary to identify this insn in an output.  It's valid to use a
+   static buffer for this.  The ALIGNED parameter should cause the string
+   to be formatted so that multiple output lines will line up nicely.  */
+
+static const char *
+rgn_print_insn (const_rtx insn, int aligned)
+{
+  static char tmp[80];
+
+  if (aligned)
+    sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
+  else
+    {
+      if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
+	sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
+      else
+	sprintf (tmp, "%d", INSN_UID (insn));
+    }
+  return tmp;
+}
+
+/* Compare priority of two insns.  Return a positive number if the second
+   insn is to be preferred for scheduling, and a negative one if the first
+   is to be preferred.  Zero if they are equally good.  */
+
+static int
+rgn_rank (rtx insn1, rtx insn2)
+{
+  /* Some comparison make sense in interblock scheduling only.  */
+  if (INSN_BB (insn1) != INSN_BB (insn2))
+    {
+      int spec_val, prob_val;
+
+      /* Prefer an inblock motion on an interblock motion.  */
+      if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
+	return 1;
+      if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
+	return -1;
+
+      /* Prefer a useful motion on a speculative one.  */
+      spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
+      if (spec_val)
+	return spec_val;
+
+      /* Prefer a more probable (speculative) insn.  */
+      prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
+      if (prob_val)
+	return prob_val;
+    }
+  return 0;
+}
+
+/* NEXT is an instruction that depends on INSN (a backward dependence);
+   return nonzero if we should include this dependence in priority
+   calculations.  */
+
+int
+contributes_to_priority (rtx next, rtx insn)
+{
+  /* NEXT and INSN reside in one ebb.  */
+  return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
+}
+
+/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
+   conditionally set before INSN.  Store the set of registers that
+   must be considered as used by this jump in USED and that of
+   registers that must be considered as set in SET.  */
+
+static void
+compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
+			       regset cond_exec ATTRIBUTE_UNUSED,
+			       regset used ATTRIBUTE_UNUSED,
+			       regset set ATTRIBUTE_UNUSED)
+{
+  /* Nothing to do here, since we postprocess jumps in
+     add_branch_dependences.  */
+}
+
+/* This variable holds common_sched_info hooks and data relevant to 
+   the interblock scheduler.  */
+static struct common_sched_info_def rgn_common_sched_info;
+
+
+/* This holds data for the dependence analysis relevant to
+   the interblock scheduler.  */
+static struct sched_deps_info_def rgn_sched_deps_info;
+
+/* This holds constant data used for initializing the above structure
+   for the Haifa scheduler.  */
+static const struct sched_deps_info_def rgn_const_sched_deps_info =
+  {
+    compute_jump_reg_dependencies,
+    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
+    0, 0, 0
+  };
+
+/* Same as above, but for the selective scheduler.  */
+static const struct sched_deps_info_def rgn_const_sel_sched_deps_info =
+  {
+    compute_jump_reg_dependencies,
+    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
+    0, 0, 0
+  };
+
+/* Used in schedule_insns to initialize current_sched_info for scheduling
+   regions (or single basic blocks).  */
+
+static const struct haifa_sched_info rgn_const_sched_info =
+{
+  init_ready_list,
+  can_schedule_ready_p,
+  schedule_more_p,
+  new_ready,
+  rgn_rank,
+  rgn_print_insn,
+  contributes_to_priority,
+
+  NULL, NULL,
+  NULL, NULL,
+  0, 0,
+
+  rgn_add_remove_insn,
+  begin_schedule_ready,
+  advance_target_bb,
+  SCHED_RGN
+};
+
+/* This variable holds the data and hooks needed to the Haifa scheduler backend
+   for the interblock scheduler frontend.  */
+static struct haifa_sched_info rgn_sched_info;
+
+/* Returns maximum priority that an insn was assigned to.  */
+
+int
+get_rgn_sched_max_insns_priority (void)
+{
+  return rgn_sched_info.sched_max_insns_priority;
+}
+
+/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register.  */
+
+static bool
+sets_likely_spilled (rtx pat)
+{
+  bool ret = false;
+  note_stores (pat, sets_likely_spilled_1, &ret);
+  return ret;
+}
+
+static void
+sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
+{
+  bool *ret = (bool *) data;
+
+  if (GET_CODE (pat) == SET
+      && REG_P (x)
+      && REGNO (x) < FIRST_PSEUDO_REGISTER
+      && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
+    *ret = true;
+}
+
+/* A bitmap to note insns that participate in any dependency.  Used in
+   add_branch_dependences.  */
+static sbitmap insn_referenced;
+
+/* Add dependences so that branches are scheduled to run last in their
+   block.  */
+static void
+add_branch_dependences (rtx head, rtx tail)
+{
+  rtx insn, last;
+
+  /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
+     that can throw exceptions, force them to remain in order at the end of
+     the block by adding dependencies and giving the last a high priority.
+     There may be notes present, and prev_head may also be a note.
+
+     Branches must obviously remain at the end.  Calls should remain at the
+     end since moving them results in worse register allocation.  Uses remain
+     at the end to ensure proper register allocation.
+
+     cc0 setters remain at the end because they can't be moved away from
+     their cc0 user.
+
+     COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
+
+     Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
+     are not moved before reload because we can wind up with register
+     allocation failures.  */
+
+  insn = tail;
+  last = 0;
+  while (CALL_P (insn)
+	 || JUMP_P (insn)
+	 || (NONJUMP_INSN_P (insn)
+	     && (GET_CODE (PATTERN (insn)) == USE
+		 || GET_CODE (PATTERN (insn)) == CLOBBER
+		 || can_throw_internal (insn)
+#ifdef HAVE_cc0
+		 || sets_cc0_p (PATTERN (insn))
+#endif
+		 || (!reload_completed
+		     && sets_likely_spilled (PATTERN (insn)))))
+	 || NOTE_P (insn))
+    {
+      if (!NOTE_P (insn))
+	{
+	  if (last != 0
+	      && sd_find_dep_between (insn, last, false) == NULL)
+	    {
+	      if (! sched_insns_conditions_mutex_p (last, insn))
+		add_dependence (last, insn, REG_DEP_ANTI);
+	      SET_BIT (insn_referenced, INSN_LUID (insn));
+	    }
+
+	  CANT_MOVE (insn) = 1;
+
+	  last = insn;
+	}
+
+      /* Don't overrun the bounds of the basic block.  */
+      if (insn == head)
+	break;
+
+      insn = PREV_INSN (insn);
+    }
+
+  /* Make sure these insns are scheduled last in their block.  */
+  insn = last;
+  if (insn != 0)
+    while (insn != head)
+      {
+	insn = prev_nonnote_insn (insn);
+
+	if (TEST_BIT (insn_referenced, INSN_LUID (insn)))
+	  continue;
+
+	if (! sched_insns_conditions_mutex_p (last, insn))
+	  add_dependence (last, insn, REG_DEP_ANTI);
+      }
+
+#ifdef HAVE_conditional_execution
+  /* Finally, if the block ends in a jump, and we are doing intra-block
+     scheduling, make sure that the branch depends on any COND_EXEC insns
+     inside the block to avoid moving the COND_EXECs past the branch insn.
+
+     We only have to do this after reload, because (1) before reload there
+     are no COND_EXEC insns, and (2) the region scheduler is an intra-block
+     scheduler after reload.
+
+     FIXME: We could in some cases move COND_EXEC insns past the branch if
+     this scheduler would be a little smarter.  Consider this code:
+
+		T = [addr]
+	C  ?	addr += 4
+	!C ?	X += 12
+	C  ?	T += 1
+	C  ?	jump foo
+
+     On a target with a one cycle stall on a memory access the optimal
+     sequence would be:
+
+		T = [addr]
+	C  ?	addr += 4
+	C  ?	T += 1
+	C  ?	jump foo
+	!C ?	X += 12
+
+     We don't want to put the 'X += 12' before the branch because it just
+     wastes a cycle of execution time when the branch is taken.
+
+     Note that in the example "!C" will always be true.  That is another
+     possible improvement for handling COND_EXECs in this scheduler: it
+     could remove always-true predicates.  */
+
+  if (!reload_completed || ! JUMP_P (tail))
+    return;
+
+  insn = tail;
+  while (insn != head)
+    {
+      insn = PREV_INSN (insn);
+
+      /* Note that we want to add this dependency even when
+	 sched_insns_conditions_mutex_p returns true.  The whole point
+	 is that we _want_ this dependency, even if these insns really
+	 are independent.  */
+      if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC)
+	add_dependence (tail, insn, REG_DEP_ANTI);
+    }
+#endif
+}
+
+/* Data structures for the computation of data dependences in a regions.  We
+   keep one `deps' structure for every basic block.  Before analyzing the
+   data dependences for a bb, its variables are initialized as a function of
+   the variables of its predecessors.  When the analysis for a bb completes,
+   we save the contents to the corresponding bb_deps[bb] variable.  */
+
+static struct deps *bb_deps;
+
+/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
+
+static rtx
+concat_INSN_LIST (rtx copy, rtx old)
+{
+  rtx new_rtx = old;
+  for (; copy ; copy = XEXP (copy, 1))
+    new_rtx = alloc_INSN_LIST (XEXP (copy, 0), new_rtx);
+  return new_rtx;
+}
+
+static void
+concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
+		      rtx *old_mems_p)
+{
+  rtx new_insns = *old_insns_p;
+  rtx new_mems = *old_mems_p;
+
+  while (copy_insns)
+    {
+      new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
+      new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
+      copy_insns = XEXP (copy_insns, 1);
+      copy_mems = XEXP (copy_mems, 1);
+    }
+
+  *old_insns_p = new_insns;
+  *old_mems_p = new_mems;
+}
+
+/* Join PRED_DEPS to the SUCC_DEPS.  */
+void
+deps_join (struct deps *succ_deps, struct deps *pred_deps)
+{
+  unsigned reg;
+  reg_set_iterator rsi;
+
+  /* The reg_last lists are inherited by successor.  */
+  EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi)
+    {
+      struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
+      struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
+
+      succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
+      succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
+      succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
+                                            succ_rl->clobbers);
+      succ_rl->uses_length += pred_rl->uses_length;
+      succ_rl->clobbers_length += pred_rl->clobbers_length;
+    }
+  IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
+
+  /* Mem read/write lists are inherited by successor.  */
+  concat_insn_mem_list (pred_deps->pending_read_insns,
+                        pred_deps->pending_read_mems,
+                        &succ_deps->pending_read_insns,
+                        &succ_deps->pending_read_mems);
+  concat_insn_mem_list (pred_deps->pending_write_insns,
+                        pred_deps->pending_write_mems,
+                        &succ_deps->pending_write_insns,
+                        &succ_deps->pending_write_mems);
+
+  succ_deps->last_pending_memory_flush
+    = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
+                        succ_deps->last_pending_memory_flush);
+
+  succ_deps->pending_read_list_length += pred_deps->pending_read_list_length;
+  succ_deps->pending_write_list_length += pred_deps->pending_write_list_length;
+  succ_deps->pending_flush_length += pred_deps->pending_flush_length;
+
+  /* last_function_call is inherited by successor.  */
+  succ_deps->last_function_call
+    = concat_INSN_LIST (pred_deps->last_function_call,
+                        succ_deps->last_function_call);
+
+  /* sched_before_next_call is inherited by successor.  */
+  succ_deps->sched_before_next_call
+    = concat_INSN_LIST (pred_deps->sched_before_next_call,
+                        succ_deps->sched_before_next_call);
+}
+
+/* After computing the dependencies for block BB, propagate the dependencies
+   found in TMP_DEPS to the successors of the block.  */
+static void
+propagate_deps (int bb, struct deps *pred_deps)
+{
+  basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb));
+  edge_iterator ei;
+  edge e;
+
+  /* bb's structures are inherited by its successors.  */
+  FOR_EACH_EDGE (e, ei, block->succs)
+    {
+      /* Only bbs "below" bb, in the same region, are interesting.  */
+      if (e->dest == EXIT_BLOCK_PTR
+	  || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index)
+	  || BLOCK_TO_BB (e->dest->index) <= bb)
+	continue;
+
+      deps_join (bb_deps + BLOCK_TO_BB (e->dest->index), pred_deps);
+    }
+
+  /* These lists should point to the right place, for correct
+     freeing later.  */
+  bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
+  bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
+  bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
+  bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
+
+  /* Can't allow these to be freed twice.  */
+  pred_deps->pending_read_insns = 0;
+  pred_deps->pending_read_mems = 0;
+  pred_deps->pending_write_insns = 0;
+  pred_deps->pending_write_mems = 0;
+}
+
+/* Compute dependences inside bb.  In a multiple blocks region:
+   (1) a bb is analyzed after its predecessors, and (2) the lists in
+   effect at the end of bb (after analyzing for bb) are inherited by
+   bb's successors.
+
+   Specifically for reg-reg data dependences, the block insns are
+   scanned by sched_analyze () top-to-bottom.  Two lists are
+   maintained by sched_analyze (): reg_last[].sets for register DEFs,
+   and reg_last[].uses for register USEs.
+
+   When analysis is completed for bb, we update for its successors:
+   ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
+   ;  - USES[succ] = Union (USES [succ], DEFS [bb])
+
+   The mechanism for computing mem-mem data dependence is very
+   similar, and the result is interblock dependences in the region.  */
+
+static void
+compute_block_dependences (int bb)
+{
+  rtx head, tail;
+  struct deps tmp_deps;
+
+  tmp_deps = bb_deps[bb];
+
+  /* Do the analysis for this block.  */
+  gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+  get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+
+  sched_analyze (&tmp_deps, head, tail);
+
+  /* Selective scheduling handles control dependencies by itself.  */
+  if (!sel_sched_p ())
+    add_branch_dependences (head, tail);
+
+  if (current_nr_blocks > 1)
+    propagate_deps (bb, &tmp_deps);
+
+  /* Free up the INSN_LISTs.  */
+  free_deps (&tmp_deps);
+
+  if (targetm.sched.dependencies_evaluation_hook)
+    targetm.sched.dependencies_evaluation_hook (head, tail);
+}
+
+/* Free dependencies of instructions inside BB.  */
+static void
+free_block_dependencies (int bb)
+{
+  rtx head;
+  rtx tail;
+
+  get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+
+  sched_free_deps (head, tail, true);
+}
+
+/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
+   them to the unused_*_list variables, so that they can be reused.  */
+
+static void
+free_pending_lists (void)
+{
+  int bb;
+
+  for (bb = 0; bb < current_nr_blocks; bb++)
+    {
+      free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
+      free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
+      free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
+      free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
+    }
+}
+
+/* Print dependences for debugging starting from FROM_BB.
+   Callable from debugger.  */
+/* Print dependences for debugging starting from FROM_BB.
+   Callable from debugger.  */
+void
+debug_rgn_dependencies (int from_bb)
+{
+  int bb;
+
+  fprintf (sched_dump,
+	   ";;   --------------- forward dependences: ------------ \n");
+
+  for (bb = from_bb; bb < current_nr_blocks; bb++)
+    {
+      rtx head, tail;
+
+      get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+      fprintf (sched_dump, "\n;;   --- Region Dependences --- b %d bb %d \n",
+	       BB_TO_BLOCK (bb), bb);
+
+      debug_dependencies (head, tail);
+    }
+}
+
+/* Print dependencies information for instructions between HEAD and TAIL.
+   ??? This function would probably fit best in haifa-sched.c.  */
+void debug_dependencies (rtx head, rtx tail)
+{
+  rtx insn;
+  rtx next_tail = NEXT_INSN (tail);
+
+  fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
+	   "insn", "code", "bb", "dep", "prio", "cost",
+	   "reservation");
+  fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
+	   "----", "----", "--", "---", "----", "----",
+	   "-----------");
+
+  for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+    {
+      if (! INSN_P (insn))
+	{
+	  int n;
+	  fprintf (sched_dump, ";;   %6d ", INSN_UID (insn));
+	  if (NOTE_P (insn))
+	    {
+	      n = NOTE_KIND (insn);
+	      fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
+	    }
+	  else
+	    fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
+	  continue;
+	}
+
+      fprintf (sched_dump,
+	       ";;   %s%5d%6d%6d%6d%6d%6d   ",
+	       (SCHED_GROUP_P (insn) ? "+" : " "),
+	       INSN_UID (insn),
+	       INSN_CODE (insn),
+	       BLOCK_NUM (insn),
+	       sched_emulate_haifa_p ? -1 : sd_lists_size (insn, SD_LIST_BACK),
+	       (sel_sched_p () ? (sched_emulate_haifa_p ? -1
+			       : INSN_PRIORITY (insn))
+		: INSN_PRIORITY (insn)),
+	       (sel_sched_p () ? (sched_emulate_haifa_p ? -1
+			       : insn_cost (insn))
+		: insn_cost (insn)));
+
+      if (recog_memoized (insn) < 0)
+	fprintf (sched_dump, "nothing");
+      else
+	print_reservation (sched_dump, insn);
+
+      fprintf (sched_dump, "\t: ");
+      {
+	sd_iterator_def sd_it;
+	dep_t dep;
+
+	FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+	  fprintf (sched_dump, "%d ", INSN_UID (DEP_CON (dep)));
+      }
+      fprintf (sched_dump, "\n");
+    }
+
+  fprintf (sched_dump, "\n");
+}
+
+/* Returns true if all the basic blocks of the current region have
+   NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region.  */
+bool
+sched_is_disabled_for_current_region_p (void)
+{
+  int bb;
+
+  for (bb = 0; bb < current_nr_blocks; bb++)
+    if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE))
+      return false;
+
+  return true;
+}
+
+/* Free all region dependencies saved in INSN_BACK_DEPS and 
+   INSN_RESOLVED_BACK_DEPS.  The Haifa scheduler does this on the fly
+   when scheduling, so this function is supposed to be called from 
+   the selective scheduling only.  */
+void
+free_rgn_deps (void)
+{
+  int bb;
+
+  for (bb = 0; bb < current_nr_blocks; bb++)
+    {
+      rtx head, tail;
+      
+      gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+      get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+
+      sched_free_deps (head, tail, false);
+    }
+}
+
+static int rgn_n_insns;
+
+/* Compute insn priority for a current region.  */
+void
+compute_priorities (void) 
+{
+  int bb;
+
+  current_sched_info->sched_max_insns_priority = 0;
+  for (bb = 0; bb < current_nr_blocks; bb++)
+    {
+      rtx head, tail;
+      
+      gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+      get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+
+      rgn_n_insns += set_priorities (head, tail);
+    }
+  current_sched_info->sched_max_insns_priority++;
+}
+
+/* Schedule a region.  A region is either an inner loop, a loop-free
+   subroutine, or a single basic block.  Each bb in the region is
+   scheduled after its flow predecessors.  */
+
+static void
+schedule_region (int rgn)
+{
+  int bb;
+  int sched_rgn_n_insns = 0;
+
+  rgn_n_insns = 0;
+
+  rgn_setup_region (rgn);
+
+  /* Don't schedule region that is marked by
+     NOTE_DISABLE_SCHED_OF_BLOCK.  */
+  if (sched_is_disabled_for_current_region_p ())
+    return;
+
+  sched_rgn_compute_dependencies (rgn);
+
+  sched_rgn_local_init (rgn);
+
+  /* Set priorities.  */
+  compute_priorities ();
+
+  sched_extend_ready_list (rgn_n_insns);
+
+  /* Now we can schedule all blocks.  */
+  for (bb = 0; bb < current_nr_blocks; bb++)
+    {
+      basic_block first_bb, last_bb, curr_bb;
+      rtx head, tail;
+
+      first_bb = EBB_FIRST_BB (bb);
+      last_bb = EBB_LAST_BB (bb);
+
+      get_ebb_head_tail (first_bb, last_bb, &head, &tail);
+
+      if (no_real_insns_p (head, tail))
+	{
+	  gcc_assert (first_bb == last_bb);
+	  continue;
+	}
+
+      current_sched_info->prev_head = PREV_INSN (head);
+      current_sched_info->next_tail = NEXT_INSN (tail);
+
+      remove_notes (head, tail);
+
+      unlink_bb_notes (first_bb, last_bb);
+
+      target_bb = bb;
+
+      gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
+      current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
+
+      curr_bb = first_bb;
+      if (dbg_cnt (sched_block))
+        {
+          schedule_block (&curr_bb);
+          gcc_assert (EBB_FIRST_BB (bb) == first_bb);
+          sched_rgn_n_insns += sched_n_insns;
+        }
+      else
+        {
+          sched_rgn_n_insns += rgn_n_insns;
+        }
+
+      /* Clean up.  */
+      if (current_nr_blocks > 1)
+	free_trg_info ();
+    }
+
+  /* Sanity check: verify that all region insns were scheduled.  */
+  gcc_assert (sched_rgn_n_insns == rgn_n_insns);
+
+  sched_finish_ready_list ();
+
+  /* Done with this region.  */
+  sched_rgn_local_finish ();
+
+  /* Free dependencies.  */
+  for (bb = 0; bb < current_nr_blocks; ++bb)
+    free_block_dependencies (bb);
+
+  gcc_assert (haifa_recovery_bb_ever_added_p
+	      || deps_pools_are_empty_p ());
+}
+
+/* Initialize data structures for region scheduling.  */
+
+void
+sched_rgn_init (bool single_blocks_p)
+{
+  min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
+		    / 100);
+
+  nr_inter = 0;
+  nr_spec = 0;
+
+  extend_regions ();
+
+  CONTAINING_RGN (ENTRY_BLOCK) = -1;
+  CONTAINING_RGN (EXIT_BLOCK) = -1;
+
+  /* Compute regions for scheduling.  */
+  if (single_blocks_p
+      || n_basic_blocks == NUM_FIXED_BLOCKS + 1
+      || !flag_schedule_interblock
+      || is_cfg_nonregular ())
+    {
+      find_single_block_region (sel_sched_p ());
+    }
+  else
+    {
+      /* Compute the dominators and post dominators.  */
+      if (!sel_sched_p ())
+	calculate_dominance_info (CDI_DOMINATORS);
+
+      /* Find regions.  */
+      find_rgns ();
+
+      if (sched_verbose >= 3)
+	debug_regions ();
+
+      /* For now.  This will move as more and more of haifa is converted
+	 to using the cfg code.  */
+      if (!sel_sched_p ())
+	free_dominance_info (CDI_DOMINATORS);
+    }
+
+  gcc_assert (0 < nr_regions && nr_regions <= n_basic_blocks);
+
+  RGN_BLOCKS (nr_regions) = (RGN_BLOCKS (nr_regions - 1) +
+			     RGN_NR_BLOCKS (nr_regions - 1));
+}
+
+/* Free data structures for region scheduling.  */
+void
+sched_rgn_finish (void)
+{
+  /* Reposition the prologue and epilogue notes in case we moved the
+     prologue/epilogue insns.  */
+  if (reload_completed)
+    reposition_prologue_and_epilogue_notes ();
+
+  if (sched_verbose)
+    {
+      if (reload_completed == 0
+	  && flag_schedule_interblock)
+	{
+	  fprintf (sched_dump,
+		   "\n;; Procedure interblock/speculative motions == %d/%d \n",
+		   nr_inter, nr_spec);
+	}
+      else
+	gcc_assert (nr_inter <= 0);
+      fprintf (sched_dump, "\n\n");
+    }
+
+  nr_regions = 0;
+
+  free (rgn_table);
+  rgn_table = NULL;
+
+  free (rgn_bb_table);
+  rgn_bb_table = NULL;
+
+  free (block_to_bb);
+  block_to_bb = NULL;
+
+  free (containing_rgn);
+  containing_rgn = NULL;
+
+  free (ebb_head);
+  ebb_head = NULL;
+}
+
+/* Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
+   point to the region RGN.  */
+void
+rgn_setup_region (int rgn)
+{
+  int bb;
+
+  /* Set variables for the current region.  */
+  current_nr_blocks = RGN_NR_BLOCKS (rgn);
+  current_blocks = RGN_BLOCKS (rgn);
+  
+  /* EBB_HEAD is a region-scope structure.  But we realloc it for
+     each region to save time/memory/something else.
+     See comments in add_block1, for what reasons we allocate +1 element.  */
+  ebb_head = XRESIZEVEC (int, ebb_head, current_nr_blocks + 1);
+  for (bb = 0; bb <= current_nr_blocks; bb++)
+    ebb_head[bb] = current_blocks + bb;
+}
+
+/* Compute instruction dependencies in region RGN.  */
+void
+sched_rgn_compute_dependencies (int rgn)
+{
+  if (!RGN_DONT_CALC_DEPS (rgn))
+    {
+      int bb;
+
+      if (sel_sched_p ())
+	sched_emulate_haifa_p = 1;
+
+      init_deps_global ();
+
+      /* Initializations for region data dependence analysis.  */
+      bb_deps = XNEWVEC (struct deps, current_nr_blocks);
+      for (bb = 0; bb < current_nr_blocks; bb++)
+	init_deps (bb_deps + bb);
+
+      /* Initialize bitmap used in add_branch_dependences.  */
+      insn_referenced = sbitmap_alloc (sched_max_luid);
+      sbitmap_zero (insn_referenced);
+      
+      /* Compute backward dependencies.  */
+      for (bb = 0; bb < current_nr_blocks; bb++)
+	compute_block_dependences (bb);
+      
+      sbitmap_free (insn_referenced);
+      free_pending_lists ();
+      finish_deps_global ();
+      free (bb_deps);
+
+      /* We don't want to recalculate this twice.  */
+      RGN_DONT_CALC_DEPS (rgn) = 1;
+
+      if (sel_sched_p ())
+	sched_emulate_haifa_p = 0;
+    }
+  else
+    /* (This is a recovery block.  It is always a single block region.)
+       OR (We use selective scheduling.)  */
+    gcc_assert (current_nr_blocks == 1 || sel_sched_p ());
+}
+
+/* Init region data structures.  Returns true if this region should
+   not be scheduled.  */
+void
+sched_rgn_local_init (int rgn)
+{
+  int bb;
+      
+  /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
+  if (current_nr_blocks > 1)
+    {
+      basic_block block;
+      edge e;
+      edge_iterator ei;
+
+      prob = XNEWVEC (int, current_nr_blocks);
+
+      dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
+      sbitmap_vector_zero (dom, current_nr_blocks);
+
+      /* Use ->aux to implement EDGE_TO_BIT mapping.  */
+      rgn_nr_edges = 0;
+      FOR_EACH_BB (block)
+	{
+	  if (CONTAINING_RGN (block->index) != rgn)
+	    continue;
+	  FOR_EACH_EDGE (e, ei, block->succs)
+	    SET_EDGE_TO_BIT (e, rgn_nr_edges++);
+	}
+
+      rgn_edges = XNEWVEC (edge, rgn_nr_edges);
+      rgn_nr_edges = 0;
+      FOR_EACH_BB (block)
+	{
+	  if (CONTAINING_RGN (block->index) != rgn)
+	    continue;
+	  FOR_EACH_EDGE (e, ei, block->succs)
+	    rgn_edges[rgn_nr_edges++] = e;
+	}
+
+      /* Split edges.  */
+      pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
+      sbitmap_vector_zero (pot_split, current_nr_blocks);
+      ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
+      sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
+
+      /* Compute probabilities, dominators, split_edges.  */
+      for (bb = 0; bb < current_nr_blocks; bb++)
+	compute_dom_prob_ps (bb);
+
+      /* Cleanup ->aux used for EDGE_TO_BIT mapping.  */
+      /* We don't need them anymore.  But we want to avoid duplication of
+	 aux fields in the newly created edges.  */
+      FOR_EACH_BB (block)
+	{
+	  if (CONTAINING_RGN (block->index) != rgn)
+	    continue;
+	  FOR_EACH_EDGE (e, ei, block->succs)
+	    e->aux = NULL;
+        }
+    }
+}
+
+/* Free data computed for the finished region.  */
+void 
+sched_rgn_local_free (void)
+{
+  free (prob);
+  sbitmap_vector_free (dom);
+  sbitmap_vector_free (pot_split);
+  sbitmap_vector_free (ancestor_edges);
+  free (rgn_edges);
+}
+
+/* Free data computed for the finished region.  */
+void
+sched_rgn_local_finish (void)
+{
+  if (current_nr_blocks > 1 && !sel_sched_p ())
+    {
+      sched_rgn_local_free ();
+    }
+}
+
+/* Setup scheduler infos.  */
+void
+rgn_setup_common_sched_info (void)
+{
+  memcpy (&rgn_common_sched_info, &haifa_common_sched_info,
+	  sizeof (rgn_common_sched_info));
+
+  rgn_common_sched_info.fix_recovery_cfg = rgn_fix_recovery_cfg;
+  rgn_common_sched_info.add_block = rgn_add_block;
+  rgn_common_sched_info.estimate_number_of_insns
+    = rgn_estimate_number_of_insns;
+  rgn_common_sched_info.sched_pass_id = SCHED_RGN_PASS;
+
+  common_sched_info = &rgn_common_sched_info;
+}
+
+/* Setup all *_sched_info structures (for the Haifa frontend
+   and for the dependence analysis) in the interblock scheduler.  */
+void
+rgn_setup_sched_infos (void)
+{
+  if (!sel_sched_p ())
+    memcpy (&rgn_sched_deps_info, &rgn_const_sched_deps_info,
+	    sizeof (rgn_sched_deps_info));
+  else
+    memcpy (&rgn_sched_deps_info, &rgn_const_sel_sched_deps_info,
+	    sizeof (rgn_sched_deps_info));
+
+  sched_deps_info = &rgn_sched_deps_info;
+
+  memcpy (&rgn_sched_info, &rgn_const_sched_info, sizeof (rgn_sched_info));
+  current_sched_info = &rgn_sched_info;
+}
+
+/* The one entry point in this file.  */
+void
+schedule_insns (void)
+{
+  int rgn;
+
+  /* Taking care of this degenerate case makes the rest of
+     this code simpler.  */
+  if (n_basic_blocks == NUM_FIXED_BLOCKS)
+    return;
+
+  rgn_setup_common_sched_info ();
+  rgn_setup_sched_infos ();
+
+  haifa_sched_init ();
+  sched_rgn_init (reload_completed);
+
+  bitmap_initialize (&not_in_df, 0);
+  bitmap_clear (&not_in_df);
+
+  /* Schedule every region in the subroutine.  */
+  for (rgn = 0; rgn < nr_regions; rgn++)
+    if (dbg_cnt (sched_region))
+      schedule_region (rgn);
+
+  /* Clean up.  */
+  sched_rgn_finish ();
+  bitmap_clear (&not_in_df);
+
+  haifa_sched_finish ();
+}
+
+/* INSN has been added to/removed from current region.  */
+static void
+rgn_add_remove_insn (rtx insn, int remove_p)
+{
+  if (!remove_p)
+    rgn_n_insns++;
+  else
+    rgn_n_insns--;
+
+  if (INSN_BB (insn) == target_bb)
+    {
+      if (!remove_p)
+	target_n_insns++;
+      else
+	target_n_insns--;
+    }
+}
+
+/* Extend internal data structures.  */
+void
+extend_regions (void)
+{
+  rgn_table = XRESIZEVEC (region, rgn_table, n_basic_blocks);
+  rgn_bb_table = XRESIZEVEC (int, rgn_bb_table, n_basic_blocks);
+  block_to_bb = XRESIZEVEC (int, block_to_bb, last_basic_block);
+  containing_rgn = XRESIZEVEC (int, containing_rgn, last_basic_block);
+}
+
+void
+rgn_make_new_region_out_of_new_block (basic_block bb)
+{
+  int i;
+
+  i = RGN_BLOCKS (nr_regions);
+  /* I - first free position in rgn_bb_table.  */
+
+  rgn_bb_table[i] = bb->index;
+  RGN_NR_BLOCKS (nr_regions) = 1;
+  RGN_HAS_REAL_EBB (nr_regions) = 0;
+  RGN_DONT_CALC_DEPS (nr_regions) = 0;
+  CONTAINING_RGN (bb->index) = nr_regions;
+  BLOCK_TO_BB (bb->index) = 0;
+
+  nr_regions++;
+      
+  RGN_BLOCKS (nr_regions) = i + 1;
+}
+
+/* BB was added to ebb after AFTER.  */
+static void
+rgn_add_block (basic_block bb, basic_block after)
+{
+  extend_regions ();
+  bitmap_set_bit (&not_in_df, bb->index);
+
+  if (after == 0 || after == EXIT_BLOCK_PTR)
+    {
+      rgn_make_new_region_out_of_new_block (bb);
+      RGN_DONT_CALC_DEPS (nr_regions - 1) = (after == EXIT_BLOCK_PTR);
+    }
+  else
+    { 
+      int i, pos;
+
+      /* We need to fix rgn_table, block_to_bb, containing_rgn
+	 and ebb_head.  */
+
+      BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
+
+      /* We extend ebb_head to one more position to
+	 easily find the last position of the last ebb in 
+	 the current region.  Thus, ebb_head[BLOCK_TO_BB (after) + 1]
+	 is _always_ valid for access.  */
+
+      i = BLOCK_TO_BB (after->index) + 1;
+      pos = ebb_head[i] - 1;
+      /* Now POS is the index of the last block in the region.  */
+
+      /* Find index of basic block AFTER.  */
+      for (; rgn_bb_table[pos] != after->index; pos--);
+
+      pos++;
+      gcc_assert (pos > ebb_head[i - 1]);
+
+      /* i - ebb right after "AFTER".  */
+      /* ebb_head[i] - VALID.  */
+
+      /* Source position: ebb_head[i]
+	 Destination position: ebb_head[i] + 1
+	 Last position: 
+	   RGN_BLOCKS (nr_regions) - 1
+	 Number of elements to copy: (last_position) - (source_position) + 1
+       */
+      
+      memmove (rgn_bb_table + pos + 1,
+	       rgn_bb_table + pos,
+	       ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
+	       * sizeof (*rgn_bb_table));
+
+      rgn_bb_table[pos] = bb->index;
+      
+      for (; i <= current_nr_blocks; i++)
+	ebb_head [i]++;
+
+      i = CONTAINING_RGN (after->index);
+      CONTAINING_RGN (bb->index) = i;
+      
+      RGN_HAS_REAL_EBB (i) = 1;
+
+      for (++i; i <= nr_regions; i++)
+	RGN_BLOCKS (i)++;
+    }
+}
+
+/* Fix internal data after interblock movement of jump instruction.
+   For parameter meaning please refer to
+   sched-int.h: struct sched_info: fix_recovery_cfg.  */
+static void
+rgn_fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
+{
+  int old_pos, new_pos, i;
+
+  BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
+  
+  for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
+       rgn_bb_table[old_pos] != check_bb_nexti;
+       old_pos--);
+  gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
+
+  for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
+       rgn_bb_table[new_pos] != bbi;
+       new_pos--);
+  new_pos++;
+  gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
+  
+  gcc_assert (new_pos < old_pos);
+
+  memmove (rgn_bb_table + new_pos + 1,
+	   rgn_bb_table + new_pos,
+	   (old_pos - new_pos) * sizeof (*rgn_bb_table));
+
+  rgn_bb_table[new_pos] = check_bb_nexti;
+
+  for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
+    ebb_head[i]++;
+}
+
+/* Return next block in ebb chain.  For parameter meaning please refer to
+   sched-int.h: struct sched_info: advance_target_bb.  */
+static basic_block
+advance_target_bb (basic_block bb, rtx insn)
+{
+  if (insn)
+    return 0;
+
+  gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
+	      && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
+  return bb->next_bb;
+}
+
+#endif
+
+static bool
+gate_handle_sched (void)
+{
+#ifdef INSN_SCHEDULING
+  return flag_schedule_insns && dbg_cnt (sched_func);
+#else
+  return 0;
+#endif
+}
+
+/* Run instruction scheduler.  */
+static unsigned int
+rest_of_handle_sched (void)
+{
+#ifdef INSN_SCHEDULING
+  if (flag_selective_scheduling
+      && ! maybe_skip_selective_scheduling ())
+    run_selective_scheduling ();
+  else
+    schedule_insns ();
+#endif
+  return 0;
+}
+
+static bool
+gate_handle_sched2 (void)
+{
+#ifdef INSN_SCHEDULING
+  return optimize > 0 && flag_schedule_insns_after_reload 
+    && dbg_cnt (sched2_func);
+#else
+  return 0;
+#endif
+}
+
+/* Run second scheduling pass after reload.  */
+static unsigned int
+rest_of_handle_sched2 (void)
+{
+#ifdef INSN_SCHEDULING
+  if (flag_selective_scheduling2
+      && ! maybe_skip_selective_scheduling ())
+    run_selective_scheduling ();
+  else
+    {
+      /* Do control and data sched analysis again,
+	 and write some more of the results to dump file.  */
+      if (flag_sched2_use_superblocks || flag_sched2_use_traces)
+	schedule_ebbs ();
+      else
+	schedule_insns ();
+    }
+#endif
+  return 0;
+}
+
+struct rtl_opt_pass pass_sched =
+{
+ {
+  RTL_PASS,
+  "sched1",                             /* name */
+  gate_handle_sched,                    /* gate */
+  rest_of_handle_sched,                 /* execute */
+  NULL,                                 /* sub */
+  NULL,                                 /* next */
+  0,                                    /* static_pass_number */
+  TV_SCHED,                             /* tv_id */
+  0,                                    /* properties_required */
+  0,                                    /* properties_provided */
+  0,                                    /* properties_destroyed */
+  0,                                    /* todo_flags_start */
+  TODO_df_finish | TODO_verify_rtl_sharing |
+  TODO_dump_func |
+  TODO_verify_flow |
+  TODO_ggc_collect                      /* todo_flags_finish */
+ }
+};
+
+struct rtl_opt_pass pass_sched2 =
+{
+ {
+  RTL_PASS,
+  "sched2",                             /* name */
+  gate_handle_sched2,                   /* gate */
+  rest_of_handle_sched2,                /* execute */
+  NULL,                                 /* sub */
+  NULL,                                 /* next */
+  0,                                    /* static_pass_number */
+  TV_SCHED2,                            /* tv_id */
+  0,                                    /* properties_required */
+  0,                                    /* properties_provided */
+  0,                                    /* properties_destroyed */
+  0,                                    /* todo_flags_start */
+  TODO_df_finish | TODO_verify_rtl_sharing |
+  TODO_dump_func |
+  TODO_verify_flow |
+  TODO_ggc_collect                      /* todo_flags_finish */
+ }
+};
+