diff options
Diffstat (limited to 'compiler/varpartitions.nim')
| -rw-r--r-- | compiler/varpartitions.nim | 283 |
1 files changed, 189 insertions, 94 deletions
diff --git a/compiler/varpartitions.nim b/compiler/varpartitions.nim index 7bb626c0a..1711fea46 100644 --- a/compiler/varpartitions.nim +++ b/compiler/varpartitions.nim @@ -32,6 +32,9 @@ import ast, types, lineinfos, options, msgs, renderer, typeallowed, modulegraphs from trees import getMagic, isNoSideEffectPragma, stupidStmtListExpr from isolation_check import canAlias +when defined(nimPreviewSlimSystem): + import std/assertions + type AbstractTime = distinct int @@ -51,6 +54,7 @@ type SubgraphFlag = enum isMutated, # graph might be mutated isMutatedDirectly, # graph is mutated directly by a non-var parameter. + isMutatedByVarParam, # graph is mutated by a var parameter. connectsConstParam # graph is connected to a non-var parameter. VarFlag = enum @@ -94,12 +98,15 @@ type Partitions* = object abstractTime: AbstractTime + defers: seq[PNode] + processDefer: bool s: seq[VarIndex] graphs: seq[MutationInfo] goals: set[Goal] unanalysableMutation: bool inAsgnSource, inConstructor, inNoSideEffectSection: int inConditional, inLoop: int + inConvHasDestructor: int owner: PSym g: ModuleGraph @@ -175,12 +182,18 @@ proc root(v: var Partitions; start: int): int = v.s[it].con = Connection(kind: dependsOn, parent: result) it = next -proc potentialMutation(v: var Partitions; s: PSym; info: TLineInfo) = +proc potentialMutation(v: var Partitions; s: PSym; level: int; info: TLineInfo) = let id = variableId(v, s) if id >= 0: let r = root(v, id) - let flags = if s.kind == skParam and isConstParam(s): - {isMutated, isMutatedDirectly} + let flags = if s.kind == skParam: + if isConstParam(s): + {isMutated, isMutatedDirectly} + elif s.typ.kind == tyVar and level <= 1: + # varParam[i] = v is different from varParam[i][] = v + {isMutatedByVarParam} + else: + {isMutated} else: {isMutated} @@ -276,7 +289,9 @@ proc borrowFromConstExpr(n: PNode): bool = result = true for i in 1..<n.len: if not borrowFromConstExpr(n[i]): return false - else: discard + else: + result = false + else: result = false proc pathExpr(node: PNode; owner: PSym): PNode = #[ From the spec: @@ -339,36 +354,44 @@ proc pathExpr(node: PNode; owner: PSym): PNode = if result == nil and borrowFromConstExpr(n): result = n -proc allRoots(n: PNode; result: var seq[PSym]; followDotExpr = true) = +const + RootEscapes = 1000 # in 'p(r)' we don't know what p does to our poor root. + # so we assume a high level of indirections + +proc allRoots(n: PNode; result: var seq[(PSym, int)]; level: int) = case n.kind of nkSym: if n.sym.kind in {skParam, skVar, skTemp, skLet, skResult, skForVar}: - result.add(n.sym) + result.add((n.sym, level)) - of nkDotExpr, nkDerefExpr, nkBracketExpr, nkHiddenDeref, - nkCheckedFieldExpr, nkAddr, nkHiddenAddr: - if followDotExpr: - allRoots(n[0], result, followDotExpr) + of nkDerefExpr, nkHiddenDeref: + allRoots(n[0], result, level+1) + of nkBracketExpr, nkDotExpr, nkCheckedFieldExpr, nkAddr, nkHiddenAddr: + allRoots(n[0], result, level) of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkConv, nkStmtList, nkStmtListExpr, nkBlockStmt, nkBlockExpr, nkCast, nkObjUpConv, nkObjDownConv: if n.len > 0: - allRoots(n.lastSon, result, followDotExpr) + allRoots(n.lastSon, result, level) of nkCaseStmt, nkObjConstr: for i in 1..<n.len: - allRoots(n[i].lastSon, result, followDotExpr) + allRoots(n[i].lastSon, result, level) of nkIfStmt, nkIfExpr: for i in 0..<n.len: - allRoots(n[i].lastSon, result, followDotExpr) + allRoots(n[i].lastSon, result, level) of nkBracket, nkTupleConstr, nkPar: for i in 0..<n.len: - allRoots(n[i], result, followDotExpr) + allRoots(n[i], result, level-1) of nkCallKinds: if n.typ != nil and n.typ.kind in {tyVar, tyLent}: if n.len > 1: - allRoots(n[1], result, followDotExpr) + # XXX We really need the unwritten RFC here and distinguish between + # proc `[]`(x: var Container): var T # resizes the container + # and + # proc `[]`(x: Container): var T # only allows for slot mutation + allRoots(n[1], result, RootEscapes) else: let m = getMagic(n) case m @@ -378,21 +401,20 @@ proc allRoots(n: PNode; result: var seq[PSym]; followDotExpr = true) = if typ != nil: typ = skipTypes(typ, abstractInst) if typ.kind != tyProc: typ = nil - else: assert(typ.len == typ.n.len) for i in 1 ..< n.len: let it = n[i] - if typ != nil and i < typ.len: + if typ != nil and i < typ.n.len: assert(typ.n[i].kind == nkSym) let paramType = typ.n[i].typ - if not paramType.isCompileTimeOnly and not typ.sons[0].isEmptyType and - canAlias(paramType, typ.sons[0]): - allRoots(it, result, followDotExpr) + if not paramType.isCompileTimeOnly and not typ.returnType.isEmptyType and + canAlias(paramType, typ.returnType): + allRoots(it, result, RootEscapes) else: - allRoots(it, result, followDotExpr) + allRoots(it, result, RootEscapes) of mSlice: - allRoots(n[1], result, followDotExpr) + allRoots(n[1], result, level+1) else: discard "harmless operation" else: @@ -401,22 +423,33 @@ proc allRoots(n: PNode; result: var seq[PSym]; followDotExpr = true) = proc destMightOwn(c: var Partitions; dest: var VarIndex; n: PNode) = ## Analyse if 'n' is an expression that owns the data, if so mark 'dest' ## with 'ownsData'. - if n.typ == nil: return case n.kind of nkEmpty, nkCharLit..nkNilLit: # primitive literals including the empty are harmless: discard - of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkCast, nkConv: + of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkCast: destMightOwn(c, dest, n[1]) + of nkConv: + if hasDestructor(n.typ): + inc c.inConvHasDestructor + destMightOwn(c, dest, n[1]) + dec c.inConvHasDestructor + else: + destMightOwn(c, dest, n[1]) + of nkIfStmt, nkIfExpr: for i in 0..<n.len: + inc c.inConditional destMightOwn(c, dest, n[i].lastSon) + dec c.inConditional of nkCaseStmt: for i in 1..<n.len: + inc c.inConditional destMightOwn(c, dest, n[i].lastSon) + dec c.inConditional of nkStmtList, nkStmtListExpr: if n.len > 0: @@ -460,30 +493,42 @@ proc destMightOwn(c: var Partitions; dest: var VarIndex; n: PNode) = destMightOwn(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: - dest.flags.incl ownsData - elif n.typ.kind in {tyLent, tyVar}: - # we know the result is derived from the first argument: - var roots: seq[PSym] - allRoots(n[1], roots) - for r in roots: - connect(c, dest.sym, r, n[1].info) + if n.typ != nil: + if hasDestructor(n.typ) or c.inConvHasDestructor > 0: + # calls do construct, what we construct must be destroyed, + # so dest cannot be a cursor: + dest.flags.incl ownsData + elif n.typ.kind in {tyLent, tyVar} and n.len > 1: + # we know the result is derived from the first argument: + var roots: seq[(PSym, int)] = @[] + allRoots(n[1], roots, RootEscapes) + if roots.len == 0 and c.inConditional > 0: + # when in a conditional expression, + # to ensure that the first argument isn't outlived + # by the lvalue, we need find the root, otherwise + # it is probably a local temporary + # (e.g. a return value from a call), + # we should prevent cursorfication + dest.flags.incl preventCursor + else: + for r in roots: + connect(c, dest.sym, r[0], n[1].info) - 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})): - destMightOwn(c, dest, n[i]) + 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, mOpenArrayToSeq}: + 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})): + destMightOwn(c, dest, n[i]) else: # something we cannot handle: @@ -505,13 +550,17 @@ const proc isConstSym(s: PSym): bool = result = s.kind in {skConst, skLet} or isConstParam(s) +proc toString(n: PNode): string = + if n.kind == nkEmpty: result = "<empty>" + else: result = $n + proc borrowFrom(c: var Partitions; dest: PSym; src: PNode) = const url = "see https://nim-lang.github.io/Nim/manual_experimental.html#view-types-algorithm-path-expressions for details" let s = pathExpr(src, c.owner) if s == nil: - localError(c.g.config, src.info, "cannot borrow from " & $src & ", it is not a path expression; " & url) + localError(c.g.config, src.info, "cannot borrow from " & src.toString & ", it is not a path expression; " & url) elif s.kind == nkSym: if dest.kind == skResult: if s.sym.kind != skParam or s.sym.position != 0: @@ -556,23 +605,33 @@ proc borrowingAsgn(c: var Partitions; dest, src: PNode) = if dest.kind == nkSym: if directViewType(dest.typ) != noView: borrowFrom(c, dest.sym, src) - elif dest.kind in {nkHiddenDeref, nkDerefExpr, nkBracketExpr}: - case directViewType(dest[0].typ) - of mutableView: - # we do not borrow, but we use the view to mutate the borrowed - # location: - let viewOrigin = pathExpr(dest, c.owner) - if viewOrigin.kind == nkSym: - let vid = variableId(c, viewOrigin.sym) + else: + let viewOrigin = pathExpr(dest, c.owner) + if viewOrigin != nil and viewOrigin.kind == nkSym: + let viewSym = viewOrigin.sym + let directView = directViewType(dest[0].typ) # check something like result[first] = toOpenArray(s, first, last-1) + # so we don't need to iterate the original type + let originSymbolView = directViewType(viewSym.typ) # find the original symbol which preserves the view type + # var foo: var Object = a + # foo.id = 777 # the type of foo is no view, so we need + # to check the original symbol + let viewSets = {directView, originSymbolView} + + if viewSets * {mutableView, immutableView} != {}: + # we do not borrow, but we use the view to mutate the borrowed + # location: + let vid = variableId(c, viewSym) if vid >= 0: c.s[vid].flags.incl viewDoesMutate - of immutableView: - if dest.kind == nkBracketExpr and dest[0].kind == nkHiddenDeref and - mutableParameter(dest[0][0]): - discard "remains a mutable location anyhow" + #[of immutableView: + if dest.kind == nkBracketExpr and dest[0].kind == nkHiddenDeref and + mutableParameter(dest[0][0]): + discard "remains a mutable location anyhow" + else: + localError(c.g.config, dest.info, "attempt to mutate a borrowed location from an immutable view") + ]# else: - localError(c.g.config, dest.info, "attempt to mutate a borrowed location from an immutable view") - of noView: discard "nothing to do" + discard "nothing to do" proc containsPointer(t: PType): bool = proc wrap(t: PType): bool {.nimcall.} = t.kind in {tyRef, tyPtr} @@ -582,19 +641,20 @@ proc deps(c: var Partitions; dest, src: PNode) = if borrowChecking in c.goals: borrowingAsgn(c, dest, src) - var targets, sources: seq[PSym] - allRoots(dest, targets) - allRoots(src, sources) + var targets: seq[(PSym, int)] = @[] + var sources: seq[(PSym, int)] = @[] + allRoots(dest, targets, 0) + allRoots(src, sources, 0) let destIsComplex = containsPointer(dest.typ) for t in targets: if dest.kind != nkSym and c.inNoSideEffectSection == 0: - potentialMutation(c, t, dest.info) + potentialMutation(c, t[0], t[1], dest.info) if destIsComplex: for s in sources: - connect(c, t, s, dest.info) + connect(c, t[0], s[0], dest.info) if cursorInference in c.goals and src.kind != nkEmpty: let d = pathExpr(dest, c.owner) @@ -602,7 +662,8 @@ proc deps(c: var Partitions; dest, src: PNode) = let vid = variableId(c, d.sym) if vid >= 0: destMightOwn(c, c.s[vid], src) - for s in sources: + for source in sources: + let s = source[0] if s == d.sym: discard "assignments like: it = it.next are fine" elif {sfGlobal, sfThread} * s.flags != {} or hasDisabledAsgn(c.g, s.typ): @@ -626,21 +687,14 @@ proc deps(c: var Partitions; dest, src: PNode) = when explainCursors: echo "D not a cursor ", d.sym, " reassignedTo ", c.s[srcid].reassignedTo c.s[vid].flags.incl preventCursor -const - nodesToIgnoreSet = {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, nkMixinStmt, nkBindStmt} proc potentialMutationViaArg(c: var Partitions; n: PNode; callee: PType) = if constParameters in c.goals and tfNoSideEffect in callee.flags: discard "we know there are no hidden mutations through an immutable parameter" elif c.inNoSideEffectSection == 0 and containsPointer(n.typ): - var roots: seq[PSym] - allRoots(n, roots) - for r in roots: potentialMutation(c, r, n.info) + var roots: seq[(PSym, int)] = @[] + allRoots(n, roots, RootEscapes) + for r in roots: potentialMutation(c, r[0], r[1], n.info) proc traverse(c: var Partitions; n: PNode) = inc c.abstractTime @@ -658,7 +712,7 @@ proc traverse(c: var Partitions; n: PNode) = for i in 0..<child.len-2: #registerVariable(c, child[i]) deps(c, child[i], last) - of nkAsgn, nkFastAsgn: + of nkAsgn, nkFastAsgn, nkSinkAsgn: traverse(c, n[0]) inc c.inAsgnSource traverse(c, n[1]) @@ -674,20 +728,24 @@ proc traverse(c: var Partitions; n: PNode) = for child in n: traverse(c, child) let parameters = n[0].typ - let L = if parameters != nil: parameters.len else: 0 + let L = if parameters != nil: parameters.signatureLen else: 0 let m = getMagic(n) + if m == mEnsureMove and n[1].kind == nkSym: + # we know that it must be moved so it cannot be a cursor + noCursor(c, n[1].sym) + for i in 1..<n.len: let it = n[i] if i < L: let paramType = parameters[i].skipTypes({tyGenericInst, tyAlias}) if not paramType.isCompileTimeOnly and paramType.kind in {tyVar, tySink, tyOwned}: - var roots: seq[PSym] - allRoots(it, roots) + var roots: seq[(PSym, int)] = @[] + allRoots(it, roots, RootEscapes) if paramType.kind == tyVar: if c.inNoSideEffectSection == 0: - for r in roots: potentialMutation(c, r, it.info) - for r in roots: noCursor(c, r) + for r in roots: potentialMutation(c, r[0], r[1], it.info) + for r in roots: noCursor(c, r[0]) if borrowChecking in c.goals: # a call like 'result.add toOpenArray()' can also be a borrow @@ -695,7 +753,7 @@ proc traverse(c: var Partitions; n: PNode) = # 'paramType[0]' is still a view type, this is not a typo! if directViewType(paramType[0]) == noView and classifyViewType(paramType[0]) != noView: borrowingCall(c, paramType[0], n, i) - elif borrowChecking in c.goals and m == mNone: + elif m == mNone: potentialMutationViaArg(c, n[i], parameters) of nkAddr, nkHiddenAddr: @@ -703,10 +761,10 @@ proc traverse(c: var Partitions; n: PNode) = when false: # XXX investigate if this is required, it doesn't look # like it is! - var roots: seq[PSym] - allRoots(n[0], roots) + var roots: seq[(PSym, int)] + allRoots(n[0], roots, RootEscapes) for r in roots: - potentialMutation(c, r, it.info) + potentialMutation(c, r[0], r[1], it.info) of nkTupleConstr, nkBracket: for child in n: traverse(c, child) @@ -748,6 +806,14 @@ proc traverse(c: var Partitions; n: PNode) = # mutate(graph) # connect(graph, cursorVar) for child in n: traverse(c, child) + + if n.kind == nkWhileStmt: + traverse(c, n[0]) + # variables in while condition has longer alive time than local variables + # in the while loop body + of nkDefer: + if c.processDefer: + for child in n: traverse(c, child) else: for child in n: traverse(c, child) @@ -778,7 +844,11 @@ proc computeLiveRanges(c: var Partitions; n: PNode) = registerVariable(c, child[i]) #deps(c, child[i], last) - of nkAsgn, nkFastAsgn: + if c.inLoop > 0 and child[0].kind == nkSym: # bug #22787 + let vid = variableId(c, child[0].sym) + if child[^1].kind != nkEmpty: + markAsReassigned(c, vid) + of nkAsgn, nkFastAsgn, nkSinkAsgn: computeLiveRanges(c, n[0]) computeLiveRanges(c, n[1]) if n[0].kind == nkSym: @@ -786,6 +856,10 @@ proc computeLiveRanges(c: var Partitions; n: PNode) = if vid >= 0: if n[1].kind == nkSym and (c.s[vid].reassignedTo == 0 or c.s[vid].reassignedTo == n[1].sym.id): c.s[vid].reassignedTo = n[1].sym.id + if c.inConditional > 0 and c.inLoop > 0: + # bug #22200: live ranges with loops and conditionals are too + # complex for our current analysis, so we prevent the cursorfication. + c.s[vid].flags.incl isConditionallyReassigned else: markAsReassigned(c, vid) @@ -805,7 +879,7 @@ proc computeLiveRanges(c: var Partitions; n: PNode) = for child in n: computeLiveRanges(c, child) let parameters = n[0].typ - let L = if parameters != nil: parameters.len else: 0 + let L = if parameters != nil: parameters.signatureLen else: 0 for i in 1..<n.len: let it = n[i] @@ -834,11 +908,21 @@ proc computeLiveRanges(c: var Partitions; n: PNode) = # connect(graph, cursorVar) inc c.inLoop for child in n: computeLiveRanges(c, child) - inc c.inLoop + dec c.inLoop + + if n.kind == nkWhileStmt: + computeLiveRanges(c, n[0]) + # variables in while condition has longer alive time than local variables + # in the while loop body of nkElifBranch, nkElifExpr, nkElse, nkOfBranch: inc c.inConditional for child in n: computeLiveRanges(c, child) dec c.inConditional + of nkDefer: + if c.processDefer: + for child in n: computeLiveRanges(c, child) + else: + c.defers.add n else: for child in n: computeLiveRanges(c, child) @@ -852,13 +936,21 @@ proc computeGraphPartitions*(s: PSym; n: PNode; g: ModuleGraph; goals: set[Goal] registerResult(result, s.ast[resultPos]) computeLiveRanges(result, n) + result.processDefer = true + for i in countdown(len(result.defers)-1, 0): + computeLiveRanges(result, result.defers[i]) + result.processDefer = false # restart the timer for the second pass: result.abstractTime = AbstractTime 0 traverse(result, n) + result.processDefer = true + for i in countdown(len(result.defers)-1, 0): + traverse(result, result.defers[i]) + result.processDefer = false proc dangerousMutation(g: MutationInfo; v: VarIndex): bool = #echo "range ", v.aliveStart, " .. ", v.aliveEnd, " ", v.sym - if isMutated in g.flags: + if {isMutated, isMutatedByVarParam} * g.flags != {}: for m in g.mutations: #echo "mutation ", m if m in v.aliveStart..v.aliveEnd: @@ -915,10 +1007,13 @@ proc computeCursors*(s: PSym; n: PNode; g: ModuleGraph) = if v.flags * {ownsData, preventCursor, isConditionallyReassigned} == {} and v.sym.kind notin {skParam, skResult} and v.sym.flags * {sfThread, sfGlobal} == {} and hasDestructor(v.sym.typ) and - v.sym.typ.skipTypes({tyGenericInst, tyAlias}).kind != tyOwned: + v.sym.typ.skipTypes({tyGenericInst, tyAlias}).kind != tyOwned and + (getAttachedOp(g, v.sym.typ, attachedAsgn) == nil or + sfError notin getAttachedOp(g, v.sym.typ, attachedAsgn).flags): let rid = root(par, i) if par.s[rid].con.kind == isRootOf and dangerousMutation(par.graphs[par.s[rid].con.graphIndex], par.s[i]): discard "cannot cursor into a graph that is mutated" else: v.sym.flags.incl sfCursor - #echo "this is now a cursor ", v.sym, " ", par.s[rid].flags, " ", config $ v.sym.info + when false: + echo "this is now a cursor ", v.sym, " ", par.s[rid].flags, " ", g.config $ v.sym.info |