/* 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 "Box.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();

 }

 static inline bool

 IsCompositeValueType(Type *type)

 {

     return type->isStruct() ||

            (type->isArray() && type->isFixedLength());

 }

 static inline Array *

 StringLiteralToArray(Zone *zone, StringLiteral *node)

 {

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

     Local<ArrayMap> map(zone, ArrayMap::Attach(zone, type));

     if (!map)

         return NULL;

     return Array::NewString(zone,

                             map,

                             node->string()->raw(),

                             node->string()->length(),

                             Heap::Tenure_Old);

 }

 void

 BytecodeCompiler::visit(Assignment *node)

 {

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

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

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

         // We need to fetch the variable under the following circumstances:

         //  (1) The variable is a reference, since we'll store into the ref.

         //  (2) The variable is a fixed array, since we need to copy into it.

         //  (3) The variable is a struct, since we need to copy into it.

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

             __ get(var);

         // Get the value if needed.

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

             // += etc is not allowed on arrays.

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

             if (var->location() == Variable::ENVIRONMENT)

                 getEnvSlot(var);

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

                 __ dup();

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

             } else if (var->location() != Variable::ENVIRONMENT) {

                 __ get(var);

             }

         }

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

         FieldExpression *expr = node->lvalue()->toFieldExpression();

         __ note_position(expr->pos());

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

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

             __ dup();

         if (node->token() != TOK_ASSIGN || IsCompositeValueType(left))

             __ getfield(expr->fieldIndex(), left);

     } else {

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

         __ note_position(index->pos());

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

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

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

             __ dup2();

         if (node->token() != TOK_ASSIGN || IsCompositeValueType(left))

             __ getelem(left);

     }

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

         // Special case: if the left-hand side is a string literal, we must

         // spawn a new copy (:TODO: something about const?)

         if (node->expression()->isStringLiteral() && !left->isFixedLength()) {

             Local<Array> string(zone_,

                     StringLiteralToArray(zone_, node->expression()->toStringLiteral()));

             if (!string)

                 return;

             Local<ArrayMap> arrayMap(zone_, ArrayMap::cast(string->map()));

             __ note_position(node->expression()->pos());

             __ int_(string->length());

             __ newarray(OP_NEWSIZED, arrayMap, Heap::Tenure_Default);

             __ object(string);

             __ copyarray();

         } else {

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

         }

     } else {

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

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

         __ note_position(node->pos());

         __ binary(TokenToOpcode(alu));

     }

     // Emit the store.

     if (left->isArray() && left->isFixedLength()) {

         // (x = y) returns the left-hand side; if |x| is a fixed-length array,

         // then |y| is as well, and we perform a deep copy.

         assert(right->isFixedLength());

         __ note_position(node->pos());

         __ copyarray();

     } else if (left->isStruct()) {

         // Structs have value semantics, so emit a full copy. We don't break

         // this down into u-ops, to avoid unnecessary bytecode explosion.

         assert(right->isStruct());

         __ note_position(node->pos());

         __ copystruct();

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

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

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

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

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

         else if (var->location() == Variable::ENVIRONMENT)

             setEnvSlot(var);

         else

             __ set(var);

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

         FieldExpression *expr = node->lvalue()->toFieldExpression();

         __ setfield(expr->fieldIndex(), left);

     } else {

         __ setelem(left);

     }

 }

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

             getEnvSlot(var);

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

             if (var->location() != Variable::ENVIRONMENT)

                 __ get(var);

             if (node->postfix())

                 __ dup();

         }

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

         FieldExpression *field = expr->toFieldExpression();

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

         __ dup();

         __ getfield(field->fieldIndex(), field->type());

         if (node->postfix()) {

             // The stack looks like this now:

             // OBJECT VALUE

             __ swap();          // VALUE OBJECT

             __ pick2();         // VALUE OBJECT VALUE

         }

     } else {

         IndexExpression *index = expr->toIndexExpression();

         __ note_position(index->pos());

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

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

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

         __ dup2();

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

             setEnvSlot(var);

         else

             __ set(var);

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

         FieldExpression *field = expr->toFieldExpression();

         __ setfield(field->fieldIndex(), field->type());

     } else {

         assert(expr->isIndexExpression());

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

       }

       case TOK_SIZEOF:

       {

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

         if (type->isFixedLength()) {

             __ int_(type->fixedLength());

         } else {

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

             __ sizeof_();

         }

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

     __ getelem(node->type());

 }

 void

 BytecodeCompiler::visit(FieldExpression *node)

 {

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

     __ getfield(node->fieldIndex(), 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());

 }

 void

 BytecodeCompiler::visit(StringLiteral *node)

 {

     Local<Array> array(zone_, StringLiteralToArray(zone_, node));

     if (!array)

         return;

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

 }

 static bool

 FillArrayLiteral_String(Zone *zone, Handle<Array> array, ArrayLiteral *literal, unsigned *maxsize)

 {

     Local<Array> string(zone);

     for (size_t i = 0; i < literal->expressions()->length(); i++) {

         Expression *expr = literal->expressions()->at(i);

         StringLiteral *lit = expr->toStringLiteral();

         if ((string = StringLiteralToArray(zone, lit)) == NULL)

             return false;

         array->writeObject(zone, i, string);

         if (string->length() > *maxsize)

             *maxsize = string->length();

         assert(!array->type()->contained()->isFixedLength() ||

                 array->type()->contained()->fixedLength() >= string->length());

     }

     return true;

 }

 static bool

 FillArrayLiteral_Primitive(Zone *zone, Handle<Array> array, ArrayLiteral *literal)

 {

     assert(array->type()->fixedLength() == literal->expressions()->length());

     for (size_t i = 0; i < literal->expressions()->length(); i++) {

         Expression *expr = literal->expressions()->at(i);

         if (IntegerLiteral *lit = expr->asIntegerLiteral()) {

             array->writeInt32(i, lit->value());

             continue;

         }

         if (BooleanLiteral *lit = expr->asBooleanLiteral()) {

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

                 array->writeInt32(i, 1);

             else

                 array->writeInt32(i, 0);

             continue;

         }

         if (FloatLiteral *lit = expr->asFloatLiteral()) {

             array->writeFloat(i, lit->value());

             continue;

         }

         // Unrecognized literal type.

         assert(false);

     }

     return true;

 }

 static bool

 TraverseArrayLiteral(Zone *zone, ArrayLiteral *literal, Handle<Array> array, Handle<Type> type,