source/glsl/optimize.cpp

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