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 void InlineContentInjector::visit(VariableReference &var)
98 map<string, VariableDeclaration *>::const_iterator i = variable_map.find(var.name);
99 if(i!=variable_map.end())
100 var.name = i->second->name;
102 else if(var.declaration)
104 SetFlag set_deps(deps_only);
105 dependencies.insert(var.declaration);
106 var.declaration->visit(*this);
110 void InlineContentInjector::visit(InterfaceBlockReference &iface)
112 if(!remap_names && iface.declaration)
114 SetFlag set_deps(deps_only);
115 dependencies.insert(iface.declaration);
116 iface.declaration->visit(*this);
120 void InlineContentInjector::visit(FunctionCall &call)
122 if(!remap_names && call.declaration)
123 dependencies.insert(call.declaration);
124 TraversingVisitor::visit(call);
127 void InlineContentInjector::visit(VariableDeclaration &var)
129 TraversingVisitor::visit(var);
131 if(var.type_declaration)
133 SetFlag set_deps(deps_only);
134 dependencies.insert(var.type_declaration);
135 var.type_declaration->visit(*this);
138 if(!remap_names && !deps_only)
140 RefPtr<VariableDeclaration> inlined_var = var.clone();
141 inlined_var->name = get_unused_variable_name(*target_block, var.name, source_func->name);
142 r_inlined_statement = inlined_var;
144 variable_map[var.name] = inlined_var.get();
148 void InlineContentInjector::visit(Return &ret)
150 TraversingVisitor::visit(ret);
154 /* Create a new variable to hold the return value of the inlined
156 r_result_name = get_unused_variable_name(*target_block, "_return", source_func->name);
157 RefPtr<VariableDeclaration> var = new VariableDeclaration;
158 var->source = ret.source;
159 var->line = ret.line;
160 var->type = source_func->return_type;
161 var->name = r_result_name;
162 var->init_expression = ret.expression->clone();
163 r_inlined_statement = var;
168 FunctionInliner::FunctionInliner():
173 bool FunctionInliner::apply(Stage &s)
176 inlineable = InlineableFunctionLocator().apply(s);
177 r_any_inlined = false;
178 s.content.visit(*this);
179 return r_any_inlined;
182 void FunctionInliner::visit(RefPtr<Expression> &ptr)
188 ptr = r_inline_result;
189 r_any_inlined = true;
194 void FunctionInliner::visit(Block &block)
196 SetForScope<Block *> set_block(current_block, &block);
197 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
198 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
205 void FunctionInliner::visit(FunctionCall &call)
207 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
210 FunctionDeclaration *def = call.declaration;
212 def = def->definition;
214 if(def && inlineable.count(def))
216 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
218 // This will later get removed by UnusedVariableRemover.
219 if(result_name.empty())
220 result_name = "msp_unused_from_inline";
222 RefPtr<VariableReference> ref = new VariableReference;
223 ref->name = result_name;
224 r_inline_result = ref;
226 /* Inlined variables need to be resolved before this function can be
228 inlineable.erase(current_function);
232 void FunctionInliner::visit(FunctionDeclaration &func)
234 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
235 TraversingVisitor::visit(func);
238 void FunctionInliner::visit(Iteration &iter)
240 /* Visit the initialization statement before entering the loop body so the
241 inlined statements get inserted outside. */
242 if(iter.init_statement)
243 iter.init_statement->visit(*this);
245 SetForScope<Block *> set_block(current_block, &iter.body);
246 /* Skip the condition and loop expression parts because they're not properly
247 inside the body block. Inlining anything into them will require a more
248 comprehensive transformation. */
249 iter.body.visit(*this);
253 ExpressionInliner::ExpressionInfo::ExpressionInfo():
262 ExpressionInliner::ExpressionInliner():
264 r_any_inlined(false),
267 iteration_init(false),
272 bool ExpressionInliner::apply(Stage &s)
274 s.content.visit(*this);
275 return r_any_inlined;
278 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
281 r_any_inlined = true;
284 void ExpressionInliner::visit(Block &block)
286 TraversingVisitor::visit(block);
288 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
290 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
291 for(; (j!=expressions.end() && j->first.declaration==i->second); )
293 if(j->second.expression && j->second.inline_point)
294 inline_expression(*j->second.expression, *j->second.inline_point);
296 expressions.erase(j++);
300 /* Expressions assigned in this block may depend on local variables of the
301 block. If this is a conditionally executed block, the assignments might not
302 always happen. Mark the expressions as not available to any outer blocks. */
303 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
304 if(i->second.assign_scope==&block)
305 i->second.available = false;
308 void ExpressionInliner::visit(RefPtr<Expression> &expr)
312 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
314 if(iteration_body && !r_ref_info->trivial)
316 /* Don't inline non-trivial expressions which were assigned outside
317 an iteration statement. The iteration may run multiple times, which
318 would cause the expression to also be evaluated multiple times. */
319 Block *i = r_ref_info->assign_scope;
320 for(; (i && i!=iteration_body); i=i->parent) ;
325 if(r_ref_info->trivial)
326 inline_expression(*r_ref_info->expression, expr);
328 /* Record the inline point for a non-trivial expression but don't
329 inline it yet. It might turn out it shouldn't be inlined after all. */
330 r_ref_info->inline_point = &expr;
336 void ExpressionInliner::visit(VariableReference &var)
340 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
341 if(i!=expressions.end())
343 /* If a non-trivial expression is referenced multiple times, don't
345 if(i->second.inline_point && !i->second.trivial)
346 i->second.expression = 0;
347 /* Mutating expressions are analogous to self-referencing assignments
348 and prevent inlining. */
350 i->second.expression = 0;
351 r_ref_info = &i->second;
356 void ExpressionInliner::visit(MemberAccess &memacc)
362 void ExpressionInliner::visit(Swizzle &swizzle)
368 void ExpressionInliner::visit(UnaryExpression &unary)
370 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
371 visit(unary.expression);
375 void ExpressionInliner::visit(BinaryExpression &binary)
379 SetFlag clear_target(mutating, false);
385 void ExpressionInliner::visit(Assignment &assign)
388 SetFlag set_target(mutating);
394 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
395 if(i!=expressions.end())
397 /* Self-referencing assignments can't be inlined without additional
398 work. Just clear any previous expression. */
399 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
400 i->second.assign_scope = current_block;
401 i->second.inline_point = 0;
402 i->second.available = true;
408 void ExpressionInliner::visit(TernaryExpression &ternary)
410 visit(ternary.condition);
411 visit(ternary.true_expr);
412 visit(ternary.false_expr);
416 void ExpressionInliner::visit(FunctionCall &call)
418 TraversingVisitor::visit(call);
422 void ExpressionInliner::visit(VariableDeclaration &var)
426 TraversingVisitor::visit(var);
428 bool constant = var.constant;
429 if(constant && var.layout)
431 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
432 constant = (i->name!="constant_id");
435 /* Only inline global variables if they're constant and have trivial
436 initializers. Non-constant variables could change in ways which are hard to
437 analyze and non-trivial expressions could be expensive to inline. */
438 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
440 ExpressionInfo &info = expressions[&var];
441 /* Assume variables declared in an iteration initialization statement
442 will have their values change throughout the iteration. */
443 info.expression = (iteration_init ? 0 : var.init_expression.get());
444 info.assign_scope = current_block;
445 info.trivial = r_trivial;
449 void ExpressionInliner::visit(Iteration &iter)
451 SetForScope<Block *> set_block(current_block, &iter.body);
452 if(iter.init_statement)
454 SetFlag set_init(iteration_init);
455 iter.init_statement->visit(*this);
458 SetForScope<Block *> set_body(iteration_body, &iter.body);
460 visit(iter.condition);
461 iter.body.visit(*this);
462 if(iter.loop_expression)
463 visit(iter.loop_expression);
467 void ConstantConditionEliminator::apply(Stage &stage)
469 stage.content.visit(*this);
470 NodeRemover().apply(stage, nodes_to_remove);
473 void ConstantConditionEliminator::visit(Block &block)
475 SetForScope<Block *> set_block(current_block, &block);
476 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
483 void ConstantConditionEliminator::visit(Conditional &cond)
485 if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
486 if(literal->value.check_type<bool>())
488 Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
489 current_block->body.splice(insert_point, block.body);
490 nodes_to_remove.insert(&cond);
494 TraversingVisitor::visit(cond);
497 void ConstantConditionEliminator::visit(Iteration &iter)
501 /* If the loop condition is always false on the first iteration, the
502 entire loop can be removed */
503 ExpressionEvaluator::ValueMap values;
504 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
505 values[var] = var->init_expression.get();
506 ExpressionEvaluator eval(values);
507 iter.condition->visit(eval);
508 if(eval.is_result_valid() && !eval.get_result())
510 nodes_to_remove.insert(&iter);
515 TraversingVisitor::visit(iter);
519 bool UnusedTypeRemover::apply(Stage &stage)
521 stage.content.visit(*this);
522 NodeRemover().apply(stage, unused_nodes);
523 return !unused_nodes.empty();
526 void UnusedTypeRemover::visit(Literal &literal)
528 unused_nodes.erase(literal.type);
531 void UnusedTypeRemover::visit(UnaryExpression &unary)
533 unused_nodes.erase(unary.type);
534 TraversingVisitor::visit(unary);
537 void UnusedTypeRemover::visit(BinaryExpression &binary)
539 unused_nodes.erase(binary.type);
540 TraversingVisitor::visit(binary);
543 void UnusedTypeRemover::visit(TernaryExpression &ternary)
545 unused_nodes.erase(ternary.type);
546 TraversingVisitor::visit(ternary);
549 void UnusedTypeRemover::visit(FunctionCall &call)
551 unused_nodes.erase(call.type);
552 TraversingVisitor::visit(call);
555 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
558 unused_nodes.erase(type.base_type);
559 unused_nodes.insert(&type);
562 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
565 unused_nodes.erase(type.base_type);
566 unused_nodes.insert(&type);
569 void UnusedTypeRemover::visit(StructDeclaration &strct)
571 unused_nodes.insert(&strct);
572 TraversingVisitor::visit(strct);
575 void UnusedTypeRemover::visit(VariableDeclaration &var)
577 unused_nodes.erase(var.type_declaration);
580 void UnusedTypeRemover::visit(InterfaceBlock &iface)
582 unused_nodes.erase(iface.type_declaration);
585 void UnusedTypeRemover::visit(FunctionDeclaration &func)
587 unused_nodes.erase(func.return_type_declaration);
588 TraversingVisitor::visit(func);
592 UnusedVariableRemover::UnusedVariableRemover():
596 assignment_target(false),
597 r_side_effects(false)
600 bool UnusedVariableRemover::apply(Stage &s)
603 s.content.visit(*this);
605 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
606 if(i->used_by.empty())
607 unused_nodes.insert(i->node);
609 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
610 if(i->second->instance_name.empty())
611 unused_nodes.insert(i->second);
613 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
617 /* The last visible assignments of output variables are used by the
618 next stage or the API. */
619 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
620 unused_nodes.erase((*j)->node);
623 if(!i->second.output && !i->second.referenced)
625 // Don't remove variables from inside interface blocks.
626 if(!i->second.interface_block)
627 unused_nodes.insert(i->first);
629 else if(i->second.interface_block)
630 // Interface blocks are kept if even one member is used.
631 unused_nodes.erase(i->second.interface_block);
634 NodeRemover().apply(s, unused_nodes);
636 return !unused_nodes.empty();
639 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
641 VariableInfo &var_info = variables[target.declaration];
642 var_info.referenced = true;
643 if(!assignment_target)
645 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
646 (*i)->used_by.push_back(&node);
650 void UnusedVariableRemover::visit(VariableReference &var)
652 referenced(var.declaration, var);
655 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
657 referenced(iface.declaration, iface);
660 void UnusedVariableRemover::visit(UnaryExpression &unary)
662 TraversingVisitor::visit(unary);
663 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
664 r_side_effects = true;
667 void UnusedVariableRemover::visit(BinaryExpression &binary)
669 if(binary.oper->token[0]=='[')
671 binary.left->visit(*this);
672 SetFlag set(assignment_target, false);
673 binary.right->visit(*this);
676 TraversingVisitor::visit(binary);
679 void UnusedVariableRemover::visit(Assignment &assign)
682 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
683 assign.left->visit(*this);
685 assign.right->visit(*this);
686 r_assignment = &assign;
687 r_side_effects = true;
690 void UnusedVariableRemover::visit(FunctionCall &call)
692 TraversingVisitor::visit(call);
693 /* Treat function calls as having side effects so expression statements
694 consisting of nothing but a function call won't be optimized away. */
695 r_side_effects = true;
697 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
699 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
701 referenced(i->first, call);
705 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
707 assignments.push_back(AssignmentInfo());
708 AssignmentInfo &assign_info = assignments.back();
709 assign_info.node = &node;
710 assign_info.target = target;
712 /* An assignment to the target hides any assignments to the same target or
714 VariableInfo &var_info = variables[target.declaration];
715 for(unsigned i=0; i<var_info.assignments.size(); ++i)
717 const Assignment::Target &t = var_info.assignments[i]->target;
719 bool subfield = (t.chain_len>=target.chain_len);
720 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
721 subfield = (t.chain[j]==target.chain[j]);
724 var_info.assignments.erase(var_info.assignments.begin()+i);
729 var_info.assignments.push_back(&assign_info);
732 void UnusedVariableRemover::visit(ExpressionStatement &expr)
735 r_side_effects = false;
736 TraversingVisitor::visit(expr);
737 if(r_assignment && r_assignment->target.declaration)
738 record_assignment(r_assignment->target, expr);
740 unused_nodes.insert(&expr);
743 void UnusedVariableRemover::visit(VariableDeclaration &var)
745 VariableInfo &var_info = variables[&var];
746 var_info.interface_block = interface_block;
748 /* Mark variables as output if they're used by the next stage or the
751 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
753 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
755 if(var.init_expression)
757 var_info.initialized = true;
758 record_assignment(&var, *var.init_expression);
760 TraversingVisitor::visit(var);
763 void UnusedVariableRemover::visit(InterfaceBlock &iface)
765 if(iface.instance_name.empty())
767 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
768 iface.struct_declaration->members.visit(*this);
772 VariableInfo &var_info = variables[&iface];
773 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
777 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
779 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
781 BlockVariableMap::iterator j = variables.find(i->first);
782 if(j!=variables.end())
784 /* The merged blocks started as copies of each other so any common
785 assignments must be in the beginning. */
787 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
788 if(i->second.assignments[k]!=j->second.assignments[k])
791 // Remaining assignments are unique to each block; merge them.
792 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
793 j->second.referenced |= i->second.referenced;
796 variables.insert(*i);
800 void UnusedVariableRemover::visit(FunctionDeclaration &func)
802 if(func.body.body.empty())
805 BlockVariableMap saved_vars = variables;
806 // Assignments from other functions should not be visible.
807 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
808 i->second.assignments.resize(i->second.initialized);
809 TraversingVisitor::visit(func);
810 swap(variables, saved_vars);
811 merge_variables(saved_vars);
813 /* Always treat function parameters as referenced. Removing unused
814 parameters is not currently supported. */
815 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
817 BlockVariableMap::iterator j = variables.find(i->get());
818 if(j!=variables.end())
819 j->second.referenced = true;
823 void UnusedVariableRemover::visit(Conditional &cond)
825 cond.condition->visit(*this);
826 BlockVariableMap saved_vars = variables;
827 cond.body.visit(*this);
828 swap(saved_vars, variables);
829 cond.else_body.visit(*this);
831 /* Visible assignments after the conditional is the union of those visible
832 at the end of the if and else blocks. If there was no else block, then it's
833 the union of the if block and the state before it. */
834 merge_variables(saved_vars);
837 void UnusedVariableRemover::visit(Iteration &iter)
839 BlockVariableMap saved_vars = variables;
840 TraversingVisitor::visit(iter);
842 /* Merge assignments from the iteration, without clearing previous state.
843 Further analysis is needed to determine which parts of the iteration body
844 are always executed, if any. */
845 merge_variables(saved_vars);
849 bool UnusedFunctionRemover::apply(Stage &stage)
851 stage.content.visit(*this);
852 NodeRemover().apply(stage, unused_nodes);
853 return !unused_nodes.empty();
856 void UnusedFunctionRemover::visit(FunctionCall &call)
858 TraversingVisitor::visit(call);
860 unused_nodes.erase(call.declaration);
861 if(call.declaration && call.declaration->definition!=call.declaration)
862 used_definitions.insert(call.declaration->definition);
865 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
867 TraversingVisitor::visit(func);
869 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
870 unused_nodes.insert(&func);