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