diff options
author | Andreas Rumpf <rumpf_a@web.de> | 2020-07-15 23:00:06 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-07-15 23:00:06 +0200 |
commit | c5358b0d4b1d27db04b974a0183c9b7312bc7bdc (patch) | |
tree | ca3a71953358c8f9475188045ba61c5dfb5caf87 | |
parent | 813dd1b670b953b0ac8348b04079faadace46c29 (diff) | |
download | Nim-c5358b0d4b1d27db04b974a0183c9b7312bc7bdc.tar.gz |
An optimizer for ARC (#14962)
* WIP: an optimizer for ARC * do not optimize away destructors in 'finally' if unstructured control flow is involved * optimized the optimizer * minor code cleanup * first steps to .cursor inference * cursor inference: big steps to a working solution * baby steps * better .cursor inference * new feature: expandArc for easy inspection of the AST after ARC transformations * added topt_cursor test * adapt tests * cleanups, make tests green * optimize common traversal patterns * moved test case * fixes .cursor inference so that npeg compiles once again * cursor inference: more bugfixes Co-authored-by: Clyybber <darkmine956@gmail.com>
-rw-r--r-- | compiler/commands.nim | 3 | ||||
-rw-r--r-- | compiler/cursor_inference.nim | 295 | ||||
-rw-r--r-- | compiler/injectdestructors.nim | 54 | ||||
-rw-r--r-- | compiler/optimizer.nim | 285 | ||||
-rw-r--r-- | compiler/options.nim | 2 | ||||
-rw-r--r-- | compiler/renderer.nim | 21 | ||||
-rw-r--r-- | compiler/transf.nim | 2 | ||||
-rw-r--r-- | doc/advopt.txt | 2 | ||||
-rw-r--r-- | doc/destructors.rst | 28 | ||||
-rw-r--r-- | lib/impure/nre.nim | 10 | ||||
-rw-r--r-- | tests/arc/tcomputedgoto.nim (renamed from tests/casestmt/t12785.nim) | 12 | ||||
-rw-r--r-- | tests/arc/topt_cursor.nim | 35 | ||||
-rw-r--r-- | tests/arc/topt_no_cursor.nim | 37 | ||||
-rw-r--r-- | tests/arc/topt_refcursors.nim | 39 | ||||
-rw-r--r-- | tests/arc/topt_wasmoved_destroy_pairs.nim | 92 | ||||
-rw-r--r-- | tests/arc/trtree.nim (renamed from tests/generics/trtree.nim) | 18 | ||||
-rw-r--r-- | tests/destructor/tdestructor3.nim | 11 | ||||
-rw-r--r-- | tests/destructor/tmisc_destructors.nim | 6 | ||||
-rw-r--r-- | tests/destructor/tuse_result_prevents_sinks.nim | 5 |
19 files changed, 895 insertions, 62 deletions
diff --git a/compiler/commands.nim b/compiler/commands.nim index 1984c894a..d0936a0c6 100644 --- a/compiler/commands.nim +++ b/compiler/commands.nim @@ -866,6 +866,9 @@ proc processSwitch*(switch, arg: string, pass: TCmdLinePass, info: TLineInfo; of "expandmacro": expectArg(conf, switch, arg, pass, info) conf.macrosToExpand[arg] = "T" + of "expandarc": + expectArg(conf, switch, arg, pass, info) + conf.arcToExpand[arg] = "T" of "oldgensym": processOnOffSwitchG(conf, {optNimV019}, arg, pass, info) of "useversion": diff --git a/compiler/cursor_inference.nim b/compiler/cursor_inference.nim new file mode 100644 index 000000000..7806a535f --- /dev/null +++ b/compiler/cursor_inference.nim @@ -0,0 +1,295 @@ +# +# +# The Nim Compiler +# (c) Copyright 2020 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Cursor inference: +## The basic idea was like this: Elide 'destroy(x)' calls if only +## special literals are assigned to 'x' and 'x' is not mutated or +## passed by 'var T' to something else. Special literals are string literals or +## arrays / tuples of string literals etc. +## +## However, there is a much more general rule here: Compute which variables +## can be annotated with `.cursor`. To see how and when we can do that, +## think about this question: In `dest = src` when do we really have to +## *materialize* the full copy? - Only if `dest` or `src` are mutated +## afterwards. `dest` is the potential cursor variable, so that is +## simple to analyse. And if `src` is a location derived from a +## formal parameter, we also know it is not mutated! In other words, we +## do a compile-time copy-on-write analysis. + +import + ast, types, renderer, idents, intsets, options, msgs + +type + Cursor = object + s: PSym + deps: IntSet + Con = object + cursors: seq[Cursor] + mayOwnData: IntSet + mutations: IntSet + reassigns: IntSet + config: ConfigRef + +proc locationRoot(e: PNode; followDotExpr = true): PSym = + var n = e + while true: + case n.kind + of nkSym: + if n.sym.kind in {skVar, skResult, skTemp, skLet, skForVar, skParam}: + return n.sym + else: + return nil + of nkDotExpr, nkDerefExpr, nkBracketExpr, nkHiddenDeref, + nkCheckedFieldExpr, nkAddr, nkHiddenAddr: + if followDotExpr: + n = n[0] + else: + return nil + of nkObjUpConv, nkObjDownConv: + n = n[0] + of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkCast: + n = n[1] + of nkStmtList, nkStmtListExpr: + if n.len > 0: + n = n[^1] + else: + return nil + else: + return nil + +proc addDep(c: var Con; dest: var Cursor; dependsOn: PSym) = + if dest.s != dependsOn: + dest.deps.incl dependsOn.id + +proc cursorId(c: Con; x: PSym): int = + for i in 0..<c.cursors.len: + if c.cursors[i].s == x: return i + return -1 + +proc getCursors(c: Con): IntSet = + #[ + Question: if x depends on y and y depends on z then also y depends on z. + + Or does it? + + var y = x # y gets the copy already + + var harmless = x + + y.s = "mutate" + + ]# + result = initIntSet() + for cur in c.cursors: + if not c.mayOwnData.contains(cur.s.id) and + cur.s.typ.skipTypes({tyGenericInst, tyAlias}).kind != tyOwned: + block doAdd: + for d in cur.deps: + # you cannot borrow from a location that is mutated or (owns data and is re-assigned) + if c.mutations.contains(d) or (c.mayOwnData.contains(d) and c.reassigns.contains(d)): + #echo "bah, not a cursor ", cur.s, " bad dependency ", d + break doAdd + when true: + result.incl cur.s.id + when true: + echo "computed as a cursor ", cur.s, " ", cur.deps, " ", c.config $ cur.s.info + +proc analyseAsgn(c: var Con; dest: var Cursor; n: PNode) = + case n.kind + of nkEmpty, nkCharLit..pred(nkNilLit): + # primitive literals including the empty are harmless: + discard + of nkNilLit: + when false: + # XXX think about this case. Is 'nil' an owned location? + if hasDestructor(n.typ): + # 'myref = nil' is destructive and so 'myref' should not be a cursor: + c.mayOwnData.incl dest.s.id + + of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkCast, nkConv: + analyseAsgn(c, dest, n[1]) + + of nkIfStmt, nkIfExpr: + for i in 0..<n.len: + analyseAsgn(c, dest, n[i].lastSon) + + of nkCaseStmt: + for i in 1..<n.len: + analyseAsgn(c, dest, n[i].lastSon) + + of nkStmtList, nkStmtListExpr: + if n.len > 0: + analyseAsgn(c, dest, n[^1]) + + of nkClosure: + for i in 1..<n.len: + analyseAsgn(c, dest, n[i]) + # you must destroy a closure: + c.mayOwnData.incl dest.s.id + + of nkObjConstr: + for i in 1..<n.len: + analyseAsgn(c, dest, n[i]) + if hasDestructor(n.typ): + # you must destroy a ref object: + c.mayOwnData.incl dest.s.id + + of nkCurly, nkBracket, nkPar, nkTupleConstr: + for son in n: + analyseAsgn(c, dest, son) + if n.typ.skipTypes(abstractInst).kind == tySequence: + # you must destroy a sequence: + c.mayOwnData.incl dest.s.id + + of nkSym: + if n.sym.kind in {skVar, skResult, skTemp, skLet, skForVar, skParam}: + if n.sym.flags * {sfThread, sfGlobal} != {}: + # aliasing a global is inherently dangerous: + c.mayOwnData.incl dest.s.id + else: + # otherwise it's just a dependency, nothing to worry about: + c.addDep(dest, n.sym) + + of nkDotExpr, nkBracketExpr, nkHiddenDeref, nkDerefExpr, + nkObjUpConv, nkObjDownConv, nkCheckedFieldExpr, nkAddr, nkHiddenAddr: + analyseAsgn(c, dest, n[0]) + + of nkCallKinds: + if hasDestructor(n.typ): + # calls do construct, what we construct must be destroyed, + # so dest cannot be a cursor: + c.mayOwnData.incl dest.s.id + elif n.typ.kind in {tyLent, tyVar}: + # we know the result is derived from the first argument: + let r = locationRoot(n[1]) + if r != nil: + c.addDep(dest, r) + else: + let magic = if n[0].kind == nkSym: n[0].sym.magic else: mNone + # this list is subtle, we try to answer the question if after 'dest = f(src)' + # there is a connection betwen 'src' and 'dest' so that mutations to 'src' + # also reflect 'dest': + if magic in {mNone, mMove, mSlice, mAppendStrCh, mAppendStrStr, mAppendSeqElem, mArrToSeq}: + for i in 1..<n.len: + # we always have to assume a 'select(...)' like mechanism. + # But at least we do filter out simple POD types from the + # list of dependencies via the 'hasDestructor' check for + # the root's symbol. + if hasDestructor(n[i].typ.skipTypes({tyVar, tySink, tyLent, tyGenericInst, tyAlias})): + analyseAsgn(c, dest, n[i]) + + else: + # something we cannot handle: + c.mayOwnData.incl dest.s.id + +proc rhsIsSink(c: var Con, n: PNode) = + if n.kind == nkSym and n.typ.skipTypes(abstractInst-{tyOwned}).kind == tyRef: + discard "do no pessimize simple refs further, injectdestructors.nim will prevent moving from it" + else: + let r = locationRoot(n, followDotExpr = false) + if r != nil and r.kind != skParam: + # let x = cursor? --> treat it like a sink parameter + c.mayOwnData.incl r.id + c.mutations.incl r.id + +proc analyse(c: var Con; n: PNode) = + case n.kind + of nkCallKinds: + let parameters = n[0].typ + let L = if parameters != nil: parameters.len else: 0 + + analyse(c, n[0]) + for i in 1..<n.len: + let it = n[i] + let r = locationRoot(it) + if r != nil and i < L: + let paramType = parameters[i].skipTypes({tyGenericInst, tyAlias}) + if paramType.kind in {tyVar, tySink, tyOwned}: + # pass by var? mayOwnData the root + # Else we seek to take ownership of 'r'. This is only valid when 'r' + # actually owns its data. Thus 'r' cannot be a cursor: + c.mayOwnData.incl r.id + # and we assume it might get wasMoved(...) too: + c.mutations.incl r.id + analyse(c, it) + + of nkAsgn, nkFastAsgn: + analyse(c, n[0]) + analyse(c, n[1]) + + if n[0].kind == nkSym: + if hasDestructor(n[0].typ): + # re-assignment to the full object is fundamentally different: + let idx = cursorId(c, n[0].sym) + if idx >= 0: + analyseAsgn(c, c.cursors[idx], n[1]) + + c.reassigns.incl n[0].sym.id + else: + # assignments like 'x.field = value' mean that 'x' itself cannot + # be a cursor: + let r = locationRoot(n[0]) + if r != nil and r.typ.skipTypes(abstractInst).kind notin {tyPtr, tyRef}: + # however, an assignment like 'it.field = x' does not influence r's + # cursorness property: + c.mayOwnData.incl r.id + c.mutations.incl r.id + + if hasDestructor(n[1].typ): + rhsIsSink(c, n[1]) + + of nkAddr, nkHiddenAddr: + analyse(c, n[0]) + let r = locationRoot(n[0]) + if r != nil: + c.mayOwnData.incl r.id + c.mutations.incl r.id + + of nkTupleConstr, nkBracket, nkObjConstr: + for i in ord(n.kind == nkObjConstr)..<n.len: + if n[i].kind == nkSym: + # we assume constructions with cursors are better without + # the cursors because it's likely we can move then, see + # test arc/topt_no_cursor.nim + let r = n[i].sym + c.mayOwnData.incl r.id + c.mutations.incl r.id + + of nkVarSection, nkLetSection: + for it in n: + let value = it[^1] + analyse(c, value) + if hasDestructor(it[0].typ): + for i in 0..<it.len-2: + let v = it[i] + if v.kind == nkSym and v.sym.flags * {sfThread, sfGlobal} == {}: + # assume it's a cursor: + c.cursors.add Cursor(s: it[i].sym) + if it.kind == nkVarTuple and value.kind in {nkPar, nkTupleConstr} and + it.len-2 == value.len: + # this might mayOwnData it again: + analyseAsgn(c, c.cursors[^1], value[i]) + rhsIsSink(c, value[i]) + else: + # this might mayOwnData it again: + analyseAsgn(c, c.cursors[^1], value) + rhsIsSink(c, value) + + of nkNone..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef, + nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo, + nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt, + nkExportStmt, nkPragma, nkCommentStmt, nkBreakState, nkTypeOfExpr: + discard + else: + for child in n: analyse(c, child) + +proc computeCursors*(n: PNode; config: ConfigRef): IntSet = + var c = Con(config: config) + analyse(c, n) + result = getCursors c diff --git a/compiler/injectdestructors.nim b/compiler/injectdestructors.nim index 98cfb4743..556d098f4 100644 --- a/compiler/injectdestructors.nim +++ b/compiler/injectdestructors.nim @@ -13,18 +13,11 @@ ## See doc/destructors.rst for a spec of the implemented rewrite rules -## XXX Optimization to implement: if a local variable is only assigned -## string literals as in ``let x = conf: "foo" else: "bar"`` do not -## produce a destructor call for ``x``. The address of ``x`` must also -## not have been taken. ``x = "abc"; x.add(...)`` - -# Todo: -# - eliminate 'wasMoved(x); destroy(x)' pairs as a post processing step. - import - intsets, ast, astalgo, msgs, renderer, magicsys, types, idents, + intsets, strtabs, ast, astalgo, msgs, renderer, magicsys, types, idents, strutils, options, dfa, lowerings, tables, modulegraphs, msgs, - lineinfos, parampatterns, sighashes, liftdestructors + lineinfos, parampatterns, sighashes, liftdestructors, optimizer, + cursor_inference from trees import exprStructuralEquivalent, getRoot @@ -42,6 +35,7 @@ type Con = object owner: PSym g: ControlFlowGraph + cursors: IntSet graph: ModuleGraph otherRead: PNode inLoop, inSpawn: int @@ -155,6 +149,17 @@ proc isLastRead(location: PNode; cfg: ControlFlowGraph; otherRead: var PNode; pc pc = min(variantA, variantB) return pc +proc isCursor(n: PNode; c: Con): bool = + case n.kind + of nkSym: + result = sfCursor in n.sym.flags or c.cursors.contains(n.sym.id) + of nkDotExpr: + result = sfCursor in n[1].sym.flags + of nkCheckedFieldExpr: + result = isCursor(n[0], c) + else: + result = false + proc isLastRead(n: PNode; c: var Con): bool = # first we need to search for the instruction that belongs to 'n': var instr = -1 @@ -486,17 +491,6 @@ proc ensureDestruction(arg, orig: PNode; c: var Con; s: var Scope): PNode = else: result = arg -proc isCursor(n: PNode): bool = - case n.kind - of nkSym: - result = sfCursor in n.sym.flags - of nkDotExpr: - result = sfCursor in n[1].sym.flags - of nkCheckedFieldExpr: - result = isCursor(n[0]) - else: - result = false - proc cycleCheck(n: PNode; c: var Con) = if c.graph.config.selectedGC != gcArc: return var value = n[1] @@ -727,7 +721,8 @@ proc p(n: PNode; c: var Con; s: var Scope; mode: ProcessMode): PNode = elif n.kind in {nkBracket, nkObjConstr, nkTupleConstr, nkClosure, nkNilLit} + nkCallKinds + nkLiterals: result = p(n, c, s, consumed) - elif ((n.kind == nkSym and isSinkParam(n.sym)) or isAnalysableFieldAccess(n, c.owner)) and isLastRead(n, c): + elif ((n.kind == nkSym and isSinkParam(n.sym)) or isAnalysableFieldAccess(n, c.owner)) and + isLastRead(n, c) and not (n.kind == nkSym and isCursor(n, c)): # Sinked params can be consumed only once. We need to reset the memory # to disable the destructor which we have not elided result = destructiveMoveVar(n, c, s) @@ -830,7 +825,7 @@ proc p(n: PNode; c: var Con; s: var Scope; mode: ProcessMode): PNode = if it.kind == nkVarTuple and hasDestructor(ri.typ): let x = lowerTupleUnpacking(c.graph, it, c.owner) result.add p(x, c, s, consumed) - elif it.kind == nkIdentDefs and hasDestructor(it[0].typ) and not isCursor(it[0]): + elif it.kind == nkIdentDefs and hasDestructor(it[0].typ) and not isCursor(it[0], c): for j in 0..<it.len-2: let v = it[j] if v.kind == nkSym: @@ -851,7 +846,7 @@ proc p(n: PNode; c: var Con; s: var Scope; mode: ProcessMode): PNode = result.add v of nkAsgn, nkFastAsgn: if hasDestructor(n[0].typ) and n[1].kind notin {nkProcDef, nkDo, nkLambda} and - not isCursor(n[0]): + not isCursor(n[0], c): # rule (self-assignment-removal): if n[1].kind == nkSym and n[0].kind == nkSym and n[0].sym == n[1].sym: result = newNodeI(nkEmpty, n.info) @@ -988,7 +983,7 @@ proc moveOrCopy(dest, ri: PNode; c: var Con; s: var Scope, isDecl = false): PNod let snk = c.genSink(dest, ri, isDecl) result = newTree(nkStmtList, snk, c.genWasMoved(ri)) elif ri.sym.kind != skParam and ri.sym.owner == c.owner and - isLastRead(ri, c) and canBeMoved(c, dest.typ): + isLastRead(ri, c) and canBeMoved(c, dest.typ) and not isCursor(ri, c): # Rule 3: `=sink`(x, z); wasMoved(z) let snk = c.genSink(dest, ri, isDecl) result = newTree(nkStmtList, snk, c.genWasMoved(ri)) @@ -1048,6 +1043,8 @@ proc injectDestructorCalls*(g: ModuleGraph; owner: PSym; n: PNode): PNode = echoCfg(c.g) echo n + c.cursors = computeCursors(n, g.config) + var scope: Scope let body = p(n, c, scope, normal) @@ -1059,7 +1056,12 @@ proc injectDestructorCalls*(g: ModuleGraph; owner: PSym; n: PNode): PNode = scope.final.add c.genDestroy(params[i]) #if optNimV2 in c.graph.config.globalOptions: # injectDefaultCalls(n, c) - result = processScope(c, scope, body) + result = optimize processScope(c, scope, body) dbg: echo ">---------transformed-to--------->" echo renderTree(result, {renderIds}) + + if g.config.arcToExpand.hasKey(owner.name.s): + echo "--expandArc: ", owner.name.s + echo renderTree(result, {renderIr}) + echo "-- end of expandArc ------------------------" diff --git a/compiler/optimizer.nim b/compiler/optimizer.nim new file mode 100644 index 000000000..5d1139bfd --- /dev/null +++ b/compiler/optimizer.nim @@ -0,0 +1,285 @@ +# +# +# The Nim Compiler +# (c) Copyright 2020 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Optimizer: +## - elide 'wasMoved(x); destroy(x)' pairs +## - recognize "all paths lead to 'wasMoved(x)'" + +import + ast, renderer, idents, intsets + +from trees import exprStructuralEquivalent + +const + nfMarkForDeletion = nfNone # faster than a lookup table + +type + BasicBlock = object + wasMovedLocs: seq[PNode] + kind: TNodeKind + hasReturn, hasBreak: bool + label: PSym # can be nil + parent: ptr BasicBlock + + Con = object + somethingTodo: bool + inFinally: int + +proc nestedBlock(parent: var BasicBlock; kind: TNodeKind): BasicBlock = + BasicBlock(wasMovedLocs: @[], kind: kind, hasReturn: false, hasBreak: false, + label: nil, parent: addr(parent)) + +proc breakStmt(b: var BasicBlock; n: PNode) = + var it = addr(b) + while it != nil: + it.wasMovedLocs.setLen 0 + it.hasBreak = true + + if n.kind == nkSym: + if it.label == n.sym: break + else: + # unnamed break leaves the block is nkWhileStmt or the like: + if it.kind in {nkWhileStmt, nkBlockStmt, nkBlockExpr}: break + + it = it.parent + +proc returnStmt(b: var BasicBlock) = + b.hasReturn = true + var it = addr(b) + while it != nil: + it.wasMovedLocs.setLen 0 + it = it.parent + +proc mergeBasicBlockInfo(parent: var BasicBlock; this: BasicBlock) {.inline.} = + if this.hasReturn: + parent.wasMovedLocs.setLen 0 + parent.hasReturn = true + +proc wasMovedTarget(matches: var IntSet; branch: seq[PNode]; moveTarget: PNode): bool = + result = false + for i in 0..<branch.len: + if exprStructuralEquivalent(branch[i][1].skipAddr, moveTarget, + strictSymEquality = true): + result = true + matches.incl i + +proc intersect(summary: var seq[PNode]; branch: seq[PNode]) = + # keep all 'wasMoved(x)' calls in summary that are also in 'branch': + var i = 0 + var matches = initIntSet() + while i < summary.len: + if wasMovedTarget(matches, branch, summary[i][1].skipAddr): + inc i + else: + summary.del i + for m in matches: + summary.add branch[m] + + +proc invalidateWasMoved(c: var BasicBlock; x: PNode) = + var i = 0 + while i < c.wasMovedLocs.len: + if exprStructuralEquivalent(c.wasMovedLocs[i][1].skipAddr, x, + strictSymEquality = true): + c.wasMovedLocs.del i + else: + inc i + +proc wasMovedDestroyPair(c: var Con; b: var BasicBlock; d: PNode) = + var i = 0 + while i < b.wasMovedLocs.len: + if exprStructuralEquivalent(b.wasMovedLocs[i][1].skipAddr, d[1].skipAddr, + strictSymEquality = true): + b.wasMovedLocs[i].flags.incl nfMarkForDeletion + c.somethingTodo = true + d.flags.incl nfMarkForDeletion + b.wasMovedLocs.del i + else: + inc i + +proc analyse(c: var Con; b: var BasicBlock; n: PNode) = + case n.kind + of nkCallKinds: + var special = false + var reverse = false + if n[0].kind == nkSym: + let s = n[0].sym + if s.magic == mWasMoved: + b.wasMovedLocs.add n + special = true + elif s.name.s == "=destroy": + if c.inFinally > 0 and (b.hasReturn or b.hasBreak): + discard "cannot optimize away the destructor" + else: + c.wasMovedDestroyPair b, n + special = true + elif s.name.s == "=sink": + reverse = true + + if not special: + if not reverse: + for i in 0 ..< n.len: + analyse(c, b, n[i]) + else: + #[ Test tmatrix.test3: + Prevent this from being elided. We should probably + find a better solution... + + `=sink`(b, - ( + let blitTmp = b; + wasMoved(b); + blitTmp + a) + `=destroy`(b) + + ]# + for i in countdown(n.len-1, 0): + analyse(c, b, n[i]) + if canRaise(n[0]): returnStmt(b) + + of nkSym: + # any usage of the location before destruction implies we + # cannot elide the 'wasMoved(x)': + b.invalidateWasMoved n + + of nkNone..pred(nkSym), succ(nkSym)..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef, + nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo, + nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt, + nkExportStmt, nkPragma, nkCommentStmt, nkBreakState, nkTypeOfExpr: + discard "do not follow the construct" + + of nkAsgn, nkFastAsgn: + # reverse order, see remark for `=sink`: + analyse(c, b, n[1]) + analyse(c, b, n[0]) + + of nkIfStmt, nkIfExpr: + let isExhaustive = n[^1].kind in {nkElse, nkElseExpr} + var wasMovedSet: seq[PNode] = @[] + + for i in 0 ..< n.len: + var branch = nestedBlock(b, n[i].kind) + + analyse(c, branch, n[i]) + mergeBasicBlockInfo(b, branch) + if isExhaustive: + if i == 0: + wasMovedSet = move(branch.wasMovedLocs) + else: + wasMovedSet.intersect(branch.wasMovedLocs) + for i in 0..<wasMovedSet.len: + b.wasMovedLocs.add wasMovedSet[i] + + of nkCaseStmt: + let isExhaustive = skipTypes(n[0].typ, + abstractVarRange-{tyTypeDesc}).kind notin {tyFloat..tyFloat128, tyString} or + n[^1].kind == nkElse + + analyse(c, b, n[0]) + + var wasMovedSet: seq[PNode] = @[] + + for i in 1 ..< n.len: + var branch = nestedBlock(b, n[i].kind) + + analyse(c, branch, n[i]) + mergeBasicBlockInfo(b, branch) + if isExhaustive: + if i == 1: + wasMovedSet = move(branch.wasMovedLocs) + else: + wasMovedSet.intersect(branch.wasMovedLocs) + for i in 0..<wasMovedSet.len: + b.wasMovedLocs.add wasMovedSet[i] + + of nkTryStmt: + for i in 0 ..< n.len: + var tryBody = nestedBlock(b, nkTryStmt) + + analyse(c, tryBody, n[i]) + mergeBasicBlockInfo(b, tryBody) + + of nkWhileStmt: + analyse(c, b, n[0]) + var loopBody = nestedBlock(b, nkWhileStmt) + analyse(c, loopBody, n[1]) + mergeBasicBlockInfo(b, loopBody) + + of nkBlockStmt, nkBlockExpr: + var blockBody = nestedBlock(b, n.kind) + if n[0].kind == nkSym: + blockBody.label = n[0].sym + analyse(c, blockBody, n[1]) + mergeBasicBlockInfo(b, blockBody) + + of nkBreakStmt: + breakStmt(b, n[0]) + + of nkReturnStmt, nkRaiseStmt: + for child in n: analyse(c, b, child) + returnStmt(b) + + of nkFinally: + inc c.inFinally + for child in n: analyse(c, b, child) + dec c.inFinally + + else: + for child in n: analyse(c, b, child) + +proc opt(c: Con; n, parent: PNode; parentPos: int) = + template recurse() = + let x = shallowCopy(n) + for i in 0 ..< n.len: + opt(c, n[i], x, i) + parent[parentPos] = x + + case n.kind + of nkCallKinds: + if nfMarkForDeletion in n.flags: + parent[parentPos] = newNodeI(nkEmpty, n.info) + else: + recurse() + + of nkNone..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef, + nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo, + nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt, + nkExportStmt, nkPragma, nkCommentStmt, nkBreakState, nkTypeOfExpr: + parent[parentPos] = n + + else: + recurse() + + +proc optimize*(n: PNode): PNode = + # optimize away simple 'wasMoved(x); destroy(x)' pairs. + #[ Unfortunately this optimization is only really safe when no exceptions + are possible, see for example: + + proc main(inp: string; cond: bool) = + if cond: + try: + var s = ["hi", inp & "more"] + for i in 0..4: + use s + consume(s) + wasMoved(s) + finally: + destroy(s) + + Now assume 'use' raises, then we shouldn't do the 'wasMoved(s)' + ]# + var c: Con + var b: BasicBlock + analyse(c, b, n) + if c.somethingTodo: + result = shallowCopy(n) + for i in 0 ..< n.safeLen: + opt(c, n[i], result, i) + else: + result = n diff --git a/compiler/options.nim b/compiler/options.nim index 80881d903..8b73c07fc 100644 --- a/compiler/options.nim +++ b/compiler/options.nim @@ -235,6 +235,7 @@ type options*: TOptions # (+) globalOptions*: TGlobalOptions # (+) macrosToExpand*: StringTableRef + arcToExpand*: StringTableRef m*: MsgConfig evalTemplateCounter*: int evalMacroCounter*: int @@ -410,6 +411,7 @@ proc newConfigRef*(): ConfigRef = options: DefaultOptions, globalOptions: DefaultGlobalOptions, macrosToExpand: newStringTable(modeStyleInsensitive), + arcToExpand: newStringTable(modeStyleInsensitive), m: initMsgConfig(), evalExpr: "", cppDefines: initHashSet[string](), diff --git a/compiler/renderer.nim b/compiler/renderer.nim index 449ee4504..3cd532e15 100644 --- a/compiler/renderer.nim +++ b/compiler/renderer.nim @@ -20,7 +20,8 @@ import type TRenderFlag* = enum renderNone, renderNoBody, renderNoComments, renderDocComments, - renderNoPragmas, renderIds, renderNoProcDefs, renderSyms, renderRunnableExamples + renderNoPragmas, renderIds, renderNoProcDefs, renderSyms, renderRunnableExamples, + renderIr TRenderFlags* = set[TRenderFlag] TRenderTok* = object kind*: TTokType @@ -47,11 +48,20 @@ type pendingNewlineCount: int fid*: FileIndex config*: ConfigRef + mangler: seq[PSym] # We render the source code in a two phases: The first # determines how long the subtree will likely be, the second # phase appends to a buffer that will be the output. +proc disamb(g: var TSrcGen; s: PSym): int = + # we group by 's.name.s' to compute the stable name ID. + result = 0 + for i in 0 ..< g.mangler.len: + if s == g.mangler[i]: return result + if s.name.s == g.mangler[i].name.s: inc result + g.mangler.add s + proc isKeyword*(i: PIdent): bool = if (i.id >= ord(tokKeywordLow) - ord(tkSymbol)) and (i.id <= ord(tokKeywordHigh) - ord(tkSymbol)): @@ -850,7 +860,12 @@ proc gident(g: var TSrcGen, n: PNode) = t = tkSymbol else: t = tkOpr - if n.kind == nkSym and (renderIds in g.flags or sfGenSym in n.sym.flags or n.sym.kind == skTemp): + if renderIr in g.flags and n.kind == nkSym: + let localId = disamb(g, n.sym) + if localId != 0 and n.sym.magic == mNone: + s.add '_' + s.addInt localId + elif n.kind == nkSym and (renderIds in g.flags or sfGenSym in n.sym.flags or n.sym.kind == skTemp): s.add '_' s.addInt n.sym.id when defined(debugMagics): @@ -1022,7 +1037,7 @@ proc gsub(g: var TSrcGen, n: PNode, c: TContext) = else: put(g, tkSymbol, "(wrong conv)") of nkHiddenCallConv: - if renderIds in g.flags: + if {renderIds, renderIr} * g.flags != {}: accentedName(g, n[0]) put(g, tkParLe, "(") gcomma(g, n, 1) diff --git a/compiler/transf.nim b/compiler/transf.nim index 10a2680ae..be559abb8 100644 --- a/compiler/transf.nim +++ b/compiler/transf.nim @@ -233,7 +233,7 @@ proc hasContinue(n: PNode): bool = proc newLabel(c: PTransf, n: PNode): PSym = result = newSym(skLabel, nil, getCurrOwner(c), n.info) - result.name = getIdent(c.graph.cache, genPrefix & $result.id) + result.name = getIdent(c.graph.cache, genPrefix) proc transformBlock(c: PTransf, n: PNode): PNode = var labl: PSym diff --git a/doc/advopt.txt b/doc/advopt.txt index 135f297c4..6665ce537 100644 --- a/doc/advopt.txt +++ b/doc/advopt.txt @@ -122,6 +122,8 @@ Advanced options: use the provided namespace for the generated C++ code, if no namespace is provided "Nim" will be used --expandMacro:MACRO dump every generated AST from MACRO + --expandArc:PROCNAME show how PROCNAME looks like after diverse optimizations + before the final backend phase (mostly ARC/ORC specific) --excludePath:PATH exclude a path from the list of search paths --dynlibOverride:SYMBOL marks SYMBOL so that dynlib:SYMBOL has no effect and can be statically linked instead; diff --git a/doc/destructors.rst b/doc/destructors.rst index fefc646f5..6cab6e1d2 100644 --- a/doc/destructors.rst +++ b/doc/destructors.rst @@ -354,7 +354,8 @@ Destructor removal ``wasMoved(x);`` followed by a `=destroy(x)` operation cancel each other out. An implementation is encouraged to exploit this in order to improve -efficiency and code sizes. +efficiency and code sizes. The current implementation does perform this +optimization. Self assignments @@ -509,6 +510,31 @@ to be safe, but for ``ptr`` the compiler has to remain silent about possible problems. +Cursor inference / copy elision +=============================== + +The current implementation also performs `.cursor` inference. Cursor inference is +a form of copy elision. + +To see how and when we can do that, think about this question: In `dest = src` when +do we really have to *materialize* the full copy? - Only if `dest` or `src` are mutated +afterwards. If `dest` is a local variable that is simple to analyse. And if `src` is a +location derived from a formal parameter, we also know it is not mutated! In other +words, we do a compile-time copy-on-write analysis. + +This means that "borrowed" views can be written naturally and without explicit pointer +indirections: + +.. code-block:: nim + + proc main(tab: Table[string, string]) = + let v = tab["key"] # inferred as .cursor because 'tab' is not mutated. + # no copy into 'v', no destruction of 'v'. + use(v) + useItAgain(v) + + + Owned refs ========== diff --git a/lib/impure/nre.nim b/lib/impure/nre.nim index 653d4d1c5..0817ca4ec 100644 --- a/lib/impure/nre.nim +++ b/lib/impure/nre.nim @@ -498,7 +498,7 @@ proc re*(pattern: string): Regex = initRegex(pattern, flags, study) proc matchImpl(str: string, pattern: Regex, start, endpos: int, flags: int): Option[RegexMatch] = - var myResult = RegexMatch(pattern : pattern, str : str) + var myResult = RegexMatch(pattern: pattern, str: str) # See PCRE man pages. # 2x capture count to make room for start-end pairs # 1x capture count as slack space for PCRE @@ -528,13 +528,13 @@ proc matchImpl(str: string, pattern: Regex, start, endpos: int, flags: int): Opt of pcre.ERROR_NULL: raise newException(AccessViolationDefect, "Expected non-null parameters") of pcre.ERROR_BADOPTION: - raise RegexInternalError(msg : "Unknown pattern flag. Either a bug or " & + raise RegexInternalError(msg: "Unknown pattern flag. Either a bug or " & "outdated PCRE.") of pcre.ERROR_BADUTF8, pcre.ERROR_SHORTUTF8, pcre.ERROR_BADUTF8_OFFSET: - raise InvalidUnicodeError(msg : "Invalid unicode byte sequence", - pos : myResult.pcreMatchBounds[0].a) + raise InvalidUnicodeError(msg: "Invalid unicode byte sequence", + pos: myResult.pcreMatchBounds[0].a) else: - raise RegexInternalError(msg : "Unknown internal error: " & $execRet) + raise RegexInternalError(msg: "Unknown internal error: " & $execRet) proc match*(str: string, pattern: Regex, start = 0, endpos = int.high): Option[RegexMatch] = ## Like ` ``find(...)`` <#proc-find>`_, but anchored to the start of the diff --git a/tests/casestmt/t12785.nim b/tests/arc/tcomputedgoto.nim index 7177fb9c2..8af17b56e 100644 --- a/tests/casestmt/t12785.nim +++ b/tests/arc/tcomputedgoto.nim @@ -1,15 +1,7 @@ discard """ cmd: '''nim c --newruntime $file''' - output: '''copied -copied -2 -destroyed -destroyed -copied -copied -2 -destroyed -destroyed''' + output: '''2 +2''' """ type diff --git a/tests/arc/topt_cursor.nim b/tests/arc/topt_cursor.nim new file mode 100644 index 000000000..6b923cf76 --- /dev/null +++ b/tests/arc/topt_cursor.nim @@ -0,0 +1,35 @@ +discard """ + output: '''("string here", 80)''' + cmd: '''nim c --gc:arc --expandArc:main --hint:Performance:off $file''' + nimout: '''--expandArc: main + +var + :tmpD + :tmpD_1 + :tmpD_2 +try: + var x = ("hi", 5) + x = if cond: + :tmpD = ("different", 54) + :tmpD else: + :tmpD_1 = ("string here", 80) + :tmpD_1 + echo [ + :tmpD_2 = `$`(x) + :tmpD_2] +finally: + `=destroy`(:tmpD_2) +-- end of expandArc ------------------------''' +""" + +proc main(cond: bool) = + var x = ("hi", 5) # goal: computed as cursor + + x = if cond: + ("different", 54) + else: + ("string here", 80) + + echo x + +main(false) diff --git a/tests/arc/topt_no_cursor.nim b/tests/arc/topt_no_cursor.nim new file mode 100644 index 000000000..3d3262491 --- /dev/null +++ b/tests/arc/topt_no_cursor.nim @@ -0,0 +1,37 @@ +discard """ + output: '''(repo: "", package: "meo", ext: "")''' + cmd: '''nim c --gc:arc --expandArc:newTarget --hint:Performance:off $file''' + nimout: '''--expandArc: newTarget + +var + splat + :tmp + :tmp_1 + :tmp_2 +splat = splitFile(path) +:tmp = splat.dir +wasMoved(splat.dir) +:tmp_1 = splat.name +wasMoved(splat.name) +:tmp_2 = splat.ext +wasMoved(splat.ext) +result = ( + let blitTmp = :tmp + blitTmp, + let blitTmp_1 = :tmp_1 + blitTmp_1, + let blitTmp_2 = :tmp_2 + blitTmp_2) +`=destroy`(splat) +-- end of expandArc ------------------------''' +""" + +import os + +type Target = tuple[repo, package, ext: string] + +proc newTarget*(path: string): Target = + let splat = path.splitFile + result = (repo: splat.dir, package: splat.name, ext: splat.ext) + +echo newTarget("meo") diff --git a/tests/arc/topt_refcursors.nim b/tests/arc/topt_refcursors.nim new file mode 100644 index 000000000..7316e2beb --- /dev/null +++ b/tests/arc/topt_refcursors.nim @@ -0,0 +1,39 @@ +discard """ + output: '''''' + cmd: '''nim c --gc:arc --expandArc:traverse --hint:Performance:off $file''' + nimout: '''--expandArc: traverse + +var it = root +block :tmp: + while ( + not (it == nil)): + echo [it.s] + it = it.ri +var jt = root +block :tmp_1: + while ( + not (jt == nil)): + let ri_1 = jt.ri + echo [jt.s] + jt = ri_1 +-- end of expandArc ------------------------''' +""" + +type + Node = ref object + le, ri: Node + s: string + +proc traverse(root: Node) = + var it = root + while it != nil: + echo it.s + it = it.ri + + var jt = root + while jt != nil: + let ri = jt.ri + echo jt.s + jt = ri + +traverse(nil) diff --git a/tests/arc/topt_wasmoved_destroy_pairs.nim b/tests/arc/topt_wasmoved_destroy_pairs.nim new file mode 100644 index 000000000..4d248492b --- /dev/null +++ b/tests/arc/topt_wasmoved_destroy_pairs.nim @@ -0,0 +1,92 @@ +discard """ + output: '''''' + cmd: '''nim c --gc:arc --expandArc:main --expandArc:tfor --hint:Performance:off $file''' + nimout: '''--expandArc: main + +var + a + b + x +x = f() +if cond: + add(a): + let blitTmp = x + blitTmp +else: + add(b): + let blitTmp_1 = x + blitTmp_1 +`=destroy`(b) +`=destroy`(a) +-- end of expandArc ------------------------ +--expandArc: tfor + +var + a + b + x +try: + x = f() + block :tmp: + var i + var i_1 = 0 + block :tmp_1: + while i_1 < 4: + var :tmpD + i = i_1 + if i == 2: + return + add(a): + wasMoved(:tmpD) + `=`(:tmpD, x) + :tmpD + inc i_1, 1 + if cond: + add(a): + let blitTmp = x + wasMoved(x) + blitTmp + else: + add(b): + let blitTmp_1 = x + wasMoved(x) + blitTmp_1 +finally: + `=destroy`(x) + `=destroy_1`(b) + `=destroy_1`(a) +-- end of expandArc ------------------------''' +""" + +proc f(): seq[int] = + @[1, 2, 3] + +proc main(cond: bool) = + var a, b: seq[seq[int]] + var x = f() + if cond: + a.add x + else: + b.add x + +# all paths move 'x' so no wasMoved(x); destroy(x) pair should be left in the +# AST. + +main(false) + + +proc tfor(cond: bool) = + var a, b: seq[seq[int]] + + var x = f() + + for i in 0 ..< 4: + if i == 2: return + a.add x + + if cond: + a.add x + else: + b.add x + +tfor(false) diff --git a/tests/generics/trtree.nim b/tests/arc/trtree.nim index b45ac8c83..986268f51 100644 --- a/tests/generics/trtree.nim +++ b/tests/arc/trtree.nim @@ -138,16 +138,16 @@ proc search*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]): seq[LT] # a R*TREE proc proc chooseSubtree[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]; level: int): H[M, D, RT, LT] = assert level >= 0 - var n = t.root - while n.level > level: - let nn = Node[M, D, RT, LT](n) + var it = t.root + while it.level > level: + let nn = Node[M, D, RT, LT](it) var i0 = 0 # selected index var minLoss = type(b[0].a).high - if n.level == 1: # childreen are leaves -- determine the minimum overlap costs - for i in 0 ..< n.numEntries: + if it.level == 1: # childreen are leaves -- determine the minimum overlap costs + for i in 0 ..< it.numEntries: let nx = union(nn.a[i].b, b) var loss = 0 - for j in 0 ..< n.numEntries: + for j in 0 ..< it.numEntries: if i == j: continue loss += (overlap(nx, nn.a[j].b) - overlap(nn.a[i].b, nn.a[j].b)) # overlap (i, j) == (j, i), so maybe cache that? var rep = loss < minLoss @@ -163,7 +163,7 @@ proc chooseSubtree[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]; lev i0 = i minLoss = loss else: - for i in 0 ..< n.numEntries: + for i in 0 ..< it.numEntries: let loss = enlargement(nn.a[i].b, b) var rep = loss < minLoss if loss == minLoss: @@ -174,8 +174,8 @@ proc chooseSubtree[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]; lev if rep: i0 = i minLoss = loss - n = nn.a[i0].n - return n + it = nn.a[i0].n + return it proc pickSeeds[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; n: Node[M, D, RT, LT] | Leaf[M, D, RT, LT]; bx: Box[D, RT]): (int, int) = var i0, j0: int diff --git a/tests/destructor/tdestructor3.nim b/tests/destructor/tdestructor3.nim index b68aedce9..f967bbf95 100644 --- a/tests/destructor/tdestructor3.nim +++ b/tests/destructor/tdestructor3.nim @@ -1,5 +1,6 @@ discard """ - output: '''assign + output: ''' +assign destroy destroy 5 @@ -104,12 +105,12 @@ test() #------------------------------------------------------------ # Issue #12883 -type +type TopObject = object internal: UniquePtr[int] proc deleteTop(p: ptr TopObject) = - if p != nil: + if p != nil: `=destroy`(p[]) # !!! this operation used to leak the integer deallocshared(p) @@ -117,12 +118,12 @@ proc createTop(): ptr TopObject = result = cast[ptr TopObject](allocShared0(sizeof(TopObject))) result.internal = newUniquePtr(1) -proc test2() = +proc test2() = let x = createTop() echo $x.internal deleteTop(x) -echo "---------------" +echo "---------------" echo "app begin" test2() echo "app end" \ No newline at end of file diff --git a/tests/destructor/tmisc_destructors.nim b/tests/destructor/tmisc_destructors.nim index 73c54eab3..082cb0f78 100644 --- a/tests/destructor/tmisc_destructors.nim +++ b/tests/destructor/tmisc_destructors.nim @@ -21,11 +21,13 @@ proc `=sink`(dest: var Foo, src: Foo) = proc `=`(dest: var Foo, src: Foo) = assign_counter.inc +proc createFoo(): Foo = Foo(boo: 0) + proc test(): auto = - var a, b: Foo + var a, b = createFoo() return (a, b, Foo(boo: 5)) -var (a, b, _) = test() +var (ag, bg, _) = test() doAssert assign_counter == 0 doAssert sink_counter == 0 diff --git a/tests/destructor/tuse_result_prevents_sinks.nim b/tests/destructor/tuse_result_prevents_sinks.nim index 37b5af9b2..6eac5c902 100644 --- a/tests/destructor/tuse_result_prevents_sinks.nim +++ b/tests/destructor/tuse_result_prevents_sinks.nim @@ -17,15 +17,20 @@ proc `=sink`(self: var Foo; other: Foo) = proc `=destroy`(self: var Foo) = discard +template preventCursorInference(x) = + let p = unsafeAddr(x) + proc test(): Foo = result = Foo() let temp = result + preventCursorInference temp doAssert temp.i > 0 return result proc testB(): Foo = result = Foo() let temp = result + preventCursorInference temp doAssert temp.i > 0 discard test() |