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