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 }
 661
 662 void ConstantFolder::visit(Literal &literal)
 663 {
 664         set_result(literal.value, true);
 665 }
 666
 667 void ConstantFolder::visit(VariableReference &var)
 668 {
 669         /* If an iteration variable is initialized with a constant value, return
 670         that value here for the purpose of evaluating the loop condition for the
 671         first iteration. */
 672         if(var.declaration==iteration_var)
 673         {
 674                 set_result(iter_init_value);
 675                 r_uses_iter_var = true;
 676         }
 677 }
 678
 679 void ConstantFolder::visit(MemberAccess &memacc)
 680 {
 681         TraversingVisitor::visit(memacc);
 682         r_constant = false;
 683 }
 684
 685 void ConstantFolder::visit(Swizzle &swizzle)
 686 {
 687         TraversingVisitor::visit(swizzle);
 688         r_constant = false;
 689 }
 690
 691 void ConstantFolder::visit(UnaryExpression &unary)
 692 {
 693         TraversingVisitor::visit(unary);
 694         bool can_fold = r_constant;
 695         r_constant = false;
 696         if(!can_fold)
 697                 return;
 698
 699         char oper = unary.oper->token[0];
 700         char oper2 = unary.oper->token[1];
 701         if(oper=='!')
 702         {
 703                 if(r_constant_value.check_type<bool>())
 704                         set_result(!r_constant_value.value<bool>());
 705         }
 706         else if(oper=='~')
 707         {
 708                 if(r_constant_value.check_type<int>())
 709                         set_result(~r_constant_value.value<int>());
 710                 else if(r_constant_value.check_type<unsigned>())
 711                         set_result(~r_constant_value.value<unsigned>());
 712         }
 713         else if(oper=='-' && !oper2)
 714         {
 715                 if(r_constant_value.check_type<int>())
 716                         set_result(-r_constant_value.value<int>());
 717                 else if(r_constant_value.check_type<unsigned>())
 718                         set_result(-r_constant_value.value<unsigned>());
 719                 else if(r_constant_value.check_type<float>())
 720                         set_result(-r_constant_value.value<float>());
 721         }
 722 }
 723
 724 void ConstantFolder::visit(BinaryExpression &binary)
 725 {
 726         visit(binary.left);
 727         bool left_constant = r_constant;
 728         bool left_iter_var = r_uses_iter_var;
 729         Variant left_value = r_constant_value;
 730         visit(binary.right);
 731         if(left_iter_var)
 732                 r_uses_iter_var = true;
 733
 734         bool can_fold = (left_constant && r_constant);
 735         r_constant = false;
 736         if(!can_fold)
 737                 return;
 738
 739         // Currently only expressions with both sides of equal types are handled.
 740         if(!left_value.check_same_type(r_constant_value))
 741                 return;
 742
 743         char oper = binary.oper->token[0];
 744         char oper2 = binary.oper->token[1];
 745         if(oper=='&' || oper=='|' || oper=='^')
 746         {
 747                 if(oper2==oper && left_value.check_type<bool>())
 748                         set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
 749                 else if(!oper2 && left_value.check_type<int>())
 750                         set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
 751                 else if(!oper2 && left_value.check_type<unsigned>())
 752                         set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 753         }
 754         else if((oper=='<' || oper=='>') && oper2!=oper)
 755         {
 756                 if(left_value.check_type<int>())
 757                         set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
 758                 else if(left_value.check_type<unsigned>())
 759                         set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 760                 else if(left_value.check_type<float>())
 761                         set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
 762         }
 763         else if((oper=='=' || oper=='!') && oper2=='=')
 764         {
 765                 if(left_value.check_type<int>())
 766                         set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
 767                 else if(left_value.check_type<unsigned>())
 768                         set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
 769                 else if(left_value.check_type<float>())
 770                         set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
 771         }
 772         else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
 773         {
 774                 if(left_value.check_type<int>())
 775                         set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
 776                 else if(left_value.check_type<unsigned>())
 777                         set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 778                 else if(left_value.check_type<float>())
 779                         set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
 780         }
 781         else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
 782         {
 783                 if(left_value.check_type<int>())
 784                         set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
 785                 else if(left_value.check_type<unsigned>())
 786                         set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 787         }
 788 }
 789
 790 void ConstantFolder::visit(Assignment &assign)
 791 {
 792         TraversingVisitor::visit(assign);
 793         r_constant = false;
 794 }
 795
 796 void ConstantFolder::visit(TernaryExpression &ternary)
 797 {
 798         TraversingVisitor::visit(ternary);
 799         r_constant = false;
 800 }
 801
 802 void ConstantFolder::visit(FunctionCall &call)
 803 {
 804         if(call.constructor && call.type && call.arguments.size()==1)
 805         {
 806                 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
 807                 if(basic)
 808                 {
 809                         call.arguments[0]->visit(*this);
 810                         bool can_fold = r_constant;
 811                         r_constant = false;
 812                         if(!can_fold)
 813                                 return;
 814
 815                         if(basic->kind==BasicTypeDeclaration::BOOL)
 816                                 convert_to_result<bool>(r_constant_value);
 817                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
 818                                 convert_to_result<int>(r_constant_value);
 819                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
 820                                 convert_to_result<unsigned>(r_constant_value);
 821                         else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
 822                                 convert_to_result<float>(r_constant_value);
 823
 824                         return;
 825                 }
 826         }
 827
 828         TraversingVisitor::visit(call);
 829         r_constant = false;
 830 }
 831
 832 void ConstantFolder::visit(VariableDeclaration &var)
 833 {
 834         if(iteration_init && var.init_expression)
 835         {
 836                 visit(var.init_expression);
 837                 if(r_constant)
 838                 {
 839                         /* Record the value of a constant initialization expression of an
 840                         iteration, so it can be used to evaluate the loop condition. */
 841                         iteration_var = &var;
 842                         iter_init_value = r_constant_value;
 843                 }
 844         }
 845         else
 846                 TraversingVisitor::visit(var);
 847 }
 848
 849 void ConstantFolder::visit(Iteration &iter)
 850 {
 851         SetForScope<Block *> set_block(current_block, &iter.body);
 852
 853         /* The iteration variable is not normally inlined into expressions, so we
 854         process it specially here.  If the initial value causes the loop condition
 855         to evaluate to false, then the expression can be folded. */
 856         iteration_var = 0;
 857         if(iter.init_statement)
 858         {
 859                 SetFlag set_init(iteration_init);
 860                 iter.init_statement->visit(*this);
 861         }
 862
 863         if(iter.condition)
 864         {
 865                 visit(iter.condition);
 866                 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
 867                 {
 868                         RefPtr<Literal> literal = new Literal;
 869                         literal->token = "false";
 870                         literal->value = r_constant_value;
 871                         iter.condition = literal;
 872                 }
 873         }
 874         iteration_var = 0;
 875
 876         iter.body.visit(*this);
 877         if(iter.loop_expression)
 878                 visit(iter.loop_expression);
 879 }
 880
 881
 882 void ConstantConditionEliminator::apply(Stage &stage)
 883 {
 884         stage.content.visit(*this);
 885         NodeRemover().apply(stage, nodes_to_remove);
 886 }
 887
 888 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
 889 {
 890         if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
 891                 if(literal->value.check_type<bool>())
 892                         return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
 893         return NOT_CONSTANT;
 894 }
 895
 896 void ConstantConditionEliminator::visit(Block &block)
 897 {
 898         SetForScope<Block *> set_block(current_block, &block);
 899         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 900         {
 901                 insert_point = i;
 902                 (*i)->visit(*this);
 903         }
 904 }
 905
 906 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
 907 {
 908         r_ternary_result = 0;
 909         expr->visit(*this);
 910         if(r_ternary_result)
 911                 expr = r_ternary_result;
 912         r_ternary_result = 0;
 913 }
 914
 915 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
 916 {
 917         ConstantStatus result = check_constant_condition(*ternary.condition);
 918         if(result!=NOT_CONSTANT)
 919                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
 920         else
 921                 r_ternary_result = 0;
 922 }
 923
 924 void ConstantConditionEliminator::visit(Conditional &cond)
 925 {
 926         ConstantStatus result = check_constant_condition(*cond.condition);
 927         if(result!=NOT_CONSTANT)
 928         {
 929                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
 930                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
 931                 current_block->body.splice(insert_point, block.body);
 932                 nodes_to_remove.insert(&cond);
 933                 return;
 934         }
 935
 936         TraversingVisitor::visit(cond);
 937 }
 938
 939 void ConstantConditionEliminator::visit(Iteration &iter)
 940 {
 941         if(iter.condition)
 942         {
 943                 ConstantStatus result = check_constant_condition(*iter.condition);
 944                 if(result==CONSTANT_FALSE)
 945                 {
 946                         nodes_to_remove.insert(&iter);
 947                         return;
 948                 }
 949         }
 950
 951         TraversingVisitor::visit(iter);
 952 }
 953
 954
 955 UnreachableCodeRemover::UnreachableCodeRemover():
 956         reachable(true)
 957 { }
 958
 959 bool UnreachableCodeRemover::apply(Stage &stage)
 960 {
 961         stage.content.visit(*this);
 962         NodeRemover().apply(stage, unreachable_nodes);
 963         return !unreachable_nodes.empty();
 964 }
 965
 966 void UnreachableCodeRemover::visit(Block &block)
 967 {
 968         NodeList<Statement>::iterator i = block.body.begin();
 969         for(; (reachable && i!=block.body.end()); ++i)
 970                 (*i)->visit(*this);
 971         for(; i!=block.body.end(); ++i)
 972                 unreachable_nodes.insert(i->get());
 973 }
 974
 975 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
 976 {
 977         TraversingVisitor::visit(func);
 978         reachable = true;
 979 }
 980
 981 void UnreachableCodeRemover::visit(Conditional &cond)
 982 {
 983         cond.body.visit(*this);
 984         bool reachable_if_true = reachable;
 985         reachable = true;
 986         cond.else_body.visit(*this);
 987
 988         reachable |= reachable_if_true;
 989 }
 990
 991 void UnreachableCodeRemover::visit(Iteration &iter)
 992 {
 993         TraversingVisitor::visit(iter);
 994
 995         /* Always consider code after a loop reachable, since there's no checking
 996         for whether the loop executes. */
 997         reachable = true;
 998 }
 999
1000
1001 bool UnusedTypeRemover::apply(Stage &stage)
1002 {
1003         stage.content.visit(*this);
1004         NodeRemover().apply(stage, unused_nodes);
1005         return !unused_nodes.empty();
1006 }
1007
1008 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1009 {
1010         unused_nodes.erase(expr->type);
1011         TraversingVisitor::visit(expr);
1012 }
1013
1014 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1015 {
1016         if(type.base_type)
1017                 unused_nodes.erase(type.base_type);
1018         unused_nodes.insert(&type);
1019 }
1020
1021 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1022 {
1023         if(type.base_type)
1024                 unused_nodes.erase(type.base_type);
1025         unused_nodes.insert(&type);
1026 }
1027
1028 void UnusedTypeRemover::visit(StructDeclaration &strct)
1029 {
1030         unused_nodes.insert(&strct);
1031         TraversingVisitor::visit(strct);
1032 }
1033
1034 void UnusedTypeRemover::visit(VariableDeclaration &var)
1035 {
1036         unused_nodes.erase(var.type_declaration);
1037         TraversingVisitor::visit(var);
1038 }
1039
1040 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1041 {
1042         unused_nodes.erase(iface.type_declaration);
1043 }
1044
1045 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1046 {
1047         unused_nodes.erase(func.return_type_declaration);
1048         TraversingVisitor::visit(func);
1049 }
1050
1051
1052 UnusedVariableRemover::UnusedVariableRemover():
1053         stage(0),
1054         interface_block(0),
1055         r_assignment(0),
1056         assignment_target(false),
1057         r_side_effects(false),
1058         in_struct(false),
1059         composite_reference(false),
1060         in_loop(0)
1061 { }
1062
1063 bool UnusedVariableRemover::apply(Stage &s)
1064 {
1065         stage = &s;
1066         s.content.visit(*this);
1067
1068         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1069                 if(i->used_by.empty())
1070                         unused_nodes.insert(i->node);
1071
1072         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1073         {
1074                 if(i->second.output)
1075                 {
1076                         /* The last visible assignments of output variables are used by the
1077                         next stage or the API. */
1078                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1079                                 unused_nodes.erase((*j)->node);
1080                 }
1081
1082                 if(!i->second.output && !i->second.referenced)
1083                 {
1084                         // Don't remove variables from inside interface blocks.
1085                         if(!i->second.interface_block)
1086                                 unused_nodes.insert(i->first);
1087                 }
1088                 else if(i->second.interface_block)
1089                         // Interface blocks are kept if even one member is used.
1090                         unused_nodes.erase(i->second.interface_block);
1091         }
1092
1093         NodeRemover().apply(s, unused_nodes);
1094
1095         return !unused_nodes.empty();
1096 }
1097
1098 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1099 {
1100         VariableInfo &var_info = variables[target.declaration];
1101         var_info.referenced = true;
1102         if(!assignment_target)
1103         {
1104                 bool loop_external = false;
1105                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1106                 {
1107                         bool covered = true;
1108                         for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1109                         {
1110                                 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1111                                 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1112                                 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1113                                 {
1114                                         unsigned index1 = (*i)->target.chain[j]&0x3F;
1115                                         unsigned index2 = target.chain[j]&0x3F;
1116                                         if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1117                                                 covered = index1&index2;
1118                                         else if(type1==Assignment::Target::ARRAY && index1<4)
1119                                                 covered = index2&(1<<index1);
1120                                         else if(type2==Assignment::Target::ARRAY && index2<4)
1121                                                 covered = index1&(1<<index2);
1122                                         /* If it's some other combination (shouldn't happen), leave
1123                                         covered as true */
1124                                 }
1125                                 else
1126                                         covered = ((*i)->target.chain[j]==target.chain[j]);
1127                         }
1128
1129                         if(covered)
1130                         {
1131                                 (*i)->used_by.push_back(&node);
1132                                 if((*i)->in_loop<in_loop)
1133                                         loop_external = true;
1134                         }
1135                 }
1136
1137                 if(loop_external)
1138                         loop_ext_refs.push_back(&node);
1139         }
1140 }
1141
1142 void UnusedVariableRemover::visit(VariableReference &var)
1143 {
1144         if(composite_reference)
1145                 r_reference.declaration = var.declaration;
1146         else
1147                 referenced(var.declaration, var);
1148 }
1149
1150 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1151 {
1152         if(composite_reference)
1153                 r_reference.declaration = iface.declaration;
1154         else
1155                 referenced(iface.declaration, iface);
1156 }
1157
1158 void UnusedVariableRemover::visit_composite(Expression &expr)
1159 {
1160         if(!composite_reference)
1161                 r_reference = Assignment::Target();
1162
1163         SetFlag set_composite(composite_reference);
1164         expr.visit(*this);
1165 }
1166
1167 void UnusedVariableRemover::visit(MemberAccess &memacc)
1168 {
1169         visit_composite(*memacc.left);
1170
1171         add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1172
1173         if(!composite_reference && r_reference.declaration)
1174                 referenced(r_reference, memacc);
1175 }
1176
1177 void UnusedVariableRemover::visit(Swizzle &swizzle)
1178 {
1179         visit_composite(*swizzle.left);
1180
1181         unsigned mask = 0;
1182         for(unsigned i=0; i<swizzle.count; ++i)
1183                 mask |= 1<<swizzle.components[i];
1184         add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1185
1186         if(!composite_reference && r_reference.declaration)
1187                 referenced(r_reference, swizzle);
1188 }
1189
1190 void UnusedVariableRemover::visit(UnaryExpression &unary)
1191 {
1192         TraversingVisitor::visit(unary);
1193         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1194                 r_side_effects = true;
1195 }
1196
1197 void UnusedVariableRemover::visit(BinaryExpression &binary)
1198 {
1199         if(binary.oper->token[0]=='[')
1200         {
1201                 visit_composite(*binary.left);
1202
1203                 {
1204                         SetFlag clear_assignment(assignment_target, false);
1205                         SetFlag clear_composite(composite_reference, false);
1206                         binary.right->visit(*this);
1207                 }
1208
1209                 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1210
1211                 if(!composite_reference && r_reference.declaration)
1212                         referenced(r_reference, binary);
1213         }
1214         else
1215         {
1216                 SetFlag clear_composite(composite_reference, false);
1217                 TraversingVisitor::visit(binary);
1218         }
1219 }
1220
1221 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1222 {
1223         SetFlag clear_composite(composite_reference, false);
1224         TraversingVisitor::visit(ternary);
1225 }
1226
1227 void UnusedVariableRemover::visit(Assignment &assign)
1228 {
1229         {
1230                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1231                 assign.left->visit(*this);
1232         }
1233         assign.right->visit(*this);
1234         r_assignment = &assign;
1235         r_side_effects = true;
1236 }
1237
1238 void UnusedVariableRemover::visit(FunctionCall &call)
1239 {
1240         SetFlag clear_composite(composite_reference, false);
1241         TraversingVisitor::visit(call);
1242         /* Treat function calls as having side effects so expression statements
1243         consisting of nothing but a function call won't be optimized away. */
1244         r_side_effects = true;
1245
1246         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1247         {
1248                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1249                         if(i->second.output)
1250                                 referenced(i->first, call);
1251         }
1252 }
1253
1254 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1255 {
1256         assignments.push_back(AssignmentInfo());
1257         AssignmentInfo &assign_info = assignments.back();
1258         assign_info.node = &node;
1259         assign_info.target = target;
1260         assign_info.in_loop = in_loop;
1261
1262         /* An assignment to the target hides any assignments to the same target or
1263         its subfields. */
1264         VariableInfo &var_info = variables[target.declaration];
1265         for(unsigned i=0; i<var_info.assignments.size(); ++i)
1266         {
1267                 const Assignment::Target &t = var_info.assignments[i]->target;
1268
1269                 bool subfield = (t.chain_len>=target.chain_len);
1270                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1271                         subfield = (t.chain[j]==target.chain[j]);
1272
1273                 if(subfield)
1274                         var_info.assignments.erase(var_info.assignments.begin()+i);
1275                 else
1276                         ++i;
1277         }
1278
1279         var_info.assignments.push_back(&assign_info);
1280 }
1281
1282 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1283 {
1284         r_assignment = 0;
1285         r_side_effects = false;
1286         TraversingVisitor::visit(expr);
1287         if(r_assignment && r_assignment->target.declaration)
1288                 record_assignment(r_assignment->target, expr);
1289         if(!r_side_effects)
1290                 unused_nodes.insert(&expr);
1291 }
1292
1293 void UnusedVariableRemover::visit(StructDeclaration &strct)
1294 {
1295         SetFlag set_struct(in_struct);
1296         TraversingVisitor::visit(strct);
1297 }
1298
1299 void UnusedVariableRemover::visit(VariableDeclaration &var)
1300 {
1301         TraversingVisitor::visit(var);
1302
1303         if(in_struct)
1304                 return;
1305
1306         VariableInfo &var_info = variables[&var];
1307         var_info.interface_block = interface_block;
1308
1309         /* Mark variables as output if they're used by the next stage or the
1310         graphics API. */
1311         if(interface_block)
1312                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1313         else
1314                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1315
1316         if(var.init_expression)
1317         {
1318                 var_info.initialized = true;
1319                 record_assignment(&var, *var.init_expression);
1320         }
1321 }
1322
1323 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1324 {
1325         VariableInfo &var_info = variables[&iface];
1326         var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1327 }
1328
1329 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1330 {
1331         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1332         {
1333                 BlockVariableMap::iterator j = variables.find(i->first);
1334                 if(j!=variables.end())
1335                 {
1336                         /* The merged blocks started as copies of each other so any common
1337                         assignments must be in the beginning. */
1338                         unsigned k = 0;
1339                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1340                                 if(i->second.assignments[k]!=j->second.assignments[k])
1341                                         break;
1342
1343                         // Remaining assignments are unique to each block; merge them.
1344                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1345                         j->second.referenced |= i->second.referenced;
1346                 }
1347                 else
1348                         variables.insert(*i);
1349         }
1350 }
1351
1352 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1353 {
1354         if(func.body.body.empty())
1355                 return;
1356
1357         BlockVariableMap saved_vars = variables;
1358         // Assignments from other functions should not be visible.
1359         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1360                 i->second.assignments.resize(i->second.initialized);
1361         TraversingVisitor::visit(func);
1362         swap(variables, saved_vars);
1363         merge_variables(saved_vars);
1364
1365         /* Always treat function parameters as referenced.  Removing unused
1366         parameters is not currently supported. */
1367         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1368         {
1369                 BlockVariableMap::iterator j = variables.find(i->get());
1370                 if(j!=variables.end())
1371                         j->second.referenced = true;
1372         }
1373 }
1374
1375 void UnusedVariableRemover::visit(Conditional &cond)
1376 {
1377         cond.condition->visit(*this);
1378         BlockVariableMap saved_vars = variables;
1379         cond.body.visit(*this);
1380         swap(saved_vars, variables);
1381         cond.else_body.visit(*this);
1382
1383         /* Visible assignments after the conditional is the union of those visible
1384         at the end of the if and else blocks.  If there was no else block, then it's
1385         the union of the if block and the state before it. */
1386         merge_variables(saved_vars);
1387 }
1388
1389 void UnusedVariableRemover::visit(Iteration &iter)
1390 {
1391         BlockVariableMap saved_vars = variables;
1392         vector<Node *> saved_refs;
1393         swap(loop_ext_refs, saved_refs);
1394         {
1395                 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1396                 TraversingVisitor::visit(iter);
1397         }
1398         swap(loop_ext_refs, saved_refs);
1399
1400         /* Visit the external references of the loop again to record assignments
1401         done in the loop as used. */
1402         for(vector<Node *>::const_iterator i=saved_refs.begin(); i!=saved_refs.end(); ++i)
1403                 (*i)->visit(*this);
1404
1405         /* Merge assignments from the iteration, without clearing previous state.
1406         Further analysis is needed to determine which parts of the iteration body
1407         are always executed, if any. */
1408         merge_variables(saved_vars);
1409 }
1410
1411
1412 bool UnusedFunctionRemover::apply(Stage &stage)
1413 {
1414         stage.content.visit(*this);
1415         NodeRemover().apply(stage, unused_nodes);
1416         return !unused_nodes.empty();
1417 }
1418
1419 void UnusedFunctionRemover::visit(FunctionCall &call)
1420 {
1421         TraversingVisitor::visit(call);
1422
1423         unused_nodes.erase(call.declaration);
1424         if(call.declaration && call.declaration->definition!=call.declaration)
1425                 used_definitions.insert(call.declaration->definition);
1426 }
1427
1428 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1429 {
1430         TraversingVisitor::visit(func);
1431
1432         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1433                 unused_nodes.insert(&func);
1434 }
1435
1436 } // namespace SL
1437 } // namespace GL
1438 } // namespace Msp