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 &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionDeclaration &src)
  72 {
  73         target_block = &tgt_blk;
  74         source_func = &src;
  75         for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
  76         {
  77                 r_inlined_statement = 0;
  78                 (*i)->visit(*this);
  79                 if(!r_inlined_statement)
  80                         r_inlined_statement = (*i)->clone();
  81
  82                 SetFlag set_remap(remap_names);
  83                 r_inlined_statement->visit(*this);
  84                 tgt_blk.body.insert(ins_pt, r_inlined_statement);
  85         }
  86
  87         NodeReorderer().apply(stage, target_func, dependencies);
  88
  89         return r_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                 r_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                 r_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 = r_result_name;
 172                 var->init_expression = ret.expression->clone();
 173                 r_inlined_statement = var;
 174         }
 175 }
 176
 177
 178 FunctionInliner::FunctionInliner():
 179         current_function(0),
 180         r_any_inlined(false)
 181 { }
 182
 183 bool FunctionInliner::apply(Stage &s)
 184 {
 185         stage = &s;
 186         inlineable = InlineableFunctionLocator().apply(s);
 187         r_any_inlined = false;
 188         s.content.visit(*this);
 189         return r_any_inlined;
 190 }
 191
 192 void FunctionInliner::visit_and_inline(RefPtr<Expression> &ptr)
 193 {
 194         r_inline_result = 0;
 195         ptr->visit(*this);
 196         if(r_inline_result)
 197         {
 198                 ptr = r_inline_result;
 199                 r_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         r_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         r_inline_result = 0;
 225 }
 226
 227 void FunctionInliner::visit(MemberAccess &memacc)
 228 {
 229         visit_and_inline(memacc.left);
 230         r_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                 r_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                 r_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         r_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         r_assignment(0),
 410         assignment_target(false),
 411         r_assign_to_subfield(false),
 412         r_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         r_assign_to_subfield = true;
 459         TraversingVisitor::visit(memacc);
 460         unused_nodes.erase(memacc.declaration);
 461 }
 462
 463 void UnusedVariableRemover::visit(UnaryExpression &unary)
 464 {
 465         TraversingVisitor::visit(unary);
 466         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 467                 r_side_effects = true;
 468 }
 469
 470 void UnusedVariableRemover::visit(BinaryExpression &binary)
 471 {
 472         if(binary.oper->token[0]=='[')
 473         {
 474                 if(assignment_target)
 475                         r_assign_to_subfield = true;
 476                 binary.left->visit(*this);
 477                 SetFlag set(assignment_target, false);
 478                 binary.right->visit(*this);
 479         }
 480         else
 481                 TraversingVisitor::visit(binary);
 482 }
 483
 484 void UnusedVariableRemover::visit(Assignment &assign)
 485 {
 486         {
 487                 SetFlag set(assignment_target, !assign.self_referencing);
 488                 assign.left->visit(*this);
 489         }
 490         assign.right->visit(*this);
 491         r_assignment = &assign;
 492         r_side_effects = true;
 493 }
 494
 495 void UnusedVariableRemover::visit(FunctionCall &call)
 496 {
 497         TraversingVisitor::visit(call);
 498         r_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         r_assignment = 0;
 523         r_assign_to_subfield = false;
 524         r_side_effects = false;
 525         TraversingVisitor::visit(expr);
 526         if(r_assignment && r_assignment->target_declaration)
 527                 record_assignment(*r_assignment->target_declaration, expr, (r_assignment->self_referencing || r_assign_to_subfield));
 528         if(!r_side_effects)
 529                 unused_nodes.insert(&expr);
 530 }
 531
 532 void UnusedVariableRemover::visit(StructDeclaration &strct)
 533 {
 534         SetForScope<Node *> set(aggregate, &strct);
 535         unused_nodes.insert(&strct);
 536         TraversingVisitor::visit(strct);
 537 }
 538
 539 void UnusedVariableRemover::visit(VariableDeclaration &var)
 540 {
 541         if(aggregate)
 542                 aggregates[&var] = aggregate;
 543         else
 544         {
 545                 variables.back()[&var].local = true;
 546                 if(var.init_expression)
 547                         record_assignment(var, *var.init_expression, false);
 548         }
 549         unused_nodes.erase(var.type_declaration);
 550         TraversingVisitor::visit(var);
 551 }
 552
 553 void UnusedVariableRemover::visit(InterfaceBlock &iface)
 554 {
 555         SetForScope<Node *> set(aggregate, &iface);
 556         unused_nodes.insert(&iface);
 557         TraversingVisitor::visit(iface);
 558 }
 559
 560 void UnusedVariableRemover::visit(FunctionDeclaration &func)
 561 {
 562         variables.push_back(BlockVariableMap());
 563
 564         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 565                 (*i)->visit(*this);
 566         func.body.visit(*this);
 567
 568         BlockVariableMap &block_variables = variables.back();
 569         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 570                 if(!i->second.local)
 571                         i->second.conditionally_assigned = true;
 572         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 573                 block_variables[i->get()].referenced = true;
 574         merge_down_variables();
 575 }
 576
 577 void UnusedVariableRemover::merge_down_variables()
 578 {
 579         BlockVariableMap &parent_variables = variables[variables.size()-2];
 580         BlockVariableMap &block_variables = variables.back();
 581         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 582         {
 583                 if(i->second.local)
 584                 {
 585                         if(!i->second.referenced)
 586                                 unused_nodes.insert(i->first);
 587                         clear_assignments(i->second, true);
 588                         continue;
 589                 }
 590
 591                 BlockVariableMap::iterator j = parent_variables.find(i->first);
 592                 if(j==parent_variables.end())
 593                         parent_variables.insert(*i);
 594                 else
 595                 {
 596                         if(i->second.referenced || !i->second.conditionally_assigned)
 597                                 clear_assignments(j->second, !i->second.referenced);
 598                         j->second.conditionally_assigned = i->second.conditionally_assigned;
 599                         j->second.referenced |= i->second.referenced;
 600                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end());
 601                 }
 602         }
 603         variables.pop_back();
 604 }
 605
 606 void UnusedVariableRemover::visit(Conditional &cond)
 607 {
 608         cond.condition->visit(*this);
 609         variables.push_back(BlockVariableMap());
 610         cond.body.visit(*this);
 611
 612         BlockVariableMap if_variables;
 613         swap(variables.back(), if_variables);
 614         cond.else_body.visit(*this);
 615
 616         BlockVariableMap &else_variables = variables.back();
 617         for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i)
 618         {
 619                 BlockVariableMap::iterator j = if_variables.find(i->first);
 620                 if(j!=if_variables.end())
 621                 {
 622                         i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end());
 623                         i->second.conditionally_assigned |= j->second.conditionally_assigned;
 624                         if_variables.erase(j);
 625                 }
 626                 else
 627                         i->second.conditionally_assigned = true;
 628         }
 629
 630         for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i)
 631         {
 632                 i->second.conditionally_assigned = true;
 633                 else_variables.insert(*i);
 634         }
 635
 636         merge_down_variables();
 637 }
 638
 639 void UnusedVariableRemover::visit(Iteration &iter)
 640 {
 641         variables.push_back(BlockVariableMap());
 642         TraversingVisitor::visit(iter);
 643         merge_down_variables();
 644 }
 645
 646
 647 bool UnusedFunctionRemover::apply(Stage &stage)
 648 {
 649         stage.content.visit(*this);
 650         NodeRemover().apply(stage, unused_nodes);
 651         return !unused_nodes.empty();
 652 }
 653
 654 void UnusedFunctionRemover::visit(FunctionCall &call)
 655 {
 656         TraversingVisitor::visit(call);
 657
 658         unused_nodes.erase(call.declaration);
 659         if(call.declaration && call.declaration->definition!=call.declaration)
 660                 used_definitions.insert(call.declaration->definition);
 661 }
 662
 663 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
 664 {
 665         TraversingVisitor::visit(func);
 666
 667         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 668                 unused_nodes.insert(&func);
 669 }
 670
 671 } // namespace SL
 672 } // namespace GL
 673 } // namespace Msp