Re: Gcc 3.1 performance regressions with respect to 2.95.3

[David Edelsohn <dje at watson dot ibm dot com>]

	Michael Matz, Daniel Berlin, and I tracked down a performance
regression that Franz Sirl had reported with -O2 causing excessive stack
usage.  I do not know if this problem affects the benchmarks being
discussed, but I thought that I might as well mention if for this topic.

	The problem we found is that the first scheduling pass is moving
the instructions in LIBCALLs far apart -- moving the CLOBBERs very early.
This creates artificially large lifetimes for the pseudos.  The local and
global register allocators could not allocate the pseudos to registers, so
reload ends up creating massively large stacks to home each pseudo over
its long lifetime.

	Michael Matz and I created a patch (appended) which marks each
LIBCALL as a SCHED_GROUP.  This fixes the problem and produces much better
code.  Andreas Jaeger ran this through his SPEC tester showing
improvements on some tests and no regressions.

	HOWEVER, the patch has a problem: I have an example
(dp-bit.c:__pack_d) where GCC with the patch loops forever in the second
scheduling phase.  I have been trying to debug it for a few months, but I
have not been able to find the source of the problem.  I think the patch
is correct, but is exposing another bug.

	The symptom of the endless loop is that
compute_forward_dependences() seems to end up with an INSN that is garbage
and points to itself.  I think it may be following links to an INSN whose
memory has been garbage collected.  Maybe an instruction in a scheduling
group is being deleted but the links are not being updated.

Thanks, David


Index: sched-deps.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/sched-deps.c,v
retrieving revision 1.34
diff -c -p -r1.34 sched-deps.c
*** sched-deps.c	2002/02/19 02:53:10	1.34
--- sched-deps.c	2002/03/17 23:57:41
*************** static void flush_pending_lists PARAMS (
*** 88,93 ****
--- 88,94 ----
  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_create_groups_for_libcalls PARAMS ((rtx, rtx));
  static rtx group_leader PARAMS ((rtx));
  
  static rtx get_condition PARAMS ((rtx));
*************** sched_analyze_insn (deps, x, insn, loop_
*** 1210,1215 ****
--- 1211,1264 ----
      }
  }
  
+ static void
+ sched_create_groups_for_libcalls (head, tail)
+      rtx head, tail;
+ {
+   rtx insn;
+   int tail_seen_p = 0;
+ 
+   for (insn = head;; insn = NEXT_INSN (insn))
+     {
+       rtx link, end_seq, set, r0, note;
+       if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == CLOBBER
+ 	  && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG)
+ 	  && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
+ 	  && (end_seq = XEXP (link, 0)) != 0
+ 	  && INSN_P (end_seq)
+ 	  && (set = single_set (end_seq)) != 0
+ 	  && SET_DEST (set) == r0 && SET_SRC (set) == r0
+ 	  && (note = find_reg_note (end_seq, REG_EQUAL, NULL_RTX)) != 0)
+ 	{
+ 	  /* We found a libcall block between insn and end_seq.
+ 	     The inner insns should be scheduled in a block.  */
+ 	  rtx inner;
+ 	  /* Paranoia.  */
+ 	  if (insn == tail)
+ 	    tail_seen_p = 1;
+ 	  /* We don't want to set this flag on the initial clobber, because
+ 	     the semantic of SCHED_GROUP_P is to make insn be scheduled
+ 	     together with the previous insn.  */
+ 	  for (inner = NEXT_INSN (insn); inner; inner = NEXT_INSN (inner))
+ 	    {
+ 	      if (INSN_P (inner))
+ 		set_sched_group_p (inner);
+ 	      /* Paranoia.  */
+ 	      if (inner == tail)
+ 		tail_seen_p = 1;
+ 	      if (inner == end_seq)
+ 		break;
+ 	    }
+ 	  /* We should be able to skip the whole lib-call block.
+ 	     Remember that one NEXT_INSN is done in the loop-iteration.  */
+ 	  insn = end_seq;
+ 	}
+       if (insn == tail || tail_seen_p)
+ 	break;
+     }
+   return;
+ }
+ 
  /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
     for every dependency.  */
  
*************** sched_analyze (deps, head, tail)
*** 1360,1365 ****
--- 1409,1418 ----
  	{
  	  if (current_sched_info->use_cselib)
  	    cselib_finish ();
+ 
+ 	  if (! reload_completed)
+ 	    sched_create_groups_for_libcalls (head, tail);
+ 
  	  return;
  	}
      }