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(InterfaceBlockReference &iface)
197 referenced_names.insert(iface.name);
200 void InlineContentInjector::visit(FunctionCall &call)
203 referenced_names.insert(call.name);
204 TraversingVisitor::visit(call);
207 void InlineContentInjector::visit(VariableDeclaration &var)
209 TraversingVisitor::visit(var);
213 /* Check against conflicts with the other context as well as variables
214 already renamed here. */
215 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
216 staging_block.variables[var.name] = &var;
219 string mapped_name = get_unused_variable_name(staging_block, var.name);
220 if(mapped_name!=var.name)
222 staging_block.variables[mapped_name] = &var;
223 var.name = mapped_name;
227 else if(pass==REFERENCED)
228 referenced_names.insert(var.type);
231 void InlineContentInjector::visit(Return &ret)
233 TraversingVisitor::visit(ret);
235 if(pass==INLINE && ret.expression)
237 // Create a new variable to hold the return value of the inlined function.
238 r_result_name = get_unused_variable_name(staging_block, "_return");
239 RefPtr<VariableDeclaration> var = new VariableDeclaration;
240 var->source = ret.source;
241 var->line = ret.line;
242 var->type = source_func->return_type;
243 var->name = r_result_name;
244 var->init_expression = ret.expression->clone();
245 r_inlined_statement = var;
250 bool FunctionInliner::apply(Stage &s)
253 inlineable = InlineableFunctionLocator().apply(s);
254 r_any_inlined = false;
255 s.content.visit(*this);
256 return r_any_inlined;
259 void FunctionInliner::visit(RefPtr<Expression> &ptr)
265 ptr = r_inline_result;
266 r_any_inlined = true;
271 void FunctionInliner::visit(Block &block)
273 SetForScope<Block *> set_block(current_block, &block);
274 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
275 for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
282 void FunctionInliner::visit(FunctionCall &call)
284 for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
290 FunctionDeclaration *def = call.declaration;
292 def = def->definition;
294 if(def && inlineable.count(def))
296 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
298 // This will later get removed by UnusedVariableRemover.
299 if(result_name.empty())
300 result_name = "_msp_unused_from_inline";
302 RefPtr<VariableReference> ref = new VariableReference;
303 ref->name = result_name;
304 r_inline_result = ref;
306 /* Inlined variables need to be resolved before this function can be
308 inlineable.erase(current_function);
309 r_inlined_here = true;
313 void FunctionInliner::visit(FunctionDeclaration &func)
315 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
316 TraversingVisitor::visit(func);
317 r_inlined_here = false;
320 void FunctionInliner::visit(Iteration &iter)
322 /* Visit the initialization statement before entering the loop body so the
323 inlined statements get inserted outside. */
324 if(iter.init_statement)
325 iter.init_statement->visit(*this);
327 SetForScope<Block *> set_block(current_block, &iter.body);
328 /* Skip the condition and loop expression parts because they're not properly
329 inside the body block. Inlining anything into them will require a more
330 comprehensive transformation. */
331 iter.body.visit(*this);
335 bool ExpressionInliner::apply(Stage &s)
337 s.content.visit(*this);
339 bool any_inlined = false;
340 for(ExpressionInfo &e: expressions)
341 if(e.expression && (e.trivial || e.uses.size()==1))
343 for(ExpressionUse &u: e.uses)
346 *u.reference = e.expression->clone();
354 void ExpressionInliner::visit(RefPtr<Expression> &expr)
358 if(r_ref_info && r_ref_info->expression)
361 use.reference = &expr;
362 use.ref_scope = current_block;
363 use.blocked = access_write || r_ref_info->blocked;
365 if(iteration_body && !r_ref_info->trivial)
367 /* Block inlining of non-trivial expressions assigned outside an
368 iteration statement. The iteration may run multiple times, which
369 would cause the expression to also be evaluated multiple times. */
370 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
371 use.blocked = (i==r_ref_info->assign_scope);
374 /* Block inlining assignments from from inner scopes. The assignment may
375 depend on local variables of that scope or may not always be executed. */
376 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
377 use.blocked = (i==current_block);
379 r_ref_info->uses.push_back(use);
385 void ExpressionInliner::visit(VariableReference &var)
387 if(var.declaration && access_read)
389 auto i = assignments.find(var.declaration);
390 if(i!=assignments.end())
391 r_ref_info = i->second;
395 void ExpressionInliner::visit(MemberAccess &memacc)
401 void ExpressionInliner::visit(Swizzle &swizzle)
407 void ExpressionInliner::visit(UnaryExpression &unary)
409 SetFlag set_write(access_write, (unary.oper->token[1]=='+' || unary.oper->token[1]=='-'));
410 visit(unary.expression);
414 void ExpressionInliner::visit(BinaryExpression &binary)
418 SetFlag clear_write(access_write, false);
424 void ExpressionInliner::visit(Assignment &assign)
427 SetFlag set_read(access_read, assign.oper->token[0]!='=');
428 SetFlag set_write(access_write);
435 auto i = assignments.find(assign.target.declaration);
436 if(i!=assignments.end())
438 if(iteration_body && i->second && i->second->expression)
440 /* Block inlining into previous references within the iteration
441 statement. On iterations after the first they would refer to the
442 assignment within the iteration. */
443 for(ExpressionUse &u: i->second->uses)
444 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
445 u.blocked = (k==iteration_body);
448 for(; (i!=assignments.end() && i->first.declaration==assign.target.declaration); ++i)
449 if(targets_overlap(i->first, assign.target))
450 i->second->blocked = true;
452 expressions.emplace_back();
453 ExpressionInfo &info = expressions.back();
454 info.target = assign.target;
455 // Self-referencing assignments can't be inlined without additional work.
456 if(!assign.self_referencing)
457 info.expression = assign.right;
458 info.assign_scope = current_block;
459 info.trivial = r_trivial;
461 assignments[assign.target] = &info;
467 void ExpressionInliner::visit(TernaryExpression &ternary)
469 visit(ternary.condition);
470 visit(ternary.true_expr);
471 visit(ternary.false_expr);
475 void ExpressionInliner::visit(FunctionCall &call)
477 TraversingVisitor::visit(call);
481 void ExpressionInliner::visit(VariableDeclaration &var)
485 TraversingVisitor::visit(var);
487 bool constant = var.constant;
488 if(constant && var.layout)
490 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
491 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
494 /* Only inline global variables if they're constant and have trivial
495 initializers. Non-constant variables could change in ways which are hard to
496 analyze and non-trivial expressions could be expensive to inline. */
497 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
499 expressions.emplace_back();
500 ExpressionInfo &info = expressions.back();
502 /* Assume variables declared in an iteration initialization statement
503 will have their values change throughout the iteration. */
505 info.expression = var.init_expression;
506 info.assign_scope = current_block;
507 info.trivial = r_trivial;
509 assignments[&var] = &info;
513 void ExpressionInliner::visit(Iteration &iter)
515 SetForScope<Block *> set_block(current_block, &iter.body);
516 if(iter.init_statement)
518 SetFlag set_init(iteration_init);
519 iter.init_statement->visit(*this);
522 SetForScope<Block *> set_body(iteration_body, &iter.body);
524 visit(iter.condition);
525 iter.body.visit(*this);
526 if(iter.loop_expression)
527 visit(iter.loop_expression);
531 bool AggregateDismantler::apply(Stage &stage)
533 stage.content.visit(*this);
535 bool any_dismantled = false;
536 for(const auto &kvp: aggregates)
538 if(kvp.second.referenced || !kvp.second.members_referenced)
541 for(const AggregateMember &m: kvp.second.members)
545 name = format("%s_%s", kvp.second.declaration->name, m.declaration->name);
547 name = format("%s_%d", kvp.second.declaration->name, m.index);
549 VariableDeclaration *var = new VariableDeclaration;
550 var->source = kvp.first->source;
551 var->line = kvp.first->line;
552 var->name = get_unused_variable_name(*kvp.second.decl_scope, name);
553 /* XXX This is kind of brittle and depends on the array declaration's
554 textual type not having brackets in it. */
555 var->type = (m.declaration ? m.declaration : kvp.second.declaration)->type;
557 var->init_expression = m.initializer->clone();
559 kvp.second.decl_scope->body.insert(kvp.second.insert_point, var);
561 for(RefPtr<Expression> *r: m.references)
563 VariableReference *ref = new VariableReference;
564 ref->name = var->name;
568 any_dismantled = true;
572 return any_dismantled;
575 void AggregateDismantler::visit(Block &block)
577 SetForScope<Block *> set_block(current_block, &block);
578 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
585 void AggregateDismantler::visit(RefPtr<Expression> &expr)
589 if(r_aggregate_ref && r_reference.chain_len==1)
591 if((r_reference.chain[0]&0x3F)!=0x3F)
593 r_aggregate_ref->members[r_reference.chain[0]&0x3F].references.push_back(&expr);
594 r_aggregate_ref->members_referenced = true;
597 /* If the accessed member is not known, mark the entire aggregate as
599 r_aggregate_ref->referenced = true;
604 void AggregateDismantler::visit(VariableReference &var)
606 if(composite_reference)
607 r_reference.declaration = var.declaration;
610 /* If an aggregate variable is referenced as a whole, it should not be
612 auto i = aggregates.find(var.declaration);
613 if(i!=aggregates.end())
614 i->second.referenced = true;
618 void AggregateDismantler::visit_composite(RefPtr<Expression> &expr)
620 if(!composite_reference)
621 r_reference = Assignment::Target();
623 SetFlag set_composite(composite_reference);
627 void AggregateDismantler::visit(MemberAccess &memacc)
629 visit_composite(memacc.left);
631 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
633 if(r_reference.declaration && r_reference.chain_len==1)
635 auto i = aggregates.find(r_reference.declaration);
636 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
642 void AggregateDismantler::visit(BinaryExpression &binary)
644 if(binary.oper->token[0]=='[')
646 visit_composite(binary.left);
648 SetFlag clear_composite(composite_reference, false);
652 unsigned index = 0x3F;
653 if(Literal *literal_subscript = dynamic_cast<Literal *>(binary.right.get()))
654 if(literal_subscript->value.check_type<int>())
655 index = literal_subscript->value.value<int>();
656 add_to_chain(r_reference, Assignment::Target::ARRAY, index);
658 if(r_reference.declaration && r_reference.chain_len==1)
660 auto i = aggregates.find(r_reference.declaration);
661 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
668 SetFlag clear_composite(composite_reference, false);
669 TraversingVisitor::visit(binary);
673 void AggregateDismantler::visit(VariableDeclaration &var)
675 TraversingVisitor::visit(var);
677 if(var.interface.empty())
679 if(const StructDeclaration *strct = dynamic_cast<const StructDeclaration *>(var.type_declaration))
681 const FunctionCall *init_call = dynamic_cast<const FunctionCall *>(var.init_expression.get());
682 if((init_call && init_call->constructor) || !var.init_expression)
685 Aggregate &aggre = aggregates[&var];
686 aggre.declaration = &var;
687 aggre.decl_scope = current_block;
688 aggre.insert_point = insert_point;
691 for(const RefPtr<Statement> &s: strct->members.body)
693 if(const VariableDeclaration *mem_decl = dynamic_cast<const VariableDeclaration *>(s.get()))
695 AggregateMember member;
696 member.declaration = mem_decl;
699 member.initializer = init_call->arguments[i];
700 aggre.members.push_back(member);
706 else if(const Literal *literal_size = dynamic_cast<const Literal *>(var.array_size.get()))
708 if(literal_size->value.check_type<int>())
710 Aggregate &aggre = aggregates[&var];
711 aggre.declaration = &var;
712 aggre.decl_scope = current_block;
713 aggre.insert_point = insert_point;
715 int size = literal_size->value.value<int>();
716 for(int i=0; i<size; ++i)
718 AggregateMember member;
720 // Array initializers are not supported yet
721 aggre.members.push_back(member);
728 void AggregateDismantler::visit(FunctionDeclaration &func)
730 func.body.visit(*this);
735 T ConstantFolder::evaluate_logical(char oper, T left, T right)
739 case '&': return left&right;
740 case '|': return left|right;
741 case '^': return left^right;
747 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
749 switch(oper[0]|oper[1])
751 case '<': return left<right;
752 case '<'|'=': return left<=right;
753 case '>': return left>right;
754 case '>'|'=': return left>=right;
755 default: return false;
760 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
764 case '+': return left+right;
765 case '-': return left-right;
766 case '*': return left*right;
767 case '/': return left/right;
773 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
777 case '%': return left%right;
778 case '<': return left<<right;
779 case '>': return left>>right;
785 void ConstantFolder::convert_to_result(const Variant &value)
787 if(value.check_type<bool>())
788 set_result(static_cast<T>(value.value<bool>()));
789 else if(value.check_type<int>())
790 set_result(static_cast<T>(value.value<int>()));
791 else if(value.check_type<unsigned>())
792 set_result(static_cast<T>(value.value<unsigned>()));
793 else if(value.check_type<float>())
794 set_result(static_cast<T>(value.value<float>()));
797 void ConstantFolder::set_result(const Variant &value, bool literal)
799 r_constant_value = value;
804 void ConstantFolder::visit(RefPtr<Expression> &expr)
806 r_constant_value = Variant();
809 r_uses_iter_var = false;
811 /* Don't replace literals since they'd only be replaced with an identical
812 literal. Also skip anything that uses an iteration variable, but pass on
813 the result so the Iteration visiting function can handle it. */
814 if(!r_constant || r_literal || r_uses_iter_var)
817 RefPtr<Literal> literal = new Literal;
818 if(r_constant_value.check_type<bool>())
819 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
820 else if(r_constant_value.check_type<int>())
821 literal->token = lexical_cast<string>(r_constant_value.value<int>());
822 else if(r_constant_value.check_type<unsigned>())
823 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
824 else if(r_constant_value.check_type<float>())
826 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
827 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
828 literal->token += ".0";
835 literal->value = r_constant_value;
840 void ConstantFolder::visit(Literal &literal)
842 set_result(literal.value, true);
845 void ConstantFolder::visit(VariableReference &var)
847 /* If an iteration variable is initialized with a constant value, return
848 that value here for the purpose of evaluating the loop condition for the
850 if(var.declaration==iteration_var)
852 set_result(iter_init_value);
853 r_uses_iter_var = true;
857 void ConstantFolder::visit(MemberAccess &memacc)
859 TraversingVisitor::visit(memacc);
863 void ConstantFolder::visit(Swizzle &swizzle)
865 TraversingVisitor::visit(swizzle);
869 void ConstantFolder::visit(UnaryExpression &unary)
871 TraversingVisitor::visit(unary);
872 bool can_fold = r_constant;
877 char oper = unary.oper->token[0];
878 char oper2 = unary.oper->token[1];
881 if(r_constant_value.check_type<bool>())
882 set_result(!r_constant_value.value<bool>());
886 if(r_constant_value.check_type<int>())
887 set_result(~r_constant_value.value<int>());
888 else if(r_constant_value.check_type<unsigned>())
889 set_result(~r_constant_value.value<unsigned>());
891 else if(oper=='-' && !oper2)
893 if(r_constant_value.check_type<int>())
894 set_result(-r_constant_value.value<int>());
895 else if(r_constant_value.check_type<unsigned>())
896 set_result(-r_constant_value.value<unsigned>());
897 else if(r_constant_value.check_type<float>())
898 set_result(-r_constant_value.value<float>());
902 void ConstantFolder::visit(BinaryExpression &binary)
905 bool left_constant = r_constant;
906 bool left_iter_var = r_uses_iter_var;
907 Variant left_value = r_constant_value;
910 r_uses_iter_var = true;
912 bool can_fold = (left_constant && r_constant);
917 // Currently only expressions with both sides of equal types are handled.
918 if(!left_value.check_same_type(r_constant_value))
921 char oper = binary.oper->token[0];
922 char oper2 = binary.oper->token[1];
923 if(oper=='&' || oper=='|' || oper=='^')
925 if(oper2==oper && left_value.check_type<bool>())
926 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
927 else if(!oper2 && left_value.check_type<int>())
928 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
929 else if(!oper2 && left_value.check_type<unsigned>())
930 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
932 else if((oper=='<' || oper=='>') && oper2!=oper)
934 if(left_value.check_type<int>())
935 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
936 else if(left_value.check_type<unsigned>())
937 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
938 else if(left_value.check_type<float>())
939 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
941 else if((oper=='=' || oper=='!') && oper2=='=')
943 if(left_value.check_type<int>())
944 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
945 else if(left_value.check_type<unsigned>())
946 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
947 else if(left_value.check_type<float>())
948 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
950 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
952 if(left_value.check_type<int>())
953 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
954 else if(left_value.check_type<unsigned>())
955 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
956 else if(left_value.check_type<float>())
957 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
959 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
961 if(left_value.check_type<int>())
962 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
963 else if(left_value.check_type<unsigned>())
964 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
968 void ConstantFolder::visit(Assignment &assign)
970 TraversingVisitor::visit(assign);
974 void ConstantFolder::visit(TernaryExpression &ternary)
976 TraversingVisitor::visit(ternary);
980 void ConstantFolder::visit(FunctionCall &call)
982 if(call.constructor && call.type && call.arguments.size()==1)
984 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
987 visit(call.arguments[0]);
988 bool can_fold = r_constant;
993 if(basic->kind==BasicTypeDeclaration::BOOL)
994 convert_to_result<bool>(r_constant_value);
995 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
996 convert_to_result<int>(r_constant_value);
997 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
998 convert_to_result<unsigned>(r_constant_value);
999 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
1000 convert_to_result<float>(r_constant_value);
1006 TraversingVisitor::visit(call);
1010 void ConstantFolder::visit(VariableDeclaration &var)
1012 if(iteration_init && var.init_expression)
1014 visit(var.init_expression);
1017 /* Record the value of a constant initialization expression of an
1018 iteration, so it can be used to evaluate the loop condition. */
1019 iteration_var = &var;
1020 iter_init_value = r_constant_value;
1024 TraversingVisitor::visit(var);
1027 void ConstantFolder::visit(Iteration &iter)
1029 SetForScope<Block *> set_block(current_block, &iter.body);
1031 /* The iteration variable is not normally inlined into expressions, so we
1032 process it specially here. If the initial value causes the loop condition
1033 to evaluate to false, then the expression can be folded. */
1035 if(iter.init_statement)
1037 SetFlag set_init(iteration_init);
1038 iter.init_statement->visit(*this);
1043 visit(iter.condition);
1044 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1046 RefPtr<Literal> literal = new Literal;
1047 literal->token = "false";
1048 literal->value = r_constant_value;
1049 iter.condition = literal;
1054 iter.body.visit(*this);
1055 if(iter.loop_expression)
1056 visit(iter.loop_expression);
1060 bool ConstantConditionEliminator::apply(Stage &stage)
1062 stage.content.visit(*this);
1063 NodeRemover().apply(stage, nodes_to_remove);
1064 return !nodes_to_remove.empty();
1067 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1069 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1070 if(literal->value.check_type<bool>())
1071 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1072 return NOT_CONSTANT;
1075 void ConstantConditionEliminator::visit(Block &block)
1077 SetForScope<Block *> set_block(current_block, &block);
1078 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1085 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1087 r_ternary_result = 0;
1089 if(r_ternary_result)
1090 expr = r_ternary_result;
1091 r_ternary_result = 0;
1094 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1096 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1097 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1099 auto i = current_block->variables.find(var->name);
1100 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1104 TraversingVisitor::visit(unary);
1107 void ConstantConditionEliminator::visit(Assignment &assign)
1109 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1110 if(i==current_block->variables.end())
1111 r_external_side_effects = true;
1112 TraversingVisitor::visit(assign);
1115 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1117 ConstantStatus result = check_constant_condition(*ternary.condition);
1118 if(result!=NOT_CONSTANT)
1119 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1121 r_ternary_result = 0;
1124 void ConstantConditionEliminator::visit(FunctionCall &call)
1126 r_external_side_effects = true;
1127 TraversingVisitor::visit(call);
1130 void ConstantConditionEliminator::visit(Conditional &cond)
1132 ConstantStatus result = check_constant_condition(*cond.condition);
1133 if(result!=NOT_CONSTANT)
1135 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1136 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1137 current_block->body.splice(insert_point, block.body);
1138 nodes_to_remove.insert(&cond);
1142 r_external_side_effects = false;
1143 TraversingVisitor::visit(cond);
1145 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1146 nodes_to_remove.insert(&cond);
1149 void ConstantConditionEliminator::visit(Iteration &iter)
1153 ConstantStatus result = check_constant_condition(*iter.condition);
1154 if(result==CONSTANT_FALSE)
1156 nodes_to_remove.insert(&iter);
1161 r_external_side_effects = false;
1162 TraversingVisitor::visit(iter);
1163 if(iter.body.body.empty() && !r_external_side_effects)
1164 nodes_to_remove.insert(&iter);
1168 bool UnreachableCodeRemover::apply(Stage &stage)
1170 stage.content.visit(*this);
1171 NodeRemover().apply(stage, unreachable_nodes);
1172 return !unreachable_nodes.empty();
1175 void UnreachableCodeRemover::visit(Block &block)
1177 auto i = block.body.begin();
1178 for(; (reachable && i!=block.body.end()); ++i)
1180 for(; i!=block.body.end(); ++i)
1181 unreachable_nodes.insert(i->get());
1184 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1186 TraversingVisitor::visit(func);
1190 void UnreachableCodeRemover::visit(Conditional &cond)
1192 cond.body.visit(*this);
1193 bool reachable_if_true = reachable;
1195 cond.else_body.visit(*this);
1197 reachable |= reachable_if_true;
1200 void UnreachableCodeRemover::visit(Iteration &iter)
1202 TraversingVisitor::visit(iter);
1204 /* Always consider code after a loop reachable, since there's no checking
1205 for whether the loop executes. */
1210 bool UnusedTypeRemover::apply(Stage &stage)
1212 stage.content.visit(*this);
1213 NodeRemover().apply(stage, unused_nodes);
1214 return !unused_nodes.empty();
1217 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1219 unused_nodes.erase(expr->type);
1220 TraversingVisitor::visit(expr);
1223 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1226 unused_nodes.erase(type.base_type);
1227 unused_nodes.insert(&type);
1230 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1233 unused_nodes.erase(type.base_type);
1234 unused_nodes.insert(&type);
1237 void UnusedTypeRemover::visit(StructDeclaration &strct)
1239 unused_nodes.insert(&strct);
1240 TraversingVisitor::visit(strct);
1243 void UnusedTypeRemover::visit(VariableDeclaration &var)
1245 unused_nodes.erase(var.type_declaration);
1246 TraversingVisitor::visit(var);
1249 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1251 unused_nodes.erase(iface.type_declaration);
1254 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1256 unused_nodes.erase(func.return_type_declaration);
1257 TraversingVisitor::visit(func);
1261 bool UnusedVariableRemover::apply(Stage &s)
1264 s.content.visit(*this);
1266 for(const AssignmentInfo &a: assignments)
1267 if(a.used_by.empty())
1268 unused_nodes.insert(a.node);
1270 for(const auto &kvp: variables)
1272 if(!kvp.second.referenced)
1273 unused_nodes.insert(kvp.first);
1274 else if(kvp.second.output)
1276 /* The last visible assignments of output variables are used by the
1277 next stage or the API. */
1278 for(AssignmentInfo *a: kvp.second.assignments)
1279 unused_nodes.erase(a->node);
1283 NodeRemover().apply(s, unused_nodes);
1285 return !unused_nodes.empty();
1288 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1290 VariableInfo &var_info = variables[target.declaration];
1291 var_info.referenced = true;
1292 if(!assignment_target)
1294 bool loop_external = false;
1295 for(AssignmentInfo *a: var_info.assignments)
1296 if(targets_overlap(a->target, target))
1298 a->used_by.push_back(&node);
1299 if(a->in_loop<in_loop)
1300 loop_external = true;
1304 loop_ext_refs.push_back(&node);
1308 void UnusedVariableRemover::visit(VariableReference &var)
1310 if(composite_reference)
1311 r_reference.declaration = var.declaration;
1312 else if(var.declaration)
1313 referenced(var.declaration, var);
1316 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1318 if(composite_reference)
1319 r_reference.declaration = iface.declaration;
1320 else if(iface.declaration)
1321 referenced(iface.declaration, iface);
1324 void UnusedVariableRemover::visit_composite(Expression &expr)
1326 if(!composite_reference)
1327 r_reference = Assignment::Target();
1329 SetFlag set_composite(composite_reference);
1333 void UnusedVariableRemover::visit(MemberAccess &memacc)
1335 visit_composite(*memacc.left);
1337 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1339 if(!composite_reference && r_reference.declaration)
1340 referenced(r_reference, memacc);
1343 void UnusedVariableRemover::visit(Swizzle &swizzle)
1345 visit_composite(*swizzle.left);
1348 for(unsigned i=0; i<swizzle.count; ++i)
1349 mask |= 1<<swizzle.components[i];
1350 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1352 if(!composite_reference && r_reference.declaration)
1353 referenced(r_reference, swizzle);
1356 void UnusedVariableRemover::visit(UnaryExpression &unary)
1358 TraversingVisitor::visit(unary);
1359 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1360 r_side_effects = true;
1363 void UnusedVariableRemover::visit(BinaryExpression &binary)
1365 if(binary.oper->token[0]=='[')
1367 visit_composite(*binary.left);
1370 SetFlag clear_assignment(assignment_target, false);
1371 SetFlag clear_composite(composite_reference, false);
1372 SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1373 binary.right->visit(*this);
1376 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1378 if(!composite_reference && r_reference.declaration)
1379 referenced(r_reference, binary);
1383 SetFlag clear_composite(composite_reference, false);
1384 TraversingVisitor::visit(binary);
1388 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1390 SetFlag clear_composite(composite_reference, false);
1391 TraversingVisitor::visit(ternary);
1394 void UnusedVariableRemover::visit(Assignment &assign)
1397 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1398 assign.left->visit(*this);
1400 assign.right->visit(*this);
1401 r_assignment = &assign;
1402 r_side_effects = true;
1405 void UnusedVariableRemover::visit(FunctionCall &call)
1407 SetFlag clear_composite(composite_reference, false);
1408 TraversingVisitor::visit(call);
1409 /* Treat function calls as having side effects so expression statements
1410 consisting of nothing but a function call won't be optimized away. */
1411 r_side_effects = true;
1413 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1415 for(const auto &kvp: variables)
1416 if(kvp.second.output)
1417 referenced(kvp.first, call);
1421 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1423 assignments.emplace_back();
1424 AssignmentInfo &assign_info = assignments.back();
1425 assign_info.node = &node;
1426 assign_info.target = target;
1427 assign_info.in_loop = in_loop;
1429 /* An assignment to the target hides any assignments to the same target or
1431 VariableInfo &var_info = variables[target.declaration];
1432 for(unsigned i=0; i<var_info.assignments.size(); )
1434 const Assignment::Target &t = var_info.assignments[i]->target;
1436 bool subfield = (t.chain_len>=target.chain_len);
1437 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1438 subfield = (t.chain[j]==target.chain[j]);
1441 var_info.assignments.erase(var_info.assignments.begin()+i);
1446 var_info.assignments.push_back(&assign_info);
1449 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1452 r_side_effects = false;
1453 TraversingVisitor::visit(expr);
1454 if(r_assignment && r_assignment->target.declaration)
1455 record_assignment(r_assignment->target, expr);
1457 unused_nodes.insert(&expr);
1460 void UnusedVariableRemover::visit(StructDeclaration &strct)
1462 SetFlag set_struct(in_struct);
1463 TraversingVisitor::visit(strct);
1466 void UnusedVariableRemover::visit(VariableDeclaration &var)
1468 TraversingVisitor::visit(var);
1473 VariableInfo &var_info = variables[&var];
1475 /* Mark variables as output if they're used by the next stage or the
1477 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1479 // Linked outputs are automatically referenced.
1480 if(var_info.output && var.linked_declaration)
1481 var_info.referenced = true;
1483 if(var.init_expression)
1485 var_info.initialized = true;
1486 record_assignment(&var, *var.init_expression);
1490 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1492 VariableInfo &var_info = variables[&iface];
1493 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1496 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1498 for(const auto &kvp: other_vars)
1500 auto j = variables.find(kvp.first);
1501 if(j!=variables.end())
1503 /* The merged blocks started as copies of each other so any common
1504 assignments must be in the beginning. */
1506 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1507 if(kvp.second.assignments[k]!=j->second.assignments[k])
1510 // Remaining assignments are unique to each block; merge them.
1511 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1512 j->second.referenced |= kvp.second.referenced;
1515 variables.insert(kvp);
1519 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1521 if(func.body.body.empty())
1524 BlockVariableMap saved_vars = variables;
1525 // Assignments from other functions should not be visible.
1526 for(auto &kvp: variables)
1527 kvp.second.assignments.resize(kvp.second.initialized);
1528 TraversingVisitor::visit(func);
1529 swap(variables, saved_vars);
1530 merge_variables(saved_vars);
1532 /* Always treat function parameters as referenced. Removing unused
1533 parameters is not currently supported. */
1534 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1536 auto j = variables.find(p.get());
1537 if(j!=variables.end())
1538 j->second.referenced = true;
1542 void UnusedVariableRemover::visit(Conditional &cond)
1544 cond.condition->visit(*this);
1545 BlockVariableMap saved_vars = variables;
1546 cond.body.visit(*this);
1547 swap(saved_vars, variables);
1548 cond.else_body.visit(*this);
1550 /* Visible assignments after the conditional is the union of those visible
1551 at the end of the if and else blocks. If there was no else block, then it's
1552 the union of the if block and the state before it. */
1553 merge_variables(saved_vars);
1556 void UnusedVariableRemover::visit(Iteration &iter)
1558 BlockVariableMap saved_vars = variables;
1559 vector<Node *> saved_refs;
1560 swap(loop_ext_refs, saved_refs);
1562 if(iter.init_statement)
1563 iter.init_statement->visit(*this);
1564 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1566 iter.condition->visit(*this);
1567 iter.body.visit(*this);
1568 if(iter.loop_expression)
1569 iter.loop_expression->visit(*this);
1571 swap(loop_ext_refs, saved_refs);
1573 /* Visit the external references of the loop again to record assignments
1574 done in the loop as used. */
1575 for(Node *n: saved_refs)
1578 /* Merge assignments from the iteration, without clearing previous state.
1579 Further analysis is needed to determine which parts of the iteration body
1580 are always executed, if any. */
1581 merge_variables(saved_vars);
1585 bool UnusedFunctionRemover::apply(Stage &stage)
1587 stage.content.visit(*this);
1588 NodeRemover().apply(stage, unused_nodes);
1589 return !unused_nodes.empty();
1592 void UnusedFunctionRemover::visit(FunctionCall &call)
1594 TraversingVisitor::visit(call);
1596 unused_nodes.erase(call.declaration);
1597 if(call.declaration && call.declaration->definition!=call.declaration)
1598 used_definitions.insert(call.declaration->definition);
1601 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1603 TraversingVisitor::visit(func);
1605 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1606 unused_nodes.insert(&func);