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();
94 remap_prefix = source_func->name;
96 std::vector<RefPtr<VariableDeclaration> > params;
97 params.reserve(source_func->parameters.size());
98 for(NodeArray<VariableDeclaration>::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i)
100 RefPtr<VariableDeclaration> var = (*i)->clone();
101 var->interface.clear();
103 SetForScope<Pass> set_pass(pass, RENAME);
106 staging_block.body.push_back(0);
107 staging_block.body.back() = var;
108 params.push_back(var);
111 for(NodeList<Statement>::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i)
113 r_inlined_statement = 0;
115 if(!r_inlined_statement)
116 r_inlined_statement = (*i)->clone();
118 SetForScope<Pass> set_pass(pass, RENAME);
119 r_inlined_statement->visit(*this);
121 staging_block.body.push_back(0);
122 staging_block.body.back() = r_inlined_statement;
125 /* Now collect names from the staging block. Local variables that would
126 have conflicted with the target function were renamed earlier. */
128 referenced_names.clear();
129 staging_block.variables.clear();
130 staging_block.visit(*this);
132 /* Rename variables in the target function so they don't interfere with
133 global identifiers used by the source function. */
135 staging_block.parent = source_func->body.parent;
136 remap_prefix = target_func.name;
137 target_func.visit(*this);
139 // Put the argument expressions in place after all renaming has been done.
140 for(unsigned i=0; i<source_func->parameters.size(); ++i)
141 params[i]->init_expression = call.arguments[i]->clone();
143 tgt_blk.body.splice(ins_pt, staging_block.body);
145 NodeReorderer().apply(stage, target_func, dependencies);
147 return r_result_name;
150 void InlineContentInjector::visit(VariableReference &var)
154 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
155 if(i!=staging_block.variables.end())
156 var.name = i->second->name;
158 else if(pass==DEPENDS && var.declaration)
160 dependencies.insert(var.declaration);
161 var.declaration->visit(*this);
163 else if(pass==REFERENCED)
164 referenced_names.insert(var.name);
167 void InlineContentInjector::visit(InterfaceBlockReference &iface)
169 if(pass==DEPENDS && iface.declaration)
171 dependencies.insert(iface.declaration);
172 iface.declaration->visit(*this);
174 else if(pass==REFERENCED)
175 referenced_names.insert(iface.name);
178 void InlineContentInjector::visit(FunctionCall &call)
180 if(pass==DEPENDS && call.declaration)
181 dependencies.insert(call.declaration);
182 else if(pass==REFERENCED)
183 referenced_names.insert(call.name);
184 TraversingVisitor::visit(call);
187 void InlineContentInjector::visit(VariableDeclaration &var)
189 TraversingVisitor::visit(var);
193 staging_block.variables[var.name] = &var;
194 if(referenced_names.count(var.name))
196 string mapped_name = get_unused_variable_name(staging_block, var.name, remap_prefix);
197 if(mapped_name!=var.name)
199 staging_block.variables[mapped_name] = &var;
200 var.name = mapped_name;
204 else if(pass==DEPENDS && var.type_declaration)
206 dependencies.insert(var.type_declaration);
207 var.type_declaration->visit(*this);
209 else if(pass==REFERENCED)
210 referenced_names.insert(var.type);
213 void InlineContentInjector::visit(Return &ret)
215 TraversingVisitor::visit(ret);
217 if(pass==INLINE && ret.expression)
219 // Create a new variable to hold the return value of the inlined function.
220 r_result_name = get_unused_variable_name(staging_block, "_return", source_func->name);
221 RefPtr<VariableDeclaration> var = new VariableDeclaration;
222 var->source = ret.source;
223 var->line = ret.line;
224 var->type = source_func->return_type;
225 var->name = r_result_name;
226 var->init_expression = ret.expression->clone();
227 r_inlined_statement = var;
232 FunctionInliner::FunctionInliner():
234 r_any_inlined(false),
235 r_inlined_here(false)
238 bool FunctionInliner::apply(Stage &s)
241 inlineable = InlineableFunctionLocator().apply(s);
242 r_any_inlined = false;
243 s.content.visit(*this);
244 return r_any_inlined;
247 void FunctionInliner::visit(RefPtr<Expression> &ptr)
253 ptr = r_inline_result;
254 r_any_inlined = true;
259 void FunctionInliner::visit(Block &block)
261 SetForScope<Block *> set_block(current_block, &block);
262 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
263 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
270 void FunctionInliner::visit(FunctionCall &call)
275 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
278 FunctionDeclaration *def = call.declaration;
280 def = def->definition;
282 if(def && inlineable.count(def))
284 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
286 // This will later get removed by UnusedVariableRemover.
287 if(result_name.empty())
288 result_name = "msp_unused_from_inline";
290 RefPtr<VariableReference> ref = new VariableReference;
291 ref->name = result_name;
292 r_inline_result = ref;
294 /* Inlined variables need to be resolved before this function can be
296 inlineable.erase(current_function);
297 r_inlined_here = true;
301 void FunctionInliner::visit(FunctionDeclaration &func)
303 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
304 TraversingVisitor::visit(func);
305 r_inlined_here = false;
308 void FunctionInliner::visit(Iteration &iter)
310 /* Visit the initialization statement before entering the loop body so the
311 inlined statements get inserted outside. */
312 if(iter.init_statement)
313 iter.init_statement->visit(*this);
315 SetForScope<Block *> set_block(current_block, &iter.body);
316 /* Skip the condition and loop expression parts because they're not properly
317 inside the body block. Inlining anything into them will require a more
318 comprehensive transformation. */
319 iter.body.visit(*this);
323 ExpressionInliner::ExpressionInfo::ExpressionInfo():
332 ExpressionInliner::ExpressionInliner():
334 r_any_inlined(false),
337 iteration_init(false),
342 bool ExpressionInliner::apply(Stage &s)
344 s.content.visit(*this);
345 return r_any_inlined;
348 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
351 r_any_inlined = true;
354 void ExpressionInliner::visit(Block &block)
356 TraversingVisitor::visit(block);
358 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
360 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
361 for(; (j!=expressions.end() && j->first.declaration==i->second); )
363 if(j->second.expression && j->second.inline_point)
364 inline_expression(*j->second.expression, *j->second.inline_point);
366 expressions.erase(j++);
370 /* Expressions assigned in this block may depend on local variables of the
371 block. If this is a conditionally executed block, the assignments might not
372 always happen. Mark the expressions as not available to any outer blocks. */
373 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
374 if(i->second.assign_scope==&block)
375 i->second.available = false;
378 void ExpressionInliner::visit(RefPtr<Expression> &expr)
382 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
384 if(iteration_body && !r_ref_info->trivial)
386 /* Don't inline non-trivial expressions which were assigned outside
387 an iteration statement. The iteration may run multiple times, which
388 would cause the expression to also be evaluated multiple times. */
389 Block *i = r_ref_info->assign_scope;
390 for(; (i && i!=iteration_body); i=i->parent) ;
395 if(r_ref_info->trivial)
396 inline_expression(*r_ref_info->expression, expr);
398 /* Record the inline point for a non-trivial expression but don't
399 inline it yet. It might turn out it shouldn't be inlined after all. */
400 r_ref_info->inline_point = &expr;
406 void ExpressionInliner::visit(VariableReference &var)
410 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
411 if(i!=expressions.end())
413 /* If a non-trivial expression is referenced multiple times, don't
415 if(i->second.inline_point && !i->second.trivial)
416 i->second.expression = 0;
417 /* Mutating expressions are analogous to self-referencing assignments
418 and prevent inlining. */
420 i->second.expression = 0;
421 r_ref_info = &i->second;
426 void ExpressionInliner::visit(MemberAccess &memacc)
432 void ExpressionInliner::visit(Swizzle &swizzle)
438 void ExpressionInliner::visit(UnaryExpression &unary)
440 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
441 visit(unary.expression);
445 void ExpressionInliner::visit(BinaryExpression &binary)
449 SetFlag clear_target(mutating, false);
455 void ExpressionInliner::visit(Assignment &assign)
458 SetFlag set_target(mutating);
464 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
465 if(i!=expressions.end())
467 /* Self-referencing assignments can't be inlined without additional
468 work. Just clear any previous expression. */
469 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
470 i->second.assign_scope = current_block;
471 i->second.inline_point = 0;
472 i->second.available = true;
478 void ExpressionInliner::visit(TernaryExpression &ternary)
480 visit(ternary.condition);
481 visit(ternary.true_expr);
482 visit(ternary.false_expr);
486 void ExpressionInliner::visit(FunctionCall &call)
488 TraversingVisitor::visit(call);
492 void ExpressionInliner::visit(VariableDeclaration &var)
496 TraversingVisitor::visit(var);
498 bool constant = var.constant;
499 if(constant && var.layout)
501 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
502 constant = (i->name!="constant_id");
505 /* Only inline global variables if they're constant and have trivial
506 initializers. Non-constant variables could change in ways which are hard to
507 analyze and non-trivial expressions could be expensive to inline. */
508 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
510 ExpressionInfo &info = expressions[&var];
511 /* Assume variables declared in an iteration initialization statement
512 will have their values change throughout the iteration. */
513 info.expression = (iteration_init ? 0 : var.init_expression.get());
514 info.assign_scope = current_block;
515 info.trivial = r_trivial;
519 void ExpressionInliner::visit(Iteration &iter)
521 SetForScope<Block *> set_block(current_block, &iter.body);
522 if(iter.init_statement)
524 SetFlag set_init(iteration_init);
525 iter.init_statement->visit(*this);
528 SetForScope<Block *> set_body(iteration_body, &iter.body);
530 visit(iter.condition);
531 iter.body.visit(*this);
532 if(iter.loop_expression)
533 visit(iter.loop_expression);
537 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
539 if(value.check_type<bool>())
540 return BasicTypeDeclaration::BOOL;
541 else if(value.check_type<int>())
542 return BasicTypeDeclaration::INT;
543 else if(value.check_type<float>())
544 return BasicTypeDeclaration::FLOAT;
546 return BasicTypeDeclaration::VOID;
550 T ConstantFolder::evaluate_logical(char oper, T left, T right)
554 case '&': return left&right;
555 case '|': return left|right;
556 case '^': return left^right;
562 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
564 switch(oper[0]|oper[1])
566 case '<': return left<right;
567 case '<'|'=': return left<=right;
568 case '>': return left>right;
569 case '>'|'=': return left>=right;
570 default: return false;
575 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
579 case '+': return left+right;
580 case '-': return left-right;
581 case '*': return left*right;
582 case '/': return left/right;
587 void ConstantFolder::set_result(const Variant &value, bool literal)
589 r_constant_value = value;
594 void ConstantFolder::visit(RefPtr<Expression> &expr)
596 r_constant_value = Variant();
599 r_uses_iter_var = false;
601 /* Don't replace literals since they'd only be replaced with an identical
602 literal. Also skip anything that uses an iteration variable, but pass on
603 the result so the Iteration visiting function can handle it. */
604 if(!r_constant || r_literal || r_uses_iter_var)
607 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
608 if(kind==BasicTypeDeclaration::VOID)
614 RefPtr<Literal> literal = new Literal;
615 if(kind==BasicTypeDeclaration::BOOL)
616 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
617 else if(kind==BasicTypeDeclaration::INT)
618 literal->token = lexical_cast<string>(r_constant_value.value<int>());
619 else if(kind==BasicTypeDeclaration::FLOAT)
620 literal->token = lexical_cast<string>(r_constant_value.value<float>());
621 literal->value = r_constant_value;
625 void ConstantFolder::visit(Literal &literal)
627 set_result(literal.value, true);
630 void ConstantFolder::visit(VariableReference &var)
632 /* If an iteration variable is initialized with a constant value, return
633 that value here for the purpose of evaluating the loop condition for the
635 if(var.declaration==iteration_var)
637 set_result(iter_init_value);
638 r_uses_iter_var = true;
642 void ConstantFolder::visit(MemberAccess &memacc)
644 TraversingVisitor::visit(memacc);
648 void ConstantFolder::visit(Swizzle &swizzle)
650 TraversingVisitor::visit(swizzle);
654 void ConstantFolder::visit(UnaryExpression &unary)
656 TraversingVisitor::visit(unary);
657 bool can_fold = r_constant;
662 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
664 char oper = unary.oper->token[0];
665 char oper2 = unary.oper->token[1];
668 if(kind==BasicTypeDeclaration::BOOL)
669 set_result(!r_constant_value.value<bool>());
673 if(kind==BasicTypeDeclaration::INT)
674 set_result(~r_constant_value.value<int>());
676 else if(oper=='-' && !oper2)
678 if(kind==BasicTypeDeclaration::INT)
679 set_result(-r_constant_value.value<int>());
680 else if(kind==BasicTypeDeclaration::FLOAT)
681 set_result(-r_constant_value.value<float>());
685 void ConstantFolder::visit(BinaryExpression &binary)
688 bool left_constant = r_constant;
689 bool left_iter_var = r_uses_iter_var;
690 Variant left_value = r_constant_value;
693 r_uses_iter_var = true;
695 bool can_fold = (left_constant && r_constant);
700 BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
701 BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
702 // Currently only expressions with both sides of equal types are handled.
703 if(left_kind!=right_kind)
706 char oper = binary.oper->token[0];
707 char oper2 = binary.oper->token[1];
708 if(oper=='&' || oper=='|' || oper=='^')
710 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
711 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
712 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
713 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
715 else if((oper=='<' || oper=='>') && oper2!=oper)
717 if(left_kind==BasicTypeDeclaration::INT)
718 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
719 else if(left_kind==BasicTypeDeclaration::FLOAT)
720 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
722 else if((oper=='=' || oper=='!') && oper2=='=')
724 if(left_kind==BasicTypeDeclaration::INT)
725 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
726 if(left_kind==BasicTypeDeclaration::FLOAT)
727 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
729 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
731 if(left_kind==BasicTypeDeclaration::INT)
732 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
733 else if(left_kind==BasicTypeDeclaration::FLOAT)
734 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
736 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
738 if(left_kind!=BasicTypeDeclaration::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>());
746 set_result(left_value.value<int>()>>r_constant_value.value<int>());
750 void ConstantFolder::visit(Assignment &assign)
752 TraversingVisitor::visit(assign);
756 void ConstantFolder::visit(TernaryExpression &ternary)
758 TraversingVisitor::visit(ternary);
762 void ConstantFolder::visit(FunctionCall &call)
764 TraversingVisitor::visit(call);
768 void ConstantFolder::visit(VariableDeclaration &var)
770 if(iteration_init && var.init_expression)
772 visit(var.init_expression);
775 /* Record the value of a constant initialization expression of an
776 iteration, so it can be used to evaluate the loop condition. */
777 iteration_var = &var;
778 iter_init_value = r_constant_value;
782 TraversingVisitor::visit(var);
785 void ConstantFolder::visit(Iteration &iter)
787 SetForScope<Block *> set_block(current_block, &iter.body);
789 /* The iteration variable is not normally inlined into expressions, so we
790 process it specially here. If the initial value causes the loop condition
791 to evaluate to false, then the expression can be folded. */
793 if(iter.init_statement)
795 SetFlag set_init(iteration_init);
796 iter.init_statement->visit(*this);
801 visit(iter.condition);
802 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
804 RefPtr<Literal> literal = new Literal;
805 literal->token = "false";
806 literal->value = r_constant_value;
807 iter.condition = literal;
812 iter.body.visit(*this);
813 if(iter.loop_expression)
814 visit(iter.loop_expression);
818 void ConstantConditionEliminator::apply(Stage &stage)
820 stage.content.visit(*this);
821 NodeRemover().apply(stage, nodes_to_remove);
824 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
826 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
827 if(literal->value.check_type<bool>())
828 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
832 void ConstantConditionEliminator::visit(Block &block)
834 SetForScope<Block *> set_block(current_block, &block);
835 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
842 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
844 r_ternary_result = 0;
847 expr = r_ternary_result;
848 r_ternary_result = 0;
851 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
853 ConstantStatus result = check_constant_condition(*ternary.condition);
854 if(result!=NOT_CONSTANT)
855 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
857 r_ternary_result = 0;
860 void ConstantConditionEliminator::visit(Conditional &cond)
862 ConstantStatus result = check_constant_condition(*cond.condition);
863 if(result!=NOT_CONSTANT)
865 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
866 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
867 current_block->body.splice(insert_point, block.body);
868 nodes_to_remove.insert(&cond);
872 TraversingVisitor::visit(cond);
875 void ConstantConditionEliminator::visit(Iteration &iter)
879 ConstantStatus result = check_constant_condition(*iter.condition);
880 if(result==CONSTANT_FALSE)
882 nodes_to_remove.insert(&iter);
887 TraversingVisitor::visit(iter);
891 bool UnusedTypeRemover::apply(Stage &stage)
893 stage.content.visit(*this);
894 NodeRemover().apply(stage, unused_nodes);
895 return !unused_nodes.empty();
898 void UnusedTypeRemover::visit(Literal &literal)
900 unused_nodes.erase(literal.type);
903 void UnusedTypeRemover::visit(UnaryExpression &unary)
905 unused_nodes.erase(unary.type);
906 TraversingVisitor::visit(unary);
909 void UnusedTypeRemover::visit(BinaryExpression &binary)
911 unused_nodes.erase(binary.type);
912 TraversingVisitor::visit(binary);
915 void UnusedTypeRemover::visit(TernaryExpression &ternary)
917 unused_nodes.erase(ternary.type);
918 TraversingVisitor::visit(ternary);
921 void UnusedTypeRemover::visit(FunctionCall &call)
923 unused_nodes.erase(call.type);
924 TraversingVisitor::visit(call);
927 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
930 unused_nodes.erase(type.base_type);
931 unused_nodes.insert(&type);
934 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
937 unused_nodes.erase(type.base_type);
938 unused_nodes.insert(&type);
941 void UnusedTypeRemover::visit(StructDeclaration &strct)
943 unused_nodes.insert(&strct);
944 TraversingVisitor::visit(strct);
947 void UnusedTypeRemover::visit(VariableDeclaration &var)
949 unused_nodes.erase(var.type_declaration);
952 void UnusedTypeRemover::visit(InterfaceBlock &iface)
954 unused_nodes.erase(iface.type_declaration);
957 void UnusedTypeRemover::visit(FunctionDeclaration &func)
959 unused_nodes.erase(func.return_type_declaration);
960 TraversingVisitor::visit(func);
964 UnusedVariableRemover::UnusedVariableRemover():
968 assignment_target(false),
969 r_side_effects(false)
972 bool UnusedVariableRemover::apply(Stage &s)
975 s.content.visit(*this);
977 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
978 if(i->used_by.empty())
979 unused_nodes.insert(i->node);
981 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
982 if(i->second->instance_name.empty())
983 unused_nodes.insert(i->second);
985 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
989 /* The last visible assignments of output variables are used by the
990 next stage or the API. */
991 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
992 unused_nodes.erase((*j)->node);
995 if(!i->second.output && !i->second.referenced)
997 // Don't remove variables from inside interface blocks.
998 if(!i->second.interface_block)
999 unused_nodes.insert(i->first);
1001 else if(i->second.interface_block)
1002 // Interface blocks are kept if even one member is used.
1003 unused_nodes.erase(i->second.interface_block);
1006 NodeRemover().apply(s, unused_nodes);
1008 return !unused_nodes.empty();
1011 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1013 VariableInfo &var_info = variables[target.declaration];
1014 var_info.referenced = true;
1015 if(!assignment_target)
1017 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1018 (*i)->used_by.push_back(&node);
1022 void UnusedVariableRemover::visit(VariableReference &var)
1024 referenced(var.declaration, var);
1027 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1029 referenced(iface.declaration, iface);
1032 void UnusedVariableRemover::visit(UnaryExpression &unary)
1034 TraversingVisitor::visit(unary);
1035 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1036 r_side_effects = true;
1039 void UnusedVariableRemover::visit(BinaryExpression &binary)
1041 if(binary.oper->token[0]=='[')
1043 binary.left->visit(*this);
1044 SetFlag set(assignment_target, false);
1045 binary.right->visit(*this);
1048 TraversingVisitor::visit(binary);
1051 void UnusedVariableRemover::visit(Assignment &assign)
1054 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1055 assign.left->visit(*this);
1057 assign.right->visit(*this);
1058 r_assignment = &assign;
1059 r_side_effects = true;
1062 void UnusedVariableRemover::visit(FunctionCall &call)
1064 TraversingVisitor::visit(call);
1065 /* Treat function calls as having side effects so expression statements
1066 consisting of nothing but a function call won't be optimized away. */
1067 r_side_effects = true;
1069 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1071 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1072 if(i->second.output)
1073 referenced(i->first, call);
1077 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1079 assignments.push_back(AssignmentInfo());
1080 AssignmentInfo &assign_info = assignments.back();
1081 assign_info.node = &node;
1082 assign_info.target = target;
1084 /* An assignment to the target hides any assignments to the same target or
1086 VariableInfo &var_info = variables[target.declaration];
1087 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1089 const Assignment::Target &t = var_info.assignments[i]->target;
1091 bool subfield = (t.chain_len>=target.chain_len);
1092 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1093 subfield = (t.chain[j]==target.chain[j]);
1096 var_info.assignments.erase(var_info.assignments.begin()+i);
1101 var_info.assignments.push_back(&assign_info);
1104 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1107 r_side_effects = false;
1108 TraversingVisitor::visit(expr);
1109 if(r_assignment && r_assignment->target.declaration)
1110 record_assignment(r_assignment->target, expr);
1112 unused_nodes.insert(&expr);
1115 void UnusedVariableRemover::visit(VariableDeclaration &var)
1117 VariableInfo &var_info = variables[&var];
1118 var_info.interface_block = interface_block;
1120 /* Mark variables as output if they're used by the next stage or the
1123 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
1125 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1127 if(var.init_expression)
1129 var_info.initialized = true;
1130 record_assignment(&var, *var.init_expression);
1132 TraversingVisitor::visit(var);
1135 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1137 if(iface.instance_name.empty())
1139 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1140 iface.struct_declaration->members.visit(*this);
1144 VariableInfo &var_info = variables[&iface];
1145 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
1149 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1151 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1153 BlockVariableMap::iterator j = variables.find(i->first);
1154 if(j!=variables.end())
1156 /* The merged blocks started as copies of each other so any common
1157 assignments must be in the beginning. */
1159 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1160 if(i->second.assignments[k]!=j->second.assignments[k])
1163 // Remaining assignments are unique to each block; merge them.
1164 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1165 j->second.referenced |= i->second.referenced;
1168 variables.insert(*i);
1172 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1174 if(func.body.body.empty())
1177 BlockVariableMap saved_vars = variables;
1178 // Assignments from other functions should not be visible.
1179 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1180 i->second.assignments.resize(i->second.initialized);
1181 TraversingVisitor::visit(func);
1182 swap(variables, saved_vars);
1183 merge_variables(saved_vars);
1185 /* Always treat function parameters as referenced. Removing unused
1186 parameters is not currently supported. */
1187 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1189 BlockVariableMap::iterator j = variables.find(i->get());
1190 if(j!=variables.end())
1191 j->second.referenced = true;
1195 void UnusedVariableRemover::visit(Conditional &cond)
1197 cond.condition->visit(*this);
1198 BlockVariableMap saved_vars = variables;
1199 cond.body.visit(*this);
1200 swap(saved_vars, variables);
1201 cond.else_body.visit(*this);
1203 /* Visible assignments after the conditional is the union of those visible
1204 at the end of the if and else blocks. If there was no else block, then it's
1205 the union of the if block and the state before it. */
1206 merge_variables(saved_vars);
1209 void UnusedVariableRemover::visit(Iteration &iter)
1211 BlockVariableMap saved_vars = variables;
1212 TraversingVisitor::visit(iter);
1214 /* Merge assignments from the iteration, without clearing previous state.
1215 Further analysis is needed to determine which parts of the iteration body
1216 are always executed, if any. */
1217 merge_variables(saved_vars);
1221 bool UnusedFunctionRemover::apply(Stage &stage)
1223 stage.content.visit(*this);
1224 NodeRemover().apply(stage, unused_nodes);
1225 return !unused_nodes.empty();
1228 void UnusedFunctionRemover::visit(FunctionCall &call)
1230 TraversingVisitor::visit(call);
1232 unused_nodes.erase(call.declaration);
1233 if(call.declaration && call.declaration->definition!=call.declaration)
1234 used_definitions.insert(call.declaration->definition);
1237 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1239 TraversingVisitor::visit(func);
1241 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1242 unused_nodes.insert(&func);