/* 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/.
 */
#ifndef _include_bytecode_emitter_h_
#define _include_bytecode_emitter_h_

#include <assert.h>
#include <limits.h>
#include "Opcodes.h"
#include "NameBinding.h"
#include "Handles.h"
#include "CompactBuffer.h"

namespace ke {

class Type;
class Map;

typedef PoolList<ScopedRoot<Object> > ObjectList;

struct OopRecord : public PoolObject
{
    unsigned depth;
    unsigned offset;
    bool *slots;

    OopRecord(unsigned length, unsigned offset)
      : depth(length),
        offset(offset),
        slots(NULL)
    {
    }
};

class BytecodeEmitter
{
  private:
    PoolAllocator &pool_;

    bytecode *buffer_;
    bytecode *buffer_pos_;
    bytecode *buffer_end_;
    bytecode inline_buffer_[512];
    bool oom_;
    unsigned maxStackDepth_;
    ObjectList objects_;
    PoolList<bool> oopMap_;
    PoolList<OopRecord *> oopRecords_;
    CompactBufferWriter sourcemap_;
    unsigned lastCodePosition_;
    unsigned firstLine_;

  private:
    // The maximum size of a code object must be such that the distance between
    // two instructions fits into a signed, 31-bit integer. This ensures that
    // all code-bounded buffers (like the number of object literals or
    // safepoints) does not need to be bounds checked. It also means we can add
    // any two offsets and be guaranteed that they don't overflow.
    static const size_t MAX_LENGTH = INT_MAX / 2;

  private:
    bool growBuffer(size_t bytes);

    // Checking the return value is not necessary, since the inline buffer is
    // used as a ballast.
    bool ensure(size_t bytes) {
        if (buffer_pos_ + bytes > buffer_end_)
            return growBuffer(bytes);
        return true;
    }

    void writeUint8(unsigned value) {
        assert(value <= UCHAR_MAX);
        *buffer_pos_++ = value;
    }
    void writeFloat(float value) {
        *(float *)buffer_pos_ = value;
        buffer_pos_ += sizeof(float);
    }
    void writeInt32(int value) {
        *(int *)buffer_pos_ = value;
        buffer_pos_ += sizeof(int);
    }
    void writeUint32(unsigned value) {
        *(unsigned *)buffer_pos_ = value;
        buffer_pos_ += sizeof(unsigned);
    }
    void writeOp(Opcode op) {
        if (oom_)
            return;

        writeUint8(op);
        for (int i = 0; i < OpcodeInfo[op].nuses; i++)
            oopMap_.pop();
        for (int i = 0; i < OpcodeInfo[op].ndefs; i++)
            oopMap_.append(false);
        if (oopMap_.length() > maxStackDepth_)
            maxStackDepth_ = oopMap_.length();
    }
    void writeObject(Object *obj) {
        writeUint32(objects_.length());
        ScopedRoot<Object> root(obj);
        if (!objects_.append(root))
            oom_ = true;
    }

    int position() const {
        assert(buffer_pos_ - buffer_ < INT_MAX / 2);
        return int(buffer_pos_ - buffer_);
    }

  public:
    BytecodeEmitter(PoolAllocator &pool);

    bytecode *buffer() const {
        return buffer_;
    }
    unsigned length() const {
        return unsigned(buffer_pos_ - buffer_);
    }
    bool oom() const {
        return oom_ || sourcemap_.oom();
    }
    unsigned stackDepth() const {
        return oopMap_.length();
    }
    unsigned maxStackDepth() const {
        return maxStackDepth_;
    }
    const ObjectList *objects() const {
        return &objects_;
    }
    PoolList<OopRecord *> *oopRecords() {
        return &oopRecords_;
    }

    void drop(unsigned amt) {
        assert(amt <= stackDepth());
        for (unsigned i = 0; i < amt; i++)
            oopMap_.pop();
    }

    void note_position(const SourcePosition &pos);
    uint8 *sourcemap() const {
        return sourcemap_.buffer();
    }
    size_t sourcemapLength() const {
        return sourcemap_.length();
    }
    void setFirstLine(unsigned line) {
        assert(!sourcemap_.length());
        firstLine_ = line;
    }

  public:
    // A label represents a local control-flow target in the bytecode. A label
    // may be in three states:
    //
    // (1) Empty - the label is not used yet.
    // (2) Pending - the label has incoming jumps, but the actual location of
    //               is not yet known. The list of jumps is threaded through
    //               the four bytes reserved for each emitted jump target. In
    //               this case, the offset field is the location of the most
    //               recently emitted incoming jump.
    // (3) Bound   - the label's position has been pinned.
    //
    // A jump can be emitted to a label in any state. Binding a label
    // immediately backpatches all pending incoming jumps. A label must be
    // bound if it is used.
    class Label
    {
        int offset_ : 31;
        bool bound_ : 1;

        void setOffset(int offset) {
            offset_ = offset;
            assert(offset_ == offset);
        }

      public:
        static const int INVALID_OFFSET = -1;

      public:
        Label()
          : offset_(INVALID_OFFSET),
            bound_(false)
        {
        }
        ~Label()
        {
            assert(bound_ || offset_ == INVALID_OFFSET);
        }
        
        bool bound() const {
            return bound_;
        }
        int offset() const {
            return offset_;
        }
        void bind(int offset) {
            assert(!bound_);
            setOffset(offset);
            bound_ = true;
        }
        int link(int offset) {
            assert(!bound_);
            int old = offset_;
            setOffset(offset);
            return old;
        }
    };

  private:
    int patchJumpAt(int at, int to) {
        assert(at >= 0 && at < position());
        int old = *(int *)(buffer_ + at + 1);
        *(int *)(buffer_ + at + 1) = (to - at);
        return old;
    }

    void singleByteOp(Opcode op) {
        assert(OpcodeInfo[op].length == 1);
        ensure(OpcodeInfo[op].length);
        writeOp(op);
    }

    // Mark a stack slot as having an object pointer.
    void markOop(unsigned depth, bool oop = true) {
        if (oom_)
            return;
        oopMap_[oopMap_.length() - depth] = oop;
    }
    bool getOop(unsigned depth) {
        if (oom_)
            return false;
        return oopMap_[oopMap_.length() - depth];
    }

    // Mark the current bytecode position as either re-entrant (meaning, it
    // can leave the interpreter or call to another function), or causing GC.
    // This will record which stack slots have objects and associate that
    // information with the current pc.
    void recordOops();

  public:
    void int_(int value) {
        ensure(OP_INT);
        writeOp(OP_INT);
        writeInt32(value);
    }
    void return_() {
        ensure(OP_RETURN);
        writeOp(OP_RETURN);
    }
    void getlocal(Variable *var) {
        ensure(OP_GETLOCAL_LENGTH);
        writeOp(OP_GETLOCAL);
        writeUint32(var->slot());

        if (var->type()->isTraceable())
            markOop(1);
    }
    void setlocal(Variable *var) {
        ensure(OP_SETLOCAL_LENGTH);
        writeOp(OP_SETLOCAL);
        writeUint32(var->slot());

        if (var->type()->isTraceable())
            markOop(1);
    }
    void getarg(Variable *var) {
        ensure(OP_GETARG_LENGTH);
        writeOp(OP_GETARG);
        writeUint32(var->slot());

        if (var->type()->isTraceable())
            markOop(1);
    }
    void setarg(Variable *var) {
        ensure(OP_SETARG_LENGTH);
        writeOp(OP_SETARG);
        writeUint32(var->slot());

        if (var->type()->isTraceable())
            markOop(1);
    }

    void j(Opcode op, Label *label) {
        // Since jumps can skip around the stream, do not try to do anything
        // in a potentially truncated state.
        if (oom())
            return;

        assert(op >= OP_JL && op <= OP_JUMP);
        ensure(OP_JUMP_LENGTH);

        if (label->bound()) {
            // We can immediately emit this jump.
            int distance = label->offset() - position();
            writeOp(op);
            writeInt32(distance);
        } else {
            // We can't emit this jump yet. Add a placeholder.
            int old = label->link(position());
            writeOp(op);
            writeInt32(old);
        }
    }
    void bind(Label *label) {
        if (oom())
            return;

        assert(!label->bound());

        int offset = label->offset();
        while (offset != Label::INVALID_OFFSET)
            offset = patchJumpAt(offset, position());

        label->bind(position());
    }
    void jump(Label *label) {
        j(OP_JUMP, label);
    }

    void binary(Opcode op) {
        singleByteOp(op);
    }

    void pop() {
        singleByteOp(OP_POP);
    }
    void stop() {
        singleByteOp(OP_STOP);
    }
    void call(Handle<Type> fun) {
        recordOops();
        ensure(OP_CALL_LENGTH);
        writeOp(OP_CALL);

        if (fun->returnType()->isVoid())
            drop(1);
        else if (fun->returnType()->isTraceable())
            markOop(1);
    }
    void callnative(unsigned index, unsigned argc) {
        recordOops();
        ensure(OP_CALLNATIVE_LENGTH);
        writeOp(OP_CALLNATIVE);
        writeUint32(index);
        writeUint32(argc);
    }

    void getelem(Type *type) {
        singleByteOp(OP_GETELEM);

        if (type->isTraceable())
            markOop(1);
    }
    void setelem(Type *type) {
        singleByteOp(OP_SETELEM);
    }

    void getfield(unsigned index, Type *type) {
        ensure(OP_GETFIELD_LENGTH);
        writeOp(OP_GETFIELD);
        writeUint32(index);

        if (type->isTraceable())
            markOop(1);
    }
    void setfield(unsigned index, Type *type) {
        ensure(OP_SETFIELD_LENGTH);
        writeOp(OP_SETFIELD);
        writeUint32(index);

        if (type->isTraceable())
            markOop(1);
    }

    void getglobal(Variable *var) {
        ensure(OP_GETGLOBAL_F_LENGTH);
        if (var->type()->isPrimitive()) {
            switch (var->type()->primitive()) {
              case PrimitiveType_Float:
                writeOp(OP_GETGLOBAL_F);
                break;
              default:
                assert(var->type()->primitive() == PrimitiveType_Int32);
                writeOp(OP_GETGLOBAL_I);
                break;
            }
        } else {
            writeOp(OP_GETGLOBAL_O);
            markOop(1);
        }
        writeUint32(var->slot());
    }
    void setglobal(Variable *var) {
        ensure(OP_SETGLOBAL_F_LENGTH);
        if (var->type()->isPrimitive()) {
            switch (var->type()->primitive()) {
              case PrimitiveType_Float:
                writeOp(OP_SETGLOBAL_F);
                break;
              default:
                assert(var->type()->primitive() == PrimitiveType_Int32);
                writeOp(OP_SETGLOBAL_I);
                break;
            }
        } else {
            writeOp(OP_SETGLOBAL_O);
        }
        writeUint32(var->slot());
    }

    void float_(float value) {
        ensure(OP_FLOAT_LENGTH);
        writeOp(OP_FLOAT);
        writeFloat(value);
    }
    void cvt_i2f() {
        singleByteOp(OP_CVT_I2F);
    }
    void newarray(Opcode op, Handle<Map> map, Heap::Tenure tenure) {
        assert(op == OP_NEWFIXED ||
               op == OP_NEWEMPTY ||
               op == OP_NEWSIZED);

        recordOops();
        ensure(OpcodeInfo[op].length);
        writeOp(op);
        writeUint8(tenure);
        writeObject(map);
        markOop(1);
    }
    void newstruct(Handle<Map> map, Heap::Tenure tenure) {
        recordOops();
        ensure(OP_NEWSTRUCT_LENGTH);
        writeOp(OP_NEWSTRUCT);
        writeUint8(tenure);
        writeObject(map);
        markOop(1);
    }
    void savelifo(unsigned slot) {
        ensure(OP_SAVELIFO_LENGTH);
        writeOp(OP_SAVELIFO);
        writeUint32(slot);
    }
    void unwindlifo(unsigned slot) {
        ensure(OP_UNWINDLIFO_LENGTH);
        writeOp(OP_UNWINDLIFO);
        writeUint32(slot);
    }
    void newref(Variable *var) {
        recordOops();
        if (var->location() == Variable::STACK) {
            ensure(OP_VARREF_LIFO_LENGTH);
            writeOp(OP_VARREF_LIFO);
        } else {
            assert(var->location() == Variable::PARAMETER);
            ensure(OP_ARGREF_LIFO_LENGTH);
            writeOp(OP_ARGREF_LIFO);
        }
        writeUint32(var->slot());
        markOop(1);
    }

    void slotref_lifo() {
        recordOops();
        singleByteOp(OP_SLOTREF_LIFO);
        markOop(1);
    }
    void arrayref_lifo() {
        recordOops();
        singleByteOp(OP_ARRAYREF_LIFO);
        markOop(1);
    }
    void fieldref_lifo(unsigned index) {
        recordOops();
        ensure(OP_FIELDREF_LIFO_LENGTH);
        writeOp(OP_FIELDREF_LIFO);
        writeUint32(index);
        markOop(1);
    }
    void getref(Type *type) {
        if (type->pod() == PrimitiveType_Int32) {
            singleByteOp(OP_GETREF_I);
        } else {
            assert(type->pod() == PrimitiveType_Float);
            singleByteOp(OP_GETREF_F);
        }
    }
    void setref(Type *type) {
        if (type->pod() == PrimitiveType_Int32) {
            singleByteOp(OP_SETREF_I);
        } else {
            assert(type->pod() == PrimitiveType_Float);
            singleByteOp(OP_SETREF_F);
        }
    }
    void object(Handle<Object> obj) {
        ensure(OP_OBJECT_LENGTH);
        writeOp(OP_OBJECT);
        writeObject(obj);
        markOop(1);
    }
    void copyarray() {
        singleByteOp(OP_COPYARRAY);
        markOop(1);
    }
    void copystruct() {
        singleByteOp(OP_COPYSTRUCT);
        markOop(1);
    }

    void dup() {
        bool oop = getOop(1);
        singleByteOp(OP_DUP);
        markOop(1, oop);
    }
    void dup2() {
        bool oop2 = getOop(2);
        bool oop1 = getOop(1);

        singleByteOp(OP_DUP2);

        markOop(2, oop2);
        markOop(1, oop1);
    }
    void swap() {
        bool oop2 = getOop(2);
        bool oop1 = getOop(1);

        singleByteOp(OP_SWAP);

        markOop(2, oop1);
        markOop(1, oop2);
    }
    void roll3() {
        bool oop3 = getOop(3);
        bool oop2 = getOop(2);
        bool oop1 = getOop(1);

        singleByteOp(OP_ROLL3);

        markOop(3, oop2);
        markOop(2, oop1);
        markOop(1, oop3);
    }
    void pick2() {
        bool oop2 = getOop(2);
        bool oop1 = getOop(1);

        singleByteOp(OP_PICK2);

        markOop(3, oop2);
        markOop(2, oop1);
        markOop(1, oop2);
    }
    void pick3() {
        bool oop3 = getOop(3);
        bool oop2 = getOop(2);
        bool oop1 = getOop(1);

        singleByteOp(OP_PICK3);

        markOop(4, oop3);
        markOop(3, oop2);
        markOop(2, oop1);
        markOop(1, oop3);
    }

    void returnvoid() {
        singleByteOp(OP_RETURNVOID);
    }
    void module() {
        singleByteOp(OP_MODULE);
        markOop(1);
    }
    void getmodule_fn(unsigned index) {
        ensure(OP_GETMODULE_FN_LENGTH);
        writeOp(OP_GETMODULE_FN);
        writeUint32(index);
        markOop(1);
    }
    void bitnot() {
        singleByteOp(OP_BITNOT);
    }
    void not_() {
        singleByteOp(OP_NOT);
    }
    void not_f() {
        singleByteOp(OP_NOT_F);
    }
    void neg() {
        singleByteOp(OP_NEG);
    }
    void neg_f() {
        singleByteOp(OP_NEG_F);
    }
    void bits_i2f() {
        singleByteOp(OP_BITS_I2F);
    }
    void bits_f2i() {
        singleByteOp(OP_BITS_F2I);
    }
    void true_() {
        singleByteOp(OP_TRUE);
    }
    void false_() {
        singleByteOp(OP_FALSE);
    }

    void tableswitch(int low, int high, Label *def, Label **labels) {
        unsigned tablesize = TableSwitchEntries(low, high);
        assert(tablesize <= MAX_TABLESWITCH_ENTRIES);

        ensure(OP_TABLESWITCH_LENGTH);
        writeOp(OP_TABLESWITCH);
        writeInt32(low);
        writeInt32(high);
        jump(def);

        // When labels are patched, we assume each position is a jump. Rather
        // than hack position offsets to make labels work without actual
        // incoming jumps, we emit a jump inline.
        for (unsigned i = 0; i < tablesize; i++)
            jump(labels[i]);
    }

    // Helpers.
    void get(Variable *var) {
        if (var->location() == Variable::STACK) {
            getlocal(var);
        } else {
            assert(var->location() == Variable::PARAMETER);
            getarg(var);
        }
    }
    void set(Variable *var) {
        assert(!var->type()->isReference());
        if (var->location() == Variable::STACK) {
            setlocal(var);
        } else {
            assert(var->location() == Variable::PARAMETER);
            setarg(var);
        }
    }
};

}

#endif // _include_bytecode_emitter_h_