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