1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
11 InlineableFunctionLocator::InlineableFunctionLocator():
16 void InlineableFunctionLocator::visit(FunctionCall &call)
18 FunctionDeclaration *def = call.declaration;
20 def = def->definition;
24 unsigned &count = refcounts[def];
26 /* Don't inline functions which are called more than once or are called
28 if(count>1 || def==current_function)
29 inlineable.erase(def);
32 TraversingVisitor::visit(call);
35 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
37 bool has_out_params = false;
38 for(NodeArray<VariableDeclaration>::const_iterator i=func.parameters.begin(); (!has_out_params && i!=func.parameters.end()); ++i)
39 has_out_params = ((*i)->interface=="out");
41 unsigned &count = refcounts[func.definition];
42 if(count<=1 && !has_out_params)
43 inlineable.insert(func.definition);
45 SetForScope<FunctionDeclaration *> set(current_function, &func);
47 TraversingVisitor::visit(func);
50 void InlineableFunctionLocator::visit(Conditional &cond)
52 TraversingVisitor::visit(cond);
53 inlineable.erase(current_function);
56 void InlineableFunctionLocator::visit(Iteration &iter)
58 TraversingVisitor::visit(iter);
59 inlineable.erase(current_function);
62 void InlineableFunctionLocator::visit(Return &ret)
64 TraversingVisitor::visit(ret);
66 inlineable.erase(current_function);
71 InlineContentInjector::InlineContentInjector():
76 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
78 source_func = call.declaration->definition;
80 // Collect all declarations the inlined function depends on.
82 source_func->visit(*this);
84 /* Populate referenced_names from the target function so we can rename
85 variables from the inlined function that would conflict. */
87 target_func.visit(*this);
89 /* Inline and rename passes must be interleaved so used variable names are
90 known when inlining the return statement. */
92 staging_block.parent = &tgt_blk;
93 staging_block.variables.clear();
95 std::vector<RefPtr<VariableDeclaration> > params;
96 params.reserve(source_func->parameters.size());
97 for(NodeArray<VariableDeclaration>::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i)
99 RefPtr<VariableDeclaration> var = (*i)->clone();
100 var->interface.clear();
102 SetForScope<Pass> set_pass(pass, RENAME);
105 staging_block.body.push_back(0);
106 staging_block.body.back() = var;
107 params.push_back(var);
110 for(NodeList<Statement>::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i)
112 r_inlined_statement = 0;
114 if(!r_inlined_statement)
115 r_inlined_statement = (*i)->clone();
117 SetForScope<Pass> set_pass(pass, RENAME);
118 r_inlined_statement->visit(*this);
120 staging_block.body.push_back(0);
121 staging_block.body.back() = r_inlined_statement;
124 /* Now collect names from the staging block. Local variables that would
125 have conflicted with the target function were renamed earlier. */
127 referenced_names.clear();
128 staging_block.variables.clear();
129 staging_block.visit(*this);
131 /* Rename variables in the target function so they don't interfere with
132 global identifiers used by the source function. */
134 staging_block.parent = source_func->body.parent;
135 target_func.visit(*this);
137 // Put the argument expressions in place after all renaming has been done.
138 for(unsigned i=0; i<source_func->parameters.size(); ++i)
139 params[i]->init_expression = call.arguments[i]->clone();
141 tgt_blk.body.splice(ins_pt, staging_block.body);
143 NodeReorderer().apply(stage, target_func, dependencies);
145 return r_result_name;
148 void InlineContentInjector::visit(VariableReference &var)
152 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
153 if(i!=staging_block.variables.end())
154 var.name = i->second->name;
156 else if(pass==DEPENDS && var.declaration)
158 dependencies.insert(var.declaration);
159 var.declaration->visit(*this);
161 else if(pass==REFERENCED)
162 referenced_names.insert(var.name);
165 void InlineContentInjector::visit(InterfaceBlockReference &iface)
167 if(pass==DEPENDS && iface.declaration)
169 dependencies.insert(iface.declaration);
170 iface.declaration->visit(*this);
172 else if(pass==REFERENCED)
173 referenced_names.insert(iface.name);
176 void InlineContentInjector::visit(FunctionCall &call)
178 if(pass==DEPENDS && call.declaration)
179 dependencies.insert(call.declaration);
180 else if(pass==REFERENCED)
181 referenced_names.insert(call.name);
182 TraversingVisitor::visit(call);
185 void InlineContentInjector::visit(VariableDeclaration &var)
187 TraversingVisitor::visit(var);
191 staging_block.variables[var.name] = &var;
192 if(referenced_names.count(var.name))
194 string mapped_name = get_unused_variable_name(staging_block, var.name);
195 if(mapped_name!=var.name)
197 staging_block.variables[mapped_name] = &var;
198 var.name = mapped_name;
202 else if(pass==DEPENDS && var.type_declaration)
204 dependencies.insert(var.type_declaration);
205 var.type_declaration->visit(*this);
207 else if(pass==REFERENCED)
208 referenced_names.insert(var.type);
211 void InlineContentInjector::visit(Return &ret)
213 TraversingVisitor::visit(ret);
215 if(pass==INLINE && ret.expression)
217 // Create a new variable to hold the return value of the inlined function.
218 r_result_name = get_unused_variable_name(staging_block, "_return");
219 RefPtr<VariableDeclaration> var = new VariableDeclaration;
220 var->source = ret.source;
221 var->line = ret.line;
222 var->type = source_func->return_type;
223 var->name = r_result_name;
224 var->init_expression = ret.expression->clone();
225 r_inlined_statement = var;
230 FunctionInliner::FunctionInliner():
232 r_any_inlined(false),
233 r_inlined_here(false)
236 bool FunctionInliner::apply(Stage &s)
239 inlineable = InlineableFunctionLocator().apply(s);
240 r_any_inlined = false;
241 s.content.visit(*this);
242 return r_any_inlined;
245 void FunctionInliner::visit(RefPtr<Expression> &ptr)
251 ptr = r_inline_result;
252 r_any_inlined = true;
257 void FunctionInliner::visit(Block &block)
259 SetForScope<Block *> set_block(current_block, &block);
260 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
261 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
268 void FunctionInliner::visit(FunctionCall &call)
273 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
276 FunctionDeclaration *def = call.declaration;
278 def = def->definition;
280 if(def && inlineable.count(def))
282 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
284 // This will later get removed by UnusedVariableRemover.
285 if(result_name.empty())
286 result_name = "_msp_unused_from_inline";
288 RefPtr<VariableReference> ref = new VariableReference;
289 ref->name = result_name;
290 r_inline_result = ref;
292 /* Inlined variables need to be resolved before this function can be
294 inlineable.erase(current_function);
295 r_inlined_here = true;
299 void FunctionInliner::visit(FunctionDeclaration &func)
301 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
302 TraversingVisitor::visit(func);
303 r_inlined_here = false;
306 void FunctionInliner::visit(Iteration &iter)
308 /* Visit the initialization statement before entering the loop body so the
309 inlined statements get inserted outside. */
310 if(iter.init_statement)
311 iter.init_statement->visit(*this);
313 SetForScope<Block *> set_block(current_block, &iter.body);
314 /* Skip the condition and loop expression parts because they're not properly
315 inside the body block. Inlining anything into them will require a more
316 comprehensive transformation. */
317 iter.body.visit(*this);
321 ExpressionInliner::ExpressionInfo::ExpressionInfo():
330 ExpressionInliner::ExpressionInliner():
332 r_any_inlined(false),
335 iteration_init(false),
340 bool ExpressionInliner::apply(Stage &s)
342 s.content.visit(*this);
343 return r_any_inlined;
346 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
349 r_any_inlined = true;
352 void ExpressionInliner::visit(Block &block)
354 TraversingVisitor::visit(block);
356 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
358 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
359 for(; (j!=expressions.end() && j->first.declaration==i->second); )
361 if(j->second.expression && j->second.inline_point)
362 inline_expression(*j->second.expression, *j->second.inline_point);
364 expressions.erase(j++);
368 /* Expressions assigned in this block may depend on local variables of the
369 block. If this is a conditionally executed block, the assignments might not
370 always happen. Mark the expressions as not available to any outer blocks. */
371 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
372 if(i->second.assign_scope==&block)
373 i->second.available = false;
376 void ExpressionInliner::visit(RefPtr<Expression> &expr)
380 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
382 if(iteration_body && !r_ref_info->trivial)
384 /* Don't inline non-trivial expressions which were assigned outside
385 an iteration statement. The iteration may run multiple times, which
386 would cause the expression to also be evaluated multiple times. */
387 Block *i = r_ref_info->assign_scope;
388 for(; (i && i!=iteration_body); i=i->parent) ;
393 if(r_ref_info->trivial)
394 inline_expression(*r_ref_info->expression, expr);
396 /* Record the inline point for a non-trivial expression but don't
397 inline it yet. It might turn out it shouldn't be inlined after all. */
398 r_ref_info->inline_point = &expr;
404 void ExpressionInliner::visit(VariableReference &var)
408 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
409 if(i!=expressions.end())
411 /* If a non-trivial expression is referenced multiple times, don't
413 if(i->second.inline_point && !i->second.trivial)
414 i->second.expression = 0;
415 /* Mutating expressions are analogous to self-referencing assignments
416 and prevent inlining. */
418 i->second.expression = 0;
419 r_ref_info = &i->second;
424 void ExpressionInliner::visit(MemberAccess &memacc)
430 void ExpressionInliner::visit(Swizzle &swizzle)
436 void ExpressionInliner::visit(UnaryExpression &unary)
438 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
439 visit(unary.expression);
443 void ExpressionInliner::visit(BinaryExpression &binary)
447 SetFlag clear_target(mutating, false);
453 void ExpressionInliner::visit(Assignment &assign)
456 SetFlag set_target(mutating);
462 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
463 if(i!=expressions.end())
465 /* Self-referencing assignments can't be inlined without additional
466 work. Just clear any previous expression. */
467 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
468 i->second.assign_scope = current_block;
469 i->second.inline_point = 0;
470 i->second.available = true;
476 void ExpressionInliner::visit(TernaryExpression &ternary)
478 visit(ternary.condition);
479 visit(ternary.true_expr);
480 visit(ternary.false_expr);
484 void ExpressionInliner::visit(FunctionCall &call)
486 TraversingVisitor::visit(call);
490 void ExpressionInliner::visit(VariableDeclaration &var)
494 TraversingVisitor::visit(var);
496 bool constant = var.constant;
497 if(constant && var.layout)
499 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
500 constant = (i->name!="constant_id");
503 /* Only inline global variables if they're constant and have trivial
504 initializers. Non-constant variables could change in ways which are hard to
505 analyze and non-trivial expressions could be expensive to inline. */
506 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
508 ExpressionInfo &info = expressions[&var];
509 /* Assume variables declared in an iteration initialization statement
510 will have their values change throughout the iteration. */
511 info.expression = (iteration_init ? 0 : var.init_expression.get());
512 info.assign_scope = current_block;
513 info.trivial = r_trivial;
517 void ExpressionInliner::visit(Iteration &iter)
519 SetForScope<Block *> set_block(current_block, &iter.body);
520 if(iter.init_statement)
522 SetFlag set_init(iteration_init);
523 iter.init_statement->visit(*this);
526 SetForScope<Block *> set_body(iteration_body, &iter.body);
528 visit(iter.condition);
529 iter.body.visit(*this);
530 if(iter.loop_expression)
531 visit(iter.loop_expression);
535 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
537 if(value.check_type<bool>())
538 return BasicTypeDeclaration::BOOL;
539 else if(value.check_type<int>())
540 return BasicTypeDeclaration::INT;
541 else if(value.check_type<float>())
542 return BasicTypeDeclaration::FLOAT;
544 return BasicTypeDeclaration::VOID;
548 T ConstantFolder::evaluate_logical(char oper, T left, T right)
552 case '&': return left&right;
553 case '|': return left|right;
554 case '^': return left^right;
560 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
562 switch(oper[0]|oper[1])
564 case '<': return left<right;
565 case '<'|'=': return left<=right;
566 case '>': return left>right;
567 case '>'|'=': return left>=right;
568 default: return false;
573 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
577 case '+': return left+right;
578 case '-': return left-right;
579 case '*': return left*right;
580 case '/': return left/right;
585 void ConstantFolder::set_result(const Variant &value, bool literal)
587 r_constant_value = value;
592 void ConstantFolder::visit(RefPtr<Expression> &expr)
594 r_constant_value = Variant();
597 r_uses_iter_var = false;
599 /* Don't replace literals since they'd only be replaced with an identical
600 literal. Also skip anything that uses an iteration variable, but pass on
601 the result so the Iteration visiting function can handle it. */
602 if(!r_constant || r_literal || r_uses_iter_var)
605 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
606 if(kind==BasicTypeDeclaration::VOID)
612 RefPtr<Literal> literal = new Literal;
613 if(kind==BasicTypeDeclaration::BOOL)
614 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
615 else if(kind==BasicTypeDeclaration::INT)
616 literal->token = lexical_cast<string>(r_constant_value.value<int>());
617 else if(kind==BasicTypeDeclaration::FLOAT)
618 literal->token = lexical_cast<string>(r_constant_value.value<float>());
619 literal->value = r_constant_value;
623 void ConstantFolder::visit(Literal &literal)
625 set_result(literal.value, true);
628 void ConstantFolder::visit(VariableReference &var)
630 /* If an iteration variable is initialized with a constant value, return
631 that value here for the purpose of evaluating the loop condition for the
633 if(var.declaration==iteration_var)
635 set_result(iter_init_value);
636 r_uses_iter_var = true;
640 void ConstantFolder::visit(MemberAccess &memacc)
642 TraversingVisitor::visit(memacc);
646 void ConstantFolder::visit(Swizzle &swizzle)
648 TraversingVisitor::visit(swizzle);
652 void ConstantFolder::visit(UnaryExpression &unary)
654 TraversingVisitor::visit(unary);
655 bool can_fold = r_constant;
660 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
662 char oper = unary.oper->token[0];
663 char oper2 = unary.oper->token[1];
666 if(kind==BasicTypeDeclaration::BOOL)
667 set_result(!r_constant_value.value<bool>());
671 if(kind==BasicTypeDeclaration::INT)
672 set_result(~r_constant_value.value<int>());
674 else if(oper=='-' && !oper2)
676 if(kind==BasicTypeDeclaration::INT)
677 set_result(-r_constant_value.value<int>());
678 else if(kind==BasicTypeDeclaration::FLOAT)
679 set_result(-r_constant_value.value<float>());
683 void ConstantFolder::visit(BinaryExpression &binary)
686 bool left_constant = r_constant;
687 bool left_iter_var = r_uses_iter_var;
688 Variant left_value = r_constant_value;
691 r_uses_iter_var = true;
693 bool can_fold = (left_constant && r_constant);
698 BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
699 BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
700 // Currently only expressions with both sides of equal types are handled.
701 if(left_kind!=right_kind)
704 char oper = binary.oper->token[0];
705 char oper2 = binary.oper->token[1];
706 if(oper=='&' || oper=='|' || oper=='^')
708 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
709 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
710 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
711 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
713 else if((oper=='<' || oper=='>') && oper2!=oper)
715 if(left_kind==BasicTypeDeclaration::INT)
716 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
717 else if(left_kind==BasicTypeDeclaration::FLOAT)
718 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
720 else if((oper=='=' || oper=='!') && oper2=='=')
722 if(left_kind==BasicTypeDeclaration::INT)
723 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
724 if(left_kind==BasicTypeDeclaration::FLOAT)
725 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
727 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
729 if(left_kind==BasicTypeDeclaration::INT)
730 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
731 else if(left_kind==BasicTypeDeclaration::FLOAT)
732 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
734 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
736 if(left_kind!=BasicTypeDeclaration::INT)
740 set_result(left_value.value<int>()%r_constant_value.value<int>());
742 set_result(left_value.value<int>()<<r_constant_value.value<int>());
744 set_result(left_value.value<int>()>>r_constant_value.value<int>());
748 void ConstantFolder::visit(Assignment &assign)
750 TraversingVisitor::visit(assign);
754 void ConstantFolder::visit(TernaryExpression &ternary)
756 TraversingVisitor::visit(ternary);
760 void ConstantFolder::visit(FunctionCall &call)
762 TraversingVisitor::visit(call);
766 void ConstantFolder::visit(VariableDeclaration &var)
768 if(iteration_init && var.init_expression)
770 visit(var.init_expression);
773 /* Record the value of a constant initialization expression of an
774 iteration, so it can be used to evaluate the loop condition. */
775 iteration_var = &var;
776 iter_init_value = r_constant_value;
780 TraversingVisitor::visit(var);
783 void ConstantFolder::visit(Iteration &iter)
785 SetForScope<Block *> set_block(current_block, &iter.body);
787 /* The iteration variable is not normally inlined into expressions, so we
788 process it specially here. If the initial value causes the loop condition
789 to evaluate to false, then the expression can be folded. */
791 if(iter.init_statement)
793 SetFlag set_init(iteration_init);
794 iter.init_statement->visit(*this);
799 visit(iter.condition);
800 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
802 RefPtr<Literal> literal = new Literal;
803 literal->token = "false";
804 literal->value = r_constant_value;
805 iter.condition = literal;
810 iter.body.visit(*this);
811 if(iter.loop_expression)
812 visit(iter.loop_expression);
816 void ConstantConditionEliminator::apply(Stage &stage)
818 stage.content.visit(*this);
819 NodeRemover().apply(stage, nodes_to_remove);
822 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
824 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
825 if(literal->value.check_type<bool>())
826 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
830 void ConstantConditionEliminator::visit(Block &block)
832 SetForScope<Block *> set_block(current_block, &block);
833 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
840 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
842 r_ternary_result = 0;
845 expr = r_ternary_result;
846 r_ternary_result = 0;
849 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
851 ConstantStatus result = check_constant_condition(*ternary.condition);
852 if(result!=NOT_CONSTANT)
853 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
855 r_ternary_result = 0;
858 void ConstantConditionEliminator::visit(Conditional &cond)
860 ConstantStatus result = check_constant_condition(*cond.condition);
861 if(result!=NOT_CONSTANT)
863 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
864 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
865 current_block->body.splice(insert_point, block.body);
866 nodes_to_remove.insert(&cond);
870 TraversingVisitor::visit(cond);
873 void ConstantConditionEliminator::visit(Iteration &iter)
877 ConstantStatus result = check_constant_condition(*iter.condition);
878 if(result==CONSTANT_FALSE)
880 nodes_to_remove.insert(&iter);
885 TraversingVisitor::visit(iter);
889 bool UnusedTypeRemover::apply(Stage &stage)
891 stage.content.visit(*this);
892 NodeRemover().apply(stage, unused_nodes);
893 return !unused_nodes.empty();
896 void UnusedTypeRemover::visit(Literal &literal)
898 unused_nodes.erase(literal.type);
901 void UnusedTypeRemover::visit(UnaryExpression &unary)
903 unused_nodes.erase(unary.type);
904 TraversingVisitor::visit(unary);
907 void UnusedTypeRemover::visit(BinaryExpression &binary)
909 unused_nodes.erase(binary.type);
910 TraversingVisitor::visit(binary);
913 void UnusedTypeRemover::visit(TernaryExpression &ternary)
915 unused_nodes.erase(ternary.type);
916 TraversingVisitor::visit(ternary);
919 void UnusedTypeRemover::visit(FunctionCall &call)
921 unused_nodes.erase(call.type);
922 TraversingVisitor::visit(call);
925 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
928 unused_nodes.erase(type.base_type);
929 unused_nodes.insert(&type);
932 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
935 unused_nodes.erase(type.base_type);
936 unused_nodes.insert(&type);
939 void UnusedTypeRemover::visit(StructDeclaration &strct)
941 unused_nodes.insert(&strct);
942 TraversingVisitor::visit(strct);
945 void UnusedTypeRemover::visit(VariableDeclaration &var)
947 unused_nodes.erase(var.type_declaration);
950 void UnusedTypeRemover::visit(InterfaceBlock &iface)
952 unused_nodes.erase(iface.type_declaration);
955 void UnusedTypeRemover::visit(FunctionDeclaration &func)
957 unused_nodes.erase(func.return_type_declaration);
958 TraversingVisitor::visit(func);
962 UnusedVariableRemover::UnusedVariableRemover():
966 assignment_target(false),
967 r_side_effects(false)
970 bool UnusedVariableRemover::apply(Stage &s)
973 s.content.visit(*this);
975 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
976 if(i->used_by.empty())
977 unused_nodes.insert(i->node);
979 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
980 if(i->second->instance_name.empty())
981 unused_nodes.insert(i->second);
983 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
987 /* The last visible assignments of output variables are used by the
988 next stage or the API. */
989 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
990 unused_nodes.erase((*j)->node);
993 if(!i->second.output && !i->second.referenced)
995 // Don't remove variables from inside interface blocks.
996 if(!i->second.interface_block)
997 unused_nodes.insert(i->first);
999 else if(i->second.interface_block)
1000 // Interface blocks are kept if even one member is used.
1001 unused_nodes.erase(i->second.interface_block);
1004 NodeRemover().apply(s, unused_nodes);
1006 return !unused_nodes.empty();
1009 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1011 VariableInfo &var_info = variables[target.declaration];
1012 var_info.referenced = true;
1013 if(!assignment_target)
1015 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1016 (*i)->used_by.push_back(&node);
1020 void UnusedVariableRemover::visit(VariableReference &var)
1022 referenced(var.declaration, var);
1025 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1027 referenced(iface.declaration, iface);
1030 void UnusedVariableRemover::visit(UnaryExpression &unary)
1032 TraversingVisitor::visit(unary);
1033 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1034 r_side_effects = true;
1037 void UnusedVariableRemover::visit(BinaryExpression &binary)
1039 if(binary.oper->token[0]=='[')
1041 binary.left->visit(*this);
1042 SetFlag set(assignment_target, false);
1043 binary.right->visit(*this);
1046 TraversingVisitor::visit(binary);
1049 void UnusedVariableRemover::visit(Assignment &assign)
1052 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1053 assign.left->visit(*this);
1055 assign.right->visit(*this);
1056 r_assignment = &assign;
1057 r_side_effects = true;
1060 void UnusedVariableRemover::visit(FunctionCall &call)
1062 TraversingVisitor::visit(call);
1063 /* Treat function calls as having side effects so expression statements
1064 consisting of nothing but a function call won't be optimized away. */
1065 r_side_effects = true;
1067 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1069 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1070 if(i->second.output)
1071 referenced(i->first, call);
1075 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1077 assignments.push_back(AssignmentInfo());
1078 AssignmentInfo &assign_info = assignments.back();
1079 assign_info.node = &node;
1080 assign_info.target = target;
1082 /* An assignment to the target hides any assignments to the same target or
1084 VariableInfo &var_info = variables[target.declaration];
1085 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1087 const Assignment::Target &t = var_info.assignments[i]->target;
1089 bool subfield = (t.chain_len>=target.chain_len);
1090 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1091 subfield = (t.chain[j]==target.chain[j]);
1094 var_info.assignments.erase(var_info.assignments.begin()+i);
1099 var_info.assignments.push_back(&assign_info);
1102 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1105 r_side_effects = false;
1106 TraversingVisitor::visit(expr);
1107 if(r_assignment && r_assignment->target.declaration)
1108 record_assignment(r_assignment->target, expr);
1110 unused_nodes.insert(&expr);
1113 void UnusedVariableRemover::visit(VariableDeclaration &var)
1115 VariableInfo &var_info = variables[&var];
1116 var_info.interface_block = interface_block;
1118 /* Mark variables as output if they're used by the next stage or the
1121 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
1123 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1125 if(var.init_expression)
1127 var_info.initialized = true;
1128 record_assignment(&var, *var.init_expression);
1130 TraversingVisitor::visit(var);
1133 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1135 if(iface.instance_name.empty())
1137 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1138 iface.struct_declaration->members.visit(*this);
1142 VariableInfo &var_info = variables[&iface];
1143 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
1147 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1149 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1151 BlockVariableMap::iterator j = variables.find(i->first);
1152 if(j!=variables.end())
1154 /* The merged blocks started as copies of each other so any common
1155 assignments must be in the beginning. */
1157 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1158 if(i->second.assignments[k]!=j->second.assignments[k])
1161 // Remaining assignments are unique to each block; merge them.
1162 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1163 j->second.referenced |= i->second.referenced;
1166 variables.insert(*i);
1170 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1172 if(func.body.body.empty())
1175 BlockVariableMap saved_vars = variables;
1176 // Assignments from other functions should not be visible.
1177 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1178 i->second.assignments.resize(i->second.initialized);
1179 TraversingVisitor::visit(func);
1180 swap(variables, saved_vars);
1181 merge_variables(saved_vars);
1183 /* Always treat function parameters as referenced. Removing unused
1184 parameters is not currently supported. */
1185 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1187 BlockVariableMap::iterator j = variables.find(i->get());
1188 if(j!=variables.end())
1189 j->second.referenced = true;
1193 void UnusedVariableRemover::visit(Conditional &cond)
1195 cond.condition->visit(*this);
1196 BlockVariableMap saved_vars = variables;
1197 cond.body.visit(*this);
1198 swap(saved_vars, variables);
1199 cond.else_body.visit(*this);
1201 /* Visible assignments after the conditional is the union of those visible
1202 at the end of the if and else blocks. If there was no else block, then it's
1203 the union of the if block and the state before it. */
1204 merge_variables(saved_vars);
1207 void UnusedVariableRemover::visit(Iteration &iter)
1209 BlockVariableMap saved_vars = variables;
1210 TraversingVisitor::visit(iter);
1212 /* Merge assignments from the iteration, without clearing previous state.
1213 Further analysis is needed to determine which parts of the iteration body
1214 are always executed, if any. */
1215 merge_variables(saved_vars);
1219 bool UnusedFunctionRemover::apply(Stage &stage)
1221 stage.content.visit(*this);
1222 NodeRemover().apply(stage, unused_nodes);
1223 return !unused_nodes.empty();
1226 void UnusedFunctionRemover::visit(FunctionCall &call)
1228 TraversingVisitor::visit(call);
1230 unused_nodes.erase(call.declaration);
1231 if(call.declaration && call.declaration->definition!=call.declaration)
1232 used_definitions.insert(call.declaration->definition);
1235 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1237 TraversingVisitor::visit(func);
1239 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1240 unused_nodes.insert(&func);