1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
12 ConstantSpecializer::ConstantSpecializer():
16 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
19 stage.content.visit(*this);
22 void ConstantSpecializer::visit(VariableDeclaration &var)
24 bool specializable = false;
27 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
28 for(vector<Layout::Qualifier>::iterator i=qualifiers.begin(); (!specializable && i!=qualifiers.end()); ++i)
29 if(i->name=="constant_id")
35 if(qualifiers.empty())
41 map<string, int>::const_iterator i = values->find(var.name);
44 RefPtr<Literal> literal = new Literal;
47 literal->token = (i->second ? "true" : "false");
48 literal->value = static_cast<bool>(i->second);
50 else if(var.type=="int")
52 literal->token = lexical_cast<string>(i->second);
53 literal->value = i->second;
55 var.init_expression = literal;
61 InlineableFunctionLocator::InlineableFunctionLocator():
66 void InlineableFunctionLocator::visit(FunctionCall &call)
68 FunctionDeclaration *def = call.declaration;
70 def = def->definition;
74 unsigned &count = refcounts[def];
76 /* Don't inline functions which are called more than once or are called
78 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
79 inlineable.erase(def);
82 TraversingVisitor::visit(call);
85 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
87 bool has_out_params = false;
88 for(NodeArray<VariableDeclaration>::const_iterator i=func.parameters.begin(); (!has_out_params && i!=func.parameters.end()); ++i)
89 has_out_params = ((*i)->interface=="out");
91 unsigned &count = refcounts[func.definition];
92 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
93 inlineable.insert(func.definition);
95 SetForScope<FunctionDeclaration *> set(current_function, &func);
97 TraversingVisitor::visit(func);
100 void InlineableFunctionLocator::visit(Conditional &cond)
102 TraversingVisitor::visit(cond);
103 inlineable.erase(current_function);
106 void InlineableFunctionLocator::visit(Iteration &iter)
108 TraversingVisitor::visit(iter);
109 inlineable.erase(current_function);
112 void InlineableFunctionLocator::visit(Return &ret)
114 TraversingVisitor::visit(ret);
116 inlineable.erase(current_function);
121 InlineContentInjector::InlineContentInjector():
126 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
128 source_func = call.declaration->definition;
130 /* Populate referenced_names from the target function so we can rename
131 variables from the inlined function that would conflict. */
133 target_func.visit(*this);
135 /* Inline and rename passes must be interleaved so used variable names are
136 known when inlining the return statement. */
138 staging_block.parent = &tgt_blk;
139 staging_block.variables.clear();
141 vector<RefPtr<VariableDeclaration> > params;
142 params.reserve(source_func->parameters.size());
143 for(NodeArray<VariableDeclaration>::iterator i=source_func->parameters.begin(); i!=source_func->parameters.end(); ++i)
145 RefPtr<VariableDeclaration> var = (*i)->clone();
146 var->interface.clear();
148 SetForScope<Pass> set_pass(pass, RENAME);
151 staging_block.body.push_back_nocopy(var);
152 params.push_back(var);
155 for(NodeList<Statement>::iterator i=source_func->body.body.begin(); i!=source_func->body.body.end(); ++i)
157 r_inlined_statement = 0;
159 if(!r_inlined_statement)
160 r_inlined_statement = (*i)->clone();
162 SetForScope<Pass> set_pass(pass, RENAME);
163 r_inlined_statement->visit(*this);
165 staging_block.body.push_back_nocopy(r_inlined_statement);
168 /* Now collect names from the staging block. Local variables that would
169 have conflicted with the target function were renamed earlier. */
171 referenced_names.clear();
172 staging_block.variables.clear();
173 staging_block.visit(*this);
175 /* Rename variables in the target function so they don't interfere with
176 global identifiers used by the source function. */
178 staging_block.parent = source_func->body.parent;
179 target_func.visit(*this);
181 // Put the argument expressions in place after all renaming has been done.
182 for(unsigned i=0; i<source_func->parameters.size(); ++i)
183 params[i]->init_expression = call.arguments[i]->clone();
185 tgt_blk.body.splice(ins_pt, staging_block.body);
187 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
189 return r_result_name;
192 void InlineContentInjector::visit(VariableReference &var)
196 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
197 if(i!=staging_block.variables.end())
198 var.name = i->second->name;
200 else if(pass==REFERENCED)
201 referenced_names.insert(var.name);
204 void InlineContentInjector::visit(InterfaceBlockReference &iface)
207 referenced_names.insert(iface.name);
210 void InlineContentInjector::visit(FunctionCall &call)
213 referenced_names.insert(call.name);
214 TraversingVisitor::visit(call);
217 void InlineContentInjector::visit(VariableDeclaration &var)
219 TraversingVisitor::visit(var);
223 /* Check against conflicts with the other context as well as variables
224 already renamed here. */
225 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
226 staging_block.variables[var.name] = &var;
229 string mapped_name = get_unused_variable_name(staging_block, var.name);
230 if(mapped_name!=var.name)
232 staging_block.variables[mapped_name] = &var;
233 var.name = mapped_name;
237 else if(pass==REFERENCED)
238 referenced_names.insert(var.type);
241 void InlineContentInjector::visit(Return &ret)
243 TraversingVisitor::visit(ret);
245 if(pass==INLINE && ret.expression)
247 // Create a new variable to hold the return value of the inlined function.
248 r_result_name = get_unused_variable_name(staging_block, "_return");
249 RefPtr<VariableDeclaration> var = new VariableDeclaration;
250 var->source = ret.source;
251 var->line = ret.line;
252 var->type = source_func->return_type;
253 var->name = r_result_name;
254 var->init_expression = ret.expression->clone();
255 r_inlined_statement = var;
260 FunctionInliner::FunctionInliner():
262 r_any_inlined(false),
263 r_inlined_here(false)
266 bool FunctionInliner::apply(Stage &s)
269 inlineable = InlineableFunctionLocator().apply(s);
270 r_any_inlined = false;
271 s.content.visit(*this);
272 return r_any_inlined;
275 void FunctionInliner::visit(RefPtr<Expression> &ptr)
281 ptr = r_inline_result;
282 r_any_inlined = true;
287 void FunctionInliner::visit(Block &block)
289 SetForScope<Block *> set_block(current_block, &block);
290 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
291 for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
298 void FunctionInliner::visit(FunctionCall &call)
300 for(NodeArray<Expression>::iterator i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
306 FunctionDeclaration *def = call.declaration;
308 def = def->definition;
310 if(def && inlineable.count(def))
312 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
314 // This will later get removed by UnusedVariableRemover.
315 if(result_name.empty())
316 result_name = "_msp_unused_from_inline";
318 RefPtr<VariableReference> ref = new VariableReference;
319 ref->name = result_name;
320 r_inline_result = ref;
322 /* Inlined variables need to be resolved before this function can be
324 inlineable.erase(current_function);
325 r_inlined_here = true;
329 void FunctionInliner::visit(FunctionDeclaration &func)
331 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
332 TraversingVisitor::visit(func);
333 r_inlined_here = false;
336 void FunctionInliner::visit(Iteration &iter)
338 /* Visit the initialization statement before entering the loop body so the
339 inlined statements get inserted outside. */
340 if(iter.init_statement)
341 iter.init_statement->visit(*this);
343 SetForScope<Block *> set_block(current_block, &iter.body);
344 /* Skip the condition and loop expression parts because they're not properly
345 inside the body block. Inlining anything into them will require a more
346 comprehensive transformation. */
347 iter.body.visit(*this);
351 ExpressionInliner::ExpressionInliner():
353 r_any_inlined(false),
356 iteration_init(false),
361 bool ExpressionInliner::apply(Stage &s)
363 s.content.visit(*this);
364 return r_any_inlined;
367 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
370 r_any_inlined = true;
373 void ExpressionInliner::visit(Block &block)
375 TraversingVisitor::visit(block);
377 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
379 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
380 for(; (j!=expressions.end() && j->first.declaration==i->second); )
382 if(j->second.expression && j->second.inline_point)
383 inline_expression(*j->second.expression, *j->second.inline_point);
385 expressions.erase(j++);
389 /* Expressions assigned in this block may depend on local variables of the
390 block. If this is a conditionally executed block, the assignments might not
391 always happen. Mark the expressions as not available to any outer blocks. */
392 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
393 if(i->second.assign_scope==&block)
394 i->second.available = false;
397 void ExpressionInliner::visit(RefPtr<Expression> &expr)
401 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
403 if(iteration_body && !r_ref_info->trivial)
405 /* Don't inline non-trivial expressions which were assigned outside
406 an iteration statement. The iteration may run multiple times, which
407 would cause the expression to also be evaluated multiple times. */
408 Block *i = r_ref_info->assign_scope;
409 for(; (i && i!=iteration_body); i=i->parent) ;
414 if(r_ref_info->trivial)
415 inline_expression(*r_ref_info->expression, expr);
417 /* Record the inline point for a non-trivial expression but don't
418 inline it yet. It might turn out it shouldn't be inlined after all. */
419 r_ref_info->inline_point = &expr;
425 void ExpressionInliner::visit(VariableReference &var)
429 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
430 if(i!=expressions.end())
432 /* If a non-trivial expression is referenced multiple times, don't
434 if(i->second.inline_point && !i->second.trivial)
435 i->second.expression = 0;
436 /* Mutating expressions are analogous to self-referencing assignments
437 and prevent inlining. */
439 i->second.expression = 0;
440 r_ref_info = &i->second;
445 void ExpressionInliner::visit(MemberAccess &memacc)
451 void ExpressionInliner::visit(Swizzle &swizzle)
457 void ExpressionInliner::visit(UnaryExpression &unary)
459 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
460 visit(unary.expression);
464 void ExpressionInliner::visit(BinaryExpression &binary)
468 SetFlag clear_target(mutating, false);
474 void ExpressionInliner::visit(Assignment &assign)
477 SetFlag set_target(mutating);
483 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
484 if(i!=expressions.end())
486 /* Self-referencing assignments can't be inlined without additional
487 work. Just clear any previous expression. */
488 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
489 i->second.assign_scope = current_block;
490 i->second.inline_point = 0;
491 i->second.available = true;
497 void ExpressionInliner::visit(TernaryExpression &ternary)
499 visit(ternary.condition);
500 visit(ternary.true_expr);
501 visit(ternary.false_expr);
505 void ExpressionInliner::visit(FunctionCall &call)
507 TraversingVisitor::visit(call);
511 void ExpressionInliner::visit(VariableDeclaration &var)
515 TraversingVisitor::visit(var);
517 bool constant = var.constant;
518 if(constant && var.layout)
520 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
521 constant = (i->name!="constant_id");
524 /* Only inline global variables if they're constant and have trivial
525 initializers. Non-constant variables could change in ways which are hard to
526 analyze and non-trivial expressions could be expensive to inline. */
527 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
529 ExpressionInfo &info = expressions[&var];
530 /* Assume variables declared in an iteration initialization statement
531 will have their values change throughout the iteration. */
532 info.expression = (iteration_init ? 0 : var.init_expression.get());
533 info.assign_scope = current_block;
534 info.trivial = r_trivial;
538 void ExpressionInliner::visit(Iteration &iter)
540 SetForScope<Block *> set_block(current_block, &iter.body);
541 if(iter.init_statement)
543 SetFlag set_init(iteration_init);
544 iter.init_statement->visit(*this);
547 SetForScope<Block *> set_body(iteration_body, &iter.body);
549 visit(iter.condition);
550 iter.body.visit(*this);
551 if(iter.loop_expression)
552 visit(iter.loop_expression);
556 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
558 if(value.check_type<bool>())
559 return BasicTypeDeclaration::BOOL;
560 else if(value.check_type<int>())
561 return BasicTypeDeclaration::INT;
562 else if(value.check_type<float>())
563 return BasicTypeDeclaration::FLOAT;
565 return BasicTypeDeclaration::VOID;
569 T ConstantFolder::evaluate_logical(char oper, T left, T right)
573 case '&': return left&right;
574 case '|': return left|right;
575 case '^': return left^right;
581 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
583 switch(oper[0]|oper[1])
585 case '<': return left<right;
586 case '<'|'=': return left<=right;
587 case '>': return left>right;
588 case '>'|'=': return left>=right;
589 default: return false;
594 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
598 case '+': return left+right;
599 case '-': return left-right;
600 case '*': return left*right;
601 case '/': return left/right;
606 void ConstantFolder::set_result(const Variant &value, bool literal)
608 r_constant_value = value;
613 void ConstantFolder::visit(RefPtr<Expression> &expr)
615 r_constant_value = Variant();
618 r_uses_iter_var = false;
620 /* Don't replace literals since they'd only be replaced with an identical
621 literal. Also skip anything that uses an iteration variable, but pass on
622 the result so the Iteration visiting function can handle it. */
623 if(!r_constant || r_literal || r_uses_iter_var)
626 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
627 if(kind==BasicTypeDeclaration::VOID)
633 RefPtr<Literal> literal = new Literal;
634 if(kind==BasicTypeDeclaration::BOOL)
635 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
636 else if(kind==BasicTypeDeclaration::INT)
637 literal->token = lexical_cast<string>(r_constant_value.value<int>());
638 else if(kind==BasicTypeDeclaration::FLOAT)
639 literal->token = lexical_cast<string>(r_constant_value.value<float>());
640 literal->value = r_constant_value;
644 void ConstantFolder::visit(Literal &literal)
646 set_result(literal.value, true);
649 void ConstantFolder::visit(VariableReference &var)
651 /* If an iteration variable is initialized with a constant value, return
652 that value here for the purpose of evaluating the loop condition for the
654 if(var.declaration==iteration_var)
656 set_result(iter_init_value);
657 r_uses_iter_var = true;
661 void ConstantFolder::visit(MemberAccess &memacc)
663 TraversingVisitor::visit(memacc);
667 void ConstantFolder::visit(Swizzle &swizzle)
669 TraversingVisitor::visit(swizzle);
673 void ConstantFolder::visit(UnaryExpression &unary)
675 TraversingVisitor::visit(unary);
676 bool can_fold = r_constant;
681 BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
683 char oper = unary.oper->token[0];
684 char oper2 = unary.oper->token[1];
687 if(kind==BasicTypeDeclaration::BOOL)
688 set_result(!r_constant_value.value<bool>());
692 if(kind==BasicTypeDeclaration::INT)
693 set_result(~r_constant_value.value<int>());
695 else if(oper=='-' && !oper2)
697 if(kind==BasicTypeDeclaration::INT)
698 set_result(-r_constant_value.value<int>());
699 else if(kind==BasicTypeDeclaration::FLOAT)
700 set_result(-r_constant_value.value<float>());
704 void ConstantFolder::visit(BinaryExpression &binary)
707 bool left_constant = r_constant;
708 bool left_iter_var = r_uses_iter_var;
709 Variant left_value = r_constant_value;
712 r_uses_iter_var = true;
714 bool can_fold = (left_constant && r_constant);
719 BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
720 BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
721 // Currently only expressions with both sides of equal types are handled.
722 if(left_kind!=right_kind)
725 char oper = binary.oper->token[0];
726 char oper2 = binary.oper->token[1];
727 if(oper=='&' || oper=='|' || oper=='^')
729 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
730 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
731 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
732 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
734 else if((oper=='<' || oper=='>') && oper2!=oper)
736 if(left_kind==BasicTypeDeclaration::INT)
737 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
738 else if(left_kind==BasicTypeDeclaration::FLOAT)
739 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
741 else if((oper=='=' || oper=='!') && oper2=='=')
743 if(left_kind==BasicTypeDeclaration::INT)
744 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
745 if(left_kind==BasicTypeDeclaration::FLOAT)
746 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
748 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
750 if(left_kind==BasicTypeDeclaration::INT)
751 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
752 else if(left_kind==BasicTypeDeclaration::FLOAT)
753 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
755 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
757 if(left_kind!=BasicTypeDeclaration::INT)
761 set_result(left_value.value<int>()%r_constant_value.value<int>());
763 set_result(left_value.value<int>()<<r_constant_value.value<int>());
765 set_result(left_value.value<int>()>>r_constant_value.value<int>());
769 void ConstantFolder::visit(Assignment &assign)
771 TraversingVisitor::visit(assign);
775 void ConstantFolder::visit(TernaryExpression &ternary)
777 TraversingVisitor::visit(ternary);
781 void ConstantFolder::visit(FunctionCall &call)
783 TraversingVisitor::visit(call);
787 void ConstantFolder::visit(VariableDeclaration &var)
789 if(iteration_init && var.init_expression)
791 visit(var.init_expression);
794 /* Record the value of a constant initialization expression of an
795 iteration, so it can be used to evaluate the loop condition. */
796 iteration_var = &var;
797 iter_init_value = r_constant_value;
801 TraversingVisitor::visit(var);
804 void ConstantFolder::visit(Iteration &iter)
806 SetForScope<Block *> set_block(current_block, &iter.body);
808 /* The iteration variable is not normally inlined into expressions, so we
809 process it specially here. If the initial value causes the loop condition
810 to evaluate to false, then the expression can be folded. */
812 if(iter.init_statement)
814 SetFlag set_init(iteration_init);
815 iter.init_statement->visit(*this);
820 visit(iter.condition);
821 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
823 RefPtr<Literal> literal = new Literal;
824 literal->token = "false";
825 literal->value = r_constant_value;
826 iter.condition = literal;
831 iter.body.visit(*this);
832 if(iter.loop_expression)
833 visit(iter.loop_expression);
837 void ConstantConditionEliminator::apply(Stage &stage)
839 stage.content.visit(*this);
840 NodeRemover().apply(stage, nodes_to_remove);
843 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
845 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
846 if(literal->value.check_type<bool>())
847 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
851 void ConstantConditionEliminator::visit(Block &block)
853 SetForScope<Block *> set_block(current_block, &block);
854 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
861 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
863 r_ternary_result = 0;
866 expr = r_ternary_result;
867 r_ternary_result = 0;
870 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
872 ConstantStatus result = check_constant_condition(*ternary.condition);
873 if(result!=NOT_CONSTANT)
874 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
876 r_ternary_result = 0;
879 void ConstantConditionEliminator::visit(Conditional &cond)
881 ConstantStatus result = check_constant_condition(*cond.condition);
882 if(result!=NOT_CONSTANT)
884 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
885 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
886 current_block->body.splice(insert_point, block.body);
887 nodes_to_remove.insert(&cond);
891 TraversingVisitor::visit(cond);
894 void ConstantConditionEliminator::visit(Iteration &iter)
898 ConstantStatus result = check_constant_condition(*iter.condition);
899 if(result==CONSTANT_FALSE)
901 nodes_to_remove.insert(&iter);
906 TraversingVisitor::visit(iter);
910 UnreachableCodeRemover::UnreachableCodeRemover():
914 bool UnreachableCodeRemover::apply(Stage &stage)
916 stage.content.visit(*this);
917 NodeRemover().apply(stage, unreachable_nodes);
918 return !unreachable_nodes.empty();
921 void UnreachableCodeRemover::visit(Block &block)
923 NodeList<Statement>::iterator i = block.body.begin();
924 for(; (reachable && i!=block.body.end()); ++i)
926 for(; i!=block.body.end(); ++i)
927 unreachable_nodes.insert(i->get());
930 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
932 TraversingVisitor::visit(func);
936 void UnreachableCodeRemover::visit(Conditional &cond)
938 cond.body.visit(*this);
939 bool reachable_if_true = reachable;
941 cond.else_body.visit(*this);
943 reachable |= reachable_if_true;
946 void UnreachableCodeRemover::visit(Iteration &iter)
948 TraversingVisitor::visit(iter);
950 /* Always consider code after a loop reachable, since there's no checking
951 for whether the loop executes. */
956 bool UnusedTypeRemover::apply(Stage &stage)
958 stage.content.visit(*this);
959 NodeRemover().apply(stage, unused_nodes);
960 return !unused_nodes.empty();
963 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
965 unused_nodes.erase(expr->type);
966 TraversingVisitor::visit(expr);
969 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
972 unused_nodes.erase(type.base_type);
973 unused_nodes.insert(&type);
976 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
979 unused_nodes.erase(type.base_type);
980 unused_nodes.insert(&type);
983 void UnusedTypeRemover::visit(StructDeclaration &strct)
985 unused_nodes.insert(&strct);
986 TraversingVisitor::visit(strct);
989 void UnusedTypeRemover::visit(VariableDeclaration &var)
991 unused_nodes.erase(var.type_declaration);
992 TraversingVisitor::visit(var);
995 void UnusedTypeRemover::visit(InterfaceBlock &iface)
997 unused_nodes.erase(iface.type_declaration);
1000 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1002 unused_nodes.erase(func.return_type_declaration);
1003 TraversingVisitor::visit(func);
1007 UnusedVariableRemover::UnusedVariableRemover():
1011 assignment_target(false),
1012 r_side_effects(false),
1014 composite_reference(false)
1017 bool UnusedVariableRemover::apply(Stage &s)
1020 s.content.visit(*this);
1022 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1023 if(i->used_by.empty())
1024 unused_nodes.insert(i->node);
1026 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1028 if(i->second.output)
1030 /* The last visible assignments of output variables are used by the
1031 next stage or the API. */
1032 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1033 unused_nodes.erase((*j)->node);
1036 if(!i->second.output && !i->second.referenced)
1038 // Don't remove variables from inside interface blocks.
1039 if(!i->second.interface_block)
1040 unused_nodes.insert(i->first);
1042 else if(i->second.interface_block)
1043 // Interface blocks are kept if even one member is used.
1044 unused_nodes.erase(i->second.interface_block);
1047 NodeRemover().apply(s, unused_nodes);
1049 return !unused_nodes.empty();
1052 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1054 VariableInfo &var_info = variables[target.declaration];
1055 var_info.referenced = true;
1056 if(!assignment_target)
1058 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1060 bool covered = true;
1061 for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1063 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1064 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1065 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1067 unsigned index1 = (*i)->target.chain[j]&0x3F;
1068 unsigned index2 = target.chain[j]&0x3F;
1069 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1070 covered = index1&index2;
1071 else if(type1==Assignment::Target::ARRAY && index1<4)
1072 covered = index2&(1<<index1);
1073 else if(type2==Assignment::Target::ARRAY && index2<4)
1074 covered = index1&(1<<index2);
1075 /* If it's some other combination (shouldn't happen), leave
1079 covered = ((*i)->target.chain[j]==target.chain[j]);
1082 (*i)->used_by.push_back(&node);
1087 void UnusedVariableRemover::visit(VariableReference &var)
1089 if(composite_reference)
1090 r_reference.declaration = var.declaration;
1092 referenced(var.declaration, var);
1095 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1097 if(composite_reference)
1098 r_reference.declaration = iface.declaration;
1100 referenced(iface.declaration, iface);
1103 void UnusedVariableRemover::visit_composite(Expression &expr)
1105 if(!composite_reference)
1106 r_reference = Assignment::Target();
1108 SetFlag set_composite(composite_reference);
1112 void UnusedVariableRemover::visit(MemberAccess &memacc)
1114 visit_composite(*memacc.left);
1116 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1118 if(!composite_reference && r_reference.declaration)
1119 referenced(r_reference, memacc);
1122 void UnusedVariableRemover::visit(Swizzle &swizzle)
1124 visit_composite(*swizzle.left);
1127 for(unsigned i=0; i<swizzle.count; ++i)
1128 mask |= 1<<swizzle.components[i];
1129 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1131 if(!composite_reference && r_reference.declaration)
1132 referenced(r_reference, swizzle);
1135 void UnusedVariableRemover::visit(UnaryExpression &unary)
1137 TraversingVisitor::visit(unary);
1138 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1139 r_side_effects = true;
1142 void UnusedVariableRemover::visit(BinaryExpression &binary)
1144 if(binary.oper->token[0]=='[')
1146 visit_composite(*binary.left);
1149 SetFlag clear_assignment(assignment_target, false);
1150 SetFlag clear_composite(composite_reference, false);
1151 binary.right->visit(*this);
1154 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1156 if(!composite_reference && r_reference.declaration)
1157 referenced(r_reference, binary);
1161 SetFlag clear_composite(composite_reference, false);
1162 TraversingVisitor::visit(binary);
1166 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1168 SetFlag clear_composite(composite_reference, false);
1169 TraversingVisitor::visit(ternary);
1172 void UnusedVariableRemover::visit(Assignment &assign)
1175 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1176 assign.left->visit(*this);
1178 assign.right->visit(*this);
1179 r_assignment = &assign;
1180 r_side_effects = true;
1183 void UnusedVariableRemover::visit(FunctionCall &call)
1185 SetFlag clear_composite(composite_reference, false);
1186 TraversingVisitor::visit(call);
1187 /* Treat function calls as having side effects so expression statements
1188 consisting of nothing but a function call won't be optimized away. */
1189 r_side_effects = true;
1191 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1193 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1194 if(i->second.output)
1195 referenced(i->first, call);
1199 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1201 assignments.push_back(AssignmentInfo());
1202 AssignmentInfo &assign_info = assignments.back();
1203 assign_info.node = &node;
1204 assign_info.target = target;
1206 /* An assignment to the target hides any assignments to the same target or
1208 VariableInfo &var_info = variables[target.declaration];
1209 for(unsigned i=0; i<var_info.assignments.size(); ++i)
1211 const Assignment::Target &t = var_info.assignments[i]->target;
1213 bool subfield = (t.chain_len>=target.chain_len);
1214 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1215 subfield = (t.chain[j]==target.chain[j]);
1218 var_info.assignments.erase(var_info.assignments.begin()+i);
1223 var_info.assignments.push_back(&assign_info);
1226 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1229 r_side_effects = false;
1230 TraversingVisitor::visit(expr);
1231 if(r_assignment && r_assignment->target.declaration)
1232 record_assignment(r_assignment->target, expr);
1234 unused_nodes.insert(&expr);
1237 void UnusedVariableRemover::visit(StructDeclaration &strct)
1239 SetFlag set_struct(in_struct);
1240 TraversingVisitor::visit(strct);
1243 void UnusedVariableRemover::visit(VariableDeclaration &var)
1245 TraversingVisitor::visit(var);
1250 VariableInfo &var_info = variables[&var];
1251 var_info.interface_block = interface_block;
1253 /* Mark variables as output if they're used by the next stage or the
1256 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1258 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1260 if(var.init_expression)
1262 var_info.initialized = true;
1263 record_assignment(&var, *var.init_expression);
1267 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1269 VariableInfo &var_info = variables[&iface];
1270 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1273 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1275 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1277 BlockVariableMap::iterator j = variables.find(i->first);
1278 if(j!=variables.end())
1280 /* The merged blocks started as copies of each other so any common
1281 assignments must be in the beginning. */
1283 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1284 if(i->second.assignments[k]!=j->second.assignments[k])
1287 // Remaining assignments are unique to each block; merge them.
1288 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1289 j->second.referenced |= i->second.referenced;
1292 variables.insert(*i);
1296 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1298 if(func.body.body.empty())
1301 BlockVariableMap saved_vars = variables;
1302 // Assignments from other functions should not be visible.
1303 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1304 i->second.assignments.resize(i->second.initialized);
1305 TraversingVisitor::visit(func);
1306 swap(variables, saved_vars);
1307 merge_variables(saved_vars);
1309 /* Always treat function parameters as referenced. Removing unused
1310 parameters is not currently supported. */
1311 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1313 BlockVariableMap::iterator j = variables.find(i->get());
1314 if(j!=variables.end())
1315 j->second.referenced = true;
1319 void UnusedVariableRemover::visit(Conditional &cond)
1321 cond.condition->visit(*this);
1322 BlockVariableMap saved_vars = variables;
1323 cond.body.visit(*this);
1324 swap(saved_vars, variables);
1325 cond.else_body.visit(*this);
1327 /* Visible assignments after the conditional is the union of those visible
1328 at the end of the if and else blocks. If there was no else block, then it's
1329 the union of the if block and the state before it. */
1330 merge_variables(saved_vars);
1333 void UnusedVariableRemover::visit(Iteration &iter)
1335 BlockVariableMap saved_vars = variables;
1336 TraversingVisitor::visit(iter);
1338 /* Merge assignments from the iteration, without clearing previous state.
1339 Further analysis is needed to determine which parts of the iteration body
1340 are always executed, if any. */
1341 merge_variables(saved_vars);
1345 bool UnusedFunctionRemover::apply(Stage &stage)
1347 stage.content.visit(*this);
1348 NodeRemover().apply(stage, unused_nodes);
1349 return !unused_nodes.empty();
1352 void UnusedFunctionRemover::visit(FunctionCall &call)
1354 TraversingVisitor::visit(call);
1356 unused_nodes.erase(call.declaration);
1357 if(call.declaration && call.declaration->definition!=call.declaration)
1358 used_definitions.insert(call.declaration->definition);
1361 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1363 TraversingVisitor::visit(func);
1365 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1366 unused_nodes.insert(&func);