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_any_inlined(false),
 355         r_trivial(false),
 356         mutating(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         return r_any_inlined;
 366 }
 367
 368 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
 369 {
 370         ptr = expr.clone();
 371         r_any_inlined = true;
 372 }
 373
 374 void ExpressionInliner::visit(Block &block)
 375 {
 376         TraversingVisitor::visit(block);
 377
 378         for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 379         {
 380                 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
 381                 for(; (j!=expressions.end() && j->first.declaration==i->second); )
 382                 {
 383                         if(j->second.expression && j->second.inline_point)
 384                                 inline_expression(*j->second.expression, *j->second.inline_point);
 385
 386                         expressions.erase(j++);
 387                 }
 388         }
 389
 390         /* Expressions assigned in this block may depend on local variables of the
 391         block.  If this is a conditionally executed block, the assignments might not
 392         always happen.  Mark the expressions as not available to any outer blocks. */
 393         for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
 394                 if(i->second.assign_scope==&block)
 395                         i->second.available = false;
 396 }
 397
 398 void ExpressionInliner::visit(RefPtr<Expression> &expr)
 399 {
 400         r_ref_info = 0;
 401         expr->visit(*this);
 402         if(r_ref_info && r_ref_info->expression && r_ref_info->available)
 403         {
 404                 if(iteration_body && !r_ref_info->trivial)
 405                 {
 406                         /* Don't inline non-trivial expressions which were assigned outside
 407                         an iteration statement.  The iteration may run multiple times, which
 408                         would cause the expression to also be evaluated multiple times. */
 409                         Block *i = r_ref_info->assign_scope;
 410                         for(; (i && i!=iteration_body); i=i->parent) ;
 411                         if(!i)
 412                                 return;
 413                 }
 414
 415                 if(r_ref_info->trivial)
 416                         inline_expression(*r_ref_info->expression, expr);
 417                 else
 418                         /* Record the inline point for a non-trivial expression but don't
 419                         inline it yet.  It might turn out it shouldn't be inlined after all. */
 420                         r_ref_info->inline_point = &expr;
 421         }
 422         r_oper = expr->oper;
 423         r_ref_info = 0;
 424 }
 425
 426 void ExpressionInliner::visit(VariableReference &var)
 427 {
 428         if(var.declaration)
 429         {
 430                 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
 431                 if(i!=expressions.end())
 432                 {
 433                         /* If a non-trivial expression is referenced multiple times, don't
 434                         inline it. */
 435                         if(i->second.inline_point && !i->second.trivial)
 436                                 i->second.expression = 0;
 437                         /* Mutating expressions are analogous to self-referencing assignments
 438                         and prevent inlining. */
 439                         if(mutating)
 440                                 i->second.expression = 0;
 441                         r_ref_info = &i->second;
 442                 }
 443         }
 444 }
 445
 446 void ExpressionInliner::visit(MemberAccess &memacc)
 447 {
 448         visit(memacc.left);
 449         r_trivial = false;
 450 }
 451
 452 void ExpressionInliner::visit(Swizzle &swizzle)
 453 {
 454         visit(swizzle.left);
 455         r_trivial = false;
 456 }
 457
 458 void ExpressionInliner::visit(UnaryExpression &unary)
 459 {
 460         SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
 461         visit(unary.expression);
 462         r_trivial = false;
 463 }
 464
 465 void ExpressionInliner::visit(BinaryExpression &binary)
 466 {
 467         visit(binary.left);
 468         {
 469                 SetFlag clear_target(mutating, false);
 470                 visit(binary.right);
 471         }
 472         r_trivial = false;
 473 }
 474
 475 void ExpressionInliner::visit(Assignment &assign)
 476 {
 477         {
 478                 SetFlag set_target(mutating);
 479                 visit(assign.left);
 480         }
 481         r_oper = 0;
 482         visit(assign.right);
 483
 484         map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
 485         if(i!=expressions.end())
 486         {
 487                 /* Self-referencing assignments can't be inlined without additional
 488                 work.  Just clear any previous expression. */
 489                 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
 490                 i->second.assign_scope = current_block;
 491                 i->second.inline_point = 0;
 492                 i->second.available = true;
 493         }
 494
 495         r_trivial = false;
 496 }
 497
 498 void ExpressionInliner::visit(TernaryExpression &ternary)
 499 {
 500         visit(ternary.condition);
 501         visit(ternary.true_expr);
 502         visit(ternary.false_expr);
 503         r_trivial = false;
 504 }
 505
 506 void ExpressionInliner::visit(FunctionCall &call)
 507 {
 508         TraversingVisitor::visit(call);
 509         r_trivial = false;
 510 }
 511
 512 void ExpressionInliner::visit(VariableDeclaration &var)
 513 {
 514         r_oper = 0;
 515         r_trivial = true;
 516         TraversingVisitor::visit(var);
 517
 518         bool constant = var.constant;
 519         if(constant && var.layout)
 520         {
 521                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 522                         constant = (i->name!="constant_id");
 523         }
 524
 525         /* Only inline global variables if they're constant and have trivial
 526         initializers.  Non-constant variables could change in ways which are hard to
 527         analyze and non-trivial expressions could be expensive to inline.  */
 528         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 529         {
 530                 ExpressionInfo &info = expressions[&var];
 531                 /* Assume variables declared in an iteration initialization statement
 532                 will have their values change throughout the iteration. */
 533                 info.expression = (iteration_init ? 0 : var.init_expression.get());
 534                 info.assign_scope = current_block;
 535                 info.trivial = r_trivial;
 536         }
 537 }
 538
 539 void ExpressionInliner::visit(Iteration &iter)
 540 {
 541         SetForScope<Block *> set_block(current_block, &iter.body);
 542         if(iter.init_statement)
 543         {
 544                 SetFlag set_init(iteration_init);
 545                 iter.init_statement->visit(*this);
 546         }
 547
 548         SetForScope<Block *> set_body(iteration_body, &iter.body);
 549         if(iter.condition)
 550                 visit(iter.condition);
 551         iter.body.visit(*this);
 552         if(iter.loop_expression)
 553                 visit(iter.loop_expression);
 554 }
 555
 556
 557 template<typename T>
 558 T ConstantFolder::evaluate_logical(char oper, T left, T right)
 559 {
 560         switch(oper)
 561         {
 562         case '&': return left&right;
 563         case '|': return left|right;
 564         case '^': return left^right;
 565         default: return T();
 566         }
 567 }
 568
 569 template<typename T>
 570 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
 571 {
 572         switch(oper[0]|oper[1])
 573         {
 574         case '<': return left<right;
 575         case '<'|'=': return left<=right;
 576         case '>': return left>right;
 577         case '>'|'=': return left>=right;
 578         default: return false;
 579         }
 580 }
 581
 582 template<typename T>
 583 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
 584 {
 585         switch(oper)
 586         {
 587         case '+': return left+right;
 588         case '-': return left-right;
 589         case '*': return left*right;
 590         case '/': return left/right;
 591         default: return T();
 592         }
 593 }
 594
 595 template<typename T>
 596 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
 597 {
 598         switch(oper)
 599         {
 600         case '%': return left%right;
 601         case '<': return left<<right;
 602         case '>': return left>>right;
 603         default: return T();
 604         }
 605 }
 606
 607 template<typename T>
 608 void ConstantFolder::convert_to_result(const Variant &value)
 609 {
 610         if(value.check_type<bool>())
 611                 set_result(static_cast<T>(value.value<bool>()));
 612         else if(value.check_type<int>())
 613                 set_result(static_cast<T>(value.value<int>()));
 614         else if(value.check_type<unsigned>())
 615                 set_result(static_cast<T>(value.value<unsigned>()));
 616         else if(value.check_type<float>())
 617                 set_result(static_cast<T>(value.value<float>()));
 618 }
 619
 620 void ConstantFolder::set_result(const Variant &value, bool literal)
 621 {
 622         r_constant_value = value;
 623         r_constant = true;
 624         r_literal = literal;
 625 }
 626
 627 void ConstantFolder::visit(RefPtr<Expression> &expr)
 628 {
 629         r_constant_value = Variant();
 630         r_constant = false;
 631         r_literal = false;
 632         r_uses_iter_var = false;
 633         expr->visit(*this);
 634         /* Don't replace literals since they'd only be replaced with an identical
 635         literal.  Also skip anything that uses an iteration variable, but pass on
 636         the result so the Iteration visiting function can handle it. */
 637         if(!r_constant || r_literal || r_uses_iter_var)
 638                 return;
 639
 640         RefPtr<Literal> literal = new Literal;
 641         if(r_constant_value.check_type<bool>())
 642                 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
 643         else if(r_constant_value.check_type<int>())
 644                 literal->token = lexical_cast<string>(r_constant_value.value<int>());
 645         else if(r_constant_value.check_type<unsigned>())
 646                 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
 647         else if(r_constant_value.check_type<float>())
 648         {
 649                 literal->token = lexical_cast<string>(r_constant_value.value<float>());
 650                 if(isnumrc(literal->token))
 651                         literal->token += ".0";
 652         }
 653         else
 654         {
 655                 r_constant = false;
 656                 return;
 657         }
 658         literal->value = r_constant_value;
 659         expr = literal;
 660         r_any_folded = true;
 661 }
 662
 663 void ConstantFolder::visit(Literal &literal)
 664 {
 665         set_result(literal.value, true);
 666 }
 667
 668 void ConstantFolder::visit(VariableReference &var)
 669 {
 670         /* If an iteration variable is initialized with a constant value, return
 671         that value here for the purpose of evaluating the loop condition for the
 672         first iteration. */
 673         if(var.declaration==iteration_var)
 674         {
 675                 set_result(iter_init_value);
 676                 r_uses_iter_var = true;
 677         }
 678 }
 679
 680 void ConstantFolder::visit(MemberAccess &memacc)
 681 {
 682         TraversingVisitor::visit(memacc);
 683         r_constant = false;
 684 }
 685
 686 void ConstantFolder::visit(Swizzle &swizzle)
 687 {
 688         TraversingVisitor::visit(swizzle);
 689         r_constant = false;
 690 }
 691
 692 void ConstantFolder::visit(UnaryExpression &unary)
 693 {
 694         TraversingVisitor::visit(unary);
 695         bool can_fold = r_constant;
 696         r_constant = false;
 697         if(!can_fold)
 698                 return;
 699
 700         char oper = unary.oper->token[0];
 701         char oper2 = unary.oper->token[1];
 702         if(oper=='!')
 703         {
 704                 if(r_constant_value.check_type<bool>())
 705                         set_result(!r_constant_value.value<bool>());
 706         }
 707         else if(oper=='~')
 708         {
 709                 if(r_constant_value.check_type<int>())
 710                         set_result(~r_constant_value.value<int>());
 711                 else if(r_constant_value.check_type<unsigned>())
 712                         set_result(~r_constant_value.value<unsigned>());
 713         }
 714         else if(oper=='-' && !oper2)
 715         {
 716                 if(r_constant_value.check_type<int>())
 717                         set_result(-r_constant_value.value<int>());
 718                 else if(r_constant_value.check_type<unsigned>())
 719                         set_result(-r_constant_value.value<unsigned>());
 720                 else if(r_constant_value.check_type<float>())
 721                         set_result(-r_constant_value.value<float>());
 722         }
 723 }
 724
 725 void ConstantFolder::visit(BinaryExpression &binary)
 726 {
 727         visit(binary.left);
 728         bool left_constant = r_constant;
 729         bool left_iter_var = r_uses_iter_var;
 730         Variant left_value = r_constant_value;
 731         visit(binary.right);
 732         if(left_iter_var)
 733                 r_uses_iter_var = true;
 734
 735         bool can_fold = (left_constant && r_constant);
 736         r_constant = false;
 737         if(!can_fold)
 738                 return;
 739
 740         // Currently only expressions with both sides of equal types are handled.
 741         if(!left_value.check_same_type(r_constant_value))
 742                 return;
 743
 744         char oper = binary.oper->token[0];
 745         char oper2 = binary.oper->token[1];
 746         if(oper=='&' || oper=='|' || oper=='^')
 747         {
 748                 if(oper2==oper && left_value.check_type<bool>())
 749                         set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
 750                 else if(!oper2 && left_value.check_type<int>())
 751                         set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
 752                 else if(!oper2 && left_value.check_type<unsigned>())
 753                         set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 754         }
 755         else if((oper=='<' || oper=='>') && oper2!=oper)
 756         {
 757                 if(left_value.check_type<int>())
 758                         set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
 759                 else if(left_value.check_type<unsigned>())
 760                         set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 761                 else if(left_value.check_type<float>())
 762                         set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
 763         }
 764         else if((oper=='=' || oper=='!') && oper2=='=')
 765         {
 766                 if(left_value.check_type<int>())
 767                         set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
 768                 else if(left_value.check_type<unsigned>())
 769                         set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
 770                 else if(left_value.check_type<float>())
 771                         set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
 772         }
 773         else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
 774         {
 775                 if(left_value.check_type<int>())
 776                         set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
 777                 else if(left_value.check_type<unsigned>())
 778                         set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 779                 else if(left_value.check_type<float>())
 780                         set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
 781         }
 782         else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
 783         {
 784                 if(left_value.check_type<int>())
 785                         set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
 786                 else if(left_value.check_type<unsigned>())
 787                         set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 788         }
 789 }
 790
 791 void ConstantFolder::visit(Assignment &assign)
 792 {
 793         TraversingVisitor::visit(assign);
 794         r_constant = false;
 795 }
 796
 797 void ConstantFolder::visit(TernaryExpression &ternary)
 798 {
 799         TraversingVisitor::visit(ternary);
 800         r_constant = false;
 801 }
 802
 803 void ConstantFolder::visit(FunctionCall &call)
 804 {
 805         if(call.constructor && call.type && call.arguments.size()==1)
 806         {
 807                 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
 808                 if(basic)
 809                 {
 810                         call.arguments[0]->visit(*this);
 811                         bool can_fold = r_constant;
 812                         r_constant = false;
 813                         if(!can_fold)
 814                                 return;
 815
 816                         if(basic->kind==BasicTypeDeclaration::BOOL)
 817                                 convert_to_result<bool>(r_constant_value);
 818                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
 819                                 convert_to_result<int>(r_constant_value);
 820                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
 821                                 convert_to_result<unsigned>(r_constant_value);
 822                         else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
 823                                 convert_to_result<float>(r_constant_value);
 824
 825                         return;
 826                 }
 827         }
 828
 829         TraversingVisitor::visit(call);
 830         r_constant = false;
 831 }
 832
 833 void ConstantFolder::visit(VariableDeclaration &var)
 834 {
 835         if(iteration_init && var.init_expression)
 836         {
 837                 visit(var.init_expression);
 838                 if(r_constant)
 839                 {
 840                         /* Record the value of a constant initialization expression of an
 841                         iteration, so it can be used to evaluate the loop condition. */
 842                         iteration_var = &var;
 843                         iter_init_value = r_constant_value;
 844                 }
 845         }
 846         else
 847                 TraversingVisitor::visit(var);
 848 }
 849
 850 void ConstantFolder::visit(Iteration &iter)
 851 {
 852         SetForScope<Block *> set_block(current_block, &iter.body);
 853
 854         /* The iteration variable is not normally inlined into expressions, so we
 855         process it specially here.  If the initial value causes the loop condition
 856         to evaluate to false, then the expression can be folded. */
 857         iteration_var = 0;
 858         if(iter.init_statement)
 859         {
 860                 SetFlag set_init(iteration_init);
 861                 iter.init_statement->visit(*this);
 862         }
 863
 864         if(iter.condition)
 865         {
 866                 visit(iter.condition);
 867                 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
 868                 {
 869                         RefPtr<Literal> literal = new Literal;
 870                         literal->token = "false";
 871                         literal->value = r_constant_value;
 872                         iter.condition = literal;
 873                 }
 874         }
 875         iteration_var = 0;
 876
 877         iter.body.visit(*this);
 878         if(iter.loop_expression)
 879                 visit(iter.loop_expression);
 880 }
 881
 882
 883 void ConstantConditionEliminator::apply(Stage &stage)
 884 {
 885         stage.content.visit(*this);
 886         NodeRemover().apply(stage, nodes_to_remove);
 887 }
 888
 889 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
 890 {
 891         if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
 892                 if(literal->value.check_type<bool>())
 893                         return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
 894         return NOT_CONSTANT;
 895 }
 896
 897 void ConstantConditionEliminator::visit(Block &block)
 898 {
 899         SetForScope<Block *> set_block(current_block, &block);
 900         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 901         {
 902                 insert_point = i;
 903                 (*i)->visit(*this);
 904         }
 905 }
 906
 907 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
 908 {
 909         r_ternary_result = 0;
 910         expr->visit(*this);
 911         if(r_ternary_result)
 912                 expr = r_ternary_result;
 913         r_ternary_result = 0;
 914 }
 915
 916 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
 917 {
 918         ConstantStatus result = check_constant_condition(*ternary.condition);
 919         if(result!=NOT_CONSTANT)
 920                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
 921         else
 922                 r_ternary_result = 0;
 923 }
 924
 925 void ConstantConditionEliminator::visit(Conditional &cond)
 926 {
 927         ConstantStatus result = check_constant_condition(*cond.condition);
 928         if(result!=NOT_CONSTANT)
 929         {
 930                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
 931                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
 932                 current_block->body.splice(insert_point, block.body);
 933                 nodes_to_remove.insert(&cond);
 934                 return;
 935         }
 936
 937         TraversingVisitor::visit(cond);
 938 }
 939
 940 void ConstantConditionEliminator::visit(Iteration &iter)
 941 {
 942         if(iter.condition)
 943         {
 944                 ConstantStatus result = check_constant_condition(*iter.condition);
 945                 if(result==CONSTANT_FALSE)
 946                 {
 947                         nodes_to_remove.insert(&iter);
 948                         return;
 949                 }
 950         }
 951
 952         TraversingVisitor::visit(iter);
 953 }
 954
 955
 956 UnreachableCodeRemover::UnreachableCodeRemover():
 957         reachable(true)
 958 { }
 959
 960 bool UnreachableCodeRemover::apply(Stage &stage)
 961 {
 962         stage.content.visit(*this);
 963         NodeRemover().apply(stage, unreachable_nodes);
 964         return !unreachable_nodes.empty();
 965 }
 966
 967 void UnreachableCodeRemover::visit(Block &block)
 968 {
 969         NodeList<Statement>::iterator i = block.body.begin();
 970         for(; (reachable && i!=block.body.end()); ++i)
 971                 (*i)->visit(*this);
 972         for(; i!=block.body.end(); ++i)
 973                 unreachable_nodes.insert(i->get());
 974 }
 975
 976 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
 977 {
 978         TraversingVisitor::visit(func);
 979         reachable = true;
 980 }
 981
 982 void UnreachableCodeRemover::visit(Conditional &cond)
 983 {
 984         cond.body.visit(*this);
 985         bool reachable_if_true = reachable;
 986         reachable = true;
 987         cond.else_body.visit(*this);
 988
 989         reachable |= reachable_if_true;
 990 }
 991
 992 void UnreachableCodeRemover::visit(Iteration &iter)
 993 {
 994         TraversingVisitor::visit(iter);
 995
 996         /* Always consider code after a loop reachable, since there's no checking
 997         for whether the loop executes. */
 998         reachable = true;
 999 }
1000
1001
1002 bool UnusedTypeRemover::apply(Stage &stage)
1003 {
1004         stage.content.visit(*this);
1005         NodeRemover().apply(stage, unused_nodes);
1006         return !unused_nodes.empty();
1007 }
1008
1009 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1010 {
1011         unused_nodes.erase(expr->type);
1012         TraversingVisitor::visit(expr);
1013 }
1014
1015 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1016 {
1017         if(type.base_type)
1018                 unused_nodes.erase(type.base_type);
1019         unused_nodes.insert(&type);
1020 }
1021
1022 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1023 {
1024         if(type.base_type)
1025                 unused_nodes.erase(type.base_type);
1026         unused_nodes.insert(&type);
1027 }
1028
1029 void UnusedTypeRemover::visit(StructDeclaration &strct)
1030 {
1031         unused_nodes.insert(&strct);
1032         TraversingVisitor::visit(strct);
1033 }
1034
1035 void UnusedTypeRemover::visit(VariableDeclaration &var)
1036 {
1037         unused_nodes.erase(var.type_declaration);
1038         TraversingVisitor::visit(var);
1039 }
1040
1041 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1042 {
1043         unused_nodes.erase(iface.type_declaration);
1044 }
1045
1046 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1047 {
1048         unused_nodes.erase(func.return_type_declaration);
1049         TraversingVisitor::visit(func);
1050 }
1051
1052
1053 UnusedVariableRemover::UnusedVariableRemover():
1054         stage(0),
1055         interface_block(0),
1056         r_assignment(0),
1057         assignment_target(false),
1058         r_side_effects(false),
1059         in_struct(false),
1060         composite_reference(false),
1061         in_loop(0)
1062 { }
1063
1064 bool UnusedVariableRemover::apply(Stage &s)
1065 {
1066         stage = &s;
1067         s.content.visit(*this);
1068
1069         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1070                 if(i->used_by.empty())
1071                         unused_nodes.insert(i->node);
1072
1073         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1074         {
1075                 if(i->second.output)
1076                 {
1077                         /* The last visible assignments of output variables are used by the
1078                         next stage or the API. */
1079                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1080                                 unused_nodes.erase((*j)->node);
1081                 }
1082
1083                 if(!i->second.output && !i->second.referenced)
1084                 {
1085                         // Don't remove variables from inside interface blocks.
1086                         if(!i->second.interface_block)
1087                                 unused_nodes.insert(i->first);
1088                 }
1089                 else if(i->second.interface_block)
1090                         // Interface blocks are kept if even one member is used.
1091                         unused_nodes.erase(i->second.interface_block);
1092         }
1093
1094         NodeRemover().apply(s, unused_nodes);
1095
1096         return !unused_nodes.empty();
1097 }
1098
1099 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1100 {
1101         VariableInfo &var_info = variables[target.declaration];
1102         var_info.referenced = true;
1103         if(!assignment_target)
1104         {
1105                 bool loop_external = false;
1106                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1107                 {
1108                         bool covered = true;
1109                         for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1110                         {
1111                                 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1112                                 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1113                                 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1114                                 {
1115                                         unsigned index1 = (*i)->target.chain[j]&0x3F;
1116                                         unsigned index2 = target.chain[j]&0x3F;
1117                                         if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1118                                                 covered = index1&index2;
1119                                         else if(type1==Assignment::Target::ARRAY && index1<4)
1120                                                 covered = index2&(1<<index1);
1121                                         else if(type2==Assignment::Target::ARRAY && index2<4)
1122                                                 covered = index1&(1<<index2);
1123                                         /* If it's some other combination (shouldn't happen), leave
1124                                         covered as true */
1125                                 }
1126                                 else
1127                                         covered = ((*i)->target.chain[j]==target.chain[j]);
1128                         }
1129
1130                         if(covered)
1131                         {
1132                                 (*i)->used_by.push_back(&node);
1133                                 if((*i)->in_loop<in_loop)
1134                                         loop_external = true;
1135                         }
1136                 }
1137
1138                 if(loop_external)
1139                         loop_ext_refs.push_back(&node);
1140         }
1141 }
1142
1143 void UnusedVariableRemover::visit(VariableReference &var)
1144 {
1145         if(composite_reference)
1146                 r_reference.declaration = var.declaration;
1147         else
1148                 referenced(var.declaration, var);
1149 }
1150
1151 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1152 {
1153         if(composite_reference)
1154                 r_reference.declaration = iface.declaration;
1155         else
1156                 referenced(iface.declaration, iface);
1157 }
1158
1159 void UnusedVariableRemover::visit_composite(Expression &expr)
1160 {
1161         if(!composite_reference)
1162                 r_reference = Assignment::Target();
1163
1164         SetFlag set_composite(composite_reference);
1165         expr.visit(*this);
1166 }
1167
1168 void UnusedVariableRemover::visit(MemberAccess &memacc)
1169 {
1170         visit_composite(*memacc.left);
1171
1172         add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1173
1174         if(!composite_reference && r_reference.declaration)
1175                 referenced(r_reference, memacc);
1176 }
1177
1178 void UnusedVariableRemover::visit(Swizzle &swizzle)
1179 {
1180         visit_composite(*swizzle.left);
1181
1182         unsigned mask = 0;
1183         for(unsigned i=0; i<swizzle.count; ++i)
1184                 mask |= 1<<swizzle.components[i];
1185         add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1186
1187         if(!composite_reference && r_reference.declaration)
1188                 referenced(r_reference, swizzle);
1189 }
1190
1191 void UnusedVariableRemover::visit(UnaryExpression &unary)
1192 {
1193         TraversingVisitor::visit(unary);
1194         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1195                 r_side_effects = true;
1196 }
1197
1198 void UnusedVariableRemover::visit(BinaryExpression &binary)
1199 {
1200         if(binary.oper->token[0]=='[')
1201         {
1202                 visit_composite(*binary.left);
1203
1204                 {
1205                         SetFlag clear_assignment(assignment_target, false);
1206                         SetFlag clear_composite(composite_reference, false);
1207                         binary.right->visit(*this);
1208                 }
1209
1210                 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1211
1212                 if(!composite_reference && r_reference.declaration)
1213                         referenced(r_reference, binary);
1214         }
1215         else
1216         {
1217                 SetFlag clear_composite(composite_reference, false);
1218                 TraversingVisitor::visit(binary);
1219         }
1220 }
1221
1222 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1223 {
1224         SetFlag clear_composite(composite_reference, false);
1225         TraversingVisitor::visit(ternary);
1226 }
1227
1228 void UnusedVariableRemover::visit(Assignment &assign)
1229 {
1230         {
1231                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1232                 assign.left->visit(*this);
1233         }
1234         assign.right->visit(*this);
1235         r_assignment = &assign;
1236         r_side_effects = true;
1237 }
1238
1239 void UnusedVariableRemover::visit(FunctionCall &call)
1240 {
1241         SetFlag clear_composite(composite_reference, false);
1242         TraversingVisitor::visit(call);
1243         /* Treat function calls as having side effects so expression statements
1244         consisting of nothing but a function call won't be optimized away. */
1245         r_side_effects = true;
1246
1247         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1248         {
1249                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1250                         if(i->second.output)
1251                                 referenced(i->first, call);
1252         }
1253 }
1254
1255 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1256 {
1257         assignments.push_back(AssignmentInfo());
1258         AssignmentInfo &assign_info = assignments.back();
1259         assign_info.node = &node;
1260         assign_info.target = target;
1261         assign_info.in_loop = in_loop;
1262
1263         /* An assignment to the target hides any assignments to the same target or
1264         its subfields. */
1265         VariableInfo &var_info = variables[target.declaration];
1266         for(unsigned i=0; i<var_info.assignments.size(); ++i)
1267         {
1268                 const Assignment::Target &t = var_info.assignments[i]->target;
1269
1270                 bool subfield = (t.chain_len>=target.chain_len);
1271                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1272                         subfield = (t.chain[j]==target.chain[j]);
1273
1274                 if(subfield)
1275                         var_info.assignments.erase(var_info.assignments.begin()+i);
1276                 else
1277                         ++i;
1278         }
1279
1280         var_info.assignments.push_back(&assign_info);
1281 }
1282
1283 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1284 {
1285         r_assignment = 0;
1286         r_side_effects = false;
1287         TraversingVisitor::visit(expr);
1288         if(r_assignment && r_assignment->target.declaration)
1289                 record_assignment(r_assignment->target, expr);
1290         if(!r_side_effects)
1291                 unused_nodes.insert(&expr);
1292 }
1293
1294 void UnusedVariableRemover::visit(StructDeclaration &strct)
1295 {
1296         SetFlag set_struct(in_struct);
1297         TraversingVisitor::visit(strct);
1298 }
1299
1300 void UnusedVariableRemover::visit(VariableDeclaration &var)
1301 {
1302         TraversingVisitor::visit(var);
1303
1304         if(in_struct)
1305                 return;
1306
1307         VariableInfo &var_info = variables[&var];
1308         var_info.interface_block = interface_block;
1309
1310         /* Mark variables as output if they're used by the next stage or the
1311         graphics API. */
1312         if(interface_block)
1313                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1314         else
1315                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1316
1317         if(var.init_expression)
1318         {
1319                 var_info.initialized = true;
1320                 record_assignment(&var, *var.init_expression);
1321         }
1322 }
1323
1324 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1325 {
1326         VariableInfo &var_info = variables[&iface];
1327         var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1328 }
1329
1330 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1331 {
1332         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1333         {
1334                 BlockVariableMap::iterator j = variables.find(i->first);
1335                 if(j!=variables.end())
1336                 {
1337                         /* The merged blocks started as copies of each other so any common
1338                         assignments must be in the beginning. */
1339                         unsigned k = 0;
1340                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1341                                 if(i->second.assignments[k]!=j->second.assignments[k])
1342                                         break;
1343
1344                         // Remaining assignments are unique to each block; merge them.
1345                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1346                         j->second.referenced |= i->second.referenced;
1347                 }
1348                 else
1349                         variables.insert(*i);
1350         }
1351 }
1352
1353 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1354 {
1355         if(func.body.body.empty())
1356                 return;
1357
1358         BlockVariableMap saved_vars = variables;
1359         // Assignments from other functions should not be visible.
1360         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1361                 i->second.assignments.resize(i->second.initialized);
1362         TraversingVisitor::visit(func);
1363         swap(variables, saved_vars);
1364         merge_variables(saved_vars);
1365
1366         /* Always treat function parameters as referenced.  Removing unused
1367         parameters is not currently supported. */
1368         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1369         {
1370                 BlockVariableMap::iterator j = variables.find(i->get());
1371                 if(j!=variables.end())
1372                         j->second.referenced = true;
1373         }
1374 }
1375
1376 void UnusedVariableRemover::visit(Conditional &cond)
1377 {
1378         cond.condition->visit(*this);
1379         BlockVariableMap saved_vars = variables;
1380         cond.body.visit(*this);
1381         swap(saved_vars, variables);
1382         cond.else_body.visit(*this);
1383
1384         /* Visible assignments after the conditional is the union of those visible
1385         at the end of the if and else blocks.  If there was no else block, then it's
1386         the union of the if block and the state before it. */
1387         merge_variables(saved_vars);
1388 }
1389
1390 void UnusedVariableRemover::visit(Iteration &iter)
1391 {
1392         BlockVariableMap saved_vars = variables;
1393         vector<Node *> saved_refs;
1394         swap(loop_ext_refs, saved_refs);
1395         {
1396                 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1397                 TraversingVisitor::visit(iter);
1398         }
1399         swap(loop_ext_refs, saved_refs);
1400
1401         /* Visit the external references of the loop again to record assignments
1402         done in the loop as used. */
1403         for(vector<Node *>::const_iterator i=saved_refs.begin(); i!=saved_refs.end(); ++i)
1404                 (*i)->visit(*this);
1405
1406         /* Merge assignments from the iteration, without clearing previous state.
1407         Further analysis is needed to determine which parts of the iteration body
1408         are always executed, if any. */
1409         merge_variables(saved_vars);
1410 }
1411
1412
1413 bool UnusedFunctionRemover::apply(Stage &stage)
1414 {
1415         stage.content.visit(*this);
1416         NodeRemover().apply(stage, unused_nodes);
1417         return !unused_nodes.empty();
1418 }
1419
1420 void UnusedFunctionRemover::visit(FunctionCall &call)
1421 {
1422         TraversingVisitor::visit(call);
1423
1424         unused_nodes.erase(call.declaration);
1425         if(call.declaration && call.declaration->definition!=call.declaration)
1426                 used_definitions.insert(call.declaration->definition);
1427 }
1428
1429 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1430 {
1431         TraversingVisitor::visit(func);
1432
1433         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1434                 unused_nodes.insert(&func);
1435 }
1436
1437 } // namespace SL
1438 } // namespace GL
1439 } // namespace Msp