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.push_back(ExpressionInfo());
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.push_back(ExpressionInfo());
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 void ConstantConditionEliminator::apply(Stage &stage)
1062 stage.content.visit(*this);
1063 NodeRemover().apply(stage, nodes_to_remove);
1066 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1068 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1069 if(literal->value.check_type<bool>())
1070 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1071 return NOT_CONSTANT;
1074 void ConstantConditionEliminator::visit(Block &block)
1076 SetForScope<Block *> set_block(current_block, &block);
1077 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1084 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1086 r_ternary_result = 0;
1088 if(r_ternary_result)
1089 expr = r_ternary_result;
1090 r_ternary_result = 0;
1093 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1095 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1096 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1098 auto i = current_block->variables.find(var->name);
1099 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1103 TraversingVisitor::visit(unary);
1106 void ConstantConditionEliminator::visit(Assignment &assign)
1108 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1109 if(i==current_block->variables.end())
1110 r_external_side_effects = true;
1111 TraversingVisitor::visit(assign);
1114 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1116 ConstantStatus result = check_constant_condition(*ternary.condition);
1117 if(result!=NOT_CONSTANT)
1118 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1120 r_ternary_result = 0;
1123 void ConstantConditionEliminator::visit(FunctionCall &call)
1125 r_external_side_effects = true;
1126 TraversingVisitor::visit(call);
1129 void ConstantConditionEliminator::visit(Conditional &cond)
1131 ConstantStatus result = check_constant_condition(*cond.condition);
1132 if(result!=NOT_CONSTANT)
1134 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1135 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1136 current_block->body.splice(insert_point, block.body);
1137 nodes_to_remove.insert(&cond);
1141 r_external_side_effects = false;
1142 TraversingVisitor::visit(cond);
1144 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1145 nodes_to_remove.insert(&cond);
1148 void ConstantConditionEliminator::visit(Iteration &iter)
1152 ConstantStatus result = check_constant_condition(*iter.condition);
1153 if(result==CONSTANT_FALSE)
1155 nodes_to_remove.insert(&iter);
1160 r_external_side_effects = false;
1161 TraversingVisitor::visit(iter);
1162 if(iter.body.body.empty() && !r_external_side_effects)
1163 nodes_to_remove.insert(&iter);
1167 bool UnreachableCodeRemover::apply(Stage &stage)
1169 stage.content.visit(*this);
1170 NodeRemover().apply(stage, unreachable_nodes);
1171 return !unreachable_nodes.empty();
1174 void UnreachableCodeRemover::visit(Block &block)
1176 auto i = block.body.begin();
1177 for(; (reachable && i!=block.body.end()); ++i)
1179 for(; i!=block.body.end(); ++i)
1180 unreachable_nodes.insert(i->get());
1183 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1185 TraversingVisitor::visit(func);
1189 void UnreachableCodeRemover::visit(Conditional &cond)
1191 cond.body.visit(*this);
1192 bool reachable_if_true = reachable;
1194 cond.else_body.visit(*this);
1196 reachable |= reachable_if_true;
1199 void UnreachableCodeRemover::visit(Iteration &iter)
1201 TraversingVisitor::visit(iter);
1203 /* Always consider code after a loop reachable, since there's no checking
1204 for whether the loop executes. */
1209 bool UnusedTypeRemover::apply(Stage &stage)
1211 stage.content.visit(*this);
1212 NodeRemover().apply(stage, unused_nodes);
1213 return !unused_nodes.empty();
1216 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1218 unused_nodes.erase(expr->type);
1219 TraversingVisitor::visit(expr);
1222 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1225 unused_nodes.erase(type.base_type);
1226 unused_nodes.insert(&type);
1229 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1232 unused_nodes.erase(type.base_type);
1233 unused_nodes.insert(&type);
1236 void UnusedTypeRemover::visit(StructDeclaration &strct)
1238 unused_nodes.insert(&strct);
1239 TraversingVisitor::visit(strct);
1242 void UnusedTypeRemover::visit(VariableDeclaration &var)
1244 unused_nodes.erase(var.type_declaration);
1245 TraversingVisitor::visit(var);
1248 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1250 unused_nodes.erase(iface.type_declaration);
1253 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1255 unused_nodes.erase(func.return_type_declaration);
1256 TraversingVisitor::visit(func);
1260 bool UnusedVariableRemover::apply(Stage &s)
1263 s.content.visit(*this);
1265 for(const AssignmentInfo &a: assignments)
1266 if(a.used_by.empty())
1267 unused_nodes.insert(a.node);
1269 for(const auto &kvp: variables)
1271 if(!kvp.second.referenced)
1272 unused_nodes.insert(kvp.first);
1273 else if(kvp.second.output)
1275 /* The last visible assignments of output variables are used by the
1276 next stage or the API. */
1277 for(AssignmentInfo *a: kvp.second.assignments)
1278 unused_nodes.erase(a->node);
1282 NodeRemover().apply(s, unused_nodes);
1284 return !unused_nodes.empty();
1287 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1289 VariableInfo &var_info = variables[target.declaration];
1290 var_info.referenced = true;
1291 if(!assignment_target)
1293 bool loop_external = false;
1294 for(AssignmentInfo *a: var_info.assignments)
1295 if(targets_overlap(a->target, target))
1297 a->used_by.push_back(&node);
1298 if(a->in_loop<in_loop)
1299 loop_external = true;
1303 loop_ext_refs.push_back(&node);
1307 void UnusedVariableRemover::visit(VariableReference &var)
1309 if(composite_reference)
1310 r_reference.declaration = var.declaration;
1311 else if(var.declaration)
1312 referenced(var.declaration, var);
1315 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1317 if(composite_reference)
1318 r_reference.declaration = iface.declaration;
1319 else if(iface.declaration)
1320 referenced(iface.declaration, iface);
1323 void UnusedVariableRemover::visit_composite(Expression &expr)
1325 if(!composite_reference)
1326 r_reference = Assignment::Target();
1328 SetFlag set_composite(composite_reference);
1332 void UnusedVariableRemover::visit(MemberAccess &memacc)
1334 visit_composite(*memacc.left);
1336 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1338 if(!composite_reference && r_reference.declaration)
1339 referenced(r_reference, memacc);
1342 void UnusedVariableRemover::visit(Swizzle &swizzle)
1344 visit_composite(*swizzle.left);
1347 for(unsigned i=0; i<swizzle.count; ++i)
1348 mask |= 1<<swizzle.components[i];
1349 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1351 if(!composite_reference && r_reference.declaration)
1352 referenced(r_reference, swizzle);
1355 void UnusedVariableRemover::visit(UnaryExpression &unary)
1357 TraversingVisitor::visit(unary);
1358 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1359 r_side_effects = true;
1362 void UnusedVariableRemover::visit(BinaryExpression &binary)
1364 if(binary.oper->token[0]=='[')
1366 visit_composite(*binary.left);
1369 SetFlag clear_assignment(assignment_target, false);
1370 SetFlag clear_composite(composite_reference, false);
1371 SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1372 binary.right->visit(*this);
1375 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1377 if(!composite_reference && r_reference.declaration)
1378 referenced(r_reference, binary);
1382 SetFlag clear_composite(composite_reference, false);
1383 TraversingVisitor::visit(binary);
1387 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1389 SetFlag clear_composite(composite_reference, false);
1390 TraversingVisitor::visit(ternary);
1393 void UnusedVariableRemover::visit(Assignment &assign)
1396 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1397 assign.left->visit(*this);
1399 assign.right->visit(*this);
1400 r_assignment = &assign;
1401 r_side_effects = true;
1404 void UnusedVariableRemover::visit(FunctionCall &call)
1406 SetFlag clear_composite(composite_reference, false);
1407 TraversingVisitor::visit(call);
1408 /* Treat function calls as having side effects so expression statements
1409 consisting of nothing but a function call won't be optimized away. */
1410 r_side_effects = true;
1412 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1414 for(const auto &kvp: variables)
1415 if(kvp.second.output)
1416 referenced(kvp.first, call);
1420 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1422 assignments.push_back(AssignmentInfo());
1423 AssignmentInfo &assign_info = assignments.back();
1424 assign_info.node = &node;
1425 assign_info.target = target;
1426 assign_info.in_loop = in_loop;
1428 /* An assignment to the target hides any assignments to the same target or
1430 VariableInfo &var_info = variables[target.declaration];
1431 for(unsigned i=0; i<var_info.assignments.size(); )
1433 const Assignment::Target &t = var_info.assignments[i]->target;
1435 bool subfield = (t.chain_len>=target.chain_len);
1436 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1437 subfield = (t.chain[j]==target.chain[j]);
1440 var_info.assignments.erase(var_info.assignments.begin()+i);
1445 var_info.assignments.push_back(&assign_info);
1448 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1451 r_side_effects = false;
1452 TraversingVisitor::visit(expr);
1453 if(r_assignment && r_assignment->target.declaration)
1454 record_assignment(r_assignment->target, expr);
1456 unused_nodes.insert(&expr);
1459 void UnusedVariableRemover::visit(StructDeclaration &strct)
1461 SetFlag set_struct(in_struct);
1462 TraversingVisitor::visit(strct);
1465 void UnusedVariableRemover::visit(VariableDeclaration &var)
1467 TraversingVisitor::visit(var);
1472 VariableInfo &var_info = variables[&var];
1474 /* Mark variables as output if they're used by the next stage or the
1476 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1478 // Linked outputs are automatically referenced.
1479 if(var_info.output && var.linked_declaration)
1480 var_info.referenced = true;
1482 if(var.init_expression)
1484 var_info.initialized = true;
1485 record_assignment(&var, *var.init_expression);
1489 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1491 VariableInfo &var_info = variables[&iface];
1492 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1495 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1497 for(const auto &kvp: other_vars)
1499 auto j = variables.find(kvp.first);
1500 if(j!=variables.end())
1502 /* The merged blocks started as copies of each other so any common
1503 assignments must be in the beginning. */
1505 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1506 if(kvp.second.assignments[k]!=j->second.assignments[k])
1509 // Remaining assignments are unique to each block; merge them.
1510 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1511 j->second.referenced |= kvp.second.referenced;
1514 variables.insert(kvp);
1518 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1520 if(func.body.body.empty())
1523 BlockVariableMap saved_vars = variables;
1524 // Assignments from other functions should not be visible.
1525 for(auto &kvp: variables)
1526 kvp.second.assignments.resize(kvp.second.initialized);
1527 TraversingVisitor::visit(func);
1528 swap(variables, saved_vars);
1529 merge_variables(saved_vars);
1531 /* Always treat function parameters as referenced. Removing unused
1532 parameters is not currently supported. */
1533 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1535 auto j = variables.find(p.get());
1536 if(j!=variables.end())
1537 j->second.referenced = true;
1541 void UnusedVariableRemover::visit(Conditional &cond)
1543 cond.condition->visit(*this);
1544 BlockVariableMap saved_vars = variables;
1545 cond.body.visit(*this);
1546 swap(saved_vars, variables);
1547 cond.else_body.visit(*this);
1549 /* Visible assignments after the conditional is the union of those visible
1550 at the end of the if and else blocks. If there was no else block, then it's
1551 the union of the if block and the state before it. */
1552 merge_variables(saved_vars);
1555 void UnusedVariableRemover::visit(Iteration &iter)
1557 BlockVariableMap saved_vars = variables;
1558 vector<Node *> saved_refs;
1559 swap(loop_ext_refs, saved_refs);
1561 if(iter.init_statement)
1562 iter.init_statement->visit(*this);
1563 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1565 iter.condition->visit(*this);
1566 iter.body.visit(*this);
1567 if(iter.loop_expression)
1568 iter.loop_expression->visit(*this);
1570 swap(loop_ext_refs, saved_refs);
1572 /* Visit the external references of the loop again to record assignments
1573 done in the loop as used. */
1574 for(Node *n: saved_refs)
1577 /* Merge assignments from the iteration, without clearing previous state.
1578 Further analysis is needed to determine which parts of the iteration body
1579 are always executed, if any. */
1580 merge_variables(saved_vars);
1584 bool UnusedFunctionRemover::apply(Stage &stage)
1586 stage.content.visit(*this);
1587 NodeRemover().apply(stage, unused_nodes);
1588 return !unused_nodes.empty();
1591 void UnusedFunctionRemover::visit(FunctionCall &call)
1593 TraversingVisitor::visit(call);
1595 unused_nodes.erase(call.declaration);
1596 if(call.declaration && call.declaration->definition!=call.declaration)
1597 used_definitions.insert(call.declaration->definition);
1600 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1602 TraversingVisitor::visit(func);
1604 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1605 unused_nodes.insert(&func);