Google Git
Sign in
android / platform / external / mesa3d / ef961309bfa2c968710994b1bff87e6a13def150 / . / src / mesa / state_tracker / st_glsl_to_tgsi_temprename.cpp
blob: 210c25e8ba8435966b515e229b868262a0794c3c [file] [log] [blame]
/*
* 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 "st_glsl_to_tgsi_array_merge.h"
#include "tgsi/tgsi_info.h"
#include "tgsi/tgsi_strings.h"
#include "program/prog_instruction.h"
#include "util/bitscan.h"
#include <limits>
#include <cstdlib>
/* std::sort is significantly faster than qsort */
#define USE_STL_SORT
#ifdef USE_STL_SORT
#include <algorithm>
#endif
#ifndef NDEBUG
#include <iostream>
#include <iomanip>
#include "program/prog_print.h"
#include "util/debug.h"
using std::cerr;
using std::setw;
using std::ostream;
#endif
/* If <windows.h> is included this is defined and clashes with
* std::numeric_limits<>::max()
*/
#ifdef max
#undef max
#endif
using std::numeric_limits;
/* Without c++11 define the nullptr for forward-compatibility
* and better readibility */
#if __cplusplus < 201103L
#define nullptr 0
#endif
#ifndef NDEBUG
/* Prepare to make it possible to specify log file */
static std::ostream& debug_log = cerr;
/* Helper function to check whether we want to seen debugging output */
static inline bool is_debug_enabled ()
{
static int debug_enabled = -1;
if (debug_enabled < 0)
debug_enabled = env_var_as_boolean("GLSL_TO_TGSI_RENAME_DEBUG", false);
return debug_enabled > 0;
}
#define RENAME_DEBUG(X) if (is_debug_enabled()) do { X; } while (false);
#else
#define RENAME_DEBUG(X)
#endif
namespace {
enum prog_scope_type {
outer_scope, /* Outer program scope */
loop_body, /* Inside a loop */
if_branch, /* Inside if branch */
else_branch, /* Inside else branch */
switch_body, /* Inside switch statmenet */
switch_case_branch, /* Inside switch case statmenet */
switch_default_branch, /* Inside switch default statmenet */
undefined_scope
};
class prog_scope {
public:
prog_scope(prog_scope *parent, prog_scope_type type, int id,
int depth, int begin);
prog_scope_type type() const;
prog_scope *parent() const;
int nesting_depth() const;
int id() const;
int end() const;
int begin() const;
int loop_break_line() const;
const prog_scope *in_else_scope() const;
const prog_scope *in_ifelse_scope() const;
const prog_scope *in_parent_ifelse_scope() const;
const prog_scope *innermost_loop() const;
const prog_scope *outermost_loop() const;
const prog_scope *enclosing_conditional() const;
bool is_loop() const;
bool is_in_loop() const;
bool is_switchcase_scope_in_loop() const;
bool is_conditional() const;
bool is_child_of(const prog_scope *scope) const;
bool is_child_of_ifelse_id_sibling(const prog_scope *scope) const;
bool break_is_for_switchcase() const;
bool contains_range_of(const prog_scope& other) const;
void set_end(int end);
void set_loop_break_line(int line);
private:
prog_scope_type scope_type;
int scope_id;
int scope_nesting_depth;
int scope_begin;
int scope_end;
int break_loop_line;
prog_scope *parent_scope;
};
/* Some storage class to encapsulate the prog_scope (de-)allocations */
class prog_scope_storage {
public:
prog_scope_storage(void *mem_ctx, int n);
~prog_scope_storage();
prog_scope * create(prog_scope *p, prog_scope_type type, int id,
int lvl, int s_begin);
private:
void *mem_ctx;
int current_slot;
prog_scope *storage;
};
/* Class to track the access to a component of a temporary register. */
class temp_comp_access {
public:
temp_comp_access();
void record_read(int line, prog_scope *scope);
void record_write(int line, prog_scope *scope);
register_live_range get_required_live_range();
private:
void propagate_live_range_to_dominant_write_scope();
bool conditional_ifelse_write_in_loop() const;
void record_ifelse_write(const prog_scope& scope);
void record_if_write(const prog_scope& scope);
void record_else_write(const prog_scope& scope);
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;
/* This member variable tracks the current resolution of conditional writing
* to this temporary in IF/ELSE clauses.
*
* The initial value "conditionality_untouched" indicates that this
* temporary has not yet been written to within an if clause.
*
* A positive (other than "conditionality_untouched") number refers to the
* last loop id for which the write was resolved as unconditional. With each
* new loop this value will be overwitten by "conditionality_unresolved"
* on entering the first IF clause writing this temporary.
*
* The value "conditionality_unresolved" indicates that no resolution has
* been achieved so far. If the variable is set to this value at the end of
* the processing of the whole shader it also indicates a conditional write.
*
* The value "write_is_conditional" marks that the variable is written
* conditionally (i.e. not in all relevant IF/ELSE code path pairs) in at
* least one loop.
*/
int conditionality_in_loop_id;
/* Helper constants to make the tracking code more readable. */
static const int write_is_conditional = -1;
static const int conditionality_unresolved = 0;
static const int conditionality_untouched;
static const int write_is_unconditional;
/* A bit field tracking the nexting levels of if-else clauses where the
* temporary has (so far) been written to in the if branch, but not in the
* else branch.
*/
unsigned int if_scope_write_flags;
int next_ifelse_nesting_depth;
static const int supported_ifelse_nesting_depth = 32;
/* Tracks the last if scope in which the temporary was written to
* without a write in the correspondig else branch. Is also used
* to track read-before-write in the according scope.
*/
const prog_scope *current_unpaired_if_write_scope;
/* Flag to resolve read-before-write in the else scope. */
bool was_written_in_current_else_scope;
};
const int
temp_comp_access::conditionality_untouched = numeric_limits<int>::max();
const int
temp_comp_access::write_is_unconditional = numeric_limits<int>::max() - 1;
/* Class to track the access to all components of a temporary register. */
class temp_access {
public:
temp_access();
void record_read(int line, prog_scope *scope, int swizzle);
void record_write(int line, prog_scope *scope, int writemask);
register_live_range get_required_live_range();
private:
void update_access_mask(int mask);
temp_comp_access comp[4];
int access_mask;
bool needs_component_tracking;
};
/* Class to track array access.
* Compared to the temporary tracking this is very simplified, mainly because
* with the likely indirect access one can not really establish access
* patterns for individual elements. Instead the life range evaluation is
* always for the whole array, handles only loops and the fact whether a
* value was accessed conditionally in a loop.
*/
class array_access {
public:
array_access();
void record_access(int line, prog_scope *scope, int swizzle);
void get_required_live_range(array_live_range &lr);
private:
int first_access;
int last_access;
prog_scope *first_access_scope;
prog_scope *last_access_scope;
unsigned accumulated_swizzle:4;
int conditional_access_in_loop:1;
};
prog_scope_storage::prog_scope_storage(void *mc, int n):
mem_ctx(mc),
current_slot(0)
{
storage = ralloc_array(mem_ctx, prog_scope, n);
}
prog_scope_storage::~prog_scope_storage()
{
ralloc_free(storage);
}
prog_scope*
prog_scope_storage::create(prog_scope *p, prog_scope_type type, int id,
int lvl, int s_begin)
{
storage[current_slot] = prog_scope(p, type, id, lvl, s_begin);
return &storage[current_slot++];
}
prog_scope::prog_scope(prog_scope *parent, prog_scope_type type, int id,
int depth, int scope_begin):
scope_type(type),
scope_id(id),
scope_nesting_depth(depth),
scope_begin(scope_begin),
scope_end(-1),
break_loop_line(numeric_limits<int>::max()),
parent_scope(parent)
{
}
prog_scope_type prog_scope::type() const
{
return scope_type;
}
prog_scope *prog_scope::parent() const
{
return parent_scope;
}
int prog_scope::nesting_depth() const
{
return scope_nesting_depth;
}
bool prog_scope::is_loop() const
{
return (scope_type == loop_body);
}
bool prog_scope::is_in_loop() const
{
if (scope_type == loop_body)
return true;
if (parent_scope)
return parent_scope->is_in_loop();
return false;
}
const prog_scope *prog_scope::innermost_loop() const
{
if (scope_type == loop_body)
return this;
if (parent_scope)
return parent_scope->innermost_loop();
return nullptr;
}
const prog_scope *prog_scope::outermost_loop() const
{
const prog_scope *loop = nullptr;
const prog_scope *p = this;
do {
if (p->type() == loop_body)
loop = p;
p = p->parent();
} while (p);
return loop;
}
bool prog_scope::is_child_of_ifelse_id_sibling(const prog_scope *scope) const
{
const prog_scope *my_parent = in_parent_ifelse_scope();
while (my_parent) {
/* is a direct child? */
if (my_parent == scope)
return false;
/* is a child of the conditions sibling? */
if (my_parent->id() == scope->id())
return true;
my_parent = my_parent->in_parent_ifelse_scope();
}
return false;
}
bool prog_scope::is_child_of(const prog_scope *scope) const
{
const prog_scope *my_parent = parent();
while (my_parent) {
if (my_parent == scope)
return true;
my_parent = my_parent->parent();
}
return false;
}
const prog_scope *prog_scope::enclosing_conditional() const
{
if (is_conditional())
return this;
if (parent_scope)
return parent_scope->enclosing_conditional();
return nullptr;
}
bool prog_scope::contains_range_of(const prog_scope& other) const
{
return (begin() <= other.begin()) && (end() >= other.end());
}
bool prog_scope::is_conditional() const
{
return scope_type == if_branch ||
scope_type == else_branch ||
scope_type == switch_case_branch ||
scope_type == switch_default_branch;
}
const prog_scope *prog_scope::in_else_scope() const
{
if (scope_type == else_branch)
return this;
if (parent_scope)
return parent_scope->in_else_scope();
return nullptr;
}
const prog_scope *prog_scope::in_parent_ifelse_scope() const
{
if (parent_scope)
return parent_scope->in_ifelse_scope();
else
return nullptr;
}
const prog_scope *prog_scope::in_ifelse_scope() const
{
if (scope_type == if_branch ||
scope_type == else_branch)
return this;
if (parent_scope)
return parent_scope->in_ifelse_scope();
return nullptr;
}
bool prog_scope::is_switchcase_scope_in_loop() const
{
return (scope_type == switch_case_branch ||
scope_type == switch_default_branch) &&
is_in_loop();
}
bool prog_scope::break_is_for_switchcase() const
{
if (scope_type == loop_body)
return false;
if (scope_type == switch_case_branch ||
scope_type == switch_default_branch ||
scope_type == switch_body)
return true;
if (parent_scope)
return parent_scope->break_is_for_switchcase();
return false;
}
int prog_scope::id() const
{
return scope_id;
}
int prog_scope::begin() const
{
return scope_begin;
}
int prog_scope::end() const
{
return scope_end;
}
void prog_scope::set_end(int end)
{
if (scope_end == -1)
scope_end = end;
}
void prog_scope::set_loop_break_line(int line)
{
if (scope_type == loop_body) {
break_loop_line = MIN2(break_loop_line, line);
} else {
if (parent_scope)
parent()->set_loop_break_line(line);
}
}
int prog_scope::loop_break_line() const
{
return break_loop_line;
}
temp_access::temp_access():
access_mask(0),
needs_component_tracking(false)
{
}
void temp_access::update_access_mask(int mask)
{
if (access_mask && access_mask != mask)
needs_component_tracking = true;
access_mask |= mask;
}
void temp_access::record_write(int line, prog_scope *scope, int writemask)
{
update_access_mask(writemask);
if (writemask & WRITEMASK_X)
comp[0].record_write(line, scope);
if (writemask & WRITEMASK_Y)
comp[1].record_write(line, scope);
if (writemask & WRITEMASK_Z)
comp[2].record_write(line, scope);
if (writemask & WRITEMASK_W)
comp[3].record_write(line, scope);
}
void temp_access::record_read(int line, prog_scope *scope, int readmask)
{
update_access_mask(readmask);
if (readmask & WRITEMASK_X)
comp[0].record_read(line, scope);
if (readmask & WRITEMASK_Y)
comp[1].record_read(line, scope);
if (readmask & WRITEMASK_Z)
comp[2].record_read(line, scope);
if (readmask & WRITEMASK_W)
comp[3].record_read(line, scope);
}
array_access::array_access():
first_access(-1),
last_access(-1),
first_access_scope(nullptr),
last_access_scope(nullptr),
accumulated_swizzle(0),
conditional_access_in_loop(false)
{
}
void array_access::record_access(int line, prog_scope *scope, int swizzle)
{
if (!first_access_scope) {
first_access = line;
first_access_scope = scope;
}
last_access_scope = scope;
last_access = line;
accumulated_swizzle |= swizzle;
if (scope->in_ifelse_scope() && scope->innermost_loop())
conditional_access_in_loop = true;
}
void array_access::get_required_live_range(array_live_range& lr)
{
RENAME_DEBUG(debug_log << "first_access_scope=" << first_access_scope << "\n");
RENAME_DEBUG(debug_log << "last_access_scope=" << last_access_scope << "\n");
if (first_access_scope == last_access_scope) {
lr.set_live_range(first_access, last_access);
lr.set_access_mask(accumulated_swizzle);
return;
}
const prog_scope *shared_scope = first_access_scope;
const prog_scope *other_scope = last_access_scope;
assert(shared_scope);
RENAME_DEBUG(debug_log << "shared_scope=" << shared_scope << "\n");
if (conditional_access_in_loop) {
const prog_scope *help = shared_scope->outermost_loop();
if (help) {
shared_scope = help;
} else {
help = other_scope->outermost_loop();
if (help)
other_scope = help;
}
if (first_access > shared_scope->begin())
first_access = shared_scope->begin();
if (last_access < shared_scope->end())
last_access = shared_scope->end();
}
/* See if any of the two is the parent of the other. */
if (other_scope->contains_range_of(*shared_scope)) {
shared_scope = other_scope;
} else while (!shared_scope->contains_range_of(*other_scope)) {
assert(shared_scope->parent());
if (shared_scope->type() == loop_body) {
if (last_access < shared_scope->end())
last_access = shared_scope->end();
}
shared_scope = shared_scope->parent();
}
while (shared_scope != other_scope) {
if (other_scope->type() == loop_body) {
if (last_access < other_scope->end())
last_access = other_scope->end();
}
other_scope = other_scope->parent();
}
lr.set_live_range(first_access, last_access);
lr.set_access_mask(accumulated_swizzle);
}
inline static register_live_range make_live_range(int b, int e)
{
register_live_range lt;
lt.begin = b;
lt.end = e;
return lt;
}
register_live_range temp_access::get_required_live_range()
{
register_live_range result = make_live_range(-1, -1);
unsigned mask = access_mask;
while (mask) {
unsigned chan = u_bit_scan(&mask);
register_live_range lt = comp[chan].get_required_live_range();
if (lt.begin >= 0) {
if ((result.begin < 0) || (result.begin > lt.begin))
result.begin = lt.begin;
}
if (lt.end > result.end)
result.end = lt.end;
if (!needs_component_tracking)
break;
}
return result;
}
temp_comp_access::temp_comp_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()),
conditionality_in_loop_id(conditionality_untouched),
if_scope_write_flags(0),
next_ifelse_nesting_depth(0),
current_unpaired_if_write_scope(nullptr),
was_written_in_current_else_scope(false)
{
}
void temp_comp_access::record_read(int line, prog_scope *scope)
{
last_read_scope = scope;
last_read = line;
if (first_read > line) {
first_read = line;
first_read_scope = scope;
}
/* If the conditionality of the first write is already resolved then
* no further checks are required.
*/
if (conditionality_in_loop_id == write_is_unconditional ||
conditionality_in_loop_id == write_is_conditional)
return;
/* Check whether we are in a condition within a loop */
const prog_scope *ifelse_scope = scope->in_ifelse_scope();
const prog_scope *enclosing_loop;
if (ifelse_scope && (enclosing_loop = ifelse_scope->innermost_loop())) {
/* If we have either not yet written to this register nor writes are
* resolved as unconditional in the enclosing loop then check whether
* we read before write in an IF/ELSE branch.
*/
if ((conditionality_in_loop_id != write_is_conditional) &&
(conditionality_in_loop_id != enclosing_loop->id())) {
if (current_unpaired_if_write_scope) {
/* Has been written in this or a parent scope? - this makes the temporary
* unconditionally set at this point.
*/
if (scope->is_child_of(current_unpaired_if_write_scope))
return;
/* Has been written in the same scope before it was read? */
if (ifelse_scope->type() == if_branch) {
if (current_unpaired_if_write_scope->id() == scope->id())
return;
} else {
if (was_written_in_current_else_scope)
return;
}
}
/* The temporary was read (conditionally) before it is written, hence
* it should survive a loop. This can be signaled like if it were
* conditionally written.
*/
conditionality_in_loop_id = write_is_conditional;
}
}
}
void temp_comp_access::record_write(int line, prog_scope *scope)
{
last_write = line;
if (first_write < 0) {
first_write = line;
first_write_scope = scope;
/* If the first write we encounter is not in a conditional branch, or
* the conditional write is not within a loop, then this is to be
* considered an unconditional dominant write.
*/
const prog_scope *conditional = scope->enclosing_conditional();
if (!conditional || !conditional->innermost_loop()) {
conditionality_in_loop_id = write_is_unconditional;
}
}
/* The conditionality of the first write is already resolved. */
if (conditionality_in_loop_id == write_is_unconditional ||
conditionality_in_loop_id == write_is_conditional)
return;
/* If the nesting depth is larger than the supported level,
* then we assume conditional writes.
*/
if (next_ifelse_nesting_depth >= supported_ifelse_nesting_depth) {
conditionality_in_loop_id = write_is_conditional;
return;
}
/* If we are in an IF/ELSE scope within a loop and the loop has not
* been resolved already, then record this write.
*/
const prog_scope *ifelse_scope = scope->in_ifelse_scope();
if (ifelse_scope && ifelse_scope->innermost_loop() &&
ifelse_scope->innermost_loop()->id() != conditionality_in_loop_id)
record_ifelse_write(*ifelse_scope);
}
void temp_comp_access::record_ifelse_write(const prog_scope& scope)
{
if (scope.type() == if_branch) {
/* The first write in an IF branch within a loop implies unresolved
* conditionality (if it was untouched or unconditional before).
*/
conditionality_in_loop_id = conditionality_unresolved;
was_written_in_current_else_scope = false;
record_if_write(scope);
} else {
was_written_in_current_else_scope = true;
record_else_write(scope);
}
}
void temp_comp_access::record_if_write(const prog_scope& scope)
{
/* Don't record write if this IF scope if it ...
* - is not the first write in this IF scope,
* - has already been written in a parent IF scope.
* In both cases this write is a secondary write that doesn't contribute
* to resolve conditionality.
*
* Record the write if it
* - is the first one (obviously),
* - happens in an IF branch that is a child of the ELSE branch of the
* last active IF/ELSE pair. In this case recording this write is used to
* established whether the write is (un-)conditional in the scope enclosing
* this outer IF/ELSE pair.
*/
if (!current_unpaired_if_write_scope ||
(current_unpaired_if_write_scope->id() != scope.id() &&
scope.is_child_of_ifelse_id_sibling(current_unpaired_if_write_scope))) {
if_scope_write_flags |= 1 << next_ifelse_nesting_depth;
current_unpaired_if_write_scope = &scope;
next_ifelse_nesting_depth++;
}
}
void temp_comp_access::record_else_write(const prog_scope& scope)
{
int mask = 1 << (next_ifelse_nesting_depth - 1);
/* If the temporary was written in an IF branch on the same scope level
* and this branch is the sibling of this ELSE branch, then we have a
* pair of writes that makes write access to this temporary unconditional
* in the enclosing scope.
*/
if ((if_scope_write_flags & mask) &&
(scope.id() == current_unpaired_if_write_scope->id())) {
--next_ifelse_nesting_depth;
if_scope_write_flags &= ~mask;
/* The following code deals with propagating unconditionality from
* inner levels of nested IF/ELSE to the outer levels like in
*
* 1: var t;
* 2: if (a) { <- start scope A
* 3: if (b)
* 4: t = ...
* 5: else
* 6: t = ...
* 7: } else { <- start scope B
* 8: if (c)
* 9: t = ...
* A: else <- start scope C
* B: t = ...
* C: }
*
*/
const prog_scope *parent_ifelse = scope.parent()->in_ifelse_scope();
if (1 << (next_ifelse_nesting_depth - 1) & if_scope_write_flags) {
/* We are at the end of scope C and already recorded a write
* within an IF scope (A), the sibling of the parent ELSE scope B,
* and it is not yet resolved. Mark that as the last relevant
* IF scope. Below the write will be resolved for the A/B
* scope pair.
*/
current_unpaired_if_write_scope = parent_ifelse;
} else {
current_unpaired_if_write_scope = nullptr;
}
/* Promote the first write scope to the enclosing scope because
* the current IF/ELSE pair is now irrelevant for the analysis.
* This is also required to evaluate the minimum life time for t in
* {
* var t;
* if (a)
* t = ...
* else
* t = ...
* x = t;
* ...
* }
*/
first_write_scope = scope.parent();
/* If some parent is IF/ELSE and in a loop then propagate the
* write to that scope. Otherwise the write is unconditional
* because it happens in both corresponding IF/ELSE branches
* in this loop, and hence, record the loop id to signal the
* resolution.
*/
if (parent_ifelse && parent_ifelse->is_in_loop()) {
record_ifelse_write(*parent_ifelse);
} else {
conditionality_in_loop_id = scope.innermost_loop()->id();
}
} else {
/* The temporary was not written in the IF branch corresponding
* to this ELSE branch, hence the write is conditional.
*/
conditionality_in_loop_id = write_is_conditional;
}
}
bool temp_comp_access::conditional_ifelse_write_in_loop() const
{
return conditionality_in_loop_id <= conditionality_unresolved;
}
void temp_comp_access::propagate_live_range_to_dominant_write_scope()
{
first_write = first_write_scope->begin();
int lr = first_write_scope->end();
if (last_read < lr)
last_read = lr;
}
register_live_range temp_comp_access::get_required_live_range()
{
bool keep_for_full_loop = false;
/* This register component is not used at all, or only read,
* mark it as unused and ignore it when renaming.
* glsl_to_tgsi_visitor::renumber_registers will take care of
* eliminating registers that are not written to.
*/
if (last_write < 0)
return make_live_range(-1, -1);
assert(first_write_scope);
/* Only written to, just make sure the register component is not
* reused in the range it is used to write to
*/
if (!last_read_scope)
return make_live_range(first_write, last_write + 1);
const prog_scope *enclosing_scope_first_read = first_read_scope;
const prog_scope *enclosing_scope_first_write = first_write_scope;
/* We read before writing in a loop
* hence the value must survive the loops
*/
if ((first_read <= first_write) &&
first_read_scope->is_in_loop()) {
keep_for_full_loop = true;
enclosing_scope_first_read = first_read_scope->outermost_loop();
}
/* A conditional write within a (nested) loop must survive the outermost
* loop if the last read was not within the same scope.
*/
const prog_scope *conditional = enclosing_scope_first_write->enclosing_conditional();
if (conditional && !conditional->contains_range_of(*last_read_scope) &&
(conditional->is_switchcase_scope_in_loop() ||
conditional_ifelse_write_in_loop())) {
keep_for_full_loop = true;
enclosing_scope_first_write = conditional->outermost_loop();
}
/* Evaluate the scope that is shared by all: required first write scope,
* required first read before write scope, and last read scope.
*/
const prog_scope *enclosing_scope = enclosing_scope_first_read;
if (enclosing_scope_first_write->contains_range_of(*enclosing_scope))
enclosing_scope = enclosing_scope_first_write;
if (last_read_scope->contains_range_of(*enclosing_scope))
enclosing_scope = last_read_scope;
while (!enclosing_scope->contains_range_of(*enclosing_scope_first_write) ||
!enclosing_scope->contains_range_of(*last_read_scope)) {
enclosing_scope = enclosing_scope->parent();
assert(enclosing_scope);
}
/* Propagate the last read scope to the target scope */
while (enclosing_scope->nesting_depth() < last_read_scope->nesting_depth()) {
/* If the read is in a loop and we have to move up the scope we need to
* extend the live range to the end of this current loop because at this
* point we don't know whether the component was written before
* un-conditionally in the same loop.
*/
if (last_read_scope->is_loop())
last_read = last_read_scope->end();
last_read_scope = last_read_scope->parent();
}
/* If the variable has to be kept for the whole loop, and we
* are currently in a loop, then propagate the live range.
*/
if (keep_for_full_loop && first_write_scope->is_loop())
propagate_live_range_to_dominant_write_scope();
/* Propagate the first_dominant_write scope to the target scope */
while (enclosing_scope->nesting_depth() < first_write_scope->nesting_depth()) {
/* Propagate live_range if there was a break in a loop and the write was
* after the break inside that loop. Note, that this is only needed if
* we move up in the scopes.
*/
if (first_write_scope->loop_break_line() < first_write) {
keep_for_full_loop = true;
propagate_live_range_to_dominant_write_scope();
}
first_write_scope = first_write_scope->parent();
/* Propagte live_range if we are now in a loop */
if (keep_for_full_loop && first_write_scope->is_loop())
propagate_live_range_to_dominant_write_scope();
}
/* The last write past the last read is dead code, but we have to
* ensure that the component is not reused too early, hence extend the
* live_range past the last write.
*/
if (last_write >= last_read)
last_read = last_write + 1;
/* Here we are at the same scope, all is resolved */
return make_live_range(first_write, last_read);
}
/* Helper class for sorting and searching the registers based
* on live ranges. */
class register_merge_record {
public:
int begin;
int end;
int reg;
bool erase;
bool operator < (const register_merge_record& rhs) const {
return begin < rhs.begin;
}
};
class access_recorder {
public:
access_recorder(int _ntemps, int _narrays);
~access_recorder();
void record_read(const st_src_reg& src, int line, prog_scope *scope);
void record_write(const st_dst_reg& src, int line, prog_scope *scope,
bool no_reswizzle);
void get_required_live_ranges(register_live_range *register_live_ranges,
array_live_range *array_live_ranges);
private:
int ntemps;
int narrays;
temp_access *temp_acc;
array_access *array_acc;
};
access_recorder::access_recorder(int _ntemps, int _narrays):
ntemps(_ntemps),
narrays(_narrays)
{
temp_acc = new temp_access[ntemps];
array_acc = new array_access[narrays];
}
access_recorder::~access_recorder()
{
delete[] array_acc;
delete[] temp_acc;
}
void access_recorder::record_read(const st_src_reg& src, int line,
prog_scope *scope)
{
int readmask = 0;
for (int idx = 0; idx < 4; ++idx) {
int swz = GET_SWZ(src.swizzle, idx);
readmask |= (1 << swz) & 0xF;
}
if (src.file == PROGRAM_TEMPORARY)
temp_acc[src.index].record_read(line, scope, readmask);
if (src.file == PROGRAM_ARRAY) {
assert(src.array_id <= narrays);
array_acc[src.array_id - 1].record_access(line, scope, readmask);
}
if (src.reladdr)
record_read(*src.reladdr, line, scope);
if (src.reladdr2)
record_read(*src.reladdr2, line, scope);
}
void access_recorder::record_write(const st_dst_reg& dst, int line,
prog_scope *scope, bool can_reswizzle)
{
if (dst.file == PROGRAM_TEMPORARY)
temp_acc[dst.index].record_write(line, scope, dst.writemask);
if (dst.file == PROGRAM_ARRAY) {
assert(dst.array_id <= narrays);
/* If the array is written as dst of a multi-dst operation, we must not
* reswizzle the access, because we would have to reswizzle also the
* other dst. For now just fill the mask to make interleaving impossible.
*/
array_acc[dst.array_id - 1].record_access(line, scope,
can_reswizzle ? dst.writemask: 0xF);
}
if (dst.reladdr)
record_read(*dst.reladdr, line, scope);
if (dst.reladdr2)
record_read(*dst.reladdr2, line, scope);
}
void access_recorder::get_required_live_ranges(struct register_live_range *register_live_ranges,
class array_live_range *array_live_ranges)
{
RENAME_DEBUG(debug_log << "== register live ranges ==========\n");
for(int i = 0; i < ntemps; ++i) {
RENAME_DEBUG(debug_log << setw(4) << i);
register_live_ranges[i] = temp_acc[i].get_required_live_range();
RENAME_DEBUG(debug_log << ": [" << register_live_ranges[i].begin << ", "
<< register_live_ranges[i].end << "]\n");
}
RENAME_DEBUG(debug_log << "==================================\n\n");
RENAME_DEBUG(debug_log << "== array live ranges ==========\n");
for(int i = 0; i < narrays; ++i) {
RENAME_DEBUG(debug_log<< setw(4) << i);
array_acc[i].get_required_live_range(array_live_ranges[i]);
RENAME_DEBUG(debug_log << ": [" <<array_live_ranges[i].begin() << ", "
<< array_live_ranges[i].end() << "]\n");
}
RENAME_DEBUG(debug_log << "==================================\n\n");
}
}
#ifndef NDEBUG
/* Function used for debugging. */
static void dump_instruction(ostream& os, int line, prog_scope *scope,
const glsl_to_tgsi_instruction& inst);
#endif
/* Scan the program and estimate the required register live ranges.
* The arraylive_ranges must be pre-allocated
*/
bool
get_temp_registers_required_live_ranges(void *mem_ctx, exec_list *instructions,
int ntemps, struct register_live_range *register_live_ranges,
int narrays, class array_live_range *array_live_ranges)
{
int line = 0;
int loop_id = 1;
int if_id = 1;
int switch_id = 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;
}
prog_scope_storage scopes(mem_ctx, n_scopes);
access_recorder access(ntemps, narrays);
prog_scope *cur_scope = scopes.create(nullptr, outer_scope, 0, 0, line);
RENAME_DEBUG(debug_log << "========= Begin shader ============\n");
foreach_in_list(glsl_to_tgsi_instruction, inst, instructions) {
if (is_at_end) {
assert(!"GLSL_TO_TGSI: shader has instructions past end marker");
break;
}
RENAME_DEBUG(dump_instruction(debug_log, line, cur_scope, *inst));
switch (inst->op) {
case TGSI_OPCODE_BGNLOOP: {
cur_scope = scopes.create(cur_scope, loop_body, loop_id++,
cur_scope->nesting_depth() + 1, line);
break;
}
case TGSI_OPCODE_ENDLOOP: {
cur_scope->set_end(line);
cur_scope = cur_scope->parent();
assert(cur_scope);
break;
}
case TGSI_OPCODE_IF:
case TGSI_OPCODE_UIF: {
assert(num_inst_src_regs(inst) == 1);
access.record_read(inst->src[0], line, cur_scope);
cur_scope = scopes.create(cur_scope, if_branch, if_id++,
cur_scope->nesting_depth() + 1, line + 1);
break;
}
case TGSI_OPCODE_ELSE: {
assert(cur_scope->type() == if_branch);
cur_scope->set_end(line - 1);
cur_scope = scopes.create(cur_scope->parent(), else_branch,
cur_scope->id(), cur_scope->nesting_depth(),
line + 1);
break;
}
case TGSI_OPCODE_END: {
cur_scope->set_end(line);
is_at_end = true;
break;
}
case TGSI_OPCODE_ENDIF: {
cur_scope->set_end(line - 1);
cur_scope = cur_scope->parent();
assert(cur_scope);
break;
}
case TGSI_OPCODE_SWITCH: {
assert(num_inst_src_regs(inst) == 1);
prog_scope *scope = scopes.create(cur_scope, switch_body, switch_id++,
cur_scope->nesting_depth() + 1, line);
/* We record the read only for the SWITCH statement itself, like it
* is used by the only consumer of TGSI_OPCODE_SWITCH in tgsi_exec.c.
*/
access.record_read(inst->src[0], line, cur_scope);
cur_scope = scope;
break;
}
case TGSI_OPCODE_ENDSWITCH: {
cur_scope->set_end(line - 1);
/* Remove the case level, it might not have been
* closed with a break.
*/
if (cur_scope->type() != switch_body)
cur_scope = cur_scope->parent();
cur_scope = cur_scope->parent();
assert(cur_scope);
break;
}
case TGSI_OPCODE_CASE: {
/* Take care of tracking the registers. */
prog_scope *switch_scope = cur_scope->type() == switch_body ?
cur_scope : cur_scope->parent();
assert(num_inst_src_regs(inst) == 1);
access.record_read(inst->src[0], line, switch_scope);
/* Fall through to allocate the scope. */
}
case TGSI_OPCODE_DEFAULT: {
prog_scope_type t = inst->op == TGSI_OPCODE_CASE ? switch_case_branch
: switch_default_branch;
prog_scope *switch_scope = (cur_scope->type() == switch_body) ?
cur_scope : cur_scope->parent();
assert(switch_scope->type() == switch_body);
prog_scope *scope = scopes.create(switch_scope, t,
switch_scope->id(),
switch_scope->nesting_depth() + 1,
line);
/* Previous case falls through, so scope was not yet closed. */
if ((cur_scope != switch_scope) && (cur_scope->end() == -1))
cur_scope->set_end(line - 1);
cur_scope = scope;
break;
}
case TGSI_OPCODE_BRK: {
if (cur_scope->break_is_for_switchcase()) {
cur_scope->set_end(line - 1);
} else {
cur_scope->set_loop_break_line(line);
}
break;
}
case TGSI_OPCODE_CAL:
case TGSI_OPCODE_RET:
/* These opcodes are not supported and if a subroutine would
* be called in a shader, then the live_range tracking would have
* to follow that call to see which registers are used there.
* Since this is not done, we have to bail out here and signal
* that no register merge will take place.
*/
return false;
default: {
for (unsigned j = 0; j < num_inst_src_regs(inst); j++) {
access.record_read(inst->src[j], line, cur_scope);
}
for (unsigned j = 0; j < inst->tex_offset_num_offset; j++) {
access.record_read(inst->tex_offsets[j], line, cur_scope);
}
unsigned ndst = num_inst_dst_regs(inst);
for (unsigned j = 0; j < ndst; j++) {
access.record_write(inst->dst[j], line, cur_scope, ndst == 1);
}
access.record_read(inst->resource, line, cur_scope);
}
}
++line;
}
RENAME_DEBUG(debug_log << "==================================\n\n");
/* Make sure last scope is closed, even though no
* TGSI_OPCODE_END was given.
*/
if (cur_scope->end() < 0)
cur_scope->set_end(line - 1);
access.get_required_live_ranges(register_live_ranges, array_live_ranges);
return true;
}
/* Find the next register between [start, end) that has a live range 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 register_merge_record*
find_next_rename(register_merge_record* start, register_merge_record* end, int bound)
{
int delta = (end - start);
while (delta > 0) {
int half = delta >> 1;
register_merge_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 register_merge_record_compare (const void *a, const void *b) {
const register_merge_record *aa = static_cast<const register_merge_record*>(a);
const register_merge_record *bb = static_cast<const register_merge_record*>(b);
return aa->begin < bb->begin ? -1 : (aa->begin > bb->begin ? 1 : 0);
}
#endif
/* This functions evaluates the register merges by using a binary
* search to find suitable merge candidates. */
void get_temp_registers_remapping(void *mem_ctx, int ntemps,
const struct register_live_range *live_ranges,
struct rename_reg_pair *result)
{
register_merge_record *reg_access = ralloc_array(mem_ctx, register_merge_record, ntemps);
int used_temps = 0;
for (int i = 0; i < ntemps; ++i) {
if (live_ranges[i].begin >= 0) {
reg_access[used_temps].begin =live_ranges[i].begin;
reg_access[used_temps].end =live_ranges[i].end;
reg_access[used_temps].reg = i;
reg_access[used_temps].erase = false;
++used_temps;
}
}
#ifdef USE_STL_SORT
std::sort(reg_access, reg_access + used_temps);
#else
std::qsort(reg_access, used_temps, sizeof(register_merge_record),
register_merge_record_compare);
#endif
register_merge_record *trgt = reg_access;
register_merge_record *reg_access_end = reg_access + used_temps;
register_merge_record *first_erase = reg_access_end;
register_merge_record *search_start = trgt + 1;
while (trgt != reg_access_end) {
register_merge_record *src = find_next_rename(search_start, reg_access_end,
trgt->end);
if (src != reg_access_end) {
result[src->reg].new_reg = trgt->reg;
result[src->reg].valid = true;
trgt->end = src->end;
/* Since we only search forward, don't remove the renamed
* register just now, only mark it. */
src->erase = true;
if (first_erase == reg_access_end)
first_erase = src;
search_start = src + 1;
} else {
/* Moving to the next target register it is time to remove
* the already merged registers from the search range */
if (first_erase != reg_access_end) {
register_merge_record *outp = first_erase;
register_merge_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
void dump_instruction(ostream& os, int line, prog_scope *scope,
const glsl_to_tgsi_instruction& inst)
{
const struct tgsi_opcode_info *info = inst.info;
int indent = scope->nesting_depth();
if ((scope->type() == switch_case_branch ||
scope->type() == switch_default_branch) &&
(info->opcode == TGSI_OPCODE_CASE ||
info->opcode == TGSI_OPCODE_DEFAULT))
--indent;
if (info->opcode == TGSI_OPCODE_ENDIF ||
info->opcode == TGSI_OPCODE_ELSE ||
info->opcode == TGSI_OPCODE_ENDLOOP ||
info->opcode == TGSI_OPCODE_ENDSWITCH)
--indent;
os << setw(4) << line << ": ";
os << setw(indent * 4) << " ";
os << inst << "\n";
}
#endif