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->source!=BUILTIN_SOURCE) || 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 || func.source==BUILTIN_SOURCE) && !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 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(RefPtr<Expression> &expr)
 918 {
 919         unused_nodes.erase(expr->type);
 920         TraversingVisitor::visit(expr);
 921 }
 922
 923 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 924 {
 925         if(type.base_type)
 926                 unused_nodes.erase(type.base_type);
 927         unused_nodes.insert(&type);
 928 }
 929
 930 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 931 {
 932         if(type.base_type)
 933                 unused_nodes.erase(type.base_type);
 934         unused_nodes.insert(&type);
 935 }
 936
 937 void UnusedTypeRemover::visit(StructDeclaration &strct)
 938 {
 939         unused_nodes.insert(&strct);
 940         TraversingVisitor::visit(strct);
 941 }
 942
 943 void UnusedTypeRemover::visit(VariableDeclaration &var)
 944 {
 945         unused_nodes.erase(var.type_declaration);
 946         TraversingVisitor::visit(var);
 947 }
 948
 949 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 950 {
 951         unused_nodes.erase(iface.type_declaration);
 952 }
 953
 954 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 955 {
 956         unused_nodes.erase(func.return_type_declaration);
 957         TraversingVisitor::visit(func);
 958 }
 959
 960
 961 UnusedVariableRemover::UnusedVariableRemover():
 962         stage(0),
 963         interface_block(0),
 964         r_assignment(0),
 965         assignment_target(false),
 966         r_side_effects(false),
 967         composite_reference(false)
 968 { }
 969
 970 bool UnusedVariableRemover::apply(Stage &s)
 971 {
 972         stage = &s;
 973         s.content.visit(*this);
 974
 975         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
 976                 if(i->used_by.empty())
 977                         unused_nodes.insert(i->node);
 978
 979         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 980         {
 981                 if(i->second.output)
 982                 {
 983                         /* The last visible assignments of output variables are used by the
 984                         next stage or the API. */
 985                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
 986                                 unused_nodes.erase((*j)->node);
 987                 }
 988
 989                 if(!i->second.output && !i->second.referenced)
 990                 {
 991                         // Don't remove variables from inside interface blocks.
 992                         if(!i->second.interface_block)
 993                                 unused_nodes.insert(i->first);
 994                 }
 995                 else if(i->second.interface_block)
 996                         // Interface blocks are kept if even one member is used.
 997                         unused_nodes.erase(i->second.interface_block);
 998         }
 999
1000         NodeRemover().apply(s, unused_nodes);
1001
1002         return !unused_nodes.empty();
1003 }
1004
1005 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1006 {
1007         VariableInfo &var_info = variables[target.declaration];
1008         var_info.referenced = true;
1009         if(!assignment_target)
1010         {
1011                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1012                 {
1013                         bool covered = true;
1014                         for(unsigned j=0; (covered && j<(*i)->target.chain_len && j<target.chain_len); ++j)
1015                         {
1016                                 Assignment::Target::ChainType type1 = static_cast<Assignment::Target::ChainType>((*i)->target.chain[j]&0xC0);
1017                                 Assignment::Target::ChainType type2 = static_cast<Assignment::Target::ChainType>(target.chain[j]&0xC0);
1018                                 if(type1==Assignment::Target::SWIZZLE || type2==Assignment::Target::SWIZZLE)
1019                                 {
1020                                         unsigned index1 = (*i)->target.chain[j]&0x3F;
1021                                         unsigned index2 = target.chain[j]&0x3F;
1022                                         if(type1==Assignment::Target::SWIZZLE && type2==Assignment::Target::SWIZZLE)
1023                                                 covered = index1&index2;
1024                                         else if(type1==Assignment::Target::ARRAY && index1<4)
1025                                                 covered = index2&(1<<index1);
1026                                         else if(type2==Assignment::Target::ARRAY && index2<4)
1027                                                 covered = index1&(1<<index2);
1028                                         /* If it's some other combination (shouldn't happen), leave
1029                                         covered as true */
1030                                 }
1031                                 else
1032                                         covered = ((*i)->target.chain[j]==target.chain[j]);
1033                         }
1034                         if(covered)
1035                                 (*i)->used_by.push_back(&node);
1036                 }
1037         }
1038 }
1039
1040 void UnusedVariableRemover::visit(VariableReference &var)
1041 {
1042         if(composite_reference)
1043                 r_reference.declaration = var.declaration;
1044         else
1045                 referenced(var.declaration, var);
1046 }
1047
1048 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1049 {
1050         if(composite_reference)
1051                 r_reference.declaration = iface.declaration;
1052         else
1053                 referenced(iface.declaration, iface);
1054 }
1055
1056 void UnusedVariableRemover::visit_composite(Expression &expr)
1057 {
1058         if(!composite_reference)
1059                 r_reference = Assignment::Target();
1060
1061         SetFlag set_composite(composite_reference);
1062         expr.visit(*this);
1063 }
1064
1065 void UnusedVariableRemover::visit(MemberAccess &memacc)
1066 {
1067         visit_composite(*memacc.left);
1068
1069         add_to_chain(r_reference, Assignment::Target::MEMBER, memacc.index);
1070
1071         if(!composite_reference && r_reference.declaration)
1072                 referenced(r_reference, memacc);
1073 }
1074
1075 void UnusedVariableRemover::visit(Swizzle &swizzle)
1076 {
1077         visit_composite(*swizzle.left);
1078
1079         unsigned mask = 0;
1080         for(unsigned i=0; i<swizzle.count; ++i)
1081                 mask |= 1<<swizzle.components[i];
1082         add_to_chain(r_reference, Assignment::Target::SWIZZLE, mask);
1083
1084         if(!composite_reference && r_reference.declaration)
1085                 referenced(r_reference, swizzle);
1086 }
1087
1088 void UnusedVariableRemover::visit(UnaryExpression &unary)
1089 {
1090         TraversingVisitor::visit(unary);
1091         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1092                 r_side_effects = true;
1093 }
1094
1095 void UnusedVariableRemover::visit(BinaryExpression &binary)
1096 {
1097         if(binary.oper->token[0]=='[')
1098         {
1099                 visit_composite(*binary.left);
1100
1101                 {
1102                         SetFlag clear_assignment(assignment_target, false);
1103                         SetFlag clear_composite(composite_reference, false);
1104                         binary.right->visit(*this);
1105                 }
1106
1107                 add_to_chain(r_reference, Assignment::Target::ARRAY, 0x3F);
1108
1109                 if(!composite_reference && r_reference.declaration)
1110                         referenced(r_reference, binary);
1111         }
1112         else
1113         {
1114                 SetFlag clear_composite(composite_reference, false);
1115                 TraversingVisitor::visit(binary);
1116         }
1117 }
1118
1119 void UnusedVariableRemover::visit(TernaryExpression &ternary)
1120 {
1121         SetFlag clear_composite(composite_reference, false);
1122         TraversingVisitor::visit(ternary);
1123 }
1124
1125 void UnusedVariableRemover::visit(Assignment &assign)
1126 {
1127         {
1128                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1129                 assign.left->visit(*this);
1130         }
1131         assign.right->visit(*this);
1132         r_assignment = &assign;
1133         r_side_effects = true;
1134 }
1135
1136 void UnusedVariableRemover::visit(FunctionCall &call)
1137 {
1138         SetFlag clear_composite(composite_reference, false);
1139         TraversingVisitor::visit(call);
1140         /* Treat function calls as having side effects so expression statements
1141         consisting of nothing but a function call won't be optimized away. */
1142         r_side_effects = true;
1143
1144         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1145         {
1146                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1147                         if(i->second.output)
1148                                 referenced(i->first, call);
1149         }
1150 }
1151
1152 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1153 {
1154         assignments.push_back(AssignmentInfo());
1155         AssignmentInfo &assign_info = assignments.back();
1156         assign_info.node = &node;
1157         assign_info.target = target;
1158
1159         /* An assignment to the target hides any assignments to the same target or
1160         its subfields. */
1161         VariableInfo &var_info = variables[target.declaration];
1162         for(unsigned i=0; i<var_info.assignments.size(); ++i)
1163         {
1164                 const Assignment::Target &t = var_info.assignments[i]->target;
1165
1166                 bool subfield = (t.chain_len>=target.chain_len);
1167                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1168                         subfield = (t.chain[j]==target.chain[j]);
1169
1170                 if(subfield)
1171                         var_info.assignments.erase(var_info.assignments.begin()+i);
1172                 else
1173                         ++i;
1174         }
1175
1176         var_info.assignments.push_back(&assign_info);
1177 }
1178
1179 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1180 {
1181         r_assignment = 0;
1182         r_side_effects = false;
1183         TraversingVisitor::visit(expr);
1184         if(r_assignment && r_assignment->target.declaration)
1185                 record_assignment(r_assignment->target, expr);
1186         if(!r_side_effects)
1187                 unused_nodes.insert(&expr);
1188 }
1189
1190 void UnusedVariableRemover::visit(VariableDeclaration &var)
1191 {
1192         VariableInfo &var_info = variables[&var];
1193         var_info.interface_block = interface_block;
1194
1195         /* Mark variables as output if they're used by the next stage or the
1196         graphics API. */
1197         if(interface_block)
1198                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1199         else
1200                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1201
1202         if(var.init_expression)
1203         {
1204                 var_info.initialized = true;
1205                 record_assignment(&var, *var.init_expression);
1206         }
1207         TraversingVisitor::visit(var);
1208 }
1209
1210 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1211 {
1212         VariableInfo &var_info = variables[&iface];
1213         var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1214 }
1215
1216 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1217 {
1218         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1219         {
1220                 BlockVariableMap::iterator j = variables.find(i->first);
1221                 if(j!=variables.end())
1222                 {
1223                         /* The merged blocks started as copies of each other so any common
1224                         assignments must be in the beginning. */
1225                         unsigned k = 0;
1226                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1227                                 if(i->second.assignments[k]!=j->second.assignments[k])
1228                                         break;
1229
1230                         // Remaining assignments are unique to each block; merge them.
1231                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1232                         j->second.referenced |= i->second.referenced;
1233                 }
1234                 else
1235                         variables.insert(*i);
1236         }
1237 }
1238
1239 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1240 {
1241         if(func.body.body.empty())
1242                 return;
1243
1244         BlockVariableMap saved_vars = variables;
1245         // Assignments from other functions should not be visible.
1246         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1247                 i->second.assignments.resize(i->second.initialized);
1248         TraversingVisitor::visit(func);
1249         swap(variables, saved_vars);
1250         merge_variables(saved_vars);
1251
1252         /* Always treat function parameters as referenced.  Removing unused
1253         parameters is not currently supported. */
1254         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1255         {
1256                 BlockVariableMap::iterator j = variables.find(i->get());
1257                 if(j!=variables.end())
1258                         j->second.referenced = true;
1259         }
1260 }
1261
1262 void UnusedVariableRemover::visit(Conditional &cond)
1263 {
1264         cond.condition->visit(*this);
1265         BlockVariableMap saved_vars = variables;
1266         cond.body.visit(*this);
1267         swap(saved_vars, variables);
1268         cond.else_body.visit(*this);
1269
1270         /* Visible assignments after the conditional is the union of those visible
1271         at the end of the if and else blocks.  If there was no else block, then it's
1272         the union of the if block and the state before it. */
1273         merge_variables(saved_vars);
1274 }
1275
1276 void UnusedVariableRemover::visit(Iteration &iter)
1277 {
1278         BlockVariableMap saved_vars = variables;
1279         TraversingVisitor::visit(iter);
1280
1281         /* Merge assignments from the iteration, without clearing previous state.
1282         Further analysis is needed to determine which parts of the iteration body
1283         are always executed, if any. */
1284         merge_variables(saved_vars);
1285 }
1286
1287
1288 bool UnusedFunctionRemover::apply(Stage &stage)
1289 {
1290         stage.content.visit(*this);
1291         NodeRemover().apply(stage, unused_nodes);
1292         return !unused_nodes.empty();
1293 }
1294
1295 void UnusedFunctionRemover::visit(FunctionCall &call)
1296 {
1297         TraversingVisitor::visit(call);
1298
1299         unused_nodes.erase(call.declaration);
1300         if(call.declaration && call.declaration->definition!=call.declaration)
1301                 used_definitions.insert(call.declaration->definition);
1302 }
1303
1304 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1305 {
1306         TraversingVisitor::visit(func);
1307
1308         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1309                 unused_nodes.insert(&func);
1310 }
1311
1312 } // namespace SL
1313 } // namespace GL
1314 } // namespace Msp