summary refs log tree commit diff stats
path: root/compiler/renderer.nim
diff options
context:
space:
mode:
authorAraq <rumpf_a@web.de>2012-11-11 22:05:04 +0100
committerAraq <rumpf_a@web.de>2012-11-11 22:05:04 +0100
commit7ba0a7e324e41a9817dfd39022263f56763682b8 (patch)
tree66b7e80a87ec05ebd3cc9223c0830426ed19d53a /compiler/renderer.nim
parent48a62af3b13015cc7eda194b9f6ec7e194456e74 (diff)
parent1b691d87479880c9a7fad9696e92dccb600d5f96 (diff)
downloadNim-7ba0a7e324e41a9817dfd39022263f56763682b8.tar.gz
Merge branch 'master' of github.com:Araq/Nimrod
Diffstat (limited to 'compiler/renderer.nim')
0 files changed, 0 insertions, 0 deletions
href='#n119'>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
#
#
#           The Nimrod 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 TIntSet): TAnalysisResult

proc isPartOfAux(n: PNode, b: PType, marker: var TIntSet): 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: internalError("isPartOfAux(record case branch)")
  of nkSym:
    result = isPartOfAux(n.sym.typ, b, marker)
  else: internalError(n.info, "isPartOfAux()")
  
proc isPartOfAux(a, b: PType, marker: var TIntSet): 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: 
    result = isPartOfAux(a.sons[0], b, marker)
    if result == arNo: result = isPartOfAux(a.n, b, marker)
  of tyGenericInst, tyDistinct:
    result = isPartOfAux(lastSon(a), b, marker)
  of tyArray, tyArrayConstr, tySet, tyTuple: 
    for i in countup(0, sonsLen(a) - 1): 
      result = isPartOfAux(a.sons[i], b, marker)
      if result == arYes: return 
  else: nil

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}
      # 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: nil
    # 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}
      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: nil
    else: nil