-
Notifications
You must be signed in to change notification settings - Fork 0
/
BrilDataFlow.scala
134 lines (108 loc) · 4.26 KB
/
BrilDataFlow.scala
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
129
130
131
132
133
134
package bril.run
import bril.lang.BrilAst._
import bril.lang.BrilParse._
import bril.structure.BrilCfg
import bril.structure.BrilCfg._
import bril.structure.BrilDataFlow._
import scala.util.{Failure, Success}
object BrilDataFlow extends App {
/**
* Live variables analysis.
*/
object LiveVariableFramework extends SetDataFlowFramework[Ident] {
val forward: Boolean = false
def transfer(input: Set[Ident], block: Block)(implicit cfg: BrilCfg): Set[Ident] = {
block.foldRight(input)({
case ValueOp(args, _, _, Some(dest), _) -> vars => (vars - dest) ++ args
case EffectOp(args, _, _) -> vars => vars ++ args
case _ -> vars => vars
})
}
}
/**
* Reaching definitions analysis.
*/
object ReachingDefinitionsFramework extends MapDataFlowFramework[Set[ValueOp]] {
type Result = Map[Ident, Set[ValueOp]]
val forward: Boolean = true
def merge(x: Set[ValueOp], y: Set[ValueOp]): Set[ValueOp] = x ++ y
def transfer(input: Result, block: Block)(implicit cfg: BrilCfg): Result = {
block.foldLeft(input)({
case defs -> (v@ValueOp(_, _, _, Some(dest), _)) => defs + (dest -> Set(v))
case defs -> _ => defs
})
}
}
/**
* Constant propagation analysis.
*/
object ConstantPropagationFramework extends MapDataFlowFramework[Option[Value]] {
type Result = Map[Ident, Option[Value]]
val forward: Boolean = true
def merge(x: Option[Value], y: Option[Value]): Option[Value] = x -> y match {
case Some(x) -> Some(y) if x == y => Some(x)
case _ => None
}
def transfer(input: Result, block: Block)(implicit cfg: BrilCfg): Result = block.foldLeft(input)({
case consts -> Const(v, Some(dest), _) => consts + (dest -> Some(v))
case consts -> ValueOp(_, _, _, Some(dest), _) => consts + (dest -> None)
case consts -> _ => consts
})
}
// read the argument from command line as to what analysis to perform
val analysis = args.headOption
// create the AST from the JSON read from stdin and
// check if the program has been correctly parsed
readProgramFromStdin match {
case Failure(e) =>
println(f"Error occurred parsing program: ${e.getLocalizedMessage}")
System.exit(1)
case Success(program) =>
// perform data flow analysis on the program
// and print the result
program.functions.foreach({ f =>
val cfg = f.toCFG
// perform the analysis and print results
println(f"${f.name}:")
analysis match {
case Some("live") =>
val res = cfg.dataFlow(LiveVariableFramework)
res.foreach({ case label -> (before -> after) =>
val bs = if (before.isEmpty) "∅" else before.mkString(", ")
val as = if (after.isEmpty) "∅" else after.mkString(", ")
println(f" $label:")
println(f" in: $bs")
println(f" out: $as")
})
case Some("defs") =>
val res = cfg.dataFlow(ReachingDefinitionsFramework)
res.foreach({ case label -> (before -> after) =>
println(f" $label:")
if (before.isEmpty) println(" in: ∅") else {
println(" in:")
before.foreach({ case v -> instrs =>
println(f" $v:")
instrs.foreach(i => println(f" ${i.prettyPrint}"))
})
}
if (after.isEmpty) println(" out: ∅") else {
println(" out:")
after.foreach({ case v -> instrs =>
println(f" $v:")
instrs.foreach(i => println(f" ${i.prettyPrint}"))
})
}
})
case _ =>
val res = cfg.dataFlow(ConstantPropagationFramework)
res.foreach({ case label -> (before -> after) =>
val bs = if (before.isEmpty) "∅" else before.collect({ case x -> Some(v) => f"$x: ${v.prettyPrint}" }).mkString(", ")
val as = if (after.isEmpty) "∅" else after.collect({ case x -> Some(v) => f"$x: ${v.prettyPrint}" }).mkString(", ")
println(f" $label:")
println(f" in: $bs")
println(f" out: $as")
})
}
})
}
}