1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
11 InlineableFunctionLocator::InlineableFunctionLocator():
16 void InlineableFunctionLocator::visit(FunctionCall &call)
18 FunctionDeclaration *def = call.declaration;
20 def = def->definition;
24 unsigned &count = refcounts[def];
26 /* Don't inline functions which are called more than once or are called
28 if(count>1 || def==current_function)
29 inlineable.erase(def);
32 TraversingVisitor::visit(call);
35 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
37 unsigned &count = refcounts[func.definition];
38 if(count<=1 && func.parameters.empty())
39 inlineable.insert(func.definition);
41 SetForScope<FunctionDeclaration *> set(current_function, &func);
43 TraversingVisitor::visit(func);
46 void InlineableFunctionLocator::visit(Conditional &cond)
48 TraversingVisitor::visit(cond);
49 inlineable.erase(current_function);
52 void InlineableFunctionLocator::visit(Iteration &iter)
54 TraversingVisitor::visit(iter);
55 inlineable.erase(current_function);
58 void InlineableFunctionLocator::visit(Return &ret)
60 TraversingVisitor::visit(ret);
62 inlineable.erase(current_function);
67 InlineContentInjector::InlineContentInjector():
72 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionDeclaration &src)
76 // Collect all declarations the inlined function depends on.
78 source_func->visit(*this);
80 /* Populate referenced_names from the target function so we can rename
81 variables from the inlined function that would conflict. */
83 target_func.visit(*this);
85 /* Inline and rename passes must be interleaved so used variable names are
86 known when inlining the return statement. */
88 staging_block.parent = &tgt_blk;
89 staging_block.variables.clear();
90 remap_prefix = source_func->name;
92 for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
94 r_inlined_statement = 0;
96 if(!r_inlined_statement)
97 r_inlined_statement = (*i)->clone();
99 SetForScope<Pass> set_pass(pass, RENAME);
100 r_inlined_statement->visit(*this);
102 staging_block.body.push_back(0);
103 staging_block.body.back() = r_inlined_statement;
106 /* Now collect names from the staging block. Local variables that would
107 have conflicted with the target function were renamed earlier. */
109 referenced_names.clear();
110 staging_block.variables.clear();
111 staging_block.visit(*this);
113 /* Rename variables in the target function so they don't interfere with
114 global identifiers used by the source function. */
116 staging_block.parent = source_func->body.parent;
117 remap_prefix = target_func.name;
118 target_func.visit(*this);
120 tgt_blk.body.splice(ins_pt, staging_block.body);
122 NodeReorderer().apply(stage, target_func, dependencies);
124 return r_result_name;
127 void InlineContentInjector::visit(VariableReference &var)
131 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
132 if(i!=staging_block.variables.end())
133 var.name = i->second->name;
135 else if(pass==DEPENDS && var.declaration)
137 dependencies.insert(var.declaration);
138 var.declaration->visit(*this);
140 else if(pass==REFERENCED)
141 referenced_names.insert(var.name);
144 void InlineContentInjector::visit(InterfaceBlockReference &iface)
146 if(pass==DEPENDS && iface.declaration)
148 dependencies.insert(iface.declaration);
149 iface.declaration->visit(*this);
151 else if(pass==REFERENCED)
152 referenced_names.insert(iface.name);
155 void InlineContentInjector::visit(FunctionCall &call)
157 if(pass==DEPENDS && call.declaration)
158 dependencies.insert(call.declaration);
159 else if(pass==REFERENCED)
160 referenced_names.insert(call.name);
161 TraversingVisitor::visit(call);
164 void InlineContentInjector::visit(VariableDeclaration &var)
166 TraversingVisitor::visit(var);
170 staging_block.variables[var.name] = &var;
171 if(referenced_names.count(var.name))
173 string mapped_name = get_unused_variable_name(staging_block, var.name, remap_prefix);
174 if(mapped_name!=var.name)
176 staging_block.variables[mapped_name] = &var;
177 var.name = mapped_name;
181 else if(pass==DEPENDS && var.type_declaration)
183 dependencies.insert(var.type_declaration);
184 var.type_declaration->visit(*this);
186 else if(pass==REFERENCED)
187 referenced_names.insert(var.type);
190 void InlineContentInjector::visit(Return &ret)
192 TraversingVisitor::visit(ret);
194 if(pass==INLINE && ret.expression)
196 // Create a new variable to hold the return value of the inlined function.
197 r_result_name = get_unused_variable_name(staging_block, "_return", source_func->name);
198 RefPtr<VariableDeclaration> var = new VariableDeclaration;
199 var->source = ret.source;
200 var->line = ret.line;
201 var->type = source_func->return_type;
202 var->name = r_result_name;
203 var->init_expression = ret.expression->clone();
204 r_inlined_statement = var;
209 FunctionInliner::FunctionInliner():
211 r_any_inlined(false),
212 r_inlined_here(false)
215 bool FunctionInliner::apply(Stage &s)
218 inlineable = InlineableFunctionLocator().apply(s);
219 r_any_inlined = false;
220 s.content.visit(*this);
221 return r_any_inlined;
224 void FunctionInliner::visit(RefPtr<Expression> &ptr)
230 ptr = r_inline_result;
231 r_any_inlined = true;
236 void FunctionInliner::visit(Block &block)
238 SetForScope<Block *> set_block(current_block, &block);
239 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
240 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
247 void FunctionInliner::visit(FunctionCall &call)
252 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
255 FunctionDeclaration *def = call.declaration;
257 def = def->definition;
259 if(def && inlineable.count(def))
261 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
263 // This will later get removed by UnusedVariableRemover.
264 if(result_name.empty())
265 result_name = "msp_unused_from_inline";
267 RefPtr<VariableReference> ref = new VariableReference;
268 ref->name = result_name;
269 r_inline_result = ref;
271 /* Inlined variables need to be resolved before this function can be
273 inlineable.erase(current_function);
274 r_inlined_here = true;
278 void FunctionInliner::visit(FunctionDeclaration &func)
280 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
281 TraversingVisitor::visit(func);
282 r_inlined_here = false;
285 void FunctionInliner::visit(Iteration &iter)
287 /* Visit the initialization statement before entering the loop body so the
288 inlined statements get inserted outside. */
289 if(iter.init_statement)
290 iter.init_statement->visit(*this);
292 SetForScope<Block *> set_block(current_block, &iter.body);
293 /* Skip the condition and loop expression parts because they're not properly
294 inside the body block. Inlining anything into them will require a more
295 comprehensive transformation. */
296 iter.body.visit(*this);
300 ExpressionInliner::ExpressionInfo::ExpressionInfo():
309 ExpressionInliner::ExpressionInliner():
311 r_any_inlined(false),
314 iteration_init(false),
319 bool ExpressionInliner::apply(Stage &s)
321 s.content.visit(*this);
322 return r_any_inlined;
325 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
328 r_any_inlined = true;
331 void ExpressionInliner::visit(Block &block)
333 TraversingVisitor::visit(block);
335 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
337 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
338 for(; (j!=expressions.end() && j->first.declaration==i->second); )
340 if(j->second.expression && j->second.inline_point)
341 inline_expression(*j->second.expression, *j->second.inline_point);
343 expressions.erase(j++);
347 /* Expressions assigned in this block may depend on local variables of the
348 block. If this is a conditionally executed block, the assignments might not
349 always happen. Mark the expressions as not available to any outer blocks. */
350 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
351 if(i->second.assign_scope==&block)
352 i->second.available = false;
355 void ExpressionInliner::visit(RefPtr<Expression> &expr)
359 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
361 if(iteration_body && !r_ref_info->trivial)
363 /* Don't inline non-trivial expressions which were assigned outside
364 an iteration statement. The iteration may run multiple times, which
365 would cause the expression to also be evaluated multiple times. */
366 Block *i = r_ref_info->assign_scope;
367 for(; (i && i!=iteration_body); i=i->parent) ;
372 if(r_ref_info->trivial)
373 inline_expression(*r_ref_info->expression, expr);
375 /* Record the inline point for a non-trivial expression but don't
376 inline it yet. It might turn out it shouldn't be inlined after all. */
377 r_ref_info->inline_point = &expr;
383 void ExpressionInliner::visit(VariableReference &var)
387 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
388 if(i!=expressions.end())
390 /* If a non-trivial expression is referenced multiple times, don't
392 if(i->second.inline_point && !i->second.trivial)
393 i->second.expression = 0;
394 /* Mutating expressions are analogous to self-referencing assignments
395 and prevent inlining. */
397 i->second.expression = 0;
398 r_ref_info = &i->second;
403 void ExpressionInliner::visit(MemberAccess &memacc)
409 void ExpressionInliner::visit(Swizzle &swizzle)
415 void ExpressionInliner::visit(UnaryExpression &unary)
417 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
418 visit(unary.expression);
422 void ExpressionInliner::visit(BinaryExpression &binary)
426 SetFlag clear_target(mutating, false);
432 void ExpressionInliner::visit(Assignment &assign)
435 SetFlag set_target(mutating);
441 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
442 if(i!=expressions.end())
444 /* Self-referencing assignments can't be inlined without additional
445 work. Just clear any previous expression. */
446 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
447 i->second.assign_scope = current_block;
448 i->second.inline_point = 0;
449 i->second.available = true;
455 void ExpressionInliner::visit(TernaryExpression &ternary)
457 visit(ternary.condition);
458 visit(ternary.true_expr);
459 visit(ternary.false_expr);
463 void ExpressionInliner::visit(FunctionCall &call)
465 TraversingVisitor::visit(call);
469 void ExpressionInliner::visit(VariableDeclaration &var)
473 TraversingVisitor::visit(var);
475 bool constant = var.constant;
476 if(constant && var.layout)
478 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
479 constant = (i->name!="constant_id");
482 /* Only inline global variables if they're constant and have trivial
483 initializers. Non-constant variables could change in ways which are hard to
484 analyze and non-trivial expressions could be expensive to inline. */
485 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
487 ExpressionInfo &info = expressions[&var];
488 /* Assume variables declared in an iteration initialization statement
489 will have their values change throughout the iteration. */
490 info.expression = (iteration_init ? 0 : var.init_expression.get());
491 info.assign_scope = current_block;
492 info.trivial = r_trivial;
496 void ExpressionInliner::visit(Iteration &iter)
498 SetForScope<Block *> set_block(current_block, &iter.body);
499 if(iter.init_statement)
501 SetFlag set_init(iteration_init);
502 iter.init_statement->visit(*this);
505 SetForScope<Block *> set_body(iteration_body, &iter.body);
507 visit(iter.condition);
508 iter.body.visit(*this);
509 if(iter.loop_expression)
510 visit(iter.loop_expression);
514 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
516 if(value.check_type<bool>())
517 return BasicTypeDeclaration::BOOL;
518 else if(value.check_type<int>())
519 return BasicTypeDeclaration::INT;
520 else if(value.check_type<float>())
521 return BasicTypeDeclaration::FLOAT;
523 return BasicTypeDeclaration::VOID;
527 T ConstantFolder::evaluate_logical(char oper, T left, T right)
531 case '&': return left&right;
532 case '|': return left|right;
533 case '^': return left^right;
539 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
541 switch(oper[0]|oper[1])
543 case '<': return left<right;
544 case '<'|'=': return left<=right;
545 case '>': return left>right;
546 case '>'|'=': return left>=right;
547 default: return false;
552 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
556 case '+': return left+right;
557 case '-': return left-right;
558 case '*': return left*right;
559 case '/': return left/right;
564 void ConstantFolder::set_result(const Variant &value, bool literal)
566 r_constant_value = value;
571 void ConstantFolder::visit(RefPtr<Expression> &expr)
573 r_constant_value = Variant();
576 r_uses_iter_var = false;
578 /* Don't replace literals since they'd only be replaced with an identical
579 literal. Also skip anything that uses an iteration variable, but pass on
580 the result so the Iteration visiting function can handle it. */
581 if(!r_constant || r_literal || r_uses_iter_var)
584 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
585 if(kind==BasicTypeDeclaration::VOID)
591 RefPtr<Literal> literal = new Literal;
592 if(kind==BasicTypeDeclaration::BOOL)
593 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
594 else if(kind==BasicTypeDeclaration::INT)
595 literal->token = lexical_cast<string>(r_constant_value.value<int>());
596 else if(kind==BasicTypeDeclaration::FLOAT)
597 literal->token = lexical_cast<string>(r_constant_value.value<float>());
598 literal->value = r_constant_value;
602 void ConstantFolder::visit(Literal &literal)
604 set_result(literal.value, true);
607 void ConstantFolder::visit(VariableReference &var)
609 /* If an iteration variable is initialized with a constant value, return
610 that value here for the purpose of evaluating the loop condition for the
612 if(var.declaration==iteration_var)
614 set_result(iter_init_value);
615 r_uses_iter_var = true;
619 void ConstantFolder::visit(MemberAccess &memacc)
621 TraversingVisitor::visit(memacc);
625 void ConstantFolder::visit(Swizzle &swizzle)
627 TraversingVisitor::visit(swizzle);
631 void ConstantFolder::visit(UnaryExpression &unary)
633 TraversingVisitor::visit(unary);
634 bool can_fold = r_constant;
639 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
641 char oper = unary.oper->token[0];
642 char oper2 = unary.oper->token[1];
645 if(kind==BasicTypeDeclaration::BOOL)
646 set_result(!r_constant_value.value<bool>());
650 if(kind==BasicTypeDeclaration::INT)
651 set_result(~r_constant_value.value<int>());
653 else if(oper=='-' && !oper2)
655 if(kind==BasicTypeDeclaration::INT)
656 set_result(-r_constant_value.value<int>());
657 else if(kind==BasicTypeDeclaration::FLOAT)
658 set_result(-r_constant_value.value<float>());
662 void ConstantFolder::visit(BinaryExpression &binary)
665 bool left_constant = r_constant;
666 bool left_iter_var = r_uses_iter_var;
667 Variant left_value = r_constant_value;
670 r_uses_iter_var = true;
672 bool can_fold = (left_constant && r_constant);
677 BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
678 BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
679 // Currently only expressions with both sides of equal types are handled.
680 if(left_kind!=right_kind)
683 char oper = binary.oper->token[0];
684 char oper2 = binary.oper->token[1];
685 if(oper=='&' || oper=='|' || oper=='^')
687 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
688 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
689 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
690 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
692 else if((oper=='<' || oper=='>') && oper2!=oper)
694 if(left_kind==BasicTypeDeclaration::INT)
695 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
696 else if(left_kind==BasicTypeDeclaration::FLOAT)
697 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
699 else if((oper=='=' || oper=='!') && oper2=='=')
701 if(left_kind==BasicTypeDeclaration::INT)
702 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
703 if(left_kind==BasicTypeDeclaration::FLOAT)
704 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
706 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
708 if(left_kind==BasicTypeDeclaration::INT)
709 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
710 else if(left_kind==BasicTypeDeclaration::FLOAT)
711 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
713 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
715 if(left_kind!=BasicTypeDeclaration::INT)
719 set_result(left_value.value<int>()%r_constant_value.value<int>());
721 set_result(left_value.value<int>()<<r_constant_value.value<int>());
723 set_result(left_value.value<int>()>>r_constant_value.value<int>());
727 void ConstantFolder::visit(Assignment &assign)
729 TraversingVisitor::visit(assign);
733 void ConstantFolder::visit(TernaryExpression &ternary)
735 TraversingVisitor::visit(ternary);
739 void ConstantFolder::visit(FunctionCall &call)
741 TraversingVisitor::visit(call);
745 void ConstantFolder::visit(VariableDeclaration &var)
747 if(iteration_init && var.init_expression)
749 visit(var.init_expression);
752 /* Record the value of a constant initialization expression of an
753 iteration, so it can be used to evaluate the loop condition. */
754 iteration_var = &var;
755 iter_init_value = r_constant_value;
759 TraversingVisitor::visit(var);
762 void ConstantFolder::visit(Iteration &iter)
764 SetForScope<Block *> set_block(current_block, &iter.body);
766 /* The iteration variable is not normally inlined into expressions, so we
767 process it specially here. If the initial value causes the loop condition
768 to evaluate to false, then the expression can be folded. */
770 if(iter.init_statement)
772 SetFlag set_init(iteration_init);
773 iter.init_statement->visit(*this);
778 visit(iter.condition);
779 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
781 RefPtr<Literal> literal = new Literal;
782 literal->token = "false";
783 literal->value = r_constant_value;
784 iter.condition = literal;
789 iter.body.visit(*this);
790 if(iter.loop_expression)
791 visit(iter.loop_expression);
795 void ConstantConditionEliminator::apply(Stage &stage)
797 stage.content.visit(*this);
798 NodeRemover().apply(stage, nodes_to_remove);
801 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
803 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
804 if(literal->value.check_type<bool>())
805 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
809 void ConstantConditionEliminator::visit(Block &block)
811 SetForScope<Block *> set_block(current_block, &block);
812 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
819 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
821 r_ternary_result = 0;
824 expr = r_ternary_result;
825 r_ternary_result = 0;
828 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
830 ConstantStatus result = check_constant_condition(*ternary.condition);
831 if(result!=NOT_CONSTANT)
832 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
834 r_ternary_result = 0;
837 void ConstantConditionEliminator::visit(Conditional &cond)
839 ConstantStatus result = check_constant_condition(*cond.condition);
840 if(result!=NOT_CONSTANT)
842 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
843 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
844 current_block->body.splice(insert_point, block.body);
845 nodes_to_remove.insert(&cond);
849 TraversingVisitor::visit(cond);
852 void ConstantConditionEliminator::visit(Iteration &iter)
856 ConstantStatus result = check_constant_condition(*iter.condition);
857 if(result==CONSTANT_FALSE)
859 nodes_to_remove.insert(&iter);
864 TraversingVisitor::visit(iter);
868 bool UnusedTypeRemover::apply(Stage &stage)
870 stage.content.visit(*this);
871 NodeRemover().apply(stage, unused_nodes);
872 return !unused_nodes.empty();
875 void UnusedTypeRemover::visit(Literal &literal)
877 unused_nodes.erase(literal.type);
880 void UnusedTypeRemover::visit(UnaryExpression &unary)
882 unused_nodes.erase(unary.type);
883 TraversingVisitor::visit(unary);
886 void UnusedTypeRemover::visit(BinaryExpression &binary)
888 unused_nodes.erase(binary.type);
889 TraversingVisitor::visit(binary);
892 void UnusedTypeRemover::visit(TernaryExpression &ternary)
894 unused_nodes.erase(ternary.type);
895 TraversingVisitor::visit(ternary);
898 void UnusedTypeRemover::visit(FunctionCall &call)
900 unused_nodes.erase(call.type);
901 TraversingVisitor::visit(call);
904 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
907 unused_nodes.erase(type.base_type);
908 unused_nodes.insert(&type);
911 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
914 unused_nodes.erase(type.base_type);
915 unused_nodes.insert(&type);
918 void UnusedTypeRemover::visit(StructDeclaration &strct)
920 unused_nodes.insert(&strct);
921 TraversingVisitor::visit(strct);
924 void UnusedTypeRemover::visit(VariableDeclaration &var)
926 unused_nodes.erase(var.type_declaration);
929 void UnusedTypeRemover::visit(InterfaceBlock &iface)
931 unused_nodes.erase(iface.type_declaration);
934 void UnusedTypeRemover::visit(FunctionDeclaration &func)
936 unused_nodes.erase(func.return_type_declaration);
937 TraversingVisitor::visit(func);
941 UnusedVariableRemover::UnusedVariableRemover():
945 assignment_target(false),
946 r_side_effects(false)
949 bool UnusedVariableRemover::apply(Stage &s)
952 s.content.visit(*this);
954 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
955 if(i->used_by.empty())
956 unused_nodes.insert(i->node);
958 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
959 if(i->second->instance_name.empty())
960 unused_nodes.insert(i->second);
962 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
966 /* The last visible assignments of output variables are used by the
967 next stage or the API. */
968 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
969 unused_nodes.erase((*j)->node);
972 if(!i->second.output && !i->second.referenced)
974 // Don't remove variables from inside interface blocks.
975 if(!i->second.interface_block)
976 unused_nodes.insert(i->first);
978 else if(i->second.interface_block)
979 // Interface blocks are kept if even one member is used.
980 unused_nodes.erase(i->second.interface_block);
983 NodeRemover().apply(s, unused_nodes);
985 return !unused_nodes.empty();
988 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
990 VariableInfo &var_info = variables[target.declaration];
991 var_info.referenced = true;
992 if(!assignment_target)
994 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
995 (*i)->used_by.push_back(&node);
999 void UnusedVariableRemover::visit(VariableReference &var)
1001 referenced(var.declaration, var);
1004 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1006 referenced(iface.declaration, iface);
1009 void UnusedVariableRemover::visit(UnaryExpression &unary)
1011 TraversingVisitor::visit(unary);
1012 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1013 r_side_effects = true;
1016 void UnusedVariableRemover::visit(BinaryExpression &binary)
1018 if(binary.oper->token[0]=='[')
1020 binary.left->visit(*this);
1021 SetFlag set(assignment_target, false);
1022 binary.right->visit(*this);
1025 TraversingVisitor::visit(binary);
1028 void UnusedVariableRemover::visit(Assignment &assign)
1031 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1032 assign.left->visit(*this);
1034 assign.right->visit(*this);
1035 r_assignment = &assign;
1036 r_side_effects = true;
1039 void UnusedVariableRemover::visit(FunctionCall &call)
1041 TraversingVisitor::visit(call);
1042 /* Treat function calls as having side effects so expression statements
1043 consisting of nothing but a function call won't be optimized away. */
1044 r_side_effects = true;
1046 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1048 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1049 if(i->second.output)
1050 referenced(i->first, call);
1054 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1056 assignments.push_back(AssignmentInfo());
1057 AssignmentInfo &assign_info = assignments.back();
1058 assign_info.node = &node;
1059 assign_info.target = target;
1061 /* An assignment to the target hides any assignments to the same target or
1063 VariableInfo &var_info = variables[target.declaration];
1064 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1066 const Assignment::Target &t = var_info.assignments[i]->target;
1068 bool subfield = (t.chain_len>=target.chain_len);
1069 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1070 subfield = (t.chain[j]==target.chain[j]);
1073 var_info.assignments.erase(var_info.assignments.begin()+i);
1078 var_info.assignments.push_back(&assign_info);
1081 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1084 r_side_effects = false;
1085 TraversingVisitor::visit(expr);
1086 if(r_assignment && r_assignment->target.declaration)
1087 record_assignment(r_assignment->target, expr);
1089 unused_nodes.insert(&expr);
1092 void UnusedVariableRemover::visit(VariableDeclaration &var)
1094 VariableInfo &var_info = variables[&var];
1095 var_info.interface_block = interface_block;
1097 /* Mark variables as output if they're used by the next stage or the
1100 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
1102 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1104 if(var.init_expression)
1106 var_info.initialized = true;
1107 record_assignment(&var, *var.init_expression);
1109 TraversingVisitor::visit(var);
1112 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1114 if(iface.instance_name.empty())
1116 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1117 iface.struct_declaration->members.visit(*this);
1121 VariableInfo &var_info = variables[&iface];
1122 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
1126 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1128 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1130 BlockVariableMap::iterator j = variables.find(i->first);
1131 if(j!=variables.end())
1133 /* The merged blocks started as copies of each other so any common
1134 assignments must be in the beginning. */
1136 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1137 if(i->second.assignments[k]!=j->second.assignments[k])
1140 // Remaining assignments are unique to each block; merge them.
1141 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1142 j->second.referenced |= i->second.referenced;
1145 variables.insert(*i);
1149 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1151 if(func.body.body.empty())
1154 BlockVariableMap saved_vars = variables;
1155 // Assignments from other functions should not be visible.
1156 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1157 i->second.assignments.resize(i->second.initialized);
1158 TraversingVisitor::visit(func);
1159 swap(variables, saved_vars);
1160 merge_variables(saved_vars);
1162 /* Always treat function parameters as referenced. Removing unused
1163 parameters is not currently supported. */
1164 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1166 BlockVariableMap::iterator j = variables.find(i->get());
1167 if(j!=variables.end())
1168 j->second.referenced = true;
1172 void UnusedVariableRemover::visit(Conditional &cond)
1174 cond.condition->visit(*this);
1175 BlockVariableMap saved_vars = variables;
1176 cond.body.visit(*this);
1177 swap(saved_vars, variables);
1178 cond.else_body.visit(*this);
1180 /* Visible assignments after the conditional is the union of those visible
1181 at the end of the if and else blocks. If there was no else block, then it's
1182 the union of the if block and the state before it. */
1183 merge_variables(saved_vars);
1186 void UnusedVariableRemover::visit(Iteration &iter)
1188 BlockVariableMap saved_vars = variables;
1189 TraversingVisitor::visit(iter);
1191 /* Merge assignments from the iteration, without clearing previous state.
1192 Further analysis is needed to determine which parts of the iteration body
1193 are always executed, if any. */
1194 merge_variables(saved_vars);
1198 bool UnusedFunctionRemover::apply(Stage &stage)
1200 stage.content.visit(*this);
1201 NodeRemover().apply(stage, unused_nodes);
1202 return !unused_nodes.empty();
1205 void UnusedFunctionRemover::visit(FunctionCall &call)
1207 TraversingVisitor::visit(call);
1209 unused_nodes.erase(call.declaration);
1210 if(call.declaration && call.declaration->definition!=call.declaration)
1211 used_definitions.insert(call.declaration->definition);
1214 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1216 TraversingVisitor::visit(func);
1218 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1219 unused_nodes.insert(&func);