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(0)
  70 { }
  71
  72 const string &InlineContentInjector::apply(Stage &stage, FunctionDeclaration &target_func, Block &tgt_blk, const NodeList<Statement>::iterator &ins_pt, FunctionDeclaration &src)
  73 {
  74         staging_block.parent = &tgt_blk;
  75         source_func = &src;
  76         remap_prefix = source_func->name;
  77
  78         for(NodeList<Statement>::iterator i=src.body.body.begin(); i!=src.body.body.end(); ++i)
  79         {
  80                 r_inlined_statement = 0;
  81                 (*i)->visit(*this);
  82                 if(!r_inlined_statement)
  83                         r_inlined_statement = (*i)->clone();
  84
  85                 SetForScope<unsigned> set_remap(remap_names, 2);
  86                 r_inlined_statement->visit(*this);
  87                 staging_block.body.push_back(r_inlined_statement);
  88         }
  89
  90         SetForScope<unsigned> set_remap(remap_names, 1);
  91         SetForScope<string> set_prefix(remap_prefix, target_func.name);
  92         staging_block.variables.clear();
  93         target_func.visit(*this);
  94
  95         tgt_blk.body.splice(ins_pt, staging_block.body);
  96
  97         NodeReorderer().apply(stage, target_func, dependencies);
  98
  99         return r_result_name;
 100 }
 101
 102 void InlineContentInjector::visit(VariableReference &var)
 103 {
 104         if(remap_names)
 105         {
 106                 map<string, VariableDeclaration *>::const_iterator i = staging_block.variables.find(var.name);
 107                 if(i!=staging_block.variables.end())
 108                         var.name = i->second->name;
 109         }
 110         else if(var.declaration)
 111         {
 112                 if(!staging_block.variables.count(var.name))
 113                 {
 114                         dependencies.insert(var.declaration);
 115                         referenced_names.insert(var.name);
 116                 }
 117                 var.declaration->visit(*this);
 118         }
 119 }
 120
 121 void InlineContentInjector::visit(InterfaceBlockReference &iface)
 122 {
 123         if(!remap_names && iface.declaration)
 124         {
 125                 dependencies.insert(iface.declaration);
 126                 referenced_names.insert(iface.name);
 127                 iface.declaration->visit(*this);
 128         }
 129 }
 130
 131 void InlineContentInjector::visit(FunctionCall &call)
 132 {
 133         if(!remap_names && call.declaration)
 134         {
 135                 dependencies.insert(call.declaration);
 136                 referenced_names.insert(call.name);
 137         }
 138         TraversingVisitor::visit(call);
 139 }
 140
 141 void InlineContentInjector::visit(VariableDeclaration &var)
 142 {
 143         TraversingVisitor::visit(var);
 144
 145         if(remap_names)
 146         {
 147                 if(remap_names==2 || referenced_names.count(var.name))
 148                 {
 149                         string mapped_name = get_unused_variable_name(staging_block, var.name, remap_prefix);
 150                         staging_block.variables[var.name] = &var;
 151                         if(mapped_name!=var.name)
 152                                 staging_block.variables[mapped_name] = &var;
 153                         var.name = mapped_name;
 154                 }
 155         }
 156         else if(var.type_declaration)
 157         {
 158                 dependencies.insert(var.type_declaration);
 159                 referenced_names.insert(var.type_declaration->name);
 160                 var.type_declaration->visit(*this);
 161         }
 162 }
 163
 164 void InlineContentInjector::visit(Return &ret)
 165 {
 166         TraversingVisitor::visit(ret);
 167
 168         if(!remap_names && ret.expression)
 169         {
 170                 /* Create a new variable to hold the return value of the inlined
 171                 function. */
 172                 r_result_name = get_unused_variable_name(staging_block, "_return", source_func->name);
 173                 RefPtr<VariableDeclaration> var = new VariableDeclaration;
 174                 var->source = ret.source;
 175                 var->line = ret.line;
 176                 var->type = source_func->return_type;
 177                 var->name = r_result_name;
 178                 var->init_expression = ret.expression->clone();
 179                 r_inlined_statement = var;
 180         }
 181 }
 182
 183
 184 FunctionInliner::FunctionInliner():
 185         current_function(0),
 186         r_any_inlined(false),
 187         r_inlined_here(false)
 188 { }
 189
 190 bool FunctionInliner::apply(Stage &s)
 191 {
 192         stage = &s;
 193         inlineable = InlineableFunctionLocator().apply(s);
 194         r_any_inlined = false;
 195         s.content.visit(*this);
 196         return r_any_inlined;
 197 }
 198
 199 void FunctionInliner::visit(RefPtr<Expression> &ptr)
 200 {
 201         r_inline_result = 0;
 202         ptr->visit(*this);
 203         if(r_inline_result)
 204         {
 205                 ptr = r_inline_result;
 206                 r_any_inlined = true;
 207         }
 208         r_inline_result = 0;
 209 }
 210
 211 void FunctionInliner::visit(Block &block)
 212 {
 213         SetForScope<Block *> set_block(current_block, &block);
 214         SetForScope<NodeList<Statement>::iterator> save_insert_point(insert_point, block.body.begin());
 215         for(NodeList<Statement>::iterator i=block.body.begin(); (!r_inlined_here && i!=block.body.end()); ++i)
 216         {
 217                 insert_point = i;
 218                 (*i)->visit(*this);
 219         }
 220 }
 221
 222 void FunctionInliner::visit(FunctionCall &call)
 223 {
 224         if(r_inlined_here)
 225                 return;
 226
 227         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 228                 visit(*i);
 229
 230         FunctionDeclaration *def = call.declaration;
 231         if(def)
 232                 def = def->definition;
 233
 234         if(def && inlineable.count(def))
 235         {
 236                 string result_name = InlineContentInjector().apply(*stage, *current_function, *current_block, insert_point, *def);
 237
 238                 // This will later get removed by UnusedVariableRemover.
 239                 if(result_name.empty())
 240                         result_name = "msp_unused_from_inline";
 241
 242                 RefPtr<VariableReference> ref = new VariableReference;
 243                 ref->name = result_name;
 244                 r_inline_result = ref;
 245
 246                 /* Inlined variables need to be resolved before this function can be
 247                 inlined further. */
 248                 inlineable.erase(current_function);
 249                 r_inlined_here = true;
 250         }
 251 }
 252
 253 void FunctionInliner::visit(FunctionDeclaration &func)
 254 {
 255         SetForScope<FunctionDeclaration *> set_func(current_function, &func);
 256         TraversingVisitor::visit(func);
 257         r_inlined_here = false;
 258 }
 259
 260 void FunctionInliner::visit(Iteration &iter)
 261 {
 262         /* Visit the initialization statement before entering the loop body so the
 263         inlined statements get inserted outside. */
 264         if(iter.init_statement)
 265                 iter.init_statement->visit(*this);
 266
 267         SetForScope<Block *> set_block(current_block, &iter.body);
 268         /* Skip the condition and loop expression parts because they're not properly
 269         inside the body block.  Inlining anything into them will require a more
 270         comprehensive transformation. */
 271         iter.body.visit(*this);
 272 }
 273
 274
 275 ExpressionInliner::ExpressionInfo::ExpressionInfo():
 276         expression(0),
 277         assign_scope(0),
 278         inline_point(0),
 279         trivial(false),
 280         available(true)
 281 { }
 282
 283
 284 ExpressionInliner::ExpressionInliner():
 285         r_ref_info(0),
 286         r_any_inlined(false),
 287         r_trivial(false),
 288         mutating(false),
 289         iteration_init(false),
 290         iteration_body(0),
 291         r_oper(0)
 292 { }
 293
 294 bool ExpressionInliner::apply(Stage &s)
 295 {
 296         s.content.visit(*this);
 297         return r_any_inlined;
 298 }
 299
 300 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
 301 {
 302         ptr = expr.clone();
 303         r_any_inlined = true;
 304 }
 305
 306 void ExpressionInliner::visit(Block &block)
 307 {
 308         TraversingVisitor::visit(block);
 309
 310         for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 311         {
 312                 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
 313                 for(; (j!=expressions.end() && j->first.declaration==i->second); )
 314                 {
 315                         if(j->second.expression && j->second.inline_point)
 316                                 inline_expression(*j->second.expression, *j->second.inline_point);
 317
 318                         expressions.erase(j++);
 319                 }
 320         }
 321
 322         /* Expressions assigned in this block may depend on local variables of the
 323         block.  If this is a conditionally executed block, the assignments might not
 324         always happen.  Mark the expressions as not available to any outer blocks. */
 325         for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
 326                 if(i->second.assign_scope==&block)
 327                         i->second.available = false;
 328 }
 329
 330 void ExpressionInliner::visit(RefPtr<Expression> &expr)
 331 {
 332         r_ref_info = 0;
 333         expr->visit(*this);
 334         if(r_ref_info && r_ref_info->expression && r_ref_info->available)
 335         {
 336                 if(iteration_body && !r_ref_info->trivial)
 337                 {
 338                         /* Don't inline non-trivial expressions which were assigned outside
 339                         an iteration statement.  The iteration may run multiple times, which
 340                         would cause the expression to also be evaluated multiple times. */
 341                         Block *i = r_ref_info->assign_scope;
 342                         for(; (i && i!=iteration_body); i=i->parent) ;
 343                         if(!i)
 344                                 return;
 345                 }
 346
 347                 if(r_ref_info->trivial)
 348                         inline_expression(*r_ref_info->expression, expr);
 349                 else
 350                         /* Record the inline point for a non-trivial expression but don't
 351                         inline it yet.  It might turn out it shouldn't be inlined after all. */
 352                         r_ref_info->inline_point = &expr;
 353         }
 354         r_oper = expr->oper;
 355         r_ref_info = 0;
 356 }
 357
 358 void ExpressionInliner::visit(VariableReference &var)
 359 {
 360         if(var.declaration)
 361         {
 362                 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
 363                 if(i!=expressions.end())
 364                 {
 365                         /* If a non-trivial expression is referenced multiple times, don't
 366                         inline it. */
 367                         if(i->second.inline_point && !i->second.trivial)
 368                                 i->second.expression = 0;
 369                         /* Mutating expressions are analogous to self-referencing assignments
 370                         and prevent inlining. */
 371                         if(mutating)
 372                                 i->second.expression = 0;
 373                         r_ref_info = &i->second;
 374                 }
 375         }
 376 }
 377
 378 void ExpressionInliner::visit(MemberAccess &memacc)
 379 {
 380         visit(memacc.left);
 381         r_trivial = false;
 382 }
 383
 384 void ExpressionInliner::visit(Swizzle &swizzle)
 385 {
 386         visit(swizzle.left);
 387         r_trivial = false;
 388 }
 389
 390 void ExpressionInliner::visit(UnaryExpression &unary)
 391 {
 392         SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
 393         visit(unary.expression);
 394         r_trivial = false;
 395 }
 396
 397 void ExpressionInliner::visit(BinaryExpression &binary)
 398 {
 399         visit(binary.left);
 400         {
 401                 SetFlag clear_target(mutating, false);
 402                 visit(binary.right);
 403         }
 404         r_trivial = false;
 405 }
 406
 407 void ExpressionInliner::visit(Assignment &assign)
 408 {
 409         {
 410                 SetFlag set_target(mutating);
 411                 visit(assign.left);
 412         }
 413         r_oper = 0;
 414         visit(assign.right);
 415
 416         map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
 417         if(i!=expressions.end())
 418         {
 419                 /* Self-referencing assignments can't be inlined without additional
 420                 work.  Just clear any previous expression. */
 421                 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
 422                 i->second.assign_scope = current_block;
 423                 i->second.inline_point = 0;
 424                 i->second.available = true;
 425         }
 426
 427         r_trivial = false;
 428 }
 429
 430 void ExpressionInliner::visit(TernaryExpression &ternary)
 431 {
 432         visit(ternary.condition);
 433         visit(ternary.true_expr);
 434         visit(ternary.false_expr);
 435         r_trivial = false;
 436 }
 437
 438 void ExpressionInliner::visit(FunctionCall &call)
 439 {
 440         TraversingVisitor::visit(call);
 441         r_trivial = false;
 442 }
 443
 444 void ExpressionInliner::visit(VariableDeclaration &var)
 445 {
 446         r_oper = 0;
 447         r_trivial = true;
 448         TraversingVisitor::visit(var);
 449
 450         bool constant = var.constant;
 451         if(constant && var.layout)
 452         {
 453                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 454                         constant = (i->name!="constant_id");
 455         }
 456
 457         /* Only inline global variables if they're constant and have trivial
 458         initializers.  Non-constant variables could change in ways which are hard to
 459         analyze and non-trivial expressions could be expensive to inline.  */
 460         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 461         {
 462                 ExpressionInfo &info = expressions[&var];
 463                 /* Assume variables declared in an iteration initialization statement
 464                 will have their values change throughout the iteration. */
 465                 info.expression = (iteration_init ? 0 : var.init_expression.get());
 466                 info.assign_scope = current_block;
 467                 info.trivial = r_trivial;
 468         }
 469 }
 470
 471 void ExpressionInliner::visit(Iteration &iter)
 472 {
 473         SetForScope<Block *> set_block(current_block, &iter.body);
 474         if(iter.init_statement)
 475         {
 476                 SetFlag set_init(iteration_init);
 477                 iter.init_statement->visit(*this);
 478         }
 479
 480         SetForScope<Block *> set_body(iteration_body, &iter.body);
 481         if(iter.condition)
 482                 visit(iter.condition);
 483         iter.body.visit(*this);
 484         if(iter.loop_expression)
 485                 visit(iter.loop_expression);
 486 }
 487
 488
 489 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
 490 {
 491         if(value.check_type<bool>())
 492                 return BasicTypeDeclaration::BOOL;
 493         else if(value.check_type<int>())
 494                 return BasicTypeDeclaration::INT;
 495         else if(value.check_type<float>())
 496                 return BasicTypeDeclaration::FLOAT;
 497         else
 498                 return BasicTypeDeclaration::VOID;
 499 }
 500
 501 template<typename T>
 502 T ConstantFolder::evaluate_logical(char oper, T left, T right)
 503 {
 504         switch(oper)
 505         {
 506         case '&': return left&right;
 507         case '|': return left|right;
 508         case '^': return left^right;
 509         default: return T();
 510         }
 511 }
 512
 513 template<typename T>
 514 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
 515 {
 516         switch(oper[0]|oper[1])
 517         {
 518         case '<': return left<right;
 519         case '<'|'=': return left<=right;
 520         case '>': return left>right;
 521         case '>'|'=': return left>=right;
 522         default: return false;
 523         }
 524 }
 525
 526 template<typename T>
 527 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
 528 {
 529         switch(oper)
 530         {
 531         case '+': return left+right;
 532         case '-': return left-right;
 533         case '*': return left*right;
 534         case '/': return left/right;
 535         default: return T();
 536         }
 537 }
 538
 539 void ConstantFolder::set_result(const Variant &value, bool literal)
 540 {
 541         r_constant_value = value;
 542         r_constant = true;
 543         r_literal = literal;
 544 }
 545
 546 void ConstantFolder::visit(RefPtr<Expression> &expr)
 547 {
 548         r_constant_value = Variant();
 549         r_constant = false;
 550         r_literal = false;
 551         r_uses_iter_var = false;
 552         expr->visit(*this);
 553         /* Don't replace literals since they'd only be replaced with an identical
 554         literal.  Also skip anything that uses an iteration variable, but pass on
 555         the result so the Iteration visiting function can handle it. */
 556         if(!r_constant || r_literal || r_uses_iter_var)
 557                 return;
 558
 559         BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
 560         if(kind==BasicTypeDeclaration::VOID)
 561         {
 562                 r_constant = false;
 563                 return;
 564         }
 565
 566         RefPtr<Literal> literal = new Literal;
 567         if(kind==BasicTypeDeclaration::BOOL)
 568                 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
 569         else if(kind==BasicTypeDeclaration::INT)
 570                 literal->token = lexical_cast<string>(r_constant_value.value<int>());
 571         else if(kind==BasicTypeDeclaration::FLOAT)
 572                 literal->token = lexical_cast<string>(r_constant_value.value<float>());
 573         literal->value = r_constant_value;
 574         expr = literal;
 575 }
 576
 577 void ConstantFolder::visit(Literal &literal)
 578 {
 579         set_result(literal.value, true);
 580 }
 581
 582 void ConstantFolder::visit(VariableReference &var)
 583 {
 584         /* If an iteration variable is initialized with a constant value, return
 585         that value here for the purpose of evaluating the loop condition for the
 586         first iteration. */
 587         if(var.declaration==iteration_var)
 588         {
 589                 set_result(iter_init_value);
 590                 r_uses_iter_var = true;
 591         }
 592 }
 593
 594 void ConstantFolder::visit(MemberAccess &memacc)
 595 {
 596         TraversingVisitor::visit(memacc);
 597         r_constant = false;
 598 }
 599
 600 void ConstantFolder::visit(Swizzle &swizzle)
 601 {
 602         TraversingVisitor::visit(swizzle);
 603         r_constant = false;
 604 }
 605
 606 void ConstantFolder::visit(UnaryExpression &unary)
 607 {
 608         TraversingVisitor::visit(unary);
 609         bool can_fold = r_constant;
 610         r_constant = false;
 611         if(!can_fold)
 612                 return;
 613
 614         BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
 615
 616         char oper = unary.oper->token[0];
 617         char oper2 = unary.oper->token[1];
 618         if(oper=='!')
 619         {
 620                 if(kind==BasicTypeDeclaration::BOOL)
 621                         set_result(!r_constant_value.value<bool>());
 622         }
 623         else if(oper=='~')
 624         {
 625                 if(kind==BasicTypeDeclaration::INT)
 626                         set_result(~r_constant_value.value<int>());
 627         }
 628         else if(oper=='-' && !oper2)
 629         {
 630                 if(kind==BasicTypeDeclaration::INT)
 631                         set_result(-r_constant_value.value<int>());
 632                 else if(kind==BasicTypeDeclaration::FLOAT)
 633                         set_result(-r_constant_value.value<float>());
 634         }
 635 }
 636
 637 void ConstantFolder::visit(BinaryExpression &binary)
 638 {
 639         visit(binary.left);
 640         bool left_constant = r_constant;
 641         bool left_iter_var = r_uses_iter_var;
 642         Variant left_value = r_constant_value;
 643         visit(binary.right);
 644         if(left_iter_var)
 645                 r_uses_iter_var = true;
 646
 647         bool can_fold = (left_constant && r_constant);
 648         r_constant = false;
 649         if(!can_fold)
 650                 return;
 651
 652         BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
 653         BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
 654         // Currently only expressions with both sides of equal types are handled.
 655         if(left_kind!=right_kind)
 656                 return;
 657
 658         char oper = binary.oper->token[0];
 659         char oper2 = binary.oper->token[1];
 660         if(oper=='&' || oper=='|' || oper=='^')
 661         {
 662                 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
 663                         set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
 664                 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
 665                         set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
 666         }
 667         else if((oper=='<' || oper=='>') && oper2!=oper)
 668         {
 669                 if(left_kind==BasicTypeDeclaration::INT)
 670                         set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
 671                 else if(left_kind==BasicTypeDeclaration::FLOAT)
 672                         set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
 673         }
 674         else if((oper=='=' || oper=='!') && oper2=='=')
 675         {
 676                 if(left_kind==BasicTypeDeclaration::INT)
 677                         set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
 678                 if(left_kind==BasicTypeDeclaration::FLOAT)
 679                         set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
 680         }
 681         else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
 682         {
 683                 if(left_kind==BasicTypeDeclaration::INT)
 684                         set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
 685                 else if(left_kind==BasicTypeDeclaration::FLOAT)
 686                         set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
 687         }
 688         else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
 689         {
 690                 if(left_kind!=BasicTypeDeclaration::INT)
 691                         return;
 692
 693                 if(oper=='%')
 694                         set_result(left_value.value<int>()%r_constant_value.value<int>());
 695                 else if(oper=='<')
 696                         set_result(left_value.value<int>()<<r_constant_value.value<int>());
 697                 else if(oper=='>')
 698                         set_result(left_value.value<int>()>>r_constant_value.value<int>());
 699         }
 700 }
 701
 702 void ConstantFolder::visit(Assignment &assign)
 703 {
 704         TraversingVisitor::visit(assign);
 705         r_constant = false;
 706 }
 707
 708 void ConstantFolder::visit(TernaryExpression &ternary)
 709 {
 710         TraversingVisitor::visit(ternary);
 711         r_constant = false;
 712 }
 713
 714 void ConstantFolder::visit(FunctionCall &call)
 715 {
 716         TraversingVisitor::visit(call);
 717         r_constant = false;
 718 }
 719
 720 void ConstantFolder::visit(VariableDeclaration &var)
 721 {
 722         if(iteration_init && var.init_expression)
 723         {
 724                 visit(var.init_expression);
 725                 if(r_constant)
 726                 {
 727                         /* Record the value of a constant initialization expression of an
 728                         iteration, so it can be used to evaluate the loop condition. */
 729                         iteration_var = &var;
 730                         iter_init_value = r_constant_value;
 731                 }
 732         }
 733         else
 734                 TraversingVisitor::visit(var);
 735 }
 736
 737 void ConstantFolder::visit(Iteration &iter)
 738 {
 739         SetForScope<Block *> set_block(current_block, &iter.body);
 740
 741         /* The iteration variable is not normally inlined into expressions, so we
 742         process it specially here.  If the initial value causes the loop condition
 743         to evaluate to false, then the expression can be folded. */
 744         iteration_var = 0;
 745         if(iter.init_statement)
 746         {
 747                 SetFlag set_init(iteration_init);
 748                 iter.init_statement->visit(*this);
 749         }
 750
 751         if(iter.condition)
 752         {
 753                 visit(iter.condition);
 754                 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
 755                 {
 756                         RefPtr<Literal> literal = new Literal;
 757                         literal->token = "false";
 758                         literal->value = r_constant_value;
 759                         iter.condition = literal;
 760                 }
 761         }
 762         iteration_var = 0;
 763
 764         iter.body.visit(*this);
 765         if(iter.loop_expression)
 766                 visit(iter.loop_expression);
 767 }
 768
 769
 770 void ConstantConditionEliminator::apply(Stage &stage)
 771 {
 772         stage.content.visit(*this);
 773         NodeRemover().apply(stage, nodes_to_remove);
 774 }
 775
 776 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
 777 {
 778         if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
 779                 if(literal->value.check_type<bool>())
 780                         return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
 781         return NOT_CONSTANT;
 782 }
 783
 784 void ConstantConditionEliminator::visit(Block &block)
 785 {
 786         SetForScope<Block *> set_block(current_block, &block);
 787         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 788         {
 789                 insert_point = i;
 790                 (*i)->visit(*this);
 791         }
 792 }
 793
 794 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
 795 {
 796         r_ternary_result = 0;
 797         expr->visit(*this);
 798         if(r_ternary_result)
 799                 expr = r_ternary_result;
 800         r_ternary_result = 0;
 801 }
 802
 803 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
 804 {
 805         ConstantStatus result = check_constant_condition(*ternary.condition);
 806         if(result!=NOT_CONSTANT)
 807                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
 808         else
 809                 r_ternary_result = 0;
 810 }
 811
 812 void ConstantConditionEliminator::visit(Conditional &cond)
 813 {
 814         ConstantStatus result = check_constant_condition(*cond.condition);
 815         if(result!=NOT_CONSTANT)
 816         {
 817                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
 818                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
 819                 current_block->body.splice(insert_point, block.body);
 820                 nodes_to_remove.insert(&cond);
 821                 return;
 822         }
 823
 824         TraversingVisitor::visit(cond);
 825 }
 826
 827 void ConstantConditionEliminator::visit(Iteration &iter)
 828 {
 829         if(iter.condition)
 830         {
 831                 ConstantStatus result = check_constant_condition(*iter.condition);
 832                 if(result==CONSTANT_FALSE)
 833                 {
 834                         nodes_to_remove.insert(&iter);
 835                         return;
 836                 }
 837         }
 838
 839         TraversingVisitor::visit(iter);
 840 }
 841
 842
 843 bool UnusedTypeRemover::apply(Stage &stage)
 844 {
 845         stage.content.visit(*this);
 846         NodeRemover().apply(stage, unused_nodes);
 847         return !unused_nodes.empty();
 848 }
 849
 850 void UnusedTypeRemover::visit(Literal &literal)
 851 {
 852         unused_nodes.erase(literal.type);
 853 }
 854
 855 void UnusedTypeRemover::visit(UnaryExpression &unary)
 856 {
 857         unused_nodes.erase(unary.type);
 858         TraversingVisitor::visit(unary);
 859 }
 860
 861 void UnusedTypeRemover::visit(BinaryExpression &binary)
 862 {
 863         unused_nodes.erase(binary.type);
 864         TraversingVisitor::visit(binary);
 865 }
 866
 867 void UnusedTypeRemover::visit(TernaryExpression &ternary)
 868 {
 869         unused_nodes.erase(ternary.type);
 870         TraversingVisitor::visit(ternary);
 871 }
 872
 873 void UnusedTypeRemover::visit(FunctionCall &call)
 874 {
 875         unused_nodes.erase(call.type);
 876         TraversingVisitor::visit(call);
 877 }
 878
 879 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 880 {
 881         if(type.base_type)
 882                 unused_nodes.erase(type.base_type);
 883         unused_nodes.insert(&type);
 884 }
 885
 886 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 887 {
 888         if(type.base_type)
 889                 unused_nodes.erase(type.base_type);
 890         unused_nodes.insert(&type);
 891 }
 892
 893 void UnusedTypeRemover::visit(StructDeclaration &strct)
 894 {
 895         unused_nodes.insert(&strct);
 896         TraversingVisitor::visit(strct);
 897 }
 898
 899 void UnusedTypeRemover::visit(VariableDeclaration &var)
 900 {
 901         unused_nodes.erase(var.type_declaration);
 902 }
 903
 904 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 905 {
 906         unused_nodes.erase(iface.type_declaration);
 907 }
 908
 909 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 910 {
 911         unused_nodes.erase(func.return_type_declaration);
 912         TraversingVisitor::visit(func);
 913 }
 914
 915
 916 UnusedVariableRemover::UnusedVariableRemover():
 917         stage(0),
 918         interface_block(0),
 919         r_assignment(0),
 920         assignment_target(false),
 921         r_side_effects(false)
 922 { }
 923
 924 bool UnusedVariableRemover::apply(Stage &s)
 925 {
 926         stage = &s;
 927         s.content.visit(*this);
 928
 929         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
 930                 if(i->used_by.empty())
 931                         unused_nodes.insert(i->node);
 932
 933         for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
 934                 if(i->second->instance_name.empty())
 935                         unused_nodes.insert(i->second);
 936
 937         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 938         {
 939                 if(i->second.output)
 940                 {
 941                         /* The last visible assignments of output variables are used by the
 942                         next stage or the API. */
 943                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
 944                                 unused_nodes.erase((*j)->node);
 945                 }
 946
 947                 if(!i->second.output && !i->second.referenced)
 948                 {
 949                         // Don't remove variables from inside interface blocks.
 950                         if(!i->second.interface_block)
 951                                 unused_nodes.insert(i->first);
 952                 }
 953                 else if(i->second.interface_block)
 954                         // Interface blocks are kept if even one member is used.
 955                         unused_nodes.erase(i->second.interface_block);
 956         }
 957
 958         NodeRemover().apply(s, unused_nodes);
 959
 960         return !unused_nodes.empty();
 961 }
 962
 963 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
 964 {
 965         VariableInfo &var_info = variables[target.declaration];
 966         var_info.referenced = true;
 967         if(!assignment_target)
 968         {
 969                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 970                         (*i)->used_by.push_back(&node);
 971         }
 972 }
 973
 974 void UnusedVariableRemover::visit(VariableReference &var)
 975 {
 976         referenced(var.declaration, var);
 977 }
 978
 979 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 980 {
 981         referenced(iface.declaration, iface);
 982 }
 983
 984 void UnusedVariableRemover::visit(UnaryExpression &unary)
 985 {
 986         TraversingVisitor::visit(unary);
 987         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 988                 r_side_effects = true;
 989 }
 990
 991 void UnusedVariableRemover::visit(BinaryExpression &binary)
 992 {
 993         if(binary.oper->token[0]=='[')
 994         {
 995                 binary.left->visit(*this);
 996                 SetFlag set(assignment_target, false);
 997                 binary.right->visit(*this);
 998         }
 999         else
1000                 TraversingVisitor::visit(binary);
1001 }
1002
1003 void UnusedVariableRemover::visit(Assignment &assign)
1004 {
1005         {
1006                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1007                 assign.left->visit(*this);
1008         }
1009         assign.right->visit(*this);
1010         r_assignment = &assign;
1011         r_side_effects = true;
1012 }
1013
1014 void UnusedVariableRemover::visit(FunctionCall &call)
1015 {
1016         TraversingVisitor::visit(call);
1017         /* Treat function calls as having side effects so expression statements
1018         consisting of nothing but a function call won't be optimized away. */
1019         r_side_effects = true;
1020
1021         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1022         {
1023                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1024                         if(i->second.output)
1025                                 referenced(i->first, call);
1026         }
1027 }
1028
1029 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1030 {
1031         assignments.push_back(AssignmentInfo());
1032         AssignmentInfo &assign_info = assignments.back();
1033         assign_info.node = &node;
1034         assign_info.target = target;
1035
1036         /* An assignment to the target hides any assignments to the same target or
1037         its subfields. */
1038         VariableInfo &var_info = variables[target.declaration];
1039         for(unsigned i=0; i<var_info.assignments.size(); ++i)
1040         {
1041                 const Assignment::Target &t = var_info.assignments[i]->target;
1042
1043                 bool subfield = (t.chain_len>=target.chain_len);
1044                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1045                         subfield = (t.chain[j]==target.chain[j]);
1046
1047                 if(subfield)
1048                         var_info.assignments.erase(var_info.assignments.begin()+i);
1049                 else
1050                         ++i;
1051         }
1052
1053         var_info.assignments.push_back(&assign_info);
1054 }
1055
1056 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1057 {
1058         r_assignment = 0;
1059         r_side_effects = false;
1060         TraversingVisitor::visit(expr);
1061         if(r_assignment && r_assignment->target.declaration)
1062                 record_assignment(r_assignment->target, expr);
1063         if(!r_side_effects)
1064                 unused_nodes.insert(&expr);
1065 }
1066
1067 void UnusedVariableRemover::visit(VariableDeclaration &var)
1068 {
1069         VariableInfo &var_info = variables[&var];
1070         var_info.interface_block = interface_block;
1071
1072         /* Mark variables as output if they're used by the next stage or the
1073         graphics API. */
1074         if(interface_block)
1075                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
1076         else
1077                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1078
1079         if(var.init_expression)
1080         {
1081                 var_info.initialized = true;
1082                 record_assignment(&var, *var.init_expression);
1083         }
1084         TraversingVisitor::visit(var);
1085 }
1086
1087 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1088 {
1089         if(iface.instance_name.empty())
1090         {
1091                 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1092                 iface.struct_declaration->members.visit(*this);
1093         }
1094         else
1095         {
1096                 VariableInfo &var_info = variables[&iface];
1097                 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
1098         }
1099 }
1100
1101 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1102 {
1103         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1104         {
1105                 BlockVariableMap::iterator j = variables.find(i->first);
1106                 if(j!=variables.end())
1107                 {
1108                         /* The merged blocks started as copies of each other so any common
1109                         assignments must be in the beginning. */
1110                         unsigned k = 0;
1111                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1112                                 if(i->second.assignments[k]!=j->second.assignments[k])
1113                                         break;
1114
1115                         // Remaining assignments are unique to each block; merge them.
1116                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1117                         j->second.referenced |= i->second.referenced;
1118                 }
1119                 else
1120                         variables.insert(*i);
1121         }
1122 }
1123
1124 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1125 {
1126         if(func.body.body.empty())
1127                 return;
1128
1129         BlockVariableMap saved_vars = variables;
1130         // Assignments from other functions should not be visible.
1131         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1132                 i->second.assignments.resize(i->second.initialized);
1133         TraversingVisitor::visit(func);
1134         swap(variables, saved_vars);
1135         merge_variables(saved_vars);
1136
1137         /* Always treat function parameters as referenced.  Removing unused
1138         parameters is not currently supported. */
1139         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1140         {
1141                 BlockVariableMap::iterator j = variables.find(i->get());
1142                 if(j!=variables.end())
1143                         j->second.referenced = true;
1144         }
1145 }
1146
1147 void UnusedVariableRemover::visit(Conditional &cond)
1148 {
1149         cond.condition->visit(*this);
1150         BlockVariableMap saved_vars = variables;
1151         cond.body.visit(*this);
1152         swap(saved_vars, variables);
1153         cond.else_body.visit(*this);
1154
1155         /* Visible assignments after the conditional is the union of those visible
1156         at the end of the if and else blocks.  If there was no else block, then it's
1157         the union of the if block and the state before it. */
1158         merge_variables(saved_vars);
1159 }
1160
1161 void UnusedVariableRemover::visit(Iteration &iter)
1162 {
1163         BlockVariableMap saved_vars = variables;
1164         TraversingVisitor::visit(iter);
1165
1166         /* Merge assignments from the iteration, without clearing previous state.
1167         Further analysis is needed to determine which parts of the iteration body
1168         are always executed, if any. */
1169         merge_variables(saved_vars);
1170 }
1171
1172
1173 bool UnusedFunctionRemover::apply(Stage &stage)
1174 {
1175         stage.content.visit(*this);
1176         NodeRemover().apply(stage, unused_nodes);
1177         return !unused_nodes.empty();
1178 }
1179
1180 void UnusedFunctionRemover::visit(FunctionCall &call)
1181 {
1182         TraversingVisitor::visit(call);
1183
1184         unused_nodes.erase(call.declaration);
1185         if(call.declaration && call.declaration->definition!=call.declaration)
1186                 used_definitions.insert(call.declaration->definition);
1187 }
1188
1189 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1190 {
1191         TraversingVisitor::visit(func);
1192
1193         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1194                 unused_nodes.insert(&func);
1195 }
1196
1197 } // namespace SL
1198 } // namespace GL
1199 } // namespace Msp