1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/BytecodeEmitter.h Tue Jul 24 23:53:34 2012 -0700
1.3 @@ -0,0 +1,626 @@
1.4 +/* vim: set ts=4 sw=4 tw=99 et:
1.5 + *
1.6 + * Copyright (C) 2012 David Anderson
1.7 + *
1.8 + * This file is part of JITCraft.
1.9 + *
1.10 + * JITCraft is free software: you can redistribute it and/or modify it under
1.11 + * the terms of the GNU General Public License as published by the Free
1.12 + * Software Foundation, either version 3 of the License, or (at your option)
1.13 + * any later version.
1.14 + *
1.15 + * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
1.16 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License along with
1.20 + * JITCraft. If not, see http://www.gnu.org/licenses/.
1.21 + */
1.22 +#ifndef _include_bytecode_emitter_h_
1.23 +#define _include_bytecode_emitter_h_
1.24 +
1.25 +#include <assert.h>
1.26 +#include <limits.h>
1.27 +#include "Opcodes.h"
1.28 +#include "NameBinding.h"
1.29 +#include "Handles.h"
1.30 +#include "CompactBuffer.h"
1.31 +
1.32 +namespace ke {
1.33 +
1.34 +class Type;
1.35 +class Map;
1.36 +
1.37 +typedef PoolList<ScopedRoot<Object>> ObjectList;
1.38 +
1.39 +struct OopRecord : public PoolObject
1.40 +{
1.41 + unsigned depth;
1.42 + unsigned offset;
1.43 + bool *slots;
1.44 +
1.45 + OopRecord(unsigned length, unsigned offset)
1.46 + : depth(length),
1.47 + offset(offset),
1.48 + slots(NULL)
1.49 + {
1.50 + }
1.51 +};
1.52 +
1.53 +class BytecodeEmitter
1.54 +{
1.55 + private:
1.56 + PoolAllocator &pool_;
1.57 +
1.58 + bytecode *buffer_;
1.59 + bytecode *buffer_pos_;
1.60 + bytecode *buffer_end_;
1.61 + bytecode inline_buffer_[512];
1.62 + bool oom_;
1.63 + unsigned maxStackDepth_;
1.64 + ObjectList objects_;
1.65 + PoolList<bool> oopMap_;
1.66 + PoolList<OopRecord *> oopRecords_;
1.67 + CompactBufferWriter sourcemap_;
1.68 + unsigned lastCodePosition_;
1.69 + unsigned firstLine_;
1.70 +
1.71 + private:
1.72 + // The maximum size of a code object must be such that the distance between
1.73 + // two instructions fits into a signed, 31-bit integer. This ensures that
1.74 + // all code-bounded buffers (like the number of object literals or
1.75 + // safepoints) does not need to be bounds checked. It also means we can add
1.76 + // any two offsets and be guaranteed that they don't overflow.
1.77 + static const size_t MAX_LENGTH = INT_MAX / 2;
1.78 +
1.79 + private:
1.80 + bool growBuffer(size_t bytes);
1.81 +
1.82 + // Checking the return value is not necessary, since the inline buffer is
1.83 + // used as a ballast.
1.84 + bool ensure(size_t bytes) {
1.85 + if (buffer_pos_ + bytes > buffer_end_)
1.86 + return growBuffer(bytes);
1.87 + return true;
1.88 + }
1.89 +
1.90 + void writeUint8(unsigned value) {
1.91 + assert(value <= UCHAR_MAX);
1.92 + *buffer_pos_++ = value;
1.93 + }
1.94 + void writeFloat(float value) {
1.95 + *(float *)buffer_pos_ = value;
1.96 + buffer_pos_ += sizeof(float);
1.97 + }
1.98 + void writeInt32(int value) {
1.99 + *(int *)buffer_pos_ = value;
1.100 + buffer_pos_ += sizeof(int);
1.101 + }
1.102 + void writeUint32(unsigned value) {
1.103 + *(unsigned *)buffer_pos_ = value;
1.104 + buffer_pos_ += sizeof(unsigned);
1.105 + }
1.106 + void writeOp(Opcode op) {
1.107 + if (oom_)
1.108 + return;
1.109 +
1.110 + writeUint8(op);
1.111 + for (int i = 0; i < OpcodeInfo[op].nuses; i++)
1.112 + oopMap_.pop();
1.113 + for (int i = 0; i < OpcodeInfo[op].ndefs; i++)
1.114 + oopMap_.append(false);
1.115 + if (oopMap_.length() > maxStackDepth_)
1.116 + maxStackDepth_ = oopMap_.length();
1.117 + }
1.118 + void writeObject(Object *obj) {
1.119 + writeUint32(objects_.length());
1.120 + ScopedRoot<Object> root(obj);
1.121 + if (!objects_.append(root))
1.122 + oom_ = true;
1.123 + }
1.124 +
1.125 + int position() const {
1.126 + assert(buffer_pos_ - buffer_ < INT_MAX / 2);
1.127 + return int(buffer_pos_ - buffer_);
1.128 + }
1.129 +
1.130 + public:
1.131 + BytecodeEmitter(PoolAllocator &pool);
1.132 +
1.133 + bytecode *buffer() const {
1.134 + return buffer_;
1.135 + }
1.136 + unsigned length() const {
1.137 + return unsigned(buffer_pos_ - buffer_);
1.138 + }
1.139 + bool oom() const {
1.140 + return oom_ || sourcemap_.oom();
1.141 + }
1.142 + unsigned stackDepth() const {
1.143 + return oopMap_.length();
1.144 + }
1.145 + unsigned maxStackDepth() const {
1.146 + return maxStackDepth_;
1.147 + }
1.148 + const ObjectList *objects() const {
1.149 + return &objects_;
1.150 + }
1.151 + PoolList<OopRecord *> *oopRecords() {
1.152 + return &oopRecords_;
1.153 + }
1.154 +
1.155 + void drop(unsigned amt) {
1.156 + assert(amt <= stackDepth());
1.157 + for (unsigned i = 0; i < amt; i++)
1.158 + oopMap_.pop();
1.159 + }
1.160 +
1.161 + void note_position(const SourcePosition &pos);
1.162 + uint8 *sourcemap() const {
1.163 + return sourcemap_.buffer();
1.164 + }
1.165 + size_t sourcemapLength() const {
1.166 + return sourcemap_.length();
1.167 + }
1.168 + void setFirstLine(unsigned line) {
1.169 + assert(!sourcemap_.length());
1.170 + firstLine_ = line;
1.171 + }
1.172 +
1.173 + public:
1.174 + // A label represents a local control-flow target in the bytecode. A label
1.175 + // may be in three states:
1.176 + //
1.177 + // (1) Empty - the label is not used yet.
1.178 + // (2) Pending - the label has incoming jumps, but the actual location of
1.179 + // is not yet known. The list of jumps is threaded through
1.180 + // the four bytes reserved for each emitted jump target. In
1.181 + // this case, the offset field is the location of the most
1.182 + // recently emitted incoming jump.
1.183 + // (3) Bound - the label's position has been pinned.
1.184 + //
1.185 + // A jump can be emitted to a label in any state. Binding a label
1.186 + // immediately backpatches all pending incoming jumps. A label must be
1.187 + // bound if it is used.
1.188 + class Label
1.189 + {
1.190 + int offset_ : 31;
1.191 + bool bound_ : 1;
1.192 +
1.193 + void setOffset(int offset) {
1.194 + offset_ = offset;
1.195 + assert(offset_ == offset);
1.196 + }
1.197 +
1.198 + public:
1.199 + static const int INVALID_OFFSET = -1;
1.200 +
1.201 + public:
1.202 + Label()
1.203 + : offset_(INVALID_OFFSET),
1.204 + bound_(false)
1.205 + {
1.206 + }
1.207 + ~Label()
1.208 + {
1.209 + assert(bound_ || offset_ == INVALID_OFFSET);
1.210 + }
1.211 +
1.212 + bool bound() const {
1.213 + return bound_;
1.214 + }
1.215 + int offset() const {
1.216 + return offset_;
1.217 + }
1.218 + void bind(int offset) {
1.219 + assert(!bound_);
1.220 + setOffset(offset);
1.221 + bound_ = true;
1.222 + }
1.223 + int link(int offset) {
1.224 + assert(!bound_);
1.225 + int old = offset_;
1.226 + setOffset(offset);
1.227 + return old;
1.228 + }
1.229 + };
1.230 +
1.231 + private:
1.232 + int patchJumpAt(int at, int to) {
1.233 + assert(at >= 0 && at < position());
1.234 + int old = *(int *)(buffer_ + at + 1);
1.235 + *(int *)(buffer_ + at + 1) = (to - at);
1.236 + return old;
1.237 + }
1.238 +
1.239 + void singleByteOp(Opcode op) {
1.240 + assert(OpcodeInfo[op].length == 1);
1.241 + ensure(OpcodeInfo[op].length);
1.242 + writeOp(op);
1.243 + }
1.244 +
1.245 + // Mark a stack slot as having an object pointer.
1.246 + void markOop(unsigned depth, bool oop = true) {
1.247 + if (oom_)
1.248 + return;
1.249 + oopMap_[oopMap_.length() - depth] = oop;
1.250 + }
1.251 + bool getOop(unsigned depth) {
1.252 + if (oom_)
1.253 + return false;
1.254 + return oopMap_[oopMap_.length() - depth];
1.255 + }
1.256 +
1.257 + // Mark the current bytecode position as either re-entrant (meaning, it
1.258 + // can leave the interpreter or call to another function), or causing GC.
1.259 + // This will record which stack slots have objects and associate that
1.260 + // information with the current pc.
1.261 + void recordOops();
1.262 +
1.263 + public:
1.264 + void int_(int value) {
1.265 + ensure(OP_INT);
1.266 + writeOp(OP_INT);
1.267 + writeInt32(value);
1.268 + }
1.269 + void return_() {
1.270 + ensure(OP_RETURN);
1.271 + writeOp(OP_RETURN);
1.272 + }
1.273 + void getlocal(Variable *var) {
1.274 + ensure(OP_GETLOCAL_LENGTH);
1.275 + writeOp(OP_GETLOCAL);
1.276 + writeUint32(var->slot());
1.277 +
1.278 + if (var->type()->isTraceable())
1.279 + markOop(1);
1.280 + }
1.281 + void setlocal(Variable *var) {
1.282 + ensure(OP_SETLOCAL_LENGTH);
1.283 + writeOp(OP_SETLOCAL);
1.284 + writeUint32(var->slot());
1.285 +
1.286 + if (var->type()->isTraceable())
1.287 + markOop(1);
1.288 + }
1.289 + void getarg(Variable *var) {
1.290 + ensure(OP_GETARG_LENGTH);
1.291 + writeOp(OP_GETARG);
1.292 + writeUint32(var->slot());
1.293 +
1.294 + if (var->type()->isTraceable())
1.295 + markOop(1);
1.296 + }
1.297 + void setarg(Variable *var) {
1.298 + ensure(OP_SETARG_LENGTH);
1.299 + writeOp(OP_SETARG);
1.300 + writeUint32(var->slot());
1.301 +
1.302 + if (var->type()->isTraceable())
1.303 + markOop(1);
1.304 + }
1.305 +
1.306 + void j(Opcode op, Label *label) {
1.307 + // Since jumps can skip around the stream, do not try to do anything
1.308 + // in a potentially truncated state.
1.309 + if (oom())
1.310 + return;
1.311 +
1.312 + assert(op >= OP_JL && op <= OP_JUMP);
1.313 + ensure(OP_JUMP_LENGTH);
1.314 +
1.315 + if (label->bound()) {
1.316 + // We can immediately emit this jump.
1.317 + int distance = label->offset() - position();
1.318 + writeOp(op);
1.319 + writeInt32(distance);
1.320 + } else {
1.321 + // We can't emit this jump yet. Add a placeholder.
1.322 + int old = label->link(position());
1.323 + writeOp(op);
1.324 + writeInt32(old);
1.325 + }
1.326 + }
1.327 + void bind(Label *label) {
1.328 + if (oom())
1.329 + return;
1.330 +
1.331 + assert(!label->bound());
1.332 +
1.333 + int offset = label->offset();
1.334 + while (offset != Label::INVALID_OFFSET)
1.335 + offset = patchJumpAt(offset, position());
1.336 +
1.337 + label->bind(position());
1.338 + }
1.339 + void jump(Label *label) {
1.340 + j(OP_JUMP, label);
1.341 + }
1.342 +
1.343 + void binary(Opcode op) {
1.344 + singleByteOp(op);
1.345 + }
1.346 +
1.347 + void pop() {
1.348 + singleByteOp(OP_POP);
1.349 + }
1.350 + void stop() {
1.351 + singleByteOp(OP_STOP);
1.352 + }
1.353 + void call(Handle<Type> fun) {
1.354 + recordOops();
1.355 + ensure(OP_CALL_LENGTH);
1.356 + writeOp(OP_CALL);
1.357 +
1.358 + if (fun->returnType()->isVoid())
1.359 + drop(1);
1.360 + else if (fun->returnType()->isTraceable())
1.361 + markOop(1);
1.362 + }
1.363 + void callnative(unsigned index, unsigned argc) {
1.364 + recordOops();
1.365 + ensure(OP_CALLNATIVE_LENGTH);
1.366 + writeOp(OP_CALLNATIVE);
1.367 + writeUint32(index);
1.368 + writeUint32(argc);
1.369 + }
1.370 +
1.371 + void getarray(PrimitiveType type) {
1.372 + switch (type) {
1.373 + case PrimitiveType_Float:
1.374 + singleByteOp(OP_GETARRAY_F);
1.375 + break;
1.376 + case PrimitiveType_Int32:
1.377 + singleByteOp(OP_GETARRAY_I);
1.378 + break;
1.379 + default:
1.380 + assert(type == PrimitiveType_Char);
1.381 + singleByteOp(OP_GETARRAY_C);
1.382 + break;
1.383 + }
1.384 + }
1.385 + void setarray(PrimitiveType type) {
1.386 + switch (type) {
1.387 + case PrimitiveType_Float:
1.388 + singleByteOp(OP_SETARRAY_F);
1.389 + break;
1.390 + case PrimitiveType_Int32:
1.391 + singleByteOp(OP_SETARRAY_I);
1.392 + break;
1.393 + default:
1.394 + assert(type == PrimitiveType_Char);
1.395 + singleByteOp(OP_SETARRAY_C);
1.396 + break;
1.397 + }
1.398 + }
1.399 +
1.400 + void getglobal(Variable *var) {
1.401 + ensure(OP_GETGLOBAL_F_LENGTH);
1.402 + if (var->type()->isPrimitive()) {
1.403 + switch (var->type()->primitive()) {
1.404 + case PrimitiveType_Float:
1.405 + writeOp(OP_GETGLOBAL_F);
1.406 + break;
1.407 + default:
1.408 + assert(var->type()->primitive() == PrimitiveType_Int32);
1.409 + writeOp(OP_GETGLOBAL_I);
1.410 + break;
1.411 + }
1.412 + } else {
1.413 + writeOp(OP_GETGLOBAL_O);
1.414 + markOop(1);
1.415 + }
1.416 + writeUint32(var->slot());
1.417 + }
1.418 + void setglobal(Variable *var) {
1.419 + ensure(OP_SETGLOBAL_F_LENGTH);
1.420 + if (var->type()->isPrimitive()) {
1.421 + switch (var->type()->primitive()) {
1.422 + case PrimitiveType_Float:
1.423 + writeOp(OP_SETGLOBAL_F);
1.424 + break;
1.425 + default:
1.426 + assert(var->type()->primitive() == PrimitiveType_Int32);
1.427 + writeOp(OP_SETGLOBAL_I);
1.428 + break;
1.429 + }
1.430 + } else {
1.431 + writeOp(OP_SETGLOBAL_O);
1.432 + }
1.433 + writeUint32(var->slot());
1.434 + }
1.435 +
1.436 + void getarray_o() {
1.437 + singleByteOp(OP_GETARRAY_O);
1.438 + markOop(1);
1.439 + }
1.440 + void bounds() {
1.441 + singleByteOp(OP_BOUNDS);
1.442 + markOop(2);
1.443 + }
1.444 + void float_(float value) {
1.445 + ensure(OP_FLOAT_LENGTH);
1.446 + writeOp(OP_FLOAT);
1.447 + writeFloat(value);
1.448 + }
1.449 + void cvt_i2f() {
1.450 + singleByteOp(OP_CVT_I2F);
1.451 + }
1.452 + void newarray(Handle<Map> map, Heap::Tenure tenure) {
1.453 + recordOops();
1.454 + ensure(OP_NEWARRAY_LENGTH);
1.455 + writeOp(OP_NEWARRAY);
1.456 + writeUint8(tenure);
1.457 + writeObject(map);
1.458 + markOop(1);
1.459 + }
1.460 + void savelifo(unsigned slot) {
1.461 + ensure(OP_SAVELIFO_LENGTH);
1.462 + writeOp(OP_SAVELIFO);
1.463 + writeUint32(slot);
1.464 + }
1.465 + void unwindlifo(unsigned slot) {
1.466 + ensure(OP_UNWINDLIFO_LENGTH);
1.467 + writeOp(OP_UNWINDLIFO);
1.468 + writeUint32(slot);
1.469 + }
1.470 + void newref(Variable *var) {
1.471 + recordOops();
1.472 + if (var->location() == Variable::STACK) {
1.473 + ensure(OP_VARREF_LIFO_LENGTH);
1.474 + writeOp(OP_VARREF_LIFO);
1.475 + } else {
1.476 + assert(var->location() == Variable::PARAMETER);
1.477 + ensure(OP_ARGREF_LIFO_LENGTH);
1.478 + writeOp(OP_ARGREF_LIFO);
1.479 + }
1.480 + writeUint32(var->slot());
1.481 + markOop(1);
1.482 + }
1.483 +
1.484 + void slotref_lifo() {
1.485 + recordOops();
1.486 + singleByteOp(OP_SLOTREF_LIFO);
1.487 + markOop(1);
1.488 + }
1.489 + void arrayref_lifo() {
1.490 + recordOops();
1.491 + singleByteOp(OP_ARRAYREF_LIFO);
1.492 + markOop(1);
1.493 + }
1.494 + void getref(PrimitiveType type) {
1.495 + if (type == PrimitiveType_Int32) {
1.496 + singleByteOp(OP_GETREF_I);
1.497 + } else {
1.498 + assert(type == PrimitiveType_Float);
1.499 + singleByteOp(OP_GETREF_F);
1.500 + }
1.501 + }
1.502 + void setref(PrimitiveType type) {
1.503 + if (type == PrimitiveType_Int32) {
1.504 + singleByteOp(OP_SETREF_I);
1.505 + } else {
1.506 + assert(type == PrimitiveType_Float);
1.507 + singleByteOp(OP_SETREF_F);
1.508 + }
1.509 + }
1.510 + void object(Handle<Object> obj) {
1.511 + ensure(OP_OBJECT_LENGTH);
1.512 + writeOp(OP_OBJECT);
1.513 + writeObject(obj);
1.514 + markOop(1);
1.515 + }
1.516 + void arraycopy() {
1.517 + singleByteOp(OP_ARRAYCOPY);
1.518 + markOop(1);
1.519 + }
1.520 +
1.521 + void dup() {
1.522 + bool oop = getOop(1);
1.523 + singleByteOp(OP_DUP);
1.524 + markOop(1, oop);
1.525 + }
1.526 + void dup2() {
1.527 + bool oop2 = getOop(2);
1.528 + bool oop1 = getOop(1);
1.529 +
1.530 + singleByteOp(OP_DUP2);
1.531 +
1.532 + markOop(2, oop2);
1.533 + markOop(1, oop1);
1.534 + }
1.535 + void swap() {
1.536 + bool oop2 = getOop(2);
1.537 + bool oop1 = getOop(1);
1.538 +
1.539 + singleByteOp(OP_SWAP);
1.540 +
1.541 + markOop(2, oop1);
1.542 + markOop(1, oop2);
1.543 + }
1.544 + void roll3() {
1.545 + bool oop3 = getOop(3);
1.546 + bool oop2 = getOop(2);
1.547 + bool oop1 = getOop(1);
1.548 +
1.549 + singleByteOp(OP_ROLL3);
1.550 +
1.551 + markOop(3, oop2);
1.552 + markOop(2, oop1);
1.553 + markOop(1, oop3);
1.554 + }
1.555 + void pick2() {
1.556 + bool oop2 = getOop(2);
1.557 + bool oop1 = getOop(1);
1.558 +
1.559 + singleByteOp(OP_PICK2);
1.560 +
1.561 + markOop(3, oop2);
1.562 + markOop(2, oop1);
1.563 + markOop(1, oop2);
1.564 + }
1.565 + void pick3() {
1.566 + bool oop3 = getOop(3);
1.567 + bool oop2 = getOop(2);
1.568 + bool oop1 = getOop(1);
1.569 +
1.570 + singleByteOp(OP_PICK3);
1.571 +
1.572 + markOop(4, oop3);
1.573 + markOop(3, oop2);
1.574 + markOop(2, oop1);
1.575 + markOop(1, oop3);
1.576 + }
1.577 +
1.578 + void returnvoid() {
1.579 + singleByteOp(OP_RETURNVOID);
1.580 + }
1.581 + void module() {
1.582 + singleByteOp(OP_MODULE);
1.583 + markOop(1);
1.584 + }
1.585 + void getmodule_fn(unsigned index) {
1.586 + ensure(OP_GETMODULE_FN_LENGTH);
1.587 + writeOp(OP_GETMODULE_FN);
1.588 + writeUint32(index);
1.589 + markOop(1);
1.590 + }
1.591 + void bitnot() {
1.592 + singleByteOp(OP_BITNOT);
1.593 + }
1.594 + void not_() {
1.595 + singleByteOp(OP_NOT);
1.596 + }
1.597 + void not_f() {
1.598 + singleByteOp(OP_NOT_F);
1.599 + }
1.600 + void neg() {
1.601 + singleByteOp(OP_NEG);
1.602 + }
1.603 + void neg_f() {
1.604 + singleByteOp(OP_NEG_F);
1.605 + }
1.606 +
1.607 + // Helpers.
1.608 + void get(Variable *var) {
1.609 + if (var->location() == Variable::STACK) {
1.610 + getlocal(var);
1.611 + } else {
1.612 + assert(var->location() == Variable::PARAMETER);
1.613 + getarg(var);
1.614 + }
1.615 + }
1.616 + void set(Variable *var) {
1.617 + assert(!var->type()->isReference());
1.618 + if (var->location() == Variable::STACK) {
1.619 + setlocal(var);
1.620 + } else {
1.621 + assert(var->location() == Variable::PARAMETER);
1.622 + setarg(var);
1.623 + }
1.624 + }
1.625 +};
1.626 +
1.627 +}
1.628 +
1.629 +#endif // _include_bytecode_emitter_h_
