[Mesa-dev] [PATCH v2 2/3] mesa/st: glsl_to_tgsi Implement a new lifetime tracker for temporaries

Gert Wollny gw.fossdev at gmail.com
Fri Jun 16 09:32:01 UTC 2017


This patch adds new classes and tests to implement a tracker for the
life time of temporary registers for the register renaming stage of
glsl_to_tgsi. The tracker aims at estimating the shortest possible
life time for each register. The code base requires c++11, the flag is
propagated from the LLVM_CXXFLAGS.
---
 configure.ac                                       |   1 +
 src/mesa/Makefile.am                               |   4 +-
 src/mesa/Makefile.sources                          |   2 +
 src/mesa/state_tracker/st_glsl_to_tgsi_private.cpp | 202 +++++
 src/mesa/state_tracker/st_glsl_to_tgsi_private.h   | 164 ++++
 .../state_tracker/st_glsl_to_tgsi_temprename.cpp   | 674 +++++++++++++++
 .../state_tracker/st_glsl_to_tgsi_temprename.h     |  30 +
 src/mesa/state_tracker/tests/Makefile.am           |  40 +
 .../tests/test_glsl_to_tgsi_lifetime.cpp           | 959 +++++++++++++++++++++
 9 files changed, 2074 insertions(+), 2 deletions(-)
 create mode 100644 src/mesa/state_tracker/st_glsl_to_tgsi_private.cpp
 create mode 100644 src/mesa/state_tracker/st_glsl_to_tgsi_private.h
 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
 create mode 100644 src/mesa/state_tracker/tests/Makefile.am
 create mode 100644 src/mesa/state_tracker/tests/test_glsl_to_tgsi_lifetime.cpp

diff --git a/configure.ac b/configure.ac
index 6c67d27084..855d06779c 100644
--- a/configure.ac
+++ b/configure.ac
@@ -2827,6 +2827,7 @@ AC_CONFIG_FILES([Makefile
 		src/mesa/drivers/osmesa/osmesa.pc
 		src/mesa/drivers/x11/Makefile
 		src/mesa/main/tests/Makefile
+		src/mesa/state_tracker/tests/Makefile
 		src/util/Makefile
 		src/util/tests/hash_table/Makefile
 		src/vulkan/Makefile])
diff --git a/src/mesa/Makefile.am b/src/mesa/Makefile.am
index 53f311d2a9..72ffd61212 100644
--- a/src/mesa/Makefile.am
+++ b/src/mesa/Makefile.am
@@ -19,7 +19,7 @@
 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 # IN THE SOFTWARE.
 
-SUBDIRS = . main/tests
+SUBDIRS = . main/tests state_tracker/tests
 
 if HAVE_XLIB_GLX
 SUBDIRS += drivers/x11
@@ -101,7 +101,7 @@ AM_CFLAGS = \
 	$(VISIBILITY_CFLAGS) \
 	$(MSVC2013_COMPAT_CFLAGS)
 AM_CXXFLAGS = \
-	$(LLVM_CFLAGS) \
+        $(LLVM_CXXFLAGS) \
 	$(VISIBILITY_CXXFLAGS) \
 	$(MSVC2013_COMPAT_CXXFLAGS)
 
diff --git a/src/mesa/Makefile.sources b/src/mesa/Makefile.sources
index 21f9167bda..a68e9d2afe 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_private.cpp b/src/mesa/state_tracker/st_glsl_to_tgsi_private.cpp
new file mode 100644
index 0000000000..d3115a4bfc
--- /dev/null
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_private.cpp
@@ -0,0 +1,202 @@
+/*
+ * Copyright © 2010 Intel Corporation
+ * Copyright © 2011 Bryan Cain
+ * 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"
+#include <tgsi/tgsi_info.h>
+#include <mesa/program/prog_instruction.h>
+
+using std::vector;
+
+extern int swizzle_for_size(int size);
+
+static int swizzle_for_type(const glsl_type *type, int component = 0)
+{
+   unsigned num_elements = 4;
+
+   if (type) {
+      type = type->without_array();
+      if (type->is_scalar() || type->is_vector() || type->is_matrix())
+         num_elements = type->vector_elements;
+   }
+
+   int swizzle = swizzle_for_size(num_elements);
+   assert(num_elements + component <= 4);
+
+   swizzle += component * MAKE_SWIZZLE4(1, 1, 1, 1);
+   return swizzle;
+}
+
+
+
+st_src_reg::st_src_reg(gl_register_file file, int index, const glsl_type *type,
+                       int component, unsigned array_id)
+{
+   assert(file != PROGRAM_ARRAY || array_id != 0);
+   this->file = file;
+   this->index = index;
+   this->swizzle = swizzle_for_type(type, component);
+   this->negate = 0;
+   this->abs = 0;
+   this->index2D = 0;
+   this->type = type ? type->base_type : GLSL_TYPE_ERROR;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->double_reg2 = false;
+   this->array_id = array_id;
+   this->is_double_vertex_input = false;
+}
+
+st_src_reg::st_src_reg(gl_register_file file, int index, enum glsl_base_type type)
+{
+   assert(file != PROGRAM_ARRAY); /* need array_id > 0 */
+   this->type = type;
+   this->file = file;
+   this->index = index;
+   this->index2D = 0;
+   this->swizzle = SWIZZLE_XYZW;
+   this->negate = 0;
+   this->abs = 0;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->double_reg2 = false;
+   this->array_id = 0;
+   this->is_double_vertex_input = false;
+}
+
+st_src_reg::st_src_reg(gl_register_file file, int index, enum glsl_base_type type, int index2D)
+{
+   assert(file != PROGRAM_ARRAY); /* need array_id > 0 */
+   this->type = type;
+   this->file = file;
+   this->index = index;
+   this->index2D = index2D;
+   this->swizzle = SWIZZLE_XYZW;
+   this->negate = 0;
+   this->abs = 0;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->double_reg2 = false;
+   this->array_id = 0;
+   this->is_double_vertex_input = false;
+}
+
+st_src_reg::st_src_reg()
+{
+   this->type = GLSL_TYPE_ERROR;
+   this->file = PROGRAM_UNDEFINED;
+   this->index = 0;
+   this->index2D = 0;
+   this->swizzle = 0;
+   this->negate = 0;
+   this->abs = 0;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->double_reg2 = false;
+   this->array_id = 0;
+   this->is_double_vertex_input = false;
+}
+
+st_src_reg st_src_reg::get_abs()
+{
+   st_src_reg reg = *this;
+   reg.negate = 0;
+   reg.abs = 1;
+   return reg;
+}
+
+st_src_reg::st_src_reg(st_dst_reg reg)
+{
+   this->type = reg.type;
+   this->file = reg.file;
+   this->index = reg.index;
+   this->swizzle = SWIZZLE_XYZW;
+   this->negate = 0;
+   this->abs = 0;
+   this->reladdr = reg.reladdr;
+   this->index2D = reg.index2D;
+   this->reladdr2 = reg.reladdr2;
+   this->has_index2 = reg.has_index2;
+   this->double_reg2 = false;
+   this->array_id = reg.array_id;
+   this->is_double_vertex_input = false;
+}
+
+st_dst_reg::st_dst_reg(st_src_reg reg)
+{
+   this->type = reg.type;
+   this->file = reg.file;
+   this->index = reg.index;
+   this->writemask = WRITEMASK_XYZW;
+   this->reladdr = reg.reladdr;
+   this->index2D = reg.index2D;
+   this->reladdr2 = reg.reladdr2;
+   this->has_index2 = reg.has_index2;
+   this->array_id = reg.array_id;
+}
+
+st_dst_reg::st_dst_reg(gl_register_file file, int writemask, enum glsl_base_type type, int index)
+{
+   assert(file != PROGRAM_ARRAY); /* need array_id > 0 */
+   this->file = file;
+   this->index = index;
+   this->index2D = 0;
+   this->writemask = writemask;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->type = type;
+   this->array_id = 0;
+}
+
+st_dst_reg::st_dst_reg(gl_register_file file, int writemask, enum glsl_base_type type)
+{
+   assert(file != PROGRAM_ARRAY); /* need array_id > 0 */
+   this->file = file;
+   this->index = 0;
+   this->index2D = 0;
+   this->writemask = writemask;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->type = type;
+   this->array_id = 0;
+}
+
+st_dst_reg::st_dst_reg()
+{
+   this->type = GLSL_TYPE_ERROR;
+   this->file = PROGRAM_UNDEFINED;
+   this->index = 0;
+   this->index2D = 0;
+   this->writemask = 0;
+   this->reladdr = NULL;
+   this->reladdr2 = NULL;
+   this->has_index2 = false;
+   this->array_id = 0;
+}
diff --git a/src/mesa/state_tracker/st_glsl_to_tgsi_private.h b/src/mesa/state_tracker/st_glsl_to_tgsi_private.h
new file mode 100644
index 0000000000..d729bc008d
--- /dev/null
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_private.h
@@ -0,0 +1,164 @@
+/*
+ * Copyright © 2010 Intel Corporation
+ * Copyright © 2011 Bryan Cain
+ * 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 <mesa/main/mtypes.h>
+#include <compiler/glsl_types.h>
+#include <compiler/glsl/ir.h>
+#include <tgsi/tgsi_info.h>
+#include <stack>
+#include <vector>
+
+class st_dst_reg;
+
+/**
+ * This struct is a corresponding struct to TGSI ureg_src.
+ */
+class st_src_reg {
+public:
+	st_src_reg(gl_register_file file, int index, const glsl_type *type,
+	           int component = 0, unsigned array_id = 0);
+
+	st_src_reg(gl_register_file file, int index, enum glsl_base_type type);
+
+	st_src_reg(gl_register_file file, int index, enum glsl_base_type type, int index2D);
+
+	st_src_reg();
+
+	explicit st_src_reg(st_dst_reg reg);
+
+   st_src_reg get_abs();
+
+   int32_t index; /**< temporary index, VERT_ATTRIB_*, VARYING_SLOT_*, etc. */
+   int16_t index2D;
+
+   uint16_t swizzle; /**< SWIZZLE_XYZWONEZERO swizzles from Mesa. */
+   int negate:4; /**< NEGATE_XYZW mask from mesa */
+   unsigned abs:1;
+   enum glsl_base_type type:5; /** GLSL_TYPE_* from GLSL IR (enum glsl_base_type) */
+   unsigned has_index2:1;
+   gl_register_file file:5; /**< PROGRAM_* from Mesa */
+   /*
+    * Is this the second half of a double register pair?
+    * currently used for input mapping only.
+    */
+   unsigned double_reg2:1;
+   unsigned is_double_vertex_input:1;
+   unsigned array_id:10;
+   /** Register index should be offset by the integer in this reg. */
+   st_src_reg *reladdr;
+   st_src_reg *reladdr2;
+
+};
+
+class st_dst_reg {
+public:
+   st_dst_reg(gl_register_file file, int writemask, enum glsl_base_type type, int index);
+
+   st_dst_reg(gl_register_file file, int writemask, enum glsl_base_type type);
+
+   st_dst_reg();
+
+   explicit st_dst_reg(st_src_reg reg);
+
+   int32_t index; /**< temporary index, VERT_ATTRIB_*, VARYING_SLOT_*, etc. */
+   int16_t index2D;
+   gl_register_file file:5; /**< PROGRAM_* from Mesa */
+   unsigned writemask:4; /**< Bitfield of WRITEMASK_[XYZW] */
+   enum glsl_base_type type:5; /** GLSL_TYPE_* from GLSL IR (enum glsl_base_type) */
+   unsigned has_index2:1;
+   unsigned array_id:10;
+
+   /** Register index should be offset by the integer in this reg. */
+   st_src_reg *reladdr;
+   st_src_reg *reladdr2;
+};
+
+class glsl_to_tgsi_instruction : public exec_node {
+public:
+   DECLARE_RALLOC_CXX_OPERATORS(glsl_to_tgsi_instruction)
+
+   st_dst_reg dst[2];
+   st_src_reg src[4];
+   st_src_reg resource; /**< sampler or buffer register */
+   st_src_reg *tex_offsets;
+
+   /** Pointer to the ir source this tree came from for debugging */
+   ir_instruction *ir;
+
+   unsigned op:8; /**< TGSI opcode */
+   unsigned saturate:1;
+   unsigned is_64bit_expanded:1;
+   unsigned sampler_base:5;
+   unsigned sampler_array_size:6; /**< 1-based size of sampler array, 1 if not array */
+   unsigned tex_target:4; /**< One of TEXTURE_*_INDEX */
+   glsl_base_type tex_type:5;
+   unsigned tex_shadow:1;
+   unsigned image_format:9;
+   unsigned tex_offset_num_offset:3;
+   unsigned dead_mask:4; /**< Used in dead code elimination */
+   unsigned buffer_access:3; /**< buffer access type */
+
+   const struct tgsi_opcode_info *info;
+};
+
+struct rename_reg_pair {
+   bool valid;
+   int new_reg;
+};
+
+inline bool
+is_resource_instruction(unsigned opcode)
+{
+   switch (opcode) {
+   case TGSI_OPCODE_RESQ:
+   case TGSI_OPCODE_LOAD:
+   case TGSI_OPCODE_ATOMUADD:
+   case TGSI_OPCODE_ATOMXCHG:
+   case TGSI_OPCODE_ATOMCAS:
+   case TGSI_OPCODE_ATOMAND:
+   case TGSI_OPCODE_ATOMOR:
+   case TGSI_OPCODE_ATOMXOR:
+   case TGSI_OPCODE_ATOMUMIN:
+   case TGSI_OPCODE_ATOMUMAX:
+   case TGSI_OPCODE_ATOMIMIN:
+   case TGSI_OPCODE_ATOMIMAX:
+      return true;
+   default:
+      return false;
+   }
+}
+
+inline unsigned
+num_inst_dst_regs(const glsl_to_tgsi_instruction *op)
+{
+   return op->info->num_dst;
+}
+
+inline unsigned
+num_inst_src_regs(const glsl_to_tgsi_instruction *op)
+{
+   return op->info->is_tex || is_resource_instruction(op->op) ?
+      op->info->num_src - 1 : op->info->num_src;
+}
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..a2e8e3778c
--- /dev/null
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.cpp
@@ -0,0 +1,674 @@
+/*
+ * 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 <stack>
+#include <algorithm>
+#include <limits>
+
+using std::vector;
+using std::stack;
+using std::pair;
+using std::make_pair;
+using std::numeric_limits;
+
+
+typedef int scope_idx;
+
+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(e_scope_type type, int my_idx, int id, int lvl, int s_begin,
+              vector<prog_scope>& scopes);
+   prog_scope(scope_idx  p, e_scope_type type, int my_idx, int id,
+              int lvl, int s_begin, vector<prog_scope>& scopes);
+
+   e_scope_type type() const { return scope_type; }
+   scope_idx parent() const { 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;}
+
+   scope_idx in_ifelse() const;
+   scope_idx in_switchcase() const;
+
+   bool in_loop() const;
+   scope_idx get_parent_loop() const;
+   bool is_conditional() const;
+   bool contains(scope_idx idx) const;
+   void set_end(int end);
+   void set_previous(scope_idx  prev);
+   void set_continue(scope_idx scope, int i);
+   bool enclosed_by_loop_prior_to_switch();
+private:
+
+   e_scope_type scope_type;
+   int scope_id;
+   int nested_level;
+   int scope_begin;
+   int scope_end;
+   int loop_continue;
+
+   scope_idx my_idx;
+   scope_idx scope_of_loop_to_continue;
+   scope_idx previous_switchcase;
+   scope_idx parent_scope;
+
+   vector<prog_scope>& scopes;
+};
+
+class temp_access {
+
+public:
+   temp_access(vector<prog_scope>& scopes);
+   void append(int index, e_acc_type rw, scope_idx pstate);
+   pair<int, int> get_required_lifetime();
+
+private:
+
+   struct temp_access_record {
+      int index;
+      e_acc_type acc;
+      scope_idx prog_scope;
+   };
+
+   std::vector<prog_scope>& scopes;
+
+   bool keep_for_full_loop;
+
+   scope_idx last_read_scope;
+   scope_idx undefined_read_scope;
+   scope_idx first_write_scope;
+
+   int first_write;
+   int last_read;
+   int last_write;
+   int undefined_read;
+};
+
+
+class tgsi_temp_lifetime {
+
+public:
+
+   tgsi_temp_lifetime();
+
+   vector<std::pair<int, int> >  get_lifetimes(exec_list *instructions,
+                                               int ntemps) const;
+private:
+
+   scope_idx make_scope(e_scope_type type, int id, int lvl, int s_begin) const;
+   scope_idx make_scope(scope_idx  p, e_scope_type type, int id,
+                             int lvl, int s_begin) const;
+
+   void evaluate();
+
+   mutable vector<prog_scope> scopes;
+
+};
+
+tgsi_temp_lifetime::tgsi_temp_lifetime()
+{
+   scopes.reserve(20);
+}
+
+scope_idx
+tgsi_temp_lifetime::make_scope(e_scope_type type, int id, int lvl,
+                               int s_begin)const
+{
+   int idx = scopes.size();
+   scopes.push_back(prog_scope(type, idx, id, lvl, s_begin, scopes));
+   return idx;
+}
+
+scope_idx
+tgsi_temp_lifetime::make_scope(scope_idx  p, e_scope_type type, int id,
+                               int lvl, int s_begin) const
+{
+   int idx = scopes.size();
+   scopes.push_back(prog_scope(p, type, idx, id, lvl, s_begin, scopes));
+   return idx;
+}
+
+vector<pair<int, int> >
+tgsi_temp_lifetime::get_lifetimes(exec_list *instructions, int ntemps) const
+{
+   int line = 0;
+   int loop_id = 0;
+   int if_id = 0;
+   int switch_id = 0;
+   int nesting_lvl = 0;
+   bool is_at_end = false;
+   stack<scope_idx> scope_stack;
+
+   std::vector<std::pair<int, int> > lifetimes(ntemps);
+   vector<temp_access> acc(ntemps, temp_access(scopes));
+
+   scope_idx current = make_scope(sct_outer, 0, nesting_lvl++, line);
+
+   foreach_in_list(glsl_to_tgsi_instruction, inst, instructions) {
+      if (is_at_end) {
+         // shader has instructions past end marker; we ignore this
+         break;
+      }
+
+      switch (inst->op) {
+      case TGSI_OPCODE_BGNLOOP: {
+         scope_idx scope = make_scope(current, sct_loop, loop_id,
+                                           nesting_lvl, line);
+         ++loop_id;
+         ++nesting_lvl;
+         scope_stack.push(current);
+         current = scope;
+         break;
+      }
+      case TGSI_OPCODE_ENDLOOP: {
+         --nesting_lvl;
+         scopes[current].set_end(line);
+         current = scope_stack.top();
+         scope_stack.pop();
+         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);
+         }
+         scope_idx scope = make_scope(current, sct_if, if_id, nesting_lvl, line);
+         ++if_id;
+         ++nesting_lvl;
+         scope_stack.push(current);
+         current = scope;
+         break;
+      }
+      case TGSI_OPCODE_ELSE: {
+         scopes[current].set_end(line-1);
+         current = make_scope(scopes[current].parent(), sct_else,
+                              scopes[current].id(), scopes[current].level(), line);
+         break;
+      }
+      case TGSI_OPCODE_END:{
+         scopes[current].set_end(line);
+         is_at_end = true;
+         break;
+      }
+      case TGSI_OPCODE_ENDIF:{
+         --nesting_lvl;
+         scopes[current].set_end(line-1);
+         current = scope_stack.top();
+         scope_stack.pop();
+         break;
+      }
+      case TGSI_OPCODE_SWITCH: {
+         scope_idx scope = make_scope(current, sct_switch, switch_id,
+                                      nesting_lvl, line);
+         ++nesting_lvl;
+         ++switch_id;
+         scope_stack.push(current);
+         current = scope;
+         break;
+      }
+      case TGSI_OPCODE_ENDSWITCH: {
+         --nesting_lvl;
+         scopes[current].set_end(line-1);
+
+         // remove the case level
+         if  (scopes[current].type() != sct_switch ) {
+            current = scope_stack.top();
+            scope_stack.pop();
+         }
+         current = scope_stack.top();
+         scope_stack.pop();
+         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 ( scopes[current].type() == sct_switch ) {
+            scope_stack.push(current);
+            current = make_scope(current, scope_type, scopes[current].id(),
+                                 nesting_lvl, line);
+         }else{
+            auto p = scopes[current].parent();
+            auto scope = make_scope(p, scope_type, scopes[p].id(),
+                                    scopes[p].level(), line);
+            if (scopes[current].end() == -1)
+               scopes[scope].set_previous(current);
+            current = scope;
+         }
+         break;
+      }
+      case TGSI_OPCODE_BRK:  {
+         if ( (scopes[current].type() == sct_switch_case) ||
+              (scopes[current].type() == sct_switch_default)) {
+            scopes[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 (scopes[current].enclosed_by_loop_prior_to_switch()) {
+            scopes[current].set_continue(current, line);
+         }
+         break;
+      }
+      case TGSI_OPCODE_CONT: {
+         scopes[current].set_continue(current, line);
+         break;
+      }
+
+      default: {
+
+         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);
+            }
+         }
+
+         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);
+            }
+         }
+
+      } // end default
+      } // end switch (op)
+
+      ++line;
+   }
+
+   // make sure last scope is closed, even though no
+   // TGSI_OPCODE_END was given
+   if (scopes[current].end() < 0) {
+      scopes[current].set_end(line-1);
+   }
+
+   for(unsigned i = 1; i < lifetimes.size(); ++i) {
+      lifetimes[i] = acc[i].get_required_lifetime();
+   }
+   scopes.clear();
+   return lifetimes;
+}
+
+
+prog_scope::prog_scope(e_scope_type type, int idx, int id,
+                                           int lvl, int s_begin,
+                                           std::vector<prog_scope>& s):
+   prog_scope(-1, type, idx, id, lvl, s_begin, s)
+{
+}
+
+prog_scope::prog_scope(scope_idx p, e_scope_type type,
+                                           int idx, int id, int lvl, int s_begin,
+                                           std::vector<prog_scope>& s):
+   scope_type(type),
+   scope_id(id),
+   nested_level(lvl),
+   scope_begin(s_begin),
+   scope_end(-1),
+   loop_continue(numeric_limits<int>::max()),
+   my_idx(idx),
+   scope_of_loop_to_continue(0),
+   previous_switchcase(0),
+   parent_scope(p),
+   scopes(s)
+{
+}
+
+bool prog_scope::in_loop() const
+{
+   if (scope_type == sct_loop)
+      return true;
+   if (parent_scope >= 0)
+      return scopes[parent_scope].in_loop();
+   return false;
+}
+
+scope_idx
+prog_scope::get_parent_loop() const
+{
+   if (scope_type == sct_loop)
+      return my_idx;
+   if (parent_scope >= 0)
+      return scopes[parent_scope].get_parent_loop();
+   else
+      return -1;
+}
+
+bool prog_scope::contains(scope_idx other) const
+{
+   return (begin() <= scopes[other].begin()) &&  (end() >= scopes[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;
+}
+
+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 >= 0)
+      return scopes[parent_scope].enclosed_by_loop_prior_to_switch();
+   else
+      return false;
+}
+
+scope_idx prog_scope::in_ifelse() const
+{
+   if ((scope_type == sct_if) ||
+       (scope_type == sct_else))
+      return my_idx;
+   else if (parent_scope >= 0)
+      return scopes[parent_scope].in_ifelse();
+   else
+      return -1;
+}
+
+scope_idx prog_scope::in_switchcase() const
+{
+   if ((scope_type == sct_switch_case) ||
+       (scope_type == sct_switch_default))
+      return my_idx;
+   else if (parent_scope >= 0)
+      return scopes[parent_scope].in_switchcase();
+   else
+      return -1;
+}
+
+void prog_scope::set_previous(scope_idx prev)
+{
+   previous_switchcase = prev;
+}
+
+void prog_scope::set_end(int end)
+{
+   if (scope_end == -1) {
+      scope_end = end;
+      if (previous_switchcase)
+         scopes[parent_scope].set_end(end);
+   }
+}
+
+void prog_scope::set_continue(scope_idx scope, int line)
+{
+   if (scope_type == sct_loop) {
+      scope_of_loop_to_continue = scope;
+      loop_continue = line;
+   } else if (parent_scope >= 0)
+      scopes[parent_scope].set_continue(scope, line);
+}
+
+temp_access::temp_access(std::vector<prog_scope>& s):
+   scopes(s),
+   keep_for_full_loop(false),
+   last_read_scope(-1),
+   undefined_read_scope(-1),
+   first_write_scope(-1),
+   first_write(-1),
+   last_read(-1),
+   last_write(-1),
+   undefined_read(numeric_limits<int>::max())
+{
+}
+
+void temp_access::append(int line, e_acc_type acc, scope_idx idx)
+{
+   last_write = line;
+   if (acc == acc_read) {
+      last_read = line;
+      last_read_scope = idx;
+      if (undefined_read > line) {
+         undefined_read = line;
+         undefined_read_scope = idx;
+      }
+   } else {
+      if (first_write == -1) {
+         first_write = line;
+         first_write_scope = idx;
+
+         // we write in an if-branch
+         auto fw_ifthen_scope = scopes[idx].in_ifelse();
+         if ((fw_ifthen_scope >= 0) && scopes[fw_ifthen_scope].in_loop()) {
+            // value not always written, in loops we must keep it
+            keep_for_full_loop = true;
+         } else {
+            // same thing for switch-case
+            auto fw_switch_scope = scopes[idx].in_switchcase();
+            if (fw_switch_scope >= 0 && scopes[fw_switch_scope].in_loop()) {
+               keep_for_full_loop = true;
+            }
+         }
+      }
+   }
+}
+
+pair<int, int> temp_access::get_required_lifetime()
+{
+   /* this temp is only read, this is undefined
+    behaviour, so we can use the register otherwise */
+   if (first_write_scope < 0) {
+      return make_pair(-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 < 0) {
+      return make_pair(first_write, first_write + 1);
+   }
+
+   // evaluate the shared scope
+   int target_level = -1;
+
+   while (target_level  < 0) {
+      if (scopes[last_read_scope].contains(first_write_scope)) {
+         target_level = scopes[last_read_scope].level();
+      } else if (scopes[first_write_scope].contains(last_read_scope)) {
+         target_level = scopes[first_write_scope].level();
+      } else {
+         // scopes (partially) disjunct, move up
+         if (scopes[last_read_scope].type() == sct_loop) {
+            last_read = scopes[last_read_scope].end();
+         }
+         last_read_scope = scopes[last_read_scope].parent();
+      }
+   }
+
+   // propagate the read scope to the target_level
+   while (scopes[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 (scopes[last_read_scope].type() == sct_loop) {
+         last_read = scopes[last_read_scope].end();
+      }
+      last_read_scope = scopes[last_read_scope].parent();
+   }
+
+   /* 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 (scopes[first_write_scope].loop_continue_line() < first_write) {
+      keep_for_full_loop  = true;
+   }
+
+   /* propagate lifetimes before moving to upper scopes */
+   if ((scopes[first_write_scope].type() == sct_loop) &&
+       (keep_for_full_loop || (undefined_read < first_write))) {
+      first_write = scopes[first_write_scope].begin();
+      int lr = scopes[first_write_scope].end();
+      if (last_read < lr)
+         last_read = lr;
+   }
+
+   // propagate the first_write scope to the target_level
+   while (target_level < scopes[first_write_scope].level()) {
+
+      first_write_scope = scopes[first_write_scope].parent();
+
+      if (scopes[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 (scopes[first_write_scope].type() == sct_loop) {
+         if (keep_for_full_loop || (undefined_read < first_write)) {
+            first_write = scopes[first_write_scope].begin();
+            int lr = scopes[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 &&
+          scopes[first_write_scope].is_conditional() &&
+          scopes[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_pair(first_write, last_read);
+}
+
+vector<pair<int, int>>
+estimate_temporary_lifetimes(exec_list *instructions, int ntemps)
+{
+   return tgsi_temp_lifetime().get_lifetimes(instructions, ntemps);
+}
+
+void evaluate_remapping(const std::vector<std::pair<int, int>>& lifetimes,
+                        struct rename_reg_pair *result)
+{
+   struct access_record {
+      int begin;
+      int end;
+      unsigned reg;
+      bool erase;
+   };
+
+   auto compare_begin = [](const access_record& a, const access_record& b) {
+      return a.begin < b.begin;
+   };
+   auto compare_end_begin = [](const access_record& a, const access_record& b) {
+      return a.end  <= b.begin;
+   };
+
+   vector<access_record> m(lifetimes.size() - 1);
+
+   for (unsigned i = 1; i < lifetimes.size(); ++i) {
+      m[i-1] =  {lifetimes[i].first, lifetimes[i].second, i, false};
+   }
+
+   std::sort(m.begin(), m.end(), compare_begin);
+
+   auto trgt = m.begin();
+   auto mend = m.end();
+   auto first_erase = mend;
+   auto search_start = trgt + 1;
+
+   while (trgt != mend) {
+
+      auto src = std::upper_bound(search_start, mend, *trgt, compare_end_begin);
+      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. The alternative
+          * to call m.erase(src) here would be quite expensive. */
+         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;
+      }
+   }
+}
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..04d5321682
--- /dev/null
+++ b/src/mesa/state_tracker/st_glsl_to_tgsi_temprename.h
@@ -0,0 +1,30 @@
+/*
+ * 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"
+
+std::vector<std::pair<int, int>>
+estimate_temporary_lifetimes(exec_list *instructions, int ntemps);
+
+void evaluate_remapping(const std::vector<std::pair<int, int>>& lt,
+                        struct rename_reg_pair *result);
diff --git a/src/mesa/state_tracker/tests/Makefile.am b/src/mesa/state_tracker/tests/Makefile.am
new file mode 100644
index 0000000000..ac6def682a
--- /dev/null
+++ b/src/mesa/state_tracker/tests/Makefile.am
@@ -0,0 +1,40 @@
+AM_CFLAGS = \
+        $(PTHREAD_CFLAGS)
+
+AM_CXXFLAGS = \
+        $(LLVM_CXXFLAGS)
+
+AM_CPPFLAGS = \
+	-I$(top_srcdir)/src/gtest/include \
+	-I$(top_srcdir)/src \
+	-I$(top_srcdir)/src/mapi \
+	-I$(top_builddir)/src/mesa \
+	-I$(top_srcdir)/src/mesa \
+	-I$(top_srcdir)/include \
+        -I$(top_srcdir)/src/gallium/include \
+        -I$(top_srcdir)/src/gallium/auxiliary \
+	$(DEFINES) $(INCLUDE_DIRS)
+
+TESTS = st-renumerate-test
+check_PROGRAMS = st-renumerate-test
+
+st_renumerate_test_SOURCES =			\
+	test_glsl_to_tgsi_lifetime.cpp
+
+st_renumerate_test_LDFLAGS = \
+        $(LLVM_LDFLAGS)
+
+st_renumerate_test_LDADD = \
+        $(top_builddir)/src/mesa/libmesagallium.la \
+        $(top_builddir)/src/mapi/shared-glapi/libglapi.la \
+        $(top_builddir)/src/gallium/auxiliary/libgallium.la \
+        $(top_builddir)/src/util/libmesautil.la \
+        $(top_builddir)/src/gallium/drivers/trace/libtrace.la \
+        $(top_builddir)/src/gallium/winsys/sw/null/libws_null.la \
+        $(top_builddir)/src/gallium/drivers/softpipe/libsoftpipe.la \
+        $(top_builddir)/src/gtest/libgtest.la \
+        $(GALLIUM_COMMON_LIB_DEPS) \
+        $(LLVM_LIBS) \
+	$(PTHREAD_LIBS) \
+        $(DLOPEN_LIBS) \
+	-ldl
diff --git a/src/mesa/state_tracker/tests/test_glsl_to_tgsi_lifetime.cpp b/src/mesa/state_tracker/tests/test_glsl_to_tgsi_lifetime.cpp
new file mode 100644
index 0000000000..a2c59fb28f
--- /dev/null
+++ b/src/mesa/state_tracker/tests/test_glsl_to_tgsi_lifetime.cpp
@@ -0,0 +1,959 @@
+/*
+ * 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 <state_tracker/st_glsl_to_tgsi_temprename.h>
+#include <tgsi/tgsi_ureg.h>
+#include <tgsi/tgsi_info.h>
+#include <compiler/glsl/list.h>
+#include <gtest/gtest.h>
+
+using std::vector;
+using std::pair;
+
+
+/* A line to describe a TGSI instruction for building mock shaders */
+struct MockCodeline {
+   MockCodeline(unsigned  _op): op(_op) {}
+   MockCodeline(unsigned _op, const vector<int>& _dst,
+                const vector<int>& _src, const vector<int>&_to):
+      op(_op), dst(_dst), src(_src), tex_offsets(_to){}
+   unsigned op;
+   vector<int> dst;
+   vector<int> src;
+   vector<int> tex_offsets;
+};
+
+/* A few constants to use in the mock shaders */
+const int in0 = 0;
+const int in1 = -1;
+const int in2 = -2;
+
+const int out0 = 0;
+const int out1 = -1;
+
+/* A  class to create a shader program to check the register allocation
+ * and renaming. The created exec_list is not completely set up and can
+ * only be used for the register tife-time analyis. */
+class MockShader {
+public:
+   MockShader(const vector<MockCodeline>& source);
+   ~MockShader();
+
+   void free();
+
+   exec_list* get_program();
+   int get_num_temps();
+private:
+   st_src_reg create_src_register(int src_idx);
+   st_dst_reg create_dst_register(int dst_idx);
+   exec_list* program;
+   int num_temps;
+   void *mem_ctx;
+};
+
+/* type for register lifetime expectation */
+using expectation = vector<vector<int>>;
+
+
+/* This is a teat class to check the exact life times of
+ * registers. */
+class LifetimeEvaluatorExactTest : public testing::Test {
+protected:
+   void run(const vector<MockCodeline>& code, const expectation& e);
+};
+
+/* This test class checks that the life time covers at least
+ * in the expected range. It is used for cases where we know that
+ * a the implementation could be improved on estimating the minimal
+ * life time.
+ */
+class LifetimeEvaluatorAtLeastTest : public testing::Test {
+protected:
+   void run(const vector<MockCodeline>& code, const expectation& e);
+};
+
+
+TEST_F(LifetimeEvaluatorExactTest, SimpleMoveAdd)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_UADD, {out0}, {1, in0}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run(code, expectation({{-1, -1}, {0,1}}));
+}
+
+
+TEST_F(LifetimeEvaluatorExactTest, SimpleMoveAddMove)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
+      { TGSI_OPCODE_MOV, {out0}, {2}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run(code, expectation({{-1, -1}, {0,1}, {1,2}}));
+}
+
+TEST_F(LifetimeEvaluatorExactTest, SimpleMoveAddMoveTexoffset)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_MOV, {2}, {in1}, {}},
+      { TGSI_OPCODE_UADD, {out0}, {}, {1,2}},
+      { TGSI_OPCODE_END}
+   };
+   run(code, expectation({{-1, -1}, {0,2}, {1,2}}));
+}
+
+
+TEST_F(LifetimeEvaluatorExactTest, SimpleMoveInLoop)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_BGNLOOP },
+      { TGSI_OPCODE_UADD, {2}, {1, in0}, {}},
+      { TGSI_OPCODE_UADD, {3}, {1, 2}, {}},
+      { TGSI_OPCODE_UADD, {3}, {3, in1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {3}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 5}, {2,3}, {3, 6}}));
+}
+
+
+/* in loop if/else value written only in one path, and read later
+ * - value must survive the whole loop */
+TEST_F(LifetimeEvaluatorExactTest, MoveInIfInLoop)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_BGNLOOP },
+      { TGSI_OPCODE_IF},
+      { TGSI_OPCODE_UADD, {2}, {1, in0}, {}},
+      { TGSI_OPCODE_ENDIF},
+      { TGSI_OPCODE_UADD, {3}, {1, 2}, {}},
+      { TGSI_OPCODE_UADD, {3}, {3, in1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {3}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 7}, {1,7}, {5, 8}}));
+}
+
+
+// in loop if/else value written in both path, and read later
+//   - value must survive from first write to last read in loop
+// for now we only check that the minimum life time is correct
+TEST_F(LifetimeEvaluatorAtLeastTest, WriteInIfAndElseInLoop)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_BGNLOOP },
+      { TGSI_OPCODE_IF},
+      { TGSI_OPCODE_UADD, {2}, {1, in0}, {}},
+      { TGSI_OPCODE_ELSE },
+      { TGSI_OPCODE_MOV, {2}, {1}, {}},
+      { TGSI_OPCODE_ENDIF},
+      { TGSI_OPCODE_UADD, {3}, {1, 2}, {}},
+      { TGSI_OPCODE_UADD, {3}, {3, in1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {3}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 9}, {3,7}, {7, 10}}));
+}
+
+/* in loop if/else value written in both path, red in else path
+ * before read and also read later- value must survive from first
+ * write to last read in loop */
+TEST_F(LifetimeEvaluatorExactTest, WriteInIfAndElseReadInElseInLoop)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_BGNLOOP },
+      { TGSI_OPCODE_IF},
+      { TGSI_OPCODE_UADD, {2}, {1, in0}, {}},
+      { TGSI_OPCODE_ELSE },
+      { TGSI_OPCODE_ADD, {2}, {1, 2}, {}},
+      { TGSI_OPCODE_ENDIF},
+      { TGSI_OPCODE_UADD, {3}, {1, 2}, {}},
+      { TGSI_OPCODE_UADD, {3}, {3, in1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {3}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 9}, {1,9}, {7, 10}}));
+}
+
+/* in loop if/else read in one path before written in the same loop
+ *   - value must survive the whole loop */
+TEST_F(LifetimeEvaluatorExactTest, ReadInIfInLoopBeforeWrite)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_BGNLOOP },
+      { TGSI_OPCODE_IF, {}, {in0}, {}},
+      { TGSI_OPCODE_UADD, {2}, {1, 3}, {}},
+      { TGSI_OPCODE_ENDIF},
+      { TGSI_OPCODE_UADD, {3}, {1, 2}, {}},
+      { TGSI_OPCODE_UADD, {3}, {3, in1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {3}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 7}, {1,7}, {1, 8}}));
+}
+
+/* Write in nested ifs in loop, for now we do test whether the
+ * life time is atleast what is required, but we know that the
+ * implementation doesn't do a full check and sets larger boundaries
+ */
+TEST_F(LifetimeEvaluatorAtLeastTest, NestedIfInLoopAlwaysWriteButNotPropagated)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ELSE},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_ELSE},
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+   {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ELSE},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },                    // 15
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{3, 14}}));
+}
+
+
+
+TEST_F(LifetimeEvaluatorExactTest, NestedIfInLoopWriteNotAlways)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ELSE},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_ELSE},
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },                    // 13
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 13}}));
+}
+
+
+/* if a continue is in the loop, all variables written after the
+ * continue and used outside the loop must be maintained for the
+ * whole loop */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterContinue)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_CONT},
+      {   TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 6}}));
+}
+
+/* if a continue is in the loop, all variables written after the
+ * continue and used outside the loop must be maintained for the
+ * whole outer loop */
+TEST_F(LifetimeEvaluatorExactTest, NestedLoopWithWriteAfterContinue)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_CONT},
+      {     TGSI_OPCODE_ENDIF},
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {   TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 8}}));
+}
+
+/* Test whether variable is kept also if the continue is in a
+ * higher scope than the variable write */
+TEST_F(LifetimeEvaluatorExactTest, NestedLoopWithWriteInLoopAfterContinue)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_CONT},
+      {     TGSI_OPCODE_ENDIF},
+      {     TGSI_OPCODE_BGNLOOP },
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 10}}));
+}
+
+/* if a continue is in the loop, all variables written after the
+ * continue and used outside the loop must be maintained for all
+ * loops including the read loop */
+TEST_F(LifetimeEvaluatorExactTest, Nested2LoopWithWriteAfterContinue)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_BGNLOOP },
+      {       TGSI_OPCODE_IF, {}, {in0}, {}},
+      {         TGSI_OPCODE_CONT},
+      {       TGSI_OPCODE_ENDIF},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 10}}));
+}
+
+/* if a break  is in the loop, all variables written after the
+ * break  and used outside the loop must be maintained for the
+ * whole loop */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterBreak)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_BRK},
+      {   TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 6}}));
+}
+
+/* if a break is in the loop, but inside a switch case, so it
+ * referes to the case and not to the loop, the variable doesn't
+ * need to survive the loop */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterBreakInSwitch)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {  TGSI_OPCODE_SWITCH, {}, {in1}, {}},
+      {    TGSI_OPCODE_CASE, {}, {in1}, {}},
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_BRK},
+      {     TGSI_OPCODE_ENDIF},
+      {    TGSI_OPCODE_DEFAULT},
+      {  TGSI_OPCODE_ENDSWITCH},
+      {  TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{8, 10}}));
+}
+
+/* if a break is in the loop, but inside a switch case, so it
+ * referes to that inner loop. The variable has to survive the loop */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterBreakInSwitchInLoop)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_SWITCH, {}, {in1}, {}},
+      {  TGSI_OPCODE_CASE, {}, {in1}, {}},
+      {   TGSI_OPCODE_BGNLOOP },
+      {    TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_BRK},
+      {    TGSI_OPCODE_ENDIF},
+      {    TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {   TGSI_OPCODE_ENDLOOP },
+      {  TGSI_OPCODE_DEFAULT, {}, {}, {}},
+      { TGSI_OPCODE_ENDSWITCH, {}, {}, {}},
+      { TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{2, 10}}));
+}
+
+
+/* if a break is in the loop, all variables written after the
+ * break and used outside the loop must be maintained for the
+ * whole loop that includes the read */
+TEST_F(LifetimeEvaluatorExactTest, NestedLoopWithWriteAfterBreak)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_IF, {}, {in0}, {}},
+      {       TGSI_OPCODE_BRK},
+      {     TGSI_OPCODE_ENDIF},
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {   TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 8}}));
+}
+
+/* if a break  is in the loop, all variables written after the
+ * break  and used outside the loop must be maintained for all
+ * loops up onto the read scope */
+TEST_F(LifetimeEvaluatorExactTest, Nested2LoopWithWriteAfterBreak)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {  TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_BGNLOOP },
+      {       TGSI_OPCODE_IF, {}, {in0}, {}},
+      {         TGSI_OPCODE_BRK},
+      {       TGSI_OPCODE_ENDIF},
+      {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      {  TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{1, 11}}));
+}
+
+/* Temporary used to switch must live through all case statememts */
+TEST_F(LifetimeEvaluatorExactTest, UseSwitchCase)
+{
+   const vector<MockCodeline> code = {
+      {TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {TGSI_OPCODE_SWITCH, {}, {1}, {}},
+      { TGSI_OPCODE_CASE, {}, {1}, {}},
+      { TGSI_OPCODE_CASE, {}, {1}, {}},
+      { TGSI_OPCODE_BRK},
+      { TGSI_OPCODE_DEFAULT},
+      {TGSI_OPCODE_ENDSWITCH},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 3}}));
+}
+
+/* variable written in a switch within a loop must survive the loop */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteInSwitch)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_SWITCH, {}, {in0}, {} },
+      {    TGSI_OPCODE_CASE, {}, {in0}, {} },
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {    TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_DEFAULT },
+      {   TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_ENDSWITCH },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 9}}));
+}
+
+/* value written in one case, and read in other, in loop
+ *  - must survive the loop */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithReadWriteInSwitchDifferentCase)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_SWITCH, {}, {in0}, {}},
+      {    TGSI_OPCODE_CASE, {}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {    TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_DEFAULT },
+      {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      {   TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_ENDSWITCH },
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 9}}));
+}
+
+/* Make sure SWITCH is closed correctly in the scope stack */
+TEST_F(LifetimeEvaluatorExactTest, LoopRWInSwitchCaseLastCaseWithoutBreak)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_SWITCH, {}, {in0}, {}},
+      {    TGSI_OPCODE_CASE, {}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {    TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_DEFAULT },
+      {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      {   TGSI_OPCODE_ENDSWITCH },
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0, 8}}));
+}
+
+
+/* value read/write in same case, stays there */
+TEST_F(LifetimeEvaluatorExactTest, LoopWithReadWriteInSwitchSameCase)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_SWITCH, {}, {in0}, {}},
+      {    TGSI_OPCODE_CASE, {}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      {    TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_DEFAULT },
+      {   TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_ENDSWITCH },
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{3,4}}));
+}
+
+/* value read/write in all cases, should only live from first
+ * write to last read, but currently the whole loop is used. */
+TEST_F(LifetimeEvaluatorAtLeastTest, LoopWithReadWriteInSwitchSameCase)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_SWITCH, {}, {in0}, {}},
+      {    TGSI_OPCODE_CASE, {}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {}, {in0}, {}},
+      {    TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_DEFAULT },
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {   TGSI_OPCODE_BRK },
+      {   TGSI_OPCODE_ENDSWITCH },
+      {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{3,9}}));
+}
+
+
+/* value read/write in differnt loops */
+TEST_F(LifetimeEvaluatorExactTest, LoopsWithDifferntScopes)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{1,5}}));
+}
+
+/* value read/write in differnt loops, conditional */
+TEST_F(LifetimeEvaluatorExactTest, LoopsWithDifferntScopesConditionalWrite)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {  TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {   TGSI_OPCODE_ENDIF},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0,7}}));
+}
+
+/* first read before first write wiredness with nested loops */
+TEST_F(LifetimeEvaluatorExactTest, LoopsWithDifferentScopesCondReadBeforeWrite)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_BGNLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {    TGSI_OPCODE_IF, {}, {in0}, {}},
+      {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
+      {    TGSI_OPCODE_ENDIF},
+      {   TGSI_OPCODE_ENDLOOP },
+      {   TGSI_OPCODE_BGNLOOP },
+      {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      {   TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_ENDLOOP },
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0,9}}));
+}
+
+/* register is only written. This should not happen,
+ * but to handle the case we want the register to life
+ * at least past the write instruction */
+TEST_F(LifetimeEvaluatorExactTest, WriteOnly)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0,1}}));
+}
+
+/* register read in if */
+TEST_F(LifetimeEvaluatorExactTest, SimpleReadForIf)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_ADD, {out0}, {in0, in1}, {}},
+      { TGSI_OPCODE_IF, {}, {1}, {}},
+      { TGSI_OPCODE_ENDIF}
+   };
+   run (code, expectation({{-1,-1},{0,2}}));
+}
+
+/* register read in switch */
+TEST_F(LifetimeEvaluatorExactTest, SimpleReadForSwitchAndCase)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_SWITCH, {}, {1}, {}},
+      { TGSI_OPCODE_CASE, {}, {1}, {}},
+      { TGSI_OPCODE_CASE, {}, {1}, {}},
+      { TGSI_OPCODE_ENDSWITCH},
+   };
+   run (code, expectation({{-1,-1},{0,3}}));
+}
+
+/* Check that a missing END is handled (Unigine-Haven creates such a
+ * shader) */
+TEST_F(LifetimeEvaluatorExactTest, DistinceScopesAndNoEndProgramId)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_IF, {}, {1}, {}},
+      { TGSI_OPCODE_MOV, {2}, {1}, {}},
+      { TGSI_OPCODE_ENDIF},
+      { TGSI_OPCODE_IF, {}, {1}, {}},
+      { TGSI_OPCODE_MOV, {out0}, {2}, {}},
+      { TGSI_OPCODE_ENDIF},
+
+   };
+   run (code, expectation({{-1,-1},{0,4}, {2,5}}));
+}
+
+/* Dead code elimination should catch and remove the case
+ * when a variable is written after its last read, but
+ * we want the code to be aware of this case.
+ * The life time of this uselessly written variable is set
+ * to the instruction after the write, because
+ * otherwise it could be re-used too early.
+*/
+TEST_F(LifetimeEvaluatorExactTest, WritePastLastRead)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_MOV, {2}, {1}, {}},
+      { TGSI_OPCODE_MOV, {1}, {2}, {}},
+      { TGSI_OPCODE_END},
+
+   };
+   run (code, expectation({{-1,-1},{0,3}, {1,2}}));
+}
+
+/*
+ * Somehow a duplicate of above tests specifically using the
+ * problematic corner case n question. DFRACEXP has two
+ * destinations, and if one value is thrown away, we must ensure
+ * that the two output registers don't merge.
+ * In this test case the last access for 2 and 3 is in line 4,
+ * but only 3 can be merged with 4 because it is read, 2 on the
+ * other hand is written to, and merging it with 4 would result in
+ * undefined behaviour.
+*/
+TEST_F(LifetimeEvaluatorExactTest, WritePastLastRead2)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_MOV, {1}, {in0}, {}},
+      { TGSI_OPCODE_MOV, {2}, {in0}, {}},
+      { TGSI_OPCODE_ADD, {3}, {1,2}, {}},
+      { TGSI_OPCODE_DFRACEXP , {2,4}, {3}, {}},
+      { TGSI_OPCODE_MOV, {out1}, {4}, {}},
+      { TGSI_OPCODE_END},
+
+   };
+   run (code, expectation({{-1,-1},{0,2}, {1,4}, {2,3}, {3,4}}));
+}
+
+
+TEST_F(LifetimeEvaluatorExactTest, OnlyWriteOne)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_DFRACEXP , {1, 2}, {in0}, {}},
+      { TGSI_OPCODE_ADD , {3}, {2, in0}, {}},
+      { TGSI_OPCODE_MOV, {out1}, {3}, {}},
+      { TGSI_OPCODE_END},
+
+   };
+   run (code, expectation({{-1,-1},{0,1}, {0,1}, {1,2}}));
+}
+
+
+/* Check that two destination registers are actually used */
+TEST_F(LifetimeEvaluatorExactTest, TwoDestRegisters)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_DFRACEXP , {1,2}, {in0}, {}},
+      { TGSI_OPCODE_ADD, {out0}, {1,2}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0,1}, {0,1}}));
+}
+
+/* Check that two destination registers and three source registers
+ * are used */
+TEST_F(LifetimeEvaluatorExactTest, ThreeSourceRegisters)
+{
+   const vector<MockCodeline> code = {
+      { TGSI_OPCODE_DFRACEXP , {1,2}, {in0}, {}},
+      { TGSI_OPCODE_ADD , {3}, {in0, in1}, {}},
+      { TGSI_OPCODE_MAD, {out0}, {1,2, 3}, {}},
+      { TGSI_OPCODE_END}
+   };
+   run (code, expectation({{-1,-1},{0,2}, {0,2}, {1,2}}));
+}
+
+
+class RegisterRemapping : public testing::Test {
+protected:
+   void run(const vector<pair<int, int>>& lt, const vector<int>& expect);
+};
+
+void RegisterRemapping::run(const vector<pair<int, int>>& lt,
+                            const vector<int>& expect)
+{
+   rename_reg_pair proto{false, 0};
+   vector<rename_reg_pair> result(lt.size(), proto);
+
+   evaluate_remapping(lt, &result[0]);
+
+   vector<int> remap(lt.size());
+   for (unsigned i = 0; i < lt.size(); ++i) {
+      remap[i] = result[i].valid ? result[i].new_reg : i;
+   }
+
+   std::transform(remap.begin(), remap.end(), result.begin(), remap.begin(),
+                  [](int x, const rename_reg_pair& rn) {
+                      return rn.valid ? rn.new_reg : x;
+                  });
+
+   for(unsigned  i = 1; i < remap.size(); ++i)
+      EXPECT_EQ(remap[i], expect[i]);
+}
+
+TEST_F(RegisterRemapping, RegisterRemapping1)
+{
+   vector<pair<int, int>> lt({{-1,-1},
+                             {0, 1},
+                             {0, 2},
+                             {1, 2},
+                             {2, 10},
+                             {3, 5},
+                             {5, 10}
+                            });
+
+   vector<int> expect({0, 1, 2, 1, 1, 2, 2});
+   run(lt, expect);
+}
+
+
+TEST_F(RegisterRemapping, RegisterRemapping2)
+{
+   vector<pair<int, int>> lt({{-1,-1},
+                             {0, 1},
+                             {0, 2},
+                             {3, 3},
+                             {4, 4},
+                            });
+   vector<int> expect({0, 1, 2, 1, 1});
+   run(lt, expect);
+}
+
+
+
+MockShader::~MockShader()
+{
+   free();
+   ralloc_free(mem_ctx);
+}
+
+int MockShader::get_num_temps()
+{
+   return num_temps;
+}
+
+
+exec_list* MockShader::get_program()
+{
+   return program;
+}
+
+MockShader::MockShader(const vector<MockCodeline>& source):
+   num_temps(0)
+{
+   mem_ctx = ralloc_context(NULL);
+
+   program = new(mem_ctx) exec_list();
+
+   for (MockCodeline i: source) {
+      glsl_to_tgsi_instruction *next_instr = new(mem_ctx) glsl_to_tgsi_instruction();
+      next_instr->op = i.op;
+      next_instr->info = tgsi_get_opcode_info(i.op);
+
+      assert(i.src.size() < 4);
+      assert(i.dst.size() < 3);
+      assert(i.tex_offsets.size() < 3);
+
+      for (unsigned  k = 0; k < i.src.size(); ++k) {
+         next_instr->src[k] = create_src_register(i.src[k]);
+      }
+      for (unsigned k = 0; k < i.dst.size(); ++k) {
+         next_instr->dst[k] = create_dst_register(i.dst[k]);
+      }
+
+      // set texture registers
+      next_instr->tex_offset_num_offset = i.tex_offsets.size();
+      if (i.tex_offsets.size() > 0)
+         next_instr->tex_offsets = new st_src_reg[i.tex_offsets.size()];
+      else
+         next_instr->tex_offsets = 0;
+      for (unsigned k = 0; k < i.tex_offsets.size(); ++k) {
+         next_instr->tex_offsets[k] = create_src_register(i.tex_offsets[k]);
+      }
+
+      program->push_tail(next_instr);
+   }
+   ++num_temps;
+}
+
+void MockShader::free()
+{
+   // the list is not fully initialized, so
+   // tearing it down also must be done manually.
+   exec_node *p;
+   while ((p = program->pop_head())) {
+      glsl_to_tgsi_instruction * instr = static_cast<glsl_to_tgsi_instruction *>(p);
+      if (instr->tex_offset_num_offset > 0)
+         delete[] instr->tex_offsets;
+      delete p;
+   }
+   program = 0;
+   num_temps = 0;
+}
+
+st_src_reg MockShader::create_src_register(int src_idx)
+{
+   gl_register_file file;
+   int idx = 0;
+   if (src_idx > 0) {
+      file = PROGRAM_TEMPORARY;
+      idx = src_idx;
+      if (num_temps < idx)
+         num_temps = idx;
+   } else {
+      file = PROGRAM_INPUT;
+      idx = -src_idx;
+   }
+   return st_src_reg(file, idx, GLSL_TYPE_INT);
+
+}
+
+st_dst_reg MockShader::create_dst_register(int dst_idx)
+{
+   gl_register_file file;
+   int idx = 0;
+   if (dst_idx > 0) {
+      file = PROGRAM_TEMPORARY;
+      idx = dst_idx;
+      if (num_temps < idx)
+         num_temps = idx;
+   } else {
+      file = PROGRAM_OUTPUT;
+      idx = - dst_idx;
+   }
+   return st_dst_reg(file, 0xF, GLSL_TYPE_INT, idx);
+}
+
+void LifetimeEvaluatorExactTest::run(const vector<MockCodeline>& code, const expectation& e)
+{
+   MockShader shader(code);
+
+   auto lifetimes = estimate_temporary_lifetimes(shader.get_program(), shader.get_num_temps());
+
+   // lifetimes[0] not used, but created for simpler processing
+   ASSERT_EQ(lifetimes.size(), e.size());
+
+   for (unsigned i = 1; i < lifetimes.size(); ++i) {
+      EXPECT_EQ(lifetimes[i].first, e[i][0]);
+      EXPECT_EQ(lifetimes[i].second, e[i][1]);
+   }
+}
+
+void LifetimeEvaluatorAtLeastTest::run(const vector<MockCodeline>& code, const expectation& e)
+{
+   MockShader shader(code);
+
+   auto lifetimes = estimate_temporary_lifetimes(shader.get_program(), shader.get_num_temps());
+
+   // lifetimes[0] not used, but created for simpler processing
+   ASSERT_EQ(lifetimes.size(), e.size());
+
+   for (unsigned i = 1; i < lifetimes.size(); ++i) {
+      EXPECT_LE(lifetimes[i].first, e[i][0]);
+      EXPECT_GE(lifetimes[i].second, e[i][1]);
+   }
+}
-- 
2.13.0



More information about the mesa-dev mailing list