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

     unsigned loopDepth_;

     unsigned maxLoopDepth_;

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

     void getarg(VariableSymbol *var);

     void setarg(VariableSymbol *var);

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

                op == OP_CONTINUE || op == OP_BREAK);

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

     }

     int enterloop() {

         int offset = position();

         ensure(OP_ENTERLOOP);

         writeOp(OP_ENTERLOOP);

         writeUint8(0);

         loopDepth_++;

         if (loopDepth_ > maxLoopDepth_)

             maxLoopDepth_ = loopDepth_;

         return offset;

     }

     void leaveloop() {

         singleByteOp(OP_LEAVELOOP);

         assert(loopDepth_);

         loopDepth_--;

     }

     void setLoopUsesLifoStack(int pos) {

         assert(pos >= 0 && pos < position());

         assert(*(buffer() + pos) == OP_ENTERLOOP);

         *(buffer() + pos + 1) = 1;

     }

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

     }

     void newref(VariableSymbol *var);

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

     }

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

     }

     unsigned addString(Handle<String> name) {

         unsigned index;

         if (!strings_.add(name, &index)) {

             oom_ |= true;

             return 0;

         }

         return index;

     }

     void getglobal(Symbol *sym);

     void setglobal(Symbol *sym);

     void public_() {

         recordOops();

         singleByteOp(OP_PUBLIC);

     }

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

     }

     bool allocate(VariableSymbol *sym);

     Code *finish();

     // Helpers.

 #if 0

     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

 };

 }

 #endif // _include_bytecode_emitter_h_