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