diff options
| -rw-r--r-- | compiler/dfa.nim | 63 | ||||
| -rw-r--r-- | compiler/injectdestructors.nim | 70 | ||||
| -rw-r--r-- | tests/arc/tmovebug.nim | 103 |
3 files changed, 163 insertions, 73 deletions
diff --git a/compiler/dfa.nim b/compiler/dfa.nim index 0db89579b..67a9e26d8 100644 --- a/compiler/dfa.nim +++ b/compiler/dfa.nim @@ -35,11 +35,11 @@ from patterns import sameTrees type InstrKind* = enum - goto, fork, join, def, use + goto, fork, def, use Instr* = object n*: PNode # contains the def/use location. case kind*: InstrKind - of goto, fork, join: dest*: int + of goto, fork: dest*: int else: discard ControlFlowGraph* = seq[Instr] @@ -47,8 +47,6 @@ type TPosition = distinct int TBlock = object - joins: seq[Instr] - forks: seq[TPosition] case isTryBlock: bool of false: label: PSym @@ -72,7 +70,7 @@ proc codeListing(c: ControlFlowGraph, result: var string, start=0; last = -1) = 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, join}: + if c[i].kind in {goto, fork}: jumpTargets.incl(i+c[i].dest) var i = start while i <= last: @@ -83,7 +81,7 @@ proc codeListing(c: ControlFlowGraph, result: var string, start=0; last = -1) = case c[i].kind of def, use: result.add renderTree(c[i].n) - of goto, fork, join: + of goto, fork: result.add "L" result.addInt c[i].dest+i result.add("\t#") @@ -102,7 +100,6 @@ proc echoCfg*(c: ControlFlowGraph; start=0; last = -1) {.deprecated.} = proc forkI(c: var Con; n: PNode): TPosition = result = TPosition(c.code.len) c.code.add Instr(n: n, kind: fork, dest: 0) - c.blocks[^1].forks.add result proc gotoI(c: var Con; n: PNode): TPosition = result = TPosition(c.code.len) @@ -110,6 +107,24 @@ proc gotoI(c: var Con; n: PNode): TPosition = #[ +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 ============== @@ -258,10 +273,6 @@ duplicate the 'join' instructions on breaks and return exits! ]# -proc joinI(c: var Con; fromFork: TPosition; n: PNode) = - let dist = fromFork.int - c.code.len - c.code.add Instr(n: n, kind: join, dest: dist) - proc genLabel(c: Con): TPosition = result = TPosition(c.code.len) @@ -289,10 +300,6 @@ proc popBlock(c: var Con; oldLen: int) = exits.add c.gotoI(newNode(nkEmpty)) for e in exits: c.patch e - for j in c.blocks[oldLen].joins: - var patchedJ = j - patchedJ.dest -= c.code.len - c.code.add patchedJ c.blocks.setLen(oldLen) template withBlock(labl: PSym; body: untyped) {.dirty.} = @@ -353,7 +360,6 @@ when true: c.gen(n[1]) else: withBlock(nil): - let oldForksLen = c.blocks[^1].forks.len var endings: array[3, TPosition] for i in 0..2: c.gen(n[0]) @@ -362,8 +368,6 @@ when true: for i in countdown(endings.high, 0): let endPos = endings[i] c.patch(endPos) - c.joinI(c.blocks[^1].forks.pop(), n) - doAssert(c.blocks[^1].forks.len == oldForksLen) else: @@ -374,7 +378,6 @@ else: # body # jmp lab1 # lab2: - let oldForksLen = c.blocks[^1].forks.len let lab1 = c.genLabel withBlock(nil): if isTrue(n[0]): @@ -386,15 +389,11 @@ else: c.gen(n[1]) c.jmpBack(n, lab1) c.patch(lab2) - setLen(c.blocks[^1].forks, oldForksLen) template forkT(n, body) = - let oldLen = c.blocks[^1].forks.len let lab1 = c.forkI(n) body c.patch(lab1) - c.joinI(lab1, n) - setLen(c.blocks[^1].forks, oldLen) proc genIf(c: var Con, n: PNode) = #[ @@ -433,7 +432,6 @@ proc genIf(c: var Con, n: PNode) = join F1 ]# - let oldLen = c.blocks[^1].forks.len var endings: seq[TPosition] = @[] for i in 0..<n.len: var it = n[i] @@ -446,8 +444,6 @@ proc genIf(c: var Con, n: PNode) = for i in countdown(endings.high, 0): let endPos = endings[i] c.patch(endPos) - c.joinI(c.blocks[^1].forks.pop(), n) - doAssert(c.blocks[^1].forks.len == oldLen) proc genAndOr(c: var Con; n: PNode) = # asgn dest, a @@ -474,7 +470,6 @@ proc genCase(c: var Con; n: PNode) = abstractVarRange-{tyTypeDesc}).kind notin {tyFloat..tyFloat128, tyString} var endings: seq[TPosition] = @[] - let oldLen = c.blocks[^1].forks.len c.gen(n[0]) for i in 1..<n.len: let it = n[i] @@ -491,8 +486,6 @@ proc genCase(c: var Con; n: PNode) = for i in countdown(endings.high, 0): let endPos = endings[i] c.patch(endPos) - c.joinI(c.blocks[^1].forks.pop(), n) - doAssert(c.blocks[^1].forks.len == oldLen) proc genBlock(c: var Con; n: PNode) = withBlock(n[0].sym): @@ -511,10 +504,6 @@ proc genBreakOrRaiseAux(c: var Con, i: int, n: PNode) = c.blocks[i].breakFixups.add (lab1, trailingFinales) - for b in countdown(c.blocks.high, i): - for f in countdown(c.blocks[b].forks.high, 0): - c.blocks[i].joins.add Instr(n: n, kind: join, dest: c.blocks[b].forks[f].int) - proc genBreak(c: var Con; n: PNode) = if n[0].kind == nkSym: #echo cast[int](n[0].sym) @@ -530,7 +519,6 @@ proc genBreak(c: var Con; n: PNode) = return proc genTry(c: var Con; n: PNode) = - let oldForksLen = c.blocks[^1].forks.len var endings: seq[TPosition] = @[] let oldLen = c.blocks.len @@ -543,10 +531,6 @@ proc genTry(c: var Con; n: PNode) = for f in c.blocks[oldLen].raiseFixups: c.patch(f) - for j in c.blocks[oldLen].joins: - var patchedJ = j - patchedJ.dest -= c.code.len - c.code.add patchedJ c.blocks.setLen oldLen @@ -561,7 +545,6 @@ proc genTry(c: var Con; n: PNode) = for i in countdown(endings.high, 0): let endPos = endings[i] c.patch(endPos) - c.joinI(c.blocks[^1].forks.pop(), n) # join the 'elsePos' forkI instruction: #c.joinI(c.blocks[^1].forks.pop(), n) @@ -569,7 +552,6 @@ proc genTry(c: var Con; n: PNode) = let fin = lastSon(n) if fin.kind == nkFinally: c.gen(fin[0]) - doAssert(c.blocks[^1].forks.len == oldForksLen) template genNoReturn(c: var Con; n: PNode) = # leave the graph @@ -751,7 +733,6 @@ proc genCall(c: var Con; n: PNode) = genBreakOrRaiseAux(c, i, n) break c.patch(endGoto) - c.joinI(c.blocks[^1].forks.pop(), n) dec c.inCall proc genMagic(c: var Con; n: PNode; m: TMagic) = diff --git a/compiler/injectdestructors.nim b/compiler/injectdestructors.nim index 44409c760..5785df6d6 100644 --- a/compiler/injectdestructors.nim +++ b/compiler/injectdestructors.nim @@ -65,9 +65,9 @@ template dbg(body) = proc p(n: PNode; c: var Con; mode: ProcessMode): PNode proc moveOrCopy(dest, ri: PNode; c: var Con): PNode -proc isLastRead(location: PNode; c: var Con; pc, comesFrom: int): int = +proc isLastRead(location: PNode; c: var Con; pc, until: int): int = var pc = pc - while pc < c.g.len: + while pc < c.g.len and pc < until: case c.g[pc].kind of def: if defInstrTargets(c.g[pc], location): @@ -83,15 +83,17 @@ proc isLastRead(location: PNode; 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: - let variantA = isLastRead(location, c, pc+1, pc) - if variantA < 0: return -1 - var variantB = isLastRead(location, c, pc + c.g[pc].dest, pc) - if variantB < 0: return -1 + var variantA = pc + 1 + var variantB = pc + c.g[pc].dest + while variantA != variantB: + if min(variantA, variantB) < 0: return -1 + if max(variantA, variantB) >= c.g.len or min(variantA, variantB) >= until: + break + if variantA < variantB: + variantA = isLastRead(location, c, variantA, min(variantB, until)) + else: + variantB = isLastRead(location, c, variantB, min(variantA, until)) pc = min(variantA, variantB) - of InstrKind.join: - let dest = pc + c.g[pc].dest - if dest == comesFrom: return pc + 1 - inc pc return pc proc isLastRead(n: PNode; c: var Con): bool = @@ -114,12 +116,12 @@ proc isLastRead(n: PNode; c: var Con): bool = # ensure that we don't find another 'use X' instruction. if instr+1 >= c.g.len: return true - result = isLastRead(n, c, instr+1, -1) >= 0 + result = isLastRead(n, c, instr+1, int.high) >= 0 dbg: echo "ugh ", c.otherRead.isNil, " ", result -proc isFirstWrite(location: PNode; c: var Con; pc, comesFrom: int; instr: int): int = +proc isFirstWrite(location: PNode; c: var Con; pc, until: int): int = var pc = pc - while pc < instr: + while pc < until: case c.g[pc].kind of def: if defInstrTargets(c.g[pc], location): @@ -134,15 +136,17 @@ proc isFirstWrite(location: PNode; c: var Con; pc, comesFrom: int; instr: int): pc = pc + c.g[pc].dest of fork: # every branch must not contain a def/use of our location: - let variantA = isFirstWrite(location, c, pc+1, pc, instr) - if variantA < 0: return -1 - var variantB = isFirstWrite(location, c, pc + c.g[pc].dest, pc, instr + c.g[pc].dest) - if variantB < 0: return -1 + var variantA = pc + 1 + var variantB = pc + c.g[pc].dest + while variantA != variantB: + if min(variantA, variantB) < 0: return -1 + if max(variantA, variantB) > until: + break + if variantA < variantB: + variantA = isFirstWrite(location, c, variantA, min(variantB, until)) + else: + variantB = isFirstWrite(location, c, variantB, min(variantA, until)) pc = min(variantA, variantB) - of InstrKind.join: - let dest = pc + c.g[pc].dest - if dest == comesFrom: return pc + 1 - inc pc return pc proc isFirstWrite(n: PNode; c: var Con): bool = @@ -161,10 +165,10 @@ proc isFirstWrite(n: PNode; c: var Con): bool = # ensure that we don't find another 'def/use X' instruction. if instr == 0: return true - result = isFirstWrite(n, c, 0, -1, instr) >= 0 + result = isFirstWrite(n, c, 0, instr) >= 0 proc initialized(code: ControlFlowGraph; pc: int, - init, uninit: var IntSet; comesFrom: int): int = + init, uninit: var IntSet; until: int): int = ## Computes the set of definitely initialized variables across all code paths ## as an IntSet of IDs. var pc = pc @@ -173,20 +177,22 @@ proc initialized(code: ControlFlowGraph; pc: int, of goto: pc = pc + code[pc].dest of fork: - let target = pc + code[pc].dest var initA = initIntSet() var initB = initIntSet() - let pcA = initialized(code, pc+1, initA, uninit, pc) - discard initialized(code, target, initB, uninit, pc) + var variantA = pc + 1 + var variantB = pc + code[pc].dest + while variantA != variantB: + if max(variantA, variantB) > until: + break + if variantA < variantB: + variantA = initialized(code, variantA, initA, uninit, min(variantB, until)) + else: + variantB = initialized(code, variantB, initB, uninit, min(variantA, until)) + pc = min(variantA, variantB) # we add vars if they are in both branches: for v in initA: if v in initB: init.incl v - pc = pcA+1 - of InstrKind.join: - let target = pc + code[pc].dest - if comesFrom == target: return pc - inc pc of use: let v = code[pc].n.sym if v.kind != skParam and v.id notin init: @@ -1040,7 +1046,7 @@ proc computeUninit(c: var Con) = c.uninitComputed = true c.uninit = initIntSet() var init = initIntSet() - discard initialized(c.g, pc = 0, init, c.uninit, comesFrom = -1) + discard initialized(c.g, pc = 0, init, c.uninit, int.high) proc injectDefaultCalls(n: PNode, c: var Con) = case n.kind diff --git a/tests/arc/tmovebug.nim b/tests/arc/tmovebug.nim index 6ed10c403..39f1c8bf4 100644 --- a/tests/arc/tmovebug.nim +++ b/tests/arc/tmovebug.nim @@ -19,6 +19,23 @@ c.text = hello c.text = hello pOD.text = hello pOD.toks = @["hello"] +fff +fff +2 +fff +fff +2 +fff +fff +2 +mmm +fff +fff +fff +3 +mmm +sink me (sink) +assign me (not sink) ''' """ @@ -199,3 +216,89 @@ when false: let pOHD = parseOHD() dump pOHD.text dump pOHD.toks + +# bug #13456 + +iterator combinations[T](s: openarray[T], k: int): seq[T] = + let n = len(s) + assert k >= 0 and k <= n + var pos = newSeq[int](k) + var current = newSeq[T](k) + for i in 0..k-1: + pos[k-i-1] = i + var done = false + while not done: + for i in 0..k-1: + current[i] = s[pos[k-i-1]] + yield current + var i = 0 + while i < k: + pos[i] += 1 + if pos[i] < n-i: + for j in 0..i-1: + pos[j] = pos[i] + i - j + break + i += 1 + if i >= k: + break + +type + UndefEx = object of Exception + +proc main2 = + var delayedSyms = @[1, 2, 3] + var unp: seq[int] + block myb: + for a in 1 .. 2: + if delayedSyms.len > a: + unp = delayedSyms + for t in unp.combinations(a + 1): + try: + var h = false + for k in t: + echo "fff" + if h: continue + if true: + raise newException(UndefEx, "forward declaration") + break myb + except UndefEx: + echo t.len + echo "mmm" + +main2() + + + +type ME = object + who: string + +proc `=`(x: var ME, y: ME) = + if x.who.len > 0: echo "assign ",x.who + +proc `=sink`(x: var ME, y: ME) = + if x.who.len > 0: echo "sink ",x.who + +var dump: ME +template use(x) = dump = x +template def(x) = x = dump + +var c = true + +proc shouldSink() = + var x = ME(who: "me (sink)") + use(x) # we analyse this + if c: def(x) + else: def(x) + use(x) # ok, with the [else] part. + +shouldSink() + +dump = ME() + +proc shouldNotSink() = + var x = ME(who: "me (not sink)") + use(x) # we analyse this + if c: def(x) + use(x) # Not ok without the '[else]' + +shouldNotSink() |