[Mesa-dev] [PATCH v3 3/7] mesa/st: glsl_to_tgsi: implement new temporary register lifetime tracker
Gert Wollny
gw.fossdev at gmail.com
Sun Jun 18 17:42:55 UTC 2017
This patch adds a class for tracking the life times of temporary registers
in the glsl to tgsi translation. The algorithm runs in three steps:
First, in order to minimize the number of needed memory allocations the
program is scanned to evaluate the number of scopes.
Then, the program is scanned second time to recorc the important register
access time points: first and last reads and writes and their link to the
execution scope (loop, if/else branch, switch case).
In the third step for each register the actuall minimal life time is
evaluated.
---
src/mesa/Makefile.sources | 2 +
.../state_tracker/st_glsl_to_tgsi_temprename.cpp | 648 +++++++++++++++++++++
.../state_tracker/st_glsl_to_tgsi_temprename.h | 33 ++
3 files changed, 683 insertions(+)
create mode 100644 src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
create mode 100644 src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
diff --git a/src/mesa/Makefile.sources b/src/mesa/Makefile.sources
index 21f9167bda..2359ec3c7d 100644
--- a/src/mesa/Makefile.sources
+++ b/src/mesa/Makefile.sources
@@ -509,6 +509,8 @@ STATETRACKER_FILES = \
state_tracker/st_glsl_to_tgsi.h \
state_tracker/st_glsl_to_tgsi_private.cpp \
state_tracker/st_glsl_to_tgsi_private.h \
+ state_tracker/st_glsl_to_tgsi_temprename.cpp \
+ state_tracker/st_glsl_to_tgsi_temprename.h \
state_tracker/st_glsl_types.cpp \
state_tracker/st_glsl_types.h \
state_tracker/st_manager.c \
diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
new file mode 100644
index 0000000000..aa3bad78c0
--- /dev/null
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
@@ -0,0 +1,648 @@
+/*
+ * Copyright © 2017 Gert Wollny
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#include "st_glsl_to_tgsi_temprename.h"
+#include <tgsi/tgsi_info.h>
+#include <mesa/program/prog_instruction.h>
+#include <limits>
+
+using std::numeric_limits;
+
+enum e_scope_type {
+ sct_outer,
+ sct_loop,
+ sct_if,
+ sct_else,
+ sct_switch,
+ sct_switch_case,
+ sct_switch_default,
+ sct_unknown
+};
+
+enum e_acc_type {
+ acc_read,
+ acc_write
+};
+
+class prog_scope {
+
+public:
+ prog_scope();
+ prog_scope(e_scope_type type, int id, int lvl, int s_begin);
+ prog_scope(prog_scope *p, e_scope_type type, int id,
+ int lvl, int s_begin);
+
+ e_scope_type type() const { return scope_type; }
+ prog_scope *parent() { return parent_scope; }
+ int level() const {return nested_level; }
+ int id() const { return scope_id; }
+ int end() const {return scope_end; }
+ int begin() const {return scope_begin; }
+ int loop_continue_line() const {return loop_continue;}
+
+ prog_scope *in_ifelse();
+ prog_scope *in_switchcase();
+ prog_scope *in_conditional();
+
+ bool in_loop() const;
+ prog_scope *get_innermost_loop();
+ bool is_conditional() const;
+ bool contains(prog_scope *scope) const;
+ void set_end(int end);
+ void set_previous(prog_scope *prev);
+ void set_continue(prog_scope *scope, int i);
+ bool enclosed_by_loop_prior_to_switch();
+ prog_scope *get_outermost_loop();
+
+private:
+ e_scope_type scope_type;
+ int scope_id;
+ int nested_level;
+ int scope_begin;
+ int scope_end;
+ int loop_continue;
+
+ prog_scope *scope_of_loop_to_continue;
+ prog_scope *previous_switchcase;
+ prog_scope *parent_scope;
+
+};
+
+class temp_access {
+
+public:
+ temp_access();
+ void append(int index, e_acc_type rw, prog_scope *pstate);
+ lifetime get_required_lifetime();
+
+private:
+
+ prog_scope *last_read_scope;
+ prog_scope *first_read_scope;
+ prog_scope *first_write_scope;
+
+ int first_write;
+ int last_read;
+ int last_write;
+ int first_read;
+};
+
+
+class tgsi_temp_lifetime {
+public:
+ tgsi_temp_lifetime(void *mem_ctx);
+ void get_lifetimes(exec_list *instructions,
+ int ntemps,struct lifetime *lifetimes);
+private:
+ prog_scope *make_scope(prog_scope *p, e_scope_type type, int id,
+ int lvl, int s_begin);
+ void evaluate();
+
+ prog_scope *scopes;
+ int n_scopes;
+ int cur_scope;
+ void *mem_ctx;
+};
+
+tgsi_temp_lifetime::tgsi_temp_lifetime(void *mc):
+ scopes(0),
+ n_scopes(0),
+ cur_scope(0),
+ mem_ctx(mc)
+{
+}
+
+prog_scope *
+tgsi_temp_lifetime::make_scope(prog_scope *p, e_scope_type type, int id,
+ int lvl, int s_begin)
+{
+ scopes[cur_scope] = prog_scope(p, type, id, lvl, s_begin);
+ return &scopes[cur_scope++];
+}
+
+void
+tgsi_temp_lifetime::get_lifetimes(exec_list *instructions, int ntemps,
+ struct lifetime *lifetimes)
+{
+ int line = 0;
+ int loop_id = 0;
+ int if_id = 0;
+ int switch_id = 0;
+ int nesting_lvl = 0;
+ bool is_at_end = false;
+
+ int n_scopes = 1;
+
+ /* count scopes to allocate the needed space without the need for
+ * re-allocation */
+ foreach_in_list(glsl_to_tgsi_instruction, inst, instructions) {
+ if (inst->op == TGSI_OPCODE_BGNLOOP ||
+ inst->op == TGSI_OPCODE_SWITCH ||
+ inst->op == TGSI_OPCODE_CASE ||
+ inst->op == TGSI_OPCODE_IF ||
+ inst->op == TGSI_OPCODE_UIF ||
+ inst->op == TGSI_OPCODE_ELSE ||
+ inst->op == TGSI_OPCODE_DEFAULT)
+ ++n_scopes;
+ }
+
+ scopes = ralloc_array(mem_ctx, prog_scope, n_scopes);
+
+ /* using this new with mem_ctx segfaults ..., but we must call
+ * the standard constructor. The alternative option would be
+ * to use ralloc_array and the placement new but I doubt that
+ * this would make any difference in performance */
+ temp_access *acc = new temp_access[ntemps];
+
+ prog_scope *current = make_scope(nullptr, sct_outer, 0, nesting_lvl++, line);
+
+ foreach_in_list(glsl_to_tgsi_instruction, inst, instructions) {
+
+ assert(!is_at_end && "Found instructions past TGSI_OPCODE_END");
+
+ switch (inst->op) {
+ case TGSI_OPCODE_BGNLOOP: {
+ current = make_scope(current, sct_loop, loop_id,
+ nesting_lvl, line);
+ ++loop_id;
+ ++nesting_lvl;
+ break;
+ }
+ case TGSI_OPCODE_ENDLOOP: {
+ --nesting_lvl;
+ current->set_end(line);
+ current = current->parent();
+ break;
+ }
+ case TGSI_OPCODE_IF:
+ case TGSI_OPCODE_UIF:{
+ if (inst->src[0].file == PROGRAM_TEMPORARY) {
+ acc[inst->src[0].index].append(line, acc_read, current);
+ }
+ current = make_scope(current, sct_if, if_id, nesting_lvl, line);
+ ++if_id;
+ ++nesting_lvl;
+ break;
+ }
+ case TGSI_OPCODE_ELSE: {
+ current->set_end(line-1);
+ current = make_scope(current->parent(), sct_else,
+ current->id(), current->level(), line);
+ break;
+ }
+ case TGSI_OPCODE_END:{
+ current->set_end(line);
+ is_at_end = true;
+ break;
+ }
+ case TGSI_OPCODE_ENDIF:{
+ --nesting_lvl;
+ current->set_end(line-1);
+ current = current->parent();
+ break;
+ }
+ case TGSI_OPCODE_SWITCH: {
+ current = make_scope(current, sct_switch, switch_id,
+ nesting_lvl, line);
+ ++nesting_lvl;
+ ++switch_id;
+ break;
+ }
+ case TGSI_OPCODE_ENDSWITCH: {
+ --nesting_lvl;
+ current->set_end(line-1);
+
+ if (current->type() != sct_switch) {
+ current = current->parent();
+ }
+ current = current->parent();
+ break;
+ }
+ case TGSI_OPCODE_CASE:
+ if (inst->src[0].file == PROGRAM_TEMPORARY) {
+ acc[inst->src[0].index].append(line, acc_read, current);
+ }
+ /* fall through */
+ case TGSI_OPCODE_DEFAULT: {
+ auto scope_type = (inst->op == TGSI_OPCODE_CASE) ?
+ sct_switch_case : sct_switch_default;
+ if (current->type() == sct_switch) {
+ current = make_scope(current, scope_type, current->id(),
+ nesting_lvl, line);
+ } else {
+ auto p = current->parent();
+ auto scope = make_scope(p, scope_type, p->id(),
+ p->level(), line);
+ if (current->end() == -1)
+ scope->set_previous(current);
+ current = scope;
+ }
+ break;
+ }
+ case TGSI_OPCODE_BRK: {
+ if ((current->type() == sct_switch_case) ||
+ (current->type() == sct_switch_default)) {
+ current->set_end(line-1);
+ }
+ /* Make sure that the nearest enclosing scope is a loop
+ * and not a switch case.
+ * Apart from that this is like a continue, just
+ * a bit more final */
+ else if (current->enclosed_by_loop_prior_to_switch()) {
+ current->set_continue(current, line);
+ }
+ break;
+ }
+ case TGSI_OPCODE_CONT: {
+ current->set_continue(current, line);
+ break;
+ }
+ default: {
+ for (unsigned j = 0; j < num_inst_src_regs(inst); j++) {
+ if (inst->src[j].file == PROGRAM_TEMPORARY) {
+ acc[inst->src[j].index].append(line, acc_read, current);
+ }
+ }
+ for (unsigned j = 0; j < inst->tex_offset_num_offset; j++) {
+ if (inst->tex_offsets[j].file == PROGRAM_TEMPORARY) {
+ acc[inst->tex_offsets[j].index].append(line, acc_read, current);
+ }
+ }
+ for (unsigned j = 0; j < num_inst_dst_regs(inst); j++) {
+ if (inst->dst[j].file == PROGRAM_TEMPORARY) {
+ acc[inst->dst[j].index].append(line, acc_write, current);
+ }
+ }
+ }
+ }
+
+ ++line;
+ }
+
+ /* make sure last scope is closed, even though no
+ * TGSI_OPCODE_END was given */
+ if (current->end() < 0) {
+ current->set_end(line-1);
+ }
+
+ for(int i = 1; i < ntemps; ++i) {
+ lifetimes[i] = acc[i].get_required_lifetime();
+ }
+ delete[] acc;
+ ralloc_free(scopes);
+}
+
+prog_scope::prog_scope():
+ prog_scope(nullptr, sct_unknown, -1, -1, -1)
+{
+}
+
+prog_scope::prog_scope(e_scope_type type, int id, int lvl, int s_begin):
+ prog_scope(nullptr, type, id, lvl, s_begin)
+{
+}
+
+prog_scope::prog_scope(prog_scope *p, e_scope_type type, int id, int lvl,
+ int s_begin):
+ scope_type(type),
+ scope_id(id),
+ nested_level(lvl),
+ scope_begin(s_begin),
+ scope_end(-1),
+ loop_continue(numeric_limits<int>::max()),
+ scope_of_loop_to_continue(nullptr),
+ previous_switchcase(nullptr),
+ parent_scope(p)
+{
+
+}
+
+bool prog_scope::in_loop() const
+{
+ if (scope_type == sct_loop)
+ return true;
+ if (parent_scope)
+ return parent_scope->in_loop();
+ return false;
+}
+
+prog_scope *prog_scope::get_innermost_loop()
+{
+ if (scope_type == sct_loop)
+ return this;
+ if (parent_scope)
+ return parent_scope->get_innermost_loop();
+ else
+ return nullptr;
+}
+
+prog_scope *
+prog_scope::get_outermost_loop()
+{
+ prog_scope *loop = nullptr;
+ if (scope_type == sct_loop)
+ loop = this;
+ if (parent_scope) {
+ prog_scope *l = parent_scope->get_outermost_loop();
+ if (l)
+ loop = l;
+ }
+ return loop;
+}
+
+bool prog_scope::contains(prog_scope *other) const
+{
+ return (begin() <= other->begin()) && (end() >= other->end());
+}
+
+bool prog_scope::is_conditional() const
+{
+ return scope_type == sct_if || scope_type == sct_else ||
+ scope_type == sct_switch_case || scope_type == sct_switch_default;
+}
+
+prog_scope *prog_scope::in_conditional()
+{
+ if (is_conditional())
+ return this;
+ if (parent_scope)
+ return parent_scope->in_conditional();
+ return nullptr;
+}
+
+bool prog_scope::enclosed_by_loop_prior_to_switch()
+{
+ if (scope_type == sct_loop)
+ return true;
+ if (scope_type == sct_switch_case ||
+ scope_type == sct_switch_default ||
+ scope_type == sct_switch)
+ return false;
+ if (parent_scope)
+ return parent_scope->enclosed_by_loop_prior_to_switch();
+ else
+ return false;
+}
+
+prog_scope *prog_scope::in_ifelse()
+{
+ if ((scope_type == sct_if) ||
+ (scope_type == sct_else))
+ return this;
+ else if (parent_scope)
+ return parent_scope->in_ifelse();
+ else
+ return nullptr;
+}
+
+prog_scope *prog_scope::in_switchcase()
+{
+ if ((scope_type == sct_switch_case) ||
+ (scope_type == sct_switch_default))
+ return this;
+ else if (parent_scope)
+ return parent_scope->in_switchcase();
+ else
+ return nullptr;
+}
+
+void prog_scope::set_previous(prog_scope *prev)
+{
+ previous_switchcase = prev;
+}
+
+void prog_scope::set_end(int end)
+{
+ if (scope_end == -1) {
+ scope_end = end;
+ if (previous_switchcase)
+ parent_scope->set_end(end);
+ }
+}
+
+void prog_scope::set_continue(prog_scope *scope, int line)
+{
+ if (scope_type == sct_loop) {
+ scope_of_loop_to_continue = scope;
+ loop_continue = line;
+ } else if (parent_scope)
+ parent_scope->set_continue(scope, line);
+}
+
+temp_access::temp_access():
+ last_read_scope(nullptr),
+ first_read_scope(nullptr),
+ first_write_scope(nullptr),
+ first_write(-1),
+ last_read(-1),
+ last_write(-1),
+ first_read(numeric_limits<int>::max())
+{
+}
+
+void temp_access::append(int line, e_acc_type acc, prog_scope *scope)
+{
+ last_write = line;
+ if (acc == acc_read) {
+ last_read = line;
+ last_read_scope = scope;
+ if (first_read > line) {
+ first_read = line;
+ first_read_scope = scope;
+ }
+ } else {
+ if (first_write == -1) {
+ first_write = line;
+ first_write_scope = scope;
+ }
+ }
+}
+
+inline lifetime make_lifetime(int b, int e)
+{
+ return lifetime{b,e};
+}
+
+lifetime temp_access::get_required_lifetime()
+{
+ bool keep_for_full_loop = false;
+ prog_scope *target_write_scope = first_write_scope;
+ prog_scope *target_read_scope = nullptr;
+
+ /* this temp is only read, this is undefined
+ * behaviour, so we can use the register otherwise */
+ if (!first_write_scope) {
+ return make_lifetime(-1, -1);
+ }
+
+ /* Only written to, just make sure that renaming
+ * doesn't reuse this register too early (corner
+ * case is the one opcode with two destinations) */
+ if (!last_read_scope) {
+ return make_lifetime(first_write, last_write + 1);
+ }
+
+ if (first_read <= first_write) {
+ /* If we conditionally read first before write and we are in a
+ * loop that also contains the first write, then this read is unlikely
+ * to be undefined, and we will have to keep the variable for
+ * all containing loops, otherwise we don't care */
+ prog_scope *fr_conditional_scope = first_read_scope->in_conditional();
+ if (fr_conditional_scope) {
+ prog_scope *fr_loop = fr_conditional_scope->get_outermost_loop();
+ if (fr_loop && fr_loop->contains(target_write_scope)) {
+ keep_for_full_loop = true;
+ target_write_scope = fr_loop;
+ }
+ }
+ }
+
+ /* If the first write is conditional within a loop, and the
+ * last read is not within the same condition scope, then we
+ * have to keep the temporary for all containing loops */
+ if (!keep_for_full_loop) {
+ auto fw_conditional_scope = target_write_scope->in_conditional();
+ if (fw_conditional_scope && fw_conditional_scope->in_loop()) {
+ if (!fw_conditional_scope->contains(last_read_scope))
+ keep_for_full_loop = true;
+ }
+ }
+
+ /* evaluate the shared scope */
+ int target_level = -1;
+
+ /* If the variable must be kept for all the loops, then
+ * find the outermost loop that contains both. last read and
+ * first write */
+ target_read_scope = last_read_scope;
+ if (keep_for_full_loop) {
+ prog_scope *target_scope = target_read_scope->get_outermost_loop();
+
+ /* If the read scope is within a loop, then just go up until
+ * the scope also containes the first write, otherwise do the
+ * same for the write scope */
+ if (target_scope) {
+ while (!target_scope->contains(target_write_scope))
+ target_scope = target_scope->parent();
+ } else {
+ target_scope = target_write_scope->get_outermost_loop();
+ assert(target_scope && "at this point read or write must be in a loop");
+ while (!target_scope->contains(target_read_scope))
+ target_scope = target_scope->parent();
+ }
+ target_level = target_scope->level();
+ }
+
+ /* The shared scope is not yet defined, so find the scope that
+ * contains first write and last read */
+ while (target_level < 0) {
+ if (target_read_scope->contains(target_write_scope)) {
+ target_level = target_read_scope->level();
+ } else if (target_write_scope->contains(target_read_scope)) {
+ target_level = target_write_scope->level();
+ } else {
+ target_read_scope = target_read_scope->parent();
+ }
+ }
+
+
+ /* propagate the read scope to the target_level */
+ while (last_read_scope->level() > target_level) {
+
+ /* if the read is in a loop we need to extend the
+ * variables life time to the end of that loop */
+ if (last_read_scope->type() == sct_loop) {
+ last_read = last_read_scope->end();
+ }
+ last_read_scope = last_read_scope->parent();
+ }
+
+ /* Prepare the write scope before propagating it. */
+ /* propagate lifetime also if there was a continue/break
+ * in a loop and the write was after it (so it constitutes
+ * a conditional write */
+ if (first_write_scope->loop_continue_line() < first_write) {
+ keep_for_full_loop = true;
+ }
+
+ /* propagate lifetimes before moving to upper scopes */
+ if ((first_write_scope->type() == sct_loop) &&
+ (keep_for_full_loop || (first_read < first_write))) {
+ first_write = first_write_scope->begin();
+ int lr = first_write_scope->end();
+ if (last_read < lr)
+ last_read = lr;
+ }
+
+ /* propagate the first_write scope to the target_level */
+ while (target_level < first_write_scope->level()) {
+
+ first_write_scope = first_write_scope->parent();
+
+ if (first_write_scope->loop_continue_line() < first_write) {
+ keep_for_full_loop = true;
+ }
+
+ /* if the value is conditionally written in a loop
+ * then propagate its lifetime to the full loop */
+ if (first_write_scope->type() == sct_loop) {
+ if (keep_for_full_loop) {
+ first_write = first_write_scope->begin();
+ int lr = first_write_scope->end();
+ if (last_read < lr)
+ last_read = lr;
+ }
+ }
+
+ /* if we currently don't propagate the lifetime but
+ * the enclosing scope is a conditional within a loop
+ * up to the last-read level we need to propagate,
+ * todo: to tighten the life time check whether the value
+ * is written in all consitional code path below the loop */
+ if (!keep_for_full_loop &&
+ first_write_scope->is_conditional() &&
+ first_write_scope->in_loop()) {
+ keep_for_full_loop = true;
+ }
+ }
+
+
+ /* We do not correct the last_write for scope, but
+ * if it is past the last_read we have to keep the
+ * temporary alive past this instructions */
+ if (last_write > last_read) {
+ last_read = last_write + 1;
+ }
+
+ return make_lifetime(first_write, last_read);
+}
+
+/* Wrapper function for the temporary register life time estimation.
+*/
+
+void
+estimate_temporary_lifetimes(void *mem_ctx, exec_list *instructions,
+ int ntemps, struct lifetime *lifetimes)
+{
+ return tgsi_temp_lifetime(mem_ctx).get_lifetimes(instructions, ntemps, lifetimes);
+}
diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
new file mode 100644
index 0000000000..0637ffab08
--- /dev/null
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
@@ -0,0 +1,33 @@
+/*
+ * Copyright © 2017 Gert Wollny
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#include "st_glsl_to_tgsi_private.h"
+
+struct lifetime {
+ int begin;
+ int end;
+};
+
+void
+estimate_temporary_lifetimes(void *mem_ctx, exec_list *instructions,
+ int ntemps, struct lifetime *lt);
--
2.13.0
More information about the mesa-dev
mailing list