source/glsl/optimize.cpp

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