diff options
Diffstat (limited to 'compiler/vm.nim')
| -rw-r--r-- | compiler/vm.nim | 584 |
1 files changed, 584 insertions, 0 deletions
diff --git a/compiler/vm.nim b/compiler/vm.nim new file mode 100644 index 000000000..72e0cb5b1 --- /dev/null +++ b/compiler/vm.nim @@ -0,0 +1,584 @@ +# +# +# The Nimrod Compiler +# (c) Copyright 2013 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## This file implements the new evaluation engine for Nimrod code. +## An instruction is 1-2 int32s in memory, it is a register based VM. + +import ast, astalgo, msgs, vmdef, vmgen, nimsets, types, passes, unsigned + +type + PStackFrame* = ref TStackFrame + TStackFrame* = object + prc: PSym # current prc; proc that is evaluated + slots: TNodeSeq # parameters passed to the proc + locals; + # parameters come first + next: PStackFrame # for stacking + comesFrom: int + safePoints: seq[int] # used for exception handling + # XXX 'break' should perform cleanup actions + # What does the C backend do for it? + +proc stackTraceAux(c: PCtx; x: PStackFrame; pc: int) = + if x != nil: + stackTraceAux(c, x.next, x.comesFrom) + var info = c.debug[pc] + # we now use the same format as in system/except.nim + var s = toFilename(info) + var line = toLineNumber(info) + if line > 0: + add(s, '(') + add(s, $line) + add(s, ')') + if x.prc != nil: + for k in 1..max(1, 25-s.len): add(s, ' ') + add(s, x.prc.name.s) + MsgWriteln(s) + +proc stackTrace(c: PCtx, tos: PStackFrame, pc: int, + msg: TMsgKind, arg = "") = + MsgWriteln("stack trace: (most recent call last)") + stackTraceAux(c, tos, pc) + LocalError(c.debug[pc], msg, arg) + +proc bailOut(c: PCtx; tos: PStackFrame) = + stackTrace(c, tos, c.exceptionInstr, errUnhandledExceptionX, + c.currentExceptionA.sons[2].strVal) + +when not defined(nimHasInterpreterLoop): + {.pragma: interpreterLoop.} + +template inc(pc: ptr TInstr, diff = 1) = + inc cast[TAddress](pc), TInstr.sizeof * diff + +template ensureKind(k: expr) {.immediate, dirty.} = + if regs[ra].kind != k: + myreset(regs[ra]) + regs[ra].kind = k + +template decodeB(k: expr) {.immediate, dirty.} = + let rb = instr.regB + ensureKind(k) + +template decodeBC(k: expr) {.immediate, dirty.} = + let rb = instr.regB + let rc = instr.regC + ensureKind(k) + +template decodeBImm(k: expr) {.immediate, dirty.} = + let rb = instr.regB + let imm = instr.regC - byteExcess + ensureKind(k) + +template decodeBx(k: expr) {.immediate, dirty.} = + let rbx = instr.regBx - wordExcess + ensureKind(k) + +proc compile(c: PCtx, s: PSym): int = vmgen.genProc(c, s) + +proc myreset(n: PNode) = + when defined(system.reset): + var oldInfo = n.info + reset(n[]) + n.info = oldInfo + +template move(a, b: expr) = system.shallowCopy(a, b) +# XXX fix minor 'shallowCopy' overloading bug in compiler + +proc asgnRef(x, y: PNode) = + myreset(x) + x.kind = y.kind + x.typ = y.typ + case x.kind + of nkCharLit..nkInt64Lit: x.intVal = y.intVal + of nkFloatLit..nkFloat64Lit: x.floatVal = y.floatVal + of nkStrLit..nkTripleStrLit: x.strVal = y.strVal + of nkIdent: x.ident = y.ident + of nkSym: x.sym = y.sym + else: + if x.kind notin {nkEmpty..nkNilLit}: + move(x.sons, y.sons) + +proc asgnComplex(x, y: PNode) = + myreset(x) + x.kind = y.kind + x.typ = y.typ + case x.kind + of nkCharLit..nkInt64Lit: x.intVal = y.intVal + of nkFloatLit..nkFloat64Lit: x.floatVal = y.floatVal + of nkStrLit..nkTripleStrLit: x.strVal = y.strVal + of nkIdent: x.ident = y.ident + of nkSym: x.sym = y.sym + else: + if x.kind notin {nkEmpty..nkNilLit}: + let y = y.copyTree + for i in countup(0, sonsLen(y) - 1): addSon(x, y.sons[i]) + +template getstr(a: expr): expr = + (if a.kind == nkStrLit: a.strVal else: $chr(int(a.intVal))) + +proc pushSafePoint(f: PStackFrame; pc: int) = + if f.safePoints.isNil: f.safePoints = @[] + f.safePoints.add(pc) + +proc popSafePoint(f: PStackFrame) = discard f.safePoints.pop() + +proc nextSafePoint(f: PStackFrame): int = + var f = f + while f.safePoints.isNil or f.safePoints.len == 0: + f = f.next + if f.isNil: return -1 + result = f.safePoints.pop + +proc cleanUpOnException(c: PCtx; tos: PStackFrame; regs: TNodeSeq): int = + let raisedType = c.currentExceptionA.typ.skipTypes(abstractPtrs) + while true: + var pc2 = tos.nextSafePoint + if pc2 == -1: return -1 + + var nextExceptOrFinally = -1 + if c.code[pc2].opcode == opcExcept: + nextExceptOrFinally = pc2 + c.code[pc2].regBx - wordExcess + inc pc2 + while c.code[pc2].opcode == opcExcept: + let exceptType = c.types[c.code[pc2].regBx-wordExcess].skipTypes( + abstractPtrs) + if inheritanceDiff(exceptType, raisedType) <= 0: + # mark exception as handled but keep it in B for + # the getCurrentException() builtin: + c.currentExceptionB = c.currentExceptionA + c.currentExceptionA = nil + # execute the corresponding handler: + return pc2 + inc pc2 + if nextExceptOrFinally >= 0: + pc2 = nextExceptOrFinally + if c.code[pc2].opcode == opcFinally: + # execute the corresponding handler, but don't quit walking the stack: + return pc2 + +proc cleanUpOnReturn(c: PCtx; f: PStackFrame): int = + if f.safePoints.isNil: return -1 + for s in f.safePoints: + var pc = s + while c.code[pc].opcode == opcExcept: + pc = pc + c.code[pc].regBx - wordExcess + if c.code[pc].opcode == opcFinally: + return pc + return -1 + +proc execute(c: PCtx, start: int) = + var pc = start + var regs: TNodeSeq # alias to tos.slots for performance + var tos: PStackFrame + newSeq(regs, c.prc.maxSlots) + while true: + {.interpreterLoop.} + let instr = c.code[pc] + let ra = instr.regA + echo "PC ", pc, " ", c.code[pc].opcode, " ra ", ra + case instr.opcode + of opcEof: break + of opcRet: + # XXX perform any cleanup actions + tos = tos.next + if tos.isNil: return + let retVal = regs[0] + move(regs, tos.slots) + pc = tos.comesFrom + assert c.code[pc].opcode in {opcIndCall, opcIndCallAsgn} + if c.code[pc].opcode == opcIndCallAsgn: + regs[c.code[pc].regA] = retVal + of opcYldYoid: assert false + of opcYldVal: assert false + of opcAsgnInt: + echo ra, " ", instr.regB, " ", regs.len, tos.prc.name.s + decodeB(nkIntLit) + regs[ra].intVal = regs[rb].intVal + of opcAsgnStr: + decodeB(nkStrLit) + debug regs[rb] + echo rb + Message(c.debug[pc], warnUser, " here") + regs[ra].strVal = regs[rb].strVal + of opcAsgnFloat: + decodeB(nkFloatLit) + regs[ra].floatVal = regs[rb].floatVal + of opcAsgnComplex: + asgnComplex(regs[ra], regs[instr.regB]) + of opcAsgnRef: + asgnRef(regs[ra], regs[instr.regB]) + of opcWrGlobalRef: + asgnRef(c.globals[instr.regBx-wordExcess-1], regs[ra]) + of opcWrGlobal: + asgnComplex(c.globals.sons[instr.regBx-wordExcess-1], regs[ra]) + of opcLdArr: + # a = b[c] + let rb = instr.regB + let rc = instr.regC + let idx = regs[rc].intVal + # XXX what if the array is not 0-based? -> codegen should insert a sub + regs[ra] = regs[rb].sons[idx.int] + of opcWrArr: + # a[b] = c + let rb = instr.regB + let rc = instr.regC + let idx = regs[rb].intVal + asgnComplex(regs[ra].sons[idx.int], regs[rc]) + of opcWrArrRef: + let rb = instr.regB + let rc = instr.regC + let idx = regs[rb].intVal + asgnRef(regs[ra].sons[idx.int], regs[rc]) + of opcLdObj: + # a = b.c + let rb = instr.regB + let rc = instr.regC + # XXX this creates a wrong alias + asgnComplex(regs[ra], regs[rb].sons[rc]) + of opcWrObj: + # a.b = c + let rb = instr.regB + let rc = instr.regC + asgnComplex(regs[ra].sons[rb], regs[rc]) + of opcWrObjRef: + let rb = instr.regB + let rc = instr.regC + asgnRef(regs[ra].sons[rb], regs[rc]) + of opcWrStrIdx: + decodeBC(nkStrLit) + let idx = regs[rb].intVal.int + regs[ra].strVal[idx] = chr(regs[rc].intVal) + of opcAddr: + decodeB(nkRefTy) + if regs[ra].len == 0: regs[ra].add regs[rb] + else: regs[ra].sons[0] = regs[rb] + of opcDeref: + # a = b[] + let rb = instr.regB + if regs[rb].kind == nkNilLit: + stackTrace(c, tos, pc, errNilAccess) + assert regs[rb].kind == nkRefTy + regs[ra] = regs[rb].sons[0] + of opcAddInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal + regs[rc].intVal + of opcAddImmInt: + decodeBImm(nkIntLit) + regs[ra].intVal = regs[rb].intVal + imm + of opcSubInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal - regs[rc].intVal + of opcSubImmInt: + decodeBImm(nkIntLit) + regs[ra].intVal = regs[rb].intVal - imm + of opcLenSeq: + decodeBImm(nkIntLit) + assert regs[rb].kind == nkBracket + regs[ra].intVal = regs[rb].len - imm + of opcLenStr: + decodeBImm(nkIntLit) + assert regs[rb].kind == nkStrLit + regs[ra].intVal = regs[rb].strVal.len - imm + of opcIncl: + decodeB(nkCurly) + if not inSet(regs[ra], regs[rb]): addSon(regs[ra], copyTree(regs[rb])) + of opcExcl: + decodeB(nkCurly) + # XXX arg we need types here :-( + var b = newNodeIT(nkCurly, regs[rb].info, regs[rb].typ) + addSon(b, regs[rb]) + var r = diffSets(regs[ra], b) + discardSons(regs[ra]) + for i in countup(0, sonsLen(r) - 1): addSon(regs[ra], r.sons[i]) + of opcCard: + decodeB(nkIntLit) + regs[ra].intVal = nimsets.cardSet(regs[rb]) + of opcMulInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal * regs[rc].intVal + of opcDivInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal div regs[rc].intVal + of opcModInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal mod regs[rc].intVal + of opcAddFloat: + decodeBC(nkFloatLit) + regs[ra].floatVal = regs[rb].floatVal + regs[rc].floatVal + of opcSubFloat: + decodeBC(nkFloatLit) + regs[ra].floatVal = regs[rb].floatVal - regs[rc].floatVal + of opcMulFloat: + decodeBC(nkFloatLit) + regs[ra].floatVal = regs[rb].floatVal * regs[rc].floatVal + of opcDivFloat: + decodeBC(nkFloatLit) + regs[ra].floatVal = regs[rb].floatVal / regs[rc].floatVal + of opcShrInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal shr regs[rc].intVal + of opcShlInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal shl regs[rc].intVal + of opcBitandInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal and regs[rc].intVal + of opcBitorInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal or regs[rc].intVal + of opcBitxorInt: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal xor regs[rc].intVal + of opcAddu: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal +% regs[rc].intVal + of opcSubu: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal -% regs[rc].intVal + of opcMulu: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal *% regs[rc].intVal + of opcDivu: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal /% regs[rc].intVal + of opcModu: + decodeBC(nkIntLit) + regs[ra].intVal = regs[rb].intVal %% regs[rc].intVal + of opcEqInt: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].intVal == regs[rc].intVal) + of opcLeInt: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].intVal <= regs[rc].intVal) + of opcLtInt: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].intVal < regs[rc].intVal) + of opcEqFloat: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].floatVal == regs[rc].floatVal) + of opcLeFloat: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].floatVal <= regs[rc].floatVal) + of opcLtFloat: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].floatVal < regs[rc].floatVal) + of opcLeu: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].intVal <=% regs[rc].intVal) + of opcLtu: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].intVal <% regs[rc].intVal) + of opcEqRef: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb] == regs[rc]) + # XXX is this correct? nope ... + of opcXor: + decodeBC(nkIntLit) + regs[ra].intVal = ord(regs[rb].intVal != regs[rc].intVal) + of opcNot: + decodeB(nkIntLit) + assert regs[rb].kind == nkIntLit + regs[ra].intVal = 1 - regs[rb].intVal + of opcUnaryMinusInt: + decodeB(nkIntLit) + assert regs[rb].kind == nkIntLit + regs[ra].intVal = -regs[rb].intVal + of opcUnaryMinusFloat: + decodeB(nkFloatLit) + assert regs[rb].kind == nkFloatLit + regs[ra].floatVal = -regs[rb].floatVal + of opcBitnotInt: + decodeB(nkIntLit) + assert regs[rb].kind == nkIntLit + regs[ra].intVal = not regs[rb].intVal + of opcEqStr: + decodeBC(nkIntLit) + regs[ra].intVal = Ord(regs[rb].strVal == regs[rc].strVal) + of opcLeStr: + decodeBC(nkIntLit) + regs[ra].intVal = Ord(regs[rb].strVal <= regs[rc].strVal) + of opcLtStr: + decodeBC(nkIntLit) + regs[ra].intVal = Ord(regs[rb].strVal < regs[rc].strVal) + of opcLeSet: + decodeBC(nkIntLit) + regs[ra].intVal = Ord(containsSets(regs[rb], regs[rc])) + of opcEqSet: + decodeBC(nkIntLit) + regs[ra].intVal = Ord(equalSets(regs[rb], regs[rc])) + of opcLtSet: + decodeBC(nkIntLit) + let a = regs[rb] + let b = regs[rc] + regs[ra].intVal = Ord(containsSets(a, b) and not equalSets(a, b)) + of opcMulSet: + decodeBC(nkCurly) + move(regs[ra].sons, nimsets.intersectSets(regs[rb], regs[rc]).sons) + of opcPlusSet: + decodeBC(nkCurly) + move(regs[ra].sons, nimsets.unionSets(regs[rb], regs[rc]).sons) + of opcMinusSet: + decodeBC(nkCurly) + move(regs[ra].sons, nimsets.diffSets(regs[rb], regs[rc]).sons) + of opcSymDiffSet: + decodeBC(nkCurly) + move(regs[ra].sons, nimsets.symdiffSets(regs[rb], regs[rc]).sons) + of opcConcatStr: + decodeBC(nkStrLit) + regs[ra].strVal = getstr(regs[rb]) + for i in rb+1..rb+rc-1: + regs[ra].strVal.add getstr(regs[i]) + of opcEcho: + echo regs[ra].strVal + of opcContainsSet: + decodeBC(nkIntLit) + regs[ra].intVal = Ord(inSet(regs[rb], regs[rc])) + of opcSubStr: + decodeBC(nkStrLit) + inc pc + assert c.code[pc].opcode == opcSubStr + let rd = c.code[pc].regA + regs[ra].strVal = substr(regs[rb].strVal, regs[rc].intVal.int, + regs[rd].intVal.int) + of opcIndCall, opcIndCallAsgn: + # dest = call regStart, n; where regStart = fn, arg1, ... + let rb = instr.regB + let rc = instr.regC + let prc = regs[rb].sym + let newPc = compile(c, prc) + var newFrame = PStackFrame(prc: prc, comesFrom: pc, next: tos) + newSeq(newFrame.slots, prc.position) + if not isEmptyType(prc.typ.sons[0]): + newFrame.slots[0] = getNullValue(prc.typ.sons[0], prc.info) + # pass every parameter by var (the language definition allows this): + for i in 1 .. rc-1: + newFrame.slots[i] = regs[rb+i] + # allocate the temporaries: + for i in rc .. <prc.position: + newFrame.slots[i] = newNode(nkEmpty) + tos = newFrame + move(regs, newFrame.slots) + pc = newPc + of opcTJmp: + # jump Bx if A != 0 + let rbx = instr.regBx - wordExcess - 1 # -1 for the following 'inc pc' + if regs[ra].intVal != 0: + inc pc, rbx + of opcFJmp: + # jump Bx if A == 0 + let rbx = instr.regBx - wordExcess - 1 # -1 for the following 'inc pc' + if regs[ra].intVal == 0: + inc pc, rbx + of opcJmp: + # jump Bx + let rbx = instr.regBx - wordExcess - 1 # -1 for the following 'inc pc' + inc pc, rbx + of opcBranch: + # we know the next instruction is a 'jmp': + let branch = c.constants[instr.regBx-wordExcess] + var cond = false + for j in countup(0, sonsLen(branch) - 2): + if overlap(regs[ra], branch.sons[j]): + cond = true + break + assert c.code[pc+1].opcode == opcJmp + inc pc + # we skip this instruction so that the final 'inc(pc)' skips + # the following jump + if cond: + let instr2 = c.code[pc] + let rbx = instr2.regBx - wordExcess - 1 # -1 for the following 'inc pc' + inc pc, rbx + of opcTry: + let rbx = instr.regBx - wordExcess + tos.pushSafePoint(pc + rbx) + of opcExcept: + # just skip it; it's followed by a jump; + # we'll execute in the 'raise' handler + discard + of opcFinally: + # just skip it; it's followed by the code we need to execute anyway + tos.popSafePoint() + of opcFinallyEnd: + if c.currentExceptionA != nil: + # we are in a cleanup run: + pc = cleanupOnException(c, tos, regs)-1 + if pc < 0: + bailOut(c, tos) + return + of opcRaise: + let raised = regs[ra] + c.currentExceptionA = raised + c.exceptionInstr = pc + # -1 because of the following 'inc' + pc = cleanupOnException(c, tos, regs) - 1 + if pc < 0: + bailOut(c, tos) + return + of opcNew: + let typ = c.types[instr.regBx - wordExcess] + regs[ra] = getNullValue(typ, regs[ra].info) + of opcNewSeq: + let typ = c.types[instr.regBx - wordExcess] + inc pc + ensureKind(nkBracket) + let instr2 = c.code[pc] + let rb = instr2.regA + regs[ra].typ = typ + newSeq(regs[ra].sons, rb) + for i in 0 .. <rb: + regs[ra].sons[i] = getNullValue(typ, regs[ra].info) + of opcNewStr: + decodeB(nkStrLit) + regs[ra].strVal = newString(regs[rb].intVal.int) + of opcLdImmInt: + # dest = immediate value + decodeBx(nkIntLit) + regs[ra].intVal = rbx + of opcLdNull: + let typ = c.types[instr.regBx - wordExcess] + regs[ra] = getNullValue(typ, c.debug[pc]) + of opcLdConst: + regs[ra] = c.constants.sons[instr.regBx - wordExcess] + of opcNBindSym: + # trivial implementation: + let rb = instr.regB + regs[ra] = regs[rb].sons[1] + else: + InternalError(c.debug[pc], "unknown opcode " & $instr.opcode) + inc pc + +proc eval*(c: PCtx, n: PNode): PNode = + ## eval never returns nil! This simplifies the code a lot and + ## makes it faster too. + let start = genStmt(c, n) + # execute new instructions; this redundant opcEof check saves us lots + # of allocations in 'execute': + if c.code[start].opcode != opcEof: + execute(c, start) + result = emptyNode + +proc myOpen(module: PSym): PPassContext = + #var c = newEvalContext(module, emRepl) + #c.features = {allowCast, allowFFI, allowInfiniteLoops} + #pushStackFrame(c, newStackFrame()) + result = newCtx() + +var oldErrorCount: int + +proc myProcess(c: PPassContext, n: PNode): PNode = + # don't eval errornous code: + if oldErrorCount == msgs.gErrorCounter: + result = eval(PCtx(c), n) + else: + result = n + oldErrorCount = msgs.gErrorCounter + +const vmPass* = makePass(myOpen, nil, myProcess, myProcess) + |