This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] cfgbuild.c: Speed up make_edges - Part 2.
- From: Jeffrey A Law <law at redhat dot com>
- To: Kazu Hirata <kazu at cs dot umass dot edu>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Mon, 14 Mar 2005 10:09:24 -0700
- Subject: Re: [patch] cfgbuild.c: Speed up make_edges - Part 2.
- Organization: Red Hat, Inc
- References: <20050311.231009.15259050.kazu@cs.umass.edu>
- Reply-to: law at redhat dot com
On Fri, 2005-03-11 at 23:10 -0500, Kazu Hirata wrote:
> Hi,
>
> Attached is a patch to further speed up make_edges.
>
> make_edges uses an adjacency matrix, called edge_cache, to represent
> edges in CFG. This adjacency matrix is used to quickly tell whether
> an edge exists for a given pair of basic blocks.
>
> The problem is that consturction of edge_cache takes quadratic amount
> of time and space because make_edge initializes every bit of the
> adjacency matrix up front.
>
> The patch solves this problem by creating one row of the adjacency
> matrix as needed. Obviously, one row of the adjacency matrix takes
> linear amount of space. Plus, if make_edge is called to "repair"
> parts of CFG, we don't need to zero this adjacency matrix as many
> times as the number of basic blocks.
>
> Here is a timing in seconds on five runs of ./cc1 -quiet -O2
> -fomit-frame-pointer -o /dev/null.
>
> original patched diff%
> c-common.i 13.848 13.813 -0.252%
> combine.i 16.884 16.842 -0.248%
> fold-const.i 18.403 18.346 -0.309%
> reload1.i 11.974 11.954 -0.167%
> reload.i 11.895 11.849 -0.386%
> insn-attrtab.i 205.229 200.687 -2.213%
>
> Tested on i686-pc-linux-gnu. OK to apply?
>
> Kazu Hirata
>
> 2005-03-12 Kazu Hirata <kazu@cs.umass.edu>
>
> * basic-block.h: Update the prototypes of cached_make_edge and
> rtl_make_eh_edge.
> * cfg.c (cached_make_edge): Take edge_cache representing one
> row of the adjacency matrix of edges.
> * cfgbuild.c (make_label_edge, rtl_make_eh_edge): Likewise.
> (make_edges): Initialize edge_cache to represent one row of
> the adjacency matrix of edges.
This is fine.
I also think it would probably be worth experimenting with avoiding the
cache, except for critical edges which connect a source block with a lot
of outgoing edges to a destination block with a lot of incoming edges.
The theory being that find_edge's behavior is reasonable in the vast
majority of the time it is called and the only purpose of the edge cache
is to avoid the poor behavior of find_edge in that one unusual corner
case.
Jeff