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<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
 203         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 204         {
 205                 insert_point = i;
 206                 (*i)->visit(*this);
 207         }
 208 }
 209
 210 void FunctionInliner::visit(UnaryExpression &unary)
 211 {
 212         visit_and_inline(unary.expression);
 213         inline_result = 0;
 214 }
 215
 216 void FunctionInliner::visit(BinaryExpression &binary)
 217 {
 218         visit_and_inline(binary.left);
 219         visit_and_inline(binary.right);
 220         inline_result = 0;
 221 }
 222
 223 void FunctionInliner::visit(MemberAccess &memacc)
 224 {
 225         visit_and_inline(memacc.left);
 226         inline_result = 0;
 227 }
 228
 229 void FunctionInliner::visit(FunctionCall &call)
 230 {
 231         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 232                 visit_and_inline(*i);
 233
 234         FunctionDeclaration *def = call.declaration;
 235         if(def)
 236                 def = def->definition;
 237
 238         if(def && inlineable.count(def))
 239         {
 240                 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
 241
 242                 // This will later get removed by UnusedVariableRemover
 243                 if(result_name.empty())
 244                         result_name = "msp_unused_from_inline";
 245
 246                 RefPtr<VariableReference> ref = new VariableReference;
 247                 ref->name = result_name;
 248                 inline_result = ref;
 249
 250                 /* Inlined variables need to be resolved before this function can be
 251                 inlined further. */
 252                 inlineable.erase(current_function);
 253         }
 254         else
 255                 inline_result = 0;
 256 }
 257
 258 void FunctionInliner::visit(ExpressionStatement &expr)
 259 {
 260         visit_and_inline(expr.expression);
 261 }
 262
 263 void FunctionInliner::visit(VariableDeclaration &var)
 264 {
 265         if(var.init_expression)
 266                 visit_and_inline(var.init_expression);
 267         inline_result = 0;
 268 }
 269
 270 void FunctionInliner::visit(FunctionDeclaration &func)
 271 {
 272         SetForScope<FunctionDeclaration *> set_func(current_function, &func);
 273         TraversingVisitor::visit(func);
 274 }
 275
 276 void FunctionInliner::visit(Return &ret)
 277 {
 278         if(ret.expression)
 279                 visit_and_inline(ret.expression);
 280 }
 281
 282
 283 ConstantConditionEliminator::ConstantConditionEliminator():
 284         record_only(false)
 285 { }
 286
 287 void ConstantConditionEliminator::apply(Stage &stage)
 288 {
 289         stage.content.visit(*this);
 290         NodeRemover().apply(stage, nodes_to_remove);
 291 }
 292
 293 void ConstantConditionEliminator::visit(Block &block)
 294 {
 295         SetForScope<Block *> set_block(current_block, &block);
 296         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 297         {
 298                 insert_point = i;
 299                 (*i)->visit(*this);
 300         }
 301
 302         for(map<string, VariableDeclaration *>::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 303                 variable_values.erase(i->second);
 304 }
 305
 306 void ConstantConditionEliminator::visit(UnaryExpression &unary)
 307 {
 308         if(VariableReference *var = dynamic_cast<VariableReference *>(unary.expression.get()))
 309                 if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 310                         variable_values.erase(var->declaration);
 311 }
 312
 313 void ConstantConditionEliminator::visit(Assignment &assign)
 314 {
 315         variable_values.erase(assign.target_declaration);
 316 }
 317
 318 void ConstantConditionEliminator::visit(VariableDeclaration &var)
 319 {
 320         bool constant = var.constant;
 321         if(constant && var.layout)
 322         {
 323                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 324                         constant = (i->name!="constant_id");
 325         }
 326         if((constant || current_block->parent) && var.init_expression)
 327                 variable_values[&var] = var.init_expression.get();
 328 }
 329
 330 void ConstantConditionEliminator::visit(Conditional &cond)
 331 {
 332         if(!record_only)
 333         {
 334                 ExpressionEvaluator eval(variable_values);
 335                 cond.condition->visit(eval);
 336                 if(eval.is_result_valid())
 337                 {
 338                         Block &block = (eval.get_result() ? cond.body : cond.else_body);
 339                         current_block->body.splice(insert_point, block.body);
 340                         nodes_to_remove.insert(&cond);
 341                         return;
 342                 }
 343         }
 344
 345         TraversingVisitor::visit(cond);
 346 }
 347
 348 void ConstantConditionEliminator::visit(Iteration &iter)
 349 {
 350         if(!record_only)
 351         {
 352                 if(iter.condition)
 353                 {
 354                         /* If the loop condition is always false on the first iteration, the
 355                         entire loop can be removed */
 356                         if(iter.init_statement)
 357                                 iter.init_statement->visit(*this);
 358                         ExpressionEvaluator eval(variable_values);
 359                         iter.condition->visit(eval);
 360                         if(eval.is_result_valid() && !eval.get_result())
 361                         {
 362                                 nodes_to_remove.insert(&iter);
 363                                 return;
 364                         }
 365                 }
 366
 367                 /* Record all assignments that occur inside the loop body so those
 368                 variables won't be considered as constant */
 369                 SetFlag set_record(record_only);
 370                 TraversingVisitor::visit(iter);
 371         }
 372
 373         TraversingVisitor::visit(iter);
 374
 375         if(VariableDeclaration *init_decl = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
 376                 variable_values.erase(init_decl);
 377 }
 378
 379
 380 UnusedVariableRemover::VariableInfo::VariableInfo():
 381         local(false),
 382         conditionally_assigned(false),
 383         referenced(false)
 384 { }
 385
 386
 387 UnusedVariableRemover::UnusedVariableRemover():
 388         aggregate(0),
 389         assignment(0),
 390         assignment_target(false),
 391         assign_to_subscript(false),
 392         side_effects(false)
 393 { }
 394
 395 bool UnusedVariableRemover::apply(Stage &stage)
 396 {
 397         variables.push_back(BlockVariableMap());
 398         stage.content.visit(*this);
 399         BlockVariableMap &global_variables = variables.back();
 400         for(BlockVariableMap::iterator i=global_variables.begin(); i!=global_variables.end(); ++i)
 401         {
 402                 if(i->first->interface=="out" && (stage.type==Stage::FRAGMENT || i->first->linked_declaration || !i->first->name.compare(0, 3, "gl_")))
 403                         continue;
 404                 if(!i->second.referenced)
 405                 {
 406                         unused_nodes.insert(i->first);
 407                         clear_assignments(i->second, true);
 408                 }
 409         }
 410         variables.pop_back();
 411
 412         NodeRemover().apply(stage, unused_nodes);
 413
 414         return !unused_nodes.empty();
 415 }
 416
 417 void UnusedVariableRemover::visit(VariableReference &var)
 418 {
 419         map<VariableDeclaration *, Node *>::iterator i = aggregates.find(var.declaration);
 420         if(i!=aggregates.end())
 421                 unused_nodes.erase(i->second);
 422
 423         if(var.declaration && !assignment_target)
 424         {
 425                 VariableInfo &var_info = variables.back()[var.declaration];
 426                 clear_assignments(var_info, false);
 427                 var_info.referenced = true;
 428         }
 429 }
 430
 431 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 432 {
 433         unused_nodes.erase(iface.declaration);
 434 }
 435
 436 void UnusedVariableRemover::visit(MemberAccess &memacc)
 437 {
 438         TraversingVisitor::visit(memacc);
 439         unused_nodes.erase(memacc.declaration);
 440 }
 441
 442 void UnusedVariableRemover::visit(UnaryExpression &unary)
 443 {
 444         TraversingVisitor::visit(unary);
 445         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 446                 side_effects = true;
 447 }
 448
 449 void UnusedVariableRemover::visit(BinaryExpression &binary)
 450 {
 451         if(binary.oper->token[0]=='[')
 452         {
 453                 if(assignment_target)
 454                         assign_to_subscript = true;
 455                 binary.left->visit(*this);
 456                 SetForScope<bool> set(assignment_target, false);
 457                 binary.right->visit(*this);
 458         }
 459         else
 460                 TraversingVisitor::visit(binary);
 461 }
 462
 463 void UnusedVariableRemover::visit(Assignment &assign)
 464 {
 465         {
 466                 assign_to_subscript = false;
 467                 SetForScope<bool> set(assignment_target, !assign.self_referencing);
 468                 assign.left->visit(*this);
 469         }
 470         assign.right->visit(*this);
 471         assignment = &assign;
 472         side_effects = true;
 473 }
 474
 475 void UnusedVariableRemover::visit(FunctionCall &call)
 476 {
 477         TraversingVisitor::visit(call);
 478         side_effects = true;
 479 }
 480
 481 void UnusedVariableRemover::record_assignment(VariableDeclaration &var, Node &node, bool chained)
 482 {
 483         VariableInfo &var_info = variables.back()[&var];
 484         if(!chained)
 485                 clear_assignments(var_info, true);
 486         var_info.assignments.push_back(&node);
 487         var_info.conditionally_assigned = false;
 488 }
 489
 490 void UnusedVariableRemover::clear_assignments(VariableInfo &var_info, bool mark_unused)
 491 {
 492         if(mark_unused)
 493         {
 494                 for(vector<Node *>::iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 495                         unused_nodes.insert(*i);
 496         }
 497         var_info.assignments.clear();
 498 }
 499
 500 void UnusedVariableRemover::visit(ExpressionStatement &expr)
 501 {
 502         assignment = 0;
 503         side_effects = false;
 504         TraversingVisitor::visit(expr);
 505         if(assignment && assignment->target_declaration)
 506                 record_assignment(*assignment->target_declaration, expr, (assignment->self_referencing || assign_to_subscript));
 507         if(!side_effects)
 508                 unused_nodes.insert(&expr);
 509 }
 510
 511 void UnusedVariableRemover::visit(StructDeclaration &strct)
 512 {
 513         SetForScope<Node *> set(aggregate, &strct);
 514         unused_nodes.insert(&strct);
 515         TraversingVisitor::visit(strct);
 516 }
 517
 518 void UnusedVariableRemover::visit(VariableDeclaration &var)
 519 {
 520         if(aggregate)
 521                 aggregates[&var] = aggregate;
 522         else
 523         {
 524                 variables.back()[&var].local = true;
 525                 if(var.init_expression)
 526                         record_assignment(var, *var.init_expression, false);
 527         }
 528         unused_nodes.erase(var.type_declaration);
 529         TraversingVisitor::visit(var);
 530 }
 531
 532 void UnusedVariableRemover::visit(InterfaceBlock &iface)
 533 {
 534         SetForScope<Node *> set(aggregate, &iface);
 535         unused_nodes.insert(&iface);
 536         TraversingVisitor::visit(iface);
 537 }
 538
 539 void UnusedVariableRemover::visit(FunctionDeclaration &func)
 540 {
 541         variables.push_back(BlockVariableMap());
 542
 543         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 544                 (*i)->visit(*this);
 545         func.body.visit(*this);
 546
 547         BlockVariableMap &block_variables = variables.back();
 548         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 549                 i->second.conditionally_assigned = true;
 550         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 551                 block_variables[i->get()].referenced = true;
 552         merge_down_variables();
 553 }
 554
 555 void UnusedVariableRemover::merge_down_variables()
 556 {
 557         BlockVariableMap &parent_variables = variables[variables.size()-2];
 558         BlockVariableMap &block_variables = variables.back();
 559         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 560         {
 561                 if(i->second.local)
 562                 {
 563                         if(!i->second.referenced)
 564                                 unused_nodes.insert(i->first);
 565                         clear_assignments(i->second, i->first->interface!="out");
 566                         continue;
 567                 }
 568
 569                 BlockVariableMap::iterator j = parent_variables.find(i->first);
 570                 if(j==parent_variables.end())
 571                         parent_variables.insert(*i);
 572                 else
 573                 {
 574                         if(i->second.referenced || !i->second.conditionally_assigned)
 575                                 clear_assignments(j->second, !i->second.referenced);
 576                         j->second.conditionally_assigned = i->second.conditionally_assigned;
 577                         j->second.referenced |= i->second.referenced;
 578                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end());
 579                 }
 580         }
 581         variables.pop_back();
 582 }
 583
 584 void UnusedVariableRemover::visit(Conditional &cond)
 585 {
 586         cond.condition->visit(*this);
 587         variables.push_back(BlockVariableMap());
 588         cond.body.visit(*this);
 589
 590         BlockVariableMap if_variables;
 591         swap(variables.back(), if_variables);
 592         cond.else_body.visit(*this);
 593
 594         BlockVariableMap &else_variables = variables.back();
 595         for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i)
 596         {
 597                 BlockVariableMap::iterator j = if_variables.find(i->first);
 598                 if(j!=if_variables.end())
 599                 {
 600                         i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end());
 601                         i->second.conditionally_assigned |= j->second.conditionally_assigned;
 602                         if_variables.erase(j);
 603                 }
 604                 else
 605                         i->second.conditionally_assigned = true;
 606         }
 607
 608         for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i)
 609         {
 610                 i->second.conditionally_assigned = true;
 611                 else_variables.insert(*i);
 612         }
 613
 614         merge_down_variables();
 615 }
 616
 617 void UnusedVariableRemover::visit(Iteration &iter)
 618 {
 619         variables.push_back(BlockVariableMap());
 620         TraversingVisitor::visit(iter);
 621
 622         BlockVariableMap &block_variables = variables.back();
 623         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 624                 if(!i->second.local && i->second.referenced)
 625                         clear_assignments(i->second, false);
 626
 627         merge_down_variables();
 628 }
 629
 630
 631 bool UnusedFunctionRemover::apply(Stage &stage)
 632 {
 633         stage.content.visit(*this);
 634         NodeRemover().apply(stage, unused_nodes);
 635         return !unused_nodes.empty();
 636 }
 637
 638 void UnusedFunctionRemover::visit(FunctionCall &call)
 639 {
 640         TraversingVisitor::visit(call);
 641
 642         unused_nodes.erase(call.declaration);
 643         if(call.declaration && call.declaration->definition!=call.declaration)
 644                 used_definitions.insert(call.declaration->definition);
 645 }
 646
 647 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
 648 {
 649         TraversingVisitor::visit(func);
 650
 651         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 652                 unused_nodes.insert(&func);
 653 }
 654
 655 } // namespace SL
 656 } // namespace GL
 657 } // namespace Msp