1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
3 #include <msp/strings/utils.h>
13 ConstantSpecializer::ConstantSpecializer():
17 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
20 stage.content.visit(*this);
23 void ConstantSpecializer::visit(VariableDeclaration &var)
25 bool specializable = false;
28 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
29 for(vector<Layout::Qualifier>::iterator i=qualifiers.begin(); (!specializable && i!=qualifiers.end()); ++i)
30 if(i->name=="constant_id")
36 if(qualifiers.empty())
42 map<string, int>::const_iterator i = values->find(var.name);
45 RefPtr<Literal> literal = new Literal;
48 literal->token = (i->second ? "true" : "false");
49 literal->value = static_cast<bool>(i->second);
51 else if(var.type=="int")
53 literal->token = lexical_cast<string>(i->second);
54 literal->value = i->second;
56 var.init_expression = literal;
62 InlineableFunctionLocator::InlineableFunctionLocator():
67 void InlineableFunctionLocator::visit(FunctionCall &call)
69 FunctionDeclaration *def = call.declaration;
71 def = def->definition;
75 unsigned &count = refcounts[def];
77 /* Don't inline functions which are called more than once or are called
79 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
80 inlineable.erase(def);
83 TraversingVisitor::visit(call);
86 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
88 bool has_out_params = false;
89 for(NodeArray<VariableDeclaration>::const_iterator i=func.parameters.begin(); (!has_out_params && i!=func.parameters.end()); ++i)
90 has_out_params = ((*i)->interface=="out");
92 unsigned &count = refcounts[func.definition];
93 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
94 inlineable.insert(func.definition);
96 SetForScope<FunctionDeclaration *> set(current_function, &func);
98 TraversingVisitor::visit(func);
101 void InlineableFunctionLocator::visit(Conditional &cond)
103 TraversingVisitor::visit(cond);
104 inlineable.erase(current_function);
107 void InlineableFunctionLocator::visit(Iteration &iter)
109 TraversingVisitor::visit(iter);
110 inlineable.erase(current_function);
113 void InlineableFunctionLocator::visit(Return &ret)
115 TraversingVisitor::visit(ret);
117 inlineable.erase(current_function);
122 InlineContentInjector::InlineContentInjector():
127 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
129 source_func = call.declaration->definition;
131 /* Populate referenced_names from the target function so we can rename
132 variables from the inlined function that would conflict. */
134 target_func.visit(*this);
136 /* Inline and rename passes must be interleaved so used variable names are
137 known when inlining the return statement. */
139 staging_block.parent = &tgt_blk;
140 staging_block.variables.clear();
142 vector<RefPtr<VariableDeclaration> > params;
143 params.reserve(source_func->parameters.size());
144 for(NodeArray<VariableDeclaration>::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i)
146 RefPtr<VariableDeclaration> var = (*i)->clone();
147 var->interface.clear();
149 SetForScope<Pass> set_pass(pass, RENAME);
152 staging_block.body.push_back_nocopy(var);
153 params.push_back(var);
156 for(NodeList<Statement>::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i)
158 r_inlined_statement = 0;
160 if(!r_inlined_statement)
161 r_inlined_statement = (*i)->clone();
163 SetForScope<Pass> set_pass(pass, RENAME);
164 r_inlined_statement->visit(*this);
166 staging_block.body.push_back_nocopy(r_inlined_statement);
169 /* Now collect names from the staging block. Local variables that would
170 have conflicted with the target function were renamed earlier. */
172 referenced_names.clear();
173 staging_block.variables.clear();
174 staging_block.visit(*this);
176 /* Rename variables in the target function so they don't interfere with
177 global identifiers used by the source function. */
179 staging_block.parent = source_func->body.parent;
180 target_func.visit(*this);
182 // Put the argument expressions in place after all renaming has been done.
183 for(unsigned i=0; i<source_func->parameters.size(); ++i)
184 params[i]->init_expression = call.arguments[i]->clone();
186 tgt_blk.body.splice(ins_pt, staging_block.body);
188 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
190 return r_result_name;
193 void InlineContentInjector::visit(VariableReference &var)
197 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
198 if(i!=staging_block.variables.end())
199 var.name = i->second->name;
201 else if(pass==REFERENCED)
202 referenced_names.insert(var.name);
205 void InlineContentInjector::visit(InterfaceBlockReference &iface)
208 referenced_names.insert(iface.name);
211 void InlineContentInjector::visit(FunctionCall &call)
214 referenced_names.insert(call.name);
215 TraversingVisitor::visit(call);
218 void InlineContentInjector::visit(VariableDeclaration &var)
220 TraversingVisitor::visit(var);
224 /* Check against conflicts with the other context as well as variables
225 already renamed here. */
226 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
227 staging_block.variables[var.name] = &var;
230 string mapped_name = get_unused_variable_name(staging_block, var.name);
231 if(mapped_name!=var.name)
233 staging_block.variables[mapped_name] = &var;
234 var.name = mapped_name;
238 else if(pass==REFERENCED)
239 referenced_names.insert(var.type);
242 void InlineContentInjector::visit(Return &ret)
244 TraversingVisitor::visit(ret);
246 if(pass==INLINE && ret.expression)
248 // Create a new variable to hold the return value of the inlined function.
249 r_result_name = get_unused_variable_name(staging_block, "_return");
250 RefPtr<VariableDeclaration> var = new VariableDeclaration;
251 var->source = ret.source;
252 var->line = ret.line;
253 var->type = source_func->return_type;
254 var->name = r_result_name;
255 var->init_expression = ret.expression->clone();
256 r_inlined_statement = var;
261 FunctionInliner::FunctionInliner():
263 r_any_inlined(false),
264 r_inlined_here(false)
267 bool FunctionInliner::apply(Stage &s)
270 inlineable = InlineableFunctionLocator().apply(s);
271 r_any_inlined = false;
272 s.content.visit(*this);
273 return r_any_inlined;
276 void FunctionInliner::visit(RefPtr<Expression> &ptr)
282 ptr = r_inline_result;
283 r_any_inlined = true;
288 void FunctionInliner::visit(Block &block)
290 SetForScope<Block *> set_block(current_block, &block);
291 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
292 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
299 void FunctionInliner::visit(FunctionCall &call)
301 for(NodeArray<Expression>::iterator i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
307 FunctionDeclaration *def = call.declaration;
309 def = def->definition;
311 if(def && inlineable.count(def))
313 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
315 // This will later get removed by UnusedVariableRemover.
316 if(result_name.empty())
317 result_name = "_msp_unused_from_inline";
319 RefPtr<VariableReference> ref = new VariableReference;
320 ref->name = result_name;
321 r_inline_result = ref;
323 /* Inlined variables need to be resolved before this function can be
325 inlineable.erase(current_function);
326 r_inlined_here = true;
330 void FunctionInliner::visit(FunctionDeclaration &func)
332 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
333 TraversingVisitor::visit(func);
334 r_inlined_here = false;
337 void FunctionInliner::visit(Iteration &iter)
339 /* Visit the initialization statement before entering the loop body so the
340 inlined statements get inserted outside. */
341 if(iter.init_statement)
342 iter.init_statement->visit(*this);
344 SetForScope<Block *> set_block(current_block, &iter.body);
345 /* Skip the condition and loop expression parts because they're not properly
346 inside the body block. Inlining anything into them will require a more
347 comprehensive transformation. */
348 iter.body.visit(*this);
352 ExpressionInliner::ExpressionInliner():
354 r_any_inlined(false),
357 iteration_init(false),
362 bool ExpressionInliner::apply(Stage &s)
364 s.content.visit(*this);
365 return r_any_inlined;
368 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
371 r_any_inlined = true;
374 void ExpressionInliner::visit(Block &block)
376 TraversingVisitor::visit(block);
378 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
380 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
381 for(; (j!=expressions.end() && j->first.declaration==i->second); )
383 if(j->second.expression && j->second.inline_point)
384 inline_expression(*j->second.expression, *j->second.inline_point);
386 expressions.erase(j++);
390 /* Expressions assigned in this block may depend on local variables of the
391 block. If this is a conditionally executed block, the assignments might not
392 always happen. Mark the expressions as not available to any outer blocks. */
393 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
394 if(i->second.assign_scope==&block)
395 i->second.available = false;
398 void ExpressionInliner::visit(RefPtr<Expression> &expr)
402 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
404 if(iteration_body && !r_ref_info->trivial)
406 /* Don't inline non-trivial expressions which were assigned outside
407 an iteration statement. The iteration may run multiple times, which
408 would cause the expression to also be evaluated multiple times. */
409 Block *i = r_ref_info->assign_scope;
410 for(; (i && i!=iteration_body); i=i->parent) ;
415 if(r_ref_info->trivial)
416 inline_expression(*r_ref_info->expression, expr);
418 /* Record the inline point for a non-trivial expression but don't
419 inline it yet. It might turn out it shouldn't be inlined after all. */
420 r_ref_info->inline_point = &expr;
426 void ExpressionInliner::visit(VariableReference &var)
430 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
431 if(i!=expressions.end())
433 /* If a non-trivial expression is referenced multiple times, don't
435 if(i->second.inline_point && !i->second.trivial)
436 i->second.expression = 0;
437 /* Mutating expressions are analogous to self-referencing assignments
438 and prevent inlining. */
440 i->second.expression = 0;
441 r_ref_info = &i->second;
446 void ExpressionInliner::visit(MemberAccess &memacc)
452 void ExpressionInliner::visit(Swizzle &swizzle)
458 void ExpressionInliner::visit(UnaryExpression &unary)
460 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
461 visit(unary.expression);
465 void ExpressionInliner::visit(BinaryExpression &binary)
469 SetFlag clear_target(mutating, false);
475 void ExpressionInliner::visit(Assignment &assign)
478 SetFlag set_target(mutating);
484 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
485 if(i!=expressions.end())
487 /* Self-referencing assignments can't be inlined without additional
488 work. Just clear any previous expression. */
489 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
490 i->second.assign_scope = current_block;
491 i->second.inline_point = 0;
492 i->second.available = true;
498 void ExpressionInliner::visit(TernaryExpression &ternary)
500 visit(ternary.condition);
501 visit(ternary.true_expr);
502 visit(ternary.false_expr);
506 void ExpressionInliner::visit(FunctionCall &call)
508 TraversingVisitor::visit(call);
512 void ExpressionInliner::visit(VariableDeclaration &var)
516 TraversingVisitor::visit(var);
518 bool constant = var.constant;
519 if(constant && var.layout)
521 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
522 constant = (i->name!="constant_id");
525 /* Only inline global variables if they're constant and have trivial
526 initializers. Non-constant variables could change in ways which are hard to
527 analyze and non-trivial expressions could be expensive to inline. */
528 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
530 ExpressionInfo &info = expressions[&var];
531 /* Assume variables declared in an iteration initialization statement
532 will have their values change throughout the iteration. */
533 info.expression = (iteration_init ? 0 : var.init_expression.get());
534 info.assign_scope = current_block;
535 info.trivial = r_trivial;
539 void ExpressionInliner::visit(Iteration &iter)
541 SetForScope<Block *> set_block(current_block, &iter.body);
542 if(iter.init_statement)
544 SetFlag set_init(iteration_init);
545 iter.init_statement->visit(*this);
548 SetForScope<Block *> set_body(iteration_body, &iter.body);
550 visit(iter.condition);
551 iter.body.visit(*this);
552 if(iter.loop_expression)
553 visit(iter.loop_expression);
558 T ConstantFolder::evaluate_logical(char oper, T left, T right)
562 case '&': return left&right;
563 case '|': return left|right;
564 case '^': return left^right;
570 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
572 switch(oper[0]|oper[1])
574 case '<': return left<right;
575 case '<'|'=': return left<=right;
576 case '>': return left>right;
577 case '>'|'=': return left>=right;
578 default: return false;
583 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
587 case '+': return left+right;
588 case '-': return left-right;
589 case '*': return left*right;
590 case '/': return left/right;
595 void ConstantFolder::set_result(const Variant &value, bool literal)
597 r_constant_value = value;
602 void ConstantFolder::visit(RefPtr<Expression> &expr)
604 r_constant_value = Variant();
607 r_uses_iter_var = false;
609 /* Don't replace literals since they'd only be replaced with an identical
610 literal. Also skip anything that uses an iteration variable, but pass on
611 the result so the Iteration visiting function can handle it. */
612 if(!r_constant || r_literal || r_uses_iter_var)
615 RefPtr<Literal> literal = new Literal;
616 if(r_constant_value.check_type<bool>())
617 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
618 else if(r_constant_value.check_type<int>())
619 literal->token = lexical_cast<string>(r_constant_value.value<int>());
620 else if(r_constant_value.check_type<float>())
622 literal->token = lexical_cast<string>(r_constant_value.value<float>());
623 if(isnumrc(literal->token))
624 literal->token += ".0";
631 literal->value = r_constant_value;
635 void ConstantFolder::visit(Literal &literal)
637 set_result(literal.value, true);
640 void ConstantFolder::visit(VariableReference &var)
642 /* If an iteration variable is initialized with a constant value, return
643 that value here for the purpose of evaluating the loop condition for the
645 if(var.declaration==iteration_var)
647 set_result(iter_init_value);
648 r_uses_iter_var = true;
652 void ConstantFolder::visit(MemberAccess &memacc)
654 TraversingVisitor::visit(memacc);
658 void ConstantFolder::visit(Swizzle &swizzle)
660 TraversingVisitor::visit(swizzle);
664 void ConstantFolder::visit(UnaryExpression &unary)
666 TraversingVisitor::visit(unary);
667 bool can_fold = r_constant;
672 char oper = unary.oper->token[0];
673 char oper2 = unary.oper->token[1];
676 if(r_constant_value.check_type<bool>())
677 set_result(!r_constant_value.value<bool>());
681 if(r_constant_value.check_type<int>())
682 set_result(~r_constant_value.value<int>());
683 else if(r_constant_value.check_type<unsigned>())
684 set_result(~r_constant_value.value<unsigned>());
686 else if(oper=='-' && !oper2)
688 if(r_constant_value.check_type<int>())
689 set_result(-r_constant_value.value<int>());
690 else if(r_constant_value.check_type<unsigned>())
691 set_result(-r_constant_value.value<unsigned>());
692 else if(r_constant_value.check_type<float>())
693 set_result(-r_constant_value.value<float>());
697 void ConstantFolder::visit(BinaryExpression &binary)
700 bool left_constant = r_constant;
701 bool left_iter_var = r_uses_iter_var;
702 Variant left_value = r_constant_value;
705 r_uses_iter_var = true;
707 bool can_fold = (left_constant && r_constant);
712 // Currently only expressions with both sides of equal types are handled.
713 if(!left_value.check_same_type(r_constant_value))
716 char oper = binary.oper->token[0];
717 char oper2 = binary.oper->token[1];
718 if(oper=='&' || oper=='|' || oper=='^')
720 if(oper2==oper && left_value.check_type<bool>())
721 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
722 else if(!oper2 && left_value.check_type<int>())
723 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
725 else if((oper=='<' || oper=='>') && oper2!=oper)
727 if(left_value.check_type<int>())
728 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
729 else if(left_value.check_type<float>())
730 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
732 else if((oper=='=' || oper=='!') && oper2=='=')
734 if(left_value.check_type<int>())
735 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
736 if(left_value.check_type<float>())
737 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
739 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
741 if(left_value.check_type<int>())
742 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
743 else if(left_value.check_type<float>())
744 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
746 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
748 if(!left_value.check_type<int>())
752 set_result(left_value.value<int>()%r_constant_value.value<int>());
754 set_result(left_value.value<int>()<<r_constant_value.value<int>());
756 set_result(left_value.value<int>()>>r_constant_value.value<int>());
760 void ConstantFolder::visit(Assignment &assign)
762 TraversingVisitor::visit(assign);
766 void ConstantFolder::visit(TernaryExpression &ternary)
768 TraversingVisitor::visit(ternary);
772 void ConstantFolder::visit(FunctionCall &call)
774 TraversingVisitor::visit(call);
778 void ConstantFolder::visit(VariableDeclaration &var)
780 if(iteration_init && var.init_expression)
782 visit(var.init_expression);
785 /* Record the value of a constant initialization expression of an
786 iteration, so it can be used to evaluate the loop condition. */
787 iteration_var = &var;
788 iter_init_value = r_constant_value;
792 TraversingVisitor::visit(var);
795 void ConstantFolder::visit(Iteration &iter)
797 SetForScope<Block *> set_block(current_block, &iter.body);
799 /* The iteration variable is not normally inlined into expressions, so we
800 process it specially here. If the initial value causes the loop condition
801 to evaluate to false, then the expression can be folded. */
803 if(iter.init_statement)
805 SetFlag set_init(iteration_init);
806 iter.init_statement->visit(*this);
811 visit(iter.condition);
812 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
814 RefPtr<Literal> literal = new Literal;
815 literal->token = "false";
816 literal->value = r_constant_value;
817 iter.condition = literal;
822 iter.body.visit(*this);
823 if(iter.loop_expression)
824 visit(iter.loop_expression);
828 void ConstantConditionEliminator::apply(Stage &stage)
830 stage.content.visit(*this);
831 NodeRemover().apply(stage, nodes_to_remove);
834 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
836 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
837 if(literal->value.check_type<bool>())
838 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
842 void ConstantConditionEliminator::visit(Block &block)
844 SetForScope<Block *> set_block(current_block, &block);
845 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
852 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
854 r_ternary_result = 0;
857 expr = r_ternary_result;
858 r_ternary_result = 0;
861 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
863 ConstantStatus result = check_constant_condition(*ternary.condition);
864 if(result!=NOT_CONSTANT)
865 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
867 r_ternary_result = 0;
870 void ConstantConditionEliminator::visit(Conditional &cond)
872 ConstantStatus result = check_constant_condition(*cond.condition);
873 if(result!=NOT_CONSTANT)
875 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
876 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
877 current_block->body.splice(insert_point, block.body);
878 nodes_to_remove.insert(&cond);
882 TraversingVisitor::visit(cond);
885 void ConstantConditionEliminator::visit(Iteration &iter)
889 ConstantStatus result = check_constant_condition(*iter.condition);
890 if(result==CONSTANT_FALSE)
892 nodes_to_remove.insert(&iter);
897 TraversingVisitor::visit(iter);
901 UnreachableCodeRemover::UnreachableCodeRemover():
905 bool UnreachableCodeRemover::apply(Stage &stage)
907 stage.content.visit(*this);
908 NodeRemover().apply(stage, unreachable_nodes);
909 return !unreachable_nodes.empty();
912 void UnreachableCodeRemover::visit(Block &block)
914 NodeList<Statement>::iterator i = block.body.begin();
915 for(; (reachable && i!=block.body.end()); ++i)
917 for(; i!=block.body.end(); ++i)
918 unreachable_nodes.insert(i->get());
921 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
923 TraversingVisitor::visit(func);
927 void UnreachableCodeRemover::visit(Conditional &cond)
929 cond.body.visit(*this);
930 bool reachable_if_true = reachable;
932 cond.else_body.visit(*this);
934 reachable |= reachable_if_true;
937 void UnreachableCodeRemover::visit(Iteration &iter)
939 TraversingVisitor::visit(iter);
941 /* Always consider code after a loop reachable, since there's no checking
942 for whether the loop executes. */
947 bool UnusedTypeRemover::apply(Stage &stage)
949 stage.content.visit(*this);
950 NodeRemover().apply(stage, unused_nodes);
951 return !unused_nodes.empty();
954 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
956 unused_nodes.erase(expr->type);
957 TraversingVisitor::visit(expr);
960 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
963 unused_nodes.erase(type.base_type);
964 unused_nodes.insert(&type);
967 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
970 unused_nodes.erase(type.base_type);
971 unused_nodes.insert(&type);
974 void UnusedTypeRemover::visit(StructDeclaration &strct)
976 unused_nodes.insert(&strct);
977 TraversingVisitor::visit(strct);
980 void UnusedTypeRemover::visit(VariableDeclaration &var)
982 unused_nodes.erase(var.type_declaration);
983 TraversingVisitor::visit(var);
986 void UnusedTypeRemover::visit(InterfaceBlock &iface)
988 unused_nodes.erase(iface.type_declaration);
991 void UnusedTypeRemover::visit(FunctionDeclaration &func)
993 unused_nodes.erase(func.return_type_declaration);
994 TraversingVisitor::visit(func);
998 UnusedVariableRemover::UnusedVariableRemover():
1002 assignment_target(false),
1003 r_side_effects(false),
1005 composite_reference(false)
1008 bool UnusedVariableRemover::apply(Stage &s)
1011 s.content.visit(*this);
1013 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1014 if(i->used_by.empty())
1015 unused_nodes.insert(i->node);
1017 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1019 if(i->second.output)
1021 /* The last visible assignments of output variables are used by the
1022 next stage or the API. */
1023 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1024 unused_nodes.erase((*j)->node);
1027 if(!i->second.output && !i->second.referenced)
1029 // Don't remove variables from inside interface blocks.
1030 if(!i->second.interface_block)
1031 unused_nodes.insert(i->first);
1033 else if(i->second.interface_block)
1034 // Interface blocks are kept if even one member is used.
1035 unused_nodes.erase(i->second.interface_block);
1038 NodeRemover().apply(s, unused_nodes);
1040 return !unused_nodes.empty();
1043 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1045 VariableInfo &var_info = variables[target.declaration];
1046 var_info.referenced = true;
1047 if(!assignment_target)
1049 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1051 bool covered = true;
1052 for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1054 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1055 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1056 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1058 unsigned index1 = (*i)->target.chain[j]&0x3F;
1059 unsigned index2 = target.chain[j]&0x3F;
1060 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1061 covered = index1&index2;
1062 else if(type1==Assignment::Target::ARRAY && index1<4)
1063 covered = index2&(1<<index1);
1064 else if(type2==Assignment::Target::ARRAY && index2<4)
1065 covered = index1&(1<<index2);
1066 /* If it's some other combination (shouldn't happen), leave
1070 covered = ((*i)->target.chain[j]==target.chain[j]);
1073 (*i)->used_by.push_back(&node);
1078 void UnusedVariableRemover::visit(VariableReference &var)
1080 if(composite_reference)
1081 r_reference.declaration = var.declaration;
1083 referenced(var.declaration, var);
1086 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1088 if(composite_reference)
1089 r_reference.declaration = iface.declaration;
1091 referenced(iface.declaration, iface);
1094 void UnusedVariableRemover::visit_composite(Expression &expr)
1096 if(!composite_reference)
1097 r_reference = Assignment::Target();
1099 SetFlag set_composite(composite_reference);
1103 void UnusedVariableRemover::visit(MemberAccess &memacc)
1105 visit_composite(*memacc.left);
1107 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1109 if(!composite_reference && r_reference.declaration)
1110 referenced(r_reference, memacc);
1113 void UnusedVariableRemover::visit(Swizzle &swizzle)
1115 visit_composite(*swizzle.left);
1118 for(unsigned i=0; i<swizzle.count; ++i)
1119 mask |= 1<<swizzle.components[i];
1120 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1122 if(!composite_reference && r_reference.declaration)
1123 referenced(r_reference, swizzle);
1126 void UnusedVariableRemover::visit(UnaryExpression &unary)
1128 TraversingVisitor::visit(unary);
1129 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1130 r_side_effects = true;
1133 void UnusedVariableRemover::visit(BinaryExpression &binary)
1135 if(binary.oper->token[0]=='[')
1137 visit_composite(*binary.left);
1140 SetFlag clear_assignment(assignment_target, false);
1141 SetFlag clear_composite(composite_reference, false);
1142 binary.right->visit(*this);
1145 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1147 if(!composite_reference && r_reference.declaration)
1148 referenced(r_reference, binary);
1152 SetFlag clear_composite(composite_reference, false);
1153 TraversingVisitor::visit(binary);
1157 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1159 SetFlag clear_composite(composite_reference, false);
1160 TraversingVisitor::visit(ternary);
1163 void UnusedVariableRemover::visit(Assignment &assign)
1166 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1167 assign.left->visit(*this);
1169 assign.right->visit(*this);
1170 r_assignment = &assign;
1171 r_side_effects = true;
1174 void UnusedVariableRemover::visit(FunctionCall &call)
1176 SetFlag clear_composite(composite_reference, false);
1177 TraversingVisitor::visit(call);
1178 /* Treat function calls as having side effects so expression statements
1179 consisting of nothing but a function call won't be optimized away. */
1180 r_side_effects = true;
1182 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1184 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1185 if(i->second.output)
1186 referenced(i->first, call);
1190 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1192 assignments.push_back(AssignmentInfo());
1193 AssignmentInfo &assign_info = assignments.back();
1194 assign_info.node = &node;
1195 assign_info.target = target;
1197 /* An assignment to the target hides any assignments to the same target or
1199 VariableInfo &var_info = variables[target.declaration];
1200 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1202 const Assignment::Target &t = var_info.assignments[i]->target;
1204 bool subfield = (t.chain_len>=target.chain_len);
1205 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1206 subfield = (t.chain[j]==target.chain[j]);
1209 var_info.assignments.erase(var_info.assignments.begin()+i);
1214 var_info.assignments.push_back(&assign_info);
1217 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1220 r_side_effects = false;
1221 TraversingVisitor::visit(expr);
1222 if(r_assignment && r_assignment->target.declaration)
1223 record_assignment(r_assignment->target, expr);
1225 unused_nodes.insert(&expr);
1228 void UnusedVariableRemover::visit(StructDeclaration &strct)
1230 SetFlag set_struct(in_struct);
1231 TraversingVisitor::visit(strct);
1234 void UnusedVariableRemover::visit(VariableDeclaration &var)
1236 TraversingVisitor::visit(var);
1241 VariableInfo &var_info = variables[&var];
1242 var_info.interface_block = interface_block;
1244 /* Mark variables as output if they're used by the next stage or the
1247 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1249 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1251 if(var.init_expression)
1253 var_info.initialized = true;
1254 record_assignment(&var, *var.init_expression);
1258 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1260 VariableInfo &var_info = variables[&iface];
1261 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1264 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1266 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1268 BlockVariableMap::iterator j = variables.find(i->first);
1269 if(j!=variables.end())
1271 /* The merged blocks started as copies of each other so any common
1272 assignments must be in the beginning. */
1274 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1275 if(i->second.assignments[k]!=j->second.assignments[k])
1278 // Remaining assignments are unique to each block; merge them.
1279 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1280 j->second.referenced |= i->second.referenced;
1283 variables.insert(*i);
1287 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1289 if(func.body.body.empty())
1292 BlockVariableMap saved_vars = variables;
1293 // Assignments from other functions should not be visible.
1294 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1295 i->second.assignments.resize(i->second.initialized);
1296 TraversingVisitor::visit(func);
1297 swap(variables, saved_vars);
1298 merge_variables(saved_vars);
1300 /* Always treat function parameters as referenced. Removing unused
1301 parameters is not currently supported. */
1302 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1304 BlockVariableMap::iterator j = variables.find(i->get());
1305 if(j!=variables.end())
1306 j->second.referenced = true;
1310 void UnusedVariableRemover::visit(Conditional &cond)
1312 cond.condition->visit(*this);
1313 BlockVariableMap saved_vars = variables;
1314 cond.body.visit(*this);
1315 swap(saved_vars, variables);
1316 cond.else_body.visit(*this);
1318 /* Visible assignments after the conditional is the union of those visible
1319 at the end of the if and else blocks. If there was no else block, then it's
1320 the union of the if block and the state before it. */
1321 merge_variables(saved_vars);
1324 void UnusedVariableRemover::visit(Iteration &iter)
1326 BlockVariableMap saved_vars = variables;
1327 TraversingVisitor::visit(iter);
1329 /* Merge assignments from the iteration, without clearing previous state.
1330 Further analysis is needed to determine which parts of the iteration body
1331 are always executed, if any. */
1332 merge_variables(saved_vars);
1336 bool UnusedFunctionRemover::apply(Stage &stage)
1338 stage.content.visit(*this);
1339 NodeRemover().apply(stage, unused_nodes);
1340 return !unused_nodes.empty();
1343 void UnusedFunctionRemover::visit(FunctionCall &call)
1345 TraversingVisitor::visit(call);
1347 unused_nodes.erase(call.declaration);
1348 if(call.declaration && call.declaration->definition!=call.declaration)
1349 used_definitions.insert(call.declaration->definition);
1352 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1354 TraversingVisitor::visit(func);
1356 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1357 unused_nodes.insert(&func);