+ auto i = current_block->variables.find(var->name);
+ r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
+ return;
+ }
+
+ TraversingVisitor::visit(unary);
+}
+
+void ConstantConditionEliminator::visit(Assignment &assign)
+{
+ auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
+ if(i==current_block->variables.end())
+ r_external_side_effects = true;
+ TraversingVisitor::visit(assign);
+}
+
+void ConstantConditionEliminator::visit(TernaryExpression &ternary)
+{
+ ConstantStatus result = check_constant_condition(*ternary.condition);
+ if(result!=NOT_CONSTANT)
+ r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
+ else
+ r_ternary_result = 0;
+}
+
+void ConstantConditionEliminator::visit(FunctionCall &call)
+{
+ r_external_side_effects = true;
+ TraversingVisitor::visit(call);
+}
+
+void ConstantConditionEliminator::visit(Conditional &cond)
+{
+ ConstantStatus result = check_constant_condition(*cond.condition);
+ if(result!=NOT_CONSTANT)
+ {
+ Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
+ // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
+ current_block->body.splice(insert_point, block.body);
+ nodes_to_remove.insert(&cond);
+ return;
+ }
+
+ r_external_side_effects = false;
+ TraversingVisitor::visit(cond);
+
+ if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
+ nodes_to_remove.insert(&cond);
+}
+
+void ConstantConditionEliminator::visit(Iteration &iter)
+{
+ if(iter.condition)
+ {
+ ConstantStatus result = check_constant_condition(*iter.condition);
+ if(result==CONSTANT_FALSE)
+ {
+ nodes_to_remove.insert(&iter);
+ return;
+ }
+ }
+
+ r_external_side_effects = false;
+ TraversingVisitor::visit(iter);
+ if(iter.body.body.empty() && !r_external_side_effects)
+ nodes_to_remove.insert(&iter);
+}
+
+
+bool UnreachableCodeRemover::apply(Stage &stage)
+{
+ stage.content.visit(*this);
+ NodeRemover().apply(stage, unreachable_nodes);
+ return !unreachable_nodes.empty();
+}
+
+void UnreachableCodeRemover::visit(Block &block)
+{
+ auto i = block.body.begin();
+ for(; (reachable && i!=block.body.end()); ++i)
+ (*i)->visit(*this);
+ for(; i!=block.body.end(); ++i)
+ unreachable_nodes.insert(i->get());
+}
+
+void UnreachableCodeRemover::visit(FunctionDeclaration &func)
+{
+ TraversingVisitor::visit(func);
+ reachable = true;
+}
+
+void UnreachableCodeRemover::visit(Conditional &cond)
+{
+ cond.body.visit(*this);
+ bool reachable_if_true = reachable;
+ reachable = true;
+ cond.else_body.visit(*this);
+
+ reachable |= reachable_if_true;
+}
+
+void UnreachableCodeRemover::visit(Iteration &iter)
+{
+ TraversingVisitor::visit(iter);
+
+ /* 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)
+ {
+ bool covered = true;
+ for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
+ {
+ Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
+ Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
+ unsigned index1 = a->target.chain[j]&0x3F;
+ unsigned index2 = target.chain[j]&0x3F;
+ if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
+ {
+ if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
+ covered = index1&index2;
+ else if(type1==Assignment::Target::ARRAY && index1<4)
+ covered = index2&(1<<index1);
+ else if(type2==Assignment::Target::ARRAY && index2<4)
+ covered = index1&(1<<index2);
+ /* If it's some other combination (shouldn't happen), leave
+ covered as true */
+ }
+ else
+ covered = (type1==type2 && (index1==index2 || index1==0x3F || index2==0x3F));
+ }
+
+ if(covered)
+ {
+ 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.push_back(AssignmentInfo());
+ 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;