From d159f1420e51fb17e38c0de3690c5d27c870e9ac Mon Sep 17 00:00:00 2001 From: Lukas Rytz Date: Tue, 2 Jun 2015 15:16:47 +0200 Subject: Producers / Consumers Analysis ASM has a built-in `SourceValue` analysis which computes for each value a set of instructions that may possibly have constructed it. The ProdConsAnalyzer class provides additional queries over the result of the SourceValue analysis: - consumers of values - tracking producers / consumers through copying operations (load, store, etc) A fix to (and therefore a new version of) ASM was required. See here: https://github.com/scala/scala-asm/commit/94106a5472 --- .../scala/tools/nsc/backend/jvm/CodeGenTools.scala | 14 +- .../jvm/analysis/NullnessAnalyzerTest.scala | 11 - .../jvm/analysis/ProdConsAnalyzerTest.scala | 249 +++++++++++++++++++++ 3 files changed, 262 insertions(+), 12 deletions(-) create mode 100644 test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala (limited to 'test/junit') diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala index d0ffd06b01..ee9580c1c3 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala @@ -6,7 +6,7 @@ import scala.collection.mutable.ListBuffer import scala.reflect.internal.util.BatchSourceFile import scala.reflect.io.VirtualDirectory import scala.tools.asm.Opcodes -import scala.tools.asm.tree.{ClassNode, MethodNode} +import scala.tools.asm.tree.{AbstractInsnNode, ClassNode, MethodNode} import scala.tools.cmd.CommandLineParser import scala.tools.nsc.io.AbstractFile import scala.tools.nsc.reporters.StoreReporter @@ -15,6 +15,7 @@ import scala.tools.nsc.{Settings, Global} import scala.tools.partest.ASMConverters import scala.collection.JavaConverters._ import scala.tools.testing.TempDir +import AsmUtils._ object CodeGenTools { import ASMConverters._ @@ -151,6 +152,17 @@ object CodeGenTools { def getSingleMethod(classNode: ClassNode, name: String): Method = convertMethod(classNode.methods.asScala.toList.find(_.name == name).get) + /** + * Instructions that match `query` when textified. + * If `query` starts with a `+`, the next instruction is returned. + */ + def findInstr(method: MethodNode, query: String): List[AbstractInsnNode] = { + val useNext = query(0) == '+' + val instrPart = if (useNext) query.drop(1) else query + val insns = method.instructions.iterator.asScala.find(i => textify(i) contains instrPart).toList + if (useNext) insns.map(_.getNext) else insns + } + def assertHandlerLabelPostions(h: ExceptionHandler, instructions: List[Instruction], startIndex: Int, endIndex: Int, handlerIndex: Int): Unit = { val insVec = instructions.toVector assertTrue(h.start == insVec(startIndex) && h.end == insVec(endIndex) && h.handler == insVec(handlerIndex)) diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala index 3a85f03da2..94e776aadb 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala @@ -38,17 +38,6 @@ class NullnessAnalyzerTest extends ClearAfterClass { nullnessAnalyzer } - /** - * Instructions that match `query` when textified. - * If `query` starts with a `+`, the next instruction is returned. - */ - def findInstr(method: MethodNode, query: String): List[AbstractInsnNode] = { - val useNext = query(0) == '+' - val instrPart = if (useNext) query.drop(1) else query - val insns = method.instructions.iterator.asScala.find(i => textify(i) contains instrPart).toList - if (useNext) insns.map(_.getNext) else insns - } - def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: Nullness): Unit = { for (i <- findInstr(method, query)) { val r = analyzer.frameAt(i, method).getValue(index).nullness diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala new file mode 100644 index 0000000000..9af9ef54fc --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala @@ -0,0 +1,249 @@ +package scala.tools.nsc +package backend.jvm +package analysis + +import org.junit.Test +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Assert._ + +import scala.tools.asm.Opcodes +import scala.tools.asm.tree.AbstractInsnNode +import scala.tools.partest.ASMConverters._ +import scala.tools.testing.ClearAfterClass +import CodeGenTools._ +import AsmUtils._ + +object ProdConsAnalyzerTest extends ClearAfterClass.Clearable { + var noOptCompiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:none") + + def clear(): Unit = { + noOptCompiler = null + } +} + +@RunWith(classOf[JUnit4]) +class ProdConsAnalyzerTest extends ClearAfterClass { + ClearAfterClass.stateToClear = ProdConsAnalyzerTest + val noOptCompiler = ProdConsAnalyzerTest.noOptCompiler + + def prodToString(producer: AbstractInsnNode) = producer match { + case p: InitialProducer => p.toString + case p => textify(p) + } + + def testSingleInsn(singletonInsns: Traversable[AbstractInsnNode], expected: String): Unit = { + testInsn(single(singletonInsns), expected) + } + + def testMultiInsns(insns: Traversable[AbstractInsnNode], expected: Traversable[String]): Unit = { + assertTrue(s"Sizes don't match: ${insns.size} vs ${expected.size}", insns.size == expected.size) + for (insn <- insns) { + val txt = prodToString(insn) + assertTrue(s"Instruction $txt not found in ${expected mkString ", "}", expected.exists(txt.contains)) + } + } + + def testInsn(insn: AbstractInsnNode, expected: String): Unit = { + val txt = prodToString(insn) + assertTrue(s"Expected $expected, found $txt", txt contains expected) + } + + def single[T](c: Traversable[T]): T = { + assertTrue(s"Expected singleton collection, got $c", c.size == 1) + c.head + } + + @Test + def parameters(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = this.toString") + val a = new ProdConsAnalyzer(m, "C") + val call = findInstr(m, "INVOKEVIRTUAL").head + + testSingleInsn(a.producersForValueAt(call, 1), "ALOAD 0") // producer of stack value + testSingleInsn(a.producersForInputsOf(call), "ALOAD 0") + + testSingleInsn(a.consumersOfValueAt(call.getNext, 1), "ARETURN") // consumer of `toString` result + testSingleInsn(a.consumersOfOutputsFrom(call), "ARETURN") + + testSingleInsn(a.ultimateConsumersOfValueAt(call.getNext, 1), "ARETURN") + + testSingleInsn(a.initialProducersForValueAt(call, 1), "ParameterProducer") + testSingleInsn(a.producersForValueAt(call, 0), "ParameterProducer") + } + + @Test + def parametersInitialProducer(): Unit = { + // mutates a parameter local (not possible in scala, but in bytecode) + import Opcodes._ + val m = genMethod(descriptor = "(I)I")( + Label(0), + VarOp(ILOAD, 1), + Jump(IFNE, Label(1)), + Op(ICONST_1), + VarOp(ISTORE, 1), + Label(1), + VarOp(ILOAD, 1), + Op(IRETURN), + Label(2) + ) + m.maxLocals = 2 + m.maxStack = 1 + val a = new ProdConsAnalyzer(m, "C") + + val ifne = findInstr(m, "IFNE").head + testSingleInsn(a.producersForValueAt(ifne, 1), "ParameterProducer") + + val ret = findInstr(m, "IRETURN").head + testMultiInsns(a.producersForValueAt(ret, 1), List("ParameterProducer", "ISTORE 1")) + } + + @Test + def branching(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f(x: Int) = { var a = x; if (a == 0) a = 12; a }") + val a = new ProdConsAnalyzer(m, "C") + + val List(ret) = findInstr(m, "IRETURN") + testMultiInsns(a.producersForValueAt(ret, 2), List("ISTORE 2", "ISTORE 2")) + testMultiInsns(a.initialProducersForValueAt(ret, 2), List("BIPUSH 12", "ParameterProducer")) + + val List(bipush) = findInstr(m, "BIPUSH 12") + testSingleInsn(a.consumersOfOutputsFrom(bipush), "ISTORE 2") + testSingleInsn(a.ultimateConsumersOfValueAt(bipush.getNext, 3), "IRETURN") + } + + @Test + def checkCast(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f(o: Object) = o.asInstanceOf[String]") + val a = new ProdConsAnalyzer(m, "C") + assert(findInstr(m, "CHECKCAST java/lang/String").length == 1) + + val List(ret) = findInstr(m, "ARETURN") + testSingleInsn(a.initialProducersForInputsOf(ret), "ParameterProducer(1)") + } + + @Test + def instanceOf(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f(o: Object) = o.isInstanceOf[String]") + val a = new ProdConsAnalyzer(m, "C") + assert(findInstr(m, "INSTANCEOF java/lang/String").length == 1) + + val List(ret) = findInstr(m, "IRETURN") + testSingleInsn(a.initialProducersForInputsOf(ret), "INSTANCEOF") + } + + @Test + def unInitLocal(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f(b: Boolean) = { if (b) { var a = 0; println(a) }; 1 }") + val a = new ProdConsAnalyzer(m, "C") + + val List(store) = findInstr(m, "ISTORE") + val List(call) = findInstr(m, "INVOKEVIRTUAL") + val List(ret) = findInstr(m, "IRETURN") + + testSingleInsn(a.producersForValueAt(store, 2), "UninitializedLocalProducer(2)") + testSingleInsn(a.producersForValueAt(call, 2), "ISTORE") + testMultiInsns(a.producersForValueAt(ret, 2), List("UninitializedLocalProducer", "ISTORE")) + } + + @Test + def dupCopying(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = new Object") + val a = new ProdConsAnalyzer(m, "C") + + val List(newO) = findInstr(m, "NEW") + val List(constr) = findInstr(m, "INVOKESPECIAL") + + testSingleInsn(a.producersForInputsOf(constr), "DUP") + testSingleInsn(a.initialProducersForInputsOf(constr), "NEW") + + testSingleInsn(a.consumersOfOutputsFrom(newO), "DUP") + testMultiInsns(a.ultimateConsumersOfOutputsFrom(newO), List("INVOKESPECIAL", "ARETURN")) + } + + @Test + def multiProducer(): Unit = { + import Opcodes._ + val m = genMethod(descriptor = "(I)I")( + VarOp(ILOAD, 1), + VarOp(ILOAD, 1), + Op(DUP2), + Op(IADD), + Op(SWAP), + VarOp(ISTORE, 1), + Op(IRETURN) + ) + m.maxLocals = 2 + m.maxStack = 4 + val a = new ProdConsAnalyzer(m, "C") + + val List(dup2) = findInstr(m, "DUP2") + val List(add) = findInstr(m, "IADD") + val List(swap) = findInstr(m, "SWAP") + val List(store) = findInstr(m, "ISTORE") + val List(ret) = findInstr(m, "IRETURN") + + testMultiInsns(a.producersForInputsOf(dup2), List("ILOAD", "ILOAD")) + testSingleInsn(a.consumersOfValueAt(dup2.getNext, 4), "IADD") + testSingleInsn(a.consumersOfValueAt(dup2.getNext, 5), "IADD") + testMultiInsns(a.consumersOfOutputsFrom(dup2), List("IADD", "SWAP")) + + testSingleInsn(a.ultimateConsumersOfOutputsFrom(dup2), "IADD") // the 'store' is not here: it's a copying instr, so not an ultimate consumer. + testMultiInsns(a.consumersOfOutputsFrom(swap), List("IRETURN", "ISTORE")) + testSingleInsn(a.ultimateConsumersOfOutputsFrom(swap), "IRETURN") // again, no store + testSingleInsn(a.initialProducersForInputsOf(add), "ParameterProducer(1)") + + testMultiInsns(a.producersForInputsOf(swap), List("IADD", "DUP2")) + testSingleInsn(a.consumersOfValueAt(swap.getNext, 4), "ISTORE") + testSingleInsn(a.consumersOfValueAt(swap.getNext, 3), "IRETURN") + testSingleInsn(a.initialProducersForInputsOf(store), "ParameterProducer(1)") + testSingleInsn(a.initialProducersForInputsOf(ret), "IADD") + } + + @Test + def iincProdCons(): Unit = { + import Opcodes._ + val m = genMethod(descriptor = "(I)I")( + Incr(IINC, 1, 1), // producer and cosumer of local variable 1 + VarOp(ILOAD, 1), + Op(IRETURN) + ) + m.maxLocals = 2 + m.maxStack = 1 + val a = new ProdConsAnalyzer(m, "C") + + val List(inc) = findInstr(m, "IINC") + val List(load) = findInstr(m, "ILOAD") + val List(ret) = findInstr(m, "IRETURN") + + testSingleInsn(a.producersForInputsOf(inc), "ParameterProducer(1)") + testSingleInsn(a.consumersOfOutputsFrom(inc), "ILOAD") + testSingleInsn(a.ultimateConsumersOfOutputsFrom(inc), "IRETURN") + testSingleInsn(a.consumersOfValueAt(inc, 1), "IINC") // parameter value has a single consumer, the IINC + testSingleInsn(a.ultimateConsumersOfValueAt(inc, 1), "IINC") + + testSingleInsn(a.producersForInputsOf(load), "IINC") + testSingleInsn(a.producersForValueAt(load, 1), "IINC") + + testSingleInsn(a.initialProducersForInputsOf(ret), "IINC") + } + + @Test + def copyingInsns(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = 0l.asInstanceOf[Int]") + val a = new ProdConsAnalyzer(m, "C") + + val List(cnst) = findInstr(m, "LCONST_0") + val List(l2i) = findInstr(m, "L2I") // l2i is not a copying instruction + val List(ret) = findInstr(m, "IRETURN") + + testSingleInsn(a.consumersOfOutputsFrom(cnst), "L2I") + testSingleInsn(a.ultimateConsumersOfOutputsFrom(cnst), "L2I") + + testSingleInsn(a.producersForInputsOf(l2i), "LCONST_0") + testSingleInsn(a.initialProducersForInputsOf(l2i), "LCONST_0") + + testSingleInsn(a.consumersOfOutputsFrom(l2i), "IRETURN") + testSingleInsn(a.producersForInputsOf(ret), "L2I") + } +} -- cgit v1.2.3