1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
11 ConstantSpecializer::ConstantSpecializer():
15 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
18 stage.content.visit(*this);
21 void ConstantSpecializer::visit(VariableDeclaration &var)
23 bool specializable = false;
26 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
27 for(vector<Layout::Qualifier>::iterator i=qualifiers.begin(); (!specializable && i!=qualifiers.end()); ++i)
28 if(i->name=="constant_id")
34 if(qualifiers.empty())
40 map<string, int>::const_iterator i = values->find(var.name);
43 RefPtr<Literal> literal = new Literal;
46 literal->token = (i->second ? "true" : "false");
47 literal->value = static_cast<bool>(i->second);
49 else if(var.type=="int")
51 literal->token = lexical_cast<string>(i->second);
52 literal->value = i->second;
54 var.init_expression = literal;
60 InlineableFunctionLocator::InlineableFunctionLocator():
65 void InlineableFunctionLocator::visit(FunctionCall &call)
67 FunctionDeclaration *def = call.declaration;
69 def = def->definition;
73 unsigned &count = refcounts[def];
75 /* Don't inline functions which are called more than once or are called
77 if(count>1 || def==current_function)
78 inlineable.erase(def);
81 TraversingVisitor::visit(call);
84 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
86 bool has_out_params = false;
87 for(NodeArray<VariableDeclaration>::const_iterator i=func.parameters.begin(); (!has_out_params && i!=func.parameters.end()); ++i)
88 has_out_params = ((*i)->interface=="out");
90 unsigned &count = refcounts[func.definition];
91 if(count<=1 && !has_out_params)
92 inlineable.insert(func.definition);
94 SetForScope<FunctionDeclaration *> set(current_function, &func);
96 TraversingVisitor::visit(func);
99 void InlineableFunctionLocator::visit(Conditional &cond)
101 TraversingVisitor::visit(cond);
102 inlineable.erase(current_function);
105 void InlineableFunctionLocator::visit(Iteration &iter)
107 TraversingVisitor::visit(iter);
108 inlineable.erase(current_function);
111 void InlineableFunctionLocator::visit(Return &ret)
113 TraversingVisitor::visit(ret);
115 inlineable.erase(current_function);
120 InlineContentInjector::InlineContentInjector():
125 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
127 source_func = call.declaration->definition;
129 // Collect all declarations the inlined function depends on.
131 source_func->visit(*this);
133 /* Populate referenced_names from the target function so we can rename
134 variables from the inlined function that would conflict. */
136 target_func.visit(*this);
138 /* Inline and rename passes must be interleaved so used variable names are
139 known when inlining the return statement. */
141 staging_block.parent = &tgt_blk;
142 staging_block.variables.clear();
144 std::vector<RefPtr<VariableDeclaration> > params;
145 params.reserve(source_func->parameters.size());
146 for(NodeArray<VariableDeclaration>::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i)
148 RefPtr<VariableDeclaration> var = (*i)->clone();
149 var->interface.clear();
151 SetForScope<Pass> set_pass(pass, RENAME);
154 staging_block.body.push_back_nocopy(var);
155 params.push_back(var);
158 for(NodeList<Statement>::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i)
160 r_inlined_statement = 0;
162 if(!r_inlined_statement)
163 r_inlined_statement = (*i)->clone();
165 SetForScope<Pass> set_pass(pass, RENAME);
166 r_inlined_statement->visit(*this);
168 staging_block.body.push_back_nocopy(r_inlined_statement);
171 /* Now collect names from the staging block. Local variables that would
172 have conflicted with the target function were renamed earlier. */
174 referenced_names.clear();
175 staging_block.variables.clear();
176 staging_block.visit(*this);
178 /* Rename variables in the target function so they don't interfere with
179 global identifiers used by the source function. */
181 staging_block.parent = source_func->body.parent;
182 target_func.visit(*this);
184 // Put the argument expressions in place after all renaming has been done.
185 for(unsigned i=0; i<source_func->parameters.size(); ++i)
186 params[i]->init_expression = call.arguments[i]->clone();
188 tgt_blk.body.splice(ins_pt, staging_block.body);
190 NodeReorderer().apply(stage, target_func, dependencies);
192 return r_result_name;
195 void InlineContentInjector::visit(VariableReference &var)
199 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
200 if(i!=staging_block.variables.end())
201 var.name = i->second->name;
203 else if(pass==DEPENDS && var.declaration)
205 dependencies.insert(var.declaration);
206 var.declaration->visit(*this);
208 else if(pass==REFERENCED)
209 referenced_names.insert(var.name);
212 void InlineContentInjector::visit(InterfaceBlockReference &iface)
214 if(pass==DEPENDS && iface.declaration)
216 dependencies.insert(iface.declaration);
217 iface.declaration->visit(*this);
219 else if(pass==REFERENCED)
220 referenced_names.insert(iface.name);
223 void InlineContentInjector::visit(FunctionCall &call)
225 if(pass==DEPENDS && call.declaration)
226 dependencies.insert(call.declaration);
227 else if(pass==REFERENCED)
228 referenced_names.insert(call.name);
229 TraversingVisitor::visit(call);
232 void InlineContentInjector::visit(VariableDeclaration &var)
234 TraversingVisitor::visit(var);
238 /* Check against conflicts with the other context as well as variables
239 already renamed here. */
240 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
241 staging_block.variables[var.name] = &var;
244 string mapped_name = get_unused_variable_name(staging_block, var.name);
245 if(mapped_name!=var.name)
247 staging_block.variables[mapped_name] = &var;
248 var.name = mapped_name;
252 else if(pass==DEPENDS && var.type_declaration)
254 dependencies.insert(var.type_declaration);
255 var.type_declaration->visit(*this);
257 else if(pass==REFERENCED)
258 referenced_names.insert(var.type);
261 void InlineContentInjector::visit(Return &ret)
263 TraversingVisitor::visit(ret);
265 if(pass==INLINE && ret.expression)
267 // Create a new variable to hold the return value of the inlined function.
268 r_result_name = get_unused_variable_name(staging_block, "_return");
269 RefPtr<VariableDeclaration> var = new VariableDeclaration;
270 var->source = ret.source;
271 var->line = ret.line;
272 var->type = source_func->return_type;
273 var->name = r_result_name;
274 var->init_expression = ret.expression->clone();
275 r_inlined_statement = var;
280 FunctionInliner::FunctionInliner():
282 r_any_inlined(false),
283 r_inlined_here(false)
286 bool FunctionInliner::apply(Stage &s)
289 inlineable = InlineableFunctionLocator().apply(s);
290 r_any_inlined = false;
291 s.content.visit(*this);
292 return r_any_inlined;
295 void FunctionInliner::visit(RefPtr<Expression> &ptr)
301 ptr = r_inline_result;
302 r_any_inlined = true;
307 void FunctionInliner::visit(Block &block)
309 SetForScope<Block *> set_block(current_block, &block);
310 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
311 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
318 void FunctionInliner::visit(FunctionCall &call)
320 for(NodeArray<Expression>::iterator i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
326 FunctionDeclaration *def = call.declaration;
328 def = def->definition;
330 if(def && inlineable.count(def))
332 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
334 // This will later get removed by UnusedVariableRemover.
335 if(result_name.empty())
336 result_name = "_msp_unused_from_inline";
338 RefPtr<VariableReference> ref = new VariableReference;
339 ref->name = result_name;
340 r_inline_result = ref;
342 /* Inlined variables need to be resolved before this function can be
344 inlineable.erase(current_function);
345 r_inlined_here = true;
349 void FunctionInliner::visit(FunctionDeclaration &func)
351 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
352 TraversingVisitor::visit(func);
353 r_inlined_here = false;
356 void FunctionInliner::visit(Iteration &iter)
358 /* Visit the initialization statement before entering the loop body so the
359 inlined statements get inserted outside. */
360 if(iter.init_statement)
361 iter.init_statement->visit(*this);
363 SetForScope<Block *> set_block(current_block, &iter.body);
364 /* Skip the condition and loop expression parts because they're not properly
365 inside the body block. Inlining anything into them will require a more
366 comprehensive transformation. */
367 iter.body.visit(*this);
371 ExpressionInliner::ExpressionInliner():
373 r_any_inlined(false),
376 iteration_init(false),
381 bool ExpressionInliner::apply(Stage &s)
383 s.content.visit(*this);
384 return r_any_inlined;
387 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
390 r_any_inlined = true;
393 void ExpressionInliner::visit(Block &block)
395 TraversingVisitor::visit(block);
397 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
399 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
400 for(; (j!=expressions.end() && j->first.declaration==i->second); )
402 if(j->second.expression && j->second.inline_point)
403 inline_expression(*j->second.expression, *j->second.inline_point);
405 expressions.erase(j++);
409 /* Expressions assigned in this block may depend on local variables of the
410 block. If this is a conditionally executed block, the assignments might not
411 always happen. Mark the expressions as not available to any outer blocks. */
412 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
413 if(i->second.assign_scope==&block)
414 i->second.available = false;
417 void ExpressionInliner::visit(RefPtr<Expression> &expr)
421 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
423 if(iteration_body && !r_ref_info->trivial)
425 /* Don't inline non-trivial expressions which were assigned outside
426 an iteration statement. The iteration may run multiple times, which
427 would cause the expression to also be evaluated multiple times. */
428 Block *i = r_ref_info->assign_scope;
429 for(; (i && i!=iteration_body); i=i->parent) ;
434 if(r_ref_info->trivial)
435 inline_expression(*r_ref_info->expression, expr);
437 /* Record the inline point for a non-trivial expression but don't
438 inline it yet. It might turn out it shouldn't be inlined after all. */
439 r_ref_info->inline_point = &expr;
445 void ExpressionInliner::visit(VariableReference &var)
449 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
450 if(i!=expressions.end())
452 /* If a non-trivial expression is referenced multiple times, don't
454 if(i->second.inline_point && !i->second.trivial)
455 i->second.expression = 0;
456 /* Mutating expressions are analogous to self-referencing assignments
457 and prevent inlining. */
459 i->second.expression = 0;
460 r_ref_info = &i->second;
465 void ExpressionInliner::visit(MemberAccess &memacc)
471 void ExpressionInliner::visit(Swizzle &swizzle)
477 void ExpressionInliner::visit(UnaryExpression &unary)
479 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
480 visit(unary.expression);
484 void ExpressionInliner::visit(BinaryExpression &binary)
488 SetFlag clear_target(mutating, false);
494 void ExpressionInliner::visit(Assignment &assign)
497 SetFlag set_target(mutating);
503 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
504 if(i!=expressions.end())
506 /* Self-referencing assignments can't be inlined without additional
507 work. Just clear any previous expression. */
508 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
509 i->second.assign_scope = current_block;
510 i->second.inline_point = 0;
511 i->second.available = true;
517 void ExpressionInliner::visit(TernaryExpression &ternary)
519 visit(ternary.condition);
520 visit(ternary.true_expr);
521 visit(ternary.false_expr);
525 void ExpressionInliner::visit(FunctionCall &call)
527 TraversingVisitor::visit(call);
531 void ExpressionInliner::visit(VariableDeclaration &var)
535 TraversingVisitor::visit(var);
537 bool constant = var.constant;
538 if(constant && var.layout)
540 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
541 constant = (i->name!="constant_id");
544 /* Only inline global variables if they're constant and have trivial
545 initializers. Non-constant variables could change in ways which are hard to
546 analyze and non-trivial expressions could be expensive to inline. */
547 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
549 ExpressionInfo &info = expressions[&var];
550 /* Assume variables declared in an iteration initialization statement
551 will have their values change throughout the iteration. */
552 info.expression = (iteration_init ? 0 : var.init_expression.get());
553 info.assign_scope = current_block;
554 info.trivial = r_trivial;
558 void ExpressionInliner::visit(Iteration &iter)
560 SetForScope<Block *> set_block(current_block, &iter.body);
561 if(iter.init_statement)
563 SetFlag set_init(iteration_init);
564 iter.init_statement->visit(*this);
567 SetForScope<Block *> set_body(iteration_body, &iter.body);
569 visit(iter.condition);
570 iter.body.visit(*this);
571 if(iter.loop_expression)
572 visit(iter.loop_expression);
576 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
578 if(value.check_type<bool>())
579 return BasicTypeDeclaration::BOOL;
580 else if(value.check_type<int>())
581 return BasicTypeDeclaration::INT;
582 else if(value.check_type<float>())
583 return BasicTypeDeclaration::FLOAT;
585 return BasicTypeDeclaration::VOID;
589 T ConstantFolder::evaluate_logical(char oper, T left, T right)
593 case '&': return left&right;
594 case '|': return left|right;
595 case '^': return left^right;
601 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
603 switch(oper[0]|oper[1])
605 case '<': return left<right;
606 case '<'|'=': return left<=right;
607 case '>': return left>right;
608 case '>'|'=': return left>=right;
609 default: return false;
614 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
618 case '+': return left+right;
619 case '-': return left-right;
620 case '*': return left*right;
621 case '/': return left/right;
626 void ConstantFolder::set_result(const Variant &value, bool literal)
628 r_constant_value = value;
633 void ConstantFolder::visit(RefPtr<Expression> &expr)
635 r_constant_value = Variant();
638 r_uses_iter_var = false;
640 /* Don't replace literals since they'd only be replaced with an identical
641 literal. Also skip anything that uses an iteration variable, but pass on
642 the result so the Iteration visiting function can handle it. */
643 if(!r_constant || r_literal || r_uses_iter_var)
646 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
647 if(kind==BasicTypeDeclaration::VOID)
653 RefPtr<Literal> literal = new Literal;
654 if(kind==BasicTypeDeclaration::BOOL)
655 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
656 else if(kind==BasicTypeDeclaration::INT)
657 literal->token = lexical_cast<string>(r_constant_value.value<int>());
658 else if(kind==BasicTypeDeclaration::FLOAT)
659 literal->token = lexical_cast<string>(r_constant_value.value<float>());
660 literal->value = r_constant_value;
664 void ConstantFolder::visit(Literal &literal)
666 set_result(literal.value, true);
669 void ConstantFolder::visit(VariableReference &var)
671 /* If an iteration variable is initialized with a constant value, return
672 that value here for the purpose of evaluating the loop condition for the
674 if(var.declaration==iteration_var)
676 set_result(iter_init_value);
677 r_uses_iter_var = true;
681 void ConstantFolder::visit(MemberAccess &memacc)
683 TraversingVisitor::visit(memacc);
687 void ConstantFolder::visit(Swizzle &swizzle)
689 TraversingVisitor::visit(swizzle);
693 void ConstantFolder::visit(UnaryExpression &unary)
695 TraversingVisitor::visit(unary);
696 bool can_fold = r_constant;
701 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
703 char oper = unary.oper->token[0];
704 char oper2 = unary.oper->token[1];
707 if(kind==BasicTypeDeclaration::BOOL)
708 set_result(!r_constant_value.value<bool>());
712 if(kind==BasicTypeDeclaration::INT)
713 set_result(~r_constant_value.value<int>());
715 else if(oper=='-' && !oper2)
717 if(kind==BasicTypeDeclaration::INT)
718 set_result(-r_constant_value.value<int>());
719 else if(kind==BasicTypeDeclaration::FLOAT)
720 set_result(-r_constant_value.value<float>());
724 void ConstantFolder::visit(BinaryExpression &binary)
727 bool left_constant = r_constant;
728 bool left_iter_var = r_uses_iter_var;
729 Variant left_value = r_constant_value;
732 r_uses_iter_var = true;
734 bool can_fold = (left_constant && r_constant);
739 BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
740 BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
741 // Currently only expressions with both sides of equal types are handled.
742 if(left_kind!=right_kind)
745 char oper = binary.oper->token[0];
746 char oper2 = binary.oper->token[1];
747 if(oper=='&' || oper=='|' || oper=='^')
749 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
750 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
751 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
752 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
754 else if((oper=='<' || oper=='>') && oper2!=oper)
756 if(left_kind==BasicTypeDeclaration::INT)
757 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
758 else if(left_kind==BasicTypeDeclaration::FLOAT)
759 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
761 else if((oper=='=' || oper=='!') && oper2=='=')
763 if(left_kind==BasicTypeDeclaration::INT)
764 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
765 if(left_kind==BasicTypeDeclaration::FLOAT)
766 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
768 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
770 if(left_kind==BasicTypeDeclaration::INT)
771 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
772 else if(left_kind==BasicTypeDeclaration::FLOAT)
773 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
775 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
777 if(left_kind!=BasicTypeDeclaration::INT)
781 set_result(left_value.value<int>()%r_constant_value.value<int>());
783 set_result(left_value.value<int>()<<r_constant_value.value<int>());
785 set_result(left_value.value<int>()>>r_constant_value.value<int>());
789 void ConstantFolder::visit(Assignment &assign)
791 TraversingVisitor::visit(assign);
795 void ConstantFolder::visit(TernaryExpression &ternary)
797 TraversingVisitor::visit(ternary);
801 void ConstantFolder::visit(FunctionCall &call)
803 TraversingVisitor::visit(call);
807 void ConstantFolder::visit(VariableDeclaration &var)
809 if(iteration_init && var.init_expression)
811 visit(var.init_expression);
814 /* Record the value of a constant initialization expression of an
815 iteration, so it can be used to evaluate the loop condition. */
816 iteration_var = &var;
817 iter_init_value = r_constant_value;
821 TraversingVisitor::visit(var);
824 void ConstantFolder::visit(Iteration &iter)
826 SetForScope<Block *> set_block(current_block, &iter.body);
828 /* The iteration variable is not normally inlined into expressions, so we
829 process it specially here. If the initial value causes the loop condition
830 to evaluate to false, then the expression can be folded. */
832 if(iter.init_statement)
834 SetFlag set_init(iteration_init);
835 iter.init_statement->visit(*this);
840 visit(iter.condition);
841 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
843 RefPtr<Literal> literal = new Literal;
844 literal->token = "false";
845 literal->value = r_constant_value;
846 iter.condition = literal;
851 iter.body.visit(*this);
852 if(iter.loop_expression)
853 visit(iter.loop_expression);
857 void ConstantConditionEliminator::apply(Stage &stage)
859 stage.content.visit(*this);
860 NodeRemover().apply(stage, nodes_to_remove);
863 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
865 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
866 if(literal->value.check_type<bool>())
867 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
871 void ConstantConditionEliminator::visit(Block &block)
873 SetForScope<Block *> set_block(current_block, &block);
874 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
881 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
883 r_ternary_result = 0;
886 expr = r_ternary_result;
887 r_ternary_result = 0;
890 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
892 ConstantStatus result = check_constant_condition(*ternary.condition);
893 if(result!=NOT_CONSTANT)
894 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
896 r_ternary_result = 0;
899 void ConstantConditionEliminator::visit(Conditional &cond)
901 ConstantStatus result = check_constant_condition(*cond.condition);
902 if(result!=NOT_CONSTANT)
904 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
905 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
906 current_block->body.splice(insert_point, block.body);
907 nodes_to_remove.insert(&cond);
911 TraversingVisitor::visit(cond);
914 void ConstantConditionEliminator::visit(Iteration &iter)
918 ConstantStatus result = check_constant_condition(*iter.condition);
919 if(result==CONSTANT_FALSE)
921 nodes_to_remove.insert(&iter);
926 TraversingVisitor::visit(iter);
930 bool UnusedTypeRemover::apply(Stage &stage)
932 stage.content.visit(*this);
933 NodeRemover().apply(stage, unused_nodes);
934 return !unused_nodes.empty();
937 void UnusedTypeRemover::visit(Literal &literal)
939 unused_nodes.erase(literal.type);
942 void UnusedTypeRemover::visit(UnaryExpression &unary)
944 unused_nodes.erase(unary.type);
945 TraversingVisitor::visit(unary);
948 void UnusedTypeRemover::visit(BinaryExpression &binary)
950 unused_nodes.erase(binary.type);
951 TraversingVisitor::visit(binary);
954 void UnusedTypeRemover::visit(TernaryExpression &ternary)
956 unused_nodes.erase(ternary.type);
957 TraversingVisitor::visit(ternary);
960 void UnusedTypeRemover::visit(FunctionCall &call)
962 unused_nodes.erase(call.type);
963 TraversingVisitor::visit(call);
966 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
969 unused_nodes.erase(type.base_type);
970 unused_nodes.insert(&type);
973 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
976 unused_nodes.erase(type.base_type);
977 unused_nodes.insert(&type);
980 void UnusedTypeRemover::visit(StructDeclaration &strct)
982 unused_nodes.insert(&strct);
983 TraversingVisitor::visit(strct);
986 void UnusedTypeRemover::visit(VariableDeclaration &var)
988 unused_nodes.erase(var.type_declaration);
991 void UnusedTypeRemover::visit(InterfaceBlock &iface)
993 unused_nodes.erase(iface.type_declaration);
996 void UnusedTypeRemover::visit(FunctionDeclaration &func)
998 unused_nodes.erase(func.return_type_declaration);
999 TraversingVisitor::visit(func);
1003 UnusedVariableRemover::UnusedVariableRemover():
1007 assignment_target(false),
1008 r_side_effects(false)
1011 bool UnusedVariableRemover::apply(Stage &s)
1014 s.content.visit(*this);
1016 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1017 if(i->used_by.empty())
1018 unused_nodes.insert(i->node);
1020 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
1021 if(i->second->instance_name.empty())
1022 unused_nodes.insert(i->second);
1024 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1026 if(i->second.output)
1028 /* The last visible assignments of output variables are used by the
1029 next stage or the API. */
1030 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1031 unused_nodes.erase((*j)->node);
1034 if(!i->second.output && !i->second.referenced)
1036 // Don't remove variables from inside interface blocks.
1037 if(!i->second.interface_block)
1038 unused_nodes.insert(i->first);
1040 else if(i->second.interface_block)
1041 // Interface blocks are kept if even one member is used.
1042 unused_nodes.erase(i->second.interface_block);
1045 NodeRemover().apply(s, unused_nodes);
1047 return !unused_nodes.empty();
1050 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1052 VariableInfo &var_info = variables[target.declaration];
1053 var_info.referenced = true;
1054 if(!assignment_target)
1056 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1057 (*i)->used_by.push_back(&node);
1061 void UnusedVariableRemover::visit(VariableReference &var)
1063 referenced(var.declaration, var);
1066 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1068 referenced(iface.declaration, iface);
1071 void UnusedVariableRemover::visit(UnaryExpression &unary)
1073 TraversingVisitor::visit(unary);
1074 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1075 r_side_effects = true;
1078 void UnusedVariableRemover::visit(BinaryExpression &binary)
1080 if(binary.oper->token[0]=='[')
1082 binary.left->visit(*this);
1083 SetFlag set(assignment_target, false);
1084 binary.right->visit(*this);
1087 TraversingVisitor::visit(binary);
1090 void UnusedVariableRemover::visit(Assignment &assign)
1093 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1094 assign.left->visit(*this);
1096 assign.right->visit(*this);
1097 r_assignment = &assign;
1098 r_side_effects = true;
1101 void UnusedVariableRemover::visit(FunctionCall &call)
1103 TraversingVisitor::visit(call);
1104 /* Treat function calls as having side effects so expression statements
1105 consisting of nothing but a function call won't be optimized away. */
1106 r_side_effects = true;
1108 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1110 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1111 if(i->second.output)
1112 referenced(i->first, call);
1116 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1118 assignments.push_back(AssignmentInfo());
1119 AssignmentInfo &assign_info = assignments.back();
1120 assign_info.node = &node;
1121 assign_info.target = target;
1123 /* An assignment to the target hides any assignments to the same target or
1125 VariableInfo &var_info = variables[target.declaration];
1126 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1128 const Assignment::Target &t = var_info.assignments[i]->target;
1130 bool subfield = (t.chain_len>=target.chain_len);
1131 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1132 subfield = (t.chain[j]==target.chain[j]);
1135 var_info.assignments.erase(var_info.assignments.begin()+i);
1140 var_info.assignments.push_back(&assign_info);
1143 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1146 r_side_effects = false;
1147 TraversingVisitor::visit(expr);
1148 if(r_assignment && r_assignment->target.declaration)
1149 record_assignment(r_assignment->target, expr);
1151 unused_nodes.insert(&expr);
1154 void UnusedVariableRemover::visit(VariableDeclaration &var)
1156 VariableInfo &var_info = variables[&var];
1157 var_info.interface_block = interface_block;
1159 /* Mark variables as output if they're used by the next stage or the
1162 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1164 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1166 if(var.init_expression)
1168 var_info.initialized = true;
1169 record_assignment(&var, *var.init_expression);
1171 TraversingVisitor::visit(var);
1174 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1176 if(iface.instance_name.empty())
1178 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1179 iface.struct_declaration->members.visit(*this);
1183 VariableInfo &var_info = variables[&iface];
1184 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1188 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1190 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1192 BlockVariableMap::iterator j = variables.find(i->first);
1193 if(j!=variables.end())
1195 /* The merged blocks started as copies of each other so any common
1196 assignments must be in the beginning. */
1198 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1199 if(i->second.assignments[k]!=j->second.assignments[k])
1202 // Remaining assignments are unique to each block; merge them.
1203 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1204 j->second.referenced |= i->second.referenced;
1207 variables.insert(*i);
1211 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1213 if(func.body.body.empty())
1216 BlockVariableMap saved_vars = variables;
1217 // Assignments from other functions should not be visible.
1218 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1219 i->second.assignments.resize(i->second.initialized);
1220 TraversingVisitor::visit(func);
1221 swap(variables, saved_vars);
1222 merge_variables(saved_vars);
1224 /* Always treat function parameters as referenced. Removing unused
1225 parameters is not currently supported. */
1226 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1228 BlockVariableMap::iterator j = variables.find(i->get());
1229 if(j!=variables.end())
1230 j->second.referenced = true;
1234 void UnusedVariableRemover::visit(Conditional &cond)
1236 cond.condition->visit(*this);
1237 BlockVariableMap saved_vars = variables;
1238 cond.body.visit(*this);
1239 swap(saved_vars, variables);
1240 cond.else_body.visit(*this);
1242 /* Visible assignments after the conditional is the union of those visible
1243 at the end of the if and else blocks. If there was no else block, then it's
1244 the union of the if block and the state before it. */
1245 merge_variables(saved_vars);
1248 void UnusedVariableRemover::visit(Iteration &iter)
1250 BlockVariableMap saved_vars = variables;
1251 TraversingVisitor::visit(iter);
1253 /* Merge assignments from the iteration, without clearing previous state.
1254 Further analysis is needed to determine which parts of the iteration body
1255 are always executed, if any. */
1256 merge_variables(saved_vars);
1260 bool UnusedFunctionRemover::apply(Stage &stage)
1262 stage.content.visit(*this);
1263 NodeRemover().apply(stage, unused_nodes);
1264 return !unused_nodes.empty();
1267 void UnusedFunctionRemover::visit(FunctionCall &call)
1269 TraversingVisitor::visit(call);
1271 unused_nodes.erase(call.declaration);
1272 if(call.declaration && call.declaration->definition!=call.declaration)
1273 used_definitions.insert(call.declaration->definition);
1276 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1278 TraversingVisitor::visit(func);
1280 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1281 unused_nodes.insert(&func);