source/glsl/optimize.cpp

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