source/glsl/optimize.cpp

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