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);
722 T ConstantFolder::evaluate_logical(char oper, T left, T right)
726 case '&': return left&right;
727 case '|': return left|right;
728 case '^': return left^right;
734 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
736 switch(oper[0]|oper[1])
738 case '<': return left<right;
739 case '<'|'=': return left<=right;
740 case '>': return left>right;
741 case '>'|'=': return left>=right;
742 default: return false;
747 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
751 case '+': return left+right;
752 case '-': return left-right;
753 case '*': return left*right;
754 case '/': return left/right;
760 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
764 case '%': return left%right;
765 case '<': return left<<right;
766 case '>': return left>>right;
772 void ConstantFolder::convert_to_result(const Variant &value)
774 if(value.check_type<bool>())
775 set_result(static_cast<T>(value.value<bool>()));
776 else if(value.check_type<int>())
777 set_result(static_cast<T>(value.value<int>()));
778 else if(value.check_type<unsigned>())
779 set_result(static_cast<T>(value.value<unsigned>()));
780 else if(value.check_type<float>())
781 set_result(static_cast<T>(value.value<float>()));
784 void ConstantFolder::set_result(const Variant &value, bool literal)
786 r_constant_value = value;
791 void ConstantFolder::visit(RefPtr<Expression> &expr)
793 r_constant_value = Variant();
796 r_uses_iter_var = false;
798 /* Don't replace literals since they'd only be replaced with an identical
799 literal. Also skip anything that uses an iteration variable, but pass on
800 the result so the Iteration visiting function can handle it. */
801 if(!r_constant || r_literal || r_uses_iter_var)
804 RefPtr<Literal> literal = new Literal;
805 if(r_constant_value.check_type<bool>())
806 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
807 else if(r_constant_value.check_type<int>())
808 literal->token = lexical_cast<string>(r_constant_value.value<int>());
809 else if(r_constant_value.check_type<unsigned>())
810 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
811 else if(r_constant_value.check_type<float>())
813 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
814 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
815 literal->token += ".0";
822 literal->value = r_constant_value;
827 void ConstantFolder::visit(Literal &literal)
829 set_result(literal.value, true);
832 void ConstantFolder::visit(VariableReference &var)
834 /* If an iteration variable is initialized with a constant value, return
835 that value here for the purpose of evaluating the loop condition for the
837 if(var.declaration==iteration_var)
839 set_result(iter_init_value);
840 r_uses_iter_var = true;
844 void ConstantFolder::visit(MemberAccess &memacc)
846 TraversingVisitor::visit(memacc);
850 void ConstantFolder::visit(Swizzle &swizzle)
852 TraversingVisitor::visit(swizzle);
856 void ConstantFolder::visit(UnaryExpression &unary)
858 TraversingVisitor::visit(unary);
859 bool can_fold = r_constant;
864 char oper = unary.oper->token[0];
865 char oper2 = unary.oper->token[1];
868 if(r_constant_value.check_type<bool>())
869 set_result(!r_constant_value.value<bool>());
873 if(r_constant_value.check_type<int>())
874 set_result(~r_constant_value.value<int>());
875 else if(r_constant_value.check_type<unsigned>())
876 set_result(~r_constant_value.value<unsigned>());
878 else if(oper=='-' && !oper2)
880 if(r_constant_value.check_type<int>())
881 set_result(-r_constant_value.value<int>());
882 else if(r_constant_value.check_type<unsigned>())
883 set_result(-r_constant_value.value<unsigned>());
884 else if(r_constant_value.check_type<float>())
885 set_result(-r_constant_value.value<float>());
889 void ConstantFolder::visit(BinaryExpression &binary)
892 bool left_constant = r_constant;
893 bool left_iter_var = r_uses_iter_var;
894 Variant left_value = r_constant_value;
897 r_uses_iter_var = true;
899 bool can_fold = (left_constant && r_constant);
904 // Currently only expressions with both sides of equal types are handled.
905 if(!left_value.check_same_type(r_constant_value))
908 char oper = binary.oper->token[0];
909 char oper2 = binary.oper->token[1];
910 if(oper=='&' || oper=='|' || oper=='^')
912 if(oper2==oper && left_value.check_type<bool>())
913 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
914 else if(!oper2 && left_value.check_type<int>())
915 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
916 else if(!oper2 && left_value.check_type<unsigned>())
917 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
919 else if((oper=='<' || oper=='>') && oper2!=oper)
921 if(left_value.check_type<int>())
922 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
923 else if(left_value.check_type<unsigned>())
924 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
925 else if(left_value.check_type<float>())
926 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
928 else if((oper=='=' || oper=='!') && oper2=='=')
930 if(left_value.check_type<int>())
931 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
932 else if(left_value.check_type<unsigned>())
933 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
934 else if(left_value.check_type<float>())
935 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
937 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
939 if(left_value.check_type<int>())
940 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
941 else if(left_value.check_type<unsigned>())
942 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
943 else if(left_value.check_type<float>())
944 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
946 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
948 if(left_value.check_type<int>())
949 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
950 else if(left_value.check_type<unsigned>())
951 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
955 void ConstantFolder::visit(Assignment &assign)
957 TraversingVisitor::visit(assign);
961 void ConstantFolder::visit(TernaryExpression &ternary)
963 TraversingVisitor::visit(ternary);
967 void ConstantFolder::visit(FunctionCall &call)
969 if(call.constructor && call.type && call.arguments.size()==1)
971 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
974 visit(call.arguments[0]);
975 bool can_fold = r_constant;
980 if(basic->kind==BasicTypeDeclaration::BOOL)
981 convert_to_result<bool>(r_constant_value);
982 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
983 convert_to_result<int>(r_constant_value);
984 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
985 convert_to_result<unsigned>(r_constant_value);
986 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
987 convert_to_result<float>(r_constant_value);
993 TraversingVisitor::visit(call);
997 void ConstantFolder::visit(VariableDeclaration &var)
999 if(iteration_init && var.init_expression)
1001 visit(var.init_expression);
1004 /* Record the value of a constant initialization expression of an
1005 iteration, so it can be used to evaluate the loop condition. */
1006 iteration_var = &var;
1007 iter_init_value = r_constant_value;
1011 TraversingVisitor::visit(var);
1014 void ConstantFolder::visit(Iteration &iter)
1016 SetForScope<Block *> set_block(current_block, &iter.body);
1018 /* The iteration variable is not normally inlined into expressions, so we
1019 process it specially here. If the initial value causes the loop condition
1020 to evaluate to false, then the expression can be folded. */
1022 if(iter.init_statement)
1024 SetFlag set_init(iteration_init);
1025 iter.init_statement->visit(*this);
1030 visit(iter.condition);
1031 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1033 RefPtr<Literal> literal = new Literal;
1034 literal->token = "false";
1035 literal->value = r_constant_value;
1036 iter.condition = literal;
1041 iter.body.visit(*this);
1042 if(iter.loop_expression)
1043 visit(iter.loop_expression);
1047 void ConstantConditionEliminator::apply(Stage &stage)
1049 stage.content.visit(*this);
1050 NodeRemover().apply(stage, nodes_to_remove);
1053 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1055 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1056 if(literal->value.check_type<bool>())
1057 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1058 return NOT_CONSTANT;
1061 void ConstantConditionEliminator::visit(Block &block)
1063 SetForScope<Block *> set_block(current_block, &block);
1064 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1071 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1073 r_ternary_result = 0;
1075 if(r_ternary_result)
1076 expr = r_ternary_result;
1077 r_ternary_result = 0;
1080 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1082 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1083 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1085 auto i = current_block->variables.find(var->name);
1086 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1090 TraversingVisitor::visit(unary);
1093 void ConstantConditionEliminator::visit(Assignment &assign)
1095 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1096 if(i==current_block->variables.end())
1097 r_external_side_effects = true;
1098 TraversingVisitor::visit(assign);
1101 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1103 ConstantStatus result = check_constant_condition(*ternary.condition);
1104 if(result!=NOT_CONSTANT)
1105 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1107 r_ternary_result = 0;
1110 void ConstantConditionEliminator::visit(FunctionCall &call)
1112 r_external_side_effects = true;
1113 TraversingVisitor::visit(call);
1116 void ConstantConditionEliminator::visit(Conditional &cond)
1118 ConstantStatus result = check_constant_condition(*cond.condition);
1119 if(result!=NOT_CONSTANT)
1121 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1122 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1123 current_block->body.splice(insert_point, block.body);
1124 nodes_to_remove.insert(&cond);
1128 r_external_side_effects = false;
1129 TraversingVisitor::visit(cond);
1131 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1132 nodes_to_remove.insert(&cond);
1135 void ConstantConditionEliminator::visit(Iteration &iter)
1139 ConstantStatus result = check_constant_condition(*iter.condition);
1140 if(result==CONSTANT_FALSE)
1142 nodes_to_remove.insert(&iter);
1147 r_external_side_effects = false;
1148 TraversingVisitor::visit(iter);
1149 if(iter.body.body.empty() && !r_external_side_effects)
1150 nodes_to_remove.insert(&iter);
1154 bool UnreachableCodeRemover::apply(Stage &stage)
1156 stage.content.visit(*this);
1157 NodeRemover().apply(stage, unreachable_nodes);
1158 return !unreachable_nodes.empty();
1161 void UnreachableCodeRemover::visit(Block &block)
1163 auto i = block.body.begin();
1164 for(; (reachable && i!=block.body.end()); ++i)
1166 for(; i!=block.body.end(); ++i)
1167 unreachable_nodes.insert(i->get());
1170 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1172 TraversingVisitor::visit(func);
1176 void UnreachableCodeRemover::visit(Conditional &cond)
1178 cond.body.visit(*this);
1179 bool reachable_if_true = reachable;
1181 cond.else_body.visit(*this);
1183 reachable |= reachable_if_true;
1186 void UnreachableCodeRemover::visit(Iteration &iter)
1188 TraversingVisitor::visit(iter);
1190 /* Always consider code after a loop reachable, since there's no checking
1191 for whether the loop executes. */
1196 bool UnusedTypeRemover::apply(Stage &stage)
1198 stage.content.visit(*this);
1199 NodeRemover().apply(stage, unused_nodes);
1200 return !unused_nodes.empty();
1203 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1205 unused_nodes.erase(expr->type);
1206 TraversingVisitor::visit(expr);
1209 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1212 unused_nodes.erase(type.base_type);
1213 unused_nodes.insert(&type);
1216 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1219 unused_nodes.erase(type.base_type);
1220 unused_nodes.insert(&type);
1223 void UnusedTypeRemover::visit(StructDeclaration &strct)
1225 unused_nodes.insert(&strct);
1226 TraversingVisitor::visit(strct);
1229 void UnusedTypeRemover::visit(VariableDeclaration &var)
1231 unused_nodes.erase(var.type_declaration);
1232 TraversingVisitor::visit(var);
1235 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1237 unused_nodes.erase(iface.type_declaration);
1240 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1242 unused_nodes.erase(func.return_type_declaration);
1243 TraversingVisitor::visit(func);
1247 bool UnusedVariableRemover::apply(Stage &s)
1250 s.content.visit(*this);
1252 for(const AssignmentInfo &a: assignments)
1253 if(a.used_by.empty())
1254 unused_nodes.insert(a.node);
1256 for(const auto &kvp: variables)
1258 if(kvp.second.output)
1260 /* The last visible assignments of output variables are used by the
1261 next stage or the API. */
1262 for(AssignmentInfo *a: kvp.second.assignments)
1263 unused_nodes.erase(a->node);
1266 if(!kvp.second.output && !kvp.second.referenced)
1268 // Don't remove variables from inside interface blocks.
1269 if(!kvp.second.interface_block)
1270 unused_nodes.insert(kvp.first);
1272 else if(kvp.second.interface_block)
1273 // Interface blocks are kept if even one member is used.
1274 unused_nodes.erase(kvp.second.interface_block);
1277 NodeRemover().apply(s, unused_nodes);
1279 return !unused_nodes.empty();
1282 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1284 VariableInfo &var_info = variables[target.declaration];
1285 var_info.referenced = true;
1286 if(!assignment_target)
1288 bool loop_external = false;
1289 for(AssignmentInfo *a: var_info.assignments)
1291 bool covered = true;
1292 for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1294 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1295 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1296 unsigned index1 = a->target.chain[j]&0x3F;
1297 unsigned index2 = target.chain[j]&0x3F;
1298 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1300 if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1301 covered = index1&index2;
1302 else if(type1==Assignment::Target::ARRAY && index1<4)
1303 covered = index2&(1<<index1);
1304 else if(type2==Assignment::Target::ARRAY && index2<4)
1305 covered = index1&(1<<index2);
1306 /* If it's some other combination (shouldn't happen), leave
1310 covered = (type1==type2 && (index1==index2 || index1==0x3F || index2==0x3F));
1315 a->used_by.push_back(&node);
1316 if(a->in_loop<in_loop)
1317 loop_external = true;
1322 loop_ext_refs.push_back(&node);
1326 void UnusedVariableRemover::visit(VariableReference &var)
1328 if(composite_reference)
1329 r_reference.declaration = var.declaration;
1331 referenced(var.declaration, var);
1334 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1336 if(composite_reference)
1337 r_reference.declaration = iface.declaration;
1339 referenced(iface.declaration, iface);
1342 void UnusedVariableRemover::visit_composite(Expression &expr)
1344 if(!composite_reference)
1345 r_reference = Assignment::Target();
1347 SetFlag set_composite(composite_reference);
1351 void UnusedVariableRemover::visit(MemberAccess &memacc)
1353 visit_composite(*memacc.left);
1355 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1357 if(!composite_reference && r_reference.declaration)
1358 referenced(r_reference, memacc);
1361 void UnusedVariableRemover::visit(Swizzle &swizzle)
1363 visit_composite(*swizzle.left);
1366 for(unsigned i=0; i<swizzle.count; ++i)
1367 mask |= 1<<swizzle.components[i];
1368 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1370 if(!composite_reference && r_reference.declaration)
1371 referenced(r_reference, swizzle);
1374 void UnusedVariableRemover::visit(UnaryExpression &unary)
1376 TraversingVisitor::visit(unary);
1377 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1378 r_side_effects = true;
1381 void UnusedVariableRemover::visit(BinaryExpression &binary)
1383 if(binary.oper->token[0]=='[')
1385 visit_composite(*binary.left);
1388 SetFlag clear_assignment(assignment_target, false);
1389 SetFlag clear_composite(composite_reference, false);
1390 binary.right->visit(*this);
1393 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1395 if(!composite_reference && r_reference.declaration)
1396 referenced(r_reference, binary);
1400 SetFlag clear_composite(composite_reference, false);
1401 TraversingVisitor::visit(binary);
1405 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1407 SetFlag clear_composite(composite_reference, false);
1408 TraversingVisitor::visit(ternary);
1411 void UnusedVariableRemover::visit(Assignment &assign)
1414 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1415 assign.left->visit(*this);
1417 assign.right->visit(*this);
1418 r_assignment = &assign;
1419 r_side_effects = true;
1422 void UnusedVariableRemover::visit(FunctionCall &call)
1424 SetFlag clear_composite(composite_reference, false);
1425 TraversingVisitor::visit(call);
1426 /* Treat function calls as having side effects so expression statements
1427 consisting of nothing but a function call won't be optimized away. */
1428 r_side_effects = true;
1430 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1432 for(const auto &kvp: variables)
1433 if(kvp.second.output)
1434 referenced(kvp.first, call);
1438 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1440 assignments.push_back(AssignmentInfo());
1441 AssignmentInfo &assign_info = assignments.back();
1442 assign_info.node = &node;
1443 assign_info.target = target;
1444 assign_info.in_loop = in_loop;
1446 /* An assignment to the target hides any assignments to the same target or
1448 VariableInfo &var_info = variables[target.declaration];
1449 for(unsigned i=0; i<var_info.assignments.size(); )
1451 const Assignment::Target &t = var_info.assignments[i]->target;
1453 bool subfield = (t.chain_len>=target.chain_len);
1454 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1455 subfield = (t.chain[j]==target.chain[j]);
1458 var_info.assignments.erase(var_info.assignments.begin()+i);
1463 var_info.assignments.push_back(&assign_info);
1466 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1469 r_side_effects = false;
1470 TraversingVisitor::visit(expr);
1471 if(r_assignment && r_assignment->target.declaration)
1472 record_assignment(r_assignment->target, expr);
1474 unused_nodes.insert(&expr);
1477 void UnusedVariableRemover::visit(StructDeclaration &strct)
1479 SetFlag set_struct(in_struct);
1480 TraversingVisitor::visit(strct);
1483 void UnusedVariableRemover::visit(VariableDeclaration &var)
1485 TraversingVisitor::visit(var);
1490 VariableInfo &var_info = variables[&var];
1491 var_info.interface_block = interface_block;
1493 /* Mark variables as output if they're used by the next stage or the
1496 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1498 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1500 if(var.init_expression)
1502 var_info.initialized = true;
1503 record_assignment(&var, *var.init_expression);
1507 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1509 VariableInfo &var_info = variables[&iface];
1510 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1513 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1515 for(const auto &kvp: other_vars)
1517 auto j = variables.find(kvp.first);
1518 if(j!=variables.end())
1520 /* The merged blocks started as copies of each other so any common
1521 assignments must be in the beginning. */
1523 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1524 if(kvp.second.assignments[k]!=j->second.assignments[k])
1527 // Remaining assignments are unique to each block; merge them.
1528 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1529 j->second.referenced |= kvp.second.referenced;
1532 variables.insert(kvp);
1536 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1538 if(func.body.body.empty())
1541 BlockVariableMap saved_vars = variables;
1542 // Assignments from other functions should not be visible.
1543 for(auto &kvp: variables)
1544 kvp.second.assignments.resize(kvp.second.initialized);
1545 TraversingVisitor::visit(func);
1546 swap(variables, saved_vars);
1547 merge_variables(saved_vars);
1549 /* Always treat function parameters as referenced. Removing unused
1550 parameters is not currently supported. */
1551 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1553 auto j = variables.find(p.get());
1554 if(j!=variables.end())
1555 j->second.referenced = true;
1559 void UnusedVariableRemover::visit(Conditional &cond)
1561 cond.condition->visit(*this);
1562 BlockVariableMap saved_vars = variables;
1563 cond.body.visit(*this);
1564 swap(saved_vars, variables);
1565 cond.else_body.visit(*this);
1567 /* Visible assignments after the conditional is the union of those visible
1568 at the end of the if and else blocks. If there was no else block, then it's
1569 the union of the if block and the state before it. */
1570 merge_variables(saved_vars);
1573 void UnusedVariableRemover::visit(Iteration &iter)
1575 BlockVariableMap saved_vars = variables;
1576 vector<Node *> saved_refs;
1577 swap(loop_ext_refs, saved_refs);
1579 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1580 TraversingVisitor::visit(iter);
1582 swap(loop_ext_refs, saved_refs);
1584 /* Visit the external references of the loop again to record assignments
1585 done in the loop as used. */
1586 for(Node *n: saved_refs)
1589 /* Merge assignments from the iteration, without clearing previous state.
1590 Further analysis is needed to determine which parts of the iteration body
1591 are always executed, if any. */
1592 merge_variables(saved_vars);
1596 bool UnusedFunctionRemover::apply(Stage &stage)
1598 stage.content.visit(*this);
1599 NodeRemover().apply(stage, unused_nodes);
1600 return !unused_nodes.empty();
1603 void UnusedFunctionRemover::visit(FunctionCall &call)
1605 TraversingVisitor::visit(call);
1607 unused_nodes.erase(call.declaration);
1608 if(call.declaration && call.declaration->definition!=call.declaration)
1609 used_definitions.insert(call.declaration->definition);
1612 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1614 TraversingVisitor::visit(func);
1616 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1617 unused_nodes.insert(&func);