This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Speed up hybrid_search_bitmap
Hello,
there is no reason to use Fibonacci heaps for worklist in
iterative_dataflow_bitmap; this patch replaces them with ordinary
heaps, thus speeding up df_analyse by 20%.
Zdenek
* heap.c: New.
* heap.h: New.
* Makefile.in (heap.o): New.
(df.c): Add heap.h dependency, remove fibheap.h dependency.
* df.c: Include heap.h instead of fibheap.h.
(iterative_dataflow_sbitmap, iterative_dataflow_bitmap): Use ordinary
heaps for worklist.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.937.2.39
diff -c -3 -p -r1.937.2.39 Makefile.in
*** Makefile.in 5 Apr 2003 23:04:31 -0000 1.937.2.39
--- Makefile.in 20 Apr 2003 22:12:20 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 806,812 ****
expr.o final.o flow.o fold-const.o function.o gcse.o gcse-utils.o \
gcse-classic.o gcse-hoist.o gcse-cprop.o gcse-pre.o gcse-store.o \
gcse-null.o gcse.o gcse-utils.o \
! genrtl.o ggc-common.o global.o graph.o gtype-desc.o \
haifa-sched.o hashtable.o hooks.o ifcvt.o insn-attrtab.o insn-emit.o \
insn-extract.o insn-opinit.o insn-output.o insn-peep.o insn-recog.o \
integrate.o intl.o jump.o langhooks.o lcm.o lists.o local-alloc.o \
--- 806,812 ----
expr.o final.o flow.o fold-const.o function.o gcse.o gcse-utils.o \
gcse-classic.o gcse-hoist.o gcse-cprop.o gcse-pre.o gcse-store.o \
gcse-null.o gcse.o gcse-utils.o \
! genrtl.o ggc-common.o global.o graph.o gtype-desc.o heap.o \
haifa-sched.o hashtable.o hooks.o ifcvt.o insn-attrtab.o insn-emit.o \
insn-extract.o insn-opinit.o insn-output.o insn-peep.o insn-recog.o \
integrate.o intl.o jump.o langhooks.o lcm.o lists.o local-alloc.o \
*************** ssa-ccp.o : ssa-ccp.c $(CONFIG_H) system
*** 1636,1642 ****
errors.h $(GGC_H) df.h function.h
df.o : df.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
insn-config.h $(RECOG_H) function.h $(REGS_H) $(OBSTACK_H) hard-reg-set.h \
! $(BASIC_BLOCK_H) df.h $(FIBHEAP_H)
var-tracking.o : var-tracking.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(TREE_H) $(BASIC_BLOCK_H) output.h insn-config.h reload.h \
sbitmap.h alloc-pool.h $(FIBHEAP_H) $(HASHTAB_H)
--- 1636,1642 ----
errors.h $(GGC_H) df.h function.h
df.o : df.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
insn-config.h $(RECOG_H) function.h $(REGS_H) $(OBSTACK_H) hard-reg-set.h \
! $(BASIC_BLOCK_H) df.h heap.h
var-tracking.o : var-tracking.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(TREE_H) $(BASIC_BLOCK_H) output.h insn-config.h reload.h \
sbitmap.h alloc-pool.h $(FIBHEAP_H) $(HASHTAB_H)
*************** alias.o : alias.c $(CONFIG_H) $(SYSTEM_H
*** 1750,1755 ****
--- 1750,1756 ----
regmove.o : regmove.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) insn-config.h \
$(RECOG_H) output.h $(REGS_H) hard-reg-set.h flags.h function.h \
$(EXPR_H) $(BASIC_BLOCK_H) toplev.h $(TM_P_H) except.h reload.h
+ heap.o: heap.c heap.h $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H)
haifa-sched.o : haifa-sched.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_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 $(TM_P_H) $(TARGET_H)
Index: df.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/df.c,v
retrieving revision 1.36.2.9
diff -c -3 -p -r1.36.2.9 df.c
*** df.c 20 Apr 2003 19:54:36 -0000 1.36.2.9
--- df.c 20 Apr 2003 22:12:24 -0000
*************** and again mark them read/write.
*** 186,192 ****
#include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
! #include "fibheap.h"
#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
do \
--- 186,192 ----
#include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
! #include "heap.h"
#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
do \
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3926,3932 ****
void *data;
{
int i;
! fibheap_t worklist;
basic_block bb;
sbitmap visited, pending;
edge *stack = xmalloc (n_basic_blocks * sizeof (edge));
--- 3926,3932 ----
void *data;
{
int i;
! struct heap *worklist;
basic_block bb;
sbitmap visited, pending;
edge *stack = xmalloc (n_basic_blocks * sizeof (edge));
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3935,3945 ****
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
! worklist = fibheap_new ();
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
SET_BIT (pending, i);
if (dir == DF_FORWARD)
sbitmap_copy (out[i], gen[i]);
--- 3935,3945 ----
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
! worklist = heap_alloc (n_basic_blocks);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! heap_insert (worklist, order[i], (void *) (size_t) i);
SET_BIT (pending, i);
if (dir == DF_FORWARD)
sbitmap_copy (out[i], gen[i]);
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3949,3957 ****
while (sbitmap_first_set_bit (pending) != -1)
{
! while (!fibheap_empty (worklist))
{
! i = (size_t) fibheap_extract_min (worklist);
bb = BASIC_BLOCK (i);
if (!TEST_BIT (visited, bb->index))
hybrid_search_sbitmap (bb, in, out, gen, kill, dir,
--- 3949,3957 ----
while (sbitmap_first_set_bit (pending) != -1)
{
! while (heap_size (worklist) > 0)
{
! i = (size_t) heap_extract_min (worklist);
bb = BASIC_BLOCK (i);
if (!TEST_BIT (visited, bb->index))
hybrid_search_sbitmap (bb, in, out, gen, kill, dir,
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3963,3969 ****
{
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
});
sbitmap_zero (visited);
}
--- 3963,3969 ----
{
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! heap_insert (worklist, order[i], (void *) (size_t) i);
});
sbitmap_zero (visited);
}
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3975,3981 ****
sbitmap_free (pending);
sbitmap_free (visited);
! fibheap_delete (worklist);
free (stack);
}
--- 3975,3981 ----
sbitmap_free (pending);
sbitmap_free (visited);
! free (worklist);
free (stack);
}
*************** iterative_dataflow_bitmap (in, out, gen,
*** 3994,4000 ****
void *data;
{
int i;
! fibheap_t worklist;
basic_block bb;
sbitmap visited, pending;
edge *stack = xmalloc (n_basic_blocks * sizeof (edge));
--- 3994,4000 ----
void *data;
{
int i;
! struct heap *worklist;
basic_block bb;
sbitmap visited, pending;
edge *stack = xmalloc (n_basic_blocks * sizeof (edge));
*************** iterative_dataflow_bitmap (in, out, gen,
*** 4003,4013 ****
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
! worklist = fibheap_new ();
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
SET_BIT (pending, i);
if (dir == DF_FORWARD)
bitmap_copy (out[i], gen[i]);
--- 4003,4013 ----
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
! worklist = heap_alloc (n_basic_blocks);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! heap_insert (worklist, order[i], (void *) (size_t) i);
SET_BIT (pending, i);
if (dir == DF_FORWARD)
bitmap_copy (out[i], gen[i]);
*************** iterative_dataflow_bitmap (in, out, gen,
*** 4017,4025 ****
while (sbitmap_first_set_bit (pending) != -1)
{
! while (!fibheap_empty (worklist))
{
! i = (size_t) fibheap_extract_min (worklist);
bb = BASIC_BLOCK (i);
if (!TEST_BIT (visited, bb->index))
hybrid_search_bitmap (bb, in, out, gen, kill, dir,
--- 4017,4025 ----
while (sbitmap_first_set_bit (pending) != -1)
{
! while (heap_size (worklist) > 0)
{
! i = (size_t) heap_extract_min (worklist);
bb = BASIC_BLOCK (i);
if (!TEST_BIT (visited, bb->index))
hybrid_search_bitmap (bb, in, out, gen, kill, dir,
*************** iterative_dataflow_bitmap (in, out, gen,
*** 4031,4037 ****
{
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! fibheap_insert (worklist, order[i], (void *) (size_t) i);
});
sbitmap_zero (visited);
}
--- 4031,4037 ----
{
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! heap_insert (worklist, order[i], (void *) (size_t) i);
});
sbitmap_zero (visited);
}
*************** iterative_dataflow_bitmap (in, out, gen,
*** 4042,4047 ****
}
sbitmap_free (pending);
sbitmap_free (visited);
! fibheap_delete (worklist);
free (stack);
}
--- 4042,4047 ----
}
sbitmap_free (pending);
sbitmap_free (visited);
! free (worklist);
free (stack);
}