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