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