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);
523 bool AggregateDismantler::apply(Stage &stage)
525 stage.content.visit(*this);
527 bool any_dismantled = false;
528 for(const auto &kvp: aggregates)
530 if(kvp.second.referenced || !kvp.second.members_referenced)
533 for(const AggregateMember &m: kvp.second.members)
535 VariableDeclaration *var = new VariableDeclaration;
536 var->source = kvp.first->source;
537 var->line = kvp.first->line;
538 var->name = get_unused_variable_name(*kvp.second.decl_scope, format("%s_%s", kvp.second.declaration->name, m.declaration->name));
539 var->type = m.declaration->type;
541 var->init_expression = m.initializer->clone();
543 kvp.second.decl_scope->body.insert(kvp.second.insert_point, var);
545 for(RefPtr<Expression> *r: m.references)
547 VariableReference *ref = new VariableReference;
548 ref->name = var->name;
552 any_dismantled = true;
556 return any_dismantled;
559 void AggregateDismantler::visit(Block &block)
561 SetForScope<Block *> set_block(current_block, &block);
562 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
569 void AggregateDismantler::visit(RefPtr<Expression> &expr)
573 if(r_aggregate_ref && r_reference.chain_len==1 && (r_reference.chain[0]&0x3F)!=0x3F)
575 r_aggregate_ref->members[r_reference.chain[0]&0x3F].references.push_back(&expr);
576 r_aggregate_ref->members_referenced = true;
581 void AggregateDismantler::visit(VariableReference &var)
583 if(composite_reference)
584 r_reference.declaration = var.declaration;
587 auto i = aggregates.find(var.declaration);
588 if(i!=aggregates.end())
589 i->second.referenced = true;
593 void AggregateDismantler::visit_composite(RefPtr<Expression> &expr)
595 if(!composite_reference)
596 r_reference = Assignment::Target();
598 SetFlag set_composite(composite_reference);
602 void AggregateDismantler::visit(MemberAccess &memacc)
604 visit_composite(memacc.left);
606 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
608 if(r_reference.declaration && r_reference.chain_len==1)
610 auto i = aggregates.find(r_reference.declaration);
611 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
617 void AggregateDismantler::visit(BinaryExpression &binary)
619 if(binary.oper->token[0]=='[')
621 visit_composite(binary.left);
623 SetFlag clear_composite(composite_reference, false);
627 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
631 SetFlag clear_composite(composite_reference, false);
632 TraversingVisitor::visit(binary);
636 void AggregateDismantler::visit(VariableDeclaration &var)
638 TraversingVisitor::visit(var);
640 if(var.interface.empty())
641 if(const StructDeclaration *strct = dynamic_cast<const StructDeclaration *>(var.type_declaration))
643 const FunctionCall *init_call = dynamic_cast<const FunctionCall *>(var.init_expression.get());
644 if((init_call && init_call->constructor) || !var.init_expression)
647 Aggregate &aggre = aggregates[&var];
648 aggre.declaration = &var;
649 aggre.decl_scope = current_block;
650 aggre.insert_point = insert_point;
653 for(const RefPtr<Statement> &s: strct->members.body)
655 if(const VariableDeclaration *mem_decl = dynamic_cast<const VariableDeclaration *>(s.get()))
657 AggregateMember member;
658 member.declaration = mem_decl;
660 member.initializer = init_call->arguments[i];
661 aggre.members.push_back(member);
671 T ConstantFolder::evaluate_logical(char oper, T left, T right)
675 case '&': return left&right;
676 case '|': return left|right;
677 case '^': return left^right;
683 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
685 switch(oper[0]|oper[1])
687 case '<': return left<right;
688 case '<'|'=': return left<=right;
689 case '>': return left>right;
690 case '>'|'=': return left>=right;
691 default: return false;
696 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
700 case '+': return left+right;
701 case '-': return left-right;
702 case '*': return left*right;
703 case '/': return left/right;
709 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
713 case '%': return left%right;
714 case '<': return left<<right;
715 case '>': return left>>right;
721 void ConstantFolder::convert_to_result(const Variant &value)
723 if(value.check_type<bool>())
724 set_result(static_cast<T>(value.value<bool>()));
725 else if(value.check_type<int>())
726 set_result(static_cast<T>(value.value<int>()));
727 else if(value.check_type<unsigned>())
728 set_result(static_cast<T>(value.value<unsigned>()));
729 else if(value.check_type<float>())
730 set_result(static_cast<T>(value.value<float>()));
733 void ConstantFolder::set_result(const Variant &value, bool literal)
735 r_constant_value = value;
740 void ConstantFolder::visit(RefPtr<Expression> &expr)
742 r_constant_value = Variant();
745 r_uses_iter_var = false;
747 /* Don't replace literals since they'd only be replaced with an identical
748 literal. Also skip anything that uses an iteration variable, but pass on
749 the result so the Iteration visiting function can handle it. */
750 if(!r_constant || r_literal || r_uses_iter_var)
753 RefPtr<Literal> literal = new Literal;
754 if(r_constant_value.check_type<bool>())
755 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
756 else if(r_constant_value.check_type<int>())
757 literal->token = lexical_cast<string>(r_constant_value.value<int>());
758 else if(r_constant_value.check_type<unsigned>())
759 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
760 else if(r_constant_value.check_type<float>())
762 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
763 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
764 literal->token += ".0";
771 literal->value = r_constant_value;
776 void ConstantFolder::visit(Literal &literal)
778 set_result(literal.value, true);
781 void ConstantFolder::visit(VariableReference &var)
783 /* If an iteration variable is initialized with a constant value, return
784 that value here for the purpose of evaluating the loop condition for the
786 if(var.declaration==iteration_var)
788 set_result(iter_init_value);
789 r_uses_iter_var = true;
793 void ConstantFolder::visit(MemberAccess &memacc)
795 TraversingVisitor::visit(memacc);
799 void ConstantFolder::visit(Swizzle &swizzle)
801 TraversingVisitor::visit(swizzle);
805 void ConstantFolder::visit(UnaryExpression &unary)
807 TraversingVisitor::visit(unary);
808 bool can_fold = r_constant;
813 char oper = unary.oper->token[0];
814 char oper2 = unary.oper->token[1];
817 if(r_constant_value.check_type<bool>())
818 set_result(!r_constant_value.value<bool>());
822 if(r_constant_value.check_type<int>())
823 set_result(~r_constant_value.value<int>());
824 else if(r_constant_value.check_type<unsigned>())
825 set_result(~r_constant_value.value<unsigned>());
827 else if(oper=='-' && !oper2)
829 if(r_constant_value.check_type<int>())
830 set_result(-r_constant_value.value<int>());
831 else if(r_constant_value.check_type<unsigned>())
832 set_result(-r_constant_value.value<unsigned>());
833 else if(r_constant_value.check_type<float>())
834 set_result(-r_constant_value.value<float>());
838 void ConstantFolder::visit(BinaryExpression &binary)
841 bool left_constant = r_constant;
842 bool left_iter_var = r_uses_iter_var;
843 Variant left_value = r_constant_value;
846 r_uses_iter_var = true;
848 bool can_fold = (left_constant && r_constant);
853 // Currently only expressions with both sides of equal types are handled.
854 if(!left_value.check_same_type(r_constant_value))
857 char oper = binary.oper->token[0];
858 char oper2 = binary.oper->token[1];
859 if(oper=='&' || oper=='|' || oper=='^')
861 if(oper2==oper && left_value.check_type<bool>())
862 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
863 else if(!oper2 && left_value.check_type<int>())
864 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
865 else if(!oper2 && left_value.check_type<unsigned>())
866 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
868 else if((oper=='<' || oper=='>') && oper2!=oper)
870 if(left_value.check_type<int>())
871 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
872 else if(left_value.check_type<unsigned>())
873 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
874 else if(left_value.check_type<float>())
875 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
877 else if((oper=='=' || oper=='!') && oper2=='=')
879 if(left_value.check_type<int>())
880 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
881 else if(left_value.check_type<unsigned>())
882 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
883 else if(left_value.check_type<float>())
884 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
886 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
888 if(left_value.check_type<int>())
889 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
890 else if(left_value.check_type<unsigned>())
891 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
892 else if(left_value.check_type<float>())
893 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
895 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
897 if(left_value.check_type<int>())
898 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
899 else if(left_value.check_type<unsigned>())
900 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
904 void ConstantFolder::visit(Assignment &assign)
906 TraversingVisitor::visit(assign);
910 void ConstantFolder::visit(TernaryExpression &ternary)
912 TraversingVisitor::visit(ternary);
916 void ConstantFolder::visit(FunctionCall &call)
918 if(call.constructor && call.type && call.arguments.size()==1)
920 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
923 visit(call.arguments[0]);
924 bool can_fold = r_constant;
929 if(basic->kind==BasicTypeDeclaration::BOOL)
930 convert_to_result<bool>(r_constant_value);
931 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
932 convert_to_result<int>(r_constant_value);
933 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
934 convert_to_result<unsigned>(r_constant_value);
935 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
936 convert_to_result<float>(r_constant_value);
942 TraversingVisitor::visit(call);
946 void ConstantFolder::visit(VariableDeclaration &var)
948 if(iteration_init && var.init_expression)
950 visit(var.init_expression);
953 /* Record the value of a constant initialization expression of an
954 iteration, so it can be used to evaluate the loop condition. */
955 iteration_var = &var;
956 iter_init_value = r_constant_value;
960 TraversingVisitor::visit(var);
963 void ConstantFolder::visit(Iteration &iter)
965 SetForScope<Block *> set_block(current_block, &iter.body);
967 /* The iteration variable is not normally inlined into expressions, so we
968 process it specially here. If the initial value causes the loop condition
969 to evaluate to false, then the expression can be folded. */
971 if(iter.init_statement)
973 SetFlag set_init(iteration_init);
974 iter.init_statement->visit(*this);
979 visit(iter.condition);
980 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
982 RefPtr<Literal> literal = new Literal;
983 literal->token = "false";
984 literal->value = r_constant_value;
985 iter.condition = literal;
990 iter.body.visit(*this);
991 if(iter.loop_expression)
992 visit(iter.loop_expression);
996 void ConstantConditionEliminator::apply(Stage &stage)
998 stage.content.visit(*this);
999 NodeRemover().apply(stage, nodes_to_remove);
1002 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1004 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1005 if(literal->value.check_type<bool>())
1006 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1007 return NOT_CONSTANT;
1010 void ConstantConditionEliminator::visit(Block &block)
1012 SetForScope<Block *> set_block(current_block, &block);
1013 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1020 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1022 r_ternary_result = 0;
1024 if(r_ternary_result)
1025 expr = r_ternary_result;
1026 r_ternary_result = 0;
1029 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1031 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1032 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1034 auto i = current_block->variables.find(var->name);
1035 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1039 TraversingVisitor::visit(unary);
1042 void ConstantConditionEliminator::visit(Assignment &assign)
1044 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1045 if(i==current_block->variables.end())
1046 r_external_side_effects = true;
1047 TraversingVisitor::visit(assign);
1050 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1052 ConstantStatus result = check_constant_condition(*ternary.condition);
1053 if(result!=NOT_CONSTANT)
1054 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1056 r_ternary_result = 0;
1059 void ConstantConditionEliminator::visit(FunctionCall &call)
1061 r_external_side_effects = true;
1062 TraversingVisitor::visit(call);
1065 void ConstantConditionEliminator::visit(Conditional &cond)
1067 ConstantStatus result = check_constant_condition(*cond.condition);
1068 if(result!=NOT_CONSTANT)
1070 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1071 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1072 current_block->body.splice(insert_point, block.body);
1073 nodes_to_remove.insert(&cond);
1077 r_external_side_effects = false;
1078 TraversingVisitor::visit(cond);
1080 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1081 nodes_to_remove.insert(&cond);
1084 void ConstantConditionEliminator::visit(Iteration &iter)
1088 ConstantStatus result = check_constant_condition(*iter.condition);
1089 if(result==CONSTANT_FALSE)
1091 nodes_to_remove.insert(&iter);
1096 r_external_side_effects = false;
1097 TraversingVisitor::visit(iter);
1098 if(iter.body.body.empty() && !r_external_side_effects)
1099 nodes_to_remove.insert(&iter);
1103 bool UnreachableCodeRemover::apply(Stage &stage)
1105 stage.content.visit(*this);
1106 NodeRemover().apply(stage, unreachable_nodes);
1107 return !unreachable_nodes.empty();
1110 void UnreachableCodeRemover::visit(Block &block)
1112 auto i = block.body.begin();
1113 for(; (reachable && i!=block.body.end()); ++i)
1115 for(; i!=block.body.end(); ++i)
1116 unreachable_nodes.insert(i->get());
1119 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1121 TraversingVisitor::visit(func);
1125 void UnreachableCodeRemover::visit(Conditional &cond)
1127 cond.body.visit(*this);
1128 bool reachable_if_true = reachable;
1130 cond.else_body.visit(*this);
1132 reachable |= reachable_if_true;
1135 void UnreachableCodeRemover::visit(Iteration &iter)
1137 TraversingVisitor::visit(iter);
1139 /* Always consider code after a loop reachable, since there's no checking
1140 for whether the loop executes. */
1145 bool UnusedTypeRemover::apply(Stage &stage)
1147 stage.content.visit(*this);
1148 NodeRemover().apply(stage, unused_nodes);
1149 return !unused_nodes.empty();
1152 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1154 unused_nodes.erase(expr->type);
1155 TraversingVisitor::visit(expr);
1158 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1161 unused_nodes.erase(type.base_type);
1162 unused_nodes.insert(&type);
1165 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1168 unused_nodes.erase(type.base_type);
1169 unused_nodes.insert(&type);
1172 void UnusedTypeRemover::visit(StructDeclaration &strct)
1174 unused_nodes.insert(&strct);
1175 TraversingVisitor::visit(strct);
1178 void UnusedTypeRemover::visit(VariableDeclaration &var)
1180 unused_nodes.erase(var.type_declaration);
1181 TraversingVisitor::visit(var);
1184 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1186 unused_nodes.erase(iface.type_declaration);
1189 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1191 unused_nodes.erase(func.return_type_declaration);
1192 TraversingVisitor::visit(func);
1196 bool UnusedVariableRemover::apply(Stage &s)
1199 s.content.visit(*this);
1201 for(const AssignmentInfo &a: assignments)
1202 if(a.used_by.empty())
1203 unused_nodes.insert(a.node);
1205 for(const auto &kvp: variables)
1207 if(kvp.second.output)
1209 /* The last visible assignments of output variables are used by the
1210 next stage or the API. */
1211 for(AssignmentInfo *a: kvp.second.assignments)
1212 unused_nodes.erase(a->node);
1215 if(!kvp.second.output && !kvp.second.referenced)
1217 // Don't remove variables from inside interface blocks.
1218 if(!kvp.second.interface_block)
1219 unused_nodes.insert(kvp.first);
1221 else if(kvp.second.interface_block)
1222 // Interface blocks are kept if even one member is used.
1223 unused_nodes.erase(kvp.second.interface_block);
1226 NodeRemover().apply(s, unused_nodes);
1228 return !unused_nodes.empty();
1231 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1233 VariableInfo &var_info = variables[target.declaration];
1234 var_info.referenced = true;
1235 if(!assignment_target)
1237 bool loop_external = false;
1238 for(AssignmentInfo *a: var_info.assignments)
1240 bool covered = true;
1241 for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1243 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1244 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1245 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1247 unsigned index1 = a->target.chain[j]&0x3F;
1248 unsigned index2 = target.chain[j]&0x3F;
1249 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1250 covered = index1&index2;
1251 else if(type1==Assignment::Target::ARRAY && index1<4)
1252 covered = index2&(1<<index1);
1253 else if(type2==Assignment::Target::ARRAY && index2<4)
1254 covered = index1&(1<<index2);
1255 /* If it's some other combination (shouldn't happen), leave
1259 covered = (a->target.chain[j]==target.chain[j]);
1264 a->used_by.push_back(&node);
1265 if(a->in_loop<in_loop)
1266 loop_external = true;
1271 loop_ext_refs.push_back(&node);
1275 void UnusedVariableRemover::visit(VariableReference &var)
1277 if(composite_reference)
1278 r_reference.declaration = var.declaration;
1280 referenced(var.declaration, var);
1283 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1285 if(composite_reference)
1286 r_reference.declaration = iface.declaration;
1288 referenced(iface.declaration, iface);
1291 void UnusedVariableRemover::visit_composite(Expression &expr)
1293 if(!composite_reference)
1294 r_reference = Assignment::Target();
1296 SetFlag set_composite(composite_reference);
1300 void UnusedVariableRemover::visit(MemberAccess &memacc)
1302 visit_composite(*memacc.left);
1304 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1306 if(!composite_reference && r_reference.declaration)
1307 referenced(r_reference, memacc);
1310 void UnusedVariableRemover::visit(Swizzle &swizzle)
1312 visit_composite(*swizzle.left);
1315 for(unsigned i=0; i<swizzle.count; ++i)
1316 mask |= 1<<swizzle.components[i];
1317 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1319 if(!composite_reference && r_reference.declaration)
1320 referenced(r_reference, swizzle);
1323 void UnusedVariableRemover::visit(UnaryExpression &unary)
1325 TraversingVisitor::visit(unary);
1326 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1327 r_side_effects = true;
1330 void UnusedVariableRemover::visit(BinaryExpression &binary)
1332 if(binary.oper->token[0]=='[')
1334 visit_composite(*binary.left);
1337 SetFlag clear_assignment(assignment_target, false);
1338 SetFlag clear_composite(composite_reference, false);
1339 binary.right->visit(*this);
1342 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1344 if(!composite_reference && r_reference.declaration)
1345 referenced(r_reference, binary);
1349 SetFlag clear_composite(composite_reference, false);
1350 TraversingVisitor::visit(binary);
1354 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1356 SetFlag clear_composite(composite_reference, false);
1357 TraversingVisitor::visit(ternary);
1360 void UnusedVariableRemover::visit(Assignment &assign)
1363 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1364 assign.left->visit(*this);
1366 assign.right->visit(*this);
1367 r_assignment = &assign;
1368 r_side_effects = true;
1371 void UnusedVariableRemover::visit(FunctionCall &call)
1373 SetFlag clear_composite(composite_reference, false);
1374 TraversingVisitor::visit(call);
1375 /* Treat function calls as having side effects so expression statements
1376 consisting of nothing but a function call won't be optimized away. */
1377 r_side_effects = true;
1379 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1381 for(const auto &kvp: variables)
1382 if(kvp.second.output)
1383 referenced(kvp.first, call);
1387 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1389 assignments.push_back(AssignmentInfo());
1390 AssignmentInfo &assign_info = assignments.back();
1391 assign_info.node = &node;
1392 assign_info.target = target;
1393 assign_info.in_loop = in_loop;
1395 /* An assignment to the target hides any assignments to the same target or
1397 VariableInfo &var_info = variables[target.declaration];
1398 for(unsigned i=0; i<var_info.assignments.size(); )
1400 const Assignment::Target &t = var_info.assignments[i]->target;
1402 bool subfield = (t.chain_len>=target.chain_len);
1403 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1404 subfield = (t.chain[j]==target.chain[j]);
1407 var_info.assignments.erase(var_info.assignments.begin()+i);
1412 var_info.assignments.push_back(&assign_info);
1415 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1418 r_side_effects = false;
1419 TraversingVisitor::visit(expr);
1420 if(r_assignment && r_assignment->target.declaration)
1421 record_assignment(r_assignment->target, expr);
1423 unused_nodes.insert(&expr);
1426 void UnusedVariableRemover::visit(StructDeclaration &strct)
1428 SetFlag set_struct(in_struct);
1429 TraversingVisitor::visit(strct);
1432 void UnusedVariableRemover::visit(VariableDeclaration &var)
1434 TraversingVisitor::visit(var);
1439 VariableInfo &var_info = variables[&var];
1440 var_info.interface_block = interface_block;
1442 /* Mark variables as output if they're used by the next stage or the
1445 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1447 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1449 if(var.init_expression)
1451 var_info.initialized = true;
1452 record_assignment(&var, *var.init_expression);
1456 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1458 VariableInfo &var_info = variables[&iface];
1459 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1462 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1464 for(const auto &kvp: other_vars)
1466 auto j = variables.find(kvp.first);
1467 if(j!=variables.end())
1469 /* The merged blocks started as copies of each other so any common
1470 assignments must be in the beginning. */
1472 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1473 if(kvp.second.assignments[k]!=j->second.assignments[k])
1476 // Remaining assignments are unique to each block; merge them.
1477 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1478 j->second.referenced |= kvp.second.referenced;
1481 variables.insert(kvp);
1485 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1487 if(func.body.body.empty())
1490 BlockVariableMap saved_vars = variables;
1491 // Assignments from other functions should not be visible.
1492 for(auto &kvp: variables)
1493 kvp.second.assignments.resize(kvp.second.initialized);
1494 TraversingVisitor::visit(func);
1495 swap(variables, saved_vars);
1496 merge_variables(saved_vars);
1498 /* Always treat function parameters as referenced. Removing unused
1499 parameters is not currently supported. */
1500 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1502 auto j = variables.find(p.get());
1503 if(j!=variables.end())
1504 j->second.referenced = true;
1508 void UnusedVariableRemover::visit(Conditional &cond)
1510 cond.condition->visit(*this);
1511 BlockVariableMap saved_vars = variables;
1512 cond.body.visit(*this);
1513 swap(saved_vars, variables);
1514 cond.else_body.visit(*this);
1516 /* Visible assignments after the conditional is the union of those visible
1517 at the end of the if and else blocks. If there was no else block, then it's
1518 the union of the if block and the state before it. */
1519 merge_variables(saved_vars);
1522 void UnusedVariableRemover::visit(Iteration &iter)
1524 BlockVariableMap saved_vars = variables;
1525 vector<Node *> saved_refs;
1526 swap(loop_ext_refs, saved_refs);
1528 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1529 TraversingVisitor::visit(iter);
1531 swap(loop_ext_refs, saved_refs);
1533 /* Visit the external references of the loop again to record assignments
1534 done in the loop as used. */
1535 for(Node *n: saved_refs)
1538 /* Merge assignments from the iteration, without clearing previous state.
1539 Further analysis is needed to determine which parts of the iteration body
1540 are always executed, if any. */
1541 merge_variables(saved_vars);
1545 bool UnusedFunctionRemover::apply(Stage &stage)
1547 stage.content.visit(*this);
1548 NodeRemover().apply(stage, unused_nodes);
1549 return !unused_nodes.empty();
1552 void UnusedFunctionRemover::visit(FunctionCall &call)
1554 TraversingVisitor::visit(call);
1556 unused_nodes.erase(call.declaration);
1557 if(call.declaration && call.declaration->definition!=call.declaration)
1558 used_definitions.insert(call.declaration->definition);
1561 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1563 TraversingVisitor::visit(func);
1565 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1566 unused_nodes.insert(&func);