Move dependency code out of haifa-sched.c

From-SVN: r37975

5 files changed, 1599 insertions, 1471 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index efabdb4..d38b6e8 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,32 @@
 2000-12-03  Bernd Schmidt  <bernds@redhat.co.uk>
 
+	* Makefile.in (OBJS): Add sched-deps.o.
+	(sched-deps.o): New rule.
+	* haifa-sched.c (struct deps, struct haifa_insn_data): Moved to
+	sched-int.h.
+	(INSN_DEPEND, INSN_LUID, CANT_MOVE, INSN_DEP_COUNT): Macros moved to
+	sched-int.h.
+	(SIZE_FOR_MODE): Delete unused macro.
+	(reg_known_equiv_p, reg_known_value, reg_pending_clobbers,
+	reg_pending_sets, reg_pending_sets_all, true_dependency_cache,
+	anti_dependency_cache, output_dependency_cache,
+	forward_dependency_cache): Variables moved to sched-deps.c.
+	(add_dependence, remove_dependence, find_insn_list,
+	find_insn_mem_list, add_insn_mem_dependence, flush_pending_lists,
+	sched_analyze_insn, sched_analyze_1, sched_analyze_2,
+	sched_analyze, group_leader, compute_forward_dependences,
+	init_deps, free_deps, init_dependency_caches, free_dependency_caches):
+	Functions moved to sched-deps.c.
+	(schedule_region): Call init_deps_global and finish_deps_global
+	instead of directly manipulating dependency data structures.
+	* sched-deps.c: New file.
+	(init_deps_global, finish_deps_global): New functions.
+	* sched-int.h (struct haifa_insn_data, struct deps): Moved here from
+	haifa-sched.c.
+	(h_i_d): Declare.
+	(INSN_DEPEND, INSN_LUID, CANT_MOVE, INSN_DEP_COUNT): Macros moved here
+	from haifa-sched.c.
+
 	* Makefile.in (OBJS): Add sched-vis.o.
 	(sched-vis.o): New rule.
 	* haifa-sched.c (get_unit_last_insn): New function.
@@ -20,6 +47,11 @@
 	print_block_visualization): Lose basic block argument.  All callers
 	changed.
 	(visualize_scheduled_insns): Use new function get_unit_last_insn.
+	* sched-int.h (current_sched_info, sched_dump): Declare.
+	(init_target_units, insn_print_units, init_block_visualization,
+	print_block_visualization, visualize_scheduled_inns,
+	visualize_no_unit, visualize_stall_cycles, visualize_alloc,
+	visualize_free): Declare functions.
 
 	* sched-int.h: New file.
 	* Makefile.in (haifa-sched.o): Depend on it.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 6cb0d77..62f5ae0 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -737,7 +737,7 @@ OBJS = diagnostic.o version.o tree.o print-tree.o stor-layout.o fold-const.o  \
  mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o	      \
  lists.o ggc-common.o $(GGC) stringpool.o simplify-rtx.o ssa.o bb-reorder.o   \
  sibcall.o conflict.o timevar.o ifcvt.o dominance.o dependence.o dce.o \
- sched-vis.o hashtab.o
+ sched-vis.o sched-deps.o hashtab.o
 
 BACKEND = toplev.o libbackend.a
 
@@ -1455,6 +1455,9 @@ regmove.o : regmove.c $(CONFIG_H) system.h $(RTL_H) insn-config.h \
 haifa-sched.o : haifa-sched.c $(CONFIG_H) system.h $(RTL_H) sched-int.h \
    $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h function.h \
    $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h
+sched-deps.o : haifa-sched.c $(CONFIG_H) system.h $(RTL_H) sched-int.h \
+   $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h function.h \
+   $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h
 sched-vis.o : sched-vis.c $(CONFIG_H) system.h $(RTL_H) sched-int.h \
    $(INSN_ATTR_H) $(REGS_H)
 final.o : final.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h intl.h \
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index f89f2a1..d768d85 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -172,9 +172,6 @@ the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "recog.h"
 #include "sched-int.h"
 
-extern char *reg_known_equiv_p;
-extern rtx *reg_known_value;
-
 #ifdef INSN_SCHEDULING
 
 /* issue_rate is the number of insns that can be scheduled in the same
@@ -225,158 +222,9 @@ fix_sched_param (param, val)
     warning ("fix_sched_param: unknown param: %s", param);
 }
 
-/* Describe state of dependencies used during sched_analyze phase.  */
-struct deps
-{
-  /* The *_insns and *_mems are paired lists.  Each pending memory operation
-     will have a pointer to the MEM rtx on one list and a pointer to the
-     containing insn on the other list in the same place in the list.  */
-
-  /* We can't use add_dependence like the old code did, because a single insn
-     may have multiple memory accesses, and hence needs to be on the list
-     once for each memory access.  Add_dependence won't let you add an insn
-     to a list more than once.  */
-
-  /* An INSN_LIST containing all insns with pending read operations.  */
-  rtx pending_read_insns;
-
-  /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
-  rtx pending_read_mems;
-
-  /* An INSN_LIST containing all insns with pending write operations.  */
-  rtx pending_write_insns;
-
-  /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
-  rtx pending_write_mems;
-
-  /* Indicates the combined length of the two pending lists.  We must prevent
-     these lists from ever growing too large since the number of dependencies
-     produced is at least O(N*N), and execution time is at least O(4*N*N), as
-     a function of the length of these pending lists.  */
-  int pending_lists_length;
-
-  /* The last insn upon which all memory references must depend.
-     This is an insn which flushed the pending lists, creating a dependency
-     between it and all previously pending memory references.  This creates
-     a barrier (or a checkpoint) which no memory reference is allowed to cross.
-
-     This includes all non constant CALL_INSNs.  When we do interprocedural
-     alias analysis, this restriction can be relaxed.
-     This may also be an INSN that writes memory if the pending lists grow
-     too large.  */
-  rtx last_pending_memory_flush;
-
-  /* The last function call we have seen.  All hard regs, and, of course,
-     the last function call, must depend on this.  */
-  rtx last_function_call;
-
-  /* Used to keep post-call psuedo/hard reg movements together with
-     the call.  */
-  int in_post_call_group_p;
-
-  /* The LOG_LINKS field of this is a list of insns which use a pseudo
-     register that does not already cross a call.  We create
-     dependencies between each of those insn and the next call insn,
-     to ensure that they won't cross a call after scheduling is done.  */
-  rtx sched_before_next_call;
-
-  /* Element N is the next insn that sets (hard or pseudo) register
-     N within the current basic block; or zero, if there is no
-     such insn.  Needed for new registers which may be introduced
-     by splitting insns.  */
-  rtx *reg_last_uses;
-  rtx *reg_last_sets;
-  rtx *reg_last_clobbers;
-};
-
-static regset reg_pending_sets;
-static regset reg_pending_clobbers;
-static int reg_pending_sets_all;
-
-/* To speed up the test for duplicate dependency links we keep a
-   record of dependencies created by add_dependence when the average
-   number of instructions in a basic block is very large.
-
-   Studies have shown that there is typically around 5 instructions between
-   branches for typical C code.  So we can make a guess that the average
-   basic block is approximately 5 instructions long; we will choose 100X
-   the average size as a very large basic block.
-
-   Each insn has associated bitmaps for its dependencies.  Each bitmap
-   has enough entries to represent a dependency on any other insn in
-   the insn chain.  All bitmap for true dependencies cache is
-   allocated then the rest two ones are also allocated. */
-static sbitmap *true_dependency_cache;
-static sbitmap *anti_dependency_cache;
-static sbitmap *output_dependency_cache;
-
-/* To speed up checking consistency of formed forward insn
-   dependencies we use the following cache.  Another possible solution
-   could be switching off checking duplication of insns in forward
-   dependencies. */
-#ifdef ENABLE_CHECKING
-static sbitmap *forward_dependency_cache;
-#endif
-
-/* Indexed by INSN_UID, the collection of all data associated with
-   a single instruction.  */
-
-struct haifa_insn_data
-{
-  /* A list of insns which depend on the instruction.  Unlike LOG_LINKS,
-     it represents forward dependancies.  */
-  rtx depend;
-
-  /* The line number note in effect for each insn.  For line number
-     notes, this indicates whether the note may be reused.  */
-  rtx line_note;
-
-  /* Logical uid gives the original ordering of the insns.  */
-  int luid;
-
-  /* A priority for each insn.  */
-  int priority;
-
-  /* The number of incoming edges in the forward dependency graph.
-     As scheduling proceds, counts are decreased.  An insn moves to
-     the ready queue when its counter reaches zero.  */
-  int dep_count;
-
-  /* An encoding of the blockage range function.  Both unit and range
-     are coded.  */
-  unsigned int blockage;
-
-  /* Number of instructions referring to this insn.  */
-  int ref_count;
-
-  /* The minimum clock tick at which the insn becomes ready.  This is
-     used to note timing constraints for the insns in the pending list.  */
-  int tick;
+struct haifa_insn_data *h_i_d;
 
-  short cost;
-
-  /* An encoding of the function units used.  */
-  short units;
-
-  /* This weight is an estimation of the insn's contribution to
-     register pressure.  */
-  short reg_weight;
-
-  /* Some insns (e.g. call) are not allowed to move across blocks.  */
-  unsigned int cant_move : 1;
-
-  /* Set if there's DEF-USE dependance between some speculatively
-     moved load insn and this one.  */
-  unsigned int fed_by_spec_load : 1;
-  unsigned int is_load_insn : 1;
-};
-
-static struct haifa_insn_data *h_i_d;
-
-#define INSN_DEPEND(INSN)	(h_i_d[INSN_UID (INSN)].depend)
-#define INSN_LUID(INSN)		(h_i_d[INSN_UID (INSN)].luid)
 #define INSN_PRIORITY(INSN)	(h_i_d[INSN_UID (INSN)].priority)
-#define INSN_DEP_COUNT(INSN)	(h_i_d[INSN_UID (INSN)].dep_count)
 #define INSN_COST(INSN)		(h_i_d[INSN_UID (INSN)].cost)
 #define INSN_UNIT(INSN)		(h_i_d[INSN_UID (INSN)].units)
 #define INSN_REG_WEIGHT(INSN)	(h_i_d[INSN_UID (INSN)].reg_weight)
@@ -407,7 +255,6 @@ static struct haifa_insn_data *h_i_d;
 #define INSN_REF_COUNT(INSN)	(h_i_d[INSN_UID (INSN)].ref_count)
 #define LINE_NOTE(INSN)		(h_i_d[INSN_UID (INSN)].line_note)
 #define INSN_TICK(INSN)		(h_i_d[INSN_UID (INSN)].tick)
-#define CANT_MOVE(insn)		(h_i_d[INSN_UID (insn)].cant_move)
 #define FED_BY_SPEC_LOAD(insn)	(h_i_d[INSN_UID (insn)].fed_by_spec_load)
 #define IS_LOAD_INSN(insn)	(h_i_d[INSN_UID (insn)].is_load_insn)
 
@@ -489,10 +336,6 @@ struct ready_list
 };
 
 /* Forward declarations.  */
-static void add_dependence PARAMS ((rtx, rtx, enum reg_note));
-static void remove_dependence PARAMS ((rtx, rtx));
-static rtx find_insn_list PARAMS ((rtx, rtx));
-static void set_sched_group_p PARAMS ((rtx));
 static unsigned int blockage_range PARAMS ((int, rtx));
 static void clear_units PARAMS ((void));
 static void schedule_unit PARAMS ((int, rtx, int));
@@ -501,13 +344,6 @@ static int potential_hazard PARAMS ((int, rtx, int));
 static int insn_cost PARAMS ((rtx, rtx, rtx));
 static int priority PARAMS ((rtx));
 static void free_pending_lists PARAMS ((void));
-static void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
-					     rtx));
-static void flush_pending_lists PARAMS ((struct deps *, rtx, int));
-static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
-static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
-static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
-static void sched_analyze PARAMS ((struct deps *, rtx, rtx));
 static int rank_for_schedule PARAMS ((const PTR, const PTR));
 static void swap_sort PARAMS ((rtx *, int));
 static void queue_insn PARAMS ((rtx, int));
@@ -740,8 +576,6 @@ static int haifa_classify_insn PARAMS ((rtx));
 static int is_prisky PARAMS ((rtx, int, int));
 static int is_exception_free PARAMS ((rtx, int, int));
 
-static char find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx));
-static void compute_forward_dependences PARAMS ((rtx, rtx));
 static void add_branch_dependences PARAMS ((rtx, rtx));
 static void compute_block_backward_dependences PARAMS ((int));
 void debug_dependencies PARAMS ((void));
@@ -794,12 +628,7 @@ void debug_reg_vector PARAMS ((regset));
 
 static rtx move_insn1 PARAMS ((rtx, rtx));
 static rtx move_insn PARAMS ((rtx, rtx));
-static rtx group_leader PARAMS ((rtx));
 static int set_priorities PARAMS ((int));
-static void init_deps PARAMS ((struct deps *));
-static void free_deps PARAMS ((struct deps *));
-static void init_dependency_caches PARAMS ((int));
-static void free_dependency_caches PARAMS ((void));
 static void init_regions PARAMS ((void));
 static void sched_init PARAMS ((FILE *));
 static void schedule_region PARAMS ((int));
@@ -809,307 +638,6 @@ static void propagate_deps PARAMS ((int, struct deps *, int));
 
 /* Point to state used for the current scheduling pass.  */
 struct sched_info *current_sched_info;
-
-#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
-
-/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
-   LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the type
-   of dependence that this link represents.  */
-
-static void
-add_dependence (insn, elem, dep_type)
-     rtx insn;
-     rtx elem;
-     enum reg_note dep_type;
-{
-  rtx link, next;
-  int present_p;
-  enum reg_note present_dep_type;
-
-  /* Don't depend an insn on itself.  */
-  if (insn == elem)
-    return;
-
-  /* We can get a dependency on deleted insns due to optimizations in
-     the register allocation and reloading or due to splitting.  Any
-     such dependency is useless and can be ignored.  */
-  if (GET_CODE (elem) == NOTE)
-    return;
-
-  /* If elem is part of a sequence that must be scheduled together, then
-     make the dependence point to the last insn of the sequence.
-     When HAVE_cc0, it is possible for NOTEs to exist between users and
-     setters of the condition codes, so we must skip past notes here.
-     Otherwise, NOTEs are impossible here.  */
-  next = next_nonnote_insn (elem);
-  if (next && SCHED_GROUP_P (next)
-      && GET_CODE (next) != CODE_LABEL)
-    {
-      /* Notes will never intervene here though, so don't bother checking
-         for them.  */
-      /* Hah!  Wrong.  */
-      /* We must reject CODE_LABELs, so that we don't get confused by one
-         that has LABEL_PRESERVE_P set, which is represented by the same
-         bit in the rtl as SCHED_GROUP_P.  A CODE_LABEL can never be
-         SCHED_GROUP_P.  */
-
-      rtx nnext;
-      while ((nnext = next_nonnote_insn (next)) != NULL
-	     && SCHED_GROUP_P (nnext)
-	     && GET_CODE (nnext) != CODE_LABEL)
-	next = nnext;
-
-      /* Again, don't depend an insn on itself.  */
-      if (insn == next)
-	return;
-
-      /* Make the dependence to NEXT, the last insn of the group, instead
-         of the original ELEM.  */
-      elem = next;
-    }
-
-  present_p = 1;
-#ifdef INSN_SCHEDULING
-  /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
-     No need for interblock dependences with calls, since
-     calls are not moved between blocks.   Note: the edge where
-     elem is a CALL is still required.  */
-  if (GET_CODE (insn) == CALL_INSN
-      && (INSN_BB (elem) != INSN_BB (insn)))
-    return;
-
-  /* If we already have a dependency for ELEM, then we do not need to
-     do anything.  Avoiding the list walk below can cut compile times
-     dramatically for some code.  */
-  if (true_dependency_cache != NULL)
-    {
-      if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
-	abort ();
-      if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
-	present_dep_type = 0;
-      else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
-			 INSN_LUID (elem)))
-	present_dep_type = REG_DEP_ANTI;
-      else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
-			 INSN_LUID (elem)))
-	present_dep_type = REG_DEP_OUTPUT;
-      else 
-	present_p = 0;
-      if (present_p && (int) dep_type >= (int) present_dep_type)
-	return;
-    }
-#endif
-
-  /* Check that we don't already have this dependence.  */
-  if (present_p)
-    for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
-      if (XEXP (link, 0) == elem)
-	{
-#ifdef INSN_SCHEDULING
-	  /* Clear corresponding cache entry because type of the link
-             may be changed. */
-	  if (true_dependency_cache != NULL)
-	    {
-	      if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
-		RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
-			   INSN_LUID (elem));
-	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
-		       && output_dependency_cache)
-		RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
-			   INSN_LUID (elem));
-	      else
-		abort ();
-	    }
-#endif
-
-	  /* If this is a more restrictive type of dependence than the existing
-	     one, then change the existing dependence to this type.  */
-	  if ((int) dep_type < (int) REG_NOTE_KIND (link))
-	    PUT_REG_NOTE_KIND (link, dep_type);
-	  
-#ifdef INSN_SCHEDULING
-	  /* If we are adding a dependency to INSN's LOG_LINKs, then
-	     note that in the bitmap caches of dependency information. */
-	  if (true_dependency_cache != NULL)
-	    {
-	      if ((int)REG_NOTE_KIND (link) == 0)
-		SET_BIT (true_dependency_cache[INSN_LUID (insn)],
-			 INSN_LUID (elem));
-	      else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
-		SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
-			 INSN_LUID (elem));
-	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
-		SET_BIT (output_dependency_cache[INSN_LUID (insn)],
-			 INSN_LUID (elem));
-	    }
-#endif
-	  return;
-      }
-  /* Might want to check one level of transitivity to save conses.  */
-
-  link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
-  LOG_LINKS (insn) = link;
-
-  /* Insn dependency, not data dependency.  */
-  PUT_REG_NOTE_KIND (link, dep_type);
-
-#ifdef INSN_SCHEDULING
-  /* If we are adding a dependency to INSN's LOG_LINKs, then note that
-     in the bitmap caches of dependency information. */
-  if (true_dependency_cache != NULL)
-    {
-      if ((int)dep_type == 0)
-	SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
-      else if (dep_type == REG_DEP_ANTI)
-	SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
-      else if (dep_type == REG_DEP_OUTPUT)
-	SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
-    }
-#endif
-}
-
-/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
-   of INSN.  Abort if not found.  */
-
-static void
-remove_dependence (insn, elem)
-     rtx insn;
-     rtx elem;
-{
-  rtx prev, link, next;
-  int found = 0;
-
-  for (prev = 0, link = LOG_LINKS (insn); link; link = next)
-    {
-      next = XEXP (link, 1);
-      if (XEXP (link, 0) == elem)
-	{
-	  if (prev)
-	    XEXP (prev, 1) = next;
-	  else
-	    LOG_LINKS (insn) = next;
-
-#ifdef INSN_SCHEDULING
-	  /* If we are removing a dependency from the LOG_LINKS list,
-	     make sure to remove it from the cache too.  */
-	  if (true_dependency_cache != NULL)
-	    {
-	      if (REG_NOTE_KIND (link) == 0)
-		RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
-			   INSN_LUID (elem));
-	      else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
-		RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
-			   INSN_LUID (elem));
-	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
-		RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
-			   INSN_LUID (elem));
-	    }
-#endif
-
-	  free_INSN_LIST_node (link);
-
-	  found = 1;
-	}
-      else
-	prev = link;
-    }
-
-  if (!found)
-    abort ();
-  return;
-}
-
-/* Return the INSN_LIST containing INSN in LIST, or NULL
-   if LIST does not contain INSN.  */
-
-static inline rtx
-find_insn_list (insn, list)
-     rtx insn;
-     rtx list;
-{
-  while (list)
-    {
-      if (XEXP (list, 0) == insn)
-	return list;
-      list = XEXP (list, 1);
-    }
-  return 0;
-}
-
-/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
-   goes along with that.  */
-
-static void
-set_sched_group_p (insn)
-     rtx insn;
-{
-  rtx link, prev;
-
-  SCHED_GROUP_P (insn) = 1;
-
-  /* There may be a note before this insn now, but all notes will
-     be removed before we actually try to schedule the insns, so
-     it won't cause a problem later.  We must avoid it here though.  */
-  prev = prev_nonnote_insn (insn);
-
-  /* Make a copy of all dependencies on the immediately previous insn,
-     and add to this insn.  This is so that all the dependencies will
-     apply to the group.  Remove an explicit dependence on this insn
-     as SCHED_GROUP_P now represents it.  */
-
-  if (find_insn_list (prev, LOG_LINKS (insn)))
-    remove_dependence (insn, prev);
-
-  for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
-    add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
-}
-
-/* If it is profitable to use them, initialize caches for tracking
-   dependency informatino.  LUID is the number of insns to be scheduled,
-   it is used in the estimate of profitability.  */
-static void
-init_dependency_caches (luid)
-     int luid;
-{
-  /* ?!? We could save some memory by computing a per-region luid mapping
-     which could reduce both the number of vectors in the cache and the size
-     of each vector.  Instead we just avoid the cache entirely unless the
-     average number of instructions in a basic block is very high.  See
-     the comment before the declaration of true_dependency_cache for
-     what we consider "very high".  */
-  if (luid / n_basic_blocks > 100 * 5)
-    {
-      true_dependency_cache = sbitmap_vector_alloc (luid, luid);
-      sbitmap_vector_zero (true_dependency_cache, luid);
-      anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
-      sbitmap_vector_zero (anti_dependency_cache, luid);
-      output_dependency_cache = sbitmap_vector_alloc (luid, luid);
-      sbitmap_vector_zero (output_dependency_cache, luid);
-#ifdef ENABLE_CHECKING
-      forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
-      sbitmap_vector_zero (forward_dependency_cache, luid);
-#endif
-    }
-}
-
-/* Free the caches allocated in init_dependency_caches.  */
-static void
-free_dependency_caches ()
-{
-  if (true_dependency_cache)
-    {
-      free (true_dependency_cache);
-      true_dependency_cache = NULL;
-      free (anti_dependency_cache);
-      anti_dependency_cache = NULL;
-      free (output_dependency_cache);
-      output_dependency_cache = NULL;
-#ifdef ENABLE_CHECKING
-      free (forward_dependency_cache);
-      forward_dependency_cache = NULL;
-#endif
-    }
-}
 
 #ifndef INSN_SCHEDULING
 void
@@ -2853,37 +2381,7 @@ is_exception_free (insn, bb_src, bb_trg)
 
   return flag_schedule_speculative_load_dangerous;
 }
-
-/* Process an insn's memory dependencies.  There are four kinds of
-   dependencies:
-
-   (0) read dependence: read follows read
-   (1) true dependence: read follows write
-   (2) anti dependence: write follows read
-   (3) output dependence: write follows write
-
-   We are careful to build only dependencies which actually exist, and
-   use transitivity to avoid building too many links.  */
 
-/* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
-   otherwise.  */
-
-HAIFA_INLINE static char
-find_insn_mem_list (insn, x, list, list1)
-     rtx insn, x;
-     rtx list, list1;
-{
-  while (list)
-    {
-      if (XEXP (list, 0) == insn
-	  && XEXP (list1, 0) == x)
-	return 1;
-      list = XEXP (list, 1);
-      list1 = XEXP (list1, 1);
-    }
-  return 0;
-}
-
 /* Compute the function units used by INSN.  This caches the value
    returned by function_units_used.  A function unit is encoded as the
    unit number if the value is non-negative and the compliment of a
@@ -3299,836 +2797,6 @@ free_pending_lists ()
       free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
     }
 }
-
-/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
-   The MEM is a memory reference contained within INSN, which we are saving
-   so that we can do memory aliasing on it.  */
-
-static void
-add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
-     struct deps *deps;
-     rtx *insn_list, *mem_list, insn, mem;
-{
-  register rtx link;
-
-  link = alloc_INSN_LIST (insn, *insn_list);
-  *insn_list = link;
-
-  link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
-  *mem_list = link;
-
-  deps->pending_lists_length++;
-}
-
-/* Make a dependency between every memory reference on the pending lists
-   and INSN, thus flushing the pending lists.  If ONLY_WRITE, don't flush
-   the read list.  */
-
-static void
-flush_pending_lists (deps, insn, only_write)
-     struct deps *deps;
-     rtx insn;
-     int only_write;
-{
-  rtx u;
-  rtx link;
-
-  while (deps->pending_read_insns && ! only_write)
-    {
-      add_dependence (insn, XEXP (deps->pending_read_insns, 0),
-		      REG_DEP_ANTI);
-
-      link = deps->pending_read_insns;
-      deps->pending_read_insns = XEXP (deps->pending_read_insns, 1);
-      free_INSN_LIST_node (link);
-
-      link = deps->pending_read_mems;
-      deps->pending_read_mems = XEXP (deps->pending_read_mems, 1);
-      free_EXPR_LIST_node (link);
-    }
-  while (deps->pending_write_insns)
-    {
-      add_dependence (insn, XEXP (deps->pending_write_insns, 0),
-		      REG_DEP_ANTI);
-
-      link = deps->pending_write_insns;
-      deps->pending_write_insns = XEXP (deps->pending_write_insns, 1);
-      free_INSN_LIST_node (link);
-
-      link = deps->pending_write_mems;
-      deps->pending_write_mems = XEXP (deps->pending_write_mems, 1);
-      free_EXPR_LIST_node (link);
-    }
-  deps->pending_lists_length = 0;
-
-  /* last_pending_memory_flush is now a list of insns.  */
-  for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
-    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-  free_INSN_LIST_list (&deps->last_pending_memory_flush);
-  deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
-}
-
-/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
-   rtx, X, creating all dependencies generated by the write to the
-   destination of X, and reads of everything mentioned.  */
-
-static void
-sched_analyze_1 (deps, x, insn)
-     struct deps *deps;
-     rtx x;
-     rtx insn;
-{
-  register int regno;
-  register rtx dest = XEXP (x, 0);
-  enum rtx_code code = GET_CODE (x);
-
-  if (dest == 0)
-    return;
-
-  if (GET_CODE (dest) == PARALLEL
-      && GET_MODE (dest) == BLKmode)
-    {
-      register int i;
-      for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
-	sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
-      if (GET_CODE (x) == SET)
-	sched_analyze_2 (deps, SET_SRC (x), insn);
-      return;
-    }
-
-  while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
-	 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
-    {
-      if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
-	{
-	  /* The second and third arguments are values read by this insn.  */
-	  sched_analyze_2 (deps, XEXP (dest, 1), insn);
-	  sched_analyze_2 (deps, XEXP (dest, 2), insn);
-	}
-      dest = XEXP (dest, 0);
-    }
-
-  if (GET_CODE (dest) == REG)
-    {
-      register int i;
-
-      regno = REGNO (dest);
-
-      /* A hard reg in a wide mode may really be multiple registers.
-         If so, mark all of them just like the first.  */
-      if (regno < FIRST_PSEUDO_REGISTER)
-	{
-	  i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
-	  while (--i >= 0)
-	    {
-	      int r = regno + i;
-	      rtx u;
-
-	      for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
-		add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-	      for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
-		add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
-
-	      /* Clobbers need not be ordered with respect to one
-		 another, but sets must be ordered with respect to a
-		 pending clobber.  */
-	      if (code == SET)
-		{
-		  free_INSN_LIST_list (&deps->reg_last_uses[r]);
-		  for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
-		    add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
-		  SET_REGNO_REG_SET (reg_pending_sets, r);
-		}
-	      else
-		SET_REGNO_REG_SET (reg_pending_clobbers, r);
-
-	      /* Function calls clobber all call_used regs.  */
-	      if (global_regs[r] || (code == SET && call_used_regs[r]))
-		for (u = deps->last_function_call; u; u = XEXP (u, 1))
-		  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-	    }
-	}
-      else
-	{
-	  rtx u;
-
-	  for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
-	    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-	  for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
-	    add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
-
-	  if (code == SET)
-	    {
-	      free_INSN_LIST_list (&deps->reg_last_uses[regno]);
-	      for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
-		add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
-	      SET_REGNO_REG_SET (reg_pending_sets, regno);
-	    }
-	  else
-	    SET_REGNO_REG_SET (reg_pending_clobbers, regno);
-
-	  /* Pseudos that are REG_EQUIV to something may be replaced
-	     by that during reloading.  We need only add dependencies for
-	     the address in the REG_EQUIV note.  */
-	  if (!reload_completed
-	      && reg_known_equiv_p[regno]
-	      && GET_CODE (reg_known_value[regno]) == MEM)
-	    sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
-
-	  /* Don't let it cross a call after scheduling if it doesn't
-	     already cross one.  */
-
-	  if (REG_N_CALLS_CROSSED (regno) == 0)
-	    for (u = deps->last_function_call; u; u = XEXP (u, 1))
-	      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-	}
-    }
-  else if (GET_CODE (dest) == MEM)
-    {
-      /* Writing memory.  */
-
-      if (deps->pending_lists_length > 32)
-	{
-	  /* Flush all pending reads and writes to prevent the pending lists
-	     from getting any larger.  Insn scheduling runs too slowly when
-	     these lists get long.  The number 32 was chosen because it
-	     seems like a reasonable number.  When compiling GCC with itself,
-	     this flush occurs 8 times for sparc, and 10 times for m88k using
-	     the number 32.  */
-	  flush_pending_lists (deps, insn, 0);
-	}
-      else
-	{
-	  rtx u;
-	  rtx pending, pending_mem;
-
-	  pending = deps->pending_read_insns;
-	  pending_mem = deps->pending_read_mems;
-	  while (pending)
-	    {
-	      if (anti_dependence (XEXP (pending_mem, 0), dest))
-		add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
-
-	      pending = XEXP (pending, 1);
-	      pending_mem = XEXP (pending_mem, 1);
-	    }
-
-	  pending = deps->pending_write_insns;
-	  pending_mem = deps->pending_write_mems;
-	  while (pending)
-	    {
-	      if (output_dependence (XEXP (pending_mem, 0), dest))
-		add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
-
-	      pending = XEXP (pending, 1);
-	      pending_mem = XEXP (pending_mem, 1);
-	    }
-
-	  for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
-	    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-	  add_insn_mem_dependence (deps, &deps->pending_write_insns,
-				   &deps->pending_write_mems, insn, dest);
-	}
-      sched_analyze_2 (deps, XEXP (dest, 0), insn);
-    }
-
-  /* Analyze reads.  */
-  if (GET_CODE (x) == SET)
-    sched_analyze_2 (deps, SET_SRC (x), insn);
-}
-
-/* Analyze the uses of memory and registers in rtx X in INSN.  */
-
-static void
-sched_analyze_2 (deps, x, insn)
-     struct deps *deps;
-     rtx x;
-     rtx insn;
-{
-  register int i;
-  register int j;
-  register enum rtx_code code;
-  register const char *fmt;
-
-  if (x == 0)
-    return;
-
-  code = GET_CODE (x);
-
-  switch (code)
-    {
-    case CONST_INT:
-    case CONST_DOUBLE:
-    case SYMBOL_REF:
-    case CONST:
-    case LABEL_REF:
-      /* Ignore constants.  Note that we must handle CONST_DOUBLE here
-         because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
-         this does not mean that this insn is using cc0.  */
-      return;
-
-#ifdef HAVE_cc0
-    case CC0:
-      /* User of CC0 depends on immediately preceding insn.  */
-      set_sched_group_p (insn);
-      return;
-#endif
-
-    case REG:
-      {
-	rtx u;
-	int regno = REGNO (x);
-	if (regno < FIRST_PSEUDO_REGISTER)
-	  {
-	    int i;
-
-	    i = HARD_REGNO_NREGS (regno, GET_MODE (x));
-	    while (--i >= 0)
-	      {
-		int r = regno + i;
-		deps->reg_last_uses[r]
-		  = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
-
-		for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
-		  add_dependence (insn, XEXP (u, 0), 0);
-
-		/* ??? This should never happen.  */
-		for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
-		  add_dependence (insn, XEXP (u, 0), 0);
-
-		if (call_used_regs[r] || global_regs[r])
-		  /* Function calls clobber all call_used regs.  */
-		  for (u = deps->last_function_call; u; u = XEXP (u, 1))
-		    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-	      }
-	  }
-	else
-	  {
-	    deps->reg_last_uses[regno]
-	      = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
-
-	    for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
-	      add_dependence (insn, XEXP (u, 0), 0);
-
-	    /* ??? This should never happen.  */
-	    for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
-	      add_dependence (insn, XEXP (u, 0), 0);
-
-	    /* Pseudos that are REG_EQUIV to something may be replaced
-	       by that during reloading.  We need only add dependencies for
-	       the address in the REG_EQUIV note.  */
-	    if (!reload_completed
-		&& reg_known_equiv_p[regno]
-		&& GET_CODE (reg_known_value[regno]) == MEM)
-	      sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
-
-	    /* If the register does not already cross any calls, then add this
-	       insn to the sched_before_next_call list so that it will still
-	       not cross calls after scheduling.  */
-	    if (REG_N_CALLS_CROSSED (regno) == 0)
-	      add_dependence (deps->sched_before_next_call, insn,
-			      REG_DEP_ANTI);
-	  }
-	return;
-      }
-
-    case MEM:
-      {
-	/* Reading memory.  */
-	rtx u;
-	rtx pending, pending_mem;
-
-	pending = deps->pending_read_insns;
-	pending_mem = deps->pending_read_mems;
-	while (pending)
-	  {
-	    if (read_dependence (XEXP (pending_mem, 0), x))
-	      add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
-
-	    pending = XEXP (pending, 1);
-	    pending_mem = XEXP (pending_mem, 1);
-	  }
-
-	pending = deps->pending_write_insns;
-	pending_mem = deps->pending_write_mems;
-	while (pending)
-	  {
-	    if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
-				 x, rtx_varies_p))
-	      add_dependence (insn, XEXP (pending, 0), 0);
-
-	    pending = XEXP (pending, 1);
-	    pending_mem = XEXP (pending_mem, 1);
-	  }
-
-	for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
-	  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-	/* Always add these dependencies to pending_reads, since
-	   this insn may be followed by a write.  */
-	add_insn_mem_dependence (deps, &deps->pending_read_insns,
-				 &deps->pending_read_mems, insn, x);
-
-	/* Take advantage of tail recursion here.  */
-	sched_analyze_2 (deps, XEXP (x, 0), insn);
-	return;
-      }
-
-    /* Force pending stores to memory in case a trap handler needs them.  */
-    case TRAP_IF:
-      flush_pending_lists (deps, insn, 1);
-      break;
-
-    case ASM_OPERANDS:
-    case ASM_INPUT:
-    case UNSPEC_VOLATILE:
-      {
-	rtx u;
-
-	/* Traditional and volatile asm instructions must be considered to use
-	   and clobber all hard registers, all pseudo-registers and all of
-	   memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
-
-	   Consider for instance a volatile asm that changes the fpu rounding
-	   mode.  An insn should not be moved across this even if it only uses
-	   pseudo-regs because it might give an incorrectly rounded result.  */
-	if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
-	  {
-	    int max_reg = max_reg_num ();
-	    for (i = 0; i < max_reg; i++)
-	      {
-		for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
-		  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-		free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
-		for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
-		  add_dependence (insn, XEXP (u, 0), 0);
-
-		for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
-		  add_dependence (insn, XEXP (u, 0), 0);
-	      }
-	    reg_pending_sets_all = 1;
-
-	    flush_pending_lists (deps, insn, 0);
-	  }
-
-	/* For all ASM_OPERANDS, we must traverse the vector of input operands.
-	   We can not just fall through here since then we would be confused
-	   by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
-	   traditional asms unlike their normal usage.  */
-
-	if (code == ASM_OPERANDS)
-	  {
-	    for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
-	      sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
-	    return;
-	  }
-	break;
-      }
-
-    case PRE_DEC:
-    case POST_DEC:
-    case PRE_INC:
-    case POST_INC:
-      /* These both read and modify the result.  We must handle them as writes
-         to get proper dependencies for following instructions.  We must handle
-         them as reads to get proper dependencies from this to previous
-         instructions.  Thus we need to pass them to both sched_analyze_1
-         and sched_analyze_2.  We must call sched_analyze_2 first in order
-         to get the proper antecedent for the read.  */
-      sched_analyze_2 (deps, XEXP (x, 0), insn);
-      sched_analyze_1 (deps, x, insn);
-      return;
-
-    case POST_MODIFY:
-    case PRE_MODIFY:
-      /* op0 = op0 + op1 */
-      sched_analyze_2 (deps, XEXP (x, 0), insn);
-      sched_analyze_2 (deps, XEXP (x, 1), insn);
-      sched_analyze_1 (deps, x, insn);
-      return;
-
-    default:
-      break;
-    }
-
-  /* Other cases: walk the insn.  */
-  fmt = GET_RTX_FORMAT (code);
-  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
-    {
-      if (fmt[i] == 'e')
-	sched_analyze_2 (deps, XEXP (x, i), insn);
-      else if (fmt[i] == 'E')
-	for (j = 0; j < XVECLEN (x, i); j++)
-	  sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
-    }
-}
-
-/* Analyze an INSN with pattern X to find all dependencies.  */
-
-static void
-sched_analyze_insn (deps, x, insn, loop_notes)
-     struct deps *deps;
-     rtx x, insn;
-     rtx loop_notes;
-{
-  register RTX_CODE code = GET_CODE (x);
-  rtx link;
-  int maxreg = max_reg_num ();
-  int i;
-
-  if (code == COND_EXEC)
-    {
-      sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
-
-      /* ??? Should be recording conditions so we reduce the number of
-	 false dependancies.  */
-      x = COND_EXEC_CODE (x);
-      code = GET_CODE (x);
-    }
-  if (code == SET || code == CLOBBER)
-    sched_analyze_1 (deps, x, insn);
-  else if (code == PARALLEL)
-    {
-      register int i;
-      for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
-	{
-	  rtx sub = XVECEXP (x, 0, i);
-	  code = GET_CODE (sub);
-
-	  if (code == COND_EXEC)
-	    {
-	      sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
-	      sub = COND_EXEC_CODE (sub);
-	      code = GET_CODE (sub);
-	    }
-	  if (code == SET || code == CLOBBER)
-	    sched_analyze_1 (deps, sub, insn);
-	  else
-	    sched_analyze_2 (deps, sub, insn);
-	}
-    }
-  else
-    sched_analyze_2 (deps, x, insn);
-
-  /* Mark registers CLOBBERED or used by called function.  */
-  if (GET_CODE (insn) == CALL_INSN)
-    for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
-      {
-	if (GET_CODE (XEXP (link, 0)) == CLOBBER)
-	  sched_analyze_1 (deps, XEXP (link, 0), insn);
-	else
-	  sched_analyze_2 (deps, XEXP (link, 0), insn);
-      }
-
-  /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
-     block, then we must be sure that no instructions are scheduled across it.
-     Otherwise, the reg_n_refs info (which depends on loop_depth) would
-     become incorrect.  */
-
-  if (loop_notes)
-    {
-      int max_reg = max_reg_num ();
-      int schedule_barrier_found = 0;
-      rtx link;
-
-      /* Update loop_notes with any notes from this insn.  Also determine
-	 if any of the notes on the list correspond to instruction scheduling
-	 barriers (loop, eh & setjmp notes, but not range notes.  */
-      link = loop_notes;
-      while (XEXP (link, 1))
-	{
-	  if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
-	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
-	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
-	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
-	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
-	    schedule_barrier_found = 1;
-
-	  link = XEXP (link, 1);
-	}
-      XEXP (link, 1) = REG_NOTES (insn);
-      REG_NOTES (insn) = loop_notes;
-
-      /* Add dependencies if a scheduling barrier was found.  */
-      if (schedule_barrier_found)
-	{
-	  for (i = 0; i < max_reg; i++)
-	    {
-	      rtx u;
-	      for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
-		add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-	      free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
-	      for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
-		add_dependence (insn, XEXP (u, 0), 0);
-
-	      for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
-		add_dependence (insn, XEXP (u, 0), 0);
-	    }
-	  reg_pending_sets_all = 1;
-
-	  flush_pending_lists (deps, insn, 0);
-	}
-
-    }
-
-  /* Accumulate clobbers until the next set so that it will be output dependent
-     on all of them.  At the next set we can clear the clobber list, since
-     subsequent sets will be output dependent on it.  */
-  EXECUTE_IF_SET_IN_REG_SET
-    (reg_pending_sets, 0, i,
-     {
-       free_INSN_LIST_list (&deps->reg_last_sets[i]);
-       free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
-       deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
-     });
-  EXECUTE_IF_SET_IN_REG_SET
-    (reg_pending_clobbers, 0, i,
-     {
-       deps->reg_last_clobbers[i]
-	 = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
-     });
-  CLEAR_REG_SET (reg_pending_sets);
-  CLEAR_REG_SET (reg_pending_clobbers);
-
-  if (reg_pending_sets_all)
-    {
-      for (i = 0; i < maxreg; i++)
-	{
-	  free_INSN_LIST_list (&deps->reg_last_sets[i]);
-	  free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
-	  deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
-	}
-
-      reg_pending_sets_all = 0;
-    }
-
-  /* If a post-call group is still open, see if it should remain so.
-     This insn must be a simple move of a hard reg to a pseudo or
-     vice-versa.
-
-     We must avoid moving these insns for correctness on
-     SMALL_REGISTER_CLASS machines, and for special registers like
-     PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
-     hard regs for all targets.  */
-
-  if (deps->in_post_call_group_p)
-    {
-      rtx tmp, set = single_set (insn);
-      int src_regno, dest_regno;
-
-      if (set == NULL)
-	goto end_call_group;
-
-      tmp = SET_DEST (set);
-      if (GET_CODE (tmp) == SUBREG)
-	tmp = SUBREG_REG (tmp);
-      if (GET_CODE (tmp) == REG)
-	dest_regno = REGNO (tmp);
-      else
-	goto end_call_group;
-
-      tmp = SET_SRC (set);
-      if (GET_CODE (tmp) == SUBREG)
-	tmp = SUBREG_REG (tmp);
-      if (GET_CODE (tmp) == REG)
-	src_regno = REGNO (tmp);
-      else
-	goto end_call_group;
-
-      if (src_regno < FIRST_PSEUDO_REGISTER
-	  || dest_regno < FIRST_PSEUDO_REGISTER)
-	{
-	  set_sched_group_p (insn);
-	  CANT_MOVE (insn) = 1;
-	}
-      else
-	{
-	end_call_group:
-	  deps->in_post_call_group_p = 0;
-	}
-    }
-}
-
-/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
-   for every dependency.  */
-
-static void
-sched_analyze (deps, head, tail)
-     struct deps *deps;
-     rtx head, tail;
-{
-  register rtx insn;
-  register rtx u;
-  rtx loop_notes = 0;
-
-  for (insn = head;; insn = NEXT_INSN (insn))
-    {
-      if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
-	{
-	  /* Clear out the stale LOG_LINKS from flow.  */
-	  free_INSN_LIST_list (&LOG_LINKS (insn));
-
-	  /* Clear out stale SCHED_GROUP_P.  */
-	  SCHED_GROUP_P (insn) = 0;
-
-	  /* Make each JUMP_INSN a scheduling barrier for memory
-             references.  */
-	  if (GET_CODE (insn) == JUMP_INSN)
-	    deps->last_pending_memory_flush
-	      = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
-	  sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
-	  loop_notes = 0;
-	}
-      else if (GET_CODE (insn) == CALL_INSN)
-	{
-	  rtx x;
-	  register int i;
-
-	  /* Clear out stale SCHED_GROUP_P.  */
-	  SCHED_GROUP_P (insn) = 0;
-
-	  CANT_MOVE (insn) = 1;
-
-	  /* Clear out the stale LOG_LINKS from flow.  */
-	  free_INSN_LIST_list (&LOG_LINKS (insn));
-
-	  /* Any instruction using a hard register which may get clobbered
-	     by a call needs to be marked as dependent on this call.
-	     This prevents a use of a hard return reg from being moved
-	     past a void call (i.e. it does not explicitly set the hard
-	     return reg).  */
-
-	  /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
-	     all registers, not just hard registers, may be clobbered by this
-	     call.  */
-
-	  /* Insn, being a CALL_INSN, magically depends on
-	     `last_function_call' already.  */
-
-	  if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
-	      && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
-	    {
-	      int max_reg = max_reg_num ();
-	      for (i = 0; i < max_reg; i++)
-		{
-		  for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
-		    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-		  free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
-		  for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
-		    add_dependence (insn, XEXP (u, 0), 0);
-
-		  for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
-		    add_dependence (insn, XEXP (u, 0), 0);
-		}
-	      reg_pending_sets_all = 1;
-
-	      /* Add a pair of REG_SAVE_NOTEs which we will later
-		 convert back into a NOTE_INSN_SETJMP note.  See
-		 reemit_notes for why we use a pair of NOTEs.  */
-	      REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
-						  GEN_INT (0),
-						  REG_NOTES (insn));
-	      REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
-						  GEN_INT (NOTE_INSN_SETJMP),
-						  REG_NOTES (insn));
-	    }
-	  else
-	    {
-	      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
-		if (call_used_regs[i] || global_regs[i])
-		  {
-		    for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
-		      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-		    for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
-		      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
-		    SET_REGNO_REG_SET (reg_pending_clobbers, i);
-		  }
-	    }
-
-	  /* For each insn which shouldn't cross a call, add a dependence
-	     between that insn and this call insn.  */
-	  x = LOG_LINKS (deps->sched_before_next_call);
-	  while (x)
-	    {
-	      add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
-	      x = XEXP (x, 1);
-	    }
-	  free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call));
-
-	  sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
-	  loop_notes = 0;
-
-	  /* In the absence of interprocedural alias analysis, we must flush
-	     all pending reads and writes, and start new dependencies starting
-	     from here.  But only flush writes for constant calls (which may
-	     be passed a pointer to something we haven't written yet).  */
-	  flush_pending_lists (deps, insn, CONST_CALL_P (insn));
-
-	  /* Depend this function call (actually, the user of this
-	     function call) on all hard register clobberage.  */
-
-	  /* last_function_call is now a list of insns.  */
-	  free_INSN_LIST_list (&deps->last_function_call);
-	  deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
-
-	  /* Before reload, begin a post-call group, so as to keep the
-	     lifetimes of hard registers correct.  */
-	  if (! reload_completed)
-	    deps->in_post_call_group_p = 1;
-	}
-
-      /* See comments on reemit_notes as to why we do this.
-	 ??? Actually, the reemit_notes just say what is done, not why.  */
-
-      else if (GET_CODE (insn) == NOTE
-	       && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
-		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
-	{
-	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
-					loop_notes);
-	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
-					GEN_INT (NOTE_LINE_NUMBER (insn)),
-					loop_notes);
-	}
-      else if (GET_CODE (insn) == NOTE
-	       && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
-		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
-		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
-		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
-		   || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
-		       && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
-	{
-	  rtx rtx_region;
-
-	  if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
-	      || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
-	    rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
-	  else
-	    rtx_region = GEN_INT (0);
-
-	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
-					rtx_region,
-					loop_notes);
-	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
-					GEN_INT (NOTE_LINE_NUMBER (insn)),
-					loop_notes);
-	  CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
-	}
-
-      if (insn == tail)
-	return;
-    }
-  abort ();
-}
 
 /* Macros and functions for keeping the priority queue sorted, and
    dealing with queueing and dequeueing of instructions.  */
@@ -5305,25 +3973,6 @@ move_insn (insn, last)
   return retval;
 }
 
-/* Return an insn which represents a SCHED_GROUP, which is
-   the last insn in the group.  */
-
-static rtx
-group_leader (insn)
-     rtx insn;
-{
-  rtx prev;
-
-  do
-    {
-      prev = insn;
-      insn = next_nonnote_insn (insn);
-    }
-  while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
-
-  return prev;
-}
-
 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
    possibly bringing insns from subsequent blocks in the same region.  */
 
@@ -5545,117 +4194,6 @@ debug_reg_vector (s)
   fprintf (sched_dump, "\n");
 }
 
-/* Examine insns in the range [ HEAD, TAIL ] and Use the backward
-   dependences from LOG_LINKS to build forward dependences in
-   INSN_DEPEND.  */
-
-static void
-compute_forward_dependences (head, tail)
-     rtx head, tail;
-{
-  rtx insn, link;
-  rtx next_tail;
-  enum reg_note dep_type;
-
-  next_tail = NEXT_INSN (tail);
-  for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
-    {
-      if (! INSN_P (insn))
-	continue;
-
-      insn = group_leader (insn);
-
-      for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
-	{
-	  rtx x = group_leader (XEXP (link, 0));
-	  rtx new_link;
-
-	  if (x != XEXP (link, 0))
-	    continue;
-
-#ifdef ENABLE_CHECKING
-	  /* If add_dependence is working properly there should never
-	     be notes, deleted insns or duplicates in the backward
-	     links.  Thus we need not check for them here.
-
-	     However, if we have enabled checking we might as well go
-	     ahead and verify that add_dependence worked properly.  */
-	  if (GET_CODE (x) == NOTE
-	      || INSN_DELETED_P (x)
-	      || (forward_dependency_cache != NULL
-		  && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
-			       INSN_LUID (insn)))
-	      || (forward_dependency_cache == NULL
-		  && find_insn_list (insn, INSN_DEPEND (x))))
-	    abort ();
-	  if (forward_dependency_cache != NULL)
-	    SET_BIT (forward_dependency_cache[INSN_LUID (x)],
-		     INSN_LUID (insn));
-#endif
-
-	  new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
-
-	  dep_type = REG_NOTE_KIND (link);
-	  PUT_REG_NOTE_KIND (new_link, dep_type);
-
-	  INSN_DEPEND (x) = new_link;
-	  INSN_DEP_COUNT (insn) += 1;
-	}
-    }
-}
-
-/* Initialize variables for region data dependence analysis.
-   n_bbs is the number of region blocks.  */
-
-static void
-init_deps (deps)
-     struct deps *deps;
-{
-  int maxreg = max_reg_num ();
-  deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx));
-  deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx));
-  deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx));
-
-  deps->pending_read_insns = 0;
-  deps->pending_read_mems = 0;
-  deps->pending_write_insns = 0;
-  deps->pending_write_mems = 0;
-  deps->pending_lists_length = 0;
-  deps->last_pending_memory_flush = 0;
-  deps->last_function_call = 0;
-  deps->in_post_call_group_p = 0;
-
-  deps->sched_before_next_call
-    = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
-		    NULL_RTX, 0, NULL_RTX, NULL_RTX);
-  LOG_LINKS (deps->sched_before_next_call) = 0;
-}
-
-/* Free insn lists found in DEPS.  */
-
-static void
-free_deps (deps)
-     struct deps *deps;
-{
-  int max_reg = max_reg_num ();
-  int i;
-
-  /* Note this loop is executed max_reg * nr_regions times.  It's first
-     implementation accounted for over 90% of the calls to free_INSN_LIST_list.
-     The list was empty for the vast majority of those calls.  On the PA, not
-     calling free_INSN_LIST_list in those cases improves -O2 compile times by
-     3-5% on average.  */
-  for (i = 0; i < max_reg; ++i)
-    {
-      if (deps->reg_last_clobbers[i])
-	free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
-      if (deps->reg_last_sets[i])
-	free_INSN_LIST_list (&deps->reg_last_sets[i]);
-      if (deps->reg_last_uses[i])
-	free_INSN_LIST_list (&deps->reg_last_uses[i]);
-    }
-}
-
 /* Add dependences so that branches are scheduled to run last in their
    block.  */
 
@@ -6051,16 +4589,12 @@ schedule_region (rgn)
   int bb;
   int rgn_n_insns = 0;
   int sched_rgn_n_insns = 0;
-  regset_head reg_pending_sets_head;
-  regset_head reg_pending_clobbers_head;
 
   /* Set variables for the current region.  */
   current_nr_blocks = RGN_NR_BLOCKS (rgn);
   current_blocks = RGN_BLOCKS (rgn);
 
-  reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
-  reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
-  reg_pending_sets_all = 0;
+  init_deps_global ();
 
   /* Initializations for region data dependence analyisis.  */
   bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
@@ -6218,8 +4752,7 @@ schedule_region (rgn)
   /* Done with this region.  */
   free_pending_lists ();
 
-  FREE_REG_SET (reg_pending_sets);
-  FREE_REG_SET (reg_pending_clobbers);
+  finish_deps_global ();
 
   free (bb_deps);
 
diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c
new file mode 100644
index 0000000..7f9914c
--- /dev/null
+++ b/gcc/sched-deps.c
@@ -0,0 +1,1399 @@
+/* Instruction scheduling pass.  This file computes dependencies between
+   instructions.
+   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+   1999, 2000 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 GNU CC.
+
+GNU CC 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 2, or (at your option) any
+later version.
+
+GNU CC 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 GNU CC; see the file COPYING.  If not, write to the Free
+the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "toplev.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.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 "sched-int.h"
+
+extern char *reg_known_equiv_p;
+extern rtx *reg_known_value;
+
+static regset_head reg_pending_sets_head;
+static regset_head reg_pending_clobbers_head;
+
+static regset reg_pending_sets;
+static regset reg_pending_clobbers;
+static int reg_pending_sets_all;
+
+/* To speed up the test for duplicate dependency links we keep a
+   record of dependencies created by add_dependence when the average
+   number of instructions in a basic block is very large.
+
+   Studies have shown that there is typically around 5 instructions between
+   branches for typical C code.  So we can make a guess that the average
+   basic block is approximately 5 instructions long; we will choose 100X
+   the average size as a very large basic block.
+
+   Each insn has associated bitmaps for its dependencies.  Each bitmap
+   has enough entries to represent a dependency on any other insn in
+   the insn chain.  All bitmap for true dependencies cache is
+   allocated then the rest two ones are also allocated. */
+static sbitmap *true_dependency_cache;
+static sbitmap *anti_dependency_cache;
+static sbitmap *output_dependency_cache;
+
+/* To speed up checking consistency of formed forward insn
+   dependencies we use the following cache.  Another possible solution
+   could be switching off checking duplication of insns in forward
+   dependencies. */
+#ifdef ENABLE_CHECKING
+static sbitmap *forward_dependency_cache;
+#endif
+
+static void remove_dependence PARAMS ((rtx, rtx));
+static void set_sched_group_p PARAMS ((rtx));
+
+static void flush_pending_lists PARAMS ((struct deps *, rtx, int));
+static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
+static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
+static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
+static rtx group_leader PARAMS ((rtx));
+
+/* Return the INSN_LIST containing INSN in LIST, or NULL
+   if LIST does not contain INSN.  */
+
+HAIFA_INLINE rtx
+find_insn_list (insn, list)
+     rtx insn;
+     rtx list;
+{
+  while (list)
+    {
+      if (XEXP (list, 0) == insn)
+	return list;
+      list = XEXP (list, 1);
+    }
+  return 0;
+}
+
+/* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
+   otherwise.  */
+
+HAIFA_INLINE int
+find_insn_mem_list (insn, x, list, list1)
+     rtx insn, x;
+     rtx list, list1;
+{
+  while (list)
+    {
+      if (XEXP (list, 0) == insn
+	  && XEXP (list1, 0) == x)
+	return 1;
+      list = XEXP (list, 1);
+      list1 = XEXP (list1, 1);
+    }
+  return 0;
+}
+
+/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
+   LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the type
+   of dependence that this link represents.  */
+
+void
+add_dependence (insn, elem, dep_type)
+     rtx insn;
+     rtx elem;
+     enum reg_note dep_type;
+{
+  rtx link, next;
+  int present_p;
+  enum reg_note present_dep_type;
+
+  /* Don't depend an insn on itself.  */
+  if (insn == elem)
+    return;
+
+  /* We can get a dependency on deleted insns due to optimizations in
+     the register allocation and reloading or due to splitting.  Any
+     such dependency is useless and can be ignored.  */
+  if (GET_CODE (elem) == NOTE)
+    return;
+
+  /* If elem is part of a sequence that must be scheduled together, then
+     make the dependence point to the last insn of the sequence.
+     When HAVE_cc0, it is possible for NOTEs to exist between users and
+     setters of the condition codes, so we must skip past notes here.
+     Otherwise, NOTEs are impossible here.  */
+  next = next_nonnote_insn (elem);
+  if (next && SCHED_GROUP_P (next)
+      && GET_CODE (next) != CODE_LABEL)
+    {
+      /* Notes will never intervene here though, so don't bother checking
+         for them.  */
+      /* Hah!  Wrong.  */
+      /* We must reject CODE_LABELs, so that we don't get confused by one
+         that has LABEL_PRESERVE_P set, which is represented by the same
+         bit in the rtl as SCHED_GROUP_P.  A CODE_LABEL can never be
+         SCHED_GROUP_P.  */
+
+      rtx nnext;
+      while ((nnext = next_nonnote_insn (next)) != NULL
+	     && SCHED_GROUP_P (nnext)
+	     && GET_CODE (nnext) != CODE_LABEL)
+	next = nnext;
+
+      /* Again, don't depend an insn on itself.  */
+      if (insn == next)
+	return;
+
+      /* Make the dependence to NEXT, the last insn of the group, instead
+         of the original ELEM.  */
+      elem = next;
+    }
+
+  present_p = 1;
+#ifdef INSN_SCHEDULING
+  /* ??? No good way to tell from here whether we're doing interblock
+     scheduling.  Possibly add another callback.  */
+#if 0
+  /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
+     No need for interblock dependences with calls, since
+     calls are not moved between blocks.   Note: the edge where
+     elem is a CALL is still required.  */
+  if (GET_CODE (insn) == CALL_INSN
+      && (INSN_BB (elem) != INSN_BB (insn)))
+    return;
+#endif
+
+  /* If we already have a dependency for ELEM, then we do not need to
+     do anything.  Avoiding the list walk below can cut compile times
+     dramatically for some code.  */
+  if (true_dependency_cache != NULL)
+    {
+      if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
+	abort ();
+      if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
+	present_dep_type = 0;
+      else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
+			 INSN_LUID (elem)))
+	present_dep_type = REG_DEP_ANTI;
+      else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
+			 INSN_LUID (elem)))
+	present_dep_type = REG_DEP_OUTPUT;
+      else 
+	present_p = 0;
+      if (present_p && (int) dep_type >= (int) present_dep_type)
+	return;
+    }
+#endif
+
+  /* Check that we don't already have this dependence.  */
+  if (present_p)
+    for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+      if (XEXP (link, 0) == elem)
+	{
+#ifdef INSN_SCHEDULING
+	  /* Clear corresponding cache entry because type of the link
+             may be changed. */
+	  if (true_dependency_cache != NULL)
+	    {
+	      if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+		RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
+			   INSN_LUID (elem));
+	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
+		       && output_dependency_cache)
+		RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
+			   INSN_LUID (elem));
+	      else
+		abort ();
+	    }
+#endif
+
+	  /* If this is a more restrictive type of dependence than the existing
+	     one, then change the existing dependence to this type.  */
+	  if ((int) dep_type < (int) REG_NOTE_KIND (link))
+	    PUT_REG_NOTE_KIND (link, dep_type);
+	  
+#ifdef INSN_SCHEDULING
+	  /* If we are adding a dependency to INSN's LOG_LINKs, then
+	     note that in the bitmap caches of dependency information. */
+	  if (true_dependency_cache != NULL)
+	    {
+	      if ((int)REG_NOTE_KIND (link) == 0)
+		SET_BIT (true_dependency_cache[INSN_LUID (insn)],
+			 INSN_LUID (elem));
+	      else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+		SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
+			 INSN_LUID (elem));
+	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+		SET_BIT (output_dependency_cache[INSN_LUID (insn)],
+			 INSN_LUID (elem));
+	    }
+#endif
+	  return;
+      }
+  /* Might want to check one level of transitivity to save conses.  */
+
+  link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
+  LOG_LINKS (insn) = link;
+
+  /* Insn dependency, not data dependency.  */
+  PUT_REG_NOTE_KIND (link, dep_type);
+
+#ifdef INSN_SCHEDULING
+  /* If we are adding a dependency to INSN's LOG_LINKs, then note that
+     in the bitmap caches of dependency information. */
+  if (true_dependency_cache != NULL)
+    {
+      if ((int)dep_type == 0)
+	SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
+      else if (dep_type == REG_DEP_ANTI)
+	SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
+      else if (dep_type == REG_DEP_OUTPUT)
+	SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
+    }
+#endif
+}
+
+/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
+   of INSN.  Abort if not found.  */
+
+static void
+remove_dependence (insn, elem)
+     rtx insn;
+     rtx elem;
+{
+  rtx prev, link, next;
+  int found = 0;
+
+  for (prev = 0, link = LOG_LINKS (insn); link; link = next)
+    {
+      next = XEXP (link, 1);
+      if (XEXP (link, 0) == elem)
+	{
+	  if (prev)
+	    XEXP (prev, 1) = next;
+	  else
+	    LOG_LINKS (insn) = next;
+
+#ifdef INSN_SCHEDULING
+	  /* If we are removing a dependency from the LOG_LINKS list,
+	     make sure to remove it from the cache too.  */
+	  if (true_dependency_cache != NULL)
+	    {
+	      if (REG_NOTE_KIND (link) == 0)
+		RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
+			   INSN_LUID (elem));
+	      else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+		RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
+			   INSN_LUID (elem));
+	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+		RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
+			   INSN_LUID (elem));
+	    }
+#endif
+
+	  free_INSN_LIST_node (link);
+
+	  found = 1;
+	}
+      else
+	prev = link;
+    }
+
+  if (!found)
+    abort ();
+  return;
+}
+
+/* Return an insn which represents a SCHED_GROUP, which is
+   the last insn in the group.  */
+
+static rtx
+group_leader (insn)
+     rtx insn;
+{
+  rtx prev;
+
+  do
+    {
+      prev = insn;
+      insn = next_nonnote_insn (insn);
+    }
+  while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
+
+  return prev;
+}
+
+/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
+   goes along with that.  */
+
+static void
+set_sched_group_p (insn)
+     rtx insn;
+{
+  rtx link, prev;
+
+  SCHED_GROUP_P (insn) = 1;
+
+  /* There may be a note before this insn now, but all notes will
+     be removed before we actually try to schedule the insns, so
+     it won't cause a problem later.  We must avoid it here though.  */
+  prev = prev_nonnote_insn (insn);
+
+  /* Make a copy of all dependencies on the immediately previous insn,
+     and add to this insn.  This is so that all the dependencies will
+     apply to the group.  Remove an explicit dependence on this insn
+     as SCHED_GROUP_P now represents it.  */
+
+  if (find_insn_list (prev, LOG_LINKS (insn)))
+    remove_dependence (insn, prev);
+
+  for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
+    add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
+}
+
+/* Process an insn's memory dependencies.  There are four kinds of
+   dependencies:
+
+   (0) read dependence: read follows read
+   (1) true dependence: read follows write
+   (2) anti dependence: write follows read
+   (3) output dependence: write follows write
+
+   We are careful to build only dependencies which actually exist, and
+   use transitivity to avoid building too many links.  */
+
+/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
+   The MEM is a memory reference contained within INSN, which we are saving
+   so that we can do memory aliasing on it.  */
+
+void
+add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
+     struct deps *deps;
+     rtx *insn_list, *mem_list, insn, mem;
+{
+  register rtx link;
+
+  link = alloc_INSN_LIST (insn, *insn_list);
+  *insn_list = link;
+
+  link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
+  *mem_list = link;
+
+  deps->pending_lists_length++;
+}
+
+/* Make a dependency between every memory reference on the pending lists
+   and INSN, thus flushing the pending lists.  If ONLY_WRITE, don't flush
+   the read list.  */
+
+static void
+flush_pending_lists (deps, insn, only_write)
+     struct deps *deps;
+     rtx insn;
+     int only_write;
+{
+  rtx u;
+  rtx link;
+
+  while (deps->pending_read_insns && ! only_write)
+    {
+      add_dependence (insn, XEXP (deps->pending_read_insns, 0),
+		      REG_DEP_ANTI);
+
+      link = deps->pending_read_insns;
+      deps->pending_read_insns = XEXP (deps->pending_read_insns, 1);
+      free_INSN_LIST_node (link);
+
+      link = deps->pending_read_mems;
+      deps->pending_read_mems = XEXP (deps->pending_read_mems, 1);
+      free_EXPR_LIST_node (link);
+    }
+  while (deps->pending_write_insns)
+    {
+      add_dependence (insn, XEXP (deps->pending_write_insns, 0),
+		      REG_DEP_ANTI);
+
+      link = deps->pending_write_insns;
+      deps->pending_write_insns = XEXP (deps->pending_write_insns, 1);
+      free_INSN_LIST_node (link);
+
+      link = deps->pending_write_mems;
+      deps->pending_write_mems = XEXP (deps->pending_write_mems, 1);
+      free_EXPR_LIST_node (link);
+    }
+  deps->pending_lists_length = 0;
+
+  /* last_pending_memory_flush is now a list of insns.  */
+  for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
+    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+  free_INSN_LIST_list (&deps->last_pending_memory_flush);
+  deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
+}
+
+/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
+   rtx, X, creating all dependencies generated by the write to the
+   destination of X, and reads of everything mentioned.  */
+
+static void
+sched_analyze_1 (deps, x, insn)
+     struct deps *deps;
+     rtx x;
+     rtx insn;
+{
+  register int regno;
+  register rtx dest = XEXP (x, 0);
+  enum rtx_code code = GET_CODE (x);
+
+  if (dest == 0)
+    return;
+
+  if (GET_CODE (dest) == PARALLEL
+      && GET_MODE (dest) == BLKmode)
+    {
+      register int i;
+      for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
+	sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
+      if (GET_CODE (x) == SET)
+	sched_analyze_2 (deps, SET_SRC (x), insn);
+      return;
+    }
+
+  while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
+	 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
+    {
+      if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
+	{
+	  /* The second and third arguments are values read by this insn.  */
+	  sched_analyze_2 (deps, XEXP (dest, 1), insn);
+	  sched_analyze_2 (deps, XEXP (dest, 2), insn);
+	}
+      dest = XEXP (dest, 0);
+    }
+
+  if (GET_CODE (dest) == REG)
+    {
+      register int i;
+
+      regno = REGNO (dest);
+
+      /* A hard reg in a wide mode may really be multiple registers.
+         If so, mark all of them just like the first.  */
+      if (regno < FIRST_PSEUDO_REGISTER)
+	{
+	  i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
+	  while (--i >= 0)
+	    {
+	      int r = regno + i;
+	      rtx u;
+
+	      for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
+		add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+	      for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
+		add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
+
+	      /* Clobbers need not be ordered with respect to one
+		 another, but sets must be ordered with respect to a
+		 pending clobber.  */
+	      if (code == SET)
+		{
+		  free_INSN_LIST_list (&deps->reg_last_uses[r]);
+		  for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
+		    add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
+		  SET_REGNO_REG_SET (reg_pending_sets, r);
+		}
+	      else
+		SET_REGNO_REG_SET (reg_pending_clobbers, r);
+
+	      /* Function calls clobber all call_used regs.  */
+	      if (global_regs[r] || (code == SET && call_used_regs[r]))
+		for (u = deps->last_function_call; u; u = XEXP (u, 1))
+		  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+	    }
+	}
+      else
+	{
+	  rtx u;
+
+	  for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
+	    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+	  for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
+	    add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
+
+	  if (code == SET)
+	    {
+	      free_INSN_LIST_list (&deps->reg_last_uses[regno]);
+	      for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
+		add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
+	      SET_REGNO_REG_SET (reg_pending_sets, regno);
+	    }
+	  else
+	    SET_REGNO_REG_SET (reg_pending_clobbers, regno);
+
+	  /* Pseudos that are REG_EQUIV to something may be replaced
+	     by that during reloading.  We need only add dependencies for
+	     the address in the REG_EQUIV note.  */
+	  if (!reload_completed
+	      && reg_known_equiv_p[regno]
+	      && GET_CODE (reg_known_value[regno]) == MEM)
+	    sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
+
+	  /* Don't let it cross a call after scheduling if it doesn't
+	     already cross one.  */
+
+	  if (REG_N_CALLS_CROSSED (regno) == 0)
+	    for (u = deps->last_function_call; u; u = XEXP (u, 1))
+	      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+	}
+    }
+  else if (GET_CODE (dest) == MEM)
+    {
+      /* Writing memory.  */
+
+      if (deps->pending_lists_length > 32)
+	{
+	  /* Flush all pending reads and writes to prevent the pending lists
+	     from getting any larger.  Insn scheduling runs too slowly when
+	     these lists get long.  The number 32 was chosen because it
+	     seems like a reasonable number.  When compiling GCC with itself,
+	     this flush occurs 8 times for sparc, and 10 times for m88k using
+	     the number 32.  */
+	  flush_pending_lists (deps, insn, 0);
+	}
+      else
+	{
+	  rtx u;
+	  rtx pending, pending_mem;
+
+	  pending = deps->pending_read_insns;
+	  pending_mem = deps->pending_read_mems;
+	  while (pending)
+	    {
+	      if (anti_dependence (XEXP (pending_mem, 0), dest))
+		add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
+
+	      pending = XEXP (pending, 1);
+	      pending_mem = XEXP (pending_mem, 1);
+	    }
+
+	  pending = deps->pending_write_insns;
+	  pending_mem = deps->pending_write_mems;
+	  while (pending)
+	    {
+	      if (output_dependence (XEXP (pending_mem, 0), dest))
+		add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
+
+	      pending = XEXP (pending, 1);
+	      pending_mem = XEXP (pending_mem, 1);
+	    }
+
+	  for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
+	    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+	  add_insn_mem_dependence (deps, &deps->pending_write_insns,
+				   &deps->pending_write_mems, insn, dest);
+	}
+      sched_analyze_2 (deps, XEXP (dest, 0), insn);
+    }
+
+  /* Analyze reads.  */
+  if (GET_CODE (x) == SET)
+    sched_analyze_2 (deps, SET_SRC (x), insn);
+}
+
+/* Analyze the uses of memory and registers in rtx X in INSN.  */
+
+static void
+sched_analyze_2 (deps, x, insn)
+     struct deps *deps;
+     rtx x;
+     rtx insn;
+{
+  register int i;
+  register int j;
+  register enum rtx_code code;
+  register const char *fmt;
+
+  if (x == 0)
+    return;
+
+  code = GET_CODE (x);
+
+  switch (code)
+    {
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case CONST:
+    case LABEL_REF:
+      /* Ignore constants.  Note that we must handle CONST_DOUBLE here
+         because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
+         this does not mean that this insn is using cc0.  */
+      return;
+
+#ifdef HAVE_cc0
+    case CC0:
+      /* User of CC0 depends on immediately preceding insn.  */
+      set_sched_group_p (insn);
+      return;
+#endif
+
+    case REG:
+      {
+	rtx u;
+	int regno = REGNO (x);
+	if (regno < FIRST_PSEUDO_REGISTER)
+	  {
+	    int i;
+
+	    i = HARD_REGNO_NREGS (regno, GET_MODE (x));
+	    while (--i >= 0)
+	      {
+		int r = regno + i;
+		deps->reg_last_uses[r]
+		  = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
+
+		for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
+		  add_dependence (insn, XEXP (u, 0), 0);
+
+		/* ??? This should never happen.  */
+		for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
+		  add_dependence (insn, XEXP (u, 0), 0);
+
+		if (call_used_regs[r] || global_regs[r])
+		  /* Function calls clobber all call_used regs.  */
+		  for (u = deps->last_function_call; u; u = XEXP (u, 1))
+		    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+	      }
+	  }
+	else
+	  {
+	    deps->reg_last_uses[regno]
+	      = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
+
+	    for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
+	      add_dependence (insn, XEXP (u, 0), 0);
+
+	    /* ??? This should never happen.  */
+	    for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
+	      add_dependence (insn, XEXP (u, 0), 0);
+
+	    /* Pseudos that are REG_EQUIV to something may be replaced
+	       by that during reloading.  We need only add dependencies for
+	       the address in the REG_EQUIV note.  */
+	    if (!reload_completed
+		&& reg_known_equiv_p[regno]
+		&& GET_CODE (reg_known_value[regno]) == MEM)
+	      sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
+
+	    /* If the register does not already cross any calls, then add this
+	       insn to the sched_before_next_call list so that it will still
+	       not cross calls after scheduling.  */
+	    if (REG_N_CALLS_CROSSED (regno) == 0)
+	      add_dependence (deps->sched_before_next_call, insn,
+			      REG_DEP_ANTI);
+	  }
+	return;
+      }
+
+    case MEM:
+      {
+	/* Reading memory.  */
+	rtx u;
+	rtx pending, pending_mem;
+
+	pending = deps->pending_read_insns;
+	pending_mem = deps->pending_read_mems;
+	while (pending)
+	  {
+	    if (read_dependence (XEXP (pending_mem, 0), x))
+	      add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
+
+	    pending = XEXP (pending, 1);
+	    pending_mem = XEXP (pending_mem, 1);
+	  }
+
+	pending = deps->pending_write_insns;
+	pending_mem = deps->pending_write_mems;
+	while (pending)
+	  {
+	    if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
+				 x, rtx_varies_p))
+	      add_dependence (insn, XEXP (pending, 0), 0);
+
+	    pending = XEXP (pending, 1);
+	    pending_mem = XEXP (pending_mem, 1);
+	  }
+
+	for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
+	  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+	/* Always add these dependencies to pending_reads, since
+	   this insn may be followed by a write.  */
+	add_insn_mem_dependence (deps, &deps->pending_read_insns,
+				 &deps->pending_read_mems, insn, x);
+
+	/* Take advantage of tail recursion here.  */
+	sched_analyze_2 (deps, XEXP (x, 0), insn);
+	return;
+      }
+
+    /* Force pending stores to memory in case a trap handler needs them.  */
+    case TRAP_IF:
+      flush_pending_lists (deps, insn, 1);
+      break;
+
+    case ASM_OPERANDS:
+    case ASM_INPUT:
+    case UNSPEC_VOLATILE:
+      {
+	rtx u;
+
+	/* Traditional and volatile asm instructions must be considered to use
+	   and clobber all hard registers, all pseudo-registers and all of
+	   memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
+
+	   Consider for instance a volatile asm that changes the fpu rounding
+	   mode.  An insn should not be moved across this even if it only uses
+	   pseudo-regs because it might give an incorrectly rounded result.  */
+	if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
+	  {
+	    int max_reg = max_reg_num ();
+	    for (i = 0; i < max_reg; i++)
+	      {
+		for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
+		  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+		free_INSN_LIST_list (&deps->reg_last_uses[i]);
+
+		for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+		  add_dependence (insn, XEXP (u, 0), 0);
+
+		for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
+		  add_dependence (insn, XEXP (u, 0), 0);
+	      }
+	    reg_pending_sets_all = 1;
+
+	    flush_pending_lists (deps, insn, 0);
+	  }
+
+	/* For all ASM_OPERANDS, we must traverse the vector of input operands.
+	   We can not just fall through here since then we would be confused
+	   by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
+	   traditional asms unlike their normal usage.  */
+
+	if (code == ASM_OPERANDS)
+	  {
+	    for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
+	      sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
+	    return;
+	  }
+	break;
+      }
+
+    case PRE_DEC:
+    case POST_DEC:
+    case PRE_INC:
+    case POST_INC:
+      /* These both read and modify the result.  We must handle them as writes
+         to get proper dependencies for following instructions.  We must handle
+         them as reads to get proper dependencies from this to previous
+         instructions.  Thus we need to pass them to both sched_analyze_1
+         and sched_analyze_2.  We must call sched_analyze_2 first in order
+         to get the proper antecedent for the read.  */
+      sched_analyze_2 (deps, XEXP (x, 0), insn);
+      sched_analyze_1 (deps, x, insn);
+      return;
+
+    case POST_MODIFY:
+    case PRE_MODIFY:
+      /* op0 = op0 + op1 */
+      sched_analyze_2 (deps, XEXP (x, 0), insn);
+      sched_analyze_2 (deps, XEXP (x, 1), insn);
+      sched_analyze_1 (deps, x, insn);
+      return;
+
+    default:
+      break;
+    }
+
+  /* Other cases: walk the insn.  */
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	sched_analyze_2 (deps, XEXP (x, i), insn);
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
+    }
+}
+
+/* Analyze an INSN with pattern X to find all dependencies.  */
+
+static void
+sched_analyze_insn (deps, x, insn, loop_notes)
+     struct deps *deps;
+     rtx x, insn;
+     rtx loop_notes;
+{
+  register RTX_CODE code = GET_CODE (x);
+  rtx link;
+  int maxreg = max_reg_num ();
+  int i;
+
+  if (code == COND_EXEC)
+    {
+      sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
+
+      /* ??? Should be recording conditions so we reduce the number of
+	 false dependancies.  */
+      x = COND_EXEC_CODE (x);
+      code = GET_CODE (x);
+    }
+  if (code == SET || code == CLOBBER)
+    sched_analyze_1 (deps, x, insn);
+  else if (code == PARALLEL)
+    {
+      register int i;
+      for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+	{
+	  rtx sub = XVECEXP (x, 0, i);
+	  code = GET_CODE (sub);
+
+	  if (code == COND_EXEC)
+	    {
+	      sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
+	      sub = COND_EXEC_CODE (sub);
+	      code = GET_CODE (sub);
+	    }
+	  if (code == SET || code == CLOBBER)
+	    sched_analyze_1 (deps, sub, insn);
+	  else
+	    sched_analyze_2 (deps, sub, insn);
+	}
+    }
+  else
+    sched_analyze_2 (deps, x, insn);
+
+  /* Mark registers CLOBBERED or used by called function.  */
+  if (GET_CODE (insn) == CALL_INSN)
+    for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
+      {
+	if (GET_CODE (XEXP (link, 0)) == CLOBBER)
+	  sched_analyze_1 (deps, XEXP (link, 0), insn);
+	else
+	  sched_analyze_2 (deps, XEXP (link, 0), insn);
+      }
+
+  /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
+     block, then we must be sure that no instructions are scheduled across it.
+     Otherwise, the reg_n_refs info (which depends on loop_depth) would
+     become incorrect.  */
+
+  if (loop_notes)
+    {
+      int max_reg = max_reg_num ();
+      int schedule_barrier_found = 0;
+      rtx link;
+
+      /* Update loop_notes with any notes from this insn.  Also determine
+	 if any of the notes on the list correspond to instruction scheduling
+	 barriers (loop, eh & setjmp notes, but not range notes.  */
+      link = loop_notes;
+      while (XEXP (link, 1))
+	{
+	  if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
+	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
+	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
+	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
+	      || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
+	    schedule_barrier_found = 1;
+
+	  link = XEXP (link, 1);
+	}
+      XEXP (link, 1) = REG_NOTES (insn);
+      REG_NOTES (insn) = loop_notes;
+
+      /* Add dependencies if a scheduling barrier was found.  */
+      if (schedule_barrier_found)
+	{
+	  for (i = 0; i < max_reg; i++)
+	    {
+	      rtx u;
+	      for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
+		add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+	      free_INSN_LIST_list (&deps->reg_last_uses[i]);
+
+	      for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+		add_dependence (insn, XEXP (u, 0), 0);
+
+	      for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
+		add_dependence (insn, XEXP (u, 0), 0);
+	    }
+	  reg_pending_sets_all = 1;
+
+	  flush_pending_lists (deps, insn, 0);
+	}
+
+    }
+
+  /* Accumulate clobbers until the next set so that it will be output dependent
+     on all of them.  At the next set we can clear the clobber list, since
+     subsequent sets will be output dependent on it.  */
+  EXECUTE_IF_SET_IN_REG_SET
+    (reg_pending_sets, 0, i,
+     {
+       free_INSN_LIST_list (&deps->reg_last_sets[i]);
+       free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
+       deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
+     });
+  EXECUTE_IF_SET_IN_REG_SET
+    (reg_pending_clobbers, 0, i,
+     {
+       deps->reg_last_clobbers[i]
+	 = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
+     });
+  CLEAR_REG_SET (reg_pending_sets);
+  CLEAR_REG_SET (reg_pending_clobbers);
+
+  if (reg_pending_sets_all)
+    {
+      for (i = 0; i < maxreg; i++)
+	{
+	  free_INSN_LIST_list (&deps->reg_last_sets[i]);
+	  free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
+	  deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
+	}
+
+      reg_pending_sets_all = 0;
+    }
+
+  /* If a post-call group is still open, see if it should remain so.
+     This insn must be a simple move of a hard reg to a pseudo or
+     vice-versa.
+
+     We must avoid moving these insns for correctness on
+     SMALL_REGISTER_CLASS machines, and for special registers like
+     PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
+     hard regs for all targets.  */
+
+  if (deps->in_post_call_group_p)
+    {
+      rtx tmp, set = single_set (insn);
+      int src_regno, dest_regno;
+
+      if (set == NULL)
+	goto end_call_group;
+
+      tmp = SET_DEST (set);
+      if (GET_CODE (tmp) == SUBREG)
+	tmp = SUBREG_REG (tmp);
+      if (GET_CODE (tmp) == REG)
+	dest_regno = REGNO (tmp);
+      else
+	goto end_call_group;
+
+      tmp = SET_SRC (set);
+      if (GET_CODE (tmp) == SUBREG)
+	tmp = SUBREG_REG (tmp);
+      if (GET_CODE (tmp) == REG)
+	src_regno = REGNO (tmp);
+      else
+	goto end_call_group;
+
+      if (src_regno < FIRST_PSEUDO_REGISTER
+	  || dest_regno < FIRST_PSEUDO_REGISTER)
+	{
+	  set_sched_group_p (insn);
+	  CANT_MOVE (insn) = 1;
+	}
+      else
+	{
+	end_call_group:
+	  deps->in_post_call_group_p = 0;
+	}
+    }
+}
+
+/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
+   for every dependency.  */
+
+void
+sched_analyze (deps, head, tail)
+     struct deps *deps;
+     rtx head, tail;
+{
+  register rtx insn;
+  register rtx u;
+  rtx loop_notes = 0;
+
+  for (insn = head;; insn = NEXT_INSN (insn))
+    {
+      if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
+	{
+	  /* Clear out the stale LOG_LINKS from flow.  */
+	  free_INSN_LIST_list (&LOG_LINKS (insn));
+
+	  /* Clear out stale SCHED_GROUP_P.  */
+	  SCHED_GROUP_P (insn) = 0;
+
+	  /* Make each JUMP_INSN a scheduling barrier for memory
+             references.  */
+	  if (GET_CODE (insn) == JUMP_INSN)
+	    deps->last_pending_memory_flush
+	      = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
+	  sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
+	  loop_notes = 0;
+	}
+      else if (GET_CODE (insn) == CALL_INSN)
+	{
+	  rtx x;
+	  register int i;
+
+	  /* Clear out stale SCHED_GROUP_P.  */
+	  SCHED_GROUP_P (insn) = 0;
+
+	  CANT_MOVE (insn) = 1;
+
+	  /* Clear out the stale LOG_LINKS from flow.  */
+	  free_INSN_LIST_list (&LOG_LINKS (insn));
+
+	  /* Any instruction using a hard register which may get clobbered
+	     by a call needs to be marked as dependent on this call.
+	     This prevents a use of a hard return reg from being moved
+	     past a void call (i.e. it does not explicitly set the hard
+	     return reg).  */
+
+	  /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
+	     all registers, not just hard registers, may be clobbered by this
+	     call.  */
+
+	  /* Insn, being a CALL_INSN, magically depends on
+	     `last_function_call' already.  */
+
+	  if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
+	      && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
+	    {
+	      int max_reg = max_reg_num ();
+	      for (i = 0; i < max_reg; i++)
+		{
+		  for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
+		    add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+		  free_INSN_LIST_list (&deps->reg_last_uses[i]);
+
+		  for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+		    add_dependence (insn, XEXP (u, 0), 0);
+
+		  for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
+		    add_dependence (insn, XEXP (u, 0), 0);
+		}
+	      reg_pending_sets_all = 1;
+
+	      /* Add a pair of REG_SAVE_NOTEs which we will later
+		 convert back into a NOTE_INSN_SETJMP note.  See
+		 reemit_notes for why we use a pair of NOTEs.  */
+	      REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
+						  GEN_INT (0),
+						  REG_NOTES (insn));
+	      REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
+						  GEN_INT (NOTE_INSN_SETJMP),
+						  REG_NOTES (insn));
+	    }
+	  else
+	    {
+	      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+		if (call_used_regs[i] || global_regs[i])
+		  {
+		    for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
+		      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+		    for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+		      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+		    SET_REGNO_REG_SET (reg_pending_clobbers, i);
+		  }
+	    }
+
+	  /* For each insn which shouldn't cross a call, add a dependence
+	     between that insn and this call insn.  */
+	  x = LOG_LINKS (deps->sched_before_next_call);
+	  while (x)
+	    {
+	      add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
+	      x = XEXP (x, 1);
+	    }
+	  free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call));
+
+	  sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
+	  loop_notes = 0;
+
+	  /* In the absence of interprocedural alias analysis, we must flush
+	     all pending reads and writes, and start new dependencies starting
+	     from here.  But only flush writes for constant calls (which may
+	     be passed a pointer to something we haven't written yet).  */
+	  flush_pending_lists (deps, insn, CONST_CALL_P (insn));
+
+	  /* Depend this function call (actually, the user of this
+	     function call) on all hard register clobberage.  */
+
+	  /* last_function_call is now a list of insns.  */
+	  free_INSN_LIST_list (&deps->last_function_call);
+	  deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
+
+	  /* Before reload, begin a post-call group, so as to keep the
+	     lifetimes of hard registers correct.  */
+	  if (! reload_completed)
+	    deps->in_post_call_group_p = 1;
+	}
+
+      /* See comments on reemit_notes as to why we do this.
+	 ??? Actually, the reemit_notes just say what is done, not why.  */
+
+      else if (GET_CODE (insn) == NOTE
+	       && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
+	{
+	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
+					loop_notes);
+	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
+					GEN_INT (NOTE_LINE_NUMBER (insn)),
+					loop_notes);
+	}
+      else if (GET_CODE (insn) == NOTE
+	       && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
+		   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
+		   || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
+		       && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
+	{
+	  rtx rtx_region;
+
+	  if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
+	      || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
+	    rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
+	  else
+	    rtx_region = GEN_INT (0);
+
+	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
+					rtx_region,
+					loop_notes);
+	  loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
+					GEN_INT (NOTE_LINE_NUMBER (insn)),
+					loop_notes);
+	  CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
+	}
+
+      if (insn == tail)
+	return;
+    }
+  abort ();
+}
+
+/* Examine insns in the range [ HEAD, TAIL ] and Use the backward
+   dependences from LOG_LINKS to build forward dependences in
+   INSN_DEPEND.  */
+
+void
+compute_forward_dependences (head, tail)
+     rtx head, tail;
+{
+  rtx insn, link;
+  rtx next_tail;
+  enum reg_note dep_type;
+
+  next_tail = NEXT_INSN (tail);
+  for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+    {
+      if (! INSN_P (insn))
+	continue;
+
+      insn = group_leader (insn);
+
+      for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+	{
+	  rtx x = group_leader (XEXP (link, 0));
+	  rtx new_link;
+
+	  if (x != XEXP (link, 0))
+	    continue;
+
+#ifdef ENABLE_CHECKING
+	  /* If add_dependence is working properly there should never
+	     be notes, deleted insns or duplicates in the backward
+	     links.  Thus we need not check for them here.
+
+	     However, if we have enabled checking we might as well go
+	     ahead and verify that add_dependence worked properly.  */
+	  if (GET_CODE (x) == NOTE
+	      || INSN_DELETED_P (x)
+	      || (forward_dependency_cache != NULL
+		  && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
+			       INSN_LUID (insn)))
+	      || (forward_dependency_cache == NULL
+		  && find_insn_list (insn, INSN_DEPEND (x))))
+	    abort ();
+	  if (forward_dependency_cache != NULL)
+	    SET_BIT (forward_dependency_cache[INSN_LUID (x)],
+		     INSN_LUID (insn));
+#endif
+
+	  new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
+
+	  dep_type = REG_NOTE_KIND (link);
+	  PUT_REG_NOTE_KIND (new_link, dep_type);
+
+	  INSN_DEPEND (x) = new_link;
+	  INSN_DEP_COUNT (insn) += 1;
+	}
+    }
+}
+
+/* Initialize variables for region data dependence analysis.
+   n_bbs is the number of region blocks.  */
+
+void
+init_deps (deps)
+     struct deps *deps;
+{
+  int maxreg = max_reg_num ();
+  deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx));
+  deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx));
+  deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx));
+
+  deps->pending_read_insns = 0;
+  deps->pending_read_mems = 0;
+  deps->pending_write_insns = 0;
+  deps->pending_write_mems = 0;
+  deps->pending_lists_length = 0;
+  deps->last_pending_memory_flush = 0;
+  deps->last_function_call = 0;
+  deps->in_post_call_group_p = 0;
+
+  deps->sched_before_next_call
+    = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
+		    NULL_RTX, 0, NULL_RTX, NULL_RTX);
+  LOG_LINKS (deps->sched_before_next_call) = 0;
+}
+
+/* Free insn lists found in DEPS.  */
+
+void
+free_deps (deps)
+     struct deps *deps;
+{
+  int max_reg = max_reg_num ();
+  int i;
+
+  /* Note this loop is executed max_reg * nr_regions times.  It's first
+     implementation accounted for over 90% of the calls to free_INSN_LIST_list.
+     The list was empty for the vast majority of those calls.  On the PA, not
+     calling free_INSN_LIST_list in those cases improves -O2 compile times by
+     3-5% on average.  */
+  for (i = 0; i < max_reg; ++i)
+    {
+      if (deps->reg_last_clobbers[i])
+	free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
+      if (deps->reg_last_sets[i])
+	free_INSN_LIST_list (&deps->reg_last_sets[i]);
+      if (deps->reg_last_uses[i])
+	free_INSN_LIST_list (&deps->reg_last_uses[i]);
+    }
+}
+
+/* If it is profitable to use them, initialize caches for tracking
+   dependency informatino.  LUID is the number of insns to be scheduled,
+   it is used in the estimate of profitability.  */
+
+void
+init_dependency_caches (luid)
+     int luid;
+{
+  /* ?!? We could save some memory by computing a per-region luid mapping
+     which could reduce both the number of vectors in the cache and the size
+     of each vector.  Instead we just avoid the cache entirely unless the
+     average number of instructions in a basic block is very high.  See
+     the comment before the declaration of true_dependency_cache for
+     what we consider "very high".  */
+  if (luid / n_basic_blocks > 100 * 5)
+    {
+      true_dependency_cache = sbitmap_vector_alloc (luid, luid);
+      sbitmap_vector_zero (true_dependency_cache, luid);
+      anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
+      sbitmap_vector_zero (anti_dependency_cache, luid);
+      output_dependency_cache = sbitmap_vector_alloc (luid, luid);
+      sbitmap_vector_zero (output_dependency_cache, luid);
+#ifdef ENABLE_CHECKING
+      forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
+      sbitmap_vector_zero (forward_dependency_cache, luid);
+#endif
+    }
+}
+
+/* Free the caches allocated in init_dependency_caches.  */
+
+void
+free_dependency_caches ()
+{
+  if (true_dependency_cache)
+    {
+      free (true_dependency_cache);
+      true_dependency_cache = NULL;
+      free (anti_dependency_cache);
+      anti_dependency_cache = NULL;
+      free (output_dependency_cache);
+      output_dependency_cache = NULL;
+#ifdef ENABLE_CHECKING
+      free (forward_dependency_cache);
+      forward_dependency_cache = NULL;
+#endif
+    }
+}
+
+/* Initialize some global variables needed by the dependency analysis
+   code.  */
+
+void
+init_deps_global ()
+{
+  reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
+  reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
+  reg_pending_sets_all = 0;
+}
+
+/* Free everything used by the dependency analysis code.  */
+
+void
+finish_deps_global ()
+{
+  FREE_REG_SET (reg_pending_sets);
+  FREE_REG_SET (reg_pending_clobbers);
+}
diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index bf14faa..faa4a8b 100644
--- a/gcc/sched-int.h
+++ b/gcc/sched-int.h
@@ -23,6 +23,70 @@ the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 /* Forward declaration.  */
 struct ready_list;
 
+/* Describe state of dependencies used during sched_analyze phase.  */
+struct deps
+{
+  /* The *_insns and *_mems are paired lists.  Each pending memory operation
+     will have a pointer to the MEM rtx on one list and a pointer to the
+     containing insn on the other list in the same place in the list.  */
+
+  /* We can't use add_dependence like the old code did, because a single insn
+     may have multiple memory accesses, and hence needs to be on the list
+     once for each memory access.  Add_dependence won't let you add an insn
+     to a list more than once.  */
+
+  /* An INSN_LIST containing all insns with pending read operations.  */
+  rtx pending_read_insns;
+
+  /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
+  rtx pending_read_mems;
+
+  /* An INSN_LIST containing all insns with pending write operations.  */
+  rtx pending_write_insns;
+
+  /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
+  rtx pending_write_mems;
+
+  /* Indicates the combined length of the two pending lists.  We must prevent
+     these lists from ever growing too large since the number of dependencies
+     produced is at least O(N*N), and execution time is at least O(4*N*N), as
+     a function of the length of these pending lists.  */
+  int pending_lists_length;
+
+  /* The last insn upon which all memory references must depend.
+     This is an insn which flushed the pending lists, creating a dependency
+     between it and all previously pending memory references.  This creates
+     a barrier (or a checkpoint) which no memory reference is allowed to cross.
+
+     This includes all non constant CALL_INSNs.  When we do interprocedural
+     alias analysis, this restriction can be relaxed.
+     This may also be an INSN that writes memory if the pending lists grow
+     too large.  */
+  rtx last_pending_memory_flush;
+
+  /* The last function call we have seen.  All hard regs, and, of course,
+     the last function call, must depend on this.  */
+  rtx last_function_call;
+
+  /* Used to keep post-call psuedo/hard reg movements together with
+     the call.  */
+  int in_post_call_group_p;
+
+  /* The LOG_LINKS field of this is a list of insns which use a pseudo
+     register that does not already cross a call.  We create
+     dependencies between each of those insn and the next call insn,
+     to ensure that they won't cross a call after scheduling is done.  */
+  rtx sched_before_next_call;
+
+  /* Element N is the next insn that sets (hard or pseudo) register
+     N within the current basic block; or zero, if there is no
+     such insn.  Needed for new registers which may be introduced
+     by splitting insns.  */
+  rtx *reg_last_uses;
+  rtx *reg_last_sets;
+  rtx *reg_last_clobbers;
+};
+
 /* This structure holds some state of the current scheduling pass, and
    contains some function pointers that abstract out some of the non-generic
    functionality from functions such as schedule_block or schedule_insn.
@@ -63,6 +127,71 @@ struct sched_info
   int queue_must_finish_empty;
 };
 
+extern struct sched_info *current_sched_info;
+
+/* Indexed by INSN_UID, the collection of all data associated with
+   a single instruction.  */
+
+struct haifa_insn_data
+{
+  /* A list of insns which depend on the instruction.  Unlike LOG_LINKS,
+     it represents forward dependancies.  */
+  rtx depend;
+
+  /* The line number note in effect for each insn.  For line number
+     notes, this indicates whether the note may be reused.  */
+  rtx line_note;
+
+  /* Logical uid gives the original ordering of the insns.  */
+  int luid;
+
+  /* A priority for each insn.  */
+  int priority;
+
+  /* The number of incoming edges in the forward dependency graph.
+     As scheduling proceds, counts are decreased.  An insn moves to
+     the ready queue when its counter reaches zero.  */
+  int dep_count;
+
+  /* An encoding of the blockage range function.  Both unit and range
+     are coded.  */
+  unsigned int blockage;
+
+  /* Number of instructions referring to this insn.  */
+  int ref_count;
+
+  /* The minimum clock tick at which the insn becomes ready.  This is
+     used to note timing constraints for the insns in the pending list.  */
+  int tick;
+
+  short cost;
+
+  /* An encoding of the function units used.  */
+  short units;
+
+  /* This weight is an estimation of the insn's contribution to
+     register pressure.  */
+  short reg_weight;
+
+  /* Some insns (e.g. call) are not allowed to move across blocks.  */
+  unsigned int cant_move : 1;
+
+  /* Set if there's DEF-USE dependance between some speculatively
+     moved load insn and this one.  */
+  unsigned int fed_by_spec_load : 1;
+  unsigned int is_load_insn : 1;
+};
+
+extern struct haifa_insn_data *h_i_d;
+
+/* Accessor macros for h_i_d.  There are more in haifa-sched.c.  */
+#define INSN_DEPEND(INSN)	(h_i_d[INSN_UID (INSN)].depend)
+#define INSN_LUID(INSN)		(h_i_d[INSN_UID (INSN)].luid)
+#define CANT_MOVE(insn)		(h_i_d[INSN_UID (insn)].cant_move)
+#define INSN_DEP_COUNT(INSN)	(h_i_d[INSN_UID (INSN)].dep_count)
+
+extern FILE *sched_dump;
+
 #ifndef __GNUC__
 #define __inline
 #endif
@@ -70,3 +199,35 @@ struct sched_info
 #ifndef HAIFA_INLINE
 #define HAIFA_INLINE __inline
 #endif
+
+/* Functions in sched-vis.c.  */
+extern void init_target_units PARAMS ((void));
+extern void insn_print_units PARAMS ((rtx));
+extern void init_block_visualization PARAMS ((void));
+extern void print_block_visualization PARAMS ((const char *));
+extern void visualize_scheduled_insns PARAMS ((int));
+extern void visualize_no_unit PARAMS ((rtx));
+extern void visualize_stall_cycles PARAMS ((int));
+extern void visualize_alloc PARAMS ((void));
+extern void visualize_free PARAMS ((void));
+
+/* Functions in sched-deps.c.  */
+extern void add_dependence PARAMS ((rtx, rtx, enum reg_note));
+extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
+					     rtx));
+extern void sched_analyze PARAMS ((struct deps *, rtx, rtx));
+extern void init_deps PARAMS ((struct deps *));
+extern void free_deps PARAMS ((struct deps *));
+extern void init_deps_global PARAMS ((void));
+extern void finish_deps_global PARAMS ((void));
+extern void compute_forward_dependences PARAMS ((rtx, rtx));
+extern int find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx));
+extern rtx find_insn_list PARAMS ((rtx, rtx));
+extern void init_dependency_caches PARAMS ((int));
+extern void free_dependency_caches PARAMS ((void));
+
+/* Functions in haifa-sched.c.  */
+extern int insn_unit PARAMS ((rtx));
+extern rtx get_unit_last_insn PARAMS ((int));
+extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
+