From c2d91771bc1593fc8432392a75223dc1106bcfa3 Mon Sep 17 00:00:00 2001
From: Andreas Rumpf <rumpf_a@web.de>
Date: Thu, 21 Dec 2017 19:05:23 +0100
Subject: DFA works for simple examples

---
 compiler/dfa.nim | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)

(limited to 'compiler/dfa.nim')

diff --git a/compiler/dfa.nim b/compiler/dfa.nim
index 66a71e839..6bb7a03a9 100644
--- a/compiler/dfa.nim
+++ b/compiler/dfa.nim
@@ -344,20 +344,20 @@ proc dfa(code: seq[Instr]) =
     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:
+    of fork, goto:
       let d = i+code[i].dest
       backrefs.add(d, i)
-    of goto: discard
 
   var w = @[0]
   var maxIters = 50
   var someChange = true
-  while w.len > 0 and maxIters > 0 and someChange:
+  var takenGotos = initIntSet()
+  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 pc < code.len and someChange:
+    while pc < code.len:
       # according to the paper, it is better to shrink the working set here
       # in this inner loop:
       #let widx = w.find(pc)
@@ -386,17 +386,21 @@ proc dfa(code: seq[Instr]) =
               if def notin d[prevPc]:
                 excl(intersect, def)
                 someChange = true
+                when defined(debugDfa):
+                  echo "Excluding ", pc, " prev ", prevPc
           assign d[pc], intersect
 
       # our interpretation ![I!]:
       prevPc = pc
+      when defined(debugDfa):
+        echo "looking at ", pc
       case code[pc].kind
       of goto:
         # we must leave endless loops eventually:
-        #if someChange:
-        pc = pc + code[pc].dest
-        #else:
-        #  inc pc
+        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:
@@ -405,6 +409,10 @@ proc dfa(code: seq[Instr]) =
       of use, useWithinCall, def:
         inc pc
 
+  when defined(useDfa) and defined(debugDfa):
+    for i in 0..<code.len:
+      echo "PC ", i, ": defs: ", d[i], "; uses ", u[i]
+
   # now check the condition we're interested in:
   for i in 0..<code.len:
     case code[i].kind
@@ -508,7 +516,7 @@ proc dfaUnused(code: seq[Instr]) =
 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 =
-- 
cgit 1.4.1-2-gfad0