source/glsl/optimize.cpp

   1 #include <msp/core/algorithm.h>
   2 #include <msp/core/raii.h>
   3 #include <msp/strings/format.h>
   4 #include <msp/strings/utils.h>
   5 #include "optimize.h"
   6 #include "reflect.h"
   7
   8 using namespace std;
   9
  10 namespace Msp {
  11 namespace GL {
  12 namespace SL {
  13
  14 void ConstantSpecializer::apply(Stage &stage, const map<string, int> &v)
  15 {
  16         values = &v;
  17         stage.content.visit(*this);
  18 }
  19
  20 void ConstantSpecializer::visit(VariableDeclaration &var)
  21 {
  22         bool specializable = false;
  23         if(var.layout)
  24         {
  25                 vector<Layout::Qualifier> &qualifiers = var.layout->qualifiers;
  26                 auto i = find_member(qualifiers, string("constant_id"), &Layout::Qualifier::name);
  27                 if(i!=qualifiers.end())
  28                 {
  29                         specializable = true;
  30                         qualifiers.erase(i);
  31                         if(qualifiers.empty())
  32                                 var.layout = 0;
  33                 }
  34         }
  35
  36         if(specializable)
  37         {
  38                 auto i = values->find(var.name);
  39                 if(i!=values->end())
  40                 {
  41                         RefPtr<Literal> literal = new Literal;
  42                         if(var.type=="bool")
  43                         {
  44                                 literal->token = (i->second ? "true" : "false");
  45                                 literal->value = static_cast<bool>(i->second);
  46                         }
  47                         else if(var.type=="int")
  48                         {
  49                                 literal->token = lexical_cast<string>(i->second);
  50                                 literal->value = i->second;
  51                         }
  52                         var.init_expression = literal;
  53                 }
  54         }
  55 }
  56
  57
  58 void InlineableFunctionLocator::visit(FunctionCall &call)
  59 {
  60         FunctionDeclaration *def = call.declaration;
  61         if(def)
  62                 def = def->definition;
  63
  64         if(def)
  65         {
  66                 unsigned &count = refcounts[def];
  67                 ++count;
  68                 /* Don't inline functions which are called more than once or are called
  69                 recursively. */
  70                 if((count>1 && def->source!=BUILTIN_SOURCE) || def==current_function)
  71                         inlineable.erase(def);
  72         }
  73
  74         TraversingVisitor::visit(call);
  75 }
  76
  77 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
  78 {
  79         bool has_out_params = any_of(func.parameters.begin(), func.parameters.end(),
  80                 [](const RefPtr<VariableDeclaration> &p){ return p->interface=="out"; });
  81
  82         unsigned &count = refcounts[func.definition];
  83         if((count<=1 || func.source==BUILTIN_SOURCE) && !has_out_params)
  84                 inlineable.insert(func.definition);
  85
  86         SetForScope<FunctionDeclaration *> set(current_function, &func);
  87         return_count = 0;
  88         TraversingVisitor::visit(func);
  89 }
  90
  91 void InlineableFunctionLocator::visit(Conditional &cond)
  92 {
  93         TraversingVisitor::visit(cond);
  94         inlineable.erase(current_function);
  95 }
  96
  97 void InlineableFunctionLocator::visit(Iteration &iter)
  98 {
  99         TraversingVisitor::visit(iter);
 100         inlineable.erase(current_function);
 101 }
 102
 103 void InlineableFunctionLocator::visit(Return &ret)
 104 {
 105         TraversingVisitor::visit(ret);
 106         if(return_count)
 107                 inlineable.erase(current_function);
 108         ++return_count;
 109 }
 110
 111
 112 string InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionCall &call)
 113 {
 114         source_func = call.declaration->definition;
 115
 116         /* Populate referenced_names from the target function so we can rename
 117         variables from the inlined function that would conflict. */
 118         pass = REFERENCED;
 119         target_func.visit(*this);
 120
 121         /* Inline and rename passes must be interleaved so used variable names are
 122         known when inlining the return statement. */
 123         pass = INLINE;
 124         staging_block.parent = &tgt_blk;
 125         staging_block.variables.clear();
 126
 127         vector<RefPtr<VariableDeclaration> > params;
 128         params.reserve(source_func->parameters.size());
 129         for(const RefPtr<VariableDeclaration> &p: source_func->parameters)
 130         {
 131                 RefPtr<VariableDeclaration> var = p->clone();
 132                 var->interface.clear();
 133
 134                 SetForScope<Pass> set_pass(pass, RENAME);
 135                 var->visit(*this);
 136
 137                 staging_block.body.push_back_nocopy(var);
 138                 params.push_back(var);
 139         }
 140
 141         for(const RefPtr<Statement> &s: source_func->body.body)
 142         {
 143                 r_inlined_statement = 0;
 144                 s->visit(*this);
 145                 if(!r_inlined_statement)
 146                         r_inlined_statement = s->clone();
 147
 148                 SetForScope<Pass> set_pass(pass, RENAME);
 149                 r_inlined_statement->visit(*this);
 150
 151                 staging_block.body.push_back_nocopy(r_inlined_statement);
 152         }
 153
 154         /* Now collect names from the staging block.  Local variables that would
 155         have conflicted with the target function were renamed earlier. */
 156         pass = REFERENCED;
 157         referenced_names.clear();
 158         staging_block.variables.clear();
 159         staging_block.visit(*this);
 160
 161         /* Rename variables in the target function so they don't interfere with
 162         global identifiers used by the source function. */
 163         pass = RENAME;
 164         staging_block.parent = source_func->body.parent;
 165         target_func.visit(*this);
 166
 167         // Put the argument expressions in place after all renaming has been done.
 168         for(unsigned i=0; i<source_func->parameters.size(); ++i)
 169                 params[i]->init_expression = call.arguments[i]->clone();
 170
 171         tgt_blk.body.splice(ins_pt, staging_block.body);
 172
 173         NodeReorderer().apply(stage, target_func, DependencyCollector().apply(*source_func));
 174
 175         return r_result_name;
 176 }
 177
 178 void InlineContentInjector::visit(VariableReference &var)
 179 {
 180         if(pass==RENAME)
 181         {
 182                 auto i = staging_block.variables.find(var.name);
 183                 if(i!=staging_block.variables.end())
 184                         var.name = i->second->name;
 185         }
 186         else if(pass==REFERENCED)
 187                 referenced_names.insert(var.name);
 188 }
 189
 190 void InlineContentInjector::visit(InterfaceBlockReference &iface)
 191 {
 192         if(pass==REFERENCED)
 193                 referenced_names.insert(iface.name);
 194 }
 195
 196 void InlineContentInjector::visit(FunctionCall &call)
 197 {
 198         if(pass==REFERENCED)
 199                 referenced_names.insert(call.name);
 200         TraversingVisitor::visit(call);
 201 }
 202
 203 void InlineContentInjector::visit(VariableDeclaration &var)
 204 {
 205         TraversingVisitor::visit(var);
 206
 207         if(pass==RENAME)
 208         {
 209                 /* Check against conflicts with the other context as well as variables
 210                 already renamed here. */
 211                 bool conflict = (staging_block.variables.count(var.name) || referenced_names.count(var.name));
 212                 staging_block.variables[var.name] = &var;
 213                 if(conflict)
 214                 {
 215                         string mapped_name = get_unused_variable_name(staging_block, var.name);
 216                         if(mapped_name!=var.name)
 217                         {
 218                                 staging_block.variables[mapped_name] = &var;
 219                                 var.name = mapped_name;
 220                         }
 221                 }
 222         }
 223         else if(pass==REFERENCED)
 224                 referenced_names.insert(var.type);
 225 }
 226
 227 void InlineContentInjector::visit(Return &ret)
 228 {
 229         TraversingVisitor::visit(ret);
 230
 231         if(pass==INLINE && ret.expression)
 232         {
 233                 // Create a new variable to hold the return value of the inlined function.
 234                 r_result_name = get_unused_variable_name(staging_block, "_return");
 235                 RefPtr<VariableDeclaration> var = new VariableDeclaration;
 236                 var->source = ret.source;
 237                 var->line = ret.line;
 238                 var->type = source_func->return_type;
 239                 var->name = r_result_name;
 240                 var->init_expression = ret.expression->clone();
 241                 r_inlined_statement = var;
 242         }
 243 }
 244
 245
 246 bool FunctionInliner::apply(Stage &s)
 247 {
 248         stage = &s;
 249         inlineable = InlineableFunctionLocator().apply(s);
 250         r_any_inlined = false;
 251         s.content.visit(*this);
 252         return r_any_inlined;
 253 }
 254
 255 void FunctionInliner::visit(RefPtr<Expression> &ptr)
 256 {
 257         r_inline_result = 0;
 258         ptr->visit(*this);
 259         if(r_inline_result)
 260         {
 261                 ptr = r_inline_result;
 262                 r_any_inlined = true;
 263         }
 264         r_inline_result = 0;
 265 }
 266
 267 void FunctionInliner::visit(Block &block)
 268 {
 269         SetForScope<Block *> set_block(current_block, &block);
 270         SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
 271         for(auto i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
 272         {
 273                 insert_point = i;
 274                 (*i)->visit(*this);
 275         }
 276 }
 277
 278 void FunctionInliner::visit(FunctionCall &call)
 279 {
 280         for(auto i=call.arguments.begin(); (!r_inlined_here && i!=call.arguments.end()); ++i)
 281                 visit(*i);
 282
 283         if(r_inlined_here)
 284                 return;
 285
 286         FunctionDeclaration *def = call.declaration;
 287         if(def)
 288                 def = def->definition;
 289
 290         if(def && inlineable.count(def))
 291         {
 292                 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, call);
 293
 294                 // This will later get removed by UnusedVariableRemover.
 295                 if(result_name.empty())
 296                         result_name = "_msp_unused_from_inline";
 297
 298                 RefPtr<VariableReference> ref = new VariableReference;
 299                 ref->name = result_name;
 300                 r_inline_result = ref;
 301
 302                 /* Inlined variables need to be resolved before this function can be
 303                 inlined further. */
 304                 inlineable.erase(current_function);
 305                 r_inlined_here = true;
 306         }
 307 }
 308
 309 void FunctionInliner::visit(FunctionDeclaration &func)
 310 {
 311         SetForScope<FunctionDeclaration *> set_func(current_function, &func);
 312         TraversingVisitor::visit(func);
 313         r_inlined_here = false;
 314 }
 315
 316 void FunctionInliner::visit(Iteration &iter)
 317 {
 318         /* Visit the initialization statement before entering the loop body so the
 319         inlined statements get inserted outside. */
 320         if(iter.init_statement)
 321                 iter.init_statement->visit(*this);
 322
 323         SetForScope<Block *> set_block(current_block, &iter.body);
 324         /* Skip the condition and loop expression parts because they're not properly
 325         inside the body block.  Inlining anything into them will require a more
 326         comprehensive transformation. */
 327         iter.body.visit(*this);
 328 }
 329
 330
 331 bool ExpressionInliner::apply(Stage &s)
 332 {
 333         s.content.visit(*this);
 334
 335         bool any_inlined = false;
 336         for(ExpressionInfo &e: expressions)
 337                 if(e.expression && (e.trivial || e.uses.size()==1))
 338                 {
 339                         for(ExpressionUse &u: e.uses)
 340                                 if(!u.blocked)
 341                                 {
 342                                         *u.reference = e.expression->clone();
 343                                         any_inlined = true;
 344                                 }
 345                 }
 346
 347         return any_inlined;
 348 }
 349
 350 void ExpressionInliner::visit(RefPtr<Expression> &expr)
 351 {
 352         r_ref_info = 0;
 353         expr->visit(*this);
 354         if(r_ref_info && r_ref_info->expression)
 355         {
 356                 ExpressionUse use;
 357                 use.reference = &expr;
 358                 use.ref_scope = current_block;
 359                 use.blocked = access_write;
 360
 361                 if(iteration_body && !r_ref_info->trivial)
 362                 {
 363                         /* Block inlining of non-trivial expressions assigned outside an
 364                         iteration statement.  The iteration may run multiple times, which
 365                         would cause the expression to also be evaluated multiple times. */
 366                         for(Block *i=iteration_body->parent; (!use.blocked && i); i=i->parent)
 367                                 use.blocked = (i==r_ref_info->assign_scope);
 368                 }
 369
 370                 /* Block inlining assignments from from inner scopes.  The assignment may
 371                 depend on local variables of that scope or may not always be executed. */
 372                 for(Block *i=r_ref_info->assign_scope->parent; (!use.blocked && i); i=i->parent)
 373                         use.blocked = (i==current_block);
 374
 375                 r_ref_info->uses.push_back(use);
 376         }
 377         r_oper = expr->oper;
 378         r_ref_info = 0;
 379 }
 380
 381 void ExpressionInliner::visit(VariableReference &var)
 382 {
 383         if(var.declaration && access_read)
 384         {
 385                 auto i = assignments.find(var.declaration);
 386                 if(i!=assignments.end())
 387                         r_ref_info = i->second;
 388         }
 389 }
 390
 391 void ExpressionInliner::visit(MemberAccess &memacc)
 392 {
 393         visit(memacc.left);
 394         r_trivial = false;
 395 }
 396
 397 void ExpressionInliner::visit(Swizzle &swizzle)
 398 {
 399         visit(swizzle.left);
 400         r_trivial = false;
 401 }
 402
 403 void ExpressionInliner::visit(UnaryExpression &unary)
 404 {
 405         SetFlag set_write(access_write, access_write || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
 406         visit(unary.expression);
 407         r_trivial = false;
 408 }
 409
 410 void ExpressionInliner::visit(BinaryExpression &binary)
 411 {
 412         visit(binary.left);
 413         {
 414                 SetFlag clear_write(access_write, false);
 415                 visit(binary.right);
 416         }
 417         r_trivial = false;
 418 }
 419
 420 void ExpressionInliner::visit(Assignment &assign)
 421 {
 422         {
 423                 SetFlag set_read(access_read, assign.oper->token[0]!='=');
 424                 SetFlag set_write(access_write);
 425                 visit(assign.left);
 426         }
 427         r_oper = 0;
 428         r_trivial = true;
 429         visit(assign.right);
 430
 431         auto i = assignments.find(assign.target);
 432         if(i!=assignments.end())
 433         {
 434                 if(iteration_body && i->second->expression)
 435                 {
 436                         /* Block inlining into previous references within the iteration
 437                         statement.  On iterations after the first they would refer to the
 438                         assignment within the iteration. */
 439                         for(ExpressionUse &u: i->second->uses)
 440                                 for(Block *k=u.ref_scope; (!u.blocked && k); k=k->parent)
 441                                         u.blocked = (k==iteration_body);
 442                 }
 443
 444                 expressions.push_back(ExpressionInfo());
 445                 ExpressionInfo &info = expressions.back();
 446                 info.target = assign.target;
 447                 // Self-referencing assignments can't be inlined without additional work.
 448                 if(!assign.self_referencing)
 449                         info.expression = assign.right;
 450                 info.assign_scope = current_block;
 451                 info.trivial = r_trivial;
 452
 453                 i->second = &info;
 454         }
 455
 456         r_trivial = false;
 457 }
 458
 459 void ExpressionInliner::visit(TernaryExpression &ternary)
 460 {
 461         visit(ternary.condition);
 462         visit(ternary.true_expr);
 463         visit(ternary.false_expr);
 464         r_trivial = false;
 465 }
 466
 467 void ExpressionInliner::visit(FunctionCall &call)
 468 {
 469         TraversingVisitor::visit(call);
 470         r_trivial = false;
 471 }
 472
 473 void ExpressionInliner::visit(VariableDeclaration &var)
 474 {
 475         r_oper = 0;
 476         r_trivial = true;
 477         TraversingVisitor::visit(var);
 478
 479         bool constant = var.constant;
 480         if(constant && var.layout)
 481         {
 482                 constant = !any_of(var.layout->qualifiers.begin(), var.layout->qualifiers.end(),
 483                         [](const Layout::Qualifier &q){ return q.name=="constant_id"; });
 484         }
 485
 486         /* Only inline global variables if they're constant and have trivial
 487         initializers.  Non-constant variables could change in ways which are hard to
 488         analyze and non-trivial expressions could be expensive to inline.  */
 489         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 490         {
 491                 expressions.push_back(ExpressionInfo());
 492                 ExpressionInfo &info = expressions.back();
 493                 info.target = &var;
 494                 /* Assume variables declared in an iteration initialization statement
 495                 will have their values change throughout the iteration. */
 496                 if(!iteration_init)
 497                         info.expression = var.init_expression;
 498                 info.assign_scope = current_block;
 499                 info.trivial = r_trivial;
 500
 501                 assignments[&var] = &info;
 502         }
 503 }
 504
 505 void ExpressionInliner::visit(Iteration &iter)
 506 {
 507         SetForScope<Block *> set_block(current_block, &iter.body);
 508         if(iter.init_statement)
 509         {
 510                 SetFlag set_init(iteration_init);
 511                 iter.init_statement->visit(*this);
 512         }
 513
 514         SetForScope<Block *> set_body(iteration_body, &iter.body);
 515         if(iter.condition)
 516                 visit(iter.condition);
 517         iter.body.visit(*this);
 518         if(iter.loop_expression)
 519                 visit(iter.loop_expression);
 520 }
 521
 522
 523 template<typename T>
 524 T ConstantFolder::evaluate_logical(char oper, T left, T right)
 525 {
 526         switch(oper)
 527         {
 528         case '&': return left&right;
 529         case '|': return left|right;
 530         case '^': return left^right;
 531         default: return T();
 532         }
 533 }
 534
 535 template<typename T>
 536 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
 537 {
 538         switch(oper[0]|oper[1])
 539         {
 540         case '<': return left<right;
 541         case '<'|'=': return left<=right;
 542         case '>': return left>right;
 543         case '>'|'=': return left>=right;
 544         default: return false;
 545         }
 546 }
 547
 548 template<typename T>
 549 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
 550 {
 551         switch(oper)
 552         {
 553         case '+': return left+right;
 554         case '-': return left-right;
 555         case '*': return left*right;
 556         case '/': return left/right;
 557         default: return T();
 558         }
 559 }
 560
 561 template<typename T>
 562 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
 563 {
 564         switch(oper)
 565         {
 566         case '%': return left%right;
 567         case '<': return left<<right;
 568         case '>': return left>>right;
 569         default: return T();
 570         }
 571 }
 572
 573 template<typename T>
 574 void ConstantFolder::convert_to_result(const Variant &value)
 575 {
 576         if(value.check_type<bool>())
 577                 set_result(static_cast<T>(value.value<bool>()));
 578         else if(value.check_type<int>())
 579                 set_result(static_cast<T>(value.value<int>()));
 580         else if(value.check_type<unsigned>())
 581                 set_result(static_cast<T>(value.value<unsigned>()));
 582         else if(value.check_type<float>())
 583                 set_result(static_cast<T>(value.value<float>()));
 584 }
 585
 586 void ConstantFolder::set_result(const Variant &value, bool literal)
 587 {
 588         r_constant_value = value;
 589         r_constant = true;
 590         r_literal = literal;
 591 }
 592
 593 void ConstantFolder::visit(RefPtr<Expression> &expr)
 594 {
 595         r_constant_value = Variant();
 596         r_constant = false;
 597         r_literal = false;
 598         r_uses_iter_var = false;
 599         expr->visit(*this);
 600         /* Don't replace literals since they'd only be replaced with an identical
 601         literal.  Also skip anything that uses an iteration variable, but pass on
 602         the result so the Iteration visiting function can handle it. */
 603         if(!r_constant || r_literal || r_uses_iter_var)
 604                 return;
 605
 606         RefPtr<Literal> literal = new Literal;
 607         if(r_constant_value.check_type<bool>())
 608                 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
 609         else if(r_constant_value.check_type<int>())
 610                 literal->token = lexical_cast<string>(r_constant_value.value<int>());
 611         else if(r_constant_value.check_type<unsigned>())
 612                 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
 613         else if(r_constant_value.check_type<float>())
 614         {
 615                 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
 616                 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
 617                         literal->token += ".0";
 618         }
 619         else
 620         {
 621                 r_constant = false;
 622                 return;
 623         }
 624         literal->value = r_constant_value;
 625         expr = literal;
 626         r_any_folded = true;
 627 }
 628
 629 void ConstantFolder::visit(Literal &literal)
 630 {
 631         set_result(literal.value, true);
 632 }
 633
 634 void ConstantFolder::visit(VariableReference &var)
 635 {
 636         /* If an iteration variable is initialized with a constant value, return
 637         that value here for the purpose of evaluating the loop condition for the
 638         first iteration. */
 639         if(var.declaration==iteration_var)
 640         {
 641                 set_result(iter_init_value);
 642                 r_uses_iter_var = true;
 643         }
 644 }
 645
 646 void ConstantFolder::visit(MemberAccess &memacc)
 647 {
 648         TraversingVisitor::visit(memacc);
 649         r_constant = false;
 650 }
 651
 652 void ConstantFolder::visit(Swizzle &swizzle)
 653 {
 654         TraversingVisitor::visit(swizzle);
 655         r_constant = false;
 656 }
 657
 658 void ConstantFolder::visit(UnaryExpression &unary)
 659 {
 660         TraversingVisitor::visit(unary);
 661         bool can_fold = r_constant;
 662         r_constant = false;
 663         if(!can_fold)
 664                 return;
 665
 666         char oper = unary.oper->token[0];
 667         char oper2 = unary.oper->token[1];
 668         if(oper=='!')
 669         {
 670                 if(r_constant_value.check_type<bool>())
 671                         set_result(!r_constant_value.value<bool>());
 672         }
 673         else if(oper=='~')
 674         {
 675                 if(r_constant_value.check_type<int>())
 676                         set_result(~r_constant_value.value<int>());
 677                 else if(r_constant_value.check_type<unsigned>())
 678                         set_result(~r_constant_value.value<unsigned>());
 679         }
 680         else if(oper=='-' && !oper2)
 681         {
 682                 if(r_constant_value.check_type<int>())
 683                         set_result(-r_constant_value.value<int>());
 684                 else if(r_constant_value.check_type<unsigned>())
 685                         set_result(-r_constant_value.value<unsigned>());
 686                 else if(r_constant_value.check_type<float>())
 687                         set_result(-r_constant_value.value<float>());
 688         }
 689 }
 690
 691 void ConstantFolder::visit(BinaryExpression &binary)
 692 {
 693         visit(binary.left);
 694         bool left_constant = r_constant;
 695         bool left_iter_var = r_uses_iter_var;
 696         Variant left_value = r_constant_value;
 697         visit(binary.right);
 698         if(left_iter_var)
 699                 r_uses_iter_var = true;
 700
 701         bool can_fold = (left_constant && r_constant);
 702         r_constant = false;
 703         if(!can_fold)
 704                 return;
 705
 706         // Currently only expressions with both sides of equal types are handled.
 707         if(!left_value.check_same_type(r_constant_value))
 708                 return;
 709
 710         char oper = binary.oper->token[0];
 711         char oper2 = binary.oper->token[1];
 712         if(oper=='&' || oper=='|' || oper=='^')
 713         {
 714                 if(oper2==oper && left_value.check_type<bool>())
 715                         set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
 716                 else if(!oper2 && left_value.check_type<int>())
 717                         set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
 718                 else if(!oper2 && left_value.check_type<unsigned>())
 719                         set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 720         }
 721         else if((oper=='<' || oper=='>') && oper2!=oper)
 722         {
 723                 if(left_value.check_type<int>())
 724                         set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
 725                 else if(left_value.check_type<unsigned>())
 726                         set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 727                 else if(left_value.check_type<float>())
 728                         set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
 729         }
 730         else if((oper=='=' || oper=='!') && oper2=='=')
 731         {
 732                 if(left_value.check_type<int>())
 733                         set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
 734                 else if(left_value.check_type<unsigned>())
 735                         set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
 736                 else if(left_value.check_type<float>())
 737                         set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
 738         }
 739         else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
 740         {
 741                 if(left_value.check_type<int>())
 742                         set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
 743                 else if(left_value.check_type<unsigned>())
 744                         set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 745                 else if(left_value.check_type<float>())
 746                         set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
 747         }
 748         else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
 749         {
 750                 if(left_value.check_type<int>())
 751                         set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
 752                 else if(left_value.check_type<unsigned>())
 753                         set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 754         }
 755 }
 756
 757 void ConstantFolder::visit(Assignment &assign)
 758 {
 759         TraversingVisitor::visit(assign);
 760         r_constant = false;
 761 }
 762
 763 void ConstantFolder::visit(TernaryExpression &ternary)
 764 {
 765         TraversingVisitor::visit(ternary);
 766         r_constant = false;
 767 }
 768
 769 void ConstantFolder::visit(FunctionCall &call)
 770 {
 771         if(call.constructor && call.type && call.arguments.size()==1)
 772         {
 773                 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
 774                 if(basic)
 775                 {
 776                         visit(call.arguments[0]);
 777                         bool can_fold = r_constant;
 778                         r_constant = false;
 779                         if(!can_fold)
 780                                 return;
 781
 782                         if(basic->kind==BasicTypeDeclaration::BOOL)
 783                                 convert_to_result<bool>(r_constant_value);
 784                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
 785                                 convert_to_result<int>(r_constant_value);
 786                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
 787                                 convert_to_result<unsigned>(r_constant_value);
 788                         else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
 789                                 convert_to_result<float>(r_constant_value);
 790
 791                         return;
 792                 }
 793         }
 794
 795         TraversingVisitor::visit(call);
 796         r_constant = false;
 797 }
 798
 799 void ConstantFolder::visit(VariableDeclaration &var)
 800 {
 801         if(iteration_init && var.init_expression)
 802         {
 803                 visit(var.init_expression);
 804                 if(r_constant)
 805                 {
 806                         /* Record the value of a constant initialization expression of an
 807                         iteration, so it can be used to evaluate the loop condition. */
 808                         iteration_var = &var;
 809                         iter_init_value = r_constant_value;
 810                 }
 811         }
 812         else
 813                 TraversingVisitor::visit(var);
 814 }
 815
 816 void ConstantFolder::visit(Iteration &iter)
 817 {
 818         SetForScope<Block *> set_block(current_block, &iter.body);
 819
 820         /* The iteration variable is not normally inlined into expressions, so we
 821         process it specially here.  If the initial value causes the loop condition
 822         to evaluate to false, then the expression can be folded. */
 823         iteration_var = 0;
 824         if(iter.init_statement)
 825         {
 826                 SetFlag set_init(iteration_init);
 827                 iter.init_statement->visit(*this);
 828         }
 829
 830         if(iter.condition)
 831         {
 832                 visit(iter.condition);
 833                 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
 834                 {
 835                         RefPtr<Literal> literal = new Literal;
 836                         literal->token = "false";
 837                         literal->value = r_constant_value;
 838                         iter.condition = literal;
 839                 }
 840         }
 841         iteration_var = 0;
 842
 843         iter.body.visit(*this);
 844         if(iter.loop_expression)
 845                 visit(iter.loop_expression);
 846 }
 847
 848
 849 void ConstantConditionEliminator::apply(Stage &stage)
 850 {
 851         stage.content.visit(*this);
 852         NodeRemover().apply(stage, nodes_to_remove);
 853 }
 854
 855 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
 856 {
 857         if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
 858                 if(literal->value.check_type<bool>())
 859                         return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
 860         return NOT_CONSTANT;
 861 }
 862
 863 void ConstantConditionEliminator::visit(Block &block)
 864 {
 865         SetForScope<Block *> set_block(current_block, &block);
 866         for(auto i=block.body.begin(); i!=block.body.end(); ++i)
 867         {
 868                 insert_point = i;
 869                 (*i)->visit(*this);
 870         }
 871 }
 872
 873 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
 874 {
 875         r_ternary_result = 0;
 876         expr->visit(*this);
 877         if(r_ternary_result)
 878                 expr = r_ternary_result;
 879         r_ternary_result = 0;
 880 }
 881
 882 void ConstantConditionEliminator::visit(UnaryExpression &unary)
 883 {
 884         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 885                 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
 886                 {
 887                         auto i = current_block->variables.find(var->name);
 888                         r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
 889                         return;
 890                 }
 891
 892         TraversingVisitor::visit(unary);
 893 }
 894
 895 void ConstantConditionEliminator::visit(Assignment &assign)
 896 {
 897         auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
 898         if(i==current_block->variables.end())
 899                 r_external_side_effects = true;
 900         TraversingVisitor::visit(assign);
 901 }
 902
 903 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
 904 {
 905         ConstantStatus result = check_constant_condition(*ternary.condition);
 906         if(result!=NOT_CONSTANT)
 907                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
 908         else
 909                 r_ternary_result = 0;
 910 }
 911
 912 void ConstantConditionEliminator::visit(FunctionCall &call)
 913 {
 914         r_external_side_effects = true;
 915         TraversingVisitor::visit(call);
 916 }
 917
 918 void ConstantConditionEliminator::visit(Conditional &cond)
 919 {
 920         ConstantStatus result = check_constant_condition(*cond.condition);
 921         if(result!=NOT_CONSTANT)
 922         {
 923                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
 924                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
 925                 current_block->body.splice(insert_point, block.body);
 926                 nodes_to_remove.insert(&cond);
 927                 return;
 928         }
 929
 930         r_external_side_effects = false;
 931         TraversingVisitor::visit(cond);
 932
 933         if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
 934                 nodes_to_remove.insert(&cond);
 935 }
 936
 937 void ConstantConditionEliminator::visit(Iteration &iter)
 938 {
 939         if(iter.condition)
 940         {
 941                 ConstantStatus result = check_constant_condition(*iter.condition);
 942                 if(result==CONSTANT_FALSE)
 943                 {
 944                         nodes_to_remove.insert(&iter);
 945                         return;
 946                 }
 947         }
 948
 949         r_external_side_effects = false;
 950         TraversingVisitor::visit(iter);
 951         if(iter.body.body.empty() && !r_external_side_effects)
 952                 nodes_to_remove.insert(&iter);
 953 }
 954
 955
 956 bool UnreachableCodeRemover::apply(Stage &stage)
 957 {
 958         stage.content.visit(*this);
 959         NodeRemover().apply(stage, unreachable_nodes);
 960         return !unreachable_nodes.empty();
 961 }
 962
 963 void UnreachableCodeRemover::visit(Block &block)
 964 {
 965         auto i = block.body.begin();
 966         for(; (reachable && i!=block.body.end()); ++i)
 967                 (*i)->visit(*this);
 968         for(; i!=block.body.end(); ++i)
 969                 unreachable_nodes.insert(i->get());
 970 }
 971
 972 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
 973 {
 974         TraversingVisitor::visit(func);
 975         reachable = true;
 976 }
 977
 978 void UnreachableCodeRemover::visit(Conditional &cond)
 979 {
 980         cond.body.visit(*this);
 981         bool reachable_if_true = reachable;
 982         reachable = true;
 983         cond.else_body.visit(*this);
 984
 985         reachable |= reachable_if_true;
 986 }
 987
 988 void UnreachableCodeRemover::visit(Iteration &iter)
 989 {
 990         TraversingVisitor::visit(iter);
 991
 992         /* Always consider code after a loop reachable, since there's no checking
 993         for whether the loop executes. */
 994         reachable = true;
 995 }
 996
 997
 998 bool UnusedTypeRemover::apply(Stage &stage)
 999 {
1000         stage.content.visit(*this);
1001         NodeRemover().apply(stage, unused_nodes);
1002         return !unused_nodes.empty();
1003 }
1004
1005 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1006 {
1007         unused_nodes.erase(expr->type);
1008         TraversingVisitor::visit(expr);
1009 }
1010
1011 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1012 {
1013         if(type.base_type)
1014                 unused_nodes.erase(type.base_type);
1015         unused_nodes.insert(&type);
1016 }
1017
1018 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1019 {
1020         if(type.base_type)
1021                 unused_nodes.erase(type.base_type);
1022         unused_nodes.insert(&type);
1023 }
1024
1025 void UnusedTypeRemover::visit(StructDeclaration &strct)
1026 {
1027         unused_nodes.insert(&strct);
1028         TraversingVisitor::visit(strct);
1029 }
1030
1031 void UnusedTypeRemover::visit(VariableDeclaration &var)
1032 {
1033         unused_nodes.erase(var.type_declaration);
1034         TraversingVisitor::visit(var);
1035 }
1036
1037 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1038 {
1039         unused_nodes.erase(iface.type_declaration);
1040 }
1041
1042 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1043 {
1044         unused_nodes.erase(func.return_type_declaration);
1045         TraversingVisitor::visit(func);
1046 }
1047
1048
1049 bool UnusedVariableRemover::apply(Stage &s)
1050 {
1051         stage = &s;
1052         s.content.visit(*this);
1053
1054         for(const AssignmentInfo &a: assignments)
1055                 if(a.used_by.empty())
1056                         unused_nodes.insert(a.node);
1057
1058         for(const auto &kvp: variables)
1059         {
1060                 if(kvp.second.output)
1061                 {
1062                         /* The last visible assignments of output variables are used by the
1063                         next stage or the API. */
1064                         for(AssignmentInfo *a: kvp.second.assignments)
1065                                 unused_nodes.erase(a->node);
1066                 }
1067
1068                 if(!kvp.second.output && !kvp.second.referenced)
1069                 {
1070                         // Don't remove variables from inside interface blocks.
1071                         if(!kvp.second.interface_block)
1072                                 unused_nodes.insert(kvp.first);
1073                 }
1074                 else if(kvp.second.interface_block)
1075                         // Interface blocks are kept if even one member is used.
1076                         unused_nodes.erase(kvp.second.interface_block);
1077         }
1078
1079         NodeRemover().apply(s, unused_nodes);
1080
1081         return !unused_nodes.empty();
1082 }
1083
1084 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1085 {
1086         VariableInfo &var_info = variables[target.declaration];
1087         var_info.referenced = true;
1088         if(!assignment_target)
1089         {
1090                 bool loop_external = false;
1091                 for(AssignmentInfo *a: var_info.assignments)
1092                 {
1093                         bool covered = true;
1094                         for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1095                         {
1096                                 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1097                                 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1098                                 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1099                                 {
1100                                         unsigned index1 = a->target.chain[j]&0x3F;
1101                                         unsigned index2 = target.chain[j]&0x3F;
1102                                         if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1103                                                 covered = index1&index2;
1104                                         else if(type1==Assignment::Target::ARRAY && index1<4)
1105                                                 covered = index2&(1<<index1);
1106                                         else if(type2==Assignment::Target::ARRAY && index2<4)
1107                                                 covered = index1&(1<<index2);
1108                                         /* If it's some other combination (shouldn't happen), leave
1109                                         covered as true */
1110                                 }
1111                                 else
1112                                         covered = (a->target.chain[j]==target.chain[j]);
1113                         }
1114
1115                         if(covered)
1116                         {
1117                                 a->used_by.push_back(&node);
1118                                 if(a->in_loop<in_loop)
1119                                         loop_external = true;
1120                         }
1121                 }
1122
1123                 if(loop_external)
1124                         loop_ext_refs.push_back(&node);
1125         }
1126 }
1127
1128 void UnusedVariableRemover::visit(VariableReference &var)
1129 {
1130         if(composite_reference)
1131                 r_reference.declaration = var.declaration;
1132         else
1133                 referenced(var.declaration, var);
1134 }
1135
1136 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1137 {
1138         if(composite_reference)
1139                 r_reference.declaration = iface.declaration;
1140         else
1141                 referenced(iface.declaration, iface);
1142 }
1143
1144 void UnusedVariableRemover::visit_composite(Expression &expr)
1145 {
1146         if(!composite_reference)
1147                 r_reference = Assignment::Target();
1148
1149         SetFlag set_composite(composite_reference);
1150         expr.visit(*this);
1151 }
1152
1153 void UnusedVariableRemover::visit(MemberAccess &memacc)
1154 {
1155         visit_composite(*memacc.left);
1156
1157         add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1158
1159         if(!composite_reference && r_reference.declaration)
1160                 referenced(r_reference, memacc);
1161 }
1162
1163 void UnusedVariableRemover::visit(Swizzle &swizzle)
1164 {
1165         visit_composite(*swizzle.left);
1166
1167         unsigned mask = 0;
1168         for(unsigned i=0; i<swizzle.count; ++i)
1169                 mask |= 1<<swizzle.components[i];
1170         add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1171
1172         if(!composite_reference && r_reference.declaration)
1173                 referenced(r_reference, swizzle);
1174 }
1175
1176 void UnusedVariableRemover::visit(UnaryExpression &unary)
1177 {
1178         TraversingVisitor::visit(unary);
1179         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1180                 r_side_effects = true;
1181 }
1182
1183 void UnusedVariableRemover::visit(BinaryExpression &binary)
1184 {
1185         if(binary.oper->token[0]=='[')
1186         {
1187                 visit_composite(*binary.left);
1188
1189                 {
1190                         SetFlag clear_assignment(assignment_target, false);
1191                         SetFlag clear_composite(composite_reference, false);
1192                         binary.right->visit(*this);
1193                 }
1194
1195                 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1196
1197                 if(!composite_reference && r_reference.declaration)
1198                         referenced(r_reference, binary);
1199         }
1200         else
1201         {
1202                 SetFlag clear_composite(composite_reference, false);
1203                 TraversingVisitor::visit(binary);
1204         }
1205 }
1206
1207 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1208 {
1209         SetFlag clear_composite(composite_reference, false);
1210         TraversingVisitor::visit(ternary);
1211 }
1212
1213 void UnusedVariableRemover::visit(Assignment &assign)
1214 {
1215         {
1216                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1217                 assign.left->visit(*this);
1218         }
1219         assign.right->visit(*this);
1220         r_assignment = &assign;
1221         r_side_effects = true;
1222 }
1223
1224 void UnusedVariableRemover::visit(FunctionCall &call)
1225 {
1226         SetFlag clear_composite(composite_reference, false);
1227         TraversingVisitor::visit(call);
1228         /* Treat function calls as having side effects so expression statements
1229         consisting of nothing but a function call won't be optimized away. */
1230         r_side_effects = true;
1231
1232         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1233         {
1234                 for(const auto &kvp: variables)
1235                         if(kvp.second.output)
1236                                 referenced(kvp.first, call);
1237         }
1238 }
1239
1240 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1241 {
1242         assignments.push_back(AssignmentInfo());
1243         AssignmentInfo &assign_info = assignments.back();
1244         assign_info.node = &node;
1245         assign_info.target = target;
1246         assign_info.in_loop = in_loop;
1247
1248         /* An assignment to the target hides any assignments to the same target or
1249         its subfields. */
1250         VariableInfo &var_info = variables[target.declaration];
1251         for(unsigned i=0; i<var_info.assignments.size(); )
1252         {
1253                 const Assignment::Target &t = var_info.assignments[i]->target;
1254
1255                 bool subfield = (t.chain_len>=target.chain_len);
1256                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1257                         subfield = (t.chain[j]==target.chain[j]);
1258
1259                 if(subfield)
1260                         var_info.assignments.erase(var_info.assignments.begin()+i);
1261                 else
1262                         ++i;
1263         }
1264
1265         var_info.assignments.push_back(&assign_info);
1266 }
1267
1268 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1269 {
1270         r_assignment = 0;
1271         r_side_effects = false;
1272         TraversingVisitor::visit(expr);
1273         if(r_assignment && r_assignment->target.declaration)
1274                 record_assignment(r_assignment->target, expr);
1275         if(!r_side_effects)
1276                 unused_nodes.insert(&expr);
1277 }
1278
1279 void UnusedVariableRemover::visit(StructDeclaration &strct)
1280 {
1281         SetFlag set_struct(in_struct);
1282         TraversingVisitor::visit(strct);
1283 }
1284
1285 void UnusedVariableRemover::visit(VariableDeclaration &var)
1286 {
1287         TraversingVisitor::visit(var);
1288
1289         if(in_struct)
1290                 return;
1291
1292         VariableInfo &var_info = variables[&var];
1293         var_info.interface_block = interface_block;
1294
1295         /* Mark variables as output if they're used by the next stage or the
1296         graphics API. */
1297         if(interface_block)
1298                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1299         else
1300                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1301
1302         if(var.init_expression)
1303         {
1304                 var_info.initialized = true;
1305                 record_assignment(&var, *var.init_expression);
1306         }
1307 }
1308
1309 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1310 {
1311         VariableInfo &var_info = variables[&iface];
1312         var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1313 }
1314
1315 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1316 {
1317         for(const auto &kvp: other_vars)
1318         {
1319                 auto j = variables.find(kvp.first);
1320                 if(j!=variables.end())
1321                 {
1322                         /* The merged blocks started as copies of each other so any common
1323                         assignments must be in the beginning. */
1324                         unsigned k = 0;
1325                         for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1326                                 if(kvp.second.assignments[k]!=j->second.assignments[k])
1327                                         break;
1328
1329                         // Remaining assignments are unique to each block; merge them.
1330                         j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1331                         j->second.referenced |= kvp.second.referenced;
1332                 }
1333                 else
1334                         variables.insert(kvp);
1335         }
1336 }
1337
1338 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1339 {
1340         if(func.body.body.empty())
1341                 return;
1342
1343         BlockVariableMap saved_vars = variables;
1344         // Assignments from other functions should not be visible.
1345         for(auto &kvp: variables)
1346                 kvp.second.assignments.resize(kvp.second.initialized);
1347         TraversingVisitor::visit(func);
1348         swap(variables, saved_vars);
1349         merge_variables(saved_vars);
1350
1351         /* Always treat function parameters as referenced.  Removing unused
1352         parameters is not currently supported. */
1353         for(const RefPtr<VariableDeclaration> &p: func.parameters)
1354         {
1355                 auto j = variables.find(p.get());
1356                 if(j!=variables.end())
1357                         j->second.referenced = true;
1358         }
1359 }
1360
1361 void UnusedVariableRemover::visit(Conditional &cond)
1362 {
1363         cond.condition->visit(*this);
1364         BlockVariableMap saved_vars = variables;
1365         cond.body.visit(*this);
1366         swap(saved_vars, variables);
1367         cond.else_body.visit(*this);
1368
1369         /* Visible assignments after the conditional is the union of those visible
1370         at the end of the if and else blocks.  If there was no else block, then it's
1371         the union of the if block and the state before it. */
1372         merge_variables(saved_vars);
1373 }
1374
1375 void UnusedVariableRemover::visit(Iteration &iter)
1376 {
1377         BlockVariableMap saved_vars = variables;
1378         vector<Node *> saved_refs;
1379         swap(loop_ext_refs, saved_refs);
1380         {
1381                 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1382                 TraversingVisitor::visit(iter);
1383         }
1384         swap(loop_ext_refs, saved_refs);
1385
1386         /* Visit the external references of the loop again to record assignments
1387         done in the loop as used. */
1388         for(Node *n: saved_refs)
1389                 n->visit(*this);
1390
1391         /* Merge assignments from the iteration, without clearing previous state.
1392         Further analysis is needed to determine which parts of the iteration body
1393         are always executed, if any. */
1394         merge_variables(saved_vars);
1395 }
1396
1397
1398 bool UnusedFunctionRemover::apply(Stage &stage)
1399 {
1400         stage.content.visit(*this);
1401         NodeRemover().apply(stage, unused_nodes);
1402         return !unused_nodes.empty();
1403 }
1404
1405 void UnusedFunctionRemover::visit(FunctionCall &call)
1406 {
1407         TraversingVisitor::visit(call);
1408
1409         unused_nodes.erase(call.declaration);
1410         if(call.declaration && call.declaration->definition!=call.declaration)
1411                 used_definitions.insert(call.declaration->definition);
1412 }
1413
1414 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1415 {
1416         TraversingVisitor::visit(func);
1417
1418         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1419                 unused_nodes.insert(&func);
1420 }
1421
1422 } // namespace SL
1423 } // namespace GL
1424 } // namespace Msp