diff options
Diffstat (limited to 'compiler/dfa.nim')
| -rw-r--r-- | compiler/dfa.nim | 549 |
1 files changed, 135 insertions, 414 deletions
diff --git a/compiler/dfa.nim b/compiler/dfa.nim index 2254cd0ff..5534d07e7 100644 --- a/compiler/dfa.nim +++ b/compiler/dfa.nim @@ -9,38 +9,34 @@ ## Data flow analysis for Nim. ## We transform the AST into a linear list of instructions first to -## make this easier to handle: There are only 2 different branching +## make this easier to handle: There are only 3 different branching ## instructions: 'goto X' is an unconditional goto, 'fork X' ## is a conditional goto (either the next instruction or 'X' can be -## taken). Exhaustive case statements are translated +## taken), 'loop X' is the only jump that jumps back. +## +## Exhaustive case statements are translated ## so that the last branch is transformed into an 'else' branch. ## ``return`` and ``break`` are all covered by 'goto'. ## -## Control flow through exception handling: -## Contrary to popular belief, exception handling doesn't cause -## many problems for this DFA representation, ``raise`` is a statement -## that ``goes to`` the outer ``finally`` or ``except`` if there is one, -## otherwise it is the same as ``return``. Every call is treated as -## a call that can potentially ``raise``. However, without a surrounding -## ``try`` we don't emit these ``fork ReturnLabel`` instructions in order -## to speed up the dataflow analysis passes. -## ## The data structures and algorithms used here are inspired by ## "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, types, intsets, lineinfos, renderer, asciitables +import ast, lineinfos, renderer, aliasanalysis +import std/private/asciitables +import std/intsets -from patterns import sameTrees +when defined(nimPreviewSlimSystem): + import std/assertions type InstrKind* = enum - goto, fork, def, use + goto, loop, fork, def, use Instr* = object - n*: PNode # contains the def/use location. case kind*: InstrKind - of goto, fork: dest*: int - else: discard + of goto, fork, loop: dest*: int + of def, use: + n*: PNode # contains the def/use location. ControlFlowGraph* = seq[Instr] @@ -50,24 +46,26 @@ type case isTryBlock: bool of false: label: PSym - breakFixups: seq[(TPosition, seq[PNode])] #Contains the gotos for the breaks along with their pending finales + breakFixups: seq[(TPosition, seq[PNode])] # Contains the gotos for the breaks along with their pending finales of true: finale: PNode - raiseFixups: seq[TPosition] #Contains the gotos for the raises + raiseFixups: seq[TPosition] # Contains the gotos for the raises Con = object code: ControlFlowGraph - inTryStmt: int + inTryStmt, interestingInstructions: int blocks: seq[TBlock] owner: PSym + root: PSym proc codeListing(c: ControlFlowGraph, start = 0; last = -1): string = # for debugging purposes # first iteration: compute all necessary labels: + result = "" var jumpTargets = initIntSet() let last = if last < 0: c.len-1 else: min(last, c.len-1) for i in start..last: - if c[i].kind in {goto, fork}: + if c[i].kind in {goto, fork, loop}: jumpTargets.incl(i+c[i].dest) var i = start while i <= last: @@ -78,12 +76,12 @@ proc codeListing(c: ControlFlowGraph, start = 0; last = -1): string = case c[i].kind of def, use: result.add renderTree(c[i].n) - of goto, fork: + result.add("\t#") + result.add($c[i].n.info.line) + result.add("\n") + of goto, fork, loop: result.add "L" result.addInt c[i].dest+i - result.add("\t#") - result.add($c[i].n.info.line) - result.add("\n") inc i if i in jumpTargets: result.add("L" & $i & ": End\n") @@ -91,181 +89,13 @@ proc echoCfg*(c: ControlFlowGraph; start = 0; last = -1) {.deprecated.} = ## echos the ControlFlowGraph for debugging purposes. echo codeListing(c, start, last).alignTable -proc forkI(c: var Con; n: PNode): TPosition = +proc forkI(c: var Con): TPosition = result = TPosition(c.code.len) - c.code.add Instr(n: n, kind: fork, dest: 0) + c.code.add Instr(kind: fork, dest: 0) -proc gotoI(c: var Con; n: PNode): TPosition = +proc gotoI(c: var Con): TPosition = result = TPosition(c.code.len) - c.code.add Instr(n: n, kind: goto, dest: 0) - -#[ - -Join is no more -=============== -Instead of generating join instructions we adapt our traversal of the CFG. - -When encountering a fork we split into two paths, we follow the path -starting at "pc + 1" until it encounters the joinpoint: "pc + forkInstr.dest". -If we encounter gotos that would jump further than the current joinpoint, -as can happen with gotos generated by unstructured controlflow such as break, raise or return, -we simply suspend following the current path, and follow the other path until the new joinpoint -which is simply the instruction pointer returned to us by the now suspended path. -If the path we are following now, also encounters a goto that exceeds the joinpoint -we repeat the process; suspending the current path and evaluating the other one with a new joinpoint. -If we eventually reach a common joinpoint we join the two paths. -This new "ping-pong" approach has the obvious advantage of not requiring join instructions, as such -cutting down on the CFG size but is also mandatory for correctly handling complicated cases -of unstructured controlflow. - - -Design of join -============== - -block: - if cond: break - def(x) - -use(x) - -Generates: - -L0: fork lab1 - join L0 # patched. - goto Louter -lab1: - def x - join L0 -Louter: - use x - - -block outer: - while a: - while b: - if foo: - if bar: - break outer # --> we need to 'join' every pushed 'fork' here - - -This works and then our abstract interpretation needs to deal with 'fork' -differently. It really causes a split in execution. Two threads are -"spawned" and both need to reach the 'join L' instruction. Afterwards -the abstract interpretations are joined and execution resumes single -threaded. - - -Abstract Interpretation ------------------------ - -proc interpret(pc, state, comesFrom): state = - result = state - # we need an explicit 'create' instruction (an explicit heap), in order - # to deal with 'var x = create(); var y = x; var z = y; destroy(z)' - while true: - case pc - of fork: - let a = interpret(pc+1, result, pc) - let b = interpret(forkTarget, result, pc) - result = a ++ b # ++ is a union operation - inc pc - of join: - if joinTarget == comesFrom: return result - else: inc pc - of use X: - if not result.contains(x): - error "variable not initialized " & x - inc pc - of def X: - if not result.contains(x): - result.incl X - else: - error "overwrite of variable causes memory leak " & x - inc pc - of destroy X: - result.excl X - -This is correct but still can lead to false positives: - -proc p(cond: bool) = - if cond: - new(x) - otherThings() - if cond: - destroy x - -Is not a leak. We should find a way to model *data* flow, not just -control flow. One solution is to rewrite the 'if' without a fork -instruction. The unstructured aspect can now be easily dealt with -the 'goto' and 'join' instructions. - -proc p(cond: bool) = - L0: fork Lend - new(x) - # do not 'join' here! - - Lend: - otherThings() - join L0 # SKIP THIS FOR new(x) SOMEHOW - destroy x - join L0 # but here. - - - -But if we follow 'goto Louter' we will never come to the join point. -We restore the bindings after popping pc from the stack then there -"no" problem?! - - -while cond: - prelude() - if not condB: break - postlude() - ----> -var setFlag = true -while cond and not setFlag: - prelude() - if not condB: - setFlag = true # BUT: Dependency - if not setFlag: # HERE - postlude() - ----> -var setFlag = true -while cond and not setFlag: - prelude() - if not condB: - postlude() - setFlag = true - - -------------------------------------------------- - -while cond: - prelude() - if more: - if not condB: break - stuffHere() - postlude() - ---> -var setFlag = true -while cond and not setFlag: - prelude() - if more: - if not condB: - setFlag = false - else: - stuffHere() - postlude() - else: - postlude() - -This is getting complicated. Instead we keep the whole 'join' idea but -duplicate the 'join' instructions on breaks and return exits! - -]# + c.code.add Instr(kind: goto, dest: 0) proc genLabel(c: Con): TPosition = TPosition(c.code.len) @@ -273,23 +103,23 @@ template checkedDistance(dist): int = doAssert low(int) div 2 + 1 < dist and dist < high(int) div 2 dist -proc jmpBack(c: var Con, n: PNode, p = TPosition(0)) = - c.code.add Instr(n: n, kind: goto, dest: checkedDistance(p.int - c.code.len)) +proc jmpBack(c: var Con, p = TPosition(0)) = + c.code.add Instr(kind: loop, dest: checkedDistance(p.int - c.code.len)) proc patch(c: var Con, p: TPosition) = # patch with current index c.code[p.int].dest = checkedDistance(c.code.len - p.int) -func gen(c: var Con; n: PNode) +proc gen(c: var Con; n: PNode) proc popBlock(c: var Con; oldLen: int) = - var exits: seq[TPosition] - exits.add c.gotoI(newNode(nkEmpty)) + var exits: seq[TPosition] = @[] + exits.add c.gotoI() for f in c.blocks[oldLen].breakFixups: c.patch(f[0]) for finale in f[1]: c.gen(finale) - exits.add c.gotoI(newNode(nkEmpty)) + exits.add c.gotoI() for e in exits: c.patch e c.blocks.setLen(oldLen) @@ -300,89 +130,28 @@ template withBlock(labl: PSym; body: untyped) = body popBlock(c, oldLen) -proc isTrue(n: PNode): bool = - n.kind == nkSym and n.sym.kind == skEnumField and n.sym.position != 0 or - n.kind == nkIntLit and n.intVal != 0 - -when true: - proc genWhile(c: var Con; n: PNode) = - # We unroll every loop 3 times. We emulate 0, 1, 2 iterations - # through the loop. We need to prove this is correct for our - # purposes. But Herb Sutter claims it is. (Proof by authority.) - #[ - while cond: - body - - Becomes: - - block: - if cond: - body - if cond: - body - if cond: - body - - We still need to ensure 'break' resolves properly, so an AST to AST - translation is impossible. - - So the code to generate is: - - cond - fork L4 # F1 - body - cond - fork L5 # F2 - body - cond - fork L6 # F3 - body - L6: - join F3 - L5: - join F2 - L4: - join F1 - ]# +template forkT(body) = + let lab1 = c.forkI() + body + c.patch(lab1) + +proc genWhile(c: var Con; n: PNode) = + # lab1: + # cond, tmp + # fork tmp, lab2 + # body + # jmp lab1 + # lab2: + let lab1 = c.genLabel + withBlock(nil): if isTrue(n[0]): - # 'while true' is an idiom in Nim and so we produce - # better code for it: - withBlock(nil): - for i in 0..2: - c.gen(n[1]) + c.gen(n[1]) + c.jmpBack(lab1) else: - withBlock(nil): - var endings: array[3, TPosition] - for i in 0..2: - c.gen(n[0]) - endings[i] = c.forkI(n) - c.gen(n[1]) - for i in countdown(endings.high, 0): - c.patch(endings[i]) - -else: - proc genWhile(c: var Con; n: PNode) = - # lab1: - # cond, tmp - # fork tmp, lab2 - # body - # jmp lab1 - # lab2: - let lab1 = c.genLabel - withBlock(nil): - if isTrue(n[0]): + c.gen(n[0]) + forkT: c.gen(n[1]) - c.jmpBack(n, lab1) - else: - c.gen(n[0]) - forkT(n): - c.gen(n[1]) - c.jmpBack(n, lab1) - -template forkT(n, body) = - let lab1 = c.forkI(n) - body - c.patch(lab1) + c.jmpBack(lab1) proc genIf(c: var Con, n: PNode) = #[ @@ -412,34 +181,32 @@ proc genIf(c: var Con, n: PNode) = goto Lend3 L3: D - goto Lend3 # not eliminated to simplify the join generation - Lend3: - join F3 - Lend2: - join F2 - Lend: - join F1 - ]# var endings: seq[TPosition] = @[] + let oldInteresting = c.interestingInstructions + let oldLen = c.code.len + for i in 0..<n.len: let it = n[i] c.gen(it[0]) if it.len == 2: - forkT(it[1]): - c.gen(it[1]) - endings.add c.gotoI(it[1]) - for i in countdown(endings.high, 0): - c.patch(endings[i]) + forkT: + c.gen(it.lastSon) + endings.add c.gotoI() + + if oldInteresting == c.interestingInstructions: + setLen c.code, oldLen + else: + for i in countdown(endings.high, 0): + c.patch(endings[i]) proc genAndOr(c: var Con; n: PNode) = # asgn dest, a # fork lab1 # asgn dest, b # lab1: - # join F1 c.gen(n[1]) - forkT(n): + forkT: c.gen(n[2]) proc genCase(c: var Con; n: PNode) = @@ -454,34 +221,40 @@ proc genCase(c: var Con; n: PNode) = # elsePart # Lend: let isExhaustive = skipTypes(n[0].typ, - abstractVarRange-{tyTypeDesc}).kind notin {tyFloat..tyFloat128, tyString} + abstractVarRange-{tyTypeDesc}).kind notin {tyFloat..tyFloat128, tyString, tyCstring} var endings: seq[TPosition] = @[] c.gen(n[0]) + let oldInteresting = c.interestingInstructions + let oldLen = c.code.len for i in 1..<n.len: let it = n[i] if it.len == 1 or (i == n.len-1 and isExhaustive): # treat the last branch as 'else' if this is an exhaustive case statement. c.gen(it.lastSon) else: - forkT(it.lastSon): + forkT: c.gen(it.lastSon) - endings.add c.gotoI(it.lastSon) - for i in countdown(endings.high, 0): - let endPos = endings[i] - c.patch(endPos) + endings.add c.gotoI() + + if oldInteresting == c.interestingInstructions: + setLen c.code, oldLen + else: + for i in countdown(endings.high, 0): + c.patch(endings[i]) proc genBlock(c: var Con; n: PNode) = withBlock(n[0].sym): c.gen(n[1]) proc genBreakOrRaiseAux(c: var Con, i: int, n: PNode) = - let lab1 = c.gotoI(n) + let lab1 = c.gotoI() if c.blocks[i].isTryBlock: c.blocks[i].raiseFixups.add lab1 else: - var trailingFinales: seq[PNode] - if c.inTryStmt > 0: #Ok, we are in a try, lets see which (if any) try's we break out from: + var trailingFinales: seq[PNode] = @[] + if c.inTryStmt > 0: + # Ok, we are in a try, lets see which (if any) try's we break out from: for b in countdown(c.blocks.high, i): if c.blocks[b].isTryBlock: trailingFinales.add c.blocks[b].finale @@ -489,6 +262,7 @@ proc genBreakOrRaiseAux(c: var Con, i: int, n: PNode) = c.blocks[i].breakFixups.add (lab1, trailingFinales) proc genBreak(c: var Con; n: PNode) = + inc c.interestingInstructions if n[0].kind == nkSym: for i in countdown(c.blocks.high, 0): if not c.blocks[i].isTryBlock and c.blocks[i].label == n[0].sym: @@ -519,9 +293,9 @@ proc genTry(c: var Con; n: PNode) = for i in 1..<n.len: let it = n[i] if it.kind != nkFinally: - forkT(it): + forkT: c.gen(it.lastSon) - endings.add c.gotoI(it) + endings.add c.gotoI() for i in countdown(endings.high, 0): c.patch(endings[i]) @@ -529,26 +303,28 @@ proc genTry(c: var Con; n: PNode) = if fin.kind == nkFinally: c.gen(fin[0]) -template genNoReturn(c: var Con; n: PNode) = +template genNoReturn(c: var Con) = # leave the graph - c.code.add Instr(n: n, kind: goto, dest: high(int) - c.code.len) + c.code.add Instr(kind: goto, dest: high(int) - c.code.len) proc genRaise(c: var Con; n: PNode) = + inc c.interestingInstructions gen(c, n[0]) if c.inTryStmt > 0: for i in countdown(c.blocks.high, 0): if c.blocks[i].isTryBlock: genBreakOrRaiseAux(c, i, n) return - assert false #Unreachable + assert false # Unreachable else: - genNoReturn(c, n) + genNoReturn(c) proc genImplicitReturn(c: var Con) = if c.owner.kind in {skProc, skFunc, skMethod, skIterator, skConverter} and resultPos < c.owner.ast.len: gen(c, c.owner.ast[resultPos]) proc genReturn(c: var Con; n: PNode) = + inc c.interestingInstructions if n[0].kind != nkEmpty: gen(c, n[0]) else: @@ -557,89 +333,6 @@ proc genReturn(c: var Con; n: PNode) = const InterestingSyms = {skVar, skResult, skLet, skParam, skForVar, skTemp} - PathKinds0 = {nkDotExpr, nkCheckedFieldExpr, - nkBracketExpr, nkDerefExpr, nkHiddenDeref, - nkAddr, nkHiddenAddr, - nkObjDownConv, nkObjUpConv} - PathKinds1 = {nkHiddenStdConv, nkHiddenSubConv} - -proc skipConvDfa*(n: PNode): PNode = - result = n - while true: - case result.kind - of nkObjDownConv, nkObjUpConv: - result = result[0] - of PathKinds1: - result = result[1] - else: break - -proc aliases*(obj, field: PNode): bool = - var n = field - var obj = obj - while true: - case obj.kind - of {nkObjDownConv, nkObjUpConv, nkAddr, nkHiddenAddr, nkDerefExpr, nkHiddenDeref}: - obj = obj[0] - of PathKinds1: - obj = obj[1] - else: break - while true: - if sameTrees(obj, n): return true - case n.kind - of PathKinds0: - n = n[0] - of PathKinds1: - n = n[1] - else: break - -type InstrTargetKind* = enum - None, Full, Partial - -proc instrTargets*(insloc, loc: PNode): InstrTargetKind = - if sameTrees(insloc, loc) or insloc.aliases(loc): - Full # x -> x; x -> x.f - elif loc.aliases(insloc): - Partial # x.f -> x - else: None - -proc isAnalysableFieldAccess*(orig: PNode; owner: PSym): bool = - var n = orig - while true: - case n.kind - of PathKinds0 - {nkBracketExpr, nkHiddenDeref, nkDerefExpr}: - n = n[0] - of PathKinds1: - n = n[1] - of nkBracketExpr: - # in a[i] the 'i' must be known - if n.len > 1 and n[1].kind in {nkCharLit..nkUInt64Lit}: - n = n[0] - else: - return false - of nkHiddenDeref, nkDerefExpr: - # We "own" sinkparam[].loc but not ourVar[].location as it is a nasty - # pointer indirection. - # bug #14159, we cannot reason about sinkParam[].location as it can - # still be shared for tyRef. - n = n[0] - return n.kind == nkSym and n.sym.owner == owner and - (n.sym.typ.skipTypes(abstractInst-{tyOwned}).kind in {tyOwned}) - 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 and - (n.sym.kind != skParam or isSinkParam(n.sym)) # or n.sym.typ.kind == tyVar) - # Note: There is a different move analyzer possible that checks for - # consume(param.key); param.key = newValue for all paths. Then code like - # - # let splited = split(move self.root, x) - # self.root = merge(splited.lower, splited.greater) - # - # could be written without the ``move self.root``. However, this would be - # wrong! Then the write barrier for the ``self.root`` assignment would - # free the old data and all is lost! Lesson: Don't be too smart, trust the - # lower level C++ optimizer to specialize this code. proc skipTrivials(c: var Con, n: PNode): PNode = result = n @@ -657,16 +350,20 @@ proc skipTrivials(c: var Con, n: PNode): PNode = proc genUse(c: var Con; orig: PNode) = let n = c.skipTrivials(orig) - if n.kind == nkSym and n.sym.kind in InterestingSyms: - c.code.add Instr(n: orig, kind: use) - elif n.kind in nkCallKinds: + if n.kind == nkSym: + if n.sym.kind in InterestingSyms and n.sym == c.root: + c.code.add Instr(kind: use, n: orig) + inc c.interestingInstructions + else: gen(c, n) proc genDef(c: var Con; orig: PNode) = let n = c.skipTrivials(orig) if n.kind == nkSym and n.sym.kind in InterestingSyms: - c.code.add Instr(n: orig, kind: def) + if n.sym == c.root: + c.code.add Instr(kind: def, n: orig) + inc c.interestingInstructions proc genCall(c: var Con; n: PNode) = gen(c, n[0]) @@ -674,18 +371,17 @@ proc genCall(c: var Con; n: PNode) = if t != nil: t = t.skipTypes(abstractInst) for i in 1..<n.len: gen(c, n[i]) - when false: - if t != nil and i < t.len and t[i].kind == tyOut: - # Pass by 'out' is a 'must def'. Good enough for a move optimizer. - genDef(c, n[i]) + if t != nil and i < t.signatureLen and isOutParam(t[i]): + # Pass by 'out' is a 'must def'. Good enough for a move optimizer. + genDef(c, n[i]) # every call can potentially raise: if c.inTryStmt > 0 and canRaiseConservative(n[0]): + inc c.interestingInstructions # we generate the instruction sequence: # fork lab1 # goto exceptionHandler (except or finally) # lab1: - # join F1 - forkT(n): + forkT: for i in countdown(c.blocks.high, 0): if c.blocks[i].isTryBlock: genBreakOrRaiseAux(c, i, n) @@ -712,7 +408,7 @@ proc genVarSection(c: var Con; n: PNode) = if a.lastSon.kind != nkEmpty: genDef(c, a[0]) -func gen(c: var Con; n: PNode) = +proc gen(c: var Con; n: PNode) = case n.kind of nkSym: genUse(c, n) of nkCallKinds: @@ -723,12 +419,18 @@ func gen(c: var Con; n: PNode) = else: genCall(c, n) if sfNoReturn in n[0].sym.flags: - genNoReturn(c, n) + genNoReturn(c) else: genCall(c, n) of nkCharLit..nkNilLit: discard - of nkAsgn, nkFastAsgn: + of nkAsgn, nkFastAsgn, nkSinkAsgn: gen(c, n[1]) + + if n[0].kind in PathKinds0: + let a = c.skipTrivials(n[0]) + if a.kind in nkCallKinds: + gen(c, a) + # 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'. @@ -755,16 +457,35 @@ func gen(c: var Con; n: PNode) = of nkConv, nkExprColonExpr, nkExprEqExpr, nkCast, PathKinds1: gen(c, n[1]) of nkVarSection, nkLetSection: genVarSection(c, n) - of nkDefer: doAssert false, "dfa construction pass requires the elimination of 'defer'" + of nkDefer: raiseAssert "dfa construction pass requires the elimination of 'defer'" else: discard -proc constructCfg*(s: PSym; body: PNode): ControlFlowGraph = +when false: + proc optimizeJumps(c: var ControlFlowGraph) = + for i in 0..<c.len: + case c[i].kind + of goto, fork: + var pc = i + c[i].dest + if pc < c.len and c[pc].kind == goto: + while pc < c.len and c[pc].kind == goto: + let newPc = pc + c[pc].dest + if newPc > pc: + pc = newPc + else: + break + c[i].dest = pc - i + of loop, def, use: discard + +proc constructCfg*(s: PSym; body: PNode; root: PSym): ControlFlowGraph = ## constructs a control flow graph for ``body``. - var c = Con(code: @[], blocks: @[], owner: s) + var c = Con(code: @[], blocks: @[], owner: s, root: root) withBlock(s): gen(c, body) - genImplicitReturn(c) - when defined(gcArc) or defined(gcOrc): + if root.kind == skResult: + genImplicitReturn(c) + when defined(gcArc) or defined(gcOrc) or defined(gcAtomicArc): result = c.code # will move else: shallowCopy(result, c.code) + when false: + optimizeJumps result |