diff options
Diffstat (limited to 'compiler/dfa.nim')
| -rw-r--r-- | compiler/dfa.nim | 63 |
1 files changed, 22 insertions, 41 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) = |