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::ExpressionInliner():
 372         r_ref_info(0),
 373         r_any_inlined(false),
 374         r_trivial(false),
 375         mutating(false),
 376         iteration_init(false),
 377         iteration_body(0),
 378         r_oper(0)
 379 { }
 380
 381 bool ExpressionInliner::apply(Stage &s)
 382 {
 383         s.content.visit(*this);
 384         return r_any_inlined;
 385 }
 386
 387 void ExpressionInliner::inline_expression(Expression &expr, RefPtr<Expression> &ptr)
 388 {
 389         ptr = expr.clone();
 390         r_any_inlined = true;
 391 }
 392
 393 void ExpressionInliner::visit(Block &block)
 394 {
 395         TraversingVisitor::visit(block);
 396
 397         for(map<string, VariableDeclaration *>::iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 398         {
 399                 map<Assignment::Target, ExpressionInfo>::iterator j = expressions.lower_bound(i->second);
 400                 for(; (j!=expressions.end() && j->first.declaration==i->second); )
 401                 {
 402                         if(j->second.expression && j->second.inline_point)
 403                                 inline_expression(*j->second.expression, *j->second.inline_point);
 404
 405                         expressions.erase(j++);
 406                 }
 407         }
 408
 409         /* Expressions assigned in this block may depend on local variables of the
 410         block.  If this is a conditionally executed block, the assignments might not
 411         always happen.  Mark the expressions as not available to any outer blocks. */
 412         for(map<Assignment::Target, ExpressionInfo>::iterator i=expressions.begin(); i!=expressions.end(); ++i)
 413                 if(i->second.assign_scope==&block)
 414                         i->second.available = false;
 415 }
 416
 417 void ExpressionInliner::visit(RefPtr<Expression> &expr)
 418 {
 419         r_ref_info = 0;
 420         expr->visit(*this);
 421         if(r_ref_info && r_ref_info->expression && r_ref_info->available)
 422         {
 423                 if(iteration_body && !r_ref_info->trivial)
 424                 {
 425                         /* Don't inline non-trivial expressions which were assigned outside
 426                         an iteration statement.  The iteration may run multiple times, which
 427                         would cause the expression to also be evaluated multiple times. */
 428                         Block *i = r_ref_info->assign_scope;
 429                         for(; (i && i!=iteration_body); i=i->parent) ;
 430                         if(!i)
 431                                 return;
 432                 }
 433
 434                 if(r_ref_info->trivial)
 435                         inline_expression(*r_ref_info->expression, expr);
 436                 else
 437                         /* Record the inline point for a non-trivial expression but don't
 438                         inline it yet.  It might turn out it shouldn't be inlined after all. */
 439                         r_ref_info->inline_point = &expr;
 440         }
 441         r_oper = expr->oper;
 442         r_ref_info = 0;
 443 }
 444
 445 void ExpressionInliner::visit(VariableReference &var)
 446 {
 447         if(var.declaration)
 448         {
 449                 map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(var.declaration);
 450                 if(i!=expressions.end())
 451                 {
 452                         /* If a non-trivial expression is referenced multiple times, don't
 453                         inline it. */
 454                         if(i->second.inline_point && !i->second.trivial)
 455                                 i->second.expression = 0;
 456                         /* Mutating expressions are analogous to self-referencing assignments
 457                         and prevent inlining. */
 458                         if(mutating)
 459                                 i->second.expression = 0;
 460                         r_ref_info = &i->second;
 461                 }
 462         }
 463 }
 464
 465 void ExpressionInliner::visit(MemberAccess &memacc)
 466 {
 467         visit(memacc.left);
 468         r_trivial = false;
 469 }
 470
 471 void ExpressionInliner::visit(Swizzle &swizzle)
 472 {
 473         visit(swizzle.left);
 474         r_trivial = false;
 475 }
 476
 477 void ExpressionInliner::visit(UnaryExpression &unary)
 478 {
 479         SetFlag set_target(mutating, mutating || unary.oper->token[1]=='+' || unary.oper->token[1]=='-');
 480         visit(unary.expression);
 481         r_trivial = false;
 482 }
 483
 484 void ExpressionInliner::visit(BinaryExpression &binary)
 485 {
 486         visit(binary.left);
 487         {
 488                 SetFlag clear_target(mutating, false);
 489                 visit(binary.right);
 490         }
 491         r_trivial = false;
 492 }
 493
 494 void ExpressionInliner::visit(Assignment &assign)
 495 {
 496         {
 497                 SetFlag set_target(mutating);
 498                 visit(assign.left);
 499         }
 500         r_oper = 0;
 501         visit(assign.right);
 502
 503         map<Assignment::Target, ExpressionInfo>::iterator i = expressions.find(assign.target);
 504         if(i!=expressions.end())
 505         {
 506                 /* Self-referencing assignments can't be inlined without additional
 507                 work.  Just clear any previous expression. */
 508                 i->second.expression = (assign.self_referencing ? 0 : assign.right.get());
 509                 i->second.assign_scope = current_block;
 510                 i->second.inline_point = 0;
 511                 i->second.available = true;
 512         }
 513
 514         r_trivial = false;
 515 }
 516
 517 void ExpressionInliner::visit(TernaryExpression &ternary)
 518 {
 519         visit(ternary.condition);
 520         visit(ternary.true_expr);
 521         visit(ternary.false_expr);
 522         r_trivial = false;
 523 }
 524
 525 void ExpressionInliner::visit(FunctionCall &call)
 526 {
 527         TraversingVisitor::visit(call);
 528         r_trivial = false;
 529 }
 530
 531 void ExpressionInliner::visit(VariableDeclaration &var)
 532 {
 533         r_oper = 0;
 534         r_trivial = true;
 535         TraversingVisitor::visit(var);
 536
 537         bool constant = var.constant;
 538         if(constant && var.layout)
 539         {
 540                 for(vector<Layout::Qualifier>::const_iterator i=var.layout->qualifiers.begin(); (constant && i!=var.layout->qualifiers.end()); ++i)
 541                         constant = (i->name!="constant_id");
 542         }
 543
 544         /* Only inline global variables if they're constant and have trivial
 545         initializers.  Non-constant variables could change in ways which are hard to
 546         analyze and non-trivial expressions could be expensive to inline.  */
 547         if((current_block->parent || (constant && r_trivial)) && var.interface.empty())
 548         {
 549                 ExpressionInfo &info = expressions[&var];
 550                 /* Assume variables declared in an iteration initialization statement
 551                 will have their values change throughout the iteration. */
 552                 info.expression = (iteration_init ? 0 : var.init_expression.get());
 553                 info.assign_scope = current_block;
 554                 info.trivial = r_trivial;
 555         }
 556 }
 557
 558 void ExpressionInliner::visit(Iteration &iter)
 559 {
 560         SetForScope<Block *> set_block(current_block, &iter.body);
 561         if(iter.init_statement)
 562         {
 563                 SetFlag set_init(iteration_init);
 564                 iter.init_statement->visit(*this);
 565         }
 566
 567         SetForScope<Block *> set_body(iteration_body, &iter.body);
 568         if(iter.condition)
 569                 visit(iter.condition);
 570         iter.body.visit(*this);
 571         if(iter.loop_expression)
 572                 visit(iter.loop_expression);
 573 }
 574
 575
 576 BasicTypeDeclaration::Kind ConstantFolder::get_value_kind(const Variant &value)
 577 {
 578         if(value.check_type<bool>())
 579                 return BasicTypeDeclaration::BOOL;
 580         else if(value.check_type<int>())
 581                 return BasicTypeDeclaration::INT;
 582         else if(value.check_type<float>())
 583                 return BasicTypeDeclaration::FLOAT;
 584         else
 585                 return BasicTypeDeclaration::VOID;
 586 }
 587
 588 template<typename T>
 589 T ConstantFolder::evaluate_logical(char oper, T left, T right)
 590 {
 591         switch(oper)
 592         {
 593         case '&': return left&right;
 594         case '|': return left|right;
 595         case '^': return left^right;
 596         default: return T();
 597         }
 598 }
 599
 600 template<typename T>
 601 bool ConstantFolder::evaluate_relation(const char *oper, T left, T right)
 602 {
 603         switch(oper[0]|oper[1])
 604         {
 605         case '<': return left<right;
 606         case '<'|'=': return left<=right;
 607         case '>': return left>right;
 608         case '>'|'=': return left>=right;
 609         default: return false;
 610         }
 611 }
 612
 613 template<typename T>
 614 T ConstantFolder::evaluate_arithmetic(char oper, T left, T right)
 615 {
 616         switch(oper)
 617         {
 618         case '+': return left+right;
 619         case '-': return left-right;
 620         case '*': return left*right;
 621         case '/': return left/right;
 622         default: return T();
 623         }
 624 }
 625
 626 void ConstantFolder::set_result(const Variant &value, bool literal)
 627 {
 628         r_constant_value = value;
 629         r_constant = true;
 630         r_literal = literal;
 631 }
 632
 633 void ConstantFolder::visit(RefPtr<Expression> &expr)
 634 {
 635         r_constant_value = Variant();
 636         r_constant = false;
 637         r_literal = false;
 638         r_uses_iter_var = false;
 639         expr->visit(*this);
 640         /* Don't replace literals since they'd only be replaced with an identical
 641         literal.  Also skip anything that uses an iteration variable, but pass on
 642         the result so the Iteration visiting function can handle it. */
 643         if(!r_constant || r_literal || r_uses_iter_var)
 644                 return;
 645
 646         BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
 647         if(kind==BasicTypeDeclaration::VOID)
 648         {
 649                 r_constant = false;
 650                 return;
 651         }
 652
 653         RefPtr<Literal> literal = new Literal;
 654         if(kind==BasicTypeDeclaration::BOOL)
 655                 literal->token = (r_constant_value.value<bool>() ? "true" : "false");
 656         else if(kind==BasicTypeDeclaration::INT)
 657                 literal->token = lexical_cast<string>(r_constant_value.value<int>());
 658         else if(kind==BasicTypeDeclaration::FLOAT)
 659                 literal->token = lexical_cast<string>(r_constant_value.value<float>());
 660         literal->value = r_constant_value;
 661         expr = literal;
 662 }
 663
 664 void ConstantFolder::visit(Literal &literal)
 665 {
 666         set_result(literal.value, true);
 667 }
 668
 669 void ConstantFolder::visit(VariableReference &var)
 670 {
 671         /* If an iteration variable is initialized with a constant value, return
 672         that value here for the purpose of evaluating the loop condition for the
 673         first iteration. */
 674         if(var.declaration==iteration_var)
 675         {
 676                 set_result(iter_init_value);
 677                 r_uses_iter_var = true;
 678         }
 679 }
 680
 681 void ConstantFolder::visit(MemberAccess &memacc)
 682 {
 683         TraversingVisitor::visit(memacc);
 684         r_constant = false;
 685 }
 686
 687 void ConstantFolder::visit(Swizzle &swizzle)
 688 {
 689         TraversingVisitor::visit(swizzle);
 690         r_constant = false;
 691 }
 692
 693 void ConstantFolder::visit(UnaryExpression &unary)
 694 {
 695         TraversingVisitor::visit(unary);
 696         bool can_fold = r_constant;
 697         r_constant = false;
 698         if(!can_fold)
 699                 return;
 700
 701         BasicTypeDeclaration::Kind kind = get_value_kind(r_constant_value);
 702
 703         char oper = unary.oper->token[0];
 704         char oper2 = unary.oper->token[1];
 705         if(oper=='!')
 706         {
 707                 if(kind==BasicTypeDeclaration::BOOL)
 708                         set_result(!r_constant_value.value<bool>());
 709         }
 710         else if(oper=='~')
 711         {
 712                 if(kind==BasicTypeDeclaration::INT)
 713                         set_result(~r_constant_value.value<int>());
 714         }
 715         else if(oper=='-' && !oper2)
 716         {
 717                 if(kind==BasicTypeDeclaration::INT)
 718                         set_result(-r_constant_value.value<int>());
 719                 else if(kind==BasicTypeDeclaration::FLOAT)
 720                         set_result(-r_constant_value.value<float>());
 721         }
 722 }
 723
 724 void ConstantFolder::visit(BinaryExpression &binary)
 725 {
 726         visit(binary.left);
 727         bool left_constant = r_constant;
 728         bool left_iter_var = r_uses_iter_var;
 729         Variant left_value = r_constant_value;
 730         visit(binary.right);
 731         if(left_iter_var)
 732                 r_uses_iter_var = true;
 733
 734         bool can_fold = (left_constant && r_constant);
 735         r_constant = false;
 736         if(!can_fold)
 737                 return;
 738
 739         BasicTypeDeclaration::Kind left_kind = get_value_kind(left_value);
 740         BasicTypeDeclaration::Kind right_kind = get_value_kind(r_constant_value);
 741         // Currently only expressions with both sides of equal types are handled.
 742         if(left_kind!=right_kind)
 743                 return;
 744
 745         char oper = binary.oper->token[0];
 746         char oper2 = binary.oper->token[1];
 747         if(oper=='&' || oper=='|' || oper=='^')
 748         {
 749                 if(oper2==oper && left_kind==BasicTypeDeclaration::BOOL)
 750                         set_result(evaluate_logical(oper, left_value.value<bool>(), r_constant_value.value<bool>()));
 751                 else if(!oper2 && left_kind==BasicTypeDeclaration::INT)
 752                         set_result(evaluate_logical(oper, left_value.value<int>(), r_constant_value.value<int>()));
 753         }
 754         else if((oper=='<' || oper=='>') && oper2!=oper)
 755         {
 756                 if(left_kind==BasicTypeDeclaration::INT)
 757                         set_result(evaluate_relation(binary.oper->token, left_value.value<int>(), r_constant_value.value<int>()));
 758                 else if(left_kind==BasicTypeDeclaration::FLOAT)
 759                         set_result(evaluate_relation(binary.oper->token, left_value.value<float>(), r_constant_value.value<float>()));
 760         }
 761         else if((oper=='=' || oper=='!') && oper2=='=')
 762         {
 763                 if(left_kind==BasicTypeDeclaration::INT)
 764                         set_result((left_value.value<int>()==r_constant_value.value<int>()) == (oper=='='));
 765                 if(left_kind==BasicTypeDeclaration::FLOAT)
 766                         set_result((left_value.value<float>()==r_constant_value.value<float>()) == (oper=='='));
 767         }
 768         else if(oper=='+' || oper=='-' || oper=='*' || oper=='/')
 769         {
 770                 if(left_kind==BasicTypeDeclaration::INT)
 771                         set_result(evaluate_arithmetic(oper, left_value.value<int>(), r_constant_value.value<int>()));
 772                 else if(left_kind==BasicTypeDeclaration::FLOAT)
 773                         set_result(evaluate_arithmetic(oper, left_value.value<float>(), r_constant_value.value<float>()));
 774         }
 775         else if(oper=='%' || ((oper=='<' || oper=='>') && oper2==oper))
 776         {
 777                 if(left_kind!=BasicTypeDeclaration::INT)
 778                         return;
 779
 780                 if(oper=='%')
 781                         set_result(left_value.value<int>()%r_constant_value.value<int>());
 782                 else if(oper=='<')
 783                         set_result(left_value.value<int>()<<r_constant_value.value<int>());
 784                 else if(oper=='>')
 785                         set_result(left_value.value<int>()>>r_constant_value.value<int>());
 786         }
 787 }
 788
 789 void ConstantFolder::visit(Assignment &assign)
 790 {
 791         TraversingVisitor::visit(assign);
 792         r_constant = false;
 793 }
 794
 795 void ConstantFolder::visit(TernaryExpression &ternary)
 796 {
 797         TraversingVisitor::visit(ternary);
 798         r_constant = false;
 799 }
 800
 801 void ConstantFolder::visit(FunctionCall &call)
 802 {
 803         TraversingVisitor::visit(call);
 804         r_constant = false;
 805 }
 806
 807 void ConstantFolder::visit(VariableDeclaration &var)
 808 {
 809         if(iteration_init && var.init_expression)
 810         {
 811                 visit(var.init_expression);
 812                 if(r_constant)
 813                 {
 814                         /* Record the value of a constant initialization expression of an
 815                         iteration, so it can be used to evaluate the loop condition. */
 816                         iteration_var = &var;
 817                         iter_init_value = r_constant_value;
 818                 }
 819         }
 820         else
 821                 TraversingVisitor::visit(var);
 822 }
 823
 824 void ConstantFolder::visit(Iteration &iter)
 825 {
 826         SetForScope<Block *> set_block(current_block, &iter.body);
 827
 828         /* The iteration variable is not normally inlined into expressions, so we
 829         process it specially here.  If the initial value causes the loop condition
 830         to evaluate to false, then the expression can be folded. */
 831         iteration_var = 0;
 832         if(iter.init_statement)
 833         {
 834                 SetFlag set_init(iteration_init);
 835                 iter.init_statement->visit(*this);
 836         }
 837
 838         if(iter.condition)
 839         {
 840                 visit(iter.condition);
 841                 if(r_constant && r_constant_value.check_type<bool>() && !r_constant_value.value<bool>())
 842                 {
 843                         RefPtr<Literal> literal = new Literal;
 844                         literal->token = "false";
 845                         literal->value = r_constant_value;
 846                         iter.condition = literal;
 847                 }
 848         }
 849         iteration_var = 0;
 850
 851         iter.body.visit(*this);
 852         if(iter.loop_expression)
 853                 visit(iter.loop_expression);
 854 }
 855
 856
 857 void ConstantConditionEliminator::apply(Stage &stage)
 858 {
 859         stage.content.visit(*this);
 860         NodeRemover().apply(stage, nodes_to_remove);
 861 }
 862
 863 ConstantConditionEliminator::ConstantStatus ConstantConditionEliminator::check_constant_condition(const Expression &expr)
 864 {
 865         if(const Literal *literal = dynamic_cast<const Literal *>(&expr))
 866                 if(literal->value.check_type<bool>())
 867                         return (literal->value.value<bool>() ? CONSTANT_TRUE : CONSTANT_FALSE);
 868         return NOT_CONSTANT;
 869 }
 870
 871 void ConstantConditionEliminator::visit(Block &block)
 872 {
 873         SetForScope<Block *> set_block(current_block, &block);
 874         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 875         {
 876                 insert_point = i;
 877                 (*i)->visit(*this);
 878         }
 879 }
 880
 881 void ConstantConditionEliminator::visit(RefPtr<Expression> &expr)
 882 {
 883         r_ternary_result = 0;
 884         expr->visit(*this);
 885         if(r_ternary_result)
 886                 expr = r_ternary_result;
 887         r_ternary_result = 0;
 888 }
 889
 890 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
 891 {
 892         ConstantStatus result = check_constant_condition(*ternary.condition);
 893         if(result!=NOT_CONSTANT)
 894                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
 895         else
 896                 r_ternary_result = 0;
 897 }
 898
 899 void ConstantConditionEliminator::visit(Conditional &cond)
 900 {
 901         ConstantStatus result = check_constant_condition(*cond.condition);
 902         if(result!=NOT_CONSTANT)
 903         {
 904                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
 905                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
 906                 current_block->body.splice(insert_point, block.body);
 907                 nodes_to_remove.insert(&cond);
 908                 return;
 909         }
 910
 911         TraversingVisitor::visit(cond);
 912 }
 913
 914 void ConstantConditionEliminator::visit(Iteration &iter)
 915 {
 916         if(iter.condition)
 917         {
 918                 ConstantStatus result = check_constant_condition(*iter.condition);
 919                 if(result==CONSTANT_FALSE)
 920                 {
 921                         nodes_to_remove.insert(&iter);
 922                         return;
 923                 }
 924         }
 925
 926         TraversingVisitor::visit(iter);
 927 }
 928
 929
 930 bool UnusedTypeRemover::apply(Stage &stage)
 931 {
 932         stage.content.visit(*this);
 933         NodeRemover().apply(stage, unused_nodes);
 934         return !unused_nodes.empty();
 935 }
 936
 937 void UnusedTypeRemover::visit(Literal &literal)
 938 {
 939         unused_nodes.erase(literal.type);
 940 }
 941
 942 void UnusedTypeRemover::visit(UnaryExpression &unary)
 943 {
 944         unused_nodes.erase(unary.type);
 945         TraversingVisitor::visit(unary);
 946 }
 947
 948 void UnusedTypeRemover::visit(BinaryExpression &binary)
 949 {
 950         unused_nodes.erase(binary.type);
 951         TraversingVisitor::visit(binary);
 952 }
 953
 954 void UnusedTypeRemover::visit(TernaryExpression &ternary)
 955 {
 956         unused_nodes.erase(ternary.type);
 957         TraversingVisitor::visit(ternary);
 958 }
 959
 960 void UnusedTypeRemover::visit(FunctionCall &call)
 961 {
 962         unused_nodes.erase(call.type);
 963         TraversingVisitor::visit(call);
 964 }
 965
 966 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 967 {
 968         if(type.base_type)
 969                 unused_nodes.erase(type.base_type);
 970         unused_nodes.insert(&type);
 971 }
 972
 973 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 974 {
 975         if(type.base_type)
 976                 unused_nodes.erase(type.base_type);
 977         unused_nodes.insert(&type);
 978 }
 979
 980 void UnusedTypeRemover::visit(StructDeclaration &strct)
 981 {
 982         unused_nodes.insert(&strct);
 983         TraversingVisitor::visit(strct);
 984 }
 985
 986 void UnusedTypeRemover::visit(VariableDeclaration &var)
 987 {
 988         unused_nodes.erase(var.type_declaration);
 989 }
 990
 991 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 992 {
 993         unused_nodes.erase(iface.type_declaration);
 994 }
 995
 996 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 997 {
 998         unused_nodes.erase(func.return_type_declaration);
 999         TraversingVisitor::visit(func);
1000 }
1001
1002
1003 UnusedVariableRemover::UnusedVariableRemover():
1004         stage(0),
1005         interface_block(0),
1006         r_assignment(0),
1007         assignment_target(false),
1008         r_side_effects(false)
1009 { }
1010
1011 bool UnusedVariableRemover::apply(Stage &s)
1012 {
1013         stage = &s;
1014         s.content.visit(*this);
1015
1016         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
1017                 if(i->used_by.empty())
1018                         unused_nodes.insert(i->node);
1019
1020         for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
1021                 if(i->second->instance_name.empty())
1022                         unused_nodes.insert(i->second);
1023
1024         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1025         {
1026                 if(i->second.output)
1027                 {
1028                         /* The last visible assignments of output variables are used by the
1029                         next stage or the API. */
1030                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
1031                                 unused_nodes.erase((*j)->node);
1032                 }
1033
1034                 if(!i->second.output && !i->second.referenced)
1035                 {
1036                         // Don't remove variables from inside interface blocks.
1037                         if(!i->second.interface_block)
1038                                 unused_nodes.insert(i->first);
1039                 }
1040                 else if(i->second.interface_block)
1041                         // Interface blocks are kept if even one member is used.
1042                         unused_nodes.erase(i->second.interface_block);
1043         }
1044
1045         NodeRemover().apply(s, unused_nodes);
1046
1047         return !unused_nodes.empty();
1048 }
1049
1050 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
1051 {
1052         VariableInfo &var_info = variables[target.declaration];
1053         var_info.referenced = true;
1054         if(!assignment_target)
1055         {
1056                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1057                         (*i)->used_by.push_back(&node);
1058         }
1059 }
1060
1061 void UnusedVariableRemover::visit(VariableReference &var)
1062 {
1063         referenced(var.declaration, var);
1064 }
1065
1066 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
1067 {
1068         referenced(iface.declaration, iface);
1069 }
1070
1071 void UnusedVariableRemover::visit(UnaryExpression &unary)
1072 {
1073         TraversingVisitor::visit(unary);
1074         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
1075                 r_side_effects = true;
1076 }
1077
1078 void UnusedVariableRemover::visit(BinaryExpression &binary)
1079 {
1080         if(binary.oper->token[0]=='[')
1081         {
1082                 binary.left->visit(*this);
1083                 SetFlag set(assignment_target, false);
1084                 binary.right->visit(*this);
1085         }
1086         else
1087                 TraversingVisitor::visit(binary);
1088 }
1089
1090 void UnusedVariableRemover::visit(Assignment &assign)
1091 {
1092         {
1093                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1094                 assign.left->visit(*this);
1095         }
1096         assign.right->visit(*this);
1097         r_assignment = &assign;
1098         r_side_effects = true;
1099 }
1100
1101 void UnusedVariableRemover::visit(FunctionCall &call)
1102 {
1103         TraversingVisitor::visit(call);
1104         /* Treat function calls as having side effects so expression statements
1105         consisting of nothing but a function call won't be optimized away. */
1106         r_side_effects = true;
1107
1108         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1109         {
1110                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1111                         if(i->second.output)
1112                                 referenced(i->first, call);
1113         }
1114 }
1115
1116 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1117 {
1118         assignments.push_back(AssignmentInfo());
1119         AssignmentInfo &assign_info = assignments.back();
1120         assign_info.node = &node;
1121         assign_info.target = target;
1122
1123         /* An assignment to the target hides any assignments to the same target or
1124         its subfields. */
1125         VariableInfo &var_info = variables[target.declaration];
1126         for(unsigned i=0; i<var_info.assignments.size(); ++i)
1127         {
1128                 const Assignment::Target &t = var_info.assignments[i]->target;
1129
1130                 bool subfield = (t.chain_len>=target.chain_len);
1131                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1132                         subfield = (t.chain[j]==target.chain[j]);
1133
1134                 if(subfield)
1135                         var_info.assignments.erase(var_info.assignments.begin()+i);
1136                 else
1137                         ++i;
1138         }
1139
1140         var_info.assignments.push_back(&assign_info);
1141 }
1142
1143 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1144 {
1145         r_assignment = 0;
1146         r_side_effects = false;
1147         TraversingVisitor::visit(expr);
1148         if(r_assignment && r_assignment->target.declaration)
1149                 record_assignment(r_assignment->target, expr);
1150         if(!r_side_effects)
1151                 unused_nodes.insert(&expr);
1152 }
1153
1154 void UnusedVariableRemover::visit(VariableDeclaration &var)
1155 {
1156         VariableInfo &var_info = variables[&var];
1157         var_info.interface_block = interface_block;
1158
1159         /* Mark variables as output if they're used by the next stage or the
1160         graphics API. */
1161         if(interface_block)
1162                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->block_name.compare(0, 3, "gl_")));
1163         else
1164                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1165
1166         if(var.init_expression)
1167         {
1168                 var_info.initialized = true;
1169                 record_assignment(&var, *var.init_expression);
1170         }
1171         TraversingVisitor::visit(var);
1172 }
1173
1174 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1175 {
1176         if(iface.instance_name.empty())
1177         {
1178                 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1179                 iface.struct_declaration->members.visit(*this);
1180         }
1181         else
1182         {
1183                 VariableInfo &var_info = variables[&iface];
1184                 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.block_name.compare(0, 3, "gl_")));
1185         }
1186 }
1187
1188 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1189 {
1190         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1191         {
1192                 BlockVariableMap::iterator j = variables.find(i->first);
1193                 if(j!=variables.end())
1194                 {
1195                         /* The merged blocks started as copies of each other so any common
1196                         assignments must be in the beginning. */
1197                         unsigned k = 0;
1198                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1199                                 if(i->second.assignments[k]!=j->second.assignments[k])
1200                                         break;
1201
1202                         // Remaining assignments are unique to each block; merge them.
1203                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1204                         j->second.referenced |= i->second.referenced;
1205                 }
1206                 else
1207                         variables.insert(*i);
1208         }
1209 }
1210
1211 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1212 {
1213         if(func.body.body.empty())
1214                 return;
1215
1216         BlockVariableMap saved_vars = variables;
1217         // Assignments from other functions should not be visible.
1218         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1219                 i->second.assignments.resize(i->second.initialized);
1220         TraversingVisitor::visit(func);
1221         swap(variables, saved_vars);
1222         merge_variables(saved_vars);
1223
1224         /* Always treat function parameters as referenced.  Removing unused
1225         parameters is not currently supported. */
1226         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1227         {
1228                 BlockVariableMap::iterator j = variables.find(i->get());
1229                 if(j!=variables.end())
1230                         j->second.referenced = true;
1231         }
1232 }
1233
1234 void UnusedVariableRemover::visit(Conditional &cond)
1235 {
1236         cond.condition->visit(*this);
1237         BlockVariableMap saved_vars = variables;
1238         cond.body.visit(*this);
1239         swap(saved_vars, variables);
1240         cond.else_body.visit(*this);
1241
1242         /* Visible assignments after the conditional is the union of those visible
1243         at the end of the if and else blocks.  If there was no else block, then it's
1244         the union of the if block and the state before it. */
1245         merge_variables(saved_vars);
1246 }
1247
1248 void UnusedVariableRemover::visit(Iteration &iter)
1249 {
1250         BlockVariableMap saved_vars = variables;
1251         TraversingVisitor::visit(iter);
1252
1253         /* Merge assignments from the iteration, without clearing previous state.
1254         Further analysis is needed to determine which parts of the iteration body
1255         are always executed, if any. */
1256         merge_variables(saved_vars);
1257 }
1258
1259
1260 bool UnusedFunctionRemover::apply(Stage &stage)
1261 {
1262         stage.content.visit(*this);
1263         NodeRemover().apply(stage, unused_nodes);
1264         return !unused_nodes.empty();
1265 }
1266
1267 void UnusedFunctionRemover::visit(FunctionCall &call)
1268 {
1269         TraversingVisitor::visit(call);
1270
1271         unused_nodes.erase(call.declaration);
1272         if(call.declaration && call.declaration->definition!=call.declaration)
1273                 used_definitions.insert(call.declaration->definition);
1274 }
1275
1276 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1277 {
1278         TraversingVisitor::visit(func);
1279
1280         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1281                 unused_nodes.insert(&func);
1282 }
1283
1284 } // namespace SL
1285 } // namespace GL
1286 } // namespace Msp