source/glsl/optimize.cpp

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