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