source/programcompiler.cpp

   1 #include <msp/core/algorithm.h>
   2 #include <msp/core/raii.h>
   3 #include <msp/gl/extensions/arb_explicit_attrib_location.h>
   4 #include <msp/gl/extensions/arb_gpu_shader5.h>
   5 #include <msp/gl/extensions/arb_uniform_buffer_object.h>
   6 #include <msp/gl/extensions/ext_gpu_shader4.h>
   7 #include <msp/strings/format.h>
   8 #include <msp/strings/utils.h>
   9 #include "error.h"
  10 #include "program.h"
  11 #include "programcompiler.h"
  12 #include "resources.h"
  13 #include "shader.h"
  14
  15 #undef interface
  16
  17 using namespace std;
  18
  19 namespace {
  20
  21 const char builtins_src[] =
  22         "#pragma MSP stage(vertex)\n"
  23         "out gl_PerVertex {\n"
  24         "  vec4 gl_Position;\n"
  25         "  float gl_ClipDistance[];\n"
  26         "};\n"
  27         "#pragma MSP stage(geometry)\n"
  28         "in gl_PerVertex {\n"
  29         "  vec4 gl_Position;\n"
  30         "  float gl_ClipDistance[];\n"
  31         "} gl_in[];\n"
  32         "out gl_PerVertex {\n"
  33         "  vec4 gl_Position;\n"
  34         "  float gl_ClipDistance[];\n"
  35         "};\n";
  36
  37 }
  38
  39 namespace Msp {
  40 namespace GL {
  41
  42 using namespace ProgramSyntax;
  43
  44 ProgramCompiler::ProgramCompiler():
  45         resources(0),
  46         module(0)
  47 { }
  48
  49 ProgramCompiler::~ProgramCompiler()
  50 {
  51         delete module;
  52 }
  53
  54 void ProgramCompiler::compile(const string &source, const string &src_name)
  55 {
  56         resources = 0;
  57         delete module;
  58         module = new Module();
  59         ProgramParser parser;
  60         imported_names.insert(src_name);
  61         append_module(parser.parse(source, src_name));
  62         process();
  63 }
  64
  65 void ProgramCompiler::compile(IO::Base &io, Resources *res, const string &src_name)
  66 {
  67         resources = res;
  68         delete module;
  69         module = new Module();
  70         ProgramParser parser;
  71         imported_names.insert(src_name);
  72         append_module(parser.parse(io, src_name));
  73         process();
  74 }
  75
  76 void ProgramCompiler::compile(IO::Base &io, const string &src_name)
  77 {
  78         compile(io, 0, src_name);
  79 }
  80
  81 void ProgramCompiler::add_shaders(Program &program)
  82 {
  83         if(!module)
  84                 throw invalid_operation("ProgramCompiler::add_shaders");
  85
  86         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
  87         {
  88                 if(i->type==VERTEX)
  89                 {
  90                         program.attach_shader_owned(new VertexShader(apply<Formatter>(*i)));
  91                         for(map<string, unsigned>::iterator j=i->locations.begin(); j!=i->locations.end(); ++j)
  92                                 program.bind_attribute(j->second, j->first);
  93                 }
  94                 else if(i->type==GEOMETRY)
  95                         program.attach_shader_owned(new GeometryShader(apply<Formatter>(*i)));
  96                 else if(i->type==FRAGMENT)
  97                 {
  98                         program.attach_shader_owned(new FragmentShader(apply<Formatter>(*i)));
  99                         if(EXT_gpu_shader4)
 100                         {
 101                                 for(map<string, unsigned>::iterator j=i->locations.begin(); j!=i->locations.end(); ++j)
 102                                         program.bind_fragment_data(j->second, j->first);
 103                         }
 104                 }
 105         }
 106 }
 107
 108 Module *ProgramCompiler::create_builtins_module()
 109 {
 110         ProgramParser parser;
 111         Module *module = new Module(parser.parse(builtins_src, "<builtin>"));
 112         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
 113         {
 114                 VariableResolver resolver;
 115                 i->content.visit(resolver);
 116                 for(map<string, VariableDeclaration *>::iterator j=i->content.variables.begin(); j!=i->content.variables.end(); ++j)
 117                         j->second->linked_declaration = j->second;
 118         }
 119         return module;
 120 }
 121
 122 Module &ProgramCompiler::get_builtins_module()
 123 {
 124         static RefPtr<Module> builtins_module = create_builtins_module();
 125         return *builtins_module;
 126 }
 127
 128 Stage *ProgramCompiler::get_builtins(StageType type)
 129 {
 130         Module &module = get_builtins_module();
 131         for(list<Stage>::iterator i=module.stages.begin(); i!=module.stages.end(); ++i)
 132                 if(i->type==type)
 133                         return &*i;
 134         return 0;
 135 }
 136
 137 void ProgramCompiler::append_module(ProgramSyntax::Module &mod)
 138 {
 139         vector<Import *> imports = apply<NodeGatherer<Import> >(mod.shared);
 140         for(vector<Import *>::iterator i=imports.begin(); i!=imports.end(); ++i)
 141                 import((*i)->module);
 142         apply<NodeRemover>(mod.shared, set<Node *>(imports.begin(), imports.end()));
 143
 144         append_stage(mod.shared);
 145         for(list<Stage>::iterator i=mod.stages.begin(); i!=mod.stages.end(); ++i)
 146                 append_stage(*i);
 147 }
 148
 149 void ProgramCompiler::append_stage(Stage &stage)
 150 {
 151         Stage *target = 0;
 152         if(stage.type==SHARED)
 153                 target = &module->shared;
 154         else
 155         {
 156                 list<Stage>::iterator i;
 157                 for(i=module->stages.begin(); (i!=module->stages.end() && i->type<stage.type); ++i) ;
 158                 if(i==module->stages.end() || i->type>stage.type)
 159                 {
 160                         list<Stage>::iterator j = module->stages.insert(i, stage.type);
 161                         if(i!=module->stages.end())
 162                                 i->previous = &*j;
 163                         i = j;
 164                         if(i!=module->stages.begin())
 165                                 i->previous = &*--j;
 166                 }
 167
 168                 target = &*i;
 169         }
 170
 171         for(NodeList<Statement>::iterator i=stage.content.body.begin(); i!=stage.content.body.end(); ++i)
 172                 target->content.body.push_back(*i);
 173         apply<DeclarationCombiner>(*target);
 174 }
 175
 176 void ProgramCompiler::process()
 177 {
 178         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
 179                 generate(*i);
 180         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); )
 181         {
 182                 if(optimize(*i))
 183                         i = module->stages.begin();
 184                 else
 185                         ++i;
 186         }
 187         for(list<Stage>::iterator i=module->stages.begin(); i!=module->stages.end(); ++i)
 188                 finalize(*i);
 189 }
 190
 191 void ProgramCompiler::import(const string &name)
 192 {
 193         string fn = name+".glsl";
 194         if(imported_names.count(fn))
 195                 return;
 196         imported_names.insert(fn);
 197
 198         RefPtr<IO::Seekable> io = (resources ? resources->open_raw(fn) : Resources::get_builtins().open(fn));
 199         if(!io)
 200                 throw runtime_error(format("module %s not found", name));
 201         ProgramParser import_parser;
 202         append_module(import_parser.parse(*io, fn));
 203 }
 204
 205 void ProgramCompiler::generate(Stage &stage)
 206 {
 207         inject_block(stage.content, module->shared.content);
 208
 209         apply<DeclarationReorderer>(stage);
 210         apply<FunctionResolver>(stage);
 211         apply<VariableResolver>(stage);
 212         apply<InterfaceGenerator>(stage);
 213         apply<VariableResolver>(stage);
 214         apply<DeclarationReorderer>(stage);
 215         apply<FunctionResolver>(stage);
 216         apply<LegacyConverter>(stage);
 217 }
 218
 219 bool ProgramCompiler::optimize(Stage &stage)
 220 {
 221         apply<ConstantConditionEliminator>(stage);
 222
 223         set<FunctionDeclaration *> inlineable = apply<InlineableFunctionLocator>(stage);
 224         apply<FunctionInliner>(stage, inlineable);
 225
 226         set<Node *> unused = apply<UnusedVariableLocator>(stage);
 227         set<Node *> unused2 = apply<UnusedFunctionLocator>(stage);
 228         unused.insert(unused2.begin(), unused2.end());
 229         apply<NodeRemover>(stage, unused);
 230
 231         return !unused.empty();
 232 }
 233
 234 void ProgramCompiler::finalize(Stage &stage)
 235 {
 236         if(get_gl_api()==OPENGL_ES2)
 237                 apply<DefaultPrecisionGenerator>(stage);
 238         else
 239                 apply<PrecisionRemover>(stage);
 240 }
 241
 242 void ProgramCompiler::inject_block(Block &target, const Block &source)
 243 {
 244         NodeList<Statement>::iterator insert_point = target.body.begin();
 245         for(NodeList<Statement>::const_iterator i=source.body.begin(); i!=source.body.end(); ++i)
 246                 target.body.insert(insert_point, (*i)->clone());
 247 }
 248
 249 template<typename T>
 250 typename T::ResultType ProgramCompiler::apply(Stage &stage)
 251 {
 252         T visitor;
 253         visitor.apply(stage);
 254         return visitor.get_result();
 255 }
 256
 257 template<typename T, typename A>
 258 typename T::ResultType ProgramCompiler::apply(Stage &stage, const A &arg)
 259 {
 260         T visitor(arg);
 261         visitor.apply(stage);
 262         return visitor.get_result();
 263 }
 264
 265
 266 ProgramCompiler::Visitor::Visitor():
 267         stage(0)
 268 { }
 269
 270 void ProgramCompiler::Visitor::apply(Stage &s)
 271 {
 272         SetForScope<Stage *> set(stage, &s);
 273         stage->content.visit(*this);
 274 }
 275
 276
 277 ProgramCompiler::BlockModifier::BlockModifier():
 278         remove_node(false)
 279 { }
 280
 281 void ProgramCompiler::BlockModifier::flatten_block(Block &block)
 282 {
 283         insert_nodes.insert(insert_nodes.end(), block.body.begin(), block.body.end());
 284         remove_node = true;
 285 }
 286
 287 void ProgramCompiler::BlockModifier::apply_and_increment(Block &block, NodeList<Statement>::iterator &i)
 288 {
 289         block.body.insert(i, insert_nodes.begin(), insert_nodes.end());
 290         insert_nodes.clear();
 291
 292         if(remove_node)
 293                 block.body.erase(i++);
 294         else
 295                 ++i;
 296         remove_node = false;
 297 }
 298
 299 void ProgramCompiler::BlockModifier::visit(Block &block)
 300 {
 301         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); )
 302         {
 303                 (*i)->visit(*this);
 304                 apply_and_increment(block, i);
 305         }
 306 }
 307
 308
 309 ProgramCompiler::Formatter::Formatter():
 310         indent(0),
 311         parameter_list(false)
 312 { }
 313
 314 void ProgramCompiler::Formatter::apply(ProgramSyntax::Stage &s)
 315 {
 316         GLApi api = get_gl_api();
 317         const Version &ver = s.required_version;
 318
 319         if(ver)
 320         {
 321                 append(format("#version %d%02d", ver.major, ver.minor));
 322                 if(api==OPENGL_ES2 && ver>=Version(3, 0))
 323                         append(" es");
 324                 formatted += '\n';
 325         }
 326
 327         for(vector<const Extension *>::const_iterator i=s.required_extensions.begin(); i!=s.required_extensions.end(); ++i)
 328                 append(format("#extension %s: require\n", (*i)->get_name()));
 329         if(!s.required_extensions.empty())
 330                 formatted += '\n';
 331
 332         Visitor::apply(s);
 333 }
 334
 335 void ProgramCompiler::Formatter::append(const string &text)
 336 {
 337         formatted += text;
 338 }
 339
 340 void ProgramCompiler::Formatter::append(char c)
 341 {
 342         formatted += c;
 343 }
 344
 345 void ProgramCompiler::Formatter::visit(Literal &literal)
 346 {
 347         append(literal.token);
 348 }
 349
 350 void ProgramCompiler::Formatter::visit(ParenthesizedExpression &parexpr)
 351 {
 352         append('(');
 353         parexpr.expression->visit(*this);
 354         append(')');
 355 }
 356
 357 void ProgramCompiler::Formatter::visit(VariableReference &var)
 358 {
 359         append(var.name);
 360 }
 361
 362 void ProgramCompiler::Formatter::visit(MemberAccess &memacc)
 363 {
 364         memacc.left->visit(*this);
 365         append(format(".%s", memacc.member));
 366 }
 367
 368 void ProgramCompiler::Formatter::visit(UnaryExpression &unary)
 369 {
 370         if(unary.prefix)
 371                 append(unary.oper);
 372         unary.expression->visit(*this);
 373         if(!unary.prefix)
 374                 append(unary.oper);
 375 }
 376
 377 void ProgramCompiler::Formatter::visit(BinaryExpression &binary)
 378 {
 379         binary.left->visit(*this);
 380         append(binary.oper);
 381         binary.right->visit(*this);
 382         append(binary.after);
 383 }
 384
 385 void ProgramCompiler::Formatter::visit(Assignment &assign)
 386 {
 387         assign.left->visit(*this);
 388         append(format(" %s ", assign.oper));
 389         assign.right->visit(*this);
 390 }
 391
 392 void ProgramCompiler::Formatter::visit(FunctionCall &call)
 393 {
 394         append(format("%s(", call.name));
 395         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
 396         {
 397                 if(i!=call.arguments.begin())
 398                         append(", ");
 399                 (*i)->visit(*this);
 400         }
 401         append(')');
 402 }
 403
 404 void ProgramCompiler::Formatter::visit(ExpressionStatement &expr)
 405 {
 406         expr.expression->visit(*this);
 407         append(';');
 408 }
 409
 410 void ProgramCompiler::Formatter::visit(Block &block)
 411 {
 412         unsigned brace_indent = indent;
 413         bool use_braces = (block.use_braces || (indent && block.body.size()!=1));
 414         if(use_braces)
 415                 append(format("%s{\n", string(brace_indent*2, ' ')));
 416
 417         SetForScope<unsigned> set(indent, indent+(indent>0 || use_braces));
 418         string spaces(indent*2, ' ');
 419         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
 420         {
 421                 if(i!=block.body.begin())
 422                         append('\n');
 423                 append(spaces);
 424                 (*i)->visit(*this);
 425         }
 426
 427         if(use_braces)
 428                 append(format("\n%s}", string(brace_indent*2, ' ')));
 429 }
 430
 431 void ProgramCompiler::Formatter::visit(Import &import)
 432 {
 433         append(format("import %s;", import.module));
 434 }
 435
 436 void ProgramCompiler::Formatter::visit(Precision &prec)
 437 {
 438         append(format("precision %s %s;", prec.precision, prec.type));
 439 }
 440
 441 void ProgramCompiler::Formatter::visit(Layout &layout)
 442 {
 443         append("layout(");
 444         for(vector<Layout::Qualifier>::const_iterator i=layout.qualifiers.begin(); i!=layout.qualifiers.end(); ++i)
 445         {
 446                 if(i!=layout.qualifiers.begin())
 447                         append(", ");
 448                 append(i->identifier);
 449                 if(!i->value.empty())
 450                         append(format("=%s", i->value));
 451         }
 452         append(')');
 453 }
 454
 455 void ProgramCompiler::Formatter::visit(InterfaceLayout &layout)
 456 {
 457         layout.layout.visit(*this);
 458         append(format(" %s;", layout.interface));
 459 }
 460
 461 void ProgramCompiler::Formatter::visit(StructDeclaration &strct)
 462 {
 463         append(format("struct %s\n", strct.name));
 464         strct.members.visit(*this);
 465         append(';');
 466 }
 467
 468 void ProgramCompiler::Formatter::visit(VariableDeclaration &var)
 469 {
 470         if(var.layout)
 471         {
 472                 var.layout->visit(*this);
 473                 append(' ');
 474         }
 475         if(var.constant)
 476                 append("const ");
 477         if(!var.interpolation.empty())
 478                 append(format("%s ", var.interpolation));
 479         if(!var.sampling.empty())
 480                 append(format("%s ", var.sampling));
 481         if(!var.interface.empty() && var.interface!=block_interface)
 482         {
 483                 string interface = var.interface;
 484                 if(stage->required_version<Version(1, 30))
 485                 {
 486                         if(stage->type==VERTEX && var.interface=="in")
 487                                 interface = "attribute";
 488                         else if((stage->type==VERTEX && var.interface=="out") || (stage->type==FRAGMENT && var.interface=="in"))
 489                                 interface = "varying";
 490                 }
 491                 append(format("%s ", interface));
 492         }
 493         if(!var.precision.empty())
 494                 append(format("%s ", var.precision));
 495         append(format("%s %s", var.type, var.name));
 496         if(var.array)
 497         {
 498                 append('[');
 499                 if(var.array_size)
 500                         var.array_size->visit(*this);
 501                 append(']');
 502         }
 503         if(var.init_expression)
 504         {
 505                 append(" = ");
 506                 var.init_expression->visit(*this);
 507         }
 508         if(!parameter_list)
 509                 append(';');
 510 }
 511
 512 void ProgramCompiler::Formatter::visit(InterfaceBlock &iface)
 513 {
 514         SetForScope<string> set(block_interface, iface.interface);
 515         append(format("%s %s\n", iface.interface, iface.name));
 516         iface.members.visit(*this);
 517         append(';');
 518 }
 519
 520 void ProgramCompiler::Formatter::visit(FunctionDeclaration &func)
 521 {
 522         append(format("%s %s(", func.return_type, func.name));
 523         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 524         {
 525                 if(i!=func.parameters.begin())
 526                         append(", ");
 527                 SetFlag set(parameter_list);
 528                 (*i)->visit(*this);
 529         }
 530         append(')');
 531         if(func.definition==&func)
 532         {
 533                 append('\n');
 534                 func.body.visit(*this);
 535         }
 536         else
 537                 append(';');
 538 }
 539
 540 void ProgramCompiler::Formatter::visit(Conditional &cond)
 541 {
 542         append("if(");
 543         cond.condition->visit(*this);
 544         append(")\n");
 545
 546         cond.body.visit(*this);
 547         if(!cond.else_body.body.empty())
 548         {
 549                 Conditional *else_cond = dynamic_cast<Conditional *>(cond.else_body.body.front().get());
 550                 if(cond.else_body.body.size()==1 && else_cond)
 551                 {
 552                         append(format("\n%selse ", string(indent*2, ' ')));
 553                         else_cond->visit(*this);
 554                 }
 555                 else
 556                 {
 557                         append(format("\n%selse\n", string(indent*2, ' ')));
 558                         cond.else_body.visit(*this);
 559                 }
 560         }
 561 }
 562
 563 void ProgramCompiler::Formatter::visit(Iteration &iter)
 564 {
 565         if(!iter.init_statement && iter.condition && !iter.loop_expression)
 566         {
 567                 append("while(");
 568                 iter.condition->visit(*this);
 569                 append(')');
 570         }
 571         else
 572         {
 573                 append("for(");
 574                 if(iter.init_statement)
 575                         iter.init_statement->visit(*this);
 576                 else
 577                         append(';');
 578                 if(iter.condition)
 579                 {
 580                         append(' ');
 581                         iter.condition->visit(*this);
 582                 }
 583                 append(';');
 584                 if(iter.loop_expression)
 585                 {
 586                         append(' ');
 587                         iter.loop_expression->visit(*this);
 588                 }
 589                 append(')');
 590         }
 591
 592         if(iter.body.body.empty())
 593                 append(" { }");
 594         else
 595         {
 596                 append('\n');
 597                 iter.body.visit(*this);
 598         }
 599 }
 600
 601 void ProgramCompiler::Formatter::visit(Return &ret)
 602 {
 603         append("return");
 604         if(ret.expression)
 605         {
 606                 append(' ');
 607                 ret.expression->visit(*this);
 608         }
 609         append(';');
 610 }
 611
 612 void ProgramCompiler::Formatter::visit(Jump &jump)
 613 {
 614         append(jump.keyword);
 615         append(';');
 616 }
 617
 618
 619 ProgramCompiler::DeclarationCombiner::DeclarationCombiner():
 620         toplevel(true)
 621 { }
 622
 623 void ProgramCompiler::DeclarationCombiner::visit(Block &block)
 624 {
 625         if(!toplevel)
 626                 return;
 627
 628         SetForScope<bool> set(toplevel, false);
 629         BlockModifier::visit(block);
 630 }
 631
 632 void ProgramCompiler::DeclarationCombiner::visit(FunctionDeclaration &func)
 633 {
 634         vector<FunctionDeclaration *> &decls = functions[func.name];
 635         if(func.definition)
 636         {
 637                 for(vector<FunctionDeclaration *>::iterator i=decls.begin(); i!=decls.end(); ++i)
 638                 {
 639                         (*i)->definition = func.definition;
 640                         (*i)->body.body.clear();
 641                 }
 642         }
 643         decls.push_back(&func);
 644 }
 645
 646 void ProgramCompiler::DeclarationCombiner::visit(VariableDeclaration &var)
 647 {
 648         VariableDeclaration *&ptr = variables[var.name];
 649         if(ptr)
 650         {
 651                 ptr->type = var.type;
 652                 if(var.init_expression)
 653                         ptr->init_expression = var.init_expression;
 654                 if(var.layout)
 655                 {
 656                         if(ptr->layout)
 657                         {
 658                                 for(vector<Layout::Qualifier>::iterator i=var.layout->qualifiers.begin(); i!=var.layout->qualifiers.end(); ++i)
 659                                 {
 660                                         bool found = false;
 661                                         for(vector<Layout::Qualifier>::iterator j=ptr->layout->qualifiers.begin(); (!found && j!=ptr->layout->qualifiers.end()); ++j)
 662                                                 if(j->identifier==i->identifier)
 663                                                 {
 664                                                         j->value = i->value;
 665                                                         found = true;
 666                                                 }
 667
 668                                         if(!found)
 669                                                 ptr->layout->qualifiers.push_back(*i);
 670                                 }
 671                         }
 672                         else
 673                                 ptr->layout = var.layout;
 674                 }
 675                 remove_node = true;
 676         }
 677         else
 678                 ptr = &var;
 679 }
 680
 681
 682 ProgramCompiler::VariableResolver::VariableResolver():
 683         anonymous(false),
 684         record_target(false),
 685         assignment_target(0),
 686         self_referencing(false)
 687 { }
 688
 689 void ProgramCompiler::VariableResolver::apply(Stage &s)
 690 {
 691         SetForScope<Stage *> set(stage, &s);
 692         Stage *builtins = get_builtins(stage->type);
 693         if(builtins)
 694                 blocks.push_back(&builtins->content);
 695         stage->content.visit(*this);
 696         if(builtins)
 697                 blocks.pop_back();
 698 }
 699
 700 void ProgramCompiler::VariableResolver::visit(Block &block)
 701 {
 702         blocks.push_back(&block);
 703         block.variables.clear();
 704         TraversingVisitor::visit(block);
 705         blocks.pop_back();
 706 }
 707
 708 void ProgramCompiler::VariableResolver::visit(VariableReference &var)
 709 {
 710         var.declaration = 0;
 711         type = 0;
 712         for(vector<Block *>::iterator i=blocks.end(); i!=blocks.begin(); )
 713         {
 714                 --i;
 715                 map<string, VariableDeclaration *>::iterator j = (*i)->variables.find(var.name);
 716                 if(j!=(*i)->variables.end())
 717                 {
 718                         var.declaration = j->second;
 719                         type = j->second->type_declaration;
 720                         break;
 721                 }
 722         }
 723
 724         if(record_target)
 725         {
 726                 if(assignment_target)
 727                 {
 728                         record_target = false;
 729                         assignment_target = 0;
 730                 }
 731                 else
 732                         assignment_target = var.declaration;
 733         }
 734         else if(var.declaration && var.declaration==assignment_target)
 735                 self_referencing = true;
 736 }
 737
 738 void ProgramCompiler::VariableResolver::visit(MemberAccess &memacc)
 739 {
 740         type = 0;
 741         TraversingVisitor::visit(memacc);
 742         memacc.declaration = 0;
 743         if(type)
 744         {
 745                 map<string, VariableDeclaration *>::iterator i = type->members.variables.find(memacc.member);
 746                 if(i!=type->members.variables.end())
 747                 {
 748                         memacc.declaration = i->second;
 749                         type = i->second->type_declaration;
 750                 }
 751                 else
 752                         type = 0;
 753         }
 754 }
 755
 756 void ProgramCompiler::VariableResolver::visit(BinaryExpression &binary)
 757 {
 758         if(binary.oper=="[")
 759         {
 760                 {
 761                         SetForScope<bool> set(record_target, false);
 762                         binary.right->visit(*this);
 763                 }
 764                 type = 0;
 765                 binary.left->visit(*this);
 766         }
 767         else
 768         {
 769                 TraversingVisitor::visit(binary);
 770                 type = 0;
 771         }
 772 }
 773
 774 void ProgramCompiler::VariableResolver::visit(Assignment &assign)
 775 {
 776         {
 777                 SetFlag set(record_target);
 778                 assignment_target = 0;
 779                 assign.left->visit(*this);
 780         }
 781
 782         self_referencing = false;
 783         assign.right->visit(*this);
 784
 785         assign.self_referencing = (self_referencing || assign.oper!="=");
 786         assign.target_declaration = assignment_target;
 787 }
 788
 789 void ProgramCompiler::VariableResolver::visit(StructDeclaration &strct)
 790 {
 791         TraversingVisitor::visit(strct);
 792         blocks.back()->types[strct.name] = &strct;
 793 }
 794
 795 void ProgramCompiler::VariableResolver::visit(VariableDeclaration &var)
 796 {
 797         for(vector<Block *>::iterator i=blocks.end(); i!=blocks.begin(); )
 798         {
 799                 --i;
 800                 map<string, StructDeclaration *>::iterator j = (*i)->types.find(var.type);
 801                 if(j!=(*i)->types.end())
 802                         var.type_declaration = j->second;
 803         }
 804
 805         if(!block_interface.empty() && var.interface.empty())
 806                 var.interface = block_interface;
 807
 808         TraversingVisitor::visit(var);
 809         blocks.back()->variables[var.name] = &var;
 810         if(anonymous && blocks.size()>1)
 811                 blocks[blocks.size()-2]->variables[var.name] = &var;
 812 }
 813
 814 void ProgramCompiler::VariableResolver::visit(InterfaceBlock &iface)
 815 {
 816         SetFlag set(anonymous);
 817         SetForScope<string> set2(block_interface, iface.interface);
 818         TraversingVisitor::visit(iface);
 819 }
 820
 821
 822 void ProgramCompiler::FunctionResolver::visit(FunctionCall &call)
 823 {
 824         map<string, vector<FunctionDeclaration *> >::iterator i = functions.find(call.name);
 825         if(i!=functions.end())
 826                 call.declaration = i->second.back();
 827
 828         TraversingVisitor::visit(call);
 829 }
 830
 831 void ProgramCompiler::FunctionResolver::visit(FunctionDeclaration &func)
 832 {
 833         vector<FunctionDeclaration *> &decls = functions[func.name];
 834         if(func.definition)
 835         {
 836                 for(vector<FunctionDeclaration *>::iterator i=decls.begin(); i!=decls.end(); ++i)
 837                         (*i)->definition = func.definition;
 838                 decls.clear();
 839                 decls.push_back(&func);
 840         }
 841         else if(!decls.empty() && decls.back()->definition)
 842                 func.definition = decls.back()->definition;
 843         else
 844                 decls.push_back(&func);
 845
 846         TraversingVisitor::visit(func);
 847 }
 848
 849
 850 ProgramCompiler::InterfaceGenerator::InterfaceGenerator():
 851         scope_level(0)
 852 { }
 853
 854 string ProgramCompiler::InterfaceGenerator::get_out_prefix(StageType type)
 855 {
 856         if(type==VERTEX)
 857                 return "_vs_out_";
 858         else if(type==GEOMETRY)
 859                 return "_gs_out_";
 860         else
 861                 return string();
 862 }
 863
 864 void ProgramCompiler::InterfaceGenerator::apply(Stage &s)
 865 {
 866         SetForScope<Stage *> set(stage, &s);
 867         if(stage->previous)
 868                 in_prefix = get_out_prefix(stage->previous->type);
 869         out_prefix = get_out_prefix(stage->type);
 870         stage->content.visit(*this);
 871 }
 872
 873 void ProgramCompiler::InterfaceGenerator::visit(Block &block)
 874 {
 875         SetForScope<unsigned> set(scope_level, scope_level+1);
 876         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); )
 877         {
 878                 (*i)->visit(*this);
 879
 880                 if(scope_level==1)
 881                 {
 882                         for(map<string, RefPtr<VariableDeclaration> >::iterator j=iface_declarations.begin(); j!=iface_declarations.end(); ++j)
 883                         {
 884                                 NodeList<Statement>::iterator k = block.body.insert(i, j->second);
 885                                 (*k)->visit(*this);
 886                         }
 887                         iface_declarations.clear();
 888                 }
 889
 890                 apply_and_increment(block, i);
 891         }
 892 }
 893
 894 string ProgramCompiler::InterfaceGenerator::change_prefix(const string &name, const string &prefix) const
 895 {
 896         unsigned offset = (name.compare(0, in_prefix.size(), in_prefix) ? 0 : in_prefix.size());
 897         return prefix+name.substr(offset);
 898 }
 899
 900 bool ProgramCompiler::InterfaceGenerator::generate_interface(VariableDeclaration &var, const string &iface, const string &name)
 901 {
 902         const map<string, VariableDeclaration *> &stage_vars = (iface=="in" ? stage->in_variables : stage->out_variables);
 903         if(stage_vars.count(name) || iface_declarations.count(name))
 904                 return false;
 905
 906         VariableDeclaration* iface_var = new VariableDeclaration;
 907         iface_var->sampling = var.sampling;
 908         iface_var->interface = iface;
 909         iface_var->type = var.type;
 910         iface_var->type_declaration = var.type_declaration;
 911         iface_var->name = name;
 912         if(stage->type==GEOMETRY)
 913                 iface_var->array = ((var.array && var.interface!="in") || iface=="in");
 914         else
 915                 iface_var->array = var.array;
 916         if(iface_var->array)
 917                 iface_var->array_size = var.array_size;
 918         if(iface=="in")
 919                 iface_var->linked_declaration = &var;
 920         iface_declarations[name] = iface_var;
 921
 922         return true;
 923 }
 924
 925 void ProgramCompiler::InterfaceGenerator::insert_assignment(const string &left, ProgramSyntax::Expression *right)
 926 {
 927         Assignment *assign = new Assignment;
 928         VariableReference *ref = new VariableReference;
 929         ref->name = left;
 930         assign->left = ref;
 931         assign->oper = "=";
 932         assign->right = right;
 933
 934         ExpressionStatement *stmt = new ExpressionStatement;
 935         stmt->expression = assign;
 936         stmt->visit(*this);
 937         insert_nodes.push_back(stmt);
 938 }
 939
 940 void ProgramCompiler::InterfaceGenerator::visit(VariableReference &var)
 941 {
 942         if(var.declaration || !stage->previous)
 943                 return;
 944         if(iface_declarations.count(var.name))
 945                 return;
 946
 947         const map<string, VariableDeclaration *> &prev_out = stage->previous->out_variables;
 948         map<string, VariableDeclaration *>::const_iterator i = prev_out.find(var.name);
 949         if(i==prev_out.end())
 950                 i = prev_out.find(in_prefix+var.name);
 951         if(i!=prev_out.end())
 952         {
 953                 generate_interface(*i->second, "in", i->second->name);
 954                 var.name = i->second->name;
 955         }
 956 }
 957
 958 void ProgramCompiler::InterfaceGenerator::visit(VariableDeclaration &var)
 959 {
 960         if(var.interface=="out")
 961         {
 962                 if(scope_level==1)
 963                         stage->out_variables[var.name] = &var;
 964                 else if(generate_interface(var, "out", change_prefix(var.name, string())))
 965                 {
 966                         remove_node = true;
 967                         if(var.init_expression)
 968                         {
 969                                 insert_assignment(var.name, var.init_expression->clone());
 970                                 return;
 971                         }
 972                 }
 973         }
 974         else if(var.interface=="in")
 975         {
 976                 stage->in_variables[var.name] = &var;
 977                 if(var.linked_declaration)
 978                         var.linked_declaration->linked_declaration = &var;
 979                 else if(stage->previous)
 980                 {
 981                         const map<string, VariableDeclaration *> &prev_out = stage->previous->out_variables;
 982                         map<string, VariableDeclaration *>::const_iterator i = prev_out.find(var.name);
 983                         if(i!=prev_out.end())
 984                         {
 985                                 var.linked_declaration = i->second;
 986                                 i->second->linked_declaration = &var;
 987                         }
 988                 }
 989         }
 990
 991         TraversingVisitor::visit(var);
 992 }
 993
 994 void ProgramCompiler::InterfaceGenerator::visit(Passthrough &pass)
 995 {
 996         vector<VariableDeclaration *> pass_vars;
 997
 998         for(map<string, VariableDeclaration *>::const_iterator i=stage->in_variables.begin(); i!=stage->in_variables.end(); ++i)
 999                 pass_vars.push_back(i->second);
1000         for(map<string, RefPtr<VariableDeclaration> >::const_iterator i=iface_declarations.begin(); i!=iface_declarations.end(); ++i)
1001                 if(i->second->interface=="in")
1002                         pass_vars.push_back(i->second.get());
1003
1004         if(stage->previous)
1005         {
1006                 const map<string, VariableDeclaration *> &prev_out = stage->previous->out_variables;
1007                 for(map<string, VariableDeclaration *>::const_iterator i=prev_out.begin(); i!=prev_out.end(); ++i)
1008                 {
1009                         bool linked = false;
1010                         for(vector<VariableDeclaration *>::const_iterator j=pass_vars.begin(); (!linked && j!=pass_vars.end()); ++j)
1011                                 linked = ((*j)->linked_declaration==i->second);
1012
1013                         if(!linked && generate_interface(*i->second, "in", i->second->name))
1014                                 pass_vars.push_back(i->second);
1015                 }
1016         }
1017
1018         if(stage->type==GEOMETRY)
1019         {
1020                 VariableReference *ref = new VariableReference;
1021                 ref->name = "gl_in";
1022
1023                 BinaryExpression *subscript = new BinaryExpression;
1024                 subscript->left = ref;
1025                 subscript->oper = "[";
1026                 subscript->right = pass.subscript;
1027                 subscript->after = "]";
1028
1029                 MemberAccess *memacc = new MemberAccess;
1030                 memacc->left = subscript;
1031                 memacc->member = "gl_Position";
1032
1033                 insert_assignment("gl_Position", memacc);
1034         }
1035
1036         for(vector<VariableDeclaration *>::const_iterator i=pass_vars.begin(); i!=pass_vars.end(); ++i)
1037         {
1038                 string out_name = change_prefix((*i)->name, out_prefix);
1039                 generate_interface(**i, "out", out_name);
1040
1041                 VariableReference *ref = new VariableReference;
1042                 ref->name = (*i)->name;
1043                 if(pass.subscript)
1044                 {
1045                         BinaryExpression *subscript = new BinaryExpression;
1046                         subscript->left = ref;
1047                         subscript->oper = "[";
1048                         subscript->right = pass.subscript;
1049                         subscript->after = "]";
1050                         insert_assignment(out_name, subscript);
1051                 }
1052                 else
1053                         insert_assignment(out_name, ref);
1054         }
1055
1056         remove_node = true;
1057 }
1058
1059
1060 ProgramCompiler::DeclarationReorderer::DeclarationReorderer():
1061         scope_level(0),
1062         kind(NO_DECLARATION)
1063 { }
1064
1065 void ProgramCompiler::DeclarationReorderer::visit(FunctionCall &call)
1066 {
1067         FunctionDeclaration *def = call.declaration;
1068         if(def)
1069                 def = def->definition;
1070         if(def && !ordered_funcs.count(def))
1071                 needed_funcs.insert(def);
1072 }
1073
1074 void ProgramCompiler::DeclarationReorderer::visit(Block &block)
1075 {
1076         SetForScope<unsigned> set(scope_level, scope_level+1);
1077         if(scope_level>1)
1078                 return Visitor::visit(block);
1079
1080         NodeList<Statement>::iterator struct_insert_point = block.body.end();
1081         NodeList<Statement>::iterator variable_insert_point = block.body.end();
1082         NodeList<Statement>::iterator function_insert_point = block.body.end();
1083         unsigned unordered_func_count = 0;
1084         bool ordered_any_funcs = false;
1085
1086         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); )
1087         {
1088                 kind = NO_DECLARATION;
1089                 (*i)->visit(*this);
1090
1091                 bool moved = false;
1092                 if(kind==STRUCT && struct_insert_point!=block.body.end())
1093                 {
1094                         block.body.insert(struct_insert_point, *i);
1095                         moved = true;
1096                 }
1097                 else if(kind>STRUCT && struct_insert_point==block.body.end())
1098                         struct_insert_point = i;
1099
1100                 if(kind==VARIABLE && variable_insert_point!=block.body.end())
1101                 {
1102                         block.body.insert(variable_insert_point, *i);
1103                         moved = true;
1104                 }
1105                 else if(kind>VARIABLE && variable_insert_point==block.body.end())
1106                         variable_insert_point = i;
1107
1108                 if(kind==FUNCTION)
1109                 {
1110                         if(function_insert_point==block.body.end())
1111                                 function_insert_point = i;
1112
1113                         if(needed_funcs.empty())
1114                         {
1115                                 ordered_funcs.insert(i->get());
1116                                 if(i!=function_insert_point)
1117                                 {
1118                                         block.body.insert(function_insert_point, *i);
1119                                         moved = true;
1120                                 }
1121                                 else
1122                                         ++function_insert_point;
1123                                 ordered_any_funcs = true;
1124                         }
1125                         else
1126                                 ++unordered_func_count;
1127                 }
1128
1129                 if(moved)
1130                 {
1131                         if(function_insert_point==i)
1132                                 ++function_insert_point;
1133                         block.body.erase(i++);
1134                 }
1135                 else
1136                         ++i;
1137
1138                 if(i==block.body.end() && unordered_func_count)
1139                 {
1140                         if(!ordered_any_funcs)
1141                                 // A subset of the remaining functions forms a recursive loop
1142                                 /* TODO pick a function and move it up, adding any necessary
1143                                 declarations */
1144                                 break;
1145
1146                         i = function_insert_point;
1147                         unordered_func_count = 0;
1148                 }
1149         }
1150 }
1151
1152 void ProgramCompiler::DeclarationReorderer::visit(ProgramSyntax::VariableDeclaration &var)
1153 {
1154         Visitor::visit(var);
1155         kind = VARIABLE;
1156 }
1157
1158 void ProgramCompiler::DeclarationReorderer::visit(FunctionDeclaration &func)
1159 {
1160         needed_funcs.clear();
1161         func.body.visit(*this);
1162         needed_funcs.erase(&func);
1163         kind = FUNCTION;
1164 }
1165
1166
1167 ProgramCompiler::InlineableFunctionLocator::InlineableFunctionLocator():
1168         in_function(0)
1169 { }
1170
1171 void ProgramCompiler::InlineableFunctionLocator::visit(FunctionCall &call)
1172 {
1173         FunctionDeclaration *def = call.declaration;
1174         if(def && def->definition!=def)
1175                 def = def->definition;
1176
1177         if(def)
1178         {
1179                 unsigned &count = refcounts[def];
1180                 ++count;
1181                 if(count>1 || def==in_function)
1182                         inlineable.erase(def);
1183         }
1184
1185         TraversingVisitor::visit(call);
1186 }
1187
1188 void ProgramCompiler::InlineableFunctionLocator::visit(FunctionDeclaration &func)
1189 {
1190         unsigned &count = refcounts[func.definition];
1191         if(!count && func.parameters.empty())
1192                 inlineable.insert(func.definition);
1193
1194         SetForScope<FunctionDeclaration *> set(in_function, &func);
1195         TraversingVisitor::visit(func);
1196 }
1197
1198
1199 ProgramCompiler::FunctionInliner::FunctionInliner():
1200         extract_result(0)
1201 { }
1202
1203 ProgramCompiler::FunctionInliner::FunctionInliner(const set<FunctionDeclaration *> &in):
1204         inlineable(in),
1205         extract_result(0)
1206 { }
1207
1208 void ProgramCompiler::FunctionInliner::visit_and_inline(RefPtr<Expression> &ptr)
1209 {
1210         inline_result = 0;
1211         ptr->visit(*this);
1212         if(inline_result)
1213                 ptr = inline_result;
1214 }
1215
1216 void ProgramCompiler::FunctionInliner::visit(Block &block)
1217 {
1218         if(extract_result)
1219                 --extract_result;
1220
1221         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
1222         {
1223                 (*i)->visit(*this);
1224                 if(extract_result)
1225                         --extract_result;
1226         }
1227 }
1228
1229 void ProgramCompiler::FunctionInliner::visit(UnaryExpression &unary)
1230 {
1231         visit_and_inline(unary.expression);
1232         inline_result = 0;
1233 }
1234
1235 void ProgramCompiler::FunctionInliner::visit(BinaryExpression &binary)
1236 {
1237         visit_and_inline(binary.left);
1238         visit_and_inline(binary.right);
1239         inline_result = 0;
1240 }
1241
1242 void ProgramCompiler::FunctionInliner::visit(MemberAccess &memacc)
1243 {
1244         visit_and_inline(memacc.left);
1245         inline_result = 0;
1246 }
1247
1248 void ProgramCompiler::FunctionInliner::visit(FunctionCall &call)
1249 {
1250         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
1251                 visit_and_inline(*i);
1252
1253         FunctionDeclaration *def = call.declaration;
1254         if(def && def->definition!=def)
1255                 def = def->definition;
1256
1257         if(def && inlineable.count(def))
1258         {
1259                 extract_result = 2;
1260                 def->visit(*this);
1261         }
1262         else
1263                 inline_result = 0;
1264 }
1265
1266 void ProgramCompiler::FunctionInliner::visit(VariableDeclaration &var)
1267 {
1268         if(var.init_expression)
1269                 visit_and_inline(var.init_expression);
1270         inline_result = 0;
1271 }
1272
1273 void ProgramCompiler::FunctionInliner::visit(Return &ret)
1274 {
1275         TraversingVisitor::visit(ret);
1276
1277         if(extract_result)
1278                 inline_result = ret.expression->clone();
1279 }
1280
1281
1282 ProgramCompiler::ExpressionEvaluator::ExpressionEvaluator():
1283         variable_values(0),
1284         result(0.0f),
1285         result_valid(false)
1286 { }
1287
1288 ProgramCompiler::ExpressionEvaluator::ExpressionEvaluator(const ValueMap &v):
1289         variable_values(&v),
1290         result(0.0f),
1291         result_valid(false)
1292 { }
1293
1294 void ProgramCompiler::ExpressionEvaluator::visit(Literal &literal)
1295 {
1296         if(literal.token=="true")
1297                 result = 1.0f;
1298         else if(literal.token=="false")
1299                 result = 0.0f;
1300         else
1301                 result = lexical_cast<float>(literal.token);
1302         result_valid = true;
1303 }
1304
1305 void ProgramCompiler::ExpressionEvaluator::visit(ParenthesizedExpression &parexp)
1306 {
1307         parexp.expression->visit(*this);
1308 }
1309
1310 void ProgramCompiler::ExpressionEvaluator::visit(VariableReference &var)
1311 {
1312         if(!var.declaration)
1313                 return;
1314
1315         if(variable_values)
1316         {
1317                 ValueMap::const_iterator i = variable_values->find(var.declaration);
1318                 if(i!=variable_values->end())
1319                         i->second->visit(*this);
1320         }
1321         else if(var.declaration->init_expression)
1322                 var.declaration->init_expression->visit(*this);
1323 }
1324
1325 void ProgramCompiler::ExpressionEvaluator::visit(UnaryExpression &unary)
1326 {
1327         result_valid = false;
1328         unary.expression->visit(*this);
1329         if(!result_valid)
1330                 return;
1331
1332         if(unary.oper=="!")
1333                 result = !result;
1334         else
1335                 result_valid = false;
1336 }
1337
1338 void ProgramCompiler::ExpressionEvaluator::visit(BinaryExpression &binary)
1339 {
1340         result_valid = false;
1341         binary.left->visit(*this);
1342         if(!result_valid)
1343                 return;
1344
1345         float left_result = result;
1346         result_valid = false;
1347         binary.right->visit(*this);
1348         if(!result_valid)
1349                 return;
1350
1351         if(binary.oper=="<")
1352                 result = (left_result<result);
1353         else if(binary.oper=="<=")
1354                 result = (left_result<=result);
1355         else if(binary.oper==">")
1356                 result = (left_result>result);
1357         else if(binary.oper==">=")
1358                 result = (left_result>=result);
1359         else if(binary.oper=="==")
1360                 result = (left_result==result);
1361         else if(binary.oper=="!=")
1362                 result = (left_result!=result);
1363         else if(binary.oper=="&&")
1364                 result = (left_result && result);
1365         else if(binary.oper=="||")
1366                 result = (left_result || result);
1367         else
1368                 result_valid = false;
1369 }
1370
1371
1372 ProgramCompiler::ConstantConditionEliminator::ConstantConditionEliminator():
1373         scope_level(0),
1374         record_only(false)
1375 { }
1376
1377 void ProgramCompiler::ConstantConditionEliminator::visit(Block &block)
1378 {
1379         SetForScope<unsigned> set(scope_level, scope_level+1);
1380         BlockModifier::visit(block);
1381
1382         for(map<string, VariableDeclaration *>::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
1383                 variable_values.erase(i->second);
1384 }
1385
1386 void ProgramCompiler::ConstantConditionEliminator::visit(UnaryExpression &unary)
1387 {
1388         if(VariableReference *var = dynamic_cast<VariableReference *>(unary.expression.get()))
1389                 if(unary.oper=="++" || unary.oper=="--")
1390                         variable_values.erase(var->declaration);
1391 }
1392
1393 void ProgramCompiler::ConstantConditionEliminator::visit(Assignment &assign)
1394 {
1395         variable_values.erase(assign.target_declaration);
1396 }
1397
1398 void ProgramCompiler::ConstantConditionEliminator::visit(VariableDeclaration &var)
1399 {
1400         if(var.constant || scope_level>1)
1401                 variable_values[&var] = var.init_expression.get();
1402 }
1403
1404 void ProgramCompiler::ConstantConditionEliminator::visit(Conditional &cond)
1405 {
1406         if(!record_only)
1407         {
1408                 ExpressionEvaluator eval(variable_values);
1409                 cond.condition->visit(eval);
1410                 if(eval.result_valid)
1411                 {
1412                         flatten_block(eval.result ? cond.body : cond.else_body);
1413                         return;
1414                 }
1415         }
1416
1417         TraversingVisitor::visit(cond);
1418 }
1419
1420 void ProgramCompiler::ConstantConditionEliminator::visit(Iteration &iter)
1421 {
1422         if(!record_only)
1423         {
1424                 if(iter.condition)
1425                 {
1426                         /* If the loop condition is always false on the first iteration, the
1427                         entire loop can be removed */
1428                         if(iter.init_statement)
1429                                 iter.init_statement->visit(*this);
1430                         ExpressionEvaluator eval(variable_values);
1431                         iter.condition->visit(eval);
1432                         if(eval.result_valid && !eval.result)
1433                         {
1434                                 remove_node = true;
1435                                 return;
1436                         }
1437                 }
1438
1439                 /* Record all assignments that occur inside the loop body so those
1440                 variables won't be considered as constant */
1441                 SetFlag set_record(record_only);
1442                 TraversingVisitor::visit(iter);
1443         }
1444
1445         TraversingVisitor::visit(iter);
1446
1447         if(VariableDeclaration *init_decl = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
1448                 variable_values.erase(init_decl);
1449 }
1450
1451
1452 ProgramCompiler::UnusedVariableLocator::UnusedVariableLocator():
1453         aggregate(0),
1454         assignment(0),
1455         assignment_target(false),
1456         assign_to_subscript(false),
1457         global_scope(true)
1458 { }
1459
1460 void ProgramCompiler::UnusedVariableLocator::apply(Stage &s)
1461 {
1462         variables.push_back(BlockVariableMap());
1463         Visitor::apply(s);
1464         BlockVariableMap &global_variables = variables.back();
1465         for(BlockVariableMap::iterator i=global_variables.begin(); i!=global_variables.end(); ++i)
1466         {
1467                 if(i->first->interface=="out" && (s.type==FRAGMENT || i->first->linked_declaration || !i->first->name.compare(0, 3, "gl_")))
1468                         continue;
1469                 if(!i->second.referenced)
1470                 {
1471                         unused_nodes.insert(i->first);
1472                         clear_assignments(i->second, true);
1473                 }
1474         }
1475         variables.pop_back();
1476 }
1477
1478 void ProgramCompiler::UnusedVariableLocator::visit(VariableReference &var)
1479 {
1480         map<VariableDeclaration *, Node *>::iterator i = aggregates.find(var.declaration);
1481         if(i!=aggregates.end())
1482                 unused_nodes.erase(i->second);
1483
1484         if(var.declaration && !assignment_target)
1485         {
1486                 VariableInfo &var_info = variables.back()[var.declaration];
1487                 var_info.assignments.clear();
1488                 var_info.referenced = true;
1489         }
1490 }
1491
1492 void ProgramCompiler::UnusedVariableLocator::visit(MemberAccess &memacc)
1493 {
1494         TraversingVisitor::visit(memacc);
1495         unused_nodes.erase(memacc.declaration);
1496 }
1497
1498 void ProgramCompiler::UnusedVariableLocator::visit(BinaryExpression &binary)
1499 {
1500         if(binary.oper=="[")
1501         {
1502                 if(assignment_target)
1503                         assign_to_subscript = true;
1504                 binary.left->visit(*this);
1505                 SetForScope<bool> set(assignment_target, false);
1506                 binary.right->visit(*this);
1507         }
1508         else
1509                 TraversingVisitor::visit(binary);
1510 }
1511
1512 void ProgramCompiler::UnusedVariableLocator::visit(Assignment &assign)
1513 {
1514         {
1515                 assign_to_subscript = false;
1516                 SetForScope<bool> set(assignment_target, !assign.self_referencing);
1517                 assign.left->visit(*this);
1518         }
1519         assign.right->visit(*this);
1520         assignment = &assign;
1521 }
1522
1523 void ProgramCompiler::UnusedVariableLocator::record_assignment(VariableDeclaration &var, Node &node, bool chained)
1524 {
1525         VariableInfo &var_info = variables.back()[&var];
1526         if(!chained)
1527                 clear_assignments(var_info, true);
1528         var_info.assignments.push_back(&node);
1529         var_info.conditionally_assigned = false;
1530 }
1531
1532 void ProgramCompiler::UnusedVariableLocator::clear_assignments(VariableInfo &var_info, bool mark_unused)
1533 {
1534         if(mark_unused)
1535         {
1536                 for(vector<Node *>::iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
1537                         unused_nodes.insert(*i);
1538         }
1539         var_info.assignments.clear();
1540 }
1541
1542 void ProgramCompiler::UnusedVariableLocator::visit(ExpressionStatement &expr)
1543 {
1544         assignment = 0;
1545         TraversingVisitor::visit(expr);
1546         if(assignment && assignment->target_declaration)
1547                 record_assignment(*assignment->target_declaration, expr, (assignment->self_referencing || assign_to_subscript));
1548 }
1549
1550 void ProgramCompiler::UnusedVariableLocator::visit(StructDeclaration &strct)
1551 {
1552         SetForScope<Node *> set(aggregate, &strct);
1553         unused_nodes.insert(&strct);
1554         TraversingVisitor::visit(strct);
1555 }
1556
1557 void ProgramCompiler::UnusedVariableLocator::visit(VariableDeclaration &var)
1558 {
1559         if(aggregate)
1560                 aggregates[&var] = aggregate;
1561         else
1562         {
1563                 variables.back()[&var].local = true;
1564                 if(var.init_expression)
1565                         record_assignment(var, *var.init_expression, false);
1566         }
1567         unused_nodes.erase(var.type_declaration);
1568         TraversingVisitor::visit(var);
1569 }
1570
1571 void ProgramCompiler::UnusedVariableLocator::visit(InterfaceBlock &iface)
1572 {
1573         SetForScope<Node *> set(aggregate, &iface);
1574         unused_nodes.insert(&iface);
1575         TraversingVisitor::visit(iface);
1576 }
1577
1578 void ProgramCompiler::UnusedVariableLocator::visit(FunctionDeclaration &func)
1579 {
1580         variables.push_back(BlockVariableMap());
1581
1582         {
1583                 SetForScope<bool> set(global_scope, false);
1584                 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1585                         (*i)->visit(*this);
1586                 func.body.visit(*this);
1587         }
1588
1589         BlockVariableMap &block_variables = variables.back();
1590         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
1591                 i->second.conditionally_assigned = true;
1592         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
1593                 block_variables[i->get()].referenced = true;
1594         merge_down_variables();
1595 }
1596
1597 void ProgramCompiler::UnusedVariableLocator::merge_down_variables()
1598 {
1599         BlockVariableMap &parent_variables = variables[variables.size()-2];
1600         BlockVariableMap &block_variables = variables.back();
1601         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
1602         {
1603                 if(i->second.local)
1604                 {
1605                         if(!i->second.referenced)
1606                                 unused_nodes.insert(i->first);
1607                         clear_assignments(i->second, true);
1608                         continue;
1609                 }
1610
1611                 BlockVariableMap::iterator j = parent_variables.find(i->first);
1612                 if(j==parent_variables.end())
1613                         parent_variables.insert(*i);
1614                 else
1615                 {
1616                         if(i->second.referenced || !i->second.conditionally_assigned)
1617                                 clear_assignments(j->second, !i->second.referenced);
1618                         j->second.conditionally_assigned = i->second.conditionally_assigned;
1619                         j->second.referenced |= i->second.referenced;
1620                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end());
1621                 }
1622         }
1623         variables.pop_back();
1624 }
1625
1626 void ProgramCompiler::UnusedVariableLocator::visit(Conditional &cond)
1627 {
1628         cond.condition->visit(*this);
1629         variables.push_back(BlockVariableMap());
1630         cond.body.visit(*this);
1631
1632         BlockVariableMap if_variables;
1633         swap(variables.back(), if_variables);
1634         cond.else_body.visit(*this);
1635
1636         BlockVariableMap &else_variables = variables.back();
1637         for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i)
1638         {
1639                 BlockVariableMap::iterator j = if_variables.find(i->first);
1640                 if(j!=if_variables.end())
1641                 {
1642                         i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end());
1643                         i->second.conditionally_assigned |= j->second.conditionally_assigned;
1644                         if_variables.erase(j);
1645                 }
1646                 else
1647                         i->second.conditionally_assigned = true;
1648         }
1649
1650         for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i)
1651         {
1652                 i->second.conditionally_assigned = true;
1653                 else_variables.insert(*i);
1654         }
1655
1656         merge_down_variables();
1657 }
1658
1659 void ProgramCompiler::UnusedVariableLocator::visit(Iteration &iter)
1660 {
1661         variables.push_back(BlockVariableMap());
1662         TraversingVisitor::visit(iter);
1663
1664         BlockVariableMap &block_variables = variables.back();
1665         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
1666                 if(!i->second.local && i->second.referenced)
1667                         i->second.assignments.clear();
1668
1669         merge_down_variables();
1670 }
1671
1672
1673 ProgramCompiler::UnusedVariableLocator::VariableInfo::VariableInfo():
1674         local(false),
1675         conditionally_assigned(false),
1676         referenced(false)
1677 { }
1678
1679
1680 void ProgramCompiler::UnusedFunctionLocator::visit(FunctionCall &call)
1681 {
1682         TraversingVisitor::visit(call);
1683
1684         unused_nodes.erase(call.declaration);
1685         if(call.declaration && call.declaration->definition!=call.declaration)
1686                 used_definitions.insert(call.declaration->definition);
1687 }
1688
1689 void ProgramCompiler::UnusedFunctionLocator::visit(FunctionDeclaration &func)
1690 {
1691         TraversingVisitor::visit(func);
1692
1693         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
1694                 unused_nodes.insert(&func);
1695 }
1696
1697
1698 ProgramCompiler::NodeRemover::NodeRemover(const set<Node *> &r):
1699         to_remove(r)
1700 { }
1701
1702 void ProgramCompiler::NodeRemover::visit(Block &block)
1703 {
1704         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); )
1705         {
1706                 (*i)->visit(*this);
1707                 if(to_remove.count(i->get()))
1708                         block.body.erase(i++);
1709                 else
1710                         ++i;
1711         }
1712 }
1713
1714 void ProgramCompiler::NodeRemover::visit(VariableDeclaration &var)
1715 {
1716         if(to_remove.count(&var))
1717         {
1718                 stage->in_variables.erase(var.name);
1719                 stage->out_variables.erase(var.name);
1720                 stage->locations.erase(var.name);
1721                 if(var.linked_declaration)
1722                         var.linked_declaration->linked_declaration = 0;
1723         }
1724         else if(var.init_expression && to_remove.count(var.init_expression.get()))
1725                 var.init_expression = 0;
1726 }
1727
1728 void ProgramCompiler::NodeRemover::visit(Iteration &iter)
1729 {
1730         if(to_remove.count(iter.init_statement.get()))
1731                 iter.init_statement = 0;
1732         TraversingVisitor::visit(iter);
1733 }
1734
1735
1736 void ProgramCompiler::PrecisionRemover::visit(Precision &)
1737 {
1738         remove_node = true;
1739 }
1740
1741 void ProgramCompiler::PrecisionRemover::visit(VariableDeclaration &var)
1742 {
1743         var.precision.clear();
1744 }
1745
1746
1747 ProgramCompiler::DefaultPrecisionGenerator::DefaultPrecisionGenerator():
1748         toplevel(true)
1749 { }
1750
1751 void ProgramCompiler::DefaultPrecisionGenerator::visit(Block &block)
1752 {
1753         if(toplevel)
1754         {
1755                 SetForScope<bool> set(toplevel, false);
1756                 BlockModifier::visit(block);
1757         }
1758         else
1759                 Visitor::visit(block);
1760 }
1761
1762 void ProgramCompiler::DefaultPrecisionGenerator::visit(Precision &prec)
1763 {
1764         have_default.insert(prec.type);
1765 }
1766
1767 void ProgramCompiler::DefaultPrecisionGenerator::visit(VariableDeclaration &var)
1768 {
1769         if(var.type_declaration)
1770                 return;
1771
1772         string type = var.type;
1773         if(!type.compare(0, 3, "vec") || !type.compare(0, 3, "mat"))
1774                 type = "float";
1775         else if(!type.compare(0, 3, "ivec") || type=="uint")
1776                 type = "int";
1777
1778         if(!have_default.count(type))
1779         {
1780                 Precision *prec = new Precision;
1781                 if(!type.compare(0, 7, "sampler"))
1782                         prec->precision = "lowp";
1783                 else if(stage->type==FRAGMENT)
1784                         prec->precision = "mediump";
1785                 else
1786                         prec->precision = "highp";
1787                 prec->type = type;
1788                 insert_nodes.push_back(prec);
1789
1790                 have_default.insert(type);
1791         }
1792 }
1793
1794
1795 ProgramCompiler::LegacyConverter::LegacyConverter():
1796         target_api(get_gl_api()),
1797         target_version(get_glsl_version()),
1798         frag_out(0)
1799 { }
1800
1801 ProgramCompiler::LegacyConverter::LegacyConverter(const Version &v):
1802         target_api(get_gl_api()),
1803         target_version(v),
1804         frag_out(0)
1805 { }
1806
1807 bool ProgramCompiler::LegacyConverter::check_version(const Version &feature_version) const
1808 {
1809         if(target_version<feature_version)
1810                 return false;
1811         else if(stage->required_version<feature_version)
1812                 stage->required_version = feature_version;
1813
1814         return true;
1815 }
1816
1817 bool ProgramCompiler::LegacyConverter::check_extension(const Extension &extension) const
1818 {
1819         if(!extension)
1820                 return false;
1821
1822         vector<const Extension *>::iterator i = find(stage->required_extensions, &extension);
1823         if(i==stage->required_extensions.end())
1824                 stage->required_extensions.push_back(&extension);
1825
1826         return true;
1827 }
1828
1829 bool ProgramCompiler::LegacyConverter::supports_unified_interface_syntax() const
1830 {
1831         if(target_api==OPENGL_ES2)
1832                 return check_version(Version(3, 0));
1833         else
1834                 return check_version(Version(1, 30));
1835 }
1836
1837 void ProgramCompiler::LegacyConverter::visit(VariableReference &var)
1838 {
1839         if(var.declaration==frag_out && !supports_unified_interface_syntax())
1840         {
1841                 var.name = "gl_FragColor";
1842                 var.declaration = 0;
1843                 type = "vec4";
1844         }
1845         else if(var.declaration)
1846                 type = var.declaration->type;
1847         else
1848                 type = string();
1849 }
1850
1851 void ProgramCompiler::LegacyConverter::visit(Assignment &assign)
1852 {
1853         TraversingVisitor::visit(assign);
1854         if(assign.target_declaration==frag_out && !supports_unified_interface_syntax())
1855                 assign.target_declaration = 0;
1856 }
1857
1858 bool ProgramCompiler::LegacyConverter::supports_unified_sampling_functions() const
1859 {
1860         if(target_api==OPENGL_ES2)
1861                 return check_version(Version(3, 0));
1862         else
1863                 return check_version(Version(1, 30));
1864 }
1865
1866 void ProgramCompiler::LegacyConverter::visit(FunctionCall &call)
1867 {
1868         if(call.name=="texture" && !call.declaration && !supports_unified_sampling_functions())
1869         {
1870                 NodeArray<Expression>::iterator i = call.arguments.begin();
1871                 if(i!=call.arguments.end())
1872                 {
1873                         (*i)->visit(*this);
1874                         if(type=="sampler1D")
1875                                 call.name = "texture1D";
1876                         else if(type=="sampler2D")
1877                                 call.name = "texture2D";
1878                         else if(type=="sampler3D")
1879                                 call.name = "texture3D";
1880                         else if(type=="sampler1DShadow")
1881                                 call.name = "shadow1D";
1882                         else if(type=="sampler2DShadow")
1883                                 call.name = "shadow2D";
1884
1885                         for(; i!=call.arguments.end(); ++i)
1886                                 (*i)->visit(*this);
1887                 }
1888         }
1889         else
1890                 TraversingVisitor::visit(call);
1891 }
1892
1893 bool ProgramCompiler::LegacyConverter::supports_interface_layouts() const
1894 {
1895         if(target_api==OPENGL_ES2)
1896                 return check_version(Version(3, 0));
1897         else if(check_version(Version(3, 30)))
1898                 return true;
1899         else
1900                 return check_extension(ARB_explicit_attrib_location);
1901 }
1902
1903 bool ProgramCompiler::LegacyConverter::supports_centroid_sampling() const
1904 {
1905         if(target_api==OPENGL_ES2)
1906                 return check_version(Version(3, 0));
1907         else if(check_version(Version(1, 20)))
1908                 return true;
1909         else
1910                 return check_extension(EXT_gpu_shader4);
1911 }
1912
1913 bool ProgramCompiler::LegacyConverter::supports_sample_sampling() const
1914 {
1915         if(target_api==OPENGL_ES2)
1916                 return check_version(Version(3, 20));
1917         else if(check_version(Version(4, 0)))
1918                 return true;
1919         else
1920                 return check_extension(ARB_gpu_shader5);
1921 }
1922
1923 void ProgramCompiler::LegacyConverter::visit(VariableDeclaration &var)
1924 {
1925         if(var.layout && !supports_interface_layouts())
1926         {
1927                 vector<Layout::Qualifier>::iterator i;
1928                 for(i=var.layout->qualifiers.begin(); (i!=var.layout->qualifiers.end() && i->identifier!="location"); ++i) ;
1929                 if(i!=var.layout->qualifiers.end())
1930                 {
1931                         unsigned location = lexical_cast<unsigned>(i->value);
1932                         if(stage->type==VERTEX && var.interface=="in")
1933                         {
1934                                 stage->locations[var.name] = location;
1935                                 var.layout->qualifiers.erase(i);
1936                         }
1937                         else if(stage->type==FRAGMENT && var.interface=="out")
1938                         {
1939                                 if(location!=0)
1940                                         static Require _req(EXT_gpu_shader4);
1941                                 stage->locations[var.name] = location;
1942                                 var.layout->qualifiers.erase(i);
1943                         }
1944
1945                         if(var.layout->qualifiers.empty())
1946                                 var.layout = 0;
1947                 }
1948         }
1949
1950         if(var.sampling=="centroid")
1951         {
1952                 if(!supports_centroid_sampling())
1953                         var.sampling = string();
1954         }
1955         else if(var.sampling=="sample")
1956         {
1957                 if(!supports_sample_sampling())
1958                         var.sampling = string();
1959         }
1960
1961         if((var.interface=="in" || var.interface=="out") && !supports_unified_interface_syntax())
1962         {
1963                 if(stage->type==FRAGMENT && var.interface=="out")
1964                 {
1965                         frag_out = &var;
1966                         remove_node = true;
1967                 }
1968         }
1969
1970         TraversingVisitor::visit(var);
1971 }
1972
1973 bool ProgramCompiler::LegacyConverter::supports_interface_blocks(const string &iface) const
1974 {
1975         if(target_api==OPENGL_ES2)
1976         {
1977                 if(iface=="uniform")
1978                         return check_version(Version(3, 0));
1979                 else
1980                         return check_version(Version(3, 20));
1981         }
1982         else if(check_version(Version(1, 50)))
1983                 return true;
1984         else if(iface=="uniform")
1985                 return check_extension(ARB_uniform_buffer_object);
1986         else
1987                 return false;
1988 }
1989
1990 void ProgramCompiler::LegacyConverter::visit(InterfaceBlock &iface)
1991 {
1992         if(!supports_interface_blocks(iface.interface))
1993                 flatten_block(iface.members);
1994 }
1995
1996 } // namespace GL
1997 } // namespace Msp