1 #include <msp/core/algorithm.h>
2 #include <msp/core/raii.h>
3 #include <msp/strings/format.h>
4 #include <msp/strings/utils.h>
14 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
17 stage.content.visit(*this);
20 void ConstantSpecializer::visit(VariableDeclaration &var)
22 bool specializable = false;
25 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
26 auto i = find_member(qualifiers, string("constant_id"), &Layout::Qualifier::name);
27 if(i!=qualifiers.end())
31 if(qualifiers.empty())
38 auto i = values->find(var.name);
41 RefPtr<Literal> literal = new Literal;
44 literal->token = (i->second ? "true" : "false");
45 literal->value = static_cast<bool>(i->second);
47 else if(var.type=="int")
49 literal->token = lexical_cast<string>(i->second);
50 literal->value = i->second;
52 var.init_expression = literal;
58 void InlineableFunctionLocator::visit(FunctionCall &call)
60 FunctionDeclaration *def = call.declaration;
62 def = def->definition;
66 unsigned &count = refcounts[def];
68 /* Don't inline functions which are called more than once or are called
70 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
71 inlineable.erase(def);
74 TraversingVisitor::visit(call);
77 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
79 bool has_out_params = any_of(func.parameters.begin(), func.parameters.end(),
80 [](const RefPtr<VariableDeclaration> &p){ return p->interface=="out"; });
82 unsigned &count = refcounts[func.definition];
83 if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
84 inlineable.insert(func.definition);
86 SetForScope<FunctionDeclaration *> set(current_function, &func);
88 TraversingVisitor::visit(func);
91 void InlineableFunctionLocator::visit(Conditional &cond)
93 TraversingVisitor::visit(cond);
94 inlineable.erase(current_function);
97 void InlineableFunctionLocator::visit(Iteration &iter)
99 TraversingVisitor::visit(iter);
100 inlineable.erase(current_function);
103 void InlineableFunctionLocator::visit(Return &ret)
105 TraversingVisitor::visit(ret);
107 inlineable.erase(current_function);
112 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
114 source_func = call.declaration->definition;
116 /* Populate referenced_names from the target function so we can rename
117 variables from the inlined function that would conflict. Only consider
118 names declared in blocks linearly related to the target block. */
120 tgt_blk.visit(*this);
121 for(const Block *b=&tgt_blk; b; b=b->parent)
122 for(const auto &kvp: b->variables)
123 referenced_names.insert(kvp.first);
124 for(const auto &kvp: stage.interface_blocks)
125 if(kvp.second->name.find(' ')!=string::npos)
126 for(const auto &kvp2: kvp.second->block_declaration->members.variables)
127 referenced_names.insert(kvp2.first);
129 /* Inline and rename passes must be interleaved so used variable names are
130 known when inlining the return statement. */
132 staging_block.parent = &tgt_blk;
133 staging_block.variables.clear();
135 vector<RefPtr<VariableDeclaration> > params;
136 params.reserve(source_func->parameters.size());
137 for(const RefPtr<VariableDeclaration> &p: source_func->parameters)
139 RefPtr<VariableDeclaration> var = p->clone();
140 var->interface.clear();
142 SetForScope<Pass> set_pass(pass, RENAME);
145 staging_block.body.push_back_nocopy(var);
146 params.push_back(var);
149 for(const RefPtr<Statement> &s: source_func->body.body)
151 r_inlined_statement = 0;
153 if(!r_inlined_statement)
154 r_inlined_statement = s->clone();
156 SetForScope<Pass> set_pass(pass, RENAME);
157 r_inlined_statement->visit(*this);
159 staging_block.body.push_back_nocopy(r_inlined_statement);
162 /* Now collect names from the staging block. Local variables that would
163 have conflicted with the target function were renamed earlier. */
165 referenced_names.clear();
166 staging_block.variables.clear();
167 staging_block.visit(*this);
169 /* Rename variables in the target function so they don't interfere with
170 global identifiers used by the source function. */
172 staging_block.parent = source_func->body.parent;
173 target_func.visit(*this);
175 // Put the argument expressions in place after all renaming has been done.
176 for(unsigned i=0; i<source_func->parameters.size(); ++i)
177 params[i]->init_expression = call.arguments[i]->clone();
179 tgt_blk.body.splice(ins_pt, staging_block.body);
181 NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
183 return r_result_name;
186 void InlineContentInjector::visit(VariableReference &var)
190 auto i = staging_block.variables.find(var.name);
191 if(i!=staging_block.variables.end())
192 var.name = i->second->name;
194 else if(pass==REFERENCED)
195 referenced_names.insert(var.name);
198 void InlineContentInjector::visit(FunctionCall &call)
201 referenced_names.insert(call.name);
202 TraversingVisitor::visit(call);
205 void InlineContentInjector::visit(VariableDeclaration &var)
207 TraversingVisitor::visit(var);
211 /* Check against conflicts with the other context as well as variables
212 already renamed here. */
213 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
214 staging_block.variables[var.name] = &var;
217 string mapped_name = get_unused_variable_name(staging_block, var.name);
218 if(mapped_name!=var.name)
220 staging_block.variables[mapped_name] = &var;
221 var.name = mapped_name;
225 else if(pass==REFERENCED)
226 referenced_names.insert(var.type);
229 void InlineContentInjector::visit(Return &ret)
231 TraversingVisitor::visit(ret);
233 if(pass==INLINE && ret.expression)
235 // Create a new variable to hold the return value of the inlined function.
236 r_result_name = get_unused_variable_name(staging_block, "_return");
237 RefPtr<VariableDeclaration> var = new VariableDeclaration;
238 var->source = ret.source;
239 var->line = ret.line;
240 var->type = source_func->return_type;
241 var->name = r_result_name;
242 var->init_expression = ret.expression->clone();
243 r_inlined_statement = var;
248 bool FunctionInliner::apply(Stage &s)
251 inlineable = InlineableFunctionLocator().apply(s);
252 r_any_inlined = false;
253 s.content.visit(*this);
254 return r_any_inlined;
257 void FunctionInliner::visit(RefPtr<Expression> &ptr)
263 ptr = r_inline_result;
264 r_any_inlined = true;
269 void FunctionInliner::visit(Block &block)
271 SetForScope<Block *> set_block(current_block, &block);
272 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
273 for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
280 void FunctionInliner::visit(FunctionCall &call)
282 for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
288 FunctionDeclaration *def = call.declaration;
290 def = def->definition;
292 if(def && inlineable.count(def))
294 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
296 // This will later get removed by UnusedVariableRemover.
297 if(result_name.empty())
298 result_name = "_msp_unused_from_inline";
300 RefPtr<VariableReference> ref = new VariableReference;
301 ref->name = result_name;
302 r_inline_result = ref;
304 /* Inlined variables need to be resolved before this function can be
306 inlineable.erase(current_function);
307 r_inlined_here = true;
311 void FunctionInliner::visit(FunctionDeclaration &func)
313 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
314 TraversingVisitor::visit(func);
315 r_inlined_here = false;
318 void FunctionInliner::visit(Iteration &iter)
320 /* Visit the initialization statement before entering the loop body so the
321 inlined statements get inserted outside. */
322 if(iter.init_statement)
323 iter.init_statement->visit(*this);
325 SetForScope<Block *> set_block(current_block, &iter.body);
326 /* Skip the condition and loop expression parts because they're not properly
327 inside the body block. Inlining anything into them will require a more
328 comprehensive transformation. */
329 iter.body.visit(*this);
333 bool ExpressionInliner::apply(Stage &s)
335 s.content.visit(*this);
337 bool any_inlined = false;
338 for(ExpressionInfo &e: expressions)
339 if(e.expression && (e.trivial || e.uses.size()==1))
341 for(ExpressionUse &u: e.uses)
344 *u.reference = e.expression->clone();
352 void ExpressionInliner::visit(RefPtr<Expression> &expr)
356 if(r_ref_info && r_ref_info->expression)
359 use.reference = &expr;
360 use.ref_scope = current_block;
361 use.blocked = access_write || r_ref_info->blocked;
363 if(iteration_body && !r_ref_info->trivial)
365 /* Block inlining of non-trivial expressions assigned outside an
366 iteration statement. The iteration may run multiple times, which
367 would cause the expression to also be evaluated multiple times. */
368 for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
369 use.blocked = (i==r_ref_info->assign_scope);
372 /* Block inlining assignments from from inner scopes. The assignment may
373 depend on local variables of that scope or may not always be executed. */
374 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
375 use.blocked = (i==current_block);
377 r_ref_info->uses.push_back(use);
383 void ExpressionInliner::visit(VariableReference &var)
385 if(var.declaration && access_read)
387 auto i = assignments.find(var.declaration);
388 if(i!=assignments.end())
389 r_ref_info = i->second;
393 void ExpressionInliner::visit(MemberAccess &memacc)
399 void ExpressionInliner::visit(Swizzle &swizzle)
405 void ExpressionInliner::visit(UnaryExpression &unary)
407 SetFlag set_write(access_write, (unary.oper->token[1]=='+' || unary.oper->token[1]=='-'));
408 visit(unary.expression);
412 void ExpressionInliner::visit(BinaryExpression &binary)
416 SetFlag clear_write(access_write, false);
422 void ExpressionInliner::visit(Assignment &assign)
425 SetFlag set_read(access_read, assign.oper->token[0]!='=');
426 SetFlag set_write(access_write);
433 auto i = assignments.find(assign.target.declaration);
434 if(i!=assignments.end())
436 if(iteration_body && i->second && i->second->expression)
438 /* Block inlining into previous references within the iteration
439 statement. On iterations after the first they would refer to the
440 assignment within the iteration. */
441 for(ExpressionUse &u: i->second->uses)
442 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
443 u.blocked = (k==iteration_body);
446 for(; (i!=assignments.end() && i->first.declaration==assign.target.declaration); ++i)
447 if(targets_overlap(i->first, assign.target))
448 i->second->blocked = true;
450 expressions.emplace_back();
451 ExpressionInfo &info = expressions.back();
452 info.target = assign.target;
453 // Self-referencing assignments can't be inlined without additional work.
454 if(!assign.self_referencing)
455 info.expression = assign.right;
456 info.assign_scope = current_block;
457 info.trivial = r_trivial;
459 assignments[assign.target] = &info;
465 void ExpressionInliner::visit(TernaryExpression &ternary)
467 visit(ternary.condition);
468 visit(ternary.true_expr);
469 visit(ternary.false_expr);
473 void ExpressionInliner::visit(FunctionCall &call)
475 TraversingVisitor::visit(call);
479 void ExpressionInliner::visit(VariableDeclaration &var)
483 TraversingVisitor::visit(var);
485 bool constant = var.constant;
486 if(constant && var.layout)
488 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
489 [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
492 /* Only inline global variables if they're constant and have trivial
493 initializers. Non-constant variables could change in ways which are hard to
494 analyze and non-trivial expressions could be expensive to inline. */
495 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
497 expressions.emplace_back();
498 ExpressionInfo &info = expressions.back();
500 /* Assume variables declared in an iteration initialization statement
501 will have their values change throughout the iteration. */
503 info.expression = var.init_expression;
504 info.assign_scope = current_block;
505 info.trivial = r_trivial;
507 assignments[&var] = &info;
511 void ExpressionInliner::visit(Iteration &iter)
513 SetForScope<Block *> set_block(current_block, &iter.body);
514 if(iter.init_statement)
516 SetFlag set_init(iteration_init);
517 iter.init_statement->visit(*this);
520 SetForScope<Block *> set_body(iteration_body, &iter.body);
522 visit(iter.condition);
523 iter.body.visit(*this);
524 if(iter.loop_expression)
525 visit(iter.loop_expression);
529 bool AggregateDismantler::apply(Stage &stage)
531 stage.content.visit(*this);
533 bool any_dismantled = false;
534 for(const auto &kvp: aggregates)
536 if(kvp.second.referenced || !kvp.second.members_referenced)
539 for(const AggregateMember &m: kvp.second.members)
543 name = format("%s_%s", kvp.second.declaration->name, m.declaration->name);
545 name = format("%s_%d", kvp.second.declaration->name, m.index);
547 VariableDeclaration *var = new VariableDeclaration;
548 var->source = kvp.first->source;
549 var->line = kvp.first->line;
550 var->name = get_unused_variable_name(*kvp.second.decl_scope, name);
551 /* XXX This is kind of brittle and depends on the array declaration's
552 textual type not having brackets in it. */
553 var->type = (m.declaration ? m.declaration : kvp.second.declaration)->type;
555 var->init_expression = m.initializer->clone();
557 kvp.second.decl_scope->body.insert(kvp.second.insert_point, var);
559 for(RefPtr<Expression> *r: m.references)
561 VariableReference *ref = new VariableReference;
562 ref->name = var->name;
566 any_dismantled = true;
570 return any_dismantled;
573 void AggregateDismantler::visit(Block &block)
575 SetForScope<Block *> set_block(current_block, &block);
576 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
583 void AggregateDismantler::visit(RefPtr<Expression> &expr)
587 if(r_aggregate_ref && r_reference.chain_len==1)
589 if((r_reference.chain[0]&0x3F)!=0x3F)
591 r_aggregate_ref->members[r_reference.chain[0]&0x3F].references.push_back(&expr);
592 r_aggregate_ref->members_referenced = true;
595 /* If the accessed member is not known, mark the entire aggregate as
597 r_aggregate_ref->referenced = true;
602 void AggregateDismantler::visit(VariableReference &var)
604 if(composite_reference)
605 r_reference.declaration = var.declaration;
608 /* If an aggregate variable is referenced as a whole, it should not be
610 auto i = aggregates.find(var.declaration);
611 if(i!=aggregates.end())
612 i->second.referenced = true;
616 void AggregateDismantler::visit_composite(RefPtr<Expression> &expr)
618 if(!composite_reference)
619 r_reference = Assignment::Target();
621 SetFlag set_composite(composite_reference);
625 void AggregateDismantler::visit(MemberAccess &memacc)
627 visit_composite(memacc.left);
629 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
631 if(r_reference.declaration && r_reference.chain_len==1)
633 auto i = aggregates.find(r_reference.declaration);
634 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
640 void AggregateDismantler::visit(BinaryExpression &binary)
642 if(binary.oper->token[0]=='[')
644 visit_composite(binary.left);
646 SetFlag clear_composite(composite_reference, false);
650 unsigned index = 0x3F;
651 if(Literal *literal_subscript = dynamic_cast<Literal *>(binary.right.get()))
652 if(literal_subscript->value.check_type<int>())
653 index = literal_subscript->value.value<int>();
654 add_to_chain(r_reference, Assignment::Target::ARRAY, index);
656 if(r_reference.declaration && r_reference.chain_len==1)
658 auto i = aggregates.find(r_reference.declaration);
659 r_aggregate_ref = (i!=aggregates.end() ? &i->second : 0);
666 SetFlag clear_composite(composite_reference, false);
667 TraversingVisitor::visit(binary);
671 void AggregateDismantler::visit(VariableDeclaration &var)
673 TraversingVisitor::visit(var);
675 if(var.interface.empty())
677 if(const StructDeclaration *strct = dynamic_cast<const StructDeclaration *>(var.type_declaration))
679 const FunctionCall *init_call = dynamic_cast<const FunctionCall *>(var.init_expression.get());
680 if((init_call && init_call->constructor) || !var.init_expression)
683 Aggregate &aggre = aggregates[&var];
684 aggre.declaration = &var;
685 aggre.decl_scope = current_block;
686 aggre.insert_point = insert_point;
689 for(const RefPtr<Statement> &s: strct->members.body)
691 if(const VariableDeclaration *mem_decl = dynamic_cast<const VariableDeclaration *>(s.get()))
693 AggregateMember member;
694 member.declaration = mem_decl;
697 member.initializer = init_call->arguments[i];
698 aggre.members.push_back(member);
704 else if(const Literal *literal_size = dynamic_cast<const Literal *>(var.array_size.get()))
706 if(literal_size->value.check_type<int>())
708 Aggregate &aggre = aggregates[&var];
709 aggre.declaration = &var;
710 aggre.decl_scope = current_block;
711 aggre.insert_point = insert_point;
713 int size = literal_size->value.value<int>();
714 for(int i=0; i<size; ++i)
716 AggregateMember member;
718 // Array initializers are not supported yet
719 aggre.members.push_back(member);
726 void AggregateDismantler::visit(FunctionDeclaration &func)
728 func.body.visit(*this);
733 T ConstantFolder::evaluate_logical(char oper, T left, T right)
737 case '&': return left&right;
738 case '|': return left|right;
739 case '^': return left^right;
745 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
747 switch(oper[0]|oper[1])
749 case '<': return left<right;
750 case '<'|'=': return left<=right;
751 case '>': return left>right;
752 case '>'|'=': return left>=right;
753 default: return false;
758 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
762 case '+': return left+right;
763 case '-': return left-right;
764 case '*': return left*right;
765 case '/': return left/right;
771 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
775 case '%': return left%right;
776 case '<': return left<<right;
777 case '>': return left>>right;
783 void ConstantFolder::convert_to_result(const Variant &value)
785 if(value.check_type<bool>())
786 set_result(static_cast<T>(value.value<bool>()));
787 else if(value.check_type<int>())
788 set_result(static_cast<T>(value.value<int>()));
789 else if(value.check_type<unsigned>())
790 set_result(static_cast<T>(value.value<unsigned>()));
791 else if(value.check_type<float>())
792 set_result(static_cast<T>(value.value<float>()));
795 void ConstantFolder::set_result(const Variant &value, bool literal)
797 r_constant_value = value;
802 void ConstantFolder::visit(RefPtr<Expression> &expr)
804 r_constant_value = Variant();
807 r_uses_iter_var = false;
809 /* Don't replace literals since they'd only be replaced with an identical
810 literal. Also skip anything that uses an iteration variable, but pass on
811 the result so the Iteration visiting function can handle it. */
812 if(!r_constant || r_literal || r_uses_iter_var)
815 RefPtr<Literal> literal = new Literal;
816 if(r_constant_value.check_type<bool>())
817 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
818 else if(r_constant_value.check_type<int>())
819 literal->token = lexical_cast<string>(r_constant_value.value<int>());
820 else if(r_constant_value.check_type<unsigned>())
821 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
822 else if(r_constant_value.check_type<float>())
824 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
825 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
826 literal->token += ".0";
833 literal->value = r_constant_value;
838 void ConstantFolder::visit(Literal &literal)
840 set_result(literal.value, true);
843 void ConstantFolder::visit(VariableReference &var)
845 /* If an iteration variable is initialized with a constant value, return
846 that value here for the purpose of evaluating the loop condition for the
848 if(var.declaration==iteration_var)
850 set_result(iter_init_value);
851 r_uses_iter_var = true;
855 void ConstantFolder::visit(MemberAccess &memacc)
857 TraversingVisitor::visit(memacc);
861 void ConstantFolder::visit(Swizzle &swizzle)
863 TraversingVisitor::visit(swizzle);
867 void ConstantFolder::visit(UnaryExpression &unary)
869 TraversingVisitor::visit(unary);
870 bool can_fold = r_constant;
875 char oper = unary.oper->token[0];
876 char oper2 = unary.oper->token[1];
879 if(r_constant_value.check_type<bool>())
880 set_result(!r_constant_value.value<bool>());
884 if(r_constant_value.check_type<int>())
885 set_result(~r_constant_value.value<int>());
886 else if(r_constant_value.check_type<unsigned>())
887 set_result(~r_constant_value.value<unsigned>());
889 else if(oper=='-' && !oper2)
891 if(r_constant_value.check_type<int>())
892 set_result(-r_constant_value.value<int>());
893 else if(r_constant_value.check_type<unsigned>())
894 set_result(-r_constant_value.value<unsigned>());
895 else if(r_constant_value.check_type<float>())
896 set_result(-r_constant_value.value<float>());
900 void ConstantFolder::visit(BinaryExpression &binary)
903 bool left_constant = r_constant;
904 bool left_iter_var = r_uses_iter_var;
905 Variant left_value = r_constant_value;
908 r_uses_iter_var = true;
910 bool can_fold = (left_constant && r_constant);
915 // Currently only expressions with both sides of equal types are handled.
916 if(!left_value.check_same_type(r_constant_value))
919 char oper = binary.oper->token[0];
920 char oper2 = binary.oper->token[1];
921 if(oper=='&' || oper=='|' || oper=='^')
923 if(oper2==oper && left_value.check_type<bool>())
924 set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
925 else if(!oper2 && left_value.check_type<int>())
926 set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
927 else if(!oper2 && left_value.check_type<unsigned>())
928 set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
930 else if((oper=='<' || oper=='>') && oper2!=oper)
932 if(left_value.check_type<int>())
933 set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
934 else if(left_value.check_type<unsigned>())
935 set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
936 else if(left_value.check_type<float>())
937 set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
939 else if((oper=='=' || oper=='!') && oper2=='=')
941 if(left_value.check_type<int>())
942 set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
943 else if(left_value.check_type<unsigned>())
944 set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
945 else if(left_value.check_type<float>())
946 set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
948 else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
950 if(left_value.check_type<int>())
951 set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
952 else if(left_value.check_type<unsigned>())
953 set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
954 else if(left_value.check_type<float>())
955 set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
957 else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
959 if(left_value.check_type<int>())
960 set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
961 else if(left_value.check_type<unsigned>())
962 set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
966 void ConstantFolder::visit(Assignment &assign)
968 TraversingVisitor::visit(assign);
972 void ConstantFolder::visit(TernaryExpression &ternary)
974 TraversingVisitor::visit(ternary);
978 void ConstantFolder::visit(FunctionCall &call)
980 if(call.constructor && call.type && call.arguments.size()==1)
982 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
985 visit(call.arguments[0]);
986 bool can_fold = r_constant;
991 if(basic->kind==BasicTypeDeclaration::BOOL)
992 convert_to_result<bool>(r_constant_value);
993 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
994 convert_to_result<int>(r_constant_value);
995 else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
996 convert_to_result<unsigned>(r_constant_value);
997 else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
998 convert_to_result<float>(r_constant_value);
1004 TraversingVisitor::visit(call);
1008 void ConstantFolder::visit(VariableDeclaration &var)
1010 if(iteration_init && var.init_expression)
1012 visit(var.init_expression);
1015 /* Record the value of a constant initialization expression of an
1016 iteration, so it can be used to evaluate the loop condition. */
1017 iteration_var = &var;
1018 iter_init_value = r_constant_value;
1022 TraversingVisitor::visit(var);
1025 void ConstantFolder::visit(Iteration &iter)
1027 SetForScope<Block *> set_block(current_block, &iter.body);
1029 /* The iteration variable is not normally inlined into expressions, so we
1030 process it specially here. If the initial value causes the loop condition
1031 to evaluate to false, then the expression can be folded. */
1033 if(iter.init_statement)
1035 SetFlag set_init(iteration_init);
1036 iter.init_statement->visit(*this);
1041 visit(iter.condition);
1042 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1044 RefPtr<Literal> literal = new Literal;
1045 literal->token = "false";
1046 literal->value = r_constant_value;
1047 iter.condition = literal;
1052 iter.body.visit(*this);
1053 if(iter.loop_expression)
1054 visit(iter.loop_expression);
1058 bool ConstantConditionEliminator::apply(Stage &stage)
1060 stage.content.visit(*this);
1061 NodeRemover().apply(stage, nodes_to_remove);
1062 return !nodes_to_remove.empty();
1065 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1067 if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1068 if(literal->value.check_type<bool>())
1069 return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1070 return NOT_CONSTANT;
1073 void ConstantConditionEliminator::visit(Block &block)
1075 SetForScope<Block *> set_block(current_block, &block);
1076 for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1083 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1085 r_ternary_result = 0;
1087 if(r_ternary_result)
1088 expr = r_ternary_result;
1089 r_ternary_result = 0;
1092 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1094 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1095 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1097 auto i = current_block->variables.find(var->name);
1098 r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1102 TraversingVisitor::visit(unary);
1105 void ConstantConditionEliminator::visit(Assignment &assign)
1107 auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1108 if(i==current_block->variables.end())
1109 r_external_side_effects = true;
1110 TraversingVisitor::visit(assign);
1113 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1115 ConstantStatus result = check_constant_condition(*ternary.condition);
1116 if(result!=NOT_CONSTANT)
1117 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1119 r_ternary_result = 0;
1122 void ConstantConditionEliminator::visit(FunctionCall &call)
1124 r_external_side_effects = true;
1125 TraversingVisitor::visit(call);
1128 void ConstantConditionEliminator::visit(Conditional &cond)
1130 ConstantStatus result = check_constant_condition(*cond.condition);
1131 if(result!=NOT_CONSTANT)
1133 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1134 // TODO should check variable names for conflicts. Potentially reuse InlineContentInjector?
1135 current_block->body.splice(insert_point, block.body);
1136 nodes_to_remove.insert(&cond);
1140 r_external_side_effects = false;
1141 TraversingVisitor::visit(cond);
1143 if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1144 nodes_to_remove.insert(&cond);
1147 void ConstantConditionEliminator::visit(Iteration &iter)
1151 ConstantStatus result = check_constant_condition(*iter.condition);
1152 if(result==CONSTANT_FALSE)
1154 nodes_to_remove.insert(&iter);
1159 r_external_side_effects = false;
1160 TraversingVisitor::visit(iter);
1161 if(iter.body.body.empty() && !r_external_side_effects)
1162 nodes_to_remove.insert(&iter);
1166 bool UnreachableCodeRemover::apply(Stage &stage)
1168 stage.content.visit(*this);
1169 NodeRemover().apply(stage, unreachable_nodes);
1170 return !unreachable_nodes.empty();
1173 void UnreachableCodeRemover::visit(Block &block)
1175 auto i = block.body.begin();
1176 for(; (reachable && i!=block.body.end()); ++i)
1178 for(; i!=block.body.end(); ++i)
1179 unreachable_nodes.insert(i->get());
1182 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1184 TraversingVisitor::visit(func);
1188 void UnreachableCodeRemover::visit(Conditional &cond)
1190 cond.body.visit(*this);
1191 bool reachable_if_true = reachable;
1193 cond.else_body.visit(*this);
1195 reachable |= reachable_if_true;
1198 void UnreachableCodeRemover::visit(Iteration &iter)
1200 TraversingVisitor::visit(iter);
1202 /* Always consider code after a loop reachable, since there's no checking
1203 for whether the loop executes. */
1208 bool UnusedTypeRemover::apply(Stage &stage)
1210 stage.content.visit(*this);
1211 NodeRemover().apply(stage, unused_nodes);
1212 return !unused_nodes.empty();
1215 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1217 unused_nodes.erase(expr->type);
1218 TraversingVisitor::visit(expr);
1221 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1224 unused_nodes.erase(type.base_type);
1225 unused_nodes.insert(&type);
1228 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1231 unused_nodes.erase(type.base_type);
1233 unused_nodes.erase(type.base_image);
1234 unused_nodes.insert(&type);
1237 void UnusedTypeRemover::visit(StructDeclaration &strct)
1239 unused_nodes.insert(&strct);
1240 TraversingVisitor::visit(strct);
1243 void UnusedTypeRemover::visit(VariableDeclaration &var)
1245 unused_nodes.erase(var.type_declaration);
1246 TraversingVisitor::visit(var);
1249 void UnusedTypeRemover::visit(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_composite(Expression &expr)
1313 if(!composite_reference)
1314 r_reference = Assignment::Target();
1316 SetFlag set_composite(composite_reference);
1320 void UnusedVariableRemover::visit(MemberAccess &memacc)
1322 visit_composite(*memacc.left);
1324 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1326 if(!composite_reference && r_reference.declaration)
1327 referenced(r_reference, memacc);
1330 void UnusedVariableRemover::visit(Swizzle &swizzle)
1332 visit_composite(*swizzle.left);
1335 for(unsigned i=0; i<swizzle.count; ++i)
1336 mask |= 1<<swizzle.components[i];
1337 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1339 if(!composite_reference && r_reference.declaration)
1340 referenced(r_reference, swizzle);
1343 void UnusedVariableRemover::visit(UnaryExpression &unary)
1345 TraversingVisitor::visit(unary);
1346 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1347 r_side_effects = true;
1350 void UnusedVariableRemover::visit(BinaryExpression &binary)
1352 if(binary.oper->token[0]=='[')
1354 visit_composite(*binary.left);
1357 SetFlag clear_assignment(assignment_target, false);
1358 SetFlag clear_composite(composite_reference, false);
1359 SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1360 binary.right->visit(*this);
1363 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1365 if(!composite_reference && r_reference.declaration)
1366 referenced(r_reference, binary);
1370 SetFlag clear_composite(composite_reference, false);
1371 TraversingVisitor::visit(binary);
1375 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1377 SetFlag clear_composite(composite_reference, false);
1378 TraversingVisitor::visit(ternary);
1381 void UnusedVariableRemover::visit(Assignment &assign)
1384 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1385 assign.left->visit(*this);
1387 assign.right->visit(*this);
1388 r_assignment = &assign;
1389 r_side_effects = true;
1392 void UnusedVariableRemover::visit(FunctionCall &call)
1394 SetFlag clear_composite(composite_reference, false);
1395 TraversingVisitor::visit(call);
1396 /* Treat function calls as having side effects so expression statements
1397 consisting of nothing but a function call won't be optimized away. */
1398 r_side_effects = true;
1400 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1402 for(const auto &kvp: variables)
1403 if(kvp.second.output)
1404 referenced(kvp.first, call);
1408 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1410 assignments.emplace_back();
1411 AssignmentInfo &assign_info = assignments.back();
1412 assign_info.node = &node;
1413 assign_info.target = target;
1414 assign_info.in_loop = in_loop;
1416 /* An assignment to the target hides any assignments to the same target or
1418 VariableInfo &var_info = variables[target.declaration];
1419 for(unsigned i=0; i<var_info.assignments.size(); )
1421 const Assignment::Target &t = var_info.assignments[i]->target;
1423 bool subfield = (t.chain_len>=target.chain_len);
1424 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1425 subfield = (t.chain[j]==target.chain[j]);
1428 var_info.assignments.erase(var_info.assignments.begin()+i);
1433 var_info.assignments.push_back(&assign_info);
1436 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1439 r_side_effects = false;
1440 TraversingVisitor::visit(expr);
1441 if(r_assignment && r_assignment->target.declaration)
1442 record_assignment(r_assignment->target, expr);
1444 unused_nodes.insert(&expr);
1447 void UnusedVariableRemover::visit(StructDeclaration &strct)
1449 SetFlag set_struct(in_struct);
1450 TraversingVisitor::visit(strct);
1453 void UnusedVariableRemover::visit(VariableDeclaration &var)
1455 TraversingVisitor::visit(var);
1460 VariableInfo &var_info = variables[&var];
1462 /* Mark variables as output if they're used by the next stage or the
1464 bool builtin = (!var.name.compare(0, 3, "gl_") || (var.block_declaration && !var.block_declaration->block_name.compare(0, 3, "gl_")));
1465 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || builtin));
1467 // Linked outputs are automatically referenced.
1468 if(var_info.output && var.linked_declaration)
1469 var_info.referenced = true;
1471 if(var.init_expression)
1473 var_info.initialized = true;
1474 record_assignment(&var, *var.init_expression);
1478 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1480 for(const auto &kvp: other_vars)
1482 auto j = variables.find(kvp.first);
1483 if(j!=variables.end())
1485 /* The merged blocks started as copies of each other so any common
1486 assignments must be in the beginning. */
1488 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1489 if(kvp.second.assignments[k]!=j->second.assignments[k])
1492 // Remaining assignments are unique to each block; merge them.
1493 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1494 j->second.referenced |= kvp.second.referenced;
1497 variables.insert(kvp);
1501 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1503 if(func.body.body.empty())
1506 BlockVariableMap saved_vars = variables;
1507 // Assignments from other functions should not be visible.
1508 for(auto &kvp: variables)
1509 kvp.second.assignments.resize(kvp.second.initialized);
1510 TraversingVisitor::visit(func);
1511 swap(variables, saved_vars);
1512 merge_variables(saved_vars);
1514 /* Always treat function parameters as referenced. Removing unused
1515 parameters is not currently supported. */
1516 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1518 auto j = variables.find(p.get());
1519 if(j!=variables.end())
1520 j->second.referenced = true;
1524 void UnusedVariableRemover::visit(Conditional &cond)
1526 cond.condition->visit(*this);
1527 BlockVariableMap saved_vars = variables;
1528 cond.body.visit(*this);
1529 swap(saved_vars, variables);
1530 cond.else_body.visit(*this);
1532 /* Visible assignments after the conditional is the union of those visible
1533 at the end of the if and else blocks. If there was no else block, then it's
1534 the union of the if block and the state before it. */
1535 merge_variables(saved_vars);
1538 void UnusedVariableRemover::visit(Iteration &iter)
1540 BlockVariableMap saved_vars = variables;
1541 vector<Node *> saved_refs;
1542 swap(loop_ext_refs, saved_refs);
1544 if(iter.init_statement)
1545 iter.init_statement->visit(*this);
1546 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1548 iter.condition->visit(*this);
1549 iter.body.visit(*this);
1550 if(iter.loop_expression)
1551 iter.loop_expression->visit(*this);
1553 swap(loop_ext_refs, saved_refs);
1555 /* Visit the external references of the loop again to record assignments
1556 done in the loop as used. */
1557 for(Node *n: saved_refs)
1560 /* Merge assignments from the iteration, without clearing previous state.
1561 Further analysis is needed to determine which parts of the iteration body
1562 are always executed, if any. */
1563 merge_variables(saved_vars);
1567 bool UnusedFunctionRemover::apply(Stage &stage)
1569 stage.content.visit(*this);
1570 NodeRemover().apply(stage, unused_nodes);
1571 return !unused_nodes.empty();
1574 void UnusedFunctionRemover::visit(FunctionCall &call)
1576 TraversingVisitor::visit(call);
1578 unused_nodes.erase(call.declaration);
1579 if(call.declaration && call.declaration->definition!=call.declaration)
1580 used_definitions.insert(call.declaration->definition);
1583 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1585 TraversingVisitor::visit(func);
1587 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1588 unused_nodes.insert(&func);