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