source/glsl/optimize.cpp

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