Merge pull request #1 from nim-lang/devel

upstream

1 files changed, 92 insertions, 87 deletions

diff --git a/compiler/dfa.nim b/compiler/dfa.nim
index ca1849a3c..b648995f4 100644
--- a/compiler/dfa.nim
+++ b/compiler/dfa.nim
@@ -132,7 +132,7 @@ proc gen(c: var Con; n: PNode) # {.noSideEffect.}
 proc genWhile(c: var Con; n: PNode) =
   # L1:
   #   cond, tmp
-  #   fjmp tmp, L2
+  #   fork tmp, L2
   #   body
   #   jmp L1
   # L2:
@@ -168,15 +168,13 @@ proc genIf(c: var Con, n: PNode) =
   var endings: seq[TPosition] = @[]
   for i in countup(0, len(n) - 1):
     var it = n.sons[i]
+    c.gen(it.sons[0])
     if it.len == 2:
-      c.gen(it.sons[0].sons[1])
-      var elsePos = c.forkI(it.sons[0].sons[1])
+      let elsePos = c.forkI(it.sons[1])
       c.gen(it.sons[1])
       if i < sonsLen(n)-1:
         endings.add(c.gotoI(it.sons[1]))
       c.patch(elsePos)
-    else:
-      c.gen(it.sons[0])
   for endPos in endings: c.patch(endPos)
 
 proc genAndOr(c: var Con; n: PNode) =
@@ -202,7 +200,7 @@ proc genCase(c: var Con; n: PNode) =
   #  Lend:
   var endings: seq[TPosition] = @[]
   c.gen(n.sons[0])
-  for i in 1 .. <n.len:
+  for i in 1 ..< n.len:
     let it = n.sons[i]
     if it.len == 1:
       c.gen(it.sons[0])
@@ -219,7 +217,7 @@ proc genTry(c: var Con; n: PNode) =
   let elsePos = c.forkI(n)
   c.gen(n.sons[0])
   c.patch(elsePos)
-  for i in 1 .. <n.len:
+  for i in 1 ..< n.len:
     let it = n.sons[i]
     if it.kind != nkFinally:
       var blen = len(it)
@@ -337,100 +335,107 @@ proc gen(c: var Con; n: PNode) =
   else: discard
 
 proc dfa(code: seq[Instr]) =
-  # We aggressively push 'undef' values for every 'use v' instruction
-  # until they are eliminated via a 'def v' instructions.
-  # If we manage to push one 'undef' to a 'use' instruction, we produce
-  # an error:
-  var undef = initIntSet()
+  var u = newSeq[IntSet](code.len) # usages
+  var d = newSeq[IntSet](code.len) # defs
+  var c = newSeq[IntSet](code.len) # consumed
+  var backrefs = initTable[int, int]()
   for i in 0..<code.len:
-    if code[i].kind == use: undef.incl(code[i].sym.id)
+    u[i] = initIntSet()
+    d[i] = initIntSet()
+    c[i] = initIntSet()
+    case code[i].kind
+    of use, useWithinCall: u[i].incl(code[i].sym.id)
+    of def: d[i].incl(code[i].sym.id)
+    of fork, goto:
+      let d = i+code[i].dest
+      backrefs.add(d, i)
 
-  var s = newSeq[IntSet](code.len)
-  for i in 0..<code.len:
-    assign(s[i], undef)
-
-  # In the original paper, W := {0,...,n} is done. This is wasteful, we
-  # have no intention to analyse a program like
-  #
-  # return 3
-  # echo a + b
-  #
-  # any further than necessary.
   var w = @[0]
-  while w.len > 0:
-    var pc = w[^1]
+  var maxIters = 50
+  var someChange = true
+  var takenGotos = initIntSet()
+  var consuming = -1
+  while w.len > 0 and maxIters > 0: # and someChange:
+    dec maxIters
+    var pc = w.pop() # w[^1]
+    var prevPc = -1
     # this simulates a single linear control flow execution:
-    while true:
-      # according to the paper, it is better to shrink the working set here
-      # in this inner loop:
-      let widx = w.find(pc)
-      if widx >= 0: w.del(widx)
+    while pc < code.len:
+      if prevPc >= 0:
+        someChange = false
+        # merge step and test for changes (we compute the fixpoints here):
+        # 'u' needs to be the union of prevPc, pc
+        # 'd' needs to be the intersection of 'pc'
+        for id in u[prevPc]:
+          if not u[pc].containsOrIncl(id):
+            someChange = true
+        # in (a; b) if ``a`` sets ``v`` so does ``b``. The intersection
+        # is only interesting on merge points:
+        for id in d[prevPc]:
+          if not d[pc].containsOrIncl(id):
+            someChange = true
+        # if this is a merge point, we take the intersection of the 'd' sets:
+        if backrefs.hasKey(pc):
+          var intersect = initIntSet()
+          assign(intersect, d[pc])
+          var first = true
+          for prevPc in backrefs.allValues(pc):
+            for def in d[pc]:
+              if def notin d[prevPc]:
+                excl(intersect, def)
+                someChange = true
+                when defined(debugDfa):
+                  echo "Excluding ", pc, " prev ", prevPc
+          assign d[pc], intersect
+      if consuming >= 0:
+        if not c[pc].containsOrIncl(consuming):
+          someChange = true
+        consuming = -1
+
       # our interpretation ![I!]:
-      var sid = -1
+      prevPc = pc
       case code[pc].kind
-      of goto, fork: discard
+      of goto:
+        # we must leave endless loops eventually:
+        if not takenGotos.containsOrIncl(pc) or someChange:
+          pc = pc + code[pc].dest
+        else:
+          inc pc
+      of fork:
+        # we follow the next instruction but push the dest onto our "work" stack:
+        #if someChange:
+        w.add pc + code[pc].dest
+        inc pc
       of use, useWithinCall:
-        let sym = code[pc].sym
-        if s[pc].contains(sym.id):
-          localError(code[pc].n.info, "variable read before initialized: " & sym.name.s)
-      of def:
-        sid = code[pc].sym.id
-
-      var pc2: int
-      if code[pc].kind == goto:
-        pc2 = pc + code[pc].dest
-      else:
-        pc2 = pc + 1
-        if code[pc].kind == fork:
-          let l = pc + code[pc].dest
-          if sid >= 0 and s[l].missingOrExcl(sid):
-            w.add l
-
-      if sid >= 0 and s[pc2].missingOrExcl(sid):
-        pc = pc2
-      else:
-        break
-      if pc >= code.len: break
-
-    when false:
-      case code[pc].kind
-      of use:
-        let s = code[pc].sym
-        if undefB.contains(s.id):
-          localError(code[pc].n.info, "variable read before initialized: " & s.name.s)
-          break
+        #if not d[prevPc].missingOrExcl():
+        # someChange = true
+        consuming = code[pc].sym.id
         inc pc
       of def:
-        let s = code[pc].sym
-        # exclude 'undef' for s for this path through the graph.
-        if not undefB.missingOrExcl(s.id):
-          inc pc
-        else:
-          break
-        #undefB.excl s.id
-        #inc pc
-        when false:
-          let prev = bindings.getOrDefault(s.id)
-          if prev != value:
-            # well now it has a value and we made progress, so
-            bindings[s.id] = value
-            inc pc
-          else:
-            break
-      of fork:
-        let diff = code[pc].dest
-        # we follow pc + 1 and remember the label for later:
-        w.add pc+diff
+        if not d[pc].containsOrIncl(code[pc].sym.id):
+          someChange = true
         inc pc
-      of goto:
-        let diff = code[pc].dest
-        pc = pc + diff
-      if pc >= code.len: break
+
+  when defined(useDfa) and defined(debugDfa):
+    for i in 0..<code.len:
+      echo "PC ", i, ": defs: ", d[i], "; uses ", u[i], "; consumes ", c[i]
+
+  # now check the condition we're interested in:
+  for i in 0..<code.len:
+    case code[i].kind
+    of use, useWithinCall:
+      let s = code[i].sym
+      if s.id notin d[i]:
+        localError(code[i].n.info, "usage of uninitialized variable: " & s.name.s)
+      if s.id in c[i]:
+        localError(code[i].n.info, "usage of an already consumed variable: " & s.name.s)
+
+    else: discard
 
 proc dataflowAnalysis*(s: PSym; body: PNode) =
   var c = Con(code: @[], blocks: @[])
   gen(c, body)
-  #echoCfg(c.code)
+  when defined(useDfa) and defined(debugDfa): echoCfg(c.code)
   dfa(c.code)
 
 proc constructCfg*(s: PSym; body: PNode): ControlFlowGraph =