1 #include <msp/core/algorithm.h>
2 #include <msp/core/raii.h>
3 #include <msp/strings/format.h>
4 #include <msp/strings/utils.h>
14 ConstantSpecializer::ConstantSpecializer():
18 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
21 stage.content.visit(*this);
24 void ConstantSpecializer::visit(VariableDeclaration &var)
26 bool specializable = false;
29 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
30 auto i = find_member(qualifiers, string("constant_id"), &Layout::Qualifier::name);
31 if(i!=qualifiers.end())
35 if(qualifiers.empty())
42 auto 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 = any_of(func.parameters.begin(), func.parameters.end(),
89 [](const RefPtr<VariableDeclaration> &p){ return p->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(const RefPtr<VariableDeclaration> &p: source_func->parameters)
145 RefPtr<VariableDeclaration> var = p->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(const RefPtr<Statement> &s: source_func->body.body)
157 r_inlined_statement = 0;
159 if(!r_inlined_statement)
160 r_inlined_statement = s->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 auto 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(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
298 void FunctionInliner::visit(FunctionCall &call)
300 for(auto 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():
356 iteration_init(false),
361 bool ExpressionInliner::apply(Stage &s)
363 s.content.visit(*this);
365 bool any_inlined = false;
366 for(ExpressionInfo &e: expressions)
367 if(e.expression && (e.trivial || e.uses.size()==1))
369 for(ExpressionUse &u: e.uses)
372 *u.reference = e.expression->clone();
380 void ExpressionInliner::visit(RefPtr<Expression> &expr)
384 if(r_ref_info && r_ref_info->expression)
387 use.reference = &expr;
388 use.ref_scope = current_block;
389 use.blocked = access_write;
391 if(iteration_body && !r_ref_info->trivial)
393 /* Block inlining of non-trivial expressions assigned outside an
394 iteration statement. The iteration may run multiple times, which
395 would cause the expression to also be evaluated multiple times. */
396 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
397 use.blocked = (i==r_ref_info->assign_scope);
400 /* Block inlining assignments from from inner scopes. The assignment may
401 depend on local variables of that scope or may not always be executed. */
402 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
403 use.blocked = (i==current_block);
405 r_ref_info->uses.push_back(use);
411 void ExpressionInliner::visit(VariableReference &var)
413 if(var.declaration && access_read)
415 auto i = assignments.find(var.declaration);
416 if(i!=assignments.end())
417 r_ref_info = i->second;
421 void ExpressionInliner::visit(MemberAccess &memacc)
427 void ExpressionInliner::visit(Swizzle &swizzle)
433 void ExpressionInliner::visit(UnaryExpression &unary)
435 SetFlag set_write(access_write, access_write || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
436 visit(unary.expression);
440 void ExpressionInliner::visit(BinaryExpression &binary)
444 SetFlag clear_write(access_write, false);
450 void ExpressionInliner::visit(Assignment &assign)
453 SetFlag set_read(access_read, assign.oper->token[0]!='=');
454 SetFlag set_write(access_write);
461 auto i = assignments.find(assign.target);
462 if(i!=assignments.end())
464 if(iteration_body && i->second->expression)
466 /* Block inlining into previous references within the iteration
467 statement. On iterations after the first they would refer to the
468 assignment within the iteration. */
469 for(ExpressionUse &u: i->second->uses)
470 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
471 u.blocked = (k==iteration_body);
474 expressions.push_back(ExpressionInfo());
475 ExpressionInfo &info = expressions.back();
476 info.target = assign.target;
477 // Self-referencing assignments can't be inlined without additional work.
478 if(!assign.self_referencing)
479 info.expression = assign.right;
480 info.assign_scope = current_block;
481 info.trivial = r_trivial;
489 void ExpressionInliner::visit(TernaryExpression &ternary)
491 visit(ternary.condition);
492 visit(ternary.true_expr);
493 visit(ternary.false_expr);
497 void ExpressionInliner::visit(FunctionCall &call)
499 TraversingVisitor::visit(call);
503 void ExpressionInliner::visit(VariableDeclaration &var)
507 TraversingVisitor::visit(var);
509 bool constant = var.constant;
510 if(constant && var.layout)
512 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
513 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
516 /* Only inline global variables if they're constant and have trivial
517 initializers. Non-constant variables could change in ways which are hard to
518 analyze and non-trivial expressions could be expensive to inline. */
519 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
521 expressions.push_back(ExpressionInfo());
522 ExpressionInfo &info = expressions.back();
524 /* Assume variables declared in an iteration initialization statement
525 will have their values change throughout the iteration. */
527 info.expression = var.init_expression;
528 info.assign_scope = current_block;
529 info.trivial = r_trivial;
531 assignments[&var] = &info;
535 void ExpressionInliner::visit(Iteration &iter)
537 SetForScope<Block *> set_block(current_block, &iter.body);
538 if(iter.init_statement)
540 SetFlag set_init(iteration_init);
541 iter.init_statement->visit(*this);
544 SetForScope<Block *> set_body(iteration_body, &iter.body);
546 visit(iter.condition);
547 iter.body.visit(*this);
548 if(iter.loop_expression)
549 visit(iter.loop_expression);
554 T ConstantFolder::evaluate_logical(char oper, T left, T right)
558 case '&': return left&right;
559 case '|': return left|right;
560 case '^': return left^right;
566 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
568 switch(oper[0]|oper[1])
570 case '<': return left<right;
571 case '<'|'=': return left<=right;
572 case '>': return left>right;
573 case '>'|'=': return left>=right;
574 default: return false;
579 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
583 case '+': return left+right;
584 case '-': return left-right;
585 case '*': return left*right;
586 case '/': return left/right;
592 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
596 case '%': return left%right;
597 case '<': return left<<right;
598 case '>': return left>>right;
604 void ConstantFolder::convert_to_result(const Variant &value)
606 if(value.check_type<bool>())
607 set_result(static_cast<T>(value.value<bool>()));
608 else if(value.check_type<int>())
609 set_result(static_cast<T>(value.value<int>()));
610 else if(value.check_type<unsigned>())
611 set_result(static_cast<T>(value.value<unsigned>()));
612 else if(value.check_type<float>())
613 set_result(static_cast<T>(value.value<float>()));
616 void ConstantFolder::set_result(const Variant &value, bool literal)
618 r_constant_value = value;
623 void ConstantFolder::visit(RefPtr<Expression> &expr)
625 r_constant_value = Variant();
628 r_uses_iter_var = false;
630 /* Don't replace literals since they'd only be replaced with an identical
631 literal. Also skip anything that uses an iteration variable, but pass on
632 the result so the Iteration visiting function can handle it. */
633 if(!r_constant || r_literal || r_uses_iter_var)
636 RefPtr<Literal> literal = new Literal;
637 if(r_constant_value.check_type<bool>())
638 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
639 else if(r_constant_value.check_type<int>())
640 literal->token = lexical_cast<string>(r_constant_value.value<int>());
641 else if(r_constant_value.check_type<unsigned>())
642 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
643 else if(r_constant_value.check_type<float>())
645 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
646 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
647 literal->token += ".0";
654 literal->value = r_constant_value;
659 void ConstantFolder::visit(Literal &literal)
661 set_result(literal.value, true);
664 void ConstantFolder::visit(VariableReference &var)
666 /* If an iteration variable is initialized with a constant value, return
667 that value here for the purpose of evaluating the loop condition for the
669 if(var.declaration==iteration_var)
671 set_result(iter_init_value);
672 r_uses_iter_var = true;
676 void ConstantFolder::visit(MemberAccess &memacc)
678 TraversingVisitor::visit(memacc);
682 void ConstantFolder::visit(Swizzle &swizzle)
684 TraversingVisitor::visit(swizzle);
688 void ConstantFolder::visit(UnaryExpression &unary)
690 TraversingVisitor::visit(unary);
691 bool can_fold = r_constant;
696 char oper = unary.oper->token[0];
697 char oper2 = unary.oper->token[1];
700 if(r_constant_value.check_type<bool>())
701 set_result(!r_constant_value.value<bool>());
705 if(r_constant_value.check_type<int>())
706 set_result(~r_constant_value.value<int>());
707 else if(r_constant_value.check_type<unsigned>())
708 set_result(~r_constant_value.value<unsigned>());
710 else if(oper=='-' && !oper2)
712 if(r_constant_value.check_type<int>())
713 set_result(-r_constant_value.value<int>());
714 else if(r_constant_value.check_type<unsigned>())
715 set_result(-r_constant_value.value<unsigned>());
716 else if(r_constant_value.check_type<float>())
717 set_result(-r_constant_value.value<float>());
721 void ConstantFolder::visit(BinaryExpression &binary)
724 bool left_constant = r_constant;
725 bool left_iter_var = r_uses_iter_var;
726 Variant left_value = r_constant_value;
729 r_uses_iter_var = true;
731 bool can_fold = (left_constant && r_constant);
736 // Currently only expressions with both sides of equal types are handled.
737 if(!left_value.check_same_type(r_constant_value))
740 char oper = binary.oper->token[0];
741 char oper2 = binary.oper->token[1];
742 if(oper=='&' || oper=='|' || oper=='^')
744 if(oper2==oper && left_value.check_type<bool>())
745 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
746 else if(!oper2 && left_value.check_type<int>())
747 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
748 else if(!oper2 && left_value.check_type<unsigned>())
749 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
751 else if((oper=='<' || oper=='>') && oper2!=oper)
753 if(left_value.check_type<int>())
754 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
755 else if(left_value.check_type<unsigned>())
756 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
757 else if(left_value.check_type<float>())
758 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
760 else if((oper=='=' || oper=='!') && oper2=='=')
762 if(left_value.check_type<int>())
763 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
764 else if(left_value.check_type<unsigned>())
765 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
766 else if(left_value.check_type<float>())
767 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
769 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
771 if(left_value.check_type<int>())
772 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
773 else if(left_value.check_type<unsigned>())
774 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
775 else if(left_value.check_type<float>())
776 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
778 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
780 if(left_value.check_type<int>())
781 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
782 else if(left_value.check_type<unsigned>())
783 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
787 void ConstantFolder::visit(Assignment &assign)
789 TraversingVisitor::visit(assign);
793 void ConstantFolder::visit(TernaryExpression &ternary)
795 TraversingVisitor::visit(ternary);
799 void ConstantFolder::visit(FunctionCall &call)
801 if(call.constructor && call.type && call.arguments.size()==1)
803 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
806 visit(call.arguments[0]);
807 bool can_fold = r_constant;
812 if(basic->kind==BasicTypeDeclaration::BOOL)
813 convert_to_result<bool>(r_constant_value);
814 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
815 convert_to_result<int>(r_constant_value);
816 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
817 convert_to_result<unsigned>(r_constant_value);
818 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
819 convert_to_result<float>(r_constant_value);
825 TraversingVisitor::visit(call);
829 void ConstantFolder::visit(VariableDeclaration &var)
831 if(iteration_init && var.init_expression)
833 visit(var.init_expression);
836 /* Record the value of a constant initialization expression of an
837 iteration, so it can be used to evaluate the loop condition. */
838 iteration_var = &var;
839 iter_init_value = r_constant_value;
843 TraversingVisitor::visit(var);
846 void ConstantFolder::visit(Iteration &iter)
848 SetForScope<Block *> set_block(current_block, &iter.body);
850 /* The iteration variable is not normally inlined into expressions, so we
851 process it specially here. If the initial value causes the loop condition
852 to evaluate to false, then the expression can be folded. */
854 if(iter.init_statement)
856 SetFlag set_init(iteration_init);
857 iter.init_statement->visit(*this);
862 visit(iter.condition);
863 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
865 RefPtr<Literal> literal = new Literal;
866 literal->token = "false";
867 literal->value = r_constant_value;
868 iter.condition = literal;
873 iter.body.visit(*this);
874 if(iter.loop_expression)
875 visit(iter.loop_expression);
879 void ConstantConditionEliminator::apply(Stage &stage)
881 stage.content.visit(*this);
882 NodeRemover().apply(stage, nodes_to_remove);
885 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
887 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
888 if(literal->value.check_type<bool>())
889 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
893 void ConstantConditionEliminator::visit(Block &block)
895 SetForScope<Block *> set_block(current_block, &block);
896 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
903 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
905 r_ternary_result = 0;
908 expr = r_ternary_result;
909 r_ternary_result = 0;
912 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
914 ConstantStatus result = check_constant_condition(*ternary.condition);
915 if(result!=NOT_CONSTANT)
916 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
918 r_ternary_result = 0;
921 void ConstantConditionEliminator::visit(Conditional &cond)
923 ConstantStatus result = check_constant_condition(*cond.condition);
924 if(result!=NOT_CONSTANT)
926 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
927 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
928 current_block->body.splice(insert_point, block.body);
929 nodes_to_remove.insert(&cond);
933 TraversingVisitor::visit(cond);
936 void ConstantConditionEliminator::visit(Iteration &iter)
940 ConstantStatus result = check_constant_condition(*iter.condition);
941 if(result==CONSTANT_FALSE)
943 nodes_to_remove.insert(&iter);
948 TraversingVisitor::visit(iter);
952 UnreachableCodeRemover::UnreachableCodeRemover():
956 bool UnreachableCodeRemover::apply(Stage &stage)
958 stage.content.visit(*this);
959 NodeRemover().apply(stage, unreachable_nodes);
960 return !unreachable_nodes.empty();
963 void UnreachableCodeRemover::visit(Block &block)
965 auto i = block.body.begin();
966 for(; (reachable && i!=block.body.end()); ++i)
968 for(; i!=block.body.end(); ++i)
969 unreachable_nodes.insert(i->get());
972 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
974 TraversingVisitor::visit(func);
978 void UnreachableCodeRemover::visit(Conditional &cond)
980 cond.body.visit(*this);
981 bool reachable_if_true = reachable;
983 cond.else_body.visit(*this);
985 reachable |= reachable_if_true;
988 void UnreachableCodeRemover::visit(Iteration &iter)
990 TraversingVisitor::visit(iter);
992 /* Always consider code after a loop reachable, since there's no checking
993 for whether the loop executes. */
998 bool UnusedTypeRemover::apply(Stage &stage)
1000 stage.content.visit(*this);
1001 NodeRemover().apply(stage, unused_nodes);
1002 return !unused_nodes.empty();
1005 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1007 unused_nodes.erase(expr->type);
1008 TraversingVisitor::visit(expr);
1011 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1014 unused_nodes.erase(type.base_type);
1015 unused_nodes.insert(&type);
1018 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1021 unused_nodes.erase(type.base_type);
1022 unused_nodes.insert(&type);
1025 void UnusedTypeRemover::visit(StructDeclaration &strct)
1027 unused_nodes.insert(&strct);
1028 TraversingVisitor::visit(strct);
1031 void UnusedTypeRemover::visit(VariableDeclaration &var)
1033 unused_nodes.erase(var.type_declaration);
1034 TraversingVisitor::visit(var);
1037 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1039 unused_nodes.erase(iface.type_declaration);
1042 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1044 unused_nodes.erase(func.return_type_declaration);
1045 TraversingVisitor::visit(func);
1049 UnusedVariableRemover::UnusedVariableRemover():
1053 assignment_target(false),
1054 r_side_effects(false),
1056 composite_reference(false),
1060 bool UnusedVariableRemover::apply(Stage &s)
1063 s.content.visit(*this);
1065 for(const AssignmentInfo &a: assignments)
1066 if(a.used_by.empty())
1067 unused_nodes.insert(a.node);
1069 for(const auto &kvp: variables)
1071 if(kvp.second.output)
1073 /* The last visible assignments of output variables are used by the
1074 next stage or the API. */
1075 for(AssignmentInfo *a: kvp.second.assignments)
1076 unused_nodes.erase(a->node);
1079 if(!kvp.second.output && !kvp.second.referenced)
1081 // Don't remove variables from inside interface blocks.
1082 if(!kvp.second.interface_block)
1083 unused_nodes.insert(kvp.first);
1085 else if(kvp.second.interface_block)
1086 // Interface blocks are kept if even one member is used.
1087 unused_nodes.erase(kvp.second.interface_block);
1090 NodeRemover().apply(s, unused_nodes);
1092 return !unused_nodes.empty();
1095 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1097 VariableInfo &var_info = variables[target.declaration];
1098 var_info.referenced = true;
1099 if(!assignment_target)
1101 bool loop_external = false;
1102 for(AssignmentInfo *a: var_info.assignments)
1104 bool covered = true;
1105 for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1107 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1108 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1109 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1111 unsigned index1 = a->target.chain[j]&0x3F;
1112 unsigned index2 = target.chain[j]&0x3F;
1113 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1114 covered = index1&index2;
1115 else if(type1==Assignment::Target::ARRAY && index1<4)
1116 covered = index2&(1<<index1);
1117 else if(type2==Assignment::Target::ARRAY && index2<4)
1118 covered = index1&(1<<index2);
1119 /* If it's some other combination (shouldn't happen), leave
1123 covered = (a->target.chain[j]==target.chain[j]);
1128 a->used_by.push_back(&node);
1129 if(a->in_loop<in_loop)
1130 loop_external = true;
1135 loop_ext_refs.push_back(&node);
1139 void UnusedVariableRemover::visit(VariableReference &var)
1141 if(composite_reference)
1142 r_reference.declaration = var.declaration;
1144 referenced(var.declaration, var);
1147 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1149 if(composite_reference)
1150 r_reference.declaration = iface.declaration;
1152 referenced(iface.declaration, iface);
1155 void UnusedVariableRemover::visit_composite(Expression &expr)
1157 if(!composite_reference)
1158 r_reference = Assignment::Target();
1160 SetFlag set_composite(composite_reference);
1164 void UnusedVariableRemover::visit(MemberAccess &memacc)
1166 visit_composite(*memacc.left);
1168 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1170 if(!composite_reference && r_reference.declaration)
1171 referenced(r_reference, memacc);
1174 void UnusedVariableRemover::visit(Swizzle &swizzle)
1176 visit_composite(*swizzle.left);
1179 for(unsigned i=0; i<swizzle.count; ++i)
1180 mask |= 1<<swizzle.components[i];
1181 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1183 if(!composite_reference && r_reference.declaration)
1184 referenced(r_reference, swizzle);
1187 void UnusedVariableRemover::visit(UnaryExpression &unary)
1189 TraversingVisitor::visit(unary);
1190 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1191 r_side_effects = true;
1194 void UnusedVariableRemover::visit(BinaryExpression &binary)
1196 if(binary.oper->token[0]=='[')
1198 visit_composite(*binary.left);
1201 SetFlag clear_assignment(assignment_target, false);
1202 SetFlag clear_composite(composite_reference, false);
1203 binary.right->visit(*this);
1206 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1208 if(!composite_reference && r_reference.declaration)
1209 referenced(r_reference, binary);
1213 SetFlag clear_composite(composite_reference, false);
1214 TraversingVisitor::visit(binary);
1218 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1220 SetFlag clear_composite(composite_reference, false);
1221 TraversingVisitor::visit(ternary);
1224 void UnusedVariableRemover::visit(Assignment &assign)
1227 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1228 assign.left->visit(*this);
1230 assign.right->visit(*this);
1231 r_assignment = &assign;
1232 r_side_effects = true;
1235 void UnusedVariableRemover::visit(FunctionCall &call)
1237 SetFlag clear_composite(composite_reference, false);
1238 TraversingVisitor::visit(call);
1239 /* Treat function calls as having side effects so expression statements
1240 consisting of nothing but a function call won't be optimized away. */
1241 r_side_effects = true;
1243 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1245 for(const auto &kvp: variables)
1246 if(kvp.second.output)
1247 referenced(kvp.first, call);
1251 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1253 assignments.push_back(AssignmentInfo());
1254 AssignmentInfo &assign_info = assignments.back();
1255 assign_info.node = &node;
1256 assign_info.target = target;
1257 assign_info.in_loop = in_loop;
1259 /* An assignment to the target hides any assignments to the same target or
1261 VariableInfo &var_info = variables[target.declaration];
1262 for(unsigned i=0; i<var_info.assignments.size(); )
1264 const Assignment::Target &t = var_info.assignments[i]->target;
1266 bool subfield = (t.chain_len>=target.chain_len);
1267 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1268 subfield = (t.chain[j]==target.chain[j]);
1271 var_info.assignments.erase(var_info.assignments.begin()+i);
1276 var_info.assignments.push_back(&assign_info);
1279 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1282 r_side_effects = false;
1283 TraversingVisitor::visit(expr);
1284 if(r_assignment && r_assignment->target.declaration)
1285 record_assignment(r_assignment->target, expr);
1287 unused_nodes.insert(&expr);
1290 void UnusedVariableRemover::visit(StructDeclaration &strct)
1292 SetFlag set_struct(in_struct);
1293 TraversingVisitor::visit(strct);
1296 void UnusedVariableRemover::visit(VariableDeclaration &var)
1298 TraversingVisitor::visit(var);
1303 VariableInfo &var_info = variables[&var];
1304 var_info.interface_block = interface_block;
1306 /* Mark variables as output if they're used by the next stage or the
1309 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1311 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1313 if(var.init_expression)
1315 var_info.initialized = true;
1316 record_assignment(&var, *var.init_expression);
1320 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1322 VariableInfo &var_info = variables[&iface];
1323 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1326 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1328 for(const auto &kvp: other_vars)
1330 auto j = variables.find(kvp.first);
1331 if(j!=variables.end())
1333 /* The merged blocks started as copies of each other so any common
1334 assignments must be in the beginning. */
1336 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1337 if(kvp.second.assignments[k]!=j->second.assignments[k])
1340 // Remaining assignments are unique to each block; merge them.
1341 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1342 j->second.referenced |= kvp.second.referenced;
1345 variables.insert(kvp);
1349 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1351 if(func.body.body.empty())
1354 BlockVariableMap saved_vars = variables;
1355 // Assignments from other functions should not be visible.
1356 for(auto &kvp: variables)
1357 kvp.second.assignments.resize(kvp.second.initialized);
1358 TraversingVisitor::visit(func);
1359 swap(variables, saved_vars);
1360 merge_variables(saved_vars);
1362 /* Always treat function parameters as referenced. Removing unused
1363 parameters is not currently supported. */
1364 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1366 auto j = variables.find(p.get());
1367 if(j!=variables.end())
1368 j->second.referenced = true;
1372 void UnusedVariableRemover::visit(Conditional &cond)
1374 cond.condition->visit(*this);
1375 BlockVariableMap saved_vars = variables;
1376 cond.body.visit(*this);
1377 swap(saved_vars, variables);
1378 cond.else_body.visit(*this);
1380 /* Visible assignments after the conditional is the union of those visible
1381 at the end of the if and else blocks. If there was no else block, then it's
1382 the union of the if block and the state before it. */
1383 merge_variables(saved_vars);
1386 void UnusedVariableRemover::visit(Iteration &iter)
1388 BlockVariableMap saved_vars = variables;
1389 vector<Node *> saved_refs;
1390 swap(loop_ext_refs, saved_refs);
1392 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1393 TraversingVisitor::visit(iter);
1395 swap(loop_ext_refs, saved_refs);
1397 /* Visit the external references of the loop again to record assignments
1398 done in the loop as used. */
1399 for(Node *n: saved_refs)
1402 /* Merge assignments from the iteration, without clearing previous state.
1403 Further analysis is needed to determine which parts of the iteration body
1404 are always executed, if any. */
1405 merge_variables(saved_vars);
1409 bool UnusedFunctionRemover::apply(Stage &stage)
1411 stage.content.visit(*this);
1412 NodeRemover().apply(stage, unused_nodes);
1413 return !unused_nodes.empty();
1416 void UnusedFunctionRemover::visit(FunctionCall &call)
1418 TraversingVisitor::visit(call);
1420 unused_nodes.erase(call.declaration);
1421 if(call.declaration && call.declaration->definition!=call.declaration)
1422 used_definitions.insert(call.declaration->definition);
1425 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1427 TraversingVisitor::visit(func);
1429 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1430 unused_nodes.insert(&func);