source/programcompiler.cpp

   1 #include <msp/core/raii.h>
   2 #include <msp/strings/format.h>
   3 #include <msp/strings/utils.h>
   4 #include "error.h"
   5 #include "program.h"
   6 #include "programcompiler.h"
   7 #include "resources.h"
   8 #include "shader.h"
   9
  10 using namespace std;
  11
  12 namespace {
  13
  14 const char builtins_src[] =
  15         "////// vertex\n"
  16         "out gl_PerVertex {\n"
  17         "  vec4 gl_Position;\n"
  18         "  float gl_ClipDistance[];\n"
  19         "};"
  20         "////// geometry\n"
  21         "in gl_PerVertex {\n"
  22         "  vec4 gl_Position;\n"
  23         "  float gl_ClipDistance[];\n"
  24         "} gl_in[];\n"
  25         "out gl_PerVertex {\n"
  26         "  vec4 gl_Position;\n"
  27         "  float gl_ClipDistance[];\n"
  28         "};\n";
  29
  30 }
  31
  32 namespace Msp {
  33 namespace GL {
  34
  35 using namespace ProgramSyntax;
  36
  37 ProgramCompiler::ProgramCompiler():
  38         resources(0),
  39         module(0)
  40 { }
  41
  42 void ProgramCompiler::compile(const string &source)
  43 {
  44         resources = 0;
  45         module = &parser.parse(source);
  46         process();
  47 }
  48
  49 void ProgramCompiler::compile(IO::Base &io, Resources *res)
  50 {
  51         resources = res;
  52         module = &parser.parse(io);
  53         process();
  54 }
  55
  56 void ProgramCompiler::add_shaders(Program &program)
  57 {
  58         if(!module)
  59                 throw invalid_operation("ProgramCompiler::add_shaders");
  60
  61         string head = "#version 150\n";
  62         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
  63         {
  64                 if(i->type==VERTEX)
  65                         program.attach_shader_owned(new VertexShader(head+apply<Formatter>(*i)));
  66                 else if(i->type==GEOMETRY)
  67                         program.attach_shader_owned(new GeometryShader(head+apply<Formatter>(*i)));
  68                 else if(i->type==FRAGMENT)
  69                         program.attach_shader_owned(new FragmentShader(head+apply<Formatter>(*i)));
  70         }
  71
  72         program.bind_attribute(VERTEX4, "vertex");
  73         program.bind_attribute(NORMAL3, "normal");
  74         program.bind_attribute(COLOR4_FLOAT, "color");
  75         program.bind_attribute(TEXCOORD4, "texcoord");
  76 }
  77
  78 Module *ProgramCompiler::create_builtins_module()
  79 {
  80         ProgramParser parser;
  81         Module *module = new Module(parser.parse(builtins_src));
  82         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
  83         {
  84                 VariableResolver resolver;
  85                 i->content.visit(resolver);
  86                 for(map<string, VariableDeclaration *>::iterator j=i->content.variables.begin(); j!=i->content.variables.end(); ++j)
  87                         j->second->linked_declaration = j->second;
  88         }
  89         return module;
  90 }
  91
  92 Module &ProgramCompiler::get_builtins_module()
  93 {
  94         static RefPtr<Module> builtins_module = create_builtins_module();
  95         return *builtins_module;
  96 }
  97
  98 Stage *ProgramCompiler::get_builtins(StageType type)
  99 {
 100         Module &module = get_builtins_module();
 101         for(list<Stage>::iterator i=module.stages.begin(); i!=module.stages.end(); ++i)
 102                 if(i->type==type)
 103                         return &*i;
 104         return 0;
 105 }
 106
 107 void ProgramCompiler::process()
 108 {
 109         list<Import *> imports = apply<NodeGatherer<Import> >(module->shared);
 110         for(list<Import *>::iterator i=imports.end(); i!=imports.begin(); )
 111                 import((*--i)->module);
 112         apply<NodeRemover>(module->shared, set<Node *>(imports.begin(), imports.end()));
 113
 114         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
 115                 generate(*i);
 116         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); )
 117         {
 118                 if(optimize(*i))
 119                         i = module->stages.begin();
 120                 else
 121                         ++i;
 122         }
 123 }
 124
 125 void ProgramCompiler::import(const string &name)
 126 {
 127         if(!resources)
 128                 throw runtime_error("no resources");
 129         RefPtr<IO::Seekable> io = resources->open_raw(name+".glsl");
 130         if(!io)
 131                 throw runtime_error(format("module %s not found", name));
 132         ProgramParser import_parser;
 133         Module &imported_module = import_parser.parse(*io);
 134
 135         inject_block(module->shared.content, imported_module.shared.content);
 136         apply<DeclarationCombiner>(module->shared);
 137         for(list<Stage>::iterator i=imported_module.stages.begin(); i!=imported_module.stages.end(); ++i)
 138         {
 139                 list<Stage>::iterator j;
 140                 for(j=module->stages.begin(); (j!=module->stages.end() && j->type<i->type); ++j) ;
 141                 if(j==module->stages.end() || j->type>i->type)
 142                 {
 143                         j = module->stages.insert(j, *i);
 144                         list<Stage>::iterator k = j;
 145                         if(++k!=module->stages.end())
 146                                 k->previous = &*j;
 147                         if(j!=module->stages.begin())
 148                                 j->previous = &*--(k=j);
 149                 }
 150                 else
 151                 {
 152                         inject_block(j->content, i->content);
 153                         apply<DeclarationCombiner>(*j);
 154                 }
 155         }
 156 }
 157
 158 void ProgramCompiler::generate(Stage &stage)
 159 {
 160         inject_block(stage.content, module->shared.content);
 161
 162         apply<VariableResolver>(stage);
 163         apply<InterfaceGenerator>(stage);
 164         apply<VariableResolver>(stage);
 165         apply<VariableRenamer>(stage);
 166 }
 167
 168 bool ProgramCompiler::optimize(Stage &stage)
 169 {
 170         apply<ConstantConditionEliminator>(stage);
 171         apply<VariableResolver>(stage);
 172
 173         set<Node *> unused = apply<UnusedVariableLocator>(stage);
 174         apply<NodeRemover>(stage, unused);
 175
 176         return !unused.empty();
 177 }
 178
 179 void ProgramCompiler::inject_block(Block &target, const Block &source)
 180 {
 181         list<NodePtr<Node> >::iterator insert_point = target.body.begin();
 182         for(list<NodePtr<Node> >::const_iterator i=source.body.begin(); i!=source.body.end(); ++i)
 183                 target.body.insert(insert_point, (*i)->clone());
 184 }
 185
 186 template<typename T>
 187 typename T::ResultType ProgramCompiler::apply(Stage &stage)
 188 {
 189         T visitor;
 190         visitor.apply(stage);
 191         return visitor.get_result();
 192 }
 193
 194 template<typename T, typename A>
 195 typename T::ResultType ProgramCompiler::apply(Stage &stage, const A &arg)
 196 {
 197         T visitor(arg);
 198         visitor.apply(stage);
 199         return visitor.get_result();
 200 }
 201
 202
 203 ProgramCompiler::Visitor::Visitor():
 204         stage(0)
 205 { }
 206
 207 void ProgramCompiler::Visitor::apply(Stage &s)
 208 {
 209         SetForScope<Stage *> set(stage, &s);
 210         stage->content.visit(*this);
 211 }
 212
 213
 214 ProgramCompiler::Formatter::Formatter():
 215         indent(0),
 216         parameter_list(false),
 217         else_if(0)
 218 { }
 219
 220 void ProgramCompiler::Formatter::visit(Literal &literal)
 221 {
 222         formatted += literal.token;
 223 }
 224
 225 void ProgramCompiler::Formatter::visit(ParenthesizedExpression &parexpr)
 226 {
 227         formatted += '(';
 228         parexpr.expression->visit(*this);
 229         formatted += ')';
 230 }
 231
 232 void ProgramCompiler::Formatter::visit(VariableReference &var)
 233 {
 234         formatted += var.name;
 235 }
 236
 237 void ProgramCompiler::Formatter::visit(MemberAccess &memacc)
 238 {
 239         memacc.left->visit(*this);
 240         formatted += format(".%s", memacc.member);
 241 }
 242
 243 void ProgramCompiler::Formatter::visit(UnaryExpression &unary)
 244 {
 245         if(unary.prefix)
 246                 formatted += unary.oper;
 247         unary.expression->visit(*this);
 248         if(!unary.prefix)
 249                 formatted += unary.oper;
 250 }
 251
 252 void ProgramCompiler::Formatter::visit(BinaryExpression &binary)
 253 {
 254         binary.left->visit(*this);
 255         formatted += binary.oper;
 256         binary.right->visit(*this);
 257         formatted += binary.after;
 258 }
 259
 260 void ProgramCompiler::Formatter::visit(Assignment &assign)
 261 {
 262         assign.left->visit(*this);
 263         formatted += format(" %s ", assign.oper);
 264         assign.right->visit(*this);
 265 }
 266
 267 void ProgramCompiler::Formatter::visit(FunctionCall &call)
 268 {
 269         formatted += format("%s(", call.name);
 270         for(vector<NodePtr<Expression> >::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 271         {
 272                 if(i!=call.arguments.begin())
 273                         formatted += ", ";
 274                 (*i)->visit(*this);
 275         }
 276         formatted += ')';
 277 }
 278
 279 void ProgramCompiler::Formatter::visit(ExpressionStatement &expr)
 280 {
 281         expr.expression->visit(*this);
 282         formatted += ';';
 283 }
 284
 285 void ProgramCompiler::Formatter::visit(Block &block)
 286 {
 287         if(else_if)
 288                 --else_if;
 289
 290         unsigned brace_indent = indent;
 291         bool use_braces = (block.use_braces || (indent && block.body.size()!=1));
 292         if(use_braces)
 293                 formatted += format("%s{\n", string(brace_indent*2, ' '));
 294
 295         SetForScope<unsigned> set(indent, indent+!formatted.empty());
 296         string spaces(indent*2, ' ');
 297         for(list<NodePtr<Node> >::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 298         {
 299                 if(i!=block.body.begin())
 300                         formatted += '\n';
 301                 formatted += spaces;
 302                 (*i)->visit(*this);
 303                 else_if = 0;
 304         }
 305
 306         if(use_braces)
 307                 formatted += format("\n%s}", string(brace_indent*2, ' '));
 308 }
 309
 310 void ProgramCompiler::Formatter::visit(Import &import)
 311 {
 312         formatted += format("import %s;", import.module);
 313 }
 314
 315 void ProgramCompiler::Formatter::visit(Layout &layout)
 316 {
 317         formatted += "layout(";
 318         for(vector<Layout::Qualifier>::const_iterator i=layout.qualifiers.begin(); i!=layout.qualifiers.end(); ++i)
 319         {
 320                 if(i!=layout.qualifiers.begin())
 321                         formatted += ", ";
 322                 formatted += i->identifier;
 323                 if(!i->value.empty())
 324                         formatted += format("=%s", i->value);
 325         }
 326         formatted += format(") %s;", layout.interface);
 327 }
 328
 329 void ProgramCompiler::Formatter::visit(StructDeclaration &strct)
 330 {
 331         formatted += format("struct %s\n", strct.name);
 332         strct.members.visit(*this);
 333         formatted += ';';
 334 }
 335
 336 void ProgramCompiler::Formatter::visit(VariableDeclaration &var)
 337 {
 338         if(var.constant)
 339                 formatted += "const ";
 340         if(!var.sampling.empty())
 341                 formatted += format("%s ", var.sampling);
 342         if(!var.interface.empty() && var.interface!=block_interface)
 343                 formatted += format("%s ", var.interface);
 344         formatted += format("%s %s", var.type, var.name);
 345         if(var.array)
 346         {
 347                 formatted += '[';
 348                 if(var.array_size)
 349                         var.array_size->visit(*this);
 350                 formatted += ']';
 351         }
 352         if(var.init_expression)
 353         {
 354                 formatted += " = ";
 355                 var.init_expression->visit(*this);
 356         }
 357         if(!parameter_list)
 358                 formatted += ';';
 359 }
 360
 361 void ProgramCompiler::Formatter::visit(InterfaceBlock &iface)
 362 {
 363         SetForScope<string> set(block_interface, iface.interface);
 364         formatted += format("%s %s\n", iface.interface, iface.name);
 365         iface.members.visit(*this);
 366         formatted += ';';
 367 }
 368
 369 void ProgramCompiler::Formatter::visit(FunctionDeclaration &func)
 370 {
 371         formatted += format("%s %s(", func.return_type, func.name);
 372         for(vector<NodePtr<VariableDeclaration> >::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 373         {
 374                 if(i!=func.parameters.begin())
 375                         formatted += ", ";
 376                 SetFlag set(parameter_list);
 377                 (*i)->visit(*this);
 378         }
 379         formatted += ')';
 380         if(func.definition==&func)
 381         {
 382                 formatted += '\n';
 383                 func.body.visit(*this);
 384         }
 385         else
 386                 formatted += ';';
 387 }
 388
 389 void ProgramCompiler::Formatter::visit(Conditional &cond)
 390 {
 391         if(else_if)
 392                 formatted.replace(formatted.rfind('\n'), string::npos, 1, ' ');
 393
 394         indent -= else_if;
 395
 396         formatted += "if(";
 397         cond.condition->visit(*this);
 398         formatted += ")\n";
 399
 400         cond.body.visit(*this);
 401         if(!cond.else_body.body.empty())
 402         {
 403                 formatted += format("\n%selse\n", string(indent*2, ' '));
 404                 SetForScope<unsigned> set(else_if, 2);
 405                 cond.else_body.visit(*this);
 406         }
 407 }
 408
 409 void ProgramCompiler::Formatter::visit(Iteration &iter)
 410 {
 411         formatted += "for(";
 412         iter.init_statement->visit(*this);
 413         formatted += ' ';
 414         iter.condition->visit(*this);
 415         formatted += "; ";
 416         iter.loop_expression->visit(*this);
 417         formatted += ")\n";
 418         iter.body.visit(*this);
 419 }
 420
 421 void ProgramCompiler::Formatter::visit(Return &ret)
 422 {
 423         formatted += "return ";
 424         ret.expression->visit(*this);
 425         formatted += ';';
 426 }
 427
 428
 429 ProgramCompiler::DeclarationCombiner::DeclarationCombiner():
 430         toplevel(true),
 431         remove_node(false)
 432 { }
 433
 434 void ProgramCompiler::DeclarationCombiner::visit(Block &block)
 435 {
 436         if(!toplevel)
 437                 return;
 438
 439         SetForScope<bool> set(toplevel, false);
 440         for(list<NodePtr<Node> >::iterator i=block.body.begin(); i!=block.body.end(); )
 441         {
 442                 remove_node = false;
 443                 (*i)->visit(*this);
 444                 if(remove_node)
 445                         block.body.erase(i++);
 446                 else
 447                         ++i;
 448         }
 449 }
 450
 451 void ProgramCompiler::DeclarationCombiner::visit(FunctionDeclaration &func)
 452 {
 453         vector<FunctionDeclaration *> &decls = functions[func.name];
 454         if(func.definition)
 455         {
 456                 for(vector<FunctionDeclaration *>::iterator i=decls.begin(); i!=decls.end(); ++i)
 457                 {
 458                         (*i)->definition = func.definition;
 459                         (*i)->body.body.clear();
 460                 }
 461         }
 462         decls.push_back(&func);
 463 }
 464
 465 void ProgramCompiler::DeclarationCombiner::visit(VariableDeclaration &var)
 466 {
 467         VariableDeclaration *&ptr = variables[var.name];
 468         if(ptr)
 469         {
 470                 if(var.init_expression)
 471                         ptr->init_expression = var.init_expression;
 472                 remove_node = true;
 473         }
 474         else
 475                 ptr = &var;
 476 }
 477
 478
 479 ProgramCompiler::VariableResolver::VariableResolver():
 480         anonymous(false),
 481         record_target(false),
 482         assignment_target(0),
 483         self_referencing(false)
 484 { }
 485
 486 void ProgramCompiler::VariableResolver::apply(Stage &s)
 487 {
 488         SetForScope<Stage *> set(stage, &s);
 489         Stage *builtins = get_builtins(stage->type);
 490         if(builtins)
 491                 blocks.push_back(&builtins->content);
 492         stage->content.visit(*this);
 493         if(builtins)
 494                 blocks.pop_back();
 495 }
 496
 497 void ProgramCompiler::VariableResolver::visit(Block &block)
 498 {
 499         blocks.push_back(&block);
 500         block.variables.clear();
 501         TraversingVisitor::visit(block);
 502         blocks.pop_back();
 503 }
 504
 505 void ProgramCompiler::VariableResolver::visit(VariableReference &var)
 506 {
 507         var.declaration = 0;
 508         type = 0;
 509         for(vector<Block *>::iterator i=blocks.end(); i!=blocks.begin(); )
 510         {
 511                 --i;
 512                 map<string, VariableDeclaration *>::iterator j = (*i)->variables.find(var.name);
 513                 if(j!=(*i)->variables.end())
 514                 {
 515                         var.declaration = j->second;
 516                         type = j->second->type_declaration;
 517                         break;
 518                 }
 519         }
 520
 521         if(record_target)
 522         {
 523                 if(assignment_target)
 524                 {
 525                         record_target = false;
 526                         assignment_target = 0;
 527                 }
 528                 else
 529                         assignment_target = var.declaration;
 530         }
 531         else if(var.declaration && var.declaration==assignment_target)
 532                 self_referencing = true;
 533 }
 534
 535 void ProgramCompiler::VariableResolver::visit(MemberAccess &memacc)
 536 {
 537         type = 0;
 538         TraversingVisitor::visit(memacc);
 539         memacc.declaration = 0;
 540         if(type)
 541         {
 542                 map<string, VariableDeclaration *>::iterator i = type->members.variables.find(memacc.member);
 543                 if(i!=type->members.variables.end())
 544                 {
 545                         memacc.declaration = i->second;
 546                         type = i->second->type_declaration;
 547                 }
 548                 else
 549                         type = 0;
 550         }
 551 }
 552
 553 void ProgramCompiler::VariableResolver::visit(BinaryExpression &binary)
 554 {
 555         if(binary.oper=="[")
 556         {
 557                 {
 558                         SetForScope<bool> set(record_target, false);
 559                         binary.right->visit(*this);
 560                 }
 561                 type = 0;
 562                 binary.left->visit(*this);
 563         }
 564         else
 565         {
 566                 TraversingVisitor::visit(binary);
 567                 type = 0;
 568         }
 569 }
 570
 571 void ProgramCompiler::VariableResolver::visit(Assignment &assign)
 572 {
 573         {
 574                 SetFlag set(record_target);
 575                 assignment_target = 0;
 576                 assign.left->visit(*this);
 577         }
 578
 579         self_referencing = false;
 580         assign.right->visit(*this);
 581
 582         assign.self_referencing = (self_referencing || assign.oper!="=");
 583         assign.target_declaration = assignment_target;
 584 }
 585
 586 void ProgramCompiler::VariableResolver::visit(StructDeclaration &strct)
 587 {
 588         TraversingVisitor::visit(strct);
 589         blocks.back()->types[strct.name] = &strct;
 590 }
 591
 592 void ProgramCompiler::VariableResolver::visit(VariableDeclaration &var)
 593 {
 594         for(vector<Block *>::iterator i=blocks.end(); i!=blocks.begin(); )
 595         {
 596                 --i;
 597                 map<string, StructDeclaration *>::iterator j = (*i)->types.find(var.type);
 598                 if(j!=(*i)->types.end())
 599                         var.type_declaration = j->second;
 600         }
 601
 602         if(!block_interface.empty() && var.interface.empty())
 603                 var.interface = block_interface;
 604
 605         TraversingVisitor::visit(var);
 606         blocks.back()->variables[var.name] = &var;
 607         if(anonymous && blocks.size()>1)
 608                 blocks[blocks.size()-2]->variables[var.name] = &var;
 609 }
 610
 611 void ProgramCompiler::VariableResolver::visit(InterfaceBlock &iface)
 612 {
 613         SetFlag set(anonymous);
 614         SetForScope<string> set2(block_interface, iface.interface);
 615         TraversingVisitor::visit(iface);
 616 }
 617
 618
 619 ProgramCompiler::InterfaceGenerator::InterfaceGenerator():
 620         scope_level(0),
 621         remove_node(false)
 622 { }
 623
 624 string ProgramCompiler::InterfaceGenerator::get_out_prefix(StageType type)
 625 {
 626         if(type==VERTEX)
 627                 return "_vs_out_";
 628         else if(type==GEOMETRY)
 629                 return "_gs_out_";
 630         else
 631                 return string();
 632 }
 633
 634 void ProgramCompiler::InterfaceGenerator::apply(Stage &s)
 635 {
 636         SetForScope<Stage *> set(stage, &s);
 637         if(stage->previous)
 638                 in_prefix = get_out_prefix(stage->previous->type);
 639         out_prefix = get_out_prefix(stage->type);
 640         stage->content.visit(*this);
 641 }
 642
 643 void ProgramCompiler::InterfaceGenerator::visit(Block &block)
 644 {
 645         SetForScope<unsigned> set(scope_level, scope_level+1);
 646         for(list<NodePtr<Node> >::iterator i=block.body.begin(); i!=block.body.end(); )
 647         {
 648                 (*i)->visit(*this);
 649
 650                 if(scope_level==1)
 651                 {
 652                         for(map<string, VariableDeclaration *>::iterator j=iface_declarations.begin(); j!=iface_declarations.end(); ++j)
 653                         {
 654                                 list<NodePtr<Node> >::iterator k = block.body.insert(i, j->second);
 655                                 (*k)->visit(*this);
 656                         }
 657                         iface_declarations.clear();
 658                 }
 659
 660                 for(list<Node *>::iterator j=insert_nodes.begin(); j!=insert_nodes.end(); ++j)
 661                         block.body.insert(i, *j);
 662                 insert_nodes.clear();
 663
 664                 if(remove_node)
 665                         block.body.erase(i++);
 666                 else
 667                         ++i;
 668                 remove_node = false;
 669         }
 670 }
 671
 672 string ProgramCompiler::InterfaceGenerator::change_prefix(const string &name, const string &prefix) const
 673 {
 674         unsigned offset = (name.compare(0, in_prefix.size(), in_prefix) ? 0 : in_prefix.size());
 675         return prefix+name.substr(offset);
 676 }
 677
 678 bool ProgramCompiler::InterfaceGenerator::generate_interface(VariableDeclaration &var, const string &iface, const string &name)
 679 {
 680         const map<string, VariableDeclaration *> &stage_vars = (iface=="in" ? stage->in_variables : stage->out_variables);
 681         if(stage_vars.count(name) || iface_declarations.count(name))
 682                 return false;
 683
 684         VariableDeclaration* iface_var = new VariableDeclaration;
 685         iface_var->sampling = var.sampling;
 686         iface_var->interface = iface;
 687         iface_var->type = var.type;
 688         iface_var->type_declaration = var.type_declaration;
 689         iface_var->name = name;
 690         if(stage->type==GEOMETRY)
 691                 iface_var->array = ((var.array && var.interface!="in") || iface=="in");
 692         else
 693                 iface_var->array = var.array;
 694         if(iface_var->array)
 695                 iface_var->array_size = var.array_size;
 696         if(iface=="in")
 697                 iface_var->linked_declaration = &var;
 698         iface_declarations[name] = iface_var;
 699
 700         return true;
 701 }
 702
 703 void ProgramCompiler::InterfaceGenerator::insert_assignment(const string &left, ProgramSyntax::Expression *right)
 704 {
 705         Assignment *assign = new Assignment;
 706         VariableReference *ref = new VariableReference;
 707         ref->name = left;
 708         assign->left = ref;
 709         assign->oper = "=";
 710         assign->right = right;
 711
 712         ExpressionStatement *stmt = new ExpressionStatement;
 713         stmt->expression = assign;
 714         insert_nodes.push_back(stmt);
 715 }
 716
 717 void ProgramCompiler::InterfaceGenerator::visit(VariableReference &var)
 718 {
 719         if(var.declaration || !stage->previous)
 720                 return;
 721         if(iface_declarations.count(var.name))
 722                 return;
 723
 724         const map<string, VariableDeclaration *> &prev_out = stage->previous->out_variables;
 725         map<string, VariableDeclaration *>::const_iterator i = prev_out.find(var.name);
 726         if(i==prev_out.end())
 727                 i = prev_out.find(in_prefix+var.name);
 728         if(i!=prev_out.end())
 729                 generate_interface(*i->second, "in", var.name);
 730 }
 731
 732 void ProgramCompiler::InterfaceGenerator::visit(VariableDeclaration &var)
 733 {
 734         if(var.interface=="out")
 735         {
 736                 if(scope_level==1)
 737                         stage->out_variables[var.name] = &var;
 738                 else if(generate_interface(var, "out", change_prefix(var.name, string())))
 739                 {
 740                         remove_node = true;
 741                         if(var.init_expression)
 742                                 insert_assignment(var.name, var.init_expression->clone());
 743                 }
 744         }
 745         else if(var.interface=="in")
 746         {
 747                 stage->in_variables[var.name] = &var;
 748                 if(var.linked_declaration)
 749                         var.linked_declaration->linked_declaration = &var;
 750                 else if(stage->previous)
 751                 {
 752                         const map<string, VariableDeclaration *> &prev_out = stage->previous->out_variables;
 753                         map<string, VariableDeclaration *>::const_iterator i = prev_out.find(var.name);
 754                         if(i!=prev_out.end())
 755                         {
 756                                 var.linked_declaration = i->second;
 757                                 i->second->linked_declaration = &var;
 758                         }
 759                 }
 760         }
 761
 762         TraversingVisitor::visit(var);
 763 }
 764
 765 void ProgramCompiler::InterfaceGenerator::visit(Passthrough &pass)
 766 {
 767         vector<VariableDeclaration *> pass_vars;
 768
 769         for(map<string, VariableDeclaration *>::const_iterator i=stage->in_variables.begin(); i!=stage->in_variables.end(); ++i)
 770                 pass_vars.push_back(i->second);
 771         for(map<string, VariableDeclaration *>::const_iterator i=iface_declarations.begin(); i!=iface_declarations.end(); ++i)
 772                 if(i->second->interface=="in")
 773                         pass_vars.push_back(i->second);
 774
 775         if(stage->previous)
 776         {
 777                 const map<string, VariableDeclaration *> &prev_out = stage->previous->out_variables;
 778                 for(map<string, VariableDeclaration *>::const_iterator i=prev_out.begin(); i!=prev_out.end(); ++i)
 779                 {
 780                         bool linked = false;
 781                         for(vector<VariableDeclaration *>::const_iterator j=pass_vars.begin(); (!linked && j!=pass_vars.end()); ++j)
 782                                 linked = ((*j)->linked_declaration==i->second);
 783
 784                         if(!linked && generate_interface(*i->second, "in", i->second->name))
 785                                 pass_vars.push_back(i->second);
 786                 }
 787         }
 788
 789         if(stage->type==GEOMETRY)
 790         {
 791                 VariableReference *ref = new VariableReference;
 792                 ref->name = "gl_in";
 793
 794                 BinaryExpression *subscript = new BinaryExpression;
 795                 subscript->left = ref;
 796                 subscript->oper = "[";
 797                 subscript->right = pass.subscript;
 798                 subscript->after = "]";
 799
 800                 MemberAccess *memacc = new MemberAccess;
 801                 memacc->left = subscript;
 802                 memacc->member = "gl_Position";
 803
 804                 insert_assignment("gl_Position", memacc);
 805         }
 806
 807         for(vector<VariableDeclaration *>::const_iterator i=pass_vars.begin(); i!=pass_vars.end(); ++i)
 808         {
 809                 string out_name = change_prefix((*i)->name, out_prefix);
 810                 generate_interface(**i, "out", out_name);
 811
 812                 VariableReference *ref = new VariableReference;
 813                 ref->name = (*i)->name;
 814                 if(pass.subscript)
 815                 {
 816                         BinaryExpression *subscript = new BinaryExpression;
 817                         subscript->left = ref;
 818                         subscript->oper = "[";
 819                         subscript->right = pass.subscript;
 820                         subscript->after = "]";
 821                         insert_assignment(out_name, subscript);
 822                 }
 823                 else
 824                         insert_assignment(out_name, ref);
 825         }
 826
 827         remove_node = true;
 828 }
 829
 830
 831 void ProgramCompiler::VariableRenamer::visit(VariableReference &var)
 832 {
 833         if(var.declaration)
 834                 var.name = var.declaration->name;
 835 }
 836
 837 void ProgramCompiler::VariableRenamer::visit(VariableDeclaration &var)
 838 {
 839         if(var.linked_declaration)
 840                 var.name = var.linked_declaration->name;
 841         TraversingVisitor::visit(var);
 842 }
 843
 844
 845 ProgramCompiler::ExpressionEvaluator::ExpressionEvaluator():
 846         variable_values(0),
 847         result(0.0f),
 848         result_valid(false)
 849 { }
 850
 851 ProgramCompiler::ExpressionEvaluator::ExpressionEvaluator(const ValueMap &v):
 852         variable_values(&v),
 853         result(0.0f),
 854         result_valid(false)
 855 { }
 856
 857 void ProgramCompiler::ExpressionEvaluator::visit(Literal &literal)
 858 {
 859         if(literal.token=="true")
 860                 result = 1.0f;
 861         else if(literal.token=="false")
 862                 result = 0.0f;
 863         else
 864                 result = lexical_cast<float>(literal.token);
 865         result_valid = true;
 866 }
 867
 868 void ProgramCompiler::ExpressionEvaluator::visit(VariableReference &var)
 869 {
 870         if(!var.declaration)
 871                 return;
 872
 873         if(variable_values)
 874         {
 875                 ValueMap::const_iterator i = variable_values->find(var.declaration);
 876                 if(i!=variable_values->end())
 877                         i->second->visit(*this);
 878         }
 879         else if(var.declaration->init_expression)
 880                 var.declaration->init_expression->visit(*this);
 881 }
 882
 883 void ProgramCompiler::ExpressionEvaluator::visit(UnaryExpression &unary)
 884 {
 885         result_valid = false;
 886         unary.expression->visit(*this);
 887         if(!result_valid)
 888                 return;
 889
 890         if(unary.oper=="!")
 891                 result = !result;
 892         else
 893                 result_valid = false;
 894 }
 895
 896 void ProgramCompiler::ExpressionEvaluator::visit(BinaryExpression &binary)
 897 {
 898         result_valid = false;
 899         binary.left->visit(*this);
 900         if(!result_valid)
 901                 return;
 902
 903         float left_result = result;
 904         result_valid = false;
 905         binary.right->visit(*this);
 906         if(!result_valid)
 907                 return;
 908
 909         if(binary.oper=="<")
 910                 result = (left_result<result);
 911         else if(binary.oper=="<=")
 912                 result = (left_result<=result);
 913         else if(binary.oper==">")
 914                 result = (left_result>result);
 915         else if(binary.oper==">=")
 916                 result = (left_result>=result);
 917         else if(binary.oper=="==")
 918                 result = (left_result==result);
 919         else if(binary.oper=="!=")
 920                 result = (left_result!=result);
 921         else if(binary.oper=="&&")
 922                 result = (left_result && result);
 923         else if(binary.oper=="||")
 924                 result = (left_result || result);
 925         else
 926                 result_valid = false;
 927 }
 928
 929
 930 ProgramCompiler::ConstantConditionEliminator::ConstantConditionEliminator():
 931         scope_level(0),
 932         remove_node(false),
 933         replacement_block(0)
 934 { }
 935
 936 void ProgramCompiler::ConstantConditionEliminator::visit(Block &block)
 937 {
 938         SetForScope<unsigned> set(scope_level, scope_level+1);
 939         for(list<NodePtr<Node> >::iterator i=block.body.begin(); i!=block.body.end(); )
 940         {
 941                 (*i)->visit(*this);
 942                 if(replacement_block)
 943                 {
 944                         for(list<NodePtr<Node> >::iterator j=replacement_block->body.begin(); j!=replacement_block->body.end(); ++j)
 945                                 block.body.insert(i, *j);
 946                         replacement_block = 0;
 947                 }
 948
 949                 if(remove_node)
 950                         block.body.erase(i++);
 951                 else
 952                         ++i;
 953                 remove_node = false;
 954         }
 955
 956         for(map<string, VariableDeclaration *>::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 957                 variable_values.erase(i->second);
 958 }
 959
 960 void ProgramCompiler::ConstantConditionEliminator::visit(Assignment &assign)
 961 {
 962         variable_values.erase(assign.target_declaration);
 963 }
 964
 965 void ProgramCompiler::ConstantConditionEliminator::visit(VariableDeclaration &var)
 966 {
 967         if(var.constant || scope_level>1)
 968                 variable_values[&var] = &*var.init_expression;
 969 }
 970
 971 void ProgramCompiler::ConstantConditionEliminator::visit(Conditional &cond)
 972 {
 973         ExpressionEvaluator eval(variable_values);
 974         cond.condition->visit(eval);
 975         if(eval.result_valid)
 976         {
 977                 remove_node = true;
 978                 replacement_block = (eval.result ? &cond.body : &cond.else_body);
 979         }
 980         else
 981                 TraversingVisitor::visit(cond);
 982 }
 983
 984 void ProgramCompiler::ConstantConditionEliminator::visit(Iteration &iter)
 985 {
 986         if(iter.condition)
 987         {
 988                 ExpressionEvaluator eval;
 989                 iter.condition->visit(eval);
 990                 if(eval.result_valid && !eval.result)
 991                 {
 992                         remove_node = true;
 993                         return;
 994                 }
 995         }
 996
 997         TraversingVisitor::visit(iter);
 998 }
 999
1000
1001 ProgramCompiler::UnusedVariableLocator::UnusedVariableLocator():
1002         aggregate(0),
1003         assignment(0),
1004         assignment_target(false)
1005 { }
1006
1007 void ProgramCompiler::UnusedVariableLocator::apply(Stage &s)
1008 {
1009         assignments.push_back(BlockAssignmentMap());
1010         Visitor::apply(s);
1011         assignments.pop_back();
1012 }
1013
1014 void ProgramCompiler::UnusedVariableLocator::visit(VariableReference &var)
1015 {
1016         unused_nodes.erase(var.declaration);
1017
1018         map<VariableDeclaration *, Node *>::iterator i = aggregates.find(var.declaration);
1019         if(i!=aggregates.end())
1020                 unused_nodes.erase(i->second);
1021
1022         if(assignment_target)
1023                 return;
1024
1025         for(vector<BlockAssignmentMap>::iterator j=assignments.end(); j!=assignments.begin(); )
1026         {
1027                 --j;
1028                 BlockAssignmentMap::iterator k = j->find(var.declaration);
1029                 if(k!=j->end())
1030                 {
1031                         for(vector<Node *>::iterator l=k->second.nodes.begin(); l!=k->second.nodes.end(); ++l)
1032                                 unused_nodes.erase(*l);
1033                         j->erase(k);
1034                         break;
1035                 }
1036         }
1037 }
1038
1039 void ProgramCompiler::UnusedVariableLocator::visit(MemberAccess &memacc)
1040 {
1041         TraversingVisitor::visit(memacc);
1042         unused_nodes.erase(memacc.declaration);
1043 }
1044
1045 void ProgramCompiler::UnusedVariableLocator::visit(BinaryExpression &binary)
1046 {
1047         if(binary.oper=="[")
1048         {
1049                 binary.left->visit(*this);
1050                 SetForScope<bool> set(assignment_target, false);
1051                 binary.right->visit(*this);
1052         }
1053         else
1054                 TraversingVisitor::visit(binary);
1055 }
1056
1057 void ProgramCompiler::UnusedVariableLocator::visit(Assignment &assign)
1058 {
1059         {
1060                 SetForScope<bool> set(assignment_target, !assign.self_referencing);
1061                 assign.left->visit(*this);
1062         }
1063         assign.right->visit(*this);
1064         assignment = &assign;
1065 }
1066
1067 void ProgramCompiler::UnusedVariableLocator::record_assignment(VariableDeclaration &var, Node &node, bool self_ref)
1068 {
1069         unused_nodes.insert(&node);
1070         BlockAssignmentMap &block_assignments = assignments.back();
1071         AssignmentList &var_assignments = block_assignments[&var];
1072         if(!self_ref)
1073                 var_assignments.nodes.clear();
1074         var_assignments.nodes.push_back(&node);
1075         var_assignments.conditional = false;
1076         var_assignments.self_referencing = self_ref;
1077 }
1078
1079 void ProgramCompiler::UnusedVariableLocator::visit(ExpressionStatement &expr)
1080 {
1081         assignment = 0;
1082         TraversingVisitor::visit(expr);
1083         if(assignment && assignment->target_declaration)
1084                 record_assignment(*assignment->target_declaration, expr, assignment->self_referencing);
1085 }
1086
1087 void ProgramCompiler::UnusedVariableLocator::visit(StructDeclaration &strct)
1088 {
1089         SetForScope<Node *> set(aggregate, &strct);
1090         unused_nodes.insert(&strct);
1091         TraversingVisitor::visit(strct);
1092 }
1093
1094 void ProgramCompiler::UnusedVariableLocator::visit(VariableDeclaration &var)
1095 {
1096         if(aggregate)
1097                 aggregates[&var] = aggregate;
1098         else
1099         {
1100                 unused_nodes.insert(&var);
1101                 if(var.init_expression)
1102                         record_assignment(var, *var.init_expression, false);
1103         }
1104         unused_nodes.erase(var.type_declaration);
1105         TraversingVisitor::visit(var);
1106 }
1107
1108 void ProgramCompiler::UnusedVariableLocator::visit(InterfaceBlock &iface)
1109 {
1110         SetForScope<Node *> set(aggregate, &iface);
1111         unused_nodes.insert(&iface);
1112         TraversingVisitor::visit(iface);
1113 }
1114
1115 void ProgramCompiler::UnusedVariableLocator::visit(FunctionDeclaration &func)
1116 {
1117         assignments.push_back(BlockAssignmentMap());
1118
1119         for(vector<NodePtr<VariableDeclaration> >::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1120                 (*i)->visit(*this);
1121         func.body.visit(*this);
1122
1123         BlockAssignmentMap &block_assignments = assignments.back();
1124         for(map<string, VariableDeclaration *>::iterator i=func.body.variables.begin(); i!=func.body.variables.end(); ++i)
1125                 block_assignments.erase(i->second);
1126         for(BlockAssignmentMap::iterator i=block_assignments.begin(); i!=block_assignments.end(); ++i)
1127         {
1128                 if(i->first->interface=="out" && stage->type!=FRAGMENT && !i->first->linked_declaration)
1129                         continue;
1130
1131                 for(vector<Node *>::iterator j=i->second.nodes.begin(); j!=i->second.nodes.end(); ++j)
1132                         unused_nodes.erase(*j);
1133         }
1134
1135         assignments.pop_back();
1136 }
1137
1138 void ProgramCompiler::UnusedVariableLocator::merge_down_assignments()
1139 {
1140         BlockAssignmentMap &parent_assignments = assignments[assignments.size()-2];
1141         BlockAssignmentMap &block_assignments = assignments.back();
1142         for(BlockAssignmentMap::iterator i=block_assignments.begin(); i!=block_assignments.end(); ++i)
1143         {
1144                 BlockAssignmentMap::iterator j = parent_assignments.find(i->first);
1145                 if(j==parent_assignments.end())
1146                         parent_assignments.insert(*i);
1147                 else if(i->second.self_referencing || i->second.conditional)
1148                 {
1149                         j->second.nodes.insert(j->second.nodes.end(), i->second.nodes.begin(), i->second.nodes.end());
1150                         j->second.conditional |= i->second.conditional;
1151                         j->second.self_referencing |= i->second.self_referencing;
1152                 }
1153                 else
1154                         j->second = i->second;
1155         }
1156         assignments.pop_back();
1157 }
1158
1159 void ProgramCompiler::UnusedVariableLocator::visit(Conditional &cond)
1160 {
1161         cond.condition->visit(*this);
1162         assignments.push_back(BlockAssignmentMap());
1163         cond.body.visit(*this);
1164
1165         BlockAssignmentMap if_assignments;
1166         swap(assignments.back(), if_assignments);
1167         cond.else_body.visit(*this);
1168
1169         BlockAssignmentMap &else_assignments = assignments.back();
1170         for(BlockAssignmentMap::iterator i=else_assignments.begin(); i!=else_assignments.end(); ++i)
1171         {
1172                 BlockAssignmentMap::iterator j = if_assignments.find(i->first);
1173                 if(j!=if_assignments.end())
1174                 {
1175                         i->second.nodes.insert(i->second.nodes.end(), j->second.nodes.begin(), j->second.nodes.end());
1176                         i->second.conditional |= j->second.conditional;
1177                         i->second.self_referencing |= j->second.self_referencing;
1178                         if_assignments.erase(j);
1179                 }
1180                 else
1181                         i->second.conditional = true;
1182         }
1183
1184         for(BlockAssignmentMap::iterator i=if_assignments.begin(); i!=if_assignments.end(); ++i)
1185         {
1186                 i->second.conditional = true;
1187                 else_assignments.insert(*i);
1188         }
1189
1190         merge_down_assignments();
1191 }
1192
1193 void ProgramCompiler::UnusedVariableLocator::visit(Iteration &iter)
1194 {
1195         assignments.push_back(BlockAssignmentMap());
1196         TraversingVisitor::visit(iter);
1197         merge_down_assignments();
1198 }
1199
1200
1201 ProgramCompiler::NodeRemover::NodeRemover(const set<Node *> &r):
1202         to_remove(r)
1203 { }
1204
1205 void ProgramCompiler::NodeRemover::visit(Block &block)
1206 {
1207         for(list<NodePtr<Node> >::iterator i=block.body.begin(); i!=block.body.end(); )
1208         {
1209                 (*i)->visit(*this);
1210                 if(to_remove.count(&**i))
1211                         block.body.erase(i++);
1212                 else
1213                         ++i;
1214         }
1215 }
1216
1217 void ProgramCompiler::NodeRemover::visit(VariableDeclaration &var)
1218 {
1219         if(to_remove.count(&var))
1220         {
1221                 stage->in_variables.erase(var.name);
1222                 stage->out_variables.erase(var.name);
1223                 if(var.linked_declaration)
1224                         var.linked_declaration->linked_declaration = 0;
1225         }
1226         else if(var.init_expression && to_remove.count(&*var.init_expression))
1227                 var.init_expression = 0;
1228 }
1229
1230 } // namespace GL
1231 } // namespace Msp