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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
/* NSC -- new Scala compiler
* Copyright 2005-2007 LAMP/EPFL
* @author Martin Odersky
*/
// $Id: $
package scala.tools.nsc.backend.icode.analysis
import compat.StringBuilder
import scala.collection.mutable.{HashMap, Map}
import scala.collection.immutable.{Set, ListSet, HashSet}
/** Compute reaching definitions. We are only interested in reaching
* definitions for local variables, since values on the stack
* behave as-if in SSA form: the closest instruction which produces a value
* on the stack is a reaching definition.
*/
abstract class ReachingDefinitions {
val global: Global
import global._
import icodes._
/** The lattice for reaching definitions. Elements are
* a triple (local variable, basic block, index of instruction of that basic block)
*/
object rdefLattice extends CompleteLattice {
type Definition = (Local, BasicBlock, Int)
type Elem = Set[Definition]
val top: Elem = new ListSet[Definition]() {
override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
}
val bottom: Elem = new ListSet[Definition]() {
override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
}
def lub2(a: Elem, b: Elem): Elem = a incl b
}
class ReachingDefinitionsAnalysis extends DataFlowAnalysis[rdefLattice.type] {
type P = BasicBlock
val lattice = rdefLattice
import lattice.Definition
import lattice.Elem
var method: IMethod = _
val gen: Map[BasicBlock, Set[Definition]] = new HashMap()
val kill:Map[BasicBlock, Set[Local]] = new HashMap()
def init(m: IMethod): Unit = {
this.method = m
gen.clear
kill.clear
for (val b <- m.code.blocks.toList;
val (g, k) = genAndKill(b)) {
gen += b -> g
kill += b -> k
}
init {
worklist ++= m.code.blocks.toList
m.code.blocks.foreach { b =>
in(b) = lattice.bottom
out(b) = lattice.bottom
}
}
}
import opcodes._
def genAndKill(b: BasicBlock): (Set[Definition], Set[Local]) = {
var genSet: Set[Definition] = new HashSet
var killSet: Set[Local] = new HashSet
for (val (i, idx) <- b.toList.zipWithIndex) i match {
case STORE_LOCAL(local) =>
killSet = killSet + local
genSet = updateReachingDefinition(b, idx, genSet)
case _ => ()
}
(genSet, killSet)
}
override def run: Unit = {
forwardAnalysis(blockTransfer)
if (settings.debug.value) {
linearizer.linearize(method).foreach(b => if (b != method.code.startBlock)
assert(lattice.bottom != in(b),
"Block " + b + " in " + this.method + " has input equal to bottom -- not visited?"));
}
}
import opcodes._
def updateReachingDefinition(b: BasicBlock, idx: Int, rd: Set[Definition]): Set[Definition] = {
val STORE_LOCAL(local) = b(idx)
var tmp = local
(rd filter { case (l, _, _) => l != tmp }) + (tmp, b, idx)
}
private def blockTransfer(b: BasicBlock, in: Set[Definition]): Set[Definition] =
(in filter { case (l, _, _) => !kill(b)(l) }) incl gen(b)
/** Return the reaching definitions corresponding to the point after idx. */
def interpret(b: BasicBlock, idx: Int, in: lattice.Elem): Elem = {
var out = in
b(idx) match {
case STORE_LOCAL(l1) =>
out = updateReachingDefinition(b, idx, out)
case _ =>
()
}
out
}
override def toString: String = {
val sb = new compat.StringBuilder
sb.append("rdef: \n")
for (val b <- method.code.blocks)
sb.append("rdef_entry(" + b + ")= " + in(b)).append("\nrdef_exit(" + b + ")= " + out(b))
sb.toString()
}
}
}
|