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