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