Some Haifa scheduler bugs

[Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>]

I've run c-torture on the egcs snapshot, using the Haifa scheduler with
all flags turned on. My system is an i586-linux one. Here's a patch to fix
some of the failures.

There seems to be at least one additional problem, which I haven't really
investigated yet. It appears as if the scheduler extends the lifetime of
hard registers, which is deadly on SMALL_REGISTER_CLASSES machines. More
specifically, the broken code looks like this:

	call somefunction
	do a multiplication; clobbers eax
	movl eax,ebx

while the correct code moves eax to ebx directly after the call. I have not
found any code in either haifa-sched.c or sched.c to prevent this problem,
so it's quite possible that the normal scheduler may also suffer from this.

	* haifa-sched.c (target_bb, bbset_size, dom, prob, rgn_nr_edges,
	rgn_edges, edgeset_size, edge_to_bit, pot_split, ancestor_edges):
	Make static.
	(move_insn): Call reemit_notes for every insn in a SCHED_GROUP.
	(schedule_block): When checking whether an insn is the 
	basic_block_head of a different block, use the first insn in the
	same SCHED_GROUP instead of the insn itself.
	(debug_dependencies): GET_RTX_NAME takes an rtx code, not an rtx.

*** haifa-sched.c.orig-1	Mon Aug 18 13:03:47 1997
--- haifa-sched.c	Mon Aug 18 21:00:48 1997
*************** int *bblst_table, bblst_size, bblst_last
*** 626,632 ****
  #define SRC_PROB(src) ( candidate_table[src].src_prob )
  
  /* The bb being currently scheduled.  */
! int target_bb;
  
  /* List of edges.  */
  typedef bitlst edgelst;
--- 626,632 ----
  #define SRC_PROB(src) ( candidate_table[src].src_prob )
  
  /* The bb being currently scheduled.  */
! static int target_bb;
  
  /* List of edges.  */
  typedef bitlst edgelst;
*************** void debug_candidates PROTO ((int));
*** 642,652 ****
  typedef bitset bbset;
  
  /* Number of words of the bbset.  */
! int bbset_size;
  
  /* Dominators array: dom[i] contains the bbset of dominators of
     bb i in the region.  */
! bbset *dom;
  
  /* bb 0 is the only region entry */
  #define IS_RGN_ENTRY(bb) (!bb)
--- 642,652 ----
  typedef bitset bbset;
  
  /* Number of words of the bbset.  */
! static int bbset_size;
  
  /* Dominators array: dom[i] contains the bbset of dominators of
     bb i in the region.  */
! static bbset *dom;
  
  /* bb 0 is the only region entry */
  #define IS_RGN_ENTRY(bb) (!bb)
*************** bbset *dom;
*** 657,663 ****
  
  /* Probability: Prob[i] is a float in [0, 1] which is the probability
     of bb i relative to the region entry.  */
! float *prob;
  
  /*  The probability of bb_src, relative to bb_trg.  Note, that while the
     'prob[bb]' is a float in [0, 1], this macro returns an integer
--- 657,663 ----
  
  /* Probability: Prob[i] is a float in [0, 1] which is the probability
     of bb i relative to the region entry.  */
! static float *prob;
  
  /*  The probability of bb_src, relative to bb_trg.  Note, that while the
     'prob[bb]' is a float in [0, 1], this macro returns an integer
*************** float *prob;
*** 669,684 ****
  typedef bitset edgeset;
  
  /* Number of edges in the region.  */
! int rgn_nr_edges;
  
  /* Array of size rgn_nr_edges.    */
! int *rgn_edges;
  
  /* Number of words in an edgeset.    */
! int edgeset_size;
  
  /* Mapping from each edge in the graph to its number in the rgn.  */
! int *edge_to_bit;
  #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
  
  /* The split edges of a source bb is different for each target
--- 669,684 ----
  typedef bitset edgeset;
  
  /* Number of edges in the region.  */
! static int rgn_nr_edges;
  
  /* Array of size rgn_nr_edges.    */
! static int *rgn_edges;
  
  /* Number of words in an edgeset.    */
! static int edgeset_size;
  
  /* Mapping from each edge in the graph to its number in the rgn.  */
! static int *edge_to_bit;
  #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
  
  /* The split edges of a source bb is different for each target
*************** int *edge_to_bit;
*** 687,696 ****
     the split edges of each bb relative to the region entry.
  
     pot_split[bb] is the set of potential split edges of bb.  */
! edgeset *pot_split;
  
  /* For every bb, a set of its ancestor edges.  */
! edgeset *ancestor_edges;
  
  static void compute_dom_prob_ps PROTO ((int));
  
--- 687,696 ----
     the split edges of each bb relative to the region entry.
  
     pot_split[bb] is the set of potential split edges of bb.  */
! static edgeset *pot_split;
  
  /* For every bb, a set of its ancestor edges.  */
! static edgeset *ancestor_edges;
  
  static void compute_dom_prob_ps PROTO ((int));
  
*************** build_control_flow ()
*** 1277,1284 ****
  /* construct edges in the control flow graph, from 'source' block, to
     blocks refered to by 'pattern'.  */
  
! static
! void 
  build_jmp_edges (pattern, source)
       rtx pattern;
       int source;
--- 1277,1283 ----
  /* construct edges in the control flow graph, from 'source' block, to
     blocks refered to by 'pattern'.  */
  
! static void
  build_jmp_edges (pattern, source)
       rtx pattern;
       int source;
*************** move_insn (insn, last)
*** 6512,6520 ****
        move_insn1 (insn, last);
        insn = prev;
      }
- 
    move_insn1 (insn, last);
!   return reemit_notes (new_last, new_last);
  }
  
  /* Return an insn which represents a SCHED_GROUP, which is
--- 6511,6524 ----
        move_insn1 (insn, last);
        insn = prev;
      }
    move_insn1 (insn, last);
!   while (insn != new_last)
!     {
!       rtx next = NEXT_INSN (insn);
!       reemit_notes (insn, insn);
!       insn = next;
!     }
!   return reemit_notes (insn, insn);
  }
  
  /* Return an insn which represents a SCHED_GROUP, which is
*************** schedule_block (bb, rgn, rgn_n_insns)
*** 6840,6848 ****
  	      /* an interblock motion? */
  	      if (INSN_BB (insn) != target_bb)
  		{
  		  if (IS_SPECULATIVE_INSN (insn))
  		    {
- 
  		      if (!check_live (insn, INSN_BB (insn), target_bb))
  			{
  			  /* speculative motion, live check failed, remove
--- 6844,6853 ----
  	      /* an interblock motion? */
  	      if (INSN_BB (insn) != target_bb)
  		{
+ 		  rtx tmp;
+ 
  		  if (IS_SPECULATIVE_INSN (insn))
  		    {
  		      if (!check_live (insn, INSN_BB (insn), target_bb))
  			{
  			  /* speculative motion, live check failed, remove
*************** schedule_block (bb, rgn, rgn_n_insns)
*** 6861,6878 ****
  		  nr_inter++;
  
  		  /* update source block boundaries */
  		  b1 = INSN_BLOCK (insn);
! 		  if (insn == basic_block_head[b1]
  		      && insn == basic_block_end[b1])
  		    {
! 		      emit_note_after (NOTE_INSN_DELETED, basic_block_head[b1]);
  		      basic_block_end[b1] = basic_block_head[b1] = NEXT_INSN (insn);
  		    }
  		  else if (insn == basic_block_end[b1])
  		    {
! 		      basic_block_end[b1] = PREV_INSN (insn);
  		    }
! 		  else if (insn == basic_block_head[b1])
  		    {
  		      basic_block_head[b1] = NEXT_INSN (insn);
  		    }
--- 6866,6886 ----
  		  nr_inter++;
  
  		  /* update source block boundaries */
+ 		  tmp = insn;
+ 		  while (SCHED_GROUP_P (tmp))
+ 		    tmp = PREV_INSN (tmp);
  		  b1 = INSN_BLOCK (insn);
! 		  if (tmp == basic_block_head[b1]
  		      && insn == basic_block_end[b1])
  		    {
! 		      emit_note_after (NOTE_INSN_DELETED, insn);
  		      basic_block_end[b1] = basic_block_head[b1] = NEXT_INSN (insn);
  		    }
  		  else if (insn == basic_block_end[b1])
  		    {
! 		      basic_block_end[b1] = PREV_INSN (tmp);
  		    }
! 		  else if (tmp == basic_block_head[b1])
  		    {
  		      basic_block_head[b1] = NEXT_INSN (insn);
  		    }
*************** debug_dependencies ()
*** 7383,7389 ****
  				 NOTE_SOURCE_FILE (insn));
  		    }
  		  else
! 		    fprintf (dump, " {%s}\n", GET_RTX_NAME (insn));
  		  continue;
  		}
  
--- 7391,7397 ----
  				 NOTE_SOURCE_FILE (insn));
  		    }
  		  else
! 		    fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
  		  continue;
  		}