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. Only consider
118 names which declared in blocks linearly related to the target block. */
120 tgt_blk.visit(*this);
121 for(const Block *b=&tgt_blk; b; b=b->parent)
122 for(const auto &kvp: b->variables)
123 referenced_names.insert(kvp.first);
125 /* Inline and rename passes must be interleaved so used variable names are
126 known when inlining the return statement. */
128 staging_block.parent = &tgt_blk;
129 staging_block.variables.clear();
131 vector<RefPtr<VariableDeclaration> > params;
132 params.reserve(source_func->parameters.size());
133 for(const RefPtr<VariableDeclaration> &p: source_func->parameters)
135 RefPtr<VariableDeclaration> var = p->clone();
136 var->interface.clear();
138 SetForScope<Pass> set_pass(pass, RENAME);
141 staging_block.body.push_back_nocopy(var);
142 params.push_back(var);
145 for(const RefPtr<Statement> &s: source_func->body.body)
147 r_inlined_statement = 0;
149 if(!r_inlined_statement)
150 r_inlined_statement = s->clone();
152 SetForScope<Pass> set_pass(pass, RENAME);
153 r_inlined_statement->visit(*this);
155 staging_block.body.push_back_nocopy(r_inlined_statement);
158 /* Now collect names from the staging block. Local variables that would
159 have conflicted with the target function were renamed earlier. */
161 referenced_names.clear();
162 staging_block.variables.clear();
163 staging_block.visit(*this);
165 /* Rename variables in the target function so they don't interfere with
166 global identifiers used by the source function. */
168 staging_block.parent = source_func->body.parent;
169 target_func.visit(*this);
171 // Put the argument expressions in place after all renaming has been done.
172 for(unsigned i=0; i<source_func->parameters.size(); ++i)
173 params[i]->init_expression = call.arguments[i]->clone();
175 tgt_blk.body.splice(ins_pt, staging_block.body);
177 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
179 return r_result_name;
182 void InlineContentInjector::visit(VariableReference &var)
186 auto i = staging_block.variables.find(var.name);
187 if(i!=staging_block.variables.end())
188 var.name = i->second->name;
190 else if(pass==REFERENCED)
191 referenced_names.insert(var.name);
194 void InlineContentInjector::visit(FunctionCall &call)
197 referenced_names.insert(call.name);
198 TraversingVisitor::visit(call);
201 void InlineContentInjector::visit(VariableDeclaration &var)
203 TraversingVisitor::visit(var);
207 /* Check against conflicts with the other context as well as variables
208 already renamed here. */
209 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
210 staging_block.variables[var.name] = &var;
213 string mapped_name = get_unused_variable_name(staging_block, var.name);
214 if(mapped_name!=var.name)
216 staging_block.variables[mapped_name] = &var;
217 var.name = mapped_name;
221 else if(pass==REFERENCED)
222 referenced_names.insert(var.type);
225 void InlineContentInjector::visit(Return &ret)
227 TraversingVisitor::visit(ret);
229 if(pass==INLINE && ret.expression)
231 // Create a new variable to hold the return value of the inlined function.
232 r_result_name = get_unused_variable_name(staging_block, "_return");
233 RefPtr<VariableDeclaration> var = new VariableDeclaration;
234 var->source = ret.source;
235 var->line = ret.line;
236 var->type = source_func->return_type;
237 var->name = r_result_name;
238 var->init_expression = ret.expression->clone();
239 r_inlined_statement = var;
244 bool FunctionInliner::apply(Stage &s)
247 inlineable = InlineableFunctionLocator().apply(s);
248 r_any_inlined = false;
249 s.content.visit(*this);
250 return r_any_inlined;
253 void FunctionInliner::visit(RefPtr<Expression> &ptr)
259 ptr = r_inline_result;
260 r_any_inlined = true;
265 void FunctionInliner::visit(Block &block)
267 SetForScope<Block *> set_block(current_block, &block);
268 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
269 for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
276 void FunctionInliner::visit(FunctionCall &call)
278 for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
284 FunctionDeclaration *def = call.declaration;
286 def = def->definition;
288 if(def && inlineable.count(def))
290 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
292 // This will later get removed by UnusedVariableRemover.
293 if(result_name.empty())
294 result_name = "_msp_unused_from_inline";
296 RefPtr<VariableReference> ref = new VariableReference;
297 ref->name = result_name;
298 r_inline_result = ref;
300 /* Inlined variables need to be resolved before this function can be
302 inlineable.erase(current_function);
303 r_inlined_here = true;
307 void FunctionInliner::visit(FunctionDeclaration &func)
309 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
310 TraversingVisitor::visit(func);
311 r_inlined_here = false;
314 void FunctionInliner::visit(Iteration &iter)
316 /* Visit the initialization statement before entering the loop body so the
317 inlined statements get inserted outside. */
318 if(iter.init_statement)
319 iter.init_statement->visit(*this);
321 SetForScope<Block *> set_block(current_block, &iter.body);
322 /* Skip the condition and loop expression parts because they're not properly
323 inside the body block. Inlining anything into them will require a more
324 comprehensive transformation. */
325 iter.body.visit(*this);
329 bool ExpressionInliner::apply(Stage &s)
331 s.content.visit(*this);
333 bool any_inlined = false;
334 for(ExpressionInfo &e: expressions)
335 if(e.expression && (e.trivial || e.uses.size()==1))
337 for(ExpressionUse &u: e.uses)
340 *u.reference = e.expression->clone();
348 void ExpressionInliner::visit(RefPtr<Expression> &expr)
352 if(r_ref_info && r_ref_info->expression)
355 use.reference = &expr;
356 use.ref_scope = current_block;
357 use.blocked = access_write || r_ref_info->blocked;
359 if(iteration_body && !r_ref_info->trivial)
361 /* Block inlining of non-trivial expressions assigned outside an
362 iteration statement. The iteration may run multiple times, which
363 would cause the expression to also be evaluated multiple times. */
364 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
365 use.blocked = (i==r_ref_info->assign_scope);
368 /* Block inlining assignments from from inner scopes. The assignment may
369 depend on local variables of that scope or may not always be executed. */
370 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
371 use.blocked = (i==current_block);
373 r_ref_info->uses.push_back(use);
379 void ExpressionInliner::visit(VariableReference &var)
381 if(var.declaration && access_read)
383 auto i = assignments.find(var.declaration);
384 if(i!=assignments.end())
385 r_ref_info = i->second;
389 void ExpressionInliner::visit(MemberAccess &memacc)
395 void ExpressionInliner::visit(Swizzle &swizzle)
401 void ExpressionInliner::visit(UnaryExpression &unary)
403 SetFlag set_write(access_write, (unary.oper->token[1]=='+' || unary.oper->token[1]=='-'));
404 visit(unary.expression);
408 void ExpressionInliner::visit(BinaryExpression &binary)
412 SetFlag clear_write(access_write, false);
418 void ExpressionInliner::visit(Assignment &assign)
421 SetFlag set_read(access_read, assign.oper->token[0]!='=');
422 SetFlag set_write(access_write);
429 auto i = assignments.find(assign.target.declaration);
430 if(i!=assignments.end())
432 if(iteration_body && i->second && i->second->expression)
434 /* Block inlining into previous references within the iteration
435 statement. On iterations after the first they would refer to the
436 assignment within the iteration. */
437 for(ExpressionUse &u: i->second->uses)
438 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
439 u.blocked = (k==iteration_body);
442 for(; (i!=assignments.end() && i->first.declaration==assign.target.declaration); ++i)
443 if(targets_overlap(i->first, assign.target))
444 i->second->blocked = true;
446 expressions.emplace_back();
447 ExpressionInfo &info = expressions.back();
448 info.target = assign.target;
449 // Self-referencing assignments can't be inlined without additional work.
450 if(!assign.self_referencing)
451 info.expression = assign.right;
452 info.assign_scope = current_block;
453 info.trivial = r_trivial;
455 assignments[assign.target] = &info;
461 void ExpressionInliner::visit(TernaryExpression &ternary)
463 visit(ternary.condition);
464 visit(ternary.true_expr);
465 visit(ternary.false_expr);
469 void ExpressionInliner::visit(FunctionCall &call)
471 TraversingVisitor::visit(call);
475 void ExpressionInliner::visit(VariableDeclaration &var)
479 TraversingVisitor::visit(var);
481 bool constant = var.constant;
482 if(constant && var.layout)
484 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
485 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
488 /* Only inline global variables if they're constant and have trivial
489 initializers. Non-constant variables could change in ways which are hard to
490 analyze and non-trivial expressions could be expensive to inline. */
491 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
493 expressions.emplace_back();
494 ExpressionInfo &info = expressions.back();
496 /* Assume variables declared in an iteration initialization statement
497 will have their values change throughout the iteration. */
499 info.expression = var.init_expression;
500 info.assign_scope = current_block;
501 info.trivial = r_trivial;
503 assignments[&var] = &info;
507 void ExpressionInliner::visit(Iteration &iter)
509 SetForScope<Block *> set_block(current_block, &iter.body);
510 if(iter.init_statement)
512 SetFlag set_init(iteration_init);
513 iter.init_statement->visit(*this);
516 SetForScope<Block *> set_body(iteration_body, &iter.body);
518 visit(iter.condition);
519 iter.body.visit(*this);
520 if(iter.loop_expression)
521 visit(iter.loop_expression);
525 bool AggregateDismantler::apply(Stage &stage)
527 stage.content.visit(*this);
529 bool any_dismantled = false;
530 for(const auto &kvp: aggregates)
532 if(kvp.second.referenced || !kvp.second.members_referenced)
535 for(const AggregateMember &m: kvp.second.members)
539 name = format("%s_%s", kvp.second.declaration->name, m.declaration->name);
541 name = format("%s_%d", kvp.second.declaration->name, m.index);
543 VariableDeclaration *var = new VariableDeclaration;
544 var->source = kvp.first->source;
545 var->line = kvp.first->line;
546 var->name = get_unused_variable_name(*kvp.second.decl_scope, name);
547 /* XXX This is kind of brittle and depends on the array declaration's
548 textual type not having brackets in it. */
549 var->type = (m.declaration ? m.declaration : kvp.second.declaration)->type;
551 var->init_expression = m.initializer->clone();
553 kvp.second.decl_scope->body.insert(kvp.second.insert_point, var);
555 for(RefPtr<Expression> *r: m.references)
557 VariableReference *ref = new VariableReference;
558 ref->name = var->name;
562 any_dismantled = true;
566 return any_dismantled;
569 void AggregateDismantler::visit(Block &block)
571 SetForScope<Block *> set_block(current_block, &block);
572 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
579 void AggregateDismantler::visit(RefPtr<Expression> &expr)
583 if(r_aggregate_ref && r_reference.chain_len==1)
585 if((r_reference.chain[0]&0x3F)!=0x3F)
587 r_aggregate_ref->members[r_reference.chain[0]&0x3F].references.push_back(&expr);
588 r_aggregate_ref->members_referenced = true;
591 /* If the accessed member is not known, mark the entire aggregate as
593 r_aggregate_ref->referenced = true;
598 void AggregateDismantler::visit(VariableReference &var)
600 if(composite_reference)
601 r_reference.declaration = var.declaration;
604 /* If an aggregate variable is referenced as a whole, it should not be
606 auto i = aggregates.find(var.declaration);
607 if(i!=aggregates.end())
608 i->second.referenced = true;
612 void AggregateDismantler::visit_composite(RefPtr<Expression> &expr)
614 if(!composite_reference)
615 r_reference = Assignment::Target();
617 SetFlag set_composite(composite_reference);
621 void AggregateDismantler::visit(MemberAccess &memacc)
623 visit_composite(memacc.left);
625 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
627 if(r_reference.declaration && r_reference.chain_len==1)
629 auto i = aggregates.find(r_reference.declaration);
630 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
636 void AggregateDismantler::visit(BinaryExpression &binary)
638 if(binary.oper->token[0]=='[')
640 visit_composite(binary.left);
642 SetFlag clear_composite(composite_reference, false);
646 unsigned index = 0x3F;
647 if(Literal *literal_subscript = dynamic_cast<Literal *>(binary.right.get()))
648 if(literal_subscript->value.check_type<int>())
649 index = literal_subscript->value.value<int>();
650 add_to_chain(r_reference, Assignment::Target::ARRAY, index);
652 if(r_reference.declaration && r_reference.chain_len==1)
654 auto i = aggregates.find(r_reference.declaration);
655 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
662 SetFlag clear_composite(composite_reference, false);
663 TraversingVisitor::visit(binary);
667 void AggregateDismantler::visit(VariableDeclaration &var)
669 TraversingVisitor::visit(var);
671 if(var.interface.empty())
673 if(const StructDeclaration *strct = dynamic_cast<const StructDeclaration *>(var.type_declaration))
675 const FunctionCall *init_call = dynamic_cast<const FunctionCall *>(var.init_expression.get());
676 if((init_call && init_call->constructor) || !var.init_expression)
679 Aggregate &aggre = aggregates[&var];
680 aggre.declaration = &var;
681 aggre.decl_scope = current_block;
682 aggre.insert_point = insert_point;
685 for(const RefPtr<Statement> &s: strct->members.body)
687 if(const VariableDeclaration *mem_decl = dynamic_cast<const VariableDeclaration *>(s.get()))
689 AggregateMember member;
690 member.declaration = mem_decl;
693 member.initializer = init_call->arguments[i];
694 aggre.members.push_back(member);
700 else if(const Literal *literal_size = dynamic_cast<const Literal *>(var.array_size.get()))
702 if(literal_size->value.check_type<int>())
704 Aggregate &aggre = aggregates[&var];
705 aggre.declaration = &var;
706 aggre.decl_scope = current_block;
707 aggre.insert_point = insert_point;
709 int size = literal_size->value.value<int>();
710 for(int i=0; i<size; ++i)
712 AggregateMember member;
714 // Array initializers are not supported yet
715 aggre.members.push_back(member);
722 void AggregateDismantler::visit(FunctionDeclaration &func)
724 func.body.visit(*this);
729 T ConstantFolder::evaluate_logical(char oper, T left, T right)
733 case '&': return left&right;
734 case '|': return left|right;
735 case '^': return left^right;
741 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
743 switch(oper[0]|oper[1])
745 case '<': return left<right;
746 case '<'|'=': return left<=right;
747 case '>': return left>right;
748 case '>'|'=': return left>=right;
749 default: return false;
754 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
758 case '+': return left+right;
759 case '-': return left-right;
760 case '*': return left*right;
761 case '/': return left/right;
767 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
771 case '%': return left%right;
772 case '<': return left<<right;
773 case '>': return left>>right;
779 void ConstantFolder::convert_to_result(const Variant &value)
781 if(value.check_type<bool>())
782 set_result(static_cast<T>(value.value<bool>()));
783 else if(value.check_type<int>())
784 set_result(static_cast<T>(value.value<int>()));
785 else if(value.check_type<unsigned>())
786 set_result(static_cast<T>(value.value<unsigned>()));
787 else if(value.check_type<float>())
788 set_result(static_cast<T>(value.value<float>()));
791 void ConstantFolder::set_result(const Variant &value, bool literal)
793 r_constant_value = value;
798 void ConstantFolder::visit(RefPtr<Expression> &expr)
800 r_constant_value = Variant();
803 r_uses_iter_var = false;
805 /* Don't replace literals since they'd only be replaced with an identical
806 literal. Also skip anything that uses an iteration variable, but pass on
807 the result so the Iteration visiting function can handle it. */
808 if(!r_constant || r_literal || r_uses_iter_var)
811 RefPtr<Literal> literal = new Literal;
812 if(r_constant_value.check_type<bool>())
813 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
814 else if(r_constant_value.check_type<int>())
815 literal->token = lexical_cast<string>(r_constant_value.value<int>());
816 else if(r_constant_value.check_type<unsigned>())
817 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
818 else if(r_constant_value.check_type<float>())
820 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
821 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
822 literal->token += ".0";
829 literal->value = r_constant_value;
834 void ConstantFolder::visit(Literal &literal)
836 set_result(literal.value, true);
839 void ConstantFolder::visit(VariableReference &var)
841 /* If an iteration variable is initialized with a constant value, return
842 that value here for the purpose of evaluating the loop condition for the
844 if(var.declaration==iteration_var)
846 set_result(iter_init_value);
847 r_uses_iter_var = true;
851 void ConstantFolder::visit(MemberAccess &memacc)
853 TraversingVisitor::visit(memacc);
857 void ConstantFolder::visit(Swizzle &swizzle)
859 TraversingVisitor::visit(swizzle);
863 void ConstantFolder::visit(UnaryExpression &unary)
865 TraversingVisitor::visit(unary);
866 bool can_fold = r_constant;
871 char oper = unary.oper->token[0];
872 char oper2 = unary.oper->token[1];
875 if(r_constant_value.check_type<bool>())
876 set_result(!r_constant_value.value<bool>());
880 if(r_constant_value.check_type<int>())
881 set_result(~r_constant_value.value<int>());
882 else if(r_constant_value.check_type<unsigned>())
883 set_result(~r_constant_value.value<unsigned>());
885 else if(oper=='-' && !oper2)
887 if(r_constant_value.check_type<int>())
888 set_result(-r_constant_value.value<int>());
889 else if(r_constant_value.check_type<unsigned>())
890 set_result(-r_constant_value.value<unsigned>());
891 else if(r_constant_value.check_type<float>())
892 set_result(-r_constant_value.value<float>());
896 void ConstantFolder::visit(BinaryExpression &binary)
899 bool left_constant = r_constant;
900 bool left_iter_var = r_uses_iter_var;
901 Variant left_value = r_constant_value;
904 r_uses_iter_var = true;
906 bool can_fold = (left_constant && r_constant);
911 // Currently only expressions with both sides of equal types are handled.
912 if(!left_value.check_same_type(r_constant_value))
915 char oper = binary.oper->token[0];
916 char oper2 = binary.oper->token[1];
917 if(oper=='&' || oper=='|' || oper=='^')
919 if(oper2==oper && left_value.check_type<bool>())
920 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
921 else if(!oper2 && left_value.check_type<int>())
922 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
923 else if(!oper2 && left_value.check_type<unsigned>())
924 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
926 else if((oper=='<' || oper=='>') && oper2!=oper)
928 if(left_value.check_type<int>())
929 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
930 else if(left_value.check_type<unsigned>())
931 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
932 else if(left_value.check_type<float>())
933 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
935 else if((oper=='=' || oper=='!') && oper2=='=')
937 if(left_value.check_type<int>())
938 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
939 else if(left_value.check_type<unsigned>())
940 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
941 else if(left_value.check_type<float>())
942 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
944 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
946 if(left_value.check_type<int>())
947 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
948 else if(left_value.check_type<unsigned>())
949 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
950 else if(left_value.check_type<float>())
951 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
953 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
955 if(left_value.check_type<int>())
956 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
957 else if(left_value.check_type<unsigned>())
958 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
962 void ConstantFolder::visit(Assignment &assign)
964 TraversingVisitor::visit(assign);
968 void ConstantFolder::visit(TernaryExpression &ternary)
970 TraversingVisitor::visit(ternary);
974 void ConstantFolder::visit(FunctionCall &call)
976 if(call.constructor && call.type && call.arguments.size()==1)
978 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
981 visit(call.arguments[0]);
982 bool can_fold = r_constant;
987 if(basic->kind==BasicTypeDeclaration::BOOL)
988 convert_to_result<bool>(r_constant_value);
989 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
990 convert_to_result<int>(r_constant_value);
991 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
992 convert_to_result<unsigned>(r_constant_value);
993 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
994 convert_to_result<float>(r_constant_value);
1000 TraversingVisitor::visit(call);
1004 void ConstantFolder::visit(VariableDeclaration &var)
1006 if(iteration_init && var.init_expression)
1008 visit(var.init_expression);
1011 /* Record the value of a constant initialization expression of an
1012 iteration, so it can be used to evaluate the loop condition. */
1013 iteration_var = &var;
1014 iter_init_value = r_constant_value;
1018 TraversingVisitor::visit(var);
1021 void ConstantFolder::visit(Iteration &iter)
1023 SetForScope<Block *> set_block(current_block, &iter.body);
1025 /* The iteration variable is not normally inlined into expressions, so we
1026 process it specially here. If the initial value causes the loop condition
1027 to evaluate to false, then the expression can be folded. */
1029 if(iter.init_statement)
1031 SetFlag set_init(iteration_init);
1032 iter.init_statement->visit(*this);
1037 visit(iter.condition);
1038 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1040 RefPtr<Literal> literal = new Literal;
1041 literal->token = "false";
1042 literal->value = r_constant_value;
1043 iter.condition = literal;
1048 iter.body.visit(*this);
1049 if(iter.loop_expression)
1050 visit(iter.loop_expression);
1054 bool ConstantConditionEliminator::apply(Stage &stage)
1056 stage.content.visit(*this);
1057 NodeRemover().apply(stage, nodes_to_remove);
1058 return !nodes_to_remove.empty();
1061 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1063 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1064 if(literal->value.check_type<bool>())
1065 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1066 return NOT_CONSTANT;
1069 void ConstantConditionEliminator::visit(Block &block)
1071 SetForScope<Block *> set_block(current_block, &block);
1072 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1079 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1081 r_ternary_result = 0;
1083 if(r_ternary_result)
1084 expr = r_ternary_result;
1085 r_ternary_result = 0;
1088 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1090 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1091 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1093 auto i = current_block->variables.find(var->name);
1094 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1098 TraversingVisitor::visit(unary);
1101 void ConstantConditionEliminator::visit(Assignment &assign)
1103 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1104 if(i==current_block->variables.end())
1105 r_external_side_effects = true;
1106 TraversingVisitor::visit(assign);
1109 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1111 ConstantStatus result = check_constant_condition(*ternary.condition);
1112 if(result!=NOT_CONSTANT)
1113 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1115 r_ternary_result = 0;
1118 void ConstantConditionEliminator::visit(FunctionCall &call)
1120 r_external_side_effects = true;
1121 TraversingVisitor::visit(call);
1124 void ConstantConditionEliminator::visit(Conditional &cond)
1126 ConstantStatus result = check_constant_condition(*cond.condition);
1127 if(result!=NOT_CONSTANT)
1129 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1130 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1131 current_block->body.splice(insert_point, block.body);
1132 nodes_to_remove.insert(&cond);
1136 r_external_side_effects = false;
1137 TraversingVisitor::visit(cond);
1139 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1140 nodes_to_remove.insert(&cond);
1143 void ConstantConditionEliminator::visit(Iteration &iter)
1147 ConstantStatus result = check_constant_condition(*iter.condition);
1148 if(result==CONSTANT_FALSE)
1150 nodes_to_remove.insert(&iter);
1155 r_external_side_effects = false;
1156 TraversingVisitor::visit(iter);
1157 if(iter.body.body.empty() && !r_external_side_effects)
1158 nodes_to_remove.insert(&iter);
1162 bool UnreachableCodeRemover::apply(Stage &stage)
1164 stage.content.visit(*this);
1165 NodeRemover().apply(stage, unreachable_nodes);
1166 return !unreachable_nodes.empty();
1169 void UnreachableCodeRemover::visit(Block &block)
1171 auto i = block.body.begin();
1172 for(; (reachable && i!=block.body.end()); ++i)
1174 for(; i!=block.body.end(); ++i)
1175 unreachable_nodes.insert(i->get());
1178 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1180 TraversingVisitor::visit(func);
1184 void UnreachableCodeRemover::visit(Conditional &cond)
1186 cond.body.visit(*this);
1187 bool reachable_if_true = reachable;
1189 cond.else_body.visit(*this);
1191 reachable |= reachable_if_true;
1194 void UnreachableCodeRemover::visit(Iteration &iter)
1196 TraversingVisitor::visit(iter);
1198 /* Always consider code after a loop reachable, since there's no checking
1199 for whether the loop executes. */
1204 bool UnusedTypeRemover::apply(Stage &stage)
1206 stage.content.visit(*this);
1207 NodeRemover().apply(stage, unused_nodes);
1208 return !unused_nodes.empty();
1211 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1213 unused_nodes.erase(expr->type);
1214 TraversingVisitor::visit(expr);
1217 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1220 unused_nodes.erase(type.base_type);
1221 unused_nodes.insert(&type);
1224 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1227 unused_nodes.erase(type.base_type);
1228 unused_nodes.insert(&type);
1231 void UnusedTypeRemover::visit(StructDeclaration &strct)
1233 unused_nodes.insert(&strct);
1234 TraversingVisitor::visit(strct);
1237 void UnusedTypeRemover::visit(VariableDeclaration &var)
1239 unused_nodes.erase(var.type_declaration);
1240 TraversingVisitor::visit(var);
1243 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1245 unused_nodes.erase(func.return_type_declaration);
1246 TraversingVisitor::visit(func);
1250 bool UnusedVariableRemover::apply(Stage &s)
1253 s.content.visit(*this);
1255 for(const AssignmentInfo &a: assignments)
1256 if(a.used_by.empty())
1257 unused_nodes.insert(a.node);
1259 for(const auto &kvp: variables)
1261 if(!kvp.second.referenced)
1262 unused_nodes.insert(kvp.first);
1263 else if(kvp.second.output)
1265 /* The last visible assignments of output variables are used by the
1266 next stage or the API. */
1267 for(AssignmentInfo *a: kvp.second.assignments)
1268 unused_nodes.erase(a->node);
1272 NodeRemover().apply(s, unused_nodes);
1274 return !unused_nodes.empty();
1277 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1279 VariableInfo &var_info = variables[target.declaration];
1280 var_info.referenced = true;
1281 if(!assignment_target)
1283 bool loop_external = false;
1284 for(AssignmentInfo *a: var_info.assignments)
1285 if(targets_overlap(a->target, target))
1287 a->used_by.push_back(&node);
1288 if(a->in_loop<in_loop)
1289 loop_external = true;
1293 loop_ext_refs.push_back(&node);
1297 void UnusedVariableRemover::visit(VariableReference &var)
1299 if(composite_reference)
1300 r_reference.declaration = var.declaration;
1301 else if(var.declaration)
1302 referenced(var.declaration, var);
1305 void UnusedVariableRemover::visit_composite(Expression &expr)
1307 if(!composite_reference)
1308 r_reference = Assignment::Target();
1310 SetFlag set_composite(composite_reference);
1314 void UnusedVariableRemover::visit(MemberAccess &memacc)
1316 visit_composite(*memacc.left);
1318 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1320 if(!composite_reference && r_reference.declaration)
1321 referenced(r_reference, memacc);
1324 void UnusedVariableRemover::visit(Swizzle &swizzle)
1326 visit_composite(*swizzle.left);
1329 for(unsigned i=0; i<swizzle.count; ++i)
1330 mask |= 1<<swizzle.components[i];
1331 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1333 if(!composite_reference && r_reference.declaration)
1334 referenced(r_reference, swizzle);
1337 void UnusedVariableRemover::visit(UnaryExpression &unary)
1339 TraversingVisitor::visit(unary);
1340 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1341 r_side_effects = true;
1344 void UnusedVariableRemover::visit(BinaryExpression &binary)
1346 if(binary.oper->token[0]=='[')
1348 visit_composite(*binary.left);
1351 SetFlag clear_assignment(assignment_target, false);
1352 SetFlag clear_composite(composite_reference, false);
1353 SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1354 binary.right->visit(*this);
1357 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1359 if(!composite_reference && r_reference.declaration)
1360 referenced(r_reference, binary);
1364 SetFlag clear_composite(composite_reference, false);
1365 TraversingVisitor::visit(binary);
1369 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1371 SetFlag clear_composite(composite_reference, false);
1372 TraversingVisitor::visit(ternary);
1375 void UnusedVariableRemover::visit(Assignment &assign)
1378 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1379 assign.left->visit(*this);
1381 assign.right->visit(*this);
1382 r_assignment = &assign;
1383 r_side_effects = true;
1386 void UnusedVariableRemover::visit(FunctionCall &call)
1388 SetFlag clear_composite(composite_reference, false);
1389 TraversingVisitor::visit(call);
1390 /* Treat function calls as having side effects so expression statements
1391 consisting of nothing but a function call won't be optimized away. */
1392 r_side_effects = true;
1394 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1396 for(const auto &kvp: variables)
1397 if(kvp.second.output)
1398 referenced(kvp.first, call);
1402 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1404 assignments.emplace_back();
1405 AssignmentInfo &assign_info = assignments.back();
1406 assign_info.node = &node;
1407 assign_info.target = target;
1408 assign_info.in_loop = in_loop;
1410 /* An assignment to the target hides any assignments to the same target or
1412 VariableInfo &var_info = variables[target.declaration];
1413 for(unsigned i=0; i<var_info.assignments.size(); )
1415 const Assignment::Target &t = var_info.assignments[i]->target;
1417 bool subfield = (t.chain_len>=target.chain_len);
1418 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1419 subfield = (t.chain[j]==target.chain[j]);
1422 var_info.assignments.erase(var_info.assignments.begin()+i);
1427 var_info.assignments.push_back(&assign_info);
1430 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1433 r_side_effects = false;
1434 TraversingVisitor::visit(expr);
1435 if(r_assignment && r_assignment->target.declaration)
1436 record_assignment(r_assignment->target, expr);
1438 unused_nodes.insert(&expr);
1441 void UnusedVariableRemover::visit(StructDeclaration &strct)
1443 SetFlag set_struct(in_struct);
1444 TraversingVisitor::visit(strct);
1447 void UnusedVariableRemover::visit(VariableDeclaration &var)
1449 TraversingVisitor::visit(var);
1454 VariableInfo &var_info = variables[&var];
1456 /* Mark variables as output if they're used by the next stage or the
1458 bool builtin = (!var.name.compare(0, 3, "gl_") || (var.block_declaration && !var.block_declaration->block_name.compare(0, 3, "gl_")));
1459 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || builtin));
1461 // Linked outputs are automatically referenced.
1462 if(var_info.output && var.linked_declaration)
1463 var_info.referenced = true;
1465 if(var.init_expression)
1467 var_info.initialized = true;
1468 record_assignment(&var, *var.init_expression);
1472 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1474 for(const auto &kvp: other_vars)
1476 auto j = variables.find(kvp.first);
1477 if(j!=variables.end())
1479 /* The merged blocks started as copies of each other so any common
1480 assignments must be in the beginning. */
1482 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1483 if(kvp.second.assignments[k]!=j->second.assignments[k])
1486 // Remaining assignments are unique to each block; merge them.
1487 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1488 j->second.referenced |= kvp.second.referenced;
1491 variables.insert(kvp);
1495 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1497 if(func.body.body.empty())
1500 BlockVariableMap saved_vars = variables;
1501 // Assignments from other functions should not be visible.
1502 for(auto &kvp: variables)
1503 kvp.second.assignments.resize(kvp.second.initialized);
1504 TraversingVisitor::visit(func);
1505 swap(variables, saved_vars);
1506 merge_variables(saved_vars);
1508 /* Always treat function parameters as referenced. Removing unused
1509 parameters is not currently supported. */
1510 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1512 auto j = variables.find(p.get());
1513 if(j!=variables.end())
1514 j->second.referenced = true;
1518 void UnusedVariableRemover::visit(Conditional &cond)
1520 cond.condition->visit(*this);
1521 BlockVariableMap saved_vars = variables;
1522 cond.body.visit(*this);
1523 swap(saved_vars, variables);
1524 cond.else_body.visit(*this);
1526 /* Visible assignments after the conditional is the union of those visible
1527 at the end of the if and else blocks. If there was no else block, then it's
1528 the union of the if block and the state before it. */
1529 merge_variables(saved_vars);
1532 void UnusedVariableRemover::visit(Iteration &iter)
1534 BlockVariableMap saved_vars = variables;
1535 vector<Node *> saved_refs;
1536 swap(loop_ext_refs, saved_refs);
1538 if(iter.init_statement)
1539 iter.init_statement->visit(*this);
1540 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1542 iter.condition->visit(*this);
1543 iter.body.visit(*this);
1544 if(iter.loop_expression)
1545 iter.loop_expression->visit(*this);
1547 swap(loop_ext_refs, saved_refs);
1549 /* Visit the external references of the loop again to record assignments
1550 done in the loop as used. */
1551 for(Node *n: saved_refs)
1554 /* Merge assignments from the iteration, without clearing previous state.
1555 Further analysis is needed to determine which parts of the iteration body
1556 are always executed, if any. */
1557 merge_variables(saved_vars);
1561 bool UnusedFunctionRemover::apply(Stage &stage)
1563 stage.content.visit(*this);
1564 NodeRemover().apply(stage, unused_nodes);
1565 return !unused_nodes.empty();
1568 void UnusedFunctionRemover::visit(FunctionCall &call)
1570 TraversingVisitor::visit(call);
1572 unused_nodes.erase(call.declaration);
1573 if(call.declaration && call.declaration->definition!=call.declaration)
1574 used_definitions.insert(call.declaration->definition);
1577 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1579 TraversingVisitor::visit(func);
1581 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1582 unused_nodes.insert(&func);