1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
/* NSC -- new Scala compiler
* Copyright 2005-2010 LAMP/EPFL
* @author Martin Odersky
*/
// $Id$
package scala.tools.nsc
package backend.icode.analysis
import scala.collection.mutable.{Map, HashMap, Set, HashSet, LinkedHashSet}
/** A generic framework for data flow analysis.
*/
trait DataFlowAnalysis[L <: CompleteLattice] {
/** A type for program points. */
type P <: ProgramPoint[P]
val lattice: L
val worklist: Set[P] = new LinkedHashSet
val in: Map[P, lattice.Elem] = new HashMap
val out: Map[P, lattice.Elem] = new HashMap
val visited: HashSet[P] = new HashSet
/** collect statistics? */
var stat = true
/** the number of times we iterated before reaching a fixpoint. */
var iterations = 0
/* Implement this function to initialize the worklist. */
def init(f: => Unit): Unit = {
iterations = 0
in.clear; out.clear; worklist.clear; visited.clear;
f
}
/** Reinitialize, but keep the old solutions. Should be used when reanalyzing the
* same method, after some code transformation.
*/
def reinit(f: => Unit): Unit = {
iterations = 0
worklist.clear; visited.clear;
f
}
def run: Unit
/** Implements forward dataflow analysis: the transfer function is
* applied when inputs to a Program point change, to obtain the new
* output value.
*
* @param f the transfer function.
*/
def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = try {
while (!worklist.isEmpty) {
if (stat) iterations += 1
//Console.println("worklist in: " + worklist);
val point = worklist.iterator.next; worklist -= point; visited += point;
//Console.println("taking out point: " + point + " worklist out: " + worklist);
val output = f(point, in(point))
if ((lattice.bottom == out(point)) || output != out(point)) {
// Console.println("Output changed at " + point
// + " from: " + out(point) + " to: " + output
// + " for input: " + in(point) + " and they are different: " + (output != out(point)))
out(point) = output
val succs = point.successors
succs foreach { p =>
if (!worklist.contains(p))
worklist += p;
if (!in.isDefinedAt(p))
assert(false, "Invalid successor for: " + point + " successor " + p + " does not exist")
// if (!p.exceptionHandlerHeader) {
// println("lubbing " + p.predecessors + " outs: " + p.predecessors.map(out.apply).mkString("\n", "\n", ""))
in(p) = lattice.lub(/*in(p) :: */(p.predecessors map out.apply), p.exceptionHandlerStart)
// }
}
}
}
} catch {
case e: NoSuchElementException =>
Console.println("in: " + in.mkString("", "\n", ""))
Console.println("out: " + out.mkString("", "\n", ""))
e.printStackTrace
Predef.error("Could not find element " + e.getMessage)
}
/** ...
*
* @param f ...
*/
def backwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit =
while (!worklist.isEmpty) {
if (stat) iterations += 1
val point = worklist.iterator.next; worklist -= point
out(point) = lattice.lub(point.successors map in.apply, false) // TODO check for exception handlers
val input = f(point, out(point))
if ((lattice.bottom == in(point)) || input != in(point)) {
in(point) = input
point.predecessors foreach { p =>
if (!worklist.contains(p))
worklist += p;
}
}
}
}
|