source/glsl/optimize.cpp

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