[Mesa-dev] [PATCH v6 4/6] mesa/st: glsl_to_tgsi: add register rename mapping evaluator

[Nicolai Hähnle]

On 04.07.2017 16:18, Gert Wollny wrote:
> 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

*registers


> 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

Add an extra line of whitespace here.


> +/* 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)
> +{
> +

... and remove this one.


> +   /* The first record is empty and only used for simpler indexing,
> +    * hence, for the mapping evaluation we only need ntemps-1 values
> +    */

Is that really true? I though TMP[0] could be used by real code.


> +   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;

Spaces around operators everywhere.


> +   }
> +
> +#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);

What's the point of this? If you want to skip registers with entirely 
undefined lifetimes, why not just leave them out of the reg_access 
array? It's admittedly a minor point.


> +
> +   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) {

Remove extra space after !=

Apart from this, the patch looks good.

Cheers,
Nicolai


> +         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
> 


-- 
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.