+ /* Always consider code after a loop reachable, since there's no checking
+ for whether the loop executes. */
+ reachable = true;
+}
+
+
+bool UnusedTypeRemover::apply(Stage &stage)
+{
+ stage.content.visit(*this);
+ NodeRemover().apply(stage, unused_nodes);
+ return !unused_nodes.empty();
+}
+
+void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
+{
+ unused_nodes.erase(expr->type);
+ TraversingVisitor::visit(expr);
+}
+
+void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
+{
+ if(type.base_type)
+ unused_nodes.erase(type.base_type);
+ unused_nodes.insert(&type);
+}
+
+void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
+{
+ if(type.base_type)
+ unused_nodes.erase(type.base_type);
+ unused_nodes.insert(&type);
+}
+
+void UnusedTypeRemover::visit(StructDeclaration &strct)
+{
+ unused_nodes.insert(&strct);
+ TraversingVisitor::visit(strct);
+}
+
+void UnusedTypeRemover::visit(VariableDeclaration &var)
+{
+ unused_nodes.erase(var.type_declaration);
+ TraversingVisitor::visit(var);
+}
+
+void UnusedTypeRemover::visit(InterfaceBlock &iface)
+{
+ unused_nodes.erase(iface.type_declaration);
+}
+
+void UnusedTypeRemover::visit(FunctionDeclaration &func)
+{
+ unused_nodes.erase(func.return_type_declaration);
+ TraversingVisitor::visit(func);
+}
+
+
+bool UnusedVariableRemover::apply(Stage &s)
+{
+ stage = &s;
+ s.content.visit(*this);
+
+ for(const AssignmentInfo &a: assignments)
+ if(a.used_by.empty())
+ unused_nodes.insert(a.node);
+
+ for(const auto &kvp: variables)
+ {
+ if(!kvp.second.referenced)
+ unused_nodes.insert(kvp.first);
+ else if(kvp.second.output)
+ {
+ /* The last visible assignments of output variables are used by the
+ next stage or the API. */
+ for(AssignmentInfo *a: kvp.second.assignments)
+ unused_nodes.erase(a->node);
+ }
+ }
+
+ NodeRemover().apply(s, unused_nodes);
+
+ return !unused_nodes.empty();
+}
+
+void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
+{
+ VariableInfo &var_info = variables[target.declaration];
+ var_info.referenced = true;
+ if(!assignment_target)
+ {
+ bool loop_external = false;
+ for(AssignmentInfo *a: var_info.assignments)
+ if(targets_overlap(a->target, target))
+ {
+ a->used_by.push_back(&node);
+ if(a->in_loop<in_loop)
+ loop_external = true;
+ }
+
+ if(loop_external)
+ loop_ext_refs.push_back(&node);
+ }
+}
+
+void UnusedVariableRemover::visit(VariableReference &var)
+{
+ if(composite_reference)
+ r_reference.declaration = var.declaration;
+ else if(var.declaration)
+ referenced(var.declaration, var);
+}
+
+void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
+{
+ if(composite_reference)
+ r_reference.declaration = iface.declaration;
+ else if(iface.declaration)
+ referenced(iface.declaration, iface);
+}
+
+void UnusedVariableRemover::visit_composite(Expression &expr)
+{
+ if(!composite_reference)
+ r_reference = Assignment::Target();
+
+ SetFlag set_composite(composite_reference);
+ expr.visit(*this);
+}
+
+void UnusedVariableRemover::visit(MemberAccess &memacc)
+{
+ visit_composite(*memacc.left);
+
+ add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
+
+ if(!composite_reference && r_reference.declaration)
+ referenced(r_reference, memacc);
+}
+
+void UnusedVariableRemover::visit(Swizzle &swizzle)
+{
+ visit_composite(*swizzle.left);
+
+ unsigned mask = 0;
+ for(unsigned i=0; i<swizzle.count; ++i)
+ mask |= 1<<swizzle.components[i];
+ add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
+
+ if(!composite_reference && r_reference.declaration)
+ referenced(r_reference, swizzle);
+}
+
+void UnusedVariableRemover::visit(UnaryExpression &unary)
+{
+ TraversingVisitor::visit(unary);
+ if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
+ r_side_effects = true;
+}
+
+void UnusedVariableRemover::visit(BinaryExpression &binary)
+{
+ if(binary.oper->token[0]=='[')
+ {
+ visit_composite(*binary.left);
+
+ {
+ SetFlag clear_assignment(assignment_target, false);
+ SetFlag clear_composite(composite_reference, false);
+ SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
+ binary.right->visit(*this);
+ }
+
+ add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
+
+ if(!composite_reference && r_reference.declaration)
+ referenced(r_reference, binary);
+ }
+ else
+ {
+ SetFlag clear_composite(composite_reference, false);
+ TraversingVisitor::visit(binary);
+ }
+}
+
+void UnusedVariableRemover::visit(TernaryExpression &ternary)
+{
+ SetFlag clear_composite(composite_reference, false);
+ TraversingVisitor::visit(ternary);
+}
+
+void UnusedVariableRemover::visit(Assignment &assign)
+{
+ {
+ SetFlag set(assignment_target, (assign.oper->token[0]=='='));
+ assign.left->visit(*this);
+ }
+ assign.right->visit(*this);
+ r_assignment = &assign;
+ r_side_effects = true;
+}
+
+void UnusedVariableRemover::visit(FunctionCall &call)
+{
+ SetFlag clear_composite(composite_reference, false);
+ TraversingVisitor::visit(call);
+ /* Treat function calls as having side effects so expression statements
+ consisting of nothing but a function call won't be optimized away. */
+ r_side_effects = true;
+
+ if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
+ {
+ for(const auto &kvp: variables)
+ if(kvp.second.output)
+ referenced(kvp.first, call);
+ }
+}
+
+void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
+{
+ assignments.emplace_back();
+ AssignmentInfo &assign_info = assignments.back();
+ assign_info.node = &node;
+ assign_info.target = target;
+ assign_info.in_loop = in_loop;
+
+ /* An assignment to the target hides any assignments to the same target or
+ its subfields. */
+ VariableInfo &var_info = variables[target.declaration];
+ for(unsigned i=0; i<var_info.assignments.size(); )
+ {
+ const Assignment::Target &t = var_info.assignments[i]->target;
+
+ bool subfield = (t.chain_len>=target.chain_len);
+ for(unsigned j=0; (subfield && j<target.chain_len); ++j)
+ subfield = (t.chain[j]==target.chain[j]);
+
+ if(subfield)
+ var_info.assignments.erase(var_info.assignments.begin()+i);
+ else
+ ++i;
+ }
+
+ var_info.assignments.push_back(&assign_info);
+}
+
+void UnusedVariableRemover::visit(ExpressionStatement &expr)
+{
+ r_assignment = 0;
+ r_side_effects = false;
+ TraversingVisitor::visit(expr);
+ if(r_assignment && r_assignment->target.declaration)
+ record_assignment(r_assignment->target, expr);
+ if(!r_side_effects)
+ unused_nodes.insert(&expr);
+}
+
+void UnusedVariableRemover::visit(StructDeclaration &strct)
+{
+ SetFlag set_struct(in_struct);
+ TraversingVisitor::visit(strct);
+}
+
+void UnusedVariableRemover::visit(VariableDeclaration &var)
+{
+ TraversingVisitor::visit(var);
+
+ if(in_struct)
+ return;
+
+ VariableInfo &var_info = variables[&var];
+
+ /* Mark variables as output if they're used by the next stage or the
+ graphics API. */
+ var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
+
+ // Linked outputs are automatically referenced.
+ if(var_info.output && var.linked_declaration)
+ var_info.referenced = true;
+
+ if(var.init_expression)
+ {
+ var_info.initialized = true;
+ record_assignment(&var, *var.init_expression);
+ }
+}
+
+void UnusedVariableRemover::visit(InterfaceBlock &iface)
+{
+ VariableInfo &var_info = variables[&iface];
+ var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
+}
+
+void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
+{
+ for(const auto &kvp: other_vars)
+ {
+ auto j = variables.find(kvp.first);
+ if(j!=variables.end())
+ {
+ /* The merged blocks started as copies of each other so any common
+ assignments must be in the beginning. */
+ unsigned k = 0;
+ for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
+ if(kvp.second.assignments[k]!=j->second.assignments[k])
+ break;
+
+ // Remaining assignments are unique to each block; merge them.
+ j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
+ j->second.referenced |= kvp.second.referenced;
+ }
+ else
+ variables.insert(kvp);
+ }
+}
+
+void UnusedVariableRemover::visit(FunctionDeclaration &func)
+{
+ if(func.body.body.empty())
+ return;
+
+ BlockVariableMap saved_vars = variables;
+ // Assignments from other functions should not be visible.
+ for(auto &kvp: variables)
+ kvp.second.assignments.resize(kvp.second.initialized);
+ TraversingVisitor::visit(func);
+ swap(variables, saved_vars);
+ merge_variables(saved_vars);
+
+ /* Always treat function parameters as referenced. Removing unused
+ parameters is not currently supported. */
+ for(const RefPtr<VariableDeclaration> &p: func.parameters)
+ {
+ auto j = variables.find(p.get());
+ if(j!=variables.end())
+ j->second.referenced = true;
+ }
+}
+
+void UnusedVariableRemover::visit(Conditional &cond)
+{
+ cond.condition->visit(*this);
+ BlockVariableMap saved_vars = variables;
+ cond.body.visit(*this);
+ swap(saved_vars, variables);
+ cond.else_body.visit(*this);
+
+ /* Visible assignments after the conditional is the union of those visible
+ at the end of the if and else blocks. If there was no else block, then it's
+ the union of the if block and the state before it. */
+ merge_variables(saved_vars);
+}
+
+void UnusedVariableRemover::visit(Iteration &iter)
+{
+ BlockVariableMap saved_vars = variables;
+ vector<Node *> saved_refs;
+ swap(loop_ext_refs, saved_refs);
+ {
+ if(iter.init_statement)
+ iter.init_statement->visit(*this);
+ SetForScope<unsigned> set_loop(in_loop, in_loop+1);
+ if(iter.condition)
+ iter.condition->visit(*this);
+ iter.body.visit(*this);
+ if(iter.loop_expression)
+ iter.loop_expression->visit(*this);
+ }
+ swap(loop_ext_refs, saved_refs);
+
+ /* Visit the external references of the loop again to record assignments
+ done in the loop as used. */
+ for(Node *n: saved_refs)
+ n->visit(*this);