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::visit_and_record(RefPtr<Expression> &ptr)
296 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
298 if(iteration_body && !r_ref_info->trivial)
300 /* Don't inline non-trivial expressions which were assigned outside
301 an iteration statement. The iteration may run multiple times, which
302 would cause the expression to also be evaluated multiple times. */
303 Block *i = r_ref_info->assign_scope;
304 for(; (i && i!=iteration_body); i=i->parent) ;
309 if(r_ref_info->trivial)
310 inline_expression(*r_ref_info->expression, ptr);
312 /* Record the inline point for a non-trivial expression but don't
313 inline it yet. It might turn out it shouldn't be inlined after all. */
314 r_ref_info->inline_point = &ptr;
319 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
322 r_any_inlined = true;
325 void ExpressionInliner::visit(Block &block)
327 TraversingVisitor::visit(block);
329 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
331 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
332 for(; (j!=expressions.end() && j->first.declaration==i->second); )
334 if(j->second.expression && j->second.inline_point)
335 inline_expression(*j->second.expression, *j->second.inline_point);
337 expressions.erase(j++);
341 /* Expressions assigned in this block may depend on local variables of the
342 block. If this is a conditionally executed block, the assignments might not
343 always happen. Mark the expressions as not available to any outer blocks. */
344 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
345 if(i->second.assign_scope==&block)
346 i->second.available = false;
349 void ExpressionInliner::visit(RefPtr<Expression> &expr)
351 visit_and_record(expr);
354 void ExpressionInliner::visit(VariableReference &var)
358 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
359 if(i!=expressions.end())
361 /* If a non-trivial expression is referenced multiple times, don't
363 if(i->second.inline_point && !i->second.trivial)
364 i->second.expression = 0;
365 /* Mutating expressions are analogous to self-referencing assignments
366 and prevent inlining. */
368 i->second.expression = 0;
369 r_ref_info = &i->second;
374 void ExpressionInliner::visit(MemberAccess &memacc)
376 visit_and_record(memacc.left);
377 r_oper = memacc.oper;
381 void ExpressionInliner::visit(Swizzle &swizzle)
383 visit_and_record(swizzle.left);
384 r_oper = swizzle.oper;
388 void ExpressionInliner::visit(UnaryExpression &unary)
390 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
391 visit_and_record(unary.expression);
396 void ExpressionInliner::visit(BinaryExpression &binary)
398 visit_and_record(binary.left);
400 SetFlag clear_target(mutating, false);
401 visit_and_record(binary.right);
403 r_oper = binary.oper;
407 void ExpressionInliner::visit(Assignment &assign)
410 SetFlag set_target(mutating);
411 visit_and_record(assign.left);
414 visit_and_record(assign.right);
416 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
417 if(i!=expressions.end())
419 /* Self-referencing assignments can't be inlined without additional
420 work. Just clear any previous expression. */
421 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
422 i->second.assign_scope = current_block;
423 i->second.inline_point = 0;
424 i->second.available = true;
427 r_oper = assign.oper;
431 void ExpressionInliner::visit(TernaryExpression &ternary)
433 visit_and_record(ternary.condition);
434 visit_and_record(ternary.true_expr);
435 visit_and_record(ternary.false_expr);
436 r_oper = ternary.oper;
440 void ExpressionInliner::visit(FunctionCall &call)
442 TraversingVisitor::visit(call);
447 void ExpressionInliner::visit(VariableDeclaration &var)
451 TraversingVisitor::visit(var);
453 bool constant = var.constant;
454 if(constant && var.layout)
456 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
457 constant = (i->name!="constant_id");
460 /* Only inline global variables if they're constant and have trivial
461 initializers. Non-constant variables could change in ways which are hard to
462 analyze and non-trivial expressions could be expensive to inline. */
463 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
465 ExpressionInfo &info = expressions[&var];
466 /* Assume variables declared in an iteration initialization statement
467 will have their values change throughout the iteration. */
468 info.expression = (iteration_init ? 0 : var.init_expression.get());
469 info.assign_scope = current_block;
470 info.trivial = r_trivial;
474 void ExpressionInliner::visit(Iteration &iter)
476 SetForScope<Block *> set_block(current_block, &iter.body);
477 if(iter.init_statement)
479 SetFlag set_init(iteration_init);
480 iter.init_statement->visit(*this);
483 SetForScope<Block *> set_body(iteration_body, &iter.body);
485 visit(iter.condition);
486 iter.body.visit(*this);
487 if(iter.loop_expression)
488 visit(iter.loop_expression);
492 void ConstantConditionEliminator::apply(Stage &stage)
494 stage.content.visit(*this);
495 NodeRemover().apply(stage, nodes_to_remove);
498 void ConstantConditionEliminator::visit(Block &block)
500 SetForScope<Block *> set_block(current_block, &block);
501 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
508 void ConstantConditionEliminator::visit(Conditional &cond)
510 if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
511 if(literal->value.check_type<bool>())
513 Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
514 current_block->body.splice(insert_point, block.body);
515 nodes_to_remove.insert(&cond);
519 TraversingVisitor::visit(cond);
522 void ConstantConditionEliminator::visit(Iteration &iter)
526 /* If the loop condition is always false on the first iteration, the
527 entire loop can be removed */
528 ExpressionEvaluator::ValueMap values;
529 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
530 values[var] = var->init_expression.get();
531 ExpressionEvaluator eval(values);
532 iter.condition->visit(eval);
533 if(eval.is_result_valid() && !eval.get_result())
535 nodes_to_remove.insert(&iter);
540 TraversingVisitor::visit(iter);
544 bool UnusedTypeRemover::apply(Stage &stage)
546 stage.content.visit(*this);
547 NodeRemover().apply(stage, unused_nodes);
548 return !unused_nodes.empty();
551 void UnusedTypeRemover::visit(Literal &literal)
553 unused_nodes.erase(literal.type);
556 void UnusedTypeRemover::visit(UnaryExpression &unary)
558 unused_nodes.erase(unary.type);
559 TraversingVisitor::visit(unary);
562 void UnusedTypeRemover::visit(BinaryExpression &binary)
564 unused_nodes.erase(binary.type);
565 TraversingVisitor::visit(binary);
568 void UnusedTypeRemover::visit(TernaryExpression &ternary)
570 unused_nodes.erase(ternary.type);
571 TraversingVisitor::visit(ternary);
574 void UnusedTypeRemover::visit(FunctionCall &call)
576 unused_nodes.erase(call.type);
577 TraversingVisitor::visit(call);
580 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
583 unused_nodes.erase(type.base_type);
584 unused_nodes.insert(&type);
587 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
590 unused_nodes.erase(type.base_type);
591 unused_nodes.insert(&type);
594 void UnusedTypeRemover::visit(StructDeclaration &strct)
596 unused_nodes.insert(&strct);
597 TraversingVisitor::visit(strct);
600 void UnusedTypeRemover::visit(VariableDeclaration &var)
602 unused_nodes.erase(var.type_declaration);
605 void UnusedTypeRemover::visit(InterfaceBlock &iface)
607 unused_nodes.erase(iface.type_declaration);
610 void UnusedTypeRemover::visit(FunctionDeclaration &func)
612 unused_nodes.erase(func.return_type_declaration);
613 TraversingVisitor::visit(func);
617 UnusedVariableRemover::UnusedVariableRemover():
621 assignment_target(false),
622 r_side_effects(false)
625 bool UnusedVariableRemover::apply(Stage &s)
628 s.content.visit(*this);
630 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
631 if(i->used_by.empty())
632 unused_nodes.insert(i->node);
634 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
635 if(i->second->instance_name.empty())
636 unused_nodes.insert(i->second);
638 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
642 /* The last visible assignments of output variables are used by the
643 next stage or the API. */
644 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
645 unused_nodes.erase((*j)->node);
648 if(!i->second.output && !i->second.referenced)
650 // Don't remove variables from inside interface blocks.
651 if(!i->second.interface_block)
652 unused_nodes.insert(i->first);
654 else if(i->second.interface_block)
655 // Interface blocks are kept if even one member is used.
656 unused_nodes.erase(i->second.interface_block);
659 NodeRemover().apply(s, unused_nodes);
661 return !unused_nodes.empty();
664 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
666 VariableInfo &var_info = variables[target.declaration];
667 var_info.referenced = true;
668 if(!assignment_target)
670 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
671 (*i)->used_by.push_back(&node);
675 void UnusedVariableRemover::visit(VariableReference &var)
677 referenced(var.declaration, var);
680 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
682 referenced(iface.declaration, iface);
685 void UnusedVariableRemover::visit(UnaryExpression &unary)
687 TraversingVisitor::visit(unary);
688 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
689 r_side_effects = true;
692 void UnusedVariableRemover::visit(BinaryExpression &binary)
694 if(binary.oper->token[0]=='[')
696 binary.left->visit(*this);
697 SetFlag set(assignment_target, false);
698 binary.right->visit(*this);
701 TraversingVisitor::visit(binary);
704 void UnusedVariableRemover::visit(Assignment &assign)
707 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
708 assign.left->visit(*this);
710 assign.right->visit(*this);
711 r_assignment = &assign;
712 r_side_effects = true;
715 void UnusedVariableRemover::visit(FunctionCall &call)
717 TraversingVisitor::visit(call);
718 /* Treat function calls as having side effects so expression statements
719 consisting of nothing but a function call won't be optimized away. */
720 r_side_effects = true;
722 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
724 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
726 referenced(i->first, call);
730 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
732 assignments.push_back(AssignmentInfo());
733 AssignmentInfo &assign_info = assignments.back();
734 assign_info.node = &node;
735 assign_info.target = target;
737 /* An assignment to the target hides any assignments to the same target or
739 VariableInfo &var_info = variables[target.declaration];
740 for(unsigned i=0; i<var_info.assignments.size(); ++i)
742 const Assignment::Target &t = var_info.assignments[i]->target;
744 bool subfield = (t.chain_len>=target.chain_len);
745 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
746 subfield = (t.chain[j]==target.chain[j]);
749 var_info.assignments.erase(var_info.assignments.begin()+i);
754 var_info.assignments.push_back(&assign_info);
757 void UnusedVariableRemover::visit(ExpressionStatement &expr)
760 r_side_effects = false;
761 TraversingVisitor::visit(expr);
762 if(r_assignment && r_assignment->target.declaration)
763 record_assignment(r_assignment->target, expr);
765 unused_nodes.insert(&expr);
768 void UnusedVariableRemover::visit(VariableDeclaration &var)
770 VariableInfo &var_info = variables[&var];
771 var_info.interface_block = interface_block;
773 /* Mark variables as output if they're used by the next stage or the
776 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
778 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
780 if(var.init_expression)
782 var_info.initialized = true;
783 record_assignment(&var, *var.init_expression);
785 TraversingVisitor::visit(var);
788 void UnusedVariableRemover::visit(InterfaceBlock &iface)
790 if(iface.instance_name.empty())
792 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
793 iface.struct_declaration->members.visit(*this);
797 VariableInfo &var_info = variables[&iface];
798 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
802 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
804 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
806 BlockVariableMap::iterator j = variables.find(i->first);
807 if(j!=variables.end())
809 /* The merged blocks started as copies of each other so any common
810 assignments must be in the beginning. */
812 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
813 if(i->second.assignments[k]!=j->second.assignments[k])
816 // Remaining assignments are unique to each block; merge them.
817 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
818 j->second.referenced |= i->second.referenced;
821 variables.insert(*i);
825 void UnusedVariableRemover::visit(FunctionDeclaration &func)
827 if(func.body.body.empty())
830 BlockVariableMap saved_vars = variables;
831 // Assignments from other functions should not be visible.
832 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
833 i->second.assignments.resize(i->second.initialized);
834 TraversingVisitor::visit(func);
835 swap(variables, saved_vars);
836 merge_variables(saved_vars);
838 /* Always treat function parameters as referenced. Removing unused
839 parameters is not currently supported. */
840 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
842 BlockVariableMap::iterator j = variables.find(i->get());
843 if(j!=variables.end())
844 j->second.referenced = true;
848 void UnusedVariableRemover::visit(Conditional &cond)
850 cond.condition->visit(*this);
851 BlockVariableMap saved_vars = variables;
852 cond.body.visit(*this);
853 swap(saved_vars, variables);
854 cond.else_body.visit(*this);
856 /* Visible assignments after the conditional is the union of those visible
857 at the end of the if and else blocks. If there was no else block, then it's
858 the union of the if block and the state before it. */
859 merge_variables(saved_vars);
862 void UnusedVariableRemover::visit(Iteration &iter)
864 BlockVariableMap saved_vars = variables;
865 TraversingVisitor::visit(iter);
867 /* Merge assignments from the iteration, without clearing previous state.
868 Further analysis is needed to determine which parts of the iteration body
869 are always executed, if any. */
870 merge_variables(saved_vars);
874 bool UnusedFunctionRemover::apply(Stage &stage)
876 stage.content.visit(*this);
877 NodeRemover().apply(stage, unused_nodes);
878 return !unused_nodes.empty();
881 void UnusedFunctionRemover::visit(FunctionCall &call)
883 TraversingVisitor::visit(call);
885 unused_nodes.erase(call.declaration);
886 if(call.declaration && call.declaration->definition!=call.declaration)
887 used_definitions.insert(call.declaration->definition);
890 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
892 TraversingVisitor::visit(func);
894 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
895 unused_nodes.insert(&func);