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

#include "../CompactBuffer.h"

#include "../Array.h"

#include "../HashTable.h"

#include "../VirtualObjectVisitor.h"

namespace ke {

// An overarching note on overflows: Though we should use CheckedInt, we rely

// on a source-length cap covering all possible overflow checks. As long as

// the source length is capped to INT_MAX, the number of AST nodes will be

// strictly beneath that cap, and so to will most things generated by the

// AST. For example, local and argument counts, number of functions, fields

// in a struct, et cetera. Not everything can be covered by this cap: the

// stack depth, number of bytecodes for example. In these cases we explicitly

// test for overflow of INT_MAX and in other cases we assert.

//

// In the future, we should of course use a checked int wrapper.

class Type;

class Map;

class ArrayMap;

class Symbol;

class VariableSymbol;

struct OopRecord

{

    unsigned depth;

    unsigned offset;

    Vector<bool> slots;

    OopRecord(unsigned length, unsigned offset)

      : depth(length),

        offset(offset)

    {

    }

};

class StringTable

{

    struct Entry

    {

        String *string;

        unsigned index;

        Entry()

          : string(NULL),

            index(0)

        {

        }

        Entry(String *string, unsigned index)

          : string(string),

            index(index)

        {

        }

    };

    struct Policy

    {

        typedef Entry Payload;

        static uint32 hash(String *string) {

            return HashPointer(string);

        }

        static bool matches(String *key, Entry &e) {

            return key == e.string;

        }

    };

    typedef HashTable<Policy, ZoneAllocatorPolicy> Set;

  public:

    StringTable();

    bool initialize();

    void accept(VirtualObjectVisitor *visitor);

    bool add(Handle<String> name, unsigned *indexp);

    size_t stringCount() const {

        return strings_.length();

    }

    String *stringAt(size_t i) const {

        return strings_[i].string;

    }

  private:

    Set set_;

    Vector<Entry> strings_;

    bool initialized_;

};

// The bytecode emitter assists in building Code objects, by emitting opcodes

// and tracking stack information. Since the SemA creates temporary pool/root

// scopes, we cannot use ScopedRoot or PoolObjects. Instead, BCE gets a

// special marking function.

class BytecodeEmitter : public AutoRooted

{

  private:

    PoolAllocator &pool_;

    bytecode *buffer_;

    bytecode *buffer_pos_;

    bytecode *buffer_end_;

    bytecode inline_buffer_[512];

    bool oom_;

    unsigned maxStackDepth_;

    Vector<bool> oopMap_;

    Vector<OopRecord *> oopRecords_;

    CompactBufferWriter sourcemap_;

    unsigned lastCodePosition_;

    unsigned firstLine_;

    StringTable strings_;

    Vector<Symbol *> locals_;

    Vector<Object *> objects_;

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

    ~BytecodeEmitter();

    void accept(VirtualObjectVisitor *visitor);

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

    }

    void drop(unsigned amt) {

        assert(amt <= stackDepth());

        for (unsigned i = 0; i < amt; i++)

            oopMap_.pop();

    }

    void note_position(const SourcePosition &pos);

    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(VariableSymbol *var);

    void setlocal(VariableSymbol *var);

#if 0

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

    }

#endif

    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_JT || op == OP_JF || 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 unary(Opcode op) {

        singleByteOp(op);

    }

    void pop() {

        singleByteOp(OP_POP);

    }

    void stop() {

        singleByteOp(OP_STOP);

    }

    void call(Handle<FunctionType> fun, unsigned argc) {

        recordOops();

        if (fun->isNative()) {

            ensure(OP_CALLNATIVE_LENGTH);

            writeOp(OP_CALLNATIVE);

            writeUint32(argc);

            drop(argc + 1);

        } else {

            ensure(OP_CALL_LENGTH);

            writeOp(OP_CALL);

            drop(argc + 1);

            if (fun->returnType()->isVoid())

                drop(1);

            else if (fun->returnType()->isTraceable())

                markOop(1);

        }

    }

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

    }

#if 0

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

    }

#endif

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

        if (op == OP_NEWSIZED)

            drop(map->type()->levels());

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

    }

#if 0

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

    }

#endif

    void slotref_lifo() {

        recordOops();

        singleByteOp(OP_SLOTREF_LIFO);

        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 sizeof_() {

        singleByteOp(OP_SIZEOF);

    }

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