blob: 93d265caacb16d9fd5a4cf9aad9f43630b2ade19 (
plain) (
blame)
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
|
package scala.tools.nsc.backend.icode.analysis;
import scala.collection.mutable.{Map, HashMap, Set, HashSet};
/** 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 HashSet;
val in: Map[P, lattice.Elem] = new HashMap;
val out: Map[P, lattice.Elem] = new HashMap;
/* Implement this function to initialize the worklist. */
def init(f: => Unit): Unit = {
in.clear; out.clear; worklist.clear;
f;
}
def run: Unit;
/** Implement forward dataflow analysis: the transfer function is
* applied when inputs to a Program point change, to obtain the new
* output value.
*/
def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = {
while (!worklist.isEmpty) {
val point = worklist.elements.next; worklist -= point;
val output = f(point, in(point));
if (out(point) == (lattice.bottom) || output != out(point)) {
out(point) = output;
val succs = point.successors;
succs foreach { p =>
if (!worklist.contains(p))
worklist += p;
in(p) = lattice.lub(p.predecessors map out.apply)
}
}
}
}
}
|