mesa/st/glsl_to_tgsi: Add array merge logic

v4: - Update the code to use the new merge logic.
    - Use a cleaner, class-based approach for the evaluation of merges.
Signed-off-by: Gert Wollny <[email protected]>
Acked-by: Dave Airlie <[email protected]>

2 files changed, 407 insertions, 2 deletions

diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.cpp b/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.cpp
index 43f0c644b2c..f95b1fac7b7 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.cpp
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.cpp
@@ -21,6 +21,109 @@
  * DEALINGS IN THE SOFTWARE.
  */
 
+/* A short overview on how the array merging works:
+ *
+ * Inputs:
+ *   - per array information: live range, access mask, size
+ *   - the program
+ *
+ * Output:
+ *   - the program with updated array addressing
+ *
+ * Pseudo algorithm:
+ *
+ * repeat
+ *    for all pairs of arrays:
+ *       if they have non-overlapping live ranges and equal access masks:
+ *          - pick shorter array
+ *          - merge its live range into the longer array
+ *          - set its merge target array to the longer array
+ *          - mark the shorter array as processed
+ *
+ *    for all pairs of arrays:
+ *       if they have overlapping live ranges use in sum at most four components:
+ *          - pick shorter array
+ *          - evaluate reswizzle map to move its components into the components
+ *            that are not used by the longer array
+ *          - set its merge target array to the longer array
+ *          - mark the shorter array as processed
+ *          - bail out loop
+ *  until no more successfull merges were found
+ *
+ *  for all pairs of arrays:
+ *     if they have non-overlapping live ranges:
+ *          - pick shorter array
+ *          - merge its live range into the longer array
+ *          - set its merge target array to the longer array
+ *          - mark the shorter array as processed
+ *
+ * Finalize remapping map so that target arrays are always final, i.e. have
+ * themselfes no merge target set.
+ *
+ * Example:
+ *   ID  | Length | Live range | access mask | target id | reswizzle
+ *   ================================================================
+ *   1       3       3-10          x___            0        ____
+ *   2       4      13-20          x___            0        ____
+ *   3       8       3-20          x___            0        ____
+ *   4       6      21-40          xy__            0        ____
+ *   5       7      12-30          xy__            0        ____
+ *
+ * 1. merge live ranges 1 and 2
+ *
+ *   ID  | Length | Live range | access mask | target id | reswizzle
+ *   ================================================================
+ *   1       -        -            x___            2        ____
+ *   2       4       3-20          x___            0        ____
+ *   3       8       3-20          x___            0        ____
+ *   4       6      21-40          xy__            0        ____
+ *   5       7      12-30          xy__            0        ____
+ *
+ *
+ *  3. interleave 2 and 3
+ *
+ *   ID  | Length | Live range | access mask | target id | reswizzle
+ *   ================================================================
+ *   1       -        -            x___            2        ____
+ *   2       -        -            x___            3        _x__
+ *   3       8       3-20          xy__            0        ____
+ *   4       6      21-40          xy__            0        ____
+ *   5       7      12-30          xy__            0        ____
+ *
+ *   3. merge live ranges 3 and 4
+ *
+ *   ID  | Length | Live range | access mask | target id | reswizzle
+ *   ================================================================
+ *   1       -        -            x___            2        ____
+ *   2       -        -            x___            3        _x__
+ *   3       8       3-40          xy__            0        ____
+ *   4       -        -            xy__            3        ____
+ *   5       7       3-21          xy__            0        ____
+ *
+ *   4. interleave 3 and 5
+ *
+ *   ID  | Length | Live range | access mask | target id | reswizzle
+ *   ================================================================
+ *   1       -        -            x___            2        ____
+ *   2       -        -            x___            3        _x__
+ *   3       8       3-40          xy__            0        ____
+ *   4       -        -            xy__            3        ____
+ *   5       -        -            xy__            3        __xy
+ *
+ *   5. finalize remapping
+ *   (Array 1 has been merged with 2 that was later interleaved, so
+ *   the reswizzeling must be propagated.
+ *
+ *   ID  | Length | Live range | new access mask | target id | reswizzle
+ *   ================================================================
+ *   1       -        -               _y__            3        _x__
+ *   2       -        -               _y__            3        _x__
+ *   3       8       3-40             xy__            0        ____
+ *   4       -        -               xy__            3        ____
+ *   5       -        -               __zw            3        __xy
+ *
+*/
+
 #include "program/prog_instruction.h"
 #include "util/u_math.h"
 #include <ostream>
@@ -313,5 +416,283 @@ bool operator == (const array_remapping& lhs, const array_remapping& rhs)
    return true;
 }
 
-/* end namespace tgsi_array_merge */
+static
+bool sort_by_begin(const array_live_range& lhs, const array_live_range& rhs) {
+   return lhs.begin() < rhs.begin();
+}
+
+/* Helper class to evaluate merging and interleaving of arrays */
+class array_merge_evaluator {
+public:
+   typedef int (*array_merger)(array_live_range& range_1,
+			       array_live_range& range_2);
+
+   array_merge_evaluator(int _narrays, array_live_range *_ranges,
+			 bool _restart);
+
+   /** Run the merge strategy on all arrays
+    * @returns number of successfull merges
+    */
+   int run();
+
+private:
+   virtual int do_run(array_live_range& range_1, array_live_range& range_2) = 0;
+
+   int narrays;
+   array_live_range *ranges;
+   bool restart;
+};
+
+array_merge_evaluator::array_merge_evaluator(int _narrays,
+					     array_live_range *_ranges,
+					     bool _restart):
+   narrays(_narrays),
+   ranges(_ranges),
+   restart(_restart)
+{
+}
+
+int array_merge_evaluator::run()
+{
+   int remaps = 0;
+
+   for (int i = 0; i < narrays; ++i) {
+      if (ranges[i].is_mapped())
+	 continue;
+
+      for (int j = i + 1; j < narrays; ++j) {
+	 if (!ranges[j].is_mapped()) {
+	    ARRAY_MERGE_DUMP("try merge " << i << " id:" << ranges[i].array_id()
+			     << " and " << j  << " id: "<< ranges[j].array_id()
+			     << "\n");
+	    int n = do_run(ranges[i], ranges[j]);
+	    if (restart && n)
+	       return n;
+	    remaps += n;
+	 }
+      }
+   }
+   return remaps;
+}
+
+/* Merge live ranges if possible at all */
+class merge_live_range_always: public array_merge_evaluator {
+public:
+   merge_live_range_always(int _narrays, array_live_range *_ranges):
+      array_merge_evaluator(_narrays, _ranges, false) {
+   }
+protected:
+   int do_run(array_live_range& range_1, array_live_range& range_2){
+      if (range_2.time_doesnt_overlap(range_1)) {
+	 ARRAY_MERGE_DUMP("merge " << range_2 << " into " << range_1 << "\n");
+	 array_live_range::merge(&range_1,&range_2);
+	 return 1;
+      }
+      return 0;
+   }
+};
+
+/* Merge live ranges only if they use the same swizzle */
+class merge_live_range_equal_swizzle: public merge_live_range_always {
+public:
+   merge_live_range_equal_swizzle(int _narrays, array_live_range *_ranges):
+      merge_live_range_always(_narrays, _ranges) {
+   }
+private:
+   int do_run(array_live_range& range_1, array_live_range& range_2){
+      if (range_1.access_mask() == range_2.access_mask()) {
+	 return merge_live_range_always::do_run(range_1, range_2);
+      }
+      return 0;
+   }
+};
+
+/* Interleave arrays if possible */
+class interleave_live_range: public  array_merge_evaluator {
+public:
+   interleave_live_range(int _narrays, array_live_range *_ranges):
+      array_merge_evaluator(_narrays, _ranges, true) {
+   }
+private:
+   int do_run(array_live_range& range_1, array_live_range& range_2){
+      if ((range_2.used_components() + range_1.used_components() <= 4) &&
+	  !range_1.time_doesnt_overlap(range_2)) {
+	 ARRAY_MERGE_DUMP("Interleave " << range_2 << " into " << range_1 << "\n");
+	 array_live_range::interleave(&range_1, &range_2);
+	 return 1;
+      }
+      return 0;
+   }
+};
+
+/* Estimate the array merging: First in a loop, arrays with equal access mask
+ * are merged, then interleave arrays that together use at most four components,
+ * and have overlapping live ranges. Finally arrays are merged regardless of
+ * access mask.
+ * @param[in] narrays number of arrays
+ * @param[in,out] alt array life times, the merge target life time will be
+ *   updated with the new life time.
+ * @param[in,out] remapping track the arraay index remapping and reswizzeling.
+ * @returns number of merged arrays
+ */
+bool get_array_remapping(int narrays, array_live_range *ranges,
+			 array_remapping *remapping)
+{
+   int total_remapped = 0;
+   int n_remapped;
+
+   /* Sort by "begin of live range" so that we don't have to restart searching
+    * after every merge.
+    */
+   std::sort(ranges, ranges + narrays, sort_by_begin);
+   merge_live_range_equal_swizzle merge_evaluator_es(narrays, ranges);
+   interleave_live_range interleave_lr(narrays, ranges);
+   do {
+
+      n_remapped = merge_evaluator_es.run();
+
+      /* try only one array interleave, if successfull, another
+       * live_range merge is tried. The test MergeAndInterleave5
+       * (mesa/st/tests/test_glsl_to_tgsi_array_merge.cpp)
+       * shows that this can result in more arrays being merged/interleaved.
+       */
+      n_remapped += interleave_lr.run();
+      total_remapped += n_remapped;
+
+      ARRAY_MERGE_DUMP("Remapped " << n_remapped << " arrays\n");
+   } while (n_remapped > 0);
+
+   total_remapped += merge_live_range_always(narrays, ranges).run();
+   ARRAY_MERGE_DUMP("Remapped a total of " << total_remapped << " arrays\n");
+
+   /* Resolve the remapping chain */
+   for (int i = 1; i <= narrays; ++i) {
+      ARRAY_MERGE_DUMP("Map " << i << ":");
+      remapping[ranges[i-1].array_id()].init_from(ranges[i-1]);
+   }
+   return total_remapped > 0;
+}
+
+/* Remap the arrays in a TGSI program according to the given mapping.
+ * @param narrays number of arrays
+ * @param array_sizes array of arrays sizes
+ * @param map the array remapping information
+ * @param instructions TGSI program
+ * @returns number of arrays after remapping
+ */
+int remap_arrays(int narrays, unsigned *array_sizes,
+		 exec_list *instructions,
+		 array_remapping *map)
+{
+   /* re-calculate arrays */
+#if __cplusplus < 201402L
+   int *idx_map = new int[narrays + 1];
+   unsigned *old_sizes = new unsigned[narrays + 1];
+#else
+   unique_ptr<int[]> idx_map = make_unique<int[]>(narrays + 1);
+   unique_ptr<unsigned[]> old_sizes = make_unique<unsigned[]>(narrays + 1);
+#endif
+
+   memcpy(&old_sizes[0], &array_sizes[0], sizeof(unsigned) * narrays);
+
+   /* Evaluate mapping for the array indices and update array sizes */
+   int new_narrays = 0;
+   for (int i = 1; i <= narrays; ++i) {
+      if (!map[i].is_valid()) {
+	 ++new_narrays;
+	 idx_map[i] = new_narrays;
+	 array_sizes[new_narrays] = old_sizes[i];
+      }
+   }
+
+   /* Map the array ids of merged arrays. */
+   for (int i = 1; i <= narrays; ++i) {
+      if (map[i].is_valid()) {
+	 map[i].set_target_id(idx_map[map[i].target_array_id()]);
+      }
+   }
+
+   /* Map the array ids of merge targets that got only renumbered. */
+   for (int i = 1; i <= narrays; ++i) {
+      if (!map[i].is_valid()) {
+	 map[i].set_target_id(idx_map[i]);
+      }
+   }
+
+   /* Update the array ids and swizzles in the registers */
+   foreach_in_list(glsl_to_tgsi_instruction, inst, instructions) {
+      for (unsigned j = 0; j < num_inst_src_regs(inst); j++) {
+	 st_src_reg& src = inst->src[j];
+	 if (src.file == PROGRAM_ARRAY && src.array_id > 0) {
+	    array_remapping& m = map[src.array_id];
+	    if (m.is_valid()) {
+	       src.array_id = m.target_array_id();
+	       src.swizzle = m.map_swizzles(src.swizzle);
+	    }
+	 }
+      }
+      for (unsigned j = 0; j < inst->tex_offset_num_offset; j++) {
+	 st_src_reg& src = inst->tex_offsets[j];
+	 if (src.file == PROGRAM_ARRAY && src.array_id > 0) {
+	    array_remapping& m = map[src.array_id];
+	    if (m.is_valid()) {
+	       src.array_id = m.target_array_id();
+	       src.swizzle = m.map_swizzles(src.swizzle);
+	    }
+	 }
+      }
+      for (unsigned j = 0; j < num_inst_dst_regs(inst); j++) {
+	 st_dst_reg& dst = inst->dst[j];
+	 if (dst.file == PROGRAM_ARRAY && dst.array_id > 0) {
+	    array_remapping& m = map[dst.array_id];
+	    if (m.is_valid()) {
+	       assert(j == 0 &&
+		      "remapping can only be done for single dest ops");
+	       dst.array_id = m.target_array_id();
+	       dst.writemask = m.map_writemask(dst.writemask);
+
+	       /* If the target component is moved, then the source swizzles
+		* must be moved accordingly.
+		*/
+	       for (unsigned j = 0; j < num_inst_src_regs(inst); j++) {
+		  st_src_reg& src = inst->src[j];
+		  src.swizzle = m.move_read_swizzles(src.swizzle);
+	       }
+	    }
+	 }
+      }
+      st_src_reg& res = inst->resource;
+      if (res.file == PROGRAM_ARRAY && res.array_id > 0) {
+	 array_remapping& m = map[res.array_id];
+	 if (m.is_valid()) {
+	    res.array_id = m.target_array_id();
+	    res.swizzle = m.map_swizzles(res.swizzle);
+	 }
+      }
+   }
+
+#if __cplusplus < 201402L
+   delete[] old_sizes;
+   delete[] idx_map;
+#endif
+
+   return new_narrays;
+}
+
 }
+
+using namespace tgsi_array_merge;
+
+int  merge_arrays(int narrays,
+		  unsigned *array_sizes,
+		  exec_list *instructions,
+		  struct array_live_range *arr_live_ranges)
+{
+   array_remapping *map= new array_remapping[narrays + 1];
+
+   if (get_array_remapping(narrays, arr_live_ranges, map))
+      narrays = remap_arrays(narrays, array_sizes, instructions, map);
+
+   delete[] map;
+   return narrays;
+}
\ No newline at end of file
diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.h b/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.h
index 9e9443c427a..abf58c307a6 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.h
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_array_merge.h
@@ -157,5 +157,29 @@ std::ostream& operator << (std::ostream& os, const array_remapping& am)
    return os;
 }
 
+/* Apply the array remapping (internal use, exposed here for testing) */
+ bool get_array_remapping(int narrays, array_live_range *array_live_ranges,
+			 array_remapping *remapping);
+
+/* Apply the array remapping (internal use, exposed here for testing) */
+int remap_arrays(int narrays, unsigned *array_sizes,
+		 exec_list *instructions,
+		 array_remapping *map);
+
 }
-#endif
+
+/** Remap the array access to finalize the array merging and interleaving.
+  * @param[in] narrays number of input arrays,
+  * @param[in,out] array_sizes length array of input arrays, on output the
+  *   array sizes will be updated according to the remapping,
+  * @param[in,out] instructions TGSI program, on output the arrays access is
+  *    remapped to the new array layout,
+  * @param[in] array_live_ranges live ranges and access information of the
+  *    arrays.
+  * @returns number of remaining arrays
+  */
+int merge_arrays(int narrays,
+		 unsigned *array_sizes,
+		 exec_list *instructions,
+		 struct array_live_range *arr_live_ranges);
+#endif
\ No newline at end of file