source/glsl/optimize.cpp

   1 #include <msp/core/raii.h>
   2 #include <msp/strings/format.h>
   3 #include "optimize.h"
   4
   5 using namespace std;
   6
   7 namespace Msp {
   8 namespace GL {
   9 namespace SL {
  10
  11 InlineableFunctionLocator::InlineableFunctionLocator():
  12         current_function(0),
  13         return_count(0)
  14 { }
  15
  16 void InlineableFunctionLocator::visit(FunctionCall &call)
  17 {
  18         FunctionDeclaration *def = call.declaration;
  19         if(def)
  20                 def = def->definition;
  21
  22         if(def)
  23         {
  24                 unsigned &count = refcounts[def];
  25                 ++count;
  26                 /* Don't inline functions which are called more than once or are called
  27                 recursively. */
  28                 if(count>1 || def==current_function)
  29                         inlineable.erase(def);
  30         }
  31
  32         TraversingVisitor::visit(call);
  33 }
  34
  35 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
  36 {
  37         unsigned &count = refcounts[func.definition];
  38         if(count<=1 && func.parameters.empty())
  39                 inlineable.insert(func.definition);
  40
  41         SetForScope<FunctionDeclaration *> set(current_function, &func);
  42         return_count = 0;
  43         TraversingVisitor::visit(func);
  44 }
  45
  46 void InlineableFunctionLocator::visit(Conditional &cond)
  47 {
  48         TraversingVisitor::visit(cond);
  49         inlineable.erase(current_function);
  50 }
  51
  52 void InlineableFunctionLocator::visit(Iteration &iter)
  53 {
  54         TraversingVisitor::visit(iter);
  55         inlineable.erase(current_function);
  56 }
  57
  58 void InlineableFunctionLocator::visit(Return &ret)
  59 {
  60         TraversingVisitor::visit(ret);
  61         if(return_count)
  62                 inlineable.erase(current_function);
  63         ++return_count;
  64 }
  65
  66
  67 InlineContentInjector::InlineContentInjector():
  68         source_func(0),
  69         remap_names(false),
  70         deps_only(false)
  71 { }
  72
  73 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionDeclaration &src)
  74 {
  75         target_block = &tgt_blk;
  76         source_func = &src;
  77         for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
  78         {
  79                 r_inlined_statement = 0;
  80                 (*i)->visit(*this);
  81                 if(!r_inlined_statement)
  82                         r_inlined_statement = (*i)->clone();
  83
  84                 SetFlag set_remap(remap_names);
  85                 r_inlined_statement->visit(*this);
  86                 tgt_blk.body.insert(ins_pt, r_inlined_statement);
  87         }
  88
  89         NodeReorderer().apply(stage, target_func, dependencies);
  90
  91         return r_result_name;
  92 }
  93
  94 string InlineContentInjector::create_unused_name(const string &base, bool always_prefix)
  95 {
  96         string result = base;
  97         if(always_prefix || target_block->variables.count(result))
  98                 result = format("_%s_%s", source_func->name, base);
  99         unsigned initial_size = result.size();
 100         for(unsigned i=1; target_block->variables.count(result); ++i)
 101         {
 102                 result.erase(initial_size);
 103                 result += format("_%d", i);
 104         }
 105         return result;
 106 }
 107
 108 void InlineContentInjector::visit(VariableReference &var)
 109 {
 110         if(remap_names)
 111         {
 112                 map<string, VariableDeclaration *>::const_iterator i = variable_map.find(var.name);
 113                 if(i!=variable_map.end())
 114                         var.name = i->second->name;
 115         }
 116         else if(var.declaration)
 117         {
 118                 SetFlag set_deps(deps_only);
 119                 dependencies.insert(var.declaration);
 120                 var.declaration->visit(*this);
 121         }
 122 }
 123
 124 void InlineContentInjector::visit(InterfaceBlockReference &iface)
 125 {
 126         if(!remap_names && iface.declaration)
 127         {
 128                 SetFlag set_deps(deps_only);
 129                 dependencies.insert(iface.declaration);
 130                 iface.declaration->visit(*this);
 131         }
 132 }
 133
 134 void InlineContentInjector::visit(FunctionCall &call)
 135 {
 136         if(!remap_names && call.declaration)
 137                 dependencies.insert(call.declaration);
 138         TraversingVisitor::visit(call);
 139 }
 140
 141 void InlineContentInjector::visit(VariableDeclaration &var)
 142 {
 143         TraversingVisitor::visit(var);
 144
 145         if(var.type_declaration)
 146         {
 147                 SetFlag set_deps(deps_only);
 148                 dependencies.insert(var.type_declaration);
 149                 var.type_declaration->visit(*this);
 150         }
 151
 152         if(!remap_names && !deps_only)
 153         {
 154                 RefPtr<VariableDeclaration> inlined_var = var.clone();
 155                 inlined_var->name = create_unused_name(var.name, false);
 156                 r_inlined_statement = inlined_var;
 157
 158                 variable_map[var.name] = inlined_var.get();
 159         }
 160 }
 161
 162 void InlineContentInjector::visit(Return &ret)
 163 {
 164         TraversingVisitor::visit(ret);
 165
 166         if(ret.expression)
 167         {
 168                 /* Create a new variable to hold the return value of the inlined
 169                 function. */
 170                 r_result_name = create_unused_name("return", true);
 171                 RefPtr<VariableDeclaration> var = new VariableDeclaration;
 172                 var->source = ret.source;
 173                 var->line = ret.line;
 174                 var->type = source_func->return_type;
 175                 var->name = r_result_name;
 176                 var->init_expression = ret.expression->clone();
 177                 r_inlined_statement = var;
 178         }
 179 }
 180
 181
 182 FunctionInliner::FunctionInliner():
 183         current_function(0),
 184         r_any_inlined(false)
 185 { }
 186
 187 bool FunctionInliner::apply(Stage &s)
 188 {
 189         stage = &s;
 190         inlineable = InlineableFunctionLocator().apply(s);
 191         r_any_inlined = false;
 192         s.content.visit(*this);
 193         return r_any_inlined;
 194 }
 195
 196 void FunctionInliner::visit(RefPtr<Expression> &ptr)
 197 {
 198         r_inline_result = 0;
 199         ptr->visit(*this);
 200         if(r_inline_result)
 201         {
 202                 ptr = r_inline_result;
 203                 r_any_inlined = true;
 204         }
 205         r_inline_result = 0;
 206 }
 207
 208 void FunctionInliner::visit(Block &block)
 209 {
 210         SetForScope<Block *> set_block(current_block, &block);
 211         SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
 212         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 213         {
 214                 insert_point = i;
 215                 (*i)->visit(*this);
 216         }
 217 }
 218
 219 void FunctionInliner::visit(FunctionCall &call)
 220 {
 221         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 222                 visit(*i);
 223
 224         FunctionDeclaration *def = call.declaration;
 225         if(def)
 226                 def = def->definition;
 227
 228         if(def && inlineable.count(def))
 229         {
 230                 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
 231
 232                 // This will later get removed by UnusedVariableRemover.
 233                 if(result_name.empty())
 234                         result_name = "msp_unused_from_inline";
 235
 236                 RefPtr<VariableReference> ref = new VariableReference;
 237                 ref->name = result_name;
 238                 r_inline_result = ref;
 239
 240                 /* Inlined variables need to be resolved before this function can be
 241                 inlined further. */
 242                 inlineable.erase(current_function);
 243         }
 244 }
 245
 246 void FunctionInliner::visit(FunctionDeclaration &func)
 247 {
 248         SetForScope<FunctionDeclaration *> set_func(current_function, &func);
 249         TraversingVisitor::visit(func);
 250 }
 251
 252 void FunctionInliner::visit(Iteration &iter)
 253 {
 254         /* Visit the initialization statement before entering the loop body so the
 255         inlined statements get inserted outside. */
 256         if(iter.init_statement)
 257                 iter.init_statement->visit(*this);
 258
 259         SetForScope<Block *> set_block(current_block, &iter.body);
 260         /* Skip the condition and loop expression parts because they're not properly
 261         inside the body block.  Inlining anything into them will require a more
 262         comprehensive transformation. */
 263         iter.body.visit(*this);
 264 }
 265
 266
 267 ExpressionInliner::ExpressionInfo::ExpressionInfo():
 268         expression(0),
 269         assign_scope(0),
 270         inline_point(0),
 271         inner_oper(0),
 272         outer_oper(0),
 273         inline_on_rhs(false),
 274         trivial(false),
 275         available(true)
 276 { }
 277
 278
 279 ExpressionInliner::ExpressionInliner():
 280         r_ref_info(0),
 281         r_any_inlined(false),
 282         r_trivial(false),
 283         mutating(false),
 284         iteration_init(false),
 285         iteration_body(0),
 286         r_oper(0)
 287 { }
 288
 289 bool ExpressionInliner::apply(Stage &s)
 290 {
 291         s.content.visit(*this);
 292         return r_any_inlined;
 293 }
 294
 295 void ExpressionInliner::visit_and_record(RefPtr<Expression> &ptr, const Operator *outer_oper, bool on_rhs)
 296 {
 297         r_ref_info = 0;
 298         ptr->visit(*this);
 299         if(r_ref_info && r_ref_info->expression && r_ref_info->available)
 300         {
 301                 if(iteration_body && !r_ref_info->trivial)
 302                 {
 303                         /* Don't inline non-trivial expressions which were assigned outside
 304                         an iteration statement.  The iteration may run multiple times, which
 305                         would cause the expression to also be evaluated multiple times. */
 306                         Block *i = r_ref_info->assign_scope;
 307                         for(; (i && i!=iteration_body); i=i->parent) ;
 308                         if(!i)
 309                                 return;
 310                 }
 311
 312                 r_ref_info->outer_oper = outer_oper;
 313                 if(r_ref_info->trivial)
 314                         inline_expression(*r_ref_info->expression, ptr, outer_oper, r_ref_info->inner_oper, on_rhs);
 315                 else
 316                 {
 317                         /* Record the inline point for a non-trivial expression but don't
 318                         inline it yet.  It might turn out it shouldn't be inlined after all. */
 319                         r_ref_info->inline_point = &ptr;
 320                         r_ref_info->inline_on_rhs = on_rhs;
 321                 }
 322         }
 323         r_ref_info = 0;
 324 }
 325
 326 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr, const Operator *outer_oper, const Operator *inner_oper, bool on_rhs)
 327 {
 328         unsigned outer_precedence = (outer_oper ? outer_oper->precedence : 20);
 329         unsigned inner_precedence = (inner_oper ? inner_oper->precedence : 0);
 330
 331         bool needs_parentheses = (inner_precedence>=outer_precedence);
 332         if(inner_oper && inner_oper==outer_oper)
 333                 // Omit parentheses if the operator's natural grouping works out.
 334                 needs_parentheses = (inner_oper->assoc!=Operator::ASSOCIATIVE && on_rhs!=(inner_oper->assoc==Operator::RIGHT_TO_LEFT));
 335
 336         if(needs_parentheses)
 337         {
 338                 RefPtr<ParenthesizedExpression> parexpr = new ParenthesizedExpression;
 339                 parexpr->expression = expr.clone();
 340                 ptr = parexpr;
 341         }
 342         else
 343                 ptr = expr.clone();
 344
 345         r_any_inlined = true;
 346 }
 347
 348 void ExpressionInliner::visit(Block &block)
 349 {
 350         TraversingVisitor::visit(block);
 351
 352         for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 353         {
 354                 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
 355                 for(; (j!=expressions.end() && j->first.declaration==i->second); )
 356                 {
 357                         if(j->second.expression && j->second.inline_point)
 358                                 inline_expression(*j->second.expression, *j->second.inline_point, j->second.outer_oper, j->second.inner_oper, j->second.inline_on_rhs);
 359
 360                         expressions.erase(j++);
 361                 }
 362         }
 363
 364         /* Expressions assigned in this block may depend on local variables of the
 365         block.  If this is a conditionally executed block, the assignments might not
 366         always happen.  Mark the expressions as not available to any outer blocks. */
 367         for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
 368                 if(i->second.assign_scope==&block)
 369                         i->second.available = false;
 370 }
 371
 372 void ExpressionInliner::visit(RefPtr<Expression> &expr)
 373 {
 374         visit_and_record(expr, 0, false);
 375 }
 376
 377 void ExpressionInliner::visit(VariableReference &var)
 378 {
 379         if(var.declaration)
 380         {
 381                 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
 382                 if(i!=expressions.end())
 383                 {
 384                         /* If a non-trivial expression is referenced multiple times, don't
 385                         inline it. */
 386                         if(i->second.inline_point && !i->second.trivial)
 387                                 i->second.expression = 0;
 388                         /* Mutating expressions are analogous to self-referencing assignments
 389                         and prevent inlining. */
 390                         if(mutating)
 391                                 i->second.expression = 0;
 392                         r_ref_info = &i->second;
 393                 }
 394         }
 395 }
 396
 397 void ExpressionInliner::visit(MemberAccess &memacc)
 398 {
 399         visit_and_record(memacc.left, memacc.oper, false);
 400         r_oper = memacc.oper;
 401         r_trivial = false;
 402 }
 403
 404 void ExpressionInliner::visit(Swizzle &swizzle)
 405 {
 406         visit_and_record(swizzle.left, swizzle.oper, false);
 407         r_oper = swizzle.oper;
 408         r_trivial = false;
 409 }
 410
 411 void ExpressionInliner::visit(UnaryExpression &unary)
 412 {
 413         SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
 414         visit_and_record(unary.expression, unary.oper, false);
 415         r_oper = unary.oper;
 416         r_trivial = false;
 417 }
 418
 419 void ExpressionInliner::visit(BinaryExpression &binary)
 420 {
 421         visit_and_record(binary.left, binary.oper, false);
 422         {
 423                 SetFlag clear_target(mutating, false);
 424                 visit_and_record(binary.right, binary.oper, true);
 425         }
 426         r_oper = binary.oper;
 427         r_trivial = false;
 428 }
 429
 430 void ExpressionInliner::visit(Assignment &assign)
 431 {
 432         {
 433                 SetFlag set_target(mutating);
 434                 visit_and_record(assign.left, assign.oper, false);
 435         }
 436         r_oper = 0;
 437         visit_and_record(assign.right, assign.oper, true);
 438
 439         map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
 440         if(i!=expressions.end())
 441         {
 442                 /* Self-referencing assignments can't be inlined without additional
 443                 work.  Just clear any previous expression. */
 444                 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
 445                 i->second.assign_scope = current_block;
 446                 i->second.inline_point = 0;
 447                 i->second.inner_oper = r_oper;
 448                 i->second.available = true;
 449         }
 450
 451         r_oper = assign.oper;
 452         r_trivial = false;
 453 }
 454
 455 void ExpressionInliner::visit(FunctionCall &call)
 456 {
 457         TraversingVisitor::visit(call);
 458         r_oper = 0;
 459         r_trivial = false;
 460 }
 461
 462 void ExpressionInliner::visit(VariableDeclaration &var)
 463 {
 464         r_oper = 0;
 465         r_trivial = true;
 466         TraversingVisitor::visit(var);
 467
 468         bool constant = var.constant;
 469         if(constant && var.layout)
 470         {
 471                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 472                         constant = (i->name!="constant_id");
 473         }
 474
 475         /* Only inline global variables if they're constant and have trivial
 476         initializers.  Non-constant variables could change in ways which are hard to
 477         analyze and non-trivial expressions could be expensive to inline.  */
 478         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 479         {
 480                 ExpressionInfo &info = expressions[&var];
 481                 /* Assume variables declared in an iteration initialization statement
 482                 will have their values change throughout the iteration. */
 483                 info.expression = (iteration_init ? 0 : var.init_expression.get());
 484                 info.assign_scope = current_block;
 485                 info.inner_oper = r_oper;
 486                 info.trivial = r_trivial;
 487         }
 488 }
 489
 490 void ExpressionInliner::visit(Iteration &iter)
 491 {
 492         SetForScope<Block *> set_block(current_block, &iter.body);
 493         if(iter.init_statement)
 494         {
 495                 SetFlag set_init(iteration_init);
 496                 iter.init_statement->visit(*this);
 497         }
 498
 499         SetForScope<Block *> set_body(iteration_body, &iter.body);
 500         if(iter.condition)
 501                 visit(iter.condition);
 502         iter.body.visit(*this);
 503         if(iter.loop_expression)
 504                 visit(iter.loop_expression);
 505 }
 506
 507
 508 void ConstantConditionEliminator::apply(Stage &stage)
 509 {
 510         stage.content.visit(*this);
 511         NodeRemover().apply(stage, nodes_to_remove);
 512 }
 513
 514 void ConstantConditionEliminator::visit(Block &block)
 515 {
 516         SetForScope<Block *> set_block(current_block, &block);
 517         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 518         {
 519                 insert_point = i;
 520                 (*i)->visit(*this);
 521         }
 522 }
 523
 524 void ConstantConditionEliminator::visit(Conditional &cond)
 525 {
 526         if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
 527                 if(literal->value.check_type<bool>())
 528                 {
 529                         Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
 530                         current_block->body.splice(insert_point, block.body);
 531                         nodes_to_remove.insert(&cond);
 532                         return;
 533                 }
 534
 535         TraversingVisitor::visit(cond);
 536 }
 537
 538 void ConstantConditionEliminator::visit(Iteration &iter)
 539 {
 540         if(iter.condition)
 541         {
 542                 /* If the loop condition is always false on the first iteration, the
 543                 entire loop can be removed */
 544                 ExpressionEvaluator::ValueMap values;
 545                 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
 546                         values[var] = var->init_expression.get();
 547                 ExpressionEvaluator eval(values);
 548                 iter.condition->visit(eval);
 549                 if(eval.is_result_valid() && !eval.get_result())
 550                 {
 551                         nodes_to_remove.insert(&iter);
 552                         return;
 553                 }
 554         }
 555
 556         TraversingVisitor::visit(iter);
 557 }
 558
 559
 560 bool UnusedTypeRemover::apply(Stage &stage)
 561 {
 562         stage.content.visit(*this);
 563         NodeRemover().apply(stage, unused_nodes);
 564         return !unused_nodes.empty();
 565 }
 566
 567 void UnusedTypeRemover::visit(Literal &literal)
 568 {
 569         unused_nodes.erase(literal.type);
 570 }
 571
 572 void UnusedTypeRemover::visit(UnaryExpression &unary)
 573 {
 574         unused_nodes.erase(unary.type);
 575         TraversingVisitor::visit(unary);
 576 }
 577
 578 void UnusedTypeRemover::visit(BinaryExpression &binary)
 579 {
 580         unused_nodes.erase(binary.type);
 581         TraversingVisitor::visit(binary);
 582 }
 583
 584 void UnusedTypeRemover::visit(FunctionCall &call)
 585 {
 586         unused_nodes.erase(call.type);
 587         TraversingVisitor::visit(call);
 588 }
 589
 590 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 591 {
 592         if(type.base_type)
 593                 unused_nodes.erase(type.base_type);
 594         unused_nodes.insert(&type);
 595 }
 596
 597 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 598 {
 599         if(type.base_type)
 600                 unused_nodes.erase(type.base_type);
 601         unused_nodes.insert(&type);
 602 }
 603
 604 void UnusedTypeRemover::visit(StructDeclaration &strct)
 605 {
 606         unused_nodes.insert(&strct);
 607         TraversingVisitor::visit(strct);
 608 }
 609
 610 void UnusedTypeRemover::visit(VariableDeclaration &var)
 611 {
 612         unused_nodes.erase(var.type_declaration);
 613 }
 614
 615 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 616 {
 617         unused_nodes.erase(iface.type_declaration);
 618 }
 619
 620 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 621 {
 622         unused_nodes.erase(func.return_type_declaration);
 623         TraversingVisitor::visit(func);
 624 }
 625
 626
 627 UnusedVariableRemover::UnusedVariableRemover():
 628         stage(0),
 629         interface_block(0),
 630         r_assignment(0),
 631         assignment_target(false),
 632         r_side_effects(false)
 633 { }
 634
 635 bool UnusedVariableRemover::apply(Stage &s)
 636 {
 637         stage = &s;
 638         s.content.visit(*this);
 639
 640         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
 641                 if(i->used_by.empty())
 642                         unused_nodes.insert(i->node);
 643
 644         for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
 645                 if(i->second->instance_name.empty())
 646                         unused_nodes.insert(i->second);
 647
 648         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 649         {
 650                 if(i->second.output)
 651                 {
 652                         /* The last visible assignments of output variables are used by the
 653                         next stage or the API. */
 654                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
 655                                 unused_nodes.erase((*j)->node);
 656                 }
 657
 658                 if(!i->second.output && !i->second.referenced)
 659                 {
 660                         // Don't remove variables from inside interface blocks.
 661                         if(!i->second.interface_block)
 662                                 unused_nodes.insert(i->first);
 663                 }
 664                 else if(i->second.interface_block)
 665                         // Interface blocks are kept if even one member is used.
 666                         unused_nodes.erase(i->second.interface_block);
 667         }
 668
 669         NodeRemover().apply(s, unused_nodes);
 670
 671         return !unused_nodes.empty();
 672 }
 673
 674 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
 675 {
 676         VariableInfo &var_info = variables[target.declaration];
 677         var_info.referenced = true;
 678         if(!assignment_target)
 679         {
 680                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 681                         (*i)->used_by.push_back(&node);
 682         }
 683 }
 684
 685 void UnusedVariableRemover::visit(VariableReference &var)
 686 {
 687         referenced(var.declaration, var);
 688 }
 689
 690 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 691 {
 692         referenced(iface.declaration, iface);
 693 }
 694
 695 void UnusedVariableRemover::visit(UnaryExpression &unary)
 696 {
 697         TraversingVisitor::visit(unary);
 698         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 699                 r_side_effects = true;
 700 }
 701
 702 void UnusedVariableRemover::visit(BinaryExpression &binary)
 703 {
 704         if(binary.oper->token[0]=='[')
 705         {
 706                 binary.left->visit(*this);
 707                 SetFlag set(assignment_target, false);
 708                 binary.right->visit(*this);
 709         }
 710         else
 711                 TraversingVisitor::visit(binary);
 712 }
 713
 714 void UnusedVariableRemover::visit(Assignment &assign)
 715 {
 716         {
 717                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
 718                 assign.left->visit(*this);
 719         }
 720         assign.right->visit(*this);
 721         r_assignment = &assign;
 722         r_side_effects = true;
 723 }
 724
 725 void UnusedVariableRemover::visit(FunctionCall &call)
 726 {
 727         TraversingVisitor::visit(call);
 728         /* Treat function calls as having side effects so expression statements
 729         consisting of nothing but a function call won't be optimized away. */
 730         r_side_effects = true;
 731
 732         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
 733         {
 734                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 735                         if(i->second.output)
 736                                 referenced(i->first, call);
 737         }
 738 }
 739
 740 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
 741 {
 742         assignments.push_back(AssignmentInfo());
 743         AssignmentInfo &assign_info = assignments.back();
 744         assign_info.node = &node;
 745         assign_info.target = target;
 746
 747         /* An assignment to the target hides any assignments to the same target or
 748         its subfields. */
 749         VariableInfo &var_info = variables[target.declaration];
 750         for(unsigned i=0; i<var_info.assignments.size(); ++i)
 751         {
 752                 const Assignment::Target &t = var_info.assignments[i]->target;
 753
 754                 bool subfield = (t.chain_len>=target.chain_len);
 755                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
 756                         subfield = (t.chain[j]==target.chain[j]);
 757
 758                 if(subfield)
 759                         var_info.assignments.erase(var_info.assignments.begin()+i);
 760                 else
 761                         ++i;
 762         }
 763
 764         var_info.assignments.push_back(&assign_info);
 765 }
 766
 767 void UnusedVariableRemover::visit(ExpressionStatement &expr)
 768 {
 769         r_assignment = 0;
 770         r_side_effects = false;
 771         TraversingVisitor::visit(expr);
 772         if(r_assignment && r_assignment->target.declaration)
 773                 record_assignment(r_assignment->target, expr);
 774         if(!r_side_effects)
 775                 unused_nodes.insert(&expr);
 776 }
 777
 778 void UnusedVariableRemover::visit(VariableDeclaration &var)
 779 {
 780         VariableInfo &var_info = variables[&var];
 781         var_info.interface_block = interface_block;
 782
 783         /* Mark variables as output if they're used by the next stage or the
 784         graphics API. */
 785         if(interface_block)
 786                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
 787         else
 788                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
 789
 790         if(var.init_expression)
 791         {
 792                 var_info.initialized = true;
 793                 record_assignment(&var, *var.init_expression);
 794         }
 795         TraversingVisitor::visit(var);
 796 }
 797
 798 void UnusedVariableRemover::visit(InterfaceBlock &iface)
 799 {
 800         if(iface.instance_name.empty())
 801         {
 802                 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
 803                 iface.struct_declaration->members.visit(*this);
 804         }
 805         else
 806         {
 807                 VariableInfo &var_info = variables[&iface];
 808                 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
 809         }
 810 }
 811
 812 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
 813 {
 814         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
 815         {
 816                 BlockVariableMap::iterator j = variables.find(i->first);
 817                 if(j!=variables.end())
 818                 {
 819                         /* The merged blocks started as copies of each other so any common
 820                         assignments must be in the beginning. */
 821                         unsigned k = 0;
 822                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
 823                                 if(i->second.assignments[k]!=j->second.assignments[k])
 824                                         break;
 825
 826                         // Remaining assignments are unique to each block; merge them.
 827                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
 828                         j->second.referenced |= i->second.referenced;
 829                 }
 830                 else
 831                         variables.insert(*i);
 832         }
 833 }
 834
 835 void UnusedVariableRemover::visit(FunctionDeclaration &func)
 836 {
 837         if(func.body.body.empty())
 838                 return;
 839
 840         BlockVariableMap saved_vars = variables;
 841         // Assignments from other functions should not be visible.
 842         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
 843                 i->second.assignments.resize(i->second.initialized);
 844         TraversingVisitor::visit(func);
 845         swap(variables, saved_vars);
 846         merge_variables(saved_vars);
 847
 848         /* Always treat function parameters as referenced.  Removing unused
 849         parameters is not currently supported. */
 850         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 851         {
 852                 BlockVariableMap::iterator j = variables.find(i->get());
 853                 if(j!=variables.end())
 854                         j->second.referenced = true;
 855         }
 856 }
 857
 858 void UnusedVariableRemover::visit(Conditional &cond)
 859 {
 860         cond.condition->visit(*this);
 861         BlockVariableMap saved_vars = variables;
 862         cond.body.visit(*this);
 863         swap(saved_vars, variables);
 864         cond.else_body.visit(*this);
 865
 866         /* Visible assignments after the conditional is the union of those visible
 867         at the end of the if and else blocks.  If there was no else block, then it's
 868         the union of the if block and the state before it. */
 869         merge_variables(saved_vars);
 870 }
 871
 872 void UnusedVariableRemover::visit(Iteration &iter)
 873 {
 874         BlockVariableMap saved_vars = variables;
 875         TraversingVisitor::visit(iter);
 876
 877         /* Merge assignments from the iteration, without clearing previous state.
 878         Further analysis is needed to determine which parts of the iteration body
 879         are always executed, if any. */
 880         merge_variables(saved_vars);
 881 }
 882
 883
 884 bool UnusedFunctionRemover::apply(Stage &stage)
 885 {
 886         stage.content.visit(*this);
 887         NodeRemover().apply(stage, unused_nodes);
 888         return !unused_nodes.empty();
 889 }
 890
 891 void UnusedFunctionRemover::visit(FunctionCall &call)
 892 {
 893         TraversingVisitor::visit(call);
 894
 895         unused_nodes.erase(call.declaration);
 896         if(call.declaration && call.declaration->definition!=call.declaration)
 897                 used_definitions.insert(call.declaration->definition);
 898 }
 899
 900 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
 901 {
 902         TraversingVisitor::visit(func);
 903
 904         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 905                 unused_nodes.insert(&func);
 906 }
 907
 908 } // namespace SL
 909 } // namespace GL
 910 } // namespace Msp