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_and_inline(RefPtr<Expression> &ptr)
202 ptr = r_inline_result;
203 r_any_inlined = true;
207 void FunctionInliner::visit(Block &block)
209 SetForScope<Block *> set_block(current_block, &block);
210 SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
211 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
218 void FunctionInliner::visit(UnaryExpression &unary)
220 visit_and_inline(unary.expression);
224 void FunctionInliner::visit(BinaryExpression &binary)
226 visit_and_inline(binary.left);
227 visit_and_inline(binary.right);
231 void FunctionInliner::visit(MemberAccess &memacc)
233 visit_and_inline(memacc.left);
237 void FunctionInliner::visit(FunctionCall &call)
239 for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
240 visit_and_inline(*i);
242 FunctionDeclaration *def = call.declaration;
244 def = def->definition;
246 if(def && inlineable.count(def))
248 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
250 // This will later get removed by UnusedVariableRemover.
251 if(result_name.empty())
252 result_name = "msp_unused_from_inline";
254 RefPtr<VariableReference> ref = new VariableReference;
255 ref->name = result_name;
256 r_inline_result = ref;
258 /* Inlined variables need to be resolved before this function can be
260 inlineable.erase(current_function);
266 void FunctionInliner::visit(ExpressionStatement &expr)
268 visit_and_inline(expr.expression);
271 void FunctionInliner::visit(VariableDeclaration &var)
273 if(var.init_expression)
274 visit_and_inline(var.init_expression);
278 void FunctionInliner::visit(FunctionDeclaration &func)
280 SetForScope<FunctionDeclaration *> set_func(current_function, &func);
281 TraversingVisitor::visit(func);
284 void FunctionInliner::visit(Conditional &cond)
286 visit_and_inline(cond.condition);
287 cond.body.visit(*this);
290 void FunctionInliner::visit(Iteration &iter)
292 SetForScope<Block *> set_block(current_block, &iter.body);
293 if(iter.init_statement)
294 iter.init_statement->visit(*this);
295 /* Skip the condition and loop expression parts because they're executed on
296 every iteration of the loop */
297 iter.body.visit(*this);
300 void FunctionInliner::visit(Return &ret)
303 visit_and_inline(ret.expression);
307 ConstantConditionEliminator::ConstantConditionEliminator():
311 void ConstantConditionEliminator::apply(Stage &stage)
313 stage.content.visit(*this);
314 NodeRemover().apply(stage, nodes_to_remove);
317 void ConstantConditionEliminator::visit(Block &block)
319 SetForScope<Block *> set_block(current_block, &block);
320 for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
326 for(map<string, VariableDeclaration *>::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
327 variable_values.erase(i->second);
330 void ConstantConditionEliminator::visit(UnaryExpression &unary)
332 if(VariableReference *var = dynamic_cast<VariableReference *>(unary.expression.get()))
333 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
334 variable_values.erase(var->declaration);
337 void ConstantConditionEliminator::visit(Assignment &assign)
339 variable_values.erase(assign.target_declaration);
342 void ConstantConditionEliminator::visit(VariableDeclaration &var)
344 bool constant = var.constant;
345 if(constant && var.layout)
347 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
348 constant = (i->name!="constant_id");
350 if((constant || current_block->parent) && var.init_expression)
351 variable_values[&var] = var.init_expression.get();
354 void ConstantConditionEliminator::visit(Conditional &cond)
358 ExpressionEvaluator eval(variable_values);
359 cond.condition->visit(eval);
360 if(eval.is_result_valid())
362 Block &block = (eval.get_result() ? cond.body : cond.else_body);
363 current_block->body.splice(insert_point, block.body);
364 nodes_to_remove.insert(&cond);
369 TraversingVisitor::visit(cond);
372 void ConstantConditionEliminator::visit(Iteration &iter)
378 /* If the loop condition is always false on the first iteration, the
379 entire loop can be removed */
380 if(iter.init_statement)
381 iter.init_statement->visit(*this);
382 ExpressionEvaluator eval(variable_values);
383 iter.condition->visit(eval);
384 if(eval.is_result_valid() && !eval.get_result())
386 nodes_to_remove.insert(&iter);
391 /* Record all assignments that occur inside the loop body so those
392 variables won't be considered as constant */
393 SetFlag set_record(record_only);
394 TraversingVisitor::visit(iter);
397 TraversingVisitor::visit(iter);
399 if(VariableDeclaration *init_decl = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
400 variable_values.erase(init_decl);
404 UnusedVariableRemover::VariableInfo::VariableInfo():
406 conditionally_assigned(false),
411 UnusedVariableRemover::UnusedVariableRemover():
414 assignment_target(false),
415 r_assign_to_subfield(false),
416 r_side_effects(false)
419 bool UnusedVariableRemover::apply(Stage &stage)
421 variables.push_back(BlockVariableMap());
422 stage.content.visit(*this);
423 BlockVariableMap &global_variables = variables.back();
424 for(BlockVariableMap::iterator i=global_variables.begin(); i!=global_variables.end(); ++i)
426 /* Don't remove output variables which are used by the next stage or the
428 if(i->first->interface=="out" && (stage.type==Stage::FRAGMENT || i->first->linked_declaration || !i->first->name.compare(0, 3, "gl_")))
431 // Mark other unreferenced global variables as unused.
432 if(!i->second.referenced)
434 unused_nodes.insert(i->first);
435 clear_assignments(i->second, true);
438 variables.pop_back();
440 NodeRemover().apply(stage, unused_nodes);
442 return !unused_nodes.empty();
445 void UnusedVariableRemover::visit(VariableReference &var)
447 map<VariableDeclaration *, Node *>::iterator i = aggregates.find(var.declaration);
448 if(i!=aggregates.end())
449 unused_nodes.erase(i->second);
451 if(var.declaration && !assignment_target)
453 VariableInfo &var_info = variables.back()[var.declaration];
454 // Previous assignments are used by this reference.
455 clear_assignments(var_info, false);
456 var_info.referenced = true;
460 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
462 unused_nodes.erase(iface.declaration);
465 void UnusedVariableRemover::visit(MemberAccess &memacc)
467 r_assign_to_subfield = true;
468 TraversingVisitor::visit(memacc);
469 unused_nodes.erase(memacc.declaration);
472 void UnusedVariableRemover::visit(UnaryExpression &unary)
474 TraversingVisitor::visit(unary);
475 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
476 r_side_effects = true;
479 void UnusedVariableRemover::visit(BinaryExpression &binary)
481 if(binary.oper->token[0]=='[')
483 if(assignment_target)
484 r_assign_to_subfield = true;
485 binary.left->visit(*this);
486 SetFlag set(assignment_target, false);
487 binary.right->visit(*this);
490 TraversingVisitor::visit(binary);
493 void UnusedVariableRemover::visit(Assignment &assign)
496 SetFlag set(assignment_target, !assign.self_referencing);
497 assign.left->visit(*this);
499 assign.right->visit(*this);
500 r_assignment = &assign;
501 r_side_effects = true;
504 void UnusedVariableRemover::visit(FunctionCall &call)
506 TraversingVisitor::visit(call);
507 /* Treat function calls as having side effects so expression statements
508 consisting of nothing but a function call won't be optimized away. */
509 r_side_effects = true;
512 void UnusedVariableRemover::record_assignment(VariableDeclaration &var, Node &node, bool chained)
514 VariableInfo &var_info = variables.back()[&var];
515 /* An assignment which completely replaces the value of the variable causes
516 any previous unreferenced assignments to be unused. */
518 clear_assignments(var_info, true);
519 var_info.assignments.push_back(&node);
520 var_info.conditionally_assigned = false;
523 void UnusedVariableRemover::clear_assignments(VariableInfo &var_info, bool mark_unused)
527 for(vector<Node *>::iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
528 unused_nodes.insert(*i);
530 var_info.assignments.clear();
533 void UnusedVariableRemover::visit(ExpressionStatement &expr)
536 r_assign_to_subfield = false;
537 r_side_effects = false;
538 TraversingVisitor::visit(expr);
539 if(r_assignment && r_assignment->target_declaration)
540 record_assignment(*r_assignment->target_declaration, expr, (r_assignment->self_referencing || r_assign_to_subfield));
542 unused_nodes.insert(&expr);
545 void UnusedVariableRemover::visit(StructDeclaration &strct)
547 SetForScope<Node *> set(aggregate, &strct);
548 unused_nodes.insert(&strct);
549 TraversingVisitor::visit(strct);
552 void UnusedVariableRemover::visit(VariableDeclaration &var)
555 aggregates[&var] = aggregate;
558 variables.back()[&var].local = true;
559 if(var.init_expression)
560 record_assignment(var, *var.init_expression, false);
562 unused_nodes.erase(var.type_declaration);
563 TraversingVisitor::visit(var);
566 void UnusedVariableRemover::visit(InterfaceBlock &iface)
568 SetForScope<Node *> set(aggregate, &iface);
569 unused_nodes.insert(&iface);
570 TraversingVisitor::visit(iface);
573 void UnusedVariableRemover::visit(FunctionDeclaration &func)
575 variables.push_back(BlockVariableMap());
577 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
579 func.body.visit(*this);
581 BlockVariableMap &block_variables = variables.back();
583 /* Mark global variables as conditionally assigned so assignments in other
584 functions won't be removed. */
585 for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
587 i->second.conditionally_assigned = true;
589 /* Always treat function parameters as referenced. Removing unused
590 parameters is not currently supported. */
591 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
592 block_variables[i->get()].referenced = true;
594 merge_down_variables();
597 void UnusedVariableRemover::merge_down_variables()
599 BlockVariableMap &parent_variables = variables[variables.size()-2];
600 BlockVariableMap &block_variables = variables.back();
601 for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
605 if(!i->second.referenced)
606 unused_nodes.insert(i->first);
607 /* Any unreferenced assignments when a variable runs out of scope
609 clear_assignments(i->second, true);
613 BlockVariableMap::iterator j = parent_variables.find(i->first);
614 if(j==parent_variables.end())
615 parent_variables.insert(*i);
618 // Merge a non-local variable's state into the parent scope.
619 if(i->second.referenced || !i->second.conditionally_assigned)
620 clear_assignments(j->second, !i->second.referenced);
621 j->second.conditionally_assigned = i->second.conditionally_assigned;
622 j->second.referenced |= i->second.referenced;
623 j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end());
626 variables.pop_back();
629 void UnusedVariableRemover::visit(Conditional &cond)
631 cond.condition->visit(*this);
632 variables.push_back(BlockVariableMap());
633 cond.body.visit(*this);
635 BlockVariableMap if_variables;
636 swap(variables.back(), if_variables);
637 cond.else_body.visit(*this);
639 // Combine variables from both branches.
640 BlockVariableMap &else_variables = variables.back();
641 for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i)
643 BlockVariableMap::iterator j = if_variables.find(i->first);
644 if(j!=if_variables.end())
646 // The variable was found in both branches.
647 i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end());
648 i->second.conditionally_assigned |= j->second.conditionally_assigned;
649 if_variables.erase(j);
652 // Mark variables found in only one branch as conditionally assigned.
653 i->second.conditionally_assigned = true;
656 /* Move variables which were only used in the if block into the combined
658 for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i)
660 i->second.conditionally_assigned = true;
661 else_variables.insert(*i);
664 merge_down_variables();
667 void UnusedVariableRemover::visit(Iteration &iter)
669 variables.push_back(BlockVariableMap());
670 TraversingVisitor::visit(iter);
671 merge_down_variables();
675 bool UnusedFunctionRemover::apply(Stage &stage)
677 stage.content.visit(*this);
678 NodeRemover().apply(stage, unused_nodes);
679 return !unused_nodes.empty();
682 void UnusedFunctionRemover::visit(FunctionCall &call)
684 TraversingVisitor::visit(call);
686 unused_nodes.erase(call.declaration);
687 if(call.declaration && call.declaration->definition!=call.declaration)
688 used_definitions.insert(call.declaration->definition);
691 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
693 TraversingVisitor::visit(func);
695 if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
696 unused_nodes.insert(&func);