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<float>())
615 set_result(static_cast<T>(value.value<float>()));
618 void ConstantFolder::set_result(const Variant &value, bool literal)
620 r_constant_value = value;
625 void ConstantFolder::visit(RefPtr<Expression> &expr)
627 r_constant_value = Variant();
630 r_uses_iter_var = false;
632 /* Don't replace literals since they'd only be replaced with an identical
633 literal. Also skip anything that uses an iteration variable, but pass on
634 the result so the Iteration visiting function can handle it. */
635 if(!r_constant || r_literal || r_uses_iter_var)
638 RefPtr<Literal> literal = new Literal;
639 if(r_constant_value.check_type<bool>())
640 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
641 else if(r_constant_value.check_type<int>())
642 literal->token = lexical_cast<string>(r_constant_value.value<int>());
643 else if(r_constant_value.check_type<float>())
645 literal->token = lexical_cast<string>(r_constant_value.value<float>());
646 if(isnumrc(literal->token))
647 literal->token += ".0";
654 literal->value = r_constant_value;
658 void ConstantFolder::visit(Literal &literal)
660 set_result(literal.value, true);
663 void ConstantFolder::visit(VariableReference &var)
665 /* If an iteration variable is initialized with a constant value, return
666 that value here for the purpose of evaluating the loop condition for the
668 if(var.declaration==iteration_var)
670 set_result(iter_init_value);
671 r_uses_iter_var = true;
675 void ConstantFolder::visit(MemberAccess &memacc)
677 TraversingVisitor::visit(memacc);
681 void ConstantFolder::visit(Swizzle &swizzle)
683 TraversingVisitor::visit(swizzle);
687 void ConstantFolder::visit(UnaryExpression &unary)
689 TraversingVisitor::visit(unary);
690 bool can_fold = r_constant;
695 char oper = unary.oper->token[0];
696 char oper2 = unary.oper->token[1];
699 if(r_constant_value.check_type<bool>())
700 set_result(!r_constant_value.value<bool>());
704 if(r_constant_value.check_type<int>())
705 set_result(~r_constant_value.value<int>());
706 else if(r_constant_value.check_type<unsigned>())
707 set_result(~r_constant_value.value<unsigned>());
709 else if(oper=='-' && !oper2)
711 if(r_constant_value.check_type<int>())
712 set_result(-r_constant_value.value<int>());
713 else if(r_constant_value.check_type<unsigned>())
714 set_result(-r_constant_value.value<unsigned>());
715 else if(r_constant_value.check_type<float>())
716 set_result(-r_constant_value.value<float>());
720 void ConstantFolder::visit(BinaryExpression &binary)
723 bool left_constant = r_constant;
724 bool left_iter_var = r_uses_iter_var;
725 Variant left_value = r_constant_value;
728 r_uses_iter_var = true;
730 bool can_fold = (left_constant && r_constant);
735 // Currently only expressions with both sides of equal types are handled.
736 if(!left_value.check_same_type(r_constant_value))
739 char oper = binary.oper->token[0];
740 char oper2 = binary.oper->token[1];
741 if(oper=='&' || oper=='|' || oper=='^')
743 if(oper2==oper && left_value.check_type<bool>())
744 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
745 else if(!oper2 && left_value.check_type<int>())
746 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
748 else if((oper=='<' || oper=='>') && oper2!=oper)
750 if(left_value.check_type<int>())
751 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
752 else if(left_value.check_type<float>())
753 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
755 else if((oper=='=' || oper=='!') && oper2=='=')
757 if(left_value.check_type<int>())
758 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
759 if(left_value.check_type<float>())
760 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
762 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
764 if(left_value.check_type<int>())
765 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
766 else if(left_value.check_type<float>())
767 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
769 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
771 if(left_value.check_type<int>())
772 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
776 void ConstantFolder::visit(Assignment &assign)
778 TraversingVisitor::visit(assign);
782 void ConstantFolder::visit(TernaryExpression &ternary)
784 TraversingVisitor::visit(ternary);
788 void ConstantFolder::visit(FunctionCall &call)
790 if(call.constructor && call.type && call.arguments.size()==1)
792 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
795 call.arguments[0]->visit(*this);
796 bool can_fold = r_constant;
801 if(basic->kind==BasicTypeDeclaration::BOOL)
802 convert_to_result<bool>(r_constant_value);
803 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32)
804 convert_to_result<int>(r_constant_value);
805 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
806 convert_to_result<float>(r_constant_value);
812 TraversingVisitor::visit(call);
816 void ConstantFolder::visit(VariableDeclaration &var)
818 if(iteration_init && var.init_expression)
820 visit(var.init_expression);
823 /* Record the value of a constant initialization expression of an
824 iteration, so it can be used to evaluate the loop condition. */
825 iteration_var = &var;
826 iter_init_value = r_constant_value;
830 TraversingVisitor::visit(var);
833 void ConstantFolder::visit(Iteration &iter)
835 SetForScope<Block *> set_block(current_block, &iter.body);
837 /* The iteration variable is not normally inlined into expressions, so we
838 process it specially here. If the initial value causes the loop condition
839 to evaluate to false, then the expression can be folded. */
841 if(iter.init_statement)
843 SetFlag set_init(iteration_init);
844 iter.init_statement->visit(*this);
849 visit(iter.condition);
850 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
852 RefPtr<Literal> literal = new Literal;
853 literal->token = "false";
854 literal->value = r_constant_value;
855 iter.condition = literal;
860 iter.body.visit(*this);
861 if(iter.loop_expression)
862 visit(iter.loop_expression);
866 void ConstantConditionEliminator::apply(Stage &stage)
868 stage.content.visit(*this);
869 NodeRemover().apply(stage, nodes_to_remove);
872 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
874 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
875 if(literal->value.check_type<bool>())
876 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
880 void ConstantConditionEliminator::visit(Block &block)
882 SetForScope<Block *> set_block(current_block, &block);
883 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
890 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
892 r_ternary_result = 0;
895 expr = r_ternary_result;
896 r_ternary_result = 0;
899 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
901 ConstantStatus result = check_constant_condition(*ternary.condition);
902 if(result!=NOT_CONSTANT)
903 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
905 r_ternary_result = 0;
908 void ConstantConditionEliminator::visit(Conditional &cond)
910 ConstantStatus result = check_constant_condition(*cond.condition);
911 if(result!=NOT_CONSTANT)
913 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
914 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
915 current_block->body.splice(insert_point, block.body);
916 nodes_to_remove.insert(&cond);
920 TraversingVisitor::visit(cond);
923 void ConstantConditionEliminator::visit(Iteration &iter)
927 ConstantStatus result = check_constant_condition(*iter.condition);
928 if(result==CONSTANT_FALSE)
930 nodes_to_remove.insert(&iter);
935 TraversingVisitor::visit(iter);
939 UnreachableCodeRemover::UnreachableCodeRemover():
943 bool UnreachableCodeRemover::apply(Stage &stage)
945 stage.content.visit(*this);
946 NodeRemover().apply(stage, unreachable_nodes);
947 return !unreachable_nodes.empty();
950 void UnreachableCodeRemover::visit(Block &block)
952 NodeList<Statement>::iterator i = block.body.begin();
953 for(; (reachable && i!=block.body.end()); ++i)
955 for(; i!=block.body.end(); ++i)
956 unreachable_nodes.insert(i->get());
959 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
961 TraversingVisitor::visit(func);
965 void UnreachableCodeRemover::visit(Conditional &cond)
967 cond.body.visit(*this);
968 bool reachable_if_true = reachable;
970 cond.else_body.visit(*this);
972 reachable |= reachable_if_true;
975 void UnreachableCodeRemover::visit(Iteration &iter)
977 TraversingVisitor::visit(iter);
979 /* Always consider code after a loop reachable, since there's no checking
980 for whether the loop executes. */
985 bool UnusedTypeRemover::apply(Stage &stage)
987 stage.content.visit(*this);
988 NodeRemover().apply(stage, unused_nodes);
989 return !unused_nodes.empty();
992 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
994 unused_nodes.erase(expr->type);
995 TraversingVisitor::visit(expr);
998 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1001 unused_nodes.erase(type.base_type);
1002 unused_nodes.insert(&type);
1005 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1008 unused_nodes.erase(type.base_type);
1009 unused_nodes.insert(&type);
1012 void UnusedTypeRemover::visit(StructDeclaration &strct)
1014 unused_nodes.insert(&strct);
1015 TraversingVisitor::visit(strct);
1018 void UnusedTypeRemover::visit(VariableDeclaration &var)
1020 unused_nodes.erase(var.type_declaration);
1021 TraversingVisitor::visit(var);
1024 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1026 unused_nodes.erase(iface.type_declaration);
1029 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1031 unused_nodes.erase(func.return_type_declaration);
1032 TraversingVisitor::visit(func);
1036 UnusedVariableRemover::UnusedVariableRemover():
1040 assignment_target(false),
1041 r_side_effects(false),
1043 composite_reference(false)
1046 bool UnusedVariableRemover::apply(Stage &s)
1049 s.content.visit(*this);
1051 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1052 if(i->used_by.empty())
1053 unused_nodes.insert(i->node);
1055 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1057 if(i->second.output)
1059 /* The last visible assignments of output variables are used by the
1060 next stage or the API. */
1061 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1062 unused_nodes.erase((*j)->node);
1065 if(!i->second.output && !i->second.referenced)
1067 // Don't remove variables from inside interface blocks.
1068 if(!i->second.interface_block)
1069 unused_nodes.insert(i->first);
1071 else if(i->second.interface_block)
1072 // Interface blocks are kept if even one member is used.
1073 unused_nodes.erase(i->second.interface_block);
1076 NodeRemover().apply(s, unused_nodes);
1078 return !unused_nodes.empty();
1081 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1083 VariableInfo &var_info = variables[target.declaration];
1084 var_info.referenced = true;
1085 if(!assignment_target)
1087 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1089 bool covered = true;
1090 for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1092 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1093 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1094 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1096 unsigned index1 = (*i)->target.chain[j]&0x3F;
1097 unsigned index2 = target.chain[j]&0x3F;
1098 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1099 covered = index1&index2;
1100 else if(type1==Assignment::Target::ARRAY && index1<4)
1101 covered = index2&(1<<index1);
1102 else if(type2==Assignment::Target::ARRAY && index2<4)
1103 covered = index1&(1<<index2);
1104 /* If it's some other combination (shouldn't happen), leave
1108 covered = ((*i)->target.chain[j]==target.chain[j]);
1111 (*i)->used_by.push_back(&node);
1116 void UnusedVariableRemover::visit(VariableReference &var)
1118 if(composite_reference)
1119 r_reference.declaration = var.declaration;
1121 referenced(var.declaration, var);
1124 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1126 if(composite_reference)
1127 r_reference.declaration = iface.declaration;
1129 referenced(iface.declaration, iface);
1132 void UnusedVariableRemover::visit_composite(Expression &expr)
1134 if(!composite_reference)
1135 r_reference = Assignment::Target();
1137 SetFlag set_composite(composite_reference);
1141 void UnusedVariableRemover::visit(MemberAccess &memacc)
1143 visit_composite(*memacc.left);
1145 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1147 if(!composite_reference && r_reference.declaration)
1148 referenced(r_reference, memacc);
1151 void UnusedVariableRemover::visit(Swizzle &swizzle)
1153 visit_composite(*swizzle.left);
1156 for(unsigned i=0; i<swizzle.count; ++i)
1157 mask |= 1<<swizzle.components[i];
1158 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1160 if(!composite_reference && r_reference.declaration)
1161 referenced(r_reference, swizzle);
1164 void UnusedVariableRemover::visit(UnaryExpression &unary)
1166 TraversingVisitor::visit(unary);
1167 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1168 r_side_effects = true;
1171 void UnusedVariableRemover::visit(BinaryExpression &binary)
1173 if(binary.oper->token[0]=='[')
1175 visit_composite(*binary.left);
1178 SetFlag clear_assignment(assignment_target, false);
1179 SetFlag clear_composite(composite_reference, false);
1180 binary.right->visit(*this);
1183 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1185 if(!composite_reference && r_reference.declaration)
1186 referenced(r_reference, binary);
1190 SetFlag clear_composite(composite_reference, false);
1191 TraversingVisitor::visit(binary);
1195 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1197 SetFlag clear_composite(composite_reference, false);
1198 TraversingVisitor::visit(ternary);
1201 void UnusedVariableRemover::visit(Assignment &assign)
1204 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1205 assign.left->visit(*this);
1207 assign.right->visit(*this);
1208 r_assignment = &assign;
1209 r_side_effects = true;
1212 void UnusedVariableRemover::visit(FunctionCall &call)
1214 SetFlag clear_composite(composite_reference, false);
1215 TraversingVisitor::visit(call);
1216 /* Treat function calls as having side effects so expression statements
1217 consisting of nothing but a function call won't be optimized away. */
1218 r_side_effects = true;
1220 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1222 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1223 if(i->second.output)
1224 referenced(i->first, call);
1228 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1230 assignments.push_back(AssignmentInfo());
1231 AssignmentInfo &assign_info = assignments.back();
1232 assign_info.node = &node;
1233 assign_info.target = target;
1235 /* An assignment to the target hides any assignments to the same target or
1237 VariableInfo &var_info = variables[target.declaration];
1238 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1240 const Assignment::Target &t = var_info.assignments[i]->target;
1242 bool subfield = (t.chain_len>=target.chain_len);
1243 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1244 subfield = (t.chain[j]==target.chain[j]);
1247 var_info.assignments.erase(var_info.assignments.begin()+i);
1252 var_info.assignments.push_back(&assign_info);
1255 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1258 r_side_effects = false;
1259 TraversingVisitor::visit(expr);
1260 if(r_assignment && r_assignment->target.declaration)
1261 record_assignment(r_assignment->target, expr);
1263 unused_nodes.insert(&expr);
1266 void UnusedVariableRemover::visit(StructDeclaration &strct)
1268 SetFlag set_struct(in_struct);
1269 TraversingVisitor::visit(strct);
1272 void UnusedVariableRemover::visit(VariableDeclaration &var)
1274 TraversingVisitor::visit(var);
1279 VariableInfo &var_info = variables[&var];
1280 var_info.interface_block = interface_block;
1282 /* Mark variables as output if they're used by the next stage or the
1285 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1287 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1289 if(var.init_expression)
1291 var_info.initialized = true;
1292 record_assignment(&var, *var.init_expression);
1296 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1298 VariableInfo &var_info = variables[&iface];
1299 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1302 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1304 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1306 BlockVariableMap::iterator j = variables.find(i->first);
1307 if(j!=variables.end())
1309 /* The merged blocks started as copies of each other so any common
1310 assignments must be in the beginning. */
1312 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1313 if(i->second.assignments[k]!=j->second.assignments[k])
1316 // Remaining assignments are unique to each block; merge them.
1317 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1318 j->second.referenced |= i->second.referenced;
1321 variables.insert(*i);
1325 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1327 if(func.body.body.empty())
1330 BlockVariableMap saved_vars = variables;
1331 // Assignments from other functions should not be visible.
1332 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1333 i->second.assignments.resize(i->second.initialized);
1334 TraversingVisitor::visit(func);
1335 swap(variables, saved_vars);
1336 merge_variables(saved_vars);
1338 /* Always treat function parameters as referenced. Removing unused
1339 parameters is not currently supported. */
1340 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1342 BlockVariableMap::iterator j = variables.find(i->get());
1343 if(j!=variables.end())
1344 j->second.referenced = true;
1348 void UnusedVariableRemover::visit(Conditional &cond)
1350 cond.condition->visit(*this);
1351 BlockVariableMap saved_vars = variables;
1352 cond.body.visit(*this);
1353 swap(saved_vars, variables);
1354 cond.else_body.visit(*this);
1356 /* Visible assignments after the conditional is the union of those visible
1357 at the end of the if and else blocks. If there was no else block, then it's
1358 the union of the if block and the state before it. */
1359 merge_variables(saved_vars);
1362 void UnusedVariableRemover::visit(Iteration &iter)
1364 BlockVariableMap saved_vars = variables;
1365 TraversingVisitor::visit(iter);
1367 /* Merge assignments from the iteration, without clearing previous state.
1368 Further analysis is needed to determine which parts of the iteration body
1369 are always executed, if any. */
1370 merge_variables(saved_vars);
1374 bool UnusedFunctionRemover::apply(Stage &stage)
1376 stage.content.visit(*this);
1377 NodeRemover().apply(stage, unused_nodes);
1378 return !unused_nodes.empty();
1381 void UnusedFunctionRemover::visit(FunctionCall &call)
1383 TraversingVisitor::visit(call);
1385 unused_nodes.erase(call.declaration);
1386 if(call.declaration && call.declaration->definition!=call.declaration)
1387 used_definitions.insert(call.declaration->definition);
1390 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1392 TraversingVisitor::visit(func);
1394 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1395 unused_nodes.insert(&func);