source/glsl/optimize.cpp

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