diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/destroyer.nim | 192 | ||||
| -rw-r--r-- | compiler/dfa.nim | 62 |
2 files changed, 232 insertions, 22 deletions
diff --git a/compiler/destroyer.nim b/compiler/destroyer.nim new file mode 100644 index 000000000..2ccef1724 --- /dev/null +++ b/compiler/destroyer.nim @@ -0,0 +1,192 @@ +# +# +# The Nim Compiler +# (c) Copyright 2017 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Injects destructor calls into Nim code as well as +## an optimizer that optimizes copies to moves. This is implemented as an +## AST to AST transformation so that every backend benefits from it. + +## Rules for destructor injections: +## +## foo(bar(X(), Y())) +## X and Y get destroyed after bar completes: +## +## foo( (tmpX = X(); tmpY = Y(); tmpBar = bar(tmpX, tmpY); +## destroy(tmpX); destroy(tmpY); +## tmpBar)) +## destroy(tmpBar) +## +## var x = f() +## body +## +## is the same as: +## +## var x; +## try: +## move(x, f()) +## finally: +## destroy(x) +## +## But this really just an optimization that tries to avoid to +## introduce too many temporaries, the 'destroy' is caused by +## the 'f()' call. No! That is not true for 'result = f()'! +## +## x = y where y is read only once +## is the same as: move(x, y) +## +## We also need to keep in mind here that the number of reads is +## control flow dependent: +## let x = foo() +## while true: +## y = x # only one read, but the 2nd iteration will fail! +## This also affects recursions! Only usages that do not cross +## a loop boundary (scope) and are not used in function calls +## are safe. +## +## +## x = f() is the same as: move(x, f()) +## +## x = y +## is the same as: copy(x, y) +## +## Reassignment works under this scheme: +## var x = f() +## x = y +## +## is the same as: +## +## var x; +## try: +## move(x, f()) +## copy(x, y) +## finally: +## destroy(x) +## +## result = f() must not destroy 'result'! +## +## The produced temporaries clutter up the code and might lead to +## inefficiencies. A better strategy is to collect all the temporaries +## in a single object that we put into a single try-finally that +## surrounds the proc body. This means the code stays quite efficient +## when compiled to C. +## +## foo(bar(X(), Y())) +## X and Y get destroyed after bar completes: +## +## var tmp: object +## foo( (move tmp.x, X(); move tmp.y, Y(); tmp.bar = bar(tmpX, tmpY); +## tmp.bar)) +## destroy(tmp.bar) +## destroy(tmp.x); destroy(tmp.y) + + +import + intsets, ast, astalgo, msgs, renderer, magicsys, types, idents, trees, + strutils, options, dfa, lowerings + +template hasDestructor(t: PType): bool = tfHasAsgn in t.flags + +when false: + type + VarInfo = object + hasInitValue: bool + addrTaken: bool + assigned: int # we don't care about the 'var' vs 'let' + # distinction; it's an optimization pass + read: int + scope: int # the scope the variable is declared in + + Con = object + t: Table[int, VarInfo] + owner: PSym + scope: int + + const + InterestingSyms = {skVar, skResult} + + proc collectData(c: var Con; n: PNode) + + proc collectDef(c: var Con; n: PNode; hasInitValue: bool) = + if n.kind == nkSym: + c.t[n.sym.id] = VarInfo(hasInitValue: hasInitValue, + addrTaken: false, assigned: 0, read: 0, + scope: scope) + + proc collectVarSection(c: var Con; n: PNode) = + for a in n: + if a.kind == nkCommentStmt: continue + if a.kind == nkVarTuple: + collectData(c, a.lastSon) + for i in 0 .. a.len-3: collectDef(c, a[i], a.lastSon != nil) + else: + collectData(c, a.lastSon) + if a.lastSon.kind != nkEmpty: + collectDef(c, a.sons[0], a.lastSon != nil) + + proc collectData(c: var Con; n: PNode) = + case n.kind + of nkAsgn, nkFastAsgn: + if n[0].kind == nkSym and (let s = n[0].sym; s.owner == c.owner and + s.kind in InterestingSyms): + inc c.t[s.id].assigned + collectData(c, n[1]) + of nkSym: + if (let s = n[0].sym; s.owner == c.owner and + s.kind in InterestingSyms): + inc c.t[s.id].read + of nkAddr, nkHiddenAddr: + var n = n[0] + while n.kind == nkBracketExpr: n = n[0] + if (let s = n[0].sym; s.owner == c.owner and + s.kind in InterestingSyms): + c.t[s.id].addrTaken = true + + of nkCallKinds: + if n.sons[0].kind == nkSym: + let s = n.sons[0].sym + if s.magic != mNone: + genMagic(c, n, s.magic) + else: + genCall(c, n) + else: + genCall(c, n) + of nkCharLit..nkNilLit, nkIdent: discard + of nkDotExpr, nkCheckedFieldExpr, nkBracketExpr, + nkDerefExpr, nkHiddenDeref: + collectData(c, n[0]) + of nkIfStmt, nkIfExpr: genIf(c, n) + of nkWhenStmt: + # This is "when nimvm" node. Chose the first branch. + collectData(c, n.sons[0].sons[1]) + of nkCaseStmt: genCase(c, n) + of nkWhileStmt: genWhile(c, n) + of nkBlockExpr, nkBlockStmt: genBlock(c, n) + of nkReturnStmt: genReturn(c, n) + of nkRaiseStmt: genRaise(c, n) + of nkBreakStmt: genBreak(c, n) + of nkTryStmt: genTry(c, n) + of nkStmtList, nkStmtListExpr, nkChckRangeF, nkChckRange64, nkChckRange, + nkBracket, nkCurly, nkPar, nkClosure, nkObjConstr: + for x in n: collectData(c, x) + of nkPragmaBlock: collectData(c, n.lastSon) + of nkDiscardStmt: collectData(c, n.sons[0]) + of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkExprColonExpr, nkExprEqExpr, + nkCast: + collectData(c, n.sons[1]) + of nkObjDownConv, nkStringToCString, nkCStringToString: + collectData(c, n.sons[0]) + of nkVarSection, nkLetSection: collectVarSection(c, n) + else: discard + +proc injectDestructorCalls*(owner: PSym; n: PNode; + disableExceptions = false): PNode = + when false: + var c = Con(t: initTable[int, VarInfo](), owner: owner) + collectData(c, n) + var allTemps = createObj(owner, n.info) + diff --git a/compiler/dfa.nim b/compiler/dfa.nim index 8361273c8..dd9dd4c79 100644 --- a/compiler/dfa.nim +++ b/compiler/dfa.nim @@ -26,13 +26,19 @@ import ast, astalgo, types, intsets, tables, msgs type - InstrKind = enum - goto, fork, def, use - Instr = object - n: PNode - case kind: InstrKind - of def, use: sym: PSym - of goto, fork: dest: int + InstrKind* = enum + goto, fork, def, use, + useWithinCall # this strange special case is used to get more + # move optimizations out of regular code + # XXX This is still overly pessimistic in + # call(let x = foo; bar(x)) + Instr* = object + n*: PNode + case kind*: InstrKind + of def, use, useWithinCall: sym*: PSym + of goto, fork: dest*: int + + ControlFlowGraph* = seq[Instr] TPosition = distinct int TBlock = object @@ -43,40 +49,42 @@ type undef, value, valueOrUndef Con = object - code: seq[Instr] + code: ControlFlowGraph + inCall: int blocks: seq[TBlock] proc debugInfo(info: TLineInfo): string = result = info.toFilename & ":" & $info.line -proc codeListing(c: Con, result: var string, start=0; last = -1) = +proc codeListing(c: ControlFlowGraph, result: var string, start=0; last = -1) = # for debugging purposes # first iteration: compute all necessary labels: var jumpTargets = initIntSet() - let last = if last < 0: c.code.len-1 else: min(last, c.code.len-1) + let last = if last < 0: c.len-1 else: min(last, c.len-1) for i in start..last: - if c.code[i].kind in {goto, fork}: - jumpTargets.incl(i+c.code[i].dest) + if c[i].kind in {goto, fork}: + jumpTargets.incl(i+c[i].dest) var i = start while i <= last: if i in jumpTargets: result.add("L" & $i & ":\n") result.add "\t" - result.add $c.code[i].kind + result.add $c[i].kind result.add "\t" - case c.code[i].kind - of def, use: - result.add c.code[i].sym.name.s + case c[i].kind + of def, use, useWithinCall: + result.add c[i].sym.name.s of goto, fork: result.add "L" - result.add c.code[i].dest+i + result.add c[i].dest+i result.add("\t#") - result.add(debugInfo(c.code[i].n.info)) + result.add(debugInfo(c[i].n.info)) result.add("\n") inc i if i in jumpTargets: result.add("L" & $i & ": End\n") -proc echoCfg*(c: Con; start=0; last = -1) {.deprecated.} = +proc echoCfg*(c: ControlFlowGraph; start=0; last = -1) {.deprecated.} = + ## echos the ControlFlowGraph for debugging purposes. var buf = "" codeListing(c, buf, start, last) echo buf @@ -243,7 +251,10 @@ proc genUse(c: var Con; n: PNode) = nkAddr, nkHiddenAddr}: n = n[0] if n.kind == nkSym and n.sym.kind in InterestingSyms: - c.code.add Instr(n: n, kind: use, sym: n.sym) + if c.inCall > 0: + c.code.add Instr(n: n, kind: useWithinCall, sym: n.sym) + else: + c.code.add Instr(n: n, kind: use, sym: n.sym) proc genDef(c: var Con; n: PNode) = if n.kind == nkSym and n.sym.kind in InterestingSyms: @@ -253,10 +264,12 @@ proc genCall(c: var Con; n: PNode) = gen(c, n[0]) var t = n[0].typ if t != nil: t = t.skipTypes(abstractInst) + inc c.inCall for i in 1..<n.len: gen(c, n[i]) if t != nil and i < t.len and t.sons[i].kind == tyVar: genDef(c, n[i]) + dec c.inCall proc genMagic(c: var Con; n: PNode; m: TMagic) = case m @@ -356,7 +369,7 @@ proc dfa(code: seq[Instr]) = var sid = -1 case code[pc].kind of goto, fork: discard - of use: + of use, useWithinCall: let sym = code[pc].sym if s[pc].contains(sym.id): localError(code[pc].n.info, "variable read before initialized: " & sym.name.s) @@ -417,5 +430,10 @@ proc dfa(code: seq[Instr]) = proc dataflowAnalysis*(s: PSym; body: PNode) = var c = Con(code: @[], blocks: @[]) gen(c, body) - echoCfg(c) + #echoCfg(c.code) dfa(c.code) + +proc constructCfg*(s: PSym; body: PNode): ControlFlowGraph = + ## constructs a control flow graph for ``body``. + var c = Con(code: @[], blocks: @[]) + shallowCopy(result, c.code) |