1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
|
#
#
# The Nim Compiler
# (c) Copyright 2012 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## Simple alias analysis for the HLO and the code generators.
import
ast, astalgo, types, trees, intsets, msgs
type
TAnalysisResult* = enum
arNo, arMaybe, arYes
proc isPartOfAux(a, b: PType, marker: var IntSet): TAnalysisResult
proc isPartOfAux(n: PNode, b: PType, marker: var IntSet): TAnalysisResult =
result = arNo
case n.kind
of nkRecList:
for i in countup(0, sonsLen(n) - 1):
result = isPartOfAux(n.sons[i], b, marker)
if result == arYes: return
of nkRecCase:
assert(n.sons[0].kind == nkSym)
result = isPartOfAux(n.sons[0], b, marker)
if result == arYes: return
for i in countup(1, sonsLen(n) - 1):
case n.sons[i].kind
of nkOfBranch, nkElse:
result = isPartOfAux(lastSon(n.sons[i]), b, marker)
if result == arYes: return
else: discard "isPartOfAux(record case branch)"
of nkSym:
result = isPartOfAux(n.sym.typ, b, marker)
else: discard
proc isPartOfAux(a, b: PType, marker: var IntSet): TAnalysisResult =
result = arNo
if a == nil or b == nil: return
if containsOrIncl(marker, a.id): return
if compareTypes(a, b, dcEqIgnoreDistinct): return arYes
case a.kind
of tyObject:
if a.sons[0] != nil:
result = isPartOfAux(a.sons[0].skipTypes(skipPtrs), b, marker)
if result == arNo: result = isPartOfAux(a.n, b, marker)
of tyGenericInst, tyDistinct, tyAlias, tySink:
result = isPartOfAux(lastSon(a), b, marker)
of tyArray, tySet, tyTuple:
for i in countup(0, sonsLen(a) - 1):
result = isPartOfAux(a.sons[i], b, marker)
if result == arYes: return
else: discard
proc isPartOf(a, b: PType): TAnalysisResult =
## checks iff 'a' can be part of 'b'. Iterates over VALUE types!
var marker = initIntSet()
# watch out: parameters reversed because I'm too lazy to change the code...
result = isPartOfAux(b, a, marker)
proc isPartOf*(a, b: PNode): TAnalysisResult =
## checks if location `a` can be part of location `b`. We treat seqs and
## strings as pointers because the code gen often just passes them as such.
##
## Note: `a` can only be part of `b`, if `a`'s type can be part of `b`'s
## type. Since however type analysis is more expensive, we perform it only
## if necessary.
##
## cases:
##
## YES-cases:
## x <| x # for general trees
## x[] <| x
## x[i] <| x
## x.f <| x
##
## NO-cases:
## x !<| y # depending on type and symbol kind
## x[constA] !<| x[constB]
## x.f !<| x.g
## x.f !<| y.f iff x !<= y
##
## MAYBE-cases:
##
## x[] ?<| y[] iff compatible type
##
##
## x[] ?<| y depending on type
##
if a.kind == b.kind:
case a.kind
of nkSym:
const varKinds = {skVar, skTemp, skProc, skFunc}
# same symbol: aliasing:
if a.sym.id == b.sym.id: result = arYes
elif a.sym.kind in varKinds or b.sym.kind in varKinds:
# actually, a param could alias a var but we know that cannot happen
# here. XXX make this more generic
result = arNo
else:
# use expensive type check:
if isPartOf(a.sym.typ, b.sym.typ) != arNo:
result = arMaybe
of nkBracketExpr:
result = isPartOf(a[0], b[0])
if len(a) >= 2 and len(b) >= 2:
# array accesses:
if result == arYes and isDeepConstExpr(a[1]) and isDeepConstExpr(b[1]):
# we know it's the same array and we have 2 constant indexes;
# if they are
var x = if a[1].kind == nkHiddenStdConv: a[1][1] else: a[1]
var y = if b[1].kind == nkHiddenStdConv: b[1][1] else: b[1]
if sameValue(x, y): result = arYes
else: result = arNo
# else: maybe and no are accurate
else:
# pointer derefs:
if result != arYes:
if isPartOf(a.typ, b.typ) != arNo: result = arMaybe
of nkDotExpr:
result = isPartOf(a[0], b[0])
if result != arNo:
# if the fields are different, it's not the same location
if a[1].sym.id != b[1].sym.id:
result = arNo
of nkHiddenDeref, nkDerefExpr:
result = isPartOf(a[0], b[0])
# weaken because of indirection:
if result != arYes:
if isPartOf(a.typ, b.typ) != arNo: result = arMaybe
of nkHiddenStdConv, nkHiddenSubConv, nkConv:
result = isPartOf(a[1], b[1])
of nkObjUpConv, nkObjDownConv, nkCheckedFieldExpr:
result = isPartOf(a[0], b[0])
else: discard
# Calls return a new location, so a default of ``arNo`` is fine.
else:
# go down recursively; this is quite demanding:
const
Ix0Kinds = {nkDotExpr, nkBracketExpr, nkObjUpConv, nkObjDownConv,
nkCheckedFieldExpr, nkHiddenAddr}
Ix1Kinds = {nkHiddenStdConv, nkHiddenSubConv, nkConv}
DerefKinds = {nkHiddenDeref, nkDerefExpr}
case b.kind
of Ix0Kinds:
# a* !<| b.f iff a* !<| b
result = isPartOf(a, b[0])
of DerefKinds:
# a* !<| b[] iff
if isPartOf(a.typ, b.typ) != arNo:
result = isPartOf(a, b[0])
if result == arNo: result = arMaybe
of Ix1Kinds:
# a* !<| T(b) iff a* !<| b
result = isPartOf(a, b[1])
of nkSym:
# b is an atom, so we have to check a:
case a.kind
of Ix0Kinds:
# a.f !<| b* iff a.f !<| b*
result = isPartOf(a[0], b)
of Ix1Kinds:
result = isPartOf(a[1], b)
of DerefKinds:
if isPartOf(a.typ, b.typ) != arNo:
result = isPartOf(a[0], b)
if result == arNo: result = arMaybe
else: discard
of nkObjConstr:
result = arNo
for i in 1..<b.len:
let res = isPartOf(a, b[i][1])
if res != arNo:
result = res
if res == arYes: break
else: discard
|