diff options
Diffstat (limited to 'compiler/writetracking.nim')
| -rw-r--r-- | compiler/writetracking.nim | 288 |
1 files changed, 149 insertions, 139 deletions
diff --git a/compiler/writetracking.nim b/compiler/writetracking.nim index db3e6c53a..38258b07a 100644 --- a/compiler/writetracking.nim +++ b/compiler/writetracking.nim @@ -9,8 +9,13 @@ ## This module implements the write tracking analysis. Read my block post for ## a basic description of the algorithm and ideas. +## The algorithm operates in 2 phases: +## +## * Collecting information about assignments (and pass-by-var calls). +## * Computing an aliasing relation based on the assignments. This relation +## is then used to compute the 'writes' and 'escapes' effects. -import idents, ast, astalgo, trees, renderer, msgs, types +import intsets, idents, ast, astalgo, trees, renderer, msgs, types const debug = false @@ -24,11 +29,87 @@ type newNone, newLit, newCall + RootInfo = enum + rootIsResultOrParam, + rootIsHeapAccess, + rootIsSym, + markAsWrittenTo, + markAsEscaping + + Assignment = object # \ + # Note that the transitive closures MUST be computed in + # phase 2 of the algorithm. + dest, src: seq[ptr TSym] # we use 'ptr' here to save RC ops and GC cycles + destNoTc, srcNoTc: int # length of 'dest', 'src' without the + # transitive closure + destInfo: set[RootInfo] + info: TLineInfo + W = object # WriteTrackContext owner: PSym returnsNew: AssignToResult # assignments to 'result' - markAsWrittenTo, markAsEscaping: PNode - assignments: seq[(PNode, PNode)] # list of all assignments in this proc + assignments: seq[Assignment] # list of all assignments in this proc + +proc allRoots(n: PNode; result: var seq[ptr TSym]; info: var set[RootInfo]) = + case n.kind + of nkSym: + if n.sym.kind in {skParam, skVar, skTemp, skLet, skResult, skForVar}: + if n.sym.kind in {skResult, skParam}: incl(info, rootIsResultOrParam) + result.add(cast[ptr TSym](n.sym)) + of nkHiddenDeref, nkDerefExpr: + incl(info, rootIsHeapAccess) + allRoots(n.sons[0], result, info) + of nkDotExpr, nkBracketExpr, nkCheckedFieldExpr, + nkHiddenAddr, nkObjUpConv, nkObjDownConv: + allRoots(n.sons[0], result, info) + of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkConv, + nkStmtList, nkStmtListExpr, nkBlockStmt, nkBlockExpr, nkOfBranch, + nkElifBranch, nkElse, nkExceptBranch, nkFinally, nkCast: + allRoots(n.lastSon, result, info) + of nkCallKinds: + if getMagic(n) == mSlice: + allRoots(n.sons[1], result, info) + else: + # we do significantly better here by using the available escape + # information: + if n.sons[0].typ.isNil: return + var typ = n.sons[0].typ + if typ != nil: + typ = skipTypes(typ, abstractInst) + if typ.kind != tyProc: typ = nil + else: assert(sonsLen(typ) == sonsLen(typ.n)) + + for i in 1 ..< n.len: + let it = n.sons[i] + if typ != nil and i < sonsLen(typ): + assert(typ.n.sons[i].kind == nkSym) + let paramType = typ.n.sons[i] + if paramType.typ.isCompileTimeOnly: continue + if sfEscapes in paramType.sym.flags or paramType.typ.kind == tyVar: + allRoots(it, result, info) + else: + allRoots(it, result, info) + else: + for i in 0..<n.safeLen: + allRoots(n.sons[i], result, info) + +proc addAsgn(a: var Assignment; dest, src: PNode; destInfo: set[RootInfo]) = + a.dest = @[] + a.src = @[] + a.destInfo = destInfo + allRoots(dest, a.dest, a.destInfo) + if dest.kind == nkSym: incl(a.destInfo, rootIsSym) + if src != nil: + var dummy: set[RootInfo] + allRoots(src, a.src, dummy) + a.destNoTc = a.dest.len + a.srcNoTc = a.src.len + a.info = dest.info + #echo "ADDING ", dest.info, " ", a.destInfo + +proc srcHasSym(a: Assignment; x: ptr TSym): bool = + for i in 0 ..< a.srcNoTc: + if a.src[i] == x: return true proc returnsNewExpr*(n: PNode): NewLocation = case n.kind @@ -54,10 +135,10 @@ proc returnsNewExpr*(n: PNode): NewLocation = else: result = newNone -proc deps(w: var W; dest, src: PNode) = +proc deps(w: var W; dest, src: PNode; destInfo: set[RootInfo]) = # let x = (localA, localB) # compute 'returnsNew' property: - let retNew = returnsNewExpr(src) + let retNew = if src.isNil: newNone else: returnsNewExpr(src) if dest.kind == nkSym and dest.sym.kind == skResult: if retNew != newNone: if w.returnsNew != asgnOther: w.returnsNew = asgnNew @@ -66,7 +147,10 @@ proc deps(w: var W; dest, src: PNode) = # mark the dependency, but # rule out obviously innocent assignments like 'somebool = true' if dest.kind == nkSym and retNew == newLit: discard - else: w.assignments.add((dest, src)) + else: + let L = w.assignments.len + w.assignments.setLen(L+1) + addAsgn(w.assignments[L], dest, src, destInfo) proc depsArgs(w: var W; n: PNode) = if n.sons[0].typ.isNil: return @@ -80,11 +164,14 @@ proc depsArgs(w: var W; n: PNode) = assert(typ.n.sons[i].kind == nkSym) let paramType = typ.n.sons[i] if paramType.typ.isCompileTimeOnly: continue + var destInfo: set[RootInfo] = {} if sfWrittenTo in paramType.sym.flags or paramType.typ.kind == tyVar: # p(f(x, y), X, g(h, z)) - deps(w, it, w.markAsWrittenTo) + destInfo.incl markAsWrittenTo if sfEscapes in paramType.sym.flags: - deps(w, it, w.markAsEscaping) + destInfo.incl markAsEscaping + if destInfo != {}: + deps(w, it, nil, destInfo) proc deps(w: var W; n: PNode) = case n.kind @@ -95,168 +182,91 @@ proc deps(w: var W; n: PNode) = if child.kind == nkVarTuple and last.kind == nkPar: internalAssert child.len-2 == last.len for i in 0 .. child.len-3: - deps(w, child.sons[i], last.sons[i]) + deps(w, child.sons[i], last.sons[i], {}) else: for i in 0 .. child.len-3: - deps(w, child.sons[i], last) + deps(w, child.sons[i], last, {}) of nkAsgn, nkFastAsgn: - deps(w, n.sons[0], n.sons[1]) + deps(w, n.sons[0], n.sons[1], {}) else: for i in 0 ..< n.safeLen: deps(w, n.sons[i]) if n.kind in nkCallKinds: if getMagic(n) in {mNew, mNewFinalize, mNewSeq}: # may not look like an assignment, but it is: - deps(w, n.sons[1], newNodeIT(nkObjConstr, n.info, n.sons[1].typ)) + deps(w, n.sons[1], newNodeIT(nkObjConstr, n.info, n.sons[1].typ), {}) else: depsArgs(w, n) -type - RootInfo = enum - rootIsResultOrParam, - rootIsHeapAccess - -proc allRoots(n: PNode; result: var seq[PSym]; info: var set[RootInfo]) = - case n.kind - of nkSym: - if n.sym.kind in {skParam, skVar, skTemp, skLet, skResult, skForVar}: - if result.isNil: result = @[] - if n.sym notin result: - if n.sym.kind in {skResult, skParam}: incl(info, rootIsResultOrParam) - result.add n.sym - of nkHiddenDeref, nkDerefExpr: - incl(info, rootIsHeapAccess) - allRoots(n.sons[0], result, info) - of nkDotExpr, nkBracketExpr, nkCheckedFieldExpr, - nkHiddenAddr, nkObjUpConv, nkObjDownConv: - allRoots(n.sons[0], result, info) - of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkConv, - nkStmtList, nkStmtListExpr, nkBlockStmt, nkBlockExpr, nkOfBranch, - nkElifBranch, nkElse, nkExceptBranch, nkFinally, nkCast: - allRoots(n.lastSon, result, info) - of nkCallKinds: - if getMagic(n) == mSlice: - allRoots(n.sons[1], result, info) - else: - # we do significantly better here by using the available escape - # information: - if n.sons[0].typ.isNil: return - var typ = n.sons[0].typ - if typ != nil: - typ = skipTypes(typ, abstractInst) - if typ.kind != tyProc: typ = nil - else: assert(sonsLen(typ) == sonsLen(typ.n)) - - for i in 1 ..< n.len: - let it = n.sons[i] - if typ != nil and i < sonsLen(typ): - assert(typ.n.sons[i].kind == nkSym) - let paramType = typ.n.sons[i] - if paramType.typ.isCompileTimeOnly: continue - if sfEscapes in paramType.sym.flags or paramType.typ.kind == tyVar: - allRoots(it, result, info) - else: - allRoots(it, result, info) - else: - for i in 0..<n.safeLen: - allRoots(n.sons[i], result, info) - -proc allRoots(n: PNode; result: var seq[PSym]) = - var dummy: set[RootInfo] - allRoots(n, result, dummy) - -proc hasSym(n: PNode; x: PSym): bool = - when false: - if n.kind == nkSym: - result = n.sym == x - else: - for i in 0..safeLen(n)-1: - if hasSym(n.sons[i], x): return true - else: - var tmp: seq[PSym] - allRoots(n, tmp) - result = not tmp.isNil and x in tmp - -when debug: - proc `$`*(x: PSym): string = x.name.s - -proc possibleAliases(w: W; result: var seq[PSym]) = - var todo = 0 +proc possibleAliases(w: var W; result: var seq[ptr TSym]) = # this is an expensive fixpoint iteration. We could speed up this analysis # by a smarter data-structure but we wait until prolifing shows us it's # expensive. Usually 'w.assignments' is small enough. + var alreadySeen = initIntSet() + template addNoDup(x) = + if not alreadySeen.containsOrIncl(x.id): result.add x + for x in result: alreadySeen.incl x.id + + var todo = 0 while todo < result.len: let x = result[todo] inc todo - when debug: - if w.owner.name.s == "m3": echo "select ", x, " ", todo, " ", result.len - for dest, src in items(w.assignments): - if src.hasSym(x): - # dest = f(..., s, ...) - allRoots(dest, result) - when debug: - if w.owner.name.s == "m3": echo "A ", result - elif dest.kind == nkSym and dest.sym == x: - # s = f(..., x, ....) - allRoots(src, result) - when debug: - if w.owner.name.s == "m3": echo "B ", result - else: - when debug: - if w.owner.name.s == "m3": echo "C ", x, " ", todo, " ", result.len + for a in mitems(w.assignments): + #if a.srcHasSym(x): + # # y = f(..., x, ...) + # for i in 0 ..< a.destNoTc: addNoDup a.dest[i] + if a.destNoTc > 0 and a.dest[0] == x and rootIsSym in a.destInfo: + # x = f(..., y, ....) + for i in 0 ..< a.srcNoTc: addNoDup a.src[i] -proc markDirty(w: W) = - for dest, src in items(w.assignments): - var r: seq[PSym] = nil - var info: set[RootInfo] - allRoots(dest, r, info) - when debug: - if w.owner.info ?? "temp18": - echo "ASGN ", dest, " = ", src, " |", heapAccess, " ", r.name.s - if rootIsHeapAccess in info or src == w.markAsWrittenTo: - # we have an assignment like: - # local.foo = bar - # --> check which parameter it may alias and mark these parameters - # as dirty: - possibleAliases(w, r) - for a in r: - if a.kind == skParam and a.owner == w.owner: - incl(a.flags, sfWrittenTo) +proc markWriteOrEscape(w: var W) = + ## Both 'writes' and 'escapes' effects ultimately only care + ## about *parameters*. + ## However, due to aliasing, even locals that might not look as parameters + ## have to count as parameters if they can alias a parameter: + ## + ## .. code-block:: nim + ## proc modifies(n: Node) {.writes: [n].} = + ## let x = n + ## x.data = "abc" + ## + ## We call a symbol *parameter-like* if it is a parameter or can alias a + ## parameter. + ## Let ``p``, ``q`` be *parameter-like* and ``x``, ``y`` be general + ## expressions. + ## + ## A write then looks like ``p[] = x``. + ## An escape looks like ``p[] = q`` or more generally + ## like ``p[] = f(q)`` where ``f`` can forward ``q``. + for a in mitems(w.assignments): + if a.destInfo != {}: + possibleAliases(w, a.dest) -proc markEscaping(w: W) = - # let p1 = p - # let p2 = q - # p2.x = call(..., p1, ...) - for dest, src in items(w.assignments): - var r: seq[PSym] = nil - var info: set[RootInfo] - allRoots(dest, r, info) + if {rootIsHeapAccess, markAsWrittenTo} * a.destInfo != {}: + for p in a.dest: + if p.kind == skParam and p.owner == w.owner: + incl(p.flags, sfWrittenTo) - if (r.len > 0) and (info != {} or src == w.markAsEscaping): - possibleAliases(w, r) + if {rootIsResultOrParam, rootIsHeapAccess, markAsEscaping}*a.destInfo != {}: var destIsParam = false - for a in r: - if a.kind in {skResult, skParam} and a.owner == w.owner: + for p in a.dest: + if p.kind in {skResult, skParam} and p.owner == w.owner: destIsParam = true break if destIsParam: - var victims: seq[PSym] = @[] - allRoots(src, victims) - possibleAliases(w, victims) - for v in victims: - if v.kind == skParam and v.owner == w.owner: - incl(v.flags, sfEscapes) + possibleAliases(w, a.src) + for p in a.src: + if p.kind == skParam and p.owner == w.owner: + incl(p.flags, sfEscapes) proc trackWrites*(owner: PSym; body: PNode) = var w: W w.owner = owner - w.markAsWrittenTo = newNodeI(nkArgList, body.info) - w.markAsEscaping = newNodeI(nkArgList, body.info) w.assignments = @[] + # Phase 1: Collect and preprocess any assignments in the proc body: deps(w, body) - markDirty(w) - markEscaping(w) + # Phase 2: Compute the 'writes' and 'escapes' effects: + markWriteOrEscape(w) if w.returnsNew != asgnOther and not isEmptyType(owner.typ.sons[0]) and containsGarbageCollectedRef(owner.typ.sons[0]): incl(owner.typ.flags, tfReturnsNew) - |