[Mesa-dev] [PATCH v6 4/6] mesa/st: glsl_to_tgsi: add register rename 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 enable the alternative code path that uses qsort.

Registers that are not used in the shader are not considered for renaming,
registeres that are only read (undefined behaviour) may be renamed
abitrarily.
---
 .../state_tracker/st_glsl_to_tgsi_temprename.cpp   | 117 +++++++++++++++++++++
 .../state_tracker/st_glsl_to_tgsi_temprename.h     |  12 +++
 2 files changed, 129 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 f85a6fa7c9..3269f6ae6a 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
@@ -841,6 +841,123 @@ lifetime temp_comp_access::get_required_lifetime()
    return make_lifetime(first_dominant_write, last_read);
 }
 
+/* helper class for sorting and searching the registers based
+ * on life times. */
+struct access_record {
+   int begin;
+   int end;
+   int reg;
+   bool erase;
+
+   bool operator < (const access_record& rhs) const {
+      return begin < rhs.begin;
+   }
+};
+
+/* 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.
+ */
+static 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;
+}
+
+#ifndef USE_STL_SORT
+static int access_record_compare (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
+/* This functions evaluates the register merges by using an buínary
+ * search to find suitable merge candidates. */
+void get_temp_registers_remapping(void *mem_ctx, int ntemps,
+                                  const struct lifetime* lifetimes,
+                                  struct rename_reg_pair *result)
+{
+
+   /* The first record is empty and only used for simpler indexing,
+    * hence, for the mapping evaluation we only need ntemps-1 values
+    */
+   access_record *reg_access = ralloc_array(mem_ctx, access_record, ntemps - 1);
+
+   for (int i = 1; i < ntemps; ++i) {
+      reg_access[i-1].begin =  lifetimes[i].begin;
+      reg_access[i-1].end = lifetimes[i].end;
+      reg_access[i-1].reg = i;
+      reg_access[i-1].erase = false;
+   }
+
+#ifdef USE_STL_SORT
+   std::sort(reg_access, reg_access + ntemps - 1);
+#else
+   std::qsort(reg_access, ntemps - 1, sizeof(access_record), access_record_compare);
+#endif
+
+   access_record *reg_access_end = reg_access + ntemps - 1;
+   access_record *trgt = find_next_rename(reg_access, reg_access_end, 0);
+
+   access_record *first_erase = reg_access_end;
+   access_record *search_start = trgt + 1;
+
+   while (trgt != reg_access_end) {
+      access_record *src = find_next_rename(search_start, reg_access_end,
+                                            trgt->end);
+      if (src !=  reg_access_end) {
+         result[src->reg].new_reg = trgt->reg;
+         result[src->reg].valid = true;
+         trgt->end = src->end;
+
+         /* Since we only search forward, don't remove the renamed
+          * register just now, only mark it. */
+         src->erase = true;
+
+         if (first_erase == reg_access_end)
+            first_erase = src;
+
+         search_start = src + 1;
+      } else {
+         /* Moving to the next target register it is time to remove
+          * the already merged registers from the search range */
+         if (first_erase != reg_access_end) {
+            access_record *outp = first_erase;
+            access_record *inp = first_erase + 1;
+
+            while (inp != reg_access_end) {
+               if (!inp->erase)
+                  *outp++ = *inp;
+               ++inp;
+            }
+
+            reg_access_end = outp;
+            first_erase = reg_access_end;
+         }
+         ++trgt;
+         search_start = trgt + 1;
+      }
+   }
+   ralloc_free(reg_access);
+}
+
 /* Code below used for debugging */
 #ifndef NDEBUG
 static const char swizzle_txt[5] = "xyzw";
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 44998cca97..6fa8e2c9f6 100644
--- a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
@@ -51,5 +51,17 @@ struct lifetime {
 void
 get_temp_registers_required_lifetimes(void *mem_ctx, exec_list *instructions,
                                       int ntemps, struct lifetime *lifetimes);
+/** Estimate the merge remapping of the registers.
+ * @param[in] mem_ctx a memory context that can be used with the ralloc_* functions
+ * @param[in] ntemps number of temporaries reserved for this shader
+ * @param[in] lifetimes required life time for each temporary register.
+ * @param[in,out] result memory location to store the register remapping table.
+ *  On input the parameter must point to allocated memory that can hold the
+ *  renaming information for ntemps registers, on output the mapping is stored.
+ *  Note that TEMP[0] is not considered for register renaming.
+ */
+void get_temp_registers_remapping(void *mem_ctx, int ntemps,
+                                  const struct lifetime* lifetimes,
+                                  struct rename_reg_pair *result);
 
 #endif
\ No newline at end of file
-- 
2.13.0