From 2b073e0a3808f8ece4b93669395e4b812214cf5d Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Sun, 13 Nov 2016 23:39:45 +0200 Subject: [PATCH] Overhaul assignment tracking to work properly with conditionals --- source/programcompiler.cpp | 253 +++++++++++++++++++++++++++---------- source/programcompiler.h | 30 ++++- source/programparser.cpp | 3 +- source/programsyntax.cpp | 19 ++- source/programsyntax.h | 15 ++- 5 files changed, 237 insertions(+), 83 deletions(-) diff --git a/source/programcompiler.cpp b/source/programcompiler.cpp index 2bb26946..fdbc83c7 100644 --- a/source/programcompiler.cpp +++ b/source/programcompiler.cpp @@ -209,14 +209,18 @@ void ProgramCompiler::Formatter::visit(UnaryExpression &unary) void ProgramCompiler::Formatter::visit(BinaryExpression &binary) { binary.left->visit(*this); - if(binary.assignment) - formatted += format(" %s ", binary.oper); - else - formatted += binary.oper; + formatted += binary.oper; binary.right->visit(*this); formatted += binary.after; } +void ProgramCompiler::Formatter::visit(Assignment &assign) +{ + assign.left->visit(*this); + formatted += format(" %s ", assign.oper); + assign.right->visit(*this); +} + void ProgramCompiler::Formatter::visit(FunctionCall &call) { formatted += format("%s(", call.name); @@ -380,7 +384,10 @@ void ProgramCompiler::Formatter::visit(Return &ret) ProgramCompiler::VariableResolver::VariableResolver(): - anonymous(false) + anonymous(false), + record_target(false), + assignment_target(0), + self_referencing(false) { } void ProgramCompiler::VariableResolver::apply(Stage &s) @@ -417,6 +424,19 @@ void ProgramCompiler::VariableResolver::visit(VariableReference &var) break; } } + + if(record_target) + { + if(assignment_target) + { + record_target = false; + assignment_target = 0; + } + else + assignment_target = var.declaration; + } + else if(var.declaration && var.declaration==assignment_target) + self_referencing = true; } void ProgramCompiler::VariableResolver::visit(MemberAccess &memacc) @@ -441,7 +461,10 @@ void ProgramCompiler::VariableResolver::visit(BinaryExpression &binary) { if(binary.oper=="[") { - binary.right->visit(*this); + { + SetForScope set(record_target, false); + binary.right->visit(*this); + } type = 0; binary.left->visit(*this); } @@ -452,6 +475,21 @@ void ProgramCompiler::VariableResolver::visit(BinaryExpression &binary) } } +void ProgramCompiler::VariableResolver::visit(Assignment &assign) +{ + { + SetFlag set(record_target); + assignment_target = 0; + assign.left->visit(*this); + } + + self_referencing = false; + assign.right->visit(*this); + + assign.self_referencing = (self_referencing || assign.oper!="="); + assign.target_declaration = assignment_target; +} + void ProgramCompiler::VariableResolver::visit(StructDeclaration &strct) { TraversingVisitor::visit(strct); @@ -571,13 +609,12 @@ bool ProgramCompiler::InterfaceGenerator::generate_interface(VariableDeclaration void ProgramCompiler::InterfaceGenerator::insert_assignment(const string &left, ProgramSyntax::Expression *right) { - BinaryExpression *assign = new BinaryExpression; + Assignment *assign = new Assignment; VariableReference *ref = new VariableReference; ref->name = left; assign->left = ref; assign->oper = "="; assign->right = right; - assign->assignment = true; ExpressionStatement *stmt = new ExpressionStatement; stmt->expression = assign; @@ -714,40 +751,40 @@ void ProgramCompiler::VariableRenamer::visit(VariableDeclaration &var) ProgramCompiler::UnusedVariableLocator::UnusedVariableLocator(): aggregate(0), - assignment(false), - record_target(false), - assignment_target(0), - indeterminate_target(false), - self_referencing(false) + assignment(0), + assignment_target(false) { } -void ProgramCompiler::UnusedVariableLocator::visit(VariableReference &var) +void ProgramCompiler::UnusedVariableLocator::apply(Stage &s) { - if(record_target) - { - if(assignment_target) - indeterminate_target = true; - else - assignment_target = var.declaration; - } - else - { - unused_nodes.erase(var.declaration); - - map::iterator i = assignments.find(var.declaration); - if(i!=assignments.end()) - { - unused_nodes.erase(i->second); - assignments.erase(i); - } + assignments.push_back(BlockAssignmentMap()); + Visitor::apply(s); + assignments.pop_back(); +} - if(assignment && var.declaration==assignment_target) - self_referencing = true; - } +void ProgramCompiler::UnusedVariableLocator::visit(VariableReference &var) +{ + unused_nodes.erase(var.declaration); map::iterator i = aggregates.find(var.declaration); if(i!=aggregates.end()) unused_nodes.erase(i->second); + + if(assignment_target) + return; + + for(vector::iterator j=assignments.end(); j!=assignments.begin(); ) + { + --j; + BlockAssignmentMap::iterator k = j->find(var.declaration); + if(k!=j->end()) + { + for(vector::iterator l=k->second.nodes.begin(); l!=k->second.nodes.end(); ++l) + unused_nodes.erase(*l); + j->erase(k); + break; + } + } } void ProgramCompiler::UnusedVariableLocator::visit(MemberAccess &memacc) @@ -758,48 +795,44 @@ void ProgramCompiler::UnusedVariableLocator::visit(MemberAccess &memacc) void ProgramCompiler::UnusedVariableLocator::visit(BinaryExpression &binary) { - if(binary.assignment) - { - assignment = true; - { - SetFlag set(record_target); - binary.left->visit(*this); - } - if(binary.oper!="=") - self_referencing = true; - binary.right->visit(*this); - } - else if(record_target && binary.oper=="[") + if(binary.oper=="[") { binary.left->visit(*this); - SetForScope set(record_target, false); + SetForScope set(assignment_target, false); binary.right->visit(*this); } else TraversingVisitor::visit(binary); } +void ProgramCompiler::UnusedVariableLocator::visit(Assignment &assign) +{ + { + SetForScope set(assignment_target, !assign.self_referencing); + assign.left->visit(*this); + } + assign.right->visit(*this); + assignment = &assign; +} + +void ProgramCompiler::UnusedVariableLocator::record_assignment(VariableDeclaration &var, Node &node, bool self_ref) +{ + unused_nodes.insert(&node); + BlockAssignmentMap &block_assignments = assignments.back(); + AssignmentList &var_assignments = block_assignments[&var]; + if(!self_ref) + var_assignments.nodes.clear(); + var_assignments.nodes.push_back(&node); + var_assignments.conditional = false; + var_assignments.self_referencing = self_ref; +} + void ProgramCompiler::UnusedVariableLocator::visit(ExpressionStatement &expr) { - assignment = false; - assignment_target = 0; - indeterminate_target = false; - self_referencing = false; + assignment = 0; TraversingVisitor::visit(expr); - if(assignment && assignment_target && !indeterminate_target) - { - Node *&assign = assignments[assignment_target]; - if(self_referencing) - unused_nodes.erase(assign); - else if(assign) - unused_nodes.insert(assign); - assign = &expr; - if(assignment_target->interface=="out" && (stage->type==FRAGMENT || assignment_target->linked_declaration)) - unused_nodes.erase(assignment_target); - else - unused_nodes.insert(&expr); - } - assignment = false; + if(assignment && assignment->target_declaration) + record_assignment(*assignment->target_declaration, expr, assignment->self_referencing); } void ProgramCompiler::UnusedVariableLocator::visit(StructDeclaration &strct) @@ -817,10 +850,7 @@ void ProgramCompiler::UnusedVariableLocator::visit(VariableDeclaration &var) { unused_nodes.insert(&var); if(var.init_expression) - { - unused_nodes.insert(&*var.init_expression); - assignments[&var] = &*var.init_expression; - } + record_assignment(var, *var.init_expression, false); } unused_nodes.erase(var.type_declaration); TraversingVisitor::visit(var); @@ -833,6 +863,91 @@ void ProgramCompiler::UnusedVariableLocator::visit(InterfaceBlock &iface) TraversingVisitor::visit(iface); } +void ProgramCompiler::UnusedVariableLocator::visit(FunctionDeclaration &func) +{ + assignments.push_back(BlockAssignmentMap()); + + for(vector >::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i) + (*i)->visit(*this); + func.body.visit(*this); + + BlockAssignmentMap &block_assignments = assignments.back(); + for(map::iterator i=func.body.variables.begin(); i!=func.body.variables.end(); ++i) + block_assignments.erase(i->second); + for(BlockAssignmentMap::iterator i=block_assignments.begin(); i!=block_assignments.end(); ++i) + { + if(i->first->interface=="out" && stage->type!=FRAGMENT && !i->first->linked_declaration) + continue; + + for(vector::iterator j=i->second.nodes.begin(); j!=i->second.nodes.end(); ++j) + unused_nodes.erase(*j); + } + + assignments.pop_back(); +} + +void ProgramCompiler::UnusedVariableLocator::merge_down_assignments() +{ + BlockAssignmentMap &parent_assignments = assignments[assignments.size()-2]; + BlockAssignmentMap &block_assignments = assignments.back(); + for(BlockAssignmentMap::iterator i=block_assignments.begin(); i!=block_assignments.end(); ++i) + { + BlockAssignmentMap::iterator j = parent_assignments.find(i->first); + if(j==parent_assignments.end()) + parent_assignments.insert(*i); + else if(i->second.self_referencing || i->second.conditional) + { + j->second.nodes.insert(j->second.nodes.end(), i->second.nodes.begin(), i->second.nodes.end()); + j->second.conditional |= i->second.conditional; + j->second.self_referencing |= i->second.self_referencing; + } + else + j->second = i->second; + } + assignments.pop_back(); +} + +void ProgramCompiler::UnusedVariableLocator::visit(Conditional &cond) +{ + cond.condition->visit(*this); + assignments.push_back(BlockAssignmentMap()); + cond.body.visit(*this); + + BlockAssignmentMap if_assignments; + swap(assignments.back(), if_assignments); + cond.else_body.visit(*this); + + BlockAssignmentMap &else_assignments = assignments.back(); + for(BlockAssignmentMap::iterator i=else_assignments.begin(); i!=else_assignments.end(); ++i) + { + BlockAssignmentMap::iterator j = if_assignments.find(i->first); + if(j!=if_assignments.end()) + { + i->second.nodes.insert(i->second.nodes.end(), j->second.nodes.begin(), j->second.nodes.end()); + i->second.conditional |= j->second.conditional; + i->second.self_referencing |= j->second.self_referencing; + if_assignments.erase(j); + } + else + i->second.conditional = true; + } + + for(BlockAssignmentMap::iterator i=if_assignments.begin(); i!=if_assignments.end(); ++i) + { + i->second.conditional = true; + else_assignments.insert(*i); + } + + merge_down_assignments(); +} + +void ProgramCompiler::UnusedVariableLocator::visit(Iteration &iter) +{ + assignments.push_back(BlockAssignmentMap()); + TraversingVisitor::visit(iter); + merge_down_assignments(); +} + void ProgramCompiler::NodeRemover::visit(Block &block) { diff --git a/source/programcompiler.h b/source/programcompiler.h index 695c2e26..1c76d63f 100644 --- a/source/programcompiler.h +++ b/source/programcompiler.h @@ -39,6 +39,7 @@ private: virtual void visit(ProgramSyntax::MemberAccess &); virtual void visit(ProgramSyntax::UnaryExpression &); virtual void visit(ProgramSyntax::BinaryExpression &); + virtual void visit(ProgramSyntax::Assignment &); virtual void visit(ProgramSyntax::FunctionCall &); virtual void visit(ProgramSyntax::ExpressionStatement &); virtual void visit(ProgramSyntax::Layout &); @@ -57,6 +58,9 @@ private: ProgramSyntax::StructDeclaration *type; bool anonymous; std::string block_interface; + bool record_target; + ProgramSyntax::VariableDeclaration *assignment_target; + bool self_referencing; VariableResolver(); @@ -65,6 +69,7 @@ private: virtual void visit(ProgramSyntax::VariableReference &); virtual void visit(ProgramSyntax::MemberAccess &); virtual void visit(ProgramSyntax::BinaryExpression &); + virtual void visit(ProgramSyntax::Assignment &); virtual void visit(ProgramSyntax::StructDeclaration &); virtual void visit(ProgramSyntax::VariableDeclaration &); virtual void visit(ProgramSyntax::InterfaceBlock &); @@ -100,25 +105,38 @@ private: struct UnusedVariableLocator: Visitor { + struct AssignmentList + { + std::vector nodes; + bool conditional; + bool self_referencing; + }; + + typedef std::map BlockAssignmentMap; + std::set unused_nodes; std::map aggregates; ProgramSyntax::Node *aggregate; - std::map assignments; - bool assignment; - bool record_target; - ProgramSyntax::VariableDeclaration *assignment_target; - bool indeterminate_target; - bool self_referencing; + std::vector assignments; + ProgramSyntax::Assignment *assignment; + bool assignment_target; UnusedVariableLocator(); + virtual void apply(ProgramSyntax::Stage &); virtual void visit(ProgramSyntax::VariableReference &); virtual void visit(ProgramSyntax::MemberAccess &); virtual void visit(ProgramSyntax::BinaryExpression &); + virtual void visit(ProgramSyntax::Assignment &); + void record_assignment(ProgramSyntax::VariableDeclaration &, ProgramSyntax::Node &, bool); virtual void visit(ProgramSyntax::ExpressionStatement &); virtual void visit(ProgramSyntax::StructDeclaration &); virtual void visit(ProgramSyntax::VariableDeclaration &); virtual void visit(ProgramSyntax::InterfaceBlock &); + virtual void visit(ProgramSyntax::FunctionDeclaration &); + void merge_down_assignments(); + virtual void visit(ProgramSyntax::Conditional &); + virtual void visit(ProgramSyntax::Iteration &); }; struct NodeRemover: Visitor diff --git a/source/programparser.cpp b/source/programparser.cpp index 11c9a9fe..f003a835 100644 --- a/source/programparser.cpp +++ b/source/programparser.cpp @@ -522,7 +522,7 @@ Expression *ProgramParser::parse_expression(unsigned precedence) BinaryExpression *ProgramParser::parse_binary(Expression *left, const Operator *oper) { - RefPtr binary = new BinaryExpression; + RefPtr binary = (oper->precedence==16 ? new Assignment : new BinaryExpression); binary->left = left; binary->oper = parse_token(); if(binary->oper=="[") @@ -533,7 +533,6 @@ BinaryExpression *ProgramParser::parse_binary(Expression *left, const Operator * } else binary->right = parse_expression(oper->precedence+(oper->assoc==RIGHT_TO_LEFT)); - binary->assignment = (oper->precedence==16); return binary.release(); } diff --git a/source/programsyntax.cpp b/source/programsyntax.cpp index dcd19f2b..83cfbb08 100644 --- a/source/programsyntax.cpp +++ b/source/programsyntax.cpp @@ -54,11 +54,18 @@ void UnaryExpression::visit(NodeVisitor &visitor) } -BinaryExpression::BinaryExpression(): - assignment(false) +void BinaryExpression::visit(NodeVisitor &visitor) +{ + visitor.visit(*this); +} + + +Assignment::Assignment(): + self_referencing(false), + target_declaration(0) { } -void BinaryExpression::visit(NodeVisitor &visitor) +void Assignment::visit(NodeVisitor &visitor) { visitor.visit(*this); } @@ -156,6 +163,12 @@ void Return::visit(NodeVisitor &visitor) } +void NodeVisitor::visit(Assignment &assign) +{ + visit(static_cast(assign)); +} + + void TraversingVisitor::visit(Block &block) { for(list >::iterator i=block.body.begin(); i!=block.body.end(); ++i) diff --git a/source/programsyntax.h b/source/programsyntax.h index 88f333ac..03b5aa88 100644 --- a/source/programsyntax.h +++ b/source/programsyntax.h @@ -126,14 +126,22 @@ struct BinaryExpression: Expression std::string oper; NodePtr right; std::string after; - bool assignment; - - BinaryExpression(); virtual BinaryExpression *clone() const { return new BinaryExpression(*this); } virtual void visit(NodeVisitor &); }; +struct Assignment: BinaryExpression +{ + bool self_referencing; + VariableDeclaration *target_declaration; + + Assignment(); + + virtual Assignment *clone() const { return new Assignment(*this); } + virtual void visit(NodeVisitor &); +}; + struct FunctionCall: Expression { std::string name; @@ -275,6 +283,7 @@ struct NodeVisitor virtual void visit(MemberAccess &) { } virtual void visit(UnaryExpression &) { } virtual void visit(BinaryExpression &) { } + virtual void visit(Assignment &); virtual void visit(FunctionCall &) { } virtual void visit(ExpressionStatement &) { } virtual void visit(Layout &) { } -- 2.43.0