src/compiler/BytecodeEmitter.h
author David Anderson <dvander@alliedmods.net>
Sun Jan 06 13:52:21 2013 -0800 (2013-01-06)
changeset 256 3c184218462d
parent 247 7721042bdb67
child 262 c4b1341297e5
permissions -rw-r--r--
Initial implementation of module imports.
     1 /* vim: set ts=4 sw=4 tw=99 et:
     2  *
     3  * Copyright (C) 2012 David Anderson
     4  *
     5  * This file is part of JITCraft.
     6  *
     7  * JITCraft is free software: you can redistribute it and/or modify it under
     8  * the terms of the GNU General Public License as published by the Free
     9  * Software Foundation, either version 3 of the License, or (at your option)
    10  * any later version.
    11  * 
    12  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
    13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
    15  *
    16  * You should have received a copy of the GNU General Public License along with
    17  * JITCraft. If not, see http://www.gnu.org/licenses/.
    18  */
    19 #ifndef _include_bytecode_emitter_h_
    20 #define _include_bytecode_emitter_h_
    21 
    22 #include <assert.h>
    23 #include <limits.h>
    24 #include "../Opcodes.h"
    25 #include "../Handles.h"
    26 #include "../CompactBuffer.h"
    27 #include "../Array.h"
    28 #include "../HashTable.h"
    29 #include "../VirtualObjectVisitor.h"
    30 
    31 namespace ke {
    32 
    33 // An overarching note on overflows: Though we should use CheckedInt, we rely
    34 // on a source-length cap covering all possible overflow checks. As long as
    35 // the source length is capped to INT_MAX, the number of AST nodes will be
    36 // strictly beneath that cap, and so to will most things generated by the
    37 // AST. For example, local and argument counts, number of functions, fields
    38 // in a struct, et cetera. Not everything can be covered by this cap: the
    39 // stack depth, number of bytecodes for example. In these cases we explicitly
    40 // test for overflow of INT_MAX and in other cases we assert.
    41 //
    42 // In the future, we should of course use a checked int wrapper.
    43 
    44 class Type;
    45 class Map;
    46 class ArrayMap;
    47 class Symbol;
    48 class VariableSymbol;
    49 
    50 struct OopRecord
    51 {
    52     unsigned depth;
    53     unsigned offset;
    54     Vector<bool> slots;
    55 
    56     OopRecord(unsigned length, unsigned offset)
    57       : depth(length),
    58         offset(offset)
    59     {
    60     }
    61 };
    62 
    63 class StringTable
    64 {
    65     struct Entry
    66     {
    67         String *string;
    68         unsigned index;
    69 
    70         Entry()
    71           : string(NULL),
    72             index(0)
    73         {
    74         }
    75 
    76         Entry(String *string, unsigned index)
    77           : string(string),
    78             index(index)
    79         {
    80         }
    81     };
    82 
    83     struct Policy
    84     {
    85         typedef Entry Payload;
    86 
    87         static uint32 hash(String *string) {
    88             return HashPointer(string);
    89         }
    90         
    91         static bool matches(String *key, Entry &e) {
    92             return key == e.string;
    93         }
    94     };
    95 
    96     typedef HashTable<Policy, ZoneAllocatorPolicy> Set;
    97 
    98   public:
    99     StringTable();
   100     bool initialize();
   101     void accept(VirtualObjectVisitor *visitor);
   102 
   103     bool add(Handle<String> name, unsigned *indexp);
   104     size_t stringCount() const {
   105         return strings_.length();
   106     }
   107     String *stringAt(size_t i) const {
   108         return strings_[i].string;
   109     }
   110 
   111   private:
   112     Set set_;
   113     Vector<Entry> strings_;
   114     bool initialized_;
   115 };
   116 
   117 // The bytecode emitter assists in building Code objects, by emitting opcodes
   118 // and tracking stack information. Since the SemA creates temporary pool/root
   119 // scopes, we cannot use ScopedRoot or PoolObjects. Instead, BCE gets a
   120 // special marking function.
   121 class BytecodeEmitter : public AutoRooted
   122 {
   123   private:
   124     PoolAllocator &pool_;
   125 
   126     bytecode *buffer_;
   127     bytecode *buffer_pos_;
   128     bytecode *buffer_end_;
   129     bytecode inline_buffer_[512];
   130     bool oom_;
   131     unsigned maxStackDepth_;
   132     Vector<bool> oopMap_;
   133     Vector<OopRecord *> oopRecords_;
   134     CompactBufferWriter sourcemap_;
   135     unsigned lastCodePosition_;
   136     unsigned firstLine_;
   137     StringTable strings_;
   138     Vector<Symbol *> locals_;
   139     Vector<Object *> objects_;
   140     unsigned loopDepth_;
   141     unsigned maxLoopDepth_;
   142 
   143   private:
   144     // The maximum size of a code object must be such that the distance between
   145     // two instructions fits into a signed, 31-bit integer. This ensures that
   146     // all code-bounded buffers (like the number of object literals or
   147     // safepoints) does not need to be bounds checked. It also means we can add
   148     // any two offsets and be guaranteed that they don't overflow.
   149     static const size_t MAX_LENGTH = INT_MAX / 2;
   150 
   151   private:
   152     bool growBuffer(size_t bytes);
   153 
   154     // Checking the return value is not necessary, since the inline buffer is
   155     // used as a ballast.
   156     bool ensure(size_t bytes) {
   157         if (buffer_pos_ + bytes > buffer_end_)
   158             return growBuffer(bytes);
   159         return true;
   160     }
   161 
   162     void writeUint8(unsigned value) {
   163         assert(value <= UCHAR_MAX);
   164         *buffer_pos_++ = value;
   165     }
   166     void writeFloat(float value) {
   167         *(float *)buffer_pos_ = value;
   168         buffer_pos_ += sizeof(float);
   169     }
   170     void writeInt32(int value) {
   171         *(int *)buffer_pos_ = value;
   172         buffer_pos_ += sizeof(int);
   173     }
   174     void writeUint32(unsigned value) {
   175         *(unsigned *)buffer_pos_ = value;
   176         buffer_pos_ += sizeof(unsigned);
   177     }
   178     void writeOp(Opcode op) {
   179         if (oom_)
   180             return;
   181 
   182         writeUint8(op);
   183         for (int i = 0; i < OpcodeInfo[op].nuses; i++)
   184             oopMap_.pop();
   185         for (int i = 0; i < OpcodeInfo[op].ndefs; i++)
   186             oopMap_.append(false);
   187         if (oopMap_.length() > maxStackDepth_)
   188             maxStackDepth_ = oopMap_.length();
   189     }
   190     void writeObject(Object *obj) {
   191         assert(obj);
   192 
   193         writeUint32(objects_.length());
   194         if (!objects_.append(obj))
   195             oom_ = true;
   196     }
   197 
   198     int position() const {
   199         assert(buffer_pos_ - buffer_ < INT_MAX / 2);
   200         return int(buffer_pos_ - buffer_);
   201     }
   202 
   203   public:
   204     BytecodeEmitter(PoolAllocator &pool);
   205     ~BytecodeEmitter();
   206 
   207     void accept(VirtualObjectVisitor *visitor);
   208 
   209     bytecode *buffer() const {
   210         return buffer_;
   211     }
   212     unsigned length() const {
   213         return unsigned(buffer_pos_ - buffer_);
   214     }
   215     bool oom() const {
   216         return oom_ || sourcemap_.oom();
   217     }
   218     unsigned stackDepth() const {
   219         return oopMap_.length();
   220     }
   221     unsigned maxStackDepth() const {
   222         return maxStackDepth_;
   223     }
   224 
   225     void drop(unsigned amt) {
   226         assert(amt <= stackDepth());
   227         for (unsigned i = 0; i < amt; i++)
   228             oopMap_.pop();
   229     }
   230 
   231     void note_position(const SourcePosition &pos);
   232     void setFirstLine(unsigned line) {
   233         assert(!sourcemap_.length());
   234         firstLine_ = line;
   235     }
   236 
   237   public:
   238     // A label represents a local control-flow target in the bytecode. A label
   239     // may be in three states:
   240     //
   241     // (1) Empty - the label is not used yet.
   242     // (2) Pending - the label has incoming jumps, but the actual location of
   243     //               is not yet known. The list of jumps is threaded through
   244     //               the four bytes reserved for each emitted jump target. In
   245     //               this case, the offset field is the location of the most
   246     //               recently emitted incoming jump.
   247     // (3) Bound   - the label's position has been pinned.
   248     //
   249     // A jump can be emitted to a label in any state. Binding a label
   250     // immediately backpatches all pending incoming jumps. A label must be
   251     // bound if it is used.
   252     class Label
   253     {
   254         int offset_ : 31;
   255         bool bound_ : 1;
   256 
   257         void setOffset(int offset) {
   258             offset_ = offset;
   259             assert(offset_ == offset);
   260         }
   261 
   262       public:
   263         static const int INVALID_OFFSET = -1;
   264 
   265       public:
   266         Label()
   267           : offset_(INVALID_OFFSET),
   268             bound_(false)
   269         {
   270         }
   271         ~Label()
   272         {
   273             assert(bound_ || offset_ == INVALID_OFFSET);
   274         }
   275         
   276         bool bound() const {
   277             return bound_;
   278         }
   279         int offset() const {
   280             return offset_;
   281         }
   282         void bind(int offset) {
   283             assert(!bound_);
   284             setOffset(offset);
   285             bound_ = true;
   286         }
   287         int link(int offset) {
   288             assert(!bound_);
   289             int old = offset_;
   290             setOffset(offset);
   291             return old;
   292         }
   293     };
   294 
   295   private:
   296     int patchJumpAt(int at, int to) {
   297         assert(at >= 0 && at < position());
   298         int old = *(int *)(buffer_ + at + 1);
   299         *(int *)(buffer_ + at + 1) = (to - at);
   300         return old;
   301     }
   302 
   303     void singleByteOp(Opcode op) {
   304         assert(OpcodeInfo[op].length == 1);
   305         ensure(OpcodeInfo[op].length);
   306         writeOp(op);
   307     }
   308 
   309     // Mark a stack slot as having an object pointer.
   310     void markOop(unsigned depth, bool oop = true) {
   311         if (oom_)
   312             return;
   313         oopMap_[oopMap_.length() - depth] = oop;
   314     }
   315     bool getOop(unsigned depth) {
   316         if (oom_)
   317             return false;
   318         return oopMap_[oopMap_.length() - depth];
   319     }
   320 
   321     // Mark the current bytecode position as either re-entrant (meaning, it
   322     // can leave the interpreter or call to another function), or causing GC.
   323     // This will record which stack slots have objects and associate that
   324     // information with the current pc.
   325     void recordOops();
   326 
   327   public:
   328     void int_(int value) {
   329         ensure(OP_INT);
   330         writeOp(OP_INT);
   331         writeInt32(value);
   332     }
   333     void return_() {
   334         ensure(OP_RETURN);
   335         writeOp(OP_RETURN);
   336     }
   337     void getlocal(VariableSymbol *var);
   338     void setlocal(VariableSymbol *var);
   339     void getarg(VariableSymbol *var);
   340     void setarg(VariableSymbol *var);
   341 
   342     void j(Opcode op, Label *label) {
   343         // Since jumps can skip around the stream, do not try to do anything
   344         // in a potentially truncated state.
   345         if (oom())
   346             return;
   347 
   348         assert(op == OP_JT || op == OP_JF || op == OP_JUMP ||
   349                op == OP_CONTINUE || op == OP_BREAK);
   350         ensure(OP_JUMP_LENGTH);
   351 
   352         if (label->bound()) {
   353             // We can immediately emit this jump.
   354             int distance = label->offset() - position();
   355             writeOp(op);
   356             writeInt32(distance);
   357         } else {
   358             // We can't emit this jump yet. Add a placeholder.
   359             int old = label->link(position());
   360             writeOp(op);
   361             writeInt32(old);
   362         }
   363     }
   364     void bind(Label *label) {
   365         if (oom())
   366             return;
   367 
   368         assert(!label->bound());
   369 
   370         int offset = label->offset();
   371         while (offset != Label::INVALID_OFFSET)
   372             offset = patchJumpAt(offset, position());
   373 
   374         label->bind(position());
   375     }
   376     void jump(Label *label) {
   377         j(OP_JUMP, label);
   378     }
   379 
   380     void binary(Opcode op) {
   381         singleByteOp(op);
   382     }
   383     void unary(Opcode op) {
   384         singleByteOp(op);
   385     }
   386 
   387     void pop() {
   388         singleByteOp(OP_POP);
   389     }
   390     void stop() {
   391         singleByteOp(OP_STOP);
   392     }
   393     void call(Handle<FunctionType> fun, unsigned argc) {
   394         recordOops();
   395 
   396         if (fun->isNative()) {
   397             ensure(OP_CALLNATIVE_LENGTH);
   398             writeOp(OP_CALLNATIVE);
   399             writeUint32(argc);
   400             drop(argc + 1);
   401         } else {
   402             ensure(OP_CALL_LENGTH);
   403             writeOp(OP_CALL);
   404             drop(argc + 1);
   405 
   406             if (fun->returnType()->isVoid())
   407                 drop(1);
   408             else if (fun->returnType()->isTraceable())
   409                 markOop(1);
   410         }
   411     }
   412 
   413     void getelem(Type *type) {
   414         singleByteOp(OP_GETELEM);
   415 
   416         if (type->isTraceable())
   417             markOop(1);
   418     }
   419     void setelem(Type *type) {
   420         singleByteOp(OP_SETELEM);
   421     }
   422 
   423     void getfield(unsigned index, Type *type) {
   424         ensure(OP_GETFIELD_LENGTH);
   425         writeOp(OP_GETFIELD);
   426         writeUint32(index);
   427 
   428         if (type->isTraceable())
   429             markOop(1);
   430     }
   431     void setfield(unsigned index, Type *type) {
   432         ensure(OP_SETFIELD_LENGTH);
   433         writeOp(OP_SETFIELD);
   434         writeUint32(index);
   435 
   436         if (type->isTraceable())
   437             markOop(1);
   438     }
   439 
   440     int enterloop() {
   441         int offset = position();
   442 
   443         ensure(OP_ENTERLOOP);
   444         writeOp(OP_ENTERLOOP);
   445         writeUint8(0);
   446 
   447         loopDepth_++;
   448         if (loopDepth_ > maxLoopDepth_)
   449             maxLoopDepth_ = loopDepth_;
   450 
   451         return offset;
   452     }
   453     void leaveloop() {
   454         singleByteOp(OP_LEAVELOOP);
   455 
   456         assert(loopDepth_);
   457         loopDepth_--;
   458     }
   459     void setLoopUsesLifoStack(int pos) {
   460         assert(pos >= 0 && pos < position());
   461         assert(*(buffer() + pos) == OP_ENTERLOOP);
   462         *(buffer() + pos + 1) = 1;
   463     }
   464 
   465     void float_(float value) {
   466         ensure(OP_FLOAT_LENGTH);
   467         writeOp(OP_FLOAT);
   468         writeFloat(value);
   469     }
   470     void cvt_i2f() {
   471         singleByteOp(OP_CVT_I2F);
   472     }
   473     void newarray(Opcode op, Handle<ArrayMap> map, Heap::Tenure tenure) {
   474         assert(op == OP_NEWFIXED ||
   475                op == OP_NEWEMPTY ||
   476                op == OP_NEWSIZED);
   477 
   478         recordOops();
   479         ensure(OpcodeInfo[op].length);
   480         writeOp(op);
   481         writeUint8(tenure);
   482         writeObject(map);
   483 
   484         if (op == OP_NEWSIZED)
   485             drop(map->type()->levels());
   486 
   487         markOop(1);
   488     }
   489     void newstruct(Handle<Map> map, Heap::Tenure tenure) {
   490         recordOops();
   491         ensure(OP_NEWSTRUCT_LENGTH);
   492         writeOp(OP_NEWSTRUCT);
   493         writeUint8(tenure);
   494         writeObject(map);
   495         markOop(1);
   496     }
   497     void deparray(ArrayMap *map) {
   498         recordOops();
   499         ensure(OP_DEPARRAY_LENGTH);
   500         writeOp(OP_DEPARRAY);
   501         writeObject(map);
   502         markOop(1);
   503     }
   504     void savelifo(unsigned slot) {
   505         ensure(OP_SAVELIFO_LENGTH);
   506         writeOp(OP_SAVELIFO);
   507         writeUint32(slot);
   508     }
   509     void unwindlifo(unsigned slot) {
   510         ensure(OP_UNWINDLIFO_LENGTH);
   511         writeOp(OP_UNWINDLIFO);
   512         writeUint32(slot);
   513     }
   514 
   515     void newref(VariableSymbol *var);
   516 
   517     void slotref_lifo() {
   518         recordOops();
   519         singleByteOp(OP_SLOTREF_LIFO);
   520         markOop(1);
   521     }
   522     void getref(Type *type) {
   523         if (type->pod() == PrimitiveType_Int32) {
   524             singleByteOp(OP_GETREF_I);
   525         } else {
   526             assert(type->pod() == PrimitiveType_Float);
   527             singleByteOp(OP_GETREF_F);
   528         }
   529     }
   530     void setref(Type *type) {
   531         if (type->pod() == PrimitiveType_Int32) {
   532             singleByteOp(OP_SETREF_I);
   533         } else {
   534             assert(type->pod() == PrimitiveType_Float);
   535             singleByteOp(OP_SETREF_F);
   536         }
   537     }
   538     void object(Handle<Object> obj) {
   539         assert(obj);
   540 
   541         ensure(OP_OBJECT_LENGTH);
   542         writeOp(OP_OBJECT);
   543         writeObject(obj);
   544         markOop(1);
   545     }
   546     void duparray() {
   547         singleByteOp(OP_DUPARRAY);
   548         markOop(1);
   549     }
   550     void copyarray() {
   551         singleByteOp(OP_COPYARRAY);
   552         markOop(1);
   553     }
   554     void copystruct() {
   555         singleByteOp(OP_COPYSTRUCT);
   556         markOop(1);
   557     }
   558     void sizeof_() {
   559         singleByteOp(OP_SIZEOF);
   560     }
   561 
   562     void dup() {
   563         bool oop = getOop(1);
   564         singleByteOp(OP_DUP);
   565         markOop(1, oop);
   566     }
   567     void dup2() {
   568         bool oop2 = getOop(2);
   569         bool oop1 = getOop(1);
   570 
   571         singleByteOp(OP_DUP2);
   572 
   573         markOop(2, oop2);
   574         markOop(1, oop1);
   575     }
   576     void swap() {
   577         bool oop2 = getOop(2);
   578         bool oop1 = getOop(1);
   579 
   580         singleByteOp(OP_SWAP);
   581 
   582         markOop(2, oop1);
   583         markOop(1, oop2);
   584     }
   585     void roll3() {
   586         bool oop3 = getOop(3);
   587         bool oop2 = getOop(2);
   588         bool oop1 = getOop(1);
   589 
   590         singleByteOp(OP_ROLL3);
   591 
   592         markOop(3, oop2);
   593         markOop(2, oop1);
   594         markOop(1, oop3);
   595     }
   596     void pick2() {
   597         bool oop2 = getOop(2);
   598         bool oop1 = getOop(1);
   599 
   600         singleByteOp(OP_PICK2);
   601 
   602         markOop(3, oop2);
   603         markOop(2, oop1);
   604         markOop(1, oop2);
   605     }
   606     void pick3() {
   607         bool oop3 = getOop(3);
   608         bool oop2 = getOop(2);
   609         bool oop1 = getOop(1);
   610 
   611         singleByteOp(OP_PICK3);
   612 
   613         markOop(4, oop3);
   614         markOop(3, oop2);
   615         markOop(2, oop1);
   616         markOop(1, oop3);
   617     }
   618 
   619     void returnvoid() {
   620         singleByteOp(OP_RETURNVOID);
   621     }
   622     void bitnot() {
   623         singleByteOp(OP_BITNOT);
   624     }
   625     void not_() {
   626         singleByteOp(OP_NOT);
   627     }
   628     void not_f() {
   629         singleByteOp(OP_NOT_F);
   630     }
   631     void neg() {
   632         singleByteOp(OP_NEG);
   633     }
   634     void neg_f() {
   635         singleByteOp(OP_NEG_F);
   636     }
   637     void true_() {
   638         singleByteOp(OP_TRUE);
   639     }
   640     void false_() {
   641         singleByteOp(OP_FALSE);
   642     }
   643     
   644     unsigned addString(Handle<String> name) {
   645         unsigned index;
   646         if (!strings_.add(name, &index)) {
   647             oom_ |= true;
   648             return 0;
   649         }
   650         return index;
   651     }
   652 
   653     void getglobal(Symbol *sym);
   654     void setglobal(Symbol *sym);
   655 
   656     void public_() {
   657         recordOops();
   658         singleByteOp(OP_PUBLIC);
   659     }
   660 
   661     void bitcast(Type *type) {
   662         ensure(OP_BITCAST_LENGTH);
   663         writeOp(OP_BITCAST);
   664         writeObject(type);
   665     }
   666 
   667     void tableswitch(int low, int high, Label *def, Label **labels) {
   668         unsigned tablesize = TableSwitchEntries(low, high);
   669         assert(tablesize <= MAX_TABLESWITCH_ENTRIES);
   670 
   671         ensure(OP_TABLESWITCH_LENGTH);
   672         writeOp(OP_TABLESWITCH);
   673         writeInt32(low);
   674         writeInt32(high);
   675         jump(def);
   676 
   677         // When labels are patched, we assume each position is a jump. Rather
   678         // than hack position offsets to make labels work without actual
   679         // incoming jumps, we emit a jump inline.
   680         for (unsigned i = 0; i < tablesize; i++)
   681             jump(labels[i]);
   682     }
   683 
   684     void import(unsigned index) {
   685         ensure(OP_IMPORT_LENGTH);
   686         writeOp(OP_IMPORT);
   687         writeUint32(index);
   688         markOop(1);
   689     }
   690 
   691     bool allocate(VariableSymbol *sym);
   692 
   693     Code *finish();
   694 
   695     // Helpers.
   696 #if 0
   697     void get(Variable *var) {
   698         if (var->location() == Variable::STACK) {
   699             getlocal(var);
   700         } else {
   701             assert(var->location() == Variable::PARAMETER);
   702             getarg(var);
   703         }
   704     }
   705     void set(Variable *var) {
   706         assert(!var->type()->isReference());
   707         if (var->location() == Variable::STACK) {
   708             setlocal(var);
   709         } else {
   710             assert(var->location() == Variable::PARAMETER);
   711             setarg(var);
   712         }
   713     }
   714 #endif
   715 };
   716 
   717 }
   718 
   719 #endif // _include_bytecode_emitter_h_