/* 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 <string.h>

 #include "BytecodeCompiler.h"

 #include "Scopes.h"

 #include "Modules.h"

 #include "Types.h"

 #include "Array.h"

 #include "Strings.h"

 #include "Zone.h"

 #include "Environments.h"

 #include "Heap-inl.h"

 using namespace ke;

 typedef BytecodeEmitter::Label Label;

 #define __ emitter_.

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

   : zone_(zone),

     tree_(tree),

     emitter_(zone->pool()),

     locals_(NULL),

     scope_(NULL),

     moduleData_(module),

     loop_(NULL)

 {

 }

 static inline TokenKind

 ToCompare(Expression *expr)

 {

     if (expr->isBinaryExpression()) {

         BinaryExpression *b = expr->toBinaryExpression();

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

             return b->token();

     } else if (expr->isUnaryExpression()) {

         UnaryExpression *u = expr->toUnaryExpression();

         if (u->token() == TOK_NOT)

             return TOK_NOT;

     }

     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_PERCENT:

         return OP_MOD;

       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;

       case TOK_GT:

           return OP_GT;

       case TOK_GE:

           return OP_GE;

       case TOK_LT:

           return OP_LT;

       case TOK_LE:

           return OP_LE;

       case TOK_EQUALS:

           return OP_EQ;

       case TOK_NOTEQUALS:

           return OP_NE;

       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 if (var->location() == Variable::ENVIRONMENT) {

             getEnvSlot(var);

         } 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());

         }

         break;

       }

       case BoundName::FUNCTION:

       {

         NamedFunction *fun = name->binding()->toNamedFunction();

         __ module();

         __ getmodule_fn(fun->slot());

         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);

     if (!node->expression()->type()->isVoid())

         __ 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());

             } else {

                 __ get(var);

             }

         }

     } else {

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

         __ note_position(index->pos());

         // 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());

         }

     }

     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));

         __ note_position(node->pos());

         __ 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.

         __ note_position(node->pos());

         __ arraycopy();

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

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

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

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

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

         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());

     }

 }

 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());

             if (node->postfix()) {

                 __ swap();

                 __ pick2();

             }

         } else {

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

             __ get(var);

             if (node->postfix())

                 __ dup();

         }

     } else {

         IndexExpression *index = expr->toIndexExpression();

         __ note_position(index->pos());

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

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

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

         __ bounds();

         __ dup2();

         __ getarray(node->type());

         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);

     }

     __ note_position(node->pos());

     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());

         else

             __ set(var);

     } else {

         __ setarray(node->type());

     }

     // 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());

 }

 static inline Type *

 GetCoercionType(TokenKind tok, Type *left, Type *right)

 {

     if (left->isFloat())

         return left;

     return right;

 }

 void

 BytecodeCompiler::visit(UnaryExpression *node)

 {

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

     switch (node->token()) {

       case TOK_MINUS:

       {

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

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

         if (out->isFloat())

             __ neg_f();

         else

             __ neg();

         break;

       }

       case TOK_NOT:

       {

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

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

         if (out->isFloat())

             __ not_f();

         else

             __ not_();

         break;

       }

       case TOK_LABEL:

       {

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

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

         if (!from->isFloat() && out->isFloat())

             __ bits_f2i();

         else if (from->isFloat() && !out->isFloat())

             __ bits_i2f();

         break;

       }

       default:

         assert(node->token() == TOK_TILDE);

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

         __ bitnot();

         break;

     }

 }

 void

 BytecodeCompiler::visit(BinaryExpression *node)

 {

     if (node->token() == TOK_AND || node->token() == TOK_OR) {

         Label success, failure, done;

         visitForTest(node, &success, &failure, &success);

         __ bind(&success);

         __ int_(1);

         __ drop(1);         // Otherwise, the stack depth will be +1 too much.

         __ jump(&done);

         __ bind(&failure);

         __ int_(0);

         __ bind(&done);

         return;

     }

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

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

     Local<Type> coerce(zone_, GetCoercionType(node->token(), leftType, rightType));

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

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

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

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

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

     __ note_position(node->pos());

     __ binary(op);

 }

 void

 BytecodeCompiler::visit(IndexExpression *node)

 {

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

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

     __ note_position(node->pos());

     __ bounds();

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

         __ getarray_o();

     else

         __ getarray(node->type());

 }

 void

 BytecodeCompiler::visit(ReturnStatement *node)

 {

     if (node->expression()) {

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

         __ return_();

     } else {

         __ returnvoid();

     }

 }

 void

 BytecodeCompiler::visitForTest(Expression *expression,

                                Label *trueBranch,

                                Label *falseBranch,

                                Label *fallthrough)

 {

     TokenKind token = ToCompare(expression);

     if (token == TOK_EOF || token == TOK_NOT) {

         if (token == TOK_EOF)

             expression->accept(this);

         else

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

         bool jumpOnTrue = (fallthrough == falseBranch) ^ (token == TOK_NOT);

         Opcode op = jumpOnTrue ? OP_JT : OP_JF;

         if (expression->type()->isFloat())

             op = (Opcode)(int(op) + (OP_JL_F - OP_JL));

         if (fallthrough == falseBranch)

             __ j(op, trueBranch);

         else

             __ j(op, falseBranch); 

         return;

     }

     BinaryExpression *binary = expression->toBinaryExpression();

     if (token == TOK_AND || token == TOK_OR) {

         Label next;

         if (token == TOK_AND)

             visitForTest(binary->left(), &next, falseBranch, &next);

         else

             visitForTest(binary->left(), trueBranch, &next, &next);

         __ bind(&next);

         visitForTest(binary->right(), trueBranch, falseBranch, fallthrough);

         return;

     }

     Opcode op = CompareTokenToJump(token);

     if (fallthrough == trueBranch)

         op = Invert(op);

     Local<Type> leftType(zone_, binary->left()->type());

     Local<Type> rightType(zone_, binary->right()->type());

     Local<Type> coerce(zone_, GetCoercionType(binary->token(), leftType, rightType));

     visitForALU(coerce, binary->left());

     visitForALU(coerce, binary->right());

     if (coerce->isFloat())

         op = (Opcode)(int(op) + (OP_JL_F - OP_JL));

     if (fallthrough == trueBranch)

         __ j(op, falseBranch);

     else

         __ j(op, trueBranch);

 }

 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, &join, &join);

     } 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) {

         Label body;

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

         __ bind(&body);

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

         __ jump(&header);

     } else {

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

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

     }

     __ 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(BooleanLiteral *node)

 {

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

         __ true_();

     else

         __ false_();

 }

 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));

     __ note_position(node->pos());

     __ object(array);

 }

 void

 BytecodeCompiler::getEnvSlot(Variable *var)

 {

     assert(var->scope()->kind() == Scope::GLOBAL);

     __ getglobal(var);

 }

 void

 BytecodeCompiler::setEnvSlot(Variable *var)

 {

     assert(var->scope()->kind() == Scope::GLOBAL);

     __ setglobal(var);

 }

 void

 BytecodeCompiler::visit(VariableDeclaration *node)

 {

     Variable *var = node->variable();

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

     if (type->isArray()) {

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

         __ note_position(node->pos());

         if (var->scope()->kind() == Scope::GLOBAL)

             __ newarray(map, Heap::Tenure_Old);

         else if (var->needsHeapAllocation())

             __ newarray(map, Heap::Tenure_Default);

         else

             __ newarray(map, Heap::Tenure_Stack);

         if (node->initialization()) {

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

             __ note_position(node->pos());

             __ arraycopy();

         }

     } else {

         if (node->initialization()) {

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

         } else {

             if (!node->postDimensions())

                 __ int_(0);

         }

     }

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

         __ setlocal(var);

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

     } else {

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

         setEnvSlot(var);

     }

     __ pop();

 }

 void

 BytecodeCompiler::visit(CallExpression *node)

 {

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

     // Sniff out natives, which have a specific opcode and are guaranteed to

     // be called via name proxy.

     NamedFunction *native = NULL;

     if (funType->isNative()) {

         native = node->callee()->toNameProxy()->binding()->toNamedFunction();

     }

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

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

         // We need to compute a reference if the parameter was in the form:

         //  f(&a)

         // Note this form does not allow: f({})

         // 

         // We also need to compute references for all variadic native

         // arguments, but arrays and references are already in the

         // appropriate form.

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

         bool mustPushReference = false;

         if (i >= funType->parameters()->length()) {

             assert(funType->isNative() && funType->isNativeVariadic());

             mustPushReference = !given->isArray() && !given->isReference();

         } else if (funType->parameterAt(i)->isReference()) {

             mustPushReference = !given->isReference();

         }

         // If a native is passed to a native, it must only be one level deep.

         assert(!funType->isNative() || !given->isArray() || given->levels() == 1);

         if (mustPushReference) {

             if (arg->isNameProxy()) {

                 // :TODO: test with functions and globals

                 // Compute a reference to the name.

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

                 __ note_position(node->pos());

                 __ newref(var);

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

                 IndexExpression *expr = arg->toIndexExpression();

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

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

                 __ note_position(expr->pos());

                 __ 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);

                 __ note_position(node->pos());

                 __ slotref_lifo();

             }

         } else {

             arg->accept(this);

         }

     }

     __ note_position(node->pos());

     if (native) {

         __ callnative(native->slot(), node->arguments()->length());

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

     } else {

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

         __ call(funType);

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

     }

 }

 void

 BytecodeCompiler::visit(TernaryExpression *node)

 {

     Label success, failure, join;

     visitForTest(node->condition(), &success, &failure, &success);

     __ bind(&success);

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

     __ drop(1);

     __ jump(&join);

     __ bind(&failure);

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

     __ bind(&join);

 }

 void

 BytecodeCompiler::visit(IfStatement *node)

 {

     Label join;

     if (!node->ifFalse()) {

         Label success;