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         unused_nodes.insert(&type);
1233 }
1234
1235 void UnusedTypeRemover::visit(StructDeclaration &strct)
1236 {
1237         unused_nodes.insert(&strct);
1238         TraversingVisitor::visit(strct);
1239 }
1240
1241 void UnusedTypeRemover::visit(VariableDeclaration &var)
1242 {
1243         unused_nodes.erase(var.type_declaration);
1244         TraversingVisitor::visit(var);
1245 }
1246
1247 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1248 {
1249         unused_nodes.erase(func.return_type_declaration);
1250         TraversingVisitor::visit(func);
1251 }
1252
1253
1254 bool UnusedVariableRemover::apply(Stage &s)
1255 {
1256         stage = &s;
1257         s.content.visit(*this);
1258
1259         for(const AssignmentInfo &a: assignments)
1260                 if(a.used_by.empty())
1261                         unused_nodes.insert(a.node);
1262
1263         for(const auto &kvp: variables)
1264         {
1265                 if(!kvp.second.referenced)
1266                         unused_nodes.insert(kvp.first);
1267                 else if(kvp.second.output)
1268                 {
1269                         /* The last visible assignments of output variables are used by the
1270                         next stage or the API. */
1271                         for(AssignmentInfo *a: kvp.second.assignments)
1272                                 unused_nodes.erase(a->node);
1273                 }
1274         }
1275
1276         NodeRemover().apply(s, unused_nodes);
1277
1278         return !unused_nodes.empty();
1279 }
1280
1281 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1282 {
1283         VariableInfo &var_info = variables[target.declaration];
1284         var_info.referenced = true;
1285         if(!assignment_target)
1286         {
1287                 bool loop_external = false;
1288                 for(AssignmentInfo *a: var_info.assignments)
1289                         if(targets_overlap(a->target, target))
1290                         {
1291                                 a->used_by.push_back(&node);
1292                                 if(a->in_loop<in_loop)
1293                                         loop_external = true;
1294                         }
1295
1296                 if(loop_external)
1297                         loop_ext_refs.push_back(&node);
1298         }
1299 }
1300
1301 void UnusedVariableRemover::visit(VariableReference &var)
1302 {
1303         if(composite_reference)
1304                 r_reference.declaration = var.declaration;
1305         else if(var.declaration)
1306                 referenced(var.declaration, var);
1307 }
1308
1309 void UnusedVariableRemover::visit_composite(Expression &expr)
1310 {
1311         if(!composite_reference)
1312                 r_reference = Assignment::Target();
1313
1314         SetFlag set_composite(composite_reference);
1315         expr.visit(*this);
1316 }
1317
1318 void UnusedVariableRemover::visit(MemberAccess &memacc)
1319 {
1320         visit_composite(*memacc.left);
1321
1322         add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1323
1324         if(!composite_reference && r_reference.declaration)
1325                 referenced(r_reference, memacc);
1326 }
1327
1328 void UnusedVariableRemover::visit(Swizzle &swizzle)
1329 {
1330         visit_composite(*swizzle.left);
1331
1332         unsigned mask = 0;
1333         for(unsigned i=0; i<swizzle.count; ++i)
1334                 mask |= 1<<swizzle.components[i];
1335         add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1336
1337         if(!composite_reference && r_reference.declaration)
1338                 referenced(r_reference, swizzle);
1339 }
1340
1341 void UnusedVariableRemover::visit(UnaryExpression &unary)
1342 {
1343         TraversingVisitor::visit(unary);
1344         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1345                 r_side_effects = true;
1346 }
1347
1348 void UnusedVariableRemover::visit(BinaryExpression &binary)
1349 {
1350         if(binary.oper->token[0]=='[')
1351         {
1352                 visit_composite(*binary.left);
1353
1354                 {
1355                         SetFlag clear_assignment(assignment_target, false);
1356                         SetFlag clear_composite(composite_reference, false);
1357                         SetForScope<Assignment::Target> clear_reference(r_reference, Assignment::Target());
1358                         binary.right->visit(*this);
1359                 }
1360
1361                 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1362
1363                 if(!composite_reference && r_reference.declaration)
1364                         referenced(r_reference, binary);
1365         }
1366         else
1367         {
1368                 SetFlag clear_composite(composite_reference, false);
1369                 TraversingVisitor::visit(binary);
1370         }
1371 }
1372
1373 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1374 {
1375         SetFlag clear_composite(composite_reference, false);
1376         TraversingVisitor::visit(ternary);
1377 }
1378
1379 void UnusedVariableRemover::visit(Assignment &assign)
1380 {
1381         {
1382                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1383                 assign.left->visit(*this);
1384         }
1385         assign.right->visit(*this);
1386         r_assignment = &assign;
1387         r_side_effects = true;
1388 }
1389
1390 void UnusedVariableRemover::visit(FunctionCall &call)
1391 {
1392         SetFlag clear_composite(composite_reference, false);
1393         TraversingVisitor::visit(call);
1394         /* Treat function calls as having side effects so expression statements
1395         consisting of nothing but a function call won't be optimized away. */
1396         r_side_effects = true;
1397
1398         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1399         {
1400                 for(const auto &kvp: variables)
1401                         if(kvp.second.output)
1402                                 referenced(kvp.first, call);
1403         }
1404 }
1405
1406 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1407 {
1408         assignments.emplace_back();
1409         AssignmentInfo &assign_info = assignments.back();
1410         assign_info.node = &node;
1411         assign_info.target = target;
1412         assign_info.in_loop = in_loop;
1413
1414         /* An assignment to the target hides any assignments to the same target or
1415         its subfields. */
1416         VariableInfo &var_info = variables[target.declaration];
1417         for(unsigned i=0; i<var_info.assignments.size(); )
1418         {
1419                 const Assignment::Target &t = var_info.assignments[i]->target;
1420
1421                 bool subfield = (t.chain_len>=target.chain_len);
1422                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1423                         subfield = (t.chain[j]==target.chain[j]);
1424
1425                 if(subfield)
1426                         var_info.assignments.erase(var_info.assignments.begin()+i);
1427                 else
1428                         ++i;
1429         }
1430
1431         var_info.assignments.push_back(&assign_info);
1432 }
1433
1434 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1435 {
1436         r_assignment = 0;
1437         r_side_effects = false;
1438         TraversingVisitor::visit(expr);
1439         if(r_assignment && r_assignment->target.declaration)
1440                 record_assignment(r_assignment->target, expr);
1441         if(!r_side_effects)
1442                 unused_nodes.insert(&expr);
1443 }
1444
1445 void UnusedVariableRemover::visit(StructDeclaration &strct)
1446 {
1447         SetFlag set_struct(in_struct);
1448         TraversingVisitor::visit(strct);
1449 }
1450
1451 void UnusedVariableRemover::visit(VariableDeclaration &var)
1452 {
1453         TraversingVisitor::visit(var);
1454
1455         if(in_struct)
1456                 return;
1457
1458         VariableInfo &var_info = variables[&var];
1459
1460         /* Mark variables as output if they're used by the next stage or the
1461         graphics API. */
1462         bool builtin = (!var.name.compare(0, 3, "gl_") || (var.block_declaration && !var.block_declaration->block_name.compare(0, 3, "gl_")));
1463         var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || builtin));
1464
1465         // Linked outputs are automatically referenced.
1466         if(var_info.output && var.linked_declaration)
1467                 var_info.referenced = true;
1468
1469         if(var.init_expression)
1470         {
1471                 var_info.initialized = true;
1472                 record_assignment(&var, *var.init_expression);
1473         }
1474 }
1475
1476 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1477 {
1478         for(const auto &kvp: other_vars)
1479         {
1480                 auto j = variables.find(kvp.first);
1481                 if(j!=variables.end())
1482                 {
1483                         /* The merged blocks started as copies of each other so any common
1484                         assignments must be in the beginning. */
1485                         unsigned k = 0;
1486                         for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1487                                 if(kvp.second.assignments[k]!=j->second.assignments[k])
1488                                         break;
1489
1490                         // Remaining assignments are unique to each block; merge them.
1491                         j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1492                         j->second.referenced |= kvp.second.referenced;
1493                 }
1494                 else
1495                         variables.insert(kvp);
1496         }
1497 }
1498
1499 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1500 {
1501         if(func.body.body.empty())
1502                 return;
1503
1504         BlockVariableMap saved_vars = variables;
1505         // Assignments from other functions should not be visible.
1506         for(auto &kvp: variables)
1507                 kvp.second.assignments.resize(kvp.second.initialized);
1508         TraversingVisitor::visit(func);
1509         swap(variables, saved_vars);
1510         merge_variables(saved_vars);
1511
1512         /* Always treat function parameters as referenced.  Removing unused
1513         parameters is not currently supported. */
1514         for(const RefPtr<VariableDeclaration> &p: func.parameters)
1515         {
1516                 auto j = variables.find(p.get());
1517                 if(j!=variables.end())
1518                         j->second.referenced = true;
1519         }
1520 }
1521
1522 void UnusedVariableRemover::visit(Conditional &cond)
1523 {
1524         cond.condition->visit(*this);
1525         BlockVariableMap saved_vars = variables;
1526         cond.body.visit(*this);
1527         swap(saved_vars, variables);
1528         cond.else_body.visit(*this);
1529
1530         /* Visible assignments after the conditional is the union of those visible
1531         at the end of the if and else blocks.  If there was no else block, then it's
1532         the union of the if block and the state before it. */
1533         merge_variables(saved_vars);
1534 }
1535
1536 void UnusedVariableRemover::visit(Iteration &iter)
1537 {
1538         BlockVariableMap saved_vars = variables;
1539         vector<Node *> saved_refs;
1540         swap(loop_ext_refs, saved_refs);
1541         {
1542                 if(iter.init_statement)
1543                         iter.init_statement->visit(*this);
1544                 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1545                 if(iter.condition)
1546                         iter.condition->visit(*this);
1547                 iter.body.visit(*this);
1548                 if(iter.loop_expression)
1549                         iter.loop_expression->visit(*this);
1550         }
1551         swap(loop_ext_refs, saved_refs);
1552
1553         /* Visit the external references of the loop again to record assignments
1554         done in the loop as used. */
1555         for(Node *n: saved_refs)
1556                 n->visit(*this);
1557
1558         /* Merge assignments from the iteration, without clearing previous state.
1559         Further analysis is needed to determine which parts of the iteration body
1560         are always executed, if any. */
1561         merge_variables(saved_vars);
1562 }
1563
1564
1565 bool UnusedFunctionRemover::apply(Stage &stage)
1566 {
1567         stage.content.visit(*this);
1568         NodeRemover().apply(stage, unused_nodes);
1569         return !unused_nodes.empty();
1570 }
1571
1572 void UnusedFunctionRemover::visit(FunctionCall &call)
1573 {
1574         TraversingVisitor::visit(call);
1575
1576         unused_nodes.erase(call.declaration);
1577         if(call.declaration && call.declaration->definition!=call.declaration)
1578                 used_definitions.insert(call.declaration->definition);
1579 }
1580
1581 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1582 {
1583         TraversingVisitor::visit(func);
1584
1585         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1586                 unused_nodes.insert(&func);
1587 }
1588
1589 } // namespace SL
1590 } // namespace GL
1591 } // namespace Msp