Re: [tree-ssa] Tail recursion improvement

[law at redhat dot com]

In message <20040225075130.GA20753@atrey.karlin.mff.cuni.cz>, Zdenek Dvorak wri
tes:
 >Hello,
 >
 >>  >! /* Checks whether the expression EXPR in stmt AT is independent on the
 >>  >!    statement pointed by BSI (in a sense that we already know its value
 >>  >!    there).  We use the fact that we are only called from the chain of
 >>  >!    basic blocks that have only single successor.  Returns the expressio
 >n
 >>  >!    containing the value of EXPR at BSI.  */
 >>  >! 
 >>  >! static tree
 >>  >! independent_on_stmt_p (tree expr, tree at, block_stmt_iterator bsi)
 >> I must be missing something -- it seems to me that this code will enter
 >> an infinite loop if EXPR is defined by a PHI node.  
 >
 >sure.  There also was another bug in the code that prevented it from
 >ever happening (and in the time I tested it we had no test in testsuite
 >that would reveal that).  Fixed now.
 >
 >>  >! /* Propagate VAR through phis on edge E.  */
 >>  >! 
 >>  >! static tree
 >>  >! propagate_through_phis (tree var, edge e)
 >>  >! {
 >>  >!   basic_block dest = e->dest;
 >>  >!   tree phi;
 >>  >! 
 >>  >!   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
 >>  >!     if (phi_element_for_edge (phi, e)->def == var)
 >>  >!       return PHI_RESULT (phi);
 >>  >! 
 >>  >!   return var;
 >
 >> You don't actually use the result of propagate_through_phis to do any
 >> kind of expression replacement do you (such as we recently found in
 >> tree-ssa-pre.c).  If so, then we'll need some adjustments to ensure
 >> that the annotations are kept up-to-date.
 >
 >Not here, but the result of independent_on_stmt_p is used.  What needs
 >to be done?
 >
 >> I'll need to go over the code more after you send the updated patch, but I'
 >ve
 >> got a reasonably good handle on what it's trying to do.
 >
 >Here is the updated patch (bootstrapped & regtested on i686).
 >
 >Zdenek
 >
 >Index: tree-optimize.c
 >===================================================================
 >RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
 >retrieving revision 1.1.4.130
 >diff -c -3 -p -r1.1.4.130 tree-optimize.c
 >*** tree-optimize.c	25 Feb 2004 03:22:47 -0000	1.1.4.130
 >--- tree-optimize.c	25 Feb 2004 07:43:11 -0000
 >*************** init_tree_optimization_passes (void)
 >*** 286,291 ****
 >--- 286,292 ----
 >    NEXT_PASS (DUP_PASS (pass_dce));
 >    NEXT_PASS (pass_forwprop);
 >    NEXT_PASS (pass_phiopt);
 >+   NEXT_PASS (pass_tail_recursion);
 >    NEXT_PASS (pass_ch);
 >    NEXT_PASS (pass_may_alias);
 >    NEXT_PASS (pass_del_pta);
 >*************** init_tree_optimization_passes (void)
 >*** 298,304 ****
 >    NEXT_PASS (pass_dse);
 >    NEXT_PASS (DUP_PASS (pass_forwprop));
 >    NEXT_PASS (DUP_PASS (pass_phiopt));
 >-   NEXT_PASS (pass_tail_recursion);
 >    NEXT_PASS (pass_loop);
 >    NEXT_PASS (pass_ccp);
 >    NEXT_PASS (DUP_PASS (pass_redundant_phi));
 >--- 299,304 ----
BTW, the tree-optimize.c change is part of the problem with this patch
not bootstrapping.

You've moved tail recursion to a point before we've got aliasing information,
which means that we haven't computed virtual uses/defs.  This ultimately lead
to transforming tail recursive calls that ought to be left alone.

I'm going to do some testing without the tree-optimize.c hunk.  It's clearly
wrong.

jeff