diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/nimconf.nim | 106 | ||||
| -rw-r--r-- | compiler/options.nim | 11 | ||||
| -rw-r--r-- | compiler/writetracking.nim | 288 |
3 files changed, 209 insertions, 196 deletions
diff --git a/compiler/nimconf.nim b/compiler/nimconf.nim index b9c78cecc..496bd0123 100644 --- a/compiler/nimconf.nim +++ b/compiler/nimconf.nim @@ -9,106 +9,106 @@ # This module handles the reading of the config file. -import - llstream, nversion, commands, os, strutils, msgs, platform, condsyms, lexer, +import + llstream, nversion, commands, os, strutils, msgs, platform, condsyms, lexer, options, idents, wordrecg, strtabs # ---------------- configuration file parser ----------------------------- # we use Nim's scanner here to save space and work -proc ppGetTok(L: var TLexer, tok: var TToken) = +proc ppGetTok(L: var TLexer, tok: var TToken) = # simple filter rawGetTok(L, tok) while tok.tokType in {tkComment}: rawGetTok(L, tok) - + proc parseExpr(L: var TLexer, tok: var TToken): bool -proc parseAtom(L: var TLexer, tok: var TToken): bool = - if tok.tokType == tkParLe: +proc parseAtom(L: var TLexer, tok: var TToken): bool = + if tok.tokType == tkParLe: ppGetTok(L, tok) result = parseExpr(L, tok) if tok.tokType == tkParRi: ppGetTok(L, tok) else: lexMessage(L, errTokenExpected, "\')\'") - elif tok.ident.id == ord(wNot): + elif tok.ident.id == ord(wNot): ppGetTok(L, tok) result = not parseAtom(L, tok) else: result = isDefined(tok.ident) ppGetTok(L, tok) -proc parseAndExpr(L: var TLexer, tok: var TToken): bool = +proc parseAndExpr(L: var TLexer, tok: var TToken): bool = result = parseAtom(L, tok) - while tok.ident.id == ord(wAnd): + while tok.ident.id == ord(wAnd): ppGetTok(L, tok) # skip "and" var b = parseAtom(L, tok) result = result and b -proc parseExpr(L: var TLexer, tok: var TToken): bool = +proc parseExpr(L: var TLexer, tok: var TToken): bool = result = parseAndExpr(L, tok) - while tok.ident.id == ord(wOr): + while tok.ident.id == ord(wOr): ppGetTok(L, tok) # skip "or" var b = parseAndExpr(L, tok) result = result or b -proc evalppIf(L: var TLexer, tok: var TToken): bool = +proc evalppIf(L: var TLexer, tok: var TToken): bool = ppGetTok(L, tok) # skip 'if' or 'elif' result = parseExpr(L, tok) if tok.tokType == tkColon: ppGetTok(L, tok) else: lexMessage(L, errTokenExpected, "\':\'") - + var condStack: seq[bool] = @[] -proc doEnd(L: var TLexer, tok: var TToken) = +proc doEnd(L: var TLexer, tok: var TToken) = if high(condStack) < 0: lexMessage(L, errTokenExpected, "@if") ppGetTok(L, tok) # skip 'end' setLen(condStack, high(condStack)) -type - TJumpDest = enum +type + TJumpDest = enum jdEndif, jdElseEndif proc jumpToDirective(L: var TLexer, tok: var TToken, dest: TJumpDest) -proc doElse(L: var TLexer, tok: var TToken) = +proc doElse(L: var TLexer, tok: var TToken) = if high(condStack) < 0: lexMessage(L, errTokenExpected, "@if") ppGetTok(L, tok) if tok.tokType == tkColon: ppGetTok(L, tok) if condStack[high(condStack)]: jumpToDirective(L, tok, jdEndif) - -proc doElif(L: var TLexer, tok: var TToken) = + +proc doElif(L: var TLexer, tok: var TToken) = if high(condStack) < 0: lexMessage(L, errTokenExpected, "@if") var res = evalppIf(L, tok) if condStack[high(condStack)] or not res: jumpToDirective(L, tok, jdElseEndif) else: condStack[high(condStack)] = true - -proc jumpToDirective(L: var TLexer, tok: var TToken, dest: TJumpDest) = + +proc jumpToDirective(L: var TLexer, tok: var TToken, dest: TJumpDest) = var nestedIfs = 0 - while true: + while true: if tok.ident != nil and tok.ident.s == "@": ppGetTok(L, tok) case whichKeyword(tok.ident) - of wIf: + of wIf: inc(nestedIfs) - of wElse: + of wElse: if dest == jdElseEndif and nestedIfs == 0: doElse(L, tok) - break - of wElif: + break + of wElif: if dest == jdElseEndif and nestedIfs == 0: doElif(L, tok) - break - of wEnd: - if nestedIfs == 0: + break + of wEnd: + if nestedIfs == 0: doEnd(L, tok) - break + break if nestedIfs > 0: dec(nestedIfs) - else: + else: discard ppGetTok(L, tok) elif tok.tokType == tkEof: lexMessage(L, errTokenExpected, "@end") else: ppGetTok(L, tok) - -proc parseDirective(L: var TLexer, tok: var TToken) = + +proc parseDirective(L: var TLexer, tok: var TToken) = ppGetTok(L, tok) # skip @ case whichKeyword(tok.ident) of wIf: @@ -126,13 +126,13 @@ proc parseDirective(L: var TLexer, tok: var TToken) = ppGetTok(L, tok) else: case tok.ident.s.normalize - of "putenv": + of "putenv": ppGetTok(L, tok) var key = tokToStr(tok) ppGetTok(L, tok) os.putEnv(key, tokToStr(tok)) ppGetTok(L, tok) - of "prependenv": + of "prependenv": ppGetTok(L, tok) var key = tokToStr(tok) ppGetTok(L, tok) @@ -145,17 +145,17 @@ proc parseDirective(L: var TLexer, tok: var TToken) = os.putEnv(key, os.getEnv(key) & tokToStr(tok)) ppGetTok(L, tok) else: lexMessage(L, errInvalidDirectiveX, tokToStr(tok)) - -proc confTok(L: var TLexer, tok: var TToken) = + +proc confTok(L: var TLexer, tok: var TToken) = ppGetTok(L, tok) - while tok.ident != nil and tok.ident.s == "@": + while tok.ident != nil and tok.ident.s == "@": parseDirective(L, tok) # else: give the token to the parser - -proc checkSymbol(L: TLexer, tok: TToken) = - if tok.tokType notin {tkSymbol..pred(tkIntLit), tkStrLit..tkTripleStrLit}: + +proc checkSymbol(L: TLexer, tok: TToken) = + if tok.tokType notin {tkSymbol..pred(tkIntLit), tkStrLit..tkTripleStrLit}: lexMessage(L, errIdentifierExpected, tokToStr(tok)) - -proc parseAssignment(L: var TLexer, tok: var TToken) = + +proc parseAssignment(L: var TLexer, tok: var TToken) = if tok.ident.id == getIdent("-").id or tok.ident.id == getIdent("--").id: confTok(L, tok) # skip unnecessary prefix var info = getLineInfo(L, tok) # save for later in case of an error @@ -163,13 +163,13 @@ proc parseAssignment(L: var TLexer, tok: var TToken) = var s = tokToStr(tok) confTok(L, tok) # skip symbol var val = "" - while tok.tokType == tkDot: + while tok.tokType == tkDot: add(s, '.') confTok(L, tok) checkSymbol(L, tok) add(s, tokToStr(tok)) confTok(L, tok) - if tok.tokType == tkBracketLe: + if tok.tokType == tkBracketLe: # BUGFIX: val, not s! # BUGFIX: do not copy '['! confTok(L, tok) @@ -180,7 +180,7 @@ proc parseAssignment(L: var TLexer, tok: var TToken) = else: lexMessage(L, errTokenExpected, "']'") add(val, ']') let percent = tok.ident.id == getIdent("%=").id - if tok.tokType in {tkColon, tkEquals} or percent: + if tok.tokType in {tkColon, tkEquals} or percent: if len(val) > 0: add(val, ':') confTok(L, tok) # skip ':' or '=' or '%' checkSymbol(L, tok) @@ -226,15 +226,7 @@ proc getSystemConfigPath(filename: string): string = if not existsFile(result): result = "/etc/" & filename proc loadConfigs*(cfg: string) = - # set default value (can be overwritten): - if libpath == "": - # choose default libpath: - var prefix = getPrefixDir() - when defined(posix): - if prefix == "/usr": libpath = "/usr/lib/nim" - elif prefix == "/usr/local": libpath = "/usr/local/lib/nim" - else: libpath = joinPath(prefix, "lib") - else: libpath = joinPath(prefix, "lib") + setDefaultLibpath() if optSkipConfigFile notin gGlobalOptions: readConfigFile(getSystemConfigPath(cfg)) @@ -246,10 +238,10 @@ proc loadConfigs*(cfg: string) = if optSkipParentConfigFiles notin gGlobalOptions: for dir in parentDirs(pd, fromRoot=true, inclusive=false): readConfigFile(dir / cfg) - + if optSkipProjConfigFile notin gGlobalOptions: readConfigFile(pd / cfg) - + if gProjectName.len != 0: # new project wide config file: var projectConfig = changeFileExt(gProjectFull, "nimcfg") diff --git a/compiler/options.nim b/compiler/options.nim index 1f167e2a6..adb340fea 100644 --- a/compiler/options.nim +++ b/compiler/options.nim @@ -191,6 +191,17 @@ proc getPrefixDir*(): string = else: result = splitPath(getAppDir()).head +proc setDefaultLibpath*() = + # set default value (can be overwritten): + if libpath == "": + # choose default libpath: + var prefix = getPrefixDir() + when defined(posix): + if prefix == "/usr": libpath = "/usr/lib/nim" + elif prefix == "/usr/local": libpath = "/usr/local/lib/nim" + else: libpath = joinPath(prefix, "lib") + else: libpath = joinPath(prefix, "lib") + proc canonicalizePath*(path: string): string = when not FileSystemCaseSensitive: result = path.expandFilename.toLower else: result = path.expandFilename 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) - |