contrib/pep8analysis/src/flow_analysis/reaching_defs.nit

   1 module reaching_defs
   2
   3 import framework
   4
   5 redef class AnalysisManager
   6         fun do_reaching_defs_analysis(cfg: CFG)
   7         do
   8                 cfg.start.backup_reaching_defs_out = new ReachingDefsMap
   9                 var reaching_defs_analysis = new ReachingDefsAnalysis
  10                 reaching_defs_analysis.analyze(cfg)
  11         end
  12 end
  13
  14 class ReachingDefsAnalysis
  15         super FineFlowAnalysis[ReachingDefsMap]
  16
  17         redef fun is_forward do return true
  18
  19         redef fun visit( node )
  20         do
  21                 node.accept_reaching_defs_analysis( self, current_in, current_out.as(not null) )
  22         end
  23         redef fun merge(a,b)
  24         do
  25                 if a == null then return b
  26                 if b == null then return a
  27                 return a.union(b)
  28         end
  29
  30         redef fun backup_in(bb) do return bb.backup_reaching_defs_in
  31         redef fun backup_out(bb) do return bb.backup_reaching_defs_out
  32         redef fun backup_in=(bb, v) do bb.backup_reaching_defs_in = v
  33         redef fun backup_out=(bb, v) do bb.backup_reaching_defs_out = v
  34
  35         redef fun line_in(line) do return line.reaching_defs_in
  36         redef fun line_out(line) do return line.reaching_defs_out
  37         redef fun line_in=(line, v) do line.reaching_defs_in = v
  38         redef fun line_out=(line, v) do line.reaching_defs_out = v
  39
  40         redef fun default_in_set do return new ReachingDefsMap
  41         redef fun empty_set do return new ReachingDefsMap
  42 end
  43
  44 redef class ANode
  45         fun accept_reaching_defs_analysis(v: ReachingDefsAnalysis, ins: nullable ReachingDefsMap, outs: ReachingDefsMap) do visit_all(v)
  46 end
  47
  48 redef class AInstruction
  49         redef fun accept_reaching_defs_analysis(v, ins, outs)
  50         do
  51                 if ins != null then outs.add_all(ins)
  52         end
  53 end
  54
  55 redef class ALoadInstruction
  56         redef fun accept_reaching_defs_analysis(v, ins, outs)
  57         do
  58                 if ins != null then outs.add_all(ins)
  59
  60                 var variable = def_var
  61                 if variable != null then
  62                         # kill & gen
  63                         var set = new HashSet[ALine]
  64                         set.add(parent.as(ALine))
  65                         outs[variable] = set
  66                 else
  67                         # TODO top
  68                 end
  69         end
  70 end
  71
  72 redef class AStoreInstruction
  73         redef fun accept_reaching_defs_analysis(v, ins, outs)
  74         do
  75                 if ins != null then outs.add_all(ins)
  76
  77                 var variable = def_var
  78                 if variable != null then
  79                         # kill & gen
  80                         var set = new HashSet[ALine]
  81                         set.add(parent.as(ALine))
  82                         outs[variable] = set
  83                 else
  84                         # TODO top
  85                 end
  86         end
  87 end
  88
  89 class ReachingDefsMap
  90         super HashMap[Var,Set[ALine]]
  91
  92         fun union(o: ReachingDefsMap): ReachingDefsMap
  93         do
  94                 var n = new ReachingDefsMap
  95                 for k, v in self do
  96                         n[k] = new HashSet[ALine]
  97                         n[k].add_all(v)
  98                 end
  99                 for k, v in o do
 100                         if not n.has_key(k) then n[k] = new HashSet[ALine]
 101                         n[k].add_all(v)
 102                 end
 103                 return n
 104         end
 105
 106         fun intersection(o: ReachingDefsMap): ReachingDefsMap
 107         do
 108                 var n = new ReachingDefsMap
 109                 for k, v in self do if n.has_key(k) then n[k].add_all(v)
 110                 for k, v in o    do if n.has_key(k) then n[k].add_all(v)
 111                 return n
 112         end
 113
 114         redef fun to_s do return join(";", ":")
 115
 116         redef fun ==(o)
 117         do
 118                 if o != null and o isa ReachingDefsMap then
 119                         if length != o.length then return false
 120                         for k,v in self do
 121                                 if not o.has_key(k) then return false
 122                                 var ok = o[k]
 123                                 if v.length != ok.length then return false
 124                                 for l in v do if not ok.has(l) then return false
 125                         end
 126                         return true
 127                 else
 128                         return false
 129                 end
 130         end
 131 end
 132
 133 redef class ALine
 134         var reaching_defs_in: nullable ReachingDefsMap = null
 135         var reaching_defs_out: nullable ReachingDefsMap = null
 136 end
 137
 138 redef class BasicBlock
 139         var backup_reaching_defs_in: nullable ReachingDefsMap = null
 140         var backup_reaching_defs_out: nullable ReachingDefsMap = null
 141
 142         redef fun dot_node_header
 143         do
 144                 if lines.is_empty then
 145                         if backup_reaching_defs_in != null then
 146                                 return "{super}-- reaching defs in = \{{backup_reaching_defs_in.to_s}\}\\l"
 147                         end
 148                 else if lines.first.reaching_defs_in != null then return  "{super}-- reaching defs in = \{{lines.first.reaching_defs_in.to_s}\}\\l"
 149                 return super
 150         end
 151         redef fun dot_node_footer
 152         do
 153                 if lines.is_empty then
 154                         if backup_reaching_defs_out != null then
 155                                 return "{super}-- reaching defs out = \{{backup_reaching_defs_out.to_s}\}\\l"
 156                         end
 157                 else if lines.first.reaching_defs_out != null then return  "{super}-- reaching defs out = \{{lines.last.reaching_defs_out.to_s}\}\\l"
 158                 return super
 159         end
 160 end
 161
 162 # This is bad.
 163 redef class HashSet[E]
 164         redef fun to_s do return join(",")
 165 end