[Mesa-dev] [PATCH v3 5/7] mesa/st: glsl_to_tgsi: add register renamame mapping evaluator

[Gert Wollny]

The remapping evaluator first sorts the temporary registers ascending
based on their first life time instruction, and then uses a binary search
to find merge canidates.
For the initial sorting it uses std::sort because qsort is quite slow in
comparison. By removing the define USE_STL_SORT in
  src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
one can use the alternative code path that uses qsort.
---
 .../state_tracker/st_glsl_to_tgsi_temprename.cpp   | 104 +++++++++++++++++++++
 .../state_tracker/st_glsl_to_tgsi_temprename.h     |   3 +
 2 files changed, 107 insertions(+)

diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
index aa3bad78c0..09660ff0d3 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
@@ -26,6 +26,13 @@
 #include <mesa/program/prog_instruction.h>
 #include <limits>
 
+#define USE_STL_SORT
+#ifdef USE_STL_SORT
+#include <algorithm>
+#else
+#include <cstdlib>
+#endif
+
 using std::numeric_limits;
 
 enum e_scope_type {
@@ -646,3 +653,100 @@ estimate_temporary_lifetimes(void *mem_ctx, exec_list *instructions,
 {
    return tgsi_temp_lifetime(mem_ctx).get_lifetimes(instructions, ntemps, lifetimes);
 }
+
+struct access_record {
+   int begin;
+   int end;
+   int reg;
+   bool erase;
+};
+
+/* Find the next register between [start, end) that has a life time starting
+ * at or after bound by using a binary search.
+ * start points at the beginning of the search range,
+ * end points at the element past the end of the search range, and
+ * the array comprising [start, end) must be sorted in ascending order.
+ */
+access_record*
+find_next_rename(access_record* start, access_record* end, int bound)
+{
+   int delta = (end - start);
+   while (delta > 0)  {
+      int half = delta >> 1;
+      access_record* middle = start + half;
+      if (bound <= middle->begin)
+         delta = half;
+      else {
+         start = middle;
+         ++start;
+         delta -= half + 1;
+      }
+   }
+   return start;
+}
+
+/* This functions evaluates the register merges by using an O(n log n)
+ * algorithm to find suitable merge candidates. */
+void evaluate_remapping(void *mem_ctx, int ntemps, const struct lifetime* lifetimes,
+                        struct rename_reg_pair *result)
+{
+
+   access_record *m = ralloc_array(mem_ctx, access_record, ntemps - 1);
+
+   for (int i = 1; i < ntemps; ++i) {
+      m[i-1] =  {lifetimes[i].begin, lifetimes[i].end, i, false};
+   }
+
+#ifdef USE_STL_SORT
+   std::sort(m, m + ntemps - 1,
+             [](const access_record& a, const access_record& b) {
+      return a.begin < b.begin;
+   });
+#else
+   std::qsort(m, ntemps - 1, sizeof(access_record),
+              [](const void *a, const void *b) {
+      const access_record *aa = static_cast<const access_record*>(a);
+      const access_record *bb = static_cast<const access_record*>(b);
+      return aa->begin < bb->begin ? -1 : (aa->begin > bb->begin ? 1 : 0);
+   });
+#endif
+
+   auto trgt = m;
+   auto mend = m + ntemps - 1;
+   auto first_erase = mend;
+   auto search_start = trgt + 1;
+
+   while (trgt != mend) {
+
+      auto src = find_next_rename(search_start, mend, trgt->end);
+      if (src !=  mend) {
+         result[src->reg].new_reg = trgt->reg;
+         result[src->reg].valid = true;
+         trgt->end = src->end;
+
+         /* Since we only search forward, don't erase the renamed
+          * register just now, just mark it for removal. */
+         src->erase = true;
+         if (first_erase == mend)
+            first_erase = src;
+         search_start = src + 1;
+      } else {
+         /* Moving to the next target register it is time to
+          * erase the already merged registers */
+         if (first_erase != mend) {
+            auto out = first_erase;
+            auto in_start = first_erase + 1;
+            while (in_start != mend) {
+               if (!in_start->erase)
+                  *out++ = *in_start;
+               ++in_start;
+            }
+            mend = out;
+            first_erase = mend;
+         }
+         ++trgt;
+         search_start = trgt + 1;
+      }
+   }
+   ralloc_free(m);
+}
diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
index 0637ffab08..4ebead1b45 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
@@ -31,3 +31,6 @@ struct lifetime {
 void
 estimate_temporary_lifetimes(void *mem_ctx, exec_list *instructions,
                              int ntemps, struct lifetime *lt);
+
+void evaluate_remapping(void *mem_ctx, int ntemps, const struct lifetime *lt,
+                        struct rename_reg_pair *result);
-- 
2.13.0