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 void AggregateDismantler::visit(FunctionDeclaration &func)
 721 {
 722         func.body.visit(*this);
 723 }
 724
 725
 726 template<typename T>
 727 T ConstantFolder::evaluate_logical(char oper, T left, T right)
 728 {
 729         switch(oper)
 730         {
 731         case '&': return left&right;
 732         case '|': return left|right;
 733         case '^': return left^right;
 734         default: return T();
 735         }
 736 }
 737
 738 template<typename T>
 739 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
 740 {
 741         switch(oper[0]|oper[1])
 742         {
 743         case '<': return left<right;
 744         case '<'|'=': return left<=right;
 745         case '>': return left>right;
 746         case '>'|'=': return left>=right;
 747         default: return false;
 748         }
 749 }
 750
 751 template<typename T>
 752 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
 753 {
 754         switch(oper)
 755         {
 756         case '+': return left+right;
 757         case '-': return left-right;
 758         case '*': return left*right;
 759         case '/': return left/right;
 760         default: return T();
 761         }
 762 }
 763
 764 template<typename T>
 765 T ConstantFolder::evaluate_int_special_op(char oper, T left, T right)
 766 {
 767         switch(oper)
 768         {
 769         case '%': return left%right;
 770         case '<': return left<<right;
 771         case '>': return left>>right;
 772         default: return T();
 773         }
 774 }
 775
 776 template<typename T>
 777 void ConstantFolder::convert_to_result(const Variant &value)
 778 {
 779         if(value.check_type<bool>())
 780                 set_result(static_cast<T>(value.value<bool>()));
 781         else if(value.check_type<int>())
 782                 set_result(static_cast<T>(value.value<int>()));
 783         else if(value.check_type<unsigned>())
 784                 set_result(static_cast<T>(value.value<unsigned>()));
 785         else if(value.check_type<float>())
 786                 set_result(static_cast<T>(value.value<float>()));
 787 }
 788
 789 void ConstantFolder::set_result(const Variant &value, bool literal)
 790 {
 791         r_constant_value = value;
 792         r_constant = true;
 793         r_literal = literal;
 794 }
 795
 796 void ConstantFolder::visit(RefPtr<Expression> &expr)
 797 {
 798         r_constant_value = Variant();
 799         r_constant = false;
 800         r_literal = false;
 801         r_uses_iter_var = false;
 802         expr->visit(*this);
 803         /* Don't replace literals since they'd only be replaced with an identical
 804         literal.  Also skip anything that uses an iteration variable, but pass on
 805         the result so the Iteration visiting function can handle it. */
 806         if(!r_constant || r_literal || r_uses_iter_var)
 807                 return;
 808
 809         RefPtr<Literal> literal = new Literal;
 810         if(r_constant_value.check_type<bool>())
 811                 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
 812         else if(r_constant_value.check_type<int>())
 813                 literal->token = lexical_cast<string>(r_constant_value.value<int>());
 814         else if(r_constant_value.check_type<unsigned>())
 815                 literal->token = lexical_cast<string>(r_constant_value.value<unsigned>())+"u";
 816         else if(r_constant_value.check_type<float>())
 817         {
 818                 literal->token = lexical_cast<string>(r_constant_value.value<float>(), Fmt().precision(8));
 819                 if(literal->token.find('.')==string::npos && literal->token.find('e')==string::npos)
 820                         literal->token += ".0";
 821         }
 822         else
 823         {
 824                 r_constant = false;
 825                 return;
 826         }
 827         literal->value = r_constant_value;
 828         expr = literal;
 829         r_any_folded = true;
 830 }
 831
 832 void ConstantFolder::visit(Literal &literal)
 833 {
 834         set_result(literal.value, true);
 835 }
 836
 837 void ConstantFolder::visit(VariableReference &var)
 838 {
 839         /* If an iteration variable is initialized with a constant value, return
 840         that value here for the purpose of evaluating the loop condition for the
 841         first iteration. */
 842         if(var.declaration==iteration_var)
 843         {
 844                 set_result(iter_init_value);
 845                 r_uses_iter_var = true;
 846         }
 847 }
 848
 849 void ConstantFolder::visit(MemberAccess &memacc)
 850 {
 851         TraversingVisitor::visit(memacc);
 852         r_constant = false;
 853 }
 854
 855 void ConstantFolder::visit(Swizzle &swizzle)
 856 {
 857         TraversingVisitor::visit(swizzle);
 858         r_constant = false;
 859 }
 860
 861 void ConstantFolder::visit(UnaryExpression &unary)
 862 {
 863         TraversingVisitor::visit(unary);
 864         bool can_fold = r_constant;
 865         r_constant = false;
 866         if(!can_fold)
 867                 return;
 868
 869         char oper = unary.oper->token[0];
 870         char oper2 = unary.oper->token[1];
 871         if(oper=='!')
 872         {
 873                 if(r_constant_value.check_type<bool>())
 874                         set_result(!r_constant_value.value<bool>());
 875         }
 876         else if(oper=='~')
 877         {
 878                 if(r_constant_value.check_type<int>())
 879                         set_result(~r_constant_value.value<int>());
 880                 else if(r_constant_value.check_type<unsigned>())
 881                         set_result(~r_constant_value.value<unsigned>());
 882         }
 883         else if(oper=='-' && !oper2)
 884         {
 885                 if(r_constant_value.check_type<int>())
 886                         set_result(-r_constant_value.value<int>());
 887                 else if(r_constant_value.check_type<unsigned>())
 888                         set_result(-r_constant_value.value<unsigned>());
 889                 else if(r_constant_value.check_type<float>())
 890                         set_result(-r_constant_value.value<float>());
 891         }
 892 }
 893
 894 void ConstantFolder::visit(BinaryExpression &binary)
 895 {
 896         visit(binary.left);
 897         bool left_constant = r_constant;
 898         bool left_iter_var = r_uses_iter_var;
 899         Variant left_value = r_constant_value;
 900         visit(binary.right);
 901         if(left_iter_var)
 902                 r_uses_iter_var = true;
 903
 904         bool can_fold = (left_constant && r_constant);
 905         r_constant = false;
 906         if(!can_fold)
 907                 return;
 908
 909         // Currently only expressions with both sides of equal types are handled.
 910         if(!left_value.check_same_type(r_constant_value))
 911                 return;
 912
 913         char oper = binary.oper->token[0];
 914         char oper2 = binary.oper->token[1];
 915         if(oper=='&' || oper=='|' || oper=='^')
 916         {
 917                 if(oper2==oper && left_value.check_type<bool>())
 918                         set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
 919                 else if(!oper2 && left_value.check_type<int>())
 920                         set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
 921                 else if(!oper2 && left_value.check_type<unsigned>())
 922                         set_result(evaluate_logical(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 923         }
 924         else if((oper=='<' || oper=='>') && oper2!=oper)
 925         {
 926                 if(left_value.check_type<int>())
 927                         set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
 928                 else if(left_value.check_type<unsigned>())
 929                         set_result(evaluate_relation(binary.oper->token, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 930                 else if(left_value.check_type<float>())
 931                         set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
 932         }
 933         else if((oper=='=' || oper=='!') && oper2=='=')
 934         {
 935                 if(left_value.check_type<int>())
 936                         set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
 937                 else if(left_value.check_type<unsigned>())
 938                         set_result((left_value.value<unsigned>()==r_constant_value.value<unsigned>()) == (oper=='='));
 939                 else if(left_value.check_type<float>())
 940                         set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
 941         }
 942         else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
 943         {
 944                 if(left_value.check_type<int>())
 945                         set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
 946                 else if(left_value.check_type<unsigned>())
 947                         set_result(evaluate_arithmetic(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 948                 else if(left_value.check_type<float>())
 949                         set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
 950         }
 951         else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
 952         {
 953                 if(left_value.check_type<int>())
 954                         set_result(evaluate_int_special_op(oper, left_value.value<int>(), r_constant_value.value<int>()));
 955                 else if(left_value.check_type<unsigned>())
 956                         set_result(evaluate_int_special_op(oper, left_value.value<unsigned>(), r_constant_value.value<unsigned>()));
 957         }
 958 }
 959
 960 void ConstantFolder::visit(Assignment &assign)
 961 {
 962         TraversingVisitor::visit(assign);
 963         r_constant = false;
 964 }
 965
 966 void ConstantFolder::visit(TernaryExpression &ternary)
 967 {
 968         TraversingVisitor::visit(ternary);
 969         r_constant = false;
 970 }
 971
 972 void ConstantFolder::visit(FunctionCall &call)
 973 {
 974         if(call.constructor && call.type && call.arguments.size()==1)
 975         {
 976                 const BasicTypeDeclaration *basic = dynamic_cast<const BasicTypeDeclaration *>(call.type);
 977                 if(basic)
 978                 {
 979                         visit(call.arguments[0]);
 980                         bool can_fold = r_constant;
 981                         r_constant = false;
 982                         if(!can_fold)
 983                                 return;
 984
 985                         if(basic->kind==BasicTypeDeclaration::BOOL)
 986                                 convert_to_result<bool>(r_constant_value);
 987                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && basic->sign)
 988                                 convert_to_result<int>(r_constant_value);
 989                         else if(basic->kind==BasicTypeDeclaration::INT && basic->size==32 && !basic->sign)
 990                                 convert_to_result<unsigned>(r_constant_value);
 991                         else if(basic->kind==BasicTypeDeclaration::FLOAT && basic->size==32)
 992                                 convert_to_result<float>(r_constant_value);
 993
 994                         return;
 995                 }
 996         }
 997
 998         TraversingVisitor::visit(call);
 999         r_constant = false;
1000 }
1001
1002 void ConstantFolder::visit(VariableDeclaration &var)
1003 {
1004         if(iteration_init && var.init_expression)
1005         {
1006                 visit(var.init_expression);
1007                 if(r_constant)
1008                 {
1009                         /* Record the value of a constant initialization expression of an
1010                         iteration, so it can be used to evaluate the loop condition. */
1011                         iteration_var = &var;
1012                         iter_init_value = r_constant_value;
1013                 }
1014         }
1015         else
1016                 TraversingVisitor::visit(var);
1017 }
1018
1019 void ConstantFolder::visit(Iteration &iter)
1020 {
1021         SetForScope<Block *> set_block(current_block, &iter.body);
1022
1023         /* The iteration variable is not normally inlined into expressions, so we
1024         process it specially here.  If the initial value causes the loop condition
1025         to evaluate to false, then the expression can be folded. */
1026         iteration_var = 0;
1027         if(iter.init_statement)
1028         {
1029                 SetFlag set_init(iteration_init);
1030                 iter.init_statement->visit(*this);
1031         }
1032
1033         if(iter.condition)
1034         {
1035                 visit(iter.condition);
1036                 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
1037                 {
1038                         RefPtr<Literal> literal = new Literal;
1039                         literal->token = "false";
1040                         literal->value = r_constant_value;
1041                         iter.condition = literal;
1042                 }
1043         }
1044         iteration_var = 0;
1045
1046         iter.body.visit(*this);
1047         if(iter.loop_expression)
1048                 visit(iter.loop_expression);
1049 }
1050
1051
1052 void ConstantConditionEliminator::apply(Stage &stage)
1053 {
1054         stage.content.visit(*this);
1055         NodeRemover().apply(stage, nodes_to_remove);
1056 }
1057
1058 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
1059 {
1060         if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
1061                 if(literal->value.check_type<bool>())
1062                         return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
1063         return NOT_CONSTANT;
1064 }
1065
1066 void ConstantConditionEliminator::visit(Block &block)
1067 {
1068         SetForScope<Block *> set_block(current_block, &block);
1069         for(auto i=block.body.begin(); i!=block.body.end(); ++i)
1070         {
1071                 insert_point = i;
1072                 (*i)->visit(*this);
1073         }
1074 }
1075
1076 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
1077 {
1078         r_ternary_result = 0;
1079         expr->visit(*this);
1080         if(r_ternary_result)
1081                 expr = r_ternary_result;
1082         r_ternary_result = 0;
1083 }
1084
1085 void ConstantConditionEliminator::visit(UnaryExpression &unary)
1086 {
1087         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1088                 if(const VariableReference *var = dynamic_cast<const VariableReference *>(unary.expression.get()))
1089                 {
1090                         auto i = current_block->variables.find(var->name);
1091                         r_external_side_effects = (i==current_block->variables.end() || i->second!=var->declaration);
1092                         return;
1093                 }
1094
1095         TraversingVisitor::visit(unary);
1096 }
1097
1098 void ConstantConditionEliminator::visit(Assignment &assign)
1099 {
1100         auto i = find_if(current_block->variables, [&assign](const pair<string, VariableDeclaration *> &kvp){ return kvp.second==assign.target.declaration; });
1101         if(i==current_block->variables.end())
1102                 r_external_side_effects = true;
1103         TraversingVisitor::visit(assign);
1104 }
1105
1106 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
1107 {
1108         ConstantStatus result = check_constant_condition(*ternary.condition);
1109         if(result!=NOT_CONSTANT)
1110                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
1111         else
1112                 r_ternary_result = 0;
1113 }
1114
1115 void ConstantConditionEliminator::visit(FunctionCall &call)
1116 {
1117         r_external_side_effects = true;
1118         TraversingVisitor::visit(call);
1119 }
1120
1121 void ConstantConditionEliminator::visit(Conditional &cond)
1122 {
1123         ConstantStatus result = check_constant_condition(*cond.condition);
1124         if(result!=NOT_CONSTANT)
1125         {
1126                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
1127                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
1128                 current_block->body.splice(insert_point, block.body);
1129                 nodes_to_remove.insert(&cond);
1130                 return;
1131         }
1132
1133         r_external_side_effects = false;
1134         TraversingVisitor::visit(cond);
1135
1136         if(cond.body.body.empty() && cond.else_body.body.empty() && !r_external_side_effects)
1137                 nodes_to_remove.insert(&cond);
1138 }
1139
1140 void ConstantConditionEliminator::visit(Iteration &iter)
1141 {
1142         if(iter.condition)
1143         {
1144                 ConstantStatus result = check_constant_condition(*iter.condition);
1145                 if(result==CONSTANT_FALSE)
1146                 {
1147                         nodes_to_remove.insert(&iter);
1148                         return;
1149                 }
1150         }
1151
1152         r_external_side_effects = false;
1153         TraversingVisitor::visit(iter);
1154         if(iter.body.body.empty() && !r_external_side_effects)
1155                 nodes_to_remove.insert(&iter);
1156 }
1157
1158
1159 bool UnreachableCodeRemover::apply(Stage &stage)
1160 {
1161         stage.content.visit(*this);
1162         NodeRemover().apply(stage, unreachable_nodes);
1163         return !unreachable_nodes.empty();
1164 }
1165
1166 void UnreachableCodeRemover::visit(Block &block)
1167 {
1168         auto i = block.body.begin();
1169         for(; (reachable && i!=block.body.end()); ++i)
1170                 (*i)->visit(*this);
1171         for(; i!=block.body.end(); ++i)
1172                 unreachable_nodes.insert(i->get());
1173 }
1174
1175 void UnreachableCodeRemover::visit(FunctionDeclaration &func)
1176 {
1177         TraversingVisitor::visit(func);
1178         reachable = true;
1179 }
1180
1181 void UnreachableCodeRemover::visit(Conditional &cond)
1182 {
1183         cond.body.visit(*this);
1184         bool reachable_if_true = reachable;
1185         reachable = true;
1186         cond.else_body.visit(*this);
1187
1188         reachable |= reachable_if_true;
1189 }
1190
1191 void UnreachableCodeRemover::visit(Iteration &iter)
1192 {
1193         TraversingVisitor::visit(iter);
1194
1195         /* Always consider code after a loop reachable, since there's no checking
1196         for whether the loop executes. */
1197         reachable = true;
1198 }
1199
1200
1201 bool UnusedTypeRemover::apply(Stage &stage)
1202 {
1203         stage.content.visit(*this);
1204         NodeRemover().apply(stage, unused_nodes);
1205         return !unused_nodes.empty();
1206 }
1207
1208 void UnusedTypeRemover::visit(RefPtr<Expression> &expr)
1209 {
1210         unused_nodes.erase(expr->type);
1211         TraversingVisitor::visit(expr);
1212 }
1213
1214 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
1215 {
1216         if(type.base_type)
1217                 unused_nodes.erase(type.base_type);
1218         unused_nodes.insert(&type);
1219 }
1220
1221 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
1222 {
1223         if(type.base_type)
1224                 unused_nodes.erase(type.base_type);
1225         unused_nodes.insert(&type);
1226 }
1227
1228 void UnusedTypeRemover::visit(StructDeclaration &strct)
1229 {
1230         unused_nodes.insert(&strct);
1231         TraversingVisitor::visit(strct);
1232 }
1233
1234 void UnusedTypeRemover::visit(VariableDeclaration &var)
1235 {
1236         unused_nodes.erase(var.type_declaration);
1237         TraversingVisitor::visit(var);
1238 }
1239
1240 void UnusedTypeRemover::visit(InterfaceBlock &iface)
1241 {
1242         unused_nodes.erase(iface.type_declaration);
1243 }
1244
1245 void UnusedTypeRemover::visit(FunctionDeclaration &func)
1246 {
1247         unused_nodes.erase(func.return_type_declaration);
1248         TraversingVisitor::visit(func);
1249 }
1250
1251
1252 bool UnusedVariableRemover::apply(Stage &s)
1253 {
1254         stage = &s;
1255         s.content.visit(*this);
1256
1257         for(const AssignmentInfo &a: assignments)
1258                 if(a.used_by.empty())
1259                         unused_nodes.insert(a.node);
1260
1261         for(const auto &kvp: variables)
1262         {
1263                 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                 if(!kvp.second.output && !kvp.second.referenced)
1272                 {
1273                         // Don't remove variables from inside interface blocks.
1274                         if(!kvp.second.interface_block)
1275                                 unused_nodes.insert(kvp.first);
1276                 }
1277                 else if(kvp.second.interface_block)
1278                         // Interface blocks are kept if even one member is used.
1279                         unused_nodes.erase(kvp.second.interface_block);
1280         }
1281
1282         NodeRemover().apply(s, unused_nodes);
1283
1284         return !unused_nodes.empty();
1285 }
1286
1287 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1288 {
1289         VariableInfo &var_info = variables[target.declaration];
1290         var_info.referenced = true;
1291         if(!assignment_target)
1292         {
1293                 bool loop_external = false;
1294                 for(AssignmentInfo *a: var_info.assignments)
1295                 {
1296                         bool covered = true;
1297                         for(unsigned j=0; (covered && j<a->target.chain_len && j<target.chain_len); ++j)
1298                         {
1299                                 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>(a->target.chain[j]&0xC0);
1300                                 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1301                                 unsigned index1 = a->target.chain[j]&0x3F;
1302                                 unsigned index2 = target.chain[j]&0x3F;
1303                                 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1304                                 {
1305                                         if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1306                                                 covered = index1&index2;
1307                                         else if(type1==Assignment::Target::ARRAY && index1<4)
1308                                                 covered = index2&(1<<index1);
1309                                         else if(type2==Assignment::Target::ARRAY && index2<4)
1310                                                 covered = index1&(1<<index2);
1311                                         /* If it's some other combination (shouldn't happen), leave
1312                                         covered as true */
1313                                 }
1314                                 else
1315                                         covered = (type1==type2 && (index1==index2 || index1==0x3F || index2==0x3F));
1316                         }
1317
1318                         if(covered)
1319                         {
1320                                 a->used_by.push_back(&node);
1321                                 if(a->in_loop<in_loop)
1322                                         loop_external = true;
1323                         }
1324                 }
1325
1326                 if(loop_external)
1327                         loop_ext_refs.push_back(&node);
1328         }
1329 }
1330
1331 void UnusedVariableRemover::visit(VariableReference &var)
1332 {
1333         if(composite_reference)
1334                 r_reference.declaration = var.declaration;
1335         else
1336                 referenced(var.declaration, var);
1337 }
1338
1339 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1340 {
1341         if(composite_reference)
1342                 r_reference.declaration = iface.declaration;
1343         else
1344                 referenced(iface.declaration, iface);
1345 }
1346
1347 void UnusedVariableRemover::visit_composite(Expression &expr)
1348 {
1349         if(!composite_reference)
1350                 r_reference = Assignment::Target();
1351
1352         SetFlag set_composite(composite_reference);
1353         expr.visit(*this);
1354 }
1355
1356 void UnusedVariableRemover::visit(MemberAccess &memacc)
1357 {
1358         visit_composite(*memacc.left);
1359
1360         add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1361
1362         if(!composite_reference && r_reference.declaration)
1363                 referenced(r_reference, memacc);
1364 }
1365
1366 void UnusedVariableRemover::visit(Swizzle &swizzle)
1367 {
1368         visit_composite(*swizzle.left);
1369
1370         unsigned mask = 0;
1371         for(unsigned i=0; i<swizzle.count; ++i)
1372                 mask |= 1<<swizzle.components[i];
1373         add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1374
1375         if(!composite_reference && r_reference.declaration)
1376                 referenced(r_reference, swizzle);
1377 }
1378
1379 void UnusedVariableRemover::visit(UnaryExpression &unary)
1380 {
1381         TraversingVisitor::visit(unary);
1382         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1383                 r_side_effects = true;
1384 }
1385
1386 void UnusedVariableRemover::visit(BinaryExpression &binary)
1387 {
1388         if(binary.oper->token[0]=='[')
1389         {
1390                 visit_composite(*binary.left);
1391
1392                 {
1393                         SetFlag clear_assignment(assignment_target, false);
1394                         SetFlag clear_composite(composite_reference, false);
1395                         binary.right->visit(*this);
1396                 }
1397
1398                 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1399
1400                 if(!composite_reference && r_reference.declaration)
1401                         referenced(r_reference, binary);
1402         }
1403         else
1404         {
1405                 SetFlag clear_composite(composite_reference, false);
1406                 TraversingVisitor::visit(binary);
1407         }
1408 }
1409
1410 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1411 {
1412         SetFlag clear_composite(composite_reference, false);
1413         TraversingVisitor::visit(ternary);
1414 }
1415
1416 void UnusedVariableRemover::visit(Assignment &assign)
1417 {
1418         {
1419                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1420                 assign.left->visit(*this);
1421         }
1422         assign.right->visit(*this);
1423         r_assignment = &assign;
1424         r_side_effects = true;
1425 }
1426
1427 void UnusedVariableRemover::visit(FunctionCall &call)
1428 {
1429         SetFlag clear_composite(composite_reference, false);
1430         TraversingVisitor::visit(call);
1431         /* Treat function calls as having side effects so expression statements
1432         consisting of nothing but a function call won't be optimized away. */
1433         r_side_effects = true;
1434
1435         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1436         {
1437                 for(const auto &kvp: variables)
1438                         if(kvp.second.output)
1439                                 referenced(kvp.first, call);
1440         }
1441 }
1442
1443 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1444 {
1445         assignments.push_back(AssignmentInfo());
1446         AssignmentInfo &assign_info = assignments.back();
1447         assign_info.node = &node;
1448         assign_info.target = target;
1449         assign_info.in_loop = in_loop;
1450
1451         /* An assignment to the target hides any assignments to the same target or
1452         its subfields. */
1453         VariableInfo &var_info = variables[target.declaration];
1454         for(unsigned i=0; i<var_info.assignments.size(); )
1455         {
1456                 const Assignment::Target &t = var_info.assignments[i]->target;
1457
1458                 bool subfield = (t.chain_len>=target.chain_len);
1459                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1460                         subfield = (t.chain[j]==target.chain[j]);
1461
1462                 if(subfield)
1463                         var_info.assignments.erase(var_info.assignments.begin()+i);
1464                 else
1465                         ++i;
1466         }
1467
1468         var_info.assignments.push_back(&assign_info);
1469 }
1470
1471 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1472 {
1473         r_assignment = 0;
1474         r_side_effects = false;
1475         TraversingVisitor::visit(expr);
1476         if(r_assignment && r_assignment->target.declaration)
1477                 record_assignment(r_assignment->target, expr);
1478         if(!r_side_effects)
1479                 unused_nodes.insert(&expr);
1480 }
1481
1482 void UnusedVariableRemover::visit(StructDeclaration &strct)
1483 {
1484         SetFlag set_struct(in_struct);
1485         TraversingVisitor::visit(strct);
1486 }
1487
1488 void UnusedVariableRemover::visit(VariableDeclaration &var)
1489 {
1490         TraversingVisitor::visit(var);
1491
1492         if(in_struct)
1493                 return;
1494
1495         VariableInfo &var_info = variables[&var];
1496         var_info.interface_block = interface_block;
1497
1498         /* Mark variables as output if they're used by the next stage or the
1499         graphics API. */
1500         if(interface_block)
1501                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1502         else
1503                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1504
1505         if(var.init_expression)
1506         {
1507                 var_info.initialized = true;
1508                 record_assignment(&var, *var.init_expression);
1509         }
1510 }
1511
1512 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1513 {
1514         VariableInfo &var_info = variables[&iface];
1515         var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1516 }
1517
1518 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1519 {
1520         for(const auto &kvp: other_vars)
1521         {
1522                 auto j = variables.find(kvp.first);
1523                 if(j!=variables.end())
1524                 {
1525                         /* The merged blocks started as copies of each other so any common
1526                         assignments must be in the beginning. */
1527                         unsigned k = 0;
1528                         for(; (k<kvp.second.assignments.size() && k<j->second.assignments.size()); ++k)
1529                                 if(kvp.second.assignments[k]!=j->second.assignments[k])
1530                                         break;
1531
1532                         // Remaining assignments are unique to each block; merge them.
1533                         j->second.assignments.insert(j->second.assignments.end(), kvp.second.assignments.begin()+k, kvp.second.assignments.end());
1534                         j->second.referenced |= kvp.second.referenced;
1535                 }
1536                 else
1537                         variables.insert(kvp);
1538         }
1539 }
1540
1541 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1542 {
1543         if(func.body.body.empty())
1544                 return;
1545
1546         BlockVariableMap saved_vars = variables;
1547         // Assignments from other functions should not be visible.
1548         for(auto &kvp: variables)
1549                 kvp.second.assignments.resize(kvp.second.initialized);
1550         TraversingVisitor::visit(func);
1551         swap(variables, saved_vars);
1552         merge_variables(saved_vars);
1553
1554         /* Always treat function parameters as referenced.  Removing unused
1555         parameters is not currently supported. */
1556         for(const RefPtr<VariableDeclaration> &p: func.parameters)
1557         {
1558                 auto j = variables.find(p.get());
1559                 if(j!=variables.end())
1560                         j->second.referenced = true;
1561         }
1562 }
1563
1564 void UnusedVariableRemover::visit(Conditional &cond)
1565 {
1566         cond.condition->visit(*this);
1567         BlockVariableMap saved_vars = variables;
1568         cond.body.visit(*this);
1569         swap(saved_vars, variables);
1570         cond.else_body.visit(*this);
1571
1572         /* Visible assignments after the conditional is the union of those visible
1573         at the end of the if and else blocks.  If there was no else block, then it's
1574         the union of the if block and the state before it. */
1575         merge_variables(saved_vars);
1576 }
1577
1578 void UnusedVariableRemover::visit(Iteration &iter)
1579 {
1580         BlockVariableMap saved_vars = variables;
1581         vector<Node *> saved_refs;
1582         swap(loop_ext_refs, saved_refs);
1583         {
1584                 SetForScope<unsigned> set_loop(in_loop, in_loop+1);
1585                 TraversingVisitor::visit(iter);
1586         }
1587         swap(loop_ext_refs, saved_refs);
1588
1589         /* Visit the external references of the loop again to record assignments
1590         done in the loop as used. */
1591         for(Node *n: saved_refs)
1592                 n->visit(*this);
1593
1594         /* Merge assignments from the iteration, without clearing previous state.
1595         Further analysis is needed to determine which parts of the iteration body
1596         are always executed, if any. */
1597         merge_variables(saved_vars);
1598 }
1599
1600
1601 bool UnusedFunctionRemover::apply(Stage &stage)
1602 {
1603         stage.content.visit(*this);
1604         NodeRemover().apply(stage, unused_nodes);
1605         return !unused_nodes.empty();
1606 }
1607
1608 void UnusedFunctionRemover::visit(FunctionCall &call)
1609 {
1610         TraversingVisitor::visit(call);
1611
1612         unused_nodes.erase(call.declaration);
1613         if(call.declaration && call.declaration->definition!=call.declaration)
1614                 used_definitions.insert(call.declaration->definition);
1615 }
1616
1617 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1618 {
1619         TraversingVisitor::visit(func);
1620
1621         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1622                 unused_nodes.insert(&func);
1623 }
1624
1625 } // namespace SL
1626 } // namespace GL
1627 } // namespace Msp