[Mesa-dev] [PATCH 07/10] glsl/linker: Sort varyings by packing class, then vector size.

[Paul Berry]

This patch paves the way for varying packing by adding a sorting step
before varying assignment, which sorts the varyings into an order that
increases the likelihood of being able to find an efficient packing.

First, varyings are sorted into "packing classes" by considering
attributes that can't be mixed during varying packing--at the moment
this includes base type (float/int/uint/bool) and interpolation mode
(smooth/noperspective/flat/centroid), though later we will hopefully
be able to relax some of these restrictions.  The number of packing
classes places an upper limit on the amount of space that must be
wasted by varying packing, since in theory a shader might nave 4n+1
components worth of varyings in each of m packing classes, resulting
in 3m components worth of wasted space.

Then, within each packing class, varyings are sorted by vector size,
with vec4's coming first, then vec2's, then scalars, and then finally
vec3's.  The motivation for this order is that it ensures that the
only vectors that might be "double parked" (with part of the vector in
one varying slot and the remainder in another) are vec3's.

Note that the varyings aren't actually packed yet, merely placed in an
order that will facilitate packing.
---
 src/glsl/linker.cpp | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 104 insertions(+)

diff --git a/src/glsl/linker.cpp b/src/glsl/linker.cpp
index 7fa980f..cee7386 100644
--- a/src/glsl/linker.cpp
+++ b/src/glsl/linker.cpp
@@ -1975,11 +1975,41 @@ public:
 
 private:
    /**
+    * Enum representing the order in which varyings are packed within a
+    * packing class.
+    *
+    * Currently we pack vec4's first, then vec2's, then scalar values, then
+    * vec3's.  This order ensures that the only vectors that are at risk of
+    * having to be "double parked" (split between two adjacent varying slots)
+    * are the vec3's.
+    */
+   enum packing_order_enum {
+      PACKING_ORDER_VEC4,
+      PACKING_ORDER_VEC2,
+      PACKING_ORDER_SCALAR,
+      PACKING_ORDER_VEC3,
+   };
+
+   static unsigned compute_packing_class(ir_variable *var);
+   static packing_order_enum compute_packing_order(ir_variable *var);
+   static int match_comparator(const void *x_generic, const void *y_generic);
+
+   /**
     * Structure recording the relationship between a single producer output
     * and a single consumer input.
     */
    struct match {
       /**
+       * Packing class for this varying, computed by compute_packing_class().
+       */
+      unsigned packing_class;
+
+      /**
+       * Packing order for this varying, computed by compute_packing_order().
+       */
+      packing_order_enum packing_order;
+
+      /**
        * The output variable in the producer stage.
        */
       ir_variable *producer_var;
@@ -2061,6 +2091,10 @@ varying_matches::record(ir_variable *producer_var, ir_variable *consumer_var)
          realloc(this->matches,
                  sizeof(*this->matches) * this->matches_capacity);
    }
+   this->matches[this->num_matches].packing_class
+      = this->compute_packing_class(producer_var);
+   this->matches[this->num_matches].packing_order
+      = this->compute_packing_order(producer_var);
    this->matches[this->num_matches].producer_var = producer_var;
    this->matches[this->num_matches].consumer_var = consumer_var;
    this->num_matches++;
@@ -2077,6 +2111,10 @@ varying_matches::record(ir_variable *producer_var, ir_variable *consumer_var)
 unsigned
 varying_matches::assign_locations()
 {
+   /* Sort varying matches into an order that makes them easy to pack. */
+   qsort(this->matches, this->num_matches, sizeof(*this->matches),
+         &varying_matches::match_comparator);
+
    unsigned generic_location = 0;
 
    for (unsigned i = 0; i < this->num_matches; i++) {
@@ -2127,6 +2165,72 @@ varying_matches::store_locations(unsigned producer_base,
 
 
 /**
+ * Compute the "packing class" of the given varying.  This is an unsigned
+ * integer with the property that two variables in the same packing class can
+ * be safely backed into the same vec4.
+ */
+unsigned
+varying_matches::compute_packing_class(ir_variable *var)
+{
+   /* In this initial implementation we conservatively assume that variables
+    * can only be packed if their base type (float/int/uint/bool) matches and
+    * their interpolation and centroid qualifiers match.
+    *
+    * TODO: relax these restrictions when the driver back-end permits.
+    */
+   unsigned packing_class = var->centroid ? 1 : 0;
+   packing_class *= 4;
+   packing_class += var->interpolation;
+   packing_class *= GLSL_TYPE_ERROR;
+   packing_class += var->type->get_scalar_type()->base_type;
+   return packing_class;
+}
+
+
+/**
+ * Compute the "packing order" of the given varying.  This is a sort key we
+ * use to determine when to attempt to pack the given varying relative to
+ * other varyings in the same packing class.
+ */
+varying_matches::packing_order_enum
+varying_matches::compute_packing_order(ir_variable *var)
+{
+   const glsl_type *element_type = var->type;
+
+   /* FINISHME: Support for "varying" records in GLSL 1.50. */
+   while (element_type->base_type == GLSL_TYPE_ARRAY) {
+      element_type = element_type->fields.array;
+   }
+
+   switch (element_type->vector_elements) {
+   case 1: return PACKING_ORDER_SCALAR;
+   case 2: return PACKING_ORDER_VEC2;
+   case 3: return PACKING_ORDER_VEC3;
+   case 4: return PACKING_ORDER_VEC4;
+   default:
+      assert(!"Unexpected value of vector_elements");
+      return PACKING_ORDER_VEC4;
+   }
+}
+
+
+/**
+ * Comparison function passed to qsort() to sort varyings by packing_class and
+ * then by packing_order.
+ */
+int
+varying_matches::match_comparator(const void *x_generic, const void *y_generic)
+{
+   const match *x = (const match *) x_generic;
+   const match *y = (const match *) y_generic;
+
+   if (x->packing_class != y->packing_class)
+      return x->packing_class - y->packing_class;
+   return x->packing_order - y->packing_order;
+}
+
+
+/**
  * Is the given variable a varying variable to be counted against the
  * limit in ctx->Const.MaxVarying?
  * This includes variables such as texcoords, colors and generic
-- 
1.8.0.1