/*
* Copyright © 2013 Intel Corporation
*
* 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.
*/
/**
* \file opt_cse.cpp
*
* constant subexpression elimination at the GLSL IR level.
*
* Compare to brw_fs_cse.cpp for a more complete CSE implementation. This one
* is generic and handles texture operations, but it's rather simple currently
* and doesn't support modification of variables in the available expressions
* list, so it can't do variables other than uniforms or shader inputs.
*/
#include "ir.h"
#include "ir_visitor.h"
#include "ir_rvalue_visitor.h"
#include "ir_basic_block.h"
#include "ir_optimization.h"
#include "ir_builder.h"
#include "glsl_types.h"
using namespace ir_builder;
static bool debug = false;
namespace {
/**
* This is the record of an available expression for common subexpression
* elimination.
*/
class ae_entry : public exec_node
{
public:
ae_entry(ir_instruction *base_ir, ir_rvalue **val)
: val(val), base_ir(base_ir)
{
assert(val);
assert(*val);
assert(base_ir);
var = NULL;
}
void init(ir_instruction *base_ir, ir_rvalue **val)
{
this->val = val;
this->base_ir = base_ir;
this->var = NULL;
assert(val);
assert(*val);
assert(base_ir);
}
/**
* The pointer to the expression that we might be able to reuse
*
* Note the double pointer -- this is the place in the base_ir expression
* tree that we would rewrite to move the expression out to a new variable
* assignment.
*/
ir_rvalue **val;
/**
* Root instruction in the basic block where the expression appeared.
*
* This is used so that we can insert the new variable declaration into the
* instruction stream (since *val is just somewhere in base_ir's expression
* tree).
*/
ir_instruction *base_ir;
/**
* The variable that the expression has been stored in, if it's been CSEd
* once already.
*/
ir_variable *var;
};
class cse_visitor : public ir_rvalue_visitor {
public:
cse_visitor(exec_list *validate_instructions)
: validate_instructions(validate_instructions)
{
progress = false;
mem_ctx = ralloc_context(NULL);
this->ae = new(mem_ctx) exec_list;
}
~cse_visitor()
{
ralloc_free(mem_ctx);
}
virtual ir_visitor_status visit_enter(ir_function_signature *ir);
virtual ir_visitor_status visit_enter(ir_loop *ir);
virtual ir_visitor_status visit_enter(ir_if *ir);
virtual ir_visitor_status visit_enter(ir_call *ir);
virtual void handle_rvalue(ir_rvalue **rvalue);
bool progress;
private:
void *mem_ctx;
ir_rvalue *try_cse(ir_rvalue *rvalue);
void add_to_ae(ir_rvalue **rvalue);
/**
* Move all nodes from the ae list to the free list
*/
void empty_ae_list();
/**
* Get and initialize a new ae_entry
*
* This will either come from the free list or be freshly allocated.
*/
ae_entry *get_ae_entry(ir_rvalue **rvalue);
/** List of ae_entry: The available expressions to reuse */
exec_list *ae;
/**
* The whole shader, so that we can validate_ir_tree in debug mode.
*
* This proved quite useful when trying to get the tree manipulation
* right.
*/
exec_list *validate_instructions;
/**
* List of available-for-use ae_entry objects.
*/
exec_list free_ae_entries;
};
/**
* Visitor to walk an expression tree to check that all variables referenced
* are constants.
*/
class is_cse_candidate_visitor : public ir_hierarchical_visitor
{
public:
is_cse_candidate_visitor()
: ok(true)
{
}
virtual ir_visitor_status visit(ir_dereference_variable *ir);
bool ok;
};
class contains_rvalue_visitor : public ir_rvalue_visitor
{
public:
contains_rvalue_visitor(ir_rvalue *val)
: val(val)
{
found = false;
}
virtual void handle_rvalue(ir_rvalue **rvalue);
bool found;
private:
ir_rvalue *val;
};
} /* unnamed namespace */
static void
dump_ae(exec_list *ae)
{
int i = 0;
printf("CSE: AE contents:\n");
foreach_in_list(ae_entry, entry, ae) {
printf("CSE: AE %2d (%p): ", i, entry);
(*entry->val)->print();
printf("\n");
if (entry->var)
printf("CSE: in var %p:\n", entry->var);
i++;
}
}
ir_visitor_status
is_cse_candidate_visitor::visit(ir_dereference_variable *ir)
{
/* Currently, since we don't handle kills of the ae based on variables
* getting assigned, we can only handle constant variables.
*/
if (ir->var->data.read_only) {
return visit_continue;
} else {
if (debug)
printf("CSE: non-candidate: var %s is not read only\n", ir->var->name);
ok = false;
return visit_stop;
}
}
void
contains_rvalue_visitor::handle_rvalue(ir_rvalue **rvalue)
{
if (*rvalue == val)
found = true;
}
static bool
contains_rvalue(ir_rvalue *haystack, ir_rvalue *needle)
{
contains_rvalue_visitor v(needle);
haystack->accept(&v);
return v.found;
}
static bool
is_cse_candidate(ir_rvalue *ir)
{
/* Our temporary variable assignment generation isn't ready to handle
* anything bigger than a vector.
*/
if (!ir->type->is_vector() && !ir->type->is_scalar()) {
if (debug)
printf("CSE: non-candidate: not a vector/scalar\n");
return false;
}
/* Only handle expressions and textures currently. We may want to extend
* to variable-index array dereferences at some point.
*/
switch (ir->ir_type) {
case ir_type_expression:
case ir_type_texture:
break;
default:
if (debug)
printf("CSE: non-candidate: not an expression/texture\n");
return false;
}
is_cse_candidate_visitor v;
ir->accept(&v);
return v.ok;
}
/**
* Tries to find and return a reference to a previous computation of a given
* expression.
*
* Walk the list of available expressions checking if any of them match the
* rvalue, and if so, move the previous copy of the expression to a temporary
* and return a reference of the temporary.
*/
ir_rvalue *
cse_visitor::try_cse(ir_rvalue *rvalue)
{
foreach_in_list(ae_entry, entry, ae) {
if (debug) {
printf("Comparing to AE %p: ", entry);
(*entry->val)->print();
printf("\n");
}
if (!rvalue->equals(*entry->val))
continue;
if (debug) {
printf("CSE: Replacing: ");
(*entry->val)->print();
printf("\n");
printf("CSE: with: ");
rvalue->print();
printf("\n");
}
if (!entry->var) {
ir_instruction *base_ir = entry->base_ir;
ir_variable *var = new(rvalue) ir_variable(rvalue->type,
"cse",
ir_var_temporary);
/* Write the previous expression result into a new variable. */
base_ir->insert_before(var);
ir_assignment *assignment = assign(var, *entry->val);
base_ir->insert_before(assignment);
/* Replace the expression in the original tree with a deref of the
* variable, but keep tracking the expression for further reuse.
*/
*entry->val = new(rvalue) ir_dereference_variable(var);
entry->val = &assignment->rhs;
entry->var = var;
/* Update the base_irs in the AE list. We have to be sure that
* they're correct -- expressions from our base_ir that weren't moved
* need to stay in this base_ir (so that later consumption of them
* puts new variables between our new variable and our base_ir), but
* expressions from our base_ir that we *did* move need base_ir
* updated so that any further elimination from inside gets its new
* assignments put before our new assignment.
*/
foreach_in_list(ae_entry, fixup_entry, ae) {
if (contains_rvalue(assignment->rhs, *fixup_entry->val))
fixup_entry->base_ir = assignment;
}
if (debug)
dump_ae(ae);
}
/* Replace the expression in our current tree with the variable. */
return new(rvalue) ir_dereference_variable(entry->var);
}
return NULL;
}
void
cse_visitor::empty_ae_list()
{
free_ae_entries.append_list(ae);
}
ae_entry *
cse_visitor::get_ae_entry(ir_rvalue **rvalue)
{
ae_entry *entry = (ae_entry *) free_ae_entries.pop_head();
if (entry) {
entry->init(base_ir, rvalue);
} else {
entry = new(mem_ctx) ae_entry(base_ir, rvalue);
}
return entry;
}
/** Add the rvalue to the list of available expressions for CSE. */
void
cse_visitor::add_to_ae(ir_rvalue **rvalue)
{
if (debug) {
printf("CSE: Add to AE: ");
(*rvalue)->print();
printf("\n");
}
ae->push_tail(get_ae_entry(rvalue));
if (debug)
dump_ae(ae);
}
void
cse_visitor::handle_rvalue(ir_rvalue **rvalue)
{
if (!*rvalue)
return;
if (debug) {
printf("CSE: handle_rvalue ");
(*rvalue)->print();
printf("\n");
}
if (!is_cse_candidate(*rvalue))
return;
ir_rvalue *new_rvalue = try_cse(*rvalue);
if (new_rvalue) {
*rvalue = new_rvalue;
progress = true;
if (debug)
validate_ir_tree(validate_instructions);
} else {
add_to_ae(rvalue);
}
}
ir_visitor_status
cse_visitor::visit_enter(ir_if *ir)
{
handle_rvalue(&ir->condition);
empty_ae_list();
visit_list_elements(this, &ir->then_instructions);
empty_ae_list();
visit_list_elements(this, &ir->else_instructions);
empty_ae_list();
return visit_continue_with_parent;
}
ir_visitor_status
cse_visitor::visit_enter(ir_function_signature *ir)
{
empty_ae_list();
visit_list_elements(this, &ir->body);
empty_ae_list();
return visit_continue_with_parent;
}
ir_visitor_status
cse_visitor::visit_enter(ir_loop *ir)
{
empty_ae_list();
visit_list_elements(this, &ir->body_instructions);
empty_ae_list();
return visit_continue_with_parent;
}
ir_visitor_status
cse_visitor::visit_enter(ir_call *)
{
/* Because call is an exec_list of ir_rvalues, handle_rvalue gets passed a
* pointer to the (ir_rvalue *) on the stack. Since we save those pointers
* in the AE list, we can't let handle_rvalue get called.
*/
return visit_continue_with_parent;
}
/**
* Does a (uniform-value) constant subexpression elimination pass on the code
* present in the instruction stream.
*/
bool
do_cse(exec_list *instructions)
{
cse_visitor v(instructions);
visit_list_elements(&v, instructions);
return v.progress;
}