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