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