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