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