source/glsl/optimize.cpp

   1 #include <msp/core/raii.h>
   2 #include "optimize.h"
   3
   4 using namespace std;
   5
   6 namespace Msp {
   7 namespace GL {
   8 namespace SL {
   9
  10 InlineableFunctionLocator::InlineableFunctionLocator():
  11         in_function(0)
  12 { }
  13
  14 void InlineableFunctionLocator::visit(FunctionCall &call)
  15 {
  16         FunctionDeclaration *def = call.declaration;
  17         if(def)
  18                 def = def->definition;
  19
  20         if(def)
  21         {
  22                 unsigned &count = refcounts[def];
  23                 ++count;
  24                 if(count>1 || def==in_function)
  25                         inlineable.erase(def);
  26         }
  27
  28         TraversingVisitor::visit(call);
  29 }
  30
  31 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
  32 {
  33         unsigned &count = refcounts[func.definition];
  34         if(!count && func.parameters.empty())
  35                 inlineable.insert(func.definition);
  36
  37         SetForScope<FunctionDeclaration *> set(in_function, &func);
  38         TraversingVisitor::visit(func);
  39 }
  40
  41
  42 void InlineDependencyCollector::visit(VariableReference &var)
  43 {
  44         if(var.declaration)
  45         {
  46                 dependencies.insert(var.declaration);
  47                 var.declaration->visit(*this);
  48         }
  49 }
  50
  51 void InlineDependencyCollector::visit(InterfaceBlockReference &iface)
  52 {
  53         if(iface.declaration)
  54         {
  55                 dependencies.insert(iface.declaration);
  56                 iface.declaration->visit(*this);
  57         }
  58 }
  59
  60 void InlineDependencyCollector::visit(FunctionCall &call)
  61 {
  62         if(call.declaration)
  63                 dependencies.insert(call.declaration);
  64         TraversingVisitor::visit(call);
  65 }
  66
  67 void InlineDependencyCollector::visit(VariableDeclaration &var)
  68 {
  69         if(var.type_declaration)
  70         {
  71                 dependencies.insert(var.type_declaration);
  72                 var.type_declaration->visit(*this);
  73         }
  74 }
  75
  76
  77 FunctionInliner::FunctionInliner():
  78         current_function(0),
  79         extract_result(0),
  80         any_inlined(false)
  81 { }
  82
  83 bool FunctionInliner::apply(Stage &s)
  84 {
  85         stage = &s;
  86         inlineable = InlineableFunctionLocator().apply(s);
  87         any_inlined = false;
  88         s.content.visit(*this);
  89         return any_inlined;
  90 }
  91
  92 void FunctionInliner::visit_and_inline(RefPtr<Expression> &ptr)
  93 {
  94         inline_result = 0;
  95         ptr->visit(*this);
  96         if(inline_result)
  97         {
  98                 ptr = inline_result;
  99                 any_inlined = true;
 100         }
 101 }
 102
 103 void FunctionInliner::visit(Block &block)
 104 {
 105         if(extract_result)
 106                 --extract_result;
 107
 108         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 109         {
 110                 (*i)->visit(*this);
 111                 if(extract_result)
 112                         --extract_result;
 113         }
 114 }
 115
 116 void FunctionInliner::visit(UnaryExpression &unary)
 117 {
 118         visit_and_inline(unary.expression);
 119         inline_result = 0;
 120 }
 121
 122 void FunctionInliner::visit(BinaryExpression &binary)
 123 {
 124         visit_and_inline(binary.left);
 125         visit_and_inline(binary.right);
 126         inline_result = 0;
 127 }
 128
 129 void FunctionInliner::visit(MemberAccess &memacc)
 130 {
 131         visit_and_inline(memacc.left);
 132         inline_result = 0;
 133 }
 134
 135 void FunctionInliner::visit(FunctionCall &call)
 136 {
 137         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 138                 visit_and_inline(*i);
 139
 140         FunctionDeclaration *def = call.declaration;
 141         if(def)
 142                 def = def->definition;
 143
 144         if(def && inlineable.count(def))
 145         {
 146                 extract_result = 2;
 147                 def->visit(*this);
 148
 149                 if(inline_result)
 150                         NodeReorderer().apply(*stage, *current_function, InlineDependencyCollector().apply(*def));
 151         }
 152         else
 153                 inline_result = 0;
 154 }
 155
 156 void FunctionInliner::visit(VariableDeclaration &var)
 157 {
 158         if(var.init_expression)
 159                 visit_and_inline(var.init_expression);
 160         inline_result = 0;
 161 }
 162
 163 void FunctionInliner::visit(FunctionDeclaration &func)
 164 {
 165         SetForScope<FunctionDeclaration *> set_func(current_function, &func);
 166         TraversingVisitor::visit(func);
 167 }
 168
 169 void FunctionInliner::visit(Return &ret)
 170 {
 171         TraversingVisitor::visit(ret);
 172
 173         if(extract_result)
 174                 inline_result = ret.expression->clone();
 175 }
 176
 177
 178 ConstantConditionEliminator::ConstantConditionEliminator():
 179         record_only(false)
 180 { }
 181
 182 void ConstantConditionEliminator::apply(Stage &stage)
 183 {
 184         stage.content.visit(*this);
 185         NodeRemover().apply(stage, nodes_to_remove);
 186 }
 187
 188 void ConstantConditionEliminator::visit(Block &block)
 189 {
 190         SetForScope<Block *> set_block(current_block, &block);
 191         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 192         {
 193                 insert_point = i;
 194                 (*i)->visit(*this);
 195         }
 196
 197         for(map<string, VariableDeclaration *>::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 198                 variable_values.erase(i->second);
 199 }
 200
 201 void ConstantConditionEliminator::visit(UnaryExpression &unary)
 202 {
 203         if(VariableReference *var = dynamic_cast<VariableReference *>(unary.expression.get()))
 204                 if(unary.oper=="++" || unary.oper=="--")
 205                         variable_values.erase(var->declaration);
 206 }
 207
 208 void ConstantConditionEliminator::visit(Assignment &assign)
 209 {
 210         variable_values.erase(assign.target_declaration);
 211 }
 212
 213 void ConstantConditionEliminator::visit(VariableDeclaration &var)
 214 {
 215         bool constant = var.constant;
 216         if(constant && var.layout)
 217         {
 218                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 219                         constant = (i->name!="constant_id");
 220         }
 221         if((constant || current_block->parent) && var.init_expression)
 222                 variable_values[&var] = var.init_expression.get();
 223 }
 224
 225 void ConstantConditionEliminator::visit(Conditional &cond)
 226 {
 227         if(!record_only)
 228         {
 229                 ExpressionEvaluator eval(variable_values);
 230                 cond.condition->visit(eval);
 231                 if(eval.is_result_valid())
 232                 {
 233                         Block &block = (eval.get_result() ? cond.body : cond.else_body);
 234                         current_block->body.splice(insert_point, block.body);
 235                         nodes_to_remove.insert(&cond);
 236                         return;
 237                 }
 238         }
 239
 240         TraversingVisitor::visit(cond);
 241 }
 242
 243 void ConstantConditionEliminator::visit(Iteration &iter)
 244 {
 245         if(!record_only)
 246         {
 247                 if(iter.condition)
 248                 {
 249                         /* If the loop condition is always false on the first iteration, the
 250                         entire loop can be removed */
 251                         if(iter.init_statement)
 252                                 iter.init_statement->visit(*this);
 253                         ExpressionEvaluator eval(variable_values);
 254                         iter.condition->visit(eval);
 255                         if(eval.is_result_valid() && !eval.get_result())
 256                         {
 257                                 nodes_to_remove.insert(&iter);
 258                                 return;
 259                         }
 260                 }
 261
 262                 /* Record all assignments that occur inside the loop body so those
 263                 variables won't be considered as constant */
 264                 SetFlag set_record(record_only);
 265                 TraversingVisitor::visit(iter);
 266         }
 267
 268         TraversingVisitor::visit(iter);
 269
 270         if(VariableDeclaration *init_decl = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
 271                 variable_values.erase(init_decl);
 272 }
 273
 274
 275 UnusedVariableRemover::VariableInfo::VariableInfo():
 276         local(false),
 277         conditionally_assigned(false),
 278         referenced(false)
 279 { }
 280
 281
 282 UnusedVariableRemover::UnusedVariableRemover():
 283         aggregate(0),
 284         assignment(0),
 285         assignment_target(false),
 286         assign_to_subscript(false),
 287         side_effects(false)
 288 { }
 289
 290 bool UnusedVariableRemover::apply(Stage &stage)
 291 {
 292         variables.push_back(BlockVariableMap());
 293         stage.content.visit(*this);
 294         BlockVariableMap &global_variables = variables.back();
 295         for(BlockVariableMap::iterator i=global_variables.begin(); i!=global_variables.end(); ++i)
 296         {
 297                 if(i->first->interface=="out" && (stage.type==Stage::FRAGMENT || i->first->linked_declaration || !i->first->name.compare(0, 3, "gl_")))
 298                         continue;
 299                 if(!i->second.referenced)
 300                 {
 301                         unused_nodes.insert(i->first);
 302                         clear_assignments(i->second, true);
 303                 }
 304         }
 305         variables.pop_back();
 306
 307         NodeRemover().apply(stage, unused_nodes);
 308
 309         return !unused_nodes.empty();
 310 }
 311
 312 void UnusedVariableRemover::visit(VariableReference &var)
 313 {
 314         map<VariableDeclaration *, Node *>::iterator i = aggregates.find(var.declaration);
 315         if(i!=aggregates.end())
 316                 unused_nodes.erase(i->second);
 317
 318         if(var.declaration && !assignment_target)
 319         {
 320                 VariableInfo &var_info = variables.back()[var.declaration];
 321                 clear_assignments(var_info, false);
 322                 var_info.referenced = true;
 323         }
 324 }
 325
 326 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 327 {
 328         unused_nodes.erase(iface.declaration);
 329 }
 330
 331 void UnusedVariableRemover::visit(MemberAccess &memacc)
 332 {
 333         TraversingVisitor::visit(memacc);
 334         unused_nodes.erase(memacc.declaration);
 335 }
 336
 337 void UnusedVariableRemover::visit(UnaryExpression &unary)
 338 {
 339         TraversingVisitor::visit(unary);
 340         if(unary.oper=="++" || unary.oper=="--")
 341                 side_effects = true;
 342 }
 343
 344 void UnusedVariableRemover::visit(BinaryExpression &binary)
 345 {
 346         if(binary.oper=="[")
 347         {
 348                 if(assignment_target)
 349                         assign_to_subscript = true;
 350                 binary.left->visit(*this);
 351                 SetForScope<bool> set(assignment_target, false);
 352                 binary.right->visit(*this);
 353         }
 354         else
 355                 TraversingVisitor::visit(binary);
 356 }
 357
 358 void UnusedVariableRemover::visit(Assignment &assign)
 359 {
 360         {
 361                 assign_to_subscript = false;
 362                 SetForScope<bool> set(assignment_target, !assign.self_referencing);
 363                 assign.left->visit(*this);
 364         }
 365         assign.right->visit(*this);
 366         assignment = &assign;
 367         side_effects = true;
 368 }
 369
 370 void UnusedVariableRemover::visit(FunctionCall &call)
 371 {
 372         TraversingVisitor::visit(call);
 373         side_effects = true;
 374 }
 375
 376 void UnusedVariableRemover::record_assignment(VariableDeclaration &var, Node &node, bool chained)
 377 {
 378         VariableInfo &var_info = variables.back()[&var];
 379         if(!chained)
 380                 clear_assignments(var_info, true);
 381         var_info.assignments.push_back(&node);
 382         var_info.conditionally_assigned = false;
 383 }
 384
 385 void UnusedVariableRemover::clear_assignments(VariableInfo &var_info, bool mark_unused)
 386 {
 387         if(mark_unused)
 388         {
 389                 for(vector<Node *>::iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 390                         unused_nodes.insert(*i);
 391         }
 392         var_info.assignments.clear();
 393 }
 394
 395 void UnusedVariableRemover::visit(ExpressionStatement &expr)
 396 {
 397         assignment = 0;
 398         side_effects = false;
 399         TraversingVisitor::visit(expr);
 400         if(assignment && assignment->target_declaration)
 401                 record_assignment(*assignment->target_declaration, expr, (assignment->self_referencing || assign_to_subscript));
 402         if(!side_effects)
 403                 unused_nodes.insert(&expr);
 404 }
 405
 406 void UnusedVariableRemover::visit(StructDeclaration &strct)
 407 {
 408         SetForScope<Node *> set(aggregate, &strct);
 409         unused_nodes.insert(&strct);
 410         TraversingVisitor::visit(strct);
 411 }
 412
 413 void UnusedVariableRemover::visit(VariableDeclaration &var)
 414 {
 415         if(aggregate)
 416                 aggregates[&var] = aggregate;
 417         else
 418         {
 419                 variables.back()[&var].local = true;
 420                 if(var.init_expression)
 421                         record_assignment(var, *var.init_expression, false);
 422         }
 423         unused_nodes.erase(var.type_declaration);
 424         TraversingVisitor::visit(var);
 425 }
 426
 427 void UnusedVariableRemover::visit(InterfaceBlock &iface)
 428 {
 429         SetForScope<Node *> set(aggregate, &iface);
 430         unused_nodes.insert(&iface);
 431         TraversingVisitor::visit(iface);
 432 }
 433
 434 void UnusedVariableRemover::visit(FunctionDeclaration &func)
 435 {
 436         variables.push_back(BlockVariableMap());
 437
 438         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 439                 (*i)->visit(*this);
 440         func.body.visit(*this);
 441
 442         BlockVariableMap &block_variables = variables.back();
 443         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 444                 i->second.conditionally_assigned = true;
 445         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 446                 block_variables[i->get()].referenced = true;
 447         merge_down_variables();
 448 }
 449
 450 void UnusedVariableRemover::merge_down_variables()
 451 {
 452         BlockVariableMap &parent_variables = variables[variables.size()-2];
 453         BlockVariableMap &block_variables = variables.back();
 454         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 455         {
 456                 if(i->second.local)
 457                 {
 458                         if(!i->second.referenced)
 459                                 unused_nodes.insert(i->first);
 460                         clear_assignments(i->second, i->first->interface!="out");
 461                         continue;
 462                 }
 463
 464                 BlockVariableMap::iterator j = parent_variables.find(i->first);
 465                 if(j==parent_variables.end())
 466                         parent_variables.insert(*i);
 467                 else
 468                 {
 469                         if(i->second.referenced || !i->second.conditionally_assigned)
 470                                 clear_assignments(j->second, !i->second.referenced);
 471                         j->second.conditionally_assigned = i->second.conditionally_assigned;
 472                         j->second.referenced |= i->second.referenced;
 473                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end());
 474                 }
 475         }
 476         variables.pop_back();
 477 }
 478
 479 void UnusedVariableRemover::visit(Conditional &cond)
 480 {
 481         cond.condition->visit(*this);
 482         variables.push_back(BlockVariableMap());
 483         cond.body.visit(*this);
 484
 485         BlockVariableMap if_variables;
 486         swap(variables.back(), if_variables);
 487         cond.else_body.visit(*this);
 488
 489         BlockVariableMap &else_variables = variables.back();
 490         for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i)
 491         {
 492                 BlockVariableMap::iterator j = if_variables.find(i->first);
 493                 if(j!=if_variables.end())
 494                 {
 495                         i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end());
 496                         i->second.conditionally_assigned |= j->second.conditionally_assigned;
 497                         if_variables.erase(j);
 498                 }
 499                 else
 500                         i->second.conditionally_assigned = true;
 501         }
 502
 503         for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i)
 504         {
 505                 i->second.conditionally_assigned = true;
 506                 else_variables.insert(*i);
 507         }
 508
 509         merge_down_variables();
 510 }
 511
 512 void UnusedVariableRemover::visit(Iteration &iter)
 513 {
 514         variables.push_back(BlockVariableMap());
 515         TraversingVisitor::visit(iter);
 516
 517         BlockVariableMap &block_variables = variables.back();
 518         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 519                 if(!i->second.local && i->second.referenced)
 520                         clear_assignments(i->second, false);
 521
 522         merge_down_variables();
 523 }
 524
 525
 526 bool UnusedFunctionRemover::apply(Stage &stage)
 527 {
 528         stage.content.visit(*this);
 529         NodeRemover().apply(stage, unused_nodes);
 530         return !unused_nodes.empty();
 531 }
 532
 533 void UnusedFunctionRemover::visit(FunctionCall &call)
 534 {
 535         TraversingVisitor::visit(call);
 536
 537         unused_nodes.erase(call.declaration);
 538         if(call.declaration && call.declaration->definition!=call.declaration)
 539                 used_definitions.insert(call.declaration->definition);
 540 }
 541
 542 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
 543 {
 544         TraversingVisitor::visit(func);
 545
 546         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 547                 unused_nodes.insert(&func);
 548 }
 549
 550 } // namespace SL
 551 } // namespace GL
 552 } // namespace Msp