src/saf/reaching_defs.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Analysis that determines which definitions may reach a given point in the code.
  16 import saf_base
  17
  18 import scope
  19
  20 # Determines wich variables definitions reach each statement.
  21 class ReachingDefsAnalysis
  22         super ForwardAnalysis
  23
  24         redef type FLOW: FlowHashSet[VarDef]
  25
  26         # New initial flows are empty (conservative analysis).
  27         redef fun new_initial_flow do return new FlowHashSet[VarDef]
  28
  29         # Perform set union (used for **some path** analysis).
  30         redef fun merge(s1, s2) do return s1.flow_union(s2)
  31
  32         redef fun visit(n) do n.accept_reaching_defs(self)
  33
  34         # Generate a new variable definition in the `current_outset`.
  35         fun gen(variable: Variable, location: Location) do
  36                 current_outset.add(new VarDef(variable, location))
  37         end
  38
  39         # Kill a variable definition in the `current_outset`.
  40         fun kill(variable: Variable) do
  41                 for vardef in current_outset.to_a do
  42                         if vardef.variable == variable then current_outset.remove(vardef)
  43                 end
  44         end
  45
  46         redef fun pretty_print do
  47                 for node, outset in outsets do
  48                         if outset.is_empty then continue
  49                         var values = outset.to_a
  50                         default_comparator.sort(values)
  51                         print "{node.location.line_end}: {values.join(", ")} out of {node.class_name}"
  52                 end
  53         end
  54 end
  55
  56 redef class ANode
  57
  58         # Apply a ReachingDefsAnalysis to `self`.
  59         fun accept_reaching_defs(v: ReachingDefsAnalysis) do accept_forward_analysis(v)
  60 end
  61
  62 redef class AVardeclExpr
  63         redef fun accept_reaching_defs(v) do
  64                 super
  65                 v.kill(variable.as(not null))
  66                 v.gen(variable.as(not null), location)
  67         end
  68 end
  69
  70 redef class AVarAssignExpr
  71         redef fun accept_reaching_defs(v) do
  72                 super
  73                 v.kill(variable.as(not null))
  74                 v.gen(variable.as(not null), location)
  75         end
  76 end
  77
  78 redef class AVarReassignExpr
  79         redef fun accept_reaching_defs(v) do
  80                 super
  81                 v.kill(variable.as(not null))
  82                 v.gen(variable.as(not null), location)
  83         end
  84 end
  85
  86 # A Variable definition.
  87 #
  88 # Associates a variable to the location of its definition.
  89 class VarDef
  90         super Comparable
  91
  92         redef type OTHER: VarDef
  93
  94         # Variable this definition is about.
  95         var variable: Variable
  96
  97         # Location of this definition in the source code.
  98         var location: Location
  99
 100         redef fun ==(o) do
 101                 return o isa OTHER and variable == o.variable and location == o.location
 102         end
 103
 104         redef fun <=>(o) do
 105                 if variable.name == o.variable.name then
 106                         return location.line_start <=> o.location.line_start
 107                 else
 108                         return variable.name <=> o.variable.name
 109                 end
 110         end
 111
 112         redef fun hash do return variable.hash + location.hash
 113         redef fun to_s do return "\{{variable}: {location.line_start}\}"
 114 end