From 045e026d0ee4e6decc4f22f1f9cbb0bdd8bc3b45 Mon Sep 17 00:00:00 2001 From: Araq Date: Mon, 15 Apr 2019 17:57:59 +0200 Subject: dfa.nim: track object/tuple field accesses more precisely; sink(o.x); sink(o.y) needs to compile; activate the tuple unpacking transf.nim bugfix --- compiler/dfa.nim | 73 +++++++++++++++++++++++++-------- compiler/injectdestructors.nim | 60 ++++++++++++++++----------- compiler/patterns.nim | 2 +- compiler/renderer.nim | 2 +- compiler/transf.nim | 4 +- tests/destructor/t6434.nim | 4 +- tests/destructor/tmatrix.nim | 4 +- tests/destructor/tobjfield_analysis.nim | 35 ++++++++++++++++ 8 files changed, 136 insertions(+), 48 deletions(-) create mode 100644 tests/destructor/tobjfield_analysis.nim diff --git a/compiler/dfa.nim b/compiler/dfa.nim index 2b5cd350a..cdb912163 100644 --- a/compiler/dfa.nim +++ b/compiler/dfa.nim @@ -29,7 +29,10 @@ ## "A Graph–Free Approach to Data–Flow Analysis" by Markus Mohnen. ## https://link.springer.com/content/pdf/10.1007/3-540-45937-5_6.pdf -import ast, astalgo, types, intsets, tables, msgs, options, lineinfos +import ast, astalgo, types, intsets, tables, msgs, options, lineinfos, renderer + +from patterns import sameTrees +from aliases import isPartOf, TAnalysisResult type InstrKind* = enum @@ -37,7 +40,10 @@ type Instr* = object n*: PNode case kind*: InstrKind - of def, use: sym*: PSym + of def, use: sym*: PSym # 'sym' can also be 'nil' and + # then 'n' contains the def/use location. + # This is used so that we can track object + # and tuple field accesses precisely. of goto, fork, join: dest*: int ControlFlowGraph* = seq[Instr] @@ -47,9 +53,6 @@ type label: PSym fixups: seq[TPosition] - ValueKind = enum - undef, value, valueOrUndef - Con = object code: ControlFlowGraph inCall, inTryStmt: int @@ -77,7 +80,7 @@ proc codeListing(c: ControlFlowGraph, result: var string, start=0; last = -1) = result.add "\t" case c[i].kind of def, use: - result.add c[i].sym.name.s + result.add renderTree(c[i].n) of goto, fork, join: result.add "L" result.add c[i].dest+i @@ -564,16 +567,50 @@ proc genReturn(c: var Con; n: PNode) = genNoReturn(c, n) const - InterestingSyms = {skVar, skResult, skLet, skParam, skForVar} - -proc genUse(c: var Con; n: PNode) = - var n = n - while n.kind in {nkDotExpr, nkCheckedFieldExpr, - nkBracketExpr, nkDerefExpr, nkHiddenDeref, - nkAddr, nkHiddenAddr}: + InterestingSyms = {skVar, skResult, skLet, skParam, skForVar, skTemp} + PathKinds* = {nkDotExpr, nkCheckedFieldExpr, + nkBracketExpr, nkDerefExpr, nkHiddenDeref, + nkAddr, nkHiddenAddr} + +proc genUse(c: var Con; orig: PNode) = + var n = orig + var iters = 0 + while n.kind in PathKinds: n = n[0] + inc iters if n.kind == nkSym and n.sym.kind in InterestingSyms: - c.code.add Instr(n: n, kind: use, sym: n.sym) + c.code.add Instr(n: orig, kind: use, sym: if iters > 0: nil else: n.sym) + +proc instrTargets*(ins: Instr; loc: PNode): bool = + assert ins.kind in {def, use} + if ins.sym != nil and loc.kind == nkSym: + result = ins.sym == loc.sym + else: + result = ins.n == loc or sameTrees(ins.n, loc) + if not result: + # We can come here if loc is 'x.f' and ins.n is 'x' or the other way round. + # def x.f; question: does it affect the full 'x'? No. + # def x; question: does it affect the 'x.f'? Yes. + # use x.f; question: does it affect the full 'x'? No. + # use x; question does it affect 'x.f'? Yes. + result = isPartOf(ins.n, loc) == arYes + +proc isAnalysableFieldAccess*(n: PNode; owner: PSym): bool = + var n = n + while true: + if n.kind in {nkDotExpr, nkCheckedFieldExpr, nkHiddenSubConv, nkHiddenStdConv, nkObjDownConv, nkObjUpConv}: + n = n[0] + elif n.kind == nkBracketExpr: + let x = n[0] + if x.typ != nil and x.typ.skipTypes(abstractInst).kind == tyTuple: + n = x + else: + break + else: + break + # XXX Allow closure deref operations here if we know + # the owner controlled the closure allocation? + result = n.kind == nkSym and n.sym.owner == owner and owner.kind != skModule proc genDef(c: var Con; n: PNode) = if n.kind == nkSym and n.sym.kind in InterestingSyms: @@ -651,10 +688,12 @@ proc gen(c: var Con; n: PNode) = of nkCharLit..nkNilLit: discard of nkAsgn, nkFastAsgn: gen(c, n[1]) + # watch out: 'obj[i].f2 = value' sets 'f2' but + # "uses" 'i'. But we are only talking about builtin array indexing so + # it doesn't matter and 'x = 34' is NOT a usage of 'x'. genDef(c, n[0]) - of nkDotExpr, nkCheckedFieldExpr, nkBracketExpr, - nkDerefExpr, nkHiddenDeref, nkAddr, nkHiddenAddr: - gen(c, n[0]) + of PathKinds: + genUse(c, n) of nkIfStmt, nkIfExpr: genIf(c, n) of nkWhenStmt: # This is "when nimvm" node. Chose the first branch. diff --git a/compiler/injectdestructors.nim b/compiler/injectdestructors.nim index db4053fb3..033d5f3f9 100644 --- a/compiler/injectdestructors.nim +++ b/compiler/injectdestructors.nim @@ -139,7 +139,7 @@ import lineinfos, parampatterns const - InterestingSyms = {skVar, skResult, skLet, skForVar} + InterestingSyms = {skVar, skResult, skLet, skForVar, skTemp} type Con = object @@ -153,17 +153,24 @@ type uninit: IntSet # set of uninit'ed vars uninitComputed: bool -proc isLastRead(s: PSym; c: var Con; pc, comesFrom: int): int = +const toDebug = "" + +template dbg(body) = + when toDebug.len > 0: + if c.owner.name.s == toDebug or toDebug == "always": + body + +proc isLastRead(location: PNode; c: var Con; pc, comesFrom: int): int = var pc = pc while pc < c.g.len: case c.g[pc].kind of def: - if c.g[pc].sym == s: + if instrTargets(c.g[pc], location): # the path lead to a redefinition of 's' --> abandon it. return high(int) inc pc of use: - if c.g[pc].sym == s: + if instrTargets(c.g[pc], location): c.otherRead = c.g[pc].n return -1 inc pc @@ -171,9 +178,9 @@ proc isLastRead(s: PSym; c: var Con; pc, comesFrom: int): int = pc = pc + c.g[pc].dest of fork: # every branch must lead to the last read of the location: - var variantA = isLastRead(s, c, pc+1, pc) + var variantA = isLastRead(location, c, pc+1, pc) if variantA < 0: return -1 - let variantB = isLastRead(s, c, pc + c.g[pc].dest, pc) + let variantB = isLastRead(location, c, pc + c.g[pc].dest, pc) if variantB < 0: return -1 elif variantA == high(int): variantA = variantB @@ -186,11 +193,11 @@ proc isLastRead(s: PSym; c: var Con; pc, comesFrom: int): int = proc isLastRead(n: PNode; c: var Con): bool = # first we need to search for the instruction that belongs to 'n': - doAssert n.kind == nkSym c.otherRead = nil var instr = -1 for i in 0..= c.g.len: return true + dbg: + echo "beginning here ", instr + when true: - result = isLastRead(n.sym, c, instr+1, -1) >= 0 + result = isLastRead(n, c, instr+1, -1) >= 0 else: let s = n.sym var pcs: seq[int] = @[instr+1] @@ -507,6 +517,8 @@ proc pArg(arg: PNode; c: var Con; isSink: bool): PNode = branch = copyNode(arg[i]) branch.add pArgIfTyped(arg[i][0]) result.add branch + elif isAnalysableFieldAccess(arg, c.owner) and isLastRead(arg, c): + result = destructiveMoveVar(arg, c) else: # an object that is not temporary but passed to a 'sink' parameter # results in a copy. @@ -647,9 +659,15 @@ proc moveOrCopy(dest, ri: PNode; c: var Con): PNode = result = genCopy(c, dest.typ, dest, ri) result.add p(ri, c) else: - # XXX At least string literals can be moved? - result = genCopy(c, dest.typ, dest, ri) - result.add p(ri, c) + if isAnalysableFieldAccess(ri, c.owner) and isLastRead(ri, c): + # Rule 3: `=sink`(x, z); wasMoved(z) + var snk = genSink(c, dest.typ, dest, ri) + snk.add ri + result = newTree(nkStmtList, snk, genWasMoved(ri, c)) + else: + # XXX At least string literals can be moved? + result = genCopy(c, dest.typ, dest, ri) + result.add p(ri, c) proc computeUninit(c: var Con) = if not c.uninitComputed: @@ -785,10 +803,6 @@ proc p(n: PNode; c: var Con): PNode = recurse(n, result) proc injectDestructorCalls*(g: ModuleGraph; owner: PSym; n: PNode): PNode = - const toDebug = "" - when toDebug.len > 0: - if owner.name.s == toDebug or toDebug == "always": - echo "injecting into ", n if sfGeneratedOp in owner.flags or isInlineIterator(owner): return n var c: Con c.owner = owner @@ -802,8 +816,9 @@ proc injectDestructorCalls*(g: ModuleGraph; owner: PSym; n: PNode): PNode = for i in 0.. 0: - if owner.name.s == toDebug or toDebug == "always": - echo "------------------------------------" - echo owner.name.s, " transformed to: " - echo result + dbg: + echo "------------------------------------" + echo owner.name.s, " transformed to: " + echo result diff --git a/compiler/patterns.nim b/compiler/patterns.nim index ebb3a7c1d..1118c8bb5 100644 --- a/compiler/patterns.nim +++ b/compiler/patterns.nim @@ -48,7 +48,7 @@ proc canonKind(n: PNode): TNodeKind = proc sameKinds(a, b: PNode): bool {.inline.} = result = a.kind == b.kind or a.canonKind == b.canonKind -proc sameTrees(a, b: PNode): bool = +proc sameTrees*(a, b: PNode): bool = if sameKinds(a, b): case a.kind of nkSym: result = a.sym == b.sym diff --git a/compiler/renderer.nim b/compiler/renderer.nim index 5d65cf6d3..297a0712c 100644 --- a/compiler/renderer.nim +++ b/compiler/renderer.nim @@ -843,7 +843,7 @@ proc gident(g: var TSrcGen, n: PNode) = else: t = tkOpr put(g, t, s, if n.kind == nkSym and renderSyms in g.flags: n.sym else: nil) - if n.kind == nkSym and (renderIds in g.flags or sfGenSym in n.sym.flags): + if n.kind == nkSym and (renderIds in g.flags or sfGenSym in n.sym.flags or n.sym.kind == skTemp): when defined(debugMagics): put(g, tkIntLit, $n.sym.id & $n.sym.magic) else: diff --git a/compiler/transf.nim b/compiler/transf.nim index febe65d73..c455e3319 100644 --- a/compiler/transf.nim +++ b/compiler/transf.nim @@ -1009,8 +1009,8 @@ proc transform(c: PTransf, n: PNode): PTransNode = result = transformYield(c, n) else: result = transformSons(c, n) - #of nkAsgn: - # result = transformAsgn(c, n) + of nkAsgn: + result = transformAsgn(c, n) of nkIdentDefs, nkConstDef: result = PTransNode(n) result[0] = transform(c, n[0]) diff --git a/tests/destructor/t6434.nim b/tests/destructor/t6434.nim index 5f5fbedfa..4e78d0469 100644 --- a/tests/destructor/t6434.nim +++ b/tests/destructor/t6434.nim @@ -23,5 +23,5 @@ proc test(): auto = var (a, b, _) = test() -doAssert: assign_counter == 0 -doAssert: sink_counter == 9 \ No newline at end of file +doAssert assign_counter == 0 +doAssert sink_counter == 12 # + 3 because of the conservative tuple unpacking transformation diff --git a/tests/destructor/tmatrix.nim b/tests/destructor/tmatrix.nim index b89b41a4c..a3bd59df3 100644 --- a/tests/destructor/tmatrix.nim +++ b/tests/destructor/tmatrix.nim @@ -88,8 +88,8 @@ proc `-`*(a: sink Matrix; b: Matrix): Matrix = doAssert(a.len == b.len) # non destructive use before sink is ok result = a for i in 0 ..< result.m: - for j in 0 ..< result.n: - result[i, j] = a[i, j] - b[i, j] + for j in 0 ..< result.n: + result[i, j] = a[i, j] - b[i, j] proc info = echo "after ", allocCount, " ", deallocCount diff --git a/tests/destructor/tobjfield_analysis.nim b/tests/destructor/tobjfield_analysis.nim new file mode 100644 index 000000000..24cf02aee --- /dev/null +++ b/tests/destructor/tobjfield_analysis.nim @@ -0,0 +1,35 @@ +discard """ + output: '''works''' +""" + +type + MyVal = object + f: ptr float + +proc `=destroy`(x: var MyVal) = + if x.f != nil: + dealloc(x.f) + +proc `=sink`(x1: var MyVal, x2: Myval) = + if x1.f != x2.f: + `=destroy`(x1) + x1.f = x2.f + +proc `=`(x1: var MyVal, x2: Myval) {.error.} + +proc newVal(x: float): MyVal = + result.f = create(float) + result.f[] = x + +proc sinkMe(x: sink MyVal) = + discard + +proc main = + var y = (newVal(3.0), newVal(4.0)) + + sinkMe y[0] + sinkMe y[1] + echo "works" + +main() + -- cgit 1.4.1-2-gfad0