Re: c/859: sparc-specific pessimal code for simple loop

[law at redhat dot com]

The following reply was made to PR c/859; it has been noted by GNATS.

From: law@redhat.com
To: Bernd Schmidt <bernds@redhat.com>
Cc: Richard Henderson <rth@redhat.com>, jakub@redhat.com, davem@redhat.com,
        gcc-gnats@gcc.gnu.org, gcc-bugs@gcc.gnu.org, jbuck@synopsys.com
Subject: Re: c/859: sparc-specific pessimal code for simple loop 
Date: Wed, 22 Nov 2000 06:23:57 -0700

   In message <Pine.LNX.4.21.0011221036150.12759-100000@host117.cygnus>you write
 :
   > I wrote a patch, then found out while testing it that the problem is
   > quite a bit more complex than I'd thought.
   > The basic problem is, if we have a giv that is computed in several
   > steps, then usually the intermediate results are also givs.  We usually
   > don't want to reduce the intermediate givs, but the final one.  Suppose
   > we have
   > 
   >   / G2
   > G1- G3
   >   \ G4- G5
   >       \ G6
   > 
   > then the best candidates for reducing are G2, G3, G5, G6.  The benefit
   > for reducing all four of them should include the benefit of reducing
   > G1 and G4, since these will no longer be necessary after reducing the
   > group G2,3,5,6.
 To the uneducated eye (mine), it seems that you've got the right idea here --
 build a graph where the nodes are givs and the edges connect steps in
 computing the givs.
 
 Based on the information above, you want to reduce leaf nodes in the
 graph.  The benefit for reducing any set of nodes should include the
 benefit of any nodes no longer needed after reduction.  This almost
 makes me think of something T1-T2 graph transformations or something
 like that.  ie, let's assume that G5 & G6 are reducible (but not G2 or G3).
 In that case we replace the subtree G4, G5, G6 with a new node (call it G4').
 
 That gives us the new tree:
 
   / G2
 G1- G3
   \ G4'
 
 We then examine G4' to see if it is reducible (since it's now a leaf node
 in the tree).  If so, then any benefit for reducing it should be added to
 the benefit for reducing G5 and G6 (ie, things which originally depended
 on G4).
 
 This process continues until you have no reducible leaf nodes in the graph.
 
 
   > However, if we don't decide to reduce (e.g.) G5, then
   > G4 should be considered separately.
 Right.  That would seem to be the last stage after reducing all leaf nodes
 and propagating benefits through the tree, you then look at the remaining
 non-leaf nodes individually to see if there's benefit for reducing them,
 but any benefits do not propagate through the tree.
 
   > Interaction with giv combination makes this problem even more interesting.
 I don't doubt it.
 
   > I could make another attempt to get it right this or next week.  I'd
   > welcome any suggestions for a good algorithm.
 I suspect if we look at problems in graph theory we'll find approaches
 for graph reduction.  This is one of those times I wish I'd paid more attention
 in that class years ago... :(
 
 jeff