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::ExpressionInfo::ExpressionInfo():
380 ExpressionInliner::ExpressionInliner():
382 r_any_inlined(false),
385 iteration_init(false),
390 bool ExpressionInliner::apply(Stage &s)
392 s.content.visit(*this);
393 return r_any_inlined;
396 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
399 r_any_inlined = true;
402 void ExpressionInliner::visit(Block &block)
404 TraversingVisitor::visit(block);
406 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
408 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
409 for(; (j!=expressions.end() && j->first.declaration==i->second); )
411 if(j->second.expression && j->second.inline_point)
412 inline_expression(*j->second.expression, *j->second.inline_point);
414 expressions.erase(j++);
418 /* Expressions assigned in this block may depend on local variables of the
419 block. If this is a conditionally executed block, the assignments might not
420 always happen. Mark the expressions as not available to any outer blocks. */
421 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
422 if(i->second.assign_scope==&block)
423 i->second.available = false;
426 void ExpressionInliner::visit(RefPtr<Expression> &expr)
430 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
432 if(iteration_body && !r_ref_info->trivial)
434 /* Don't inline non-trivial expressions which were assigned outside
435 an iteration statement. The iteration may run multiple times, which
436 would cause the expression to also be evaluated multiple times. */
437 Block *i = r_ref_info->assign_scope;
438 for(; (i && i!=iteration_body); i=i->parent) ;
443 if(r_ref_info->trivial)
444 inline_expression(*r_ref_info->expression, expr);
446 /* Record the inline point for a non-trivial expression but don't
447 inline it yet. It might turn out it shouldn't be inlined after all. */
448 r_ref_info->inline_point = &expr;
454 void ExpressionInliner::visit(VariableReference &var)
458 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
459 if(i!=expressions.end())
461 /* If a non-trivial expression is referenced multiple times, don't
463 if(i->second.inline_point && !i->second.trivial)
464 i->second.expression = 0;
465 /* Mutating expressions are analogous to self-referencing assignments
466 and prevent inlining. */
468 i->second.expression = 0;
469 r_ref_info = &i->second;
474 void ExpressionInliner::visit(MemberAccess &memacc)
480 void ExpressionInliner::visit(Swizzle &swizzle)
486 void ExpressionInliner::visit(UnaryExpression &unary)
488 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
489 visit(unary.expression);
493 void ExpressionInliner::visit(BinaryExpression &binary)
497 SetFlag clear_target(mutating, false);
503 void ExpressionInliner::visit(Assignment &assign)
506 SetFlag set_target(mutating);
512 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
513 if(i!=expressions.end())
515 /* Self-referencing assignments can't be inlined without additional
516 work. Just clear any previous expression. */
517 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
518 i->second.assign_scope = current_block;
519 i->second.inline_point = 0;
520 i->second.available = true;
526 void ExpressionInliner::visit(TernaryExpression &ternary)
528 visit(ternary.condition);
529 visit(ternary.true_expr);
530 visit(ternary.false_expr);
534 void ExpressionInliner::visit(FunctionCall &call)
536 TraversingVisitor::visit(call);
540 void ExpressionInliner::visit(VariableDeclaration &var)
544 TraversingVisitor::visit(var);
546 bool constant = var.constant;
547 if(constant && var.layout)
549 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
550 constant = (i->name!="constant_id");
553 /* Only inline global variables if they're constant and have trivial
554 initializers. Non-constant variables could change in ways which are hard to
555 analyze and non-trivial expressions could be expensive to inline. */
556 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
558 ExpressionInfo &info = expressions[&var];
559 /* Assume variables declared in an iteration initialization statement
560 will have their values change throughout the iteration. */
561 info.expression = (iteration_init ? 0 : var.init_expression.get());
562 info.assign_scope = current_block;
563 info.trivial = r_trivial;
567 void ExpressionInliner::visit(Iteration &iter)
569 SetForScope<Block *> set_block(current_block, &iter.body);
570 if(iter.init_statement)
572 SetFlag set_init(iteration_init);
573 iter.init_statement->visit(*this);
576 SetForScope<Block *> set_body(iteration_body, &iter.body);
578 visit(iter.condition);
579 iter.body.visit(*this);
580 if(iter.loop_expression)
581 visit(iter.loop_expression);
585 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
587 if(value.check_type<bool>())
588 return BasicTypeDeclaration::BOOL;
589 else if(value.check_type<int>())
590 return BasicTypeDeclaration::INT;
591 else if(value.check_type<float>())
592 return BasicTypeDeclaration::FLOAT;
594 return BasicTypeDeclaration::VOID;
598 T ConstantFolder::evaluate_logical(char oper, T left, T right)
602 case '&': return left&right;
603 case '|': return left|right;
604 case '^': return left^right;
610 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
612 switch(oper[0]|oper[1])
614 case '<': return left<right;
615 case '<'|'=': return left<=right;
616 case '>': return left>right;
617 case '>'|'=': return left>=right;
618 default: return false;
623 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
627 case '+': return left+right;
628 case '-': return left-right;
629 case '*': return left*right;
630 case '/': return left/right;
635 void ConstantFolder::set_result(const Variant &value, bool literal)
637 r_constant_value = value;
642 void ConstantFolder::visit(RefPtr<Expression> &expr)
644 r_constant_value = Variant();
647 r_uses_iter_var = false;
649 /* Don't replace literals since they'd only be replaced with an identical
650 literal. Also skip anything that uses an iteration variable, but pass on
651 the result so the Iteration visiting function can handle it. */
652 if(!r_constant || r_literal || r_uses_iter_var)
655 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
656 if(kind==BasicTypeDeclaration::VOID)
662 RefPtr<Literal> literal = new Literal;
663 if(kind==BasicTypeDeclaration::BOOL)
664 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
665 else if(kind==BasicTypeDeclaration::INT)
666 literal->token = lexical_cast<string>(r_constant_value.value<int>());
667 else if(kind==BasicTypeDeclaration::FLOAT)
668 literal->token = lexical_cast<string>(r_constant_value.value<float>());
669 literal->value = r_constant_value;
673 void ConstantFolder::visit(Literal &literal)
675 set_result(literal.value, true);
678 void ConstantFolder::visit(VariableReference &var)
680 /* If an iteration variable is initialized with a constant value, return
681 that value here for the purpose of evaluating the loop condition for the
683 if(var.declaration==iteration_var)
685 set_result(iter_init_value);
686 r_uses_iter_var = true;
690 void ConstantFolder::visit(MemberAccess &memacc)
692 TraversingVisitor::visit(memacc);
696 void ConstantFolder::visit(Swizzle &swizzle)
698 TraversingVisitor::visit(swizzle);
702 void ConstantFolder::visit(UnaryExpression &unary)
704 TraversingVisitor::visit(unary);
705 bool can_fold = r_constant;
710 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
712 char oper = unary.oper->token[0];
713 char oper2 = unary.oper->token[1];
716 if(kind==BasicTypeDeclaration::BOOL)
717 set_result(!r_constant_value.value<bool>());
721 if(kind==BasicTypeDeclaration::INT)
722 set_result(~r_constant_value.value<int>());
724 else if(oper=='-' && !oper2)
726 if(kind==BasicTypeDeclaration::INT)
727 set_result(-r_constant_value.value<int>());
728 else if(kind==BasicTypeDeclaration::FLOAT)
729 set_result(-r_constant_value.value<float>());
733 void ConstantFolder::visit(BinaryExpression &binary)
736 bool left_constant = r_constant;
737 bool left_iter_var = r_uses_iter_var;
738 Variant left_value = r_constant_value;
741 r_uses_iter_var = true;
743 bool can_fold = (left_constant && r_constant);
748 BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
749 BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
750 // Currently only expressions with both sides of equal types are handled.
751 if(left_kind!=right_kind)
754 char oper = binary.oper->token[0];
755 char oper2 = binary.oper->token[1];
756 if(oper=='&' || oper=='|' || oper=='^')
758 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
759 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
760 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
761 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
763 else if((oper=='<' || oper=='>') && oper2!=oper)
765 if(left_kind==BasicTypeDeclaration::INT)
766 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
767 else if(left_kind==BasicTypeDeclaration::FLOAT)
768 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
770 else if((oper=='=' || oper=='!') && oper2=='=')
772 if(left_kind==BasicTypeDeclaration::INT)
773 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
774 if(left_kind==BasicTypeDeclaration::FLOAT)
775 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
777 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
779 if(left_kind==BasicTypeDeclaration::INT)
780 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
781 else if(left_kind==BasicTypeDeclaration::FLOAT)
782 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
784 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
786 if(left_kind!=BasicTypeDeclaration::INT)
790 set_result(left_value.value<int>()%r_constant_value.value<int>());
792 set_result(left_value.value<int>()<<r_constant_value.value<int>());
794 set_result(left_value.value<int>()>>r_constant_value.value<int>());
798 void ConstantFolder::visit(Assignment &assign)
800 TraversingVisitor::visit(assign);
804 void ConstantFolder::visit(TernaryExpression &ternary)
806 TraversingVisitor::visit(ternary);
810 void ConstantFolder::visit(FunctionCall &call)
812 TraversingVisitor::visit(call);
816 void ConstantFolder::visit(VariableDeclaration &var)
818 if(iteration_init && var.init_expression)
820 visit(var.init_expression);
823 /* Record the value of a constant initialization expression of an
824 iteration, so it can be used to evaluate the loop condition. */
825 iteration_var = &var;
826 iter_init_value = r_constant_value;
830 TraversingVisitor::visit(var);
833 void ConstantFolder::visit(Iteration &iter)
835 SetForScope<Block *> set_block(current_block, &iter.body);
837 /* The iteration variable is not normally inlined into expressions, so we
838 process it specially here. If the initial value causes the loop condition
839 to evaluate to false, then the expression can be folded. */
841 if(iter.init_statement)
843 SetFlag set_init(iteration_init);
844 iter.init_statement->visit(*this);
849 visit(iter.condition);
850 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
852 RefPtr<Literal> literal = new Literal;
853 literal->token = "false";
854 literal->value = r_constant_value;
855 iter.condition = literal;
860 iter.body.visit(*this);
861 if(iter.loop_expression)
862 visit(iter.loop_expression);
866 void ConstantConditionEliminator::apply(Stage &stage)
868 stage.content.visit(*this);
869 NodeRemover().apply(stage, nodes_to_remove);
872 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
874 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
875 if(literal->value.check_type<bool>())
876 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
880 void ConstantConditionEliminator::visit(Block &block)
882 SetForScope<Block *> set_block(current_block, &block);
883 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
890 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
892 r_ternary_result = 0;
895 expr = r_ternary_result;
896 r_ternary_result = 0;
899 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
901 ConstantStatus result = check_constant_condition(*ternary.condition);
902 if(result!=NOT_CONSTANT)
903 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
905 r_ternary_result = 0;
908 void ConstantConditionEliminator::visit(Conditional &cond)
910 ConstantStatus result = check_constant_condition(*cond.condition);
911 if(result!=NOT_CONSTANT)
913 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
914 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
915 current_block->body.splice(insert_point, block.body);
916 nodes_to_remove.insert(&cond);
920 TraversingVisitor::visit(cond);
923 void ConstantConditionEliminator::visit(Iteration &iter)
927 ConstantStatus result = check_constant_condition(*iter.condition);
928 if(result==CONSTANT_FALSE)
930 nodes_to_remove.insert(&iter);
935 TraversingVisitor::visit(iter);
939 bool UnusedTypeRemover::apply(Stage &stage)
941 stage.content.visit(*this);
942 NodeRemover().apply(stage, unused_nodes);
943 return !unused_nodes.empty();
946 void UnusedTypeRemover::visit(Literal &literal)
948 unused_nodes.erase(literal.type);
951 void UnusedTypeRemover::visit(UnaryExpression &unary)
953 unused_nodes.erase(unary.type);
954 TraversingVisitor::visit(unary);
957 void UnusedTypeRemover::visit(BinaryExpression &binary)
959 unused_nodes.erase(binary.type);
960 TraversingVisitor::visit(binary);
963 void UnusedTypeRemover::visit(TernaryExpression &ternary)
965 unused_nodes.erase(ternary.type);
966 TraversingVisitor::visit(ternary);
969 void UnusedTypeRemover::visit(FunctionCall &call)
971 unused_nodes.erase(call.type);
972 TraversingVisitor::visit(call);
975 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
978 unused_nodes.erase(type.base_type);
979 unused_nodes.insert(&type);
982 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
985 unused_nodes.erase(type.base_type);
986 unused_nodes.insert(&type);
989 void UnusedTypeRemover::visit(StructDeclaration &strct)
991 unused_nodes.insert(&strct);
992 TraversingVisitor::visit(strct);
995 void UnusedTypeRemover::visit(VariableDeclaration &var)
997 unused_nodes.erase(var.type_declaration);
1000 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1002 unused_nodes.erase(iface.type_declaration);
1005 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1007 unused_nodes.erase(func.return_type_declaration);
1008 TraversingVisitor::visit(func);
1012 UnusedVariableRemover::UnusedVariableRemover():
1016 assignment_target(false),
1017 r_side_effects(false)
1020 bool UnusedVariableRemover::apply(Stage &s)
1023 s.content.visit(*this);
1025 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1026 if(i->used_by.empty())
1027 unused_nodes.insert(i->node);
1029 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
1030 if(i->second->instance_name.empty())
1031 unused_nodes.insert(i->second);
1033 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1035 if(i->second.output)
1037 /* The last visible assignments of output variables are used by the
1038 next stage or the API. */
1039 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1040 unused_nodes.erase((*j)->node);
1043 if(!i->second.output && !i->second.referenced)
1045 // Don't remove variables from inside interface blocks.
1046 if(!i->second.interface_block)
1047 unused_nodes.insert(i->first);
1049 else if(i->second.interface_block)
1050 // Interface blocks are kept if even one member is used.
1051 unused_nodes.erase(i->second.interface_block);
1054 NodeRemover().apply(s, unused_nodes);
1056 return !unused_nodes.empty();
1059 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1061 VariableInfo &var_info = variables[target.declaration];
1062 var_info.referenced = true;
1063 if(!assignment_target)
1065 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1066 (*i)->used_by.push_back(&node);
1070 void UnusedVariableRemover::visit(VariableReference &var)
1072 referenced(var.declaration, var);
1075 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1077 referenced(iface.declaration, iface);
1080 void UnusedVariableRemover::visit(UnaryExpression &unary)
1082 TraversingVisitor::visit(unary);
1083 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1084 r_side_effects = true;
1087 void UnusedVariableRemover::visit(BinaryExpression &binary)
1089 if(binary.oper->token[0]=='[')
1091 binary.left->visit(*this);
1092 SetFlag set(assignment_target, false);
1093 binary.right->visit(*this);
1096 TraversingVisitor::visit(binary);
1099 void UnusedVariableRemover::visit(Assignment &assign)
1102 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1103 assign.left->visit(*this);
1105 assign.right->visit(*this);
1106 r_assignment = &assign;
1107 r_side_effects = true;
1110 void UnusedVariableRemover::visit(FunctionCall &call)
1112 TraversingVisitor::visit(call);
1113 /* Treat function calls as having side effects so expression statements
1114 consisting of nothing but a function call won't be optimized away. */
1115 r_side_effects = true;
1117 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1119 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1120 if(i->second.output)
1121 referenced(i->first, call);
1125 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1127 assignments.push_back(AssignmentInfo());
1128 AssignmentInfo &assign_info = assignments.back();
1129 assign_info.node = &node;
1130 assign_info.target = target;
1132 /* An assignment to the target hides any assignments to the same target or
1134 VariableInfo &var_info = variables[target.declaration];
1135 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1137 const Assignment::Target &t = var_info.assignments[i]->target;
1139 bool subfield = (t.chain_len>=target.chain_len);
1140 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1141 subfield = (t.chain[j]==target.chain[j]);
1144 var_info.assignments.erase(var_info.assignments.begin()+i);
1149 var_info.assignments.push_back(&assign_info);
1152 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1155 r_side_effects = false;
1156 TraversingVisitor::visit(expr);
1157 if(r_assignment && r_assignment->target.declaration)
1158 record_assignment(r_assignment->target, expr);
1160 unused_nodes.insert(&expr);
1163 void UnusedVariableRemover::visit(VariableDeclaration &var)
1165 VariableInfo &var_info = variables[&var];
1166 var_info.interface_block = interface_block;
1168 /* Mark variables as output if they're used by the next stage or the
1171 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1173 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1175 if(var.init_expression)
1177 var_info.initialized = true;
1178 record_assignment(&var, *var.init_expression);
1180 TraversingVisitor::visit(var);
1183 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1185 if(iface.instance_name.empty())
1187 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1188 iface.struct_declaration->members.visit(*this);
1192 VariableInfo &var_info = variables[&iface];
1193 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1197 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1199 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1201 BlockVariableMap::iterator j = variables.find(i->first);
1202 if(j!=variables.end())
1204 /* The merged blocks started as copies of each other so any common
1205 assignments must be in the beginning. */
1207 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1208 if(i->second.assignments[k]!=j->second.assignments[k])
1211 // Remaining assignments are unique to each block; merge them.
1212 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1213 j->second.referenced |= i->second.referenced;
1216 variables.insert(*i);
1220 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1222 if(func.body.body.empty())
1225 BlockVariableMap saved_vars = variables;
1226 // Assignments from other functions should not be visible.
1227 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1228 i->second.assignments.resize(i->second.initialized);
1229 TraversingVisitor::visit(func);
1230 swap(variables, saved_vars);
1231 merge_variables(saved_vars);
1233 /* Always treat function parameters as referenced. Removing unused
1234 parameters is not currently supported. */
1235 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1237 BlockVariableMap::iterator j = variables.find(i->get());
1238 if(j!=variables.end())
1239 j->second.referenced = true;
1243 void UnusedVariableRemover::visit(Conditional &cond)
1245 cond.condition->visit(*this);
1246 BlockVariableMap saved_vars = variables;
1247 cond.body.visit(*this);
1248 swap(saved_vars, variables);
1249 cond.else_body.visit(*this);
1251 /* Visible assignments after the conditional is the union of those visible
1252 at the end of the if and else blocks. If there was no else block, then it's
1253 the union of the if block and the state before it. */
1254 merge_variables(saved_vars);
1257 void UnusedVariableRemover::visit(Iteration &iter)
1259 BlockVariableMap saved_vars = variables;
1260 TraversingVisitor::visit(iter);
1262 /* Merge assignments from the iteration, without clearing previous state.
1263 Further analysis is needed to determine which parts of the iteration body
1264 are always executed, if any. */
1265 merge_variables(saved_vars);
1269 bool UnusedFunctionRemover::apply(Stage &stage)
1271 stage.content.visit(*this);
1272 NodeRemover().apply(stage, unused_nodes);
1273 return !unused_nodes.empty();
1276 void UnusedFunctionRemover::visit(FunctionCall &call)
1278 TraversingVisitor::visit(call);
1280 unused_nodes.erase(call.declaration);
1281 if(call.declaration && call.declaration->definition!=call.declaration)
1282 used_definitions.insert(call.declaration->definition);
1285 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1287 TraversingVisitor::visit(func);
1289 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1290 unused_nodes.insert(&func);