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),
1063 bool UnusedVariableRemover::apply(Stage &s)
1066 s.content.visit(*this);
1068 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1069 if(i->used_by.empty())
1070 unused_nodes.insert(i->node);
1072 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1074 if(i->second.output)
1076 /* The last visible assignments of output variables are used by the
1077 next stage or the API. */
1078 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1079 unused_nodes.erase((*j)->node);
1082 if(!i->second.output && !i->second.referenced)
1084 // Don't remove variables from inside interface blocks.
1085 if(!i->second.interface_block)
1086 unused_nodes.insert(i->first);
1088 else if(i->second.interface_block)
1089 // Interface blocks are kept if even one member is used.
1090 unused_nodes.erase(i->second.interface_block);
1093 NodeRemover().apply(s, unused_nodes);
1095 return !unused_nodes.empty();
1098 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1100 VariableInfo &var_info = variables[target.declaration];
1101 var_info.referenced = true;
1102 if(!assignment_target)
1104 bool loop_external = false;
1105 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1107 bool covered = true;
1108 for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1110 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1111 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1112 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1114 unsigned index1 = (*i)->target.chain[j]&0x3F;
1115 unsigned index2 = target.chain[j]&0x3F;
1116 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1117 covered = index1&index2;
1118 else if(type1==Assignment::Target::ARRAY && index1<4)
1119 covered = index2&(1<<index1);
1120 else if(type2==Assignment::Target::ARRAY && index2<4)
1121 covered = index1&(1<<index2);
1122 /* If it's some other combination (shouldn't happen), leave
1126 covered = ((*i)->target.chain[j]==target.chain[j]);
1131 (*i)->used_by.push_back(&node);
1132 if((*i)->in_loop<in_loop)
1133 loop_external = true;
1138 loop_ext_refs.push_back(&node);
1142 void UnusedVariableRemover::visit(VariableReference &var)
1144 if(composite_reference)
1145 r_reference.declaration = var.declaration;
1147 referenced(var.declaration, var);
1150 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1152 if(composite_reference)
1153 r_reference.declaration = iface.declaration;
1155 referenced(iface.declaration, iface);
1158 void UnusedVariableRemover::visit_composite(Expression &expr)
1160 if(!composite_reference)
1161 r_reference = Assignment::Target();
1163 SetFlag set_composite(composite_reference);
1167 void UnusedVariableRemover::visit(MemberAccess &memacc)
1169 visit_composite(*memacc.left);
1171 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1173 if(!composite_reference && r_reference.declaration)
1174 referenced(r_reference, memacc);
1177 void UnusedVariableRemover::visit(Swizzle &swizzle)
1179 visit_composite(*swizzle.left);
1182 for(unsigned i=0; i<swizzle.count; ++i)
1183 mask |= 1<<swizzle.components[i];
1184 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1186 if(!composite_reference && r_reference.declaration)
1187 referenced(r_reference, swizzle);
1190 void UnusedVariableRemover::visit(UnaryExpression &unary)
1192 TraversingVisitor::visit(unary);
1193 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1194 r_side_effects = true;
1197 void UnusedVariableRemover::visit(BinaryExpression &binary)
1199 if(binary.oper->token[0]=='[')
1201 visit_composite(*binary.left);
1204 SetFlag clear_assignment(assignment_target, false);
1205 SetFlag clear_composite(composite_reference, false);
1206 binary.right->visit(*this);
1209 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1211 if(!composite_reference && r_reference.declaration)
1212 referenced(r_reference, binary);
1216 SetFlag clear_composite(composite_reference, false);
1217 TraversingVisitor::visit(binary);
1221 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1223 SetFlag clear_composite(composite_reference, false);
1224 TraversingVisitor::visit(ternary);
1227 void UnusedVariableRemover::visit(Assignment &assign)
1230 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1231 assign.left->visit(*this);
1233 assign.right->visit(*this);
1234 r_assignment = &assign;
1235 r_side_effects = true;
1238 void UnusedVariableRemover::visit(FunctionCall &call)
1240 SetFlag clear_composite(composite_reference, false);
1241 TraversingVisitor::visit(call);
1242 /* Treat function calls as having side effects so expression statements
1243 consisting of nothing but a function call won't be optimized away. */
1244 r_side_effects = true;
1246 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1248 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1249 if(i->second.output)
1250 referenced(i->first, call);
1254 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1256 assignments.push_back(AssignmentInfo());
1257 AssignmentInfo &assign_info = assignments.back();
1258 assign_info.node = &node;
1259 assign_info.target = target;
1260 assign_info.in_loop = in_loop;
1262 /* An assignment to the target hides any assignments to the same target or
1264 VariableInfo &var_info = variables[target.declaration];
1265 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1267 const Assignment::Target &t = var_info.assignments[i]->target;
1269 bool subfield = (t.chain_len>=target.chain_len);
1270 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1271 subfield = (t.chain[j]==target.chain[j]);
1274 var_info.assignments.erase(var_info.assignments.begin()+i);
1279 var_info.assignments.push_back(&assign_info);
1282 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1285 r_side_effects = false;
1286 TraversingVisitor::visit(expr);
1287 if(r_assignment && r_assignment->target.declaration)
1288 record_assignment(r_assignment->target, expr);
1290 unused_nodes.insert(&expr);
1293 void UnusedVariableRemover::visit(StructDeclaration &strct)
1295 SetFlag set_struct(in_struct);
1296 TraversingVisitor::visit(strct);
1299 void UnusedVariableRemover::visit(VariableDeclaration &var)
1301 TraversingVisitor::visit(var);
1306 VariableInfo &var_info = variables[&var];
1307 var_info.interface_block = interface_block;
1309 /* Mark variables as output if they're used by the next stage or the
1312 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1314 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1316 if(var.init_expression)
1318 var_info.initialized = true;
1319 record_assignment(&var, *var.init_expression);
1323 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1325 VariableInfo &var_info = variables[&iface];
1326 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1329 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1331 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1333 BlockVariableMap::iterator j = variables.find(i->first);
1334 if(j!=variables.end())
1336 /* The merged blocks started as copies of each other so any common
1337 assignments must be in the beginning. */
1339 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1340 if(i->second.assignments[k]!=j->second.assignments[k])
1343 // Remaining assignments are unique to each block; merge them.
1344 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1345 j->second.referenced |= i->second.referenced;
1348 variables.insert(*i);
1352 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1354 if(func.body.body.empty())
1357 BlockVariableMap saved_vars = variables;
1358 // Assignments from other functions should not be visible.
1359 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1360 i->second.assignments.resize(i->second.initialized);
1361 TraversingVisitor::visit(func);
1362 swap(variables, saved_vars);
1363 merge_variables(saved_vars);
1365 /* Always treat function parameters as referenced. Removing unused
1366 parameters is not currently supported. */
1367 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1369 BlockVariableMap::iterator j = variables.find(i->get());
1370 if(j!=variables.end())
1371 j->second.referenced = true;
1375 void UnusedVariableRemover::visit(Conditional &cond)
1377 cond.condition->visit(*this);
1378 BlockVariableMap saved_vars = variables;
1379 cond.body.visit(*this);
1380 swap(saved_vars, variables);
1381 cond.else_body.visit(*this);
1383 /* Visible assignments after the conditional is the union of those visible
1384 at the end of the if and else blocks. If there was no else block, then it's
1385 the union of the if block and the state before it. */
1386 merge_variables(saved_vars);
1389 void UnusedVariableRemover::visit(Iteration &iter)
1391 BlockVariableMap saved_vars = variables;
1392 vector<Node *> saved_refs;
1393 swap(loop_ext_refs, saved_refs);
1395 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1396 TraversingVisitor::visit(iter);
1398 swap(loop_ext_refs, saved_refs);
1400 /* Visit the external references of the loop again to record assignments
1401 done in the loop as used. */
1402 for(vector<Node *>::const_iterator i=saved_refs.begin(); i!=saved_refs.end(); ++i)
1405 /* Merge assignments from the iteration, without clearing previous state.
1406 Further analysis is needed to determine which parts of the iteration body
1407 are always executed, if any. */
1408 merge_variables(saved_vars);
1412 bool UnusedFunctionRemover::apply(Stage &stage)
1414 stage.content.visit(*this);
1415 NodeRemover().apply(stage, unused_nodes);
1416 return !unused_nodes.empty();
1419 void UnusedFunctionRemover::visit(FunctionCall &call)
1421 TraversingVisitor::visit(call);
1423 unused_nodes.erase(call.declaration);
1424 if(call.declaration && call.declaration->definition!=call.declaration)
1425 used_definitions.insert(call.declaration->definition);
1428 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1430 TraversingVisitor::visit(func);
1432 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1433 unused_nodes.insert(&func);