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>(), Fmt().precision(8));
650 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
651 literal->token += ".0";
658 literal->value = r_constant_value;
663 void ConstantFolder::visit(Literal &literal)
665 set_result(literal.value, true);
668 void ConstantFolder::visit(VariableReference &var)
670 /* If an iteration variable is initialized with a constant value, return
671 that value here for the purpose of evaluating the loop condition for the
673 if(var.declaration==iteration_var)
675 set_result(iter_init_value);
676 r_uses_iter_var = true;
680 void ConstantFolder::visit(MemberAccess &memacc)
682 TraversingVisitor::visit(memacc);
686 void ConstantFolder::visit(Swizzle &swizzle)
688 TraversingVisitor::visit(swizzle);
692 void ConstantFolder::visit(UnaryExpression &unary)
694 TraversingVisitor::visit(unary);
695 bool can_fold = r_constant;
700 char oper = unary.oper->token[0];
701 char oper2 = unary.oper->token[1];
704 if(r_constant_value.check_type<bool>())
705 set_result(!r_constant_value.value<bool>());
709 if(r_constant_value.check_type<int>())
710 set_result(~r_constant_value.value<int>());
711 else if(r_constant_value.check_type<unsigned>())
712 set_result(~r_constant_value.value<unsigned>());
714 else if(oper=='-' && !oper2)
716 if(r_constant_value.check_type<int>())
717 set_result(-r_constant_value.value<int>());
718 else if(r_constant_value.check_type<unsigned>())
719 set_result(-r_constant_value.value<unsigned>());
720 else if(r_constant_value.check_type<float>())
721 set_result(-r_constant_value.value<float>());
725 void ConstantFolder::visit(BinaryExpression &binary)
728 bool left_constant = r_constant;
729 bool left_iter_var = r_uses_iter_var;
730 Variant left_value = r_constant_value;
733 r_uses_iter_var = true;
735 bool can_fold = (left_constant && r_constant);
740 // Currently only expressions with both sides of equal types are handled.
741 if(!left_value.check_same_type(r_constant_value))
744 char oper = binary.oper->token[0];
745 char oper2 = binary.oper->token[1];
746 if(oper=='&' || oper=='|' || oper=='^')
748 if(oper2==oper && left_value.check_type<bool>())
749 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
750 else if(!oper2 && left_value.check_type<int>())
751 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
752 else if(!oper2 && left_value.check_type<unsigned>())
753 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
755 else if((oper=='<' || oper=='>') && oper2!=oper)
757 if(left_value.check_type<int>())
758 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
759 else if(left_value.check_type<unsigned>())
760 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
761 else if(left_value.check_type<float>())
762 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
764 else if((oper=='=' || oper=='!') && oper2=='=')
766 if(left_value.check_type<int>())
767 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
768 else if(left_value.check_type<unsigned>())
769 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
770 else if(left_value.check_type<float>())
771 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
773 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
775 if(left_value.check_type<int>())
776 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
777 else if(left_value.check_type<unsigned>())
778 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
779 else if(left_value.check_type<float>())
780 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
782 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
784 if(left_value.check_type<int>())
785 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
786 else if(left_value.check_type<unsigned>())
787 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
791 void ConstantFolder::visit(Assignment &assign)
793 TraversingVisitor::visit(assign);
797 void ConstantFolder::visit(TernaryExpression &ternary)
799 TraversingVisitor::visit(ternary);
803 void ConstantFolder::visit(FunctionCall &call)
805 if(call.constructor && call.type && call.arguments.size()==1)
807 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
810 call.arguments[0]->visit(*this);
811 bool can_fold = r_constant;
816 if(basic->kind==BasicTypeDeclaration::BOOL)
817 convert_to_result<bool>(r_constant_value);
818 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
819 convert_to_result<int>(r_constant_value);
820 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
821 convert_to_result<unsigned>(r_constant_value);
822 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
823 convert_to_result<float>(r_constant_value);
829 TraversingVisitor::visit(call);
833 void ConstantFolder::visit(VariableDeclaration &var)
835 if(iteration_init && var.init_expression)
837 visit(var.init_expression);
840 /* Record the value of a constant initialization expression of an
841 iteration, so it can be used to evaluate the loop condition. */
842 iteration_var = &var;
843 iter_init_value = r_constant_value;
847 TraversingVisitor::visit(var);
850 void ConstantFolder::visit(Iteration &iter)
852 SetForScope<Block *> set_block(current_block, &iter.body);
854 /* The iteration variable is not normally inlined into expressions, so we
855 process it specially here. If the initial value causes the loop condition
856 to evaluate to false, then the expression can be folded. */
858 if(iter.init_statement)
860 SetFlag set_init(iteration_init);
861 iter.init_statement->visit(*this);
866 visit(iter.condition);
867 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
869 RefPtr<Literal> literal = new Literal;
870 literal->token = "false";
871 literal->value = r_constant_value;
872 iter.condition = literal;
877 iter.body.visit(*this);
878 if(iter.loop_expression)
879 visit(iter.loop_expression);
883 void ConstantConditionEliminator::apply(Stage &stage)
885 stage.content.visit(*this);
886 NodeRemover().apply(stage, nodes_to_remove);
889 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
891 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
892 if(literal->value.check_type<bool>())
893 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
897 void ConstantConditionEliminator::visit(Block &block)
899 SetForScope<Block *> set_block(current_block, &block);
900 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
907 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
909 r_ternary_result = 0;
912 expr = r_ternary_result;
913 r_ternary_result = 0;
916 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
918 ConstantStatus result = check_constant_condition(*ternary.condition);
919 if(result!=NOT_CONSTANT)
920 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
922 r_ternary_result = 0;
925 void ConstantConditionEliminator::visit(Conditional &cond)
927 ConstantStatus result = check_constant_condition(*cond.condition);
928 if(result!=NOT_CONSTANT)
930 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
931 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
932 current_block->body.splice(insert_point, block.body);
933 nodes_to_remove.insert(&cond);
937 TraversingVisitor::visit(cond);
940 void ConstantConditionEliminator::visit(Iteration &iter)
944 ConstantStatus result = check_constant_condition(*iter.condition);
945 if(result==CONSTANT_FALSE)
947 nodes_to_remove.insert(&iter);
952 TraversingVisitor::visit(iter);
956 UnreachableCodeRemover::UnreachableCodeRemover():
960 bool UnreachableCodeRemover::apply(Stage &stage)
962 stage.content.visit(*this);
963 NodeRemover().apply(stage, unreachable_nodes);
964 return !unreachable_nodes.empty();
967 void UnreachableCodeRemover::visit(Block &block)
969 NodeList<Statement>::iterator i = block.body.begin();
970 for(; (reachable && i!=block.body.end()); ++i)
972 for(; i!=block.body.end(); ++i)
973 unreachable_nodes.insert(i->get());
976 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
978 TraversingVisitor::visit(func);
982 void UnreachableCodeRemover::visit(Conditional &cond)
984 cond.body.visit(*this);
985 bool reachable_if_true = reachable;
987 cond.else_body.visit(*this);
989 reachable |= reachable_if_true;
992 void UnreachableCodeRemover::visit(Iteration &iter)
994 TraversingVisitor::visit(iter);
996 /* Always consider code after a loop reachable, since there's no checking
997 for whether the loop executes. */
1002 bool UnusedTypeRemover::apply(Stage &stage)
1004 stage.content.visit(*this);
1005 NodeRemover().apply(stage, unused_nodes);
1006 return !unused_nodes.empty();
1009 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1011 unused_nodes.erase(expr->type);
1012 TraversingVisitor::visit(expr);
1015 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1018 unused_nodes.erase(type.base_type);
1019 unused_nodes.insert(&type);
1022 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1025 unused_nodes.erase(type.base_type);
1026 unused_nodes.insert(&type);
1029 void UnusedTypeRemover::visit(StructDeclaration &strct)
1031 unused_nodes.insert(&strct);
1032 TraversingVisitor::visit(strct);
1035 void UnusedTypeRemover::visit(VariableDeclaration &var)
1037 unused_nodes.erase(var.type_declaration);
1038 TraversingVisitor::visit(var);
1041 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1043 unused_nodes.erase(iface.type_declaration);
1046 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1048 unused_nodes.erase(func.return_type_declaration);
1049 TraversingVisitor::visit(func);
1053 UnusedVariableRemover::UnusedVariableRemover():
1057 assignment_target(false),
1058 r_side_effects(false),
1060 composite_reference(false),
1064 bool UnusedVariableRemover::apply(Stage &s)
1067 s.content.visit(*this);
1069 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1070 if(i->used_by.empty())
1071 unused_nodes.insert(i->node);
1073 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1075 if(i->second.output)
1077 /* The last visible assignments of output variables are used by the
1078 next stage or the API. */
1079 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1080 unused_nodes.erase((*j)->node);
1083 if(!i->second.output && !i->second.referenced)
1085 // Don't remove variables from inside interface blocks.
1086 if(!i->second.interface_block)
1087 unused_nodes.insert(i->first);
1089 else if(i->second.interface_block)
1090 // Interface blocks are kept if even one member is used.
1091 unused_nodes.erase(i->second.interface_block);
1094 NodeRemover().apply(s, unused_nodes);
1096 return !unused_nodes.empty();
1099 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1101 VariableInfo &var_info = variables[target.declaration];
1102 var_info.referenced = true;
1103 if(!assignment_target)
1105 bool loop_external = false;
1106 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1108 bool covered = true;
1109 for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1111 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1112 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1113 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1115 unsigned index1 = (*i)->target.chain[j]&0x3F;
1116 unsigned index2 = target.chain[j]&0x3F;
1117 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1118 covered = index1&index2;
1119 else if(type1==Assignment::Target::ARRAY && index1<4)
1120 covered = index2&(1<<index1);
1121 else if(type2==Assignment::Target::ARRAY && index2<4)
1122 covered = index1&(1<<index2);
1123 /* If it's some other combination (shouldn't happen), leave
1127 covered = ((*i)->target.chain[j]==target.chain[j]);
1132 (*i)->used_by.push_back(&node);
1133 if((*i)->in_loop<in_loop)
1134 loop_external = true;
1139 loop_ext_refs.push_back(&node);
1143 void UnusedVariableRemover::visit(VariableReference &var)
1145 if(composite_reference)
1146 r_reference.declaration = var.declaration;
1148 referenced(var.declaration, var);
1151 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1153 if(composite_reference)
1154 r_reference.declaration = iface.declaration;
1156 referenced(iface.declaration, iface);
1159 void UnusedVariableRemover::visit_composite(Expression &expr)
1161 if(!composite_reference)
1162 r_reference = Assignment::Target();
1164 SetFlag set_composite(composite_reference);
1168 void UnusedVariableRemover::visit(MemberAccess &memacc)
1170 visit_composite(*memacc.left);
1172 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1174 if(!composite_reference && r_reference.declaration)
1175 referenced(r_reference, memacc);
1178 void UnusedVariableRemover::visit(Swizzle &swizzle)
1180 visit_composite(*swizzle.left);
1183 for(unsigned i=0; i<swizzle.count; ++i)
1184 mask |= 1<<swizzle.components[i];
1185 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1187 if(!composite_reference && r_reference.declaration)
1188 referenced(r_reference, swizzle);
1191 void UnusedVariableRemover::visit(UnaryExpression &unary)
1193 TraversingVisitor::visit(unary);
1194 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1195 r_side_effects = true;
1198 void UnusedVariableRemover::visit(BinaryExpression &binary)
1200 if(binary.oper->token[0]=='[')
1202 visit_composite(*binary.left);
1205 SetFlag clear_assignment(assignment_target, false);
1206 SetFlag clear_composite(composite_reference, false);
1207 binary.right->visit(*this);
1210 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1212 if(!composite_reference && r_reference.declaration)
1213 referenced(r_reference, binary);
1217 SetFlag clear_composite(composite_reference, false);
1218 TraversingVisitor::visit(binary);
1222 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1224 SetFlag clear_composite(composite_reference, false);
1225 TraversingVisitor::visit(ternary);
1228 void UnusedVariableRemover::visit(Assignment &assign)
1231 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1232 assign.left->visit(*this);
1234 assign.right->visit(*this);
1235 r_assignment = &assign;
1236 r_side_effects = true;
1239 void UnusedVariableRemover::visit(FunctionCall &call)
1241 SetFlag clear_composite(composite_reference, false);
1242 TraversingVisitor::visit(call);
1243 /* Treat function calls as having side effects so expression statements
1244 consisting of nothing but a function call won't be optimized away. */
1245 r_side_effects = true;
1247 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1249 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1250 if(i->second.output)
1251 referenced(i->first, call);
1255 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1257 assignments.push_back(AssignmentInfo());
1258 AssignmentInfo &assign_info = assignments.back();
1259 assign_info.node = &node;
1260 assign_info.target = target;
1261 assign_info.in_loop = in_loop;
1263 /* An assignment to the target hides any assignments to the same target or
1265 VariableInfo &var_info = variables[target.declaration];
1266 for(unsigned i=0; i<var_info.assignments.size(); )
1268 const Assignment::Target &t = var_info.assignments[i]->target;
1270 bool subfield = (t.chain_len>=target.chain_len);
1271 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1272 subfield = (t.chain[j]==target.chain[j]);
1275 var_info.assignments.erase(var_info.assignments.begin()+i);
1280 var_info.assignments.push_back(&assign_info);
1283 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1286 r_side_effects = false;
1287 TraversingVisitor::visit(expr);
1288 if(r_assignment && r_assignment->target.declaration)
1289 record_assignment(r_assignment->target, expr);
1291 unused_nodes.insert(&expr);
1294 void UnusedVariableRemover::visit(StructDeclaration &strct)
1296 SetFlag set_struct(in_struct);
1297 TraversingVisitor::visit(strct);
1300 void UnusedVariableRemover::visit(VariableDeclaration &var)
1302 TraversingVisitor::visit(var);
1307 VariableInfo &var_info = variables[&var];
1308 var_info.interface_block = interface_block;
1310 /* Mark variables as output if they're used by the next stage or the
1313 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1315 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1317 if(var.init_expression)
1319 var_info.initialized = true;
1320 record_assignment(&var, *var.init_expression);
1324 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1326 VariableInfo &var_info = variables[&iface];
1327 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1330 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1332 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1334 BlockVariableMap::iterator j = variables.find(i->first);
1335 if(j!=variables.end())
1337 /* The merged blocks started as copies of each other so any common
1338 assignments must be in the beginning. */
1340 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1341 if(i->second.assignments[k]!=j->second.assignments[k])
1344 // Remaining assignments are unique to each block; merge them.
1345 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1346 j->second.referenced |= i->second.referenced;
1349 variables.insert(*i);
1353 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1355 if(func.body.body.empty())
1358 BlockVariableMap saved_vars = variables;
1359 // Assignments from other functions should not be visible.
1360 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1361 i->second.assignments.resize(i->second.initialized);
1362 TraversingVisitor::visit(func);
1363 swap(variables, saved_vars);
1364 merge_variables(saved_vars);
1366 /* Always treat function parameters as referenced. Removing unused
1367 parameters is not currently supported. */
1368 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1370 BlockVariableMap::iterator j = variables.find(i->get());
1371 if(j!=variables.end())
1372 j->second.referenced = true;
1376 void UnusedVariableRemover::visit(Conditional &cond)
1378 cond.condition->visit(*this);
1379 BlockVariableMap saved_vars = variables;
1380 cond.body.visit(*this);
1381 swap(saved_vars, variables);
1382 cond.else_body.visit(*this);
1384 /* Visible assignments after the conditional is the union of those visible
1385 at the end of the if and else blocks. If there was no else block, then it's
1386 the union of the if block and the state before it. */
1387 merge_variables(saved_vars);
1390 void UnusedVariableRemover::visit(Iteration &iter)
1392 BlockVariableMap saved_vars = variables;
1393 vector<Node *> saved_refs;
1394 swap(loop_ext_refs, saved_refs);
1396 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1397 TraversingVisitor::visit(iter);
1399 swap(loop_ext_refs, saved_refs);
1401 /* Visit the external references of the loop again to record assignments
1402 done in the loop as used. */
1403 for(vector<Node *>::const_iterator i=saved_refs.begin(); i!=saved_refs.end(); ++i)
1406 /* Merge assignments from the iteration, without clearing previous state.
1407 Further analysis is needed to determine which parts of the iteration body
1408 are always executed, if any. */
1409 merge_variables(saved_vars);
1413 bool UnusedFunctionRemover::apply(Stage &stage)
1415 stage.content.visit(*this);
1416 NodeRemover().apply(stage, unused_nodes);
1417 return !unused_nodes.empty();
1420 void UnusedFunctionRemover::visit(FunctionCall &call)
1422 TraversingVisitor::visit(call);
1424 unused_nodes.erase(call.declaration);
1425 if(call.declaration && call.declaration->definition!=call.declaration)
1426 used_definitions.insert(call.declaration->definition);
1429 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1431 TraversingVisitor::visit(func);
1433 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1434 unused_nodes.insert(&func);