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 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
17 stage.content.visit(*this);
20 void ConstantSpecializer::visit(VariableDeclaration &var)
22 bool specializable = false;
25 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
26 auto i = find_member(qualifiers, string("constant_id"), &Layout::Qualifier::name);
27 if(i!=qualifiers.end())
31 if(qualifiers.empty())
38 auto i = values->find(var.name);
41 RefPtr<Literal> literal = new Literal;
44 literal->token = (i->second ? "true" : "false");
45 literal->value = static_cast<bool>(i->second);
47 else if(var.type=="int")
49 literal->token = lexical_cast<string>(i->second);
50 literal->value = i->second;
52 var.init_expression = literal;
58 void InlineableFunctionLocator::visit(FunctionCall &call)
60 FunctionDeclaration *def = call.declaration;
62 def = def->definition;
66 unsigned &count = refcounts[def];
68 /* Don't inline functions which are called more than once or are called
70 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
71 inlineable.erase(def);
74 TraversingVisitor::visit(call);
77 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
79 bool has_out_params = any_of(func.parameters.begin(), func.parameters.end(),
80 [](const RefPtr<VariableDeclaration> &p){ return p->interface=="out"; });
82 unsigned &count = refcounts[func.definition];
83 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
84 inlineable.insert(func.definition);
86 SetForScope<FunctionDeclaration *> set(current_function, &func);
88 TraversingVisitor::visit(func);
91 void InlineableFunctionLocator::visit(Conditional &cond)
93 TraversingVisitor::visit(cond);
94 inlineable.erase(current_function);
97 void InlineableFunctionLocator::visit(Iteration &iter)
99 TraversingVisitor::visit(iter);
100 inlineable.erase(current_function);
103 void InlineableFunctionLocator::visit(Return &ret)
105 TraversingVisitor::visit(ret);
107 inlineable.erase(current_function);
112 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
114 source_func = call.declaration->definition;
116 /* Populate referenced_names from the target function so we can rename
117 variables from the inlined function that would conflict. */
119 target_func.visit(*this);
121 /* Inline and rename passes must be interleaved so used variable names are
122 known when inlining the return statement. */
124 staging_block.parent = &tgt_blk;
125 staging_block.variables.clear();
127 vector<RefPtr<VariableDeclaration> > params;
128 params.reserve(source_func->parameters.size());
129 for(const RefPtr<VariableDeclaration> &p: source_func->parameters)
131 RefPtr<VariableDeclaration> var = p->clone();
132 var->interface.clear();
134 SetForScope<Pass> set_pass(pass, RENAME);
137 staging_block.body.push_back_nocopy(var);
138 params.push_back(var);
141 for(const RefPtr<Statement> &s: source_func->body.body)
143 r_inlined_statement = 0;
145 if(!r_inlined_statement)
146 r_inlined_statement = s->clone();
148 SetForScope<Pass> set_pass(pass, RENAME);
149 r_inlined_statement->visit(*this);
151 staging_block.body.push_back_nocopy(r_inlined_statement);
154 /* Now collect names from the staging block. Local variables that would
155 have conflicted with the target function were renamed earlier. */
157 referenced_names.clear();
158 staging_block.variables.clear();
159 staging_block.visit(*this);
161 /* Rename variables in the target function so they don't interfere with
162 global identifiers used by the source function. */
164 staging_block.parent = source_func->body.parent;
165 target_func.visit(*this);
167 // Put the argument expressions in place after all renaming has been done.
168 for(unsigned i=0; i<source_func->parameters.size(); ++i)
169 params[i]->init_expression = call.arguments[i]->clone();
171 tgt_blk.body.splice(ins_pt, staging_block.body);
173 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
175 return r_result_name;
178 void InlineContentInjector::visit(VariableReference &var)
182 auto i = staging_block.variables.find(var.name);
183 if(i!=staging_block.variables.end())
184 var.name = i->second->name;
186 else if(pass==REFERENCED)
187 referenced_names.insert(var.name);
190 void InlineContentInjector::visit(InterfaceBlockReference &iface)
193 referenced_names.insert(iface.name);
196 void InlineContentInjector::visit(FunctionCall &call)
199 referenced_names.insert(call.name);
200 TraversingVisitor::visit(call);
203 void InlineContentInjector::visit(VariableDeclaration &var)
205 TraversingVisitor::visit(var);
209 /* Check against conflicts with the other context as well as variables
210 already renamed here. */
211 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
212 staging_block.variables[var.name] = &var;
215 string mapped_name = get_unused_variable_name(staging_block, var.name);
216 if(mapped_name!=var.name)
218 staging_block.variables[mapped_name] = &var;
219 var.name = mapped_name;
223 else if(pass==REFERENCED)
224 referenced_names.insert(var.type);
227 void InlineContentInjector::visit(Return &ret)
229 TraversingVisitor::visit(ret);
231 if(pass==INLINE && ret.expression)
233 // Create a new variable to hold the return value of the inlined function.
234 r_result_name = get_unused_variable_name(staging_block, "_return");
235 RefPtr<VariableDeclaration> var = new VariableDeclaration;
236 var->source = ret.source;
237 var->line = ret.line;
238 var->type = source_func->return_type;
239 var->name = r_result_name;
240 var->init_expression = ret.expression->clone();
241 r_inlined_statement = var;
246 bool FunctionInliner::apply(Stage &s)
249 inlineable = InlineableFunctionLocator().apply(s);
250 r_any_inlined = false;
251 s.content.visit(*this);
252 return r_any_inlined;
255 void FunctionInliner::visit(RefPtr<Expression> &ptr)
261 ptr = r_inline_result;
262 r_any_inlined = true;
267 void FunctionInliner::visit(Block &block)
269 SetForScope<Block *> set_block(current_block, &block);
270 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
271 for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
278 void FunctionInliner::visit(FunctionCall &call)
280 for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
286 FunctionDeclaration *def = call.declaration;
288 def = def->definition;
290 if(def && inlineable.count(def))
292 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
294 // This will later get removed by UnusedVariableRemover.
295 if(result_name.empty())
296 result_name = "_msp_unused_from_inline";
298 RefPtr<VariableReference> ref = new VariableReference;
299 ref->name = result_name;
300 r_inline_result = ref;
302 /* Inlined variables need to be resolved before this function can be
304 inlineable.erase(current_function);
305 r_inlined_here = true;
309 void FunctionInliner::visit(FunctionDeclaration &func)
311 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
312 TraversingVisitor::visit(func);
313 r_inlined_here = false;
316 void FunctionInliner::visit(Iteration &iter)
318 /* Visit the initialization statement before entering the loop body so the
319 inlined statements get inserted outside. */
320 if(iter.init_statement)
321 iter.init_statement->visit(*this);
323 SetForScope<Block *> set_block(current_block, &iter.body);
324 /* Skip the condition and loop expression parts because they're not properly
325 inside the body block. Inlining anything into them will require a more
326 comprehensive transformation. */
327 iter.body.visit(*this);
331 bool ExpressionInliner::apply(Stage &s)
333 s.content.visit(*this);
335 bool any_inlined = false;
336 for(ExpressionInfo &e: expressions)
337 if(e.expression && (e.trivial || e.uses.size()==1))
339 for(ExpressionUse &u: e.uses)
342 *u.reference = e.expression->clone();
350 void ExpressionInliner::visit(RefPtr<Expression> &expr)
354 if(r_ref_info && r_ref_info->expression)
357 use.reference = &expr;
358 use.ref_scope = current_block;
359 use.blocked = access_write;
361 if(iteration_body && !r_ref_info->trivial)
363 /* Block inlining of non-trivial expressions assigned outside an
364 iteration statement. The iteration may run multiple times, which
365 would cause the expression to also be evaluated multiple times. */
366 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
367 use.blocked = (i==r_ref_info->assign_scope);
370 /* Block inlining assignments from from inner scopes. The assignment may
371 depend on local variables of that scope or may not always be executed. */
372 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
373 use.blocked = (i==current_block);
375 r_ref_info->uses.push_back(use);
381 void ExpressionInliner::visit(VariableReference &var)
383 if(var.declaration && access_read)
385 auto i = assignments.find(var.declaration);
386 if(i!=assignments.end())
387 r_ref_info = i->second;
391 void ExpressionInliner::visit(MemberAccess &memacc)
397 void ExpressionInliner::visit(Swizzle &swizzle)
403 void ExpressionInliner::visit(UnaryExpression &unary)
405 SetFlag set_write(access_write, access_write || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
406 visit(unary.expression);
410 void ExpressionInliner::visit(BinaryExpression &binary)
414 SetFlag clear_write(access_write, false);
420 void ExpressionInliner::visit(Assignment &assign)
423 SetFlag set_read(access_read, assign.oper->token[0]!='=');
424 SetFlag set_write(access_write);
431 auto i = assignments.find(assign.target);
432 if(i!=assignments.end())
434 if(iteration_body && i->second->expression)
436 /* Block inlining into previous references within the iteration
437 statement. On iterations after the first they would refer to the
438 assignment within the iteration. */
439 for(ExpressionUse &u: i->second->uses)
440 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
441 u.blocked = (k==iteration_body);
444 expressions.push_back(ExpressionInfo());
445 ExpressionInfo &info = expressions.back();
446 info.target = assign.target;
447 // Self-referencing assignments can't be inlined without additional work.
448 if(!assign.self_referencing)
449 info.expression = assign.right;
450 info.assign_scope = current_block;
451 info.trivial = r_trivial;
459 void ExpressionInliner::visit(TernaryExpression &ternary)
461 visit(ternary.condition);
462 visit(ternary.true_expr);
463 visit(ternary.false_expr);
467 void ExpressionInliner::visit(FunctionCall &call)
469 TraversingVisitor::visit(call);
473 void ExpressionInliner::visit(VariableDeclaration &var)
477 TraversingVisitor::visit(var);
479 bool constant = var.constant;
480 if(constant && var.layout)
482 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
483 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
486 /* Only inline global variables if they're constant and have trivial
487 initializers. Non-constant variables could change in ways which are hard to
488 analyze and non-trivial expressions could be expensive to inline. */
489 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
491 expressions.push_back(ExpressionInfo());
492 ExpressionInfo &info = expressions.back();
494 /* Assume variables declared in an iteration initialization statement
495 will have their values change throughout the iteration. */
497 info.expression = var.init_expression;
498 info.assign_scope = current_block;
499 info.trivial = r_trivial;
501 assignments[&var] = &info;
505 void ExpressionInliner::visit(Iteration &iter)
507 SetForScope<Block *> set_block(current_block, &iter.body);
508 if(iter.init_statement)
510 SetFlag set_init(iteration_init);
511 iter.init_statement->visit(*this);
514 SetForScope<Block *> set_body(iteration_body, &iter.body);
516 visit(iter.condition);
517 iter.body.visit(*this);
518 if(iter.loop_expression)
519 visit(iter.loop_expression);
524 T ConstantFolder::evaluate_logical(char oper, T left, T right)
528 case '&': return left&right;
529 case '|': return left|right;
530 case '^': return left^right;
536 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
538 switch(oper[0]|oper[1])
540 case '<': return left<right;
541 case '<'|'=': return left<=right;
542 case '>': return left>right;
543 case '>'|'=': return left>=right;
544 default: return false;
549 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
553 case '+': return left+right;
554 case '-': return left-right;
555 case '*': return left*right;
556 case '/': return left/right;
562 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
566 case '%': return left%right;
567 case '<': return left<<right;
568 case '>': return left>>right;
574 void ConstantFolder::convert_to_result(const Variant &value)
576 if(value.check_type<bool>())
577 set_result(static_cast<T>(value.value<bool>()));
578 else if(value.check_type<int>())
579 set_result(static_cast<T>(value.value<int>()));
580 else if(value.check_type<unsigned>())
581 set_result(static_cast<T>(value.value<unsigned>()));
582 else if(value.check_type<float>())
583 set_result(static_cast<T>(value.value<float>()));
586 void ConstantFolder::set_result(const Variant &value, bool literal)
588 r_constant_value = value;
593 void ConstantFolder::visit(RefPtr<Expression> &expr)
595 r_constant_value = Variant();
598 r_uses_iter_var = false;
600 /* Don't replace literals since they'd only be replaced with an identical
601 literal. Also skip anything that uses an iteration variable, but pass on
602 the result so the Iteration visiting function can handle it. */
603 if(!r_constant || r_literal || r_uses_iter_var)
606 RefPtr<Literal> literal = new Literal;
607 if(r_constant_value.check_type<bool>())
608 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
609 else if(r_constant_value.check_type<int>())
610 literal->token = lexical_cast<string>(r_constant_value.value<int>());
611 else if(r_constant_value.check_type<unsigned>())
612 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
613 else if(r_constant_value.check_type<float>())
615 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
616 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
617 literal->token += ".0";
624 literal->value = r_constant_value;
629 void ConstantFolder::visit(Literal &literal)
631 set_result(literal.value, true);
634 void ConstantFolder::visit(VariableReference &var)
636 /* If an iteration variable is initialized with a constant value, return
637 that value here for the purpose of evaluating the loop condition for the
639 if(var.declaration==iteration_var)
641 set_result(iter_init_value);
642 r_uses_iter_var = true;
646 void ConstantFolder::visit(MemberAccess &memacc)
648 TraversingVisitor::visit(memacc);
652 void ConstantFolder::visit(Swizzle &swizzle)
654 TraversingVisitor::visit(swizzle);
658 void ConstantFolder::visit(UnaryExpression &unary)
660 TraversingVisitor::visit(unary);
661 bool can_fold = r_constant;
666 char oper = unary.oper->token[0];
667 char oper2 = unary.oper->token[1];
670 if(r_constant_value.check_type<bool>())
671 set_result(!r_constant_value.value<bool>());
675 if(r_constant_value.check_type<int>())
676 set_result(~r_constant_value.value<int>());
677 else if(r_constant_value.check_type<unsigned>())
678 set_result(~r_constant_value.value<unsigned>());
680 else if(oper=='-' && !oper2)
682 if(r_constant_value.check_type<int>())
683 set_result(-r_constant_value.value<int>());
684 else if(r_constant_value.check_type<unsigned>())
685 set_result(-r_constant_value.value<unsigned>());
686 else if(r_constant_value.check_type<float>())
687 set_result(-r_constant_value.value<float>());
691 void ConstantFolder::visit(BinaryExpression &binary)
694 bool left_constant = r_constant;
695 bool left_iter_var = r_uses_iter_var;
696 Variant left_value = r_constant_value;
699 r_uses_iter_var = true;
701 bool can_fold = (left_constant && r_constant);
706 // Currently only expressions with both sides of equal types are handled.
707 if(!left_value.check_same_type(r_constant_value))
710 char oper = binary.oper->token[0];
711 char oper2 = binary.oper->token[1];
712 if(oper=='&' || oper=='|' || oper=='^')
714 if(oper2==oper && left_value.check_type<bool>())
715 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
716 else if(!oper2 && left_value.check_type<int>())
717 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
718 else if(!oper2 && left_value.check_type<unsigned>())
719 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
721 else if((oper=='<' || oper=='>') && oper2!=oper)
723 if(left_value.check_type<int>())
724 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
725 else if(left_value.check_type<unsigned>())
726 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
727 else if(left_value.check_type<float>())
728 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
730 else if((oper=='=' || oper=='!') && oper2=='=')
732 if(left_value.check_type<int>())
733 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
734 else if(left_value.check_type<unsigned>())
735 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
736 else if(left_value.check_type<float>())
737 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
739 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
741 if(left_value.check_type<int>())
742 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
743 else if(left_value.check_type<unsigned>())
744 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
745 else if(left_value.check_type<float>())
746 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
748 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
750 if(left_value.check_type<int>())
751 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
752 else if(left_value.check_type<unsigned>())
753 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
757 void ConstantFolder::visit(Assignment &assign)
759 TraversingVisitor::visit(assign);
763 void ConstantFolder::visit(TernaryExpression &ternary)
765 TraversingVisitor::visit(ternary);
769 void ConstantFolder::visit(FunctionCall &call)
771 if(call.constructor && call.type && call.arguments.size()==1)
773 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
776 visit(call.arguments[0]);
777 bool can_fold = r_constant;
782 if(basic->kind==BasicTypeDeclaration::BOOL)
783 convert_to_result<bool>(r_constant_value);
784 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
785 convert_to_result<int>(r_constant_value);
786 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
787 convert_to_result<unsigned>(r_constant_value);
788 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
789 convert_to_result<float>(r_constant_value);
795 TraversingVisitor::visit(call);
799 void ConstantFolder::visit(VariableDeclaration &var)
801 if(iteration_init && var.init_expression)
803 visit(var.init_expression);
806 /* Record the value of a constant initialization expression of an
807 iteration, so it can be used to evaluate the loop condition. */
808 iteration_var = &var;
809 iter_init_value = r_constant_value;
813 TraversingVisitor::visit(var);
816 void ConstantFolder::visit(Iteration &iter)
818 SetForScope<Block *> set_block(current_block, &iter.body);
820 /* The iteration variable is not normally inlined into expressions, so we
821 process it specially here. If the initial value causes the loop condition
822 to evaluate to false, then the expression can be folded. */
824 if(iter.init_statement)
826 SetFlag set_init(iteration_init);
827 iter.init_statement->visit(*this);
832 visit(iter.condition);
833 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
835 RefPtr<Literal> literal = new Literal;
836 literal->token = "false";
837 literal->value = r_constant_value;
838 iter.condition = literal;
843 iter.body.visit(*this);
844 if(iter.loop_expression)
845 visit(iter.loop_expression);
849 void ConstantConditionEliminator::apply(Stage &stage)
851 stage.content.visit(*this);
852 NodeRemover().apply(stage, nodes_to_remove);
855 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
857 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
858 if(literal->value.check_type<bool>())
859 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
863 void ConstantConditionEliminator::visit(Block &block)
865 SetForScope<Block *> set_block(current_block, &block);
866 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
873 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
875 r_ternary_result = 0;
878 expr = r_ternary_result;
879 r_ternary_result = 0;
882 void ConstantConditionEliminator::visit(UnaryExpression &unary)
884 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
885 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
887 auto i = current_block->variables.find(var->name);
888 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
892 TraversingVisitor::visit(unary);
895 void ConstantConditionEliminator::visit(Assignment &assign)
897 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
898 if(i==current_block->variables.end())
899 r_external_side_effects = true;
900 TraversingVisitor::visit(assign);
903 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
905 ConstantStatus result = check_constant_condition(*ternary.condition);
906 if(result!=NOT_CONSTANT)
907 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
909 r_ternary_result = 0;
912 void ConstantConditionEliminator::visit(FunctionCall &call)
914 r_external_side_effects = true;
915 TraversingVisitor::visit(call);
918 void ConstantConditionEliminator::visit(Conditional &cond)
920 ConstantStatus result = check_constant_condition(*cond.condition);
921 if(result!=NOT_CONSTANT)
923 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
924 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
925 current_block->body.splice(insert_point, block.body);
926 nodes_to_remove.insert(&cond);
930 r_external_side_effects = false;
931 TraversingVisitor::visit(cond);
933 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
934 nodes_to_remove.insert(&cond);
937 void ConstantConditionEliminator::visit(Iteration &iter)
941 ConstantStatus result = check_constant_condition(*iter.condition);
942 if(result==CONSTANT_FALSE)
944 nodes_to_remove.insert(&iter);
949 r_external_side_effects = false;
950 TraversingVisitor::visit(iter);
951 if(iter.body.body.empty() && !r_external_side_effects)
952 nodes_to_remove.insert(&iter);
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 bool UnusedVariableRemover::apply(Stage &s)
1052 s.content.visit(*this);
1054 for(const AssignmentInfo &a: assignments)
1055 if(a.used_by.empty())
1056 unused_nodes.insert(a.node);
1058 for(const auto &kvp: variables)
1060 if(kvp.second.output)
1062 /* The last visible assignments of output variables are used by the
1063 next stage or the API. */
1064 for(AssignmentInfo *a: kvp.second.assignments)
1065 unused_nodes.erase(a->node);
1068 if(!kvp.second.output && !kvp.second.referenced)
1070 // Don't remove variables from inside interface blocks.
1071 if(!kvp.second.interface_block)
1072 unused_nodes.insert(kvp.first);
1074 else if(kvp.second.interface_block)
1075 // Interface blocks are kept if even one member is used.
1076 unused_nodes.erase(kvp.second.interface_block);
1079 NodeRemover().apply(s, unused_nodes);
1081 return !unused_nodes.empty();
1084 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1086 VariableInfo &var_info = variables[target.declaration];
1087 var_info.referenced = true;
1088 if(!assignment_target)
1090 bool loop_external = false;
1091 for(AssignmentInfo *a: var_info.assignments)
1093 bool covered = true;
1094 for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1096 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1097 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1098 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1100 unsigned index1 = a->target.chain[j]&0x3F;
1101 unsigned index2 = target.chain[j]&0x3F;
1102 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1103 covered = index1&index2;
1104 else if(type1==Assignment::Target::ARRAY && index1<4)
1105 covered = index2&(1<<index1);
1106 else if(type2==Assignment::Target::ARRAY && index2<4)
1107 covered = index1&(1<<index2);
1108 /* If it's some other combination (shouldn't happen), leave
1112 covered = (a->target.chain[j]==target.chain[j]);
1117 a->used_by.push_back(&node);
1118 if(a->in_loop<in_loop)
1119 loop_external = true;
1124 loop_ext_refs.push_back(&node);
1128 void UnusedVariableRemover::visit(VariableReference &var)
1130 if(composite_reference)
1131 r_reference.declaration = var.declaration;
1133 referenced(var.declaration, var);
1136 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1138 if(composite_reference)
1139 r_reference.declaration = iface.declaration;
1141 referenced(iface.declaration, iface);
1144 void UnusedVariableRemover::visit_composite(Expression &expr)
1146 if(!composite_reference)
1147 r_reference = Assignment::Target();
1149 SetFlag set_composite(composite_reference);
1153 void UnusedVariableRemover::visit(MemberAccess &memacc)
1155 visit_composite(*memacc.left);
1157 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1159 if(!composite_reference && r_reference.declaration)
1160 referenced(r_reference, memacc);
1163 void UnusedVariableRemover::visit(Swizzle &swizzle)
1165 visit_composite(*swizzle.left);
1168 for(unsigned i=0; i<swizzle.count; ++i)
1169 mask |= 1<<swizzle.components[i];
1170 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1172 if(!composite_reference && r_reference.declaration)
1173 referenced(r_reference, swizzle);
1176 void UnusedVariableRemover::visit(UnaryExpression &unary)
1178 TraversingVisitor::visit(unary);
1179 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1180 r_side_effects = true;
1183 void UnusedVariableRemover::visit(BinaryExpression &binary)
1185 if(binary.oper->token[0]=='[')
1187 visit_composite(*binary.left);
1190 SetFlag clear_assignment(assignment_target, false);
1191 SetFlag clear_composite(composite_reference, false);
1192 binary.right->visit(*this);
1195 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1197 if(!composite_reference && r_reference.declaration)
1198 referenced(r_reference, binary);
1202 SetFlag clear_composite(composite_reference, false);
1203 TraversingVisitor::visit(binary);
1207 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1209 SetFlag clear_composite(composite_reference, false);
1210 TraversingVisitor::visit(ternary);
1213 void UnusedVariableRemover::visit(Assignment &assign)
1216 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1217 assign.left->visit(*this);
1219 assign.right->visit(*this);
1220 r_assignment = &assign;
1221 r_side_effects = true;
1224 void UnusedVariableRemover::visit(FunctionCall &call)
1226 SetFlag clear_composite(composite_reference, false);
1227 TraversingVisitor::visit(call);
1228 /* Treat function calls as having side effects so expression statements
1229 consisting of nothing but a function call won't be optimized away. */
1230 r_side_effects = true;
1232 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1234 for(const auto &kvp: variables)
1235 if(kvp.second.output)
1236 referenced(kvp.first, call);
1240 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1242 assignments.push_back(AssignmentInfo());
1243 AssignmentInfo &assign_info = assignments.back();
1244 assign_info.node = &node;
1245 assign_info.target = target;
1246 assign_info.in_loop = in_loop;
1248 /* An assignment to the target hides any assignments to the same target or
1250 VariableInfo &var_info = variables[target.declaration];
1251 for(unsigned i=0; i<var_info.assignments.size(); )
1253 const Assignment::Target &t = var_info.assignments[i]->target;
1255 bool subfield = (t.chain_len>=target.chain_len);
1256 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1257 subfield = (t.chain[j]==target.chain[j]);
1260 var_info.assignments.erase(var_info.assignments.begin()+i);
1265 var_info.assignments.push_back(&assign_info);
1268 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1271 r_side_effects = false;
1272 TraversingVisitor::visit(expr);
1273 if(r_assignment && r_assignment->target.declaration)
1274 record_assignment(r_assignment->target, expr);
1276 unused_nodes.insert(&expr);
1279 void UnusedVariableRemover::visit(StructDeclaration &strct)
1281 SetFlag set_struct(in_struct);
1282 TraversingVisitor::visit(strct);
1285 void UnusedVariableRemover::visit(VariableDeclaration &var)
1287 TraversingVisitor::visit(var);
1292 VariableInfo &var_info = variables[&var];
1293 var_info.interface_block = interface_block;
1295 /* Mark variables as output if they're used by the next stage or the
1298 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1300 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1302 if(var.init_expression)
1304 var_info.initialized = true;
1305 record_assignment(&var, *var.init_expression);
1309 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1311 VariableInfo &var_info = variables[&iface];
1312 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1315 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1317 for(const auto &kvp: other_vars)
1319 auto j = variables.find(kvp.first);
1320 if(j!=variables.end())
1322 /* The merged blocks started as copies of each other so any common
1323 assignments must be in the beginning. */
1325 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1326 if(kvp.second.assignments[k]!=j->second.assignments[k])
1329 // Remaining assignments are unique to each block; merge them.
1330 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1331 j->second.referenced |= kvp.second.referenced;
1334 variables.insert(kvp);
1338 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1340 if(func.body.body.empty())
1343 BlockVariableMap saved_vars = variables;
1344 // Assignments from other functions should not be visible.
1345 for(auto &kvp: variables)
1346 kvp.second.assignments.resize(kvp.second.initialized);
1347 TraversingVisitor::visit(func);
1348 swap(variables, saved_vars);
1349 merge_variables(saved_vars);
1351 /* Always treat function parameters as referenced. Removing unused
1352 parameters is not currently supported. */
1353 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1355 auto j = variables.find(p.get());
1356 if(j!=variables.end())
1357 j->second.referenced = true;
1361 void UnusedVariableRemover::visit(Conditional &cond)
1363 cond.condition->visit(*this);
1364 BlockVariableMap saved_vars = variables;
1365 cond.body.visit(*this);
1366 swap(saved_vars, variables);
1367 cond.else_body.visit(*this);
1369 /* Visible assignments after the conditional is the union of those visible
1370 at the end of the if and else blocks. If there was no else block, then it's
1371 the union of the if block and the state before it. */
1372 merge_variables(saved_vars);
1375 void UnusedVariableRemover::visit(Iteration &iter)
1377 BlockVariableMap saved_vars = variables;
1378 vector<Node *> saved_refs;
1379 swap(loop_ext_refs, saved_refs);
1381 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1382 TraversingVisitor::visit(iter);
1384 swap(loop_ext_refs, saved_refs);
1386 /* Visit the external references of the loop again to record assignments
1387 done in the loop as used. */
1388 for(Node *n: saved_refs)
1391 /* Merge assignments from the iteration, without clearing previous state.
1392 Further analysis is needed to determine which parts of the iteration body
1393 are always executed, if any. */
1394 merge_variables(saved_vars);
1398 bool UnusedFunctionRemover::apply(Stage &stage)
1400 stage.content.visit(*this);
1401 NodeRemover().apply(stage, unused_nodes);
1402 return !unused_nodes.empty();
1405 void UnusedFunctionRemover::visit(FunctionCall &call)
1407 TraversingVisitor::visit(call);
1409 unused_nodes.erase(call.declaration);
1410 if(call.declaration && call.declaration->definition!=call.declaration)
1411 used_definitions.insert(call.declaration->definition);
1414 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1416 TraversingVisitor::visit(func);
1418 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1419 unused_nodes.insert(&func);