contrib/pep8analysis/src/flow_analysis/range_analysis.nit

   1 module range_analysis
   2
   3 import framework
   4
   5 # for linex, and should be used in the future
   6 import reaching_defs
   7
   8 redef class AnalysisManager
   9         fun do_range_analysis(ast: AListing, cfg: CFG)
  10         do
  11                 var range_init_analysis = new InitRangeAnalysis(ast)
  12                 range_init_analysis.analyze(ast)
  13
  14                 cfg.start.backup_ranges_out = range_init_analysis.set
  15
  16                 var range_analysis = new RangeAnalysis
  17                 range_analysis.analyze(cfg)
  18         end
  19 end
  20
  21 class RangeAnalysis
  22         super FineFlowAnalysis[RangeMap]
  23
  24         var current_range: nullable ValRange = null
  25         var current_var: nullable Var = null
  26
  27         redef fun empty_set do return new RangeMap
  28         redef fun is_forward do return true
  29
  30         init do super
  31
  32         redef fun visit(node)
  33         do
  34                 node.accept_range_analysis(self,
  35                         current_in, current_out.as(not null))
  36         end
  37
  38         # union
  39         redef fun merge(a, b)
  40         do
  41                 if a == null and b == null then return null
  42                 if a == null then return b.copy
  43                 if b == null then return a.copy
  44
  45                 var n = new RangeMap
  46                 for k, v in a do
  47                         if b.has_key(k) then
  48                                 # merge ranges
  49                                 var u = b[k]
  50                                 n[k] = new ValRange(v.min.min(u.min), v.max.max(u.max))
  51                         end
  52                 end
  53
  54                 return n
  55         end
  56
  57         redef fun line_in(line) do return line.ranges_in
  58         redef fun line_out(line) do return line.ranges_out
  59         redef fun line_in=(line, s) do line.ranges_in = s
  60         redef fun line_out=(line, s) do line.ranges_out = s
  61
  62         redef fun backup_in(bb) do return bb.backup_ranges_in
  63         redef fun backup_out(bb) do return bb.backup_ranges_out
  64         redef fun backup_in=(bb, s) do bb.backup_ranges_in = s
  65         redef fun backup_out=(bb, s) do bb.backup_ranges_out = s
  66 end
  67
  68 class InitRangeAnalysis
  69         super StaticAnalysis[RangeMap]
  70
  71         var current_line: ALine
  72
  73         init(prog: AListing)
  74         do
  75                 super( new RangeMap )
  76                 current_line = prog.n_lines.first
  77         end
  78         redef fun visit(node)
  79         do
  80                 if node isa ALine then current_line = node
  81                 node.accept_init_range_analysis(self, set)
  82         end
  83 end
  84
  85 redef class ALine
  86         var ranges_in: nullable RangeMap = null
  87         var ranges_out: nullable RangeMap = null
  88 end
  89
  90 redef class BasicBlock
  91         var backup_ranges_in: nullable RangeMap = null
  92         var backup_ranges_out: nullable RangeMap = null
  93
  94         redef fun dot_node_header
  95         do
  96                 if backup_ranges_in != null then
  97                         return "{super}-- ranges in = {backup_ranges_in.as(not null)}\\l"
  98                 else if not lines.is_empty and lines.first.ranges_in != null then
  99                         return "{super}-- ranges in = {lines.first.ranges_in.as(not null)}\\l"
 100                 else return super
 101         end
 102         redef fun dot_node_footer
 103         do
 104                 if backup_ranges_out != null then
 105                         return "{super}-- ranges out = {backup_ranges_out.as(not null)}\\l"
 106                 else if not lines.is_empty and lines.last.ranges_out != null then
 107                         return "{super}-- ranges out = {lines.last.ranges_out.as(not null)}\\l"
 108                 else return super
 109         end
 110 end
 111
 112 class ValRange
 113         var min: Int
 114         var max: Int
 115         init(min, max: Int)
 116         do
 117                 self.min = min
 118                 self.max = max
 119         end
 120         init from(o: ValRange)
 121         do
 122                 self.min = o.min
 123                 self.max = o.max
 124         end
 125         init at(v: Int)
 126         do
 127                 self.min = v
 128                 self.max = v
 129         end
 130
 131         redef fun to_s do
 132                 if min == max then return min.to_s
 133                 return "[{min}..{max}]"
 134         end
 135
 136         redef fun ==(o) do return o != null and o isa ValRange and
 137                 min == o.min and max == o.max
 138
 139         fun ponctual: Bool do return min == max
 140 end
 141 class RangeMap
 142         super HashMap[Var, ValRange]
 143         redef fun ==(o)
 144         do
 145                 if o == null or not o isa RangeMap then return false
 146                 if o.length != length then return false
 147
 148                 for k, v in self do if not o.has_key(k) or o[k] != v then return false
 149
 150                 return true
 151         end
 152
 153         fun copy: RangeMap
 154         do
 155                 var c = new RangeMap
 156                 c.recover_with(self)
 157                 return c
 158         end
 159
 160         redef fun to_s do return "\{{join(", ", ":")}\}"
 161 end
 162
 163 redef class ANode
 164         fun accept_range_analysis(v: RangeAnalysis,
 165                 ins: nullable RangeMap, outs: RangeMap) do visit_all(v)
 166         fun accept_init_range_analysis(v: InitRangeAnalysis,
 167                 set: RangeMap) do visit_all(v)
 168 end
 169
 170 redef class AInstruction
 171         redef fun accept_range_analysis(v, ins, outs)
 172         do
 173                 visit_all(v)
 174                 if ins != null then outs.recover_with(ins)
 175         end
 176 end
 177
 178 redef class ALoadInstruction
 179         redef fun accept_range_analysis(v, ins, outs)
 180         do
 181                 visit_all(v)
 182
 183                 if ins != null then outs.recover_with(ins)
 184                 var variable = def_var
 185                 #var add = new RangeMap[Var, ValRange](variable,
 186
 187                 # kill every set for variable
 188                 # (is automatic by HashMap)
 189
 190                 if variable != null then
 191                         # gen (&kill)
 192                         var cr = v.current_range
 193                         if cr != null then
 194                                 outs[variable] = cr
 195                         else
 196                                 outs.keys.remove(variable)
 197                         end
 198                 end
 199                 v.current_range = null
 200         end
 201 end
 202
 203 redef class AStoreInstruction
 204         redef fun accept_range_analysis(v, ins, outs)
 205         do
 206                 visit_all(v)
 207
 208                 if ins != null then outs.recover_with(ins)
 209                 var src = src_var # reg
 210                 var def = def_var # mem
 211
 212                 if def != null then
 213                         if src != null and ins != null and ins.has_key(src) then # we know the source and dest
 214                                 var cr = ins[src]
 215                                 outs[def] = cr
 216                         else
 217                                 outs.keys.remove(def)
 218                         end
 219                 end
 220         end
 221 end
 222
 223 redef class AInputInstruction
 224         redef fun accept_range_analysis(v, ins, outs)
 225         do
 226                 visit_all(v)
 227
 228                 if ins != null then outs.recover_with(ins)
 229
 230                 var def = def_var # mem
 231
 232                 if def != null and outs.has_key(def) then
 233                         outs.keys.remove(def)
 234                 end
 235
 236         end
 237 end
 238
 239 redef class AArithmeticInstruction
 240         fun do_arithmetic(rv, rm: ValRange): nullable ValRange do return null
 241
 242         redef fun accept_range_analysis(v, ins, outs)
 243         do
 244                 v.current_range = null
 245                 visit_all(v)
 246
 247                 if ins != null then outs.recover_with(ins)
 248
 249                 var reg = reg_var
 250
 251                 var cr = v.current_range
 252
 253                 if cr != null and ins.has_key(reg) then
 254                 # and ins.has_key(mem) then
 255                         var r = do_arithmetic(ins[reg], cr)
 256
 257                         if r != null then
 258                                 # this prevents infinite loops
 259                                 # we assume that the max for a student program in 50
 260                                 if r.max > 50 then r.max = 50
 261                                 if r.min < -50 then r.min = -50
 262
 263                                 outs[reg] = r
 264                         else
 265                                 outs.keys.remove(reg)
 266                         end
 267                 else
 268                         outs.keys.remove(reg)
 269                 end
 270         end
 271 end
 272
 273 redef class AAddInstruction
 274         redef fun do_arithmetic(rv, rm) do return new ValRange(rv.min+rm.min, rv.max+rm.max)
 275 end
 276
 277 redef class ASubInstruction
 278         redef fun do_arithmetic(rv, rm) do return new ValRange(rv.min-rm.max, rv.max-rm.min)
 279 end
 280
 281 redef class ANegInstruction
 282         redef fun accept_range_analysis(v, ins, outs)
 283         do
 284                 v.current_range = null
 285                 visit_all(v)
 286
 287                 if ins != null then outs.recover_with(ins)
 288
 289                 var reg = reg_var
 290                 if ins.has_key(reg) then
 291                         var rm = ins[reg]
 292                         outs[reg] = new ValRange(-rm.max, -rm.min)
 293                 end
 294         end
 295 end
 296
 297 redef class AAnyOperand
 298         redef fun accept_range_analysis(v, ins, outs)
 299         do
 300                 if addressing_mode == "i" then # immediate
 301                         v.current_var = null
 302                         v.current_range = new ValRange(n_value.to_i, n_value.to_i)
 303                         return
 304                 else if addressing_mode == "d" then # direct
 305                         var ci = v.current_in
 306                         var address = n_value.to_i
 307                         var variable = new MemVar(address)
 308                         v.current_var = variable
 309                         if ci != null and ci.has_key(variable) then
 310                                 var value = ci[variable]
 311                                 v.current_range = new ValRange(value.min, value.max)
 312                                 return
 313                         end
 314                 end
 315
 316                 v.current_range = null
 317         end
 318 end
 319
 320 redef class AMovInstruction
 321         # Almost impossible to guess so, topped
 322         redef fun accept_range_analysis(v, ins, outs)
 323         do
 324                 v.current_range = null
 325                 visit_all(v)
 326
 327                 if ins != null then outs.recover_with(ins)
 328
 329                 var reg = new RegisterVar('A')
 330                 if outs.has_key(reg) then
 331                         outs.keys.remove(reg)
 332                 end
 333         end
 334 end
 335
 336 redef class AWordDirective
 337         redef fun accept_init_range_analysis(v, set)
 338         do
 339                 var variable = new MemVar(v.current_line.address)
 340                 var value = new ValRange.at(n_value.to_i)
 341                 set[variable] = value
 342         end
 343 end
 344
 345 redef class AByteDirective
 346         redef fun accept_init_range_analysis(v, set)
 347         do
 348                 var variable = new MemVar(v.current_line.address)
 349                 var value = new ValRange.at(n_value.to_i)
 350                 set[variable] = value
 351         end
 352 end