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                 /* Don't inline functions which are called more than once or are called
  27                 recursively. */
  28                 if(count>1 || def==current_function)
  29                         inlineable.erase(def);
  30         }
  31
  32         TraversingVisitor::visit(call);
  33 }
  34
  35 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
  36 {
  37         unsigned &count = refcounts[func.definition];
  38         if(count<=1 && func.parameters.empty())
  39                 inlineable.insert(func.definition);
  40
  41         SetForScope<FunctionDeclaration *> set(current_function, &func);
  42         return_count = 0;
  43         TraversingVisitor::visit(func);
  44 }
  45
  46 void InlineableFunctionLocator::visit(Conditional &cond)
  47 {
  48         TraversingVisitor::visit(cond);
  49         inlineable.erase(current_function);
  50 }
  51
  52 void InlineableFunctionLocator::visit(Iteration &iter)
  53 {
  54         TraversingVisitor::visit(iter);
  55         inlineable.erase(current_function);
  56 }
  57
  58 void InlineableFunctionLocator::visit(Return &ret)
  59 {
  60         TraversingVisitor::visit(ret);
  61         if(return_count)
  62                 inlineable.erase(current_function);
  63         ++return_count;
  64 }
  65
  66
  67 InlineContentInjector::InlineContentInjector():
  68         source_func(0),
  69         remap_names(false),
  70         deps_only(false)
  71 { }
  72
  73 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionDeclaration &src)
  74 {
  75         target_block = &tgt_blk;
  76         source_func = &src;
  77         for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
  78         {
  79                 r_inlined_statement = 0;
  80                 (*i)->visit(*this);
  81                 if(!r_inlined_statement)
  82                         r_inlined_statement = (*i)->clone();
  83
  84                 SetFlag set_remap(remap_names);
  85                 r_inlined_statement->visit(*this);
  86                 tgt_blk.body.insert(ins_pt, r_inlined_statement);
  87         }
  88
  89         NodeReorderer().apply(stage, target_func, dependencies);
  90
  91         return r_result_name;
  92 }
  93
  94 string InlineContentInjector::create_unused_name(const string &base, bool always_prefix)
  95 {
  96         string result = base;
  97         if(always_prefix || target_block->variables.count(result))
  98                 result = format("_%s_%s", source_func->name, base);
  99         unsigned initial_size = result.size();
 100         for(unsigned i=1; target_block->variables.count(result); ++i)
 101         {
 102                 result.erase(initial_size);
 103                 result += format("_%d", i);
 104         }
 105         return result;
 106 }
 107
 108 void InlineContentInjector::visit(VariableReference &var)
 109 {
 110         if(remap_names)
 111         {
 112                 map<string, VariableDeclaration *>::const_iterator i = variable_map.find(var.name);
 113                 if(i!=variable_map.end())
 114                         var.name = i->second->name;
 115         }
 116         else if(var.declaration)
 117         {
 118                 SetFlag set_deps(deps_only);
 119                 dependencies.insert(var.declaration);
 120                 var.declaration->visit(*this);
 121         }
 122 }
 123
 124 void InlineContentInjector::visit(InterfaceBlockReference &iface)
 125 {
 126         if(!remap_names && iface.declaration)
 127         {
 128                 SetFlag set_deps(deps_only);
 129                 dependencies.insert(iface.declaration);
 130                 iface.declaration->visit(*this);
 131         }
 132 }
 133
 134 void InlineContentInjector::visit(FunctionCall &call)
 135 {
 136         if(!remap_names && call.declaration)
 137                 dependencies.insert(call.declaration);
 138         TraversingVisitor::visit(call);
 139 }
 140
 141 void InlineContentInjector::visit(VariableDeclaration &var)
 142 {
 143         TraversingVisitor::visit(var);
 144
 145         if(var.type_declaration)
 146         {
 147                 SetFlag set_deps(deps_only);
 148                 dependencies.insert(var.type_declaration);
 149                 var.type_declaration->visit(*this);
 150         }
 151
 152         if(!remap_names && !deps_only)
 153         {
 154                 RefPtr<VariableDeclaration> inlined_var = var.clone();
 155                 inlined_var->name = create_unused_name(var.name, false);
 156                 r_inlined_statement = inlined_var;
 157
 158                 variable_map[var.name] = inlined_var.get();
 159         }
 160 }
 161
 162 void InlineContentInjector::visit(Return &ret)
 163 {
 164         TraversingVisitor::visit(ret);
 165
 166         if(ret.expression)
 167         {
 168                 /* Create a new variable to hold the return value of the inlined
 169                 function. */
 170                 r_result_name = create_unused_name("return", true);
 171                 RefPtr<VariableDeclaration> var = new VariableDeclaration;
 172                 var->source = ret.source;
 173                 var->line = ret.line;
 174                 var->type = source_func->return_type;
 175                 var->name = r_result_name;
 176                 var->init_expression = ret.expression->clone();
 177                 r_inlined_statement = var;
 178         }
 179 }
 180
 181
 182 FunctionInliner::FunctionInliner():
 183         current_function(0),
 184         r_any_inlined(false)
 185 { }
 186
 187 bool FunctionInliner::apply(Stage &s)
 188 {
 189         stage = &s;
 190         inlineable = InlineableFunctionLocator().apply(s);
 191         r_any_inlined = false;
 192         s.content.visit(*this);
 193         return r_any_inlined;
 194 }
 195
 196 void FunctionInliner::visit(RefPtr<Expression> &ptr)
 197 {
 198         r_inline_result = 0;
 199         ptr->visit(*this);
 200         if(r_inline_result)
 201         {
 202                 ptr = r_inline_result;
 203                 r_any_inlined = true;
 204         }
 205         r_inline_result = 0;
 206 }
 207
 208 void FunctionInliner::visit(Block &block)
 209 {
 210         SetForScope<Block *> set_block(current_block, &block);
 211         SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
 212         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 213         {
 214                 insert_point = i;
 215                 (*i)->visit(*this);
 216         }
 217 }
 218
 219 void FunctionInliner::visit(FunctionCall &call)
 220 {
 221         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 222                 visit(*i);
 223
 224         FunctionDeclaration *def = call.declaration;
 225         if(def)
 226                 def = def->definition;
 227
 228         if(def && inlineable.count(def))
 229         {
 230                 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
 231
 232                 // This will later get removed by UnusedVariableRemover.
 233                 if(result_name.empty())
 234                         result_name = "msp_unused_from_inline";
 235
 236                 RefPtr<VariableReference> ref = new VariableReference;
 237                 ref->name = result_name;
 238                 r_inline_result = ref;
 239
 240                 /* Inlined variables need to be resolved before this function can be
 241                 inlined further. */
 242                 inlineable.erase(current_function);
 243         }
 244 }
 245
 246 void FunctionInliner::visit(FunctionDeclaration &func)
 247 {
 248         SetForScope<FunctionDeclaration *> set_func(current_function, &func);
 249         TraversingVisitor::visit(func);
 250 }
 251
 252 void FunctionInliner::visit(Iteration &iter)
 253 {
 254         /* Visit the initialization statement before entering the loop body so the
 255         inlined statements get inserted outside. */
 256         if(iter.init_statement)
 257                 iter.init_statement->visit(*this);
 258
 259         SetForScope<Block *> set_block(current_block, &iter.body);
 260         /* Skip the condition and loop expression parts because they're not properly
 261         inside the body block.  Inlining anything into them will require a more
 262         comprehensive transformation. */
 263         iter.body.visit(*this);
 264 }
 265
 266
 267 ExpressionInliner::ExpressionInfo::ExpressionInfo():
 268         expression(0),
 269         assign_scope(0),
 270         inline_point(0),
 271         trivial(false),
 272         available(true)
 273 { }
 274
 275
 276 ExpressionInliner::ExpressionInliner():
 277         r_ref_info(0),
 278         r_any_inlined(false),
 279         r_trivial(false),
 280         mutating(false),
 281         iteration_init(false),
 282         iteration_body(0),
 283         r_oper(0)
 284 { }
 285
 286 bool ExpressionInliner::apply(Stage &s)
 287 {
 288         s.content.visit(*this);
 289         return r_any_inlined;
 290 }
 291
 292 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
 293 {
 294         ptr = expr.clone();
 295         r_any_inlined = true;
 296 }
 297
 298 void ExpressionInliner::visit(Block &block)
 299 {
 300         TraversingVisitor::visit(block);
 301
 302         for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 303         {
 304                 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
 305                 for(; (j!=expressions.end() && j->first.declaration==i->second); )
 306                 {
 307                         if(j->second.expression && j->second.inline_point)
 308                                 inline_expression(*j->second.expression, *j->second.inline_point);
 309
 310                         expressions.erase(j++);
 311                 }
 312         }
 313
 314         /* Expressions assigned in this block may depend on local variables of the
 315         block.  If this is a conditionally executed block, the assignments might not
 316         always happen.  Mark the expressions as not available to any outer blocks. */
 317         for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
 318                 if(i->second.assign_scope==&block)
 319                         i->second.available = false;
 320 }
 321
 322 void ExpressionInliner::visit(RefPtr<Expression> &expr)
 323 {
 324         r_ref_info = 0;
 325         expr->visit(*this);
 326         if(r_ref_info && r_ref_info->expression && r_ref_info->available)
 327         {
 328                 if(iteration_body && !r_ref_info->trivial)
 329                 {
 330                         /* Don't inline non-trivial expressions which were assigned outside
 331                         an iteration statement.  The iteration may run multiple times, which
 332                         would cause the expression to also be evaluated multiple times. */
 333                         Block *i = r_ref_info->assign_scope;
 334                         for(; (i && i!=iteration_body); i=i->parent) ;
 335                         if(!i)
 336                                 return;
 337                 }
 338
 339                 if(r_ref_info->trivial)
 340                         inline_expression(*r_ref_info->expression, expr);
 341                 else
 342                         /* Record the inline point for a non-trivial expression but don't
 343                         inline it yet.  It might turn out it shouldn't be inlined after all. */
 344                         r_ref_info->inline_point = &expr;
 345         }
 346         r_oper = expr->oper;
 347         r_ref_info = 0;
 348 }
 349
 350 void ExpressionInliner::visit(VariableReference &var)
 351 {
 352         if(var.declaration)
 353         {
 354                 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
 355                 if(i!=expressions.end())
 356                 {
 357                         /* If a non-trivial expression is referenced multiple times, don't
 358                         inline it. */
 359                         if(i->second.inline_point && !i->second.trivial)
 360                                 i->second.expression = 0;
 361                         /* Mutating expressions are analogous to self-referencing assignments
 362                         and prevent inlining. */
 363                         if(mutating)
 364                                 i->second.expression = 0;
 365                         r_ref_info = &i->second;
 366                 }
 367         }
 368 }
 369
 370 void ExpressionInliner::visit(MemberAccess &memacc)
 371 {
 372         visit(memacc.left);
 373         r_trivial = false;
 374 }
 375
 376 void ExpressionInliner::visit(Swizzle &swizzle)
 377 {
 378         visit(swizzle.left);
 379         r_trivial = false;
 380 }
 381
 382 void ExpressionInliner::visit(UnaryExpression &unary)
 383 {
 384         SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
 385         visit(unary.expression);
 386         r_trivial = false;
 387 }
 388
 389 void ExpressionInliner::visit(BinaryExpression &binary)
 390 {
 391         visit(binary.left);
 392         {
 393                 SetFlag clear_target(mutating, false);
 394                 visit(binary.right);
 395         }
 396         r_trivial = false;
 397 }
 398
 399 void ExpressionInliner::visit(Assignment &assign)
 400 {
 401         {
 402                 SetFlag set_target(mutating);
 403                 visit(assign.left);
 404         }
 405         r_oper = 0;
 406         visit(assign.right);
 407
 408         map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
 409         if(i!=expressions.end())
 410         {
 411                 /* Self-referencing assignments can't be inlined without additional
 412                 work.  Just clear any previous expression. */
 413                 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
 414                 i->second.assign_scope = current_block;
 415                 i->second.inline_point = 0;
 416                 i->second.available = true;
 417         }
 418
 419         r_trivial = false;
 420 }
 421
 422 void ExpressionInliner::visit(TernaryExpression &ternary)
 423 {
 424         visit(ternary.condition);
 425         visit(ternary.true_expr);
 426         visit(ternary.false_expr);
 427         r_trivial = false;
 428 }
 429
 430 void ExpressionInliner::visit(FunctionCall &call)
 431 {
 432         TraversingVisitor::visit(call);
 433         r_trivial = false;
 434 }
 435
 436 void ExpressionInliner::visit(VariableDeclaration &var)
 437 {
 438         r_oper = 0;
 439         r_trivial = true;
 440         TraversingVisitor::visit(var);
 441
 442         bool constant = var.constant;
 443         if(constant && var.layout)
 444         {
 445                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 446                         constant = (i->name!="constant_id");
 447         }
 448
 449         /* Only inline global variables if they're constant and have trivial
 450         initializers.  Non-constant variables could change in ways which are hard to
 451         analyze and non-trivial expressions could be expensive to inline.  */
 452         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 453         {
 454                 ExpressionInfo &info = expressions[&var];
 455                 /* Assume variables declared in an iteration initialization statement
 456                 will have their values change throughout the iteration. */
 457                 info.expression = (iteration_init ? 0 : var.init_expression.get());
 458                 info.assign_scope = current_block;
 459                 info.trivial = r_trivial;
 460         }
 461 }
 462
 463 void ExpressionInliner::visit(Iteration &iter)
 464 {
 465         SetForScope<Block *> set_block(current_block, &iter.body);
 466         if(iter.init_statement)
 467         {
 468                 SetFlag set_init(iteration_init);
 469                 iter.init_statement->visit(*this);
 470         }
 471
 472         SetForScope<Block *> set_body(iteration_body, &iter.body);
 473         if(iter.condition)
 474                 visit(iter.condition);
 475         iter.body.visit(*this);
 476         if(iter.loop_expression)
 477                 visit(iter.loop_expression);
 478 }
 479
 480
 481 void ConstantConditionEliminator::apply(Stage &stage)
 482 {
 483         stage.content.visit(*this);
 484         NodeRemover().apply(stage, nodes_to_remove);
 485 }
 486
 487 void ConstantConditionEliminator::visit(Block &block)
 488 {
 489         SetForScope<Block *> set_block(current_block, &block);
 490         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 491         {
 492                 insert_point = i;
 493                 (*i)->visit(*this);
 494         }
 495 }
 496
 497 void ConstantConditionEliminator::visit(Conditional &cond)
 498 {
 499         if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
 500                 if(literal->value.check_type<bool>())
 501                 {
 502                         Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
 503                         current_block->body.splice(insert_point, block.body);
 504                         nodes_to_remove.insert(&cond);
 505                         return;
 506                 }
 507
 508         TraversingVisitor::visit(cond);
 509 }
 510
 511 void ConstantConditionEliminator::visit(Iteration &iter)
 512 {
 513         if(iter.condition)
 514         {
 515                 /* If the loop condition is always false on the first iteration, the
 516                 entire loop can be removed */
 517                 ExpressionEvaluator::ValueMap values;
 518                 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
 519                         values[var] = var->init_expression.get();
 520                 ExpressionEvaluator eval(values);
 521                 iter.condition->visit(eval);
 522                 if(eval.is_result_valid() && !eval.get_result())
 523                 {
 524                         nodes_to_remove.insert(&iter);
 525                         return;
 526                 }
 527         }
 528
 529         TraversingVisitor::visit(iter);
 530 }
 531
 532
 533 bool UnusedTypeRemover::apply(Stage &stage)
 534 {
 535         stage.content.visit(*this);
 536         NodeRemover().apply(stage, unused_nodes);
 537         return !unused_nodes.empty();
 538 }
 539
 540 void UnusedTypeRemover::visit(Literal &literal)
 541 {
 542         unused_nodes.erase(literal.type);
 543 }
 544
 545 void UnusedTypeRemover::visit(UnaryExpression &unary)
 546 {
 547         unused_nodes.erase(unary.type);
 548         TraversingVisitor::visit(unary);
 549 }
 550
 551 void UnusedTypeRemover::visit(BinaryExpression &binary)
 552 {
 553         unused_nodes.erase(binary.type);
 554         TraversingVisitor::visit(binary);
 555 }
 556
 557 void UnusedTypeRemover::visit(TernaryExpression &ternary)
 558 {
 559         unused_nodes.erase(ternary.type);
 560         TraversingVisitor::visit(ternary);
 561 }
 562
 563 void UnusedTypeRemover::visit(FunctionCall &call)
 564 {
 565         unused_nodes.erase(call.type);
 566         TraversingVisitor::visit(call);
 567 }
 568
 569 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 570 {
 571         if(type.base_type)
 572                 unused_nodes.erase(type.base_type);
 573         unused_nodes.insert(&type);
 574 }
 575
 576 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 577 {
 578         if(type.base_type)
 579                 unused_nodes.erase(type.base_type);
 580         unused_nodes.insert(&type);
 581 }
 582
 583 void UnusedTypeRemover::visit(StructDeclaration &strct)
 584 {
 585         unused_nodes.insert(&strct);
 586         TraversingVisitor::visit(strct);
 587 }
 588
 589 void UnusedTypeRemover::visit(VariableDeclaration &var)
 590 {
 591         unused_nodes.erase(var.type_declaration);
 592 }
 593
 594 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 595 {
 596         unused_nodes.erase(iface.type_declaration);
 597 }
 598
 599 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 600 {
 601         unused_nodes.erase(func.return_type_declaration);
 602         TraversingVisitor::visit(func);
 603 }
 604
 605
 606 UnusedVariableRemover::UnusedVariableRemover():
 607         stage(0),
 608         interface_block(0),
 609         r_assignment(0),
 610         assignment_target(false),
 611         r_side_effects(false)
 612 { }
 613
 614 bool UnusedVariableRemover::apply(Stage &s)
 615 {
 616         stage = &s;
 617         s.content.visit(*this);
 618
 619         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
 620                 if(i->used_by.empty())
 621                         unused_nodes.insert(i->node);
 622
 623         for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
 624                 if(i->second->instance_name.empty())
 625                         unused_nodes.insert(i->second);
 626
 627         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 628         {
 629                 if(i->second.output)
 630                 {
 631                         /* The last visible assignments of output variables are used by the
 632                         next stage or the API. */
 633                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
 634                                 unused_nodes.erase((*j)->node);
 635                 }
 636
 637                 if(!i->second.output && !i->second.referenced)
 638                 {
 639                         // Don't remove variables from inside interface blocks.
 640                         if(!i->second.interface_block)
 641                                 unused_nodes.insert(i->first);
 642                 }
 643                 else if(i->second.interface_block)
 644                         // Interface blocks are kept if even one member is used.
 645                         unused_nodes.erase(i->second.interface_block);
 646         }
 647
 648         NodeRemover().apply(s, unused_nodes);
 649
 650         return !unused_nodes.empty();
 651 }
 652
 653 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
 654 {
 655         VariableInfo &var_info = variables[target.declaration];
 656         var_info.referenced = true;
 657         if(!assignment_target)
 658         {
 659                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 660                         (*i)->used_by.push_back(&node);
 661         }
 662 }
 663
 664 void UnusedVariableRemover::visit(VariableReference &var)
 665 {
 666         referenced(var.declaration, var);
 667 }
 668
 669 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 670 {
 671         referenced(iface.declaration, iface);
 672 }
 673
 674 void UnusedVariableRemover::visit(UnaryExpression &unary)
 675 {
 676         TraversingVisitor::visit(unary);
 677         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 678                 r_side_effects = true;
 679 }
 680
 681 void UnusedVariableRemover::visit(BinaryExpression &binary)
 682 {
 683         if(binary.oper->token[0]=='[')
 684         {
 685                 binary.left->visit(*this);
 686                 SetFlag set(assignment_target, false);
 687                 binary.right->visit(*this);
 688         }
 689         else
 690                 TraversingVisitor::visit(binary);
 691 }
 692
 693 void UnusedVariableRemover::visit(Assignment &assign)
 694 {
 695         {
 696                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
 697                 assign.left->visit(*this);
 698         }
 699         assign.right->visit(*this);
 700         r_assignment = &assign;
 701         r_side_effects = true;
 702 }
 703
 704 void UnusedVariableRemover::visit(FunctionCall &call)
 705 {
 706         TraversingVisitor::visit(call);
 707         /* Treat function calls as having side effects so expression statements
 708         consisting of nothing but a function call won't be optimized away. */
 709         r_side_effects = true;
 710
 711         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
 712         {
 713                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 714                         if(i->second.output)
 715                                 referenced(i->first, call);
 716         }
 717 }
 718
 719 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
 720 {
 721         assignments.push_back(AssignmentInfo());
 722         AssignmentInfo &assign_info = assignments.back();
 723         assign_info.node = &node;
 724         assign_info.target = target;
 725
 726         /* An assignment to the target hides any assignments to the same target or
 727         its subfields. */
 728         VariableInfo &var_info = variables[target.declaration];
 729         for(unsigned i=0; i<var_info.assignments.size(); ++i)
 730         {
 731                 const Assignment::Target &t = var_info.assignments[i]->target;
 732
 733                 bool subfield = (t.chain_len>=target.chain_len);
 734                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
 735                         subfield = (t.chain[j]==target.chain[j]);
 736
 737                 if(subfield)
 738                         var_info.assignments.erase(var_info.assignments.begin()+i);
 739                 else
 740                         ++i;
 741         }
 742
 743         var_info.assignments.push_back(&assign_info);
 744 }
 745
 746 void UnusedVariableRemover::visit(ExpressionStatement &expr)
 747 {
 748         r_assignment = 0;
 749         r_side_effects = false;
 750         TraversingVisitor::visit(expr);
 751         if(r_assignment && r_assignment->target.declaration)
 752                 record_assignment(r_assignment->target, expr);
 753         if(!r_side_effects)
 754                 unused_nodes.insert(&expr);
 755 }
 756
 757 void UnusedVariableRemover::visit(VariableDeclaration &var)
 758 {
 759         VariableInfo &var_info = variables[&var];
 760         var_info.interface_block = interface_block;
 761
 762         /* Mark variables as output if they're used by the next stage or the
 763         graphics API. */
 764         if(interface_block)
 765                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
 766         else
 767                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
 768
 769         if(var.init_expression)
 770         {
 771                 var_info.initialized = true;
 772                 record_assignment(&var, *var.init_expression);
 773         }
 774         TraversingVisitor::visit(var);
 775 }
 776
 777 void UnusedVariableRemover::visit(InterfaceBlock &iface)
 778 {
 779         if(iface.instance_name.empty())
 780         {
 781                 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
 782                 iface.struct_declaration->members.visit(*this);
 783         }
 784         else
 785         {
 786                 VariableInfo &var_info = variables[&iface];
 787                 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
 788         }
 789 }
 790
 791 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
 792 {
 793         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
 794         {
 795                 BlockVariableMap::iterator j = variables.find(i->first);
 796                 if(j!=variables.end())
 797                 {
 798                         /* The merged blocks started as copies of each other so any common
 799                         assignments must be in the beginning. */
 800                         unsigned k = 0;
 801                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
 802                                 if(i->second.assignments[k]!=j->second.assignments[k])
 803                                         break;
 804
 805                         // Remaining assignments are unique to each block; merge them.
 806                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
 807                         j->second.referenced |= i->second.referenced;
 808                 }
 809                 else
 810                         variables.insert(*i);
 811         }
 812 }
 813
 814 void UnusedVariableRemover::visit(FunctionDeclaration &func)
 815 {
 816         if(func.body.body.empty())
 817                 return;
 818
 819         BlockVariableMap saved_vars = variables;
 820         // Assignments from other functions should not be visible.
 821         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
 822                 i->second.assignments.resize(i->second.initialized);
 823         TraversingVisitor::visit(func);
 824         swap(variables, saved_vars);
 825         merge_variables(saved_vars);
 826
 827         /* Always treat function parameters as referenced.  Removing unused
 828         parameters is not currently supported. */
 829         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 830         {
 831                 BlockVariableMap::iterator j = variables.find(i->get());
 832                 if(j!=variables.end())
 833                         j->second.referenced = true;
 834         }
 835 }
 836
 837 void UnusedVariableRemover::visit(Conditional &cond)
 838 {
 839         cond.condition->visit(*this);
 840         BlockVariableMap saved_vars = variables;
 841         cond.body.visit(*this);
 842         swap(saved_vars, variables);
 843         cond.else_body.visit(*this);
 844
 845         /* Visible assignments after the conditional is the union of those visible
 846         at the end of the if and else blocks.  If there was no else block, then it's
 847         the union of the if block and the state before it. */
 848         merge_variables(saved_vars);
 849 }
 850
 851 void UnusedVariableRemover::visit(Iteration &iter)
 852 {
 853         BlockVariableMap saved_vars = variables;
 854         TraversingVisitor::visit(iter);
 855
 856         /* Merge assignments from the iteration, without clearing previous state.
 857         Further analysis is needed to determine which parts of the iteration body
 858         are always executed, if any. */
 859         merge_variables(saved_vars);
 860 }
 861
 862
 863 bool UnusedFunctionRemover::apply(Stage &stage)
 864 {
 865         stage.content.visit(*this);
 866         NodeRemover().apply(stage, unused_nodes);
 867         return !unused_nodes.empty();
 868 }
 869
 870 void UnusedFunctionRemover::visit(FunctionCall &call)
 871 {
 872         TraversingVisitor::visit(call);
 873
 874         unused_nodes.erase(call.declaration);
 875         if(call.declaration && call.declaration->definition!=call.declaration)
 876                 used_definitions.insert(call.declaration->definition);
 877 }
 878
 879 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
 880 {
 881         TraversingVisitor::visit(func);
 882
 883         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 884                 unused_nodes.insert(&func);
 885 }
 886
 887 } // namespace SL
 888 } // namespace GL
 889 } // namespace Msp