implemented reordering pass

2 files changed, 105 insertions, 1 deletions

diff --git a/compiler/passes.nim b/compiler/passes.nim
index 7966ee88d..d63a79692 100644
--- a/compiler/passes.nim
+++ b/compiler/passes.nim
@@ -13,7 +13,7 @@
 import
   strutils, options, ast, astalgo, llstream, msgs, platform, os,
   condsyms, idents, renderer, types, extccomp, math, magicsys, nversion,
-  nimsets, syntaxes, times, rodread, idgen, modulegraphs
+  nimsets, syntaxes, times, rodread, idgen, modulegraphs, reorder
 
 type
   TPassContext* = object of RootObj # the pass's context
@@ -210,6 +210,8 @@ proc processModule*(graph: ModuleGraph; module: PSym, stream: PLLStream,
             var n = parseTopLevelStmt(p)
             if n.kind == nkEmpty: break
             sl.add n
+          if isDefined"nimreorder":
+            sl = reorder sl
           discard processTopLevelStmt(sl, a)
           break
         elif not processTopLevelStmt(n, a): break
diff --git a/compiler/reorder.nim b/compiler/reorder.nim
new file mode 100644
index 000000000..215bc4112
--- /dev/null
+++ b/compiler/reorder.nim
@@ -0,0 +1,102 @@
+
+import intsets, tables, ast, idents, renderer
+
+const
+  nfTempMark = nfTransf
+  nfPermMark = nfNoRewrite
+
+proc accQuoted(n: PNode): PIdent =
+  var id = ""
+  for i in 0 .. <n.len:
+    let x = n[i]
+    case x.kind
+    of nkIdent: id.add(x.ident.s)
+    of nkSym: id.add(x.sym.name.s)
+    else: discard
+  result = getIdent(id)
+
+proc addDecl(n: PNode; declares: var IntSet) =
+  case n.kind
+  of nkPostfix: addDecl(n[1], declares)
+  of nkPragmaExpr: addDecl(n[0], declares)
+  of nkIdent:
+    declares.incl n.ident.id
+  of nkSym:
+    declares.incl n.sym.name.id
+  of nkAccQuoted:
+    declares.incl accQuoted(n).id
+  else: discard
+
+proc computeDeps(n: PNode, declares, uses: var IntSet; topLevel: bool) =
+  template deps(n) = computeDeps(n, declares, uses, false)
+  template decl(n) =
+    if topLevel: addDecl(n, declares)
+  case n.kind
+  of procDefs:
+    decl(n[0])
+    for i in 1..bodyPos: deps(n[i])
+  of nkLetSection, nkVarSection:
+    for a in n:
+      if a.kind in {nkIdentDefs, nkVarTuple}:
+        for j in countup(0, a.len-3): decl(a[j])
+        for j in a.len-2..a.len-1: deps(a[j])
+  of nkConstSection, nkTypeSection:
+    for a in n:
+      if a.len >= 3:
+        decl(a[0])
+        for i in 1..<a.len: deps(a[i])
+  of nkIdent: uses.incl n.ident.id
+  of nkSym: uses.incl n.sym.name.id
+  of nkAccQuoted: uses.incl accQuoted(n).id
+  of nkOpenSymChoice, nkClosedSymChoice:
+    uses.incl n.sons[0].sym.name.id
+  of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse:
+    for i in 0..<len(n): computeDeps(n[i], declares, uses, topLevel)
+  else:
+    for i in 0..<safeLen(n): deps(n[i])
+
+proc visit(i: int; all, res: PNode; deps: var seq[(IntSet, IntSet)]): bool =
+  let n = all[i]
+  if nfTempMark in n.flags:
+    # not a DAG!
+    return true
+  if nfPermMark notin n.flags:
+    incl n.flags, nfTempMark
+    var uses = deps[i][1]
+    for j in 0..<all.len:
+      if j != i:
+        let declares = deps[j][0]
+        for d in declares:
+          if uses.contains(d):
+            let oldLen = res.len
+            if visit(j, all, res, deps):
+              result = true
+              # rollback what we did, it turned out to be a dependency that caused
+              # trouble:
+              for k in oldLen..<res.len:
+                res.sons[k].flags = res.sons[k].flags - {nfPermMark, nfTempMark}
+              res.sons.setLen oldLen
+            break
+    n.flags = n.flags + {nfPermMark} - {nfTempMark}
+    res.add n
+
+proc reorder*(n: PNode): PNode =
+  result = newNodeI(nkStmtList, n.info)
+  var deps = newSeq[(IntSet, IntSet)](n.len)
+  for i in 0..<n.len:
+    deps[i][0] = initIntSet()
+    deps[i][1] = initIntSet()
+    computeDeps(n[i], deps[i][0], deps[i][1], true)
+
+  for i in 0 .. n.len-1:
+    discard visit(i, n, result, deps)
+  for i in 0..<result.len:
+    result.sons[i].flags = result.sons[i].flags - {nfTempMark, nfPermMark}
+  when false:
+    # reverse the result:
+    let L = result.len-1
+    for i in 0 .. result.len div 2:
+      result.sons[i].flags = result.sons[i].flags - {nfTempMark, nfPermMark}
+      result.sons[L - i].flags = result.sons[L - i].flags - {nfTempMark, nfPermMark}
+      swap(result.sons[i], result.sons[L - i])
+  echo result