From 1cd0ea7f79b2b0dedd8a2a6622e5d2e8b2ea2512 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Thu, 4 Mar 2021 01:05:22 +0200 Subject: [PATCH] Add expression inlining --- source/glsl/compiler.cpp | 1 + source/glsl/optimize.cpp | 314 ++++++++++++++++++++++++++++++++------- source/glsl/optimize.h | 57 ++++++- 3 files changed, 313 insertions(+), 59 deletions(-) diff --git a/source/glsl/compiler.cpp b/source/glsl/compiler.cpp index 1eeb3625..7ff589e7 100644 --- a/source/glsl/compiler.cpp +++ b/source/glsl/compiler.cpp @@ -244,6 +244,7 @@ Compiler::OptimizeResult Compiler::optimize(Stage &stage) ConstantConditionEliminator().apply(stage); bool any_inlined = FunctionInliner().apply(stage); + any_inlined |= ExpressionInliner().apply(stage); if(any_inlined) { VariableResolver().apply(stage); diff --git a/source/glsl/optimize.cpp b/source/glsl/optimize.cpp index a7786295..a999a654 100644 --- a/source/glsl/optimize.cpp +++ b/source/glsl/optimize.cpp @@ -304,66 +304,286 @@ void FunctionInliner::visit(Return &ret) } -ConstantConditionEliminator::ConstantConditionEliminator(): - record_only(false) +ExpressionInliner::ExpressionInfo::ExpressionInfo(): + expression(0), + assign_scope(0), + inline_point(0), + inner_oper(0), + outer_oper(0), + inline_on_rhs(false), + trivial(false), + available(true) { } -void ConstantConditionEliminator::apply(Stage &stage) + +ExpressionInliner::ExpressionInliner(): + r_ref_info(0), + r_any_inlined(false), + r_trivial(false), + mutating(false), + iteration_init(false), + iteration_body(0), + r_oper(0) +{ } + +bool ExpressionInliner::apply(Stage &s) { - stage.content.visit(*this); - NodeRemover().apply(stage, nodes_to_remove); + s.content.visit(*this); + return r_any_inlined; } -void ConstantConditionEliminator::visit(Block &block) +void ExpressionInliner::visit_and_record(RefPtr &ptr, const Operator *outer_oper, bool on_rhs) { - SetForScope set_block(current_block, &block); - for(NodeList::iterator i=block.body.begin(); i!=block.body.end(); ++i) + r_ref_info = 0; + ptr->visit(*this); + if(r_ref_info && r_ref_info->expression && r_ref_info->available) { - insert_point = i; - (*i)->visit(*this); + 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; + } + + r_ref_info->outer_oper = outer_oper; + if(r_ref_info->trivial) + inline_expression(*r_ref_info->expression, ptr, outer_oper, r_ref_info->inner_oper, on_rhs); + 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 = &ptr; + r_ref_info->inline_on_rhs = on_rhs; + } + } +} + +void ExpressionInliner::inline_expression(Expression &expr, RefPtr &ptr, const Operator *outer_oper, const Operator *inner_oper, bool on_rhs) +{ + unsigned outer_precedence = (outer_oper ? outer_oper->precedence : 20); + unsigned inner_precedence = (inner_oper ? inner_oper->precedence : 0); + + bool needs_parentheses = (inner_precedence>=outer_precedence); + if(inner_oper && inner_oper==outer_oper) + // Omit parentheses if the operator's natural grouping works out. + needs_parentheses = (inner_oper->assoc!=Operator::ASSOCIATIVE && on_rhs!=(inner_oper->assoc==Operator::RIGHT_TO_LEFT)); + + if(needs_parentheses) + { + RefPtr parexpr = new ParenthesizedExpression; + parexpr->expression = expr.clone(); + ptr = parexpr; + } + else + ptr = expr.clone(); + + r_any_inlined = true; +} + +void ExpressionInliner::visit(Block &block) +{ + TraversingVisitor::visit(block); + + for(map::iterator i=expressions.begin(); i!=expressions.end(); ) + { + map::iterator j = block.variables.find(i->first->name); + if(j!=block.variables.end() && j->second==i->first) + { + if(i->second.expression && i->second.inline_point) + inline_expression(*i->second.expression, *i->second.inline_point, i->second.outer_oper, i->second.inner_oper, i->second.inline_on_rhs); + + expressions.erase(i++); + } + else + { + /* The expression was assigned in this block and may depend on local + variables of the block. If this is a conditionally executed block, + the assignment might not always happen. Mark the expression as not + available to any outer blocks. */ + if(i->second.assign_scope==&block) + i->second.available = false; + + ++i; + } } +} - for(map::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i) - variable_values.erase(i->second); +void ExpressionInliner::visit(VariableReference &var) +{ + if(var.declaration) + { + map::iterator i = expressions.find(var.declaration); + if(i!=expressions.end()) + { + /* 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; + } + } +} + +void ExpressionInliner::visit(MemberAccess &memacc) +{ + visit_and_record(memacc.left, memacc.oper, false); + r_ref_info = 0; + r_oper = memacc.oper; + r_trivial = false; } -void ConstantConditionEliminator::visit(UnaryExpression &unary) +void ExpressionInliner::visit(UnaryExpression &unary) { - if(VariableReference *var = dynamic_cast(unary.expression.get())) - if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-') - variable_values.erase(var->declaration); + SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-'); + visit_and_record(unary.expression, unary.oper, false); + r_ref_info = 0; + r_oper = unary.oper; + r_trivial = false; } -void ConstantConditionEliminator::visit(Assignment &assign) +void ExpressionInliner::visit(BinaryExpression &binary) { - variable_values.erase(assign.target_declaration); + visit_and_record(binary.left, binary.oper, false); + { + SetFlag clear_target(mutating, false); + visit_and_record(binary.right, binary.oper, true); + } + r_ref_info = 0; + r_oper = binary.oper; + r_trivial = false; } -void ConstantConditionEliminator::visit(VariableDeclaration &var) +void ExpressionInliner::visit(Assignment &assign) { + { + SetFlag set_target(mutating); + visit_and_record(assign.left, assign.oper, false); + } + r_oper = 0; + visit_and_record(assign.right, assign.oper, true); + + if(assign.target_declaration) + { + map::iterator i = expressions.find(assign.target_declaration); + 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.inner_oper = r_oper; + i->second.available = true; + } + } + + r_ref_info = 0; + r_oper = assign.oper; + r_trivial = false; +} + +void ExpressionInliner::visit(FunctionCall &call) +{ + for(NodeArray::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i) + visit_and_record(*i, 0, false); + r_ref_info = 0; + r_oper = 0; + r_trivial = false; +} + +void ExpressionInliner::visit(VariableDeclaration &var) +{ + r_oper = 0; + r_trivial = true; + if(var.init_expression) + visit_and_record(var.init_expression, 0, false); + 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"); } - if((constant || current_block->parent) && var.init_expression) - variable_values[&var] = var.init_expression.get(); + + /* 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.inner_oper = r_oper; + info.trivial = r_trivial; + } +} + +void ExpressionInliner::visit(Conditional &cond) +{ + visit_and_record(cond.condition, 0, false); + cond.body.visit(*this); +} + +void ExpressionInliner::visit(Iteration &iter) +{ + SetForScope set_block(current_block, &iter.body); + if(iter.init_statement) + { + SetFlag set_init(iteration_init); + iter.init_statement->visit(*this); + } + + SetForScope set_body(iteration_body, &iter.body); + if(iter.condition) + iter.condition->visit(*this); + iter.body.visit(*this); + if(iter.loop_expression) + iter.loop_expression->visit(*this); +} + +void ExpressionInliner::visit(Return &ret) +{ + if(ret.expression) + visit_and_record(ret.expression, 0, false); +} + + +void ConstantConditionEliminator::apply(Stage &stage) +{ + stage.content.visit(*this); + NodeRemover().apply(stage, nodes_to_remove); +} + +void ConstantConditionEliminator::visit(Block &block) +{ + SetForScope set_block(current_block, &block); + for(NodeList::iterator i=block.body.begin(); i!=block.body.end(); ++i) + { + insert_point = i; + (*i)->visit(*this); + } } void ConstantConditionEliminator::visit(Conditional &cond) { - if(!record_only) + ExpressionEvaluator eval; + cond.condition->visit(eval); + if(eval.is_result_valid()) { - ExpressionEvaluator eval(variable_values); - cond.condition->visit(eval); - if(eval.is_result_valid()) - { - Block &block = (eval.get_result() ? cond.body : cond.else_body); - current_block->body.splice(insert_point, block.body); - nodes_to_remove.insert(&cond); - return; - } + Block &block = (eval.get_result() ? cond.body : cond.else_body); + current_block->body.splice(insert_point, block.body); + nodes_to_remove.insert(&cond); + return; } TraversingVisitor::visit(cond); @@ -371,33 +591,23 @@ void ConstantConditionEliminator::visit(Conditional &cond) void ConstantConditionEliminator::visit(Iteration &iter) { - if(!record_only) + if(iter.condition) { - if(iter.condition) + /* If the loop condition is always false on the first iteration, the + entire loop can be removed */ + ExpressionEvaluator::ValueMap values; + if(VariableDeclaration *var = dynamic_cast(iter.init_statement.get())) + values[var] = var->init_expression.get(); + ExpressionEvaluator eval(values); + iter.condition->visit(eval); + if(eval.is_result_valid() && !eval.get_result()) { - /* 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()) - { - nodes_to_remove.insert(&iter); - return; - } + nodes_to_remove.insert(&iter); + return; } - - /* 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); } TraversingVisitor::visit(iter); - - if(VariableDeclaration *init_decl = dynamic_cast(iter.init_statement.get())) - variable_values.erase(init_decl); } diff --git a/source/glsl/optimize.h b/source/glsl/optimize.h index 28f5e876..c932767e 100644 --- a/source/glsl/optimize.h +++ b/source/glsl/optimize.h @@ -98,26 +98,69 @@ private: virtual void visit(Return &); }; +/** Inlines variables into expressions. Variables with trivial values (those +consisting of a single literal or variable reference) are always inlined. +Variables which are only referenced once are also inlined. */ +class ExpressionInliner: private TraversingVisitor +{ +private: + struct ExpressionInfo + { + Expression *expression; + Block *assign_scope; + RefPtr *inline_point; + const Operator *inner_oper; + const Operator *outer_oper; + bool inline_on_rhs; + bool trivial; + bool available; + + ExpressionInfo(); + }; + + std::map expressions; + ExpressionInfo *r_ref_info; + bool r_any_inlined; + bool r_trivial; + bool mutating; + bool iteration_init; + Block *iteration_body; + const Operator *r_oper; + +public: + ExpressionInliner(); + + bool apply(Stage &); + +private: + void visit_and_record(RefPtr &, const Operator *, bool); + void inline_expression(Expression &, RefPtr &, const Operator *, const Operator *, bool); + virtual void visit(Block &); + virtual void visit(VariableReference &); + virtual void visit(MemberAccess &); + virtual void visit(UnaryExpression &); + virtual void visit(BinaryExpression &); + virtual void visit(Assignment &); + virtual void visit(FunctionCall &); + virtual void visit(VariableDeclaration &); + virtual void visit(Conditional &); + virtual void visit(Iteration &); + virtual void visit(Return &); +}; + /** Removes conditional statements and loops where the condition can be determined as constant at compile time. */ class ConstantConditionEliminator: private TraversingVisitor { private: - bool record_only; - ExpressionEvaluator::ValueMap variable_values; NodeList::iterator insert_point; std::set nodes_to_remove; public: - ConstantConditionEliminator(); - void apply(Stage &); private: virtual void visit(Block &); - virtual void visit(UnaryExpression &); - virtual void visit(Assignment &); - virtual void visit(VariableDeclaration &); virtual void visit(Conditional &); virtual void visit(Iteration &); }; -- 2.43.0