1 #include <msp/core/algorithm.h>
2 #include <msp/core/raii.h>
3 #include <msp/strings/format.h>
4 #include <msp/strings/utils.h>
14 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
17 stage.content.visit(*this);
20 void ConstantSpecializer::visit(VariableDeclaration &var)
22 bool specializable = false;
25 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
26 auto i = find_member(qualifiers, string("constant_id"), &Layout::Qualifier::name);
27 if(i!=qualifiers.end())
31 if(qualifiers.empty())
38 auto i = values->find(var.name);
41 RefPtr<Literal> literal = new Literal;
44 literal->token = (i->second ? "true" : "false");
45 literal->value = static_cast<bool>(i->second);
47 else if(var.type=="int")
49 literal->token = lexical_cast<string>(i->second);
50 literal->value = i->second;
52 var.init_expression = literal;
58 void InlineableFunctionLocator::visit(FunctionCall &call)
60 FunctionDeclaration *def = call.declaration;
62 def = def->definition;
66 unsigned &count = refcounts[def];
68 /* Don't inline functions which are called more than once or are called
70 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
71 inlineable.erase(def);
74 TraversingVisitor::visit(call);
77 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
79 bool has_out_params = any_of(func.parameters.begin(), func.parameters.end(),
80 [](const RefPtr<VariableDeclaration> &p){ return p->interface=="out"; });
82 unsigned &count = refcounts[func.definition];
83 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
84 inlineable.insert(func.definition);
86 SetForScope<FunctionDeclaration *> set(current_function, &func);
88 TraversingVisitor::visit(func);
91 void InlineableFunctionLocator::visit(Conditional &cond)
93 TraversingVisitor::visit(cond);
94 inlineable.erase(current_function);
97 void InlineableFunctionLocator::visit(Iteration &iter)
99 TraversingVisitor::visit(iter);
100 inlineable.erase(current_function);
103 void InlineableFunctionLocator::visit(Return &ret)
105 TraversingVisitor::visit(ret);
107 inlineable.erase(current_function);
112 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
114 source_func = call.declaration->definition;
116 /* Populate referenced_names from the target function so we can rename
117 variables from the inlined function that would conflict. */
119 target_func.visit(*this);
121 /* Inline and rename passes must be interleaved so used variable names are
122 known when inlining the return statement. */
124 staging_block.parent = &tgt_blk;
125 staging_block.variables.clear();
127 vector<RefPtr<VariableDeclaration> > params;
128 params.reserve(source_func->parameters.size());
129 for(const RefPtr<VariableDeclaration> &p: source_func->parameters)
131 RefPtr<VariableDeclaration> var = p->clone();
132 var->interface.clear();
134 SetForScope<Pass> set_pass(pass, RENAME);
137 staging_block.body.push_back_nocopy(var);
138 params.push_back(var);
141 for(const RefPtr<Statement> &s: source_func->body.body)
143 r_inlined_statement = 0;
145 if(!r_inlined_statement)
146 r_inlined_statement = s->clone();
148 SetForScope<Pass> set_pass(pass, RENAME);
149 r_inlined_statement->visit(*this);
151 staging_block.body.push_back_nocopy(r_inlined_statement);
154 /* Now collect names from the staging block. Local variables that would
155 have conflicted with the target function were renamed earlier. */
157 referenced_names.clear();
158 staging_block.variables.clear();
159 staging_block.visit(*this);
161 /* Rename variables in the target function so they don't interfere with
162 global identifiers used by the source function. */
164 staging_block.parent = source_func->body.parent;
165 target_func.visit(*this);
167 // Put the argument expressions in place after all renaming has been done.
168 for(unsigned i=0; i<source_func->parameters.size(); ++i)
169 params[i]->init_expression = call.arguments[i]->clone();
171 tgt_blk.body.splice(ins_pt, staging_block.body);
173 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
175 return r_result_name;
178 void InlineContentInjector::visit(VariableReference &var)
182 auto i = staging_block.variables.find(var.name);
183 if(i!=staging_block.variables.end())
184 var.name = i->second->name;
186 else if(pass==REFERENCED)
187 referenced_names.insert(var.name);
190 void InlineContentInjector::visit(InterfaceBlockReference &iface)
193 referenced_names.insert(iface.name);
196 void InlineContentInjector::visit(FunctionCall &call)
199 referenced_names.insert(call.name);
200 TraversingVisitor::visit(call);
203 void InlineContentInjector::visit(VariableDeclaration &var)
205 TraversingVisitor::visit(var);
209 /* Check against conflicts with the other context as well as variables
210 already renamed here. */
211 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
212 staging_block.variables[var.name] = &var;
215 string mapped_name = get_unused_variable_name(staging_block, var.name);
216 if(mapped_name!=var.name)
218 staging_block.variables[mapped_name] = &var;
219 var.name = mapped_name;
223 else if(pass==REFERENCED)
224 referenced_names.insert(var.type);
227 void InlineContentInjector::visit(Return &ret)
229 TraversingVisitor::visit(ret);
231 if(pass==INLINE && ret.expression)
233 // Create a new variable to hold the return value of the inlined function.
234 r_result_name = get_unused_variable_name(staging_block, "_return");
235 RefPtr<VariableDeclaration> var = new VariableDeclaration;
236 var->source = ret.source;
237 var->line = ret.line;
238 var->type = source_func->return_type;
239 var->name = r_result_name;
240 var->init_expression = ret.expression->clone();
241 r_inlined_statement = var;
246 bool FunctionInliner::apply(Stage &s)
249 inlineable = InlineableFunctionLocator().apply(s);
250 r_any_inlined = false;
251 s.content.visit(*this);
252 return r_any_inlined;
255 void FunctionInliner::visit(RefPtr<Expression> &ptr)
261 ptr = r_inline_result;
262 r_any_inlined = true;
267 void FunctionInliner::visit(Block &block)
269 SetForScope<Block *> set_block(current_block, &block);
270 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
271 for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
278 void FunctionInliner::visit(FunctionCall &call)
280 for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
286 FunctionDeclaration *def = call.declaration;
288 def = def->definition;
290 if(def && inlineable.count(def))
292 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
294 // This will later get removed by UnusedVariableRemover.
295 if(result_name.empty())
296 result_name = "_msp_unused_from_inline";
298 RefPtr<VariableReference> ref = new VariableReference;
299 ref->name = result_name;
300 r_inline_result = ref;
302 /* Inlined variables need to be resolved before this function can be
304 inlineable.erase(current_function);
305 r_inlined_here = true;
309 void FunctionInliner::visit(FunctionDeclaration &func)
311 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
312 TraversingVisitor::visit(func);
313 r_inlined_here = false;
316 void FunctionInliner::visit(Iteration &iter)
318 /* Visit the initialization statement before entering the loop body so the
319 inlined statements get inserted outside. */
320 if(iter.init_statement)
321 iter.init_statement->visit(*this);
323 SetForScope<Block *> set_block(current_block, &iter.body);
324 /* Skip the condition and loop expression parts because they're not properly
325 inside the body block. Inlining anything into them will require a more
326 comprehensive transformation. */
327 iter.body.visit(*this);
331 bool ExpressionInliner::apply(Stage &s)
333 s.content.visit(*this);
335 bool any_inlined = false;
336 for(ExpressionInfo &e: expressions)
337 if(e.expression && (e.trivial || e.uses.size()==1))
339 for(ExpressionUse &u: e.uses)
342 *u.reference = e.expression->clone();
350 void ExpressionInliner::visit(RefPtr<Expression> &expr)
354 if(r_ref_info && r_ref_info->expression)
357 use.reference = &expr;
358 use.ref_scope = current_block;
359 use.blocked = access_write || r_ref_info->blocked;
361 if(iteration_body && !r_ref_info->trivial)
363 /* Block inlining of non-trivial expressions assigned outside an
364 iteration statement. The iteration may run multiple times, which
365 would cause the expression to also be evaluated multiple times. */
366 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
367 use.blocked = (i==r_ref_info->assign_scope);
370 /* Block inlining assignments from from inner scopes. The assignment may
371 depend on local variables of that scope or may not always be executed. */
372 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
373 use.blocked = (i==current_block);
375 r_ref_info->uses.push_back(use);
381 void ExpressionInliner::visit(VariableReference &var)
383 if(var.declaration && access_read)
385 auto i = assignments.find(var.declaration);
386 if(i!=assignments.end())
387 r_ref_info = i->second;
391 void ExpressionInliner::visit(MemberAccess &memacc)
397 void ExpressionInliner::visit(Swizzle &swizzle)
403 void ExpressionInliner::visit(UnaryExpression &unary)
405 SetFlag set_write(access_write, (unary.oper->token[1]=='+' || unary.oper->token[1]=='-'));
406 visit(unary.expression);
410 void ExpressionInliner::visit(BinaryExpression &binary)
414 SetFlag clear_write(access_write, false);
420 void ExpressionInliner::visit(Assignment &assign)
423 SetFlag set_read(access_read, assign.oper->token[0]!='=');
424 SetFlag set_write(access_write);
431 auto i = assignments.find(assign.target.declaration);
432 if(i!=assignments.end())
434 if(iteration_body && i->second && i->second->expression)
436 /* Block inlining into previous references within the iteration
437 statement. On iterations after the first they would refer to the
438 assignment within the iteration. */
439 for(ExpressionUse &u: i->second->uses)
440 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
441 u.blocked = (k==iteration_body);
444 for(; (i!=assignments.end() && i->first.declaration==assign.target.declaration); ++i)
445 if(targets_overlap(i->first, assign.target))
446 i->second->blocked = true;
448 expressions.push_back(ExpressionInfo());
449 ExpressionInfo &info = expressions.back();
450 info.target = assign.target;
451 // Self-referencing assignments can't be inlined without additional work.
452 if(!assign.self_referencing)
453 info.expression = assign.right;
454 info.assign_scope = current_block;
455 info.trivial = r_trivial;
457 assignments[assign.target] = &info;
463 void ExpressionInliner::visit(TernaryExpression &ternary)
465 visit(ternary.condition);
466 visit(ternary.true_expr);
467 visit(ternary.false_expr);
471 void ExpressionInliner::visit(FunctionCall &call)
473 TraversingVisitor::visit(call);
477 void ExpressionInliner::visit(VariableDeclaration &var)
481 TraversingVisitor::visit(var);
483 bool constant = var.constant;
484 if(constant && var.layout)
486 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
487 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
490 /* Only inline global variables if they're constant and have trivial
491 initializers. Non-constant variables could change in ways which are hard to
492 analyze and non-trivial expressions could be expensive to inline. */
493 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
495 expressions.push_back(ExpressionInfo());
496 ExpressionInfo &info = expressions.back();
498 /* Assume variables declared in an iteration initialization statement
499 will have their values change throughout the iteration. */
501 info.expression = var.init_expression;
502 info.assign_scope = current_block;
503 info.trivial = r_trivial;
505 assignments[&var] = &info;
509 void ExpressionInliner::visit(Iteration &iter)
511 SetForScope<Block *> set_block(current_block, &iter.body);
512 if(iter.init_statement)
514 SetFlag set_init(iteration_init);
515 iter.init_statement->visit(*this);
518 SetForScope<Block *> set_body(iteration_body, &iter.body);
520 visit(iter.condition);
521 iter.body.visit(*this);
522 if(iter.loop_expression)
523 visit(iter.loop_expression);
527 bool AggregateDismantler::apply(Stage &stage)
529 stage.content.visit(*this);
531 bool any_dismantled = false;
532 for(const auto &kvp: aggregates)
534 if(kvp.second.referenced || !kvp.second.members_referenced)
537 for(const AggregateMember &m: kvp.second.members)
541 name = format("%s_%s", kvp.second.declaration->name, m.declaration->name);
543 name = format("%s_%d", kvp.second.declaration->name, m.index);
545 VariableDeclaration *var = new VariableDeclaration;
546 var->source = kvp.first->source;
547 var->line = kvp.first->line;
548 var->name = get_unused_variable_name(*kvp.second.decl_scope, name);
549 /* XXX This is kind of brittle and depends on the array declaration's
550 textual type not having brackets in it. */
551 var->type = (m.declaration ? m.declaration : kvp.second.declaration)->type;
553 var->init_expression = m.initializer->clone();
555 kvp.second.decl_scope->body.insert(kvp.second.insert_point, var);
557 for(RefPtr<Expression> *r: m.references)
559 VariableReference *ref = new VariableReference;
560 ref->name = var->name;
564 any_dismantled = true;
568 return any_dismantled;
571 void AggregateDismantler::visit(Block &block)
573 SetForScope<Block *> set_block(current_block, &block);
574 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
581 void AggregateDismantler::visit(RefPtr<Expression> &expr)
585 if(r_aggregate_ref && r_reference.chain_len==1)
587 if((r_reference.chain[0]&0x3F)!=0x3F)
589 r_aggregate_ref->members[r_reference.chain[0]&0x3F].references.push_back(&expr);
590 r_aggregate_ref->members_referenced = true;
593 /* If the accessed member is not known, mark the entire aggregate as
595 r_aggregate_ref->referenced = true;
600 void AggregateDismantler::visit(VariableReference &var)
602 if(composite_reference)
603 r_reference.declaration = var.declaration;
606 /* If an aggregate variable is referenced as a whole, it should not be
608 auto i = aggregates.find(var.declaration);
609 if(i!=aggregates.end())
610 i->second.referenced = true;
614 void AggregateDismantler::visit_composite(RefPtr<Expression> &expr)
616 if(!composite_reference)
617 r_reference = Assignment::Target();
619 SetFlag set_composite(composite_reference);
623 void AggregateDismantler::visit(MemberAccess &memacc)
625 visit_composite(memacc.left);
627 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
629 if(r_reference.declaration && r_reference.chain_len==1)
631 auto i = aggregates.find(r_reference.declaration);
632 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
638 void AggregateDismantler::visit(BinaryExpression &binary)
640 if(binary.oper->token[0]=='[')
642 visit_composite(binary.left);
644 SetFlag clear_composite(composite_reference, false);
648 unsigned index = 0x3F;
649 if(Literal *literal_subscript = dynamic_cast<Literal *>(binary.right.get()))
650 if(literal_subscript->value.check_type<int>())
651 index = literal_subscript->value.value<int>();
652 add_to_chain(r_reference, Assignment::Target::ARRAY, index);
654 if(r_reference.declaration && r_reference.chain_len==1)
656 auto i = aggregates.find(r_reference.declaration);
657 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
664 SetFlag clear_composite(composite_reference, false);
665 TraversingVisitor::visit(binary);
669 void AggregateDismantler::visit(VariableDeclaration &var)
671 TraversingVisitor::visit(var);
673 if(var.interface.empty())
675 if(const StructDeclaration *strct = dynamic_cast<const StructDeclaration *>(var.type_declaration))
677 const FunctionCall *init_call = dynamic_cast<const FunctionCall *>(var.init_expression.get());
678 if((init_call && init_call->constructor) || !var.init_expression)
681 Aggregate &aggre = aggregates[&var];
682 aggre.declaration = &var;
683 aggre.decl_scope = current_block;
684 aggre.insert_point = insert_point;
687 for(const RefPtr<Statement> &s: strct->members.body)
689 if(const VariableDeclaration *mem_decl = dynamic_cast<const VariableDeclaration *>(s.get()))
691 AggregateMember member;
692 member.declaration = mem_decl;
695 member.initializer = init_call->arguments[i];
696 aggre.members.push_back(member);
702 else if(const Literal *literal_size = dynamic_cast<const Literal *>(var.array_size.get()))
704 if(literal_size->value.check_type<int>())
706 Aggregate &aggre = aggregates[&var];
707 aggre.declaration = &var;
708 aggre.decl_scope = current_block;
709 aggre.insert_point = insert_point;
711 int size = literal_size->value.value<int>();
712 for(int i=0; i<size; ++i)
714 AggregateMember member;
716 // Array initializers are not supported yet
717 aggre.members.push_back(member);
724 void AggregateDismantler::visit(FunctionDeclaration &func)
726 func.body.visit(*this);
731 T ConstantFolder::evaluate_logical(char oper, T left, T right)
735 case '&': return left&right;
736 case '|': return left|right;
737 case '^': return left^right;
743 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
745 switch(oper[0]|oper[1])
747 case '<': return left<right;
748 case '<'|'=': return left<=right;
749 case '>': return left>right;
750 case '>'|'=': return left>=right;
751 default: return false;
756 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
760 case '+': return left+right;
761 case '-': return left-right;
762 case '*': return left*right;
763 case '/': return left/right;
769 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
773 case '%': return left%right;
774 case '<': return left<<right;
775 case '>': return left>>right;
781 void ConstantFolder::convert_to_result(const Variant &value)
783 if(value.check_type<bool>())
784 set_result(static_cast<T>(value.value<bool>()));
785 else if(value.check_type<int>())
786 set_result(static_cast<T>(value.value<int>()));
787 else if(value.check_type<unsigned>())
788 set_result(static_cast<T>(value.value<unsigned>()));
789 else if(value.check_type<float>())
790 set_result(static_cast<T>(value.value<float>()));
793 void ConstantFolder::set_result(const Variant &value, bool literal)
795 r_constant_value = value;
800 void ConstantFolder::visit(RefPtr<Expression> &expr)
802 r_constant_value = Variant();
805 r_uses_iter_var = false;
807 /* Don't replace literals since they'd only be replaced with an identical
808 literal. Also skip anything that uses an iteration variable, but pass on
809 the result so the Iteration visiting function can handle it. */
810 if(!r_constant || r_literal || r_uses_iter_var)
813 RefPtr<Literal> literal = new Literal;
814 if(r_constant_value.check_type<bool>())
815 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
816 else if(r_constant_value.check_type<int>())
817 literal->token = lexical_cast<string>(r_constant_value.value<int>());
818 else if(r_constant_value.check_type<unsigned>())
819 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
820 else if(r_constant_value.check_type<float>())
822 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
823 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
824 literal->token += ".0";
831 literal->value = r_constant_value;
836 void ConstantFolder::visit(Literal &literal)
838 set_result(literal.value, true);
841 void ConstantFolder::visit(VariableReference &var)
843 /* If an iteration variable is initialized with a constant value, return
844 that value here for the purpose of evaluating the loop condition for the
846 if(var.declaration==iteration_var)
848 set_result(iter_init_value);
849 r_uses_iter_var = true;
853 void ConstantFolder::visit(MemberAccess &memacc)
855 TraversingVisitor::visit(memacc);
859 void ConstantFolder::visit(Swizzle &swizzle)
861 TraversingVisitor::visit(swizzle);
865 void ConstantFolder::visit(UnaryExpression &unary)
867 TraversingVisitor::visit(unary);
868 bool can_fold = r_constant;
873 char oper = unary.oper->token[0];
874 char oper2 = unary.oper->token[1];
877 if(r_constant_value.check_type<bool>())
878 set_result(!r_constant_value.value<bool>());
882 if(r_constant_value.check_type<int>())
883 set_result(~r_constant_value.value<int>());
884 else if(r_constant_value.check_type<unsigned>())
885 set_result(~r_constant_value.value<unsigned>());
887 else if(oper=='-' && !oper2)
889 if(r_constant_value.check_type<int>())
890 set_result(-r_constant_value.value<int>());
891 else if(r_constant_value.check_type<unsigned>())
892 set_result(-r_constant_value.value<unsigned>());
893 else if(r_constant_value.check_type<float>())
894 set_result(-r_constant_value.value<float>());
898 void ConstantFolder::visit(BinaryExpression &binary)
901 bool left_constant = r_constant;
902 bool left_iter_var = r_uses_iter_var;
903 Variant left_value = r_constant_value;
906 r_uses_iter_var = true;
908 bool can_fold = (left_constant && r_constant);
913 // Currently only expressions with both sides of equal types are handled.
914 if(!left_value.check_same_type(r_constant_value))
917 char oper = binary.oper->token[0];
918 char oper2 = binary.oper->token[1];
919 if(oper=='&' || oper=='|' || oper=='^')
921 if(oper2==oper && left_value.check_type<bool>())
922 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
923 else if(!oper2 && left_value.check_type<int>())
924 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
925 else if(!oper2 && left_value.check_type<unsigned>())
926 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
928 else if((oper=='<' || oper=='>') && oper2!=oper)
930 if(left_value.check_type<int>())
931 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
932 else if(left_value.check_type<unsigned>())
933 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
934 else if(left_value.check_type<float>())
935 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
937 else if((oper=='=' || oper=='!') && oper2=='=')
939 if(left_value.check_type<int>())
940 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
941 else if(left_value.check_type<unsigned>())
942 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
943 else if(left_value.check_type<float>())
944 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
946 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
948 if(left_value.check_type<int>())
949 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
950 else if(left_value.check_type<unsigned>())
951 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
952 else if(left_value.check_type<float>())
953 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
955 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
957 if(left_value.check_type<int>())
958 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
959 else if(left_value.check_type<unsigned>())
960 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
964 void ConstantFolder::visit(Assignment &assign)
966 TraversingVisitor::visit(assign);
970 void ConstantFolder::visit(TernaryExpression &ternary)
972 TraversingVisitor::visit(ternary);
976 void ConstantFolder::visit(FunctionCall &call)
978 if(call.constructor && call.type && call.arguments.size()==1)
980 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
983 visit(call.arguments[0]);
984 bool can_fold = r_constant;
989 if(basic->kind==BasicTypeDeclaration::BOOL)
990 convert_to_result<bool>(r_constant_value);
991 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
992 convert_to_result<int>(r_constant_value);
993 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
994 convert_to_result<unsigned>(r_constant_value);
995 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
996 convert_to_result<float>(r_constant_value);
1002 TraversingVisitor::visit(call);
1006 void ConstantFolder::visit(VariableDeclaration &var)
1008 if(iteration_init && var.init_expression)
1010 visit(var.init_expression);
1013 /* Record the value of a constant initialization expression of an
1014 iteration, so it can be used to evaluate the loop condition. */
1015 iteration_var = &var;
1016 iter_init_value = r_constant_value;
1020 TraversingVisitor::visit(var);
1023 void ConstantFolder::visit(Iteration &iter)
1025 SetForScope<Block *> set_block(current_block, &iter.body);
1027 /* The iteration variable is not normally inlined into expressions, so we
1028 process it specially here. If the initial value causes the loop condition
1029 to evaluate to false, then the expression can be folded. */
1031 if(iter.init_statement)
1033 SetFlag set_init(iteration_init);
1034 iter.init_statement->visit(*this);
1039 visit(iter.condition);
1040 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1042 RefPtr<Literal> literal = new Literal;
1043 literal->token = "false";
1044 literal->value = r_constant_value;
1045 iter.condition = literal;
1050 iter.body.visit(*this);
1051 if(iter.loop_expression)
1052 visit(iter.loop_expression);
1056 void ConstantConditionEliminator::apply(Stage &stage)
1058 stage.content.visit(*this);
1059 NodeRemover().apply(stage, nodes_to_remove);
1062 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1064 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1065 if(literal->value.check_type<bool>())
1066 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1067 return NOT_CONSTANT;
1070 void ConstantConditionEliminator::visit(Block &block)
1072 SetForScope<Block *> set_block(current_block, &block);
1073 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1080 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1082 r_ternary_result = 0;
1084 if(r_ternary_result)
1085 expr = r_ternary_result;
1086 r_ternary_result = 0;
1089 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1091 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1092 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1094 auto i = current_block->variables.find(var->name);
1095 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1099 TraversingVisitor::visit(unary);
1102 void ConstantConditionEliminator::visit(Assignment &assign)
1104 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1105 if(i==current_block->variables.end())
1106 r_external_side_effects = true;
1107 TraversingVisitor::visit(assign);
1110 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1112 ConstantStatus result = check_constant_condition(*ternary.condition);
1113 if(result!=NOT_CONSTANT)
1114 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1116 r_ternary_result = 0;
1119 void ConstantConditionEliminator::visit(FunctionCall &call)
1121 r_external_side_effects = true;
1122 TraversingVisitor::visit(call);
1125 void ConstantConditionEliminator::visit(Conditional &cond)
1127 ConstantStatus result = check_constant_condition(*cond.condition);
1128 if(result!=NOT_CONSTANT)
1130 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1131 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1132 current_block->body.splice(insert_point, block.body);
1133 nodes_to_remove.insert(&cond);
1137 r_external_side_effects = false;
1138 TraversingVisitor::visit(cond);
1140 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1141 nodes_to_remove.insert(&cond);
1144 void ConstantConditionEliminator::visit(Iteration &iter)
1148 ConstantStatus result = check_constant_condition(*iter.condition);
1149 if(result==CONSTANT_FALSE)
1151 nodes_to_remove.insert(&iter);
1156 r_external_side_effects = false;
1157 TraversingVisitor::visit(iter);
1158 if(iter.body.body.empty() && !r_external_side_effects)
1159 nodes_to_remove.insert(&iter);
1163 bool UnreachableCodeRemover::apply(Stage &stage)
1165 stage.content.visit(*this);
1166 NodeRemover().apply(stage, unreachable_nodes);
1167 return !unreachable_nodes.empty();
1170 void UnreachableCodeRemover::visit(Block &block)
1172 auto i = block.body.begin();
1173 for(; (reachable && i!=block.body.end()); ++i)
1175 for(; i!=block.body.end(); ++i)
1176 unreachable_nodes.insert(i->get());
1179 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1181 TraversingVisitor::visit(func);
1185 void UnreachableCodeRemover::visit(Conditional &cond)
1187 cond.body.visit(*this);
1188 bool reachable_if_true = reachable;
1190 cond.else_body.visit(*this);
1192 reachable |= reachable_if_true;
1195 void UnreachableCodeRemover::visit(Iteration &iter)
1197 TraversingVisitor::visit(iter);
1199 /* Always consider code after a loop reachable, since there's no checking
1200 for whether the loop executes. */
1205 bool UnusedTypeRemover::apply(Stage &stage)
1207 stage.content.visit(*this);
1208 NodeRemover().apply(stage, unused_nodes);
1209 return !unused_nodes.empty();
1212 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1214 unused_nodes.erase(expr->type);
1215 TraversingVisitor::visit(expr);
1218 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1221 unused_nodes.erase(type.base_type);
1222 unused_nodes.insert(&type);
1225 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1228 unused_nodes.erase(type.base_type);
1229 unused_nodes.insert(&type);
1232 void UnusedTypeRemover::visit(StructDeclaration &strct)
1234 unused_nodes.insert(&strct);
1235 TraversingVisitor::visit(strct);
1238 void UnusedTypeRemover::visit(VariableDeclaration &var)
1240 unused_nodes.erase(var.type_declaration);
1241 TraversingVisitor::visit(var);
1244 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1246 unused_nodes.erase(iface.type_declaration);
1249 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1251 unused_nodes.erase(func.return_type_declaration);
1252 TraversingVisitor::visit(func);
1256 bool UnusedVariableRemover::apply(Stage &s)
1259 s.content.visit(*this);
1261 for(const AssignmentInfo &a: assignments)
1262 if(a.used_by.empty())
1263 unused_nodes.insert(a.node);
1265 for(const auto &kvp: variables)
1267 if(!kvp.second.referenced)
1268 unused_nodes.insert(kvp.first);
1269 else if(kvp.second.output)
1271 /* The last visible assignments of output variables are used by the
1272 next stage or the API. */
1273 for(AssignmentInfo *a: kvp.second.assignments)
1274 unused_nodes.erase(a->node);
1278 NodeRemover().apply(s, unused_nodes);
1280 return !unused_nodes.empty();
1283 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1285 VariableInfo &var_info = variables[target.declaration];
1286 var_info.referenced = true;
1287 if(!assignment_target)
1289 bool loop_external = false;
1290 for(AssignmentInfo *a: var_info.assignments)
1291 if(targets_overlap(a->target, target))
1293 a->used_by.push_back(&node);
1294 if(a->in_loop<in_loop)
1295 loop_external = true;
1299 loop_ext_refs.push_back(&node);
1303 void UnusedVariableRemover::visit(VariableReference &var)
1305 if(composite_reference)
1306 r_reference.declaration = var.declaration;
1307 else if(var.declaration)
1308 referenced(var.declaration, var);
1311 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1313 if(composite_reference)
1314 r_reference.declaration = iface.declaration;
1315 else if(iface.declaration)
1316 referenced(iface.declaration, iface);
1319 void UnusedVariableRemover::visit_composite(Expression &expr)
1321 if(!composite_reference)
1322 r_reference = Assignment::Target();
1324 SetFlag set_composite(composite_reference);
1328 void UnusedVariableRemover::visit(MemberAccess &memacc)
1330 visit_composite(*memacc.left);
1332 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1334 if(!composite_reference && r_reference.declaration)
1335 referenced(r_reference, memacc);
1338 void UnusedVariableRemover::visit(Swizzle &swizzle)
1340 visit_composite(*swizzle.left);
1343 for(unsigned i=0; i<swizzle.count; ++i)
1344 mask |= 1<<swizzle.components[i];
1345 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1347 if(!composite_reference && r_reference.declaration)
1348 referenced(r_reference, swizzle);
1351 void UnusedVariableRemover::visit(UnaryExpression &unary)
1353 TraversingVisitor::visit(unary);
1354 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1355 r_side_effects = true;
1358 void UnusedVariableRemover::visit(BinaryExpression &binary)
1360 if(binary.oper->token[0]=='[')
1362 visit_composite(*binary.left);
1365 SetFlag clear_assignment(assignment_target, false);
1366 SetFlag clear_composite(composite_reference, false);
1367 SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1368 binary.right->visit(*this);
1371 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1373 if(!composite_reference && r_reference.declaration)
1374 referenced(r_reference, binary);
1378 SetFlag clear_composite(composite_reference, false);
1379 TraversingVisitor::visit(binary);
1383 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1385 SetFlag clear_composite(composite_reference, false);
1386 TraversingVisitor::visit(ternary);
1389 void UnusedVariableRemover::visit(Assignment &assign)
1392 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1393 assign.left->visit(*this);
1395 assign.right->visit(*this);
1396 r_assignment = &assign;
1397 r_side_effects = true;
1400 void UnusedVariableRemover::visit(FunctionCall &call)
1402 SetFlag clear_composite(composite_reference, false);
1403 TraversingVisitor::visit(call);
1404 /* Treat function calls as having side effects so expression statements
1405 consisting of nothing but a function call won't be optimized away. */
1406 r_side_effects = true;
1408 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1410 for(const auto &kvp: variables)
1411 if(kvp.second.output)
1412 referenced(kvp.first, call);
1416 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1418 assignments.push_back(AssignmentInfo());
1419 AssignmentInfo &assign_info = assignments.back();
1420 assign_info.node = &node;
1421 assign_info.target = target;
1422 assign_info.in_loop = in_loop;
1424 /* An assignment to the target hides any assignments to the same target or
1426 VariableInfo &var_info = variables[target.declaration];
1427 for(unsigned i=0; i<var_info.assignments.size(); )
1429 const Assignment::Target &t = var_info.assignments[i]->target;
1431 bool subfield = (t.chain_len>=target.chain_len);
1432 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1433 subfield = (t.chain[j]==target.chain[j]);
1436 var_info.assignments.erase(var_info.assignments.begin()+i);
1441 var_info.assignments.push_back(&assign_info);
1444 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1447 r_side_effects = false;
1448 TraversingVisitor::visit(expr);
1449 if(r_assignment && r_assignment->target.declaration)
1450 record_assignment(r_assignment->target, expr);
1452 unused_nodes.insert(&expr);
1455 void UnusedVariableRemover::visit(StructDeclaration &strct)
1457 SetFlag set_struct(in_struct);
1458 TraversingVisitor::visit(strct);
1461 void UnusedVariableRemover::visit(VariableDeclaration &var)
1463 TraversingVisitor::visit(var);
1468 VariableInfo &var_info = variables[&var];
1470 /* Mark variables as output if they're used by the next stage or the
1472 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1474 // Linked outputs are automatically referenced.
1475 if(var_info.output && var.linked_declaration)
1476 var_info.referenced = true;
1478 if(var.init_expression)
1480 var_info.initialized = true;
1481 record_assignment(&var, *var.init_expression);
1485 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1487 VariableInfo &var_info = variables[&iface];
1488 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1491 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1493 for(const auto &kvp: other_vars)
1495 auto j = variables.find(kvp.first);
1496 if(j!=variables.end())
1498 /* The merged blocks started as copies of each other so any common
1499 assignments must be in the beginning. */
1501 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1502 if(kvp.second.assignments[k]!=j->second.assignments[k])
1505 // Remaining assignments are unique to each block; merge them.
1506 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1507 j->second.referenced |= kvp.second.referenced;
1510 variables.insert(kvp);
1514 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1516 if(func.body.body.empty())
1519 BlockVariableMap saved_vars = variables;
1520 // Assignments from other functions should not be visible.
1521 for(auto &kvp: variables)
1522 kvp.second.assignments.resize(kvp.second.initialized);
1523 TraversingVisitor::visit(func);
1524 swap(variables, saved_vars);
1525 merge_variables(saved_vars);
1527 /* Always treat function parameters as referenced. Removing unused
1528 parameters is not currently supported. */
1529 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1531 auto j = variables.find(p.get());
1532 if(j!=variables.end())
1533 j->second.referenced = true;
1537 void UnusedVariableRemover::visit(Conditional &cond)
1539 cond.condition->visit(*this);
1540 BlockVariableMap saved_vars = variables;
1541 cond.body.visit(*this);
1542 swap(saved_vars, variables);
1543 cond.else_body.visit(*this);
1545 /* Visible assignments after the conditional is the union of those visible
1546 at the end of the if and else blocks. If there was no else block, then it's
1547 the union of the if block and the state before it. */
1548 merge_variables(saved_vars);
1551 void UnusedVariableRemover::visit(Iteration &iter)
1553 BlockVariableMap saved_vars = variables;
1554 vector<Node *> saved_refs;
1555 swap(loop_ext_refs, saved_refs);
1557 if(iter.init_statement)
1558 iter.init_statement->visit(*this);
1559 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1561 iter.condition->visit(*this);
1562 iter.body.visit(*this);
1563 if(iter.loop_expression)
1564 iter.loop_expression->visit(*this);
1566 swap(loop_ext_refs, saved_refs);
1568 /* Visit the external references of the loop again to record assignments
1569 done in the loop as used. */
1570 for(Node *n: saved_refs)
1573 /* Merge assignments from the iteration, without clearing previous state.
1574 Further analysis is needed to determine which parts of the iteration body
1575 are always executed, if any. */
1576 merge_variables(saved_vars);
1580 bool UnusedFunctionRemover::apply(Stage &stage)
1582 stage.content.visit(*this);
1583 NodeRemover().apply(stage, unused_nodes);
1584 return !unused_nodes.empty();
1587 void UnusedFunctionRemover::visit(FunctionCall &call)
1589 TraversingVisitor::visit(call);
1591 unused_nodes.erase(call.declaration);
1592 if(call.declaration && call.declaration->definition!=call.declaration)
1593 used_definitions.insert(call.declaration->definition);
1596 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1598 TraversingVisitor::visit(func);
1600 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1601 unused_nodes.insert(&func);