From ba97b71564cadd322fe1bf3d8afe556b38ef0647 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Mon, 14 Nov 2016 15:33:45 +0200 Subject: [PATCH] Remove conditionals and loops that can be determined to never run This is the other major step required for standard shader generation. Currently the constant condition eliminator is pretty conservative and will only consider the initialization values of variables. Globals are only considered if they are declared const. --- source/programcompiler.cpp | 159 +++++++++++++++++++++++++++++++++++++ source/programcompiler.h | 33 ++++++++ 2 files changed, 192 insertions(+) diff --git a/source/programcompiler.cpp b/source/programcompiler.cpp index 82a324de..9b326675 100644 --- a/source/programcompiler.cpp +++ b/source/programcompiler.cpp @@ -167,6 +167,9 @@ void ProgramCompiler::generate(Stage &stage) bool ProgramCompiler::optimize(Stage &stage) { + apply(stage); + apply(stage); + set unused = apply(stage); apply(stage, unused); @@ -839,6 +842,162 @@ void ProgramCompiler::VariableRenamer::visit(VariableDeclaration &var) } +ProgramCompiler::ExpressionEvaluator::ExpressionEvaluator(): + variable_values(0), + result(0.0f), + result_valid(false) +{ } + +ProgramCompiler::ExpressionEvaluator::ExpressionEvaluator(const ValueMap &v): + variable_values(&v), + result(0.0f), + result_valid(false) +{ } + +void ProgramCompiler::ExpressionEvaluator::visit(Literal &literal) +{ + if(literal.token=="true") + result = 1.0f; + else if(literal.token=="false") + result = 0.0f; + else + result = lexical_cast(literal.token); + result_valid = true; +} + +void ProgramCompiler::ExpressionEvaluator::visit(VariableReference &var) +{ + if(!var.declaration) + return; + + if(variable_values) + { + ValueMap::const_iterator i = variable_values->find(var.declaration); + if(i!=variable_values->end()) + i->second->visit(*this); + } + else if(var.declaration->init_expression) + var.declaration->init_expression->visit(*this); +} + +void ProgramCompiler::ExpressionEvaluator::visit(UnaryExpression &unary) +{ + result_valid = false; + unary.expression->visit(*this); + if(!result_valid) + return; + + if(unary.oper=="!") + result = !result; + else + result_valid = false; +} + +void ProgramCompiler::ExpressionEvaluator::visit(BinaryExpression &binary) +{ + result_valid = false; + binary.left->visit(*this); + if(!result_valid) + return; + + float left_result = result; + result_valid = false; + binary.right->visit(*this); + if(!result_valid) + return; + + if(binary.oper=="<") + result = (left_result") + result = (left_result>result); + else if(binary.oper==">=") + result = (left_result>=result); + else if(binary.oper=="==") + result = (left_result==result); + else if(binary.oper=="!=") + result = (left_result!=result); + else if(binary.oper=="&&") + result = (left_result && result); + else if(binary.oper=="||") + result = (left_result || result); + else + result_valid = false; +} + + +ProgramCompiler::ConstantConditionEliminator::ConstantConditionEliminator(): + scope_level(0), + remove_node(false), + replacement_block(0) +{ } + +void ProgramCompiler::ConstantConditionEliminator::visit(Block &block) +{ + SetForScope set(scope_level, scope_level+1); + for(list >::iterator i=block.body.begin(); i!=block.body.end(); ) + { + (*i)->visit(*this); + if(replacement_block) + { + for(list >::iterator j=replacement_block->body.begin(); j!=replacement_block->body.end(); ++j) + block.body.insert(i, *j); + replacement_block = 0; + } + + if(remove_node) + block.body.erase(i++); + else + ++i; + remove_node = false; + } + + for(map::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i) + variable_values.erase(i->second); +} + +void ProgramCompiler::ConstantConditionEliminator::visit(Assignment &assign) +{ + variable_values.erase(assign.target_declaration); +} + +void ProgramCompiler::ConstantConditionEliminator::visit(VariableDeclaration &var) +{ + if(var.constant || scope_level>1) + variable_values[&var] = &*var.init_expression; +} + +void ProgramCompiler::ConstantConditionEliminator::visit(Conditional &cond) +{ + ExpressionEvaluator eval(variable_values); + cond.condition->visit(eval); + if(eval.result_valid) + { + remove_node = true; + replacement_block = (eval.result ? &cond.body : &cond.else_body); + } + else + TraversingVisitor::visit(cond); +} + +void ProgramCompiler::ConstantConditionEliminator::visit(Iteration &iter) +{ + if(iter.condition) + { + ExpressionEvaluator eval; + iter.condition->visit(eval); + if(eval.result_valid && !eval.result) + { + remove_node = true; + return; + } + } + + TraversingVisitor::visit(iter); +} + + ProgramCompiler::UnusedVariableLocator::UnusedVariableLocator(): aggregate(0), assignment(0), diff --git a/source/programcompiler.h b/source/programcompiler.h index 0c87acf0..f585ba92 100644 --- a/source/programcompiler.h +++ b/source/programcompiler.h @@ -136,6 +136,39 @@ private: virtual void visit(ProgramSyntax::VariableDeclaration &); }; + struct ExpressionEvaluator: ProgramSyntax::NodeVisitor + { + typedef std::map ValueMap; + + const ValueMap *variable_values; + float result; + bool result_valid; + + ExpressionEvaluator(); + ExpressionEvaluator(const ValueMap &); + + virtual void visit(ProgramSyntax::Literal &); + virtual void visit(ProgramSyntax::VariableReference &); + virtual void visit(ProgramSyntax::UnaryExpression &); + virtual void visit(ProgramSyntax::BinaryExpression &); + }; + + struct ConstantConditionEliminator: Visitor + { + unsigned scope_level; + ExpressionEvaluator::ValueMap variable_values; + bool remove_node; + ProgramSyntax::Block *replacement_block; + + ConstantConditionEliminator(); + + virtual void visit(ProgramSyntax::Block &); + virtual void visit(ProgramSyntax::Assignment &); + virtual void visit(ProgramSyntax::VariableDeclaration &); + virtual void visit(ProgramSyntax::Conditional &); + virtual void visit(ProgramSyntax::Iteration &); + }; + struct UnusedVariableLocator: Visitor { struct AssignmentList -- 2.45.2