X-Git-Url: http://git.tdb.fi/?p=libs%2Fgl.git;a=blobdiff_plain;f=source%2Fglsl%2Foptimize.cpp;h=ed20bb175dcc9277e1ff84e2e1a1734b2279668f;hp=c76cae1b50f34a69ade9d31ead0c563250d24ae6;hb=8bf70f4d445cf63386ad7aafc5b3ebdbd8369939;hpb=1fa69bb8eec3070f5da296d6dd0bd67aea62d3bf diff --git a/source/glsl/optimize.cpp b/source/glsl/optimize.cpp index c76cae1b..ed20bb17 100644 --- a/source/glsl/optimize.cpp +++ b/source/glsl/optimize.cpp @@ -1,5 +1,8 @@ #include +#include +#include #include "optimize.h" +#include "reflect.h" using namespace std; @@ -7,21 +10,73 @@ namespace Msp { namespace GL { namespace SL { +ConstantSpecializer::ConstantSpecializer(): + values(0) +{ } + +void ConstantSpecializer::apply(Stage &stage, const map &v) +{ + values = &v; + stage.content.visit(*this); +} + +void ConstantSpecializer::visit(VariableDeclaration &var) +{ + bool specializable = false; + if(var.layout) + { + vector &qualifiers = var.layout->qualifiers; + for(vector::iterator i=qualifiers.begin(); (!specializable && i!=qualifiers.end()); ++i) + if(i->name=="constant_id") + { + specializable = true; + qualifiers.erase(i); + } + + if(qualifiers.empty()) + var.layout = 0; + } + + if(specializable) + { + map::const_iterator i = values->find(var.name); + if(i!=values->end()) + { + RefPtr literal = new Literal; + if(var.type=="bool") + { + literal->token = (i->second ? "true" : "false"); + literal->value = static_cast(i->second); + } + else if(var.type=="int") + { + literal->token = lexical_cast(i->second); + literal->value = i->second; + } + var.init_expression = literal; + } + } +} + + InlineableFunctionLocator::InlineableFunctionLocator(): - in_function(0) + current_function(0), + return_count(0) { } void InlineableFunctionLocator::visit(FunctionCall &call) { FunctionDeclaration *def = call.declaration; - if(def && def->definition!=def) + if(def) def = def->definition; if(def) { unsigned &count = refcounts[def]; ++count; - if(count>1 || def==in_function) + /* Don't inline functions which are called more than once or are called + recursively. */ + if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function) inlineable.erase(def); } @@ -30,409 +85,1339 @@ void InlineableFunctionLocator::visit(FunctionCall &call) void InlineableFunctionLocator::visit(FunctionDeclaration &func) { + bool has_out_params = false; + for(NodeArray::const_iterator i=func.parameters.begin(); (!has_out_params && i!=func.parameters.end()); ++i) + has_out_params = ((*i)->interface=="out"); + unsigned &count = refcounts[func.definition]; - if(!count && func.parameters.empty()) + if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params) inlineable.insert(func.definition); - SetForScope set(in_function, &func); + SetForScope set(current_function, &func); + return_count = 0; TraversingVisitor::visit(func); } +void InlineableFunctionLocator::visit(Conditional &cond) +{ + TraversingVisitor::visit(cond); + inlineable.erase(current_function); +} -FunctionInliner::FunctionInliner(): - extract_result(0) -{ } +void InlineableFunctionLocator::visit(Iteration &iter) +{ + TraversingVisitor::visit(iter); + inlineable.erase(current_function); +} + +void InlineableFunctionLocator::visit(Return &ret) +{ + TraversingVisitor::visit(ret); + if(return_count) + inlineable.erase(current_function); + ++return_count; +} -FunctionInliner::FunctionInliner(const set &in): - inlineable(in), - extract_result(0) + +InlineContentInjector::InlineContentInjector(): + source_func(0), + pass(REFERENCED) { } -void FunctionInliner::visit_and_inline(RefPtr &ptr) +string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList::iterator &ins_pt, FunctionCall &call) { - inline_result = 0; - ptr->visit(*this); - if(inline_result) - ptr = inline_result; + source_func = call.declaration->definition; + + /* Populate referenced_names from the target function so we can rename + variables from the inlined function that would conflict. */ + pass = REFERENCED; + target_func.visit(*this); + + /* Inline and rename passes must be interleaved so used variable names are + known when inlining the return statement. */ + pass = INLINE; + staging_block.parent = &tgt_blk; + staging_block.variables.clear(); + + vector > params; + params.reserve(source_func->parameters.size()); + for(NodeArray::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i) + { + RefPtr var = (*i)->clone(); + var->interface.clear(); + + SetForScope set_pass(pass, RENAME); + var->visit(*this); + + staging_block.body.push_back_nocopy(var); + params.push_back(var); + } + + for(NodeList::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i) + { + r_inlined_statement = 0; + (*i)->visit(*this); + if(!r_inlined_statement) + r_inlined_statement = (*i)->clone(); + + SetForScope set_pass(pass, RENAME); + r_inlined_statement->visit(*this); + + staging_block.body.push_back_nocopy(r_inlined_statement); + } + + /* Now collect names from the staging block. Local variables that would + have conflicted with the target function were renamed earlier. */ + pass = REFERENCED; + referenced_names.clear(); + staging_block.variables.clear(); + staging_block.visit(*this); + + /* Rename variables in the target function so they don't interfere with + global identifiers used by the source function. */ + pass = RENAME; + staging_block.parent = source_func->body.parent; + target_func.visit(*this); + + // Put the argument expressions in place after all renaming has been done. + for(unsigned i=0; iparameters.size(); ++i) + params[i]->init_expression = call.arguments[i]->clone(); + + tgt_blk.body.splice(ins_pt, staging_block.body); + + NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func)); + + return r_result_name; } -void FunctionInliner::visit(Block &block) +void InlineContentInjector::visit(VariableReference &var) { - if(extract_result) - --extract_result; + if(pass==RENAME) + { + map::const_iterator i = staging_block.variables.find(var.name); + if(i!=staging_block.variables.end()) + var.name = i->second->name; + } + else if(pass==REFERENCED) + referenced_names.insert(var.name); +} - for(NodeList::iterator i=block.body.begin(); i!=block.body.end(); ++i) +void InlineContentInjector::visit(InterfaceBlockReference &iface) +{ + if(pass==REFERENCED) + referenced_names.insert(iface.name); +} + +void InlineContentInjector::visit(FunctionCall &call) +{ + if(pass==REFERENCED) + referenced_names.insert(call.name); + TraversingVisitor::visit(call); +} + +void InlineContentInjector::visit(VariableDeclaration &var) +{ + TraversingVisitor::visit(var); + + if(pass==RENAME) { - (*i)->visit(*this); - if(extract_result) - --extract_result; + /* Check against conflicts with the other context as well as variables + already renamed here. */ + bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name)); + staging_block.variables[var.name] = &var; + if(conflict) + { + string mapped_name = get_unused_variable_name(staging_block, var.name); + if(mapped_name!=var.name) + { + staging_block.variables[mapped_name] = &var; + var.name = mapped_name; + } + } } + else if(pass==REFERENCED) + referenced_names.insert(var.type); } -void FunctionInliner::visit(UnaryExpression &unary) +void InlineContentInjector::visit(Return &ret) { - visit_and_inline(unary.expression); - inline_result = 0; + TraversingVisitor::visit(ret); + + if(pass==INLINE && ret.expression) + { + // Create a new variable to hold the return value of the inlined function. + r_result_name = get_unused_variable_name(staging_block, "_return"); + RefPtr var = new VariableDeclaration; + var->source = ret.source; + var->line = ret.line; + var->type = source_func->return_type; + var->name = r_result_name; + var->init_expression = ret.expression->clone(); + r_inlined_statement = var; + } } -void FunctionInliner::visit(BinaryExpression &binary) + +FunctionInliner::FunctionInliner(): + current_function(0), + r_any_inlined(false), + r_inlined_here(false) +{ } + +bool FunctionInliner::apply(Stage &s) { - visit_and_inline(binary.left); - visit_and_inline(binary.right); - inline_result = 0; + stage = &s; + inlineable = InlineableFunctionLocator().apply(s); + r_any_inlined = false; + s.content.visit(*this); + return r_any_inlined; } -void FunctionInliner::visit(MemberAccess &memacc) +void FunctionInliner::visit(RefPtr &ptr) { - visit_and_inline(memacc.left); - inline_result = 0; + r_inline_result = 0; + ptr->visit(*this); + if(r_inline_result) + { + ptr = r_inline_result; + r_any_inlined = true; + } + r_inline_result = 0; +} + +void FunctionInliner::visit(Block &block) +{ + SetForScope set_block(current_block, &block); + SetForScope::iterator> save_insert_point(insert_point, block.body.begin()); + for(NodeList::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i) + { + insert_point = i; + (*i)->visit(*this); + } } void FunctionInliner::visit(FunctionCall &call) { - for(NodeArray::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i) - visit_and_inline(*i); + for(NodeArray::iterator i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i) + visit(*i); + + if(r_inlined_here) + return; FunctionDeclaration *def = call.declaration; - if(def && def->definition!=def) + if(def) def = def->definition; if(def && inlineable.count(def)) { - extract_result = 2; - def->visit(*this); + string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call); + + // This will later get removed by UnusedVariableRemover. + if(result_name.empty()) + result_name = "_msp_unused_from_inline"; + + RefPtr ref = new VariableReference; + ref->name = result_name; + r_inline_result = ref; + + /* Inlined variables need to be resolved before this function can be + inlined further. */ + inlineable.erase(current_function); + r_inlined_here = true; } - else - inline_result = 0; } -void FunctionInliner::visit(VariableDeclaration &var) +void FunctionInliner::visit(FunctionDeclaration &func) { - if(var.init_expression) - visit_and_inline(var.init_expression); - inline_result = 0; + SetForScope set_func(current_function, &func); + TraversingVisitor::visit(func); + r_inlined_here = false; } -void FunctionInliner::visit(Return &ret) +void FunctionInliner::visit(Iteration &iter) { - TraversingVisitor::visit(ret); - - if(extract_result) - inline_result = ret.expression->clone(); + /* Visit the initialization statement before entering the loop body so the + inlined statements get inserted outside. */ + if(iter.init_statement) + iter.init_statement->visit(*this); + + SetForScope set_block(current_block, &iter.body); + /* Skip the condition and loop expression parts because they're not properly + inside the body block. Inlining anything into them will require a more + comprehensive transformation. */ + iter.body.visit(*this); } -ConstantConditionEliminator::ConstantConditionEliminator(): - scope_level(0), - record_only(false) +ExpressionInliner::ExpressionInliner(): + r_ref_info(0), + r_any_inlined(false), + r_trivial(false), + mutating(false), + iteration_init(false), + iteration_body(0), + r_oper(0) { } -void ConstantConditionEliminator::visit(Block &block) +bool ExpressionInliner::apply(Stage &s) { - SetForScope set(scope_level, scope_level+1); - BlockModifier::visit(block); - - for(map::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i) - variable_values.erase(i->second); + s.content.visit(*this); + return r_any_inlined; } -void ConstantConditionEliminator::visit(UnaryExpression &unary) +void ExpressionInliner::inline_expression(Expression &expr, RefPtr &ptr) { - if(VariableReference *var = dynamic_cast(unary.expression.get())) - if(unary.oper=="++" || unary.oper=="--") - variable_values.erase(var->declaration); + ptr = expr.clone(); + r_any_inlined = true; } -void ConstantConditionEliminator::visit(Assignment &assign) +void ExpressionInliner::visit(Block &block) { - variable_values.erase(assign.target_declaration); + TraversingVisitor::visit(block); + + for(map::iterator i=block.variables.begin(); i!=block.variables.end(); ++i) + { + map::iterator j = expressions.lower_bound(i->second); + for(; (j!=expressions.end() && j->first.declaration==i->second); ) + { + if(j->second.expression && j->second.inline_point) + inline_expression(*j->second.expression, *j->second.inline_point); + + expressions.erase(j++); + } + } + + /* Expressions assigned in this block may depend on local variables of the + block. If this is a conditionally executed block, the assignments might not + always happen. Mark the expressions as not available to any outer blocks. */ + for(map::iterator i=expressions.begin(); i!=expressions.end(); ++i) + if(i->second.assign_scope==&block) + i->second.available = false; } -void ConstantConditionEliminator::visit(VariableDeclaration &var) +void ExpressionInliner::visit(RefPtr &expr) { - if(var.constant || scope_level>1) - variable_values[&var] = var.init_expression.get(); + r_ref_info = 0; + expr->visit(*this); + if(r_ref_info && r_ref_info->expression && r_ref_info->available) + { + if(iteration_body && !r_ref_info->trivial) + { + /* Don't inline non-trivial expressions which were assigned outside + an iteration statement. The iteration may run multiple times, which + would cause the expression to also be evaluated multiple times. */ + Block *i = r_ref_info->assign_scope; + for(; (i && i!=iteration_body); i=i->parent) ; + if(!i) + return; + } + + if(r_ref_info->trivial) + inline_expression(*r_ref_info->expression, expr); + else + /* Record the inline point for a non-trivial expression but don't + inline it yet. It might turn out it shouldn't be inlined after all. */ + r_ref_info->inline_point = &expr; + } + r_oper = expr->oper; + r_ref_info = 0; } -void ConstantConditionEliminator::visit(Conditional &cond) +void ExpressionInliner::visit(VariableReference &var) { - if(!record_only) + if(var.declaration) { - ExpressionEvaluator eval(variable_values); - cond.condition->visit(eval); - if(eval.is_result_valid()) + map::iterator i = expressions.find(var.declaration); + if(i!=expressions.end()) { - flatten_block(eval.get_result() ? cond.body : cond.else_body); - return; + /* If a non-trivial expression is referenced multiple times, don't + inline it. */ + if(i->second.inline_point && !i->second.trivial) + i->second.expression = 0; + /* Mutating expressions are analogous to self-referencing assignments + and prevent inlining. */ + if(mutating) + i->second.expression = 0; + r_ref_info = &i->second; } } +} - TraversingVisitor::visit(cond); +void ExpressionInliner::visit(MemberAccess &memacc) +{ + visit(memacc.left); + r_trivial = false; } -void ConstantConditionEliminator::visit(Iteration &iter) +void ExpressionInliner::visit(Swizzle &swizzle) { - if(!record_only) + visit(swizzle.left); + r_trivial = false; +} + +void ExpressionInliner::visit(UnaryExpression &unary) +{ + SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-'); + visit(unary.expression); + r_trivial = false; +} + +void ExpressionInliner::visit(BinaryExpression &binary) +{ + visit(binary.left); { - if(iter.condition) - { - /* If the loop condition is always false on the first iteration, the - entire loop can be removed */ - if(iter.init_statement) - iter.init_statement->visit(*this); - ExpressionEvaluator eval(variable_values); - iter.condition->visit(eval); - if(eval.is_result_valid() && !eval.get_result()) - { - remove_node = true; - return; - } - } + SetFlag clear_target(mutating, false); + visit(binary.right); + } + r_trivial = false; +} - /* Record all assignments that occur inside the loop body so those - variables won't be considered as constant */ - SetFlag set_record(record_only); - TraversingVisitor::visit(iter); +void ExpressionInliner::visit(Assignment &assign) +{ + { + SetFlag set_target(mutating); + visit(assign.left); } + r_oper = 0; + visit(assign.right); - TraversingVisitor::visit(iter); + map::iterator i = expressions.find(assign.target); + if(i!=expressions.end()) + { + /* Self-referencing assignments can't be inlined without additional + work. Just clear any previous expression. */ + i->second.expression = (assign.self_referencing ? 0 : assign.right.get()); + i->second.assign_scope = current_block; + i->second.inline_point = 0; + i->second.available = true; + } - if(VariableDeclaration *init_decl = dynamic_cast(iter.init_statement.get())) - variable_values.erase(init_decl); + r_trivial = false; } +void ExpressionInliner::visit(TernaryExpression &ternary) +{ + visit(ternary.condition); + visit(ternary.true_expr); + visit(ternary.false_expr); + r_trivial = false; +} -UnusedVariableLocator::VariableInfo::VariableInfo(): - local(false), - conditionally_assigned(false), - referenced(false) -{ } +void ExpressionInliner::visit(FunctionCall &call) +{ + TraversingVisitor::visit(call); + r_trivial = false; +} +void ExpressionInliner::visit(VariableDeclaration &var) +{ + r_oper = 0; + r_trivial = true; + TraversingVisitor::visit(var); -UnusedVariableLocator::UnusedVariableLocator(): - aggregate(0), - assignment(0), - assignment_target(false), - assign_to_subscript(false), - global_scope(true) -{ } + bool constant = var.constant; + if(constant && var.layout) + { + for(vector::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i) + constant = (i->name!="constant_id"); + } -const set &UnusedVariableLocator::apply(Stage &s) + /* Only inline global variables if they're constant and have trivial + initializers. Non-constant variables could change in ways which are hard to + analyze and non-trivial expressions could be expensive to inline. */ + if((current_block->parent || (constant && r_trivial)) && var.interface.empty()) + { + ExpressionInfo &info = expressions[&var]; + /* Assume variables declared in an iteration initialization statement + will have their values change throughout the iteration. */ + info.expression = (iteration_init ? 0 : var.init_expression.get()); + info.assign_scope = current_block; + info.trivial = r_trivial; + } +} + +void ExpressionInliner::visit(Iteration &iter) { - variables.push_back(BlockVariableMap()); - visit(s.content); - BlockVariableMap &global_variables = variables.back(); - for(BlockVariableMap::iterator i=global_variables.begin(); i!=global_variables.end(); ++i) + SetForScope set_block(current_block, &iter.body); + if(iter.init_statement) { - if(i->first->interface=="out" && (s.type==Stage::FRAGMENT || i->first->linked_declaration || !i->first->name.compare(0, 3, "gl_"))) - continue; - if(!i->second.referenced) - { - unused_nodes.insert(i->first); - clear_assignments(i->second, true); - } + SetFlag set_init(iteration_init); + iter.init_statement->visit(*this); } - variables.pop_back(); - return unused_nodes; + SetForScope set_body(iteration_body, &iter.body); + if(iter.condition) + visit(iter.condition); + iter.body.visit(*this); + if(iter.loop_expression) + visit(iter.loop_expression); +} + + +template +T ConstantFolder::evaluate_logical(char oper, T left, T right) +{ + switch(oper) + { + case '&': return left&right; + case '|': return left|right; + case '^': return left^right; + default: return T(); + } } -void UnusedVariableLocator::visit(VariableReference &var) +template +bool ConstantFolder::evaluate_relation(const char *oper, T left, T right) { - map::iterator i = aggregates.find(var.declaration); - if(i!=aggregates.end()) - unused_nodes.erase(i->second); + switch(oper[0]|oper[1]) + { + case '<': return left': return left>right; + case '>'|'=': return left>=right; + default: return false; + } +} - if(var.declaration && !assignment_target) +template +T ConstantFolder::evaluate_arithmetic(char oper, T left, T right) +{ + switch(oper) { - VariableInfo &var_info = variables.back()[var.declaration]; - var_info.assignments.clear(); - var_info.referenced = true; + case '+': return left+right; + case '-': return left-right; + case '*': return left*right; + case '/': return left/right; + default: return T(); } } -void UnusedVariableLocator::visit(MemberAccess &memacc) +template +T ConstantFolder::evaluate_int_special_op(char oper, T left, T right) +{ + switch(oper) + { + case '%': return left%right; + case '<': return left<': return left>>right; + default: return T(); + } +} + +template +void ConstantFolder::convert_to_result(const Variant &value) +{ + if(value.check_type()) + set_result(static_cast(value.value())); + else if(value.check_type()) + set_result(static_cast(value.value())); + else if(value.check_type()) + set_result(static_cast(value.value())); + else if(value.check_type()) + set_result(static_cast(value.value())); +} + +void ConstantFolder::set_result(const Variant &value, bool literal) +{ + r_constant_value = value; + r_constant = true; + r_literal = literal; +} + +void ConstantFolder::visit(RefPtr &expr) +{ + r_constant_value = Variant(); + r_constant = false; + r_literal = false; + r_uses_iter_var = false; + expr->visit(*this); + /* Don't replace literals since they'd only be replaced with an identical + literal. Also skip anything that uses an iteration variable, but pass on + the result so the Iteration visiting function can handle it. */ + if(!r_constant || r_literal || r_uses_iter_var) + return; + + RefPtr literal = new Literal; + if(r_constant_value.check_type()) + literal->token = (r_constant_value.value() ? "true" : "false"); + else if(r_constant_value.check_type()) + literal->token = lexical_cast(r_constant_value.value()); + else if(r_constant_value.check_type()) + literal->token = lexical_cast(r_constant_value.value())+"u"; + else if(r_constant_value.check_type()) + { + literal->token = lexical_cast(r_constant_value.value()); + if(isnumrc(literal->token)) + literal->token += ".0"; + } + else + { + r_constant = false; + return; + } + literal->value = r_constant_value; + expr = literal; + r_any_folded = true; +} + +void ConstantFolder::visit(Literal &literal) +{ + set_result(literal.value, true); +} + +void ConstantFolder::visit(VariableReference &var) +{ + /* If an iteration variable is initialized with a constant value, return + that value here for the purpose of evaluating the loop condition for the + first iteration. */ + if(var.declaration==iteration_var) + { + set_result(iter_init_value); + r_uses_iter_var = true; + } +} + +void ConstantFolder::visit(MemberAccess &memacc) { TraversingVisitor::visit(memacc); - unused_nodes.erase(memacc.declaration); + r_constant = false; +} + +void ConstantFolder::visit(Swizzle &swizzle) +{ + TraversingVisitor::visit(swizzle); + r_constant = false; } -void UnusedVariableLocator::visit(BinaryExpression &binary) +void ConstantFolder::visit(UnaryExpression &unary) { - if(binary.oper=="[") + TraversingVisitor::visit(unary); + bool can_fold = r_constant; + r_constant = false; + if(!can_fold) + return; + + char oper = unary.oper->token[0]; + char oper2 = unary.oper->token[1]; + if(oper=='!') { - if(assignment_target) - assign_to_subscript = true; - binary.left->visit(*this); - SetForScope set(assignment_target, false); - binary.right->visit(*this); + if(r_constant_value.check_type()) + set_result(!r_constant_value.value()); + } + else if(oper=='~') + { + if(r_constant_value.check_type()) + set_result(~r_constant_value.value()); + else if(r_constant_value.check_type()) + set_result(~r_constant_value.value()); + } + else if(oper=='-' && !oper2) + { + if(r_constant_value.check_type()) + set_result(-r_constant_value.value()); + else if(r_constant_value.check_type()) + set_result(-r_constant_value.value()); + else if(r_constant_value.check_type()) + set_result(-r_constant_value.value()); + } +} + +void ConstantFolder::visit(BinaryExpression &binary) +{ + visit(binary.left); + bool left_constant = r_constant; + bool left_iter_var = r_uses_iter_var; + Variant left_value = r_constant_value; + visit(binary.right); + if(left_iter_var) + r_uses_iter_var = true; + + bool can_fold = (left_constant && r_constant); + r_constant = false; + if(!can_fold) + return; + + // Currently only expressions with both sides of equal types are handled. + if(!left_value.check_same_type(r_constant_value)) + return; + + char oper = binary.oper->token[0]; + char oper2 = binary.oper->token[1]; + if(oper=='&' || oper=='|' || oper=='^') + { + if(oper2==oper && left_value.check_type()) + set_result(evaluate_logical(oper, left_value.value(), r_constant_value.value())); + else if(!oper2 && left_value.check_type()) + set_result(evaluate_logical(oper, left_value.value(), r_constant_value.value())); + else if(!oper2 && left_value.check_type()) + set_result(evaluate_logical(oper, left_value.value(), r_constant_value.value())); + } + else if((oper=='<' || oper=='>') && oper2!=oper) + { + if(left_value.check_type()) + set_result(evaluate_relation(binary.oper->token, left_value.value(), r_constant_value.value())); + else if(left_value.check_type()) + set_result(evaluate_relation(binary.oper->token, left_value.value(), r_constant_value.value())); + else if(left_value.check_type()) + set_result(evaluate_relation(binary.oper->token, left_value.value(), r_constant_value.value())); + } + else if((oper=='=' || oper=='!') && oper2=='=') + { + if(left_value.check_type()) + set_result((left_value.value()==r_constant_value.value()) == (oper=='=')); + else if(left_value.check_type()) + set_result((left_value.value()==r_constant_value.value()) == (oper=='=')); + else if(left_value.check_type()) + set_result((left_value.value()==r_constant_value.value()) == (oper=='=')); + } + else if(oper=='+' || oper=='-' || oper=='*' || oper=='/') + { + if(left_value.check_type()) + set_result(evaluate_arithmetic(oper, left_value.value(), r_constant_value.value())); + else if(left_value.check_type()) + set_result(evaluate_arithmetic(oper, left_value.value(), r_constant_value.value())); + else if(left_value.check_type()) + set_result(evaluate_arithmetic(oper, left_value.value(), r_constant_value.value())); + } + else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper)) + { + if(left_value.check_type()) + set_result(evaluate_int_special_op(oper, left_value.value(), r_constant_value.value())); + else if(left_value.check_type()) + set_result(evaluate_int_special_op(oper, left_value.value(), r_constant_value.value())); + } +} + +void ConstantFolder::visit(Assignment &assign) +{ + TraversingVisitor::visit(assign); + r_constant = false; +} + +void ConstantFolder::visit(TernaryExpression &ternary) +{ + TraversingVisitor::visit(ternary); + r_constant = false; +} + +void ConstantFolder::visit(FunctionCall &call) +{ + if(call.constructor && call.type && call.arguments.size()==1) + { + const BasicTypeDeclaration *basic = dynamic_cast(call.type); + if(basic) + { + call.arguments[0]->visit(*this); + bool can_fold = r_constant; + r_constant = false; + if(!can_fold) + return; + + if(basic->kind==BasicTypeDeclaration::BOOL) + convert_to_result(r_constant_value); + else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign) + convert_to_result(r_constant_value); + else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign) + convert_to_result(r_constant_value); + else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32) + convert_to_result(r_constant_value); + + return; + } + } + + TraversingVisitor::visit(call); + r_constant = false; +} + +void ConstantFolder::visit(VariableDeclaration &var) +{ + if(iteration_init && var.init_expression) + { + visit(var.init_expression); + if(r_constant) + { + /* Record the value of a constant initialization expression of an + iteration, so it can be used to evaluate the loop condition. */ + iteration_var = &var; + iter_init_value = r_constant_value; + } } else - TraversingVisitor::visit(binary); + TraversingVisitor::visit(var); } -void UnusedVariableLocator::visit(Assignment &assign) +void ConstantFolder::visit(Iteration &iter) { + SetForScope set_block(current_block, &iter.body); + + /* The iteration variable is not normally inlined into expressions, so we + process it specially here. If the initial value causes the loop condition + to evaluate to false, then the expression can be folded. */ + iteration_var = 0; + if(iter.init_statement) { - assign_to_subscript = false; - SetForScope set(assignment_target, !assign.self_referencing); - assign.left->visit(*this); + SetFlag set_init(iteration_init); + iter.init_statement->visit(*this); } - assign.right->visit(*this); - assignment = &assign; + + if(iter.condition) + { + visit(iter.condition); + if(r_constant && r_constant_value.check_type() && !r_constant_value.value()) + { + RefPtr literal = new Literal; + literal->token = "false"; + literal->value = r_constant_value; + iter.condition = literal; + } + } + iteration_var = 0; + + iter.body.visit(*this); + if(iter.loop_expression) + visit(iter.loop_expression); +} + + +void ConstantConditionEliminator::apply(Stage &stage) +{ + stage.content.visit(*this); + NodeRemover().apply(stage, nodes_to_remove); } -void UnusedVariableLocator::record_assignment(VariableDeclaration &var, Node &node, bool chained) +ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr) { - VariableInfo &var_info = variables.back()[&var]; - if(!chained) - clear_assignments(var_info, true); - var_info.assignments.push_back(&node); - var_info.conditionally_assigned = false; + if(const Literal *literal = dynamic_cast(&expr)) + if(literal->value.check_type()) + return (literal->value.value() ? CONSTANT_TRUE : CONSTANT_FALSE); + return NOT_CONSTANT; } -void UnusedVariableLocator::clear_assignments(VariableInfo &var_info, bool mark_unused) +void ConstantConditionEliminator::visit(Block &block) { - if(mark_unused) + SetForScope set_block(current_block, &block); + for(NodeList::iterator i=block.body.begin(); i!=block.body.end(); ++i) { - for(vector::iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i) - unused_nodes.insert(*i); + insert_point = i; + (*i)->visit(*this); } - var_info.assignments.clear(); } -void UnusedVariableLocator::visit(ExpressionStatement &expr) +void ConstantConditionEliminator::visit(RefPtr &expr) +{ + r_ternary_result = 0; + expr->visit(*this); + if(r_ternary_result) + expr = r_ternary_result; + r_ternary_result = 0; +} + +void ConstantConditionEliminator::visit(TernaryExpression &ternary) { - assignment = 0; + ConstantStatus result = check_constant_condition(*ternary.condition); + if(result!=NOT_CONSTANT) + r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr); + else + r_ternary_result = 0; +} + +void ConstantConditionEliminator::visit(Conditional &cond) +{ + ConstantStatus result = check_constant_condition(*cond.condition); + if(result!=NOT_CONSTANT) + { + Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body); + // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector? + current_block->body.splice(insert_point, block.body); + nodes_to_remove.insert(&cond); + return; + } + + TraversingVisitor::visit(cond); +} + +void ConstantConditionEliminator::visit(Iteration &iter) +{ + if(iter.condition) + { + ConstantStatus result = check_constant_condition(*iter.condition); + if(result==CONSTANT_FALSE) + { + nodes_to_remove.insert(&iter); + return; + } + } + + TraversingVisitor::visit(iter); +} + + +UnreachableCodeRemover::UnreachableCodeRemover(): + reachable(true) +{ } + +bool UnreachableCodeRemover::apply(Stage &stage) +{ + stage.content.visit(*this); + NodeRemover().apply(stage, unreachable_nodes); + return !unreachable_nodes.empty(); +} + +void UnreachableCodeRemover::visit(Block &block) +{ + NodeList::iterator i = block.body.begin(); + for(; (reachable && i!=block.body.end()); ++i) + (*i)->visit(*this); + for(; i!=block.body.end(); ++i) + unreachable_nodes.insert(i->get()); +} + +void UnreachableCodeRemover::visit(FunctionDeclaration &func) +{ + TraversingVisitor::visit(func); + reachable = true; +} + +void UnreachableCodeRemover::visit(Conditional &cond) +{ + cond.body.visit(*this); + bool reachable_if_true = reachable; + reachable = true; + cond.else_body.visit(*this); + + reachable |= reachable_if_true; +} + +void UnreachableCodeRemover::visit(Iteration &iter) +{ + TraversingVisitor::visit(iter); + + /* Always consider code after a loop reachable, since there's no checking + for whether the loop executes. */ + reachable = true; +} + + +bool UnusedTypeRemover::apply(Stage &stage) +{ + stage.content.visit(*this); + NodeRemover().apply(stage, unused_nodes); + return !unused_nodes.empty(); +} + +void UnusedTypeRemover::visit(RefPtr &expr) +{ + unused_nodes.erase(expr->type); TraversingVisitor::visit(expr); - if(assignment && assignment->target_declaration) - record_assignment(*assignment->target_declaration, expr, (assignment->self_referencing || assign_to_subscript)); } -void UnusedVariableLocator::visit(StructDeclaration &strct) +void UnusedTypeRemover::visit(BasicTypeDeclaration &type) +{ + if(type.base_type) + unused_nodes.erase(type.base_type); + unused_nodes.insert(&type); +} + +void UnusedTypeRemover::visit(ImageTypeDeclaration &type) +{ + if(type.base_type) + unused_nodes.erase(type.base_type); + unused_nodes.insert(&type); +} + +void UnusedTypeRemover::visit(StructDeclaration &strct) { - SetForScope set(aggregate, &strct); unused_nodes.insert(&strct); TraversingVisitor::visit(strct); } -void UnusedVariableLocator::visit(VariableDeclaration &var) +void UnusedTypeRemover::visit(VariableDeclaration &var) { - if(aggregate) - aggregates[&var] = aggregate; - else - { - variables.back()[&var].local = true; - if(var.init_expression) - record_assignment(var, *var.init_expression, false); - } unused_nodes.erase(var.type_declaration); TraversingVisitor::visit(var); } -void UnusedVariableLocator::visit(InterfaceBlock &iface) +void UnusedTypeRemover::visit(InterfaceBlock &iface) { - SetForScope set(aggregate, &iface); - unused_nodes.insert(&iface); - TraversingVisitor::visit(iface); + unused_nodes.erase(iface.type_declaration); } -void UnusedVariableLocator::visit(FunctionDeclaration &func) +void UnusedTypeRemover::visit(FunctionDeclaration &func) +{ + unused_nodes.erase(func.return_type_declaration); + TraversingVisitor::visit(func); +} + + +UnusedVariableRemover::UnusedVariableRemover(): + stage(0), + interface_block(0), + r_assignment(0), + assignment_target(false), + r_side_effects(false), + in_struct(false), + composite_reference(false), + in_loop(0) +{ } + +bool UnusedVariableRemover::apply(Stage &s) { - variables.push_back(BlockVariableMap()); + stage = &s; + s.content.visit(*this); + + for(list::const_iterator i=assignments.begin(); i!=assignments.end(); ++i) + if(i->used_by.empty()) + unused_nodes.insert(i->node); + for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i) { - SetForScope set(global_scope, false); - for(NodeArray::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i) - (*i)->visit(*this); - func.body.visit(*this); + if(i->second.output) + { + /* The last visible assignments of output variables are used by the + next stage or the API. */ + for(vector::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j) + unused_nodes.erase((*j)->node); + } + + if(!i->second.output && !i->second.referenced) + { + // Don't remove variables from inside interface blocks. + if(!i->second.interface_block) + unused_nodes.insert(i->first); + } + else if(i->second.interface_block) + // Interface blocks are kept if even one member is used. + unused_nodes.erase(i->second.interface_block); } - BlockVariableMap &block_variables = variables.back(); - for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i) - i->second.conditionally_assigned = true; - for(NodeArray::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i) - block_variables[i->get()].referenced = true; - merge_down_variables(); + NodeRemover().apply(s, unused_nodes); + + return !unused_nodes.empty(); } -void UnusedVariableLocator::merge_down_variables() +void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node) { - BlockVariableMap &parent_variables = variables[variables.size()-2]; - BlockVariableMap &block_variables = variables.back(); - for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i) + VariableInfo &var_info = variables[target.declaration]; + var_info.referenced = true; + if(!assignment_target) { - if(i->second.local) + bool loop_external = false; + for(vector::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i) { - if(!i->second.referenced) - unused_nodes.insert(i->first); - clear_assignments(i->second, i->first->interface!="out"); - continue; + bool covered = true; + for(unsigned j=0; (covered && j<(*i)->target.chain_len && j((*i)->target.chain[j]&0xC0); + Assignment::Target::ChainType type2 = static_cast(target.chain[j]&0xC0); + if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE) + { + unsigned index1 = (*i)->target.chain[j]&0x3F; + unsigned index2 = target.chain[j]&0x3F; + if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE) + covered = index1&index2; + else if(type1==Assignment::Target::ARRAY && index1<4) + covered = index2&(1<target.chain[j]==target.chain[j]); + } + + if(covered) + { + (*i)->used_by.push_back(&node); + if((*i)->in_loopfirst); - if(j==parent_variables.end()) - parent_variables.insert(*i); - else + if(loop_external) + loop_ext_refs.push_back(&node); + } +} + +void UnusedVariableRemover::visit(VariableReference &var) +{ + if(composite_reference) + r_reference.declaration = var.declaration; + else + referenced(var.declaration, var); +} + +void UnusedVariableRemover::visit(InterfaceBlockReference &iface) +{ + if(composite_reference) + r_reference.declaration = iface.declaration; + else + referenced(iface.declaration, iface); +} + +void UnusedVariableRemover::visit_composite(Expression &expr) +{ + if(!composite_reference) + r_reference = Assignment::Target(); + + SetFlag set_composite(composite_reference); + expr.visit(*this); +} + +void UnusedVariableRemover::visit(MemberAccess &memacc) +{ + visit_composite(*memacc.left); + + add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index); + + if(!composite_reference && r_reference.declaration) + referenced(r_reference, memacc); +} + +void UnusedVariableRemover::visit(Swizzle &swizzle) +{ + visit_composite(*swizzle.left); + + unsigned mask = 0; + for(unsigned i=0; itoken[1]=='+' || unary.oper->token[1]=='-') + r_side_effects = true; +} + +void UnusedVariableRemover::visit(BinaryExpression &binary) +{ + if(binary.oper->token[0]=='[') + { + visit_composite(*binary.left); + { - if(i->second.referenced || !i->second.conditionally_assigned) - clear_assignments(j->second, !i->second.referenced); - j->second.conditionally_assigned = i->second.conditionally_assigned; - j->second.referenced |= i->second.referenced; - j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end()); + SetFlag clear_assignment(assignment_target, false); + SetFlag clear_composite(composite_reference, false); + binary.right->visit(*this); } + + add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F); + + if(!composite_reference && r_reference.declaration) + referenced(r_reference, binary); + } + else + { + SetFlag clear_composite(composite_reference, false); + TraversingVisitor::visit(binary); } - variables.pop_back(); } -void UnusedVariableLocator::visit(Conditional &cond) +void UnusedVariableRemover::visit(TernaryExpression &ternary) { - cond.condition->visit(*this); - variables.push_back(BlockVariableMap()); - cond.body.visit(*this); + SetFlag clear_composite(composite_reference, false); + TraversingVisitor::visit(ternary); +} - BlockVariableMap if_variables; - swap(variables.back(), if_variables); - cond.else_body.visit(*this); +void UnusedVariableRemover::visit(Assignment &assign) +{ + { + SetFlag set(assignment_target, (assign.oper->token[0]=='=')); + assign.left->visit(*this); + } + assign.right->visit(*this); + r_assignment = &assign; + r_side_effects = true; +} + +void UnusedVariableRemover::visit(FunctionCall &call) +{ + SetFlag clear_composite(composite_reference, false); + TraversingVisitor::visit(call); + /* Treat function calls as having side effects so expression statements + consisting of nothing but a function call won't be optimized away. */ + r_side_effects = true; + + if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex") + { + for(map::const_iterator i=variables.begin(); i!=variables.end(); ++i) + if(i->second.output) + referenced(i->first, call); + } +} - BlockVariableMap &else_variables = variables.back(); - for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i) +void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node) +{ + assignments.push_back(AssignmentInfo()); + AssignmentInfo &assign_info = assignments.back(); + assign_info.node = &node; + assign_info.target = target; + assign_info.in_loop = in_loop; + + /* An assignment to the target hides any assignments to the same target or + its subfields. */ + VariableInfo &var_info = variables[target.declaration]; + for(unsigned i=0; ifirst); - if(j!=if_variables.end()) + const Assignment::Target &t = var_info.assignments[i]->target; + + bool subfield = (t.chain_len>=target.chain_len); + for(unsigned j=0; (subfield && jtarget.declaration) + record_assignment(r_assignment->target, expr); + if(!r_side_effects) + unused_nodes.insert(&expr); +} + +void UnusedVariableRemover::visit(StructDeclaration &strct) +{ + SetFlag set_struct(in_struct); + TraversingVisitor::visit(strct); +} + +void UnusedVariableRemover::visit(VariableDeclaration &var) +{ + TraversingVisitor::visit(var); + + if(in_struct) + return; + + VariableInfo &var_info = variables[&var]; + var_info.interface_block = interface_block; + + /* Mark variables as output if they're used by the next stage or the + graphics API. */ + if(interface_block) + var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_"))); + else + var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_"))); + + if(var.init_expression) + { + var_info.initialized = true; + record_assignment(&var, *var.init_expression); + } +} + +void UnusedVariableRemover::visit(InterfaceBlock &iface) +{ + VariableInfo &var_info = variables[&iface]; + var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_"))); +} + +void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars) +{ + for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i) + { + BlockVariableMap::iterator j = variables.find(i->first); + if(j!=variables.end()) { - i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end()); - i->second.conditionally_assigned |= j->second.conditionally_assigned; - if_variables.erase(j); + /* The merged blocks started as copies of each other so any common + assignments must be in the beginning. */ + unsigned k = 0; + for(; (ksecond.assignments.size() && ksecond.assignments.size()); ++k) + if(i->second.assignments[k]!=j->second.assignments[k]) + break; + + // Remaining assignments are unique to each block; merge them. + j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end()); + j->second.referenced |= i->second.referenced; } else - i->second.conditionally_assigned = true; + variables.insert(*i); } +} + +void UnusedVariableRemover::visit(FunctionDeclaration &func) +{ + if(func.body.body.empty()) + return; - for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i) + BlockVariableMap saved_vars = variables; + // Assignments from other functions should not be visible. + for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i) + i->second.assignments.resize(i->second.initialized); + TraversingVisitor::visit(func); + swap(variables, saved_vars); + merge_variables(saved_vars); + + /* Always treat function parameters as referenced. Removing unused + parameters is not currently supported. */ + for(NodeArray::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i) { - i->second.conditionally_assigned = true; - else_variables.insert(*i); + BlockVariableMap::iterator j = variables.find(i->get()); + if(j!=variables.end()) + j->second.referenced = true; } +} - merge_down_variables(); +void UnusedVariableRemover::visit(Conditional &cond) +{ + cond.condition->visit(*this); + BlockVariableMap saved_vars = variables; + cond.body.visit(*this); + swap(saved_vars, variables); + cond.else_body.visit(*this); + + /* Visible assignments after the conditional is the union of those visible + at the end of the if and else blocks. If there was no else block, then it's + the union of the if block and the state before it. */ + merge_variables(saved_vars); } -void UnusedVariableLocator::visit(Iteration &iter) +void UnusedVariableRemover::visit(Iteration &iter) { - variables.push_back(BlockVariableMap()); - TraversingVisitor::visit(iter); + BlockVariableMap saved_vars = variables; + vector saved_refs; + swap(loop_ext_refs, saved_refs); + { + SetForScope set_loop(in_loop, in_loop+1); + TraversingVisitor::visit(iter); + } + swap(loop_ext_refs, saved_refs); - BlockVariableMap &block_variables = variables.back(); - for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i) - if(!i->second.local && i->second.referenced) - i->second.assignments.clear(); + /* Visit the external references of the loop again to record assignments + done in the loop as used. */ + for(vector::const_iterator i=saved_refs.begin(); i!=saved_refs.end(); ++i) + (*i)->visit(*this); - merge_down_variables(); + /* Merge assignments from the iteration, without clearing previous state. + Further analysis is needed to determine which parts of the iteration body + are always executed, if any. */ + merge_variables(saved_vars); } -void UnusedFunctionLocator::visit(FunctionCall &call) +bool UnusedFunctionRemover::apply(Stage &stage) +{ + stage.content.visit(*this); + NodeRemover().apply(stage, unused_nodes); + return !unused_nodes.empty(); +} + +void UnusedFunctionRemover::visit(FunctionCall &call) { TraversingVisitor::visit(call); @@ -441,7 +1426,7 @@ void UnusedFunctionLocator::visit(FunctionCall &call) used_definitions.insert(call.declaration->definition); } -void UnusedFunctionLocator::visit(FunctionDeclaration &func) +void UnusedFunctionRemover::visit(FunctionDeclaration &func) { TraversingVisitor::visit(func);