DFA and injectdestructors cleanup (#14824)

* DFA and injectdestructors cleanup

* More precise write analysis

* Cleanup obsoleted path

* Unify defInstrTargets and useInstrTargets

* Misc cleanups

* Nicer CFG printing

* Misc cleanups 2

2 files changed, 118 insertions, 157 deletions

diff --git a/compiler/dfa.nim b/compiler/dfa.nim
index c393b2c81..2254cd0ff 100644
--- a/compiler/dfa.nim
+++ b/compiler/dfa.nim
@@ -29,7 +29,7 @@
 ## "A Graph–Free Approach to Data–Flow Analysis" by Markus Mohnen.
 ## https://link.springer.com/content/pdf/10.1007/3-540-45937-5_6.pdf
 
-import ast, types, intsets, lineinfos, renderer
+import ast, types, intsets, lineinfos, renderer, asciitables
 
 from patterns import sameTrees
 
@@ -57,14 +57,11 @@ type
 
   Con = object
     code: ControlFlowGraph
-    inCall, inTryStmt: int
+    inTryStmt: int
     blocks: seq[TBlock]
     owner: PSym
 
-proc debugInfo(info: TLineInfo): string =
-  result = $info.line #info.toFilename & ":" & $info.line
-
-proc codeListing(c: ControlFlowGraph, result: var string, start=0; last = -1) =
+proc codeListing(c: ControlFlowGraph, start = 0; last = -1): string =
   # for debugging purposes
   # first iteration: compute all necessary labels:
   var jumpTargets = initIntSet()
@@ -85,17 +82,14 @@ proc codeListing(c: ControlFlowGraph, result: var string, start=0; last = -1) =
       result.add "L"
       result.addInt c[i].dest+i
     result.add("\t#")
-    result.add(debugInfo(c[i].n.info))
+    result.add($c[i].n.info.line)
     result.add("\n")
     inc i
   if i in jumpTargets: result.add("L" & $i & ": End\n")
-  # consider calling `asciitables.alignTable`
 
-proc echoCfg*(c: ControlFlowGraph; start=0; last = -1) {.deprecated.} =
+proc echoCfg*(c: ControlFlowGraph; start = 0; last = -1) {.deprecated.} =
   ## echos the ControlFlowGraph for debugging purposes.
-  var buf = ""
-  codeListing(c, buf, start, last)
-  echo buf
+  echo codeListing(c, start, last).alignTable
 
 proc forkI(c: var Con; n: PNode): TPosition =
   result = TPosition(c.code.len)
@@ -273,22 +267,20 @@ duplicate the 'join' instructions on breaks and return exits!
 
 ]#
 
-proc genLabel(c: Con): TPosition =
-  result = TPosition(c.code.len)
+proc genLabel(c: Con): TPosition = TPosition(c.code.len)
+
+template checkedDistance(dist): int =
+  doAssert low(int) div 2 + 1 < dist and dist < high(int) div 2
+  dist
 
 proc jmpBack(c: var Con, n: PNode, p = TPosition(0)) =
-  let dist = p.int - c.code.len
-  doAssert(low(int) div 2 + 1 < dist and dist < high(int) div 2)
-  c.code.add Instr(n: n, kind: goto, dest: dist)
+  c.code.add Instr(n: n, kind: goto, dest: checkedDistance(p.int - c.code.len))
 
 proc patch(c: var Con, p: TPosition) =
   # patch with current index
-  let p = p.int
-  let diff = c.code.len - p
-  doAssert(low(int) div 2 + 1 < diff and diff < high(int) div 2)
-  c.code[p].dest = diff
+  c.code[p.int].dest = checkedDistance(c.code.len - p.int)
 
-proc gen(c: var Con; n: PNode) # {.noSideEffect.}
+func gen(c: var Con; n: PNode)
 
 proc popBlock(c: var Con; oldLen: int) =
   var exits: seq[TPosition]
@@ -302,8 +294,8 @@ proc popBlock(c: var Con; oldLen: int) =
     c.patch e
   c.blocks.setLen(oldLen)
 
-template withBlock(labl: PSym; body: untyped) {.dirty.} =
-  var oldLen {.gensym.} = c.blocks.len
+template withBlock(labl: PSym; body: untyped) =
+  let oldLen = c.blocks.len
   c.blocks.add TBlock(isTryBlock: false, label: labl)
   body
   popBlock(c, oldLen)
@@ -366,11 +358,9 @@ when true:
           endings[i] = c.forkI(n)
           c.gen(n[1])
         for i in countdown(endings.high, 0):
-          let endPos = endings[i]
-          c.patch(endPos)
+          c.patch(endings[i])
 
 else:
-
   proc genWhile(c: var Con; n: PNode) =
     # lab1:
     #   cond, tmp
@@ -385,10 +375,9 @@ else:
         c.jmpBack(n, lab1)
       else:
         c.gen(n[0])
-        let lab2 = c.forkI(n)
-        c.gen(n[1])
-        c.jmpBack(n, lab1)
-        c.patch(lab2)
+        forkT(n):
+          c.gen(n[1])
+          c.jmpBack(n, lab1)
 
 template forkT(n, body) =
   let lab1 = c.forkI(n)
@@ -434,16 +423,14 @@ proc genIf(c: var Con, n: PNode) =
   ]#
   var endings: seq[TPosition] = @[]
   for i in 0..<n.len:
-    var it = n[i]
+    let it = n[i]
     c.gen(it[0])
     if it.len == 2:
-      let elsePos = forkI(c, it[1])
-      c.gen(it[1])
-      endings.add(c.gotoI(it[1]))
-      c.patch(elsePos)
+      forkT(it[1]):
+        c.gen(it[1])
+        endings.add c.gotoI(it[1])
   for i in countdown(endings.high, 0):
-    let endPos = endings[i]
-    c.patch(endPos)
+    c.patch(endings[i])
 
 proc genAndOr(c: var Con; n: PNode) =
   #   asgn dest, a
@@ -473,16 +460,13 @@ proc genCase(c: var Con; n: PNode) =
   c.gen(n[0])
   for i in 1..<n.len:
     let it = n[i]
-    if it.len == 1:
-      c.gen(it[0])
-    elif i == n.len-1 and isExhaustive:
+    if it.len == 1 or (i == n.len-1 and isExhaustive):
       # treat the last branch as 'else' if this is an exhaustive case statement.
       c.gen(it.lastSon)
     else:
-      let elsePos = c.forkI(it.lastSon)
-      c.gen(it.lastSon)
-      endings.add(c.gotoI(it.lastSon))
-      c.patch(elsePos)
+      forkT(it.lastSon):
+        c.gen(it.lastSon)
+        endings.add c.gotoI(it.lastSon)
   for i in countdown(endings.high, 0):
     let endPos = endings[i]
     c.patch(endPos)
@@ -506,7 +490,6 @@ proc genBreakOrRaiseAux(c: var Con, i: int, n: PNode) =
 
 proc genBreak(c: var Con; n: PNode) =
   if n[0].kind == nkSym:
-    #echo cast[int](n[0].sym)
     for i in countdown(c.blocks.high, 0):
       if not c.blocks[i].isTryBlock and c.blocks[i].label == n[0].sym:
         genBreakOrRaiseAux(c, i, n)
@@ -525,7 +508,6 @@ proc genTry(c: var Con; n: PNode) =
   c.blocks.add TBlock(isTryBlock: true, finale: if n[^1].kind == nkFinally: n[^1] else: newNode(nkEmpty))
 
   inc c.inTryStmt
-  #let elsePos = c.forkI(n)
   c.gen(n[0])
   dec c.inTryStmt
 
@@ -534,20 +516,14 @@ proc genTry(c: var Con; n: PNode) =
 
   c.blocks.setLen oldLen
 
-  #c.patch(elsePos)
   for i in 1..<n.len:
     let it = n[i]
     if it.kind != nkFinally:
-      let endExcept = c.forkI(it)
-      c.gen(it.lastSon)
-      endings.add(c.gotoI(it))
-      c.patch(endExcept)
+      forkT(it):
+        c.gen(it.lastSon)
+        endings.add c.gotoI(it)
   for i in countdown(endings.high, 0):
-    let endPos = endings[i]
-    c.patch(endPos)
-
-  # join the 'elsePos' forkI instruction:
-  #c.joinI(c.blocks[^1].forks.pop(), n)
+    c.patch(endings[i])
 
   let fin = lastSon(n)
   if fin.kind == nkFinally:
@@ -597,59 +573,43 @@ proc skipConvDfa*(n: PNode): PNode =
       result = result[1]
     else: break
 
-proc genUse(c: var Con; orig: PNode) =
-  var n = orig
-  while true:
-    case n.kind
-    of PathKinds0 - {nkBracketExpr}:
-      n = n[0]
-    of nkBracketExpr:
-      gen(c, n[1])
-      n = n[0]
-    of PathKinds1:
-      n = n[1]
-    else: break
-    if n.kind in nkCallKinds:
-      gen(c, n)
-  if n.kind == nkSym and n.sym.kind in InterestingSyms:
-    c.code.add Instr(n: orig, kind: use)
-
 proc aliases*(obj, field: PNode): bool =
   var n = field
   var obj = obj
-  while obj.kind in {nkHiddenSubConv, nkHiddenStdConv, nkObjDownConv, nkObjUpConv,
-                     nkAddr, nkHiddenAddr, nkDerefExpr, nkHiddenDeref}:
-    obj = obj[0]
+  while true:
+    case obj.kind
+    of {nkObjDownConv, nkObjUpConv, nkAddr, nkHiddenAddr, nkDerefExpr, nkHiddenDeref}:
+      obj = obj[0]
+    of PathKinds1:
+      obj = obj[1]
+    else: break
   while true:
     if sameTrees(obj, n): return true
     case n.kind
-    of PathKinds0, PathKinds1:
+    of PathKinds0:
       n = n[0]
-    else:
-      break
-
-proc useInstrTargets*(ins: Instr; loc: PNode): bool =
-  assert ins.kind == use
-  result = sameTrees(ins.n, loc) or
-    ins.n.aliases(loc) or loc.aliases(ins.n)
-  # We can come here if loc is 'x.f' and ins.n is 'x' or the other way round.
-  # use x.f;  question: does it affect the full 'x'? No.
-  # use x; question does it affect 'x.f'? Yes.
-
-proc defInstrTargets*(ins: Instr; loc: PNode): bool =
-  assert ins.kind == def
-  result = sameTrees(ins.n, loc) or ins.n.aliases(loc)
-  # We can come here if loc is 'x.f' and ins.n is 'x' or the other way round.
-  # def x.f; question: does it affect the full 'x'? No.
-  # def x; question: does it affect the 'x.f'? Yes.
+    of PathKinds1:
+      n = n[1]
+    else: break
+
+type InstrTargetKind* = enum
+  None, Full, Partial
+
+proc instrTargets*(insloc, loc: PNode): InstrTargetKind =
+  if sameTrees(insloc, loc) or insloc.aliases(loc):
+    Full    # x -> x; x -> x.f
+  elif loc.aliases(insloc):
+    Partial # x.f -> x
+  else: None
 
 proc isAnalysableFieldAccess*(orig: PNode; owner: PSym): bool =
   var n = orig
   while true:
     case n.kind
-    of nkDotExpr, nkCheckedFieldExpr, nkHiddenSubConv, nkHiddenStdConv,
-       nkObjDownConv, nkObjUpConv, nkHiddenAddr, nkAddr:
+    of PathKinds0 - {nkBracketExpr, nkHiddenDeref, nkDerefExpr}:
       n = n[0]
+    of PathKinds1:
+      n = n[1]
     of nkBracketExpr:
       # in a[i] the 'i' must be known
       if n.len > 1 and n[1].kind in {nkCharLit..nkUInt64Lit}:
@@ -662,10 +622,9 @@ proc isAnalysableFieldAccess*(orig: PNode; owner: PSym): bool =
       # bug #14159, we cannot reason about sinkParam[].location as it can
       # still be shared for tyRef.
       n = n[0]
-      return n.kind == nkSym and n.sym.owner == owner and (
-          n.sym.typ.skipTypes(abstractInst-{tyOwned}).kind in {tyOwned})
-    else:
-      break
+      return n.kind == nkSym and n.sym.owner == owner and
+         (n.sym.typ.skipTypes(abstractInst-{tyOwned}).kind in {tyOwned})
+    else: break
   # XXX Allow closure deref operations here if we know
   # the owner controlled the closure allocation?
   result = n.kind == nkSym and n.sym.owner == owner and
@@ -682,36 +641,37 @@ proc isAnalysableFieldAccess*(orig: PNode; owner: PSym): bool =
   # free the old data and all is lost! Lesson: Don't be too smart, trust the
   # lower level C++ optimizer to specialize this code.
 
-proc genDef(c: var Con; n: PNode) =
-  var m = n
-  # XXX do something about this duplicated logic here.
+proc skipTrivials(c: var Con, n: PNode): PNode =
+  result = n
   while true:
-    case m.kind
-    of nkDotExpr, nkCheckedFieldExpr, nkHiddenSubConv, nkHiddenStdConv,
-        nkObjDownConv, nkObjUpConv, nkHiddenAddr, nkAddr:
-      m = m[0]
+    case result.kind
+    of PathKinds0 - {nkBracketExpr}:
+      result = result[0]
     of nkBracketExpr:
-      gen(c, m[1])
-      m = m[0]
-    of nkHiddenDeref, nkDerefExpr:
-      m = m[0]
-    else:
-      break
+      gen(c, result[1])
+      result = result[0]
+    of PathKinds1:
+      result = result[1]
+    else: break
+
+proc genUse(c: var Con; orig: PNode) =
+  let n = c.skipTrivials(orig)
 
   if n.kind == nkSym and n.sym.kind in InterestingSyms:
-    c.code.add Instr(n: n, kind: def)
-  elif isAnalysableFieldAccess(n, c.owner):
-    c.code.add Instr(n: n, kind: def)
-  else:
-    # bug #13314: An assignment to t5.w = -5 is a usage of 't5'
-    # we still need to gather the use information:
+    c.code.add Instr(n: orig, kind: use)
+  elif n.kind in nkCallKinds:
     gen(c, n)
 
+proc genDef(c: var Con; orig: PNode) =
+  let n = c.skipTrivials(orig)
+
+  if n.kind == nkSym and n.sym.kind in InterestingSyms:
+    c.code.add Instr(n: orig, kind: def)
+
 proc genCall(c: var Con; n: PNode) =
   gen(c, n[0])
   var t = n[0].typ
   if t != nil: t = t.skipTypes(abstractInst)
-  inc c.inCall
   for i in 1..<n.len:
     gen(c, n[i])
     when false:
@@ -725,13 +685,11 @@ proc genCall(c: var Con; n: PNode) =
     # goto exceptionHandler (except or finally)
     # lab1:
     # join F1
-    let endGoto = c.forkI(n)
-    for i in countdown(c.blocks.high, 0):
-      if c.blocks[i].isTryBlock:
-        genBreakOrRaiseAux(c, i, n)
-        break
-    c.patch(endGoto)
-  dec c.inCall
+    forkT(n):
+      for i in countdown(c.blocks.high, 0):
+        if c.blocks[i].isTryBlock:
+          genBreakOrRaiseAux(c, i, n)
+          break
 
 proc genMagic(c: var Con; n: PNode; m: TMagic) =
   case m
@@ -754,7 +712,7 @@ proc genVarSection(c: var Con; n: PNode) =
       if a.lastSon.kind != nkEmpty:
         genDef(c, a[0])
 
-proc gen(c: var Con; n: PNode) =
+func gen(c: var Con; n: PNode) =
   case n.kind
   of nkSym: genUse(c, n)
   of nkCallKinds:
@@ -775,7 +733,7 @@ proc gen(c: var Con; n: PNode) =
     # "uses" 'i'. But we are only talking about builtin array indexing so
     # it doesn't matter and 'x = 34' is NOT a usage of 'x'.
     genDef(c, n[0])
-  of PathKinds0 - {nkHiddenStdConv, nkHiddenSubConv, nkObjDownConv, nkObjUpConv}:
+  of PathKinds0 - {nkObjDownConv, nkObjUpConv}:
     genUse(c, n)
   of nkIfStmt, nkIfExpr: genIf(c, n)
   of nkWhenStmt:
@@ -792,13 +750,12 @@ proc gen(c: var Con; n: PNode) =
      nkBracket, nkCurly, nkPar, nkTupleConstr, nkClosure, nkObjConstr, nkYieldStmt:
     for x in n: gen(c, x)
   of nkPragmaBlock: gen(c, n.lastSon)
-  of nkDiscardStmt, nkObjDownConv, nkObjUpConv: gen(c, n[0])
-  of nkConv, nkExprColonExpr, nkExprEqExpr, nkCast, nkHiddenSubConv, nkHiddenStdConv:
+  of nkDiscardStmt, nkObjDownConv, nkObjUpConv, nkStringToCString, nkCStringToString:
+    gen(c, n[0])
+  of nkConv, nkExprColonExpr, nkExprEqExpr, nkCast, PathKinds1:
     gen(c, n[1])
-  of nkStringToCString, nkCStringToString: gen(c, n[0])
   of nkVarSection, nkLetSection: genVarSection(c, n)
-  of nkDefer:
-    doAssert false, "dfa construction pass requires the elimination of 'defer'"
+  of nkDefer: doAssert false, "dfa construction pass requires the elimination of 'defer'"
   else: discard
 
 proc constructCfg*(s: PSym; body: PNode): ControlFlowGraph =
diff --git a/compiler/injectdestructors.nim b/compiler/injectdestructors.nim
index d5eca7475..a2669be99 100644
--- a/compiler/injectdestructors.nim
+++ b/compiler/injectdestructors.nim
@@ -65,40 +65,43 @@ template dbg(body) =
 proc p(n: PNode; c: var Con; mode: ProcessMode): PNode
 proc moveOrCopy(dest, ri: PNode; c: var Con, isDecl = false): PNode
 
-proc isLastRead(location: PNode; c: var Con; pc, until: int): int =
+proc isLastRead(location: PNode; cfg: ControlFlowGraph; otherRead: var PNode; pc, until: int): int =
   var pc = pc
-  while pc < c.g.len and pc < until:
-    case c.g[pc].kind
+  while pc < cfg.len and pc < until:
+    case cfg[pc].kind
     of def:
-      if defInstrTargets(c.g[pc], location):
+      if instrTargets(cfg[pc].n, location) == Full:
         # the path leads to a redefinition of 's' --> abandon it.
         return high(int)
+      elif instrTargets(cfg[pc].n, location) == Partial:
+        # only partially writes to 's' --> can't sink 's', so this def reads 's'
+        otherRead = cfg[pc].n
+        return -1
       inc pc
     of use:
-      if useInstrTargets(c.g[pc], location):
-        c.otherRead = c.g[pc].n
+      if instrTargets(cfg[pc].n, location) != None:
+        otherRead = cfg[pc].n
         return -1
       inc pc
     of goto:
-      pc = pc + c.g[pc].dest
+      pc = pc + cfg[pc].dest
     of fork:
       # every branch must lead to the last read of the location:
       var variantA = pc + 1
-      var variantB = pc + c.g[pc].dest
+      var variantB = pc + cfg[pc].dest
       while variantA != variantB:
         if min(variantA, variantB) < 0: return -1
-        if max(variantA, variantB) >= c.g.len or min(variantA, variantB) >= until:
+        if max(variantA, variantB) >= cfg.len or min(variantA, variantB) >= until:
           break
         if variantA < variantB:
-          variantA = isLastRead(location, c, variantA, min(variantB, until))
+          variantA = isLastRead(location, cfg, otherRead, variantA, min(variantB, until))
         else:
-          variantB = isLastRead(location, c, variantB, min(variantA, until))
+          variantB = isLastRead(location, cfg, otherRead, variantB, min(variantA, until))
       pc = min(variantA, variantB)
   return pc
 
 proc isLastRead(n: PNode; c: var Con): bool =
   # first we need to search for the instruction that belongs to 'n':
-  c.otherRead = nil
   var instr = -1
   let m = dfa.skipConvDfa(n)
 
@@ -116,36 +119,37 @@ 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, int.high) >= 0
+  c.otherRead = nil
+  result = isLastRead(n, c.g, c.otherRead, instr+1, int.high) >= 0
   dbg: echo "ugh ", c.otherRead.isNil, " ", result
 
-proc isFirstWrite(location: PNode; c: var Con; pc, until: int): int =
+proc isFirstWrite(location: PNode; cfg: ControlFlowGraph; pc, until: int): int =
   var pc = pc
   while pc < until:
-    case c.g[pc].kind
+    case cfg[pc].kind
     of def:
-      if defInstrTargets(c.g[pc], location):
+      if instrTargets(cfg[pc].n, location) != None:
         # a definition of 's' before ours makes ours not the first write
         return -1
       inc pc
     of use:
-      if useInstrTargets(c.g[pc], location):
+      if instrTargets(cfg[pc].n, location) != None:
         return -1
       inc pc
     of goto:
-      pc = pc + c.g[pc].dest
+      pc = pc + cfg[pc].dest
     of fork:
       # every branch must not contain a def/use of our location:
       var variantA = pc + 1
-      var variantB = pc + c.g[pc].dest
+      var variantB = pc + cfg[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))
+          variantA = isFirstWrite(location, cfg, variantA, min(variantB, until))
         else:
-          variantB = isFirstWrite(location, c, variantB, min(variantA, until))
+          variantB = isFirstWrite(location, cfg, variantB, min(variantA, until))
       pc = min(variantA, variantB)
   return pc
 
@@ -165,7 +169,7 @@ 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, instr) >= 0
+  result = isFirstWrite(n, c.g, 0, instr) >= 0
 
 proc initialized(code: ControlFlowGraph; pc: int,
                  init, uninit: var IntSet; until: int): int =