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(TernaryExpression &ternary)
 456 {
 457         visit_and_record(ternary.condition, ternary.oper, false);
 458         visit_and_record(ternary.true_expr, ternary.oper, false);
 459         visit_and_record(ternary.false_expr, ternary.oper, true);
 460         r_oper = ternary.oper;
 461         r_trivial = false;
 462 }
 463
 464 void ExpressionInliner::visit(FunctionCall &call)
 465 {
 466         TraversingVisitor::visit(call);
 467         r_oper = 0;
 468         r_trivial = false;
 469 }
 470
 471 void ExpressionInliner::visit(VariableDeclaration &var)
 472 {
 473         r_oper = 0;
 474         r_trivial = true;
 475         TraversingVisitor::visit(var);
 476
 477         bool constant = var.constant;
 478         if(constant && var.layout)
 479         {
 480                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 481                         constant = (i->name!="constant_id");
 482         }
 483
 484         /* Only inline global variables if they're constant and have trivial
 485         initializers.  Non-constant variables could change in ways which are hard to
 486         analyze and non-trivial expressions could be expensive to inline.  */
 487         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 488         {
 489                 ExpressionInfo &info = expressions[&var];
 490                 /* Assume variables declared in an iteration initialization statement
 491                 will have their values change throughout the iteration. */
 492                 info.expression = (iteration_init ? 0 : var.init_expression.get());
 493                 info.assign_scope = current_block;
 494                 info.inner_oper = r_oper;
 495                 info.trivial = r_trivial;
 496         }
 497 }
 498
 499 void ExpressionInliner::visit(Iteration &iter)
 500 {
 501         SetForScope<Block *> set_block(current_block, &iter.body);
 502         if(iter.init_statement)
 503         {
 504                 SetFlag set_init(iteration_init);
 505                 iter.init_statement->visit(*this);
 506         }
 507
 508         SetForScope<Block *> set_body(iteration_body, &iter.body);
 509         if(iter.condition)
 510                 visit(iter.condition);
 511         iter.body.visit(*this);
 512         if(iter.loop_expression)
 513                 visit(iter.loop_expression);
 514 }
 515
 516
 517 void ConstantConditionEliminator::apply(Stage &stage)
 518 {
 519         stage.content.visit(*this);
 520         NodeRemover().apply(stage, nodes_to_remove);
 521 }
 522
 523 void ConstantConditionEliminator::visit(Block &block)
 524 {
 525         SetForScope<Block *> set_block(current_block, &block);
 526         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 527         {
 528                 insert_point = i;
 529                 (*i)->visit(*this);
 530         }
 531 }
 532
 533 void ConstantConditionEliminator::visit(Conditional &cond)
 534 {
 535         if(Literal *literal = dynamic_cast<Literal *>(cond.condition.get()))
 536                 if(literal->value.check_type<bool>())
 537                 {
 538                         Block &block = (literal->value.value<bool>() ? cond.body : cond.else_body);
 539                         current_block->body.splice(insert_point, block.body);
 540                         nodes_to_remove.insert(&cond);
 541                         return;
 542                 }
 543
 544         TraversingVisitor::visit(cond);
 545 }
 546
 547 void ConstantConditionEliminator::visit(Iteration &iter)
 548 {
 549         if(iter.condition)
 550         {
 551                 /* If the loop condition is always false on the first iteration, the
 552                 entire loop can be removed */
 553                 ExpressionEvaluator::ValueMap values;
 554                 if(VariableDeclaration *var = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
 555                         values[var] = var->init_expression.get();
 556                 ExpressionEvaluator eval(values);
 557                 iter.condition->visit(eval);
 558                 if(eval.is_result_valid() && !eval.get_result())
 559                 {
 560                         nodes_to_remove.insert(&iter);
 561                         return;
 562                 }
 563         }
 564
 565         TraversingVisitor::visit(iter);
 566 }
 567
 568
 569 bool UnusedTypeRemover::apply(Stage &stage)
 570 {
 571         stage.content.visit(*this);
 572         NodeRemover().apply(stage, unused_nodes);
 573         return !unused_nodes.empty();
 574 }
 575
 576 void UnusedTypeRemover::visit(Literal &literal)
 577 {
 578         unused_nodes.erase(literal.type);
 579 }
 580
 581 void UnusedTypeRemover::visit(UnaryExpression &unary)
 582 {
 583         unused_nodes.erase(unary.type);
 584         TraversingVisitor::visit(unary);
 585 }
 586
 587 void UnusedTypeRemover::visit(BinaryExpression &binary)
 588 {
 589         unused_nodes.erase(binary.type);
 590         TraversingVisitor::visit(binary);
 591 }
 592
 593 void UnusedTypeRemover::visit(TernaryExpression &ternary)
 594 {
 595         unused_nodes.erase(ternary.type);
 596         TraversingVisitor::visit(ternary);
 597 }
 598
 599 void UnusedTypeRemover::visit(FunctionCall &call)
 600 {
 601         unused_nodes.erase(call.type);
 602         TraversingVisitor::visit(call);
 603 }
 604
 605 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 606 {
 607         if(type.base_type)
 608                 unused_nodes.erase(type.base_type);
 609         unused_nodes.insert(&type);
 610 }
 611
 612 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 613 {
 614         if(type.base_type)
 615                 unused_nodes.erase(type.base_type);
 616         unused_nodes.insert(&type);
 617 }
 618
 619 void UnusedTypeRemover::visit(StructDeclaration &strct)
 620 {
 621         unused_nodes.insert(&strct);
 622         TraversingVisitor::visit(strct);
 623 }
 624
 625 void UnusedTypeRemover::visit(VariableDeclaration &var)
 626 {
 627         unused_nodes.erase(var.type_declaration);
 628 }
 629
 630 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 631 {
 632         unused_nodes.erase(iface.type_declaration);
 633 }
 634
 635 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 636 {
 637         unused_nodes.erase(func.return_type_declaration);
 638         TraversingVisitor::visit(func);
 639 }
 640
 641
 642 UnusedVariableRemover::UnusedVariableRemover():
 643         stage(0),
 644         interface_block(0),
 645         r_assignment(0),
 646         assignment_target(false),
 647         r_side_effects(false)
 648 { }
 649
 650 bool UnusedVariableRemover::apply(Stage &s)
 651 {
 652         stage = &s;
 653         s.content.visit(*this);
 654
 655         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
 656                 if(i->used_by.empty())
 657                         unused_nodes.insert(i->node);
 658
 659         for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
 660                 if(i->second->instance_name.empty())
 661                         unused_nodes.insert(i->second);
 662
 663         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 664         {
 665                 if(i->second.output)
 666                 {
 667                         /* The last visible assignments of output variables are used by the
 668                         next stage or the API. */
 669                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
 670                                 unused_nodes.erase((*j)->node);
 671                 }
 672
 673                 if(!i->second.output && !i->second.referenced)
 674                 {
 675                         // Don't remove variables from inside interface blocks.
 676                         if(!i->second.interface_block)
 677                                 unused_nodes.insert(i->first);
 678                 }
 679                 else if(i->second.interface_block)
 680                         // Interface blocks are kept if even one member is used.
 681                         unused_nodes.erase(i->second.interface_block);
 682         }
 683
 684         NodeRemover().apply(s, unused_nodes);
 685
 686         return !unused_nodes.empty();
 687 }
 688
 689 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
 690 {
 691         VariableInfo &var_info = variables[target.declaration];
 692         var_info.referenced = true;
 693         if(!assignment_target)
 694         {
 695                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 696                         (*i)->used_by.push_back(&node);
 697         }
 698 }
 699
 700 void UnusedVariableRemover::visit(VariableReference &var)
 701 {
 702         referenced(var.declaration, var);
 703 }
 704
 705 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 706 {
 707         referenced(iface.declaration, iface);
 708 }
 709
 710 void UnusedVariableRemover::visit(UnaryExpression &unary)
 711 {
 712         TraversingVisitor::visit(unary);
 713         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 714                 r_side_effects = true;
 715 }
 716
 717 void UnusedVariableRemover::visit(BinaryExpression &binary)
 718 {
 719         if(binary.oper->token[0]=='[')
 720         {
 721                 binary.left->visit(*this);
 722                 SetFlag set(assignment_target, false);
 723                 binary.right->visit(*this);
 724         }
 725         else
 726                 TraversingVisitor::visit(binary);
 727 }
 728
 729 void UnusedVariableRemover::visit(Assignment &assign)
 730 {
 731         {
 732                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
 733                 assign.left->visit(*this);
 734         }
 735         assign.right->visit(*this);
 736         r_assignment = &assign;
 737         r_side_effects = true;
 738 }
 739
 740 void UnusedVariableRemover::visit(FunctionCall &call)
 741 {
 742         TraversingVisitor::visit(call);
 743         /* Treat function calls as having side effects so expression statements
 744         consisting of nothing but a function call won't be optimized away. */
 745         r_side_effects = true;
 746
 747         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
 748         {
 749                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 750                         if(i->second.output)
 751                                 referenced(i->first, call);
 752         }
 753 }
 754
 755 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
 756 {
 757         assignments.push_back(AssignmentInfo());
 758         AssignmentInfo &assign_info = assignments.back();
 759         assign_info.node = &node;
 760         assign_info.target = target;
 761
 762         /* An assignment to the target hides any assignments to the same target or
 763         its subfields. */
 764         VariableInfo &var_info = variables[target.declaration];
 765         for(unsigned i=0; i<var_info.assignments.size(); ++i)
 766         {
 767                 const Assignment::Target &t = var_info.assignments[i]->target;
 768
 769                 bool subfield = (t.chain_len>=target.chain_len);
 770                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
 771                         subfield = (t.chain[j]==target.chain[j]);
 772
 773                 if(subfield)
 774                         var_info.assignments.erase(var_info.assignments.begin()+i);
 775                 else
 776                         ++i;
 777         }
 778
 779         var_info.assignments.push_back(&assign_info);
 780 }
 781
 782 void UnusedVariableRemover::visit(ExpressionStatement &expr)
 783 {
 784         r_assignment = 0;
 785         r_side_effects = false;
 786         TraversingVisitor::visit(expr);
 787         if(r_assignment && r_assignment->target.declaration)
 788                 record_assignment(r_assignment->target, expr);
 789         if(!r_side_effects)
 790                 unused_nodes.insert(&expr);
 791 }
 792
 793 void UnusedVariableRemover::visit(VariableDeclaration &var)
 794 {
 795         VariableInfo &var_info = variables[&var];
 796         var_info.interface_block = interface_block;
 797
 798         /* Mark variables as output if they're used by the next stage or the
 799         graphics API. */
 800         if(interface_block)
 801                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
 802         else
 803                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
 804
 805         if(var.init_expression)
 806         {
 807                 var_info.initialized = true;
 808                 record_assignment(&var, *var.init_expression);
 809         }
 810         TraversingVisitor::visit(var);
 811 }
 812
 813 void UnusedVariableRemover::visit(InterfaceBlock &iface)
 814 {
 815         if(iface.instance_name.empty())
 816         {
 817                 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
 818                 iface.struct_declaration->members.visit(*this);
 819         }
 820         else
 821         {
 822                 VariableInfo &var_info = variables[&iface];
 823                 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
 824         }
 825 }
 826
 827 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
 828 {
 829         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
 830         {
 831                 BlockVariableMap::iterator j = variables.find(i->first);
 832                 if(j!=variables.end())
 833                 {
 834                         /* The merged blocks started as copies of each other so any common
 835                         assignments must be in the beginning. */
 836                         unsigned k = 0;
 837                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
 838                                 if(i->second.assignments[k]!=j->second.assignments[k])
 839                                         break;
 840
 841                         // Remaining assignments are unique to each block; merge them.
 842                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
 843                         j->second.referenced |= i->second.referenced;
 844                 }
 845                 else
 846                         variables.insert(*i);
 847         }
 848 }
 849
 850 void UnusedVariableRemover::visit(FunctionDeclaration &func)
 851 {
 852         if(func.body.body.empty())
 853                 return;
 854
 855         BlockVariableMap saved_vars = variables;
 856         // Assignments from other functions should not be visible.
 857         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
 858                 i->second.assignments.resize(i->second.initialized);
 859         TraversingVisitor::visit(func);
 860         swap(variables, saved_vars);
 861         merge_variables(saved_vars);
 862
 863         /* Always treat function parameters as referenced.  Removing unused
 864         parameters is not currently supported. */
 865         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 866         {
 867                 BlockVariableMap::iterator j = variables.find(i->get());
 868                 if(j!=variables.end())
 869                         j->second.referenced = true;
 870         }
 871 }
 872
 873 void UnusedVariableRemover::visit(Conditional &cond)
 874 {
 875         cond.condition->visit(*this);
 876         BlockVariableMap saved_vars = variables;
 877         cond.body.visit(*this);
 878         swap(saved_vars, variables);
 879         cond.else_body.visit(*this);
 880
 881         /* Visible assignments after the conditional is the union of those visible
 882         at the end of the if and else blocks.  If there was no else block, then it's
 883         the union of the if block and the state before it. */
 884         merge_variables(saved_vars);
 885 }
 886
 887 void UnusedVariableRemover::visit(Iteration &iter)
 888 {
 889         BlockVariableMap saved_vars = variables;
 890         TraversingVisitor::visit(iter);
 891
 892         /* Merge assignments from the iteration, without clearing previous state.
 893         Further analysis is needed to determine which parts of the iteration body
 894         are always executed, if any. */
 895         merge_variables(saved_vars);
 896 }
 897
 898
 899 bool UnusedFunctionRemover::apply(Stage &stage)
 900 {
 901         stage.content.visit(*this);
 902         NodeRemover().apply(stage, unused_nodes);
 903         return !unused_nodes.empty();
 904 }
 905
 906 void UnusedFunctionRemover::visit(FunctionCall &call)
 907 {
 908         TraversingVisitor::visit(call);
 909
 910         unused_nodes.erase(call.declaration);
 911         if(call.declaration && call.declaration->definition!=call.declaration)
 912                 used_definitions.insert(call.declaration->definition);
 913 }
 914
 915 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
 916 {
 917         TraversingVisitor::visit(func);
 918
 919         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 920                 unused_nodes.insert(&func);
 921 }
 922
 923 } // namespace SL
 924 } // namespace GL
 925 } // namespace Msp