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