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
|
/* NSC -- new Scala compiler
* Copyright 2005-2013 LAMP/EPFL
* @author Martin Odersky
*/
package scala.tools.nsc
package backend.icode
package analysis
import scala.collection.{ mutable, immutable }
import immutable.ListSet
/**
* Compute liveness information for local variables.
*
* @author Iulian Dragos
*/
abstract class Liveness {
val global: Global
import global._
import icodes._
/** The lattice for this analysis. */
object livenessLattice extends SemiLattice {
type Elem = Set[Local]
object top extends ListSet[Local] with ReferenceEquality
object bottom extends ListSet[Local] with ReferenceEquality
def lub2(exceptional: Boolean)(a: Elem, b: Elem): Elem = a ++ b
}
final class LivenessAnalysis extends DataFlowAnalysis[livenessLattice.type] {
type P = BasicBlock
val lattice = livenessLattice
var method: IMethod = _
val gen: mutable.Map[BasicBlock, Set[Local]] = perRunCaches.newMap()
val kill: mutable.Map[BasicBlock, Set[Local]] = perRunCaches.newMap()
def init(m: IMethod) {
this.method = m
gen.clear()
kill.clear()
m foreachBlock { b =>
val (g, k) = genAndKill(b)
gen += (b -> g)
kill += (b -> k)
}
init {
m foreachBlock { b =>
worklist += b
in(b) = lattice.bottom
out(b) = lattice.bottom
}
}
}
import opcodes._
/** Return the gen and kill sets for this block. */
def genAndKill(b: BasicBlock): (Set[Local], Set[Local]) = {
var genSet = new ListSet[Local]
var killSet = new ListSet[Local]
for (i <- b) i match {
case LOAD_LOCAL(local) if (!killSet(local)) => genSet = genSet + local
case STORE_LOCAL(local) if (!genSet(local)) => killSet = killSet + local
case _ => ()
}
(genSet, killSet)
}
override def run() {
backwardAnalysis(blockTransfer)
if (settings.debug) {
linearizer.linearize(method).foreach(b => if (b != method.startBlock)
assert(lattice.bottom != in(b),
"Block " + b + " in " + this.method + " has input equal to bottom -- not visited?"))
}
}
def blockTransfer(b: BasicBlock, out: lattice.Elem): lattice.Elem =
gen(b) ++ (out -- kill(b))
/** Abstract interpretation for one instruction. Very important:
* liveness is a backward DFA, so this method should be used to compute
* liveness *before* the given instruction `i`.
*/
def interpret(out: lattice.Elem, i: Instruction): lattice.Elem = {
debuglog("- " + i + "\nout: " + out + "\n")
i match {
case LOAD_LOCAL(l) => out + l
case STORE_LOCAL(l) => out - l
case _ => out
}
}
override def toString() =
(method.blocks map (b => "\nlive-in(%s)=%s\nlive-out(%s)=%s".format(b, in(b), b, out(b)))).mkString
} /* Liveness analysis */
}
|
