This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Optimize allocation of INSN_REF_COUNT (PR middle-end/37499)


Hello,

PR37499 demonstrates compile time regression in Haifa scheduler that appeared
with selective scheduler merge.  The problem is multiple allocation and
zeroing of ref_counts array (this array is used to hold values of
INSN_REF_COUNT, which previously was a field of _haifa_insn_data structure,
but it's better to have it split out due to a very short lifetime).

The array is indexed by INSN_UID and cleared for every region, resulting in
quadratic behaviour.  The solution is either to clear the array once for all
regions and re-allocate it as needed if scheduler introduces new instructions,
or to index it by INSN_LUID, which allows to reduce its size from number of
insns in function to number of insns in region.

This patch implement the latter approach.  It also changes the array to
sbitmap to reduce needed space and removes an unused field of _haifa_insn_data
structure (that previously stored INSN_REF_COUNT).

I have verified that this does not change code generation by building third
stage of bootstrapped compiler with BOOT_CFLAGS="-O2 -g -save-temps" and
comparing .s files on pristine and patched trees.  Only files that include
sched-int.h and cc1 checksum have changed.

Bootstrap and regtest in progress on x86_64 and ia64.  OK for trunk if both
succeed?


2008-09-16  Alexander Monakov  <amonakov@ispras.ru>

	PR middle-end/37499
	* sched-int.h (struct _haifa_insn_data): Remove unused field
	ref_count.

	* sched-rgn.c (ref_counts): Remove.
	(insn_referenced): New static variable.
	(INSN_REF_COUNT): Remove.
	(sched_run_compute_dependencies): Use insn_referenced instead of
	INSN_REF_COUNT.
	(add_branch_dependences): Likewise.  Delete dead assignment.


diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index d358650..c547080 100644
--- a/gcc/sched-int.h
+++ b/gcc/sched-int.h
@@ -678,9 +678,6 @@ struct _haifa_insn_data
   /* A priority for each insn.  */
   int priority;
 
-  /* 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;
diff --git a/gcc/sched-rgn.c b/gcc/sched-rgn.c
index 8ea3d09..004064e 100644
--- a/gcc/sched-rgn.c
+++ b/gcc/sched-rgn.c
@@ -2395,9 +2395,9 @@ sets_likely_spilled_1 (rtx x, const_rtx pat, void *data)
     *ret = true;
 }
 
-/* An array used to hold the number of dependencies in which insn 
-   participates.  Used in add_branch_dependences.  */
-static int *ref_counts;
+/* A bitmap to note insns that participate in any dependency.  Used in
+   add_branch_dependences.  */
+static sbitmap insn_referenced;
 
 /* Add dependences so that branches are scheduled to run last in their
    block.  */
@@ -2424,8 +2424,6 @@ add_branch_dependences (rtx head, rtx tail)
      are not moved before reload because we can wind up with register
      allocation failures.  */
 
-#define INSN_REF_COUNT(INSN) (ref_counts[INSN_UID (INSN)])
-
   insn = tail;
   last = 0;
   while (CALL_P (insn)
@@ -2448,7 +2446,7 @@ add_branch_dependences (rtx head, rtx tail)
 	    {
 	      if (! sched_insns_conditions_mutex_p (last, insn))
 		add_dependence (last, insn, REG_DEP_ANTI);
-	      INSN_REF_COUNT (insn)++;
+	      SET_BIT (insn_referenced, INSN_LUID (insn));
 	    }
 
 	  CANT_MOVE (insn) = 1;
@@ -2470,12 +2468,11 @@ add_branch_dependences (rtx head, rtx tail)
       {
 	insn = prev_nonnote_insn (insn);
 
-	if (INSN_REF_COUNT (insn) != 0)
+	if (TEST_BIT (insn_referenced, INSN_LUID (insn)))
 	  continue;
 
 	if (! sched_insns_conditions_mutex_p (last, insn))
 	  add_dependence (last, insn, REG_DEP_ANTI);
-	INSN_REF_COUNT (insn) = 1;
       }
 
 #ifdef HAVE_conditional_execution
@@ -3086,14 +3083,15 @@ sched_rgn_compute_dependencies (int rgn)
       for (bb = 0; bb < current_nr_blocks; bb++)
 	init_deps (bb_deps + bb);
 
-      /* Initialize array used in add_branch_dependencies ().  */
-      ref_counts = XCNEWVEC (int, get_max_uid () + 1);
+      /* Initialize bitmap used in add_branch_dependences.  */
+      insn_referenced = sbitmap_alloc (sched_max_luid);
+      sbitmap_zero (insn_referenced);
       
       /* Compute backward dependencies.  */
       for (bb = 0; bb < current_nr_blocks; bb++)
 	compute_block_dependences (bb);
       
-      free (ref_counts);
+      sbitmap_free (insn_referenced);
       free_pending_lists ();
       finish_deps_global ();
       free (bb_deps);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]