[Mesa-dev] [PATCH 1/5] glsl: Add a union location_tree * type to hold more storage information.

[Paul Berry]

On 28 January 2012 09:54, Paul Berry <stereotype441 at gmail.com> wrote:

> On 24 January 2012 13:05, Vincent Lejeune <vljn at ovi.com> wrote:
>
>> Ir_variable::location field is currently represented by a single int.
>> Datas of composite type (arrays, records) is assumed to be stored in a
>> linear fashion from this base location. In some situation this assumption
>> is not optimal : struct fields cannot be stored in a custom order and a
>>  single location (which is often used to identify a vec4-like register in
>> hardware) cannot be shared by several datas.
>> Location_tree data structure is a tree datatype that can store information
>> for every fields of a record (allowing to reorder them) and store the
>> location of the leaf type (float, int, veci, everything that can be hold
>> in a hardware reg) in a byte-aligned way, so that 2 datas/fields can be
>> stored in a same reg using different components.
>>
>
> Hi Vincent,
>
> I'm glad you're working on this.  We really need varying packing in order
> to be strictly OpenGL conformant.  I was planning on working on it myself
> sometime in the next few months, but I have so far been caught up in other
> tasks.
>
> Unfortunately I have some big concerns about the approach you are taking:
>
> 1. The new data structure your patch series introduces (location_tree) is
> extremely general.  It tries to allow for every possible way that a data
> type could be laid out inside a shader, including layouts used by both UBOs
> and varyings (even though we don't support UBOs yet), including constraints
> from layout qualifiers (which AFAIK we don't support, at least not for
> varyings), and including varying types that contain structures (which
> aren't allowed until GLSL 1.50).  This extra generality makes the code
> difficult to understand and to test.  For example, I suspect there's a bug
> because i965 assumes that all instances of a given structure have the same
> layout, so that it can just copy from one to the other in bulk.  That
> assumption will no longer be true with this patch series, because local
> structs will have the layout chosen by the i965 back-end, whereas varying
> structs will have the layout chosen by varying packing.  But I can't test
> that because varying structs don't exist yet.  I also believe that the
> extra generality is going to come at a performance cost, because many
> operations that used to be simple (e.g. figuring out which locations are
> covered by a single varying variable) now require traversing large data
> structures and allocating/deallocating memory.
>
> I would strongly recommend trying a more incremental approach, where for
> now we make the data structures just general enough to be able to pack the
> easy cases (for example to pack two vec2's together, or a vec3 with a vec1,
> where neither is an array).  Once that is working, we can move on to harder
> cases (like matrices, and ultimately, arrays).  As for supporting packing
> of UBOs and structs, and handling layout qualifiers, let's wait on those
> until Mesa supports the features that require them.
>
>
> 2. I don't understand how the code deals with packing of varying arrays,
> and I'm particularly concerned that it doesn't appear to be making
> allowances for different packing needs in different architectures.  For
> example, if MAX_VARYING_COMPONENTS is 60, each of the following ought to be
> possible (not all at once of course):
>
> varying float foo[60];
> varying vec2 foo[30];
> varying vec3 foo[20];
> varying vec4 foo[15];
>
> I can see two possible ways to pack arrays, and it's not clear from your
> code which approach you've taken.  Taking vec2 foo[30] as an example,
> here's one possible way to pack the array:
>
> location 0: x=foo[0].x y=foo[0].y z=foo[15].x w=foo[15].y
> location 1: x=foo[1].x y=foo[1].y z=foo[16].x w=foo[16].y
> ...
> location 14: x=foo[14].x y=foo[14].y z=foo[29].x w=foo[29].y
>
> I call this a "vertical" packing, because if you look at the locations of
> consecutive array elements in the table, they go vertically down the table
> first, and then horizontally across once they run out of room.
>
> Here's a packing I would call a "horizontal" packing:
>
> location 0: x=foo[0].x y=foo[0].y z=foo[1].x w=foo[1].y
> location 1: x=foo[2].x y=foo[2].y z=foo[3].x w=foo[3].y
> ...
> location 14: x=foo[28].x y=foo[28].y z=foo[29].x w=foo[29].y
>
> Another way to think of this is that each element of the array gets
> assigned a horizontal coordinate (x=0, y=1, z=2, w=3) and a vertical
> coordinate (the location).  In the horizontal packing example, the
> coordinates are h=((index%2)*2) and v=(index/2).  In the vertical packing
> example, h=(index/15)*2 and v=(index%15).  Both of the above packings might
> be said to have a width of 4 and a height of 15.  Note that we might not
> always want to use a width of 4 (see below).
>
> Both the horizontal and vertical arrangements have their pros and cons,
> and we might even want different back-ends to be able to favor one or the
> other.  For example, in i965's vertex shader, the time it takes to access
> an element in a packed array will probably be dominated by the time it
> takes to compute the horizontal and vertical coordinates.  In this example,
> the coordinates for horizontal packing can be computed using bitwise
> operations (because all of the multiplies, divisions, and mods are by
> powers of two), so it will be probably be faster than vertical packing.
>  But other array sizes will have different tradeoffs.  For example, if an
> array is small enough that it can fit in a single vertical column, vertical
> packing will be faster, because then the coordinate formulas will be h=0
> and v=index.  Other architectures are likely to have different tradeoffs
> than i965.
>
> The vec3[20] case is particularly tricky because if you pack it
> horizontally with a width of 4, you get a complex pattern:
>
> location 0: x=foo[0].x y=foo[0].y z=foo[0].z w=foo[1].x
> location 1: x=foo[1].y y=foo[1].z z=foo[2].x w=foo[2].y
> location 2: x=foo[2].z y=foo[3].x z=foo[3].y w=foo[3].z
> location 3: x=foo[4].x y=foo[4].y z=foo[4].z w=foo[5].x
> ...
> location 15: x=foo[18].z y=foo[19].x z=foo[19].y w=foo[19].z
>
> The formulas for the horizontal and vertical coordinates are now
> h=((index*3)%4) and v=((index*3)/4), which are expensive to compute for
> i965.  To make matters worse, accessing the array elements that cross
> between two locations will require 2 MOV instructions.  This makes the
> horizontal layout very slow for i965.  But I can imagine there might be
> other architectures where this is layout is fast.
>
> The alternative, packing vertically, looks like this:
>
> location 0: x=foo[0].x y=foo[0].y z=foo[0].z
> location 1: x=foo[1].x y=foo[1].y z=foo[0].z
> ...
> location 19: x=foo[19].x y=foo[19].y z=foo[19].z
>
> In other words, no packing at all, unless there happen to be some scalar
> floats that can be packed into the unused w column.  On some architectures,
> vertically packing vec3s is impractical, because it takes up too many
> locations.  But on i965 gen6, we could actually get away with this, because
> we have a few more varying locations than we advertise.
>
> Because of these complex tradeoffs, I think we need a solution for packing
> arrays that allows architecture-specific decisions about whether to pack
> arrays vertically or horizontally.
>
>
> 3. We really need some extensive Piglit tests to be sure this code is ok.
> At the moment we have none.  At a minimum, I would recommend writing tests
> to cover the following cases:
>
> varying float[MAX_VARYING_COMPONENTS];
> varying vec2[MAX_VARYING_COMPONENTS/2];
> varying vec3[MAX_VARYING_COMPONENTS/3];
> varying vec4[MAX_VARYING_COMPONENTS/4];
> varying mat2[MAX_VARYING_COMPONENTS/4];
>
> And so on for every matrix type, including non-square matrices.  The tests
> should access the arrays using non-constant indices (e.g. using a uniform)
> so that we can verify that relative addressing works correctly.  (It's not
> good enough to write a loop in the shader that accesses each component of
> the array, because if the loop is unrolled all of the indices will become
> constant).  The matrix tests should do actual matrix operations (not just
> access components), so that we can make sure the back-end is interpreting a
> packed matrix correctly.
>
> For each of the above combinations, we should also have a test that uses N
> separate varyings rather than a single array of size N, so that we test the
> packing of both arrays and individual variables.
>
> We also should test a number of combinations of various types.  For
> example we should do a test where one varying is an array of
> MAX_VARYING_COMPONENTS/4 floats, and another is an array of
> MAX_VARYING_COMPONENTS/4 vec3s.  This will verify that vec3's and floats
> get paired up properly.
>
> We should also have some test cases where some varyings are flat, others
> are noperspective, and others are smooth, and the test verifies that each
> varying is interpolated in the correct way.  This is important because some
> back-ends can't pack together varyings of different interpolation types.
> (For example, i965 gen6 can pack together smooth with noperspective, but it
> can't pack either of these together with flat).
>
> In all of these tests, we should also verify that the varying data is
> correct when transform feedback is used.  Since transform feedback can
> request array data either in bulk or component-by-component, we should test
> both of those.
>
> There should also be variants of each of the array tests in which the data
> is prepared in a local array and then copied in bulk to the varying (and
> vice versa for the fragment shader).  We may have to take special care to
> make sure these bulk copies don't get optimized out, so that we are truly
> testing that bulk copying works correctly.
>
> We should probably also have a few hand-crafted tests that use a large
> hodge-podge of different varying types and interpolation qualifiers, to
> reduce the risk of a subtle bug being missed by the other tests.
>
> And of course we should test any corner cases that we discover over the
> course of implementing this feature.
>
>
> 4. Some of the more complex packings may be a lot of work to implement in
> the back-ends (for example the horizontal vec3 case I talked about above).
> Before we go too far we should investigate whether it would be better to do
> this with lowering passes at the GLSL IR level rather than by writing
> varying packing code for every single back-end.  I can see pros and cons of
> both approaches.  On the one hand, it's appealing to only have to write the
> code once in GLSL land, and all back-ends get the benefit for free.  On the
> other hand, rearranging the varyings in GLSL IR complicates transform
> feedback (as I discovered when trying to get gl_ClipDistance to work with
> transform feedback).  Also, there may be some kinds of packing that can be
> implemented more efficiently if they're done directly by the back end.
>
> A possible hybrid approach would be to start off by implementing varying
> packing with a GLSL IR lowering pass.  Then, if we discover that some
> back-ends can pack and un-pack more efficiently with custom code, we can
> switch off the lowering pass for those back-ends and modify the back-end
> code instead.  This approach would have the advantage that all drivers
> would get at least some of the benefit of varying packing from the start,
> and you wouldn't have to get too familiar with the details of each back-end
> until you wanted to heavily optimize things.
>
>
>
> 5. The patches as they exist right now don't look bisectable--it looks
> like patch 1 won't even build because it accesses
> ir_variable::complete_location, which doesn't exist until a later patch.
> Ideally, every patch in a series should build properly and add a small
> increment of functionality--it's not ok if the first commit in a series
> breaks some drivers (or breaks the build) and then later commits fix it,
> because if a developer later tries to do a "git bisect", and they land in
> the middle of the patch series, they may be misled.  IMHO, a sign that
> you're doing this well is if the first several patches in a series are all
> refactorings that prepare for the new feature, with no actual change in
> functionality, and then the last few patches add the new feature.  If those
> later patches each say "fixes piglit test blah blah blah" in their commit
> message, that's even better, because then when we're reviewing the patch
> it'll be easy to understand what user-visible effect it has.
>
> One possible way to do this with varying packing would be as follows
> (assuming we do the hybrid approach I suggested in point 4):
>
> First patch series: only try to pack floats and vectors.  Don't try to
> pack arrays or matrices.
> - Patch 1: add a field to ir_variable that indicates the "horizontal
> coordinate" of the location it's been packed into.  (The existing
> "location" is the vertical coordinate).  Always set the horizontal
> coordinate to 0, so there is no functional change yet.
> - Patch 2: add a GLSL IR lowering pass that combines together varyings
> with the same vertical coordinate, doing appropriate swizzling to account
> for the horizontal coordinate.  Again, there's no functional change since
> we aren't packing anything yet.
> - Patch 3: modify the linker to pack varyings by assigning each variable
> both a horizontal and vertical coordinate, instead of just a single
> location.  Assuming you've got good piglit test coverage, this should cause
> a bunch of tests to start passing.
>
> Second patch series: try to pack arrays and matrices.  Always pack
> vertically.
> - Patch 1: add a field to ir_variable that indicates the "height" of the
> packed array (I think this will be sufficient for now).  Always set the
> height to the size of the array, so there is no functional change yet.
> - Patch 2: add a GLSL IR lowering pass that rewrites accesses to arrays
> and matrices to deal with how they are packed.  Again, there is no
> functional change since we're not packing yet.
> - Patch 3: modify the linker to pack arrays and matrices by assigning them
> appropriate locations and heights.  Again, this should cause a bunch of
> tests to start passing.
>
> Third patch series: Allow arrays and matrices to be packed horizontally
> too.  In this patch series, maybe we add some heuristics that each back-end
> can customize to account for the way different packings are more or less
> efficient on different drivers.
>
> ...And so on.
>
>
> This is just my two cents, and I'd be glad to hear other people's
> opinions.  Most of what I'm concerned about is making sure we implement
> this feature in small, well-tested increments.  I'm hoping to get some time
> to work on varying packing after Mesa 8.0 releases, so with luck, maybe
> Vincent and I can team up on some of these tasks.
>
> Thanks,
>
> Paul
>

I have some more info about varying packing: the GLSL ES specification (
http://www.khronos.org/registry/gles/specs/2.0/GLSL_ES_Specification_1.0.17.pdf)
specifies a minimal packing algorithm on page 111 (page 117 of the pdf).
IMHO, our first cut at varying packing should implement exactly this
algorithm.  In all likelihood it will be sufficient for any practical use
case.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20120202/7a9e6d1a/attachment-0001.html>