diff options
| author | Andreas Rumpf <rumpf_a@web.de> | 2023-10-11 17:44:14 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-10-11 17:44:14 +0200 |
| commit | 816589b6674e3af281766f1279420758dcacedc4 (patch) | |
| tree | 3e4f825e29e2068466a35edc69cc27967b743687 /compiler/nir | |
| parent | ecaccafa6c18e0b92cd5f75d3363d61c0866dec9 (diff) | |
| download | Nim-816589b6674e3af281766f1279420758dcacedc4.tar.gz | |
NIR: Nim intermediate representation (#22777)
Theoretical Benefits / Plans: - Typed assembler-like language. - Allows for a CPS transformation. - Can replace the existing C backend by a new C backend. - Can replace the VM. - Can do more effective "not nil" checking and static array bounds checking. - Can be used instead of the DFA. - Easily translatable to LLVM. - Reasonably easy to produce native code from. - Tiny memory consumption. No pointers, no cry. **In very early stages of development.** Todo: - [x] Map Nim types to IR types. - [ ] Map Nim AST to IR instructions: - [x] Map bitsets to bitops. - [ ] Implement string cases. - [ ] Implement range and index checks. - [x] Implement `default(T)` builtin. - [x] Implement multi string concat. - [ ] Write some analysis passes. - [ ] Write a backend. - [x] Integrate into the compilation pipeline.
Diffstat (limited to 'compiler/nir')
| -rw-r--r-- | compiler/nir/ast2ir.nim | 2189 | ||||
| -rw-r--r-- | compiler/nir/cir.nim | 78 | ||||
| -rw-r--r-- | compiler/nir/nir.nim | 71 | ||||
| -rw-r--r-- | compiler/nir/nirinsts.nim | 418 | ||||
| -rw-r--r-- | compiler/nir/nirlineinfos.nim | 78 | ||||
| -rw-r--r-- | compiler/nir/nirslots.nim | 105 | ||||
| -rw-r--r-- | compiler/nir/nirtypes.nim | 347 | ||||
| -rw-r--r-- | compiler/nir/types2ir.nim | 466 |
8 files changed, 3752 insertions, 0 deletions
diff --git a/compiler/nir/ast2ir.nim b/compiler/nir/ast2ir.nim new file mode 100644 index 000000000..f06bb3ae8 --- /dev/null +++ b/compiler/nir/ast2ir.nim @@ -0,0 +1,2189 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +import std / [assertions, tables, sets] +import ".." / [ast, astalgo, types, options, lineinfos, msgs, magicsys, + modulegraphs, guards, renderer, transf, bitsets, trees, nimsets, + expanddefaults] +from ".." / lowerings import lowerSwap, lowerTupleUnpacking +from ".." / pathutils import customPath +import .. / ic / bitabs + +import nirtypes, nirinsts, nirlineinfos, nirslots, types2ir + +type + ModuleCon* = ref object + strings*: BiTable[string] + integers*: BiTable[int64] + man*: LineInfoManager + types*: TypesCon + slotGenerator: ref int + module*: PSym + graph*: ModuleGraph + nativeIntId, nativeUIntId: TypeId + idgen: IdGenerator + pendingProcs: Table[ItemId, PSym] # procs we still need to generate code for + + ProcCon* = object + config: ConfigRef + lastFileKey: FileIndex + lastFileVal: LitId + labelGen: int + exitLabel: LabelId + code*: Tree + blocks: seq[(PSym, LabelId)] + sm: SlotManager + locGen: int + m: ModuleCon + prc: PSym + +proc initModuleCon*(graph: ModuleGraph; config: ConfigRef; idgen: IdGenerator; module: PSym): ModuleCon = + result = ModuleCon(graph: graph, types: initTypesCon(config), slotGenerator: new(int), + idgen: idgen, module: module) + case config.target.intSize + of 2: + result.nativeIntId = Int16Id + result.nativeUIntId = UInt16Id + of 4: + result.nativeIntId = Int32Id + result.nativeUIntId = UInt16Id + else: + result.nativeIntId = Int64Id + result.nativeUIntId = UInt16Id + +proc initProcCon*(m: ModuleCon; prc: PSym; config: ConfigRef): ProcCon = + ProcCon(m: m, sm: initSlotManager({}, m.slotGenerator), prc: prc, config: config) + +proc toLineInfo(c: var ProcCon; i: TLineInfo): PackedLineInfo = + var val: LitId + if c.lastFileKey == i.fileIndex: + val = c.lastFileVal + else: + val = c.m.strings.getOrIncl(toFullPath(c.config, i.fileIndex)) + # remember the entry: + c.lastFileKey = i.fileIndex + c.lastFileVal = val + result = pack(c.m.man, val, int32 i.line, int32 i.col) + +proc bestEffort(c: ProcCon): TLineInfo = + if c.prc != nil: + c.prc.info + else: + c.m.module.info + +proc popBlock(c: var ProcCon; oldLen: int) = + c.blocks.setLen(oldLen) + +template withBlock(labl: PSym; info: PackedLineInfo; asmLabl: LabelId; body: untyped) {.dirty.} = + var oldLen {.gensym.} = c.blocks.len + c.blocks.add (labl, asmLabl) + body + popBlock(c, oldLen) + +type + GenFlag = enum + gfAddrOf # load the address of the expression + gfToOutParam # the expression is passed to an `out` parameter + GenFlags = set[GenFlag] + +proc gen(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags = {}) + +proc genScope(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags = {}) = + openScope c.sm + gen c, n, d, flags + closeScope c.sm + +proc freeTemp(c: var ProcCon; tmp: Value) = + let s = extractTemp(tmp) + if s != SymId(-1): + freeTemp(c.sm, s) + +proc getTemp(c: var ProcCon; n: PNode): Value = + let info = toLineInfo(c, n.info) + let t = typeToIr(c.m.types, n.typ) + let tmp = allocTemp(c.sm, t) + c.code.addSummon info, tmp, t + result = localToValue(info, tmp) + +template withTemp(tmp, n, body: untyped) {.dirty.} = + var tmp = getTemp(c, n) + body + c.freeTemp(tmp) + +proc gen(c: var ProcCon; n: PNode; flags: GenFlags = {}) = + var tmp = default(Value) + gen(c, n, tmp, flags) + freeTemp c, tmp + +proc genScope(c: var ProcCon; n: PNode; flags: GenFlags = {}) = + openScope c.sm + gen c, n, flags + closeScope c.sm + +proc genx(c: var ProcCon; n: PNode; flags: GenFlags = {}): Value = + result = default(Value) + gen(c, n, result, flags) + assert Tree(result).len > 0, $n + +proc clearDest(c: var ProcCon; n: PNode; d: var Value) {.inline.} = + when false: + if n.typ.isNil or n.typ.kind == tyVoid: + let s = extractTemp(d) + if s != SymId(-1): + freeLoc(c.sm, s) + +proc isNotOpr(n: PNode): bool = + n.kind in nkCallKinds and n[0].kind == nkSym and n[0].sym.magic == mNot + +proc jmpBack(c: var ProcCon; n: PNode; lab: LabelId) = + c.code.gotoLabel toLineInfo(c, n.info), GotoLoop, lab + +type + JmpKind = enum opcFJmp, opcTJmp + +proc xjmp(c: var ProcCon; n: PNode; jk: JmpKind; v: Value): LabelId = + result = newLabel(c.labelGen) + let info = toLineInfo(c, n.info) + buildTyped c.code, info, Select, Bool8Id: + c.code.copyTree Tree(v) + build c.code, info, SelectPair: + build c.code, info, SelectValue: + c.code.boolVal(info, jk == opcTJmp) + c.code.gotoLabel info, Goto, result + +proc patch(c: var ProcCon; n: PNode; L: LabelId) = + addLabel c.code, toLineInfo(c, n.info), Label, L + +proc genWhile(c: var ProcCon; n: PNode) = + # lab1: + # cond, tmp + # fjmp tmp, lab2 + # body + # jmp lab1 + # lab2: + let info = toLineInfo(c, n.info) + let lab1 = c.code.addNewLabel(c.labelGen, info, LoopLabel) + withBlock(nil, info, lab1): + if isTrue(n[0]): + c.gen(n[1]) + c.jmpBack(n, lab1) + elif isNotOpr(n[0]): + var tmp = c.genx(n[0][1]) + let lab2 = c.xjmp(n, opcTJmp, tmp) + c.freeTemp(tmp) + c.gen(n[1]) + c.jmpBack(n, lab1) + c.patch(n, lab2) + else: + var tmp = c.genx(n[0]) + let lab2 = c.xjmp(n, opcFJmp, tmp) + c.freeTemp(tmp) + c.gen(n[1]) + c.jmpBack(n, lab1) + c.patch(n, lab2) + +proc genBlock(c: var ProcCon; n: PNode; d: var Value) = + openScope c.sm + let info = toLineInfo(c, n.info) + let lab1 = newLabel(c.labelGen) + + withBlock(n[0].sym, info, lab1): + c.gen(n[1], d) + + c.code.addLabel(info, Label, lab1) + closeScope c.sm + c.clearDest(n, d) + +proc jumpTo(c: var ProcCon; n: PNode; L: LabelId) = + c.code.addLabel(toLineInfo(c, n.info), Goto, L) + +proc genBreak(c: var ProcCon; n: PNode) = + if n[0].kind == nkSym: + for i in countdown(c.blocks.len-1, 0): + if c.blocks[i][0] == n[0].sym: + c.jumpTo n, c.blocks[i][1] + return + localError(c.config, n.info, "NIR problem: cannot find 'break' target") + else: + c.jumpTo n, c.blocks[c.blocks.high][1] + +proc genIf(c: var ProcCon; n: PNode; d: var Value) = + # if (!expr1) goto lab1; + # thenPart + # goto LEnd + # lab1: + # if (!expr2) goto lab2; + # thenPart2 + # goto LEnd + # lab2: + # elsePart + # Lend: + if isEmpty(d) and not isEmptyType(n.typ): d = getTemp(c, n) + var ending = newLabel(c.labelGen) + for i in 0..<n.len: + var it = n[i] + if it.len == 2: + let info = toLineInfo(c, it[0].info) + withTemp(tmp, it[0]): + var elsePos: LabelId + if isNotOpr(it[0]): + c.gen(it[0][1], tmp) + elsePos = c.xjmp(it[0][1], opcTJmp, tmp) # if true + else: + c.gen(it[0], tmp) + elsePos = c.xjmp(it[0], opcFJmp, tmp) # if false + c.clearDest(n, d) + if isEmptyType(it[1].typ): # maybe noreturn call, don't touch `d` + c.genScope(it[1]) + else: + c.genScope(it[1], d) # then part + if i < n.len-1: + c.jumpTo it[1], ending + c.patch(it, elsePos) + else: + c.clearDest(n, d) + if isEmptyType(it[0].typ): # maybe noreturn call, don't touch `d` + c.genScope(it[0]) + else: + c.genScope(it[0], d) + c.patch(n, ending) + c.clearDest(n, d) + +proc tempToDest(c: var ProcCon; n: PNode; d: var Value; tmp: Value) = + if isEmpty(d): + d = tmp + else: + let info = toLineInfo(c, n.info) + build c.code, info, Asgn: + c.code.addTyped info, typeToIr(c.m.types, n.typ) + c.code.copyTree d + c.code.copyTree tmp + freeTemp(c, tmp) + +proc genAndOr(c: var ProcCon; n: PNode; opc: JmpKind; d: var Value) = + # asgn d, a + # tjmp|fjmp lab1 + # asgn d, b + # lab1: + var tmp = getTemp(c, n) + c.gen(n[1], tmp) + let lab1 = c.xjmp(n, opc, tmp) + c.gen(n[2], tmp) + c.patch(n, lab1) + tempToDest c, n, d, tmp + +proc unused(c: var ProcCon; n: PNode; x: Value) {.inline.} = + if hasValue(x): + #debug(n) + localError(c.config, n.info, "not unused") + +proc caseValue(c: var ProcCon; n: PNode) = + let info = toLineInfo(c, n.info) + build c.code, info, SelectValue: + let x = genx(c, n) + c.code.copyTree x + freeTemp(c, x) + +proc caseRange(c: var ProcCon; n: PNode) = + let info = toLineInfo(c, n.info) + build c.code, info, SelectRange: + let x = genx(c, n[0]) + let y = genx(c, n[1]) + c.code.copyTree x + c.code.copyTree y + freeTemp(c, y) + freeTemp(c, x) + +proc genCase(c: var ProcCon; n: PNode; d: var Value) = + if not isEmptyType(n.typ): + if isEmpty(d): d = getTemp(c, n) + else: + unused(c, n, d) + var sections = newSeqOfCap[LabelId](n.len-1) + let ending = newLabel(c.labelGen) + let info = toLineInfo(c, n.info) + withTemp(tmp, n[0]): + build c.code, info, Select: + c.code.addTyped info, typeToIr(c.m.types, n[0].typ) + c.gen(n[0], tmp) + for i in 1..<n.len: + let section = newLabel(c.labelGen) + sections.add section + let it = n[i] + let itinfo = toLineInfo(c, it.info) + build c.code, itinfo, SelectPair: + build c.code, itinfo, SelectList: + for j in 0..<it.len-1: + if it[j].kind == nkRange: + caseRange c, it[j] + else: + caseValue c, it[j] + c.code.addLabel itinfo, Goto, section + for i in 1..<n.len: + let it = n[i] + let itinfo = toLineInfo(c, it.info) + c.code.addLabel itinfo, Label, sections[i-1] + c.gen it.lastSon + if i != n.len-1: + c.code.addLabel itinfo, Goto, ending + c.code.addLabel info, Label, ending + +proc rawCall(c: var ProcCon; info: PackedLineInfo; opc: Opcode; t: TypeId; args: var openArray[Value]) = + build c.code, info, opc: + c.code.addTyped info, t + if opc in {CheckedCall, CheckedIndirectCall}: + c.code.addLabel info, CheckedGoto, c.exitLabel + for a in mitems(args): + c.code.copyTree a + freeTemp c, a + +proc canRaiseDisp(c: ProcCon; n: PNode): bool = + # we assume things like sysFatal cannot raise themselves + if n.kind == nkSym and {sfNeverRaises, sfImportc, sfCompilerProc} * n.sym.flags != {}: + result = false + elif optPanics in c.config.globalOptions or + (n.kind == nkSym and sfSystemModule in getModule(n.sym).flags and + sfSystemRaisesDefect notin n.sym.flags): + # we know we can be strict: + result = canRaise(n) + else: + # we have to be *very* conservative: + result = canRaiseConservative(n) + +proc genCall(c: var ProcCon; n: PNode; d: var Value) = + let canRaise = canRaiseDisp(c, n[0]) + + let opc = if n[0].kind == nkSym and n[0].sym.kind in routineKinds: + (if canRaise: CheckedCall else: Call) + else: + (if canRaise: CheckedIndirectCall else: IndirectCall) + let info = toLineInfo(c, n.info) + + # In the IR we cannot nest calls. Thus we use two passes: + var args: seq[Value] = @[] + var t = n[0].typ + if t != nil: t = t.skipTypes(abstractInst) + args.add genx(c, n[0]) + for i in 1..<n.len: + if t != nil and i < t.len: + if isCompileTimeOnly(t[i]): discard + elif isOutParam(t[i]): args.add genx(c, n[i], {gfToOutParam}) + else: args.add genx(c, n[i]) + else: + args.add genx(c, n[i]) + + let tb = typeToIr(c.m.types, n.typ) + if not isEmptyType(n.typ): + if isEmpty(d): d = getTemp(c, n) + # XXX Handle problematic aliasing here: `a = f_canRaise(a)`. + build c.code, info, Asgn: + c.code.addTyped info, tb + c.code.copyTree d + rawCall c, info, opc, tb, args + else: + rawCall c, info, opc, tb, args + +proc genRaise(c: var ProcCon; n: PNode) = + let info = toLineInfo(c, n.info) + let tb = typeToIr(c.m.types, n[0].typ) + + let d = genx(c, n[0]) + build c.code, info, SetExc: + c.code.addTyped info, tb + c.code.copyTree d + c.freeTemp(d) + c.code.addLabel info, Goto, c.exitLabel + +proc genReturn(c: var ProcCon; n: PNode) = + if n[0].kind != nkEmpty: + gen(c, n[0]) + # XXX Block leave actions? + let info = toLineInfo(c, n.info) + c.code.addLabel info, Goto, c.exitLabel + +proc genTry(c: var ProcCon; n: PNode; d: var Value) = + if isEmpty(d) and not isEmptyType(n.typ): d = getTemp(c, n) + var endings: seq[LabelId] = @[] + let ehPos = newLabel(c.labelGen) + let oldExitLab = c.exitLabel + c.exitLabel = ehPos + if isEmptyType(n[0].typ): # maybe noreturn call, don't touch `d` + c.gen(n[0]) + else: + c.gen(n[0], d) + c.clearDest(n, d) + + # Add a jump past the exception handling code + let jumpToFinally = newLabel(c.labelGen) + c.jumpTo n, jumpToFinally + # This signals where the body ends and where the exception handling begins + c.patch(n, ehPos) + c.exitLabel = oldExitLab + for i in 1..<n.len: + let it = n[i] + if it.kind != nkFinally: + # first opcExcept contains the end label of the 'except' block: + let endExcept = newLabel(c.labelGen) + for j in 0..<it.len - 1: + assert(it[j].kind == nkType) + let typ = it[j].typ.skipTypes(abstractPtrs-{tyTypeDesc}) + let itinfo = toLineInfo(c, it[j].info) + build c.code, itinfo, TestExc: + c.code.addTyped itinfo, typeToIr(c.m.types, typ) + if it.len == 1: + let itinfo = toLineInfo(c, it.info) + build c.code, itinfo, TestExc: + c.code.addTyped itinfo, VoidId + let body = it.lastSon + if isEmptyType(body.typ): # maybe noreturn call, don't touch `d` + c.gen(body) + else: + c.gen(body, d) + c.clearDest(n, d) + if i < n.len: + endings.add newLabel(c.labelGen) + c.patch(it, endExcept) + let fin = lastSon(n) + # we always generate an 'opcFinally' as that pops the safepoint + # from the stack if no exception is raised in the body. + c.patch(fin, jumpToFinally) + #c.gABx(fin, opcFinally, 0, 0) + for endPos in endings: c.patch(n, endPos) + if fin.kind == nkFinally: + c.gen(fin[0]) + c.clearDest(n, d) + #c.gABx(fin, opcFinallyEnd, 0, 0) + +template isGlobal(s: PSym): bool = sfGlobal in s.flags and s.kind != skForVar +proc isGlobal(n: PNode): bool = n.kind == nkSym and isGlobal(n.sym) + +proc genField(c: var ProcCon; n: PNode; d: var Value) = + var pos: int + if n.kind != nkSym or n.sym.kind != skField: + localError(c.config, n.info, "no field symbol") + pos = 0 + else: + pos = n.sym.position + d.addImmediateVal toLineInfo(c, n.info), pos + +proc genIndex(c: var ProcCon; n: PNode; arr: PType; d: var Value) = + if arr.skipTypes(abstractInst).kind == tyArray and + (let x = firstOrd(c.config, arr); x != Zero): + let info = toLineInfo(c, n.info) + buildTyped d, info, Sub, c.m.nativeIntId: + c.gen(n, d) + d.addImmediateVal toLineInfo(c, n.info), toInt(x) + else: + c.gen(n, d) + +proc genNew(c: var ProcCon; n: PNode; needsInit: bool) = + # If in doubt, always follow the blueprint of the C code generator for `mm:orc`. + let refType = n[1].typ.skipTypes(abstractInstOwned) + assert refType.kind == tyRef + let baseType = refType.lastSon + + let info = toLineInfo(c, n.info) + let codegenProc = magicsys.getCompilerProc(c.m.graph, + if needsInit: "nimNewObj" else: "nimNewObjUninit") + let x = genx(c, n[1]) + let refTypeIr = typeToIr(c.m.types, refType) + buildTyped c.code, info, Asgn, refTypeIr: + copyTree c.code, x + buildTyped c.code, info, Cast, refTypeIr: + buildTyped c.code, info, Call, VoidPtrId: + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + c.code.addImmediateVal info, int(getSize(c.config, baseType)) + c.code.addImmediateVal info, int(getAlign(c.config, baseType)) + +proc genNewSeqOfCap(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let seqtype = skipTypes(n.typ, abstractVarRange) + let baseType = seqtype.lastSon + var a = c.genx(n[1]) + if isEmpty(d): d = getTemp(c, n) + # $1.len = 0 + buildTyped c.code, info, Asgn, c.m.nativeIntId: + buildTyped c.code, info, FieldAt, c.m.nativeIntId: + copyTree c.code, d + c.code.addImmediateVal info, 0 + c.code.addImmediateVal info, 0 + # $1.p = ($4*) #newSeqPayloadUninit($2, sizeof($3), NIM_ALIGNOF($3)) + let payloadPtr = seqPayloadPtrType(c.m.types, seqtype) + buildTyped c.code, info, Asgn, payloadPtr: + # $1.p + buildTyped c.code, info, FieldAt, payloadPtr: + copyTree c.code, d + c.code.addImmediateVal info, 1 + # ($4*) #newSeqPayloadUninit($2, sizeof($3), NIM_ALIGNOF($3)) + buildTyped c.code, info, Cast, payloadPtr: + buildTyped c.code, info, Call, VoidPtrId: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "newSeqPayloadUninit") + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + copyTree c.code, a + c.code.addImmediateVal info, int(getSize(c.config, baseType)) + c.code.addImmediateVal info, int(getAlign(c.config, baseType)) + freeTemp c, a + +proc genNewSeq(c: var ProcCon; n: PNode) = + let info = toLineInfo(c, n.info) + let seqtype = skipTypes(n[1].typ, abstractVarRange) + let baseType = seqtype.lastSon + var d = c.genx(n[1]) + var b = c.genx(n[2]) + + # $1.len = $2 + buildTyped c.code, info, Asgn, c.m.nativeIntId: + buildTyped c.code, info, FieldAt, c.m.nativeIntId: + copyTree c.code, d + c.code.addImmediateVal info, 0 + copyTree c.code, b + c.code.addImmediateVal info, 0 + + # $1.p = ($4*) #newSeqPayload($2, sizeof($3), NIM_ALIGNOF($3)) + let payloadPtr = seqPayloadPtrType(c.m.types, seqtype) + buildTyped c.code, info, Asgn, payloadPtr: + # $1.p + buildTyped c.code, info, FieldAt, payloadPtr: + copyTree c.code, d + c.code.addImmediateVal info, 1 + # ($4*) #newSeqPayload($2, sizeof($3), NIM_ALIGNOF($3)) + buildTyped c.code, info, Cast, payloadPtr: + buildTyped c.code, info, Call, VoidPtrId: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "newSeqPayload") + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + copyTree c.code, b + c.code.addImmediateVal info, int(getSize(c.config, baseType)) + c.code.addImmediateVal info, int(getAlign(c.config, baseType)) + freeTemp c, b + freeTemp c, d + +template intoDest*(d: var Value; info: PackedLineInfo; typ: TypeId; body: untyped) = + if typ == VoidId: + body(c.code) + elif isEmpty(d): + body(Tree(d)) + else: + buildTyped c.code, info, Asgn, typ: + copyTree c.code, d + body(c.code) + +proc genBinaryOp(c: var ProcCon; n: PNode; d: var Value; opc: Opcode) = + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[1]) + let tmp2 = c.genx(n[2]) + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, opc, t: + copyTree target, tmp + copyTree target, tmp2 + intoDest d, info, t, body + c.freeTemp(tmp) + c.freeTemp(tmp2) + +proc genCmpOp(c: var ProcCon; n: PNode; d: var Value; opc: Opcode) = + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[1]) + let tmp2 = c.genx(n[2]) + let t = typeToIr(c.m.types, n[1].typ) + template body(target) = + buildTyped target, info, opc, t: + copyTree target, tmp + copyTree target, tmp2 + intoDest d, info, Bool8Id, body + c.freeTemp(tmp) + c.freeTemp(tmp2) + +proc genUnaryOp(c: var ProcCon; n: PNode; d: var Value; opc: Opcode) = + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[1]) + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, opc, t: + copyTree target, tmp + intoDest d, info, t, body + c.freeTemp(tmp) + +proc genIncDec(c: var ProcCon; n: PNode; opc: Opcode) = + let info = toLineInfo(c, n.info) + let t = typeToIr(c.m.types, skipTypes(n[1].typ, abstractVar)) + + let d = c.genx(n[1]) + let tmp = c.genx(n[2]) + # we produce code like: i = i + 1 + buildTyped c.code, info, Asgn, t: + copyTree c.code, d + buildTyped c.code, info, opc, t: + copyTree c.code, d + copyTree c.code, tmp + c.freeTemp(tmp) + #c.genNarrow(n[1], d) + c.freeTemp(d) + +proc genArrayLen(c: var ProcCon; n: PNode; d: var Value) = + #echo c.m.graph.config $ n.info, " ", n + let info = toLineInfo(c, n.info) + var a = n[1] + #if a.kind == nkHiddenAddr: a = a[0] + var typ = skipTypes(a.typ, abstractVar + tyUserTypeClasses) + case typ.kind + of tyOpenArray, tyVarargs: + let xa = c.genx(a) + template body(target) = + buildTyped target, info, FieldAt, c.m.nativeIntId: + copyTree target, xa + target.addImmediateVal info, 1 # (p, len)-pair so len is at index 1 + intoDest d, info, c.m.nativeIntId, body + + of tyCstring: + let xa = c.genx(a) + if isEmpty(d): d = getTemp(c, n) + buildTyped c.code, info, Call, c.m.nativeIntId: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "nimCStrLen") + assert codegenProc != nil + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + copyTree c.code, xa + + of tyString, tySequence: + let xa = c.genx(a) + + if typ.kind == tySequence: + # we go through a temporary here because people write bullshit code. + if isEmpty(d): d = getTemp(c, n) + + template body(target) = + buildTyped target, info, FieldAt, c.m.nativeIntId: + copyTree target, xa + target.addImmediateVal info, 0 # (len, p)-pair so len is at index 0 + intoDest d, info, c.m.nativeIntId, body + + of tyArray: + template body(target) = + target.addIntVal(c.m.integers, info, c.m.nativeIntId, toInt lengthOrd(c.config, typ)) + intoDest d, info, c.m.nativeIntId, body + else: internalError(c.config, n.info, "genArrayLen()") + +proc genUnaryMinus(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[1]) + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, Sub, t: + # Little hack: This works because we know that `0.0` is all 0 bits: + target.addIntVal(c.m.integers, info, t, 0) + copyTree target, tmp + intoDest d, info, t, body + c.freeTemp(tmp) + +proc genHigh(c: var ProcCon; n: PNode; d: var Value) = + let subOpr = createMagic(c.m.graph, c.m.idgen, "-", mSubI) + let lenOpr = createMagic(c.m.graph, c.m.idgen, "len", mLengthOpenArray) + let asLenExpr = subOpr.buildCall(lenOpr.buildCall(n[1]), nkIntLit.newIntNode(1)) + c.gen asLenExpr, d + +proc genBinaryCp(c: var ProcCon; n: PNode; d: var Value; compilerProc: string) = + let info = toLineInfo(c, n.info) + let xa = c.genx(n[1]) + let xb = c.genx(n[2]) + if isEmpty(d) and not isEmptyType(n.typ): d = getTemp(c, n) + + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, Call, t: + let codegenProc = magicsys.getCompilerProc(c.m.graph, compilerProc) + #assert codegenProc != nil, $n & " " & (c.m.graph.config $ n.info) + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree target, theProc + copyTree target, xa + copyTree target, xb + + intoDest d, info, t, body + c.freeTemp xb + c.freeTemp xa + +proc genUnaryCp(c: var ProcCon; n: PNode; d: var Value; compilerProc: string; argAt = 1) = + let info = toLineInfo(c, n.info) + let xa = c.genx(n[argAt]) + if isEmpty(d) and not isEmptyType(n.typ): d = getTemp(c, n) + + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, Call, t: + let codegenProc = magicsys.getCompilerProc(c.m.graph, compilerProc) + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree target, theProc + copyTree target, xa + + intoDest d, info, t, body + c.freeTemp xa + +proc genEnumToStr(c: var ProcCon; n: PNode; d: var Value) = + let t = n[1].typ.skipTypes(abstractInst+{tyRange}) + let toStrProc = getToStringProc(c.m.graph, t) + # XXX need to modify this logic for IC. + var nb = copyTree(n) + nb[0] = newSymNode(toStrProc) + gen(c, nb, d) + +proc genOf(c: var ProcCon; n: PNode; d: var Value) = + genUnaryOp c, n, d, TestOf + +template sizeOfLikeMsg(name): string = + "'" & name & "' requires '.importc' types to be '.completeStruct'" + +proc genIsNil(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[1]) + let t = typeToIr(c.m.types, n[1].typ) + template body(target) = + buildTyped target, info, Eq, t: + copyTree target, tmp + addNilVal target, info, t + intoDest d, info, Bool8Id, body + c.freeTemp(tmp) + +proc fewCmps(conf: ConfigRef; s: PNode): bool = + # this function estimates whether it is better to emit code + # for constructing the set or generating a bunch of comparisons directly + if s.kind != nkCurly: + result = false + elif (getSize(conf, s.typ) <= conf.target.intSize) and (nfAllConst in s.flags): + result = false # it is better to emit the set generation code + elif elemType(s.typ).kind in {tyInt, tyInt16..tyInt64}: + result = true # better not emit the set if int is basetype! + else: + result = s.len <= 8 # 8 seems to be a good value + +proc genInBitset(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let a = c.genx(n[1]) + let b = c.genx(n[2]) + + let t = bitsetBasetype(c.m.types, n[1].typ) + let setType = typeToIr(c.m.types, n[1].typ) + let mask = + case t + of UInt8Id: 7 + of UInt16Id: 15 + of UInt32Id: 31 + else: 63 + let expansion = if t == UInt64Id: UInt64Id else: c.m.nativeUIntId + # "(($1 &(1U<<((NU)($2)&7U)))!=0)" - or - + # "(($1[(NU)($2)>>3] &(1U<<((NU)($2)&7U)))!=0)" + + template body(target) = + buildTyped target, info, BoolNot, Bool8Id: + buildTyped target, info, Eq, t: + buildTyped target, info, BitAnd, t: + if c.m.types.g[setType].kind != ArrayTy: + copyTree target, a + else: + buildTyped target, info, ArrayAt, t: + copyTree target, a + buildTyped target, info, BitShr, t: + buildTyped target, info, Cast, expansion: + copyTree target, b + addIntVal target, c.m.integers, info, expansion, 3 + + buildTyped target, info, BitShl, t: + addIntVal target, c.m.integers, info, t, 1 + buildTyped target, info, BitAnd, t: + buildTyped target, info, Cast, expansion: + copyTree target, b + addIntVal target, c.m.integers, info, expansion, mask + addIntVal target, c.m.integers, info, t, 0 + intoDest d, info, t, body + + c.freeTemp(b) + c.freeTemp(a) + +proc genInSet(c: var ProcCon; n: PNode; d: var Value) = + let g {.cursor.} = c.m.graph + if n[1].kind == nkCurly and fewCmps(g.config, n[1]): + # a set constructor but not a constant set: + # do not emit the set, but generate a bunch of comparisons; and if we do + # so, we skip the unnecessary range check: This is a semantical extension + # that code now relies on. :-/ XXX + let elem = if n[2].kind in {nkChckRange, nkChckRange64}: n[2][0] + else: n[2] + let curly = n[1] + var ex: PNode = nil + for it in curly: + var test: PNode + if it.kind == nkRange: + test = newTree(nkCall, g.operators.opAnd.newSymNode, + newTree(nkCall, g.operators.opLe.newSymNode, it[0], elem), # a <= elem + newTree(nkCall, g.operators.opLe.newSymNode, elem, it[1]) + ) + else: + test = newTree(nkCall, g.operators.opEq.newSymNode, elem, it) + test.typ = getSysType(g, it.info, tyBool) + + if ex == nil: ex = test + else: ex = newTree(nkCall, g.operators.opOr.newSymNode, ex, test) + + if ex == nil: + let info = toLineInfo(c, n.info) + template body(target) = + boolVal target, info, false + intoDest d, info, Bool8Id, body + else: + gen c, ex, d + else: + genInBitset c, n, d + +proc genCard(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let a = c.genx(n[1]) + let t = typeToIr(c.m.types, n.typ) + + let setType = typeToIr(c.m.types, n[1].typ) + if isEmpty(d): d = getTemp(c, n) + + buildTyped c.code, info, Asgn, t: + copyTree c.code, d + buildTyped c.code, info, Call, t: + if c.m.types.g[setType].kind == ArrayTy: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "cardSet") + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + buildTyped c.code, info, AddrOf, ptrTypeOf(c.m.types.g, setType): + copyTree c.code, a + c.code.addImmediateVal info, int(getSize(c.config, n[1].typ)) + elif t == UInt64Id: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "countBits64") + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + copyTree c.code, a + else: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "countBits32") + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + buildTyped c.code, info, Cast, UInt32Id: + copyTree c.code, a + freeTemp c, a + +proc genEqSet(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let a = c.genx(n[1]) + let b = c.genx(n[2]) + let t = typeToIr(c.m.types, n.typ) + + let setType = typeToIr(c.m.types, n[1].typ) + + if c.m.types.g[setType].kind == ArrayTy: + if isEmpty(d): d = getTemp(c, n) + + buildTyped c.code, info, Asgn, t: + copyTree c.code, d + buildTyped c.code, info, Eq, t: + buildTyped c.code, info, Call, t: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "nimCmpMem") + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + buildTyped c.code, info, AddrOf, ptrTypeOf(c.m.types.g, setType): + copyTree c.code, a + buildTyped c.code, info, AddrOf, ptrTypeOf(c.m.types.g, setType): + copyTree c.code, b + c.code.addImmediateVal info, int(getSize(c.config, n[1].typ)) + c.code.addIntVal c.m.integers, info, c.m.nativeIntId, 0 + + else: + template body(target) = + buildTyped target, info, Eq, setType: + copyTree target, a + copyTree target, b + intoDest d, info, Bool8Id, body + + freeTemp c, b + freeTemp c, a + +proc beginCountLoop(c: var ProcCon; info: PackedLineInfo; first, last: int): (SymId, LabelId, LabelId) = + let tmp = allocTemp(c.sm, c.m.nativeIntId) + c.code.addSummon info, tmp, c.m.nativeIntId + buildTyped c.code, info, Asgn, c.m.nativeIntId: + c.code.addSymUse info, tmp + c.code.addIntVal c.m.integers, info, c.m.nativeIntId, first + let lab1 = c.code.addNewLabel(c.labelGen, info, LoopLabel) + result = (tmp, lab1, newLabel(c.labelGen)) + + buildTyped c.code, info, Select, Bool8Id: + buildTyped c.code, info, Lt, c.m.nativeIntId: + c.code.addSymUse info, tmp + c.code.addIntVal c.m.integers, info, c.m.nativeIntId, last + build c.code, info, SelectPair: + build c.code, info, SelectValue: + c.code.boolVal(info, false) + c.code.gotoLabel info, Goto, result[2] + +proc beginCountLoop(c: var ProcCon; info: PackedLineInfo; first, last: Value): (SymId, LabelId, LabelId) = + let tmp = allocTemp(c.sm, c.m.nativeIntId) + c.code.addSummon info, tmp, c.m.nativeIntId + buildTyped c.code, info, Asgn, c.m.nativeIntId: + c.code.addSymUse info, tmp + copyTree c.code, first + let lab1 = c.code.addNewLabel(c.labelGen, info, LoopLabel) + result = (tmp, lab1, newLabel(c.labelGen)) + + buildTyped c.code, info, Select, Bool8Id: + buildTyped c.code, info, Le, c.m.nativeIntId: + c.code.addSymUse info, tmp + copyTree c.code, last + build c.code, info, SelectPair: + build c.code, info, SelectValue: + c.code.boolVal(info, false) + c.code.gotoLabel info, Goto, result[2] + +proc endLoop(c: var ProcCon; info: PackedLineInfo; s: SymId; back, exit: LabelId) = + buildTyped c.code, info, Asgn, c.m.nativeIntId: + c.code.addSymUse info, s + buildTyped c.code, info, Add, c.m.nativeIntId: + c.code.addSymUse info, s + c.code.addIntVal c.m.integers, info, c.m.nativeIntId, 1 + c.code.addLabel info, GotoLoop, back + c.code.addLabel info, Label, exit + freeTemp(c.sm, s) + +proc genLeSet(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + let a = c.genx(n[1]) + let b = c.genx(n[2]) + let t = typeToIr(c.m.types, n.typ) + + let setType = typeToIr(c.m.types, n[1].typ) + + if c.m.types.g[setType].kind == ArrayTy: + let elemType = bitsetBasetype(c.m.types, n[1].typ) + if isEmpty(d): d = getTemp(c, n) + # "for ($1 = 0; $1 < $2; $1++):" + # " $3 = (($4[$1] & ~ $5[$1]) == 0)" + # " if (!$3) break;" + let (idx, backLabel, endLabel) = beginCountLoop(c, info, 0, int(getSize(c.config, n[1].typ))) + buildTyped c.code, info, Asgn, Bool8Id: + copyTree c.code, d + buildTyped c.code, info, Eq, elemType: + buildTyped c.code, info, BitAnd, elemType: + buildTyped c.code, info, ArrayAt, elemType: + copyTree c.code, a + c.code.addSymUse info, idx + buildTyped c.code, info, BitNot, elemType: + buildTyped c.code, info, ArrayAt, elemType: + copyTree c.code, b + c.code.addSymUse info, idx + c.code.addIntVal c.m.integers, info, elemType, 0 + + # if !$3: break + buildTyped c.code, info, Select, Bool8Id: + c.code.copyTree d + build c.code, info, SelectPair: + build c.code, info, SelectValue: + c.code.boolVal(info, false) + c.code.gotoLabel info, Goto, endLabel + + endLoop(c, info, idx, backLabel, endLabel) + else: + # "(($1 & ~ $2)==0)" + template body(target) = + buildTyped target, info, Eq, setType: + buildTyped target, info, BitAnd, setType: + copyTree target, a + buildTyped target, info, BitNot, setType: + copyTree target, b + target.addIntVal c.m.integers, info, setType, 0 + + intoDest d, info, Bool8Id, body + + freeTemp c, b + freeTemp c, a + +proc genLtSet(c: var ProcCon; n: PNode; d: var Value) = + localError(c.m.graph.config, n.info, "`<` for sets not implemented") + +proc genBinarySet(c: var ProcCon; n: PNode; d: var Value; m: TMagic) = + let info = toLineInfo(c, n.info) + let a = c.genx(n[1]) + let b = c.genx(n[2]) + let t = typeToIr(c.m.types, n.typ) + + let setType = typeToIr(c.m.types, n[1].typ) + + if c.m.types.g[setType].kind == ArrayTy: + let elemType = bitsetBasetype(c.m.types, n[1].typ) + if isEmpty(d): d = getTemp(c, n) + # "for ($1 = 0; $1 < $2; $1++):" + # " $3 = (($4[$1] & ~ $5[$1]) == 0)" + # " if (!$3) break;" + let (idx, backLabel, endLabel) = beginCountLoop(c, info, 0, int(getSize(c.config, n[1].typ))) + buildTyped c.code, info, Asgn, elemType: + buildTyped c.code, info, ArrayAt, elemType: + copyTree c.code, d + c.code.addSymUse info, idx + buildTyped c.code, info, (if m == mPlusSet: BitOr else: BitAnd), elemType: + buildTyped c.code, info, ArrayAt, elemType: + copyTree c.code, a + c.code.addSymUse info, idx + if m == mMinusSet: + buildTyped c.code, info, BitNot, elemType: + buildTyped c.code, info, ArrayAt, elemType: + copyTree c.code, b + c.code.addSymUse info, idx + else: + buildTyped c.code, info, ArrayAt, elemType: + copyTree c.code, b + c.code.addSymUse info, idx + + endLoop(c, info, idx, backLabel, endLabel) + else: + # "(($1 & ~ $2)==0)" + template body(target) = + buildTyped target, info, (if m == mPlusSet: BitOr else: BitAnd), setType: + copyTree target, a + if m == mMinusSet: + buildTyped target, info, BitNot, setType: + copyTree target, b + else: + copyTree target, b + + intoDest d, info, setType, body + + freeTemp c, b + freeTemp c, a + +proc genInclExcl(c: var ProcCon; n: PNode; m: TMagic) = + let info = toLineInfo(c, n.info) + let a = c.genx(n[1]) + let b = c.genx(n[2]) + + let setType = typeToIr(c.m.types, n[1].typ) + + let t = bitsetBasetype(c.m.types, n[1].typ) + let mask = + case t + of UInt8Id: 7 + of UInt16Id: 15 + of UInt32Id: 31 + else: 63 + + buildTyped c.code, info, Asgn, setType: + if c.m.types.g[setType].kind == ArrayTy: + if m == mIncl: + # $1[(NU)($2)>>3] |=(1U<<($2&7U)) + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, a + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + copyTree c.code, b + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitOr, t: + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, a + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + copyTree c.code, b + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + copyTree c.code, b + c.code.addIntVal c.m.integers, info, t, 7 + else: + # $1[(NU)($2)>>3] &= ~(1U<<($2&7U)) + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, a + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + copyTree c.code, b + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitAnd, t: + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, a + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + copyTree c.code, b + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitNot, t: + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + copyTree c.code, b + c.code.addIntVal c.m.integers, info, t, 7 + + else: + copyTree c.code, a + if m == mIncl: + # $1 |= ((NU8)1)<<(($2) & 7) + buildTyped c.code, info, BitOr, setType: + copyTree c.code, a + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + copyTree c.code, b + c.code.addIntVal c.m.integers, info, t, mask + else: + # $1 &= ~(((NU8)1) << (($2) & 7)) + buildTyped c.code, info, BitAnd, setType: + copyTree c.code, a + buildTyped c.code, info, BitNot, t: + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + copyTree c.code, b + c.code.addIntVal c.m.integers, info, t, mask + freeTemp c, b + freeTemp c, a + +proc genSetConstrDyn(c: var ProcCon; n: PNode; d: var Value) = + # example: { a..b, c, d, e, f..g } + # we have to emit an expression of the form: + # nimZeroMem(tmp, sizeof(tmp)); inclRange(tmp, a, b); incl(tmp, c); + # incl(tmp, d); incl(tmp, e); inclRange(tmp, f, g); + let info = toLineInfo(c, n.info) + let setType = typeToIr(c.m.types, n.typ) + let size = int(getSize(c.config, n.typ)) + let t = bitsetBasetype(c.m.types, n.typ) + let mask = + case t + of UInt8Id: 7 + of UInt16Id: 15 + of UInt32Id: 31 + else: 63 + + if isEmpty(d): d = getTemp(c, n) + if c.m.types.g[setType].kind != ArrayTy: + buildTyped c.code, info, Asgn, setType: + copyTree c.code, d + c.code.addIntVal c.m.integers, info, t, 0 + + for it in n: + if it.kind == nkRange: + let a = genx(c, it[0]) + let b = genx(c, it[1]) + let (idx, backLabel, endLabel) = beginCountLoop(c, info, a, b) + buildTyped c.code, info, Asgn, setType: + copyTree c.code, d + buildTyped c.code, info, BitAnd, setType: + copyTree c.code, d + buildTyped c.code, info, BitNot, t: + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + c.code.addSymUse info, idx + c.code.addIntVal c.m.integers, info, t, mask + + endLoop(c, info, idx, backLabel, endLabel) + freeTemp c, b + freeTemp c, a + + else: + let a = genx(c, it) + buildTyped c.code, info, Asgn, setType: + copyTree c.code, d + buildTyped c.code, info, BitAnd, setType: + copyTree c.code, d + buildTyped c.code, info, BitNot, t: + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + copyTree c.code, a + c.code.addIntVal c.m.integers, info, t, mask + freeTemp c, a + + else: + # init loop: + let (idx, backLabel, endLabel) = beginCountLoop(c, info, 0, size) + buildTyped c.code, info, Asgn, t: + copyTree c.code, d + c.code.addIntVal c.m.integers, info, t, 0 + endLoop(c, info, idx, backLabel, endLabel) + + # incl elements: + for it in n: + if it.kind == nkRange: + let a = genx(c, it[0]) + let b = genx(c, it[1]) + let (idx, backLabel, endLabel) = beginCountLoop(c, info, a, b) + + buildTyped c.code, info, Asgn, t: + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, d + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + c.code.addSymUse info, idx + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitOr, t: + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, d + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + c.code.addSymUse info, idx + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + c.code.addSymUse info, idx + c.code.addIntVal c.m.integers, info, t, 7 + + endLoop(c, info, idx, backLabel, endLabel) + freeTemp c, b + freeTemp c, a + + else: + let a = genx(c, it) + # $1[(NU)($2)>>3] |=(1U<<($2&7U)) + buildTyped c.code, info, Asgn, t: + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, d + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + copyTree c.code, a + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitOr, t: + buildTyped c.code, info, ArrayAt, t: + copyTree c.code, d + buildTyped c.code, info, BitShr, t: + buildTyped c.code, info, Cast, c.m.nativeUIntId: + copyTree c.code, a + addIntVal c.code, c.m.integers, info, c.m.nativeUIntId, 3 + buildTyped c.code, info, BitShl, t: + c.code.addIntVal c.m.integers, info, t, 1 + buildTyped c.code, info, BitAnd, t: + copyTree c.code, a + c.code.addIntVal c.m.integers, info, t, 7 + freeTemp c, a + +proc genSetConstr(c: var ProcCon; n: PNode; d: var Value) = + if isDeepConstExpr(n): + let info = toLineInfo(c, n.info) + let setType = typeToIr(c.m.types, n.typ) + let size = int(getSize(c.config, n.typ)) + let cs = toBitSet(c.config, n) + + if c.m.types.g[setType].kind != ArrayTy: + template body(target) = + target.addIntVal c.m.integers, info, setType, cast[BiggestInt](bitSetToWord(cs, size)) + intoDest d, info, setType, body + else: + let t = bitsetBasetype(c.m.types, n.typ) + template body(target) = + buildTyped target, info, ArrayConstr, setType: + for i in 0..high(cs): + target.addIntVal c.m.integers, info, t, int64 cs[i] + intoDest d, info, setType, body + else: + genSetConstrDyn c, n, d + +proc genStrConcat(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + # <Nim code> + # s = "Hello " & name & ", how do you feel?" & 'z' + # + # <generated code> + # { + # string tmp0; + # ... + # tmp0 = rawNewString(6 + 17 + 1 + s2->len); + # // we cannot generate s = rawNewString(...) here, because + # // ``s`` may be used on the right side of the expression + # appendString(tmp0, strlit_1); + # appendString(tmp0, name); + # appendString(tmp0, strlit_2); + # appendChar(tmp0, 'z'); + # asgn(s, tmp0); + # } + var args: seq[Value] = @[] + var precomputedLen = 0 + for i in 1 ..< n.len: + let it = n[i] + if skipTypes(it.typ, abstractVarRange).kind == tyChar: + inc precomputedLen + elif it.kind in {nkStrLit..nkTripleStrLit}: + inc precomputedLen, it.strVal.len + args.add genx(c, it) + + # generate length computation: + var tmpLen = allocTemp(c.sm, c.m.nativeIntId) + buildTyped c.code, info, Asgn, c.m.nativeIntId: + c.code.addSymUse info, tmpLen + c.code.addIntVal c.m.integers, info, c.m.nativeIntId, precomputedLen + for a in mitems(args): + buildTyped c.code, info, Asgn, c.m.nativeIntId: + c.code.addSymUse info, tmpLen + buildTyped c.code, info, CheckedAdd, c.m.nativeIntId: + c.code.addSymUse info, tmpLen + buildTyped c.code, info, FieldAt, c.m.nativeIntId: + copyTree c.code, a + c.code.addImmediateVal info, 0 # (len, p)-pair so len is at index 0 + + var tmpStr = getTemp(c, n) + # ^ because of aliasing, we always go through a temporary + let t = typeToIr(c.m.types, n.typ) + buildTyped c.code, info, Asgn, t: + copyTree c.code, tmpStr + buildTyped c.code, info, Call, t: + let codegenProc = magicsys.getCompilerProc(c.m.graph, "rawNewString") + #assert codegenProc != nil, $n & " " & (c.m.graph.config $ n.info) + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + c.code.addSymUse info, tmpLen + freeTemp c.sm, tmpLen + + for i in 1 ..< n.len: + let it = n[i] + let isChar = skipTypes(it.typ, abstractVarRange).kind == tyChar + buildTyped c.code, info, Call, VoidId: + let codegenProc = magicsys.getCompilerProc(c.m.graph, + (if isChar: "appendChar" else: "appendString")) + #assert codegenProc != nil, $n & " " & (c.m.graph.config $ n.info) + let theProc = c.genx newSymNode(codegenProc, n.info) + copyTree c.code, theProc + buildTyped c.code, info, AddrOf, ptrTypeOf(c.m.types.g, t): + copyTree c.code, tmpStr + copyTree c.code, args[i-1] + freeTemp c, args[i-1] + + if isEmpty(d): + d = tmpStr + else: + # XXX Test that this does not cause memory leaks! + buildTyped c.code, info, Asgn, t: + copyTree c.code, d + copyTree c.code, tmpStr + +proc genDefault(c: var ProcCon; n: PNode; d: var Value) = + let m = expandDefault(n.typ, n.info) + gen c, m, d + +proc genMagic(c: var ProcCon; n: PNode; d: var Value; m: TMagic) = + case m + of mAnd: c.genAndOr(n, opcFJmp, d) + of mOr: c.genAndOr(n, opcTJmp, d) + of mPred, mSubI: c.genBinaryOp(n, d, CheckedSub) + of mSucc, mAddI: c.genBinaryOp(n, d, CheckedAdd) + of mInc: + unused(c, n, d) + c.genIncDec(n, CheckedAdd) + of mDec: + unused(c, n, d) + c.genIncDec(n, CheckedSub) + of mOrd, mChr, mArrToSeq, mUnown: + c.gen(n[1], d) + of generatedMagics: + genCall(c, n, d) + of mNew, mNewFinalize: + unused(c, n, d) + c.genNew(n, needsInit = true) + of mNewSeq: + unused(c, n, d) + c.genNewSeq(n) + of mNewSeqOfCap: c.genNewSeqOfCap(n, d) + of mNewString, mNewStringOfCap, mExit: c.genCall(n, d) + of mLengthOpenArray, mLengthArray, mLengthSeq, mLengthStr: + genArrayLen(c, n, d) + of mMulI: genBinaryOp(c, n, d, Mul) + of mDivI: genBinaryOp(c, n, d, Div) + of mModI: genBinaryOp(c, n, d, Mod) + of mAddF64: genBinaryOp(c, n, d, Add) + of mSubF64: genBinaryOp(c, n, d, Sub) + of mMulF64: genBinaryOp(c, n, d, Mul) + of mDivF64: genBinaryOp(c, n, d, Div) + of mShrI: genBinaryOp(c, n, d, BitShr) + of mShlI: genBinaryOp(c, n, d, BitShl) + of mAshrI: genBinaryOp(c, n, d, BitShr) + of mBitandI: genBinaryOp(c, n, d, BitAnd) + of mBitorI: genBinaryOp(c, n, d, BitOr) + of mBitxorI: genBinaryOp(c, n, d, BitXor) + of mAddU: genBinaryOp(c, n, d, Add) + of mSubU: genBinaryOp(c, n, d, Sub) + of mMulU: genBinaryOp(c, n, d, Mul) + of mDivU: genBinaryOp(c, n, d, Div) + of mModU: genBinaryOp(c, n, d, Mod) + of mEqI, mEqB, mEqEnum, mEqCh: + genCmpOp(c, n, d, Eq) + of mLeI, mLeEnum, mLeCh, mLeB: + genCmpOp(c, n, d, Le) + of mLtI, mLtEnum, mLtCh, mLtB: + genCmpOp(c, n, d, Lt) + of mEqF64: genCmpOp(c, n, d, Eq) + of mLeF64: genCmpOp(c, n, d, Le) + of mLtF64: genCmpOp(c, n, d, Lt) + of mLePtr, mLeU: genCmpOp(c, n, d, Le) + of mLtPtr, mLtU: genCmpOp(c, n, d, Lt) + of mEqProc, mEqRef: + genCmpOp(c, n, d, Eq) + of mXor: genBinaryOp(c, n, d, BitXor) + of mNot: genUnaryOp(c, n, d, BoolNot) + of mUnaryMinusI, mUnaryMinusI64: + genUnaryMinus(c, n, d) + #genNarrow(c, n, d) + of mUnaryMinusF64: genUnaryMinus(c, n, d) + of mUnaryPlusI, mUnaryPlusF64: gen(c, n[1], d) + of mBitnotI: + genUnaryOp(c, n, d, BitNot) + when false: + # XXX genNarrowU modified, do not narrow signed types + let t = skipTypes(n.typ, abstractVar-{tyTypeDesc}) + let size = getSize(c.config, t) + if t.kind in {tyUInt8..tyUInt32} or (t.kind == tyUInt and size < 8): + c.gABC(n, opcNarrowU, d, TRegister(size*8)) + of mStrToStr, mEnsureMove: c.gen n[1], d + of mIntToStr: genUnaryCp(c, n, d, "nimIntToStr") + of mInt64ToStr: genUnaryCp(c, n, d, "nimInt64ToStr") + of mBoolToStr: genUnaryCp(c, n, d, "nimBoolToStr") + of mCharToStr: genUnaryCp(c, n, d, "nimCharToStr") + of mFloatToStr: + if n[1].typ.skipTypes(abstractInst).kind == tyFloat32: + genUnaryCp(c, n, d, "nimFloat32ToStr") + else: + genUnaryCp(c, n, d, "nimFloatToStr") + of mCStrToStr: genUnaryCp(c, n, d, "cstrToNimstr") + of mEnumToStr: genEnumToStr(c, n, d) + + of mEqStr: genBinaryCp(c, n, d, "eqStrings") + of mEqCString: genCall(c, n, d) + of mLeStr: genBinaryCp(c, n, d, "leStrings") + of mLtStr: genBinaryCp(c, n, d, "ltStrings") + + of mSetLengthStr: + unused(c, n, d) + let nb = copyTree(n) + nb[1] = makeAddr(nb[1], c.m.idgen) + genBinaryCp(c, nb, d, "setLengthStrV2") + + of mSetLengthSeq: + unused(c, n, d) + let nb = copyTree(n) + nb[1] = makeAddr(nb[1], c.m.idgen) + genCall(c, nb, d) + + of mSwap: + unused(c, n, d) + c.gen(lowerSwap(c.m.graph, n, c.m.idgen, + if c.prc == nil: c.m.module else: c.prc), d) + of mParseBiggestFloat: + genCall c, n, d + of mHigh: + c.genHigh n, d + + of mEcho: + unused(c, n, d) + genUnaryCp c, n, d, "echoBinSafe" + + of mAppendStrCh: + unused(c, n, d) + let nb = copyTree(n) + nb[1] = makeAddr(nb[1], c.m.idgen) + genBinaryCp(c, nb, d, "nimAddCharV1") + of mMinI, mMaxI, mAbsI, mDotDot: + c.genCall(n, d) + of mSizeOf: + localError(c.config, n.info, sizeOfLikeMsg("sizeof")) + of mAlignOf: + localError(c.config, n.info, sizeOfLikeMsg("alignof")) + of mOffsetOf: + localError(c.config, n.info, sizeOfLikeMsg("offsetof")) + of mRunnableExamples: + discard "just ignore any call to runnableExamples" + of mDestroy, mTrace: discard "ignore calls to the default destructor" + of mOf: genOf(c, n, d) + of mAppendStrStr: + unused(c, n, d) + let nb = copyTree(n) + nb[1] = makeAddr(nb[1], c.m.idgen) + genBinaryCp(c, nb, d, "nimAddStrV1") + of mAppendSeqElem: + unused(c, n, d) + let nb = copyTree(n) + nb[1] = makeAddr(nb[1], c.m.idgen) + genCall(c, nb, d) + of mIsNil: genIsNil(c, n, d) + of mInSet: genInSet(c, n, d) + of mCard: genCard(c, n, d) + of mEqSet: genEqSet(c, n, d) + of mLeSet: genLeSet(c, n, d) + of mLtSet: genLtSet(c, n, d) + of mMulSet: genBinarySet(c, n, d, m) + of mPlusSet: genBinarySet(c, n, d, m) + of mMinusSet: genBinarySet(c, n, d, m) + of mIncl, mExcl: + unused(c, n, d) + genInclExcl(c, n, m) + of mConStrStr: genStrConcat(c, n, d) + of mDefault, mZeroDefault: + genDefault c, n, d + else: + # mGCref, mGCunref, + globalError(c.config, n.info, "cannot generate code for: " & $m) + +#[ + + of mReset: + unused(c, n, d) + var d = c.genx(n[1]) + # XXX use ldNullOpcode() here? + c.gABx(n, opcLdNull, d, c.genType(n[1].typ)) + c.gABC(n, opcNodeToReg, d, d) + c.gABx(n, ldNullOpcode(n.typ), d, c.genType(n.typ)) + + of mConStrStr: genVarargsABC(c, n, d, opcConcatStr) + + of mRepr: genUnaryABC(c, n, d, opcRepr) + + of mSlice: + var + d = c.genx(n[1]) + left = c.genIndex(n[2], n[1].typ) + right = c.genIndex(n[3], n[1].typ) + if isEmpty(d): d = c.getTemp(n) + c.gABC(n, opcNodeToReg, d, d) + c.gABC(n, opcSlice, d, left, right) + c.freeTemp(left) + c.freeTemp(right) + c.freeTemp(d) + + of mMove: + let arg = n[1] + let a = c.genx(arg) + if isEmpty(d): d = c.getTemp(arg) + gABC(c, arg, whichAsgnOpc(arg, requiresCopy=false), d, a) + c.freeTemp(a) + of mDup: + let arg = n[1] + let a = c.genx(arg) + if isEmpty(d): d = c.getTemp(arg) + gABC(c, arg, whichAsgnOpc(arg, requiresCopy=false), d, a) + c.freeTemp(a) + + of mNodeId: + c.genUnaryABC(n, d, opcNodeId) + + of mExpandToAst: + if n.len != 2: + globalError(c.config, n.info, "expandToAst requires 1 argument") + let arg = n[1] + if arg.kind in nkCallKinds: + #if arg[0].kind != nkSym or arg[0].sym.kind notin {skTemplate, skMacro}: + # "ExpandToAst: expanded symbol is no macro or template" + if isEmpty(d): d = c.getTemp(n) + c.genCall(arg, d) + # do not call clearDest(n, d) here as getAst has a meta-type as such + # produces a value + else: + globalError(c.config, n.info, "expandToAst requires a call expression") + of mParseExprToAst: + genBinaryABC(c, n, d, opcParseExprToAst) + of mParseStmtToAst: + genBinaryABC(c, n, d, opcParseStmtToAst) + of mTypeTrait: + let tmp = c.genx(n[1]) + if isEmpty(d): d = c.getTemp(n) + c.gABx(n, opcSetType, tmp, c.genType(n[1].typ)) + c.gABC(n, opcTypeTrait, d, tmp) + c.freeTemp(tmp) + of mSlurp: genUnaryABC(c, n, d, opcSlurp) + of mNLen: genUnaryABI(c, n, d, opcLenSeq, nimNodeFlag) + of mGetImpl: genUnaryABC(c, n, d, opcGetImpl) + of mGetImplTransf: genUnaryABC(c, n, d, opcGetImplTransf) + of mSymOwner: genUnaryABC(c, n, d, opcSymOwner) + of mSymIsInstantiationOf: genBinaryABC(c, n, d, opcSymIsInstantiationOf) + of mNChild: genBinaryABC(c, n, d, opcNChild) + of mNAdd: genBinaryABC(c, n, d, opcNAdd) + of mNAddMultiple: genBinaryABC(c, n, d, opcNAddMultiple) + of mNKind: genUnaryABC(c, n, d, opcNKind) + of mNSymKind: genUnaryABC(c, n, d, opcNSymKind) + + of mNccValue: genUnaryABC(c, n, d, opcNccValue) + of mNccInc: genBinaryABC(c, n, d, opcNccInc) + of mNcsAdd: genBinaryABC(c, n, d, opcNcsAdd) + of mNcsIncl: genBinaryABC(c, n, d, opcNcsIncl) + of mNcsLen: genUnaryABC(c, n, d, opcNcsLen) + of mNcsAt: genBinaryABC(c, n, d, opcNcsAt) + of mNctLen: genUnaryABC(c, n, d, opcNctLen) + of mNctGet: genBinaryABC(c, n, d, opcNctGet) + of mNctHasNext: genBinaryABC(c, n, d, opcNctHasNext) + of mNctNext: genBinaryABC(c, n, d, opcNctNext) + + of mNIntVal: genUnaryABC(c, n, d, opcNIntVal) + of mNFloatVal: genUnaryABC(c, n, d, opcNFloatVal) + of mNSymbol: genUnaryABC(c, n, d, opcNSymbol) + of mNIdent: genUnaryABC(c, n, d, opcNIdent) + of mNGetType: + let tmp = c.genx(n[1]) + if isEmpty(d): d = c.getTemp(n) + let rc = case n[0].sym.name.s: + of "getType": 0 + of "typeKind": 1 + of "getTypeInst": 2 + else: 3 # "getTypeImpl" + c.gABC(n, opcNGetType, d, tmp, rc) + c.freeTemp(tmp) + #genUnaryABC(c, n, d, opcNGetType) + of mNSizeOf: + let imm = case n[0].sym.name.s: + of "getSize": 0 + of "getAlign": 1 + else: 2 # "getOffset" + c.genUnaryABI(n, d, opcNGetSize, imm) + of mNStrVal: genUnaryABC(c, n, d, opcNStrVal) + of mNSigHash: genUnaryABC(c, n , d, opcNSigHash) + of mNSetIntVal: + unused(c, n, d) + genBinaryStmt(c, n, opcNSetIntVal) + of mNSetFloatVal: + unused(c, n, d) + genBinaryStmt(c, n, opcNSetFloatVal) + of mNSetSymbol: + unused(c, n, d) + genBinaryStmt(c, n, opcNSetSymbol) + of mNSetIdent: + unused(c, n, d) + genBinaryStmt(c, n, opcNSetIdent) + of mNSetStrVal: + unused(c, n, d) + genBinaryStmt(c, n, opcNSetStrVal) + of mNNewNimNode: genBinaryABC(c, n, d, opcNNewNimNode) + of mNCopyNimNode: genUnaryABC(c, n, d, opcNCopyNimNode) + of mNCopyNimTree: genUnaryABC(c, n, d, opcNCopyNimTree) + of mNBindSym: genBindSym(c, n, d) + of mStrToIdent: genUnaryABC(c, n, d, opcStrToIdent) + of mEqIdent: genBinaryABC(c, n, d, opcEqIdent) + of mEqNimrodNode: genBinaryABC(c, n, d, opcEqNimNode) + of mSameNodeType: genBinaryABC(c, n, d, opcSameNodeType) + of mNLineInfo: + case n[0].sym.name.s + of "getFile": genUnaryABI(c, n, d, opcNGetLineInfo, 0) + of "getLine": genUnaryABI(c, n, d, opcNGetLineInfo, 1) + of "getColumn": genUnaryABI(c, n, d, opcNGetLineInfo, 2) + of "copyLineInfo": + internalAssert c.config, n.len == 3 + unused(c, n, d) + genBinaryStmt(c, n, opcNCopyLineInfo) + of "setLine": + internalAssert c.config, n.len == 3 + unused(c, n, d) + genBinaryStmt(c, n, opcNSetLineInfoLine) + of "setColumn": + internalAssert c.config, n.len == 3 + unused(c, n, d) + genBinaryStmt(c, n, opcNSetLineInfoColumn) + of "setFile": + internalAssert c.config, n.len == 3 + unused(c, n, d) + genBinaryStmt(c, n, opcNSetLineInfoFile) + else: internalAssert c.config, false + of mNHint: + unused(c, n, d) + genBinaryStmt(c, n, opcNHint) + of mNWarning: + unused(c, n, d) + genBinaryStmt(c, n, opcNWarning) + of mNError: + if n.len <= 1: + # query error condition: + c.gABC(n, opcQueryErrorFlag, d) + else: + # setter + unused(c, n, d) + genBinaryStmt(c, n, opcNError) + of mNCallSite: + if isEmpty(d): d = c.getTemp(n) + c.gABC(n, opcCallSite, d) + of mNGenSym: genBinaryABC(c, n, d, opcGenSym) + +]# + +proc canElimAddr(n: PNode; idgen: IdGenerator): PNode = + result = nil + case n[0].kind + of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64: + var m = n[0][0] + if m.kind in {nkDerefExpr, nkHiddenDeref}: + # addr ( nkConv ( deref ( x ) ) ) --> nkConv(x) + result = copyNode(n[0]) + result.add m[0] + if n.typ.skipTypes(abstractVar).kind != tyOpenArray: + result.typ = n.typ + elif n.typ.skipTypes(abstractInst).kind in {tyVar}: + result.typ = toVar(result.typ, n.typ.skipTypes(abstractInst).kind, idgen) + of nkHiddenStdConv, nkHiddenSubConv, nkConv: + var m = n[0][1] + if m.kind in {nkDerefExpr, nkHiddenDeref}: + # addr ( nkConv ( deref ( x ) ) ) --> nkConv(x) + result = copyNode(n[0]) + result.add n[0][0] + result.add m[0] + if n.typ.skipTypes(abstractVar).kind != tyOpenArray: + result.typ = n.typ + elif n.typ.skipTypes(abstractInst).kind in {tyVar}: + result.typ = toVar(result.typ, n.typ.skipTypes(abstractInst).kind, idgen) + else: + if n[0].kind in {nkDerefExpr, nkHiddenDeref}: + # addr ( deref ( x )) --> x + result = n[0][0] + +template valueIntoDest(c: var ProcCon; info: PackedLineInfo; d: var Value; typ: PType; body: untyped) = + if isEmpty(d): + body(Tree d) + else: + buildTyped c.code, info, Asgn, typeToIr(c.m.types, typ): + copyTree c.code, d + body(c.code) + +proc genAddr(c: var ProcCon; n: PNode; d: var Value, flags: GenFlags) = + if (let m = canElimAddr(n, c.m.idgen); m != nil): + gen(c, m, d, flags) + return + + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[0], flags) + template body(target) = + buildTyped target, info, AddrOf, typeToIr(c.m.types, n.typ): + copyTree target, tmp + + valueIntoDest c, info, d, n.typ, body + freeTemp c, tmp + +proc genDeref(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags) = + let info = toLineInfo(c, n.info) + let tmp = c.genx(n[0], flags) + template body(target) = + buildTyped target, info, Load, typeToIr(c.m.types, n.typ): + copyTree target, tmp + + valueIntoDest c, info, d, n.typ, body + freeTemp c, tmp + +proc genConv(c: var ProcCon; n, arg: PNode; d: var Value; flags: GenFlags; opc: Opcode) = + let targetType = n.typ.skipTypes({tyDistinct}) + let argType = arg.typ.skipTypes({tyDistinct}) + + if sameBackendType(targetType, argType) or ( + argType.kind == tyProc and targetType.kind == argType.kind): + # don't do anything for lambda lifting conversions: + gen c, arg, d + return + + let info = toLineInfo(c, n.info) + let tmp = c.genx(arg, flags) + template body(target) = + buildTyped target, info, opc, typeToIr(c.m.types, n.typ): + if opc == CheckedObjConv: + target.addLabel info, CheckedGoto, c.exitLabel + copyTree target, tmp + + valueIntoDest c, info, d, n.typ, body + freeTemp c, tmp + +proc genObjOrTupleConstr(c: var ProcCon; n: PNode, d: var Value) = + # XXX x = (x.old, 22) produces wrong code ... stupid self assignments + let info = toLineInfo(c, n.info) + template body(target) = + buildTyped target, info, ObjConstr, typeToIr(c.m.types, n.typ): + for i in ord(n.kind == nkObjConstr)..<n.len: + let it = n[i] + if it.kind == nkExprColonExpr: + genField(c, it[0], Value target) + let tmp = c.genx(it[1]) + copyTree target, tmp + c.freeTemp(tmp) + else: + let tmp = c.genx(it) + target.addImmediateVal info, i + copyTree target, tmp + c.freeTemp(tmp) + + valueIntoDest c, info, d, n.typ, body + +proc genArrayConstr(c: var ProcCon; n: PNode, d: var Value) = + let seqType = n.typ.skipTypes(abstractVar-{tyTypeDesc}) + if seqType.kind == tySequence: + localError c.config, n.info, "sequence constructor not implemented" + return + + let info = toLineInfo(c, n.info) + template body(target) = + buildTyped target, info, ArrayConstr, typeToIr(c.m.types, n.typ): + for i in 0..<n.len: + let tmp = c.genx(n[i]) + copyTree target, tmp + c.freeTemp(tmp) + + valueIntoDest c, info, d, n.typ, body + +proc genAsgn2(c: var ProcCon; a, b: PNode) = + assert a != nil + assert b != nil + var d = c.genx(a) + c.gen b, d + +proc genVarSection(c: var ProcCon; n: PNode) = + for a in n: + if a.kind == nkCommentStmt: continue + #assert(a[0].kind == nkSym) can happen for transformed vars + if a.kind == nkVarTuple: + c.gen(lowerTupleUnpacking(c.m.graph, a, c.m.idgen, c.prc)) + else: + var vn = a[0] + if vn.kind == nkPragmaExpr: vn = vn[0] + if vn.kind == nkSym: + let s = vn.sym + var opc: Opcode + if sfThread in s.flags: + opc = SummonThreadLocal + elif sfGlobal in s.flags: + opc = SummonGlobal + else: + opc = Summon + c.code.addSummon toLineInfo(c, a.info), SymId(s.itemId.item), typeToIr(c.m.types, s.typ), opc + if a[2].kind != nkEmpty: + genAsgn2(c, vn, a[2]) + else: + if a[2].kind == nkEmpty: + discard "XXX assign default value to location here" + else: + genAsgn2(c, vn, a[2]) + +proc genAsgn(c: var ProcCon; n: PNode) = + var d = c.genx(n[0]) + c.gen n[1], d + +proc convStrToCStr(c: var ProcCon; n: PNode; d: var Value) = + genUnaryCp(c, n, d, "nimToCStringConv", argAt = 0) + +proc convCStrToStr(c: var ProcCon; n: PNode; d: var Value) = + genUnaryCp(c, n, d, "cstrToNimstr", argAt = 0) + +proc irModule(c: var ProcCon; owner: PSym): string = + #if owner == c.m.module: "" else: + customPath(toFullPath(c.config, owner.info)) + +proc genRdVar(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags) = + let info = toLineInfo(c, n.info) + let s = n.sym + if ast.originatingModule(s) != c.m.module: + template body(target) = + build target, info, ModuleSymUse: + target.addStrVal c.m.strings, info, irModule(c, ast.originatingModule(s)) + target.addImmediateVal info, s.itemId.item.int + + valueIntoDest c, info, d, s.typ, body + else: + template body(target) = + target.addSymUse info, SymId(s.itemId.item) + valueIntoDest c, info, d, s.typ, body + +proc genSym(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags = {}) = + let s = n.sym + case s.kind + of skVar, skForVar, skTemp, skLet, skResult, skParam, skConst: + genRdVar(c, n, d, flags) + of skProc, skFunc, skConverter, skMethod, skIterator: + if ast.originatingModule(s) == c.m.module: + # anon and generic procs have no AST so we need to remember not to forget + # to emit these: + if not c.m.pendingProcs.hasKey(s.itemId): + c.m.pendingProcs[s.itemId] = s + genRdVar(c, n, d, flags) + of skEnumField: + let info = toLineInfo(c, n.info) + template body(target) = + target.addIntVal c.m.integers, info, typeToIr(c.m.types, n.typ), s.position + valueIntoDest c, info, d, n.typ, body + else: + localError(c.config, n.info, "cannot generate code for: " & s.name.s) + +proc genNumericLit(c: var ProcCon; n: PNode; d: var Value; bits: int64) = + let info = toLineInfo(c, n.info) + template body(target) = + target.addIntVal c.m.integers, info, typeToIr(c.m.types, n.typ), bits + valueIntoDest c, info, d, n.typ, body + +proc genStringLit(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + template body(target) = + target.addStrVal c.m.strings, info, n.strVal + valueIntoDest c, info, d, n.typ, body + +proc genNilLit(c: var ProcCon; n: PNode; d: var Value) = + let info = toLineInfo(c, n.info) + template body(target) = + target.addNilVal info, typeToIr(c.m.types, n.typ) + valueIntoDest c, info, d, n.typ, body + +proc genRangeCheck(c: var ProcCon; n: PNode; d: var Value) = + # XXX to implement properly + gen c, n[0], d + +proc genArrAccess(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags) = + let arrayKind = n[0].typ.skipTypes(abstractVarRange-{tyTypeDesc}).kind + let info = toLineInfo(c, n.info) + case arrayKind + of tyString: + # XXX implement range check + let a = genx(c, n[0], flags) + let b = genx(c, n[1]) + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, ArrayAt, t: + buildTyped target, info, FieldAt, strPayloadPtrType(c.m.types): + copyTree target, a + target.addImmediateVal info, 1 # (len, p)-pair + copyTree target, b + intoDest d, info, t, body + freeTemp c, b + freeTemp c, a + + of tyCstring, tyPtr, tyUncheckedArray: + let a = genx(c, n[0], flags) + let b = genx(c, n[1]) + template body(target) = + buildTyped target, info, ArrayAt, typeToIr(c.m.types, n.typ): + copyTree target, a + copyTree target, b + valueIntoDest c, info, d, n.typ, body + + freeTemp c, b + freeTemp c, a + of tyTuple: + let a = genx(c, n[0], flags) + let b = int n[1].intVal + template body(target) = + buildTyped target, info, FieldAt, typeToIr(c.m.types, n.typ): + copyTree target, a + target.addImmediateVal info, b + valueIntoDest c, info, d, n.typ, body + + freeTemp c, a + of tyOpenArray, tyVarargs: + # XXX implement range check + let a = genx(c, n[0], flags) + let b = genx(c, n[1]) + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, ArrayAt, t: + buildTyped target, info, FieldAt, openArrayPayloadType(c.m.types, n[0].typ): + copyTree target, a + target.addImmediateVal info, 0 # (p, len)-pair + copyTree target, b + intoDest d, info, t, body + + freeTemp c, b + freeTemp c, a + of tyArray: + # XXX implement range check + let a = genx(c, n[0], flags) + var b = default(Value) + genIndex(c, n[1], n[0].typ, b) + + template body(target) = + buildTyped target, info, ArrayAt, typeToIr(c.m.types, n.typ): + copyTree target, a + copyTree target, b + valueIntoDest c, info, d, n.typ, body + freeTemp c, b + freeTemp c, a + of tySequence: + let a = genx(c, n[0], flags) + let b = genx(c, n[1]) + let t = typeToIr(c.m.types, n.typ) + template body(target) = + buildTyped target, info, ArrayAt, t: + buildTyped target, info, FieldAt, seqPayloadPtrType(c.m.types, n[0].typ): + copyTree target, a + target.addImmediateVal info, 1 # (len, p)-pair + copyTree target, b + intoDest d, info, t, body + freeTemp c, b + freeTemp c, a + else: + localError c.config, n.info, "invalid type for nkBracketExpr: " & $arrayKind + +proc genObjAccess(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags) = + let info = toLineInfo(c, n.info) + let a = genx(c, n[0], flags) + + template body(target) = + buildTyped target, info, FieldAt, typeToIr(c.m.types, n.typ): + copyTree target, a + genField c, n[1], Value(target) + + valueIntoDest c, info, d, n.typ, body + freeTemp c, a + +proc genParams(c: var ProcCon; params: PNode) = + for i in 1..<params.len: + let s = params[i].sym + c.code.addSummon toLineInfo(c, params[i].info), SymId(s.itemId.item), typeToIr(c.m.types, s.typ), SummonParam + +proc addCallConv(c: var ProcCon; info: PackedLineInfo; callConv: TCallingConvention) = + template ann(s: untyped) = c.code.addPragmaId info, s + case callConv + of ccNimCall, ccFastCall, ccClosure: ann FastCall + of ccStdCall: ann StdCall + of ccCDecl: ann CDeclCall + of ccSafeCall: ann SafeCall + of ccSysCall: ann SysCall + of ccInline: ann InlineCall + of ccNoInline: ann NoinlineCall + of ccThisCall: ann ThisCall + of ccNoConvention: ann NoCall + +proc genProc(cOuter: var ProcCon; n: PNode) = + if n.len == 0 or n[namePos].kind != nkSym: return + let prc = n[namePos].sym + if isGenericRoutineStrict(prc): return + + var c = initProcCon(cOuter.m, prc, cOuter.m.graph.config) + genParams(c, prc.typ.n) + + let body = transformBody(c.m.graph, c.m.idgen, prc, useCache) + + let info = toLineInfo(c, body.info) + build c.code, info, ProcDecl: + addSymDef c.code, info, SymId(prc.itemId.item) + addCallConv c, info, prc.typ.callConv + if {sfImportc, sfExportc} * prc.flags != {}: + build c.code, info, PragmaPair: + c.code.addPragmaId info, ExternName + c.code.addStrVal c.m.strings, info, prc.loc.r + if sfImportc in prc.flags: + if lfHeader in prc. loc.flags: + assert(prc. annex != nil) + let str = getStr(prc. annex.path) + build c.code, info, PragmaPair: + c.code.addPragmaId info, HeaderImport + c.code.addStrVal c.m.strings, info, str + elif lfDynamicLib in prc. loc.flags: + assert(prc. annex != nil) + let str = getStr(prc. annex.path) + build c.code, info, PragmaPair: + c.code.addPragmaId info, DllImport + c.code.addStrVal c.m.strings, info, str + elif sfExportc in prc.flags: + if lfDynamicLib in prc. loc.flags: + c.code.addPragmaId info, DllExport + else: + c.code.addPragmaId info, ObjExport + + gen(c, body) + patch c, body, c.exitLabel + + copyTree cOuter.code, c.code + +proc gen(c: var ProcCon; n: PNode; d: var Value; flags: GenFlags = {}) = + when defined(nimCompilerStacktraceHints): + setFrameMsg c.config$n.info & " " & $n.kind & " " & $flags + case n.kind + of nkSym: genSym(c, n, d, flags) + of nkCallKinds: + if n[0].kind == nkSym: + let s = n[0].sym + if s.magic != mNone: + genMagic(c, n, d, s.magic) + elif s.kind == skMethod: + localError(c.config, n.info, "cannot call method " & s.name.s & + " at compile time") + else: + genCall(c, n, d) + clearDest(c, n, d) + else: + genCall(c, n, d) + clearDest(c, n, d) + of nkCharLit..nkInt64Lit, nkUIntLit..nkUInt64Lit: + genNumericLit(c, n, d, n.intVal) + of nkFloatLit..nkFloat128Lit: + genNumericLit(c, n, d, cast[int64](n.floatVal)) + of nkStrLit..nkTripleStrLit: + genStringLit(c, n, d) + of nkNilLit: + if not n.typ.isEmptyType: genNilLit(c, n, d) + else: unused(c, n, d) + of nkAsgn, nkFastAsgn, nkSinkAsgn: + unused(c, n, d) + genAsgn(c, n) + of nkDotExpr: genObjAccess(c, n, d, flags) + of nkCheckedFieldExpr: genObjAccess(c, n[0], d, flags) + of nkBracketExpr: genArrAccess(c, n, d, flags) + of nkDerefExpr, nkHiddenDeref: genDeref(c, n, d, flags) + of nkAddr, nkHiddenAddr: genAddr(c, n, d, flags) + of nkIfStmt, nkIfExpr: genIf(c, n, d) + of nkWhenStmt: + # This is "when nimvm" node. Chose the first branch. + gen(c, n[0][1], d) + of nkCaseStmt: genCase(c, n, d) + of nkWhileStmt: + unused(c, n, d) + genWhile(c, n) + of nkBlockExpr, nkBlockStmt: genBlock(c, n, d) + of nkReturnStmt: genReturn(c, n) + of nkRaiseStmt: genRaise(c, n) + of nkBreakStmt: genBreak(c, n) + of nkTryStmt, nkHiddenTryStmt: genTry(c, n, d) + of nkStmtList: + #unused(c, n, d) + # XXX Fix this bug properly, lexim triggers it + for x in n: gen(c, x) + of nkStmtListExpr: + for i in 0..<n.len-1: gen(c, n[i]) + gen(c, n[^1], d, flags) + of nkPragmaBlock: + gen(c, n.lastSon, d, flags) + of nkDiscardStmt: + unused(c, n, d) + gen(c, n[0], d) + of nkHiddenStdConv, nkHiddenSubConv, nkConv: + genConv(c, n, n[1], d, flags, NumberConv) # misnomer? + of nkObjDownConv: + genConv(c, n, n[0], d, flags, ObjConv) + of nkObjUpConv: + genConv(c, n, n[0], d, flags, CheckedObjConv) + of nkVarSection, nkLetSection, nkConstSection: + unused(c, n, d) + genVarSection(c, n) + of nkLambdaKinds: + #let s = n[namePos].sym + #discard genProc(c, s) + gen(c, newSymNode(n[namePos].sym), d) + of nkChckRangeF, nkChckRange64, nkChckRange: + genRangeCheck(c, n, d) + of declarativeDefs - {nkIteratorDef}: + unused(c, n, d) + genProc(c, n) + of nkEmpty, nkCommentStmt, nkTypeSection, nkPragma, + nkTemplateDef, nkIncludeStmt, nkImportStmt, nkFromStmt, nkExportStmt, + nkMixinStmt, nkBindStmt, nkMacroDef, nkIteratorDef: + unused(c, n, d) + of nkStringToCString: convStrToCStr(c, n, d) + of nkCStringToString: convCStrToStr(c, n, d) + of nkBracket: genArrayConstr(c, n, d) + of nkCurly: genSetConstr(c, n, d) + of nkObjConstr, nkPar, nkClosure, nkTupleConstr: + genObjOrTupleConstr(c, n, d) + of nkCast: + genConv(c, n, n[1], d, flags, Cast) + of nkComesFrom: + discard "XXX to implement for better stack traces" + else: + localError(c.config, n.info, "cannot generate IR code for " & $n) + +proc genStmt*(c: var ProcCon; n: PNode): int = + result = c.code.len + var d = default(Value) + c.gen(n, d) + unused c, n, d + +proc genExpr*(c: var ProcCon; n: PNode, requiresValue = true): int = + result = c.code.len + var d = default(Value) + c.gen(n, d) + if isEmpty d: + if requiresValue: + globalError(c.config, n.info, "VM problem: d register is not set") diff --git a/compiler/nir/cir.nim b/compiler/nir/cir.nim new file mode 100644 index 000000000..90a3035dd --- /dev/null +++ b/compiler/nir/cir.nim @@ -0,0 +1,78 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# We produce C code as a list of tokens. + +import std / assertions +import .. / ic / bitabs + +type + Token = LitId # indexing into the tokens BiTable[string] + + PredefinedToken = enum + IgnoreMe = "<unused>" + EmptyToken = "" + DeclPrefix = "" # the next token is the name of a definition + CurlyLe = "{" + CurlyRi = "}" + ParLe = "(" + ParRi = ")" + BracketLe = "[" + BracketRi = "]" + NewLine = "\n" + Semicolon = ";" + Comma = ", " + Space = " " + Colon = ":" + Dot = "." + Arrow = "->" + Star = "*" + Amp = "&" + AsgnOpr = " = " + ScopeOpr = "::" + ConstKeyword = "const " + StaticKeyword = "static " + NimString = "NimString" + StrLitPrefix = "(NimChar*)" + StrLitNamePrefix = "Qstr" + LoopKeyword = "while (true) " + WhileKeyword = "while (" + IfKeyword = "if (" + ElseKeyword = "else " + SwitchKeyword = "switch (" + CaseKeyword = "case " + DefaultKeyword = "default:" + BreakKeyword = "break" + NullPtr = "nullptr" + IfNot = "if (!(" + ReturnKeyword = "return " + +const + ModulePrefix = Token(int(ReturnKeyword)+1) + +proc fillTokenTable(tab: var BiTable[string]) = + for e in EmptyToken..high(PredefinedToken): + let id = tab.getOrIncl $e + assert id == LitId(e) + +type + GeneratedCode* = object + code: seq[LitId] + tokens: BiTable[string] + +proc initGeneratedCode*(): GeneratedCode = + result = GeneratedCode(code: @[], tokens: initBiTable[string]()) + fillTokenTable(result.tokens) + +proc add*(g: var GeneratedCode; t: PredefinedToken) {.inline.} = + g.code.add Token(t) + +proc add*(g: var GeneratedCode; s: string) {.inline.} = + g.code.add g.tokens.getOrIncl(s) + diff --git a/compiler/nir/nir.nim b/compiler/nir/nir.nim new file mode 100644 index 000000000..1994a1be7 --- /dev/null +++ b/compiler/nir/nir.nim @@ -0,0 +1,71 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Nim Intermediate Representation, designed to capture all of Nim's semantics without losing too much +## precious information. Can easily be translated into C. And to JavaScript, hopefully. + +import ".." / [ast, modulegraphs, renderer, transf] +import nirtypes, nirinsts, ast2ir + +type + PCtx* = ref object of TPassContext + m: ModuleCon + c: ProcCon + oldErrorCount: int + +proc newCtx*(module: PSym; g: ModuleGraph; idgen: IdGenerator): PCtx = + let m = initModuleCon(g, g.config, idgen, module) + PCtx(m: m, c: initProcCon(m, nil, g.config), idgen: idgen) + +proc refresh*(c: PCtx; module: PSym; idgen: IdGenerator) = + c.m = initModuleCon(c.m.graph, c.m.graph.config, idgen, module) + c.c = initProcCon(c.m, nil, c.m.graph.config) + c.idgen = idgen + +proc setupGlobalCtx*(module: PSym; graph: ModuleGraph; idgen: IdGenerator) = + if graph.repl.isNil: + graph.repl = newCtx(module, graph, idgen) + #registerAdditionalOps(PCtx graph.repl) + else: + refresh(PCtx graph.repl, module, idgen) + +proc setupNirReplGen*(graph: ModuleGraph; module: PSym; idgen: IdGenerator): PPassContext = + setupGlobalCtx(module, graph, idgen) + result = PCtx graph.repl + +proc evalStmt(c: PCtx; n: PNode) = + let n = transformExpr(c.m.graph, c.idgen, c.m.module, n) + let pc = genStmt(c.c, n) + + var res = "" + if pc < c.c.code.len: + toString c.c.code, NodePos(pc), c.m.strings, c.m.integers, res + #res.add "\n" + #toString res, c.m.types.g + echo res + + +proc runCode*(c: PPassContext; n: PNode): PNode = + let c = PCtx(c) + # don't eval errornous code: + if c.oldErrorCount == c.m.graph.config.errorCounter: + evalStmt(c, n) + result = newNodeI(nkEmpty, n.info) + else: + result = n + c.oldErrorCount = c.m.graph.config.errorCounter + +when false: + type + Module* = object + types: TypeGraph + data: seq[Tree] + init: seq[Tree] + procs: seq[Tree] + diff --git a/compiler/nir/nirinsts.nim b/compiler/nir/nirinsts.nim new file mode 100644 index 000000000..f037b4f0e --- /dev/null +++ b/compiler/nir/nirinsts.nim @@ -0,0 +1,418 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## NIR instructions. Somewhat inspired by LLVM's instructions. + +import std / [assertions, hashes] +import .. / ic / bitabs +import nirlineinfos, nirtypes + +type + SymId* = distinct int + +proc `$`*(s: SymId): string {.borrow.} +proc hash*(s: SymId): Hash {.borrow.} +proc `==`*(a, b: SymId): bool {.borrow.} + +type + Opcode* = enum + Nop, + ImmediateVal, + IntVal, + StrVal, + SymDef, + SymUse, + Typed, # with type ID + PragmaId, # with Pragma ID, possible values: see PragmaKey enum + NilVal, + Label, + Goto, + CheckedGoto, + LoopLabel, + GotoLoop, # last atom + + ModuleSymUse, # `"module".x` + + ArrayConstr, + ObjConstr, + Ret, + Yld, + + Select, + SelectPair, # ((values...), Label) + SelectList, # (values...) + SelectValue, # (value) + SelectRange, # (valueA..valueB) + SummonGlobal, + SummonThreadLocal, + Summon, # x = Summon Typed <Type ID>; x begins to live + SummonParam, + SummonConst, + Kill, # `Kill x`: scope end for `x` + + AddrOf, + ArrayAt, # addr(a[i]) + FieldAt, # addr(obj.field) + + Load, # a[] + Store, # a[] = b + Asgn, # a = b + SetExc, + TestExc, + + Call, + IndirectCall, + CheckedCall, # call that can raise + CheckedIndirectCall, # call that can raise + CheckedAdd, # with overflow checking etc. + CheckedSub, + CheckedMul, + CheckedDiv, + CheckedMod, + Add, + Sub, + Mul, + Div, + Mod, + BitShl, + BitShr, + BitAnd, + BitOr, + BitXor, + BitNot, + BoolNot, + Eq, + Le, + Lt, + Cast, + NumberConv, + CheckedObjConv, + ObjConv, + TestOf, + Emit, + ProcDecl, + PragmaPair + +type + PragmaKey* = enum + FastCall, StdCall, CDeclCall, SafeCall, SysCall, InlineCall, NoinlineCall, ThisCall, NoCall, + ExternName, + HeaderImport, + DllImport, + DllExport, + ObjExport + +const + LastAtomicValue = GotoLoop + + OpcodeBits = 8'u32 + OpcodeMask = (1'u32 shl OpcodeBits) - 1'u32 + + ValueProducingAtoms = {ImmediateVal, IntVal, StrVal, SymUse, NilVal} + + ValueProducing* = { + ImmediateVal, + IntVal, + StrVal, + SymUse, + NilVal, + ModuleSymUse, + ArrayConstr, + ObjConstr, + CheckedAdd, + CheckedSub, + CheckedMul, + CheckedDiv, + CheckedMod, + Add, + Sub, + Mul, + Div, + Mod, + BitShl, + BitShr, + BitAnd, + BitOr, + BitXor, + BitNot, + BoolNot, + Eq, + Le, + Lt, + Cast, + NumberConv, + CheckedObjConv, + ObjConv, + AddrOf, + Load, + ArrayAt, + FieldAt, + TestOf + } + +type + Instr* = object # 8 bytes + x: uint32 + info: PackedLineInfo + +template kind*(n: Instr): Opcode = Opcode(n.x and OpcodeMask) +template operand(n: Instr): uint32 = (n.x shr OpcodeBits) + +template toX(k: Opcode; operand: uint32): uint32 = + uint32(k) or (operand shl OpcodeBits) + +template toX(k: Opcode; operand: LitId): uint32 = + uint32(k) or (operand.uint32 shl OpcodeBits) + +type + Tree* = object + nodes: seq[Instr] + + Values* = object + numbers: BiTable[int64] + strings: BiTable[string] + +type + PatchPos* = distinct int + NodePos* = distinct int + +const + InvalidPatchPos* = PatchPos(-1) + +proc isValid(p: PatchPos): bool {.inline.} = p.int != -1 + +proc prepare*(tree: var Tree; info: PackedLineInfo; kind: Opcode): PatchPos = + result = PatchPos tree.nodes.len + tree.nodes.add Instr(x: toX(kind, 1'u32), info: info) + +proc isAtom(tree: Tree; pos: int): bool {.inline.} = tree.nodes[pos].kind <= LastAtomicValue +proc isAtom(tree: Tree; pos: NodePos): bool {.inline.} = tree.nodes[pos.int].kind <= LastAtomicValue + +proc patch*(tree: var Tree; pos: PatchPos) = + let pos = pos.int + let k = tree.nodes[pos].kind + assert k > LastAtomicValue + let distance = int32(tree.nodes.len - pos) + assert distance > 0 + tree.nodes[pos].x = toX(k, cast[uint32](distance)) + +template build*(tree: var Tree; info: PackedLineInfo; kind: Opcode; body: untyped) = + let pos = prepare(tree, info, kind) + body + patch(tree, pos) + +template buildTyped*(tree: var Tree; info: PackedLineInfo; kind: Opcode; typ: TypeId; body: untyped) = + let pos = prepare(tree, info, kind) + tree.addTyped info, typ + body + patch(tree, pos) + +proc len*(tree: Tree): int {.inline.} = tree.nodes.len + +template rawSpan(n: Instr): int = int(operand(n)) + +proc nextChild(tree: Tree; pos: var int) {.inline.} = + if tree.nodes[pos].kind > LastAtomicValue: + assert tree.nodes[pos].operand > 0'u32 + inc pos, tree.nodes[pos].rawSpan + else: + inc pos + +iterator sons*(tree: Tree; n: NodePos): NodePos = + var pos = n.int + assert tree.nodes[pos].kind > LastAtomicValue + let last = pos + tree.nodes[pos].rawSpan + inc pos + while pos < last: + yield NodePos pos + nextChild tree, pos + +template `[]`*(t: Tree; n: NodePos): Instr = t.nodes[n.int] + +proc span(tree: Tree; pos: int): int {.inline.} = + if tree.nodes[pos].kind <= LastAtomicValue: 1 else: int(tree.nodes[pos].operand) + +proc copyTree*(dest: var Tree; src: Tree) = + let pos = 0 + let L = span(src, pos) + let d = dest.nodes.len + dest.nodes.setLen(d + L) + assert L > 0 + for i in 0..<L: + dest.nodes[d+i] = src.nodes[pos+i] + +type + LabelId* = distinct int + +proc newLabel*(labelGen: var int): LabelId {.inline.} = + result = LabelId labelGen + inc labelGen + +proc addNewLabel*(t: var Tree; labelGen: var int; info: PackedLineInfo; k: Opcode): LabelId = + assert k in {Label, LoopLabel} + result = LabelId labelGen + t.nodes.add Instr(x: toX(k, uint32(result)), info: info) + inc labelGen + +proc boolVal*(t: var Tree; info: PackedLineInfo; b: bool) = + t.nodes.add Instr(x: toX(ImmediateVal, uint32(b)), info: info) + +proc gotoLabel*(t: var Tree; info: PackedLineInfo; k: Opcode; L: LabelId) = + assert k in {Goto, GotoLoop, CheckedGoto} + t.nodes.add Instr(x: toX(k, uint32(L)), info: info) + +proc addLabel*(t: var Tree; info: PackedLineInfo; k: Opcode; L: LabelId) {.inline.} = + assert k in {Label, LoopLabel, Goto, GotoLoop, CheckedGoto} + t.nodes.add Instr(x: toX(k, uint32(L)), info: info) + +proc addSymUse*(t: var Tree; info: PackedLineInfo; s: SymId) {.inline.} = + t.nodes.add Instr(x: toX(SymUse, uint32(s)), info: info) + +proc addSymDef*(t: var Tree; info: PackedLineInfo; s: SymId) {.inline.} = + t.nodes.add Instr(x: toX(SymDef, uint32(s)), info: info) + +proc addTyped*(t: var Tree; info: PackedLineInfo; typ: TypeId) {.inline.} = + t.nodes.add Instr(x: toX(Typed, uint32(typ)), info: info) + +proc addSummon*(t: var Tree; info: PackedLineInfo; s: SymId; typ: TypeId; opc = Summon) {.inline.} = + assert opc in {Summon, SummonConst, SummonGlobal, SummonThreadLocal, SummonParam} + let x = prepare(t, info, opc) + t.nodes.add Instr(x: toX(Typed, uint32(typ)), info: info) + t.nodes.add Instr(x: toX(SymDef, uint32(s)), info: info) + patch t, x + +proc addImmediateVal*(t: var Tree; info: PackedLineInfo; x: int) = + assert x >= 0 and x < ((1 shl 32) - OpcodeBits.int) + t.nodes.add Instr(x: toX(ImmediateVal, uint32(x)), info: info) + +proc addPragmaId*(t: var Tree; info: PackedLineInfo; x: PragmaKey) = + t.nodes.add Instr(x: toX(PragmaId, uint32(x)), info: info) + +proc addIntVal*(t: var Tree; integers: var BiTable[int64]; info: PackedLineInfo; typ: TypeId; x: int64) = + buildTyped t, info, NumberConv, typ: + t.nodes.add Instr(x: toX(IntVal, uint32(integers.getOrIncl(x))), info: info) + +proc addStrVal*(t: var Tree; strings: var BiTable[string]; info: PackedLineInfo; s: string) = + t.nodes.add Instr(x: toX(StrVal, uint32(strings.getOrIncl(s))), info: info) + +proc addNilVal*(t: var Tree; info: PackedLineInfo; typ: TypeId) = + buildTyped t, info, NumberConv, typ: + t.nodes.add Instr(x: toX(NilVal, uint32(0)), info: info) + +proc escapeToNimLit(s: string; result: var string) = + result.add '"' + for c in items s: + if c < ' ' or int(c) >= 128: + result.add '\\' + result.addInt int(c) + elif c == '\\': + result.add r"\\" + elif c == '\n': + result.add r"\n" + elif c == '\r': + result.add r"\r" + elif c == '\t': + result.add r"\t" + else: + result.add c + result.add '"' + +proc toString*(t: Tree; pos: NodePos; strings: BiTable[string]; integers: BiTable[int64]; + r: var string; nesting = 0) = + if r.len > 0 and r[r.len-1] notin {' ', '\n', '(', '[', '{'}: + r.add ' ' + + case t[pos].kind + of Nop: r.add "Nop" + of ImmediateVal: + r.add $t[pos].operand + of IntVal: + r.add "IntVal " + r.add $integers[LitId t[pos].operand] + of StrVal: + escapeToNimLit(strings[LitId t[pos].operand], r) + of SymDef: + r.add "SymDef " + r.add $t[pos].operand + of SymUse: + r.add "SymUse " + r.add $t[pos].operand + of PragmaId: + r.add $cast[PragmaKey](t[pos].operand) + of Typed: + r.add "Typed " + r.add $t[pos].operand + of NilVal: + r.add "NilVal" + of Label: + r.add "L" + r.add $t[pos].operand + of Goto, CheckedGoto, LoopLabel, GotoLoop: + r.add $t[pos].kind + r.add ' ' + r.add $t[pos].operand + else: + r.add $t[pos].kind + r.add "{\n" + for i in 0..<(nesting+1)*2: r.add ' ' + for p in sons(t, pos): + toString t, p, strings, integers, r, nesting+1 + r.add "\n" + for i in 0..<nesting*2: r.add ' ' + r.add "}" + +type + Value* = distinct Tree + +proc prepare*(dest: var Value; info: PackedLineInfo; k: Opcode): PatchPos {.inline.} = + assert k in ValueProducing - ValueProducingAtoms + result = prepare(Tree(dest), info, k) + +proc patch*(dest: var Value; pos: PatchPos) {.inline.} = + patch(Tree(dest), pos) + +proc localToValue*(info: PackedLineInfo; s: SymId): Value = + result = Value(Tree()) + Tree(result).addSymUse info, s + +proc hasValue*(v: Value): bool {.inline.} = Tree(v).len > 0 + +proc isEmpty*(v: Value): bool {.inline.} = Tree(v).len == 0 + +proc extractTemp*(v: Value): SymId = + if hasValue(v) and Tree(v)[NodePos 0].kind == SymUse: + result = SymId(Tree(v)[NodePos 0].operand) + else: + result = SymId(-1) + +proc copyTree*(dest: var Tree; src: Value) = copyTree dest, Tree(src) + +proc addImmediateVal*(t: var Value; info: PackedLineInfo; x: int) = + assert x >= 0 and x < ((1 shl 32) - OpcodeBits.int) + Tree(t).nodes.add Instr(x: toX(ImmediateVal, uint32(x)), info: info) + +template build*(tree: var Value; info: PackedLineInfo; kind: Opcode; body: untyped) = + let pos = prepare(Tree(tree), info, kind) + body + patch(tree, pos) + +proc addTyped*(t: var Value; info: PackedLineInfo; typ: TypeId) {.inline.} = + addTyped(Tree(t), info, typ) + +template buildTyped*(tree: var Value; info: PackedLineInfo; kind: Opcode; typ: TypeId; body: untyped) = + let pos = prepare(tree, info, kind) + tree.addTyped info, typ + body + patch(tree, pos) + +proc addStrVal*(t: var Value; strings: var BiTable[string]; info: PackedLineInfo; s: string) = + addStrVal(Tree(t), strings, info, s) + +proc addNilVal*(t: var Value; info: PackedLineInfo; typ: TypeId) = + addNilVal Tree(t), info, typ diff --git a/compiler/nir/nirlineinfos.nim b/compiler/nir/nirlineinfos.nim new file mode 100644 index 000000000..4e86f619e --- /dev/null +++ b/compiler/nir/nirlineinfos.nim @@ -0,0 +1,78 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# For the line information we use 32 bits. They are used as follows: +# Bit 0 (AsideBit): If we have inline line information or not. If not, the +# remaining 31 bits are used as an index into a seq[(LitId, int, int)]. +# +# We use 10 bits for the "file ID", this means a program can consist of as much +# as 1024 different files. (If it uses more files than that, the overflow bit +# would be set.) +# This means we have 21 bits left to encode the (line, col) pair. We use 7 bits for the column +# so 128 is the limit and 14 bits for the line number. +# The packed representation supports files with up to 16384 lines. +# Keep in mind that whenever any limit is reached the AsideBit is set and the real line +# information is kept in a side channel. + +import std / assertions + +const + AsideBit = 1 + FileBits = 10 + LineBits = 14 + ColBits = 7 + FileMax = (1 shl FileBits) - 1 + LineMax = (1 shl LineBits) - 1 + ColMax = (1 shl ColBits) - 1 + +static: + assert AsideBit + FileBits + LineBits + ColBits == 32 + +import .. / ic / bitabs # for LitId + +type + PackedLineInfo* = distinct uint32 + + LineInfoManager* = object + aside*: seq[(LitId, int32, int32)] + +proc pack*(m: var LineInfoManager; file: LitId; line, col: int32): PackedLineInfo = + if file.uint32 <= FileMax.uint32 and line <= LineMax and col <= ColMax: + let col = if col < 0'i32: 0'u32 else: col.uint32 + let line = if line < 0'i32: 0'u32 else: line.uint32 + # use inline representation: + result = PackedLineInfo((file.uint32 shl 1'u32) or (line shl uint32(AsideBit + FileBits)) or + (col shl uint32(AsideBit + FileBits + LineBits))) + else: + result = PackedLineInfo((m.aside.len shl 1) or AsideBit) + m.aside.add (file, line, col) + +proc unpack*(m: LineInfoManager; i: PackedLineInfo): (LitId, int32, int32) = + let i = i.uint32 + if (i and 1'u32) == 0'u32: + # inline representation: + result = (LitId((i shr 1'u32) and FileMax.uint32), + int32((i shr uint32(AsideBit + FileBits)) and LineMax.uint32), + int32((i shr uint32(AsideBit + FileBits + LineBits)) and ColMax.uint32)) + else: + result = m.aside[int(i shr 1'u32)] + +proc getFileId*(m: LineInfoManager; i: PackedLineInfo): LitId = + result = unpack(m, i)[0] + +when isMainModule: + var m = LineInfoManager(aside: @[]) + for i in 0'i32..<16388'i32: + for col in 0'i32..<100'i32: + let packed = pack(m, LitId(1023), i, col) + let u = unpack(m, packed) + assert u[0] == LitId(1023) + assert u[1] == i + assert u[2] == col + echo m.aside.len diff --git a/compiler/nir/nirslots.nim b/compiler/nir/nirslots.nim new file mode 100644 index 000000000..256c25a19 --- /dev/null +++ b/compiler/nir/nirslots.nim @@ -0,0 +1,105 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Management of slots. Similar to "register allocation" +## in lower level languages. + +import std / [assertions, tables] +import nirtypes, nirinsts + +type + SlotManagerFlag* = enum + ReuseTemps, + ReuseVars + SlotKind* = enum + Temp, Perm + SlotManager* = object # "register allocator" + live: Table[SymId, (SlotKind, TypeId)] + dead: Table[TypeId, seq[SymId]] + flags: set[SlotManagerFlag] + inScope: seq[SymId] + locGen: ref int + +proc initSlotManager*(flags: set[SlotManagerFlag]; generator: ref int): SlotManager {.inline.} = + SlotManager(flags: flags, locGen: generator) + +proc allocRaw(m: var SlotManager; t: TypeId; f: SlotManagerFlag; k: SlotKind): SymId {.inline.} = + if f in m.flags and m.dead.hasKey(t) and m.dead[t].len > 0: + result = m.dead[t].pop() + else: + result = SymId(m.locGen[]) + inc m.locGen[] + m.inScope.add result + m.live[result] = (k, t) + +proc allocTemp*(m: var SlotManager; t: TypeId): SymId {.inline.} = + result = allocRaw(m, t, ReuseTemps, Temp) + +proc allocVar*(m: var SlotManager; t: TypeId): SymId {.inline.} = + result = allocRaw(m, t, ReuseVars, Perm) + +proc freeLoc*(m: var SlotManager; s: SymId) = + let t = m.live.getOrDefault(s) + assert t[1].int != 0 + m.live.del s + m.dead.mgetOrPut(t[1], @[]).add s + +proc freeTemp*(m: var SlotManager; s: SymId) = + let t = m.live.getOrDefault(s) + if t[1].int != 0 and t[0] == Temp: + m.live.del s + m.dead.mgetOrPut(t[1], @[]).add s + +iterator stillAlive*(m: SlotManager): (SymId, TypeId) = + for k, v in pairs(m.live): + yield (k, v[1]) + +proc getType*(m: SlotManager; s: SymId): TypeId {.inline.} = m.live[s][1] + +proc openScope*(m: var SlotManager) = + m.inScope.add SymId(-1) # add marker + +proc closeScope*(m: var SlotManager) = + var i = m.inScope.len - 1 + while i >= 0: + if m.inScope[i] == SymId(-1): + m.inScope.setLen i + break + dec i + +when isMainModule: + var m = initSlotManager({ReuseTemps}, new(int)) + + var g = initTypeGraph() + + let a = g.openType ArrayTy + g.addBuiltinType Int8Id + g.addArrayLen 5'u64 + let finalArrayType = sealType(g, a) + + let obj = g.openType ObjectDecl + g.addName "MyType" + + g.addField "p", finalArrayType + let objB = sealType(g, obj) + + let x = m.allocTemp(objB) + assert x.int == 0 + + let y = m.allocTemp(objB) + assert y.int == 1 + + let z = m.allocTemp(Int8Id) + assert z.int == 2 + + m.freeLoc y + let y2 = m.allocTemp(objB) + assert y2.int == 1 + + diff --git a/compiler/nir/nirtypes.nim b/compiler/nir/nirtypes.nim new file mode 100644 index 000000000..d989397a6 --- /dev/null +++ b/compiler/nir/nirtypes.nim @@ -0,0 +1,347 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Type system for NIR. Close to C's type system but without its quirks. + +import std / [assertions, hashes] +import .. / ic / bitabs + +type + NirTypeKind* = enum + VoidTy, IntTy, UIntTy, FloatTy, BoolTy, CharTy, NameVal, IntVal, + AnnotationVal, + VarargsTy, # the `...` in a C prototype; also the last "atom" + APtrTy, # pointer to aliasable memory + UPtrTy, # pointer to unique/unaliasable memory + AArrayPtrTy, # pointer to array of aliasable memory + UArrayPtrTy, # pointer to array of unique/unaliasable memory + ArrayTy, + LastArrayTy, # array of unspecified size as a last field inside an object + ObjectTy, + UnionTy, + ProcTy, + ObjectDecl, + UnionDecl, + FieldDecl + +const + TypeKindBits = 8'u32 + TypeKindMask = (1'u32 shl TypeKindBits) - 1'u32 + +type + TypeNode* = object # 4 bytes + x: uint32 + +template kind*(n: TypeNode): NirTypeKind = NirTypeKind(n.x and TypeKindMask) +template operand(n: TypeNode): uint32 = (n.x shr TypeKindBits) + +template toX(k: NirTypeKind; operand: uint32): uint32 = + uint32(k) or (operand shl TypeKindBits) + +template toX(k: NirTypeKind; operand: LitId): uint32 = + uint32(k) or (operand.uint32 shl TypeKindBits) + +type + TypeId* = distinct int + +proc `==`*(a, b: TypeId): bool {.borrow.} +proc hash*(a: TypeId): Hash {.borrow.} + +type + TypeGraph* = object + nodes: seq[TypeNode] + names: BiTable[string] + numbers: BiTable[uint64] + +const + VoidId* = TypeId 0 + Bool8Id* = TypeId 1 + Char8Id* = TypeId 2 + Int8Id* = TypeId 3 + Int16Id* = TypeId 4 + Int32Id* = TypeId 5 + Int64Id* = TypeId 6 + UInt8Id* = TypeId 7 + UInt16Id* = TypeId 8 + UInt32Id* = TypeId 9 + UInt64Id* = TypeId 10 + Float32Id* = TypeId 11 + Float64Id* = TypeId 12 + VoidPtrId* = TypeId 13 + LastBuiltinId* = 13 + +proc initTypeGraph*(): TypeGraph = + result = TypeGraph(nodes: @[ + TypeNode(x: toX(VoidTy, 0'u32)), + TypeNode(x: toX(BoolTy, 8'u32)), + TypeNode(x: toX(CharTy, 8'u32)), + TypeNode(x: toX(IntTy, 8'u32)), + TypeNode(x: toX(IntTy, 16'u32)), + TypeNode(x: toX(IntTy, 32'u32)), + TypeNode(x: toX(IntTy, 64'u32)), + TypeNode(x: toX(UIntTy, 8'u32)), + TypeNode(x: toX(UIntTy, 16'u32)), + TypeNode(x: toX(UIntTy, 32'u32)), + TypeNode(x: toX(UIntTy, 64'u32)), + TypeNode(x: toX(FloatTy, 32'u32)), + TypeNode(x: toX(FloatTy, 64'u32)), + TypeNode(x: toX(APtrTy, 2'u32)), + TypeNode(x: toX(VoidTy, 0'u32)) + ]) + assert result.nodes.len == LastBuiltinId+2 + +type + TypePatchPos* = distinct int + +const + InvalidTypePatchPos* = TypePatchPos(-1) + LastAtomicValue = VarargsTy + +proc isValid(p: TypePatchPos): bool {.inline.} = p.int != -1 + +proc prepare(tree: var TypeGraph; kind: NirTypeKind): TypePatchPos = + result = TypePatchPos tree.nodes.len + tree.nodes.add TypeNode(x: toX(kind, 1'u32)) + +proc isAtom(tree: TypeGraph; pos: int): bool {.inline.} = tree.nodes[pos].kind <= LastAtomicValue +proc isAtom(tree: TypeGraph; pos: TypeId): bool {.inline.} = tree.nodes[pos.int].kind <= LastAtomicValue + +proc patch(tree: var TypeGraph; pos: TypePatchPos) = + let pos = pos.int + let k = tree.nodes[pos].kind + assert k > LastAtomicValue + let distance = int32(tree.nodes.len - pos) + assert distance > 0 + tree.nodes[pos].x = toX(k, cast[uint32](distance)) + +proc len*(tree: TypeGraph): int {.inline.} = tree.nodes.len + +template rawSpan(n: TypeNode): int = int(operand(n)) + +proc nextChild(tree: TypeGraph; pos: var int) {.inline.} = + if tree.nodes[pos].kind > LastAtomicValue: + assert tree.nodes[pos].operand > 0'u32 + inc pos, tree.nodes[pos].rawSpan + else: + inc pos + +iterator sons*(tree: TypeGraph; n: TypeId): TypeId = + var pos = n.int + assert tree.nodes[pos].kind > LastAtomicValue + let last = pos + tree.nodes[pos].rawSpan + inc pos + while pos < last: + yield TypeId pos + nextChild tree, pos + +template `[]`*(t: TypeGraph; n: TypeId): TypeNode = t.nodes[n.int] + +proc elementType*(tree: TypeGraph; n: TypeId): TypeId {.inline.} = + assert tree[n].kind in {APtrTy, UPtrTy, AArrayPtrTy, UArrayPtrTy, ArrayTy, LastArrayTy} + result = TypeId(n.int+1) + +proc kind*(tree: TypeGraph; n: TypeId): NirTypeKind {.inline.} = tree[n].kind + +proc span(tree: TypeGraph; pos: int): int {.inline.} = + if tree.nodes[pos].kind <= LastAtomicValue: 1 else: int(tree.nodes[pos].operand) + +proc sons2(tree: TypeGraph; n: TypeId): (TypeId, TypeId) = + assert(not isAtom(tree, n.int)) + let a = n.int+1 + let b = a + span(tree, a) + result = (TypeId a, TypeId b) + +proc sons3(tree: TypeGraph; n: TypeId): (TypeId, TypeId, TypeId) = + assert(not isAtom(tree, n.int)) + let a = n.int+1 + let b = a + span(tree, a) + let c = b + span(tree, b) + result = (TypeId a, TypeId b, TypeId c) + +proc arrayLen*(tree: TypeGraph; n: TypeId): BiggestUInt = + assert tree[n].kind == ArrayTy + result = tree.numbers[LitId tree[n].operand] + +proc openType*(tree: var TypeGraph; kind: NirTypeKind): TypePatchPos = + assert kind in {APtrTy, UPtrTy, AArrayPtrTy, UArrayPtrTy, + ArrayTy, LastArrayTy, ProcTy, ObjectDecl, UnionDecl, + FieldDecl} + result = prepare(tree, kind) + +proc sealType*(tree: var TypeGraph; p: TypePatchPos): TypeId = + # TODO: Search for an existing instance of this type in + # order to reduce memory consumption. + result = TypeId(p) + patch tree, p + +proc nominalType*(tree: var TypeGraph; kind: NirTypeKind; name: string): TypeId = + assert kind in {ObjectTy, UnionTy} + result = TypeId tree.nodes.len + tree.nodes.add TypeNode(x: toX(kind, tree.names.getOrIncl(name))) + +proc addNominalType*(tree: var TypeGraph; kind: NirTypeKind; name: string) = + assert kind in {ObjectTy, UnionTy} + tree.nodes.add TypeNode(x: toX(kind, tree.names.getOrIncl(name))) + +proc addVarargs*(tree: var TypeGraph) = + tree.nodes.add TypeNode(x: toX(VarargsTy, 0'u32)) + +proc getFloat128Type*(tree: var TypeGraph): TypeId = + result = TypeId tree.nodes.len + tree.nodes.add TypeNode(x: toX(FloatTy, 128'u32)) + +proc addBuiltinType*(g: var TypeGraph; id: TypeId) = + g.nodes.add g[id] + +template firstSon(n: TypeId): TypeId = TypeId(n.int+1) + +proc addType*(g: var TypeGraph; t: TypeId) = + # We cannot simply copy `*Decl` nodes. We have to introduce `*Ty` nodes instead: + if g[t].kind in {ObjectDecl, UnionDecl}: + assert g[t.firstSon].kind == NameVal + let name = LitId g[t.firstSon].operand + if g[t].kind == ObjectDecl: + g.nodes.add TypeNode(x: toX(ObjectTy, name)) + else: + g.nodes.add TypeNode(x: toX(UnionTy, name)) + else: + let pos = t.int + let L = span(g, pos) + let d = g.nodes.len + g.nodes.setLen(d + L) + assert L > 0 + for i in 0..<L: + g.nodes[d+i] = g.nodes[pos+i] + +proc addArrayLen*(g: var TypeGraph; len: uint64) = + g.nodes.add TypeNode(x: toX(IntVal, g.numbers.getOrIncl(len))) + +proc addName*(g: var TypeGraph; name: string) = + g.nodes.add TypeNode(x: toX(NameVal, g.names.getOrIncl(name))) + +proc addAnnotation*(g: var TypeGraph; name: string) = + g.nodes.add TypeNode(x: toX(NameVal, g.names.getOrIncl(name))) + +proc addField*(g: var TypeGraph; name: string; typ: TypeId) = + let f = g.openType FieldDecl + g.addType typ + g.addName name + discard sealType(g, f) + +proc ptrTypeOf*(g: var TypeGraph; t: TypeId): TypeId = + let f = g.openType APtrTy + g.addType t + result = sealType(g, f) + +proc toString*(dest: var string; g: TypeGraph; i: TypeId) = + case g[i].kind + of VoidTy: dest.add "void" + of IntTy: + dest.add "i" + dest.addInt g[i].operand + of UIntTy: + dest.add "u" + dest.addInt g[i].operand + of FloatTy: + dest.add "f" + dest.addInt g[i].operand + of BoolTy: + dest.add "b" + dest.addInt g[i].operand + of CharTy: + dest.add "c" + dest.addInt g[i].operand + of NameVal, AnnotationVal: + dest.add g.names[LitId g[i].operand] + of IntVal: + dest.add $g.numbers[LitId g[i].operand] + of VarargsTy: + dest.add "..." + of APtrTy: + dest.add "aptr[" + toString(dest, g, g.elementType(i)) + dest.add "]" + of UPtrTy: + dest.add "uptr[" + toString(dest, g, g.elementType(i)) + dest.add "]" + of AArrayPtrTy: + dest.add "aArrayPtr[" + toString(dest, g, g.elementType(i)) + dest.add "]" + of UArrayPtrTy: + dest.add "uArrayPtr[" + toString(dest, g, g.elementType(i)) + dest.add "]" + of ArrayTy: + dest.add "Array[" + let (elems, len) = g.sons2(i) + toString(dest, g, elems) + dest.add ", " + toString(dest, g, len) + dest.add "]" + of LastArrayTy: + # array of unspecified size as a last field inside an object + dest.add "LastArrayTy[" + toString(dest, g, g.elementType(i)) + dest.add "]" + of ObjectTy: + dest.add "object " + dest.add g.names[LitId g[i].operand] + of UnionTy: + dest.add "union " + dest.add g.names[LitId g[i].operand] + of ProcTy: + dest.add "proc[" + for t in sons(g, i): toString(dest, g, t) + dest.add "]" + of ObjectDecl: + dest.add "object[" + for t in sons(g, i): + toString(dest, g, t) + dest.add '\n' + dest.add "]" + of UnionDecl: + dest.add "union[" + for t in sons(g, i): + toString(dest, g, t) + dest.add '\n' + dest.add "]" + of FieldDecl: + let (typ, name) = g.sons2(i) + toString(dest, g, typ) + dest.add ' ' + toString(dest, g, name) + +proc toString*(dest: var string; g: TypeGraph) = + var i = 0 + while i < g.len: + toString(dest, g, TypeId i) + dest.add '\n' + nextChild g, i + +proc `$`(g: TypeGraph): string = + result = "" + toString(result, g) + +when isMainModule: + var g = initTypeGraph() + + let a = g.openType ArrayTy + g.addBuiltinType Int8Id + g.addArrayLen 5'u64 + let finalArrayType = sealType(g, a) + + let obj = g.openType ObjectDecl + g.nodes.add TypeNode(x: toX(NameVal, g.names.getOrIncl("MyType"))) + + g.addField "p", finalArrayType + discard sealType(g, obj) + + echo g diff --git a/compiler/nir/types2ir.nim b/compiler/nir/types2ir.nim new file mode 100644 index 000000000..6d163c6c7 --- /dev/null +++ b/compiler/nir/types2ir.nim @@ -0,0 +1,466 @@ +# +# +# The Nim Compiler +# (c) Copyright 2023 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +import std / [assertions, tables, sets] +import ".." / [ast, types, options, sighashes, modulegraphs] +import nirtypes + +type + TypesCon* = object + processed: Table[ItemId, TypeId] + recursionCheck: HashSet[ItemId] + g*: TypeGraph + conf: ConfigRef + +proc initTypesCon*(conf: ConfigRef): TypesCon = + TypesCon(g: initTypeGraph(), conf: conf) + +proc mangle(c: var TypesCon; t: PType): string = + result = $sighashes.hashType(t, c.conf) + +template cached(c: var TypesCon; t: PType; body: untyped) = + result = c.processed.getOrDefault(t.itemId) + if result.int == 0: + body + c.processed[t.itemId] = result + +proc typeToIr*(c: var TypesCon; t: PType): TypeId + +proc collectFieldTypes(c: var TypesCon; n: PNode; dest: var Table[ItemId, TypeId]) = + case n.kind + of nkRecList: + for i in 0..<n.len: + collectFieldTypes(c, n[i], dest) + of nkRecCase: + assert(n[0].kind == nkSym) + collectFieldTypes(c, n[0], dest) + for i in 1..<n.len: + case n[i].kind + of nkOfBranch, nkElse: + collectFieldTypes c, lastSon(n[i]), dest + else: discard + of nkSym: + dest[n.sym.itemId] = typeToIr(c, n.sym.typ) + else: + assert false, "unknown node kind: " & $n.kind + +proc objectToIr(c: var TypesCon; n: PNode; fieldTypes: Table[ItemId, TypeId]; unionId: var int) = + case n.kind + of nkRecList: + for i in 0..<n.len: + objectToIr(c, n[i], fieldTypes, unionId) + of nkRecCase: + assert(n[0].kind == nkSym) + objectToIr(c, n[0], fieldTypes, unionId) + let u = openType(c.g, UnionDecl) + c.g.addName "u_" & $unionId + inc unionId + for i in 1..<n.len: + case n[i].kind + of nkOfBranch, nkElse: + let subObj = openType(c.g, ObjectDecl) + c.g.addName "uo_" & $unionId & "_" & $i + objectToIr c, lastSon(n[i]), fieldTypes, unionId + discard sealType(c.g, subObj) + else: discard + discard sealType(c.g, u) + of nkSym: + c.g.addField n.sym.name.s & "_" & $n.sym.position, fieldTypes[n.sym.itemId] + else: + assert false, "unknown node kind: " & $n.kind + +proc objectToIr(c: var TypesCon; t: PType): TypeId = + if t[0] != nil: + # ensure we emitted the base type: + discard typeToIr(c, t[0]) + + var unionId = 0 + var fieldTypes = initTable[ItemId, TypeId]() + collectFieldTypes c, t.n, fieldTypes + let obj = openType(c.g, ObjectDecl) + c.g.addName mangle(c, t) + if t[0] != nil: + c.g.addNominalType(ObjectTy, mangle(c, t[0])) + else: + c.g.addBuiltinType VoidId # object does not inherit + if not lacksMTypeField(t): + let f2 = c.g.openType FieldDecl + let voidPtr = openType(c.g, APtrTy) + c.g.addBuiltinType(VoidId) + discard sealType(c.g, voidPtr) + c.g.addName "m_type" + discard sealType(c.g, f2) # FieldDecl + + objectToIr c, t.n, fieldTypes, unionId + result = sealType(c.g, obj) + +proc objectHeaderToIr(c: var TypesCon; t: PType): TypeId = + result = c.g.nominalType(ObjectTy, mangle(c, t)) + +proc tupleToIr(c: var TypesCon; t: PType): TypeId = + var fieldTypes = newSeq[TypeId](t.len) + for i in 0..<t.len: + fieldTypes[i] = typeToIr(c, t[i]) + let obj = openType(c.g, ObjectDecl) + c.g.addName mangle(c, t) + for i in 0..<t.len: + c.g.addField "f_" & $i, fieldTypes[i] + result = sealType(c.g, obj) + +proc procToIr(c: var TypesCon; t: PType; addEnv = false): TypeId = + var fieldTypes = newSeq[TypeId](0) + for i in 0..<t.len: + if t[i] == nil or not isCompileTimeOnly(t[i]): + fieldTypes.add typeToIr(c, t[i]) + let obj = openType(c.g, ProcTy) + + case t.callConv + of ccNimCall, ccFastCall, ccClosure: c.g.addAnnotation "__fastcall" + of ccStdCall: c.g.addAnnotation "__stdcall" + of ccCDecl: c.g.addAnnotation "__cdecl" + of ccSafeCall: c.g.addAnnotation "__safecall" + of ccSysCall: c.g.addAnnotation "__syscall" + of ccInline: c.g.addAnnotation "__inline" + of ccNoInline: c.g.addAnnotation "__noinline" + of ccThisCall: c.g.addAnnotation "__thiscall" + of ccNoConvention: c.g.addAnnotation "" + + for i in 0..<fieldTypes.len: + c.g.addType fieldTypes[i] + + if addEnv: + let a = openType(c.g, APtrTy) + c.g.addBuiltinType(VoidId) + discard sealType(c.g, a) + + if tfVarargs in t.flags: + c.g.addVarargs() + result = sealType(c.g, obj) + +proc nativeInt(c: TypesCon): TypeId = + case c.conf.target.intSize + of 2: result = Int16Id + of 4: result = Int32Id + else: result = Int64Id + +proc openArrayPayloadType*(c: var TypesCon; t: PType): TypeId = + let e = lastSon(t) + let elementType = typeToIr(c, e) + let arr = c.g.openType AArrayPtrTy + c.g.addType elementType + result = sealType(c.g, arr) # LastArrayTy + +proc openArrayToIr(c: var TypesCon; t: PType): TypeId = + # object (a: ArrayPtr[T], len: int) + let e = lastSon(t) + let mangledBase = mangle(c, e) + let typeName = "NimOpenArray" & mangledBase + + let elementType = typeToIr(c, e) + #assert elementType.int >= 0, typeToString(t) + + let p = openType(c.g, ObjectDecl) + c.g.addName typeName + + let f = c.g.openType FieldDecl + let arr = c.g.openType AArrayPtrTy + c.g.addType elementType + discard sealType(c.g, arr) # LastArrayTy + c.g.addName "data" + discard sealType(c.g, f) # FieldDecl + + c.g.addField "len", c.nativeInt + + result = sealType(c.g, p) # ObjectDecl + +proc strPayloadType(c: var TypesCon): string = + result = "NimStrPayload" + let p = openType(c.g, ObjectDecl) + c.g.addName result + c.g.addField "cap", c.nativeInt + + let f = c.g.openType FieldDecl + let arr = c.g.openType LastArrayTy + c.g.addBuiltinType Char8Id + discard sealType(c.g, arr) # LastArrayTy + c.g.addName "data" + discard sealType(c.g, f) # FieldDecl + + discard sealType(c.g, p) + +proc strPayloadPtrType*(c: var TypesCon): TypeId = + let mangled = strPayloadType(c) + let ffp = c.g.openType APtrTy + c.g.addNominalType ObjectTy, mangled + result = sealType(c.g, ffp) # APtrTy + +proc stringToIr(c: var TypesCon): TypeId = + #[ + + NimStrPayload = object + cap: int + data: UncheckedArray[char] + + NimStringV2 = object + len: int + p: ptr NimStrPayload + + ]# + let payload = strPayloadType(c) + + let str = openType(c.g, ObjectDecl) + c.g.addName "NimStringV2" + c.g.addField "len", c.nativeInt + + let fp = c.g.openType FieldDecl + let ffp = c.g.openType APtrTy + c.g.addNominalType ObjectTy, "NimStrPayload" + discard sealType(c.g, ffp) # APtrTy + c.g.addName "p" + discard sealType(c.g, fp) # FieldDecl + + result = sealType(c.g, str) # ObjectDecl + +proc seqPayloadType(c: var TypesCon; t: PType): string = + #[ + NimSeqPayload[T] = object + cap: int + data: UncheckedArray[T] + ]# + let e = lastSon(t) + result = mangle(c, e) + let payloadName = "NimSeqPayload" & result + + let elementType = typeToIr(c, e) + + let p = openType(c.g, ObjectDecl) + c.g.addName payloadName + c.g.addField "cap", c.nativeInt + + let f = c.g.openType FieldDecl + let arr = c.g.openType LastArrayTy + c.g.addType elementType + discard sealType(c.g, arr) # LastArrayTy + c.g.addName "data" + discard sealType(c.g, f) # FieldDecl + discard sealType(c.g, p) + +proc seqPayloadPtrType*(c: var TypesCon; t: PType): TypeId = + let mangledBase = seqPayloadType(c, t) + let ffp = c.g.openType APtrTy + c.g.addNominalType ObjectTy, "NimSeqPayload" & mangledBase + result = sealType(c.g, ffp) # APtrTy + +proc seqToIr(c: var TypesCon; t: PType): TypeId = + #[ + NimSeqV2*[T] = object + len: int + p: ptr NimSeqPayload[T] + ]# + let mangledBase = seqPayloadType(c, t) + + let sq = openType(c.g, ObjectDecl) + c.g.addName "NimSeqV2" & mangledBase + c.g.addField "len", c.nativeInt + + let fp = c.g.openType FieldDecl + let ffp = c.g.openType APtrTy + c.g.addNominalType ObjectTy, "NimSeqPayload" & mangledBase + discard sealType(c.g, ffp) # APtrTy + c.g.addName "p" + discard sealType(c.g, fp) # FieldDecl + + result = sealType(c.g, sq) # ObjectDecl + + +proc closureToIr(c: var TypesCon; t: PType): TypeId = + # struct {fn(args, void* env), env} + # typedef struct {$n" & + # "N_NIMCALL_PTR($2, ClP_0) $3;$n" & + # "void* ClE_0;$n} $1;$n" + let mangledBase = mangle(c, t) + let typeName = "NimClosure" & mangledBase + + let procType = procToIr(c, t, addEnv=true) + + let p = openType(c.g, ObjectDecl) + c.g.addName typeName + + let f = c.g.openType FieldDecl + c.g.addType procType + c.g.addName "ClP_0" + discard sealType(c.g, f) # FieldDecl + + let f2 = c.g.openType FieldDecl + let voidPtr = openType(c.g, APtrTy) + c.g.addBuiltinType(VoidId) + discard sealType(c.g, voidPtr) + + c.g.addName "ClE_0" + discard sealType(c.g, f2) # FieldDecl + + result = sealType(c.g, p) # ObjectDecl + +proc bitsetBasetype*(c: var TypesCon; t: PType): TypeId = + let s = int(getSize(c.conf, t)) + case s + of 1: result = UInt8Id + of 2: result = UInt16Id + of 4: result = UInt32Id + of 8: result = UInt64Id + else: result = UInt8Id + +proc typeToIr*(c: var TypesCon; t: PType): TypeId = + if t == nil: return VoidId + case t.kind + of tyInt: + case int(getSize(c.conf, t)) + of 2: result = Int16Id + of 4: result = Int32Id + else: result = Int64Id + of tyInt8: result = Int8Id + of tyInt16: result = Int16Id + of tyInt32: result = Int32Id + of tyInt64: result = Int64Id + of tyFloat: + case int(getSize(c.conf, t)) + of 4: result = Float32Id + else: result = Float64Id + of tyFloat32: result = Float32Id + of tyFloat64: result = Float64Id + of tyFloat128: result = getFloat128Type(c.g) + of tyUInt: + case int(getSize(c.conf, t)) + of 2: result = UInt16Id + of 4: result = UInt32Id + else: result = UInt64Id + of tyUInt8: result = UInt8Id + of tyUInt16: result = UInt16Id + of tyUInt32: result = UInt32Id + of tyUInt64: result = UInt64Id + of tyBool: result = Bool8Id + of tyChar: result = Char8Id + of tyVoid: result = VoidId + of tySink, tyGenericInst, tyDistinct, tyAlias, tyOwned, tyRange: + result = typeToIr(c, t.lastSon) + of tyEnum: + if firstOrd(c.conf, t) < 0: + result = Int32Id + else: + case int(getSize(c.conf, t)) + of 1: result = UInt8Id + of 2: result = UInt16Id + of 4: result = Int32Id + of 8: result = Int64Id + else: result = Int32Id + of tyOrdinal, tyGenericBody, tyGenericParam, tyInferred, tyStatic: + if t.len > 0: + result = typeToIr(c, t.lastSon) + else: + result = TypeId(-1) + of tyFromExpr: + if t.n != nil and t.n.typ != nil: + result = typeToIr(c, t.n.typ) + else: + result = TypeId(-1) + of tyArray: + cached(c, t): + var n = toInt64(lengthOrd(c.conf, t)) + if n <= 0: n = 1 # make an array of at least one element + let elemType = typeToIr(c, t[1]) + let a = openType(c.g, ArrayTy) + c.g.addType(elemType) + c.g.addArrayLen uint64(n) + result = sealType(c.g, a) + of tyPtr, tyRef: + cached(c, t): + let e = t.lastSon + if e.kind == tyUncheckedArray: + let elemType = typeToIr(c, e.lastSon) + let a = openType(c.g, AArrayPtrTy) + c.g.addType(elemType) + result = sealType(c.g, a) + else: + let elemType = typeToIr(c, t.lastSon) + let a = openType(c.g, APtrTy) + c.g.addType(elemType) + result = sealType(c.g, a) + of tyVar, tyLent: + cached(c, t): + let e = t.lastSon + if e.skipTypes(abstractInst).kind in {tyOpenArray, tyVarargs}: + # skip the modifier, `var openArray` is a (ptr, len) pair too: + result = typeToIr(c, e) + else: + let elemType = typeToIr(c, e) + let a = openType(c.g, APtrTy) + c.g.addType(elemType) + result = sealType(c.g, a) + of tySet: + let s = int(getSize(c.conf, t)) + case s + of 1: result = UInt8Id + of 2: result = UInt16Id + of 4: result = UInt32Id + of 8: result = UInt64Id + else: + # array[U8, s] + cached(c, t): + let a = openType(c.g, ArrayTy) + c.g.addType(UInt8Id) + c.g.addArrayLen uint64(s) + result = sealType(c.g, a) + of tyPointer: + let a = openType(c.g, APtrTy) + c.g.addBuiltinType(VoidId) + result = sealType(c.g, a) + of tyObject: + # Objects are special as they can be recursive in Nim. This is easily solvable. + # We check if we are already "processing" t. If so, we produce `ObjectTy` + # instead of `ObjectDecl`. + cached(c, t): + if not c.recursionCheck.containsOrIncl(t.itemId): + result = objectToIr(c, t) + else: + result = objectHeaderToIr(c, t) + of tyTuple: + cached(c, t): + result = tupleToIr(c, t) + of tyProc: + cached(c, t): + if t.callConv == ccClosure: + result = closureToIr(c, t) + else: + result = procToIr(c, t) + of tyVarargs, tyOpenArray: + cached(c, t): + result = openArrayToIr(c, t) + of tyString: + cached(c, t): + result = stringToIr(c) + of tySequence: + cached(c, t): + result = seqToIr(c, t) + of tyCstring: + cached(c, t): + let a = openType(c.g, AArrayPtrTy) + c.g.addBuiltinType Char8Id + result = sealType(c.g, a) + of tyUncheckedArray: + # We already handled the `ptr UncheckedArray` in a special way. + cached(c, t): + let elemType = typeToIr(c, t.lastSon) + let a = openType(c.g, LastArrayTy) + c.g.addType(elemType) + result = sealType(c.g, a) + of tyNone, tyEmpty, tyUntyped, tyTyped, tyTypeDesc, + tyNil, tyGenericInvocation, tyProxy, tyBuiltInTypeClass, + tyUserTypeClass, tyUserTypeClassInst, tyCompositeTypeClass, + tyAnd, tyOr, tyNot, tyAnything, tyConcept, tyIterable, tyForward: + result = TypeId(-1) |