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 for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
79 r_inlined_statement = 0;
81 if(!r_inlined_statement)
82 r_inlined_statement = (*i)->clone();
84 SetFlag set_remap(remap_names);
85 r_inlined_statement->visit(*this);
86 tgt_blk.body.insert(ins_pt, r_inlined_statement);
89 NodeReorderer().apply(stage, target_func, dependencies);
94 string InlineContentInjector::create_unused_name(const string &base, bool always_prefix)
97 if(always_prefix || target_block->variables.count(result))
98 result = format("_%s_%s", source_func->name, base);
99 unsigned initial_size = result.size();
100 for(unsigned i=1; target_block->variables.count(result); ++i)
102 result.erase(initial_size);
103 result += format("_%d", i);
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 dependencies.insert(var.declaration);
120 var.declaration->visit(*this);
124 void InlineContentInjector::visit(InterfaceBlockReference &iface)
126 if(!remap_names && iface.declaration)
128 SetFlag set_deps(deps_only);
129 dependencies.insert(iface.declaration);
130 iface.declaration->visit(*this);
134 void InlineContentInjector::visit(FunctionCall &call)
136 if(!remap_names && call.declaration)
137 dependencies.insert(call.declaration);
138 TraversingVisitor::visit(call);
141 void InlineContentInjector::visit(VariableDeclaration &var)
143 TraversingVisitor::visit(var);
145 if(var.type_declaration)
147 SetFlag set_deps(deps_only);
148 dependencies.insert(var.type_declaration);
149 var.type_declaration->visit(*this);
152 if(!remap_names && !deps_only)
154 RefPtr<VariableDeclaration> inlined_var = var.clone();
155 inlined_var->name = create_unused_name(var.name, false);
156 r_inlined_statement = inlined_var;
158 variable_map[var.name] = inlined_var.get();
162 void InlineContentInjector::visit(Return &ret)
164 TraversingVisitor::visit(ret);
168 /* Create a new variable to hold the return value of the inlined
170 r_result_name = create_unused_name("return", true);
171 RefPtr<VariableDeclaration> var = new VariableDeclaration;
172 var->source = ret.source;
173 var->line = ret.line;
174 var->type = source_func->return_type;
175 var->name = r_result_name;
176 var->init_expression = ret.expression->clone();
177 r_inlined_statement = var;
182 FunctionInliner::FunctionInliner():
187 bool FunctionInliner::apply(Stage &s)
190 inlineable = InlineableFunctionLocator().apply(s);
191 r_any_inlined = false;
192 s.content.visit(*this);
193 return r_any_inlined;
196 void FunctionInliner::visit(RefPtr<Expression> &ptr)
202 ptr = r_inline_result;
203 r_any_inlined = true;
208 void FunctionInliner::visit(Block &block)
210 SetForScope<Block *> set_block(current_block, &block);
211 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
212 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
219 void FunctionInliner::visit(FunctionCall &call)
221 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
224 FunctionDeclaration *def = call.declaration;
226 def = def->definition;
228 if(def && inlineable.count(def))
230 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
232 // This will later get removed by UnusedVariableRemover.
233 if(result_name.empty())
234 result_name = "msp_unused_from_inline";
236 RefPtr<VariableReference> ref = new VariableReference;
237 ref->name = result_name;
238 r_inline_result = ref;
240 /* Inlined variables need to be resolved before this function can be
242 inlineable.erase(current_function);
246 void FunctionInliner::visit(FunctionDeclaration &func)
248 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
249 TraversingVisitor::visit(func);
252 void FunctionInliner::visit(Iteration &iter)
254 /* Visit the initialization statement before entering the loop body so the
255 inlined statements get inserted outside. */
256 if(iter.init_statement)
257 iter.init_statement->visit(*this);
259 SetForScope<Block *> set_block(current_block, &iter.body);
260 /* Skip the condition and loop expression parts because they're not properly
261 inside the body block. Inlining anything into them will require a more
262 comprehensive transformation. */
263 iter.body.visit(*this);
267 ExpressionInliner::ExpressionInfo::ExpressionInfo():
276 ExpressionInliner::ExpressionInliner():
278 r_any_inlined(false),
281 iteration_init(false),
286 bool ExpressionInliner::apply(Stage &s)
288 s.content.visit(*this);
289 return r_any_inlined;
292 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
295 r_any_inlined = true;
298 void ExpressionInliner::visit(Block &block)
300 TraversingVisitor::visit(block);
302 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
304 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
305 for(; (j!=expressions.end() && j->first.declaration==i->second); )
307 if(j->second.expression && j->second.inline_point)
308 inline_expression(*j->second.expression, *j->second.inline_point);
310 expressions.erase(j++);
314 /* Expressions assigned in this block may depend on local variables of the
315 block. If this is a conditionally executed block, the assignments might not
316 always happen. Mark the expressions as not available to any outer blocks. */
317 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
318 if(i->second.assign_scope==&block)
319 i->second.available = false;
322 void ExpressionInliner::visit(RefPtr<Expression> &expr)
326 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
328 if(iteration_body && !r_ref_info->trivial)
330 /* Don't inline non-trivial expressions which were assigned outside
331 an iteration statement. The iteration may run multiple times, which
332 would cause the expression to also be evaluated multiple times. */
333 Block *i = r_ref_info->assign_scope;
334 for(; (i && i!=iteration_body); i=i->parent) ;
339 if(r_ref_info->trivial)
340 inline_expression(*r_ref_info->expression, expr);
342 /* Record the inline point for a non-trivial expression but don't
343 inline it yet. It might turn out it shouldn't be inlined after all. */
344 r_ref_info->inline_point = &expr;
350 void ExpressionInliner::visit(VariableReference &var)
354 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
355 if(i!=expressions.end())
357 /* If a non-trivial expression is referenced multiple times, don't
359 if(i->second.inline_point && !i->second.trivial)
360 i->second.expression = 0;
361 /* Mutating expressions are analogous to self-referencing assignments
362 and prevent inlining. */
364 i->second.expression = 0;
365 r_ref_info = &i->second;
370 void ExpressionInliner::visit(MemberAccess &memacc)
376 void ExpressionInliner::visit(Swizzle &swizzle)
382 void ExpressionInliner::visit(UnaryExpression &unary)
384 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
385 visit(unary.expression);
389 void ExpressionInliner::visit(BinaryExpression &binary)
393 SetFlag clear_target(mutating, false);
399 void ExpressionInliner::visit(Assignment &assign)
402 SetFlag set_target(mutating);
408 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
409 if(i!=expressions.end())
411 /* Self-referencing assignments can't be inlined without additional
412 work. Just clear any previous expression. */
413 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
414 i->second.assign_scope = current_block;
415 i->second.inline_point = 0;
416 i->second.available = true;
422 void ExpressionInliner::visit(TernaryExpression &ternary)
424 visit(ternary.condition);
425 visit(ternary.true_expr);
426 visit(ternary.false_expr);
430 void ExpressionInliner::visit(FunctionCall &call)
432 TraversingVisitor::visit(call);
436 void ExpressionInliner::visit(VariableDeclaration &var)
440 TraversingVisitor::visit(var);
442 bool constant = var.constant;
443 if(constant && var.layout)
445 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
446 constant = (i->name!="constant_id");
449 /* Only inline global variables if they're constant and have trivial
450 initializers. Non-constant variables could change in ways which are hard to
451 analyze and non-trivial expressions could be expensive to inline. */
452 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
454 ExpressionInfo &info = expressions[&var];
455 /* Assume variables declared in an iteration initialization statement
456 will have their values change throughout the iteration. */
457 info.expression = (iteration_init ? 0 : var.init_expression.get());
458 info.assign_scope = current_block;
459 info.trivial = r_trivial;
463 void ExpressionInliner::visit(Iteration &iter)
465 SetForScope<Block *> set_block(current_block, &iter.body);
466 if(iter.init_statement)
468 SetFlag set_init(iteration_init);
469 iter.init_statement->visit(*this);
472 SetForScope<Block *> set_body(iteration_body, &iter.body);
474 visit(iter.condition);
475 iter.body.visit(*this);
476 if(iter.loop_expression)
477 visit(iter.loop_expression);
481 void ConstantConditionEliminator::apply(Stage &stage)
483 stage.content.visit(*this);
484 NodeRemover().apply(stage, nodes_to_remove);
487 void ConstantConditionEliminator::visit(Block &block)
489 SetForScope<Block *> set_block(current_block, &block);
490 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
497 void ConstantConditionEliminator::visit(Conditional &cond)
499 if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
500 if(literal->value.check_type<bool>())
502 Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
503 current_block->body.splice(insert_point, block.body);
504 nodes_to_remove.insert(&cond);
508 TraversingVisitor::visit(cond);
511 void ConstantConditionEliminator::visit(Iteration &iter)
515 /* If the loop condition is always false on the first iteration, the
516 entire loop can be removed */
517 ExpressionEvaluator::ValueMap values;
518 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
519 values[var] = var->init_expression.get();
520 ExpressionEvaluator eval(values);
521 iter.condition->visit(eval);
522 if(eval.is_result_valid() && !eval.get_result())
524 nodes_to_remove.insert(&iter);
529 TraversingVisitor::visit(iter);
533 bool UnusedTypeRemover::apply(Stage &stage)
535 stage.content.visit(*this);
536 NodeRemover().apply(stage, unused_nodes);
537 return !unused_nodes.empty();
540 void UnusedTypeRemover::visit(Literal &literal)
542 unused_nodes.erase(literal.type);
545 void UnusedTypeRemover::visit(UnaryExpression &unary)
547 unused_nodes.erase(unary.type);
548 TraversingVisitor::visit(unary);
551 void UnusedTypeRemover::visit(BinaryExpression &binary)
553 unused_nodes.erase(binary.type);
554 TraversingVisitor::visit(binary);
557 void UnusedTypeRemover::visit(TernaryExpression &ternary)
559 unused_nodes.erase(ternary.type);
560 TraversingVisitor::visit(ternary);
563 void UnusedTypeRemover::visit(FunctionCall &call)
565 unused_nodes.erase(call.type);
566 TraversingVisitor::visit(call);
569 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
572 unused_nodes.erase(type.base_type);
573 unused_nodes.insert(&type);
576 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
579 unused_nodes.erase(type.base_type);
580 unused_nodes.insert(&type);
583 void UnusedTypeRemover::visit(StructDeclaration &strct)
585 unused_nodes.insert(&strct);
586 TraversingVisitor::visit(strct);
589 void UnusedTypeRemover::visit(VariableDeclaration &var)
591 unused_nodes.erase(var.type_declaration);
594 void UnusedTypeRemover::visit(InterfaceBlock &iface)
596 unused_nodes.erase(iface.type_declaration);
599 void UnusedTypeRemover::visit(FunctionDeclaration &func)
601 unused_nodes.erase(func.return_type_declaration);
602 TraversingVisitor::visit(func);
606 UnusedVariableRemover::UnusedVariableRemover():
610 assignment_target(false),
611 r_side_effects(false)
614 bool UnusedVariableRemover::apply(Stage &s)
617 s.content.visit(*this);
619 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
620 if(i->used_by.empty())
621 unused_nodes.insert(i->node);
623 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
624 if(i->second->instance_name.empty())
625 unused_nodes.insert(i->second);
627 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
631 /* The last visible assignments of output variables are used by the
632 next stage or the API. */
633 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
634 unused_nodes.erase((*j)->node);
637 if(!i->second.output && !i->second.referenced)
639 // Don't remove variables from inside interface blocks.
640 if(!i->second.interface_block)
641 unused_nodes.insert(i->first);
643 else if(i->second.interface_block)
644 // Interface blocks are kept if even one member is used.
645 unused_nodes.erase(i->second.interface_block);
648 NodeRemover().apply(s, unused_nodes);
650 return !unused_nodes.empty();
653 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
655 VariableInfo &var_info = variables[target.declaration];
656 var_info.referenced = true;
657 if(!assignment_target)
659 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
660 (*i)->used_by.push_back(&node);
664 void UnusedVariableRemover::visit(VariableReference &var)
666 referenced(var.declaration, var);
669 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
671 referenced(iface.declaration, iface);
674 void UnusedVariableRemover::visit(UnaryExpression &unary)
676 TraversingVisitor::visit(unary);
677 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
678 r_side_effects = true;
681 void UnusedVariableRemover::visit(BinaryExpression &binary)
683 if(binary.oper->token[0]=='[')
685 binary.left->visit(*this);
686 SetFlag set(assignment_target, false);
687 binary.right->visit(*this);
690 TraversingVisitor::visit(binary);
693 void UnusedVariableRemover::visit(Assignment &assign)
696 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
697 assign.left->visit(*this);
699 assign.right->visit(*this);
700 r_assignment = &assign;
701 r_side_effects = true;
704 void UnusedVariableRemover::visit(FunctionCall &call)
706 TraversingVisitor::visit(call);
707 /* Treat function calls as having side effects so expression statements
708 consisting of nothing but a function call won't be optimized away. */
709 r_side_effects = true;
711 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
713 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
715 referenced(i->first, call);
719 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
721 assignments.push_back(AssignmentInfo());
722 AssignmentInfo &assign_info = assignments.back();
723 assign_info.node = &node;
724 assign_info.target = target;
726 /* An assignment to the target hides any assignments to the same target or
728 VariableInfo &var_info = variables[target.declaration];
729 for(unsigned i=0; i<var_info.assignments.size(); ++i)
731 const Assignment::Target &t = var_info.assignments[i]->target;
733 bool subfield = (t.chain_len>=target.chain_len);
734 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
735 subfield = (t.chain[j]==target.chain[j]);
738 var_info.assignments.erase(var_info.assignments.begin()+i);
743 var_info.assignments.push_back(&assign_info);
746 void UnusedVariableRemover::visit(ExpressionStatement &expr)
749 r_side_effects = false;
750 TraversingVisitor::visit(expr);
751 if(r_assignment && r_assignment->target.declaration)
752 record_assignment(r_assignment->target, expr);
754 unused_nodes.insert(&expr);
757 void UnusedVariableRemover::visit(VariableDeclaration &var)
759 VariableInfo &var_info = variables[&var];
760 var_info.interface_block = interface_block;
762 /* Mark variables as output if they're used by the next stage or the
765 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
767 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
769 if(var.init_expression)
771 var_info.initialized = true;
772 record_assignment(&var, *var.init_expression);
774 TraversingVisitor::visit(var);
777 void UnusedVariableRemover::visit(InterfaceBlock &iface)
779 if(iface.instance_name.empty())
781 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
782 iface.struct_declaration->members.visit(*this);
786 VariableInfo &var_info = variables[&iface];
787 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
791 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
793 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
795 BlockVariableMap::iterator j = variables.find(i->first);
796 if(j!=variables.end())
798 /* The merged blocks started as copies of each other so any common
799 assignments must be in the beginning. */
801 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
802 if(i->second.assignments[k]!=j->second.assignments[k])
805 // Remaining assignments are unique to each block; merge them.
806 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
807 j->second.referenced |= i->second.referenced;
810 variables.insert(*i);
814 void UnusedVariableRemover::visit(FunctionDeclaration &func)
816 if(func.body.body.empty())
819 BlockVariableMap saved_vars = variables;
820 // Assignments from other functions should not be visible.
821 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
822 i->second.assignments.resize(i->second.initialized);
823 TraversingVisitor::visit(func);
824 swap(variables, saved_vars);
825 merge_variables(saved_vars);
827 /* Always treat function parameters as referenced. Removing unused
828 parameters is not currently supported. */
829 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
831 BlockVariableMap::iterator j = variables.find(i->get());
832 if(j!=variables.end())
833 j->second.referenced = true;
837 void UnusedVariableRemover::visit(Conditional &cond)
839 cond.condition->visit(*this);
840 BlockVariableMap saved_vars = variables;
841 cond.body.visit(*this);
842 swap(saved_vars, variables);
843 cond.else_body.visit(*this);
845 /* Visible assignments after the conditional is the union of those visible
846 at the end of the if and else blocks. If there was no else block, then it's
847 the union of the if block and the state before it. */
848 merge_variables(saved_vars);
851 void UnusedVariableRemover::visit(Iteration &iter)
853 BlockVariableMap saved_vars = variables;
854 TraversingVisitor::visit(iter);
856 /* Merge assignments from the iteration, without clearing previous state.
857 Further analysis is needed to determine which parts of the iteration body
858 are always executed, if any. */
859 merge_variables(saved_vars);
863 bool UnusedFunctionRemover::apply(Stage &stage)
865 stage.content.visit(*this);
866 NodeRemover().apply(stage, unused_nodes);
867 return !unused_nodes.empty();
870 void UnusedFunctionRemover::visit(FunctionCall &call)
872 TraversingVisitor::visit(call);
874 unused_nodes.erase(call.declaration);
875 if(call.declaration && call.declaration->definition!=call.declaration)
876 used_definitions.insert(call.declaration->definition);
879 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
881 TraversingVisitor::visit(func);
883 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
884 unused_nodes.insert(&func);