This is the mail archive of the gcc-bugs@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

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



  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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]