1 #include <msp/core/algorithm.h>
2 #include <msp/core/raii.h>
3 #include <msp/strings/format.h>
4 #include <msp/strings/utils.h>
14 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
17 stage.content.visit(*this);
20 void ConstantSpecializer::visit(VariableDeclaration &var)
22 bool specializable = false;
25 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
26 auto i = find_member(qualifiers, string("constant_id"), &Layout::Qualifier::name);
27 if(i!=qualifiers.end())
31 if(qualifiers.empty())
38 auto i = values->find(var.name);
41 RefPtr<Literal> literal = new Literal;
44 literal->token = (i->second ? "true" : "false");
45 literal->value = static_cast<bool>(i->second);
47 else if(var.type=="int")
49 literal->token = lexical_cast<string>(i->second);
50 literal->value = i->second;
52 var.init_expression = literal;
58 void InlineableFunctionLocator::visit(FunctionCall &call)
60 FunctionDeclaration *def = call.declaration;
62 def = def->definition;
66 unsigned &count = refcounts[def];
68 /* Don't inline functions which are called more than once or are called
70 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
71 inlineable.erase(def);
74 TraversingVisitor::visit(call);
77 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
79 bool has_out_params = any_of(func.parameters.begin(), func.parameters.end(),
80 [](const RefPtr<VariableDeclaration> &p){ return p->interface=="out"; });
82 unsigned &count = refcounts[func.definition];
83 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
84 inlineable.insert(func.definition);
86 SetForScope<FunctionDeclaration *> set(current_function, &func);
88 TraversingVisitor::visit(func);
91 void InlineableFunctionLocator::visit(Conditional &cond)
93 TraversingVisitor::visit(cond);
94 inlineable.erase(current_function);
97 void InlineableFunctionLocator::visit(Iteration &iter)
99 TraversingVisitor::visit(iter);
100 inlineable.erase(current_function);
103 void InlineableFunctionLocator::visit(Return &ret)
105 TraversingVisitor::visit(ret);
107 inlineable.erase(current_function);
112 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
114 source_func = call.declaration->definition;
116 /* Populate referenced_names from the target function so we can rename
117 variables from the inlined function that would conflict. */
119 target_func.visit(*this);
121 /* Inline and rename passes must be interleaved so used variable names are
122 known when inlining the return statement. */
124 staging_block.parent = &tgt_blk;
125 staging_block.variables.clear();
127 vector<RefPtr<VariableDeclaration> > params;
128 params.reserve(source_func->parameters.size());
129 for(const RefPtr<VariableDeclaration> &p: source_func->parameters)
131 RefPtr<VariableDeclaration> var = p->clone();
132 var->interface.clear();
134 SetForScope<Pass> set_pass(pass, RENAME);
137 staging_block.body.push_back_nocopy(var);
138 params.push_back(var);
141 for(const RefPtr<Statement> &s: source_func->body.body)
143 r_inlined_statement = 0;
145 if(!r_inlined_statement)
146 r_inlined_statement = s->clone();
148 SetForScope<Pass> set_pass(pass, RENAME);
149 r_inlined_statement->visit(*this);
151 staging_block.body.push_back_nocopy(r_inlined_statement);
154 /* Now collect names from the staging block. Local variables that would
155 have conflicted with the target function were renamed earlier. */
157 referenced_names.clear();
158 staging_block.variables.clear();
159 staging_block.visit(*this);
161 /* Rename variables in the target function so they don't interfere with
162 global identifiers used by the source function. */
164 staging_block.parent = source_func->body.parent;
165 target_func.visit(*this);
167 // Put the argument expressions in place after all renaming has been done.
168 for(unsigned i=0; i<source_func->parameters.size(); ++i)
169 params[i]->init_expression = call.arguments[i]->clone();
171 tgt_blk.body.splice(ins_pt, staging_block.body);
173 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
175 return r_result_name;
178 void InlineContentInjector::visit(VariableReference &var)
182 auto i = staging_block.variables.find(var.name);
183 if(i!=staging_block.variables.end())
184 var.name = i->second->name;
186 else if(pass==REFERENCED)
187 referenced_names.insert(var.name);
190 void InlineContentInjector::visit(InterfaceBlockReference &iface)
193 referenced_names.insert(iface.name);
196 void InlineContentInjector::visit(FunctionCall &call)
199 referenced_names.insert(call.name);
200 TraversingVisitor::visit(call);
203 void InlineContentInjector::visit(VariableDeclaration &var)
205 TraversingVisitor::visit(var);
209 /* Check against conflicts with the other context as well as variables
210 already renamed here. */
211 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
212 staging_block.variables[var.name] = &var;
215 string mapped_name = get_unused_variable_name(staging_block, var.name);
216 if(mapped_name!=var.name)
218 staging_block.variables[mapped_name] = &var;
219 var.name = mapped_name;
223 else if(pass==REFERENCED)
224 referenced_names.insert(var.type);
227 void InlineContentInjector::visit(Return &ret)
229 TraversingVisitor::visit(ret);
231 if(pass==INLINE && ret.expression)
233 // Create a new variable to hold the return value of the inlined function.
234 r_result_name = get_unused_variable_name(staging_block, "_return");
235 RefPtr<VariableDeclaration> var = new VariableDeclaration;
236 var->source = ret.source;
237 var->line = ret.line;
238 var->type = source_func->return_type;
239 var->name = r_result_name;
240 var->init_expression = ret.expression->clone();
241 r_inlined_statement = var;
246 bool FunctionInliner::apply(Stage &s)
249 inlineable = InlineableFunctionLocator().apply(s);
250 r_any_inlined = false;
251 s.content.visit(*this);
252 return r_any_inlined;
255 void FunctionInliner::visit(RefPtr<Expression> &ptr)
261 ptr = r_inline_result;
262 r_any_inlined = true;
267 void FunctionInliner::visit(Block &block)
269 SetForScope<Block *> set_block(current_block, &block);
270 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
271 for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
278 void FunctionInliner::visit(FunctionCall &call)
280 for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
286 FunctionDeclaration *def = call.declaration;
288 def = def->definition;
290 if(def && inlineable.count(def))
292 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
294 // This will later get removed by UnusedVariableRemover.
295 if(result_name.empty())
296 result_name = "_msp_unused_from_inline";
298 RefPtr<VariableReference> ref = new VariableReference;
299 ref->name = result_name;
300 r_inline_result = ref;
302 /* Inlined variables need to be resolved before this function can be
304 inlineable.erase(current_function);
305 r_inlined_here = true;
309 void FunctionInliner::visit(FunctionDeclaration &func)
311 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
312 TraversingVisitor::visit(func);
313 r_inlined_here = false;
316 void FunctionInliner::visit(Iteration &iter)
318 /* Visit the initialization statement before entering the loop body so the
319 inlined statements get inserted outside. */
320 if(iter.init_statement)
321 iter.init_statement->visit(*this);
323 SetForScope<Block *> set_block(current_block, &iter.body);
324 /* Skip the condition and loop expression parts because they're not properly
325 inside the body block. Inlining anything into them will require a more
326 comprehensive transformation. */
327 iter.body.visit(*this);
331 bool ExpressionInliner::apply(Stage &s)
333 s.content.visit(*this);
335 bool any_inlined = false;
336 for(ExpressionInfo &e: expressions)
337 if(e.expression && (e.trivial || e.uses.size()==1))
339 for(ExpressionUse &u: e.uses)
342 *u.reference = e.expression->clone();
350 void ExpressionInliner::visit(RefPtr<Expression> &expr)
354 if(r_ref_info && r_ref_info->expression)
357 use.reference = &expr;
358 use.ref_scope = current_block;
359 use.blocked = access_write;
361 if(iteration_body && !r_ref_info->trivial)
363 /* Block inlining of non-trivial expressions assigned outside an
364 iteration statement. The iteration may run multiple times, which
365 would cause the expression to also be evaluated multiple times. */
366 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
367 use.blocked = (i==r_ref_info->assign_scope);
370 /* Block inlining assignments from from inner scopes. The assignment may
371 depend on local variables of that scope or may not always be executed. */
372 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
373 use.blocked = (i==current_block);
375 r_ref_info->uses.push_back(use);
381 void ExpressionInliner::visit(VariableReference &var)
383 if(var.declaration && access_read)
385 auto i = assignments.find(var.declaration);
386 if(i!=assignments.end())
387 r_ref_info = i->second;
391 void ExpressionInliner::visit(MemberAccess &memacc)
397 void ExpressionInliner::visit(Swizzle &swizzle)
403 void ExpressionInliner::visit(UnaryExpression &unary)
405 SetFlag set_write(access_write, access_write || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
406 visit(unary.expression);
410 void ExpressionInliner::visit(BinaryExpression &binary)
414 SetFlag clear_write(access_write, false);
420 void ExpressionInliner::visit(Assignment &assign)
423 SetFlag set_read(access_read, assign.oper->token[0]!='=');
424 SetFlag set_write(access_write);
431 auto i = assignments.find(assign.target);
432 if(i!=assignments.end())
434 if(iteration_body && i->second->expression)
436 /* Block inlining into previous references within the iteration
437 statement. On iterations after the first they would refer to the
438 assignment within the iteration. */
439 for(ExpressionUse &u: i->second->uses)
440 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
441 u.blocked = (k==iteration_body);
444 expressions.push_back(ExpressionInfo());
445 ExpressionInfo &info = expressions.back();
446 info.target = assign.target;
447 // Self-referencing assignments can't be inlined without additional work.
448 if(!assign.self_referencing)
449 info.expression = assign.right;
450 info.assign_scope = current_block;
451 info.trivial = r_trivial;
459 void ExpressionInliner::visit(TernaryExpression &ternary)
461 visit(ternary.condition);
462 visit(ternary.true_expr);
463 visit(ternary.false_expr);
467 void ExpressionInliner::visit(FunctionCall &call)
469 TraversingVisitor::visit(call);
473 void ExpressionInliner::visit(VariableDeclaration &var)
477 TraversingVisitor::visit(var);
479 bool constant = var.constant;
480 if(constant && var.layout)
482 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
483 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
486 /* Only inline global variables if they're constant and have trivial
487 initializers. Non-constant variables could change in ways which are hard to
488 analyze and non-trivial expressions could be expensive to inline. */
489 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
491 expressions.push_back(ExpressionInfo());
492 ExpressionInfo &info = expressions.back();
494 /* Assume variables declared in an iteration initialization statement
495 will have their values change throughout the iteration. */
497 info.expression = var.init_expression;
498 info.assign_scope = current_block;
499 info.trivial = r_trivial;
501 assignments[&var] = &info;
505 void ExpressionInliner::visit(Iteration &iter)
507 SetForScope<Block *> set_block(current_block, &iter.body);
508 if(iter.init_statement)
510 SetFlag set_init(iteration_init);
511 iter.init_statement->visit(*this);
514 SetForScope<Block *> set_body(iteration_body, &iter.body);
516 visit(iter.condition);
517 iter.body.visit(*this);
518 if(iter.loop_expression)
519 visit(iter.loop_expression);
523 bool AggregateDismantler::apply(Stage &stage)
525 stage.content.visit(*this);
527 bool any_dismantled = false;
528 for(const auto &kvp: aggregates)
530 if(kvp.second.referenced || !kvp.second.members_referenced)
533 for(const AggregateMember &m: kvp.second.members)
537 name = format("%s_%s", kvp.second.declaration->name, m.declaration->name);
539 name = format("%s_%d", kvp.second.declaration->name, m.index);
541 VariableDeclaration *var = new VariableDeclaration;
542 var->source = kvp.first->source;
543 var->line = kvp.first->line;
544 var->name = get_unused_variable_name(*kvp.second.decl_scope, name);
545 /* XXX This is kind of brittle and depends on the array declaration's
546 textual type not having brackets in it. */
547 var->type = (m.declaration ? m.declaration : kvp.second.declaration)->type;
549 var->init_expression = m.initializer->clone();
551 kvp.second.decl_scope->body.insert(kvp.second.insert_point, var);
553 for(RefPtr<Expression> *r: m.references)
555 VariableReference *ref = new VariableReference;
556 ref->name = var->name;
560 any_dismantled = true;
564 return any_dismantled;
567 void AggregateDismantler::visit(Block &block)
569 SetForScope<Block *> set_block(current_block, &block);
570 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
577 void AggregateDismantler::visit(RefPtr<Expression> &expr)
581 if(r_aggregate_ref && r_reference.chain_len==1)
583 if((r_reference.chain[0]&0x3F)!=0x3F)
585 r_aggregate_ref->members[r_reference.chain[0]&0x3F].references.push_back(&expr);
586 r_aggregate_ref->members_referenced = true;
589 /* If the accessed member is not known, mark the entire aggregate as
591 r_aggregate_ref->referenced = true;
596 void AggregateDismantler::visit(VariableReference &var)
598 if(composite_reference)
599 r_reference.declaration = var.declaration;
602 /* If an aggregate variable is referenced as a whole, it should not be
604 auto i = aggregates.find(var.declaration);
605 if(i!=aggregates.end())
606 i->second.referenced = true;
610 void AggregateDismantler::visit_composite(RefPtr<Expression> &expr)
612 if(!composite_reference)
613 r_reference = Assignment::Target();
615 SetFlag set_composite(composite_reference);
619 void AggregateDismantler::visit(MemberAccess &memacc)
621 visit_composite(memacc.left);
623 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
625 if(r_reference.declaration && r_reference.chain_len==1)
627 auto i = aggregates.find(r_reference.declaration);
628 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
634 void AggregateDismantler::visit(BinaryExpression &binary)
636 if(binary.oper->token[0]=='[')
638 visit_composite(binary.left);
640 SetFlag clear_composite(composite_reference, false);
644 unsigned index = 0x3F;
645 if(Literal *literal_subscript = dynamic_cast<Literal *>(binary.right.get()))
646 if(literal_subscript->value.check_type<int>())
647 index = literal_subscript->value.value<int>();
648 add_to_chain(r_reference, Assignment::Target::ARRAY, index);
650 if(r_reference.declaration && r_reference.chain_len==1)
652 auto i = aggregates.find(r_reference.declaration);
653 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
660 SetFlag clear_composite(composite_reference, false);
661 TraversingVisitor::visit(binary);
665 void AggregateDismantler::visit(VariableDeclaration &var)
667 TraversingVisitor::visit(var);
669 if(var.interface.empty())
671 if(const StructDeclaration *strct = dynamic_cast<const StructDeclaration *>(var.type_declaration))
673 const FunctionCall *init_call = dynamic_cast<const FunctionCall *>(var.init_expression.get());
674 if((init_call && init_call->constructor) || !var.init_expression)
677 Aggregate &aggre = aggregates[&var];
678 aggre.declaration = &var;
679 aggre.decl_scope = current_block;
680 aggre.insert_point = insert_point;
683 for(const RefPtr<Statement> &s: strct->members.body)
685 if(const VariableDeclaration *mem_decl = dynamic_cast<const VariableDeclaration *>(s.get()))
687 AggregateMember member;
688 member.declaration = mem_decl;
691 member.initializer = init_call->arguments[i];
692 aggre.members.push_back(member);
698 else if(const Literal *literal_size = dynamic_cast<const Literal *>(var.array_size.get()))
700 if(literal_size->value.check_type<int>())
702 Aggregate &aggre = aggregates[&var];
703 aggre.declaration = &var;
704 aggre.decl_scope = current_block;
705 aggre.insert_point = insert_point;
707 int size = literal_size->value.value<int>();
708 for(int i=0; i<size; ++i)
710 AggregateMember member;
712 // Array initializers are not supported yet
713 aggre.members.push_back(member);
720 void AggregateDismantler::visit(FunctionDeclaration &func)
722 func.body.visit(*this);
727 T ConstantFolder::evaluate_logical(char oper, T left, T right)
731 case '&': return left&right;
732 case '|': return left|right;
733 case '^': return left^right;
739 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
741 switch(oper[0]|oper[1])
743 case '<': return left<right;
744 case '<'|'=': return left<=right;
745 case '>': return left>right;
746 case '>'|'=': return left>=right;
747 default: return false;
752 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
756 case '+': return left+right;
757 case '-': return left-right;
758 case '*': return left*right;
759 case '/': return left/right;
765 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
769 case '%': return left%right;
770 case '<': return left<<right;
771 case '>': return left>>right;
777 void ConstantFolder::convert_to_result(const Variant &value)
779 if(value.check_type<bool>())
780 set_result(static_cast<T>(value.value<bool>()));
781 else if(value.check_type<int>())
782 set_result(static_cast<T>(value.value<int>()));
783 else if(value.check_type<unsigned>())
784 set_result(static_cast<T>(value.value<unsigned>()));
785 else if(value.check_type<float>())
786 set_result(static_cast<T>(value.value<float>()));
789 void ConstantFolder::set_result(const Variant &value, bool literal)
791 r_constant_value = value;
796 void ConstantFolder::visit(RefPtr<Expression> &expr)
798 r_constant_value = Variant();
801 r_uses_iter_var = false;
803 /* Don't replace literals since they'd only be replaced with an identical
804 literal. Also skip anything that uses an iteration variable, but pass on
805 the result so the Iteration visiting function can handle it. */
806 if(!r_constant || r_literal || r_uses_iter_var)
809 RefPtr<Literal> literal = new Literal;
810 if(r_constant_value.check_type<bool>())
811 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
812 else if(r_constant_value.check_type<int>())
813 literal->token = lexical_cast<string>(r_constant_value.value<int>());
814 else if(r_constant_value.check_type<unsigned>())
815 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
816 else if(r_constant_value.check_type<float>())
818 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
819 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
820 literal->token += ".0";
827 literal->value = r_constant_value;
832 void ConstantFolder::visit(Literal &literal)
834 set_result(literal.value, true);
837 void ConstantFolder::visit(VariableReference &var)
839 /* If an iteration variable is initialized with a constant value, return
840 that value here for the purpose of evaluating the loop condition for the
842 if(var.declaration==iteration_var)
844 set_result(iter_init_value);
845 r_uses_iter_var = true;
849 void ConstantFolder::visit(MemberAccess &memacc)
851 TraversingVisitor::visit(memacc);
855 void ConstantFolder::visit(Swizzle &swizzle)
857 TraversingVisitor::visit(swizzle);
861 void ConstantFolder::visit(UnaryExpression &unary)
863 TraversingVisitor::visit(unary);
864 bool can_fold = r_constant;
869 char oper = unary.oper->token[0];
870 char oper2 = unary.oper->token[1];
873 if(r_constant_value.check_type<bool>())
874 set_result(!r_constant_value.value<bool>());
878 if(r_constant_value.check_type<int>())
879 set_result(~r_constant_value.value<int>());
880 else if(r_constant_value.check_type<unsigned>())
881 set_result(~r_constant_value.value<unsigned>());
883 else if(oper=='-' && !oper2)
885 if(r_constant_value.check_type<int>())
886 set_result(-r_constant_value.value<int>());
887 else if(r_constant_value.check_type<unsigned>())
888 set_result(-r_constant_value.value<unsigned>());
889 else if(r_constant_value.check_type<float>())
890 set_result(-r_constant_value.value<float>());
894 void ConstantFolder::visit(BinaryExpression &binary)
897 bool left_constant = r_constant;
898 bool left_iter_var = r_uses_iter_var;
899 Variant left_value = r_constant_value;
902 r_uses_iter_var = true;
904 bool can_fold = (left_constant && r_constant);
909 // Currently only expressions with both sides of equal types are handled.
910 if(!left_value.check_same_type(r_constant_value))
913 char oper = binary.oper->token[0];
914 char oper2 = binary.oper->token[1];
915 if(oper=='&' || oper=='|' || oper=='^')
917 if(oper2==oper && left_value.check_type<bool>())
918 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
919 else if(!oper2 && left_value.check_type<int>())
920 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
921 else if(!oper2 && left_value.check_type<unsigned>())
922 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
924 else if((oper=='<' || oper=='>') && oper2!=oper)
926 if(left_value.check_type<int>())
927 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
928 else if(left_value.check_type<unsigned>())
929 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
930 else if(left_value.check_type<float>())
931 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
933 else if((oper=='=' || oper=='!') && oper2=='=')
935 if(left_value.check_type<int>())
936 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
937 else if(left_value.check_type<unsigned>())
938 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
939 else if(left_value.check_type<float>())
940 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
942 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
944 if(left_value.check_type<int>())
945 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
946 else if(left_value.check_type<unsigned>())
947 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
948 else if(left_value.check_type<float>())
949 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
951 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
953 if(left_value.check_type<int>())
954 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
955 else if(left_value.check_type<unsigned>())
956 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
960 void ConstantFolder::visit(Assignment &assign)
962 TraversingVisitor::visit(assign);
966 void ConstantFolder::visit(TernaryExpression &ternary)
968 TraversingVisitor::visit(ternary);
972 void ConstantFolder::visit(FunctionCall &call)
974 if(call.constructor && call.type && call.arguments.size()==1)
976 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
979 visit(call.arguments[0]);
980 bool can_fold = r_constant;
985 if(basic->kind==BasicTypeDeclaration::BOOL)
986 convert_to_result<bool>(r_constant_value);
987 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
988 convert_to_result<int>(r_constant_value);
989 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
990 convert_to_result<unsigned>(r_constant_value);
991 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
992 convert_to_result<float>(r_constant_value);
998 TraversingVisitor::visit(call);
1002 void ConstantFolder::visit(VariableDeclaration &var)
1004 if(iteration_init && var.init_expression)
1006 visit(var.init_expression);
1009 /* Record the value of a constant initialization expression of an
1010 iteration, so it can be used to evaluate the loop condition. */
1011 iteration_var = &var;
1012 iter_init_value = r_constant_value;
1016 TraversingVisitor::visit(var);
1019 void ConstantFolder::visit(Iteration &iter)
1021 SetForScope<Block *> set_block(current_block, &iter.body);
1023 /* The iteration variable is not normally inlined into expressions, so we
1024 process it specially here. If the initial value causes the loop condition
1025 to evaluate to false, then the expression can be folded. */
1027 if(iter.init_statement)
1029 SetFlag set_init(iteration_init);
1030 iter.init_statement->visit(*this);
1035 visit(iter.condition);
1036 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1038 RefPtr<Literal> literal = new Literal;
1039 literal->token = "false";
1040 literal->value = r_constant_value;
1041 iter.condition = literal;
1046 iter.body.visit(*this);
1047 if(iter.loop_expression)
1048 visit(iter.loop_expression);
1052 void ConstantConditionEliminator::apply(Stage &stage)
1054 stage.content.visit(*this);
1055 NodeRemover().apply(stage, nodes_to_remove);
1058 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1060 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1061 if(literal->value.check_type<bool>())
1062 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1063 return NOT_CONSTANT;
1066 void ConstantConditionEliminator::visit(Block &block)
1068 SetForScope<Block *> set_block(current_block, &block);
1069 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1076 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1078 r_ternary_result = 0;
1080 if(r_ternary_result)
1081 expr = r_ternary_result;
1082 r_ternary_result = 0;
1085 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1087 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1088 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1090 auto i = current_block->variables.find(var->name);
1091 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1095 TraversingVisitor::visit(unary);
1098 void ConstantConditionEliminator::visit(Assignment &assign)
1100 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1101 if(i==current_block->variables.end())
1102 r_external_side_effects = true;
1103 TraversingVisitor::visit(assign);
1106 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1108 ConstantStatus result = check_constant_condition(*ternary.condition);
1109 if(result!=NOT_CONSTANT)
1110 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1112 r_ternary_result = 0;
1115 void ConstantConditionEliminator::visit(FunctionCall &call)
1117 r_external_side_effects = true;
1118 TraversingVisitor::visit(call);
1121 void ConstantConditionEliminator::visit(Conditional &cond)
1123 ConstantStatus result = check_constant_condition(*cond.condition);
1124 if(result!=NOT_CONSTANT)
1126 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1127 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1128 current_block->body.splice(insert_point, block.body);
1129 nodes_to_remove.insert(&cond);
1133 r_external_side_effects = false;
1134 TraversingVisitor::visit(cond);
1136 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1137 nodes_to_remove.insert(&cond);
1140 void ConstantConditionEliminator::visit(Iteration &iter)
1144 ConstantStatus result = check_constant_condition(*iter.condition);
1145 if(result==CONSTANT_FALSE)
1147 nodes_to_remove.insert(&iter);
1152 r_external_side_effects = false;
1153 TraversingVisitor::visit(iter);
1154 if(iter.body.body.empty() && !r_external_side_effects)
1155 nodes_to_remove.insert(&iter);
1159 bool UnreachableCodeRemover::apply(Stage &stage)
1161 stage.content.visit(*this);
1162 NodeRemover().apply(stage, unreachable_nodes);
1163 return !unreachable_nodes.empty();
1166 void UnreachableCodeRemover::visit(Block &block)
1168 auto i = block.body.begin();
1169 for(; (reachable && i!=block.body.end()); ++i)
1171 for(; i!=block.body.end(); ++i)
1172 unreachable_nodes.insert(i->get());
1175 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1177 TraversingVisitor::visit(func);
1181 void UnreachableCodeRemover::visit(Conditional &cond)
1183 cond.body.visit(*this);
1184 bool reachable_if_true = reachable;
1186 cond.else_body.visit(*this);
1188 reachable |= reachable_if_true;
1191 void UnreachableCodeRemover::visit(Iteration &iter)
1193 TraversingVisitor::visit(iter);
1195 /* Always consider code after a loop reachable, since there's no checking
1196 for whether the loop executes. */
1201 bool UnusedTypeRemover::apply(Stage &stage)
1203 stage.content.visit(*this);
1204 NodeRemover().apply(stage, unused_nodes);
1205 return !unused_nodes.empty();
1208 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1210 unused_nodes.erase(expr->type);
1211 TraversingVisitor::visit(expr);
1214 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1217 unused_nodes.erase(type.base_type);
1218 unused_nodes.insert(&type);
1221 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1224 unused_nodes.erase(type.base_type);
1225 unused_nodes.insert(&type);
1228 void UnusedTypeRemover::visit(StructDeclaration &strct)
1230 unused_nodes.insert(&strct);
1231 TraversingVisitor::visit(strct);
1234 void UnusedTypeRemover::visit(VariableDeclaration &var)
1236 unused_nodes.erase(var.type_declaration);
1237 TraversingVisitor::visit(var);
1240 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1242 unused_nodes.erase(iface.type_declaration);
1245 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1247 unused_nodes.erase(func.return_type_declaration);
1248 TraversingVisitor::visit(func);
1252 bool UnusedVariableRemover::apply(Stage &s)
1255 s.content.visit(*this);
1257 for(const AssignmentInfo &a: assignments)
1258 if(a.used_by.empty())
1259 unused_nodes.insert(a.node);
1261 for(const auto &kvp: variables)
1263 if(!kvp.second.referenced)
1264 unused_nodes.insert(kvp.first);
1265 else if(kvp.second.output)
1267 /* The last visible assignments of output variables are used by the
1268 next stage or the API. */
1269 for(AssignmentInfo *a: kvp.second.assignments)
1270 unused_nodes.erase(a->node);
1274 NodeRemover().apply(s, unused_nodes);
1276 return !unused_nodes.empty();
1279 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1281 VariableInfo &var_info = variables[target.declaration];
1282 var_info.referenced = true;
1283 if(!assignment_target)
1285 bool loop_external = false;
1286 for(AssignmentInfo *a: var_info.assignments)
1288 bool covered = true;
1289 for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1291 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1292 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1293 unsigned index1 = a->target.chain[j]&0x3F;
1294 unsigned index2 = target.chain[j]&0x3F;
1295 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1297 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1298 covered = index1&index2;
1299 else if(type1==Assignment::Target::ARRAY && index1<4)
1300 covered = index2&(1<<index1);
1301 else if(type2==Assignment::Target::ARRAY && index2<4)
1302 covered = index1&(1<<index2);
1303 /* If it's some other combination (shouldn't happen), leave
1307 covered = (type1==type2 && (index1==index2 || index1==0x3F || index2==0x3F));
1312 a->used_by.push_back(&node);
1313 if(a->in_loop<in_loop)
1314 loop_external = true;
1319 loop_ext_refs.push_back(&node);
1323 void UnusedVariableRemover::visit(VariableReference &var)
1325 if(composite_reference)
1326 r_reference.declaration = var.declaration;
1328 referenced(var.declaration, var);
1331 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1333 if(composite_reference)
1334 r_reference.declaration = iface.declaration;
1336 referenced(iface.declaration, iface);
1339 void UnusedVariableRemover::visit_composite(Expression &expr)
1341 if(!composite_reference)
1342 r_reference = Assignment::Target();
1344 SetFlag set_composite(composite_reference);
1348 void UnusedVariableRemover::visit(MemberAccess &memacc)
1350 visit_composite(*memacc.left);
1352 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1354 if(!composite_reference && r_reference.declaration)
1355 referenced(r_reference, memacc);
1358 void UnusedVariableRemover::visit(Swizzle &swizzle)
1360 visit_composite(*swizzle.left);
1363 for(unsigned i=0; i<swizzle.count; ++i)
1364 mask |= 1<<swizzle.components[i];
1365 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1367 if(!composite_reference && r_reference.declaration)
1368 referenced(r_reference, swizzle);
1371 void UnusedVariableRemover::visit(UnaryExpression &unary)
1373 TraversingVisitor::visit(unary);
1374 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1375 r_side_effects = true;
1378 void UnusedVariableRemover::visit(BinaryExpression &binary)
1380 if(binary.oper->token[0]=='[')
1382 visit_composite(*binary.left);
1385 SetFlag clear_assignment(assignment_target, false);
1386 SetFlag clear_composite(composite_reference, false);
1387 binary.right->visit(*this);
1390 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1392 if(!composite_reference && r_reference.declaration)
1393 referenced(r_reference, binary);
1397 SetFlag clear_composite(composite_reference, false);
1398 TraversingVisitor::visit(binary);
1402 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1404 SetFlag clear_composite(composite_reference, false);
1405 TraversingVisitor::visit(ternary);
1408 void UnusedVariableRemover::visit(Assignment &assign)
1411 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1412 assign.left->visit(*this);
1414 assign.right->visit(*this);
1415 r_assignment = &assign;
1416 r_side_effects = true;
1419 void UnusedVariableRemover::visit(FunctionCall &call)
1421 SetFlag clear_composite(composite_reference, false);
1422 TraversingVisitor::visit(call);
1423 /* Treat function calls as having side effects so expression statements
1424 consisting of nothing but a function call won't be optimized away. */
1425 r_side_effects = true;
1427 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1429 for(const auto &kvp: variables)
1430 if(kvp.second.output)
1431 referenced(kvp.first, call);
1435 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1437 assignments.push_back(AssignmentInfo());
1438 AssignmentInfo &assign_info = assignments.back();
1439 assign_info.node = &node;
1440 assign_info.target = target;
1441 assign_info.in_loop = in_loop;
1443 /* An assignment to the target hides any assignments to the same target or
1445 VariableInfo &var_info = variables[target.declaration];
1446 for(unsigned i=0; i<var_info.assignments.size(); )
1448 const Assignment::Target &t = var_info.assignments[i]->target;
1450 bool subfield = (t.chain_len>=target.chain_len);
1451 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1452 subfield = (t.chain[j]==target.chain[j]);
1455 var_info.assignments.erase(var_info.assignments.begin()+i);
1460 var_info.assignments.push_back(&assign_info);
1463 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1466 r_side_effects = false;
1467 TraversingVisitor::visit(expr);
1468 if(r_assignment && r_assignment->target.declaration)
1469 record_assignment(r_assignment->target, expr);
1471 unused_nodes.insert(&expr);
1474 void UnusedVariableRemover::visit(StructDeclaration &strct)
1476 SetFlag set_struct(in_struct);
1477 TraversingVisitor::visit(strct);
1480 void UnusedVariableRemover::visit(VariableDeclaration &var)
1482 TraversingVisitor::visit(var);
1487 VariableInfo &var_info = variables[&var];
1489 /* Mark variables as output if they're used by the next stage or the
1491 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1493 // Linked outputs are automatically referenced.
1494 if(var_info.output && var.linked_declaration)
1495 var_info.referenced = true;
1497 if(var.init_expression)
1499 var_info.initialized = true;
1500 record_assignment(&var, *var.init_expression);
1504 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1506 VariableInfo &var_info = variables[&iface];
1507 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1510 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1512 for(const auto &kvp: other_vars)
1514 auto j = variables.find(kvp.first);
1515 if(j!=variables.end())
1517 /* The merged blocks started as copies of each other so any common
1518 assignments must be in the beginning. */
1520 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1521 if(kvp.second.assignments[k]!=j->second.assignments[k])
1524 // Remaining assignments are unique to each block; merge them.
1525 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1526 j->second.referenced |= kvp.second.referenced;
1529 variables.insert(kvp);
1533 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1535 if(func.body.body.empty())
1538 BlockVariableMap saved_vars = variables;
1539 // Assignments from other functions should not be visible.
1540 for(auto &kvp: variables)
1541 kvp.second.assignments.resize(kvp.second.initialized);
1542 TraversingVisitor::visit(func);
1543 swap(variables, saved_vars);
1544 merge_variables(saved_vars);
1546 /* Always treat function parameters as referenced. Removing unused
1547 parameters is not currently supported. */
1548 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1550 auto j = variables.find(p.get());
1551 if(j!=variables.end())
1552 j->second.referenced = true;
1556 void UnusedVariableRemover::visit(Conditional &cond)
1558 cond.condition->visit(*this);
1559 BlockVariableMap saved_vars = variables;
1560 cond.body.visit(*this);
1561 swap(saved_vars, variables);
1562 cond.else_body.visit(*this);
1564 /* Visible assignments after the conditional is the union of those visible
1565 at the end of the if and else blocks. If there was no else block, then it's
1566 the union of the if block and the state before it. */
1567 merge_variables(saved_vars);
1570 void UnusedVariableRemover::visit(Iteration &iter)
1572 BlockVariableMap saved_vars = variables;
1573 vector<Node *> saved_refs;
1574 swap(loop_ext_refs, saved_refs);
1576 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1577 TraversingVisitor::visit(iter);
1579 swap(loop_ext_refs, saved_refs);
1581 /* Visit the external references of the loop again to record assignments
1582 done in the loop as used. */
1583 for(Node *n: saved_refs)
1586 /* Merge assignments from the iteration, without clearing previous state.
1587 Further analysis is needed to determine which parts of the iteration body
1588 are always executed, if any. */
1589 merge_variables(saved_vars);
1593 bool UnusedFunctionRemover::apply(Stage &stage)
1595 stage.content.visit(*this);
1596 NodeRemover().apply(stage, unused_nodes);
1597 return !unused_nodes.empty();
1600 void UnusedFunctionRemover::visit(FunctionCall &call)
1602 TraversingVisitor::visit(call);
1604 unused_nodes.erase(call.declaration);
1605 if(call.declaration && call.declaration->definition!=call.declaration)
1606 used_definitions.insert(call.declaration->definition);
1609 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1611 TraversingVisitor::visit(func);
1613 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1614 unused_nodes.insert(&func);