/* vim: set ts=4 sw=4 tw=99 et:

  *

  * Copyright (C) 2012 David Anderson

  *

  * This file is part of JITCraft.

  *

  * JITCraft is free software: you can redistribute it and/or modify it under

  * the terms of the GNU General Public License as published by the Free

  * Software Foundation, either version 3 of the License, or (at your option)

  * any later version.

  * 

  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY

  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

  *

  * You should have received a copy of the GNU General Public License along with

  * JITCraft. If not, see http://www.gnu.org/licenses/.

  */

 #include "BytecodeCompiler.h"

 #include "Scopes.h"

 #include "Modules.h"

 #include "Types.h"

 #include "Array.h"

 #include "Strings.h"

 #include "Zone.h"

 #include "Heap-inl.h"

 using namespace ke;

 typedef BytecodeEmitter::Label Label;

 #define __ emitter_.

 BytecodeCompiler::BytecodeCompiler(Zone *zone, ParseTree *tree, Module *module)

   : zone_(zone),

     tree_(tree),

     emitter_(zone->pool()),

     module_(module),

     locals_(NULL),

     scope_(NULL),

     loop_(NULL)

 {

 }

 static inline TokenKind

 ToCompare(Expression *expr)

 {

     if (expr->isBinaryExpression()) {

         BinaryExpression *b = expr->toBinaryExpression();

         if (b->token() >= TOK_EQUALS && b->token() <= TOK_GE)

             return b->token();

     }

     return TOK_EOF;

 }

 static inline Opcode

 CompareTokenToJump(TokenKind kind)

 {

     switch (kind) {

       case TOK_EQUALS:

         return OP_JEQ;

       case TOK_NOTEQUALS:

         return OP_JNE;

       case TOK_GT:

         return OP_JG;

       case TOK_GE:

         return OP_JGE;

       case TOK_LT:

         return OP_JL;

       default:

         assert(kind == TOK_LE);

         return OP_JLE;

     }

 }

 static inline Opcode

 TokenToOpcode(TokenKind kind)

 {

     switch (kind) {

       case TOK_PLUS:

         return OP_ADD;

       case TOK_MINUS:

         return OP_SUB;

       case TOK_STAR:

         return OP_MUL;

       case TOK_SLASH:

         return OP_DIV;

       case TOK_SHR:

         return OP_SHR;

       case TOK_USHR:

         return OP_USHR;

       case TOK_SHL:

         return OP_SHL;

       case TOK_BITAND:

         return OP_BITAND;

       case TOK_BITOR:

         return OP_BITOR;

       default:

         assert(kind == TOK_BITXOR);

         return OP_BITXOR;

     }

 }

 void

 BytecodeCompiler::recordLifoSlot(Scope *scope)

 {

     if (!scope)

         return;

     if (Variable *var = scope->lifoSlot()) {

         locals_->set(zone_, var->slot(), var->type());

         __ savelifo(var->slot());

     }

 }

 void

 BytecodeCompiler::unwindTo(Scope *scope)

 {

     // Note: we only need to unwind to the outermost scope's LIFO slot.

     Variable *var = NULL;

     for (Scope *current = scope_; current != scope; current = current->enclosing()) {

         if (Variable *slot = current->lifoSlot())

             var = slot;

     }

     if (var)

         __ unwindlifo(var->slot());

 }

 void

 BytecodeCompiler::visit(NameProxy *name)

 {

     switch (name->binding()->kind()) {

       case BoundName::VARIABLE:

       {

         Variable *var = name->binding()->toVariable();

         if (var->location() == Variable::STACK) {

             __ getlocal(var);

             assert(!name->type()->isReference());

         } else {

             assert(var->location() == Variable::PARAMETER);

             __ getarg(var);

             // If this argument is actually a reference, dereference it now.

             if (var->type()->isReference())

                 __ getref(var->type()->contained()->primitive());

         }

         break;

       }

       default:

       {

         NamedConstant *constant = name->binding()->toNamedConstant();

         __ int_(constant->value().toInt());

         break;

       }

     }

 }

 void

 BytecodeCompiler::visit(ExpressionStatement *node)

 {

     // Expressions leave their value on the top of the stack, so we make sure

     // to balance the stack if they're used as a statement.

     node->expression()->accept(this);

     __ pop();

 }

 void

 BytecodeCompiler::visit(Assignment *node)

 {

     // The first step is three sub-steps:

     //

     //   (1) Bind the left-hand side.

     //   -- If a cumulative operation (+=, etc):

     //   (2) Save a copy of the binding on the stack.

     //   (3) Dereference the binding to get a value.

     //

     if (node->lvalue()->isNameProxy()) {

         NameProxy *proxy = node->lvalue()->toNameProxy();

         Variable *var = proxy->binding()->toVariable();

         // Bind.

         if (var->type()->isReference() || var->type()->isArray())

             __ get(var);

         // Get the value if needed.

         if (node->token() != TOK_ASSIGN) {

             // += etc is not allowed on arrays.

             assert(!var->type()->isArray());

             if (var->type()->isReference()) {

                 __ dup();

                 __ getref(var->type()->contained()->primitive());

             } else {

                 __ get(var);

             }

         }

     } else {

         IndexExpression *index = node->lvalue()->toIndexExpression();

         // Note: Eventually, watch out for a whole here. An expression like:

         //

         //   (a[4] = (5, a = []))

         //

         // Could shrink array, so we need to either bind a[i] to a Reference,

         // or keep the bounds check near the set. This is just a semantic

         // decision.

         index->left()->accept(this);

         index->right()->accept(this);

         if (node->token() != TOK_ASSIGN) {

             __ dup2();

             __ bounds();

             if (node->type()->isArray())

                 __ getarray_o();

             else

                 __ getarray(node->type()->primitive());

         }

     }

     if (node->token() == TOK_ASSIGN) {

         node->expression()->accept(this);

     } else {

         visitForALU(node->type(), node->expression());

         TokenKind alu = TokenKind(int(node->token()) - (TOK_ASSIGN_ADD - TOK_PLUS));

         __ binary(TokenToOpcode(alu));

     }

     // Emit the store.

     if (node->expression()->type()->isArray()) {

         // Unlike references, which can only be computed from a NamePRoxy,

         // arrays can be computed from multiple lvalue types.

         __ arraycopy();

     } else if (node->lvalue()->isNameProxy()) {

         NameProxy *proxy = node->lvalue()->toNameProxy();

         Variable *var = proxy->binding()->toVariable();

         if (var->type()->isReference())

             __ setref(var->type()->contained()->primitive());

         else

             __ set(var);

     } else {

         IndexExpression *index = node->lvalue()->toIndexExpression();

         // :TODO: get rid of the BOUNDS instruction, embed it in g/setarray*?

         // We can't emit it here because the stack is slightly out of position.

         // __ bounds();

         __ setarray(index->left()->type()->contained()->primitive());

     }

 }

 void

 BytecodeCompiler::visit(IncDecExpression *node)

 {

     // In the postfix case, the logic looks like:

     //      (1) Bind       -> REF

     //      (2) Dup        -> REF REF

     //      (3) Fetch      -> REF VAL

     //      (4) Swap       -> VAL REF

     //      (5) Pick       -> VAL REF VAL

     //      (6) Add        -> VAL REF VAL+1

     //      (7) Store      -> VAL VAL+1

     //      (8) Drop       -> VAL

     //

     // In the prefix case, the logic looks like:

     //      (1) Bind       -> REF

     //      (2) Dup        -> REF REF

     //      (3) Fetch      -> REF VAL

     //      --

     //      --

     //      (6) Add        -> REF VAL+1

     //      (7) Store      -> VAL+1

     //      --

     //

     // This is squirrely enough such that we don't bother sharing too much

     // with the above.

     // 

     // Note: We simulate a "Pick" operation with a dup2+pop.

     // This is steps (1) to (5).

     Expression *expr = node->expression();

     if (expr->isNameProxy()) {

         NameProxy *proxy = expr->toNameProxy();

         Variable *var = proxy->binding()->toVariable();

         // Bind.

         if (var->type()->isReference() || var->type()->isArray())

             __ get(var);

         // Dup and fetch.

         if (var->type()->isReference()) {

             __ dup();

             __ getref(node->type()->primitive());

             if (node->postfix()) {

                 __ swap();

                 __ pick2();

             }

         } else {

             assert(!var->type()->isArray());

             __ get(var);

             if (node->postfix())

                 __ dup();

         }

     } else {

         IndexExpression *index = expr->toIndexExpression();

         index->left()->accept(this);

         index->right()->accept(this);

         assert(!node->type()->isArray());

         __ bounds();

         __ dup2();

         __ getarray(node->type()->primitive());

         if (node->postfix()) {

             // The stack looks like this now:

             // ARRAY INDEX VALUE

             //

             // So we must use a PICK operation to rotate the stack into position.

             __ roll3();         // INDEX VALUE ARRAY

             __ roll3();         // VALUE ARRAY INDEX

             __ pick3();         // VALUE ARRAY INDEX VALUE

         }

     }

     // Perform step (6).

     if (node->type()->isFloat()) {

         __ float_(1.0);

     } else {

         assert(node->type()->isInt32());

         __ int_(1);

     }

     if (node->token() == TOK_INCREMENT)

         __ binary(OP_ADD);

     else

         __ binary(OP_SUB);

     // Perform step (7).

     if (expr->isNameProxy()) {

         NameProxy *proxy = expr->toNameProxy();

         Variable *var = proxy->binding()->toVariable();

         if (var->type()->isReference())

             __ setref(node->type()->primitive());

         else

             __ set(var);

     } else {

         __ setarray(node->type()->primitive());

     }

     // Perform step (8).

     if (node->postfix())

         __ pop();

 }

 void

 BytecodeCompiler::visitForALU(Type *needed, Expression *node)

 {

     node->accept(this);

     if (needed->isFloat() && !node->type()->isFloat())

         __ cvt_i2f();

     else

         assert(needed->primitive() == node->type()->primitive());

 }

 void

 BytecodeCompiler::visit(BinaryExpression *node)

 {

     visitForALU(node->type(), node->left());

     visitForALU(node->type(), node->right());

     Opcode op = TokenToOpcode(node->token());

     if (node->type()->isFloat())

         op = (Opcode)(int(op) + (OP_ADD_F - OP_ADD));

     __ binary(op);

 }

 void

 BytecodeCompiler::visit(IndexExpression *node)

 {

     node->left()->accept(this);

     node->right()->accept(this);

     __ bounds();

     if (node->type()->isArray())

         __ getarray_o();

     else

         __ getarray(node->type()->primitive());

 }

 void

 BytecodeCompiler::visit(ReturnStatement *node)

 {

     if (node->expression())

         node->expression()->accept(this);

     else

         __ int_(0);

     __ return_();

 }

 void

 BytecodeCompiler::visitForTest(Expression *expression, Label *label, bool onTrue)

 {

     TokenKind token = ToCompare(expression);

     if (token == TOK_EOF) {

         expression->accept(this);

         if (onTrue)

             __ j(OP_JT, label);

         else

             __ j(OP_JF, label);

         return;

     }

     Opcode op = CompareTokenToJump(token);

     if (!onTrue)

         op = Invert(op);

     assert(expression->isBinaryExpression());

     BinaryExpression *binary = expression->toBinaryExpression();

     binary->left()->accept(this);

     binary->right()->accept(this);

     __ j(op, label);

 }

 void

 BytecodeCompiler::visit(ForStatement *node)

 {

     AutoEnterScope forScope(this, node->scope());

     recordLifoSlot(node->scope());

     Label join, update;

     LoopScope loop(scope_, &join, &update, &loop_);

     if (node->initialization())

         node->initialization()->accept(this);

     Label header, test;

     if (node->condition())

         __ jump(&test);

     __ bind(&header);

     node->body()->accept(this);

     __ bind(&update);

     if (node->update())

         node->update()->accept(this);

     if (node->condition()) {

         __ bind(&test);

         visitForTest(node->condition(), &header, true);

     } else {

         __ jump(&header);

     }

     __ bind(&join);

     if (node->scope())

         unwindTo(node->scope()->enclosing());

     assert(__ stackDepth() == 0);

 }

 void

 BytecodeCompiler::visit(WhileStatement *node)

 {

     Label header, join;

     __ bind(&header);

     LoopScope loop(scope_, &join, &header, &loop_);

     if (node->token() == TOK_WHILE) {

         visitForTest(node->condition(), &join, false);

         node->body()->accept(this);

         __ jump(&header);

     } else {

         node->body()->accept(this);

         visitForTest(node->condition(), &header, true);

     }

     __ bind(&join);

 }

 void

 BytecodeCompiler::visit(BreakStatement *node)

 {

     unwindTo(loop_->scope());

     __ jump(loop_->break_());

 }

 void

 BytecodeCompiler::visit(ContinueStatement *node)

 {

     unwindTo(loop_->scope());

     __ jump(loop_->continue_());

 }

 void

 BytecodeCompiler::visit(BlockStatement *node)

 {

     AutoEnterScope blockScope(this, node->scope());

     recordLifoSlot(node->scope());

     for (size_t i = 0; i < node->statements()->length(); i++) {

         Statement *statement = node->statements()->at(i);

         statement->accept(this);

         assert(__ stackDepth() == 0);

     }

     // We don't bother emitting an "unwind" instruction for function scopes,

     // since this is taken care of by the calling convention.

     if (node->scope() && node->scope()->enclosing()->kind() != Scope::FUNCTION)

         unwindTo(node->scope()->enclosing());

 }

 void

 BytecodeCompiler::visit(IntegerLiteral *node)

 {

     __ int_(node->value());

 }

 void

 BytecodeCompiler::visit(FloatLiteral *node)

 {

     __ float_((float)node->value());

 }

 static inline ArrayMap *

 BuildArrayMap(Zone *zone, Handle<Type> type)

 {

     Local<ArrayMap> contained(zone);

     if (type->levels() > 1) {

         Local<Type> containedType(zone, type->contained());

         contained = BuildArrayMap(zone, containedType);

         if (!contained)

             return NULL;

     }

     return ArrayMap::New(zone, type, contained);

 }

 void

 BytecodeCompiler::visit(StringLiteral *node)

 {

     Local<Type> type(zone_, node->type());

     Local<ArrayMap> map(zone_, BuildArrayMap(zone_, type));

     if (!map)

         return;

     Local<Array> array(zone_, Array::New(zone_, map, node->string()->length(), Heap::Tenure_Old));

     if (!array)

         return;

     assert(array->nelements() >= node->string()->length());

     memcpy(array->chars(), node->string()->raw(), node->string()->length() * sizeof(char));

     __ object(array);

 }

 void

 BytecodeCompiler::visit(VariableDeclaration *node)

 {

     Variable *var = node->variable();

     assert(var->location() == Variable::STACK);

     Local<Type> type(zone_, var->type());

     if (type->isArray()) {

         Local<ArrayMap> map(zone_, BuildArrayMap(zone_, type));

         __ newarray_lifo(map);

         if (node->initialization()) {

             node->initialization()->accept(this);

             __ arraycopy();

         }

     } else {

         if (node->initialization()) {

             node->initialization()->accept(this);

         } else {

             if (!node->postDimensions())

                 __ int_(0);

         }

     }

     __ setlocal(var);

     __ pop();

     locals_->set(zone_, var->slot(), var->type());

 }

 void

 BytecodeCompiler::visit(CallExpression *node)

 {

     Local<Type> funType(zone_, node->callee()->type());

     for (size_t i = 0; i < node->arguments()->length(); i++) {

         Expression *arg = node->arguments()->at(i);

         Local<Type> given(zone_, arg->type());

         Local<Type> actual(zone_, Type::cast(funType->parameters()->at(i)));

         if (actual->isReference()) {

             if (given->isReference()) {

                 // The input type is already a reference, so we're just passing

                 // it on to the callee.

                 arg->accept(this);

             } else if (arg->isNameProxy()) {

                 // :TODO: test with functions and globals

                 // Compute a reference to the name.

                 Variable *var = arg->toNameProxy()->binding()->toVariable();

                 __ newref(var);

             } else if (arg->isIndexExpression()) {

                 IndexExpression *expr = arg->toIndexExpression();

                 expr->left()->accept(this);

                 expr->right()->accept(this);

                 __ bounds();

                 __ arrayref_lifo();

             } else {

                 // We don't know how to, or can't, build a direct reference to

                 // this type. Make an indirect one, by taking the top of the

                 // stack and boxing it up.

                 arg->accept(this);

                 __ slotref_lifo();

             }

         } else {

             arg->accept(this);

         }

     }

     __ callglobal(node->callee()->toNameProxy()->binding()->toNamedFunction()->slot());

     __ drop(node->arguments()->length());

 }

 void

 BytecodeCompiler::visit(IfStatement *node)

 {

     if (!node->ifFalse()) {

         Label fail;

         visitForTest(node->condition(), &fail, false);

         node->ifTrue()->accept(this);

         __ bind(&fail);

     } else {

         Label fail, join;

         visitForTest(node->condition(), &fail, false);

         node->ifTrue()->accept(this);

         __ jump(&join);

         __ bind(&fail);

         node->ifFalse()->accept(this);

         __ bind(&join);

     }

 }

 void

 BytecodeCompiler::visit(FunctionStatement *node)

 {

     BytecodeCompiler child(zone_, tree_, module_);

     Local<Function> fun(zone_, child.compileFunction(module_, node));

     if (!fun)

         return;

     assert(!module_->getFunction(node->fun()->slot()));

     module_->setFunction(zone_, node->fun()->slot(), fun);

 }

 void

 BytecodeCompiler::visit(EnumStatement *node)

 {

     // :TODO: eventually, we'll export these.

 }

 Function *

 BytecodeCompiler::compileFunction(Module *module, FunctionStatement *node)

 {

     // Note: No need to record a life slot here, since it's part of the Frame.

     AutoEnterScope functionScope(this, node->scope());

     locals_ = FixedArray::New(zone_, node->scope()->maxContainedLocals(), Heap::Tenure_Old);

     node->body()->accept(this);

     __ stop();

     if (__ oom())

         return NULL;

     Local<ByteArray> bytes(zone_, ByteArray::New(zone_, __ length() * sizeof(bytecode), Heap::Tenure_Old));

     if (!bytes)

         return NULL;

     memcpy(bytes->raw(), __ buffer(), __ length());

     unsigned nargs = node->scope()->numArguments();

     Local<FixedArray> args(zone_, FixedArray::New(zone_, nargs, Heap::Tenure_Old));

     if (!args)

         return NULL;

     for (size_t i = 0; i < node->scope()->numArguments(); i++)

         args->set(zone_, i, node->scope()->getArgument(i)->type());

     for (size_t i = 0; i < node->scope()->maxContainedLocals(); i++)

         assert(locals_->at(i));

     Local<FixedArray> objects(zone_, FixedArray::New(zone_, __ objects()->length(), Heap::Tenure_Old));

     if (!objects)

         return NULL;

     for (size_t i = 0; i < __ objects()->length(); i++)

         objects->set(zone_, i, *(__ objects()->at(i)));

     Local<ByteArray> safepoints(zone_);

     // If any stack slots hold gc pointers at potential failure points in the

     // bytecode, record them now. We do this by building a list of tuples;

     // each tuple contains the pc offset, and a bitset containing which stack

     // slots must be scanned by the gc.

     if (__ oopRecords()->length()) {

         size_t bytesPerSafepoint = Code::BytesPerSafepoint(__ maxStackDepth());

         size_t gcmapSize = bytesPerSafepoint * __ oopRecords()->length();

         safepoints = ByteArray::New(zone_, gcmapSize, Heap::Tenure_Old);

         if (!safepoints)

             return NULL;

         Address cursor = safepoints->raw();

         for (size_t i = 0; i < __ oopRecords()->length(); i++) {

             OopRecord *record = __ oopRecords()->at(i);

             assert(record->depth <= __ maxStackDepth());

             *reinterpret_cast<unsigned *>(cursor) = record->offset;

             unsigned char *bits = reinterpret_cast<unsigned char *>(cursor + sizeof(unsigned));

             for (unsigned i = 0; i < record->depth; i++)

                 bits[i / 8] |= (1 << (i % 8));

             cursor += bytesPerSafepoint;

         }

         assert(cursor == safepoints->raw() + gcmapSize);

     }

     Local<Code> code(zone_, Code::New(zone_, bytes, locals_, objects, __ maxStackDepth(), module_,

                      safepoints));

     if (!code)

         return NULL;

     Local<Function> fun(zone_, Function::New(zone_, module_, code, node->fun()->type(), node->pos()));

     if (!fun)

         return NULL;

     return fun;

 }

 Module *

 BytecodeCompiler::compile()

 {

     module_ = Module::New(zone_, tree_->scope()->numFunctions());

     if (!module_)

         return NULL;

     for (size_t i = 0; i < tree_->statements()->length(); i++) {

         Statement *statement = tree_->statements()->at(i);

         statement->accept(this);

     }

 #ifndef NDEBUG

     for (size_t i = 0; i < tree_->scope()->numFunctions(); i++)

         assert(module_->getFunction(i));

 #endif

     return module_;

 }