From 7fd67c4a1ed1c04b09c4bf58489a34809017ba8b Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Thu, 22 Apr 2021 15:10:21 +0300 Subject: [PATCH] Redesign ExpressionInliner Similarly to the rewrite of UnusedVariableRemover from d230392, it now analyzes the entire stage before inlining anything. This approach is more robust and easier to debug. The inliner can now inline into the right side of an assignment even if the left side references the same variable. --- source/glsl/optimize.cpp | 135 +++++++++++++++---------------- source/glsl/optimize.h | 26 +++--- tests/glsl/binary_operators.glsl | 19 +---- tests/glsl/unary_operators.glsl | 4 +- 4 files changed, 88 insertions(+), 96 deletions(-) diff --git a/source/glsl/optimize.cpp b/source/glsl/optimize.cpp index 55e5da5f..2e7f8aa7 100644 --- a/source/glsl/optimize.cpp +++ b/source/glsl/optimize.cpp @@ -351,9 +351,9 @@ void FunctionInliner::visit(Iteration &iter) ExpressionInliner::ExpressionInliner(): r_ref_info(0), - r_any_inlined(false), r_trivial(false), - mutating(false), + access_read(true), + access_write(false), iteration_init(false), iteration_body(0), r_oper(0) @@ -362,62 +362,48 @@ ExpressionInliner::ExpressionInliner(): bool ExpressionInliner::apply(Stage &s) { s.content.visit(*this); - return r_any_inlined; -} - -void ExpressionInliner::inline_expression(Expression &expr, RefPtr &ptr) -{ - ptr = expr.clone(); - r_any_inlined = true; -} - -void ExpressionInliner::visit(Block &block) -{ - 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); ) + bool any_inlined = false; + for(list::iterator i=expressions.begin(); i!=expressions.end(); ++i) + if(i->expression && (i->trivial || i->uses.size()==1)) { - if(j->second.expression && j->second.inline_point) - inline_expression(*j->second.expression, *j->second.inline_point); - - expressions.erase(j++); + for(vector::iterator j=i->uses.begin(); j!=i->uses.end(); ++j) + if(!j->blocked) + { + *j->reference = i->expression->clone(); + any_inlined = true; + } } - } - /* 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; + return any_inlined; } void ExpressionInliner::visit(RefPtr &expr) { r_ref_info = 0; expr->visit(*this); - if(r_ref_info && r_ref_info->expression && r_ref_info->available) + if(r_ref_info && r_ref_info->expression) { + ExpressionUse use; + use.reference = &expr; + use.ref_scope = current_block; + use.blocked = access_write; + 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 + /* Block inlining of non-trivial expressions 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; + for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent) + use.blocked = (i==r_ref_info->assign_scope); } - 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; + /* Block inlining assignments from from inner scopes. The assignment may + depend on local variables of that scope or may not always be executed. */ + for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent) + use.blocked = (i==current_block); + + r_ref_info->uses.push_back(use); } r_oper = expr->oper; r_ref_info = 0; @@ -425,21 +411,11 @@ void ExpressionInliner::visit(RefPtr &expr) void ExpressionInliner::visit(VariableReference &var) { - if(var.declaration) + if(var.declaration && access_read) { - 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; - } + map::iterator i = assignments.find(var.declaration); + if(i!=assignments.end()) + r_ref_info = i->second; } } @@ -457,7 +433,7 @@ void ExpressionInliner::visit(Swizzle &swizzle) void ExpressionInliner::visit(UnaryExpression &unary) { - SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-'); + SetFlag set_write(access_write, access_write || unary.oper->token[1]=='+' || unary.oper->token[1]=='-'); visit(unary.expression); r_trivial = false; } @@ -466,7 +442,7 @@ void ExpressionInliner::visit(BinaryExpression &binary) { visit(binary.left); { - SetFlag clear_target(mutating, false); + SetFlag clear_write(access_write, false); visit(binary.right); } r_trivial = false; @@ -475,21 +451,37 @@ void ExpressionInliner::visit(BinaryExpression &binary) void ExpressionInliner::visit(Assignment &assign) { { - SetFlag set_target(mutating); + SetFlag set_read(access_read, assign.oper->token[0]!='='); + SetFlag set_write(access_write); visit(assign.left); } r_oper = 0; + r_trivial = true; visit(assign.right); - map::iterator i = expressions.find(assign.target); - if(i!=expressions.end()) + map::iterator i = assignments.find(assign.target); + if(i!=assignments.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(iteration_body && i->second->expression) + { + /* Block inlining into previous references within the iteration + statement. On iterations after the first they would refer to the + assignment within the iteration. */ + for(vector::iterator j=i->second->uses.begin(); j!=i->second->uses.end(); ++j) + for(Block *k=j->ref_scope; (!j->blocked && k); k=k->parent) + j->blocked = (k==iteration_body); + } + + expressions.push_back(ExpressionInfo()); + ExpressionInfo &info = expressions.back(); + info.target = assign.target; + // Self-referencing assignments can't be inlined without additional work. + if(!assign.self_referencing) + info.expression = assign.right; + info.assign_scope = current_block; + info.trivial = r_trivial; + + i->second = &info; } r_trivial = false; @@ -527,12 +519,17 @@ void ExpressionInliner::visit(VariableDeclaration &var) analyze and non-trivial expressions could be expensive to inline. */ if((current_block->parent || (constant && r_trivial)) && var.interface.empty()) { - ExpressionInfo &info = expressions[&var]; + expressions.push_back(ExpressionInfo()); + ExpressionInfo &info = expressions.back(); + info.target = &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()); + if(!iteration_init) + info.expression = var.init_expression; info.assign_scope = current_block; info.trivial = r_trivial; + + assignments[&var] = &info; } } diff --git a/source/glsl/optimize.h b/source/glsl/optimize.h index 6d8a6194..6250130f 100644 --- a/source/glsl/optimize.h +++ b/source/glsl/optimize.h @@ -116,22 +116,32 @@ Variables which are only referenced once are also inlined. */ class ExpressionInliner: private TraversingVisitor { private: + struct ExpressionUse + { + RefPtr *reference; + Block *ref_scope; + bool blocked; + + ExpressionUse(): reference(0), ref_scope(0), blocked(false) { } + }; + struct ExpressionInfo { - Expression *expression; + Assignment::Target target; + RefPtr expression; Block *assign_scope; - RefPtr *inline_point; + std::vector uses; bool trivial; - bool available; - ExpressionInfo(): expression(0), assign_scope(0), inline_point(0), trivial(false), available(true) { } + ExpressionInfo(): expression(0), assign_scope(0), trivial(false) { } }; - std::map expressions; + std::list expressions; + std::map assignments; ExpressionInfo *r_ref_info; - bool r_any_inlined; bool r_trivial; - bool mutating; + bool access_read; + bool access_write; bool iteration_init; Block *iteration_body; const Operator *r_oper; @@ -142,8 +152,6 @@ public: bool apply(Stage &); private: - void inline_expression(Expression &, RefPtr &); - virtual void visit(Block &); virtual void visit(RefPtr &); virtual void visit(VariableReference &); virtual void visit(MemberAccess &); diff --git a/tests/glsl/binary_operators.glsl b/tests/glsl/binary_operators.glsl index edf36ebb..a67a5a72 100644 --- a/tests/glsl/binary_operators.glsl +++ b/tests/glsl/binary_operators.glsl @@ -1,7 +1,7 @@ #pragma MSP stage(vertex) void main() { - int i = 0; + int i = 5; i = i-3; float f = 0; f = i+1; @@ -34,26 +34,13 @@ void main() /* Expected output: vertex void main() { - int i = 0; - i = i-3; - float f; - f = float(i+1); - f = (f+float(i))*(f/float(i)); - bool b = float(i)=f; - b = b&&float(i)==f; - int j = 1; - i = i|1; - j = j<>ivec2(i); + iv = iv>>ivec2(768); mat4x2 m1; mat2x4 m2; vec4 v1 = vec4(1.0); vec2 v3; v3 = v1*m2+(m2*m1*5.0*v1).xy+vec2(iv); - if(b) - ++v3; + ++v3; } */ diff --git a/tests/glsl/unary_operators.glsl b/tests/glsl/unary_operators.glsl index a04d24f7..bd9803b2 100644 --- a/tests/glsl/unary_operators.glsl +++ b/tests/glsl/unary_operators.glsl @@ -16,8 +16,8 @@ void main() /* Expected output: vertex void main() { - int i = 0; - i = -~i; + int i; + i = 1; ++i; --i; i++; -- 2.43.0