1 #include <msp/core/raii.h>
2 #include <msp/strings/format.h>
11 InlineableFunctionLocator::InlineableFunctionLocator():
16 void InlineableFunctionLocator::visit(FunctionCall &call)
18 FunctionDeclaration *def = call.declaration;
20 def = def->definition;
24 unsigned &count = refcounts[def];
26 /* Don't inline functions which are called more than once or are called
28 if(count>1 || def==current_function)
29 inlineable.erase(def);
32 TraversingVisitor::visit(call);
35 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
37 unsigned &count = refcounts[func.definition];
38 if(count<=1 && func.parameters.empty())
39 inlineable.insert(func.definition);
41 SetForScope<FunctionDeclaration *> set(current_function, &func);
43 TraversingVisitor::visit(func);
46 void InlineableFunctionLocator::visit(Conditional &cond)
48 TraversingVisitor::visit(cond);
49 inlineable.erase(current_function);
52 void InlineableFunctionLocator::visit(Iteration &iter)
54 TraversingVisitor::visit(iter);
55 inlineable.erase(current_function);
58 void InlineableFunctionLocator::visit(Return &ret)
60 TraversingVisitor::visit(ret);
62 inlineable.erase(current_function);
67 InlineContentInjector::InlineContentInjector():
73 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionDeclaration &src)
75 target_block = &tgt_blk;
77 remap_prefix = source_func->name;
79 vector<RefPtr<Statement> > inlined;
80 inlined.reserve(src.body.body.size());
81 for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
83 r_inlined_statement = 0;
85 if(!r_inlined_statement)
86 r_inlined_statement = (*i)->clone();
88 SetForScope<unsigned> set_remap(remap_names, 2);
89 r_inlined_statement->visit(*this);
90 inlined.push_back(r_inlined_statement);
93 // Insert the variables here to enable further inlinings to avoid conflicts.
94 tgt_blk.variables.insert(variable_map.begin(), variable_map.end());
96 SetForScope<unsigned> set_remap(remap_names, 1);
97 SetForScope<string> set_prefix(remap_prefix, target_func.name);
99 target_func.visit(*this);
101 tgt_blk.body.insert(ins_pt, inlined.begin(), inlined.end());
103 NodeReorderer().apply(stage, target_func, dependencies);
105 return r_result_name;
108 void InlineContentInjector::visit(VariableReference &var)
112 map<string, VariableDeclaration *>::const_iterator i = variable_map.find(var.name);
113 if(i!=variable_map.end())
114 var.name = i->second->name;
116 else if(var.declaration)
118 SetFlag set_deps(deps_only);
119 if(!variable_map.count(var.name))
121 dependencies.insert(var.declaration);
122 referenced_names.insert(var.name);
124 var.declaration->visit(*this);
128 void InlineContentInjector::visit(InterfaceBlockReference &iface)
130 if(!remap_names && iface.declaration)
132 SetFlag set_deps(deps_only);
133 dependencies.insert(iface.declaration);
134 referenced_names.insert(iface.name);
135 iface.declaration->visit(*this);
139 void InlineContentInjector::visit(FunctionCall &call)
141 if(!remap_names && call.declaration)
143 dependencies.insert(call.declaration);
144 referenced_names.insert(call.name);
146 TraversingVisitor::visit(call);
149 void InlineContentInjector::visit(VariableDeclaration &var)
151 TraversingVisitor::visit(var);
155 if(remap_names==2 || referenced_names.count(var.name))
157 string mapped_name = get_unused_variable_name(*target_block, var.name, remap_prefix);
158 variable_map[var.name] = &var;
159 var.name = mapped_name;
162 else if(var.type_declaration)
164 SetFlag set_deps(deps_only);
165 dependencies.insert(var.type_declaration);
166 referenced_names.insert(var.type_declaration->name);
167 var.type_declaration->visit(*this);
171 void InlineContentInjector::visit(Return &ret)
173 TraversingVisitor::visit(ret);
175 if(!remap_names && ret.expression)
177 /* Create a new variable to hold the return value of the inlined
179 r_result_name = get_unused_variable_name(*target_block, "_return", source_func->name);
180 RefPtr<VariableDeclaration> var = new VariableDeclaration;
181 var->source = ret.source;
182 var->line = ret.line;
183 var->type = source_func->return_type;
184 var->name = r_result_name;
185 var->init_expression = ret.expression->clone();
186 r_inlined_statement = var;
191 FunctionInliner::FunctionInliner():
196 bool FunctionInliner::apply(Stage &s)
199 inlineable = InlineableFunctionLocator().apply(s);
200 r_any_inlined = false;
201 s.content.visit(*this);
202 return r_any_inlined;
205 void FunctionInliner::visit(RefPtr<Expression> &ptr)
211 ptr = r_inline_result;
212 r_any_inlined = true;
217 void FunctionInliner::visit(Block &block)
219 SetForScope<Block *> set_block(current_block, &block);
220 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
221 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
228 void FunctionInliner::visit(FunctionCall &call)
230 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
233 FunctionDeclaration *def = call.declaration;
235 def = def->definition;
237 if(def && inlineable.count(def))
239 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
241 // This will later get removed by UnusedVariableRemover.
242 if(result_name.empty())
243 result_name = "msp_unused_from_inline";
245 RefPtr<VariableReference> ref = new VariableReference;
246 ref->name = result_name;
247 r_inline_result = ref;
249 /* Inlined variables need to be resolved before this function can be
251 inlineable.erase(current_function);
255 void FunctionInliner::visit(FunctionDeclaration &func)
257 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
258 TraversingVisitor::visit(func);
261 void FunctionInliner::visit(Iteration &iter)
263 /* Visit the initialization statement before entering the loop body so the
264 inlined statements get inserted outside. */
265 if(iter.init_statement)
266 iter.init_statement->visit(*this);
268 SetForScope<Block *> set_block(current_block, &iter.body);
269 /* Skip the condition and loop expression parts because they're not properly
270 inside the body block. Inlining anything into them will require a more
271 comprehensive transformation. */
272 iter.body.visit(*this);
276 ExpressionInliner::ExpressionInfo::ExpressionInfo():
285 ExpressionInliner::ExpressionInliner():
287 r_any_inlined(false),
290 iteration_init(false),
295 bool ExpressionInliner::apply(Stage &s)
297 s.content.visit(*this);
298 return r_any_inlined;
301 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
304 r_any_inlined = true;
307 void ExpressionInliner::visit(Block &block)
309 TraversingVisitor::visit(block);
311 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
313 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
314 for(; (j!=expressions.end() && j->first.declaration==i->second); )
316 if(j->second.expression && j->second.inline_point)
317 inline_expression(*j->second.expression, *j->second.inline_point);
319 expressions.erase(j++);
323 /* Expressions assigned in this block may depend on local variables of the
324 block. If this is a conditionally executed block, the assignments might not
325 always happen. Mark the expressions as not available to any outer blocks. */
326 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
327 if(i->second.assign_scope==&block)
328 i->second.available = false;
331 void ExpressionInliner::visit(RefPtr<Expression> &expr)
335 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
337 if(iteration_body && !r_ref_info->trivial)
339 /* Don't inline non-trivial expressions which were assigned outside
340 an iteration statement. The iteration may run multiple times, which
341 would cause the expression to also be evaluated multiple times. */
342 Block *i = r_ref_info->assign_scope;
343 for(; (i && i!=iteration_body); i=i->parent) ;
348 if(r_ref_info->trivial)
349 inline_expression(*r_ref_info->expression, expr);
351 /* Record the inline point for a non-trivial expression but don't
352 inline it yet. It might turn out it shouldn't be inlined after all. */
353 r_ref_info->inline_point = &expr;
359 void ExpressionInliner::visit(VariableReference &var)
363 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
364 if(i!=expressions.end())
366 /* If a non-trivial expression is referenced multiple times, don't
368 if(i->second.inline_point && !i->second.trivial)
369 i->second.expression = 0;
370 /* Mutating expressions are analogous to self-referencing assignments
371 and prevent inlining. */
373 i->second.expression = 0;
374 r_ref_info = &i->second;
379 void ExpressionInliner::visit(MemberAccess &memacc)
385 void ExpressionInliner::visit(Swizzle &swizzle)
391 void ExpressionInliner::visit(UnaryExpression &unary)
393 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
394 visit(unary.expression);
398 void ExpressionInliner::visit(BinaryExpression &binary)
402 SetFlag clear_target(mutating, false);
408 void ExpressionInliner::visit(Assignment &assign)
411 SetFlag set_target(mutating);
417 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
418 if(i!=expressions.end())
420 /* Self-referencing assignments can't be inlined without additional
421 work. Just clear any previous expression. */
422 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
423 i->second.assign_scope = current_block;
424 i->second.inline_point = 0;
425 i->second.available = true;
431 void ExpressionInliner::visit(TernaryExpression &ternary)
433 visit(ternary.condition);
434 visit(ternary.true_expr);
435 visit(ternary.false_expr);
439 void ExpressionInliner::visit(FunctionCall &call)
441 TraversingVisitor::visit(call);
445 void ExpressionInliner::visit(VariableDeclaration &var)
449 TraversingVisitor::visit(var);
451 bool constant = var.constant;
452 if(constant && var.layout)
454 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
455 constant = (i->name!="constant_id");
458 /* Only inline global variables if they're constant and have trivial
459 initializers. Non-constant variables could change in ways which are hard to
460 analyze and non-trivial expressions could be expensive to inline. */
461 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
463 ExpressionInfo &info = expressions[&var];
464 /* Assume variables declared in an iteration initialization statement
465 will have their values change throughout the iteration. */
466 info.expression = (iteration_init ? 0 : var.init_expression.get());
467 info.assign_scope = current_block;
468 info.trivial = r_trivial;
472 void ExpressionInliner::visit(Iteration &iter)
474 SetForScope<Block *> set_block(current_block, &iter.body);
475 if(iter.init_statement)
477 SetFlag set_init(iteration_init);
478 iter.init_statement->visit(*this);
481 SetForScope<Block *> set_body(iteration_body, &iter.body);
483 visit(iter.condition);
484 iter.body.visit(*this);
485 if(iter.loop_expression)
486 visit(iter.loop_expression);
490 void ConstantConditionEliminator::apply(Stage &stage)
492 stage.content.visit(*this);
493 NodeRemover().apply(stage, nodes_to_remove);
496 void ConstantConditionEliminator::visit(Block &block)
498 SetForScope<Block *> set_block(current_block, &block);
499 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
506 void ConstantConditionEliminator::visit(Conditional &cond)
508 if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
509 if(literal->value.check_type<bool>())
511 Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
512 current_block->body.splice(insert_point, block.body);
513 nodes_to_remove.insert(&cond);
517 TraversingVisitor::visit(cond);
520 void ConstantConditionEliminator::visit(Iteration &iter)
524 /* If the loop condition is always false on the first iteration, the
525 entire loop can be removed */
526 ExpressionEvaluator::ValueMap values;
527 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
528 values[var] = var->init_expression.get();
529 ExpressionEvaluator eval(values);
530 iter.condition->visit(eval);
531 if(eval.is_result_valid() && !eval.get_result())
533 nodes_to_remove.insert(&iter);
538 TraversingVisitor::visit(iter);
542 bool UnusedTypeRemover::apply(Stage &stage)
544 stage.content.visit(*this);
545 NodeRemover().apply(stage, unused_nodes);
546 return !unused_nodes.empty();
549 void UnusedTypeRemover::visit(Literal &literal)
551 unused_nodes.erase(literal.type);
554 void UnusedTypeRemover::visit(UnaryExpression &unary)
556 unused_nodes.erase(unary.type);
557 TraversingVisitor::visit(unary);
560 void UnusedTypeRemover::visit(BinaryExpression &binary)
562 unused_nodes.erase(binary.type);
563 TraversingVisitor::visit(binary);
566 void UnusedTypeRemover::visit(TernaryExpression &ternary)
568 unused_nodes.erase(ternary.type);
569 TraversingVisitor::visit(ternary);
572 void UnusedTypeRemover::visit(FunctionCall &call)
574 unused_nodes.erase(call.type);
575 TraversingVisitor::visit(call);
578 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
581 unused_nodes.erase(type.base_type);
582 unused_nodes.insert(&type);
585 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
588 unused_nodes.erase(type.base_type);
589 unused_nodes.insert(&type);
592 void UnusedTypeRemover::visit(StructDeclaration &strct)
594 unused_nodes.insert(&strct);
595 TraversingVisitor::visit(strct);
598 void UnusedTypeRemover::visit(VariableDeclaration &var)
600 unused_nodes.erase(var.type_declaration);
603 void UnusedTypeRemover::visit(InterfaceBlock &iface)
605 unused_nodes.erase(iface.type_declaration);
608 void UnusedTypeRemover::visit(FunctionDeclaration &func)
610 unused_nodes.erase(func.return_type_declaration);
611 TraversingVisitor::visit(func);
615 UnusedVariableRemover::UnusedVariableRemover():
619 assignment_target(false),
620 r_side_effects(false)
623 bool UnusedVariableRemover::apply(Stage &s)
626 s.content.visit(*this);
628 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
629 if(i->used_by.empty())
630 unused_nodes.insert(i->node);
632 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
633 if(i->second->instance_name.empty())
634 unused_nodes.insert(i->second);
636 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
640 /* The last visible assignments of output variables are used by the
641 next stage or the API. */
642 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
643 unused_nodes.erase((*j)->node);
646 if(!i->second.output && !i->second.referenced)
648 // Don't remove variables from inside interface blocks.
649 if(!i->second.interface_block)
650 unused_nodes.insert(i->first);
652 else if(i->second.interface_block)
653 // Interface blocks are kept if even one member is used.
654 unused_nodes.erase(i->second.interface_block);
657 NodeRemover().apply(s, unused_nodes);
659 return !unused_nodes.empty();
662 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
664 VariableInfo &var_info = variables[target.declaration];
665 var_info.referenced = true;
666 if(!assignment_target)
668 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
669 (*i)->used_by.push_back(&node);
673 void UnusedVariableRemover::visit(VariableReference &var)
675 referenced(var.declaration, var);
678 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
680 referenced(iface.declaration, iface);
683 void UnusedVariableRemover::visit(UnaryExpression &unary)
685 TraversingVisitor::visit(unary);
686 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
687 r_side_effects = true;
690 void UnusedVariableRemover::visit(BinaryExpression &binary)
692 if(binary.oper->token[0]=='[')
694 binary.left->visit(*this);
695 SetFlag set(assignment_target, false);
696 binary.right->visit(*this);
699 TraversingVisitor::visit(binary);
702 void UnusedVariableRemover::visit(Assignment &assign)
705 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
706 assign.left->visit(*this);
708 assign.right->visit(*this);
709 r_assignment = &assign;
710 r_side_effects = true;
713 void UnusedVariableRemover::visit(FunctionCall &call)
715 TraversingVisitor::visit(call);
716 /* Treat function calls as having side effects so expression statements
717 consisting of nothing but a function call won't be optimized away. */
718 r_side_effects = true;
720 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
722 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
724 referenced(i->first, call);
728 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
730 assignments.push_back(AssignmentInfo());
731 AssignmentInfo &assign_info = assignments.back();
732 assign_info.node = &node;
733 assign_info.target = target;
735 /* An assignment to the target hides any assignments to the same target or
737 VariableInfo &var_info = variables[target.declaration];
738 for(unsigned i=0; i<var_info.assignments.size(); ++i)
740 const Assignment::Target &t = var_info.assignments[i]->target;
742 bool subfield = (t.chain_len>=target.chain_len);
743 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
744 subfield = (t.chain[j]==target.chain[j]);
747 var_info.assignments.erase(var_info.assignments.begin()+i);
752 var_info.assignments.push_back(&assign_info);
755 void UnusedVariableRemover::visit(ExpressionStatement &expr)
758 r_side_effects = false;
759 TraversingVisitor::visit(expr);
760 if(r_assignment && r_assignment->target.declaration)
761 record_assignment(r_assignment->target, expr);
763 unused_nodes.insert(&expr);
766 void UnusedVariableRemover::visit(VariableDeclaration &var)
768 VariableInfo &var_info = variables[&var];
769 var_info.interface_block = interface_block;
771 /* Mark variables as output if they're used by the next stage or the
774 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
776 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
778 if(var.init_expression)
780 var_info.initialized = true;
781 record_assignment(&var, *var.init_expression);
783 TraversingVisitor::visit(var);
786 void UnusedVariableRemover::visit(InterfaceBlock &iface)
788 if(iface.instance_name.empty())
790 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
791 iface.struct_declaration->members.visit(*this);
795 VariableInfo &var_info = variables[&iface];
796 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
800 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
802 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
804 BlockVariableMap::iterator j = variables.find(i->first);
805 if(j!=variables.end())
807 /* The merged blocks started as copies of each other so any common
808 assignments must be in the beginning. */
810 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
811 if(i->second.assignments[k]!=j->second.assignments[k])
814 // Remaining assignments are unique to each block; merge them.
815 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
816 j->second.referenced |= i->second.referenced;
819 variables.insert(*i);
823 void UnusedVariableRemover::visit(FunctionDeclaration &func)
825 if(func.body.body.empty())
828 BlockVariableMap saved_vars = variables;
829 // Assignments from other functions should not be visible.
830 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
831 i->second.assignments.resize(i->second.initialized);
832 TraversingVisitor::visit(func);
833 swap(variables, saved_vars);
834 merge_variables(saved_vars);
836 /* Always treat function parameters as referenced. Removing unused
837 parameters is not currently supported. */
838 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
840 BlockVariableMap::iterator j = variables.find(i->get());
841 if(j!=variables.end())
842 j->second.referenced = true;
846 void UnusedVariableRemover::visit(Conditional &cond)
848 cond.condition->visit(*this);
849 BlockVariableMap saved_vars = variables;
850 cond.body.visit(*this);
851 swap(saved_vars, variables);
852 cond.else_body.visit(*this);
854 /* Visible assignments after the conditional is the union of those visible
855 at the end of the if and else blocks. If there was no else block, then it's
856 the union of the if block and the state before it. */
857 merge_variables(saved_vars);
860 void UnusedVariableRemover::visit(Iteration &iter)
862 BlockVariableMap saved_vars = variables;
863 TraversingVisitor::visit(iter);
865 /* Merge assignments from the iteration, without clearing previous state.
866 Further analysis is needed to determine which parts of the iteration body
867 are always executed, if any. */
868 merge_variables(saved_vars);
872 bool UnusedFunctionRemover::apply(Stage &stage)
874 stage.content.visit(*this);
875 NodeRemover().apply(stage, unused_nodes);
876 return !unused_nodes.empty();
879 void UnusedFunctionRemover::visit(FunctionCall &call)
881 TraversingVisitor::visit(call);
883 unused_nodes.erase(call.declaration);
884 if(call.declaration && call.declaration->definition!=call.declaration)
885 used_definitions.insert(call.declaration->definition);
888 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
890 TraversingVisitor::visit(func);
892 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
893 unused_nodes.insert(&func);