This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Patch to speedup haifa scheduler for big basic blocks
- To: gcc-patches at gcc dot gnu dot org
- Subject: Patch to speedup haifa scheduler for big basic blocks
- From: Vladimir Makarov <vmakarov at touchme dot toronto dot redhat dot com>
- Date: Fri, 6 Oct 2000 15:18:17 -0400
- CC: vmakarov at cygnus dot com
Hello, I've committed the following patch which permits to speedup
gcc on scheduling big basic blocks (e.g. for fast Fourier
transformation sh-elf gcc is 4 times faster for fftw/frc_64.c and ~20 times
faster on fftw/frc_128.c).
Vladimir Makarov
2000-10-06 Vladimir Makarov <vmakarov@touchme.toronto.redhat.com>
* haifa-sched.c (anti_dependency_cache, output_dependency_cache,
forward_dependency_cache): New variables.
(add_dependence, remove_dependence): Use anti_dependency_cache and
output_dependency_cache.
(compute_block_forward_dependences): Use forward_dependency_cache.
(schedule_insns): Allocate and free memory for anti/output/forward
dependencies caches.
Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/haifa-sched.c,v
retrieving revision 1.158
diff -c -p -r1.158 haifa-sched.c
*** haifa-sched.c 2000/09/12 16:19:18 1.158
--- haifa-sched.c 2000/10/06 19:05:35
*************** static regset reg_pending_sets;
*** 298,317 ****
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 true 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 an associated bitmap for its dependencies. Each bitmap
! has enough entries to represent a dependency on any other insn in the
! insn chain. */
static sbitmap *true_dependency_cache;
/* Indexed by INSN_UID, the collection of all data associated with
a single instruction. */
--- 298,328 ----
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. */
*************** add_dependence (insn, elem, dep_type)
*** 802,807 ****
--- 813,820 ----
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)
*************** add_dependence (insn, elem, dep_type)
*** 845,850 ****
--- 858,864 ----
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
*************** add_dependence (insn, elem, dep_type)
*** 854,883 ****
&& (INSN_BB (elem) != INSN_BB (insn)))
return;
! /* If we already have a true 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
! && TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
! return;
#endif
/* Check that we don't already have this dependence. */
! for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
! if (XEXP (link, 0) == elem)
! {
! /* 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 true dependency to INSN's LOG_LINKs, then
! note that in the bitmap cache of true dependency information. */
! if ((int) dep_type == 0 && true_dependency_cache)
! SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
#endif
! return;
}
/* Might want to check one level of transitivity to save conses. */
--- 868,939 ----
&& (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. */
*************** add_dependence (insn, elem, dep_type)
*** 888,897 ****
PUT_REG_NOTE_KIND (link, dep_type);
#ifdef INSN_SCHEDULING
! /* If we are adding a true dependency to INSN's LOG_LINKs, then
! note that in the bitmap cache of true dependency information. */
! if ((int) dep_type == 0 && true_dependency_cache)
! SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
#endif
}
--- 944,960 ----
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_dependence (insn, elem)
*** 917,927 ****
LOG_LINKS (insn) = next;
#ifdef INSN_SCHEDULING
! /* If we are removing a true dependency from the LOG_LINKS list,
make sure to remove it from the cache too. */
! if (REG_NOTE_KIND (link) == 0 && true_dependency_cache)
! RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
! INSN_LUID (elem));
#endif
free_INSN_LIST_node (link);
--- 980,999 ----
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);
*************** compute_block_forward_dependences (bb)
*** 6195,6202 ****
ahead and verify that add_dependence worked properly. */
if (GET_CODE (x) == NOTE
|| INSN_DELETED_P (x)
! || find_insn_list (insn, INSN_DEPEND (x)))
abort ();
#endif
new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
--- 6267,6281 ----
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));
*************** schedule_insns (dump_file)
*** 6847,6852 ****
--- 6926,6939 ----
{
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
}
nr_regions = 0;
*************** schedule_insns (dump_file)
*** 7063,7068 ****
--- 7150,7163 ----
{
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 (output_dependency_cache);
+ forward_dependency_cache = NULL;
+ #endif
}
free (rgn_table);
free (rgn_bb_table);