1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
3 #include <msp/strings/utils.h>
13 ConstantSpecializer::ConstantSpecializer():
17 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
20 stage.content.visit(*this);
23 void ConstantSpecializer::visit(VariableDeclaration &var)
25 bool specializable = false;
28 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
29 for(vector<Layout::Qualifier>::iterator i=qualifiers.begin(); (!specializable && i!=qualifiers.end()); ++i)
30 if(i->name=="constant_id")
36 if(qualifiers.empty())
42 map<string, int>::const_iterator i = values->find(var.name);
45 RefPtr<Literal> literal = new Literal;
48 literal->token = (i->second ? "true" : "false");
49 literal->value = static_cast<bool>(i->second);
51 else if(var.type=="int")
53 literal->token = lexical_cast<string>(i->second);
54 literal->value = i->second;
56 var.init_expression = literal;
62 InlineableFunctionLocator::InlineableFunctionLocator():
67 void InlineableFunctionLocator::visit(FunctionCall &call)
69 FunctionDeclaration *def = call.declaration;
71 def = def->definition;
75 unsigned &count = refcounts[def];
77 /* Don't inline functions which are called more than once or are called
79 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
80 inlineable.erase(def);
83 TraversingVisitor::visit(call);
86 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
88 bool has_out_params = false;
89 for(NodeArray<VariableDeclaration>::const_iterator i=func.parameters.begin(); (!has_out_params && i!=func.parameters.end()); ++i)
90 has_out_params = ((*i)->interface=="out");
92 unsigned &count = refcounts[func.definition];
93 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
94 inlineable.insert(func.definition);
96 SetForScope<FunctionDeclaration *> set(current_function, &func);
98 TraversingVisitor::visit(func);
101 void InlineableFunctionLocator::visit(Conditional &cond)
103 TraversingVisitor::visit(cond);
104 inlineable.erase(current_function);
107 void InlineableFunctionLocator::visit(Iteration &iter)
109 TraversingVisitor::visit(iter);
110 inlineable.erase(current_function);
113 void InlineableFunctionLocator::visit(Return &ret)
115 TraversingVisitor::visit(ret);
117 inlineable.erase(current_function);
122 InlineContentInjector::InlineContentInjector():
127 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
129 source_func = call.declaration->definition;
131 /* Populate referenced_names from the target function so we can rename
132 variables from the inlined function that would conflict. */
134 target_func.visit(*this);
136 /* Inline and rename passes must be interleaved so used variable names are
137 known when inlining the return statement. */
139 staging_block.parent = &tgt_blk;
140 staging_block.variables.clear();
142 vector<RefPtr<VariableDeclaration> > params;
143 params.reserve(source_func->parameters.size());
144 for(NodeArray<VariableDeclaration>::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i)
146 RefPtr<VariableDeclaration> var = (*i)->clone();
147 var->interface.clear();
149 SetForScope<Pass> set_pass(pass, RENAME);
152 staging_block.body.push_back_nocopy(var);
153 params.push_back(var);
156 for(NodeList<Statement>::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i)
158 r_inlined_statement = 0;
160 if(!r_inlined_statement)
161 r_inlined_statement = (*i)->clone();
163 SetForScope<Pass> set_pass(pass, RENAME);
164 r_inlined_statement->visit(*this);
166 staging_block.body.push_back_nocopy(r_inlined_statement);
169 /* Now collect names from the staging block. Local variables that would
170 have conflicted with the target function were renamed earlier. */
172 referenced_names.clear();
173 staging_block.variables.clear();
174 staging_block.visit(*this);
176 /* Rename variables in the target function so they don't interfere with
177 global identifiers used by the source function. */
179 staging_block.parent = source_func->body.parent;
180 target_func.visit(*this);
182 // Put the argument expressions in place after all renaming has been done.
183 for(unsigned i=0; i<source_func->parameters.size(); ++i)
184 params[i]->init_expression = call.arguments[i]->clone();
186 tgt_blk.body.splice(ins_pt, staging_block.body);
188 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
190 return r_result_name;
193 void InlineContentInjector::visit(VariableReference &var)
197 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
198 if(i!=staging_block.variables.end())
199 var.name = i->second->name;
201 else if(pass==REFERENCED)
202 referenced_names.insert(var.name);
205 void InlineContentInjector::visit(InterfaceBlockReference &iface)
208 referenced_names.insert(iface.name);
211 void InlineContentInjector::visit(FunctionCall &call)
214 referenced_names.insert(call.name);
215 TraversingVisitor::visit(call);
218 void InlineContentInjector::visit(VariableDeclaration &var)
220 TraversingVisitor::visit(var);
224 /* Check against conflicts with the other context as well as variables
225 already renamed here. */
226 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
227 staging_block.variables[var.name] = &var;
230 string mapped_name = get_unused_variable_name(staging_block, var.name);
231 if(mapped_name!=var.name)
233 staging_block.variables[mapped_name] = &var;
234 var.name = mapped_name;
238 else if(pass==REFERENCED)
239 referenced_names.insert(var.type);
242 void InlineContentInjector::visit(Return &ret)
244 TraversingVisitor::visit(ret);
246 if(pass==INLINE && ret.expression)
248 // Create a new variable to hold the return value of the inlined function.
249 r_result_name = get_unused_variable_name(staging_block, "_return");
250 RefPtr<VariableDeclaration> var = new VariableDeclaration;
251 var->source = ret.source;
252 var->line = ret.line;
253 var->type = source_func->return_type;
254 var->name = r_result_name;
255 var->init_expression = ret.expression->clone();
256 r_inlined_statement = var;
261 FunctionInliner::FunctionInliner():
263 r_any_inlined(false),
264 r_inlined_here(false)
267 bool FunctionInliner::apply(Stage &s)
270 inlineable = InlineableFunctionLocator().apply(s);
271 r_any_inlined = false;
272 s.content.visit(*this);
273 return r_any_inlined;
276 void FunctionInliner::visit(RefPtr<Expression> &ptr)
282 ptr = r_inline_result;
283 r_any_inlined = true;
288 void FunctionInliner::visit(Block &block)
290 SetForScope<Block *> set_block(current_block, &block);
291 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
292 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
299 void FunctionInliner::visit(FunctionCall &call)
301 for(NodeArray<Expression>::iterator i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
307 FunctionDeclaration *def = call.declaration;
309 def = def->definition;
311 if(def && inlineable.count(def))
313 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
315 // This will later get removed by UnusedVariableRemover.
316 if(result_name.empty())
317 result_name = "_msp_unused_from_inline";
319 RefPtr<VariableReference> ref = new VariableReference;
320 ref->name = result_name;
321 r_inline_result = ref;
323 /* Inlined variables need to be resolved before this function can be
325 inlineable.erase(current_function);
326 r_inlined_here = true;
330 void FunctionInliner::visit(FunctionDeclaration &func)
332 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
333 TraversingVisitor::visit(func);
334 r_inlined_here = false;
337 void FunctionInliner::visit(Iteration &iter)
339 /* Visit the initialization statement before entering the loop body so the
340 inlined statements get inserted outside. */
341 if(iter.init_statement)
342 iter.init_statement->visit(*this);
344 SetForScope<Block *> set_block(current_block, &iter.body);
345 /* Skip the condition and loop expression parts because they're not properly
346 inside the body block. Inlining anything into them will require a more
347 comprehensive transformation. */
348 iter.body.visit(*this);
352 ExpressionInliner::ExpressionInliner():
354 r_any_inlined(false),
357 iteration_init(false),
362 bool ExpressionInliner::apply(Stage &s)
364 s.content.visit(*this);
365 return r_any_inlined;
368 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
371 r_any_inlined = true;
374 void ExpressionInliner::visit(Block &block)
376 TraversingVisitor::visit(block);
378 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
380 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
381 for(; (j!=expressions.end() && j->first.declaration==i->second); )
383 if(j->second.expression && j->second.inline_point)
384 inline_expression(*j->second.expression, *j->second.inline_point);
386 expressions.erase(j++);
390 /* Expressions assigned in this block may depend on local variables of the
391 block. If this is a conditionally executed block, the assignments might not
392 always happen. Mark the expressions as not available to any outer blocks. */
393 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
394 if(i->second.assign_scope==&block)
395 i->second.available = false;
398 void ExpressionInliner::visit(RefPtr<Expression> &expr)
402 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
404 if(iteration_body && !r_ref_info->trivial)
406 /* Don't inline non-trivial expressions which were assigned outside
407 an iteration statement. The iteration may run multiple times, which
408 would cause the expression to also be evaluated multiple times. */
409 Block *i = r_ref_info->assign_scope;
410 for(; (i && i!=iteration_body); i=i->parent) ;
415 if(r_ref_info->trivial)
416 inline_expression(*r_ref_info->expression, expr);
418 /* Record the inline point for a non-trivial expression but don't
419 inline it yet. It might turn out it shouldn't be inlined after all. */
420 r_ref_info->inline_point = &expr;
426 void ExpressionInliner::visit(VariableReference &var)
430 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
431 if(i!=expressions.end())
433 /* If a non-trivial expression is referenced multiple times, don't
435 if(i->second.inline_point && !i->second.trivial)
436 i->second.expression = 0;
437 /* Mutating expressions are analogous to self-referencing assignments
438 and prevent inlining. */
440 i->second.expression = 0;
441 r_ref_info = &i->second;
446 void ExpressionInliner::visit(MemberAccess &memacc)
452 void ExpressionInliner::visit(Swizzle &swizzle)
458 void ExpressionInliner::visit(UnaryExpression &unary)
460 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
461 visit(unary.expression);
465 void ExpressionInliner::visit(BinaryExpression &binary)
469 SetFlag clear_target(mutating, false);
475 void ExpressionInliner::visit(Assignment &assign)
478 SetFlag set_target(mutating);
484 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
485 if(i!=expressions.end())
487 /* Self-referencing assignments can't be inlined without additional
488 work. Just clear any previous expression. */
489 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
490 i->second.assign_scope = current_block;
491 i->second.inline_point = 0;
492 i->second.available = true;
498 void ExpressionInliner::visit(TernaryExpression &ternary)
500 visit(ternary.condition);
501 visit(ternary.true_expr);
502 visit(ternary.false_expr);
506 void ExpressionInliner::visit(FunctionCall &call)
508 TraversingVisitor::visit(call);
512 void ExpressionInliner::visit(VariableDeclaration &var)
516 TraversingVisitor::visit(var);
518 bool constant = var.constant;
519 if(constant && var.layout)
521 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
522 constant = (i->name!="constant_id");
525 /* Only inline global variables if they're constant and have trivial
526 initializers. Non-constant variables could change in ways which are hard to
527 analyze and non-trivial expressions could be expensive to inline. */
528 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
530 ExpressionInfo &info = expressions[&var];
531 /* Assume variables declared in an iteration initialization statement
532 will have their values change throughout the iteration. */
533 info.expression = (iteration_init ? 0 : var.init_expression.get());
534 info.assign_scope = current_block;
535 info.trivial = r_trivial;
539 void ExpressionInliner::visit(Iteration &iter)
541 SetForScope<Block *> set_block(current_block, &iter.body);
542 if(iter.init_statement)
544 SetFlag set_init(iteration_init);
545 iter.init_statement->visit(*this);
548 SetForScope<Block *> set_body(iteration_body, &iter.body);
550 visit(iter.condition);
551 iter.body.visit(*this);
552 if(iter.loop_expression)
553 visit(iter.loop_expression);
558 T ConstantFolder::evaluate_logical(char oper, T left, T right)
562 case '&': return left&right;
563 case '|': return left|right;
564 case '^': return left^right;
570 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
572 switch(oper[0]|oper[1])
574 case '<': return left<right;
575 case '<'|'=': return left<=right;
576 case '>': return left>right;
577 case '>'|'=': return left>=right;
578 default: return false;
583 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
587 case '+': return left+right;
588 case '-': return left-right;
589 case '*': return left*right;
590 case '/': return left/right;
596 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
600 case '%': return left%right;
601 case '<': return left<<right;
602 case '>': return left>>right;
608 void ConstantFolder::convert_to_result(const Variant &value)
610 if(value.check_type<bool>())
611 set_result(static_cast<T>(value.value<bool>()));
612 else if(value.check_type<int>())
613 set_result(static_cast<T>(value.value<int>()));
614 else if(value.check_type<unsigned>())
615 set_result(static_cast<T>(value.value<unsigned>()));
616 else if(value.check_type<float>())
617 set_result(static_cast<T>(value.value<float>()));
620 void ConstantFolder::set_result(const Variant &value, bool literal)
622 r_constant_value = value;
627 void ConstantFolder::visit(RefPtr<Expression> &expr)
629 r_constant_value = Variant();
632 r_uses_iter_var = false;
634 /* Don't replace literals since they'd only be replaced with an identical
635 literal. Also skip anything that uses an iteration variable, but pass on
636 the result so the Iteration visiting function can handle it. */
637 if(!r_constant || r_literal || r_uses_iter_var)
640 RefPtr<Literal> literal = new Literal;
641 if(r_constant_value.check_type<bool>())
642 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
643 else if(r_constant_value.check_type<int>())
644 literal->token = lexical_cast<string>(r_constant_value.value<int>());
645 else if(r_constant_value.check_type<unsigned>())
646 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
647 else if(r_constant_value.check_type<float>())
649 literal->token = lexical_cast<string>(r_constant_value.value<float>());
650 if(isnumrc(literal->token))
651 literal->token += ".0";
658 literal->value = r_constant_value;
662 void ConstantFolder::visit(Literal &literal)
664 set_result(literal.value, true);
667 void ConstantFolder::visit(VariableReference &var)
669 /* If an iteration variable is initialized with a constant value, return
670 that value here for the purpose of evaluating the loop condition for the
672 if(var.declaration==iteration_var)
674 set_result(iter_init_value);
675 r_uses_iter_var = true;
679 void ConstantFolder::visit(MemberAccess &memacc)
681 TraversingVisitor::visit(memacc);
685 void ConstantFolder::visit(Swizzle &swizzle)
687 TraversingVisitor::visit(swizzle);
691 void ConstantFolder::visit(UnaryExpression &unary)
693 TraversingVisitor::visit(unary);
694 bool can_fold = r_constant;
699 char oper = unary.oper->token[0];
700 char oper2 = unary.oper->token[1];
703 if(r_constant_value.check_type<bool>())
704 set_result(!r_constant_value.value<bool>());
708 if(r_constant_value.check_type<int>())
709 set_result(~r_constant_value.value<int>());
710 else if(r_constant_value.check_type<unsigned>())
711 set_result(~r_constant_value.value<unsigned>());
713 else if(oper=='-' && !oper2)
715 if(r_constant_value.check_type<int>())
716 set_result(-r_constant_value.value<int>());
717 else if(r_constant_value.check_type<unsigned>())
718 set_result(-r_constant_value.value<unsigned>());
719 else if(r_constant_value.check_type<float>())
720 set_result(-r_constant_value.value<float>());
724 void ConstantFolder::visit(BinaryExpression &binary)
727 bool left_constant = r_constant;
728 bool left_iter_var = r_uses_iter_var;
729 Variant left_value = r_constant_value;
732 r_uses_iter_var = true;
734 bool can_fold = (left_constant && r_constant);
739 // Currently only expressions with both sides of equal types are handled.
740 if(!left_value.check_same_type(r_constant_value))
743 char oper = binary.oper->token[0];
744 char oper2 = binary.oper->token[1];
745 if(oper=='&' || oper=='|' || oper=='^')
747 if(oper2==oper && left_value.check_type<bool>())
748 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
749 else if(!oper2 && left_value.check_type<int>())
750 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
751 else if(!oper2 && left_value.check_type<unsigned>())
752 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
754 else if((oper=='<' || oper=='>') && oper2!=oper)
756 if(left_value.check_type<int>())
757 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
758 else if(left_value.check_type<unsigned>())
759 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
760 else if(left_value.check_type<float>())
761 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
763 else if((oper=='=' || oper=='!') && oper2=='=')
765 if(left_value.check_type<int>())
766 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
767 else if(left_value.check_type<unsigned>())
768 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
769 else if(left_value.check_type<float>())
770 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
772 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
774 if(left_value.check_type<int>())
775 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
776 else if(left_value.check_type<unsigned>())
777 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
778 else if(left_value.check_type<float>())
779 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
781 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
783 if(left_value.check_type<int>())
784 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
785 else if(left_value.check_type<unsigned>())
786 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
790 void ConstantFolder::visit(Assignment &assign)
792 TraversingVisitor::visit(assign);
796 void ConstantFolder::visit(TernaryExpression &ternary)
798 TraversingVisitor::visit(ternary);
802 void ConstantFolder::visit(FunctionCall &call)
804 if(call.constructor && call.type && call.arguments.size()==1)
806 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
809 call.arguments[0]->visit(*this);
810 bool can_fold = r_constant;
815 if(basic->kind==BasicTypeDeclaration::BOOL)
816 convert_to_result<bool>(r_constant_value);
817 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
818 convert_to_result<int>(r_constant_value);
819 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
820 convert_to_result<unsigned>(r_constant_value);
821 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
822 convert_to_result<float>(r_constant_value);
828 TraversingVisitor::visit(call);
832 void ConstantFolder::visit(VariableDeclaration &var)
834 if(iteration_init && var.init_expression)
836 visit(var.init_expression);
839 /* Record the value of a constant initialization expression of an
840 iteration, so it can be used to evaluate the loop condition. */
841 iteration_var = &var;
842 iter_init_value = r_constant_value;
846 TraversingVisitor::visit(var);
849 void ConstantFolder::visit(Iteration &iter)
851 SetForScope<Block *> set_block(current_block, &iter.body);
853 /* The iteration variable is not normally inlined into expressions, so we
854 process it specially here. If the initial value causes the loop condition
855 to evaluate to false, then the expression can be folded. */
857 if(iter.init_statement)
859 SetFlag set_init(iteration_init);
860 iter.init_statement->visit(*this);
865 visit(iter.condition);
866 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
868 RefPtr<Literal> literal = new Literal;
869 literal->token = "false";
870 literal->value = r_constant_value;
871 iter.condition = literal;
876 iter.body.visit(*this);
877 if(iter.loop_expression)
878 visit(iter.loop_expression);
882 void ConstantConditionEliminator::apply(Stage &stage)
884 stage.content.visit(*this);
885 NodeRemover().apply(stage, nodes_to_remove);
888 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
890 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
891 if(literal->value.check_type<bool>())
892 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
896 void ConstantConditionEliminator::visit(Block &block)
898 SetForScope<Block *> set_block(current_block, &block);
899 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
906 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
908 r_ternary_result = 0;
911 expr = r_ternary_result;
912 r_ternary_result = 0;
915 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
917 ConstantStatus result = check_constant_condition(*ternary.condition);
918 if(result!=NOT_CONSTANT)
919 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
921 r_ternary_result = 0;
924 void ConstantConditionEliminator::visit(Conditional &cond)
926 ConstantStatus result = check_constant_condition(*cond.condition);
927 if(result!=NOT_CONSTANT)
929 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
930 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
931 current_block->body.splice(insert_point, block.body);
932 nodes_to_remove.insert(&cond);
936 TraversingVisitor::visit(cond);
939 void ConstantConditionEliminator::visit(Iteration &iter)
943 ConstantStatus result = check_constant_condition(*iter.condition);
944 if(result==CONSTANT_FALSE)
946 nodes_to_remove.insert(&iter);
951 TraversingVisitor::visit(iter);
955 UnreachableCodeRemover::UnreachableCodeRemover():
959 bool UnreachableCodeRemover::apply(Stage &stage)
961 stage.content.visit(*this);
962 NodeRemover().apply(stage, unreachable_nodes);
963 return !unreachable_nodes.empty();
966 void UnreachableCodeRemover::visit(Block &block)
968 NodeList<Statement>::iterator i = block.body.begin();
969 for(; (reachable && i!=block.body.end()); ++i)
971 for(; i!=block.body.end(); ++i)
972 unreachable_nodes.insert(i->get());
975 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
977 TraversingVisitor::visit(func);
981 void UnreachableCodeRemover::visit(Conditional &cond)
983 cond.body.visit(*this);
984 bool reachable_if_true = reachable;
986 cond.else_body.visit(*this);
988 reachable |= reachable_if_true;
991 void UnreachableCodeRemover::visit(Iteration &iter)
993 TraversingVisitor::visit(iter);
995 /* Always consider code after a loop reachable, since there's no checking
996 for whether the loop executes. */
1001 bool UnusedTypeRemover::apply(Stage &stage)
1003 stage.content.visit(*this);
1004 NodeRemover().apply(stage, unused_nodes);
1005 return !unused_nodes.empty();
1008 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1010 unused_nodes.erase(expr->type);
1011 TraversingVisitor::visit(expr);
1014 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1017 unused_nodes.erase(type.base_type);
1018 unused_nodes.insert(&type);
1021 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1024 unused_nodes.erase(type.base_type);
1025 unused_nodes.insert(&type);
1028 void UnusedTypeRemover::visit(StructDeclaration &strct)
1030 unused_nodes.insert(&strct);
1031 TraversingVisitor::visit(strct);
1034 void UnusedTypeRemover::visit(VariableDeclaration &var)
1036 unused_nodes.erase(var.type_declaration);
1037 TraversingVisitor::visit(var);
1040 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1042 unused_nodes.erase(iface.type_declaration);
1045 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1047 unused_nodes.erase(func.return_type_declaration);
1048 TraversingVisitor::visit(func);
1052 UnusedVariableRemover::UnusedVariableRemover():
1056 assignment_target(false),
1057 r_side_effects(false),
1059 composite_reference(false)
1062 bool UnusedVariableRemover::apply(Stage &s)
1065 s.content.visit(*this);
1067 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1068 if(i->used_by.empty())
1069 unused_nodes.insert(i->node);
1071 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1073 if(i->second.output)
1075 /* The last visible assignments of output variables are used by the
1076 next stage or the API. */
1077 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1078 unused_nodes.erase((*j)->node);
1081 if(!i->second.output && !i->second.referenced)
1083 // Don't remove variables from inside interface blocks.
1084 if(!i->second.interface_block)
1085 unused_nodes.insert(i->first);
1087 else if(i->second.interface_block)
1088 // Interface blocks are kept if even one member is used.
1089 unused_nodes.erase(i->second.interface_block);
1092 NodeRemover().apply(s, unused_nodes);
1094 return !unused_nodes.empty();
1097 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1099 VariableInfo &var_info = variables[target.declaration];
1100 var_info.referenced = true;
1101 if(!assignment_target)
1103 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1105 bool covered = true;
1106 for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1108 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1109 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1110 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1112 unsigned index1 = (*i)->target.chain[j]&0x3F;
1113 unsigned index2 = target.chain[j]&0x3F;
1114 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1115 covered = index1&index2;
1116 else if(type1==Assignment::Target::ARRAY && index1<4)
1117 covered = index2&(1<<index1);
1118 else if(type2==Assignment::Target::ARRAY && index2<4)
1119 covered = index1&(1<<index2);
1120 /* If it's some other combination (shouldn't happen), leave
1124 covered = ((*i)->target.chain[j]==target.chain[j]);
1127 (*i)->used_by.push_back(&node);
1132 void UnusedVariableRemover::visit(VariableReference &var)
1134 if(composite_reference)
1135 r_reference.declaration = var.declaration;
1137 referenced(var.declaration, var);
1140 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1142 if(composite_reference)
1143 r_reference.declaration = iface.declaration;
1145 referenced(iface.declaration, iface);
1148 void UnusedVariableRemover::visit_composite(Expression &expr)
1150 if(!composite_reference)
1151 r_reference = Assignment::Target();
1153 SetFlag set_composite(composite_reference);
1157 void UnusedVariableRemover::visit(MemberAccess &memacc)
1159 visit_composite(*memacc.left);
1161 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1163 if(!composite_reference && r_reference.declaration)
1164 referenced(r_reference, memacc);
1167 void UnusedVariableRemover::visit(Swizzle &swizzle)
1169 visit_composite(*swizzle.left);
1172 for(unsigned i=0; i<swizzle.count; ++i)
1173 mask |= 1<<swizzle.components[i];
1174 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1176 if(!composite_reference && r_reference.declaration)
1177 referenced(r_reference, swizzle);
1180 void UnusedVariableRemover::visit(UnaryExpression &unary)
1182 TraversingVisitor::visit(unary);
1183 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1184 r_side_effects = true;
1187 void UnusedVariableRemover::visit(BinaryExpression &binary)
1189 if(binary.oper->token[0]=='[')
1191 visit_composite(*binary.left);
1194 SetFlag clear_assignment(assignment_target, false);
1195 SetFlag clear_composite(composite_reference, false);
1196 binary.right->visit(*this);
1199 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1201 if(!composite_reference && r_reference.declaration)
1202 referenced(r_reference, binary);
1206 SetFlag clear_composite(composite_reference, false);
1207 TraversingVisitor::visit(binary);
1211 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1213 SetFlag clear_composite(composite_reference, false);
1214 TraversingVisitor::visit(ternary);
1217 void UnusedVariableRemover::visit(Assignment &assign)
1220 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1221 assign.left->visit(*this);
1223 assign.right->visit(*this);
1224 r_assignment = &assign;
1225 r_side_effects = true;
1228 void UnusedVariableRemover::visit(FunctionCall &call)
1230 SetFlag clear_composite(composite_reference, false);
1231 TraversingVisitor::visit(call);
1232 /* Treat function calls as having side effects so expression statements
1233 consisting of nothing but a function call won't be optimized away. */
1234 r_side_effects = true;
1236 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1238 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1239 if(i->second.output)
1240 referenced(i->first, call);
1244 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1246 assignments.push_back(AssignmentInfo());
1247 AssignmentInfo &assign_info = assignments.back();
1248 assign_info.node = &node;
1249 assign_info.target = target;
1251 /* An assignment to the target hides any assignments to the same target or
1253 VariableInfo &var_info = variables[target.declaration];
1254 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1256 const Assignment::Target &t = var_info.assignments[i]->target;
1258 bool subfield = (t.chain_len>=target.chain_len);
1259 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1260 subfield = (t.chain[j]==target.chain[j]);
1263 var_info.assignments.erase(var_info.assignments.begin()+i);
1268 var_info.assignments.push_back(&assign_info);
1271 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1274 r_side_effects = false;
1275 TraversingVisitor::visit(expr);
1276 if(r_assignment && r_assignment->target.declaration)
1277 record_assignment(r_assignment->target, expr);
1279 unused_nodes.insert(&expr);
1282 void UnusedVariableRemover::visit(StructDeclaration &strct)
1284 SetFlag set_struct(in_struct);
1285 TraversingVisitor::visit(strct);
1288 void UnusedVariableRemover::visit(VariableDeclaration &var)
1290 TraversingVisitor::visit(var);
1295 VariableInfo &var_info = variables[&var];
1296 var_info.interface_block = interface_block;
1298 /* Mark variables as output if they're used by the next stage or the
1301 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1303 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1305 if(var.init_expression)
1307 var_info.initialized = true;
1308 record_assignment(&var, *var.init_expression);
1312 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1314 VariableInfo &var_info = variables[&iface];
1315 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1318 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1320 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1322 BlockVariableMap::iterator j = variables.find(i->first);
1323 if(j!=variables.end())
1325 /* The merged blocks started as copies of each other so any common
1326 assignments must be in the beginning. */
1328 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1329 if(i->second.assignments[k]!=j->second.assignments[k])
1332 // Remaining assignments are unique to each block; merge them.
1333 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1334 j->second.referenced |= i->second.referenced;
1337 variables.insert(*i);
1341 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1343 if(func.body.body.empty())
1346 BlockVariableMap saved_vars = variables;
1347 // Assignments from other functions should not be visible.
1348 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1349 i->second.assignments.resize(i->second.initialized);
1350 TraversingVisitor::visit(func);
1351 swap(variables, saved_vars);
1352 merge_variables(saved_vars);
1354 /* Always treat function parameters as referenced. Removing unused
1355 parameters is not currently supported. */
1356 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1358 BlockVariableMap::iterator j = variables.find(i->get());
1359 if(j!=variables.end())
1360 j->second.referenced = true;
1364 void UnusedVariableRemover::visit(Conditional &cond)
1366 cond.condition->visit(*this);
1367 BlockVariableMap saved_vars = variables;
1368 cond.body.visit(*this);
1369 swap(saved_vars, variables);
1370 cond.else_body.visit(*this);
1372 /* Visible assignments after the conditional is the union of those visible
1373 at the end of the if and else blocks. If there was no else block, then it's
1374 the union of the if block and the state before it. */
1375 merge_variables(saved_vars);
1378 void UnusedVariableRemover::visit(Iteration &iter)
1380 BlockVariableMap saved_vars = variables;
1381 TraversingVisitor::visit(iter);
1383 /* Merge assignments from the iteration, without clearing previous state.
1384 Further analysis is needed to determine which parts of the iteration body
1385 are always executed, if any. */
1386 merge_variables(saved_vars);
1390 bool UnusedFunctionRemover::apply(Stage &stage)
1392 stage.content.visit(*this);
1393 NodeRemover().apply(stage, unused_nodes);
1394 return !unused_nodes.empty();
1397 void UnusedFunctionRemover::visit(FunctionCall &call)
1399 TraversingVisitor::visit(call);
1401 unused_nodes.erase(call.declaration);
1402 if(call.declaration && call.declaration->definition!=call.declaration)
1403 used_definitions.insert(call.declaration->definition);
1406 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1408 TraversingVisitor::visit(func);
1410 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1411 unused_nodes.insert(&func);