From 301e5838ecc154b9bdf7067da8f7b8d723ce4504 Mon Sep 17 00:00:00 2001
From: Clyybber <darkmine956@gmail.com>
Date: Sun, 24 Jan 2021 21:01:41 +0100
Subject: Finer analysis for array access (#16787)

* Refine the analysis for array access
* Cleanup
* Add comments
---
 compiler/dfa.nim | 100 ++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 73 insertions(+), 27 deletions(-)

(limited to 'compiler/dfa.nim')

diff --git a/compiler/dfa.nim b/compiler/dfa.nim
index efd826594..f3985822b 100644
--- a/compiler/dfa.nim
+++ b/compiler/dfa.nim
@@ -574,32 +574,84 @@ proc skipConvDfa*(n: PNode): PNode =
       result = result[1]
     else: break
 
-proc aliases*(obj, field: PNode): bool =
-  var n = field
-  var obj = obj
-  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:
-      n = n[0]
-    of PathKinds1:
-      n = n[1]
-    else: break
+type AliasKind* = enum
+  yes, no, maybe
+
+proc aliases*(obj, field: PNode): AliasKind =
+  # obj -> field:
+  # x -> x: true
+  # x -> x.f: true
+  # x.f -> x: false
+  # x.f -> x.f: true
+  # x.f -> x.v: false
+  # x -> x[0]: true
+  # x[0] -> x: false
+  # x[0] -> x[0]: true
+  # x[0] -> x[1]: false
+  # x -> x[i]: true
+  # x[i] -> x: false
+  # x[i] -> x[i]: maybe; Further analysis could make this return true when i is a runtime-constant
+  # x[i] -> x[j]: maybe; also returns maybe if only one of i or j is a compiletime-constant
+  template collectImportantNodes(result, n) =
+    var result: seq[PNode]
+    var n = n
+    while true:
+      case n.kind
+      of PathKinds0 - {nkDotExpr, nkCheckedFieldExpr, nkBracketExpr}:
+        n = n[0]
+      of PathKinds1:
+        n = n[1]
+      of nkDotExpr, nkCheckedFieldExpr, nkBracketExpr:
+        result.add n
+        n = n[0]
+      of nkSym:
+        result.add n; break
+      else: return no
+
+  collectImportantNodes(objImportantNodes, obj)
+  collectImportantNodes(fieldImportantNodes, field)
+
+  # If field is less nested than obj, then it cannot be part of/aliased by obj
+  if fieldImportantNodes.len < objImportantNodes.len: return no
+
+  result = yes
+  for i in 1..objImportantNodes.len:
+    # We compare the nodes leading to the location of obj and field
+    # with each other.
+    # We continue until they diverge, in which case we return no, or
+    # until we reach the location of obj, in which case we do not need
+    # to look further, since field must be part of/aliased by obj now.
+    # If we encounter an element access using an index which is a runtime value,
+    # we simply return maybe instead of yes; should further nodes not diverge.
+    let currFieldPath = fieldImportantNodes[^i]
+    let currObjPath = objImportantNodes[^i]
+
+    if currFieldPath.kind != currObjPath.kind:
+      return no
+
+    case currFieldPath.kind
+    of nkSym:
+      if currFieldPath.sym != currObjPath.sym: return no
+    of nkDotExpr, nkCheckedFieldExpr:
+      if currFieldPath[1].sym != currObjPath[1].sym: return no
+    of nkBracketExpr:
+      if currFieldPath[1].kind in nkLiterals and currObjPath[1].kind in nkLiterals:
+        if currFieldPath[1].intVal != currObjPath[1].intVal:
+          return no
+      else:
+        result = maybe
+    else: assert false # unreachable
 
 type InstrTargetKind* = enum
   None, Full, Partial
 
 proc instrTargets*(insloc, loc: PNode): InstrTargetKind =
-  if sameTrees(insloc, loc) or insloc.aliases(loc):
+  case insloc.aliases(loc)
+  of yes:
     Full    # x -> x; x -> x.f
-  elif loc.aliases(insloc):
+  of maybe:
+    Partial # We treat this like a partial write/read
+  elif loc.aliases(insloc) != no:
     Partial # x.f -> x
   else: None
 
@@ -607,16 +659,10 @@ proc isAnalysableFieldAccess*(orig: PNode; owner: PSym): bool =
   var n = orig
   while true:
     case n.kind
-    of PathKinds0 - {nkBracketExpr, nkHiddenDeref, nkDerefExpr}:
+    of PathKinds0 - {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}:
-        n = n[0]
-      else:
-        return false
     of nkHiddenDeref, nkDerefExpr:
       # We "own" sinkparam[].loc but not ourVar[].location as it is a nasty
       # pointer indirection.
-- 
cgit 1.4.1-2-gfad0