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