source/glsl/optimize.cpp

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