[patch] tree-cfg.c: Speed up find_taken_edge.

[Jeffrey A Law]

On Mon, 2005-02-21 at 11:25 -0500, Kazu Hirata wrote:
> Hi,
> 
> Attached is a patch to speed up find_taken_edge.
> 
> Here is what's happening.
> 
> A lot of passes calls cleanup_tree_cfg.
> 
> Via the following call tree, find_taken_edge is called on every
> conditional jump in the instruction stream.
> 
>   cleanup_tree_cfg
>     cleanup_control_flow
>       cleanup_control_expr_graph
>         find_taken_edge
> 
> Since find_taken_edge calls fold to fold a given value, we burn a lot
> of cycles there.
> 
> Note that find_taken_edge won't be able to determine which edge is
> taken if we pass it an expression like a > b.  It can do useful things
> only when we pass it an INTEGER_CST or something that folds to an
> INTEGER_CST like a == a.
> 
> The patch removes fold in find_taken_edge.  There is no point
> repeatedly trying to fold conditoinals that cannot be folded.  If they
> can be folded via constant/copy propagation, passes like DOM and CCP
> would fold them anyway.
> 
> I should note two things.
> 
> 1. When cleanup_tree_cfg is called for the first time, we can fold some
>    conditions, so I created fold_cond_expr_cond to fold conditionals
>    immediately before calling cleanup_tree_cfg for the first time.
>    Even then COND_EXPR_CONDs that we can fold is less than 0.05% of
>    all COND_EXPR_CONDs in cc1 files.  I vaguely remember C++ testcases
>    had a little more foldable COND_EXPR_CONDs at this point when I
>    tested this patch several months ago.  I could get this number for
>    you if you are interested.
> 
> 2. There are some rare cases where fold in find_taken_edge is
>    useful.  TER stuffs a big conditional into COND_EXPR_COND.  Having
>    more information, fold in find_taken_edge can fold the condition to
>    a constant.  This only happens only a few times during the
>    bootstrap. If this missed optimization bothers you, we could call
>    fold_cond_expr_cond before calling cleanup_tree_cfg for the last
>    time, but do note that we would be papering over missed constant
>    propagation opportunities at a wrong place.
> 
> Here is a timing in seconds for five runs of ./cc1 -quiet -O2 -o
> /dev/null.
> 
>                original patched   diff%
> c-common.i       18.152  18.117 -0.192%
> combine.i        16.689  16.584 -0.629%
> fold-const.i     37.712  37.483 -0.607%
> reload1.i        13.172  13.102 -0.531%
> reload.i         12.110  12.007 -0.850%
> insn-attrtab.i  236.465 235.329 -0.480%
> 
> There is no difference in generated code among cc1 files with or
> without this patch..
> 
> Tested on i686-pc-linux-gnu.  OK to apply?
> 
> Kazu Hirata
> 
> 2005-02-20  Kazu Hirata  <kazu@cs.umass.edu>
> 
> 	* tree-cfg.c (fold_cond_expr_cond): New.
> 	(make_edges): Call fold_cond_expr_cond.
> 	(find_taken_edge): Accept nothing but INTEGER_CST.
> 	(find_taken_edge_cond_expr): Reject INTEGER_CST other than 0
> 	and 1.
> 	(find_taken_edge_switch_expr): Remove a check for INTEGER_CST.
I'd looked at this stuff in the past as well.  I was rather dismayed at
how much time we spent trying to fold COND_EXPR_COND.  There was one
testcase in particular I was looking at least year where this has a
couple percent of the compilation time (Which I ultimately fixed by
finding a way for DOM to eliminate all the annoying COND_EXPRs so
that we didn't see them every time we ran cleanup_tree_cfg :-)

I think the overarching question here is whether or not a pass such as
DOM, CCP, PRE, etc ought to fold statements as they are changed.  THe
answer to date has been yes.  Assuming that is the direction we want
to continue to pursue, then your patch makes a lot of sense.

Approved.

jeff