source/glsl/optimize.cpp

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