source/glsl/optimize.cpp

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