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(RefPtr<Expression> &expr)
 796 {
 797         r_ternary_result = 0;
 798         expr->visit(*this);
 799         if(r_ternary_result)
 800                 expr = r_ternary_result;
 801         r_ternary_result = 0;
 802 }
 803
 804 void ConstantConditionEliminator::visit(TernaryExpression &ternary)
 805 {
 806         ConstantStatus result = check_constant_condition(*ternary.condition);
 807         if(result!=NOT_CONSTANT)
 808                 r_ternary_result = (result==CONSTANT_TRUE ? ternary.true_expr : ternary.false_expr);
 809         else
 810                 r_ternary_result = 0;
 811 }
 812
 813 void ConstantConditionEliminator::visit(Conditional &cond)
 814 {
 815         ConstantStatus result = check_constant_condition(*cond.condition);
 816         if(result!=NOT_CONSTANT)
 817         {
 818                 Block &block = (result==CONSTANT_TRUE ? cond.body : cond.else_body);
 819                 // TODO should check variable names for conflicts.  Potentially reuse InlineContentInjector?
 820                 current_block->body.splice(insert_point, block.body);
 821                 nodes_to_remove.insert(&cond);
 822                 return;
 823         }
 824
 825         TraversingVisitor::visit(cond);
 826 }
 827
 828 void ConstantConditionEliminator::visit(Iteration &iter)
 829 {
 830         if(iter.condition)
 831         {
 832                 ConstantStatus result = check_constant_condition(*iter.condition);
 833                 if(result==CONSTANT_FALSE)
 834                 {
 835                         nodes_to_remove.insert(&iter);
 836                         return;
 837                 }
 838         }
 839
 840         TraversingVisitor::visit(iter);
 841 }
 842
 843
 844 bool UnusedTypeRemover::apply(Stage &stage)
 845 {
 846         stage.content.visit(*this);
 847         NodeRemover().apply(stage, unused_nodes);
 848         return !unused_nodes.empty();
 849 }
 850
 851 void UnusedTypeRemover::visit(Literal &literal)
 852 {
 853         unused_nodes.erase(literal.type);
 854 }
 855
 856 void UnusedTypeRemover::visit(UnaryExpression &unary)
 857 {
 858         unused_nodes.erase(unary.type);
 859         TraversingVisitor::visit(unary);
 860 }
 861
 862 void UnusedTypeRemover::visit(BinaryExpression &binary)
 863 {
 864         unused_nodes.erase(binary.type);
 865         TraversingVisitor::visit(binary);
 866 }
 867
 868 void UnusedTypeRemover::visit(TernaryExpression &ternary)
 869 {
 870         unused_nodes.erase(ternary.type);
 871         TraversingVisitor::visit(ternary);
 872 }
 873
 874 void UnusedTypeRemover::visit(FunctionCall &call)
 875 {
 876         unused_nodes.erase(call.type);
 877         TraversingVisitor::visit(call);
 878 }
 879
 880 void UnusedTypeRemover::visit(BasicTypeDeclaration &type)
 881 {
 882         if(type.base_type)
 883                 unused_nodes.erase(type.base_type);
 884         unused_nodes.insert(&type);
 885 }
 886
 887 void UnusedTypeRemover::visit(ImageTypeDeclaration &type)
 888 {
 889         if(type.base_type)
 890                 unused_nodes.erase(type.base_type);
 891         unused_nodes.insert(&type);
 892 }
 893
 894 void UnusedTypeRemover::visit(StructDeclaration &strct)
 895 {
 896         unused_nodes.insert(&strct);
 897         TraversingVisitor::visit(strct);
 898 }
 899
 900 void UnusedTypeRemover::visit(VariableDeclaration &var)
 901 {
 902         unused_nodes.erase(var.type_declaration);
 903 }
 904
 905 void UnusedTypeRemover::visit(InterfaceBlock &iface)
 906 {
 907         unused_nodes.erase(iface.type_declaration);
 908 }
 909
 910 void UnusedTypeRemover::visit(FunctionDeclaration &func)
 911 {
 912         unused_nodes.erase(func.return_type_declaration);
 913         TraversingVisitor::visit(func);
 914 }
 915
 916
 917 UnusedVariableRemover::UnusedVariableRemover():
 918         stage(0),
 919         interface_block(0),
 920         r_assignment(0),
 921         assignment_target(false),
 922         r_side_effects(false)
 923 { }
 924
 925 bool UnusedVariableRemover::apply(Stage &s)
 926 {
 927         stage = &s;
 928         s.content.visit(*this);
 929
 930         for(list<AssignmentInfo>::const_iterator i=assignments.begin(); i!=assignments.end(); ++i)
 931                 if(i->used_by.empty())
 932                         unused_nodes.insert(i->node);
 933
 934         for(map<string, InterfaceBlock *>::const_iterator i=s.interface_blocks.begin(); i!=s.interface_blocks.end(); ++i)
 935                 if(i->second->instance_name.empty())
 936                         unused_nodes.insert(i->second);
 937
 938         for(BlockVariableMap::const_iterator i=variables.begin(); i!=variables.end(); ++i)
 939         {
 940                 if(i->second.output)
 941                 {
 942                         /* The last visible assignments of output variables are used by the
 943                         next stage or the API. */
 944                         for(vector<AssignmentInfo *>::const_iterator j=i->second.assignments.begin(); j!=i->second.assignments.end(); ++j)
 945                                 unused_nodes.erase((*j)->node);
 946                 }
 947
 948                 if(!i->second.output && !i->second.referenced)
 949                 {
 950                         // Don't remove variables from inside interface blocks.
 951                         if(!i->second.interface_block)
 952                                 unused_nodes.insert(i->first);
 953                 }
 954                 else if(i->second.interface_block)
 955                         // Interface blocks are kept if even one member is used.
 956                         unused_nodes.erase(i->second.interface_block);
 957         }
 958
 959         NodeRemover().apply(s, unused_nodes);
 960
 961         return !unused_nodes.empty();
 962 }
 963
 964 void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &node)
 965 {
 966         VariableInfo &var_info = variables[target.declaration];
 967         var_info.referenced = true;
 968         if(!assignment_target)
 969         {
 970                 for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 971                         (*i)->used_by.push_back(&node);
 972         }
 973 }
 974
 975 void UnusedVariableRemover::visit(VariableReference &var)
 976 {
 977         referenced(var.declaration, var);
 978 }
 979
 980 void UnusedVariableRemover::visit(InterfaceBlockReference &iface)
 981 {
 982         referenced(iface.declaration, iface);
 983 }
 984
 985 void UnusedVariableRemover::visit(UnaryExpression &unary)
 986 {
 987         TraversingVisitor::visit(unary);
 988         if(unary.oper->token[1]=='+' || unary.oper->token[1]=='-')
 989                 r_side_effects = true;
 990 }
 991
 992 void UnusedVariableRemover::visit(BinaryExpression &binary)
 993 {
 994         if(binary.oper->token[0]=='[')
 995         {
 996                 binary.left->visit(*this);
 997                 SetFlag set(assignment_target, false);
 998                 binary.right->visit(*this);
 999         }
1000         else
1001                 TraversingVisitor::visit(binary);
1002 }
1003
1004 void UnusedVariableRemover::visit(Assignment &assign)
1005 {
1006         {
1007                 SetFlag set(assignment_target, (assign.oper->token[0]=='='));
1008                 assign.left->visit(*this);
1009         }
1010         assign.right->visit(*this);
1011         r_assignment = &assign;
1012         r_side_effects = true;
1013 }
1014
1015 void UnusedVariableRemover::visit(FunctionCall &call)
1016 {
1017         TraversingVisitor::visit(call);
1018         /* Treat function calls as having side effects so expression statements
1019         consisting of nothing but a function call won't be optimized away. */
1020         r_side_effects = true;
1021
1022         if(stage->type==Stage::GEOMETRY && call.name=="EmitVertex")
1023         {
1024                 for(map<Statement *, VariableInfo>::const_iterator i=variables.begin(); i!=variables.end(); ++i)
1025                         if(i->second.output)
1026                                 referenced(i->first, call);
1027         }
1028 }
1029
1030 void UnusedVariableRemover::record_assignment(const Assignment::Target &target, Node &node)
1031 {
1032         assignments.push_back(AssignmentInfo());
1033         AssignmentInfo &assign_info = assignments.back();
1034         assign_info.node = &node;
1035         assign_info.target = target;
1036
1037         /* An assignment to the target hides any assignments to the same target or
1038         its subfields. */
1039         VariableInfo &var_info = variables[target.declaration];
1040         for(unsigned i=0; i<var_info.assignments.size(); ++i)
1041         {
1042                 const Assignment::Target &t = var_info.assignments[i]->target;
1043
1044                 bool subfield = (t.chain_len>=target.chain_len);
1045                 for(unsigned j=0; (subfield && j<target.chain_len); ++j)
1046                         subfield = (t.chain[j]==target.chain[j]);
1047
1048                 if(subfield)
1049                         var_info.assignments.erase(var_info.assignments.begin()+i);
1050                 else
1051                         ++i;
1052         }
1053
1054         var_info.assignments.push_back(&assign_info);
1055 }
1056
1057 void UnusedVariableRemover::visit(ExpressionStatement &expr)
1058 {
1059         r_assignment = 0;
1060         r_side_effects = false;
1061         TraversingVisitor::visit(expr);
1062         if(r_assignment && r_assignment->target.declaration)
1063                 record_assignment(r_assignment->target, expr);
1064         if(!r_side_effects)
1065                 unused_nodes.insert(&expr);
1066 }
1067
1068 void UnusedVariableRemover::visit(VariableDeclaration &var)
1069 {
1070         VariableInfo &var_info = variables[&var];
1071         var_info.interface_block = interface_block;
1072
1073         /* Mark variables as output if they're used by the next stage or the
1074         graphics API. */
1075         if(interface_block)
1076                 var_info.output = (interface_block->interface=="out" && (interface_block->linked_block || !interface_block->name.compare(0, 3, "gl_")));
1077         else
1078                 var_info.output = (var.interface=="out" && (stage->type==Stage::FRAGMENT || var.linked_declaration || !var.name.compare(0, 3, "gl_")));
1079
1080         if(var.init_expression)
1081         {
1082                 var_info.initialized = true;
1083                 record_assignment(&var, *var.init_expression);
1084         }
1085         TraversingVisitor::visit(var);
1086 }
1087
1088 void UnusedVariableRemover::visit(InterfaceBlock &iface)
1089 {
1090         if(iface.instance_name.empty())
1091         {
1092                 SetForScope<InterfaceBlock *> set_block(interface_block, &iface);
1093                 iface.struct_declaration->members.visit(*this);
1094         }
1095         else
1096         {
1097                 VariableInfo &var_info = variables[&iface];
1098                 var_info.output = (iface.interface=="out" && (iface.linked_block || !iface.name.compare(0, 3, "gl_")));
1099         }
1100 }
1101
1102 void UnusedVariableRemover::merge_variables(const BlockVariableMap &other_vars)
1103 {
1104         for(BlockVariableMap::const_iterator i=other_vars.begin(); i!=other_vars.end(); ++i)
1105         {
1106                 BlockVariableMap::iterator j = variables.find(i->first);
1107                 if(j!=variables.end())
1108                 {
1109                         /* The merged blocks started as copies of each other so any common
1110                         assignments must be in the beginning. */
1111                         unsigned k = 0;
1112                         for(; (k<i->second.assignments.size() && k<j->second.assignments.size()); ++k)
1113                                 if(i->second.assignments[k]!=j->second.assignments[k])
1114                                         break;
1115
1116                         // Remaining assignments are unique to each block; merge them.
1117                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin()+k, i->second.assignments.end());
1118                         j->second.referenced |= i->second.referenced;
1119                 }
1120                 else
1121                         variables.insert(*i);
1122         }
1123 }
1124
1125 void UnusedVariableRemover::visit(FunctionDeclaration &func)
1126 {
1127         if(func.body.body.empty())
1128                 return;
1129
1130         BlockVariableMap saved_vars = variables;
1131         // Assignments from other functions should not be visible.
1132         for(BlockVariableMap::iterator i=variables.begin(); i!=variables.end(); ++i)
1133                 i->second.assignments.resize(i->second.initialized);
1134         TraversingVisitor::visit(func);
1135         swap(variables, saved_vars);
1136         merge_variables(saved_vars);
1137
1138         /* Always treat function parameters as referenced.  Removing unused
1139         parameters is not currently supported. */
1140         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1141         {
1142                 BlockVariableMap::iterator j = variables.find(i->get());
1143                 if(j!=variables.end())
1144                         j->second.referenced = true;
1145         }
1146 }
1147
1148 void UnusedVariableRemover::visit(Conditional &cond)
1149 {
1150         cond.condition->visit(*this);
1151         BlockVariableMap saved_vars = variables;
1152         cond.body.visit(*this);
1153         swap(saved_vars, variables);
1154         cond.else_body.visit(*this);
1155
1156         /* Visible assignments after the conditional is the union of those visible
1157         at the end of the if and else blocks.  If there was no else block, then it's
1158         the union of the if block and the state before it. */
1159         merge_variables(saved_vars);
1160 }
1161
1162 void UnusedVariableRemover::visit(Iteration &iter)
1163 {
1164         BlockVariableMap saved_vars = variables;
1165         TraversingVisitor::visit(iter);
1166
1167         /* Merge assignments from the iteration, without clearing previous state.
1168         Further analysis is needed to determine which parts of the iteration body
1169         are always executed, if any. */
1170         merge_variables(saved_vars);
1171 }
1172
1173
1174 bool UnusedFunctionRemover::apply(Stage &stage)
1175 {
1176         stage.content.visit(*this);
1177         NodeRemover().apply(stage, unused_nodes);
1178         return !unused_nodes.empty();
1179 }
1180
1181 void UnusedFunctionRemover::visit(FunctionCall &call)
1182 {
1183         TraversingVisitor::visit(call);
1184
1185         unused_nodes.erase(call.declaration);
1186         if(call.declaration && call.declaration->definition!=call.declaration)
1187                 used_definitions.insert(call.declaration->definition);
1188 }
1189
1190 void UnusedFunctionRemover::visit(FunctionDeclaration &func)
1191 {
1192         TraversingVisitor::visit(func);
1193
1194         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1195                 unused_nodes.insert(&func);
1196 }
1197
1198 } // namespace SL
1199 } // namespace GL
1200 } // namespace Msp