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);
1232 unused_nodes.insert(&type);
1235 void UnusedTypeRemover::visit(StructDeclaration &strct)
1237 unused_nodes.insert(&strct);
1238 TraversingVisitor::visit(strct);
1241 void UnusedTypeRemover::visit(VariableDeclaration &var)
1243 unused_nodes.erase(var.type_declaration);
1244 TraversingVisitor::visit(var);
1247 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1249 unused_nodes.erase(func.return_type_declaration);
1250 TraversingVisitor::visit(func);
1254 bool UnusedVariableRemover::apply(Stage &s)
1257 s.content.visit(*this);
1259 for(const AssignmentInfo &a: assignments)
1260 if(a.used_by.empty())
1261 unused_nodes.insert(a.node);
1263 for(const auto &kvp: variables)
1265 if(!kvp.second.referenced)
1266 unused_nodes.insert(kvp.first);
1267 else if(kvp.second.output)
1269 /* The last visible assignments of output variables are used by the
1270 next stage or the API. */
1271 for(AssignmentInfo *a: kvp.second.assignments)
1272 unused_nodes.erase(a->node);
1276 NodeRemover().apply(s, unused_nodes);
1278 return !unused_nodes.empty();
1281 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1283 VariableInfo &var_info = variables[target.declaration];
1284 var_info.referenced = true;
1285 if(!assignment_target)
1287 bool loop_external = false;
1288 for(AssignmentInfo *a: var_info.assignments)
1289 if(targets_overlap(a->target, target))
1291 a->used_by.push_back(&node);
1292 if(a->in_loop<in_loop)
1293 loop_external = true;
1297 loop_ext_refs.push_back(&node);
1301 void UnusedVariableRemover::visit(VariableReference &var)
1303 if(composite_reference)
1304 r_reference.declaration = var.declaration;
1305 else if(var.declaration)
1306 referenced(var.declaration, var);
1309 void UnusedVariableRemover::visit_composite(Expression &expr)
1311 if(!composite_reference)
1312 r_reference = Assignment::Target();
1314 SetFlag set_composite(composite_reference);
1318 void UnusedVariableRemover::visit(MemberAccess &memacc)
1320 visit_composite(*memacc.left);
1322 add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1324 if(!composite_reference && r_reference.declaration)
1325 referenced(r_reference, memacc);
1328 void UnusedVariableRemover::visit(Swizzle &swizzle)
1330 visit_composite(*swizzle.left);
1333 for(unsigned i=0; i<swizzle.count; ++i)
1334 mask |= 1<<swizzle.components[i];
1335 add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1337 if(!composite_reference && r_reference.declaration)
1338 referenced(r_reference, swizzle);
1341 void UnusedVariableRemover::visit(UnaryExpression &unary)
1343 TraversingVisitor::visit(unary);
1344 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1345 r_side_effects = true;
1348 void UnusedVariableRemover::visit(BinaryExpression &binary)
1350 if(binary.oper->token[0]=='[')
1352 visit_composite(*binary.left);
1355 SetFlag clear_assignment(assignment_target, false);
1356 SetFlag clear_composite(composite_reference, false);
1357 SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1358 binary.right->visit(*this);
1361 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1363 if(!composite_reference && r_reference.declaration)
1364 referenced(r_reference, binary);
1368 SetFlag clear_composite(composite_reference, false);
1369 TraversingVisitor::visit(binary);
1373 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1375 SetFlag clear_composite(composite_reference, false);
1376 TraversingVisitor::visit(ternary);
1379 void UnusedVariableRemover::visit(Assignment &assign)
1382 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1383 assign.left->visit(*this);
1385 assign.right->visit(*this);
1386 r_assignment = &assign;
1387 r_side_effects = true;
1390 void UnusedVariableRemover::visit(FunctionCall &call)
1392 SetFlag clear_composite(composite_reference, false);
1393 TraversingVisitor::visit(call);
1394 /* Treat function calls as having side effects so expression statements
1395 consisting of nothing but a function call won't be optimized away. */
1396 r_side_effects = true;
1398 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1400 for(const auto &kvp: variables)
1401 if(kvp.second.output)
1402 referenced(kvp.first, call);
1406 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1408 assignments.emplace_back();
1409 AssignmentInfo &assign_info = assignments.back();
1410 assign_info.node = &node;
1411 assign_info.target = target;
1412 assign_info.in_loop = in_loop;
1414 /* An assignment to the target hides any assignments to the same target or
1416 VariableInfo &var_info = variables[target.declaration];
1417 for(unsigned i=0; i<var_info.assignments.size(); )
1419 const Assignment::Target &t = var_info.assignments[i]->target;
1421 bool subfield = (t.chain_len>=target.chain_len);
1422 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1423 subfield = (t.chain[j]==target.chain[j]);
1426 var_info.assignments.erase(var_info.assignments.begin()+i);
1431 var_info.assignments.push_back(&assign_info);
1434 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1437 r_side_effects = false;
1438 TraversingVisitor::visit(expr);
1439 if(r_assignment && r_assignment->target.declaration)
1440 record_assignment(r_assignment->target, expr);
1442 unused_nodes.insert(&expr);
1445 void UnusedVariableRemover::visit(StructDeclaration &strct)
1447 SetFlag set_struct(in_struct);
1448 TraversingVisitor::visit(strct);
1451 void UnusedVariableRemover::visit(VariableDeclaration &var)
1453 TraversingVisitor::visit(var);
1458 VariableInfo &var_info = variables[&var];
1460 /* Mark variables as output if they're used by the next stage or the
1462 bool builtin = (!var.name.compare(0, 3, "gl_") || (var.block_declaration && !var.block_declaration->block_name.compare(0, 3, "gl_")));
1463 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || builtin));
1465 // Linked outputs are automatically referenced.
1466 if(var_info.output && var.linked_declaration)
1467 var_info.referenced = true;
1469 if(var.init_expression)
1471 var_info.initialized = true;
1472 record_assignment(&var, *var.init_expression);
1476 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1478 for(const auto &kvp: other_vars)
1480 auto j = variables.find(kvp.first);
1481 if(j!=variables.end())
1483 /* The merged blocks started as copies of each other so any common
1484 assignments must be in the beginning. */
1486 for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1487 if(kvp.second.assignments[k]!=j->second.assignments[k])
1490 // Remaining assignments are unique to each block; merge them.
1491 j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1492 j->second.referenced |= kvp.second.referenced;
1495 variables.insert(kvp);
1499 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1501 if(func.body.body.empty())
1504 BlockVariableMap saved_vars = variables;
1505 // Assignments from other functions should not be visible.
1506 for(auto &kvp: variables)
1507 kvp.second.assignments.resize(kvp.second.initialized);
1508 TraversingVisitor::visit(func);
1509 swap(variables, saved_vars);
1510 merge_variables(saved_vars);
1512 /* Always treat function parameters as referenced. Removing unused
1513 parameters is not currently supported. */
1514 for(const RefPtr<VariableDeclaration> &p: func.parameters)
1516 auto j = variables.find(p.get());
1517 if(j!=variables.end())
1518 j->second.referenced = true;
1522 void UnusedVariableRemover::visit(Conditional &cond)
1524 cond.condition->visit(*this);
1525 BlockVariableMap saved_vars = variables;
1526 cond.body.visit(*this);
1527 swap(saved_vars, variables);
1528 cond.else_body.visit(*this);
1530 /* Visible assignments after the conditional is the union of those visible
1531 at the end of the if and else blocks. If there was no else block, then it's
1532 the union of the if block and the state before it. */
1533 merge_variables(saved_vars);
1536 void UnusedVariableRemover::visit(Iteration &iter)
1538 BlockVariableMap saved_vars = variables;
1539 vector<Node *> saved_refs;
1540 swap(loop_ext_refs, saved_refs);
1542 if(iter.init_statement)
1543 iter.init_statement->visit(*this);
1544 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1546 iter.condition->visit(*this);
1547 iter.body.visit(*this);
1548 if(iter.loop_expression)
1549 iter.loop_expression->visit(*this);
1551 swap(loop_ext_refs, saved_refs);
1553 /* Visit the external references of the loop again to record assignments
1554 done in the loop as used. */
1555 for(Node *n: saved_refs)
1558 /* Merge assignments from the iteration, without clearing previous state.
1559 Further analysis is needed to determine which parts of the iteration body
1560 are always executed, if any. */
1561 merge_variables(saved_vars);
1565 bool UnusedFunctionRemover::apply(Stage &stage)
1567 stage.content.visit(*this);
1568 NodeRemover().apply(stage, unused_nodes);
1569 return !unused_nodes.empty();
1572 void UnusedFunctionRemover::visit(FunctionCall &call)
1574 TraversingVisitor::visit(call);
1576 unused_nodes.erase(call.declaration);
1577 if(call.declaration && call.declaration->definition!=call.declaration)
1578 used_definitions.insert(call.declaration->definition);
1581 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1583 TraversingVisitor::visit(func);
1585 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1586 unused_nodes.insert(&func);