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 SetForScope<unsigned> set_remap(remap_names, 1);
94 SetForScope<string> set_prefix(remap_prefix, target_func.name);
96 target_func.visit(*this);
98 tgt_blk.body.insert(ins_pt, inlined.begin(), inlined.end());
100 NodeReorderer().apply(stage, target_func, dependencies);
102 return r_result_name;
105 void InlineContentInjector::visit(VariableReference &var)
109 map<string, VariableDeclaration *>::const_iterator i = variable_map.find(var.name);
110 if(i!=variable_map.end())
111 var.name = i->second->name;
113 else if(var.declaration)
115 SetFlag set_deps(deps_only);
116 if(!variable_map.count(var.name))
118 dependencies.insert(var.declaration);
119 referenced_names.insert(var.name);
121 var.declaration->visit(*this);
125 void InlineContentInjector::visit(InterfaceBlockReference &iface)
127 if(!remap_names && iface.declaration)
129 SetFlag set_deps(deps_only);
130 dependencies.insert(iface.declaration);
131 referenced_names.insert(iface.name);
132 iface.declaration->visit(*this);
136 void InlineContentInjector::visit(FunctionCall &call)
138 if(!remap_names && call.declaration)
140 dependencies.insert(call.declaration);
141 referenced_names.insert(call.name);
143 TraversingVisitor::visit(call);
146 void InlineContentInjector::visit(VariableDeclaration &var)
148 TraversingVisitor::visit(var);
152 if(remap_names==2 || referenced_names.count(var.name))
154 string mapped_name = get_unused_variable_name(*target_block, var.name, remap_prefix);
155 variable_map[var.name] = &var;
156 var.name = mapped_name;
159 else if(var.type_declaration)
161 SetFlag set_deps(deps_only);
162 dependencies.insert(var.type_declaration);
163 referenced_names.insert(var.type_declaration->name);
164 var.type_declaration->visit(*this);
168 void InlineContentInjector::visit(Return &ret)
170 TraversingVisitor::visit(ret);
172 if(!remap_names && ret.expression)
174 /* Create a new variable to hold the return value of the inlined
176 r_result_name = get_unused_variable_name(*target_block, "_return", source_func->name);
177 RefPtr<VariableDeclaration> var = new VariableDeclaration;
178 var->source = ret.source;
179 var->line = ret.line;
180 var->type = source_func->return_type;
181 var->name = r_result_name;
182 var->init_expression = ret.expression->clone();
183 r_inlined_statement = var;
188 FunctionInliner::FunctionInliner():
193 bool FunctionInliner::apply(Stage &s)
196 inlineable = InlineableFunctionLocator().apply(s);
197 r_any_inlined = false;
198 s.content.visit(*this);
199 return r_any_inlined;
202 void FunctionInliner::visit(RefPtr<Expression> &ptr)
208 ptr = r_inline_result;
209 r_any_inlined = true;
214 void FunctionInliner::visit(Block &block)
216 SetForScope<Block *> set_block(current_block, &block);
217 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
218 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
225 void FunctionInliner::visit(FunctionCall &call)
227 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
230 FunctionDeclaration *def = call.declaration;
232 def = def->definition;
234 if(def && inlineable.count(def))
236 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
238 // This will later get removed by UnusedVariableRemover.
239 if(result_name.empty())
240 result_name = "msp_unused_from_inline";
242 RefPtr<VariableReference> ref = new VariableReference;
243 ref->name = result_name;
244 r_inline_result = ref;
246 /* Inlined variables need to be resolved before this function can be
248 inlineable.erase(current_function);
252 void FunctionInliner::visit(FunctionDeclaration &func)
254 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
255 TraversingVisitor::visit(func);
258 void FunctionInliner::visit(Iteration &iter)
260 /* Visit the initialization statement before entering the loop body so the
261 inlined statements get inserted outside. */
262 if(iter.init_statement)
263 iter.init_statement->visit(*this);
265 SetForScope<Block *> set_block(current_block, &iter.body);
266 /* Skip the condition and loop expression parts because they're not properly
267 inside the body block. Inlining anything into them will require a more
268 comprehensive transformation. */
269 iter.body.visit(*this);
273 ExpressionInliner::ExpressionInfo::ExpressionInfo():
282 ExpressionInliner::ExpressionInliner():
284 r_any_inlined(false),
287 iteration_init(false),
292 bool ExpressionInliner::apply(Stage &s)
294 s.content.visit(*this);
295 return r_any_inlined;
298 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
301 r_any_inlined = true;
304 void ExpressionInliner::visit(Block &block)
306 TraversingVisitor::visit(block);
308 for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
310 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
311 for(; (j!=expressions.end() && j->first.declaration==i->second); )
313 if(j->second.expression && j->second.inline_point)
314 inline_expression(*j->second.expression, *j->second.inline_point);
316 expressions.erase(j++);
320 /* Expressions assigned in this block may depend on local variables of the
321 block. If this is a conditionally executed block, the assignments might not
322 always happen. Mark the expressions as not available to any outer blocks. */
323 for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
324 if(i->second.assign_scope==&block)
325 i->second.available = false;
328 void ExpressionInliner::visit(RefPtr<Expression> &expr)
332 if(r_ref_info && r_ref_info->expression && r_ref_info->available)
334 if(iteration_body && !r_ref_info->trivial)
336 /* Don't inline non-trivial expressions which were assigned outside
337 an iteration statement. The iteration may run multiple times, which
338 would cause the expression to also be evaluated multiple times. */
339 Block *i = r_ref_info->assign_scope;
340 for(; (i && i!=iteration_body); i=i->parent) ;
345 if(r_ref_info->trivial)
346 inline_expression(*r_ref_info->expression, expr);
348 /* Record the inline point for a non-trivial expression but don't
349 inline it yet. It might turn out it shouldn't be inlined after all. */
350 r_ref_info->inline_point = &expr;
356 void ExpressionInliner::visit(VariableReference &var)
360 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
361 if(i!=expressions.end())
363 /* If a non-trivial expression is referenced multiple times, don't
365 if(i->second.inline_point && !i->second.trivial)
366 i->second.expression = 0;
367 /* Mutating expressions are analogous to self-referencing assignments
368 and prevent inlining. */
370 i->second.expression = 0;
371 r_ref_info = &i->second;
376 void ExpressionInliner::visit(MemberAccess &memacc)
382 void ExpressionInliner::visit(Swizzle &swizzle)
388 void ExpressionInliner::visit(UnaryExpression &unary)
390 SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
391 visit(unary.expression);
395 void ExpressionInliner::visit(BinaryExpression &binary)
399 SetFlag clear_target(mutating, false);
405 void ExpressionInliner::visit(Assignment &assign)
408 SetFlag set_target(mutating);
414 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
415 if(i!=expressions.end())
417 /* Self-referencing assignments can't be inlined without additional
418 work. Just clear any previous expression. */
419 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
420 i->second.assign_scope = current_block;
421 i->second.inline_point = 0;
422 i->second.available = true;
428 void ExpressionInliner::visit(TernaryExpression &ternary)
430 visit(ternary.condition);
431 visit(ternary.true_expr);
432 visit(ternary.false_expr);
436 void ExpressionInliner::visit(FunctionCall &call)
438 TraversingVisitor::visit(call);
442 void ExpressionInliner::visit(VariableDeclaration &var)
446 TraversingVisitor::visit(var);
448 bool constant = var.constant;
449 if(constant && var.layout)
451 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
452 constant = (i->name!="constant_id");
455 /* Only inline global variables if they're constant and have trivial
456 initializers. Non-constant variables could change in ways which are hard to
457 analyze and non-trivial expressions could be expensive to inline. */
458 if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
460 ExpressionInfo &info = expressions[&var];
461 /* Assume variables declared in an iteration initialization statement
462 will have their values change throughout the iteration. */
463 info.expression = (iteration_init ? 0 : var.init_expression.get());
464 info.assign_scope = current_block;
465 info.trivial = r_trivial;
469 void ExpressionInliner::visit(Iteration &iter)
471 SetForScope<Block *> set_block(current_block, &iter.body);
472 if(iter.init_statement)
474 SetFlag set_init(iteration_init);
475 iter.init_statement->visit(*this);
478 SetForScope<Block *> set_body(iteration_body, &iter.body);
480 visit(iter.condition);
481 iter.body.visit(*this);
482 if(iter.loop_expression)
483 visit(iter.loop_expression);
487 void ConstantConditionEliminator::apply(Stage &stage)
489 stage.content.visit(*this);
490 NodeRemover().apply(stage, nodes_to_remove);
493 void ConstantConditionEliminator::visit(Block &block)
495 SetForScope<Block *> set_block(current_block, &block);
496 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
503 void ConstantConditionEliminator::visit(Conditional &cond)
505 if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
506 if(literal->value.check_type<bool>())
508 Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
509 current_block->body.splice(insert_point, block.body);
510 nodes_to_remove.insert(&cond);
514 TraversingVisitor::visit(cond);
517 void ConstantConditionEliminator::visit(Iteration &iter)
521 /* If the loop condition is always false on the first iteration, the
522 entire loop can be removed */
523 ExpressionEvaluator::ValueMap values;
524 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
525 values[var] = var->init_expression.get();
526 ExpressionEvaluator eval(values);
527 iter.condition->visit(eval);
528 if(eval.is_result_valid() && !eval.get_result())
530 nodes_to_remove.insert(&iter);
535 TraversingVisitor::visit(iter);
539 bool UnusedTypeRemover::apply(Stage &stage)
541 stage.content.visit(*this);
542 NodeRemover().apply(stage, unused_nodes);
543 return !unused_nodes.empty();
546 void UnusedTypeRemover::visit(Literal &literal)
548 unused_nodes.erase(literal.type);
551 void UnusedTypeRemover::visit(UnaryExpression &unary)
553 unused_nodes.erase(unary.type);
554 TraversingVisitor::visit(unary);
557 void UnusedTypeRemover::visit(BinaryExpression &binary)
559 unused_nodes.erase(binary.type);
560 TraversingVisitor::visit(binary);
563 void UnusedTypeRemover::visit(TernaryExpression &ternary)
565 unused_nodes.erase(ternary.type);
566 TraversingVisitor::visit(ternary);
569 void UnusedTypeRemover::visit(FunctionCall &call)
571 unused_nodes.erase(call.type);
572 TraversingVisitor::visit(call);
575 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
578 unused_nodes.erase(type.base_type);
579 unused_nodes.insert(&type);
582 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
585 unused_nodes.erase(type.base_type);
586 unused_nodes.insert(&type);
589 void UnusedTypeRemover::visit(StructDeclaration &strct)
591 unused_nodes.insert(&strct);
592 TraversingVisitor::visit(strct);
595 void UnusedTypeRemover::visit(VariableDeclaration &var)
597 unused_nodes.erase(var.type_declaration);
600 void UnusedTypeRemover::visit(InterfaceBlock &iface)
602 unused_nodes.erase(iface.type_declaration);
605 void UnusedTypeRemover::visit(FunctionDeclaration &func)
607 unused_nodes.erase(func.return_type_declaration);
608 TraversingVisitor::visit(func);
612 UnusedVariableRemover::UnusedVariableRemover():
616 assignment_target(false),
617 r_side_effects(false)
620 bool UnusedVariableRemover::apply(Stage &s)
623 s.content.visit(*this);
625 for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
626 if(i->used_by.empty())
627 unused_nodes.insert(i->node);
629 for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
630 if(i->second->instance_name.empty())
631 unused_nodes.insert(i->second);
633 for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
637 /* The last visible assignments of output variables are used by the
638 next stage or the API. */
639 for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
640 unused_nodes.erase((*j)->node);
643 if(!i->second.output && !i->second.referenced)
645 // Don't remove variables from inside interface blocks.
646 if(!i->second.interface_block)
647 unused_nodes.insert(i->first);
649 else if(i->second.interface_block)
650 // Interface blocks are kept if even one member is used.
651 unused_nodes.erase(i->second.interface_block);
654 NodeRemover().apply(s, unused_nodes);
656 return !unused_nodes.empty();
659 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
661 VariableInfo &var_info = variables[target.declaration];
662 var_info.referenced = true;
663 if(!assignment_target)
665 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
666 (*i)->used_by.push_back(&node);
670 void UnusedVariableRemover::visit(VariableReference &var)
672 referenced(var.declaration, var);
675 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
677 referenced(iface.declaration, iface);
680 void UnusedVariableRemover::visit(UnaryExpression &unary)
682 TraversingVisitor::visit(unary);
683 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
684 r_side_effects = true;
687 void UnusedVariableRemover::visit(BinaryExpression &binary)
689 if(binary.oper->token[0]=='[')
691 binary.left->visit(*this);
692 SetFlag set(assignment_target, false);
693 binary.right->visit(*this);
696 TraversingVisitor::visit(binary);
699 void UnusedVariableRemover::visit(Assignment &assign)
702 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
703 assign.left->visit(*this);
705 assign.right->visit(*this);
706 r_assignment = &assign;
707 r_side_effects = true;
710 void UnusedVariableRemover::visit(FunctionCall &call)
712 TraversingVisitor::visit(call);
713 /* Treat function calls as having side effects so expression statements
714 consisting of nothing but a function call won't be optimized away. */
715 r_side_effects = true;
717 if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
719 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
721 referenced(i->first, call);
725 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
727 assignments.push_back(AssignmentInfo());
728 AssignmentInfo &assign_info = assignments.back();
729 assign_info.node = &node;
730 assign_info.target = target;
732 /* An assignment to the target hides any assignments to the same target or
734 VariableInfo &var_info = variables[target.declaration];
735 for(unsigned i=0; i<var_info.assignments.size(); ++i)
737 const Assignment::Target &t = var_info.assignments[i]->target;
739 bool subfield = (t.chain_len>=target.chain_len);
740 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
741 subfield = (t.chain[j]==target.chain[j]);
744 var_info.assignments.erase(var_info.assignments.begin()+i);
749 var_info.assignments.push_back(&assign_info);
752 void UnusedVariableRemover::visit(ExpressionStatement &expr)
755 r_side_effects = false;
756 TraversingVisitor::visit(expr);
757 if(r_assignment && r_assignment->target.declaration)
758 record_assignment(r_assignment->target, expr);
760 unused_nodes.insert(&expr);
763 void UnusedVariableRemover::visit(VariableDeclaration &var)
765 VariableInfo &var_info = variables[&var];
766 var_info.interface_block = interface_block;
768 /* Mark variables as output if they're used by the next stage or the
771 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
773 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
775 if(var.init_expression)
777 var_info.initialized = true;
778 record_assignment(&var, *var.init_expression);
780 TraversingVisitor::visit(var);
783 void UnusedVariableRemover::visit(InterfaceBlock &iface)
785 if(iface.instance_name.empty())
787 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
788 iface.struct_declaration->members.visit(*this);
792 VariableInfo &var_info = variables[&iface];
793 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
797 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
799 for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
801 BlockVariableMap::iterator j = variables.find(i->first);
802 if(j!=variables.end())
804 /* The merged blocks started as copies of each other so any common
805 assignments must be in the beginning. */
807 for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
808 if(i->second.assignments[k]!=j->second.assignments[k])
811 // Remaining assignments are unique to each block; merge them.
812 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
813 j->second.referenced |= i->second.referenced;
816 variables.insert(*i);
820 void UnusedVariableRemover::visit(FunctionDeclaration &func)
822 if(func.body.body.empty())
825 BlockVariableMap saved_vars = variables;
826 // Assignments from other functions should not be visible.
827 for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
828 i->second.assignments.resize(i->second.initialized);
829 TraversingVisitor::visit(func);
830 swap(variables, saved_vars);
831 merge_variables(saved_vars);
833 /* Always treat function parameters as referenced. Removing unused
834 parameters is not currently supported. */
835 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
837 BlockVariableMap::iterator j = variables.find(i->get());
838 if(j!=variables.end())
839 j->second.referenced = true;
843 void UnusedVariableRemover::visit(Conditional &cond)
845 cond.condition->visit(*this);
846 BlockVariableMap saved_vars = variables;
847 cond.body.visit(*this);
848 swap(saved_vars, variables);
849 cond.else_body.visit(*this);
851 /* Visible assignments after the conditional is the union of those visible
852 at the end of the if and else blocks. If there was no else block, then it's
853 the union of the if block and the state before it. */
854 merge_variables(saved_vars);
857 void UnusedVariableRemover::visit(Iteration &iter)
859 BlockVariableMap saved_vars = variables;
860 TraversingVisitor::visit(iter);
862 /* Merge assignments from the iteration, without clearing previous state.
863 Further analysis is needed to determine which parts of the iteration body
864 are always executed, if any. */
865 merge_variables(saved_vars);
869 bool UnusedFunctionRemover::apply(Stage &stage)
871 stage.content.visit(*this);
872 NodeRemover().apply(stage, unused_nodes);
873 return !unused_nodes.empty();
876 void UnusedFunctionRemover::visit(FunctionCall &call)
878 TraversingVisitor::visit(call);
880 unused_nodes.erase(call.declaration);
881 if(call.declaration && call.declaration->definition!=call.declaration)
882 used_definitions.insert(call.declaration->definition);
885 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
887 TraversingVisitor::visit(func);
889 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
890 unused_nodes.insert(&func);