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.

diff --git a/source/programcompiler.cpp b/source/programcompiler.cpp
index 82a324dec52d8e7c9e92b8d8c56cb15264e423f3..9b3266755b0b4f36c7bdc1ebe3471ebba48e8d40 100644 (file)
--- a/source/programcompiler.cpp
+++ b/source/programcompiler.cpp
@@ -167,6 +167,9 @@ void ProgramCompiler::generate(Stage &stage)
 
 bool ProgramCompiler::optimize(Stage &stage)
 {
 
 bool ProgramCompiler::optimize(Stage &stage)
 {

+       apply<ConstantConditionEliminator>(stage);
+       apply<VariableResolver>(stage);
+

        set<Node *> unused = apply<UnusedVariableLocator>(stage);
        apply<NodeRemover>(stage, unused);
 
        set<Node *> unused = apply<UnusedVariableLocator>(stage);
        apply<NodeRemover>(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<float>(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);
+       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 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<unsigned> set(scope_level, scope_level+1);
+       for(list<NodePtr<Node> >::iterator i=block.body.begin(); i!=block.body.end(); )
+       {
+               (*i)->visit(*this);
+               if(replacement_block)
+               {
+                       for(list<NodePtr<Node> >::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<string, VariableDeclaration *>::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),
 ProgramCompiler::UnusedVariableLocator::UnusedVariableLocator():
        aggregate(0),
        assignment(0),

diff --git a/source/programcompiler.h b/source/programcompiler.h
index 0c87acf0b953a40198b60299f4288b57a0c59cbe..f585ba92347ae52e580eec7c5d42ce993fc8c483 100644 (file)
--- a/source/programcompiler.h
+++ b/source/programcompiler.h
@@ -136,6 +136,39 @@ private:
                virtual void visit(ProgramSyntax::VariableDeclaration &);
        };
 
                virtual void visit(ProgramSyntax::VariableDeclaration &);
        };
 

+       struct ExpressionEvaluator: ProgramSyntax::NodeVisitor
+       {
+               typedef std::map<ProgramSyntax::VariableDeclaration *, ProgramSyntax::Expression *> 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
        struct UnusedVariableLocator: Visitor
        {
                struct AssignmentList