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():
273 inline_on_rhs(false),
279 ExpressionInliner::ExpressionInliner():
281 r_any_inlined(false),
284 iteration_init(false),
289 bool ExpressionInliner::apply(Stage &s)
291 s.content.visit(*this);
292 return r_any_inlined;
295 void ExpressionInliner::visit_and_record(RefPtr<Expression> &ptr, const Operator *outer_oper, bool on_rhs)
299 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
301 if(iteration_body && !r_ref_info->trivial)
303 /* Don't inline non-trivial expressions which were assigned outside
304 an iteration statement. The iteration may run multiple times, which
305 would cause the expression to also be evaluated multiple times. */
306 Block *i = r_ref_info->assign_scope;
307 for(; (i && i!=iteration_body); i=i->parent) ;
312 r_ref_info->outer_oper = outer_oper;
313 if(r_ref_info->trivial)
314 inline_expression(*r_ref_info->expression, ptr, outer_oper, r_ref_info->inner_oper, on_rhs);
317 /* Record the inline point for a non-trivial expression but don't
318 inline it yet. It might turn out it shouldn't be inlined after all. */
319 r_ref_info->inline_point = &ptr;
320 r_ref_info->inline_on_rhs = on_rhs;
326 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr, const Operator *outer_oper, const Operator *inner_oper, bool on_rhs)
328 unsigned outer_precedence = (outer_oper ? outer_oper->precedence : 20);
329 unsigned inner_precedence = (inner_oper ? inner_oper->precedence : 0);
331 bool needs_parentheses = (inner_precedence>=outer_precedence);
332 if(inner_oper && inner_oper==outer_oper)
333 // Omit parentheses if the operator's natural grouping works out.
334 needs_parentheses = (inner_oper->assoc!=Operator::ASSOCIATIVE && on_rhs!=(inner_oper->assoc==Operator::RIGHT_TO_LEFT));
336 if(needs_parentheses)
338 RefPtr<ParenthesizedExpression> parexpr = new ParenthesizedExpression;
339 parexpr->expression = expr.clone();
345 r_any_inlined = true;
348 void ExpressionInliner::visit(Block &block)
350 TraversingVisitor::visit(block);
352 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
354 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
355 for(; (j!=expressions.end() && j->first.declaration==i->second); )
357 if(j->second.expression && j->second.inline_point)
358 inline_expression(*j->second.expression, *j->second.inline_point, j->second.outer_oper, j->second.inner_oper, j->second.inline_on_rhs);
360 expressions.erase(j++);
364 /* Expressions assigned in this block may depend on local variables of the
365 block. If this is a conditionally executed block, the assignments might not
366 always happen. Mark the expressions as not available to any outer blocks. */
367 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
368 if(i->second.assign_scope==&block)
369 i->second.available = false;
372 void ExpressionInliner::visit(RefPtr<Expression> &expr)
374 visit_and_record(expr, 0, false);
377 void ExpressionInliner::visit(VariableReference &var)
381 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
382 if(i!=expressions.end())
384 /* If a non-trivial expression is referenced multiple times, don't
386 if(i->second.inline_point && !i->second.trivial)
387 i->second.expression = 0;
388 /* Mutating expressions are analogous to self-referencing assignments
389 and prevent inlining. */
391 i->second.expression = 0;
392 r_ref_info = &i->second;
397 void ExpressionInliner::visit(MemberAccess &memacc)
399 visit_and_record(memacc.left, memacc.oper, false);
400 r_oper = memacc.oper;
404 void ExpressionInliner::visit(Swizzle &swizzle)
406 visit_and_record(swizzle.left, swizzle.oper, false);
407 r_oper = swizzle.oper;
411 void ExpressionInliner::visit(UnaryExpression &unary)
413 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
414 visit_and_record(unary.expression, unary.oper, false);
419 void ExpressionInliner::visit(BinaryExpression &binary)
421 visit_and_record(binary.left, binary.oper, false);
423 SetFlag clear_target(mutating, false);
424 visit_and_record(binary.right, binary.oper, true);
426 r_oper = binary.oper;
430 void ExpressionInliner::visit(Assignment &assign)
433 SetFlag set_target(mutating);
434 visit_and_record(assign.left, assign.oper, false);
437 visit_and_record(assign.right, assign.oper, true);
439 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
440 if(i!=expressions.end())
442 /* Self-referencing assignments can't be inlined without additional
443 work. Just clear any previous expression. */
444 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
445 i->second.assign_scope = current_block;
446 i->second.inline_point = 0;
447 i->second.inner_oper = r_oper;
448 i->second.available = true;
451 r_oper = assign.oper;
455 void ExpressionInliner::visit(FunctionCall &call)
457 TraversingVisitor::visit(call);
462 void ExpressionInliner::visit(VariableDeclaration &var)
466 TraversingVisitor::visit(var);
468 bool constant = var.constant;
469 if(constant && var.layout)
471 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
472 constant = (i->name!="constant_id");
475 /* Only inline global variables if they're constant and have trivial
476 initializers. Non-constant variables could change in ways which are hard to
477 analyze and non-trivial expressions could be expensive to inline. */
478 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
480 ExpressionInfo &info = expressions[&var];
481 /* Assume variables declared in an iteration initialization statement
482 will have their values change throughout the iteration. */
483 info.expression = (iteration_init ? 0 : var.init_expression.get());
484 info.assign_scope = current_block;
485 info.inner_oper = r_oper;
486 info.trivial = r_trivial;
490 void ExpressionInliner::visit(Iteration &iter)
492 SetForScope<Block *> set_block(current_block, &iter.body);
493 if(iter.init_statement)
495 SetFlag set_init(iteration_init);
496 iter.init_statement->visit(*this);
499 SetForScope<Block *> set_body(iteration_body, &iter.body);
501 visit(iter.condition);
502 iter.body.visit(*this);
503 if(iter.loop_expression)
504 visit(iter.loop_expression);
508 void ConstantConditionEliminator::apply(Stage &stage)
510 stage.content.visit(*this);
511 NodeRemover().apply(stage, nodes_to_remove);
514 void ConstantConditionEliminator::visit(Block &block)
516 SetForScope<Block *> set_block(current_block, &block);
517 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
524 void ConstantConditionEliminator::visit(Conditional &cond)
526 if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
527 if(literal->value.check_type<bool>())
529 Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
530 current_block->body.splice(insert_point, block.body);
531 nodes_to_remove.insert(&cond);
535 TraversingVisitor::visit(cond);
538 void ConstantConditionEliminator::visit(Iteration &iter)
542 /* If the loop condition is always false on the first iteration, the
543 entire loop can be removed */
544 ExpressionEvaluator::ValueMap values;
545 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
546 values[var] = var->init_expression.get();
547 ExpressionEvaluator eval(values);
548 iter.condition->visit(eval);
549 if(eval.is_result_valid() && !eval.get_result())
551 nodes_to_remove.insert(&iter);
556 TraversingVisitor::visit(iter);
560 bool UnusedTypeRemover::apply(Stage &stage)
562 stage.content.visit(*this);
563 NodeRemover().apply(stage, unused_nodes);
564 return !unused_nodes.empty();
567 void UnusedTypeRemover::visit(Literal &literal)
569 unused_nodes.erase(literal.type);
572 void UnusedTypeRemover::visit(UnaryExpression &unary)
574 unused_nodes.erase(unary.type);
575 TraversingVisitor::visit(unary);
578 void UnusedTypeRemover::visit(BinaryExpression &binary)
580 unused_nodes.erase(binary.type);
581 TraversingVisitor::visit(binary);
584 void UnusedTypeRemover::visit(FunctionCall &call)
586 unused_nodes.erase(call.type);
587 TraversingVisitor::visit(call);
590 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
593 unused_nodes.erase(type.base_type);
594 unused_nodes.insert(&type);
597 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
600 unused_nodes.erase(type.base_type);
601 unused_nodes.insert(&type);
604 void UnusedTypeRemover::visit(StructDeclaration &strct)
606 unused_nodes.insert(&strct);
607 TraversingVisitor::visit(strct);
610 void UnusedTypeRemover::visit(VariableDeclaration &var)
612 unused_nodes.erase(var.type_declaration);
615 void UnusedTypeRemover::visit(InterfaceBlock &iface)
617 unused_nodes.erase(iface.type_declaration);
620 void UnusedTypeRemover::visit(FunctionDeclaration &func)
622 unused_nodes.erase(func.return_type_declaration);
623 TraversingVisitor::visit(func);
627 UnusedVariableRemover::UnusedVariableRemover():
631 assignment_target(false),
632 r_side_effects(false)
635 bool UnusedVariableRemover::apply(Stage &s)
638 s.content.visit(*this);
640 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
641 if(i->used_by.empty())
642 unused_nodes.insert(i->node);
644 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
645 if(i->second->instance_name.empty())
646 unused_nodes.insert(i->second);
648 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
652 /* The last visible assignments of output variables are used by the
653 next stage or the API. */
654 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
655 unused_nodes.erase((*j)->node);
658 if(!i->second.output && !i->second.referenced)
660 // Don't remove variables from inside interface blocks.
661 if(!i->second.interface_block)
662 unused_nodes.insert(i->first);
664 else if(i->second.interface_block)
665 // Interface blocks are kept if even one member is used.
666 unused_nodes.erase(i->second.interface_block);
669 NodeRemover().apply(s, unused_nodes);
671 return !unused_nodes.empty();
674 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
676 VariableInfo &var_info = variables[target.declaration];
677 var_info.referenced = true;
678 if(!assignment_target)
680 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
681 (*i)->used_by.push_back(&node);
685 void UnusedVariableRemover::visit(VariableReference &var)
687 referenced(var.declaration, var);
690 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
692 referenced(iface.declaration, iface);
695 void UnusedVariableRemover::visit(UnaryExpression &unary)
697 TraversingVisitor::visit(unary);
698 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
699 r_side_effects = true;
702 void UnusedVariableRemover::visit(BinaryExpression &binary)
704 if(binary.oper->token[0]=='[')
706 binary.left->visit(*this);
707 SetFlag set(assignment_target, false);
708 binary.right->visit(*this);
711 TraversingVisitor::visit(binary);
714 void UnusedVariableRemover::visit(Assignment &assign)
717 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
718 assign.left->visit(*this);
720 assign.right->visit(*this);
721 r_assignment = &assign;
722 r_side_effects = true;
725 void UnusedVariableRemover::visit(FunctionCall &call)
727 TraversingVisitor::visit(call);
728 /* Treat function calls as having side effects so expression statements
729 consisting of nothing but a function call won't be optimized away. */
730 r_side_effects = true;
732 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
734 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
736 referenced(i->first, call);
740 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
742 assignments.push_back(AssignmentInfo());
743 AssignmentInfo &assign_info = assignments.back();
744 assign_info.node = &node;
745 assign_info.target = target;
747 /* An assignment to the target hides any assignments to the same target or
749 VariableInfo &var_info = variables[target.declaration];
750 for(unsigned i=0; i<var_info.assignments.size(); ++i)
752 const Assignment::Target &t = var_info.assignments[i]->target;
754 bool subfield = (t.chain_len>=target.chain_len);
755 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
756 subfield = (t.chain[j]==target.chain[j]);
759 var_info.assignments.erase(var_info.assignments.begin()+i);
764 var_info.assignments.push_back(&assign_info);
767 void UnusedVariableRemover::visit(ExpressionStatement &expr)
770 r_side_effects = false;
771 TraversingVisitor::visit(expr);
772 if(r_assignment && r_assignment->target.declaration)
773 record_assignment(r_assignment->target, expr);
775 unused_nodes.insert(&expr);
778 void UnusedVariableRemover::visit(VariableDeclaration &var)
780 VariableInfo &var_info = variables[&var];
781 var_info.interface_block = interface_block;
783 /* Mark variables as output if they're used by the next stage or the
786 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
788 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
790 if(var.init_expression)
792 var_info.initialized = true;
793 record_assignment(&var, *var.init_expression);
795 TraversingVisitor::visit(var);
798 void UnusedVariableRemover::visit(InterfaceBlock &iface)
800 if(iface.instance_name.empty())
802 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
803 iface.struct_declaration->members.visit(*this);
807 VariableInfo &var_info = variables[&iface];
808 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
812 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
814 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
816 BlockVariableMap::iterator j = variables.find(i->first);
817 if(j!=variables.end())
819 /* The merged blocks started as copies of each other so any common
820 assignments must be in the beginning. */
822 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
823 if(i->second.assignments[k]!=j->second.assignments[k])
826 // Remaining assignments are unique to each block; merge them.
827 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
828 j->second.referenced |= i->second.referenced;
831 variables.insert(*i);
835 void UnusedVariableRemover::visit(FunctionDeclaration &func)
837 if(func.body.body.empty())
840 BlockVariableMap saved_vars = variables;
841 // Assignments from other functions should not be visible.
842 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
843 i->second.assignments.resize(i->second.initialized);
844 TraversingVisitor::visit(func);
845 swap(variables, saved_vars);
846 merge_variables(saved_vars);
848 /* Always treat function parameters as referenced. Removing unused
849 parameters is not currently supported. */
850 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
852 BlockVariableMap::iterator j = variables.find(i->get());
853 if(j!=variables.end())
854 j->second.referenced = true;
858 void UnusedVariableRemover::visit(Conditional &cond)
860 cond.condition->visit(*this);
861 BlockVariableMap saved_vars = variables;
862 cond.body.visit(*this);
863 swap(saved_vars, variables);
864 cond.else_body.visit(*this);
866 /* Visible assignments after the conditional is the union of those visible
867 at the end of the if and else blocks. If there was no else block, then it's
868 the union of the if block and the state before it. */
869 merge_variables(saved_vars);
872 void UnusedVariableRemover::visit(Iteration &iter)
874 BlockVariableMap saved_vars = variables;
875 TraversingVisitor::visit(iter);
877 /* Merge assignments from the iteration, without clearing previous state.
878 Further analysis is needed to determine which parts of the iteration body
879 are always executed, if any. */
880 merge_variables(saved_vars);
884 bool UnusedFunctionRemover::apply(Stage &stage)
886 stage.content.visit(*this);
887 NodeRemover().apply(stage, unused_nodes);
888 return !unused_nodes.empty();
891 void UnusedFunctionRemover::visit(FunctionCall &call)
893 TraversingVisitor::visit(call);
895 unused_nodes.erase(call.declaration);
896 if(call.declaration && call.declaration->definition!=call.declaration)
897 used_definitions.insert(call.declaration->definition);
900 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
902 TraversingVisitor::visit(func);
904 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
905 unused_nodes.insert(&func);