Am Montag, den 12.06.2017, 21:00 +0200 schrieb Nicolai Hähnle:
Thanks for you comments, although I do not agree with most of them.
>
> > Okay. I think you should seriously re-think your algorithm in a way
> > that makes it a more natural evolution from the algorithm that's
> > already there.
Well, when I look at the current algorithm than I don't really see much
to evolve from: The tracking of loops is minimal and it actually only
uses the outer loop to assign life times.
In any case, 80% of this code I already re-used (i.e. the loop over the
instructions and iterating over the registers).
> > Basically, the current algorithm tracks (first_write, last_read),
> > so think about what you need to track in order to obtain a single-
> > pass algorithm that computes lifetime (first, last) for every
> > temporary. I
IMHO a single pass algorithm is not better then what I do now.
Especially with nested loops a single pass algorithm will be more
complicated.
Think e.g.
...
BEGIN_LOOP
...
BEGIN_LOOP
a = ...
b = ...
c = a OP b;
END_LOOP
... /* more processing that doesn't access a, b, or c */
END_LOOP
out = f(a, c, ...)
END
Here, a and c must be kept alive for both loops, but b only is
needed for a few instructions. However, in a single pass state tracker
I have to keep all the information for a, b, and c until the end of the
program, because only then I can discard the loop information for b,
and resolve everything else for a and c.
With the approach I am using, i.e. only collecting all the access
information in the pass over the program, and resolving the life-times
at the end by re-playing the temp-access timeline, the above can be
achieved with less hassle, because I don't need to track per temporary
information for all the temporaries all the time, instead, I only need
to resolve loops and scopes when it is really needed.
[snip]
To me the algorithm you lined out looks quite complicated, but not too
different from what I'm doing when I replay the access time-line of a
register. However, with your approach one has to track the state of
each variable all the time, information that could be shared otherwise
and might not even needed.
[snip]
> >
> > I hope I didn't miss anything, because after all this is
> > admittedly subtle stuff.
It is, and this is why I think it is better to separate the steps into
manageable chunks that can be put under test. (I admit, I'm a fan of
test driven development, and for that I also think it is more important
to write test cases instead of sketching out algorithms).
> > Still, I think this kind of state-machine approach should
> > work and allow you to avoid *lots* of allocations and pointer-
> > chasing.
The allocations I can (and will) get rid of, but I don't see some
pointer-chasing as a problem, since it is encapsulated within class
methods.
I thank you for your comments, but given that my code is working I
don't see that re-doing it from scratch is such a good idea. I think
refactoring it to eliminate the allocations and covering additional
test cases is a better approach. If this makes it possible to move the
implementation to be single pass, then I might consider it, but I think
tracking all the information for all temporaries all the time is not
such a good idea, especially for large shaders that might have 2000+
temporaries before register merging.
Best,
Gert
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
